Efficiently Computing Static Single Assignment Form and the Control Dependence Graph

1 INTRODUCTION

In optimizing compilers, data structure choices directly influence the power and efficiency of practical program optimization. A poor choice of data structure can inhibit optimization or slow compilation to the point where advanced optimization features become undesirable. Recently, static single assignment (SSA) form [5, 43] and the control dependence graph [24] have been proposed to represent data flow and control flow properties of programs. Each of these previously unrelated techniques lends efficiency and power to a useful class of program optimizations. Although both of these structures are attractive, the difficulty of their construction and their potential size have discouraged their use [4]. We present new algorithms that efficiently compute these data structures for arbitrary control flow graphs. The algorithms use dominance frontiers, a new concept that may have other applications. We also give analytical and experimental evidence that the sum of the sizes of all the dominance frontiers is usually linear in the size of the original program. This paper thus presents strong evidence that SSA form and control dependences can be of practical use in optimization.

Figure 1 illustrates the role of SSA form in a compiler. The intermediate code is put into SSA form, optimized in various ways, and then translated back out of SSA form. Optimizations that can benefit from using SSA form include code motion [22] and elimination of partial redundancies [43], as well as the constant propagation discussed later in this section.

Variants of SSA form have been used for detecting program equivalence [5, 52] and for increasing parallelism in imperative programs [21]. The representation of simple data flow information (def-use chains) may be made more compact through SSA form. If a variable has $D$ definitions and $U$ uses, then there can be $D \times U$ def-use chains. When similar information is encoded in SSA form, there can be at most $E$ def-use chains, where $E$ is the number of edges in the control flow graph [40]. Moreover, the def-use information encoded in SSA form can be updated easily when optimizations are applied. This is important for a constant propagation algorithm that deletes branches to code proven at compile time to be unexecutable [50]. Specifically, the def-use information is just a list, for each variable, of the places in the program text that use that variable. Every use of V is indeed a use of the value provided by the (unique) assignment to V.

To see the intuition behind SSA form, it is helpful to begin with straight-line code. Each assignment to a variable is given a unique name (shown as a subscript in Figure 2), and all of the uses reached by that assignment are renamed to match the assignment’s new name.

Most programs, however, have branch and join nodes. At the join nodes, we add a special form of assignment called a $\phi$-function. In Figure 3, the

Original Intermediate Code ↓ $P_0 \rightarrow P_1 \rightarrow P_2 \rightarrow \ldots P_n$ Optimized Intermediate Code ↑

Fig. 1. Vertical arrows represent translation to/from static single assignment form. Horizontal arrows represent optimizations.

            
              if P
then V ← 4
else V ← 6
            
          

/ Use V several times. /

            
              if P
then V₁ ← 4
else V₂ ← 6
            
          

$V_3 \leftarrow \phi(V_1, V_2)$ / Use V_3 several times. /

operands to the $\phi$-function indicate which assignments to $V$ reach the join point. Subsequent uses of $V$ become uses of $V_3$. The old variable $V$ is thus replaced by new variables $V_1, V_2, V_3, \ldots$, and each use of $V_i$ is reached by just one assignment to $V_i$. Indeed, there is only one assignment to $V_i$ in the entire program. This simplifies the record keeping for several optimizations. An especially clear example is constant propagation based on SSA form [50]; the next subsection sketches this application.

1.1 Constant Propagation

Figure 4 is a more elaborate version of Figure 3. The else branch includes a test of $Q$, and propagating the constant true to this use of $Q$ tells a compiler that the else branch never falls through to the join point. If $Q$ is the constant true, then all uses of $V$ after the join point are really uses of the constant 4. Such possibilities can be taken into account without SSA form, but the processing is either costly [48] or difficult to understand [49]. With SSA form, the algorithm is fast and simple.

Initially, the algorithm assumes that each edge is unexecutable (i.e., never followed at run time) and that each variable is constant with an as-yet unknown value (denoted $T$). Worklists are initialized appropriately, and the assumptions are corrected until they stabilize. Suppose the algorithm finds that variable $P$ is not constant (denoted $\perp$) and, hence, that either branch of

            
              if P
then do V ← 4
    end
else do V ← 6
    if Q then return
end
            
          

... ← V + 5

            
              if P
then do V₁ ← 4
    end
else do V₂ ← 6
    if Q then return
end
V₃ ← φ(V₁, V₂)
... ← V₃ + 5
            
          

Fig 4. Example of constant propagation.

the outer conditional may be taken. The outedges of the test of P are marked executable, and the statements they reach are processed. When V₁ ← 4 is processed, the assumption about V₁ is changed from T to 4, and all uses of V₁ are notified that they are uses of 4. (Each use of V₁ is indeed a use of this value, thanks to the single assignment property.) In particular, the φ-function combines 4 with V₂. The second operand of the φ-function, however, is associated with the inedge of the join point that corresponds to falling through the else branch. So long as this edge is considered unexecutable, the algorithm uses T for the second operand, no matter what is currently assumed about V₂. Combining 4 with T yields 4, so uses of V₃ are still tentatively assumed to be uses of 4. Eventually, the assumption about Q may change from T to a known constant or to ⊥. A change to either false or ⊥ would lead to the discovery that the second inedge of the join point can be followed, and then the 6 at V₂ combines with the 4 at V₁ to yield ⊥ at V₃. A change to true would have no effect on the assumption at V₃. Traditional constant propagation algorithms, on the other hand, would see that assignments of two different constants to V seem to “reach” all uses after the join point. They would thus decide that V is not constant at these uses.

The algorithm just sketched is linear in the size of the SSA program it sees [50], but this size might be nonlinear in the size of the original program. In particular, it would be safe but inefficient to place a φ-function for every variable at every join point. This paper shows how to obtain SSA form efficiently. When φ-functions are placed carefully, nonlinear behavior is still possible but is unlikely in practice. The size of the SSA program is typically linear in the size of the original program; the time to do the work is essentially linear in the SSA size.

1.2 Where to Place φ-Functions

At first glance, careful placement might seem to require the enumeration of pairs of assignment statements for each variable. Checking whether there are two assignments to V that reach a common point might seem to be intrinsically nonlinear. In fact, however, it is enough to look at the dominance frontier of each node in the control flow graph. Leaving the technicalities to later sections, we sketch the method here.

