[Bug middle-end/50708] New: Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[Bug middle-end/50708] New: Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rmansfield at qnx dot com]

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

             Bug #: 50708
           Summary: Infinite loop between rshift_double and lshift_double
                    if count is LONG_MIN
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: rmansfield@qnx.com
                CC: rguenther@suse.de
              Host: i686-unknown-linux-gnu
            Target: arm-unknown-linux-gnu
             Build: i686-unknown-linux-gnu


rshift_double() has 

  if (count < 0)
    {
      lshift_double (l1, h1, -count, prec, lv, hv, arith);
      return;
    }

and lshift_double() has:

  if (count < 0)
    {
      rshift_double (l1, h1, -count, prec, lv, hv, arith);
      return;
    }

so when count = LONG_MIN, count and -count are the same and end up calling each
forever, or until the process runs out of stack.

The backtrace shows the issue:

<snip>

#189 0x082e6cac in rshift_double (l1=1, h1=0, count=-2147483648, prec=32,
lv=0xbfdb53ac, hv=0xbfdb53b0, arith=1 '\001') at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/double-int.c:267
#190 0x082e6b28 in lshift_double (l1=1, h1=0, count=-2147483648, prec=32,
lv=0xbfdb53ac, hv=0xbfdb53b0, arith=1 '\001') at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/double-int.c:204
#191 0x082e6cac in rshift_double (l1=1, h1=0, count=-2147483648, prec=32,
lv=0xbfdb53ac, hv=0xbfdb53b0, arith=1 '\001') at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/double-int.c:267
#192 0x082e6b28 in lshift_double (l1=1, h1=0, count=-2147483648, prec=32,
lv=0xbfdb53ac, hv=0xbfdb53b0, arith=1 '\001') at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/double-int.c:204
#193 0x082e6cac in rshift_double (l1=1, h1=0, count=-2147483648, prec=32,
lv=0xbfdb53ac, hv=0xbfdb53b0, arith=1 '\001') at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/double-int.c:267
#194 0x082e6b28 in lshift_double (l1=1, h1=0, count=-2147483648, prec=32,
lv=0xbfdb53ac, hv=0xbfdb53b0, arith=1 '\001') at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/double-int.c:204
#195 0x082e7fd5 in double_int_lshift (a={low = 1, high = 0}, count=-2147483648,
prec=32, arith=1 '\001') at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/double-int.c:886
#196 0x083a9572 in int_const_binop (code=LSHIFT_EXPR, arg1=0x12a58c,
arg2=0x84d730) at /home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/fold-const.c:975
#197 0x083a9f2e in const_binop (code=LSHIFT_EXPR, arg1=0x12a58c, arg2=0x84d730)
at /home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/fold-const.c:1104
#198 0x084065f4 in fold_binary_loc (loc=0, code=LSHIFT_EXPR, type=0x13e360,
op0=0x12a58c, op1=0x84d730) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/fold-const.c:9517
#199 0x08889d8d in fully_constant_expression (e=0xaaf9204) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/tree-ssa-pre.c:1177
#200 0x0888ab34 in phi_translate_1 (expr=0xaaf9204, set1=0xaaf8830, set2=0x0,
pred=0xb57700, phiblock=0xb3d4c0) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/tree-ssa-pre.c:1511
#201 0x0888c05a in phi_translate (expr=0xaaf5690, set1=0xaaf8830, set2=0x0,
pred=0xb57700, phiblock=0xb3d4c0) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/tree-ssa-pre.c:1843
#202 0x0888c21e in phi_translate_set (dest=0xaaf8d70, set=0xaaf8830,
pred=0xb57700, phiblock=0xb3d4c0) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/tree-ssa-pre.c:1877
#203 0x0888de46 in compute_partial_antic_aux (block=0xb57700,
block_has_abnormal_pred_edge=0 '\0') at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/tree-ssa-pre.c:2449
#204 0x0888e7d7 in compute_antic () at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/tree-ssa-pre.c:2622
#205 0x08897841 in execute_pre (do_fre=0 '\0') at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/tree-ssa-pre.c:4898
#206 0x0889794e in do_pre () at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/tree-ssa-pre.c:4946
#207 0x085fe0e3 in execute_one_pass (pass=0x9016c00) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/passes.c:2064
#208 0x085fe50b in execute_pass_list (pass=0x9016c00) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/passes.c:2119
#209 0x085fe527 in execute_pass_list (pass=0x9015fc0) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/passes.c:2120
#210 0x08784f2a in tree_rest_of_compilation (fndecl=0x930a00) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/tree-optimize.c:420
#211 0x0829e503 in cgraph_expand_function (node=0x94f750) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/cgraphunit.c:1805
#212 0x0829e6a6 in cgraph_expand_all_functions () at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/cgraphunit.c:1864
#213 0x0829edf0 in cgraph_optimize () at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/cgraphunit.c:2141
#214 0x0829bc18 in cgraph_finalize_compilation_unit () at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/cgraphunit.c:1312
#215 0x080e729e in c_write_global_declarations () at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/c-decl.c:9940
#216 0x086e8e2f in compile_file () at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/toplev.c:581
#217 0x086eaeec in do_compile () at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/toplev.c:1925
#218 0x086eb069 in toplev_main (argc=125, argv=0xbfdbc134) at
/home/ryan/gnu/gcc/trunk/arm-oabi/../gcc/toplev.c:2001
#219 0x081d9e9a in main (argc=Cannot access memory at address 0x80000000

