rucc_mir/

func.rs

//! The function: its blocks, its instructions, and the tables they live in.
//!
//! Design: `spec/10-backend.md` section 10.1.
//!
//! One [`Func`] owns everything in it, the same shape `rucc-ir` uses and for the same reasons:
//! nothing is boxed, a reference to an instruction is a four-byte index, and the whole function
//! is dropped in one go.
//!
//! The instructions in a block are a doubly linked list rather than a run, because the passes
//! that run over MIR are the ones that insert most: the allocator writes spills and reloads
//! between existing instructions, edge moves appear after it, and the peepholes of
//! `spec/10-backend.md` section 10.9 delete. A run would move everything after each edit and
//! invalidate every index a pass was holding.
//!
//! A block's parameters and its successors are `Vec`s rather than runs in a pool, because both
//! grow after the block exists. Splitting a critical edge adds a block whose successor list is
//! written after it is created, and the allocator's live-range splitting adds parameters.
//!
//! # What the builder keeps
//!
//! An instruction's operands are in one order and only one: the ones it writes, then the ones it
//! reads, then the registers its memory operand names. The printer writes that order and the
//! parser rebuilds it, so a function whose operands are in some other order prints as text that
//! reads back as a different function. [`InstBuilder`] is what makes the order an invariant
//! rather than a rule every caller has to remember, which is why it is the only way to make an
//! instruction that is in a block.

use std::ops::{Index, IndexMut};

use rucc_base::{Idx, IdxRange, Symbol};
use rucc_diag::Span;
use rucc_target::RegClass;

use crate::inst::{
    Amode, Block, BlockCall, BlockData, Imm, ImmRef, Inst, InstData, InstLayout, Mem, MemRef,
    Opcode, Operand, OperandList, Param, Reg,
};

/// How far a function's name reaches.
///
/// The three an object file can say, which is fewer than the five the IR has, and the narrowing
/// is done where a function is lowered rather than where it is written out. What it is here for
/// is to survive the trip: everything between the IR and the object file is handed machine
/// functions, so a fact about the symbol that is not on one is a fact that is gone.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub enum Binding {
    /// Visible to every other object, and the definition here is the definition. What a plain
    /// definition at file scope gets, which is why it is the one a function starts as.
    #[default]
    Global,
    /// Invisible outside this object, which is what `static` at file scope means. Two files may
    /// each have one of the same name and they are two functions.
    Local,
    /// Visible, and allowed to lose to a definition in another object.
    Weak,
}

/// How far outside a shared library a function's name reaches.
///
/// Here for the reason [`Binding`] is here and not for any other: everything between the IR and
/// the object file is handed machine functions, so a fact about the symbol that is not on one is
/// a fact that is gone by the time anything can write it down. Nothing in this crate reads it.
///
/// The three the IR has, unnarrowed, because ELF says all three and the format is what decides
/// how many there are rather than the machine.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub enum Visibility {
    /// In the dynamic symbol table and interposable, which is what a name nothing marked gets.
    #[default]
    Default,
    /// Not in the dynamic symbol table, so nothing outside the library can name it.
    Hidden,
    /// In the dynamic symbol table, and a call from inside the library binds to the definition
    /// inside it.
    Protected,
}

