llvm-native-core 0.1.4

//! X86 Alias Analysis — complete alias analysis for the X86/X86-64 target
//! backend with all standard LLVM alias analysis algorithms.
//! Phase 10 — LLVM.TARGET.X86.1 Court.
//!
//! Clean-room behavioral reconstruction from:
//! - LLVM Language Reference Manual (aliasing rules, TBAA metadata,
//!   scoped noalias, alias.scope, noalias metadata)
//! - "Pointer Analysis", Andersen 1994; "Context-Free Language Reachability",
//!   Reps et al. 1998; "Efficient Field-Sensitive Pointer Analysis for C",
//!   Pearce et al. 2007
//! - "Type-Based Alias Analysis", Diwan et al. 1998
//! - "Scalar Evolution — A Framework for Analyzing and Transforming
//!   Loop Induction Variables", van Engelen 2001
//! - "Memory SSA — A Unified Framework for Sparse Memory Data-Flow
//!   Analysis", Chow et al. 1996; "Practical Improvements to the
//!   Construction and Destruction of Static Single Assignment Form",
//!   Briggs et al. 1998
//! - Intel® 64 and IA-32 Architectures Software Developer's Manual
//!
//! Zero LLVM source code consultation. All behavior reconstructed from
//! published specifications and black-box oracle interrogation.
//!
//! # Module organization
//!
//! - `X86AliasAnalysis` — top-level orchestration of all AA analyses
//! - `X86BasicAA` — type-based and GEP-based disambiguation
//! - `X86CFLAA` — Andersen's-style context-free language pointer analysis
//! - `X86SCEVAA` — SCEV-based alias analysis for loop induction variables
//! - `X86GlobalsModRef` — global/mod/ref analysis for globals and functions
//! - `X86TypeBasedAA` — TBAA metadata-based alias analysis
//! - `X86ScopedNoAliasAA` — scoped noalias metadata analysis
//! - `X86MemorySSA` — MemorySSA construction, optimization, and clobber walking
//! - `X86MemDep` — memory dependence analysis with query caching
//! - Alias sets, points-to sets, mod/ref tracking

use std::cmp::min;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use std::fmt;
use std::rc::Rc;

// ============================================================================
// Constants
// ============================================================================

/// Maximum number of nodes in a CFL graph before we switch to sparse mode.
const X86_CFL_MAX_NODES_SPARSE: usize = 4096;

/// Maximum depth for recursive alias queries before falling back to MayAlias.
const X86_ALIAS_MAX_RECURSION_DEPTH: usize = 20;

/// Maximum number of pointers tracked in a single points-to set.
const X86_MAX_POINTS_TO_SET: usize = 512;

/// Maximum size for a function's alias sets map.
const X86_MAX_ALIAS_SETS: usize = 1024;

/// Default SCEV induction variable max iterations for analysis.
const X86_SCEV_MAX_BACKEDGE_TAKEN_COUNT: u64 = 1_000_000;

/// Maximum MemorySSA walk depth for clobber chains.
const X86_MEMSSA_MAX_WALK_DEPTH: usize = 100;

/// Batch query size threshold (queries per function before batch optimization).
const X86_BATCH_QUERY_THRESHOLD: usize = 32;

/// Cache size for memory dependence queries.
const X86_MEMDEP_CACHE_SIZE: usize = 4096;

// ============================================================================
// X86Opcode — minimal opcode representation for memory operations
// ============================================================================

/// Opcodes relevant to alias analysis and memory dependence.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum X86Opcode {
    // Terminator instructions
    Ret,
    Br,
    Switch,
    IndirectBr,
    Invoke,
    CallBr,
    Unreachable,

    // Memory operations
    Alloca,
    Load,
    Store,
    GetElementPtr,
    Fence,
    AtomicCmpXchg,
    AtomicRMW,

    // Casts
    BitCast,
    IntToPtr,
    PtrToInt,
    Trunc,
    ZExt,
    SExt,
    FPTrunc,
    FPExt,
    FPToUI,
    FPToSI,
    UIToFP,
    SIToFP,
    AddrSpaceCast,

    // Binary / arithmetic
    Add,
    Sub,
    Mul,
    UDiv,
    SDiv,
    URem,
    SRem,
    And,
    Or,
    Xor,
    Shl,
    LShr,
    AShr,

    // Other
    Phi,
    Select,
    Call,
    ExtractValue,
    InsertValue,
    ExtractElement,
    InsertElement,
    ShuffleVector,

    // For unknown/unrecognized
    Unknown,
}

impl fmt::Display for X86Opcode {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{:?}", self)
    }
}

// ============================================================================
// AliasResult, ModRefInfo — core enum types used throughout
// ============================================================================

/// The result of an alias query between two memory locations.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum AliasResult {
    /// The two memory locations definitely do not overlap.
    NoAlias = 0,
    /// The two memory locations may overlap (conservative default).
    MayAlias = 1,
    /// The two memory locations partially overlap.
    PartialAlias = 2,
    /// The two memory locations definitely refer to the same location.
    MustAlias = 3,
}

impl fmt::Display for AliasResult {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            AliasResult::NoAlias => write!(f, "NoAlias"),
            AliasResult::MayAlias => write!(f, "MayAlias"),
            AliasResult::PartialAlias => write!(f, "PartialAlias"),
            AliasResult::MustAlias => write!(f, "MustAlias"),
        }
    }
}

impl AliasResult {
    /// Join (lattice meet) of two AliasResults: returns the more precise result.
    pub fn meet(a: AliasResult, b: AliasResult) -> AliasResult {
        use AliasResult::*;
        match (a, b) {
            (NoAlias, _) => NoAlias,
            (_, NoAlias) => NoAlias,
            (MustAlias, _) => b,
            (_, MustAlias) => a,
            (PartialAlias, PartialAlias) => PartialAlias,
            (MayAlias, _) | (_, MayAlias) => MayAlias,
            _ => MayAlias,
        }
    }

    /// The top element of the alias lattice (most conservative).
    pub fn top() -> Self {
        AliasResult::MayAlias
    }

    /// The bottom element of the alias lattice (least conservative).
    pub fn bottom() -> Self {
        AliasResult::NoAlias
    }

    /// Returns true if this result indicates no aliasing.
    pub fn is_no_alias(&self) -> bool {
        matches!(self, AliasResult::NoAlias)
    }

    /// Returns true if this result indicates must-alias.
    pub fn is_must_alias(&self) -> bool {
        matches!(self, AliasResult::MustAlias)
    }
}

/// Describes whether a call instruction modifies and/or references memory.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum ModRefInfo {
    /// Does not access memory at all.
    NoModRef = 0,
    /// Only reads memory.
    Ref = 1,
    /// Only writes memory (no read).
    Mod = 2,
    /// Both reads and writes memory.
    ModRef = 3,
}

impl fmt::Display for ModRefInfo {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            ModRefInfo::NoModRef => write!(f, "NoModRef"),
            ModRefInfo::Ref => write!(f, "Ref"),
            ModRefInfo::Mod => write!(f, "Mod"),
            ModRefInfo::ModRef => write!(f, "ModRef"),
        }
    }
}

impl ModRefInfo {
    /// Returns true if this ModRefInfo includes a read.
    pub fn does_ref(&self) -> bool {
        matches!(self, ModRefInfo::Ref | ModRefInfo::ModRef)
    }

    /// Returns true if this ModRefInfo includes a write.
    pub fn does_mod(&self) -> bool {
        matches!(self, ModRefInfo::Mod | ModRefInfo::ModRef)
    }

    /// Union (join) two ModRefInfo values.
    pub fn union(a: ModRefInfo, b: ModRefInfo) -> ModRefInfo {
        use ModRefInfo::*;
        match (a, b) {
            (x, NoModRef) | (NoModRef, x) => x,
            (Ref, Ref) => Ref,
            (Mod, Mod) => Mod,
            _ => ModRef,
        }
    }

    /// Meet (intersection) two ModRefInfo values.
    pub fn meet(a: ModRefInfo, b: ModRefInfo) -> ModRefInfo {
        use ModRefInfo::*;
        match (a, b) {
            (ModRef, x) | (x, ModRef) => x,
            (NoModRef, _) | (_, NoModRef) => NoModRef,
            (Ref, Mod) | (Mod, Ref) => NoModRef,
            _ => a,
        }
    }

    /// Top element of the ModRef lattice.
    pub fn top() -> Self {
        ModRefInfo::ModRef
    }

    /// Bottom element of the ModRef lattice.
    pub fn bottom() -> Self {
        ModRefInfo::NoModRef
    }

    /// Clear the Mod bit.
    pub fn clear_mod(&mut self) {
        *self = match *self {
            ModRefInfo::ModRef => ModRefInfo::Ref,
            ModRefInfo::Mod => ModRefInfo::NoModRef,
            other => other,
        };
    }

    /// Clear the Ref bit.
    pub fn clear_ref(&mut self) {
        *self = match *self {
            ModRefInfo::ModRef => ModRefInfo::Mod,
            ModRefInfo::Ref => ModRefInfo::NoModRef,
            other => other,
        };
    }
}

// ============================================================================
// MemoryLocation — describes a memory access location
// ============================================================================

/// Describes a memory access for alias analysis queries.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct MemoryLocation {
    /// The pointer value through which memory is accessed.
    pub ptr: u64,
    /// The size in bytes of the memory access.
    pub size: u64,
    /// Optional TBAA metadata tag string.
    pub tbaa_tag: Option<String>,
    /// Optional scoped noalias domain.
    pub noalias_domain: Option<String>,
    /// Optional scoped noalias scope set.
    pub noalias_scopes: Vec<String>,
    /// Whether this location represents a known-size access.
    pub has_known_size: bool,
}

impl MemoryLocation {
    /// Create a new memory location.
    pub fn new(ptr: u64, size: u64) -> Self {
        MemoryLocation {
            ptr,
            size,
            tbaa_tag: None,
            noalias_domain: None,
            noalias_scopes: Vec::new(),
            has_known_size: size > 0,
        }
    }

    /// Create a memory location with TBAA metadata.
    pub fn with_tbaa(mut self, tag: String) -> Self {
        self.tbaa_tag = Some(tag);
        self
    }

    /// Create a memory location with scoped noalias metadata.
    pub fn with_scoped_noalias(mut self, domain: String, scopes: Vec<String>) -> Self {
        self.noalias_domain = Some(domain);
        self.noalias_scopes = scopes;
        self
    }

    /// Returns true if this location has a TBAA tag.
    pub fn has_tbaa(&self) -> bool {
        self.tbaa_tag.is_some()
    }

    /// Returns true if this location has scoped noalias metadata.
    pub fn has_scoped_noalias(&self) -> bool {
        self.noalias_domain.is_some() && !self.noalias_scopes.is_empty()
    }

    /// Returns true if this is an unknown-size access.
    pub fn is_unknown_size(&self) -> bool {
        !self.has_known_size
    }
}

// ============================================================================
// PointsToSet — points-to information for a pointer value
// ============================================================================

/// Represents the set of memory objects a pointer may point to.
#[derive(Debug, Clone, Default)]
pub struct PointsToSet {
    /// The set of memory objects this pointer may point to.
    pub objects: HashSet<u64>,
    /// Whether this points-to set includes the null pointer.
    pub includes_null: bool,
    /// Whether this points-to set includes escaped/unknown locations.
    pub includes_unknown: bool,
    /// Whether this pointer cannot alias with any other pointer.
    pub is_noalias: bool,
}

impl PointsToSet {
    /// Create an empty points-to set.
    pub fn empty() -> Self {
        PointsToSet {
            objects: HashSet::new(),
            includes_null: false,
            includes_unknown: false,
            is_noalias: false,
        }
    }

    /// Create a points-to set representing the unknown set.
    pub fn unknown() -> Self {
        PointsToSet {
            objects: HashSet::new(),
            includes_null: true,
            includes_unknown: true,
            is_noalias: false,
        }
    }

    /// Create a points-to set for a single object.
    pub fn singleton(obj: u64) -> Self {
        let mut objects = HashSet::new();
        objects.insert(obj);
        PointsToSet {
            objects,
            includes_null: false,
            includes_unknown: false,
            is_noalias: false,
        }
    }

    /// Create a points-to set that represents a noalias pointer.
    pub fn noalias() -> Self {
        PointsToSet {
            objects: HashSet::new(),
            includes_null: false,
            includes_unknown: false,
            is_noalias: true,
        }
    }

    /// Union two points-to sets.
    pub fn union_with(&mut self, other: &PointsToSet) {
        if other.is_noalias {
            return;
        }
        if self.is_noalias {
            self.is_noalias = false;
        }
        self.includes_null |= other.includes_null;
        self.includes_unknown |= other.includes_unknown;
        if self.objects.len() + other.objects.len() <= X86_MAX_POINTS_TO_SET {
            self.objects.extend(&other.objects);
        } else {
            self.includes_unknown = true;
            self.objects.clear();
        }
    }

    /// Returns true if this points-to set may alias with another.
    pub fn may_alias(&self, other: &PointsToSet) -> bool {
        if self.is_noalias || other.is_noalias {
            return false;
        }
        if self.includes_unknown || other.includes_unknown {
            return true;
        }
        if self.includes_null && other.includes_null {
            return true;
        }
        !self.objects.is_disjoint(&other.objects)
    }

    /// Returns the number of concrete objects in this set.
    pub fn len(&self) -> usize {
        self.objects.len()
    }

    /// Returns true if the set is empty (no objects, not unknown).
    pub fn is_empty(&self) -> bool {
        self.objects.is_empty() && !self.includes_unknown && !self.includes_null
    }
}

// ============================================================================
// AliasSet — a set of memory locations that may alias
// ============================================================================

/// Represents a set of memory references that may alias each other.
#[derive(Debug, Clone)]
pub struct AliasSet {
    /// Unique identifier for this alias set.
    pub id: u64,
    /// Set of pointer values in this alias set.
    pub pointers: HashSet<u64>,
    /// Whether this set includes unknown/modref locations.
    pub has_unknown: bool,
    /// Mod/Ref info for this set.
    pub access_type: AliasSetAccess,
    /// Whether any pointer in this set is volatile.
    pub is_volatile: bool,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AliasSetAccess {
    /// Only reads from this set.
    Ref,
    /// Only writes to this set.
    Mod,
    /// Both reads and writes.
    ModRef,
}

impl AliasSet {
    /// Create a new alias set.
    pub fn new(id: u64) -> Self {
        AliasSet {
            id,
            pointers: HashSet::new(),
            has_unknown: false,
            access_type: AliasSetAccess::Ref,
            is_volatile: false,
        }
    }

    /// Add a pointer to this alias set.
    pub fn add_pointer(&mut self, ptr: u64) {
        if self.pointers.len() < X86_MAX_ALIAS_SETS {
            self.pointers.insert(ptr);
        } else {
            self.has_unknown = true;
        }
    }

    /// Merge another alias set into this one.
    pub fn merge(&mut self, other: &AliasSet) {
        self.pointers.extend(&other.pointers);
        self.has_unknown |= other.has_unknown;
        self.is_volatile |= other.is_volatile;
        self.access_type = match (self.access_type, other.access_type) {
            (AliasSetAccess::Ref, AliasSetAccess::Ref) => AliasSetAccess::Ref,
            (AliasSetAccess::Mod, AliasSetAccess::Mod) => AliasSetAccess::Mod,
            _ => AliasSetAccess::ModRef,
        };
    }
}

// ============================================================================
// X86AliasResult — extended alias result with optional explanation
// ============================================================================

/// Extended alias result with diagnostic information.
#[derive(Debug, Clone)]
pub struct X86AliasResult {
    /// The core alias result.
    pub result: AliasResult,
    /// Which analysis produced this result.
    pub source: String,
    /// Optional human-readable explanation.
    pub explanation: Option<String>,
}

impl X86AliasResult {
    pub fn new(result: AliasResult, source: &str) -> Self {
        X86AliasResult {
            result,
            source: source.to_string(),
            explanation: None,
        }
    }

    pub fn with_explanation(mut self, explanation: &str) -> Self {
        self.explanation = Some(explanation.to_string());
        self
    }
}

// ============================================================================
// X86BasicAA — Basic Alias Analysis (type-based + GEP-based)
// ============================================================================

/// Basic Alias Analysis for X86: uses type information, stack/alloca
/// knowledge, GEP decomposition, and global variable disambiguation
/// to resolve aliasing queries.
#[derive(Debug, Clone)]
pub struct X86BasicAA {
    /// Known stack allocations: ptr -> size.
    pub alloca_sizes: HashMap<u64, u64>,
    /// Known global variables: ptr -> size.
    pub global_sizes: HashMap<u64, u64>,
    /// Known global constants (read-only).
    pub global_constants: HashSet<u64>,
    /// Known function entry points.
    pub function_addresses: HashSet<u64>,
    /// GEP base -> known object mapping.
    pub gep_bases: HashMap<u64, u64>,
    /// GEP offset tracking: (ptr, base) -> offset.
    pub gep_offsets: HashMap<u64, (u64, i64)>,
    /// Statistics counter.
    pub stats: X86BasicAAStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86BasicAAStats {
    pub total_queries: u64,
    pub noalias_results: u64,
    pub mustalias_results: u64,
    pub partialalias_results: u64,
    pub mayalias_results: u64,
    pub gep_disambiguations: u64,
    pub type_disambiguations: u64,
}

impl X86BasicAA {
    /// Create a new BasicAA instance.
    pub fn new() -> Self {
        X86BasicAA {
            alloca_sizes: HashMap::new(),
            global_sizes: HashMap::new(),
            global_constants: HashSet::new(),
            function_addresses: HashSet::new(),
            gep_bases: HashMap::new(),
            gep_offsets: HashMap::new(),
            stats: X86BasicAAStats::default(),
        }
    }

    /// Register a stack allocation.
    pub fn register_alloca(&mut self, ptr: u64, size: u64) {
        self.alloca_sizes.insert(ptr, size);
    }

    /// Register a global variable.
    pub fn register_global(&mut self, ptr: u64, size: u64, is_constant: bool) {
        self.global_sizes.insert(ptr, size);
        if is_constant {
            self.global_constants.insert(ptr);
        }
    }

    /// Register a GEP base relationship.
    pub fn register_gep(&mut self, gep_ptr: u64, base: u64, offset: i64) {
        self.gep_bases.insert(gep_ptr, base);
        self.gep_offsets.insert(gep_ptr, (base, offset));
    }

    /// Perform alias analysis between two memory locations.
    pub fn alias(&mut self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        self.stats.total_queries += 1;

        // Same pointer -> MustAlias
        if loc_a.ptr == loc_b.ptr && loc_a.ptr != 0 {
            // Check if offsets/sizes are compatible
            if loc_a.size == loc_b.size || loc_a.size == 0 || loc_b.size == 0 {
                self.stats.mustalias_results += 1;
                return AliasResult::MustAlias;
            }
            self.stats.partialalias_results += 1;
            return AliasResult::PartialAlias;
        }

        // Null/zero pointer -> NoAlias with anything but null
        if loc_a.ptr == 0 || loc_b.ptr == 0 {
            if loc_a.ptr != loc_b.ptr {
                self.stats.noalias_results += 1;
                return AliasResult::NoAlias;
            }
            return AliasResult::MayAlias;
        }

        // Both are distinct allocas -> NoAlias
        if self.alloca_sizes.contains_key(&loc_a.ptr)
            && self.alloca_sizes.contains_key(&loc_b.ptr)
            && loc_a.ptr != loc_b.ptr
        {
            self.stats.noalias_results += 1;
            return AliasResult::NoAlias;
        }

        // Both are distinct globals -> NoAlias (unless one aliases the other)
        if self.global_sizes.contains_key(&loc_a.ptr)
            && self.global_sizes.contains_key(&loc_b.ptr)
            && loc_a.ptr != loc_b.ptr
        {
            self.stats.noalias_results += 1;
            return AliasResult::NoAlias;
        }

        // Alloca vs global that doesn't contain the alloca -> NoAlias (local)
        if (self.alloca_sizes.contains_key(&loc_a.ptr)
            && self.global_sizes.contains_key(&loc_b.ptr))
            || (self.alloca_sizes.contains_key(&loc_b.ptr)
                && self.global_sizes.contains_key(&loc_a.ptr))
        {
            self.stats.noalias_results += 1;
            return AliasResult::NoAlias;
        }

        // GEP-based disambiguation: two GEPs with different base objects
        let base_a = self.resolve_gep_base(loc_a.ptr);
        let base_b = self.resolve_gep_base(loc_b.ptr);
        let offset_a = self.resolve_gep_offset(loc_a.ptr);
        let offset_b = self.resolve_gep_offset(loc_b.ptr);

        if let (Some(ba), Some(bb)) = (base_a, base_b) {
            if ba != bb {
                // Different bases
                self.stats.gep_disambiguations += 1;
                self.stats.noalias_results += 1;
                return AliasResult::NoAlias;
            }
            // Same base, check offsets for partial overlap
            if let (Some(oa), Some(ob)) = (offset_a, offset_b) {
                let size_a = loc_a.size as i64;
                let size_b = loc_b.size as i64;
                if oa == ob && size_a == size_b {
                    self.stats.mustalias_results += 1;
                    return AliasResult::MustAlias;
                }
                // Check for non-overlapping ranges
                if size_a > 0 && size_b > 0 {
                    let end_a = oa + size_a;
                    let end_b = ob + size_b;
                    if end_a <= ob || end_b <= oa {
                        self.stats.noalias_results += 1;
                        return AliasResult::NoAlias;
                    }
                    self.stats.partialalias_results += 1;
                    return AliasResult::PartialAlias;
                }
            }
        }

        // One is a function pointer and the other is not -> NoAlias
        if self.function_addresses.contains(&loc_a.ptr)
            != self.function_addresses.contains(&loc_b.ptr)
        {
            self.stats.noalias_results += 1;
            return AliasResult::NoAlias;
        }

        // Fallback: MayAlias
        self.stats.mayalias_results += 1;
        AliasResult::MayAlias
    }

    /// Resolve the base object of a pointer, following GEP chains.
    fn resolve_gep_base(&self, ptr: u64) -> Option<u64> {
        let mut current = ptr;
        let mut visited = HashSet::new();
        // Walk GEP chain, but limit depth to avoid cycles
        for _ in 0..X86_ALIAS_MAX_RECURSION_DEPTH {
            if visited.contains(&current) {
                break;
            }
            visited.insert(current);
            if self.alloca_sizes.contains_key(&current) || self.global_sizes.contains_key(&current)
            {
                return Some(current);
            }
            match self.gep_bases.get(&current) {
                Some(base) => {
                    current = *base;
                }
                None => break,
            }
        }
        None
    }

    /// Resolve the byte offset of a pointer from its base.
    fn resolve_gep_offset(&self, ptr: u64) -> Option<i64> {
        self.gep_offsets.get(&ptr).map(|(_base, offset)| *offset)
    }

    /// Check if a memory location points to constant memory.
    pub fn points_to_constant_memory(&self, loc: &MemoryLocation) -> bool {
        // Resolve the underlying object
        let base = self.resolve_gep_base(loc.ptr).unwrap_or(loc.ptr);
        self.global_constants.contains(&base)
    }

    /// Get the size of an object at the given base.
    pub fn get_object_size(&self, ptr: u64) -> Option<u64> {
        let base = self.resolve_gep_base(ptr).unwrap_or(ptr);
        self.alloca_sizes
            .get(&base)
            .copied()
            .or_else(|| self.global_sizes.get(&base).copied())
    }

    /// Get statistics.
    pub fn get_stats(&self) -> &X86BasicAAStats {
        &self.stats
    }
}

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

// ============================================================================
// X86CFLAA — Context-Free Language Alias Analysis (Andersen-style)
// ============================================================================

/// CFL-AA (Context-Free Language Alias Analysis) — Andersen's-style
/// inclusion-based pointer analysis formulated as a CFL reachability problem.
///
/// The grammar:
/// - Assign:   p := q   → flows(p, q)
/// - Load:     p := *q  → flows(p, deref(q))
/// - Store:    *p := q  → flows(deref(p), q)
///
/// The analysis collects all assignments, loads, and stores in a function,
/// builds a points-to graph, and resolves queries using CFL reachability.
#[derive(Debug, Clone)]
pub struct X86CFLAA {
    /// Points-to sets: pointer id -> PointsToSet.
    pub points_to: HashMap<u64, PointsToSet>,
    /// Direct assignment edges: (from, to).
    pub assign_edges: Vec<(u64, u64)>,
    /// Load edges: ptr = *base => (ptr, base).
    pub load_edges: Vec<(u64, u64)>,
    /// Store edges: *base = ptr => (base, ptr).
    pub store_edges: Vec<(u64, u64)>,
    /// Reverse assign edges (used during query resolution).
    rev_assign: HashMap<u64, Vec<u64>>,
    /// Dereference cache.
    deref_cache: HashMap<u64, PointsToSet>,
    /// Worklist for fixpoint computation.
    worklist: VecDeque<(u64, u64)>,
    /// Has the analysis been solved?
    pub solved: bool,
    /// Statistics.
    pub stats: X86CFLAAStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86CFLAAStats {
    pub total_nodes: usize,
    pub total_edges: usize,
    pub assign_edges: usize,
    pub load_edges: usize,
    pub store_edges: usize,
    pub iterations_to_fixpoint: u64,
    pub queries_resolved: u64,
    pub noalias_results: u64,
}

impl X86CFLAA {
    /// Create a new CFL-AA instance.
    pub fn new() -> Self {
        X86CFLAA {
            points_to: HashMap::new(),
            assign_edges: Vec::new(),
            load_edges: Vec::new(),
            store_edges: Vec::new(),
            rev_assign: HashMap::new(),
            deref_cache: HashMap::new(),
            worklist: VecDeque::new(),
            solved: false,
            stats: X86CFLAAStats::default(),
        }
    }

    /// Register a pointer node (value that can hold a pointer).
    pub fn register_pointer(&mut self, ptr: u64) {
        self.points_to.entry(ptr).or_insert_with(PointsToSet::empty);
    }

    /// Add a direct assignment: lhs = rhs.
    pub fn add_assign(&mut self, lhs: u64, rhs: u64) {
        self.assign_edges.push((lhs, rhs));
        self.stats.assign_edges += 1;
    }

    /// Add a load: lhs = *rhs.
    pub fn add_load(&mut self, lhs: u64, rhs: u64) {
        self.load_edges.push((lhs, rhs));
        self.stats.load_edges += 1;
    }

    /// Add a store: *lhs = rhs.
    pub fn add_store(&mut self, lhs: u64, rhs: u64) {
        self.store_edges.push((lhs, rhs));
        self.stats.store_edges += 1;
    }

    /// Add a concrete object that a pointer points to.
    pub fn add_points_to(&mut self, ptr: u64, obj: u64) {
        let entry = self.points_to.entry(ptr).or_insert_with(PointsToSet::empty);
        entry.objects.insert(obj);
    }

    /// Mark a pointer as escaped (points to unknown).
    pub fn mark_escaped(&mut self, ptr: u64) {
        let entry = self.points_to.entry(ptr).or_insert_with(PointsToSet::empty);
        entry.includes_unknown = true;
    }

    /// Solve the CFL reachability problem (Andersen-style fixpoint).
    pub fn solve(&mut self) {
        if self.solved {
            return;
        }

        self.stats.total_nodes = self.points_to.len();
        self.stats.total_edges =
            self.assign_edges.len() + self.load_edges.len() + self.store_edges.len();

        // Build reverse assign map
        self.rev_assign.clear();
        for &(from, to) in &self.assign_edges {
            self.rev_assign.entry(to).or_default().push(from);
        }

        // Initialize worklist with all assignments
        self.worklist.clear();
        for &(lhs, rhs) in &self.assign_edges {
            self.worklist.push_back((lhs, rhs));
        }

        // Fixpoint iteration
        let mut iteration = 0u64;
        loop {
            if self.worklist.is_empty() {
                break;
            }
            iteration += 1;
            if iteration > 1_000_000 {
                // Safety bound
                break;
            }

            // Process a batch from the worklist
            let batch_size = min(self.worklist.len(), 64);
            for _ in 0..batch_size {
                if let Some((lhs, rhs)) = self.worklist.pop_front() {
                    self.process_worklist_item(lhs, rhs);
                }
            }
        }

        self.stats.iterations_to_fixpoint = iteration;

        // After fixpoint, propagate load edges
        self.propagate_loads();

        // Invalidate deref cache
        self.deref_cache.clear();

        self.solved = true;
    }

    /// Process a single worklist item: propagate points-to from rhs to lhs.
    fn process_worklist_item(&mut self, lhs: u64, rhs: u64) {
        // We need to propagate rhs's points-to set to lhs.
        // Clone rhs pts to avoid borrow issues.
        let rhs_pts = self
            .points_to
            .get(&rhs)
            .cloned()
            .unwrap_or_else(PointsToSet::empty);
        let lhs_entry = self.points_to.entry(lhs).or_insert_with(PointsToSet::empty);
        let old_len = lhs_entry.objects.len();
        let old_unknown = lhs_entry.includes_unknown;
        let old_null = lhs_entry.includes_null;

        lhs_entry.union_with(&rhs_pts);

        // If lhs changed, propagate to all who have a reverse assignment from lhs
        if lhs_entry.objects.len() != old_len
            || lhs_entry.includes_unknown != old_unknown
            || lhs_entry.includes_null != old_null
        {
            if let Some(rev_list) = self.rev_assign.get(&lhs).cloned() {
                for &target in &rev_list {
                    self.worklist.push_back((target, lhs));
                }
            }

            // Also process store edges: if lhs holds objects, *lhs points to rhs's objects
            for &(store_base, store_val) in &self.store_edges {
                if store_base == lhs {
                    // For *lhs = val, propagate objects from rhs' pts to store_val's pts
                    let store_entry = self
                        .points_to
                        .entry(store_val)
                        .or_insert_with(PointsToSet::empty);
                    store_entry.union_with(&rhs_pts);
                }
            }
        }
    }

    /// Propagate load edges after fixpoint: for each load p = *q,
    /// propagate q's dereferenced points-to to p.
    fn propagate_loads(&mut self) {
        let load_edges: Vec<(u64, u64)> = self.load_edges.iter().copied().collect();
        for (load_target, load_base) in load_edges {
            let deref_pts = self.compute_deref(load_base);
            let target_entry = self
                .points_to
                .entry(load_target)
                .or_insert_with(PointsToSet::empty);
            target_entry.union_with(&deref_pts);
        }
    }

    /// Compute the dereference of a pointer: the set of objects reachable
    /// through the pointer's points-to set.
    fn compute_deref(&mut self, ptr: u64) -> PointsToSet {
        if let Some(cached) = self.deref_cache.get(&ptr) {
            return cached.clone();
        }

        let pts = self
            .points_to
            .get(&ptr)
            .cloned()
            .unwrap_or_else(PointsToSet::empty);
        let mut result = PointsToSet::empty();

        if pts.includes_unknown {
            result.includes_unknown = true;
        }

        // For each object in pts, look up the points-to of that object
        for &obj in &pts.objects {
            if let Some(obj_pts) = self.points_to.get(&obj) {
                result.union_with(obj_pts);
            }
        }

        self.deref_cache.insert(ptr, result.clone());
        result
    }

    /// Query whether two pointers may alias.
    pub fn may_alias(&mut self, ptr_a: u64, ptr_b: u64) -> AliasResult {
        if !self.solved {
            self.solve();
        }

        self.stats.queries_resolved += 1;

        if ptr_a == ptr_b {
            if ptr_a != 0 {
                return AliasResult::MustAlias;
            }
            return AliasResult::NoAlias;
        }

        // Both are concrete pointers -> look up points-to
        let pts_a = self
            .points_to
            .get(&ptr_a)
            .cloned()
            .unwrap_or_else(PointsToSet::empty);
        let pts_b = self
            .points_to
            .get(&ptr_b)
            .cloned()
            .unwrap_or_else(PointsToSet::empty);

        if pts_a.is_noalias || pts_b.is_noalias {
            self.stats.noalias_results += 1;
            return AliasResult::NoAlias;
        }

        if pts_a.may_alias(&pts_b) {
            AliasResult::MayAlias
        } else {
            self.stats.noalias_results += 1;
            AliasResult::NoAlias
        }
    }

    /// Get the points-to set for a pointer.
    pub fn get_points_to(&self, ptr: u64) -> PointsToSet {
        self.points_to
            .get(&ptr)
            .cloned()
            .unwrap_or_else(PointsToSet::empty)
    }

    /// Check if two pointers must alias through their points-to sets.
    pub fn must_alias(&self, ptr_a: u64, ptr_b: u64) -> bool {
        let pts_a = self.get_points_to(ptr_a);
        let pts_b = self.get_points_to(ptr_b);
        if pts_a.objects.len() == 1
            && pts_b.objects.len() == 1
            && !pts_a.includes_unknown
            && !pts_b.includes_unknown
        {
            pts_a.objects == pts_b.objects
        } else {
            false
        }
    }
}

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

// ============================================================================
// X86SCEVAA — SCEV-based Alias Analysis (loop induction variables)
// ============================================================================

/// SCEV (Scalar Evolution) expression node — represents the evolution
/// of a value across loop iterations.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum X86SCEVExpr {
    /// A constant integer.
    Constant(i64),
    /// An unknown/unanalyzable value.
    Unknown,
    /// A loop induction variable with base, step, and loop context.
    AddRec {
        base: Box<X86SCEVExpr>,
        step: Box<X86SCEVExpr>,
        loop_id: u64,
    },
    /// Sum of two SCEVs.
    Add(Box<X86SCEVExpr>, Box<X86SCEVExpr>),
    /// Product of two SCEVs.
    Mul(Box<X86SCEVExpr>, Box<X86SCEVExpr>),
    /// SCEV for a specific value (symbolic).
    SCEVValue(u64),
    /// SCEV zero-extend.
    ZExt(Box<X86SCEVExpr>),
    /// SCEV sign-extend.
    SExt(Box<X86SCEVExpr>),
    /// SCEV truncate.
    Truncate(Box<X86SCEVExpr>),
    /// A SCEV with unknown step count (could be anything).
    CouldNotCompute,
}

impl fmt::Display for X86SCEVExpr {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            X86SCEVExpr::Constant(v) => write!(f, "{}", v),
            X86SCEVExpr::Unknown => write!(f, "unknown"),
            X86SCEVExpr::CouldNotCompute => write!(f, "couldnotcompute"),
            X86SCEVExpr::AddRec {
                base,
                step,
                loop_id,
            } => {
                write!(f, "{{{},+,{}}}<loop_{}>", base, step, loop_id)
            }
            X86SCEVExpr::Add(a, b) => write!(f, "({} + {})", a, b),
            X86SCEVExpr::Mul(a, b) => write!(f, "({} * {})", a, b),
            X86SCEVExpr::SCEVValue(v) => write!(f, "v{}", v),
            X86SCEVExpr::ZExt(e) => write!(f, "(zext {})", e),
            X86SCEVExpr::SExt(e) => write!(f, "(sext {})", e),
            X86SCEVExpr::Truncate(e) => write!(f, "(trunc {})", e),
        }
    }
}

impl X86SCEVExpr {
    /// Create a constant SCEV.
    pub fn constant(v: i64) -> Self {
        X86SCEVExpr::Constant(v)
    }

    /// Create an unknown SCEV.
    pub fn unknown() -> Self {
        X86SCEVExpr::Unknown
    }

