rucc_codegen/

finish.rs

//! The prologue, the epilogue, and the moves the allocator asked for.
//!
//! Design: `spec/10-backend.md` sections 10.4 and 10.7.
//!
//! [`crate::frame`] works out what a function's stack looks like and writes nothing. This is what
//! writes it. Three things are still missing from a function the allocator has finished with, and
//! all three of them are instructions no lowering rule chose:
//!
//! ```text
//!   the prologue     takes the frame the layout worked out, and puts away the registers a call
//!                    leaves alone that this function writes anyway
//!   the moves        every spill, every reload and every copy the allocator handed back as an
//!                    edit, in the place it said and in the order it said
//!   the epilogue     gives the frame back and puts the registers back, at the end of every block
//!                    the function returns from
//! ```
//!
//! There is a fourth thing and it is not an instruction but a number. The lowering wrote an
//! instruction for every `alloca` that computes the address of the memory it asked for, and could
//! not write how far into the frame that memory is, because when it ran there was no frame. So
//! the displacement of each of those is filled in here, out of the same [`Frame`] everything else
//! here reads, and off the same stack pointer every other offset in it is from.
//!
//! The loads that read the arguments the caller passed on the stack are waiting on the same number
//! and on one more. Those bytes are the caller's rather than this function's, and a frame that had
//! to force its own alignment cannot say how far away the caller's stack pointer was, so it reaches
//! back through the frame pointer instead. Which register a load reads through is therefore settled
//! here too, and it is the only base register in a finished function that was not settled by
//! whoever wrote the instruction.
//!
//! After this the function is one an encoder can read: every register is physical, every offset
//! into the frame is a constant, and the stack pointer is where the convention says it should be
//! at every instruction that could look.
//!
//! # Why the moves go in first
//!
//! Every offset the frame reports is from the stack pointer as it stands in the body of the
//! function. A spill written before the prologue exists would be written in front of the
//! instruction it belongs to and behind nothing, which is where the prologue then goes, so the
//! prologue ends up in front of it and the offsets stay true. Writing them the other way round
//! would put the first reload above the instruction that takes the frame, and it would read from
//! an address that is one frame out.
//!
//! # Where a return is
//!
//! A block that goes nowhere is a block the function leaves from. Mostly that is a return, and
//! the other kind is a block ending in `unreachable`, which is a point the front end says control
//! does not arrive at and which the lowering writes no instruction for. Both want the same thing
//! here. A return wants the epilogue because that is what a return is once the frame is known,
//! and an unreachable block wants it because the alternative is a function whose last instruction
//! falls into whatever the assembler put after it, which is worse than an epilogue nothing runs.
//! So the epilogue goes at the end of every block with an empty successor list, and there may be
//! several, because nothing here insists a function has one exit.
//!
//! # What is target-specific here
//!
//! The names, and only the names. Which instruction pushes a register and which one moves the
//! stack pointer is [`rucc_target::FrameInsts`], which the target says and this reads, so what
//! is written below is the shape of a prologue rather than any particular machine's. That is
//! `spec/10-backend.md` section 10.8 as it applies to the one pass that would otherwise be full
//! of `x64.` by hand.

use rucc_base::Interner;
use rucc_mir::{Block, BlockCall, CfiOp, Func, Inst, Mem, Opcode, Operand, Reg};
use rucc_regalloc::Allocation;
use rucc_regalloc::assign::Place;
use rucc_regalloc::rewrite::{At, Edit};
use rucc_target::{BranchInsts, CallRegs, FrameInsts, Guard, PhysReg, RegClass};

use crate::frame::Frame;
use crate::lower::Stack;

/// What the stack protector's check needs beyond the frame, in a function that has one.
///
/// Three things that come from three places, which is why they arrive together rather than being
/// looked up here. Where the word the canary is copied from lives is a fact about the runtime the
/// code is linked against. What a branch on a register is is a fact about the machine. And the two
/// registers are neither: they are the ones the allocator was told to hold back, which is a
/// decision about the allocator, and they are free at a return for exactly that reason.
#[derive(Debug, Clone, Copy)]
pub struct Protect<'a> {
    /// Where the word the canary is a copy of lives, and what to call when the copy has changed.
    pub guard: &'a Guard,
    /// What a branch on a register is, which is what the check ends its block with.
    pub branch: &'a BranchInsts,
    /// The two registers the check may use, which are two the allocator never handed out.
    pub scratch: [PhysReg; 2],
}