/// One row of the table that says what the frame looks like at a given instruction.
///
/// Design: `spec/11-asm-objects-debug.md` section 11.6.
///
/// An unwinder is handed a return address and has to answer two questions about the function it
/// landed in: where the caller's stack pointer was, and where the caller's copy of each register
/// this function overwrote went. The first answer is a register and an offset and is called the
/// canonical frame address. The second is one entry per register that was saved. Both change as
/// the prologue runs, which is why this is a table over the function and not a fact about it.
///
/// The register numbers here are DWARF's and not the machine's, because the two disagree on
/// x86-64 and there is no reason to write the mapping down twice: `rucc-target` holds it, the
/// prologue asks for it once, and the number that comes out is the number the listing prints and
/// the number the FDE encodes. That is why this enum can live in a crate that knows nothing about
/// any particular machine.
///
/// Every row takes effect after the instruction it is attached to, which is the only arrangement
/// that works: a rule describes the state a machine is in, and the machine is not in that state
/// until the instruction that puts it there has run.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CfiOp {
    /// The canonical frame address is that register plus that offset from here on.
    DefCfa {
        /// The register it is counted from, by DWARF's number for it.
        reg: u16,
        /// How far above that register's value it is.
        offset: i32,
    },
    /// The same register as before and a new offset, which is what a push or a subtraction from
    /// the stack pointer produces while the stack pointer is still what the address is counted
    /// from.
    DefCfaOffset(i32),
    /// The same offset as before and a new register, which is what pointing the frame pointer at
    /// the frame produces, and is the whole reason a frame pointer is worth having to an
    /// unwinder: after it the address stops depending on what the body does to the stack.
    DefCfaRegister(u16),
    /// The caller's copy of that register is in memory, that far from the canonical frame
    /// address. The offset is almost always negative, since the frame is below the address.
    Offset {
        /// The register that was saved, by DWARF's number for it.
        reg: u16,
        /// Where it went, counted from the canonical frame address.
        offset: i32,
    },
    /// That register holds what the caller left in it again, so the rule that said where the
    /// saved copy went stops applying.
    ///
    /// Worth writing down rather than leaving the old rule standing, because a table that is
    /// asked about every instruction is asked about the ones between a pop and the return, and by
    /// then the memory the old rule points at is above the stack pointer and is where a signal
    /// handler's own frame goes.
    Restore(u16),
    /// Put the whole rule set on a stack, so that an epilogue can undo its own changes without
    /// the next one starting from what it left behind.
    ///
    /// A function with several returns has several epilogues, and they are laid out one after
    /// another rather than nested, so without this the second one would begin from the rules the
    /// first one ended with rather than from the rules the body had.
    RememberState,
    /// Take the rule set back off that stack.
    RestoreState,
}

/// Where the room a patcher was promised at the top of a function is.
///
/// What `-fpatchable-function-entry=` asks for. The room is a run of the shortest instruction that
/// does nothing, and the point of it is that something else is written over it once the program is
/// running, so what has to survive to the writers is where it starts and how much of it there is.
///
/// Two halves, because the room can be on either side of the function's own label and the two sides
/// reach the writers differently. What is after the label is in the instruction stream like anything
/// else, so it is named by the first instruction of it. What is in front of the label is not in the
/// stream at all, since the stream starts at the label, so it is a count the writer lays down
/// itself, out of the one opcode kept here for it.
///
/// The address the room is recorded under is its start, which is the front of the half in front of
/// the label in a function that has one and the front of the other half otherwise. The two halves
/// are not always next to each other: a function that also opens with a landing pad has the pad
/// between them, because the pad has to be the first thing after the label and the room does not.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Patch {
    /// How many bytes go in front of the function's own label.
    pub before: u32,
    /// What one of those is written as, which is the instruction that does nothing.
    ///
    /// Kept because they are the only instructions in a finished function that are not in a block,
    /// so there is nowhere else for a writer to read the opcode off. The ones after the label are
    /// in the stream and this is the opcode they carry too.
    pub pad: Opcode,
    /// The first instruction of the room after the label, or `None` in a function whose room is all
    /// in front of it.
    pub after: Option<Inst>,
}

/// One function, in machine instructions.
#[derive(Debug)]
pub struct Func {
    /// The name it is called by, which is the name of the IR function it was lowered from.
    pub name: Symbol,
    /// What its first instruction has to be aligned to, from the IR function it was lowered
    /// from, or `None` for the alignment every function gets anyway.
    pub align: Option<u32>,
    /// How far the name reaches, from the linkage of the IR function it was lowered from.
    ///
    /// Nothing in this crate reads it. It is here because it is the last place the fact can be
    /// kept: the assembler and the object writer are handed functions and nothing else, so a
    /// machine function that does not carry this is one whose symbol they have no choice but to
    /// make global, and a `static` function that every object declares global is a link that
    /// fails the moment two files have one of the same name.
    pub binding: Binding,
    /// How far the name reaches outside a shared library, from the visibility of the IR function
    /// it was lowered from. Carried for the reason the binding above is carried.
    pub visibility: Visibility,
    /// What the frame looks like as the function runs, as rows attached to the instructions they
    /// take effect after. See [`CfiOp`].
    ///
    /// Written by whatever builds the prologue and the epilogues, because that is the only thing
    /// that knows what they did, and read by the listing and by the object writer. Empty until
    /// then, and empty for a machine nothing here writes a table for.
    pub cfi: Vec<(Inst, CfiOp)>,
    /// Where the room a patcher was promised is, or `None` in a function that was promised none,
    /// which is every function on a command line that did not ask. See [`Patch`].
    ///
    /// Written by whatever builds the prologue, for the reason [`Func::cfi`] is: a run of bytes
    /// that do nothing is indistinguishable from any other run of them once it is in the stream,
    /// so which one was reserved has to be said rather than looked for.
    pub patch: Option<Patch>,

