Method and apparatus for ordered predicate phi in static single assignment form

Abstract

A Φ function provides a mechanism for static single assignment in the presence of predicated code. Guards placed on each source operand of the Φ function indicate the condition under which the corresponding source operand is live and provide correct materialization of the Φ functions after code reordering. For control functions Φrepresenting a confluence of live reaching definitions at a join point in the control flow graph, the guards indicate the basic block which is the source of the edge associated with the source operand. The Φoperands are paired with the source basic block of the incoming edge(s) along which they are live. The operands are also ordered according to a topological ordering of their associated block. This ordering is maintained through subsequent code transformations. In the topological ordering, the source of the edge from which the definition was passed is defined. A predicate Φ function Φ, represents the confluence of definitions in a straight line of code in which some of the definitions have been predicated. For Φ, the guards on the source operands indicate the predicate under which the corresponding operand is live. The order of the operands is such that the Φfunction can be fully materialized by inserting a copy from each source operand to the target variable, in the corresponding order, and each predicated by the associated predicate guard.