celox-backend-x86 0.8.2

//! Sparse stack-slot interval unions.
//!
//! Stack homes retain exact per-block ranges rather than being projected onto
//! one linear instruction interval. Each dynamically-created slot stores only
//! the occupied CFG rows required for first-fit coloring.

use std::collections::BTreeMap;
use std::fmt;
use std::sync::Arc;

use crate::HashMap;
use crate::native::mir::BlockId;

use super::cfg::NormalizedCfg;
use super::live_interval::{LiveSegment, SlotIndex};

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

/// Borrowed canonical sparse range proved once at an allocator boundary.
/// All stack-slot unions in one matrix share the same CFG index, so a token
/// can be reused across every slot probe without rechecking order,
/// self-interference, and block membership.
#[derive(Debug, Clone, Copy)]
pub(super) struct ValidatedSegments<'a> {
    index: &'a Arc<IntervalIndex>,
    segments: &'a [LiveSegment],
    block_indices: &'a [usize],
}

impl<'a> ValidatedSegments<'a> {
    fn as_slice(self) -> &'a [LiveSegment] {
        self.segments
    }

    pub(super) fn iter(self) -> impl Iterator<Item = (LiveSegment, usize)> + 'a {
        debug_assert_eq!(self.segments.len(), self.block_indices.len());
        self.segments
            .iter()
            .copied()
            .zip(self.block_indices.iter().copied())
    }
}

/// Allocation-owned sparse range with CFG row identities resolved once.
/// `LiveSegment::block` remains the semantic/diagnostic identity; interval
/// unions use the parallel row index for all hot ordered-map operations.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(super) struct SparseRange {
    index: Arc<IntervalIndex>,
    segments: Vec<LiveSegment>,
    block_indices: Vec<usize>,
}

impl SparseRange {
    pub(super) fn validated(&self) -> ValidatedSegments<'_> {
        debug_assert_eq!(self.segments.len(), self.block_indices.len());
        ValidatedSegments {
            index: &self.index,
            segments: &self.segments,
            block_indices: &self.block_indices,
        }
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub(super) struct IntervalUnionError {
    pub rule: &'static str,
    pub block: Option<BlockId>,
    pub bundles: Vec<AllocationBundleId>,
    pub message: String,
}

impl IntervalUnionError {
    fn new(
        rule: &'static str,
        block: Option<BlockId>,
        bundles: impl IntoIterator<Item = AllocationBundleId>,
        message: impl Into<String>,
    ) -> Self {
        Self {
            rule,
            block,
            bundles: bundles.into_iter().collect(),
            message: message.into(),
        }
    }
}

impl fmt::Display for IntervalUnionError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(formatter, "{}", self.rule)?;
        if let Some(block) = self.block {
            write!(formatter, " at {block}")?;
        }
        if !self.bundles.is_empty() {
            write!(formatter, " bundles={:?}", self.bundles)?;
        }
        write!(formatter, ": {}", self.message)
    }
}

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

#[derive(Debug, PartialEq, Eq)]
struct IntervalIndex {
    block_index: HashMap<BlockId, usize>,
    block_ids: Vec<BlockId>,
}

impl IntervalIndex {
    fn new(cfg: &NormalizedCfg) -> Result<Self, IntervalUnionError> {
        let block_count = cfg.successors.len();
        if cfg.block_index.len() != block_count {
            return Err(IntervalUnionError::new(
                "INTERVAL_UNION.CFG_SHAPE",
                None,
                [],
                "block-index table and CFG row count differ",
            ));
        }
        let mut block_ids = vec![None; block_count];
        for (&block, &index) in &cfg.block_index {
            let Some(slot) = block_ids.get_mut(index) else {
                return Err(IntervalUnionError::new(
                    "INTERVAL_UNION.CFG_SHAPE",
                    Some(block),
                    [],
                    "block index is outside the CFG",
                ));
            };
            if slot.replace(block).is_some() {
                return Err(IntervalUnionError::new(
                    "INTERVAL_UNION.CFG_SHAPE",
                    Some(block),
                    [],
                    "two MIR blocks share one CFG index",
                ));
            }
        }
        let block_ids = block_ids
            .into_iter()
            .collect::<Option<Vec<_>>>()
            .ok_or_else(|| {
                IntervalUnionError::new(
                    "INTERVAL_UNION.CFG_SHAPE",
                    None,
                    [],
                    "CFG index does not name every block row",
                )
            })?;
        Ok(Self {
            block_index: cfg.block_index.clone(),
            block_ids,
        })
    }

