[Bug rtl-optimization/61657] New: Undefined behavior in loop-iv.c

[Bug rtl-optimization/61657] New: Undefined behavior in loop-iv.c

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

            Bug ID: 61657
           Summary: Undefined behavior in loop-iv.c
           Product: gcc
           Version: 4.10.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jakub at gcc dot gnu.org
                CC: rakdver at gcc dot gnu.org, rguenth at gcc dot gnu.org

Seen during bootstrap-ubsan bootstrap/regtest.  E.g.
./cc1 -O3 -fomit-frame-pointer -funroll-loops gcc.c-torture/compile/pr42049.c
../../gcc/loop-iv.c:2626:14: runtime error: signed integer overflow:
9223372036854775806 - -9223372036854775808 cannot be represented in type 'long
int'
../../gcc/loop-iv.c:2288:24: runtime error: signed integer overflow:
9223372036854775807 - -9223372036854775808 cannot be represented in type 'long
int'
but seen also during the bootstrap itself.
E.g. on line 2626:
          inc = INTVAL (iv0.step) - INTVAL (iv1.step);
          if (CONST_INT_P (iv1.base))
            up = INTVAL (iv1.base);
          else
            up = INTVAL (mode_mmax) - inc;
          down = INTVAL (CONST_INT_P (iv0.base)
                         ? iv0.base
                         : mode_mmin);
          max = (up - down) / inc + 1;
inc is 1, both iv0.base and iv1.base are non-CONST_INT and thus up is
0x7ffffffffffffffeLL and down is 0x8000000000000000LL (-LONG_MIN).
The subtraction and division surely can be performed in UHWI, or perhaps
widest_int, just not sure what is the right thing if there is any overflow or
if max is negative in the end - shall we just not record the bound at all?

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |trippels at gcc dot gnu.org

--- Comment #1 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
*** Bug 63396 has been marked as a duplicate of this bug. ***

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

--- Comment #3 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
*** Bug 61944 has been marked as a duplicate of this bug. ***

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zeccav at gmail dot com

--- Comment #2 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
*** Bug 61942 has been marked as a duplicate of this bug. ***

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[zeccav at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

--- Comment #4 from Vittorio Zecca <zeccav at gmail dot com> ---
I am having the same problem in 5.2.0:
/* must be compiled with -O[1] -funroll-loops -foptimize-sibling-calls
-finline-small-functions */
/* target x86_64-unknown-linux-gnu */
/* Fedora 21 */
/*gcc-5.2.0/gcc/loop-iv.c:2670:25: runtime error: signed integer overflow: 123
- -9223372036854775808 cannot be represented in type 'long int'*/
/* source line "max = (uint64_t) (up - down) / inc + 1;" */
long level = 0;
extern long foo (void);
extern long bar (void);


long
foo (void)
{
  long tmp = ++level;
  return bar () + tmp;
}

long
bar (void)
{
  long tmp = level;
  return tmp > 123 ? -42 - tmp : foo () - tmp;
}

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[zeccav at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

--- Comment #5 from Vittorio Zecca <zeccav at gmail dot com> ---
Just confirmed adding
printf("up=%li down=%li up-down=%li\n", up,down,up-down);
before line 2670.
Output is
up=123 down=-9223372036854775808 up-down=-9223372036854775685

You could probably get an ICE with
gcc_assert(up-down>0);

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[zeccav at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

--- Comment #6 from Vittorio Zecca <zeccav at gmail dot com> ---
A shorter source file displaying the same bug:

// from pr42049.c
// gcc -funroll-loops -O
// ../../gcc-5.2.0/gcc/loop-iv.c:2670:14: runtime error: 
// signed integer overflow: 7 - -9223372036854775808 cannot be represented in
type 'long int'
// loop-iv.c source line "max = (uint64_t) (up - down) / inc + 1;"
// Target: x86_64-unknown-linux-gnu
// COLLECT_GCC_OPTIONS='-funroll-loops' '-O' '-mtune=generic' '-march=x86-64'
void
foo (void)
{
 long int i;
 for (i = 1; i  && i < 8; i++);
}

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2015-08-21
           Assignee|unassigned at gcc dot gnu.org      |trippels at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #7 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
Hmm, git blame of /* source line "max = (uint64_t) (up - down) / inc + 1;" */
points to me.
I will take a look.

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[zeccav at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

--- Comment #8 from Vittorio Zecca <zeccav at gmail dot com> ---
Maybe the easiest way to reproduce the issue is as in the following;

gdb ~/local/gcc-5.2.0-sanitized/libexec/gcc/x86_64-unknown-linux-gnu/5.2.0/cc1
GNU gdb (GDB) Fedora 7.8.2-39.fc21
Copyright (C) 2014 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-redhat-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from
/home/vitti/local/gcc-5.2.0-sanitized/libexec/gcc/x86_64-unknown-linux-gnu/5.2.0/cc1...done.
(gdb) break ../../gcc-5.2.0/gcc/loop-iv.c:2671
Breakpoint 1 at 0x153209e: file ../../gcc-5.2.0/gcc/loop-iv.c, line 2671.
(gdb) run gccerr14.c -O -quiet -funroll-loops
Starting program:
/home/vitti/local/gcc-5.2.0-sanitized/libexec/gcc/x86_64-unknown-linux-gnu/5.2.0/cc1
gccerr14.c -O -quiet -funroll-loops
Missing separate debuginfos, use: debuginfo-install glibc-2.20-8.fc21.x86_64
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".

Breakpoint 1, iv_number_of_iterations (loop=0x2aaab633f360,
insn=0x2aaab635e400, condition=0x2aaab6362d98, 
    desc=0x7fffffffa810) at ../../gcc-5.2.0/gcc/loop-iv.c:2671
2671              max = (uint64_t) (up - down) / inc + 1;
Missing separate debuginfos, use: debuginfo-install gmp-6.0.0-9.fc21.x86_64
libmpc-1.0.2-3.fc21.x86_64 mpfr-3.1.2-8.fc21.x86_64
(gdb) print up
$1 = 7
(gdb) print down
$2 = -9223372036854775808

But you need an unoptimized version of cc1

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

--- Comment #9 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
Patch posted: https://gcc.gnu.org/ml/gcc-patches/2015-08/msg01308.html

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

--- Comment #10 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
Author: trippels
Date: Fri Aug 21 16:44:30 2015
New Revision: 227075

URL: https://gcc.gnu.org/viewcvs?rev=227075&root=gcc&view=rev
Log:
Fix PR61657 (undefined behavior in loop-iv.c)

bootstrap-ubsan shows:
 loop-iv.c:2626:14: runtime error: signed integer overflow: 9223372036854775806
- -9223372036854775808 cannot be represented in type 'long int'

Fixed by moving the variables in question from signed to unsigned.

        PR rtl-optimization/61657
        * loop-iv.c (iv_number_of_iterations): Declare up and down as
        unsigned. Remove superflous uint64_t cast.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/loop-iv.c

[Bug rtl-optimization/61657] Undefined behavior in loop-iv.c

[trippels at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61657

Markus Trippelsdorf <trippels at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #11 from Markus Trippelsdorf <trippels at gcc dot gnu.org> ---
Fixed on trunk.