Suppose that a variable V has just one assignment in the original program, so that any use of V will be either a use of the value V₀ at entry to the program or a use of the value V₁ from the most recent execution of the assignment to V. Let X be the basic block of code that assigns to V, so X will determine the value of V when control flows along any edge X → Y to a basic block Y. When entered along X → Y, the code in Y will see V₁ and be unaffected by V₀. If Y ≠ X, but all paths to Y must still go through X (in which case X is said to strictly dominate Y), then the code in Y will always see V₁. Indeed, any node strictly dominated by X will always see V₁, no matter how far from X it may be. Eventually, however, control may be able to reach a node Z not strictly dominated by X. Suppose Z is the first such node on a path, so that Z sees V₁ along one inedge but may see V₀ along another inedge. Then Z is said to be in the dominance frontier of X and is clearly in need of a φ-function for V. In general, no matter how many assignments to V may appear in the original program and no matter how complex the control flow may be, we can place φ-functions for V by finding the dominance frontier of every node that assigns to V, then the dominance frontier of every node where a φ-function has already been placed, and so on.

The same concept of dominance frontiers used for computing SSA form can also be used to compute control dependences [20, 24], which identify those conditions affecting statement execution. Informally, a statement is control dependent on a branch if one edge from the branch definitely causes that statement to execute while another edge can cause the statement to be skipped. Such information is vital for detection of parallelism [2], program optimization, and program analysis [28].

1.3 Outline of the Rest of the Paper

Section 2 reviews the representation of control flow by a directed graph. Section 3 explains SSA form and sketches how to construct it. This section also considers variants of SSA form as defined here. Our algorithm can be adjusted to deal with these variants. Section 4 reviews the dominator tree concept and formalizes dominance frontiers. Then we show how to compute SSA form (Section 5) and the control dependence graph (Section 6) efficiently. Section 7 explains how to translate out of SSA form. Section 8 shows that our algorithms are linear in the size of programs restricted to certain control structures. We also give evidence of general linear behavior by reporting on experiments with FORTRAN programs. Section 9 summarizes the algorithms and time bounds, compares our technique with other techniques, and presents some conclusions.

2 CONTROL FLOW GRAPHS

The statements of a program are organized into (not necessarily maximal) basic blocks, where program flow enters a basic block at its first statement and leaves the basic block at its last statement [1, 36]. Basic blocks are indicated by the column of numbers in parentheses in Figure 5. A control flow graph is a directed graph whose nodes are the basic blocks of a program and two additional nodes, Entry and Exit. There is an edge from Entry to

            
              I ← 1	(1)
J ← 1	(1)
K ← 1	(1)
L ← 1	(1)
repeat	(2)
    if (P)	(2)
        then do	(3)
            J ← I	(3)
            if (Q)	(3)
                then L ← 2	(4)
                else L ← 3	(5)
            K ← K + 1	(6)
        end	(6)
    else K ← K + 2	(7)
print(I,J,K,L)	(8)
repeat	(9)
    if (R)	(9)
        then L ← L + 4	(10)
until (S)	(11)
I ← I + 6	(12)
until (T)	(12)
            
          

Fig 5 Simple program and its control flow graph.

any basic block at which the program can be entered, and there is an edge to Exit from any basic block that can exit the program. For reasons related to the representation of control dependences and explained in Section 6, there is also an edge from Entry to Exit. The other edges of the graph represent transfers of control (jumps) between the basic blocks. We assume that each node is on a path from Entry and on a path to Exit. For each node X, a successor of X is any node Y with an edge X → Y in the graph, and Succ(X) is the set of all successors of X; similarly for predecessors. A node with more than one successor is a branch node; a node with more than one predecessor is a join node. Finally, each variable is considered to have an assignment in Entry to represent whatever value the variable may have when the program is entered. This assignment is treated just like the ones that appear explicitly in the code. Throughout this paper, CFG denotes the control flow graph of the program under discussion.

For any nonnegative integer J, a path of length J in CFG consists of a sequence of J + 1 nodes (denoted X₀, ..., X_J) and a sequence of J edges (denoted e₁, ..., e_J) such that e_j runs from X_{j-1} to X_j for all j with 1 ≤ j ≤ J. (We write e_j: X_{j-1} → X_j.) As is usual with sequences, one item (node or edge) may occur several times. The null path, with J = 0, is allowed. We write $p: X_0 \to^* X_J$ for an unrestricted path $p$, but $p: X_0 \to^+ X_J$ if $p$ is known to be nonnull.

Nonnull paths $p: X_0 \to^+ X_J$ and $q: Y_0 \to^+ Y_K$ are said to converge at a node $Z$ if

Intuitively, the paths $p$ and $q$ start at different nodes and are almost node-disjoint, but they come together at the end. The use of or rather than and in (3) is deliberate. One of the paths may happen to be a cycle $Z \to^+ Z$, but we still need to consider the possibility of convergence.

3 STATIC SINGLE ASSIGNMENT FORM

This section initially assumes that programs have been expanded to an intermediate form in which each statement evaluates some expressions and uses the results either to determine a branch or to assign to some variables. (Other program constructs are considered in Section 3.1.) An assignment statement $A$ has the form $LHS(A) \leftarrow RHS(A)$, where the left-hand side $LHS(A)$ is a tuple of distinct target variables $\langle U, V, \ldots \rangle$ and the right-hand side $RHS(A)$ is a tuple of expressions, with the same length as the $LHS$ tuple. Each target variable in $LHS(A)$ is assigned the corresponding value from $RHS(A)$. In the examples already discussed, all tuples are 1-tuples, and there is no need to distinguish between $V$ and $\langle V \rangle$. Section 3.1 sketches the use of longer tuples in expanding other program constructs (such as procedure calls) so as to make explicit the variables used and/or changed by the statements in the source program. Such explicitness is a prerequisite for most optimizations anyway. The only novelty in our use of tuples is the fact that they provide a simple and uniform way to fold the results of analysis into the intermediate text. Practical concerns about the size of the intermediate text are addressed in Section 3.1.

Translating a program into SSA form is a two-step process. In the first step, some trivial $\phi$-functions $V \leftarrow \phi(V, V, \ldots)$ are inserted at some of the join nodes in the program's control flow graph. In the second step, new variables $V_i$ (for $i = 0, 1, 2, \ldots$) are generated. Each mention of a variable $V$ in the program is replaced by a mention of one of the new variables $V_i$, where a mention may be in a branch expression or on either side of an assignment statement. Throughout this paper, an assignment statement may be either an ordinary assignment or a $\phi$-function. Figure 6 displays the result of translating a simple program to SSA form.

