PR25514: A problem with note distribution in combine

Richard Sandiford richard@codesourcery.com
Tue Apr 25 15:39:00 GMT 2006


This patch fixes PR rtl-optimization/25514.  The PR is closely
related to PR22002, the patch for which was posted here:

    http://gcc.gnu.org/ml/gcc-patches/2005-11/msg00598.html

In the testcase below, the else block looks like this before combine:

    A: (set (reg tmp) (reg node))
         REG_EQUAL (symbol_ref "global_list")
         REG_DEAD (reg node)

    B: (set (reg node) (reg next))
         REG_DEAD (reg next)

    C: (set (mem (const (plus (symbol_ref "global_list") (const_int 4))))
            (mem (plus (reg node) (const_int 4))))

    D: (set (mem (reg tmp)) (mem (reg node)))
         REG_DEAD (reg node)

Combine considers combining A and D, but rightly declines because of the
assignment to NODE in B.  It then replaces the right hand side of A with
the REG_EQUAL note and tries again.  This time it succeeds with:

    D': (set (mem (symbol_ref "global_list"))
             (mem (reg node)))

distribute_notes then has to update the live range of NODE that previously
ended at A.

So far this is the same as the situation Alan described.  The crucial
difference is that in this case, the combined instruction reads the
new value of the REG_DEAD register, whereas Alan's patch only handles
the case where the REG_DEAD register is not used in the combined
instruction at all.

Alan added the comment:

              /* You might think you could search back from FROM_INSN
                 rather than from I3, but combine tries to split invalid
                 combined instructions.  This can result in the old I2
                 or I1 moving later in the insn sequence.  */
              for (tem = PREV_INSN (tem); place == 0; tem = PREV_INSN (tem))

But I don't quite follow that.  I think the idea of the original code
was this:

  (1) The REG_DEAD note refers to something that was used in the
      right hand side of the old FROM_INSN pattern (if FROM_INSN
      is nonnull)

  (2) The right hand side of that pattern has been combined into
      what is now I3 and I2 (if the latter is nonnull)

  (3) The register used to die at FROM_INSN.

  (4) Therefore, the register now dies at the last use before or
      during I3.  If there is no such use, the definition of the
      register is now unused.

  (5) (4) implies searching back from I3 (== D') looking for the first
      use or set of the REG_DEAD register.  If we find a use, we should
      add the REG_DEAD note there.  If we find a set, we should try to
      delete the set as dead, or add a REG_UNUSED note if that isn't
      possible.

The search described in (5) could be quite expensive, so
distribute_notes has some straight-line code to handle common cases.
One of the straight-line cases is where I3 itself uses the register.
Having disposed of that, the main loop can start at the insn before
I3 rather than I3 itself.

Forgetting about the bug in hand, that approach seems correct to me,
so I don't really see what the comment is trying to apologise for.
Conceptually, the search really should start at I3.

The problem of course is that (2) does not hold in this case.
The original rhs of FROM_INSN (the one to which the REG_DEAD note
applies) was _not_ used in the combination; a REG_EQUAL note was
used instead.  Thus any use of the register after FROM_INSN
cannot be part of the same live range.

I therefore think we should base the start of the search on whether the
REG_DEAD note refers to something that was combined (the usual case) or
not (this case).  In the former case we start at I3, as now, and in the
latter case we start before FROM_INSN.

The patch uses a new global variable to distinguish the two cases.
I know this isn't elegant, but I think it's simpler and faster
than trying to propagate the information from combine_instructios
by other means, and we already use global variables for other parts
of the combiner state.

I've tested this patch on m68k-linux-gnu on csl/coldfire-4_1 (it isn't
possible to test Coldfire on mainline without unmerged patches).
I've also run compile.exp=pr25514.c on an m68k-elf mainline
crosscompiler before and after the patch to make sure it failed
beforehand and passed afterwards.  Finally, I bootstrapped &
regression-tested on i686-pc-linux-gnu.  OK to install?

Richard


	PR rtl-optimization/25514
	* combine.c (replaced_rhs_insn): New variable.
	(combine_instructions): Set replaced_rhs_insn when trying to replace
	a SET_SRC with a REG_EQUAL note.
	(distribute_notes): Use replaced_rhs_insn when determining the live
	range of a REG_DEAD register.

gcc/testsute
	* gcc.c-torture/compile/pr25514.c: New test.

Index: gcc/testsuite/gcc.c-torture/compile/pr25514.c
===================================================================
--- gcc/testsuite/gcc.c-torture/compile/pr25514.c	(revision 0)
+++ gcc/testsuite/gcc.c-torture/compile/pr25514.c	(revision 0)
@@ -0,0 +1,24 @@
+struct node {
+  struct node *next;
+  int value;
+};
+
+struct node *current_node, global_list;
+
+void
+bar (void)
+{
+  struct node *node, *next;
+
+  node = current_node;
+  next = node->next;
+  if (node != &global_list)
+    current_node = next;
+  else
+    {
+      node = global_list.next;
+      global_list.value = node->value;
+      global_list.next = node->next;
+    }
+  foo (node);
+}
Index: gcc/combine.c
===================================================================
--- gcc/combine.c	(revision 113248)
+++ gcc/combine.c	(working copy)
@@ -123,6 +123,11 @@ Software Foundation; either version 2, o
 
 static int total_attempts, total_merges, total_extras, total_successes;
 
