Register allocation and spill complexity under SSA

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

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

This report deals with the problem of choosing which variables to spill during the register allocation phase. Spilling is used when the number of variables is higher than the number of registers, and consists of storing the value of a variable in memory and loading it when necessary. The problem is that instructions dealing with memory are time-consumming. Hence the goal is to minimize the amount of spilled variables, which is a highly studied problem for compiler design, but nevertheless NP-complete. Meanwhile, a program under SSA form has the interesting property that on cases where spill is unnecessary, the problem of register allocation is not anymore NP-complete but polynomial. The interesting question is: can we solve the spilling problem under SSA, come back from SSA by splitting live-ranges as SSA does and finaly use classical register allocator? We show in this report that unfortunately many formulations of the spilling problem are also NP-complete under SSA form. In particular, the node-deletion approach used in most compilers remains NP-complete on most cases even on basic-blocks. The only polynomial solution has a too high complexity in practice. But this first advanced study on the complexity of the spill problem under SSA greatly helps to the understanding and gives directions for polynomial approximations. In this report, we also talk about the problem of splitting variables aggressively as in SSA. This shows the weakness of the "iterated register coalescing" regarding false interferences created by the adding of move instructions. We then implemented in a production compiler for st200 an interference graph based on liveness analysis and value numbering: two variables interfere if at one's definition the other is live and carries another value. The experiments we made and present in this report show that with such an interference graph aggressive splitting is not a problem.

Les problèmes de l’allocation de registres et du vidage en mémoire (spill)sont nés avec la compilation ; ils ont été très étudiés mais sont NP completsdans le cas général. Cependant, un programme sous forme SSA a la particularité de posséder un graphe d’interférences trianguléce qui rend polynomiale la phase d’allocation de registres. Nous montronsdans ce rapport que malheureusement le problème du vidage en mémoire sous forme SSA reste NP-complet dans le cas général et mêmesi l’on se restreint au bloc de base presque tous les cas sont NP-complets.L’algorithme polynomial trouvé dans un cas particulier est inutilisable car trop coûteux. On trouvera donc dans ce rapport la première étude poussée de complexité du problème de vidage en mémoire sous forme SSA. Cette étudeaide à la compréhension du problème et mène à des pistes pour des heuristiques polynomiales.Ce rapport présente également un algorithme simple pour réduire le nombre d’instructions de copie créées lors du passage à la forme SSA. Il se base sur une étude des valeurs que contiennent les variables pour détecterles copies inutiles et allouer les variables correspondantes au même registre. Cet algorithme a été implanté avec succès dans un compilateur industriel utilisé par STMicroelectronics.

Mots clés: Coalescing; Compilation; NP-completeness; Perfect graph; SSA; Spill; register allocation

Mots clés: Allocation de registres; Forme SSA; Graphe parfait; NP-complétude; Réduction des copies; Vidage en mémoire

Domaines: Informatique [cs]

Florent Bouchez, Alain Darte, Christophe Guillon, Fabrice Rastello. Register allocation and spill complexity under SSA. [Research Report] Laboratoire de l'informatique du parallélisme. 2005, 2+28p. ⟨hal-02102197⟩