A $\phi$-function at entrance to a node $X$ has the form $V \leftarrow \phi(R, S, \ldots)$, where $V, R, S, \ldots$ are variables. The number of operands $R, S, \ldots$ is the number of control flow predecessors of $X$. The predecessors of $X$ are listed in some arbitrary fixed order, and the $j$th operand of $\phi$ is associated with the $j$th

            
              I ← 1
J ← 1
K ← 1
L ← 1
repeat
    I₁ ← 1
    J₁ ← 1
    K₁ ← 1
    L₁ ← 1
    repeat
        I₂ ← φ(I₃, I₁)
        J₂ ← φ(J₄, J₁)
        K₂ ← φ(K₅, K₁)
        L₂ ← φ(L₉, L₁)
        if (P)
            then do
                J ← I
                if (Q)
                    then L ← 2
                    else L ← 3
                K ← K + 1
            end
        else K ← K + 2
    print(I, J, K, L)
    repeat
        if (R)
            then L ← L + 4
        until (S)
        I ← I + 6
until (T)

I₁ ← 1
J₁ ← 1
K₁ ← 1
L₁ ← 1
repeat
    I₂ ← φ(I₃, I₁)
    J₂ ← φ(J₄, J₁)
    K₂ ← φ(K₅, K₁)
    L₂ ← φ(L₉, L₁)
    if (P)
        then do
            J₃ ← I₂
            if (Q)
                then L₃ ← 2
                else L₄ ← 3
            L₅ ← φ(L₃, L₄)
            K₃ ← K₂ + 1
        end
    else K₄ ← K₂ + 2
        J₄ ← φ(J₃, J₂)
        K₅ ← φ(K₃, K₄)
        L₆ ← φ(L₂, L₅)
    print(I₂, J₄, K₅, L₆)
    repeat
        L₇ ← φ(L₉, L₆)
        if (R)
            then L₈ ← L₇ + 4
            L₉ ← φ(L₈, L₇)
        until (S)
        I₃ ← I₂ + 6
    until (T)
            
          

Fig. 6 Simple program and its SSA form.

predecessor. If control reaches X from its jth predecessor, then the run-time support¹ remembers j while executing the φ-functions in X. The value of φ(R, S, ...) is just the value of the jth operand. Each execution of a φ-function uses only one of the operands, but which one depends on the flow of control just before entering X. Any φ-functions in X are executed before the ordinary statements in X. Some variants of φ-functions as defined here are useful for special purposes. For example, each φ-function can be tagged

¹When SSA form is used only as an intermediate form (Figure 1), there is no need actually to provide this support. For us, the semantics of φ are only important when assessing the correctness of intermediate steps in a sequence of program transformations beginning and ending with code that has no φ-functions. Others [6, 11, 52] have found it useful to give φ another parameter that incidentally encodes j, under various restrictions on the control flow.

with the node $X$ where it appears [5]. When the control flow of a language is suitably restricted, each $\phi$-function can be tagged with information about conditionals or loops [5, 6, 11, 52]. The algorithms in this paper apply to such variants as well.

SSA form may be considered as a property of a single program or as a relation between two programs. A single program is defined to be in SSA form if each variable is a target of exactly one assignment statement in the program text. Translation to SSA form replaces the original program by a new program with the same control flow graph. For every original variable $V$, the following conditions are required of the new program:

(1) If two nonnull paths $X \xrightarrow{+} Z$ and $Y \xrightarrow{+} Z$ converge at a node $Z$, and nodes $X$ and $Y$ contain assignments to $V$ (in the original program), then a trivial $\phi$-function $V \leftarrow \phi(V, \ldots, V)$ has been inserted at $Z$ (in the new program). (2) Each mention of $V$ in the original program or in an inserted $\phi$-function has been replaced by a mention of a new variable $V_i$, leaving the new program in SSA form. (3) Along any control flow path, consider any use of a variable $V$ (in the original program) and the corresponding use of $V_i$ (in the new program). Then $V$ and $V_i$ have the same value.

Translation to minimal SSA form is translation to SSA form with the proviso that the number of $\phi$-functions inserted is as small as possible, subject to Condition (1) above. The optimizations that depend on SSA form are still valid if there are some extraneous $\phi$-functions beyond those that would appear in minimal SSA form. However, extraneous $\phi$-functions can cause information to be lost, and they always add unnecessary overhead to the optimization process itself. Thus, it is important to place $\phi$-functions only where they are required. One variant of SSA form [52] would sometimes forego placing a $\phi$-function at a convergence point $Z$, so long as there are no more uses for $V$ in or after $Z$. The $\phi$-function could then be omitted without any risk of losing Condition (3). This has been called pruned SSA form [16], and it is sometimes preferable to our placement at all convergence points. However, as Figure 16 in Section 7 illustrates, our form is sometimes preferable to pruned form. When desired, pruned SSA form can be obtained by a simple adjustment of our algorithm [16, Section 5.1].

For any variable $V$, the nodes at which we should insert $\phi$-functions in the original program can be defined recursively by Condition (1) in the definition of SSA form. A node $Z$ needs a $\phi$-function for $V$ if $Z$ is a convergence point for two paths that originate at two different nodes, both nodes containing assignments to $V$ or needing $\phi$-functions for $V$. Nonrecursively, we may observe that a node $Z$ needs a $\phi$-function for $V$ because $Z$ is a convergence point for two nonnull paths $X \xrightarrow{+} Z$ and $Y \xrightarrow{+} Z$ that start at nodes $X$ and $Y$ already containing assignments to $V$. If $Z$ did not already contain an assignment to $V$, then the $\phi$-function inserted at $Z$ adds $Z$ to the set of nodes that contain assignments to $V$. With more nodes to consider as origins of paths, we may observe more nodes appearing as convergence points of nonnull paths originating at nodes with assignments to V. The set of nodes needing $\phi$-functions could thus be found by iterating an observation/insertion cycle.$^2$ The algorithm presented here obtains the same end results in much less time.

3.1 Other Program Constructs

If the source program computes expressions using constants and scalar variables to assign values to scalar variables, then it is straightforward to derive an intermediate text that is ready to be put into SSA form (or otherwise analyzed and transformed by an optimizing compiler). However, source programs commonly use other constructs as well: Some variables are not scalars, and some computations do not explicitly indicate which variables they use or change. This section sketches how to map some important constructs to an explicit intermediate text suitable for use in a compiler.

3.1.1 Arrays. It will suffice to consider one-dimensional arrays here. Arrays of higher dimension involve more notation but no more concerns.

