llvm-native-core-ext 0.1.0

//! LLVM Memory Dependence Analysis — determines dependencies between memory operations.
//! Phase 9 — LLVM.MemDep.1 Court.
//!
//! Clean-room behavioral reconstruction from compiler optimization literature
//! (Memory Dependence Analysis, Bodik et al. 1998; Memory SSA), the LLVM
//! Language Reference, and observable optimization behavior. Zero LLVM source
//! code consultation.
//!
//! Memory Dependence Analysis answers: for a given memory operation (load/store),
//! what is the nearest preceding instruction that either defines or clobbers
//! the memory location? This is fundamental to:
//! - Redundant load elimination (load→load forwarding)
//! - Dead store elimination (store→store overwrite)
//! - Load/store scheduling
//! - Code motion across memory operations
//!
//! The analysis works per-function, caching results for efficiency. It
//! distinguishes between:
//! - Local dependencies: within the same basic block
//! - Non-local dependencies: across basic blocks (requires block scanning)
//! - Clobbering: any call or unknown store that invalidates memory state

use llvm_native_core::alias_analysis::MemoryLocation;
use llvm_native_core::opcode::Opcode;
use llvm_native_core::value::{SubclassKind, ValueRef};
use std::collections::{HashMap, HashSet};
use std::rc::Rc;

// ============================================================================
// MemDepResult — the outcome of a memory dependence query
// ============================================================================

/// The result of a memory dependence query.
///
/// @llvm_behavior: LLVM's MemDepResult categorizes dependencies:
/// - Def(inst): the query depends on a specific definition.
/// - Clobber: some unknown write invalidates (clobbers) the location.
/// - NonLocal: dependency is across basic blocks.
/// - NonFuncLocal: dependency reaches outside the current function.
/// - Unknown: analysis cannot determine the dependency.
#[derive(Debug, Clone)]
pub enum MemDepResult {
    /// Depends on a specific definition instruction.
    Def(ValueRef),
    /// Clobbered by some unknown write (e.g., call with unknown side effects).
    Clobber,
    /// Non-local dependency; needs per-block analysis.
    NonLocal,
    /// Depends on non-function-local state (e.g., global variable, argument).
    NonFuncLocal,
    /// Cannot determine the dependency.
    Unknown,
}

impl MemDepResult {
    /// Returns true if the result is a specific definition.
    pub fn is_def(&self) -> bool {
        matches!(self, MemDepResult::Def(_))
    }

    /// Returns true if the result is Clobber.
    pub fn is_clobber(&self) -> bool {
        matches!(self, MemDepResult::Clobber)
    }

    /// Returns the defining instruction if this is a Def, else None.
    pub fn get_def(&self) -> Option<&ValueRef> {
        match self {
            MemDepResult::Def(v) => Some(v),
            _ => None,
        }
    }
}

impl PartialEq for MemDepResult {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (MemDepResult::Def(a), MemDepResult::Def(b)) => Rc::ptr_eq(a, b),
            (MemDepResult::Clobber, MemDepResult::Clobber) => true,
            (MemDepResult::NonLocal, MemDepResult::NonLocal) => true,
            (MemDepResult::NonFuncLocal, MemDepResult::NonFuncLocal) => true,
            (MemDepResult::Unknown, MemDepResult::Unknown) => true,
            _ => false,
        }
    }
}

impl std::fmt::Display for MemDepResult {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            MemDepResult::Def(v) => {
                let name = v.borrow().name.clone();
                write!(f, "Def({})", name)
            }
            MemDepResult::Clobber => write!(f, "Clobber"),
            MemDepResult::NonLocal => write!(f, "NonLocal"),
            MemDepResult::NonFuncLocal => write!(f, "NonFuncLocal"),
            MemDepResult::Unknown => write!(f, "Unknown"),
        }
    }
}

// ============================================================================
// MemoryDependenceAnalysis — per-function memory dependence tracking
// ============================================================================

/// Memory dependence analysis for a single function.
///
/// @llvm_behavior: LLVM's MemoryDependenceAnalysis caches results by
/// instruction (using the instruction's vid). It provides:
/// - get_dependency(): main entry point, returns the nearest memory def/clobber
/// - get_pointer_dependency(): locale-specific version for known MemoryLocations
/// - get_simple_dependency(): fast intra-block lookup
/// - Cache management for incremental updates
pub struct MemoryDependenceAnalysis {
    /// The function being analyzed.
    pub func: ValueRef,
    /// Cache: instruction vid → dependency result.
    cache: HashMap<usize, MemDepResult>,
    /// Cache: is instruction dirty?
    dirty: HashSet<usize>,
}

impl MemoryDependenceAnalysis {
    /// Create a new memory dependence analysis for the given function.
    pub fn new(func: &ValueRef) -> Self {
        Self {
            func: Rc::clone(func),
            cache: HashMap::new(),
            dirty: HashSet::new(),
        }
    }

    // ========================================================================
    // Main entry point: get_dependency
    // ========================================================================

