[tree-ssa] Dce & infinite loops

[tree-ssa] Dce & infinite loops

[Zdenek Dvorak]

Hello,

I may be wrong, but IIRC it is incorrect to remove infinite loops, as
happens currently for example for the following code:

int main(void)
{
  unsigned i;

  for (i = 1; i != 0; i+=2);

  return 0;
}

Zdenek

Re: [tree-ssa] Dce & infinite loops

[Paolo Carlini]

Zdenek Dvorak wrote:

>Hello,
>
>I may be wrong, but IIRC it is incorrect to remove infinite loops, as
>happens currently for example for the following code:
>  
>
Hi Zdenek, a naive reply: I'm almost sure to remember messages pointing
out that in fact we don't want to remove infinite loop and even finite but
redundant ones (empty body).

I will try to dig out something from the archive.

Paolo.

Re: [tree-ssa] Dce & infinite loops

[Steven Bosscher]

On Thursday 18 March 2004 13:21, Zdenek Dvorak wrote:
> Hello,
>
> I may be wrong, but IIRC it is incorrect to remove infinite loops, as
> happens currently for example for the following code:
>
> int main(void)
> {
>   unsigned i;
>
>   for (i = 1; i != 0; i+=2);
>
>   return 0;
> }

Removing an infinte loop is indeed wrong.  Hence this comment
in tree-ssa-dce.c:

  /* Some blocks don't have an immediate post dominator.  This can happen
     for example with infinite loops.  Removing an infinite loop is an
     inappropriate transformation anyway...  */

If we remove that infinite loop, you found a bug.

Gr.
Steven

Re: [tree-ssa] Dce & infinite loops

[Zdenek Dvorak]

Hello,

> > I may be wrong, but IIRC it is incorrect to remove infinite loops, as
> > happens currently for example for the following code:
> >
> > int main(void)
> > {
> >   unsigned i;
> >
> >   for (i = 1; i != 0; i+=2);
> >
> >   return 0;
> > }
> 
> Removing an infinte loop is indeed wrong.  Hence this comment
> in tree-ssa-dce.c:
> 
>   /* Some blocks don't have an immediate post dominator.  This can happen
>      for example with infinite loops.  Removing an infinite loop is an
>      inappropriate transformation anyway...  */
> 
> If we remove that infinite loop, you found a bug.

the problem is that the loop in the example above has an exit (that is
never taken); therefore the code in tree-ssa-dce.c you cite does not
handle it.

Zdenek

Re: [tree-ssa] Dce & infinite loops

[Steven Bosscher]

On Thursday 18 March 2004 13:34, Zdenek Dvorak wrote:
> Hello,
>
> > > I may be wrong, but IIRC it is incorrect to remove infinite loops, as
> > > happens currently for example for the following code:
> > >
> > > int main(void)
> > > {
> > >   unsigned i;
> > >
> > >   for (i = 1; i != 0; i+=2);
> > >
> > >   return 0;
> > > }
> >
> > Removing an infinte loop is indeed wrong.  Hence this comment
> > in tree-ssa-dce.c:
> >
> >   /* Some blocks don't have an immediate post dominator.  This can happen
> >      for example with infinite loops.  Removing an infinite loop is an
> >      inappropriate transformation anyway...  */
> >
> > If we remove that infinite loop, you found a bug.
>
> the problem is that the loop in the example above has an exit (that is
> never taken); therefore the code in tree-ssa-dce.c you cite does not
> handle it.

I know, and I'm not sure how to deal with this.  It seems kind of silly
to need something like IV/loop analysis to decide whether or not some
code is dead.  What do other compilers do with your example?

Gr.
Steven

Re: [tree-ssa] Dce & infinite loops

[Zdenek Dvorak]

Hello,

> > > > I may be wrong, but IIRC it is incorrect to remove infinite loops, as
> > > > happens currently for example for the following code:
> > > >
> > > > int main(void)
> > > > {
> > > >   unsigned i;
> > > >
> > > >   for (i = 1; i != 0; i+=2);
> > > >
> > > >   return 0;
> > > > }
> > >
> > > Removing an infinte loop is indeed wrong.  Hence this comment
> > > in tree-ssa-dce.c:
> > >
> > >   /* Some blocks don't have an immediate post dominator.  This can happen
> > >      for example with infinite loops.  Removing an infinite loop is an
> > >      inappropriate transformation anyway...  */
> > >
> > > If we remove that infinite loop, you found a bug.
> >
> > the problem is that the loop in the example above has an exit (that is
> > never taken); therefore the code in tree-ssa-dce.c you cite does not
> > handle it.
> 
> I know, and I'm not sure how to deal with this.  It seems kind of silly
> to need something like IV/loop analysis to decide whether or not some
> code is dead.

