The Lazy-Code-Motion Problem
Introduction: It is desirable for programs optimized with a partial-redundancy-elimination algorithm to have the following properties:
1. All redundant computations of expressions that can be eliminated without code duplication are eliminated.
2. The optimized program does not perform any computation that is not in the original program execution.
3. Expressions are computed at the latest possible time.
The last property is important because the values of expressions found to be redundant are usually held in registers until they are used. Computing a value as late as possible minimizes its lifetime — the duration between the time the value is defined and the time it is last used, which in turn minimizes its usage of a register. We refer to the optimization of eliminating partial redundancy with the goal of delaying the computations as much as possible as lazy code motion.
To build up our intuition of the problem, we first discuss how to reason about partial redundancy of a single expression along a single path. For convenience, we assume for the rest of the discussion that every statement is a basic block of its own.
- Full Redundancy: An expression e in block B is redundant if along all paths reaching B, e has been evaluated and the operands of e have not been redefined subsequently. Let S be the set of blocks, each containing expression e, that renders e in B redundant. The set of edges leaving the blocks in S must necessarily form a cutset, which if removed, disconnects block B from the entry of the program. Moreover, no operands of e are redefined along the paths that lead from the n blocks in S to B.
- Partial Redundancy: If an expression e in block B is only partially redundant, the lazy-code-motion algorithm attempts to render e fully redundant in B by placing additional copies of the expressions in the flow graph. If the attempt is successful, the optimized flow graph will also have a set of basic blocks 5, each containing expression e, and whose outgoing edges are a cutset between the entry and B. Like the fully redundant case, no operands of e are redefined along the paths that lead from the blocks in S to B.
- Anticipation of Expressions: There is an additional constraint imposed on inserted expressions to ensure that no extra operations are executed. Copies of an expression must be placed only at program points where the expression is anticipated. We say that an expression b c is anticipated at point p if all paths leading from the point p eventually compute the value of the expression b c from the values of b and c that are available at that point.
Let us now examine what it takes to eliminate partial redundancy along an acyclic path Bi - B2 -»...-» Bn. Suppose expression e is evaluated only in blocks B\ and Bn, and that the operands of e are not redefined in blocks along the path. There are incoming edges that join the path and there are outgoing edges that exit the path. We see that e is not anticipated at the entry of block Bi if and only if there exists an outgoing edge leaving block Bj, i < j < n, that leads to an execution path that does not use the value of e. Thus, anticipation limits how early an expression can be inserted. We can create a cutset that includes the edge B^i - Bi and that renders e redundant in Bn if e is either available or anticipated at the entry of Bi. If e is anticipated but not available at the entry of Bi, we must place a copy of the expression e along the incoming edge.
We have a choice of where to place the copies of the expression, since there are usually several cutsets in the flow graph that satisfy all the requirements. In the above, computation is introduced along the incoming edges to the path of interest and so the expression is computed as close to the use as possible, without introducing redundancy. Note that these introduced operations may themselves be partially redundant with other instances of the same expression in the program. Such partial redundancy may be eliminated by moving these computations further up.
In summary, anticipation of expressions limits how early an expression can be placed; you cannot place an expression so early that it is not anticipated where you place it. The earlier an expression is placed, the more redundancy can be removed, and among all solutions that eliminate the same redundancies, the one that computes the expressions the latest minimizes the lifetimes of the registers holding the values of the expressions involved.