Register allocation and spill complexity under SSA

Abstract : 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.
Document type :
Complete list of metadatas
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 10:11:15 AM
Last modification on : Monday, April 29, 2019 - 11:38:04 AM


Files produced by the author(s)


  • HAL Id : hal-02102197, version 1



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⟩



Record views


Files downloads