If A and B are array variables, then array assignment statements like A \leftarrow B or A \leftarrow 0, if allowed by the source language, can be treated just like assignments to scalar variables. Many of the mentions of A(i) for some index i, which may be taken to be an integer variable. Treating A(i) as a variable would be awkward, both because an assignment to A(i) may or may not change the value of A(j) and because the value of A(i) could be changed by assigning to i rather than to A(i). An easier approach is illustrated in Figure 7. The entire array is treated like a single scalar variable, which may be one of the operands of Access or Update.$^3$ The expression Access(A, i) evaluates to the ith component of A; the expression Update(A, j, V) evaluates to an array value that is of the same size as A and has the same component values, except for V as the value of the jth component. Assigning a scalar value V to A(j) is equivalent to assigning an array value to the entire array A, where the new array value depends on the old one, as well as on the index j and on the new scalar value V. The translation to SSA form is unconcerned with whether the values of variables are large objects or what the operators mean.

As with scalars, translation of array references to SSA form removes some anti- and output-dependences [32]. In the program in Figure 7a, dependence analysis may prohibit reordering the use of A(i) by the first statement and the definition of A(j) by the second statement. After translation to SSA form, the two references to A have been renamed, and reordering is then possible. For example, the two statements can execute concurrently. Where optimization does not reorder the two references, Section 7.2 describes how translation out of SSA form reclaims storage that would otherwise be necessary to maintain distinct variables.

\footnotetext{ $^2$In typical cases, paths originating at $\phi$-functions add nothing beyond the contributions from paths originating at ordinary assignments. The straightforward iteration is still too slow, even in typical cases $^3$This notation is similar to Select and Update [24], which, in turn, is similar to notation for referencing aggregate structures in a data flow language [23]. }

(a) (b) (c)

Consider the loop shown in Figure 8a, which assigns to every component of array A. The value assigned to each component $\mathbf{A}(i)$ does not depend (even indirectly) on any of the values previously assigned to components of A. In terms of its effect on A, the whole loop is like an assignment of the form $\mathbf{A} \leftarrow (\ldots)$, where A is not used in (\ldots). Any assignment to a component of A that is not used before entering such an initialization loop is dead code that should be eliminated. With or without SSA form, the Update operator in Figure 8b makes A appear to be live at entry to the loop.

One reasonable response to the crudeness of the Update operator is to accept it. Address calculations and other genuine scalar calculations can still be optimized extensively. Another response is to perform dependence analysis [3, 10, 32, 51], which can sometimes determine that no subsequent accesses of A require values produced by any other assignment to A. Such is the case for each execution of the assignment to $\mathbf{A}(i)$ in Figure 8a. The assignment statement can then be viewed as an initialization of A. The problem for us, or for anyone who uses Update to make arrays look like scalars, is to communicate some of the results of dependence analysis to optimizations (like dead code elimination) that are usually formulated in terms of "scalar" variables. A simple solution to this formal problem is shown in Figure 8c, where the HiddenUpdate operator does not mention the assigned array operand. The actual code generated for an assignment from a HiddenUpdate expression is exactly the same as for an assignment from the corresponding Update expression, where the hidden operand is supplied by the target of the assignment.

3.1.2 Structures. A structure can be generally regarded as an array, where references to structure fields are treated as references to elements of the array. Thus, an assignment to a structure field is translated into an Update of the structure, and a use of a structure field is translated into an Access of the structure. In the prevalent case of simple structure field references, this treatment results in arrays whose elements are indexed by constants. Dependence analysis can often determine independence among such accesses, so that optimizations may move an assignment to one field far from an assignment to another field. If analysis or language semantics reveals a structure whose n fields are always accessed disjointly, then the structure can be decomposed into $n$ distinct variables. The elements of such structures are united in the source program only for organizational reasons, and the expression of the structure's decomposition in SSA form makes the program's actual use of the structure more apparent to subsequent optimization.

            
              integer A(1:100)
integer A₀(1:100)
integer A₁(1:100)
integer A₂(1:100)
i ← 1
repeat
    i₂ ← φ(i₁, i₃)
    A₁ ← φ(A₀, A₂)
    A₂ ← Update(A₁, i₂, i₂)
    i₃ ← i₂ + 1
    A(i) ← i
    i ← i + 1
until i ≥ 100
            
          

            
              (a)
integer A_0(1:100)
integer A_1(1:100)
integer A_2(1:100)
i_1 ← 1
repeat
    i_2 ← φ(i_1, i_3)
    A_1 ← φ(A_0, A_2)
    A_2 ← HiddenUpdate(i_2, i_2)
    i_3 ← i_2 + 1
until i_3 ≥ 100

(b)
integer A_0(1:100)
integer A_1(1:100)
integer A_2(1:100)
i_1 ← 1
repeat
    i_2 ← φ(i_1, i_3)
    A_1 ← φ(A_0, A_2)
    A_2 ← HiddenUpdate(i_2, i_2)
    i_3 ← i_2 + 1
until i_3 ≥ 100
(c)
            
          

Fig. 8. Source loop with array assignment (a) is equivalent to code with an Update operator that treats the array A just like a scalar (b). As Section 7.2 explains, the eventual translation out of SSA form will leave just one array here. Using HiddenUpdate (c) is a purely formal way to summarize some results of dependency analysis, if available.

3.1.3 Implicit References to Variables. The construction of SSA form requires knowing those variables modified and used by a statement. In addition to those variables explicitly referenced, a statement may use or modify variables not mentioned by the statement itself. Examples of such implicit references are global variables modified or used by a procedure call, aliased variables, and dereferenced pointer variables. To obtain SSA form, we must account for implicit as well as explicit references, either by conservative assumptions or by analysis. Heap storage can be conservatively modeled by representing the entire heap as a single variable that is both modified and used by any statement that may change the heap. More refined modeling is also possible [15], but the conservative approach is already strong enough to support optimization of code that does not involve the heap but is interspersed with heap-dependent code.

For any statement $S$, three types of references affect translation into SSA form:

(1) MustMod(S) is the set of variables that must be modified by execution of $S$. (2) MayMod(S) is the set of variables that may be modified by execution of $S$. (3) MayUse(S) is the set of variables whose values prior to execution of $S$ may be used by $S$.

We represent implicit references for any statement $S$ by transformation to an assignment statement $A$, where all the variables in MayMod(S) appear in $LHS(A)$ and all the variables in $MayUse(S) \cup (MayMod(S) - MustMod(S))$ appear in $RHS(A)$.