    fn make_range(
        self: &Arc<Self>,
        segments: Vec<LiveSegment>,
    ) -> Result<SparseRange, IntervalUnionError> {
        let mut block_indices = Vec::with_capacity(segments.len());
        let mut previous = None::<LiveSegment>;
        for &segment in &segments {
            if segment.start >= segment.end {
                return Err(IntervalUnionError::new(
                    "INTERVAL_UNION.SEGMENT_RANGE",
                    Some(segment.block),
                    [],
                    format!(
                        "segment {:?}..{:?} is empty or reversed",
                        segment.start, segment.end
                    ),
                ));
            }
            let Some(&block_index) = self.block_index.get(&segment.block) else {
                return Err(IntervalUnionError::new(
                    "INTERVAL_UNION.SEGMENT_BLOCK",
                    Some(segment.block),
                    [],
                    "segment references a block outside the normalized CFG",
                ));
            };
            if self.block_ids.get(block_index) != Some(&segment.block) {
                return Err(IntervalUnionError::new(
                    "INTERVAL_UNION.CFG_SHAPE",
                    Some(segment.block),
                    [],
                    "CFG row does not resolve back to the segment block",
                ));
            }
            if let Some(prior) = previous {
                if (segment.block, segment.start) <= (prior.block, prior.start) {
                    return Err(IntervalUnionError::new(
                        "INTERVAL_UNION.SEGMENT_ORDER",
                        Some(segment.block),
                        [],
                        "bundle segments are not in strict block/slot order",
                    ));
                }
                if prior.overlaps(segment) {
                    return Err(IntervalUnionError::new(
                        "INTERVAL_UNION.SELF_INTERFERENCE",
                        Some(segment.block),
                        [],
                        "one bundle contains overlapping sparse segments",
                    ));
                }
            }
            previous = Some(segment);
            block_indices.push(block_index);
        }
        Ok(SparseRange {
            index: Arc::clone(self),
            segments,
            block_indices,
        })
    }
}

/// Sparse interference matrix with an allocation-owned, dynamically growing
/// color domain. Physical-register allocation has a fixed target register
/// set; stack-slot coloring instead creates a new color only when every
/// existing slot interferes with a home's exact CFG range.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct DynamicUnionNode {
    start: SlotIndex,
    end: SlotIndex,
    next: u32,
}

// Ordinary blocks use 32-bit slots. Keep a lossless wide fallback for the
// same slot domain as LiveSegment, without doubling every occupancy node.
#[derive(Debug, Clone)]
enum DynamicNodeArena {
    Packed(Vec<[u32; 3]>),
    Wide(Vec<DynamicUnionNode>),
}

impl DynamicNodeArena {
    fn pack(node: DynamicUnionNode) -> Option<[u32; 3]> {
        Some([node.start.packed()?, node.end.packed()?, node.next])
    }

    fn unpack([start, end, next]: [u32; 3]) -> DynamicUnionNode {
        DynamicUnionNode {
            start: SlotIndex::from_packed(start),
            end: SlotIndex::from_packed(end),
            next,
        }
    }

    fn len(&self) -> usize {
        match self {
            Self::Packed(nodes) => nodes.len(),
            Self::Wide(nodes) => nodes.len(),
        }
    }

    fn get(&self, index: usize) -> Option<DynamicUnionNode> {
        match self {
            Self::Packed(nodes) => nodes.get(index).copied().map(Self::unpack),
            Self::Wide(nodes) => nodes.get(index).copied(),
        }
    }

    fn node(&self, index: usize) -> DynamicUnionNode {
        self.get(index).expect("dynamic union node is in range")
    }

    fn promote(&mut self) -> &mut Vec<DynamicUnionNode> {
        if let Self::Packed(nodes) = self {
            *self = Self::Wide(nodes.iter().copied().map(Self::unpack).collect());
        }
        let Self::Wide(nodes) = self else {
            unreachable!()
        };
        nodes
    }

    fn push(&mut self, node: DynamicUnionNode) {
        if let Self::Packed(nodes) = self
            && let Some(packed) = Self::pack(node)
        {
            nodes.push(packed);
            return;
        }
        self.promote().push(node);
    }

