Content

Register Interference Graph
Algorithms
1. Chaitin's/Simplification Algorithm
2. Brigg's Optimistic Algorithm
3. Linear Scan Algorithm
4. Bin Packing Algorithm
Techniques
1. Spilling
2. Rewriting Code
3. Coalescing
4. Live Range Splitting
5. Building Interference Graph

Register Interference Graph

Algorithms

Chaitin's/Simplification Algorithm

Coloring G with K colors:
1. Find a node with < K incident edges
    - If cannot find, spill the node to memory (no stack); won't return
2. Prune the node
3. Recursively color the rest of the graph
4. Add back the node
5. Assign a valid color to the node

Not optimal. Runtime O(n^2).

Brigg's Optimistic Algorithm

If all nodes have degree >= K, push nodes onto stack & mark "possible spilling" instead of spilling them. They may still be colorable when working backwards.

Linear Scan Algorithm

1. Dataflow analysis to gather liveness info, sorted in increasing start point
2. Iterate through liveness start points, assign registers from pool
3. Maintain list of active intervals sorted by end point, remove expired intervals and release register
4. If no registers in pool, add current interval to active list, spill the interval with furthest end point, assign its register to current interval (or it is the one spilled)

Bin Packing Algorithm

1. Compute live ranges
2. Treat registers as bins holding 1 valid value at any point
3. View registers as containing a hole during free intervals
    - Reflect arbitrary constraints on register usage
4. Pack the same bin with 2 live ranges if
    - They don't interfere
    - One fits in another's live range hole
5. Live range is either in register or memory
    - Assign a temporary t to register r if
        - t not assigned & r has large enough hole
        - Choose r with smallest such hole
        - Otherwise, spill the lowest cost candidate
6. One pass for allocation, another for rewriting code

Techniques

Spilling

Minimize cost of spilling/degree
One that isn't used much (e.g. inner loop)

Rewriting Code

Shorten live ranges of the spilled variable to reduce interference.

add t1, t2;

# spill t2
-> invent new temporary variable t35
mv t35, M;
add t1, t35;

# rerun algorithm

Coalescing

Copy elimination at the register level.

mv t5, t9;

-> assign to the same register if no edge between them

May increase number of interference edges
- Avoid coalescing high-degree nodes
- Can be coalesced if neighbors of node a already interfere with node b, or has low degree

Live Range Splitting

Save value of a variable to memory at one point, and restore it at another point. Hard to find heuristics to decide which variable to split.

Assign a part of a live range to a register
Assign different parts of a live range to different registers

Building Interference Graph

in[B]     - variables live on entry of B
out[B]    - variables live on exit of B
def[B]    - variables assigned values in B before being used
use[B]    - variables used in B before being assigned to 

in[B] = use[B] ∪ (out[B] - def[B])
out[B] = ∪_succ_S_of_B(in[S])

for basic blocks B in program P:
    live = out[B]
    for reversed instructions I in B:
        for d in def(I):
            for n in (live ∪ def(I)):
                add edge <n, d>
        live = use(I) ∪ (live - def(I))

Also used in dead code elimination
- If some variable not live after some statements, those statements are dead

Register Allocation