rucc_ir/

inst.rs

//! What one instruction is, and what a value is.
//!
//! Design: `spec/08-ir.md` sections 8.1 and 8.3.
//!
//! An instruction is an [`Opcode`], a set of [`Flags`], a run of value operands, and whatever
//! else that opcode needs, which is [`Extra`]. Everything that fits in eight bytes is in the
//! [`Extra`] itself and everything larger is an index into a side table, so the instruction
//! stays small enough that walking a function is walking one dense array.
//!
//! A value is the result of an instruction or a parameter of a block, and it is nothing else.
//! There is no constant operand kind: a constant is an [`Opcode::IConst`] with a result like
//! any other instruction. That is what makes the dominance rule in the verifier a single rule
//! with no exceptions, and it costs nothing, because a constant with no uses is deleted by the
//! same pass that deletes anything else with no uses.

use rucc_base::{Idx, IdxRange, Symbol};

use rucc_target::Slot;

use crate::{
    ExtraKind, Flags, FloatPred, IntPred, MemOrder, Opcode, Owner, PrefetchHint, RmwOp,
    StorageClass, Type,
};

/// One value: the result of an instruction, or a parameter of a block.
pub type Value = Idx<ValueData>;
/// One instruction, in the function that owns it.
pub type Inst = Idx<InstData>;
/// One basic block, in the function that owns it.
pub type Block = Idx<BlockData>;

/// The table of references to values, which is what an operand list is a run of.
#[derive(Debug)]
pub struct ValueRef;
/// A run of value operands.
pub type ValueList = IdxRange<ValueRef>;
/// A run of branch targets, which is what a terminator's successors are.
pub type BlockCallList = IdxRange<BlockCall>;
/// A run of immediates, which is what a `switch` holds its case values in.
pub type ImmList = IdxRange<Imm>;
/// A run of ABI attributes, which is what a call says about the arguments its signature does
/// not name.
pub type AbiList = IdxRange<Abi>;
/// A run of eightbytes, which is how an object read off a variable argument list travelled.
pub type SlotList = IdxRange<Slot>;

/// A constant, in the immediate table.
///
/// The bits and nothing else. An integer is stored two's complement in as many of the low bits
/// as its type is wide, and a floating point value is stored as its bit pattern, so the same
/// table holds both and the type on the result says how to read it. That keeps a bit-preserving
/// answer for a NaN payload, which a value of a Rust floating type would not.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Imm(u128);

impl Imm {
    /// The bits, as they are stored.
    #[must_use]
    pub const fn bits(self) -> u128 {
        self.0
    }

    /// An immediate holding these bits.
    #[must_use]
    pub const fn from_bits(bits: u128) -> Self {
        Self(bits)
    }

    /// An integer, with the bits above `ty` cleared.
    ///
    /// A value is stored in exactly the width its type has, so two immediates are equal when
    /// they are the same value, which is what lets an equality on the table stand in for an
    /// equality on the numbers.
    ///
    /// # Panics
    ///
    /// Panics if `ty` is not an integer type.
    #[must_use]
    pub fn int(value: i128, ty: Type) -> Self {
        assert!(ty.is_int(), "an integer immediate needs an integer type");
        Self(value as u128 & mask(ty.bits()))
    }

    /// The value read as unsigned.
    #[must_use]
    pub const fn unsigned(self) -> u128 {
        self.0
    }

    /// The value read as signed, with the sign bit of `ty` extended.
    ///
    /// # Panics
    ///
    /// Panics if `ty` is not an integer type.
    #[must_use]
    pub fn signed(self, ty: Type) -> i128 {
        assert!(ty.is_int(), "an integer immediate needs an integer type");
        let spare = 128 - ty.bits();
        // Shifting left and then arithmetic right is the branch-free way to sign extend from
        // an arbitrary width, and it is correct for a width of 128 because the shift is zero.
        ((self.0 << spare) as i128) >> spare
    }
}

/// The low `bits` bits set, and a width of 128 meaning all of them.
fn mask(bits: u32) -> u128 {
    if bits >= 128 { u128::MAX } else { (1u128 << bits) - 1 }
}