/// What the convention this function is compiled for says a frame is.
///
/// Three answers to the one question, which is why they travel together: where it puts things,
/// which instructions build one, and whether this function's carries a protector. The last is the
/// only one that is about this function rather than about every function on the target, and it is
/// here because what it needs is the other two and nothing else.
#[derive(Debug, Clone, Copy)]
pub struct Convention<'a> {
    /// Where the convention puts things.
    pub regs: &'a CallRegs,
    /// The instructions a prologue, an epilogue, a spill and a reload are made of on it.
    pub insts: &'a FrameInsts,
    /// What this function's stack protector needs, or `None` in a function with none.
    pub protect: Option<Protect<'a>>,
}

impl<'a> Convention<'a> {
    /// That convention, for a function with no stack protector, which is most of them.
    #[must_use]
    pub fn new(regs: &'a CallRegs, insts: &'a FrameInsts) -> Self {
        Self { regs, insts, protect: None }
    }
}

/// Writes the moves, the prologue and the epilogue into a function the allocator has finished
/// with.
///
/// # Panics
///
/// Panics on a function with no blocks in it, on a frame whose slots or locals the allocation and
/// the lowering do not match, and on a move of a class the target did not say how to move. All of
/// them are the caller handing it a frame and a function that were not worked out from each other.
pub fn finish(
    func: &mut Func,
    allocation: &Allocation,
    frame: &Frame,
    stack: &Stack,
    convention: Convention<'_>,
    names: &mut Interner,
) {
    let Convention { regs: conv, insts, protect } = convention;
    let entry = func.entry().expect("a function with a block in it");
    let returns: Vec<Block> = func.blocks().filter(|&block| func[block].succs.is_empty()).collect();

    // Before anything is written, because these are instructions the lowering already put in the
    // function and every one of them is somewhere the prologue is about to go in front of, which
    // is what makes an offset from the stack pointer the right thing to write into them.
    for &(inst, local) in &stack.addresses {
        let at = frame.local(local).expect("a local the frame was worked out from");
        let mem = func[inst].mem.expect("the address of a local is an address");
        func[mem].disp = at;
    }

    // The same, one area further up, and through the frame pointer when that is what reaches it.
    // These are in the entry block ahead of everything, so the prologue still goes in front of
    // them, which is what makes both registers hold what these offsets are counted from.
    let incoming = frame.incoming();
    for &(inst, up) in &stack.arguments {
        let mem = func[inst].mem.expect("an argument read out of memory is read from an address");
        func[mem].disp = incoming.at + offset(up);
        if incoming.through_frame_pointer {
            // The base register is an operand of the instruction and the addressing mode holds
            // where in the operand vector it is, so the register is changed there and not here.
            let at = func[mem].base.expect("an address the lowering wrote a base register into");
            let operands = func[inst].operands;
            func[operands][usize::from(at)].reg = Reg::physical(conv.frame_pointer);
        }
    }

    let mut writer = Writer { func, conv, insts, names };

    let mut cursors: Vec<(At, Inst)> = Vec::new();
    for edit in &allocation.edits {
        let inst = writer.mov(edit, frame);
        writer.put(&mut cursors, edit.at, inst);
    }

    let prologue = writer.prologue(frame, protect);
    for &inst in prologue.iter().rev() {
        writer.func.prepend_inst(entry, inst);
    }
    for block in returns {
        // The check goes in front of the epilogue and takes the return with it. What is left in
        // the block the function used to return from is the check, and the block the epilogue then
        // goes in is the arm the canary was unchanged on.
        let block = match protect {
            Some(protect) => writer.check(block, frame, protect),
            None => block,
        };
        let epilogue = writer.epilogue(frame);
        for inst in epilogue {
            writer.func.append_inst(block, inst);
        }
    }
}

/// One function having its frame written into it.
struct Writer<'a> {
    func: &'a mut Func,
    conv: &'a CallRegs,
    insts: &'a FrameInsts,
    names: &'a mut Interner,
}