    fn update(&mut self, index: usize, update: impl FnOnce(&mut DynamicUnionNode)) {
        let mut node = self.node(index);
        update(&mut node);
        if let Self::Packed(nodes) = self
            && let Some(packed) = Self::pack(node)
        {
            nodes[index] = packed;
            return;
        }
        self.promote()[index] = node;
    }
}

/// Ownerless, append-only occupancy for one dynamically created stack slot.
///
/// Stack coloring never evicts an assigned home and only needs to know
/// whether a slot is occupied. Reusing `IntervalUnion` here retained one
/// owner-bearing BTree node for nearly every `(slot, block)` pair. Large RTL
/// functions make that relation close to dense: Heliodor produced tens of
/// millions of one-entry trees. A dense four-byte head per CFG block plus one
/// flat node arena stores the same interval union without per-segment heap
/// allocations. Adjacent ranges are merged because their owners are
/// irrelevant after the assignment map records the selected slot.
/// Most occupied rows cover their complete block. Keep those as bits and
/// allocate a node head only for partial rows. Fall back to the ordinary dense
/// table if partial occupancy would cost more than one u32 per block.
#[derive(Debug, Clone)]
enum BlockHeads {
    Sparse {
        len: usize,
        full: Box<[u64]>,
        partial: HashMap<usize, u32>,
    },
    Dense(Box<[u32]>),
}

impl BlockHeads {
    fn new(len: usize) -> Self {
        Self::Sparse {
            len,
            full: vec![0; len.div_ceil(64)].into_boxed_slice(),
            partial: HashMap::default(),
        }
    }

    fn len(&self) -> usize {
        match self {
            Self::Sparse { len, .. } => *len,
            Self::Dense(heads) => heads.len(),
        }
    }

    fn get(&self, block: usize) -> u32 {
        match self {
            Self::Sparse { full, partial, .. } => {
                if full[block / 64] & (1u64 << (block % 64)) != 0 {
                    DynamicSlotUnion::FULL
                } else {
                    partial
                        .get(&block)
                        .copied()
                        .unwrap_or(DynamicSlotUnion::NONE)
                }
            }
            Self::Dense(heads) => heads[block],
        }
    }

    fn set(&mut self, block: usize, head: u32) {
        match self {
            Self::Dense(heads) => {
                heads[block] = head;
                return;
            }
            Self::Sparse { full, partial, .. } => {
                let bit = 1u64 << (block % 64);
                if head == DynamicSlotUnion::FULL {
                    full[block / 64] |= bit;
                    partial.remove(&block);
                } else {
                    full[block / 64] &= !bit;
                    if head == DynamicSlotUnion::NONE {
                        partial.remove(&block);
                    } else {
                        partial.insert(block, head);
                    }
                }
            }
        }
        let Self::Sparse { len, full, partial } = self else {
            unreachable!()
        };
        if full.len() * 8 + partial.capacity() * std::mem::size_of::<(usize, u32)>() >= *len * 4 {
            let heads = (0..*len).map(|block| self.get(block)).collect();
            *self = Self::Dense(heads);
        }
    }

    fn iter(&self) -> impl Iterator<Item = u32> + '_ {
        (0..self.len()).map(|block| self.get(block))
    }
}

#[derive(Debug, Clone)]
struct DynamicSlotUnion {
    heads: BlockHeads,
    nodes: DynamicNodeArena,
    full_ends: Arc<[SlotIndex]>,
}

impl DynamicSlotUnion {
    const NONE: u32 = u32::MAX;
    const FULL: u32 = u32::MAX - 1;

    fn new(block_count: usize) -> Self {
        Self {
            heads: BlockHeads::new(block_count),
            nodes: DynamicNodeArena::Packed(Vec::new()),
            full_ends: Arc::from([]),
        }
    }

    fn node(&self, identity: u32, block: usize) -> Option<DynamicUnionNode> {
        if identity == Self::FULL {
            self.full_ends
                .get(block)
                .copied()
                .map(|end| DynamicUnionNode {
                    start: SlotIndex::from_u64(0),
                    end,
                    next: Self::NONE,
                })
        } else {
            self.nodes.get(identity as usize)
        }
    }

