Register Allocation

  1. Register allocation is the process of determining storage locations to the values used in a program.
  2. These values can either be stored in registers or in memory.
  3. Registers provide fast access but are limited in number.
  4. Memory has much higher latency and slower access speeds.
  5. A good register allocation strategy keeps frequently accessed variables in registers to maximize performance.

much of the material for these slides comes from fernando

terms

  1. The task of determining the register in which each variable will be stored is known as register assignment.
  2. If a variable must be stored in memory, it is referred to as a spill. Spilling involves identifying which variables need to be mapped to memory.
  3. If the same register can be assigned to two variables related by a move instruction, the move can be eliminated. This optimization is called coalescing.

more terms

  1. GPU performance often improves when fewer registers are used.
  2. Variables in Bril are virtual registers. After assignment, they become physical registers.

Register allocators often have to manage constraints. For example, a function argument may need to be placed in a specific physical register.

Formal Limits

Register allocation is NP complete. Given a program P and K registers, is there an assignment where each variable gets a register and all simultaneously live variables get different registers

Gregory Chaitin showed that if we have a graph that we want to paint with K colors, such that adjacent vertices get different colors we can construct a program where the program can be allocated with K registers iff the graph can be colored with K colors

Interference Graph

Chaitin used the interference graph. One vertex for each variable, and edge between variables that are simultaneously live.

Two variables that interfere cannot be in the same register

Allocation and Liveness

If two variables are alive at the same point, and they have different values, they have to be assigned different registers

Approximate this by ignoring “have different values” - Different registers if alive at the same point. (id is special)

MaxLive is the max number of values live at the same point

MinReg is the min number of registers we need

minReg >= MaxLive

an example

  1. What is the maximum number of variables alive at any program point?
  2. What is the interference graph of this program?

draw it?

interference graph

MaxLive = 2 Can we compile this with 2 registers? - Need 3

draw it?

The interference graph is a pentagon, needed 3 registers.

A pentagon is the smallest graph whose chromatic number (number of colors needed 3 ) is less the maximum clique (2)

SSA Form

with liveness

ssa with interference graph

register allocation

swaps

We need to copy e2 to e, but we have no registers left, so how do we swap them?

swaps via xor

final code

ssa based register allocation

We have been able to compile the SSA-form program with less registers than the minimum that the original program requires.

Two claims

  1. The SSA-form program will never require more registers than the original program.
  2. And we can find the minimum number of registers that the SSA-form program needs in polynomial time.

setting up the colors

suppose we have an ordering of the vertices, where the neighbors of a node to the left of the node in the ordering from a clique. If there are K such neighbors we need K+1 colors

an example

Code 
%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TD;
n1--> n2 --> n3 -->  n4 --> n5 --> n6--> n1

%%{init: {"flowchart": {"htmlLabels": false}} }%%

graph TD;
n1--> n2 --> n3 -->  n4 --> n5 --> n6--> n1

draw it

given this order - it is simple to pick the colors

once we have an order , we can greedy color the nodes. When we get to the n’th node, all the neighbors are in a clique and are colored, so just pick one

maybe try not to clobber a copy

all nodes in the clique need different colors

In a chordal graph the size of the largest clique equals the chromatic number

if we find the point in the program with max live variables, we know the chromatic number

how do we get the order

  1. give each node number
  2. initially each node gets count of zero 1 pick an unordered node with max count
  3. put that node in the front of the list, mark that node ordered
  4. increment each neighbor by 1

draw the example

dominance trees

What is the dominance tree of this program?

dominance tree

dom sub trees

interference graph

Chordal Graphs (triangular graphs)

  1. intersection graph of subtrees
  2. A graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle.
  3. if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chord free cycles have at most three nodes.

examples of chordal graphs

draw am example of a cord graph

orderings

we number the vertices of G

v0,v1,v2,…., vi, …

consider vi all the neighbors to the left are a clique (all connected )

running example

running example

running example

running example

running example

running example

running example

running example

coloring

once we have an order (the reverse order above), we can greedy color the nodes. When we get to the n’th node, all the neighbors are in a clique and are colored

all nodes in the clique need different colors

In a chordal graph the size of the largest clique equals the chromatic number

if we find the point in the program with max live variables, we know the chromatic number

spilling

if we ever have a program point where the number of live variables is > MaxRegs we will have to spill - so do it here

spilling

coalescing

if we assign both sides of a copy to the same register, we can eliminate the copy.

input: L list of copy instructions, G=(V,E), K
output: updated graph G'

G' = G
for all x=y in L
   sx is the set of colors in the neighborhood of x
   sy is the set of colors in the neighborood of y
   let c be a color < K that not in either set 
   add xy a new node xy is ajacent to all node in the union of neighborhoods 
   remove x and y from G'

xy is a merge of x and y

how do we know that ssa graphs are chordal

dominance and interference Thm 1

In a strict ssa form the definition of a variable dominates all the uses

lemma1 : if two variables interfere then the def of one dominates the def of the other

lemma2 if two variables a and b interfere and Da < Db, then a is live at Db

lemma3 if u,v,w are variables u-v interfere and v-w interfere and u-w do not if Du < Dv then Dv < Dw

thm: the interference graph of an ssa form program is chordal