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.
//!
//! There is a fifth thing on a command line that asked for the stack to be touched a page at a
//! time, and it is the only one of them that is written into the middle of a block rather than at
//! one end of the function. A variable length array moves the stack pointer by a number that is not
//! known until the declaration runs, so walking it a page at a time is a loop written around the one
//! instruction the lowering left, and that turns the block the declaration was in into four.
//!
//! 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_base::hash::Map;
use rucc_diag::Span;
use rucc_mir::{Block, BlockCall, CfiOp, Func, Inst, Mem, Opcode, Operand, Patch, Reg, Role};
use rucc_regalloc::Allocation;
use rucc_regalloc::assign::Place;
use rucc_regalloc::rewrite::{At, Edit};
use rucc_target::{BranchInsts, CallRegs, Chkstk, FrameInsts, Guard, PhysReg, Probe, 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 a function that takes its stack a page at a time needs beyond the frame.
///
/// What `-fstack-clash-protection` asks for, and the same three kinds of thing [`Protect`] is:
/// one fact about the platform, one about the machine, and two registers that are neither. See
/// [`rucc_target::Probe`] for what the sequence is defending against.
///
/// Read in two places, because a function has two ways of moving its stack pointer and the flag is
/// about both of them. The prologue takes the frame the layout worked out, and a variable length
/// array takes however many bytes its declaration asked for while the function runs. The same three
/// things answer both.
#[derive(Debug, Clone, Copy)]
pub struct Probing<'a> {
    /// What touches a page and how far apart the pages are.
    pub probe: &'a Probe,
    /// What a branch on a register is, which is what the loop under a large frame ends with.
    pub branch: &'a BranchInsts,
    /// The two registers the sequence may use, which are two the allocator never handed out.
    pub scratch: [PhysReg; 2],
}

/// What a profiler's hook at the top of a function is, in a function that has one.
///
/// What `-pg` asks for. See [`rucc_target::Trace`] for why there are two of these and what each of
/// them lets the hook see. Only the name survives to here, because by this point the flag has been
/// read against the target and a prologue that has the name has everything it needs.
#[derive(Debug, Clone, Copy)]
pub struct Tracing {
    /// What is called, which is a routine the runtime provides and not one the program wrote.
    pub name: &'static str,
    /// Whether the call goes in front of the prologue rather than once the frame is taken.
    pub early: bool,
}

/// The room at the top of a function for something to be written over later, in a function that
/// was promised any.
///
/// What `-fpatchable-function-entry=` asks for. The room is a run of the shortest instruction the
/// machine has that does nothing, and what makes it worth reserving is that it is never run for
/// long: a tracer or a live patcher writes a jump or a call over it once the program is up, and
/// what it needs from the compiler is a known address and a known number of bytes.
///
/// Two counts because the room can be on either side of the function's own label. Only the half
/// after it is written here, since the stream starts at the label and there is nowhere in it to put
/// the other half; the half in front is carried through so that whatever lays the function down can
/// lay that many bytes ahead of the symbol.
#[derive(Debug, Clone, Copy)]
pub struct Padding {
    /// What the instruction that does nothing is called on this target.
    pub name: &'static str,
    /// How many of them go in front of the function's own label.
    pub before: u32,
    /// How many go after it.
    pub after: u32,
}

/// What the convention this function is compiled for says a frame is.
///
/// Seven answers to the one question, which is why they travel together: where it puts things,
/// which instructions build one, whether this function's carries a protector, whether it is taken a
/// page at a time, whether the function opens with a landing pad, whether it calls a profiler on
/// the way in, and how much room it opens with for a patcher. The last five are the only ones about
/// this function rather than about every function on the target, and they are here because what
/// they need 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>>,
    /// What this function's probing prologue needs, or `None` when the frame is taken in one
    /// subtraction, which is what a command line that did not ask asks for.
    pub probe: Option<Probing<'a>>,
    /// What says an indirect branch may arrive at the top of this function, or `None` when the
    /// command line did not ask for one and on a target that has no such instruction.
    ///
    /// See [`rucc_target::FrameInsts::landing`]. A name rather than a flag because the flag has
    /// already been read against the target by the time this is built, and because a prologue that
    /// has the name has everything it needs.
    pub landing: Option<&'static str>,
    /// What this function's call to a profiler is, or `None` in one that makes none, which is every
    /// function on a command line that did not ask.
    pub trace: Option<Tracing>,
    /// What room this function opens with for a patcher, or `None` in one that was promised none,
    /// which is every function on a command line that did not ask.
    pub pad: Option<Padding>,
}

impl<'a> Convention<'a> {
    /// That convention, for a function with no stack protector, no probing, no landing pad, no
    /// call to a profiler and no room for a patcher, which is most of them.
    #[must_use]
    pub fn new(regs: &'a CallRegs, insts: &'a FrameInsts) -> Self {
        Self { regs, insts, protect: None, probe: None, landing: None, trace: None, pad: None }
    }
}

/// Which instruction each of the allocator's moves became.
///
/// A spill and a copy are both a `mov` once they are written, and so is an instruction the lowering
/// wrote that happens to move the same register to the same address. Telling them apart afterwards
/// by looking at them is guesswork, and a pass that guesses wrong about a store to a volatile
/// variable deletes a read the program insisted on. So what the allocator asked for is recorded as
/// it is written, and a later pass that is only allowed to touch the allocator's own moves has the
/// list rather than a heuristic. See [`crate::copies`], which is the one pass that reads this.
///
/// It is kept by instruction number rather than in a hash map, because that pass asks about every
/// instruction in the function and the numbers are dense.
#[derive(Debug, Default)]
pub struct Moves(Vec<Option<Edit>>);

impl Moves {
    /// What the allocator asked for at this instruction, or `None` at an instruction that is not
    /// one of its moves.
    #[must_use]
    pub fn at(&self, inst: Inst) -> Option<Edit> {
        self.0.get(inst.index()).copied().flatten()
    }

    /// Records that this instruction is what that move came to.
    pub fn record(&mut self, inst: Inst, edit: Edit) {
        if self.0.len() <= inst.index() {
            self.0.resize(inst.index() + 1, None);
        }
        self.0[inst.index()] = Some(edit);
    }
}