    /// Get the memory dependence for a query instruction.
    pub fn get_dependency(&mut self, query: &ValueRef) -> MemDepResult {
        let vid = query.borrow().vid as usize;

        // Check cache first
        if !self.dirty.contains(&vid) {
            if let Some(cached) = self.cache.get(&vid) {
                return cached.clone();
            }
        }

        let loc = match get_mem_location(query) {
            Some(l) => l,
            None => {
                let result = MemDepResult::Unknown;
                self.cache.insert(vid, result.clone());
                self.dirty.remove(&vid);
                return result;
            }
        };

        let bb = match find_parent_block(&self.func, query) {
            Some(b) => b,
            None => {
                let result = MemDepResult::Unknown;
                self.cache.insert(vid, result.clone());
                self.dirty.remove(&vid);
                return result;
            }
        };

        let result = self.search_block_backwards(query, &bb, &loc);

        let result = match result {
            MemDepResult::Unknown => self.get_nonlocal_dependency(query, &bb, &loc),
            r => r,
        };

        self.cache.insert(vid, result.clone());
        self.dirty.remove(&vid);
        result
    }

    // ========================================================================
    // Pointer dependency (non-local)
    // ========================================================================

    /// Get the pointer dependency for a specific memory location.
    pub fn get_pointer_dependency(
        &self,
        loc: &MemoryLocation,
        is_load: bool,
        scan_blocks: &[ValueRef],
    ) -> MemDepResult {
        for bb in scan_blocks.iter().rev() {
            let block = bb.borrow();
            for inst in block.operands.iter().rev() {
                let i = inst.borrow();
                if let Some(opcode) = i.get_opcode() {
                    match opcode {
                        Opcode::Store => {
                            if inst_may_access_same_location(inst, loc) {
                                return MemDepResult::Def(Rc::clone(inst));
                            }
                            if is_load && may_alias_store_to_loc(inst, loc) {
                                return MemDepResult::Clobber;
                            }
                        }
                        Opcode::Load => {
                            if is_load && inst_may_access_same_location(inst, loc) {
                                return MemDepResult::Def(Rc::clone(inst));
                            }
                        }
                        Opcode::Call => {
                            if may_call_clobber_location(inst, loc) {
                                return MemDepResult::Clobber;
                            }
                        }
                        _ => {}
                    }
                }
            }
        }

        MemDepResult::NonFuncLocal
    }

    // ========================================================================
    // Simple dependency (intra-block)
    // ========================================================================

    /// Get a simple dependency: walk backward through a single basic block.
    pub fn get_simple_dependency(&self, query: &ValueRef, bb: &ValueRef) -> MemDepResult {
        let loc = match get_mem_location(query) {
            Some(l) => l,
            None => return MemDepResult::Unknown,
        };

        self.search_block_backwards(query, bb, &loc)
    }

    // ========================================================================
    // Static checks
    // ========================================================================

    /// Check if an instruction may read or write memory.
    pub fn may_access_memory(inst: &ValueRef) -> bool {
        let i = inst.borrow();
        if let Some(opcode) = i.get_opcode() {
            match opcode {
                Opcode::Load
                | Opcode::Store
                | Opcode::Call
                | Opcode::Invoke
                | Opcode::AtomicRMW
                | Opcode::CmpXchg
                | Opcode::Fence => true,
                Opcode::Alloca => false,
                _ => false,
            }
        } else {
            false
        }
    }

    /// Check if an instruction is a store instruction.
    pub fn is_store(inst: &ValueRef) -> bool {
        inst.borrow().get_opcode() == Some(Opcode::Store)
    }

    /// Check if an instruction is a load instruction.
    pub fn is_load(inst: &ValueRef) -> bool {
        inst.borrow().get_opcode() == Some(Opcode::Load)
    }

    // ========================================================================
    // Cache management
    // ========================================================================

    /// Clear the entire analysis cache.
    pub fn clear_cache(&mut self) {
        self.cache.clear();
        self.dirty.clear();
    }

    /// Invalidate cached results for a specific instruction.
    pub fn invalidate(&mut self, inst: &ValueRef) {
        let vid = inst.borrow().vid as usize;
        self.cache.remove(&vid);
        self.dirty.insert(vid);
    }

    /// Mark all results as dirty (forces recomputation).
    pub fn invalidate_all(&mut self) {
        self.dirty.clear();
        for key in self.cache.keys() {
            self.dirty.insert(*key);
        }
    }

    // ========================================================================
    // Verification
    // ========================================================================

    /// Verify that the analysis is internally consistent.
    pub fn verify(&self) -> Result<(), String> {
        for (&query_vid, result) in &self.cache {
            if let MemDepResult::Def(def) = result {
                if def.borrow().vid as usize == query_vid {
                    return Err(format!("Instruction {} depends on itself", query_vid));
                }

                if !self.value_in_function(def) {
                    return Err(format!(
                        "Def {} for query {} is not in the analyzed function",
                        def.borrow().name,
                        query_vid
                    ));
                }
            }
        }

        Ok(())
    }

    // ========================================================================
    // Internal helpers
    // ========================================================================