    fn interferes_segment(&self, segment: LiveSegment, block: usize) -> bool {
        let mut current = self.heads.get(block);
        while current != Self::NONE {
            let node = self
                .node(current, block)
                .expect("occupied block has a node");
            if node.end <= segment.start {
                current = node.next;
                continue;
            }
            if node.start >= segment.end {
                break;
            }
            return true;
        }
        false
    }

    fn interferes_indexed(&self, segments: ValidatedSegments<'_>) -> bool {
        segments
            .iter()
            .any(|(segment, block)| self.interferes_segment(segment, block))
    }

    fn interferes_indexed_with_hint(&self, segments: ValidatedSegments<'_>, hint: usize) -> bool {
        if self.interferes_segment(segments.segments[hint], segments.block_indices[hint]) {
            return true;
        }
        segments
            .iter()
            .enumerate()
            .any(|(index, (segment, block))| {
                index != hint && self.interferes_segment(segment, block)
            })
    }

    fn insert_indexed(
        &mut self,
        bundle: AllocationBundleId,
        segments: ValidatedSegments<'_>,
    ) -> Result<(), IntervalUnionError> {
        if segments.as_slice().is_empty() {
            return Err(IntervalUnionError::new(
                "INTERVAL_UNION.EMPTY_ASSIGNMENT",
                None,
                [bundle],
                "a stack-slot assignment must own at least one live segment",
            ));
        }
        if self.interferes_indexed(segments) {
            return Err(IntervalUnionError::new(
                "INTERVAL_UNION.INTERFERENCE",
                segments.as_slice().first().map(|segment| segment.block),
                [bundle],
                "cannot overlap occupancy in one dynamic stack slot",
            ));
        }
        if self
            .nodes
            .len()
            .checked_add(segments.as_slice().len())
            .and_then(|count| count.checked_add(segments.as_slice().len()))
            .is_none_or(|count| count > Self::FULL as usize)
        {
            return Err(IntervalUnionError::new(
                "INTERVAL_UNION.DYNAMIC_NODE_RANGE",
                segments.as_slice().first().map(|segment| segment.block),
                [bundle],
                "dynamic stack-slot union exceeds the node identity domain",
            ));
        }
        for (segment, block) in segments.iter() {
            self.insert_segment(segment, block);
        }
        Ok(())
    }

    fn insert_segment(&mut self, segment: LiveSegment, block: usize) {
        if self.heads.get(block) == Self::NONE
            && segment.start.as_u64() == 0
            && self.full_ends.get(block) == Some(&segment.end)
        {
            self.heads.set(block, Self::FULL);
            return;
        }
        if self.heads.get(block) == Self::FULL {
            // Only a disjoint interval beyond the shared endpoint can reach
            // here. Materialize the prefix so ordinary merging stays exact.
            let node = self
                .node(Self::FULL, block)
                .expect("full block has an endpoint");
            self.heads.set(block, self.nodes.len() as u32);
            self.nodes.push(node);
        }
        let mut previous = Self::NONE;
        let mut current = self.heads.get(block);
        while current != Self::NONE {
            let node = self.nodes.node(current as usize);
            if node.end <= segment.start {
                previous = current;
                current = node.next;
            } else {
                break;
            }
        }

        let merge_left =
            previous != Self::NONE && self.nodes.node(previous as usize).end == segment.start;
        let merge_right =
            current != Self::NONE && self.nodes.node(current as usize).start == segment.end;
        match (merge_left, merge_right) {
            (true, true) => {
                let right = self.nodes.node(current as usize);
                self.nodes.update(previous as usize, |left| {
                    left.end = right.end;
                    left.next = right.next;
                });
            }
            (true, false) => {
                self.nodes
                    .update(previous as usize, |node| node.end = segment.end);
            }
            (false, true) => {
                self.nodes
                    .update(current as usize, |node| node.start = segment.start);
            }
            (false, false) => {
                let node = self.nodes.len() as u32;
                self.nodes.push(DynamicUnionNode {
                    start: segment.start,
                    end: segment.end,
                    next: current,
                });
                if previous == Self::NONE {
                    self.heads.set(block, node);
                } else {
                    self.nodes
                        .update(previous as usize, |previous| previous.next = node);
                }
            }
        }
        let head = self.heads.get(block);
        if let Some(node) = self.nodes.get(head as usize)
            && node.start.as_u64() == 0
            && node.next == Self::NONE
            && self.full_ends.get(block) == Some(&node.end)
        {
            self.heads.set(block, Self::FULL);
        }
    }

