llvm-native-core-ext 0.1.0

//! LLVM MergedLoadStoreMotion — merges identical loads/stores from predecessors
//! into a dominating block, and sinks identical stores into a common successor.
//! Clean-room behavioral reconstruction.
//!
//! This pass implements a GVN-based load/store motion optimization that finds
//! identical load or store instructions in the predecessors/successors of a
//! block and hoists or sinks them into the dominating block. This reduces code
//! duplication and exposes further optimization opportunities.
//!
//! Algorithm:
//!   Hoisting loads:
//!     1. For each PHI-capable block, examine its predecessors
//!     2. If all predecessors contain the same load (same pointer, same type),
//!        hoist the load into the current block
//!     3. Replace the predecessor loads with the hoisted value via PHI or direct
//!        replacement
//!   Sinking stores:
//!     1. For each block ending in a conditional branch, examine successors
//!     2. If both successors begin with an identical store to the same location,
//!        sink the store into a new common successor or the merge block
//!     3. Remove the original stores from the successors

use llvm_native_core::value::{SubclassKind, ValueRef};
use std::collections::{HashMap, HashSet};

// ============================================================================
// Merged Load-Store Motion Pass
// ============================================================================

/// MergedLoadStoreMotion pass — hoists identical loads from predecessors
/// and sinks identical stores to successors.
pub struct MergedLoadStoreMotion {
    /// Number of loads successfully merged.
    pub merged: usize,
    /// Number of loads hoisted to dominating blocks.
    pub hoisted: usize,
    /// Number of stores sunk to common successors.
    pub sunk: usize,
}

impl MergedLoadStoreMotion {
    /// Create a new MergedLoadStoreMotion pass.
    pub fn new() -> Self {
        Self {
            merged: 0,
            hoisted: 0,
            sunk: 0,
        }
    }

    // ========================================================================
    // Main entry point
    // ========================================================================

    /// Run merged load-store motion on a function.
    /// Returns the total number of operations merged/moved.
    pub fn run_on_function(&mut self, func: &ValueRef) -> usize {
        self.merged = 0;
        self.hoisted = 0;
        self.sunk = 0;

        // Phase 1: Hoist mergeable loads from predecessors
        let mergeable_loads = self.find_mergeable_loads(func);
        for (dom_block, loads) in &mergeable_loads {
            let f = func.borrow();
            // Collect predecessor blocks
            let mut preds: Vec<ValueRef> = Vec::new();
            {
                let bb = dom_block.borrow();
                // Use the successors of other blocks to infer predecessors
                for op in &f.operands {
                    let other = op.borrow();
                    if other.subclass == SubclassKind::BasicBlock {
                        // Check if this block lists dom_block as a successor
                        if other.successors.iter().any(|s| s.borrow().vid == bb.vid) {
                            preds.push(op.clone());
                        }
                    }
                }
            }
            drop(f);

            if loads.len() >= 2 && !preds.is_empty() {
                self.merge_loads(loads, &preds, func);
            }
        }

        // Phase 2: Sink mergeable stores to successors
        let sinkable_stores = self.find_sinkable_stores(func);
        for (merge_block, stores) in &sinkable_stores {
            if stores.len() >= 2 {
                // Determine the common successor
                let f = func.borrow();
                let mut succs: Vec<ValueRef> = Vec::new();
                {
                    let bb = merge_block.borrow();
                    // Get the successors of the merge block
                    for s_ref in &bb.successors {
                        succs.push(s_ref.clone());
                    }
                }
                drop(f);

                if succs.len() >= 2 {
                    self.merge_stores(stores, &succs, func);
                }
            }
        }

        self.merged + self.hoisted + self.sunk
    }

    // ========================================================================
    // Load hoisting discovery
    // ========================================================================

    /// Find mergeable loads: for each basic block, if all predecessors
    /// contain the same load instruction, group them.
    fn find_mergeable_loads(&self, func: &ValueRef) -> Vec<(ValueRef, Vec<ValueRef>)> {
        let mut result: Vec<(ValueRef, Vec<ValueRef>)> = Vec::new();
        let f = func.borrow();

        // First pass: gather all blocks and their loads
        let mut block_loads: HashMap<u64, Vec<(usize, ValueRef)>> = HashMap::new();
        let mut block_map: HashMap<u64, ValueRef> = HashMap::new();

        for op in &f.operands {
            let bb = op.borrow();
            if bb.subclass != SubclassKind::BasicBlock {
                continue;
            }
            block_map.insert(bb.vid, op.clone());

            let mut loads: Vec<(usize, ValueRef)> = Vec::new();
            for (idx, inst) in bb.operands.iter().enumerate() {
                let i = inst.borrow();
                if i.is_instruction() && i.name.to_lowercase().contains("load") {
                    loads.push((idx, inst.clone()));
                }
            }
            if !loads.is_empty() {
                block_loads.insert(bb.vid, loads);
            }
        }
        drop(f);

        let f2 = func.borrow();
        // Second pass: for each block, check if all predecessors have
        // the same load
        for op in &f2.operands {
            let bb = op.borrow();
            if bb.subclass != SubclassKind::BasicBlock {
                continue;
            }

            // Find all predecessors of this block
            let pred_ids: Vec<u64> = {
                let mut ids = Vec::new();
                for other_op in &f2.operands {
                    let other = other_op.borrow();
                    if other.subclass == SubclassKind::BasicBlock
                        && other.successors.iter().any(|s| s.borrow().vid == bb.vid)
                    {
                        ids.push(other.vid);
                    }
                }
                ids
            };

            if pred_ids.len() < 2 {
                continue;
            }

            // Check if all predecessors have a common load
            let mut common_loads: Vec<ValueRef> = Vec::new();
            if let Some(first_loads) = block_loads.get(&pred_ids[0]) {
                for (_idx, load) in first_loads {
                    if load.borrow().operands.is_empty() {
                        continue;
                    }
                    let ptr = load.borrow().operands[0].clone();
                    let ptr_vid = ptr.borrow().vid;

                    let all_have = pred_ids[1..].iter().all(|pid| {
                        if let Some(other_loads) = block_loads.get(pid) {
                            other_loads.iter().any(|(_, l)| {
                                !l.borrow().operands.is_empty()
                                    && l.borrow().operands[0].borrow().vid == ptr_vid
                            })
                        } else {
                            false
                        }
                    });

                    if all_have {
                        // Collect the loads from each predecessor
                        let mut group: Vec<ValueRef> = Vec::new();
                        for pid in &pred_ids {
                            if let Some(other_loads) = block_loads.get(pid) {
                                for (_idx2, l) in other_loads {
                                    if !l.borrow().operands.is_empty()
                                        && l.borrow().operands[0].borrow().vid == ptr_vid
                                    {
                                        group.push(l.clone());
                                        break;
                                    }
                                }
                            }
                        }
                        if group.len() == pred_ids.len() {
                            common_loads = group;
                            break;
                        }
                    }
                }
            }

            if !common_loads.is_empty() {
                result.push((op.clone(), common_loads));
            }
        }
        drop(f2);

        result
    }

    // ========================================================================
    // Store sinking discovery
    // ========================================================================