/// Writes the moves, the prologue and the epilogue into a function the allocator has finished
/// with.
///
/// Hands back which instruction each of the allocator's moves became, for the one pass that is
/// allowed to take one of them out again.
///
/// # 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,
) -> Moves {
    let Convention { regs: conv, insts, protect, probe, landing, trace, pad } = convention;
    let entry = func.entry().expect("a function with a block in it");

    // 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. In a
    // frame that grows it is an offset from the frame pointer instead, so the base register is
    // rewritten the way an incoming argument's is, and for a version of the same reason.
    //
    // Added rather than assigned. The instruction named here is the `lea` the lowering wrote, or
    // whatever [`crate::fold`] folded that `lea` into, and a reader that took it brought a
    // displacement of its own: the address of a local is where the object starts and reading a
    // field of it is some way past that. Assigning would throw the field offset away and read the
    // front of the object every time.
    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;
        if frame.grows() {
            rebase(func, inst, conv.frame_pointer);
        }
    }

    // The bytes a variable length array takes are already off the stack pointer by the time one of
    // these runs, so what is left to write is how far above the new stack pointer the array starts,
    // which is however much of the bottom of the frame belongs to the arguments of a call. That
    // area stays at the bottom wherever the bottom has moved to. Added rather than assigned for the
    // reason the loop above is: one of these folds into its readers like any other address, and a
    // reader that took it brought a displacement of its own.
    for &inst in &stack.dynamic {
        let mem = func[inst].mem.expect("the address of a growable local is an address");
        func[mem].disp += offset(frame.below());
    }

    // 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 {
            rebase(func, inst, conv.frame_pointer);
        }
    }

    // Every offset the frame reports is from this one register, which is the stack pointer in an
    // ordinary frame and the frame pointer in one that moves the stack pointer while it runs.
    let base = if frame.grows() { conv.frame_pointer } else { conv.stack_pointer };
    let mut writer = Writer { func, conv, insts, names, base, ahead: None };

    let mut cursors: Map<At, Inst> = Map::default();
    let mut moves = Moves::default();
    for edit in &allocation.edits {
        let inst = writer.mov(edit, frame);
        writer.put(&mut cursors, edit.at, inst);
        moves.record(inst, *edit);
    }

    // Before the epilogues, because this is what turns one block into four and the last of the four
    // is the one the function goes on to return from. A block that went nowhere before a variable
    // length array was walked in the middle of it is not the block that goes nowhere afterwards, and
    // an epilogue written into the wrong one of them gives the frame back before the body has run.
    if let Some(probing) = probe {
        for &took in &stack.grown {
            writer.walk(took, probing);
        }
    }

    // Almost nothing of either in a naked function, which is the whole of what the attribute asks
    // for and the only place in this file that knows the word. The frame is empty by the time one
    // gets here, since [`crate::pipeline`] refuses a naked function that wanted bytes, so what is
    // left to leave out is the part of the prologue that is written on somebody's instruction
    // rather than on the frame's: the room a patcher was promised and the profiler's hook, both of
    // which are a call or a run of bytes in front of a body that said it is the whole of the
    // function. The protector and the probe are already off, the first because the pipeline turned
    // it off and the second because it only fires on a frame there is none of.
    //
    // The landing pad stays. It is not the compiler adding something to the function, it is the
    // address of the function being made one an indirect branch may arrive at, and gcc writes it
    // in a naked function too.
    //
    // The epilogue is the one that matters. It is what writes the `ret`, and a naked function ends
    // where its own text ends, which for micropython's `nlr_push` is a jump somewhere else and for
    // everything else is the `ud2` the lowering put there.
    let bare = frame.naked();
    let prologue = writer.prologue(
        frame,
        protect,
        probe.filter(|_| !bare),
        landing,
        trace.filter(|_| !bare),
        pad.filter(|_| !bare),
    );
    for &inst in prologue.iter().rev() {
        writer.func.prepend_inst(entry, inst);
    }
    let returns: Vec<Block> = if bare {
        Vec::new()
    } else {
        writer.func.blocks().filter(|&block| writer.func[block].succs.is_empty()).collect()
    };
    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);
        }
    }

    // Last of everything, because the blocks a probing prologue made have to come in front of the
    // block the function used to begin with and the ones the protector's check makes are made
    // after that. Nothing has been laid out yet: `crate::layout` runs after this and puts every
    // block in its own order, and all this decides is which block the function is entered at.
    if let Some(ahead) = writer.ahead {
        let rest: Vec<Block> =
            writer.func.blocks().filter(|block| !ahead.contains(block)).collect();
        let order: Vec<Block> = ahead.into_iter().chain(rest).collect();
        writer.func.set_block_order(&order);
    }
    moves
}

/// Points every access to the frame that its instruction cannot carry the offset of at a scratch
/// register holding most of the address.
///
/// Nothing to do on x86, where every offset a frame has fits in the instruction. An AArch64 load
/// reaches a few kilobytes up from the stack pointer and `add` reaches four, so a local deep in a
/// large frame is written as `add x16, sp, #4096` and then the access four thousand and some bytes
/// closer, which is what gcc writes. The part left in the instruction is the low bits when the
/// instruction can carry those and nothing when it cannot, which is the unaligned offset a scaled
/// load refuses.
///
/// After the allocator's moves have been cleaned up rather than here in [`finish`], because that
/// pass reads what each scratch register holds between one move and the next and an address
/// written into one in the middle is not a move it knows about. The scratch register is one the
/// instruction does not read, and one of the two always is, since an access through the stack
/// pointer has no base register of its own to have been reloaded into a scratch.
pub fn far(
    func: &mut Func,
    insts: &FrameInsts,
    conv: &CallRegs,
    scratch: &[PhysReg],
    names: &mut Interner,
) {
    let Some(reaches) = insts.reaches else { return };
    let lea = Opcode::new(names.intern(&format!("{}{}", insts.prefix, insts.lea)));
    let frame = [conv.stack_pointer, conv.frame_pointer];
    let all: Vec<Inst> = func.blocks().flat_map(|block| func.insts(block)).collect();
    for inst in all {
        let Some(mem) = func[inst].mem else { continue };
        let amode = func[mem];
        let plain = amode.index.is_none()
            && amode.symbol.is_none()
            && amode.block.is_none()
            && amode.table.is_none()
            && amode.segment.is_none();
        let Some(at) = amode.base.filter(|_| plain) else { continue };
        let operands = func[inst].operands;
        let Some(from) = func[operands][usize::from(at)].reg.phys() else { continue };
        let Some(name) = names.resolve(func[inst].opcode.name()).strip_prefix(insts.prefix) else {
            continue;
        };
        if !frame.contains(&from) || reaches(name, amode.disp) {
            continue;
        }
        let read = |reg: PhysReg| {
            func[operands].iter().any(|op| op.role != Role::Def && op.reg.phys() == Some(reg))
        };
        let written = |reg: PhysReg| {
            func[operands].iter().any(|op| op.role == Role::Def && op.reg.phys() == Some(reg))
        };
        // A scratch register the instruction writes is free for the address, and so is one
        // nothing reads again. The cleanup keeps a value in scratch from one instruction to the
        // next, so a register this instruction does not read can still be holding one. Taking
        // that register put the frame address in `x16` just before a store read the value it had.
        let free = |reg: PhysReg| !read(reg) && (written(reg) || !live_after(func, inst, reg));
        let loaded = || {
            func[operands]
                .iter()
                .filter(|op| op.role == Role::Def && op.class == conv.int_class)
                .filter_map(|op| op.reg.phys())
                .find(|&reg| !read(reg) && !frame.contains(&reg))
        };
        // With neither free, one the instruction does not read is pushed around it and popped
        // back after, which moves the stack pointer and so every offset counted from it. That is
        // a store of one scratch register while the other is still wanted, which is rare. The
        // unwind table is not told, so a backtrace taken on one of those few instructions in a
        // function with no frame pointer is sixteen bytes off.
        let (into, saved) = match scratch.iter().copied().find(|&reg| free(reg)).or_else(loaded) {
            Some(reg) => (reg, false),
            None => match scratch.iter().copied().find(|&reg| !read(reg)) {
                Some(reg) => (reg, true),
                None => continue,
            },
        };
        let moved = if saved && from == conv.stack_pointer { offset(conv.push) } else { 0 };
        let disp = amode.disp + moved;
        let sign = disp.signum();
        let mut steps: Vec<i32> =
            insts.steps(disp.unsigned_abs()).into_iter().map(|step| offset(step) * sign).collect();
        let last = steps.last().copied().unwrap_or(0);
        let keep = if steps.len() > 1 && reaches(name, last) {
            steps.pop();
            last
        } else {
            0
        };
        let class = conv.int_class;
        if saved {
            let push = Opcode::new(names.intern(&format!("{}{}", insts.prefix, insts.push)));
            let pop = Opcode::new(names.intern(&format!("{}{}", insts.prefix, insts.pop)));
            let push = func.build_loose(push).uses(Reg::physical(into), class).finish();
            func.insert_before(inst, push);
            let pop = func.build_loose(pop).def(Reg::physical(into), class).finish();
            func.insert_after(inst, pop);
        }
        let mut base = from;
        for step in steps {
            let address = func
                .build_loose(lea)
                .def(Reg::physical(into), class)
                .mem(Mem::at(Operand::read(Reg::physical(base), class)).plus(step))
                .finish();
            func.insert_before(inst, address);
            base = into;
        }
        func[operands][usize::from(at)].reg = Reg::physical(into);
        func[mem].disp = keep;
    }
}

/// Whether something after that instruction in its block reads the register before anything
/// writes it again.
///
/// Only the block, because a scratch register is not live into another one. The cleanup follows
/// what one holds from a move to its reader and starts again at the top of every block.
fn live_after(func: &Func, inst: Inst, reg: PhysReg) -> bool {
    let Some(block) = func.block_of(inst) else { return true };
    for next in func.insts(block).skip_while(|&at| at != inst).skip(1) {
        let operands = func[next].operands;
        let holds = |def: bool| {
            func[operands].iter().any(|op| op.role.is_def() == def && op.reg.phys() == Some(reg))
        };
        if holds(false) {
            return true;
        }
        if holds(true) {
            return false;
        }
    }
    false
}

