14/29/09 Prof. Hilfinger CS164 Lecture 38 1Register AllocationLecture 28(from notes by G. Necula and R. Bodik)4/29/09 Prof. Hilfinger CS164 Lecture 38 2Lecture Outline• Memory Hierarchy Management• Register Allocation– Register interference graph– Graph coloring heuristics– Spilling• Cache Management4/29/09 Prof. Hilfinger CS164 Lecture 38 3The Memory HierarchyRegisters 1 cycle 256-2000 bytesCache 1-100 cycles 256k-16MMain memory 150-1000 cycles 32M-16GDisk 0.5-10M cycles 10G-1T4/29/09 Prof. Hilfinger CS164 Lecture 38 4Managing the Memory Hierarchy• Programs are written as if there are only twokinds of memory: main memory and disk• Programmer is responsible for moving datafrom disk to memory (e.g., file I/O)• Hardware is responsible for moving databetween memory and caches• Compiler is responsible for moving databetween memory and registers4/29/09 Prof. Hilfinger CS164 Lecture 38 5Current Trends• Cache and register sizes are growing slowly• Processor speed improves faster than memoryspeed and disk speed– The cost of a cache miss is growing– The widening gap is bridged with more caches• It is very important to:– Manage registers properly– Manage caches properly• Compilers are good at managing registers4/29/09 Prof. Hilfinger CS164 Lecture 38 6The Register Allocation Problem• Intermediate code uses as many temporaries asnecessary– This complicates final translation to assembly– But simplifies code generation and optimization– Typical intermediate code uses too many temporaries• The register allocation problem:– Rewrite the intermediate code to use fewertemporaries than there are machine registers– Method: assign more temporaries to a register• But without changing the program behavior24/29/09 Prof. Hilfinger CS164 Lecture 38 7History• Register allocation is as old as intermediatecode• Register allocation was used in the originalFORTRAN compiler in the ‘50s– Very crude algorithms• A breakthrough was not achieved until 1980when Chaitin invented a register allocationscheme based on graph coloring– Relatively simple, global and works well in practice4/29/09 Prof. Hilfinger CS164 Lecture 38 8An Example• Consider the programa := c + de := a + bf := e - 1– with the assumption that a and e die after use• Temporary a can be “reused” after “a + b”• Same with temporary e after “e - 1”• Can allocate a, e, and f all to one register (r1):r1 := c + dr1 := r1 + br1 := r1 - 14/29/09 Prof. Hilfinger CS164 Lecture 38 9Basic Register Allocation Idea• The value in a dead temporary is not neededfor the rest of the computation– A dead temporary can be reused• Basic rule:– Temporaries t1 and t2 can share the sameregister if at any point in the program atmost one of t1 or t2 is live !4/29/09 Prof. Hilfinger CS164 Lecture 38 10Algorithm: Part I• Compute live variables for each point:a := b + cd := -ae := d + ff := 2 * eb := d + ee := e - 1b := f + c{b}{c,e}{b}{c,f}{c,f}{b,c,e,f}{c,d,e,f}{b,c,f}{c,d,f}{a,c,f}4/29/09 Prof. Hilfinger CS164 Lecture 38 11The Register Interference Graph• Two temporaries that are live simultaneouslycannot be allocated in the same register• We construct an undirected graph– A node for each temporary– An edge between t1 and t2 if they are livesimultaneously at some point in the program• This is the register interference graph (RIG)– Two temporaries can be allocated to the sameregister if there is no edge connecting them4/29/09 Prof. Hilfinger CS164 Lecture 38 12Register Interference Graph. Example.• For our example:afedcb• E.g., b and c cannot be in the same register• E.g., b and d can be in the same register34/29/09 Prof. Hilfinger CS164 Lecture 38 13Register Interference Graph. Properties.• It extracts exactly the information needed tocharacterize legal register assignments• It gives a global (i.e., over the entire flowgraph) picture of the register requirements• After RIG construction the register allocationalgorithm is architecture independent4/29/09 Prof. Hilfinger CS164 Lecture 38 14Graph Coloring. Definitions.• A coloring of a graph is an assignment ofcolors to nodes, such that nodes connected byan edge have different colors• A graph is k-colorable if it has a coloring withk colors4/29/09 Prof. Hilfinger CS164 Lecture 38 15Register Allocation Through Graph Coloring• In our problem, colors = registers– We need to assign colors (registers) to graph nodes(temporaries)• Let k = number of machine registers• If the RIG is k-colorable then there is aregister assignment that uses no more than kregisters4/29/09 Prof. Hilfinger CS164 Lecture 38 16Graph Coloring. Example.• Consider the sample RIGafedcb• There is no coloring with fewer than 4 colors• There are 4-colorings of this graphr4r1r2r3r2r34/29/09 Prof. Hilfinger CS164 Lecture 38 17Graph Coloring. Example.• Under this coloring the code becomes:r2 := r3 + r4r3 := -r2r2 := r3 + r1r1 := 2 * r2r3 := r3 + r2r2 := r2 - 1r3 := r1 + r44/29/09 Prof. Hilfinger CS164 Lecture 38 18Computing Graph Colorings• The remaining problem is to compute acoloring for the interference graph• But:1. This problem is very hard (NP-hard). No efficientalgorithms are known.2. A coloring might not exist for a given number orregisters• The solution to (1) is to use heuristics• We’ll consider later the other problem44/29/09 Prof. Hilfinger CS164 Lecture 38 19Graph Coloring Heuristic• Observation:– Pick a node t with fewer than k neighbors in RIG– Eliminate t and its edges from RIG– If the resulting graph has a k-coloring then so doesthe original graph• Why:– Let c1,…,cn be the colors assigned to the neighborsof t in the reduced graph– Since n < k we can pick some color for t that isdifferent from those of its neighbors4/29/09 Prof. Hilfinger CS164 Lecture 38 20Graph Coloring Heuristic• The following works well in practice:– Pick a node t with fewer than k neighbors– Push t on a stack and remove it from the RIG– Repeat until the graph has one node• Then start assigning colors to nodes in thestack (starting with the last node added)– At each step pick a color different from thoseassigned to already colored neighbors4/29/09 Prof. Hilfinger CS164 Lecture 38 21Graph Coloring Example (1)• Remove a and then dafedcb• Start with the RIG and with k = 4:Stack: {} 4/29/09 Prof. Hilfinger CS164 Lecture 38 22Graph Coloring Example (2)• Now all
View Full Document
Unlocking...