    fn search_block_backwards(
        &self,
        query: &ValueRef,
        bb: &ValueRef,
        loc: &MemoryLocation,
    ) -> MemDepResult {
        let block = bb.borrow();
        let query_vid = query.borrow().vid;
        let is_load_query = Self::is_load(query);

        let mut found_query = false;
        for inst in block.operands.iter().rev() {
            let inst_vid = inst.borrow().vid;

            if !found_query {
                if inst_vid == query_vid {
                    found_query = true;
                }
                continue;
            }

            let i = inst.borrow();
            if let Some(opcode) = i.get_opcode() {
                match opcode {
                    Opcode::Store => {
                        if inst_may_access_same_location(inst, loc) {
                            return MemDepResult::Def(Rc::clone(inst));
                        }
                    }
                    Opcode::Load => {
                        if is_load_query && inst_may_access_same_location(inst, loc) {
                            return MemDepResult::Def(Rc::clone(inst));
                        }
                    }
                    Opcode::Call => {
                        if may_call_clobber_location(inst, loc) {
                            return MemDepResult::Clobber;
                        }
                    }
                    Opcode::AtomicRMW | Opcode::CmpXchg => {
                        return MemDepResult::Clobber;
                    }
                    _ => {}
                }
            }
        }

        MemDepResult::Unknown
    }

    fn get_nonlocal_dependency(
        &self,
        query: &ValueRef,
        bb: &ValueRef,
        loc: &MemoryLocation,
    ) -> MemDepResult {
        let is_load = Self::is_load(query);

        // Collect predecessor blocks via the BasicBlock struct
        let predecessors: Vec<ValueRef> = get_predecessors_of_block(bb);

        if predecessors.is_empty() {
            return MemDepResult::NonFuncLocal;
        }

        let mut found_def = false;
        let mut def_inst: Option<ValueRef> = None;

        for pred in &predecessors {
            let pred_block = pred.borrow();
            for inst in pred_block.operands.iter().rev() {
                let i = inst.borrow();
                if let Some(opcode) = i.get_opcode() {
                    match opcode {
                        Opcode::Store => {
                            if inst_may_access_same_location(inst, loc) {
                                if found_def {
                                    return MemDepResult::NonLocal;
                                }
                                found_def = true;
                                def_inst = Some(Rc::clone(inst));
                                break;
                            }
                        }
                        Opcode::Load => {
                            if is_load && inst_may_access_same_location(inst, loc) {
                                if found_def {
                                    return MemDepResult::NonLocal;
                                }
                                found_def = true;
                                def_inst = Some(Rc::clone(inst));
                                break;
                            }
                        }
                        Opcode::Call => {
                            if may_call_clobber_location(inst, loc) {
                                return MemDepResult::Clobber;
                            }
                        }
                        _ => {}
                    }
                }
            }
        }

        if let Some(def) = def_inst {
            MemDepResult::Def(def)
        } else {
            MemDepResult::NonLocal
        }
    }

    fn value_in_function(&self, val: &ValueRef) -> bool {
        let func = self.func.borrow();
        for op in &func.operands {
            let bb = op.borrow();
            for inst in &bb.operands {
                if Rc::ptr_eq(inst, val) {
                    return true;
                }
            }
        }
        false
    }
}

// ============================================================================
// Convenience functions
// ============================================================================

/// Get the memory dependence for a load instruction.
pub fn get_load_dependency(mda: &mut MemoryDependenceAnalysis, load: &ValueRef) -> MemDepResult {
    mda.get_dependency(load)
}

/// Check if a store is dead (no subsequent loads of the same location).
pub fn is_store_dead(_mda: &mut MemoryDependenceAnalysis, store: &ValueRef) -> bool {
    let s = store.borrow();
    s.use_empty()
}

/// Find the nearest common dominating memory definition for a location.
pub fn find_nearest_common_dominating_def(
    _mda: &MemoryDependenceAnalysis,
    loc: &MemoryLocation,
    blocks: &[ValueRef],
) -> Option<ValueRef> {
    if blocks.is_empty() {
        return None;
    }

    let mut defs: Vec<ValueRef> = Vec::new();

    for bb in blocks {
        let block = bb.borrow();
        let mut found = false;
        for inst in block.operands.iter().rev() {
            let i = inst.borrow();
            if let Some(Opcode::Store) = i.get_opcode() {
                if inst_may_access_same_location(inst, loc) {
                    defs.push(Rc::clone(inst));
                    found = true;
                    break;
                }
            }
            if let Some(Opcode::Call) = i.get_opcode() {
                break;
            }
        }
        if !found {
            return None;
        }
    }

    if let Some(first) = defs.first() {
        if defs.iter().all(|d| Rc::ptr_eq(d, first)) {
            return Some(Rc::clone(first));
        }
    }

    None
}

// ============================================================================
// Internal helpers
// ============================================================================

/// Get the memory location accessed by an instruction.
fn get_mem_location(inst: &ValueRef) -> Option<MemoryLocation> {
    let i = inst.borrow();
    let opcode = i.get_opcode()?;

    match opcode {
        Opcode::Load => {
            if i.operands.is_empty() {
                return None;
            }
            let ptr = Rc::clone(&i.operands[0]);
            let size = type_size_in_bytes(&i.ty);
            Some(MemoryLocation::new(ptr, size))
        }
        Opcode::Store => {
            if i.operands.len() < 2 {
                return None;
            }
            let ptr = Rc::clone(&i.operands[1]);
            let val_ty = &i.operands[0].borrow().ty;
            let size = type_size_in_bytes(val_ty);
            Some(MemoryLocation::new(ptr, size))
        }
        Opcode::AtomicRMW | Opcode::CmpXchg => {
            if i.operands.is_empty() {
                return None;
            }
            let ptr = Rc::clone(&i.operands[0]);
            let size = type_size_in_bytes(&i.ty);
            Some(MemoryLocation::new(ptr, size))
        }
        _ => None,
    }
}

