RE: [PATCH] PR/17860: wrong code generated by loop optimizer up to 3.4

["Dave Korn" <dave dot korn at artimi dot com>]

> -----Original Message-----
> From: Paolo Bonzini
> Sent: 07 October 2004 11:04

[ main gcc list added because I'm not subbed to -patches and it's all a
bit theoretical and not directly about the patch in question. ]

    Hi Paolo,

> This patch fixes PR rtl-optimization/17860, a miscompilation of a loop

> whose bound is changed in the middle of the loop.  An example is

> 	int i, foo = 2;
> 	for (i = 0; i < foo; i++)
> 	  foo = 0;

> The optimizer fails not recognize that FOO is changed in the middle of

> the loop, and decides to transform the loop into something like
> 
> 	for (i = 0; --i != 0; )
> 	  foo = 0;
> 
> foo = 0 is then eliminated as dead.

  This is a very nasty bug indeed.  A testcase like this might seem a
bit artificial, but can we be confident that gcc might not miscompile
(under the right combination of cirumstances) something altogether more
common such as ...

    for (i = 0, done = 0;  i < loop_count && !done; i++)
        done = some_function ();

...? 


> The NOTE_INSN_LOOP_VTOP note is bogus, because the test is not a 
> duplicate of the loop-entry test: we have
> 
> 	(compare:CCGC (reg/v:SI 61) (const_int 2)),
> 
> at the loop top, vs.
> 
> 	(compare:CCGC (reg/v:SI 61) (const_int 0)).
> 
> following the note.  So, at least the bug is not latent on mainline 
> because such notes have been killed last August there.

> I tried a fix in CSE, examining the insns following a 
> NOTE_INSN_LOOP_VTOP, up to a JUMP_INSN or NOTE_INSN_LOOP_END. 
>  If two or 
> more REGs/MEMs mentioned in those insns have been changed in 
> this basic 
> block, we assume the note is now bogus.  The threshold was 
> two because 
> one is likely an induction variable (and if it weren't, loop 
> optimization would not do the erroneous transformation).

  A couple of things occur to me:

1)  Would it perhaps be possible to check the comparison at the VTOP
against the one at the LOOP_BEG and decide that the note was bogus if
they don't match?  Would this not be a valid diagnostic, or would it be
valid but difficult to implement?  (I found some thread in the list
archive discussing loop optimiser problems a while ago which suggested
this might be quite hard).

2)  Does it actually matter directly that the VTOPs don't match?  AFAICS
the test (set (reg:CCGC 17 flags) ...) at the LOOP_BEG (insn 61) is
dead, isn't it, since there's nothing in straight-line between it and
the clobber (reg:CC 17 flags) at insn 28.  The code in the dbra
optimisation that you've patched out doesn't check for anything else
except the existence of a vtop; if the two tests still matched, would it
still be wrong?

3)  Can't we teach the loop optimiser to know if any of the variables in
the loop condition might be changed during the loop body and tell it not
to optimise in that case?

> I'm quite at a loss as to what the correct fix is: on one 
> hand, teaching 
> CSE and GCSE about such notes is brittle, and pointless as the notes 
> themselves are nowadays.  On the other hand, removing the one use of 
> VTOP notes that causes the miscompilation (present since August 26, 
> 1998, CVS revision 1.67) is just papering over the problem 
> because the 
> bogus VTOP note remains.
> 
> VTOP notes are used so little that I'm tempted to kill VTOP notes 
> entirely on the branches too... for now, my fix for the bug is what I 
> just rejected: kill the one use in check_dbra_loop, where GCC 
> tries to 
> use an end condition like "i != 0" in the reversed loop, if 
> it could not 
> use the end condition "i >= 0".  At least, this fixes all the above 
> testcases.

  But the invalid note remains in the generated rtl, yes?  And so it
might perhaps - but in these testcases doesn't - cause a problem in one
of these four later places you list ?
 
> The other uses are:
> - in two places in loop.c, detecting insns that are outside of a
>    LOOP_BEG/LOOP_END pair, and are always executed;
> - in doloop.c, doing some special checks on do-while loops that are
>    exited immediately in order to hardcode the doloop counter to 1.
>    doloop.c would not produce wrong code without the note: the counter
>    would be hardcoded for all loops that roll once;
> - in unroll.c, to compute the number of iterations of loops like
>    like "for (i = init; i < init + const; i++)", when running the
>    loop optimizer twice;
> - in unroll.c, to determine the number of iterations of a loop like
>    "for (i = reg + const1; i < reg + const2; i++)".
> 
> The only interesting case in practice seems to be the last 
> one, but even that one should not be terribly frequent.  

  I'm not familiar with the loop optimisers, so forgive me if some of my
questions seem dumb, but I'm curious about the implications of these
uses.  Are you fairly confident that simply removing the code that emits
the VTOP notes will just cause a few optimisation opportunities to be
lost but is unlikely to lead to misbehaviour in these places?  I have to
maintain a production compiler, and I'd rather have a solution that was
more guaranteed correct at the cost of some pessimisation, than as you
suggested one which 'papers over the crack' but does not fix the
underlying problem in the codegen and therefore may resurface further
down the line.

  And those last two cases that you mention in unroll.c, if we're just
trying to find the loop iteration count, wouldn't it be possible to
determine the information from the LOOP_BEG instead of the VTOP?  They
both seem like they ought to be quite simple cases to recognize,
shouldn't they?


    cheers, 
      DaveK
-- 
Can't think of a witty .sigline today....