logicaffeine_proof/register_alloc.rs
1//! Certified linear-scan register allocation — the matching/Hall reasoner as a compiler back-end.
2//!
3//! In a basic block (straight-line code) each variable is *live* over a contiguous range of
4//! instructions, so the interference graph — variables that are live at the same time — is an
5//! **interval graph**, which is perfect. Hence the minimum number of registers needed is exactly the
6//! **register pressure**: the most variables simultaneously live (the largest clique). If that fits
7//! the physical register count, a one-sweep `interval_sched` colouring assigns registers; if not,
8//! the over-pressure point yields `R+1` mutually-live variables — a clique that provably cannot share
9//! `R` registers, so at least one *must* spill. The allocation is re-checkable, and the spill is
10//! certified by that clique (a Hall/pigeonhole witness) — no trusted solver, and far faster than
11//! throwing the colouring at a general SAT/SMT solver.
12
13use crate::interval_sched::{peak_concurrency, schedule_or_overflow, Interval, ScheduleOutcome};
14
15/// A variable's live range over instruction positions `[start, end)`.
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub struct LiveRange {
18 /// The variable identifier.
19 pub var: usize,
20 /// First instruction the variable is live.
21 pub start: i64,
22 /// One past the last instruction the variable is live.
23 pub end: i64,
24}
25
26impl LiveRange {
27 /// Construct a live range for `var` over `[start, end)`.
28 pub fn new(var: usize, start: i64, end: i64) -> Self {
29 LiveRange { var, start, end }
30 }
31}
32
33/// The result of allocating physical registers to a basic block.
34#[derive(Clone, Debug, PartialEq, Eq)]
35pub enum Allocation {
36 /// Success: `(var, register)` pairs, every register in `0..registers`, no two
37 /// simultaneously-live variables sharing one (re-checkable via [`is_valid_allocation`]).
38 Allocated(Vec<(usize, usize)>),
39 /// Spilling is unavoidable: the block needs `pressure` registers, and `must_spill` is a set of
40 /// pairwise-live variables larger than the register count — a certified proof that they cannot
41 /// all be kept in registers (re-checkable via [`is_spill_certificate`]).
42 Spill {
43 /// Minimum registers the block requires (peak simultaneous liveness).
44 pressure: usize,
45 /// `> registers` mutually-live variables — the spill certificate.
46 must_spill: Vec<usize>,
47 },
48}
49
50/// The register pressure of a block: the most variables live at once (the fewest registers needed).
51pub fn register_pressure(ranges: &[LiveRange]) -> usize {
52 let tasks: Vec<Interval> = ranges
53 .iter()
54 .map(|r| Interval::new(r.start, r.end))
55 .collect();
56 peak_concurrency(&tasks)
57}
58
59/// Allocate `registers` physical registers to a basic block's `ranges`, or certify that spilling is
60/// unavoidable. O(n log n) via the interval sweep.
61pub fn allocate(ranges: &[LiveRange], registers: usize) -> Allocation {
62 let tasks: Vec<Interval> = ranges
63 .iter()
64 .map(|r| Interval::new(r.start, r.end))
65 .collect();
66 match schedule_or_overflow(&tasks, registers) {
67 ScheduleOutcome::Feasible(reg) => {
68 Allocation::Allocated(ranges.iter().zip(reg).map(|(r, m)| (r.var, m)).collect())
69 }
70 ScheduleOutcome::Infeasible(positions) => Allocation::Spill {
71 pressure: peak_concurrency(&tasks),
72 must_spill: positions.iter().map(|&i| ranges[i].var).collect(),
73 },
74 }
75}
76
77fn live_overlap(a: &LiveRange, b: &LiveRange) -> bool {
78 a.start < b.end && b.start < a.end
79}
80
81/// Re-check an allocation: every variable is assigned a register `< registers`, and no two
82/// simultaneously-live variables share one.
83pub fn is_valid_allocation(
84 ranges: &[LiveRange],
85 registers: usize,
86 reg_of: &[(usize, usize)],
87) -> bool {
88 if reg_of.len() != ranges.len() {
89 return false;
90 }
91 let reg: std::collections::HashMap<usize, usize> = reg_of.iter().copied().collect();
92 if reg.len() != ranges.len() || reg.values().any(|&r| r >= registers) {
93 return false;
94 }
95 for i in 0..ranges.len() {
96 for j in (i + 1)..ranges.len() {
97 if live_overlap(&ranges[i], &ranges[j])
98 && reg.get(&ranges[i].var) == reg.get(&ranges[j].var)
99 {
100 return false;
101 }
102 }
103 }
104 true
105}
106
107/// Re-check a spill certificate: the listed variables pairwise interfere (are mutually live) and
108/// number more than `registers` — so they cannot all reside in registers at once.
109pub fn is_spill_certificate(ranges: &[LiveRange], registers: usize, must_spill: &[usize]) -> bool {
110 if must_spill.len() <= registers {
111 return false;
112 }
113 let by_var: std::collections::HashMap<usize, &LiveRange> =
114 ranges.iter().map(|r| (r.var, r)).collect();
115 must_spill.iter().enumerate().all(|(a, v)| {
116 by_var.get(v).is_some_and(|rv| {
117 must_spill
118 .iter()
119 .skip(a + 1)
120 .all(|u| by_var.get(u).is_some_and(|ru| live_overlap(rv, ru)))
121 })
122 })
123}
124
125#[cfg(test)]
126#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/register_alloc/tests.rs"]
127mod tests;