A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 37

Draw all the tree patterns corresponding to this instruction (and its specialcases).b. Pick one of the bigger patterns and show how to write a Java if-statement tomatch it, with the Tree representation used for the MiniJava compiler.9.3 The Jouette machine has control-flow instructions as follows:BRANCHGE if ri ≥ 0 goto LBRANCHLT if ri < 0 goto LBRANCHEQ if ri = 0 goto LBRANCHNE if ri ≠ 0 goto LJUMP••••goto riwhere the JUMP instruction goes to an address contained in a register.Use these instructions to implement the following tree patterns:Assume that a CJUMP is always followed by its false label.

Show the best way toimplement each pattern; in some cases you may need to use more than one instruction173or make up a new temporary. How do you implement CJUMP(GT, …) without aBRANCHGT instruction?174Chapter 10: Liveness Analysislive: of continuing or current interestWebster's DictionaryOVERVIEWThe front end of the compiler translates programs into an intermediate language with anunbounded number of temporaries.

This program must run on a machine with a boundednumber of registers. Two temporaries a and b can fit into the same register, if a and b arenever "in use" at the same time. Thus, many temporaries can fit in few registers; if they don'tall fit, the excess temporaries can be kept in memory.Therefore, the compiler needs to analyze the intermediate-representation program todetermine which temporaries are in use at the same time.

We say a variable is live if it holds avalue that may be needed in the future, so this analysis is called liveness analysis.To perform analyses on a program, it is often useful to make a control-flow graph. Eachstatement in the program is a node in the flow graph; if statement x can be followed bystatement y, there is an edge from x to y. Graph 10.1 shows the flow graph for a simple loop.GRAPH 10.1: Control-flow graph of a program.Let us consider the liveness of each variable (Figure 10.2). A variable is live if its currentvalue will be used in the future, so we analyze liveness by working from the future to the past.Variable b is used in statement 4, so b is live on the 3 → 4 edge. Since statement 3 does notassign into b, then b is also live on the 2 → 3 edge. Statement 2 assigns into b.

That means175that the contents of b on the 1 → 2 edge are not needed by anyone; b is dead on this edge. Sothe live range of b is {2 → 3, 3 → 4}.Figure 10.2: Liveness of variables a, b, c.The variable a is an interesting case. It's live from 1 → 2, and again from 4 → 5 → 2, but notfrom 2 → 3 → 4. Although a has a perfectly well-defined value at node 3, that value will notbe needed again before a is assigned a new value.The variable c is live on entry to this program. Perhaps it is a formal parameter. If it is a localvariable, then liveness analysis has detected an uninitialized variable; the compiler could printa warning message for the programmer.Once all the live ranges are computed, we can see that only two registers are needed to hold a,b, and c, since a and b are never live at the same time. Register 1 can hold both a and b, andregister 2 can hold c.10.1 SOLUTION OF DATAFLOW EQUATIONSLiveness of variables "flows" around the edges of the control-flow graph; determining the liverange of each variable is an example of a dataflow problem.

Chapter 17 will discuss severalother kinds of dataflow problems.Flow-graph terminology A flow-graph node has out-edges that lead to successor nodes, andin-edges that come from predecessor nodes. The set pred[n] is all the predecessors of node n,and succ[n] is the set of successors.176In Graph 10.1 the out-edges 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 occurrenceof a variable on the right-hand side of an assignment (or in other expressions) uses thevariable.

We can speak of the def of a variable as the set of graph nodes that define it; or thedef of a graph node as the set of variables that it defines; and similarly for the use of a variableor 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 thevariable that does not go through any def.

A variable is live-in at a node if it is live on any ofthe in-edges of that node; it is live-out at a node if it is live on any of the out-edges of thenode.CALCULATION OF LIVENESSLiveness information (live-in and live-out) can be calculated from use and def as follows:1. If a variable is in use[n], then it is live-in at node n. That is, if a statement uses avariable, the variable is live on entry to that statement.2. If a variable is live-in at a node n, then it is live-out at all nodes m in pred[n].3.

