[Bug tree-optimization/57511] New: [4.8/4.9 Regression] Missing SCEV final value replacement

[Bug tree-optimization/57511] New: [4.8/4.9 Regression] Missing SCEV final value replacement

[amonakov at gcc dot gnu.org]

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

            Bug ID: 57511
           Summary: [4.8/4.9 Regression] Missing SCEV final value
                    replacement
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: amonakov at gcc dot gnu.org

The following simple loop is no longer optimized out with 4.8 and 4.9:


int main(int argc, char* argv[])
{
    int i, a = 0;
    for (i=0; i < 10000; i++)
            a += i + 0xff00ff;
    return a;
}


$ gcc-4.7.2 -O2 -S main.c -o-
main:
.LFB0:
    .cfi_startproc
    movl    $-334379544, %eax
    ret


$ gcc-4.8.0 -O2 -S main.c -o-
main:
.LFB0:
    .cfi_startproc
    movl    $16711935, %edx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    addl    %edx, %eax
    addl    $1, %edx
    cmpl    $16721935, %edx
    jne    .L3
    rep ret

[Bug tree-optimization/57511] [4.8/4.9 Regression] Missing SCEV final value replacement

[amonakov at gcc dot gnu.org]

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

--- Comment #1 from Alexander Monakov <amonakov at gcc dot gnu.org> ---
The loop invokes signed integer overflow, but changing 10000 to 10 still keeps
the missed optimization there.

[Bug tree-optimization/57511] [4.8/4.9 Regression] Missing SCEV final value replacement

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2013-06-04
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
   Target Milestone|---                         |4.8.2
     Ever confirmed|0                           |1

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

[Bug tree-optimization/57511] [4.8/4.9 Regression] Missing SCEV final value replacement

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |spop at gcc dot gnu.org
             Blocks|                            |55555

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
analyze_scalar_evolution_in_loop fails for a_4 in

  <bb 4>:
  # i_11 = PHI <i_5(3), 0(2)>
  # a_12 = PHI <a_4(3), 0(2)>
  _3 = i_11 + 16711935;
  a_4 = _3 + a_12;
  i_5 = i_11 + 1;
  if (i_5 != 10)
    goto <bb 3>;
  else
    goto <bb 5>;

  <bb 5>:
  # a_6 = PHI <a_4(4)>
  return a_6;

the evolution is {16711935, +, _3 + 1}_1 but the evolution of _3
is { 16711935, +, 1 }_1 and { 16711935, +, { 16711935, +, 1 }_1 + 1}_1
isn't a valid evolution.  Even though 4.7 computed:

(chrec_apply
  (varying_loop = 1
)
  (chrec = {16711935, +, {16711936, +, 1}_1}_1)
  (x = 9)
  (res = 167119395))

this is probably caused by the fix for PR55555.

I will experiment with relaxing it a bit tomorrow.  But the question
remains(?), is

  { 16711935, +, { 16711935, +, 1 }_1 + 1}_1

a valid scalar evolution?

[Bug tree-optimization/57511] [4.8/4.9 Regression] Missing SCEV final value replacement

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
It looks like

