Re: Fix alias problems in PR19633

[Diego Novillo <dnovillo at redhat dot com>]

Diego Novillo wrote:

> Mainline is broken on x86-64 ATM (this is unrelated to my patch), so I 
> will not be applying the patch until I can get a clean bootstrap on x86-64.
I've committed the attached patch.  It includes a small tweak to the 
alias analyzer to avoid setting PT_ANYTHING on pointers that are 
assigned the NULL value.

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


Diego.
2005-02-01  Diego Novillo  <dnovillo@redhat.com>

	PR tree-optimization/19633
	* tree-flow.h (struct ptr_info_def): Add field 'pt_null'.
	* tree-ssa-alias.c (init_alias_info): Initialize.
	(merge_pointed_to_info): Set.
	(add_pointed_to_expr): Set pt_null if EXPR is a NULL pointer.
	(dump_points_to_info_for): Show value of pt_null.
	(struct count_ptr_d): Declare.
	(find_ptr_dereference): Remove.
	(ptr_is_dereferenced_by): Remove.
	(count_ptr_derefs): New local function.
	(count_uses_and_derefs): New local function.
	(compute_points_to_and_addr_escape): Call it.  If the number
	of dereferences is greater than zero, mark the pointer as
	dereferenced.  If there are fewer dereferences than uses of
	the pointer, the pointer's value escapes.

testsuite/ChangeLog

	PR tree-optimization/19633
	* testsuite/gcc.dg/pr19633-1.c: New test.
	* testsuite/gcc.dg/pr19633.c: Tweak to make pointer point
	to NULL or a symbol.

Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.78
diff -d -u -p -r2.78 tree-flow.h
--- tree-flow.h	24 Jan 2005 20:47:43 -0000	2.78
+++ tree-flow.h	1 Feb 2005 20:14:54 -0000
@@ -66,6 +66,9 @@ struct ptr_info_def GTY(())
   /* Nonzero if this pointer points to a global variable.  */
   unsigned int pt_global_mem : 1;
 
+  /* Nonzero if this pointer points to NULL.  */
+  unsigned int pt_null : 1;
+
   /* Set of variables that this pointer may point to.  */
   bitmap pt_vars;
 
Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.67
diff -d -u -p -r2.67 tree-ssa-alias.c
--- tree-ssa-alias.c	27 Jan 2005 04:45:07 -0000	2.67
+++ tree-ssa-alias.c	1 Feb 2005 20:14:55 -0000
@@ -149,7 +149,6 @@ static bool is_escape_site (tree, size_t
 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);
-static bool ptr_is_dereferenced_by (tree, tree, bool *);
 static void maybe_create_global_var (struct alias_info *ai);
 static void group_aliases (struct alias_info *);
 static void set_pt_anything (tree ptr);
@@ -359,6 +358,113 @@ struct tree_opt_pass pass_may_alias = 
   0					/* letter */
 };
 
