Analysis techniques for predicated code

Predicated execution offers new approaches to exploiting instruction-level parallelism (ILP), but it also presents new challenges for compiler analysis and optimization. In predicated code, each operation is guarded by a boolean operand whose run-time value determines whether the operation is executed or nullified. While research has shown the utility of predication in enhancing ILP, there has been little discussion of the difficulties surrounding compiler support for predicated execution. Conventional program analysis tools (e.g. data flow analysis) assume that operations execute unconditionally within each basic block and thus make incorrect assumptions about the run-rime behavior of predicated code. These tools can be modified to be correct without requiring predicate analysis, but this yields overly-conservative results in crucial areas such as scheduling and register allocation. To generate high-quality code for machines offering predicated execution, a compiler must incorporate information about relations between predicates into its analysis. We present new techniques for analyzing predicated code. Operations which compute predicates are analyzed to determine relations between predicate values. These relations are captured in a graph-based data structure, which supports efficient manipulation of boolean expression representing facts about predicated code. This approach forms the basis for predicate-sensitive data flow analysis. Conventional data flow algorithms can be systematically upgraded to be predicate sensitive by incorporating information about predicates. Predicate-sensitive data flow analysis yields significantly more accurate results than conventional data flow analysis when applied to predicated code.