Partitioned Boolean Quadratic Programming for Register Allocation

Coloring reduces allocation to one question, whether two values can share a register, and answers spills with a separate heuristic bolted onto the failure case. That separation is the source of most of the quality gap: a coloring allocator does not know, while it is coloring, that a particular assignment will force a spill, and it does not know that a particular coalesce will make a future spill more expensive. Partitioned Boolean quadratic programming puts both decisions into one objective. Each virtual register gets a cost for every possible assignment, each interference edge gets a matrix of costs for every pair of assignments, and a solver minimizes the sum. Spilling, coalescing, and register choice become entries in those tables rather than phases in a pipeline.

The formulation

A PBQP instance has three parts. The variables are the virtual registers, and each variable’s domain is the set of registers it may take, plus one extra value representing “spilled”. The node cost vector for variable v gives the cost of assigning v to each value in its domain. The edge cost matrix for an interfering pair (u, v) gives the cost of each combination of assignments, and it is infinite on the diagonal entries that would put both in the same register.

The objective is the sum of all node costs plus all edge costs. A solution assigns one value per variable, and the minimum of the objective is the best allocation under the model. The edge terms are quadratic in the assignment indicators, and every constraint is pairwise, which is what makes the reduction rules below meaningful.

The important structural fact is that the matrix for an interference edge is mostly infinite. If u and v interfere, the entry for “both in r5” is infinite, which makes that combination infeasible rather than expensive. The remaining finite entries encode preferences: assigning both to the same register class, or to registers that make a move free, can be cheaper than assigning them to unrelated registers. A move between u and v is represented by a finite, low-cost entry for the pairs of assignments where the move becomes a no-op, and a higher cost elsewhere.

Spilling enters as the last domain value. Assigning v to “spilled” costs the estimated reload cost from the spill cost model, and the edge matrix charges the interactions: a spilled value conflicts with nothing in the graph, so every entry in its row and column is finite and the solver can choose the spill whenever the reload cost is lower than the register cost.

Why the objective is better than the pipeline

The pipeline’s problem is that each phase optimizes a local quantity and the phases interact. Coalescing merges two values to remove a move, and the merged value may then spill, which turns the removed move into a load and a store. Coloring decides only whether K colors suffice and then picks one arbitrarily, so a value that would be cheapest in a callee-saved register can be left in a caller-saved one that then needs a save around every call. Spilling picks victims by cost-to-degree, and the victim may be a value whose spill forces the spill of several neighbours.

A single objective sees all of these at once. The edge matrix for a move can price the move elimination against the risk that the merged value spills, because the spill value is in the domain. The node cost for a caller-saved register can include the expected save cost, and the solver will choose a callee-saved register when the value’s lifetime makes that cheaper. The model is only as good as its cost numbers, but the numbers are at least comparable to each other, which they are not when they live in separate heuristics.

The formulation also handles the case that coloring handles badly: a graph that is colorable but only with an assignment that produces many moves. Coloring finds some coloring and stops; the PBQP solver finds the coloring that minimizes the total cost, including the moves. On graphs where the coloring is essentially forced, the two agree. On graphs with slack, meaning more registers than the clique number requires, the solver spends that slack on reducing moves, which is exactly where the pipeline leaves quality on the table.

Reduction rules instead of a general solver

Solving a general quadratic program is expensive, and the instances are structured enough that they can be solved by reduction. The rules eliminate variables one at a time, transforming the instance into a smaller one, and the sequence of eliminations is recorded so that the solution can be reconstructed by back-substitution.

The simplest rule handles a variable with degree zero: its node cost vector is minimized independently, the minimum is added to the constant term, and the variable is fixed to the minimizing value. A variable with degree one can be eliminated by folding its edge into its neighbor’s node vector: for each value of the neighbor, the cost of the best assignment of the eliminated variable is computed and added. The result is a new node vector for the neighbor, and the eliminated variable is fixed once the neighbor’s value is known.

The rule that makes the approach practical handles a variable of degree two, usually called R2. Its two edges can be merged into a single edge between its two neighbors, with each entry of the new matrix computed by minimizing over the values of the eliminated variable, which removes the variable without dropping the constraint it carried. Each application reduces the variable count by one and can increase the size of one matrix, so the rules are applied in an order that keeps matrices small: degree-zero and degree-one eliminations first, degree-two merges next, and a fallback that fixes a variable to its minimum-cost value when no rule applies without blowing up a matrix.

