ralloc

暫存器分配

• http://web.cecs.pdx.edu/~mperkows/temp/register-allocation.pdf

The value in a dead temporary is not needed for the rest of the computation
– A dead temporary can be reused

• Basic rule:
– Temporaries t1 and t2 can share the same register if at any point 
  in the program at most one of t1 or t2 is live !
...

Graph Coloring Heuristic

• Observation:
– Pick a node t with fewer than k neighbors in RIG
– Eliminate t and its edges from RIG
– If the resulting graph has a k-coloring then so does the original graph

Why:
– Let c1,…,cn be the colors assigned to the neighbors of t in the reduced graph
– Since n < k we can pick some color for t that is different from those of its neighbors