[LLVMdev] Chaitin-Briggs Register Allocation in LLVM

[David A. Greene]

"Prajish Prasad" <prajish at cse.iitb.ac.in> writes:

>   We noticed that LLVM has implemented register allocation using PBQP and
> Briggs as a heuristic for spilling. Is there a direct implementation of
> the Chaitin-Briggs register allocation algorithm? We intend to modify
> parts of this algorithm in order to implement a variant of it. It will
> save us a lot of time if it is already implemented, rather than writing
> the code from scratch.

Such things have been done by several people, including myself.  I
believe the reason nothing ever got committed is that it isn't worth it.
My experience with an x86 target is that graph coloring buys almost
nothing.  It does indeed do what it claims to do - reduce spilling.  But
it turns out that the amount of spilling on x86 doesn't matter.  What
matters is _what_ is spilled.  The existing allocators are quite hard to
beat in that regard.

So this is a bit of a cautionary tale as you do your research.  Don't
just look at the number of spills to determine which allocator is
"best."  That number is completely misleading.  As in any study with
performance as a goal, measuring performance is the only valid
evaluation.

                             -Dave