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)), 
      Move(Register(2), Memory(yAddr)),
      Move(Register(3), Memory(zAddr)),
      Quad(Register(4), Mul, Register(1), Register(2)),
      Quad(Register(2), Mul, Register(2), Register(3)),
      Quad(Register(4), Add, Register(4), Register(2)),
      Quad(Register(1), Mul, Register(1), Register(3)),
      Quad(Register(4), Add, Register(4), Register(1)),
      Move(Memory(rAddr), Register(4))

One solution:

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

A lot of research was done and better techiques were found

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:

• 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

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)

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

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)

• TIger book, Chapter 11
• Interprocedural Register Allocation