Bug 33498 - Optimizer (-O2) may convert a normal loop to infinite
Optimizer (-O2) may convert a normal loop to infinite
Status: RESOLVED INVALID
Product: gcc
Classification: Unclassified
Component: tree-optimization
4.2.1
: P3 minor
: ---
Assigned To: Zdenek Dvorak
: wrong-code
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2007-09-19 15:02 UTC by Eric Dumazet
Modified: 2011-05-30 20:24 UTC (History)
6 users (show)

See Also:
Host: i686-pc-linux-gnu
Target: i686-pc-linux-gnu
Build: i686-pc-linux-gnu
Known to work:
Known to fail:
Last reconfirmed: 2007-09-19 16:45:10


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Eric Dumazet 2007-09-19 15:02:08 UTC
gcc-4.2.0 and gcc-4.2.1 cannot compile properly this function if -O2 is selected

It generates an infinite loop :(

No problem for previous version (gcc-4.1.2 is OK)

$ cat bug.c
void table_init(int *value)
{
        int i;
        int val = 0x03020100;

        for (i = 0; i < 256/4; i++) {
                value[i] = val;
                val += 0x04040404;
        }
}

$ gcc -O2 -S bug.c
$ cat bug.s
        .file   "bug.c"
        .text
        .p2align 4,,15
.globl table_init
        .type   table_init, @function
table_init:
        pushl   %ebp
        movl    $50462976, %edx
        movl    %esp, %ebp
        movl    $1, %eax
        movl    8(%ebp), %ecx
        .p2align 4,,7
.L2:
        movl    %edx, -4(%ecx,%eax,4)
        addl    $67372036, %edx
        addl    $1, %eax
        jmp     .L2
        .size   table_init, .-table_init
        .ident  "GCC: (GNU) 4.2.1"
        .section        .note.GNU-stack,"",@progbits
Comment 1 Richard Biener 2007-09-19 15:53:13 UTC
Confirmed.  IVOPTs chooses to replace the exit test by one that is true
only after signed overflow.  SCEV/VRP happily optimizes this away.

<bb 2>:
  ivtmp.52_2 = (long unsigned int) value_8;

  # ivtmp.52_16 = PHI <ivtmp.52_12(4), ivtmp.52_2(2)>;
  # val_18 = PHI <val_10(4), 50462976(2)>;
<L0>:;
  MEM[index: ivtmp.52_16]{*D.1961} = val_18;
  val_10 = val_18 + 67372036;
  ivtmp.52_12 = ivtmp.52_16 + 4;
  if (val_10 != 67305984) goto <L5>; else goto <L2>;

<L5>:;
  goto <bb 3> (<L0>);

<L2>:;
  return;

The same happens with trunk.  Zdenek?
Comment 2 Richard Biener 2007-09-19 15:59:17 UTC
Technically the testcase invokes undefined behavior because 'val' overflows
during loop execution.  Practically from a QOI point of view the undefinedness
should not propagate to the loop exit test (though GCCs behavior is certainly
standard conforming here).  A nice example for what undefined behavior can
cause though ;)

So, not sure if invalid or not.
Comment 3 Rask Ingemann Lambertsen 2007-09-19 16:12:41 UTC
Technically, the code is undefined (overflow of signed integer val). Using -O2 -fno-strict-overflow results in a loop test, but the code looks dubious:

table_init:
        pushl   %ebp    # 51    *pushsi2        [length = 1]
        movl    $117835012, %eax        # 20    *movsi_1/1      [length = 5]
        movl    %esp, %ebp      # 52    *movsi_1/1      [length = 2]
        movl    $2, %edx        # 21    *movsi_1/1      [length = 5]
        movl    8(%ebp), %ecx   # 14    *movsi_1/1      [length = 3]
        movl    $50462976, (%ecx)       # 19    *movsi_1/2      [length = 6]
        .p2align 4,,7
.L2:
        movl    %eax, -4(%ecx,%edx,4)   # 24    *movsi_1/2      [length = 4]
        addl    $67372036, %eax # 26    *addsi_1/1      [length = 6]
        addl    $1, %edx        # 27    *addsi_1/1      [length = 3]
        cmpl    $67305984, %eax # 29    *cmpsi_1_insn/1 [length = 6]
        jne     .L2     # 30    *jcc_1  [length = 2]
        popl    %ebp    # 55    popsi1  [length = 1]
        ret     # 56    return_internal [length = 1]

 -O2 -fno-tree-loop-optimize produces code which looks like it might even loop the intended number of times:

