This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH]: Rewrite sharing of finished solutions in PTA


While changing the partitioning strategy, Diego noticed some bootstrap
failures that are attributable to the fact that we share *final* (IE
after merging smt aliases in) points-to sets in some cases where we
can't.

In particular, the safety of what is there now relies on being able to
identify and collapse all equivalent variables.  There are some corner
cases where we miss pointer equivalences, and when that happens, they
do not always properly end up with intersecting points-to sets if they
are shared. It also caused us to miss setting pt_global_mem on some
variables that should have had it.

Along the way, it was discovered what appears to be a necessary check
in tree-ssa-operands.c was also deleted.  This is restored.

The attached patch fixes this by doing the sharing in a different way.
Rather than automatically sharing final points-to sets between
variables determined to be pointer-equivalent, we now do the work of
creating the points-to set, and then see if we've already created this
one.

This is technically more work than we previously did, so this patch
may have a small compile time hit.
This is easy to fix by changing merge_smts_into to only compute the
bitmap to merge in once per SMT, rather than every time we see an SMT.
I will do this in a followup patch.

The attach was bootstrapped with param max-vops set to the default,
and also set to 400, in order to disable partitioning which was hiding
this bug.

Bootstrapped and regtested with all languages on x86-64-linux-gnu, and
C only on i386-darwin (C++ is currently untestable in the current 10.5
seed I have)

Committed to mainline.

2007-03-09 Daniel Berlin <dberlin@dberlin.org>

	* tree-ssa-structalias.c (variable_info): Remove
	finished_solution.
	(new_var_info): Ditto.
	(shared_bitmap_info_t): New structure.
	(shared_bitmap_table): New variable.
	(shared_bitmap_hash): New function.
	(shared_bitmap_eq): Ditto
	(shared_bitmap_lookup): Ditto.
	(shared_bitmap_add): Ditto.
	(merge_smts_into): Change to take bitmap directly.
	(find_what_p_points_to): Rewrite to use shared bitmap hashtable.
	(init_alias_vars): Init shared bitmap hashtable.
	(delete_points_to_sets): Delete shared bitmap hashtable.
	* tree-ssa-operands.c (add_virtual_operand): Partially revert the
	is_aliased removal as a change that was still necessary was
	deleted.
Index: tree-ssa-structalias.c
===================================================================
--- tree-ssa-structalias.c	(revision 122688)
+++ tree-ssa-structalias.c	(working copy)
@@ -256,10 +256,6 @@ struct variable_info
   /* Old points-to set for this variable.  */
   bitmap oldsolution;
 
-  /* Finished points-to set for this variable (IE what is returned
-     from find_what_p_points_to.  */
-  bitmap finished_solution;
-
   /* Variable ids represented by this node.  */
   bitmap variables;
 
@@ -374,7 +370,6 @@ new_var_info (tree t, unsigned int id, c
   ret->has_union = false;
   ret->solution = BITMAP_ALLOC (&pta_obstack);
   ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
-  ret->finished_solution = NULL;
   ret->next = NULL;
   ret->collapsed_to = NULL;
   return ret;
@@ -4159,6 +4154,75 @@ intra_create_variable_infos (void)
     }
 }
 
