[LLVMdev] Graph Coloring Regalloc

[Chris Lattner]

On Wed, 4 Apr 2007, Domagoj Babic wrote:
> Has anyone tried optimal graph coloring algorithms? Yeah, it's NP,
> but the chances are that you are not looking at that many variables
> at the same time. I'm wondering how much could one improve the
> register allocation by using optimal algorithms, and how much impact
> would that have on the speed of the produced native code?

<soapbox>

IMO, coloring the graph / assigning the registeres isn't the hard part. 
The hard part of doing a decent job of register allocation is handling 
things like: folding spill code into instructions, handling register 
coallescing, splitting live ranges, doing rematerialization, doing shrink 
wrapping, etc.

This opinion is largely "colored" (haha) by experience with ISAs that have 
few registers.  If you are targeting itanium, you have a whole different 
set of issues.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/