An optimizing compiler runs many analyses: constant propagation, value numbering, unboxing, closure analysis. Each is its own algorithm with its own kind of fact. We show that they find facts of one kind, a pattern that the arguments of every call of a block match, and we give one algorithm that finds the most specific such patterns.
Read the paper
Programs are basic blocks with arguments, as in SSA with block arguments or in
continuation-passing style. We write ?x where a variable is bound and
plain x where it is used. A pattern stands in place of a block's parameters and
says what every call of the block passes:
| Pattern | What it says | What it gives |
|---|---|---|
loop(?i, 1) |
the second argument is always 1 | constant propagation |
loop(?i, ?a, a) |
the last two arguments are always equal | value numbering |
loop(?i, (?s, u)) |
the second argument is always a pair, whose second field is the caller's u |
unboxing: the pair is never built |
app(inc⟨u⟩) |
the argument is always a closure of inc that captured u |
a direct call: the closure is never built |
dup(?s; k⟨ret⟩) |
the function always returns to the same place | contification |
Pick an example, or edit the program.
The step-by-step demo shows the rounds of the algorithm on every example of the paper, and the full explorer adds the specialization policies and runs both programs.
Constant propagation, value numbering, SSA construction, unboxing and contification are usually presented as separate analyses. We show that they can be seen as special cases of one analysis. The analysis finds a pattern (in the sense of ML pattern matching) that the arguments of every call to a block (a function, loop or branch target) match. A pattern can say that an argument is a constant, that two arguments are equal, that an argument is a pair, or that it is a known closure; rewriting the block to assume its pattern can then drop a constant parameter, merge two equal parameters, unbox a pair, and make a closure call a direct call. Patterns are stable if they hold for all calls/jumps that remain in the rewritten block. Stability is what we need for correctness: any set of stable patterns is sound for optimization. We give an algorithm that computes the most specific stable patterns, which generalizes many classical analyses. We prove correctness, optimality, and termination in Lean, for a core language. If we allow several patterns per block, the same algorithm becomes an inliner, a specializer of higher-order functions, or a partial evaluator, depending on the policy that chooses patterns. We illustrate these ideas: (1) in an optimizer for a dependently typed language, where it does monomorphization and compiles programs written with folds, streams and dictionaries of functions to tight loops, (2) by porting some of the ideas to Flambda 2 and Chez Scheme, to speed up some OCaml and Scheme benchmarks, (3) by comparing it experimentally to prior classical analyses.
@unpublished{grubmuller2026stablepatterns,
title = {Dataflow Facts as Stable Patterns},
author = {Grubm{\"u}ller, Fabian Lukas and Jacobs, Jules},
year = {2026},
month = nov,
note = {Manuscript},
url = {https://julesjacobs.com/papers/stable-patterns/}
}
If you work on a compiler and would like to try this in it, we would be glad to help. The video's chapter In your compiler says what the analysis needs from an intermediate representation, and Open problems lists what we do not know yet. If you would like to work on those as a student, see here.