/// How often an arm of a branch is the one taken, where something knows.
///
/// Parts out of [`Hint::SCALE`], and nothing at all for an arm nobody has said anything about,
/// which is almost every arm of almost every branch. A hint is what somebody claimed and not what
/// a heuristic guessed: `__builtin_expect` writes one, a profile will write one, and the ten
/// static predictors in `rucc_opt::predict` write none, because a guess that was written down
/// would be indistinguishable afterwards from a fact.
///
/// The scale is ten thousandths because that is the scale `rucc_opt::Probability` and
/// `rucc_mir::Weight` are in, and a number that changed scale on its way through the compiler is a
/// number somebody will eventually divide twice.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Hint(Option<u16>);

impl Hint {
    /// What a hint is out of.
    pub const SCALE: u32 = 10_000;

    /// Nothing said about this arm, which is what every arm starts as.
    pub const NONE: Self = Self(None);

    /// This arm is taken `parts` times in [`Hint::SCALE`].
    ///
    /// More than the scale is certainty rather than a mistake worth refusing, because the callers
    /// that can produce one are doing arithmetic whose answer is certainty, so it is clamped.
    #[must_use]
    pub fn parts(parts: u32) -> Self {
        Self(Some(u16::try_from(parts.min(Self::SCALE)).unwrap_or(u16::MAX)))
    }

    /// The number, or nothing where nothing was said.
    #[must_use]
    pub fn taken(self) -> Option<u32> {
        self.0.map(u32::from)
    }

    /// The hint the other arm of a two armed branch carries, so that the two sum to certainty.
    #[must_use]
    pub fn complement(self) -> Self {
        match self.0 {
            Some(parts) => Self::parts(Self::SCALE - u32::from(parts)),
            None => Self::NONE,
        }
    }
}

/// A branch target, and the values passed to it.
///
/// This is the whole reason there are no phi nodes. The arguments are here, in the branch,
/// beside the block they go to, so removing a predecessor is one edit in one place and there
/// is no second list anywhere that has to be kept in step with this one.
///
/// The hint is here for the same reason and not on the instruction: a branch has as many arms as
/// it has block calls, and a weight held anywhere else would be a second list to keep in step with
/// this one.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct BlockCall {
    /// Where control goes.
    pub block: Block,
    /// What is passed, one for each of the block's parameters.
    pub args: ValueList,
    /// How often this arm is the one taken, where something said so.
    pub hint: Hint,
}

impl BlockCall {
    /// An arm going to a block with arguments and nothing said about how often it is taken.
    #[must_use]
    pub const fn new(block: Block, args: ValueList) -> Self {
        Self { block, args, hint: Hint::NONE }
    }

    /// An arm going to a block that takes no arguments.
    #[must_use]
    pub const fn to(block: Block) -> Self {
        Self::new(block, ValueList::EMPTY)
    }
}

/// What defines a value.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Def {
    /// The result of an instruction, at this position among its results.
    Result {
        /// The instruction.
        inst: Inst,
        /// Which of its results this is.
        index: u8,
    },
    /// A parameter of a block, at this position among its parameters.
    Param {
        /// The block.
        block: Block,
        /// Which of its parameters this is.
        index: u32,
    },
}

/// One value.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct ValueData {
    /// Its type.
    pub ty: Type,
    /// Where it comes from.
    pub def: Def,
}

/// The three parts of a bulk memory operation, taken apart so that nothing has to know the order.
///
/// It exists because the length is a number on almost every one of these and a value on a few, and
/// a reader that takes the operands apart itself is a reader that can get the number from the
/// payload without noticing that this one has an operand instead. Asking for this hands back the
/// length either way and there is no shape of it that reads as a length when it is not one.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Bulk {
    /// Where it writes.
    pub to: Value,
    /// What it puts there: the address it reads for a copy, the byte for a fill.
    pub with: Value,
    /// How many bytes, where the program works the count out rather than the compiler.
    ///
    /// `None` is the ordinary one, where the count is [`MemInfo::size`].
    pub length: Option<Value>,
}

