Faster Chaitin-like Register Allocation via Grammatical Decompositions of Control-Flow Graphs

A compiler has to pack a program's variables into a small fixed set of CPU registers so that two variables alive at the same time never share one — a classic hard problem — and a known speed-up is to exploit the fact that the control-flow graphs of real programs are unusually simple in shape; this paper (HKUST) points out that the graph measure people use for that (treewidth) is looser than it needs to be, since it also admits shapes that no real program produces, and instead builds a grammar that generates exactly the graphs real programs can have, giving a decomposition that runs the same style of algorithm far faster — dropping the dependence on the variable count from a sixteenth power to a fifth.

Why this problem is worth solving

The reason this is worth a new graph theory is that register allocation is one of the oldest and most consequential problems a compiler solves.

The special structure everyone leans on has, until now, been captured by a parameter that is close but not exact.

What people did before, and where it broke

• Solve register allocation on general graphs. Treat it as graph coloring and use the standard heuristics and exact methods for arbitrary interference graphs. Where it broke. Graph coloring is hard in general, so exact methods are expensive and heuristics give up optimality; nothing about the arbitrary-graph view exploits that program control-flow graphs are highly structured.
• Parameterize by treewidth. Use the fact that structured control-flow graphs have treewidth at most a small constant to build a tree decomposition and run dynamic programming, beating general-graph methods. Where it broke. Treewidth is only an upper bound on the shape; the algorithm ends up solving over the whole family of small-treewidth graphs, most of which are not control-flow graphs, so it carries a worse asymptotic cost than the real structure permits.
• Parameterize by pathwidth. Use pathwidth, a linear cousin of treewidth, when the structure is more path-like, for similar dynamic-programming speedups. Where it broke. Same fundamental looseness — pathwidth is another approximate measure of the sparsity, not an exact characterization of control-flow graphs, so it too pays for generality the programs never use.
• Restrict to easier sub-cases. Handle only programs or graphs where allocation is known to be easy (for instance without the full interference structure). Where it broke. These restrictions dodge the general structured-program case rather than solving it, and do not give a single method that is both exact and fast on the control-flow graphs that real compilers actually see.
• The gap. No one had a decomposition that captured exactly the graphs realizable as control-flow graphs — tight rather than an over-approximation — while still supporting the dynamic-programming machinery that makes treewidth so useful, which is what it would take to get algorithms whose running time reflects the true, narrower structure of programs.

How the grammatical decomposition works

The idea

Match the exact family, not a superset that happens to contain it. The whole gain comes from a precision argument. Treewidth is a genuine bound — structured control-flow graphs really do have treewidth at most 7 — but it is a one-way bound: the set of graphs with small treewidth is much bigger than the set of graphs that are actually control-flow graphs, so an algorithm keyed to treewidth wastes effort being correct on graphs no compiler will ever hand it. This paper instead characterizes the family exactly, with a grammar that generates precisely the control-flow graphs and nothing more, so the algorithm reasons only about the structures that occur. Getting efficiency by modeling the true, narrower object a system actually faces, rather than a convenient general superset, is the same discipline the zero-knowledge-compiler work covered elsewhere on this site relies on, where replacing a cost model borrowed from general hardware with one that matches the real target is exactly what unlocks the performance the generality was hiding.

Let the way programs are built become the way the graph is decomposed. Structured programs are compositional — a program is a sequence, a branch, or a loop wrapped around smaller programs — and their control-flow graphs inherit that compositional shape. The grammar makes this explicit: its productions are the rules for composing larger control-flow graphs from smaller ones, so a derivation in the grammar is a recipe for building the graph, and reading that recipe backwards gives a decomposition into the small pieces the program was assembled from. Dynamic programming then rides on this decomposition, solving register allocation on each small piece and merging along the derivation, just as tree-decomposition algorithms sweep a tree — but here the pieces are the program own building blocks. Decomposing a large graph into the smaller structural units it was composed from, so a hard global computation becomes a series of cheap local ones stitched together, is the same divide-and-conquer strategy the large-scale graph-training work covered elsewhere on this site is built on, partitioning an unwieldy graph into pieces that fit the computation so the whole becomes tractable.

Register allocation is the proving ground, and the numbers move. The payoff is concrete on the classical problem. For minimum-cost register allocation over a fixed number of registers, the previous treewidth-based algorithm ran in time proportional to the program size times the number of variables raised to the sixteenth power (times the register count); the grammatical decomposition brings that down to the number of variables raised only to the fifth power. For the decision version of spill-free allocation, the dependence on the number of registers likewise drops from an exponent of about sixteen times the register count to about five times it. These are asymptotic improvements over both the naive general-graph solutions and the state-of-the-art structure-aware methods, and the paper backs them with scalability experiments on spill-free allocation. Solving a classic constrained-assignment problem faster by exploiting the precise structure of the instances that arise, rather than treating them as arbitrary, is the same instinct the on-chip memory-allocation work covered elsewhere on this site follows, turning a hard packing-and-assignment problem into one an efficient method can dispatch by leaning on the structure of real workloads.