the simple conservative solution is to mark all back edges as neccesary.
You can do a bit better and use the results of simple loop analysis to
avoid doing this for back edges of loops for that you are sure that they terminate.
But you won't gain much by this in practice, since people usually do not
write useless loops.  Also it is not clear whether people really want such
loop to be optimized out (they might write it in order to make the
program wait).

Zdenek

Re: [tree-ssa] Dce & infinite loops

[Paolo Carlini]

Zdenek Dvorak wrote:

>But you won't gain much by this in practice, since people usually do not
>write useless loops.  Also it is not clear whether people really want such
>loop to be optimized out (they might write it in order to make the
>program wait).
>  
>
Exactly: these two observations I remember perfectly from that discussion.

Paolo.

RE: [tree-ssa] Dce & infinite loops

[Dave Korn]

> -----Original Message-----
> From: gcc-owner On Behalf Of Paolo Carlini
> Sent: 18 March 2004 13:18

> Zdenek Dvorak wrote:
> 
> >But you won't gain much by this in practice, since people usually do 
> >not write useless loops.  Also it is not clear whether people really 
> >want such loop to be optimized out (they might write it in order to 
> >make the program wait).
> >  
> >
> Exactly: these two observations I remember perfectly from 
> that discussion.
> 
> Paolo.

  AFAIUI, anyone who writes a loop to make a delay is writing
non-standards-compliant code.  If you have a loop like

  for (i = 0; i < very_big_number; i++)
    /* do nothing but delay */ ;

then surely under the "as-if rule", the compiler is completely within its
rights to just replace it with

  i = very_big_number;

and so anyone expecting to get a delay loop is making a false assumption,
isn't it so?

  It's been bad engineering practice for many years now to assume a fixed
relationship between machine cycles and real time; it was OK on the CBM64 to
assume that each instruction was 1us, maybe, but in a world where CPUs range
from 486 to K8 to ppc and SH and beyond, and clocks vary from 50MHz to 3GHz,
and memory subsystems include 1, 2 or even 3 levels of caching..... it's
just borked.

[  I was going to butt into the PCH thread as well and mention that the last
time I coded for a system where you could actually *rely* on loading data
back into memory at the same address you wrote it out from, it was also the
C64.... ]

    cheers, 
      DaveK
-- 
Can't think of a witty .sigline today....

Re: [tree-ssa] Dce & infinite loops

[Geert Bosch]

On Mar 18, 2004, at 08:12, Zdenek Dvorak wrote:
> the simple conservative solution is to mark all back edges as 
> neccesary.
> You can do a bit better and use the results of simple loop analysis to
> avoid doing this for back edges of loops for that you are sure that 
> they terminate.
> But you won't gain much by this in practice, since people usually do 
> not
> write useless loops.  Also it is not clear whether people really want 
> such
> loop to be optimized out (they might write it in order to make the
> program wait).

It is important to remove loops that are empty, but can be shown
to terminate. Even though programmers may not write such code,
other optimizations may make all code invariant, resulting in an
empty loop.

True, long ago GCC did keep such loops, but that policy has been
explicitly reversed later on. If someone wants to keep a loop,
just make sure it has some external effect such as writing to
volatile memory.

I fail to see why you would need to have any special hacks to
prevent infinite loops from being optimized away. What is the
logic that causes this? There seems to be a more fundamental
problem if the optimizers determine that the function would
return 0. What if the loop was replaced with a call to a
function that is marked non-terminating?

   -Geert

Re: [tree-ssa] Dce & infinite loops

[Zdenek Dvorak]

Hello,

> >the simple conservative solution is to mark all back edges as 
> >neccesary.
> >You can do a bit better and use the results of simple loop analysis to
> >avoid doing this for back edges of loops for that you are sure that 
> >they terminate.
> >But you won't gain much by this in practice, since people usually do 
> >not
> >write useless loops.  Also it is not clear whether people really want 
> >such
> >loop to be optimized out (they might write it in order to make the
> >program wait).
> 
> It is important to remove loops that are empty, but can be shown
> to terminate. Even though programmers may not write such code,
> other optimizations may make all code invariant, resulting in an
> empty loop.

how often this happens? More precisely, could I see at least one
real-world example?

> True, long ago GCC did keep such loops, but that policy has been
> explicitly reversed later on. If someone wants to keep a loop,
> just make sure it has some external effect such as writing to
> volatile memory.
> 
> I fail to see why you would need to have any special hacks to
> prevent infinite loops from being optimized away.

