## Code Generation

### Register Allocation

- Hypothetical code sequence:
- ...
*-- x and y are in registers (alive) before*- t1 := x + 1;
- t2 := y + t1;
- t3 := y * t2;
- z := x + t3;
*-- want x and z to be in registers (alive) after*- ...

x and y alive | |||||||

x | y | z | t1 | t2 | t3 | ||
---|---|---|---|---|---|---|---|

* | * | ||||||

x + 1; | * | * | |||||

t1 := | * | * | * | ||||

y + t1; | * | * | * | ||||

t2 := | * | * | * | ||||

y * t2; | * | * | * | ||||

t3 := | * | * | |||||

x + t3; | * | * | |||||

z := | * | * | |||||

* | * | ||||||

x and z alive |

Register allocation can be treated as a graph-colouring problem.

#### Register Allocation Graph

- Vertices (variables):
- x, y, z, t1, t2, t3
- Edges (where (v1, v2) are alive at same times):
- (x,y), (x,z), (x,t1), (x,t2), (x,t3),
- (y,t1), (y,t2)
- Possible register allocation (vertex colouring):
- R1: x
- R2: y, z
- R3: t1, t2, t3
- Other choices are possible but we need at least 3 registers, e.g.,
for a typical 2-address machine: *-- x in R1 and y in R2*load R3, R1 add R3, literal 1 *-- t1 := x + 1*add R3, R2 *-- t2 := y + t1*mult R3, R2 *-- t3 := y * t2*load R2, R1 add R2, R3 *-- z := x + t3**-- x in R1 and z in R2*