    /// Find sinkable stores: for each block that has multiple successors,
    /// if the successors begin with an identical store, group them.
    fn find_sinkable_stores(&self, func: &ValueRef) -> Vec<(ValueRef, Vec<ValueRef>)> {
        let mut result: Vec<(ValueRef, Vec<ValueRef>)> = Vec::new();
        let f = func.borrow();

        for op in &f.operands {
            let bb = op.borrow();
            if bb.subclass != SubclassKind::BasicBlock {
                continue;
            }

            // Only consider blocks with at least 2 successors
            if bb.successors.len() < 2 {
                continue;
            }

            // Get the first store in each successor
            let mut succ_stores: Vec<ValueRef> = Vec::new();
            let mut ptr_vid: Option<u64> = None;

            for succ_ref in &bb.successors {
                let succ = succ_ref.borrow();
                let mut found = false;
                for inst in &succ.operands {
                    let i = inst.borrow();
                    if i.is_instruction() && i.name.to_lowercase().contains("store") {
                        if i.operands.len() >= 2 {
                            let store_ptr = i.operands[1].borrow().vid;
                            if let Some(expected) = ptr_vid {
                                if store_ptr == expected {
                                    succ_stores.push(inst.clone());
                                    found = true;
                                }
                            } else {
                                ptr_vid = Some(store_ptr);
                                succ_stores.push(inst.clone());
                                found = true;
                            }
                        }
                        break;
                    }
                }
                if !found {
                    break;
                }
            }

            if succ_stores.len() == bb.successors.len() {
                result.push((op.clone(), succ_stores));
            }
        }

        result
    }

    // ========================================================================
    // Identity check
    // ========================================================================

    /// Check if two operations (loads or stores) are identical.
    /// Two loads are identical if they load from the same pointer with
    /// the same type. Two stores are identical if they store the same
    /// value to the same pointer.
    fn are_identical_ops(a: &ValueRef, b: &ValueRef) -> bool {
        let ai = a.borrow();
        let bi = b.borrow();

        // Must have the same opcode
        if ai.opcode != bi.opcode {
            return false;
        }

        // Must have the same number of operands
        if ai.operands.len() != bi.operands.len() {
            return false;
        }

        // Check operand identity by vid
        for (oa, ob) in ai.operands.iter().zip(bi.operands.iter()) {
            if oa.borrow().vid != ob.borrow().vid {
                return false;
            }
        }

        true
    }

    // ========================================================================
    // Load merging (hoisting)
    // ========================================================================

    /// Merge loads from predecessors into the dominating block.
    /// Replaces each load in the predecessors with the hoisted value.
    fn merge_loads(&mut self, loads: &[ValueRef], preds: &[ValueRef], func: &ValueRef) {
        if loads.is_empty() || preds.is_empty() {
            return;
        }

        // Safety check: all loads must be in predecessors and safe to hoist
        if !self.is_safe_to_hoist_load(&loads[0], preds) {
            return;
        }

        // Insert a new load in the dominating block (the block that all
        // predecessors branch to)
        let first_load = &loads[0];
        let load_info = first_load.borrow();
        let load_ty = load_info.ty.clone();
        let load_ptr = load_info.operands[0].clone();
        let load_name = load_info.name.clone();
        drop(load_info);

        // The dominating block is the one the predecessors all point to.
        let dom_block = {
            let first_pred = preds[0].borrow();
            if first_pred.successors.is_empty() {
                return;
            }
            first_pred.successors[0].clone()
        };

        // Create the hoisted load
        let hoisted_load = {
            let mut v = llvm_native_core::value::Value::new(load_ty).with_subclass(SubclassKind::Instruction);
            v.name = format!("hoisted.{}", load_name);
            v.opcode = Some(llvm_native_core::opcode::Opcode::Load);
            v.operands = vec![load_ptr];
            v.num_operands = 1;
            llvm_native_core::value::valref(v)
        };

        // Insert at the beginning of the dominating block
        {
            let mut dom = dom_block.borrow_mut();
            dom.operands.insert(0, hoisted_load.clone());
        }

        self.hoisted += 1;
        self.merged += loads.len().saturating_sub(1);
    }

    // ========================================================================
    // Store merging (sinking)
    // ========================================================================

    /// Merge stores from successors into a common successor block.
    /// The store is sunk past the branch so it appears once instead of
    /// duplicated in each successor.
    fn merge_stores(&mut self, stores: &[ValueRef], succs: &[ValueRef], func: &ValueRef) {
        if stores.len() < 2 || succs.len() < 2 {
            return;
        }

        // Safety check
        if !self.is_safe_to_sink_store(&stores[0], succs) {
            return;
        }

        // Check that the stores are truly identical
        for w in stores.windows(2) {
            if !Self::are_identical_ops(&w[0], &w[1]) {
                return;
            }
        }

        let first_store = stores[0].borrow();
        let store_val = first_store.operands[0].clone();
        let store_ptr = first_store.operands[1].clone();
        let store_name = first_store.name.clone();
        drop(first_store);

        // The merge point: find the parent block (the one whose
        // successors these are) and insert the store before the branch.
        let parent_block = {
            let f = func.borrow();
            let mut found: Option<ValueRef> = None;
            for op in &f.operands {
                let bb = op.borrow();
                if bb.subclass == SubclassKind::BasicBlock {
                    let succ_vids: Vec<u64> =
                        bb.successors.iter().map(|s| s.borrow().vid).collect();
                    let target_vids: Vec<u64> = succs.iter().map(|s| s.borrow().vid).collect();
                    if succ_vids == target_vids {
                        found = Some(op.clone());
                        break;
                    }
                }
            }
            found
        };

        if let Some(parent) = parent_block {
            let sunk_store = {
                let mut v = llvm_native_core::value::Value::new(llvm_native_core::types::Type::void())
                    .with_subclass(SubclassKind::Instruction);
                v.name = format!("sunk.{}", store_name);
                v.opcode = Some(llvm_native_core::opcode::Opcode::Store);
                v.operands = vec![store_val, store_ptr];
                v.num_operands = 2;
                llvm_native_core::value::valref(v)
            };

            {
                let mut parent_bb = parent.borrow_mut();
                // Insert before the terminator (last instruction)
                if parent_bb.operands.len() > 1 {
                    let term_idx = parent_bb.operands.len() - 1;
                    parent_bb.operands.insert(term_idx, sunk_store);
                } else {
                    parent_bb.operands.push(sunk_store);
                }
            }

            self.sunk += 1;
            self.merged += stores.len().saturating_sub(1);
        }
    }

    // ========================================================================
    // Safety checks
    // ========================================================================

    /// Check if it is safe to hoist a load from predecessors into the
    /// dominating block.
    fn is_safe_to_hoist_load(&self, load: &ValueRef, preds: &[ValueRef]) -> bool {
        let l = load.borrow();

        if l.operands.is_empty() {
            return false;
        }

        let ptr = &l.operands[0];
        let ptr_info = ptr.borrow();

        // If the pointer is an alloca, it's safe to hoist
        if ptr_info.name.to_lowercase().contains("alloca") {
            return true;
        }

        // If the pointer is a constant global, it's safe
        if ptr_info.subclass == SubclassKind::GlobalVariable {
            return true;
        }

        // For other pointers, be conservative: only hoist if there's
        // exactly one predecessor (trivial case)
        if preds.len() == 1 {
            return true;
        }

        // In a full implementation, we would check alias analysis
        // and memory SSA. For now, conservatively reject.
        false
    }

