Efficient Building and Placing of Gating Functions

In this paper, we present an almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at 0—nodes. The gating functions specify the control dependences for each reaching definition at a node. We introduce a new concept of gating path, which is a path in the control flow graph from the immediate dominator u of a. node v to v, such that every node in the path is dominated by u. Previous algorithms start with —function placement, and then traverse the control flow graph to compute the gating functions. By formulating the problem into gating path construction, we are able to identify not only a (f>—node, but also a gating path expression which defines a gating function for the d>-node.