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]

[VTA] optimize out redundant var-tracking notes


It's quite common that we emit the same notes over and over for the same
variable, just because the value became avaialble at some new location,
or because it ceased to be avaialble at some location, or because some
value equivalence was established or removed.

Ideally, we *would* emit such changes so that the locations in debug
info would reflect all locations in which a variable is held.  However,
that would require some major surgery in the back end of var-tracking,
and in dwarf2out, which I'm not quite ready to do yet.

However, I can speed up significantly the emission of notes in some
pathological cases https://bugzilla.redhat.com/show_bug.cgi?id=522316
taking advantage of the fact that we pick up only one location at a
time.  The strategy here is that, if the location doesn't change, leave
it alone, rather than emitting a new var_location note for all variables
bound to any of the values in an equivalence set, or expressions
involving them, whenever any change to this set occurs.  We remember the
expression we last used to expand a value, and stick to it if it still
works, avoiding gratuitous changes to any other value or variable that
depends on that value.

This required minor surgery in var-tracking: we now have to deal with
sets at points where htabs or shared_hashes would suffice.  This is
good: my next patch (that I should post in a few days) will introduce
partially-shared sets, and this would have been needed anyway.

I'm not entirely convinced we're back-propagating the changes to all
affected values, but this hasn't regressed any of the guality tests, and
it reduces the number of emitted notes for the testcase above by about
an order of magnitude, spending much less time in final, dwarf2out and
even in var-tracking itself.

Is this ok?  (IIRC this was bootstrapped on x86_64-linux-gnu before some
minor tweaks, like removing asserts that proved to be unnecessary)

for  gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	* var-tracking.c (struct emit_note_data_def): Move after
	dataflow_set_def.  Hold a set rather than a vars htab.
	(dv_changed_p): Declare earlier.
	(emit_notes_for_changes): Take a set rather than a shared_hash.
	(dv_is_decl_p): Complain on DEBUG_EXPR.
	(shared_var_p, same_regno_or_equal_p): New fns.
	(variable_union): Use them.
	(VALUE_RECOMPUTE_LOC): New.
	(dataflow_set_preserve_mem_locs): Use new fns.
	(variable_part_different_p): Likewise.
	(variable_different_p): Likewise.  Handle NULL cur_loc.
	(dump_variable_name): New, split out of...
	(dump_variable): ... this.
	(set_slot_part): Use new fns.  Retain cur_loc of values while
	emitting notes.
	(delete_slot_part): Likewise.
	(vt_expand_loc_callback): Turned into wrapper for...
	(vt_expand_loc_callback_both): ... this.  Keep track of internal
	depth and self recursion.  Resolve values's cur_loc, or use
	resolved location.
	(vt_expand_loc_callback_stable): New.
	(vt_expand_loc): Turned into wrapper for...
	(vt_expand_loc_cb): ... this.
	(vt_expand_loc_stable): New.
	(emit_note_resolve_value): New.
	(emit_note_insn_var_location): Adjust for set rather than htab.
	Reject values.
	(check_changed_vars_1): Turned into wrapper for...
	(check_changed_vars_0): ... this.  For values only, check whether
	cur_loc is still usable, and mark as changed only values whose
	cur_loc involves this one.
	(check_chanved_vars_2): Rewritten in terms of check_changed_vars_0.
	(emit_notes_for_changes): Take set rather than shared_hash.  Pass
	it on.
	(emit_notes_for_differences_1): Likewise.  Attempt to preserve
	cur_loc, but mark value as requiring recomputation if needed.
	(emit_notes_for_differences_2): Use set rather than htab.
	(emit_notes_in_bb, vt_emit_notes): Adjust.

Index: gcc/var-tracking.c
===================================================================
--- gcc/var-tracking.c.orig	2009-12-15 17:03:42.000000000 -0200
+++ gcc/var-tracking.c	2009-12-15 17:19:31.000000000 -0200
@@ -182,20 +182,6 @@ typedef struct micro_operation_def
    declaration.  */
 typedef void *decl_or_value;
 
-/* Structure for passing some other parameters to function
-   emit_note_insn_var_location.  */
-typedef struct emit_note_data_def
-{
-  /* The instruction which the note will be emitted before/after.  */
-  rtx insn;
-
-  /* Where the note will be emitted (before/after insn)?  */
-  enum emit_note_where where;
-
-  /* The variables and values active at this point.  */
-  htab_t vars;
-} emit_note_data;
-
 /* Description of location of a part of a variable.  The content of a physical
    register is described by a chain of these structures.
    The chains are pretty short (usually 1 or 2 elements) and thus
@@ -242,6 +228,20 @@ typedef struct dataflow_set_def
   shared_hash traversed_vars;
 } dataflow_set;
 
+/* Structure for passing some other parameters to function
+   emit_note_insn_var_location.  */
+typedef struct emit_note_data_def
+{
+  /* The instruction which the note will be emitted before/after.  */
+  rtx insn;
+
+  /* Where the note will be emitted (before/after insn)?  */
+  enum emit_note_where where;
+
+  /* The variables and values active at this point.  */
+  dataflow_set *varset;
+} emit_note_data;
+
 /* The structure (one for each basic block) containing the information
    needed for variable tracking.  */
 typedef struct variable_tracking_info_def
@@ -401,6 +401,7 @@ static void attrs_list_insert (attrs *, 
 static void attrs_list_copy (attrs *, attrs);
 static void attrs_list_union (attrs *, attrs);
 
+static inline bool dv_changed_p (decl_or_value dv);
 static void **unshare_variable (dataflow_set *set, void **slot, variable var,
 				enum var_init_status);
 static int vars_copy_1 (void **, void *);
@@ -467,7 +468,7 @@ static void **delete_slot_part (dataflow
 static void delete_variable_part (dataflow_set *, rtx,
 				  decl_or_value, HOST_WIDE_INT);
 static int emit_note_insn_var_location (void **, void *);
-static void emit_notes_for_changes (rtx, enum emit_note_where, shared_hash);
+static void emit_notes_for_changes (rtx, enum emit_note_where, dataflow_set *);
 static int emit_notes_for_differences_1 (void **, void *);
 static int emit_notes_for_differences_2 (void **, void *);
 static void emit_notes_for_differences (rtx, dataflow_set *, dataflow_set *);
@@ -739,6 +740,7 @@ dv_is_decl_p (decl_or_value dv)
     case (int)VALUE:
       return false;
 
+    case (int)DEBUG_EXPR:
     default:
       gcc_unreachable ();
     }
@@ -1039,6 +1041,21 @@ shared_hash_shared (shared_hash vars)
   return vars->refcount > 1;
 }
 