    fn verify(&self, index: &IntervalIndex) -> Result<(), IntervalUnionError> {
        if self.heads.len() != index.block_ids.len() {
            return Err(IntervalUnionError::new(
                "INTERVAL_UNION.CFG_SHAPE",
                None,
                [],
                "dynamic stack-slot block table does not cover the CFG",
            ));
        }
        for (block, head) in self.heads.iter().enumerate() {
            let mut current = head;
            let mut previous_end = None::<SlotIndex>;
            let mut traversed = 0usize;
            while current != Self::NONE {
                let Some(node) = self.node(current, block) else {
                    return Err(IntervalUnionError::new(
                        "INTERVAL_UNION.DYNAMIC_NODE_RANGE",
                        index.block_ids.get(block).copied(),
                        [],
                        "dynamic stack-slot chain references a missing node",
                    ));
                };
                if node.start >= node.end {
                    return Err(IntervalUnionError::new(
                        "INTERVAL_UNION.SEGMENT_RANGE",
                        index.block_ids.get(block).copied(),
                        [],
                        "dynamic stack-slot union contains an empty or reversed segment",
                    ));
                }
                if previous_end.is_some_and(|end| end >= node.start) {
                    return Err(IntervalUnionError::new(
                        "INTERVAL_UNION.INTERFERENCE",
                        index.block_ids.get(block).copied(),
                        [],
                        "dynamic stack-slot union contains overlapping or unmerged segments",
                    ));
                }
                previous_end = Some(node.end);
                current = node.next;
                traversed += 1;
                if traversed > self.nodes.len().saturating_add(1) {
                    return Err(IntervalUnionError::new(
                        "INTERVAL_UNION.DYNAMIC_NODE_CYCLE",
                        index.block_ids.get(block).copied(),
                        [],
                        "dynamic stack-slot union contains a node cycle",
                    ));
                }
            }
        }
        Ok(())
    }

    fn same_occupancy(&self, other: &Self) -> bool {
        if self.heads.len() != other.heads.len() {
            return false;
        }
        for block in 0..self.heads.len() {
            let mut left = self.heads.get(block);
            let mut right = other.heads.get(block);
            loop {
                match (left, right) {
                    (Self::NONE, Self::NONE) => break,
                    (Self::NONE, _) | (_, Self::NONE) => return false,
                    _ => {
                        let left_node = self.node(left, block).expect("occupied block has a node");
                        let right_node =
                            other.node(right, block).expect("occupied block has a node");
                        if (left_node.start, left_node.end) != (right_node.start, right_node.end) {
                            return false;
                        }
                        left = left_node.next;
                        right = right_node.next;
                    }
                }
            }
        }
        true
    }

    fn is_empty(&self) -> bool {
        self.heads.iter().all(|head| head == Self::NONE)
    }
}

#[derive(Debug, Clone)]
pub(super) struct DynamicIntervalMatrix {
    index: Arc<IntervalIndex>,
    unions: Vec<DynamicSlotUnion>,
    assignments: BTreeMap<AllocationBundleId, usize>,
    block_slot_counts: Vec<u32>,
    full_ends: Arc<[SlotIndex]>,
}

impl PartialEq for DynamicIntervalMatrix {
    fn eq(&self, other: &Self) -> bool {
        self.index == other.index
            && self.assignments == other.assignments
            && self.block_slot_counts == other.block_slot_counts
            && self.unions.len() == other.unions.len()
            && self
                .unions
                .iter()
                .zip(&other.unions)
                .all(|(left, right)| left.same_occupancy(right))
    }
}

impl Eq for DynamicIntervalMatrix {}

impl DynamicIntervalMatrix {
    pub(super) fn new(cfg: &NormalizedCfg) -> Result<Self, IntervalUnionError> {
        Ok(Self {
            index: Arc::new(IntervalIndex::new(cfg)?),
            unions: Vec::new(),
            assignments: BTreeMap::new(),
            block_slot_counts: vec![0; cfg.successors.len()],
            full_ends: Arc::from([]),
        })
    }

