Re: Fix twolf -funroll-loops -O3 miscompilation (a semi-latent web.c bug)

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

On Mon, Nov 19, 2012 at 11:47 PM, Steven Bosscher wrote:
> On Mon, Nov 19, 2012 at 11:42 PM, Eric Botcazou wrote:
>>> That could be done, yes. Cleaning up the REG_EQ* notes requires
>>> liveness at the insn level, so it'd require a bigger re-organization
>>> of the code. Perhaps adding a new pass (conditional on DF_EQ_NOTES)
>>> over all insn in df_lr_finalize, tracking liveness and calling
>>> df_remove_dead_eq_notes on each insn.
>>>
>>> But most passes that use the REG_EQ* notes don't set the DF_EQ_NOTES flag.
>>
>> Right.  After the DF merge, the de-facto consensus was that individual passes
>> were still responsible for cleaning up the REG_EQ* notes when they change the
>> code, whereas the REG_DEAD/REG_UNUSED notes are entirely handled by DF.  As
>> such, the bug here is in the unroller, not in the webizer.
>
> Then it's in -fsplit-ivs-in-unroller. Looking into it.

This bug is giving me head-aches, but I think I finally understand
what is going wrong here.

Compiling the C test case with --param max-unroll-times=2, you get the
attached dumps. The loop that is unrolled to wrong-code is
bb10->bb7->bb8->bb9->bb10 in the loop2_unswitch dump (the last dump
before unrolling). The IV that is being split is in r132. In basic
block 9 of the loop2_unswitch dump there is the IV increment in insn
78:

   78 r132:SI=r132:SI+0x4

In the loop2_unroll dump the loop is
bb10->bb7->bb8->bb9->bb23->bb24->bb25->bb26->bb10. The loop is
unrolled by copying the body once, and the IV increment is expanded
into r165 at the end of basic block 9 in the loop2_unroll dump. This
makes r132 die after insn 181. The incremented IV is copied back into
r132 in insn 78, but there are no no-EQ_USES of this DEF so r132 is
still dead after insn 78. The IV increment of the unrolled loop
happens in insn 175 in basic block 25, which makes r132 live again:

  181 r165:SI=r132:SI+0x4
   78 r132:SI=r165:SI
...
  175 r132:SI=r165:SI+0x4

The insn with the REG_EQUAL note using r132 is insn 172 in the copied body:

  172 r131:SF=r158:SF
      REG_EQUAL: [r132:SI]
      REG_DEAD: r158:SF

With the (assumed agreed) semantics of REG_EQ* notes being invalid if
they use a register that isn't live in the insn with the note, this
REG_EQUAL note is invalid because r132 is dead after insn 78.

The note would be valid if loop2_unroll would copy-prop out r132 for
r165, or if it would remove the note in the copied body. I'd like to
do the former but DEF-USE chains aren't available at this point. We
could run CPROP before web (instead of web before CPROP like we do
now) which would make the REG_EQUAL note valid again, but that'd be
papering over the problem that loop2_unroll leaves this bad note.
Removing the note is easier but it may hurt optimization later on:
CSE2 puts the note back in but this introduces a pass ordering
dependency. Perhaps that's not a big problem, but I'm not sure...

Anyway, just so you know I haven't forgotten about this one yet :-)

Ciao!
Steven

Attachment: PR55006.c.179r.loop2_unswitch.svg
Description: image/svg

Attachment: PR55006.c.180r.loop2_unroll.svg
Description: image/svg

Attachment: PR55006.c.182r.loop2_done.svg
Description: image/svg