## Code Generation

 LA home Computing Prog.Langs  Code Gen.  Instn sets

### 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 y z t1 t2 x and y alive * * * * * * * * * * * * * * * * * * * * * * * * 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
www:
 The C++ Cookbook mastering the language

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Thursday, 21-Sep-2017 01:11:32 EDT.

 free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.