pretty-ipa merge 15: loop finiteness testing

[Richard Guenther]

On Sat, Apr 25, 2009 at 8:11 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> 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?
>
> you test whether it dominates loop latch (of course, you may also need
> to test that the exit is reached at all, i.e., that there is no function
> call or other reason why it could fail to be reached before it in the
> loop).
>
>> 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?
>
> SCEV actually does not need preheaders (or at least, it would be easy to
> modify it not to, if some code that assumes preheaders creeped in);
> however, there are cases where preheaders make it possible to get better
> results, e.g. if you have a loop with two entry edges like this:
>
> loop
>  {
>    i_1 = phi (3, 5, i_2);
>    i_2 = i_1 + 1;
>  }
>
> There is no way how to express the scev of i_1, while after introducing
> the preheaders, we get
>
> i_0 = phi (3,5);
> loop
>  {
>    i_1 = phi (i_0, i_2);
>    i_2 = i_1 + 1;
>  }
>
> and i_1 = {i_0, +, 1}.
>
>>  How far did you get on maintaining the loop structure plan?
>
> At some point, we were able to maintain the loop structure through
> all of tree-ssa optimizations, we just never got to switch it on.  I am
> not sure whether this still works (I'd suspect that it does not),

It would be a worthy goal for 4.5 at least.  But I wonder what we do
during inlining - do we properly duplicate loop information?

Richard.