rucc_regalloc/

rewrite.rs

//! Making an assignment true in the function it was worked out for.
//!
//! Design: `spec/10-backend.md` section 10.4.
//!
//! [`crate::assign`] says where every value goes and touches nothing. This is the other half: every
//! operand is rewritten to the place its value was given, and the moves that the places do not
//! already say are collected. After it the function names no virtual register and no block asks
//! for anything, which is the point at which machine IR stops being in SSA form and starts being
//! something an encoder could read.
//!
//! # Why the moves are handed back rather than written
//!
//! A move is an instruction, and an instruction has an opcode, and an opcode belongs to a target.
//! `spec/10-backend.md` section 10.8 says no pipeline crate holds target specific code, so this
//! crate is not the one that can write `x64.mov`. What it hands back is an [`Edit`]: a move
//! between two places, the class it is in, and where in the function it goes. `rucc-codegen` turns
//! each one into whatever its target moves a register with, which for a value on the stack is a
//! load or a store rather than a move at all.
//!
//! The edits at any one place are in the order they have to be made in. That matters in two
//! places: a spilled operand is read into a scratch register before the instruction that wants it,
//! and a two address instruction's copy has to come after that read, because what it is copying
//! may be the thing that was just read in.
//!
//! # How many scratch registers one instruction wants
//!
//! Two of a class, and a target holds two of each back for exactly this. The instruction that asks
//! for most reads two values and writes a third with nothing of the three in a register, and the
//! arithmetic works out because the two reads are what use the two scratch registers and the answer
//! is written back into one of them. Writing over it destroys nothing, since it holds a copy of a
//! value whose home is a stack slot and the instruction has already read it, and the answer is
//! stored away from it afterwards. Giving the answer a scratch register of its own would want a
//! third, which a program with enough live values around a call reaches, and that was issue #350.
//!
//! Which register the answer goes back into depends on what wrote it. A two address instruction
//! writes the register the operand it reuses was read into, because that is what two address means.
//! A three address one, which is `lea` and the compare and set pairs, writes a register that is
//! none of its operands, and there the answer takes the first scratch register of the class again:
//! the reads are done by the time the write happens, so the two uses of that register do not meet.
//! Counting the two jobs in one running number is what made a three address instruction with every
//! end on the stack ask for a third register and abort, which was issue #726.
//!
//! It is only a scratch register the answer may have either way. Where the operand a two address
//! instruction reuses is in a register the assignment gave out, the value in it may be wanted after
//! the instruction, and the assignment only lets one be written over when it is not, which it says
//! by giving the answer that register in the first place. So the answer takes a scratch register
//! there and the two address copy fills it. That one is filled in front of the instruction rather
//! than by it, so it cannot share with a read, and the count still comes to two, because an operand
//! that is in a register is not holding a scratch register.
//!
//! Deciding either way needs to know where the operand it reuses went, so an operand that reuses
//! another and has no register of its own is placed in a second pass over the operands.
//!
//! The count is per class. An instruction reading a spilled value out of each of two files wants
//! the first register of each, since a class holds its own back and nothing on the instruction is
//! in the other's.
//!
//! # What happens when two is not enough after all
//!
//! Two runs out on an instruction that reads three registers and writes none, because then there is
//! no answer to fold back into a register an operand arrived in and the arithmetic above has nothing
//! to work on. The instruction that does this on x86-64 is the indexed store, whose base, index and
//! value are three registers it only reads, and at `-O0` all three of them can be stack slots. That
//! is tamnd/rucc#913, and it stopped brotli and cmocka on the first file that held one.
//!
//! What answers it is borrowing: a register of the class the instruction has not named is
//! taken, whatever is in it is put in a slot of the frame in front of the instruction, and it is
//! brought back behind it. That asks nothing at all of the register, so it does not matter whether
//! the value in it is wanted afterwards, whether the callee owes it back, or whether an argument
//! travels in it, which are the three things that make a register held back hard to find. A third
//! register held back would cost every function in the program one, and on x86-64 the only one
//! available is `rax`, which is the return value, so the bill would be a move at every return. This
//! costs two memory accesses at the one instruction that wanted it and a slot most functions never
//! take.
//!
//! # What a fixed register turns into
//!
//! A move each way. The assignment deliberately gave the value some other register, so a division
//! whose dividend has to be in `rax` gets a move into `rax` in front of it and a move out of `rax`
//! behind it. That is the cost of the rule the assignment follows, and it is the rule that keeps
//! the `-O0` allocator one pass.
//!
//! # What an edge turns into
//!
//! The moves that write the block's parameters, in an order they can be made in one at a time,
//! which is what [`crate::moves`] is for. Where they go depends on the shape of the edge. A block
//! with one successor puts them at its own end, in front of the branch it finishes with, and a
//! block with several puts them at the start of the block the edge goes to, which is safe exactly
//! because that block has no other predecessor. An edge that is critical has neither place to put
//! them and has to have been split before allocation ran, which this checks rather than assumes.
//!
//! An edge is also the one place a value can be asked to go from one stack slot to another, which
//! happens when a spilled value is passed to a parameter that was itself spilled. No machine here
//! has that instruction, so the move goes through a register, and the register is a second scratch
//! rather than the one the ordering may be holding a value in for the length of a cycle. Expanding
//! it here rather than leaving it to the target is the same decision as everything else in this
//! file: a move through a temporary is a fact about places, and which register is free to be the
//! temporary is a fact only this crate has.

use rucc_mir::{Block, Constraint, Func, Inst, Operand, Param, Reg, Role};
use rucc_target::{PhysReg, RegClass};

use crate::assign::{Assignment, Env, Place};
use crate::moves::{self, Move};

/// One move the places did not already make true.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Edit {
    /// Where in the function it goes.
    pub at: At,
    /// What it moves, and where to.
    pub mov: Move<Place>,
    /// The class both places are in, which is what says how wide the move is.
    pub class: RegClass,
}

/// Where an edit goes.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum At {
    /// In front of an instruction, which is where a value it reads is put where it wants it.
    Before(Inst),
    /// Behind an instruction, which is where a value it wrote somewhere it insisted on is taken
    /// away to where it lives.
    After(Inst),
    /// At the start of a block, in front of everything in it.
    StartOf(Block),
    /// At the end of a block, behind everything in it. Only ever a block with one edge out of
    /// it, since a block with two puts an edge's moves at the start of the block it goes to.
    EndOf(Block),
}

