rucc_regalloc/
lib.rs

1//! Both register allocators and the allocation checker.
2//!
3//! Design: `spec/10-backend.md`. Layer rank 10, 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.
16//!
17//! Every crate in the workspace is published, and publishing implies a promise. This one is
18//! tier 3: its Rust API is explicitly unstable and will change without a major version bump.
19//! Depend on the `rucc` binary's behaviour, not on this.
20
21#![doc(html_root_url = "https://docs.rs/rucc-regalloc/0.3.4")]
22
23pub mod assign;
24pub mod check;
25pub mod live;
26pub mod moves;
27pub mod order;
28pub mod rewrite;
29
30/// What allocating a function produced.
31///
32/// The moves are handed back rather than written into the function because a move is an
33/// instruction and an instruction belongs to a target, which `spec/10-backend.md` section 10.8
34/// says this crate holds nothing of. The consumer turns each one into whatever its target moves a
35/// register with.
36#[derive(Debug, Clone)]
37pub struct Allocation {
38    /// Where every value of the function went, which is what the frame layout reads.
39    pub assignment: assign::Assignment,
40    /// The moves the places do not already make true, in the order they have to be made in.
41    pub edits: Vec<rewrite::Edit>,
42}
43
44/// Allocates registers for a function the way `-O0` asks for, rewriting it as it goes.
45///
46/// This is the shape `spec/10-backend.md` section 10.4 gives an allocator: a function and the
47/// registers it may use in, an assignment and the moves that make it true out. The backtracking
48/// allocator will answer the same question the same way.
49///
50/// # Panics
51///
52/// Panics on a function the caller was told not to hand it, which is one with a critical edge,
53/// one whose entry block has parameters, or one wanting more scratch registers at an instruction
54/// than the environment holds back. See [`rewrite::rewrite`].
55///
56/// In a debug build it also panics on an assignment [`check`] finds a problem with, which is a bug
57/// in this crate rather than anything the caller did. `spec/10-backend.md` section 10.4 asks for
58/// that check in debug and CI builds, and it runs before the rewrite because the assignment is the
59/// decision and the rewrite only writes it down.
60pub fn run(func: &mut rucc_mir::Func, env: &assign::Env) -> Allocation {
61    let order = order::Order::of(func);
62    let live = live::Live::of(func, &order);
63    let assignment = assign::assign(func, &order, &live, env);
64    if cfg!(debug_assertions) {
65        let problems = check::check(func, &order, &live, &assignment);
66        assert!(problems.is_empty(), "{}", check::report(&problems));
67    }
68    let edits = rewrite::rewrite(func, &assignment, env);
69    Allocation { assignment, edits }
70}
71
72/// The milestone in `spec/17-milestones.md` that fills this crate in.
73pub const MILESTONE: &str = "M3";
74
75#[cfg(test)]
76mod tests {
77    use rucc_base::Interner;
78    use rucc_mir::{Func, Opcode};
79    use rucc_target::x86_64::{GPR, SYSV};
80
81    use super::*;
82
83    #[test]
84    fn milestone_is_recorded() {
85        assert!(MILESTONE.starts_with('M'));
86    }
87
88    #[test]
89    fn allocating_a_function_places_every_value_and_hands_back_the_moves_it_needs() {
90        let mut names = Interner::new();
91        let mut func = Func::new(names.intern("f"));
92        let opcode = Opcode::new(names.intern("x64.nop"));
93        let block = func.create_block();
94        let first = func.new_vreg(GPR);
95        let second = func.new_vreg(GPR);
96        let third = func.new_vreg(GPR);
97        func.build(block, opcode).def(first, GPR).finish();
98        func.build(block, opcode).def(second, GPR).finish();
99        func.build(block, opcode).def(third, GPR).finish();
100        func.build(block, opcode).uses(first, GPR).uses(second, GPR).uses(third, GPR).finish();
101
102        // Two registers to hand out and three values that are all wanted at once, so one of them
103        // goes to the stack and the instruction that reads it gets a reload. This is also where
104        // the checker runs, since a debug build asserts on what it says.
105        let env = assign::Env::new().with(GPR, &SYSV.int_order[..2], &SYSV.int_order[2..5]);
106        let allocation = run(&mut func, &env);
107
108        assert_eq!(allocation.assignment.spilled(), 1);
109        assert_eq!(allocation.edits.len(), 2);
110    }
111}
rucc_regalloc/lib.rs

rucc_regalloc/
lib.rs
