Paolo Bonzini - [PATCH] PR/17860: wrong code generated by loop optimizer up to 3.4 (original) (raw)

This is the mail archive of the gcc-patches@gcc.gnu.orgmailing list for the GCC project.

• From: Paolo Bonzini
• To: GCC Patches
• Date: Thu, 07 Oct 2004 12:04:19 +0200
• Subject: [PATCH] PR/17860: wrong code generated by loop optimizer up to 3.4

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;

Instead of ending after a single iteration, 2^32 iterations are performed and in the end i == 0 instead of 1. The assembly language output on i686-pc-linux-gnu is quite clear:

.L9:
    dec %eax
    jne .L9

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. The reason is that, after CSE1, the following RTL is produced for the loop:

(insn 61 14 15 0 0x401572ec (set (reg:CCGC 17 flags)
        (compare:CCGC (reg/v:SI 61)
            (const_int 2 [0x2]))) 2 {*cmpsi_1_insn} (nil)
    (nil))
;; End of basic block 0, registers live:
 (nil)

(note 15 61 29 NOTE_INSN_LOOP_BEG)

;; Start of basic block 1, registers live: (nil)
(code_label 29 15 52 1 6 "" [1 uses])

(note 52 29 26 1 [bb 1] NOTE_INSN_BASIC_BLOCK) (note 26 52 28 1 NOTE_INSN_LOOP_CONT)

(insn 28 26 67 1 0x401572ec (parallel [
            (set (reg/v:SI 61)
                (plus:SI (reg/v:SI 61)
                    (const_int 1 [0x1])))
            (clobber (reg:CC 17 flags))
        ]) 146 {*addsi_1} (nil)
    (nil))

(note 67 28 17 1 NOTE_INSN_LOOP_VTOP)

(insn 17 67 18 1 0x401572ec (set (reg:CCGC 17 flags)
        (compare:CCGC (reg/v:SI 61)
            (const_int 0 [0x0]))) 2 {*cmpsi_1_insn} (nil)
    (nil))


(jump_insn 18 17 34 1 0x401572ec (set (pc)
        (if_then_else (lt (reg:CCGC 17 flags)
                (const_int 0 [0x0]))
            (label_ref 29)
            (pc))) 356 {*jcc_1} (nil)
    (nil))
;; End of basic block 1, registers live:
 (nil)

(note 34 18 57 NOTE_INSN_LOOP_END)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).This fix can fix test cases like this, all of which fail on GCC 3.3.1 (the one I had lying around):

Test case 1: int main() { int i, foo = 2; for (i = 0; i < foo; i++) foo = 0;

  if (i != 1)
    abort ();
}

Test case 2: int foo = 2;

int main()
{
  int i;
  for (i = 0; i < foo; i++)
    foo = 0;


  if (i != 1)
    abort ();
}

Test case 3: extern void abort ();

int main()
{
  int i = 0, foo = 2;
  while (i < foo)
    foo = 0, i++;


  if (i != 1)
    abort ();
}

but it *is* brittle because, especially with -fno-cse-skip-blocks or -fno-cse-follow-jumps, CSE might fail to constant-propagate, and GCSE will do it without taking VTOP notes in consideration. An example test case is:

int bar;

void
baz (void)
{
  bar = !bar;
}


int main()
{
  int i, foo = 2;
  for (i = 0; i < foo; i++)
    {
      foo = 0;
      if (bar)
        baz ();
    }


  if (i != 1)
    abort ();
}

With CSE block skipping enabled, the VTOP note is processed correctly; with -fno-cse-skip-blocks, instead, GCSE's constant-propagation triggers the bug.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.

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. If somebody can run SPEC and has a few spare cycles, I'll be grateful. The VTOP note is emitted in jump.c (duplicate_loop_exit_test) and removing it is a one-liner for the purposes of SPEC.

I bootstrapped/regtested this patch on i686-pc-linux-gnu, starting from 3.3.1; ok for 3.4/3.3 if it bootstraps/regtests on the CVS branches?

Paolo

2004-10-06 Paolo Bonzini bonzini@gnu.org

PR rtl-optimization/17860
* loop.c (check_dbra_loop): Do not try to use an end condition
like "i != 0" in the reversed loop.

--- loop.c.save 2004-10-06 23:22:39.000000000 +0200 +++ loop.c 2004-10-06 23:26:23.000000000 +0200 @@ -8391,17 +8391,6 @@ /* First check if we can do a vanilla loop reversal. / if (initial_value == const0_rtx - / If we have a decrement_and_branch_on_count, - prefer the NE test, since this will allow that - instruction to be generated. Note that we must - use a vanilla loop reversal if the biv is used to - calculate a giv or has a non-counting use. / -#if ! defined (HAVE_decrement_and_branch_until_zero)
-&& defined (HAVE_decrement_and_branch_on_count) - && (! (add_val == 1 && loop->vtop - && (bl->biv_count == 0 - || no_use_except_counting))) -#endif && GET_CODE (comparison_value) == CONST_INT / Now do postponed overflow checks on COMPARISON_VAL. */ && ! (((comparison_val - add_val) ^ INTVAL (comparison_value)) @@ -8413,13 +8402,6 @@ nonneg = 1; cmp_code = GE; } - else if (add_val == 1 && loop->vtop - && (bl->biv_count == 0 - || no_use_except_counting)) - { - add_adjust = 0; - cmp_code = NE; - } else return 0;