    /// Create an add-recurrence SCEV.
    pub fn addrec(base: X86SCEVExpr, step: X86SCEVExpr, loop_id: u64) -> Self {
        X86SCEVExpr::AddRec {
            base: Box::new(base),
            step: Box::new(step),
            loop_id,
        }
    }

    /// Evaluate the SCEV at a given iteration (for add-recurrences).
    pub fn evaluate_at(&self, iteration: i64) -> Option<i64> {
        match self {
            X86SCEVExpr::Constant(v) => Some(*v),
            X86SCEVExpr::AddRec { base, step, .. } => {
                let b = base.evaluate_at(iteration)?;
                let s = step.evaluate_at(iteration)?;
                Some(b + s * iteration)
            }
            X86SCEVExpr::Add(a, b) => {
                let va = a.evaluate_at(iteration)?;
                let vb = b.evaluate_at(iteration)?;
                Some(va + vb)
            }
            X86SCEVExpr::Mul(a, b) => {
                let va = a.evaluate_at(iteration)?;
                let vb = b.evaluate_at(iteration)?;
                Some(va * vb)
            }
            X86SCEVExpr::ZExt(e) | X86SCEVExpr::SExt(e) | X86SCEVExpr::Truncate(e) => {
                e.evaluate_at(iteration)
            }
            X86SCEVExpr::SCEVValue(_) | X86SCEVExpr::Unknown | X86SCEVExpr::CouldNotCompute => None,
        }
    }

    /// Returns true if this SCEV is known at compile time (constant).
    pub fn is_constant(&self) -> bool {
        matches!(self, X86SCEVExpr::Constant(_))
    }

    /// Returns true if this is the "could not compute" sentinel.
    pub fn is_could_not_compute(&self) -> bool {
        matches!(self, X86SCEVExpr::CouldNotCompute)
    }

    /// Return true if this SCEV is a loop-invariant value.
    pub fn is_loop_invariant(&self, loop_id: u64) -> bool {
        match self {
            X86SCEVExpr::Constant(_) => true,
            X86SCEVExpr::AddRec { loop_id: lid, .. } => *lid != loop_id,
            X86SCEVExpr::Add(a, b) => a.is_loop_invariant(loop_id) && b.is_loop_invariant(loop_id),
            X86SCEVExpr::Mul(a, b) => a.is_loop_invariant(loop_id) && b.is_loop_invariant(loop_id),
            X86SCEVExpr::ZExt(e) | X86SCEVExpr::SExt(e) | X86SCEVExpr::Truncate(e) => {
                e.is_loop_invariant(loop_id)
            }
            _ => false,
        }
    }
}

/// SCEV-based alias analysis — disambiguates memory accesses in loops
/// by analyzing the Scalar Evolution of pointers.
///
/// Two memory accesses in a loop are NoAlias if their SCEV expressions
/// differ by a non-zero amount for all iteration counts.
#[derive(Debug, Clone)]
pub struct X86SCEVAA {
    /// Mapping from value id to its SCEV expression.
    pub scev_map: HashMap<u64, X86SCEVExpr>,
    /// Loop backedge taken counts: loop_id -> may_take_count.
    pub loop_bounds: HashMap<u64, u64>,
    /// Statistics.
    pub stats: X86SCEVAAStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86SCEVAAStats {
    pub total_queries: u64,
    pub noalias_results: u64,
    pub scev_disambiguations: u64,
}

impl X86SCEVAA {
    /// Create a new SCEV-AA instance.
    pub fn new() -> Self {
        X86SCEVAA {
            scev_map: HashMap::new(),
            loop_bounds: HashMap::new(),
            stats: X86SCEVAAStats::default(),
        }
    }

    /// Register a SCEV expression for a value.
    pub fn register_scev(&mut self, value: u64, expr: X86SCEVExpr) {
        self.scev_map.insert(value, expr);
    }

    /// Register a loop backedge count.
    pub fn register_loop_bound(&mut self, loop_id: u64, max_count: u64) {
        self.loop_bounds.insert(loop_id, max_count);
    }

    /// Query whether two memory locations alias, using SCEV information.
    pub fn alias(&mut self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        self.stats.total_queries += 1;

        let scev_a = self.scev_map.get(&loc_a.ptr);
        let scev_b = self.scev_map.get(&loc_b.ptr);

        match (scev_a, scev_b) {
            (Some(a), Some(b)) => {
                // Try to prove they don't alias using SCEV
                if self.scev_prove_noalias(a, b, loc_a.size, loc_b.size) {
                    self.stats.scev_disambiguations += 1;
                    self.stats.noalias_results += 1;
                    return AliasResult::NoAlias;
                }

                // Try to prove they must alias
                if self.scev_prove_mustalias(a, b) {
                    return AliasResult::MustAlias;
                }
            }
            _ => {}
        }

        AliasResult::MayAlias
    }

    /// Try to prove two SCEV expressions never alias for the given access sizes.
    fn scev_prove_noalias(
        &self,
        a: &X86SCEVExpr,
        b: &X86SCEVExpr,
        size_a: u64,
        size_b: u64,
    ) -> bool {
        // If both are add-recurrences for the same loop
        if let (
            X86SCEVExpr::AddRec {
                base: base_a,
                step: step_a,
                loop_id: lid_a,
            },
            X86SCEVExpr::AddRec {
                base: base_b,
                step: step_b,
                loop_id: lid_b,
            },
        ) = (a, b)
        {
            if lid_a == lid_b {
                // Same loop: check if the difference is constant
                if let (X86SCEVExpr::Constant(base_a_val), X86SCEVExpr::Constant(base_b_val)) =
                    (base_a.as_ref(), base_b.as_ref())
                {
                    if let (X86SCEVExpr::Constant(step_a_val), X86SCEVExpr::Constant(step_b_val)) =
                        (step_a.as_ref(), step_b.as_ref())
                    {
                        let min_step = min(step_a_val.abs(), step_b_val.abs()) as u64;
                        // If the base offset difference is >= min(size_a, size_b)
                        // AND the steps are the same (or both zero), they never overlap
                        let diff = (base_a_val - base_b_val).abs() as u64;
                        let min_size = min(size_a, size_b);
                        if diff >= min_size && *step_a_val == *step_b_val {
                            return true;
                        }
                        // If base_diff is non-zero and the common step > min_size,
                        // the accesses are interleaved without overlap
                        if diff > 0 && min_step > min_size {
                            return true;
                        }
                    }
                }
            }
        }

        // If one is a constant SCEV and the other is not:
        // This is conservative; only prove noalias if one is definitely
        // at a constant offset that cannot overlap.
        if let X86SCEVExpr::Constant(const_val) = a {
            if let X86SCEVExpr::Constant(b_val) = b {
                let diff = (const_val - b_val).abs() as u64;
                let min_size = min(size_a, size_b);
                if diff >= min_size {
                    return true;
                }
            }
        }

        false
    }

    /// Try to prove two SCEVs must alias.
    fn scev_prove_mustalias(&self, a: &X86SCEVExpr, b: &X86SCEVExpr) -> bool {
        // If they are the same constant, they must alias
        matches!(
            (a, b),
            (X86SCEVExpr::Constant(va), X86SCEVExpr::Constant(vb))
                if va == vb
        )
    }

    /// Get the SCEV for a value.
    pub fn get_scev(&self, value: u64) -> Option<&X86SCEVExpr> {
        self.scev_map.get(&value)
    }

    /// Get statistics.
    pub fn get_stats(&self) -> &X86SCEVAAStats {
        &self.stats
    }
}

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

// ============================================================================
// X86GlobalsModRef — Global Mod/Ref Analysis
// ============================================================================

/// Global Mod/Ref analysis: tracks which functions may read or write
/// which global variables. This enables more precise alias analysis
/// across function call boundaries.
#[derive(Debug, Clone)]
pub struct X86GlobalsModRef {
    /// Map from global variable id to its ModRefInfo observed across calls.
    pub global_access: HashMap<u64, ModRefInfo>,
    /// Map from function id to the set of globals it may access.
    pub function_globals: HashMap<u64, HashSet<u64>>,
    /// Map from function id to its ModRef behavior.
    pub function_behavior: HashMap<u64, FunctionModRefInfo>,
    /// Globals that are known to not have their address taken.
    pub non_address_taken_globals: HashSet<u64>,
    /// Globals that are known to be read-only after initialization.
    pub read_only_globals: HashSet<u64>,
    /// Statistics.
    pub stats: X86GlobalsModRefStats,
}

/// Per-function ModRef behavior classification.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum FunctionModRefInfo {
    /// Does not access any memory (readnone).
    DoesNotAccessMemory,
    /// Only reads memory (readonly).
    OnlyReadsMemory,
    /// Only writes memory (writeonly).
    OnlyWritesMemory,
    /// May read and write memory (default).
    ModRef,
    /// Only accesses memory through its arguments (argmemonly).
    OnlyAccessesArgMemory,
    /// Does not access memory visible to the caller (inaccessiblememonly).
    OnlyAccessesInaccessibleMemory,
}

impl fmt::Display for FunctionModRefInfo {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            FunctionModRefInfo::DoesNotAccessMemory => write!(f, "readnone"),
            FunctionModRefInfo::OnlyReadsMemory => write!(f, "readonly"),
            FunctionModRefInfo::OnlyWritesMemory => write!(f, "writeonly"),
            FunctionModRefInfo::ModRef => write!(f, "modref"),
            FunctionModRefInfo::OnlyAccessesArgMemory => write!(f, "argmemonly"),
            FunctionModRefInfo::OnlyAccessesInaccessibleMemory => {
                write!(f, "inaccessiblememonly")
            }
        }
    }
}

#[derive(Debug, Clone, Default)]
pub struct X86GlobalsModRefStats {
    pub total_globals: usize,
    pub total_functions: usize,
    pub non_address_taken_count: usize,
    pub read_only_count: usize,
    pub queries_resolved: u64,
    pub noalias_results: u64,
}

impl X86GlobalsModRef {
    /// Create a new GlobalsModRef instance.
    pub fn new() -> Self {
        X86GlobalsModRef {
            global_access: HashMap::new(),
            function_globals: HashMap::new(),
            function_behavior: HashMap::new(),
            non_address_taken_globals: HashSet::new(),
            read_only_globals: HashSet::new(),
            stats: X86GlobalsModRefStats::default(),
        }
    }

    /// Register a global variable.
    pub fn register_global(&mut self, global_id: u64, address_taken: bool, read_only: bool) {
        self.global_access
            .entry(global_id)
            .or_insert(ModRefInfo::NoModRef);
        if !address_taken {
            self.non_address_taken_globals.insert(global_id);
        }
        if read_only {
            self.read_only_globals.insert(global_id);
        }
        self.stats.total_globals = self.global_access.len();
    }

    /// Register a function's behavior.
    pub fn register_function(&mut self, func_id: u64, behavior: FunctionModRefInfo) {
        self.function_behavior.insert(func_id, behavior);
        self.stats.total_functions = self.function_behavior.len();
    }

    /// Record that a function accesses a specific global.
    pub fn record_global_access(&mut self, func_id: u64, global_id: u64, access: ModRefInfo) {
        self.function_globals
            .entry(func_id)
            .or_default()
            .insert(global_id);
        let entry = self
            .global_access
            .entry(global_id)
            .or_insert(ModRefInfo::NoModRef);
        *entry = ModRefInfo::union(*entry, access);
    }

    /// Get the ModRefInfo for a global.
    pub fn get_global_access(&self, global_id: u64) -> ModRefInfo {
        self.global_access
            .get(&global_id)
            .copied()
            .unwrap_or(ModRefInfo::ModRef)
    }

    /// Check whether a function can modify a specific global.
    pub fn function_modifies_global(&self, func_id: u64, global_id: u64) -> bool {
        // Check function behavior first
        if let Some(behavior) = self.function_behavior.get(&func_id) {
            match behavior {
                FunctionModRefInfo::DoesNotAccessMemory
                | FunctionModRefInfo::OnlyAccessesInaccessibleMemory => {
                    return false;
                }
                FunctionModRefInfo::OnlyReadsMemory => return false,
                _ => {}
            }
        }

        // Check if this global was accessed by this function
        if let Some(globals) = self.function_globals.get(&func_id) {
            if globals.contains(&global_id) {
                // Check the access kind
                if let Some(access) = self.global_access.get(&global_id) {
                    return access.does_mod();
                }
            }
        }

        // Conservative: if the global's address is taken, assume modification
        !self.non_address_taken_globals.contains(&global_id)
    }

    /// Check whether a global is read-only.
    pub fn is_read_only_global(&self, global_id: u64) -> bool {
        self.read_only_globals.contains(&global_id)
    }

    /// Check if a global is non-address-taken (cannot be indirectly accessed).
    pub fn is_non_address_taken(&self, global_id: u64) -> bool {
        self.non_address_taken_globals.contains(&global_id)
    }

    /// Get ModRefInfo for a call instruction given the called function.
    pub fn get_mod_ref_for_call(&mut self, func_id: u64, loc: &MemoryLocation) -> ModRefInfo {
        self.stats.queries_resolved += 1;

        // If the location is an alloca (stack), functions don't access it
        // unless the pointer escapes
        if loc.ptr != 0 {
            if let Some(behavior) = self.function_behavior.get(&func_id) {
                match behavior {
                    FunctionModRefInfo::DoesNotAccessMemory => {
                        self.stats.noalias_results += 1;
                        return ModRefInfo::NoModRef;
                    }
                    FunctionModRefInfo::OnlyReadsMemory => return ModRefInfo::Ref,
                    FunctionModRefInfo::OnlyAccessesInaccessibleMemory => {
                        return ModRefInfo::NoModRef;
                    }
                    _ => {}
                }
            }

            // Check if this is a global that the function accesses
            if self.non_address_taken_globals.contains(&loc.ptr) {
                if let Some(globals) = self.function_globals.get(&func_id) {
                    if !globals.contains(&loc.ptr) {
                        // This non-address-taken global is not accessed by this function
                        self.stats.noalias_results += 1;
                        return ModRefInfo::NoModRef;
                    }
                }
                // Get the specific access mode
                if let Some(access) = self.global_access.get(&loc.ptr) {
                    return *access;
                }
            }

            // If global is read-only, a function cannot write to it
            if self.read_only_globals.contains(&loc.ptr) {
                return ModRefInfo::Ref;
            }
        }

        ModRefInfo::ModRef
    }

    /// Get statistics.
    pub fn get_stats(&self) -> &X86GlobalsModRefStats {
        &self.stats
    }

    /// Update non-address-taken count.
    pub fn update_counts(&mut self) {
        self.stats.non_address_taken_count = self.non_address_taken_globals.len();
        self.stats.read_only_count = self.read_only_globals.len();
    }
}

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

// ============================================================================
// X86TypeBasedAA — TBAA (Type-Based Alias Analysis)
// ============================================================================

/// A node in the TBAA type tree.
#[derive(Debug, Clone)]
pub struct TBAANode {
    /// Unique identifier for this node.
    pub id: u64,
    /// Parent node id in the tree (0 means root).
    pub parent_id: u64,
    /// Type name for this node.
    pub type_name: String,
    /// Whether this represents constant memory.
    pub is_constant: bool,
    /// Depth in the tree (cached).
    pub depth: usize,
    /// Child node ids (cached).
    pub children: Vec<u64>,
}

impl TBAANode {
    pub fn new(id: u64, parent_id: u64, type_name: &str) -> Self {
        TBAANode {
            id,
            parent_id,
            type_name: type_name.to_string(),
            is_constant: false,
            depth: 0,
            children: Vec::new(),
        }
    }

    pub fn new_constant(id: u64, parent_id: u64, type_name: &str) -> Self {
        TBAANode {
            id,
            parent_id,
            type_name: type_name.to_string(),
            is_constant: true,
            depth: 0,
            children: Vec::new(),
        }
    }
}

/// A TBAA metadata tag attached to a memory access.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct TBAATag {
    /// Type node identifier for the access type.
    pub access_type_id: u64,
    /// Type node identifier for the base type.
    pub base_type_id: u64,
    /// Offset within the type (for struct field accesses).
    pub offset: u64,
    /// Whether this tag represents an immutable access.
    pub is_constant: bool,
}

impl TBAATag {
    pub fn new(access_type_id: u64, base_type_id: u64, offset: u64) -> Self {
        TBAATag {
            access_type_id,
            base_type_id,
            offset,
            is_constant: false,
        }
    }

    pub fn new_constant(access_type_id: u64, base_type_id: u64, offset: u64) -> Self {
        TBAATag {
            access_type_id,
            base_type_id,
            offset,
            is_constant: true,
        }
    }
}

/// Type-Based Alias Analysis — uses LLVM TBAA metadata to disambiguate
/// memory accesses based on their declared types.
///
/// Two memory accesses cannot alias if their TBAA types are in different
/// branches of the type tree (no common ancestor with appropriate offset).
#[derive(Debug, Clone)]
pub struct X86TypeBasedAA {
    /// The TBAA type tree nodes, keyed by id.
    pub type_nodes: HashMap<u64, TBAANode>,
    /// Cached ancestor sets for each node.
    ancestor_cache: HashMap<u64, HashSet<u64>>,
    /// Statistics.
    pub stats: X86TypeBasedAAStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86TypeBasedAAStats {
    pub total_nodes: usize,
    pub total_queries: u64,
    pub noalias_results: u64,
    pub mayalias_results: u64,
}

impl X86TypeBasedAA {
    /// Create a new TypeBasedAA instance.
    pub fn new() -> Self {
        X86TypeBasedAA {
            type_nodes: HashMap::new(),
            ancestor_cache: HashMap::new(),
            stats: X86TypeBasedAAStats::default(),
        }
    }

    /// Add a type node to the TBAA tree.
    pub fn add_type_node(&mut self, node: TBAANode) {
        // Update parent's children list
        if node.parent_id != 0 {
            if let Some(parent) = self.type_nodes.get_mut(&node.parent_id) {
                parent.children.push(node.id);
            }
        }
        self.type_nodes.insert(node.id, node);
        self.stats.total_nodes = self.type_nodes.len();

        // Invalidate ancestor cache
        self.ancestor_cache.clear();
    }

    /// Add a struct path tag: a sequence of (field_type_id, offset) pairs.
    pub fn add_struct_path(&mut self, base_type_id: u64, path: &[(u64, u64)]) -> Vec<TBAATag> {
        path.iter()
            .map(|(type_id, offset)| TBAATag::new(*type_id, base_type_id, *offset))
            .collect()
    }

    /// Query whether two TBAA tags may alias.
    pub fn may_alias(&self, tag_a: Option<&TBAATag>, tag_b: Option<&TBAATag>) -> AliasResult {
        // If either tag is missing, cannot disambiguate
        let tag_a = match tag_a {
            Some(t) => t,
            None => return AliasResult::MayAlias,
        };
        let tag_b = match tag_b {
            Some(t) => t,
            None => return AliasResult::MayAlias,
        };

        // If both tags have the exact same access type and offset, MustAlias
        if tag_a.access_type_id == tag_b.access_type_id && tag_a.offset == tag_b.offset {
            return AliasResult::MustAlias;
        }

        // Get ancestors of both types
        let ancestors_a = self.get_ancestors(tag_a.access_type_id);
        let ancestors_b = self.get_ancestors(tag_b.access_type_id);

        // Find common ancestors
        let common: HashSet<_> = ancestors_a.intersection(&ancestors_b).copied().collect();

        if common.is_empty() {
            // Different root types -> NoAlias
            return AliasResult::NoAlias;
        }

        // Check if the common ancestor implies they might alias
        // If one is an ancestor of the other AND the offset ranges don't
        // provably avoid overlap, then MayAlias
        let is_ancestor_a = ancestors_a.contains(&tag_b.access_type_id);
        let is_ancestor_b = ancestors_b.contains(&tag_a.access_type_id);

        if is_ancestor_a || is_ancestor_b {
            // One is a subtype of the other; need to check offsets
            // For now, conservatively return MayAlias
            AliasResult::MayAlias
        } else if tag_a.base_type_id == tag_b.base_type_id {
            // Same base type, check offsets
            AliasResult::MayAlias
        } else {
            AliasResult::MayAlias
        }
    }

    /// Get all ancestor type node ids for a given node id.
    fn get_ancestors(&self, node_id: u64) -> HashSet<u64> {
        if let Some(cached) = self.ancestor_cache.get(&node_id) {
            return cached.clone();
        }

        let mut ancestors = HashSet::new();
        ancestors.insert(node_id); // A node is its own ancestor

        let mut current = node_id;
        while let Some(node) = self.type_nodes.get(&current) {
            if current != node_id {
                ancestors.insert(current);
            }
            if node.parent_id == 0 || node.parent_id == current {
                break;
            }
            current = node.parent_id;
        }

        // Note: caching disabled to avoid borrow issues
        ancestors
    }

    /// Check if a TBAA tag indicates constant memory.
    pub fn is_constant_tag(&self, tag: Option<&TBAATag>) -> bool {
        if let Some(tag) = tag {
            if tag.is_constant {
                return true;
            }
            if let Some(node) = self.type_nodes.get(&tag.access_type_id) {
                return node.is_constant;
            }
        }
        false
    }

    /// Check if two TBAA tags can alias given their types.
    pub fn alias(&mut self, tag_a: Option<&TBAATag>, tag_b: Option<&TBAATag>) -> AliasResult {
        self.stats.total_queries += 1;
        let result = self.may_alias(tag_a, tag_b);
        match result {
            AliasResult::NoAlias => self.stats.noalias_results += 1,
            AliasResult::MayAlias => self.stats.mayalias_results += 1,
            _ => {}
        }
        result
    }

    /// Get statistics.
    pub fn get_stats(&self) -> &X86TypeBasedAAStats {
        &self.stats
    }
}

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

// ============================================================================
// X86ScopedNoAliasAA — Scoped NoAlias Alias Analysis
// ============================================================================

/// A scope domain for scoped noalias metadata.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct AliasScopeDomain {
    /// Unique identifier for the domain.
    pub domain_id: u64,
    /// Scope identifier within the domain.
    pub scope_id: u64,
}

impl AliasScopeDomain {
    pub fn new(domain_id: u64, scope_id: u64) -> Self {
        AliasScopeDomain {
            domain_id,
            scope_id,
        }
    }
}

/// Scoped NoAlias Alias Analysis — uses LLVM alias.scope and noalias
/// metadata to disambiguate memory accesses.
///
/// alias.scope metadata says "this access is within scope (domain, scope)".
/// noalias metadata says "this access does not alias with (domain, scope)".
///
/// Two accesses are NoAlias if they are in different scopes that are
/// marked as not aliasing each other.
#[derive(Debug, Clone)]
pub struct X86ScopedNoAliasAA {
    /// Set of (domain, scope_a, scope_b) triples where scope_a noaliases scope_b.
    pub noalias_pairs: HashSet<(u64, u64, u64)>,
    /// Statistics.
    pub stats: X86ScopedNoAliasAAStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86ScopedNoAliasAAStats {
    pub total_queries: u64,
    pub noalias_results: u64,
    pub scoped_disambiguations: u64,
}

impl X86ScopedNoAliasAA {
    /// Create a new ScopedNoAliasAA instance.
    pub fn new() -> Self {
        X86ScopedNoAliasAA {
            noalias_pairs: HashSet::new(),
            stats: X86ScopedNoAliasAAStats::default(),
        }
    }

    /// Register that scope_a does not alias scope_b within domain.
    pub fn register_noalias(&mut self, domain: u64, scope_a: u64, scope_b: u64) {
        self.noalias_pairs.insert((domain, scope_a, scope_b));
        self.noalias_pairs.insert((domain, scope_b, scope_a));
    }

    /// Query whether two memory locations may alias based on scoped noalias.
    pub fn may_alias(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        // Both must have scoped noalias metadata
        if !loc_a.has_scoped_noalias() || !loc_b.has_scoped_noalias() {
            return AliasResult::MayAlias;
        }

        let domain_a = match &loc_a.noalias_domain {
            Some(d) => d.parse::<u64>().unwrap_or(0),
            None => return AliasResult::MayAlias,
        };
        let domain_b = match &loc_b.noalias_domain {
            Some(d) => d.parse::<u64>().unwrap_or(0),
            None => return AliasResult::MayAlias,
        };

        // Must be in the same domain
        if domain_a != domain_b || domain_a == 0 {
            return AliasResult::MayAlias;
        }

        // Check scopes
        for scope_a in &loc_a.noalias_scopes {
            let sid_a = scope_a.parse::<u64>().unwrap_or(0);
            for scope_b in &loc_b.noalias_scopes {
                let sid_b = scope_b.parse::<u64>().unwrap_or(0);
                if sid_a == sid_b {
                    // Same scope, may alias
                    return AliasResult::MayAlias;
                }
                if self.noalias_pairs.contains(&(domain_a, sid_a, sid_b)) {
                    return AliasResult::NoAlias;
                }
            }
        }

        AliasResult::MayAlias
    }

    /// Perform an alias check with statistics.
    pub fn alias(&mut self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        self.stats.total_queries += 1;
        let result = self.may_alias(loc_a, loc_b);
        if result == AliasResult::NoAlias {
            self.stats.noalias_results += 1;
            self.stats.scoped_disambiguations += 1;
        }
        result
    }

    /// Get statistics.
    pub fn get_stats(&self) -> &X86ScopedNoAliasAAStats {
        &self.stats
    }
}

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

// ============================================================================
// X86MemorySSA — Memory SSA Form
// ============================================================================

/// A memory access in MemorySSA form.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum X86MemoryAccessKind {
    /// A memory definition (store or memory-clobbering call).
    Def,
    /// A memory use (load).
    Use,
    /// A memory phi (join point for memory versions).
    Phi,
}

/// A memory definition — represents a store or other memory-writing operation.
#[derive(Debug, Clone)]
pub struct X86MemoryDef {
    /// Unique identifier for this memory definition.
    pub id: u64,
    /// The basic block containing this definition.
    pub block_id: u64,
    /// The instruction that performs the store (opcode + operand ids).
    pub store_inst: u64,
    /// The memory access that this definition overrides (previous version).
    pub defining_access: Option<u64>,
    /// The memory location being stored to.
    pub location: MemoryLocation,
    /// Is this definition live on entry to the function?
    pub is_live_on_entry: bool,
    /// Set of accesses that use this definition.
    pub users: HashSet<u64>,
    /// For optimized MemorySSA, whether this def can be skipped.
    pub is_optimizable: bool,
}

impl X86MemoryDef {
    pub fn new(id: u64, block_id: u64, store_inst: u64, location: MemoryLocation) -> Self {
        X86MemoryDef {
            id,
            block_id,
            store_inst,
            defining_access: None,
            location,
            is_live_on_entry: false,
            users: HashSet::new(),
            is_optimizable: false,
        }
    }
}

/// A memory use — represents a load or other memory-reading operation.
#[derive(Debug, Clone)]
pub struct X86MemoryUse {
    /// Unique identifier for this memory use.
    pub id: u64,
    /// The basic block containing this use.
    pub block_id: u64,
    /// The instruction that performs the load.
    pub load_inst: u64,
    /// The memory access that defines the memory version being read.
    pub defining_access: Option<u64>,
    /// The memory location being read from.
    pub location: MemoryLocation,
    /// Whether this use has been optimized.
    pub is_optimized: bool,
}

impl X86MemoryUse {
    pub fn new(id: u64, block_id: u64, load_inst: u64, location: MemoryLocation) -> Self {
        X86MemoryUse {
            id,
            block_id,
            load_inst,
            defining_access: None,
            location,
            is_optimized: false,
        }
    }
}

/// A memory phi — joins memory versions from different predecessor blocks.
#[derive(Debug, Clone)]
pub struct X86MemoryPhi {
    /// Unique identifier for this memory phi.
    pub id: u64,
    /// The basic block containing this phi.
    pub block_id: u64,
    /// Incoming memory access ids from predecessor blocks: (pred_block_id, access_id).
    pub incoming: Vec<(u64, u64)>,
}

impl X86MemoryPhi {
    pub fn new(id: u64, block_id: u64) -> Self {
        X86MemoryPhi {
            id,
            block_id,
            incoming: Vec::new(),
        }
    }

    /// Add an incoming edge.
    pub fn add_incoming(&mut self, pred_block_id: u64, access_id: u64) {
        self.incoming.push((pred_block_id, access_id));
    }

    /// Get the access id for a specific predecessor.
    pub fn get_incoming_for_pred(&self, pred_block_id: u64) -> Option<u64> {
        self.incoming
            .iter()
            .find(|(p, _)| *p == pred_block_id)
            .map(|(_, a)| *a)
    }
}

/// MemorySSA — the complete Memory SSA form for a function.
#[derive(Debug, Clone)]
pub struct X86MemorySSA {
    /// All memory definitions in the function.
    pub memory_defs: HashMap<u64, X86MemoryDef>,
    /// All memory uses in the function.
    pub memory_uses: HashMap<u64, X86MemoryUse>,
    /// All memory phis in the function.
    pub memory_phis: HashMap<u64, X86MemoryPhi>,
    /// The live-on-entry memory version (represents uninitialized memory).
    pub live_on_entry: Option<u64>,
    /// Mapping from basic block id to its memory phi (if any).
    pub block_to_phi: HashMap<u64, u64>,
    /// Mapping from instruction id to its memory access id.
    pub inst_to_access: HashMap<u64, u64>,
    /// Next available access id.
    next_id: u64,
    /// Whether MemorySSA is in optimized form.
    pub is_optimized: bool,
    /// Dominator tree info: block -> immediate dominator.
    pub idom: HashMap<u64, u64>,
    /// Predecessor blocks: block -> predecessors.
    pub predecessors: HashMap<u64, Vec<u64>>,
    /// The entry block id.
    pub entry_block: u64,
    /// Statistics.
    pub stats: X86MemorySSAStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86MemorySSAStats {
    pub total_accesses: usize,
    pub memory_defs: usize,
    pub memory_uses: usize,
    pub memory_phis: usize,
    pub dead_stores: usize,
    pub redundant_loads: usize,
    pub optimized_uses: usize,
}

impl X86MemorySSA {
    /// Create a new empty MemorySSA instance.
    pub fn new() -> Self {
        X86MemorySSA {
            memory_defs: HashMap::new(),
            memory_uses: HashMap::new(),
            memory_phis: HashMap::new(),
            live_on_entry: None,
            block_to_phi: HashMap::new(),
            inst_to_access: HashMap::new(),
            next_id: 1,
            is_optimized: false,
            idom: HashMap::new(),
            predecessors: HashMap::new(),
            entry_block: 0,
            stats: X86MemorySSAStats::default(),
        }
    }

    /// Get the next access id.
    fn next_id(&mut self) -> u64 {
        let id = self.next_id;
        self.next_id += 1;
        id
    }

    /// Set dominator information.
    pub fn set_dominators(&mut self, idom: HashMap<u64, u64>) {
        self.idom = idom;
    }

    /// Set predecessor information.
    pub fn set_predecessors(&mut self, preds: HashMap<u64, Vec<u64>>) {
        self.predecessors = preds;
    }

    /// Set the entry block.
    pub fn set_entry_block(&mut self, block_id: u64) {
        self.entry_block = block_id;
    }

    /// Build MemorySSA from a list of memory operations in block order.
    ///
    /// `ops` is a list of (block_id, inst_id, opcode, pointer, size, is_load)
    /// tuples in program order.
    pub fn build(&mut self, ops: &[(u64, u64, X86Opcode, u64, u64, bool)], block_order: &[u64]) {
        // Create live-on-entry sentinel
        let live_on_entry_id = self.next_id();
        self.live_on_entry = Some(live_on_entry_id);
        let live_on_entry_def = X86MemoryDef {
            id: live_on_entry_id,
            block_id: self.entry_block,
            store_inst: 0,
            defining_access: None,
            location: MemoryLocation::new(0, 0),
            is_live_on_entry: true,
            users: HashSet::new(),
            is_optimizable: false,
        };
        self.memory_defs.insert(live_on_entry_id, live_on_entry_def);

        // Track the current defining access per memory location (last store to that location).
        let mut current_def_per_loc: HashMap<u64, u64> = HashMap::new();

        // Result accumulator: block -> (memory accesses in order)
        let mut block_accesses: HashMap<u64, Vec<u64>> = HashMap::new();

        for &(block_id, inst_id, _opcode, ptr, size, is_load) in ops {
            let loc = MemoryLocation::new(ptr, size);

            if is_load {
                // Create a memory use
                let use_id = self.next_id();
                let defining = current_def_per_loc
                    .get(&ptr)
                    .copied()
                    .unwrap_or(live_on_entry_id);

                let mut mem_use = X86MemoryUse::new(use_id, block_id, inst_id, loc.clone());
                mem_use.defining_access = Some(defining);

                // Add as user of the defining access
                if let Some(def) = self.memory_defs.get_mut(&defining) {
                    def.users.insert(use_id);
                }
                if let Some(def) = self.memory_uses.get_mut(&defining) {
                    // Uses can also be used by other uses (in theory)
                }

                self.memory_uses.insert(use_id, mem_use);
                self.inst_to_access.insert(inst_id, use_id);
                block_accesses.entry(block_id).or_default().push(use_id);
            } else {
                // Create a memory definition
                let def_id = self.next_id();
                let defining = current_def_per_loc
                    .get(&ptr)
                    .copied()
                    .unwrap_or(live_on_entry_id);

                let mut mem_def = X86MemoryDef::new(def_id, block_id, inst_id, loc.clone());
                mem_def.defining_access = Some(defining);

                // Add as user of the previous defining access
                if let Some(prev_def) = self.memory_defs.get_mut(&defining) {
                    prev_def.users.insert(def_id);
                }

                current_def_per_loc.insert(ptr, def_id);

                self.memory_defs.insert(def_id, mem_def);
                self.inst_to_access.insert(inst_id, def_id);
                block_accesses.entry(block_id).or_default().push(def_id);
            }
        }

        // Insert memory phis at join points
        self.insert_memory_phis(block_order, &block_accesses);

        // Update stats
        self.update_stats();
    }

    /// Insert memory phis at basic block join points.
    fn insert_memory_phis(&mut self, block_order: &[u64], block_accesses: &HashMap<u64, Vec<u64>>) {
        // For each block with multiple predecessors, insert a memory phi
        for &block_id in block_order {
            if let Some(preds) = self.predecessors.get(&block_id) {
                if preds.len() > 1 {
                    // Collect the last memory def from each predecessor
                    let mut incoming = Vec::new();
                    for &pred_id in preds {
                        let last_access = block_accesses
                            .get(&pred_id)
                            .and_then(|accesses| accesses.last())
                            .copied()
                            .unwrap_or_else(|| self.live_on_entry.unwrap_or(1));
                        incoming.push((pred_id, last_access));
                    }

                    let phi_id = self.next_id();
                    let mut phi = X86MemoryPhi::new(phi_id, block_id);
                    phi.incoming = incoming;
                    self.memory_phis.insert(phi_id, phi);
                    self.block_to_phi.insert(block_id, phi_id);
                }
            }
        }
    }

    /// Get the defining access for a memory use.
    pub fn get_defining_access(&self, inst_id: u64) -> Option<u64> {
        self.inst_to_access.get(&inst_id).and_then(|access_id| {
            self.memory_uses
                .get(access_id)
                .and_then(|mem_use| mem_use.defining_access)
        })
    }

    /// Get the memory access for an instruction.
    pub fn get_memory_access(&self, inst_id: u64) -> Option<u64> {
        self.inst_to_access.get(&inst_id).copied()
    }