This happens in:

gcc version 4.7.0 20111012 (experimental) [trunk revision 179835] (GCC) 

I haven't come up with a small reproducible test case just yet..

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011-10-13
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-10-13 09:26:28 UTC ---
Confirmed.  Not very likely, but ...

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rmansfield at qnx dot com]

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

--- Comment #2 from Ryan Mansfield <rmansfield at qnx dot com> 2011-10-29 01:16:37 UTC ---
My large testcase reduced to:

void
foo ()
{
  unsigned int a = 1 << 0x80000000;
}

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[mikpe at it dot uu.se]

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

Mikael Pettersson <mikpe at it dot uu.se> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mikpe at it dot uu.se

--- Comment #3 from Mikael Pettersson <mikpe at it dot uu.se> 2011-10-29 13:29:20 UTC ---
The reduced test case throws 4.6.1 and 4.6-20111021 in a loop on i686-linux,
but 4.4/4.5/4.7 don't loop.  On m68k-linux both 4.6-20111021 and 4.7-20111022
loop.  I haven't been able to reproduce the loop on armv5tel-linux-gnueabi with
any of 4.4/4.5/4.6/4.7.

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rmansfield at qnx dot com]

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

--- Comment #4 from Ryan Mansfield <rmansfield at qnx dot com> 2011-10-29 14:28:57 UTC ---
(In reply to comment #3)
> I haven't been able to reproduce the loop on armv5tel-linux-gnueabi with
> any of 4.4/4.5/4.6/4.7.

arm eabi targets force 64bit HOST_WIDE_INT which is why the reduced testcase
didn't fail.

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[mikpe at it dot uu.se]

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

--- Comment #5 from Mikael Pettersson <mikpe at it dot uu.se> 2011-10-30 20:35:03 UTC ---
The regression started with r158372:
http://gcc.gnu.org/ml/gcc-cvs/2010-04/msg00478.html

Here's what seems to have happened:
1. Anatoly Sokolov suggested to add a bunch of double_int_ functions:
http://gcc.gnu.org/ml/gcc-patches/2010-04/msg00482.html.

2. Eric Botcazou replied about the added double_int_rshift (a wrapper around
rshift_double) that the comment about the COUNT parameter was wrong, and that
rshift_double requires it to be positive (double_int_rshift stated that a
negative COUNT turned it into a left-shift):
http://gcc.gnu.org/ml/gcc-patches/2010-04/msg00557.html.

3. In the final version of Anatoly's patch committed in r158360:
http://gcc.gnu.org/ml/gcc-cvs/2010-04/msg00466.html, the comment above
rshift_double was changed to allow a negative COUNT as meaning a left-shift. 
However, the code in rshift_double was not changed, and still assumed that
COUNT would be positive.

4. Richard Guenther followed up with a cleanup patch to move rshift_double and
other related functions from fold-const.c to double-int.c in r158372:
http://gcc.gnu.org/ml/gcc-cvs/2010-04/msg00478.html.  However, rshift_double
was not copied verbatim, as a check for a negative COUNT was added at the
beginning followed by a conditional call to lshift_double with -COUNT.  This
made the code consistent with the comment, but also caused the loop on HWI32
platforms.

I suspect that r158360 shouldn't have allowed for a negative COUNT to
rshift_double or double_int_rshift.  Removing the check for negative COUNT from
the start of rshift_double does fix the test case on i686 with gcc-4.6.

However, I'm worried that parts of gcc now depend on the extended semantics of
rshift_double and double_int_rshift, so reverting that may be problematic. 
Instead we can robustify rshift_double a bit: if COUNT < 0, check if COUNT
equals INTTYPE_MINIMUM (HOST_WIDE_INT), and if so don't negate COUNT and call
lshift_double but instead set COUNT to 2 * HOST_BITS_PER_WIDE_INT.  The
following code will then handle this like other too-large shifts.  This fixes
the test case too with no testsuite regressions on i686 with gcc-4.6.

gcc-4.7 doesn't have the issue on i686 because i686 is now HWI64 (right?), but
other HWI32 platforms like m68k and arm-oabi still have the problem.  I'm
currently testing the 2nd patch with gcc-4.7 on i686 and x86_64.

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |borut.razem at gmail dot
                   |                            |com

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-03-28 14:23:40 UTC ---
*** Bug 52653 has been marked as a duplicate of this bug. ***

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-03-28 14:24:15 UTC ---
Mine.

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rguenth at gcc dot gnu.org]

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

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-03-29 08:27:16 UTC ---
Author: rguenth
Date: Thu Mar 29 08:27:04 2012
New Revision: 185951

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=185951
Log:
2012-03-29  Richard Guenther  <rguenther@suse.de>

    PR middle-end/50708
    * double-int.h (rshift_double): Remove.
    * double-int.c (lshift_double): Use absu_hwi to make count
    positive.
    (rshift_double): Make static, take unsigned count argument,
    remove handling of negative count argument.
    (double_int_rshift): Dispatch to lshift_double.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/double-int.c
    trunk/gcc/double-int.h

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.8.0

