Efficient static single assignment form for predication

Abstract

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 /spl Psi/-functions similar to the /spl 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 /spl Psi/-functions. We present efficient algorithms for constructing, and then for removing the /spl Psi/-functions at the end of SSA processing. Our algorithm for translating out of the /spl 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.