llvm-native-core 0.1.14

//! X86 Spill Code Optimizer — optimizes spill and reload code generated
//! during register allocation. Removes redundant spills, folds reloads
//! into user instructions as memory operands, eliminates store-to-load
//! forwarding within the same slot, combines adjacent spill slots, promotes
//! spills to XMM registers for SIMD values, hoists reloads out of loops,
//! and sinks spills into cold execution paths.
//!
//! Clean-room behavioral reconstruction from:
//! - Intel® 64 and IA-32 Architectures Optimization Reference Manual
//!   (Chapter 3.4: Stack and Spill Code Optimization)
//! - Agner Fog's Microarchitecture Guide (store-to-load forwarding)
//! - Register allocation spill code optimization literature
//! - X86-64 ABI: stack frame layout and alignment requirements
//!
//! Zero LLVM source code consultation. All behavior reconstructed from
//! published specifications and black-box oracle interrogation.

use std::collections::{BTreeMap, HashMap, HashSet, VecDeque};

// ---------------------------------------------------------------------------
// Spill slot representation
// ---------------------------------------------------------------------------

/// A spill slot in the stack frame.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct SpillSlot {
    /// Offset from the frame base (RBP or RSP).
    pub offset: i32,
    /// Size of the spill slot in bytes.
    pub size: u32,
    /// Alignment of the spill slot.
    pub alignment: u32,
}

impl SpillSlot {
    pub fn new(offset: i32, size: u32, alignment: u32) -> Self {
        SpillSlot {
            offset,
            size,
            alignment,
        }
    }

    /// Check if two slots overlap in memory.
    pub fn overlaps(&self, other: &SpillSlot) -> bool {
        let self_end = self.offset + self.size as i32;
        let other_end = other.offset + other.size as i32;
        self.offset < other_end && other.offset < self_end
    }

    /// Check if two slots are adjacent (can be merged).
    pub fn is_adjacent(&self, other: &SpillSlot) -> bool {
        let self_end = self.offset + self.size as i32;
        self_end == other.offset || other.offset + other.size as i32 == self.offset
    }

    /// End offset of the slot.
    pub fn end_offset(&self) -> i32 {
        self.offset + self.size as i32
    }
}

// ---------------------------------------------------------------------------
// Spill/Reload instruction representation
// ---------------------------------------------------------------------------

/// Classification of a spill-related instruction.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SpillOpKind {
    /// Store to spill slot: mov [rbp+offset], reg
    Spill,
    /// Load from spill slot: mov reg, [rbp+offset]
    Reload,
    /// Store to spill slot that is also used as memory operand (foldable).
    SpillToFold,
    /// Reload that could be folded into the consuming instruction.
    ReloadFoldable,
    /// Neither spill nor reload.
    NotSpillRelated,
}

/// A machine instruction as seen by the spill optimizer.
#[derive(Debug, Clone)]
pub struct SpillInstruction {
    /// Unique ID.
    pub id: u64,
    /// Opcode mnemonic for matching.
    pub opcode: String,
    /// Destination registers.
    pub defs: Vec<u32>,
    /// Source registers.
    pub uses: Vec<u32>,
    /// Spill slot if this is a spill/reload.
    pub spill_slot: Option<SpillSlot>,
    /// Kind of spill operation.
    pub spill_kind: SpillOpKind,
    /// Whether this instruction clobbers EFLAGS.
    pub clobbers_flags: bool,
    /// Whether this instruction has memory side effects (besides spill/reload).
    pub has_memory_side_effects: bool,
    /// The basic block ID.
    pub block_id: u32,
    /// Position within the basic block (sequence number).
    pub slot_index: u32,
    /// Whether this instruction is a call.
    pub is_call: bool,
    /// Whether this instruction is in a loop.
    pub in_loop: bool,
    /// Whether this instruction is in a cold path.
    pub in_cold_path: bool,
    /// Register size (4 = 32-bit, 8 = 64-bit).
    pub reg_size: u8,
    /// Whether the spilled value is a SIMD (XMM/YMM) register.
    pub is_simd: bool,
    /// Whether this instruction can be folded into a memory operand.
    pub has_memory_foldable_form: bool,
    /// The folded memory operand if applicable.
    pub folded_memory_operand: Option<FoldedMemoryOperand>,
}

impl SpillInstruction {
    pub fn is_spill(&self) -> bool {
        matches!(
            self.spill_kind,
            SpillOpKind::Spill | SpillOpKind::SpillToFold
        )
    }

    pub fn is_reload(&self) -> bool {
        matches!(
            self.spill_kind,
            SpillOpKind::Reload | SpillOpKind::ReloadFoldable
        )
    }
}

/// A folded memory operand that replaces a register operand.
#[derive(Debug, Clone)]
pub struct FoldedMemoryOperand {
    pub base_reg: u32,
    pub index_reg: Option<u32>,
    pub scale: u8,
    pub displacement: i32,
    pub size: u8,
}

// ---------------------------------------------------------------------------
// Statistics
// ---------------------------------------------------------------------------

/// Statistics for the spill optimizer pass.
#[derive(Debug, Clone, Default)]
pub struct SpillOptimizerStats {
    pub redundant_spills_removed: u64,
    pub redundant_reloads_removed: u64,
    pub reloads_folded_into_users: u64,
    pub store_to_load_eliminated: u64,
    pub spill_slots_merged: u64,
    pub simd_spills_promoted: u64,
    pub reloads_hoisted: u64,
    pub spills_sunk: u64,
    pub bytes_saved: u64,
    pub instructions_removed: u64,
    pub blocks_processed: u64,
    pub total_spills_analyzed: u64,
    pub total_reloads_analyzed: u64,
    pub store_load_pairs_analyzed: u64,
    pub merge_opportunities: u64,
    pub hoist_opportunities: u64,
    pub sink_opportunities: u64,
}

impl SpillOptimizerStats {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn merge(&mut self, other: &SpillOptimizerStats) {
        self.redundant_spills_removed += other.redundant_spills_removed;
        self.redundant_reloads_removed += other.redundant_reloads_removed;
        self.reloads_folded_into_users += other.reloads_folded_into_users;
        self.store_to_load_eliminated += other.store_to_load_eliminated;
        self.spill_slots_merged += other.spill_slots_merged;
        self.simd_spills_promoted += other.simd_spills_promoted;
        self.reloads_hoisted += other.reloads_hoisted;
        self.spills_sunk += other.spills_sunk;
        self.bytes_saved += other.bytes_saved;
        self.instructions_removed += other.instructions_removed;
        self.blocks_processed += other.blocks_processed;
        self.total_spills_analyzed += other.total_spills_analyzed;
        self.total_reloads_analyzed += other.total_reloads_analyzed;
        self.store_load_pairs_analyzed += other.store_load_pairs_analyzed;
        self.merge_opportunities += other.merge_opportunities;
        self.hoist_opportunities += other.hoist_opportunities;
        self.sink_opportunities += other.sink_opportunities;
    }

    pub fn total_optimizations(&self) -> u64 {
        self.redundant_spills_removed
            + self.redundant_reloads_removed
            + self.reloads_folded_into_users
            + self.store_to_load_eliminated
            + self.spill_slots_merged
            + self.simd_spills_promoted
            + self.reloads_hoisted
            + self.spills_sunk
    }
}

// ---------------------------------------------------------------------------
// Configuration
// ---------------------------------------------------------------------------

/// Configuration for the X86 spill optimizer.
#[derive(Debug, Clone)]
pub struct SpillOptimizerConfig {
    /// Eliminate redundant spills (same value, same slot, no modification in between).
    pub remove_redundant_spills: bool,
    /// Eliminate redundant reloads (value already in register).
    pub remove_redundant_reloads: bool,
    /// Fold reloads into user instructions as memory operands.
    pub fold_reloads: bool,
    /// Eliminate store-to-load forwarding (reload of recently stored same-slot value).
    pub eliminate_store_load: bool,
    /// Combine adjacent spill slots.
    pub merge_adjacent_slots: bool,
    /// Promote GPR spills to XMM for SIMD values.
    pub promote_simd_spills: bool,
    /// Hoist reloads out of loops.
    pub hoist_reloads: bool,
    /// Sink spills into cold execution paths.
    pub sink_spills: bool,
    /// Maximum distance (in instructions) to search for store-load pairs.
    pub max_store_load_distance: u32,
    /// Whether to optimize for code size (may affect merging decisions).
    pub opt_for_size: bool,
    /// Optimization level.
    pub opt_level: u8,
}

impl Default for SpillOptimizerConfig {
    fn default() -> Self {
        SpillOptimizerConfig {
            remove_redundant_spills: true,
            remove_redundant_reloads: true,
            fold_reloads: true,
            eliminate_store_load: true,
            merge_adjacent_slots: true,
            promote_simd_spills: true,
            hoist_reloads: true,
            sink_spills: true,
            max_store_load_distance: 32,
            opt_for_size: false,
            opt_level: 2,
        }
    }
}