/// What an access does beyond naming an address.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct MemInfo {
    /// How many bytes the access covers, for the ones whose size is not their result type.
    ///
    /// A `load` takes its size from the type it produces. An `alloca` and a `memset` do not,
    /// and this is where theirs is.
    ///
    /// Zero on a bulk operation that carries its length as an operand, which is the one shape
    /// where this is not the count. [`Bulk`] is how those are read, and the verifier refuses a
    /// zero here on one that has no operand, so a reader that goes through it cannot mistake the
    /// one for the other.
    pub size: u64,
    /// The alignment the access is known to have, in bytes.
    pub align: u32,
    /// How strongly it is ordered, with [`MemOrder::NotAtomic`] for an ordinary access.
    pub order: MemOrder,
    /// The type-based aliasing node, if the front end knew one.
    pub tbaa: Option<Meta>,
    /// How many bytes of its record this access owns, counting the padding after it.
    ///
    /// Zero for an access that is not a member of a record, and zero when the front end was not
    /// asked to work it out. What it is for is the init plane of
    /// `spec/safe-memory/09-type-init-and-races.md` section 9.3: under `-fsafety-init=nopadding`
    /// a store through a member records the padding after the member as written too, so that a
    /// record filled a member at a time comes out whole and the ordinary reads of it, which are a
    /// `memcmp` or a hash or a `write` of the record, are not refused.
    ///
    /// Only the init plane reads it. A bounds check over these bytes would be asking about bytes
    /// the access does not touch, and a type plane write over them would be saying the padding
    /// holds a value of the member's type, which it does not.
    pub owns: u32,
    /// Which `restrict` scope the access is in and which pointer it went through.
    pub restrict: Restrict,
}

/// Which `restrict` scope an access is in, and which pointer inside that scope it went through.
///
/// Two small numbers, which is the whole of the mechanism. GCC spells them
/// `MR_DEPENDENCE_CLIQUE` and `MR_DEPENDENCE_BASE` at `gcc/tree-ssa-alias.cc:2503` and the rule
/// is one line: same clique and different base means the two accesses cannot touch the same
/// byte, because that is exactly what `restrict` promises. A clique is one scope, numbered as
/// lowering enters it, and a base is one `restrict` pointer declared inside it. Clique zero
/// means nothing is known, which is what every access that is not under a `restrict` gets.
///
/// This is spec 9.4's scope tree rather than a blanket assumption, and it costs four bytes that
/// were padding in [`MemInfo`] already.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Restrict {
    /// The scope, with zero meaning no information.
    pub clique: u16,
    /// The pointer within that scope, which only means anything when the clique is not zero.
    pub base: u16,
}

impl Restrict {
    /// No information, which is what an access outside any `restrict` scope carries.
    pub const NONE: Self = Self { clique: 0, base: 0 };

    /// Whether `restrict` says these two accesses cannot touch the same byte.
    ///
    /// Only accesses. GCC's PR71062 is what happens when this answer is used to fold a
    /// comparison of the two pointers: `restrict` constrains what is read and written through a
    /// pointer and says nothing about what the pointer's value is, so two pointers that may not
    /// be used to reach the same object can still compare equal. A rule that folds `p == q` to
    /// false on the strength of this is wrong.
    #[must_use]
    pub const fn disjoint(self, other: Self) -> bool {
        self.clique != 0 && self.clique == other.clique && self.base != other.base
    }
}

/// A metadata node, in the module's table.
pub type Meta = Idx<MetaNode>;

/// A node of the metadata graph.
///
/// Two kinds share the one table and the one numbering, because both of them are the compiler's
/// interned type universe seen from a different side and a reader chasing a `!3` should not have
/// to know which table it came out of.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum MetaNode {
    /// What aliasing needs: a type, and where it sits in the tree of types.
    Tbaa(TbaaNode),
    /// What the type plane needs: one entry in the vocabulary its bytes are written in.
    Plane(PlaneNode),
}

impl MetaNode {
    /// The aliasing node this is, or `None` when it is a plane entry.
    #[must_use]
    pub const fn tbaa(self) -> Option<TbaaNode> {
        match self {
            Self::Tbaa(node) => Some(node),
            Self::Plane(_) => None,
        }
    }

    /// The plane entry this is, or `None` when it is an aliasing node.
    #[must_use]
    pub const fn plane(self) -> Option<PlaneNode> {
        match self {
            Self::Plane(node) => Some(node),
            Self::Tbaa(_) => None,
        }
    }

