The classic algorithms for eliminating useless code operate in a manner similar to mark-sweep garbage collectors with the IR code as data (see Section 6.6.2). Like mark-sweep collectors, they perform two passes over the code. The first pass starts by clearing all the mark fields and marking “critical” operations as “useful.” An operation is critical if it sets return values for the procedure, it is an input/output statement, or it affects the value in a storage location that may be accessible from outside the current procedure. Examples of critical operations include a procedure's prologue and epilogue code and the precall and postreturn sequences at calls. Next, the algorithm traces the operands of useful operations back to their definitions and marks those operations as useful. This process continues, in a simple worklist iterative scheme, until no more operations can be marked as useful. The second pass walks the code and removes any operation not marked as useful.

Figure 10.1 makes these ideas concrete. The algorithm, which we call Dead, assumes that the code is in ssa form. ssa simplifies the process because each use refers to a single definition. Dead consists of two passes. The first, called Mark, discovers the set of useful operations. The second, called Sweep, removes useless operations. Mark relies on reverse dominance frontiers, which derive from the dominance frontiers used in the ssa construction (see Section 9.3.2).

The treatment of operations other than branches or jumps is straightforward. The marking phase determines whether an operation is useful. The sweep phase removes operations that have not been marked as useful.

The treatment of control-flow operations is more complex. Every jump is considered useful. Branches are considered useful only if the execution of a useful operation depends on their presence. As the marking phase discovers useful operations, it also marks the appropriate branches as useful. To map from a marked operation to the branches that it makes useful, the algorithm relies on the notion of control dependence.

The definition of control dependence relies on postdominance. In a cfg, node j postdominates node i if every path from i to the cfg's exit node passes through j. Using postdominance, we can define control dependence as follows: in a cfg, node j is control-dependent on node i if and only if

In other words, two or more edges leave block i. One or more edges leads to j and one or more edges do not. Thus, the decision made at the branch-ending block i can determine whether or not j executes. If an operation in j is useful, then the branch that ends i is also useful.

This notion of control dependence is captured precisely by the reverse dominance frontier of j, denoted rdf( j). Reverse dominance frontiers are simply dominance frontiers computed on the reverse cfg. When Mark marks an operation in block b as useful, it visits every block in b's reverse dominance frontier and marks their block-ending branches as useful. As it marks these branches, it adds them to the worklist. It halts when that worklist is empty.

Sweep replaces any unmarked branch with a jump to its first postdominator that contains a marked operation. If the branch is unmarked, then its successors, down to its immediate postdominator, contain no useful operations. (Otherwise, when those operations were marked, the branch would have been marked.) A similar argument applies if the immediate postdominator contains no marked operations. To find the nearest useful postdominator, the algorithm can walk up the postdominator tree until it finds a block that contains a useful operation. Since, by definition, the exit block is useful, this search must terminate.

After Dead runs, the code contains no useless computations. It may contain empty blocks, which can be removed by the next algorithm.

Optimization can change the ir form of the program so that it has useless control flow. If the compiler includes optimizations that can produce useless control flow as a side effect, then it should include a pass that simplifies the cfg by eliminating useless control flow. This section presents a simple algorithm called Clean that handles this task.

Clean operates directly on the procedure's cfg. It uses four transformations, shown in the margin. They are applied in the following order:

Some bookkeeping is required to implement these transformations. Some of the modifications are trivial. To fold a redundant branch in a program represented with iloc and a graphical cfg, Clean simply overwrites the block-ending branch with a jump and adjusts the successor and predecessor lists of the blocks. Others are more difficult. Merging two blocks may involve allocating space for the merged block, copying the operations into the new block, adjusting the predecessor and successor lists of the new block and its neighbors in the cfg, and discarding the two original blocks.

Clean applies these four transformations in a systematic fashion. It traverses the graph in postorder, so that B _i's successors are simplified before B _i, unless the successor lies along a back edge with respect to the postorder numbering. In that case, Clean will visit the predecessor before the successor. This is unavoidable in a cyclic graph. Simplifying successors before predecessors reduces the number of times that the implementation must move some edges.

In some situations, more than one of the transformations may apply. Careful analysis of the various cases leads to the order shown in Figure 10.2, which corresponds to the order in which they are presented in this section. The algorithm uses a series of if statements rather than an if-then-else to let it apply multiple transformations in a single visit to a block.