/// Rewrites a function to the places it was given, and says what moves are still wanted.
///
/// # Panics
///
/// Panics if the entry block has parameters, since there is no edge into it for their moves to go
/// on and what arrives in a function is the ABI lowering's to say. Panics on a critical edge, on
/// an edge carrying the wrong number of arguments, and if a class has fewer than two registers on
/// an edge that moves a spilled value into a spilled parameter, all of which are the caller handing
/// it something it was told not to.
///
/// The assignment is taken by reference and may gain a slot, which is the one the register borrowed
/// at an instruction with more spilled operands than the class holds registers back for waits in.
/// The section above says what the borrowing is, and the slot is asked for here rather than planned
/// before allocation because most functions never want one.
#[must_use]
pub fn rewrite(func: &mut Func, assignment: &mut Assignment, env: &Env) -> Vec<Edit> {
    let blocks: Vec<Block> = func.blocks().collect();
    assert!(
        func.entry().is_none_or(|entry| func[entry].params.is_empty()),
        "what arrives in a function is not a block parameter"
    );

    let mut edits = Vec::new();
    let mut spare = Spare::default();
    for &block in &blocks {
        let insts: Vec<Inst> = func.insts(block).collect();
        for inst in insts {
            instruction(func, assignment, env, &mut spare, inst, &mut edits);
        }
    }

    let preds = preds(func, &blocks);
    for &block in &blocks {
        edges(func, assignment, env, block, &preds, &mut edits);
    }
    for &block in &blocks {
        func.params_mut(block).clear();
        for call in func.succs_mut(block) {
            call.args.clear();
        }
    }
    edits
}

/// Rewrites one instruction's operands, and says what has to happen either side of it.
fn instruction(
    func: &mut Func,
    assignment: &mut Assignment,
    env: &Env,
    spare: &mut Spare,
    inst: Inst,
    edits: &mut Vec<Edit>,
) {
    let list = func[inst].operands;
    let mut operands: Vec<Operand> = func[list].to_vec();
    let mut before = Moves::new();
    let mut after = Moves::new();
    let mut taken = Taken::new();

    // Where the assignment put each operand's value, taken before anything is rewritten, since
    // rewriting an operand is what loses that. The second pass below reads it.
    let places: Vec<Place> =
        operands.iter().map(|operand| place(assignment, operand.reg)).collect();

    // A spilled operand that reuses another is left for the second pass, because where it goes
    // depends on where the operand it reuses went and that is not known until every operand ahead
    // of it has been placed.
    let mut reusing: Vec<usize> = Vec::new();

    // Every register the instruction has named for itself, which is one an operand's value is
    // already in and one a fixed constraint asked for. Taken before anything is rewritten, for the
    // same reason the places above are: rewriting is what turns an operand's register into a
    // physical one and loses which of the two it was.
    let mut claimed = Claimed::default();
    for (operand, place) in operands.iter().zip(&places) {
        if let Place::Reg(at) = *place {
            claimed.named(operand, at);
        }
        if let Constraint::Fixed(at) = operand.constraint {
            claimed.named(operand, at);
        }
    }
    let mut scratch = Scratch::new(env, assignment, spare, claimed);

    for (index, operand) in operands.iter_mut().enumerate() {
        let fixed = match operand.constraint {
            Constraint::Fixed(at) => Some(at),
            _ => None,
        };
        let at = match (place(scratch.assignment, operand.reg), fixed) {
            (Place::Reg(at), None) => at,
            (Place::Reg(at), Some(fixed)) => {
                if at != fixed {
                    let (there, here) = (Place::Reg(fixed), Place::Reg(at));
                    push(&mut before, &mut after, operand, Move::new(there, here));
                }
                fixed
            }
            (Place::Slot(_), None) if matches!(operand.constraint, Constraint::Reuse(_)) => {
                reusing.push(index);
                continue;
            }
            (Place::Slot(slot), fixed) => {
                // Which of the two jobs this register is for. An operand the instruction only
                // writes wants one from the instruction onwards, and an operand it reads wants one
                // from before the instruction until it reads it, so the same register does both
                // and the two are counted apart.
                let at = match fixed {
                    Some(fixed) => fixed,
                    None if operand.role.is_def() => {
                        taken.written_into(operand.class, &mut scratch)
                    }
                    None => taken.read_into(operand.class, &mut scratch),
                };
                push(
                    &mut before,
                    &mut after,
                    operand,
                    Move::new(Place::Reg(at), Place::Slot(slot)),
                );
                at
            }
        };
        operand.reg = Reg::physical(at);
    }

    for index in reusing {
        let Constraint::Reuse(other) = operands[index].constraint else {
            unreachable!("only an operand that reuses another was left for this pass")
        };
        let Place::Slot(slot) = places[index] else {
            unreachable!("only a spilled operand was left for this pass")
        };
        // Where the operand it reuses was read into, if it was read into anywhere. A scratch
        // register holds a copy of a value that lives on the stack, so writing over it destroys
        // nothing and the instruction can have it. A register the assignment gave out is a
        // different matter: the value in it may be wanted after the instruction, and the
        // assignment only lets one be written over when it is not, which it says by giving the
        // answer that register. So a fresh scratch register there, and the copy below fills it.
        //
        // Either way this shape wants two of the class and no more. If the operand it reuses is on
        // the stack then it is holding one of them already, and if it is not then it is not
        // holding one at all.
        //
        // This one is asked for as a read even though the instruction writes it, because the copy
        // that fills it goes in front of the instruction. It is live from there, which is the same
        // span a value read in off the stack is live for, so it cannot share with one.
        let other = usize::from(other);
        let at = match places[other] {
            Place::Slot(_) => phys(operands[other].reg),
            Place::Reg(_) => taken.read_into(operands[index].class, &mut scratch),
        };
        push(
            &mut before,
            &mut after,
            &operands[index],
            Move::new(Place::Reg(at), Place::Slot(slot)),
        );
        operands[index].reg = Reg::physical(at);
    }

    // A two address instruction writes one of the registers it reads, and the copy that makes that
    // true goes after everything else in front of the instruction, since what it reads may be a
    // value that was itself only just read in from the stack.
    for index in 0..operands.len() {
        let Constraint::Reuse(other) = operands[index].constraint else { continue };
        let (to, from) = (operands[index], operands[usize::from(other)]);
        if to.reg != from.reg {
            let mov = Move::new(Place::Reg(phys(to.reg)), Place::Reg(phys(from.reg)));
            before.push((mov, to.class));
        }
    }

    // A borrowed register is put away in front of everything else and brought back behind
    // everything else, since what happens in between is the instruction using it and the moves
    // that carry its operands in and out. Nothing borrowed at one instruction is still borrowed at
    // the next, which is what lets the slot be shared.
    let (saves, restores) = scratch.finish();

    func[list].copy_from_slice(&operands);
    edits.extend(saves.into_iter().map(|(mov, class)| Edit { at: At::Before(inst), mov, class }));
    edits.extend(before.into_iter().map(|(mov, class)| Edit { at: At::Before(inst), mov, class }));
    edits.extend(after.into_iter().map(|(mov, class)| Edit { at: At::After(inst), mov, class }));
    edits.extend(restores.into_iter().map(|(mov, class)| Edit { at: At::After(inst), mov, class }));
}

