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

Florent Bouchez (1) , Alain Darte (1) , Fabrice Rastello (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

L’allocation de registres est l’un des problèmes les plus étudiés en compilation.On le considère en général NP-complet depuis que Chaitin,en1981,a montré qu’affecter des variables temporaires à k registres physiques revient à colorier avec k couleurs le graphe d’interférences associé aux variables et que ce graphe peut être quelconque. En revanche,cette démonstration ne révèle pas vraiment d’où vient la complexité.Récemment,la redécouverte que les graphes d’interférence des programmes SSA peuvent être coloriés en temps polynomial a conduit à la question: peut-on exploiter la forme SSA pour faire de l’allocation de registres en temps polynomial sans contredire la preuve de Chaitin? Pour répondre à ce genre de questions, nous revisitons la démonstration de Chaitin pour mieux identifier les interactions entre le“spilling”(insertion de store/load), le“coalescing”/”splitting”(moves entre registres),la présence d’arcs critiques(une propriété du graphe de flot de contrôle)et le coloriage proprement dit (affectation aux registres). En particulier, nous montrons quand il est facile de décider si des variables temporaires peuvent être affectées à k registres ou si du“spilling”est nécessaire.La vraie complexité du problème d’allocation de registres provient de la présence d’arcs critiques,du“spilling”et du“coalescing”,problèmes que nous consid ́erons dans nos autres rapports.

Mots clés: Chordal graph; Critical edge; NP-completeness; Register allocation; SSA form

Mots clés: Forme SSA; Graphe triangulé; Allocation de registres; Arc critique; NP-complétude

Domaines: Informatique [cs]

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⟩