celox-backend-x86 0.3.1

//! Machine-level IR: word-level SSA with virtual registers.
//!
//! MIR sits between SIR (bit-level) and x86-64 machine code. Instructions
//! operate on word-sized values; bit-level access information is preserved
//! only in [`SpillDesc`] side-tables so the register allocator can make
//! cost-aware spill decisions without knowing about bit layouts.

use std::fmt;

use crate::HashMap;

use crate::RegionedAbsoluteAddr;

// ────────────────────────────────────────────────────────────────
// Uses: fixed-size operand list
// ────────────────────────────────────────────────────────────────

const MAX_USES: usize = 5;

/// Stack-allocated VReg operands for one MIR instruction.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Uses {
    buf: [VReg; MAX_USES],
    len: u8,
}

impl Uses {
    #[inline]
    pub fn none() -> Self {
        Self {
            buf: [VReg(0); MAX_USES],
            len: 0,
        }
    }
    #[inline]
    pub fn from_slice(values: &[VReg]) -> Self {
        assert!(values.len() <= MAX_USES, "MIR operand capacity exceeded");
        let mut result = Self::none();
        result.buf[..values.len()].copy_from_slice(values);
        result.len = values.len() as u8;
        result
    }
    #[inline]
    pub fn one(a: VReg) -> Self {
        Self::from_slice(&[a])
    }
    #[inline]
    pub fn two(a: VReg, b: VReg) -> Self {
        Self::from_slice(&[a, b])
    }
    #[inline]
    pub fn three(a: VReg, b: VReg, c: VReg) -> Self {
        Self::from_slice(&[a, b, c])
    }
    #[inline]
    pub fn four(a: VReg, b: VReg, c: VReg, d: VReg) -> Self {
        Self::from_slice(&[a, b, c, d])
    }
    #[inline]
    pub fn five(a: VReg, b: VReg, c: VReg, d: VReg, e: VReg) -> Self {
        Self::from_slice(&[a, b, c, d, e])
    }
    #[inline]
    pub fn len(&self) -> usize {
        usize::from(self.len)
    }
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }
    #[inline]
    pub fn contains(&self, v: &VReg) -> bool {
        self.iter().any(|value| value == v)
    }
    #[inline]
    pub fn iter(&self) -> std::slice::Iter<'_, VReg> {
        self.buf[..usize::from(self.len)].iter()
    }
    #[inline]
    pub fn as_slice(&self) -> &[VReg] {
        &self.buf[..usize::from(self.len)]
    }
}

impl std::ops::Deref for Uses {
    type Target = [VReg];
    fn deref(&self) -> &[VReg] {
        self.as_slice()
    }
}

impl<'a> IntoIterator for &'a Uses {
    type Item = &'a VReg;
    type IntoIter = std::slice::Iter<'a, VReg>;
    fn into_iter(self) -> Self::IntoIter {
        self.as_slice().iter()
    }
}

impl IntoIterator for Uses {
    type Item = VReg;
    type IntoIter = std::iter::Take<std::array::IntoIter<VReg, MAX_USES>>;

    fn into_iter(self) -> Self::IntoIter {
        self.buf.into_iter().take(usize::from(self.len))
    }
}

// ────────────────────────────────────────────────────────────────
// Virtual register
// ────────────────────────────────────────────────────────────────

/// Virtual register index. Allocated linearly during ISel; the spilling
/// phase may allocate additional VRegs for reload results.
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct VReg(pub u32);

impl fmt::Debug for VReg {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "v{}", self.0)
    }
}
impl fmt::Display for VReg {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "v{}", self.0)
    }
}

/// Virtual 128-bit x86 vector register.
///
/// Vector values deliberately have a namespace and register class separate
/// from scalar [`VReg`]s.  Treating an XMM-resident value as a scalar VReg
/// would make the GPR allocator create pointless copies and spills.
#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct X86VecReg(pub u32);

impl fmt::Debug for X86VecReg {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "xv{}", self.0)
    }
}

impl fmt::Display for X86VecReg {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "xv{}", self.0)
    }
}

/// Index of an immutable u64 constant table owned by an [`MFunction`].
///
/// The emitter materializes table addresses relative to the generated code,
/// so MIR refers to tables by identity rather than embedding host pointers.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct ConstantTableId(pub usize);

impl fmt::Display for ConstantTableId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "table{}", self.0)
    }
}

/// Allocator for virtual registers.
#[derive(Debug, Clone)]
pub struct VRegAllocator {
    next: u32,
}

/// Exhaustion of the dense `u32` VReg namespace.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct VRegAllocError;

impl fmt::Display for VRegAllocError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        formatter.write_str("VReg namespace exhausted")
    }
}

impl std::error::Error for VRegAllocError {}

impl Default for VRegAllocator {
    fn default() -> Self {
        Self::new()
    }
}

impl VRegAllocator {
    pub fn new() -> Self {
        Self { next: 0 }
    }

    pub fn alloc(&mut self) -> VReg {
        self.try_alloc().expect("VReg overflow")
    }

    /// Allocate one VReg without panicking or changing state on exhaustion.
    pub fn try_alloc(&mut self) -> Result<VReg, VRegAllocError> {
        let Some(next) = self.next.checked_add(1) else {
            return Err(VRegAllocError);
        };
        let id = self.next;
        self.next = next;
        Ok(VReg(id))
    }

    /// Total number of allocated VRegs. Used for sizing per-vreg arrays.
    pub fn count(&self) -> u32 {
        self.next
    }

    #[cfg(test)]
    pub(crate) fn set_next_for_test(&mut self, next: u32) {
        self.next = next;
    }
}

// ────────────────────────────────────────────────────────────────
// Spill descriptors
// ────────────────────────────────────────────────────────────────

/// Where a value can be spilled / reloaded from.
#[derive(Debug, Clone)]
pub enum SpillKind {
    /// Value lives in simulation state at a known location.
    /// Reload = load from `[sim_base + byte_offset]` (+ optional shift/mask).
    SimState {
        addr: RegionedAbsoluteAddr,
        bit_offset: usize,
        width_bits: usize,
    },
    /// Alias of a simulation-state-backed value.
    /// Unlike `SimState`, this is intended for backend-internal aliases that
    /// may safely share the same reload home.
    SimStateAlias {
        addr: RegionedAbsoluteAddr,
        bit_offset: usize,
        width_bits: usize,
    },
    /// Intermediate value with no home in simulation state.
    /// Spill to a stack slot.
    Stack,
    /// Constant that can be cheaply rematerialized (mov imm).
    Remat { value: u64 },
}

/// Version identity for one allocator-created packed-state home.
///
/// The identity is distinct from the physical address: two SSA versions may
/// use the same packed word at different points, but a reload is valid only
/// for the exact version which most recently established that home.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub(crate) struct StateHomeId(pub u32);

/// One full machine-accessible packed-state word.  This is allocator metadata
/// over target-relevant 8/16/32/64-bit operations, not an HDL value width.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub(crate) struct PackedStateHome {
    pub id: StateHomeId,
    pub offset: i32,
    pub size: OpSize,
    pub live_on_entry: bool,
}

impl PackedStateHome {
    pub(crate) fn byte_range(self) -> Option<std::ops::Range<i64>> {
        let start = i64::from(self.offset);
        let end = start.checked_add(i64::from(self.size.bytes()))?;
        Some(start..end)
    }
}

/// Semantic subvalue inserted into the machine word produced by a static
/// state-store read-modify-write. This is per-definition provenance for
/// MemorySSA, not a width or type attached to the referenced VReg.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct StateInsertDesc {
    pub value: VReg,
    /// First bit of `value` represented by this stored fragment.  This is a
    /// relation between two machine values, not an HDL width attached to the
    /// VReg.
    pub value_bit_offset: usize,
    /// First bit within the physical word written by the store.
    pub bit_offset: usize,
    pub width_bits: usize,
    /// The fragment alone contains every significant bit of `value` expected
    /// by the legacy single-load reload path.
    pub complete_value: bool,
}

/// Cost information for spilling / reloading a virtual register.
#[derive(Debug, Clone)]
pub struct SpillDesc {
    pub kind: SpillKind,
    /// Estimated cost (in x86-64 instructions) to reload this value.
    pub reload_cost: u8,
    /// Estimated cost to spill. 0 if the value is already in memory
    /// (store-back-only or rematerializable).
    pub spill_cost: u8,
    /// Optional relation established only when this definition is stored.
    pub(crate) state_insert: Option<StateInsertDesc>,
    /// Optional allocator-created physical spill home for this complete
    /// 32/64-bit machine value.  The store is deferred until allocation
    /// actually chooses this home.
    pub(crate) deferred_state_home: Option<PackedStateHome>,
}

impl SpillDesc {
    /// Rematerializable constant (cost 0 to spill, cost 1 to reload).
    pub fn remat(value: u64) -> Self {
        Self {
            kind: SpillKind::Remat { value },
            reload_cost: 1,
            spill_cost: 0,
            state_insert: None,
            deferred_state_home: None,
        }
    }

    /// Value backed by simulation state.
    pub fn sim_state(
        addr: RegionedAbsoluteAddr,
        bit_offset: usize,
        width_bits: usize,
        store_back_only: bool,
    ) -> Self {
        let reload_cost = if bit_offset.is_multiple_of(64) && matches!(width_bits, 8 | 16 | 32 | 64)
        {
            1 // word-aligned: single load
        } else {
            2 // needs shift/mask
        };
        Self {
            kind: SpillKind::SimState {
                addr,
                bit_offset,
                width_bits,
            },
            reload_cost,
            spill_cost: if store_back_only { 0 } else { reload_cost },
            state_insert: None,
            deferred_state_home: None,
        }
    }

    /// Backend-internal alias of a simulation-state-backed value.
    pub fn sim_state_alias(
        addr: RegionedAbsoluteAddr,
        bit_offset: usize,
        width_bits: usize,
        store_back_only: bool,
    ) -> Self {
        let reload_cost = if bit_offset.is_multiple_of(64) && matches!(width_bits, 8 | 16 | 32 | 64)
        {
            1
        } else {
            2
        };
        Self {
            kind: SpillKind::SimStateAlias {
                addr,
                bit_offset,
                width_bits,
            },
            reload_cost,
            spill_cost: if store_back_only { 0 } else { reload_cost },
            state_insert: None,
            deferred_state_home: None,
        }
    }

    /// Copy semantics for a value snapshot created by `Mov`.
    pub fn copy_for_snapshot(&self) -> Self {
        match self.kind {
            SpillKind::Remat { .. } => self.clone(),
            _ => self
                .deferred_state_home
                .map_or_else(Self::transient, |home| {
                    Self::transient().with_deferred_state_home(home)
                }),
        }
    }