+/* Return true if VAR is shared, or maybe because VARS is shared.  */
+
+static inline bool
+shared_var_p (variable var, shared_hash vars)
+{
+  return ((var->refcount > 1
+	   /* Don't count an entry in the changed_variables table as a
+	      duplicate.  */
+	   && !(var->refcount == 2 && dv_changed_p (var->dv)
+		&& htab_find_slot_with_hash (changed_variables, var->dv,
+					     dv_htab_hash (var->dv),
+					     NO_INSERT)))
+	  || shared_hash_shared (vars));
+}
+
 /* Return the hash table for VARS.  */
 
 static inline htab_t
@@ -1728,6 +1745,19 @@ dataflow_set_copy (dataflow_set *dst, da
   dst->stack_adjust = src->stack_adjust;
 }
 
+/* Same as rtx_equal_p, but locally-optimized for registers.  */
+static inline bool
+same_regno_or_equal_p (rtx x1, rtx x2)
+{
+  if (x1 == x2)
+    return true;
+
+  if (REG_P (x1) && REG_P (x2))
+    return REGNO (x1) == REGNO (x2);
+
+  return rtx_equal_p (x1, x2);
+}
+
 /* Information for merging lists of locations for a given offset of variable.
  */
 struct variable_union_info
@@ -1898,8 +1928,7 @@ variable_union (void **slot, void *data)
      thus there are at most MAX_VAR_PARTS different offsets.  */
   gcc_assert (dv_onepart_p (dst->dv) ? k == 1 : k <= MAX_VAR_PARTS);
 