    /// The node one level up, which a plane entry never has.
    ///
    /// The tree is the aliasing tree and a plane entry is not in it. A plane entry that names a
    /// type points at a node of that tree, and that is a reference and not a parent: the walk
    /// that answers an aliasing query has no business leaving the tree it is walking.
    #[must_use]
    pub const fn parent(self) -> Option<Meta> {
        match self {
            Self::Tbaa(node) => node.parent,
            Self::Plane(_) => None,
        }
    }

    /// The node it points at, which is the parent of an aliasing node and the type of a plane
    /// entry, and is what has to come earlier in the table than the node itself.
    #[must_use]
    pub const fn points_at(self) -> Option<Meta> {
        match self {
            Self::Tbaa(node) => node.parent,
            Self::Plane(PlaneNode::Type(node)) => Some(node),
            Self::Plane(_) => None,
        }
    }
}

/// A node of the type based aliasing tree.
///
/// The tree this forms is checked by the verifier, since a cycle in it would make the aliasing
/// query that walks it not terminate, and the place to find that out is here and not there.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct TbaaNode {
    /// What this node is called, which is what the printer writes and the parser reads.
    pub name: Symbol,
    /// The node one level up, with the root having none.
    pub parent: Option<Meta>,
    /// The offset within the parent, for a member of a struct type.
    pub offset: u64,
}

/// One entry in the type plane's vocabulary, per `spec/safe-memory/09-type-init-and-races.md`
/// section 9.1.
///
/// The plane maps every byte to one of these, so this is what a `meta_type` writes and what a
/// `check_type` is asking about. Three of the four are the distinguished values that document
/// says the plane has beyond the types themselves, and they are why the plane needs a node kind
/// of its own rather than pointing straight at an aliasing node: there is no aliasing node for
/// "nobody has stored here yet".
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum PlaneNode {
    /// A type, named by the aliasing node that is that type.
    ///
    /// The same node the front end already interned, so the plane's vocabulary is exactly the
    /// compiler's and a report can name a type in the spelling the source used.
    Type(Meta),
    /// Bytes nothing has stored through, or stored from an untyped source.
    ///
    /// Compatible with every access, because storage with no declared type takes its effective
    /// type from the store, which is C's rule and is also the only choice that does not fire at
    /// every boundary with uninstrumented code.
    NoType,
    /// Bytes stored through a character type, which is compatible with every access.
    ///
    /// This is what makes the byte-wise copy idiom work. C 6.5 says a character access is
    /// always permitted and that a store through a character lvalue does not set an effective
    /// type, so the plane says `character` over those bytes and the later read of the field
    /// still passes.
    Character,
    /// Byte `k` of a pointer shaped word.
    ///
    /// A pointer is not one type over its bytes, it is a word whose bytes are only meaningful
    /// together, so reading four bytes out of the middle of one is a different thing from
    /// reading four bytes of an `int` and the plane has to be able to say which byte it is.
    PointerSlot(u8),
}

/// What a call needs beyond its arguments.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct CallInfo {
    /// The name, for a direct call. `None` for a call through an address, where the address is
    /// the first operand.
    pub callee: Option<Symbol>,
    /// The signature it is called with, which is where the ABI attributes are.
    pub signature: Sig,
    /// What the ABI asks of the arguments the signature does not name, one entry for each of
    /// them.
    ///
    /// Only a variadic call has any, because only a variadic call passes an argument no
    /// parameter stands for, and it is empty when every one of them travels as the value in
    /// hand, which is nearly always. A structure the classification puts in the argument area
    /// is the case it exists for: the bytes travel and there is no parameter to hang the
    /// [`Abi::ByVal`] on, so it hangs here instead.
    pub varargs: AbiList,
}

/// A signature, in the function's table.
pub type Sig = Idx<Signature>;

/// What a `switch` needs beyond the value it switches on.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct SwitchInfo {
    /// The targets, with the default first and one for each case after it.
    pub targets: BlockCallList,
    /// The case values, one for each target after the default.
    pub cases: ImmList,
}

