Re: Patch to fix mark_constant_function

[John Wehle <john at feith dot com>]

> I'm a little concerned about the efficiency of the loop detection code; 
> it appears to be a little heavyweight.

You're probably right.

> It seems to me that you can detect loops in the CFG quickly by doing a
> DFS traversal, giving each node a DFS number.

Here's an implementation using DFS.

This addresses a long standing issue where functions with loops
were considered as constant function candidates ... several people
pointed out that this is undesirable since the function might never
return which counts as a side effect.  This patch passes make
bootstrap and make check on Solaris 7 Intel, Solaris 7 SPARC,
and Compaq Tru64 UNIX 4.0f.

ChangeLog:

Tue Oct 24 00:54:41 EDT 2000  John Wehle  (john@feith.com)

	* alias.c: Include basic-block.h.
	(loop_p): New function.
	(mark_constant_function): Use it.
	* Makefile.in (alias.o): Update dependencies.

Enjoy!

-- John Wehle
------------------8<------------------------8<------------------------
*** gcc/alias.c.ORIGINAL	Fri Oct 20 00:54:31 2000
--- gcc/alias.c	Sun Oct 22 02:54:07 2000
*************** Boston, MA 02111-1307, USA.  */
*** 29,34 ****
--- 29,35 ----
  #include "expr.h"
  #include "regs.h"
  #include "hard-reg-set.h"
+ #include "basic-block.h"
  #include "flags.h"
  #include "output.h"
  #include "toplev.h"
*************** static int aliases_everything_p         
*** 105,110 ****
--- 106,113 ----
  static int write_dependence_p           PARAMS ((rtx, rtx, int));
  static int nonlocal_mentioned_p         PARAMS ((rtx));
  
+ static int loop_p                       PARAMS ((void));
+ 
  /* Set up all info needed to perform alias analysis on memory references.  */
  
  /* Returns the size in bytes of the mode of X.  */
*************** nonlocal_mentioned_p (x)
*** 1863,1868 ****
--- 1866,1961 ----
    return 0;
  }
  
+ /* Return non-zero if a loop (natural or otherwise) is present.
+    Inspired by Depth_First_Search_PP described in:
+ 
+      Advanced Compiler Design and Implementation
+      Steven Muchnick
+      Morgan Kaufmann, 1997
+ 
+    and heavily borrowed from flow_depth_first_order_compute.  */
+ 
+ static int
+ loop_p ()
+ {
+   edge *stack;
+   int *pre;
+   int *post;
+   int sp;
+   int prenum = 1;
+   int postnum = 1;
+   sbitmap visited;
+ 
+   /* Allocate the preorder and postorder number arrays.  */
+   pre = (int *) xcalloc (n_basic_blocks, sizeof (int));
+   post = (int *) xcalloc (n_basic_blocks, sizeof (int));
+ 
+   /* Allocate stack for back-tracking up CFG.  */
+   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
+   sp = 0;
+ 
+   /* Allocate bitmap to track nodes that have been visited.  */
+   visited = sbitmap_alloc (n_basic_blocks);
+ 
+   /* None of the nodes in the CFG have been visited yet.  */
+   sbitmap_zero (visited);
+ 
+   /* Push the first edge on to the stack.  */
+   stack[sp++] = ENTRY_BLOCK_PTR->succ;
+ 
+   while (sp)
+     {
+       edge e;
+       basic_block src;
+       basic_block dest;
+ 
+       /* Look at the edge on the top of the stack.  */
+       e = stack[sp - 1];
+       src = e->src;
+       dest = e->dest;
+ 
+       /* Check if the edge destination has been visited yet.  */
+       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
+ 	{
+ 	  /* Mark that we have visited the destination.  */
+ 	  SET_BIT (visited, dest->index);
+ 
+ 	  pre[dest->index] = prenum++;
+ 
+ 	  if (dest->succ)
+ 	    {
+ 	      /* Since the DEST node has been visited for the first
+ 		 time, check its successors.  */
+ 	      stack[sp++] = dest->succ;
+ 	    }
+ 	  else
+ 	    post[dest->index] = postnum++;
+ 	}
+       else
+ 	{
+ 	  if (dest != EXIT_BLOCK_PTR
+ 	      && pre[src->index] >= pre[dest->index]
+ 	      && post[dest->index] == 0)
+ 	    break;
+ 
+ 	  if (! e->succ_next && src != ENTRY_BLOCK_PTR)
+ 	    post[src->index] = postnum++;
+ 
+ 	  if (e->succ_next)
+ 	    stack[sp - 1] = e->succ_next;
+ 	  else
+ 	    sp--;
+ 	}
+     }
+ 
+   free (pre);
+   free (post);
+   free (stack);
+   sbitmap_free (visited);
+ 
+   return sp;
+ }
+ 
  /* Mark the function if it is constant.  */
  
  void
*************** mark_constant_function ()
*** 1876,1881 ****
--- 1969,1978 ----
        || DECL_IS_PURE (current_function_decl)
        || TREE_THIS_VOLATILE (current_function_decl)
        || TYPE_MODE (TREE_TYPE (current_function_decl)) == VOIDmode)
+     return;
+ 
+   /* A loop might not return which counts as a side effect.  */
+   if (loop_p ())
      return;
  
    nonlocal_mentioned = 0;
*** gcc/Makefile.in.ORIGINAL	Sat Oct 21 19:21:43 2000
--- gcc/Makefile.in	Tue Oct 24 00:52:28 2000
*************** reorg.o : reorg.c $(CONFIG_H) system.h $
*** 1398,1405 ****
     $(BASIC_BLOCK_H) $(REGS_H) insn-config.h $(INSN_ATTR_H) insn-flags.h \
     $(RECOG_H) function.h flags.h output.h $(EXPR_H) toplev.h
  alias.o : alias.c $(CONFIG_H) system.h $(RTL_H) flags.h hard-reg-set.h \
!    $(REGS_H) toplev.h output.h $(EXPR_H) insn-flags.h $(GGC_H) function.h \
!    cselib.h $(TREE_H)
  regmove.o : regmove.c $(CONFIG_H) system.h $(RTL_H) insn-config.h \
     $(RECOG_H) output.h $(REGS_H) hard-reg-set.h flags.h function.h \
     $(EXPR_H) insn-flags.h $(BASIC_BLOCK_H) toplev.h
--- 1398,1405 ----
     $(BASIC_BLOCK_H) $(REGS_H) insn-config.h $(INSN_ATTR_H) insn-flags.h \
     $(RECOG_H) function.h flags.h output.h $(EXPR_H) toplev.h
  alias.o : alias.c $(CONFIG_H) system.h $(RTL_H) flags.h hard-reg-set.h \
!    $(BASIC_BLOCK_H) $(REGS_H) toplev.h output.h $(EXPR_H) insn-flags.h \
!    $(GGC_H) function.h cselib.h $(TREE_H)
  regmove.o : regmove.c $(CONFIG_H) system.h $(RTL_H) insn-config.h \
     $(RECOG_H) output.h $(REGS_H) hard-reg-set.h flags.h function.h \
     $(EXPR_H) insn-flags.h $(BASIC_BLOCK_H) toplev.h
-------------------------------------------------------------------------
|   Feith Systems  |   Voice: 1-215-646-8000  |  Email: john@feith.com  |
|    John Wehle    |     Fax: 1-215-540-5495  |                         |
-------------------------------------------------------------------------