    insts: Vec<InstData>,
    inst_layout: Vec<InstLayout>,
    inst_spans: Vec<Span>,
    blocks: Vec<BlockData>,

    operands: Vec<Operand>,
    imms: Vec<Imm>,
    amodes: Vec<Amode>,
    /// The class of each virtual register, which is what says how many there are and what the
    /// allocator may put each of them in.
    vregs: Vec<RegClass>,

    first_block: Option<Block>,
    last_block: Option<Block>,
}

impl Func {
    /// A function of that name with nothing in it.
    #[must_use]
    pub fn new(name: Symbol) -> Self {
        Self {
            name,
            align: None,
            binding: Binding::Global,
            visibility: Visibility::Default,
            cfi: Vec::new(),
            patch: None,
            insts: Vec::new(),
            inst_layout: Vec::new(),
            inst_spans: Vec::new(),
            blocks: Vec::new(),
            operands: Vec::new(),
            imms: Vec::new(),
            amodes: Vec::new(),
            vregs: Vec::new(),
            first_block: None,
            last_block: None,
        }
    }

    // Registers.

    /// A virtual register of that class, which nothing has defined yet.
    ///
    /// # Panics
    ///
    /// Panics if the function already has two billion of them, which no function does.
    pub fn new_vreg(&mut self, class: RegClass) -> Reg {
        let number = u32::try_from(self.vregs.len()).expect("too many virtual registers");
        self.vregs.push(class);
        Reg::virtual_reg(number)
    }

    /// How many virtual registers the function has, which is what the allocator sizes itself
    /// against.
    #[must_use]
    pub fn vregs(&self) -> usize {
        self.vregs.len()
    }

    /// The class of a virtual register, or `None` for a physical one or a number this function
    /// never handed out.
    #[must_use]
    pub fn class_of(&self, reg: Reg) -> Option<RegClass> {
        self.vregs.get(usize::try_from(reg.number()?).ok()?).copied()
    }

    // Blocks.

    /// Creates a block with no parameters and nothing in it, at the end of the layout.
    pub fn create_block(&mut self) -> Block {
        let block = Idx::from_usize(self.blocks.len());
        self.blocks.push(BlockData { prev: self.last_block, ..BlockData::default() });
        match self.last_block {
            Some(last) => self.blocks[last.index()].next = Some(block),
            None => self.first_block = Some(block),
        }
        self.last_block = Some(block);
        block
    }

    /// The entry block, which is the first in layout order, or `None` before there is one.
    #[must_use]
    pub fn entry(&self) -> Option<Block> {
        self.first_block
    }

    /// How many blocks the function has ever had, which is what a table indexed by block is
    /// sized against. A block taken out of the layout still counts, because it keeps its index.
    #[must_use]
    pub fn block_count(&self) -> usize {
        self.blocks.len()
    }

    /// How many instructions the function has ever had, which is what a table indexed by
    /// instruction is sized against. One taken out of a block still counts, because it keeps its
    /// index.
    #[must_use]
    pub fn inst_count(&self) -> usize {
        self.insts.len()
    }

