|
Dataflow analysis examines how information flows through a flowgraph from one block to another.
A variable is live at a particular point in a basic block if its value might be used later, on some path in the flowgraph.
A variable might be stored in a register while a basic block is being computed, to be stored back into memory at the end of the block. But a variable that is not live does not need to be stored.
Performing a liveness analysis is fairly simple using the following concepts.
in[B] is the set of all variables that are live at entry to basic block B.
out[B] is the set of all variables that are live at the end of basic block B.
def[B] is the set of all variables that are assigned new values in basic block B before they are used in B.
use[B] is the set of all variables that are used in B before they are assigned any value.
Because of the straight-line nature of a basic block, computing def[B] and use[B] is straightforward. Start with both sets empty and sweep through B. At instruction x = y + z:
If y is not in def[B] then add y to use[B]. Do similarly for z.
If x is not in use[B] then add x to def[B].
A successor of basic block B is any basic block A where there is an edge pointing from B to A. Define succ[B] to be the set of all successors of B.
in[B] and out[B] satisfy the following equations.
| in[exit] | = | ∅ |
| in[B] | = | use[B] ∪ (out[B] − def[B]) |
| out[B] | = | ∪S ∈ succ[B] in[S]) |
To compute in[B] and out[B], begin with in[B] = out[B] = ∅ for all blocks B.
The final in[B] and out[B] sets are computed using fixed-point iteration. Using the above equations, compute new values for in[B] and out[B] based on the old values. Keep doing that until no change occurs.
Dataflow analysis is what allows a compiler to detect use of a variable before it is defined.
The Dragon Book shows how to do that in Section 9.2.4.
|