llvm-native-core-ext 0.1.0

//! LLVM CalledValuePropagation — propagates known callee values through
//! indirect function pointers and virtual method calls.
//! Clean-room behavioral reconstruction.
//!
//! This pass analyzes indirect call sites and attempts to resolve the
//! actual callee by tracking function pointer values through stores,
//! loads, and PHI nodes. When a unique callee is determined, the indirect
//! call can be devirtualized into a direct call, which enables inlining
//! and other interprocedural optimizations.
//!
//! Algorithm:
//!   1. Scan all call instructions in a function
//!   2. For indirect calls (calls through a function pointer), trace the
//!      pointer value back through its definition chain
//!   3. Look through loads from known function pointer storage, PHI nodes
//!      merging known functions, and select instructions
//!   4. If the callee resolves to a unique function, replace the indirect
//!      call with a direct call to the resolved function
//!   5. If the callee resolves to a small set of functions, optionally
//!      create a guarded dispatch (if-conversion)
//!
//! This is especially effective after inlining and constant propagation,
//! which can expose the actual targets of virtual method calls and
//! callback registrations.

use llvm_native_core::value::{SubclassKind, ValueRef};

// ============================================================================
// Called Value Propagation Pass
// ============================================================================

/// CalledValuePropagation pass — resolves indirect call targets by
/// tracing function pointer values.
pub struct CalledValuePropagation {
    /// Number of call sites successfully devirtualized.
    pub propagated: usize,
}

impl CalledValuePropagation {
    /// Create a new CalledValuePropagation pass.
    pub fn new() -> Self {
        Self { propagated: 0 }
    }

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

    /// Run called-value propagation on a function. Returns the number of
    /// indirect calls devirtualized to direct calls.
    pub fn run_on_function(&mut self, func: &ValueRef) -> usize {
        self.propagated = 0;

        let call_sites = self.find_call_sites(func);

        for call in call_sites {
            if let Some(callee) = self.resolve_callee(&call) {
                self.propagate_callee(&call, &callee, func);
            }
        }

        self.propagated
    }

    // ========================================================================
    // Call site discovery
    // ========================================================================