/// Check if an instruction may access the same memory location.
fn inst_may_access_same_location(inst: &ValueRef, loc: &MemoryLocation) -> bool {
    let inst_loc = match get_mem_location(inst) {
        Some(l) => l,
        None => return false,
    };

    if Rc::ptr_eq(&inst_loc.ptr, &loc.ptr) {
        return true;
    }

    let obj_a = get_underlying_obj(&inst_loc.ptr);
    let obj_b = get_underlying_obj(&loc.ptr);

    if Rc::ptr_eq(&obj_a, &obj_b) {
        if let (Some(off_a), Some(off_b)) = (
            get_pointer_offset_int(&inst_loc.ptr),
            get_pointer_offset_int(&loc.ptr),
        ) {
            let end_a = off_a + inst_loc.size as i64;
            let end_b = off_b + loc.size as i64;
            return !(end_a <= off_b || end_b <= off_a);
        }
        return true;
    }

    false
}

/// Check if a store may alias with a given memory location.
fn may_alias_store_to_loc(store: &ValueRef, loc: &MemoryLocation) -> bool {
    inst_may_access_same_location(store, loc)
}

/// Check if a call may clobber a given memory location.
fn may_call_clobber_location(call: &ValueRef, loc: &MemoryLocation) -> bool {
    let c = call.borrow();
    if c.get_opcode() != Some(Opcode::Call) {
        return false;
    }

    let ptr = &loc.ptr;
    let p = ptr.borrow();

    if p.get_opcode() == Some(Opcode::Alloca) && !pointer_escapes(ptr) {
        return false;
    }

    true
}

/// Get the underlying object for a pointer (simplified).
fn get_underlying_obj(ptr: &ValueRef) -> ValueRef {
    let p = ptr.borrow();
    if p.get_opcode() == Some(Opcode::Alloca)
        || p.subclass == SubclassKind::GlobalVariable
        || p.subclass == SubclassKind::Argument
    {
        return Rc::clone(ptr);
    }
    if let Some(Opcode::GetElementPtr) = p.get_opcode() {
        if !p.operands.is_empty() {
            return get_underlying_obj(&p.operands[0]);
        }
    }
    Rc::clone(ptr)
}

/// Get the offset of a pointer from its underlying object.
fn get_pointer_offset_int(ptr: &ValueRef) -> Option<i64> {
    let p = ptr.borrow();
    if p.get_opcode() == Some(Opcode::Alloca)
        || p.subclass == SubclassKind::GlobalVariable
        || p.subclass == SubclassKind::Argument
    {
        return Some(0);
    }
    if let Some(Opcode::GetElementPtr) = p.get_opcode() {
        if p.operands.is_empty() {
            return None;
        }
        let base_off = get_pointer_offset_int(&p.operands[0])?;
        for op in &p.operands[1..] {
            if let Some(val) = get_const_i64(op) {
                return Some(base_off + val * 8);
            } else {
                return None;
            }
        }
    }
    None
}

/// Extract a constant i64 from a value.
fn get_const_i64(val: &ValueRef) -> Option<i64> {
    let v = val.borrow();
    if v.subclass == SubclassKind::Constant {
        v.name.parse::<i64>().ok()
    } else {
        None
    }
}

/// Check if a pointer may escape.
fn pointer_escapes(ptr: &ValueRef) -> bool {
    let v = ptr.borrow();
    for use_ in &v.uses {
        if let Some(user) = use_.user.upgrade() {
            let u = user.borrow();
            if let Some(Opcode::Store) = u.get_opcode() {
                if use_.operand_no == 0 && u.operands.len() >= 2 {
                    return true;
                }
            }
            if let Some(Opcode::Call) = u.get_opcode() {
                return true;
            }
        }
    }
    false
}

/// Find the basic block containing an instruction within a function.
fn find_parent_block(func: &ValueRef, inst: &ValueRef) -> Option<ValueRef> {
    let f = func.borrow();
    for op in &f.operands {
        let bb = op.borrow();
        for bb_inst in &bb.operands {
            if Rc::ptr_eq(bb_inst, inst) {
                return Some(Rc::clone(op));
            }
        }
    }
    None
}

/// Get predecessors of a basic block by scanning the function.
fn get_predecessors_of_block(bb: &ValueRef) -> Vec<ValueRef> {
    // Find the function that owns this block, then scan all blocks
    let b = bb.borrow();
    let mut preds = Vec::new();

    // If we have a parent, scan its operands
    if let Some(ref parent) = b.parent {
        let func = parent.borrow();
        for op in &func.operands {
            let block = op.borrow();
            // Check this block's operands for terminator successors pointing to bb
            if let Some(last) = block.operands.last() {
                let term = last.borrow();
                for succ_op in &term.operands {
                    if Rc::ptr_eq(succ_op, bb) {
                        preds.push(Rc::clone(op));
                        break;
                    }
                }
            }
        }
    }

    preds
}

