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 Of this node input yes c -> r1,e-> r2;
c = d, Of this node input yes d->r1, e->r2;
e = a, Of this node input yes d->r1, a->r2; At this point, the discovery and the initial assumption a->r1 Conflict .

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 To memory, Will interrupt variable Life cycle

spill ：need store/load placemeng

coalescing

live ranges with holes

graph coloring register allocation

the interference graph

simplification When , take node Put it on the stack at one time .
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

Among them d For example ：2 yes d stay loop In addition to the def and use,10 To the power of d Of loop nesting factor yes 1, multiply 2 Because loop Within def and use two ,d Of degree by 4.