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]: Fix may_alias slowdown in 23835


This fixes the slowdown in 23835 due to create_name_tags being
NUM_SSA_NAMES^2.

It does so by making it not NUM_SSA_NAMES^2.  On 23835, it's 3x faster
(9 seconds -> 2.85 seconds), and should take create_name_tags off the
profile entirely.

The routine doesn't actualy do anything different than it used to, it
just doesn't waste it's time walking ssa_names that don't affect it's
outcome.

We used to simply walk all the ssa_names, see if any were pointers with
ptr info set, whether they had pt_vars in that pointer info, etc, and if
so, then walk all the ssa_names in the inner loop to see if *they* had
the same qualities.  This makes a heck of a lot of useless memory
accesses to check these properties.

The common case is actually one of
1. All of the pointers have pt_vars set to something
2. None of the pointers have pt_vars set to something.
3. All of the pointers point to anything or are not dereferenced

In the second case, the entire nested loop is only going to set
pt_anything on the vars and go away.  

In the third case, the loop does nothing but set the name tags to null,
very slowly.  :)

Instead, we start by collecting only the pointers that we actually want
to walk in the original nested loops (instead of touching all the ssa
names twice), into a list,  setting the name tag to null and skipping
the pointer if it was going to be skipped before the rewrite.

If we end up with no pointers that still want name tags, we end the
function there, since there is nothing left to do.

We then sort the list into two pieces, so that those that have pt_vars
bitmaps with bits in them, come last, since those are the only things
the actual nested loop needs to look at.

Those without pt_vars bitmaps with bits in them just get set to
pt_anything.  As a side-effect, we find the first place in the array
that has a variable with pt_vars set.

We then walk those with pt_vars set in the nested loop, as we did before
the rewrite.

Thus, the expensive loop is now only O(number of variables with pt_vars
set^2) instead of O(num_ssa_names^2).

There is no actual change in semantics or what this function marks.
If one stares at the two copies long enough, you can convince yourself
of this, or at least have nice hallucinations.

If we'd rather split the lists into two, instead of sorting it so there
is a split, i'm happy to make that change. :)

Bootstrapped and regtested on i686-pc-linux-gnu.  No regressions.

Okay for mainline?


2005-09-14  Daniel Berlin  <dberlin@dberlin.org>

	PR tree-optimization/23835
	* tree-ssa-alias.c (sort_pointers_by_pt_vars): New function.
	(create_name_tags): Rewrite to be not O(num_ssa_names^2).

Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.109
diff -u -p -r2.109 tree-ssa-alias.c
--- tree-ssa-alias.c	28 Jul 2005 16:29:53 -0000	2.109
+++ tree-ssa-alias.c	14 Sep 2005 14:29:21 -0000
@@ -568,6 +568,27 @@ delete_alias_info (struct alias_info *ai
   delete_points_to_sets ();
 }
 
+/* qsort comparison function to sort pointers by whether they
+   have pt_vars or not.  */
+
+static int
+sort_pointers_by_pt_vars (const void *pa, const void *pb)
+{
+  tree a = *(tree *)pa;
+  tree b = *(tree *)pb;
+  struct ptr_info_def *pia;
+  struct ptr_info_def *pib;
+  int first_has_ptvars = 0;
+  int second_has_ptvars = 0;
+  
+  pia = SSA_NAME_PTR_INFO (a);
+  pib = SSA_NAME_PTR_INFO (b);
+
+  first_has_ptvars = pia->pt_vars && !bitmap_empty_p (pia->pt_vars);
+  second_has_ptvars = pib->pt_vars && !bitmap_empty_p (pib->pt_vars);
+
+  return first_has_ptvars - second_has_ptvars;
+}
 
 /* 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
@@ -582,7 +603,15 @@ static void
 create_name_tags (void)
 {
   size_t i;
-
+  VEC (tree, heap) *pointers = NULL;
+  tree ptr;
+  /* This number should be bigger than the length of the pointers
+     vector.  */
+  unsigned int first_with_ptvars = ~0;
+
+  /* Collect the list of pointers the loops below are going to want to
+     look at.  These are those pointers with SSA_NAME_POINTER_INFO set
+     and don't point to anything.  */
   for (i = 1; i < num_ssa_names; i++)
     {
       tree ptr = ssa_name (i);
@@ -603,68 +632,89 @@ create_name_tags (void)
 	  continue;
 	}
 
