[LLVMdev] Spillers

[David Greene]

On Monday 06 August 2007 12:15, Anton Vayvod wrote:

> Spill intervals must be precolored because they can't be spilled once more.
> They are the shortest intervals precisely over each def/use of the original
> interval. That is why they also have their weights set to #INF.

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?

> As for giving the best result. If assumed that each interval is spilled
> into the shortest spill intervals then precoloring won't do any harm to the
> quality of allocation (as shown above). 

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.

> But in theory you can spill intervals differently. For example, interval can 
> be split into two  intervals - the shortest interval that cannot be colored 
> right now and the  rest part that can be colored. That say if you have [10, 
> 50) intervals that conflicts with [40, 45) and can't be colored it can be 
> split into smth like  [10, 40) and [40, 50). The former part should not be 
> precolored as it has  less conflicts (it doesn't intersects with [40, 45) ) 
> and can be colored entirely by one register on the next iteration.

Right.  Live range splitting would indeed be nice to have.  Bill's 
implementation has a flavor of it.

> Unfortunately, it seems that current implementation doesn't support such
> "clever" spilling.

True.  People have talked about adding it ever since I started getting 
involved.

> Anyway, this precoloring doesn't force allocation algorithms to be
> non-iterative. In my implementation of optimistic register coloring I
> precolor spill intervals at the beginning of each iteration and thus don't
> have to spill their neghbours specifically. It was done automatically by
> Select phase of algorithm.

So how did you get around the requirement of the spillers that intervals
be mapped to physical registers?  Or did you not use the provided spillers?
That may be what I end up doing.  Loads and stores don't absolutely have to be
inserted into the actual instruction text on each iteration, though it is nice
for debugging purposes.

> As Fernando has mentioned while I was writing this after the last iteration
> of your algorithm before you call Spiller::runOnMachineFunction method
> every interval in VirtRegMap must be mapped to a physical register, both
> spill and others.

Right, which means the pre-defined spillers can't be called during iteration.

                                     -Dave