Abstract:

We have shown that register allocation can be viewed as solving a collection of puzzles. We model the register file as a puzzle board and the program variables as puzzle pieces; pre-coloring and register aliasing fit in naturally. For architectures such as x86, PowerPC, and StrongARM, we can solve the puzzles in polynomial time, and we have augmented the puzzle solver with a simple heuristic for spilling. For SPEC CPU2000, our implementation is as fast as the extended version of linear scan used by LLVM, which is the JIT compiler in the openGL stack of Mac OS 10.5. Our implementation produces Pentium code that is of similar quality to the code produced by the slower, state-of-the-art iterated register coalescing algorithm of George and Appel augmented with extensions by Smith, Ramsey, and Holloway.

Bibtex:

@inproceedings{Pereira08PLDI,
 author = {Fernando Magno Quintao Pereira and Jens Palsberg},
 title = {Register Allocation by Puzzle Solving},
 booktitle = {ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation (PLDI'08)},
 year = {2008},
}

Download:

• Register Allocation by Puzzle Solving (PDF)
• Page with links to PDF and source code