Created attachment 32546 [details] Compile with -O2 and input 9 Compile the following code with -O2: ~~~~~ #include <cstdlib> #include <iostream> #include <cstdio> using namespace std; int main() { int n; cin >> n; for (int x = 0; x <= n; x++) { if (n == x + (x + 1) + (x + 2)) { cout << x + 2 << " " << x + 1 << " " << x << endl; exit(0); } } cout << -1 << endl; return 0; } ~~~~~ Start binary and enter 9 It will print "-1", but expected output is "4 3 2".
Looks like IV-opt is creating some overflows that were not there in the original code. Fails with: g++ (GCC) 4.9.0 20131026 (experimental) [trunk revision 204095] I have not updated my compiler since then.
fails for me with the (old) 4.7, 4.8 branch, works with 4.9. gcc version 4.7.2 20120816 (prerelease) [gcc-4_7-branch revision 190437] (GCC) : fail gcc version 4.8.3 20140315 (prerelease) [gcc-4_8-branch revision 208588] : fail gcc version 4.9.0 20140405 (experimental) [trunk revision 209137] (GCC) : OK
The bug is easily reproducible. It has the same behavior with gcc 4.7.3 on my Ubuntu. I hope this bug can be fixed soon, since the source code is so simple, and hence the bug may affect a lot of innocent programs.
Created attachment 32552 [details] self-contained test case, compilable as C and C++ The wrong-code reproduces for me with gcc 4.7 and 4.8 on x86_64-linux. For trunk it was fixed by r204515, which doesn't appear to be a wrong-code fix. Backporting r204515 to 4.8 fixes the wrong-code there too, but I haven't tested it beyond this test case.
I will have a look.
Created attachment 32556 [details] patch The issue is that tree-ssa-loop-ivopts.c:cand_value_at converts niter ((unsigned int) n_3 * 2863311531 + 4294967294) to 'int' via static void cand_value_at (struct loop *loop, struct iv_cand *cand, gimple at, tree niter, aff_tree *val) { aff_tree step, delta, nit; struct iv *iv = cand->iv; tree type = TREE_TYPE (iv->base); tree steptype = type; if (POINTER_TYPE_P (type)) steptype = sizetype; tree_to_aff_combination (iv->step, steptype, &step); tree_to_aff_combination (niter, TREE_TYPE (niter), &nit); aff_combination_convert (&nit, steptype); ^^^ which just does comb->type = type; if (comb->rest && !POINTER_TYPE_P (type)) comb->rest = fold_convert (type, comb->rest); thus re-interprets everything as signed. The whole aff_combination_convert function looks suspicious ... but at this stage the easiest thing to do is to avoid this 2nd call to this function (the other always converts to an unsigned type). Unfortunately doing that: Index: gcc/tree-ssa-loop-ivopts.c =================================================================== --- gcc/tree-ssa-loop-ivopts.c (revision 209181) +++ gcc/tree-ssa-loop-ivopts.c (working copy) @@ -4238,8 +4238,7 @@ cand_value_at (struct loop *loop, struct steptype = sizetype; tree_to_aff_combination (iv->step, steptype, &step); - tree_to_aff_combination (niter, TREE_TYPE (niter), &nit); - aff_combination_convert (&nit, steptype); + tree_to_aff_combination (fold_convert (steptype, niter), steptype, &nit); aff_combination_mult (&nit, &step, &delta); if (stmt_after_increment (loop, cand, at)) aff_combination_add (&delta, &step); reveals the other suspicious void tree_to_aff_combination (tree expr, tree type, aff_tree *comb) { aff_tree tmp; enum tree_code code; tree cst, core, toffset; HOST_WIDE_INT bitpos, bitsize; enum machine_mode mode; int unsignedp, volatilep; STRIP_NOPS (expr); which just re-introduces the exact same affine combination. This is kind-of a mess. Either the internal affine workings is modulo two arithmetic and thus it doesn't need to care - but then it needs to use unsigned arithmetic only at affine-to-tree time. Or it depends on the sign of the affine combination but then it has to be more careful. IIRC it is the first, thus affine-to-tree is wrong in returning signed arithmetic and keeping a "type" for the affine combination doesn't make much sense (similar issue for pointer arithmetic btw, where we choose a random "base"). But it's all kind of a mess. Working, somewhat localized patch attached.
Author: rguenth Date: Mon Apr 7 14:03:55 2014 New Revision: 209190 URL: http://gcc.gnu.org/viewcvs?rev=209190&root=gcc&view=rev Log: 2014-04-07 Richard Biener <rguenther@suse.de> PR tree-optimization/60766 * tree-ssa-loop-ivopts.c (cand_value_at): Compute in an unsigned type. (may_eliminate_iv): Convert cand_value_at result to desired type. * gcc.dg/torture/pr60766.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/torture/pr60766.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-loop-ivopts.c
Fixed on trunk sofar.
Author: rguenth Date: Tue May 6 09:02:08 2014 New Revision: 210099 URL: http://gcc.gnu.org/viewcvs?rev=210099&root=gcc&view=rev Log: 2014-05-06 Richard Biener <rguenther@suse.de> Backport from mainline 2014-04-17 Richard Biener <rguenther@suse.de> PR middle-end/60849 * tree-ssa-propagate.c (valid_gimple_rhs_p): Only allow effective boolean results for comparisons. * g++.dg/opt/pr60849.C: New testcase. 2014-04-07 Richard Biener <rguenther@suse.de> PR tree-optimization/60766 * tree-ssa-loop-ivopts.c (cand_value_at): Compute in an unsigned type. (may_eliminate_iv): Convert cand_value_at result to desired type. * gcc.dg/torture/pr60766.c: New testcase. 2014-04-23 Richard Biener <rguenther@suse.de> PR tree-optimization/60903 * tree-ssa-loop-im.c (execute_sm_if_changed): Properly apply IRREDUCIBLE_LOOP loop flags to newly created BBs and edges. * gcc.dg/torture/pr60903.c: New testcase. Added: branches/gcc-4_8-branch/gcc/testsuite/g++.dg/opt/pr60849.C branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr60766.c branches/gcc-4_8-branch/gcc/testsuite/gcc.dg/torture/pr60903.c Modified: branches/gcc-4_8-branch/gcc/ChangeLog branches/gcc-4_8-branch/gcc/testsuite/ChangeLog branches/gcc-4_8-branch/gcc/tree-ssa-loop-im.c branches/gcc-4_8-branch/gcc/tree-ssa-loop-ivopts.c branches/gcc-4_8-branch/gcc/tree-ssa-propagate.c
Fixed for 4.8.3.