impl Writer<'_> {
    /// The instructions the prologue is, in the order they run.
    ///
    /// The order is the one the epilogue undoes and it is not free. The frame pointer is saved
    /// before anything else, so that it points at a fixed place whatever else happens. The
    /// registers are pushed before the alignment is forced, so that the epilogue can find them
    /// again from the frame pointer, since after the alignment is forced nothing else can. And the
    /// vector registers are stored last, because until the frame has been taken there is nowhere
    /// to store them.
    fn prologue(&mut self, frame: &Frame, protect: Option<Protect<'_>>) -> Vec<Inst> {
        let sp = self.conv.stack_pointer;
        let fp = self.conv.frame_pointer;
        let int = self.conv.int_class;
        let sse = self.conv.sse_class;
        let word = offset(self.conv.word);
        let mut out = Vec::new();
        // How far the stack pointer is below the canonical frame address, and whether the address
        // is still counted from the stack pointer at all. It starts at the return address the
        // call itself pushed, which is the rule the CIE already states, so the first row here is
        // the first thing this function does on top of that.
        let mut below = offset(self.conv.return_address);
        let mut from_sp = true;
        if frame.frame_pointer() {
            let inst = self.push(fp);
            out.push(inst);
            below += word;
            self.row(inst, CfiOp::DefCfaOffset(below));
            self.saved(inst, int, fp, -below);
            let mov = self.opcode(self.insts.moves(int).expect("a move").mov);
            let inst = self.two(mov, fp, sp);
            out.push(inst);
            let number = self.dwarf(int, fp);
            self.row(inst, CfiOp::DefCfaRegister(number));
            from_sp = false;
        }
        for &reg in frame.saved_int() {
            let inst = self.push(reg);
            out.push(inst);
            below += word;
            if from_sp {
                self.row(inst, CfiOp::DefCfaOffset(below));
            }
            self.saved(inst, int, reg, -below);
        }
        if let Some(to) = frame.realign() {
            // Nothing is written for this and nothing can be. After it the stack pointer is a
            // rounded-down version of where it was rather than a fixed distance from it, which is
            // exactly what a rule cannot say. It is also why a frame that realigns is a frame
            // with a frame pointer: by here the address is already counted from that instead.
            assert!(!from_sp, "a frame that forces its own alignment has a frame pointer");
            let and = self.opcode(self.insts.align);
            out.push(self.arith(and, -i64::from(to)));
        }
        if frame.size() > 0 {
            let sub = self.opcode(self.insts.sub);
            let inst = self.arith(sub, i64::from(frame.size()));
            out.push(inst);
            below += offset(frame.size());
            if from_sp {
                self.row(inst, CfiOp::DefCfaOffset(below));
            }
        }
        for save in frame.saved_sse() {
            let inst = self.store(sse, save.reg, save.at);
            out.push(inst);
            // Where it went is an offset from the stack pointer in the body, and the address is
            // `below` above that, so the two make one constant. Unless the frame realigned, in
            // which case there is no such constant and the rule is left out rather than guessed;
            // the one convention that realigns and the one that preserves a vector register are
            // not the same convention, so nothing reaches this today.
            if frame.realign().is_none() {
                self.saved(inst, sse, save.reg, save.at - below);
            }
        }
        // Last of everything, because it writes into the frame and there is no frame to write into
        // until the stack pointer has moved. Nothing is described for either instruction: they
        // write a slot rather than save a register, and no unwinder wants to put a canary back.
        if let Some(protect) = protect {
            let at = frame.canary().expect("a protected function has a slot for its canary");
            let [into, _] = protect.scratch;
            out.push(self.read_guard(into, protect.guard));
            out.push(self.store(self.conv.int_class, into, at));
        }
        // The rules the body runs under, kept so that each epilogue can put them back rather than
        // leaving the next block reading whatever the last one ended on. See `epilogue`.
        if let Some(&last) = out.last() {
            self.row(last, CfiOp::RememberState);
        }
        out
    }

    /// The stack protector's check, written at the end of a block the function returns from.
    ///
    /// Gives back the block the epilogue goes in, which is a new one: the check has to be the last
    /// thing the old block does, and what follows it is one of two arms rather than the return.
    ///
    /// ```text
    ///   block that returned      reload the slot, read the word again, compare, branch
    ///   the arm it changed on    call the function that does not come back, and nothing after
    ///   the arm it did not       the epilogue, which the caller writes into what this gives back
    /// ```
    ///
    /// The two registers are the ones the allocator was told to hold back, so nothing here has to
    /// ask what is live: a scratch register holds nothing at the end of a block, because the only
    /// thing that writes one is a move the rewriter put in and every one of those is read by the
    /// instruction it was put in front of.
    fn check(&mut self, block: Block, frame: &Frame, protect: Protect<'_>) -> Block {
        let class = self.conv.int_class;
        let at = frame.canary().expect("a protected function has a slot for its canary");
        let [ours, theirs] = protect.scratch;

        let inst = self.load(class, ours, at);
        self.func.append_inst(block, inst);
        let inst = self.read_guard(theirs, protect.guard);
        self.func.append_inst(block, inst);
        let differ = self.opcode(self.insts.differ);
        let inst = self
            .func
            .build_loose(differ)
            .def(Reg::physical(theirs), class)
            .uses(Reg::physical(ours), class)
            .uses(Reg::physical(theirs), class)
            .finish();
        self.func.append_inst(block, inst);

        let failed = self.func.create_block();
        let ok = self.func.create_block();
        let cond = Opcode::new(
            self.names.intern(&format!("{}{}", protect.branch.prefix, protect.branch.cond)),
        );
        let inst = self.func.build_loose(cond).uses(Reg::physical(theirs), class).finish();
        self.func.append_inst(block, inst);
        // The first arm is the one taken when the condition held, and the condition is that the
        // two words differ, so the first arm is the one the canary was overwritten on.
        *self.func.succs_mut(block) = vec![BlockCall::to(failed), BlockCall::to(ok)];

        let call = self.opcode(self.insts.call);
        let symbol = self.names.intern(protect.guard.fail);
        self.func.build(failed, call).symbol(symbol).finish();
        ok
    }

    /// Reads the word the canary is a copy of into a register.
    ///
    /// The address is a constant and names no register at all, because where the block a thread
    /// has to itself begins is something only the machine knows and the segment register is what
    /// holds it.
    fn read_guard(&mut self, into: PhysReg, guard: &Guard) -> Inst {
        let class = self.conv.int_class;
        let load = self.opcode(self.insts.moves(class).expect("a class to load").load);
        self.func
            .build_loose(load)
            .def(Reg::physical(into), class)
            .mem(Mem::in_segment(guard.segment, guard.at))
            .finish()
    }

    /// The instructions the epilogue is, in the order they run.
    ///
    /// The vector registers are read back while the stack pointer is still where the body left it,
    /// because that is what their offsets are from. Then the stack pointer goes back to the last
    /// register the prologue pushed, which is arithmetic when the prologue knew how far it had
    /// moved and a read of the frame pointer when it did not.
    fn epilogue(&mut self, frame: &Frame) -> Vec<Inst> {
        let sp = self.conv.stack_pointer;
        let fp = self.conv.frame_pointer;
        let int = self.conv.int_class;
        let sse = self.conv.sse_class;
        let word = self.conv.word;
        let described = !self.func.cfi.is_empty();
        let mut out = Vec::new();
        // Where the body left things, which is where every epilogue starts from.
        let mut below = offset(self.conv.return_address)
            + offset(word) * self.pushes(frame)
            + offset(frame.size());
        let from_sp = !frame.frame_pointer();
        for save in frame.saved_sse() {
            let inst = self.load(sse, save.reg, save.at);
            out.push(inst);
            if frame.realign().is_none() {
                self.restored(inst, sse, save.reg);
            }
        }
        let pushed = u32::try_from(frame.saved_int().len()).expect("a frame");
        if frame.frame_pointer() {
            // No row for either of these. The address is counted from the frame pointer here and
            // this is what moves the stack pointer rather than the frame pointer, so the rule that
            // was true before it is still true after it.
            if pushed == 0 {
                let mov = self.opcode(self.insts.moves(int).expect("a move").mov);
                out.push(self.two(mov, sp, fp));
            } else {
                let lea = self.opcode(self.insts.lea);
                let back = -offset(word * pushed);
                out.push(self.address(lea, sp, fp, back));
            }
        } else if frame.size() > 0 {
            let add = self.opcode(self.insts.add);
            let inst = self.arith(add, i64::from(frame.size()));
            out.push(inst);
            below -= offset(frame.size());
            self.row(inst, CfiOp::DefCfaOffset(below));
        }
        for &reg in frame.saved_int().iter().rev() {
            let inst = self.pop(reg);
            out.push(inst);
            self.restored(inst, int, reg);
            below -= offset(word);
            if from_sp {
                self.row(inst, CfiOp::DefCfaOffset(below));
            }
        }
        if frame.frame_pointer() {
            let inst = self.pop(fp);
            out.push(inst);
            self.restored(inst, int, fp);
            // The frame pointer holds the caller's value again, so the address goes back to being
            // counted from the stack pointer, which by now is at the return address.
            let number = self.dwarf(int, sp);
            self.row(inst, CfiOp::DefCfa { reg: number, offset: offset(self.conv.return_address) });
        }
        let ret = self.opcode(self.insts.ret);
        let inst = self.func.build_loose(ret).finish();
        out.push(inst);
        // These take effect at the address just past the return, which is where the next block
        // begins, and the next block is body again. Popping the body's rules and pushing them
        // straight back leaves the stack one deep however many blocks the function returns from,
        // which is what makes one remembering in the prologue enough for all of them.
        if described {
            self.row(inst, CfiOp::RestoreState);
            self.row(inst, CfiOp::RememberState);
        }
        out
    }

    /// How many general purpose registers the prologue put on the stack, the frame pointer
    /// included.
    fn pushes(&self, frame: &Frame) -> i32 {
        let saved = i32::try_from(frame.saved_int().len()).expect("a frame");
        saved + i32::from(frame.frame_pointer())
    }

    /// One row of the unwind table, taking effect after that instruction.
    fn row(&mut self, inst: Inst, op: CfiOp) {
        self.func.cfi.push((inst, op));
    }

    /// A row saying the caller's copy of that register is that far from the canonical frame
    /// address, which is below it and so is negative.
    fn saved(&mut self, inst: Inst, class: RegClass, reg: PhysReg, from_cfa: i32) {
        let number = self.dwarf(class, reg);
        self.row(inst, CfiOp::Offset { reg: number, offset: from_cfa });
    }

    /// A row saying that register holds what the caller left in it again.
    fn restored(&mut self, inst: Inst, class: RegClass, reg: PhysReg) {
        let number = self.dwarf(class, reg);
        self.row(inst, CfiOp::Restore(number));
    }

    /// What an unwind table calls that register.
    fn dwarf(&self, class: RegClass, reg: PhysReg) -> u16 {
        self.conv.dwarf(class, reg).expect("a register a frame saves is one the table can name")
    }

    /// One edit as the instruction that makes it true.
    fn mov(&mut self, edit: &Edit, frame: &Frame) -> Inst {
        let moves = self.insts.moves(edit.class).expect("a class the target says how to move");
        match (edit.mov.to, edit.mov.from) {
            (Place::Reg(to), Place::Reg(from)) => {
                let mov = self.opcode(moves.mov);
                self.func
                    .build_loose(mov)
                    .def(Reg::physical(to), edit.class)
                    .uses(Reg::physical(from), edit.class)
                    .finish()
            }
            (Place::Reg(to), Place::Slot(slot)) => {
                let at = self.slot(frame, slot);
                self.load(edit.class, to, at)
            }
            (Place::Slot(slot), Place::Reg(from)) => {
                let at = self.slot(frame, slot);
                self.store(edit.class, from, at)
            }
            // The allocator expands this into two moves through a register of its own, because a
            // machine that could do it in one is not a machine any of this is written for.
            (Place::Slot(_), Place::Slot(_)) => {
                unreachable!("a move from one stack slot straight into another")
            }
        }
    }

    /// Puts an instruction where an edit says it goes, after whatever earlier edits went there.
    ///
    /// The edits at one place are in the order they have to be made in, so each one goes behind
    /// the last, and the first of them is what the place itself means.
    fn put(&mut self, cursors: &mut Vec<(At, Inst)>, at: At, inst: Inst) {
        if let Some(cursor) = cursors.iter_mut().find(|(place, _)| *place == at) {
            self.func.insert_after(cursor.1, inst);
            cursor.1 = inst;
            return;
        }
        match at {
            At::Before(before) => self.func.insert_before(before, inst),
            At::After(after) => self.func.insert_after(after, inst),
            At::StartOf(block) => self.func.prepend_inst(block, inst),
            // Behind everything in the block. A block the allocator puts an edge's moves at the
            // end of is one with a single edge out of it, and an edge like that is not an
            // instruction here: [`crate::layout`] writes the jump it becomes after this has run.
            // So the last instruction is an ordinary one, which may still be waiting on moves of
            // its own that have to be made before the edge's are.
            At::EndOf(block) => self.func.append_inst(block, inst),
        }
        cursors.push((at, inst));
    }

    /// Where a spill slot is, from the stack pointer in the body of the function.
    fn slot(&self, frame: &Frame, slot: u32) -> i32 {
        frame.slot(slot).expect("a slot the frame was worked out from")
    }

    /// Reads a register out of the frame.
    fn load(&mut self, class: RegClass, reg: PhysReg, at: i32) -> Inst {
        let load = self.opcode(self.insts.moves(class).expect("a class to load").load);
        let base = Operand::read(Reg::physical(self.conv.stack_pointer), self.conv.int_class);
        self.func
            .build_loose(load)
            .def(Reg::physical(reg), class)
            .mem(Mem::at(base).plus(at))
            .finish()
    }

    /// Writes a register into the frame.
    fn store(&mut self, class: RegClass, reg: PhysReg, at: i32) -> Inst {
        let store = self.opcode(self.insts.moves(class).expect("a class to store").store);
        let base = Operand::read(Reg::physical(self.conv.stack_pointer), self.conv.int_class);
        self.func
            .build_loose(store)
            .uses(Reg::physical(reg), class)
            .mem(Mem::at(base).plus(at))
            .finish()
    }

    /// Puts a general purpose register on the stack.
    fn push(&mut self, reg: PhysReg) -> Inst {
        let push = self.opcode(self.insts.push);
        self.func.build_loose(push).uses(Reg::physical(reg), self.conv.int_class).finish()
    }

    /// Takes a general purpose register back off the stack.
    fn pop(&mut self, reg: PhysReg) -> Inst {
        let pop = self.opcode(self.insts.pop);
        self.func.build_loose(pop).def(Reg::physical(reg), self.conv.int_class).finish()
    }

    /// One general purpose register written with another.
    fn two(&mut self, opcode: Opcode, to: PhysReg, from: PhysReg) -> Inst {
        let class = self.conv.int_class;
        self.func
            .build_loose(opcode)
            .def(Reg::physical(to), class)
            .uses(Reg::physical(from), class)
            .finish()
    }

    /// Two-address arithmetic on the stack pointer, which reads it and writes it back.
    fn arith(&mut self, opcode: Opcode, value: i64) -> Inst {
        let class = self.conv.int_class;
        let sp = Reg::physical(self.conv.stack_pointer);
        self.func.build_loose(opcode).def(sp, class).uses(sp, class).imm(value).finish()
    }

    /// One register written with an address rather than with what is at it.
    fn address(&mut self, opcode: Opcode, to: PhysReg, base: PhysReg, disp: i32) -> Inst {
        let class = self.conv.int_class;
        let base = Operand::read(Reg::physical(base), class);
        self.func
            .build_loose(opcode)
            .def(Reg::physical(to), class)
            .mem(Mem::at(base).plus(disp))
            .finish()
    }

    /// The opcode of that name, in the machine IR's spelling, which is the target's prefix and
    /// then the name the target gave.
    fn opcode(&mut self, name: &str) -> Opcode {
        Opcode::new(self.names.intern(&format!("{}{name}", self.insts.prefix)))
    }
}

