DCC888 ：Register Allocation

Register Allocation

（0）These values might be stored either in registers, or in memory.
（1）Registers are fast, but they come in small quantity.
（2）Memory is plenty, but it has slower access time.
（3） A good register allocator should strive to keep in registers the variables used more often.

the three aspects of register allocation

register assignment

The task of determining in which register each variable will be kept

spill

If a variable must be mapped into memory, we call it a spill.
Spilling is the task of determining which variables must be mapped to memory.

coalescing

If we can assign the same register to two variables related by a move instruction, then we can eliminate this move. This optimization is called coalescing.

register constraints

maxLive ：MaxLive is the maximum number of registers that are simultaneously alive at any program point of the program’s control flow graph.
MinReg ：The minimum number of registers that a program needs,
MinReg > MaxLive


@ = e, c 该节点的input是c -> r1,e-> r2;
c = d， 该节点的input是d->r1, e->r2;
e = a, 该节点的input是d->r1, a->r2;此时发现与最开始的假设a->r1冲突。

Register Assignment is NP-Complete

Chaitin’s proof

the interference graph

Linear Scan

It is based on the greedy coloring of interval graphs:
– Given a sequence of intervals, we want to find the minimum number of colors necessary to paint them, so that overlapping intervals are given different colors.

Linearization of Basic Blocks

reverse post-order






first :r3 ->c
second: r1->a

intervals once spill

spill 到memory，将会打断variable生命周期

spill ：need store/load placemeng

coalescing

live ranges with holes

graph coloring register allocation

the interference graph

simplification的时候，将node一次放入栈中。
r3 - r1 - r2 - e - c - b - a - d
reverse order : d - a - b - c - e - r2 - r1 - r3

greedy coloring

iterated register coalescing

spilling heuristics

spilling

其中以d为例：2是d在loop之外的def和use，10的一次方是d的loop nesting factor是1，乘以2是因为loop之内有def和use两次，d的degree为4.