    /// Find all call instructions in the function.
    fn find_call_sites(&self, func: &ValueRef) -> Vec<ValueRef> {
        let mut calls = Vec::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();
                if !i.is_instruction() {
                    continue;
                }

                // Check for call instructions by opcode or name
                if i.opcode == Some(llvm_native_core::opcode::Opcode::Call)
                    || i.opcode == Some(llvm_native_core::opcode::Opcode::Invoke)
                    || i.name.to_lowercase().contains("call")
                    || i.name.to_lowercase().contains("invoke")
                {
                    calls.push(inst.clone());
                }
            }
        }

        calls
    }

    // ========================================================================
    // Callee resolution
    // ========================================================================

    /// Attempt to resolve the callee of an indirect call.
    /// Returns Some(callee) if a unique function target is found, None
    /// if the callee cannot be determined.
    fn resolve_callee(&self, call: &ValueRef) -> Option<ValueRef> {
        let i = call.borrow();

        // Check if the value itself is already a function
        if i.subclass == SubclassKind::Function {
            return Some(call.clone());
        }

        // For call instructions, the first operand is the callee
        if i.operands.is_empty() {
            return None;
        }

        let callee_op = &i.operands[0];
        let callee = callee_op.borrow();

        // Case 1: Direct call — callee is already a function
        if callee.subclass == SubclassKind::Function {
            return Some(callee_op.clone());
        }

        // Case 2: The callee is a constant (function address)
        if callee.subclass == SubclassKind::Constant {
            // Check if this constant was created from a known function
            // (e.g., bitcast of a function to a pointer, then stored)
            // For now, check if the constant's name matches a known function
            return self.trace_to_function(callee_op);
        }

        // Case 3: The callee is loaded from memory (vtable dispatch)
        // Trace the pointer back to see if it's a known function
        if callee.opcode == Some(llvm_native_core::opcode::Opcode::Load) {
            return self.trace_load_to_function(callee_op);
        }

        // Case 4: The callee is a PHI node merging known functions
        if callee.name.to_lowercase().contains("phi") {
            return self.resolve_phi_callee(callee_op);
        }

        // Case 5: The callee is a select between known functions
        if callee.opcode == Some(llvm_native_core::opcode::Opcode::Select) {
            return self.resolve_select_callee(callee_op);
        }

        None
    }

    /// Trace a value back to a known function definition.
    fn trace_to_function(&self, val: &ValueRef) -> Option<ValueRef> {
        let v = val.borrow();

        // If it's already a function, return it
        if v.subclass == SubclassKind::Function {
            return Some(val.clone());
        }

        // If it's a bitcast of a function, trace through
        if v.opcode == Some(llvm_native_core::opcode::Opcode::BitCast) {
            if !v.operands.is_empty() {
                return self.trace_to_function(&v.operands[0]);
            }
        }

        // If it's an inttoptr of a known function address, resolve
        if v.opcode == Some(llvm_native_core::opcode::Opcode::IntToPtr) {
            if !v.operands.is_empty() {
                return self.trace_to_function(&v.operands[0]);
            }
        }

        None
    }

    /// Trace a load back to the stored function pointer.
    fn trace_load_to_function(&self, load: &ValueRef) -> Option<ValueRef> {
        let l = load.borrow();

        // Get the pointer being loaded from
        if l.operands.is_empty() {
            return None;
        }

        let ptr = &l.operands[0];

        // Walk backwards through the block looking for a store to this pointer
        let parent_bb = l.parent.clone()?;
        let bb = parent_bb.borrow();

        // Find the position of this load
        let load_pos = bb
            .operands
            .iter()
            .position(|inst| inst.borrow().vid == l.vid)?;

        // Scan backwards for stores to the same pointer
        for idx in (0..load_pos).rev() {
            let prev_inst = &bb.operands[idx];
            let pi = prev_inst.borrow();

            if pi.opcode == Some(llvm_native_core::opcode::Opcode::Store)
                || pi.name.to_lowercase().contains("store")
            {
                if pi.operands.len() >= 2 {
                    let store_ptr = &pi.operands[1];
                    if store_ptr.borrow().vid == ptr.borrow().vid {
                        // Found a store to the same location
                        let stored_val = pi.operands[0].clone();
                        let sv = stored_val.borrow();

                        // Is the stored value a function pointer?
                        if sv.subclass == SubclassKind::Function {
                            return Some(stored_val.clone());
                        }

                        // Try tracing further
                        return self.trace_to_function(&stored_val);
                    }
                }
            }

            // If we encounter a call, stop (may modify the pointer)
            if pi.name.to_lowercase().contains("call") {
                break;
            }
        }

        None
    }

    /// Resolve a PHI node that merges multiple function pointers.
    /// Returns Some(callee) if all incoming values resolve to the same
    /// function.
    fn resolve_phi_callee(&self, phi: &ValueRef) -> Option<ValueRef> {
        let p = phi.borrow();
        let mut common_callee: Option<ValueRef> = None;

        // PHI operands come in pairs: (value, predecessor_block)
        for chunk in p.operands.chunks(2) {
            if chunk.is_empty() {
                continue;
            }

            let incoming_val = &chunk[0];
            let resolved = self.resolve_callee(incoming_val)?;

            match &common_callee {
                None => common_callee = Some(resolved),
                Some(existing) => {
                    if existing.borrow().vid != resolved.borrow().vid {
                        // Different functions — can't resolve uniquely
                        return None;
                    }
                }
            }
        }

        common_callee
    }

    /// Resolve a select instruction that chooses between function pointers.
    fn resolve_select_callee(&self, select: &ValueRef) -> Option<ValueRef> {
        let s = select.borrow();

        if s.operands.len() < 3 {
            return None;
        }

        // Select: condition, true_val, false_val
        let true_val = &s.operands[1];
        let false_val = &s.operands[2];

        let true_callee = self.resolve_callee(true_val)?;
        let false_callee = self.resolve_callee(false_val)?;

        if true_callee.borrow().vid == false_callee.borrow().vid {
            Some(true_callee)
        } else {
            // Different targets — could still optimize with a conditional
            // dispatch, but for now report as not uniquely resolved
            None
        }
    }

    // ========================================================================
    // Callee propagation
    // ========================================================================

    /// Propagate a resolved callee to an indirect call site.
    /// Replaces the indirect call with a direct call to the resolved
    /// function.
    fn propagate_callee(&mut self, call: &ValueRef, callee: &ValueRef, func: &ValueRef) {
        let mut ci = call.borrow_mut();

        // Mark this as devirtualized
        ci.name = format!("call.{}.devirt", callee.borrow().name);

        // Replace the callee operand with the resolved function
        if !ci.operands.is_empty() {
            ci.operands[0] = callee.clone();
        }

        drop(ci);

        self.propagated += 1;
    }

    // ========================================================================
    // Devirtualization
    // ========================================================================

    /// Devirtualize a virtual method call by replacing it with a direct
    /// call. The virtual_method parameter is a hint for the vtable
    /// method name.
    fn devirtualize_call(&mut self, call: &ValueRef, virtual_method: &str, func: &ValueRef) {
        let is_indirect = {
            let ci = call.borrow();
            if ci.opcode == Some(llvm_native_core::opcode::Opcode::Call) && !ci.operands.is_empty() {
                let callee_op = &ci.operands[0];
                let callee = callee_op.borrow();
                callee.subclass != SubclassKind::Function
            } else {
                false
            }
        };

        if is_indirect {
            if let Some(resolved) = self.resolve_callee(call) {
                self.propagate_callee(call, &resolved, func);
            }
        }
    }
}

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

