llvm-native-core-ext 0.1.0

//! Loop Interchange — swaps the order of nested loops to improve
//! cache locality and enable vectorization of inner loops.
//! Clean-room behavioral reconstruction.
//!
//! @llvm_behavior: Loop interchange (also called loop permutation)
//! reorders a loop nest by swapping an outer loop with an inner loop.
//! The primary goal is to improve cache locality: by making the loop
//! that accesses memory with stride-1 the innermost loop, we maximize
//! spatial locality and enable vectorization.
//!
//! Example transformation:
//! ```c
//! // Before (poor locality: inner loop strides through columns)
//! for (i = 0; i < N; i++)
//!   for (j = 0; j < M; j++)
//!     A[i][j] = B[i][j];  // A[i][j] has stride M
//!
//! // After interchange (good locality: inner loop accesses contiguously)
//! for (j = 0; j < M; j++)
//!   for (i = 0; i < N; i++)
//!     A[i][j] = B[i][j];  // Now A[i][j] accessed sequentially in inner loop
//! ```
//!
//! Legality conditions:
//! 1. Both loops must be perfectly nested (no code between them)
//! 2. No dependence that would be reversed by the interchange
//! 3. The loop bounds must be independent (no outer loop bound depends
//!    on the inner loop index)
//!
//! Profitability heuristics:
//! 1. Innermost loop should have stride-1 memory access
//! 2. Outer loop should be parallelizable (no carried dependencies)
//! 3. Cache line utilization should improve
//! 4. Vectorization should be enabled by the interchange

use llvm_native_core::analysis::LoopInfo;
use llvm_native_core::opcode::Opcode;
use llvm_native_core::value::{SubclassKind, ValueRef};
use std::collections::HashMap;

// ============================================================================
// Interchange Result
// ============================================================================

/// Result of interchange profitability analysis.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum InterchangeResult {
    /// Interchange is profitable and legal.
    Profitable,
    /// Interchange is legal but not profitable.
    NotProfitable,
    /// Interchange is illegal (would violate dependencies).
    Illegal,
}

// ============================================================================
// Stride Info — Memory access stride in a loop
// ============================================================================

/// Describes the stride of a memory access relative to a loop index.
#[derive(Debug, Clone)]
struct StrideInfo {
    /// Stride value: 1 = sequential, 0 = loop-invariant, >1 = strided
    pub stride: i64,
    /// Whether the access stride is known at compile time.
    pub is_known: bool,
    /// The loop to which this stride is relative.
    pub relative_to_loop: usize,
}

// ============================================================================
// Loop Interchange Pass
// ============================================================================

/// Loop Interchange pass — swaps nested loop order for cache locality.
pub struct LoopInterchange {
    /// Number of loop pairs interchanged.
    pub interchanged: usize,
    /// Maximum depth of loop nests to consider.
    pub max_nest_depth: usize,
    /// Minimum trip count of inner loop to consider interchange.
    pub min_inner_trip_count: u64,
    /// Whether to prefer parallel outer loops.
    pub prefer_parallel_outer: bool,
}

impl LoopInterchange {
    /// Create a new LoopInterchange pass.
    pub fn new() -> Self {
        Self {
            interchanged: 0,
            max_nest_depth: 3,
            min_inner_trip_count: 8,
            prefer_parallel_outer: true,
        }
    }

    /// Run loop interchange on a function.
    ///
    /// Returns the number of loop pairs successfully interchanged.
    pub fn run_on_function(&mut self, func: &ValueRef) -> usize {
        self.interchanged = 0;

        // Find interchangeable loop nests
        let nests = self.find_interchangeable_nests(func);

        for nest in &nests {
            if nest.len() < 2 {
                continue;
            }

            // Try interchanging adjacent pairs in the nest
            for depth in 0..nest.len() - 1 {
                let outer = &nest[depth];
                let inner = &nest[depth + 1];

                let result = self.compute_profitability(outer, inner);
                match result {
                    InterchangeResult::Profitable => {
                        self.interchange(outer, inner, func);
                        self.interchanged += 1;
                    }
                    InterchangeResult::NotProfitable => {
                        // Skip this pair
                    }
                    InterchangeResult::Illegal => {
                        // Can't interchange this nest
                        break;
                    }
                }
            }
        }

        self.interchanged
    }

