[LLVMdev] Greedy Register Allocation in LLVM 3.0

Daniel Berlin dberlin at dberlin.org
Wed Sep 28 08:58:59 PDT 2011

On Tue, Sep 27, 2011 at 2:24 PM, Leo Romanoff <romixlev at yahoo.com> wrote:
> Hi Jakob,
> Yes. I have references. For example, from the top of my head I would name
> the following papers:
> 1)  A Generalized Algorithm for Graph-Coloring Register Allocation
> by Michael D. Smith, Norman Ramsey and Glenn Holloway
>      http://www.cs.tufts.edu/~nr/pubs/gcra-abstract.html
> 2) Register allocation by puzzle solving by Fernando Magno Quintão Pereira,
> Jens Palsberg
>      http://llvm.org/pubs/2008-06-PLDI-PuzzleSolving.pdf

Fernando was an intern of mine at Google for the summer (now he's a
professor in Brazil :P), and has LLVM code for his allocator.
It was quite nice, from what I remember, and quite practical.  I doubt
the code still works, but he was always interested in seeing it taken
over and used for real.
(He definitely understood the difference between "research" and "reality").

As Leo says, the "world of register allocation" has definitely caught
up to the realities of SSA and newer compilers in the past 5-6 years.

> I think I've seen a few more papers on this topic, but cannot remember them
> at the moment. If I find more papers in my collection I'll let you know.

More information about the llvm-dev mailing list