This is the mail archive of the
mailing list for the GCC project.
Re: [patch] Make jump threading preserve loops
- From: Dorit Nuzman <DORIT at il dot ibm dot com>
- To: law at redhat dot com
- Cc: gcc-patches at gcc dot gnu dot org, Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- Date: Wed, 8 Nov 2006 14:41:32 +0200
- Subject: Re: [patch] Make jump threading preserve loops
> 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.....