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 :
Reports
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102286
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 11:00:28 AM
Last modification on : Thursday, November 21, 2019 - 2:38:41 AM

File

RR2006-13.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102286, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

14

Files downloads

112