A Practical and Fast Iterative Algorithm for φ-Function Computation Using DJ Graphs

摘要

We present a new and practical method of computing φ-function for all variables in a function for Static Single Assignment (SSA) form. The new algorithm is based on computing the Merge set of each node in the control flow graph of a function (a node here represents a basic block and the terms will be used interchangeably). Merge set of a node n is the set of nodes N, where φ-functions may need to be placed if variables are defined in n. It is not necessary for n to have a definition of a variable in it. Thus, the merge set of n is dictated by the underlying structure of the CFG. The new method presented here precomputes the merge set of every node in the CFG using an iterative approach. Later, these merge sets are used to carry out the actual φ-function placement. The advantages are in examples where dense definitions of variables are present (i.e., original definitions of variables―user defined or otherwise, in a majority of basic blocks). Our experience with SSA in the High Level Optimizer (optimization levels +O3/+O4) shows that most examples from the Spec2000 benchmark suite require a high percentage of basic blocks to have their φ points computed. Previous methods of computing the same relied on the dominance frontier (DF) concept, first introduced by Cytron et al. The method presented in this paper gives a new effective iterative solution to the problem. Also, in cases, where the control flow graph does not change, our method does not require any additional computation for new definitions introduced as part of optimizations. We present implementation details with results from Spec2000 benchmarks. Our algorithm runs faster than the existing methods used.