Previous Next 
Liveness of variables "flows" around the edges of the controlflow graph; determining the live range of each variable is an example of a dataflow problem. will discuss several other kinds of dataflow problems. Flowgraph terminology A flowgraph node has outedges that lead to successor nodes, and inedges that come from predecessor nodes. The set pred[n] is all the predecessors of node n, and succ[n] is the set of successors. In Graph 10.1 the outedges of node 5 are 5 → 6 and 5 → 2, and succ[5] = {2, 6}. The inedges of 2 are 5 → 2 and 1 → 2, and pred[2] = {1, 5}. Uses and defs An assignment to a variable or temporary defines that variable. An occurrence of a variable on the righthand side of an assignment (or in other expressions) uses the variable. We can speak of the def of a variable as the set of graph nodes that define it; or the def of a graph node as the set of variables that it defines; and similarly for the use of a variable or graph node. In Graph 10.1, def(3) = {c}, use(3) = {b, c}. Liveness A variable is live on an edge if there is a directed path from that edge to a use of the variable that does not go through any def. A variable is livein at a node if it is live on any of the inedges of that node; it is liveout at a node if it is live on any of the outedges of the node.
Liveness information (livein and liveout) can be calculated from use and def as follows:
If a variable is in use[n], then it is livein at node n. That is, if a statement uses a variable, the variable is live on entry to that statement.
These three statements can be written as Equations 10.3 on sets of variables. The livein sets are an array in[n] indexed by node, and the liveout sets are an array out[n]. That is, in[n] is all the variables in use[n], plus all the variables in out[n] and not in def [n]. And out[n] is the union of the livein sets of all successors of n.
EQUATIONS 10.3: Dataflow equations for liveness analysis.Algorithm 10.4 finds a solution to these equations by iteration. As usual, we initialize in[n] and out[n] to the the empty set {}, forall n, then repeatedly treat the equations as assignment statements until a fixed point is reached.
ALGORITHM 10.4: Computation of liveness by iteration.for each n
in[n] {}; out[n] {}
repeat
for each n
in′[n] → in[n]; out′[n] ← out[n]
in[n] ← use[n] ∪ (out[n] − def[n])
out[n] ← ∪_{s∈succ[n]}in[s]
until in′[n] = in[n] and out′[n] = out[n] for all n
Table 10.5 shows the results of running the algorithm on Graph 10.1. The columns 1st, 2nd, etc., are the values of in and out on successive iterations of the repeat loop. Since the 7th column is the same as the 6th, the algorithm terminates.
1st 
2nd 
3rd 
4th 
5th 
6th 
7th 


use 
def 
in 
out 
in 
out 
in 
out 
in 
out 
in 
out 
in 
out 
in 
out 



1 
a 
a 
a 
ac 
c 
ac 
c 
ac 
c 
ac 

2 
a 
b 
a 
a 
bc 
ac 
bc 
ac 
bc 
ac 
bc 
ac 
bc 
ac 
bc 

3 
bc 
c 
bc 
bc 
b 
bc 
b 
bc 
b 
bc 
b 
bc 
bc 
bc 
bc 

4 
b 
a 
b 
b 
a 
b 
a 
b 
ac 
bc 
ac 
bc 
ac 
bc 
ac 

5 
a 
a 
a 
a 
ac 
ac 
ac 
ac 
ac 
ac 
ac 
ac 
ac 
ac 
ac 

6 
c 
c 
c 
c 
c 
c 
c 
c 
We can speed the convergence of this algorithm significantly by ordering the nodes properly. Suppose there is an edge 3 → 4 in the graph. Since in[4] is computed from out[4], and out[3] is computed from in[4], and so on, we should compute the in and out sets in the order out[4] → in[4] → out[3] → in[3]. But in Table 10.5, just the opposite order is used in each iteration! We have waited as long as possible (in each iteration) to make use of information gained from the previous iteration. Table 10.6 shows the computation, in which each for loop iterates from 6 to 1 (approximately following the reversed direction of the flowgraph arrows), and in each iteration the out sets are computed before the in sets. By the end of the second iteration, the fixed point has been found; the third iteration just confirms this.
1st 
2nd 
3rd 


use 
def 
out 
in 
out 
in 
out 
in 



6 
c 
c 
c 
c 

5 
a 
c 
ac 
ac 
ac 
ac 
ac 

