llvm-native-core-ext 0.1.0

//! LLVM LoopAccessInfo — high-level access pattern and dependence
//! analysis for loop vectorisation.
//!
//! Clean-room behavioural reconstruction from compiler optimisation
//! literature. Zero LLVM source code consultation.

use llvm_native_core::analysis::LoopInfo;
use llvm_native_core::loop_access_analysis::{AccessType, LoopAccessAnalysis};
use llvm_native_core::opcode::Opcode;
use llvm_native_core::scalar_evolution::ScalarEvolution;
use llvm_native_core::value::ValueRef;
use std::collections::HashMap;

// ============================================================================
// Support types
// ============================================================================

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DepType {
    NoDep,
    RAW,
    WAR,
    WAW,
    RAR,
    Unknown,
}

impl DepType {
    pub fn is_safe_for_vectorization(&self) -> bool {
        matches!(self, DepType::NoDep | DepType::RAR)
    }
    pub fn name(&self) -> &'static str {
        match self {
            DepType::NoDep => "NoDep",
            DepType::RAW => "RAW",
            DepType::WAR => "WAR",
            DepType::WAW => "WAW",
            DepType::RAR => "RAR",
            DepType::Unknown => "Unknown",
        }
    }
}

#[derive(Debug, Clone)]
pub struct RuntimeCheck {
    pub start_a: ValueRef,
    pub end_a: ValueRef,
    pub start_b: ValueRef,
    pub end_b: ValueRef,
    pub count: u64,
}

#[derive(Debug, Clone)]
pub struct MemoryDep {
    pub src: ValueRef,
    pub dst: ValueRef,
    pub dep_type: DepType,
}

// ============================================================================
// LoopAccessInfo — high-level vectorisation info
// ============================================================================

pub struct LoopAccessInfo {
    loop_info: LoopInfo,
    access_analysis: LoopAccessAnalysis,
    runtime_checks: Vec<RuntimeCheck>,
    dependences: Vec<MemoryDep>,
    stride_info: HashMap<usize, (i64, bool)>,
    vectorizable: bool,
    vectorization_factor: u32,
}

impl LoopAccessInfo {
    pub fn new(loop_info: &LoopInfo, _scev: &ScalarEvolution) -> Self {
        let mut access_analysis = LoopAccessAnalysis::new(&loop_info.header);

        // Analyze loop memory accesses.
        let _ = access_analysis.analyze_loop(loop_info);

        let dependences = Self::compute_memory_dependences(&access_analysis);
        let runtime_checks = Self::compute_runtime_checks(&access_analysis, loop_info);
        let vectorizable = Self::evaluate_vectorizability(&access_analysis, &dependences);
        let stride_info = Self::compute_stride_info(&access_analysis);
        let vf = if vectorizable {
            access_analysis.vectorization_factor
        } else {
            1
        };

        LoopAccessInfo {
            loop_info: loop_info.clone(),
            access_analysis,
            runtime_checks,
            dependences,
            stride_info,
            vectorizable,
            vectorization_factor: vf,
        }
    }

    pub fn can_vectorize(&self) -> bool {
        self.vectorizable
    }

    pub fn get_checks(&self) -> Vec<RuntimeCheck> {
        self.runtime_checks.clone()
    }

    pub fn get_dependences(&self) -> Vec<MemoryDep> {
        self.dependences.clone()
    }

    pub fn get_stride_info(&self, ptr: &ValueRef) -> (i64, bool) {
        let ptr_id = ptr.borrow().vid as usize;
        self.stride_info.get(&ptr_id).copied().unwrap_or((0, false))
    }

    pub fn get_vectorization_factor(&self) -> u32 {
        self.vectorization_factor
    }

    pub fn num_runtime_checks(&self) -> usize {
        self.runtime_checks.len()
    }

    pub fn num_dependences(&self) -> usize {
        self.dependences.len()
    }

    pub fn set_vectorization_factor(&mut self, vf: u32) {
        self.vectorization_factor = vf;
    }

