[Bug c/33498] New: Optimizer (-O2) may convert a normal loop to infinite

[Bug c/33498] New: Optimizer (-O2) may convert a normal loop to infinite

[dada1 at cosmosbay dot com]

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


-- 
           Summary: Optimizer (-O2) may convert a normal loop to infinite
           Product: gcc
           Version: 4.2.1
            Status: UNCONFIRMED
          Severity: critical
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dada1 at cosmosbay dot com
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2007-09-19 15:53 -------
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?


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org, rakdver at gcc dot gnu
                   |                            |dot org
             Status|UNCONFIRMED                 |NEW
          Component|c                           |tree-optimization
     Ever Confirmed|0                           |1
           Keywords|                            |wrong-code
   Last reconfirmed|0000-00-00 00:00:00         |2007-09-19 15:53:13
               date|                            |
            Summary|Optimizer (-O2) may convert |[4.2/4.3 Regression]
                   |a normal loop to infinite   |Optimizer (-O2) may convert
                   |                            |a normal loop to infinite
   Target Milestone|---                         |4.2.2


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2007-09-19 15:59 -------
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.


-- 


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[rask at gcc dot gnu dot org]

------- Comment #3 from rask at gcc dot gnu dot org  2007-09-19 16:12 -------
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]


-- 


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[pinskia at gcc dot gnu dot org]

------- Comment #4 from pinskia at gcc dot gnu dot org  2007-09-19 16:35 -------
what happens when val is turned into unsgned?


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
           Severity|critical                    |minor


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[rask at gcc dot gnu dot org]

------- Comment #5 from rask at gcc dot gnu dot org  2007-09-19 16:39 -------
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.


-- 


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[rakdver at gcc dot gnu dot org]

------- Comment #6 from rakdver at gcc dot gnu dot org  2007-09-19 16:45 -------
Mine.


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rakdver at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-09-19 15:53:13         |2007-09-19 16:45:10
               date|                            |


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2007-09-19 16:50 -------
And the code here is undefined as val does overflow.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |INVALID


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[rakdver at gcc dot gnu dot org]

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


-- 


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[ebotcazou at gcc dot gnu dot org]

------- Comment #9 from ebotcazou at gcc dot gnu dot org  2007-09-19 17:33 -------
Don't we/can't we issue a warning here?


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[dada1 at cosmosbay dot com]

------- Comment #10 from dada1 at cosmosbay dot com  2007-09-20 08:17 -------
> 
> 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.


-- 

dada1 at cosmosbay dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|INVALID                     |


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

[Bug tree-optimization/33498] [4.2/4.3 Regression] Optimizer (-O2) may convert a normal loop to infinite

[rguenther at suse dot de]

------- Comment #11 from rguenther at suse dot de  2007-09-20 08:44 -------
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.


-- 


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

[Bug tree-optimization/33498] Optimizer (-O2) may convert a normal loop to infinite

[pinskia at gcc dot gnu dot org]

------- Comment #12 from pinskia at gcc dot gnu dot org  2007-09-20 09:22 -------
>/* 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.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|                            |INVALID
            Summary|[4.2/4.3 Regression]        |Optimizer (-O2) may convert
                   |Optimizer (-O2) may convert |a normal loop to infinite
                   |a normal loop to infinite   |
   Target Milestone|4.2.2                       |---


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

[Bug tree-optimization/33498] Optimizer (-O2) may convert a normal loop to infinite

[rask at gcc dot gnu dot org]

------- Comment #13 from rask at gcc dot gnu dot org  2007-09-20 09:55 -------
> 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.


-- 


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

[Bug tree-optimization/33498] Optimizer (-O2) may convert a normal loop to infinite

[pinskia at gcc dot gnu dot org]

------- Comment #14 from pinskia at gcc dot gnu dot org  2007-09-20 15:30 -------
(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.


-- 


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

[Bug tree-optimization/33498] Optimizer (-O2) may convert a normal loop to infinite

[rakdver at gcc dot gnu dot org]

------- Comment #15 from rakdver at gcc dot gnu dot org  2007-09-20 18:47 -------
> 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.


-- 


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