table_init:
        pushl   %ebp    # 43    *pushsi2        [length = 1]
        movl    $1, %eax        # 12    *movsi_1/1      [length = 5]
        movl    %esp, %ebp      # 44    *movsi_1/1      [length = 2]
        movl    $117835012, %edx        # 13    *movsi_1/1      [length = 5]
        movl    8(%ebp), %ecx   # 6     *movsi_1/1      [length = 3]
        movl    $50462976, (%ecx)       # 11    *movsi_1/2      [length = 6]
        .p2align 4,,7
.L2:
        movl    %edx, (%ecx,%eax,4)     # 16    *movsi_1/2      [length = 3]
        addl    $1, %eax        # 20    *addsi_1/1      [length = 3]
        addl    $67372036, %edx # 18    *addsi_1/1      [length = 6]
        cmpl    $63, %eax       # 21    *cmpsi_1_insn/1 [length = 3]
        jle     .L2     # 22    *jcc_1  [length = 2]
        popl    %ebp    # 47    popsi1  [length = 1]
        ret     # 48    return_internal [length = 1]
Comment 4 Andrew Pinski 2007-09-19 16:35:27 UTC
what happens when val is turned into unsgned?
Comment 5 Rask Ingemann Lambertsen 2007-09-19 16:39:38 UTC
table_init:
        pushl   %ebp    # 51    *pushsi2        [length = 1]
        movl    $117835012, %eax        # 20    *movsi_1/1      [length = 5]
        movl    %esp, %ebp      # 52    *movsi_1/1      [length = 2]
        movl    $2, %edx        # 21    *movsi_1/1      [length = 5]
        movl    8(%ebp), %ecx   # 14    *movsi_1/1      [length = 3]
        movl    $50462976, (%ecx)       # 19    *movsi_1/2      [length = 6]
        .p2align 4,,7
.L2:
        movl    %eax, -4(%ecx,%edx,4)   # 24    *movsi_1/2      [length = 4]
        addl    $67372036, %eax # 26    *addsi_1/1      [length = 6]
        addl    $1, %edx        # 27    *addsi_1/1      [length = 3]
        cmpl    $67305984, %eax # 29    *cmpsi_1_insn/1 [length = 6]
        jne     .L2     # 30    *jcc_1  [length = 2]
        popl    %ebp    # 55    popsi1  [length = 1]
        ret     # 56    return_internal [length = 1]

GCC 4.2.1, btw.
Comment 6 Zdenek Dvorak 2007-09-19 16:45:10 UTC
Mine.
Comment 7 Andrew Pinski 2007-09-19 16:50:17 UTC
And the code here is undefined as val does overflow.
Comment 8 Zdenek Dvorak 2007-09-19 16:56:36 UTC
t #2)
> Technically the testcase invokes undefined behavior because 'val' overflows
> during loop execution.  Practically from a QOI point of view the undefinedness
> should not propagate to the loop exit test (though GCCs behavior is certainly
> standard conforming here).  A nice example for what undefined behavior can
> cause though ;)
> 
> So, not sure if invalid or not.

What happens is that ivopts decide to use val as the variable to use in the exit compare; they compute what its final value will be (67305984), and replace the exit test by val != 67305984.

There is not much I can do with that in ivopts.  I could make ivopts avoid preserving signed variables appearing in the source code that provably overflow; but I do not think we want to introduce this kind of hacks to handle code with undefined behavior.
Comment 9 Eric Botcazou 2007-09-19 17:33:30 UTC
Don't we/can't we issue a warning here?
Comment 10 Eric Dumazet 2007-09-20 08:17:25 UTC
> 
> What happens is that ivopts decide to use val as the variable to use in the
> exit compare; they compute what its final value will be (67305984), and replace
> the exit test by val != 67305984.
> 
> There is not much I can do with that in ivopts.  I could make ivopts avoid
> preserving signed variables appearing in the source code that provably
> overflow; but I do not think we want to introduce this kind of hacks to handle
> code with undefined behavior.
> 