    fn compute_memory_dependences(analysis: &LoopAccessAnalysis) -> Vec<MemoryDep> {
        let mut deps = Vec::new();
        for dep in &analysis.dependences {
            let src = analysis
                .accesses
                .get(dep.source)
                .map(|a| a.instruction.clone());
            let dst = analysis
                .accesses
                .get(dep.target)
                .map(|a| a.instruction.clone());
            if let (Some(src_v), Some(dst_v)) = (src, dst) {
                deps.push(MemoryDep {
                    src: src_v,
                    dst: dst_v,
                    dep_type: convert_dep_type(&dep.dependence_type),
                });
            }
        }
        deps
    }

    fn compute_runtime_checks(
        analysis: &LoopAccessAnalysis,
        loop_info: &LoopInfo,
    ) -> Vec<RuntimeCheck> {
        if !analysis.needs_runtime_checks() {
            return Vec::new();
        }
        let mut checks = Vec::new();
        for i in 0..analysis.accesses.len() {
            for j in (i + 1)..analysis.accesses.len() {
                if analysis.may_alias(&analysis.accesses[i], &analysis.accesses[j]) {
                    checks.push(RuntimeCheck {
                        start_a: analysis.accesses[i].pointer.clone(),
                        end_a: analysis.accesses[i].pointer.clone(),
                        start_b: analysis.accesses[j].pointer.clone(),
                        end_b: analysis.accesses[j].pointer.clone(),
                        count: loop_info.trip_count.unwrap_or(1),
                    });
                }
            }
        }
        checks
    }

    fn evaluate_vectorizability(analysis: &LoopAccessAnalysis, dependences: &[MemoryDep]) -> bool {
        if !analysis.is_vectorizable {
            return false;
        }
        for dep in dependences {
            if !dep.dep_type.is_safe_for_vectorization() {
                return false;
            }
        }
        true
    }

    fn compute_stride_info(analysis: &LoopAccessAnalysis) -> HashMap<usize, (i64, bool)> {
        let mut info = HashMap::new();
        for access in &analysis.accesses {
            let ptr_id = access.pointer.borrow().vid as usize;
            let is_strided = access.access_type.is_consecutive()
                || matches!(access.access_type, AccessType::Strided(_));
            info.insert(ptr_id, (access.stride, is_strided));
        }
        info
    }
}

fn convert_dep_type(dt: &llvm_native_core::loop_access_analysis::DependenceType) -> DepType {
    use llvm_native_core::loop_access_analysis::DependenceType;
    match dt {
        DependenceType::NoDep => DepType::NoDep,
        DependenceType::Forward => DepType::RAW,
        DependenceType::Backward => DepType::WAR,
        DependenceType::Bidirectional => DepType::WAW,
        DependenceType::Unknown => DepType::Unknown,
    }
}

// ============================================================================
// RuntimePointerChecking — SCEV-Based Alias Check Generation
// ============================================================================

/// Configuration for runtime pointer checking.
#[derive(Debug, Clone)]
pub struct RuntimePointerCheckingConfig {
    /// Whether to use SCEV for precise comparison.
    pub use_scev: bool,
    /// Maximum number of pointer pairs to check before bailing out.
    pub max_check_pairs: usize,
    /// Whether to merge checks when possible.
    pub merge_checks: bool,
    /// Whether to generate checks for same-underlying-object pointers.
    pub check_same_object: bool,
}

impl Default for RuntimePointerCheckingConfig {
    fn default() -> Self {
        RuntimePointerCheckingConfig {
            use_scev: true,
            max_check_pairs: 100,
            merge_checks: true,
            check_same_object: false,
        }
    }
}

/// A pointer group — accesses to the same underlying object.
#[derive(Debug, Clone)]
pub struct PointerGroup {
    /// The underlying object (alloca, global, or argument).
    pub underlying_object: Option<ValueRef>,
    /// All memory accesses in this group.
    pub accesses: Vec<ValueRef>,
    /// Minimum SCEV start across all accesses.
    pub min_start: Option<i64>,
    /// Maximum SCEV end across all accesses.
    pub max_end: Option<i64>,
}

