[LLVMdev] Spillers

[David Greene]

On Tuesday 07 August 2007 14:42, Anton Vayvod wrote:
> > 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.
>
> But they can be uncolored like every other interval then, right? When your
> algorithm finds out during one iteration that it should spill some interval
> it checks whether this interval is marked. If it is marked what's
> happening? Choosing some neighbour interval to spill instead of that one?

Exactly.  There is always guaranteed to be at least one neighbor that can be
colored.  Otherwise, the spiller didn't spill properly.

> Is this better then precoloring spill intervals (starting from 
> allocation_order_end phys reg)? 

Potentially, in at least a couple of ways.

These colors are picked outside the regular "select" phase and therefore don't 
take advantage of any heuristics that might be there to do various things.  
For example, select could have heuristics to guide allocation to keep maximum 
flexibility for the scheduler.  Adding similar heuristics to the pre-color 
code would be needless duplication and a maintenance headache.

Precoloring necessarily restricts what the allocator can do with other 
intervals.  Some precoloring is necessary for things like ABI conformance
but generally, less is better.

In practice, do these things make a difference?  I don't know.  I haven't come
across any papers asking these questions.  My intuition says it doesn't matter
for 99% of codes out there, but in our case, that 1% of codes can often mean
the difference between a sale and going home empty-handed.

The main reason I did what I did was to keep all of the select code in one
place.  This is simply a matter of maintenance and keeping things as simple
and uniform as possible.

                                            -Dave