    // ========================================================================
    // Candidate discovery
    // ========================================================================

    /// Find loop nests that are candidates for interchange.
    ///
    /// Returns a list of loop nests, where each nest is a vector of
    /// LoopInfo from outermost to innermost (perfectly nested).
    fn find_interchangeable_nests(&self, func: &ValueRef) -> Vec<Vec<LoopInfo>> {
        let analysis = llvm_native_core::analysis::LoopAnalysis::compute(func);
        let loops = &analysis.loops;

        let mut nests = Vec::new();

        // Organize loops by nesting: find outer loops that contain inner loops
        for (outer_idx, outer) in loops.iter().enumerate() {
            // Look for a perfectly nested inner loop
            let mut nest = vec![outer.clone()];
            let mut current = outer.clone();

            loop {
                let inner = self.find_inner_loop(loops, &current);
                match inner {
                    Some(inner_loop) => {
                        if nest.len() >= self.max_nest_depth {
                            break;
                        }
                        nest.push(inner_loop.clone());
                        current = inner_loop.clone();
                    }
                    None => break,
                }
            }

            if nest.len() >= 2 {
                nests.push(nest);
            }
        }

        nests
    }

    /// Find a loop that is perfectly nested inside another loop.
    fn find_inner_loop<'a>(&self, loops: &'a [LoopInfo], outer: &LoopInfo) -> Option<&'a LoopInfo> {
        // An inner loop is a loop where:
        // 1. Its header is contained within the outer loop's blocks
        // 2. All its blocks are within the outer loop
        // 3. It's at depth = outer.depth + 1
        // 4. The outer loop has no instructions between header and inner loop
        //    (perfect nesting)

        for inner in loops {
            if inner.depth == outer.depth + 1 {
                // Check that inner's header is in outer's blocks
                let header_in_outer = outer.blocks.iter().any(|b| {
                    let b_name = &b.borrow().name;
                    let h_name = &inner.header.borrow().name;
                    b_name == h_name || Rc::ptr_eq(b, &inner.header)
                });

                if header_in_outer {
                    // Check perfect nesting: the outer loop header should only
                    // contain the inner loop (no independent instructions
                    // between the outer header and inner loop body)
                    if self.is_perfectly_nested(outer, inner) {
                        return Some(inner);
                    }
                }
            }
        }

        None
    }

    /// Check if an inner loop is perfectly nested inside the outer loop.
    ///
    /// Perfect nesting means the outer loop body contains ONLY the inner
    /// loop (no other instructions).
    fn is_perfectly_nested(&self, outer: &LoopInfo, inner: &LoopInfo) -> bool {
        // The outer loop's header should branch directly to the inner loop's
        // preheader or header
        let outer_header = &outer.header;
        let oh = outer_header.borrow();

        let inner_pre_or_header: Vec<&ValueRef> = if let Some(ref pre) = inner.preheader {
            vec![pre, &inner.header]
        } else {
            vec![&inner.header]
        };

        for succ in &oh.successors {
            for candidate in &inner_pre_or_header {
                if Rc::ptr_eq(succ, candidate) {
                    return true;
                }
                // Also check by name
                if succ.borrow().name == candidate.borrow().name {
                    return true;
                }
            }
        }

        // Fallback: if the outer loop's body is entirely the inner loop's blocks
        let inner_blocks: std::collections::HashSet<String> = inner
            .blocks
            .iter()
            .map(|b| b.borrow().name.clone())
            .collect();

        let outer_body_blocks: Vec<&ValueRef> = outer
            .blocks
            .iter()
            .filter(|b| !Rc::ptr_eq(b, outer_header))
            .collect();

        if outer_body_blocks.len() <= inner.blocks.len() + 1 {
            // +1 accounts for potential preheader/latch
            return true;
        }

        // Check that all outer blocks (except header) are in inner loop
        for block in &outer_body_blocks {
            let name = &block.borrow().name;
            if !inner_blocks.contains(name) {
                // This block is part of the outer loop but not the inner loop
                // → not perfectly nested
                return false;
            }
        }

        true
    }

    // ========================================================================
    // Profitability analysis
    // ========================================================================

    /// Compute whether interchanging an outer loop with an inner loop
    /// is profitable.
    pub fn compute_profitability(&self, outer: &LoopInfo, inner: &LoopInfo) -> InterchangeResult {
        // Step 1: Check legality
        if !self.is_legal_to_interchange(outer, inner) {
            return InterchangeResult::Illegal;
        }

        // Step 2: Check profitability
        if !self.is_profitable_to_interchange(outer, inner) {
            return InterchangeResult::NotProfitable;
        }

        InterchangeResult::Profitable
    }

    /// Check if interchanging the two loops is legal.
    fn is_legal_to_interchange(&self, outer: &LoopInfo, inner: &LoopInfo) -> bool {
        // Legality conditions:
        // 1. No dependence direction vector that would be reversed
        // 2. Loop bounds of inner loop do not depend on outer loop index
        //    (or are separable)
        // 3. Both loops have known trip counts

        // Check trip counts
        if outer.trip_count.is_none() || inner.trip_count.is_none() {
            return false;
        }

        // Check for dependencies that would be reversed
        if self.has_reversible_dependence(outer, inner) {
            return false;
        }

        // Check that inner loop's trip count doesn't depend on outer
        if self.inner_trip_depends_on_outer(outer, inner) {
            return false;
        }

        true
    }

    /// Check if interchanging would reverse a dangerous dependence.
    fn has_reversible_dependence(&self, _outer: &LoopInfo, _inner: &LoopInfo) -> bool {
        // For now, assume all dependences are reversible.
        true
    }

    /// Check if the inner loop's trip count depends on the outer loop index.
    fn inner_trip_depends_on_outer(&self, _outer: &LoopInfo, _inner: &LoopInfo) -> bool {
        // For a typical C-style for(i=0; i<N; i++) for(j=0; j<M; j++),
        // the inner trip count (M) does not depend on i.
        // If it does (e.g., triangular loop: for(j=0; j<i; j++)),
        // we can't interchange because the loops are not rectangular.
        false // Simplified: assume rectangular loops
    }

    /// Check if it's profitable to interchange.
    fn is_profitable_to_interchange(&self, outer: &LoopInfo, inner: &LoopInfo) -> bool {
        // Profitability heuristics:
        // 1. Inner loop should benefit from better cache locality
        // 2. Outer loop should be parallelizable after interchange
        // 3. Vectorization should be enabled

        // Check stride patterns: if the inner loop currently has poor
        // stride (non-unit stride) and the outer loop has good stride
        // (unit stride), interchange is profitable.
        let inner_stride = self.estimate_dominant_stride(inner);
        let outer_stride = self.estimate_dominant_stride(outer);

        // If inner has poor locality (stride > 1) and outer has good locality
        if inner_stride > 1 && outer_stride <= 1 {
            return true;
        }

        // If the inner loop is very small (few iterations), interchange
        // might help increase the inner loop trip count for vectorization
        if let Some(inner_tc) = inner.trip_count {
            if inner_tc < 4 {
                // Small inner loop — interchange to make it larger for
                // better vectorization opportunity
                return true;
            }
        }

        // If outer loop is parallel and we prefer parallel outer loops
        if self.prefer_parallel_outer && self.loop_has_no_carried_deps(outer) {
            // Interchanging may make the new outer loop parallel
            return true;
        }

        false
    }

    /// Estimate the dominant memory access stride for a loop.
    fn estimate_dominant_stride(&self, loop_info: &LoopInfo) -> i64 {
        // Walk memory accesses and estimate their stride relative to the
        // loop index. For a simplified model, we check GEP operands.
        let loads = self.collect_loads(loop_info);
        let stores = self.collect_stores(loop_info);

        let mut has_unit_stride = false;
        let mut has_large_stride = false;

        for inst in loads.iter().chain(stores.iter()) {
            let i = inst.borrow();
            // Find the pointer operand
            let ptr = if i.get_opcode() == Some(Opcode::Store) {
                i.operands.get(1)
            } else {
                i.operands.first()
            };

            if let Some(ptr_val) = ptr {
                // If the pointer is a GEP, examine indices for stride patterns
                if ptr_val.borrow().get_opcode() == Some(Opcode::GetElementPtr) {
                    let gep = ptr_val.borrow();
                    // The last GEP index is typically the innermost array index
                    if let Some(last_idx) = gep.operands.last() {
                        // If the last index is a constant 1 or loop-invariant,
                        // it might indicate unit stride
                        let idx_val = &last_idx.borrow();
                        if idx_val.subclass == SubclassKind::Constant {
                            if idx_val.name == "1" || idx_val.name == "0" {
                                has_unit_stride = true;
                            } else {
                                has_large_stride = true;
                            }
                        }
                    }
                }
            }
        }

        if has_unit_stride && !has_large_stride {
            1
        } else if has_large_stride && !has_unit_stride {
            16 // Arbitrary large stride
        } else {
            8 // Unknown, conservative
        }
    }

    /// Check if a loop has no loop-carried dependencies (is parallel).
    fn loop_has_no_carried_deps(&self, _loop_info: &LoopInfo) -> bool {
        // A loop is parallel if no iteration reads a value written by
        // a previous iteration (no RAW loop-carried dependence) and no
        // iteration writes a value read by a previous iteration.
        // Simplified: check for PHI nodes with inter-iteration dependences
        true // Optimistic: assume parallel for now
    }

    // ========================================================================
    // Interchange implementation
    // ========================================================================

    /// Interchange two nested loops.
    ///
    /// Swaps the outer and inner loops in the loop nest:
    /// 1. Swap the loop headers
    /// 2. Adjust the induction variables
    /// 3. Fix up the CFG edges
    /// 4. Update PHI nodes
    /// 5. Update the preheader relationships
    pub fn interchange(&mut self, outer: &LoopInfo, inner: &LoopInfo, _func: &ValueRef) {
        // Algorithm for loop interchange:
        // 1. Save the original loop structure
        // 2. Swap the iteration spaces:
        //    - New outer loop = old inner loop
        //    - New inner loop = old outer loop
        // 3. Move the loop bodies:
        //    - New outer loop body = new inner loop (the old outer loop)
        // 4. Update induction variables:
        //    - Old outer IV → new inner IV
        //    - Old inner IV → new outer IV
        // 5. Fix up branch targets and PHI nodes
        // 6. Update loop info metadata

        let _ = outer;
        let _ = inner;

        // In a full implementation:
        // - Create a new preheader for the new outer (old inner) loop
        // - Move the old outer loop body inside the old inner loop
        // - Update the GEP indices and memory access patterns
        // - The induction variable update in the latch must be adjusted
    }

    // ========================================================================
    // Analysis helpers
    // ========================================================================

    /// Collect all store instructions in a loop.
    fn collect_stores(&self, loop_info: &LoopInfo) -> Vec<ValueRef> {
        let mut stores = Vec::new();
        for block in &loop_info.blocks {
            let bb = block.borrow();
            for inst in &bb.operands {
                if inst.borrow().get_opcode() == Some(Opcode::Store) {
                    stores.push(inst.clone());
                }
            }
        }
        stores
    }

    /// Collect all load instructions in a loop.
    fn collect_loads(&self, loop_info: &LoopInfo) -> Vec<ValueRef> {
        let mut loads = Vec::new();
        for block in &loop_info.blocks {
            let bb = block.borrow();
            for inst in &bb.operands {
                if inst.borrow().get_opcode() == Some(Opcode::Load) {
                    loads.push(inst.clone());
                }
            }
        }
        loads
    }

    /// Check if instruction A dominates instruction B.
    fn instruction_dominates(&self, a: &ValueRef, b: &ValueRef) -> bool {
        let a_vid = a.borrow().vid;
        let b_vid = b.borrow().vid;
        // Simplified: instructions in the same block — earlier vid dominates
        // later vid within the same block
        a_vid < b_vid
    }

    /// Conservative may-alias check.
    fn may_alias(&self, a: &ValueRef, b: &ValueRef) -> bool {
        let inst_a = a.borrow();
        let inst_b = b.borrow();

        if inst_a.operands.is_empty() || inst_b.operands.is_empty() {
            return true;
        }

        let ptr_a = if inst_a.get_opcode() == Some(Opcode::Store) {
            inst_a.operands.get(1)
        } else {
            inst_a.operands.first()
        };

        let ptr_b = if inst_b.get_opcode() == Some(Opcode::Store) {
            inst_b.operands.get(1)
        } else {
            inst_b.operands.first()
        };

        match (ptr_a, ptr_b) {
            (Some(pa), Some(pb)) => {
                let pa_name = &pa.borrow().name;
                let pb_name = &pb.borrow().name;
                if !pa_name.is_empty()
                    && !pb_name.is_empty()
                    && pa_name != pb_name
                    && pa.borrow().get_opcode() == Some(Opcode::Alloca)
                    && pb.borrow().get_opcode() == Some(Opcode::Alloca)
                {
                    return false;
                }
                true
            }
            _ => true,
        }
    }
}

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

// ============================================================================
// Interchange Permutation Selection with SCEV-Based Analysis
// ============================================================================

/// A candidate permutation for loop interchange.
#[derive(Debug, Clone)]
pub struct InterchangePermutation {
    /// The new loop order: indices into the original nest.
    pub perm: Vec<usize>,
    /// Estimated cache line stride improvement.
    pub stride_improvement: i64,
    /// Whether this permutation enables vectorization.
    pub enables_vectorization: bool,
    /// Estimated speedup factor.
    pub estimated_speedup: f64,
}

/// SCEV-based accessibility analysis for interchange.
#[derive(Debug, Clone)]
pub struct SCEVAccessInfo {
    /// For each loop level: the memory stride of the dominant access.
    pub strides: Vec<i64>,
    /// Whether each level has contiguous access.
    pub has_contiguous: Vec<bool>,
    /// The dominant (most frequent) access pattern per level.
    pub access_count: Vec<usize>,
}

impl LoopInterchange {
    /// Select the best interchange permutation using SCEV-based analysis.
    ///
    /// The goal is to find a permutation that:
    /// 1. Makes the innermost loop access memory contiguously
    /// 2. Does not introduce forward dependencies
    /// 3. Maximizes cache line utilization
    pub fn select_interchange_permutation(
        &self,
        outer_loop: &LoopInfo,
        inner_loop: &LoopInfo,
        nest_depth: usize,
    ) -> Option<InterchangePermutation> {
        if nest_depth < 2 {
            return None;
        }

        // Compute SCEV-based access info for each loop level.
        let access_info = self.compute_scev_access_info(&[outer_loop.clone(), inner_loop.clone()]);

        // Current order: [outer, inner].
        // Desired: inner loop should have stride-1 (contiguous) access.
        let current_inner_stride = access_info.strides.get(1).copied().unwrap_or(0);

        // If the inner loop already has contiguous access, no interchange needed.
        if access_info.has_contiguous.get(1).copied().unwrap_or(false) {
            return None;
        }

        // If the outer loop has contiguous access, interchange is beneficial.
        if access_info.has_contiguous.get(0).copied().unwrap_or(false) {
            let improvement = (current_inner_stride - 1).abs().max(1);

            return Some(InterchangePermutation {
                perm: vec![1, 0], // swap outer and inner
                stride_improvement: improvement,
                enables_vectorization: true,
                estimated_speedup: improvement as f64 * 2.0,
            });
        }

        None
    }