/// What an object read off a variable argument list is.
///
/// The access says how many bytes it is and what it is aligned to, which is the whole of what an
/// object the convention put in the caller's argument area needs: it is there, and those two say
/// where the argument behind it starts. An object that travelled in registers is not there at all.
/// It is in the callee's own register save area, in as many places as it has eightbytes, and which
/// register file each of those came from is not something the size and the alignment say. So the
/// slots say it, and they are empty for the object that went in memory.
///
/// The classification is the front end's, because it is the one that still has the type. By the
/// time an instruction reaches a backend the type is a size and an alignment, and the algorithm in
/// section 3.5.7 of the psABI wants more than that.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct VaInfo {
    /// The object, as any other access describes one.
    pub mem: Idx<MemInfo>,
    /// Where each of its eightbytes travelled, or nothing at all for one that travelled whole in
    /// the caller's memory.
    pub slots: SlotList,
}

/// What inline assembly needs.
///
/// The semantics belong to the inline assembly document. What is here is the shape: a
/// template, the constraints, the clobbers, and the successors that make `asm goto` the one
/// instruction whose being a terminator is a property of the instruction and not the opcode.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct AsmInfo {
    /// The template string, as written.
    pub template: Symbol,
    /// The constraint list, as written.
    pub constraints: Symbol,
    /// The clobber list, as written.
    pub clobbers: Symbol,
    /// The labels, which are empty for everything except `asm goto`.
    pub targets: BlockCallList,
}

/// Everything an instruction carries that is not a value operand.
///
/// Anything that fits in eight bytes is here and anything larger is an index into a side
/// table, so that the common instructions, which are the arithmetic ones carrying nothing at
/// all, do not pay for the rare ones.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Extra {
    /// Nothing, which is most instructions.
    None,
    /// A constant, for `iconst`, `fconst` and `splat`.
    Imm(Idx<Imm>),
    /// A name, for `global_addr` and for a target-specific intrinsic.
    Symbol(Symbol),
    /// Which comparison, for `icmp`.
    IntPred(IntPred),
    /// Which comparison, for `fcmp`.
    FloatPred(FloatPred),
    /// An access, for the loads, the stores, the copies and `alloca`.
    Mem(Idx<MemInfo>),
    /// An atomic read-modify-write, which is an access and which operation.
    Rmw(RmwOp, Idx<MemInfo>),
    /// A barrier's ordering, for `fence`.
    Order(MemOrder),
    /// What a `prefetch` is a hint about, which is a read or a write and how much locality.
    Prefetch(PrefetchHint),
    /// How many frames up to walk, for `frame_address` and `return_address`.
    Depth(u32),
    /// Which question an `object_size` asks, from zero to three.
    Question(u8),
    /// The targets of a branch, with the default first for a `switch`.
    Targets(BlockCallList),
    /// A call.
    Call(Idx<CallInfo>),
    /// A `switch`, which is targets and the values that select them.
    Switch(Idx<SwitchInfo>),
    /// Inline assembly.
    Asm(Idx<AsmInfo>),
    /// An object read off a variable argument list, which is an access and how it travelled.
    VaObject(Idx<VaInfo>),
    /// What kind of storage an instance is, for `meta_begin`.
    Class(StorageClass),
    /// Who a range went to, for `meta_transfer`.
    Owner(Owner),
    /// A metadata node, for `meta_type`, which is the one plane write that names a type.
    Node(Meta),
    /// Why an exemption was declared, for `safe_region_begin`.
    Reason(Symbol),
}

impl Extra {
    /// Which shape this is, without the payload.
    ///
    /// The verifier compares this with [`Opcode::extra_kind`], because an instruction carrying
    /// the payload of some other opcode prints as text the parser cannot read back.
    #[must_use]
    pub const fn kind(self) -> ExtraKind {
        match self {
            Self::None => ExtraKind::None,
            Self::Imm(_) => ExtraKind::Imm,
            Self::Symbol(_) => ExtraKind::Symbol,
            Self::IntPred(_) => ExtraKind::IntPred,
            Self::FloatPred(_) => ExtraKind::FloatPred,
            Self::Mem(_) => ExtraKind::Mem,
            Self::Rmw(..) => ExtraKind::Rmw,
            Self::Order(_) => ExtraKind::Order,
            Self::Prefetch(_) => ExtraKind::Prefetch,
            Self::Depth(_) => ExtraKind::Depth,
            Self::Question(_) => ExtraKind::Question,
            Self::Targets(_) => ExtraKind::Targets,
            Self::Call(_) => ExtraKind::Call,
            Self::Switch(_) => ExtraKind::Switch,
            Self::Asm(_) => ExtraKind::Asm,
            Self::VaObject(_) => ExtraKind::VaObject,
            Self::Class(_) => ExtraKind::Class,
            Self::Owner(_) => ExtraKind::Owner,
            Self::Node(_) => ExtraKind::Node,
            Self::Reason(_) => ExtraKind::Reason,
        }
    }
}

