[Bug tree-optimization/55107] New: GCC in an infinite loop at -O2

[Bug tree-optimization/55107] New: GCC in an infinite loop at -O2

[antoine.balestrat at gmail dot com]

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

             Bug #: 55107
           Summary: GCC in an infinite loop at -O2
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: antoine.balestrat@gmail.com


Hello !
GCC 4.8.0 as of 20121021 and GCC 4.7.2 won't compile the following testcase at
-O2 and higher because they look stuck in an infinite loop.

$ cat infinite.c
#include <stdint.h>

uint16_t a, b;

uint16_t f(void)
{
    int c, **p;
    short d = 2, e = 4;

    for (;; b++)
    {
        int *j, k = 0;

        for (; *j; j++)
        {
            for(; c; c++)
                for(; k < 1; k++)
                {
                    short *f = &d;

                    if(b)
                        return *f;
                }
        }

        if(!c)
            d *= e;

        ((a = d) ? b = 0 : (**p ? : 1) != (d != 1 ? : (a = 0))) != (k ? a : 0)
< (a *= c = k) && (**p = 0);
    }
}

$ ulimite -t 60

$ xgcc -O2 -w infinite.c
cc: internal compiler error: CPU time limit exceeded (program cc1)
linux-vdso.so.1: No such file or directory
0x40b937 execute
    ../../srcdir/gcc/gcc.c:2739
0x40c7be do_spec_1
    ../../srcdir/gcc/gcc.c:4534
0x40f0d5 process_brace_body
    ../../srcdir/gcc/gcc.c:5782
0x40f0d5 handle_braces
    ../../srcdir/gcc/gcc.c:5696
0x40d397 do_spec_1
    ../../srcdir/gcc/gcc.c:5179
0x40f0d5 process_brace_body
    ../../srcdir/gcc/gcc.c:5782
0x40f0d5 handle_braces
    ../../srcdir/gcc/gcc.c:5696
0x40d397 do_spec_1
    ../../srcdir/gcc/gcc.c:5179
0x40cff7 do_spec_1
    ../../srcdir/gcc/gcc.c:5284
0x40f0d5 process_brace_body
    ../../srcdir/gcc/gcc.c:5782
0x40f0d5 handle_braces
    ../../srcdir/gcc/gcc.c:5696
0x40d397 do_spec_1
    ../../srcdir/gcc/gcc.c:5179
0x40f0d5 process_brace_body
    ../../srcdir/gcc/gcc.c:5782
0x40f0d5 handle_braces
    ../../srcdir/gcc/gcc.c:5696
0x40d397 do_spec_1
    ../../srcdir/gcc/gcc.c:5179
0x40f0d5 process_brace_body
    ../../srcdir/gcc/gcc.c:5782
0x40f0d5 handle_braces
    ../../srcdir/gcc/gcc.c:5696
0x40d397 do_spec_1
    ../../srcdir/gcc/gcc.c:5179
0x40f0d5 process_brace_body
    ../../srcdir/gcc/gcc.c:5782
0x40f0d5 handle_braces
    ../../srcdir/gcc/gcc.c:5696
Please submit a full bug report,
with preprocessed source if appropriate.
Please include the complete backtrace with any bug report.
See <http://gcc.gnu.org/bugs.html> for instructions.

Note that the stack trace looks the same as in PR55011.

