Efficient Static Single Assignment Form for Predication

Arthur Stoutchinin


We present a framework that allows translation of predicated code into the static single assignment (SSA) form, and simplifies application of the SSA-based optimizations to predicated code. In particular, we represent predicate join points in the program by the PSI-functions similar to the PHI-functions of the basic SSA. The SSA-based optimizations (such as constant propagation) can be applied to predicated code by simply specifying additional rules for processing the PSI-functions. We present efficient algorithms for constructing, and then for removing the PSI-functions at the end of SSA processing. Our algorithm for translating out of the PSI-SSA splits predicated live ranges into smaller live ranges active under disjoint predicates. The experimental evaluation on a set of predicated benchmarks demonstrates efficiency of our approach.