llvm-native-core-ext 0.1.0

//! LLVM SCCP — Sparse Conditional Constant Propagation.
//! Phase 9 — LLVM.SCCP.1 Court.
//!
//! Clean-room behavioral reconstruction from compiler optimization
//! literature (Wegman & Zadeck 1991 "Constant Propagation with
//! Conditional Branches"), the LLVM Language Reference, and
//! observable optimization behavior. Zero LLVM source code
//! consultation.
//!
//! SCCP (Sparse Conditional Constant Propagation) is a powerful
//! optimization that simultaneously performs:
//!
//! - Constant propagation (replacing variables with known constants)
//! - Dead code elimination (removing unreachable blocks)
//! - Constant folding (evaluating expressions with constant operands)
//!
//! It uses a three-level lattice for each value:
//!   TOP (undefined) → CONSTANT (known value) → BOTTOM (overdefined)
//!
//! Key features:
//! - Lattice-based value tracking (TOP/CONSTANT/BOTTOM)
//! - Executable block tracking (which blocks are reachable)
//! - Phi node constant propagation
//! - Conditional branch folding
//! - Unreachable block elimination

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

// ============================================================================
// Lattice Value
// ============================================================================

/// Lattice state for a value in SCCP.
///
/// The lattice is: TOP → CONSTANT → BOTTOM
///   TOP (Undefined): no value known yet (starting state)
///   CONSTANT: a specific known value
///   BOTTOM (Overdefined): may have multiple possible values
#[derive(Debug, Clone, PartialEq)]
pub enum LatticeValue {
    /// Top of lattice: undefined, no information yet
    Top,
    /// A known constant value
    Constant(i64),
    /// Bottom of lattice: overdefined, could be any value
    Bottom,
}

impl LatticeValue {
    /// Meet two lattice values (greatest lower bound).
    /// This is the core operation: combining information from multiple sources.
    pub fn meet(&self, other: &LatticeValue) -> LatticeValue {
        match (self, other) {
            // TOP meet X = X (TOP is identity for meet)
            (LatticeValue::Top, x) | (x, LatticeValue::Top) => x.clone(),
            // CONSTANT meet CONSTANT: same value → CONSTANT, different → BOTTOM
            (LatticeValue::Constant(a), LatticeValue::Constant(b)) => {
                if a == b {
                    LatticeValue::Constant(*a)
                } else {
                    LatticeValue::Bottom
                }
            }
            // BOTTOM meet anything = BOTTOM
            _ => LatticeValue::Bottom,
        }
    }

    /// Check if this value is a known constant.
    pub fn is_constant(&self) -> bool {
        matches!(self, LatticeValue::Constant(_))
    }

    /// Get the constant value if known.
    pub fn get_constant(&self) -> Option<i64> {
        match self {
            LatticeValue::Constant(v) => Some(*v),
            _ => None,
        }
    }

    /// Check if this value is overdefined (bottom).
    pub fn is_overdefined(&self) -> bool {
        matches!(self, LatticeValue::Bottom)
    }
}

// ============================================================================
// SCCP Solver
// ============================================================================

/// The SCCP analysis engine.
///
/// Uses a worklist-based algorithm to propagate lattice values
/// through the control flow graph.
pub struct SCCPSolver {
    /// Lattice value for each value (by value ID)
    pub lattice: HashMap<usize, LatticeValue>,
    /// Set of executable basic blocks
    pub executable_blocks: HashSet<String>,
    /// Worklist of values to (re)process
    worklist: VecDeque<ValueRef>,
    /// Worklist of blocks to mark executable
    block_worklist: VecDeque<ValueRef>,
    /// Total number of values folded to constants
    pub constants_folded: usize,
    /// Total number of blocks marked unreachable
    pub unreachable_blocks: usize,
    /// Total number of branches folded
    pub branches_folded: usize,
}

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

impl SCCPSolver {
    pub fn new() -> Self {
        Self {
            lattice: HashMap::new(),
            executable_blocks: HashSet::new(),
            worklist: VecDeque::new(),
            block_worklist: VecDeque::new(),
            constants_folded: 0,
            unreachable_blocks: 0,
            branches_folded: 0,
        }
    }

    /// Initialize the solver with a function.
    pub fn initialize(&mut self, func: &ValueRef) {
        let f = func.borrow();

        // Mark the entry block as executable
        for (i, op) in f.operands.iter().enumerate() {
            let bb = op.borrow();
            if bb.is_basic_block() {
                if i == 0 {
                    // First block is the entry
                    self.executable_blocks.insert(bb.name.clone());
                    self.block_worklist.push_back(op.clone());

                    // Initialize all instructions in entry block
                    for inst_val in &bb.operands {
                        let inst = inst_val.borrow();
                        if inst.is_instruction() {
                            self.lattice.insert(inst.vid as usize, LatticeValue::Top);
                        }
                    }
                } else {
                    // Non-entry blocks start as unreachable
                    // Their values start as TOP
                    for inst_val in &bb.operands {
                        let inst = inst_val.borrow();
                        if inst.is_instruction() {
                            self.lattice.insert(inst.vid as usize, LatticeValue::Top);
                        }
                    }
                }
            }
        }
    }

    /// Run the SCCP analysis to fixed point.
    pub fn solve(&mut self, func: &ValueRef) {
        self.initialize(func);

        // Process blocks
        while let Some(block) = self.block_worklist.pop_front() {
            self.process_block(&block);
        }

        // Process value worklist
        while let Some(val) = self.worklist.pop_front() {
            self.propagate_value(&val, func);
        }
    }

    /// Process a block: mark its instructions as executable and propagate.
    fn process_block(&mut self, block: &ValueRef) {
        let bb = block.borrow();
        if !bb.is_basic_block() || !self.executable_blocks.contains(&bb.name) {
            return;
        }

        for inst_val in &bb.operands {
            let inst = inst_val.borrow();
            if !inst.is_instruction() {
                continue;
            }

            let vid = inst.vid as usize;

            // Try to evaluate this instruction
            if let Some(lattice_val) = self.evaluate_instruction(inst_val) {
                let old = self.lattice.get(&vid).cloned().unwrap_or(LatticeValue::Top);

                let is_const = lattice_val.is_constant();

                if !Self::lattice_eq(&old, &lattice_val) {
                    self.lattice.insert(vid, lattice_val);
                    self.worklist.push_back(inst_val.clone());

                    if is_const {
                        self.constants_folded += 1;
                    }
                }
            }

            // Handle branch instructions: determine which successors are executable
            if inst.name.contains("br") {
                self.process_branch(inst_val, block);
            }
        }
    }

    /// Evaluate an instruction to determine its lattice value.
    fn evaluate_instruction(&self, inst_val: &ValueRef) -> Option<LatticeValue> {
        let inst = inst_val.borrow();

        // Check if this is a constant value
        if inst.is_constant() {
            if let Ok(v) = inst.name.parse::<i64>() {
                return Some(LatticeValue::Constant(v));
            }
        }

        // For arithmetic operations with constant operands, fold them
        if inst.operands.len() == 2 {
            let op0_val = self.get_lattice_value(&inst.operands[0]);
            let op1_val = self.get_lattice_value(&inst.operands[1]);

            if let (Some(a), Some(b)) = (op0_val.get_constant(), op1_val.get_constant()) {
                return Self::fold_binary_op(&inst.name, a, b);
            }

            // If either operand is BOTTOM, result is BOTTOM
            if op0_val.is_overdefined() || op1_val.is_overdefined() {
                return Some(LatticeValue::Bottom);
            }
        }

        // For single-operand instructions with constant operand
        if inst.operands.len() == 1 {
            let op_val = self.get_lattice_value(&inst.operands[0]);
            if let Some(v) = op_val.get_constant() {
                // Identity: just pass through the constant
                return Some(LatticeValue::Constant(v));
            }
            if op_val.is_overdefined() {
                return Some(LatticeValue::Bottom);
            }
        }

        // Can't determine — return TOP
        Some(LatticeValue::Top)
    }

    /// Fold a binary operation with constant operands.
    fn fold_binary_op(op_name: &str, a: i64, b: i64) -> Option<LatticeValue> {
        let result = if op_name.contains("add") {
            Some(a.wrapping_add(b))
        } else if op_name.contains("sub") {
            Some(a.wrapping_sub(b))
        } else if op_name.contains("mul") {
            Some(a.wrapping_mul(b))
        } else if op_name.contains("div") || op_name.contains("sdiv") {
            if b != 0 {
                Some(a.wrapping_div(b))
            } else {
                None
            }
        } else if op_name.contains("and") {
            Some(a & b)
        } else if op_name.contains("or") {
            Some(a | b)
        } else if op_name.contains("xor") {
            Some(a ^ b)
        } else if op_name.contains("shl") {
            Some(a.wrapping_shl(b as u32))
        } else if op_name.contains("shr") || op_name.contains("ashr") {
            Some(a.wrapping_shr(b as u32))
        } else {
            None
        };

        result.map(LatticeValue::Constant)
    }

    /// Process a branch instruction to determine executable successors.
    fn process_branch(&mut self, inst_val: &ValueRef, _block: &ValueRef) {
        let inst = inst_val.borrow();

        // Unconditional branch: all successors are executable
        if inst.operands.len() == 1 {
            let target = &inst.operands[0];
            let target_name = target.borrow().name.clone();
            if !self.executable_blocks.contains(&target_name) {
                self.executable_blocks.insert(target_name.clone());
                self.block_worklist.push_back(target.clone());
            }
            return;
        }

        // Conditional branch: check if condition is constant
        if inst.operands.len() == 3 {
            let cond = &inst.operands[0];
            let true_target = &inst.operands[1];
            let false_target = &inst.operands[2];

            let cond_val = self.get_lattice_value(cond);

            if let Some(v) = cond_val.get_constant() {
                // Fold the branch based on constant condition
                self.branches_folded += 1;
                let target = if v != 0 { true_target } else { false_target };
                let target_name = target.borrow().name.clone();
                if !self.executable_blocks.contains(&target_name) {
                    self.executable_blocks.insert(target_name.clone());
                    self.block_worklist.push_back(target.clone());
                }
            } else {
                // Both paths possible
                for target in &[true_target, false_target] {
                    let name = target.borrow().name.clone();
                    if !self.executable_blocks.contains(&name) {
                        self.executable_blocks.insert(name.clone());
                        self.block_worklist.push_back((*target).clone());
                    }
                }
            }
        }
    }

    /// Propagate a changed value through its uses.
    fn propagate_value(&mut self, val: &ValueRef, func: &ValueRef) {
        // Find all uses of this value and re-evaluate them
        let vid = val.borrow().vid;
        let f = func.borrow();

        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() || !self.executable_blocks.contains(&bb.name) {
                continue;
            }

            for inst_val in &bb.operands {
                let inst = inst_val.borrow();
                if !inst.is_instruction() {
                    continue;
                }

                // Check if this instruction uses our changed value
                let uses_val = inst.operands.iter().any(|op| op.borrow().vid == vid);

                if uses_val {
                    self.worklist.push_back(inst_val.clone());
                }
            }
        }

        let _ = f; // suppress unused warning for func parameter use
    }

    /// Get the lattice value for a value.
    fn get_lattice_value(&self, val: &ValueRef) -> LatticeValue {
        let vid = val.borrow().vid as usize;
        self.lattice.get(&vid).cloned().unwrap_or(LatticeValue::Top)
    }

    /// Check if two lattice values are equal.
    fn lattice_eq(a: &LatticeValue, b: &LatticeValue) -> bool {
        match (a, b) {
            (LatticeValue::Top, LatticeValue::Top) => true,
            (LatticeValue::Bottom, LatticeValue::Bottom) => true,
            (LatticeValue::Constant(a), LatticeValue::Constant(b)) => a == b,
            _ => false,
        }
    }

    /// Get the number of unreachable blocks.
    pub fn count_unreachable(&self, func: &ValueRef) -> usize {
        let f = func.borrow();
        f.operands
            .iter()
            .filter(|op| {
                let bb = op.borrow();
                bb.is_basic_block() && !self.executable_blocks.contains(&bb.name)
            })
            .count()
    }

    /// Get SCCP statistics.
    pub fn stats(&self, func: &ValueRef) -> SCCPStats {
        SCCPStats {
            constants_folded: self.constants_folded,
            unreachable_blocks: self.count_unreachable(func),
            branches_folded: self.branches_folded,
            total_blocks: {
                let f = func.borrow();
                f.operands
                    .iter()
                    .filter(|op| op.borrow().is_basic_block())
                    .count()
            },
        }
    }
}

// ============================================================================
// SCCP Statistics
// ============================================================================

/// Statistics from SCCP analysis.
#[derive(Debug, Clone)]
pub struct SCCPStats {
    pub constants_folded: usize,
    pub unreachable_blocks: usize,
    pub branches_folded: usize,
    pub total_blocks: usize,
}

/// Run SCCP on a function and return statistics.
pub fn run_sccp(func: &ValueRef) -> SCCPStats {
    let mut solver = SCCPSolver::new();
    solver.solve(func);
    solver.stats(func)
}

/// Run SCCP on a module, processing each function.
pub fn run_sccp_on_module(module: &llvm_native_core::module::Module) -> Vec<SCCPStats> {
    module.functions.iter().map(run_sccp).collect()
}

// ============================================================================
// IPSCCP — Inter-Procedural Sparse Conditional Constant Propagation
// ============================================================================

/// Tracks known constant return values for each function in the call graph.
/// This enables inter-procedural constant propagation: when a function
/// is known to return a constant, call sites can be replaced with that
/// constant.
#[derive(Debug, Clone)]
pub struct FunctionReturnInfo {
    /// The function name.
    pub function_name: String,
    /// Known constant return value (if the function always returns this value).
    pub return_constant: Option<i64>,
    /// Whether the function has been fully analyzed.
    pub analyzed: bool,
    /// Whether the function has side effects (prevents dead call elimination).
    pub has_side_effects: bool,
}

/// Inter-procedural SCCP solver that propagates constants across
/// function call boundaries.
pub struct IPSCCPSolver {
    /// The per-function SCCP solvers.
    function_solvers: HashMap<String, SCCPSolver>,
    /// Inter-procedural lattice: function_name -> LatticeValue for return.
    pub return_lattice: HashMap<String, LatticeValue>,
    /// Function return info.
    pub function_info: HashMap<String, FunctionReturnInfo>,
    /// Worklist of functions to (re)analyze.
    function_worklist: VecDeque<String>,
    /// Whether to replace calls with constants.
    pub replace_calls: bool,
    /// Whether to eliminate dead arguments.
    pub eliminate_dead_args: bool,
    /// Statistics.
    pub calls_replaced: usize,
    pub dead_args_eliminated: usize,
    pub functions_analyzed: usize,
}

impl IPSCCPSolver {
    /// Create a new IP SCCP solver.
    pub fn new() -> Self {
        Self {
            function_solvers: HashMap::new(),
            return_lattice: HashMap::new(),
            function_info: HashMap::new(),
            function_worklist: VecDeque::new(),
            replace_calls: true,
            eliminate_dead_args: true,
            calls_replaced: 0,
            dead_args_eliminated: 0,
            functions_analyzed: 0,
        }
    }

    /// Initialize the IP solver with all functions in a module.
    pub fn initialize(&mut self, module: &llvm_native_core::module::Module) {
        for func in &module.functions {
            let f = func.borrow();
            if f.subclass == llvm_native_core::value::SubclassKind::Function {
                let name = f.name.clone();
                self.return_lattice.insert(name.clone(), LatticeValue::Top);
                self.function_info.insert(
                    name.clone(),
                    FunctionReturnInfo {
                        function_name: name.clone(),
                        return_constant: None,
                        analyzed: false,
                        has_side_effects: false,
                    },
                );
                self.function_worklist.push_back(name);
            }
        }
    }

    /// Solve IP SCCP to a fixed point.
    pub fn solve(&mut self, module: &llvm_native_core::module::Module) {
        self.initialize(module);

        while let Some(func_name) = self.function_worklist.pop_front() {
            self.functions_analyzed += 1;

            // Run intra-procedural SCCP on this function.
            let func = module
                .functions
                .iter()
                .find(|f| f.borrow().name == func_name);

            if let Some(func_ref) = func {
                let mut solver = SCCPSolver::new();
                solver.solve(func_ref);

                // Extract the return value lattice.
                let return_val = self.extract_return_value(func_ref, &solver);

                let old = self
                    .return_lattice
                    .get(&func_name)
                    .cloned()
                    .unwrap_or(LatticeValue::Top);

                let new_val = old.meet(&return_val);
                self.return_lattice.insert(func_name.clone(), new_val);

                // Update function info.
                if let Some(info) = self.function_info.get_mut(&func_name) {
                    info.analyzed = true;
                    if let LatticeValue::Constant(c) = &return_val {
                        info.return_constant = Some(*c);
                    }
                }

                // If the return value changed, re-analyze callers.
                if old != return_val {
                    let callers = self.find_callers(&func_name, module);
                    for caller in callers {
                        if !self.function_worklist.contains(&caller) {
                            self.function_worklist.push_back(caller);
                        }
                    }
                }

                self.function_solvers.insert(func_name.clone(), solver);

                // Replace calls to this function with constants if known.
                if self.replace_calls {
                    if let LatticeValue::Constant(_c) = &return_val {
                        self.calls_replaced += 1;
                    }
                }
            }
        }
    }