These are no special hacks. The problem that was missed here is
that nontermination is (an ugly kind of) side effect.  So there
is no fundamental difference between handling this and handling
any other statement that may cause something observable, except
for the value produced.

Zdenek

> What is the
> logic that causes this? There seems to be a more fundamental
> problem if the optimizers determine that the function would
> return 0. What if the loop was replaced with a call to a
> function that is marked non-terminating?

Re: [tree-ssa] Dce & infinite loops

[Joseph S. Myers]

On Thu, 18 Mar 2004, Zdenek Dvorak wrote:

> > It is important to remove loops that are empty, but can be shown
> > to terminate. Even though programmers may not write such code,
> > other optimizations may make all code invariant, resulting in an
> > empty loop.
> 
> how often this happens? More precisely, could I see at least one
> real-world example?

See the previous discussions that resulted in the change to the section of
the manual explaining why we didn't remove empty loops, e.g.
<http://gcc.gnu.org/ml/gcc/1998-05/msg00651.html> and thread,
<http://gcc.gnu.org/ml/gcc/1998-06/msg00011.html> and (long) thread.  For
example, the example in <http://gcc.gnu.org/ml/gcc/1998-06/msg00089.html>
generates an empty loop just as it did in 1998, and the threads have other
examples.

-- 
Joseph S. Myers
jsm@polyomino.org.uk

Re: [tree-ssa] Dce & infinite loops

[Zdenek Dvorak]

Hello,

> > > It is important to remove loops that are empty, but can be shown
> > > to terminate. Even though programmers may not write such code,
> > > other optimizations may make all code invariant, resulting in an
> > > empty loop.
> > 
> > how often this happens? More precisely, could I see at least one
> > real-world example?
> 
> See the previous discussions that resulted in the change to the section of
> the manual explaining why we didn't remove empty loops, e.g.
> <http://gcc.gnu.org/ml/gcc/1998-05/msg00651.html> and thread,
> <http://gcc.gnu.org/ml/gcc/1998-06/msg00011.html> and (long) thread.  For
> example, the example in <http://gcc.gnu.org/ml/gcc/1998-06/msg00089.html>
> generates an empty loop just as it did in 1998, and the threads have other
> examples.

OK, I may easily extend the loop optimizer to remove empty loops if
there is a demand for it (once dce is fixed so that it is not done
even in cases it is incorrect, as happens now).

Zdenek

Re: [tree-ssa] Dce & infinite loops

[Geert Bosch]

On Mar 18, 2004, at 11:25, Zdenek Dvorak wrote:

> OK, I may easily extend the loop optimizer to remove empty loops if
> there is a demand for it (once dce is fixed so that it is not done
> even in cases it is incorrect, as happens now).
>

How is the loop in your example different from a call to
a non-terminating function returning void? I don't see
why the optimizers would handle that correctly and not
the infinite loop. Could you explain?

   -Geert

Re: [tree-ssa] Dce & infinite loops

[Zdenek Dvorak]

Hello,

> >OK, I may easily extend the loop optimizer to remove empty loops if
> >there is a demand for it (once dce is fixed so that it is not done
> >even in cases it is incorrect, as happens now).
> >
> 
> How is the loop in your example different from a call to
> a non-terminating function returning void? I don't see
> why the optimizers would handle that correctly and not
> the infinite loop. Could you explain?

I had in one of previous mails, but anyway:  for the function we see it
has side effects (nontermination), so we mark it as neccesary.  For the
loop we do not.

The solution is obvious -- mark the backedges of the loops for that we are
not able to prove that they have to terminate as well.

Zdenek

Re: [tree-ssa] Dce & infinite loops

[Steven Bosscher]

On Thursday 18 March 2004 17:34, Zdenek Dvorak wrote:
> Hello,
>
> > >OK, I may easily extend the loop optimizer to remove empty loops if
> > >there is a demand for it (once dce is fixed so that it is not done
> > >even in cases it is incorrect, as happens now).
> >
> > How is the loop in your example different from a call to
> > a non-terminating function returning void? I don't see
> > why the optimizers would handle that correctly and not
> > the infinite loop. Could you explain?
>
> I had in one of previous mails, but anyway:  for the function we see it
> has side effects (nontermination), so we mark it as neccesary.  For the
> loop we do not.
>
> The solution is obvious -- mark the backedges of the loops for that we are
> not able to prove that they have to terminate as well.

If we can eliminate empty loop bodies -- fine with me.  One of the
reasons why cd-dce does better than regular dce is because we kill
such loops.  Yes, they happen.  When I looked at this, there were
about 2 dozen times or so in the test case for PR8361, so they're
not even that uncommon.