/// How many scratch registers of each class one instruction has been handed, in each of the two
/// jobs they do.
///
/// Counted per class rather than in one running number, because the classes hold their own back
/// and an instruction reading a spilled value out of each of two files would otherwise skip the
/// first register of the second file for no reason.
///
/// Counted per job as well, and that is the part that keeps the count down. A register a spilled
/// value is read into is live from in front of the instruction until the instruction reads it. A
/// register the instruction writes its answer into is live from the instruction until the store
/// behind it. Those two spans do not meet, so one register does both jobs and the counting starts
/// again rather than carrying on. What that rests on is the machine reading its operands before it
/// writes its answer, which is true of every instruction the backends here emit and is the same
/// thing that makes `addq %rax, %rax` mean what it looks like.
///
/// Where the count runs out is an instruction that reads three registers and writes none, because
/// then there is no answer to fold back into a register an operand arrived in and the trick above
/// has nothing to work on. On x86-64 that instruction is the indexed store, whose base, index and
/// value are three registers it only reads, and at `-O0` all three of them can be stack slots. That
/// is tamnd/rucc#913, and what answers it is [`Scratch::borrow`] rather than a third register held
/// back, since holding a third back costs every function a register and this costs only the
/// instruction that wanted one.
#[derive(Debug, Default)]
struct Taken {
    /// How many of each class hold a value read in ahead of the instruction.
    read: Vec<usize>,
    /// How many of each class hold an answer the instruction writes.
    written: Vec<usize>,
}

impl Taken {
    /// Nothing handed out yet.
    fn new() -> Self {
        Self::default()
    }

    /// A register of a class for a value read in ahead of the instruction.
    fn read_into(&mut self, class: RegClass, scratch: &mut Scratch<'_>) -> PhysReg {
        Self::take(&mut self.read, class, scratch, Role::Use)
    }

    /// A register of a class for an answer the instruction writes.
    fn written_into(&mut self, class: RegClass, scratch: &mut Scratch<'_>) -> PhysReg {
        Self::take(&mut self.written, class, scratch, Role::Def)
    }

    /// The next register of a class out of one of the two counts, passing over any the instruction
    /// has already named itself for a value travelling the same way and borrowing one when the held
    /// back ones run out.
    ///
    /// An operand with a fixed constraint names a register the instruction has to have its value
    /// in, and the move that puts it there is in the same list as the move that would fill a
    /// scratch register. So handing the same register out for both would lose one of the two
    /// values, quietly and at run time. It is passed over instead.
    ///
    /// Which way the value travels is what decides whether there is a clash at all, and [`Claimed`]
    /// says why. A register the instruction only writes is free to carry a value in, which is what a
    /// call wants: a call names every caller saved register as one it writes, and those are the very
    /// registers held back for scratch.
    ///
    /// A clash comes up on a machine where a register held back is one an instruction can also
    /// insist on, and on x86-64 the way in is inline assembly naming `r10` or `r11`.
    fn take(
        counts: &mut Vec<usize>,
        class: RegClass,
        scratch: &mut Scratch<'_>,
        role: Role,
    ) -> PhysReg {
        let index = usize::from(class.number());
        if counts.len() <= index {
            counts.resize(index + 1, 0);
        }
        let held: &[PhysReg] = scratch.env.scratch(class);
        while held.get(counts[index]).is_some_and(|&reg| scratch.claimed.clashes(role, class, reg))
        {
            counts[index] += 1;
        }
        if let Some(&at) = held.get(counts[index]) {
            counts[index] += 1;
            return at;
        }
        scratch.borrow(class)
    }
}

/// The registers the instruction has named for itself, which scratch has to work around.
///
/// A register is kept with the class it was named in, because a register number is only a number
/// into one file and the same one means a different register in another: a call names sixteen vector
/// registers numbered nought to fifteen and sixteen general purpose ones numbered the same, and
/// reading the two lists as one leaves the general purpose file looking entirely spoken for.
///
/// Reading and writing are kept apart because they clash with different things. A register a value
/// arrives in is one no move in front of the instruction may write, and a register an answer leaves
/// in is one no move behind it may write. A call is the case that makes the difference matter: it
/// names every caller saved register as one it writes, `r10` and `r11` among them, and an indirect
/// call through a pointer on the stack has to read that pointer into one of exactly those two.
#[derive(Debug, Default)]
struct Claimed {
    /// The registers a value arrives in, with the class each was named in.
    reads: Vec<(RegClass, PhysReg)>,
    /// The registers an answer leaves in, with the class each was named in.
    writes: Vec<(RegClass, PhysReg)>,
}

impl Claimed {
    /// Records a register an operand named, on the side its value travels.
    fn named(&mut self, operand: &Operand, at: PhysReg) {
        self.side_mut(operand.role).push((operand.class, at));
    }

    /// Records a register nothing may be handed for the rest of the instruction, which is one
    /// [`Scratch::borrow`] has just taken.
    fn taken(&mut self, class: RegClass, at: PhysReg) {
        self.reads.push((class, at));
        self.writes.push((class, at));
    }

    /// Whether handing that register out for a value travelling that way would lose a value.
    fn clashes(&self, role: Role, class: RegClass, at: PhysReg) -> bool {
        self.side(role).contains(&(class, at))
    }

