Re: [patch] Make jump threading preserve loops

[Jeffrey Law <law at redhat dot com>]

On Tue, 2006-10-31 at 22:07 +0100, Zdenek Dvorak wrote:
> Hello,
> 
> this patch makes jump threading preserve loops.  At the moment, jump
> threading tries to keep the loops valid by using edge flags; this is
> not quite reliable, and also not all cases are handled correctly.
> Preserving the validity of current_loops structure ensures that
> no invalid loops may be created much more reliably.
My background in graph theory is pretty weak and it shows when
it comes to a lot of this stuff.  It's absolutely true that using
edge flags to drive pruning of jump threads was hackish at best
and only worked for those cases which I had seen often in practice.
A more systematic approach is certainly welcome.


> Some changes to other parts of compiler turned out to be necessary:
> 1) cleanup_tree_cfg_loop is now run a bit more often, which revealed
>    problems in fix_loop_structure and several other functions related
>    to maintaining information about loops.
Would it make sense to break this out while I try to wrap my brain
around the rest of the patch?

> 2) Jump threading sometimes peels iterations from loops, which is
>    annoying and may prevent e.g. vectorizer from working efficiently,
>    by spoiling the alignment of arrays.  With this patch, loop peeling
>    occured more often, so I was forced to restrict it a bit (otherwise,
>    since vrp + dom are run about 5 times through the compilation, we
>    would end up peeling 4 or 5 iterations from many loops); in
>    particular, some types of jump threading are only allowed in the
>    first instance of dom pass, so some changes to enable us to detect
>    whether the first instance of a pass is run were necessary.
Yes.  I've never looked at any approaches to determine when peeling was
profitable vs unprofitable.  Also note that aggressively peeling can
result in compile-time explosions during the SSA graph updates if the
loop can be entirely peeled into straightline code.  I don't recall
offhand how that's throttled anymore.

ISTM that you almost want to have done some basic analysis of the loop
to determine if it might be vectorizable, and if vectorization might be
possible, then you don't peel.

However, I'm OK with simply restricting peeling to the first iteration
if you're getting reasonable results with that.  I also wonder if we
should go ahead and install that infrastructure immediately while I
continue to review the more complex parts of the patch.


> One a bit annoying bit is that although we update the information about
> loops, we do not manage to update dominators during jump threading;
> the main problem there is that jump threading may create unreachable
> blocks, and dominators infrastructure does not like that.  I am thinking
> about some solution, but for the moment, we use
> determine_bb_domination_status to recover the parts of the dominance
> information we need by scanning cfg.
Yes.  That was amazingly annoying, on many levels.  

Did you happen to do any compile-time testing of this patch?  One of the
other drivers for some of the structure of the code was compile time
efficiency.  Knowing that we're not going to send compile time through
the roof would be good.

Still reading.....

Jeff