A Multi-Variable -Function Placement Algorithm Based on Dominator Frontier Inverse

Based on the work of Cytron and Cooper, we employ the concept of dominance frontier inverse (DFI) to present an iterative algorithm to simultaneously place -nodes for all variables of a function. The set DFI(x) is a set of the nodes N whose dominance frontier is x. The set DFI(x) has one important property: The nodes in the set DFI(x) must be the nodes whose level is no smaller than the level of x on the dominator tree. For each node y contained in the set DFI(x), the variables defined on node y should be placed on node x, and if there are -nodes only, the variables of -nodes should also be placed on x. In fact, the DFI set neednt be computed when placing -nodes in the algorithm of this paper, because a variable set is adopted to hold the -nodes. The algorithm firstly visits the dominator tree in a bottom-up traversal by levels, and then iteratively computes fixed point for the -nodes sets on the join nodes with the same level. The innovation is that the algorithm can directly work on the dominator tree. And it merges the former two-step algorithm into one. Experimental results of the C Specint2000 show that this algorithm is much faster than Cytrons original algorithm, and is also comparable with Cytrons -placement algorithm based on Coopers DF algorithm.