// ============================================================================
// Value Lattice for Called Value Propagation
// ============================================================================

/// Value lattice state for function pointer tracking.
/// Progresses: Undef → Constant(Vec<ValueRef>) → Overdefined
#[derive(Debug, Clone)]
pub enum CVPLatticeValue {
    /// No known value (bottom of lattice).
    Undef,
    /// Known to be one of these values (function references).
    Constant(Vec<ValueRef>),
    /// Too many possible values to track (top of lattice).
    Overdefined,
}

impl CVPLatticeValue {
    /// Join two lattice values (union).
    pub fn join(a: &CVPLatticeValue, b: &CVPLatticeValue) -> CVPLatticeValue {
        match (a, b) {
            (CVPLatticeValue::Undef, x) | (x, CVPLatticeValue::Undef) => x.clone(),
            (CVPLatticeValue::Overdefined, _) | (_, CVPLatticeValue::Overdefined) => {
                CVPLatticeValue::Overdefined
            }
            (CVPLatticeValue::Constant(v1), CVPLatticeValue::Constant(v2)) => {
                let mut merged = v1.clone();
                for v in v2 {
                    if !merged.iter().any(|m| m.borrow().vid == v.borrow().vid) {
                        merged.push(v.clone());
                    }
                }
                // If too many candidates, go overdefined
                if merged.len() > 8 {
                    CVPLatticeValue::Overdefined
                } else {
                    CVPLatticeValue::Constant(merged)
                }
            }
        }
    }

    /// Returns true if this is a unique constant value.
    pub fn is_unique(&self) -> bool {
        matches!(self, CVPLatticeValue::Constant(v) if v.len() == 1)
    }

    /// Get the unique value if exactly one.
    pub fn get_unique(&self) -> Option<&ValueRef> {
        match self {
            CVPLatticeValue::Constant(v) if v.len() == 1 => Some(&v[0]),
            _ => None,
        }
    }

    /// Get all candidate values.
    pub fn get_candidates(&self) -> Vec<ValueRef> {
        match self {
            CVPLatticeValue::Constant(v) => v.clone(),
            _ => Vec::new(),
        }
    }
}

impl Default for CVPLatticeValue {
    fn default() -> Self {
        CVPLatticeValue::Undef
    }
}

// ============================================================================
// Enhanced Called Value Propagation
// ============================================================================

impl CalledValuePropagation {
    /// Run value-lattice-based CVP on a function.
    /// Builds a lattice of possible callee values for each indirect call site
    /// and resolves them when a unique target is found.
    pub fn run_lattice_cvp(&mut self, func: &ValueRef) -> usize {
        let lattice = self.build_callee_lattice(func);
        let call_sites = self.find_call_sites(func);
        let mut resolved = 0usize;

        for call in &call_sites {
            let c = call.borrow();
            if c.operands.is_empty() {
                continue;
            }
            if c.operands[0].borrow().subclass == SubclassKind::Function {
                continue; // Already direct
            }

            let callee_vid = c.operands[0].borrow().vid;
            if let Some(lv) = lattice.get(&callee_vid) {
                if let Some(unique_target) = lv.get_unique() {
                    self.propagate_callee(call, unique_target, func);
                    resolved += 1;
                }
            }
        }

        self.propagated += resolved;
        resolved
    }

