Register Allocation

RegisterAllocation is the process of allocating CPU registers for local or temporary variables in a basic block of code during compilation. Register Allocation is similar to the NP-Complete Graph Coloring problem. Linear-scan heuristics are frequently used to produce fast, but sub-optimal results.

I believe RegisterAllocation is essentially the same as the Graph Coloring problem. (Graph nodes are values, edges represent overlapping value lifetimes, and colors are available registers.)

Basically yes, but the actual task always involves compromises for live range splitting and spill code generation, because even if we could solve the NP-problem, we may end up with too much registers anyway.

Some relevant papers:

• Linear scan register allocation (1999) http://portal.acm.org/citation.cfm?id=330250
• Fusion-based register allocation (2000) http://portal.acm.org/citation.cfm?id=353926.353929

---

CategoryCompilers