Fix PR 20100, PR 20115. Remove pass_maybe_create_global_var.

[Diego Novillo <dnovillo at redhat dot com>]

When a function has no call-clobbered variables, any functions it
calls will not be apparently related to each other.  For
instance,

   x = a();
   b();
   x = a();
   return x;

If a() is a pure function, value numbering will think that the
second call to a() is redundant.  However, in this case function
a() returns the value of a global variable that function b()
modifies.  So, removing the second call to a() is wrong.

To avoid this situation, we should create .GLOBAL_VAR when we
find this situation.

I also noticed that in some situations we were creating
.GLOBAL_VAR unnecessarily.  The problem is that once we create
.GLOBAL_VAR, we are stuck with it (this is a limitation that we
should remove, but removing symbols from referenced_vars may be
too intrusive for 4.0).

We were creating .GLOBAL_VAR before comptuing aliases to avoid
the initial SSA creation to deal with too many virtual operands.
So, we do an IL scan, and if we find a lot of function calls, we
would create .GLOBAL_VAR.  A better solution is to just not
bother adding virtual operands at call sites if aliases have not
been computed.  This gives us a minor speedup in operand
scanning and SSA rewriting.

Bootstrapped and tested x86, x86-64, ppc and ia64.


Diego.


	PR tree-optimization/20100
	PR tree-optimization/20115
	* tree-optimize.c (init_tree_optimization_passes): Remove
	pass_maybe_create_global_var.
	* tree-pass.h (pass_maybe_create_global_var): Remove.
	* tree-ssa-alias.c (aliases_computed_p): Declare.
	(struct alias_info): Add field NUM_PURE_CONST_CALLS_FOUND.
	(count_calls_and_maybe_create_global_var): Remove.
	(pass_maybe_create_global_var): Remove.
	(init_alias_info): Do not declare aliases_computed_p.
	(maybe_create_global_var): If the function contains no
	call-clobbered variables and a mix of pure/const and regular
	function calls, create .GLOBAL_VAR.
	Mark all call-clobbered variables for renaming.
	(merge_pointed_to_info): Update comment.
	(add_pointed_to_var): Likewise.
	(is_escape_site): Likewise.
	Accept struct alias_info * instead of size_t *.
	Update all users.
	Update AI->NUM_CALLS_FOUND and AI->NUM_PURE_CONST_CALLS_FOUND
	as necessary.
	* tree-ssa-operands.c (get_call_expr_operands): If
	ALIASES_COMPUTED_P is false, do not add call-clobbering
	operands.
	* tree-ssa.c (init_tree_ssa): Set ALIASES_COMPUTED_P to false.
	(delete_tree_ssa): Likewise.

testsuite/ChangeLog

	PR tree-optimization/20100
	PR tree-optimization/20115
	* gcc.dg/pr20115.c: New test.
	* gcc.dg/pr20115-1.c: New test.
	* gcc.dg/pr20100.c: New test.
	* gcc.dg/tree-ssa/20040517-1.c: Expect virtual operands for
	call-clobbered variables after alias1.

Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.73
diff -d -u -p -r2.73 tree-optimize.c
--- tree-optimize.c	17 Feb 2005 16:19:41 -0000	2.73
+++ tree-optimize.c	23 Feb 2005 02:48:31 -0000
@@ -347,7 +347,6 @@ init_tree_optimization_passes (void)
 
   p = &pass_all_optimizations.sub;
   NEXT_PASS (pass_referenced_vars);
-  NEXT_PASS (pass_maybe_create_global_var);
   NEXT_PASS (pass_build_ssa);
   NEXT_PASS (pass_may_alias);
   NEXT_PASS (pass_rename_ssa_copies);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-pass.h,v
retrieving revision 2.26
diff -d -u -p -r2.26 tree-pass.h
--- tree-pass.h	14 Feb 2005 21:32:14 -0000	2.26
+++ tree-pass.h	23 Feb 2005 02:48:31 -0000
@@ -166,6 +166,5 @@ extern struct tree_opt_pass pass_expand;
 extern struct tree_opt_pass pass_rest_of_compilation;
 extern struct tree_opt_pass pass_fre;
 extern struct tree_opt_pass pass_linear_transform;
-extern struct tree_opt_pass pass_maybe_create_global_var;
 
 #endif /* GCC_TREE_PASS_H */
Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.70
diff -d -u -p -r2.70 tree-ssa-alias.c
--- tree-ssa-alias.c	22 Feb 2005 02:27:35 -0000	2.70
+++ tree-ssa-alias.c	23 Feb 2005 02:48:31 -0000
@@ -43,6 +43,8 @@ Boston, MA 02111-1307, USA.  */
 #include "convert.h"
 #include "params.h"
 