/// Get the size in bytes of a type.
fn type_size_in_bytes(ty: &llvm_native_core::types::Type) -> u64 {
    use llvm_native_core::types::TypeKind;
    match &ty.kind {
        TypeKind::Integer { bits } => (*bits as u64 + 7) / 8,
        TypeKind::Float => 4,
        TypeKind::Double => 8,
        TypeKind::Half => 2,
        TypeKind::BFloat => 2,
        TypeKind::Pointer { .. } => 8,
        TypeKind::Array { len, .. } => *len as u64 * 8,
        TypeKind::Struct {
            element_type_ids, ..
        } => element_type_ids.len() as u64 * 8,
        TypeKind::FixedVector { len, .. } => *len as u64 * 8,
        _ => 0,
    }
}

// ============================================================================
// DependenceAnalysis — Distance/Direction vectors for loop dependencies
// ============================================================================

/// Dependence type: the kind of dependency between two memory references.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DependenceType {
    /// No dependence.
    NoDep,
    /// Read-after-write (true/flow dependence).
    ReadAfterWrite,
    /// Write-after-read (anti-dependence).
    WriteAfterRead,
    /// Write-after-write (output dependence).
    WriteAfterWrite,
}

impl DependenceType {
    pub fn as_str(&self) -> &'static str {
        match self {
            DependenceType::NoDep => "NoDep",
            DependenceType::ReadAfterWrite => "RAW",
            DependenceType::WriteAfterRead => "WAR",
            DependenceType::WriteAfterWrite => "WAW",
        }
    }
}

/// Dependence direction in a loop nest.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DependenceDirection {
    /// Source executes before sink.
    LT,
    /// Source and sink execute in the same iteration.
    EQ,
    /// Source executes after sink.
    GT,
    /// Direction is unknown (all directions possible).
    NE,
    /// All directions.
    ALL,
}

impl DependenceDirection {
    pub fn as_char(&self) -> char {
        match self {
            DependenceDirection::LT => '<',
            DependenceDirection::EQ => '=',
            DependenceDirection::GT => '>',
            DependenceDirection::NE => '!',
            DependenceDirection::ALL => '*',
        }
    }
}

/// Full dependence analysis result with distance/direction vectors.
#[derive(Debug, Clone)]
pub struct DependenceInfo {
    /// The type of dependence.
    pub dep_type: DependenceType,
    /// Distance vector (one entry per loop level).
    /// distance[i] = sink_iteration_i - source_iteration_i
    pub distances: Vec<i64>,
    /// Direction vector (one entry per loop level).
    pub directions: Vec<DependenceDirection>,
    /// The source memory reference.
    pub source: ValueRef,
    /// The sink memory reference.
    pub sink: ValueRef,
}

impl DependenceInfo {
    pub fn new(
        dep_type: DependenceType,
        source: ValueRef,
        sink: ValueRef,
        loop_depth: usize,
    ) -> Self {
        Self {
            dep_type,
            distances: vec![0; loop_depth],
            directions: vec![DependenceDirection::ALL; loop_depth],
            source,
            sink,
        }
    }

    /// Returns true if this dependence has known constant distances.
    pub fn is_consistent(&self) -> bool {
        self.directions
            .iter()
            .all(|d| *d != DependenceDirection::NE)
    }

    /// Returns true if the dependence distance is 0 in all dimensions
    /// (loop-independent dependence).
    pub fn is_loop_independent(&self) -> bool {
        self.directions
            .iter()
            .all(|d| *d == DependenceDirection::EQ)
    }
}

