Machine-independent bug in cse, with analysis.

[Geoffrey KEATING <geoffk@discus.anu.edu.au>]

Jeff said:
> Given time and appropriate incentive I could find bugs in every
> optimization pass in the compiler.

Here's one in CSE :-).  It's the last egcs bug that causes the glibc
test cases to fail on PowerPC.  It may be a known bug.

The following program, when compiled under (at least) egcs 1.0.2
configured for powerpc-unknown-linux-gnu, and under gcc 2.8.1
configured for sparc-sun-solaris2.6, with either gcc -O2 or
gcc -O1 -frerun-cse-after-loop, fails with exit code 1.  It should
(and does under plain -O1) succeed.  I would expect it appears under
all configurations, and I seem to remember it being in 2.7.2.1.

static int f(int) __attribute__((const));
int main()
{
   int f1, f2, x;
   x = 1; f1 = f(x);
   x = 2; f2 = f(x);
   return f1 == f2 ? 1 : 0;
}
static int f(int x) { return x; }

Any const definition for f will do.

What happens is that the RTL initially looks like this (#comments are mine):

...
# x = 1
(insn 9 6 11 (set (reg/v:SI 107)
        (const_int 1)) -1 (nil)
    (nil))

# setup argument for f(x); from the REG_LIBCALL note to the REG_RETVAL
# note is treated specially by CSE.
(insn 11 9 13 (set (reg:SI 8 %o0)
        (reg/v:SI 107)) -1 (nil)
    (insn_list:REG_LIBCALL 15 (nil)))
...
# this is what CSE uses for t1.
(insn 15 13 17 (set (reg:SI 108)
        (reg:SI 8 %o0)) -1 (nil)
    (insn_list:REG_RETVAL 11 (expr_list:REG_EQUAL (expr_list (symbol_ref:SI ("f"
))
                (expr_list (reg/v:SI 107)
                    (nil)))
            (nil))))
...
# x = 2
(insn 20 17 22 (set (reg/v:SI 107)
        (const_int 2)) -1 (nil)
    (nil))
# setup argument for f(x)
(insn 22 20 24 (set (reg:SI 8 %o0)
        (reg/v:SI 107)) -1 (nil)
    (insn_list:REG_LIBCALL 26 (nil)))

...
# this is what CSE uses for t2.
(insn 26 24 28 (set (reg:SI 109)
        (reg:SI 8 %o0)) -1 (nil)
    (insn_list:REG_RETVAL 22 (expr_list:REG_EQUAL (expr_list (symbol_ref:SI ("f"
))
                (expr_list (reg/v:SI 107)
                    (nil)))
            (nil))))


Now, the first pass of CSE replaces register 107, 'x', with the
appropriate constants (1 or 2, respectively), and deletes the now-dead
instructions that set it (insns 9 and 20).  But it does not change
insns 15 or 26.  This is fine in a single CSE run, because the
REG_RETVAL note does not correspond to actual code output; but when
CSE is run a second time, now it looks like register 107 is not
changed between the two function invocations, so the two calls of f()
produce the same result.  I think the RETVAL notes are also used by
loop.c, so there's probably a way to show this bug there too.

So, how to fix?

1. In CSE passes, delete REG_RETVAL notes if they might be wrong
   (which is possibly always).  This prevents some important loop
   optimisations, so it's really not very nice.
or
2. Maintain REG_RETVAL notes in CSE.  This might be difficult, it's
   not immediately obvious which part of the note corresponds to which
   part of the actual code generated.  I don't think you can just
   let CSE work on the notes, because the results of CSE on the inputs
   might depend on where (stack/memory/registers) they're being
   stored.
or
3. Don't let pre-loop CSE work on inputs of LIBCALLs.  This might not
   hurt performance very much...

Any other suggestions?

--
Geoff Keating <Geoff.Keating@anu.edu.au>