which registers to use for coloring? which not?
register allocation update print x86
R1: Integers and Variables
exp ::= x | n | (op exp*) | (let ([x exp]) exp)
R1 ::= (program exp)
uniquify | V
exp ::= x | n | (op exp*) | (let ([x exp]) exp)
R1' ::= (program () exp)
remove-complex-opera* | V
arg ::= x | n
exp ::= arg | (op arg*) | (let ([x exp]) exp)
R1' ::= (program () exp)
create-CFG (the graph is empty for this assignment) | V
arg ::= x | n
exp ::= arg | (op arg*)
stmt ::= (assign x exp)
tail ::= (return exp) | (seq stmt tail)
C0 ::= (program () ((label . tail)*))
uncover-locals | V
arg ::= x | n
exp ::= arg | (op arg*)
stmt ::= (assign x exp)
tail ::= (return exp) | (seq stmt tail)
C0 ::= (program ((locals . x*)) ((label . tail)*))
select-instructions | V
imm ::= (var x) | (reg r) | (deref r n) | (int n)
instr ::= (addq imm imm) | (retq) | ...
block ::= (block () instr*)
x86 ::= (program ((locals . x*)) ((label . block)*))
assign-homes | V
imm ::= (reg r) | (deref r n) | (int n)
instr ::= (addq imm imm) | ...
block ::= (block () instr*)
x86 ::= (program ((stack-space . n)) ((label . block)*))
patch-instructions | V
same grammar as above
print-x86 | V
R2: Booleans and Conditionals
exp ::= x | n | #t | #f | (op exp*) | (let ([x exp]) exp) | (if exp exp exp)
R2 ::= (program exp)
type-check | V
exp ::= x | n | #t | #f | (op exp*) | (let ([x exp]) exp) | (if exp exp exp)
R2 ::= (program ((type . type)) exp)
remove-complex-opera* | V
arg ::= x | n | #t | #f
exp ::= arg | (op arg*) | (let ([x exp]) exp) | (if exp exp exp)
R2 ::= (program ((type . type)) exp)
create-CFG | V
arg ::= x | n | #t | #f
exp ::= arg | (op arg*)
tail ::= (return exp) | (seq stmt tail)
| (goto label) | (if (op arg*) (goto label) (goto label))
stmt ::= (assign x exp)
C1 ::= (program ((type . type)) ((label . tail)*))
optimize-jumps | V
same grammar as above
uncover-locals | V
arg ::= x | n | #t | #f
exp ::= arg | (op arg*)
tail ::= (return exp) | (seq stmt tail)
| (goto label) | (if (op exp*) (goto label) (goto label))
stmt ::= (assign x exp)
C1 ::= (program ((type . type) (locals . x*))
((label . tail)*))
select-instructions | V
imm ::= (var x) | (deref r n) | (int n)
instr ::= (addq imm imm) | ... | (jmp label) | (jmp-if cc label) | (retq)
block ::= (block () instr*)
x86 ::= (program ((locals . x*) (type . type)) ((label . block)*))
uncover-live | V
imm ::= (var x) | (deref r n) | (int n)
instr ::= (addq imm imm) | (jmp label) | (jmp-if cc label) | (retq)
block ::= (block (lives ls*) instr*)
x86 ::= (program ((locals . x*) (type . type)) ((label . block)*))
build-interference | V
block ::= (block () instr*)
x86 ::= (program ((locals . x*) (type . type) (conflicts . graph))
((label . block)*))
allocate-registers | V
imm ::= (reg r) | (deref r n) | (int n)
instr ::= (addq imm imm) | ... | (jmp label) | (jmp-if cc label) | (retq)
block ::= (block () instr*)
x86 ::= (program ((locals . x*) (type . type))
((label . block)*))
print-x86 | V
R3: Vectors
exp ::= x | n | #t | #f | (op exp*) | (let ([x exp]) exp) | (if exp exp exp)
| (vector exp*) | (vector-ref exp n) | (vector-set! exp n exp)
| (void)
R3 ::= (program exp)
type-check | V
type ::= ... | Void | (Vector type*)
exp ::= x | n | #t | #f | (op exp*) | (let ([x exp]) exp) | (if exp exp exp)
| (vector exp*) | (vector-ref exp n) | (vector-set! exp n exp)
| (void)
| (has-type exp type)
R3 ::= (program ((type . type)) exp)
expose-allocation | V
type ::= ... | Void | (Vector type*)
exp ::= x | n | #t | #f | (op exp*) | (let ([x exp]) exp) | (if exp exp exp)
| (vector exp*) | (vector-ref exp n) | (vector-set! exp n exp)
| (void) | (has-type exp type)
| (collect n) | (allocate n type) | (global-value x)
R3 ::= (program ((type . type)) exp)
remove-complex-opera* | V
arg ::= x | n | #t | #f | (void)
exp ::= arg | (op arg*) | (let ([x exp]) exp) | (if exp exp exp)
| (vector exp*) | (vector-ref exp n) | (vector-set! exp n exp)
| (void) | (has-type exp type)
| (collect n) | (allocate n type) | (global-value x)
R3 ::= (program ((type . type)) exp)
create-CFG | V
arg ::= x | n | #t | #f | (void)
exp ::= arg | (op arg*) | (allocate n type) | (global-value x)
| (has-type exp type)
tail ::= (goto label) | (if (op arg*) (goto label) (goto label))
| (return exp) | (seq stmt tail)
stmt ::= (assign x exp) | (collect n)
C2 ::= (program ((type . type)) ((label . tail)*))
uncover-locals | V
...
C2 ::= (program ((locals . ((x . type)*)) (type . type)
(flow-graph . ((label . tail)*))) tail)
select-instructions | V
imm ::= (var x) | (deref r n) | (int n) | (global-value x)
instr ::= (addq imm imm) | ... | (jmp label) | (jmp-if cc label) | (retq)
block ::= (block () instr*)
x86 ::= (program ((locals . ((x . type)*)) (type . type))
((label . block)*))
uncover-live | V
imm ::= (var x) | (deref r n) | (int n) | (global-value x)
instr ::= (addq imm imm) | ... | (jmp label) | (jmp-if cc label) | (retq)
block ::= (block (lives x**) instr*)
x86 ::= (program ((locals . ((x . type)*)) (type . type))
((label . block)*))
build-interference | V
...
x86 ::= (program ((locals . ((x . type)*)) (type . type)
(conflicts . graph))
((label . block)*))
build-move-graph | V
...
x86-CFG ::= (program ((locals . ((x . type)*)) (type . type)
(conflicts . graph) (move-graph . graph))
((label . block)*))
allocate-registers | V
imm ::= (reg x) | (deref r n) | (int n) | (global-value x)
instr ::= (addq imm imm) | ... | (jmp label) | (jmp-if cc label) | (retq)
x86 ::= (program ((locals . ((x . type)*)) (type . type))
((label . block)*))
patch-instructions | V
same as above
print-x96 | V
R4: Functions
type ::= ... | (type* -> type)
exp ::= x | n | #t | #f | (op exp*) | (let ([x exp]) exp) | (if exp exp exp)
| (vector exp*) | (vector-ref exp n) | (vector-set! exp n exp)
| (void)
| (exp exp*)
def ::= (define (var [var : type]*) : type exp)
R4 ::= (program def* exp)
type-check | V
R4 ::= (program () def+)
uniquify | V
same as above
limit-functions | V
same as above, but with a limit on the number of parameters to a function
reveal-functions | V
exp ::= (function-ref label) | (app exp exp*) | ...
tail ::= x | n | #t | #f | (op exp*) | (let ([x exp]) tail)
| (if exp tail tail)
| (vector exp*) | (vector-ref exp n) | (vector-set! exp n exp)
| (void)
| (function-ref label) | (tailcall exp exp*)
def ::= (define (var [var : type]*) : type tail)
F1 ::= (program () def+)
expose-allocations | V
same as above
remove-complex-opera* | V
arg ::= x | n | #t | #f | (void)
exp ::= ... | (op arg*) | (app arg arg*) | ...
tail ::= ... | (op arg*) | (tailcall arg arg*) | ...
def ::= (define (var [var : type]*) : type tail)
F1 ::= (program () def+)
create-CFG | V
arg ::= x | n | #t | #f | (void)
exp ::= arg | (op arg*) | (allocate n type) | (global-value x)
| (has-type exp type) | (app arg arg*)
tail ::= (goto label) | (if (op arg*) (goto label) (goto label))
| (return exp) | (seq stmt tail) | (tailcall arg arg*)
stmt ::= (assign x exp) | (collect n)
def ::= (define (var [var : type]*) : type ((label . tail)*))
C3 ::= (program ((type . type)) def+)
| V