Register Allocation

Chaitin’s and Brigg’s  register allocator has different phases. 

Renumber:

Identification of Live ranges:

Live ranges identification is the backward Data flow problem. Live(v) = Availability & Anticipability.

According to Fred Chow based Priority Based Graph coloring each live unit in the live range is the basic block  used in open64 based compilers.

Building Interference Graphs:

Live ranges are used in building interference graph. There is an edge between live ranges if they are live at the same point. 

Coalescing:

If the live ranges don’t interfere, they can be coalesced. The coalescing technique are conservative coalescing and Aggressive coalescing. The conservative coalescing checks if after the coalescing the interference graph is colorable then the coalescing is performed. So, after each coalescing phase it checks whether the graph is colorable. 

Aggressive coalescing does the coalescing aggressively and in the simplification phase if it finds the interference graph is not colorable then it reverts the coalescing. This is what is being done on Aggressive coalescing.

Simplification.

From the interference graph each live range will be pushed into the stack. The unconstrained live ranges where the degree is less than K is taken from the interference graph and pushed into the stack. And the degree of each live range is updated and decremented for incident edge on the nodes that gets removed and pushed into the stack. The constrained nodes become unconstrained and move into the unconstrained nodes.

Most of the recent Register Allocator make the constrained nodes as priority and pushed into the stack first. As the Chaitain’s allocator  the graph is not colorable then live ranges are spilled but in the Brigg Allocator the live range is pushed into the stack instead of colorable so that there may be  a chance that the graph may become colorable.

Spilling.

During the Simplification phase even after inserting the stack there are no nodes left then the graph is colorable. If there are some nodes left, then the spilling is decided by considering the spilling costs which considers the 10 to the power of loop nesting depth multiplied with the weight.

The priority-based graph coloring by Fred chow select the live ranges for colorable based on priority. The priority is calculated by = weight * number of defs + weight* number of uses – weight * move costs/number of live units.

If the number of live units is more and the cost is same priority is less whereas if the number of live units is less than the priority is more. The register should be assigned to the shorter live ranges rather than longer live ranges. If the longer live ranges is assigned first and given the high priority than there is a chance of more spill and fetch as the registers are occupied for longer time.