Re: [PATCH] Remove empty loop with assumed finiteness (PR tree-optimization/89713)

[Richard Biener <richard.guenther@gmail.com>]

On Sat, May 18, 2019 at 4:00 PM Marc Glisse <marc.glisse@inria.fr> wrote:
>
> (@Feng Xue, it is better to include testcases in your patches)
>
> >> I'm not a big fan of this patch.  I'd rather be looking at either
> >> improving our analysis
>
> Better analysis cannot hurt.
>
> >> or adding attributes to the loops to help the analysis bits prove
> >> termination.
>
> There may not be a loop in the source code, it may be a recursive function
> call that gcc turned into a loop. Plus, I know that it applies to all
> loops in my program.
>
> We could have a function to compute the length of a linked list:
> struct A { A*p; };
> unsigned l(A*a){return a?l(a->p)+1:0;}
>
> and because of other optimizations, it turns out that we do not actually
> use this length
> void g(A*a){l(a);}
>
> wouldn't it be nice if gcc could remove all that useless code, instead of
> keeping a useless loop on the off chance that it might be infinite?
>
> > And we had sth similar in the past and ended up removing it. -funsafe-loop-optimizations IIRC.
>
> IIUC that was slightly different: "This option tells the loop optimizer to
> assume that loop indices do not overflow, and that loops with nontrivial
> exit condition are not infinite."
>
> The assumption on indices looks unsafe indeed if it applied to unsigned
> indices in non-empty loops.

The question is of couse what a "nontrivial exit condition" is.  Indeed
the general handling of unsigned wrapping was what made the option
useless in practice.

But we thoroughly need to specify "nontrivial exit condition", if going
as far as non-constant exit condition, that is, only do {} while (1) is required
to be detected as infinite then this breaks down to unsigned wrapping IVs
not be infinite.  Otherwise it requires the compiler to be able to correctly
analyze all unsigned IVs which I know we do not at the moment (SCEV
has limits).

So - any suggestion as to how define "nontrivial exit condition"?

> But the C++ standard went to the trouble of banning infinite loops without
> side effects specifically to enable DCE on this type of code... Actually,
> an infinite loop with a trivial exit condition looks like a great
> opportunity to use __builtin_unreachable() to me ;-) (I have been wanting
> a -fmain-does-return -fno-funny-business for years, since I looked at
> replacing some malloc with stack allocations, but that's all out of scope
> for this patch)
>
> Why exactly are we trying so hard to preserve no-side-effect, infinite
> loops? What are they good for? Note that reading an atomic or volatile
> variable counts as a side effect for this purpose. It looks like some kind
> of busy waiting, but without checking a flag, so it can only be stopped by
> some external action (say a signal), so if the OS has any notion of sleep
> for a thread, blocking would be better. Or maybe it is running through a
> circular list, ensuring that it stays in RAM? Anyway it seems specific
> enough that that strange code should be the one needing an annotation.

I guess we preserve them because we have to?

I suppose we could add a flag that allows us to elide
loops with no side-effect and non-constant exit condition
(so only preserve do{}while (1))?

Not sure where that would fit best though - certainly not
in niter / IV analysis but in CD-DCE then?

Richard.

> --
> Marc Glisse