[Bug c/56463] New: infinite loop when having integer overflow in a simple accumulator

[Bug c/56463] New: infinite loop when having integer overflow in a simple accumulator

[nakacristo at hotmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56463

             Bug #: 56463
           Summary: infinite loop when having integer overflow in a simple
                    accumulator
    Classification: Unclassified
           Product: gcc
           Version: 4.6.3
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: nakacristo@hotmail.com


A colleague has showed me a problem and I have reduced it to this code:

#include <stdio.h>
int main()
{
    int i,j;
    int a=0;
    for(i=0;i<20000;i++)
        for(j=0;j<600;j++)
            a=a+3435345234440;
    printf("%d\n",a);
    return 0;
}

With 'gcc test.c' or 'gcc test.c -O' works correctly, but with 'gcc test.c -O2'
fails. More exactly, fails with 'gcc test.c -O -fstrict-overflow -ftree-pre
-ftree-vrp'.

With the optimization it becomes an infinite loop
00000000004004f4 <main>:
  4004f4:    b8 58 02 00 00           mov    $0x258,%eax
  4004f9:    ba 58 02 00 00           mov    $0x258,%edx
  4004fe:    83 e8 01                 sub    $0x1,%eax
  400501:    0f 44 c2                 cmove  %edx,%eax
  400504:    eb f8                    jmp    4004fe <main+0xa>

The overflow could make the variable 'a' to take any value, but never to make
the loop infinite.


My gcc version: gcc version 4.6.3 (Gentoo 4.6.3 p1.9, pie-0.5.2)
I have checked that in gcc-4.5.3 works correctly.

[Bug c/56463] infinite loop when having integer overflow in a simple accumulator

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56463

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
                 CC|                            |jakub at gcc dot gnu.org
         Resolution|                            |INVALID

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-02-26 16:15:48 UTC ---
That is a problem with the testcase, not on the gcc side.  If you hit undefined
behavior (signed integer overflow in this case), anything can happen.

[Bug c/56463] infinite loop when having integer overflow in a simple accumulator

[nakacristo at hotmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56463

--- Comment #2 from Cristóbal Camarero <nakacristo at hotmail dot com> 2013-02-26 17:39:31 UTC ---
I think that at least -Wall -Wextra -Wstrict-overflow=5 should give a giving
notice of the extremely odd behaviour.

However, I am not following your reasoning to invalidate the bug. Are you
implying that any program with an integer overflow can be legally substituted
by a "Hello World"? It would have almost the same sense that the displayed
behaviour.

[Bug c/56463] infinite loop when having integer overflow in a simple accumulator

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56463

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-02-26 17:53:43 UTC ---
The compiler may assume that undefined behavior doesn't happen in the program.
It is fine to have undefined behavior in code that will be never executed, but
as soon as you hit it, the program can do anything.

[Bug c/56463] infinite loop when having integer overflow in a simple accumulator

[dominiq at lps dot ens.fr]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56463

--- Comment #4 from Dominique d'Humieres <dominiq at lps dot ens.fr> 2013-02-26 18:41:56 UTC ---
> The compiler may assume that undefined behavior doesn't happen in the program.
> It is fine to have undefined behavior in code that will be never executed, but
> as soon as you hit it, the program can do anything.

IMO the anything should be based on the "quality of implementation".
The present behavior is

(1) inconsistent (see PR 54932), the following test

#include "stdio.h"
int main(void)
{
 int huge=2147483647;
 int i, j, k;
 int e;

 i=huge-10;
 j=0;
 k=0;
 do
   {
    j=j+1;
    k=k-1;
    e = (i == huge);
    i++;
    if (e) break;
   }
 while(1);
 printf("i=%d,  j=%d,  k=%d\n", i, j, k);

 return 0;
}

does not give an infinite loop, but skip the last iteration, while the
following test

#include "stdio.h"
int main(void)
{
 int huge=2147483647;
 int i, j, init;
 int e;

 init = 0;
 j = init;
 for(i=-(huge/2);i<=1+huge/2; i++)
   {
    e = (j == huge);
    j=j+1;
    if (e) break;
   }
 printf("i=%d,  j=%d\n", i, j);

 return 0;
}

gives an infinite loop when compiled with -O2 (but indeed works for any
init<0);

(2) easy to fool: PR 54932 again;

(3) nasty: an infinite loop can hardly be considered as an optimization and it
is done without warning.

And yes I know that a compiler can do anything with undefined behavior, even
issue a rm -rf * for the home directory (and there are standard fundamentalists
around who think that this is the only sensible behavior).

[Bug c/56463] infinite loop when having integer overflow in a simple accumulator

[nakacristo at hotmail dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56463

--- Comment #5 from Cristóbal Camarero <nakacristo at hotmail dot com> 2013-02-27 08:19:04 UTC ---
Dominique, I think the test I found is more problematic than yours. Since in
mine, the huge value is completely independent of the ending condition. Hence
most people would expect the loop to end without care of what happens to the
accumulator variable 'a'.

Exploring the intermediate steps of my test (with gcc test.c -O2
-fdump-tree-all) I see that in test.c.119t.ivopts the condition of the loop is
changed from 'ivtmp.8_3 != 0' to 'a_25 != 1267128320', which would be correct
considering overflow.
From here the situation must be similar to Dominique's examples.
In test.c.123t.vrp2 we see that the Value Range Propagation has decided that
the ending condition never happens, probably because the ranges have no modular
considerations. The ending condition and the printf are eliminated. In a later
stage the infinite loop is substituted by an empty infinite loop.

I suppose that this is not technically a bug. However, the lack of warning IS a
bug.
And a coherent behaviour would still being a good enhancement.

[Bug c/56463] infinite loop when having integer overflow in a simple accumulator

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56463

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-02-27 08:31:25 UTC ---
The lack of warning is already tracked under PR53265.

[Bug c/56463] infinite loop when having integer overflow in a simple accumulator

[Joost.VandeVondele at mat dot ethz.ch]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56463

Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |john2.718281828459045235360
                   |                            |287 at gmail dot com

--- Comment #7 from Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> ---
*** Bug 59370 has been marked as a duplicate of this bug. ***

[Bug c/56463] infinite loop when having integer overflow in a simple accumulator

[Joost.VandeVondele at mat dot ethz.ch]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56463

Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mskyeong at naver dot com

--- Comment #8 from Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> ---
*** Bug 56600 has been marked as a duplicate of this bug. ***