Following register allocation through the decomposition

This is the classical, hard version of the problem; the goal is an exact, efficient algorithm by exploiting program structure.

Why it works

• An exact characterization beats an upper bound. Treewidth admits many graphs that are not control-flow graphs, so algorithms keyed to it over-generalize → but a grammar that generates exactly the control-flow graphs reasons only about real structures → so the running time reflects the true, narrower family and improves asymptotically.
• The grammar mirrors how programs are built. A structured program is composed from sequences, branches, and loops → but that is precisely what the grammar productions encode, so a derivation decomposes the graph into the program own building blocks → so dynamic programming has small, meaningful pieces to work on.
• Small boundaries make the dynamic program cheap. Combining partial solutions is only fast if little information crosses each piece boundary → but the grammatical pieces keep that boundary information small → so the exponents in the running time shrink, from a sixteenth power to a fifth for the variable count in minimum-cost allocation.
• The same machinery transfers, so gains are not one-off. Treewidth is useful because one dynamic-programming template solves many problems → but the grammatical decomposition supports that same template, now on the exact family → so it yields faster algorithms for both register-allocation variants and, in principle, other compiler and analysis tasks.
• Theory that meets real programs stays practical. An exact structural result could be a curiosity if programs did not fit it → but every structured control-flow graph is generated by the grammar by construction → so the speedups apply to real code, and the experiments show scaling to large real-world spill-free instances.

What it costs (trade-offs and scope)

• This is a draft written without the paper’s main text. The full paper was behind access barriers for this draft (the publisher copy required bot verification, an open-archive copy was behind a proof-of-work wall, there is no arXiv version, and no web-archive snapshot exists), so this account is built from the paper’s abstract. The complexity results quoted — the drop from a sixteenth to a fifth power for minimum-cost allocation, and the reduced exponent for spill-free allocation — are the abstract’s own; the grammar itself, the dynamic-programming recurrences, the proofs, and the specific experimental instance sizes are not reproduced here and should be read from the paper.
• The improvement is asymptotic, and the exponents are still large. A fifth power in the number of variables is a big improvement over a sixteenth, but it is still a high-degree polynomial, and the spill-free bound remains exponential in the number of registers (just with a smaller exponent); how these translate to wall-clock time depends on constants and instance sizes the abstract does not give in full.
• It targets Chaitin’s formulation specifically. The results are for Chaitin-style register allocation, which notably does not allow live-range splitting; modern allocators often do split live ranges, so the exact model here is the classical one, and extending the approach to splitting or to other allocation models is not something the abstract claims.
• The decomposition is tied to structured control flow. The grammar captures control-flow graphs of structured programs; how the approach handles unstructured control flow (arbitrary gotos, irreducible loops) that can arise in real code is a matter for the full paper, and the strength of the exact-characterization argument depends on the programs genuinely being structured.
• Evidence beyond complexity is one experiment set. The paper reports scalability experiments on spill-free allocation against prior state-of-the-art; this is a targeted demonstration of practicality rather than a broad empirical study across allocation variants, compilers, or production pipelines, and the abstract cuts off before stating the full instance scale.

The evaluation

Check yourself

Sources

The paper is “Faster Chaitin-like Register Allocation via Grammatical Decompositions of Control-Flow Graphs” by Xuran Cai, Amir Kafshdar Goharshady, S. Hitarth, and Chun Kit Lam (Hong Kong University of Science and Technology), published at ASPLOS 2025 (Volume 1), DOI 10.1145/3669940.3707286.

This explainer is a draft. The paper’s main text was not accessible at the time of writing (the ACM Digital Library copy returned a bot-verification challenge, an open-access copy on the HAL archive was behind a proof-of-work wall, there is no arXiv version, and no web-archive snapshot exists), so it is written from the paper’s abstract. The abstract supplies the problem framing (control-flow graphs of structured programs are sparse, formalized via treewidth and pathwidth for fast parameterized algorithms in compiler optimization, model checking, and program analysis), the central observation (known sparsity parameters do not exactly capture control-flow-graph sparsity, since all structured control-flow graphs have treewidth at most 7 but not every treewidth-7 graph is realizable as a control-flow graph, so current algorithms solve over a more general family), the contribution (a graph decomposition based on a grammar that precisely captures the set of graphs realizable as control-flow graphs, enabling the same dynamic-programming algorithms used in treewidth and pathwidth methods), and the two applications to Chaitin’s register allocation (which does not allow live-range splitting) with their complexity results: minimum-cost register allocation over a fixed number of registers improving from a runtime proportional to the program size times the number of variables to the sixteenth power (times the register count) down to the fifth power, and spill-free register allocation improving the register-count exponent from about sixteen times to about five times the number of registers, together with experiments on spill-free allocation showing scalability to large real-world instances against prior state-of-the-art methods. The grammar itself, the dynamic-programming algorithms and proofs, and the specific experimental instance sizes are not reproduced here and should be read from the paper; no numbers beyond the abstract’s have been introduced.