We show 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 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 with an extension by Smith, Ramsey, and Holloway from 2004.
In the talk I will show how puzzle solving is an 
instance of SSA-based register allocation.

Joint work with Fernando Pereira.  More information is at:
http://compilers.cs.ucla.edu/fernando/projects/puzzles/