    /// Whether the instruction names that register at all, which is what borrowing has to keep off:
    /// what is borrowed is put back behind the instruction, over anything left there.
    fn names(&self, class: RegClass, at: PhysReg) -> bool {
        self.reads.contains(&(class, at)) || self.writes.contains(&(class, at))
    }

    /// The list for values travelling that way. The lists are one instruction's long, so a scan
    /// beats a set.
    fn side(&self, role: Role) -> &Vec<(RegClass, PhysReg)> {
        if role.is_def() { &self.writes } else { &self.reads }
    }

    /// The same, to write to.
    fn side_mut(&mut self, role: Role) -> &mut Vec<(RegClass, PhysReg)> {
        if role.is_def() { &mut self.writes } else { &mut self.reads }
    }
}

/// Moves waiting to be filed, each with the class of the value it moves.
///
/// The class travels with the move because an [`Edit`] carries one and the consumer needs it to pick
/// the instruction that does the move, and by the time a move is filed the operand it came from is
/// out of reach.
type Moves = Vec<(Move<Place>, RegClass)>;

/// The frame slots a borrowed register's value waits in, one list per class.
///
/// They belong to the function rather than to an instruction, because a borrowed register is given
/// back before the next instruction starts and the slot is dead in between, so one slot serves
/// every instruction in the function that borrows. Most functions never take one at all.
type Spare = Vec<Vec<u32>>;

/// What it takes to hand a register to one instruction.
///
/// It is a struct rather than four arguments because [`Scratch::borrow`] writes to all of them at
/// once: it reads the environment, takes a slot off the assignment, remembers the register so a
/// second borrow at the same instruction does not land on it, and files the two moves that make it
/// safe.
struct Scratch<'a> {
    env: &'a Env,
    /// Where every value went, and where a slot for a borrowed register comes from.
    assignment: &'a mut Assignment,
    /// The function's slots for borrowed registers, reused at every instruction.
    spare: &'a mut Spare,
    /// Every register the instruction has named, and then every one borrowed here as it is borrowed.
    claimed: Claimed,
    /// How many of each class have been borrowed at this instruction, which says which slot the
    /// next one uses.
    borrowed: Vec<usize>,
    /// The moves that put a borrowed register's value away, which go in front of everything else.
    saves: Moves,
    /// The moves that bring it back, which go behind everything else.
    restores: Moves,
}

impl<'a> Scratch<'a> {
    /// Nothing borrowed yet at an instruction claiming those registers.
    fn new(
        env: &'a Env,
        assignment: &'a mut Assignment,
        spare: &'a mut Spare,
        claimed: Claimed,
    ) -> Self {
        Self {
            env,
            assignment,
            spare,
            claimed,
            borrowed: Vec::new(),
            saves: Vec::new(),
            restores: Vec::new(),
        }
    }

    /// A register of the class the instruction is not using, with whatever is in it put away in
    /// front of the instruction and brought back behind it.
    ///
    /// This is what a class runs out to, and it works on any machine because it asks nothing at all
    /// of the register it takes. Whatever was in it is somewhere else for the length of one
    /// instruction, so it does not matter whether that value is wanted afterwards, whether the
    /// callee owes the register back, or whether an argument travels in it, which are the three
    /// things that make a register held back hard to find. What it costs is two memory accesses at
    /// the one instruction that wanted it and one slot of the frame, against a register taken off
    /// every function in the program, and `rucc_codegen::pipeline` says why that trade goes this
    /// way round on x86-64.
    ///
    /// The register is any of the class the instruction has not claimed for itself. A register the
    /// allocator gave a value that is live right across the instruction is as good as an idle one,
    /// which is the whole point of putting the contents away first.
    ///
    /// # Panics
    ///
    /// Panics if the class has no register the instruction has not already claimed, which is an
    /// instruction naming every register of a file at once.
    fn borrow(&mut self, class: RegClass) -> PhysReg {
        let index = usize::from(class.number());
        let at = *self
            .env
            .order(class)
            .iter()
            .find(|&&reg| !self.claimed.names(class, reg))
            .expect("an instruction naming every register of its class at once");

        if self.borrowed.len() <= index {
            self.borrowed.resize(index + 1, 0);
        }
        if self.spare.len() <= index {
            self.spare.resize(index + 1, Vec::new());
        }
        let nth = self.borrowed[index];
        if self.spare[index].len() <= nth {
            let slot = self.assignment.take_slot(class);
            self.spare[index].push(slot);
        }
        let slot = self.spare[index][nth];

        self.borrowed[index] = nth + 1;
        self.claimed.taken(class, at);
        self.saves.push((Move::new(Place::Slot(slot), Place::Reg(at)), class));
        self.restores.push((Move::new(Place::Reg(at), Place::Slot(slot)), class));
        at
    }

    /// The moves either side of the instruction, once every register has been handed out.
    fn finish(self) -> (Moves, Moves) {
        (self.saves, self.restores)
    }
}

/// Files a move in front of the instruction or behind it, and turns it round for a value the
/// instruction writes, since that one travels the other way.
fn push(before: &mut Moves, after: &mut Moves, operand: &Operand, mov: Move<Place>) {
    if operand.role.is_def() {
        after.push((Move::new(mov.from, mov.to), operand.class));
    } else {
        before.push((mov, operand.class));
    }
}

/// The moves the edges out of a block turn into.
fn edges(
    func: &mut Func,
    assignment: &Assignment,
    env: &Env,
    block: Block,
    preds: &[usize],
    edits: &mut Vec<Edit>,
) {
    let succs = func[block].succs.clone();
    let single = succs.len() == 1;
    for call in &succs {
        let params = func[call.block].params.clone();
        assert_eq!(
            params.len(),
            call.args.len(),
            "an edge carries what the block it goes to asks for"
        );
        if params.is_empty() {
            continue;
        }
        assert!(
            single || preds[call.block.index()] == 1,
            "a critical edge has nowhere to put its moves and has to be split before allocation"
        );
        let at = if single { At::EndOf(block) } else { At::StartOf(call.block) };
        edits.extend(edge(assignment, env, &params, &call.args, at));
    }
}