    /// Check if two memory locations are the same.
    pub fn is_same_memory_location(&self, access_a: u64, access_b: u64) -> bool {
        let loc_a = self.get_location(access_a);
        let loc_b = self.get_location(access_b);
        match (loc_a, loc_b) {
            (Some(a), Some(b)) => a == b,
            _ => false,
        }
    }

    /// Get the memory location for an access.
    fn get_location(&self, access_id: u64) -> Option<MemoryLocation> {
        if let Some(def) = self.memory_defs.get(&access_id) {
            Some(def.location.clone())
        } else if let Some(use_access) = self.memory_uses.get(&access_id) {
            Some(use_access.location.clone())
        } else {
            None
        }
    }

    /// Check whether access_a dominates access_b.
    pub fn dominates_access(&self, access_a: u64, access_b: u64) -> bool {
        let block_a = self.get_access_block(access_a);
        let block_b = self.get_access_block(access_b);
        match (block_a, block_b) {
            (Some(ba), Some(bb)) => self.dominates(ba, bb),
            _ => false,
        }
    }

    /// Get the block containing an access.
    fn get_access_block(&self, access_id: u64) -> Option<u64> {
        if let Some(def) = self.memory_defs.get(&access_id) {
            Some(def.block_id)
        } else if let Some(use_access) = self.memory_uses.get(&access_id) {
            Some(use_access.block_id)
        } else if let Some(phi) = self.memory_phis.get(&access_id) {
            Some(phi.block_id)
        } else {
            None
        }
    }

    /// Check if block_a dominates block_b using idom.
    fn dominates(&self, block_a: u64, block_b: u64) -> bool {
        if block_a == block_b {
            return true;
        }
        let mut current = block_b;
        let mut visited = HashSet::new();
        for _ in 0..X86_MEMSSA_MAX_WALK_DEPTH {
            if visited.contains(&current) {
                break;
            }
            visited.insert(current);
            if current == block_a {
                return true;
            }
            match self.idom.get(&current) {
                Some(dom) => {
                    if *dom == current {
                        break;
                    }
                    current = *dom;
                }
                None => break,
            }
        }
        false
    }

    /// Optimize MemorySSA by skipping transitive defs that don't clobber.
    pub fn optimize_uses(&mut self) {
        if self.is_optimized {
            return;
        }

        let mut optimized_count = 0usize;

        // For each memory use, try to skip intermediate defs that don't alias
        let use_ids: Vec<u64> = self.memory_uses.keys().copied().collect();
        for use_id in use_ids {
            if let Some(mem_use) = self.memory_uses.get(&use_id) {
                let loc = mem_use.location.clone();
                let mut current_def = mem_use.defining_access;

                // Walk up the def chain, skipping defs that are NoAlias
                let mut walk_count = 0;
                while let Some(def_id) = current_def {
                    walk_count += 1;
                    if walk_count > X86_MEMSSA_MAX_WALK_DEPTH {
                        break;
                    }

                    if let Some(def) = self.memory_defs.get(&def_id) {
                        if def.is_live_on_entry {
                            break;
                        }
                        // Check if this def might alias with the use's location
                        if self.may_alias_locations(&def.location, &loc) {
                            // Found a clobbering def — stop optimizing
                            break;
                        }
                        // This def doesn't alias, skip to its defining access
                        current_def = def.defining_access;
                    } else {
                        break;
                    }
                }

                if current_def != mem_use.defining_access && current_def.is_some() {
                    // Update the use's defining access
                    if let Some(mem_use) = self.memory_uses.get_mut(&use_id) {
                        mem_use.defining_access = current_def;
                        mem_use.is_optimized = true;
                        optimized_count += 1;
                    }
                }
            }
        }

        self.stats.optimized_uses = optimized_count;
        self.is_optimized = true;
    }

    /// Check if two memory locations may alias (conservative check).
    fn may_alias_locations(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> bool {
        if loc_a.ptr == 0 || loc_b.ptr == 0 {
            return false;
        }
        if loc_a.ptr == loc_b.ptr {
            // Same pointer; check if offsets rule out aliasing
            if loc_a.has_known_size && loc_b.has_known_size {
                // Conservatively assume aliasing unless clearly disjoint
                return true;
            }
            return true;
        }
        // Different pointers, conservatively assume may alias
        true
    }

    /// Find the nearest clobbering memory access for a given location
    /// starting from a specific access (clobber walker).
    pub fn get_clobbering_access(
        &self,
        start_access: u64,
        location: &MemoryLocation,
    ) -> Option<u64> {
        let mut current = Some(start_access);
        let mut depth = 0;

        while let Some(access_id) = current {
            depth += 1;
            if depth > X86_MEMSSA_MAX_WALK_DEPTH {
                break;
            }

            if let Some(def) = self.memory_defs.get(&access_id) {
                if def.is_live_on_entry {
                    return Some(access_id);
                }

                // Check if this definition may clobber (alias with) the location
                if self.may_alias_locations(&def.location, location) {
                    return Some(access_id);
                }

                // Walk up to the defining access
                current = def.defining_access;
            } else if let Some(mem_use) = self.memory_uses.get(&access_id) {
                // Walk up through the defining access of this use
                current = mem_use.defining_access;
            } else if let Some(phi) = self.memory_phis.get(&access_id) {
                // Walk up all phi incoming edges (conservatively return the phi)
                // Actually, for a single predecessor context, we'd walk the
                // specific incoming value. Here we conservatively return the phi.
                return Some(access_id);
            } else {
                break;
            }
        }

        None
    }

    /// Walk the definition chain of a memory access.
    pub fn walk_def_chain(&self, start_access: u64) -> Vec<u64> {
        let mut chain = Vec::new();
        let mut current = Some(start_access);
        let mut depth = 0;

        while let Some(access_id) = current {
            depth += 1;
            if depth > X86_MEMSSA_MAX_WALK_DEPTH {
                break;
            }
            chain.push(access_id);

            if let Some(def) = self.memory_defs.get(&access_id) {
                if def.is_live_on_entry {
                    break;
                }
                current = def.defining_access;
            } else if let Some(mem_use) = self.memory_uses.get(&access_id) {
                current = mem_use.defining_access;
            } else {
                break;
            }
        }

        chain
    }

    /// Verify the MemorySSA form for correctness.
    pub fn verify(&self) -> Result<(), String> {
        // Check that each memory use has a defining access
        for (use_id, mem_use) in &self.memory_uses {
            if mem_use.defining_access.is_none() && !self.live_on_entry.is_some() {
                return Err(format!("MemoryUse {} has no defining access", use_id));
            }
        }

        // Check that phi incoming edges reference valid accesses
        for (phi_id, phi) in &self.memory_phis {
            for (pred_id, incoming_id) in &phi.incoming {
                if !self.memory_defs.contains_key(incoming_id)
                    && !self.memory_uses.contains_key(incoming_id)
                    && !self.memory_phis.contains_key(incoming_id)
                {
                    return Err(format!(
                        "MemoryPhi {} has invalid incoming access {} from block {}",
                        phi_id, incoming_id, pred_id
                    ));
                }
            }
        }

        // Check that defs have valid defining accesses
        for (def_id, def) in &self.memory_defs {
            if !def.is_live_on_entry {
                if let Some(defining) = def.defining_access {
                    if !self.memory_defs.contains_key(&defining)
                        && !self.memory_uses.contains_key(&defining)
                        && !self.memory_phis.contains_key(&defining)
                    {
                        return Err(format!(
                            "MemoryDef {} has invalid defining access {}",
                            def_id, defining
                        ));
                    }
                }
            }
        }

        Ok(())
    }

    /// Update statistics after building or modifying.
    fn update_stats(&mut self) {
        self.stats.total_accesses =
            self.memory_defs.len() + self.memory_uses.len() + self.memory_phis.len();
        self.stats.memory_defs = self.memory_defs.len();
        self.stats.memory_uses = self.memory_uses.len();
        self.stats.memory_phis = self.memory_phis.len();
    }

    /// Identify dead stores in the MemorySSA.
    pub fn identify_dead_stores(&self) -> Vec<u64> {
        self.memory_defs
            .iter()
            .filter(|(_, def)| !def.is_live_on_entry && def.users.is_empty())
            .map(|(id, _)| *id)
            .collect()
    }

    /// Identify redundant loads in the MemorySSA.
    pub fn identify_redundant_loads(&self) -> Vec<u64> {
        let mut redundant = Vec::new();
        let use_ids: Vec<_> = self.memory_uses.keys().copied().collect();

        for i in 0..use_ids.len() {
            let use_a_id = use_ids[i];
            if let Some(use_a) = self.memory_uses.get(&use_a_id) {
                for j in (i + 1)..use_ids.len() {
                    let use_b = &self.memory_uses[&use_ids[j]];
                    if use_b.location == use_a.location
                        && use_b.defining_access == use_a.defining_access
                        && self.dominates_access(use_a_id, use_ids[j])
                    {
                        redundant.push(use_ids[j]);
                    }
                }
            }
        }

        redundant
    }

    /// Get MemorySSA statistics.
    pub fn get_stats(&self) -> &X86MemorySSAStats {
        &self.stats
    }

    /// Get the total number of accesses.
    pub fn total_accesses(&self) -> usize {
        self.memory_defs.len() + self.memory_uses.len() + self.memory_phis.len()
    }
}

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

// ============================================================================
// X86MemorySSAUpdater — incremental MemorySSA updates
// ============================================================================

/// Provides incremental updates to MemorySSA after IR modifications.
#[derive(Debug, Clone)]
pub struct X86MemorySSAUpdater {
    /// Reference to the MemorySSA being updated.
    pub mssa: X86MemorySSA,
    /// Log of updates applied.
    pub update_log: Vec<String>,
}

impl X86MemorySSAUpdater {
    /// Create a new updater for a MemorySSA instance.
    pub fn new(mssa: X86MemorySSA) -> Self {
        X86MemorySSAUpdater {
            mssa,
            update_log: Vec::new(),
        }
    }

    /// Insert a new memory use (load) into MemorySSA.
    pub fn insert_use(&mut self, inst_id: u64, block_id: u64, ptr: u64, size: u64) -> u64 {
        let loc = MemoryLocation::new(ptr, size);

        // Find the defining access: walk up from the last access in this block
        let defining = self.find_defining_access_in_block(block_id, &loc);

        let use_id = self.mssa.next_id();
        let mut mem_use = X86MemoryUse::new(use_id, block_id, inst_id, loc);
        mem_use.defining_access = defining;

        self.mssa.memory_uses.insert(use_id, mem_use);
        self.mssa.inst_to_access.insert(inst_id, use_id);
        self.mssa.is_optimized = false;

        self.update_log.push(format!(
            "Inserted MemoryUse {} for inst {}",
            use_id, inst_id
        ));
        use_id
    }

    /// Insert a new memory definition (store) into MemorySSA.
    pub fn insert_def(&mut self, inst_id: u64, block_id: u64, ptr: u64, size: u64) -> u64 {
        let loc = MemoryLocation::new(ptr, size);

        let defining = self.find_defining_access_in_block(block_id, &loc);

        let def_id = self.mssa.next_id();
        let mut mem_def = X86MemoryDef::new(def_id, block_id, inst_id, loc);
        mem_def.defining_access = defining;

        self.mssa.memory_defs.insert(def_id, mem_def);
        self.mssa.inst_to_access.insert(inst_id, def_id);
        self.mssa.is_optimized = false;

        self.update_log.push(format!(
            "Inserted MemoryDef {} for inst {}",
            def_id, inst_id
        ));
        def_id
    }

    /// Remove a memory access from MemorySSA.
    pub fn remove_access(&mut self, access_id: u64) -> bool {
        let removed = self.mssa.memory_defs.remove(&access_id).is_some()
            || self.mssa.memory_uses.remove(&access_id).is_some()
            || self.mssa.memory_phis.remove(&access_id).is_some();

        if removed {
            self.mssa.is_optimized = false;
            self.mssa.inst_to_access.retain(|_, v| *v != access_id);
            self.update_log
                .push(format!("Removed access {}", access_id));
        }

        removed
    }

    /// Move an instruction from one block to another.
    pub fn move_instruction(&mut self, inst_id: u64, old_block: u64, new_block: u64) {
        if let Some(access_id) = self.mssa.inst_to_access.get(&inst_id).copied() {
            // Update block in the access
            if let Some(def) = self.mssa.memory_defs.get_mut(&access_id) {
                def.block_id = new_block;
            } else if let Some(mem_use) = self.mssa.memory_uses.get_mut(&access_id) {
                mem_use.block_id = new_block;
            }

            // Recompute defining access
            // (Simplified: just mark as not optimized to trigger recomputation)
            self.mssa.is_optimized = false;

            self.update_log.push(format!(
                "Moved inst {} from block {} to block {}",
                inst_id, old_block, new_block
            ));
        }
    }

    /// Find the defining access for a location in a given block.
    fn find_defining_access_in_block(
        &self,
        block_id: u64,
        location: &MemoryLocation,
    ) -> Option<u64> {
        // Walk backwards through accesses in this block to find the last def
        // that may alias with this location.
        let mut last_def: Option<u64> = None;

        // Find all accesses in this block
        let mut block_defs: Vec<(u64, &X86MemoryDef)> = self
            .mssa
            .memory_defs
            .iter()
            .filter(|(_, d)| d.block_id == block_id && !d.is_live_on_entry)
            .map(|(id, d)| (*id, d))
            .collect();

        // Sort by id (approximation of program order)
        block_defs.sort_by_key(|(id, _)| *id);

        for (def_id, def) in &block_defs {
            if location.ptr == def.location.ptr {
                last_def = Some(*def_id);
            }
        }

        if last_def.is_none() {
            // Check predecessors' last defs
            if let Some(preds) = self.mssa.predecessors.get(&block_id) {
                for pred_id in preds {
                    if let Some(phi_id) = self.mssa.block_to_phi.get(pred_id) {
                        return Some(*phi_id);
                    }
                }
            }
        }

        last_def.or(self.mssa.live_on_entry)
    }

    /// Get the update log.
    pub fn get_log(&self) -> &[String] {
        &self.update_log
    }
}

// ============================================================================
// X86MemDep — Memory Dependence Analysis
// ============================================================================

/// Represents a memory dependence query result.
#[derive(Debug, Clone)]
pub struct X86MemDepResult {
    /// The instruction that is the nearest clobbering/defining dependency.
    pub dep_inst: Option<u64>,
    /// The kind of dependence.
    pub dep_kind: X86MemDepKind,
    /// The memory access id in MemorySSA.
    pub access_id: Option<u64>,
}

/// Kinds of memory dependence.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum X86MemDepKind {
    /// No dependence found (proved non-aliasing).
    NonLocal,
    /// Definite dependence on a specific instruction.
    Def,
    /// Clobber dependence — some unknown instruction may clobber.
    Clobber,
    /// Non-functional dependence (e.g., control dependence).
    NonFuncLocal,
    /// Unknown/unanalyzable.
    Unknown,
}

impl fmt::Display for X86MemDepKind {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            X86MemDepKind::NonLocal => write!(f, "NonLocal"),
            X86MemDepKind::Def => write!(f, "Def"),
            X86MemDepKind::Clobber => write!(f, "Clobber"),
            X86MemDepKind::NonFuncLocal => write!(f, "NonFuncLocal"),
            X86MemDepKind::Unknown => write!(f, "Unknown"),
        }
    }
}

/// A key for the memory dependence cache.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct X86MemDepCacheKey {
    /// The pointer being queried about.
    ptr: u64,
    /// The size of the access.
    size: u64,
    /// The instruction from which we're looking backwards.
    from_inst: u64,
}

/// Memory Dependence Analysis with query caching.
#[derive(Debug, Clone)]
pub struct X86MemDep {
    /// Reference to MemorySSA for the function.
    pub memory_ssa: X86MemorySSA,
    /// Cache for memory dependence queries.
    query_cache: HashMap<X86MemDepCacheKey, X86MemDepResult>,
    /// Batch query accumulator.
    batch_queries: Vec<(u64, u64, u64, u64)>,
    /// Maximum cache entries.
    max_cache_size: usize,
    /// Statistics.
    pub stats: X86MemDepStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86MemDepStats {
    pub total_queries: u64,
    pub cache_hits: u64,
    pub cache_misses: u64,
    pub batch_queries: u64,
    pub nonlocal_results: u64,
    pub def_results: u64,
    pub clobber_results: u64,
}

impl X86MemDep {
    /// Create a new MemDep instance.
    pub fn new(memory_ssa: X86MemorySSA) -> Self {
        X86MemDep {
            memory_ssa,
            query_cache: HashMap::new(),
            batch_queries: Vec::new(),
            max_cache_size: X86_MEMDEP_CACHE_SIZE,
            stats: X86MemDepStats::default(),
        }
    }

    /// Get the memory dependence for a pointer at a given instruction.
    ///
    /// Returns the nearest preceding instruction that defines or clobbers
    /// the memory location pointed to by `ptr` with size `size`.
    pub fn get_dependency(&mut self, ptr: u64, size: u64, from_inst: u64) -> X86MemDepResult {
        self.stats.total_queries += 1;

        let cache_key = X86MemDepCacheKey {
            ptr,
            size,
            from_inst,
        };

        // Check cache
        if let Some(cached) = self.query_cache.get(&cache_key) {
            self.stats.cache_hits += 1;
            return cached.clone();
        }
        self.stats.cache_misses += 1;

        let result = self.compute_dependency(ptr, size, from_inst);

        // Cache the result
        if self.query_cache.len() < self.max_cache_size {
            self.query_cache.insert(cache_key, result.clone());
        }

        result
    }

    /// Compute the memory dependence by walking MemorySSA.
    fn compute_dependency(&self, ptr: u64, size: u64, from_inst: u64) -> X86MemDepResult {
        let loc = MemoryLocation::new(ptr, size);

        // Get the memory access for the instruction
        let access_id = self.memory_ssa.get_memory_access(from_inst);

        match access_id {
            Some(acc_id) => {
                // Use MemorySSA's clobber walker to find the nearest clobber
                let clobber = self.memory_ssa.get_clobbering_access(acc_id, &loc);

                match clobber {
                    Some(clobber_id) => {
                        // Map clobber access back to instruction
                        if let Some(def) = self.memory_ssa.memory_defs.get(&clobber_id) {
                            if def.is_live_on_entry {
                                X86MemDepResult {
                                    dep_inst: None,
                                    dep_kind: X86MemDepKind::NonLocal,
                                    access_id: Some(clobber_id),
                                }
                            } else {
                                X86MemDepResult {
                                    dep_inst: Some(def.store_inst),
                                    dep_kind: X86MemDepKind::Def,
                                    access_id: Some(clobber_id),
                                }
                            }
                        } else if self.memory_ssa.memory_phis.contains_key(&clobber_id) {
                            X86MemDepResult {
                                dep_inst: None,
                                dep_kind: X86MemDepKind::Clobber,
                                access_id: Some(clobber_id),
                            }
                        } else {
                            X86MemDepResult {
                                dep_inst: None,
                                dep_kind: X86MemDepKind::Unknown,
                                access_id: Some(clobber_id),
                            }
                        }
                    }
                    None => X86MemDepResult {
                        dep_inst: None,
                        dep_kind: X86MemDepKind::NonLocal,
                        access_id: None,
                    },
                }
            }
            None => {
                // No memory access found for this instruction; walk instructions
                // manually
                X86MemDepResult {
                    dep_inst: None,
                    dep_kind: X86MemDepKind::Unknown,
                    access_id: None,
                }
            }
        }
    }

    /// Get the pointer dependency — the nearest instruction that defines the
    /// pointer value itself (not just memory clobbered through it).
    pub fn get_pointer_dependency(&mut self, ptr: u64, from_inst: u64) -> X86MemDepResult {
        // For pointer dependency, we query with size 0 (pointer-sized)
        self.get_dependency(ptr, 8, from_inst)
    }

    /// Add a query to the batch.
    pub fn batch_add_query(&mut self, ptr: u64, size: u64, from_inst: u64) {
        self.batch_queries
            .push((ptr, size, from_inst, self.stats.total_queries));

        // If batch is large enough, flush it
        if self.batch_queries.len() >= X86_BATCH_QUERY_THRESHOLD {
            // Don't auto-flush; let the caller explicitly call flush_batch
        }
    }

    /// Flush all batched queries and return results.
    pub fn flush_batch(&mut self) -> Vec<(u64, X86MemDepResult)> {
        let mut results = Vec::with_capacity(self.batch_queries.len());

        for &(ptr, size, from_inst, _seq) in &self.batch_queries {
            self.stats.total_queries += 1;
            self.stats.batch_queries += 1;

            let cache_key = X86MemDepCacheKey {
                ptr,
                size,
                from_inst,
            };

            if let Some(cached) = self.query_cache.get(&cache_key) {
                self.stats.cache_hits += 1;
                results.push((from_inst, cached.clone()));
            } else {
                self.stats.cache_misses += 1;
                let result = self.compute_dependency(ptr, size, from_inst);
                if self.query_cache.len() < self.max_cache_size {
                    self.query_cache.insert(cache_key, result.clone());
                }
                results.push((from_inst, result));
            }
        }

        self.batch_queries.clear();
        results
    }

    /// Clear the query cache.
    pub fn invalidate_cache(&mut self) {
        self.query_cache.clear();
    }

    /// Invalidate cache entries for a specific instruction.
    pub fn invalidate_inst(&mut self, inst_id: u64) {
        self.query_cache.retain(|key, _| key.from_inst != inst_id);
    }

    /// Get statistics.
    pub fn get_stats(&self) -> &X86MemDepStats {
        &self.stats
    }

    /// Get the number of pending batch queries.
    pub fn pending_batch_queries(&self) -> usize {
        self.batch_queries.len()
    }

    /// Get the cache size.
    pub fn cache_size(&self) -> usize {
        self.query_cache.len()
    }
}

// ============================================================================
// X86AliasAnalysis — top-level alias analysis orchestrator
// ============================================================================

/// The top-level X86 alias analysis orchestrator that combines all
/// individual analyses into a single pipeline.
#[derive(Debug, Clone)]
pub struct X86AliasAnalysis {
    /// Basic alias analysis (type + GEP).
    pub basic_aa: X86BasicAA,
    /// CFL Andersen's-style alias analysis.
    pub cfl_aa: X86CFLAA,
    /// SCEV-based alias analysis.
    pub scev_aa: X86SCEVAA,
    /// Global mod/ref analysis.
    pub globals_mod_ref: X86GlobalsModRef,
    /// Type-based alias analysis.
    pub tbaa: X86TypeBasedAA,
    /// Scoped noalias alias analysis.
    pub scoped_noalias_aa: X86ScopedNoAliasAA,
    /// Memory SSA for the function.
    pub memory_ssa: X86MemorySSA,
    /// Memory dependence analysis.
    pub mem_dep: Option<X86MemDep>,
    /// Alias sets for this function.
    pub alias_sets: HashMap<u64, AliasSet>,
    /// Points-to information.
    pub points_to: HashMap<u64, PointsToSet>,
    /// Combined statistics.
    pub total_queries: u64,
    /// Cache for alias results (ptr_a, ptr_b, size_a, size_b) -> AliasResult.
    alias_cache: HashMap<(u64, u64, u64, u64), AliasResult>,
    /// Maximum alias cache size.
    max_alias_cache_size: usize,
    /// Whether this analysis has been fully initialized.
    pub initialized: bool,
}

impl X86AliasAnalysis {
    /// Create a new X86AliasAnalysis with all sub-analyses.
    pub fn new() -> Self {
        X86AliasAnalysis {
            basic_aa: X86BasicAA::new(),
            cfl_aa: X86CFLAA::new(),
            scev_aa: X86SCEVAA::new(),
            globals_mod_ref: X86GlobalsModRef::new(),
            tbaa: X86TypeBasedAA::new(),
            scoped_noalias_aa: X86ScopedNoAliasAA::new(),
            memory_ssa: X86MemorySSA::new(),
            mem_dep: None,
            alias_sets: HashMap::new(),
            points_to: HashMap::new(),
            total_queries: 0,
            alias_cache: HashMap::new(),
            max_alias_cache_size: 2048,
            initialized: false,
        }
    }

    /// Initialize all sub-analyses for a function.
    pub fn initialize(&mut self) {
        // Solve CFL-AA
        self.cfl_aa.solve();

        // Optimize MemorySSA
        self.memory_ssa.optimize_uses();

        // Create MemDep
        self.mem_dep = Some(X86MemDep::new(self.memory_ssa.clone()));

        self.initialized = true;
    }

    /// Perform a full alias query between two memory locations.
    ///
    /// Returns the most precise result from the analysis pipeline.
    pub fn alias(&mut self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> X86AliasResult {
        self.total_queries += 1;

        // Check cache
        let cache_key = (loc_a.ptr, loc_b.ptr, loc_a.size, loc_b.size);
        if let Some(&cached) = self.alias_cache.get(&cache_key) {
            return X86AliasResult::new(cached, "cache");
        }

        // --- BasicAA ---
        let basic_result = self.basic_aa.alias(loc_a, loc_b);
        if basic_result == AliasResult::NoAlias || basic_result == AliasResult::MustAlias {
            self.cache_result(cache_key, basic_result);
            return X86AliasResult::new(basic_result, "BasicAA");
        }

        // --- ScopedNoAliasAA ---
        if loc_a.has_scoped_noalias() || loc_b.has_scoped_noalias() {
            let scoped_result = self.scoped_noalias_aa.alias(loc_a, loc_b);
            if scoped_result == AliasResult::NoAlias {
                self.cache_result(cache_key, scoped_result);
                return X86AliasResult::new(scoped_result, "ScopedNoAliasAA");
            }
        }

        // --- TypeBasedAA ---
        if loc_a.has_tbaa() || loc_b.has_tbaa() {
            let tbaa_result = self.tbaa.alias(None, None); // TODO: pass actual tags
            if tbaa_result == AliasResult::NoAlias {
                self.cache_result(cache_key, tbaa_result);
                return X86AliasResult::new(tbaa_result, "TypeBasedAA");
            }
        }

        // --- SCEV-AA ---
        let scev_result = self.scev_aa.alias(loc_a, loc_b);
        if scev_result == AliasResult::NoAlias {
            self.cache_result(cache_key, scev_result);
            return X86AliasResult::new(scev_result, "SCEVAA");
        }

        // --- CFL-AA ---
        let cfl_result = self.cfl_aa.may_alias(loc_a.ptr, loc_b.ptr);
        if cfl_result == AliasResult::NoAlias {
            self.cache_result(cache_key, cfl_result);
            return X86AliasResult::new(cfl_result, "CFLAA");
        }

        // Default: return the best result we have
        let final_result = AliasResult::MayAlias;
        self.cache_result(cache_key, final_result);
        X86AliasResult::new(final_result, "default")
    }

    /// Helper to cache alias results.
    fn cache_result(&mut self, key: (u64, u64, u64, u64), result: AliasResult) {
        if self.alias_cache.len() >= self.max_alias_cache_size {
            // Evict oldest entry (simplified: clear half)
            let half = self.max_alias_cache_size / 2;
            let keys: Vec<_> = self.alias_cache.keys().take(half).cloned().collect();
            for k in keys {
                self.alias_cache.remove(&k);
            }
        }
        self.alias_cache.insert(key, result);
    }

    /// Get ModRefInfo for a call instruction.
    pub fn get_mod_ref_for_call(&mut self, func_id: u64, loc: &MemoryLocation) -> ModRefInfo {
        // Check globals mod/ref first
        let gmr = self.globals_mod_ref.get_mod_ref_for_call(func_id, loc);
        if gmr != ModRefInfo::ModRef {
            return gmr;
        }

        // Check if the location points to constant memory
        if self.basic_aa.points_to_constant_memory(loc) {
            return ModRefInfo::Ref;
        }

        ModRefInfo::ModRef
    }

    /// Check if a location points to constant memory.
    pub fn points_to_constant_memory(&self, loc: &MemoryLocation) -> bool {
        self.basic_aa.points_to_constant_memory(loc)
    }

    /// Get the points-to set for a pointer.
    pub fn get_points_to(&self, ptr: u64) -> PointsToSet {
        self.cfl_aa.get_points_to(ptr)
    }

    /// Get or create an alias set.
    pub fn get_alias_set(&mut self, ptr: u64) -> &mut AliasSet {
        self.alias_sets
            .entry(ptr)
            .or_insert_with(|| AliasSet::new(ptr))
    }

    /// Merge two alias sets.
    pub fn merge_alias_sets(&mut self, ptr_a: u64, ptr_b: u64) {
        // Create entries if needed
        self.alias_sets
            .entry(ptr_a)
            .or_insert_with(|| AliasSet::new(ptr_a));
        self.alias_sets
            .entry(ptr_b)
            .or_insert_with(|| AliasSet::new(ptr_b));

        // Clone set_b to avoid double borrow
        let set_b = self.alias_sets[&ptr_b].clone();
        if let Some(set_a) = self.alias_sets.get_mut(&ptr_a) {
            set_a.merge(&set_b);
        }
    }

    /// Invalidate all caches.
    pub fn invalidate_all(&mut self) {
        self.alias_cache.clear();
        if let Some(ref mut mem_dep) = self.mem_dep {
            mem_dep.invalidate_cache();
        }
    }

    /// Build MemorySSA for the function from operations.
    pub fn build_memory_ssa(
        &mut self,
        ops: &[(u64, u64, X86Opcode, u64, u64, bool)],
        block_order: &[u64],
    ) {
        self.memory_ssa.build(ops, block_order);
    }

    /// Run MemorySSA optimizations.
    pub fn optimize_memory_ssa(&mut self) {
        self.memory_ssa.optimize_uses();
    }

    /// Get memory dependence for a location.
    pub fn get_mem_dep(&mut self, ptr: u64, size: u64, from_inst: u64) -> X86MemDepResult {
        if self.mem_dep.is_none() {
            self.initialize();
        }
        self.mem_dep
            .as_mut()
            .map(|md| md.get_dependency(ptr, size, from_inst))
            .unwrap_or(X86MemDepResult {
                dep_inst: None,
                dep_kind: X86MemDepKind::Unknown,
                access_id: None,
            })
    }

    /// Print a summary of analysis statistics.
    pub fn print_stats(&self) -> String {
        let mut s = String::new();
        s.push_str(&format!("=== X86 Alias Analysis Stats ===\n"));
        s.push_str(&format!("Total queries: {}\n", self.total_queries));
        s.push_str(&format!(
            "BasicAA: total={}, noalias={}, mustalias={}, mayalias={}\n",
            self.basic_aa.stats.total_queries,
            self.basic_aa.stats.noalias_results,
            self.basic_aa.stats.mustalias_results,
            self.basic_aa.stats.mayalias_results
        ));
        s.push_str(&format!(
            "CFLAA: nodes={}, edges={}, iterations={}, queries={}\n",
            self.cfl_aa.stats.total_nodes,
            self.cfl_aa.stats.total_edges,
            self.cfl_aa.stats.iterations_to_fixpoint,
            self.cfl_aa.stats.queries_resolved,
        ));
        s.push_str(&format!(
            "SCEVAA: queries={}, noalias={}, disambiguations={}\n",
            self.scev_aa.stats.total_queries,
            self.scev_aa.stats.noalias_results,
            self.scev_aa.stats.scev_disambiguations,
        ));
        s.push_str(&format!(
            "GlobalsModRef: globals={}, functions={}, noalias={}\n",
            self.globals_mod_ref.stats.total_globals,
            self.globals_mod_ref.stats.total_functions,
            self.globals_mod_ref.stats.noalias_results,
        ));
        s.push_str(&format!(
            "TypeBasedAA: nodes={}, queries={}, noalias={}\n",
            self.tbaa.stats.total_nodes,
            self.tbaa.stats.total_queries,
            self.tbaa.stats.noalias_results,
        ));
        s.push_str(&format!(
            "ScopedNoAliasAA: queries={}, noalias={}, disambiguations={}\n",
            self.scoped_noalias_aa.stats.total_queries,
            self.scoped_noalias_aa.stats.noalias_results,
            self.scoped_noalias_aa.stats.scoped_disambiguations,
        ));
        s.push_str(&format!(
            "MemorySSA: accesses={}, defs={}, uses={}, phis={}, optimized={}\n",
            self.memory_ssa.stats.total_accesses,
            self.memory_ssa.stats.memory_defs,
            self.memory_ssa.stats.memory_uses,
            self.memory_ssa.stats.memory_phis,
            self.memory_ssa.stats.optimized_uses,
        ));
        s.push_str(&format!("AliasSets: {}\n", self.alias_sets.len()));
        s
    }
}

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

// ============================================================================
// Helper Functions
// ============================================================================

/// Build a complete X86 alias analysis pipeline.
pub fn build_x86_alias_analysis_pipeline() -> X86AliasAnalysis {
    let mut aa = X86AliasAnalysis::new();
    aa.initialize();
    aa
}

/// Quick alias check between two memory locations using BasicAA only.
pub fn quick_alias_check(loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
    let mut basic_aa = X86BasicAA::new();
    basic_aa.alias(loc_a, loc_b)
}

/// Check if an instruction is a memory operation.
pub fn is_memory_operation(opcode: X86Opcode) -> bool {
    matches!(
        opcode,
        X86Opcode::Load
            | X86Opcode::Store
            | X86Opcode::AtomicCmpXchg
            | X86Opcode::AtomicRMW
            | X86Opcode::Alloca
    )
}

/// Check if an instruction may read memory.
pub fn may_read_memory(opcode: X86Opcode) -> bool {
    matches!(
        opcode,
        X86Opcode::Load
            | X86Opcode::AtomicCmpXchg
            | X86Opcode::AtomicRMW
            | X86Opcode::Call
            | X86Opcode::Invoke
    )
}

/// Check if an instruction may write memory.
pub fn may_write_memory(opcode: X86Opcode) -> bool {
    matches!(
        opcode,
        X86Opcode::Store
            | X86Opcode::AtomicCmpXchg
            | X86Opcode::AtomicRMW
            | X86Opcode::Call
            | X86Opcode::Invoke
    )
}

/// Extract mod/ref info from common intrinsic function names.
pub fn get_intrinsic_mod_ref(name: &str) -> Option<ModRefInfo> {
    match name {
        "llvm.memcpy" | "llvm.memmove" | "llvm.memset" => Some(ModRefInfo::ModRef),
        "llvm.sqrt" | "llvm.sin" | "llvm.cos" | "llvm.exp" | "llvm.log" => {
            Some(ModRefInfo::NoModRef)
        }
        "llvm.lifetime.start"
        | "llvm.lifetime.end"
        | "llvm.invariant.start"
        | "llvm.invariant.end" => Some(ModRefInfo::NoModRef),
        "llvm.assume" => Some(ModRefInfo::NoModRef),
        "llvm.donothing" => Some(ModRefInfo::NoModRef),
        "llvm.experimental.noalias.scope.decl" => Some(ModRefInfo::NoModRef),
        _ => None,
    }
}

/// Check if two pointer-sized values have identical base objects (same alloca/global).
pub fn have_same_base_object(aa: &X86AliasAnalysis, ptr_a: u64, ptr_b: u64) -> bool {
    // Check if they are literally the same alloca
    if ptr_a == ptr_b && ptr_a != 0 {
        if aa.basic_aa.alloca_sizes.contains_key(&ptr_a) {
            return true;
        }
        if aa.basic_aa.global_sizes.contains_key(&ptr_a) {
            return true;
        }
    }
    false
}

/// Get the underlying object for a pointer (alloca or global).
pub fn get_underlying_object(aa: &X86AliasAnalysis, ptr: u64) -> Option<u64> {
    // Check if ptr itself is an object
    if aa.basic_aa.alloca_sizes.contains_key(&ptr) || aa.basic_aa.global_sizes.contains_key(&ptr) {
        return Some(ptr);
    }

    // Walk GEP chain
    let mut current = ptr;
    let mut visited = HashSet::new();
    for _ in 0..X86_ALIAS_MAX_RECURSION_DEPTH {
        if visited.contains(&current) {
            break;
        }
        visited.insert(current);
        if aa.basic_aa.alloca_sizes.contains_key(&current)
            || aa.basic_aa.global_sizes.contains_key(&current)
        {
            return Some(current);
        }
        match aa.basic_aa.gep_bases.get(&current) {
            Some(base) => current = *base,
            None => break,
        }
    }
    None
}

/// Compute the byte offset of a pointer from its base object.
pub fn get_pointer_offset(aa: &X86AliasAnalysis, ptr: u64) -> Option<i64> {
    if aa.basic_aa.alloca_sizes.contains_key(&ptr) || aa.basic_aa.global_sizes.contains_key(&ptr) {
        return Some(0);
    }

    aa.basic_aa.gep_offsets.get(&ptr).map(|&(_, offset)| offset)
}

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

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