4 
b 
a 
ac 
bc 
ac 
bc 
ac 
bc 
3 
bc 
c 
bc 
bc 
bc 
bc 
bc 
bc 
2 
a 
b 
bc 
ac 
bc 
ac 
bc 
ac 
1 
a 
ac 
c 
ac 
c 
ac 
c 
When solving dataflow equations by iteration, the order of computation should follow the "flow." Since liveness flows backward along controlflow arrows, and from "out" to "in", so should the computation. Ordering the nodes can be done easily by depthfirst search, as shown in . Basic blocks Flowgraph nodes that have only one predecessor and one successor are not very interesting. Such nodes can be merged with their predecessors and successors; what results is a graph with many fewer nodes, where each node represents a basic block. The algorithms that operate on flow graphs, such as liveness analysis, go much faster on the smaller graphs. explains how to adjust the dataflow equations to use basic blocks. In this chapter we keep things simple. One variable at a time Instead of doing dataflow "in parallel" using set equations, it can be just as practical to compute dataflow for one variable at a time as information about that variable is needed. For liveness, this would mean repeating the dataflow traversal once for each temporary. Starting from each use site of a temporary t, and tracing backward (following predecessor edges of the flow graph) using depthfirst search, we note the liveness of t at each flowgraph node. The search stops at any definition of the temporary. Although this might seem expensive, many temporaries have very short live ranges, so the searches terminate quickly and do not traverse the entire flow graph for most variables.
There are at least two good ways to represent sets for dataflow equations: as arrays of bits or as sorted lists of variables. If there are N variables in the program, the bitarray representation uses N bits for each set. Calculating the union of two sets is done by oring the corresponding bits at each position. Since computers can represent K bits per word (with K = 32 typical), one setunion operation takes N/K operations. A set can also be represented as a linked list of its members, sorted by any totally ordered key (such as variable name). Calculating the union is done by merging the lists (discarding duplicates). This takes time proportional to the size of the sets being unioned.
Clearly, when the sets are sparse (fewer than N/K elements, on the average), the sortedlist representation is asymptotically faster; when the sets are dense, the bitarray representation is better.
How fast is iterative dataflow analysis? A program of size N has at most N nodes in the flow graph, and at most N variables. Thus, each livein set (or liveout set) has at most N elements; each setunion operation to compute livein (or liveout) takes O(N) time. The for loop computes a constant number of set operations per flowgraph node; there are O(N) nodes; thus, the for loop takes O(N^{2}) time. Each iteration of the repeat loop can only make each in or out set larger, never smaller. This is because the in and out sets are monotonic with respect to each other. That is, in the equation in[n] = use[n]∪(out[n]−def[n]), a larger out[n] can only make in[n] larger. Similarly, in out[n] = ∪_{s∈succ[n]}in[s], a larger in[s] can only make out[n] larger. Each iteration must add something to the sets; but the sets cannot keep growing infinitely; at most every set can contain every variable. Thus, the sum of the sizes of all in and out sets is 2N^{2}, which is the most that the repeat loop can iterate. Thus, the worstcase run time of this algorithm is O(N^{4}). Ordering the nodes using depthfirst search (Algorithm 17.5, page 363) usually brings the number of repeatloop iterations to two or three, and the live sets are often sparse, so the algorithm runs between O(N) and O(N^{2}) in practice.
discusses more sophisticated ways of solving dataflow equations quickly.
Table 10.7 illustrates two solutions (and a nonsolution!) to the Equations 10.3; assume there is another program variable d not used in this fragment of the program.
X 
Y 
Z 


use 
def 
in 
out 
in 
out 
in 
out 

1 
a 
c 
ac 
cd 
acd 
c 
ac 

2 
a 
b 
ac 
bc 
acd 
bcd 
ac 
b 
3 
bc 
c 
bc 
bc 
bcd 
bcd 
b 
b 
4 
b 
a 
bc 
ac 
bcd 
acd 
b 
ac 
5 
a 
ac 
ac 
acd 
acd 
ac 
ac 