Index: gcc/tree-scalar-evolution.c
===================================================================
--- gcc/tree-scalar-evolution.c (revision 202068)
+++ gcc/tree-scalar-evolution.c (working copy)
@@ -2252,6 +2252,7 @@ instantiate_scev_name (basic_block insta
   else if (res != chrec_dont_know)
     {
       if (inner_loop
+         && def_bb->loop_father != inner_loop
          && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
        /* ???  We could try to compute the overall effect of the loop here. 
*/
        res = chrec_dont_know;

should be correct, but it has some testsuite fallout that needs to be
analyzed (at least uncovering an IVOPTS issue).

[Bug tree-optimization/57511] [4.8/4.9 Regression] Missing SCEV final value replacement

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #4)
> It looks like
> 
> Index: gcc/tree-scalar-evolution.c
> ===================================================================
> --- gcc/tree-scalar-evolution.c (revision 202068)
> +++ gcc/tree-scalar-evolution.c (working copy)
> @@ -2252,6 +2252,7 @@ instantiate_scev_name (basic_block insta
>    else if (res != chrec_dont_know)
>      {
>        if (inner_loop
> +         && def_bb->loop_father != inner_loop
>           && !flow_loop_nested_p (def_bb->loop_father, inner_loop))
>         /* ???  We could try to compute the overall effect of the loop here.
> */
>         res = chrec_dont_know;
> 
> should be correct, but it has some testsuite fallout that needs to be
> analyzed (at least uncovering an IVOPTS issue).

Ok, the only issue is gcc.dg/tree-ssa/reassoc-19.c FAILing because IVOPTs
now detects a BIV and does something - previously it bailed out.  We have

  <bb 2>:
  goto <bb 4>;

  <bb 3>:
  _7 = (sizetype) element_6(D);
  _8 = -_7;
  rite_9 = rite_1 + _8;
  bar (left_5(D), rite_9, element_6(D));

  <bb 4>:
  # rite_1 = PHI <rite_3(D)(2), rite_9(3)>
  if (left_5(D) <= rite_1)
    goto <bb 3>;
  else
    goto <bb 5>;

  <bb 5>:
  return;

and the BIV rite_1 is {rite_3(D), +, -(sizetype) element_6(D)}_1

that's good and an improvement.  IVOPTs decides to use the original BIV:

candidate 8 (important)
  var_before rite_1
  var_after rite_9
  original biv
  type char *
  base rite_3(D)
  step -(sizetype) element_6(D)
  base object (void *) rite_3(D)

which ideally would result in no code change ...?

Well.

The issue is that rewrite_use_nonlinear_expr of rite_9 = rite_1 + _8
gets things folded back to (char *) ((unsigned long) rite_1 - (unsigned long)
element_6(D)) from the more optimal
rite_1 + (-(sizetype) element_6(D))

Which is because of the way we try to get around plus vs. pointer-plus
in get_computation_aff and ultimately aff_combination_to_tree.

I'm going to clean that up ...

[Bug tree-optimization/57511] [4.8/4.9 Regression] Missing SCEV final value replacement

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Mon Sep  2 13:24:30 2013
New Revision: 202168

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

    PR middle-end/57511
    * tree-scalar-evolution.c (instantiate_scev_name): Allow
    non-linear SCEVs.

    * gcc.dg/tree-ssa/sccp-1.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/sccp-1.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-scalar-evolution.c

[Bug tree-optimization/57511] [4.8 Regression] Missing SCEV final value replacement

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
      Known to work|                            |4.9.0
            Summary|[4.8/4.9 Regression]        |[4.8 Regression] Missing
                   |Missing SCEV final value    |SCEV final value
                   |replacement                 |replacement

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk.  Note that patch requires

2013-09-02  Richard Biener  <rguenther@suse.de>

        * tree-affine.c (add_elt_to_tree): Avoid converting all pointer
        arithmetic to sizetype.

to not regress gcc.dg/tree-ssa/reassoc-19.c which means it isn't suitable
for backporting IMHO.

[Bug tree-optimization/57511] [4.8 Regression] Missing SCEV final value replacement

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.2                       |4.8.3

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.8.2 has been released.

[Bug tree-optimization/57511] [4.8 Regression] Missing SCEV final value replacement

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57511

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.3                       |4.8.4

--- Comment #10 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 4.8.3 is being released, adjusting target milestone.

[Bug tree-optimization/57511] [4.8 Regression] Missing SCEV final value replacement

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57511

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|4.8.4                       |4.9.0
      Known to fail|                            |4.8.4

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed for 4.9, not backporting for said reasons and dependencies.

[Bug tree-optimization/57511] [4.8 Regression] Missing SCEV final value replacement

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57511

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

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

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
*** Bug 58122 has been marked as a duplicate of this bug. ***