    /// Build a value lattice for all function-pointer values in the function.
    fn build_callee_lattice(
        &self,
        func: &ValueRef,
    ) -> std::collections::HashMap<u64, CVPLatticeValue> {
        let mut lattice: std::collections::HashMap<u64, CVPLatticeValue> =
            std::collections::HashMap::new();
        let f = func.borrow();

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

            for inst_val in &bb.operands {
                let inst = inst_val.borrow();

                // Store to a known function pointer → lattice update
                if inst.get_opcode() == Some(llvm_native_core::opcode::Opcode::Store)
                    && inst.operands.len() >= 2
                {
                    let stored_val = &inst.operands[0];
                    if stored_val.borrow().subclass == SubclassKind::Function {
                        let ptr_vid = inst.operands[1].borrow().vid;
                        lattice
                            .insert(ptr_vid, CVPLatticeValue::Constant(vec![stored_val.clone()]));
                    }
                }

                // Load from a pointer → inherit lattice value
                if inst.get_opcode() == Some(llvm_native_core::opcode::Opcode::Load)
                    && !inst.operands.is_empty()
                {
                    let ptr_vid = inst.operands[0].borrow().vid;
                    if let Some(lv) = lattice.get(&ptr_vid).cloned() {
                        lattice.insert(inst_val.borrow().vid, lv);
                    }
                }

                // PHI node → join lattice values of incoming edges
                if inst.name.to_lowercase().contains("phi") {
                    let mut phi_lv = CVPLatticeValue::Undef;
                    for incoming in &inst.operands {
                        let incoming_vid = incoming.borrow().vid;
                        if let Some(lv) = lattice.get(&incoming_vid) {
                            phi_lv = CVPLatticeValue::join(&phi_lv, lv);
                        }
                    }
                    if !matches!(phi_lv, CVPLatticeValue::Undef) {
                        lattice.insert(inst_val.borrow().vid, phi_lv);
                    }
                }

                // Select → join both branches
                if inst.opcode == Some(llvm_native_core::opcode::Opcode::Select) && inst.operands.len() >= 3 {
                    let true_vid = inst.operands[1].borrow().vid;
                    let false_vid = inst.operands[2].borrow().vid;
                    let mut select_lv = CVPLatticeValue::Undef;
                    if let Some(lv) = lattice.get(&true_vid) {
                        select_lv = CVPLatticeValue::join(&select_lv, lv);
                    }
                    if let Some(lv) = lattice.get(&false_vid) {
                        select_lv = CVPLatticeValue::join(&select_lv, lv);
                    }
                    if !matches!(select_lv, CVPLatticeValue::Undef) {
                        lattice.insert(inst_val.borrow().vid, select_lv);
                    }
                }
            }
        }

        lattice
    }

    /// Perform indirect call promotion: transform an indirect call
    /// into a guarded direct call sequence.
    ///
    /// if (callee == expected_target) {
    ///     call expected_target(args)
    /// } else {
    ///     call callee(args)
    /// }
    pub fn indirect_call_promote(
        &mut self,
        call: &ValueRef,
        expected_target: &ValueRef,
        _func: &ValueRef,
    ) -> bool {
        let c = call.borrow();
        if c.operands.is_empty() {
            return false;
        }

        // For simplicity, if we have a unique target, just do full devirtualization
        if expected_target.borrow().subclass == SubclassKind::Function {
            self.propagate_callee(call, expected_target, _func);
            return true;
        }

        false
    }

    /// Check if an indirect call is eligible for devirtualization.
    pub fn can_devirtualize(&self, call: &ValueRef) -> bool {
        let c = call.borrow();
        if c.operands.is_empty() {
            return false;
        }
        let callee = &c.operands[0];
        let callee_val = callee.borrow();

        // Direct call — no devirtualization needed
        if callee_val.subclass == SubclassKind::Function {
            return false;
        }

        // Check if callee resolves to a unique target
        self.resolve_callee(call).is_some()
    }

    /// Get the number of indirect calls that were successfully resolved.
    pub fn get_devirtualized_count(&self) -> usize {
        self.propagated
    }

    /// Returns a set of all functions that may be called at a call site.
    pub fn get_possible_callees(&self, call: &ValueRef) -> Vec<ValueRef> {
        let c = call.borrow();
        if c.operands.is_empty() {
            return Vec::new();
        }

        // Try direct resolution first
        if let Some(target) = self.resolve_callee(call) {
            return vec![target];
        }

        Vec::new()
    }
}