/// Full runtime pointer checking analysis for vectorization.
#[derive(Debug)]
pub struct RuntimePointerChecking {
    /// All pointer groups (accesses to the same object).
    pub groups: Vec<PointerGroup>,
    /// Pairs of groups that need runtime checks.
    pub check_pairs: Vec<(usize, usize)>,
    /// Whether any checks need to be generated.
    pub needs_checks: bool,
    /// The SCEV reference (held externally).
    pub config: RuntimePointerCheckingConfig,
}

impl RuntimePointerChecking {
    /// Create a new runtime pointer checking analysis.
    pub fn new(config: RuntimePointerCheckingConfig) -> Self {
        RuntimePointerChecking {
            groups: Vec::new(),
            check_pairs: Vec::new(),
            needs_checks: false,
            config,
        }
    }

    /// Insert a pointer into its group (based on underlying object).
    pub fn insert_pointer(
        &mut self,
        ptr: &ValueRef,
        start: i64,
        end: i64,
        underlying: Option<ValueRef>,
    ) {
        // Try to find an existing group for this underlying object.
        let group_idx = if let Some(ref obj) = underlying {
            self.groups.iter().position(|g| {
                g.underlying_object
                    .as_ref()
                    .map_or(false, |o| o.borrow().vid == obj.borrow().vid)
            })
        } else {
            None
        };

        match group_idx {
            Some(idx) => {
                let group = &mut self.groups[idx];
                group.accesses.push(ptr.clone());
                group.min_start = Some(group.min_start.unwrap_or(start).min(start));
                group.max_end = Some(group.max_end.unwrap_or(end).max(end));
            }
            None => {
                self.groups.push(PointerGroup {
                    underlying_object: underlying.clone(),
                    accesses: vec![ptr.clone()],
                    min_start: Some(start),
                    max_end: Some(end),
                });
            }
        }
    }

    /// Group accesses by their underlying object.
    ///
    /// Two pointers access the same underlying object if they are:
    /// - The same alloca
    /// - The same global variable
    /// - The same GEP base pointer
    pub fn group_by_underlying_object(&mut self, accesses: &[ValueRef]) -> usize {
        let mut group_map: HashMap<u64, usize> = HashMap::new();

        for acc in accesses {
            let underlying = find_underlying_object(acc);
            let key = underlying
                .as_ref()
                .map(|u| u.borrow().vid)
                .unwrap_or(acc.borrow().vid);

            if let Some(&group_idx) = group_map.get(&key) {
                self.groups[group_idx].accesses.push(acc.clone());
            } else {
                let idx = self.groups.len();
                group_map.insert(key, idx);
                self.groups.push(PointerGroup {
                    underlying_object: underlying,
                    accesses: vec![acc.clone()],
                    min_start: None,
                    max_end: None,
                });
            }
        }

        self.groups.len()
    }

    /// Generate SCEV-based runtime alias checks between pointer groups.
    ///
    /// For each pair of groups that may alias, generate a runtime check
    /// that tests whether the memory ranges overlap.
    pub fn generate_scev_checks(&mut self, trip_count: u64) -> Vec<RuntimeCheck> {
        let mut checks = Vec::new();

        if self.groups.len() < 2 {
            return checks;
        }

        let max_pairs = self.config.max_check_pairs;
        let mut pair_count = 0;

        for i in 0..self.groups.len() {
            for j in (i + 1)..self.groups.len() {
                if pair_count >= max_pairs {
                    break;
                }

                let group_a = &self.groups[i];
                let group_b = &self.groups[j];

                // Skip if both groups have known bounds and don't overlap.
                if let (Some(a_start), Some(a_end), Some(b_start), Some(b_end)) = (
                    group_a.min_start,
                    group_a.max_end,
                    group_b.min_start,
                    group_b.max_end,
                ) {
                    // If ranges are disjoint, no check needed.
                    if a_end < b_start || b_end < a_start {
                        continue;
                    }
                }

                // Create a runtime check for this pair.
                if let Some(check) = self.create_check_for_groups(group_a, group_b, trip_count) {
                    checks.push(check);
                    self.check_pairs.push((i, j));
                    pair_count += 1;
                }
            }
        }

        self.needs_checks = !checks.is_empty();
        checks
    }

