Efficiently computing static single assignment form and the control dependence graph

Reviewer: Benjamin Rayborn Seyfarth

The authors present strong arguments for the practicality and utility of the static single assignment (SSA) form and the control dependence graph (CDG) in optimizing compilers. They use the concept of a dominator tree to formalize the concept of dominance frontiers and use this to derive efficient algorithms for computing the SSA form and the CDG. They show that their algorithms require linear time for programs restricted to straight-line code, that is, if-then-else and while-do constructs. They also present experimental evidence that suggests that their algorithms are linear for typical programs. This paper is important, since SSA and CDG have been proposed as useful data structures for optimization without practical algorithms. It is well written and moderately long (40 pages), which is essential for describing the authors' algorithms adequately. An extensive bibliography points to excellent papers on compiler optimization techniques. Both compiler writers and theorists will find this paper useful.