+      VEC_safe_push (tree, heap, pointers, ptr);
+    }
+  
+  /* If we didn't find any pointers with pt_vars set, we're done.  */
+  if (!pointers)
+    return;
+  
+  /* Sort the array so that things with pt_vars come *last* */
+  qsort (VEC_address (tree, pointers),
+	 VEC_length (tree, pointers),
+	 sizeof (tree),
+	 sort_pointers_by_pt_vars);
+  
+  /* Set pt_anything on the pointers without pt_vars filled in, and as
+     a consequence find the first pointer with pt_vars set in the
+     array.  */
+  for (i = 0; VEC_iterate (tree, pointers, i, ptr); i++)
+    {
+      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
+      
       if (pi->pt_vars && !bitmap_empty_p (pi->pt_vars))
 	{
-	  size_t j;
-	  tree old_name_tag = pi->name_mem_tag;
-
-	  /* 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).  */
-	  for (j = 1; j < i; j++)
-	    {
-	      tree q = ssa_name (j);
-	      struct ptr_info_def *qi;
-
-	      if (!q || !POINTER_TYPE_P (TREE_TYPE (q)))
-		continue;
-
-	      qi = SSA_NAME_PTR_INFO (q);
+	  first_with_ptvars = i;
+	  break;
+	}
 
-	      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 the pointer does not point to a known spot, we should
+	 use type tags.  */
+      set_pt_anything (ptr);
+    }
 
-	  /* If we didn't find a pointer with the same points-to set
-	     as PTR, create a new name tag if needed.  */
-	  if (pi->name_mem_tag == NULL_TREE)
-	    pi->name_mem_tag = get_nmt_for (ptr);
-
-	  /* If the new name tag computed for PTR is different than
-	     the old name tag that it used to have, then the old tag
-	     needs to be removed from the IL, so we mark it for
-	     renaming.  */
-	  if (old_name_tag && old_name_tag != pi->name_mem_tag)
-	    mark_sym_for_renaming (old_name_tag);
-	}
-      else
+  /* Now go through the pointers with pt_vars, and find a name tag
+     with the same pt_vars as this pointer, or create one if one
+     doesn't exist.  */
+  for (i = first_with_ptvars; VEC_iterate (tree, pointers, i, ptr); i++)
+    {
+      struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
+      size_t j;
+      tree ptr2;
+      tree old_name_tag = pi->name_mem_tag;
+      
+      /* 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).  */
+      for (j = first_with_ptvars; VEC_iterate (tree, pointers, j, ptr2); j++)
 	{
-	  /* If the pointer does not point to a known spot, we should
-	     use type tags.  */
-	  set_pt_anything (ptr);
-	  continue;
+	  struct ptr_info_def *qi = SSA_NAME_PTR_INFO (ptr2);
+	  
+	  if (bitmap_equal_p (pi->pt_vars, qi->pt_vars))
+	    {
+	      pi->name_mem_tag = qi->name_mem_tag;
+	      break;
+	    }
 	}
-
+      
+      /* If we didn't find a pointer with the same points-to set
+	 as PTR, create a new name tag if needed.  */
+      if (pi->name_mem_tag == NULL_TREE)
+	pi->name_mem_tag = get_nmt_for (ptr);
+      
+      /* If the new name tag computed for PTR is different than
+	 the old name tag that it used to have, then the old tag
+	 needs to be removed from the IL, so we mark it for
+	 renaming.  */
+      if (old_name_tag && old_name_tag != pi->name_mem_tag)
+	mark_sym_for_renaming (old_name_tag);
+      
       TREE_THIS_VOLATILE (pi->name_mem_tag)
-	  |= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
-
+	|= TREE_THIS_VOLATILE (TREE_TYPE (TREE_TYPE (ptr)));
+      
       /* Mark the new name tag for renaming.  */
       mark_sym_for_renaming (pi->name_mem_tag);
     }
+
+  VEC_free (tree, heap, pointers);
 }
 
 

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