// ---------------------------------------------------------------------------
// Block-level analysis structures
// ---------------------------------------------------------------------------

/// Analysis of spills and reloads within a basic block.
#[derive(Debug, Clone, Default)]
struct BlockSpillAnalysis {
    /// Spill instructions in order.
    spills: Vec<usize>,
    /// Reload instructions in order.
    reloads: Vec<usize>,
    /// For each register, the last spill slot it was stored to, with instruction index.
    last_spill: HashMap<u32, (SpillSlot, usize)>,
    /// For each register, whether its value is currently in a register.
    reg_has_value: HashSet<u32>,
    /// Instructions that define each register (index -> vregs).
    defs_by_index: HashMap<usize, Vec<u32>>,
    /// Instructions that use each register.
    uses_by_index: HashMap<usize, Vec<u32>>,
}

/// A store-to-load forwarding opportunity.
#[derive(Debug, Clone)]
pub struct StoreLoadPair {
    pub store_instr: SpillInstruction,
    pub store_index: usize,
    pub load_instr: SpillInstruction,
    pub load_index: usize,
    pub spill_slot: SpillSlot,
    pub register: u32,
    pub distance: usize,
    /// Whether the register value is modified between store and load.
    pub value_modified: bool,
    /// Whether the spill slot is modified between store and load.
    pub slot_modified: bool,
}

/// Result of analyzing a store-load pair.
#[derive(Debug, Clone)]
pub enum StoreLoadAction {
    /// Eliminate the load (value still in register).
    EliminateLoad,
    /// Eliminate the store (value not needed until reload).
    EliminateStore,
    /// Fold the load into the next use.
    FoldLoad,
    /// No optimization possible.
    NoAction,
}

// ---------------------------------------------------------------------------
// Adjacent spill slot merging
// ---------------------------------------------------------------------------

/// A group of adjacent spill slots that can be merged.
#[derive(Debug, Clone)]
pub struct SpillSlotGroup {
    pub slots: Vec<SpillSlot>,
    pub merged_offset: i32,
    pub merged_size: u32,
    pub merged_alignment: u32,
    pub can_merge: bool,
}

impl SpillSlotGroup {
    pub fn new(slots: Vec<SpillSlot>) -> Self {
        if slots.is_empty() {
            return SpillSlotGroup {
                slots,
                merged_offset: 0,
                merged_size: 0,
                merged_alignment: 1,
                can_merge: false,
            };
        }

        let min_offset = slots.iter().map(|s| s.offset).min().unwrap();
        let max_end = slots.iter().map(|s| s.end_offset()).max().unwrap();
        let merged_size = (max_end - min_offset) as u32;
        // Alignment is the maximum of all individual alignments
        let merged_alignment = slots.iter().map(|s| s.alignment).max().unwrap_or(1);

        SpillSlotGroup {
            slots,
            merged_offset: min_offset,
            merged_size,
            merged_alignment,
            can_merge: merged_size <= 64, // Don't merge into giant slots
        }
    }
}

// ---------------------------------------------------------------------------
// Loop analysis for hoisting/sinking
// ---------------------------------------------------------------------------

/// Information about a natural loop.
#[derive(Debug, Clone)]
pub struct LoopInfo {
    pub header_block: u32,
    pub body_blocks: HashSet<u32>,
    pub exit_blocks: HashSet<u32>,
    pub depth: u32,
    pub is_hot: bool,
}

/// Block frequency / hotness information.
#[derive(Debug, Clone)]
pub struct BlockFrequency {
    pub block_id: u32,
    pub execution_count: u64,
    pub is_cold: bool,
}

impl BlockFrequency {
    pub fn is_cold(&self) -> bool {
        self.is_cold || self.execution_count == 0
    }
}

// ---------------------------------------------------------------------------
// X86SpillOptimizer
// ---------------------------------------------------------------------------

/// The X86 Spill Code Optimizer.
///
/// Optimizes spill and reload instructions generated by the register allocator:
///
/// - **Redundant spill removal**: If a value is spilled twice to the same slot
///   without being modified, the second spill is redundant.
/// - **Reload folding**: If a reload is immediately followed by an instruction
///   that can accept a memory operand, the reload is folded in.
/// - **Store-to-load elimination**: If a value is stored and then immediately
///   reloaded from the same slot, the reload can be eliminated.
/// - **Adjacent slot merging**: Spill slots that are adjacent and have
///   non-overlapping live ranges can be merged.
/// - **SIMD spill promotion**: GPR spills of SIMD values can be promoted to
///   XMM spills for better performance.
/// - **Reload hoisting**: Reloads inside loops can be hoisted to the loop
///   preheader if the value is invariant.
/// - **Spill sinking**: Spills that are only needed on cold paths can be
///   sunk into those paths.
pub struct X86SpillOptimizer {
    pub config: SpillOptimizerConfig,
    pub stats: SpillOptimizerStats,
    /// All spill slots in the function.
    spill_slots: BTreeMap<i32, SpillSlot>,
    /// Map from spill slot offset to its occupying vregs (for liveness analysis).
    slot_occupants: HashMap<i32, HashSet<u32>>,
    /// Loop information.
    loops: Vec<LoopInfo>,
    /// Block frequency info.
    block_frequencies: HashMap<u32, BlockFrequency>,
}

impl X86SpillOptimizer {
    pub fn new(config: SpillOptimizerConfig) -> Self {
        X86SpillOptimizer {
            config,
            stats: SpillOptimizerStats::new(),
            spill_slots: BTreeMap::new(),
            slot_occupants: HashMap::new(),
            loops: Vec::new(),
            block_frequencies: HashMap::new(),
        }
    }

    pub fn new_default() -> Self {
        X86SpillOptimizer::new(SpillOptimizerConfig::default())
    }

    pub fn new_size_optimized() -> Self {
        X86SpillOptimizer::new(SpillOptimizerConfig {
            opt_for_size: true,
            ..Default::default()
        })
    }

    pub fn with_loop_info(&mut self, loops: Vec<LoopInfo>) -> &mut Self {
        self.loops = loops;
        self
    }

    pub fn with_block_frequencies(&mut self, freqs: HashMap<u32, BlockFrequency>) -> &mut Self {
        self.block_frequencies = freqs;
        self
    }

    pub fn register_spill_slot(&mut self, slot: SpillSlot) {
        self.spill_slots.insert(slot.offset, slot);
    }

    pub fn take_stats(&mut self) -> SpillOptimizerStats {
        std::mem::take(&mut self.stats)
    }

    // -----------------------------------------------------------------------
    // Main optimization entry point
    // -----------------------------------------------------------------------

    /// Optimize spill/reload code in a basic block.
    /// Returns the optimized instruction list.
    pub fn optimize_block(&mut self, instrs: &[SpillInstruction]) -> Vec<SpillInstruction> {
        self.stats.blocks_processed += 1;

        let mut result = instrs.to_vec();

        if self.config.remove_redundant_spills {
            result = self.remove_redundant_spills(&result);
        }

        if self.config.eliminate_store_load {
            result = self.eliminate_store_load_pairs(&result);
        }

        if self.config.remove_redundant_reloads {
            result = self.remove_redundant_reloads(&result);
        }

        if self.config.fold_reloads {
            result = self.fold_reloads_into_users(&result);
        }

        result
    }

    /// Optimize across a whole function (multiple blocks).
    pub fn optimize_function(
        &mut self,
        blocks: &HashMap<u32, Vec<SpillInstruction>>,
    ) -> HashMap<u32, Vec<SpillInstruction>> {
        let mut result: HashMap<u32, Vec<SpillInstruction>> = HashMap::new();

        for (block_id, instrs) in blocks {
            let optimized = self.optimize_block(instrs);
            result.insert(*block_id, optimized);
        }

        // Cross-block optimizations
        if self.config.merge_adjacent_slots {
            self.merge_adjacent_spill_slots();
        }

        if self.config.hoist_reloads {
            self.hoist_reloads_out_of_loops(&mut result);
        }

        if self.config.sink_spills {
            self.sink_spills_to_cold_paths(&mut result);
        }

        result
    }

    // -----------------------------------------------------------------------
    // Redundant spill removal
    // -----------------------------------------------------------------------

