[Bug tree-optimization/49218] New: Incorrect optimization of a 'for' loop creates an infinite loop

[Bug tree-optimization/49218] New: Incorrect optimization of a 'for' loop creates an infinite loop

[personal@e-maxx.ru]

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

           Summary: Incorrect optimization of a 'for' loop creates an
                    infinite loop
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: personal@e-maxx.ru


Created attachment 24388
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=24388
The program reads a number, and then it should output it back. After incorrect
optimization, however, the program hangs up

The following small program hangs up if compiled under gcc 4.6 with -O2.

The program reads a number (it can be any number, '5' for example), and then it
performs some silly for-loop, and then it should output the same number.

In gcc 4.6 with -O2, however, the program hangs up without outputting anything.
It looks like the loop (which can be doing less that 10 operations in reality)
is 'optimized' into an infinite loop.

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-29 10:22:24 UTC ---
Works for me on the 4.6 branch on x86_64-darwin.

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[mikpe at it dot uu.se]

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

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

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

--- Comment #2 from Mikael Pettersson <mikpe at it dot uu.se> 2011-05-29 11:31:51 UTC ---
Fails for me with recent 4.6 snapshots on i686-linux and m68k-linux, but not on
powerpc64-linux, alpha-linux, or armv5tel-linux.

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|                            |i686-pc-linux-gnu,
                   |                            |m68k-linux
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.05.29 16:36:29
     Ever Confirmed|0                           |1

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-29 16:36:29 UTC ---
Also works for me on x86_64-darwin with -m32.  Maybe a HWI issue?

Well, confirmed according to comment #5.

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-29 17:07:11 UTC ---
Works for me with a x86_64 multilibbed 4.6 from Debian on i?86-linux as well.
Bulding non-multilibbed variant now.

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-29 17:19:36 UTC ---
It's VRP being confused about the IV-optimized variant

<bb 2>:
  std::basic_istream<char>::_M_extract<float> (&cin, &ans);
  ans.1_2 = ans;
  i_3 = (long long int) ans.1_2;
  if (i_3 <= 10)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 3>:
  # i_12 = PHI <i_6(3), i_3(2)>
  i_6 = i_12 + 1;
  if (i_6 != 11)
    goto <bb 3>;
  else
    goto <bb 4>;

<bb 4>:
  std::basic_ostream<char>::operator<< (&cout, ans.1_2);
  return 0;

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-29 17:48:21 UTC ---
C testcase:

float f;
int main()
{
  long long i = f;
  if (i <= 10)
    do
      {
        ++i;
        asm("");
      }
    while (i != 11);
  return 0;
}

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> 2011-05-30 08:31:24 UTC ---
Can be reproduced on x86_64-linux too, with:
#ifdef __x86_64__
typedef __int128 L;
#else
typedef long long L;
#endif
float f;

int
main ()
{
  L i = f;
  if (i <= 10)
    do
      {
        ++i;
        asm ("");
      }
    while (i != 11);
  return 0;
}

at -O2.

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[mikpe at it dot uu.se]

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

--- Comment #8 from Mikael Pettersson <mikpe at it dot uu.se> 2011-05-30 09:00:46 UTC ---
Triggered by r163724:

Author: rguenth
Date: Wed Sep  1 11:39:55 2010
New Revision: 163724

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=163724
Log:
2010-09-01  Richard Guenther  <rguenther@suse.de>

    * tree-vrp.c (adjust_range_with_scev): Use number of iteration
    estimate.
    (vrp_visit_phi_node): Delay using SCEV till we balloon the
    range.
    (execute_vrp): Compute number of iteration estimates.
    * cfgloop.h (estimate_numbers_of_iterations_loop): Adjust prototype.
    * tree-flow.h (estimate_numbers_of_iterations): Likewise.
    * tree-data-ref.c (estimated_loop_iterations): Adjust.
    * tree-ssa-loop-niter.c (estimate_numbers_of_iterations_loop):
    Infer loop bounds from undefined behavior based on a new
    parameter.
    (estimate_numbers_of_iterations): Likewise.
    (scev_probably_wraps_p): Adjust.
    * tree-ssa-loop.c (tree_ssa_loop_bounds): Likewise.

The original C++ test case stopped failing on trunk with r171450:

Author: rguenth
Date: Fri Mar 25 11:59:19 2011
New Revision: 171450

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

    * passes.c (init_optimization_passes): Add FRE pass after
    early SRA.

but that's accidental: the C test case still fails after this, and the C++ one
fails if compiled with -O2 -fno-tree-fre.

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-30 09:13:17 UTC ---
I'm going to test

@@ -3423,11 +3423,14 @@ adjust_range_with_scev (value_range_t *v
                                            loop->nb_iterations_upper_bound,
                                            double_int_one),
                                        unsigned_p, &overflow);
-      tem = double_int_to_tree (TREE_TYPE (init), dtmp);
       /* If the multiplication overflowed we can't do a meaningful
-        adjustment.  */
-      if (!overflow && double_int_equal_p (dtmp, tree_to_double_int (tem)))
+        adjustment.  Likewise if the unsigned result doesn't fit in the type
+        of the induction variable.  */
+      if (!overflow
+         && double_int_fits_to_tree_p (TREE_TYPE (init), dtmp)
+         && (unsigned_p || dtmp.high > 0))
        {
+         tem = double_int_to_tree (TREE_TYPE (init), dtmp);
          extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
                                          TREE_TYPE (init), init, tem);
          /* Likewise if the addition did.  */

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #10 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-30 11:15:25 UTC ---
Author: rguenth
Date: Mon May 30 11:15:20 2011
New Revision: 174429

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=174429
Log:
2011-05-30  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/49218
    * tree-vrp.c (adjust_range_with_scev): Properly check whether
    overflow occured.

    * gcc.c-torture/execute/pr49218.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr49218.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[rguenth at gcc dot gnu.org]

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

--- Comment #11 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-30 11:17:38 UTC ---
Author: rguenth
Date: Mon May 30 11:17:35 2011
New Revision: 174430

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=174430
Log:
2011-05-30  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/49218
    * tree-vrp.c (adjust_range_with_scev): Properly check whether
    overflow occured.

    * gcc.c-torture/execute/pr49218.c: New testcase.

Added:
    branches/gcc-4_6-branch/gcc/testsuite/gcc.c-torture/execute/pr49218.c
Modified:
    branches/gcc-4_6-branch/gcc/ChangeLog
    branches/gcc-4_6-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_6-branch/gcc/tree-vrp.c

[Bug tree-optimization/49218] Incorrect optimization of a 'for' loop creates an infinite loop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.6.1
      Known to fail|                            |4.6.0

--- Comment #12 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-05-30 11:20:06 UTC ---
Fixed.