    /// Its blocks, in layout order, which is the order they are printed and emitted in.
    pub fn blocks(&self) -> impl Iterator<Item = Block> + use<'_> {
        std::iter::successors(self.first_block, |&block| self[block].next)
    }

    /// Puts the blocks in that order, which is the order they are printed and emitted in.
    ///
    /// A block keeps its index, so nothing holding one is invalidated and nothing else in the
    /// function has to be touched: the order is a linked list and this relinks it. That is the
    /// whole reason the list is a list rather than the order the blocks were created in.
    ///
    /// The first block in the order becomes the entry, which is a real decision rather than a
    /// consequence: on this machine a function is entered at its first byte, so the block that
    /// runs first has to be laid out first.
    ///
    /// # Panics
    ///
    /// Panics unless `order` is every block of the function exactly once. A block left out would
    /// be unreachable in a way nothing later could notice, and one named twice would make the
    /// list a loop, so both are worth finding here rather than in the encoder.
    pub fn set_block_order(&mut self, order: &[Block]) {
        assert_eq!(order.len(), self.blocks.len(), "the order is not every block of the function");
        let mut seen = vec![false; self.blocks.len()];
        for &block in order {
            assert!(!seen[block.index()], "the order names a block twice");
            seen[block.index()] = true;
        }
        for (at, &block) in order.iter().enumerate() {
            let data = &mut self.blocks[block.index()];
            data.prev = at.checked_sub(1).map(|before| order[before]);
            data.next = order.get(at + 1).copied();
        }
        self.first_block = order.first().copied();
        self.last_block = order.last().copied();
    }

    /// Adds a parameter of that class to a block, and gives back the virtual register it
    /// arrives as.
    ///
    /// Every predecessor's arm has to grow an argument to match, which is what
    /// [`Func::succs_mut`] is for.
    pub fn append_param(&mut self, block: Block, class: RegClass) -> Reg {
        let reg = self.new_vreg(class);
        self.blocks[block.index()].params.push(Param { reg, class });
        reg
    }

    /// Adds a parameter that is already a particular register, which is what allocation leaves
    /// behind.
    pub fn append_given_param(&mut self, block: Block, param: Param) {
        self.blocks[block.index()].params.push(param);
    }

    /// What arrives in a block, to be read or replaced.
    ///
    /// Allocation is what replaces it: once every parameter is a place and every argument is a
    /// place, an edge is a set of moves and the parameters are what those moves write, so the
    /// block stops asking for anything and the machine IR stops being in SSA form.
    pub fn params_mut(&mut self, block: Block) -> &mut Vec<Param> {
        &mut self.blocks[block.index()].params
    }

    /// Where a block goes, to be read or replaced.
    ///
    /// The arms are in the order the terminator's own arms run, so the first is the arm a
    /// conditional branch takes when its condition holds.
    pub fn succs_mut(&mut self, block: Block) -> &mut Vec<BlockCall> {
        &mut self.blocks[block.index()].succs
    }

    // Instructions.

    /// The instructions of a block, in order.
    pub fn insts(&self, block: Block) -> impl Iterator<Item = Inst> + use<'_> {
        std::iter::successors(self[block].first_inst, |&inst| self.inst_layout[inst.index()].next)
    }

    /// The last instruction of a block, which is its terminator once it has one.
    #[must_use]
    pub fn terminator(&self, block: Block) -> Option<Inst> {
        self[block].last_inst
    }

    /// Which block an instruction is in, or `None` for one that has been taken out of its
    /// block.
    #[must_use]
    pub fn block_of(&self, inst: Inst) -> Option<Block> {
        self.inst_layout[inst.index()].block
    }

    /// Where an instruction came from.
    #[must_use]
    pub fn span(&self, inst: Inst) -> Span {
        self.inst_spans[inst.index()]
    }

    /// Starts an instruction at the end of that block.
    ///
    /// Nothing is added to the function until [`InstBuilder::finish`], so a builder that is
    /// dropped leaves no trace.
    pub fn build(&mut self, block: Block, opcode: Opcode) -> InstBuilder<'_> {
        InstBuilder {
            func: self,
            block: Some(block),
            opcode,
            operands: Vec::new(),
            imm: None,
            mem: None,
            symbol: None,
            span: Span::DUMMY,
        }
    }

    /// Puts an instruction that is in no block at the end of one.
    ///
    /// # Panics
    ///
    /// Panics if the instruction is already in a block, because an instruction in two blocks is
    /// the kind of thing that is found much later and somewhere else.
    pub fn append_inst(&mut self, block: Block, inst: Inst) {
        assert!(self.inst_layout[inst.index()].block.is_none(), "the instruction is in a block");
        let last = self.blocks[block.index()].last_inst;
        self.inst_layout[inst.index()] = InstLayout { block: Some(block), prev: last, next: None };
        match last {
            Some(last) => self.inst_layout[last.index()].next = Some(inst),
            None => self.blocks[block.index()].first_inst = Some(inst),
        }
        self.blocks[block.index()].last_inst = Some(inst);
    }

    /// Puts an instruction that is in no block immediately after another one.
    ///
    /// # Panics
    ///
    /// Panics if the instruction is already in a block, or if the one it is to follow is in
    /// none.
    pub fn insert_after(&mut self, after: Inst, inst: Inst) {
        assert!(self.inst_layout[inst.index()].block.is_none(), "the instruction is in a block");
        let layout = self.inst_layout[after.index()];
        let block = layout.block.expect("the instruction to insert after is in no block");
        self.inst_layout[inst.index()] =
            InstLayout { block: Some(block), prev: Some(after), next: layout.next };
        self.inst_layout[after.index()].next = Some(inst);
        match layout.next {
            Some(next) => self.inst_layout[next.index()].prev = Some(inst),
            None => self.blocks[block.index()].last_inst = Some(inst),
        }
    }

    /// Starts an instruction that will be in no block until something puts it in one.
    ///
    /// This is what a pass that inserts rather than appends builds with, and it hands the
    /// instruction to [`Func::prepend_inst`], [`Func::insert_before`] or [`Func::insert_after`].
    /// Everything else about it is the same, which is the point: the operand order is the
    /// builder's invariant wherever the instruction ends up.
    pub fn build_loose(&mut self, opcode: Opcode) -> InstBuilder<'_> {
        InstBuilder {
            func: self,
            block: None,
            opcode,
            operands: Vec::new(),
            imm: None,
            mem: None,
            symbol: None,
            span: Span::DUMMY,
        }
    }

    /// Puts an instruction that is in no block at the start of one, in front of everything in it.
    ///
    /// # Panics
    ///
    /// Panics if the instruction is already in a block.
    pub fn prepend_inst(&mut self, block: Block, inst: Inst) {
        assert!(self.inst_layout[inst.index()].block.is_none(), "the instruction is in a block");
        let first = self.blocks[block.index()].first_inst;
        self.inst_layout[inst.index()] = InstLayout { block: Some(block), prev: None, next: first };
        match first {
            Some(first) => self.inst_layout[first.index()].prev = Some(inst),
            None => self.blocks[block.index()].last_inst = Some(inst),
        }
        self.blocks[block.index()].first_inst = Some(inst);
    }

    /// Puts an instruction that is in no block immediately before another one.
    ///
    /// This is what a reload is: the instruction that wants the value has to see it already
    /// read in, so the load goes in front of it rather than behind whatever came before, which
    /// is the same place only when something came before.
    ///
    /// # Panics
    ///
    /// Panics if the instruction is already in a block, or if the one it is to precede is in
    /// none.
    pub fn insert_before(&mut self, before: Inst, inst: Inst) {
        assert!(self.inst_layout[inst.index()].block.is_none(), "the instruction is in a block");
        let layout = self.inst_layout[before.index()];
        let block = layout.block.expect("the instruction to insert before is in no block");
        self.inst_layout[inst.index()] =
            InstLayout { block: Some(block), prev: layout.prev, next: Some(before) };
        self.inst_layout[before.index()].prev = Some(inst);
        match layout.prev {
            Some(prev) => self.inst_layout[prev.index()].next = Some(inst),
            None => self.blocks[block.index()].first_inst = Some(inst),
        }
    }

    /// Takes an instruction out of its block, leaving it in the function's tables.
    ///
    /// It keeps its index, the way a removed block keeps its number, because renumbering would
    /// invalidate every index anything else was holding.
    pub fn remove_inst(&mut self, inst: Inst) {
        let layout = self.inst_layout[inst.index()];
        let Some(block) = layout.block else { return };
        match layout.prev {
            Some(prev) => self.inst_layout[prev.index()].next = layout.next,
            None => self.blocks[block.index()].first_inst = layout.next,
        }
        match layout.next {
            Some(next) => self.inst_layout[next.index()].prev = layout.prev,
            None => self.blocks[block.index()].last_inst = layout.prev,
        }
        self.inst_layout[inst.index()] = InstLayout::default();
    }

    /// The frame rules that take effect after that instruction, in the order they were written.
    ///
    /// A scan rather than an index, because a prologue is a handful of rows and a function is
    /// walked once by each of the two things that read them. An index would cost more to build
    /// than the scans it saves.
    pub fn cfi_after(&self, inst: Inst) -> impl Iterator<Item = CfiOp> + '_ {
        self.cfi.iter().filter(move |&&(at, _)| at == inst).map(|&(_, op)| op)
    }

    /// The instruction the record stops after, which is the last one in the layout.
    ///
    /// A record covers the function and not the byte after it, so a row attached to this
    /// instruction describes an address nothing can return to and is dropped. What is otherwise
    /// found there is the epilogue of the last block putting back a state no unwinder will read.
    ///
    /// Asked for here rather than worked out by each of the two things that write a record out,
    /// because the two of them writing different tables for one function is exactly what
    /// `spec/11-asm-objects-debug.md` section 11.1 says must not be possible.
    pub fn cfi_end(&self) -> Option<Inst> {
        self.blocks().last().and_then(|block| self.insts(block).last())
    }

    // The tables.

    /// Puts a run of operands in the operand table and gives back the run.
    pub fn push_operands(&mut self, operands: &[Operand]) -> OperandList {
        let start = Idx::from_usize(self.operands.len());
        self.operands.extend_from_slice(operands);
        IdxRange::new(start, Idx::from_usize(self.operands.len()))
    }

    /// Puts an immediate in the immediate table.
    pub fn add_imm(&mut self, value: i64) -> ImmRef {
        self.imms.push(Imm(value));
        Idx::from_usize(self.imms.len() - 1)
    }

    /// Puts an addressing mode in the table of them.
    pub fn add_amode(&mut self, amode: Amode) -> MemRef {
        self.amodes.push(amode);
        Idx::from_usize(self.amodes.len() - 1)
    }

    /// Creates an instruction that is in no block yet.
    pub fn create_inst(&mut self, data: InstData, span: Span) -> Inst {
        self.insts.push(data);
        self.inst_layout.push(InstLayout::default());
        self.inst_spans.push(span);
        Idx::from_usize(self.insts.len() - 1)
    }
}