    /// Share canonical full-block occupancy without allocating one arena node
    /// for each block/stack-slot pair. Other intervals retain the exact arena.
    pub(super) fn with_block_ends(
        cfg: &NormalizedCfg,
        ends: &crate::HashMap<u32, u64>,
    ) -> Result<Self, IntervalUnionError> {
        let mut matrix = Self::new(cfg)?;
        matrix.full_ends = matrix
            .index
            .block_ids
            .iter()
            .map(|block| {
                ends.get(&block.0)
                    .copied()
                    .filter(|&end| end > 0)
                    .map(SlotIndex::from_u64)
                    .ok_or_else(|| {
                        IntervalUnionError::new(
                            "INTERVAL_UNION.BLOCK_ENDPOINT",
                            Some(*block),
                            [],
                            "full-block endpoint table does not cover the CFG",
                        )
                    })
            })
            .collect::<Result<Vec<_>, _>>()?
            .into();
        Ok(matrix)
    }

    pub(super) fn make_range(
        &self,
        segments: Vec<LiveSegment>,
    ) -> Result<SparseRange, IntervalUnionError> {
        self.index.make_range(segments)
    }

    fn validate_token(&self, segments: ValidatedSegments<'_>) -> Result<(), IntervalUnionError> {
        if !Arc::ptr_eq(&self.index, segments.index) {
            return Err(IntervalUnionError::new(
                "INTERVAL_UNION.RANGE_CFG",
                None,
                [],
                "sparse range belongs to a different normalized CFG",
            ));
        }
        Ok(())
    }

    pub(super) fn first_available_validated(
        &self,
        segments: ValidatedSegments<'_>,
    ) -> Result<usize, IntervalUnionError> {
        self.validate_token(segments)?;
        let Some(hint) = segments
            .block_indices
            .iter()
            .enumerate()
            .max_by_key(|&(_, &block)| self.block_slot_counts[block])
            .map(|(index, _)| index)
        else {
            return Ok(self.unions.len());
        };
        Ok(self
            .unions
            .iter()
            .position(|union| !union.interferes_indexed_with_hint(segments, hint))
            .unwrap_or(self.unions.len()))
    }

    pub(super) fn assign_validated(
        &mut self,
        bundle: AllocationBundleId,
        slot: usize,
        segments: ValidatedSegments<'_>,
    ) -> Result<(), IntervalUnionError> {
        self.validate_token(segments)?;
        if let Some(current) = self.assignments.get(&bundle) {
            return Err(IntervalUnionError::new(
                "INTERVAL_UNION.DUPLICATE_ASSIGNMENT",
                None,
                [bundle],
                format!("bundle is already assigned to dynamic slot {current}"),
            ));
        }
        if slot > self.unions.len() {
            return Err(IntervalUnionError::new(
                "INTERVAL_UNION.DYNAMIC_SLOT_RANGE",
                None,
                [bundle],
                format!("dynamic slot {slot} skips the current color domain"),
            ));
        }
        let mut newly_occupied_blocks = Vec::new();
        let mut previous_block = None;
        for (_, block) in segments.iter() {
            if previous_block == Some(block) {
                continue;
            }
            previous_block = Some(block);
            if slot == self.unions.len()
                || self.unions[slot].heads.get(block) == DynamicSlotUnion::NONE
            {
                newly_occupied_blocks.push(block);
            }
        }
        if slot == self.unions.len() {
            let mut union = DynamicSlotUnion::new(self.index.block_ids.len());
            union.full_ends = Arc::clone(&self.full_ends);
            union.insert_indexed(bundle, segments)?;
            self.unions.push(union);
        } else {
            self.unions[slot].insert_indexed(bundle, segments)?;
        }
        for block in newly_occupied_blocks {
            self.block_slot_counts[block] = self.block_slot_counts[block]
                .checked_add(1)
                .ok_or_else(|| {
                    IntervalUnionError::new(
                        "INTERVAL_UNION.BLOCK_SLOT_COUNT",
                        self.index.block_ids.get(block).copied(),
                        [bundle],
                        "dynamic stack-slot occupancy count exceeds u32",
                    )
                })?;
        }
        self.assignments.insert(bundle, slot);
        Ok(())
    }

    pub(super) fn slot_count(&self) -> usize {
        self.unions.len()
    }

    pub(super) fn slot(&self, bundle: AllocationBundleId) -> Option<usize> {
        self.assignments.get(&bundle).copied()
    }