/// How many pages a probing prologue touches one after another before it writes a loop instead.
///
/// Three, which is what gcc unrolls to. The loop is four instructions however many pages it walks
/// and a page written out is two, so three is the last size at which the straight line is no
/// longer than the loop, and the straight line has no branch in it and needs no register.
const UNROLLED: u32 = 3;

/// One function having its frame written into it.
/// Points an address the lowering left counted from the stack pointer at another register.
///
/// 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 in the mode.
fn rebase(func: &mut Func, inst: Inst, to: PhysReg) {
    let mem = func[inst].mem.expect("an address");
    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(to);
}

struct Writer<'a> {
    func: &'a mut Func,
    conv: &'a CallRegs,
    insts: &'a FrameInsts,
    names: &'a mut Interner,
    /// Which register every offset into the frame is counted from, which is the stack pointer
    /// unless the function moves it while it runs. See `Growing` in [`crate::frame`].
    base: PhysReg,
    /// The blocks a probing prologue made, which go in front of the one the function began with.
    ///
    /// Empty in every function whose frame is taken in one subtraction, which is every function
    /// on a command line that did not ask for the stack to be touched a page at a time and most
    /// of them on one that did. See [`Writer::pages`].
    ahead: Option<[Block; 2]>,
}

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.
    ///
    /// Where the pointer is pointed at the frame is the one part of that order the platform gets a
    /// say in. Windows wants it after the frame has been taken rather than before, because the
    /// unwind record it reads has no way to describe the other order, so on that target the move
    /// goes between the frame and the vector stores instead. See `Late` in [`crate::frame`].
    ///
    /// The landing pad is in front of all of it, because the address it makes reachable is the
    /// address of the function and the address of the function is where the first instruction is.
    /// It has to be written here rather than after the fact, since a probing prologue moves the
    /// instructions written so far into a block of its own and the pad has to move with them.
    ///
    /// The room a patcher was promised goes after the pad, because a patcher wants somewhere it can
    /// write a call that happens before anything else, and the pad is the one instruction that has
    /// to come first for a reason of its own.
    ///
    /// A profiler's hook goes next, or at the end when it is the kind that reads the frame pointer.
    /// The early one is in front of everything the frame does for a reason of its own: what makes
    /// it worth replacing while the program runs is that the stack at that instruction is exactly
    /// what a call leaves, and a prologue that had already run would have changed it.
    fn prologue(
        &mut self,
        frame: &Frame,
        protect: Option<Protect<'_>>,
        probe: Option<Probing<'_>>,
        landing: Option<&'static str>,
        trace: Option<Tracing>,
        pad: Option<Padding>,
    ) -> 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 push = offset(self.conv.push);
        let mut out = Vec::new();
        // What the prologue wrote before it had described anything, which is what decides whether
        // there is a rule to remember at the end of it. Neither of these moves a register or takes
        // a frame, so a function whose whole prologue is one of them has no rows and must not be
        // given a pair of them that cancel out.
        let mut quiet = Vec::new();
        if let Some(name) = landing {
            let opcode = self.opcode(name);
            let inst = self.func.build_loose(opcode).finish();
            out.push(inst);
            quiet.push(inst);
        }
        // After the pad and in front of everything else, which is where gcc puts it. The pad is the
        // function's first instruction because the address an indirect branch may arrive at is the
        // address of the function, and the room comes next because what gets written over it is a
        // call and the point of that call is that it happens before the function has done anything.
        //
        // Nothing is described for any of it. A byte that does nothing does not move the stack
        // pointer, and what a patcher writes over it later is its own problem rather than this
        // function's: the rules here say what this function did, and it did nothing.
        if let Some(pad) = pad {
            let opcode = self.opcode(pad.name);
            let mut first = None;
            for _ in 0..pad.after {
                let inst = self.func.build_loose(opcode).finish();
                out.push(inst);
                quiet.push(inst);
                first.get_or_insert(inst);
            }
            self.func.patch = Some(Patch { before: pad.before, pad: opcode, after: first });
        }
        // Nothing is described for it and nothing needs to be: the call pushes a return address and
        // the hook pops it, so the frame is the same on both sides, and the hook preserves every
        // register because it is written in assembly for exactly this. That is also why the
        // allocator, which ran before any of this, never saw the call and did not have to.
        if let Some(trace) = trace.filter(|trace| trace.early) {
            let inst = self.hook(trace);
            out.push(inst);
            quiet.push(inst);
        }
        // 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_frame();
            out.push(inst);
            below += push;
            self.row(inst, CfiOp::DefCfaOffset(below));
            self.saved(inst, int, fp, -below);
            // The frame record, where the return address a call left in a register goes on with
            // the frame pointer and sits the word above it.
            if let Some(link) = self.record() {
                self.saved(inst, int, link, word - below);
            }
            // Straight away unless the platform wants it after the frame, where the same two
            // instructions go at the bottom of this function instead. See `Late` in
            // [`crate::frame`].
            if !frame.late() {
                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 regs in frame.pushed_int() {
            let inst = self.push_int(regs);
            out.push(inst);
            below += push;
            if from_sp {
                self.row(inst, CfiOp::DefCfaOffset(below));
            }
            // The first of a pair at the lower address and the second a word above it, which is
            // what the pair instruction does and where [`Self::push_frame`] puts its two as well.
            for (&reg, above) in regs.iter().zip([0, offset(self.conv.word)]) {
                self.saved(inst, int, reg, above - below);
            }
        }
        if let Some(to) = frame.realign().filter(|_| !frame.late()) {
            // 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 {
            self.take(&mut out, frame.size(), &mut below, from_sp, probe);
        }
        // The other half of the pair above, for the platform whose record counts everything from
        // where the stack pointer ends the prologue. Here it is that register the pointer is a copy
        // of, so what the row says is the whole distance rather than that nothing has changed, and
        // the frame is described before it rather than after, which is the whole of what the record
        // could not say about the early order.
        if frame.late() && frame.frame_pointer() {
            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::DefCfa { reg: number, offset: below });
        }
        for save in frame.saved_sse() {
            let inst = self.save_sse(save.reg, save.at);
            out.push(inst);
            // Where it went is an offset from whichever register the frame counts from, and the
            // address is a constant above that register, so the two make one constant. In an
            // ordinary frame that register is the stack pointer and the constant is `below`. In one
            // that grows it is the frame pointer, which the address has been counted from since the
            // prologue pointed it at where it saved the caller's copy, so the constant is the two
            // words above it and nothing the prologue did afterwards changes it. Unless the pointer
            // went up late, where it holds what the stack pointer holds and the constant is `below`
            // again, which is why the question is about both. A realigned frame has no such constant
            // at all and the rule is left out rather than guessed. On SysV that costs nothing, since
            // it preserves no vector register for a prologue to save. On Windows it would be a save
            // with no row, and what stops that reaching an object file is that a realigned frame
            // there takes the late order, where the saves happen before the alignment is forced
            // and `below` is still the constant. See `Late` in [`crate::frame`].
            if frame.realign().is_none() || frame.late() {
                let above = if frame.grows() && !frame.late() {
                    push + offset(self.conv.return_address)
                } else {
                    below
                };
                self.saved(inst, sse, save.reg, save.at - above);
            }
        }
        // The alignment a late frame forces, once everything the record describes is done. No row,
        // for the reason the early order has none, and none is needed: the address is counted from
        // the frame pointer by now. The body counts from the stack pointer this leaves.
        if let Some(to) = frame.realign().filter(|_| frame.late()) {
            let and = self.opcode(self.insts.align);
            out.push(self.arith(and, -i64::from(to)));
        }
        // Before the canary and after the frame, which is where gcc puts it. The hook reads the
        // frame pointer to find out who called this function, so it has to run once there is one,
        // and it is a call, so it has to run before anything the function is keeping in the frame
        // could be read back.
        if let Some(trace) = trace.filter(|trace| !trace.early) {
            let inst = self.hook(trace);
            out.push(inst);
        }
        // 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`.
        //
        // Nothing is kept in a function whose whole prologue is the pieces that describe nothing.
        // See `quiet` above.
        if let Some(&last) = out.last() {
            if !quiet.contains(&last) {
                self.row(last, CfiOp::RememberState);
            }
        }
        out
    }

    /// The call to a profiler's hook.
    ///
    /// No arguments and no result. Which function is being entered is not passed, because the hook
    /// reads its own return address to find out, and that is the whole reason the call is written
    /// rather than something cheaper.
    fn hook(&mut self, trace: Tracing) -> Inst {
        let call = self.opcode(self.insts.call);
        let symbol = self.names.intern(trace.name);
        self.func.build_loose(call).symbol(symbol).finish()
    }

    /// Takes the frame, which is one subtraction unless the command line asked for the stack to be
    /// touched a page at a time.
    ///
    /// `below` is how far the canonical frame address is above the stack pointer, and it comes
    /// back as what it is once the frame has been taken.
    fn take(
        &mut self,
        out: &mut Vec<Inst>,
        size: u32,
        below: &mut i32,
        from_sp: bool,
        probe: Option<Probing<'_>>,
    ) {
        // In front of everything else, because a platform with a routine for this has it for every
        // frame rather than for the ones a flag was passed about, and because the routine does the
        // whole of what the walk below would have done. See [`rucc_target::Chkstk`].
        let page = self.insts.probe.map_or(u32::MAX, |probe| probe.interval);
        if let Some(chkstk) = self.conv.chkstk.filter(|_| size > page) {
            let inst = self.reach(out, chkstk, size);
            *below += offset(size);
            if from_sp {
                self.row(inst, CfiOp::DefCfaOffset(*below));
            }
            return;
        }
        let Some(probing) = probe.filter(|probing| size > probing.probe.interval) else {
            for step in self.insts.steps(size) {
                let inst = self.sub(step);
                out.push(inst);
                *below += offset(step);
                if from_sp {
                    self.row(inst, CfiOp::DefCfaOffset(*below));
                }
            }
            return;
        };
        // Every step but the last is a whole page and is followed by a touch, and the last is
        // whatever is left over, which is between one byte and one whole page. So the stack
        // pointer never moves further than a page without something being written where it landed,
        // and the unmapped page an operating system leaves below a stack cannot be stepped over.
        //
        // That is why the count is worked out from one less than the size. A frame that is an
        // exact number of pages gets one fewer touch than it has pages, and the step left over is
        // a whole page, which is a step that lands on the next page boundary rather than past it.
        // gcc touches that last page as well, so this is one instruction shorter on a frame whose
        // size is a multiple of the page and the same everywhere else.
        let interval = probing.probe.interval;
        let pages = (size - 1) / interval;
        let rest = size - pages * interval;
        let mut walked = false;
        if pages <= UNROLLED {
            for _ in 0..pages {
                let inst = self.sub(interval);
                out.push(inst);
                *below += offset(interval);
                if from_sp {
                    self.row(inst, CfiOp::DefCfaOffset(*below));
                }
                let touch = self.touch(probing.probe);
                out.push(touch);
            }
        } else {
            self.pages(out, pages, below, from_sp, probing);
            walked = from_sp;
        }
        let inst = self.sub(rest);
        out.push(inst);
        *below += offset(rest);
        if from_sp {
            // A loop leaves the address counted from the register the stack pointer was compared
            // against, since that is the one thing in it that holds still. This is where it goes
            // back to being counted from the stack pointer, and it is written behind this
            // instruction rather than behind the branch because a row is written behind an
            // instruction and the branch is not one that survives [`crate::layout`].
            let op = if walked {
                let number = self.dwarf(self.conv.int_class, self.conv.stack_pointer);
                CfiOp::DefCfa { reg: number, offset: *below }
            } else {
                CfiOp::DefCfaOffset(*below)
            };
            self.row(inst, op);
        }
    }

    /// Reaches the pages of a frame by calling the routine this platform has for it, and then takes
    /// the frame.
    ///
    /// Three instructions, and the third is the one that moves anything:
    ///
    /// ```text
    ///   the size into a register    which register is the platform's answer rather than ours
    ///   the call                    touches every page from here down to that many bytes below
    ///   the subtraction             takes the frame, of the register the size is still in
    /// ```
    ///
    /// The routine comes back having moved nothing, which is what makes the third instruction
    /// necessary and is also what makes it a subtraction of a register rather than of the constant
    /// written again. Writing the constant twice would be the same number of bytes of code and one
    /// more place for the two to disagree.
    ///
    /// Nothing is described to the unwinder for the first two. The call pushes a return address and
    /// the routine pops it, so the frame is the same on both sides of it, which is the same argument
    /// the profiler's hook makes a few lines above. The row goes behind the subtraction, where the
    /// stack pointer has actually moved.
    ///
    /// No register here has to be asked about. The size goes in one the convention passes no
    /// argument in, which is what lets the platform name it at all, and the routine destroys two
    /// that are exactly the two the allocator was told to hold back. A prologue is also the one
    /// place in a function where the only live values are the ones that arrived in the convention's
    /// own registers.
    fn reach(&mut self, out: &mut Vec<Inst>, chkstk: Chkstk, size: u32) -> Inst {
        let class = self.conv.int_class;
        let sp = Reg::physical(self.conv.stack_pointer);
        let count = Reg::physical(chkstk.size);

        let imm = self.opcode(self.insts.imm);
        let inst = self.func.build_loose(imm).def(count, class).imm(i64::from(size)).finish();
        out.push(inst);
        let call = self.opcode(self.insts.call);
        let symbol = self.names.intern(chkstk.name);
        let inst = self.func.build_loose(call).symbol(symbol).finish();
        out.push(inst);
        let grow = self.opcode(self.insts.grow);
        let inst =
            self.func.build_loose(grow).def(sp, class).uses(sp, class).uses(count, class).finish();
        out.push(inst);
        inst
    }

    /// The loop that takes a frame too large for the touches to be written one after another.
    ///
    /// Three blocks, and the first two are new and go in front of the one the function began with:
    ///
    /// ```text
    ///   what the function is entered at   everything the prologue did before this, and then the
    ///                                     address the stack pointer is walking down to
    ///   the loop                          one page, the touch, and the question of whether the
    ///                                     stack pointer has got there yet
    ///   what the function began with      the rest of the prologue, and then the body
    /// ```
    ///
    /// The instructions the prologue has written so far move into the first of them, because a
    /// block is entered at the top and they have to run before the loop does. Nothing is laid out
    /// here: which block comes first in memory is [`crate::layout`]'s answer, and all this decides
    /// is which one the function is entered at.
    fn pages(
        &mut self,
        out: &mut Vec<Inst>,
        pages: u32,
        below: &mut i32,
        from_sp: bool,
        probing: Probing<'_>,
    ) {
        let class = self.conv.int_class;
        let sp = self.conv.stack_pointer;
        let all = offset(pages * probing.probe.interval);
        let [limit, byte] = probing.scratch;

        let head = self.func.create_block();
        for &inst in out.iter() {
            self.func.append_inst(head, inst);
        }
        out.clear();
        // Where the stack pointer is walking down to, worked out before it starts moving. A loop
        // that counted down instead would need somewhere to keep the count, and this is somewhere
        // to keep it that the comparison can read without arithmetic.
        let lea = self.opcode(self.insts.lea);
        let inst = self.address(lea, limit, sp, -all);
        self.func.append_inst(head, inst);
        if from_sp {
            // The address is counted from that register for as long as the loop runs, and it has
            // to be: the stack pointer moves once an iteration, so no fixed distance from it is
            // true twice, and this register was written so that one distance is.
            let number = self.dwarf(class, limit);
            self.row(inst, CfiOp::DefCfa { reg: number, offset: *below + all });
        }

        let body = self.func.create_block();
        *self.func.succs_mut(head) = vec![BlockCall::to(body)];
        let inst = self.sub(probing.probe.interval);
        self.func.append_inst(body, inst);
        let touch = self.touch(probing.probe);
        self.func.append_inst(body, touch);
        let differ = self.opcode(self.insts.differ);
        let inst = self
            .func
            .build_loose(differ)
            .def(Reg::physical(byte), class)
            .uses(Reg::physical(sp), class)
            .uses(Reg::physical(limit), class)
            .finish();
        self.func.append_inst(body, inst);
        let cond = Opcode::new(
            self.names.intern(&format!("{}{}", probing.branch.prefix, probing.branch.cond)),
        );
        let inst = self.func.build_loose(cond).uses(Reg::physical(byte), class).finish();
        self.func.append_inst(body, inst);
        // The first arm is the one taken when the condition held, and the condition is that the
        // stack pointer and the address it is walking down to still differ, so the first arm is
        // another page.
        let began = self.func.entry().expect("a function with a block in it");
        *self.func.succs_mut(body) = vec![BlockCall::to(body), BlockCall::to(began)];
        *below += all;
        self.ahead = Some([head, body]);
    }

    /// Walks the pages a variable length array takes, at the declaration that takes them.
    ///
    /// The prologue's own pages are counted when it is written, so it can step down to an address
    /// it worked out in advance and stop when it gets there. A declaration in the body cannot: how
    /// many bytes it asked for arrives in a register, so where it is going is arithmetic rather than
    /// a constant, and how many pages that is is a number nothing has. What is written instead is a
    /// loop that steps a page and asks whether it has arrived yet, which is the same walk with the
    /// count taken out of it.
    ///
    /// The one instruction the lowering wrote becomes four blocks:
    ///
    /// ```text
    ///   what the block was          everything it did before the declaration, and then where the
    ///                               stack pointer is going, worked out before it starts moving
    ///   the step                    one page, and whether the stack pointer is still above there
    ///   the page it stepped onto    the touch, and round again
    ///   the rest of the block       the stack pointer put where it was going, and then the body
    /// ```
    ///
    /// The touch is behind the question rather than in front of it, so the only page ever written
    /// is one the array reaches. The last step down is a whole page whatever is left, which puts the
    /// stack pointer at or past the end of the array, and the block that follows puts it back on the
    /// end. Nothing is touched there and nothing has to be: that is a move of less than a page from
    /// a page this loop has already been to, which is the whole of what a guard page asks.
    ///
    /// Nothing is described to the unwinder for any of it. A function with a variable length array
    /// in it keeps a frame pointer, because its own stack pointer is not a fixed distance from
    /// anything, and by here the frame is already counted from that register rather than from the
    /// stack pointer. So the rule that was true before the walk is still true after it.
    fn walk(&mut self, took: Inst, probing: Probing<'_>) {
        let class = self.conv.int_class;
        let sp = self.conv.stack_pointer;
        let span = self.func.span(took);
        let block = self.func.block_of(took).expect("an instruction the lowering put in a block");

        // Which register the bytes arrived in, and which two the walk may use. The bytes may be in
        // one of the two, because a reload the rewriter wrote is written into one of them, and a
        // value that arrived that way is read by the one instruction it was written in front of and
        // is dead after it. So the limit goes in whichever of the pair the bytes are not in, and the
        // other one is free from the moment the limit has been worked out.
        let operands = self.func[took].operands;
        let bytes = self.func[operands][2].reg.phys().expect("a register the allocator settled");
        let [first, second] = probing.scratch;
        let (limit, flag) = if bytes == first { (second, first) } else { (first, second) };

        let tail: Vec<Inst> = {
            let mut rest = self.func.insts(block).skip_while(|&inst| inst != took);
            rest.next();
            rest.collect()
        };
        let step = self.func.create_block();
        let onto = self.func.create_block();
        let done = self.func.create_block();

        let mov = self.opcode(self.insts.moves(class).expect("a class the target can move").mov);
        let inst = self.two(mov, sp, limit);
        self.func.append_inst(done, inst);
        for inst in tail {
            self.func.remove_inst(inst);
            self.func.append_inst(done, inst);
        }
        let succs = std::mem::take(self.func.succs_mut(block));
        *self.func.succs_mut(done) = succs;

        // The subtraction the lowering wrote is what the loop is instead of, so it goes. What is
        // left in the block it was in is where the stack pointer is walking down to.
        self.func.remove_inst(took);
        let inst = self.two(mov, limit, sp);
        self.func.append_inst(block, inst);
        let grow = self.opcode(self.insts.grow);
        let inst = self
            .func
            .build_loose(grow)
            .at(span)
            .def(Reg::physical(limit), class)
            .uses(Reg::physical(limit), class)
            .uses(Reg::physical(bytes), class)
            .finish();
        self.func.append_inst(block, inst);
        *self.func.succs_mut(block) = vec![BlockCall::to(step)];

        let inst = self.sub(probing.probe.interval);
        self.func.append_inst(step, inst);
        let above = self.opcode(self.insts.above);
        let inst = self
            .func
            .build_loose(above)
            .def(Reg::physical(flag), class)
            .uses(Reg::physical(sp), class)
            .uses(Reg::physical(limit), class)
            .finish();
        self.func.append_inst(step, inst);
        let cond = Opcode::new(
            self.names.intern(&format!("{}{}", probing.branch.prefix, probing.branch.cond)),
        );
        let inst = self.func.build_loose(cond).uses(Reg::physical(flag), class).finish();
        self.func.append_inst(step, inst);
        // The first arm is the one taken when the condition held, and the condition is that the
        // stack pointer is still above where the array ends, so the first arm is the page it has
        // just stepped onto being written and another time round.
        *self.func.succs_mut(step) = vec![BlockCall::to(onto), BlockCall::to(done)];

        let touch = self.touch(probing.probe);
        self.func.append_inst(onto, touch);
        *self.func.succs_mut(onto) = vec![BlockCall::to(step)];
    }

    /// Writes the page the stack pointer is on without changing what is there.
    fn touch(&mut self, probe: &Probe) -> Inst {
        let opcode = self.opcode(probe.inst);
        let base = Operand::read(Reg::physical(self.conv.stack_pointer), self.conv.int_class);
        self.func.build_loose(opcode).imm(0).mem(Mem::at(base)).finish()
    }

    /// Takes that many bytes off the stack pointer.
    fn sub(&mut self, bytes: u32) -> Inst {
        let sub = self.opcode(self.insts.sub);
        self.arith(sub, i64::from(bytes))
    }

    /// 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 push = self.conv.push;
        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(push) * self.pushes(frame)
            + offset(frame.size());
        let from_sp = !frame.frame_pointer();
        // A late frame that forced its alignment has the stack pointer somewhere below where the
        // prologue left it, and the frame pointer holds where that was. Putting it back first makes
        // the rest of this the epilogue of any other late frame.
        if frame.late() && frame.realign().is_some() {
            let mov = self.opcode(self.insts.moves(int).expect("a move").mov);
            out.push(self.two(mov, sp, fp));
        }
        for save in frame.saved_sse() {
            let inst = self.restore_sse(save.reg, save.at);
            out.push(inst);
            if frame.realign().is_none() || frame.late() {
                self.restored(inst, sse, save.reg);
            }
        }
        let pushed = u32::try_from(frame.pushed_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.
            //
            // Where the pointer is decides how far back this has to go. The early order left it one
            // push above the first push, so the pops start that many pushes below it. The late one
            // left it where the body's stack pointer was, so they start the whole frame above it,
            // and in both cases the distance is a constant even in a frame that grew while it ran,
            // which is why this is written rather than an addition to the stack pointer.
            let back = if frame.late() { offset(frame.size()) } else { -offset(push * pushed) };
            if back == 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);
                out.push(self.address(lea, sp, fp, back));
            }
        } else if frame.size() > 0 {
            let add = self.opcode(self.insts.add);
            for step in self.insts.steps(frame.size()) {
                let inst = self.arith(add, i64::from(step));
                out.push(inst);
                below -= offset(step);
                self.row(inst, CfiOp::DefCfaOffset(below));
            }
        }
        for regs in frame.pushed_int().rev() {
            let inst = self.pop_int(regs);
            out.push(inst);
            for &reg in regs {
                self.restored(inst, int, reg);
            }
            below -= offset(push);
            if from_sp {
                self.row(inst, CfiOp::DefCfaOffset(below));
            }
        }
        if frame.frame_pointer() {
            let inst = self.pop_frame();
            out.push(inst);
            self.restored(inst, int, fp);
            if let Some(link) = self.record() {
                self.restored(inst, int, link);
            }
            // 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);
        }
        // And where all of it came from, which is the closing brace. Nothing here has a span of its
        // own: an epilogue is the frame going back the way it came and no expression in the source
        // asked for any of it, so without this the bytes are covered by whatever the last statement
        // of the body was. That is the hole the prologue used to have, at the other end, and gcc
        // fills it the same way it fills the other one, with the brace. A function whose body this
        // does not know is left alone and keeps covering those bytes with the last row before them.
        let closing = ending(self.func.declared);
        if !closing.is_dummy() {
            for &inst in &out {
                self.func.set_span(inst, closing);
            }
        }
        out
    }

    /// How many pushes the prologue made, the frame pointer's included, which on a machine that
    /// pushes two at a time is fewer than the registers they saved.
    fn pushes(&self, frame: &Frame) -> i32 {
        let saved = i32::try_from(frame.pushed_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 Map<At, Inst>, at: At, inst: Inst) {
        if let Some(cursor) = cursors.get_mut(&at) {
            self.func.insert_after(*cursor, inst);
            *cursor = 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.insert(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.insts.moves(class).expect("a class to load").load;
        self.load_as(load, class, reg, at)
    }

    /// Reads a register out of the frame with that load.
    fn load_as(&mut self, load: &str, class: RegClass, reg: PhysReg, at: i32) -> Inst {
        let load = self.opcode(load);
        let base = Operand::read(Reg::physical(self.base), 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.insts.moves(class).expect("a class to store").store;
        self.store_as(store, class, reg, at)
    }

    /// The part of a vector register the prologue owes the caller, into the frame. The whole of it
    /// unless the convention keeps only part, and then that part and no more. See
    /// [`rucc_target::Kept`].
    fn save_sse(&mut self, reg: PhysReg, at: i32) -> Inst {
        let sse = self.conv.sse_class;
        match self.insts.kept.filter(|_| self.conv.sse_kept.is_some()) {
            Some(kept) => self.store_as(kept.store, sse, reg, at),
            None => self.store(sse, reg, at),
        }
    }

    /// What [`Self::save_sse`] wrote, back out of the frame.
    fn restore_sse(&mut self, reg: PhysReg, at: i32) -> Inst {
        let sse = self.conv.sse_class;
        match self.insts.kept.filter(|_| self.conv.sse_kept.is_some()) {
            Some(kept) => self.load_as(kept.load, sse, reg, at),
            None => self.load(sse, reg, at),
        }
    }

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

    /// Puts one general purpose register on the stack, or two with the pair instruction. See
    /// [`crate::frame::Layout::pairs`].
    fn push_int(&mut self, regs: &[PhysReg]) -> Inst {
        let &[first, second] = regs else { return self.push(regs[0]) };
        let pair = self.insts.pair.expect("a frame that pairs is on a machine that can");
        let push = self.opcode(pair.push);
        let class = self.conv.int_class;
        self.func
            .build_loose(push)
            .uses(Reg::physical(first), class)
            .uses(Reg::physical(second), class)
            .finish()
    }

    /// Takes back what [`Self::push_int`] put on the stack.
    fn pop_int(&mut self, regs: &[PhysReg]) -> Inst {
        let &[first, second] = regs else { return self.pop(regs[0]) };
        let pair = self.insts.pair.expect("a frame that pairs is on a machine that can");
        let pop = self.opcode(pair.pop);
        let class = self.conv.int_class;
        self.func
            .build_loose(pop)
            .def(Reg::physical(first), class)
            .def(Reg::physical(second), class)
            .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()
    }

    /// The register that goes on the stack with the frame pointer, which is the one a call leaves
    /// the return address in on a machine that pushes the two together, and nothing anywhere else.
    fn record(&self) -> Option<PhysReg> {
        self.conv.link.filter(|_| self.insts.pair.is_some())
    }

    /// Puts the caller's frame pointer on the stack, together with the return address on a machine
    /// that keeps it in a register. The frame pointer goes at the lower address, so the pointer set
    /// to it straight after names the caller's copy and the return address is the word above.
    fn push_frame(&mut self) -> Inst {
        let fp = self.conv.frame_pointer;
        let (Some(link), Some(pair)) = (self.record(), self.insts.pair) else {
            return self.push(fp);
        };
        let push = self.opcode(pair.push);
        let class = self.conv.int_class;
        self.func
            .build_loose(push)
            .uses(Reg::physical(fp), class)
            .uses(Reg::physical(link), class)
            .finish()
    }

    /// Takes back what [`Self::push_frame`] put on the stack.
    fn pop_frame(&mut self) -> Inst {
        let fp = self.conv.frame_pointer;
        let (Some(link), Some(pair)) = (self.record(), self.insts.pair) else {
            return self.pop(fp);
        };
        let pop = self.opcode(pair.pop);
        let class = self.conv.int_class;
        self.func
            .build_loose(pop)
            .def(Reg::physical(fp), class)
            .def(Reg::physical(link), 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")
}

/// The last character of a span, which for the span of a function body is its closing brace.
///
/// A span runs from the first byte to one past the last, so the brace is the byte before the end
/// rather than the end. [`Span::DUMMY`] for a function that came from no C source, which is what
/// the tests and the IR parser build, and for the empty span that cannot have a last character.
fn ending(body: Span) -> Span {
    if body.is_dummy() || body.hi <= body.lo {
        return Span::DUMMY;
    }
    Span::new(body.hi - 1, body.hi)
}

#[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, PROBE, R10, R11, RAX, REGS, SYSV, WIN64, XMM, xmm,
    };

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

    /// The closing brace of a body is the last character of its span and not the end of it, since a
    /// span runs to one past what it covers. A function that came from no source has no brace and
    /// asks for no row, which is what keeps the epilogue of one the IR parser built covered by the
    /// row before it rather than by a position in a file that is not there.
    #[test]
    fn the_end_of_a_body_is_its_closing_brace_and_not_one_past_it() {
        assert_eq!(ending(Span::new(10, 40)), Span::new(39, 40));
        assert_eq!(ending(Span::DUMMY), Span::DUMMY);
        assert_eq!(ending(Span::new(7, 7)), Span::DUMMY);
    }

    /// 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", true);
        (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 convention = Convention { protect, ..Convention::new(layout.conv, &FRAME) };
        under(func, allocation, layout, &Stack::default(), convention, names)
    }

    /// The same, for a function whose frame the caller has decided is taken a page at a time.
    fn with_probing(
        func: &mut Func,
        allocation: &Allocation,
        layout: &Layout<'_>,
        probe: Option<Probing<'_>>,
        names: &mut Interner,
    ) -> Vec<String> {
        let convention = Convention { probe, ..Convention::new(layout.conv, &FRAME) };
        under(func, allocation, layout, &Stack::default(), convention, names)
    }

    /// A function whose one block takes a run of bytes off the stack pointer, which is what the
    /// lowering writes for a variable length array, with the count already in the register given.
    fn growing(count: PhysReg) -> (Func, Allocation, Interner, Stack) {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let sp = Reg::physical(SYSV.stack_pointer);
        let grow = Opcode::new(names.intern("x64.sub_rr_64"));
        let took = func
            .build(block, grow)
            .def(sp, GPR)
            .uses(sp, GPR)
            .uses(Reg::physical(count), GPR)
            .finish();
        let nop = Opcode::new(names.intern("x64.nop"));
        func.build(block, nop).finish();
        let allocation = rucc_regalloc::run(&mut func, &env(&SYSV, 4), "test", true);
        (func, allocation, names, Stack { grown: vec![took], ..Stack::default() })
    }

    /// The function with its frame written into it under that convention.
    fn under(
        func: &mut Func,
        allocation: &Allocation,
        layout: &Layout<'_>,
        stack: &Stack,
        convention: Convention<'_>,
        names: &mut Interner,
    ) -> Vec<String> {
        let frame = Frame::of(func, allocation, layout);
        finish(func, allocation, &frame, stack, 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"]);
    }

    /// The bytes that give a frame back are filed under the closing brace, which is where a
    /// debugger says a function ends and which nothing in an epilogue could say for itself.
    #[test]
    fn an_epilogue_is_filed_under_the_closing_brace_of_the_body() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 4, 2);
        func.declared = Span::new(100, 140);
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { red_zone: false, ..base };
        written(&mut func, &allocation, &layout, &mut names);

        // Everything from the first instruction of the epilogue to the return, and nothing above
        // it: the body's own instructions keep the spans they arrived with, which here is none.
        let ends: Vec<Span> = func
            .blocks()
            .flat_map(|block| func.insts(block).collect::<Vec<_>>())
            .map(|inst| func.span(inst))
            .filter(|span| !span.is_dummy())
            .collect();
        assert!(!ends.is_empty(), "an epilogue was written");
        assert!(ends.iter().all(|&span| span == Span::new(139, 140)), "{ends:?}");
    }

    #[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", true);
        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_frame_that_fits_in_one_page_is_taken_in_one_subtraction_even_when_pages_are_touched() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 2, 4);
        let locals = [Local { size: 4088, align: 16 }];
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { leaf: false, locals: &locals, ..base };
        let probing = Probing { probe: &PROBE, branch: &BRANCH, scratch: [R10, R11] };
        let lines = with_probing(&mut func, &allocation, &layout, Some(probing), &mut names);

        // A frame of one page cannot step over the page below it, because the far end of it is the
        // near end of that page and anything written there is written to a page that is there. So
        // the flag costs such a function nothing, which is most functions.
        assert_eq!(
            added(&lines),
            ["$rsp = x64.sub_ri_64 $rsp, 4088", "$rsp = x64.add_ri_64 $rsp, 4088", "x64.ret",]
        );
    }

    #[test]
    fn a_probing_prologue_touches_every_page_of_a_frame_a_few_pages_deep() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 2, 4);
        let locals = [Local { size: 9000, align: 16 }];
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { leaf: false, locals: &locals, ..base };
        let probing = Probing { probe: &PROBE, branch: &BRANCH, scratch: [R10, R11] };
        let lines = with_probing(&mut func, &allocation, &layout, Some(probing), &mut names);

        // A page of the stack pointer's own, then the touch that says the page is there, and only
        // then the next one, which is the whole of the defence: nothing here ever moves the stack
        // pointer further than one page without writing where it landed. The last subtraction is
        // the remainder and is smaller than a page, so it needs no touch of its own, and it exists
        // in every frame because the count of pages is taken off one less than the size.
        assert_eq!(
            added(&lines),
            [
                "$rsp = x64.sub_ri_64 $rsp, 4096",
                "x64.or_mi_8 [$rsp], 0",
                "$rsp = x64.sub_ri_64 $rsp, 4096",
                "x64.or_mi_8 [$rsp], 0",
                "$rsp = x64.sub_ri_64 $rsp, 808",
                "$rsp = x64.add_ri_64 $rsp, 9000",
                "x64.ret",
            ]
        );
    }

    #[test]
    fn a_variable_length_array_walks_its_pages_where_the_declaration_stands() {
        let (mut func, allocation, mut names, stack) = growing(RAX);
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { leaf: false, grows: true, ..base };
        let probing = Probing { probe: &PROBE, branch: &BRANCH, scratch: [R10, R11] };
        let convention = Convention { probe: Some(probing), ..Convention::new(&SYSV, &FRAME) };
        let lines = under(&mut func, &allocation, &layout, &stack, convention, &mut names);

        // The whole listing, because what the walk is cannot be read off the instructions alone.
        // The one subtraction the lowering wrote is gone and four blocks stand where its block was:
        // where the stack pointer is going, the step, the page the step landed on, and the rest of
        // what the block was doing with the stack pointer put back where it was going.
        assert_eq!(
            lines,
            [
                "mfunc @f {",
                "block0:",
                "x64.push_64 $rbp",
                "$rbp = x64.mov_rr_64 $rsp",
                "$r10 = x64.mov_rr_64 $rsp",
                "$r10 = x64.sub_rr_64 $r10, $rax, block1",
                "block1:",
                "$rsp = x64.sub_ri_64 $rsp, 4096",
                "$r11 = x64.cmp_set_a_64 $rsp, $r10",
                "x64.br_cond_8 $r11, block2, block3",
                "block2:",
                "x64.or_mi_8 [$rsp], 0, block1",
                "block3:",
                "$rsp = x64.mov_rr_64 $r10",
                "x64.nop",
                "$rsp = x64.mov_rr_64 $rbp",
                "$rbp = x64.pop_64",
                "x64.ret",
                "}",
            ]
        );
    }

    #[test]
    fn the_walk_keeps_the_register_the_count_arrived_in() {
        let (mut func, allocation, mut names, stack) = growing(R10);
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { leaf: false, grows: true, ..base };
        let probing = Probing { probe: &PROBE, branch: &BRANCH, scratch: [R10, R11] };
        let convention = Convention { probe: Some(probing), ..Convention::new(&SYSV, &FRAME) };
        let lines = under(&mut func, &allocation, &layout, &stack, convention, &mut names);

        // The count is in the first of the two registers the walk was given, which is where a
        // reload the rewriter wrote would have put it, so the limit goes in the other one and the
        // comparison writes the first one back only once the count has been read for the last time.
        let added = added(&lines);
        assert!(added.contains(&"$r11 = x64.mov_rr_64 $rsp"), "{added:?}");
        assert!(added.contains(&"$r11 = x64.sub_rr_64 $r11, $r10, block1"), "{added:?}");
        assert!(added.contains(&"$r10 = x64.cmp_set_a_64 $rsp, $r11"), "{added:?}");
    }

    #[test]
    fn a_variable_length_array_takes_its_bytes_in_one_subtraction_when_nothing_asked() {
        let (mut func, allocation, mut names, stack) = growing(RAX);
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { leaf: false, grows: true, ..base };
        let convention = Convention::new(&SYSV, &FRAME);
        let lines = under(&mut func, &allocation, &layout, &stack, convention, &mut names);

        // The instruction the lowering wrote, where it wrote it, and one block still.
        assert!(lines.contains(&"$rsp = x64.sub_rr_64 $rsp, $rax".to_owned()), "{lines:?}");
        assert_eq!(lines.iter().filter(|line| line.starts_with("block")).count(), 1, "{lines:?}");
    }

    #[test]
    fn a_probing_prologue_deeper_than_that_walks_the_pages_in_a_loop() {
        let (mut func, allocation, mut names) = pressure(&SYSV, 2, 4);
        let locals = [Local { size: 100_000, align: 16 }];
        let base = Layout::new(&SYSV, REGS);
        let layout = Layout { leaf: false, locals: &locals, ..base };
        let probing = Probing { probe: &PROBE, branch: &BRANCH, scratch: [R10, R11] };
        let lines = with_probing(&mut func, &allocation, &layout, Some(probing), &mut names);

        // Twenty-four pages, which is more than a straight line is worth, so the prologue works out
        // where it is going first and then walks there. The whole listing rather than the added
        // lines, because what matters as much as the instructions is that the two blocks the walk
        // is made of come in front of the block the function began with: the body the allocator
        // filled is block2 here and it was block0 before this ran.
        assert_eq!(
            lines,
            [
                "mfunc @f {",
                "block0:",
                "$r10 = x64.lea_64 [$rsp - 98304], block1",
                "block1:",
                "$rsp = x64.sub_ri_64 $rsp, 4096",
                "x64.or_mi_8 [$rsp], 0",
                "$r11 = x64.cmp_set_ne_64 $rsp, $r10",
                "x64.br_cond_8 $r11, block1, block2",
                "block2:",
                "$rsp = x64.sub_ri_64 $rsp, 1704",
                "$rax = x64.nop",
                "$rcx = x64.nop",
                "x64.nop $rax",
                "x64.nop $rcx",
                "$rsp = x64.add_ri_64 $rsp, 100008",
                "x64.ret",
                "}",
            ]
        );
    }

    #[test]
    fn a_large_frame_on_a_platform_with_a_routine_for_its_pages_calls_the_routine() {
        let (mut func, allocation, mut names) = pressure(&WIN64, 2, 4);
        let locals = [Local { size: 100_000, align: 16 }];
        let base = Layout::new(&WIN64, REGS);
        let layout = Layout { leaf: false, locals: &locals, ..base };
        let lines = written(&mut func, &allocation, &layout, &mut names);

        // Nothing asked for this on the command line, which is the point: Windows commits a stack
        // by having the pages touched in order, so a frame this size has to reach them whatever the
        // flags said. The size goes in the register the platform names, the routine touches every
        // page down to there, and the frame is taken afterwards, because the routine comes back
        // having moved nothing. What the epilogue gives back is what the register was given, which
        // is the one thing worth tying together here.
        let added = added(&lines);
        assert_eq!(added.len(), 5, "{added:?}");
        let size = added[0].strip_prefix("$rax = x64.mov_ri_64 ").expect("a size in a register");
        assert_eq!(added[1], "x64.call @__chkstk");
        assert_eq!(added[2], "$rsp = x64.sub_rr_64 $rsp, $rax");
        assert_eq!(added[3], format!("$rsp = x64.add_ri_64 $rsp, {size}"));
        assert_eq!(added[4], "x64.ret");
    }

    #[test]
    fn a_frame_of_one_page_calls_nothing_on_that_platform_either() {
        let (mut func, allocation, mut names) = pressure(&WIN64, 2, 4);
        let locals = [Local { size: 4000, align: 16 }];
        let base = Layout::new(&WIN64, REGS);
        let layout = Layout { leaf: false, locals: &locals, ..base };
        let lines = written(&mut func, &allocation, &layout, &mut names);

        // The same reason a frame of one page is taken in one subtraction under the flag. The far
        // end of such a frame is inside the page below the stack pointer, and touching that page is
        // what the function does on its way to using the frame at all, so there is nothing for a
        // routine to do and a call to it would be a call in every function that declares an array.
        let added = added(&lines);
        assert!(added.iter().all(|line| !line.contains("chkstk")), "{added:?}");
        assert_eq!(added.len(), 3, "{added:?}");
    }

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

        // The other order, which is what every other platform here writes, has no unwind record on
        // this one: the record counts its slots from where the stack pointer ends the prologue and
        // gets there by taking a constant off the frame pointer, so a register pushed after the
        // pointer was established sits below the place the record counts from. Pushing first and
        // pointing last is the order that has a record, and it leaves the pointer holding a copy of
        // the stack pointer, so the spills stay where they were and the epilogue counts the frame
        // back off the pointer rather than moving the pointer into the stack pointer.
        assert_eq!(
            added(&lines),
            [
                "x64.push_64 $rbp",
                "$rsp = x64.sub_ri_64 $rsp, 16",
                "$rbp = x64.mov_rr_64 $rsp",
                "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.lea_64 [$rbp + 16]",
                "$rbp = x64.pop_64",
                "x64.ret",
            ]
        );
    }

    #[test]
    fn a_windows_prologue_that_saves_registers_too_pushes_all_of_them_before_the_frame() {
        let (mut func, allocation, mut names) = pressure(&WIN64, 9, 8);
        let base = Layout::new(&WIN64, REGS);
        let layout = Layout { leaf: false, frame_pointer: true, ..base };
        let lines = written(&mut func, &allocation, &layout, &mut names);

        // The shape that made the order necessary. All three pushes are above the frame, so every
        // one of them has a row the record can write, and the pointer is the last thing the
        // prologue does. Forty eight bytes is the thirty two every Windows caller reserves below a
        // call, eight for the one value that did not fit in a register, and eight that put the
        // stack pointer back where a call wants it given three pushes and the return address.
        assert_eq!(
            added(&lines),
            [
                "x64.push_64 $rbp",
                "x64.push_64 $rbx",
                "x64.push_64 $rsi",
                "$rsp = x64.sub_ri_64 $rsp, 48",
                "$rbp = x64.mov_rr_64 $rsp",
                "x64.mov_mr_64 $rsi, [$rsp + 32]",
                "$rsi = x64.mov_rm_64 [$rsp + 32]",
                "$rsp = x64.lea_64 [$rbp + 48]",
                "$rsi = x64.pop_64",
                "$rbx = x64.pop_64",
                "$rbp = x64.pop_64",
                "x64.ret",
            ]
        );
    }

    #[test]
    fn a_realigned_windows_frame_forces_the_alignment_after_the_prologue() {
        let (mut func, allocation, mut names) = pressure(&WIN64, 9, 8);
        let locals = [Local { size: 64, align: 32 }];
        let base = Layout::new(&WIN64, REGS);
        let layout = Layout { leaf: false, locals: &locals, ..base };
        let lines = written(&mut func, &allocation, &layout, &mut names);

        // The late order the record can describe, and the rounding after all of it, which is
        // clang's shape for the same frame. The epilogue puts the stack pointer back from the frame
        // pointer before it does anything else, and from there it is any other late epilogue.
        assert_eq!(
            added(&lines),
            [
                "x64.push_64 $rbp",
                "x64.push_64 $rbx",
                "x64.push_64 $rsi",
                "$rsp = x64.sub_ri_64 $rsp, 112",
                "$rbp = x64.mov_rr_64 $rsp",
                "$rsp = x64.and_ri_64 $rsp, -32",
                "x64.mov_mr_64 $rsi, [$rsp + 96]",
                "$rsi = x64.mov_rm_64 [$rsp + 96]",
                "$rsp = x64.mov_rr_64 $rbp",
                "$rsp = x64.lea_64 [$rbp + 112]",
                "$rsi = x64.pop_64",
                "$rbx = x64.pop_64",
                "$rbp = x64.pop_64",
                "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", true);
        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",
            ]
        );
    }

    /// A reload from deep in the frame takes the scratch register it loads into for the address,
    /// and not the other one, which the store after it reads. This is the pair the cleanup leaves
    /// when it keeps a value in `x16`, and taking `x16` stored the frame address in its place.
    #[test]
    fn a_far_access_leaves_alone_the_scratch_register_read_after_it() {
        use rucc_target::aarch64::{self, AAPCS64, X16, X17};
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let gpr = aarch64::GPR;
        let sp = Mem::at(Operand::read(Reg::physical(AAPCS64.stack_pointer), gpr)).plus(40_000);
        let load = Opcode::new(names.intern("a64.ldr_64"));
        let store = Opcode::new(names.intern("a64.str_64"));
        let reload = func.build(block, load).def(Reg::physical(X17), gpr).mem(sp).finish();
        let into = Mem::at(Operand::read(Reg::physical(X17), gpr));
        func.build(block, store).uses(Reg::physical(X16), gpr).mem(into).finish();

        far(&mut func, &aarch64::FRAME, &AAPCS64, &[X16, X17], &mut names);
        let insts: Vec<Inst> = func.insts(block).collect();
        assert!(insts.len() > 2, "the offset is out of reach and wants an address");
        for &inst in &insts[..insts.iter().position(|&at| at == reload).expect("still there")] {
            let written = func[func[inst].operands].iter().filter(|op| op.role.is_def());
            assert!(written.map(|op| op.reg.phys()).all(|reg| reg == Some(X17)));
        }
    }

    /// A store of one scratch register deep in the frame while the other is still wanted after it
    /// has neither to build the address in, so the other goes on the stack for the length of the
    /// store, and the offset grows by the sixteen bytes the push moved the stack pointer.
    #[test]
    fn a_far_store_with_no_free_scratch_register_saves_one_around_itself() {
        use rucc_target::aarch64::{self, AAPCS64, X16, X17};
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let gpr = aarch64::GPR;
        let sp = Mem::at(Operand::read(Reg::physical(AAPCS64.stack_pointer), gpr)).plus(40_000);
        let store = Opcode::new(names.intern("a64.str_64"));
        let spill = func.build(block, store).uses(Reg::physical(X16), gpr).mem(sp).finish();
        let into = Mem::at(Operand::read(Reg::physical(AAPCS64.stack_pointer), gpr));
        func.build(block, store).uses(Reg::physical(X17), gpr).mem(into).finish();

        far(&mut func, &aarch64::FRAME, &AAPCS64, &[X16, X17], &mut names);
        let text = print_func(&func, &names, &aarch64::REGS);
        let lines: Vec<&str> =
            text.lines().map(str::trim).filter(|line| line.contains("a64.")).collect();
        assert!(lines[0].starts_with("a64.push_64 $x17"), "{text}");
        assert!(lines.last().unwrap().starts_with("a64.str_64 $x17"), "{text}");
        assert!(lines[lines.len() - 2].contains("a64.pop_64"), "{text}");
        let spilled = func.insts(block).position(|at| at == spill).expect("still there");
        let base = func[func[spill].mem.expect("an address")].base.expect("a base");
        assert_eq!(func[func[spill].operands][usize::from(base)].reg, Reg::physical(X17), "{text}");
        let whole: i32 = func
            .insts(block)
            .take(spilled)
            .filter_map(|at| func[at].mem.map(|mem| func[mem].disp))
            .sum::<i32>()
            + func[func[spill].mem.expect("an address")].disp;
        assert_eq!(whole, 40_016, "{text}");
    }
}