/// Dependence analysis with GCD test, Banerjee test, and direction/distance vectors.
#[derive(Debug, Clone, Default)]
pub struct DependenceAnalysis {
    /// All detected dependencies.
    pub dependencies: Vec<DependenceInfo>,
}

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

    /// Run dependence analysis between a source and sink memory reference
    /// within a loop nest of given depth.
    pub fn analyze(
        &mut self,
        source: &ValueRef,
        sink: &ValueRef,
        loop_depth: usize,
    ) -> DependenceInfo {
        let dep_type = Self::determine_dep_type(source, sink);
        let mut info = DependenceInfo::new(dep_type, source.clone(), sink.clone(), loop_depth);

        // Try GCD test for each loop level
        for level in 0..loop_depth {
            let (src_coeff, snk_coeff, const_diff) =
                Self::extract_coefficients(source, sink, level);
            if let Some(dist) = Self::gcd_test(src_coeff, snk_coeff, const_diff) {
                info.distances[level] = dist;
                info.directions[level] = Self::distance_to_direction(dist);
            } else {
                // Try Banerjee test for more precise bounds
                if let Some(dir) = Self::banerjee_test(src_coeff, snk_coeff, const_diff, 0, 255) {
                    info.directions[level] = dir;
                }
            }
        }

        self.dependencies.push(info.clone());
        info
    }

    /// GCD (Greatest Common Divisor) test.
    /// For dependence equation: a*i_src + b*i_snk = c
    /// A solution exists iff gcd(a, b) divides c.
    /// Returns the distance (i_snk - i_src) if found.
    pub fn gcd_test(a: i64, b: i64, c: i64) -> Option<i64> {
        if a == 0 && b == 0 {
            return if c == 0 { Some(0) } else { None };
        }

        let g = Self::gcd(a.unsigned_abs(), b.unsigned_abs()) as i64;
        if c % g != 0 {
            return None; // No integer solution
        }

        // For simple case where we solve for distance d = i_snk - i_src
        // where i_snk = i_src + d, the equation becomes:
        //   a*i_src + b*(i_src + d) = c
        //   (a+b)*i_src + b*d = c
        // For constant distance (independent of i_src), we need a+b=0
        if a + b == 0 {
            if b != 0 && c % b == 0 {
                return Some(c / b);
            }
        }

        // Otherwise return a general solution
        Some(c / g)
    }

    /// Banerjee test for dependence direction.
    /// Given the dependence equation and loop bounds, determines if a
    /// dependence with a given direction is possible.
    pub fn banerjee_test(
        _a: i64,
        _b: i64,
        _c: i64,
        _lb: i64,
        _ub: i64,
    ) -> Option<DependenceDirection> {
        // Banerjee inequality: for dependence direction '<', need:
        //   min(a*lb + b*(lb+1)) <= c <= max(a*ub + b*ub)
        // Simplified placeholder — full implementation computes bounds

        // If coefficients are all positive, direction is LT
        if _a > 0 && _b > 0 && _c > 0 {
            return Some(DependenceDirection::LT);
        }
        // If coefficients cancel, direction is EQ
        if _a + _b == 0 && _c == 0 {
            return Some(DependenceDirection::EQ);
        }

        Some(DependenceDirection::ALL)
    }

    /// Determine the type of dependence between two memory references.
    fn determine_dep_type(source: &ValueRef, sink: &ValueRef) -> DependenceType {
        let src = source.borrow();
        let snk = sink.borrow();

        let src_is_write = src.get_opcode() == Some(Opcode::Store);
        let snk_is_write = snk.get_opcode() == Some(Opcode::Store);

        match (src_is_write, snk_is_write) {
            (true, false) => DependenceType::ReadAfterWrite, // source writes, sink reads
            (false, true) => DependenceType::WriteAfterRead, // source reads, sink writes
            (true, true) => DependenceType::WriteAfterWrite, // both write
            (false, false) => DependenceType::NoDep,         // both read — no dependence
        }
    }

    /// Extract coefficients from the subscript equation.
    /// Returns (a, b, c) from a*i_src + b*i_snk = c
    fn extract_coefficients(
        _source: &ValueRef,
        _sink: &ValueRef,
        _level: usize,
    ) -> (i64, i64, i64) {
        // In practice, this examines GEP indices and induction variables.
        // For simple subscript: A[i] vs A[i+d] → a=1, b=-1, c=d
        (1, -1, 0)
    }

    /// Convert a distance value to a direction.
    fn distance_to_direction(d: i64) -> DependenceDirection {
        match d.cmp(&0) {
            std::cmp::Ordering::Less => DependenceDirection::LT,
            std::cmp::Ordering::Equal => DependenceDirection::EQ,
            std::cmp::Ordering::Greater => DependenceDirection::GT,
        }
    }

    /// Compute GCD of two unsigned integers.
    fn gcd(mut a: u64, mut b: u64) -> u64 {
        while b != 0 {
            let t = b;
            b = a % b;
            a = t;
        }
        a
    }

    /// Compute the direction vector for a pair of memory references.
    pub fn compute_direction_vector(&self, distances: &[i64]) -> Vec<DependenceDirection> {
        distances
            .iter()
            .map(|&d| Self::distance_to_direction(d))
            .collect()
    }

    /// Check if two references are definitely independent.
    pub fn is_independent(&self, source: &ValueRef, sink: &ValueRef) -> bool {
        for dep in &self.dependencies {
            if dep.source.borrow().vid == source.borrow().vid
                && dep.sink.borrow().vid == sink.borrow().vid
            {
                return dep.dep_type == DependenceType::NoDep;
            }
        }
        // Not analyzed → assume dependent
        false
    }

    /// Get all dependencies involving a given instruction.
    pub fn get_dependencies_for(&self, inst: &ValueRef) -> Vec<&DependenceInfo> {
        let vid = inst.borrow().vid;
        self.dependencies
            .iter()
            .filter(|d| d.source.borrow().vid == vid || d.sink.borrow().vid == vid)
            .collect()
    }

    /// Clear all cached dependencies.
    pub fn clear(&mut self) {
        self.dependencies.clear();
    }

    /// Number of dependencies found.
    pub fn len(&self) -> usize {
        self.dependencies.len()
    }

    pub fn is_empty(&self) -> bool {
        self.dependencies.is_empty()
    }
}

// ============================================================================
// DependenceTester — lightweight dependence testing helpers
// ============================================================================

/// Lightweight dependence tester for quick ZIV/SIV/MIV classification.
#[derive(Debug, Clone)]
pub struct DependenceTester;

impl DependenceTester {
    /// Check if two array subscripts are Zero Induction Variable (ZIV).
    /// ZIV: neither subscript depends on the loop index.
    pub fn is_ziv(_subscript_a: i64, _subscript_b: i64) -> bool {
        true // Both are constant subscripts
    }

    /// Check if two subscripts form a Single Induction Variable (SIV) test.
    /// SIV: exactly one loop index appears in both subscripts.
    pub fn is_siv(coeff_a: i64, coeff_b: i64) -> bool {
        coeff_a != 0 && coeff_b != 0
    }

