[Bug c++/58417] New: Incorrect optimization

[Bug c++/58417] New: Incorrect optimization

[mirzayanovmr at gmail dot com]

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

            Bug ID: 58417
           Summary: Incorrect optimization
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: mirzayanovmr at gmail dot com

Created attachment 30820
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30820&action=edit
Compile it with "g++ -O2 a.cpp" and run. It will output 0 instead of 10.

The following code writes 0 (but 10 is expected) with -O1 or -O2. Checked on
4.7.2 and 4.8.1 (mingw), on Fedora with g++ (GCC) 4.8.1 20130603 (Red Hat
4.8.1-1).

Command line to compile: g++ -O2 a.cpp

Code:

#include<iostream>

using namespace std;

long long arr[6] = {0, 1, 2, 3, 4, 5};

int main()
{
    int n = 5;
    long long sum = 0, prevsum = 0;

    for(int i = 1; i <= n; i++)
    {
        cout << "sum = " << sum << endl;
        sum = (i - 1) * arr[i] - prevsum;
        // cout<<"sum : "<<sum<<endl;
        prevsum += arr[i];
    }

    cout << "Final Result: " << sum << endl;
}

[Bug tree-optimization/58417] Incorrect optimization

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-09-13
          Component|c++                         |tree-optimization
     Ever confirmed|0                           |1

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Confirmed with trunk and 4.4. sccp for some reason decides that after the loop
sum is 0.

[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
            Summary|Incorrect optimization      |Incorrect optimization in
                   |                            |SCEV const-prop
      Known to fail|                            |4.4.7, 4.5.4, 4.6.4, 4.7.3,
                   |                            |4.8.1, 4.9.0

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
C testcase that fails everywhere:

/* { dg-do run } */

long long arr[6] = {0, 1, 2, 3, 4, 5};
extern  void abort (void);
void __attribute__((noinline,noclone))
foo (long long sum)
{
  asm ("");
}
int main()
{
  int i, n = 5;
  long long sum = 0, prevsum = 0;

  for(i = 1; i <= n; i++)
    {
      foo (sum);
      sum = (i - 1) * arr[i] - prevsum;
      prevsum += arr[i];
    }

  if (sum != 10)
    abort ();
  return 0;
}

[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I will have a look.

[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sebpop at gmail dot com

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
SCCP does "constant propagation" each SSA name at the beginning which is where
it replaces sum_23 with 0.  It ends up there through interpret_condition_phi
with respect to loop 0 which analyzes the scalar evolution of
sum_11 in loop 1 to 0 because it simply passes down the loop

#2  0x0000000000c417c2 in interpret_condition_phi (loop=0x7ffff6d13320, 
    condition_phi=<gimple_phi 0x7ffff6e48200>)
    at /space/rguenther/src/svn/trunk/gcc/tree-scalar-evolution.c:1585
1585            (loop, PHI_ARG_DEF (condition_phi, i));
(gdb) l
1580              res = chrec_dont_know;
1581              break;
1582            }
1583
1584          branch_chrec = analyze_scalar_evolution
1585            (loop, PHI_ARG_DEF (condition_phi, i));
1586
1587          res = chrec_merge (res, branch_chrec);
1588        }

that is, this is a loop-closed PHI node, not a "condition PHI".  The
SSA edge following code seems to have the same issues.

That is, if an edge into a PHI is coming from an inner loop then we need
to compute the evolution of the PHI arg with respect to that (the definition
loop) and compute the overall effects for that inner loop before using
the result.

Hm, but analyzing sum_11 in loop1 results in

_10 = {0, +, _9}_1
prevsum_21 = {0, +, _9}_1

and thus sum_11 = _10 - prevsum_21 = 0.

Hmm.  I don't think that's a valid CHREC (_9 is defined in loop 1).  And
indeed resolve_mixers will drop those to scev_not_known.  But it doesn't
get to that as we first cancel the thing by doing the minus ...

So,

