[LLVMdev] Graph coloring register allocation
lhames at gmail.com
Thu Nov 20 00:42:14 PST 2008
I have an old (LLVM 1.9) graph coloring allocator based on paper 
below, and Appel's iterated register coalescing. You're welcome to the
code, though it may take some time to bring up to date. I believe
Roman Levenstein is working on an updated, improved & highly optimized
version - go for his if he's ready to release it.
Shameless plug: You might want to check out the PBQP allocator too.
It's already in the LLVM mainline and makes modeling register
constraints such as pairs very easy. See  for a good reference for
this technique, with a focus on embedded systems.
I can't help much with tablegen questions, but I'm very happy to help
with any specific register allocation ones.
 Michael D. Smith, Norman Ramsey, and Glenn Holloway. A generalized
algorithm for graph-coloring
register allocation. In PLDI '04: Proceedings of the ACM SIGPLAN 2004
conference on Programming
language design and implementation, pages 277¨C288, New York, NY, USA, 2004. ACM.
 Bernhard Scholz and Erik Eckstein. Register allocation for
irregular architectures. SIGPLAN Not., 37(7):139¨C148, 2002.
On Thu, Nov 20, 2008 at 5:19 PM, §¦§Ó§Ô§Ö§ß§Ú§Û §¢§Ñ§Ý§Ñ§ê§à§Ó <heavior at yandex.ru> wrote:
> I am working on developing register allocator for irregular
> architectures (with register
> pair, and banks) and plan to base my work on graph coloring register
> I wonder if LLVM already has basic graph coloring register
> allocator, or somebody is
> working on it?
> Also, I'm not sure what is the best way to even describe the
> register constraints in
> - How can I describe register pairs?
> - It it possible to have overlapping register classes?
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
More information about the llvm-dev