DOC PREVIEW
UD CISC 672 - Global Register Allocation via Graph Coloring

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 procedureComputing LIVE is harder than in the local caseGI is not an interval graph2(try to) construct a k-coloringMinimal coloring is NP-CompleteSpill 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 interferencesFor 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 LIVEEdge from result to each value in LIVERemove result from LIVEEdge 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 bd REACHESOUT(b) if there is no other definition on some path from d to the end of block bFor 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 vAt 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) = ssucc(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 stackRemove that vertex and all edges incident from the interference graphThis may make some new nodes have fewer than k neighborsAt the end, if some vertex n still has k or more neighbors, then spill the live range associated with nOtherwise 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

UD CISC 672 - Global Register Allocation via Graph Coloring

Documents in this Course
Syllabus

Syllabus

18 pages

Load more
Download Global Register Allocation via Graph Coloring
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Global Register Allocation via Graph Coloring and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Global Register Allocation via Graph Coloring 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?