Re: GCC optimization bug?

[Mason <slash dot tmp at free dot fr>]

On 17/01/2017 11:49, Mason wrote:

> On 17/01/2017 11:15, anubhav wrote:
> 
>> The following code prints different results when run with different 
>> optimization levels (O0 vs O2).
>>
>> int main() {
>>          int i = INT_MAX - 5;
>>          int j = 0;
>>          for (; i <= INT_MAX - 2; i += 3) {
>>                  if (i <= 1) {
>>                          j = 1;
>>                  }
>>          }
>>          printf("%d",j);
>>          return 0;
>> }
>>
>> Commands used :
>>   gcc -O0 -fno-strict-overflow bug.c -o bug        # Output is 1
>>   gcc -O2 -fno-strict-overflow bug.c -o bug        # Output is 0
>>
>> GCC version :
>> gcc version 6.2.0 20160901 (Ubuntu 6.2.0-3ubuntu11~16.04)
>>
>> The expected output is 1 since the value of i overflows once. Is this 
>> an optimization bug?
> 
> Interesting.
> 
> To be clear, in standard C, signed integer overflow has undefined behavior.
> So we are actually considering the *extension* requested with -fno-strict-overflow.
> 
> https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#index-fstrict-overflow-935
> 
>> -fstrict-overflow
>>
>> Allow the compiler to assume strict signed overflow rules, depending
>> on the language being compiled. For C (and C++) this means that
>> overflow when doing arithmetic with signed numbers is undefined,
>> which means that the compiler may assume that it does not happen.
>> This permits various optimizations. For example, the compiler assumes
>> that an expression like i + 10 > i is always true for signed i. This
>> assumption is only valid if signed overflow is undefined, as the
>> expression is false if i + 10 overflows when using twos complement
>> arithmetic. When this option is in effect any attempt to determine
>> whether an operation on signed numbers overflows must be written
>> carefully to not actually involve overflow.
>>
>> This option also allows the compiler to assume strict pointer
>> semantics: given a pointer to an object, if adding an offset to that
>> pointer does not produce a pointer to the same object, the addition
>> is undefined. This permits the compiler to conclude that p + u > p is
>> always true for a pointer p and unsigned integer u. This assumption
>> is only valid because pointer wraparound is undefined, as the
>> expression is false if p + u overflows using twos complement
>> arithmetic.
>>
>> See also the -fwrapv option. Using -fwrapv means that integer signed
>> overflow is fully defined: it wraps. When -fwrapv is used, there is
>> no difference between -fstrict-overflow and -fno-strict-overflow for
>> integers. With -fwrapv certain types of overflow are permitted. For
>> example, if the compiler gets an overflow when doing arithmetic on
>> constants, the overflowed value can still be used with -fwrapv, but
>> not otherwise.
>>
>> The -fstrict-overflow option is enabled at levels -O2, -O3, -Os.
> 
> It seems there is a complex interaction between -fstrict-overflow
> and -fwrapv. I'm not sure -fno-strict-overflow guarantees that signed
> integer overflow will actually wrap around.
> 
>> -fwrapv
>>
>> This option instructs the compiler to assume that signed arithmetic
>> overflow of addition, subtraction and multiplication wraps around
>> using twos-complement representation. This flag enables some
>> optimizations and disables others. The options -ftrapv and -fwrapv
>> override each other, so using -ftrapv -fwrapv on the command-line
>> results in -fwrapv being effective. Note that only active options
>> override, so using -ftrapv -fwrapv -fno-wrapv on the command-line
>> results in -ftrapv being effective.
> 
> So the question becomes:
> What is the exact semantic of -fno-strict-overflow -fno-wrapv ?
> 
> #include <limits.h>
> #include <stdio.h>
> int main() {
>          int i = INT_MAX - 5;
>          int j = 0;
>          for (; i <= INT_MAX - 2; i += 3) {
>                  if (i <= 1) {
>                          j = 1;
>                  }
>          }
>          printf("%d",j);
>          return 0;
> }
> 
> translated by gcc-6.3 -O2 -fstrict-overflow -fno-wrapv
> 
> .LC0:
>         .string "%d"
> main:
>         sub     rsp, 8
>         xor     esi, esi
>         mov     edi, OFFSET FLAT:.LC0
>         xor     eax, eax
>         call    printf
>         xor     eax, eax
>         add     rsp, 8
>         ret
> 
> translated by gcc-6.3 -O2 -fno-strict-overflow -fno-wrapv
> 
> main:
>         sub     rsp, 8
>         mov     eax, 2147483642
> .L2:
>         add     eax, 3
>         cmp     eax, 2147483645
>         jle     .L2
>         xor     esi, esi
>         mov     edi, OFFSET FLAT:.LC0
>         xor     eax, eax
>         call    printf
>         xor     eax, eax
>         add     rsp, 8
>         ret
> 
> => gcc keeps the loop, but removes the test and just calls printf("%d", 0); always.
> I'm not sure what these "xor eax, eax" are doing. They seem wasted.
> 
> translated by gcc-6.3 -O2 -fno-strict-overflow -fwrapv
> 
> main:
>         sub     rsp, 8
>         mov     eax, 2147483642
>         xor     esi, esi
>         mov     edx, 1
>         jmp     .L2
> .L4:
>         cmp     eax, 1
>         cmovle  esi, edx
> .L2:
>         add     eax, 3
>         cmp     eax, 2147483645
>         jle     .L4
>         mov     edi, OFFSET FLAT:.LC0
>         xor     eax, eax
>         call    printf
>         xor     eax, eax
>         add     rsp, 8
>         ret
> 
> This is the code you were expecting, I think.

Jeffrey's link to Ian's blog seems to clear some of the confusion.
http://www.airs.com/blog/archives/120


Ian wrote:

> However, gcc does need to respond to the concerns of the user
> community. I introduced two new options in gcc 4.2. The first is
> -fno-strict-overflow. This tells the compiler that it may not assume
> that signed overflow is undefined. The second is -Wstrict-overflow.
> This tells the compiler to warn about cases where it is using the
> fact that signed overflow is undefined to implement an optimization.
> With these options it is possible to detect cases where signed
> overflow occurs in a program, and it is possible to disable
> optimizations which rely on signed overflow until the program is
> fixed. The -Wstrict-overflow warning even found one minor case where
> gcc itself relied on wrapping signed overflow, in the handling of
> division by the constant 0x80000000.
> 
> This naturally leads to the question: what is the difference between
> -fwrapv and -fno-strict-overflow? There is a clear difference on a
> processor which does not use ordinary twos-complement arithmetic:
> -fwrapv requires twos-complement overflow, and -fno-strict-overflow
> does not. However, no such processor is in common use today. In
> practice, I think that the code generated by the two options will
> always behave the same. However, they affect the optimizers
> differently. For example, this code
>
>     int f(int x) { return (x + 0x7fffffff) * 2; } 
> 
> is compiled differently with -fwrapv and -fno-strict-overflow. The
> difference occurs because -fwrapv precisely specifies how the
> overflow should behave. -fno-strict-overflow merely says that the
> compiler should not optimize away the overflow. With the current
> compiler, with -fwrapv (and -O2 -fomit-frame-pointer), I see this:
> 
>     movl $1, %eax
>     subl 4(%esp), %eax
>     addl %eax, %eax
>     negl %eax
>     ret 
> 
> With -fno-strict-overflow I see this:
> 
>     movl 4(%esp), %eax
>     leal -2(%eax,%eax), %eax
>     ret 
> 
> Same result, different algorithm.


Regards.