Global Register Allocation via Graph ColoringRegister AllocationGlobal Register AllocationSlide 4Slide 5Slide 6Graph Coloring (A Background Digression)Building the Interference GraphSlide 9What is a Live Range?Computing LIVE SetsObservation on Coloring for Register AllocationChaitin’s AlgorithmChaitin Allocator (Bottom-up Coloring)Chaitin’s Algorithm in PracticeSlide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Picking a Spill CandidateGlobal Register Allocationvia Graph ColoringCopyright 2003, Keith D. Cooper, Ken Kennedy & Linda Torczon, all rights reserved.Register AllocationPart of the compiler’s back endCritical properties•Produce correct code that uses k (or fewer) registers•Minimize added loads and stores•Minimize space used to hold spilled values•Operate efficiently O(n), O(n log2n), maybe O(n2), but not O(2n)Errors IRRegisterAllocationInstructionSelectionMachinecodeInstructionSchedulingm registerIRk registerIRGlobal Register AllocationThe big pictureAt each point in the code1Determine which values will reside in registers2Select a register for each such valueThe goal is an allocation that “minimizes” running timeMost modern, global allocators use a graph-coloring paradigm•Build a “conflict graph” or “interference graph”•Find a k-coloring for the graph, or change the code to a nearby problem that it can k-colorRegisterAllocatorm register codek register codeOptimal global allocation is NP-Complete, under almost any assumptions.Global Register AllocationWhat’s harder across multiple blocks?•Could replace a load with a move•Good assignment would obviate the move•Must build a control-flow graph to understand inter-block flow•Can spend an inordinate amount of time adjusting the allocation...store r4 xload x r1...This is an assignment problem,not an allocation problem !Global Register AllocationA more complex scenario•Block with multiple predecessors in the control-flow graph•Must get the “right” values in the “right” registers in each predecessor•In a loop, a block can be its own predecessorsThis adds tremendous complications...store r4 xload x r1......store r4 xWhat if one block has x in a register, but the other does not?Global Register AllocationTaking a global approach•Abandon the distinction between local & global •Make systematic use of registers or memory•Adopt a general scheme to approximate a good allocationGraph coloring paradigm (Lavrov & (later) Chaitin )1Build an interference graph GI for the procedureComputing LIVE is harder than in the local caseGI is not an interval graph2(try to) construct a k-coloringMinimal coloring is NP-CompleteSpill placement becomes a critical issue3Map colors onto physical registersGraph Coloring (A Background Digression)The problemA graph G is said to be k-colorable iff the nodes can be labeled with integers 1… k so that no edge in G connects two nodes with the same label ExamplesEach color can be mapped to a distinct physical register2-colorable 3-colorableBuilding the Interference GraphWhat is an “interference” ? (or conflict)•Two values interfere if there exists an operation where both are simultaneously live•If x and y interfere, they cannot occupy the same registerTo compute interferences, we must know where values are “live”The interference graph, GI•Nodes in GI represent values, or live ranges•Edges in GI represent individual interferencesFor x, y GI, <x,y> iff x and y interfere•A k-coloring of GI can be mapped into an allocation to k registersBuilding the Interference GraphTo build the interference graph1Discover live ranges>Build SSA form>At each -function, take the union of the arguments2Compute LIVE sets for each block>Use an iterative data-flow solver>Solve equations for LIVE over domain of live range names3Iterate over each block>Track the current LIVE set>At each operation, add appropriate edges & update LIVEEdge from result to each value in LIVERemove result from LIVEEdge from each operand to each value in LIVEWhat is a Live Range?•A set LR of definitions {d1,d2,…,dn} such that for any two definitions di and dj in LR, there exists some use u that is reached by both di and dj .•How can we compute live ranges?For each basic block b in the program, compute REACHESOUT(b) — the set of definitions that reach the exit of basic block bd REACHESOUT(b) if there is no other definition on some path from d to the end of block bFor each basic block b, compute LIVEIN(b)—the set of variables that are live on entry to b v LIVEIN(b) if there is a path from the entry of b to a use of v that contains no definition of vAt each join point in the CFG, for each live variable v, merge the live ranges associated with definitions in REACHESOUT(p), for all predecessors of b, that assign a value to v.Computing LIVE SetsA value v is live at p if a path from p to someuse of v along which v is not re-definedData-flow problems are expressed as simultaneous equationsLIVEOUT(b) = ssucc(b) LIVEIN(s)LIVEIN(b) = (LIVEOUT(b) VARKILL(b)) UEVAR(b)whereUEVAR(b) is the set of upward-exposed variables in b (names used before redefinition in block b)VARKILLb) is the set of variable names redefined in bAs output,LIVEOUT(x) is the set of names live on exit from block x LIVEIN(x) is the set of names live on entry to block xsolve it with the iterative algorithmObservation on Coloring for Register Allocation•Suppose you have k registers—look for a k coloring•Any vertex n that has fewer than k neighbors in the interference graph (n < k) can always be colored !Pick any color not used by its neighbors — there must be one•Ideas behind Chaitin’s algorithm:Pick any vertex n such that n< k and put it on the stackRemove that vertex and all edges incident from the interference graphThis may make some new nodes have fewer than k neighborsAt the end, if some vertex n still has k or more neighbors, then spill the live range associated with nOtherwise successively pop vertices off the stack and color them in the lowest color not used by some neighborChaitin’s Algorithm1. While vertices with < k neighbors in GI >Pick any vertex n such that n< k and put it on the stack>Remove that vertex and all edges incident to it from GI1. This will lower the degree of n’s neighbors•If GI is
View Full Document