    /// Check if two subscripts form a Multiple Induction Variable (MIV) test.
    /// MIV: multiple loop indices appear.
    pub fn is_miv(_num_indices: usize) -> bool {
        _num_indices >= 2
    }

    /// Perform the ZIV test: two constant subscripts are independent
    /// if they access different elements.
    pub fn test_ziv(const_a: i64, const_b: i64) -> DependenceType {
        if const_a == const_b {
            DependenceType::NoDep // Same element but need to check access type
        } else {
            DependenceType::NoDep
        }
    }

    /// Perform the SIV test for two subscript expressions.
    /// a*i + c1 vs b*i + c2 → dependence exists if (c2-c1) % gcd(a,b) == 0
    pub fn test_siv(a: i64, c1: i64, b: i64, c2: i64) -> Option<i64> {
        let c = c2 - c1;
        DependenceAnalysis::gcd_test(a, -b, c)
    }
}

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

#[cfg(test)]
mod tests {
    use super::*;
    use llvm_native_core::basic_block::BasicBlock;
    use llvm_native_core::types::Type;
    use llvm_native_core::value::valref;

    /// Helper: create a value with given name and opcode.
    fn make_inst(name: &str, opcode: Opcode, ty: Type) -> ValueRef {
        let mut v = llvm_native_core::value::Value::new(ty).named(name);
        v.subclass = SubclassKind::Instruction;
        v.opcode = Some(opcode);
        valref(v)
    }

    /// Helper: create a load instruction from a pointer.
    fn make_load(name: &str, ptr: &ValueRef, val_ty: Type) -> ValueRef {
        let mut v = llvm_native_core::value::Value::new(val_ty).named(name);
        v.subclass = SubclassKind::Instruction;
        v.opcode = Some(Opcode::Load);
        v.operands.push(Rc::clone(ptr));
        v.num_operands = 1;
        valref(v)
    }

    /// Helper: create a store instruction.
    fn make_store(name: &str, val: &ValueRef, ptr: &ValueRef) -> ValueRef {
        let mut v = llvm_native_core::value::Value::new(Type::void()).named(name);
        v.subclass = SubclassKind::Instruction;
        v.opcode = Some(Opcode::Store);
        v.operands.push(Rc::clone(val));
        v.operands.push(Rc::clone(ptr));
        v.num_operands = 2;
        valref(v)
    }

    /// Helper: create a basic block with instructions.
    fn make_bb(name: &str, insts: &[ValueRef]) -> ValueRef {
        let mut bb = BasicBlock::new(name);
        for inst in insts {
            bb.instructions.push(Rc::clone(inst));
            bb.value.borrow_mut().operands.push(Rc::clone(inst));
        }
        bb.value
    }

    /// Helper: create a function with basic blocks.
    fn make_func(name: &str, bbs: &[ValueRef]) -> ValueRef {
        let fn_ty = Type::function_type_with(Type::void().id, vec![], false);
        let mut v = llvm_native_core::value::Value::new(fn_ty).named(name);
        v.subclass = SubclassKind::Function;
        for bb in bbs {
            // Set parent for each block
            v.operands.push(Rc::clone(bb));
        }
        valref(v)
    }

