Machine-independent bug in cse, with analysis.

Machine-independent bug in cse, with analysis.

[Geoffrey KEATING]

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>

Re: Machine-independent bug in cse, with analysis.

[Jeffrey A Law]

  In message <199804180333.NAA04430@discus.anu.edu.au>you write:
  > 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.
Just a minor note for the future, when writing testcases that can
be executed, the standard is for the test to call abort () if something
goes wrong and exit (0) if everything is OK.

Writing tests in that form makes it easier for us to drop them into
the testsuite :-)

I've tweaked yours appropriately and added it to the testsuite.

[ ... ]
  > 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).
Right.

  > But it does not change insns 15 or 26.
Right.  For those without context, insns 15 and 26 have the REG_RETVAL
notes for the constant call.

  > 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.
Right.  It also means we can't eliminate libcalls which produce a
known value (ie a call to a compiler intrinsic like adddi3 when cse
can find constant values for both input operands).

  > 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.
I think this is the best approach.

All insns relating to the libcall will be in a libcall block; this
should include argument setup.

It's not too difficult to map from an insn in a libcall block to the
insn for the libcall block with the REG_RETVAL note.

Anytime we replace a register in a libcall block we'd need to go to
the insn with the RETVAL note and replace it there too.

Want to take a stab at it?


  > or
  > 3. Don't let pre-loop CSE work on inputs of LIBCALLs.  This might not
  >    hurt performance very much...
This would be another option, but #2 is only a small incremental
improvement from #3 unless I'm misunderstanding something.

Jeff

Re: Machine-independent bug in cse, with analysis.

[Jeffrey A Law]

  In message <199804180333.NAA04430@discus.anu.edu.au>you write:
  > 
  > 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.
This has been fixed :-)

jeff