If a variable is live-out at node n, and not in def [n], then the variable is also live-in atn. That is, if someone needs the value of a at the end of statement n, and n does notprovide that value, then a's value is needed even on entry to n.These three statements can be written as Equations 10.3 on sets of variables. The live-in setsare an array in[n] indexed by node, and the live-out sets are an array out[n]. That is, in[n] isall the variables in use[n], plus all the variables in out[n] and not in def [n]. And out[n] is theunion of the live-in 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 assignmentstatements until a fixed point is reached.ALGORITHM 10.4: Computation of liveness by iteration.for each nin[n] {}; out[n] {}repeatfor each nin′[n] → in[n]; out′[n] ← out[n]in[n] ← use[n] U (out[n] − def[n])out[n] ← Us insucc[n]in[s]until in′[n] = in[n] and out′[n] = out[n] for all n177Table 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 7thcolumn is the same as the 6th, the algorithm terminates.Table 10.5: Liveness calculation following forward control-flow edges.1st2nd3rd4th5th6th7thdef in out in out in out in out in out in out in outuse123456abcaabcbacabcbacaabcbacabcbaacacbcbaccabcbaacacbcbaccacbcbacaccacbcbcaccacbcbacaccacbcbcaccacbcbcacaccacbcbcaccacbcbcacacWe 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 fromthe previous iteration.Table 10.6 shows the computation, in which each for loop iterates from 6 to 1 (approximatelyfollowing the reversed direction of the flow-graph arrows), and in each iteration the out setsare computed before the in sets. By the end of the second iteration, the fixed point has beenfound; the third iteration just confirms this.Table 10.6: Liveness calculation following reverse control-flow edges.1st2nd3rdusedefoutinoutinout654321cabbcaacbacacbcbcaccacbcbcaccacacbcbcaccacbcbcaccacacbcbcacincacbcbcaccWhen solving dataflow equations by iteration, the order of computation should follow the"flow." Since liveness flows backward along control-flow arrows, and from "out" to "in", soshould the computation.178Ordering the nodes can be done easily by depth-first search, as shown in Section 17.4.Basic blocks Flow-graph nodes that have only one predecessor and one successor are notvery interesting.

Such nodes can be merged with their predecessors and successors; whatresults is a graph with many fewer nodes, where each node represents a basic block. Thealgorithms that operate on flow graphs, such as liveness analysis, go much faster on thesmaller graphs. Chapter 17 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 bejust as practical to compute dataflow for one variable at a time as information about thatvariable is needed.

For liveness, this would mean repeating the dataflow traversal once foreach temporary. Starting from each use site of a temporary t, and tracing backward (followingpredecessor edges of the flow graph) using depth-first search, we note the liveness of t at eachflow-graph node. The search stops at any definition of the temporary. Although this mightseem expensive, many temporaries have very short live ranges, so the searches terminatequickly and do not traverse the entire flow graph for most variables.REPRESENTATION OF SETSThere are at least two good ways to represent sets for dataflow equations: as arrays of bits oras sorted lists of variables.If there are N variables in the program, the bit-array representation uses N bits for each set.Calculating the union of two sets is done by or-ing the corresponding bits at each position.Since computers can represent K bits per word (with K = 32 typical), one set-union operationtakes 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 (discardingduplicates). 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 sorted-listrepresentation is asymptotically faster; when the sets are dense, the bit-array representation isbetter.TIME COMPLEXITYHow 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 live-in set (or live-out set) has at most N elements; each set-union operation to computelive-in (or live-out) takes O(N) time.The for loop computes a constant number of set operations per flow-graph node; there areO(N) nodes; thus, the for loop takes O(N2) time.Each iteration of the repeat loop can only make each in or out set larger, never smaller. Thisis because the in and out sets are monotonic with respect to each other.