pretty-ipa merge 15: loop finiteness testing

[Jan Hubicka]

> Hi,
> 
> > this patch adds finite_loop_p I would like to use in pure/const and cd-dce later.
> > It is basically same logic as in niter, just bit relaxed in three ways:
> > 
> >   1) It is not working hard enough to find minimal number of iterations
> >   2) In pure/const functions it assumes that all loops must be finite.
> >   3) It also assume for flag_unsafe_loop_optimizations.
> > 
> > I would hope that later we will add more tricks.
> > 
> > I also wonder why !just_once_each_iteration_p is needed here?  It does
> > not matter if the exit sits inside nested loop, right?
> 
> it's used there to test that the exit is executed at least once in each
> iteration.

Hmm, testing that test is executed once or more times is probably
difficult?  I have to think about it a bit.  Testcases I saw on STL are
of form of "if (iter has integer overflow) throw ()" tests that are
useless for bounding number of iterations but still give hint for
finiteness.  Those can happen in inner loops of outer loop.
> 
> > + /* Return true if loop is known to be finite.  */
> > + 
> > + bool
> > + finite_loop_p (struct loop *loop)
> 
> This comment is a bit missleading -- it is not entirely clear
> what does it mean that the loop is finite.  finite_loop_p can return true for
> loops that never end (e.g. if the loop has an infinite subloop, or
> calls a function containing such a loop).

Thanks! I will rephrase it as
 /* Return true if loop is known to have bounded number of iterations.  */

On pretty-ipa I use the predicate to drive cd-dce that I hope can
eliminate empty loop removal.  Quite surprisingly even in GCC bootstrap
(mainly mpfr) there are several cases of dead loops with multiple exits
that are dificult to handle by loop pass.  (i.e. there is inner empty
loop that computes amount of iterations of next execution of herself).
STL code tends to construct very complex dead loops when STL iterators
are used with multiple exits etc.

However I am bit concerned about fact that SCEV is relatively expensive
to fire up.  The patch to enable ipa-reference and cd-dce use the info
actually improved bootstrap time of pretty-ipa a lot (580s->560s). I
plan to figure out why.  Libstdc++ builds faster as STL code simplifies
and DCE scheduled before inlining avoids inlining of pure functions but
difference is not that grand.

In addition to the expense there is problem with fact that SCEV needs to
fire up loop optimizer up to point constructing preheaders.  During IPA
analysis we are not expected to change CFG so this is bit fragile (even
if it works well in practice as new BBs will be all empty)

Why SCEV needs preheaders at first place and also is there some chance
to put this bit conveniently somewhere?  How far did you get on
maintaining the loop structure plan?

Honza
> 
> Otherwise OK,
> 
> Zdenek