impl Index<Inst> for Func {
    type Output = InstData;

    fn index(&self, inst: Inst) -> &InstData {
        &self.insts[inst.index()]
    }
}

impl IndexMut<Inst> for Func {
    fn index_mut(&mut self, inst: Inst) -> &mut InstData {
        &mut self.insts[inst.index()]
    }
}

impl Index<Block> for Func {
    type Output = BlockData;

    fn index(&self, block: Block) -> &BlockData {
        &self.blocks[block.index()]
    }
}

impl Index<OperandList> for Func {
    type Output = [Operand];

    fn index(&self, list: OperandList) -> &[Operand] {
        &self.operands[list.as_usize_range()]
    }
}

impl IndexMut<OperandList> for Func {
    fn index_mut(&mut self, list: OperandList) -> &mut [Operand] {
        &mut self.operands[list.as_usize_range()]
    }
}

impl Index<ImmRef> for Func {
    type Output = Imm;

    fn index(&self, at: ImmRef) -> &Imm {
        &self.imms[at.index()]
    }
}

impl Index<MemRef> for Func {
    type Output = Amode;

    fn index(&self, at: MemRef) -> &Amode {
        &self.amodes[at.index()]
    }
}

impl IndexMut<MemRef> for Func {
    fn index_mut(&mut self, at: MemRef) -> &mut Amode {
        &mut self.amodes[at.index()]
    }
}