--- Comment #9 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-03-29 09:21:17 UTC ---
Fixed on trunk sofar.

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.8.0

--- Comment #10 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-05 14:55:41 UTC ---
Anyway, fixed for 4.8.

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-06 09:25:51 UTC ---
Author: rguenth
Date: Fri Jul  6 09:25:46 2012
New Revision: 189314

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=189314
Log:
2012-07-06  Richard Guenther  <rguenther@suse.de>

    Backport from mainline
        2012-03-30  Richard Guenther  <rguenther@suse.de>

        PR middle-end/52786
        * double-int.c (rshift_double): Remove not
        needed cast.

    2012-03-28  Richard Guenther  <rguenther@suse.de>

    PR middle-end/50708
    * double-int.h (rshift_double): Remove.
    * double-int.c (lshift_double): Use absu_hwi to make count
    positive.
    (rshift_double): Make static, take unsigned count argument,
    remove handling of negative count argument.
    (double_int_rshift): Dispatch to lshift_double.

Modified:
    branches/gcc-4_7-branch/gcc/ChangeLog
    branches/gcc-4_7-branch/gcc/double-int.c
    branches/gcc-4_7-branch/gcc/double-int.h

[Bug middle-end/50708] Infinite loop between rshift_double and lshift_double if count is LONG_MIN

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.7.2
   Target Milestone|4.8.0                       |4.7.2
      Known to fail|                            |4.7.1

--- Comment #12 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-06 09:27:34 UTC ---
4.7.2 even.