stop unnecessary spills in gcc/reload1.c

[edmundo at rano dot demon dot co dot uk]

Here's a little patch for reload1.c that stops it from letting
instructions that are going to be deleted anyway from causing a spill.
In many cases the damage done by the unnecessary spill is repaired
later anyway, but there's an example below of a C function which gets
better register allocation on Intel with this patch than without it
(gcc -S -O2 -dl -dg).

Even when the final code is identical you can see from .c.lreg and
.c.greg that fewer spills are happening, so I think this patch is
morally right.

It's very messy, though. Someone more familiar with the data
structures could probably simplify it a lot. In particular, the first
hunk of the patch seems, from experiments, to be unnecessary. However,
until I can see why an instruction deleted by a recursive call to
delete_dead_insn can never be deleted beforehand due to being in
reg_equiv_init[i] for a smaller i, I feel safer doing the deleting in
this order ...

I've tested this by bootstrapping the compiler on Intel with extra
code doing various consistency checks.

Edmund


Here's the C function I mentioned:

int add(int x1, int x3, int x4, int x5, int x6, int x7, int n)
{
  int x2 = 0;

  for (;;) {
    x1 += 1;
    x2 += x1;
    x3 += x2;
    x4 += x3;
    x5 += x4;
    x6 += x5;
    x7 += x6;
    if (x7 > n) return x1;
  }
}


Here's the patch itself:

--- egcs/gcc/reload1.c.orig	Sat May  8 02:34:55 1999
+++ egcs/gcc/reload1.c	Sun Jun 13 19:21:38 1999
@@ -1032,12 +1032,23 @@
 		continue;
 	      if (reg_set_p (regno_reg_rtx[i], PATTERN (equiv_insn)))
 		delete_dead_insn (equiv_insn);
-	      else
-		{
-		  PUT_CODE (equiv_insn, NOTE);
-		  NOTE_SOURCE_FILE (equiv_insn) = 0;
-		  NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED;
-		}
+	    }
+	}
+    }
+
+  for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
+    {
+      if (reg_renumber[i] < 0 && reg_equiv_init[i] != 0)
+	{
+	  rtx list;
+	  for (list = reg_equiv_init[i]; list; list = XEXP (list, 1))
+	    {
+	      rtx equiv_insn = XEXP (list, 0);
+	      if (GET_CODE (equiv_insn) == NOTE)
+		continue;
+	      PUT_CODE (equiv_insn, NOTE);
+	      NOTE_SOURCE_FILE (equiv_insn) = 0;
+	      NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED;
 	    }
 	}
     }
@@ -1397,6 +1408,64 @@
 	      continue;
 	    }
 
+	  /* Also skip other insns that only set an equivalence
+	     and would be deleted later if nothing else changes */
+	  {
+	    rtx insn2, set2, list, next_insn, dest, arg;
+	    int i;
+
+	    insn2 = insn;
+	    for (;;)
+	      {
+		/* Find equivalencing insns, referring to how
+		   reg_equiv_init was set up in the first place */
+		if ((set2 = single_set (insn2))
+		    && ((arg = SET_DEST (set2), GET_CODE (arg) == REG)
+			|| (arg = SET_SRC (set2), GET_CODE (arg) == REG))
+		    && (i = REGNO (arg)) >= FIRST_PSEUDO_REGISTER
+		    && reg_renumber[i] < 0)
+		  {
+		    for (list = reg_equiv_init[i]; list; list = XEXP (list, 1))
+		      {
+			if (insn2 == XEXP (list, 0)
+			    && GET_CODE (insn2) != NOTE
+			    && (insn2 == insn
+				|| reg_set_p (regno_reg_rtx[i],
+					      PATTERN (insn2))))
+			  break;
+		      }
+		    if (list)
+		      break;
+		  }
+
+		/* This test duplicates delete_dead_insn, but
+		   looking forwards instead of backwards. */
+		if ((next_insn = next_real_insn (insn2))
+		    && GET_CODE (PATTERN (insn2)) == SET
+		    && (dest = SET_DEST (PATTERN (insn2)),
+			GET_CODE (dest) == REG)
+		    && reg_mentioned_p (dest, PATTERN (next_insn))
+		    && find_regno_note (next_insn, REG_DEAD, REGNO (dest))
+		    && ! side_effects_p (SET_SRC (PATTERN (insn))))
+		  {
+		    insn2 = next_insn;
+		    continue;
+		  }
+
+		insn2 = 0;
+		break;
+	      }
+	    if (insn2)
+	      {
+		/* Clear out the shortcuts */
+		chain->need_elim = 0;
+		chain->need_reload = 0;
+		chain->need_operand_change = 0;
+		insn = insn2;
+		continue;
+	      }
+	  }
+	    
 	  /* If needed, eliminate any eliminable registers.  */
 	  if (num_eliminable || num_eliminable_invariants)
 	    did_elimination = eliminate_regs_in_insn (insn, 0);