CSE411: Introduction to Compilers

Register Allocation

Jooyong Yi (UNIST)

Register Allocation Problem

• The problem at hand: IR can use an unlimited number of virtual registers, but the machine has only a limited number of physical registers.
• Naive solution: map each virtual register to distinct a memory address.
  • But this is too slow.
• Goal: rewrite the IR to maximally utilize the physical registers, while minimizing the use of memory.

Register Allocation Problem Example

v3 = v1 + v2
v4 = v1 + v3
ret v4

• Assume we have only two physical registers, r1 and r2.

Register Allocation Problem Example

  v1, v4 ---------  r1       

  v2, v3 ---------  r2

v3 = v1 + v2  --->   r2 = r1 + r2
v4 = v1 + v3         r1 = r1 + r2 
ret v4               ret r1

How to Solve the Register Allocation Problem?

  v1, v4 ---------  r1       
  
  v2, v3 ---------  r2

v3 = v1 + v2  --->   r2 = r1 + r2
v4 = v1 + v3         r1 = r1 + r2 
ret v4               ret r1

Observations

v3 = v1 + v2  --->   r2 = r1 + r2
v4 = v1 + v3         r1 = r1 + r2 
ret v4               ret r1

• v1 and v2 are used at the same time.
  • We say that v1 and v2 interfere with each other.
• Thus, reg(v1) reg(v2)

Observations

v3 = v1 + v2  --->   r2 = r1 + r2
v4 = v1 + v3         r1 = r1 + r2 
ret v4               ret r1

• v1 and v2 interfere with each other. Thus, reg(v1) reg(v2)

    v1 ------ v2


    v3        v4

Observations

v3 = v1 + v2  --->   r2 = r1 + r2
v4 = v1 + v3         r1 = r1 + r2 
ret v4               ret r1

• v1 and v2 interfere with each other. Thus, reg(v1) reg(v2)
• v1 and v3 interfere with each other. Thus, reg(v1) reg(v3)

    v1 ------ v2
    | 
    |
    v3        v4

Interference Graph

    v1 ------ v2
    | 
    |
    v3        v4

• Nodes: variables
• Each edge connects variables interfering with each other.

Solving Register Allocation Problem with Interference Graph

    v1:r1  ------ v2: ?
    | 
    |
    v3            v4

Solving Register Allocation Problem with Interference Graph

    v1:r1  ------ v2: r2
    | 
    |
    v3            v4

Solving Register Allocation Problem with Interference Graph

    v1:r1  ------ v2: r2
    | 
    |
    v3:r2         v4: r1 or r2

Recall the Solution

    v1:r1  ------ v2: r2
    | 
    |
    v3:r2         v4: r1 or r2

  v1, v4 ---------  r1       
  
  v2, v3 ---------  r2

v3 = v1 + v2  --->   r2 = r1 + r2
v4 = v1 + v3         r1 = r1 + r2 
ret v4               ret r1

General Strategy

• Two key questions
  • Q1: How to construct the interference graph?
  • Q2: How to assign the registers to the nodes in the interference graph?

Q2: How to assign the registers to the nodes in the interference graph?

Graph Coloring Problem

• Adjacent nodes must have different colors.

Graph Coloring Problem

• NP-complete problem
• Still, there are efficient algorithms that work well in special cases.

Idea

• Assume that we have 3 colors.

Idea

• Assume that we have 3 colors.
• If we can successfully color , we can color .

Coloring by Simplification

• Input: Graph and the number of colors
• Algorithm
  • Find a node with fewer than neighbors.
  • Remove and its edges from . i.e.,
  • Recursively solve the problem with .

Simplification Example ()

Simplification Example ()

• Stack: 5

Simplification Example ()

• Stack: 5 2

Simplification Example ()

• Stack: 5 2 1

Simplification Example ()

• Stack: 5 2 1 3

Simplification Example ()

• Stack: 5 2 1 3

Simplification Example ()

• Stack: 5 2 1

Simplification Example ()

• Stack: 5 2

Simplification Example ()

• Stack: 5

Simplification Example ()

• Stack:

Another Example ()

Another Example ()

Another Example ()

• Pick a node and remove it from the graph.

Another Example ()

• Continue the simplification process.
• Hope: {b, c, d, e} use less than 3 colors.
  • This idea is called optimistic coloring.

Another Example ()

• Continue the simplification process.
• Hope: {b, c, d, e} use less than 3 colors.
  • This idea is called optimistic coloring.
• Does not work in our example and we need to spill f into the memory.

Spilling

• Before each operation that reads a spilled variable , insert
  • = load // : the memory address where the value of is stored
• After each operation that writes to a spilled variable , insert
  • store , // store the value of to

Spilling

• Which one to spill?
  • a node that interferes with many other nodes.
  • a node that is not frequently used.

Register Allocation

1. Build the interference graph
2. Apply the simplification algorithm
   1. If stuck, remove a node and try with the optimistic coloring.
   2. If the optimistic coloring fails, spill the node to the memory.
      1. This involves rewriting the code to load and store the value of the spilled variable.
      2. Repeat step 1.