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

A directed edge from n to m is created by g.addEdge(n,m); after that, mwill be found in the list n.succ() and n will be in m.pred(). When working with undirectedgraphs, the function adj is useful: m.adj() = m.succ() ∪ m.pred().To delete an edge, use rmEdge. To test whether m and n are the same node, use m==n.When using a graph in an algorithm, we want each node to represent something (aninstruction in a program, for example). To make mappings from nodes to the things they aresupposed to represent, we use a Hashtable.

The following idiom associates information xwith node n in a mapping mytable.java.util.Dictionary mytable = new java.util.Hashtable();... mytable.put(n,x);CONTROL-FLOW GRAPHSThe FlowGraph package manages control-flow graphs. Each instruction (or basic block) isrepresented by a node in the flow graph.

If instruction m can be followed by instruction n(either by a jump or by falling through), then there will be an edge (m, n) in the graph.public abstract class FlowGraph extends Graph.Graph {public abstract TempList def(Node node);public abstract TempList use(Node node);public abstract boolean isMove(Node node);public void show(java.io.PrintStream out);}Each Node of the flow graph represents an instruction (or, perhaps, a basic block).

The def()method tells what temporaries are defined at this node (destination registers of theinstruction). use() tells what temporaries are used at this node (source registers of the184instruction). isMove tells whether this instruction is a MOVE instruction, one that could bedeleted if the def and use were identical.The AssemFlowGraph class provides an implementation of FlowGraph for Assem instructions.package FlowGraph;public class AssemFlowGraph extends FlowGraph {public Instr instr(Node n);public AssemFlowGraph(Assem.InstrList instrs);}The constructor AssemFlowGraph takes a list of instructions and returns a flow graph.

Inmaking the flow graph, the jump fields of the instrs are used in creating control-flow edges,and the use and def information (obtained from the src and dst fields of the instrs) isattached to the nodes by means of the use and def methods of the flowgraph.Information associated with the nodes For a flow graph, we want to associate some use anddef information with each node in the graph. Then the liveness-analysis algorithm will alsowant to remember live-in and live-out information at each node.

We could make room in theNode class to store all of this information. This would work well and would be quite efficient.However, it may not be very modular. Eventually we may want to do other analyses on flowgraphs, which remember other kinds of information about each node. We may not want tomodify the data structure (which is a widely used interface) for each new analysis.Instead of storing the information in the nodes, a more modular approach is to say that a graphis a graph, and that a flow graph is a graph along with separately packaged auxiliaryinformation (tables, or functions mapping nodes to whatever).

Similarly, a dataflow algorithmon a graph does not need to modify dataflow information in the nodes, but modifies its ownprivately held mappings.There may be a trade-off here between efficiency and modularity, since it may be faster tokeep the information in the nodes, accessible by a simple pointer-traversal instead of a hashtable or search-tree lookup.LIVENESS ANALYSISThe RegAlloc package has an abstract class InterferenceGraph to indicate which pairs oftemporaries cannot share a register:package RegAlloc;abstract public class InterferenceGraph extends Graph.Graph{abstract public Graph.Node tnode(Temp.Temp temp);abstract public Temp.Temp gtemp(Node node);abstract public MoveList moves();public int spillCost(Node node);}The method tnode relates a Temp to a Node, and gtemp is the inverse map. The method movestells what MOVE instructions are associated with this graph (this is a hint about what pairs oftemporaries to try to allocate to the same register).

The spillCost(n) is an estimate of howmany extra instructions would be executed if n were kept in memory instead of in registers;for a naive spiller, it suffices to return 1 for every n.The class Liveness produces an interference graph from a flow graph:185package RegAlloc;public class Liveness extends InterferenceGraph {public Liveness(FlowGraph flow);}In the implementation of the Liveness module, it is useful to maintain a data structure thatremembers what is live at the exit of each flow-graph node:private java.util.Dictionary liveMap =new java.util.Hashtable();where the keys are nodes and objects are TempLists.

Given a flow-graph node n, the set oflive temporaries at that node can be looked up in a global liveMap.Having calculated a complete liveMap, we can now construct an interference graph. At eachflow node n where there is a newly defined temporary d ∈ def(n), and where temporaries {t1,t2;…} are in the liveMap, we just add interference edges (d, t1), (d, t2),…. For MOVEs, theseedges will be safe but suboptimal; pages 213-214 describe a better treatment.What if a newly defined temporary is not live just after its definition? This would be the caseif a variable is defined but never used. It would seem that there's no need to put it in a registerat all; thus it would not interfere with any other temporaries.

