[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[pinskia at gcc dot gnu.org]

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

--- Comment #23 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-10-19 19:10:38 UTC ---
The other way to handle this is to allow unswitch loops to handle non inner
loops which from what I can tell is a two line patch.

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenther at suse dot de]

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

--- Comment #24 from rguenther at suse dot de <rguenther at suse dot de> 2011-10-20 07:43:44 UTC ---
On Wed, 19 Oct 2011, pinskia at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23855
> 
> --- Comment #23 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-10-19 19:10:38 UTC ---
> The other way to handle this is to allow unswitch loops to handle non inner
> loops which from what I can tell is a two line patch.

Though unswitching is too late for loop invariant motion to work here.

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schwab@linux-m68k.org

--- Comment #25 from Richard Biener <rguenth at gcc dot gnu.org> 2012-12-07 10:11:58 UTC ---
*** Bug 55187 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #11231|0                           |1
        is obsolete|                            |
           Assignee|rakdver at gcc dot gnu.org         |rguenth at gcc dot gnu.org

--- Comment #26 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 32049
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32049&action=edit
updated patch

Updated the patch to trunk.

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenth at gcc dot gnu.org]

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

--- Comment #27 from Richard Biener <rguenth at gcc dot gnu.org> ---
Some more TLC to be applied before it's ready for prime time (and obviously
testing).  Eventually integrating with LIM sounds better?

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenth at gcc dot gnu.org]

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

--- Comment #28 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 32051
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=32051&action=edit
updated patch

Slight update to apply all possible hoists to PR60042.

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[pinskia at gcc dot gnu.org]

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

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

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

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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[dberlin at gcc dot gnu dot org]

------- Comment #22 from dberlin at gcc dot gnu dot org  2006-10-24 14:23 -------
(In reply to comment #19)
> So it is indeed chicken and egg ;)  load-PRE does not PRE the loads if the loop
> is not in do-while form, and we won't hoist the loop header copies until the
> loads are PREd.  As to comment #13, if we are able to "clean" the two innermost
> loops
> of a nest that is already a good improvement.  Though from all the experiments
> it looks like it is advisable to write do-while loops with hoisted loop header
> copies manually rather than for loops.
> 

So the PRE fixes i've got should help here, i think.
Maybe not.
:)


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rakdver at gcc dot gnu dot org]

------- Comment #21 from rakdver at gcc dot gnu dot org  2006-10-24 13:58 -------
(In reply to comment #20)
> So, where do we want to go?
> 

Unless the basic patch is approved (which did not happen so far, despite of
several pings), I do not know.  I will try to resend the patch, perhaps that
will help.


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenth at gcc dot gnu dot org]

------- Comment #20 from rguenth at gcc dot gnu dot org  2006-10-24 13:56 -------
So, where do we want to go?


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenth at gcc dot gnu dot org]

------- Comment #19 from rguenth at gcc dot gnu dot org  2006-04-10 11:56 -------
So it is indeed chicken and egg ;)  load-PRE does not PRE the loads if the loop
is not in do-while form, and we won't hoist the loop header copies until the
loads are PREd.  As to comment #13, if we are able to "clean" the two innermost
loops
of a nest that is already a good improvement.  Though from all the experiments
it looks like it is advisable to write do-while loops with hoisted loop header
copies manually rather than for loops.


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #18 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-04-10 10:24 -------
Subject: Re:  loop header should also be pulled out of the inner loop too

> > > actually, thinking about it again, it should suffice to teach
> > > invariant_without_guard_p about invariant memory loads, and this should just
> > > work.
> > 
> > It basically does, the only other problem is that we are not able to determine
> > that the outer loop is not infinite.
> 
> It that because we don't recognize the condition of the loop header?  

the problem is that we use # of iterations analysis, and it tries to
fully instantiate the scalar evolutions, which is impossible for *je.


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenther at suse dot de]

------- Comment #17 from rguenther at suse dot de  2006-04-10 08:10 -------
Subject: Re:  loop header should also be pulled
 out of the inner loop too

On Mon, 9 Apr 2006, rakdver at gcc dot gnu dot org wrote:

