[LLVMdev] Graph Coloring Regalloc
sabre at nondot.org
Wed Apr 4 19:33:30 PDT 2007
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?
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
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.
More information about the llvm-dev