Fix PR 15555

[Diego Novillo <dnovillo at redhat dot com>]

Now we should really be able to schedule pass_may_aliases more than
once.  I added a second call after DOM2 so that we rebuild name tags
after jump threading.

All this is changing soon, so I didn't spend a lot of time doing
timings.

Bootstrapped and tested on x86.


Diego.


	* tree-dfa.c (dump_variable): If the variable is a pointer
	SSA_NAME, also dump its points-to information.
	* tree-flow.h (struct ptr_info_def): Add field
	is_dereferenced.
	(dump_points_to_info_for): Declare.
	(debug_points_to_info_for): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Add a
	second alias analysis pass after DOM2.
	Move pass_del_pta to a later spot.
	* tree-ssa-alias.c (compute_points_to_and_addr_escape): Do not
	create a name tags when we find a dereferenced pointer.  Just
	mark the pointer dereferenced.
	(collect_points_to_info_for): Move code to clear points-to
	information to create_name_tags.
	(create_name_tags): New function.
	(compute_flow_sensitive_aliasing): Call it.
	(setup_pointers_and_addressables): Mark type tags for renaming
	here instead of ...
	(create_memory_tag): ... here.
	(merge_pointed_to_info): Do not merge PT_MALLOC attributes.
	(dump_points_to_info_for): Declare extern.
	(debug_points_to_info_for): New function.

Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-dfa.c,v
retrieving revision 2.15
diff -d -c -p -d -u -p -r2.15 tree-dfa.c
--- tree-dfa.c	25 Jun 2004 18:30:09 -0000	2.15
+++ tree-dfa.c	9 Jul 2004 15:10:09 -0000
@@ -534,6 +534,13 @@ void
 dump_variable (FILE *file, tree var)
 {
   var_ann_t ann;
+  
+  if (TREE_CODE (var) == SSA_NAME)
+    {
+      if (POINTER_TYPE_P (TREE_TYPE (var)))
+	dump_points_to_info_for (file, var);
+      var = SSA_NAME_VAR (var);
+    }
 
   if (var == NULL_TREE)
     {
@@ -542,9 +549,6 @@ dump_variable (FILE *file, tree var)
     }
 
   print_generic_expr (file, var, dump_flags);
-  
-  if (TREE_CODE (var) == SSA_NAME)
-    var = SSA_NAME_VAR (var);
 
   ann = var_ann (var);
 
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.21
diff -d -c -p -d -u -p -r2.21 tree-flow.h
--- tree-flow.h	9 Jul 2004 03:19:13 -0000	2.21
+++ tree-flow.h	9 Jul 2004 15:10:09 -0000
@@ -59,6 +59,9 @@ struct ptr_info_def GTY(())
   /* Nonzero if the value of this pointer escapes the current function.  */
   unsigned int value_escapes_p : 1;
 
+  /* Nonzero if this pointer is dereferenced.  */
+  unsigned int is_dereferenced : 1;
+
   /* Set of variables that this pointer may point to.  */
   bitmap pt_vars;
 
@@ -550,6 +553,8 @@ extern void dump_alias_info (FILE *);
 extern void debug_alias_info (void);
 extern void dump_points_to_info (FILE *);
 extern void debug_points_to_info (void);
+extern void dump_points_to_info_for (FILE *, tree);
+extern void debug_points_to_info_for (tree);
 
 /* Call-back function for walk_use_def_chains().  At each reaching
    definition, a function with this prototype is called.  */
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 2.26
diff -d -c -p -d -u -p -r2.26 tree-optimize.c
--- tree-optimize.c	7 Jul 2004 03:19:55 -0000	2.26
+++ tree-optimize.c	9 Jul 2004 15:10:09 -0000
@@ -294,7 +294,6 @@ init_tree_optimization_passes (void)
   NEXT_PASS (pass_may_alias);
   NEXT_PASS (pass_tail_recursion);
   NEXT_PASS (pass_ch);
-  NEXT_PASS (pass_del_pta);
   NEXT_PASS (pass_profile);
   NEXT_PASS (pass_lower_complex);
   NEXT_PASS (pass_sra);
@@ -303,6 +302,7 @@ init_tree_optimization_passes (void)
   NEXT_PASS (DUP_PASS (pass_redundant_phi));
   NEXT_PASS (DUP_PASS (pass_dce));
   NEXT_PASS (pass_dse);
+  NEXT_PASS (DUP_PASS (pass_may_alias));
   NEXT_PASS (DUP_PASS (pass_forwprop));
   NEXT_PASS (DUP_PASS (pass_phiopt));
   NEXT_PASS (pass_ccp);
@@ -320,6 +320,7 @@ init_tree_optimization_passes (void)
   NEXT_PASS (pass_tail_calls);
   NEXT_PASS (pass_late_warn_uninitialized);
   NEXT_PASS (pass_warn_function_return);
+  NEXT_PASS (pass_del_pta);
   NEXT_PASS (pass_del_ssa);
   NEXT_PASS (pass_nrv);
   NEXT_PASS (pass_remove_useless_vars);
Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.9
diff -d -c -p -d -u -p -r2.9 tree-ssa-alias.c
--- tree-ssa-alias.c	8 Jul 2004 06:34:22 -0000	2.9
+++ tree-ssa-alias.c	9 Jul 2004 15:10:09 -0000
@@ -432,21 +442,9 @@ collect_points_to_info_for (struct alias
 
   if (!bitmap_bit_p (ai->ssa_names_visited, SSA_NAME_VERSION (ptr)))
     {
-      struct ptr_info_def *pi;
-
       bitmap_set_bit (ai->ssa_names_visited, SSA_NAME_VERSION (ptr));
       walk_use_def_chains (ptr, collect_points_to_info_r, ai);
-
       VARRAY_PUSH_TREE (ai->processed_ptrs, ptr);
-
-      /* If we could not determine where PTR was pointing to, clear all the
-	 other points-to information.  */
-      pi = SSA_NAME_PTR_INFO (ptr);
-      if (pi->pt_anything)
-	{
-	  pi->pt_malloc = 0;
-	  pi->pt_vars = NULL;
-	}
     }
 }
 
@@ -609,15 +607,12 @@ compute_points_to_and_addr_escape (struc
 	      if (ptr_is_dereferenced_by (op, stmt, &is_store))
 		{
 		  /* If we found OP to point to a set of variables or
-		     malloc, then create a name memory tag for it.  This
-		     gives more precise aliasing information, which helps
-		     the optimizers.
-
-		     FIXME: Cycles in the SSA web and the lack of SSA 
-		     information for structures will prevent the creation
-		     of name tags.  Find ways around this limitation.  */
+		     malloc, then mark it as being dereferenced.  In a
+		     subsequent pass, dereferenced pointers that point
+		     to a set of variables will be assigned a name tag
+		     to alias all the variables OP points to.  */
 		  if (pi->pt_malloc || pi->pt_vars)
-		    pi->name_mem_tag = get_nmt_for (op);
+		    pi->is_dereferenced = 1;
 
 		  /* Keep track of how many time we've dereferenced each
 		     pointer.  Again, we don't need to grow
@@ -695,6 +690,92 @@ compute_points_to_and_addr_escape (struc
 }
 
 
+/* Create name tags for all the pointers that have been dereferenced.
+   We only create a name tag for a pointer P if P is found to point to
+   a set of variables (so that we can alias them to *P) or if it is
+   the result of a call to malloc (which means that P cannot point to
+   anything else nor alias any other variable).
+
+   If two pointers P and Q point to the same set of variables, they
+   are assigned the same name tag.  */
+
+static void
+create_name_tags (struct alias_info *ai)
+{
+  size_t i;
+
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
+    {
+      tree ptr = VARRAY_TREE (ai->processed_ptrs, i);
+      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
+
+      /* If we could not determine where PTR was pointing to, clear
+	 all the other points-to flags.  */
+      pi = SSA_NAME_PTR_INFO (ptr);
+      if (pi->pt_anything)
+	{
+	  pi->pt_malloc = 0;
+	  pi->pt_vars = NULL;
+	  pi->is_dereferenced = 0;
+	}
+
+      if (!pi->is_dereferenced)
+	continue;
+
+      if (pi->pt_vars)
+	{
+	  size_t j;
+
+	  /* If PTR points to a set of variables, check if we don't
+	     have another pointer Q with the same points-to set before
+	     creating a tag.  If so, use Q's tag instead of creating a
+	     new one.
+
+	     This is important for not creating unnecessary symbols
+	     and also for copy propagation.  If we ever need to
+	     propagate PTR into Q or vice-versa, we would run into
+	     problems if they both had different name tags because
+	     they would have different SSA version numbers (which
+	     would force us to take the name tags in and out of SSA).  */
+	  pi->name_mem_tag = NULL_TREE;
+	  for (j = 0; j < i; j++)
+	    {
+	      tree q = VARRAY_TREE (ai->processed_ptrs, j);
+	      struct ptr_info_def *qi = SSA_NAME_PTR_INFO (q);
+
+	      if (qi
+		  && qi->pt_vars
+		  && qi->name_mem_tag
+		  && bitmap_equal_p (pi->pt_vars, qi->pt_vars))
+		{
+		  pi->name_mem_tag = qi->name_mem_tag;
+		  break;
+		}
+	    }
+
+	  if (pi->name_mem_tag == NULL_TREE)
+	    pi->name_mem_tag = get_nmt_for (ptr);
+	}
+      else if (pi->pt_malloc)
+	{
+	  /* Otherwise, create a unique name tag for this pointer.  */
+	  pi->name_mem_tag = get_nmt_for (ptr);
+	}
+      else
+	{
+	  /* Only pointers that may point to malloc or other variables
+	     may receive a name tag.  If the pointer does not point to
+	     a known spot, we should use type tags.  */
+	  abort ();
+	}
+
+      /* Mark the new name tag for renaming.  */
+      bitmap_set_bit (vars_to_rename, var_ann (pi->name_mem_tag)->uid);
+    }
+}
+
+
+
 /* For every pointer P_i in AI->PROCESSED_PTRS, create may-alias sets for
    the name memory tag (NMT) associated with P_i.  If P_i escapes, then its
    name tag and the variables it points-to are call-clobbered.  Finally, if
@@ -708,6 +789,8 @@ compute_flow_sensitive_aliasing (struct 
 {
   size_t i;
 
+  create_name_tags (ai);
+
   for (i = 0; i < VARRAY_ACTIVE_SIZE (ai->processed_ptrs); i++)
     {
       size_t j;
@@ -1173,10 +1256,10 @@ setup_pointers_and_addressables (struct 
       tree var = referenced_var (i);
       var_ann_t v_ann = var_ann (var);
 
-      /* Name memory tags already have flow-sensitive aliasing information, so
-	 they need not be processed by compute_may_aliases.  Similarly,
-	 type memory tags are already accounted for when we process their
-	 associated pointer.  */
+      /* Name memory tags already have flow-sensitive aliasing
+	 information, so they need not be processed by
+	 compute_may_aliases.  Similarly, type memory tags are already
+	 accounted for when we process their associated pointer.  */
       if (v_ann->mem_tag_kind != NOT_A_TAG)
 	continue;
 
@@ -1192,8 +1275,9 @@ setup_pointers_and_addressables (struct 
 	      && v_ann->mem_tag_kind == NOT_A_TAG
 	      && !needs_to_live_in_memory (var))
 	    {
-	      /* The address of VAR is not needed, remove the addressable bit,
-	         so that it can be optimized as a regular variable.  */
+	      /* The address of VAR is not needed, remove the
+		 addressable bit, so that it can be optimized as a
+		 regular variable.  */
 	      mark_non_addressable (var);
 
 	      /* Since VAR is now a regular GIMPLE register, we will need
@@ -1227,12 +1311,18 @@ setup_pointers_and_addressables (struct 
 	  tree tag = v_ann->type_mem_tag;
 	  var_ann_t t_ann;
 
-	  /* If pointer VAR still doesn't have a memory tag associated with it,
-	     create it now or re-use an existing one.  */
+	  /* If pointer VAR still doesn't have a memory tag associated
+	     with it, create it now or re-use an existing one.  */
 	  if (tag == NULL_TREE)
 	    tag = get_tmt_for (var, ai);
 	  t_ann = var_ann (tag);
 
+	  /* The type tag will need to be renamed into SSA afterwards.
+	     Note that we cannot do this inside get_tmt_for because
+	     aliasing may run multiple times and we only create type
+	     tags the first time.  */
+	  bitmap_set_bit (vars_to_rename, t_ann->uid);
+
 	  /* Associate the tag with pointer VAR.  */
 	  v_ann->type_mem_tag = tag;
 
@@ -1548,7 +1638,32 @@ merge_pointed_to_info (struct alias_info
   if (orig_pi)
     {
       dest_pi->pt_anything |= orig_pi->pt_anything;
-      dest_pi->pt_malloc |= orig_pi->pt_malloc;
+
+      /* 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:
+
+	 P_i = malloc ();
+	 ...
+	 P_j = P_i + X;
+
+	 P_j would be marked as PT_MALLOC, which is wrong because
+	 PT_MALLOC implies that the pointer may not point to another
+	 variable.
+
+	 FIXME 1: Subsequent analysis may determine that P_j
+	 cannot alias anything else, but we are being conservative
+	 here.
+
+	 FIXME 2: If the merging comes from a copy assignment, we
+	 ought to merge PT_MALLOC, but then both pointers would end up
+	 getting different name tags because 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.  */
+      dest_pi->pt_malloc = 0;
+      if (orig_pi->pt_malloc)
+	dest_pi->pt_anything = 1;
 
       if (orig_pi->pt_vars)
 	{
@@ -1559,9 +1674,9 @@ merge_pointed_to_info (struct alias_info
 	    }
 	  else
 	    bitmap_a_or_b (dest_pi->pt_vars,
-			   dest_pi->pt_vars,
-			   orig_pi->pt_vars);
-      }
+		           dest_pi->pt_vars,
+		           orig_pi->pt_vars);
+	}
     }
 }
 
@@ -1821,9 +1936,8 @@ create_memory_tag (tree type, bool is_ty
   ann->mem_tag_kind = (is_type_tag) ? TYPE_TAG : NAME_TAG;
   ann->type_mem_tag = NULL_TREE;
 
-  /* Add the tag to the symbol table and mark it for renaming.  */
+  /* Add the tag to the symbol table.  */
   add_referenced_tmp_var (tag);
-  bitmap_set_bit (vars_to_rename, ann->uid);
 
   return tag;
 }
@@ -2030,7 +2144,7 @@ get_ptr_info (tree t)
 
 /* Dump points-to information for SSA_NAME PTR into FILE.  */
 
-static void
+void
 dump_points_to_info_for (FILE *file, tree ptr)
 {
   struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
@@ -2038,41 +2152,53 @@ dump_points_to_info_for (FILE *file, tre
   fprintf (file, "Pointer ");
   print_generic_expr (file, ptr, dump_flags);
 
-  if (pi == NULL)
-    return;
-
-  if (pi->name_mem_tag)
+  if (pi)
     {
-      fprintf (file, ", name memory tag: ");
-      print_generic_expr (file, pi->name_mem_tag, dump_flags);
-    }
+      if (pi->name_mem_tag)
+	{
+	  fprintf (file, ", name memory tag: ");
+	  print_generic_expr (file, pi->name_mem_tag, dump_flags);
+	}
 
-  if (pi->value_escapes_p)
-    fprintf (file, ", its value escapes");
+      if (pi->is_dereferenced)
+	fprintf (file, ", is dereferenced");
 
-  if (pi->pt_anything)
-    fprintf (file, ", points-to anything");
+      if (pi->value_escapes_p)
+	fprintf (file, ", its value escapes");
 
-  if (pi->pt_malloc)
-    fprintf (file, ", points-to malloc");
+      if (pi->pt_anything)
+	fprintf (file, ", points-to anything");
 
-  if (pi->pt_vars)
-    {
-      unsigned ix;
+      if (pi->pt_malloc)
+	fprintf (file, ", points-to malloc");
 
-      fprintf (file, ", points-to vars: { ");
-      EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix,
-	  {
-	    print_generic_expr (file, referenced_var (ix), dump_flags);
-	    fprintf (file, " ");
-	  });
-      fprintf (file, "}");
+      if (pi->pt_vars)
+	{
+	  unsigned ix;
+
+	  fprintf (file, ", points-to vars: { ");
+	  EXECUTE_IF_SET_IN_BITMAP (pi->pt_vars, 0, ix,
+	      {
+		print_generic_expr (file, referenced_var (ix), dump_flags);
+		fprintf (file, " ");
+	      });
+	  fprintf (file, "}");
+	}
     }
 
   fprintf (file, "\n");
 }
 
 
+/* Dump points-to information for VAR into stderr.  */
+
+void
+debug_points_to_info_for (tree var)
+{
+  dump_points_to_info_for (stderr, var);
+}
+
+
 /* Dump points-to information into FILE.  NOTE: This function is slow, as
    it needs to traverse the whole CFG looking for pointer SSA_NAMEs.  */