Question? Leave a message!




Register Allocation

Register Allocation
Spring Spring 2010 2010 Register Allocation Courtesy of Saman Amarasinghe and Armando SolarLezama. Used with permission. 5 Outline • What is register allocation • Webs • Interference Graphs • Graph coloring • Spilling • S S plitti litting • More optimizations Saman Amarasinghe Armando SolarLezama 2 6.035 ©MIT Storing g values between def and use • Program computes with values – value value definitions definitions (where (where c computed) omputed) – value uses (where read to compute new values) • Values must be stored between def and use – First Option •st tore each h vall ue i in memory at t d deffii niitition • retrieve from memory at each use – Second Op ption • store each value in register at definition • retrieve value from register at each use Saman Amarasinghe Armando SolarLezama 3 6.035 ©MIT Reg gister Allocation • Deciding which values to store in limited numb ber off regii stters • Register Register allocation allocation has has a direct a direct impact impact on on performance – Affects almost every statement of the program – Eliminates expensive memory instructions – of instructions goes down due to direct manipulation manipulation o of f registers registers • Limited memtomem ALU ops, may need two instructions – Probably is the optimization with the most impact Saman Amarasinghe Armando SolarLezama 4 6.035 ©MIT What can be p put in a reg gister • Values stored in compilergenerated temps • Languagelevel values – Values stored in local scalar variables – Big constants – Values Values stored stored in in array array e elements lements and and object object fields fields • Issue: alias analysis • Register set depends on the datatype – floatingpoint values in floating point registers – integer and pointer values in integer registers Saman Amarasinghe Armando SolarLezama 5 6.035 ©MIT Issues • Fewer instructions when using registers – Additional instructions when using memory accesses • Registers are faster than memory – wider wider gap gap in in faster faster, newer newer processors processors – Factor of about 4 bandwidth, factor of about 3 latency – Could be bigger if program characteristics were different • But only a small number of registers available – Usually Usually 16 16 integer integer and and 16 16 floating floatingpoint point registers registers – Some of those registers have fixed users (ex: RSP, RBP) Saman Amarasinghe Armando SolarLezama 6 6.035 ©MIT 15 Outline • What is register allocation • Key ideas in register allocation • Webs • Interference Graphs • Graph coloring • S Splitti litting • More optimizations Saman Amarasinghe Armando SolarLezama 7 6.035 ©MIT Summary y of Reg gister Allocation • You want to put each temporary in a register – But, you don’t have enough registers. • Key Ideas: 1 1. When When a a temporary temporary goes goes dead dead , its its register register can can be be reused reused 2. Two live temporaries can’t use the same register at the same time Saman Amarasinghe Armando SolarLezama 8 6.035 ©MIT Summary y of Reg g ister Allocation • When a temporary goes dead, its register can be reused • • Example: Example: a := c + d e := a + b f f: := =e e 1 1 (assume that a and e die after use) • temporaries a, e and f can go in the same register r1 1 := c + + d d r1 := r1 + b r1:= r1 – 1 Saman Amarasinghe Armando SolarLezama 9 6.035 ©MIT Summary y of Reg g ister Allocation • Two live temporaries can’t use the same register at the same same time time • Example 2: a: a := =c c + +d d e := a + b f := e a • ttemporariies e and d a can nott go iin t thh e same regiistter r1 := c + d r2 := r1 + b r r1 1 := := r r2 2 – r r1 1 Saman Amarasinghe Armando SolarLezama 10 6.035 ©MIT When thing g s don’t work out • Sometimes more live variables than registers a := c + d e := c + b Won’t work for f := e – c 2 reg g isters g := e + +f f h := a + g (assume only g and h live at the end) • You can split a live range by storing to memory a := c + d store a e := c + b f := e – c g := e + f load a h := a + g Saman Amarasinghe Armando SolarLezama 11 6.035 ©MIT WebBased Reg gister Allocation • Determine live ranges for each value (web) • Determine overlapping ranges (interference) • Compute the benefit of keeping each web in a register register (spill (spill cost) cost) • Decide which webs get a register (allocation) • • Split Split webs webs if if needed needed (spilling (spilling and and splitting) splitting) • Assign hard registers to webs (assignment) • • Generate Generate code code including including spills spills (code gen) (code gen) Saman Amarasinghe Armando SolarLezama 12 6.035 ©MIT 25 Outline • What is register allocation • Key ideas in register allocation • Webs • Interference Graphs • Graph coloring • S Splitti litting • More optimizations Saman Amarasinghe Armando SolarLezama 13 6.035 ©MIT Webs • Starting Point: defuse chains (DU chains) – Connects Connects definition definition to to a all ll reachable reachable u uses ses • Conditions for Conditions for putting putting defs defs and and uses uses into into same same web – Def and all reachable uses must be in same web – All defs that reach same use must be in same web • Use a unionfind algorithm Saman Amarasinghe Armando SolarLezama 14 6.035 ©MIT Examp ple def y y def def x x def def x x def y use y use x use x use y def x use use x x Saman Amarasinghe Armando SolarLezama 15 6.035 ©MIT Examp ple def y y def def x x def def x x def y use y use x use x use y def x use use x x Saman Amarasinghe Armando SolarLezama 16 6.035 ©MIT Examp ple def y y def def x x def def x x def y use y use x use x use y def x use use x x Saman Amarasinghe Armando SolarLezama 17 6.035 ©MIT Examp ple def y y def def x x def def x x def y use y use x use x use y def x use use x x Saman Amarasinghe Armando SolarLezama 18 6.035 ©MIT Examp ple def y y def def x x def def x x def y use y use x use x use y def x use use x x Saman Amarasinghe Armando SolarLezama 19 6.035 ©MIT Examp ple def y y def def x x def def x x def y use y use x use x use y def x use use x x Saman Amarasinghe Armando SolarLezama 20 6.035 ©MIT Examp ple def y y def def x x def def x x def y use y use x use x use y def x use use x x Saman Amarasinghe Armando SolarLezama 21 6.035 ©MIT Examp ple s1 def y y def def x x def def x x s2 2 def y use y s3 use x use x use y def x s4 use use x x Saman Amarasinghe Armando SolarLezama 22 6.035 ©MIT Webs • Web is unit of register allocation • If web allocated to a given register R – All definitions computed into R – All uses read from R • If web allocated to a memory location M – All All d defi finiti itions comput ted d i int to M M – All uses read from M Saman Amarasinghe Armando SolarLezama 23 6.035 ©MIT 31 Outline • What is register allocation • Webs • Interference Graphs • Graph coloring • Splitting • M More optiti miizattii ons Saman Amarasinghe Armando SolarLezama 24 6.035 ©MIT Convex Sets and Live Rang ges • Concept of convex set • A set S is convex if – A, , B in S S a and d C C is s o on a a pat path fro om A tto o B imp plies es – C is in S • Concept of live range of a web – Minimal convex set of instructions that includes all defs and uses in web – Intuitively, region in which web’s value is live Saman Amarasinghe Armando SolarLezama 25 6.035 ©MIT Interference • Two webs interfere if their live ranges overlap (have a nonemtpy intersection) • If two webs interfere, values must be stored in different registers or memory locations • If two webs do not interfere, can store values in same same register register or or memory memory location location Saman Amarasinghe Armando SolarLezama 26 6.035 ©MIT Examp ple s1 def y y def def x x def def x x s2 2 def y use y s3 use x use x use y def x s4 use use x x Saman Amarasinghe Armando SolarLezama 27 6.035 ©MIT Examp ple s1 def y y def def x x def def x x s2 2 def y use y s3 use x use x use y def x s4 use use x x Saman Amarasinghe Armando SolarLezama 28 6.035 ©MIT Examp ple Webs s1 and s2 interfere s1 def y y Webs s2 and s3 interfere def def x x def def x x s2 2 def y use y s3 use x use x use y def x s4 use use x x Saman Amarasinghe Armando SolarLezama 29 6.035 ©MIT Interference Grap ph • Representation of webs and their interference – Nodes are the webs – An edge exists between two nodes if they interfere s1 s2 s3 s4 Saman Amarasinghe Armando SolarLezama 30 6.035 ©MIT Examp ple s1 def y y def def x x def def x x s2 2 def y use y s3 s1 s2 use x use x use y def x s4 use use x x s3 3 s4 4 Saman Amarasinghe Armando SolarLezama 31 6.035 ©MIT Examp ple Webs s1 and s2 interfere s1 def y y Webs s2 and s3 interfere def def x x def def x x s2 2 def y use y s3 s1 s2 use x use x use y def x s4 use use x x s3 3 s4 4 Saman Amarasinghe Armando SolarLezama 32 6.035 ©MIT 37 Outline • Overview of procedure optimizations • What is register allocation • A simple register allocator • Webs • Interference Graphs • G Graph h colloriing • Splitting • More optimi More optimiza ations tions Saman Amarasinghe Armando SolarLezama 33 6.035 ©MIT Register Allocation Using Graph Graph Coloring Coloring • Each web is allocated a register – each node gets a register (color) • If two webs interfere they cannot use the same register register – if two nodes have an edge between them, they cannot have the same color s1 s2 s3 s4 Saman Amarasinghe Armando SolarLezama 34 6.035 ©MIT Grap ph Coloring g • Assign a color to each node in graph • Two nodes connected to same edge must have different colors • Cl Classi ic prob bll em i in graph h th heory • NP NP compllette – But good heuristics exist for register allocation Saman Amarasinghe Armando SolarLezama 35 6.035 ©MIT Grap p h Coloring g Examp p le Saman Amarasinghe Armando SolarLezama 36 6.035 ©MIT Grap p h Coloring g Examp p le • 1 Color Saman Amarasinghe Armando SolarLezama 37 6.035 ©MIT Grap p h Coloring g Examp p le Saman Amarasinghe Armando SolarLezama 38 6.035 ©MIT Grap p h Coloring g Examp p le • 2 Colors Saman Amarasinghe Armando SolarLezama 39 6.035 ©MIT Grap p h Coloring g Examp p le Saman Amarasinghe Armando SolarLezama 40 6.035 ©MIT Grap p h Coloring g Examp p le • Still 2 Colors Saman Amarasinghe Armando SolarLezama 41 6.035 ©MIT Grap p h Coloring g Examp p le Saman Amarasinghe Armando SolarLezama 42 6.035 ©MIT Grap p h Coloring g Examp p le • 3 Colors Saman Amarasinghe Armando SolarLezama 43 6.035 ©MIT Heuristics for Reg gister Coloring g • Coloring a graph with N colors • If degree N (degree of a node = of edges) – Node can always be colored – After coloring the rest of the nodes, you’ll have at least one color left to color the current node • If If d degree = N N – still may be colorable with N colors Saman Amarasinghe Armando SolarLezama 44 6.035 ©MIT Heuristics for Reg gister Coloring g • Remove nodes that have degree N – push the removed nodes onto a stack • When all the nodes have degree = N – Find a node to spill (no color for that node) – Remove that node • When empty, start to color – pop a node from stack back – A Assiign it it a collor tth h at t i is d diff iff erent t ff rom it it s connectted d nodes (since degree N, a color should exist) Saman Amarasinghe Armando SolarLezama 45 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s3 s4 Saman Amarasinghe Armando SolarLezama 46 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s3 s4 Saman Amarasinghe Armando SolarLezama 47 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 48 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s2 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 49 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s1 s2 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 50 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s3 s0 s1 s2 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 51 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s3 s0 s1 s2 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 52 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s3 s0 s1 s2 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 53 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s1 s2 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 54 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s1 s2 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 55 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s2 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 56 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s2 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 57 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 58 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 59 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s3 s4 Saman Amarasinghe Armando SolarLezama 60 6.035 ©MIT Coloring g Examp ple N = 3 s1 s2 s0 s3 s4 Saman Amarasinghe Armando SolarLezama 61 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s3 s4 Saman Amarasinghe Armando SolarLezama 62 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 63 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 64 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s3 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 65 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s2 s0 s3 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 66 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s2 s0 s3 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 67 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s2 s0 s3 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 68 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s3 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 69 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s3 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 70 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 71 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s4 4 s3 s4 Saman Amarasinghe Armando SolarLezama 72 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s3 s4 Saman Amarasinghe Armando SolarLezama 73 6.035 ©MIT Another Coloring g Examp p le N = 3 s1 s2 s0 s3 s4 Saman Amarasinghe Armando SolarLezama 74 6.035 ©MIT What Now • Option 1 – Pick a web and allocate value in memory – All defs go to memory, all uses come from memory • Option 2 – Split the web into multiple webs • In either case, will retry the coloring Saman Amarasinghe Armando SolarLezama 75 6.035 ©MIT Which web to p pick • One with interference degree = N • One with minimal spill cost (cost of placing value in memory rather than in register) • What is spill cost – Cost of extra load and store instructions Saman Amarasinghe Armando SolarLezama 76 6.035 ©MIT Ideal and Useful Sp pill Costs • Ideal spill cost dynamic cost of extra load and store instructions. Can’t expect to compute this. – Don’t know which way branches resolve – DD’ on’t k know h how many ti imes lloops execute – Actual cost may be different for different executions • Solution: Solution: Use Use a a static static approximation approximation – profiling can give instruction execution frequencies – – or use or use heuristics heuristics based based on on structure structure o of f c control ontrol flow flow graph Saman Amarasinghe Armando SolarLezama 77 6.035 ©MIT One Way y to Comp pute Sp pill Cost • Goal: give priority to values used in loops • So assume loops execute 10 or 100 times • Spill cost = – sum over all def sites of cost of a store instruction times 10 to the loop nesting depth power, plus – sum over all ll use sit ites of f costt off a lload d i insttructtiion ttiimes 10 to the loop nesting depth power • • Choose Choose the the web w web with ith the the lowest lowest s spill pill cost cost Saman Amarasinghe Armando SolarLezama 78 6.035 ©MIT Sp p ill Cost Examp ple Spill Spill Cost Cost For For x x def x storeCost+loadCost def y Spill Cost For y use y y 9 9 stor storeCost+ eCost+9 9 loadCost loadCost def y Wi Wit th h 1 1 R Regi ist ter, Whi Which h use x Variable Gets Spilled use use y y Saman Amarasinghe Armando SolarLezama 79 6.035 ©MIT 47 Outline • Overview of procedure optimizations • What is register allocation • A simple register allocator • Webs • Interference Graphs • G Graph h colloriing • Splitting • More optimi More optimiza ations tions Saman Amarasinghe Armando SolarLezama 80 6.035 ©MIT Sp plitting g Rather Than Sp pilling g • Split the web – Split a web into multiple webs so that there will be less interference in the interference graph making it N colorable – Spill the value to memory and load it back at the points where the web is split Saman Amarasinghe Armando SolarLezama 81 6.035 ©MIT Sp p litting g Examp p le x y z def z use z def def x x def y use x use x use y use z Saman Amarasinghe Armando SolarLezama 82 6.035 ©MIT Sp p litting g Examp p le x y z def z use z def def x x def y use x x y use x use y z z use z Saman Amarasinghe Armando SolarLezama 83 6.035 ©MIT Sp p litting g Examp p le x y z def z use z def def x x def y use x x y use x use y z z use z 2 colorable Saman Amarasinghe Armando SolarLezama 84 6.035 ©MIT Sp p litting g Examp p le x y z def z use z def def x x def y use x x y use x use y z z use z 2 colorable NO NO Saman Amarasinghe Armando SolarLezama 85 6.035 ©MIT Sp p litting g Examp p le x y z def z use z def def x x def y use x use x use y use z Saman Amarasinghe Armando SolarLezama 86 6.035 ©MIT Sp p litting g Examp p le x y z def z use z def def x x def y use x use x use y use z Saman Amarasinghe Armando SolarLezama 87 6.035 ©MIT Sp p litting g Examp p le x y z def z use z z1 def def x x def y use x x y use x use y z2 z2 use z Saman Amarasinghe Armando SolarLezama 88 6.035 ©MIT Sp p litting g Examp p le x y z def z use z z1 def def x x def y use x x y use x use y z z2 2 use z 2 colorable Saman Amarasinghe Armando SolarLezama 89 6.035 ©MIT Sp p litting g Examp p le x y z def z use z z1 def def x x def y use x x y use x use y z2 z2 use z 2 colorable YES YES Saman Amarasinghe Armando SolarLezama 90 6.035 ©MIT Sp p litting g Examp p le x y z def z use z r1 z1 r2 def def x x r1 1 def y use x x y use x use y z z2 2 r1 r1 use z 2 colorable YES YES Saman Amarasinghe Armando SolarLezama 91 6.035 ©MIT Sp plitting g Examp p le def z x y z use z str str z z r1 z1 r2 def def x x r1 1 def y use x x y use x use y z2 z2 r1 r1 ld z 2 colorable use z YES YES Saman Amarasinghe Armando SolarLezama 92 6.035 ©MIT Sp plitting g Heuristic • Identify a program point where the graph is not R colorable (point where of webs N) – Pick a web that is not used for the largest enclosing block block a around round that point that point of the of the p program rogram – Split that web at the corresponding edge – Redo Redo the the iinterference nterference g graph raph – Try to recolor the graph Saman Amarasinghe Armando SolarLezama 93 6.035 ©MIT Cost and benefit of sp p litting g • Cost of splitting a node – Proportion to number of times splitted edge has to be crossed dynamically – Estimate Estimate by by its its lloop oop nesting nesting • Benefit – Increase colorability of the nodes the splitted web interferes with – Can approximate by its degree in the interference graph • • Greedy Greedy heuristic heuristic – pick the liverange with the highest benefittocost ration to spill Saman Amarasinghe Armando SolarLezama 94 6.035 ©MIT 52 Outline • Overview of procedure optimizations • What is register allocation • A simple register allocator • Webs • Interference Graphs • G Graph h colloriing • Splitting • More optimi More optimiza ations tions Saman Amarasinghe Armando SolarLezama 95 6.035 ©MIT Further Op ptimizations • Register coalescing • Register targeting (precoloring) • Presplitting g of webs • Interprocedural register allocation Saman Amarasinghe Armando SolarLezama 96 6.035 ©MIT Reg gister Coalescing g • Find register copy instructions sj = si • If sj and si do not interfere, combine their webs •Pros – similar similar to to copy copy propagation propagation – reduce the number of instructions • Cons – may increase the degree of the combined node – a colorable graph may become noncolorable Saman Amarasinghe Armando SolarLezama 97 6.035 ©MIT Regg ister Targ geting g ( (pp recoloring) g) • Some variables need to be in special registers at a given time – fist 6 arguments to a function – return vallue • Pre Pre color color those those w webs ebs and bind and bind them them to to the right the right register • Will eliminate unnecessary copy instructions Saman Amarasinghe Armando SolarLezama 98 6.035 ©MIT Presp plitting g of the webs • Some live ranges have very large “dead” regions. – Large region where the variable is unused • Break Breakup up the the live live ranges ranges – need to pay a small cost in spilling – but but the the g graph raph will will be be very very easy easy to to c color olor • Can find strateg gic locations to breakup p – at a call site (need to spill anyway) – around a large loop nest (reserve registers for values used in the loop) ) Saman Amarasinghe Armando SolarLezama 99 6.035 ©MIT Interprocedural register allocation allocation • saving registers across procedure boundaries is expensive – especially for programs with many small functions • Calling convention is too general and inefficient • Customize calling convention per function by doing doing interprocedural interprocedural register allocation register allocation Saman Amarasinghe Armando SolarLezama 100 6.035 ©MIT Summary y • Register Allocation – Store values in registers between def and use – Can improve performance substantially • Key concepts –Wb Webs – Interference graphs – Colorability Colorability – Splitting Saman Amarasinghe Armando SolarLezama 101 6.035 ©MIT MIT OpenCourseWare http://ocw.mit.edu 6.035 Computer Language Engineering Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.MasonHanks
User Type:
Teacher
Country:
Germany
Uploaded Date:
23-07-2017