On Mon, 20 May 2019, Richard Biener wrote:
On Sat, May 18, 2019 at 4:00 PM Marc Glisse <marc.gli...@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).
We also want to handle pointer-chasing loops (lists, trees), not
specifically unsigned IV.
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))?
The C++ standard says that do{}while(1) is __builtin_unreachable(), we
don't have to preserve it. There is no mention of anything like a
"nontrivial exit condition". Other languages may have a different opinion
though, so it would probably need a flag indeed... But I am curious what
the point of such a loop is.
--
Marc Glisse