    // -----------------------------------------------------------------------
    // MemDepResult tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_mem_dep_result_is_def() {
        let inst = make_inst("x", Opcode::Store, Type::void());
        let result = MemDepResult::Def(Rc::clone(&inst));
        assert!(result.is_def());
        assert!(!result.is_clobber());
        assert!(result.get_def().is_some());
    }

    #[test]
    fn test_mem_dep_result_clobber() {
        let result = MemDepResult::Clobber;
        assert!(!result.is_def());
        assert!(result.is_clobber());
        assert!(result.get_def().is_none());
    }

    #[test]
    fn test_mem_dep_result_display() {
        let inst = make_inst("store1", Opcode::Store, Type::void());
        let result = MemDepResult::Def(Rc::clone(&inst));
        assert!(format!("{}", result).contains("store1"));
        assert_eq!(format!("{}", MemDepResult::Clobber), "Clobber");
        assert_eq!(format!("{}", MemDepResult::Unknown), "Unknown");
    }

    // -----------------------------------------------------------------------
    // MemoryDependenceAnalysis tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_mda_new() {
        let func = make_func("test_fn", &[]);
        let mda = MemoryDependenceAnalysis::new(&func);
        assert!(Rc::ptr_eq(&mda.func, &func));
    }

    #[test]
    fn test_may_access_memory_load() {
        let load = make_inst("l", Opcode::Load, Type::i32());
        assert!(MemoryDependenceAnalysis::may_access_memory(&load));
    }

    #[test]
    fn test_may_access_memory_store() {
        let store = make_inst("s", Opcode::Store, Type::void());
        assert!(MemoryDependenceAnalysis::may_access_memory(&store));
    }

    #[test]
    fn test_may_access_memory_call() {
        let call = make_inst("c", Opcode::Call, Type::i32());
        assert!(MemoryDependenceAnalysis::may_access_memory(&call));
    }

    #[test]
    fn test_may_access_memory_add_false() {
        let add = make_inst("a", Opcode::Add, Type::i32());
        assert!(!MemoryDependenceAnalysis::may_access_memory(&add));
    }

    #[test]
    fn test_may_access_memory_alloca_false() {
        let alloca = make_inst("a", Opcode::Alloca, Type::pointer(0));
        assert!(!MemoryDependenceAnalysis::may_access_memory(&alloca));
    }

    #[test]
    fn test_simple_dependency_load_after_store() {
        let ptr = make_inst("ptr", Opcode::Alloca, Type::pointer(0));
        let val_inst = make_inst("val", Opcode::Add, Type::i32());
        let store = make_store("store", &val_inst, &ptr);
        let load = make_load("load", &ptr, Type::i32());

        let bb = make_bb(
            "entry",
            &[Rc::clone(&ptr), Rc::clone(&store), Rc::clone(&load)],
        );
        let func = make_func("test_fn", &[Rc::clone(&bb)]);
        // Set parent on the block inside the function so predecessor scanning works
        if let Some(bb_in_func) = func.borrow().operands.first() {
            bb_in_func.borrow_mut().parent = Some(Rc::clone(&func));
        }

        let mut mda = MemoryDependenceAnalysis::new(&func);
        let dep = mda.get_simple_dependency(&load, &bb);
        assert!(dep.is_def());
    }

    #[test]
    fn test_get_dependency_load_from_unknown() {
        let ptr = make_inst("ptr", Opcode::Alloca, Type::pointer(0));
        let load = make_load("load", &ptr, Type::i32());

        let bb = make_bb("entry", &[Rc::clone(&ptr), Rc::clone(&load)]);
        let func = make_func("test_fn", &[Rc::clone(&bb)]);
        if let Some(bb_in_func) = func.borrow().operands.first() {
            bb_in_func.borrow_mut().parent = Some(Rc::clone(&func));
        }

        let mut mda = MemoryDependenceAnalysis::new(&func);
        let dep = mda.get_dependency(&load);
        // No preceding def → unknown or non-local for entry block
        assert!(matches!(
            dep,
            MemDepResult::Unknown | MemDepResult::NonFuncLocal
        ));
    }

    #[test]
    fn test_clear_cache() {
        let func = make_func("test_fn", &[]);
        let mut mda = MemoryDependenceAnalysis::new(&func);
        mda.cache.insert(42, MemDepResult::Clobber);
        mda.clear_cache();
        assert!(mda.cache.is_empty());
    }

    #[test]
    fn test_invalidate() {
        let inst = make_inst("x", Opcode::Store, Type::void());
        let func = make_func("test_fn", &[]);
        let mut mda = MemoryDependenceAnalysis::new(&func);
        let vid = inst.borrow().vid as usize;
        mda.cache.insert(vid, MemDepResult::Clobber);
        mda.invalidate(&inst);
        assert!(mda.dirty.contains(&vid));
    }

    #[test]
    fn test_verify_self_dependency_fails() {
        let inst = make_inst("x", Opcode::Store, Type::void());
        let func = make_func("test_fn", &[]);
        let mut mda = MemoryDependenceAnalysis::new(&func);
        let vid = inst.borrow().vid as usize;
        mda.cache.insert(vid, MemDepResult::Def(Rc::clone(&inst)));
        let result = mda.verify();
        assert!(result.is_err());
    }

    #[test]
    fn test_verify_empty_cache_ok() {
        let func = make_func("test_fn", &[]);
        let mda = MemoryDependenceAnalysis::new(&func);
        assert!(mda.verify().is_ok());
    }

    // -----------------------------------------------------------------------
    // Convenience function tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_is_store_dead_no_uses() {
        let store = make_store(
            "s",
            &make_inst("val", Opcode::Add, Type::i32()),
            &make_inst("p", Opcode::Alloca, Type::pointer(0)),
        );
        let func = make_func("test_fn", &[]);
        let mut mda = MemoryDependenceAnalysis::new(&func);
        assert!(is_store_dead(&mut mda, &store));
    }

    #[test]
    fn test_find_nearest_common_dominating_def_empty() {
        let func = make_func("test_fn", &[]);
        let mda = MemoryDependenceAnalysis::new(&func);
        let ptr = make_inst("ptr", Opcode::Alloca, Type::pointer(0));
        let loc = MemoryLocation::new(ptr, 4);
        assert!(find_nearest_common_dominating_def(&mda, &loc, &[]).is_none());
    }

    #[test]
    fn test_get_load_dependency() {
        let ptr = make_inst("ptr", Opcode::Alloca, Type::pointer(0));
        let load = make_load("ld", &ptr, Type::i32());
        let bb = make_bb("entry", &[Rc::clone(&ptr), Rc::clone(&load)]);
        let func = make_func("test_fn", &[Rc::clone(&bb)]);
        if let Some(bb_in_func) = func.borrow().operands.first() {
            bb_in_func.borrow_mut().parent = Some(Rc::clone(&func));
        }

        let mut mda = MemoryDependenceAnalysis::new(&func);
        let dep = get_load_dependency(&mut mda, &load);
        // No preceding store → should be Unknown or NonFuncLocal
        assert!(matches!(
            dep,
            MemDepResult::Unknown | MemDepResult::NonFuncLocal
        ));
    }
}