[PATCH] Compare recursively rtxs with embedded VALUEs during location chain intersection (PR debug/43051)

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

This patch fixes a regression from pre-VTA, where e.g. on i?86 we often
pretend we don't know where e.g. parameters live inside loops, eventhough
they are always there in their incoming stack slot.

The problem is that with -fvar-tracking-assignments, MEMs addresses are
replaced with VALUEs, and upon merging two bb's out sets those VALUEs can be
different, eventhough they really contain the same thing.
This patch fixes it by recursively comparing the embedded VALUEs.  In order
to avoid too much processing, it limits it to one differing VALUE pair per
comparison.  So for say (mem (value:6)) and (mem (value:11)) it will
consider the two MEMs might be equal, looks up locations for value:6
in the first vars table and recurses to compare those to all locations of
value:11.  This then can lead to comparison of say (plus (value:5) (const_int 16))
(plus (value:10) (const_int 16)), which again matches except for the first
value pair and recurses again, to find say that both value:5 and value:10
include %ebp location and thus says the two MEMs are the same.

Bootstrapped/regtested on x86_64-linux and i686-linux, on the few larger
testcases I've tried it didn't measurably affect compile time.
On x86_64-linux code it doesn't seem to have very big visible effect,
but on i686-linux it does:
 number of dies with DW_AT_location attribute before/after:
 readelf -wi obj598/gcc/cc1 | grep DW_AT_location | wc -l; readelf -wi obj600/gcc/cc1 | grep DW_AT_location | wc -l
 158673
 226078
 number of location lists in .debug_loc before/after:
 readelf -wo obj598/gcc/cc1 | grep '<End of' | wc -l; readelf -wo obj600/gcc/cc1
 | grep '<End of' | wc -l
 116508
 182037
 and number of ranges with a valid location before/after:
 readelf -wo obj598/gcc/cc1 | grep DW_OP_ | wc -l; readelf -wo obj600/gcc/cc1 |
 grep DW_OP_ | wc -l
 495513
 980535
Ok for trunk?

2010-02-17  Alexandre Oliva  <aoliva@redhat.com>

	PR debug/43051
	* var-tracking.c (dataflow_set_preserve_mem_locs): Update cur_loc.

2010-02-17  Jakub Jelinek  <jakub@redhat.com>

	PR debug/43051
	* var-tracking.c (struct dfset_merge): Move definition earlier.
	(value_pair): New variable.
	(ignore_first_value_pair): New function.
	(find_loc_in_1pdv_1): Change last argument to struct dfset_merge *.
	If node->loc is VALUE, don't call rtx_equal_p at all, instead just
	compare pointers and then recurse.  For other rtxes, call
	rtx_equal_p_cb instead of rtx_equal_p and ignore first VALUE pair
	during comparison, if some has been found, compare those VALUEs
	recursively.
	(find_loc_in_1pdv): Change last argument to struct dfset_merge *.
	(intersect_loc_chains, variable_post_merge_perm_vals): Adjust callers.

--- gcc/var-tracking.c.jj	2010-02-07 11:53:22.000000000 +0100
+++ gcc/var-tracking.c	2010-02-15 12:37:00.000000000 +0100
@@ -428,7 +428,8 @@ static int variable_union_info_cmp_pos (
 static int variable_union (void **, void *);
 static int variable_canonicalize (void **, void *);
 static void dataflow_set_union (dataflow_set *, dataflow_set *);
-static location_chain find_loc_in_1pdv (rtx, variable, htab_t);
+struct dfset_merge;
+static location_chain find_loc_in_1pdv (rtx, variable, struct dfset_merge *);
 static bool canon_value_cmp (rtx, rtx);
 static int loc_cmp (rtx, rtx);
 static bool variable_part_different_p (variable_part *, variable_part *);
@@ -2234,6 +2235,53 @@ dv_changed_p (decl_or_value dv)
 	  : DECL_CHANGED (dv_as_decl (dv)));
 }
 