    /// Create a single runtime check for two pointer groups.
    fn create_check_for_groups(
        &self,
        group_a: &PointerGroup,
        group_b: &PointerGroup,
        trip_count: u64,
    ) -> Option<RuntimeCheck> {
        let start_a = group_a.accesses.first()?.clone();
        let end_a = group_a.accesses.last().unwrap_or(&start_a).clone();
        let start_b = group_b.accesses.first()?.clone();
        let end_b = group_b.accesses.last().unwrap_or(&start_b).clone();

        Some(RuntimeCheck {
            start_a,
            end_a,
            start_b,
            end_b,
            count: trip_count,
        })
    }

    /// Try to merge overlapping or adjacent checks into a single check.
    ///
    /// Merging reduces the number of runtime checks, which improves
    /// performance (fewer branches before the vectorized loop).
    pub fn merge_overlapping_checks(&self, checks: &[RuntimeCheck]) -> Vec<RuntimeCheck> {
        if !self.config.merge_checks || checks.len() <= 1 {
            return checks.to_vec();
        }

        let mut merged: Vec<RuntimeCheck> = Vec::new();
        let mut remaining: Vec<RuntimeCheck> = checks.to_vec();

        while !remaining.is_empty() {
            let mut current = remaining.remove(0);
            let mut changed = true;

            while changed {
                changed = false;
                let mut i = 0;
                while i < remaining.len() {
                    if self.can_merge_checks(&current, &remaining[i]) {
                        current = self.merge_two_checks(&current, &remaining[i]);
                        remaining.remove(i);
                        changed = true;
                    } else {
                        i += 1;
                    }
                }
            }

            merged.push(current);
        }

        merged
    }

    /// Check if two runtime checks can be merged.
    fn can_merge_checks(&self, a: &RuntimeCheck, b: &RuntimeCheck) -> bool {
        // Checks can be merged if they access the same pointer pairs.
        let a_start = a.start_a.borrow().vid;
        let b_start = b.start_b.borrow().vid;
        let same_start_a = a_start == b.start_a.borrow().vid || a_start == b.start_b.borrow().vid;
        let same_start_b = b_start == b.start_a.borrow().vid || b_start == b.start_b.borrow().vid;
        same_start_a && same_start_b
    }

    /// Merge two runtime checks into one.
    fn merge_two_checks(&self, a: &RuntimeCheck, b: &RuntimeCheck) -> RuntimeCheck {
        RuntimeCheck {
            start_a: a.start_a.clone(),
            end_a: b.end_a.clone(),
            start_b: a.start_b.clone(),
            end_b: b.end_b.clone(),
            count: a.count.max(b.count),
        }
    }
}

// ============================================================================
// AccessAnalysis — Group Memory Access By Underlying Object
// ============================================================================

/// Tracks how each pointer is derived from a base object.
#[derive(Debug, Clone)]
pub struct PointerDerivation {
    /// The base object (the alloca, global, or argument).
    pub base: ValueRef,
    /// The cumulative constant offset from the base.
    pub offset: i64,
    /// Whether the offset is known to be constant.
    pub offset_is_constant: bool,
}

/// Detailed access analysis grouping memory operations by their
/// underlying storage object.
#[derive(Debug)]
pub struct AccessAnalysis {
    /// Groups: each group maps to accesses sharing an underlying object.
    pub groups: HashMap<u64, Vec<ValueRef>>,
    /// Sizes of each underlying object (in bytes).
    pub object_sizes: HashMap<u64, u64>,
    /// Pointer derivation info for each access.
    pub derivations: HashMap<u64, PointerDerivation>,
    /// The trip count of the loop.
    pub trip_count: u64,
}

impl AccessAnalysis {
    /// Create a new access analysis.
    pub fn new(trip_count: u64) -> Self {
        AccessAnalysis {
            groups: HashMap::new(),
            object_sizes: HashMap::new(),
            derivations: HashMap::new(),
            trip_count,
        }
    }