Index: tree-scalar-evolution.c
===================================================================
--- tree-scalar-evolution.c     (revision 202619)
+++ tree-scalar-evolution.c     (working copy)
@@ -1699,6 +1699,8 @@ interpret_rhs_expr (struct loop *loop, g
       chrec2 = analyze_scalar_evolution (loop, rhs2);
       chrec1 = chrec_convert (type, chrec1, at_stmt);
       chrec2 = chrec_convert (type, chrec2, at_stmt);
+      chrec1 = resolve_mixers (loop, chrec1);
+      chrec2 = resolve_mixers (loop, chrec2);
       res = chrec_fold_minus (type, chrec1, chrec2);
       break;

fixes this, but ... I suppose we need to do that for each binary/ternary
op and chrec (or just those that call chrec_fold_{plus,minus}).
That said, we cannot hope on such SSA names canceling themselves out
as they may not refer to the same actual value.

[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
But that eventually causes infinite recursions through instantiate_scev.

[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
So we want the evolution of sum_11 in the following loop (for a use on the
exit edge):

  # i_18 = PHI <i_13(4), 1(2)>
  # sum_19 = PHI <sum_11(4), 0(2)>
  # prevsum_21 = PHI <prevsum_12(4), 0(2)>
  foo (sum_19);
  _7 = i_18 + -1;
  _8 = (long long int) _7;
  _9 = arr[i_18];
  _10 = _8 * _9;
  sum_11 = _10 - prevsum_21;
  prevsum_12 = prevsum_21 + _9;
  i_13 = i_18 + 1;
  if (i_13 <= 5)
    goto <bb 4>;
  else
    goto <bb 5>;

  <bb 4>:
  goto <bb 3>;

and we compute

_10 = {0, +, _9}_1
_prevsum_21 = {0, +, _9}_1

but that is really meaningless as _9 is not a loop invariant which means that
this two very CHRECs are not "valid" as far as I understand, not valid to
operate on at least.

Thus the following asserts should IMHO hold (and trigger on the testcase
and many others)

Index: gcc/tree-chrec.c
===================================================================
--- gcc/tree-chrec.c    (revision 202644)
+++ gcc/tree-chrec.c    (working copy)
@@ -268,9 +268,14 @@ chrec_fold_plus_1 (enum tree_code code,
   switch (TREE_CODE (op0))
     {
     case POLYNOMIAL_CHREC:
+      gcc_checking_assert
+       (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
       switch (TREE_CODE (op1))
        {
        case POLYNOMIAL_CHREC:
+         gcc_checking_assert
+           (!chrec_contains_symbols_defined_in_loop (op1,
+                                                     CHREC_VARIABLE (op1)));
          return chrec_fold_plus_poly_poly (code, type, op0, op1);

        CASE_CONVERT:
@@ -298,6 +303,9 @@ chrec_fold_plus_1 (enum tree_code code,
       switch (TREE_CODE (op1))
        {
        case POLYNOMIAL_CHREC:
+         gcc_checking_assert
+           (!chrec_contains_symbols_defined_in_loop (op1,
+                                                     CHREC_VARIABLE (op1)));
          if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
            return build_polynomial_chrec
              (CHREC_VARIABLE (op1),
@@ -396,9 +404,14 @@ chrec_fold_multiply (tree type,
   switch (TREE_CODE (op0))
     {
     case POLYNOMIAL_CHREC:
+      gcc_checking_assert
+       (!chrec_contains_symbols_defined_in_loop (op0, CHREC_VARIABLE (op0)));
       switch (TREE_CODE (op1))
        {
        case POLYNOMIAL_CHREC:
+         gcc_checking_assert
+           (!chrec_contains_symbols_defined_in_loop (op1,
+                                                     CHREC_VARIABLE (op1)));
          return chrec_fold_multiply_poly_poly (type, op0, op1);

        CASE_CONVERT:
@@ -431,6 +444,9 @@ chrec_fold_multiply (tree type,
       switch (TREE_CODE (op1))
        {
        case POLYNOMIAL_CHREC:
+         gcc_checking_assert
+           (!chrec_contains_symbols_defined_in_loop (op1,
+                                                     CHREC_VARIABLE (op1)));
          return build_polynomial_chrec
            (CHREC_VARIABLE (op1),
             chrec_fold_multiply (type, CHREC_LEFT (op1), op0),

as of the recursion we can fix that by making the cache used to guard against
the recursion global (and maybe use instantiate_parameters instead of
resolve_mixers).

[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Wed Sep 18 12:31:45 2013
New Revision: 202700

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

    PR tree-optimization/58417
    * tree-chrec.c (chrec_fold_plus_1): Assert that we do not
    have chrecs with symbols defined in the loop as operands.
    (chrec_fold_multiply): Likewise.
    * tree-scalar-evolution.c (interpret_rhs_expr): Instantiate
    parameters before folding binary operations.
    (struct instantiate_cache_entry_hasher): Remove.
    (struct instantiate_cache_type): Use a pointer-map.
    (instantiate_cache_type::instantiate_cache_type): New function.
    (instantiate_cache_type::get): Likewise.
    (instantiate_cache_type::set): Likewise.
    (instantiate_cache_type::~instantiate_cache_type): Adjust.
    (get_instantiated_value_entry): Likewise.
    (global_cache): New global.
    (instantiate_scev_r, instantiate_scev_poly, instantiate_scev_binary,
    instantiate_array_ref, instantiate_scev_convert, instantiate_scev_3,
    instantiate_scev_2, instantiate_scev_1): Do not pass along cache.
    (instantiate_scev_name): Adjust.
    (instantiate_scev): Construct global instead of local cache.
    (resolve_mixers): Likewise.

    * gcc.dg/torture/pr58417.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr58417.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-chrec.c
    trunk/gcc/tree-scalar-evolution.c

[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
      Known to work|                            |4.9.0
         Resolution|---                         |FIXED

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk.

[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop

[rguenth at gcc dot gnu.org]

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

Bug 58417 depends on bug 58473, which changed state.

Bug 58473 Summary: [4.9 regression] FAIL: ext/random/normal_mv_distribution/cons/default.cc (test for excess errors)
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58473

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

[Bug tree-optimization/58417] Incorrect optimization in SCEV const-prop

[rguenth at gcc dot gnu.org]

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

Bug 58417 depends on bug 58484, which changed state.

Bug 58484 Summary: [4.9 Regression] ICE in chrec_fold_plus_1, at tree-chrec.c:272 building 416.gamess
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58484

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED