[LLVMdev] Graph coloring register allocation

[Lang Hames]

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.

Cheers,
Lang.


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



On Thu, Nov 20, 2008 at 5:19 PM, §¦§Ó§Ô§Ö§ß§Ú§Û §¢§Ñ§Ý§Ñ§ê§à§Ó <heavior at yandex.ru> wrote:
>
>        Hello,
>        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
> allocator.
>        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
>        tablegen:
>        - How can I describe register pairs?
>        - It it possible to have overlapping register classes?
>
>        Thanks,
>        Eugeny
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>