> (In reply to comment #14)
> > (In reply to comment #11)
> > > I updated the patch for current mainline, but it still has issues for some
> > > common uses of loops:
> > > 
> > > void foo(int *ie, int *je, double *x)
> > > {
> > >   int i, j;
> > >   for (j=0; j<*je; ++j)
> > >     for (i=0; i<*ie; ++i)
> > >       x[i+j] = 0.0;
> > > }
> > > 
> > > After loop header copying we have
> > > 
> > >   if (*je > 0)
> > >     for (j=0; j<*je; ++j)
> > >       if (*ie > 0)
> > >         for (i=0; i<*ie; ++i)
> > >           x[i+j ] = 0.0;
> > > 
> > > note how in this form we see the condition *ie > 0 not invariant wrt the
> > > outer loop (because it does a memory load), but if we would run load-PRE
> > > between loop header copying and guard hoisting we would get
> > 
> > actually, thinking about it again, it should suffice to teach
> > invariant_without_guard_p about invariant memory loads, and this should just
> > work.
> 
> It basically does, the only other problem is that we are not able to determine
> that the outer loop is not infinite.

It that because we don't recognize the condition of the loop header?  
Otherwise we know that *je > 0 and the loop runs from 0 to *je (in fact,
I have loop determine the number of iterations of the loop to be *je).  Of
course this is with load-PRE moving the load before the loop-header and 
thus SCEV being presented with

   D.xxx = *je;
   if (D.xxx > 0)
     for (j=0; j<D.xxx; ++j)
      ...

which it just handles fine.  It looks like a chicken-and-egg problem ;)

Richard.


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rakdver at gcc dot gnu dot org]

------- Comment #16 from rakdver at gcc dot gnu dot org  2006-04-10 00:03 -------
Created an attachment (id=11231)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=11231&action=view)
Updated version of the patch, also handling invariant memory references


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rakdver at gcc dot gnu dot org]

------- Comment #15 from rakdver at gcc dot gnu dot org  2006-04-09 23:51 -------
(In reply to comment #14)
> (In reply to comment #11)
> > I updated the patch for current mainline, but it still has issues for some
> > common uses of loops:
> > 
> > void foo(int *ie, int *je, double *x)
> > {
> >   int i, j;
> >   for (j=0; j<*je; ++j)
> >     for (i=0; i<*ie; ++i)
> >       x[i+j] = 0.0;
> > }
> > 
> > After loop header copying we have
> > 
> >   if (*je > 0)
> >     for (j=0; j<*je; ++j)
> >       if (*ie > 0)
> >         for (i=0; i<*ie; ++i)
> >           x[i+j ] = 0.0;
> > 
> > note how in this form we see the condition *ie > 0 not invariant wrt the
> > outer loop (because it does a memory load), but if we would run load-PRE
> > between loop header copying and guard hoisting we would get
> 
> actually, thinking about it again, it should suffice to teach
> invariant_without_guard_p about invariant memory loads, and this should just
> work.

It basically does, the only other problem is that we are not able to determine
that the outer loop is not infinite.


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rakdver at gcc dot gnu dot org]

------- Comment #14 from rakdver at gcc dot gnu dot org  2006-04-07 13:20 -------
(In reply to comment #11)
> I updated the patch for current mainline, but it still has issues for some
> common uses of loops:
> 
> void foo(int *ie, int *je, double *x)
> {
>   int i, j;
>   for (j=0; j<*je; ++j)
>     for (i=0; i<*ie; ++i)
>       x[i+j] = 0.0;
> }
> 
> After loop header copying we have
> 
>   if (*je > 0)
>     for (j=0; j<*je; ++j)
>       if (*ie > 0)
>         for (i=0; i<*ie; ++i)
>           x[i+j ] = 0.0;
> 
> note how in this form we see the condition *ie > 0 not invariant wrt the
> outer loop (because it does a memory load), but if we would run load-PRE
> between loop header copying and guard hoisting we would get

actually, thinking about it again, it should suffice to teach
invariant_without_guard_p about invariant memory loads, and this should just
work.


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Comment #13 from rakdver at atrey dot karlin dot mff dot cuni dot cz  2006-04-07 12:57 -------
Subject: Re:  loop header should also be pulled out of the inner loop too

> I updated the patch for current mainline, but it still has issues for some
> common uses of loops:
> 
> void foo(int *ie, int *je, double *x)
> {
>   int i, j;
>   for (j=0; j<*je; ++j)
>     for (i=0; i<*ie; ++i)
>       x[i+j] = 0.0;
> }
> 
> After loop header copying we have
> 
>   if (*je > 0)
>     for (j=0; j<*je; ++j)
>       if (*ie > 0)
>         for (i=0; i<*ie; ++i)
>           x[i+j ] = 0.0;
> 
> note how in this form we see the condition *ie > 0 not invariant wrt the
> outer loop (because it does a memory load), but if we would run load-PRE
> between loop header copying and guard hoisting we would get
> 
>   pretmp.1 = *je;
>   if (pretmp.1 > 0)
>     pretmp.2 = *ie;
>     for (j=0; j<pretmp.1; ++j)
>       if (pretmp.2 > 0)
>         for (i=0; i<pretmp.2; ++i)
>           x[i+j] = 0.0;
> 
> which would enable us to hoist the guard out of the outer loop.

this is somewhat problematic; it would work for 2 nested loops, but not
for 3 or more (one would need to iterate guard hoisting & invariant
motion or PRE for that).  It would be possible to integrate guard hoisting
into the loop invariant motion pass, I may give it a try.


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2006-04-07 12:01 -------
So what I now have is (ahh, a PROP_loops would be so nice...)

  pass_ch
  pass_split_crit_edges
  pass_pre
  [cfg_cleanup to re-merge critical edges]
  pass_hoist_guards

which works nice for this scenario, still without an extra load-PRE pass we
have
memory loads that were only PREd out of the inner loop (due to the not hoisted
guard) inside the outer loop, even if they're now redundant.

Which makes me wonder, if PRE could do loop-header-FRE here?  Danny?  Has such
been done before?  Basically you have

do {
  if (*mem > 0)
    {
      i = 0;
      do {
      } while (*mem > i);
    }
} while (...);

where the (*mem > 0) is (full or partially?) redundant.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dberlin at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2006-04-07 11:34 -------
I updated the patch for current mainline, but it still has issues for some
common uses of loops:

void foo(int *ie, int *je, double *x)
{
  int i, j;
  for (j=0; j<*je; ++j)
    for (i=0; i<*ie; ++i)
      x[i+j] = 0.0;
}

After loop header copying we have

  if (*je > 0)
    for (j=0; j<*je; ++j)
      if (*ie > 0)
        for (i=0; i<*ie; ++i)
          x[i+j ] = 0.0;

note how in this form we see the condition *ie > 0 not invariant wrt the
outer loop (because it does a memory load), but if we would run load-PRE
between loop header copying and guard hoisting we would get

  pretmp.1 = *je;
  if (pretmp.1 > 0)
    pretmp.2 = *ie;
    for (j=0; j<pretmp.1; ++j)
      if (pretmp.2 > 0)
        for (i=0; i<pretmp.2; ++i)
          x[i+j] = 0.0;

which would enable us to hoist the guard out of the outer loop.


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[patchapp at dberlin dot org]

------- Comment #10 from patchapp at dberlin dot org  2006-02-28 18:15 -------
Subject: Bug number PR23855

A patch for this bug has been added to the patch tracker.
The mailing list url for the patch is
http://gcc.gnu.org/ml/gcc-patches/2006-01/msg01424.html


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rakdver at gcc dot gnu dot org]

------- Comment #9 from rakdver at gcc dot gnu dot org  2006-01-20 23:56 -------
Patch:

http://gcc.gnu.org/ml/gcc-patches/2006-01/msg01424.html


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |http://gcc.gnu.org/ml/gcc-
                   |                            |patches/2006-
                   |                            |01/msg01424.html
           Keywords|                            |patch


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rakdver at gcc dot gnu dot org]