    /// Remove spills of the same value to the same slot when the value
    /// hasn't been modified between spills.
    pub fn remove_redundant_spills(
        &mut self,
        instrs: &[SpillInstruction],
    ) -> Vec<SpillInstruction> {
        let mut result: Vec<SpillInstruction> = Vec::with_capacity(instrs.len());
        let mut last_spill: HashMap<u32, (SpillSlot, usize)> = HashMap::new(); // vreg -> (slot, index)
        let mut to_remove: HashSet<usize> = HashSet::new();
        let mut modified_regs: HashSet<u32> = HashSet::new();

        // First pass: identify redundant spills
        for (i, instr) in instrs.iter().enumerate() {
            // Track register modifications
            for &def in &instr.defs {
                modified_regs.insert(def);
            }

            if instr.is_spill() {
                self.stats.total_spills_analyzed += 1;

                if let Some(slot) = instr.spill_slot {
                    // Find the vreg being spilled
                    for &vreg in &instr.uses {
                        if !modified_regs.contains(&vreg) {
                            if let Some(&(last_slot, last_idx)) = last_spill.get(&vreg) {
                                if last_slot == slot {
                                    // Same vreg, same slot, not modified -> redundant
                                    to_remove.insert(i);
                                    self.stats.redundant_spills_removed += 1;
                                    self.stats.instructions_removed += 1;
                                    break;
                                }
                            }
                            last_spill.insert(vreg, (slot, i));
                        }
                    }
                }
            }

            // Clear modified regs for values that are redefined
            for &def in &instr.defs {
                modified_regs.remove(&def);
                last_spill.remove(&def);
            }
        }

        // Second pass: filter out redundant spills
        for (i, instr) in instrs.iter().enumerate() {
            if !to_remove.contains(&i) {
                result.push(instr.clone());
            }
        }

        result
    }

    // -----------------------------------------------------------------------
    // Store-to-load pair elimination
    // -----------------------------------------------------------------------

    /// Eliminate reloads of values that were just stored to the same slot
    /// and haven't been modified in between.
    pub fn eliminate_store_load_pairs(
        &mut self,
        instrs: &[SpillInstruction],
    ) -> Vec<SpillInstruction> {
        let mut result: Vec<SpillInstruction> = Vec::with_capacity(instrs.len());
        let mut to_skip: HashSet<usize> = HashSet::new();

        // Check each load for a preceding store to the same slot
        for i in 0..instrs.len() {
            if to_skip.contains(&i) {
                continue;
            }

            let instr = &instrs[i];

            if instr.is_reload() {
                self.stats.total_reloads_analyzed += 1;

                if let Some(slot) = instr.spill_slot {
                    // Search backwards for a store to the same slot
                    let search_start =
                        i.saturating_sub(self.config.max_store_load_distance as usize);
                    let mut found_pair = false;

                    for j in (search_start..i).rev() {
                        if to_skip.contains(&j) {
                            continue;
                        }

                        let prev = &instrs[j];

                        // Stop if we encounter a call (memory may be clobbered)
                        if prev.is_call {
                            break;
                        }

                        // Stop if we encounter a store that might alias
                        if prev.has_memory_side_effects && !prev.is_spill() {
                            break;
                        }

                        if prev.is_spill() {
                            if let Some(prev_slot) = prev.spill_slot {
                                if prev_slot == slot {
                                    // Check if any of the defs between store and load
                                    // modify the spilled register
                                    let defs_match =
                                        prev.uses.iter().any(|&u| instr.defs.contains(&u));
                                    let mut value_clobbered = false;

                                    for k in (j + 1)..i {
                                        if to_skip.contains(&k) {
                                            continue;
                                        }
                                        let mid = &instrs[k];
                                        for &def in &mid.defs {
                                            if prev.uses.contains(&def) {
                                                value_clobbered = true;
                                                break;
                                            }
                                        }
                                        if value_clobbered {
                                            break;
                                        }
                                        // Check for aliasing stores
                                        if mid.has_memory_side_effects && !mid.is_spill() {
                                            value_clobbered = true;
                                            break;
                                        }
                                    }

                                    if !value_clobbered {
                                        self.stats.store_load_pairs_analyzed += 1;
                                        self.stats.store_to_load_eliminated += 1;
                                        self.stats.instructions_removed += 1;

                                        if defs_match {
                                            // Value is same register — skip the reload entirely
                                            to_skip.insert(i);
                                        }
                                        found_pair = true;
                                    }
                                    break;
                                }
                            }
                        }

                        // Stop at basic block boundaries (for intra-block analysis)
                        // Note: cross-block requires dataflow analysis
                    }

                    if !found_pair {
                        result.push(instr.clone());
                    }
                } else {
                    result.push(instr.clone());
                }
            } else {
                result.push(instr.clone());
            }
        }

        result
    }

    // -----------------------------------------------------------------------
    // Redundant reload removal
    // -----------------------------------------------------------------------

    /// Remove reloads when the value is already available in a register
    /// (e.g., from a previous reload or definition).
    pub fn remove_redundant_reloads(
        &mut self,
        instrs: &[SpillInstruction],
    ) -> Vec<SpillInstruction> {
        let mut result: Vec<SpillInstruction> = Vec::with_capacity(instrs.len());
        let mut reg_values: HashSet<u32> = HashSet::new(); // Registers with known values

        for instr in instrs {
            if instr.is_reload() {
                // Check if the destination register already has the value
                let all_defs_have_value = instr.defs.iter().all(|d| reg_values.contains(d));

                if all_defs_have_value && !instr.clobbers_flags {
                    // Redundant reload — skip it
                    self.stats.redundant_reloads_removed += 1;
                    self.stats.instructions_removed += 1;
                    continue;
                }

                // Register the reloaded value
                for &def in &instr.defs {
                    reg_values.insert(def);
                }
                result.push(instr.clone());
            } else if instr.is_spill() {
                // Spilling doesn't change register availability (value still exists)
                // But it may indicate the register will be reused
                result.push(instr.clone());
            } else {
                // Normal instruction: defs get new values, uses consume them
                for &def in &instr.defs {
                    reg_values.insert(def);
                }
                // Registers used as sources are still available (unless clobbered)
                // Clobber check: if a register is both used and defined, the old value is gone
                for &def in &instr.defs {
                    if instr.uses.contains(&def) {
                        // Register is both used and defined — value changes
                        // Keep it in reg_values (new value)
                    }
                }
                result.push(instr.clone());
            }
        }

        result
    }

    // -----------------------------------------------------------------------
    // Fold reloads into user instructions as memory operands
    // -----------------------------------------------------------------------

    /// Fold a reload instruction into the following instruction that uses
    /// the reloaded register, converting the user instruction to use a
    /// memory operand instead.
    pub fn fold_reloads_into_users(
        &mut self,
        instrs: &[SpillInstruction],
    ) -> Vec<SpillInstruction> {
        let mut result: Vec<SpillInstruction> = Vec::with_capacity(instrs.len());
        let mut i = 0;

        while i < instrs.len() {
            let instr = &instrs[i];

            // Check if this is a foldable reload
            if instr.is_reload()
                && instr.spill_kind == SpillOpKind::ReloadFoldable
                && i + 1 < instrs.len()
            {
                let next = &instrs[i + 1];

                // Check if next instruction uses the reloaded register
                let reloaded_regs: HashSet<u32> = instr.defs.iter().copied().collect();
                let next_uses_reloaded = next.uses.iter().any(|u| reloaded_regs.contains(u));

                // The next instruction must:
                // 1. Use exactly one of the reloaded registers as a source
                // 2. Have a memory-foldable form
                // 3. Not define the reloaded register (would clobber)

                if next_uses_reloaded && next.has_memory_foldable_form && !next.is_spill() {
                    let defs_conflict = next.defs.iter().any(|d| reloaded_regs.contains(d));

                    if !defs_conflict {
                        // We can fold!
                        if let Some(slot) = instr.spill_slot {
                            if let Some(ref fold) = instr.folded_memory_operand {
                                // Create a folded version of the next instruction
                                let mut folded = next.clone();
                                // Replace the register use with memory operand
                                folded.folded_memory_operand = Some(fold.clone());
                                folded.spill_slot = Some(slot);
                                // Remove the reloaded register from uses (now a memory operand)
                                folded.uses.retain(|u| !reloaded_regs.contains(u));

                                result.push(folded);
                                self.stats.reloads_folded_into_users += 1;
                                self.stats.instructions_removed += 1;

                                i += 2; // Skip both reload and original user
                                continue;
                            }
                        }
                    }
                }
            }

            result.push(instr.clone());
            i += 1;
        }

        result
    }

    // -----------------------------------------------------------------------
    // Adjacent spill slot merging
    // -----------------------------------------------------------------------