+/* Hash table iteration argument passed to variable_merge.  */
+struct dfset_merge
+{
+  /* The set in which the merge is to be inserted.  */
+  dataflow_set *dst;
+  /* The set that we're iterating in.  */
+  dataflow_set *cur;
+  /* The set that may contain the other dv we are to merge with.  */
+  dataflow_set *src;
+  /* Number of onepart dvs in src.  */
+  int src_onepart_cnt;
+};
+
+/* First encountered differing VALUE pair remembered by
+   ignore_first_value_pair hook.  */
+
+static rtx value_pair[2];
+
+/* Helper for rtx_equal_p_cb.  Pretend the first encountered VALUE pair
+   is the same and remember it.  */
+
+static int
+ignore_first_value_pair (const_rtx *px, const_rtx *py, rtx *nx, rtx *ny)
+{
+  const_rtx x = *px, y;
+
+  if (GET_CODE (x) != VALUE)
+    return 0;
+  y = *py;
+  if (GET_CODE (y) != VALUE)
+    return 0;
+  if (x == y)
+    return 0;
+  if (GET_MODE (x) != GET_MODE (y))
+    return 0;
+  /* If this isn't the first encountered VALUE pair, fail.  */
+  if (value_pair[0])
+    return 0;
+  /* Remember the first encountered VALUE pair and pretend the VALUEs are the
+     same.  */
+  value_pair[0] = CONST_CAST_RTX (x);
+  value_pair[1] = CONST_CAST_RTX (y);
+  *nx = CONST_CAST_RTX (x);
+  *ny = CONST_CAST_RTX (x);
+  return 1;
+}
+
 /* 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.  */
@@ -2245,7 +2293,7 @@ static VEC(rtx, heap) *values_to_unmark;
    any values recursively mentioned in the location lists.  */
 
 static location_chain
