Question? Leave a message!




Register Allocation

Register Allocation
Dr.MasonHanks Profile Pic
Dr.MasonHanks,Germany,Teacher
Published Date:23-07-2017
Website URL
Comment
Spring Spring 2010 2010 Register Allocation Courtesy of Saman Amarasinghe and Armando Solar-Lezama. Used with permission. 5 Outline • What is register allocation • Webs • Interference Graphs • Graph coloring • Spilling • S S plitti litting • More optimizations Saman Amarasinghe & Armando Solar-Lezama 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 Solar-Lezama 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 mem-to-mem ALU ops, may need two instructions – Probably is the optimization with the most impact Saman Amarasinghe & Armando Solar-Lezama 4 6.035 ©MIT What can be p put in a reg gister? • Values stored in compiler-generated temps • Language-level 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 data-type – floating-point values in floating point registers – integer and pointer values in integer registers Saman Amarasinghe & Armando Solar-Lezama 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 floating-point point registers registers – Some of those registers have fixed users (ex: RSP, RBP) Saman Amarasinghe & Armando Solar-Lezama 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 Solar-Lezama 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 Solar-Lezama 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 Solar-Lezama 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 Solar-Lezama 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 Solar-Lezama 11 6.035 ©MIT Web-Based 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 Solar-Lezama 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 Solar-Lezama 13 6.035 ©MIT Webs • Starting Point: def-use 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 union-find algorithm Saman Amarasinghe & Armando Solar-Lezama 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 Solar-Lezama 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 Solar-Lezama 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 Solar-Lezama 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 Solar-Lezama 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 Solar-Lezama 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 Solar-Lezama 20 6.035 ©MIT