But if the defining instruction isgoing to execute (perhaps it is necessary for some other side effect of the instruction), then itwill write to some register, and that register had better not contain any other live variable.Thus, zero-length live ranges do interfere with any live ranges that overlap them.PROGRAM CONSTRUCTING FLOW GRAPHSImplement the AssemFlowGraph class that turns a list of Assem instructions into a flow graph.Use the abstract classes Graph.Graph and Flow- Graph.FlowGraph provided in$MINIJAVA/chap10.PROGRAM LIVENESSImplement the Liveness module. Use either the set-equation algorithm with the array-ofboolean or sorted-list-of-temporaries representation of sets, or the one-variable-at-a-timemethod.EXERCISES••10.1 Perform flow analysis on the program of Exercise 8.6:a.

Draw the control-flow graph.b. Calculate live-in and live-out at each statement.c. Construct the register interference graph.**10.2 Prove that Equations 10.3 have a least fixed point and that Algorithm 10.4always computes it.Hint: We know the algorithm refuses to terminate until it has a fixed point. Thequestions are whether (a) it must eventually terminate, and (b) the fixed point itcomputes is smaller than all other fixed points.

For (a) show that the sets can only getbigger. For (b) show by induction that at any time the in and out sets are subsets of186those in any possible fixed point. This is clearly true initially, when in and out are bothempty; show that each step of the algorithm preserves the invariant.•*10.3 Analyze the asymptotic complexity of the one-variable-at-a-time method ofcomputing dataflow information.• *10.4 Analyze the worst-case asymptotic complexity of making an interference graph,for a program of size N (with at most N variables and at most N control-flow nodes).Assume the dataflow analysis is already done and that use, def, and live-outinformation for each node can be queried in constant time. What representation ofgraph adjacency matrices should be used for efficiency?• 10.5 The DEC Alpha architecture places the following restrictions on floating-pointinstructions, for programs that wish to recover from arithmetic exceptions:1.Within a basic block (actually, in any sequence of instructions not separated by a trapbarrier instruction), no two instructions should write to the same destination register.2.A source register of an instruction cannot be the same as the destination register of thatinstruction or any later instruction in the basic block.r1 + r5 → r4r1 + r5 → r4r1 + r5 → r3r1 + r5 → r4r3 × r2 → r4r4 × r2 → r1r4 × r2 → r4r4 × r2 → r6violates rule 1.

violates rule 2. violates rule 2. OK3.Show how to express these restrictions in the register interference graph.187Chapter 11: Register Allocationreg-is-ter: a device for storing small amounts of dataal-lo-cate: to apportion for a specific purposeWebster's DictionaryOVERVIEWThe Translate, Canon, and Codegen phases of the compiler assume that there are an infinitenumber of registers to hold temporary values and that MOVE instructions cost nothing. Thejob of the register allocator is to assign the many temporaries to a small number of machineregisters, and, where possible, to assign the source and destination of a MOVE to the sameregister so that the MOVE can be deleted.From an examination of the control and dataflow graph, we derive an interference graph.Each node in the interference graph represents a temporary value; each edge (t1, t2) indicates apair of temporaries that cannot be assigned to the same register.

The most common reason foran interference edge is that t1 and t2 are live at the same time. Interference edges can alsoexpress other constraints; for example, if a certain instruction a ← b ⊕ c cannot produceresults in register r12 on our machine, we can make a interfere with r12.Next we color the interference graph. We want to use as few colors as possible, but no pair ofnodes connected by an edge may be assigned the same color. Graph coloring problems derivefrom the old mapmakers' rule that adjacent countries on a map should be colored withdifferent colors.

Our "colors" correspond to registers: If our target machine has K registers,and we can K -color the graph (color the graph with K colors), then the coloring is a validregister assignment for the interference graph. If there is no K -coloring, we will have to keepsome of our variables and temporaries in memory instead of registers; this is called spilling.11.1 COLORING BY SIMPLIFICATIONRegister allocation is an NP-complete problem (except in special cases, such as expressiontrees); graph coloring is also NP-complete. Fortunately there is a linear-time approximationalgorithm that gives good results; its principal phases are Build, Simplify, Spill, and Select.Build: Construct the interference graph.

We use dataflow analysis to compute the set oftemporaries that are simultaneously live at each program point, and we add an edge to thegraph for each pair of temporaries in the set. We repeat this for all program points.Simplify: We color the graph using a simple heuristic. Suppose the graph G contains a nodem with fewer than K neighbors, where K is the number of registers on the machine. Let G′ bethe graph G − {m} obtained by removing m. If G′ can be colored, then so can G, for when mis added to the colored graph G′, the neighbors of m have at most K − 1 colors among them,so a free color can always be found for m.