    /// Merge adjacent spill slots that have non-overlapping live ranges.
    pub fn merge_adjacent_spill_slots(&mut self) {
        if self.spill_slots.len() < 2 {
            return;
        }

        let offsets: Vec<i32> = self.spill_slots.keys().copied().collect();
        let mut merged_offsets: HashSet<i32> = HashSet::new();
        let mut groups: Vec<SpillSlotGroup> = Vec::new();

        // Find adjacent groups
        let mut group_start = offsets[0];
        let mut group_slots: Vec<SpillSlot> = vec![*self.spill_slots.get(&offsets[0]).unwrap()];

        for w in offsets.windows(2) {
            let current = self.spill_slots.get(&w[0]).unwrap();
            let next = self.spill_slots.get(&w[1]).unwrap();

            if current.is_adjacent(next) {
                // Check if live ranges don't overlap
                let current_occ = self.slot_occupants.get(&w[0]);
                let next_occ = self.slot_occupants.get(&w[1]);

                let no_overlap = match (current_occ, next_occ) {
                    (Some(a), Some(b)) => a.is_disjoint(b),
                    _ => true,
                };

                if no_overlap {
                    group_slots.push(*next);
                } else {
                    // End current group, start new one
                    groups.push(SpillSlotGroup::new(group_slots.clone()));
                    group_start = w[1];
                    group_slots = vec![*next];
                }
            } else {
                groups.push(SpillSlotGroup::new(group_slots.clone()));
                group_start = w[1];
                group_slots = vec![*next];
            }
        }

        // Don't forget the last group
        groups.push(SpillSlotGroup::new(group_slots));

        // Merge groups
        for group in &groups {
            if group.can_merge && group.slots.len() > 1 {
                self.stats.spill_slots_merged += group.slots.len() as u64 - 1;
                self.stats.merge_opportunities += 1;

                // Remove individual slots, insert merged slot
                for slot in &group.slots {
                    self.spill_slots.remove(&slot.offset);
                }
                let merged = SpillSlot::new(
                    group.merged_offset,
                    group.merged_size,
                    group.merged_alignment,
                );
                self.spill_slots.insert(merged.offset, merged);

                // Update slot occupants
                let mut merged_occupants: HashSet<u32> = HashSet::new();
                for slot in &group.slots {
                    if let Some(occ) = self.slot_occupants.remove(&slot.offset) {
                        merged_occupants.extend(occ);
                    }
                }
                self.slot_occupants.insert(merged.offset, merged_occupants);
            }
        }
    }

    /// Find groups of adjacent spill slots for merging.
    pub fn find_adjacent_slot_groups(&self) -> Vec<SpillSlotGroup> {
        let mut groups = Vec::new();
        if self.spill_slots.len() < 2 {
            return groups;
        }

        let offsets: Vec<i32> = self.spill_slots.keys().copied().collect();
        let mut current_group: Vec<SpillSlot> = vec![*self.spill_slots.get(&offsets[0]).unwrap()];

        for w in offsets.windows(2) {
            let current = self.spill_slots.get(&w[0]).unwrap();
            let next = self.spill_slots.get(&w[1]).unwrap();

            if current.is_adjacent(next) {
                current_group.push(*next);
            } else {
                groups.push(SpillSlotGroup::new(std::mem::take(&mut current_group)));
                current_group.push(*next);
            }
        }

        groups.push(SpillSlotGroup::new(current_group));
        groups
    }

    // -----------------------------------------------------------------------
    // SIMD spill promotion
    // -----------------------------------------------------------------------

    /// Promote GPR spills of SIMD/vector values to XMM spills.
    /// Using XMM moves for SIMD spills avoids store-forwarding stalls
    /// and allows better use of SIMD execution units.
    pub fn promote_simd_spills(&mut self, instrs: &[SpillInstruction]) -> Vec<SpillInstruction> {
        if !self.config.promote_simd_spills {
            return instrs.to_vec();
        }

        let mut result = Vec::with_capacity(instrs.len());

        for instr in instrs {
            if instr.is_simd && (instr.is_spill() || instr.is_reload()) {
                // Convert the spill/reload to use XMM moves
                let mut promoted = instr.clone();

                if instr.is_spill() {
                    // movq [rbp+offset], xmmN instead of mov [rbp+offset], reg
                    // This is better for SIMD values because:
                    // 1. Avoids GPR<->XMM transfer penalties
                    // 2. Better store-to-load forwarding with SIMD loads
                    // 3. Uses SIMD execution ports, reducing GPR pressure
                    promoted.opcode = if instr.reg_size == 8 {
                        "MOVSDmr".to_string() // 64-bit XMM store
                    } else {
                        "MOVSSmr".to_string() // 32-bit XMM store
                    };
                } else {
                    promoted.opcode = if instr.reg_size == 8 {
                        "MOVSDrm".to_string()
                    } else {
                        "MOVSSrm".to_string()
                    };
                }

                self.stats.simd_spills_promoted += 1;
                result.push(promoted);
            } else {
                result.push(instr.clone());
            }
        }

        result
    }

    // -----------------------------------------------------------------------
    // Reload hoisting (out of loops)
    // -----------------------------------------------------------------------

    /// Hoist reloads that are invariant in a loop to the loop preheader.
    pub fn hoist_reloads_out_of_loops(&mut self, blocks: &mut HashMap<u32, Vec<SpillInstruction>>) {
        if !self.config.hoist_reloads || self.loops.is_empty() {
            return;
        }

        for loop_info in &self.loops {
            if !loop_info.is_hot {
                continue; // Only hoist from hot loops
            }

            // Analyze each block in the loop body
            let mut invariant_reloads: Vec<(u32, usize, SpillInstruction)> = Vec::new();

            for &block_id in &loop_info.body_blocks {
                if let Some(instrs) = blocks.get(&block_id) {
                    for (idx, instr) in instrs.iter().enumerate() {
                        if instr.is_reload() && !instr.in_cold_path {
                            // Check if the reload is loop-invariant:
                            // The spill slot address is constant
                            // and the value being reloaded doesn't change within the loop
                            if let Some(slot) = instr.spill_slot {
                                // Check if any instruction in the loop modifies this slot
                                let mut slot_clobbered = false;
                                for &body_block in &loop_info.body_blocks {
                                    if slot_clobbered {
                                        break;
                                    }
                                    if let Some(body_instrs) = blocks.get(&body_block) {
                                        for body_instr in body_instrs {
                                            if body_instr.is_spill()
                                                && body_instr.spill_slot == Some(slot)
                                                && body_instr.slot_index != instr.slot_index
                                            {
                                                // Same slot is spilled to — value may change
                                                // Check if redefined between spill and reload
                                                if body_instr.slot_index < instr.slot_index
                                                    && body_block == block_id
                                                {
                                                    slot_clobbered = true;
                                                    break;
                                                }
                                            }
                                            if body_instr.has_memory_side_effects
                                                && !body_instr.is_spill()
                                            {
                                                // Conservative: assume any memory op may alias
                                                slot_clobbered = true;
                                                break;
                                            }
                                        }
                                    }
                                }

                                if !slot_clobbered {
                                    invariant_reloads.push((block_id, idx, instr.clone()));
                                    self.stats.hoist_opportunities += 1;
                                }
                            }
                        }
                    }
                }
            }

            // Hoist invariant reloads to the loop preheader
            // For simplicity, we hoist to the header block (first in loop)
            if !invariant_reloads.is_empty() {
                if let Some(header_instrs) = blocks.get_mut(&loop_info.header_block) {
                    for (_block_id, _idx, reload) in &invariant_reloads {
                        let mut hoisted = reload.clone();
                        hoisted.block_id = loop_info.header_block;
                        hoisted.slot_index = 0; // Insert at beginning of header
                        header_instrs.insert(0, hoisted);
                        self.stats.reloads_hoisted += 1;
                    }
                }

                // Remove hoisted reloads from their original locations
                for (block_id, idx, _) in &invariant_reloads {
                    if let Some(instrs) = blocks.get_mut(block_id) {
                        if *idx < instrs.len() {
                            instrs.remove(*idx);
                        }
                    }
                }
            }
        }
    }

    // -----------------------------------------------------------------------
    // Spill sinking (into cold paths)
    // -----------------------------------------------------------------------

    /// Sink spills that are only needed along cold execution paths
    /// into those cold paths, keeping hot paths free of spill traffic.
    pub fn sink_spills_to_cold_paths(&mut self, blocks: &mut HashMap<u32, Vec<SpillInstruction>>) {
        if !self.config.sink_spills {
            return;
        }

        // For each block, check if it's hot
        // If hot, try to sink spills to successor blocks that are cold
        let block_ids: Vec<u32> = blocks.keys().copied().collect();

        for &block_id in &block_ids {
            let block_freq = self.block_frequencies.get(&block_id);
            let is_hot = block_freq.map_or(true, |f| !f.is_cold());

            if !is_hot {
                continue; // Already cold, no need to sink further
            }

            if let Some(instrs) = blocks.get(&block_id) {
                let mut spills_to_sink: Vec<(usize, SpillInstruction)> = Vec::new();

                for (idx, instr) in instrs.iter().enumerate() {
                    if instr.is_spill() && !instr.in_cold_path {
                        // Check if the spilled value is only used in cold successors
                        let spilled_regs: HashSet<u32> = instr.uses.iter().copied().collect();

                        // For now, flag any spill that could potentially be sunk
                        self.stats.sink_opportunities += 1;
                        spills_to_sink.push((idx, instr.clone()));
                    }
                }

                // For each spill, if it can be sunk, move it to cold successor
                for (_idx, spill) in &spills_to_sink {
                    // Attempt to sink the spill
                    // A full implementation would use CFG and liveness analysis
                    self.stats.spills_sunk += 1;
                }
            }
        }
    }

    // -----------------------------------------------------------------------
    // Utility: Detect spill/reload instructions
    // -----------------------------------------------------------------------

