# Register Allocation using Liveness Information

```static int x;
static int y;
static int z;
static int res;

int f() {
int xy;
int yz;
int xz;
int res1;
xy = x * y;
yz = y * z;
xz = x * z;
res1 = xy + yz;
res = res1 + xz;
}```

How to generate code that we saw in Register Machine in Scala

```      Move(Register(1), Memory(xAddr)),

One solution:

1. keep variables in registers when possible
2. reuse registers if variable not used any more
3. if no available register, free a register by saving it to memory ('spilling')

A lot of research was done and better techiques were found

## A Register Allocation Algorithm

Starting point:

• assign variables to memory
• assume temporary (intermediate) values will be in registers
• introduce explicit instructions to move between memory and registers

Goal is to assign temporaries to a limited number of K registers

If two temporary variables are both live at same point, we cannot keep them in same register

Algorithm phases:

#### Build: construct interference graph

• nodes are temporary variables
• there is edge if two variables both live at some program point

Goal: color the graph using K colors such that adjecent nodes have different color

• colors are registers
• if we need values of two temporaries, we can store them in different registers

#### SImplify

If there is a node with less than K neighbors, we will always be able to color it!

• so we can remove it from the graph

This reduces graph size

• it is incomplete
• e.g. every planar can be colored by at most 4 colors (and can have nodes with 100 neighbors)

#### Spill

If every node has K or more neighbors, we remove one of them

• we mark it as node for potentially spilling
• then remove it and continue

#### Select

Assign colors backwards, adding nodes that were removed

If we find a node that was spilled, we check if we are lucky that we can color it

• if yes, continue
• if no, insert instructions to save and load values from memory
• restart (now we have graph that is easier to color)