6 
c 
c 
c 
c 
In solution Y, the variable d is carried uselessly around the loop. But in fact, Y satisfies Equations 10.3 just as X does. What does this mean? Is d live or not? The answer is that any solution to the dataflow equations is a conservative approximation. If the value of variable a will truly be needed in some execution of the program when execution reaches node n of the flow graph, then we can be assured that a is liveout at node n in any solution of the equations. But the converse is not true; we might calculate that d is liveout, but that doesn't mean that its value will really be used. Is this acceptable? We can answer that question by asking what use will be made of the dataflow information. In the case of liveness analysis, if a variable is thought to be live, then we will make sure to have its value in a register. A conservative approximation of liveness is one that may erroneously believe a variable is live, but will never erroneously believe it is dead. The consequence of a conservative approximation is that the compiled code might use more registers than it really needs; but it will compute the right answer. Consider instead the livein sets Z, which fail to satisfy the dataflow equations. Using this Z we think that b and c are never live at the same time, and we would assign them to the same register. The resulting program would use an optimal number of registers but compute the wrong answer. A dataflow equation used for compiler optimization should be set up so that any solution to it provides conservative information to the optimizer; imprecise information may lead to suboptimal but never incorrect programs. Theorem Equations 10.3 have more than one solution. Proof X and Y are both solutions. Theorem All solutions to Equations 10.3 contain solution X. That is, if in_{X} [n] and in_{Y} [n] are the livein sets for some node n in solutions X and Y, then in_{X} [n] ⊆ in_{Y} [n]. Proof See Exercise 10.2.
We say that X is the least solution to Equations 10.3. Clearly, since a bigger solution will lead to using more registers (producing suboptimal code), we want to use the least solution. Fortunately, Algorithm 10.4 always computes the least fixed point.
A variable is live "if its value will be used in the future." In Graph 10.8, we know that b × b must be nonnegative, so that the test c ≥ b will be true. Thus, node 4 will never be reached, and a's value will not be used after node 2; a is not liveout of node 2.
GRAPH 10.8: Standard static dataflow analysis will not take advantage of the fact that node 4 can never be reached.But Equations 10.3 say that a is livein to node 4, and therefore liveout of nodes 3 and 2. The equations are ignorant of which way the conditional branch will go. "Smarter" equations would permit a and c to be assigned the same register. Although we can prove here that b*b ≥ 0, and we could have the compiler look for arithmetic identities, no compiler can ever fully understand how all the control flow in every program will work. This is a fundamental mathematical theorem, derivable from the halting problem. Theorem There is no program H that takes as input any program P and input X and (without infinitelooping) returns true if P(X) halts and false if P(X) infiniteloops. Proof Suppose that there were such a program H; then we could arrive at a contradiction as follows. From the program H, construct the function F,
By the definition of H, if F(F) halts, then H(F, F) is true; so the then clause is taken; so the while loop executes forever; so F(F) does not halt. But if F(F) loops forever, then H(F, F) is false; so the else clause is taken; so F(F) halts. The program F(F) halts if it doesn't halt, and doesn't halt if it halts: a contradiction. Thus there can be no program H that tests whether another program halts (and always halts itself). Corollary No program H′(X, L) can tell, for any program X and label L within X, whether the label L is ever reached on an execution of X. Proof From H′ we could construct H. In some program that we want to test for halting, just let L be the end of the program, and replace all instances of the halt command with goto L. Conservative approximation This theorem does not mean that we can never tell if a given label is reached or not, just that there is not a general algorithm that can always tell. We could improve our liveness analysis with some specialcase algorithms that, in some cases, calculate more information about runtime control flow. But any such algorithm will come up against many cases where it simply cannot tell exactly what will happen at run time. Because of this inherent limitation of program analysis, no compiler can really tell if a variable's value is truly needed  whether the variable is truly live. Instead, we have to make do with a conservative approximation. We assume that any conditional branch goes both ways. Thus, we have a dynamic condition and its static approximation:
Dynamic liveness Avariable a is dynamically live at node n if some execution of the program goes from n to a use of a without going through any definition of a.
Clearly, if a is dynamically live, it is also statically live. An optimizing compiler must allocate registers, and do other optimizations, on the basis of static liveness, because (in general) dynamic liveness cannot be computed.
Liveness information is used for several kinds of optimizations in a compiler. For some optimizations, we need to know exactly which variables are live at each node in the flow graph. One of the most important apps of liveness analysis is for register allocation: We have a set of temporaries a, b, c,… that must be allocated to registers r_{1},…, r_{k}. A condition that prevents a and b from being allocated to the same register is called an interference. The most common kind of interference is caused by overlapping live ranges: When a and b are both live at the same program point, then they cannot be put in the same register. But there are some other causes of interference: for example, when a must be generated by an instruction that cannot address register r_{1}, then a and r_{1} interfere. Interference information can be expressed as a matrix; Image 10.9a has an x marking interferences of the variables in Graph 10.1. The interference matrix can also be expressed as an undirected graph (Image 10.9b), with a node for each variable, and edges connecting variables that interfere.
Special treatment of MOVE instructions In static liveness analysis, we can give MOVE instructions special consideration. It is important not to create artifical interferences between the source and destination of a move. Consider the program:
After the copy instruction both s and t are live, and normally we would make an interference edge (s, t) since t is being defined at a point where s is live. But we do not need separate registers for s and t, since they contain the same value. The solution is just not to add an interference edge (t, s) in this case. Of course, if there is a later (nonmove) definition of t while s is still live, that will create the interference edge (t, s). Therefore, the way to add interference edges for each new definition is
At any nonmove instruction that defines avariable a, where the liveout variables are b_{1},…, b_{j}, add interference edges (a, b_{1}),…,(a, b_{j}).
JaVa  Previous Next 