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 and y alive
  xyzt1t2t3
  **        
  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
www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Friday, 24-Nov-2017 04:27:21 EST.

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