    /// Transient value (spill to stack).
    pub fn transient() -> Self {
        Self {
            kind: SpillKind::Stack,
            reload_cost: 2,
            spill_cost: 2,
            state_insert: None,
            deferred_state_home: None,
        }
    }

    pub(crate) fn with_deferred_state_home(mut self, home: PackedStateHome) -> Self {
        self.deferred_state_home = Some(home);
        self
    }

    pub(crate) fn with_state_insert(
        mut self,
        value: VReg,
        bit_offset: usize,
        width_bits: usize,
    ) -> Self {
        self.state_insert = Some(StateInsertDesc {
            value,
            value_bit_offset: 0,
            bit_offset,
            width_bits,
            complete_value: true,
        });
        self
    }

    /// Record one physical fragment of a 32/64-bit machine value committed by
    /// a later static SimState store.
    pub(crate) fn with_state_insert_fragment(
        mut self,
        value: VReg,
        value_bit_offset: usize,
        bit_offset: usize,
        width_bits: usize,
    ) -> Self {
        self.state_insert = Some(StateInsertDesc {
            value,
            value_bit_offset,
            bit_offset,
            width_bits,
            complete_value: false,
        });
        self
    }
}

// ────────────────────────────────────────────────────────────────
// Block identifiers
// ────────────────────────────────────────────────────────────────

#[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct BlockId(pub u32);

impl fmt::Debug for BlockId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "bb{}", self.0)
    }
}
impl fmt::Display for BlockId {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "bb{}", self.0)
    }
}

// ────────────────────────────────────────────────────────────────
// MIR operand sizes
// ────────────────────────────────────────────────────────────────

/// Operand size for memory and ALU operations.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum OpSize {
    S8,
    S16,
    S32,
    S64,
}

impl OpSize {
    pub fn bytes(self) -> u32 {
        match self {
            OpSize::S8 => 1,
            OpSize::S16 => 2,
            OpSize::S32 => 4,
            OpSize::S64 => 8,
        }
    }

    pub fn from_bits(bits: usize) -> Option<Self> {
        match bits {
            8 => Some(OpSize::S8),
            16 => Some(OpSize::S16),
            32 => Some(OpSize::S32),
            64 => Some(OpSize::S64),
            _ => None,
        }
    }
}

// ────────────────────────────────────────────────────────────────
// Base register for memory access
// ────────────────────────────────────────────────────────────────

/// Base pointer for memory operations.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum BaseReg {
    /// Simulation state base pointer (passed as function argument).
    SimState,
    /// Stack frame pointer (RSP-relative).
    StackFrame,
}

/// Closed-open physical-state byte envelope which may be observed or changed
/// by a register-indexed access.
///
/// A read-modify-write may use a wider machine access while preserving bytes
/// outside this envelope. This range describes its semantic memory effect,
/// not every byte touched by that machine access. It is alias-analysis
/// metadata on the memory operation, not a bit width or range type attached to
/// the index VReg. `None` means that the whole base remains the conservative
/// alias set.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct MemoryAliasRange {
    offset: i32,
    byte_len: usize,
}

impl MemoryAliasRange {
    pub fn new(offset: i32, byte_len: usize) -> Option<Self> {
        if byte_len == 0 {
            return None;
        }
        i64::from(offset)
            .checked_add(i64::try_from(byte_len).ok()?)
            .map(|_| Self { offset, byte_len })
    }

    pub fn end(self) -> i64 {
        i64::from(self.offset) + self.byte_len as i64
    }

    pub fn offset(self) -> i32 {
        self.offset
    }

    pub fn byte_len(self) -> usize {
        self.byte_len
    }
}

// ────────────────────────────────────────────────────────────────
// Comparison kinds
// ────────────────────────────────────────────────────────────────

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum CmpKind {
    Eq,
    Ne,
    LtU,
    LtS,
    LeU,
    LeS,
    GtU,
    GtS,
    GeU,
    GeS,
}

/// A condition consumed directly by a machine branch without first
/// materializing a zero/one SSA value.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum BranchPredicate {
    Compare {
        lhs: VReg,
        rhs: VReg,
        kind: CmpKind,
    },
    CompareImm {
        lhs: VReg,
        imm: i32,
        kind: CmpKind,
    },
    MemoryNonZero {
        base: BaseReg,
        offset: i32,
        size: OpSize,
    },
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum PackedLaneCompareRhs {
    Scalar(VReg),
    Memory {
        offset: i32,
        alias_range: Option<MemoryAliasRange>,
    },
}

/// One immutable row consumed by the sparse-region worklist commit loop.
/// Rows are stored as eight u64 values in a function-local constant table.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SparseCommitDescriptor {
    pub src_offset: u64,
    pub dst_offset: u64,
    pub byte_size: u64,
    pub dirty_words_offset: u64,
    pub dirty_word_count: u64,
    pub summary_words_offset: u64,
    pub summary_word_count: u64,
    pub four_state: u64,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86SimdBinaryOp {
    And,
    Or,
    Xor,
}

impl SparseCommitDescriptor {
    pub const WORDS: usize = 8;

    pub fn words(self) -> [u64; Self::WORDS] {
        [
            self.src_offset,
            self.dst_offset,
            self.byte_size,
            self.dirty_words_offset,
            self.dirty_word_count,
            self.summary_words_offset,
            self.summary_word_count,
            self.four_state,
        ]
    }
}

/// Target-owned SIMD operations selected from scalar MIR.
///
/// These are executable x86 recipes, not architecture-neutral vector
/// semantics. Scalar MIR remains the semantic fallback when a pack is not
/// legal or profitable for this target.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86SimdInst {
    /// A short-lived vector temporary owned by the following recipe.
    ///
    /// This is a virtual value rather than a fixed physical register so the
    /// vector allocator can keep it disjoint from the recipe's live inputs.
    Scratch128 { dst: X86VecReg },
    /// `dst = <0, 0>`, emitted with a dependency-breaking x86 zero idiom.
    Zero128 { dst: X86VecReg },
    /// `dst = <low, high>`, with each scalar becoming one 64-bit lane.
    Pack128 {
        dst: X86VecReg,
        low: VReg,
        high: VReg,
        /// Required when `low != high`; defined immediately before this pack.
        scratch: Option<X86VecReg>,
    },
    /// `dst = load 16 bytes [base + offset]`.
    Load128 {
        dst: X86VecReg,
        base: BaseReg,
        offset: i32,
    },
    /// `dst = op(lhs, rhs)` over two independent 64-bit lanes.
    Binary128 {
        op: X86SimdBinaryOp,
        dst: X86VecReg,
        lhs: X86VecReg,
        rhs: X86VecReg,
    },
    /// `store 16 bytes [base + offset] = src`.
    Store128 {
        base: BaseReg,
        offset: i32,
        src: X86VecReg,
    },
}

impl X86SimdInst {
    pub fn def(self) -> Option<X86VecReg> {
        match self {
            Self::Scratch128 { dst }
            | Self::Zero128 { dst }
            | Self::Pack128 { dst, .. }
            | Self::Load128 { dst, .. }
            | Self::Binary128 { dst, .. } => Some(dst),
            Self::Store128 { .. } => None,
        }
    }

    pub fn uses(self) -> [Option<X86VecReg>; 2] {
        match self {
            Self::Scratch128 { .. } | Self::Zero128 { .. } | Self::Load128 { .. } => [None, None],
            Self::Pack128 { scratch, .. } => [scratch, None],
            Self::Binary128 { lhs, rhs, .. } => [Some(lhs), Some(rhs)],
            Self::Store128 { src, .. } => [Some(src), None],
        }
    }
}

// ────────────────────────────────────────────────────────────────
// MIR instructions
// ────────────────────────────────────────────────────────────────