-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rakdver at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[rakdver at gcc dot gnu dot org]

------- Comment #8 from rakdver at gcc dot gnu dot org  2006-01-15 20:15 -------
Unswitching the condition (i < ie) (plus empty loop removal) would produce this
code.  Nevertheless, this is a fairly common case, so perhaps it might make
sense to special-case it in loop header copying (for performance reasons).


-- 


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2006-01-15 20:12 -------
Oh, that was PR 23970.

And I had meant:
void bar(void);
void foo(int ie, int je)
{
  int i, j;
  if (0<je && 0 <ie)
  {
  j = 0;
  do {
   i  =0;
  do {
      bar();
    i++;
  } while (i < ie);
  j++;
  } while (j < ie);
  }
}


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |23970
              nThis|                            |


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

[Bug tree-optimization/23855] loop header should also be pulled out of the inner loop too

[pinskia at gcc dot gnu dot org]

------- Comment #6 from pinskia at gcc dot gnu dot org  2006-01-15 20:08 -------
What really should happen is that we should change the loop to be something
like which helps a different bug too (I cannot find it right now but it has to
do with pulling stuff out of the loops):
void bar(void);
void foo(int ie, int je)
{
  int i, j;
  if (0<je && 0 <ie)
  {
  j = 0;
  do {
  do {
   i  =0;
      bar(); 
    i++;
  } while (i < ie);
  j++;
  } while (j < ie);
}


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2006-01-15 20:08:39
               date|                            |
            Summary|Should not do loop header   |loop header should also be
                   |copying for inner loop      |pulled out of the inner loop
                   |                            |too


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