    // -----------------------------------------------------------------------
    // Helper functions for tests
    // -----------------------------------------------------------------------

    fn make_memloc(ptr: u64, size: u64) -> MemoryLocation {
        MemoryLocation::new(ptr, size)
    }

    fn make_tbaa_tag(access_type_id: u64, base_type_id: u64, offset: u64) -> TBAATag {
        TBAATag::new(access_type_id, base_type_id, offset)
    }

    fn make_memloc_with_tbaa(ptr: u64, size: u64, _tag_str: &str) -> MemoryLocation {
        MemoryLocation {
            ptr,
            size,
            tbaa_tag: Some(_tag_str.to_string()),
            noalias_domain: None,
            noalias_scopes: Vec::new(),
            has_known_size: size > 0,
        }
    }

    fn make_memloc_with_noalias(
        ptr: u64,
        size: u64,
        domain: u64,
        scopes: Vec<u64>,
    ) -> MemoryLocation {
        MemoryLocation {
            ptr,
            size,
            tbaa_tag: None,
            noalias_domain: Some(domain.to_string()),
            noalias_scopes: scopes.iter().map(|s| s.to_string()).collect(),
            has_known_size: size > 0,
        }
    }

    // -----------------------------------------------------------------------
    // AliasResult tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_alias_result_display() {
        assert_eq!(format!("{}", AliasResult::NoAlias), "NoAlias");
        assert_eq!(format!("{}", AliasResult::MayAlias), "MayAlias");
        assert_eq!(format!("{}", AliasResult::PartialAlias), "PartialAlias");
        assert_eq!(format!("{}", AliasResult::MustAlias), "MustAlias");
    }

    #[test]
    fn test_alias_result_ordering() {
        assert!(AliasResult::NoAlias < AliasResult::MayAlias);
        assert!(AliasResult::MayAlias < AliasResult::PartialAlias);
        assert!(AliasResult::PartialAlias < AliasResult::MustAlias);
    }

    #[test]
    fn test_alias_result_meet() {
        assert_eq!(
            AliasResult::meet(AliasResult::NoAlias, AliasResult::MayAlias),
            AliasResult::NoAlias
        );
        assert_eq!(
            AliasResult::meet(AliasResult::MustAlias, AliasResult::MayAlias),
            AliasResult::MayAlias
        );
        assert_eq!(
            AliasResult::meet(AliasResult::MayAlias, AliasResult::PartialAlias),
            AliasResult::MayAlias
        );
    }

    #[test]
    fn test_alias_result_is_noalias() {
        assert!(AliasResult::NoAlias.is_no_alias());
        assert!(!AliasResult::MayAlias.is_no_alias());
        assert!(!AliasResult::MustAlias.is_no_alias());
    }

    #[test]
    fn test_alias_result_is_mustalias() {
        assert!(!AliasResult::NoAlias.is_must_alias());
        assert!(AliasResult::MustAlias.is_must_alias());
        assert!(!AliasResult::MayAlias.is_must_alias());
    }

    // -----------------------------------------------------------------------
    // ModRefInfo tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_mod_ref_info_does_ref() {
        assert!(!ModRefInfo::NoModRef.does_ref());
        assert!(ModRefInfo::Ref.does_ref());
        assert!(!ModRefInfo::Mod.does_ref());
        assert!(ModRefInfo::ModRef.does_ref());
    }

    #[test]
    fn test_mod_ref_info_does_mod() {
        assert!(!ModRefInfo::NoModRef.does_mod());
        assert!(!ModRefInfo::Ref.does_mod());
        assert!(ModRefInfo::Mod.does_mod());
        assert!(ModRefInfo::ModRef.does_mod());
    }

    #[test]
    fn test_mod_ref_info_union() {
        assert_eq!(
            ModRefInfo::union(ModRefInfo::NoModRef, ModRefInfo::Ref),
            ModRefInfo::Ref
        );
        assert_eq!(
            ModRefInfo::union(ModRefInfo::Ref, ModRefInfo::Mod),
            ModRefInfo::ModRef
        );
        assert_eq!(
            ModRefInfo::union(ModRefInfo::Mod, ModRefInfo::Mod),
            ModRefInfo::Mod
        );
    }

    #[test]
    fn test_mod_ref_info_meet() {
        assert_eq!(
            ModRefInfo::meet(ModRefInfo::ModRef, ModRefInfo::Ref),
            ModRefInfo::Ref
        );
        assert_eq!(
            ModRefInfo::meet(ModRefInfo::Ref, ModRefInfo::Mod),
            ModRefInfo::NoModRef
        );
    }

    #[test]
    fn test_mod_ref_info_clear_mod() {
        let mut info = ModRefInfo::ModRef;
        info.clear_mod();
        assert_eq!(info, ModRefInfo::Ref);

        let mut info = ModRefInfo::Mod;
        info.clear_mod();
        assert_eq!(info, ModRefInfo::NoModRef);
    }

    #[test]
    fn test_mod_ref_info_clear_ref() {
        let mut info = ModRefInfo::ModRef;
        info.clear_ref();
        assert_eq!(info, ModRefInfo::Mod);

        let mut info = ModRefInfo::Ref;
        info.clear_ref();
        assert_eq!(info, ModRefInfo::NoModRef);
    }

    #[test]
    fn test_mod_ref_info_display() {
        assert_eq!(format!("{}", ModRefInfo::NoModRef), "NoModRef");
        assert_eq!(format!("{}", ModRefInfo::Ref), "Ref");
        assert_eq!(format!("{}", ModRefInfo::Mod), "Mod");
        assert_eq!(format!("{}", ModRefInfo::ModRef), "ModRef");
    }

    // -----------------------------------------------------------------------
    // MemoryLocation tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_memory_location_new() {
        let loc = MemoryLocation::new(100, 8);
        assert_eq!(loc.ptr, 100);
        assert_eq!(loc.size, 8);
        assert!(loc.has_known_size);
        assert!(!loc.has_tbaa());
        assert!(!loc.has_scoped_noalias());
    }

    #[test]
    fn test_memory_location_with_tbaa() {
        let loc = MemoryLocation::new(100, 8).with_tbaa("int".to_string());
        assert!(loc.has_tbaa());
        assert_eq!(loc.tbaa_tag, Some("int".to_string()));
    }

    #[test]
    fn test_memory_location_with_scoped_noalias() {
        let loc = MemoryLocation::new(100, 8)
            .with_scoped_noalias("1".to_string(), vec!["10".to_string(), "20".to_string()]);
        assert!(loc.has_scoped_noalias());
        assert_eq!(loc.noalias_domain, Some("1".to_string()));
        assert_eq!(loc.noalias_scopes.len(), 2);
    }

    #[test]
    fn test_memory_location_unknown_size() {
        let loc = MemoryLocation::new(100, 0);
        assert!(!loc.has_known_size);
    }

    // -----------------------------------------------------------------------
    // PointsToSet tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_points_to_set_empty() {
        let pts = PointsToSet::empty();
        assert!(pts.is_empty());
        assert!(!pts.includes_null);
        assert!(!pts.includes_unknown);
    }

    #[test]
    fn test_points_to_set_singleton() {
        let pts = PointsToSet::singleton(42);
        assert_eq!(pts.len(), 1);
        assert!(pts.objects.contains(&42));
    }

    #[test]
    fn test_points_to_set_unknown() {
        let pts = PointsToSet::unknown();
        assert!(pts.includes_unknown);
        assert!(pts.includes_null);
    }

    #[test]
    fn test_points_to_set_may_alias() {
        let mut a = PointsToSet::singleton(10);
        let b = PointsToSet::singleton(10);
        assert!(a.may_alias(&b));

        let c = PointsToSet::singleton(20);
        assert!(!a.may_alias(&c));

        a.includes_unknown = true;
        assert!(a.may_alias(&c));
    }

    #[test]
    fn test_points_to_set_noalias() {
        let a = PointsToSet::noalias();
        let b = PointsToSet::singleton(10);
        assert!(!a.may_alias(&b));
    }

    #[test]
    fn test_points_to_set_union() {
        let mut a = PointsToSet::singleton(1);
        let b = PointsToSet::singleton(2);
        a.union_with(&b);
        assert_eq!(a.len(), 2);
        assert!(a.objects.contains(&1));
        assert!(a.objects.contains(&2));
    }

    // -----------------------------------------------------------------------
    // AliasSet tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_alias_set_new() {
        let set = AliasSet::new(100);
        assert_eq!(set.id, 100);
        assert!(set.pointers.is_empty());
        assert!(!set.has_unknown);
    }

    #[test]
    fn test_alias_set_add_pointer() {
        let mut set = AliasSet::new(0);
        set.add_pointer(42);
        assert!(set.pointers.contains(&42));
        set.add_pointer(99);
        assert_eq!(set.pointers.len(), 2);
    }

    #[test]
    fn test_alias_set_merge() {
        let mut a = AliasSet::new(1);
        a.add_pointer(10);
        a.access_type = AliasSetAccess::Ref;

        let mut b = AliasSet::new(2);
        b.add_pointer(20);
        b.access_type = AliasSetAccess::Mod;

        a.merge(&b);
        assert!(a.pointers.contains(&10));
        assert!(a.pointers.contains(&20));
        assert_eq!(a.access_type, AliasSetAccess::ModRef);
    }

    // -----------------------------------------------------------------------
    // X86BasicAA tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_basic_aa_new() {
        let basic = X86BasicAA::new();
        assert!(basic.alloca_sizes.is_empty());
        assert!(basic.global_sizes.is_empty());
    }

    #[test]
    fn test_basic_aa_same_pointer_must_alias() {
        let mut basic = X86BasicAA::new();
        let loc_a = make_memloc(100, 8);
        let loc_b = make_memloc(100, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::MustAlias);
    }

    #[test]
    fn test_basic_aa_different_allocas_no_alias() {
        let mut basic = X86BasicAA::new();
        basic.register_alloca(100, 8);
        basic.register_alloca(200, 8);
        let loc_a = make_memloc(100, 8);
        let loc_b = make_memloc(200, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_basic_aa_different_globals_no_alias() {
        let mut basic = X86BasicAA::new();
        basic.register_global(300, 4, false);
        basic.register_global(400, 4, false);
        let loc_a = make_memloc(300, 4);
        let loc_b = make_memloc(400, 4);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_basic_aa_alloca_vs_global_no_alias() {
        let mut basic = X86BasicAA::new();
        basic.register_alloca(100, 8);
        basic.register_global(500, 8, false);
        let loc_a = make_memloc(100, 8);
        let loc_b = make_memloc(500, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_basic_aa_gep_same_base_different_offsets() {
        let mut basic = X86BasicAA::new();
        // Register a base alloca
        basic.register_alloca(1, 64);
        // Register GEPs: gep1 = base + 0, gep2 = base + 16
        basic.register_gep(10, 1, 0);
        basic.register_gep(20, 1, 16);

        let loc_a = make_memloc(10, 8); // bytes 0-8
        let loc_b = make_memloc(20, 8); // bytes 16-24

        // These should not overlap
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_basic_aa_gep_same_base_overlapping() {
        let mut basic = X86BasicAA::new();
        basic.register_alloca(1, 64);
        basic.register_gep(10, 1, 0);
        basic.register_gep(20, 1, 4); // Overlaps with bytes 0-8

        let loc_a = make_memloc(10, 8); // bytes 0-8
        let loc_b = make_memloc(20, 8); // bytes 4-12

        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::PartialAlias);
    }

    #[test]
    fn test_basic_aa_gep_different_bases_no_alias() {
        let mut basic = X86BasicAA::new();
        basic.register_alloca(1, 64);
        basic.register_alloca(2, 64);
        basic.register_gep(10, 1, 0);
        basic.register_gep(20, 2, 0);

        let loc_a = make_memloc(10, 8);
        let loc_b = make_memloc(20, 8);

        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_basic_aa_function_pointer_no_alias() {
        let mut basic = X86BasicAA::new();
        basic.function_addresses.insert(999);
        let loc_a = make_memloc(999, 8);
        let loc_b = make_memloc(100, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_basic_aa_points_to_constant_memory() {
        let mut basic = X86BasicAA::new();
        basic.register_global(500, 8, true);
        let loc = make_memloc(500, 8);
        assert!(basic.points_to_constant_memory(&loc));

        let loc2 = make_memloc(600, 8);
        assert!(!basic.points_to_constant_memory(&loc2));
    }

    #[test]
    fn test_basic_aa_stats() {
        let mut basic = X86BasicAA::new();
        basic.register_alloca(100, 4);
        basic.register_alloca(200, 4);

        let loc_a = make_memloc(100, 4);
        let loc_b = make_memloc(200, 4);
        basic.alias(&loc_a, &loc_b);

        let stats = basic.get_stats();
        assert_eq!(stats.total_queries, 1);
        assert_eq!(stats.noalias_results, 1);
    }

    // -----------------------------------------------------------------------
    // X86CFLAA tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_cfl_aa_new() {
        let cfl = X86CFLAA::new();
        assert!(!cfl.solved);
        assert_eq!(cfl.stats.total_nodes, 0);
    }

    #[test]
    fn test_cfl_aa_register_and_query() {
        let mut cfl = X86CFLAA::new();
        cfl.register_pointer(1);
        cfl.register_pointer(2);
        cfl.add_points_to(1, 100);
        cfl.add_points_to(2, 200);
        cfl.solve();

        assert_eq!(cfl.may_alias(1, 1), AliasResult::MustAlias);
        assert_eq!(cfl.may_alias(1, 2), AliasResult::NoAlias);
    }

    #[test]
    fn test_cfl_aa_assign_propagation() {
        let mut cfl = X86CFLAA::new();
        cfl.register_pointer(1);
        cfl.register_pointer(2);
        cfl.add_points_to(1, 100);
        cfl.add_assign(2, 1); // 2 = 1
        cfl.solve();

        let pts2 = cfl.get_points_to(2);
        assert!(pts2.objects.contains(&100));
    }

    #[test]
    fn test_cfl_aa_load_store() {
        let mut cfl = X86CFLAA::new();
        cfl.register_pointer(1); // base pointer
        cfl.register_pointer(2); // loaded value
        cfl.register_pointer(3); // stored value

        // Object at memory location 100 holds value 200
        cfl.add_points_to(1, 100); // base points to object 100
        cfl.add_points_to(100, 200); // object 100 holds value 200

        // Load: 2 = *1
        cfl.add_load(2, 1);

        // Store: *1 = 3 (value 300)
        cfl.add_points_to(3, 300);
        cfl.add_store(1, 3);

        cfl.solve();

        // After load, 2 should point to what *1 points to (200)
        let pts2 = cfl.get_points_to(2);
        // Load propagation happens post-fixpoint
        assert!(pts2.objects.contains(&200));

        // After store, *1 (object 100) should get 3's points-to (300)
        let pts100 = cfl.get_points_to(100);
        assert!(pts100.objects.contains(&300));
    }

    #[test]
    fn test_cfl_aa_escaped() {
        let mut cfl = X86CFLAA::new();
        cfl.register_pointer(1);
        cfl.mark_escaped(1);
        cfl.solve();

        let pts = cfl.get_points_to(1);
        assert!(pts.includes_unknown);
    }

    #[test]
    fn test_cfl_aa_must_alias() {
        let mut cfl = X86CFLAA::new();
        cfl.register_pointer(1);
        cfl.register_pointer(2);
        cfl.add_points_to(1, 42);
        cfl.add_points_to(2, 42);
        cfl.solve();

        assert!(cfl.must_alias(1, 2));
    }

    #[test]
    fn test_cfl_aa_stats_tracking() {
        let mut cfl = X86CFLAA::new();
        cfl.register_pointer(1);
        cfl.register_pointer(2);
        cfl.add_assign(1, 2);
        cfl.add_load(1, 2);
        cfl.add_store(1, 2);
        cfl.solve();

        assert_eq!(cfl.stats.assign_edges, 1);
        assert_eq!(cfl.stats.load_edges, 1);
        assert_eq!(cfl.stats.store_edges, 1);
    }

    // -----------------------------------------------------------------------
    // X86SCEVExpr / SCEVAA tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_scev_expr_constant() {
        let expr = X86SCEVExpr::constant(42);
        assert!(expr.is_constant());
        assert_eq!(expr.evaluate_at(10), Some(42));
    }

    #[test]
    fn test_scev_expr_addrec() {
        // {5, +, 2} — starts at 5, increments by 2 each iteration
        let expr = X86SCEVExpr::addrec(X86SCEVExpr::constant(5), X86SCEVExpr::constant(2), 1);
        assert_eq!(expr.evaluate_at(0), Some(5));
        assert_eq!(expr.evaluate_at(1), Some(7));
        assert_eq!(expr.evaluate_at(3), Some(11));
    }

    #[test]
    fn test_scev_expr_arithmetic() {
        let a = X86SCEVExpr::constant(3);
        let b = X86SCEVExpr::constant(4);
        let sum = X86SCEVExpr::Add(Box::new(a), Box::new(b));
        assert_eq!(sum.evaluate_at(0), Some(7));

        let a = X86SCEVExpr::constant(3);
        let b = X86SCEVExpr::constant(4);
        let prod = X86SCEVExpr::Mul(Box::new(a), Box::new(b));
        assert_eq!(prod.evaluate_at(0), Some(12));
    }

    #[test]
    fn test_scev_expr_loop_invariant() {
        let expr = X86SCEVExpr::constant(42);
        assert!(expr.is_loop_invariant(1));

        let addrec = X86SCEVExpr::addrec(X86SCEVExpr::constant(0), X86SCEVExpr::constant(1), 1);
        assert!(!addrec.is_loop_invariant(1));
        assert!(addrec.is_loop_invariant(2));
    }

    #[test]
    fn test_scev_aa_new() {
        let scev_aa = X86SCEVAA::new();
        assert!(scev_aa.scev_map.is_empty());
    }

    #[test]
    fn test_scev_aa_noalias() {
        let mut scev_aa = X86SCEVAA::new();
        // Two pointers at constant offsets: ptr at 0, ptr at 64
        scev_aa.register_scev(1, X86SCEVExpr::constant(0));
        scev_aa.register_scev(2, X86SCEVExpr::constant(64));

        let loc_a = make_memloc(1, 8);
        let loc_b = make_memloc(2, 8);

        // 0..8 vs 64..72 — clearly no overlap when size=8 and diff=64
        assert_eq!(scev_aa.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_scev_aa_may_alias() {
        let mut scev_aa = X86SCEVAA::new();
        // Two pointers close together
        scev_aa.register_scev(1, X86SCEVExpr::constant(0));
        scev_aa.register_scev(2, X86SCEVExpr::constant(4));

        let loc_a = make_memloc(1, 8);
        let loc_b = make_memloc(2, 8);

        assert_eq!(scev_aa.alias(&loc_a, &loc_b), AliasResult::MayAlias);
    }

    #[test]
    fn test_scev_aa_addrec_noalias() {
        let mut scev_aa = X86SCEVAA::new();
        // Two add-recurrences in the same loop, different constant bases
        let a = X86SCEVExpr::addrec(X86SCEVExpr::constant(0), X86SCEVExpr::constant(8), 1);
        let b = X86SCEVExpr::addrec(X86SCEVExpr::constant(64), X86SCEVExpr::constant(8), 1);
        scev_aa.register_scev(1, a);
        scev_aa.register_scev(2, b);

        let loc_a = make_memloc(1, 8);
        let loc_b = make_memloc(2, 8);

        // Bases differ by 64, step is the same (8)
        assert_eq!(scev_aa.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    // -----------------------------------------------------------------------
    // X86GlobalsModRef tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_globals_mod_ref_new() {
        let gmr = X86GlobalsModRef::new();
        assert!(gmr.global_access.is_empty());
        assert!(gmr.function_behavior.is_empty());
    }

    #[test]
    fn test_globals_mod_ref_readnone() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_function(100, FunctionModRefInfo::DoesNotAccessMemory);
        let loc = make_memloc(1, 8);
        assert_eq!(gmr.get_mod_ref_for_call(100, &loc), ModRefInfo::NoModRef);
    }

    #[test]
    fn test_globals_mod_ref_readonly() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_function(100, FunctionModRefInfo::OnlyReadsMemory);
        let loc = make_memloc(1, 8);
        assert_eq!(gmr.get_mod_ref_for_call(100, &loc), ModRefInfo::Ref);
    }

    #[test]
    fn test_globals_mod_ref_non_address_taken() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_global(42, false, false); // not address-taken
        gmr.register_function(100, FunctionModRefInfo::ModRef);
        gmr.record_global_access(100, 42, ModRefInfo::Ref);

        let loc = make_memloc(42, 8);
        assert_eq!(gmr.get_mod_ref_for_call(100, &loc), ModRefInfo::Ref);
    }

    #[test]
    fn test_globals_mod_ref_read_only_global() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_global(42, true, true); // address-taken, read-only

        let loc = make_memloc(42, 8);
        assert_eq!(gmr.get_mod_ref_for_call(999, &loc), ModRefInfo::Ref);
    }

    #[test]
    fn test_globals_mod_ref_function_modifies_global() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_global(42, false, false);
        gmr.register_function(100, FunctionModRefInfo::ModRef);
        gmr.record_global_access(100, 42, ModRefInfo::Mod);

        assert!(gmr.function_modifies_global(100, 42));
        assert!(!gmr.function_modifies_global(200, 42));
    }

    // -----------------------------------------------------------------------
    // X86TypeBasedAA tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_tbaa_new() {
        let tbaa = X86TypeBasedAA::new();
        assert_eq!(tbaa.stats.total_nodes, 0);
    }

    #[test]
    fn test_tbaa_add_node() {
        let mut tbaa = X86TypeBasedAA::new();
        let node = TBAANode::new(1, 0, "int");
        tbaa.add_type_node(node);
        assert_eq!(tbaa.stats.total_nodes, 1);
        assert!(tbaa.type_nodes.contains_key(&1));
    }

    #[test]
    fn test_tbaa_may_alias_same_type() {
        let mut tbaa = X86TypeBasedAA::new();
        tbaa.add_type_node(TBAANode::new(1, 0, "root"));
        tbaa.add_type_node(TBAANode::new(2, 1, "int"));

        let tag_a = make_tbaa_tag(2, 1, 0);
        let tag_b = make_tbaa_tag(2, 1, 0);

        assert_eq!(
            tbaa.may_alias(Some(&tag_a), Some(&tag_b)),
            AliasResult::MustAlias
        );
    }

    #[test]
    fn test_tbaa_may_alias_different_roots() {
        let mut tbaa = X86TypeBasedAA::new();
        tbaa.add_type_node(TBAANode::new(1, 0, "root1"));
        tbaa.add_type_node(TBAANode::new(2, 1, "int"));
        tbaa.add_type_node(TBAANode::new(3, 0, "root2"));
        tbaa.add_type_node(TBAANode::new(4, 3, "float"));

        let tag_a = make_tbaa_tag(2, 1, 0);
        let tag_b = make_tbaa_tag(4, 3, 0);

        assert_eq!(
            tbaa.may_alias(Some(&tag_a), Some(&tag_b)),
            AliasResult::NoAlias
        );
    }

    #[test]
    fn test_tbaa_missing_tag_returns_may_alias() {
        let tbaa = X86TypeBasedAA::new();
        assert_eq!(tbaa.may_alias(None, None), AliasResult::MayAlias);
    }

    #[test]
    fn test_tbaa_constant_tag() {
        let mut tbaa = X86TypeBasedAA::new();
        tbaa.add_type_node(TBAANode::new_constant(1, 0, "const_root"));
        let tag = TBAATag::new_constant(1, 0, 0);
        assert!(tbaa.is_constant_tag(Some(&tag)));
    }

    #[test]
    fn test_tbaa_stats() {
        let mut tbaa = X86TypeBasedAA::new();
        tbaa.add_type_node(TBAANode::new(1, 0, "root"));
        tbaa.add_type_node(TBAANode::new(2, 1, "child"));

        let tag_a = make_tbaa_tag(1, 1, 0);
        let tag_b = make_tbaa_tag(2, 1, 0);

        tbaa.alias(Some(&tag_a), Some(&tag_b));

        let stats = tbaa.get_stats();
        assert_eq!(stats.total_queries, 1);
    }

    // -----------------------------------------------------------------------
    // X86ScopedNoAliasAA tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_scoped_noalias_new() {
        let aa = X86ScopedNoAliasAA::new();
        assert!(aa.noalias_pairs.is_empty());
    }

    #[test]
    fn test_scoped_noalias_different_scopes() {
        let mut aa = X86ScopedNoAliasAA::new();
        aa.register_noalias(1, 10, 20);

        let loc_a = make_memloc_with_noalias(100, 8, 1, vec![10]);
        let loc_b = make_memloc_with_noalias(200, 8, 1, vec![20]);

        assert_eq!(aa.may_alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_scoped_noalias_same_scope() {
        let mut aa = X86ScopedNoAliasAA::new();

        let loc_a = make_memloc_with_noalias(100, 8, 1, vec![10]);
        let loc_b = make_memloc_with_noalias(200, 8, 1, vec![10]);

        assert_eq!(aa.may_alias(&loc_a, &loc_b), AliasResult::MayAlias);
    }

    #[test]
    fn test_scoped_noalias_different_domains() {
        let mut aa = X86ScopedNoAliasAA::new();
        aa.register_noalias(1, 10, 20);

        let loc_a = make_memloc_with_noalias(100, 8, 1, vec![10]);
        let loc_b = make_memloc_with_noalias(200, 8, 2, vec![20]);

        assert_eq!(aa.may_alias(&loc_a, &loc_b), AliasResult::MayAlias);
    }

    #[test]
    fn test_scoped_noalias_no_metadata() {
        let aa = X86ScopedNoAliasAA::new();
        let loc_a = make_memloc(100, 8);
        let loc_b = make_memloc(200, 8);

        assert_eq!(aa.may_alias(&loc_a, &loc_b), AliasResult::MayAlias);
    }

    #[test]
    fn test_scoped_noalias_stats() {
        let mut aa = X86ScopedNoAliasAA::new();
        aa.register_noalias(1, 10, 20);

        let loc_a = make_memloc_with_noalias(100, 8, 1, vec![10]);
        let loc_b = make_memloc_with_noalias(200, 8, 1, vec![20]);

        aa.alias(&loc_a, &loc_b);

        let stats = aa.get_stats();
        assert_eq!(stats.total_queries, 1);
        assert_eq!(stats.noalias_results, 1);
        assert_eq!(stats.scoped_disambiguations, 1);
    }

    // -----------------------------------------------------------------------
    // X86MemorySSA tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_memory_ssa_new() {
        let mssa = X86MemorySSA::new();
        assert!(mssa.live_on_entry.is_none());
        assert_eq!(mssa.total_accesses(), 0);
    }

    #[test]
    fn test_memory_ssa_build_simple() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        // Two stores and one load
        let ops = vec![
            (1, 10, X86Opcode::Store, 100, 8, false),
            (1, 11, X86Opcode::Store, 100, 8, false),
            (1, 12, X86Opcode::Load, 100, 8, true),
        ];
        let block_order = vec![1];
        mssa.build(&ops, &block_order);

        assert!(mssa.live_on_entry.is_some());
        assert_eq!(mssa.memory_defs.len(), 3); // 2 stores + 1 live-on-entry
        assert_eq!(mssa.memory_uses.len(), 1);
    }

    #[test]
    fn test_memory_ssa_get_defining_access() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let ops = vec![
            (1, 10, X86Opcode::Store, 100, 8, false),
            (1, 11, X86Opcode::Load, 100, 8, true),
        ];
        mssa.build(&ops, &[1]);

        let defining = mssa.get_defining_access(11);
        assert!(defining.is_some());
    }

    #[test]
    fn test_memory_ssa_verify_ok() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let ops = vec![(1, 10, X86Opcode::Store, 100, 8, false)];
        mssa.build(&ops, &[1]);

        assert!(mssa.verify().is_ok());
    }

    #[test]
    fn test_memory_ssa_identify_dead_stores() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let ops = vec![
            (1, 10, X86Opcode::Store, 100, 8, false), // killed by store 11
            (1, 11, X86Opcode::Store, 100, 8, false), // used by load 12
            (1, 12, X86Opcode::Load, 100, 8, true),
        ];
        mssa.build(&ops, &[1]);

        let dead = mssa.identify_dead_stores();
        assert!(!dead.is_empty());
    }

    #[test]
    fn test_memory_ssa_optimize_uses() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let ops = vec![
            (1, 10, X86Opcode::Store, 200, 8, false), // different location
            (1, 11, X86Opcode::Load, 100, 8, true),
        ];
        mssa.build(&ops, &[1]);

        // The use at inst 11 should not be affected by store to 200
        mssa.optimize_uses();

        assert!(mssa.is_optimized);
    }

    #[test]
    fn test_memory_ssa_clobber_walker() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let ops = vec![
            (1, 10, X86Opcode::Store, 100, 8, false),
            (1, 11, X86Opcode::Load, 100, 8, true),
        ];
        mssa.build(&ops, &[1]);

        let access_id = mssa.get_memory_access(11);
        assert!(access_id.is_some());

        let loc = MemoryLocation::new(100, 8);
        let clobber = mssa.get_clobbering_access(access_id.unwrap(), &loc);
        assert!(clobber.is_some());
    }

    #[test]
    fn test_memory_ssa_walk_def_chain() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let ops = vec![
            (1, 10, X86Opcode::Store, 100, 8, false),
            (1, 11, X86Opcode::Store, 100, 8, false),
        ];
        mssa.build(&ops, &[1]);

        let access_id = mssa.get_memory_access(11);
        let chain = mssa.walk_def_chain(access_id.unwrap());
        assert!(!chain.is_empty());
    }

    #[test]
    fn test_memory_ssa_dominates() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let mut idom = HashMap::new();
        idom.insert(1, 0);
        idom.insert(2, 1);
        idom.insert(3, 1);
        mssa.set_dominators(idom);

        assert!(mssa.dominates(1, 2));
        assert!(mssa.dominates(1, 3));
        assert!(!mssa.dominates(2, 3));
    }

    // -----------------------------------------------------------------------
    // X86MemorySSAUpdater tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_mssa_updater_insert_use() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        let mut updater = X86MemorySSAUpdater::new(mssa);

        let use_id = updater.insert_use(100, 1, 42, 8);
        assert!(use_id > 0);
        assert!(!updater.update_log.is_empty());
    }

    #[test]
    fn test_mssa_updater_insert_def() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        let mut updater = X86MemorySSAUpdater::new(mssa);

        let def_id = updater.insert_def(100, 1, 42, 8);
        assert!(def_id > 0);
    }

    #[test]
    fn test_mssa_updater_remove_access() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);

        let access_id = mssa.get_memory_access(10);
        let mut updater = X86MemorySSAUpdater::new(mssa);

        assert!(updater.remove_access(access_id.unwrap()));
    }

    // -----------------------------------------------------------------------
    // X86MemDep tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_mem_dep_new() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[], &[]);
        let mem_dep = X86MemDep::new(mssa);

        assert_eq!(mem_dep.cache_size(), 0);
    }

    #[test]
    fn test_mem_dep_get_dependency() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let ops = vec![
            (1, 10, X86Opcode::Store, 100, 8, false),
            (1, 11, X86Opcode::Load, 100, 8, true),
        ];
        mssa.build(&ops, &[1]);

        let mut mem_dep = X86MemDep::new(mssa);
        let result = mem_dep.get_dependency(100, 8, 11);
        assert!(
            result.dep_kind == X86MemDepKind::Def || result.dep_kind == X86MemDepKind::NonLocal
        );
    }

    #[test]
    fn test_mem_dep_cache_hit() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);

        let mut mem_dep = X86MemDep::new(mssa);

        // First query: cache miss
        let _ = mem_dep.get_dependency(100, 8, 10);
        assert_eq!(mem_dep.stats.cache_misses, 1);

        // Second query: cache hit
        let _ = mem_dep.get_dependency(100, 8, 10);
        assert_eq!(mem_dep.stats.cache_hits, 1);
    }

    #[test]
    fn test_mem_dep_invalidate_cache() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[], &[]);
        let mut mem_dep = X86MemDep::new(mssa);

        let _ = mem_dep.get_dependency(100, 8, 11);
        assert_eq!(mem_dep.cache_size(), 1);

        mem_dep.invalidate_cache();
        assert_eq!(mem_dep.cache_size(), 0);
    }

    #[test]
    fn test_mem_dep_batch_query() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[], &[]);
        let mut mem_dep = X86MemDep::new(mssa);

        mem_dep.batch_add_query(100, 8, 10);
        mem_dep.batch_add_query(200, 4, 10);
        assert_eq!(mem_dep.pending_batch_queries(), 2);

        let results = mem_dep.flush_batch();
        assert_eq!(results.len(), 2);
        assert_eq!(mem_dep.pending_batch_queries(), 0);
    }

    // -----------------------------------------------------------------------
    // X86AliasAnalysis integration tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_x86_alias_analysis_new() {
        let aa = X86AliasAnalysis::new();
        assert!(!aa.initialized);
    }

    #[test]
    fn test_x86_alias_analysis_initialize() {
        let mut aa = X86AliasAnalysis::new();
        aa.initialize();
        assert!(aa.initialized);
        assert!(aa.mem_dep.is_some());
    }

    #[test]
    fn test_x86_alias_analysis_alias() {
        let mut aa = X86AliasAnalysis::new();
        aa.basic_aa.register_alloca(100, 8);
        aa.basic_aa.register_alloca(200, 8);

        let loc_a = make_memloc(100, 8);
        let loc_b = make_memloc(200, 8);

        let result = aa.alias(&loc_a, &loc_b);
        assert_eq!(result.result, AliasResult::NoAlias);
    }

    #[test]
    fn test_x86_alias_analysis_cache() {
        let mut aa = X86AliasAnalysis::new();
        aa.basic_aa.register_alloca(100, 8);
        aa.basic_aa.register_alloca(200, 8);

        let loc_a = make_memloc(100, 8);
        let loc_b = make_memloc(200, 8);

        // First call: compute
        let _ = aa.alias(&loc_a, &loc_b);
        // Second call: should be cached
        let result = aa.alias(&loc_a, &loc_b);
        assert_eq!(result.result, AliasResult::NoAlias);
        assert_eq!(result.source, "cache");
    }

    #[test]
    fn test_x86_alias_analysis_get_mod_ref_for_call() {
        let mut aa = X86AliasAnalysis::new();
        aa.globals_mod_ref
            .register_function(100, FunctionModRefInfo::DoesNotAccessMemory);

        let loc = make_memloc(500, 8);
        let modref = aa.get_mod_ref_for_call(100, &loc);
        assert_eq!(modref, ModRefInfo::NoModRef);
    }

    #[test]
    fn test_x86_alias_analysis_get_points_to() {
        let mut aa = X86AliasAnalysis::new();
        aa.cfl_aa.register_pointer(1);
        aa.cfl_aa.add_points_to(1, 42);

        let pts = aa.get_points_to(1);
        assert!(pts.objects.contains(&42));
    }

    #[test]
    fn test_x86_alias_analysis_alias_sets() {
        let mut aa = X86AliasAnalysis::new();
        let set = aa.get_alias_set(100);
        assert_eq!(set.id, 100);

        aa.merge_alias_sets(100, 200);
        assert!(aa.alias_sets.contains_key(&100));
        assert!(aa.alias_sets.contains_key(&200));
    }

    #[test]
    fn test_x86_alias_analysis_print_stats() {
        let aa = X86AliasAnalysis::new();
        let stats = aa.print_stats();
        assert!(stats.contains("X86 Alias Analysis Stats"));
        assert!(stats.contains("Total queries"));
    }

    #[test]
    fn test_x86_alias_analysis_invalidate_all() {
        let mut aa = X86AliasAnalysis::new();
        aa.initialize();

        // Do a query to populate cache
        let loc = make_memloc(100, 8);
        let _ = aa.alias(&loc, &loc);
        assert!(!aa.alias_cache.is_empty());

        aa.invalidate_all();
        // Note: alias cache may be repopulated by subsequent operations,
        // but it should be cleared now
        assert!(aa.alias_cache.is_empty());
    }

    // -----------------------------------------------------------------------
    // Helper function tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_is_memory_operation() {
        assert!(is_memory_operation(X86Opcode::Load));
        assert!(is_memory_operation(X86Opcode::Store));
        assert!(is_memory_operation(X86Opcode::Alloca));
        assert!(!is_memory_operation(X86Opcode::Add));
    }

    #[test]
    fn test_may_read_memory() {
        assert!(may_read_memory(X86Opcode::Load));
        assert!(!may_read_memory(X86Opcode::Store));
        assert!(may_read_memory(X86Opcode::Call));
    }

    #[test]
    fn test_may_write_memory() {
        assert!(may_write_memory(X86Opcode::Store));
        assert!(!may_write_memory(X86Opcode::Load));
        assert!(may_write_memory(X86Opcode::Call));
    }

    #[test]
    fn test_get_intrinsic_mod_ref() {
        assert_eq!(
            get_intrinsic_mod_ref("llvm.memcpy"),
            Some(ModRefInfo::ModRef)
        );
        assert_eq!(
            get_intrinsic_mod_ref("llvm.sqrt"),
            Some(ModRefInfo::NoModRef)
        );
        assert_eq!(get_intrinsic_mod_ref("unknown_func"), None);
    }

    #[test]
    fn test_have_same_base_object() {
        let mut aa = X86AliasAnalysis::new();
        aa.basic_aa.register_alloca(100, 8);
        assert!(have_same_base_object(&aa, 100, 100));
        assert!(!have_same_base_object(&aa, 100, 200));
    }

    #[test]
    fn test_get_underlying_object() {
        let mut aa = X86AliasAnalysis::new();
        aa.basic_aa.register_alloca(100, 64);
        aa.basic_aa.register_gep(200, 100, 16);

        assert_eq!(get_underlying_object(&aa, 100), Some(100));
        assert_eq!(get_underlying_object(&aa, 200), Some(100));
        assert_eq!(get_underlying_object(&aa, 999), None);
    }

    #[test]
    fn test_get_pointer_offset() {
        let mut aa = X86AliasAnalysis::new();
        aa.basic_aa.register_alloca(100, 64);
        aa.basic_aa.register_gep(200, 100, 16);

        assert_eq!(get_pointer_offset(&aa, 100), Some(0));
        assert_eq!(get_pointer_offset(&aa, 200), Some(16));
    }

    #[test]
    fn test_quick_alias_check() {
        let loc_a = make_memloc(100, 8);
        let loc_b = make_memloc(200, 8);
        assert_eq!(quick_alias_check(&loc_a, &loc_b), AliasResult::MayAlias);
    }

    #[test]
    fn test_build_pipeline() {
        let aa = build_x86_alias_analysis_pipeline();
        assert!(aa.initialized);
    }

    // -----------------------------------------------------------------------
    // FunctionModRefInfo tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_function_mod_ref_info_display() {
        assert_eq!(
            format!("{}", FunctionModRefInfo::DoesNotAccessMemory),
            "readnone"
        );
        assert_eq!(
            format!("{}", FunctionModRefInfo::OnlyReadsMemory),
            "readonly"
        );
        assert_eq!(
            format!("{}", FunctionModRefInfo::OnlyAccessesInaccessibleMemory),
            "inaccessiblememonly"
        );
    }

    // -----------------------------------------------------------------------
    // Edge case tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_null_pointer_no_alias() {
        let mut basic = X86BasicAA::new();
        let loc_a = make_memloc(0, 8);
        let loc_b = make_memloc(100, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_same_pointer_zero_size() {
        let mut basic = X86BasicAA::new();
        let loc_a = make_memloc(100, 0);
        let loc_b = make_memloc(100, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::MustAlias);
    }

    #[test]
    fn test_many_allocas() {
        let mut basic = X86BasicAA::new();
        for i in 0..100 {
            basic.register_alloca(i * 10, 8);
        }
        let loc_a = make_memloc(10, 8);
        let loc_b = make_memloc(990, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_cfl_aa_fixpoint_convergence() {
        let mut cfl = X86CFLAA::new();
        // Create a cyclic assignment chain
        cfl.register_pointer(1);
        cfl.register_pointer(2);
        cfl.register_pointer(3);
        cfl.add_assign(1, 2);
        cfl.add_assign(2, 3);
        cfl.add_assign(3, 1);
        cfl.add_points_to(1, 42);
        cfl.solve();

        // All should eventually point to 42
        assert!(cfl.get_points_to(2).objects.contains(&42));
        assert!(cfl.get_points_to(3).objects.contains(&42));
    }

    #[test]
    fn test_mem_dep_kind_display() {
        assert_eq!(format!("{}", X86MemDepKind::NonLocal), "NonLocal");
        assert_eq!(format!("{}", X86MemDepKind::Def), "Def");
        assert_eq!(format!("{}", X86MemDepKind::Clobber), "Clobber");
        assert_eq!(format!("{}", X86MemDepKind::Unknown), "Unknown");
    }

    #[test]
    fn test_scev_display() {
        let expr = X86SCEVExpr::addrec(X86SCEVExpr::constant(0), X86SCEVExpr::constant(1), 1);
        assert_eq!(format!("{}", expr), "{0,+,1}<loop_1>");
    }

    #[test]
    fn test_tbaa_tag_new() {
        let tag = TBAATag::new(1, 2, 16);
        assert_eq!(tag.access_type_id, 1);
        assert_eq!(tag.base_type_id, 2);
        assert_eq!(tag.offset, 16);
        assert!(!tag.is_constant);
    }

    // -----------------------------------------------------------------------
    // Stress / regression tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_basic_aa_gep_deep_chain() {
        let mut basic = X86BasicAA::new();
        basic.register_alloca(1, 1024);

        // Create a chain of GEPs: gep1 -> base, gep2 -> gep1, ...
        let mut prev = 1u64;
        for i in 0..20 {
            let gep_id = 100 + i;
            basic.register_gep(gep_id, prev, (i * 8) as i64);
            prev = gep_id;
        }

        // Last GEP should resolve to base 1
        let base = basic.resolve_gep_base(119);
        assert_eq!(base, Some(1));
    }

    #[test]
    fn test_cfl_aa_many_pointers() {
        let mut cfl = X86CFLAA::new();
        for i in 1..=100 {
            cfl.register_pointer(i);
            cfl.add_points_to(i, i + 1000);
        }
        cfl.solve();

        // Check that all pointers have unique points-to
        for i in 1..=100 {
            let pts = cfl.get_points_to(i);
            assert_eq!(pts.len(), 1);
            assert!(pts.objects.contains(&(i + 1000)));
        }
    }

    #[test]
    fn test_memory_ssa_deep_def_chain() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let mut ops = Vec::new();
        for i in 0..50 {
            ops.push((1, i, X86Opcode::Store, 100, 8, false));
        }
        mssa.build(&ops, &[1]);

        // Walk the chain from the last def
        let access_id = mssa.get_memory_access(49);
        let chain = mssa.walk_def_chain(access_id.unwrap());
        assert!(chain.len() >= 2);
    }

    #[test]
    fn test_alias_result_meet_symmetry() {
        assert_eq!(
            AliasResult::meet(AliasResult::MayAlias, AliasResult::NoAlias),
            AliasResult::NoAlias
        );
        assert_eq!(
            AliasResult::meet(AliasResult::NoAlias, AliasResult::NoAlias),
            AliasResult::NoAlias
        );
        assert_eq!(
            AliasResult::meet(AliasResult::MustAlias, AliasResult::MustAlias),
            AliasResult::MustAlias
        );
    }

    #[test]
    fn test_memory_location_zero_size_has_known() {
        let loc = MemoryLocation::new(100, 0);
        assert!(!loc.has_known_size);
    }

    #[test]
    fn test_points_to_set_max_size() {
        let mut pts = PointsToSet::empty();
        // Try to add more objects than the max
        for i in 0..(X86_MAX_POINTS_TO_SET + 10) {
            pts.objects.insert(i as u64);
        }
        // Sanity: it holds what we put in
        assert!(pts.objects.len() > X86_MAX_POINTS_TO_SET || pts.objects.len() > 0);
    }

    #[test]
    fn test_globals_mod_ref_unknown_function() {
        let gmr = X86GlobalsModRef::new();
        let loc = make_memloc(42, 8);

        // Unknown function with non-address-taken global -> ModRef (conservative)
        let result = gmr.get_mod_ref_for_call(999, &loc);
        // For a non-registered global, the function behavior is conservative
        assert_eq!(result, ModRefInfo::ModRef);
    }

    #[test]
    fn test_x86_opcode_display() {
        let op = X86Opcode::Store;
        assert!(!format!("{}", op).is_empty());
    }

    #[test]
    fn test_memory_ssa_optimize_no_defs() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[], &[1]);

        mssa.optimize_uses();
        assert!(mssa.is_optimized);
    }

    #[test]
    fn test_memory_ssa_verify_empty() {
        let mssa = X86MemorySSA::new();
        // Empty MSSA should be valid
        assert!(mssa.verify().is_ok());
    }

    #[test]
    fn test_memory_ssa_multi_block_phis() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        // Set up predecessors: block 3 has two predecessors (1 and 2)
        let mut preds = HashMap::new();
        preds.insert(1, vec![]);
        preds.insert(2, vec![1]);
        preds.insert(3, vec![1, 2]);
        mssa.set_predecessors(preds);

        // Stores in each predecessor
        let ops = vec![
            (1, 10, X86Opcode::Store, 100, 8, false),
            (2, 20, X86Opcode::Store, 100, 8, false),
            (3, 30, X86Opcode::Load, 100, 8, true),
        ];
        mssa.build(&ops, &[1, 2, 3]);

        // Block 3 should have a memory phi
        assert!(mssa.block_to_phi.contains_key(&3));
    }

    #[test]
    fn test_memory_ssa_redundant_load_detection() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);

        let ops = vec![
            (1, 10, X86Opcode::Store, 100, 8, false),
            (1, 11, X86Opcode::Load, 100, 8, true),
            (1, 12, X86Opcode::Load, 100, 8, true), // redundant load
        ];
        mssa.build(&ops, &[1]);

        let redundant = mssa.identify_redundant_loads();
        assert!(!redundant.is_empty());
    }

    #[test]
    fn test_mssa_updater_move_instruction() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);
        let mut updater = X86MemorySSAUpdater::new(mssa);

        updater.move_instruction(10, 1, 2);
        assert!(!updater.update_log.is_empty());
    }

    #[test]
    fn test_scoped_noalias_symmetric() {
        let mut aa = X86ScopedNoAliasAA::new();
        aa.register_noalias(1, 10, 20);

        // Check symmetry: (10, 20) and (20, 10) both return NoAlias
        let loc_a = make_memloc_with_noalias(100, 8, 1, vec![10]);
        let loc_b = make_memloc_with_noalias(200, 8, 1, vec![20]);
        let loc_c = make_memloc_with_noalias(300, 8, 1, vec![10]);
        let loc_d = make_memloc_with_noalias(400, 8, 1, vec![20]);

        assert_eq!(aa.may_alias(&loc_a, &loc_b), AliasResult::NoAlias);
        assert_eq!(aa.may_alias(&loc_c, &loc_d), AliasResult::NoAlias);
    }

    #[test]
    fn test_basic_aa_partial_alias_exact_overlap() {
        let mut basic = X86BasicAA::new();
        basic.register_alloca(1, 64);

        // GEP at offset 4, size 4 vs GEP at offset 4, size 8 — partial overlap
        basic.register_gep(10, 1, 4);
        basic.register_gep(20, 1, 4);

        let loc_a = make_memloc(10, 4);
        let loc_b = make_memloc(20, 8);

        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::MustAlias);
    }

    #[test]
    fn test_scev_aa_unknown_scev() {
        let mut scev_aa = X86SCEVAA::new();
        scev_aa.register_scev(1, X86SCEVExpr::Unknown);
        scev_aa.register_scev(2, X86SCEVExpr::Unknown);

        let loc_a = make_memloc(1, 8);
        let loc_b = make_memloc(2, 8);

        // Both unknown: cannot disambiguate
        assert_eq!(scev_aa.alias(&loc_a, &loc_b), AliasResult::MayAlias);
    }

    #[test]
    fn test_tbaa_ancestor_caching() {
        let mut tbaa = X86TypeBasedAA::new();
        tbaa.add_type_node(TBAANode::new(1, 0, "root"));
        tbaa.add_type_node(TBAANode::new(2, 1, "middle"));
        tbaa.add_type_node(TBAANode::new(3, 2, "leaf"));

        // First call builds cache
        let ancestors = tbaa.get_ancestors(3);
        assert!(ancestors.contains(&3));
        assert!(ancestors.contains(&2));
        assert!(ancestors.contains(&1));

        // Second call uses cache
        let ancestors2 = tbaa.get_ancestors(3);
        assert_eq!(ancestors, ancestors2);
    }

    #[test]
    fn test_globals_mod_ref_accessible_only() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_function(100, FunctionModRefInfo::OnlyAccessesInaccessibleMemory);
        let loc = make_memloc(500, 8);
        assert_eq!(gmr.get_mod_ref_for_call(100, &loc), ModRefInfo::NoModRef);
    }

    #[test]
    fn test_globals_mod_ref_writeonly() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_function(100, FunctionModRefInfo::OnlyWritesMemory);
        let loc = make_memloc(500, 8);
        assert_eq!(gmr.get_mod_ref_for_call(100, &loc), ModRefInfo::ModRef);
    }

    #[test]
    fn test_globals_mod_ref_unknown_global_modifies() {
        let mut gmr = X86GlobalsModRef::new();
        // An address-taken global (default) — unknown functions may modify it
        gmr.register_global(42, true, false);
        assert!(gmr.function_modifies_global(999, 42));
    }

    #[test]
    fn test_globals_mod_ref_statistics_update() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_global(1, false, false);
        gmr.register_global(2, false, true);
        gmr.update_counts();

        let stats = gmr.get_stats();
        assert_eq!(stats.non_address_taken_count, 2);
        assert_eq!(stats.read_only_count, 1);
    }

    #[test]
    fn test_alias_set_access_mod_ref() {
        let mut a = AliasSet::new(1);
        a.access_type = AliasSetAccess::Mod;

        let mut b = AliasSet::new(2);
        b.access_type = AliasSetAccess::Ref;

        a.merge(&b);
        assert_eq!(a.access_type, AliasSetAccess::ModRef);
    }

    #[test]
    fn test_alias_result_partial_alias() {
        let mut basic = X86BasicAA::new();

        // Same pointer, different sizes -> PartialAlias
        let loc_a = make_memloc(100, 4);
        let loc_b = make_memloc(100, 8);

        // But we need to register as an alloca or something
        // Without registration, same pointer -> MustAlias when sizes differ? No, PartialAlias.
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::PartialAlias);
    }

    #[test]
    fn test_cfl_aa_chain_of_assigns() {
        let mut cfl = X86CFLAA::new();
        for i in 1..=5 {
            cfl.register_pointer(i);
        }
        // Chain: 1 -> 2 -> 3 -> 4 -> 5
        cfl.add_assign(2, 1);
        cfl.add_assign(3, 2);
        cfl.add_assign(4, 3);
        cfl.add_assign(5, 4);
        cfl.add_points_to(1, 42);

        cfl.solve();

        assert!(cfl.get_points_to(5).objects.contains(&42));
    }

    #[test]
    fn test_mem_dep_pointer_dependency() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[], &[1]);

        let mut mem_dep = X86MemDep::new(mssa);
        let result = mem_dep.get_pointer_dependency(100, 10);
        // Should be Unknown since no memory operations exist
        assert!(matches!(
            result.dep_kind,
            X86MemDepKind::Unknown | X86MemDepKind::NonLocal
        ));
    }

    #[test]
    fn test_alias_cache_eviction() {
        let mut aa = X86AliasAnalysis::new();
        aa.max_alias_cache_size = 10;

        // Fill the cache beyond capacity
        for i in 0..20 {
            aa.basic_aa.register_alloca(i * 10, 8);
        }

        for i in 0..15 {
            let loc_a = make_memloc(i * 10, 8);
            let loc_b = make_memloc(i * 10 + 5, 8);
            let _ = aa.alias(&loc_a, &loc_b);
        }

        // Cache should not exceed limit + eviction overhead
        assert!(aa.alias_cache.len() <= aa.max_alias_cache_size + 5);
    }

    #[test]
    fn test_x86_alias_result_with_explanation() {
        let result =
            X86AliasResult::new(AliasResult::NoAlias, "Test").with_explanation("Because reasons");
        assert_eq!(result.result, AliasResult::NoAlias);
        assert_eq!(result.source, "Test");
        assert_eq!(result.explanation, Some("Because reasons".to_string()));
    }

    #[test]
    fn test_mod_ref_info_top_bottom() {
        assert_eq!(ModRefInfo::top(), ModRefInfo::ModRef);
        assert_eq!(ModRefInfo::bottom(), ModRefInfo::NoModRef);
    }

    #[test]
    fn test_alias_result_top_bottom() {
        assert_eq!(AliasResult::top(), AliasResult::MayAlias);
        assert_eq!(AliasResult::bottom(), AliasResult::NoAlias);
    }
}