/// Word-level SSA instruction. All operands are virtual registers.
///
/// Instructions use 3-operand form (dst, src1, src2). The emit phase
/// handles x86-64's 2-operand constraint by inserting mov when needed.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MInst {
    /// Explicit target-specific SIMD instruction with its own register class.
    X86Simd(X86SimdInst),

    // ── Data movement ──────────────────────────────────────────
    /// dst = src (full 64-bit word copy)
    Mov { dst: VReg, src: VReg },
    /// `dst = zero_extend(src[31:0])`
    Mov32 { dst: VReg, src: VReg },
    /// dst = immediate
    LoadImm { dst: VReg, value: u64 },
    /// Define an arbitrary machine-register value without emitting code.
    /// The sole purpose is to reserve one explicit temporary for a following
    /// pseudo instruction instead of hiding a post-RA scratch clobber.
    Scratch { dst: VReg },
    /// dst = address of an immutable function-local constant table
    LoadConstantTableAddr { dst: VReg, table: ConstantTableId },

    // ── Memory access (word-level, byte offsets) ───────────────
    /// dst = load [base + offset]
    Load {
        dst: VReg,
        base: BaseReg,
        offset: i32,
        size: OpSize,
    },
    /// store [base + offset] = src
    Store {
        base: BaseReg,
        offset: i32,
        src: VReg,
        size: OpSize,
    },
    /// Non-atomic `memory &= immediate` over simulator-owned direct memory.
    ///
    /// This target operation is selected from an exact load/and/store chain.
    /// `imm` is truncated to the memory access width by construction.
    AndStoreImm {
        base: BaseReg,
        offset: i32,
        size: OpSize,
        imm: u64,
    },
    /// Non-atomic `memory |= immediate` over simulator-owned direct memory.
    OrStoreImm {
        base: BaseReg,
        offset: i32,
        size: OpSize,
        imm: u64,
    },
    /// dst = load [ptr + offset] in the runtime-owned indirect-memory domain.
    /// This domain is disjoint from SimState and StackFrame.
    LoadPtr {
        dst: VReg,
        ptr: VReg,
        offset: i32,
        size: OpSize,
    },
    /// store [ptr + offset] = src in the runtime-owned indirect-memory domain.
    /// This domain is disjoint from SimState and StackFrame.
    StorePtr {
        ptr: VReg,
        offset: i32,
        src: VReg,
        size: OpSize,
    },
    /// release-store [ptr + offset] = src.
    ///
    /// This is used as a publish point for lock-free runtime-event buffers:
    /// payload words are stored normally, then the sequence word is release-stored.
    /// It is not a read-modify-write atomic operation.
    ReleaseStorePtr {
        ptr: VReg,
        offset: i32,
        src: VReg,
        size: OpSize,
    },
    /// dst = load [base + offset + index * scale].
    ///
    /// `scale` is an x86 addressing-mode scale (1, 2, 4, or 8). It is not a
    /// value-width annotation: selecting a scale requires a prior proof that
    /// the corresponding RTL offset computation cannot wrap differently.
    LoadIndexed {
        dst: VReg,
        base: BaseReg,
        offset: i32,
        index: VReg,
        scale: u8,
        size: OpSize,
        /// Conservative physical envelope for every possible indexed read.
        /// `None` means the complete direct-addressed base may be observed.
        alias_range: Option<MemoryAliasRange>,
    },
    /// Compare a byte-addressable lane sequence against either one scalar or a
    /// second identically-shaped lane sequence and return one predicate bit per
    /// lane in the low bits of `dst`.
    ///
    /// The physical element slots are 1, 2, or 4 bytes wide. Keeping this as
    /// one memory-reading MIR operation lets the emitter use packed SIMD
    /// comparisons without first rebuilding the logical packed array.
    PackedLaneCompare {
        dst: VReg,
        rhs: PackedLaneCompareRhs,
        kind: CmpKind,
        offset: i32,
        lane_count: u8,
        element_stride: u8,
        bit_offset: u8,
        field_width: u8,
        alias_range: Option<MemoryAliasRange>,
    },
    /// Compare the byte lanes `(base + 0..15) mod 256` with one scalar byte
    /// and return the sixteen predicate bits in `dst`.
    PackedByteAffineCompare {
        dst: VReg,
        base: VReg,
        rhs: VReg,
        kind: CmpKind,
    },
    /// store [base + offset + index] = src  (register-indexed memory access)
    StoreIndexed {
        base: BaseReg,
        offset: i32,
        index: VReg,
        src: VReg,
        size: OpSize,
        alias_range: Option<MemoryAliasRange>,
    },
    /// [base + offset + index] |= src.
    ///
    /// This is a non-atomic read-modify-write used for simulator-owned
    /// metadata.  Its memory effect is both a read and a write; keeping the
    /// operation explicit avoids extending a loaded metadata value through
    /// the surrounding RTL dataflow graph.
    OrStoreIndexed {
        base: BaseReg,
        offset: i32,
        index: VReg,
        src: VReg,
        size: OpSize,
        alias_range: Option<MemoryAliasRange>,
    },
    /// dst = load [ptr + offset + index] in the runtime-owned indirect-memory
    /// domain, which is disjoint from SimState and StackFrame.
    LoadPtrIndexed {
        dst: VReg,
        ptr: VReg,
        offset: i32,
        index: VReg,
        size: OpSize,
    },
    /// store [ptr + offset + index] = src in the runtime-owned indirect-memory
    /// domain, which is disjoint from SimState and StackFrame.
    StorePtrIndexed {
        ptr: VReg,
        offset: i32,
        index: VReg,
        src: VReg,
        size: OpSize,
    },
    /// release-store [ptr + offset + index] = src.
    ///
    /// This is used as a publish point for lock-free runtime-event buffers:
    /// payload words are stored normally, then the sequence word is release-stored.
    /// It is not a read-modify-write atomic operation.
    ReleaseStorePtrIndexed {
        ptr: VReg,
        offset: i32,
        index: VReg,
        src: VReg,
        size: OpSize,
    },
    MemCopy {
        src_offset: i32,
        dst_offset: i32,
        byte_len: usize,
    },
    /// Fill a contiguous simulator-state byte range with one byte value.
    ///
    /// This remains one MIR memory operation so reset/bulk initialization does
    /// not create one register-allocation node per logical array element.
    MemFill {
        dst_offset: i32,
        byte_len: usize,
        value: u8,
    },
    /// Commit dirty chunks from a sparse FF next-state region.  This is kept
    /// as one MIR memory barrier and expanded to a bitmap-scanning machine-code
    /// loop by the emitter.
    SparseCommit {
        src_offset: i32,
        dst_offset: i32,
        byte_size: usize,
        dirty_words_offset: i32,
        dirty_word_count: usize,
        summary_words_offset: i32,
        summary_word_count: usize,
        four_state: bool,
    },
    /// Mark one sparse region active in the event-local bitmap. Repeated marks
    /// are naturally idempotent and need no temporary register.
    SparseMarkActive {
        active_index: u32,
        active_bits_offset: i32,
        active_capacity: usize,
    },
    /// Drain the sparse active bitmap and commit dirty chunks through one
    /// shared generated loop. Descriptor rows are indexed by active_index.
    SparseCommitWorklist {
        descriptor_table: ConstantTableId,
        active_bits_offset: i32,
        active_capacity: usize,
    },

    // ── ALU (3-operand SSA) ────────────────────────────────────
    /// dst = lhs + rhs modulo 2^64
    Add { dst: VReg, lhs: VReg, rhs: VReg },
    /// `dst = zero_extend((lhs + rhs)[31:0])`
    Add32 { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs - rhs modulo 2^64
    Sub { dst: VReg, lhs: VReg, rhs: VReg },
    /// `dst = zero_extend((lhs - rhs)[31:0])`
    Sub32 { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs * rhs modulo 2^64
    Mul { dst: VReg, lhs: VReg, rhs: VReg },
    /// `dst = zero_extend((lhs * rhs)[31:0])`
    Mul32 { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = upper 64 bits of lhs * rhs (unsigned)
    UMulHi { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs & rhs (full 64-bit word)
    And { dst: VReg, lhs: VReg, rhs: VReg },
    /// `dst = zero_extend((lhs & rhs)[31:0])`
    And32 { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs | rhs (full 64-bit word)
    Or { dst: VReg, lhs: VReg, rhs: VReg },
    /// `dst = zero_extend((lhs | rhs)[31:0])`
    Or32 { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs ^ rhs (full 64-bit word)
    Xor { dst: VReg, lhs: VReg, rhs: VReg },
    /// `dst = zero_extend((lhs ^ rhs)[31:0])`
    Xor32 { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs >> rhs (logical)
    Shr { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs << rhs
    Shl { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs >> rhs (arithmetic)
    Sar { dst: VReg, lhs: VReg, rhs: VReg },

    // ── ALU with immediate ─────────────────────────────────────
    /// dst = src & imm (full 64-bit word)
    AndImm { dst: VReg, src: VReg, imm: u64 },
    /// `dst = zero_extend((src & imm)[31:0])`
    ///
    /// `imm` must fit in u32.
    AndImm32 { dst: VReg, src: VReg, imm: u32 },
    /// dst = src | imm
    OrImm { dst: VReg, src: VReg, imm: u64 },
    /// dst = src >> imm (logical)
    ShrImm { dst: VReg, src: VReg, imm: u8 },
    /// dst = src << imm
    ShlImm { dst: VReg, src: VReg, imm: u8 },
    /// dst = src >> imm (arithmetic)
    SarImm { dst: VReg, src: VReg, imm: u8 },
    /// dst = src + imm
    AddImm { dst: VReg, src: VReg, imm: i32 },
    /// dst = src - imm
    SubImm { dst: VReg, src: VReg, imm: i32 },

    // ── Comparison ─────────────────────────────────────────────
    /// dst = (lhs cmp rhs) ? 1 : 0
    Cmp {
        dst: VReg,
        lhs: VReg,
        rhs: VReg,
        kind: CmpKind,
    },
    /// dst = (lhs cmp imm) ? 1 : 0
    CmpImm {
        dst: VReg,
        lhs: VReg,
        imm: i32,
        kind: CmpKind,
    },

    // ── Division (uses RAX/RDX, handled at emit time) ────────
    /// dst = lhs / rhs (unsigned)
    UDiv { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs % rhs (unsigned)
    URem { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs / rhs (signed, truncating toward zero)
    SDiv { dst: VReg, lhs: VReg, rhs: VReg },
    /// dst = lhs % rhs (signed, with the dividend's sign)
    SRem { dst: VReg, lhs: VReg, rhs: VReg },

    // ── Unary ──────────────────────────────────────────────────
    /// dst = ~src (bitwise NOT)
    BitNot { dst: VReg, src: VReg },
    /// dst = -src (negate)
    Neg { dst: VReg, src: VReg },
    /// dst = popcnt(src) (population count — number of set bits)
    Popcnt { dst: VReg, src: VReg },
    /// dst = bsf(src). The result is unspecified when src == 0.
    ///
    /// This is intended for guarded lowering where the result is consumed only
    /// on a path or select arm that has already proven src != 0.
    Bsf { dst: VReg, src: VReg },
    /// dst = bsr(src). The result is unspecified when src == 0.
    ///
    /// This is intended for guarded lowering where the result is consumed only
    /// on a path or select arm that has already proven src != 0.
    Bsr { dst: VReg, src: VReg },
    /// dst = src != 0 ? bsr(src) : zero_value.
    ///
    /// This is a defined wrapper around x86 BSR, whose destination is
    /// otherwise undefined when the source is zero.
    BsrOr {
        dst: VReg,
        src: VReg,
        zero_value: u8,
    },
    /// dst = pext(src, mask) — parallel bit extract (BMI2).
    /// Extracts bits from src at positions where mask has 1s,
    /// and packs them contiguously starting at bit 0.
    Pext { dst: VReg, src: VReg, mask: VReg },
    /// dst = pdep(src, mask) — parallel bit deposit (BMI2).
    /// Deposits contiguous low bits from src into positions where mask has 1s.
    Pdep { dst: VReg, src: VReg, mask: VReg },

    // ── Select (for div-by-zero guard, etc.) ───────────────────
    /// dst = cond ? true_val : false_val
    Select {
        dst: VReg,
        cond: VReg,
        true_val: VReg,
        false_val: VReg,
    },
    /// dst = (lhs cmp rhs) ? true_val : false_val
    CmpSelect {
        dst: VReg,
        lhs: VReg,
        rhs: VReg,
        kind: CmpKind,
        true_val: VReg,
        false_val: VReg,
    },
    /// dst = (lhs cmp imm) ? true_val : false_val
    CmpImmSelect {
        dst: VReg,
        lhs: VReg,
        imm: i32,
        kind: CmpKind,
        true_val: VReg,
        false_val: VReg,
    },
    /// dst = (guard != 0 && lhs cmp rhs) ? true_val : false_val
    GuardedCmpSelect {
        dst: VReg,
        guard: VReg,
        lhs: VReg,
        rhs: VReg,
        kind: CmpKind,
        true_val: VReg,
        false_val: VReg,
    },

    // ── Control flow ───────────────────────────────────────────
    /// Conditional branch: if cond != 0 then goto true_bb else goto false_bb
    Branch {
        cond: VReg,
        true_bb: BlockId,
        false_bb: BlockId,
    },
    /// Conditional branch which consumes flags directly. Unlike `Branch`,
    /// this instruction deliberately has no predicate-result VReg.
    BranchPred {
        predicate: BranchPredicate,
        true_bb: BlockId,
        false_bb: BlockId,
    },
    /// Dense full-domain dispatch through signed offsets relative to
    /// `table_base`. The index is proven to be within `targets`.
    JumpTable {
        index: VReg,
        table_base: VReg,
        target: VReg,
        targets: Box<[BlockId]>,
    },
    /// Unconditional jump
    Jump { target: BlockId },
    /// Return from function (success, code 0)
    Return,
    /// Return with error code (non-zero)
    ReturnError { code: i64 },
}

impl fmt::Display for MInst {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            MInst::X86Simd(X86SimdInst::Scratch128 { dst }) => {
                write!(f, "{dst} = x86.scratch.v128")
            }
            MInst::X86Simd(X86SimdInst::Zero128 { dst }) => {
                write!(f, "{dst} = x86.zero.v128")
            }
            MInst::X86Simd(X86SimdInst::Pack128 {
                dst,
                low,
                high,
                scratch,
            }) => {
                write!(
                    f,
                    "{dst} = x86.pack.v2i64 {low}, {high} [scratch={scratch:?}]"
                )
            }
            MInst::X86Simd(X86SimdInst::Load128 { dst, base, offset }) => {
                write!(f, "{dst} = x86.load.v128 [{base} + {offset}]")
            }
            MInst::X86Simd(X86SimdInst::Binary128 { op, dst, lhs, rhs }) => {
                write!(f, "{dst} = x86.{op:?}.v2i64 {lhs}, {rhs}")
            }
            MInst::X86Simd(X86SimdInst::Store128 { base, offset, src }) => {
                write!(f, "x86.store.v128 [{base} + {offset}], {src}")
            }
            MInst::Mov { dst, src } => write!(f, "{dst} = mov.w64 {src}"),
            MInst::Mov32 { dst, src } => write!(f, "{dst} = mov.w32 {src}"),
            MInst::LoadImm { dst, value } => write!(f, "{dst} = imm {value:#x}"),
            MInst::Scratch { dst } => write!(f, "{dst} = scratch"),
            MInst::LoadConstantTableAddr { dst, table } => {
                write!(f, "{dst} = constant_table_addr {table}")
            }
            MInst::Load {
                dst,
                base,
                offset,
                size,
            } => write!(f, "{dst} = load.{size} [{base} + {offset}]"),
            MInst::Store {
                base,
                offset,
                src,
                size,
            } => write!(f, "store.{size} [{base} + {offset}], {src}"),
            MInst::AndStoreImm {
                base,
                offset,
                size,
                imm,
            } => write!(f, "and_store.{size} [{base} + {offset}], {imm:#x}"),
            MInst::OrStoreImm {
                base,
                offset,
                size,
                imm,
            } => write!(f, "or_store_imm.{size} [{base} + {offset}], {imm:#x}"),
            MInst::LoadPtr {
                dst,
                ptr,
                offset,
                size,
            } => write!(f, "{dst} = load.{size} [{ptr} + {offset}]"),
            MInst::StorePtr {
                ptr,
                offset,
                src,
                size,
            } => write!(f, "store.{size} [{ptr} + {offset}], {src}"),
            MInst::ReleaseStorePtr {
                ptr,
                offset,
                src,
                size,
            } => write!(f, "release_store.{size} [{ptr} + {offset}], {src}"),
            MInst::LoadIndexed {
                dst,
                base,
                offset,
                index,
                scale,
                size,
                ..
            } => write!(
                f,
                "{dst} = load.{size} [{base} + {offset} + {index}*{scale}]"
            ),
            MInst::PackedLaneCompare {
                dst,
                rhs,
                kind,
                offset,
                lane_count,
                element_stride,
                bit_offset,
                field_width,
                ..
            } => write!(
                f,
                "{dst} = packed_lane_compare.{kind:?} [sim + {offset}], {rhs:?}, lanes={lane_count}, stride={element_stride}, field={bit_offset}:{field_width}"
            ),
            MInst::PackedByteAffineCompare {
                dst,
                base,
                rhs,
                kind,
            } => write!(
                f,
                "{dst} = packed_byte_affine_compare.{kind:?} base={base}, rhs={rhs}, lanes=16"
            ),
            MInst::StoreIndexed {
                base,
                offset,
                index,
                src,
                size,
                alias_range,
            } => {
                write!(f, "store.{size} [{base} + {offset} + {index}], {src}")?;
                if let Some(range) = alias_range {
                    write!(f, " ; aliases [{base} + {}..{})", range.offset, range.end())?;
                }
                Ok(())
            }
            MInst::OrStoreIndexed {
                base,
                offset,
                index,
                src,
                size,
                alias_range,
            } => {
                write!(f, "or_store.{size} [{base} + {offset} + {index}], {src}")?;
                if let Some(range) = alias_range {
                    write!(f, " ; aliases [{base} + {}..{})", range.offset, range.end())?;
                }
                Ok(())
            }
            MInst::LoadPtrIndexed {
                dst,
                ptr,
                offset,
                index,
                size,
            } => write!(f, "{dst} = load.{size} [{ptr} + {offset} + {index}]"),
            MInst::StorePtrIndexed {
                ptr,
                offset,
                index,
                src,
                size,
            } => write!(f, "store.{size} [{ptr} + {offset} + {index}], {src}"),
            MInst::ReleaseStorePtrIndexed {
                ptr,
                offset,
                index,
                src,
                size,
            } => write!(
                f,
                "release_store.{size} [{ptr} + {offset} + {index}], {src}"
            ),
            MInst::MemCopy {
                src_offset,
                dst_offset,
                byte_len,
            } => write!(
                f,
                "memcopy [sim + {dst_offset}], [sim + {src_offset}], {byte_len}"
            ),
            MInst::MemFill {
                dst_offset,
                byte_len,
                value,
            } => write!(f, "memfill [sim + {dst_offset}], {byte_len}, {value:#04x}"),
            MInst::SparseCommit {
                src_offset,
                dst_offset,
                byte_size,
                dirty_word_count,
                summary_word_count,
                four_state,
                ..
            } => write!(
                f,
                "sparse_commit [sim + {dst_offset}], [sim + {src_offset}], bytes={byte_size}, dirty_words={dirty_word_count}, summary_words={summary_word_count}, four_state={four_state}"
            ),
            MInst::SparseMarkActive { active_index, .. } => {
                write!(f, "sparse_mark_active region={active_index}")
            }
            MInst::SparseCommitWorklist {
                descriptor_table,
                active_capacity,
                ..
            } => write!(
                f,
                "sparse_commit_worklist table={descriptor_table}, capacity={active_capacity}"
            ),
            MInst::Add { dst, lhs, rhs } => write!(f, "{dst} = add.w64 {lhs}, {rhs}"),
            MInst::Add32 { dst, lhs, rhs } => write!(f, "{dst} = add.w32 {lhs}, {rhs}"),
            MInst::Sub { dst, lhs, rhs } => write!(f, "{dst} = sub.w64 {lhs}, {rhs}"),
            MInst::Sub32 { dst, lhs, rhs } => write!(f, "{dst} = sub.w32 {lhs}, {rhs}"),
            MInst::Mul { dst, lhs, rhs } => write!(f, "{dst} = mul.w64 {lhs}, {rhs}"),
            MInst::Mul32 { dst, lhs, rhs } => write!(f, "{dst} = mul.w32 {lhs}, {rhs}"),
            MInst::UMulHi { dst, lhs, rhs } => write!(f, "{dst} = umulhi {lhs}, {rhs}"),
            MInst::And { dst, lhs, rhs } => write!(f, "{dst} = and.w64 {lhs}, {rhs}"),
            MInst::And32 { dst, lhs, rhs } => write!(f, "{dst} = and.w32 {lhs}, {rhs}"),
            MInst::Or { dst, lhs, rhs } => write!(f, "{dst} = or.w64 {lhs}, {rhs}"),
            MInst::Or32 { dst, lhs, rhs } => write!(f, "{dst} = or.w32 {lhs}, {rhs}"),
            MInst::Xor { dst, lhs, rhs } => write!(f, "{dst} = xor.w64 {lhs}, {rhs}"),
            MInst::Xor32 { dst, lhs, rhs } => write!(f, "{dst} = xor.w32 {lhs}, {rhs}"),
            MInst::Shr { dst, lhs, rhs } => write!(f, "{dst} = shr {lhs}, {rhs}"),
            MInst::Shl { dst, lhs, rhs } => write!(f, "{dst} = shl {lhs}, {rhs}"),
            MInst::Sar { dst, lhs, rhs } => write!(f, "{dst} = sar {lhs}, {rhs}"),
            MInst::UDiv { dst, lhs, rhs } => write!(f, "{dst} = udiv {lhs}, {rhs}"),
            MInst::URem { dst, lhs, rhs } => write!(f, "{dst} = urem {lhs}, {rhs}"),
            MInst::SDiv { dst, lhs, rhs } => write!(f, "{dst} = sdiv {lhs}, {rhs}"),
            MInst::SRem { dst, lhs, rhs } => write!(f, "{dst} = srem {lhs}, {rhs}"),
            MInst::AndImm { dst, src, imm } => write!(f, "{dst} = and.w64 {src}, {imm:#x}"),
            MInst::AndImm32 { dst, src, imm } => {
                write!(f, "{dst} = and.w32 {src}, {imm:#x}")
            }
            MInst::OrImm { dst, src, imm } => write!(f, "{dst} = or {src}, {imm:#x}"),
            MInst::ShrImm { dst, src, imm } => write!(f, "{dst} = shr {src}, {imm}"),
            MInst::ShlImm { dst, src, imm } => write!(f, "{dst} = shl {src}, {imm}"),
            MInst::SarImm { dst, src, imm } => write!(f, "{dst} = sar {src}, {imm}"),
            MInst::AddImm { dst, src, imm } => write!(f, "{dst} = add {src}, {imm}"),
            MInst::SubImm { dst, src, imm } => write!(f, "{dst} = sub {src}, {imm}"),
            MInst::Cmp {
                dst,
                lhs,
                rhs,
                kind,
            } => write!(f, "{dst} = cmp.{kind:?} {lhs}, {rhs}"),
            MInst::CmpImm {
                dst,
                lhs,
                imm,
                kind,
            } => write!(f, "{dst} = cmp.{kind:?} {lhs}, {imm}"),
            MInst::BitNot { dst, src } => write!(f, "{dst} = not {src}"),
            MInst::Neg { dst, src } => write!(f, "{dst} = neg {src}"),
            MInst::Popcnt { dst, src } => write!(f, "{dst} = popcnt {src}"),
            MInst::Bsf { dst, src } => write!(f, "{dst} = bsf {src}"),
            MInst::Bsr { dst, src } => write!(f, "{dst} = bsr {src}"),
            MInst::BsrOr {
                dst,
                src,
                zero_value,
            } => write!(f, "{dst} = bsr_or {src}, {zero_value}"),
            MInst::Pext { dst, src, mask } => write!(f, "{dst} = pext {src}, {mask}"),
            MInst::Pdep { dst, src, mask } => write!(f, "{dst} = pdep {src}, {mask}"),
            MInst::Select {
                dst,
                cond,
                true_val,
                false_val,
            } => write!(f, "{dst} = select {cond}, {true_val}, {false_val}"),
            MInst::CmpSelect {
                dst,
                lhs,
                rhs,
                kind,
                true_val,
                false_val,
            } => write!(
                f,
                "{dst} = cmp_select cmp.{kind:?} {lhs}, {rhs}, {true_val}, {false_val}"
            ),
            MInst::CmpImmSelect {
                dst,
                lhs,
                imm,
                kind,
                true_val,
                false_val,
            } => write!(
                f,
                "{dst} = cmp_select cmp.{kind:?} {lhs}, {imm}, {true_val}, {false_val}"
            ),
            MInst::GuardedCmpSelect {
                dst,
                guard,
                lhs,
                rhs,
                kind,
                true_val,
                false_val,
            } => write!(
                f,
                "{dst} = guarded_cmp_select {guard}, cmp.{kind:?} {lhs}, {rhs}, {true_val}, {false_val}"
            ),
            MInst::Branch {
                cond,
                true_bb,
                false_bb,
            } => write!(f, "br {cond}, {true_bb}, {false_bb}"),
            MInst::BranchPred {
                predicate,
                true_bb,
                false_bb,
            } => write!(f, "br_pred {predicate:?}, {true_bb}, {false_bb}"),
            MInst::JumpTable { index, targets, .. } => {
                write!(f, "jmp_table {index}, [")?;
                for (position, target) in targets.iter().enumerate() {
                    if position != 0 {
                        write!(f, ", ")?;
                    }
                    write!(f, "{target}")?;
                }
                write!(f, "]")
            }
            MInst::Jump { target } => write!(f, "jmp {target}"),
            MInst::Return => write!(f, "ret"),
            MInst::ReturnError { code } => write!(f, "ret_error {code}"),
        }
    }
}

impl fmt::Display for BaseReg {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            BaseReg::SimState => write!(f, "sim"),
            BaseReg::StackFrame => write!(f, "sp"),
        }
    }
}

impl fmt::Display for OpSize {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            OpSize::S8 => write!(f, "i8"),
            OpSize::S16 => write!(f, "i16"),
            OpSize::S32 => write!(f, "i32"),
            OpSize::S64 => write!(f, "i64"),
        }
    }
}

impl fmt::Display for MFunction {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let block_indices = self
            .blocks
            .iter()
            .enumerate()
            .map(|(index, block)| (block.id, index))
            .collect::<HashMap<_, _>>();
        let order =
            celox_analysis::cfg_order::dominance_order(0usize, 0..self.blocks.len(), |index| {
                self.blocks[index]
                    .successors()
                    .into_iter()
                    .filter_map(|id| block_indices.get(&id).copied())
                    .collect()
            });
        for index in order {
            let block = &self.blocks[index];
            writeln!(f, "{}:", block.id)?;
            for phi in &block.phis {
                let srcs: Vec<String> = phi
                    .sources
                    .iter()
                    .map(|(bid, v)| format!("{bid}: {v}"))
                    .collect();
                writeln!(f, "  {} = phi({})", phi.dst, srcs.join(", "))?;
            }
            for inst in &block.insts {
                writeln!(f, "  {inst}")?;
            }
        }
        Ok(())
    }
}

impl MInst {
    pub fn x86_vec_def(&self) -> Option<X86VecReg> {
        match self {
            Self::X86Simd(inst) => inst.def(),
            _ => None,
        }
    }

    pub fn x86_vec_uses(&self) -> [Option<X86VecReg>; 2] {
        match self {
            Self::X86Simd(inst) => inst.uses(),
            _ => [None, None],
        }
    }

    /// Returns the destination VReg, if any.
    pub fn def(&self) -> Option<VReg> {
        match self {
            MInst::Mov { dst, .. }
            | MInst::Mov32 { dst, .. }
            | MInst::LoadImm { dst, .. }
            | MInst::Scratch { dst }
            | MInst::LoadConstantTableAddr { dst, .. }
            | MInst::Load { dst, .. }
            | MInst::LoadPtr { dst, .. }
            | MInst::LoadIndexed { dst, .. }
            | MInst::PackedLaneCompare { dst, .. }
            | MInst::PackedByteAffineCompare { dst, .. }
            | MInst::LoadPtrIndexed { dst, .. }
            | MInst::Add { dst, .. }
            | MInst::Add32 { dst, .. }
            | MInst::Sub { dst, .. }
            | MInst::Sub32 { dst, .. }
            | MInst::Mul { dst, .. }
            | MInst::Mul32 { dst, .. }
            | MInst::UMulHi { dst, .. }
            | MInst::And { dst, .. }
            | MInst::And32 { dst, .. }
            | MInst::Or { dst, .. }
            | MInst::Or32 { dst, .. }
            | MInst::Xor { dst, .. }
            | MInst::Xor32 { dst, .. }
            | MInst::Shr { dst, .. }
            | MInst::Shl { dst, .. }
            | MInst::Sar { dst, .. }
            | MInst::AndImm { dst, .. }
            | MInst::AndImm32 { dst, .. }
            | MInst::OrImm { dst, .. }
            | MInst::ShrImm { dst, .. }
            | MInst::ShlImm { dst, .. }
            | MInst::SarImm { dst, .. }
            | MInst::AddImm { dst, .. }
            | MInst::SubImm { dst, .. }
            | MInst::Cmp { dst, .. }
            | MInst::CmpImm { dst, .. }
            | MInst::UDiv { dst, .. }
            | MInst::URem { dst, .. }
            | MInst::SDiv { dst, .. }
            | MInst::SRem { dst, .. }
            | MInst::BitNot { dst, .. }
            | MInst::Neg { dst, .. }
            | MInst::Popcnt { dst, .. }
            | MInst::Bsf { dst, .. }
            | MInst::Bsr { dst, .. }
            | MInst::BsrOr { dst, .. }
            | MInst::Pext { dst, .. }
            | MInst::Pdep { dst, .. }
            | MInst::Select { dst, .. }
            | MInst::CmpSelect { dst, .. }
            | MInst::CmpImmSelect { dst, .. }
            | MInst::GuardedCmpSelect { dst, .. } => Some(*dst),

            MInst::Store { .. }
            | MInst::X86Simd(_)
            | MInst::AndStoreImm { .. }
            | MInst::OrStoreImm { .. }
            | MInst::StorePtr { .. }
            | MInst::ReleaseStorePtr { .. }
            | MInst::StoreIndexed { .. }
            | MInst::OrStoreIndexed { .. }
            | MInst::StorePtrIndexed { .. }
            | MInst::ReleaseStorePtrIndexed { .. }
            | MInst::MemCopy { .. }
            | MInst::MemFill { .. }
            | MInst::SparseCommit { .. }
            | MInst::SparseMarkActive { .. }
            | MInst::SparseCommitWorklist { .. }
            | MInst::Branch { .. }
            | MInst::BranchPred { .. }
            | MInst::JumpTable { .. }
            | MInst::Jump { .. }
            | MInst::Return
            | MInst::ReturnError { .. } => None,
        }
    }

    /// Returns the destination VReg by mutable reference, if any.
    ///
    /// This is used by whole-function VReg renumbering. Keeping destination
    /// mutation beside [`Self::def`] makes it impossible for the compactor to
    /// silently omit a defining opcode while still compiling successfully.
    pub fn def_mut(&mut self) -> Option<&mut VReg> {
        match self {
            MInst::Mov { dst, .. }
            | MInst::Mov32 { dst, .. }
            | MInst::LoadImm { dst, .. }
            | MInst::Scratch { dst }
            | MInst::LoadConstantTableAddr { dst, .. }
            | MInst::Load { dst, .. }
            | MInst::LoadPtr { dst, .. }
            | MInst::LoadIndexed { dst, .. }
            | MInst::PackedLaneCompare { dst, .. }
            | MInst::PackedByteAffineCompare { dst, .. }
            | MInst::LoadPtrIndexed { dst, .. }
            | MInst::Add { dst, .. }
            | MInst::Add32 { dst, .. }
            | MInst::Sub { dst, .. }
            | MInst::Sub32 { dst, .. }
            | MInst::Mul { dst, .. }
            | MInst::Mul32 { dst, .. }
            | MInst::UMulHi { dst, .. }
            | MInst::And { dst, .. }
            | MInst::And32 { dst, .. }
            | MInst::Or { dst, .. }
            | MInst::Or32 { dst, .. }
            | MInst::Xor { dst, .. }
            | MInst::Xor32 { dst, .. }
            | MInst::Shr { dst, .. }
            | MInst::Shl { dst, .. }
            | MInst::Sar { dst, .. }
            | MInst::AndImm { dst, .. }
            | MInst::AndImm32 { dst, .. }
            | MInst::OrImm { dst, .. }
            | MInst::ShrImm { dst, .. }
            | MInst::ShlImm { dst, .. }
            | MInst::SarImm { dst, .. }
            | MInst::AddImm { dst, .. }
            | MInst::SubImm { dst, .. }
            | MInst::Cmp { dst, .. }
            | MInst::CmpImm { dst, .. }
            | MInst::UDiv { dst, .. }
            | MInst::URem { dst, .. }
            | MInst::SDiv { dst, .. }
            | MInst::SRem { dst, .. }
            | MInst::BitNot { dst, .. }
            | MInst::Neg { dst, .. }
            | MInst::Popcnt { dst, .. }
            | MInst::Bsf { dst, .. }
            | MInst::Bsr { dst, .. }
            | MInst::BsrOr { dst, .. }
            | MInst::Pext { dst, .. }
            | MInst::Pdep { dst, .. }
            | MInst::Select { dst, .. }
            | MInst::CmpSelect { dst, .. }
            | MInst::CmpImmSelect { dst, .. }
            | MInst::GuardedCmpSelect { dst, .. } => Some(dst),

            MInst::Store { .. }
            | MInst::X86Simd(_)
            | MInst::AndStoreImm { .. }
            | MInst::OrStoreImm { .. }
            | MInst::StorePtr { .. }
            | MInst::ReleaseStorePtr { .. }
            | MInst::StoreIndexed { .. }
            | MInst::OrStoreIndexed { .. }
            | MInst::StorePtrIndexed { .. }
            | MInst::ReleaseStorePtrIndexed { .. }
            | MInst::MemCopy { .. }
            | MInst::MemFill { .. }
            | MInst::SparseCommit { .. }
            | MInst::SparseMarkActive { .. }
            | MInst::SparseCommitWorklist { .. }
            | MInst::Branch { .. }
            | MInst::BranchPred { .. }
            | MInst::JumpTable { .. }
            | MInst::Jump { .. }
            | MInst::Return
            | MInst::ReturnError { .. } => None,
        }
    }

    /// Returns all VRegs used (read) by this instruction.
    /// Returns the VRegs used by this instruction (max 3, no heap allocation).
    pub fn uses(&self) -> Uses {
        match self {
            MInst::Mov { src, .. } | MInst::Mov32 { src, .. } => Uses::one(*src),
            MInst::X86Simd(X86SimdInst::Pack128 { low, high, .. }) => Uses::two(*low, *high),
            MInst::LoadImm { .. }
            | MInst::X86Simd(X86SimdInst::Scratch128 { .. })
            | MInst::X86Simd(X86SimdInst::Zero128 { .. })
            | MInst::X86Simd(X86SimdInst::Load128 { .. })
            | MInst::X86Simd(X86SimdInst::Binary128 { .. })
            | MInst::X86Simd(X86SimdInst::Store128 { .. })
            | MInst::Scratch { .. }
            | MInst::LoadConstantTableAddr { .. }
            | MInst::Load { .. }
            | MInst::AndStoreImm { .. }
            | MInst::OrStoreImm { .. }
            | MInst::MemCopy { .. }
            | MInst::MemFill { .. }
            | MInst::SparseCommit { .. }
            | MInst::SparseMarkActive { .. }
            | MInst::SparseCommitWorklist { .. } => Uses::none(),
            MInst::Store { src, .. } => Uses::one(*src),
            MInst::LoadPtr { ptr, .. } => Uses::one(*ptr),
            MInst::StorePtr { ptr, src, .. } => Uses::two(*ptr, *src),
            MInst::ReleaseStorePtr { ptr, src, .. } => Uses::two(*ptr, *src),
            MInst::LoadIndexed { index, .. } => Uses::one(*index),
            MInst::PackedLaneCompare {
                rhs: PackedLaneCompareRhs::Scalar(value),
                ..
            } => Uses::one(*value),
            MInst::PackedLaneCompare {
                rhs: PackedLaneCompareRhs::Memory { .. },
                ..
            } => Uses::none(),
            MInst::PackedByteAffineCompare { base, rhs, .. } => Uses::two(*base, *rhs),
            MInst::StoreIndexed { index, src, .. } | MInst::OrStoreIndexed { index, src, .. } => {
                Uses::two(*index, *src)
            }
            MInst::LoadPtrIndexed { ptr, index, .. } => Uses::two(*ptr, *index),
            MInst::StorePtrIndexed {
                ptr, index, src, ..
            } => Uses::three(*ptr, *index, *src),
            MInst::ReleaseStorePtrIndexed {
                ptr, index, src, ..
            } => Uses::three(*ptr, *index, *src),
            MInst::Add { lhs, rhs, .. }
            | MInst::Add32 { lhs, rhs, .. }
            | MInst::Sub { lhs, rhs, .. }
            | MInst::Sub32 { lhs, rhs, .. }
            | MInst::Mul { lhs, rhs, .. }
            | MInst::Mul32 { lhs, rhs, .. }
            | MInst::UMulHi { lhs, rhs, .. }
            | MInst::And { lhs, rhs, .. }
            | MInst::And32 { lhs, rhs, .. }
            | MInst::Or { lhs, rhs, .. }
            | MInst::Or32 { lhs, rhs, .. }
            | MInst::Xor { lhs, rhs, .. }
            | MInst::Xor32 { lhs, rhs, .. }
            | MInst::Shr { lhs, rhs, .. }
            | MInst::Shl { lhs, rhs, .. }
            | MInst::Sar { lhs, rhs, .. }
            | MInst::Cmp { lhs, rhs, .. }
            | MInst::UDiv { lhs, rhs, .. }
            | MInst::URem { lhs, rhs, .. }
            | MInst::SDiv { lhs, rhs, .. }
            | MInst::SRem { lhs, rhs, .. } => Uses::two(*lhs, *rhs),
            MInst::Pext { src, mask, .. } | MInst::Pdep { src, mask, .. } => Uses::two(*src, *mask),
            MInst::AndImm { src, .. }
            | MInst::AndImm32 { src, .. }
            | MInst::OrImm { src, .. }
            | MInst::ShrImm { src, .. }
            | MInst::ShlImm { src, .. }
            | MInst::SarImm { src, .. }
            | MInst::AddImm { src, .. }
            | MInst::SubImm { src, .. }
            | MInst::BitNot { src, .. }
            | MInst::Neg { src, .. }
            | MInst::Popcnt { src, .. }
            | MInst::Bsf { src, .. }
            | MInst::Bsr { src, .. }
            | MInst::BsrOr { src, .. } => Uses::one(*src),
            MInst::CmpImm { lhs, .. } => Uses::one(*lhs),
            MInst::Select {
                cond,
                true_val,
                false_val,
                ..
            } => Uses::three(*cond, *true_val, *false_val),
            MInst::CmpSelect {
                lhs,
                rhs,
                true_val,
                false_val,
                ..
            } => Uses::four(*lhs, *rhs, *true_val, *false_val),
            MInst::CmpImmSelect {
                lhs,
                true_val,
                false_val,
                ..
            } => Uses::three(*lhs, *true_val, *false_val),
            MInst::GuardedCmpSelect {
                guard,
                lhs,
                rhs,
                true_val,
                false_val,
                ..
            } => Uses::five(*guard, *lhs, *rhs, *true_val, *false_val),
            MInst::Branch { cond, .. } => Uses::one(*cond),
            MInst::BranchPred {
                predicate: BranchPredicate::Compare { lhs, rhs, .. },
                ..
            } => Uses::two(*lhs, *rhs),
            MInst::BranchPred {
                predicate: BranchPredicate::CompareImm { lhs, .. },
                ..
            } => Uses::one(*lhs),
            MInst::BranchPred {
                predicate: BranchPredicate::MemoryNonZero { .. },
                ..
            } => Uses::none(),
            MInst::JumpTable {
                index,
                table_base,
                target,
                ..
            } => Uses::three(*index, *table_base, *target),
            MInst::Jump { .. } | MInst::Return | MInst::ReturnError { .. } => Uses::none(),
        }
    }

    /// Replace all occurrences of `old` with `new` in the use operands.
    pub fn rewrite_use(&mut self, old: VReg, new: VReg) {
        match self {
            MInst::Mov { src, .. } | MInst::Mov32 { src, .. } => {
                if *src == old {
                    *src = new;
                }
            }
            MInst::X86Simd(X86SimdInst::Pack128 { low, high, .. }) => {
                if *low == old {
                    *low = new;
                }
                if *high == old {
                    *high = new;
                }
            }
            MInst::Store { src, .. } => {
                if *src == old {
                    *src = new;
                }
            }
            MInst::LoadPtr { ptr, .. } => {
                if *ptr == old {
                    *ptr = new;
                }
            }
            MInst::StorePtr { ptr, src, .. } => {
                if *ptr == old {
                    *ptr = new;
                }
                if *src == old {
                    *src = new;
                }
            }
            MInst::ReleaseStorePtr { ptr, src, .. } => {
                if *ptr == old {
                    *ptr = new;
                }
                if *src == old {
                    *src = new;
                }
            }
            MInst::LoadIndexed { index, .. } => {
                if *index == old {
                    *index = new;
                }
            }
            MInst::PackedLaneCompare {
                rhs: PackedLaneCompareRhs::Scalar(value),
                ..
            } => {
                if *value == old {
                    *value = new;
                }
            }
            MInst::PackedLaneCompare {
                rhs: PackedLaneCompareRhs::Memory { .. },
                ..
            } => {}
            MInst::PackedByteAffineCompare { base, rhs, .. } => {
                if *base == old {
                    *base = new;
                }
                if *rhs == old {
                    *rhs = new;
                }
            }
            MInst::StoreIndexed { index, src, .. } | MInst::OrStoreIndexed { index, src, .. } => {
                if *index == old {
                    *index = new;
                }
                if *src == old {
                    *src = new;
                }
            }
            MInst::LoadPtrIndexed { ptr, index, .. } => {
                if *ptr == old {
                    *ptr = new;
                }
                if *index == old {
                    *index = new;
                }
            }
            MInst::StorePtrIndexed {
                ptr, index, src, ..
            } => {
                if *ptr == old {
                    *ptr = new;
                }
                if *index == old {
                    *index = new;
                }
                if *src == old {
                    *src = new;
                }
            }
            MInst::ReleaseStorePtrIndexed {
                ptr, index, src, ..
            } => {
                if *ptr == old {
                    *ptr = new;
                }
                if *index == old {
                    *index = new;
                }
                if *src == old {
                    *src = new;
                }
            }
            MInst::Add { lhs, rhs, .. }
            | MInst::Add32 { lhs, rhs, .. }
            | MInst::Sub { lhs, rhs, .. }
            | MInst::Sub32 { lhs, rhs, .. }
            | MInst::Mul { lhs, rhs, .. }
            | MInst::Mul32 { lhs, rhs, .. }
            | MInst::UMulHi { lhs, rhs, .. }
            | MInst::And { lhs, rhs, .. }
            | MInst::And32 { lhs, rhs, .. }
            | MInst::Or { lhs, rhs, .. }
            | MInst::Or32 { lhs, rhs, .. }
            | MInst::Xor { lhs, rhs, .. }
            | MInst::Xor32 { lhs, rhs, .. }
            | MInst::Shr { lhs, rhs, .. }
            | MInst::Shl { lhs, rhs, .. }
            | MInst::Sar { lhs, rhs, .. }
            | MInst::Cmp { lhs, rhs, .. }
            | MInst::UDiv { lhs, rhs, .. }
            | MInst::URem { lhs, rhs, .. }
            | MInst::SDiv { lhs, rhs, .. }
            | MInst::SRem { lhs, rhs, .. } => {
                if *lhs == old {
                    *lhs = new;
                }
                if *rhs == old {
                    *rhs = new;
                }
            }
            MInst::AndImm { src, .. }
            | MInst::AndImm32 { src, .. }
            | MInst::OrImm { src, .. }
            | MInst::ShrImm { src, .. }
            | MInst::ShlImm { src, .. }
            | MInst::SarImm { src, .. }
            | MInst::AddImm { src, .. }
            | MInst::SubImm { src, .. }
            | MInst::BitNot { src, .. }
            | MInst::Neg { src, .. }
            | MInst::Popcnt { src, .. }
            | MInst::Bsf { src, .. }
            | MInst::Bsr { src, .. }
            | MInst::BsrOr { src, .. } => {
                if *src == old {
                    *src = new;
                }
            }
            MInst::CmpImm { lhs, .. } => {
                if *lhs == old {
                    *lhs = new;
                }
            }
            MInst::Pext { src, mask, .. } | MInst::Pdep { src, mask, .. } => {
                if *src == old {
                    *src = new;
                }
                if *mask == old {
                    *mask = new;
                }
            }
            MInst::Select {
                cond,
                true_val,
                false_val,
                ..
            } => {
                if *cond == old {
                    *cond = new;
                }
                if *true_val == old {
                    *true_val = new;
                }
                if *false_val == old {
                    *false_val = new;
                }
            }
            MInst::CmpSelect {
                lhs,
                rhs,
                true_val,
                false_val,
                ..
            } => {
                if *lhs == old {
                    *lhs = new;
                }
                if *rhs == old {
                    *rhs = new;
                }
                if *true_val == old {
                    *true_val = new;
                }
                if *false_val == old {
                    *false_val = new;
                }
            }
            MInst::CmpImmSelect {
                lhs,
                true_val,
                false_val,
                ..
            } => {
                if *lhs == old {
                    *lhs = new;
                }
                if *true_val == old {
                    *true_val = new;
                }
                if *false_val == old {
                    *false_val = new;
                }
            }
            MInst::GuardedCmpSelect {
                guard,
                lhs,
                rhs,
                true_val,
                false_val,
                ..
            } => {
                if *guard == old {
                    *guard = new;
                }
                if *lhs == old {
                    *lhs = new;
                }
                if *rhs == old {
                    *rhs = new;
                }
                if *true_val == old {
                    *true_val = new;
                }
                if *false_val == old {
                    *false_val = new;
                }
            }
            MInst::Branch { cond, .. } => {
                if *cond == old {
                    *cond = new;
                }
            }
            MInst::BranchPred { predicate, .. } => match predicate {
                BranchPredicate::Compare { lhs, rhs, .. } => {
                    if *lhs == old {
                        *lhs = new;
                    }
                    if *rhs == old {
                        *rhs = new;
                    }
                }
                BranchPredicate::CompareImm { lhs, .. } => {
                    if *lhs == old {
                        *lhs = new;
                    }
                }
                BranchPredicate::MemoryNonZero { .. } => {}
            },
            MInst::JumpTable {
                index,
                table_base,
                target,
                ..
            } => {
                if *index == old {
                    *index = new;
                }
                if *table_base == old {
                    *table_base = new;
                }
                if *target == old {
                    *target = new;
                }
            }
            MInst::LoadImm { .. }
            | MInst::X86Simd(X86SimdInst::Scratch128 { .. })
            | MInst::X86Simd(X86SimdInst::Zero128 { .. })
            | MInst::X86Simd(X86SimdInst::Load128 { .. })
            | MInst::X86Simd(X86SimdInst::Binary128 { .. })
            | MInst::X86Simd(X86SimdInst::Store128 { .. })
            | MInst::Scratch { .. }
            | MInst::LoadConstantTableAddr { .. }
            | MInst::Load { .. }
            | MInst::AndStoreImm { .. }
            | MInst::OrStoreImm { .. }
            | MInst::MemCopy { .. }
            | MInst::MemFill { .. }
            | MInst::SparseCommit { .. }
            | MInst::SparseMarkActive { .. }
            | MInst::SparseCommitWorklist { .. }
            | MInst::Jump { .. }
            | MInst::Return
            | MInst::ReturnError { .. } => {}
        }
    }

    /// Returns true if this instruction is a terminator (branch/jump/return).
    pub fn is_terminator(&self) -> bool {
        matches!(
            self,
            MInst::Branch { .. }
                | MInst::BranchPred { .. }
                | MInst::JumpTable { .. }
                | MInst::Jump { .. }
                | MInst::Return
                | MInst::ReturnError { .. }
        )
    }

    pub fn branch_targets(&self) -> Option<(BlockId, BlockId)> {
        match self {
            MInst::Branch {
                true_bb, false_bb, ..
            }
            | MInst::BranchPred {
                true_bb, false_bb, ..
            } => Some((*true_bb, *false_bb)),
            _ => None,
        }
    }

    pub fn rewrite_successors(&mut self, mut rewrite: impl FnMut(BlockId) -> BlockId) {
        match self {
            MInst::Branch {
                true_bb, false_bb, ..
            }
            | MInst::BranchPred {
                true_bb, false_bb, ..
            } => {
                *true_bb = rewrite(*true_bb);
                *false_bb = rewrite(*false_bb);
            }
            MInst::JumpTable { targets, .. } => {
                for target in targets {
                    *target = rewrite(*target);
                }
            }
            MInst::Jump { target } => *target = rewrite(*target),
            _ => {}
        }
    }
}

// ────────────────────────────────────────────────────────────────
// Basic block
// ────────────────────────────────────────────────────────────────

/// A phi node at block entry: `dst = phi(pred1: src1, pred2: src2, ...)`.
/// Maintains SSA: each VReg has exactly one definition point.
#[derive(Debug, Clone)]
pub struct PhiNode {
    pub dst: VReg,
    pub sources: Vec<(BlockId, VReg)>,
}

/// A basic block containing a sequence of MIR instructions.
/// The last instruction must be a terminator.
#[derive(Debug, Clone)]
pub struct MBlock {
    pub id: BlockId,
    /// Phi nodes at block entry (SSA merge points).
    pub phis: Vec<PhiNode>,
    pub insts: Vec<MInst>,
}

impl MBlock {
    pub fn new(id: BlockId) -> Self {
        Self {
            id,
            phis: Vec::new(),
            insts: Vec::new(),
        }
    }

    pub fn push(&mut self, inst: MInst) {
        self.insts.push(inst);
    }

    pub fn terminator(&self) -> Option<&MInst> {
        self.insts.last().filter(|i| i.is_terminator())
    }

    /// Successor block IDs (from the terminator).
    pub fn successors(&self) -> Vec<BlockId> {
        match self.terminator() {
            Some(MInst::Branch {
                true_bb, false_bb, ..
            })
            | Some(MInst::BranchPred {
                true_bb, false_bb, ..
            }) => vec![*true_bb, *false_bb],
            Some(MInst::JumpTable { targets, .. }) => targets.to_vec(),
            Some(MInst::Jump { target }) => vec![*target],
            _ => vec![],
        }
    }
}

// ────────────────────────────────────────────────────────────────
// Function (compilation unit)
// ────────────────────────────────────────────────────────────────

/// A MIR function: the unit of compilation for the native backend.
/// Corresponds to one SIR execution unit.
#[derive(Debug, Clone)]
pub struct MFunction {
    /// Basic blocks in layout order. `blocks[0]` is the unique CFG entry and
    /// no block may branch back to it; loops therefore have a distinct header.
    pub blocks: Vec<MBlock>,
    /// Spill descriptors indexed by VReg number.
    pub spill_descs: Vec<SpillDesc>,
    /// VReg allocator (for the spilling phase to allocate reload regs).
    pub vregs: VRegAllocator,
    /// Number of target-specific virtual XMM values allocated by x86 SLP.
    x86_vec_count: u32,
    /// Immutable u64 lookup tables embedded in the emitted function body.
    constant_tables: Vec<Vec<u64>>,
    /// Target facts shared by optimization, register allocation, and emission.
    pub(crate) target_features: super::features::X86Features,
}

impl MFunction {
    pub fn new(vregs: VRegAllocator, spill_descs: Vec<SpillDesc>) -> Self {
        Self {
            blocks: Vec::new(),
            spill_descs,
            vregs,
            x86_vec_count: 0,
            constant_tables: Vec::new(),
            target_features: super::features::X86Features::detect(),
        }
    }

    pub fn alloc_x86_vec(&mut self) -> X86VecReg {
        let value = X86VecReg(self.x86_vec_count);
        self.x86_vec_count = self
            .x86_vec_count
            .checked_add(1)
            .expect("x86 vector VReg overflow");
        value
    }

    pub fn x86_vec_count(&self) -> u32 {
        self.x86_vec_count
    }

    /// Return the stable identity of `values`, reusing an identical table.
    pub fn intern_constant_table(&mut self, values: Vec<u64>) -> ConstantTableId {
        if let Some(index) = self
            .constant_tables
            .iter()
            .position(|existing| existing == &values)
        {
            return ConstantTableId(index);
        }
        let id = ConstantTableId(self.constant_tables.len());
        self.constant_tables.push(values);
        id
    }

    /// All function-local constant tables, in stable emission order.
    pub fn constant_tables(&self) -> &[Vec<u64>] {
        &self.constant_tables
    }

    /// Resolve a constant-table identity without panicking on malformed MIR.
    pub fn constant_table(&self, id: ConstantTableId) -> Option<&[u64]> {
        self.constant_tables.get(id.0).map(Vec::as_slice)
    }

    pub fn push_block(&mut self, block: MBlock) {
        self.blocks.push(block);
    }

    pub fn entry_block(&self) -> Option<&MBlock> {
        self.blocks.first()
    }

    /// Get SpillDesc for a VReg. Returns None for VRegs allocated after
    /// the initial ISel (e.g. reload temporaries created by the spilling phase).
    pub fn spill_desc(&self, vreg: VReg) -> Option<&SpillDesc> {
        self.spill_descs.get(vreg.0 as usize)
    }

    /// Verify the canonical MIR contract without modifying the function.
    pub fn verify_result(&self) -> Result<(), super::mir_verify::MirVerifyError> {
        super::mir_verify::verify_function(self)
    }

    /// Verify the canonical MIR contract and panic with a structured diagnostic.
    pub fn verify(&self) {
        if let Err(error) = self.verify_result() {
            panic!("{error}");
        }
    }
}

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

    #[test]
    fn uses_keeps_all_machine_operands_inline() {
        let values = (0..MAX_USES as u32).map(VReg).collect::<Vec<_>>();
        let uses = Uses::from_slice(&values);
        assert_eq!(uses.as_slice(), values);
        assert_eq!(uses.into_iter().next_back(), Some(VReg(4)));
    }

    #[test]
    fn uses_does_not_inflate_the_previous_inline_representation() {
        #[allow(dead_code)]
        struct PreviousUses {
            buf: [VReg; 16],
            len: u8,
        }

        assert!(
            std::mem::size_of::<Uses>() <= std::mem::size_of::<PreviousUses>(),
            "Uses grew from {} to {} bytes",
            std::mem::size_of::<PreviousUses>(),
            std::mem::size_of::<Uses>(),
        );
    }

    #[test]
    fn memory_alias_range_must_be_nonempty() {
        assert_eq!(MemoryAliasRange::new(8, 0), None);
        assert_eq!(MemoryAliasRange::new(8, 1).unwrap().end(), 9);
    }

    #[test]
    fn try_alloc_reports_exhaustion_without_changing_state() {
        let mut allocator = VRegAllocator::new();
        allocator.set_next_for_test(u32::MAX);

        assert_eq!(allocator.try_alloc(), Err(VRegAllocError));
        assert_eq!(allocator.count(), u32::MAX);
    }

    struct UseCase {
        name: &'static str,
        inst: MInst,
        expected: Vec<VReg>,
    }

    fn vreg(index: u32) -> VReg {
        VReg(index)
    }

    fn use_cases() -> Vec<UseCase> {
        let dst = vreg(100);
        let a = vreg(1);
        let b = vreg(2);
        let c = vreg(3);
        let d = vreg(4);
        let e = vreg(5);
        let block_a = BlockId(1);
        let block_b = BlockId(2);

        vec![
            UseCase {
                name: "Mov",
                inst: MInst::Mov { dst, src: a },
                expected: vec![a],
            },
            UseCase {
                name: "LoadImm",
                inst: MInst::LoadImm { dst, value: 42 },
                expected: vec![],
            },
            UseCase {
                name: "Scratch",
                inst: MInst::Scratch { dst },
                expected: vec![],
            },
            UseCase {
                name: "LoadConstantTableAddr",
                inst: MInst::LoadConstantTableAddr {
                    dst,
                    table: ConstantTableId(0),
                },
                expected: vec![],
            },
            UseCase {
                name: "Load",
                inst: MInst::Load {
                    dst,
                    base: BaseReg::SimState,
                    offset: 8,
                    size: OpSize::S64,
                },
                expected: vec![],
            },
            UseCase {
                name: "Store",
                inst: MInst::Store {
                    base: BaseReg::SimState,
                    offset: 8,
                    src: a,
                    size: OpSize::S64,
                },
                expected: vec![a],
            },
            UseCase {
                name: "LoadPtr",
                inst: MInst::LoadPtr {
                    dst,
                    ptr: a,
                    offset: 8,
                    size: OpSize::S64,
                },
                expected: vec![a],
            },
            UseCase {
                name: "StorePtr",
                inst: MInst::StorePtr {
                    ptr: a,
                    offset: 8,
                    src: b,
                    size: OpSize::S64,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "ReleaseStorePtr",
                inst: MInst::ReleaseStorePtr {
                    ptr: a,
                    offset: 8,
                    src: b,
                    size: OpSize::S64,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "LoadIndexed",
                inst: MInst::LoadIndexed {
                    dst,
                    base: BaseReg::SimState,
                    offset: 8,
                    index: a,
                    scale: 1,
                    size: OpSize::S64,
                    alias_range: None,
                },
                expected: vec![a],
            },
            UseCase {
                name: "StoreIndexed",
                inst: MInst::StoreIndexed {
                    base: BaseReg::SimState,
                    offset: 8,
                    index: a,
                    src: b,
                    size: OpSize::S64,
                    alias_range: None,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "OrStoreIndexed",
                inst: MInst::OrStoreIndexed {
                    base: BaseReg::SimState,
                    offset: 8,
                    index: a,
                    src: b,
                    size: OpSize::S64,
                    alias_range: None,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "LoadPtrIndexed",
                inst: MInst::LoadPtrIndexed {
                    dst,
                    ptr: a,
                    offset: 8,
                    index: b,
                    size: OpSize::S64,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "StorePtrIndexed",
                inst: MInst::StorePtrIndexed {
                    ptr: a,
                    offset: 8,
                    index: b,
                    src: c,
                    size: OpSize::S64,
                },
                expected: vec![a, b, c],
            },
            UseCase {
                name: "ReleaseStorePtrIndexed",
                inst: MInst::ReleaseStorePtrIndexed {
                    ptr: a,
                    offset: 8,
                    index: b,
                    src: c,
                    size: OpSize::S64,
                },
                expected: vec![a, b, c],
            },
            UseCase {
                name: "MemCopy",
                inst: MInst::MemCopy {
                    src_offset: 0,
                    dst_offset: 8,
                    byte_len: 16,
                },
                expected: vec![],
            },
            UseCase {
                name: "MemFill",
                inst: MInst::MemFill {
                    dst_offset: 0,
                    byte_len: 16,
                    value: 0x5a,
                },
                expected: vec![],
            },
            UseCase {
                name: "SparseMarkActive",
                inst: MInst::SparseMarkActive {
                    active_index: 0,
                    active_bits_offset: 8,
                    active_capacity: 1,
                },
                expected: vec![],
            },
            UseCase {
                name: "Add",
                inst: MInst::Add {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "Sub",
                inst: MInst::Sub {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "Mul",
                inst: MInst::Mul {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "UMulHi",
                inst: MInst::UMulHi {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "And",
                inst: MInst::And {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "Or",
                inst: MInst::Or {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "Xor",
                inst: MInst::Xor {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "Shr",
                inst: MInst::Shr {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "Shl",
                inst: MInst::Shl {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "Sar",
                inst: MInst::Sar {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "AndImm",
                inst: MInst::AndImm {
                    dst,
                    src: a,
                    imm: 0xff,
                },
                expected: vec![a],
            },
            UseCase {
                name: "OrImm",
                inst: MInst::OrImm {
                    dst,
                    src: a,
                    imm: 0xff,
                },
                expected: vec![a],
            },
            UseCase {
                name: "ShrImm",
                inst: MInst::ShrImm {
                    dst,
                    src: a,
                    imm: 3,
                },
                expected: vec![a],
            },
            UseCase {
                name: "ShlImm",
                inst: MInst::ShlImm {
                    dst,
                    src: a,
                    imm: 3,
                },
                expected: vec![a],
            },
            UseCase {
                name: "SarImm",
                inst: MInst::SarImm {
                    dst,
                    src: a,
                    imm: 3,
                },
                expected: vec![a],
            },
            UseCase {
                name: "AddImm",
                inst: MInst::AddImm {
                    dst,
                    src: a,
                    imm: 3,
                },
                expected: vec![a],
            },
            UseCase {
                name: "SubImm",
                inst: MInst::SubImm {
                    dst,
                    src: a,
                    imm: 3,
                },
                expected: vec![a],
            },
            UseCase {
                name: "Cmp",
                inst: MInst::Cmp {
                    dst,
                    lhs: a,
                    rhs: b,
                    kind: CmpKind::Eq,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "CmpImm",
                inst: MInst::CmpImm {
                    dst,
                    lhs: a,
                    imm: 3,
                    kind: CmpKind::Eq,
                },
                expected: vec![a],
            },
            UseCase {
                name: "UDiv",
                inst: MInst::UDiv {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "URem",
                inst: MInst::URem {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "SDiv",
                inst: MInst::SDiv {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "SRem",
                inst: MInst::SRem {
                    dst,
                    lhs: a,
                    rhs: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "BitNot",
                inst: MInst::BitNot { dst, src: a },
                expected: vec![a],
            },
            UseCase {
                name: "Neg",
                inst: MInst::Neg { dst, src: a },
                expected: vec![a],
            },
            UseCase {
                name: "Popcnt",
                inst: MInst::Popcnt { dst, src: a },
                expected: vec![a],
            },
            UseCase {
                name: "Bsf",
                inst: MInst::Bsf { dst, src: a },
                expected: vec![a],
            },
            UseCase {
                name: "Bsr",
                inst: MInst::Bsr { dst, src: a },
                expected: vec![a],
            },
            UseCase {
                name: "BsrOr",
                inst: MInst::BsrOr {
                    dst,
                    src: a,
                    zero_value: 63,
                },
                expected: vec![a],
            },
            UseCase {
                name: "Pext",
                inst: MInst::Pext {
                    dst,
                    src: a,
                    mask: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "Pdep",
                inst: MInst::Pdep {
                    dst,
                    src: a,
                    mask: b,
                },
                expected: vec![a, b],
            },
            UseCase {
                name: "Select",
                inst: MInst::Select {
                    dst,
                    cond: a,
                    true_val: b,
                    false_val: c,
                },
                expected: vec![a, b, c],
            },
            UseCase {
                name: "CmpSelect",
                inst: MInst::CmpSelect {
                    dst,
                    lhs: a,
                    rhs: b,
                    kind: CmpKind::Eq,
                    true_val: c,
                    false_val: d,
                },
                expected: vec![a, b, c, d],
            },
            UseCase {
                name: "CmpImmSelect",
                inst: MInst::CmpImmSelect {
                    dst,
                    lhs: a,
                    imm: 3,
                    kind: CmpKind::Eq,
                    true_val: b,
                    false_val: c,
                },
                expected: vec![a, b, c],
            },
            UseCase {
                name: "GuardedCmpSelect",
                inst: MInst::GuardedCmpSelect {
                    dst,
                    guard: a,
                    lhs: b,
                    rhs: c,
                    kind: CmpKind::Eq,
                    true_val: d,
                    false_val: e,
                },
                expected: vec![a, b, c, d, e],
            },
            UseCase {
                name: "Branch",
                inst: MInst::Branch {
                    cond: a,
                    true_bb: block_a,
                    false_bb: block_b,
                },
                expected: vec![a],
            },
            UseCase {
                name: "Jump",
                inst: MInst::Jump { target: block_a },
                expected: vec![],
            },
            UseCase {
                name: "Return",
                inst: MInst::Return,
                expected: vec![],
            },
            UseCase {
                name: "ReturnError",
                inst: MInst::ReturnError { code: 1 },
                expected: vec![],
            },
        ]
    }

    #[test]
    fn uses_reports_every_use_operand_for_every_instruction_variant() {
        let cases = use_cases();
        assert_eq!(
            cases.len(),
            57,
            "the MInst variant table must stay exhaustive"
        );

        for case in cases {
            assert_eq!(
                case.inst.uses().into_iter().collect::<Vec<_>>(),
                case.expected,
                "{}",
                case.name
            );
        }
    }

    #[test]
    fn rewrite_use_rewrites_every_operand_reported_by_uses() {
        for case in use_cases() {
            let original_def = case.inst.def();
            for old in case.expected.iter().copied() {
                let replacement = vreg(old.0 + 200);
                let mut rewritten = case.inst.clone();
                rewritten.rewrite_use(old, replacement);

                let expected = case
                    .expected
                    .iter()
                    .copied()
                    .map(|used| if used == old { replacement } else { used })
                    .collect::<Vec<_>>();
                assert_eq!(
                    rewritten.uses().into_iter().collect::<Vec<_>>(),
                    expected,
                    "{} did not rewrite {old}",
                    case.name
                );
                assert_eq!(
                    rewritten.def(),
                    original_def,
                    "{} rewrote its definition while replacing {old}",
                    case.name
                );
            }
        }
    }

    #[test]
    fn rewrite_use_rewrites_all_occurrences_of_the_same_vreg() {
        let shared = vreg(50);
        let replacement = vreg(51);

        for case in use_cases() {
            if case.expected.is_empty() {
                continue;
            }
            let original_def = case.inst.def();
            let mut rewritten = case.inst;
            for used in case.expected {
                rewritten.rewrite_use(used, shared);
            }
            rewritten.rewrite_use(shared, replacement);

            assert!(
                rewritten.uses().into_iter().all(|used| used == replacement),
                "{} left an occurrence of the shared use unchanged",
                case.name
            );
            assert_eq!(
                rewritten.def(),
                original_def,
                "{} changed its def",
                case.name
            );
        }
    }
}