Just always removing infinite loops is also not very hard to do.
All we'd need to do is add fake edges for tree DCE.  I decided
against that because I thought that removing infinite loops was
not a valid transformation.  But if it is valid after all, I can
put fake edges in, and all infinite loops will be removed.

For me, the most important thing is consistency.  Right now we
do not remove infinite loops that are infinite because they have
no loop exit, but we do kill infinite loops that are infinite
because the exit condition can never be true.  We should either
remove all infinite loops, or none at all.

Gr.
Steven

Re: [tree-ssa] Dce & infinite loops

[Zdenek Dvorak]

Hello,

> > > >OK, I may easily extend the loop optimizer to remove empty loops if
> > > >there is a demand for it (once dce is fixed so that it is not done
> > > >even in cases it is incorrect, as happens now).
> > >
> > > How is the loop in your example different from a call to
> > > a non-terminating function returning void? I don't see
> > > why the optimizers would handle that correctly and not
> > > the infinite loop. Could you explain?
> >
> > I had in one of previous mails, but anyway:  for the function we see it
> > has side effects (nontermination), so we mark it as neccesary.  For the
> > loop we do not.
> >
> > The solution is obvious -- mark the backedges of the loops for that we are
> > not able to prove that they have to terminate as well.
> 
> If we can eliminate empty loop bodies -- fine with me.  One of the
> reasons why cd-dce does better than regular dce is because we kill
> such loops.  Yes, they happen.  When I looked at this, there were
> about 2 dozen times or so in the test case for PR8361, so they're
> not even that uncommon.
> 
> Just always removing infinite loops is also not very hard to do.
> All we'd need to do is add fake edges for tree DCE.  I decided
> against that because I thought that removing infinite loops was
> not a valid transformation.  But if it is valid after all, I can
> put fake edges in, and all infinite loops will be removed.
> 
> For me, the most important thing is consistency.  Right now we
> do not remove infinite loops that are infinite because they have
> no loop exit, but we do kill infinite loops that are infinite
> because the exit condition can never be true.  We should either
> remove all infinite loops, or none at all.

sorry, this is not up to us -- we must preserve *all* infinite loops to
be correct.  Only if we are able to prove the loop must always terminate
we may remove it.

Zdenek

RE: [tree-ssa] Dce & infinite loops

[Dave Korn]

> -----Original Message-----
> From: gcc-owner On Behalf Of Zdenek Dvorak
> Sent: 18 March 2004 17:00

> > For me, the most important thing is consistency.  Right now 
> we do not 
> > remove infinite loops that are infinite because they have no loop 
> > exit, but we do kill infinite loops that are infinite 
> because the exit 
> > condition can never be true.  We should either remove all infinite 
> > loops, or none at all.
> 
> sorry, this is not up to us -- we must preserve *all* 
> infinite loops to be correct.  Only if we are able to prove 
> the loop must always terminate we may remove it.
> 
> Zdenek

  This discussion is becoming confused, owing to a lack of clarity in
people's posts: we must all take more care to be clear about the distinction
between finite and _in_finite loops.

  Removing an empty loop BODY (but keeping the actual loop) is always valid.

  Removing the body of a FINITE loop and just emitting code to perform the
side-effects is also always valid.

  Removing an INFINITE loop is NEVER valid, regardless of the content of its
body, because the program flow should never get past an INfinite loop.

    cheers, 
      DaveK
-- 
Can't think of a witty .sigline today....

Re: [tree-ssa] Dce & infinite loops

[Dale Johannesen]

On Mar 18, 2004, at 8:25 AM, Zdenek Dvorak wrote:
>
> OK, I may easily extend the loop optimizer to remove empty loops if
> there is a demand for it (once dce is fixed so that it is not done
> even in cases it is incorrect, as happens now).

I think it is a good idea.  In the past I've been on RMS's side in this
matter (don't remove them under the assumption that users put it
there for a reason), but enough people inside Apple have asked
for empty loops to be removed that I'm ready to change my mind.
If there is controversy, it might be conditionalized on 
-fremove-empty-loops
or something like that.

Of course this refers only to finite empty loops; infinite ones cannot
be removed, as several people have said.  (As a semi-practical
matter, you can use these to wait for an external signal from ^C
or the like.)

Re: [tree-ssa] Dce & infinite loops

[Alex Rosenberg]

On Mar 18, 2004, at 9:47 AM, Dale Johannesen wrote:

> Of course this refers only to finite empty loops; infinite ones cannot
> be removed, as several people have said.  (As a semi-practical
> matter, you can use these to wait for an external signal from ^C
> or the like.)