// ============================================================================
// X86SCEVTripCount — SCEV-based trip count and loop analysis
// ============================================================================

/// Represents the computed trip count of a loop.
#[derive(Debug, Clone)]
pub enum X86SCEVTripCount {
    /// Exact trip count known at compile time.
    Exact(u64),
    /// Upper bound on trip count (may execute fewer iterations).
    UpperBound(u64),
    /// Lower bound on trip count (will execute at least this many).
    LowerBound(u64),
    /// Trip count is bounded between two values.
    Bounded(u64, u64),
    /// Unknown trip count.
    Unknown,
}

impl X86SCEVTripCount {
    /// Get the maximum trip count (upper bound or exact).
    pub fn max(&self) -> Option<u64> {
        match self {
            X86SCEVTripCount::Exact(v) => Some(*v),
            X86SCEVTripCount::UpperBound(v) => Some(*v),
            X86SCEVTripCount::Bounded(_lo, hi) => Some(*hi),
            X86SCEVTripCount::LowerBound(_) => None,
            X86SCEVTripCount::Unknown => None,
        }
    }

    /// Get the minimum trip count (lower bound or exact).
    pub fn min(&self) -> Option<u64> {
        match self {
            X86SCEVTripCount::Exact(v) => Some(*v),
            X86SCEVTripCount::LowerBound(v) => Some(*v),
            X86SCEVTripCount::Bounded(lo, _) => Some(*lo),
            X86SCEVTripCount::UpperBound(_) => None,
            X86SCEVTripCount::Unknown => None,
        }
    }

    /// Returns true if the trip count is exactly known.
    pub fn is_exact(&self) -> bool {
        matches!(self, X86SCEVTripCount::Exact(_))
    }

    /// Returns true if the trip count is completely unknown.
    pub fn is_unknown(&self) -> bool {
        matches!(self, X86SCEVTripCount::Unknown)
    }
}

impl fmt::Display for X86SCEVTripCount {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            X86SCEVTripCount::Exact(v) => write!(f, "exact({})", v),
            X86SCEVTripCount::UpperBound(v) => write!(f, "<={}", v),
            X86SCEVTripCount::LowerBound(v) => write!(f, ">={}", v),
            X86SCEVTripCount::Bounded(lo, hi) => write!(f, "bounded({}, {})", lo, hi),
            X86SCEVTripCount::Unknown => write!(f, "unknown"),
        }
    }
}

/// Compute the backedge-taken count for a loop given the induction variable's
/// start value, step, and exit condition.
#[derive(Debug, Clone)]
pub struct X86SCEVTripCounter {
    /// SCEV expressions for induction variables.
    pub scev_map: HashMap<u64, X86SCEVExpr>,
    /// Loop bounds: loop_id -> max estimated trip count.
    pub loop_max_trips: HashMap<u64, u64>,
}

impl X86SCEVTripCounter {
    /// Create a new trip counter.
    pub fn new() -> Self {
        X86SCEVTripCounter {
            scev_map: HashMap::new(),
            loop_max_trips: HashMap::new(),
        }
    }

    /// Compute the trip count for a loop given the induction variable's
    /// start, step, and exit limit.
    pub fn compute_trip_count(
        &self,
        start: i64,
        step: i64,
        limit: i64,
        is_signed: bool,
    ) -> X86SCEVTripCount {
        if step == 0 {
            if start < limit {
                return X86SCEVTripCount::Unknown;
            }
            return X86SCEVTripCount::Exact(0);
        }

        if is_signed {
            self.compute_signed_trip_count(start, step, limit)
        } else {
            self.compute_unsigned_trip_count(start as u64, step as u64, limit as u64)
        }
    }

    /// Compute signed trip count.
    fn compute_signed_trip_count(&self, start: i64, step: i64, limit: i64) -> X86SCEVTripCount {
        if step > 0 {
            if start >= limit {
                return X86SCEVTripCount::Exact(0);
            }
            let diff = (limit - start) as u64;
            let step_u = step as u64;
            let trips = (diff + step_u - 1) / step_u;

            if diff % step_u == 0 {
                X86SCEVTripCount::Exact(trips)
            } else {
                X86SCEVTripCount::UpperBound(trips)
            }
        } else {
            if start <= limit {
                return X86SCEVTripCount::Exact(0);
            }
            let diff = (start - limit) as u64;
            let step_abs = (-step) as u64;
            let trips = (diff + step_abs - 1) / step_abs;

            if diff % step_abs == 0 {
                X86SCEVTripCount::Exact(trips)
            } else {
                X86SCEVTripCount::UpperBound(trips)
            }
        }
    }

    /// Compute unsigned trip count.
    fn compute_unsigned_trip_count(&self, start: u64, step: u64, limit: u64) -> X86SCEVTripCount {
        if step == 0 {
            if start < limit {
                return X86SCEVTripCount::Unknown;
            }
            return X86SCEVTripCount::Exact(0);
        }

        if start >= limit {
            return X86SCEVTripCount::Exact(0);
        }

        let diff = limit - start;
        let trips = (diff + step - 1) / step;

        if diff % step == 0 {
            X86SCEVTripCount::Exact(trips)
        } else {
            X86SCEVTripCount::UpperBound(trips)
        }
    }

    /// Estimate the trip count from an SCEV add-recurrence and loop bound.
    pub fn estimate_from_addrec(&self, addrec: &X86SCEVExpr) -> X86SCEVTripCount {
        if let X86SCEVExpr::AddRec {
            base,
            step,
            loop_id,
        } = addrec
        {
            if let (X86SCEVExpr::Constant(base_val), X86SCEVExpr::Constant(step_val)) =
                (base.as_ref(), step.as_ref())
            {
                if let Some(max_trips) = self.loop_max_trips.get(loop_id) {
                    return X86SCEVTripCount::UpperBound(*max_trips);
                }

                let max_val = base_val
                    .checked_add(
                        step_val
                            .checked_mul(X86_SCEV_MAX_BACKEDGE_TAKEN_COUNT as i64)
                            .unwrap_or(i64::MAX),
                    )
                    .unwrap_or(i64::MAX);

                if *step_val > 0 {
                    self.compute_signed_trip_count(*base_val, *step_val, max_val)
                } else {
                    self.compute_signed_trip_count(*base_val, *step_val, -max_val)
                }
            } else {
                X86SCEVTripCount::Unknown
            }
        } else {
            X86SCEVTripCount::Unknown
        }
    }

    /// Register a loop with a known max trip count.
    pub fn register_loop(&mut self, loop_id: u64, max_trips: u64) {
        self.loop_max_trips.insert(loop_id, max_trips);
    }
}

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

// ============================================================================
// X86StratifiedCFLAA — Stratified CFL-AA with field sensitivity
// ============================================================================

/// Stratified CFL-AA extends the basic CFL-AA with support for field-sensitive
/// analysis. Each pointer can have multiple "strata" (field offsets), and
/// stratified reachability determines whether two field accesses can alias.
#[derive(Debug, Clone)]
pub struct X86StratifiedCFLAA {
    /// Base CFL-AA analysis.
    pub base: X86CFLAA,
    /// Field-sensitive points-to: (pointer, field_offset) -> PointsToSet.
    pub field_points_to: HashMap<(u64, u64), PointsToSet>,
    /// Known struct layouts: (base_type_id, field_offset) -> field_type_id.
    pub struct_layouts: HashMap<(u64, u64), u64>,
    /// Stratification depth (max field nesting).
    pub max_depth: usize,
    /// Statistics.
    pub stats: X86StratifiedCFLAAStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86StratifiedCFLAAStats {
    pub total_field_queries: u64,
    pub field_noalias: u64,
    pub field_mustalias: u64,
}

impl X86StratifiedCFLAA {
    /// Create a new stratified CFL-AA instance.
    pub fn new(max_depth: usize) -> Self {
        X86StratifiedCFLAA {
            base: X86CFLAA::new(),
            field_points_to: HashMap::new(),
            struct_layouts: HashMap::new(),
            max_depth,
            stats: X86StratifiedCFLAAStats::default(),
        }
    }

    /// Register a struct field layout.
    pub fn register_field(&mut self, base_type_id: u64, field_offset: u64, field_type_id: u64) {
        self.struct_layouts
            .insert((base_type_id, field_offset), field_type_id);
    }

    /// Add a field-sensitive points-to fact.
    pub fn add_field_points_to(&mut self, ptr: u64, field_offset: u64, obj: u64) {
        self.field_points_to
            .entry((ptr, field_offset))
            .or_insert_with(PointsToSet::empty)
            .objects
            .insert(obj);
    }

    /// Query whether two field accesses may alias.
    pub fn field_may_alias(
        &mut self,
        ptr_a: u64,
        offset_a: u64,
        size_a: u64,
        ptr_b: u64,
        offset_b: u64,
        size_b: u64,
    ) -> AliasResult {
        self.stats.total_field_queries += 1;

        if ptr_a == ptr_b && ptr_a != 0 {
            if offset_a == offset_b && size_a == size_b {
                self.stats.field_mustalias += 1;
                return AliasResult::MustAlias;
            }
            let end_a = offset_a + size_a;
            let end_b = offset_b + size_b;
            if end_a <= offset_b || end_b <= offset_a {
                self.stats.field_noalias += 1;
                return AliasResult::NoAlias;
            }
            return AliasResult::PartialAlias;
        }

        let pts_a = self
            .field_points_to
            .get(&(ptr_a, offset_a))
            .cloned()
            .unwrap_or_else(PointsToSet::empty);
        let pts_b = self
            .field_points_to
            .get(&(ptr_b, offset_b))
            .cloned()
            .unwrap_or_else(PointsToSet::empty);

        if pts_a.is_noalias || pts_b.is_noalias {
            self.stats.field_noalias += 1;
            return AliasResult::NoAlias;
        }

        if pts_a.may_alias(&pts_b) {
            AliasResult::MayAlias
        } else {
            self.stats.field_noalias += 1;
            AliasResult::NoAlias
        }
    }

    /// Get the field type for a struct access.
    pub fn get_field_type(&self, base_type_id: u64, offset: u64) -> Option<u64> {
        self.struct_layouts.get(&(base_type_id, offset)).copied()
    }
}

// ============================================================================
// X86MemorySSAPlacer — dominator-based MemorySSA placement
// ============================================================================

/// Implements the iterative dominator-frontier-based placement algorithm
/// for MemorySSA phi nodes.
#[derive(Debug, Clone)]
pub struct X86MemorySSAPlacer {
    /// Dominator tree: block_id -> immediate dominator.
    pub idom: HashMap<u64, u64>,
    /// Dominator tree children: block_id -> children.
    pub dom_children: HashMap<u64, Vec<u64>>,
    /// Dominance frontiers: block_id -> set of blocks in its DF.
    pub df: HashMap<u64, HashSet<u64>>,
    /// Iterated dominance frontiers (cached).
    idf_cache: HashMap<u64, HashSet<u64>>,
    /// The entry block.
    entry_block: u64,
}

impl X86MemorySSAPlacer {
    /// Create a new placer with dominator info.
    pub fn new(idom: HashMap<u64, u64>, entry_block: u64) -> Self {
        let mut dom_children: HashMap<u64, Vec<u64>> = HashMap::new();
        for (&node, &idom_val) in &idom {
            if node != entry_block && idom_val != 0 {
                dom_children.entry(idom_val).or_default().push(node);
            }
        }

        let mut placer = X86MemorySSAPlacer {
            idom,
            dom_children,
            df: HashMap::new(),
            idf_cache: HashMap::new(),
            entry_block,
        };

        placer.compute_df();
        placer
    }

    /// Compute dominance frontiers for all blocks.
    fn compute_df(&mut self) {
        let all_blocks: Vec<u64> = self.idom.keys().copied().collect();

        for &block in &all_blocks {
            self.df.entry(block).or_insert_with(HashSet::new);
        }

        for &block in &all_blocks {
            if block == self.entry_block {
                continue;
            }
            let mut runner = block;
            if let Some(&idom_block) = self.idom.get(&block) {
                while runner != idom_block && runner != 0 {
                    self.df.entry(runner).or_default().insert(block);
                    runner = self.idom.get(&runner).copied().unwrap_or(0);
                    if runner == 0 {
                        break;
                    }
                }
            }
        }
    }

    /// Compute the iterated dominance frontier for a set of blocks.
    pub fn iterated_dominance_frontier(&mut self, blocks: &HashSet<u64>) -> HashSet<u64> {
        let key: u64 = blocks
            .iter()
            .fold(0, |acc, b| acc.wrapping_mul(31).wrapping_add(*b));
        if let Some(cached) = self.idf_cache.get(&key) {
            return cached.clone();
        }

        let mut idf = blocks.clone();
        let mut changed = true;

        while changed {
            changed = false;
            let current: Vec<u64> = idf.iter().copied().collect();
            for &block in &current {
                if let Some(df_set) = self.df.get(&block) {
                    for &df_block in df_set {
                        if idf.insert(df_block) {
                            changed = true;
                        }
                    }
                }
            }
        }

        self.idf_cache.insert(key, idf.clone());
        idf
    }

    /// Place memory phis at the iterated dominance frontier.
    pub fn place_phis(&mut self, def_blocks: &HashSet<u64>) -> HashSet<u64> {
        self.iterated_dominance_frontier(def_blocks)
    }

    /// Get the dominance frontier for a specific block.
    pub fn get_df(&self, block: u64) -> HashSet<u64> {
        self.df.get(&block).cloned().unwrap_or_default()
    }

    /// Check if block_a dominates block_b.
    pub fn dominates(&self, block_a: u64, block_b: u64) -> bool {
        if block_a == block_b {
            return true;
        }
        let mut current = block_b;
        for _ in 0..X86_MEMSSA_MAX_WALK_DEPTH {
            if current == block_a {
                return true;
            }
            match self.idom.get(&current) {
                Some(&idom_val) if idom_val != current && idom_val != 0 => {
                    current = idom_val;
                }
                _ => break,
            }
        }
        false
    }
}

// ============================================================================
// X86AliasEvaluator — evaluate alias analysis precision
// ============================================================================

/// Evaluates the precision of alias analysis by comparing results
/// against a dynamic oracle or a set of known ground-truth pairs.
#[derive(Debug, Clone)]
pub struct X86AliasEvaluator {
    /// Ground-truth alias pairs: (ptr_a, size_a, ptr_b, size_b) -> expected AliasResult.
    pub ground_truth: HashMap<(u64, u64, u64, u64), AliasResult>,
    /// Recorded analysis results.
    pub results: Vec<X86EvalRecord>,
    /// Summary statistics.
    pub summary: X86EvalSummary,
}

/// A single evaluation record.
#[derive(Debug, Clone)]
pub struct X86EvalRecord {
    /// The query that was evaluated.
    pub query: (u64, u64, u64, u64),
    /// The expected result.
    pub expected: AliasResult,
    /// The actual result from analysis.
    pub actual: AliasResult,
    /// Which analysis produced the result.
    pub source: String,
    /// Whether this is a correct result.
    pub correct: bool,
}

/// Summary statistics for alias analysis evaluation.
#[derive(Debug, Clone, Default)]
pub struct X86EvalSummary {
    pub total_queries: u64,
    pub correct_noalias: u64,
    pub correct_mustalias: u64,
    pub correct_partialalias: u64,
    pub correct_mayalias: u64,
    pub incorrect: u64,
    pub precision: f64,
    pub soundness: f64,
}

impl X86AliasEvaluator {
    /// Create a new evaluator.
    pub fn new() -> Self {
        X86AliasEvaluator {
            ground_truth: HashMap::new(),
            results: Vec::new(),
            summary: X86EvalSummary::default(),
        }
    }

    /// Add a ground-truth pair.
    pub fn add_ground_truth(
        &mut self,
        ptr_a: u64,
        size_a: u64,
        ptr_b: u64,
        size_b: u64,
        expected: AliasResult,
    ) {
        self.ground_truth
            .insert((ptr_a, size_a, ptr_b, size_b), expected);
    }

    /// Evaluate a single alias query.
    pub fn evaluate(
        &mut self,
        ptr_a: u64,
        size_a: u64,
        ptr_b: u64,
        size_b: u64,
        actual: X86AliasResult,
    ) {
        let expected = self
            .ground_truth
            .get(&(ptr_a, size_a, ptr_b, size_b))
            .copied()
            .unwrap_or(AliasResult::MayAlias);

        let correct = self.check_correctness(expected, actual.result);

        self.results.push(X86EvalRecord {
            query: (ptr_a, size_a, ptr_b, size_b),
            expected,
            actual: actual.result,
            source: actual.source,
            correct,
        });
    }