+
+/* Data structure used to count the number of dereferences to PTR
+   inside an expression.  */
+struct count_ptr_d
+{
+  tree ptr;
+  unsigned count;
+};
+
+
+/* Helper for count_uses_and_derefs.  Called by walk_tree to look for
+   (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
+
+static tree
+count_ptr_derefs (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
+{
+  struct count_ptr_d *count_p = (struct count_ptr_d *) data;
+
+  if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr)
+    count_p->count++;
+
+  return NULL_TREE;
+}
+
+
+/* Count the number of direct and indirect uses for pointer PTR in
+   statement STMT.  The two counts are stored in *NUM_USES_P and
+   *NUM_DEREFS_P respectively.  *IS_STORE_P is set to 'true' if at
+   least one of those dereferences is a store operation.  */
+
+static void
+count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p,
+		       unsigned *num_derefs_p, bool *is_store)
+{
+  ssa_op_iter i;
+  tree use;
+
+  *num_uses_p = 0;
+  *num_derefs_p = 0;
+  *is_store = false;
+
+  /* Find out the total number of uses of PTR in STMT.  */
+  FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
+    if (use == ptr)
+      (*num_uses_p)++;
+
+  /* Now count the number of indirect references to PTR.  This is
+     truly awful, but we don't have much choice.  There are no parent
+     pointers inside INDIRECT_REFs, so an expression like
+     '*x_1 = foo (x_1, *x_1)' needs to be traversed piece by piece to
+     find all the indirect and direct uses of x_1 inside.  The only
+     shortcut we can take is the fact that GIMPLE only allows
+     INDIRECT_REFs inside the expressions below.  */
+  if (TREE_CODE (stmt) == MODIFY_EXPR
+      || (TREE_CODE (stmt) == RETURN_EXPR
+	  && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
+      || TREE_CODE (stmt) == ASM_EXPR
+      || TREE_CODE (stmt) == CALL_EXPR)
+    {
+      tree lhs, rhs;
+
+      if (TREE_CODE (stmt) == MODIFY_EXPR)
+	{
+	  lhs = TREE_OPERAND (stmt, 0);
+	  rhs = TREE_OPERAND (stmt, 1);
+	}
+      else if (TREE_CODE (stmt) == RETURN_EXPR)
+	{
+	  tree e = TREE_OPERAND (stmt, 0);
+	  lhs = TREE_OPERAND (e, 0);
+	  rhs = TREE_OPERAND (e, 1);
+	}
+      else if (TREE_CODE (stmt) == ASM_EXPR)
+	{
+	  lhs = ASM_OUTPUTS (stmt);
+	  rhs = ASM_INPUTS (stmt);
+	}
+      else
+	{
+	  lhs = NULL_TREE;
+	  rhs = stmt;
+	}
+
+      if (lhs && EXPR_P (lhs))
+	{
+	  struct count_ptr_d count;
+	  count.ptr = ptr;
+	  count.count = 0;
+	  walk_tree (&lhs, count_ptr_derefs, &count, NULL);
+	  *is_store = true;
+	  *num_derefs_p = count.count;
+	}
+
+      if (rhs && EXPR_P (rhs))
+	{
+	  struct count_ptr_d count;
+	  count.ptr = ptr;
+	  count.count = 0;
+	  walk_tree (&rhs, count_ptr_derefs, &count, NULL);
+	  *num_derefs_p += count.count;
+	}
+    }
+
+  gcc_assert (*num_uses_p >= *num_derefs_p);
+}
+
+
 /* 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
@@ -495,6 +601,7 @@ init_alias_info (void)
 		 tag will need to be created in create_name_tags.  */
 	      pi->pt_anything = 0;
 	      pi->pt_malloc = 0;
+	      pi->pt_null = 0;
 	      pi->value_escapes_p = 0;
 	      pi->is_dereferenced = 0;
 	      if (pi->pt_vars)
@@ -561,81 +668,6 @@ collect_points_to_info_for (struct alias
 }
 
 
-/* Helper for ptr_is_dereferenced_by.  Called by walk_tree to look for
-   (ALIGN/MISALIGNED_)INDIRECT_REF nodes for the pointer passed in DATA.  */
-
-static tree
-find_ptr_dereference (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data)
-{
-  tree ptr = (tree) data;
-
-  if (INDIRECT_REF_P (*tp)
-      && TREE_OPERAND (*tp, 0) == ptr)
-    return *tp;
-
-  return NULL_TREE;
-}
-
-
-/* Return true if STMT contains (ALIGN/MISALIGNED_)INDIRECT_REF <PTR>.  
-   *IS_STORE is set to 'true' if the dereference is on the LHS of an 
-   assignment.  */
-
-static bool
-ptr_is_dereferenced_by (tree ptr, tree stmt, bool *is_store)
-{
-  *is_store = false;
-
-  if (TREE_CODE (stmt) == MODIFY_EXPR
-      || (TREE_CODE (stmt) == RETURN_EXPR
-	  && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR))
-    {
-      tree e, lhs, rhs;
-
-      e = (TREE_CODE (stmt) == RETURN_EXPR) ? TREE_OPERAND (stmt, 0) : stmt;
-      lhs = TREE_OPERAND (e, 0);
-      rhs = TREE_OPERAND (e, 1);
-
-      if (EXPR_P (lhs)
-	  && walk_tree (&lhs, find_ptr_dereference, ptr, NULL))
-	{
-	  *is_store = true;
-	  return true;
-	}
-      else if (EXPR_P (rhs)
-	       && walk_tree (&rhs, find_ptr_dereference, ptr, NULL))
-	{
-	  return true;
-	}
-    }
-  else if (TREE_CODE (stmt) == ASM_EXPR)
-    {
-      if (walk_tree (&ASM_OUTPUTS (stmt), find_ptr_dereference, ptr, NULL)
-	  || walk_tree (&ASM_CLOBBERS (stmt), find_ptr_dereference, ptr, NULL))
-	{
-	  *is_store = true;
-	  return true;
-	}
-      else if (walk_tree (&ASM_INPUTS (stmt), find_ptr_dereference, ptr, NULL))
-	{
-	  return true;
-	}
-    }
-  else
-    {
-      /* CALL_EXPRs may also contain pointer dereferences for types
-	 that are not GIMPLE register types.  If the CALL_EXPR is on
-	 the RHS of an assignment, it will be handled by the
-	 MODIFY_EXPR handler above.  */
-      tree call = get_call_expr_in (stmt);
-      if (call && walk_tree (&call, find_ptr_dereference, ptr, NULL))
-	return true;
-    }
-
-  return false;
-}
-
-
 /* Traverse use-def links for all the pointers in the program to collect
    address escape and points-to information.
    
@@ -689,6 +721,7 @@ compute_points_to_and_addr_escape (struc
 	      var_ann_t v_ann = var_ann (SSA_NAME_VAR (op));
 	      struct ptr_info_def *pi;
 	      bool is_store;
+	      unsigned num_uses, num_derefs;
 
 	      /* If the operand's variable may be aliased, keep track
 		 of how many times we've referenced it.  This is used
@@ -706,7 +739,10 @@ compute_points_to_and_addr_escape (struc
 	      collect_points_to_info_for (ai, op);
 
 	      pi = SSA_NAME_PTR_INFO (op);
-	      if (ptr_is_dereferenced_by (op, stmt, &is_store))
+	      count_uses_and_derefs (op, stmt, &num_uses, &num_derefs,
+				     &is_store);
+
+	      if (num_derefs > 0)
 		{
 		  /* Mark OP as dereferenced.  In a subsequent pass,
 		     dereferenced pointers that point to a set of
@@ -728,12 +764,13 @@ compute_points_to_and_addr_escape (struc
 		  else
 		    bitmap_set_bit (ai->dereferenced_ptrs_load, v_ann->uid);
 		}
-	      else if (stmt_escapes_p)
+
+	      if (stmt_escapes_p && num_derefs < num_uses)
 		{
-		  /* Note that even if STMT is an escape point, pointer OP
-		     will not escape if it is being dereferenced.  That's
-		     why we only check for escape points if OP is not
-		     dereferenced by STMT.  */
+		  /* If STMT is an escape point and STMT contains at
+		     least one direct use of OP, then the value of OP
+		     escapes and so the pointed-to variables need to
+		     be marked call-clobbered.  */
 		  pi->value_escapes_p = 1;
 
 		  /* If the statement makes a function call, assume
@@ -1742,6 +1779,8 @@ merge_pointed_to_info (struct alias_info
 
   if (orig_pi)
     {
+      gcc_assert (orig_pi != dest_pi);
+
       /* Notice that we never merge PT_MALLOC.  This attribute is only
 	 true if the pointer is the result of a malloc() call.
 	 Otherwise, we can end up in this situation:
@@ -1761,13 +1800,12 @@ merge_pointed_to_info (struct alias_info
 	 create_name_tags is not smart enough to determine that the
 	 two come from the same malloc call.  Copy propagation before
 	 aliasing should cure this.  */
-      gcc_assert (orig_pi != dest_pi);
-      
       dest_pi->pt_malloc = 0;
-
       if (orig_pi->pt_malloc || orig_pi->pt_anything)
 	set_pt_anything (dest);
 
+      dest_pi->pt_null |= orig_pi->pt_null;
+
       if (!dest_pi->pt_anything
 	  && orig_pi->pt_vars
 	  && !bitmap_empty_p (orig_pi->pt_vars))
@@ -1853,6 +1891,11 @@ add_pointed_to_expr (struct alias_info *
 	       && TREE_CODE (op1) != INTEGER_CST))
 	set_pt_anything (ptr);
     }