One cause of infinite loops is a common error:

while (!flag) { }

where flag should have been declared volatile.

For that reason, I'd like to see a warning when the compiler sees a 
trivially reduced infinite loop (L1: goto L1) in some later pass.

+------------------------------------------------------------+
| Alexander M. Rosenberg           <mailto:alexr@_spies.com> |
| Nobody cares what I say. Remove the underscore to mail me. |

Re: [tree-ssa] Dce & infinite loops

[Diego Novillo]

On Thu, 2004-03-18 at 07:31, Steven Bosscher wrote:

> Removing an infinte loop is indeed wrong.  Hence this comment
> in tree-ssa-dce.c:
> 
>   /* Some blocks don't have an immediate post dominator.  This can happen
>      for example with infinite loops.  Removing an infinite loop is an
>      inappropriate transformation anyway...  */
> 
> If we remove that infinite loop, you found a bug.
> 
I've always hated this custom.  Is this a language mandate?  Or just
"we've always done it this way"?  Why not tell the user to use a
volatile index variable if they want the infinite loop?


Diego.

Re: [tree-ssa] Dce & infinite loops

[Richard Henderson]

On Thu, Mar 18, 2004 at 09:31:39AM -0500, Diego Novillo wrote:
> I've always hated this custom.  Is this a language mandate?  Or just
> "we've always done it this way"?

The later.  Lets stop this madness.


r~

Re: [tree-ssa] Dce & infinite loops

[Diego Novillo]

On Thu, 2004-03-18 at 11:26, Richard Henderson wrote:
> On Thu, Mar 18, 2004 at 09:31:39AM -0500, Diego Novillo wrote:
> > I've always hated this custom.  Is this a language mandate?  Or just
> > "we've always done it this way"?
> 
> The later.  Lets stop this madness.
> 
*shrug*  I don't really care, but we had better have some empty loop
protection code then.  Apparently what we have now is not enough.


Diego.

Re: [tree-ssa] Dce & infinite loops

[Geert Bosch]

On Mar 18, 2004, at 11:26, Richard Henderson wrote:
> On Thu, Mar 18, 2004 at 09:31:39AM -0500, Diego Novillo wrote:
>> I've always hated this custom.  Is this a language mandate?  Or just
>> "we've always done it this way"?
>
> The later.  Lets stop this madness.

Richard, Diego was talking about removing infinite loops.
Of course this is an invalid transformation and I'm surprised
that anyone would think otherwise. Whether a program halts or
not  is the fundamental outcome of running it.

   -Geert

Re: [tree-ssa] Dce & infinite loops

[Richard Guenther]

On Thu, 2004-03-18 at 07:31, Steven Bosscher wrote:

> Removing an infinte loop is indeed wrong.  Hence this comment
> in tree-ssa-dce.c:
>
>   /* Some blocks don't have an immediate post dominator.  This can
happen
>      for example with infinite loops.  Removing an infinite loop is an
>      inappropriate transformation anyway...  */
>
> If we remove that infinite loop, you found a bug.
>

Diego wrote:
> I've always hated this custom.  Is this a language mandate?  Or just
> "we've always done it this way"?  Why not tell the user to use a
> volatile index variable if they want the infinite loop?

People - you may never remove infinite loops because that would change
program behavior for f.i.:

int main() {
  printf("1");
  for (;;) ;
  printf("1");
  return 0;
}

The "best" (or worst to someone for sure) would be, if the C standard says
infinite loops result in undefined behavior (as program never terminates),
to reject the program.  But never silently delete them.

For optimizing away empty (but finite) loops, this is certainly correct,
though maybe not what Joe average kernel hacker would expect ;) I.e.
issuing a warning if doing that is highly appreciated.

Richard.

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

Re: [tree-ssa] Dce & infinite loops

[Paolo Carlini]

Richard Guenther wrote:

>For optimizing away empty (but finite) loops, this is certainly correct,
>though maybe not what Joe average kernel hacker would expect ;) I.e.
>issuing a warning if doing that is highly appreciated.
>  
>
I find important this point about warnings because a loop may be written 
as not
empty, then become empty as a result of previous optimizations: this may
become quite common thanks to the new powerful SSA machineries.

But this is a general issue, I think: some optimizations (the 
"interesting" ones?)
may happen only thanks to previous optimizations and feedback to the user in
the "dangerous" (and "unexpected"!) cases is appreciated, isn't it?

Or just put everything under -ffast-math or something similar?

Something we lack, perhaps, is -fast, not just -ffast-math, which is not 
really
the same thing as this kind of interesting discussion shows!

Paolo.