    /// Compute SCEV-based memory access information for a loop nest.
    fn compute_scev_access_info(&self, loop_nest: &[LoopInfo]) -> SCEVAccessInfo {
        let n = loop_nest.len();
        let mut strides = vec![0i64; n];
        let mut has_contiguous = vec![false; n];
        let mut access_count = vec![0usize; n];

        for (level, loop_info) in loop_nest.iter().enumerate() {
            let stores = self.collect_stores(loop_info);
            let loads = self.collect_loads(loop_info);
            let all_accesses: Vec<&ValueRef> = stores.iter().chain(loads.iter()).collect();

            access_count[level] = all_accesses.len();

            // Analyze the dominant stride for this loop level.
            let mut total_stride: i64 = 0;
            let mut strided_accesses = 0;

            for access in &all_accesses {
                if let Some(stride) = self.estimate_stride_for_access(access) {
                    total_stride += stride;
                    strided_accesses += 1;
                }
            }

            if strided_accesses > 0 {
                let avg_stride = total_stride / strided_accesses;
                strides[level] = avg_stride;
                has_contiguous[level] = avg_stride == 1;
            }
        }

        SCEVAccessInfo {
            strides,
            has_contiguous,
            access_count,
        }
    }

    /// Estimate the stride of a memory access relative to a loop level.
    fn estimate_stride_for_access(&self, _access: &ValueRef) -> Option<i64> {
        // In a full implementation, this would:
        // 1. Get the GEP indices for the access
        // 2. Determine which index corresponds to the loop IV
        // 3. Compute the stride as the size * product of other dimensions
        // For simplicity, return a conservative estimate.
        Some(1)
    }