    /// Check if the actual result is correct with respect to expected.
    fn check_correctness(&self, expected: AliasResult, actual: AliasResult) -> bool {
        match (expected, actual) {
            (AliasResult::MustAlias, AliasResult::MustAlias) => true,
            (AliasResult::MustAlias, AliasResult::NoAlias) => false,
            (AliasResult::MustAlias, _) => false,
            (AliasResult::NoAlias, AliasResult::NoAlias) => true,
            (AliasResult::NoAlias, _) => true,
            (AliasResult::PartialAlias, AliasResult::PartialAlias) => true,
            (AliasResult::PartialAlias, AliasResult::NoAlias) => false,
            (AliasResult::PartialAlias, _) => true,
            (AliasResult::MayAlias, _) => true,
        }
    }

    /// Compute summary statistics.
    pub fn compute_summary(&mut self) {
        let mut summary = X86EvalSummary::default();
        summary.total_queries = self.results.len() as u64;

        for record in &self.results {
            if record.correct {
                match record.expected {
                    AliasResult::NoAlias => summary.correct_noalias += 1,
                    AliasResult::MustAlias => summary.correct_mustalias += 1,
                    AliasResult::PartialAlias => summary.correct_partialalias += 1,
                    AliasResult::MayAlias => summary.correct_mayalias += 1,
                }
            } else {
                summary.incorrect += 1;
            }
        }

        let non_mayalias: u64 = self
            .results
            .iter()
            .filter(|r| r.actual != AliasResult::MayAlias)
            .count() as u64;
        summary.precision = if summary.total_queries > 0 {
            non_mayalias as f64 / summary.total_queries as f64
        } else {
            0.0
        };

        summary.soundness = if summary.total_queries > 0 {
            (summary.total_queries - summary.incorrect) as f64 / summary.total_queries as f64
        } else {
            1.0
        };

        self.summary = summary;
    }

    /// Get a report string.
    pub fn report(&self) -> String {
        let s = &self.summary;
        format!(
            "Alias Analysis Evaluation Report\n\
             ==================================\n\
             Total queries:     {}\n\
             Correct NoAlias:   {}\n\
             Correct MustAlias: {}\n\
             Correct PartAlias: {}\n\
             Correct MayAlias:  {}\n\
             Incorrect:         {}\n\
             Precision:         {:.2}%\n\
             Soundness:         {:.2}%\n",
            s.total_queries,
            s.correct_noalias,
            s.correct_mustalias,
            s.correct_partialalias,
            s.correct_mayalias,
            s.incorrect,
            s.precision * 100.0,
            s.soundness * 100.0,
        )
    }
}

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

// ============================================================================
// X86BatchAliasQuery — batch query optimization
// ============================================================================

/// Batch alias query optimizer: collects multiple alias queries and
/// processes them together to share intermediate results.
#[derive(Debug, Clone)]
pub struct X86BatchAliasQuery {
    /// Pending queries: (ptr_a, size_a, ptr_b, size_b).
    pub pending: Vec<(u64, u64, u64, u64)>,
    /// Results cache shared across the batch.
    pub cache: HashMap<(u64, u64, u64, u64), AliasResult>,
    /// Maximum batch size before auto-flush.
    pub max_batch_size: usize,
    /// Statistics.
    pub stats: X86BatchStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86BatchStats {
    pub batches_processed: u64,
    pub queries_processed: u64,
    pub cache_hits: u64,
}

impl X86BatchAliasQuery {
    /// Create a new batch query manager.
    pub fn new(max_batch_size: usize) -> Self {
        X86BatchAliasQuery {
            pending: Vec::new(),
            cache: HashMap::new(),
            max_batch_size,
            stats: X86BatchStats::default(),
        }
    }

    /// Add a query to the batch.
    pub fn add(&mut self, ptr_a: u64, size_a: u64, ptr_b: u64, size_b: u64) {
        self.pending.push((ptr_a, size_a, ptr_b, size_b));
    }

    /// Flush the batch and process all pending queries.
    pub fn flush<F>(&mut self, mut query_fn: F) -> Vec<AliasResult>
    where
        F: FnMut(u64, u64, u64, u64) -> AliasResult,
    {
        let mut results = Vec::with_capacity(self.pending.len());

        for &(ptr_a, size_a, ptr_b, size_b) in &self.pending {
            let key = (ptr_a, size_a, ptr_b, size_b);
            let sym_key = (ptr_b, size_b, ptr_a, size_a);

            if let Some(&cached) = self.cache.get(&key).or_else(|| self.cache.get(&sym_key)) {
                self.stats.cache_hits += 1;
                results.push(cached);
            } else {
                let result = query_fn(ptr_a, size_a, ptr_b, size_b);
                self.cache.insert(key, result);
                results.push(result);
            }
        }

        self.stats.queries_processed += self.pending.len() as u64;
        self.stats.batches_processed += 1;
        self.pending.clear();

        results
    }

    /// Clear the batch and cache.
    pub fn clear(&mut self) {
        self.pending.clear();
        self.cache.clear();
    }

    /// Get the number of pending queries.
    pub fn pending_count(&self) -> usize {
        self.pending.len()
    }
}

// ============================================================================
// X86AliasSetTracker — alias set construction and tracking
// ============================================================================

/// Tracks alias sets across a function, merging sets when aliasing
/// is discovered. Implements a union-find like structure.
#[derive(Debug, Clone)]
pub struct X86AliasSetTracker {
    /// Alias sets mapping: set_id -> AliasSet.
    pub sets: HashMap<u64, AliasSet>,
    /// Union-find: pointer -> set_id.
    pub pointer_to_set: HashMap<u64, u64>,
    /// Next available set id.
    next_set_id: u64,
    /// Statistics.
    pub stats: X86AliasSetTrackerStats,
}

#[derive(Debug, Clone, Default)]
pub struct X86AliasSetTrackerStats {
    pub total_sets: usize,
    pub total_merges: u64,
    pub max_set_size: usize,
}

impl X86AliasSetTracker {
    /// Create a new alias set tracker.
    pub fn new() -> Self {
        X86AliasSetTracker {
            sets: HashMap::new(),
            pointer_to_set: HashMap::new(),
            next_set_id: 1,
            stats: X86AliasSetTrackerStats::default(),
        }
    }

    /// Get the set id for a pointer, creating one if needed.
    pub fn get_or_create_set(&mut self, ptr: u64) -> u64 {
        if let Some(&set_id) = self.pointer_to_set.get(&ptr) {
            return set_id;
        }

        let set_id = self.next_set_id;
        self.next_set_id += 1;

        let mut set = AliasSet::new(set_id);
        set.add_pointer(ptr);
        self.sets.insert(set_id, set);
        self.pointer_to_set.insert(ptr, set_id);
        self.stats.total_sets = self.sets.len();

        set_id
    }

    /// Merge the alias sets containing ptr_a and ptr_b.
    pub fn merge_sets(&mut self, ptr_a: u64, ptr_b: u64) {
        let set_a_id = self.get_or_create_set(ptr_a);
        let set_b_id = self.get_or_create_set(ptr_b);

        if set_a_id == set_b_id {
            return;
        }

        let (keep_id, absorb_id) = {
            let size_a = self
                .sets
                .get(&set_a_id)
                .map(|s| s.pointers.len())
                .unwrap_or(0);
            let size_b = self
                .sets
                .get(&set_b_id)
                .map(|s| s.pointers.len())
                .unwrap_or(0);
            if size_a >= size_b {
                (set_a_id, set_b_id)
            } else {
                (set_b_id, set_a_id)
            }
        };

        let absorb_set = self.sets[&absorb_id].clone();
        let absorbed_pointers: Vec<u64> = absorb_set.pointers.iter().copied().collect();

        if let Some(keep_set) = self.sets.get_mut(&keep_id) {
            keep_set.merge(&absorb_set);
        }

        for ptr in &absorbed_pointers {
            self.pointer_to_set.insert(*ptr, keep_id);
        }

        self.sets.remove(&absorb_id);

        self.stats.total_merges += 1;
        self.stats.total_sets = self.sets.len();

        if let Some(keep_set) = self.sets.get(&keep_id) {
            if keep_set.pointers.len() > self.stats.max_set_size {
                self.stats.max_set_size = keep_set.pointers.len();
            }
        }
    }

    /// Get the alias set containing a pointer.
    pub fn get_set(&self, ptr: u64) -> Option<&AliasSet> {
        self.pointer_to_set
            .get(&ptr)
            .and_then(|set_id| self.sets.get(set_id))
    }

    /// Get all unique alias sets.
    pub fn get_all_sets(&self) -> Vec<&AliasSet> {
        self.sets.values().collect()
    }

    /// Get the set id for a pointer if it exists.
    pub fn get_set_id(&self, ptr: u64) -> Option<u64> {
        self.pointer_to_set.get(&ptr).copied()
    }

    /// Get statistics.
    pub fn get_stats(&self) -> &X86AliasSetTrackerStats {
        &self.stats
    }
}

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

// ============================================================================
// X86CaptureTracker — track pointer captures
// ============================================================================

/// Tracks whether a pointer value escapes (is captured) through function
/// calls, returns, stores to globals, or other mechanisms.
#[derive(Debug, Clone)]
pub struct X86CaptureTracker {
    /// Whether the pointer has been captured in any way.
    pub captured: bool,
    /// Whether the pointer is captured by the return value.
    pub captured_by_ret: bool,
    /// Whether the pointer is captured by being passed as an argument.
    pub captured_by_arg: bool,
    /// Whether the pointer is stored to a global or escaped location.
    pub captured_by_global: bool,
    /// The set of users that capture this pointer.
    pub capturing_users: HashSet<u64>,
    /// The number of uses of this pointer.
    pub total_uses: usize,
}

impl X86CaptureTracker {
    /// Create a new capture tracker.
    pub fn new() -> Self {
        X86CaptureTracker {
            captured: false,
            captured_by_ret: false,
            captured_by_arg: false,
            captured_by_global: false,
            capturing_users: HashSet::new(),
            total_uses: 0,
        }
    }

    /// Mark the pointer as captured by a return instruction.
    pub fn mark_captured_by_ret(&mut self, user: u64) {
        self.captured = true;
        self.captured_by_ret = true;
        self.capturing_users.insert(user);
    }

    /// Mark the pointer as captured by being passed as a call argument.
    pub fn mark_captured_by_arg(&mut self, user: u64) {
        self.captured = true;
        self.captured_by_arg = true;
        self.capturing_users.insert(user);
    }

    /// Mark the pointer as captured by a store to a global.
    pub fn mark_captured_by_global(&mut self, user: u64) {
        self.captured = true;
        self.captured_by_global = true;
        self.capturing_users.insert(user);
    }

    /// Mark a use (that doesn't capture).
    pub fn mark_use(&mut self) {
        self.total_uses += 1;
    }

    /// Returns true if the pointer is captured in any way.
    pub fn is_captured(&self) -> bool {
        self.captured
    }

    /// Returns true if the pointer is only captured by return.
    pub fn is_captured_by_ret_only(&self) -> bool {
        self.captured_by_ret && !self.captured_by_arg && !self.captured_by_global
    }

    /// Returns true if the pointer has not escaped at all.
    pub fn is_not_captured(&self) -> bool {
        !self.captured
    }
}

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

// ============================================================================
// X86MemDepBlock — block-level memory dependence traversal
// ============================================================================

/// Block-level memory dependence analysis. Walks basic blocks in reverse
/// postorder to find the nearest memory dependency for a given location.
#[derive(Debug, Clone)]
pub struct X86MemDepBlock {
    /// The memory SSA for the function.
    pub mssa: X86MemorySSA,
    /// Cache: (block_id, ptr, size) -> nearest def in that block.
    block_cache: HashMap<(u64, u64, u64), Option<u64>>,
    /// Maximum blocks to traverse.
    max_blocks: usize,
}

impl X86MemDepBlock {
    /// Create a new block-level memdep analyzer.
    pub fn new(mssa: X86MemorySSA) -> Self {
        X86MemDepBlock {
            mssa,
            block_cache: HashMap::new(),
            max_blocks: 100,
        }
    }

    /// Find the nearest preceding memory definition in the given block.
    pub fn find_def_in_block(&mut self, block_id: u64, ptr: u64, size: u64) -> Option<u64> {
        let cache_key = (block_id, ptr, size);
        if let Some(cached) = self.block_cache.get(&cache_key) {
            return *cached;
        }

        let mut result = None;

        let mut block_defs: Vec<(u64, &X86MemoryDef)> = self
            .mssa
            .memory_defs
            .iter()
            .filter(|(_, d)| d.block_id == block_id && !d.is_live_on_entry)
            .map(|(id, d)| (*id, d))
            .collect();

        block_defs.sort_by_key(|(id, _)| *id);

        for (def_id, def) in block_defs.iter().rev() {
            if def.location.ptr == ptr || self.locations_may_alias(&def.location, ptr, size) {
                result = Some(*def_id);
                break;
            }
        }

        self.block_cache.insert(cache_key, result);
        result
    }

    /// Check whether a MemoryLocation may alias with a given (ptr, size).
    fn locations_may_alias(&self, loc: &MemoryLocation, ptr: u64, size: u64) -> bool {
        if loc.ptr == 0 || ptr == 0 {
            return false;
        }
        if loc.ptr == ptr {
            return true;
        }
        true
    }

    /// Walk backwards through blocks to find the nearest dominating definition.
    pub fn find_nearest_dominating_def(
        &mut self,
        block_id: u64,
        ptr: u64,
        size: u64,
    ) -> Option<u64> {
        if let Some(def) = self.find_def_in_block(block_id, ptr, size) {
            return Some(def);
        }

        let mut current = block_id;
        for _ in 0..self.max_blocks {
            match self.mssa.idom.get(&current) {
                Some(&idom_val) if idom_val != current && idom_val != 0 => {
                    if let Some(def) = self.find_def_in_block(idom_val, ptr, size) {
                        return Some(def);
                    }
                    current = idom_val;
                }
                _ => break,
            }
        }

        None
    }

    /// Invalidate the block cache.
    pub fn invalidate_cache(&mut self) {
        self.block_cache.clear();
    }
}

// ============================================================================
// X86AAQueryCache — LRU cache for alias analysis queries
// ============================================================================

/// LRU cache for alias analysis query results.
#[derive(Debug, Clone)]
pub struct X86AAQueryCache {
    /// Cache entries: key -> (result, access_counter).
    entries: HashMap<(u64, u64, u64, u64), (AliasResult, u64)>,
    /// Maximum number of entries.
    capacity: usize,
    /// Monotonically increasing access counter.
    counter: u64,
}

impl X86AAQueryCache {
    /// Create a new cache with the given capacity.
    pub fn new(capacity: usize) -> Self {
        X86AAQueryCache {
            entries: HashMap::new(),
            capacity,
            counter: 0,
        }
    }

    /// Look up a cached result.
    pub fn get(&mut self, ptr_a: u64, size_a: u64, ptr_b: u64, size_b: u64) -> Option<AliasResult> {
        let key = (ptr_a, size_a, ptr_b, size_b);
        let sym_key = (ptr_b, size_b, ptr_a, size_a);

        self.counter += 1;

        if let Some((result, cnt)) = self.entries.get_mut(&key) {
            *cnt = self.counter;
            return Some(*result);
        }
        if let Some((result, cnt)) = self.entries.get_mut(&sym_key) {
            *cnt = self.counter;
            return Some(*result);
        }

        None
    }

    /// Insert a result into the cache.
    pub fn insert(
        &mut self,
        ptr_a: u64,
        size_a: u64,
        ptr_b: u64,
        size_b: u64,
        result: AliasResult,
    ) {
        if self.capacity == 0 {
            return;
        }

        self.counter += 1;
        let key = (ptr_a, size_a, ptr_b, size_b);

        if self.entries.len() >= self.capacity {
            let mut min_counter = u64::MAX;
            let mut min_key = None;
            for (k, (_, cnt)) in &self.entries {
                if *cnt < min_counter {
                    min_counter = *cnt;
                    min_key = Some(*k);
                }
            }
            if let Some(k) = min_key {
                self.entries.remove(&k);
            }
        }

        self.entries.insert(key, (result, self.counter));
    }

    /// Clear the cache.
    pub fn clear(&mut self) {
        self.entries.clear();
        self.counter = 0;
    }

    /// Get the current number of entries.
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Returns true if the cache is empty.
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }
}

// ============================================================================
// X86PointsToAnalysis — full points-to analysis wrapper
// ============================================================================

/// Complete points-to analysis that wraps CFL-AA and provides a unified
/// interface for querying points-to relationships.
#[derive(Debug, Clone)]
pub struct X86PointsToAnalysis {
    /// The CFL-AA engine.
    pub cfl: X86CFLAA,
    /// Stratified (field-sensitive) extension.
    pub stratified: Option<X86StratifiedCFLAA>,
    /// Cached points-to results.
    pub cache: X86AAQueryCache,
    /// Whether the analysis is field-sensitive.
    pub field_sensitive: bool,
}

impl X86PointsToAnalysis {
    /// Create a new points-to analysis.
    pub fn new(field_sensitive: bool) -> Self {
        X86PointsToAnalysis {
            cfl: X86CFLAA::new(),
            stratified: if field_sensitive {
                Some(X86StratifiedCFLAA::new(8))
            } else {
                None
            },
            cache: X86AAQueryCache::new(1024),
            field_sensitive,
        }
    }

    /// Query whether two pointers may alias.
    pub fn may_alias(
        &mut self,
        ptr_a: u64,
        offset_a: u64,
        size_a: u64,
        ptr_b: u64,
        offset_b: u64,
        size_b: u64,
    ) -> AliasResult {
        if let Some(cached) = self.cache.get(ptr_a, size_a, ptr_b, size_b) {
            return cached;
        }

        let result = if self.field_sensitive {
            if let Some(ref mut strat) = self.stratified {
                strat.field_may_alias(ptr_a, offset_a, size_a, ptr_b, offset_b, size_b)
            } else {
                self.cfl.may_alias(ptr_a, ptr_b)
            }
        } else {
            self.cfl.may_alias(ptr_a, ptr_b)
        };

        self.cache.insert(ptr_a, size_a, ptr_b, size_b, result);
        result
    }

    /// Run the full points-to analysis.
    pub fn solve(&mut self) {
        self.cfl.solve();
    }
}

// ============================================================================
// Extended Tests — integration, stress, and property tests
// ============================================================================

#[cfg(test)]
mod extended_tests {
    use super::*;

    // -------------------------------------------------------------------
    // SCEV Trip Count Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_trip_count_signed_positive_step() {
        let counter = X86SCEVTripCounter::new();
        let tc = counter.compute_trip_count(0, 1, 100, true);
        assert_eq!(tc.max(), Some(100));
        assert_eq!(tc.min(), Some(100));
        assert!(tc.is_exact());
    }

    #[test]
    fn test_trip_count_signed_negative_step() {
        let counter = X86SCEVTripCounter::new();
        let tc = counter.compute_trip_count(100, -1, 0, true);
        assert_eq!(tc.max(), Some(100));
        assert!(tc.is_exact());
    }

    #[test]
    fn test_trip_count_zero_iterations() {
        let counter = X86SCEVTripCounter::new();
        let tc = counter.compute_trip_count(100, 1, 50, true);
        assert_eq!(tc.max(), Some(0));
        assert!(tc.is_exact());
    }

    #[test]
    fn test_trip_count_unsigned() {
        let counter = X86SCEVTripCounter::new();
        let tc = counter.compute_trip_count(0, 2, 100, false);
        assert_eq!(tc.max(), Some(50));
        assert!(tc.is_exact());
    }

    #[test]
    fn test_trip_count_unsigned_no_iterations() {
        let counter = X86SCEVTripCounter::new();
        let tc = counter.compute_trip_count(100, 1, 50, false);
        assert_eq!(tc.max(), Some(0));
    }

    #[test]
    fn test_trip_count_display_formats() {
        assert_eq!(format!("{}", X86SCEVTripCount::Exact(42)), "exact(42)");
        assert_eq!(format!("{}", X86SCEVTripCount::UpperBound(100)), "<=100");
        assert_eq!(format!("{}", X86SCEVTripCount::LowerBound(10)), ">=10");
        assert_eq!(
            format!("{}", X86SCEVTripCount::Bounded(5, 50)),
            "bounded(5, 50)"
        );
        assert_eq!(format!("{}", X86SCEVTripCount::Unknown), "unknown");
    }

    #[test]
    fn test_trip_count_bounded() {
        let tc = X86SCEVTripCount::Bounded(10, 100);
        assert_eq!(tc.max(), Some(100));
        assert_eq!(tc.min(), Some(10));
        assert!(!tc.is_exact());
        assert!(!tc.is_unknown());
    }

    #[test]
    fn test_trip_count_lower_bound() {
        let tc = X86SCEVTripCount::LowerBound(5);
        assert_eq!(tc.min(), Some(5));
        assert_eq!(tc.max(), None);
    }

    #[test]
    fn test_trip_counter_register_loop() {
        let mut counter = X86SCEVTripCounter::new();
        counter.register_loop(1, 42);
        assert_eq!(counter.loop_max_trips.get(&1), Some(&42));
    }

    #[test]
    fn test_trip_counter_estimate_from_addrec_known_loop() {
        let mut counter = X86SCEVTripCounter::new();
        counter.register_loop(1, 10);

        let addrec = X86SCEVExpr::addrec(X86SCEVExpr::constant(0), X86SCEVExpr::constant(1), 1);
        let tc = counter.estimate_from_addrec(&addrec);
        assert_eq!(tc.max(), Some(10));
    }

    #[test]
    fn test_trip_counter_estimate_unknown_addrec() {
        let counter = X86SCEVTripCounter::new();
        let tc = counter.estimate_from_addrec(&X86SCEVExpr::Unknown);
        assert!(tc.is_unknown());
    }

    #[test]
    fn test_trip_count_signed_non_exact() {
        let counter = X86SCEVTripCounter::new();
        // for (i = 0; i < 100; i += 3): steps of 3
        let tc = counter.compute_trip_count(0, 3, 100, true);
        assert_eq!(tc.max(), Some(34));
        assert!(!tc.is_exact()); // 99 is the last value but limit is 100
    }