/// One instruction.
///
/// There is no result type here. Each result is a value in the function's value table and the
/// type is on the value, which means a reader asking what an instruction produces asks the
/// same question about `add` as about `call`, and there is no second copy of the type to
/// disagree with the first.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct InstData {
    /// Which instruction this is.
    pub opcode: Opcode,
    /// What the optimizer is licensed to assume about it.
    pub flags: Flags,
    /// How many values it produces.
    pub results: u8,
    /// The first of them, with the rest following it in the value table.
    pub first_result: Option<Value>,
    /// Its value operands.
    pub args: ValueList,
    /// Everything else it carries.
    pub extra: Extra,
}

impl InstData {
    /// An instruction with no operands, no flags, no results and nothing extra.
    #[must_use]
    pub const fn new(opcode: Opcode) -> Self {
        Self {
            opcode,
            flags: Flags::NONE,
            results: 0,
            first_result: None,
            args: ValueList::EMPTY,
            extra: Extra::None,
        }
    }

    /// The values it produces, in order.
    pub fn results(&self) -> impl Iterator<Item = Value> + use<> {
        let first = self.first_result.map_or(0, Idx::raw);
        (0..u32::from(self.results)).map(move |offset| Value::new(first + offset))
    }

    /// The run of targets it branches to, which is empty when it does not branch.
    ///
    /// A `switch` keeps its targets in a side table, so this reads `Extra::Targets` only and
    /// the function is what answers for the rest.
    #[must_use]
    pub fn targets(&self) -> BlockCallList {
        match self.extra {
            Extra::Targets(targets) => targets,
            _ => BlockCallList::EMPTY,
        }
    }
}

/// How one parameter or one return value travels, beyond what its type says.
///
/// The IR's types are the machine's and not C's, so a `ptr` parameter says nothing about
/// whether the pointer is the argument or whether the object it points at is, and an `i8` says
/// nothing about which half of the register above it the callee may read. Both are the ABI's
/// answer rather than the type's, which is why they are here and not on [`Type`].
///
/// A signature carrying one of these has already had the ABI applied to it. What the walk to
/// the IR builds first is the C-level form, where every parameter is [`Abi::Plain`], and the
/// classification in `rucc-target` is what turns one into the other.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
pub enum Abi {
    /// The value itself, in the type it is written as.
    #[default]
    Plain,
    /// An integer narrower than a register, with the bits above it its own sign.
    ///
    /// Which of these an ABI asks for is not a property of the value: `unsigned char` is
    /// [`Abi::Sext`] on the Darwin ABIs and [`Abi::Zext`] elsewhere, and on SysV neither the
    /// caller nor the callee may assume anything about those bits at all.
    Sext,
    /// An integer narrower than a register, with zeroes above it.
    Zext,
    /// The bytes of the object the pointer points at, in the argument area, with no address
    /// travelling anywhere.
    ///
    /// The caller makes the copy the callee is free to write to, which is what makes this a C
    /// call by value rather than a pointer the callee must not keep.
    ByVal {
        /// How many bytes travel.
        size: u64,
        /// What the copy is aligned to, which is the C alignment of the type and not the
        /// pointer's.
        align: u32,
    },
    /// Somewhere for the return value to go, whose address the caller passes as the first
    /// argument because the value does not fit in the registers a return comes back in.
    Sret {
        /// How many bytes the callee writes.
        size: u64,
        /// What the space is aligned to.
        align: u32,
    },
}

impl Abi {
    /// Whether this describes an object behind a pointer rather than the value in hand.
    #[must_use]
    pub const fn indirect(self) -> bool {
        matches!(self, Self::ByVal { .. } | Self::Sret { .. })
    }

