PR rtl-optimization/22167: Fix gcse hoisting bug

[Richard Sandiford]

This patch fixes PR rtl-optimization/22167, which was caused by a
typo in gcse.c:hoist_code().  As I understand it, the algorithm is
roughly this:

  for each block BB
    for each expr E
      HOISTABLE := 0
A:    if (E is very busy at the end of BB
          && E is transparent at the end of BB)
        for each block BB' that is immediately dominated by BB
          if (BB' uses E
              && a computation of E at the end of BB would reach that use)
            HOISTABLE := HOISTABLE + 1
      HOIST_EXPRS[E] := HOISTABLE > 1
    if there exists an E such that HOIST_EXPRS[E] > 0
      for each expr E
B:      if HOIST_EXPRS[E]
	  for each block BB' that is immediately dominated by BB
	    if (BB' uses E
	        && a computation of E at the end of BB would reach that use)
	      replace the use with the reaching reg

The hoist_code() typo is in condition B.  It's checking the bitmap
hoist_vbeout instead of hoist_exprs.  This means that the code is
effectively doing:

B:      if E is very busy at the end of BB

Thus hoist_code() will do nothing when there are no candidate
expressions with two or more suitable uses.  However, if there _is_
such an expression, hoist_code() will hoist all candidate expressions,
even if they have only one use.  And it will effectively drop the
all-important "E is transparent at the end of BB" condition when
doing this.

The problem can be seen in the attached testcase.  The call to foo()
has two successors, one normal and one abnormal.  And both of these
successors use &a[0] and s.x.

Because the call to foo() can throw, any hoisted code must be
inserted _before_ the call.  This is OK for &a[0] but not for s.x,
since the call to foo() could modify s.x.  Thus &a[0] is transparent
at the end of the call's block but s.x isn't.

The first loop in hoist_code() decides to hoist &a[0], and the bug
then causes the second loop to hoist s.x too.  Thus the code after
the call will use a value of s.x that was loaded before the call.

Patch tested on mips64-elf, both on mainline and 3.4 branch.
OK to install?

The testcase I've used here is reduced from the one in the
original PR.  It fails on 3.4 and mainline before the patch,
but because it's so direct, there's a chance that it could fail
for all versions of gcc since the hoisting code was introduced.

The original testcase was different.  It fails for 3.4 but works
in 3.2, 4.0 and 4.1.  It's therefore a 3.4 regression.

Andrew Pinski also reports that the reduced testcase fails on
4.0 for powerpc (thanks Andrew).  I haven't yet checked MIPS.

If the patch is OK for mainline, is it OK for the two release
branches too, assuming suitable testing in the 4.0 case?

Richard


	* gcse.c (hoist_code): Fix hoist_exprs[] check.

testsuite/
	* g++.dg/opt/pr22167.C: New test.

Index: gcc/gcse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/gcse.c,v
retrieving revision 1.288.2.9
diff -u -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.288.2.9 gcse.c
--- gcc/gcse.c	30 Oct 2004 18:02:53 -0000	1.288.2.9
+++ gcc/gcse.c	14 Jul 2005 16:36:31 -0000
@@ -6445,7 +6445,7 @@ hoist_code (void)
 	  insn_inserted_p = 0;
 
 	  /* These tests should be the same as the tests above.  */
-	  if (TEST_BIT (hoist_vbeout[bb->index], i))
+	  if (TEST_BIT (hoist_exprs[bb->index], i))
 	    {
 	      /* We've found a potentially hoistable expression, now
 		 we look at every block BB dominates to see if it
diff -u /dev/null gcc/testsuite/g++.dg/opt/pr22167.C
--- /dev/null	2005-06-16 22:49:09.000000000 +0100
+++ gcc/testsuite/g++.dg/opt/pr22167.C	2005-07-14 17:32:39.000000000 +0100
@@ -0,0 +1,32 @@
+// Derived from PR22167, which failed on some RISC targets.  The call to
+// foo() has two successors, one normal and one exceptional, and both
+// successors use &a[0] and x.  Expressions involving &a[0] can be hoisted
+// before the call but those involving x cannot.
+// { dg-options "-Os" }
+// { dg-do run }
+
+int a[4];
+
+struct S {
+  S() : x (0) {}
+  ~S() { a[0] = x; }
+  int x;
+};
+
+void
+foo (int *x)
+{
+  if (*x == 1)
+    throw 1;
+  *x = 1;
+}
+
+int
+main()
+{
+  S s;
+  foo (&s.x);
+  if (a[0] == s.x)
+    a[0]++;
+  return a[0];
+}