Register Allocation Algorithms

Ryan Brock

What is a Register Allocation Algorithm?

• Assigns high-level variables to register locations
• Handled by the compiler
• Limited number of registers
• Storage in main memory not efficient
• Typically cannot operate on main memory locations

a = b + c

d = d + b

e = b + a

Main

Reg

0

lw $8, $0

b

c

lw $9, b

lw $10, c

add $8, $9, $10

sw a, $8

lw $8, d

sw d, $8

lw $8, $0

lw $9, b

lw $10, a

a

add $8, $9, $10

sw e, $8

b+c

d

b+a

lw $9, b

add $8, $9

d+b

a = b + c

d = d + b

e = b + a

lw $8, $0

lw $9, b

lw $10, c

add $8, $9, $10

sw a, $8

lw $8, d

lw $9, b

add $8, $9

sw d, $8

lw $8, $0

lw $9, b

lw $10, a

add $8, $9, $10

sw e, $8

Naive Algorithm

• All variables are stored in main memory
• Only bring variables into registers when used
• Advantages:
• Easy to implement
• Fast
• Disadvantages:
• LOAD and STORE is costly
• Not efficient use of registers

a = b + c

d = d + b

e = b + a

Reg

a = b + c

d = d + b

e = b + a

b

lw $8, b

lw $9, c

lw $10, d

c

d

add $9, $8

a

add $10, $8

add $8, $9

e

Linear Scan Algorithm

• Compare live intervals of variables
• Live intervals include lifetime of variable
• More efficient that naive algorithm
• Fast compile time
• Prefers compile speed to register optimization

a = b + c

d = d + b

e = b + a

Reg

a = b + c

d = d + b

e = b + a

lw $8, b

lw $9, c

b

c

a

add $9, $8

sw a, $9

lw $9, d

d

add $9, $8

lw $9, a

e

add $8, $9

Spilling

• Happens when not enough registers available
• “Swaps” variable in register for variable in memory
• Variables can be un-spilled if registers open up
• Second Chance Bin Packing

c

a

b

d

e

c

a

b

d

e

e

a

b

c

d

d

c

b

a

e

Reg

a = b + c

d = d + b

e = b + a

b

lw $8, b

lw $9, c

lw $10, d

c

d

add $9, $8

a

add $10, $8

add $8, $9

e

c

a

b

d

e

d

c

b

a

e

Chaitin’s Algorithm

• Uses k-coloring to allocate registers
• Takes longer to compile
• Allocation is more optimized than linear scan
• Graph coloring is NP-Complete
• Relies heavily on heuristics
• Briggs et al contribution for spilling

c

a

b

d

e

e

a

b

c

d

b

c

a

d

e

d’

a’

Reg

a = b + c

d = d + b

e = b + a

lw $8, b

lw $9, c

b

c

a

add $9, $8

sw a, $9

lw d, $9

d

add $9, $8

lw $9, a

e

add $8, $9

c

a

b

d

e

b

c

a

d

e

d’

a’

Resources

https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/17/Slides17.pdf

https://dash.harvard.edu/bitstream/handle/1/34325454/tr-21-97.pdf;jsessionid=459FDE826D321EAA23EE5197A997768B?sequence=1

https://www.researchgate.net/publication/2392358_Improvements_to_Graph_Coloring_Register_Allocation

https://www.inf.ed.ac.uk/teaching/courses/copt/lecture-7.pdf

https://people.cs.rutgers.edu/~farach/pubs/cc99-tk.pdf

https://kodu.ut.ee/~varmo/TM2010/slides/tm-reg.pdf

http://www.cs.toronto.edu/~pekhimenko/courses/cscd70-w19/docs/Lecture%206%20[Register%20Allocation]%2002.14.2019.pdf