-find_loc_in_1pdv_1 (rtx loc, variable var, htab_t vars)
+find_loc_in_1pdv_1 (rtx loc, variable var, struct dfset_merge *dsm)
 {
   location_chain node;
 
@@ -2260,22 +2308,65 @@ find_loc_in_1pdv_1 (rtx loc, variable va
   gcc_assert (var->var_part[0].offset == 0);
 
   for (node = var->var_part[0].loc_chain; node; node = node->next)
-    if (rtx_equal_p (loc, node->loc))
-      return node;
-    else if (GET_CODE (node->loc) == VALUE
-	     && !VALUE_RECURSED_INTO (node->loc))
+    if (GET_CODE (node->loc) == VALUE)
       {
-	decl_or_value dv = dv_from_value (node->loc);
-	variable var = (variable)
-		       htab_find_with_hash (vars, dv, dv_htab_hash (dv));
+	if (loc == node->loc)
+	  return node;
+	if (!VALUE_RECURSED_INTO (node->loc))
+	  {
+	    decl_or_value dv = dv_from_value (node->loc);
+	    htab_t vars = shared_hash_htab (dsm->src->vars);
+	    variable var
+	      = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
 
-	if (var)
+	    if (var)
+	      {
+		location_chain where;
+		VALUE_RECURSED_INTO (node->loc) = true;
+		VEC_safe_push (rtx, heap, values_to_unmark, node->loc);
+		if ((where = find_loc_in_1pdv_1 (loc, var, dsm)))
+		  return where;
+	      }
+	  }
+      }
+    else if (GET_CODE (node->loc) == GET_CODE (loc))
+      {
+	rtx val1, val2;
+	if (!rtx_equal_p_cb (loc, node->loc, ignore_first_value_pair))
 	  {
-	    location_chain where;
-	    VALUE_RECURSED_INTO (node->loc) = true;
-	    VEC_safe_push (rtx, heap, values_to_unmark, node->loc);
-	    if ((where = find_loc_in_1pdv_1 (loc, var, vars)))
-	      return where;
+	    value_pair[0] = NULL;
+	    value_pair[1] = NULL;
+	    continue;
+	  }
+	if (!value_pair[0])
+	  return node;
+	val1 = value_pair[0];
+	val2 = value_pair[1];
+	value_pair[0] = NULL;
+	value_pair[1] = NULL;
+        if (dsm->cur)
+	  {
+	    decl_or_value dv;
+	    htab_t vars;
+	    variable var1, var2;
+	    dv = dv_from_value (val1);
+	    vars = shared_hash_htab (dsm->cur->vars);
+	    var1 = (variable) htab_find_with_hash (vars, dv,
+						   dv_htab_hash (dv));
+	    if (var1)
+	      {
+		dv = dv_from_value (val2);
+		vars = shared_hash_htab (dsm->src->vars);
+		var2 = (variable) htab_find_with_hash (vars, dv,
+						       dv_htab_hash (dv));
+		if (var2)
+		  {
+		    location_chain s1node = var1->var_part[0].loc_chain;
+		    for (; s1node; s1node = s1node->next)
+		      if (find_loc_in_1pdv_1 (s1node->loc, var2, dsm))
+			return node;
+		  }
+	      }
 	  }
       }
 
@@ -2287,32 +2378,19 @@ find_loc_in_1pdv_1 (rtx loc, variable va
    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 (rtx loc, variable var, struct dfset_merge *dsm)
 {
   location_chain ret;
   unsigned int i;
   rtx value;
 
-  ret = find_loc_in_1pdv_1 (loc, var, vars);
+  ret = find_loc_in_1pdv_1 (loc, var, dsm);
   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
-{
-  /* The set in which the merge is to be inserted.  */
-  dataflow_set *dst;
-  /* The set that we're iterating in.  */
-  dataflow_set *cur;
-  /* The set that may contain the other dv we are to merge with.  */
-  dataflow_set *src;
-  /* Number of onepart dvs in src.  */
-  int src_onepart_cnt;
-};
-
 /* Insert LOC in *DNODE, if it's not there yet.  The list must be in
    loc_cmp order, and it is maintained as such.  */
 
@@ -2351,7 +2429,6 @@ intersect_loc_chains (rtx val, location_
 		      location_chain s1node, variable s2var)
 {
   dataflow_set *s1set = dsm->cur;
-  dataflow_set *s2set = dsm->src;
   location_chain found;
 
   for (; s1node; s1node = s1node->next)
@@ -2359,8 +2436,7 @@ intersect_loc_chains (rtx val, location_
       if (s1node->loc == val)
 	continue;
 
-      if ((found = find_loc_in_1pdv (s1node->loc, s2var,
-				     shared_hash_htab (s2set->vars))))
+      if ((found = find_loc_in_1pdv (s1node->loc, s2var, dsm)))
 	{
 	  insert_into_intersection (dest, s1node->loc,
 				    MIN (s1node->init, found->init));
@@ -3592,7 +3668,10 @@ variable_post_merge_perm_vals (void **ps
   var = shared_hash_find (set->vars, dv);
   if (var)
     {
-      if (find_loc_in_1pdv (pnode->loc, var, shared_hash_htab (set->vars)))
+      struct dfset_merge dsm;
+      memset (&dsm, '\0', sizeof (dsm));
+      dsm.src = set;
+      if (find_loc_in_1pdv (pnode->loc, var, &dsm))
 	return 1;
       val_reset (set, dv);
     }
@@ -3808,6 +3808,7 @@ dataflow_set_preserve_mem_locs (void **s
     {
       tree decl = dv_as_decl (var->dv);
       location_chain loc, *locp;
+      bool changed = false;
 
       if (!var->n_var_parts)
 	return 1;
@@ -3881,6 +3882,9 @@ dataflow_set_preserve_mem_locs (void **s
 	  if (emit_notes)
 	    remove_value_chains (var->dv, old_loc);
 	  *locp = loc->next;
+	  if (var->var_part[0].cur_loc
+	      && rtx_equal_p (loc->loc, var->var_part[0].cur_loc))
+	    changed = true;
 	  pool_free (loc_chain_pool, loc);
 	}
 
@@ -3889,6 +3893,12 @@ dataflow_set_preserve_mem_locs (void **s
 	  var->n_var_parts--;
 	  if (emit_notes && dv_is_value_p (var->dv))
 	    remove_cselib_value_chains (var->dv);
+	  gcc_assert (changed);
+	}
+      if (changed)
+	{
+	  if (var->n_var_parts && var->var_part[0].loc_chain)
+	    var->var_part[0].cur_loc = var->var_part[0].loc_chain->loc;
 	  variable_was_changed (var, set);
 	}
     }

	Jakub