|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 ABSTRACT
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. REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
INDEX TERMS
Primary Classification:
Additional Classification:
Keywords:
REVIEW
"R. Clayton : Reviewer"
A standard way to reduce the time taken by a multi-pass algorithm is to reduce the number of passes made by the algorithm. The multi-pass algorithm for placing phi functions in a static, single assignment-based control flow graph (CFG) has been un
more...
The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage Privacy Policy Code of Ethics Contact Us Useful downloads:  Adobe Acrobat
 QuickTime
 Windows Media Player
 Real Player
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Pdf
D.3