-  if ((dst->refcount > 1 || shared_hash_shared (set->vars))
-      && dst->n_var_parts != k)
+  if (shared_var_p (dst, set->vars) && dst->n_var_parts != k)
     {
       dstp = unshare_variable (set, dstp, dst, VAR_INIT_STATUS_UNKNOWN);
       dst = (variable)*dstp;
@@ -1926,16 +1955,13 @@ variable_union (void **slot, void *data)
 	  /* If DST is shared compare the location chains.
 	     If they are different we will modify the chain in DST with
 	     high probability so make a copy of DST.  */
-	  if (dst->refcount > 1 || shared_hash_shared (set->vars))
+	  if (shared_var_p (dst, set->vars))
 	    {
 	      for (node = src->var_part[i].loc_chain,
 		   node2 = dst->var_part[j].loc_chain; node && node2;
 		   node = node->next, node2 = node2->next)
 		{
-		  if (!((REG_P (node2->loc)
-			 && REG_P (node->loc)
-			 && REGNO (node2->loc) == REGNO (node->loc))
-			|| rtx_equal_p (node2->loc, node->loc)))
+		  if (!same_regno_or_equal_p (node2->loc, node->loc))
 		    {
 		      if (node2->init < node->init)
 		        node2->init = node->init;
@@ -1965,10 +1991,7 @@ variable_union (void **slot, void *data)
 	      dst->var_part[k].offset = dst->var_part[j].offset;
 	      node2 = dstnode;
 	      for (node = src->var_part[i].loc_chain; node; node = node->next)
-		if (!((REG_P (dstnode->loc)
-		       && REG_P (node->loc)
-		       && REGNO (dstnode->loc) == REGNO (node->loc))
-		      || rtx_equal_p (dstnode->loc, node->loc)))
+		if (!same_regno_or_equal_p (dstnode->loc, node->loc))
 		  {
 		    location_chain new_node;
 
@@ -2014,10 +2037,7 @@ variable_union (void **slot, void *data)
 		  /* Find location from NODE.  */
 		  for (jj = 0; jj < dst_l; jj++)
 		    {
-		      if ((REG_P (vui[jj].lc->loc)
-			   && REG_P (node->loc)
-			   && REGNO (vui[jj].lc->loc) == REGNO (node->loc))
-			  || rtx_equal_p (vui[jj].lc->loc, node->loc))
+		      if (same_regno_or_equal_p (vui[jj].lc->loc, node->loc))
 			{
 			  vui[jj].pos = jj + ii;
 			  break;
@@ -2221,6 +2241,9 @@ dataflow_set_union (dataflow_set *dst, d
     htab_traverse (shared_hash_htab (src->vars), variable_union, dst);
 }
 
+/* Whether the cur_loc of the value must be disregarded.  */
+#define VALUE_RECOMPUTE_LOC(x) \
+  (RTL_FLAG_CHECK1 ("VALUE_RECOMPUTE_LOC", (x), VALUE)->volatil)
 /* Whether the value is currently being expanded.  */
 #define VALUE_RECURSED_INTO(x) \
   (RTL_FLAG_CHECK2 ("VALUE_RECURSED_INTO", (x), VALUE, DEBUG_EXPR)->used)
@@ -3725,7 +3748,7 @@ dataflow_set_preserve_mem_locs (void **s
 
       gcc_assert (var->n_var_parts == 1);
 
-      if (var->refcount > 1 || shared_hash_shared (set->vars))
+      if (shared_var_p (var, set->vars))
 	{
 	  for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
 	    {
@@ -3820,7 +3843,7 @@ dataflow_set_remove_mem_locs (void **slo
 
       gcc_assert (var->n_var_parts == 1);
 
-      if (var->refcount > 1 || shared_hash_shared (set->vars))
+      if (shared_var_p (var, set->vars))
 	{
 	  for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
 	    if (GET_CODE (loc->loc) == MEM)
@@ -3849,8 +3872,9 @@ dataflow_set_remove_mem_locs (void **slo
 	  /* If we have deleted the location which was last emitted
 	     we have to emit new location so add the variable to set
 	     of changed variables.  */
-	  if (var->var_part[0].cur_loc
-	      && rtx_equal_p (loc->loc, var->var_part[0].cur_loc))
+	  if (emit_notes
+	      || (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);
 	}
@@ -3864,7 +3888,9 @@ dataflow_set_remove_mem_locs (void **slo
 	}
       if (changed)
 	{
-	  if (var->n_var_parts && var->var_part[0].loc_chain)
+	  /* While emitting notes, leave the current location of
+	     values alone.  */
+	  if (!emit_notes && 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);
 	}
@@ -3910,12 +3936,7 @@ variable_part_different_p (variable_part
     {
       for (lc2 = vp2->loc_chain; lc2; lc2 = lc2->next)
 	{
-	  if (REG_P (lc1->loc) && REG_P (lc2->loc))
-	    {
-	      if (REGNO (lc1->loc) == REGNO (lc2->loc))
-		break;
-	    }
-	  if (rtx_equal_p (lc1->loc, lc2->loc))
+	  if (same_regno_or_equal_p (lc1->loc, lc2->loc))
 	    break;
 	}
       if (!lc2)
@@ -3977,12 +3998,12 @@ variable_different_p (variable var1, var
 	return true;
       if (compare_current_location)
 	{
-	  if (!((REG_P (var1->var_part[i].cur_loc)
-		 && REG_P (var2->var_part[i].cur_loc)
-		 && (REGNO (var1->var_part[i].cur_loc)
-		     == REGNO (var2->var_part[i].cur_loc)))
-		|| rtx_equal_p (var1->var_part[i].cur_loc,
-				var2->var_part[i].cur_loc)))
+	  if (!var1->var_part[i].cur_loc != !var2->var_part[i].cur_loc)
+	    return true;
+
+	  if (var1->var_part[i].cur_loc
+	      && !same_regno_or_equal_p (var1->var_part[i].cur_loc,
+					 var2->var_part[i].cur_loc))
 	    return true;
 	}
       /* One-part values have locations in a canonical order.  */
@@ -5697,14 +5718,9 @@ dump_variable_slot (void **slot, void *d
   return 1;
 }
 
-/* Print the information about variable VAR to dump file.  */
-
 static void
-dump_variable (variable var)
+dump_variable_name (variable var)
 {
-  int i;
-  location_chain node;
-
   if (dv_is_decl_p (var->dv))
     {
       const_tree decl = dv_as_decl (var->dv);
@@ -5724,6 +5740,17 @@ dump_variable (variable var)
       fputc (' ', dump_file);
       print_rtl_single (dump_file, dv_as_value (var->dv));
     }
+}
+
+/* Print the information about variable VAR to dump file.  */
+
+static void
+dump_variable (variable var)
+{
+  int i;
+  location_chain node;
+
+  dump_variable_name (var);
 
   for (i = 0; i < var->n_var_parts; i++)
     {
@@ -6002,7 +6029,7 @@ set_slot_part (dataflow_set *set, rtx lo
       if (r == 0)
 	return slot;
 
-      if (var->refcount > 1 || shared_hash_shared (set->vars))
+      if (shared_var_p (var, set->vars))
 	{
 	  slot = unshare_variable (set, slot, var, initialized);
 	  var = (variable)*slot;
@@ -6025,9 +6052,7 @@ set_slot_part (dataflow_set *set, rtx lo
 	  node = var->var_part[pos].loc_chain;
 
 	  if (node
-	      && ((REG_P (node->loc) && REG_P (loc)
-		   && REGNO (node->loc) == REGNO (loc))
-		  || rtx_equal_p (node->loc, loc)))
+	      && same_regno_or_equal_p (node->loc, loc))
 	    {
 	      /* LOC is in the beginning of the chain so we have nothing
 		 to do.  */
@@ -6041,7 +6066,7 @@ set_slot_part (dataflow_set *set, rtx lo
 	  else
 	    {
 	      /* We have to make a copy of a shared variable.  */
-	      if (var->refcount > 1 || shared_hash_shared (set->vars))
+	      if (shared_var_p (var, set->vars))
 		{
 		  slot = unshare_variable (set, slot, var, initialized);
 		  var = (variable)*slot;
@@ -6053,7 +6078,7 @@ set_slot_part (dataflow_set *set, rtx lo
 	  /* We have not found the location part, new one will be created.  */
 
 	  /* We have to make a copy of the shared variable.  */
-	  if (var->refcount > 1 || shared_hash_shared (set->vars))
+	  if (shared_var_p (var, set->vars))
 	    {
 	      slot = unshare_variable (set, slot, var, initialized);
 	      var = (variable)*slot;
@@ -6080,9 +6105,7 @@ set_slot_part (dataflow_set *set, rtx lo
       for (node = var->var_part[pos].loc_chain; node; node = next)
 	{
 	  next = node->next;
-	  if ((REG_P (node->loc) && REG_P (loc)
-	       && REGNO (node->loc) == REGNO (loc))
-	      || rtx_equal_p (node->loc, loc))
+	  if (same_regno_or_equal_p (node->loc, loc))
 	    {
 	      /* Save these values, to assign to the new node, before
 		 deleting this one.  */
@@ -6115,7 +6138,10 @@ set_slot_part (dataflow_set *set, rtx lo
   /* If no location was emitted do so.  */
   if (var->var_part[pos].cur_loc == NULL)
     {
-      var->var_part[pos].cur_loc = loc;
+      /* While emitting notes, leave the current location of values
+	 alone.  */
+      if (!onepart || !emit_notes || !dv_is_value_p (var->dv))
+	var->var_part[pos].cur_loc = loc;
       variable_was_changed (var, set);
     }
 
@@ -6245,16 +6271,14 @@ delete_slot_part (dataflow_set *set, rtx
       location_chain *nextp;
       bool changed;
 
-      if (var->refcount > 1 || shared_hash_shared (set->vars))
+      if (shared_var_p (var, set->vars))
 	{
 	  /* If the variable contains the location part we have to
 	     make a copy of the variable.  */
 	  for (node = var->var_part[pos].loc_chain; node;
 	       node = node->next)
 	    {
-	      if ((REG_P (node->loc) && REG_P (loc)
-		   && REGNO (node->loc) == REGNO (loc))
-		  || rtx_equal_p (node->loc, loc))
+	      if (same_regno_or_equal_p (node->loc, loc))
 		{
 		  slot = unshare_variable (set, slot, var,
 					   VAR_INIT_STATUS_UNKNOWN);
@@ -6265,39 +6289,46 @@ delete_slot_part (dataflow_set *set, rtx
 	}
 
       /* Delete the location part.  */
+      changed = false;
       nextp = &var->var_part[pos].loc_chain;
       for (node = *nextp; node; node = next)
 	{
 	  next = node->next;
-	  if ((REG_P (node->loc) && REG_P (loc)
-	       && REGNO (node->loc) == REGNO (loc))
-	      || rtx_equal_p (node->loc, loc))
+	  if (same_regno_or_equal_p (node->loc, loc))
 	    {
 	      if (emit_notes && pos == 0 && dv_onepart_p (var->dv))
-		remove_value_chains (var->dv, node->loc);
+		{
+		  remove_value_chains (var->dv, node->loc);
+		  if (dv_is_value_p (var->dv))
+		    VALUE_RECOMPUTE_LOC (dv_as_value (var->dv)) = true;
+		}
 	      pool_free (loc_chain_pool, node);
 	      *nextp = next;
+	      changed = true;
 	      break;
 	    }
 	  else
 	    nextp = &node->next;
 	}
 
-      /* If we have deleted the location which was last emitted
-	 we have to emit new location so add the variable to set
-	 of changed variables.  */
-      if (var->var_part[pos].cur_loc
-	  && ((REG_P (loc)
-	       && REG_P (var->var_part[pos].cur_loc)
-	       && REGNO (loc) == REGNO (var->var_part[pos].cur_loc))
-	      || rtx_equal_p (loc, var->var_part[pos].cur_loc)))
-	{
-	  changed = true;
-	  if (var->var_part[pos].loc_chain)
-	    var->var_part[pos].cur_loc = var->var_part[pos].loc_chain->loc;
+      /* While emitting notes, leave the current location of values
+	 alone.  */
+      if (!(emit_notes && pos == 0 && dv_is_value_p (var->dv)))
+	{
+	  /* If we have deleted the location which was last emitted we
+	     have to emit new location so add the variable to set of
+	     changed variables.  */
+	  if (var->var_part[pos].cur_loc
+	      && same_regno_or_equal_p (loc, var->var_part[pos].cur_loc))
+	    {
+	      changed = true;
+	      if (var->var_part[pos].loc_chain)
+		var->var_part[pos].cur_loc
+		  = var->var_part[pos].loc_chain->loc;
+	    }
+	  else
+	    changed = false;
 	}
-      else
-	changed = false;
 
       if (var->var_part[pos].loc_chain == NULL)
 	{
@@ -6335,16 +6366,25 @@ delete_variable_part (dataflow_set *set,
 
 /* Callback for cselib_expand_value, that looks for expressions
    holding the value in the var-tracking hash tables.  Return X for
-   standard processing, anything else is to be used as-is.  */
+   standard processing, anything else is to be used as-is.
+
+   When a STABLE expansion is requested, don't expand VALUEs marked as
+   needing recomputation of the current location, and only use the
+   current location.  */
 
 static rtx
-vt_expand_loc_callback (rtx x, bitmap regs, int max_depth, void *data)
+vt_expand_loc_callback_both (rtx x, bitmap regs, int max_depth,
+			     dataflow_set *set, bool stable,
+			     cselib_expand_callback callback)
 {
-  htab_t vars = (htab_t)data;
   decl_or_value dv;
+  void **slot;
   variable var;
   location_chain loc;
-  rtx result, subreg, xret;
+  rtx result, subreg, xret, cur_loc;
+  static rtx self_recurse;
+  bool self_recursing = self_recurse == x;
+  static int depth;
 
   switch (GET_CODE (x))
     {
@@ -6354,9 +6394,11 @@ vt_expand_loc_callback (rtx x, bitmap re
       if (GET_CODE (SUBREG_REG (x)) != VALUE)
 	return x;
 
+      depth++;
       subreg = cselib_expand_value_rtx_cb (SUBREG_REG (x), regs,
 					   max_depth - 1,
-					   vt_expand_loc_callback, data);
+					   callback, set);
+      depth--;
 
       if (!subreg)
 	return NULL;
@@ -6387,12 +6429,28 @@ vt_expand_loc_callback (rtx x, bitmap re
     }
 
   if (VALUE_RECURSED_INTO (x))
+    {
+      if (self_recursing)
+	return xret;
+      else
+	return NULL;
+    }
+
+  gcc_assert (!self_recursing);
+
+  if (stable && dv_changed_p (dv))
     return NULL;
 
-  var = (variable) htab_find_with_hash (vars, dv, dv_htab_hash (dv));
+  slot = shared_hash_find_slot_noinsert (set->vars, dv);
 
-  if (!var)
-    return xret;
+  if (!slot)
+    {
+      if (!depth && !stable && dv_is_value_p (dv) && dv_changed_p (dv))
+	set_dv_changed (dv, false);
+      return xret;
+    }
+
+  var = (variable)*slot;
 
   if (var->n_var_parts == 0)
     return xret;
@@ -6402,32 +6460,125 @@ vt_expand_loc_callback (rtx x, bitmap re
   VALUE_RECURSED_INTO (x) = true;
   result = NULL;
 
-  for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
+  if (dv_is_value_p (dv) && VALUE_RECOMPUTE_LOC (x))
+    cur_loc = NULL;
+  else
+    cur_loc = var->var_part[0].cur_loc;
+
+  depth++;
+
+  if (cur_loc)
     {
-      result = cselib_expand_value_rtx_cb (loc->loc, regs, max_depth,
-					   vt_expand_loc_callback, vars);
-      if (result)
-	break;
+      if (cur_loc == x)
+	self_recurse = x;
+      result = cselib_expand_value_rtx_cb (cur_loc, regs, max_depth,
+					   callback, set);
+      self_recurse = NULL;
+    }
+
+  if (!result && !stable && dv_changed_p (dv))
+    {
+      for (loc = var->var_part[0].loc_chain; loc; loc = loc->next)
+	{
+	  if (loc->loc == cur_loc)
+	    continue;
+
+	  result = cselib_expand_value_rtx_cb (loc->loc, regs, max_depth,
+					       callback, set);
+	  if (result)
+	    {
+	      cur_loc = loc->loc;
+	      break;
+	    }
+	}
+
+      if (!result && x != cur_loc)
+	{
+	  self_recurse = x;
+	  result = cselib_expand_value_rtx_cb (x, regs, max_depth,
+					       callback, set);
+	  self_recurse = NULL;
+
+	  if (result)
+	    cur_loc = x;
+	}
+
+      if (!result)
+	cur_loc = NULL;
+
+      depth--;
+
+      if (!depth)
+	{
+	  if (shared_var_p (var, set->vars))
+	    {
+	      slot = unshare_variable (set, slot, var,
+				       VAR_INIT_STATUS_UNKNOWN);
+	      var = (variable)*slot;
+	    }
+
+	  var->var_part[0].cur_loc = cur_loc;
+	  if (dv_is_value_p (dv))
+	    VALUE_RECOMPUTE_LOC (x) = false;
+
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      dump_variable_name (var);
+	      fputs ("curloc := ", dump_file);
+	      print_rtl_single (dump_file, cur_loc);
+	    }
+	}
+
+      /* After self recursion, return NULL rather than xret.  */
+      xret = NULL;
     }
+  else
+    depth--;
+
+  if (!depth && !stable && dv_is_value_p (dv) && dv_changed_p (dv))
+    set_dv_changed (dv, false);
 
   VALUE_RECURSED_INTO (x) = false;
-  if (result)
+
+  if (result || (stable && dv_changed_p (dv)))
     return result;
   else
     return xret;
 }
 
+/* Wrapper for vt_expand_loc_callback_both() in unstable expansion.  */
+
+static rtx
+vt_expand_loc_callback (rtx x, bitmap regs,
+			int max_depth, void *data)
+{
+  dataflow_set *set = (dataflow_set *)data;
+  return vt_expand_loc_callback_both (x, regs, max_depth, set, false,
+				      vt_expand_loc_callback);
+}
+
+/* Wrapper for vt_expand_loc_callback_both() in stable expansion.  */
+
+static rtx
+vt_expand_loc_callback_stable (rtx x, bitmap regs,
+			       int max_depth, void *data)
+{
+  dataflow_set *set = (dataflow_set *)data;
+  return vt_expand_loc_callback_both (x, regs, max_depth, set, true,
+				      vt_expand_loc_callback_stable);
+}
+
 /* Expand VALUEs in LOC, using VARS as well as cselib's equivalence
    tables.  */
 
 static rtx
-vt_expand_loc (rtx loc, htab_t vars)
+vt_expand_loc_cb (rtx loc, dataflow_set *set, cselib_expand_callback callback)
 {
   if (!MAY_HAVE_DEBUG_INSNS)
     return loc;
 
   loc = cselib_expand_value_rtx_cb (loc, scratch_regs, 5,
-				    vt_expand_loc_callback, vars);
+				    callback, set);
 
   if (loc && MEM_P (loc))
     loc = targetm.delegitimize_address (loc);
@@ -6438,6 +6589,61 @@ vt_expand_loc (rtx loc, htab_t vars)
   return loc;
 }
 
+/* Expand VALUEs in LOC, resolving their current locations as needed.  */
+
+static rtx
+vt_expand_loc (rtx loc, dataflow_set *set)
+{
+  return vt_expand_loc_cb (loc, set, vt_expand_loc_callback);
+}
+
+/* Expand VALUEs in LOC, using already-resolved locations.  */
+
+static rtx
+vt_expand_loc_stable (rtx loc, dataflow_set *set)
+{
+  return vt_expand_loc_cb (loc, set, vt_expand_loc_callback_stable);
+}
+
+/* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
+   additional parameters: WHERE specifies whether the note shall be emitted
+   before or after instruction INSN.  */
+
+static int
+emit_note_resolve_value (void **varp, void *data)
+{
+  variable var = (variable) *varp;
+  dataflow_set *set = (dataflow_set *)data;
+
+  if (!dv_is_value_p (var->dv))
+    {
+      gcc_assert (dv_changed_p (var->dv));
+      return 1;
+    }
+
+  /* This value may have been resolved while expanding another value
+     defined as cselib-equivalent to this one.  */
+  if (dv_changed_p (var->dv))
+    {
+      vt_expand_loc (dv_as_value (var->dv), set);
+      gcc_assert (!dv_changed_p (var->dv));
+    }
+
+#if ENABLE_CHECKING
+  var = shared_hash_find (set->vars, var->dv);
+  if (var)
+    {
+      gcc_assert (var->n_var_parts == 1);
+      gcc_assert (!dv_is_value_p (var->dv)
+		  || !VALUE_RECOMPUTE_LOC (dv_as_value (var->dv)));
+    }
+#endif
+
+  htab_clear_slot (changed_variables, varp);
+
+  return 1;
+}
+
 /* Emit the NOTE_INSN_VAR_LOCATION for variable *VARP.  DATA contains
    additional parameters: WHERE specifies whether the note shall be emitted
    before or after instruction INSN.  */
@@ -6446,9 +6652,10 @@ static int
 emit_note_insn_var_location (void **varp, void *data)
 {
   variable var = (variable) *varp;
-  rtx insn = ((emit_note_data *)data)->insn;
-  enum emit_note_where where = ((emit_note_data *)data)->where;
-  htab_t vars = ((emit_note_data *)data)->vars;
+  emit_note_data *dt = (emit_note_data *)data;
+  rtx insn = dt->insn;
+  enum emit_note_where where = dt->where;
+  dataflow_set *set = dt->varset;
   rtx note;
   int i, j, n_var_parts;
   bool complete;
@@ -6459,8 +6666,7 @@ emit_note_insn_var_location (void **varp
   rtx loc[MAX_VAR_PARTS];
   tree decl;
 
-  if (dv_is_value_p (var->dv))
-    goto clear;
+  gcc_assert (!dv_is_value_p (var->dv));
 
   decl = dv_as_decl (var->dv);
 
@@ -6485,7 +6691,7 @@ emit_note_insn_var_location (void **varp
       else if (last_limit > var->var_part[i].offset)
 	continue;
       offsets[n_var_parts] = var->var_part[i].offset;
-      loc2 = vt_expand_loc (var->var_part[i].loc_chain->loc, vars);
+      loc2 = vt_expand_loc (var->var_part[i].loc_chain->loc, set);
       if (!loc2)
 	{
 	  complete = false;
@@ -6505,7 +6711,7 @@ emit_note_insn_var_location (void **varp
 	  && wider_mode != VOIDmode
 	  && mode == GET_MODE (var->var_part[j].loc_chain->loc)
 	  && (REG_P (loc[n_var_parts]) || MEM_P (loc[n_var_parts]))
-	  && (loc2 = vt_expand_loc (var->var_part[j].loc_chain->loc, vars))
+	  && (loc2 = vt_expand_loc (var->var_part[j].loc_chain->loc, set))
 	  && GET_CODE (loc[n_var_parts]) == GET_CODE (loc2)
 	  && last_limit == var->var_part[j].offset)
 	{
@@ -6581,7 +6787,8 @@ emit_note_insn_var_location (void **varp
   if (!complete)
     {
       NOTE_VAR_LOCATION (note) = gen_rtx_VAR_LOCATION (VOIDmode, decl,
-						       NULL_RTX, (int) initialized);
+						       NULL_RTX,
+						       (int) initialized);
     }
   else if (n_var_parts == 1)
     {
@@ -6626,34 +6833,124 @@ DEF_VEC_ALLOC_P (variable, heap);
 
 static VEC (variable, heap) *changed_variables_stack;
 
-/* Populate changed_variables_stack with variable_def pointers
-   that need variable_was_changed called on them.  */
+/* Return true if the one-part variable VAR needs its cur_loc
+   recomputed, false otherwise.  */
 
-static int
-check_changed_vars_1 (void **slot, void *data)
+static variable
+check_changed_vars_0 (variable var, dataflow_set *set)
 {
-  variable var = (variable) *slot;
-  htab_t htab = (htab_t) data;
+  rtx cur_loc = NULL;
+  location_chain loc_chain = NULL;
 
-  if (dv_is_value_p (var->dv))
+  if (!dv_is_value_p (var->dv))
+    return var;
+
+  if (var->n_var_parts)
     {
+      gcc_assert (var->n_var_parts == 1);
+
+      cur_loc = var->var_part[0].cur_loc;
+      loc_chain = var->var_part[0].loc_chain;
+    }
+
+  if (VALUE_RECOMPUTE_LOC (dv_as_value (var->dv)))
+    ;
+  /* If cur_loc is NULL and so is loc_chain (including a value
+     definition), no change is needed.  */
+  else if (!cur_loc)
+    {
+      if (!loc_chain
+	  && (!dv_is_value_p (var->dv)
+	      || !vt_expand_loc_stable (dv_as_value (var->dv), set)))
+	return NULL;
+    }
+  /* If we're using the definition of a VALUE, check that it's still
+     valid.  */
+  else if (dv_as_value (var->dv) == cur_loc)
+    {
+      if (vt_expand_loc_stable (cur_loc, set))
+	return NULL;
+    }
+  else
+    {
+      /* Look for cur_loc in the loc_chain.  */
+      location_chain node = loc_chain;
+      while (node && node->loc != cur_loc)
+	node = node->next;
+
+      /* If it still expands to something useful, no change is needed.
+	 Note that, if cur_loc or any of its components is itself
+	 marked as changed, the expansion will fail.  */
+      if (node && vt_expand_loc_stable (cur_loc, set))
+	return NULL;
+
+    }
+
+  VALUE_RECOMPUTE_LOC (dv_as_value (var->dv)) = true;
+
+  /* if (dv_is_value_p (var->dv)) */
+    {
+      rtx val = dv_as_value (var->dv);
       value_chain vc
 	= (value_chain) htab_find_with_hash (value_chains, var->dv,
 					     dv_htab_hash (var->dv));
 
-      if (vc == NULL)
-	return 1;
+      if (!vc)
+	return var;
+
       for (vc = vc->next; vc; vc = vc->next)
 	if (!dv_changed_p (vc->dv))
 	  {
-	    variable vcvar
-	      = (variable) htab_find_with_hash (htab, vc->dv,
-						dv_htab_hash (vc->dv));
-	    if (vcvar)
-	      VEC_safe_push (variable, heap, changed_variables_stack,
-			     vcvar);
+	    variable vcvar = shared_hash_find (set->vars, vc->dv);
+	    rtx vcloc;
+
+	    if (!vcvar)
+	      continue;
+
+	    gcc_assert (dv_onepart_p (vc->dv));
+
+	    if (dv_is_value_p (vc->dv))
+	      {
+		gcc_assert (vcvar->n_var_parts == 1);
+		vcloc = vcvar->var_part[0].cur_loc;
+	      }
+	    else
+	      vcloc = NULL;
+
+	    if (vcloc == NULL
+		|| vcloc == val
+		|| vcloc == dv_as_opaque (vc->dv))
+	      {
+		set_dv_changed (vc->dv, true);
+		VEC_safe_push (variable, heap, changed_variables_stack,
+			       vcvar);
+		/* We might recurse right away, but this would
+		   complicate hashtable management, and it's not
+		   necessary: once vc->dv is marked as changed, nodes
+		   that have it as cur_loc will be as well.  */
+	      }
 	  }
     }
+
+  return var;
+}
+
+/* Populate changed_variables_stack with variable_def pointers
+   that need variable_was_changed called on them.  */
+
+static int
+check_changed_vars_1 (void **slot, void *data)
+{
+  variable var = (variable) *slot;
+  dataflow_set *set = (dataflow_set *)data;
+  variable newvar = check_changed_vars_0 (var, set);
+
+  if (!newvar)
+    {
+      set_dv_changed (var->dv, false);
+      htab_clear_slot (changed_variables, slot);
+    }
+
   return 1;
 }
 
@@ -6662,27 +6959,14 @@ check_changed_vars_1 (void **slot, void 
    VALUE from its loc_chain.  */
 
 static void
-check_changed_vars_2 (variable var, htab_t htab)
+check_changed_vars_2 (variable var, dataflow_set *set)
 {
-  variable_was_changed (var, NULL);
-  if (dv_is_value_p (var->dv))
-    {
-      value_chain vc
-	= (value_chain) htab_find_with_hash (value_chains, var->dv,
-					     dv_htab_hash (var->dv));
+  variable newvar = check_changed_vars_0 (var, set);
 
-      if (vc == NULL)
-	return;
-      for (vc = vc->next; vc; vc = vc->next)
-	if (!dv_changed_p (vc->dv))
-	  {
-	    variable vcvar
-	      = (variable) htab_find_with_hash (htab, vc->dv,
-						dv_htab_hash (vc->dv));
-	    if (vcvar)
-	      check_changed_vars_2 (vcvar, htab);
-	  }
-    }
+  if (newvar)
+    variable_was_changed (newvar, NULL);
+  else
+    set_dv_changed (var->dv, false);
 }
 
 /* Emit NOTE_INSN_VAR_LOCATION note for each variable from a chain
@@ -6691,10 +6975,9 @@ check_changed_vars_2 (variable var, htab
 
 static void
 emit_notes_for_changes (rtx insn, enum emit_note_where where,
-			shared_hash vars)
+			dataflow_set *set)
 {
   emit_note_data data;
-  htab_t htab = shared_hash_htab (vars);
 
   if (!htab_elements (changed_variables))
     return;
@@ -6704,15 +6987,16 @@ emit_notes_for_changes (rtx insn, enum e
       /* Unfortunately this has to be done in two steps, because
 	 we can't traverse a hashtab into which we are inserting
 	 through variable_was_changed.  */
-      htab_traverse (changed_variables, check_changed_vars_1, htab);
+      htab_traverse (changed_variables, check_changed_vars_1, set);
       while (VEC_length (variable, changed_variables_stack) > 0)
 	check_changed_vars_2 (VEC_pop (variable, changed_variables_stack),
-			      htab);
+			      set);
+      htab_traverse (changed_variables, emit_note_resolve_value, set);
     }
 
   data.insn = insn;
   data.where = where;
-  data.vars = htab;
+  data.varset = set;
 
   htab_traverse (changed_variables, emit_note_insn_var_location, &data);
 }
@@ -6721,14 +7005,19 @@ emit_notes_for_changes (rtx insn, enum e
    same variable in hash table DATA or is not there at all.  */
 
 static int
-emit_notes_for_differences_1 (void **slot, void *data)
+emit_notes_for_differences_1 (void **old_slot, void *data)
 {
-  htab_t new_vars = (htab_t) data;
+  dataflow_set *new_set = (dataflow_set *)data;
+  void **new_slot;
   variable old_var, new_var;
 
-  old_var = (variable) *slot;
-  new_var = (variable) htab_find_with_hash (new_vars, old_var->dv,
-					    dv_htab_hash (old_var->dv));
+  old_var = (variable) *old_slot;
+
+  new_slot = shared_hash_find_slot_noinsert (new_set->vars, old_var->dv);
+  if (new_slot)
+    new_var = (variable) *new_slot;
+  else
+    new_var = NULL;
 
   if (!new_var)
     {
@@ -6739,7 +7028,7 @@ emit_notes_for_differences_1 (void **slo
       empty_var->dv = old_var->dv;
       empty_var->refcount = 0;
       empty_var->n_var_parts = 0;
-      if (dv_onepart_p (old_var->dv))
+      if (dv_onepart_p (old_var->dv) && old_var->n_var_parts)
 	{
 	  location_chain lc;
 
@@ -6756,6 +7045,23 @@ emit_notes_for_differences_1 (void **slo
       if (dv_onepart_p (old_var->dv))
 	{
 	  location_chain lc1, lc2;
+	  rtx old_loc = old_var->var_part[0].cur_loc;
+	  rtx new_loc = NULL;
+	  bool recompute_loc = false;
+
+	  /* Force a note to be emitted on all dependent vars, unless
+	     the same location was already current.  This may actually
+	     force a note even when one isn't necessary, say if both
+	     have the same REG as current, but not with the same
+	     address, or even RTXs with the same address, but with
+	     other intervening location expressions.  This shouldn't
+	     happen very often and, worst case, we emit some redundant
+	     notes.  */
+	  if (new_loc != old_loc && dv_is_value_p (old_var->dv))
+	    {
+	      recompute_loc = true;
+	      new_loc = NULL;
+	    }
 
 	  gcc_assert (old_var->n_var_parts == 1);
 	  gcc_assert (new_var->n_var_parts == 1);
@@ -6766,6 +7072,11 @@ emit_notes_for_differences_1 (void **slo
 		 && ((REG_P (lc1->loc) && REG_P (lc2->loc))
 		     || rtx_equal_p (lc1->loc, lc2->loc)))
 	    {
+	      if (old_loc == lc2->loc)
+		{
+		  new_loc = lc2->loc;
+		  recompute_loc = false;
+		}
 	      lc1 = lc1->next;
 	      lc2 = lc2->next;
 	    }
@@ -6773,6 +7084,12 @@ emit_notes_for_differences_1 (void **slo
 	    add_value_chains (old_var->dv, lc2->loc);
 	  for (; lc1; lc1 = lc1->next)
 	    remove_value_chains (old_var->dv, lc1->loc);
+
+	  if (new_loc && new_var->var_part[0].cur_loc != new_loc
+	      && !shared_var_p (new_var, new_set->vars))
+	    new_var->var_part[0].cur_loc = new_loc;
+	  else if (recompute_loc)
+	    VALUE_RECOMPUTE_LOC (dv_as_value (new_var->dv)) = true;
 	}
       variable_was_changed (new_var, NULL);
     }
@@ -6787,12 +7104,13 @@ emit_notes_for_differences_1 (void **slo
 static int
 emit_notes_for_differences_2 (void **slot, void *data)
 {
-  htab_t old_vars = (htab_t) data;
+  dataflow_set *old_set = (dataflow_set *)data;
+  shared_hash old_vars = old_set->vars;
   variable old_var, new_var;
 
   new_var = (variable) *slot;
-  old_var = (variable) htab_find_with_hash (old_vars, new_var->dv,
-					    dv_htab_hash (new_var->dv));
+  old_var = (variable) shared_hash_find (old_vars, new_var->dv);
+
   if (!old_var)
     {
       /* Variable has appeared.  */
@@ -6829,12 +7147,10 @@ emit_notes_for_differences (rtx insn, da
     }
 
   htab_traverse (shared_hash_htab (old_set->vars),
-		 emit_notes_for_differences_1,
-		 shared_hash_htab (new_set->vars));
+		 emit_notes_for_differences_1, new_set);
   htab_traverse (shared_hash_htab (new_set->vars),
-		 emit_notes_for_differences_2,
-		 shared_hash_htab (old_set->vars));
-  emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN, new_set->vars);
+		 emit_notes_for_differences_2, old_set);
+  emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN, new_set);
 }
 
 /* Emit the notes for changes of location parts in the basic block BB.  */
@@ -6855,7 +7171,7 @@ emit_notes_in_bb (basic_block bb, datafl
 	{
 	  case MO_CALL:
 	    dataflow_set_clear_at_call (set);
-	    emit_notes_for_changes (insn, EMIT_NOTE_AFTER_CALL_INSN, set->vars);
+	    emit_notes_for_changes (insn, EMIT_NOTE_AFTER_CALL_INSN, set);
 	    break;
 
 	  case MO_USE:
@@ -6867,7 +7183,7 @@ emit_notes_in_bb (basic_block bb, datafl
 	      else
 		var_mem_set (set, loc, VAR_INIT_STATUS_UNINITIALIZED, NULL);
 
-	      emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set->vars);
+	      emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set);
 	    }
 	    break;
 
@@ -6901,7 +7217,7 @@ emit_notes_in_bb (basic_block bb, datafl
 				     INSERT);
 		}
 
-	      emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set->vars);
+	      emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set);
 	    }
 	    break;
 
@@ -6932,7 +7248,7 @@ emit_notes_in_bb (basic_block bb, datafl
 				 NULL);
 		}
 
-	      emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN, set->vars);
+	      emit_notes_for_changes (insn, EMIT_NOTE_BEFORE_INSN, set);
 	    }
 	    break;
 
@@ -7011,7 +7327,7 @@ emit_notes_in_bb (basic_block bb, datafl
 	      val_store (set, val, vloc, insn);
 
 	      emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
-				      set->vars);
+				      set);
 	    }
 	    break;
 
@@ -7034,7 +7350,7 @@ emit_notes_in_bb (basic_block bb, datafl
 					set_src);
 
 	      emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
-				      set->vars);
+				      set);
 	    }
 	    break;
 
@@ -7059,7 +7375,7 @@ emit_notes_in_bb (basic_block bb, datafl
 		var_mem_delete_and_set (set, loc, false, src_status, set_src);
 
 	      emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
-				      set->vars);
+				      set);
 	    }
 	    break;
 
@@ -7072,7 +7388,7 @@ emit_notes_in_bb (basic_block bb, datafl
 	      else
 		var_mem_delete (set, loc, false);
 
-	      emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set->vars);
+	      emit_notes_for_changes (insn, EMIT_NOTE_AFTER_INSN, set);
 	    }
 	    break;
 
@@ -7086,7 +7402,7 @@ emit_notes_in_bb (basic_block bb, datafl
 		var_mem_delete (set, loc, true);
 
 	      emit_notes_for_changes (NEXT_INSN (insn), EMIT_NOTE_BEFORE_INSN,
-				      set->vars);
+				      set);
 	    }
 	    break;
 
@@ -7103,7 +7419,7 @@ static void
 vt_emit_notes (void)
 {
   basic_block bb;
-  dataflow_set cur;
+  dataflow_set cur, *last;
 
   gcc_assert (!htab_elements (changed_variables));
 
@@ -7120,24 +7436,26 @@ vt_emit_notes (void)
     changed_variables_stack = VEC_alloc (variable, heap, 40);
 
   dataflow_set_init (&cur);
+  last = &cur;
 
   FOR_EACH_BB (bb)
     {
+      last = &VTI (bb)->in;
+
       /* Emit the notes for changes of variable locations between two
 	 subsequent basic blocks.  */
-      emit_notes_for_differences (BB_HEAD (bb), &cur, &VTI (bb)->in);
+      emit_notes_for_differences (BB_HEAD (bb), &cur, last);
 
       /* Emit the notes for the changes in the basic block itself.  */
       emit_notes_in_bb (bb, &cur);
 
       /* Free memory occupied by the in hash table, we won't need it
 	 again.  */
-      dataflow_set_clear (&VTI (bb)->in);
+      dataflow_set_clear (last);
     }
 #ifdef ENABLE_CHECKING
   htab_traverse (shared_hash_htab (cur.vars),
-		 emit_notes_for_differences_1,
-		 shared_hash_htab (empty_shared_hash));
+		 emit_notes_for_differences_1, last);
   if (MAY_HAVE_DEBUG_INSNS)
     gcc_assert (htab_elements (value_chains) == 0);
 #endif
-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer

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