Increasing the scope and resolution of Interprocedural Static Single Assignment

While intraprocedural Static Single Assignment (SSA) is ubiquitous in modern compilers, the use of interprocedural SSA, although seemingly a natural extension, is limited. We find that part of the impediment is due to the narrow scope of variables handled by previously reported approaches, leading to limited benefits in optimization.

In this talk, we present our Interprocedural SSA (ISSA) construction algorithm where the scope is extended to include record elements and singleton heap variables. We show that ISSA scales reasonably well (to all MediaBench and most of the SPEC2K) and demonstrate the effectiveness of interprocedural copy propagation and interprocedural liveness analysis in reducing input and output instructions. ISSA is then leveraged for constant propagation and dead code removal, where 11.8% additional expressions are folded. Lastly, we discuss future research directions.

Greg Steffan

Last modified: Wed Aug 26 18:20:34 EDT 2009