Skip to main content

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;