    /// Check dependence legality for a candidate interchange.
    ///
    /// An interchange is legal if no dependence direction is reversed.
    /// A dependence (d1, d2) becomes (d2, d1) after interchange. If the
    /// original dependence was (<, =) and becomes (=, <), it's still legal.
    /// If it was (<, >) and becomes (>, <), it's illegal.
    pub fn check_interchange_dependence_legality(
        &self,
        outer: &LoopInfo,
        inner: &LoopInfo,
    ) -> bool {
        // Collect all memory operations.
        let accesses_outer = self.collect_all_memory_ops(outer);
        let accesses_inner = self.collect_all_memory_ops(inner);

        // Check each pair for reversible dependence.
        for ao in &accesses_outer {
            for ai in &accesses_inner {
                // If they access the same location, check dependence direction.
                if self.may_alias(ao, ai) {
                    // Check dependence direction — simplified check
                    if !self.has_reversible_dependence(outer, inner) {
                        return false;
                    }
                }
            }
        }

        true
    }

    /// Collect all memory operations from a loop (loads + stores).
    fn collect_all_memory_ops(&self, loop_info: &LoopInfo) -> Vec<ValueRef> {
        let mut ops = Vec::new();
        for block in &loop_info.blocks {
            let bb = block.borrow();
            for inst in &bb.operands {
                let opcode = inst.borrow().get_opcode();
                if opcode == Some(Opcode::Load) || opcode == Some(Opcode::Store) {
                    ops.push(inst.clone());
                }
            }
        }
        ops
    }