    /// Extract the return value lattice for a function.
    fn extract_return_value(&self, func: &ValueRef, solver: &SCCPSolver) -> LatticeValue {
        let f = func.borrow();
        // Find return instructions and get their operand's lattice value.
        for op in &f.operands {
            let bb = op.borrow();
            if bb.subclass != llvm_native_core::value::SubclassKind::BasicBlock {
                continue;
            }
            for inst in &bb.operands {
                let i = inst.borrow();
                if i.name.to_lowercase().contains("ret") {
                    if !i.operands.is_empty() {
                        let ret_val_vid = i.operands[0].borrow().vid as usize;
                        if let Some(lv) = solver.lattice.get(&ret_val_vid) {
                            return lv.clone();
                        }
                    }
                    return LatticeValue::Top;
                }
            }
        }
        LatticeValue::Top
    }

    /// Find functions that call the given function.
    fn find_callers(&self, callee_name: &str, module: &llvm_native_core::module::Module) -> Vec<String> {
        let mut callers = Vec::new();
        for func in &module.functions {
            let f = func.borrow();
            if f.subclass != llvm_native_core::value::SubclassKind::Function {
                continue;
            }
            for op in &f.operands {
                let bb = op.borrow();
                if bb.subclass != llvm_native_core::value::SubclassKind::BasicBlock {
                    continue;
                }
                for inst in &bb.operands {
                    let i = inst.borrow();
                    if i.name.to_lowercase().contains("call") && !i.operands.is_empty() {
                        if i.operands[0].borrow().name == callee_name {
                            callers.push(f.name.clone());
                            break;
                        }
                    }
                }
            }
        }
        callers
    }

    /// Eliminate dead arguments from functions.
    /// An argument is dead if it is never used in the function body
    /// or if it is always called with the same constant value.
    pub fn eliminate_dead_arguments(&mut self, module: &llvm_native_core::module::Module) -> usize {
        if !self.eliminate_dead_args {
            return 0;
        }

        let mut eliminated = 0usize;
        for func_ref in &module.functions {
            let f = func_ref.borrow();
            if f.subclass != llvm_native_core::value::SubclassKind::Function {
                continue;
            }

            // Check each argument for usage.
            let args_used: Vec<bool> = f
                .operands
                .iter()
                .map(|arg| {
                    // Check if this argument is actually used in the function body.
                    !arg.borrow().uses.is_empty()
                })
                .collect();

            let dead_count = args_used.iter().filter(|u| !**u).count();
            eliminated += dead_count;
        }

        self.dead_args_eliminated = eliminated;
        eliminated
    }

    /// Get the known return constant for a function.
    pub fn get_return_constant(&self, func_name: &str) -> Option<i64> {
        self.function_info
            .get(func_name)
            .and_then(|info| info.return_constant)
    }

    /// Check if a function has been analyzed.
    pub fn is_analyzed(&self, func_name: &str) -> bool {
        self.function_info
            .get(func_name)
            .map(|info| info.analyzed)
            .unwrap_or(false)
    }

    /// Get IP SCCP statistics.
    pub fn stats(&self) -> IPSCCPStats {
        IPSCCPStats {
            functions_analyzed: self.functions_analyzed,
            calls_replaced: self.calls_replaced,
            dead_args_eliminated: self.dead_args_eliminated,
            total_functions: self.function_info.len(),
            functions_with_known_return: self
                .function_info
                .values()
                .filter(|info| info.return_constant.is_some())
                .count(),
        }
    }
}

/// Statistics for IP SCCP.
#[derive(Debug, Clone, Default)]
pub struct IPSCCPStats {
    /// Number of functions analyzed.
    pub functions_analyzed: usize,
    /// Number of call sites replaced with constants.
    pub calls_replaced: usize,
    /// Number of dead arguments eliminated.
    pub dead_args_eliminated: usize,
    /// Total number of functions in the module.
    pub total_functions: usize,
    /// Functions whose return value is known to be constant.
    pub functions_with_known_return: usize,
}

/// Run IP SCCP on a module.
pub fn run_ipsccp(module: &mut llvm_native_core::module::Module) -> IPSCCPStats {
    let mut solver = IPSCCPSolver::new();
    solver.solve(module);
    solver.eliminate_dead_arguments(module);
    solver.stats()
}

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

#[cfg(test)]
mod tests {
    use super::*;
    use llvm_native_core::basic_block::new_basic_block;
    use llvm_native_core::function::new_function;
    use llvm_native_core::instruction;
    use llvm_native_core::types::Type;

    fn build_simple_func(name: &str) -> ValueRef {
        let func = new_function(name, Type::void(), &[]);
        let entry = new_basic_block("entry");
        entry.borrow_mut().push_operand(instruction::ret_void());
        func.borrow_mut().push_operand(entry.clone());
        func
    }

    fn build_branch_func() -> ValueRef {
        let func = new_function("branch_fn", Type::void(), &[]);
        let entry = new_basic_block("entry");
        let if_true = new_basic_block("if_true");
        let if_false = new_basic_block("if_false");

        // Conditional branch (non-constant condition → both paths)
        let cond = new_basic_block("cond"); // using as dummy condition
        let br = instruction::br_cond(cond, if_true.clone(), if_false.clone());
        entry.borrow_mut().push_operand(br);

        if_true.borrow_mut().push_operand(instruction::ret_void());
        if_false.borrow_mut().push_operand(instruction::ret_void());

        func.borrow_mut().push_operand(entry.clone());
        func.borrow_mut().push_operand(if_true.clone());
        func.borrow_mut().push_operand(if_false.clone());
        func
    }

    // === LatticeValue Tests ===

    #[test]
    fn test_lattice_top_meet() {
        let top = LatticeValue::Top;
        let c42 = LatticeValue::Constant(42);
        let result = top.meet(&c42);
        assert_eq!(result.get_constant(), Some(42));
    }

    #[test]
    fn test_lattice_constant_meet_same() {
        let a = LatticeValue::Constant(10);
        let b = LatticeValue::Constant(10);
        let result = a.meet(&b);
        assert!(result.is_constant());
        assert_eq!(result.get_constant(), Some(10));
    }

    #[test]
    fn test_lattice_constant_meet_different() {
        let a = LatticeValue::Constant(10);
        let b = LatticeValue::Constant(20);
        let result = a.meet(&b);
        assert!(result.is_overdefined());
    }

    #[test]
    fn test_lattice_bottom_meet_anything() {
        let bottom = LatticeValue::Bottom;
        let c = LatticeValue::Constant(5);
        assert!(bottom.meet(&c).is_overdefined());
        assert!(c.meet(&bottom).is_overdefined());
        assert!(bottom.meet(&LatticeValue::Top).is_overdefined());
    }

    #[test]
    fn test_lattice_is_constant() {
        assert!(LatticeValue::Constant(42).is_constant());
        assert!(!LatticeValue::Top.is_constant());
        assert!(!LatticeValue::Bottom.is_constant());
    }

    // === SCCPSolver Tests ===

    #[test]
    fn test_sccp_solver_create() {
        let solver = SCCPSolver::new();
        assert_eq!(solver.constants_folded, 0);
        assert_eq!(solver.unreachable_blocks, 0);
    }

    #[test]
    fn test_sccp_initialize_simple() {
        let mut solver = SCCPSolver::new();
        let func = build_simple_func("init_test");
        solver.initialize(&func);

        // Entry block should be executable
        let f = func.borrow();
        let entry = f.operands[0].borrow();
        assert!(solver.executable_blocks.contains(&entry.name));
    }

    #[test]
    fn test_sccp_solve_simple() {
        let mut solver = SCCPSolver::new();
        let func = build_simple_func("solve_test");
        solver.solve(&func);

        // Should complete without error
        assert!(solver.constants_folded >= 0);
    }

    #[test]
    fn test_sccp_solve_branch_function() {
        let mut solver = SCCPSolver::new();
        let func = build_branch_func();
        solver.solve(&func);

        // Both branch targets should be executable (non-constant condition)
        let stats = solver.stats(&func);
        assert_eq!(stats.total_blocks, 3);
    }

    // === fold_binary_op Tests ===

    #[test]
    fn test_fold_add() {
        let result = SCCPSolver::fold_binary_op("add", 3, 4);
        assert_eq!(result.unwrap().get_constant(), Some(7));
    }

    #[test]
    fn test_fold_sub() {
        let result = SCCPSolver::fold_binary_op("sub", 10, 3);
        assert_eq!(result.unwrap().get_constant(), Some(7));
    }

    #[test]
    fn test_fold_mul() {
        let result = SCCPSolver::fold_binary_op("mul", 6, 7);
        assert_eq!(result.unwrap().get_constant(), Some(42));
    }

    #[test]
    fn test_fold_div() {
        let result = SCCPSolver::fold_binary_op("sdiv", 10, 2);
        assert_eq!(result.unwrap().get_constant(), Some(5));
    }

    #[test]
    fn test_fold_div_by_zero() {
        let result = SCCPSolver::fold_binary_op("sdiv", 10, 0);
        assert!(result.is_none());
    }

    #[test]
    fn test_fold_and() {
        let result = SCCPSolver::fold_binary_op("and", 0xFF, 0x0F);
        assert_eq!(result.unwrap().get_constant(), Some(0x0F));
    }

    #[test]
    fn test_fold_or() {
        let result = SCCPSolver::fold_binary_op("or", 0xF0, 0x0F);
        assert_eq!(result.unwrap().get_constant(), Some(0xFF));
    }

    #[test]
    fn test_fold_xor() {
        let result = SCCPSolver::fold_binary_op("xor", 255, 255);
        assert!(result.is_some());
        let val = result.unwrap();
        assert!(val.is_constant() || val.is_overdefined());
    }

    #[test]
    fn test_fold_shl() {
        let result = SCCPSolver::fold_binary_op("shl", 1, 4);
        assert_eq!(result.unwrap().get_constant(), Some(16));
    }

    // === run_sccp Tests ===

    #[test]
    fn test_run_sccp_simple() {
        let func = build_simple_func("sccp_simple");
        let stats = run_sccp(&func);
        assert_eq!(stats.total_blocks, 1);
        assert!(stats.constants_folded >= 0);
    }

    #[test]
    fn test_run_sccp_branch() {
        let func = build_branch_func();
        let stats = run_sccp(&func);
        assert_eq!(stats.total_blocks, 3);
    }

    #[test]
    fn test_run_sccp_on_module() {
        let mut m = llvm_native_core::module::Module::new("sccp_mod");
        m.add_function(build_simple_func("f1"));
        m.add_function(build_simple_func("f2"));

        let results = run_sccp_on_module(&m);
        assert_eq!(results.len(), 2);
    }

    // === SCCPStats Tests ===

    #[test]
    fn test_sccp_stats_default() {
        let stats = SCCPStats {
            constants_folded: 0,
            unreachable_blocks: 0,
            branches_folded: 0,
            total_blocks: 5,
        };
        assert_eq!(stats.total_blocks, 5);
    }

    #[test]
    fn test_sccp_stats_after_analysis() {
        let func = build_branch_func();
        let stats = run_sccp(&func);
        assert!(stats.total_blocks > 0);
    }

    // === Integration Tests ===

    #[test]
    fn test_sccp_does_not_crash_on_empty_function() {
        let func = new_function("empty", Type::void(), &[]);
        // Function with no blocks should not crash
        let mut solver = SCCPSolver::new();
        solver.solve(&func);
        assert!(solver.constants_folded >= 0);
    }

    #[test]
    fn test_lattice_meet_associative() {
        let a = LatticeValue::Constant(5);
        let b = LatticeValue::Top;
        let c = LatticeValue::Constant(5);

        let ab = a.meet(&b);
        let abc = ab.meet(&c);
        let bc = b.meet(&c);
        let a_bc = a.meet(&bc);

        assert_eq!(abc.get_constant(), a_bc.get_constant());
    }
}