[PATCH] Speed up var-tracking on various KDE sources (PR debug/41371)

[Jakub Jelinek]

Hi!

On PR41371 (but it seems to be a common problem in many KDE sources)
we spend minutes to hours/days in intersect_loc_chains/find_loc_in_1pdv.
The problem seems to be that as we recurse through VALUEs, we only set
VALUE_RECURSED_INTO for VALUEs that are currently being searched, which
means we can search the same VALUEs many times.  On the qmc2main.ii testcase
this leads to one find_loc_in_1pdv outermost call doing up to almost 1000000
rtx_equal_p comparisons, even when only a few hundreds are needed.

Fixed by not clearing VALUE_RECURSED_INTO immediately after we return from
recursion, but queueing the VALUE in a vector and let just the outermost
find_loc_in_1pdv call clear VALUE_RECURSED_INTO for all the VALUEs it has
recursed into.

Bootstrapped/regtested on powerpc64-linux (-m32/-m64 testing) on the trunk
and on {i686,x86_64,powerpc,powerpc64}-linux in 4.4.2-RH backport.

Ok for trunk?

2010-01-13  Jakub Jelinek  <jakub@redhat.com>

	PR debug/41371
	* var-tracking.c (values_to_unmark): New variable.
	(find_loc_in_1pdv): Clear VALUE_RECURSED_INTO of values in
	values_to_unmark vector.  Moved body to...
	(find_loc_in_1pdv_1): ... this.  Don't clear VALUE_RECURSED_INTO,
	instead queue it into values_to_unmark vector.
	(vt_find_locations): Free values_to_unmark vector.

--- gcc/var-tracking.c.jj	2010-01-12 10:37:30.000000000 +0100
+++ gcc/var-tracking.c	2010-01-12 17:41:39.000000000 +0100
@@ -2252,12 +2252,18 @@ dv_changed_p (decl_or_value dv)
 	  : DECL_CHANGED (dv_as_decl (dv)));
 }
 
-/* Return a location list node whose loc is rtx_equal to LOC, in the
+/* Vector of VALUEs that should have VALUE_RECURSED_INTO bit cleared
+   at the end of find_loc_in_1pdv.  Not a static variable in find_loc_in_1pdv
+   to avoid constant allocation/freeing of it.  */
+static VEC(rtx, heap) *values_to_unmark;
+
+/* Helper function for find_loc_in_1pdv.
+   Return a location list node whose loc is rtx_equal to LOC, in the
    location list of a one-part variable or value VAR, or in that of
    any values recursively mentioned in the location lists.  */
 
 static location_chain
-find_loc_in_1pdv (rtx loc, variable var, htab_t vars)
+find_loc_in_1pdv_1 (rtx loc, variable var, htab_t vars)
 {
   location_chain node;
 
@@ -2285,18 +2291,33 @@ find_loc_in_1pdv (rtx loc, variable var,
 	  {
 	    location_chain where;
 	    VALUE_RECURSED_INTO (node->loc) = true;
-	    if ((where = find_loc_in_1pdv (loc, var, vars)))
-	      {
-		VALUE_RECURSED_INTO (node->loc) = false;
-		return where;
-	      }
-	    VALUE_RECURSED_INTO (node->loc) = false;
+	    VEC_safe_push (rtx, heap, values_to_unmark, node->loc);
+	    if ((where = find_loc_in_1pdv_1 (loc, var, vars)))
+	      return where;
 	  }
       }
 
   return NULL;
 }
 
+/* Return a location list node whose loc is rtx_equal to LOC, in the
+   location list of a one-part variable or value VAR, or in that of
+   any values recursively mentioned in the location lists.  */
+
+static location_chain
+find_loc_in_1pdv (rtx loc, variable var, htab_t vars)
+{
+  location_chain ret;
+  unsigned int i;
+  rtx value;
+
+  ret = find_loc_in_1pdv_1 (loc, var, vars);
+  for (i = 0; VEC_iterate (rtx, values_to_unmark, i, value); i++)
+    VALUE_RECURSED_INTO (value) = false;
+  VEC_truncate (rtx, values_to_unmark, 0);
+  return ret;
+}
+
 /* Hash table iteration argument passed to variable_merge.  */
 struct dfset_merge
 {
@@ -5648,6 +5669,7 @@ vt_find_locations (void)
     FOR_EACH_BB (bb)
       gcc_assert (VTI (bb)->flooded);
 
+  VEC_free (rtx, heap, values_to_unmark);
   free (bb_order);
   fibheap_delete (worklist);
   fibheap_delete (pending);

	Jakub