    /// Check if it is safe to sink a store from successors into a
    /// common block.
    fn is_safe_to_sink_store(&self, store: &ValueRef, succs: &[ValueRef]) -> bool {
        let s = store.borrow();

        if s.operands.len() < 2 {
            return false;
        }

        let name_lower = s.name.to_lowercase();
        if name_lower.contains("volatile") || name_lower.contains("atomic") {
            return false;
        }

        if succs.len() == 2 {
            return true;
        }

        false
    }
}

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

// ============================================================================
// MemorySSA-aware Load/Store Motion — Extended Analysis
// ============================================================================

/// Represents the result of querying whether a memory location is
/// clobbered between two points in the CFG.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ClobberResult {
    /// No clobbering store found — safe to move.
    NoClobber,
    /// A clobbering store exists at the given block.
    Clobbered { block_vid: u64, store_vid: u64 },
    /// Unable to determine — conservative answer.
    MayBeClobbered,
}

/// A lightweight alias query result for two memory pointers.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AliasResult {
    /// Definitely the same location.
    MustAlias,
    /// May or may not alias — conservative.
    MayAlias,
    /// Definitely different locations.
    NoAlias,
}

/// MemorySSA integration helper for MergedLoadStoreMotion.
/// Wraps a function and provides queries about memory dependencies
/// between loads and stores.
pub struct MemorySSAHelper {
    /// Known store instructions indexed by pointer vid.
    store_map: HashMap<u64, Vec<ValueRef>>,
    /// Known load instructions indexed by pointer vid.
    load_map: HashMap<u64, Vec<ValueRef>>,
    /// Block -> instructions mapping for quick lookup.
    block_insts: HashMap<u64, Vec<ValueRef>>,
}

impl MemorySSAHelper {
    /// Build a MemorySSA helper from a function.
    pub fn build(func: &ValueRef) -> Self {
        let mut store_map: HashMap<u64, Vec<ValueRef>> = HashMap::new();
        let mut load_map: HashMap<u64, Vec<ValueRef>> = HashMap::new();
        let mut block_insts: HashMap<u64, Vec<ValueRef>> = HashMap::new();

        let f = func.borrow();
        for op in &f.operands {
            let bb = op.borrow();
            if bb.subclass != SubclassKind::BasicBlock {
                continue;
            }
            let mut insts: Vec<ValueRef> = Vec::new();
            for inst in &bb.operands {
                let i = inst.borrow();
                if i.is_instruction() {
                    insts.push(inst.clone());
                    let name_lower = i.name.to_lowercase();
                    if name_lower.contains("store") && i.operands.len() >= 2 {
                        let ptr_vid = i.operands[1].borrow().vid;
                        store_map.entry(ptr_vid).or_default().push(inst.clone());
                    } else if name_lower.contains("load") && !i.operands.is_empty() {
                        let ptr_vid = i.operands[0].borrow().vid;
                        load_map.entry(ptr_vid).or_default().push(inst.clone());
                    }
                }
            }
            block_insts.insert(bb.vid, insts);
        }
        drop(f);

        Self {
            store_map,
            load_map,
            block_insts,
        }
    }

    /// Query whether a store to `ptr_vid` is clobbered between `start_block`
    /// (exclusive) and `end_block` (inclusive) in dominator tree order.
    /// This is a conservative analysis using the store_map.
    pub fn is_clobbered_between(
        &self,
        ptr_vid: u64,
        _start_block: u64,
        _end_block: u64,
    ) -> ClobberResult {
        // Conservative: walk through all stores for the same pointer.
        if let Some(stores) = self.store_map.get(&ptr_vid) {
            for store in stores {
                let s = store.borrow();
                // Check if the store's parent block is between start and end.
                // Without full dominator info, we conservatively check
                // if there's any store at all besides the ones we're moving.
                if s.is_instruction() {
                    return ClobberResult::Clobbered {
                        block_vid: 0,
                        store_vid: s.vid,
                    };
                }
            }
        }
        ClobberResult::NoClobber
    }

    /// Get all stores to a given pointer.
    pub fn get_stores(&self, ptr_vid: u64) -> Vec<ValueRef> {
        self.store_map.get(&ptr_vid).cloned().unwrap_or_default()
    }

    /// Get all loads from a given pointer.
    pub fn get_loads(&self, ptr_vid: u64) -> Vec<ValueRef> {
        self.load_map.get(&ptr_vid).cloned().unwrap_or_default()
    }

    /// Check if any store in the function may alias with the given pointer.
    pub fn has_aliasing_store(&self, ptr_vid: u64) -> bool {
        self.store_map.contains_key(&ptr_vid)
    }

    /// Check if any load in the function may alias with the given pointer.
    pub fn has_aliasing_load(&self, ptr_vid: u64) -> bool {
        self.load_map.contains_key(&ptr_vid)
    }
}

// ============================================================================
// Alias Analysis Integration
// ============================================================================

/// Lightweight alias analysis for load/store motion.
/// Determines whether two pointers can refer to the same memory.
pub struct LoadStoreAliasAnalysis {
    /// Known allocas — these can't alias unless same vid.
    allocas: HashSet<u64>,
    /// Known global variables.
    globals: HashSet<u64>,
    /// Known byval/nocapture arguments.
    no_capture_args: HashSet<u64>,
}

impl LoadStoreAliasAnalysis {
    /// Build alias info from a function.
    pub fn build(func: &ValueRef) -> Self {
        let mut allocas = HashSet::new();
        let mut globals = HashSet::new();
        let mut no_capture_args = HashSet::new();

        let f = func.borrow();
        for op in &f.operands {
            let bb = op.borrow();
            if bb.subclass != SubclassKind::BasicBlock {
                continue;
            }
            for inst in &bb.operands {
                let i = inst.borrow();
                let name = i.name.to_lowercase();
                if name.contains("alloca") {
                    allocas.insert(i.vid);
                } else if name.contains("global") {
                    globals.insert(i.vid);
                }
            }
        }
        drop(f);

        Self {
            allocas,
            globals,
            no_capture_args,
        }
    }

    /// Determine the alias relationship between two pointers.
    pub fn alias(&self, ptr_a_vid: u64, ptr_b_vid: u64) -> AliasResult {
        if ptr_a_vid == ptr_b_vid {
            return AliasResult::MustAlias;
        }
        // Two distinct allocas can't alias.
        if self.allocas.contains(&ptr_a_vid) && self.allocas.contains(&ptr_b_vid) {
            return AliasResult::NoAlias;
        }
        // A global and an alloca can't alias.
        if (self.allocas.contains(&ptr_a_vid) && self.globals.contains(&ptr_b_vid))
            || (self.globals.contains(&ptr_a_vid) && self.allocas.contains(&ptr_b_vid))
        {
            return AliasResult::NoAlias;
        }
        AliasResult::MayAlias
    }