/// One instruction being built.
///
/// The order the operands are given in is the order they are stored in, and the builder is what
/// insists that order is the one the printer and the parser agree on.
#[derive(Debug)]
pub struct InstBuilder<'a> {
    func: &'a mut Func,
    block: Option<Block>,
    opcode: Opcode,
    operands: Vec<Operand>,
    imm: Option<i64>,
    mem: Option<Amode>,
    symbol: Option<Symbol>,
    span: Span,
}

impl InstBuilder<'_> {
    /// Adds an operand.
    ///
    /// # Panics
    ///
    /// Panics if an operand the instruction writes is given after one it reads, or if either is
    /// given after the memory operand, because both make the instruction print as text that
    /// reads back as a different one.
    #[must_use]
    pub fn operand(mut self, operand: Operand) -> Self {
        assert!(self.mem.is_none(), "the memory operand's registers come last");
        if operand.role.is_def() {
            let reads = self.operands.iter().any(|earlier| !earlier.role.is_def());
            assert!(!reads, "the operands an instruction writes come first");
        }
        self.operands.push(operand);
        self
    }

    /// Adds the operand the instruction writes, in the common case where nothing constrains it.
    #[must_use]
    pub fn def(self, reg: Reg, class: RegClass) -> Self {
        self.operand(Operand::write(reg, class))
    }

    /// Adds an operand the instruction reads, in the common case where nothing constrains it.
    #[must_use]
    pub fn uses(self, reg: Reg, class: RegClass) -> Self {
        self.operand(Operand::read(reg, class))
    }

    /// Gives the instruction a memory operand, whose registers become its last operands.
    ///
    /// # Panics
    ///
    /// Panics if it already has one.
    #[must_use]
    pub fn mem(mut self, mem: Mem) -> Self {
        assert!(self.mem.is_none(), "the instruction already has a memory operand");
        let mut amode = Amode {
            base: None,
            index: None,
            scale: mem.scale.max(1),
            disp: mem.disp,
            symbol: mem.symbol,
            got: mem.got,
            segment: mem.segment,
        };
        if let Some(base) = mem.base {
            amode.base = Some(self.next_operand());
            self.operands.push(base);
        }
        if let Some(index) = mem.index {
            amode.index = Some(self.next_operand());
            self.operands.push(index);
        }
        self.mem = Some(amode);
        self
    }

    /// Gives the instruction an immediate.
    #[must_use]
    pub fn imm(mut self, value: i64) -> Self {
        self.imm = Some(value);
        self
    }

    /// Gives the instruction the symbol it names.
    #[must_use]
    pub fn symbol(mut self, symbol: Symbol) -> Self {
        self.symbol = Some(symbol);
        self
    }

    /// Says where in the source the instruction came from.
    #[must_use]
    pub fn at(mut self, span: Span) -> Self {
        self.span = span;
        self
    }

    /// Puts the instruction at the end of the block it was started in, or in no block at all if
    /// it was started loose.
    pub fn finish(self) -> Inst {
        let InstBuilder { func, block, opcode, operands, imm, mem, symbol, span } = self;
        let data = InstData {
            opcode,
            operands: func.push_operands(&operands),
            imm: imm.map(|value| func.add_imm(value)),
            mem: mem.map(|amode| func.add_amode(amode)),
            symbol,
        };
        let inst = func.create_inst(data, span);
        if let Some(block) = block {
            func.append_inst(block, inst);
        }
        inst
    }

    /// The index the next operand will have, for an addressing mode to point at.
    ///
    /// # Panics
    ///
    /// Panics past 255 operands, which is far more than any instruction of any target we have
    /// and which the index in an addressing mode could not name anyway.
    fn next_operand(&self) -> u8 {
        u8::try_from(self.operands.len()).expect("too many operands on one instruction")
    }
}

