PRACTICAL IMPROVEMENTS TO THE CONSTRUCTION AND DESTRUCTION OF STATIC SINGLE ASSIGNMENT FORM

Static Single Assignment (SSA) form is a program representation that i s becoming increasingly popular for compiler-based code optimization. In this paper, we address three problems that have arisen in our use o f SSA form. Two are variations to the SSA construction algorithms pres ented by Cytron et al,(1) The first variation is a version of SSA form that we call 'semi-pruned' SSA, It offers an attractive trade-off bet ween the cost of global data-how analysis required to build 'pruned' S SA and the large number of unused phi-functions found in minimal SSA, The second variation speeds up the program renaming process by efficie ntly manipulating the stacks of names used during renaming. Our improv ement reduces the number of pushes performed, in addition to more effi ciently locating the stacks that should be popped. To convert code in SSA form back into an executable form, the compiler must use an algori thm that replaces phi-functions with appropriately-placed copy instruc tions. The algorithm given by Cytron et al, for inserting copies produ ces incorrect results in some situations; particularly in cases like i nstruction scheduling, where the compiler may not be able to split 'cr itical edges', and in the aftermath of optimizations that aggressively rewrite the name space, like some forms of global value numbering.(2) We present a new algorithm for inserting copy instructions to replace phi-functions. It fixes the problems that we have encountered with th e original copy insertion algorithm. We present experimental results t hat demonstrate the effectiveness of the first two improvements not on ly during the construction of SSA form, but also in the time saved by subsequent optimization passes that use a smaller representation of th e program. (C) 1998 John Wiley & Sons, Ltd.