[LLVMdev] Spillers

[David Greene]

On Tuesday 07 August 2007 05:00, Anton Vayvod wrote:

> > Yes, that's true.  But I wonder if we shouldn't be smarter about which
> > register we pick to color it.  In Bill W's implementation, it was
> > essentially random.  What was your solution to this?
>
> I allocated spill intervals at the beginning of each iteration so all the
> rest intervals (except of physreg intervals) were uncolored at the moment.
> So the only difference in allocating regs for spills was what end to
> choose: allocation_order_begin() or allocation_order_end(), I chose the
> former. I understand that sometimes you can prefer one register over
> another for spill so it won't conflict with as much intervals as it would
> being mapped to another phys, but the same can be said about every
> interval, right?

Ah, ok, that makes sense.  Yes, this is true of every interval.  It's the
classic, "do I reuse registers to limit spilling or chew up registers to
help scheduling" question.

FYI, in my implementation I just marked the intervals introduced by
spills as being special so that they would not be chosen to be spilled
again.  Then they just get colored like every other interval.

> > Wait, but aren't you implying then that it's impossible for an interval
> > corresponding to a spill to be uncolorable?  I don't think that's true.
> > Therefore, precoloring most certainly can cause harm because a decision
> > is being made in local context without the global information that could
> > help make a better one.
>
> At least this is the imply of LiveIntervals: try to call
> addIntervalsForSpills on a spill interval and you'll have an assertion

Yep, and that's a good check.

> algorithm could spill these intervals over and over again. Having spill
> intervals mapped to physregs garantees that your iterations will finish
> eventually.

As noted above, you don't actually have to color them early.  You can just
mark them as unspillable.  There will always be some other interval to
spill, unless there's a serious bug in the algorithm.

> > Right.  Live range splitting would indeed be nice to have.  Bill's
> > implementation has a flavor of it.
>
> In case live range splitting implemented spill intervals wouldn't have to
> be the shortest when some interval is spilled the first time. But during
> iterations uncolored spill intervals should become shorter and shorter
> until they are must-be-precolored.

Right, except for the pre-coloring bit.  :)

> As far as I understand, you don't need to call spiller every iteration.

Right, that was my fundamental misunderstanding.  I've got it straight
now.

Thanks to everyone for the help.

                                        -Dave