Bug 49218 - Incorrect optimization of a 'for' loop creates an infinite loop
Summary: Incorrect optimization of a 'for' loop creates an infinite loop
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.6.0
: P3 normal
Target Milestone: 4.6.1
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-05-29 01:33 UTC by e-maxx
Modified: 2011-05-30 11:20 UTC (History)
2 users (show)

See Also:
Host:
Target: i686-pc-linux-gnu, m68k-linux
Build:
Known to work:
Known to fail: 4.6.0
Last reconfirmed: 2011-05-29 16:36:29


Attachments
The program reads a number, and then it should output it back. After incorrect optimization, however, the program hangs up (315 bytes, application/octet-stream)
2011-05-29 01:33 UTC, e-maxx
Details

Note You need to log in before you can comment on or make changes to this bug.
Description e-maxx 2011-05-29 01:33:35 UTC
Created attachment 24388 [details]
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.
Comment 1 Richard Biener 2011-05-29 10:22:24 UTC
Works for me on the 4.6 branch on x86_64-darwin.
Comment 2 Mikael Pettersson 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.
Comment 3 Richard Biener 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.
Comment 4 Richard Biener 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.
Comment 5 Richard Biener 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;
Comment 6 Richard Biener 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;
}
Comment 7 Jakub Jelinek 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.
Comment 8 Mikael Pettersson 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.
Comment 9 Richard Biener 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.  */
Comment 10 Richard Biener 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
Comment 11 Richard Biener 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
Comment 12 Richard Biener 2011-05-30 11:20:06 UTC
Fixed.