chaitin-register-allocator

Answer

The Chaitin-Briggs register allocator is implemented in /tmp/chaitin_allocator.py (~17KB). The core algorithm has four phases:

1. Input Parsing & Interference Graph Construction

Three input formats are supported: - live-ranges: each virtual register has (vreg, start, end) defining its live range. Overlapping ranges produce interference edges. - ir: three-address code (e.g., v1 = v2 + v3). Live ranges are computed by tracking defs and last uses, then the interference graph is built from overlaps. - edges: direct edge list u v for each interference pair.

2. Spill Cost Computation

Spill cost is inversely proportional to live range length (shorter ranges = cheaper to spill). For IR input, costs are scaled by 1 + ln(use_count) to reflect that frequently-used variables are more expensive to reload from memory.

3. Simplify Phase

Iteratively pops nodes off the graph: - Low-degree nodes (degree < k) are pushed onto a stack (they're guaranteed colorable) - High-degree nodes are spilled based on spill_cost / degree ratio — the variable with the lowest cost per interference edge is spilled first

4. Select Phase

Nodes are popped from the stack in reverse order. Each node gets the lowest-numbered physical register (0..k-1) not used by any already-colored neighbor. If no color is available, the node is spilled.

Key code excerpt — the Chaitin-Briggs loop:

def chaitin_briggs_allocate(graph: InterferenceGraph) -> dict[int, int | None]:
    k = graph.num_regs
    work_graph = graph.copy()
    stack = []
    spilled = set()

    # ---- SIMPLIFY ----
    while work_graph.nodes:
        low_degree = work_graph.get_low_degree_nodes(k)
        if low_degree:
            # Remove highest-cost low-degree node (better coloring)
            node = max(low_degree, key=lambda n: work_graph.spill_cost.get(n, 1.0))
        else:
            # All high-degree: spill cheapest
            node = min(work_graph.get_high_degree_nodes(k),
                       key=lambda n: work_graph.spill_cost.get(n, 1.0) /
                                     max(work_graph.degree(n), 1))
            spilled.add(node)
        neighbors = list(work_graph.adj[node])
        stack.append((node, neighbors))
        work_graph.remove_node(node)

    # ---- SELECT ----
    assignment = {}
    for node, neighbors in reversed(stack):
        if node in spilled:
            assignment[node] = None
            continue
        used = {assignment[n] for n in neighbors
                if n in assignment and assignment[n] is not None}
        for c in range(k):
            if c not in used:
                assignment[node] = c
                break
        else:
            spilled.add(node)
            assignment[node] = None
    return assignment