rucc_regalloc/
lib.rs

1//! Both register allocators and the allocation checker.
2//!
3//! Design: `spec/10-backend.md`. Layer rank 11, see `spec/18-package-layout.md`.
4//!
5//! # Status
6//!
7//! Liveness is here, which is the question both allocators ask first: [`order`] lays a function
8//! out in the line the encoder will emit it in, and [`live`] says where in that line each value
9//! is wanted. So is [`moves`], which puts the moves an edge turns into in an order they can be
10//! made in one at a time. The single pass allocator's decision is in [`assign`]: where every value
11//! of a function goes, in one linear scan, which is what `-O0` asks for. The rewrite that makes
12//! that decision true in the function is in [`rewrite`], and [`run`] is the two of them together,
13//! which is the whole of the `-O0` allocator. [`check`] reads an assignment back and says whether
14//! it is one the machine can run, which [`run`] asserts on in debug and CI builds and which the
15//! backtracking allocator in M4 will be held to the same way. [`trace`] asks the other half of the
16//! question, which is whether the rewrite wrote that decision down without losing a value on the
17//! way: it follows every value from the instruction that wrote it to the instructions that read
18//! it, through the moves, and [`run`] asserts on it in the same builds.
19//!
20//! Every crate in the workspace is published, and publishing implies a promise. This one is
21//! tier 3: its Rust API is explicitly unstable and will change without a major version bump.
22//! Depend on the `rucc` binary's behaviour, not on this.
23
24#![doc(html_root_url = "https://docs.rs/rucc-regalloc/0.10.41")]
25
26pub mod assign;
27pub mod check;
28pub mod live;
29pub mod moves;
30pub mod order;
31pub mod rewrite;
32pub mod trace;
33
34/// What allocating a function produced.
35///
36/// The moves are handed back rather than written into the function because a move is an
37/// instruction and an instruction belongs to a target, which `spec/10-backend.md` section 10.8
38/// says this crate holds nothing of. The consumer turns each one into whatever its target moves a
39/// register with.
40#[derive(Debug, Clone)]
41pub struct Allocation {
42    /// Where every value of the function went, which is what the frame layout reads.
43    pub assignment: assign::Assignment,
44    /// The moves the places do not already make true, in the order they have to be made in.
45    pub edits: Vec<rewrite::Edit>,
46    /// The line the function was laid out in while it was allocated, which the liveness below is
47    /// counted along.
48    pub order: order::Order,
49    /// Where every value was live.
50    ///
51    /// Handed back rather than dropped because the stack slot allocator shares one run of bytes
52    /// between two things that are never both wanted, and the only liveness that knows where a
53    /// spilled value is wanted is the one the spilling was decided from. Working a second one out
54    /// afterwards would cost a pass and would be free to disagree with this one.
55    /// `spec/optimizer/36-lowering-and-isel.md` section 36.7 asks for the one answer.
56    pub live: live::Live,
57}
58
59/// Allocates registers for a function the way `-O0` asks for, rewriting it as it goes.
60///
61/// This is the shape `spec/10-backend.md` section 10.4 gives an allocator: a function and the
62/// registers it may use in, an assignment and the moves that make it true out. The backtracking
63/// allocator will answer the same question the same way.
64///
65/// # Panics
66///
67/// Panics on a function the caller was told not to hand it, which is one with a critical edge,
68/// one whose entry block has parameters, or one wanting more scratch registers at an instruction
69/// than the environment holds back. See [`rewrite::rewrite`].
70///
71/// In a debug build it also panics on an assignment [`check`] finds a problem with, which is a bug
72/// in this crate rather than anything the caller did. `spec/10-backend.md` section 10.4 asks for
73/// that check in debug and CI builds, and it runs before the rewrite because the assignment is the
74/// decision and the rewrite only writes it down.
75///
76/// A debug build panics on a rewrite [`trace`] finds a value missing from as well. That one runs
77/// afterwards, since a transcription can only be read once it has been made, and it is the check
78/// `spec/optimizer/39-register-allocation.md` section 39.6 asks for.
79///
80/// `called` is what to call the function in that message. It is passed in rather than read off the
81/// function because the name there is a symbol and resolving one wants the interner, which this
82/// crate has no reason to be handed otherwise. Without it the message is a pair of register numbers
83/// and nothing that says where, and finding the function it was about in a file the size of the
84/// SQLite amalgamation means bisecting by hand.
85pub fn run(func: &mut rucc_mir::Func, env: &assign::Env, called: &str) -> Allocation {
86    let order = order::Order::of(func);
87    let live = live::Live::of(func, &order);
88    let assignment = assign::assign(func, &order, &live, env);
89    if cfg!(debug_assertions) {
90        let problems = check::check(func, &order, &live, &assignment);
91        assert!(problems.is_empty(), "in '{called}': {}", check::report(&problems));
92    }
93    // What the rewrite is about to lose, taken while it is still there. Only in a build that is
94    // going to read it, since the snapshot is a copy of every operand list in the function.
95    let shape = cfg!(debug_assertions).then(|| trace::shape(func));
96    let edits = rewrite::rewrite(func, &assignment, env);
97    if let Some(shape) = shape {
98        let faults = trace::trace(func, &shape, &assignment, &edits);
99        assert!(faults.is_empty(), "in '{called}': {}", trace::report(&faults));
100    }
101    Allocation { assignment, edits, order, live }
102}
103
104/// The milestone in `spec/17-milestones.md` that fills this crate in.
105pub const MILESTONE: &str = "M3";
106
107#[cfg(test)]
108mod tests {
109    use rucc_base::Interner;
110    use rucc_mir::{Func, Opcode};
111    use rucc_target::x86_64::{GPR, SYSV};
112
113    use super::*;
114
115    #[test]
116    fn milestone_is_recorded() {
117        assert!(MILESTONE.starts_with('M'));
118    }
119
120    #[test]
121    fn allocating_a_function_places_every_value_and_hands_back_the_moves_it_needs() {
122        let mut names = Interner::new();
123        let mut func = Func::new(names.intern("f"));
124        let opcode = Opcode::new(names.intern("x64.nop"));
125        let block = func.create_block();
126        let first = func.new_vreg(GPR);
127        let second = func.new_vreg(GPR);
128        let third = func.new_vreg(GPR);
129        func.build(block, opcode).def(first, GPR).finish();
130        func.build(block, opcode).def(second, GPR).finish();
131        func.build(block, opcode).def(third, GPR).finish();
132        func.build(block, opcode).uses(first, GPR).uses(second, GPR).uses(third, GPR).finish();
133
134        // Two registers to hand out and three values that are all wanted at once, so one of them
135        // goes to the stack and the instruction that reads it gets a reload. This is also where
136        // the checker runs, since a debug build asserts on what it says.
137        let env = assign::Env::new().with(GPR, &SYSV.int_order[..2], &SYSV.int_order[2..5]);
138        let allocation = run(&mut func, &env, "test");
139
140        assert_eq!(allocation.assignment.spilled(), 1);
141        assert_eq!(allocation.edits.len(), 2);
142    }
143}
rucc_regalloc/lib.rs

rucc_regalloc/
lib.rs
