Next-Use Information
Introduction: Knowing when the value of a variable will be used next is essential for generating good code. If the value of a variable that is currently in a register will never be referenced subsequently, then that register can be assigned to another variable.
The use of a name in a three-address statement is defined as follows. Suppose three-address statement i assigns a value to x. If statement j has x as an operand, and control can flow from statement i to j along a path that has no intervening assignments to x, then we say statement j uses the value of x computed at statement i. We further say that x is live at statement i.
We wish to determine for each three-address statement x = y z what the next uses of x, y, and z are. For the present, we do not concern ourselves with nuses outside the basic block containing this three-address statement.
Our algorithm to determine liveness and next-use information makes a backward pass over each basic block. We store the information in the symbol table.
We can easily scan a stream of three-address statements to find the ends of basic blocks as in Algorithm 8.5. Since procedures can have arbitrary side effects, we assume for convenience that each procedure call starts a new basic block.
Algorithm: Determining the liveness and next-use information for each statement in a basic block.
INPUT: A basic block B of three-address statements. We assume that the symbol table initially shows all non-temporary variables in B as being live on exit.
OUTPUT: At each statement i: x = y z in B, we attach to i the liveness and next-use information of x, y, and z.
METHOD: We start at the last statement in B and scan backwards to the beginning of B. At each statement i: x = y z in B, we do the following:
1. Attach to statement i the information currently found in the symbol table regarding the next use and liveness of x, y, and y.
2. In the symbol table, set x to "not live" and "no next use."
3. In the symbol table, set y and z to "live" and the next uses of y and z to i.
Here we have used as a symbol representing any operator. If the three-address statement i is of the form x = y or x = y, the steps are the same as above, ignoring z. Note that the order of steps (2) and (3) may not be interchanged because x may be y or z.
Flow Graphs
Once an intermediate-code program is partitioned into basic blocks, we represent the flow of control between them by a flow graph. The nodes of the flow graph are the basic blocks. There is an edge from block B to block C if and only if it is possible for the first instruction in block C to immediately follow the last instruction in block B. There are two ways that such an edge could be justified:
• There is a conditional or unconditional jump from the end of B to the beginning of C.
• C immediately follows B in the original order of the three-address instructions, and B does not end in an unconditional jump.
We say that B is a predecessor of C, and C is a successor of B. Often we add two nodes, called the entry and exit, that do not correspond to executable intermediate instructions. There is an edge from the entry to the first executable node of the flow graph, that is, to the basic block that comes from the first instruction of the intermediate code. There is an edge to the exit from any basic block that contains an instruction that could be the last executed instruction of the program. If the final instruction of the program is not an unconditional jump, then the block containing the final instruction of the program is one predecessor of the exit, but so is any basic block that has a jump to code that is not part of the program.
Example: The set of basic blocks constructed in Example 8.6 yields the flow graph of Fig. 8.9. The entry points to basic block B\, since B\ contains the first instruction of the program. The only successor of B\ is B2, because B\ does not end in an unconditional jump, and the leader of B2 immediately follows the end of B\.
Block B3 has two successors. One is itself, because the leader of B3, instruction 3, is the target of the conditional jump at the end of £3, instruction 9. The other successor is B4, because control can fall through the conditional jump at the end of B3 and next enter the leader of B±.
Only BQ points to the exit of the flow graph, since the only way to get to code that follows the program from which we constructed the flow graph is to fall through the conditional jump that ends BG.