An optimizing compiler may or may not have access to the bodies of all procedures called (directly or indirectly) or to summaries of their effects. If no specific information is available, it is customary to make conservative assumptions. A call might change any global variable or any parameter passed by reference, but it is reasonable to assume that variables local to the caller will not change. Such assumptions limit the extent that transformations can be performed. Techniques are available to extract more detailed information: To determine parameter aliasing and effects of procedures on global variables, see [7–9], [19], [37], and [42]; to determine pointer aliasing, see [14, 15, 27, 29, 33, 34], and [44].

When a sophisticated analysis technique is applied, the usual result is that there are few side effects and the tuples (both LHS and RHS) are small. Small tuples can be represented directly. Sophisticated analysis, however, is often unavailable. Many compilers do no interprocedural analysis at all. Consider a call to an external procedure that has not been analyzed. Both tuples for the call must contain all global variables. The compiler’s own representation of the tuples can still be compact. The representation can be a structure that includes a flag (set to indicate that all globals are in the tuple) plus a direct representation of the few local variables that are in the tuple because of parameter transmission. The intuitive explanations and theoretical analyses of optimization techniques (with or without SSA form) are conveniently formulated in terms of explicit tuples; compact representations can still be used in the implementations.

3.2 Overview of the SSA Algorithm

Translation to minimal SSA form is done in three steps:

(1) The dominance frontier mapping is constructed from the control flow graph (Section 4.2). (2) Using the dominance frontiers, the locations of the $\phi$-functions for each variable in the original program are determined (Section 5.1). (3) The variables are renamed (Section 5.2) by replacing each mention of an original variable $V$ by an appropriate mention of a new variable $V_t$.

4 DOMINANCE

Section 4.1 reviews the dominance relation [47] between nodes in the control flow graph and how to summarize this relation in a dominator tree. Section 4.2 introduces the dominance frontier mapping and gives an algorithm for its computation.

4.1 Dominator Trees

Let $X$ and $Y$ be nodes in the control flow graph $CFG$ of a program. If -$X$ appears on every path from Entry to $Y$, then $X$ dominates $Y$. Domination is both reflexive and transitive. If $X$ dominates $Y$ and $X \neq Y$, then $X$ strictly

Fig. 9 Control flow graph and dominator tree of the simple program The sets of nodes listed in () and [ ] brackets summarize the dominance frontier calculation from Section 4.2. Each node $X$ is annotated with two sets $[DF_{local}(X)|DF(X)]$ and a third set $(DF_{up}(X))$.

dominates $Y$. In formulas, we write $X \gg Y$ for strict domination and $X \geq Y$ for domination. If $X$ does not strictly dominate $Y$, we write $X \not\gg Y$. The immediate dominator of $Y$ (denoted $idom(Y)$) is the closest strict dominator of $Y$ on any path from Entry to $Y$. In a dominator tree, the children of a node $X$ are all immediately dominated by $X$. The root of a dominator tree is Entry, and any node $Y$ other than Entry has $idom(Y)$ as its parent in the tree. The dominator tree for $CFG$ from Figure 5 is shown in Figure 9. Let $N$ and $E$ be the numbers of nodes and edges in $CFG$. The dominator tree can be constructed in $O(E \alpha(E, N))$ time [35] or (by a more difficult algorithm) in $O(E)$ time [26]. For all practical purposes, $\alpha(E, N)$ is a small constant,$^4$ so this paper will consider the dominator tree to have been found in linear time.

The dominator tree of $CFG$ has exactly the same set of nodes as $CFG$ but a very different set of edges. Here, the words predecessor, successor, and path always refer to $CFG$. The words parent, child, ancestor, and descendant always refer to the dominator tree.

$^4$Under the definition of $\alpha$ used in analyzing the dominator tree algorithm [35, p. 123], $N \leq E$ implies that $\alpha(E, N) = 1$ when $\log_2 N < 16$ and $\alpha(E, N) = 2$ when $16 \leq \log_2 N < 2^{16}$.

4.2 Dominance Frontiers

The dominance frontier $DF(X)$ of a $CFG$ node $X$ is the set of all $CFG$ nodes $Y$ such that $X$ dominates a predecessor of $Y$ but does not strictly dominate $Y$:

Computing $DF(X)$ directly from the definition would require searching much of the dominator-tree. The total time to compute $DF(X)$ for all nodes $X$ would be quadratic, even when the sets themselves are small. To compute the dominance frontier mapping in time linear in the size $\sum_X |DF(X)|$ of the mapping, we define two intermediate sets $DF_{local}$ and $DF_{up}$ for each node such that the following equation holds:

Given any node $X$, some of the successors of $X$ may contribute to $DF(X)$. This local contribution $DF_{local}(X)$ is defined by

Given any node $Z$ that is not the root Entry of the dominator tree, some of the nodes in $DF(Z)$ may contribute to $DF(idom(Z))$. The contribution $DF_{up}(Z)$ that $Z$ passes up to $idom(Z)$ is defined by

Lemma 1. The dominance frontier equation (4) is correct.

Proof. Because dominance is reflexive, $DF_{local}(X) \subseteq DF(X)$. Because dominance is transitive, each child $Z$ of $X$ has $DF_{up}(Z) \subseteq DF(X)$. We must still show that everything in $DF(X)$ has been accounted for. Suppose $Y \in DF(X)$, and let $U \to Y$ be an edge such that $X$ dominates $U$ but does not strictly dominate $Y$. If $U = X$, then $Y \in DF_{local}(X)$, and we are done. If $U \neq X$, on the other hand, then there is a child $Z$ of $X$ that dominates $U$ but cannot strictly dominate $Y$ because $X$ does not strictly dominate $Y$. This implies that $Y \in DF_{up}(Z)$.

The intermediate sets can be computed with simple equality tests as follows:

Lemma 2. For any node $X$,

Proof. We assume that $Y \in Succ(X)$ and show that

The $\Leftarrow$ part is true because the immediate dominator is defined to be a strict dominator. For the $\Rightarrow$ part, suppose that $X$ strictly dominates $Y$ and, hence,

            
              for each X in a bottom-up traversal of the dominator tree do
DF(X) ← ∅
for each Y ∈ Succ(X) do
/*local*/ if idom(Y) ≠ X then DF(X) ← DF(X) ∪ {Y}
end
for each Z ∈ Children(X) do
for each Y ∈ DF(Z) do
/*up*/ if idom(Y) ≠ X then DF(X) ← DF(X) ∪ {Y}
end
end
end
            
          

that some child $V$ of $X$ dominates $Y$. Then $V$ appears on any path from Entry to $Y$ that goes to $X$ and then follows the edge $X \rightarrow Y$, so either $V$ dominates $X$ or $V = Y$. But $V$ cannot dominate $X$, so $V = Y$ and $idom(Y) = idom(V) = X$. $\Box$

