Bug 60766 - [4.7 Regression] Wrong optimization with -O2
Summary: [4.7 Regression] Wrong optimization with -O2
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.8.2
: P2 major
Target Milestone: 4.8.3
Assignee: Richard Biener
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2014-04-04 23:12 UTC by MikeMirzayanov
Modified: 2015-03-14 21:59 UTC (History)
8 users (show)

See Also:
Host:
Target: x86_64-*-*-*
Build:
Known to work: 4.4.5, 4.8.3, 4.9.0
Known to fail: 4.7.2, 4.7.4, 4.8.2
Last reconfirmed: 2014-04-07 00:00:00


Attachments
Compile with -O2 and input 9 (183 bytes, text/plain)
2014-04-04 23:12 UTC, MikeMirzayanov
Details
self-contained test case, compilable as C and C++ (136 bytes, text/plain)
2014-04-06 12:44 UTC, Mikael Pettersson
Details
patch (857 bytes, patch)
2014-04-07 11:20 UTC, Richard Biener
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description MikeMirzayanov 2014-04-04 23:12:47 UTC
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".
Comment 1 Andrew Pinski 2014-04-05 00:05:46 UTC
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.
Comment 2 Joost VandeVondele 2014-04-05 08:04:41 UTC
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
Comment 3 netheril96 2014-04-06 08:20:14 UTC
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.
Comment 4 Mikael Pettersson 2014-04-06 12:44:19 UTC
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.
Comment 5 Richard Biener 2014-04-07 10:26:36 UTC
I will have a look.
Comment 6 Richard Biener 2014-04-07 11:20:39 UTC
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.
Comment 7 Richard Biener 2014-04-07 14:04:27 UTC
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
Comment 8 Richard Biener 2014-04-07 14:09:49 UTC
Fixed on trunk sofar.
Comment 9 Richard Biener 2014-05-06 09:02:41 UTC
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
Comment 10 Richard Biener 2014-06-12 13:38:39 UTC
Fixed for 4.8.3.