|
|
- 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 |
* = 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 |
|
|