Lemma 3. For any node $X$ and any child $Z$ of $X$ in the dominator tree,

Proof. We assume that $Y \in DF(Z)$ and show that

The $\Leftarrow$ part is true because strict dominance is the transitive closure of immediate dominance. For the $\Rightarrow$ part, suppose that $X$ strictly dominates $Y$ and, hence, that some child $V$ of $X$ dominates $Y$. Choose a predecessor $U$ of $Y$ such that $Z$ dominates $U$. Then $V$ appears on any path from Entry to $Y$ that goes to $U$ and then follows the edge $U \rightarrow Y$, so either $V$ dominates $U$ or $V = Y$. If $V = Y$, then $idom(Y) = idom(V) = X$, and we are done. Suppose that $V \neq Y$ (and, hence, that $V$ dominates $U$) and derive a contradiction. Only one child of $X$ can dominate $U$, so $V = Z$ and $Z$ dominates $Y$. This contradicts the hypothesis that $Y \in DF(Z)$. $\Box$

These results imply the correctness of the algorithm for computing the dominance frontiers given in Figure 10. The /local/ line effectively computes $DF_{local}(X)$ on the fly and uses it in (4) without needing to devote storage to it. The /up/ line is similar for $DF_{up}(Z)$. We traverse the dominator tree bottom-up, visiting each node $X$ only after visiting each of its children. To illustrate the working of this algorithm, we have annotated the dominator tree in Figure 9 with the information [ ] and () brackets.

Theorem 1. The algorithm in Figure 10 is correct.

Proof. Direct from the preceding lemmas. $\Box$

Let $CFG$ have $N$ nodes and $E$ edges. The loop over $Succ(X)$ in Figure 10 examines each edge just once, so all executions of the /local/ line are complete in time $O(E)$. Similarly, all executions of the /up/ line are complete in time $O(\mathrm{size}(DF))$. The overall time is thus $O(E + \mathrm{size}(DF))$, which amounts to a worst-case complexity of $O(E + N^2)$. However, Section 8 shows that, in practice, the size of the mapping $DF$ is usually linear. We have implemented this algorithm and have observed that it is faster than the standard data-flow computations in the PTRAN compiler [2].

4.3 Relating Dominance Frontiers to Joins

We start by stating more formally the nonrecursive characterization of where the $\phi$-functions should be located. Given a set $\mathcal{S}$ of $CFG$ nodes, the set $J(\mathcal{S})$ of join nodes is defined to be the set of all nodes $Z$ such that there are two nonnull $CFG$ paths that start at two distinct nodes in $\mathcal{S}$ and converge at $Z$. The iterated join $J^+(\mathcal{S})$ is the limit of the increasing sequence of sets of nodes

In particular, if $\mathcal{S}$ happens to be the set of assignment nodes for a variable $V$, then $J^+(\mathcal{S})$ is the set of $\phi$-function nodes for $V$.

The join and iterated join operations map sets of nodes to sets of nodes. We extend the dominance frontier mapping from nodes to sets of nodes in the natural way:

As with join, the iterated dominance frontier $DF^+(\mathcal{S})$ is the limit of the increasing sequence of sets of nodes

The actual computation of $DF^+(\mathcal{S})$ is performed by the efficient worklist algorithm in Section 5.1; the formulation here is convenient for relating iterated dominance frontiers to iterated joins. If the set $\mathcal{S}$ is the set of assignment nodes for a variable $V$, then we will show that

(this equation depends on the fact that Entry is in $\mathcal{S}$) and, hence, that the location of the $\phi$-functions for $V$ can be computed by the worklist algorithm for computing $DF^+(\mathcal{S})$ that is given in Section 5.1.

The following lemmas do most of the work by relating dominance frontiers to joins:

Lemma 4. For any nonnull path p: $X \rightarrow^+ Z$ in $CFG$, there is a node $X' \in \{ X \} \cup DF^+(\{ X \})$ on p that dominates $Z$. Moreover, unless $X$ dominates every node on p, the node $X'$ can be chosen in $DF^+(\{ X \})$.