+/* Structure used to put solution bitmaps in a hashtable so they can
+   be shared among variables with the same points-to set.  */
+
+typedef struct shared_bitmap_info
+{
+  bitmap pt_vars;
+  hashval_t hashcode;
+} *shared_bitmap_info_t;
+
+static htab_t shared_bitmap_table;
+
+/* Hash function for a shared_bitmap_info_t */
+
+static hashval_t
+shared_bitmap_hash (const void *p)
+{
+  const shared_bitmap_info_t bi = (shared_bitmap_info_t) p;
+  return bi->hashcode;
+}
+
+/* Equality function for two shared_bitmap_info_t's. */
+
+static int
+shared_bitmap_eq (const void *p1, const void *p2)
+{
+  const shared_bitmap_info_t sbi1 = (shared_bitmap_info_t) p1;
+  const shared_bitmap_info_t sbi2 = (shared_bitmap_info_t) p2;
+  return bitmap_equal_p (sbi1->pt_vars, sbi2->pt_vars);
+}
+
+/* Lookup a bitmap in the shared bitmap hashtable, and return an already
+   existing instance if there is one, NULL otherwise.  */
+
+static bitmap
+shared_bitmap_lookup (bitmap pt_vars)
+{
+  void **slot;
+  struct shared_bitmap_info sbi;
+
+  sbi.pt_vars = pt_vars;
+  sbi.hashcode = bitmap_hash (pt_vars);
+  
+  slot = htab_find_slot_with_hash (shared_bitmap_table, &sbi,
+				   sbi.hashcode, NO_INSERT);
+  if (!slot)
+    return NULL;
+  else
+    return ((shared_bitmap_info_t) *slot)->pt_vars;
+}
+
+
+/* Add a bitmap to the shared bitmap hashtable.  */
+
+static void
+shared_bitmap_add (bitmap pt_vars)
+{
+  void **slot;
+  shared_bitmap_info_t sbi = XNEW (struct shared_bitmap_info);
+  
+  sbi->pt_vars = pt_vars;
+  sbi->hashcode = bitmap_hash (pt_vars);
+  
+  slot = htab_find_slot_with_hash (shared_bitmap_table, sbi,
+				   sbi->hashcode, INSERT);
+  gcc_assert (!*slot);
+  *slot = (void *) sbi;
+}
+
+
 /* Set bits in INTO corresponding to the variable uids in solution set
    FROM, which came from variable PTR.
    For variables that are actually dereferenced, we also use type
@@ -4282,12 +4346,12 @@ set_used_smts (void)
     }
 }
 
-/* Merge the necessary SMT's into the solution set for VI, which is
+/* Merge the necessary SMT's into the bitmap INTO, which is
    P's varinfo.  This involves merging all SMT's that are a subset of
    the SMT necessary for P. */
 
 static void
-merge_smts_into (tree p, varinfo_t vi)
+merge_smts_into (tree p, bitmap solution)
 {
   unsigned int i;
   bitmap_iterator bi;
@@ -4305,7 +4369,7 @@ merge_smts_into (tree p, varinfo_t vi)
 
       /* Need to set the SMT subsets first before this
 	 will work properly.  */
-      bitmap_set_bit (vi->finished_solution, DECL_UID (smt));
+      bitmap_set_bit (solution, DECL_UID (smt));
       EXECUTE_IF_SET_IN_BITMAP (used_smts, 0, i, bi)
 	{
 	  tree newsmt = referenced_var (i);
@@ -4313,12 +4377,12 @@ merge_smts_into (tree p, varinfo_t vi)
 
 	  if (alias_set_subset_of (get_alias_set (newsmttype),
 				   smtset))
-	    bitmap_set_bit (vi->finished_solution, i);
+	    bitmap_set_bit (solution, i);
 	}
 
       aliases = MTAG_ALIASES (smt);
       if (aliases)
-        bitmap_ior_into (vi->finished_solution, aliases);
+        bitmap_ior_into (solution, aliases);
     }
 }
 
@@ -4371,7 +4435,9 @@ find_what_p_points_to (tree p)
 	  unsigned int i;
 	  bitmap_iterator bi;
 	  bool was_pt_anything = false;
-
+	  bitmap finished_solution;
+	  bitmap result;
+	  
 	  if (!pi->is_dereferenced)
 	    return false;
 
@@ -4403,32 +4469,31 @@ find_what_p_points_to (tree p)
 		}
 	    }
 
