Register allocation : what does Chaitin's NP-completeness proof really prove ?

Abstract : Register allocation is one of the most studied problem in compilation. It is consideredas an NP-complete problem since Chaitin, in 1981, showed that assigning temporary variablesto k machine registers amounts to color, with k colors, the interference graph associatedto variables and that this graph can be arbitrary, thereby proving the NP-completenessof the problem. However, this original proof does not really show where the complexitycomes from. Recently, the re-discovery that interference graphs of SSA programs can becolored in polynomial time raised the question: Can we exploit SSA to perform register allocationin polynomial time, without contradicting Chaitin’s NP-completeness result? Toaddress such a question, we revisit Chaitin’s proof to better identity the interactions betweenspilling (load/store insertion), coalescing/splitting (moves between registers), criticaledges (a property of the control-flow graph), and coloring (assignment to registers). Inparticular, we show when it is easy to decide if temporary variables can be assigned to kregisters or if some spilling is necessary. The real complexity comes from critical edges,spilling, and coalescing, which are addressed in our other reports.
Document type :
Complete list of metadatas
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:00:28 AM
Last modification on : Friday, April 19, 2019 - 1:38:15 AM


Files produced by the author(s)


  • HAL Id : hal-02102286, version 1



Florent Bouchez, Alain Darte, Fabrice Rastello. Register allocation : what does Chaitin's NP-completeness proof really prove ?. [Research Report] LIP RR-2006-13, Laboratoire de l'informatique du parallélisme. 2006, 2+12p. ⟨hal-02102286⟩



Record views


Files downloads