+/* 'true' after aliases have been computed (see compute_may_aliases).  */
+bool aliases_computed_p;
 
 /* Structure to map a variable to its alias set and keep track of the
    virtual operands that will be needed to represent it.  */
@@ -94,6 +96,9 @@ struct alias_info
   /* Number of function calls found in the program.  */
   size_t num_calls_found;
 
+  /* Number of const/pure function calls found in the program.  */
+  size_t num_pure_const_calls_found;
+
   /* Array of counters to keep track of how many times each pointer has
      been dereferenced in the program.  This is used by the alias grouping
      heuristic in compute_flow_insensitive_aliasing.  */
@@ -145,7 +150,7 @@ static void compute_points_to_and_addr_e
 static void compute_flow_sensitive_aliasing (struct alias_info *);
 static void setup_pointers_and_addressables (struct alias_info *);
 static bool collect_points_to_info_r (tree, tree, void *);
-static bool is_escape_site (tree, size_t *);
+static bool is_escape_site (tree, struct alias_info *);
 static void add_pointed_to_var (struct alias_info *, tree, tree);
 static void create_global_var (void);
 static void collect_points_to_info_for (struct alias_info *, tree);
@@ -465,70 +470,12 @@ count_uses_and_derefs (tree ptr, tree st
 }
 
 
-/* Count the number of calls in the function and conditionally
-   create GLOBAL_VAR.   This is performed before translation
-   into SSA (and thus before alias analysis) to avoid compile time
-   and memory utilization explosions in functions with many
-   of calls and call clobbered variables.  */
-
-static void
-count_calls_and_maybe_create_global_var (void)
-{
-  struct alias_info ai;
-  basic_block bb;
-  bool temp;
-
-  memset (&ai, 0, sizeof (struct alias_info));
-
-  /* First count the number of calls in the IL.  */
-  FOR_EACH_BB (bb)
-    {
-      block_stmt_iterator si;
-
-      for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
-        {
-          tree stmt = bsi_stmt (si);
-
-	  if (get_call_expr_in (stmt) != NULL_TREE)
-	    ai.num_calls_found++;
-	}
-    }
-
-  /* If there are no call clobbered variables, then maybe_create_global_var
-     will always create a GLOBAL_VAR.  At this point we do not want that
-     behavior.  So we turn on one bit in CALL_CLOBBERED_VARs, call
-     maybe_create_global_var, then reset the bit to its original state.  */
-  temp = bitmap_bit_p (call_clobbered_vars, 0);
-  bitmap_set_bit (call_clobbered_vars, 0);
-  maybe_create_global_var (&ai);
-  if (!temp)
-    bitmap_clear_bit (call_clobbered_vars, 0);
-}
-
-struct tree_opt_pass pass_maybe_create_global_var = 
-{
-  "maybe_create_global_var",		/* name */
-  NULL,					/* gate */
-  count_calls_and_maybe_create_global_var, /* execute */
-  NULL,					/* sub */
-  NULL,					/* next */
-  0,					/* static_pass_number */
-  TV_TREE_MAY_ALIAS,			/* tv_id */
-  PROP_cfg,				/* properties_required */
-  0,					/* properties_provided */
-  0,					/* properties_destroyed */
-  0,					/* todo_flags_start */
-  0,					/* todo_flags_finish */
-  0					/* letter */
-};
-
 /* Initialize the data structures used for alias analysis.  */
 
 static struct alias_info *
 init_alias_info (void)
 {
   struct alias_info *ai;
-  static bool aliases_computed_p = false;
 
   ai = xcalloc (1, sizeof (struct alias_info));
   ai->ssa_names_visited = sbitmap_alloc (num_ssa_names);
@@ -695,7 +642,7 @@ compute_points_to_and_addr_escape (struc
 	{
 	  bitmap addr_taken;
 	  tree stmt = bsi_stmt (si);
-	  bool stmt_escapes_p = is_escape_site (stmt, &ai->num_calls_found);
+	  bool stmt_escapes_p = is_escape_site (stmt, ai);
 	  bitmap_iterator bi;
 
 	  /* Mark all the variables whose address are taken by the
@@ -1586,22 +1533,56 @@ maybe_create_global_var (struct alias_in
 	  n_clobbered++;
 	}
 
-      if (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD)
+      /* If the number of virtual operands that would be needed to
+	 model all the call-clobbered variables is larger than
+	 GLOBAL_VAR_THRESHOLD, create .GLOBAL_VAR.
+
+	 Also create .GLOBAL_VAR if there are no call-clobbered
+	 variables and the program contains a mixture of pure/const
+	 and regular function calls.  This is to avoid the problem
+	 described in PR 20115:
+
+	      int X;
+	      int func_pure (void) { return X; }
+	      int func_non_pure (int a) { X += a; }
+	      int foo ()
+	      {
+	 	int a = func_pure ();
+		func_non_pure (a);
+		a = func_pure ();
+		return a;
+	      }
+
+	 Since foo() has no call-clobbered variables, there is
+	 no relationship between the calls to func_pure and
+	 func_non_pure.  Since func_pure has no side-effects, value
+	 numbering optimizations elide the second call to func_pure.
+	 So, if we have some pure/const and some regular calls in the
+	 program we create .GLOBAL_VAR to avoid missing these
+	 relations.  */
+      if (ai->num_calls_found * n_clobbered >= (size_t) GLOBAL_VAR_THRESHOLD
+	  || (n_clobbered == 0
+	      && ai->num_calls_found > 0
+	      && ai->num_pure_const_calls_found > 0
+	      && ai->num_calls_found > ai->num_pure_const_calls_found))
 	create_global_var ();
     }
 
-  /* If the function has calls to clobbering functions and .GLOBAL_VAR has
-     been created, make it an alias for all call-clobbered variables.  */
-  if (global_var)
-    EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
-      {
-	tree var = referenced_var (i);
-	if (var != global_var)
-	  {
-	     add_may_alias (var, global_var);
-	     bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
-	  }
-      }
+  /* Mark all call-clobbered symbols for renaming.  Since the initial
+     rewrite into SSA ignored all call sites, we may need to rename
+     .GLOBAL_VAR and the call-clobbered variables.  */
+  EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi)
+    {
+      tree var = referenced_var (i);
+
+      /* If the function has calls to clobbering functions and
+	 .GLOBAL_VAR has been created, make it an alias for all
+	 call-clobbered variables.  */
+      if (global_var && var != global_var)
+	add_may_alias (var, global_var);
+      
+      bitmap_set_bit (vars_to_rename, var_ann (var)->uid);
+    }
 }
 
 