+/* Sometimes combine tries to replace the right hand side of an insn
+   with the value of a REG_EQUAL note.  This is the insn that has been
+   so modified, or null if none.  */
+
+static rtx replaced_rhs_insn;
 
 /* Vector mapping INSN_UIDs to cuids.
    The cuids are like uids but increase monotonically always.
@@ -922,8 +927,10 @@ combine_instructions (rtx f, unsigned in
 			 be deleted or recognized by try_combine.  */
 		      rtx orig = SET_SRC (set);
 		      SET_SRC (set) = note;
+		      replaced_rhs_insn = temp;
 		      next = try_combine (insn, temp, NULL_RTX,
 					  &new_direct_jump_p);
+		      replaced_rhs_insn = NULL;
 		      if (next)
 			goto retry;
 		      SET_SRC (set) = orig;
@@ -12085,7 +12092,15 @@ distribute_notes (rtx notes, rtx from_in
 	  break;
 
 	case REG_DEAD:
-	  /* If the register is used as an input in I3, it dies there.
+	  /* If we replaced the right hand side of FROM_INSN with a
+	     REG_EQUAL note, the original use of the dying register
+	     will not have been combined into I3 and I2.  In such cases,
+	     FROM_INSN is guaranteed to be the first of the combined
+	     instructions, so we simply need to search back before
+	     FROM_INSN for the previous use or set of this register,
+	     then alter the notes there appropriately.
+
+	     If the register is used as an input in I3, it dies there.
 	     Similarly for I2, if it is nonzero and adjacent to I3.
 
 	     If the register is not used as an input in either I3 or I2
@@ -12099,30 +12114,30 @@ distribute_notes (rtx notes, rtx from_in
 	     In both cases, we must search to see if we can find a previous
 	     use of A and put the death note there.  */
 
-	  if (from_insn
-	      && CALL_P (from_insn)
-	      && find_reg_fusage (from_insn, USE, XEXP (note, 0)))
-	    place = from_insn;
-	  else if (reg_referenced_p (XEXP (note, 0), PATTERN (i3)))
-	    place = i3;
-	  else if (i2 != 0 && next_nonnote_insn (i2) == i3
-		   && reg_referenced_p (XEXP (note, 0), PATTERN (i2)))
-	    place = i2;
-
-	  if (place == 0
-	      && (rtx_equal_p (XEXP (note, 0), elim_i2)
-		  || rtx_equal_p (XEXP (note, 0), elim_i1)))
-	    break;
+	  if (from_insn && from_insn == replaced_rhs_insn)
+	    tem = from_insn;
+	  else
+	    {
+	      if (from_insn
+		  && CALL_P (from_insn)
+		  && find_reg_fusage (from_insn, USE, XEXP (note, 0)))
+		place = from_insn;
+	      else if (reg_referenced_p (XEXP (note, 0), PATTERN (i3)))
+		place = i3;
+	      else if (i2 != 0 && next_nonnote_insn (i2) == i3
+		       && reg_referenced_p (XEXP (note, 0), PATTERN (i2)))
+		place = i2;
+	      else if (rtx_equal_p (XEXP (note, 0), elim_i2)
+		       || rtx_equal_p (XEXP (note, 0), elim_i1))
+		break;
+	      tem = i3;
+	    }
 
 	  if (place == 0)
 	    {
 	      basic_block bb = this_basic_block;
 
-	      /* You might think you could search back from FROM_INSN
-		 rather than from I3, but combine tries to split invalid
-		 combined instructions.  This can result in the old I2
-		 or I1 moving later in the insn sequence.  */
-	      for (tem = PREV_INSN (i3); place == 0; tem = PREV_INSN (tem))
+	      for (tem = PREV_INSN (tem); place == 0; tem = PREV_INSN (tem))
 		{
 		  if (! INSN_P (tem))
 		    {
@@ -12222,22 +12237,6 @@ distribute_notes (rtx notes, rtx from_in
 			   || (CALL_P (tem)
 			       && find_reg_fusage (tem, USE, XEXP (note, 0))))
 		    {
-		      /* This may not be the correct place for the death
-			 note if FROM_INSN is before TEM, and the reg is
-			 set between FROM_INSN and TEM.  The reg might
-			 die two or more times.  An existing death note
-			 means we are looking at the wrong live range.  */
-		      if (from_insn
-			  && INSN_CUID (from_insn) < INSN_CUID (tem)
-			  && find_regno_note (tem, REG_DEAD,
-					      REGNO (XEXP (note, 0))))
-			{
-			  tem = from_insn;
-			  if (tem == BB_HEAD (bb))
-			    break;
-			  continue;
-			}
-
 		      place = tem;
 
 		      /* If we are doing a 3->2 combination, and we have a



More information about the Gcc-patches mailing list