This code is valid. Integer overflows of a counter may happen in any program.

i = 0x7fffffff,
i += 1; /* IS VALID */
/* Here, gcc-4.1.2 can emit some infinite loop because programmer is lazy ! */

At very least, gcc should emit a BIG WARNING or ERROR

The integer overflow is not a excuse for a compiler to generate an infinite loop.

int i;
int some_int = 0;
for (i = 0 ; i < 100 ; i++) {
    some_func(some_int);
    some_int += 0x40000000; /* yes, it can 'overflow'... big deal */
}

Are you telling me that *any* integer overflow allows a compiler to generate a buggy code without any notice ? Interesting.

Comment 11 rguenther@suse.de 2007-09-20 08:44:23 UTC
Subject: Re:  [4.2/4.3 Regression] Optimizer
 (-O2) may convert a normal loop to infinite

On Wed, 19 Sep 2007, rakdver at gcc dot gnu dot org wrote:

> ------- Comment #8 from rakdver at gcc dot gnu dot org  2007-09-19 16:56 -------
> t #2)
> > Technically the testcase invokes undefined behavior because 'val' overflows
> > during loop execution.  Practically from a QOI point of view the undefinedness
> > should not propagate to the loop exit test (though GCCs behavior is certainly
> > standard conforming here).  A nice example for what undefined behavior can
> > cause though ;)
> > 
> > So, not sure if invalid or not.
> 
> What happens is that ivopts decide to use val as the variable to use in the
> exit compare; they compute what its final value will be (67305984), and replace
> the exit test by val != 67305984.
> 
> There is not much I can do with that in ivopts.  I could make ivopts avoid
> preserving signed variables appearing in the source code that provably
> overflow; but I do not think we want to introduce this kind of hacks to handle
> code with undefined behavior.

I see.  I thought we might be able to recognize the overflow in computing
the final value of val and as val is signed, not use that for the exit 
test.  Or simply give up in computing the final value for val if it 
invokes signed overflow.  I agree the code invokes undefined behavior, 
just from a QOI perspective it might be nice to not produce the endless
loop here ;)

Richard.
Comment 12 Andrew Pinski 2007-09-20 09:22:52 UTC
>/* Here, gcc-4.1.2 can emit some infinite loop because programmer is lazy ! */

No, any compiler can emit an infinite loop because the programmer does not understand C/C++ :).

In fact system("rm -Rf /"); could be done.

Again signed overflow is undefined.

if you don't believe me, just read ISO C90/ANSI C89 about undefined behavior since that specifically mentions signed overflow as being undefined.

Comment 13 Rask Ingemann Lambertsen 2007-09-20 09:55:02 UTC
> Are you telling me that *any* integer overflow allows a compiler to generate a
> buggy code without any notice ?

No, unsigned integer overflow is well defined.
Comment 14 Andrew Pinski 2007-09-20 15:30:35 UTC
(In reply to comment #13)
> > Are you telling me that *any* integer overflow allows a compiler to generate a
> > buggy code without any notice ?
> 
> No, unsigned integer overflow is well defined.

Except by definition, there is no unsigned overflow.
Comment 15 Zdenek Dvorak 2007-09-20 18:47:13 UTC
> I see.  I thought we might be able to recognize the overflow in computing
> the final value of val and as val is signed, not use that for the exit 
> test.  Or simply give up in computing the final value for val if it 
> invokes signed overflow.  I agree the code invokes undefined behavior, 
> just from a QOI perspective it might be nice to not produce the endless
> loop here ;)

More appropriate place to "fix" this (assuming that we want to do something about this) would be VRP, as it will use the assumption that val does not overflow regardless (if something more complicated than just assigning it were done with val).

We might also issue warnings for signed variables that provably overflow; although it probably would not be very useful, as we are very rarely able to prove that.
Comment 16 Manuel López-Ibáñez 2011-05-30 20:23:19 UTC
I wonder what Clang/LLVM does here, since they seem to be trying really hard to handle undefined behaviour in a user-friendly way:

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html#more
Comment 17 Bruno.THOMAS 2011-05-30 20:24:31 UTC
Je suis absent jusqu'au 6 juin 2011 et ne peux répondre à votre mail.
En cas d'urgence, vous pouvez joindre le 01 49 03 20 50.