-	  /* Share the final set of variables between the SSA_NAME
-	     pointer infos for collapsed nodes that are collapsed to
-	     non-special variables.  This is because special vars have
-	     no real types associated with them, so while we know the
-	     pointers are equivalent to them, we need to generate the
-	     solution separately since it will include SMT's from the
-	     original non-collapsed variable.  */
-	  if (!vi->is_special_var && vi->finished_solution)
+	  /* Share the final set of variables when possible.  */
+	  
+	  finished_solution = BITMAP_GGC_ALLOC ();
+	  stats.points_to_sets_created++;
+	  
+	  /* Instead of using pt_anything, we instead merge in the SMT
+	     aliases for the underlying SMT.  */
+	  if (was_pt_anything)
+	    {
+	      merge_smts_into (p, finished_solution);
+	      pi->pt_global_mem = 1;
+	    }
+	  
+	  set_uids_in_ptset (vi->decl, finished_solution, vi->solution);
+	  result = shared_bitmap_lookup (finished_solution);
+
+	  if (!result)
 	    {
-	      pi->pt_vars = vi->finished_solution;
+	      shared_bitmap_add (finished_solution);
+	      pi->pt_vars = finished_solution;
 	    }
 	  else
 	    {
-	      vi->finished_solution = BITMAP_GGC_ALLOC ();
-	      stats.points_to_sets_created++;
-
-	      /* Instead of using pt_anything, we instead merge in the SMT
-		 aliases for the underlying SMT.  */
-	      if (was_pt_anything)
-		{
-		  merge_smts_into (p, vi);
-		  pi->pt_global_mem = 1;
-		}
-
-	      set_uids_in_ptset (vi->decl, vi->finished_solution, vi->solution);
-	      pi->pt_vars = vi->finished_solution;
+	      pi->pt_vars = result;
+	      bitmap_clear (finished_solution);
 	    }
 
 	  if (bitmap_empty_p (pi->pt_vars))
@@ -4602,7 +4667,8 @@ init_alias_vars (void)
   vi_for_tree = pointer_map_create ();
 
   memset (&stats, 0, sizeof (stats));
-
+  shared_bitmap_table = htab_create (511, shared_bitmap_hash,
+				     shared_bitmap_eq, free);
   init_base_vars ();
 }
 
@@ -4737,6 +4803,7 @@ delete_points_to_sets (void)
   varinfo_t v;
   int i;
 
+  htab_delete (shared_bitmap_table);
   if (dump_file && (dump_flags & TDF_STATS))
     fprintf (dump_file, "Points to sets created:%d\n",
 	     stats.points_to_sets_created);
Index: tree-ssa-operands.c
===================================================================
--- tree-ssa-operands.c	(revision 122688)
+++ tree-ssa-operands.c	(working copy)
@@ -1523,13 +1523,23 @@ add_virtual_operand (tree var, stmt_ann_
 	      append_vdef (al);
 	    }
 
-	  /* Even if no aliases have been added, we still need to
-	     establish def-use and use-def chains, lest
-	     transformations think that this is not a memory
-	     reference.  For an example of this scenario, see
-	     testsuite/g++.dg/opt/cleanup1.C.  */
-	  if (none_added)
-	    append_vdef (var);
+	  /* If the variable is also an alias tag, add a virtual
+	     operand for it, otherwise we will miss representing
+	     references to the members of the variable's alias set.	     
+	     This fixes the bug in gcc.c-torture/execute/20020503-1.c.
+	     
+	     It is also necessary to add bare defs on clobbers for
+	     SMT's, so that bare SMT uses caused by pruning all the
+	     aliases will link up properly with calls.   In order to
+	     keep the number of these bare defs we add down to the
+	     minimum necessary, we keep track of which SMT's were used
+	     alone in statement vdefs or VUSEs.  */
+	  if (none_added
+	      || (TREE_CODE (var) == SYMBOL_MEMORY_TAG
+		  && is_call_site))
+	    {
+	      append_vdef (var);
+	    }
 	}
       else
 	{

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]