/// The moves one edge turns into, in the order they can be made in.
fn edge(assignment: &Assignment, env: &Env, params: &[Param], args: &[Reg], at: At) -> Vec<Edit> {
    let mut classes: Vec<RegClass> = params.iter().map(|param| param.class).collect();
    classes.sort_unstable();
    classes.dedup();

    let mut edits = Vec::new();
    for class in classes {
        // One class at a time, because a scratch register is per class and a value never crosses
        // from one to another on an edge.
        let parallel: Vec<Move<Place>> = params
            .iter()
            .zip(args)
            .filter(|(param, _)| param.class == class)
            .map(|(param, &arg)| Move::new(place(assignment, param.reg), place(assignment, arg)))
            .collect();
        let scratch = env.scratch(class);
        let cycle = *scratch
            .first()
            .expect("a class whose values are passed on an edge and which has no scratch register");
        for mov in moves::sequence(&parallel, Place::Reg(cycle)) {
            match (mov.to, mov.from) {
                // No machine here moves one piece of memory into another, so the value goes
                // through a register, and it is a second scratch rather than the one the ordering
                // above may be holding a value in for the length of a cycle.
                (Place::Slot(_), Place::Slot(_)) => {
                    let through = Place::Reg(*scratch.get(1).expect(
                        "a class passing a spilled value to a spilled parameter and having only \
                         one scratch register",
                    ));
                    edits.push(Edit { at, mov: Move::new(through, mov.from), class });
                    edits.push(Edit { at, mov: Move::new(mov.to, through), class });
                }
                _ => edits.push(Edit { at, mov, class }),
            }
        }
    }
    edits
}

/// How many edges arrive in each block.
fn preds(func: &Func, blocks: &[Block]) -> Vec<usize> {
    let mut preds = vec![0; func.block_count()];
    for &block in blocks {
        for call in &func[block].succs {
            preds[call.block.index()] += 1;
        }
    }
    preds
}

/// Where a register is, whether the allocator put it there or it was already somewhere.
fn place(assignment: &Assignment, reg: Reg) -> Place {
    assignment.place(reg).unwrap_or_else(|| Place::Reg(phys(reg)))
}

/// The physical register a register is, once it has to be one.
fn phys(reg: Reg) -> PhysReg {
    reg.phys().expect("a register the assignment says nothing about and that is not a register")
}

#[cfg(test)]
mod tests {
    use rucc_base::Interner;
    use rucc_mir::{BlockCall, Opcode};
    use rucc_target::x86_64::{GPR, RAX, RCX, RDX, REGS, RSI, SYSV, XMM};

    use super::*;
    use crate::assign::assign;
    use crate::live::Live;
    use crate::order::Order;

    /// The x86-64 environment, with the last three of the allocation order held back as scratch.
    fn env() -> Env {
        let (order, scratch) = SYSV.int_order.split_at(SYSV.int_order.len() - 3);
        Env::new().with(GPR, order, scratch)
    }

    /// An environment with that many general purpose registers and two scratch after them.
    fn narrow(count: usize) -> Env {
        Env::new().with(GPR, &SYSV.int_order[..count], &SYSV.int_order[count..count + 2])
    }

    /// What a place is called, which is what an assertion reads.
    ///
    /// The class comes in because a register is a number within its class and the two files here
    /// number from zero, so nothing but the class tells `rcx` from `xmm1`.
    fn named(class: RegClass, place: Place) -> String {
        match place {
            Place::Reg(reg) => REGS.name(class, reg).expect("a register").to_string(),
            Place::Slot(slot) => format!("slot{slot}"),
        }
    }

    /// Runs both halves and reports the edits as lines an assertion can read.
    fn run(func: &mut Func, env: &Env) -> Vec<String> {
        let order = Order::of(func);
        let live = Live::of(func, &order);
        let mut assignment = assign(func, &order, &live, env);
        rewrite(func, &mut assignment, env)
            .into_iter()
            .map(|edit| {
                let at = match edit.at {
                    At::Before(inst) => format!("before {}", inst.index()),
                    At::After(inst) => format!("after {}", inst.index()),
                    At::StartOf(block) => format!("start of {}", block.index()),
                    At::EndOf(block) => format!("end of {}", block.index()),
                };
                format!(
                    "{at}: {} = {}",
                    named(edit.class, edit.mov.to),
                    named(edit.class, edit.mov.from)
                )
            })
            .collect()
    }

    /// The registers an instruction's operands ended up naming.
    fn operands(func: &Func, inst: Inst) -> Vec<String> {
        func[func[inst].operands]
            .iter()
            .map(|operand| named(operand.class, Place::Reg(phys(operand.reg))))
            .collect()
    }

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