[Bug tree-optimization/55107] [4.7/4.8 Regression] GCC in an infinite loop in PRE

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
      Known to work|                            |4.4.5
           Keywords|                            |compile-time-hog
   Last reconfirmed|                            |2012-12-09
     Ever Confirmed|0                           |1
            Summary|GCC in an infinite loop at  |[4.7/4.8 Regression] GCC in
                   |-O2                         |an infinite loop in PRE
   Target Milestone|---                         |4.7.3
      Known to fail|                            |4.7.0, 4.8.0

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-12-09 02:55:54 UTC ---
#0  0x0000000000bd02db in bmp_iter_set (bi=0x7fffffffda90,
bit_no=0x7fffffffdab4) at /home/apinski/src/gcc-fsf/local//gcc/gcc/bitmap.h:532
#1  0x0000000000bd305f in bitmap_set_replace_value (set=0x1970858, lookfor=29,
expr=0x197d9a8) at /home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:862
#2  0x0000000000bd30e6 in bitmap_value_replace_in_set (set=0x1970858,
expr=0x197d9a8) at /home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:889
#3  0x0000000000bda1dd in insert_aux (block=0x7ffff70223a8) at
/home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:3639
#4  0x0000000000bda294 in insert_aux (block=0x7ffff6fe6d00) at
/home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:3654
#5  0x0000000000bda294 in insert_aux (block=0x7ffff6fe6bc8) at
/home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:3654
#6  0x0000000000bda294 in insert_aux (block=0x7ffff6fe6820) at
/home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:3654
#7  0x0000000000bda294 in insert_aux (block=0x7ffff6fe62d8) at
/home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:3654
#8  0x0000000000bda294 in insert_aux (block=0x7ffff6fe6270) at
/home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:3654
#9  0x0000000000bda294 in insert_aux (block=0x7ffff6fe61a0) at
/home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:3654
#10 0x0000000000bda372 in insert () at
/home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:3677
#11 0x0000000000bdd70f in do_pre () at
/home/apinski/src/gcc-fsf/local//gcc/gcc/tree-ssa-pre.c:4729

>Note that the stack trace looks the same as in PR55011.
That stack trace is just where xgcc is saying the cc1 was executed from.

[Bug tree-optimization/55107] [4.7/4.8 Regression] GCC in an infinite loop in PRE

[rguenth at gcc dot gnu.org]

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

Richard Biener <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 #2 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-10 09:50:51 UTC ---
Mine.  We don't stop insertion:

Starting insert iteration 3362
Found partial redundancy for expression {nop_expr,d_33} (0024)
Skipping insertion of phi for partial redundancy: Looks like an induction
variable
Inserted pretmp_3451 = (unsigned short) d_25;
 in predecessor 19
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Starting insert iteration 3363
Found partial redundancy for expression {nop_expr,d_33} (0024)
Skipping insertion of phi for partial redundancy: Looks like an induction
variable
Inserted pretmp_3452 = (unsigned short) d_25;
 in predecessor 19
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Found fully redundant value
Starting insert iteration 3364
Found partial redundancy for expression {nop_expr,d_33} (0024)
...

[Bug tree-optimization/55107] [4.7/4.8 Regression] GCC in an infinite loop in PRE

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |55629

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-10 12:13:54 UTC ---
The issue is shown by:

Index: tree-ssa-pre.c
===================================================================
--- tree-ssa-pre.c      (revision 194345)
+++ tree-ssa-pre.c      (working copy)
@@ -867,6 +867,8 @@ bitmap_set_replace_value (bitmap_set_t s
          return;
        }
     }
+
+  gcc_unreachable ();
 }

that is, we have a value in NEW_SETS,

(gdb) call debug_bitmap_set (set)
debug[0] := { prephitmp_61 (0036), prephitmp_74 (0056), prephitmp_29 (0057),
prephitmp_62 (0046), prephitmp_6 (0047), prephitmp_73 (0029) }
(gdb) p lookfor
$1 = 29

that is not in value_expressions:

0029[0] := { d.7_35 (0029), {nop_expr,d_25} (0029),
{mem_ref<0B>,addr_expr<&a>}@.MEM_36 (0029), prephitmp_83 (0029) }