    /// Adjust loop bounds after interchange.
    ///
    /// When interchanging loops, the loop bounds may need to be adjusted
    /// if the inner loop's bound depends on the outer loop's induction
    /// variable. This function computes the new bounds for each loop.
    pub fn adjust_loop_bounds(
        &self,
        _outer_loop: &LoopInfo,
        _inner_loop: &LoopInfo,
    ) -> Option<(i64, i64, i64, i64)> {
        // outer_start, outer_end, inner_start, inner_end
        // In a simple interchange where bounds are independent:
        // - Outer bounds become inner bounds (swapped)
        // - Inner bounds become outer bounds (swapped)

        // The actual bounds depend on the specific loop structure.
        None
    }

    /// Run loop interchange with profitability analysis.
    pub fn run_with_profitability(&mut self, func: &ValueRef) -> usize {
        self.interchanged = 0;
        let nests = self.find_interchangeable_nests(func);

        for (outer_idx, _) in nests.iter().enumerate() {
            // For each nest, try to find an inner loop to interchange with.
            for (inner_idx, _) in nests.iter().enumerate() {
                if outer_idx == inner_idx {
                    continue;
                }

                let outer_nest = &nests[outer_idx];
                let inner_nest = &nests[inner_idx];

                if outer_nest.is_empty() || inner_nest.is_empty() {
                    continue;
                }

                let outer = &outer_nest[0];
                let inner = &inner_nest[0];

                // Check perfect nesting.
                if !self.is_perfectly_nested(outer, inner) {
                    continue;
                }

                // Check legality.
                if !self.check_interchange_dependence_legality(outer, inner) {
                    continue;
                }

                // Check profitability.
                let permutation = self.select_interchange_permutation(outer, inner, 2);

                if let Some(perm) = permutation {
                    if perm.enables_vectorization {
                        self.interchange(outer, inner, func);
                        self.interchanged += 1;
                        break; // one interchange per nest
                    }
                }
            }
        }

        self.interchanged
    }

    /// Compute the cache line stride improvement from interchange.
    ///
    /// Cache lines are typically 64 bytes. If the innermost loop
    /// accesses memory with stride S, each cache line contains 64/S
    /// useful elements. By making S=1 (contiguous), we use all 64 bytes.
    pub fn compute_cache_line_improvement(&self, current_stride: i64, new_stride: i64) -> f64 {
        if current_stride == 0 || new_stride == 0 {
            return 1.0;
        }

        let cache_line_size: i64 = 64; // typical cache line
        let current_utilization = cache_line_size / current_stride.abs();
        let new_utilization = cache_line_size / new_stride.abs();

        new_utilization as f64 / current_utilization.max(1) as f64
    }
}

// ============================================================================
// Advanced Loop Interchange Analysis
// ============================================================================

/// Detailed dependence direction vector for interchange legality.
#[derive(Debug, Clone)]
pub struct DependenceDirection {
    /// Direction for the outer loop: -1 (negative), 0 (=), 1 (positive), * (unknown).
    pub outer_direction: i8,
    /// Direction for the inner loop.
    pub inner_direction: i8,
}

impl DependenceDirection {
    pub fn new(outer: i8, inner: i8) -> Self {
        DependenceDirection {
            outer_direction: outer,
            inner_direction: inner,
        }
    }

    /// Check if this direction is legal after interchange.
    pub fn is_legal_after_interchange(&self) -> bool {
        // After interchange, (d1, d2) becomes (d2, d1).
        // Legal if the new (inner, outer) direction is lexicographically positive.
        // (>, *) and (*, >) are NOT legal.
        // (<, *) and (*, <) are legal.
        // (=, <) becomes (<, =) which is legal.
        // (<, >) becomes (>, <) which is NOT legal.

        let new_outer = self.inner_direction;
        let new_inner = self.outer_direction;

        // If the new outermost direction is negative, it's illegal.
        if new_outer > 0 {
            return false;
        }

        // If both are positive, illegal.
        new_outer <= 0 || new_inner <= 0
    }
}

impl LoopInterchange {
    /// Analyze dependence directions between two loops.
    pub fn analyze_dependence_direction(
        &self,
        outer: &LoopInfo,
        inner: &LoopInfo,
    ) -> Vec<DependenceDirection> {
        let mut directions = Vec::new();

        let writes_outer = self.collect_stores(outer);
        let reads_inner = self.collect_loads(inner);

        for wo in &writes_outer {
            for ri in &reads_inner {
                if self.may_alias(wo, ri) {
                    // Conservative: assume unknown direction.
                    directions.push(DependenceDirection::new(0, 0));
                }
            }
        }

        directions
    }

    /// Estimate the speedup from interchange based on cache line utilization.
    pub fn estimate_speedup(
        &self,
        current_inner_stride: i64,
        cache_line_size: usize,
        element_size: usize,
    ) -> f64 {
        if element_size == 0 {
            return 1.0;
        }

        let elements_per_line = cache_line_size / element_size;

        // Current: only 1 out of `stride` elements per cache line is used.
        let current_utilization = 1.0 / current_inner_stride.abs().max(1) as f64;

        // After interchange: all elements in cache line are used.
        let new_utilization = 1.0;

        new_utilization / current_utilization.max(0.01)
    }

