Re: [patch] Make jump threading preserve loops

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> > 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?

I will try.

> > 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 am sorry for the ambiguity. What the patch tries is to avoid peeling
the loop at all.  The problem with this is that we want to allow jump
threading in cases like

i = 0;
while (1)
  {
    if (i == 100)
      break;
    body;
  }

It is somewhat difficult to distinguish these cases, especially for
loops with multiple exits; so the heuristics is to allow threading
from loop entry edge to non-exit edge only once (in dom1 pass),
and furthermore disallow it if whole loop body would be copied this
way, which works fine for simple loops, although it still can have
effect of peeling one iteration in more complicated cases.

> > 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.

I think I did the measurements on preprocessed gcc sources and did not
observe any slowdowns; but I already deleted the results, so I will
re-measure it just for sure.

Zdenek