@@ -1762,8 +1743,8 @@ set_pt_malloc (tree ptr)
 
 
 /* Given two different pointers DEST and ORIG.  Merge the points-to
-   information in ORIG into DEST.  AI is as in
-   collect_points_to_info.  */
+   information in ORIG into DEST.  AI contains all the alias
+   information collected up to this point.  */
 
 static void
 merge_pointed_to_info (struct alias_info *ai, tree dest, tree orig)
@@ -1908,7 +1889,7 @@ add_pointed_to_expr (struct alias_info *
 
 /* If VALUE is of the form &DECL, add DECL to the set of variables
    pointed-to by PTR.  Otherwise, add VALUE as a pointed-to expression by
-   PTR.  AI is as in collect_points_to_info.  */
+   PTR.  AI points to the collected alias information.  */
 
 static void
 add_pointed_to_var (struct alias_info *ai, tree ptr, tree value)
@@ -2040,16 +2021,18 @@ collect_points_to_info_r (tree var, tree
 	3- STMT is an assignment to a non-local variable, or
 	4- STMT is a return statement.
 
-   If NUM_CALLS_P is not NULL, the counter is incremented if STMT contains
-   a function call.  */
+   AI points to the alias information collected so far.  */
 
 static bool
-is_escape_site (tree stmt, size_t *num_calls_p)
+is_escape_site (tree stmt, struct alias_info *ai)
 {
-  if (get_call_expr_in (stmt) != NULL_TREE)
+  tree call = get_call_expr_in (stmt);
+  if (call != NULL_TREE)
     {
-      if (num_calls_p)
-	(*num_calls_p)++;
+      ai->num_calls_found++;
+
+      if (!TREE_SIDE_EFFECTS (call))
+	ai->num_pure_const_calls_found++;
 
       return true;
     }
Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.62
diff -d -u -p -r2.62 tree-ssa-operands.c
--- tree-ssa-operands.c	18 Jan 2005 11:36:27 -0000	2.62
+++ tree-ssa-operands.c	23 Feb 2005 02:48:31 -0000
@@ -1460,7 +1460,17 @@ get_call_expr_operands (tree stmt, tree 
   tree op;
   int call_flags = call_expr_flags (expr);
 
-  if (!bitmap_empty_p (call_clobbered_vars))
+  /* If aliases have been computed already, add V_MAY_DEF or V_USE
+     operands for all the symbols that have been found to be
+     call-clobbered.
+     
+     Note that if aliases have not been computed, the global effects
+     of calls will not be included in the SSA web. This is fine
+     because no optimizer should run before aliases have been
+     computed.  By not bothering with virtual operands for CALL_EXPRs
+     we avoid adding superfluous virtual operands, which can be a
+     significant compile time sink (See PR 15855).  */
+  if (aliases_computed_p && !bitmap_empty_p (call_clobbered_vars))
     {
       /* A 'pure' or a 'const' functions never call clobber anything. 
 	 A 'noreturn' function might, but since we don't return anyway 
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa.c,v
retrieving revision 2.77
diff -d -u -p -r2.77 tree-ssa.c
--- tree-ssa.c	17 Feb 2005 16:19:47 -0000	2.77
+++ tree-ssa.c	23 Feb 2005 02:48:31 -0000
@@ -723,6 +723,7 @@ init_tree_ssa (void)
   init_ssanames ();
   init_phinodes ();
   global_var = NULL_TREE;
+  aliases_computed_p = false;
 }
 
 
@@ -767,6 +768,7 @@ delete_tree_ssa (void)
   BITMAP_FREE (addressable_vars);
   addressable_vars = NULL;
   modified_noreturn_calls = NULL;
+  aliases_computed_p = false;
 }
 
 
Index: testsuite/gcc.dg/pr20100.c
===================================================================
RCS file: testsuite/gcc.dg/pr20100.c
diff -N testsuite/gcc.dg/pr20100.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/pr20100.c	23 Feb 2005 02:48:48 -0000
@@ -0,0 +1,32 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+int func_pure (void) __attribute__ ((pure));
+void func_other (int);
+int global_int;
+void abort ();
+void func_other(int a)
+{
+  if (a != global_int)
+   abort ();
+  global_int++;
+}
+
+int func_pure(void)
+{
+  return global_int;
+}
+
+int
+func_loop (int arg)
+{
+ // global_int ++;
+  while (arg--)
+      func_other (func_pure ());
+}
+
+int main(void)
+{
+  func_loop(10);
+  return 0;
+}
Index: testsuite/gcc.dg/pr20115-1.c
===================================================================
RCS file: testsuite/gcc.dg/pr20115-1.c
diff -N testsuite/gcc.dg/pr20115-1.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/pr20115-1.c	23 Feb 2005 02:48:48 -0000
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-dom1" } */
+
+extern int foo (void) __attribute__((pure));
+
+int bar()
+{
+  int a = foo ();
+  a += foo ();
+  return a;
+}
+
+/* Check that we only have one call to foo.  */
+/* { dg-final { scan-tree-dump-times "foo" 1 "dom1" } } */
Index: testsuite/gcc.dg/pr20115.c
===================================================================
RCS file: testsuite/gcc.dg/pr20115.c
diff -N testsuite/gcc.dg/pr20115.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/pr20115.c	23 Feb 2005 02:48:48 -0000
@@ -0,0 +1,28 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+int func_pure (void);
+void func_other (int);
+int global_int;
+int func_pure (void) { return global_int; }
+void func_other (int a)
+{
+  global_int = a + 1;
+}
+int f(void)
+{
+  int a;
+  a = func_pure();
+  func_other (a);
+  a = func_pure (); // We were removing this function call
+  return a;
+}
+void abort (void);
+
+int main(void)
+{
+  global_int = 10;
+  if (f() != 11)
+    abort ();
+  return 0;
+}
Index: testsuite/gcc.dg/tree-ssa/20040517-1.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/tree-ssa/20040517-1.c,v
retrieving revision 1.3
diff -d -u -p -r1.3 20040517-1.c
--- testsuite/gcc.dg/tree-ssa/20040517-1.c	3 Aug 2004 08:22:25 -0000	1.3
+++ testsuite/gcc.dg/tree-ssa/20040517-1.c	23 Feb 2005 02:48:50 -0000
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O1 -fdump-tree-ssa-vops" } */
+/* { dg-options "-O1 -fdump-tree-alias1-vops" } */
 extern void abort (void);
 int a; 
  
@@ -17,5 +17,4 @@ void bar (void) 
    malloc functions may clobber global memory.  Only the function result
    does not alias any other pointer.
    Hence, we must have a VDEF for a before and after the call to foo().  */
-/* { dg-final { scan-tree-dump-times "V_MAY_DEF" 1 "ssa"} } */
-
+/* { dg-final { scan-tree-dump-times "V_MAY_DEF" 1 "alias1"} } */