[Bug tree-optimization/18754] New: unrolling happens too late/SRA does not happen late enough

[Bug tree-optimization/18754] New: unrolling happens too late/SRA does not happen late enough

[pinskia at gcc dot gnu dot org]

Take the following code:
struct X { float array[4]; };

X a,b;

float foobar () {
  float s = 0;
  X c;
  for (unsigned int d=0; d<4; ++d)
    c.array[d] = a.array[d] * b.array[d];
  for (unsigned int d=0; d<4; ++d)
    s+=c.array[d];
  return s;
}

With -O3 -funroll-loops -fno-ivopts -ffast-math (the fno-ivopts is because there are some ADDR_EXPR 
which we don't mark as invariant/constant which I will file in another bug) we get in .vars:
  c.array[0] = a.array[0] * b.array[0];
  c.array[1] = a.array[1] * b.array[1];
  c.array[2] = a.array[2] * b.array[2];
  D.1572 = a.array[3] * b.array[3];
  c.array[3] = D.1572;
  return D.1572 + c.array[0] + c.array[1] + c.array[2];

Note how we could SRA c.array.

-- 
           Summary: unrolling happens too late/SRA does not happen late
                    enough
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: missed-optimization, TREE
          Severity: enhancement
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-06 05:01 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-12-06 05:01:09
               date|                            |


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[rguenth at tat dot physik dot uni-tuebingen dot de]

------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2004-12-16 17:08 -------
The attached patch makes us for -O3 -funroll-loops -ffast-math produce in .vars

float foobar() ()
{
<bb 0>:
  return a.array[3] * b.array[3] + a.array[2] * b.array[2] + a.array[0] *
b.array[0] + a.array[1] * b.array[1];

}

though the assembly is as good as before.

-- 


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[rguenth at tat dot physik dot uni-tuebingen dot de]

------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2005-01-20 10:57 -------
This is also somewhat related to PR19401 as we do not unroll loops completely
with just -O2 at the moment, which is important for the second testcase.

-- 


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-20 14:49 -------
Note PR 18755 blocks this if we go the SRA after loop optimization which seems like a better idea.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |18755


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[rguenth at tat dot physik dot uni-tuebingen dot de]

------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2005-01-20 14:57 -------
Subject: Re:  unrolling happens too late/SRA
 does not happen late enough

> Note PR 18755 blocks this if we go the SRA after loop optimization which
> seems like a better idea.

I do not completely understand this sentence ;)  I argue that SRA after
loop is a bad idea, because SRA, in my testcases, will expose new
oportunities for selecting ivs, so we'll need to run another loop after
SRA.  So I chose for

  loop0
  sra
  loop

instead of

  sra
  loop
  sra
  loop

which is one pass less.  Also with -ftree-early-loop-optimize we get
in .vars for PR18755:

;; Function float foobar() (_Z6foobarv)

float foobar() ()
{
<bb 0>:
  return a.array[3] * b.array[3] + b.array[2] * a.array[2] + b.array[1] *
a.array[1] + a.array[0] * b.array[0] + 0.0;

}

which is what we want?  Or do we now just paper over another problem here?

I'm confused...

Richard.



-- 


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-01-20 15:06 -------
Subject: Re:  unrolling happens too late/SRA
 does not happen late enough



On Thu, 20 Jan 2005, rguenth at tat dot physik dot uni-tuebingen dot de wrote:

>
> ------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2005-01-20 14:57 -------
> Subject: Re:  unrolling happens too late/SRA
> does not happen late enough
>
>> Note PR 18755 blocks this if we go the SRA after loop optimization which
>> seems like a better idea.
>
> I do not completely understand this sentence ;)  I argue that SRA after
> loop is a bad idea, because SRA, in my testcases, will expose new
> oportunities for selecting ivs, so we'll need to run another loop after
> SRA.

Wiat, why are we running SRA twice again at all?
I can't figure this out from the bug report, other than seeing that we 
"could sra c.array", but i don't see why that requires a loop opt first.