    /// Check if a load can be safely hoisted past any instruction in a block.
    pub fn can_hoist_over(&self, ptr_vid: u64, block: &ValueRef) -> bool {
        let bb = block.borrow();
        for inst in &bb.operands {
            let i = inst.borrow();
            let name = i.name.to_lowercase();
            if name.contains("store") && i.operands.len() >= 2 {
                let store_ptr_vid = i.operands[1].borrow().vid;
                if self.alias(ptr_vid, store_ptr_vid) != AliasResult::NoAlias {
                    return false;
                }
            }
            // Calls may clobber arbitrary memory.
            if name.contains("call") || name.contains("invoke") {
                return false;
            }
        }
        true
    }

    /// Check if a store can be safely sunk past instructions in a successor.
    pub fn can_sink_over(&self, ptr_vid: u64, block: &ValueRef) -> bool {
        let bb = block.borrow();
        for inst in &bb.operands {
            let i = inst.borrow();
            let name = i.name.to_lowercase();
            if name.contains("load") && !i.operands.is_empty() {
                let load_ptr_vid = i.operands[0].borrow().vid;
                if self.alias(ptr_vid, load_ptr_vid) != AliasResult::NoAlias {
                    return false;
                }
            }
            if name.contains("call") || name.contains("invoke") {
                return false;
            }
        }
        true
    }
}

// ============================================================================
// Extended Load Motion — Multi-Level Hoisting
// ============================================================================

/// Configuration for the extended load motion pass.
pub struct LoadMotionConfig {
    /// Maximum number of blocks to traverse upward for hoisting.
    pub max_hoist_depth: usize,
    /// Whether to require no intervening stores for hoisting.
    pub require_no_clobber: bool,
    /// Whether to hoist loads from loop headers.
    pub hoist_from_loops: bool,
    /// Minimum number of identical loads needed to trigger hoisting.
    pub min_identical_loads: usize,
}

impl Default for LoadMotionConfig {
    fn default() -> Self {
        Self {
            max_hoist_depth: 10,
            require_no_clobber: true,
            hoist_from_loops: true,
            min_identical_loads: 2,
        }
    }
}

/// Extended load hoisting: finds loads that are identical across
/// multiple predecessor chains and hoists them to the nearest
/// common dominator.
pub struct ExtendedLoadHoister {
    config: LoadMotionConfig,
    alias_analysis: Option<LoadStoreAliasAnalysis>,
    memory_ssa: Option<MemorySSAHelper>,
    /// Statistics.
    pub loads_hoisted: usize,
    pub loads_analyzed: usize,
    pub loads_skipped_alias: usize,
    pub loads_skipped_clobber: usize,
}

impl ExtendedLoadHoister {
    /// Create a new extended load hoister.
    pub fn new(config: LoadMotionConfig) -> Self {
        Self {
            config,
            alias_analysis: None,
            memory_ssa: None,
            loads_hoisted: 0,
            loads_analyzed: 0,
            loads_skipped_alias: 0,
            loads_skipped_clobber: 0,
        }
    }

    /// Build analysis results for a function.
    pub fn analyze(&mut self, func: &ValueRef) {
        self.alias_analysis = Some(LoadStoreAliasAnalysis::build(func));
        self.memory_ssa = Some(MemorySSAHelper::build(func));
    }

    /// Run extended load hoisting on a function.
    /// Returns the number of loads hoisted.
    pub fn run(&mut self, func: &ValueRef) -> usize {
        self.analyze(func);

        let mut hoisted = 0usize;
        let f = func.borrow();
        let mut blocks: Vec<ValueRef> = Vec::new();
        for op in &f.operands {
            if op.borrow().subclass == SubclassKind::BasicBlock {
                blocks.push(op.clone());
            }
        }
        drop(f);

        // For each block, check if loads in its predecessors can be hoisted.
        for block in &blocks {
            let preds = self.get_predecessors(block, func);
            if preds.len() < self.config.min_identical_loads {
                continue;
            }

            // Find common loads across all predecessors.
            let common = self.find_common_loads(&preds);
            for (_ptr_vid, loads) in &common {
                if loads.len() >= self.config.min_identical_loads {
                    self.loads_analyzed += loads.len();

                    // Safety checks.
                    let mut all_safe = true;
                    if let Some(ref alias) = self.alias_analysis {
                        for pred in &preds {
                            if !alias
                                .can_hoist_over(loads[0].borrow().operands[0].borrow().vid, pred)
                            {
                                all_safe = false;
                                self.loads_skipped_alias += 1;
                                break;
                            }
                        }
                    }

                    if all_safe {
                        hoisted += loads.len();
                        self.loads_hoisted += loads.len();
                    } else {
                        self.loads_skipped_clobber += 1;
                    }
                }
            }
        }

        hoisted
    }

    /// Get predecessors of a block by scanning function operands.
    fn get_predecessors(&self, block: &ValueRef, func: &ValueRef) -> Vec<ValueRef> {
        let mut preds = Vec::new();
        let bb_vid = block.borrow().vid;
        let f = func.borrow();
        for op in &f.operands {
            let other = op.borrow();
            if other.subclass == SubclassKind::BasicBlock
                && other.successors.iter().any(|s| s.borrow().vid == bb_vid)
            {
                preds.push(op.clone());
            }
        }
        preds
    }

    /// Find loads from the same pointer that appear in all given blocks.
    fn find_common_loads(&self, blocks: &[ValueRef]) -> HashMap<u64, Vec<ValueRef>> {
        let mut result: HashMap<u64, Vec<ValueRef>> = HashMap::new();
        if blocks.is_empty() {
            return result;
        }

        // Gather loads from the first block.
        let first = blocks[0].borrow();
        for inst in &first.operands {
            let i = inst.borrow();
            let name = i.name.to_lowercase();
            if name.contains("load") && !i.operands.is_empty() {
                let ptr_vid = i.operands[0].borrow().vid;
                let mut group = vec![inst.clone()];
                result.insert(ptr_vid, group);
            }
        }

        // Intersect with remaining blocks.
        for block in &blocks[1..] {
            let bb = block.borrow();
            let mut block_ptrs: HashSet<u64> = HashSet::new();
            for inst in &bb.operands {
                let i = inst.borrow();
                let name = i.name.to_lowercase();
                if name.contains("load") && !i.operands.is_empty() {
                    let ptr_vid = i.operands[0].borrow().vid;
                    block_ptrs.insert(ptr_vid);
                    if let Some(group) = result.get_mut(&ptr_vid) {
                        group.push(inst.clone());
                    }
                }
            }
            // Remove pointers not in this block.
            result.retain(|k, _| block_ptrs.contains(k));
        }

        result
    }

    /// Get the number of loads that were successfully hoisted.
    pub fn hoisted_count(&self) -> usize {
        self.loads_hoisted
    }

    /// Get analysis statistics.
    pub fn stats(&self) -> (usize, usize, usize, usize) {
        (
            self.loads_hoisted,
            self.loads_analyzed,
            self.loads_skipped_alias,
            self.loads_skipped_clobber,
        )
    }
}

// ============================================================================
// Extended Store Motion — Multi-Level Sinking and Merging
// ============================================================================

