Graph coloring register allocation

  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?


Hi Eugeny,

I have an old (LLVM 1.9) graph coloring allocator based on paper [1]
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 [2] 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.


[1] 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.

[2] Bernhard Scholz and Erik Eckstein. Register allocation for
irregular architectures. SIGPLAN Not., 37(7):139¨C148, 2002.