    /// Add a memory access to the analysis.
    pub fn add_access(
        &mut self,
        access: &ValueRef,
        base: Option<ValueRef>,
        offset: i64,
        size: u64,
    ) {
        let access_vid = access.borrow().vid;

        if let Some(ref base_val) = base {
            let base_vid = base_val.borrow().vid;
            self.groups
                .entry(base_vid)
                .or_default()
                .push(access.clone());
            self.object_sizes.entry(base_vid).or_insert(size);
            self.derivations.insert(
                access_vid,
                PointerDerivation {
                    base: base_val.clone(),
                    offset,
                    offset_is_constant: true,
                },
            );
        } else {
            // Unknown base — create a unique group for this access.
            self.groups
                .entry(access_vid)
                .or_default()
                .push(access.clone());
        }
    }

    /// Group accesses by their underlying object.
    ///
    /// All accesses derived from the same base pointer (e.g., the same
    /// alloca or global) are placed in the same group. This is essential
    /// for dependence analysis because accesses within a group are known
    /// to potentially alias, while accesses in different groups alias
    /// only if the groups' underlying objects may alias.
    pub fn group_by_underlying_object(&mut self, accesses: &[ValueRef]) {
        for acc in accesses {
            let base = find_underlying_object(acc);
            let offset = compute_constant_offset(acc);
            let size = estimate_access_size(acc);
            self.add_access(acc, base, offset, size);
        }
    }

    /// Check if two accesses are in the same group (same underlying object).
    pub fn same_group(&self, a: &ValueRef, b: &ValueRef) -> bool {
        let a_vid = a.borrow().vid;
        let b_vid = b.borrow().vid;

        for group in self.groups.values() {
            let mut has_a = false;
            let mut has_b = false;
            for acc in group {
                let vid = acc.borrow().vid;
                if vid == a_vid {
                    has_a = true;
                }
                if vid == b_vid {
                    has_b = true;
                }
            }
            if has_a && has_b {
                return true;
            }
        }
        false
    }

    /// Compute the number of distinct underlying objects accessed.
    pub fn num_distinct_objects(&self) -> usize {
        self.groups.len()
    }

    /// Get all accesses in the same group as the given access.
    pub fn get_group_for(&self, access: &ValueRef) -> Vec<ValueRef> {
        let access_vid = access.borrow().vid;
        for group in self.groups.values() {
            if group.iter().any(|a| a.borrow().vid == access_vid) {
                return group.clone();
            }
        }
        Vec::new()
    }
}

// ============================================================================
// Dependence Distance Computation
// ============================================================================

/// A dependence distance between two memory accesses.
#[derive(Debug, Clone, Copy)]
pub struct DependenceDistance {
    /// The minimum distance (in iterations).
    pub min_distance: i64,
    /// The maximum distance (may be infinite).
    pub max_distance: Option<i64>,
    /// Whether the distance is known exactly (min == max).
    pub is_exact: bool,
    /// The type of dependence.
    pub dep_type: DepType,
}

impl DependenceDistance {
    /// Create a new dependence distance.
    pub fn new(min: i64, max: Option<i64>, dep_type: DepType) -> Self {
        DependenceDistance {
            min_distance: min,
            max_distance: max,
            is_exact: max.map_or(false, |m| m == min),
            dep_type,
        }
    }

    /// Check if the dependence prevents vectorization.
    ///
    /// A dependence is safe for vectorization if:
    /// - It is NoDep or RAR (no data hazard)
    /// - The distance is >= vectorization factor (for RAW/WAW/WAR)
    pub fn safe_for_vectorization(&self, vf: u32) -> bool {
        match self.dep_type {
            DepType::NoDep | DepType::RAR => true,
            _ => self.min_distance.abs() >= vf as i64,
        }
    }

    /// Check if the distance is infinite (no dependence).
    pub fn is_infinite(&self) -> bool {
        self.max_distance.is_none() && self.min_distance == i64::MAX
    }
}

impl LoopAccessInfo {
    /// Check if two memory accesses are dependent.
    ///
    /// Two accesses are dependent if they may access the same memory
    /// location and at least one is a write.
    pub fn is_dependent(&self, a: &ValueRef, b: &ValueRef) -> bool {
        let a_val = a.borrow();
        let b_val = b.borrow();

        // If neither is a store, and they don't have potential
        // aliasing issues, they are independent.
        let a_is_write = a_val.subclass == llvm_native_core::value::SubclassKind::StoreInst;
        let b_is_write = b_val.subclass == llvm_native_core::value::SubclassKind::StoreInst;

        // RAR (Read-After-Read) is not a dependence.
        if !a_is_write && !b_is_write {
            return false;
        }

        // Check if they have the same base.
        let a_base = find_underlying_object(a);
        let b_base = find_underlying_object(b);

        match (&a_base, &b_base) {
            (Some(ab), Some(bb)) => {
                // Same base → may alias.
                ab.borrow().vid == bb.borrow().vid
            }
            _ => {
                // Unknown bases → conservatively assume dependence.
                true
            }
        }
    }

    /// Compute the dependence distance between two memory accesses.
    ///
    /// The dependence distance is the number of loop iterations between
    /// when the source access and the target access refer to the same
    /// memory location.
    pub fn get_dependence_distance(&self, src: &ValueRef, dst: &ValueRef) -> DependenceDistance {
        let src_deriv = compute_pointer_derivation(src);
        let dst_deriv = compute_pointer_derivation(dst);

        // If both derivations are known and have the same base:
        if let (Some(s), Some(d)) = (&src_deriv, &dst_deriv) {
            if s.base.borrow().vid == d.base.borrow().vid {
                // The distance is (dst_offset - src_offset) / stride.
                let offset_diff = d.offset - s.offset;

                // Determine stride from the loop access analysis.
                let stride = self
                    .access_analysis
                    .accesses
                    .iter()
                    .find(|a| a.pointer.borrow().vid == src.borrow().vid)
                    .map(|a| a.stride)
                    .unwrap_or(1);

                if stride != 0 {
                    let distance = offset_diff / stride;
                    let dep_type = classify_dependence(src, dst);
                    return DependenceDistance::new(distance, Some(distance), dep_type);
                }
            }
        }

        // Unknown distance → conservative estimate.
        let dep_type = classify_dependence(src, dst);
        DependenceDistance::new(0, None, dep_type)
    }

    /// Build a complete dependence graph for all memory accesses in the loop.
    pub fn build_dependence_graph(
        &self,
        accesses: &[ValueRef],
    ) -> Vec<(usize, usize, DependenceDistance)> {
        let mut deps = Vec::new();

        for i in 0..accesses.len() {
            for j in (i + 1)..accesses.len() {
                if self.is_dependent(&accesses[i], &accesses[j]) {
                    let dist = self.get_dependence_distance(&accesses[i], &accesses[j]);
                    deps.push((i, j, dist));
                }
            }
        }

        deps
    }

    /// Analyze full memory dependence for vectorization.
    ///
    /// This is the main analysis entry point: it examines all memory
    /// accesses in the loop, computes their dependence relationships,
    /// and determines the optimal vectorization factor.
    pub fn analyze_memory_dependence_for_vectorization(&mut self, accesses: &[ValueRef]) -> bool {
        // Reset state.
        self.dependences.clear();
        self.runtime_checks.clear();
        self.vectorizable = true;

        if accesses.is_empty() {
            return true;
        }

        // Build dependence graph.
        let deps = self.build_dependence_graph(accesses);

        // Check each dependence for vectorization safety.
        for &(src_idx, dst_idx, ref dist) in &deps {
            let dep = MemoryDep {
                src: accesses[src_idx].clone(),
                dst: accesses[dst_idx].clone(),
                dep_type: dist.dep_type,
            };

            self.dependences.push(dep);

            // Check if the dependence prevents vectorization.
            if !dist.safe_for_vectorization(self.vectorization_factor) {
                self.vectorizable = false;

                // Try reducing the vectorization factor.
                for vf in (2..=self.vectorization_factor).rev() {
                    if dist.safe_for_vectorization(vf) {
                        self.vectorization_factor = vf;
                        self.vectorizable = true;
                        break;
                    }
                }
            }
        }

        // Generate runtime checks for overlapping accesses.
        let mut rtc = RuntimePointerChecking::new(RuntimePointerCheckingConfig::default());
        rtc.group_by_underlying_object(accesses);
        self.runtime_checks = rtc.generate_scev_checks(self.loop_info.trip_count.unwrap_or(1));

        self.vectorizable
    }
}

// ============================================================================
// Helper functions for pointer and dependence analysis
// ============================================================================

/// Find the underlying object for a pointer value.
///
/// Strips through GEPs, bitcasts, and addrspace casts to find the
/// original alloca, global variable, or function argument.
fn find_underlying_object(ptr: &ValueRef) -> Option<ValueRef> {
    let p = ptr.borrow();

    // If this is an alloca, global, or argument, it's the underlying object.
    match p.subclass {
        llvm_native_core::value::SubclassKind::AllocaInst
        | llvm_native_core::value::SubclassKind::GlobalVariable
        | llvm_native_core::value::SubclassKind::Argument => {
            return Some(ptr.clone());
        }
        _ => {}
    }

    // If this is a GEP, bitcast, or addrspace cast, recurse into the
    // pointer operand (operand 0).
    if p.opcode == Some(Opcode::GetElementPtr)
        || p.opcode == Some(Opcode::BitCast)
        || p.opcode == Some(Opcode::AddrSpaceCast)
    {
        if let Some(op) = p.operand(0) {
            return find_underlying_object(&op);
        }
    }

    None
}

/// Compute the constant offset from the underlying object.
fn compute_constant_offset(ptr: &ValueRef) -> i64 {
    let p = ptr.borrow();

    if p.opcode == Some(Opcode::GetElementPtr) && p.operands.len() >= 2 {
        // The GEP indices (operands 1+) contribute to the offset.
        let mut total_offset: i64 = 0;
        for idx in &p.operands[1..] {
            if let Some(c) = try_extract_constant_internal(idx) {
                total_offset += c;
            } else {
                return 0; // Non-constant index — unknown offset.
            }
        }
        return total_offset;
    }

    0
}

/// Estimate the size in bytes of a memory access.
fn estimate_access_size(access: &ValueRef) -> u64 {
    let a = access.borrow();
    match a.subclass {
        llvm_native_core::value::SubclassKind::LoadInst | llvm_native_core::value::SubclassKind::StoreInst => {
            // Default to 8 bytes if unknown, or use the type size.
            8
        }
        _ => 8,
    }
}

/// Compute the pointer derivation for a memory access.
fn compute_pointer_derivation(access: &ValueRef) -> Option<PointerDerivation> {
    let a = access.borrow();

    // Get the pointer operand.
    let ptr = if a.operands.is_empty() {
        return None;
    } else {
        a.operands[0].clone()
    };

    let base = find_underlying_object(&ptr)?;
    let offset = compute_constant_offset(&ptr);

    Some(PointerDerivation {
        base,
        offset,
        offset_is_constant: true,
    })
}

/// Classify the dependence type between two memory accesses.
fn classify_dependence(src: &ValueRef, dst: &ValueRef) -> DepType {
    let s = src.borrow();
    let d = dst.borrow();

    let src_is_write = s.subclass == llvm_native_core::value::SubclassKind::StoreInst;
    let dst_is_write = d.subclass == llvm_native_core::value::SubclassKind::StoreInst;

    match (src_is_write, dst_is_write) {
        (false, false) => DepType::RAR, // Read-After-Read
        (true, false) => DepType::RAW,  // Read-After-Write
        (false, true) => DepType::WAR,  // Write-After-Read
        (true, true) => DepType::WAW,   // Write-After-Write
    }
}

/// Try to extract a constant integer value from a ValueRef.
fn try_extract_constant_internal(val: &ValueRef) -> Option<i64> {
    let v = val.borrow();
    if v.is_constant() {
        return Some(v.get_subclass_data() as i64);
    }
    None
}

// ============================================================================
// Extended Dependence Analysis
// ============================================================================

/// A fully-qualified dependence between two memory accesses including
/// distance information and vectorization impact.
#[derive(Debug, Clone)]
pub struct QualifiedDependence {
    /// The source access index.
    pub source: usize,
    /// The target access index.
    pub target: usize,
    /// The dependence distance.
    pub distance: DependenceDistance,
    /// Whether this dependence is loop-carried.
    pub is_loop_carried: bool,
    /// Whether this dependence prevents vectorization.
    pub prevents_vectorization: bool,
}