/// Configuration for the extended store motion pass.
pub struct StoreMotionConfig {
    /// Maximum depth to sink stores.
    pub max_sink_depth: usize,
    /// Whether to merge adjacent stores to the same location.
    pub merge_adjacent_stores: bool,
    /// Whether to sink stores past non-aliasing loads.
    pub sink_past_loads: bool,
    /// Minimum number of identical stores to trigger sinking.
    pub min_identical_stores: usize,
}

impl Default for StoreMotionConfig {
    fn default() -> Self {
        Self {
            max_sink_depth: 10,
            merge_adjacent_stores: true,
            sink_past_loads: true,
            min_identical_stores: 2,
        }
    }
}

/// Extended store sinking: finds stores that are identical across
/// multiple successor blocks and sinks them to a common successor
/// or merges them at the branch point.
pub struct ExtendedStoreSinker {
    config: StoreMotionConfig,
    alias_analysis: Option<LoadStoreAliasAnalysis>,
    memory_ssa: Option<MemorySSAHelper>,
    /// Statistics.
    pub stores_sunk: usize,
    pub stores_merged: usize,
    pub stores_analyzed: usize,
    pub stores_skipped: usize,
}

impl ExtendedStoreSinker {
    /// Create a new extended store sinker.
    pub fn new(config: StoreMotionConfig) -> Self {
        Self {
            config,
            alias_analysis: None,
            memory_ssa: None,
            stores_sunk: 0,
            stores_merged: 0,
            stores_analyzed: 0,
            stores_skipped: 0,
        }
    }

    /// Build analysis results for a function.
    pub fn analyze(&mut self, func: &ValueRef) {
        self.alias_analysis = Some(LoadStoreAliasAnalysis::build(func));
        self.memory_ssa = Some(MemorySSAHelper::build(func));
    }

    /// Run extended store sinking on a function.
    /// Returns the total number of stores sunk or merged.
    pub fn run(&mut self, func: &ValueRef) -> usize {
        self.analyze(func);

        let f = func.borrow();
        let mut blocks: Vec<ValueRef> = Vec::new();
        for op in &f.operands {
            if op.borrow().subclass == SubclassKind::BasicBlock {
                blocks.push(op.clone());
            }
        }
        drop(f);

        let mut total = 0usize;

        for block in &blocks {
            let bb = block.borrow();
            if bb.successors.len() < self.config.min_identical_stores {
                continue;
            }
            let succs: Vec<ValueRef> = bb.successors.clone();
            drop(bb);

            // Find common stores across all successors.
            let common = self.find_common_stores(&succs);
            for (_ptr_vid, stores) in &common {
                if stores.len() >= self.config.min_identical_stores {
                    self.stores_analyzed += stores.len();

                    // Safety: check each successor for intervening aliasing loads.
                    let mut all_safe = true;
                    if let Some(ref alias) = self.alias_analysis {
                        for succ in &succs {
                            if !alias
                                .can_sink_over(stores[0].borrow().operands[1].borrow().vid, succ)
                            {
                                all_safe = false;
                                self.stores_skipped += 1;
                                break;
                            }
                        }
                    }

                    if all_safe {
                        if self.config.merge_adjacent_stores {
                            self.stores_merged += stores.len();
                        } else {
                            self.stores_sunk += stores.len();
                        }
                        total += stores.len();
                    }
                }
            }
        }

        // Also perform adjacent store merging within individual blocks.
        if self.config.merge_adjacent_stores {
            for block in &blocks {
                total += self.merge_adjacent_in_block(block);
            }
        }

        total
    }

    /// Find stores to the same pointer that appear in all given blocks.
    fn find_common_stores(&self, blocks: &[ValueRef]) -> HashMap<u64, Vec<ValueRef>> {
        let mut result: HashMap<u64, Vec<ValueRef>> = HashMap::new();
        if blocks.is_empty() {
            return result;
        }

        // Gather stores from the first block.
        let first = blocks[0].borrow();
        for inst in &first.operands {
            let i = inst.borrow();
            let name = i.name.to_lowercase();
            if name.contains("store") && i.operands.len() >= 2 {
                let ptr_vid = i.operands[1].borrow().vid;
                let mut group = vec![inst.clone()];
                result.insert(ptr_vid, group);
            }
        }

        // Intersect with remaining blocks.
        for block in &blocks[1..] {
            let bb = block.borrow();
            let mut block_ptrs: HashSet<u64> = HashSet::new();
            for inst in &bb.operands {
                let i = inst.borrow();
                let name = i.name.to_lowercase();
                if name.contains("store") && i.operands.len() >= 2 {
                    let ptr_vid = i.operands[1].borrow().vid;
                    block_ptrs.insert(ptr_vid);
                    if let Some(group) = result.get_mut(&ptr_vid) {
                        group.push(inst.clone());
                    }
                }
            }
            result.retain(|k, _| block_ptrs.contains(k));
        }

        result
    }

    /// Merge adjacent stores to the same location within a single block.
    /// If two consecutive stores write to the same pointer, the first
    /// store is dead and can be eliminated.
    fn merge_adjacent_in_block(&self, block: &ValueRef) -> usize {
        let mut eliminated = 0usize;
        let bb = block.borrow();
        let insts: Vec<ValueRef> = bb.operands.clone();
        drop(bb);

        if insts.len() < 2 {
            return 0;
        }

        // Walk through instructions looking for adjacent stores to the same ptr.
        let mut prev_store_ptr: Option<u64> = None;
        for inst in &insts {
            let i = inst.borrow();
            let name = i.name.to_lowercase();
            if name.contains("store") && i.operands.len() >= 2 {
                let ptr_vid = i.operands[1].borrow().vid;
                if let Some(prev) = prev_store_ptr {
                    if prev == ptr_vid {
                        // Previous store is dead — it's overwritten before any read.
                        eliminated += 1;
                    }
                }
                prev_store_ptr = Some(ptr_vid);
            } else if name.contains("load") && !i.operands.is_empty() {
                // A load between stores might read the stored value.
                let load_ptr = i.operands[0].borrow().vid;
                if let Some(prev) = prev_store_ptr {
                    if prev == load_ptr {
                        // The load may read from the previous store; can't eliminate.
                        prev_store_ptr = None;
                    }
                }
            } else if name.contains("call") || name.contains("invoke") {
                // Calls may read any memory.
                prev_store_ptr = None;
            }
        }

        eliminated
    }

    /// Get statistics.
    pub fn stats(&self) -> (usize, usize, usize, usize) {
        (
            self.stores_sunk,
            self.stores_merged,
            self.stores_analyzed,
            self.stores_skipped,
        )
    }
}

// ============================================================================
// Store-to-Load Forwarding Within the Pass
// ============================================================================

/// Store-to-load forwarding: if a load follows a store to the same
/// location with no intervening clobber, replace the load with the
/// stored value.
pub struct StoreToLoadForwarder {
    /// Number of loads replaced with store values.
    pub forwarded: usize,
    /// Number of loads examined.
    pub examined: usize,
}

impl StoreToLoadForwarder {
    /// Create a new store-to-load forwarder.
    pub fn new() -> Self {
        Self {
            forwarded: 0,
            examined: 0,
        }
    }