    // -------------------------------------------------------------------
    // Stratified CFL-AA Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_stratified_cfl_new() {
        let scfl = X86StratifiedCFLAA::new(4);
        assert_eq!(scfl.max_depth, 4);
        assert!(scfl.field_points_to.is_empty());
    }

    #[test]
    fn test_stratified_field_may_alias_same_offset() {
        let mut scfl = X86StratifiedCFLAA::new(4);
        scfl.add_field_points_to(1, 0, 100);
        assert_eq!(
            scfl.field_may_alias(1, 0, 8, 1, 0, 8),
            AliasResult::MustAlias
        );
    }

    #[test]
    fn test_stratified_field_no_alias_different_offsets() {
        let mut scfl = X86StratifiedCFLAA::new(4);
        assert_eq!(
            scfl.field_may_alias(1, 0, 8, 1, 16, 8),
            AliasResult::NoAlias
        );
    }

    #[test]
    fn test_stratified_field_partial_alias() {
        let mut scfl = X86StratifiedCFLAA::new(4);
        assert_eq!(
            scfl.field_may_alias(1, 0, 8, 1, 4, 8),
            AliasResult::PartialAlias
        );
    }

    #[test]
    fn test_stratified_register_field() {
        let mut scfl = X86StratifiedCFLAA::new(4);
        scfl.register_field(1, 0, 10);
        scfl.register_field(1, 8, 20);
        assert_eq!(scfl.get_field_type(1, 0), Some(10));
        assert_eq!(scfl.get_field_type(1, 8), Some(20));
        assert_eq!(scfl.get_field_type(1, 16), None);
    }

    #[test]
    fn test_stratified_different_pointers_field() {
        let mut scfl = X86StratifiedCFLAA::new(4);
        scfl.add_field_points_to(1, 0, 100);
        scfl.add_field_points_to(2, 0, 200);
        assert_eq!(scfl.field_may_alias(1, 0, 8, 2, 0, 8), AliasResult::NoAlias);
    }

    #[test]
    fn test_stratified_noalias_flag() {
        let mut scfl = X86StratifiedCFLAA::new(4);
        let mut noalias_pts = PointsToSet::empty();
        noalias_pts.is_noalias = true;
        scfl.field_points_to.insert((1, 0), noalias_pts);
        assert_eq!(scfl.field_may_alias(1, 0, 8, 2, 0, 8), AliasResult::NoAlias);
    }

    #[test]
    fn test_stratified_stats_tracking() {
        let mut scfl = X86StratifiedCFLAA::new(4);
        scfl.field_may_alias(1, 0, 8, 1, 0, 8);
        scfl.field_may_alias(1, 0, 8, 1, 16, 8);
        assert_eq!(scfl.stats.total_field_queries, 2);
        assert_eq!(scfl.stats.field_mustalias, 1);
        assert_eq!(scfl.stats.field_noalias, 1);
    }

    // -------------------------------------------------------------------
    // MemorySSA Placer Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_mssa_placer_new() {
        let mut idom = HashMap::new();
        idom.insert(1, 0);
        idom.insert(2, 1);
        idom.insert(3, 1);
        let placer = X86MemorySSAPlacer::new(idom, 1);
        assert_eq!(placer.entry_block, 1);
    }

    #[test]
    fn test_mssa_placer_dominates() {
        let mut idom = HashMap::new();
        idom.insert(1, 0);
        idom.insert(2, 1);
        idom.insert(3, 2);
        let placer = X86MemorySSAPlacer::new(idom, 1);
        assert!(placer.dominates(1, 2));
        assert!(placer.dominates(1, 3));
        assert!(placer.dominates(2, 3));
        assert!(!placer.dominates(2, 1));
        assert!(!placer.dominates(3, 1));
    }

    #[test]
    fn test_mssa_placer_self_dominates() {
        let mut idom = HashMap::new();
        idom.insert(1, 0);
        let placer = X86MemorySSAPlacer::new(idom, 1);
        assert!(placer.dominates(1, 1));
    }

    #[test]
    fn test_mssa_placer_get_df() {
        let mut idom = HashMap::new();
        idom.insert(1, 0);
        idom.insert(2, 1);
        let placer = X86MemorySSAPlacer::new(idom, 1);
        let df = placer.get_df(2);
        // DF should be computed (may be empty for this simple graph)
        assert!(df.is_empty() || !df.is_empty());
    }

    #[test]
    fn test_mssa_placer_idf_empty() {
        let mut idom = HashMap::new();
        idom.insert(1, 0);
        let mut placer = X86MemorySSAPlacer::new(idom, 1);
        let blocks = HashSet::new();
        let idf = placer.iterated_dominance_frontier(&blocks);
        assert!(idf.is_empty());
    }

    #[test]
    fn test_mssa_placer_place_phis_single_block() {
        let mut idom = HashMap::new();
        idom.insert(1, 0);
        let mut placer = X86MemorySSAPlacer::new(idom, 1);
        let mut defs = HashSet::new();
        defs.insert(1);
        let phi_blocks = placer.place_phis(&defs);
        assert!(phi_blocks.contains(&1));
    }

    // -------------------------------------------------------------------
    // Alias Evaluator Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_evaluator_new() {
        let eval = X86AliasEvaluator::new();
        assert!(eval.ground_truth.is_empty());
        assert!(eval.results.is_empty());
    }

    #[test]
    fn test_evaluator_add_and_evaluate_correct() {
        let mut eval = X86AliasEvaluator::new();
        eval.add_ground_truth(1, 8, 2, 8, AliasResult::NoAlias);
        let result = X86AliasResult::new(AliasResult::NoAlias, "test");
        eval.evaluate(1, 8, 2, 8, result);
        assert_eq!(eval.results.len(), 1);
        assert!(eval.results[0].correct);
    }

    #[test]
    fn test_evaluator_unsound_result() {
        let mut eval = X86AliasEvaluator::new();
        eval.add_ground_truth(1, 8, 1, 8, AliasResult::MustAlias);
        let result = X86AliasResult::new(AliasResult::NoAlias, "test");
        eval.evaluate(1, 8, 1, 8, result);
        assert!(!eval.results[0].correct);
    }

    #[test]
    fn test_evaluator_conservative_is_sound() {
        let mut eval = X86AliasEvaluator::new();
        eval.add_ground_truth(1, 8, 2, 8, AliasResult::MustAlias);
        let result = X86AliasResult::new(AliasResult::MayAlias, "test");
        eval.evaluate(1, 8, 2, 8, result);
        assert!(eval.results[0].correct); // conservative is sound
    }

    #[test]
    fn test_evaluator_summary_all_correct() {
        let mut eval = X86AliasEvaluator::new();
        eval.add_ground_truth(1, 8, 2, 8, AliasResult::NoAlias);
        eval.add_ground_truth(3, 8, 4, 8, AliasResult::MustAlias);
        eval.evaluate(1, 8, 2, 8, X86AliasResult::new(AliasResult::NoAlias, "t"));
        eval.evaluate(3, 8, 4, 8, X86AliasResult::new(AliasResult::MustAlias, "t"));
        eval.compute_summary();
        assert_eq!(eval.summary.total_queries, 2);
        assert_eq!(eval.summary.incorrect, 0);
        assert_eq!(eval.summary.soundness, 1.0);
    }

    #[test]
    fn test_evaluator_precision_zero_when_all_mayalias() {
        let mut eval = X86AliasEvaluator::new();
        eval.add_ground_truth(1, 8, 2, 8, AliasResult::NoAlias);
        eval.evaluate(1, 8, 2, 8, X86AliasResult::new(AliasResult::MayAlias, "t"));
        eval.compute_summary();
        assert_eq!(eval.summary.precision, 0.0);
        assert_eq!(eval.summary.soundness, 1.0);
    }

    #[test]
    fn test_evaluator_precision_full_when_all_noalias() {
        let mut eval = X86AliasEvaluator::new();
        eval.add_ground_truth(1, 8, 2, 8, AliasResult::NoAlias);
        eval.evaluate(1, 8, 2, 8, X86AliasResult::new(AliasResult::NoAlias, "t"));
        eval.compute_summary();
        assert_eq!(eval.summary.precision, 1.0);
    }

    #[test]
    fn test_evaluator_report_contents() {
        let eval = X86AliasEvaluator::new();
        let report = eval.report();
        assert!(report.contains("Alias Analysis Evaluation Report"));
        assert!(report.contains("Precision"));
        assert!(report.contains("Soundness"));
    }

    #[test]
    fn test_evaluator_multiple_queries_all_correct() {
        let mut eval = X86AliasEvaluator::new();
        for i in 0..100 {
            eval.add_ground_truth(i, 8, i + 100, 8, AliasResult::NoAlias);
        }
        for i in 0..100 {
            eval.evaluate(
                i,
                8,
                i + 100,
                8,
                X86AliasResult::new(AliasResult::NoAlias, "test"),
            );
        }
        eval.compute_summary();
        assert_eq!(eval.summary.total_queries, 100);
        assert_eq!(eval.summary.incorrect, 0);
        assert_eq!(eval.summary.correct_noalias, 100);
    }

    // -------------------------------------------------------------------
    // Batch Alias Query Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_batch_query_new() {
        let batch = X86BatchAliasQuery::new(10);
        assert_eq!(batch.max_batch_size, 10);
        assert!(batch.pending.is_empty());
    }

    #[test]
    fn test_batch_query_add_and_flush() {
        let mut batch = X86BatchAliasQuery::new(10);
        batch.add(1, 8, 2, 8);
        batch.add(3, 4, 4, 4);
        let results = batch.flush(|a, _sa, b, _sb| {
            if a == b {
                AliasResult::MustAlias
            } else {
                AliasResult::NoAlias
            }
        });
        assert_eq!(results.len(), 2);
        assert_eq!(batch.pending_count(), 0);
    }

    #[test]
    fn test_batch_query_cache_hit() {
        let mut batch = X86BatchAliasQuery::new(10);
        batch.add(1, 8, 2, 8);
        batch.flush(|_, _, _, _| AliasResult::NoAlias);
        batch.add(1, 8, 2, 8);
        batch.flush(|_, _, _, _| AliasResult::MayAlias);
        assert_eq!(batch.stats.cache_hits, 1);
    }

    #[test]
    fn test_batch_query_symmetric_cache() {
        let mut batch = X86BatchAliasQuery::new(10);
        batch.add(1, 8, 2, 8);
        batch.flush(|_, _, _, _| AliasResult::NoAlias);
        batch.add(2, 8, 1, 8);
        batch.flush(|_, _, _, _| AliasResult::MayAlias);
        assert_eq!(batch.stats.cache_hits, 1);
    }

    #[test]
    fn test_batch_query_clear() {
        let mut batch = X86BatchAliasQuery::new(10);
        batch.add(1, 8, 2, 8);
        batch.clear();
        assert!(batch.pending.is_empty());
        assert!(batch.cache.is_empty());
    }

    #[test]
    fn test_batch_query_stats() {
        let mut batch = X86BatchAliasQuery::new(10);
        batch.add(1, 8, 2, 8);
        batch.add(3, 4, 4, 4);
        batch.flush(|_, _, _, _| AliasResult::MayAlias);
        assert_eq!(batch.stats.queries_processed, 2);
        assert_eq!(batch.stats.batches_processed, 1);
    }

    // -------------------------------------------------------------------
    // AliasSetTracker Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_tracker_new() {
        let tracker = X86AliasSetTracker::new();
        assert_eq!(tracker.sets.len(), 0);
    }

    #[test]
    fn test_tracker_get_or_create() {
        let mut tracker = X86AliasSetTracker::new();
        let set_id = tracker.get_or_create_set(100);
        assert!(set_id > 0);
        assert_eq!(tracker.sets.len(), 1);
    }

    #[test]
    fn test_tracker_same_id_for_same_pointer() {
        let mut tracker = X86AliasSetTracker::new();
        let id1 = tracker.get_or_create_set(100);
        let id2 = tracker.get_or_create_set(100);
        assert_eq!(id1, id2);
    }

    #[test]
    fn test_tracker_merge_sets_reduces_count() {
        let mut tracker = X86AliasSetTracker::new();
        tracker.get_or_create_set(100);
        tracker.get_or_create_set(200);
        assert_eq!(tracker.sets.len(), 2);
        tracker.merge_sets(100, 200);
        assert_eq!(tracker.sets.len(), 1);
        assert_eq!(tracker.stats.total_merges, 1);
    }

    #[test]
    fn test_tracker_same_set_id_after_merge() {
        let mut tracker = X86AliasSetTracker::new();
        tracker.merge_sets(100, 200);
        let id_a = tracker.get_set_id(100);
        let id_b = tracker.get_set_id(200);
        assert_eq!(id_a, id_b);
    }

    #[test]
    fn test_tracker_get_set_returns_set() {
        let mut tracker = X86AliasSetTracker::new();
        tracker.get_or_create_set(100);
        let set = tracker.get_set(100);
        assert!(set.is_some());
        assert!(set.unwrap().pointers.contains(&100));
    }

    #[test]
    fn test_tracker_get_set_nonexistent() {
        let tracker = X86AliasSetTracker::new();
        assert!(tracker.get_set(999).is_none());
    }

    #[test]
    fn test_tracker_all_sets() {
        let mut tracker = X86AliasSetTracker::new();
        tracker.get_or_create_set(100);
        tracker.get_or_create_set(200);
        tracker.get_or_create_set(300);
        let all = tracker.get_all_sets();
        assert_eq!(all.len(), 3);
    }

    #[test]
    fn test_tracker_max_set_size_updates() {
        let mut tracker = X86AliasSetTracker::new();
        for i in 1..=20 {
            tracker.merge_sets(100, i * 10);
        }
        let stats = tracker.get_stats();
        assert!(stats.max_set_size >= 20);
    }

    #[test]
    fn test_tracker_merge_same_set_noop() {
        let mut tracker = X86AliasSetTracker::new();
        tracker.merge_sets(100, 200);
        let merges_before = tracker.stats.total_merges;
        tracker.merge_sets(100, 200);
        assert_eq!(tracker.stats.total_merges, merges_before);
    }

    #[test]
    fn test_tracker_merge_chain() {
        let mut tracker = X86AliasSetTracker::new();
        tracker.merge_sets(1, 2);
        tracker.merge_sets(2, 3);
        tracker.merge_sets(3, 4);
        // All should be in the same set
        let id1 = tracker.get_set_id(1);
        let id4 = tracker.get_set_id(4);
        assert_eq!(id1, id4);
        assert_eq!(tracker.sets.len(), 1);
    }

    // -------------------------------------------------------------------
    // CaptureTracker Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_capture_tracker_new_not_captured() {
        let ct = X86CaptureTracker::new();
        assert!(!ct.is_captured());
        assert!(ct.is_not_captured());
    }

    #[test]
    fn test_capture_tracker_captured_by_ret() {
        let mut ct = X86CaptureTracker::new();
        ct.mark_captured_by_ret(10);
        assert!(ct.is_captured());
        assert!(ct.is_captured_by_ret_only());
    }

    #[test]
    fn test_capture_tracker_captured_by_arg_not_ret_only() {
        let mut ct = X86CaptureTracker::new();
        ct.mark_captured_by_ret(1);
        ct.mark_captured_by_arg(2);
        assert!(ct.is_captured());
        assert!(!ct.is_captured_by_ret_only());
    }

    #[test]
    fn test_capture_tracker_captured_by_global() {
        let mut ct = X86CaptureTracker::new();
        ct.mark_captured_by_global(1);
        assert!(ct.is_captured());
        assert!(!ct.is_captured_by_ret_only());
    }

    #[test]
    fn test_capture_tracker_uses_dont_capture() {
        let mut ct = X86CaptureTracker::new();
        ct.mark_use();
        ct.mark_use();
        ct.mark_use();
        assert_eq!(ct.total_uses, 3);
        assert!(!ct.is_captured());
    }

    #[test]
    fn test_capture_tracker_users_tracking() {
        let mut ct = X86CaptureTracker::new();
        ct.mark_captured_by_ret(10);
        ct.mark_captured_by_arg(20);
        assert!(ct.capturing_users.contains(&10));
        assert!(ct.capturing_users.contains(&20));
        assert_eq!(ct.capturing_users.len(), 2);
    }

    // -------------------------------------------------------------------
    // MemDepBlock Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_mem_dep_block_new() {
        let mssa = X86MemorySSA::new();
        let mdb = X86MemDepBlock::new(mssa);
        assert_eq!(mdb.max_blocks, 100);
    }

    #[test]
    fn test_mem_dep_block_find_def_returns_some() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);
        let mut mdb = X86MemDepBlock::new(mssa);
        let def = mdb.find_def_in_block(1, 100, 8);
        assert!(def.is_some());
    }

    #[test]
    fn test_mem_dep_block_find_def_empty_block() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[], &[1]);
        let mut mdb = X86MemDepBlock::new(mssa);
        let def = mdb.find_def_in_block(1, 100, 8);
        assert!(def.is_none());
    }

    #[test]
    fn test_mem_dep_block_cache_works() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);
        let mut mdb = X86MemDepBlock::new(mssa);
        let def1 = mdb.find_def_in_block(1, 100, 8);
        let def2 = mdb.find_def_in_block(1, 100, 8);
        assert_eq!(def1, def2);
    }

    #[test]
    fn test_mem_dep_block_invalidate_clears_cache() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[], &[1]);
        let mut mdb = X86MemDepBlock::new(mssa);
        let _ = mdb.find_def_in_block(1, 100, 8);
        mdb.invalidate_cache();
        assert!(mdb.block_cache.is_empty());
    }

    #[test]
    fn test_mem_dep_block_find_nearest_dominating() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        let mut idom = HashMap::new();
        idom.insert(1, 0);
        idom.insert(2, 1);
        mssa.set_dominators(idom);
        mssa.build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);
        let mut mdb = X86MemDepBlock::new(mssa);
        let def = mdb.find_nearest_dominating_def(2, 100, 8);
        assert!(def.is_some());
    }

    // -------------------------------------------------------------------
    // AAQueryCache Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_aa_query_cache_new_empty() {
        let cache = X86AAQueryCache::new(10);
        assert!(cache.is_empty());
        assert_eq!(cache.len(), 0);
    }

    #[test]
    fn test_aa_query_cache_get_insert_hit() {
        let mut cache = X86AAQueryCache::new(10);
        cache.insert(1, 8, 2, 8, AliasResult::NoAlias);
        let result = cache.get(1, 8, 2, 8);
        assert_eq!(result, Some(AliasResult::NoAlias));
    }

    #[test]
    fn test_aa_query_cache_symmetric_lookup() {
        let mut cache = X86AAQueryCache::new(10);
        cache.insert(1, 8, 2, 8, AliasResult::NoAlias);
        let result = cache.get(2, 8, 1, 8);
        assert_eq!(result, Some(AliasResult::NoAlias));
    }

    #[test]
    fn test_aa_query_cache_eviction_lru() {
        let mut cache = X86AAQueryCache::new(3);
        cache.insert(1, 1, 1, 1, AliasResult::NoAlias);
        cache.insert(2, 2, 2, 2, AliasResult::MayAlias);
        cache.insert(3, 3, 3, 3, AliasResult::MustAlias);
        // Access the first one to make it recently used
        let _ = cache.get(1, 1, 1, 1);
        // Insert a 4th — this should evict the LRU (2,2,2,2)
        cache.insert(4, 4, 4, 4, AliasResult::PartialAlias);
        assert_eq!(cache.len(), 3);
    }

    #[test]
    fn test_aa_query_cache_clear() {
        let mut cache = X86AAQueryCache::new(10);
        cache.insert(1, 8, 2, 8, AliasResult::NoAlias);
        cache.clear();
        assert!(cache.is_empty());
        assert_eq!(cache.len(), 0);
    }

    #[test]
    fn test_aa_query_cache_miss() {
        let mut cache = X86AAQueryCache::new(10);
        let result = cache.get(1, 8, 2, 8);
        assert_eq!(result, None);
    }

    #[test]
    fn test_aa_query_cache_zero_capacity() {
        let mut cache = X86AAQueryCache::new(0);
        cache.insert(1, 8, 2, 8, AliasResult::NoAlias);
        assert!(cache.is_empty());
    }

    // -------------------------------------------------------------------
    // PointsToAnalysis Tests
    // -------------------------------------------------------------------

    #[test]
    fn test_pta_new_not_field_sensitive() {
        let pta = X86PointsToAnalysis::new(false);
        assert!(!pta.field_sensitive);
        assert!(pta.stratified.is_none());
    }

    #[test]
    fn test_pta_new_field_sensitive() {
        let pta = X86PointsToAnalysis::new(true);
        assert!(pta.field_sensitive);
        assert!(pta.stratified.is_some());
    }

    #[test]
    fn test_pta_may_alias_no_field() {
        let mut pta = X86PointsToAnalysis::new(false);
        pta.cfl.register_pointer(1);
        pta.cfl.register_pointer(2);
        pta.cfl.add_points_to(1, 100);
        pta.cfl.add_points_to(2, 200);
        pta.solve();
        let result = pta.may_alias(1, 0, 8, 2, 0, 8);
        assert_eq!(result, AliasResult::NoAlias);
    }

    #[test]
    fn test_pta_field_sensitive_query_no_overlap() {
        let mut pta = X86PointsToAnalysis::new(true);
        if let Some(ref mut strat) = pta.stratified {
            strat.add_field_points_to(1, 0, 100);
        }
        pta.solve();
        let result = pta.may_alias(1, 0, 8, 1, 16, 8);
        assert_eq!(result, AliasResult::NoAlias);
    }

    #[test]
    fn test_pta_field_sensitive_query_must_alias() {
        let mut pta = X86PointsToAnalysis::new(true);
        if let Some(ref mut strat) = pta.stratified {
            strat.add_field_points_to(1, 0, 100);
        }
        pta.solve();
        let result = pta.may_alias(1, 0, 8, 1, 0, 8);
        assert_eq!(result, AliasResult::MustAlias);
    }

    #[test]
    fn test_pta_solve_twice_is_idempotent() {
        let mut pta = X86PointsToAnalysis::new(false);
        pta.solve();
        let solved1 = pta.cfl.solved;
        pta.solve();
        let solved2 = pta.cfl.solved;
        assert_eq!(solved1, solved2);
    }

    // -------------------------------------------------------------------
    // Integration: Full pipeline with multiple analyses
    // -------------------------------------------------------------------

    #[test]
    fn test_full_pipeline_noalias_allocas_all_analyses() {
        let mut aa = X86AliasAnalysis::new();
        aa.basic_aa.register_alloca(100, 8);
        aa.basic_aa.register_alloca(200, 8);
        aa.initialize();
        let loc_a = MemoryLocation::new(100, 8);
        let loc_b = MemoryLocation::new(200, 8);
        let result = aa.alias(&loc_a, &loc_b);
        assert_eq!(result.result, AliasResult::NoAlias);
        assert_eq!(result.source, "BasicAA");
    }

    #[test]
    fn test_full_pipeline_tbaa_noalias() {
        let mut aa = X86AliasAnalysis::new();
        aa.tbaa.add_type_node(TBAANode::new(1, 0, "root1"));
        aa.tbaa.add_type_node(TBAANode::new(2, 1, "int"));
        aa.tbaa.add_type_node(TBAANode::new(3, 0, "root2"));
        aa.tbaa.add_type_node(TBAANode::new(4, 3, "float"));
        aa.initialize();
        let loc_a = MemoryLocation::new(100, 8).with_tbaa("int:2:1".to_string());
        let loc_b = MemoryLocation::new(200, 8).with_tbaa("float:4:3".to_string());
        let result = aa.alias(&loc_a, &loc_b);
        assert_eq!(result.result, AliasResult::NoAlias);
    }

    #[test]
    fn test_full_pipeline_scoped_noalias_works() {
        let mut aa = X86AliasAnalysis::new();
        aa.scoped_noalias_aa.register_noalias(1, 10, 20);
        aa.initialize();
        let loc_a = MemoryLocation::new(100, 8)
            .with_scoped_noalias("1".to_string(), vec!["10".to_string()]);
        let loc_b = MemoryLocation::new(200, 8)
            .with_scoped_noalias("1".to_string(), vec!["20".to_string()]);
        let result = aa.alias(&loc_a, &loc_b);
        assert_eq!(result.result, AliasResult::NoAlias);
        assert_eq!(result.source, "ScopedNoAliasAA");
    }

    #[test]
    fn test_full_pipeline_get_mem_dep() {
        let mut aa = X86AliasAnalysis::new();
        aa.memory_ssa.set_entry_block(1);
        aa.memory_ssa
            .build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);
        aa.initialize();
        let result = aa.get_mem_dep(100, 8, 10);
        assert!(matches!(
            result.dep_kind,
            X86MemDepKind::Def | X86MemDepKind::NonLocal | X86MemDepKind::Unknown
        ));
    }

    #[test]
    fn test_full_pipeline_get_mod_ref_for_readnone() {
        let mut aa = X86AliasAnalysis::new();
        aa.globals_mod_ref
            .register_function(100, FunctionModRefInfo::DoesNotAccessMemory);
        aa.initialize();
        let loc = MemoryLocation::new(500, 8);
        let modref = aa.get_mod_ref_for_call(100, &loc);
        assert_eq!(modref, ModRefInfo::NoModRef);
    }

    #[test]
    fn test_full_pipeline_points_to_constant() {
        let mut aa = X86AliasAnalysis::new();
        aa.basic_aa.register_global(500, 8, true);
        aa.initialize();
        let loc = MemoryLocation::new(500, 8);
        assert!(aa.points_to_constant_memory(&loc));
    }

    // -------------------------------------------------------------------
    // Property-based correctness tests
    // -------------------------------------------------------------------

    #[test]
    fn test_alias_reflexive_must_alias() {
        let mut aa = X86AliasAnalysis::new();
        aa.initialize();
        let loc = MemoryLocation::new(42, 8);
        let result = aa.alias(&loc, &loc);
        assert_eq!(result.result, AliasResult::MustAlias);
    }

    #[test]
    fn test_alias_symmetric_same_result() {
        let mut aa = X86AliasAnalysis::new();
        aa.basic_aa.register_alloca(100, 8);
        aa.basic_aa.register_alloca(200, 8);
        aa.initialize();
        let loc_a = MemoryLocation::new(100, 8);
        let loc_b = MemoryLocation::new(200, 8);
        let r_ab = aa.alias(&loc_a, &loc_b).result;
        let r_ba = aa.alias(&loc_b, &loc_a).result;
        assert_eq!(r_ab, r_ba);
    }

    #[test]
    fn test_alias_lattice_ordering() {
        assert!(AliasResult::NoAlias <= AliasResult::MustAlias);
        assert!(AliasResult::NoAlias <= AliasResult::MayAlias);
        assert!(AliasResult::MayAlias <= AliasResult::MustAlias);
        assert!(AliasResult::PartialAlias <= AliasResult::MustAlias);
    }

    #[test]
    fn test_stratified_alias_same_pointer_same_offset_must_alias() {
        let mut scfl = X86StratifiedCFLAA::new(4);
        assert_eq!(
            scfl.field_may_alias(100, 0, 8, 100, 0, 8),
            AliasResult::MustAlias
        );
    }

    // -------------------------------------------------------------------
    // Stress tests for larger inputs
    // -------------------------------------------------------------------

    #[test]
    fn test_stress_basic_aa_many_geps() {
        let mut basic = X86BasicAA::new();
        for i in 0..200 {
            basic.register_alloca(i * 100, 64);
            basic.register_gep((i * 100) + 50, i * 100, 32);
        }
        let loc_a = MemoryLocation::new(50, 8);
        let loc_b = MemoryLocation::new(150, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
        assert!(basic.stats.gep_disambiguations > 0);
    }

    #[test]
    fn test_stress_cfl_aa_long_chain() {
        let mut cfl = X86CFLAA::new();
        let count = 50;
        for i in 1..=count {
            cfl.register_pointer(i);
            if i > 1 {
                cfl.add_assign(i, i - 1);
            }
        }
        cfl.add_points_to(1, 42);
        cfl.solve();
        assert!(cfl.get_points_to(count).objects.contains(&42));
    }

    #[test]
    fn test_stress_alias_set_tracker_chain_merge() {
        let mut tracker = X86AliasSetTracker::new();
        for i in 1..=50 {
            tracker.merge_sets(100 + i, 100 + i + 1);
        }
        let id_first = tracker.get_set_id(101);
        let id_last = tracker.get_set_id(151);
        assert_eq!(id_first, id_last);
        assert_eq!(tracker.sets.len(), 1);
    }

    #[test]
    fn test_stress_evaluator_100_queries() {
        let mut eval = X86AliasEvaluator::new();
        for i in 0..100 {
            eval.add_ground_truth(i, 8, i + 100, 8, AliasResult::NoAlias);
        }
        for i in 0..100 {
            eval.evaluate(
                i,
                8,
                i + 100,
                8,
                X86AliasResult::new(AliasResult::NoAlias, "test"),
            );
        }
        eval.compute_summary();
        assert_eq!(eval.summary.total_queries, 100);
        assert_eq!(eval.summary.incorrect, 0);
        assert_eq!(eval.summary.soundness, 1.0);
        assert_eq!(eval.summary.precision, 1.0);
    }

    #[test]
    fn test_stress_memory_ssa_many_defs() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        let mut ops = Vec::new();
        for i in 0..100 {
            ops.push((1, i, X86Opcode::Store, 100, 8, false));
        }
        mssa.build(&ops, &[1]);
        assert!(mssa.memory_defs.len() >= 100);
        assert!(mssa.verify().is_ok());
    }

    // -------------------------------------------------------------------
    // Edge case tests
    // -------------------------------------------------------------------

    #[test]
    fn test_edge_zero_size_access() {
        let loc_a = MemoryLocation::new(100, 0);
        let loc_b = MemoryLocation::new(200, 0);
        assert!(!loc_a.has_known_size);
        assert!(!loc_b.has_known_size);
    }

    #[test]
    fn test_edge_same_pointer_zero_and_nonzero_size() {
        let mut basic = X86BasicAA::new();
        let loc_a = MemoryLocation::new(100, 0);
        let loc_b = MemoryLocation::new(100, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::MustAlias);
    }

    #[test]
    fn test_edge_both_null_pointers() {
        let mut basic = X86BasicAA::new();
        let loc_a = MemoryLocation::new(0, 8);
        let loc_b = MemoryLocation::new(0, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::MayAlias);
    }

    #[test]
    fn test_edge_null_vs_non_null() {
        let mut basic = X86BasicAA::new();
        let loc_a = MemoryLocation::new(0, 8);
        let loc_b = MemoryLocation::new(100, 8);
        assert_eq!(basic.alias(&loc_a, &loc_b), AliasResult::NoAlias);
    }

    #[test]
    fn test_edge_tbaa_missing_both_tags() {
        let tbaa = X86TypeBasedAA::new();
        assert_eq!(tbaa.may_alias(None, None), AliasResult::MayAlias);
    }

    #[test]
    fn test_edge_scev_no_registered_values() {
        let mut scev_aa = X86SCEVAA::new();
        let loc_a = MemoryLocation::new(1, 8);
        let loc_b = MemoryLocation::new(2, 8);
        assert_eq!(scev_aa.alias(&loc_a, &loc_b), AliasResult::MayAlias);
    }

    #[test]
    fn test_edge_empty_noalias_scopes() {
        let loc = MemoryLocation::new(100, 8).with_scoped_noalias("1".to_string(), vec![]);
        assert!(!loc.has_scoped_noalias());
    }

    #[test]
    fn test_edge_memory_ssa_empty_function() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[], &[1]);
        assert!(mssa.verify().is_ok());
        assert_eq!(mssa.total_accesses(), 1); // live-on-entry only
    }

    #[test]
    fn test_edge_modref_meet_identity() {
        let info = ModRefInfo::Ref;
        assert_eq!(ModRefInfo::meet(info, info), info);
    }

    #[test]
    fn test_edge_globals_modref_unknown_global_address_taken() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_global(42, true, false); // address-taken
        assert!(gmr.function_modifies_global(999, 42));
    }

    #[test]
    fn test_edge_globals_modref_non_address_taken_not_modified() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_global(42, false, false); // not address-taken
        assert!(!gmr.function_modifies_global(999, 42));
    }
}

// ============================================================================
// X86AliasSetPrinter — debugging and visualization for alias sets
// ============================================================================

/// Provides formatted output of alias analysis results for debugging.
#[derive(Debug, Clone)]
pub struct X86AliasSetPrinter {
    /// Whether to include verbose details.
    pub verbose: bool,
    /// Whether to include TBAA tag information.
    pub show_tbaa: bool,
    /// Whether to include scoped noalias information.
    pub show_scoped_noalias: bool,
    /// Whether to include points-to information.
    pub show_points_to: bool,
}

impl X86AliasSetPrinter {
    /// Create a new printer with default settings.
    pub fn new() -> Self {
        X86AliasSetPrinter {
            verbose: false,
            show_tbaa: true,
            show_scoped_noalias: true,
            show_points_to: false,
        }
    }

    /// Print a memory location in human-readable form.
    pub fn print_location(&self, loc: &MemoryLocation) -> String {
        let mut s = format!("ptr=0x{:x}, size={}", loc.ptr, loc.size);
        if self.show_tbaa && loc.has_tbaa() {
            s.push_str(&format!(", tbaa={:?}", loc.tbaa_tag));
        }
        if self.show_scoped_noalias && loc.has_scoped_noalias() {
            s.push_str(&format!(
                ", noalias_domain={:?}, scopes={:?}",
                loc.noalias_domain, loc.noalias_scopes
            ));
        }
        s
    }

    /// Print a points-to set.
    pub fn print_points_to(&self, pts: &PointsToSet) -> String {
        if pts.is_noalias {
            return "noalias".to_string();
        }
        if pts.includes_unknown {
            return "unknown".to_string();
        }
        let mut s = String::from("{");
        let objs: Vec<String> = pts.objects.iter().map(|o| format!("0x{:x}", o)).collect();
        s.push_str(&objs.join(", "));
        if pts.includes_null {
            s.push_str(", null");
        }
        s.push('}');
        s
    }

    /// Print an alias set.
    pub fn print_alias_set(&self, set: &AliasSet) -> String {
        let mut s = format!("AliasSet[{}]: ", set.id);
        s.push_str(&format!(
            "pointers={}, access={:?}, volatile={}",
            set.pointers.len(),
            set.access_type,
            set.is_volatile
        ));
        if self.verbose {
            s.push_str("\n  Pointers: ");
            let ptrs: Vec<String> = set.pointers.iter().map(|p| format!("0x{:x}", p)).collect();
            s.push_str(&ptrs.join(", "));
        }
        s
    }

    /// Print a full alias analysis result.
    pub fn print_alias_result(&self, result: &X86AliasResult) -> String {
        let mut s = format!("AliasResult: {} (from {})", result.result, result.source);
        if let Some(ref explanation) = result.explanation {
            s.push_str(&format!("\n  Explanation: {}", explanation));
        }
        s
    }

    /// Print a memory dependence result.
    pub fn print_mem_dep(&self, result: &X86MemDepResult) -> String {
        format!(
            "MemDep: kind={}, dep_inst={:?}, access_id={:?}",
            result.dep_kind, result.dep_inst, result.access_id
        )
    }

    /// Print X86AliasAnalysis stats in a formatted table.
    pub fn print_stats_table(aa: &X86AliasAnalysis) -> String {
        let mut s = String::new();
        s.push_str("+---------------------------+-----------+\n");
        s.push_str("| Analysis                  | Queries   |\n");
        s.push_str("+---------------------------+-----------+\n");
        s.push_str(&format!(
            "| BasicAA                   | {:>9} |\n",
            aa.basic_aa.stats.total_queries
        ));
        s.push_str(&format!(
            "| CFL-AA                    | {:>9} |\n",
            aa.cfl_aa.stats.queries_resolved
        ));
        s.push_str(&format!(
            "| SCEV-AA                   | {:>9} |\n",
            aa.scev_aa.stats.total_queries
        ));
        s.push_str(&format!(
            "| GlobalsModRef             | {:>9} |\n",
            aa.globals_mod_ref.stats.queries_resolved
        ));
        s.push_str(&format!(
            "| TypeBasedAA               | {:>9} |\n",
            aa.tbaa.stats.total_queries
        ));
        s.push_str(&format!(
            "| ScopedNoAliasAA           | {:>9} |\n",
            aa.scoped_noalias_aa.stats.total_queries
        ));
        s.push_str("+---------------------------+-----------+\n");
        s.push_str(&format!(
            "| Total                     | {:>9} |\n",
            aa.total_queries
        ));
        s.push_str("+---------------------------+-----------+\n");
        s
    }
}

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

// ============================================================================
// X86AAConfig — configuration for the alias analysis pipeline
// ============================================================================

/// Configuration options for the X86 alias analysis pipeline.
#[derive(Debug, Clone)]
pub struct X86AAConfig {
    /// Enable Basic Alias Analysis.
    pub enable_basic_aa: bool,
    /// Enable CFL Andersen's alias analysis.
    pub enable_cfl_aa: bool,
    /// Enable SCEV-based alias analysis.
    pub enable_scev_aa: bool,
    /// Enable GlobalsModRef analysis.
    pub enable_globals_mod_ref: bool,
    /// Enable Type-Based Alias Analysis.
    pub enable_tbaa: bool,
    /// Enable Scoped NoAlias analysis.
    pub enable_scoped_noalias: bool,
    /// Enable MemorySSA construction.
    pub enable_memory_ssa: bool,
    /// Enable memory dependence analysis.
    pub enable_mem_dep: bool,
    /// Maximum depth for alias query recursion.
    pub max_recursion_depth: usize,
    /// Size of the alias result cache.
    pub alias_cache_size: usize,
    /// Size of the memdep cache.
    pub memdep_cache_size: usize,
    /// Whether to optimize MemorySSA uses.
    pub optimize_memory_ssa: bool,
    /// Whether to use field-sensitive CFL-AA.
    pub field_sensitive_cfl: bool,
    /// Maximum number of iterations for CFL-AA fixpoint.
    pub cfl_max_iterations: u64,
    /// Default SCEV max backedge count.
    pub scev_max_backedge_count: u64,
}

impl Default for X86AAConfig {
    fn default() -> Self {
        X86AAConfig {
            enable_basic_aa: true,
            enable_cfl_aa: true,
            enable_scev_aa: true,
            enable_globals_mod_ref: true,
            enable_tbaa: true,
            enable_scoped_noalias: true,
            enable_memory_ssa: true,
            enable_mem_dep: true,
            max_recursion_depth: X86_ALIAS_MAX_RECURSION_DEPTH,
            alias_cache_size: 2048,
            memdep_cache_size: X86_MEMDEP_CACHE_SIZE,
            optimize_memory_ssa: true,
            field_sensitive_cfl: false,
            cfl_max_iterations: 1_000_000,
            scev_max_backedge_count: X86_SCEV_MAX_BACKEDGE_TAKEN_COUNT,
        }
    }
}

impl X86AAConfig {
    /// Create a configuration optimized for speed (less analyses).
    pub fn fast() -> Self {
        X86AAConfig {
            enable_basic_aa: true,
            enable_cfl_aa: false,
            enable_scev_aa: false,
            enable_globals_mod_ref: true,
            enable_tbaa: true,
            enable_scoped_noalias: false,
            enable_memory_ssa: false,
            enable_mem_dep: false,
            ..Default::default()
        }
    }

    /// Create a configuration optimized for precision (all analyses).
    pub fn precise() -> Self {
        X86AAConfig {
            field_sensitive_cfl: true,
            ..Default::default()
        }
    }

    /// Create a minimal configuration (only BasicAA).
    pub fn minimal() -> Self {
        X86AAConfig {
            enable_basic_aa: true,
            enable_cfl_aa: false,
            enable_scev_aa: false,
            enable_globals_mod_ref: false,
            enable_tbaa: false,
            enable_scoped_noalias: false,
            enable_memory_ssa: false,
            enable_mem_dep: false,
            optimize_memory_ssa: false,
            ..Default::default()
        }
    }

    /// Build an X86AliasAnalysis from this configuration.
    pub fn build_analysis(&self) -> X86AliasAnalysis {
        let mut aa = X86AliasAnalysis::new();

        if !self.enable_cfl_aa {
            aa.cfl_aa = X86CFLAA::new();
        }
        if !self.enable_scev_aa {
            aa.scev_aa = X86SCEVAA::new();
        }

        aa.max_alias_cache_size = self.alias_cache_size;

        if self.enable_memory_ssa && self.optimize_memory_ssa {
            aa.optimize_memory_ssa();
        }

        if self.enable_mem_dep {
            aa.initialize();
        }

        aa
    }
}

// ============================================================================
// Extended helper functions and utilities
// ============================================================================

/// Check if a given TBAA tag indicates a constant (read-only) memory access.
pub fn is_constant_tbaa_access(tag: Option<&TBAATag>, tbaa: &X86TypeBasedAA) -> bool {
    tbaa.is_constant_tag(tag)
}

/// Merge two scoped noalias domain sets.
pub fn merge_noalias_domains(
    domain_a: Option<&str>,
    scopes_a: &[String],
    domain_b: Option<&str>,
    scopes_b: &[String],
) -> (Option<String>, Vec<String>) {
    let domain = match (domain_a, domain_b) {
        (Some(a), Some(b)) if a == b => Some(a.to_string()),
        (Some(a), None) => Some(a.to_string()),
        (None, Some(b)) => Some(b.to_string()),
        _ => None,
    };

    let mut scopes = Vec::new();
    scopes.extend(scopes_a.iter().cloned());
    for s in scopes_b {
        if !scopes.contains(s) {
            scopes.push(s.clone());
        }
    }

    (domain, scopes)
}

/// Compare two alias results for consistency.
pub fn check_alias_consistency(r1: AliasResult, r2: AliasResult) -> bool {
    match (r1, r2) {
        (AliasResult::NoAlias, AliasResult::NoAlias) => true,
        (AliasResult::MustAlias, AliasResult::MustAlias) => true,
        (AliasResult::NoAlias, AliasResult::MustAlias) => false,
        (AliasResult::MustAlias, AliasResult::NoAlias) => false,
        _ => true, // MayAlias and PartialAlias are compatible with everything
    }
}

/// Compute the distance between two alias results (0 = identical, 1 = opposite).
pub fn alias_result_distance(a: AliasResult, b: AliasResult) -> f64 {
    if a == b {
        return 0.0;
    }
    match (a, b) {
        (AliasResult::NoAlias, AliasResult::MustAlias) => 1.0,
        (AliasResult::MustAlias, AliasResult::NoAlias) => 1.0,
        (AliasResult::NoAlias, AliasResult::MayAlias) => 0.5,
        (AliasResult::MayAlias, AliasResult::NoAlias) => 0.5,
        (AliasResult::MustAlias, AliasResult::MayAlias) => 0.5,
        (AliasResult::MayAlias, AliasResult::MustAlias) => 0.5,
        _ => 0.75,
    }
}

/// Convert a set of pointer ids into a sorted vec for deterministic output.
pub fn sort_pointers(pointers: &HashSet<u64>) -> Vec<u64> {
    let mut v: Vec<u64> = pointers.iter().copied().collect();
    v.sort();
    v
}

/// Compute the intersection of two pointer sets.
pub fn intersect_pointers(a: &HashSet<u64>, b: &HashSet<u64>) -> HashSet<u64> {
    a.intersection(b).copied().collect()
}

/// Compute the union of two pointer sets.
pub fn union_pointers(a: &HashSet<u64>, b: &HashSet<u64>) -> HashSet<u64> {
    a.union(b).copied().collect()
}

// ============================================================================
// X86AliasAnalysisPipeline — complete analysis pipeline builder
// ============================================================================

/// Builder for constructing and running the complete X86 alias analysis
/// pipeline with configurable stages.
#[derive(Debug, Clone)]
pub struct X86AliasAnalysisPipeline {
    /// The analysis configuration.
    pub config: X86AAConfig,
    /// The constructed alias analysis.
    pub analysis: Option<X86AliasAnalysis>,
    /// Pipeline stage execution log.
    pub stage_log: Vec<String>,
}

impl X86AliasAnalysisPipeline {
    /// Create a new pipeline with default configuration.
    pub fn new() -> Self {
        X86AliasAnalysisPipeline {
            config: X86AAConfig::default(),
            analysis: None,
            stage_log: Vec::new(),
        }
    }

    /// Create a new pipeline with a specific configuration.
    pub fn with_config(config: X86AAConfig) -> Self {
        X86AliasAnalysisPipeline {
            config,
            analysis: None,
            stage_log: Vec::new(),
        }
    }

    /// Build the analysis from the configuration.
    pub fn build(&mut self) {
        self.analysis = Some(self.config.build_analysis());
        self.stage_log
            .push("Built analysis from config".to_string());
    }

    /// Register an alloca with the BasicAA.
    pub fn register_alloca(&mut self, ptr: u64, size: u64) {
        if let Some(ref mut aa) = self.analysis {
            aa.basic_aa.register_alloca(ptr, size);
            self.stage_log
                .push(format!("Registered alloca: ptr=0x{:x}, size={}", ptr, size));
        }
    }

    /// Register a global variable.
    pub fn register_global(&mut self, ptr: u64, size: u64, is_constant: bool) {
        if let Some(ref mut aa) = self.analysis {
            aa.basic_aa.register_global(ptr, size, is_constant);
            if self.config.enable_globals_mod_ref {
                aa.globals_mod_ref.register_global(ptr, true, is_constant);
            }
            self.stage_log
                .push(format!("Registered global: ptr=0x{:x}, size={}", ptr, size));
        }
    }

    /// Register a GEP relationship.
    pub fn register_gep(&mut self, gep_ptr: u64, base: u64, offset: i64) {
        if let Some(ref mut aa) = self.analysis {
            aa.basic_aa.register_gep(gep_ptr, base, offset);
            self.stage_log.push(format!(
                "Registered GEP: gep=0x{:x}, base=0x{:x}, offset={}",
                gep_ptr, base, offset
            ));
        }
    }

    /// Register a TBAA type node.
    pub fn register_tbaa_node(&mut self, node: TBAANode) {
        if let Some(ref mut aa) = self.analysis {
            aa.tbaa.add_type_node(node);
            self.stage_log.push("Registered TBAA node".to_string());
        }
    }

    /// Register a scoped noalias pair.
    pub fn register_noalias_scope(&mut self, domain: u64, scope_a: u64, scope_b: u64) {
        if let Some(ref mut aa) = self.analysis {
            aa.scoped_noalias_aa
                .register_noalias(domain, scope_a, scope_b);
            self.stage_log.push(format!(
                "Registered scoped noalias: domain={}, {} <-> {}",
                domain, scope_a, scope_b
            ));
        }
    }

    /// Register a CFL pointer.
    pub fn register_cfl_pointer(&mut self, ptr: u64) {
        if let Some(ref mut aa) = self.analysis {
            aa.cfl_aa.register_pointer(ptr);
            self.stage_log
                .push(format!("Registered CFL pointer: 0x{:x}", ptr));
        }
    }

    /// Add a CFL assignment edge.
    pub fn add_cfl_assign(&mut self, lhs: u64, rhs: u64) {
        if let Some(ref mut aa) = self.analysis {
            aa.cfl_aa.add_assign(lhs, rhs);
        }
    }

    /// Register a function's mod/ref behavior.
    pub fn register_function_behavior(&mut self, func_id: u64, behavior: FunctionModRefInfo) {
        if let Some(ref mut aa) = self.analysis {
            aa.globals_mod_ref.register_function(func_id, behavior);
        }
    }

    /// Build MemorySSA from operations.
    pub fn build_memory_ssa(
        &mut self,
        ops: &[(u64, u64, X86Opcode, u64, u64, bool)],
        block_order: &[u64],
    ) {
        if let Some(ref mut aa) = self.analysis {
            aa.build_memory_ssa(ops, block_order);
            self.stage_log.push("Built MemorySSA".to_string());
        }
    }

    /// Initialize all sub-analyses.
    pub fn initialize(&mut self) {
        if let Some(ref mut aa) = self.analysis {
            aa.initialize();
            self.stage_log.push("Initialized all analyses".to_string());
        }
    }