If you are just trying to convince it that constant indexed accesses to 
each prat of that array is actually a different element, the 
structure-aliasing branch will help (though not quite yet, because i've 
punted on array_ref until i add the code to not punt when we have constant 
indexed array_ref)


-- 


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-20 15:07 -------
(In reply to comment #9)
> Subject: Re:  unrolling happens too late/SRA
>  does not happen late enough
> 
> which is what we want?  Or do we now just paper over another problem here?

Yes you are paper over another problem.  The point is ivopts and unroll are interacting badly here, how 
I don't know, but unroll is not marking the new ADDR_EXPR as invariant which causes the problem I am 
see. No SRA should happen after loop.  Nothing else at least for the current time. Loop setup is too 
slow at this point.  Once we have more and more optimizations which keep uptodate the loop structors 
we can do an early unrolling.

-- 


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[rguenth at tat dot physik dot uni-tuebingen dot de]

------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2005-01-20 15:15 -------
Subject: Re:  unrolling happens too late/SRA
 does not happen late enough

On 20 Jan 2005, dberlin at dberlin dot org wrote:

> Wiat, why are we running SRA twice again at all?
> I can't figure this out from the bug report, other than seeing that we
> "could sra c.array", but i don't see why that requires a loop opt first.

We don't run sra twice.  But an early loop unrolling will change f.i.

  for (unsigned int d=0; d<4; ++d)
    c.array[d] = a.array[d] * b.array[d];

to

    c.array[0] = a.array[0] * b.array[0];
    c.array[1] = a.array[1] * b.array[1];
    c.array[2] = a.array[2] * b.array[2];
    c.array[3] = a.array[3] * b.array[3];

and SRA can only scalarize this variant, not if the loop is still
there.  That's the whole point of the loop<->sra ordering problem.
And of course sra may then expose new interesting choices for iv's
of outer loops - at least I think.

Richard.

--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/



-- 


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[rguenth at tat dot physik dot uni-tuebingen dot de]

------- Additional Comments From rguenth at tat dot physik dot uni-tuebingen dot de  2005-01-21 16:07 -------
Experimenting with SRA inside loop together with cleanup passes after
cunroll/sra didn't reveal anything good - even with loop cfg_cleanup patched in.
 See thread starting at http://gcc.gnu.org/ml/gcc-patches/2005-01/msg01315.html

-- 


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[pinskia at gcc dot gnu dot org]

-- 
Bug 18754 depends on bug 18755, which changed state.

Bug 18755 Summary: invariant/constant not recomputed when ADDR_EXPR changed
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18755

           What    |Old Value                   |New Value
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED

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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[rguenth at gcc dot gnu dot org]

------- Comment #21 from rguenth at gcc dot gnu dot org  2008-04-27 17:16 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.4.0


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[rguenth at gcc dot gnu dot org]

------- Comment #20 from rguenth at gcc dot gnu dot org  2008-04-27 16:27 -------
Subject: Bug 18754

Author: rguenth
Date: Sun Apr 27 16:27:08 2008
New Revision: 134730

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=134730
Log:
2008-04-27  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/18754
        PR tree-optimization/34223
        * tree-pass.h (pass_complete_unrolli): Declare.
        * tree-ssa-loop-ivcanon.c (try_unroll_loop_completely): Print
        loop size before and after unconditionally of UL_NO_GROWTH in effect.
        Rewrite loop into loop closed SSA form if it is not already.
        (tree_unroll_loops_completely): Re-structure to iterate over
        innermost loops with intermediate CFG cleanups.
        Unroll outermost loops only if requested or the code does not grow
        doing so.
        * tree-ssa-loop.c (gate_tree_vectorize): Don't shortcut if no
        loops are available.
        (tree_vectorize): Instead do so here.
        (tree_complete_unroll): Also unroll outermost loops.
        (tree_complete_unroll_inner): New function.
        (gate_tree_complete_unroll_inner): Likewise.
        (pass_complete_unrolli): New pass.
        * tree-ssa-loop-manip.c (find_uses_to_rename_use): Only record
        uses outside of the loop.
        (tree_duplicate_loop_to_header_edge): Only verify loop-closed SSA
        form if it is available.  
        * tree-flow.h (tree_unroll_loops_completely): Add extra parameter.
        * passes.c (init_optimization_passes): Schedule complete inner
        loop unrolling pass before the first CCP pass after final inlining.

        * gcc.dg/tree-ssa/loop-36.c: New testcase.
        * gcc.dg/tree-ssa/loop-37.c: Likewise.
        * gcc.dg/vect/vect-118.c: Likewise.
        * gcc.dg/Wunreachable-8.c: XFAIL bogus warning.
        * gcc.dg/vect/vect-66.c: Increase loop trip count.
        * gcc.dg/vect/no-section-anchors-vect-66.c: Likewise.
        * gcc.dg/vect/no-section-anchors-vect-69.c: Likewise.
        * gcc.dg/vect/vect-76.c: Likewise.
        * gcc.dg/vect/vect-outer-6.c: Likewise.
        * gcc.dg/vect/vect-outer-1.c: Likewise.
        * gcc.dg/vect/vect-outer-1a.c: Likewise.
        * gcc.dg/vect/vect-11a.c: Likewise.
        * gcc.dg/vect/vect-shift-1.c: Likewise.
        * gcc.target/i386/vectorize1.c: Likewise.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-36.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-37.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-118.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/passes.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/Wunreachable-8.c
    trunk/gcc/testsuite/gcc.dg/vect/no-section-anchors-vect-66.c
    trunk/gcc/testsuite/gcc.dg/vect/no-section-anchors-vect-69.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-11a.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-66.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-76.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-outer-1.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-outer-1a.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-outer-6.c
    trunk/gcc/testsuite/gcc.dg/vect/vect-shift-1.c
    trunk/gcc/testsuite/gcc.target/i386/vectorize1.c
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-pass.h
    trunk/gcc/tree-ssa-loop-ivcanon.c
    trunk/gcc/tree-ssa-loop-manip.c
    trunk/gcc/tree-ssa-loop.c


-- 


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[rguenth at gcc dot gnu dot org]

------- Comment #19 from rguenth at gcc dot gnu dot org  2008-04-22 09:31 -------
Mine.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-08-12 16:58:50         |2008-04-22 09:31:17
               date|                            |


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[belyshev at depni dot sinp dot msu dot ru]

------- Comment #18 from belyshev at depni dot sinp dot msu dot ru  2007-08-12 16:58 -------
Another test for this bug:

/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-final_cleanup" } */

extern void link_error (void);
static const int my_array [3] = { 4, 5, 6 };

void f0 (void)
{
  int j, sum = 0;
  for (j = 0; j < 3; j ++)
    sum += my_array [j];
  if (15 != sum)
    link_error ();
}

int f1 (int a [])
{
  int j, sum = 0;
  for (j = 0; j < 3; j ++)
    sum += a [j] + my_array [j];
  return sum;
}

/* { dg-final { scan-tree-dump-not "link_error" "final_cleanup" } } */
/* { dg-final { scan-tree-dump-not "my_array" "final_cleanup" } } */
/* { dg-final { cleanup-tree-dump "final_cleanup" } } */


-- 

belyshev at depni dot sinp dot msu dot ru changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2005-12-21 03:50:49         |2007-08-12 16:58:50
               date|                            |


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[pinskia at gcc dot gnu dot org]

------- Comment #17 from pinskia at gcc dot gnu dot org  2007-02-10 09:40 -------
*** Bug 30697 has been marked as a duplicate of this bug. ***


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |stefaan dot deroeck at gmail
                   |                            |dot com


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[rguenth at gcc dot gnu dot org]

------- Comment #16 from rguenth at gcc dot gnu dot org  2006-03-06 14:30 -------
Or with a pass recovering loops before vectorization.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |22501
              nThis|                            |


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

[Bug tree-optimization/18754] unrolling happens too late/SRA does not happen late enough

[pinskia at gcc dot gnu dot org]

------- Comment #15 from pinskia at gcc dot gnu dot org  2006-03-05 21:27 -------
Oh, the one thing we would miss with unrolling early is some vectorization. 
That could be fixed with a basic block vectorizer.


-- 


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