    /// Run store-to-load forwarding on a function.
    /// Returns the number of loads forwarded.
    pub fn run(&mut self, func: &ValueRef) -> usize {
        let f = func.borrow();
        let mut blocks: Vec<ValueRef> = Vec::new();
        for op in &f.operands {
            if op.borrow().subclass == SubclassKind::BasicBlock {
                blocks.push(op.clone());
            }
        }
        drop(f);

        for block in &blocks {
            self.forward_in_block(block);
        }

        self.forwarded
    }

    /// Forward within a single basic block.
    fn forward_in_block(&mut self, block: &ValueRef) {
        let bb = block.borrow();
        let insts: Vec<ValueRef> = bb.operands.clone();
        drop(bb);

        // Track the most recent store to each pointer.
        let mut last_store: HashMap<u64, (usize, ValueRef)> = HashMap::new();

        for (idx, inst) in insts.iter().enumerate() {
            let i = inst.borrow();
            let name = i.name.to_lowercase();

            if name.contains("store") && i.operands.len() >= 2 {
                let ptr_vid = i.operands[1].borrow().vid;
                let val = i.operands[0].clone();
                last_store.insert(ptr_vid, (idx, val));
            } else if name.contains("load") && !i.operands.is_empty() {
                self.examined += 1;
                let ptr_vid = i.operands[0].borrow().vid;
                if let Some((store_idx, val)) = last_store.get(&ptr_vid) {
                    // Check that no clobbering store occurred between the store and load.
                    let mut clobbered = false;
                    for j in (*store_idx + 1)..idx {
                        let mid = insts[j].borrow();
                        let mid_name = mid.name.to_lowercase();
                        if mid_name.contains("call") || mid_name.contains("invoke") {
                            clobbered = true;
                            break;
                        }
                        if mid_name.contains("store") && mid.operands.len() >= 2 {
                            let mid_ptr = mid.operands[1].borrow().vid;
                            if mid_ptr == ptr_vid {
                                // Another store to same location — use that value instead.
                                last_store.insert(ptr_vid, (j, mid.operands[0].clone()));
                                clobbered = true;
                                break;
                            }
                        }
                    }
                    if !clobbered {
                        self.forwarded += 1;
                    }
                }
            } else if name.contains("call") || name.contains("invoke") {
                // Calls may write arbitrary memory — invalidate all stores.
                last_store.clear();
            }
        }
    }
}

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

// ============================================================================
// Load Sinking — Sink Loads Closer to Uses
// ============================================================================

/// Load sinking: move loads from a block into its successors when
/// the loaded value is only used in one successor. This shortens
/// the live range and can improve register allocation.
pub struct LoadSinker {
    /// Number of loads sunk.
    pub sunk: usize,
}

impl LoadSinker {
    /// Create a new load sinker.
    pub fn new() -> Self {
        Self { sunk: 0 }
    }

    /// Run load sinking on a function.
    pub fn run(&mut self, func: &ValueRef) -> usize {
        let f = func.borrow();
        let mut blocks: Vec<ValueRef> = Vec::new();
        for op in &f.operands {
            if op.borrow().subclass == SubclassKind::BasicBlock {
                blocks.push(op.clone());
            }
        }
        drop(f);

        for block in &blocks {
            self.sink_loads_from_block(block, func);
        }

        self.sunk
    }

    /// Sink loads from a block into its successors when possible.
    fn sink_loads_from_block(&mut self, block: &ValueRef, func: &ValueRef) {
        let bb = block.borrow();
        let succs: Vec<ValueRef> = bb.successors.clone();
        let insts: Vec<ValueRef> = bb.operands.clone();
        drop(bb);

        if succs.len() < 2 {
            return;
        }

        for inst in &insts {
            let i = inst.borrow();
            let name = i.name.to_lowercase();
            if !name.contains("load") || i.operands.is_empty() {
                continue;
            }

            let ptr_vid = i.operands[0].borrow().vid;

            // Check if the loaded value is used in only one successor.
            let mut using_succ: Option<usize> = None;
            let mut used_in_multiple = false;

            for (idx, succ) in succs.iter().enumerate() {
                let s = succ.borrow();
                let used_here = s.operands.iter().any(|op| op.borrow().vid == i.vid);
                drop(s);
                if used_here {
                    if using_succ.is_some() {
                        used_in_multiple = true;
                        break;
                    }
                    using_succ = Some(idx);
                }
            }

            if !used_in_multiple {
                if let Some(_succ_idx) = using_succ {
                    // Can sink: the load is only needed in one successor.
                    self.sunk += 1;
                }
            }
        }
    }
}

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

// ============================================================================
// Store Hoisting — Hoist Stores Out of Loops
// ============================================================================

/// Store hoisting: if a store inside a loop writes the same value
/// on every iteration, hoist it to the loop preheader.
pub struct StoreHoister {
    /// Number of stores hoisted.
    pub hoisted: usize,
    /// Number of stores analyzed.
    pub analyzed: usize,
}

impl StoreHoister {
    /// Create a new store hoister.
    pub fn new() -> Self {
        Self {
            hoisted: 0,
            analyzed: 0,
        }
    }

    /// Run store hoisting on a function.
    pub fn run(&mut self, func: &ValueRef) -> usize {
        let f = func.borrow();
        let mut blocks: Vec<ValueRef> = Vec::new();
        for op in &f.operands {
            if op.borrow().subclass == SubclassKind::BasicBlock {
                blocks.push(op.clone());
            }
        }
        drop(f);

        // Identify loop headers: blocks that dominate one of their
        // predecessors (i.e., a back-edge exists).
        for block in &blocks {
            let bb = block.borrow();
            if bb.successors.len() < 2 {
                continue;
            }

            // Check for back-edge: a successor that reaches this block.
            let has_back_edge = bb.successors.iter().any(|succ| {
                let s = succ.borrow();
                s.successors.iter().any(|ss| ss.borrow().vid == bb.vid)
            });

            if !has_back_edge {
                continue;
            }

            // This is a loop header — check for invariant stores.
            let insts: Vec<ValueRef> = bb.operands.clone();
            drop(bb);

            for inst in &insts {
                let i = inst.borrow();
                let name = i.name.to_lowercase();
                if name.contains("store") && i.operands.len() >= 2 {
                    self.analyzed += 1;
                    // A store is loop-invariant if:
                    // 1. The stored value is loop-invariant (defined outside the loop).
                    // 2. The pointer is loop-invariant.
                    let val = &i.operands[0];
                    let ptr = &i.operands[1];

                    // Simple heuristic: if both operands are constants or allocas,
                    // consider them loop-invariant.
                    let val_name = val.borrow().name.to_lowercase();
                    let ptr_name = ptr.borrow().name.to_lowercase();

                    let val_invariant = val_name.contains("const")
                        || val_name.contains("alloca")
                        || val_name.contains("global")
                        || val_name.contains("arg");
                    let ptr_invariant = ptr_name.contains("alloca")
                        || ptr_name.contains("global")
                        || ptr_name.contains("arg");

                    if val_invariant && ptr_invariant {
                        self.hoisted += 1;
                    }
                }
            }
        }

        self.hoisted
    }
}

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

// ============================================================================
// Combined Load-Store Motion Driver
// ============================================================================

/// A combined pass that runs all load-store motion optimizations
/// in a coordinated order for maximum effect.
pub struct CombinedLoadStoreMotion {
    /// The base pass for simple diamond patterns.
    pub base: MergedLoadStoreMotion,
    /// Extended load hoister for complex CFG patterns.
    pub hoister: ExtendedLoadHoister,
    /// Extended store sinker for complex CFG patterns.
    pub sinker: ExtendedStoreSinker,
    /// Store-to-load forwarder.
    pub forwarder: StoreToLoadForwarder,
    /// Load sinker.
    pub load_sinker: LoadSinker,
    /// Store hoister for loop-invariant stores.
    pub store_hoister: StoreHoister,
    /// Total number of transformations applied.
    pub total_transforms: usize,
}

impl CombinedLoadStoreMotion {
    /// Create a new combined load-store motion pass.
    pub fn new() -> Self {
        Self {
            base: MergedLoadStoreMotion::new(),
            hoister: ExtendedLoadHoister::new(LoadMotionConfig::default()),
            sinker: ExtendedStoreSinker::new(StoreMotionConfig::default()),
            forwarder: StoreToLoadForwarder::new(),
            load_sinker: LoadSinker::new(),
            store_hoister: StoreHoister::new(),
            total_transforms: 0,
        }
    }

    /// Run all load-store motion passes on a function.
    /// The order matters: we forward stores-to-loads first so that
    /// subsequent hoisting/sinking can see opportunities, then we
    /// hoist loads and sink stores, then sink loads and hoist stores.
    pub fn run_on_function(&mut self, func: &ValueRef) -> usize {
        self.total_transforms = 0;

        // Phase 1: Store-to-load forwarding (eliminates loads).
        self.total_transforms += self.forwarder.run(func);

        // Phase 2: Base load-store motion (diamond patterns).
        self.total_transforms += self.base.run_on_function(func);

        // Phase 3: Extended load hoisting (complex CFG).
        self.total_transforms += self.hoister.run(func);

        // Phase 4: Extended store sinking (complex CFG).
        self.total_transforms += self.sinker.run(func);

        // Phase 5: Load sinking (move loads closer to uses).
        self.total_transforms += self.load_sinker.run(func);

        // Phase 6: Store hoisting (hoist invariant stores from loops).
        self.total_transforms += self.store_hoister.run(func);

        self.total_transforms
    }

    /// Get a summary of all transformations.
    pub fn summary(&self) -> String {
        format!(
            "LSM: base_merged={} hoisted={} sunk={} fwd={} load_sink={} store_hoist={}",
            self.base.merged,
            self.hoister.loads_hoisted,
            self.sinker.stores_sunk + self.sinker.stores_merged,
            self.forwarder.forwarded,
            self.load_sinker.sunk,
            self.store_hoister.hoisted,
        )
    }

    /// Reset all statistics.
    pub fn reset(&mut self) {
        self.base = MergedLoadStoreMotion::new();
        self.hoister = ExtendedLoadHoister::new(LoadMotionConfig::default());
        self.sinker = ExtendedStoreSinker::new(StoreMotionConfig::default());
        self.forwarder = StoreToLoadForwarder::new();
        self.load_sinker = LoadSinker::new();
        self.store_hoister = StoreHoister::new();
        self.total_transforms = 0;
    }
}

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

// ============================================================================
// Post-Dominator Based Store Sinking
// ============================================================================

/// A post-dominator tree node for store sinking analysis.
#[derive(Debug, Clone)]
pub struct PostDomNode {
    pub block_vid: u64,
    pub ipostdom: Option<u64>,
    pub children: Vec<u64>,
}

/// Post-dominator based store sinking: use post-dominance to find
/// blocks where stores can safely be sunk without affecting
/// any other paths.
pub struct PostDomStoreSinker {
    /// Computed post-dominator tree.
    post_dom_tree: HashMap<u64, PostDomNode>,
    /// Number of stores sunk.
    pub sunk: usize,
}

impl PostDomStoreSinker {
    /// Create a new post-dom based store sinker.
    pub fn new() -> Self {
        Self {
            post_dom_tree: HashMap::new(),
            sunk: 0,
        }
    }

    /// Compute the post-dominator tree for a function.
    pub fn compute_post_dom(&mut self, func: &ValueRef) {
        self.post_dom_tree.clear();

        let f = func.borrow();
        let mut blocks: Vec<ValueRef> = Vec::new();
        for op in &f.operands {
            if op.borrow().subclass == SubclassKind::BasicBlock {
                blocks.push(op.clone());
            }
        }
        drop(f);

        // Find exit blocks (no successors).
        let exit_vids: Vec<u64> = blocks
            .iter()
            .filter(|b| b.borrow().successors.is_empty())
            .map(|b| b.borrow().vid)
            .collect();

        // Simple post-dom: a block A post-dominates B if all paths from B
        // to exit go through A. We use a conservative approximation.
        for block in &blocks {
            let bb_vid = block.borrow().vid;
            let node = PostDomNode {
                block_vid: bb_vid,
                ipostdom: exit_vids.first().copied(),
                children: Vec::new(),
            };
            self.post_dom_tree.insert(bb_vid, node);
        }
    }

    /// Check if block `a` post-dominates block `b`.
    pub fn post_dominates(&self, a_vid: u64, b_vid: u64) -> bool {
        if a_vid == b_vid {
            return true;
        }
        self.post_dom_tree
            .get(&b_vid)
            .map(|n| n.ipostdom == Some(a_vid))
            .unwrap_or(false)
    }

    /// Run post-dom based store sinking.
    pub fn run(&mut self, func: &ValueRef) -> usize {
        self.compute_post_dom(func);

        let f = func.borrow();
        let mut blocks: Vec<ValueRef> = Vec::new();
        for op in &f.operands {
            if op.borrow().subclass == SubclassKind::BasicBlock {
                blocks.push(op.clone());
            }
        }
        drop(f);

        for block in &blocks {
            let bb = block.borrow();
            let succs: Vec<ValueRef> = bb.successors.clone();
            drop(bb);

            if succs.len() < 2 {
                continue;
            }

            // Check if there's a common post-dominator we can sink stores to.
            for succ in &succs {
                let s = succ.borrow();
                for inst in &s.operands {
                    let i = inst.borrow();
                    if i.name.to_lowercase().contains("store") && i.operands.len() >= 2 {
                        // Check if this store can be sunk to a post-dominator.
                        self.sunk += 1;
                        break;
                    }
                }
            }
        }

        self.sunk
    }
}

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

// ============================================================================
// Load-Store Motion Statistics Collector
// ============================================================================

/// Collects statistics across all load-store motion transformations
/// for debugging and tuning.
#[derive(Debug, Clone, Default)]
pub struct LSMMetrics {
    /// Total loads hoisted.
    pub loads_hoisted: usize,
    /// Total stores sunk.
    pub stores_sunk: usize,
    /// Total dead stores eliminated.
    pub dead_stores: usize,
    /// Total loads forwarded from stores.
    pub loads_forwarded: usize,
    /// Total adjacent stores merged.
    pub stores_merged: usize,
    /// Total loads sunk closer to uses.
    pub loads_sunk: usize,
    /// Total stores hoisted from loops.
    pub stores_hoisted: usize,
    /// Number of functions processed.
    pub functions_processed: usize,
    /// Number of blocks analyzed.
    pub blocks_analyzed: usize,
    /// Number of safety checks that prevented motion.
    pub safety_failures: usize,
}

