Previous Next 
The IBM Fortran H compiler used dominators to identify loops in controlflow graphs of basic blocks of machine instructions [Lowry and Medlock 1969]. Lengauer and Tarjan [1979] developed the nearlineartime algorithm for finding dominators in a directed graph, and proved the related theorems mentioned in this chapter. It is common to use this algorithm while mentioning the existence [Harel 1985] of a more complicated lineartime algorithm. Finding the "best" node above a given spanningforest node is an example of a unionfind problem; analyses of balanced pathcompression algorithms for unionfind (such as the "sophisticated" version of the LengauerTarjan algorithm) can be found in many algorithms textbooks (e.g., Sections 22.322.4 of Cormen et al. [1990]). Static singleassignment form was developed by Wegman, Zadeck, Alpern, and Rosen [Alpern et al. 1988; Rosen et al. 1988] for efficient computation of dataflow problems such as global value numbering, congruence of variables, aggressive deadcode removal, and constant propagation with conditional branches [Wegman and Zadeck 1991]. Controldependence was formalized by Ferrante et al. [1987] for use in an optimizing compiler for vector parallel machines. Cytron et al. [1991] describe the efficient computation of SSA and controldependence graphs using dominance frontiers and prove several of the theorems mentioned in this chapter. Wolfe [1996] describes several optimization algorithms on SSA (which he calls factored usedef chains), including inductionvariable analysis. It is useful to perform several transformations on the flowgraph before conversion to SSA form. These include the conversion of whileloops to repeatloops (); and the insertion of loop preheader nodes (see page 382), postbody nodes [Wolfe 1996] (Exercise 18.6), and landing pads for loopexit edges [Rosen et al. 1988] (edgesplitting effectively accomplishes the insertion of landing pads). Such transformations provide locations into which statements (such as loopinvariant computations or common subexpressions) may be placed. Varieties of functional intermediate representations Functional intermediate forms are all based on lambdacalculus, more or less, but they differ in three important respects:
Distinction (1) ceases to matter in continuationpassing style. The design space of these options has been well explored, as this table shows:
Direct style 


Strict 
Lazy 
Continuation passing 

Arbitrarily nested sub expressions 
Cardelli [1984], Cousineau et al. [1985] 
Augustsson [1984] 

Atomic arguments + λ 
Flanagan et al. [1993] 
Steele [1978], Kranz et al. [1986] 

Atomic arguments 
Tarditi [1997] 
Peyton Jones [1992] 
Appel [1992] 
The functional intermediate form shown in Image 19.18 fits in the lower lefthand corner, along with Tarditi [1997]. Kelsey [1995] shows how to convert between SSA and continuationpassing style.
JaVa  Previous Next 