/// A distance in a frame, as the signed number every offset is.
fn offset(bytes: u32) -> i32 {
    i32::try_from(bytes).expect("a frame under two gigabytes")
}

#[cfg(test)]
mod tests {
    use rucc_base::Interner;
    use rucc_mir::{BlockCall, print_func};
    use rucc_regalloc::assign::Env;
    use rucc_target::x86_64::{BRANCH, FRAME, GPR, R10, R11, REGS, SYSV, WIN64, XMM, xmm};

    use super::*;
    use crate::frame::{Layout, Local};

    /// An environment offering that many of the convention's registers, with everything after
    /// them held back as scratch.
    fn env(conv: &CallRegs, count: usize) -> Env {
        Env::new().with(GPR, &conv.int_order[..count], &conv.int_order[count..])
    }

    /// A function of that many values, every one written before any is read, allocated with that
    /// many registers to hand out. The same shape the frame layout's own tests are written
    /// against, so that a frame here is one that has already been checked there.
    fn pressure(conv: &CallRegs, values: usize, count: usize) -> (Func, Allocation, Interner) {
        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 regs: Vec<Reg> = (0..values).map(|_| func.new_vreg(GPR)).collect();
        for &reg in &regs {
            func.build(block, opcode).def(reg, GPR).finish();
        }
        for &reg in &regs {
            func.build(block, opcode).uses(reg, GPR).finish();
        }
        let allocation = rucc_regalloc::run(&mut func, &env(conv, count), "test");
        (func, allocation, names)
    }

