[Bug tree-optimization/57685] New: GCC stuck in an infinite loop

[Bug tree-optimization/57685] New: GCC stuck in an infinite loop

[antoine.balestrat at gmail dot com]

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

            Bug ID: 57685
           Summary: GCC stuck in an infinite loop
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: antoine.balestrat at gmail dot com

Hello !
Using GCC 4.9.0 as of 20130623 :

$ cat inf.c
unsigned f(void)
{
    unsigned a;
    int b, c, d, e;

    for(c = 27; c < 40; c++)
        b |= d |= b;

    if(b)
        a = e;

    return a;
}

$ ulimit -t 60

$ xgcc -O3 inf.c
gcc: internal compiler error: CPU time limit exceeded (program cc1)
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

[Bug tree-optimization/57685] GCC stuck in an infinite loop

[mikpe at it dot uu.se]

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

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

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

--- Comment #1 from Mikael Pettersson <mikpe at it dot uu.se> ---
Also affects gcc-4.8-20130620, but not gcc-4.7-20130622, on x86_64-linux.  A
typical stack trace looks like:

0x00000000008709d5 in register_new_assert_for (expr=0x7f24dc840c60,
comp_code=EQ_EXPR, val=0x7f24dc855320, bb=<optimized out>, e=0x7f24dc975310,
si=..., 
    name=<optimized out>) at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:4486
4486          if (loc->comp_code == comp_code
Missing separate debuginfos, use: debuginfo-install glibc-2.15-59.fc17.x86_64
(gdb) bt
#0  0x00000000008709d5 in register_new_assert_for (expr=0x7f24dc840c60,
comp_code=EQ_EXPR, val=0x7f24dc855320, bb=<optimized out>, e=0x7f24dc975310, 
    si=..., name=<optimized out>) at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:4486
#1  0x000000000087633b in register_edge_assert_for_1 (op=0x7f24dc840c60,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5217
#2  0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#3  0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#4  0x000000000087650b in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5252
#5  0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#6  0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#7  0x000000000087650b in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5252
#8  0x000000000087650b in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5252
#9  0x000000000087650b in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5252
#10 0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#11 0x000000000087650b in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5252
#12 0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#13 0x000000000087650b in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5252
#14 0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#15 0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#16 0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#17 0x00000000008764aa in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5250
#18 0x000000000087650b in register_edge_assert_for_1 (op=<optimized out>,
code=code@entry=EQ_EXPR, e=e@entry=0x7f24dc975310, bsi=...)
    at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5252
#19 0x0000000000876886 in register_edge_assert_for (name=0x7f24dc840d38,
e=e@entry=0x7f24dc975310, si=..., cond_code=<optimized out>, 
    cond_op0=<optimized out>, cond_op1=0x7f24dc855320) at
/tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5347
#20 0x00000000008772cb in find_conditional_asserts (last=0x7f24dc960aa0,
bb=0x7f24dc9551a0) at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5393
#21 find_assert_locations_1 (bb=bb@entry=0x7f24dc9551a0, live=0x26d6640) at
/tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5607
#22 0x0000000000882c19 in find_assert_locations () at
/tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5747
#23 insert_range_assertions () at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:5935
#24 execute_vrp () at /tmp/gcc-4.8-20130620/gcc/tree-vrp.c:9287
#25 0x0000000000695785 in execute_one_pass (pass=pass@entry=0x26e2900) at
/tmp/gcc-4.8-20130620/gcc/passes.c:2330
#26 0x0000000000695b45 in execute_pass_list (pass=0x26e2900) at
/tmp/gcc-4.8-20130620/gcc/passes.c:2378
#27 0x0000000000695b57 in execute_pass_list (pass=0x11ca2a0) at
/tmp/gcc-4.8-20130620/gcc/passes.c:2379
#28 0x00000000004f0127 in expand_function (node=0x7f24dc8486f0) at
/tmp/gcc-4.8-20130620/gcc/cgraphunit.c:1640
#29 0x00000000004f1583 in expand_all_functions () at
/tmp/gcc-4.8-20130620/gcc/cgraphunit.c:1744
#30 compile () at /tmp/gcc-4.8-20130620/gcc/cgraphunit.c:2042
#31 0x00000000004f1ab5 in finalize_compilation_unit () at
/tmp/gcc-4.8-20130620/gcc/cgraphunit.c:2119
#32 0x00000000004275d5 in c_write_global_declarations () at
/tmp/gcc-4.8-20130620/gcc/c/c-decl.c:10118
#33 0x00000000007295d5 in compile_file () at
/tmp/gcc-4.8-20130620/gcc/toplev.c:557
#34 0x000000000072ac55 in do_compile () at
/tmp/gcc-4.8-20130620/gcc/toplev.c:1864
#35 toplev_main (argc=19, argv=0x7fff3eee17b8) at
/tmp/gcc-4.8-20130620/gcc/toplev.c:1940
#36 0x00007f24dca5e735 in __libc_start_main () from /lib64/libc.so.6
#37 0x00000000004194a1 in _start ()

[Bug tree-optimization/57685] GCC stuck in an infinite loop

[mikpe at it dot uu.se]

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

--- Comment #2 from Mikael Pettersson <mikpe at it dot uu.se> ---
Started with the PR55079 fix in r193098.

The test case uses the values of uninitialized auto variables, perhaps that's
confusing the compiler.

[Bug tree-optimization/57685] [4.8/4.9 Regression] GCC stuck in an infinite loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2013-06-24
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
   Target Milestone|---                         |4.8.2
            Summary|GCC stuck in an infinite    |[4.8/4.9 Regression] GCC
                   |loop                        |stuck in an infinite loop
     Ever confirmed|0                           |1
      Known to fail|                            |4.8.1

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed, mine.

[Bug tree-optimization/57685] [4.8/4.9 Regression] GCC stuck in an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
Hmm, it's register_edge_assert_for_1 not limiting its recursion and not
avoiding duplicate visits.  Which in this case leads to exponential
compile-time behavior.
We can mitigate the latter by only considering single-use defs.

[Bug tree-optimization/57685] [4.8/4.9 Regression] GCC stuck in an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Thu Aug 29 07:45:59 2013
New Revision: 202068

URL: http://gcc.gnu.org/viewcvs?rev=202068&root=gcc&view=rev
Log:
2013-08-29  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/57685
    * tree-vrp.c (register_edge_assert_for_1): Recurse only for
    single-use operands to avoid exponential complexity.

    * gcc.dg/torture/pr57685.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr57685.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/57685] [4.8 Regression] GCC stuck in an infinite loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.9.0
            Summary|[4.8/4.9 Regression] GCC    |[4.8 Regression] GCC stuck
                   |stuck in an infinite loop   |in an infinite loop

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk sofar.

[Bug tree-optimization/57685] [4.8 Regression] GCC stuck in an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Mon Sep  9 09:48:43 2013
New Revision: 202386

URL: http://gcc.gnu.org/viewcvs?rev=202386&root=gcc&view=rev
Log:
2013-09-09  Richard Biener  <rguenther@suse.de>

    Backport from mainline
    2013-08-29  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/57685
    * tree-vrp.c (register_edge_assert_for_1): Recurse only for
    single-use operands to avoid exponential complexity.

    * gcc.dg/torture/pr57685.c: New testcase.

Added:
    branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr57685.c
Modified:
    branches/gcc-4_8-branch/gcc/ChangeLog
    branches/gcc-4_8-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_8-branch/gcc/tree-vrp.c

[Bug tree-optimization/57685] [4.8 Regression] GCC stuck in an infinite loop

[rguenth at gcc dot gnu.org]

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

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

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

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed.