[patch] Make jump threading preserve loops

Dorit Nuzman DORIT@il.ibm.com
Wed Nov 8 12:45:00 GMT 2006

> On Tue, 2006-10-31 at 22:07 +0100, Zdenek Dvorak wrote:
> > Hello,
> >
> > this patch makes jump threading preserve loops.  At the moment, jump
> > 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.

Two options to consider (beyond really calling vect_analyze_loop):
- don't peel if -ftree-vectorize is on
- maybe just check dependences in the loop, as a measure to evaluate
vectorizability. it's an anlysis that is useful to have as a stand-alone
anyhow (and mostly already is - compute_data_dependences_for_loop I guess).

> However, I'm OK with simply restricting peeling to the first iteration
> if you're getting reasonable results with that.

this would still spoil the alignment, which is *very* unfortunate. People
put a lot of attention to structuring their code such that the data would
be aligned for vectorization (just two recent examples:
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=27827#c56). I think we should
strongly consider Jeff's comment above.


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

More information about the Gcc-patches mailing list