    /// The function with its frame written into it, as the lines a dump would show.
    fn written(
        func: &mut Func,
        allocation: &Allocation,
        layout: &Layout<'_>,
        names: &mut Interner,
    ) -> Vec<String> {
        with_protector(func, allocation, layout, None, names)
    }

    /// The same, for a function the caller has decided is protected or is not.
    fn with_protector(
        func: &mut Func,
        allocation: &Allocation,
        layout: &Layout<'_>,
        protect: Option<Protect<'_>>,
        names: &mut Interner,
    ) -> Vec<String> {
        let frame = Frame::of(func, allocation, layout);
        let convention = Convention { protect, ..Convention::new(layout.conv, &FRAME) };
        finish(func, allocation, &frame, &Stack::default(), convention, names);
        print_func(func, names, &REGS)
            .lines()
            .filter(|line| !line.is_empty())
            .map(|line| line.trim().to_string())
            .collect()
    }

    /// Just the lines the frame put in, which is every line that is not the function it was
    /// given and not the shape of the dump around it.
    fn added(lines: &[String]) -> Vec<&str> {
        lines
            .iter()
            .map(String::as_str)
            .filter(|line| !line.contains("x64.nop"))
            .filter(|line| !line.starts_with("mfunc") && !line.starts_with("block") && *line != "}")
            .collect()
    }

