A Multi-variable Algorithm for Placing Phi-nodes

Based on the work of Cytron, we employ the concept of dominance frontier inverse (DFI) to present an iterative algorithm to simultaneously place phi-nodes for all variables of a function. The set DFI(x) is a set of the nodes N whose dominance frontier is x. Two important properties of the set DFI(x) make this algorithm faster: (1) The set DFI(x) is empty if x has a single predecessor, that is only the DFI set of the join nodes may not be empty; (2) The nodes in the set DFI(x) must be nodes whose level is no smaller than the level of x on the dominator tree. After the DFI sets are calculated, the algorithm travels bottom-up on the dominator tree by levels, and iteratively computes a fixed point for the DFI sets of the join nodes with the same level, and after a fixed point is reached for the DFI sets of the level, the phi-nodes for multi-variable are placed on these join nodes. The advantage of this algorithm is that the phi-nodes doesnpsilat need to be placed for each variable separately. Experimental results of the C Specint2000 show that this algorithm is about 13.0% faster than Cytronpsilas algorithm on average, and especially for 176.gcc benchmark, the improvement is 20.7%, while it is 0.7% in Das.