    /// The size and alignment of that object, for the two that have one.
    #[must_use]
    pub const fn object(self) -> Option<(u64, u32)> {
        match self {
            Self::ByVal { size, align } | Self::Sret { size, align } => Some((size, align)),
            _ => None,
        }
    }
}

/// One parameter, or one return value: a type and how it travels.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Param {
    /// The type the IR sees, which for the indirect forms is `ptr`.
    pub ty: Type,
    /// What the ABI asks of it.
    pub abi: Abi,
}

impl Param {
    /// A parameter of this type, in its C-level form.
    #[must_use]
    pub const fn new(ty: Type) -> Self {
        Self { ty, abi: Abi::Plain }
    }

    /// A parameter of this type travelling this way.
    #[must_use]
    pub const fn with_abi(ty: Type, abi: Abi) -> Self {
        Self { ty, abi }
    }
}

/// What a function takes and returns.
///
/// A signature is not a type. Nothing in the IR has a function type, because a `ptr` has no
/// pointee and there is nothing else a function type could sit on. A `call_indirect` names the
/// signature it is called with, and that is where the ABI attributes are read from.
#[derive(Clone, Debug, PartialEq, Eq, Default)]
pub struct Signature {
    /// What it takes, in their C-level form until the ABI has been applied.
    pub params: Vec<Param>,
    /// What it returns, which is empty for a `void` function and for one whose return value
    /// comes back through an [`Abi::Sret`] parameter.
    pub returns: Vec<Param>,
    /// Whether it takes arguments beyond the ones named.
    pub variadic: bool,
}

impl Signature {
    /// A signature taking and returning nothing.
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// The same signature with these parameters, each in its C-level form.
    #[must_use]
    pub fn with_params(mut self, params: &[Type]) -> Self {
        self.params = params.iter().copied().map(Param::new).collect();
        self
    }

    /// The same signature returning these, each in its C-level form.
    #[must_use]
    pub fn with_returns(mut self, returns: &[Type]) -> Self {
        self.returns = returns.iter().copied().map(Param::new).collect();
        self
    }

    /// The same signature with one more parameter, travelling the way the ABI said.
    #[must_use]
    pub fn and_param(mut self, param: Param) -> Self {
        self.params.push(param);
        self
    }

    /// The same signature with one more return value, travelling the way the ABI said.
    #[must_use]
    pub fn and_return(mut self, param: Param) -> Self {
        self.returns.push(param);
        self
    }

    /// The types it takes, without what the ABI asks of them.
    pub fn param_types(&self) -> impl Iterator<Item = Type> + use<'_> {
        self.params.iter().map(|param| param.ty)
    }

    /// The types it returns.
    pub fn return_types(&self) -> impl Iterator<Item = Type> + use<'_> {
        self.returns.iter().map(|param| param.ty)
    }

    /// The same signature, variadic.
    #[must_use]
    pub fn variadic(mut self) -> Self {
        self.variadic = true;
        self
    }
}

/// One basic block: parameters, then instructions, then exactly one terminator.
///
/// The instructions are a doubly linked list rather than a vector, so that inserting one in
/// the middle of a block does not move the ones after it. An optimizer does that constantly,
/// and a move would invalidate every [`Inst`] anybody was holding.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct BlockData {
    /// The values arriving here, which is what other IRs spell as phi nodes.
    ///
    /// A `Vec` and not a run in a pool, because SSA construction adds a parameter to a loop
    /// header long after the blocks that come after it have been built, and a run in a pool
    /// cannot grow in the middle.
    pub params: Vec<Value>,
    /// The first instruction, or `None` for a block nothing has been put in yet.
    pub first: Option<Inst>,
    /// The last instruction, which is the terminator once the block is finished.
    pub last: Option<Inst>,
    /// The block before this one in layout order.
    pub prev: Option<Block>,
    /// The block after it.
    pub next: Option<Block>,
}