    pub(super) fn verify(&self) -> Result<(), IntervalUnionError> {
        for (slot, union) in self.unions.iter().enumerate() {
            union.verify(&self.index)?;
            if union.is_empty() {
                return Err(IntervalUnionError::new(
                    "INTERVAL_UNION.EMPTY_DYNAMIC_SLOT",
                    None,
                    [],
                    format!("dynamic slot {slot} has no assigned sparse range"),
                ));
            }
        }
        if self
            .assignments
            .values()
            .any(|&slot| slot >= self.unions.len())
        {
            return Err(IntervalUnionError::new(
                "INTERVAL_UNION.ASSIGNMENT_MAP",
                None,
                [],
                "dynamic stack-slot assignment names a missing slot",
            ));
        }
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    #[test]
    fn full_block_heads_stay_compact_and_promote_exactly() {
        use super::{BlockHeads, DynamicSlotUnion};
        const BLOCKS: usize = 65_537;
        let mut heads = BlockHeads::new(BLOCKS);
        let mut expected = vec![DynamicSlotUnion::NONE; BLOCKS];
        for (block, expected_head) in expected.iter_mut().enumerate() {
            if block % 3 != 0 {
                heads.set(block, DynamicSlotUnion::FULL);
                *expected_head = DynamicSlotUnion::FULL;
            }
        }
        heads.set(64, 7);
        expected[64] = 7;
        heads.set(65, DynamicSlotUnion::NONE);
        expected[65] = DynamicSlotUnion::NONE;
        let BlockHeads::Sparse { full, partial, .. } = &heads else {
            panic!("full blocks need a bitmap")
        };
        assert!(full.len() * 8 + partial.capacity() * std::mem::size_of::<(usize, u32)>() < BLOCKS);
        assert_eq!(heads.iter().collect::<Vec<_>>(), expected);
        let saved = heads.clone();
        for (block, expected_head) in expected.iter_mut().enumerate() {
            heads.set(block, block as u32);
            *expected_head = block as u32;
        }
        assert!(matches!(heads, BlockHeads::Dense(_)));
        assert_eq!(heads.iter().collect::<Vec<_>>(), expected);
        assert_eq!(saved.get(64), 7);
        assert_eq!(saved.get(65), DynamicSlotUnion::NONE);
        heads.set(64, DynamicSlotUnion::FULL);
        heads.set(65, DynamicSlotUnion::NONE);
        assert_eq!(heads.get(64), DynamicSlotUnion::FULL);
        assert_eq!(heads.get(65), DynamicSlotUnion::NONE);
    }

    #[test]
    fn dynamic_nodes_promote_without_losing_slots_or_links() {
        let mut nodes = super::DynamicNodeArena::Packed(Vec::new());
        let first = super::DynamicUnionNode {
            start: super::SlotIndex::for_test(2),
            end: super::SlotIndex::for_test(u32::MAX as u64),
            next: u32::MAX,
        };
        nodes.push(first);
        assert_eq!(nodes.get(0), Some(first));
        assert!(matches!(nodes, super::DynamicNodeArena::Packed(_)));
        nodes.update(0, |node| {
            node.end = super::SlotIndex::for_test(u32::MAX as u64 + 1)
        });
        assert!(matches!(nodes, super::DynamicNodeArena::Wide(_)));
        assert_eq!(nodes.node(0).start, first.start);
        assert_eq!(nodes.node(0).next, first.next);
        assert_eq!(
            nodes.node(0).end,
            super::SlotIndex::for_test(u32::MAX as u64 + 1)
        );
        let wide = super::DynamicUnionNode {
            start: super::SlotIndex::for_test(u64::MAX - 1),
            end: super::SlotIndex::for_test(u64::MAX),
            next: 0,
        };
        nodes.push(wide);
        assert_eq!(nodes.get(1), Some(wide));
        assert_eq!(nodes.get(2), None);
        let mut direct = super::DynamicNodeArena::Packed(Vec::new());
        direct.push(wide);
        assert_eq!(direct.get(0), Some(wide));
    }

    use super::*;
    use crate::native::mir::{MBlock, MFunction, MInst, SpillDesc, VRegAllocator};

    fn one_block_cfg() -> NormalizedCfg {
        let mut block = MBlock::new(BlockId(0));
        block.push(MInst::Return);
        let mut function = MFunction::new(VRegAllocator::new(), Vec::<SpillDesc>::new());
        function.blocks.push(block);
        super::super::cfg::normalize(&mut function).unwrap()
    }

    #[test]
    fn dynamic_slot_merges_adjacent_ranges_in_any_insertion_order() {
        let cfg = one_block_cfg();
        let slot = |phase: u64| SlotIndex::for_test(phase);
        let segments = [
            LiveSegment {
                block: BlockId(0),
                start: slot(0),
                end: slot(1),
            },
            LiveSegment {
                block: BlockId(0),
                start: slot(1),
                end: slot(2),
            },
            LiveSegment {
                block: BlockId(0),
                start: slot(2),
                end: slot(3),
            },
        ];
        let build = |order: [usize; 3]| {
            let mut matrix = DynamicIntervalMatrix::new(&cfg).unwrap();
            for (bundle, segment) in order.into_iter().map(|index| segments[index]).enumerate() {
                let range = matrix.make_range(vec![segment]).unwrap();
                matrix
                    .assign_validated(AllocationBundleId(bundle as u32), 0, range.validated())
                    .unwrap();
            }
            matrix.verify().unwrap();
            matrix
        };
        assert_eq!(build([0, 2, 1]), build([2, 1, 0]));
    }

    #[test]
    fn full_block_heads_match_node_arena_across_merges_and_later_ranges() {
        let cfg = one_block_cfg();
        for segments in [
            vec![(0, 3)],
            vec![(0, 1), (2, 3), (1, 2)],
            vec![(2, 3), (1, 2), (0, 1)],
        ] {
            let mut reference = DynamicIntervalMatrix::new(&cfg).unwrap();
            let mut compact =
                DynamicIntervalMatrix::with_block_ends(&cfg, &[(0, 3)].into_iter().collect())
                    .unwrap();
            for (bundle, &(start, end)) in segments.iter().enumerate() {
                for matrix in [&mut reference, &mut compact] {
                    let range = matrix
                        .make_range(vec![LiveSegment {
                            block: BlockId(0),
                            start: SlotIndex::for_test(start),
                            end: SlotIndex::for_test(end),
                        }])
                        .unwrap();
                    matrix
                        .assign_validated(AllocationBundleId(bundle as u32), 0, range.validated())
                        .unwrap();
                    matrix.verify().unwrap();
                }
                assert_eq!(reference, compact);
            }
            assert_eq!(compact.unions[0].heads.get(0), DynamicSlotUnion::FULL);
            let overlapping = compact
                .make_range(vec![LiveSegment {
                    block: BlockId(0),
                    start: SlotIndex::for_test(1),
                    end: SlotIndex::for_test(2),
                }])
                .unwrap();
            assert_eq!(
                compact
                    .first_available_validated(overlapping.validated())
                    .unwrap(),
                1
            );
            assert!(
                compact
                    .assign_validated(AllocationBundleId(100), 0, overlapping.validated())
                    .is_err()
            );
            if segments.len() == 1 {
                assert_eq!(compact.unions[0].nodes.len(), 0);
            }
            for (bundle, (start, end)) in [(3, 5), (7, 9), (5, 7)].into_iter().enumerate() {
                for matrix in [&mut reference, &mut compact] {
                    let range = matrix
                        .make_range(vec![LiveSegment {
                            block: BlockId(0),
                            start: SlotIndex::for_test(start),
                            end: SlotIndex::for_test(end),
                        }])
                        .unwrap();
                    assert_eq!(
                        matrix.first_available_validated(range.validated()).unwrap(),
                        0
                    );
                    matrix
                        .assign_validated(
                            AllocationBundleId(10 + bundle as u32),
                            0,
                            range.validated(),
                        )
                        .unwrap();
                    matrix.verify().unwrap();
                }
                assert_eq!(reference, compact);
            }
        }
    }

    #[test]
    fn validated_range_cannot_cross_cfg_owners() {
        let first = DynamicIntervalMatrix::new(&one_block_cfg()).unwrap();
        let second = DynamicIntervalMatrix::new(&one_block_cfg()).unwrap();
        let range = first
            .make_range(vec![LiveSegment {
                block: BlockId(0),
                start: SlotIndex::for_test(0),
                end: SlotIndex::for_test(1),
            }])
            .unwrap();
        let error = second
            .first_available_validated(range.validated())
            .unwrap_err();
        assert_eq!(error.rule, "INTERVAL_UNION.RANGE_CFG");
    }
}