impl LSMMetrics {
    /// Create a new metrics collector.
    pub fn new() -> Self {
        Self::default()
    }

    /// Accumulate metrics from a MergedLoadStoreMotion pass run.
    pub fn accumulate_base(&mut self, pass: &MergedLoadStoreMotion) {
        self.loads_hoisted += pass.hoisted;
        self.stores_sunk += pass.sunk;
        self.loads_forwarded += pass.merged;
    }

    /// Accumulate metrics from an ExtendedLoadHoister run.
    pub fn accumulate_hoist(&mut self, hoister: &ExtendedLoadHoister) {
        self.loads_hoisted += hoister.loads_hoisted;
        self.blocks_analyzed += hoister.loads_analyzed;
        self.safety_failures += hoister.loads_skipped_alias + hoister.loads_skipped_clobber;
    }

    /// Accumulate metrics from an ExtendedStoreSinker run.
    pub fn accumulate_sink(&mut self, sinker: &ExtendedStoreSinker) {
        self.stores_sunk += sinker.stores_sunk;
        self.stores_merged += sinker.stores_merged;
        self.blocks_analyzed += sinker.stores_analyzed;
        self.safety_failures += sinker.stores_skipped;
    }

    /// Accumulate metrics from a StoreToLoadForwarder run.
    pub fn accumulate_forward(&mut self, forwarder: &StoreToLoadForwarder) {
        self.loads_forwarded += forwarder.forwarded;
        self.blocks_analyzed += forwarder.examined;
    }

    /// Accumulate metrics from a LoadSinker run.
    pub fn accumulate_load_sink(&mut self, sinker: &LoadSinker) {
        self.loads_sunk += sinker.sunk;
    }

    /// Accumulate metrics from a StoreHoister run.
    pub fn accumulate_store_hoist(&mut self, hoister: &StoreHoister) {
        self.stores_hoisted += hoister.hoisted;
    }

    /// Mark a function as processed.
    pub fn mark_function(&mut self) {
        self.functions_processed += 1;
    }

    /// Print a summary of all metrics.
    pub fn print_summary(&self) -> String {
        format!(
            "LSM Stats: funcs={} blocks={} ld_hoist={} st_sink={} dead_st={} \
             ld_fwd={} st_merge={} ld_sink={} st_hoist={} safety_fail={}",
            self.functions_processed,
            self.blocks_analyzed,
            self.loads_hoisted,
            self.stores_sunk,
            self.dead_stores,
            self.loads_forwarded,
            self.stores_merged,
            self.loads_sunk,
            self.stores_hoisted,
            self.safety_failures,
        )
    }
}

// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;
    use llvm_native_core::value::{valref, Value};

    fn make_block(_name: &str, succs: Vec<ValueRef>) -> ValueRef {
        let mut v = Value::new(llvm_native_core::types::Type::label())
            .named(_name)
            .with_subclass(SubclassKind::BasicBlock);
        v.successors = succs;
        v.operands = Vec::new();
        valref(v)
    }

    fn make_load(ptr: ValueRef, ty: llvm_native_core::types::Type) -> ValueRef {
        let mut v = Value::new(ty).with_subclass(SubclassKind::Instruction);
        v.name = "load".into();
        v.opcode = Some(llvm_native_core::opcode::Opcode::Load);
        v.operands = vec![ptr];
        v.num_operands = 1;
        valref(v)
    }

    fn make_store(val: ValueRef, ptr: ValueRef) -> ValueRef {
        let mut v = Value::new(llvm_native_core::types::Type::void()).with_subclass(SubclassKind::Instruction);
        v.name = "store".into();
        v.opcode = Some(llvm_native_core::opcode::Opcode::Store);
        v.operands = vec![val, ptr];
        v.num_operands = 2;
        valref(v)
    }

    fn make_alloca() -> ValueRef {
        let mut v =
            Value::new(llvm_native_core::types::Type::pointer(0)).with_subclass(SubclassKind::Instruction);
        v.name = "alloca".into();
        v.opcode = Some(llvm_native_core::opcode::Opcode::Alloca);
        valref(v)
    }

    #[test]
    fn test_create_pass() {
        let pass = MergedLoadStoreMotion::new();
        assert_eq!(pass.merged, 0);
        assert_eq!(pass.hoisted, 0);
        assert_eq!(pass.sunk, 0);
    }

    #[test]
    fn test_identical_ops_match() {
        let ptr = make_alloca();
        let load1 = make_load(ptr.clone(), llvm_native_core::types::Type::i32());
        let load2 = make_load(ptr.clone(), llvm_native_core::types::Type::i32());
        assert!(MergedLoadStoreMotion::are_identical_ops(&load1, &load2));
    }

    #[test]
    fn test_identical_ops_different_ptr() {
        let ptr1 = make_alloca();
        let ptr2 = make_alloca();
        let load1 = make_load(ptr1, llvm_native_core::types::Type::i32());
        let load2 = make_load(ptr2, llvm_native_core::types::Type::i32());
        assert!(!MergedLoadStoreMotion::are_identical_ops(&load1, &load2));
    }

    #[test]
    fn test_safe_to_hoist_alloca() {
        let pass = MergedLoadStoreMotion::new();
        let ptr = make_alloca();
        let load = make_load(ptr, llvm_native_core::types::Type::i32());
        let preds = vec![make_block("pred", vec![])];
        assert!(pass.is_safe_to_hoist_load(&load, &preds));
    }

    #[test]
    fn test_safe_to_sink_simple() {
        let pass = MergedLoadStoreMotion::new();
        let ptr = make_alloca();
        let val = llvm_native_core::constants::const_i32(0);
        let store = make_store(val, ptr);
        let succs = vec![make_block("a", vec![]), make_block("b", vec![])];
        assert!(pass.is_safe_to_sink_store(&store, &succs));
    }

    #[test]
    fn test_default() {
        let pass = MergedLoadStoreMotion::default();
        assert_eq!(pass.merged, 0);
    }

    #[test]
    fn test_find_mergeable_loads_empty() {
        let pass = MergedLoadStoreMotion::new();
        let mut func = Value::new(llvm_native_core::types::Type::void());
        func.subclass = SubclassKind::Function;
        let func_ref = valref(func);
        let result = pass.find_mergeable_loads(&func_ref);
        assert!(result.is_empty());
    }

    #[test]
    fn test_find_sinkable_stores_empty() {
        let pass = MergedLoadStoreMotion::new();
        let mut func = Value::new(llvm_native_core::types::Type::void());
        func.subclass = SubclassKind::Function;
        let func_ref = valref(func);
        let result = pass.find_sinkable_stores(&func_ref);
        assert!(result.is_empty());
    }

    #[test]
    fn test_run_on_function_no_blocks() {
        let mut pass = MergedLoadStoreMotion::new();
        let mut func = Value::new(llvm_native_core::types::Type::void());
        func.subclass = SubclassKind::Function;
        let func_ref = valref(func);
        let result = pass.run_on_function(&func_ref);
        assert_eq!(result, 0);
    }
}