The fallback is where optimality is lost. It is a heuristic choice, equivalent in spirit to the coloring loop’s optimistic spill, and it makes the whole procedure a heuristic on general graphs. On an instance that reduces to empty without it, the assignment is optimal; the fallback is the only source of suboptimality the solver introduces.

Cost model construction

The model is only as good as the numbers. The following builds a node cost vector and an edge matrix for a small instance with two registers and a spill option, which is enough to show the structure.

INF = float("inf")

def node_cost(vreg, uses, is_loop, regs, spill_cost):
    # in this sketch any register costs 0; only the spill option is priced
    cost = {}
    for r in regs:
        cost[r] = 0
    cost["spill"] = spill_cost * uses * (10 if is_loop else 1)
    return cost

def edge_cost(u, v, interfere, move_related, regs):
    m = {}
    for a in list(regs) + ["spill"]:
        for b in list(regs) + ["spill"]:
            if interfere and a == b and a != "spill":
                m[(a, b)] = INF          # same register is impossible
            elif move_related and a == b:
                m[(a, b)] = 0            # the move becomes a no-op
            elif move_related:
                m[(a, b)] = 1            # the move costs one instruction
            else:
                m[(a, b)] = 0
    return m

Two features of this construction are worth pointing at. The spill value has no interference with anything, including another spill, because two spilled values can occupy the same stack slot only if their live ranges do not overlap; if they do overlap, the slot assignment problem is separate and is solved after allocation. The move entries are the mechanism by which coalescing happens: an edge between a move-related pair with a zero cost on equal assignments makes the solver prefer to merge them, and the interference entries on other pairs keep it from doing so when the merge is impossible.

The costs must be on a common scale. A spill cost of a hundred per use and a move cost of one per execution is a statement that a move is a hundred times cheaper than a reload, which is roughly true for a reload from L1 and wrong for one from a cold stack slot. The model cannot express that difference unless the spill cost is computed per value from its access pattern, which is why the cost model construction is the part of the implementation that receives the most tuning.

What the solver produces and what it costs

The output is an assignment for every variable, including the spilled ones, and the constant term accumulated during reduction is the objective value of that assignment. The assignment is not guaranteed optimal when the fallback fired, and it is guaranteed feasible only if the model’s infinite entries were respected. A solver that treats infinity as a large finite number can produce a solution that assigns two interfering values to the same register, which is a miscompile rather than a quality loss. Implementations use a saturating integer representation and check the result, or they use a representation in which infinite entries are structurally excluded from consideration.

The compile-time cost is the reason the approach is not universal. The reduction rules are simple, but the matrices can grow, and a graph with a few thousand variables and dense edges can produce matrices large enough that the reduction is slower than the coloring loop. Production implementations bound the matrix size and fall back to a simpler rule when the bound is exceeded, which caps the cost at the price of optimality. The trade is favorable for functions where the coloring heuristic struggles, such as high pressure, many moves, and complex control flow, and unfavorable for large functions with simple structure, where the coloring loop finishes quickly and the PBQP instance is large.

How it relates to the rest of the cluster

The formulation subsumes the earlier mechanisms rather than replacing them. Interference edges are the same edges built by liveness and graph construction; the infinite entries encode the same constraint that coloring enforces with distinct colors. The move edges encode the same preference that coalescing implements with its conservative tests, but without the need for a test, because the cost of a bad merge is expressed rather than forbidden. Spilling is a domain value rather than a post-pass, and live-range splitting appears as a refinement of the model: splitting a variable into two with a move between them changes the instance’s structure, and the solver then decides whether the split was worth it.

The limitation is the same one that limits every cost-based approach: the model’s numbers are estimates of dynamic behaviour derived from static structure, and the solver faithfully optimizes the estimates. A program whose hot loop is not identified by the loop weights will be allocated for the wrong objective, and no amount of solver quality fixes that. The advantage over the heuristic pipeline is that the estimate is applied consistently across all decisions at once, which removes the phase-ordering problem but not the estimation problem.