Register Allocation by Puzzle Solving

This project consists in developing a new model for register allocation that has fast compilation time, produces code of good quality, is able to address the many irregularities found in common computer architectures and is intuitive enough to be easily understood. 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, SPARC V8, 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 CPU 2000, 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.

  • A short introduction about register allocation by puzzle solving.

  • A tutorial on register allocation by puzzle solving.

  • The raw data used in our experiments is available here.

  • We have some goodies in the publications section.

  • The source files are now available for download.

  • We have proved the soundness of our approch in twelf.

  • A debugger/verifier for register allocation can be found here.


Full version of the paper:
Download it This is the short version of our paper.
Download it This is the full version of our paper. The appendices contain the proofs of the theorems stated in the main body of the paper, plus more detailed pseudo-code for the register assignment phase, with spilling and coalescing.