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

That is, in the equationin[n] = use[n]U(out[n]−def[n]), a larger out[n] can only make in[n] larger. Similarly, in out[n]= Us in succ[n]in[s], a larger in[s] can only make out[n] larger.179Each iteration must add something to the sets; but the sets cannot keep growing infinitely; atmost every set can contain every variable. Thus, the sum of the sizes of all in and out sets is2N2, which is the most that the repeat loop can iterate.Thus, the worst-case run time of this algorithm is O(N4).

Ordering the nodes using depth-firstsearch (Algorithm 17.5, page 363) usually brings the number of repeat-loop iterations to twoor three, and the live sets are often sparse, so the algorithm runs between O(N) and O(N2) inpractice.Section 17.4 discusses more sophisticated ways of solving dataflow equations quickly.LEAST FIXED POINTSTable 10.7 illustrates two solutions (and a nonsolution!) to the Equations 10.3; assume there isanother program variable d not used in this fragment of the program.123456Table 10.7: X and Y are solutions to the liveness equations; Z is not a solution.XYZusedefinoutinoutinoutacaccdacdcacabacbcacdbcdacbbccbcbcbcdbcdbbbabcacbcdacdbacaacacacdacdacacccccIn solution Y, the variable d is carried uselessly around the loop.

But in fact, Y satisfiesEquations 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. Ifthe value of variable a will truly be needed in some execution of the program when executionreaches node n of the flow graph, then we can be assured that a is live-out at node n in anysolution of the equations.

But the converse is not true; we might calculate that d is live-out,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 thedataflow information. In the case of liveness analysis, if a variable is thought to be live, thenwe will make sure to have its value in a register.

A conservative approximation of liveness isone that may erroneously believe a variable is live, but will never erroneously believe it isdead. The consequence of a conservative approximation is that the compiled code might usemore registers than it really needs; but it will compute the right answer.Consider instead the live-in sets Z, which fail to satisfy the dataflow equations. Using this Zwe think that b and c are never live at the same time, and we would assign them to the sameregister.

The resulting program would use an optimal number of registers but compute thewrong answer.180A dataflow equation used for compiler optimization should be set up so that any solution to itprovides conservative information to the optimizer; imprecise information may lead tosuboptimal 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 inX [n] and inY [n] arethe live-in sets for some node n in solutions X and Y, then inX [n] ⊆ inY [n].Proof See Exercise 10.2.We say that X is the least solution to Equations 10.3. Clearly, since a bigger solution will leadto using more registers (producing suboptimal code), we want to use the least solution.Fortunately, Algorithm 10.4 always computes the least fixed point.STATIC VS.

DYNAMIC LIVENESSA variable is live "if its value will be used in the future." In Graph 10.8, we know that b × bmust 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 live-out of node 2.GRAPH 10.8: Standard static dataflow analysis will not take advantage of the fact that node 4can never be reached.But Equations 10.3 say that a is live-in to node 4, and therefore live-out of nodes 3 and 2.

Theequations are ignorant of which way the conditional branch will go. "Smarter" equationswould 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 arithmeticidentities, no compiler can ever fully understand how all the control flow in every programwill 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 (withoutinfinite-looping) returns true if P(X) halts and false if P(X) infinite-loops.181Proof Suppose that there were such a program H; then we could arrive at a contradiction asfollows. 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 thewhile loop executes forever; so F(F) does not halt.

But if F(F) loops forever, then H(F, F) isfalse; so the else clause is taken; so F(F) halts. The program F(F) halts if it doesn't halt, anddoesn't halt if it halts: a contradiction. Thus there can be no program H that tests whetheranother program halts (and always halts itself).Corollary No program H′(X, L) can tell, for any program X and label L within X, whether thelabel 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, justlet 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 givenlabel is reached or not, just that there is not a general algorithm that can always tell.

We couldimprove our liveness analysis with some special-case algorithms that, in some cases, calculatemore information about run-time control flow. But any such algorithm will come up againstmany 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 avariable's value is truly needed - whether the variable is truly live. Instead, we have to makedo with a conservative approximation. We assume that any conditional branch goes bothways.

Thus, we have a dynamic condition and its static approximation:••Dynamic liveness Avariable a is dynamically live at node n if some execution of theprogram goes from n to a use of a without going through any definition of a.Static liveness Avariable a is statically live at node n if there is some path of controlflow edges from n to some use of a that does not go through a definition of a.Clearly, if a is dynamically live, it is also statically live.

An optimizing compiler must allocateregisters, and do other optimizations, on the basis of static liveness, because (in general)dynamic liveness cannot be computed.INTERFERENCE GRAPHSLiveness information is used for several kinds of optimizations in a compiler. For someoptimizations, we need to know exactly which variables are live at each node in the flowgraph.One of the most important applications of liveness analysis is for register allocation: We havea set of temporaries a, b, c,… that must be allocated to registers r1,…, rk. A condition thatprevents 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 bare both live at the same program point, then they cannot be put in the same register.

But thereare some other causes of interference: for example, when a must be generated by aninstruction that cannot address register r1, then a and r1 interfere.182Interference information can be expressed as a matrix; Figure 10.9a has an x markinginterferences of the variables in Graph 10.1. The interference matrix can also be expressed asan undirected graph (Figure 10.9b), with a node for each variable, and edges connectingvariables that interfere.Figure 10.9: Representations of interference.Special treatment of MOVE instructions In static liveness analysis, we can give MOVEinstructions special consideration.

It is important not to create artifical interferences betweenthe 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 interferenceedge (s, t) since t is being defined at a point where s is live. But we do not need separateregisters for s and t, since they contain the same value.

The solution is just not to add aninterference edge (t, s) in this case. Of course, if there is a later (nonmove) definition of twhile s is still live, that will create the interference edge (t, s).Therefore, the way to add interference edges for each new definition is1. At any nonmove instruction that defines avariable a, where the live-out variables areb1,…, bj, add interference edges (a, b1),…,(a, bj).2.

At a move instruction a ← c, where variables b1,…, bj are live-out, add interferenceedges (a, b1),…,(a, bj) for any bi that is not the same as c.10.2 LIVENESS IN THE MiniJava COMPILERThe flow analysis for the MiniJava compiler is done in two stages: First, the control flow ofthe Assem program is analyzed, producing a control-flow graph; then, the liveness of variablesin the control-flow graph is analyzed, producing an interference graph.GRAPHSTo represent both kinds of graphs, let's make a Graph abstract data type (Program 10.10).PROGRAM 10.10: The Graph abstract data type.package Graph;183public class Graph {public Graph();public NodeList nodes();public Node newNode();public void addEdge(Node from, Node to);public void rmEdge(Node from, Node to);public void show(java.io.PrintStream out);}public class Node {public Node(Graph g);public NodeList succ();public NodeList pred();public NodeList adj();public int outDegree();public int inDegree();public int degree();public boolean goesTo(Node n);public boolean comesFrom(Node n);public boolean adj(Node n);public String toString();}The constructor Graph() creates an empty directed graph; g.newNode() makes a new nodewithin a graph g.