If the cfg contains back edges, then a pass of Clean may create additional opportunities—namely, unprocessed successors along the back edges. These, in turn, may create other opportunities. For this reason, Clean repeats the transformation sequence iteratively until the cfg stops changing. It must compute a new postorder numbering between calls to OnePass because each pass changes the underlying graph. Figure 10.2 shows pseudo-code for Clean.

Clean cannot, by itself, eliminate an empty loop. Consider the cfg shown in the margin. Assume that block B₂ is empty. None of Clean's transformations can eliminate B₂ because the branch that ends B₂ is not redundant. B₂ does not end with a jump, so Clean cannot combine it with B₃. Its predecessor ends with a branch rather than a jump, so Clean can neither combine B₂ with B₁ nor fold its branch into B₁.

However, cooperation between Clean and Dead can eliminate the empty loop. Dead used control dependence to mark useful branches. If B₁ and B₃ contain useful operations, but B₂ does not, then the Mark pass in Dead will decide that the branch ending B₂ is not useful because B₂ ∉ rdf( B₃). Because the branch is useless, the code that computes the branch condition is also useless. Thus, Dead eliminates all of the operations in B₂ and converts the branch that ends it into a jump to its closest useful postdominator, B₃. This eliminates the original loop and produces the cfg labelled “After Dead” in the margin.

In this form, Clean folds B₂ into B₁, to produce the cfg labelled “Remove B₂” in the margin. This action also makes the branch at the end of B₁ redundant. Clean rewrites it with a jump, producing the cfg labelled “Fold the Branch” in the margin. At this point, if B₁ is B₃'s sole remaining predecessor, Clean coalesces the two blocks into a single block.

This cooperation is simpler and more effective than adding a transformation to Clean that handles empty loops. Such a transformation might recognize a branch from B_i to itself and, for an empty B_i, rewrite it with a jump to the branch's other target. The problem lies in determining when B_i is truly empty. If B_i contains no operations other than the branch, then the code that computes the branch condition must lie outside the loop. Thus, the transformation is safe only if the self-loop never executes. Reasoning about the number of executions of the self-loop requires knowledge about the runtime value of the comparison, a task that is, in general, beyond a compiler's ability. If the block contains operations, but only operations that control the branch, then the transformation would need to recognize the situation with pattern matching. In either case, this new transformation would be more complex than the four included in Clean. Relying on the combination of Dead and Clean achieves the appropriate result in a simpler, more modular fashion.

Sometimes the cfg contains code that is unreachable. The compiler should find unreachable blocks and remove them. A block can be unreachable for two distinct reasons: there may be no path through the cfg that leads to the block, or the paths that reach the block may not be executable—for example, guarded by a condition that always evaluates to false.

The former case is easy to handle. The compiler can perform a simple mark-sweep-style reachability analysis on the cfg. First, it initializes a mark on each block to the value “unreachable.” Next, it starts with the entry and marks each cfg node that it can reach as “reachable.” If all branches and jumps are unambiguous, then all unmarked blocks can be deleted. With ambiguous branches or jumps, the compiler must preserve any block that the branch or jump can reach. This analysis is simple and inexpensive. It can be done during traversals of the cfg for other purposes or during cfg construction itself.

Handling the second case is harder. It requires the compiler to reason about the values of expressions that control branches. Section 10.7.1 presents an algorithm that finds some blocks that are unreachable because the paths leading to them are not executable.

Lazy code motion ( lcm) uses data-flow analysis to discover both operations that are candidates for code motion and locations where it can place those operations. The algorithm operates on the ir form of the program and its cfg, rather than on ssa form. The algorithm use three different sets of data-flow equations and derives additional sets from those results. It produces, for each edge in the cfg, a set of expressions that should be evaluated along that edge and, for each node in the cfg, a set of expressions whose upward-exposed evaluations should be removed from the corresponding block. A simple rewriting strategy interprets these sets and modifies the code.

lcm combines code motion with elimination of both redundant and partially redundant computations. Redundancy was introduced in the context of local and superlocal value numbering in Section 8.4.1. A computation is partially redundant at point p if it occurs on some, but not all, paths that reach p and none of its constituent operands changes between those evaluations and p. Figure 10.3 shows two ways that an expression can be partially redundant. In Figure 10.3a, a ← b × c occurs on one path leading to the merge point but not on the other. To make the second computation redundant, lcm inserts an evaluation of a ← b × c on the other path as shown in Figure 10.3b. In Figure 10.3c, a ← b × c is redundant along the loop's back edge but not along the edge entering the loop. Inserting an evaluation of a ← b × c before the loop makes the occurrence inside the loop redundant, as shown in Figure 10.3d. By making the loop-invariant computation redundant and eliminating it, lcm moves it out of the loop, an optimization called loopinvariant code motion when performed by itself.

