International Symposium on Code Generation and Optimization (CGO'04)
Optimizing Translation Out of SSA Using Renaming Constraints
San Jose, California
March 20-March 24
ISBN: 0-7695-2102-9
Static Single Assignment form is an intermediate representation that uses ? instructions to merge values at each confluent point of the control flow graph. ? 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 ? 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 ?-related copies during the out of SSA translation, thanks to a pinning-based coalescing algorithm that is aware of renaming constraints. We implemented our algorithm in the STMicro-electronics 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.
Citation:
F. Rastello, F. de Ferri?re, C. Guillon, "Optimizing Translation Out of SSA Using Renaming Constraints," cgo, pp.265, International Symposium on Code Generation and Optimization (CGO'04), 2004