Add a new combine pass

Segher Boessenkool segher@kernel.crashing.org
Tue Nov 26 01:44:00 GMT 2019


On Mon, Nov 25, 2019 at 11:08:47PM +0000, Richard Sandiford wrote:
> Segher Boessenkool <segher@kernel.crashing.org> writes:
> > On Mon, Nov 25, 2019 at 09:16:52PM +0000, Richard Sandiford wrote:
> >> Segher Boessenkool <segher@kernel.crashing.org> writes:
> >> > I am wondering the other way around :-)  Is what you do for combine2
> >> > something that would be more generally applicable/useful?  That's what
> >> > I'm trying to find out :-)
> >> >
> >> > What combine does could use some improvement, if you want to hear a
> >> > more direct motivations.  LOG_LINKS just skip references we cannot
> >> > handle (and some more), so we always have to do modified_between etc.,
> >> > which hurts.
> >> 
> >> The trade-offs behind the choice of representation are very specific
> >> to the pass.
> >
> > Yes, but hopefully not so specific that every pass needs a completely
> > different representation ;-)
> 
> Well, it depends.  Most passes make do with df (without DU/UD-chains).
> But since DU/UD-chains are naturally quadratic in the general case,
> and are expensive to keep up to date, each DU/UD pass is going to have
> make some compromises.  It doesn't seem too bad that passes make
> different compromises based on what they're trying to do.  (combine:
> single use per definition; fwprop.c: track all uses, but for dominating
> definitions only; sched: fudged via a param; regrename: single
> definition/multiple use chains optimised for renmaing; combine2: full
> live range information, but limited use list; etc.)

combine actually *calculates* DU chains almost completely, it just throws
away most of that information (it wants to have LOG_LINKS, as it did ages
ago).  The only thing stopping us from doing that right now is that not
all uses are counted (some are skipped).

Since combine works only within BBs, DU chains are linear to compute, and
UD chains are trivial (and just linear to compute).

Updating is quadratic in general, sure.  Luckily in most realistic cases
it is cheap (most, sigh) (insns aren't combined to very far away).

> So yeah, if passes want to make roughly the same compromises, it would
> obviously be good if they shared a representation.  But since each pass
> does something different, I don't think it's a bad sign that they make
> different compromises and use different representations.
> 
> So I don't think a new pass with a new representation is in itself a
> sign of failure.

Oh, I don't think so either.  I just wonder if it would be useful more
generically :-)

> >> >> >> Target                 Tests   Delta    Best   Worst  Median
> >> >> >> avr-elf                 1341 -111401  -13824     680     -10
> >> >> >
> >> >> > Things like this are kind of suspicious :-)
> >> >> 
> >> >> Yeah.  This mostly seems to come from mopping up the extra moves created
> >> >> by make_more_copies.  So we have combinations like:
> >> >> 
> >> >>    58: r70:SF=r94:SF
> >> >>       REG_DEAD r94:SF
> >> >>    60: r22:SF=r70:SF
> >> >>       REG_DEAD r70:SF
> >> >
> >> > Why didn't combine do this?  A target problem?
> >> 
> >> Seems to be because combine rejects hard-reg destinations whose classes
> >> are likely spilled (cant_combine_insn_p).
> >
> > Ah, okay.  And that is required to prevent ICEs, in combine2 as well
> > then -- ICEs in RA.
> 
> Not in this case though.  The final instruction is a hardreg<-pseudo move
> whatever happens.  There's nothing special about r70 compared to r94.

So the target hook could be improved?  Or, this doesn't matter anyway,
the extra register move does not prevent any combinations, and RA should
get rid of it when that is beneficial.

But you see smaller code in the end, hrm.


Segher



More information about the Gcc-patches mailing list