+  else if (integer_zerop (expr))
+    {
+      /* EXPR is the NULL pointer.  Mark PTR as pointing to NULL.  */
+      SSA_NAME_PTR_INFO (ptr)->pt_null = 1;
+    }
   else
     {
       /* If we can't recognize the expression, assume that PTR may
@@ -2356,6 +2399,9 @@ dump_points_to_info_for (FILE *file, tre
       if (pi->pt_malloc)
 	fprintf (file, ", points-to malloc");
 
+      if (pi->pt_null)
+	fprintf (file, ", points-to NULL");
+
       if (pi->pt_vars)
 	{
 	  unsigned ix;
@@ -2511,4 +2557,3 @@ may_be_aliased (tree var)
 
   return true;
 }
-
Index: testsuite/gcc.dg/pr19633-1.c
===================================================================
RCS file: testsuite/gcc.dg/pr19633-1.c
diff -N testsuite/gcc.dg/pr19633-1.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/pr19633-1.c	1 Feb 2005 20:14:57 -0000
@@ -0,0 +1,66 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+extern void abort (void);
+
+struct S
+{
+  int w, x, y, z;
+};
+
+struct T
+{
+  int r;
+  struct S s;
+};
+
+struct S bar (struct S x, struct S *y)
+{
+  y->w = 4;
+  return *y;
+}
+
+void
+foo (int a, struct T b)
+{
+  struct S x;
+  struct S *c = &x;
+  if (a)
+    c = &b.s;
+  b.s.w = 3;
+  /* This call should be marked as clobbering 'x' and 'b'.  */
+  *c = bar (*c, c);
+  if (b.s.w == 3)
+    abort ();
+}
+
+float Y;
+
+struct S bar1 (struct S x, struct S y)
+{
+  Y = 4;
+  return x;
+}
+
+void
+foo1 (int a, struct T b)
+{
+  struct S x;
+  struct S *c = &x;
+  float z, *k = &z;
+  if (a)
+    c = &b.s;
+  b.s.w = 3;
+  /* This call should NOT be marked as clobbering 'x' and 'b'.  */
+  x = bar1 (*c, *c);
+  if (b.s.w != 3)
+    link_error ();
+}
+
+int main ()
+{
+  struct T b;
+  foo (3, b);
+  foo1 (3, b);
+  return 0;
+}
Index: testsuite/gcc.dg/pr19633.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/testsuite/gcc.dg/pr19633.c,v
retrieving revision 1.1
diff -d -u -p -r1.1 pr19633.c
--- testsuite/gcc.dg/pr19633.c	27 Jan 2005 04:45:19 -0000	1.1
+++ testsuite/gcc.dg/pr19633.c	1 Feb 2005 20:14:57 -0000
@@ -15,12 +15,21 @@ struct T
 void
 foo (int a, struct T b)
 {
-  struct S x;
-  struct S *c = &x;
+  struct S *c = 0;
+
   if (a)
     c = &b.s;
+
   b.s.w = 3;
+
+  /* Since 'c' may be pointing to NULL here, we used to flag it as
+     pointing anywhere, which was forcing the aliaser to mark as
+     call-clobbered every other variable pointed-to by 'c' ('b' in
+     this case).  This, in turn, caused the insertion of V_MAY_DEFs
+     for 'b' at this call-site, which prevented constant propagation
+     from 'b.s.w = 3' to 'if (b.s.w != 3)'.  */
   bar (*c, a);
+
   if (b.s.w != 3)
     link_error ();
 }