rucc_regalloc/

lib.rs

//! Both register allocators and the allocation checker.
//!
//! Design: `spec/10-backend.md`. Layer rank 11, see `spec/18-package-layout.md`.
//!
//! # Status
//!
//! Liveness is here, which is the question both allocators ask first: [`order`] lays a function out
//! in the line the encoder will emit it in, and [`live`] says where in that line each value is
//! wanted. So is [`moves`], which puts the moves an edge turns into in an order they can be made in
//! one at a time. The single pass allocator's decision is in [`assign`]: where every value of a
//! function goes, in one linear scan, which is what `-O0` asks for. The rewrite that makes that
//! decision true in the function is in [`rewrite`], with what each instruction needs around it for
//! the machine to accept the places worked out in [`legalize`], and [`run`] is the two of them
//! together, which is the whole of the `-O0` allocator. [`check`] reads an assignment back and says
//! whether it is one the machine can run, which [`run`] asserts on in debug and CI builds and which
//! the backtracking allocator is held to the same way. [`trace`] asks the other half of the
//! question, which is whether the rewrite wrote that decision down without losing a value on the
//! way: it follows every value from the instruction that wrote it to the instructions that read it,
//! through the moves, and [`run`] asserts on it in the same builds.
//!
//! The allocator the optimizer uses is in [`backtrack`]. [`pressure`] counts, at every point, the
//! values that want a register against the registers there are, and [`spill`] reads that to pick
//! which values go to memory before [`backtrack`] places the rest.
//!
//! Every crate in the workspace is published, and publishing implies a promise. This one is
//! tier 3: its Rust API is explicitly unstable and will change without a major version bump.
//! Depend on the `rucc` binary's behaviour, not on this.

#![doc(html_root_url = "https://docs.rs/rucc-regalloc/0.15.3")]

pub mod assign;
pub mod backtrack;
pub mod check;
pub mod legalize;
pub mod live;
pub mod moves;
pub mod order;
pub mod pressure;
pub mod rewrite;
pub mod spill;
pub mod trace;

/// What allocating a function produced.
///
/// The moves are handed back rather than written into the function because a move is an
/// instruction and an instruction belongs to a target, which `spec/10-backend.md` section 10.8
/// says this crate holds nothing of. The consumer turns each one into whatever its target moves a
/// register with.
#[derive(Debug, Clone)]
pub struct Allocation {
    /// Where every value of the function went, which is what the frame layout reads.
    pub assignment: assign::Assignment,
    /// The moves the places do not already make true, in the order they have to be made in.
    pub edits: Vec<rewrite::Edit>,
    /// The line the function was laid out in while it was allocated, which the liveness below is
    /// counted along.
    pub order: order::Order,
    /// Where every value was live.
    ///
    /// Handed back rather than dropped because the stack slot allocator shares one run of bytes
    /// between two things that are never both wanted, and the only liveness that knows where a
    /// spilled value is wanted is the one the spilling was decided from. Working a second one out
    /// afterwards would cost a pass and would be free to disagree with this one.
    /// `spec/optimizer/36-lowering-and-isel.md` section 36.7 asks for the one answer.
    pub live: live::Live,
}

/// Allocates registers for a function the way `-O0` asks for, rewriting it as it goes.
///
/// This is the shape `spec/10-backend.md` section 10.4 gives an allocator: a function and the
/// registers it may use in, an assignment and the moves that make it true out. The backtracking
/// allocator will answer the same question the same way.
///
/// # Panics
///
/// Panics on a function the caller was told not to hand it, which is one with a critical edge or
/// one whose entry block has parameters. See [`rewrite::rewrite`].
///
/// It also panics on an assignment [`check`] finds a problem with, which is a bug in this crate or
/// in whatever produced the function rather than anything the caller did. `spec/10-backend.md`
/// section 10.4 asks for that check in debug and CI builds, and it runs before the rewrite because
/// the assignment is the decision and the rewrite only writes it down.
///
/// It panics on a rewrite [`trace`] finds a value missing from as well. That one runs afterwards,
/// since a transcription can only be read once it has been made, and it is the check
/// `spec/optimizer/39-register-allocation.md` section 39.6 asks for.
///
/// `verify` is what turns both of those on in a build that has assertions compiled out. A debug
/// build runs them whatever it says, since that is where a broken pass should be caught, and a
/// release build runs them when the caller asks, which is what `-Zverify-each` is for and what
/// section 10.4 means by a CI build. It is a parameter rather than a `cfg!` because the thing
/// worth catching is a pass that writes a function nothing defines a register in, the gate
/// compiles release, and a check the gate never runs is a check that finds the bug after the merge
/// rather than on the pull request. tamnd/rucc#1411.
///
/// `called` is what to call the function in that message. It is passed in rather than read off the
/// function because the name there is a symbol and resolving one wants the interner, which this
/// crate has no reason to be handed otherwise. Without it the message is a pair of register numbers
/// and nothing that says where, and finding the function it was about in a file the size of the
/// SQLite amalgamation means bisecting by hand.
pub fn run(func: &mut rucc_mir::Func, env: &assign::Env, called: &str, verify: bool) -> Allocation {
    run_with(func, env, called, verify, Allocator::Single)
}