Proof. If $X$ dominates every node on $p$, then we just choose $X' = X$ to get all the claimed properties of $X'$. We may assume that some of the nodes on $p$ are not dominated by $X$. Let the sequence of nodes on $p$ be $X = X_0, \ldots, X_J = Z$. For the smallest $i$ such that $X$ does not dominate $X_i$, the predecessor $X_{i-1}$ is dominated by $X$ and so puts $X_i$ into $DF(X)$. Thus, there are choices of $j$ with $X_j \in DF^+(\{X\})$. Consider $X' = X_j$ for the largest $j$ with $X_j \in DF^+(\{X\})$. We will show that $X' \gg Z$. Suppose not. Then $j < J$, and there is a first $k$ with $j < k \leq J$ such that $X'$ does not dominate $X_k$. The predecessor $X_{k-1}$ is dominated by $X'$ and so puts $X_k$ into $DF(X')$. Thus, $X_k \in DF(DF^+(\{X\})) = DF^+(\{X\})$, contradicting the choice of $j$.

Lemma 5. Let $X \neq Y$ be two nodes in CFG, and suppose that nonnull paths $p: X \to^+ Z$ and $q: Y \to^+ Z$ in CFG converge at $Z$. Then $Z \in DF^+(\{X\}) \cup DF^+(\{Y\})$.

Proof. We consider three cases that are obviously exhaustive. In the first two cases, we prove that $Z \in DF^+(\{X\}) \cup DF^+(\{Y\})$. Then we show that the first two cases are (unobviously) exhaustive because the third case leads to a contradiction. Let $X'$ be from Lemma 4 for the path $p$, with the sequence of nodes $X = X_0, \ldots, X_J = Z$. Let $Y'$ be from Lemma 4 for the path $q$, with the sequence of nodes $Y = Y_0, \ldots, Y_K = Z$.

Case 1. We suppose that $X'$ is on $q$ and show that $Z \in DF^+(\{X\})$. By the definition of convergence (specifically, (3) in Section 2), $X' = Z$. We may now assume that $Z = X$ and $X$ dominates every node on $p$. (Otherwise, Lemma 4 already asserts $Z \in DF^+(\{X\})$.) Because $X$ dominates the predecessor $X_{J-1}$ of $Z$ but does not strictly dominate $Z$, we have $Z \in DF(X) \subseteq DF^+(\{X\})$.

Case 2. We suppose that $Y'$ is on $p$, and show that $Z \in DF^+(\{Y\})$, reasoning just as in Case 1.

Case 3. We derive a contradiction from the suppositions that $X'$ is not on $q$ and $Y'$ is not on $p$. Because $X' \gg Z$ but $X'$ is not on $q$, $X' \gg Y_K = Z$ and, therefore, dominates all predecessors of $Y_K$. In particular, $X' \gg Y_{K-1}$. But $X' \neq Y_{K-1}$, so $X' \gg Y_{K-1}$, and we continue inductively to show that $X' \gg Y_k$ for all $k$. In particular, $X' \gg Y'$. On the other hand, by similar reasoning from the supposition that $Y' \gg Z$ but $Y'$ is not on $p$, we can show that $Y' \gg X'$. Two nodes cannot strictly dominate each other, so Case 3 is impossible.

Lemma 6. For any set $\mathcal{S}$ of CFG nodes, $J(\mathcal{S}) \subseteq DF^+(\mathcal{S})$.

Proof. We apply Lemma 5.

Lemma 7. For any set $\mathcal{S}$ of CFG nodes such that Entry $\in \mathcal{S}$, $DF(\mathcal{S}) \subseteq J(\mathcal{S})$.

Proof. Consider any $X \in \mathcal{S}$ and any $Y \in DF(X)$. There is a path from $X$ to $Y$ where all nodes before $Y$ are dominated by $X$. There is also a path from Entry to $Y$ where none of the nodes are dominated by $X$. The paths therefore converge at $Y$.

Theorem 2. The set of nodes that need $\phi$-functions for any variable V is the iterated dominance frontier $DF^+(\mathcal{S})$, where $\mathcal{S}$ is the set of nodes with assignments to V.

Proof. By Lemma 6 and induction on $i$ in the definition of $J^+$, we can show that

The induction step is as follows:

The node Entry is in $\mathcal{S}$, so Lemma 7 and another induction yield

The induction step is as follows:

The set of nodes that need $\phi$-functions for $V$ is precisely $J^+(\mathcal{S})$, so (5) and (6) prove the theorem. □

5 CONSTRUCTION OF MINIMAL SSA FORM

5.1 Using Dominance Frontiers to Find Where $\phi$-Functions Are Needed

The algorithm in Figure 11 inserts trivial $\phi$-functions. The outer loop of this algorithm is performed once for each variable $V$ in the program. Several data structures are used:

— $W$ is the worklist of $CFG$ nodes being processed. In each iteration of this algorithm, $W$ is initialized to the set $\mathcal{A}(V)$ of nodes that contain assignments to $V$. Each node $X$ in the worklist ensures that each node $Y$ in $DF(X)$ receives a $\phi$-function. Each iteration terminates when the worklist becomes empty. — $Work(*)$ is an array of flags, one flag for each node, where $Work(X)$ indicates whether $X$ has ever been added to $W$ during the current iteration of the outer loop. — $HasAlready(*)$ is an array of flags, one for each node, where $HasAlready(X)$ indicates whether a $\phi$-function for $V$ has already been inserted at $X$.

The flags $Work(X)$ and $HasAlready(X)$ are independent. We need two flags because the property of assigning to $V$ is independent of the property of needing a $\phi$-function for $V$. The flags could have been implemented with just the values true and false, but this would require additional record keeping to reset any true flags between iterations, without the expense of looping over all the nodes. It is simpler to devote an integer to each flag and to test flags by comparing them with the current iteration count.

Let each node $X$ have $A_{orig}(X)$ original assignments to variables, where each ordinary assignment statement $LHS \leftarrow RHS$ contributes the length of the tuple $LHS$ to $A_{orig}(X)$. Counting assignments to variables is one of

            
              IterCount ← 0
for each node X do
    HasAlready(X) ← 0
    Work(X) ← 0
end
W ← ∅
for each variable V do
    IterCount ← IterCount + 1
    for each X ∈ A(V) do
        Work(X) ← IterCount
        W ← W ∪ {X}
    end
while W ≠ ∅ do
    take X from W
    for each Y ∈ DF(X) do
        if HasAlready(Y) < IterCount
            then do
                place ⟨ V ← φ(V, ..., V) ⟩ at Y
                HasAlready(Y) ← IterCount
                if Work(Y) < IterCount
                    then do
                        Work(Y) ← IterCount
                        W ← W ∪ {Y}
                    end
                end
            end
        end
    end
end
            
          

Fig. 11. Placement of $\phi$-functions.

several measures of program size.$^5$ By this measure, the program expands from size $A_{orig} = \sum_X A_{orig}(X)$ to size $A_{tot} = \sum_X A_{tot}(X)$, where each $\phi$-function placed at $X$ contributes 1 to $A_{tot}(X) = A_{orig}(X) + A_\phi(X)$. There is a similar expansion in the number of mentions of variables, from $M_{orig} = \sum_X M_{orig}(X)$ to $M_{tot} = \sum_X M_{tot}(X)$, where each $\phi$-function placed at $X$ contributes 1 plus the indegree of $X$ to $M_{tot}(X) = M_{orig}(X) + M_\phi(X)$.

Placing a $\phi$-function at $Y$ in Figure 11 has cost linear in the indegree of $Y$, so there is an $O(\sum_X M_\phi(X))$ contribution to the running time from the work done when $HasAlready(Y) < IterCount$. Replacing mentions of variables will contribute at least $O(M_{tot})$ to the running time of any SSA translation algorithm, so the cost of placement can be ignored in analyzing the contribution of Figure 11 to the $O(...)$ bound for the whole process. The $O(N)$ cost of

$^5$The various measures relevant here are reviewed when the whole SSA translation process is summarized in Section 9.1.

initialization can be similarly ignored because it is subsumed by the cost of the dominance frontier calculation. What cannot be ignored is the cost of managing the worklist W. The statement take X from W in Figure 11 is performed $A_{tot}(X)$ times, and each time incurs a cost linear in $|DF(X)|$ because all $Y \in DF(X)$ are polled. The contribution of Figure 11 to the running time of the whole process is therefore $O(\sum_X (A_{tot}(X) \times |DF(X)|))$. Sizing the output in the natural way as $A_{tot}$, we can also describe the contribution as $O(A_{tot} \times avrgDF)$, where the weighted average

emphasizes the dominance frontiers of nodes with many assignments. As Section 8 shows, the dominance frontiers are small in practice, and Figure 11 is effectively $O(A_{tot})$. This, in turn, is effectively $O(A_{orig})$.

5.2 Renaming

The algorithm in Figure 12 renames all mentions of variables. New variables denoted $V_i$, where $i$ is an integer, are generated for each variable $V$. Figure 12 begins a top-down traversal of the dominator tree by calling SEARCH at the root node Entry. The visit to a node processes the statements associated with the node in sequential order, starting with any $\phi$-functions that may have been inserted. The processing of a statement requires work for only those variables actually mentioned in the statement. In contrast with Figure 11, we need a loop over all variables only when we initialize two arrays among the following data structures:

—$S(*)$ is an array of stacks, one stack for each variable $V$. The stacks can hold integers. The integer $i$ at the top of $S(V)$ is used to construct the variable $V_i$ that should replace a use of $V$. —$C(*)$ is an array of integers, one for each variable $V$. The counter value $C(V)$ tells how many assignments to $V$ have been processed. —WhichPred($X, Y$) is an integer telling which predecessor of $Y$ in $CFG$ is $X$. The $j$th operand of a $\phi$-function in $Y$ corresponds to the $j$th predecessor of $Y$ from the listing of the inedges of $Y$. —Each assignment statement $A$ has the form

where the right-hand side $RHS(A)$ is a tuple of expressions and the left-hand side $LHS(A)$ is a tuple of distinct target variables. These tuples change as mentions of variables are renamed, but the original target tuple is still remembered as $oldLHS(A)$. To minimize notation, a conditional branch is treated as an ordinary assignment to a special variable whose value indicates which edge the branch should follow. A real implementation would recognize that a conditional branch involves a little less work than a genuine assignment: The $LHS$ part of the processing can be omitted.

            
              for each variable V do
    C(V) ← 0
    S(V) ← EmptyStack
end
call SEARCH(Entry)
            
          

SEARCH($X$) : for each statement $A$ in $X$ do if $A$ is an ordinary assignment then for each variable $V$ used in $RHS(A)$ do replace use of $V$ by use of $V_i$, where $i = Top(S(V))$ end for each $V$ in $LHS(A)$ do $i \leftarrow C(V)$ replace $V$ by new $V_i$ in $LHS(A)$ push $i$ onto $S(V)$ $C(V) \leftarrow i + 1$ end end / of first loop / for each $Y \in Succ(X)$ do $j \leftarrow WhichPred(Y, X)$ for each $\phi$-function $F$ in $Y$ do replace the $j$-th operand $V$ in $RHS(F)$ by $V_i$ where $i = Top(S(V))$ end end for each $Y \in Children(X)$ do call SEARCH(Y) end end for each assignment $A$ in $X$ do for each $V$ in $oldLHS(A)$ do pop $S(V)$ end end end SEARCH

Fig. 12 Renaming mentions of variables. The list of uses of $V_i$ grows with each replacement of $V$ by $V_i$ in a $RHS$

The processing of an assignment statement $A$ considers the mentions of variables in $A$. The simplest case is that of a target variable $V$ in the tuple $LHS(A)$. We need a new variable $V_i$. By keeping a count $C(V)$ of the number of assignments to $V$ that have already been processed, we can find an appropriate new variable by using $i = C(V)$ and then incrementing $C(V)$. To facilitate renaming uses of $V$ in the future, we also push $i$ (which identifies $V_i$) onto a stack $S(V)$ of (integers that identify) new variables replacing $V$.

A subtler computation is needed for the right-hand side $RHS(A)$. Consider any variable $V$ used in $RHS(A)$; that is, $V$ appears in at least one of the expressions in the tuple. We want to replace $V$ by $V_i$, where $V_i$ is the target of the assignment that produces the value for $V$ actually used in $RHS(A)$. There are two subcases because $A$ may be either an ordinary assignment or a $\phi$-function. Both subcases get $V_i$ from the top of the stack $S(V)$, but they inspect $S(V)$ at different times in Figure 12. Lemma 10, introduced later in this section, shows that $V_i$ is correctly chosen in both subcases.

The correctness proof for renaming depends on results from Section 4 and on three more lemmas. We start by showing that it makes sense to speak of "the" assignment to a variable in the transformed program.

Lemma 8. Each new variable $V_i$ in the transformed program is a target of exactly one assignment.

Proof. Because the counter $C(V)$ is incremented after processing each assignment to $V$, there can be at most one assignment to $V_i$. To show that there is at least one assignment to $V_i$, we consider the two ways $V_i$ can be mentioned. If $V_i$ is mentioned on the LHS on an assignment, then there is nothing more to show. If the value of $V_i$ is used, on the other hand, then $i = Top(S(V))$ was true at the time when the algorithm renamed the old use of $V$ to a use of $V_i$. At the earlier time when $i$ was pushed onto $S(V)$, it was pushed because an assignment to $V$ had just been changed to an assignment to $V_i$.

A node $X$ may contain assignments to the variable $V$ that appeared in the original program or were introduced to receive the value of a $\phi$-function for $V$. Let $TopAfter(V, X)$ denote the new variable in effect for $V$ after all statements in node $X$ have been considered by the first loop in Figure 12. Specifically, we consider the top of each stack $S(V)$ at the end of this loop and define

If there are no assignments to $V$ in $X$, then the top-down traversal ensures that $TopAfter(V, X)$ is inherited from the closest dominator of $X$ that assigns to $V$.

Lemma 9. For any variable $V$ and any CFG edge $X \to Y$ such that $Y$ does not have a $\phi$-function for $V$,

Proof. We may assume that $X \neq idom(Y)$. Because $Y$ does not have a $\phi$-function for $V$, if a node $Z$ has $Y \in DF(Z)$, then $Z$ does not assign to a new variable derived from $V$. We use this fact twice below.

By Lemma 2, $Y \in DF_{local}(X) \subseteq DF(X)$, and, thus, $X$ does not assign to a new variable derived from $V$. Let $U$ be the first node in the sequence $idom(X), idom(idom(X)), \ldots$ that assigns to such a variable. Then

Because $U$ assigns to a new variable derived from $V$, it follows that $Y \notin DF(U)$. But $U$ dominates a predecessor of $Y$, so $U$ strictly dominates $Y$. For any $Z$ with $U \gg Z \gg idom(Y)$, we get $Z \gg X$ because $Z \gg Y$ and there is an edge $X \to Y$. By the choice of $U, U \gg Z \gg X$ implies that $Z$ does not assign to a new variable derived from $V$. Therefore,

and (8) follows from (9).

The preceding lemma helps establish Condition (3) in the definition of SSA form, but first we must extend $TopAfter$ so as to specify which new variable corresponds to $V$ just before and just after each statement $A$. There is one iteration of the first loop in Figure 12 for $A$. We consider the top of each stack just before and just after this iteration to define