    /// Print the current loop nest structure for debugging.
    pub fn dump_nest(&self, loops: &[LoopInfo]) -> String {
        let mut out = String::new();
        for (i, l) in loops.iter().enumerate() {
            let indent = "  ".repeat(i);
            out.push_str(&format!(
                "{}Loop {} at depth {}: {} blocks, {} trip_count",
                indent,
                i,
                l.depth,
                l.blocks.len(),
                l.trip_count.unwrap_or(0)
            ));
            out.push('\n');
        }
        out
    }
}

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

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

    fn make_loop_info(header: ValueRef, depth: u32, trip_count: u64) -> LoopInfo {
        LoopInfo {
            header,
            blocks: Vec::new(),
            exits: Vec::new(),
            latch: None,
            preheader: None,
            depth,
            parent_loop: None,
            is_simplified: false,
            trip_count: Some(trip_count),
        }
    }

    #[test]
    fn test_interchange_result_equality() {
        assert_eq!(InterchangeResult::Profitable, InterchangeResult::Profitable);
        assert_ne!(
            InterchangeResult::Profitable,
            InterchangeResult::NotProfitable
        );
        assert_ne!(InterchangeResult::Profitable, InterchangeResult::Illegal);
    }

    #[test]
    fn test_loop_interchange_new() {
        let li = LoopInterchange::new();
        assert_eq!(li.interchanged, 0);
        assert_eq!(li.max_nest_depth, 3);
        assert_eq!(li.min_inner_trip_count, 8);
        assert!(li.prefer_parallel_outer);
    }

    #[test]
    fn test_default() {
        let li = LoopInterchange::default();
        assert_eq!(li.max_nest_depth, 3);
    }

    #[test]
    fn test_compute_profitability_no_trip_count() {
        let li = LoopInterchange::new();
        let h1 = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::label())
                .with_subclass(SubclassKind::BasicBlock),
        );
        let h2 = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::label())
                .with_subclass(SubclassKind::BasicBlock),
        );

        let outer = make_loop_info(h1, 0, 10);
        let mut inner = make_loop_info(h2, 1, 0);
        inner.trip_count = None; // Unknown trip count

        let result = li.compute_profitability(&outer, &inner);
        assert_eq!(result, InterchangeResult::Illegal);
    }

    #[test]
    fn test_compute_profitability_both_known() {
        let li = LoopInterchange::new();
        let h1 = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::label())
                .with_subclass(SubclassKind::BasicBlock),
        );
        let h2 = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::label())
                .with_subclass(SubclassKind::BasicBlock),
        );

        let outer = make_loop_info(h1, 0, 100);
        let inner = make_loop_info(h2, 1, 10);

        let result = li.compute_profitability(&outer, &inner);
        // No reversible deps, trip counts known → at least legal
        assert!(result != InterchangeResult::Illegal);
    }

    #[test]
    fn test_find_nests_no_loops() {
        let li = LoopInterchange::new();
        let func = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::void())
                .with_subclass(SubclassKind::Function),
        );
        let nests = li.find_interchangeable_nests(&func);
        assert!(nests.is_empty());
    }

    #[test]
    fn test_run_on_function_no_loops() {
        let mut li = LoopInterchange::new();
        let func = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::void())
                .with_subclass(SubclassKind::Function),
        );
        let count = li.run_on_function(&func);
        assert_eq!(count, 0);
    }

    #[test]
    fn test_collect_stores_empty() {
        let li = LoopInterchange::new();
        let h = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::label())
                .with_subclass(SubclassKind::BasicBlock),
        );
        let info = make_loop_info(h, 0, 10);
        let stores = li.collect_stores(&info);
        assert!(stores.is_empty());
    }

    #[test]
    fn test_collect_stores_with_store() {
        let li = LoopInterchange::new();
        let bb = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::label())
                .with_subclass(SubclassKind::BasicBlock),
        );
        let store = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::void())
                .with_subclass(SubclassKind::Instruction),
        );
        store.borrow_mut().opcode = Some(Opcode::Store);
        bb.borrow_mut().operands.push(store);

        let header = bb.clone();
        let info = LoopInfo {
            header,
            blocks: vec![bb],
            exits: Vec::new(),
            latch: None,
            preheader: None,
            depth: 0,
            parent_loop: None,
            is_simplified: false,
            trip_count: Some(10),
        };
        let stores = li.collect_stores(&info);
        assert_eq!(stores.len(), 1);
    }

    #[test]
    fn test_instruction_dominates() {
        let li = LoopInterchange::new();
        let a = valref(llvm_native_core::value::Value::new(llvm_native_core::types::Type::i32()));
        let b = valref(llvm_native_core::value::Value::new(llvm_native_core::types::Type::i32()));
        a.borrow_mut().vid = 1;
        b.borrow_mut().vid = 5;
        assert!(li.instruction_dominates(&a, &b));
        assert!(!li.instruction_dominates(&b, &a));
    }

    #[test]
    fn test_inner_trip_depends_on_outer() {
        let li = LoopInterchange::new();
        let h = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::label())
                .with_subclass(SubclassKind::BasicBlock),
        );
        let outer = make_loop_info(h.clone(), 0, 10);
        let inner = make_loop_info(h, 1, 5);
        // Simplified implementation always returns false
        assert!(!li.inner_trip_depends_on_outer(&outer, &inner));
    }

    #[test]
    fn test_estimate_dominant_stride_empty() {
        let li = LoopInterchange::new();
        let h = valref(
            llvm_native_core::value::Value::new(llvm_native_core::types::Type::label())
                .with_subclass(SubclassKind::BasicBlock),
        );
        let info = make_loop_info(h, 0, 10);
        let stride = li.estimate_dominant_stride(&info);
        // No memory ops → stride is whatever default
        assert!(stride >= 1 || stride == 8);
    }

    #[test]
    fn test_prefer_parallel_flag() {
        let mut li = LoopInterchange::new();
        assert!(li.prefer_parallel_outer);
        li.prefer_parallel_outer = false;
        assert!(!li.prefer_parallel_outer);
    }
}

use std::collections::HashSet;
use std::rc::Rc;