/// Whether an operand is one the instruction writes, for a printer or a pass that splits the
/// operand vector at the point the writes stop.
#[must_use]
pub fn defs(operands: &[Operand]) -> usize {
    operands.iter().position(|operand| !operand.role.is_def()).unwrap_or(operands.len())
}

#[cfg(test)]
mod tests {
    use rucc_base::Interner;

    use super::*;

    fn class() -> RegClass {
        RegClass::new(0)
    }

    #[test]
    fn the_blocks_can_be_put_in_another_order_and_keep_everything_in_them() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let opcode = Opcode::new(names.intern("x64.nop"));
        let blocks: Vec<Block> = (0..4).map(|_| func.create_block()).collect();
        let marker = func.build(blocks[3], opcode).finish();

        func.set_block_order(&[blocks[0], blocks[3], blocks[1], blocks[2]]);
        assert_eq!(
            func.blocks().collect::<Vec<_>>(),
            vec![blocks[0], blocks[3], blocks[1], blocks[2]]
        );
        assert_eq!(func.entry(), Some(blocks[0]));
        // A block keeps its index, so what was in it is still in it and an instruction still
        // knows which block it is in. That is the whole point of relinking rather than moving.
        assert_eq!(func.block_of(marker), Some(blocks[3]));
        assert_eq!(func.insts(blocks[3]).collect::<Vec<_>>(), vec![marker]);

