[PATCH][reload] Fix inheritance bug with register elimination

[Rask Ingemann Lambertsen <rask at sygehus dot dk>]

gcc/testsuite/gcc.dg/20020210-1.c execution was failing on my 16-bit x86
target. The testcase contains this simple little function, which was
being miscompiled:

void
foo (int a, int b, int c, int d, int e)
{
  bar (a, b, c, d, e);
}

Compare the asm output with -fno-omit-frame-pointer to the left and
-fomit-frame-pointer to the right:

foo:					foo:
	pushw	%bp				pushw	%bp
	movw	%sp,	%bp	    <
	subw	$10,	%sp			subw	$10,	%sp
	pushw	12(%bp)		    |		movw	%sp,	%bp
	pushw	10(%bp)		    |		pushw	22(%bp)
	pushw	8(%bp)		    |		pushw	22(%bp)
	pushw	6(%bp)		    |		pushw	22(%bp)
	pushw	4(%bp)		    |		pushw	22(%bp)
				    >		pushw	22(%bp)
	call	bar				call	bar
	addw	$10,	%sp	    |		addw	$20,	%sp
	movw	%bp,	%sp	    <
	popw	%bp				popw	%bp
	ret					ret

The first push is OK: The argument pointer has been eliminated as %bp + 4
and to the right, %bp has been eliminated as %sp + 10, so pushw 12(%bp)
becomes pushw 22(%sp). Because %sp isn't a base register, reload finds a
free base register, in this case %bp, emits the necessary reload insn and
uses %bp in place of %sp: pushw 22(%sp) becomes pushw 22(%bp).

The second push is where things go wrong: The previous push decreased %sp by
2 and so reload increases the elimination offset from 10 to 12. %bp is now
eliminated as %sp + 12, so pushw 10(%bp) becomes pushw 22(%sp). Again,
reload needs to find a valid base register and makes a reload from %sp to %bp
and turns pushw 22(%sp) into pushw 22(%bp). The inheritance code sees that
we have already copied %sp to %bp for the first push and decides that this
reload should be inherited by the second push. The fact that %sp changed
between the two pushes goes unnoticed by the inheritance code. Result: We
pass the wrong argument to bar(). The patch below fixes this problem by
preventing the affected reload(s) from being inherited further.

Broken:					Fixed:
foo:					foo:
	pushw	%bp				pushw	%bp
	subw	$10,	%sp			subw	$10,	%sp
	movw	%sp,	%bp			movw	%sp,	%bp
	pushw	22(%bp)				pushw	22(%bp)
				    >		movw	%sp,	%bp
	pushw	22(%bp)				pushw	22(%bp)
				    >		movw	%sp,	%bp
	pushw	22(%bp)				pushw	22(%bp)
				    >		movw	%sp,	%bp
	pushw	22(%bp)				pushw	22(%bp)
				    >		movw	%sp,	%bp
	pushw	22(%bp)				pushw	22(%bp)
	call	bar				call	bar
	addw	$20,	%sp			addw	$20,	%sp
	popw	%bp				popw	%bp
	ret					ret

(Yes, it would be nice to adjust the address accordingly instead, but
that'll be another patch.)

This fixes a lot of execution failures, likely because libgcc and newlib
were also miscompiled:

                === gcc Summary ===

-# of expected passes           38538
-# of unexpected failures       1901
+# of expected passes           38801
+# of unexpected failures       1652
 # of unexpected successes      1
 # of expected failures         79
-# of unresolved testcases      177
+# of unresolved testcases      165
 # of untested testcases        35
-# of unsupported tests         592
+# of unsupported tests         591
 /home/rask/cvsbuild/gcc/gcc/xgcc  version 4.3.0 20070501 (experimental) (with 8086 modifications)

I do see new execution failures for the following tests which used to pass
at some optimization levels:
gcc.c-torture/execute/20021118-2.c (floating point is broken)
gcc.c-torture/execute/20021120-3.c (C library issue? Many *printf failures)
gcc.c-torture/execute/980223.c (?)
gcc.c-torture/execute/nestfunc-3.c (nested functions likely broken)

I'm going to test this patch on several targets over the next few days.
Interesting targets are those which allow register elimination, preferably
to registers which are not base registers. Suggestions are welcome.
I'm posting the patch now since I'm not sure that I've found all places that
need to be fixed.

2007-05-06  Rask Ingemann Lambertsen  <rask@sygehus.dk>

	* reload1.c (break_reload_inheritance): New function.
	(elimination_effects): Use it when an elimination target
	changes to mark reloads from this register as invalid
	for inheritance.

Index: reload1.c
===================================================================
--- reload1.c	(revision 124334)
+++ reload1.c	(working copy)
@@ -2709,6 +2722,20 @@ eliminate_regs (rtx x, enum machine_mode
   return eliminate_regs_1 (x, mem_mode, insn, false);
 }
 
+/* Disable inheritance of past reloads from hard reg REG.  Helper function
+   for elimination_effects().  */
+static void
+break_reload_inheritance (unsigned int reg)
+{
+  unsigned int r;
+
+  for (r = 0; r < FIRST_PSEUDO_REGISTER; r++)
+    {
+      if (reg_reloaded_contents[r] == reg)
+	CLEAR_HARD_REG_BIT (reg_reloaded_valid, r);
+    }
+}
+
 /* Scan rtx X for modifications of elimination target registers.  Update
    the table of eliminables to reflect the changed state.  MEM_MODE is
    the mode of an enclosing MEM rtx, or VOIDmode if not within a MEM.  */
@@ -2798,6 +2825,8 @@ elimination_effects (rtx x, enum machine
 		else
 		  ep->can_eliminate = 0;
 	      }
+	    /* The offset changed, past reloads can't be inherited.  */
+	    break_reload_inheritance (ep->to);
 	  }
 
       /* These two aren't unary operators.  */
@@ -2882,7 +2911,11 @@ elimination_effects (rtx x, enum machine
 		if (GET_CODE (src) == PLUS
 		    && XEXP (src, 0) == SET_DEST (x)
 		    && GET_CODE (XEXP (src, 1)) == CONST_INT)
-		  ep->offset -= INTVAL (XEXP (src, 1));
+                  {
+		    ep->offset -= INTVAL (XEXP (src, 1));
+		    /* The offset changed, past reloads can't be inherited.  */
+		    break_reload_inheritance (ep->to);
+		  }
 		else
 		  ep->can_eliminate = 0;
 	      }

-- 
Rask Ingemann Lambertsen