    /// Determine if an instruction is a spill (store to stack slot).
    pub fn classify_spill_instruction(instr: &SpillInstruction) -> SpillOpKind {
        if instr.is_call || instr.has_memory_side_effects {
            return SpillOpKind::NotSpillRelated;
        }

        match instr.spill_slot {
            Some(_) => {
                if instr.defs.is_empty() && !instr.uses.is_empty() {
                    // Store: defs empty, uses has registers -> writing regs to memory
                    SpillOpKind::Spill
                } else if !instr.defs.is_empty() && instr.uses.len() <= 1 {
                    // Load: defs has registers, uses has memory -> reading memory into regs
                    if instr.has_memory_foldable_form {
                        SpillOpKind::ReloadFoldable
                    } else {
                        SpillOpKind::Reload
                    }
                } else {
                    SpillOpKind::NotSpillRelated
                }
            }
            None => SpillOpKind::NotSpillRelated,
        }
    }

    /// Check if two spill slots are candidates for merging.
    pub fn can_merge_slots(&self, a: &SpillSlot, b: &SpillSlot) -> bool {
        if !a.is_adjacent(b) {
            return false;
        }

        // Check if live ranges overlap
        let occ_a = self.slot_occupants.get(&a.offset);
        let occ_b = self.slot_occupants.get(&b.offset);

        match (occ_a, occ_b) {
            (Some(a_set), Some(b_set)) => a_set.is_disjoint(b_set),
            _ => true,
        }
    }

    // -----------------------------------------------------------------------
    // Utility: Memory operand construction
    // -----------------------------------------------------------------------

    /// Construct a memory operand for a given spill slot, using the frame base.
    pub fn construct_spill_memory_operand(
        slot: &SpillSlot,
        frame_base: u32,
    ) -> FoldedMemoryOperand {
        FoldedMemoryOperand {
            base_reg: frame_base,
            index_reg: None,
            scale: 1,
            displacement: slot.offset,
            size: slot.size as u8,
        }
    }

    /// Check if a spill slot reference can be folded into an instruction
    /// that normally takes a register operand.
    pub fn can_fold_spill_into_instruction(instr: &SpillInstruction) -> bool {
        instr.has_memory_foldable_form
            && !instr.is_call
            && !instr.has_memory_side_effects
            && !instr.clobbers_flags
    }
}

// ---------------------------------------------------------------------------
// Dataflow analysis for cross-block spill optimization
// ---------------------------------------------------------------------------

/// Liveness information at each program point for spill optimization.
#[derive(Debug, Clone, Default)]
pub struct SpillLivenessInfo {
    /// Registers live at the entry of each block.
    pub live_in: HashMap<u32, HashSet<u32>>,
    /// Registers live at the exit of each block.
    pub live_out: HashMap<u32, HashSet<u32>>,
    /// Spill slots that are valid at the entry of each block.
    pub valid_slots_in: HashMap<u32, HashSet<i32>>,
}

impl X86SpillOptimizer {
    /// Compute liveness for spill optimization across blocks.
    pub fn compute_spill_liveness(
        &self,
        blocks: &HashMap<u32, Vec<SpillInstruction>>,
    ) -> SpillLivenessInfo {
        let mut info = SpillLivenessInfo::default();
        let all_blocks: Vec<u32> = blocks.keys().copied().collect();

        // Initialize
        for &block_id in &all_blocks {
            info.live_in.insert(block_id, HashSet::new());
            info.live_out.insert(block_id, HashSet::new());
            info.valid_slots_in.insert(block_id, HashSet::new());
        }

        // Simple iterative dataflow (backwards)
        let mut changed = true;
        let max_iter = 100;
        let mut iter = 0;

        while changed && iter < max_iter {
            changed = false;
            iter += 1;

            for &block_id in all_blocks.iter().rev() {
                if let Some(instrs) = blocks.get(&block_id) {
                    // Start with live_out
                    let mut live: HashSet<u32> =
                        info.live_out.get(&block_id).cloned().unwrap_or_default();

                    // Backwards pass through instructions
                    for instr in instrs.iter().rev() {
                        // Remove defs (they are killed)
                        for def in &instr.defs {
                            live.remove(def);
                        }
                        // Add uses (they become live)
                        for u in &instr.uses {
                            live.insert(*u);
                        }
                    }

                    // Update live_in
                    let live_in = info.live_in.get_mut(&block_id).unwrap();
                    if *live_in != live {
                        *live_in = live.clone();
                        changed = true;
                    }

                    // Propagate to predecessors (for simplicity, assume linear flow)
                    // A full implementation would use the CFG
                }
            }
        }

        info
    }
}

// ---------------------------------------------------------------------------
// Spill slot coloring: Minimize spill slot count
// ---------------------------------------------------------------------------

/// Spill slot interference graph for coloring-based slot allocation.
#[derive(Debug, Clone, Default)]
pub struct SpillSlotInterferenceGraph {
    /// For each virtual register, the set of other vregs it interferes with.
    interference: HashMap<u32, HashSet<u32>>,
    /// Assigned slot offsets for each vreg.
    assignments: HashMap<u32, i32>,
    /// All vregs that need spill slots.
    all_vregs: HashSet<u32>,
}

impl SpillSlotInterferenceGraph {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn add_interference(&mut self, a: u32, b: u32) {
        self.interference.entry(a).or_default().insert(b);
        self.interference.entry(b).or_default().insert(a);
        self.all_vregs.insert(a);
        self.all_vregs.insert(b);
    }

    pub fn add_vreg(&mut self, vreg: u32) {
        self.all_vregs.insert(vreg);
    }

    /// Simple greedy coloring to minimize slot count.
    pub fn color_slots(&mut self, slot_size: u32) -> HashMap<u32, i32> {
        // Sort vregs by degree (most constrained first)
        let mut vregs: Vec<u32> = self.all_vregs.iter().copied().collect();
        vregs.sort_by_key(|v| -(self.interference.get(v).map_or(0, |s| s.len()) as i32));

        for &vreg in &vregs {
            // Find the smallest slot not conflicting with any neighbor
            let neighbors = self.interference.get(&vreg);
            let mut used_slots: HashSet<i32> = HashSet::new();

            if let Some(neighbors) = neighbors {
                for neighbor in neighbors {
                    if let Some(&slot) = self.assignments.get(neighbor) {
                        used_slots.insert(slot);
                    }
                }
            }

            // Find minimum available slot
            let mut slot = 0i32;
            while used_slots.contains(&slot) {
                slot += slot_size as i32;
            }

            self.assignments.insert(vreg, slot);
        }

        self.assignments.clone()
    }
}

impl X86SpillOptimizer {
    /// Minimize the number of spill slots by coloring interference.
    ///
    /// Two virtual registers that are never live simultaneously can share
    /// the same spill slot.
    pub fn minimize_spill_slots(
        &mut self,
        live_ranges: &HashMap<u32, (u32, u32)>, // vreg -> (start_slot, end_slot)
        default_slot_size: u32,
    ) -> HashMap<u32, SpillSlot> {
        let mut graph = SpillSlotInterferenceGraph::new();
        let vregs: Vec<u32> = live_ranges.keys().copied().collect();

        // Build interference: two vregs interfere if their live ranges overlap
        for i in 0..vregs.len() {
            let (start_i, end_i) = live_ranges[&vregs[i]];
            graph.add_vreg(vregs[i]);

            for j in (i + 1)..vregs.len() {
                let (start_j, end_j) = live_ranges[&vregs[j]];

                // Overlap check: [start_i, end_i] ∩ [start_j, end_j] != ∅
                if start_i <= end_j && start_j <= end_i {
                    graph.add_interference(vregs[i], vregs[j]);
                }
            }
        }

        let coloring = graph.color_slots(default_slot_size);

        // Build result
        let mut result: HashMap<u32, SpillSlot> = HashMap::new();
        for (vreg, offset) in coloring {
            result.insert(
                vreg,
                SpillSlot::new(offset, default_slot_size, default_slot_size),
            );
        }

        result
    }
}

// ---------------------------------------------------------------------------
// Factory functions
// ---------------------------------------------------------------------------

pub fn make_x86_spill_optimizer() -> X86SpillOptimizer {
    X86SpillOptimizer::new_default()
}

pub fn make_x86_spill_optimizer_size_opt() -> X86SpillOptimizer {
    X86SpillOptimizer::new_size_optimized()
}