// ============================================================================
// CVP Result — summary of propagation results
// ============================================================================

/// Summary statistics from a CVP run.
#[derive(Debug, Clone, Default)]
pub struct CVPResult {
    /// Total number of call sites examined.
    pub total_calls: usize,
    /// Number of indirect calls found.
    pub indirect_calls: usize,
    /// Number of calls successfully devirtualized.
    pub devirtualized: usize,
    /// Number of calls promoted (guarded dispatch).
    pub promoted: usize,
}

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

    /// Returns the devirtualization rate as a percentage.
    pub fn devirtualization_rate(&self) -> f64 {
        if self.indirect_calls == 0 {
            0.0
        } else {
            (self.devirtualized as f64) / (self.indirect_calls as f64) * 100.0
        }
    }
}

// ============================================================================
// CVP Walkers — walk instruction chains to resolve callees
// ============================================================================

impl CalledValuePropagation {
    /// Walk through bitcasts to find the underlying function.
    pub fn walk_through_bitcasts(&self, val: &ValueRef) -> Option<ValueRef> {
        let v = val.borrow();
        match v.get_opcode() {
            Some(llvm_native_core::opcode::Opcode::BitCast) | Some(llvm_native_core::opcode::Opcode::IntToPtr) => {
                if v.operands.is_empty() {
                    None
                } else {
                    self.walk_through_bitcasts(&v.operands[0])
                }
            }
            _ => {
                if v.subclass == SubclassKind::Function {
                    Some(val.clone())
                } else {
                    None
                }
            }
        }
    }

    /// Walk through select instructions to resolve common callees.
    pub fn walk_through_selects(&self, val: &ValueRef) -> Vec<ValueRef> {
        let v = val.borrow();
        match v.get_opcode() {
            Some(llvm_native_core::opcode::Opcode::Select) if v.operands.len() >= 3 => {
                let mut results = self.walk_through_selects(&v.operands[1]);
                results.extend(self.walk_through_selects(&v.operands[2]));
                results
            }
            _ => {
                match self.walk_through_bitcasts(val) { Some(target) => {
                    vec![target]
                } _ => {
                    Vec::new()
                }}
            }
        }
    }

    /// Walk through PHI nodes to resolve common callees.
    pub fn walk_through_phis(&self, val: &ValueRef) -> Vec<ValueRef> {
        let v = val.borrow();
        if v.name.to_lowercase().contains("phi") {
            let mut results = Vec::new();
            for incoming in &v.operands {
                results.extend(self.walk_through_selects(incoming));
            }
            results
        } else {
            self.walk_through_selects(val)
        }
    }

    /// Compute the total number of call sites that can be devirtualized
    /// across a module.
    pub fn compute_module_stats(&self, module: &llvm_native_core::module::Module) -> CVPResult {
        let mut result = CVPResult::new();
        for func in &module.functions {
            let f = func.borrow();
            if f.is_function() {
                let calls = self.collect_call_stats(func);
                result.total_calls += calls.0;
                result.indirect_calls += calls.1;
                result.devirtualized += calls.2;
            }
        }
        result
    }