    #[test]
    fn a_function_that_needs_no_frame_is_given_a_return_and_nothing_else() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 2, 4);
        let lines = written(&mut func, &allocation, &Layout::new(&SYSV, REGS), &mut names);

        // Two values and four registers, so nothing is spilled, nothing is saved and the stack
        // pointer never moves. A prologue of nothing is the right prologue for that.
        assert_eq!(added(&lines), ["x64.ret"]);
    }

    #[test]
    fn a_spill_is_a_store_and_a_reload_is_a_load() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 4, 2);
        let lines = written(&mut func, &allocation, &Layout::new(&SYSV, REGS), &mut names);

        // Two registers for four values, so two of them go to the stack. The store goes behind the
        // instruction that wrote the value and the load in front of the one that wants it, both at
        // the offsets the frame gave, which are below the stack pointer because a small leaf
        // function is entitled to the red zone.
        assert_eq!(
            lines,
            [
                "mfunc @f {",
                "block0:",
                "$rax = x64.nop",
                "$rcx = x64.nop",
                "$rdx = x64.nop",
                "x64.mov_mr_64 $rdx, [$rsp - 16]",
                "$rdx = x64.nop",
                "x64.mov_mr_64 $rdx, [$rsp - 8]",
                "x64.nop $rax",
                "x64.nop $rcx",
                "$rdx = x64.mov_rm_64 [$rsp - 16]",
                "x64.nop $rdx",
                "$rdx = x64.mov_rm_64 [$rsp - 8]",
                "x64.nop $rdx",
                "x64.ret",
                "}",
            ]
        );
    }

    #[test]
    fn the_frame_the_prologue_takes_is_the_frame_the_epilogue_gives_back() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 4, 2);
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { red_zone: false, ..base };
        let lines = written(&mut func, &allocation, &layout, &mut names);

        // The same function told it may not use the red zone takes sixteen bytes instead, and
        // every offset moves above the stack pointer to match.
        assert_eq!(
            added(&lines),
            [
                "$rsp = x64.sub_ri_64 $rsp, 16",
                "x64.mov_mr_64 $rdx, [$rsp]",
                "x64.mov_mr_64 $rdx, [$rsp + 8]",
                "$rdx = x64.mov_rm_64 [$rsp]",
                "$rdx = x64.mov_rm_64 [$rsp + 8]",
                "$rsp = x64.add_ri_64 $rsp, 16",
                "x64.ret",
            ]
        );
    }

    #[test]
    fn the_registers_the_prologue_pushes_come_back_in_the_opposite_order() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 13, 13);
        let lines = written(&mut func, &allocation, &Layout::new(&SYSV, REGS), &mut names);

        // Four registers a call leaves alone, pushed in the convention's order and popped in the
        // other one, which is the only order that gets each of them its own value back.
        assert_eq!(
            added(&lines),
            [
                "x64.push_64 $rbx",
                "x64.push_64 $r12",
                "x64.push_64 $r13",
                "x64.push_64 $r14",
                "$r14 = x64.pop_64",
                "$r13 = x64.pop_64",
                "$r12 = x64.pop_64",
                "$rbx = x64.pop_64",
                "x64.ret",
            ]
        );
    }

    #[test]
    fn a_function_that_keeps_a_frame_pointer_sets_it_up_and_leaves_by_it() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 4, 2);
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { frame_pointer: true, red_zone: false, ..base };
        let lines = written(&mut func, &allocation, &layout, &mut names);

        // The frame pointer is saved before anything else and points at where it was saved, so the
        // epilogue reaches the stack pointer through it rather than by counting the frame back.
        assert_eq!(
            added(&lines),
            [
                "x64.push_64 $rbp",
                "$rbp = x64.mov_rr_64 $rsp",
                "$rsp = x64.sub_ri_64 $rsp, 16",
                "x64.mov_mr_64 $rdx, [$rsp]",
                "x64.mov_mr_64 $rdx, [$rsp + 8]",
                "$rdx = x64.mov_rm_64 [$rsp]",
                "$rdx = x64.mov_rm_64 [$rsp + 8]",
                "$rsp = x64.mov_rr_64 $rbp",
                "$rbp = x64.pop_64",
                "x64.ret",
            ]
        );
    }

    #[test]
    fn a_realigned_frame_forces_the_alignment_after_it_has_pushed_what_it_saves() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 13, 13);
        let locals = [Local { size: 64, align: 32 }];
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { locals: &locals, ..base };
        let lines = written(&mut func, &allocation, &layout, &mut names);

        // Forcing the alignment throws away how far the stack pointer had moved, so the registers
        // are pushed before it happens and the epilogue counts back from the frame pointer to find
        // them. The frame pointer is required here whatever the flags said.
        assert_eq!(
            added(&lines),
            [
                "x64.push_64 $rbp",
                "$rbp = x64.mov_rr_64 $rsp",
                "x64.push_64 $rbx",
                "x64.push_64 $r12",
                "x64.push_64 $r13",
                "x64.push_64 $r14",
                "$rsp = x64.and_ri_64 $rsp, -32",
                "$rsp = x64.sub_ri_64 $rsp, 64",
                "$rsp = x64.lea_64 [$rbp - 32]",
                "$r14 = x64.pop_64",
                "$r13 = x64.pop_64",
                "$r12 = x64.pop_64",
                "$rbx = x64.pop_64",
                "$rbp = x64.pop_64",
                "x64.ret",
            ]
        );
    }

    #[test]
    fn every_block_the_function_returns_from_gets_an_epilogue() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let opcode = Opcode::new(names.intern("x64.nop"));
        let head = func.create_block();
        let left = func.create_block();
        let right = func.create_block();
        func.build(head, opcode).finish();
        *func.succs_mut(head) = vec![BlockCall::to(left), BlockCall::to(right)];
        func.build(left, opcode).finish();
        func.build(right, opcode).finish();
        let allocation = rucc_regalloc::run(&mut func, &env(&SYSV, 4), "test");
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { leaf: false, ..base };
        let lines = written(&mut func, &allocation, &layout, &mut names);

        // Both ways out get the frame given back, and the block that goes somewhere gets nothing,
        // because a block with an edge out of it is not a block anything returns from.
        assert_eq!(
            lines,
            [
                "mfunc @f {",
                "block0:",
                "$rsp = x64.sub_ri_64 $rsp, 8",
                "x64.nop block1, block2",
                "block1:",
                "x64.nop",
                "$rsp = x64.add_ri_64 $rsp, 8",
                "x64.ret",
                "block2:",
                "x64.nop",
                "$rsp = x64.add_ri_64 $rsp, 8",
                "x64.ret",
                "}",
            ]
        );
    }

    #[test]
    fn a_protected_function_writes_the_canary_last_and_checks_it_before_it_returns() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 4, 2);
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { leaf: false, protect: true, ..base };
        let guard = SYSV.guard.as_ref().expect("this convention has somewhere to keep the word");
        // The two the real pipeline holds back, which are held back in the environment above too:
        // it hands out the first two of the convention's order and keeps everything after them.
        let protect = Protect { guard, branch: &BRANCH, scratch: [R10, R11] };
        let lines = with_protector(&mut func, &allocation, &layout, Some(protect), &mut names);

        // The read of the word and the store into the slot come after the stack pointer has moved,
        // because there is no slot to store into until it has. The check is the last thing the
        // block that returned does and the epilogue is on the arm the canary was unchanged on, so
        // a function whose canary changed never gives its frame back and never returns.
        assert_eq!(
            added(&lines),
            [
                "$rsp = x64.sub_ri_64 $rsp, 24",
                "$r10 = x64.mov_rm_64 [fs:40]",
                "x64.mov_mr_64 $r10, [$rsp + 16]",
                "x64.mov_mr_64 $rdx, [$rsp]",
                "x64.mov_mr_64 $rdx, [$rsp + 8]",
                "$rdx = x64.mov_rm_64 [$rsp]",
                "$rdx = x64.mov_rm_64 [$rsp + 8]",
                "$r10 = x64.mov_rm_64 [$rsp + 16]",
                "$r11 = x64.mov_rm_64 [fs:40]",
                "$r11 = x64.cmp_set_ne_64 $r10, $r11",
                "x64.br_cond_8 $r11, block1, block2",
                "x64.call @__stack_chk_fail",
                "$rsp = x64.add_ri_64 $rsp, 24",
                "x64.ret",
            ]
        );
    }

    #[test]
    fn a_vector_register_a_windows_call_preserves_is_stored_and_read_back() {
        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();
        // An instruction that writes one of the vector registers Windows preserves, which is what
        // a rule for something that has to use it produces.
        func.build(block, opcode).operand(Operand::write(Reg::physical(xmm(6)), XMM)).finish();
        let allocation = rucc_regalloc::run(&mut func, &env(&WIN64, 4), "test");
        let lines = written(&mut func, &allocation, &Layout::new(&WIN64, REGS), &mut names);

        // No machine here pushes a vector register, so it is stored into the frame rather than
        // pushed, and the frame has to be taken before there is anywhere to put it.
        assert_eq!(
            added(&lines),
            [
                "$rsp = x64.sub_ri_64 $rsp, 24",
                "x64.movaps_mr $xmm6, [$rsp]",
                "$xmm6 = x64.movaps_rm [$rsp]",
                "$rsp = x64.add_ri_64 $rsp, 24",
                "x64.ret",
            ]
        );
    }
}