        // And backwards, since the list is doubly linked and a pass may walk it either way.
        func.set_block_order(&[blocks[2], blocks[1], blocks[0], blocks[3]]);
        assert_eq!(func.entry(), Some(blocks[2]));
        let mut back = Vec::new();
        let mut at = Some(blocks[3]);
        while let Some(block) = at {
            back.push(block);
            at = func[block].prev;
        }
        assert_eq!(back, vec![blocks[3], blocks[0], blocks[1], blocks[2]]);
    }

    #[test]
    #[should_panic(expected = "the order names a block twice")]
    fn an_order_that_names_a_block_twice_is_refused_rather_than_made_into_a_loop() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let first = func.create_block();
        let _second = func.create_block();
        func.set_block_order(&[first, first]);
    }

    #[test]
    #[should_panic(expected = "the order is not every block of the function")]
    fn an_order_that_leaves_a_block_out_is_refused() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let first = func.create_block();
        let _second = func.create_block();
        func.set_block_order(&[first]);
    }

    #[test]
    fn instructions_come_back_in_the_order_they_were_built() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let opcode = Opcode::new(names.intern("x64.nop"));
        let first = func.build(block, opcode).finish();
        let second = func.build(block, opcode).finish();
        assert_eq!(func.insts(block).collect::<Vec<_>>(), vec![first, second]);
        assert_eq!(func.terminator(block), Some(second));
        assert_eq!(func.block_of(first), Some(block));
    }

    #[test]
    fn a_removed_instruction_is_in_no_block_and_the_rest_still_link_up() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let opcode = Opcode::new(names.intern("x64.nop"));
        let first = func.build(block, opcode).finish();
        let second = func.build(block, opcode).finish();
        let third = func.build(block, opcode).finish();
        func.remove_inst(second);
        assert_eq!(func.insts(block).collect::<Vec<_>>(), vec![first, third]);
        assert_eq!(func.block_of(second), None);
    }

    #[test]
    fn an_instruction_can_be_put_back_between_two_others() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let opcode = Opcode::new(names.intern("x64.nop"));
        let first = func.build(block, opcode).finish();
        let last = func.build(block, opcode).finish();
        let spill = func.create_inst(InstData::new(opcode), Span::DUMMY);
        func.insert_after(first, spill);
        assert_eq!(func.insts(block).collect::<Vec<_>>(), vec![first, spill, last]);
        assert_eq!(func.terminator(block), Some(last));
    }

    #[test]
    fn an_instruction_can_be_put_in_front_of_the_first_one_in_a_block() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let opcode = Opcode::new(names.intern("x64.nop"));
        let first = func.build(block, opcode).finish();
        let last = func.build(block, opcode).finish();
        let reload = func.create_inst(InstData::new(opcode), Span::DUMMY);
        let prologue = func.create_inst(InstData::new(opcode), Span::DUMMY);
        func.insert_before(last, reload);
        func.prepend_inst(block, prologue);
        assert_eq!(func.insts(block).collect::<Vec<_>>(), vec![prologue, first, reload, last]);
        assert_eq!(func.terminator(block), Some(last));
        assert_eq!(func.block_of(prologue), Some(block));
    }

    #[test]
    fn the_first_instruction_in_an_empty_block_is_also_its_last() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let opcode = Opcode::new(names.intern("x64.ret"));
        let only = func.create_inst(InstData::new(opcode), Span::DUMMY);
        func.prepend_inst(block, only);
        assert_eq!(func.insts(block).collect::<Vec<_>>(), vec![only]);
        assert_eq!(func.terminator(block), Some(only));
    }

    #[test]
    fn a_memory_operand_names_the_operands_holding_its_registers() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let base = func.new_vreg(class());
        let index = func.new_vreg(class());
        let dest = func.new_vreg(class());
        let inst = func
            .build(block, Opcode::new(names.intern("x64.lea")))
            .def(dest, class())
            .mem(
                Mem::at(Operand::read(base, class()))
                    .indexed(Operand::read(index, class()), 4)
                    .plus(16),
            )
            .finish();
        let data = func[inst];
        let amode = func[data.mem.expect("it was given a memory operand")];
        assert_eq!(amode.base, Some(1));
        assert_eq!(amode.index, Some(2));
        assert_eq!(amode.scale, 4);
        assert_eq!(amode.disp, 16);
        assert_eq!(func[data.operands][1].reg, base);
        assert_eq!(defs(&func[data.operands]), 1);
    }

    #[test]
    #[should_panic(expected = "the operands an instruction writes come first")]
    fn a_def_after_a_use_is_refused() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let reg = func.new_vreg(class());
        let _ = func
            .build(block, Opcode::new(names.intern("x64.add")))
            .uses(reg, class())
            .def(reg, class());
    }

    #[test]
    fn a_block_parameter_is_a_virtual_register_of_its_class() {
        let mut names = Interner::new();
        let mut func = Func::new(names.intern("f"));
        let block = func.create_block();
        let param = func.append_param(block, class());
        assert_eq!(func[block].params, vec![Param { reg: param, class: class() }]);
        assert_eq!(func.class_of(param), Some(class()));
        assert_eq!(func.vregs(), 1);
        assert_eq!(func.entry(), Some(block));
    }
}