[LLVMdev] Spillers

[Anton Vayvod]

 Hi, David.

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.

Imagine that on a second iteration allocation algorithm figures out that
some spilled interval can't be assigned a physical register. Allocator can't
spill it so some recoloring must be done to free at least one physical
register to allocate. Precoloring #INF weighted intervals makes allocation
simpler by eliminating such situations.

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). 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.

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

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.

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.

Hope that helps.

Anton.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070806/b5db574a/attachment.html>