        assert_eq!(run(&mut func, &env()), Vec::<String>::new());
        assert_eq!(operands(&func, read), ["rax", "rcx"]);
    }

    #[test]
    fn a_register_an_instruction_insists_on_costs_nothing_when_the_values_can_have_it() {
        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 dividend = func.new_vreg(GPR);
        let quotient = func.new_vreg(GPR);
        func.build(block, opcode).def(dividend, GPR).finish();
        let divide = func
            .build(block, opcode)
            .operand(Operand::write(quotient, GPR).with(Constraint::Fixed(RAX)))
            .operand(Operand::read(dividend, GPR).with(Constraint::Fixed(RAX)))
            .finish();
        func.build(block, opcode).uses(quotient, GPR).finish();

        // Nothing either side of the division. The dividend is read out of `rax` for the last
        // time and the quotient is written into it afterwards, so both of them live there and the
        // moves that used to carry the value in and the answer out are not written.
        assert_eq!(run(&mut func, &env()), Vec::<String>::new());
        assert_eq!(operands(&func, divide), ["rax", "rax"]);
    }

    #[test]
    fn a_register_an_instruction_insists_on_is_moved_into_when_the_value_cannot_have_it() {
        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 dividend = func.new_vreg(GPR);
        let quotient = func.new_vreg(GPR);
        func.build(block, opcode).def(dividend, GPR).finish();
        let divide = func
            .build(block, opcode)
            .operand(Operand::write(quotient, GPR).with(Constraint::Fixed(RAX)))
            .operand(Operand::read(dividend, GPR).with(Constraint::Fixed(RAX)))
            .finish();
        func.build(block, opcode).uses(quotient, GPR).finish();
        func.build(block, opcode).uses(dividend, GPR).finish();

        // This time the dividend is wanted after the division, so it cannot be in the register the
        // division writes and the value is moved in. The answer still comes out of `rax` without
        // a move, which is the half of it the hint bought.
        assert_eq!(run(&mut func, &env()), ["before 1: rax = rcx"]);
        assert_eq!(operands(&func, divide), ["rax", "rax"]);
    }

    #[test]
    fn a_two_address_instruction_that_did_not_get_its_register_copies_first() {
        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 left = func.new_vreg(GPR);
        let right = func.new_vreg(GPR);
        let sum = func.new_vreg(GPR);
        func.build(block, opcode).def(left, GPR).finish();
        func.build(block, opcode).def(right, GPR).finish();
        let add = func
            .build(block, opcode)
            .operand(Operand::write(sum, GPR).with(Constraint::Reuse(1)))
            .uses(left, GPR)
            .uses(right, GPR)
            .finish();
        func.build(block, opcode).uses(left, GPR).finish();

        // The left value is wanted afterwards, so the answer could not have its register and the
        // copy in front of the addition is what makes the instruction two address.
        assert_eq!(run(&mut func, &env()), ["before 2: rdx = rax"]);
        assert_eq!(operands(&func, add), ["rdx", "rax", "rcx"]);
    }

    #[test]
    fn a_two_address_instruction_that_did_get_its_register_copies_nothing() {
        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 left = func.new_vreg(GPR);
        let right = func.new_vreg(GPR);
        let sum = func.new_vreg(GPR);
        func.build(block, opcode).def(left, GPR).finish();
        func.build(block, opcode).def(right, GPR).finish();
        let add = func
            .build(block, opcode)
            .operand(Operand::write(sum, GPR).with(Constraint::Reuse(1)))
            .uses(left, GPR)
            .uses(right, GPR)
            .finish();
        func.build(block, opcode).uses(right, GPR).finish();

        assert_eq!(run(&mut func, &env()), Vec::<String>::new());
        assert_eq!(operands(&func, add), ["rax", "rax", "rcx"]);
    }

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

        // One register between two values, so one of them goes to the stack. It is written there
        // where it is computed and read back where it is wanted, and both ends of that go through
        // the scratch register that is held out of the allocation order for exactly this.
        assert_eq!(run(&mut func, &narrow(1)), ["after 1: slot0 = rcx", "before 2: rcx = slot0"]);
        assert_eq!(operands(&func, read), ["rax", "rcx"]);
    }

    /// A two address instruction with nothing in a register is two scratch registers and not three.
    ///
    /// The answer has no register of its own to be in, so what it is written into is whichever one
    /// the operand it reuses was read into, and it is stored away from there afterwards. Handing it
    /// a scratch register of its own would want a third, and a class holds two back, which is issue
    /// #350: a program with enough live values around a call reached it and the compiler aborted.
    #[test]
    fn a_two_address_instruction_whose_answer_and_operands_are_all_spilled_wants_two_registers() {
        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 keeper = func.new_vreg(GPR);
        let left = func.new_vreg(GPR);
        let right = func.new_vreg(GPR);
        let sum = func.new_vreg(GPR);
        func.build(block, opcode).def(keeper, GPR).finish();
        func.build(block, opcode)
            .operand(Operand::write(left, GPR).with(Constraint::Stack))
            .finish();
        func.build(block, opcode)
            .operand(Operand::write(right, GPR).with(Constraint::Stack))
            .finish();
        let add = func
            .build(block, opcode)
            .operand(Operand::write(sum, GPR).with(Constraint::Reuse(1)))
            .uses(left, GPR)
            .uses(right, GPR)
            .finish();
        func.build(block, opcode).uses(keeper, GPR).finish();
        func.build(block, opcode).uses(sum, GPR).finish();

        // Both operands are read in, the answer is written into the register the operand it
        // reuses arrived in, and it is stored away from there. Two scratch registers, which is
        // what the class holds back. Asking for one of its own would be a third and would abort.
        assert_eq!(
            run(&mut func, &narrow(1)),
            [
                "after 1: slot0 = rcx",
                "after 2: slot1 = rcx",
                "before 3: rcx = slot0",
                "before 3: rdx = slot1",
                "after 3: slot2 = rcx",
                "before 5: rcx = slot2",
            ]
        );
        assert_eq!(operands(&func, add), ["rcx", "rcx", "rdx"]);
    }

    /// A three address instruction with nothing in a register is two scratch registers, not three.
    ///
    /// The case #726 aborted on. `x64.lea_64` and the `x64.cmp_set_*` family read two values and
    /// write a third that is neither of them, and when all three ends are on the stack there are
    /// three operands wanting a register at one instruction. Counting them in one running number
    /// asks for a third scratch register and the class holds two back.
    ///
    /// Two is enough because the answer's register is not wanted until the instruction writes it,
    /// by which time the registers the operands were read into have been read. So the answer goes
    /// back into the first of them and is stored away from there.
    #[test]
    fn a_three_address_instruction_whose_answer_and_operands_are_all_spilled_wants_two_registers() {
        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 keeper = func.new_vreg(GPR);
        let base = func.new_vreg(GPR);
        let index = func.new_vreg(GPR);
        let address = func.new_vreg(GPR);
        func.build(block, opcode).def(keeper, GPR).finish();
        func.build(block, opcode)
            .operand(Operand::write(base, GPR).with(Constraint::Stack))
            .finish();
        func.build(block, opcode)
            .operand(Operand::write(index, GPR).with(Constraint::Stack))
            .finish();
        let lea =
            func.build(block, opcode).def(address, GPR).uses(base, GPR).uses(index, GPR).finish();
        func.build(block, opcode).uses(keeper, GPR).finish();
        func.build(block, opcode).uses(address, GPR).finish();

        // Both operands are read in, the answer is written into the first of the two registers
        // they arrived in, and it is stored away from there. Two, which is what the class holds.
        assert_eq!(
            run(&mut func, &narrow(1)),
            [
                "after 1: slot0 = rcx",
                "after 2: slot1 = rcx",
                "before 3: rcx = slot0",
                "before 3: rdx = slot1",
                "after 3: slot2 = rcx",
                "before 5: rcx = slot2",
            ]
        );
        assert_eq!(operands(&func, lea), ["rcx", "rcx", "rdx"]);
    }

    /// A spilled answer takes a scratch register where the operand it reuses is in a real one.
    ///
    /// The value in that register may be wanted after the instruction, and the assignment is the
    /// only thing that knows whether it is. It says so by giving the answer that register, and here
    /// it did not, so writing over it would destroy a value. The count still comes to two, because
    /// an operand that is in a register is not holding a scratch register.
    #[test]
    fn a_spilled_answer_does_not_write_over_a_register_the_assignment_gave_to_something_else() {
        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 left = func.new_vreg(GPR);
        let right = func.new_vreg(GPR);
        let sum = func.new_vreg(GPR);
        func.build(block, opcode).def(left, GPR).finish();
        func.build(block, opcode)
            .operand(Operand::write(right, GPR).with(Constraint::Stack))
            .finish();
        let add = func
            .build(block, opcode)
            .operand(Operand::write(sum, GPR).with(Constraint::Reuse(1)))
            .uses(left, GPR)
            .uses(right, GPR)
            .finish();
        func.build(block, opcode).uses(left, GPR).finish();
        func.build(block, opcode).uses(sum, GPR).finish();

        // The left value is in `rax` and is read again afterwards, so the answer is copied into a
        // scratch register and written there instead.
        assert_eq!(
            run(&mut func, &narrow(1)),
            [
                "after 1: slot0 = rcx",
                "before 2: rcx = slot0",
                "before 2: rdx = rax",
                "after 2: slot1 = rdx",
                "before 4: rcx = slot1",
            ]
        );
        assert_eq!(operands(&func, add), ["rdx", "rax", "rcx"]);
    }

    /// The count of scratch registers handed out is per class and not one number for all of them.
    ///
    /// An instruction reading a spilled value out of each of two files wants the first register of
    /// each, since the files hold their own back and nothing on the instruction is in the other's.
    #[test]
    fn an_instruction_reading_out_of_two_files_takes_the_first_scratch_register_of_each() {
        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 integer = func.new_vreg(GPR);
        let number = func.new_vreg(XMM);
        let spare = func.new_vreg(GPR);
        let other = func.new_vreg(XMM);
        func.build(block, opcode).def(integer, GPR).finish();
        func.build(block, opcode).def(number, XMM).finish();
        func.build(block, opcode).def(spare, GPR).finish();
        func.build(block, opcode).def(other, XMM).finish();
        func.build(block, opcode).uses(integer, GPR).uses(number, XMM).finish();
        let read = func.build(block, opcode).uses(spare, GPR).uses(other, XMM).finish();

        // One register in each file, so the value of each that is wanted later goes to the stack
        // and is read back at the instruction that wants it.
        let env = Env::new().with(GPR, &SYSV.int_order[..1], &SYSV.int_order[1..3]).with(
            XMM,
            &SYSV.sse_order[..1],
            &SYSV.sse_order[1..3],
        );
        assert_eq!(
            run(&mut func, &env),
            [
                "after 2: slot0 = rcx",
                "after 3: slot1 = xmm1",
                "before 5: rcx = slot0",
                "before 5: xmm1 = slot1",
            ]
        );
        assert_eq!(operands(&func, read), ["rcx", "xmm1"]);
    }

    #[test]
    fn an_edge_out_of_a_block_with_one_way_to_go_moves_at_the_end_of_it() {
        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 tail = func.create_block();
        let held = func.new_vreg(GPR);
        let carried = func.new_vreg(GPR);
        func.build(head, opcode).def(held, GPR).finish();
        func.build(head, opcode).def(carried, GPR).finish();
        func.build(head, opcode).uses(held, GPR).finish();
        let param = func.append_param(tail, GPR);
        *func.succs_mut(head) = vec![BlockCall::with(tail, vec![carried])];
        let read = func.build(tail, opcode).uses(param, GPR).finish();

        // The value the edge carries is in the second register, because the first was busy where
        // the value was written, and the parameter it arrives as is in the first, because by then
        // it is not. So the edge is a move, and it goes at the end of the block it leaves.
        assert_eq!(run(&mut func, &env()), ["end of 0: rax = rcx"]);
        assert_eq!(operands(&func, read), ["rax"]);
        // Nothing arrives in a block any more and no edge carries anything, which is where SSA
        // form stops.
        assert!(func[tail].params.is_empty());
        assert!(func[head].succs[0].args.is_empty());
    }

    #[test]
    fn an_edge_out_of_a_block_with_a_choice_moves_at_the_start_of_where_it_goes() {
        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();
        let held = func.new_vreg(GPR);
        let carried = func.new_vreg(GPR);
        func.build(head, opcode).def(held, GPR).finish();
        func.build(head, opcode).def(carried, GPR).finish();
        func.build(head, opcode).uses(held, GPR).finish();
        let taken = func.append_param(left, GPR);
        *func.succs_mut(head) = vec![BlockCall::with(left, vec![carried]), BlockCall::to(right)];
        func.build(left, opcode).uses(taken, GPR).finish();

        // The move cannot go at the end of the block it leaves, because the other way out of that
        // block does not want it. It goes at the start of the block it arrives in, which is safe
        // because nothing else arrives there.
        assert_eq!(run(&mut func, &env()), ["start of 1: rax = rcx"]);
    }

    #[test]
    fn two_values_that_swap_on_an_edge_get_an_order_and_a_scratch_register() {
        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 body = func.create_block();
        let first = func.new_vreg(GPR);
        let second = func.new_vreg(GPR);
        func.build(head, opcode).def(first, GPR).finish();
        func.build(head, opcode).def(second, GPR).finish();
        let left = func.append_param(body, GPR);
        let right = func.append_param(body, GPR);
        *func.succs_mut(head) = vec![BlockCall::with(body, vec![first, second])];
        func.build(body, opcode).uses(left, GPR).uses(right, GPR).finish();
        *func.succs_mut(body) = vec![BlockCall::with(body, vec![right, left])];

        // The loop hands each value back the other way round, which is the case no order of two
        // moves answers, so one of them goes through the scratch register. The edge into the loop
        // moves nothing, because each value is already where the parameter it feeds lives.
        assert_eq!(
            run(&mut func, &env()),
            ["end of 1: r13 = rcx", "end of 1: rcx = rax", "end of 1: rax = r13"]
        );
    }

    #[test]
    fn a_spilled_value_handed_to_a_spilled_parameter_goes_through_a_register() {
        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 body = func.create_block();
        let first = func.new_vreg(GPR);
        let second = func.new_vreg(GPR);
        func.build(head, opcode).def(first, GPR).finish();
        func.build(head, opcode).def(second, GPR).finish();
        let left = func.append_param(body, GPR);
        let right = func.append_param(body, GPR);
        *func.succs_mut(head) = vec![BlockCall::with(body, vec![first, second])];
        func.build(body, opcode).uses(left, GPR).uses(right, GPR).finish();

        // One register between the values and the parameters, so a value on the stack is handed to
        // a parameter on the stack, and no machine here has that instruction. It goes through the
        // second scratch register rather than the first, which is the one the ordering above is
        // entitled to be holding a value in.
        assert_eq!(
            run(&mut func, &narrow(1)),
            [
                "after 1: slot0 = rcx",
                "before 2: rcx = slot1",
                "end of 0: rdx = slot0",
                "end of 0: slot1 = rdx",
            ]
        );
    }

    /// Three values read and none written wants a third register, which is tamnd/rucc#913.
    ///
    /// There is no answer here to fold back into the register an operand arrived in, so the trick
    /// that keeps a two address instruction down to two has nothing to work on and each of the
    /// three wants a register of its own. The instruction is the indexed store: `a[i] = v` reads a
    /// base, an index and a value, and at `-O0`, where nothing is coalesced, all three of them are
    /// stack slots. The rewriter aborted on it, which stopped brotli and cmocka on the first file
    /// that held one and sqlite3 on `fts5Init`.
    ///
    /// The third register is borrowed rather than held back, and the borrowing is what this is
    /// really about: it takes a register the allocator gave to a value that is live right across
    /// the instruction, which is safe because that value is put in a slot in front of the
    /// instruction and brought back behind it.
    #[test]
    fn an_instruction_reading_three_spilled_values_borrows_a_register_for_the_third() {
        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 keeper = func.new_vreg(GPR);
        let base = func.new_vreg(GPR);
        let index = func.new_vreg(GPR);
        let value = func.new_vreg(GPR);
        func.build(block, opcode).def(keeper, GPR).finish();
        for reg in [base, index, value] {
            func.build(block, opcode)
                .operand(Operand::write(reg, GPR).with(Constraint::Stack))
                .finish();
        }
        let store =
            func.build(block, opcode).uses(base, GPR).uses(index, GPR).uses(value, GPR).finish();
        func.build(block, opcode).uses(keeper, GPR).finish();

        assert_eq!(
            run(&mut func, &narrow(2)),
            [
                "after 1: slot0 = rdx",
                "after 2: slot1 = rdx",
                "after 3: slot2 = rdx",
                "before 4: slot3 = rax",
                "before 4: rdx = slot0",
                "before 4: rsi = slot1",
                "before 4: rax = slot2",
                "after 4: rax = slot3",
            ]
        );
        assert_eq!(operands(&func, store), ["rdx", "rsi", "rax"]);
    }

    /// A register the instruction only writes still carries a value in.
    ///
    /// A call names every caller saved register as one it writes, and on x86-64 the two held back for
    /// scratch are both caller saved, so an indirect call through a pointer on the stack has nowhere
    /// to read the pointer into unless a register named only on the way out is still free on the way
    /// in. Reading them as spoken for stopped cmocka on its first file.
    #[test]
    fn a_register_the_instruction_only_writes_still_carries_a_value_in() {
        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 target = func.new_vreg(GPR);
        func.build(block, opcode)
            .operand(Operand::write(target, GPR).with(Constraint::Stack))
            .finish();
        let call = func
            .build(block, opcode)
            .def(Reg::physical(RDX), GPR)
            .def(Reg::physical(RSI), GPR)
            .uses(target, GPR)
            .finish();

        assert_eq!(run(&mut func, &narrow(2)), ["after 0: slot0 = rdx", "before 1: rdx = slot0"]);
        assert_eq!(operands(&func, call), ["rdx", "rsi", "rdx"]);
    }

    /// A scratch register the instruction has already named for itself is passed over.
    ///
    /// The move that carries a value into a register a fixed constraint asks for and the move that
    /// fills a scratch register both go in front of the instruction, so handing the same register
    /// out twice would lose one of the two values without anything saying so. On x86-64 the way
    /// into this is inline assembly naming `r10` or `r11`, which are the two the file holds back.
    #[test]
    fn a_register_the_instruction_already_named_is_not_handed_out_as_scratch() {
        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 wanted = func.new_vreg(GPR);
        let other = func.new_vreg(GPR);
        for reg in [wanted, other] {
            func.build(block, opcode)
                .operand(Operand::write(reg, GPR).with(Constraint::Stack))
                .finish();
        }
        let read = func
            .build(block, opcode)
            .operand(Operand::read(wanted, GPR).with(Constraint::Fixed(RCX)))
            .uses(other, GPR)
            .finish();

        // `rcx` is both the first scratch register here and the one the instruction insists on, so
        // the value it did not ask for by name starts at the second one instead.
        assert_eq!(
            run(&mut func, &narrow(1)),
            [
                "after 0: slot0 = rcx",
                "after 1: slot1 = rcx",
                "before 2: rcx = slot0",
                "before 2: rdx = slot1"
            ]
        );
        assert_eq!(operands(&func, read), ["rcx", "rdx"]);
    }

    #[test]
    #[should_panic(expected = "a critical edge has nowhere to put its moves")]
    fn a_critical_edge_is_refused() {
        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 other = func.create_block();
        let join = func.create_block();
        let value = func.new_vreg(GPR);
        func.build(head, opcode).def(value, GPR).finish();
        let param = func.append_param(join, GPR);
        *func.succs_mut(head) = vec![BlockCall::with(join, vec![value]), BlockCall::to(other)];
        *func.succs_mut(other) = vec![BlockCall::with(join, vec![value])];
        func.build(join, opcode).uses(param, GPR).finish();

        let _ = run(&mut func, &env());
    }

    #[test]
    #[should_panic(expected = "what arrives in a function is not a block parameter")]
    fn a_parameter_on_the_entry_block_is_refused() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let param = func.append_param(block, GPR);
        let opcode = Opcode::new(names.intern("x64.nop"));
        func.build(block, opcode).uses(param, GPR).finish();

        let _ = run(&mut func, &env());
    }

    #[test]
    fn a_value_already_in_a_register_is_left_where_it_is() {
        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 inst = func.build(block, opcode).uses(Reg::physical(RDX), GPR).finish();

        assert_eq!(run(&mut func, &env()), Vec::<String>::new());
        assert_eq!(operands(&func, inst), ["rdx"]);
    }
}