Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Optimizing the translation out-of-SSA with renaming constraints

Abstract : Static Single Assignment form is an intermediate representation that uses phi instructions to merge values at each confluent point of the control flow graph. phi instructions are not machine instructions and must be renamed back to move instructions when translating out of SSA form. Without a coalescing algorithm, the out of SSA translation generates many move instructions. Leung and George use a SSA form for programs represented as native machine instructions, including the use of machine dedicated registers. For this purpose, they handle renaming constraints thanks to a pinning mechanism. Pinning phi arguments and their corresponding definition to a common resource is also a very attractive technique for coalescing variables. In this paper, extending this idea, we propose a method to reduce the phi-related copies during the out of SSA translation, thanks to a pinning-based coalescing algorithm that is aware of renaming constraints. This report provides also a discussion about the formulation of this problem, its complexity and its motivations. We implemented our algorithm in the STMicroelectronics Linear Assembly Optimizer. Our experiments show interesting results when comparing to the existing approaches of Leung and George, Sreedhar et al., and Appel and George for register coalescing.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 10:06:23 AM
Last modification on : Wednesday, October 26, 2022 - 8:15:44 AM


Files produced by the author(s)


  • HAL Id : hal-02102190, version 1



Fabrice Rastello, F. de Ferrière, Christophe Guillon. Optimizing the translation out-of-SSA with renaming constraints. [Research Report] LIP RR-2005-34, Laboratoire de l'informatique du parallélisme. 2005, 2+26p. ⟨hal-02102190⟩



Record views


Files downloads