The fundamental ideas that underlie lcm were introduced in Section 9.2.4. lcm computes both available expressions and anticipable expressions. Next, lcm uses the results of these analyses to annotate each cfg edge with a set Earliest( i, j) that contains the expressions for which this edge is the earliest legal placement. lcm then solves a third data-flow problem to find later placements, that is, situations where evaluating an expression after its earliest placement has the same effect. Later placements are desirable because they can shorten the lifetimes of values defined by the inserted evaluations. Finally, lcm computes its final products, two sets Insert and Delete, that guide its code-rewriting step.

Code motion techniques can also be used to reduce the size of the compiled code. A transformation called code hoisting provides one direct way of accomplishing this goal. It uses the results of anticipability analysis in a particularly simple way.

If an expression e ∈ A ntO ut(b), for some block b, that means that e is evaluated along every path that leaves b and that evaluating e at the end of b would make the first evaluation along each path redundant. (The equations for A ntO ut ensure that none of e's operands is redefined between the end of b and the next evaluation of e along each path leaving b.) To reduce code size, the compiler can insert an evaluation of e at the end of b and replace the first occurrence of e on each path leaving b with a reference to the previously computed value. The effect of this transformation is to replace multiple copies of the evaluation of e with a single copy, reducing the overall number of operations in the compiled code.

To replace those expressions directly, the compiler would need to locate them. It could insert e, then solve another data-flow problem, proving that the path from b to some evaluation of e is clear of definitions for e's operands. Alternatively, it could traverse each of the paths leaving b to find the first block where e is defined—by looking in the block's UE Expr set. Each of these approaches seems complicated.

A simpler approach has the compiler visit each block b and insert an evaluation of e at the end of b, for every expression e ∈ A ntO ut( b). If the compiler uses a uniform discipline for naming, as suggested in the discussion of lcm, then each evaluation will define the appropriate name. Subsequent application of lcm or superlocal value numbering will then remove the newly redundant expressions.

When the last action that a procedure takes is a call, we refer to that call as a tail call. The compiler can specialize tail calls to their contexts in ways that eliminate much of the overhead from the procedure linkage. To understand how the opportunity for improvement arises, consider what happens when o calls p and p calls q. When q returns, it executes its epilogue sequence and jumps back to p's postreturn sequence. Execution continues in p until p returns, at which point p executes its epilogue sequence and jumps to o's postreturn sequence.

If the call from p to q is a tail call, then no useful computation occurs between the postreturn sequence and the epilogue sequence in p. Thus, any code that preserves and restores p's state, beyond what is needed for the return from p to o, is useless. A standard linkage, as described in Section 6.5, spends much of its effort to preserve state that is useless in the context of a tail call.

At the call from p to q, the minimal precall sequence must evaluate the actual parameters at the call from p to q and adjust the access links or the display if necessary. It need not preserve any caller-saves registers, because they cannot be live. It need not allocate a new ar, because q can use p's ar. It must leave intact the context created for a return to o, namely the return address and caller's arp that o passed to p and any callee-saves registers that p preserved by writing them into the ar. (That context will cause the epilogue code for q to return control directly to o.) Finally, the precall sequence must jump to a tailored prologue sequence for q.

In this scheme, q must execute a custom prologue sequence to match the minimal precall sequence in p. It only saves those parts of p's state that allow a return to o. The precall sequence does not preserve callee-saves registers, for two reasons. First, the values from p in those registers are no longer live. Second, the values that p left in the ar's register-save area are needed for the return to o. Thus, the prologue sequence in q should initialize local variables and values that q needs; it should then branch into the code for q.

With these changes to the precall sequence in p and the prologue sequence in q, the tail call avoids preserving and restoring p's state and eliminates much of the overhead of the call. Of course, once the precall sequence in p has been tailored in this way, the postreturn and epilogue sequences are unreachable. Standard techniques such as Dead and Clean will not discover that fact, because they assume that the interprocedural jumps to their labels are executable. As the optimizer tailors the call, it can eliminate these dead sequences.

With a little care, the optimizer can arrange for the operations in the tailored prologue for q to appear as the last operations in its more general prologue. In this scheme, the tail call from p to q simply jumps to a point farther into the prologue sequence than would a normal call from some other routine.

If the tail call is a self-recursive call—that is, p and q are the same procedure—then tail-call optimization can produce particularly efficient code. In a tail recursion, the entire precall sequence devolves to argument evaluation and a branch back to the top of the routine. An eventual return out of the recursion requires one branch, rather than one branch per recursive invocation. The resulting code rivals a traditional loop for efficiency.

Some of the overhead involved in a procedure call arises from the need to prepare for calls that the callee might make. A procedure that makes no calls, called a leaf procedure, creates opportunities for specialization. The compiler can easily recognize the opportunity; the procedure calls no other procedures.

During translation of a leaf procedure, the compiler can avoid inserting operations whose sole purpose is to set up for subsequent calls. For example, the procedure prologue code may save the return address from a register into a slot in the ar. That action is unnecessary unless the procedure itself makes another call. If the register that holds the return address is needed for some other purpose, the register allocator can spill the value. Similarly, if the implementation uses a display to provide addressability for nonlocal variables, as described in Section 6.4.3, it can avoid the display update in the prologue sequence.

The register allocator should try to use caller-saves registers before callee-saves registers in a leaf procedure. To the extent that it can leave callee-saves registers untouched, it can avoid the save and restore code for them in the prologue and epilogue. In small leaf procedures, the compiler may be able to avoid all use of callee-saves registers. If the compiler has access to both the caller and the callee, it can do better; for leaf procedures that need fewer registers than the caller-save set includes, it can avoid some of the register saves and restores in the caller as well.

In addition, the compiler can avoid the runtime overhead of activation-record allocation for leaf procedures. In an implementation that heap allocates ars, that cost can be significant. In an application with a single thread of control, the compiler can allocate statically the ar of any leaf procedure. A more aggressive compiler might allocate one static ar that is large enough to work for any leaf procedure and have all the leaf procedures share that ar.

If the compiler has access to both the leaf procedure and its callers, it can allocate space for the leaf procedure's ar in each of its callers’ ars. This scheme amortizes the cost of ar allocation over at least two calls—the invocation of the caller and the call to the leaf procedure. If the caller invokes the leaf procedure multiple times, the savings are multiplied.

Ambiguous memory references prevent the compiler from keeping values in registers. Sometimes, the compiler can prove that an ambiguous value has just one corresponding memory location through detailed analysis of pointer values or array subscript values, or special case analysis. In these cases, it can rewrite the code to move that value into a scalar local variable, where the register allocator can keep it in a register. This kind of transformation is often called promotion. The analysis to promote array references or pointer-based references is beyond the scope of this book. However, a simpler case can illustrate these transformations equally well.

Consider the code generated for an ambiguous call-by-reference parameter. Such parameters can arise in many ways. The code might pass the same actual parameter in two distinct parameter slots, or it might pass a global variable as an actual parameter. Unless the compiler performs interprocedural analysis to rule out those possibilities, it must treat all reference parameters as potentially ambiguous. Thus, every use of the parameter requires a load and every definition requires a store.

If the compiler can prove that the actual parameter must be unambiguous in the callee, it can promote the parameter's value into a local scalar value, which allows the callee to keep it in a register. If the actual parameter is not modified by the callee, the promoted parameter can be passed by value. If the callee modifies the actual parameter and the result is live in the caller, then the compiler must use value-result semantics to pass the promoted parameter (see Section 6.4.1).

To apply this transformation to a procedure p, the optimizer must identify all of the call sites that can invoke p. It can either prove that the transformation applies at all of those call sites or it can clone p to create a copy that handles the promoted values (see Section 10.6.2). Parameter promotion is most attractive in a language that uses call-by-reference binding.

lvn introduced a simple mechanism to prove that two expressions had the same value. lvn relies on two principles. It assigns each value a unique identifying number—its value number. It assumes that two expressions produce the same value if they have the same operator and their operands have the same value numbers. These simple rules allow lvn to find a broad class of redundant operations—any operation that produces a pre-existing value number is redundant.

With these rules, lvn can prove that 2 + a has the same value as a + 2 or as 2 + b when a and b have the same value number. It cannot prove that a + a and 2 × a have the same value because they have different operators. Similarly, it cannot prove the a + 0 and a have the same value. Thus, we extend lvn with algebraic identities that can handle the well-defined cases not covered by the original rule. The table in Figure 8.3 on page 424 shows the range of identities that lvn can handle.

By contrast, lcm relies on names to prove that two values have the same number. If lcm sees a + b and a + c, it assumes that they have different values because b and c have different names. It has relies on a lexical comparison—name identity. The underlying data-flow analyses cannot directly accommodate the notion of value identity; data-flow problems operate a predefined name space and propagate facts about those names over the cfg. The kind of ad hoc comparisons used in lvn do not fit into the data-flow framework.

As described in Section 10.6.4, one way to improve the effectiveness of lcm is to encode value identity into the name space of the code before applying lcm. lcm recognizes redundancies that neither lvn nor svn can find. In particular, it finds redundancies that lie on paths through join points in the cfg, including those that flow along loop-closing branches, and it finds partial redundancies. On the other hand, both lvn and svn find value-based redundancies and simplifications that lcm cannot find. Thus, encoding value identity into the name space allows the compiler to take advantage of the strengths of both approaches.

Chapter 8 presented both local value numbering lvn and its extension to extended basic blocks ( Ebbs), called superlocal value numbering svn. While svn discovers more redundancies than lvn, it still misses some opportunities because it is limited to Ebbs. Recall that the svn algorithm propagates information along each path through an Ebb. For example, in the cfg fragment shown in the margin, svn will process the paths ( B₀, B₁, B₂) and ( B₀, B₁, B₃). Thus, it optimizes both B₂ and B₃ in the context of the prefix path ( B₀, B₁). Because B₄ forms its own degenerate Ebb, svn optimizes B₄ without prior context.

From an algorithmic point of view, svn begins each block with a table that includes the results of all predecessors on its Ebb path. Block B₄ has no predecessors, so it begins with no prior context. To improve on that situation, we must answer the question: on what state could B₄ rely? B₄ cannot rely on values computed in either B₂ or B₃, since neither lies on every path that reaches B₄. By contrast, B₄ can rely on values computed in B₀ and B₁, since they occur on every path that reaches B₄. Thus, we might extend value numbering for B₄ with information about computations in B₀ and B₁. We must, however, account for the impact of assignments in the intervening blocks, B₂ or B₃.

Consider an expression, x + y, that occurs at the end of B₁ and again at the start of B₄. If neither B₂ or B₃ redefines x or y, then the evaluation of x + y in B₄ is redundant and the optimizer can reuse the value computed in B₁. On the other hand, if either of those blocks redefines x or y, then the evaluation of x + y in B₄ computes a distinct value from the evaluation in B₁ and the evaluation is not redundant.

Fortunately, the ssa name space encodes precisely this distinction. In ssa, a name that is used in some block B _i can only enter B _i in one of two ways. Either the name is defined by a ϕ-function at the top of B _i, or it is defined in some block that dominates B _i. Thus, an assignment to x in either B₂ or B₃ creates a new name for x and forces the insertion of a ϕ-function for x at the head of B₄. That ϕ-function creates a new ssa name for x and the renaming process changes the ssa name used in the subsequent computation of x + y. Thus, ssa form encodes the presence or absence of an intervening assignment in B₂ or B₃ directly into the names used in the expression. Our algorithm can rely on ssa names to avoid this problem.

The other major question that we must answer before we can extend svn to larger regions is, given a block such as B₄, how do we locate the most recent predecessor with information that the algorithm can use? Dominance information, discussed at length in Section 9.2.1 and Section 9.3.2, captures precisely this effect. Dom( B₄) = { B₀, B₁, B₄}. B₄'s immediate dominator, defined as the node in ( Dom( B₄) − B₄) that is closest to B₄, is B₁, the last node that occurs on all path from the entry node B₀ to B₄.

The dominator-based value numbering technique dvnt builds on the ideas behind svn. It uses a scoped hash table to hold value numbers. dvnt opens a new scope for each block and discards that scope when they are no longer needed. dvnt actually uses ssa names as value numbers; thus the value number for an expression a_i × b_j is the ssa name defined in the first evaluation of a_i × b_j. (That is, if the first evaluation occurs in t_k ← a_i × b_j, then the value number for a_i × b_j is t_k.)

Figure 10.6 shows the algorithm. It takes the form of a recursive procedure that the optimizer invokes on a procedure's entry block. It follows both the cfg for the procedure, represented by the dominator tree, and the flow of values in the ssa form. For each block B, dvnt takes three steps: it processes the ϕ-functions in B, if any exist, it value numbers the assignments, and it propagates information into B's successors and recurs on B's children in the dominator tree.

Sometimes, reformulating two distinct optimizations in a unified framework and solving them jointly can produce results that cannot be obtained by any combination of the optimizations run separately. As an example, consider the sparse simple constant propagation ( sscp) algorithm described in Section 9.3.6. It assigns a lattice value to the result of each operation in the ssa form of the program. When it halts, it has tagged every definition with a lattice value that is either ⊤, ⊥, or a constant. A definition can have the value ⊤ only if it relies on an uninitialized variable or it occurs in an unreachable block.

sscp assigns a lattice value to the operand used by a conditional branch. If the value is ⊥, then either branch target is reachable. If the value is neither ⊥ nor ⊤, then the operand must have a known value and the compiler can rewrite the branch with a jump to one of its two targets, simplifying the cfg. Since this removes an edge from the cfg, it may make the block that was the branch target unreachable. Constant propagation can ignore any effects of an unreachable block. sscp has no mechanism to take advantage of this knowledge.

We can extend the sscp algorithm to capitalize on these observations. The resulting algorithm, called sparse conditional constant propagation ( sccp), appears in Figure 10.8, Figure 10.9 and Figure 10.10.

In concept, sccp operates in a straightforward way. It initializes the data structures. It iterates over two graphs, the cfg and the ssa graph. It propagates reachability information on the cfg and value information on the ssa graph. It halts when the value information reaches a fixed point; because the constant propagation lattice is so shallow, it halts quickly. Combining these two kinds of information, sccp can discover both unreachable code and constant values that the compiler simply could not discover with any combination of the sscp and unreachable code elimination.

To simplify the explanation of sccp, we assume that each block in the cfg represents just one statement, plus some optional ϕ-functions. A cfg node with a single predecessor holds either an assignment statement or a conditional branch. A cfg node with multiple predecessors holds a set of ϕ-functions, followed by an assignment or a conditional branch.

In detail, sccp is much more complex than either sscp or unreachable code elimination. Using two graphs introduces additional bookkeeping. Making the flow of values depend on reachability introduces additional work to the algorithm. The result is a powerful but complex algorithm.

The algorithm proceeds as follows. It initializes each Value field to ⊤ and marks each cfg edge as “unexecuted.” It initializes two worklists, one for cfg edges and the other for ssa graph edges. The cfg worklist receives the set of edges that leave the procedure's entry node, n₀. The ssa worklist receives the empty set.

After the initialization phase, the algorithm repeatedly picks an edge from one of the two worklists and processes that edge. For a cfg edge ( m, n), sccp determines if the edge is marked as executed. If ( m, n) is so marked, sccp takes no further action for ( m, n). If ( m, n) is marked as unexecuted, then sccp marks it as executed and evaluates all of the ϕ-functions at the start of block n. Next, sccp determines if block n has been previously entered along another edge. If it has not, then sccp evaluates the assignment or conditional branch in n. This processing may add edges to either worklist.

For an ssa edge, the algorithm first checks if the destination block is reachable. If the block is reachable, sccp calls one of EvaluatePhi, EvaluateAssign, or EvaluateConditional, based on the kind of operation that uses the ssa name. When sccp must evaluate an assignment or a conditional over the lattice of values, it follows the same scheme used in sscp, discussed in Section 9.3.6 on page 515. Each time the lattice value for a definition changes, all the uses of that name are added to the ssa worklist.

Because sccp only propagates values into blocks that it has already proved executable, it avoids processing unreachable blocks. Because each value propagation step is guarded by a test on the executable flag for the entering edge, values from unreachable blocks do not flow out of those blocks. Thus, values from unreachable blocks have no role in setting the lattice values in other blocks.

After the propagation step, a final pass is required to replace operations that have operands with Value tags other than ⊥. It can specialize many of these operations. It should also rewrite branches that have known outcomes with the appropriate jump operations. Later passes can remove the unreachable code (see Section 10.2). The algorithm cannot rewrite the code until the propagation completes.

Operator strength reduction is a transformation that replaces a repeated series of expensive (“strong”) operations with a series of inexpensive (“weak”) operations that compute the same values. The classic example replaces integer multiplications based on a loop index with equivalent additions. This particular case arises routinely from the expansion of array and structure addresses in loops. Figure 10.11a shows the iloc that might be generated for the following loop:

The code is in semipruned ssa form; the purely local values ( r ₂, r ₂, r ₃, and r ₄) have neither subscripts nor ϕ-functions. Notice how the reference to a(i) expands to four operations—the subI, multI, and addI that compute (i − 1) × 4 − @a and the load that defines r ₄.

For each iteration, this sequence of operations computes the address of a(i) from scratch as a function of the loop index variable i. Consider the sequences of values taken on by r _{i 1}, r ₁, r ₂, and r ₃.

r _{i 1}: {1, 2, 3, …, 100}

r ₁: {0, 1, 2, …, 99}

r ₂: {0, 4, 8, …, 396}

r ₃: { @a, @a+4, @a+8, …, @a+396}

The values in r ₁, r ₂, and r ₃ exist solely to compute the address for the load operation. If the program computed each value of r ₃ from the preceding one, it could eliminate the operations that define r ₁ and r ₂. Of course, r ₃ would then need an initialization and an update. This would make it a nonlocal name, so it would also need a ϕ-function at both l ₁ and l ₂.

Figure 10.11b shows the code after strength reduction, linear-function test replacement, and dead-code elimination. It computes those values formerly in r ₃ directly into r _{t 7} and uses r _{t 7} in the load operation. The end-of-loop test, which used r ₁ in the original code, has been modified to use r _{t 8}. This makes the computations of r ₁, r ₂, r ₃, r _{i 0}, r _{i 1}, and r _{i 2} all dead. They have been removed to produce the final code. Now, the loop contains just five operations, ignoring ϕ-functions, while the original code contained eight. (In translating from ssa form back to executable code, the ϕ-functions become copy operations that the register allocator can usually remove.)

If the multI operation is more expensive than an addI, the savings will be larger. Historically, the high cost of multiplication justified strength reduction. However, even if multiplication and addition have equal costs, the strength-reduced form of the loop may be preferred because it creates a better code shape for later transformations and for code generation. In particular, if the target machine has an autoincrement addressing mode, then the addI operation in the loop can be folded into the memory operation. This option simply does not exist for the original multiply.

The rest of this section presents a simple algorithm for strength reduction, which we call OSR, followed by a scheme for linear function test replacement that shifts end-of-loop tests away from variables that would otherwise be dead. OSR operates on the ssa form of the code, considered as a graph. Figure 10.12 shows the code for our example, alongside its ssa graph.

The effectiveness of an optimizer on any given code depends on the sequence of optimizations that it applies to the code—both the specific transformations that it uses and the order in which it applies them. Traditional optimizing compilers have offered the user the choice of several sequences (e.g. −O, −O1, −O2, …). Those sequences provide a tradeoff between compile time and the amount of optimization that the compiler attempts. Increased optimization effort, however, does not guarantee improvement.

The optimization sequence problem arises because the effectiveness of any given transformation depends on several factors.

The interactions between transformations makes it difficult to predict the improvement from the application of any single transformation or any sequence of transformations.

Some research compilers attempt to discover good optimization sequences. The approaches vary in granularity and in technique. The various systems have looked for sequences at the block level, at the source-file level, and at the whole-program level. Most of these systems have used some kind of search over the space of optimization sequences.

The space of potential optimization sequences is huge. For example, if the compiler chooses a sequence of length 10 from a pool of 15 transformations, it has 10 ¹⁵ possible sequences that it can generate—an impractically large number for the compiler to explore. Thus, compilers that search for good sequences use heuristic techniques to sample smaller portions of the search space. In general, these techniques fall into three categories: (1) genetic algorithms adapted to act as intelligent searches, (2) randomized search algorithms, and (3) statistical machine learning techniques. All three approaches have shown promise.

Despite the huge size of the search spaces, well-tuned search algorithms can find good optimization sequences with 100 to 200 probes of the search space. While that number is not yet practical, further refinement may reduce the number of probes to a practical level.

One interesting application of these techniques is to derive the sequences used by the compiler's command line flags, such as −O2. The compiler writer can use an ensemble of representative applications to discover good general sequences and then apply those sequences as the compiler's default sequences. A more aggressive approach, used in several systems, is to derive a handful of good sequences for different application ensembles and have the compiler try each of those sequences and retain the best result.