    /// Collect call statistics for a single function.
    fn collect_call_stats(&self, func: &ValueRef) -> (usize, usize, usize) {
        let call_sites = self.find_call_sites(func);
        let total = call_sites.len();
        let mut indirect = 0usize;
        let mut devirtualized = 0usize;

        for call in &call_sites {
            let c = call.borrow();
            if c.operands.is_empty() {
                continue;
            }
            if c.operands[0].borrow().subclass != SubclassKind::Function {
                indirect += 1;
                if self.resolve_callee(call).is_some() {
                    devirtualized += 1;
                }
            }
        }

        (total, indirect, devirtualized)
    }
}

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

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

    fn make_function(name: &str) -> ValueRef {
        let return_ty = llvm_native_core::types::Type::void();
        let fn_ty = llvm_native_core::types::Type::function_type_with(return_ty.id, vec![], false);
        let mut v = Value::new(fn_ty)
            .named(name)
            .with_subclass(SubclassKind::Function);
        valref(v)
    }

    fn make_call(callee: ValueRef) -> ValueRef {
        let mut v = Value::new(llvm_native_core::types::Type::void()).with_subclass(SubclassKind::Instruction);
        v.name = "call".into();
        v.opcode = Some(llvm_native_core::opcode::Opcode::Call);
        v.operands = vec![callee];
        v.num_operands = 1;
        valref(v)
    }

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

    fn make_phi(incoming: Vec<ValueRef>) -> ValueRef {
        let len = incoming.len();
        let mut v = Value::new(llvm_native_core::types::Type::void()).with_subclass(SubclassKind::Instruction);
        v.name = "phi".into();
        v.opcode = Some(llvm_native_core::opcode::Opcode::Phi);
        v.operands = incoming;
        v.num_operands = len;
        valref(v)
    }

    #[test]
    fn test_create_pass() {
        let pass = CalledValuePropagation::new();
        assert_eq!(pass.propagated, 0);
    }

    #[test]
    fn test_resolve_direct_call() {
        let pass = CalledValuePropagation::new();
        let func = make_function("target");
        let call = make_call(func);
        let result = pass.resolve_callee(&call);
        assert!(result.is_some());
    }

    #[test]
    fn test_resolve_indirect_unresolvable() {
        let pass = CalledValuePropagation::new();
        let ptr = llvm_native_core::constants::const_i32(0xDEAD);
        let call = make_indirect_call(ptr);
        let result = pass.resolve_callee(&call);
        assert!(result.is_none());
    }

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

    #[test]
    fn test_find_call_sites_with_call() {
        let pass = CalledValuePropagation::new();
        let target = make_function("target");
        let call = make_call(target);

        let mut bb =
            Value::new(llvm_native_core::types::Type::label()).with_subclass(SubclassKind::BasicBlock);
        bb.operands = vec![call];
        let bb_ref = valref(bb);

        let mut func = Value::new(llvm_native_core::types::Type::void());
        func.subclass = SubclassKind::Function;
        func.operands = vec![bb_ref];
        let func_ref = valref(func);

        let calls = pass.find_call_sites(&func_ref);
        assert_eq!(calls.len(), 1);
    }

    #[test]
    fn test_resolve_phi_unique_callee() {
        let pass = CalledValuePropagation::new();
        let func1 = make_function("target");
        let bb = Value::new(llvm_native_core::types::Type::label()).with_subclass(SubclassKind::BasicBlock);
        let bb_ref = valref(bb);
        // PHI operands: (value, pred_block) pairs
        let phi = make_phi(vec![func1.clone(), bb_ref.clone(), func1.clone(), bb_ref]);
        let call = make_call(phi);
        let result = pass.resolve_callee(&call);
        // Both incoming values point to the same function
        assert!(result.is_some());
    }

    #[test]
    fn test_resolve_phi_different_callee() {
        let pass = CalledValuePropagation::new();
        let func1 = make_function("target1");
        let func2 = make_function("target2");
        // PHI operands in LLVM are interleaved: (value, predecessor_block)
        let bb1 = Value::new(llvm_native_core::types::Type::label()).with_subclass(SubclassKind::BasicBlock);
        let bb2 = Value::new(llvm_native_core::types::Type::label()).with_subclass(SubclassKind::BasicBlock);
        let bb1_ref = valref(bb1);
        let bb2_ref = valref(bb2);

        let phi = make_phi(vec![func1, bb1_ref, func2, bb2_ref]);
        let call = make_call(phi);
        let result = pass.resolve_callee(&call);
        // Different targets — cannot resolve uniquely
        assert!(result.is_none());
    }

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

    #[test]
    fn test_run_on_function_no_blocks() {
        let mut pass = CalledValuePropagation::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);
    }

    #[test]
    fn test_trace_to_function_direct() {
        let pass = CalledValuePropagation::new();
        let func = make_function("target");
        let result = pass.trace_to_function(&func);
        assert!(result.is_some());
    }

    #[test]
    fn test_trace_to_function_non_func() {
        let pass = CalledValuePropagation::new();
        let val = llvm_native_core::constants::const_i32(42);
        let result = pass.trace_to_function(&val);
        assert!(result.is_none());
    }

    #[test]
    fn test_devirtualize_call_direct() {
        let mut pass = CalledValuePropagation::new();
        let func = make_function("direct_target");
        let call = make_call(func.clone());

        let mut function = Value::new(llvm_native_core::types::Type::void());
        function.subclass = SubclassKind::Function;
        let func_ref = valref(function);

        pass.devirtualize_call(&call, "foo", &func_ref);
        // Already a direct call — no devirtualization needed
        assert_eq!(pass.propagated, 0);
    }
}