/// Where one instruction sits.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct InstLayout {
    /// The block it is in, or `None` if it has been made and not yet inserted.
    pub block: Option<Block>,
    /// The instruction before it in that block.
    pub prev: Option<Inst>,
    /// The instruction after it.
    pub next: Option<Inst>,
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn an_immediate_keeps_only_the_bits_its_type_has() {
        let byte = Type::int(8);
        assert_eq!(Imm::int(-1, byte).unsigned(), 0xff);
        assert_eq!(Imm::int(-1, byte).signed(byte), -1);
        assert_eq!(Imm::int(255, byte), Imm::int(-1, byte));
        assert_eq!(Imm::int(127, byte).signed(byte), 127);
        assert_eq!(Imm::int(128, byte).signed(byte), -128);
    }

    #[test]
    fn a_widest_immediate_is_not_truncated() {
        let word = Type::int(128);
        assert_eq!(Imm::int(i128::MIN, word).signed(word), i128::MIN);
        assert_eq!(Imm::int(i128::MAX, word).signed(word), i128::MAX);
        assert_eq!(Imm::int(-1, word).unsigned(), u128::MAX);
    }

    #[test]
    fn a_one_bit_immediate_is_a_bit() {
        let bit = Type::I1;
        assert_eq!(Imm::int(1, bit).unsigned(), 1);
        assert_eq!(Imm::int(3, bit).unsigned(), 1);
        assert_eq!(Imm::int(2, bit).unsigned(), 0);
        // The one bit is the sign bit, so the only two values are zero and minus one.
        assert_eq!(Imm::int(1, bit).signed(bit), -1);
    }

    #[test]
    fn a_floating_immediate_keeps_its_bits() {
        let bits = f64::NAN.to_bits() | 0x7;
        assert_eq!(Imm::from_bits(u128::from(bits)).bits(), u128::from(bits));
    }

    #[test]
    fn an_instruction_with_no_results_yields_none() {
        let inst = InstData::new(Opcode::Store);
        assert_eq!(inst.results().count(), 0);
    }

    #[test]
    fn results_follow_the_first_one() {
        let mut inst = InstData::new(Opcode::SAddOverflow);
        inst.first_result = Some(Value::new(4));
        inst.results = 2;
        let got: Vec<u32> = inst.results().map(Idx::raw).collect();
        assert_eq!(got, [4, 5]);
    }

    #[test]
    fn a_jump_says_where_it_goes() {
        let mut inst = InstData::new(Opcode::Jump);
        inst.extra = Extra::Targets(BlockCallList::new(Idx::new(0), Idx::new(1)));
        assert_eq!(inst.targets().len(), 1);
    }

    #[test]
    fn a_signature_is_built_by_saying_what_it_takes_and_returns() {
        let sig = Signature::new()
            .with_params(&[Type::int(32), Type::PTR])
            .with_returns(&[Type::int(32)])
            .variadic();
        assert_eq!(sig.param_types().collect::<Vec<_>>(), [Type::int(32), Type::PTR]);
        assert_eq!(sig.return_types().collect::<Vec<_>>(), [Type::int(32)]);
        assert!(sig.variadic);
        assert_eq!(Signature::new(), Signature::default());
    }

    #[test]
    fn a_parameter_says_how_it_travels_and_not_only_what_it_is() {
        let object = Abi::ByVal { size: 24, align: 8 };
        let sig = Signature::new()
            .and_param(Param::with_abi(Type::PTR, Abi::Sret { size: 32, align: 16 }))
            .and_param(Param::with_abi(Type::PTR, object))
            .and_param(Param::with_abi(Type::int(8), Abi::Zext));
        // The types alone say `ptr, ptr, i8`, which is three of the calls in any C program and
        // none of them the same call.
        assert_eq!(sig.param_types().collect::<Vec<_>>(), [Type::PTR, Type::PTR, Type::int(8)]);
        assert_eq!(sig.params[1].abi.object(), Some((24, 8)));
        assert!(sig.params[0].abi.indirect() && !sig.params[2].abi.indirect());
        assert_eq!(Param::new(Type::PTR).abi, Abi::Plain);
        assert_eq!(Abi::Plain.object(), None);
    }

    #[test]
    fn an_instruction_stays_small() {
        // Not a promise, a tripwire. Every function in the program is a run of these, and a
        // change that doubles this should be a change somebody decided to make.
        assert!(size_of::<InstData>() <= 32, "{}", size_of::<InstData>());
        assert_eq!(size_of::<ValueData>(), 16);
        assert_eq!(size_of::<Extra>(), 12);
    }
}