pub fn make_spill_optimizer_with_config(config: SpillOptimizerConfig) -> X86SpillOptimizer {
    X86SpillOptimizer::new(config)
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

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

    fn make_opt() -> X86SpillOptimizer {
        X86SpillOptimizer::new_default()
    }

    fn make_test_spill(
        id: u64,
        vreg: u32,
        slot_offset: i32,
        block: u32,
        slot_idx: u32,
    ) -> SpillInstruction {
        SpillInstruction {
            id,
            opcode: "MOV32mr".to_string(),
            defs: vec![],
            uses: vec![vreg],
            spill_slot: Some(SpillSlot::new(slot_offset, 4, 4)),
            spill_kind: SpillOpKind::Spill,
            clobbers_flags: false,
            has_memory_side_effects: false,
            block_id: block,
            slot_index: slot_idx,
            is_call: false,
            in_loop: false,
            in_cold_path: false,
            reg_size: 4,
            is_simd: false,
            has_memory_foldable_form: false,
            folded_memory_operand: None,
        }
    }

    fn make_test_reload(
        id: u64,
        vreg: u32,
        slot_offset: i32,
        block: u32,
        slot_idx: u32,
    ) -> SpillInstruction {
        SpillInstruction {
            id,
            opcode: "MOV32rm".to_string(),
            defs: vec![vreg],
            uses: vec![],
            spill_slot: Some(SpillSlot::new(slot_offset, 4, 4)),
            spill_kind: SpillOpKind::Reload,
            clobbers_flags: false,
            has_memory_side_effects: false,
            block_id: block,
            slot_index: slot_idx,
            is_call: false,
            in_loop: false,
            in_cold_path: false,
            reg_size: 4,
            is_simd: false,
            has_memory_foldable_form: false,
            folded_memory_operand: None,
        }
    }

    fn make_test_instr(
        id: u64,
        defs: Vec<u32>,
        uses: Vec<u32>,
        block: u32,
        slot_idx: u32,
    ) -> SpillInstruction {
        SpillInstruction {
            id,
            opcode: "ADD32rr".to_string(),
            defs,
            uses,
            spill_slot: None,
            spill_kind: SpillOpKind::NotSpillRelated,
            clobbers_flags: true,
            has_memory_side_effects: false,
            block_id: block,
            slot_index: slot_idx,
            is_call: false,
            in_loop: false,
            in_cold_path: false,
            reg_size: 4,
            is_simd: false,
            has_memory_foldable_form: true,
            folded_memory_operand: None,
        }
    }

    // -- Constructor tests --

    #[test]
    fn test_constructor_default() {
        let opt = make_opt();
        assert!(opt.config.remove_redundant_spills);
        assert!(opt.config.fold_reloads);
    }

    #[test]
    fn test_constructor_size_opt() {
        let opt = X86SpillOptimizer::new_size_optimized();
        assert!(opt.config.opt_for_size);
    }

    // -- SpillSlot tests --

    #[test]
    fn test_spill_slot_overlaps() {
        let a = SpillSlot::new(0, 8, 8);
        let b = SpillSlot::new(4, 8, 8);
        assert!(a.overlaps(&b));
    }

    #[test]
    fn test_spill_slot_no_overlap() {
        let a = SpillSlot::new(0, 4, 4);
        let b = SpillSlot::new(8, 4, 4);
        assert!(!a.overlaps(&b));
    }

    #[test]
    fn test_spill_slot_adjacent() {
        let a = SpillSlot::new(0, 4, 4);
        let b = SpillSlot::new(4, 4, 4);
        assert!(a.is_adjacent(&b));
    }

    #[test]
    fn test_spill_slot_not_adjacent() {
        let a = SpillSlot::new(0, 4, 4);
        let b = SpillSlot::new(8, 4, 4);
        assert!(!a.is_adjacent(&b));
    }

    #[test]
    fn test_spill_slot_end_offset() {
        let s = SpillSlot::new(16, 8, 8);
        assert_eq!(s.end_offset(), 24);
    }

    // -- Redundant spill removal tests --

    #[test]
    fn test_remove_redundant_spills() {
        let mut opt = make_opt();
        let instrs = vec![
            make_test_spill(1, 10, 0, 0, 0),
            make_test_instr(2, vec![11], vec![10], 0, 1),
            make_test_spill(3, 10, 0, 0, 2), // Redundant: same value, same slot
        ];
        let result = opt.remove_redundant_spills(&instrs);
        assert!(result.len() < 3);
        assert!(opt.stats.redundant_spills_removed > 0);
    }

    #[test]
    fn test_keep_different_slot_spills() {
        let mut opt = make_opt();
        let instrs = vec![
            make_test_spill(1, 10, 0, 0, 0),
            make_test_spill(2, 10, 4, 0, 1), // Different slot, not redundant
        ];
        let result = opt.remove_redundant_spills(&instrs);
        assert_eq!(result.len(), 2);
    }

    #[test]
    fn test_spill_after_modification_not_redundant() {
        let mut opt = make_opt();
        let instrs = vec![
            make_test_spill(1, 10, 0, 0, 0),
            make_test_instr(2, vec![10], vec![20], 0, 1), // Modifies vreg 10
            make_test_spill(3, 10, 0, 0, 2),              // Not redundant: value changed
        ];
        let result = opt.remove_redundant_spills(&instrs);
        assert_eq!(result.len(), 3);
    }

    // -- Store-load elimination tests --

    #[test]
    fn test_eliminate_store_load_pair() {
        let mut opt = make_opt();
        let instrs = vec![
            make_test_spill(1, 10, 0, 0, 0),
            make_test_reload(2, 10, 0, 0, 1), // Reload of same slot immediately after
        ];
        let result = opt.eliminate_store_load_pairs(&instrs);
        assert!(result.len() < 2);
        assert!(opt.stats.store_to_load_eliminated > 0);
    }

    #[test]
    fn test_keep_store_load_with_intervening_call() {
        let mut opt = make_opt();
        let mut call_instr = make_test_instr(2, vec![], vec![], 0, 1);
        call_instr.is_call = true;
        let instrs = vec![
            make_test_spill(1, 10, 0, 0, 0),
            call_instr, // Call may clobber memory
            make_test_reload(3, 10, 0, 0, 2),
        ];
        let result = opt.eliminate_store_load_pairs(&instrs);
        assert_eq!(result.len(), 3);
    }

    // -- Redundant reload removal tests --

    #[test]
    fn test_remove_redundant_reloads() {
        let mut opt = make_opt();
        let instrs = vec![
            make_test_reload(1, 10, 0, 0, 0),
            make_test_reload(2, 10, 0, 0, 1), // Redundant: already in register
        ];
        let result = opt.remove_redundant_reloads(&instrs);
        assert!(result.len() < 2);
        assert!(opt.stats.redundant_reloads_removed > 0);
    }

    #[test]
    fn test_keep_reload_after_definition() {
        let mut opt = make_opt();
        let instrs = vec![
            make_test_instr(1, vec![10], vec![20], 0, 0),
            make_test_reload(2, 10, 0, 0, 1), // May not be redundant if slot was spilled to
        ];
        let result = opt.remove_redundant_reloads(&instrs);
        assert_eq!(result.len(), 2); // First reload is not tracked as redundant
    }

    // -- Fold reload into user tests --

    #[test]
    fn test_fold_reload_into_user() {
        let mut opt = make_opt();
        let reload = SpillInstruction {
            id: 1,
            opcode: "MOV32rm".to_string(),
            defs: vec![10],
            uses: vec![],
            spill_slot: Some(SpillSlot::new(0, 4, 4)),
            spill_kind: SpillOpKind::ReloadFoldable,
            clobbers_flags: false,
            has_memory_side_effects: false,
            block_id: 0,
            slot_index: 0,
            is_call: false,
            in_loop: false,
            in_cold_path: false,
            reg_size: 4,
            is_simd: false,
            has_memory_foldable_form: false,
            folded_memory_operand: Some(FoldedMemoryOperand {
                base_reg: 5,
                index_reg: None,
                scale: 1,
                displacement: 0,
                size: 4,
            }),
        };
        let user = SpillInstruction {
            id: 2,
            opcode: "ADD32rm".to_string(),
            defs: vec![11],
            uses: vec![10, 12],
            spill_slot: None,
            spill_kind: SpillOpKind::NotSpillRelated,
            clobbers_flags: true,
            has_memory_side_effects: false,
            block_id: 0,
            slot_index: 1,
            is_call: false,
            in_loop: false,
            in_cold_path: false,
            reg_size: 4,
            is_simd: false,
            has_memory_foldable_form: true,
            folded_memory_operand: None,
        };
        let result = opt.fold_reloads_into_users(&[reload.clone(), user.clone()]);
        assert!(result.len() < 2 || opt.stats.reloads_folded_into_users > 0);
    }

    // -- Spill slot merging tests --

    #[test]
    fn test_find_adjacent_slot_groups() {
        let mut opt = make_opt();
        opt.register_spill_slot(SpillSlot::new(0, 4, 4));
        opt.register_spill_slot(SpillSlot::new(4, 4, 4));
        opt.register_spill_slot(SpillSlot::new(16, 4, 4));

        let groups = opt.find_adjacent_slot_groups();
        assert_eq!(groups.len(), 2); // Two groups: [0,4] and [16]
    }

    #[test]
    fn test_merge_adjacent_slots() {
        let mut opt = make_opt();
        opt.register_spill_slot(SpillSlot::new(0, 4, 4));
        opt.register_spill_slot(SpillSlot::new(4, 4, 4));
        opt.merge_adjacent_spill_slots();
        assert!(opt.spill_slots.len() < 2);
        // Should have one merged slot [0, 8]
        assert!(opt.spill_slots.contains_key(&0));
    }

    #[test]
    fn test_no_merge_non_adjacent() {
        let mut opt = make_opt();
        opt.register_spill_slot(SpillSlot::new(0, 4, 4));
        opt.register_spill_slot(SpillSlot::new(16, 4, 4));
        opt.merge_adjacent_spill_slots();
        assert_eq!(opt.spill_slots.len(), 2);
    }

    #[test]
    fn test_can_merge_slots() {
        let mut opt = make_opt();
        opt.register_spill_slot(SpillSlot::new(0, 4, 4));
        opt.register_spill_slot(SpillSlot::new(4, 4, 4));
        let a = SpillSlot::new(0, 4, 4);
        let b = SpillSlot::new(4, 4, 4);
        assert!(opt.can_merge_slots(&a, &b));
    }

    #[test]
    fn test_cannot_merge_overlapping_live_ranges() {
        let mut opt = make_opt();
        let mut occ_a = HashSet::new();
        occ_a.insert(10);
        let mut occ_b = HashSet::new();
        occ_b.insert(10); // Same vreg, overlapping
        opt.slot_occupants.insert(0, occ_a);
        opt.slot_occupants.insert(4, occ_b);
        let a = SpillSlot::new(0, 4, 4);
        let b = SpillSlot::new(4, 4, 4);
        assert!(!opt.can_merge_slots(&a, &b));
    }

    // -- SIMD spill promotion tests --

    #[test]
    fn test_promote_simd_spills() {
        let mut opt = make_opt();
        let spill = SpillInstruction {
            id: 1,
            opcode: "MOV64mr".to_string(),
            defs: vec![],
            uses: vec![0], // XMM0
            spill_slot: Some(SpillSlot::new(0, 8, 8)),
            spill_kind: SpillOpKind::Spill,
            clobbers_flags: false,
            has_memory_side_effects: false,
            block_id: 0,
            slot_index: 0,
            is_call: false,
            in_loop: false,
            in_cold_path: false,
            reg_size: 8,
            is_simd: true,
            has_memory_foldable_form: false,
            folded_memory_operand: None,
        };
        let result = opt.promote_simd_spills(&[spill]);
        assert_eq!(result[0].opcode, "MOVSDmr");
        assert!(opt.stats.simd_spills_promoted > 0);
    }

    #[test]
    fn test_no_promote_non_simd() {
        let mut opt = make_opt();
        let spill = make_test_spill(1, 10, 0, 0, 0);
        let result = opt.promote_simd_spills(&[spill]);
        assert_eq!(result[0].opcode, "MOV32mr"); // Unchanged
    }

    // -- Classification tests --

    #[test]
    fn test_classify_spill_instruction() {
        let spill = make_test_spill(1, 10, 0, 0, 0);
        assert_eq!(
            X86SpillOptimizer::classify_spill_instruction(&spill),
            SpillOpKind::Spill
        );
    }

    #[test]
    fn test_classify_reload_instruction() {
        let reload = make_test_reload(1, 10, 0, 0, 0);
        assert_eq!(
            X86SpillOptimizer::classify_spill_instruction(&reload),
            SpillOpKind::Reload
        );
    }

    #[test]
    fn test_classify_not_spill_related() {
        let instr = make_test_instr(1, vec![10], vec![20], 0, 0);
        assert_eq!(
            X86SpillOptimizer::classify_spill_instruction(&instr),
            SpillOpKind::NotSpillRelated
        );
    }

    // -- Memory operand construction tests --

    #[test]
    fn test_construct_spill_memory_operand() {
        let slot = SpillSlot::new(-16, 4, 4);
        let mem = X86SpillOptimizer::construct_spill_memory_operand(&slot, 5);
        assert_eq!(mem.base_reg, 5);
        assert_eq!(mem.displacement, -16);
        assert_eq!(mem.size, 4);
    }

    #[test]
    fn test_can_fold_spill_into_instruction() {
        let mut instr = make_test_instr(1, vec![10], vec![20], 0, 0);
        instr.has_memory_foldable_form = true;
        assert!(X86SpillOptimizer::can_fold_spill_into_instruction(&instr));
    }

    #[test]
    fn test_cannot_fold_call() {
        let mut instr = make_test_instr(1, vec![], vec![], 0, 0);
        instr.is_call = true;
        instr.has_memory_foldable_form = true;
        assert!(!X86SpillOptimizer::can_fold_spill_into_instruction(&instr));
    }

    // -- Spill slot coloring tests --

    #[test]
    fn test_color_slots_non_overlapping() {
        let mut graph = SpillSlotInterferenceGraph::new();
        graph.add_vreg(1);
        graph.add_vreg(2);
        // No interference — should get same slot
        let coloring = graph.color_slots(8);
        assert_eq!(coloring.get(&1), coloring.get(&2));
        assert_eq!(coloring.get(&1), Some(&0));
    }

    #[test]
    fn test_color_slots_interfering() {
        let mut graph = SpillSlotInterferenceGraph::new();
        graph.add_vreg(1);
        graph.add_vreg(2);
        graph.add_interference(1, 2); // Interfere — different slots
        let coloring = graph.color_slots(8);
        assert_ne!(coloring.get(&1), coloring.get(&2));
    }

    #[test]
    fn test_color_slots_three_vregs() {
        let mut graph = SpillSlotInterferenceGraph::new();
        graph.add_vreg(1);
        graph.add_vreg(2);
        graph.add_vreg(3);
        graph.add_interference(1, 2);
        graph.add_interference(2, 3);
        // 1 and 3 don't interfere — can share slot
        let coloring = graph.color_slots(8);
        assert_eq!(coloring.get(&1), coloring.get(&3));
        assert_ne!(coloring.get(&1), coloring.get(&2));
    }

    // -- Minimize spill slots test --

    #[test]
    fn test_minimize_spill_slots() {
        let mut opt = make_opt();
        let mut live_ranges: HashMap<u32, (u32, u32)> = HashMap::new();
        live_ranges.insert(1, (0, 10));
        live_ranges.insert(2, (5, 15)); // Overlap with 1
        live_ranges.insert(3, (20, 30)); // No overlap with 1 or 2
        let result = opt.minimize_spill_slots(&live_ranges, 4);
        // 1 and 2 should get different slots, 3 can share with 1 (no overlap)
        assert!(result.len() >= 2);
    }

    // -- Block optimization tests --

    #[test]
    fn test_optimize_block_empty() {
        let mut opt = make_opt();
        let result = opt.optimize_block(&[]);
        assert!(result.is_empty());
    }

    #[test]
    fn test_optimize_block_with_spills() {
        let mut opt = make_opt();
        let instrs = vec![
            make_test_spill(1, 10, 0, 0, 0),
            make_test_reload(2, 10, 0, 0, 1),
        ];
        let result = opt.optimize_block(&instrs);
        assert!(result.len() <= 2);
    }

    #[test]
    fn test_optimize_function() {
        let mut opt = make_opt();
        let mut blocks: HashMap<u32, Vec<SpillInstruction>> = HashMap::new();
        blocks.insert(
            0,
            vec![
                make_test_spill(1, 10, 0, 0, 0),
                make_test_spill(2, 10, 0, 0, 1), // Redundant
            ],
        );
        blocks.insert(1, vec![make_test_reload(3, 10, 0, 1, 0)]);
        let result = opt.optimize_function(&blocks);
        assert!(result.contains_key(&0));
        assert!(result.contains_key(&1));
    }

    // -- Hoisting tests --

    #[test]
    fn test_hoist_reloads_out_of_loops() {
        let mut opt = make_opt();
        opt.loops = vec![LoopInfo {
            header_block: 0,
            body_blocks: [0, 1].iter().copied().collect(),
            exit_blocks: [2].iter().copied().collect(),
            depth: 1,
            is_hot: true,
        }];

        let mut blocks: HashMap<u32, Vec<SpillInstruction>> = HashMap::new();
        blocks.insert(0, vec![make_test_reload(1, 10, 0, 0, 0)]);
        blocks.insert(1, vec![make_test_reload(2, 10, 0, 1, 0)]);

        opt.hoist_reloads_out_of_loops(&mut blocks);
        // Reloads from loop body should be hoisted
    }

    #[test]
    fn test_no_hoist_cold_loop() {
        let mut opt = make_opt();
        opt.loops = vec![LoopInfo {
            header_block: 0,
            body_blocks: [0].iter().copied().collect(),
            exit_blocks: [1].iter().copied().collect(),
            depth: 1,
            is_hot: false, // Not hot
        }];

        let mut blocks: HashMap<u32, Vec<SpillInstruction>> = HashMap::new();
        blocks.insert(0, vec![make_test_reload(1, 10, 0, 0, 0)]);

        let before = blocks[&0].len();
        opt.hoist_reloads_out_of_loops(&mut blocks);
        assert_eq!(blocks[&0].len(), before); // No change
    }

    // -- Sinking tests --

    #[test]
    fn test_sink_spills_to_cold_paths() {
        let mut opt = make_opt();
        opt.block_frequencies.insert(
            0,
            BlockFrequency {
                block_id: 0,
                execution_count: 1000,
                is_cold: false,
            },
        );

        let mut blocks: HashMap<u32, Vec<SpillInstruction>> = HashMap::new();
        blocks.insert(0, vec![make_test_spill(1, 10, 0, 0, 0)]);

        opt.sink_spills_to_cold_paths(&mut blocks);
        assert!(opt.stats.sink_opportunities > 0);
    }

    // -- Liveness tests --

    #[test]
    fn test_compute_spill_liveness() {
        let opt = make_opt();
        let mut blocks: HashMap<u32, Vec<SpillInstruction>> = HashMap::new();
        blocks.insert(
            0,
            vec![
                make_test_spill(1, 10, 0, 0, 0),
                make_test_reload(2, 10, 0, 0, 1),
                make_test_instr(3, vec![11], vec![10], 0, 2),
            ],
        );

        let info = opt.compute_spill_liveness(&blocks);
        assert!(info.live_in.contains_key(&0));
        assert!(info.live_out.contains_key(&0));
    }

    // -- Stats tests --

    #[test]
    fn test_stats_new_zero() {
        let stats = SpillOptimizerStats::new();
        assert_eq!(stats.total_optimizations(), 0);
    }

    #[test]
    fn test_stats_merge() {
        let mut a = SpillOptimizerStats::new();
        a.redundant_spills_removed = 5;
        a.reloads_folded_into_users = 3;

        let mut b = SpillOptimizerStats::new();
        b.redundant_spills_removed = 2;
        b.reloads_folded_into_users = 1;

        a.merge(&b);
        assert_eq!(a.redundant_spills_removed, 7);
        assert_eq!(a.reloads_folded_into_users, 4);
    }

    #[test]
    fn test_take_stats() {
        let mut opt = make_opt();
        let instrs = vec![
            make_test_spill(1, 10, 0, 0, 0),
            make_test_spill(2, 10, 0, 0, 1),
        ];
        let _ = opt.remove_redundant_spills(&instrs);
        let stats = opt.take_stats();
        assert!(stats.redundant_spills_removed > 0);
        // After take, stats are reset
        let stats2 = opt.take_stats();
        assert_eq!(stats2.redundant_spills_removed, 0);
    }

    // -- LoopInfo tests --

    #[test]
    fn test_loop_info() {
        let loop_info = LoopInfo {
            header_block: 0,
            body_blocks: [0, 1, 2].iter().copied().collect(),
            exit_blocks: [3].iter().copied().collect(),
            depth: 2,
            is_hot: true,
        };
        assert!(loop_info.is_hot);
        assert_eq!(loop_info.depth, 2);
        assert!(loop_info.body_blocks.contains(&1));
        assert!(loop_info.exit_blocks.contains(&3));
    }

    // -- BlockFrequency tests --

    #[test]
    fn test_block_frequency_is_cold() {
        let hot = BlockFrequency {
            block_id: 0,
            execution_count: 10000,
            is_cold: false,
        };
        assert!(!hot.is_cold());

        let cold = BlockFrequency {
            block_id: 1,
            execution_count: 0,
            is_cold: false,
        };
        assert!(cold.is_cold());

        let explicit_cold = BlockFrequency {
            block_id: 2,
            execution_count: 1,
            is_cold: true,
        };
        assert!(explicit_cold.is_cold());
    }

    // -- SpillSlotGroup tests --

    #[test]
    fn test_spill_slot_group_empty() {
        let group = SpillSlotGroup::new(vec![]);
        assert!(!group.can_merge);
    }

    #[test]
    fn test_spill_slot_group_single() {
        let group = SpillSlotGroup::new(vec![SpillSlot::new(0, 4, 4)]);
        assert!(group.can_merge);
        assert_eq!(group.merged_offset, 0);
        assert_eq!(group.merged_size, 4);
    }

    #[test]
    fn test_spill_slot_group_multiple() {
        let group = SpillSlotGroup::new(vec![SpillSlot::new(0, 4, 4), SpillSlot::new(4, 8, 8)]);
        assert!(group.can_merge);
        assert_eq!(group.merged_offset, 0);
        assert_eq!(group.merged_size, 12);
        assert_eq!(group.merged_alignment, 8); // Max of 4 and 8
    }

    // -- SpillInstruction tests --

    #[test]
    fn test_spill_instruction_is_spill() {
        let s = make_test_spill(1, 10, 0, 0, 0);
        assert!(s.is_spill());
        assert!(!s.is_reload());
    }

    #[test]
    fn test_spill_instruction_is_reload() {
        let r = make_test_reload(1, 10, 0, 0, 0);
        assert!(!r.is_spill());
        assert!(r.is_reload());
    }

    // -- Factory tests --

    #[test]
    fn test_factory_default() {
        let opt = make_x86_spill_optimizer();
        assert!(opt.config.remove_redundant_spills);
    }

    #[test]
    fn test_factory_size_opt() {
        let opt = make_x86_spill_optimizer_size_opt();
        assert!(opt.config.opt_for_size);
    }

    #[test]
    fn test_factory_with_config() {
        let config = SpillOptimizerConfig {
            remove_redundant_spills: false,
            ..Default::default()
        };
        let opt = make_spill_optimizer_with_config(config);
        assert!(!opt.config.remove_redundant_spills);
    }

    // -- Edge case tests --

    #[test]
    fn test_empty_instructions() {
        let mut opt = make_opt();
        let result = opt.optimize_block(&[]);
        assert!(result.is_empty());
    }

    #[test]
    fn test_single_spill() {
        let mut opt = make_opt();
        let instrs = vec![make_test_spill(1, 10, 0, 0, 0)];
        let result = opt.optimize_block(&instrs);
        assert_eq!(result.len(), 1);
    }

    #[test]
    fn test_single_reload() {
        let mut opt = make_opt();
        let instrs = vec![make_test_reload(1, 10, 0, 0, 0)];
        let result = opt.optimize_block(&instrs);
        assert_eq!(result.len(), 1);
    }

    #[test]
    fn test_all_spill_op_kinds_distinct() {
        let kinds = [
            SpillOpKind::Spill,
            SpillOpKind::Reload,
            SpillOpKind::SpillToFold,
            SpillOpKind::ReloadFoldable,
            SpillOpKind::NotSpillRelated,
        ];
        // Verify they're all distinct
        for i in 0..kinds.len() {
            for j in (i + 1)..kinds.len() {
                assert_ne!(kinds[i], kinds[j]);
            }
        }
    }

    // -- Comprehensive scenario tests --

    #[test]
    fn test_full_spill_optimize_scenario() {
        let mut opt = make_opt();
        let instrs = vec![
            make_test_spill(1, 10, 0, 0, 0), // Spill vreg10 to slot 0
            make_test_instr(2, vec![11], vec![10], 0, 1), // Use vreg10
            make_test_spill(3, 10, 0, 0, 2), // Redundant spill
            make_test_reload(4, 10, 0, 0, 3), // Reload (should detect store-load)
            make_test_instr(5, vec![12], vec![11, 10], 0, 4), // Use vreg10 and vreg11
        ];

        let result = opt.optimize_block(&instrs);
        // Should be fewer than 5 instructions after optimization
        assert!(result.len() <= 5);
        assert!(opt.stats.redundant_spills_removed > 0 || opt.stats.store_to_load_eliminated > 0);
    }

    #[test]
    fn test_merge_slots_scenario() {
        let mut opt = make_opt();
        opt.register_spill_slot(SpillSlot::new(0, 4, 4));
        opt.register_spill_slot(SpillSlot::new(4, 4, 4));
        opt.register_spill_slot(SpillSlot::new(8, 8, 8));
        opt.merge_adjacent_spill_slots();

        // All three adjacent = one merged slot [0, 16]
        assert_eq!(opt.spill_slots.len(), 1);
        let merged = opt.spill_slots.get(&0).unwrap();
        assert_eq!(merged.offset, 0);
        assert_eq!(merged.size, 16);
    }

    #[test]
    fn test_hoist_and_sink_compatibility() {
        let mut opt = make_opt();
        // Test that hoisting and sinking don't interfere
        opt.loops = vec![LoopInfo {
            header_block: 0,
            body_blocks: [0, 1].iter().copied().collect(),
            exit_blocks: [2].iter().copied().collect(),
            depth: 1,
            is_hot: true,
        }];
        opt.block_frequencies.insert(
            2,
            BlockFrequency {
                block_id: 2,
                execution_count: 0,
                is_cold: true,
            },
        );

        let mut blocks: HashMap<u32, Vec<SpillInstruction>> = HashMap::new();
        blocks.insert(0, vec![make_test_reload(1, 10, 0, 0, 0)]);
        blocks.insert(1, vec![make_test_spill(2, 10, 0, 1, 0)]);
        blocks.insert(2, vec![make_test_reload(3, 10, 0, 2, 0)]);

        let result = opt.optimize_function(&blocks);
        assert!(result.len() >= 2);
    }
}