llvm dev - Apr 2011 - [LLVMdev] Chaitin-Briggs Register Allocation in LLVM

Hi,

  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.


Thanks and Regards,
Prajish

"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