Bug 33498

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?

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.

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]

what happens when val is turned into unsgned?

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.

Mine.

And the code here is undefined as val does overflow.

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.

Don't we/can't we issue a warning here?

> 
> 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.

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.

>/* 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.

> 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.

(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.

> 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.

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

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.