/// Which of the two allocators decides where the values go.
///
/// The rewrite, the checks and the moves are the same for both, since each hands back an
/// [`assign::Assignment`] and nothing after the decision asks which one made it.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum Allocator {
    /// The single pass of [`assign`], which is what `-O0` asks for.
    #[default]
    Single,
    /// The allocator of [`backtrack`], which weighs what each value costs to keep in memory.
    Backtracking,
}

/// Allocates registers for a function with the allocator asked for, rewriting it as it goes.
///
/// # Panics
///
/// As [`run`].
pub fn run_with(
    func: &mut rucc_mir::Func,
    env: &assign::Env,
    called: &str,
    verify: bool,
    allocator: Allocator,
) -> Allocation {
    let checking = verify || cfg!(debug_assertions);
    let order = order::Order::of(func);
    let live = live::Live::of(func, &order);
    let mut assignment = match allocator {
        Allocator::Single => assign::assign(func, &order, &live, env),
        Allocator::Backtracking => backtrack::assign(func, &order, &live, env),
    };
    // An answer that went over the second source of an instruction that reads its sources either
    // way round. Swapping them makes it an ordinary reuse of the first, so the checker, the trace
    // and the rewrite read it as one. Liveness does not care which way round two uses are.
    for &inst in assignment.commuted() {
        let list = func[inst].operands;
        func[list].swap(1, 2);
    }
    if checking {
        let problems = check::check(func, &order, &live, &assignment);
        assert!(problems.is_empty(), "in '{called}': {}", check::report(&problems));
    }
    // What the rewrite is about to lose, taken while it is still there. Only in a build that is
    // going to read it, since the snapshot is a copy of every operand list in the function.
    let shape = checking.then(|| trace::shape(func));
    let edits = rewrite::rewrite(func, &mut assignment, env);
    if let Some(shape) = shape {
        let faults = trace::trace(func, &shape, &assignment, &edits);
        assert!(faults.is_empty(), "in '{called}': {}", trace::report(&faults));
    }
    Allocation { assignment, edits, order, live }
}

/// The milestone in `spec/17-milestones.md` that fills this crate in.
pub const MILESTONE: &str = "M3";

#[cfg(test)]
mod tests {
    use rucc_base::Interner;
    use rucc_mir::{Func, Opcode};
    use rucc_target::x86_64::{GPR, SYSV};

    use super::*;

    #[test]
    fn milestone_is_recorded() {
        assert!(MILESTONE.starts_with('M'));
    }

    #[test]
    fn allocating_a_function_places_every_value_and_hands_back_the_moves_it_needs() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let opcode = Opcode::new(names.intern("x64.nop"));
        let block = func.create_block();
        let first = func.new_vreg(GPR);
        let second = func.new_vreg(GPR);
        let third = func.new_vreg(GPR);
        func.build(block, opcode).def(first, GPR).finish();
        func.build(block, opcode).def(second, GPR).finish();
        func.build(block, opcode).def(third, GPR).finish();
        func.build(block, opcode).uses(first, GPR).uses(second, GPR).uses(third, GPR).finish();

        // Two registers to hand out and three values that are all wanted at once, so one of them
        // goes to the stack and the instruction that reads it gets a reload. This is also where
        // the checker runs, since a debug build asserts on what it says.
        let env = assign::Env::new().with(GPR, &SYSV.int_order[..2], &SYSV.int_order[2..5]);
        let allocation = run(&mut func, &env, "test", true);

        assert_eq!(allocation.assignment.spilled(), 1);
        assert_eq!(allocation.edits.len(), 2);
    }
}