impl LoopAccessInfo {
    /// Check if a dependence is loop-carried.
    ///
    /// A loop-carried dependence occurs when the same memory location
    /// is accessed in different iterations. This is safe for vectorization
    /// only if the distance is large enough.
    pub fn is_loop_carried(&self, dep: &MemoryDep, _dist: &DependenceDistance) -> bool {
        dep.dep_type != DepType::NoDep && dep.dep_type != DepType::RAR
    }

    /// Determine the minimum safe vectorization factor based on dependence distances.
    pub fn compute_safe_vf(&self, deps: &[(usize, usize, DependenceDistance)]) -> u32 {
        let mut max_safe_vf = 64u32; // Start with a generous max.

        for &(_, _, ref dist) in deps {
            if dist.dep_type == DepType::NoDep || dist.dep_type == DepType::RAR {
                continue;
            }

            // For loop-carried dependences, the VF must be <= distance.
            if dist.min_distance > 0 {
                let safe_vf = dist.min_distance as u32;
                if safe_vf < max_safe_vf {
                    max_safe_vf = safe_vf;
                }
            } else {
                // Unknown or zero distance prevents vectorization.
                return 1;
            }
        }

        max_safe_vf
    }

    /// Analyze which accesses are safe for interleaved access.
    ///
    /// Interleaved access (stride > 1) requires that accesses to the
    /// same location are at least `stride * VF` apart.
    pub fn can_interleave_access(&self, access: &ValueRef, stride: i64, vf: u32) -> bool {
        if stride == 0 {
            return false;
        }

        let distance_needed = stride.abs() * vf as i64;

        // Check all dependences involving this access.
        for dep in &self.dependences {
            let is_involved = dep.src.borrow().vid == access.borrow().vid
                || dep.dst.borrow().vid == access.borrow().vid;

            if is_involved && dep.dep_type != DepType::NoDep {
                // Need to ensure the distance is sufficient.
                let dist = self.get_dependence_distance(&dep.src, &dep.dst);
                if dist.min_distance.abs() < distance_needed {
                    return false;
                }
            }
        }

        true
    }
}

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

#[cfg(test)]
mod tests {
    use super::*;
    use llvm_native_core::analysis::LoopInfo;
    use llvm_native_core::scalar_evolution::ScalarEvolution;
    use llvm_native_core::types::Type;
    use llvm_native_core::value::{valref, Value};

    fn make_test_function() -> ValueRef {
        valref(Value::new(Type::void()))
    }

    fn make_test_loop() -> LoopInfo {
        let func = make_test_function();
        LoopInfo {
            header: func.clone(),
            blocks: vec![func.clone()],
            exits: vec![],
            latch: None,
            preheader: None,
            depth: 0,
            parent_loop: None,
            is_simplified: false,
            trip_count: Some(100),
        }
    }

    #[test]
    fn test_dep_type_is_safe() {
        assert!(DepType::NoDep.is_safe_for_vectorization());
        assert!(DepType::RAR.is_safe_for_vectorization());
        assert!(!DepType::RAW.is_safe_for_vectorization());
    }

    #[test]
    fn test_loop_access_info_new() {
        let li = make_test_loop();
        let func = make_test_function();
        let scev = ScalarEvolution::new(&func);
        let lai = LoopAccessInfo::new(&li, &scev);
        assert!(lai.num_dependences() >= 0);
    }

    #[test]
    fn test_can_vectorize_empty_loop() {
        let li = make_test_loop();
        let func = make_test_function();
        let scev = ScalarEvolution::new(&func);
        let lai = LoopAccessInfo::new(&li, &scev);
        // The loop has no real blocks with memory accesses.
        // Vectorizability depends on whether the analysis found any barriers.
        // This test just exercises the constructor and query path.
        let _ = lai.can_vectorize();
    }

    #[test]
    fn test_get_stride_info_unknown() {
        let li = make_test_loop();
        let func = make_test_function();
        let scev = ScalarEvolution::new(&func);
        let lai = LoopAccessInfo::new(&li, &scev);
        let (stride, is_strided) = lai.get_stride_info(&func);
        assert_eq!(stride, 0);
        assert!(!is_strided);
    }
}