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

Cited literature [14 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102190
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 10:06:23 AM
Last modification on : Thursday, November 21, 2019 - 2:38:44 AM

File

RR2005-34.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102190, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

19

Files downloads

22