That happens because we re-set prephitmp_73's value from its original 37
to 29 in do_regular_insertion but do not adjust value_expressions.
In fact,

          /* If all edges produce the same value and that value is
             an invariant, then the PHI has the same value on all
             edges.  Note this.  */
          else if (!cant_insert && all_same && eprime
                   && (edoubleprime->kind == CONSTANT
                       || edoubleprime->kind == NAME)
                   && !value_id_constant_p (val))
            {
              unsigned int j;
              bitmap_iterator bi;
              bitmap exprset = value_expressions[val];

              unsigned int new_val = get_expr_value_id (edoubleprime);
              EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bi)
                {
                  pre_expr expr = expression_for_id (j);

                  if (expr->kind == NAME)
                    {
                      vn_ssa_aux_t info = VN_INFO (PRE_EXPR_NAME (expr));
                      /* Just reset the value id and valnum so it is
                         the same as the constant we have discovered.  */
                      if (edoubleprime->kind == CONSTANT)
                        {
                          info->valnum = PRE_EXPR_CONSTANT (edoubleprime);
                          pre_stats.constified++;
                        }
                      else
                        info->valnum = VN_INFO (PRE_EXPR_NAME
(edoubleprime))->valnum;
                      info->value_id = new_val;
                    }
                }

looks like a hack that while adjusting all existing name(!)
expressions for a value it does not adjust bitmap sets.  What it seems to
try to do is unify two value-ids after-the-fact.

We cannot get this "right" this way.  We simply have to perform PHI
insertion to "merge" the values.

The above is a hack around the inability of the value-numbering to handle
this case (see PR55629).  But it's not a sustainable solution as this
bug shows ...

I have a patch.

[Bug tree-optimization/55107] [4.7 Regression] GCC in an infinite loop in PRE

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.8.0
            Summary|[4.7/4.8 Regression] GCC in |[4.7 Regression] GCC in an
                   |an infinite loop in PRE     |infinite loop in PRE
      Known to fail|4.8.0                       |

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-10 14:01:33 UTC ---
Fixed on trunk sofar.

[Bug tree-optimization/55107] [4.7/4.8 Regression] GCC in an infinite loop in PRE

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-10 14:00:39 UTC ---
Author: rguenth
Date: Mon Dec 10 14:00:25 2012
New Revision: 194358

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=194358
Log:
2012-12-10  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/55107
    * tree-ssa-pre.c (struct pre_stats): Remove constified field.
    (bitmap_set_replace_value): Add gcc_unreachable.
    (do_regular_insertion): Re-write all_same handling.  Insert
    an assignment instead of a PHI in this case.
    (eliminate_bb): Record availability also for SSA names defined
    by a constant.
    (do_pre): Do not record constified events.
    (execute_fre): Likewise.

    * gcc.dg/torture/pr55107.c: New testcase.
    * gcc.dg/tree-ssa/ssa-pre-5.c: Adjust.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr55107.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-5.c
    trunk/gcc/tree-ssa-pre.c

[Bug tree-optimization/55107] [4.7 Regression] GCC in an infinite loop in PRE

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> 2013-02-05 12:56:56 UTC ---
Author: rguenth
Date: Tue Feb  5 12:56:51 2013
New Revision: 195755

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

    Backport from mainline
    2012-12-10  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/55107
    * tree-ssa-pre.c (struct pre_stats): Remove constified field.
    (bitmap_set_replace_value): Add gcc_unreachable.
    (do_regular_insertion): Re-write all_same handling.  Insert
    an assignment instead of a PHI in this case.
    (execute_pre): Do not record constified events.

    * gcc.dg/torture/pr55107.c: New testcase.
    * gcc.dg/tree-ssa/ssa-pre-5.c: Adjust.

Added:
    branches/gcc-4_7-branch/gcc/testsuite/gcc.dg/torture/pr55107.c
Modified:
    branches/gcc-4_7-branch/gcc/ChangeLog
    branches/gcc-4_7-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_7-branch/gcc/testsuite/gcc.dg/tree-ssa/ssa-pre-5.c
    branches/gcc-4_7-branch/gcc/tree-ssa-pre.c

[Bug tree-optimization/55107] [4.7 Regression] GCC in an infinite loop in PRE

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
      Known to fail|                            |4.7.2

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> 2013-02-05 12:57:26 UTC ---
Fixed.