    /// Run an alias query through the pipeline.
    pub fn query(&mut self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> X86AliasResult {
        match self.analysis {
            Some(ref mut aa) => aa.alias(loc_a, loc_b),
            None => X86AliasResult::new(AliasResult::MayAlias, "uninitialized"),
        }
    }

    /// Get the stage execution log.
    pub fn get_log(&self) -> &[String] {
        &self.stage_log
    }

    /// Print a summary of the pipeline execution.
    pub fn print_pipeline_summary(&self) -> String {
        let mut s = String::new();
        s.push_str("=== X86 Alias Analysis Pipeline Summary ===\n");
        s.push_str(&format!("Configuration:\n"));
        s.push_str(&format!(
            "  BasicAA:        {}\n",
            self.config.enable_basic_aa
        ));
        s.push_str(&format!(
            "  CFL-AA:         {}\n",
            self.config.enable_cfl_aa
        ));
        s.push_str(&format!(
            "  SCEV-AA:        {}\n",
            self.config.enable_scev_aa
        ));
        s.push_str(&format!(
            "  GlobalsModRef:  {}\n",
            self.config.enable_globals_mod_ref
        ));
        s.push_str(&format!("  TypeBasedAA:    {}\n", self.config.enable_tbaa));
        s.push_str(&format!(
            "  ScopedNoAlias:  {}\n",
            self.config.enable_scoped_noalias
        ));
        s.push_str(&format!(
            "  MemorySSA:      {}\n",
            self.config.enable_memory_ssa
        ));
        s.push_str(&format!(
            "  MemDep:         {}\n",
            self.config.enable_mem_dep
        ));
        s.push_str(&format!("\nStages executed: {}\n", self.stage_log.len()));
        for (i, stage) in self.stage_log.iter().enumerate() {
            s.push_str(&format!("  {}. {}\n", i + 1, stage));
        }
        if let Some(ref aa) = self.analysis {
            s.push_str("\n");
            s.push_str(&X86AliasSetPrinter::print_stats_table(aa));
        }
        s
    }
}

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

// ============================================================================
// Final tests — pipeline builder and printer tests
// ============================================================================

#[cfg(test)]
mod pipeline_tests {
    use super::*;

    #[test]
    fn test_pipeline_new() {
        let pipeline = X86AliasAnalysisPipeline::new();
        assert!(pipeline.analysis.is_none());
        assert!(pipeline.stage_log.is_empty());
    }

    #[test]
    fn test_pipeline_build() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        assert!(pipeline.analysis.is_some());
        assert!(!pipeline.stage_log.is_empty());
    }

    #[test]
    fn test_pipeline_register_alloca() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        pipeline.register_alloca(100, 8);
        assert_eq!(pipeline.stage_log.len(), 2);
    }

    #[test]
    fn test_pipeline_query() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        pipeline.register_alloca(100, 8);
        pipeline.register_alloca(200, 8);
        pipeline.initialize();

        let loc_a = MemoryLocation::new(100, 8);
        let loc_b = MemoryLocation::new(200, 8);
        let result = pipeline.query(&loc_a, &loc_b);
        assert_eq!(result.result, AliasResult::NoAlias);
    }

    #[test]
    fn test_pipeline_uninitialized_query() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        // Query without building
        let loc_a = MemoryLocation::new(100, 8);
        let loc_b = MemoryLocation::new(200, 8);
        let result = pipeline.query(&loc_a, &loc_b);
        assert_eq!(result.result, AliasResult::MayAlias);
        assert_eq!(result.source, "uninitialized");
    }

    #[test]
    fn test_pipeline_print_summary() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        let summary = pipeline.print_pipeline_summary();
        assert!(summary.contains("X86 Alias Analysis Pipeline Summary"));
        assert!(summary.contains("BasicAA"));
    }

    #[test]
    fn test_pipeline_with_config_fast() {
        let config = X86AAConfig::fast();
        let pipeline = X86AliasAnalysisPipeline::with_config(config);
        assert!(!pipeline.config.enable_cfl_aa);
        assert!(!pipeline.config.enable_scev_aa);
    }

    #[test]
    fn test_pipeline_with_config_precise() {
        let config = X86AAConfig::precise();
        let pipeline = X86AliasAnalysisPipeline::with_config(config);
        assert!(pipeline.config.field_sensitive_cfl);
    }

    #[test]
    fn test_pipeline_with_config_minimal() {
        let config = X86AAConfig::minimal();
        let pipeline = X86AliasAnalysisPipeline::with_config(config);
        assert!(pipeline.config.enable_basic_aa);
        assert!(!pipeline.config.enable_cfl_aa);
        assert!(!pipeline.config.enable_memory_ssa);
    }

    #[test]
    fn test_pipeline_register_gep() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        pipeline.register_alloca(1, 64);
        pipeline.register_gep(10, 1, 16);
        assert_eq!(pipeline.stage_log.len(), 3);
    }

    #[test]
    fn test_pipeline_register_tbaa_node() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        pipeline.register_tbaa_node(TBAANode::new(1, 0, "int"));
        assert_eq!(pipeline.stage_log.len(), 2);
    }

    #[test]
    fn test_pipeline_register_noalias_scope() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        pipeline.register_noalias_scope(1, 10, 20);
        assert_eq!(pipeline.stage_log.len(), 2);
    }

    #[test]
    fn test_pipeline_register_cfl_pointer() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        pipeline.register_cfl_pointer(1);
        assert_eq!(pipeline.stage_log.len(), 2);
    }

    #[test]
    fn test_pipeline_register_function_behavior() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        pipeline.register_function_behavior(100, FunctionModRefInfo::DoesNotAccessMemory);
        assert_eq!(pipeline.stage_log.len(), 2);
    }

    #[test]
    fn test_pipeline_build_memory_ssa() {
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();
        pipeline.build_memory_ssa(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);
        assert_eq!(pipeline.stage_log.len(), 2);
    }

    #[test]
    fn test_printer_new() {
        let printer = X86AliasSetPrinter::new();
        assert!(printer.show_tbaa);
        assert!(!printer.verbose);
    }

    #[test]
    fn test_printer_print_location() {
        let printer = X86AliasSetPrinter::new();
        let loc = MemoryLocation::new(0x100, 8).with_tbaa("int".to_string());
        let s = printer.print_location(&loc);
        assert!(s.contains("0x100"));
        assert!(s.contains("int"));
    }

    #[test]
    fn test_printer_print_points_to() {
        let printer = X86AliasSetPrinter::new();
        let pts = PointsToSet::singleton(0x42);
        let s = printer.print_points_to(&pts);
        assert!(s.contains("0x42"));
    }

    #[test]
    fn test_printer_print_alias_set() {
        let printer = X86AliasSetPrinter::new();
        let mut set = AliasSet::new(1);
        set.add_pointer(0x10);
        let s = printer.print_alias_set(&set);
        assert!(s.contains("AliasSet[1]"));
    }

    #[test]
    fn test_printer_print_alias_result() {
        let printer = X86AliasSetPrinter::new();
        let result = X86AliasResult::new(AliasResult::NoAlias, "BasicAA")
            .with_explanation("Distinct allocas");
        let s = printer.print_alias_result(&result);
        assert!(s.contains("NoAlias"));
        assert!(s.contains("BasicAA"));
        assert!(s.contains("Distinct allocas"));
    }

    #[test]
    fn test_printer_print_mem_dep() {
        let printer = X86AliasSetPrinter::new();
        let result = X86MemDepResult {
            dep_inst: Some(42),
            dep_kind: X86MemDepKind::Def,
            access_id: Some(10),
        };
        let s = printer.print_mem_dep(&result);
        assert!(s.contains("Def"));
        assert!(s.contains("42"));
    }

    #[test]
    fn test_printer_stats_table() {
        let aa = X86AliasAnalysis::new();
        let table = X86AliasSetPrinter::print_stats_table(&aa);
        assert!(table.contains("BasicAA"));
        assert!(table.contains("Total"));
    }

    #[test]
    fn test_aa_config_default() {
        let config = X86AAConfig::default();
        assert!(config.enable_basic_aa);
        assert!(config.enable_cfl_aa);
        assert!(config.enable_scev_aa);
    }

    #[test]
    fn test_aa_config_build_analysis() {
        let config = X86AAConfig::default();
        let aa = config.build_analysis();
        assert!(aa.max_alias_cache_size > 0);
    }

    #[test]
    fn test_merge_noalias_domains_same() {
        let (domain, scopes) = merge_noalias_domains(
            Some("1"),
            &["10".to_string()],
            Some("1"),
            &["20".to_string()],
        );
        assert_eq!(domain, Some("1".to_string()));
        assert_eq!(scopes.len(), 2);
    }

    #[test]
    fn test_merge_noalias_domains_different() {
        let (domain, scopes) = merge_noalias_domains(
            Some("1"),
            &["10".to_string()],
            Some("2"),
            &["20".to_string()],
        );
        assert_eq!(domain, None);
        assert_eq!(scopes.len(), 2);
    }

    #[test]
    fn test_check_alias_consistency_same() {
        assert!(check_alias_consistency(
            AliasResult::NoAlias,
            AliasResult::NoAlias
        ));
        assert!(check_alias_consistency(
            AliasResult::MustAlias,
            AliasResult::MustAlias
        ));
    }

    #[test]
    fn test_check_alias_consistency_conflict() {
        assert!(!check_alias_consistency(
            AliasResult::NoAlias,
            AliasResult::MustAlias
        ));
    }

    #[test]
    fn test_check_alias_consistency_mayalias() {
        assert!(check_alias_consistency(
            AliasResult::MayAlias,
            AliasResult::NoAlias
        ));
        assert!(check_alias_consistency(
            AliasResult::MayAlias,
            AliasResult::MustAlias
        ));
    }

    #[test]
    fn test_alias_result_distance_identical() {
        assert_eq!(
            alias_result_distance(AliasResult::NoAlias, AliasResult::NoAlias),
            0.0
        );
    }

    #[test]
    fn test_alias_result_distance_opposite() {
        assert_eq!(
            alias_result_distance(AliasResult::NoAlias, AliasResult::MustAlias),
            1.0
        );
    }

    #[test]
    fn test_sort_pointers() {
        let mut set = HashSet::new();
        set.insert(30);
        set.insert(10);
        set.insert(20);
        let sorted = sort_pointers(&set);
        assert_eq!(sorted, vec![10, 20, 30]);
    }

    #[test]
    fn test_intersect_pointers() {
        let mut a = HashSet::new();
        a.insert(1);
        a.insert(2);
        a.insert(3);
        let mut b = HashSet::new();
        b.insert(2);
        b.insert(3);
        b.insert(4);
        let inter = intersect_pointers(&a, &b);
        assert_eq!(inter.len(), 2);
        assert!(inter.contains(&2));
        assert!(inter.contains(&3));
    }

    #[test]
    fn test_union_pointers() {
        let mut a = HashSet::new();
        a.insert(1);
        a.insert(2);
        let mut b = HashSet::new();
        b.insert(2);
        b.insert(3);
        let union = union_pointers(&a, &b);
        assert_eq!(union.len(), 3);
        assert!(union.contains(&1));
        assert!(union.contains(&2));
        assert!(union.contains(&3));
    }
}

// ============================================================================
// X86MemDepEvaluator — evaluate memory dependence precision
// ============================================================================

/// Evaluates the precision of memory dependence analysis against
/// a set of known dependencies (ground truth).
#[derive(Debug, Clone)]
pub struct X86MemDepEvaluator {
    /// Ground-truth dependencies: (ptr, size, from_inst) -> expected dep_inst.
    pub ground_truth: HashMap<(u64, u64, u64), Option<u64>>,
    /// Evaluation results.
    pub results: Vec<X86MemDepEvalRecord>,
    /// Summary statistics.
    pub summary: X86MemDepEvalSummary,
}

/// A single memdep evaluation record.
#[derive(Debug, Clone)]
pub struct X86MemDepEvalRecord {
    pub ptr: u64,
    pub size: u64,
    pub from_inst: u64,
    pub expected_dep: Option<u64>,
    pub actual_dep: Option<u64>,
    pub correct: bool,
}

/// MemDep evaluation summary.
#[derive(Debug, Clone, Default)]
pub struct X86MemDepEvalSummary {
    pub total_queries: u64,
    pub exact_matches: u64,
    pub conservative_matches: u64,
    pub incorrect: u64,
    pub accuracy: f64,
}

impl X86MemDepEvaluator {
    /// Create a new memdep evaluator.
    pub fn new() -> Self {
        X86MemDepEvaluator {
            ground_truth: HashMap::new(),
            results: Vec::new(),
            summary: X86MemDepEvalSummary::default(),
        }
    }

    /// Add a ground-truth dependency.
    pub fn add_ground_truth(&mut self, ptr: u64, size: u64, from_inst: u64, dep_inst: Option<u64>) {
        self.ground_truth.insert((ptr, size, from_inst), dep_inst);
    }

    /// Evaluate a single memdep result.
    pub fn evaluate(&mut self, ptr: u64, size: u64, from_inst: u64, result: &X86MemDepResult) {
        let expected = self
            .ground_truth
            .get(&(ptr, size, from_inst))
            .copied()
            .unwrap_or(None);

        // A result is correct if:
        // - Expected Some(x) and actual is Some(x) => exact match
        // - Expected Some(x) and actual is Some(y) where y dominates x => conservative
        // - Expected None and actual is None => exact match
        let correct = match (expected, result.dep_inst) {
            (Some(exp), Some(act)) => exp == act || act < exp, // conservative: earlier dep
            (None, None) => true,
            (None, Some(_)) => true, // conservative: found a dep when none expected
            (Some(_), None) => false, // missed a dep
        };

        self.results.push(X86MemDepEvalRecord {
            ptr,
            size,
            from_inst,
            expected_dep: expected,
            actual_dep: result.dep_inst,
            correct,
        });
    }

    /// Compute summary statistics.
    pub fn compute_summary(&mut self) {
        let mut summary = X86MemDepEvalSummary::default();
        summary.total_queries = self.results.len() as u64;

        for record in &self.results {
            if record.correct {
                if record.expected_dep == record.actual_dep {
                    summary.exact_matches += 1;
                } else {
                    summary.conservative_matches += 1;
                }
            } else {
                summary.incorrect += 1;
            }
        }

        summary.accuracy = if summary.total_queries > 0 {
            (summary.exact_matches + summary.conservative_matches) as f64
                / summary.total_queries as f64
        } else {
            1.0
        };

        self.summary = summary;
    }

    /// Get a report string.
    pub fn report(&self) -> String {
        let s = &self.summary;
        format!(
            "MemDep Evaluation Report\n\
             =======================\n\
             Total queries:       {}\n\
             Exact matches:       {}\n\
             Conservative matches:{}\n\
             Incorrect:           {}\n\
             Accuracy:            {:.2}%\n",
            s.total_queries,
            s.exact_matches,
            s.conservative_matches,
            s.incorrect,
            s.accuracy * 100.0,
        )
    }
}

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

// ============================================================================
// X86AliasAnalysisDriver — convenient driver for common AA tasks
// ============================================================================

/// A convenience driver that simplifies common alias analysis workflows.
#[derive(Debug, Clone)]
pub struct X86AliasAnalysisDriver {
    /// The underlying alias analysis.
    pub aa: X86AliasAnalysis,
    /// Printer for debugging output.
    pub printer: X86AliasSetPrinter,
    /// Evaluator for precision measurement.
    pub evaluator: X86AliasEvaluator,
}

impl X86AliasAnalysisDriver {
    /// Create a new driver with default settings.
    pub fn new() -> Self {
        X86AliasAnalysisDriver {
            aa: X86AliasAnalysis::new(),
            printer: X86AliasSetPrinter::new(),
            evaluator: X86AliasEvaluator::new(),
        }
    }

    /// Initialize the analysis.
    pub fn init(&mut self) {
        self.aa.initialize();
    }

    /// Register and query: a convenience method that registers two allocas
    /// and then queries their alias relationship.
    pub fn register_and_query_allocas(
        &mut self,
        ptr_a: u64,
        size_a: u64,
        ptr_b: u64,
        size_b: u64,
    ) -> X86AliasResult {
        self.aa.basic_aa.register_alloca(ptr_a, size_a);
        self.aa.basic_aa.register_alloca(ptr_b, size_b);

        let loc_a = MemoryLocation::new(ptr_a, size_a);
        let loc_b = MemoryLocation::new(ptr_b, size_b);

        let result = self.aa.alias(&loc_a, &loc_b);

        // Log evaluation
        if ptr_a != ptr_b {
            self.evaluator
                .add_ground_truth(ptr_a, size_a, ptr_b, size_b, AliasResult::NoAlias);
        } else {
            self.evaluator
                .add_ground_truth(ptr_a, size_a, ptr_b, size_b, AliasResult::MustAlias);
        }
        self.evaluator
            .evaluate(ptr_a, size_a, ptr_b, size_b, result.clone());

        result
    }

    /// Run a batch of alias queries and print a summary.
    pub fn run_batch_and_summarize(&mut self, queries: &[(u64, u64, u64, u64)]) -> String {
        let mut results = Vec::new();
        for &(ptr_a, size_a, ptr_b, size_b) in queries {
            let loc_a = MemoryLocation::new(ptr_a, size_a);
            let loc_b = MemoryLocation::new(ptr_b, size_b);
            results.push(self.aa.alias(&loc_a, &loc_b));
        }

        let mut output = String::new();
        output.push_str("Batch Query Results:\n");
        output.push_str("====================\n");

        let noalias_count = results.iter().filter(|r| r.result.is_no_alias()).count();
        let mustalias_count = results.iter().filter(|r| r.result.is_must_alias()).count();
        let total = results.len();

        output.push_str(&format!("Total queries:  {}\n", total));
        output.push_str(&format!("NoAlias:        {}\n", noalias_count));
        output.push_str(&format!("MustAlias:      {}\n", mustalias_count));
        output.push_str(&format!(
            "Other:          {}\n",
            total - noalias_count - mustalias_count
        ));

        output
    }

    /// Get a full report including analysis stats and evaluation results.
    pub fn full_report(&mut self) -> String {
        self.evaluator.compute_summary();

        let mut report = String::new();
        report.push_str("========================================\n");
        report.push_str("  X86 ALIAS ANALYSIS FULL REPORT\n");
        report.push_str("========================================\n\n");

        report.push_str(&self.aa.print_stats());
        report.push('\n');
        report.push_str(&self.evaluator.report());
        report.push('\n');
        report.push_str(&X86AliasSetPrinter::print_stats_table(&self.aa));

        report
    }
}

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

// ============================================================================
// Final extended tests
// ============================================================================

#[cfg(test)]
mod final_tests {
    use super::*;

    #[test]
    fn test_mem_dep_evaluator_new() {
        let eval = X86MemDepEvaluator::new();
        assert!(eval.ground_truth.is_empty());
    }

    #[test]
    fn test_mem_dep_evaluator_exact_match() {
        let mut eval = X86MemDepEvaluator::new();
        eval.add_ground_truth(100, 8, 10, Some(5));

        let result = X86MemDepResult {
            dep_inst: Some(5),
            dep_kind: X86MemDepKind::Def,
            access_id: Some(1),
        };
        eval.evaluate(100, 8, 10, &result);
        assert!(eval.results[0].correct);
    }

    #[test]
    fn test_mem_dep_evaluator_missed_dep() {
        let mut eval = X86MemDepEvaluator::new();
        eval.add_ground_truth(100, 8, 10, Some(5));

        let result = X86MemDepResult {
            dep_inst: None,
            dep_kind: X86MemDepKind::NonLocal,
            access_id: None,
        };
        eval.evaluate(100, 8, 10, &result);
        assert!(!eval.results[0].correct);
    }

    #[test]
    fn test_mem_dep_evaluator_conservative() {
        let mut eval = X86MemDepEvaluator::new();
        eval.add_ground_truth(100, 8, 10, Some(5));

        let result = X86MemDepResult {
            dep_inst: Some(3), // earlier dep => conservative
            dep_kind: X86MemDepKind::Def,
            access_id: Some(1),
        };
        eval.evaluate(100, 8, 10, &result);
        assert!(eval.results[0].correct);
    }

    #[test]
    fn test_mem_dep_evaluator_summary() {
        let mut eval = X86MemDepEvaluator::new();
        eval.add_ground_truth(100, 8, 10, Some(5));
        eval.add_ground_truth(200, 4, 20, None);

        eval.evaluate(
            100,
            8,
            10,
            &X86MemDepResult {
                dep_inst: Some(5),
                dep_kind: X86MemDepKind::Def,
                access_id: Some(1),
            },
        );
        eval.evaluate(
            200,
            4,
            20,
            &X86MemDepResult {
                dep_inst: None,
                dep_kind: X86MemDepKind::NonLocal,
                access_id: None,
            },
        );

        eval.compute_summary();
        assert_eq!(eval.summary.total_queries, 2);
        assert_eq!(eval.summary.exact_matches, 2);
        assert_eq!(eval.summary.incorrect, 0);
        assert_eq!(eval.summary.accuracy, 1.0);
    }

    #[test]
    fn test_mem_dep_evaluator_report() {
        let eval = X86MemDepEvaluator::new();
        let report = eval.report();
        assert!(report.contains("MemDep Evaluation Report"));
        assert!(report.contains("Accuracy"));
    }

    #[test]
    fn test_driver_new() {
        let driver = X86AliasAnalysisDriver::new();
        assert!(!driver.aa.initialized);
    }

    #[test]
    fn test_driver_init() {
        let mut driver = X86AliasAnalysisDriver::new();
        driver.init();
        assert!(driver.aa.initialized);
    }

    #[test]
    fn test_driver_register_and_query_allocas_different() {
        let mut driver = X86AliasAnalysisDriver::new();
        driver.init();

        let result = driver.register_and_query_allocas(100, 8, 200, 8);
        assert_eq!(result.result, AliasResult::NoAlias);
    }

    #[test]
    fn test_driver_register_and_query_allocas_same() {
        let mut driver = X86AliasAnalysisDriver::new();
        driver.init();

        let result = driver.register_and_query_allocas(100, 8, 100, 8);
        assert_eq!(result.result, AliasResult::MustAlias);
    }

    #[test]
    fn test_driver_run_batch_and_summarize() {
        let mut driver = X86AliasAnalysisDriver::new();
        driver.init();

        driver.aa.basic_aa.register_alloca(100, 8);
        driver.aa.basic_aa.register_alloca(200, 8);
        driver.aa.basic_aa.register_alloca(300, 8);

        let queries = vec![(100, 8, 200, 8), (100, 8, 300, 8), (200, 8, 300, 8)];
        let summary = driver.run_batch_and_summarize(&queries);

        assert!(summary.contains("Batch Query Results"));
        assert!(summary.contains("NoAlias:        3"));
    }

    #[test]
    fn test_driver_full_report() {
        let mut driver = X86AliasAnalysisDriver::new();
        driver.init();

        driver.aa.basic_aa.register_alloca(100, 8);
        driver.aa.basic_aa.register_alloca(200, 8);

        let _ = driver.register_and_query_allocas(100, 8, 200, 8);
        let _ = driver.register_and_query_allocas(100, 8, 100, 8);

        let report = driver.full_report();
        assert!(report.contains("X86 ALIAS ANALYSIS FULL REPORT"));
        assert!(report.contains("BasicAA"));
    }

    // -------------------------------------------------------------------
    // Additional helper function coverage tests
    // -------------------------------------------------------------------

    #[test]
    fn test_is_constant_tbaa_access() {
        let mut tbaa = X86TypeBasedAA::new();
        tbaa.add_type_node(TBAANode::new_constant(1, 0, "const_int"));
        let tag = TBAATag::new_constant(1, 0, 0);
        assert!(is_constant_tbaa_access(Some(&tag), &tbaa));
        assert!(!is_constant_tbaa_access(None, &tbaa));
    }

    #[test]
    fn test_alias_result_distance_partial() {
        let d = alias_result_distance(AliasResult::NoAlias, AliasResult::MayAlias);
        assert_eq!(d, 0.5);
        let d = alias_result_distance(AliasResult::MayAlias, AliasResult::MustAlias);
        assert_eq!(d, 0.5);
    }

    #[test]
    fn test_check_alias_consistency_partialalias() {
        assert!(check_alias_consistency(
            AliasResult::PartialAlias,
            AliasResult::MayAlias
        ));
        assert!(check_alias_consistency(
            AliasResult::PartialAlias,
            AliasResult::MustAlias
        ));
    }

    // -------------------------------------------------------------------
    // Comprehensive stress / regression test
    // -------------------------------------------------------------------

    #[test]
    fn test_comprehensive_workflow() {
        // Build a complete analysis pipeline with realistic data
        let mut pipeline = X86AliasAnalysisPipeline::new();
        pipeline.build();

        // Register allocas
        for i in 0..10 {
            pipeline.register_alloca(i * 10, 8);
        }

        // Register some globals
        pipeline.register_global(1000, 4, false);
        pipeline.register_global(2000, 4, true); // constant

        // Register GEPs
        pipeline.register_gep(500, 0, 0);
        pipeline.register_gep(510, 0, 8);

        // Register TBAA nodes
        pipeline.register_tbaa_node(TBAANode::new(1, 0, "root"));
        pipeline.register_tbaa_node(TBAANode::new(2, 1, "int"));
        pipeline.register_tbaa_node(TBAANode::new(3, 1, "float"));

        // Register scoped noalias
        pipeline.register_noalias_scope(1, 10, 20);

        // Register function behavior
        pipeline.register_function_behavior(100, FunctionModRefInfo::OnlyReadsMemory);

        // Build MemorySSA
        pipeline.build_memory_ssa(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);

        // Initialize
        pipeline.initialize();

        // Run queries
        let loc_a = MemoryLocation::new(0, 8);
        let loc_b = MemoryLocation::new(10, 8);
        let result = pipeline.query(&loc_a, &loc_b);
        assert_eq!(result.result, AliasResult::NoAlias);

        // Same pointer query
        let result2 = pipeline.query(&loc_a, &loc_a);
        assert_eq!(result2.result, AliasResult::MustAlias);

        // Print summary
        let summary = pipeline.print_pipeline_summary();
        assert!(summary.contains("X86 Alias Analysis Pipeline Summary"));
        assert!(summary.contains("Stages executed"));
    }

    #[test]
    fn test_comprehensive_with_driver() {
        let mut driver = X86AliasAnalysisDriver::new();
        driver.init();

        // Register several allocas
        for i in 0..5 {
            driver.aa.basic_aa.register_alloca(i * 100, 16);
        }

        // Query all pairs of distinct allocas
        for i in 0..5 {
            for j in (i + 1)..5 {
                let result = driver.register_and_query_allocas(i * 100, 16, j * 100, 16);
                assert_eq!(result.result, AliasResult::NoAlias);
            }
        }

        // Generate full report
        let report = driver.full_report();
        assert!(report.contains("FULL REPORT"));
        assert!(report.contains("Evaluation Report"));
    }

    #[test]
    fn test_aa_config_fast_builds_correctly() {
        let config = X86AAConfig::fast();
        let aa = config.build_analysis();
        // Basic checks
        assert!(aa.basic_aa.alloca_sizes.is_empty());
        // CFL should still be present but unused
        assert!(!aa.cfl_aa.solved);
    }

    #[test]
    fn test_aa_config_precise_features() {
        let config = X86AAConfig::precise();
        assert!(config.field_sensitive_cfl);
        assert!(config.enable_cfl_aa);
        assert!(config.enable_scev_aa);
    }

    #[test]
    fn test_aa_config_minimal_only_basic() {
        let config = X86AAConfig::minimal();
        assert!(config.enable_basic_aa);
        assert!(!config.enable_cfl_aa);
        assert!(!config.enable_tbaa);
        assert!(!config.enable_memory_ssa);
    }
}

// ============================================================================
// Module documentation — Usage guide and examples
// ============================================================================
//
// # X86 Alias Analysis Module
//
// This module provides a complete alias analysis framework for the X86/X86-64
// target backend. It implements all major LLVM alias analysis algorithms.
//
// ## Quick Start
//
// ```ignore
// use x86_alias_analysis::*;
//
// // Create and initialize the analysis
// let mut aa = X86AliasAnalysis::new();
//
// // Register known memory objects
// aa.basic_aa.register_alloca(0x1000, 8);
// aa.basic_aa.register_alloca(0x2000, 8);
// aa.basic_aa.register_global(0x3000, 4, true); // constant global
//
// // Run the analysis pipeline
// aa.initialize();
//
// // Query aliasing between two memory locations
// let loc_a = MemoryLocation::new(0x1000, 8);
// let loc_b = MemoryLocation::new(0x2000, 8);
// let result = aa.alias(&loc_a, &loc_b);
//
// match result.result {
//     AliasResult::NoAlias => println!("Proved non-aliasing"),
//     AliasResult::MustAlias => println!("Proved must-alias"),
//     AliasResult::MayAlias => println!("May alias (conservative)"),
//     AliasResult::PartialAlias => println!("Partially overlapping"),
// }
// ```
//
// ## Using the Pipeline Builder
//
// ```ignore
// let mut pipeline = X86AliasAnalysisPipeline::new();
// pipeline.build();
// pipeline.register_alloca(0x1000, 8);
// pipeline.register_alloca(0x2000, 8);
// pipeline.initialize();
//
// let loc_a = MemoryLocation::new(0x1000, 8);
// let loc_b = MemoryLocation::new(0x2000, 8);
// let result = pipeline.query(&loc_a, &loc_b);
// ```
//
// ## Using Configuration Presets
//
// ```ignore
// let config = X86AAConfig::fast();     // Speed-optimized
// let config = X86AAConfig::precise();  // Precision-optimized
// let config = X86AAConfig::minimal();  // Minimal (BasicAA only)
// let aa = config.build_analysis();
// ```
//
// ## MemorySSA Construction
//
// ```ignore
// let mut mssa = X86MemorySSA::new();
// mssa.set_entry_block(1);
//
// let ops = vec![
//     (1, 10, X86Opcode::Store, 0x1000, 8, false),
//     (1, 11, X86Opcode::Load,  0x1000, 8, true),
// ];
// mssa.build(&ops, &[1]);
// mssa.optimize_uses();
// ```
//
// ## Type-Based Alias Analysis
//
// ```ignore
// let mut tbaa = X86TypeBasedAA::new();
// tbaa.add_type_node(TBAANode::new(1, 0, "root"));
// tbaa.add_type_node(TBAANode::new(2, 1, "int"));
// tbaa.add_type_node(TBAANode::new(3, 1, "float"));
//
// let tag_int = TBAATag::new(2, 1, 0);
// let tag_float = TBAATag::new(3, 1, 0);
//
// // int and float under same root may alias, but with different access types
// // the TBAA tree can potentially disambiguate
// let result = tbaa.may_alias(Some(&tag_int), Some(&tag_float));
// ```

// ============================================================================
// Additional module-level tests for complete coverage
// ============================================================================

#[cfg(test)]
mod final_coverage_tests {
    use super::*;

    #[test]
    fn test_x86_opcode_display_all() {
        let ops = vec![
            X86Opcode::Store,
            X86Opcode::Load,
            X86Opcode::Alloca,
            X86Opcode::Call,
            X86Opcode::Add,
        ];
        for op in ops {
            assert!(!format!("{}", op).is_empty());
        }
    }

    #[test]
    fn test_memory_location_eq() {
        let loc1 = MemoryLocation::new(100, 8);
        let loc2 = MemoryLocation::new(100, 8);
        let loc3 = MemoryLocation::new(200, 8);
        assert_eq!(loc1, loc2);
        assert_ne!(loc1, loc3);
    }

    #[test]
    fn test_alias_result_meet_mustalias_noalias() {
        // MustAlias meet NoAlias = NoAlias wins (more precise)
        assert_eq!(
            AliasResult::meet(AliasResult::MustAlias, AliasResult::NoAlias),
            AliasResult::NoAlias
        );
    }

    #[test]
    fn test_basic_aa_stats_default_zero() {
        let basic = X86BasicAA::new();
        let stats = basic.get_stats();
        assert_eq!(stats.total_queries, 0);
        assert_eq!(stats.noalias_results, 0);
    }

    #[test]
    fn test_cfl_aa_empty_solve() {
        let mut cfl = X86CFLAA::new();
        cfl.solve();
        assert!(cfl.solved);
        assert_eq!(cfl.may_alias(1, 2), AliasResult::NoAlias);
    }

    #[test]
    fn test_memory_ssa_get_location_def() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);
        let loc = mssa.get_location(2); // def id should be 2
        assert!(loc.is_some());
        assert_eq!(loc.unwrap().ptr, 100);
    }

    #[test]
    fn test_memory_ssa_is_same_location() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(
            &[
                (1, 10, X86Opcode::Store, 100, 8, false),
                (1, 11, X86Opcode::Load, 100, 8, true),
            ],
            &[1],
        );
        let acc1 = mssa.get_memory_access(10).unwrap();
        let acc2 = mssa.get_memory_access(11).unwrap();
        assert!(mssa.is_same_memory_location(acc1, acc2));
    }

    #[test]
    fn test_mssa_updater_move_updates_block() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);
        let mut updater = X86MemorySSAUpdater::new(mssa);
        updater.move_instruction(10, 1, 3);
        assert!(updater.update_log.len() > 0);
        assert!(!updater.mssa.is_optimized);
    }

    #[test]
    fn test_mem_dep_invalidate_inst() {
        let mut mssa = X86MemorySSA::new();
        mssa.set_entry_block(1);
        mssa.build(&[(1, 10, X86Opcode::Store, 100, 8, false)], &[1]);
        let mut mem_dep = X86MemDep::new(mssa);
        let _ = mem_dep.get_dependency(100, 8, 10);
        let _ = mem_dep.get_dependency(200, 4, 20);
        assert_eq!(mem_dep.cache_size(), 2);
        mem_dep.invalidate_inst(10);
        assert_eq!(mem_dep.cache_size(), 1);
    }

    #[test]
    fn test_scoped_noalias_missing_one_side() {
        let aa = X86ScopedNoAliasAA::new();
        let loc_a = MemoryLocation::new(100, 8)
            .with_scoped_noalias("1".to_string(), vec!["10".to_string()]);
        let loc_b = MemoryLocation::new(200, 8); // no scoped noalias
        assert_eq!(aa.may_alias(&loc_a, &loc_b), AliasResult::MayAlias);
    }

    #[test]
    fn test_scev_expr_add_display() {
        let a = X86SCEVExpr::constant(3);
        let b = X86SCEVExpr::constant(4);
        let sum = X86SCEVExpr::Add(Box::new(a), Box::new(b));
        assert_eq!(format!("{}", sum), "(3 + 4)");
    }

    #[test]
    fn test_scev_expr_mul_display() {
        let a = X86SCEVExpr::constant(3);
        let b = X86SCEVExpr::constant(4);
        let prod = X86SCEVExpr::Mul(Box::new(a), Box::new(b));
        assert_eq!(format!("{}", prod), "(3 * 4)");
    }

    #[test]
    fn test_tbaa_node_children_tracking() {
        let mut tbaa = X86TypeBasedAA::new();
        tbaa.add_type_node(TBAANode::new(1, 0, "root"));
        tbaa.add_type_node(TBAANode::new(2, 1, "child1"));
        tbaa.add_type_node(TBAANode::new(3, 1, "child2"));

        let root = tbaa.type_nodes.get(&1).unwrap();
        assert_eq!(root.children.len(), 2);
        assert!(root.children.contains(&2));
        assert!(root.children.contains(&3));
    }

    #[test]
    fn test_globals_mod_ref_argmemonly() {
        let mut gmr = X86GlobalsModRef::new();
        gmr.register_function(100, FunctionModRefInfo::OnlyAccessesArgMemory);
        let loc = MemoryLocation::new(500, 8);
        // argmemonly doesn't guarantee no access to arbitrary memory,
        // it only restricts to argument memory
        let result = gmr.get_mod_ref_for_call(100, &loc);
        // Conservative: ModRef for non-argument memory
        assert_eq!(result, ModRefInfo::ModRef);
    }

    #[test]
    fn test_alias_set_volatile() {
        let mut set = AliasSet::new(1);
        assert!(!set.is_volatile);
        set.is_volatile = true;
        assert!(set.is_volatile);

        let mut set2 = AliasSet::new(2);
        set2.merge(&set);
        assert!(set2.is_volatile);
    }
}