Module register_alloc 

Certified linear-scan register allocation — the matching/Hall reasoner as a compiler back-end.

In a basic block (straight-line code) each variable is live over a contiguous range of instructions, so the interference graph — variables that are live at the same time — is an interval graph, which is perfect. Hence the minimum number of registers needed is exactly the register pressure: the most variables simultaneously live (the largest clique). If that fits the physical register count, a one-sweep interval_sched colouring assigns registers; if not, the over-pressure point yields R+1 mutually-live variables — a clique that provably cannot share R registers, so at least one must spill. The allocation is re-checkable, and the spill is certified by that clique (a Hall/pigeonhole witness) — no trusted solver, and far faster than throwing the colouring at a general SAT/SMT solver.

Structs

LiveRange

A variable’s live range over instruction positions [start, end).

Enums

Allocation

The result of allocating physical registers to a basic block.

Functions

allocate

Allocate registers physical registers to a basic block’s ranges, or certify that spilling is unavoidable. O(n log n) via the interval sweep.

is_spill_certificate

Re-check a spill certificate: the listed variables pairwise interfere (are mutually live) and number more than registers — so they cannot all reside in registers at once.

is_valid_allocation

Re-check an allocation: every variable is assigned a register < registers, and no two simultaneously-live variables share one.

register_pressure

The register pressure of a block: the most variables live at once (the fewest registers needed).