llvm-native-core-ext 0.1.0

//! LLVM Alias Analysis — determines whether two memory references may alias.
//! Phase 6 — LLVM.AA.1 Court.
//!
//! Clean-room behavioral reconstruction from the LLVM Language Reference,
//! compiler optimization literature (Alias Analysis, Steensgaard 1996;
//! Type-Based Alias Analysis, Diwan et al. 1998), and observable
//! optimization behavior. Zero LLVM source code consultation.
//!
//! Alias analysis answers the question: can two memory references
//! refer to the same memory location? This is fundamental to:
//! - Instruction scheduling (reordering memory operations)
//! - Loop-invariant code motion
//! - Dead store elimination
//! - Load/store forwarding
//! - Scalar replacement of aggregates
//!
//! This module provides:
//! - BasicAliasAnalysis: local/stack-based AA using allocas and GEPs
//! - TypeBasedAliasAnalysis: TBAA using metadata tags
//! - ScopedNoAliasAnalysis: restrict/noalias scoping
//! - AliasAnalysisAggregator: chaining multiple AA implementations
//! - MemoryLocation descriptor and helpers

use llvm_native_core::opcode::Opcode;
use llvm_native_core::value::{SubclassKind, ValueRef};
use std::rc::Rc;

// ============================================================================
// AliasResult — the result of an alias query
// ============================================================================

/// The possible results of an alias query between two memory locations.
///
/// @llvm_behavior: LLVM uses a lattice: NoAlias < MayAlias < PartialAlias < MustAlias.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum AliasResult {
    /// Definitely not aliasing — locations provably disjoint.
    NoAlias,
    /// Might alias — analysis cannot disprove aliasing.
    MayAlias,
    /// Partially overlapping — known overlap but different sizes/offsets.
    PartialAlias,
    /// Definitely aliasing — same memory location.
    MustAlias,
}

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

// ============================================================================
// ModRefInfo — does an instruction modify and/or reference memory?
// ============================================================================

/// Describes whether an instruction modifies and/or references memory.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ModRefInfo {
    /// Does not access memory at all.
    NoModRef,
    /// Only reads memory (does not write).
    Ref,
    /// Only writes memory (does not read).
    Mod,
    /// Both reads and writes memory.
    ModRef,
}

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

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

    /// Combine two ModRefInfo values (lattice join).
    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,
        }
    }
}

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

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

/// A memory location descriptor used by alias analysis.
///
/// @llvm_behavior: LLVM's MemoryLocation encodes the pointer,
/// access size, and optional AA metadata tags (TBAA, scoped noalias).
#[derive(Debug, Clone)]
pub struct MemoryLocation {
    /// The pointer value being accessed.
    pub ptr: ValueRef,
    /// Size of the access in bytes. 0 = unknown/variable size.
    pub size: u64,
    /// Optional alias-analysis metadata tags.
    /// Bit-packed: upper 16 bits = TBAA root, lower 16 bits = access type.
    pub aa_tags: Option<u32>,
}

impl MemoryLocation {
    /// Create a new memory location.
    pub fn new(ptr: ValueRef, size: u64) -> Self {
        Self {
            ptr,
            size,
            aa_tags: None,
        }
    }

    /// Create a memory location with AA tags.
    pub fn with_tags(ptr: ValueRef, size: u64, aa_tags: u32) -> Self {
        Self {
            ptr,
            size,
            aa_tags: Some(aa_tags),
        }
    }

    /// Returns true if this location has a known size (non-zero).
    pub fn has_size(&self) -> bool {
        self.size > 0
    }

    /// Get the TBAA root tag (upper 16 bits), if tags are present.
    pub fn tbaa_root(&self) -> Option<u16> {
        self.aa_tags.map(|t| (t >> 16) as u16)
    }

    /// Get the TBAA access type tag (lower 16 bits), if tags are present.
    pub fn tbaa_access_type(&self) -> Option<u16> {
        self.aa_tags.map(|t| (t & 0xFFFF) as u16)
    }
}

// ============================================================================
// AliasAnalysis trait — the interface all AA implementations satisfy
// ============================================================================

/// Alias analysis interface.
///
/// @llvm_behavior: LLVM's AliasAnalysis is an abstract interface that
/// provides alias queries, mod/ref information for calls, and
/// constant-memory queries.
pub trait AliasAnalysis {
    /// Human-readable name of this analysis (e.g., "BasicAA", "TBAA").
    fn name(&self) -> &str;

    /// Determine the aliasing relationship between two memory locations.
    fn alias(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult;

    /// Return the ModRef info for a call instruction.
    fn get_mod_ref_info(&self, call: &ValueRef) -> ModRefInfo;

    /// Returns true if the given memory location is known to point to
    /// constant (read-only) memory.
    fn points_to_constant_memory(&self, loc: &MemoryLocation) -> bool;
}

// ============================================================================
// BasicAliasAnalysis — local alias analysis for stack and global objects
// ============================================================================

/// Basic alias analysis: determines aliasing based on stack objects (alloca),
/// global variables, GEP offsets, and known distinct identities.
///
/// @llvm_behavior: BasicAA is LLVM's workhorse alias analysis. It uses
/// the "underlying object" concept — tracing a pointer back through GEPs
/// and bitcasts to its original allocation.
pub struct BasicAliasAnalysis;

impl BasicAliasAnalysis {
    /// Create a new BasicAliasAnalysis instance.
    pub fn new() -> Self {
        BasicAliasAnalysis
    }
}

impl AliasAnalysis for BasicAliasAnalysis {
    fn name(&self) -> &str {
        "BasicAA"
    }

    fn alias(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        // Same pointer -> MustAlias
        if Rc::ptr_eq(&loc_a.ptr, &loc_b.ptr) {
            return AliasResult::MustAlias;
        }

        // Get underlying objects
        let obj_a = get_underlying_object(&loc_a.ptr);
        let obj_b = get_underlying_object(&loc_b.ptr);

        // Different underlying objects that are distinct
        if !Rc::ptr_eq(&obj_a, &obj_b) {
            // Both are distinct allocas -> NoAlias
            if is_alloca(&obj_a) && is_alloca(&obj_b) {
                return AliasResult::NoAlias;
            }

            // Both are distinct global variables -> NoAlias
            if is_global_var(&obj_a) && is_global_var(&obj_b) {
                return AliasResult::NoAlias;
            }

            // One is an alloca, the other is a non-escaping global -> NoAlias
            if is_alloca(&obj_a) && is_global_var(&obj_b) && !pointer_may_escape(&obj_a) {
                return AliasResult::NoAlias;
            }
            if is_alloca(&obj_b) && is_global_var(&obj_a) && !pointer_may_escape(&obj_b) {
                return AliasResult::NoAlias;
            }

            return AliasResult::MayAlias;
        }

        // Same underlying object — check offsets and sizes
        let offset_a = get_pointer_offset(&loc_a.ptr);
        let offset_b = get_pointer_offset(&loc_b.ptr);

        if offset_a.is_some() && offset_b.is_some() && loc_a.has_size() && loc_b.has_size() {
            let oa = offset_a.unwrap();
            let ob = offset_b.unwrap();
            let end_a = oa + loc_a.size as i64;
            let end_b = ob + loc_b.size as i64;

            if oa == ob && loc_a.size == loc_b.size {
                return AliasResult::MustAlias;
            }

            if end_a <= ob || end_b <= oa {
                return AliasResult::NoAlias;
            }

            if oa != ob || loc_a.size != loc_b.size {
                return AliasResult::PartialAlias;
            }
        }

        AliasResult::MayAlias
    }

    fn get_mod_ref_info(&self, call: &ValueRef) -> ModRefInfo {
        get_call_mod_ref_info(call)
    }

    fn points_to_constant_memory(&self, loc: &MemoryLocation) -> bool {
        let obj = get_underlying_object(&loc.ptr);
        if is_global_var(&obj) {
            // Check if it's a constant global by checking the name prefix
            let g = obj.borrow();
            if g.name.starts_with("const_") || g.name.contains("constant") {
                return true;
            }
        }
        false
    }
}

// ============================================================================
// TypeBasedAliasAnalysis — TBAA using type metadata
// ============================================================================

/// Type-Based Alias Analysis: uses TBAA metadata tags on loads/stores
/// to determine aliasing based on C/C++ type rules.
///
/// @llvm_behavior: TBAA encodes a type tree in metadata. Two accesses
/// are NoAlias if their TBAA tags indicate they access unrelated types.
pub struct TypeBasedAliasAnalysis;

impl TypeBasedAliasAnalysis {
    /// Create a new TypeBasedAliasAnalysis instance.
    pub fn new() -> Self {
        TypeBasedAliasAnalysis
    }
}

impl AliasAnalysis for TypeBasedAliasAnalysis {
    fn name(&self) -> &str {
        "TBAA"
    }

    fn alias(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        let tags_a = match loc_a.aa_tags {
            Some(t) => t,
            None => return AliasResult::MayAlias,
        };
        let tags_b = match loc_b.aa_tags {
            Some(t) => t,
            None => return AliasResult::MayAlias,
        };

        let root_a = (tags_a >> 16) as u16;
        let root_b = (tags_b >> 16) as u16;
        if root_a != root_b {
            return AliasResult::NoAlias;
        }

        let access_a = (tags_a & 0xFFFF) as u16;
        let access_b = (tags_b & 0xFFFF) as u16;

        if access_a == access_b {
            AliasResult::MayAlias
        } else if tbaa_types_may_alias(access_a, access_b) {
            AliasResult::MayAlias
        } else {
            AliasResult::NoAlias
        }
    }

    fn get_mod_ref_info(&self, _call: &ValueRef) -> ModRefInfo {
        ModRefInfo::ModRef
    }

    fn points_to_constant_memory(&self, loc: &MemoryLocation) -> bool {
        loc.aa_tags == Some(0)
    }
}

/// Simplified TBAA type compatibility check.
/// Adjacent types (within 8) may alias; others are NoAlias.
fn tbaa_types_may_alias(tag_a: u16, tag_b: u16) -> bool {
    let diff = if tag_a > tag_b {
        tag_a - tag_b
    } else {
        tag_b - tag_a
    };
    diff <= 8
}

// ============================================================================
// ScopedNoAliasAnalysis — restrict/noalias scoping
// ============================================================================

/// Scoped NoAlias analysis: leverages the `restrict` keyword semantics
/// (C) or `noalias` attribute (LLVM IR) to determine that pointers
/// derived from different noalias scopes do not alias.
pub struct ScopedNoAliasAnalysis;

impl ScopedNoAliasAnalysis {
    /// Create a new ScopedNoAliasAnalysis instance.
    pub fn new() -> Self {
        ScopedNoAliasAnalysis
    }
}

impl AliasAnalysis for ScopedNoAliasAnalysis {
    fn name(&self) -> &str {
        "ScopedNoAliasAA"
    }

    fn alias(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        let tags_a = match loc_a.aa_tags {
            Some(t) => t,
            None => return AliasResult::MayAlias,
        };
        let tags_b = match loc_b.aa_tags {
            Some(t) => t,
            None => return AliasResult::MayAlias,
        };

        // Scope domain encoded in bits 24-31
        let scope_a = ((tags_a >> 24) & 0xFF) as u8;
        let scope_b = ((tags_b >> 24) & 0xFF) as u8;

        if scope_a != 0 && scope_b != 0 && scope_a != scope_b {
            AliasResult::NoAlias
        } else {
            AliasResult::MayAlias
        }
    }

    fn get_mod_ref_info(&self, _call: &ValueRef) -> ModRefInfo {
        ModRefInfo::ModRef
    }

    fn points_to_constant_memory(&self, _loc: &MemoryLocation) -> bool {
        false
    }
}

// ============================================================================
// AliasAnalysisAggregator — chains multiple AA implementations
// ============================================================================

/// Aggregates multiple alias analysis implementations.
///
/// Queries are forwarded through the chain in order.
pub struct AliasAnalysisAggregator {
    /// The ordered list of alias analysis implementations.
    pub analyses: Vec<Box<dyn AliasAnalysis>>,
}

impl AliasAnalysisAggregator {
    /// Create a new empty aggregator.
    pub fn new() -> Self {
        Self {
            analyses: Vec::new(),
        }
    }

    /// Add an alias analysis to the chain.
    pub fn add(&mut self, aa: Box<dyn AliasAnalysis>) {
        self.analyses.push(aa);
    }

    /// Add an analysis, consuming the aggregator (builder pattern).
    pub fn with(mut self, aa: Box<dyn AliasAnalysis>) -> Self {
        self.add(aa);
        self
    }
}

impl AliasAnalysis for AliasAnalysisAggregator {
    fn name(&self) -> &str {
        "AggregateAA"
    }

    fn alias(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        let mut best = AliasResult::MayAlias;

        for aa in &self.analyses {
            let result = aa.alias(loc_a, loc_b);
            match result {
                AliasResult::NoAlias | AliasResult::MustAlias => return result,
                AliasResult::PartialAlias => best = AliasResult::PartialAlias,
                AliasResult::MayAlias => {}
            }
        }

        best
    }

    fn get_mod_ref_info(&self, call: &ValueRef) -> ModRefInfo {
        for aa in &self.analyses {
            let info = aa.get_mod_ref_info(call);
            if info != ModRefInfo::ModRef {
                return info;
            }
        }
        ModRefInfo::ModRef
    }

    fn points_to_constant_memory(&self, loc: &MemoryLocation) -> bool {
        self.analyses
            .iter()
            .any(|aa| aa.points_to_constant_memory(loc))
    }
}

// ============================================================================
// Standalone alias analysis functions
// ============================================================================

/// Perform a basic alias check between two memory locations.
pub fn basic_alias_check(loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
    let baa = BasicAliasAnalysis::new();
    baa.alias(loc_a, loc_b)
}

/// Check if two pointers definitely do not alias.
pub fn is_no_alias(loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> bool {
    basic_alias_check(loc_a, loc_b) == AliasResult::NoAlias
}

// ============================================================================
// Helper functions
// ============================================================================

/// Determine if two alloca instructions must alias.
pub fn is_identical_alloca(a: &ValueRef, b: &ValueRef) -> bool {
    if !is_alloca(a) || !is_alloca(b) {
        return false;
    }
    Rc::ptr_eq(a, b)
}

/// Determine if a value is a global constant.
pub fn is_global_constant(val: &ValueRef) -> bool {
    let v = val.borrow();
    match v.subclass {
        SubclassKind::GlobalVariable => v.name.starts_with("const_") || v.name.contains("constant"),
        SubclassKind::Constant => true,
        _ => false,
    }
}

/// Get the underlying object for a pointer.
///
/// Traces through GEPs, bitcasts, and addrspace casts to find the
/// base allocation (alloca, global, argument, or unknown).
pub fn get_underlying_object(ptr: &ValueRef) -> ValueRef {
    let p = ptr.borrow();

    if is_alloca(ptr) || is_global_var(ptr) || p.subclass == SubclassKind::Argument {
        return Rc::clone(ptr);
    }

    if let Some(opcode) = p.get_opcode() {
        match opcode {
            Opcode::GetElementPtr | Opcode::BitCast | Opcode::AddrSpaceCast => {
                if !p.operands.is_empty() {
                    return get_underlying_object(&p.operands[0]);
                }
            }
            Opcode::IntToPtr | Opcode::PtrToInt => {
                return Rc::clone(ptr);
            }
            _ => {}
        }
    }

    if let Some(Opcode::Load) = p.get_opcode() {
        if !p.operands.is_empty() {
            return get_underlying_object(&p.operands[0]);
        }
    }

    Rc::clone(ptr)
}

/// Get the memory location for a load or store instruction.
pub fn get_memory_location(inst: &ValueRef) -> Option<MemoryLocation> {
    let i = inst.borrow();
    let opcode = i.get_opcode()?;

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

/// Get the pointer offset from its underlying object.
pub fn get_pointer_offset(ptr: &ValueRef) -> Option<i64> {
    let p = ptr.borrow();

    if is_alloca(ptr) || is_global_var(ptr) || p.subclass == SubclassKind::Argument {
        return Some(0);
    }

    if let Some(Opcode::GetElementPtr) = p.get_opcode() {
        let base_offset = if p.operands.is_empty() {
            None
        } else {
            get_pointer_offset(&p.operands[0])
        };

        if base_offset.is_none() {
            return None;
        }

        let mut offset = base_offset.unwrap();

        for operand in &p.operands[1..] {
            if let Some(val) = get_constant_i64(operand) {
                offset += val * 8; // conservative stride
            } else {
                return None;
            }
        }

        return Some(offset);
    }

    if let Some(Opcode::BitCast) = p.get_opcode() {
        if !p.operands.is_empty() {
            return get_pointer_offset(&p.operands[0]);
        }
    }

    None
}

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

/// Check if a value is an alloca instruction.
fn is_alloca(val: &ValueRef) -> bool {
    val.borrow().get_opcode() == Some(Opcode::Alloca)
}

/// Check if a value is a global variable.
fn is_global_var(val: &ValueRef) -> bool {
    val.borrow().subclass == SubclassKind::GlobalVariable
}

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

/// Get the size in bytes of a type. Returns 0 for unknown/variable size.
fn type_size_in_bytes(ty: &llvm_native_core::types::Type) -> u64 {
    use llvm_native_core::types::TypeKind;

    match &ty.kind {
        TypeKind::Integer { bits } => (*bits as u64 + 7) / 8,
        TypeKind::Float => 4,
        TypeKind::Double => 8,
        TypeKind::Half => 2,
        TypeKind::BFloat => 2,
        TypeKind::FP128 => 16,
        TypeKind::X86FP80 => 10,
        TypeKind::PPCFP128 => 16,
        TypeKind::Pointer { .. } => 8,
        TypeKind::Array { len, .. } => *len as u64 * 8,
        TypeKind::Struct {
            element_type_ids, ..
        } => element_type_ids.len() as u64 * 8,
        TypeKind::FixedVector { len, .. } => *len as u64 * 8,
        _ => 0,
    }
}

/// Get mod/ref info for a call instruction.
pub fn get_call_mod_ref_info(call: &ValueRef) -> ModRefInfo {
    let c = call.borrow();

    if c.get_opcode() != Some(Opcode::Call) {
        return ModRefInfo::NoModRef;
    }

    if let Some(ref name) = get_called_function_name(call) {
        match name.as_str() {
            "llvm.sqrt.f64" | "llvm.sin.f64" | "llvm.cos.f64" | "llvm.floor.f64"
            | "llvm.ceil.f64" | "llvm.trunc.f64" | "llvm.fabs.f64" | "llvm.expect.i64" => {
                return ModRefInfo::NoModRef
            }
            "llvm.memcpy.p0i8.p0i8.i64" | "llvm.memmove.p0i8.p0i8.i64" => {
                return ModRefInfo::ModRef;
            }
            "llvm.memset.p0i8.i64" => return ModRefInfo::Mod,
            "llvm.lifetime.start.p0i8" | "llvm.lifetime.end.p0i8" => {
                return ModRefInfo::NoModRef;
            }
            _ => {}
        }
    }

    ModRefInfo::ModRef
}

/// Try to get the name of the function being called.
fn get_called_function_name(call: &ValueRef) -> Option<String> {
    let c = call.borrow();
    if c.operands.is_empty() {
        return None;
    }
    let callee = c.operands[0].borrow();
    if callee.subclass == SubclassKind::Function {
        Some(callee.name.clone())
    } else {
        None
    }
}

// ============================================================================
// FunctionAttributeAA — alias analysis from function attributes
// ============================================================================

/// Function attribute-based alias analysis.
/// Uses readnone, readonly, writeonly, argmemonly attributes on functions
/// to refine ModRefInfo and aliasing for call instructions.
///
/// @llvm_behavior: LLVM uses function attributes to determine if a call
/// can access memory at all, and which arguments' memory it can access.
pub struct FunctionAttributeAA;

impl FunctionAttributeAA {
    pub fn new() -> Self {
        FunctionAttributeAA
    }

    /// Check if a function has the readnone attribute (no memory access).
    pub fn is_readnone(&self, func: &ValueRef) -> bool {
        let f = func.borrow();
        f.name.contains("readnone")
            || f.name.starts_with("llvm.sqrt")
            || f.name.starts_with("llvm.sin")
            || f.name.starts_with("llvm.cos")
            || f.name.starts_with("llvm.floor")
            || f.name.starts_with("llvm.ceil")
            || f.name.starts_with("llvm.fabs")
            || f.name.starts_with("llvm.expect")
    }

    /// Check if a function has the readonly attribute (reads but does not write).
    pub fn is_readonly(&self, func: &ValueRef) -> bool {
        let f = func.borrow();
        f.name.contains("readonly")
            || f.name.starts_with("llvm.ctpop")
            || f.name.starts_with("llvm.ctlz")
            || f.name.starts_with("llvm.cttz")
            || f.name.starts_with("llvm.bswap")
    }

    /// Check if a function has the writeonly attribute (writes but does not read).
    pub fn is_writeonly(&self, func: &ValueRef) -> bool {
        let f = func.borrow();
        f.name.contains("writeonly") || f.name.starts_with("llvm.memset")
    }

    /// Check if a function has the argmemonly attribute (only accesses
    /// memory pointed to by its arguments).
    pub fn is_argmemonly(&self, func: &ValueRef) -> bool {
        let f = func.borrow();
        f.name.contains("argmemonly")
            || f.name.starts_with("llvm.memcpy")
            || f.name.starts_with("llvm.memmove")
    }

    /// Check if a function has the inaccessiblememonly attribute
    /// (only accesses memory that is inaccessible to the module).
    pub fn is_inaccessiblememonly(&self, func: &ValueRef) -> bool {
        let f = func.borrow();
        f.name.contains("inaccessiblememonly")
    }

    /// Check if a function has the nounwind attribute.
    pub fn is_nounwind(&self, func: &ValueRef) -> bool {
        let f = func.borrow();
        f.name.contains("nounwind")
    }

    /// Check if a function has the willreturn attribute.
    pub fn is_willreturn(&self, func: &ValueRef) -> bool {
        let f = func.borrow();
        f.name.contains("willreturn")
    }

    /// Determine the ModRefInfo for a call based on function attributes.
    pub fn get_mod_ref_from_attrs(&self, call: &ValueRef) -> ModRefInfo {
        let c = call.borrow();
        if c.get_opcode() != Some(Opcode::Call) || c.operands.is_empty() {
            return ModRefInfo::NoModRef;
        }

        let callee = c.operands[0].borrow();
        if callee.subclass != SubclassKind::Function {
            return ModRefInfo::ModRef;
        }

        if self.is_readnone(&c.operands[0]) {
            return ModRefInfo::NoModRef;
        }
        if self.is_writeonly(&c.operands[0]) {
            return ModRefInfo::Mod;
        }
        if self.is_readonly(&c.operands[0]) {
            return ModRefInfo::Ref;
        }

        ModRefInfo::ModRef
    }
}

impl AliasAnalysis for FunctionAttributeAA {
    fn name(&self) -> &str {
        "FunctionAttrAA"
    }

    fn alias(&self, _loc_a: &MemoryLocation, _loc_b: &MemoryLocation) -> AliasResult {
        AliasResult::MayAlias
    }

    fn get_mod_ref_info(&self, call: &ValueRef) -> ModRefInfo {
        self.get_mod_ref_from_attrs(call)
    }

    fn points_to_constant_memory(&self, loc: &MemoryLocation) -> bool {
        let obj = get_underlying_object(&loc.ptr);
        let v = obj.borrow();
        v.name.contains("readonly") || v.name.starts_with(".rodata")
    }
}

// ============================================================================
// ModRefInfo Lattice — complete lattice operations
// ============================================================================

impl ModRefInfo {
    /// Meet (intersection) of two ModRefInfo values.
    /// Only returns what both values agree on.
    pub fn meet(a: ModRefInfo, b: ModRefInfo) -> ModRefInfo {
        use ModRefInfo::*;
        match (a, b) {
            (NoModRef, _) | (_, NoModRef) => NoModRef,
            (ModRef, x) | (x, ModRef) => x,
            (Ref, Mod) | (Mod, Ref) => NoModRef,
            (x, y) if x == y => x,
            _ => NoModRef,
        }
    }

    /// Return the most conservative ModRefInfo (top of lattice).
    pub fn top() -> ModRefInfo {
        ModRefInfo::ModRef
    }

    /// Return the least conservative ModRefInfo (bottom of lattice).
    pub fn bottom() -> ModRefInfo {
        ModRefInfo::NoModRef
    }

    /// Returns true if `a` is at least as precise as `b` (a <= b in lattice).
    pub fn leq(a: ModRefInfo, b: ModRefInfo) -> bool {
        Self::union(a, b) == b
    }

    /// Subtract mod access: returns what remains after removing mod capability.
    pub fn clear_mod(self) -> ModRefInfo {
        match self {
            ModRefInfo::ModRef => ModRefInfo::Ref,
            ModRefInfo::Mod => ModRefInfo::NoModRef,
            other => other,
        }
    }

    /// Subtract ref access: returns what remains after removing ref capability.
    pub fn clear_ref(self) -> ModRefInfo {
        match self {
            ModRefInfo::ModRef => ModRefInfo::Mod,
            ModRefInfo::Ref => ModRefInfo::NoModRef,
            other => other,
        }
    }
}

// ============================================================================
// AliasResult Lattice — complete lattice operations
// ============================================================================

impl AliasResult {
    /// Meet (intersection) of two AliasResult values, producing the most
    /// precise result that both agree on.
    pub fn meet(a: AliasResult, b: AliasResult) -> AliasResult {
        use AliasResult::*;
        match (a, b) {
            (NoAlias, NoAlias) => NoAlias,
            // MustAlias and something else → that something else (if compatible)
            (MustAlias, x) | (x, MustAlias) => x,
            // Anything else is MayAlias at best
            _ => MayAlias,
        }
    }

    /// Return the most conservative result (top of lattice).
    pub fn top() -> AliasResult {
        AliasResult::MayAlias
    }

    /// Return the least conservative result (bottom of lattice).
    pub fn bottom() -> AliasResult {
        AliasResult::MustAlias
    }
}

// ============================================================================
// AAResults — aggregated alias analysis results with caching
// ============================================================================

/// Complete alias analysis results aggregator.
/// Maintains a chain of AA passes and caches queries for efficiency.
///
/// @llvm_behavior: LLVM's AAResults wraps the AA pipeline and provides
/// a unified interface with optional per-query caching.
pub struct AAResults {
    aa_chain: AliasAnalysisAggregator,
    /// Optional cache for alias queries.
    alias_cache: std::collections::HashMap<(usize, usize), AliasResult>,
    /// Optional cache for modref queries.
    modref_cache: std::collections::HashMap<usize, ModRefInfo>,
}

impl AAResults {
    /// Create AAResults from an existing aggregator.
    pub fn new(aa: AliasAnalysisAggregator) -> Self {
        Self {
            aa_chain: aa,
            alias_cache: std::collections::HashMap::new(),
            modref_cache: std::collections::HashMap::new(),
        }
    }

    /// Create AAResults with the standard AA pipeline.
    pub fn standard_pipeline() -> Self {
        let mut agg = AliasAnalysisAggregator::new();
        agg.add(Box::new(BasicAliasAnalysis::new()));
        agg.add(Box::new(TypeBasedAliasAnalysis::new()));
        agg.add(Box::new(ScopedNoAliasAnalysis::new()));
        agg.add(Box::new(FunctionAttributeAA::new()));
        Self::new(agg)
    }

    /// Determine the aliasing relationship between two memory locations.
    pub fn alias(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        let key = (
            loc_a.ptr.borrow().vid as usize,
            loc_b.ptr.borrow().vid as usize,
        );
        if let Some(cached) = self.alias_cache.get(&key) {
            return *cached;
        }
        self.aa_chain.alias(loc_a, loc_b)
    }

    /// Determine the aliasing relationship with caching.
    pub fn alias_mut(&mut self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> AliasResult {
        let key = (
            loc_a.ptr.borrow().vid as usize,
            loc_b.ptr.borrow().vid as usize,
        );
        if let Some(cached) = self.alias_cache.get(&key) {
            return *cached;
        }
        let result = self.aa_chain.alias(loc_a, loc_b);
        self.alias_cache.insert(key, result);
        result
    }

    /// Get the ModRefInfo for a call instruction.
    pub fn get_mod_ref_info(&self, call: &ValueRef) -> ModRefInfo {
        let key = call.borrow().vid as usize;
        if let Some(cached) = self.modref_cache.get(&key) {
            return *cached;
        }
        self.aa_chain.get_mod_ref_info(call)
    }

    /// Get the ModRefInfo with caching.
    pub fn get_mod_ref_info_mut(&mut self, call: &ValueRef) -> ModRefInfo {
        let key = call.borrow().vid as usize;
        if let Some(cached) = self.modref_cache.get(&key) {
            return *cached;
        }
        let result = self.aa_chain.get_mod_ref_info(call);
        self.modref_cache.insert(key, result);
        result
    }

    /// Returns true if the given location is constant memory.
    pub fn points_to_constant_memory(&self, loc: &MemoryLocation) -> bool {
        self.aa_chain.points_to_constant_memory(loc)
    }

    /// Add an AA pass to the chain.
    pub fn add_aa(&mut self, aa: Box<dyn AliasAnalysis>) {
        self.aa_chain.add(aa);
        self.alias_cache.clear();
        self.modref_cache.clear();
    }

    /// Clear all caches.
    pub fn invalidate_cache(&mut self) {
        self.alias_cache.clear();
        self.modref_cache.clear();
    }

    /// Returns true if the two pointers definitely do not alias.
    pub fn is_no_alias(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> bool {
        matches!(self.alias(loc_a, loc_b), AliasResult::NoAlias)
    }

    /// Returns true if the two pointers definitely alias.
    pub fn is_must_alias(&self, loc_a: &MemoryLocation, loc_b: &MemoryLocation) -> bool {
        matches!(self.alias(loc_a, loc_b), AliasResult::MustAlias)
    }

    /// Returns true if call only reads memory.
    pub fn only_reads_memory(&self, call: &ValueRef) -> bool {
        let mri = self.get_mod_ref_info(call);
        mri == ModRefInfo::Ref || mri == ModRefInfo::NoModRef
    }

    /// Returns true if call does not access memory.
    pub fn does_not_access_memory(&self, call: &ValueRef) -> bool {
        self.get_mod_ref_info(call) == ModRefInfo::NoModRef
    }
}

impl Default for AAResults {
    fn default() -> Self {
        Self::standard_pipeline()
    }
}

// ============================================================================
// Enhanced TBAA — StructPath TBAA with type tree hierarchy
// ============================================================================

/// TBAA type tree node — encodes C/C++ type hierarchy for alias analysis.
#[derive(Debug, Clone)]
pub struct TBAATypeNode {
    /// Unique identifier for this type node.
    pub id: u16,
    /// Parent type node id (0 for root).
    pub parent_id: u16,
    /// Human-readable type name.
    pub type_name: String,
    /// Whether this type is constant.
    pub is_constant: bool,
}

impl TBAATypeNode {
    pub fn new(id: u16, parent_id: u16, name: &str) -> Self {
        Self {
            id,
            parent_id,
            type_name: name.to_string(),
            is_constant: false,
        }
    }

    pub fn constant(mut self) -> Self {
        self.is_constant = true;
        self
    }
}

/// TBAA type tree — full hierarchy of type nodes for alias queries.
#[derive(Debug, Clone, Default)]
pub struct TBAATypeTree {
    nodes: Vec<TBAATypeNode>,
}

impl TBAATypeTree {
    pub fn new() -> Self {
        // Root node at index 0
        let mut tree = Self { nodes: Vec::new() };
        tree.nodes.push(TBAATypeNode::new(0, 0, "root"));
        tree
    }

    /// Add a type node to the tree.
    pub fn add_node(&mut self, node: TBAATypeNode) -> u16 {
        let id = node.id;
        self.nodes.push(node);
        id
    }

    /// Add a struct path tag — records access path through a struct.
    pub fn add_struct_path(
        &mut self,
        base_type_id: u16,
        access_type_id: u16,
        offset: u64,
    ) -> TBAATag {
        TBAATag::new_struct_path(base_type_id, access_type_id, offset)
    }

    /// Check if two type nodes may alias (share a common ancestor).
    pub fn types_may_alias(&self, id_a: u16, id_b: u16) -> bool {
        if id_a == id_b {
            return true;
        }
        // Walk up the parent chain of both to find a common ancestor
        let ancestors_a = self.get_ancestors(id_a);
        let ancestors_b: std::collections::HashSet<u16> =
            self.get_ancestors(id_b).into_iter().collect();
        ancestors_a.iter().any(|a| ancestors_b.contains(a))
    }

    /// Get all ancestors of a type node (including itself).
    fn get_ancestors(&self, id: u16) -> Vec<u16> {
        let mut result = Vec::new();
        let mut current = id;
        while current != 0 {
            result.push(current);
            if let Some(node) = self.nodes.iter().find(|n| n.id == current) {
                current = node.parent_id;
            } else {
                break;
            }
        }
        result.push(0); // root
        result
    }

    /// Get the number of nodes in the tree.
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

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

/// TBAA tag — encodes type access information for a memory operation.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct TBAATag {
    /// 32-bit packed tag: [root:8][scope:8][base:8][access:8].
    pub tag: u32,
    /// Optional struct path offset.
    pub offset: Option<u64>,
}

impl TBAATag {
    /// Create a simple TBAA tag from base and access type IDs.
    pub fn new(base_type_id: u16, access_type_id: u16) -> Self {
        Self {
            tag: ((base_type_id as u32) << 16) | (access_type_id as u32),
            offset: None,
        }
    }

    /// Create a TBAA tag with root scope.
    pub fn new_with_root(root_id: u8, base_type_id: u16, access_type_id: u16) -> Self {
        Self {
            tag: ((root_id as u32) << 24)
                | ((base_type_id as u32 & 0xFF) << 16)
                | (access_type_id as u32 & 0xFFFF),
            offset: None,
        }
    }

    /// Create a struct path TBAA tag.
    pub fn new_struct_path(base_type_id: u16, access_type_id: u16, offset: u64) -> Self {
        Self {
            tag: ((base_type_id as u32) << 16) | (access_type_id as u32),
            offset: Some(offset),
        }
    }

    /// Get the root id (bits 24-31).
    pub fn root_id(&self) -> u8 {
        ((self.tag >> 24) & 0xFF) as u8
    }

    /// Get the scope id (bits 16-23).
    pub fn scope_id(&self) -> u8 {
        ((self.tag >> 16) & 0xFF) as u8
    }

    /// Get the base type id (bits 16-31).
    pub fn base_type_id(&self) -> u16 {
        ((self.tag >> 16) & 0xFFFF) as u16
    }

    /// Get the access type id (bits 0-15).
    pub fn access_type_id(&self) -> u16 {
        (self.tag & 0xFFFF) as u16
    }

    /// Set the scope domain.
    pub fn with_scope(mut self, scope: u8) -> Self {
        self.tag = (self.tag & 0xFF00FFFF) | ((scope as u32) << 16);
        self
    }
}

// ============================================================================
// Enhanced ScopedNoAlias analysis with domain management
// ============================================================================

/// Domain scope identifier for ScopedNoAlias.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct AliasScopeDomain {
    pub domain_id: u8,
    pub scope_id: u8,
}

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

    /// Returns true if this domain and scope make the location noalias.
    pub fn is_noalias(&self, other: &AliasScopeDomain) -> bool {
        // Same domain but different scopes → NoAlias
        self.domain_id != 0
            && other.domain_id != 0
            && self.domain_id == other.domain_id
            && self.scope_id != other.scope_id
    }
}

// ============================================================================
// CaptureTracker — track pointer escapes
// ============================================================================

/// Tracks whether a pointer value is captured (escapes its defining scope).
///
/// @llvm_behavior: LLVM's CaptureTracker is used by BasicAA to determine
/// if an alloca can be proven not to escape, enabling stronger alias results.
#[derive(Debug, Clone)]
pub struct CaptureTracker {
    pub captured: bool,
    pub captured_by_ret: bool,
    pub captured_by_arg: bool,
    pub captured_by_global: bool,
    pub capturing_users: Vec<ValueRef>,
}

impl CaptureTracker {
    pub fn new() -> Self {
        Self {
            captured: false,
            captured_by_ret: false,
            captured_by_arg: false,
            captured_by_global: false,
            capturing_users: Vec::new(),
        }
    }

    /// Track uses of a pointer to determine if it escapes.
    pub fn track_uses(&mut self, ptr: &ValueRef) {
        let p = ptr.borrow();
        for use_ in &p.uses {
            if let Some(user) = use_.user.upgrade() {
                let u = user.borrow();
                match u.get_opcode() {
                    Some(Opcode::Store) => {
                        // If stored, the pointer value (operand 0) is stored to
                        // memory (operand 1); the stored-to pointer also captures
                        // if operand 0 is a pointer
                        if use_.operand_no == 0 {
                            self.captured = true;
                            self.capturing_users.push(user.clone());
                        }
                    }
                    Some(Opcode::Load) => {
                        // Load doesn't capture the pointer itself
                    }
                    Some(Opcode::GetElementPtr) => {
                        // GEP doesn't capture — track through it
                        self.track_uses(&user);
                    }
                    Some(Opcode::BitCast) => {
                        self.track_uses(&user);
                    }
                    Some(Opcode::Call) => {
                        // Calling a function passes the pointer as an argument
                        if use_.operand_no > 0 {
                            self.captured = true;
                            self.captured_by_arg = true;
                            self.capturing_users.push(user.clone());
                        }
                    }
                    Some(Opcode::Ret) => {
                        self.captured = true;
                        self.captured_by_ret = true;
                        self.capturing_users.push(user.clone());
                    }
                    _ => {}
                }
            }
        }
    }

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

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

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

// ============================================================================
// Additional MemoryLocation helpers
// ============================================================================

impl MemoryLocation {
    /// Create a MemoryLocation for an instruction (load or store).
    pub fn from_instruction(inst: &ValueRef) -> Option<Self> {
        get_memory_location(inst)
    }

    /// Set TBAA tags from a 32-bit tag.
    pub fn with_tbaa_tag(mut self, tag: u32) -> Self {
        self.aa_tags = Some(tag);
        self
    }

    /// Set scoped noalias domain and scope.
    pub fn with_scoped_noalias(mut self, domain: u8, scope: u8) -> Self {
        let scope_tag = ((domain as u32) << 24) | ((scope as u32) << 16);
        self.aa_tags = Some(match self.aa_tags {
            Some(existing) => (existing & 0xFFFF) | scope_tag,
            None => scope_tag,
        });
        self
    }

    /// Check if this location has scoped noalias metadata.
    pub fn has_scoped_noalias(&self) -> bool {
        self.aa_tags.map_or(false, |t| ((t >> 24) & 0xFF) != 0)
    }

    /// Get the scoped noalias domain, if present.
    pub fn scoped_noalias_domain(&self) -> Option<u8> {
        self.aa_tags.map(|t| ((t >> 24) & 0xFF) as u8)
    }

    /// Get the scoped noalias scope, if present.
    pub fn scoped_noalias_scope(&self) -> Option<u8> {
        self.aa_tags.map(|t| ((t >> 16) & 0xFF) as u8)
    }

    /// Check if the size is a known, compile-time constant.
    pub fn has_known_size(&self) -> bool {
        self.size > 0 && self.size != u64::MAX
    }

    /// Returns a String representation for debugging.
    pub fn to_debug_string(&self) -> String {
        format!(
            "MemoryLocation(ptr_vid={}, size={}, tags={:?})",
            self.ptr.borrow().vid,
            self.size,
            self.aa_tags
        )
    }
}

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

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

    /// Helper: create a basic test Value with a given name and type.
    fn make_ptr_val(name: &str) -> ValueRef {
        let ty = Type::pointer(0);
        let v = llvm_native_core::value::Value::new(ty).named(name);
        valref(v)
    }

    /// Helper: create an alloca instruction ValueRef.
    fn make_alloca(name: &str) -> ValueRef {
        let ptr_ty = Type::pointer(0);
        let mut v = llvm_native_core::value::Value::new(ptr_ty).named(name);
        v.subclass = SubclassKind::Instruction;
        v.opcode = Some(Opcode::Alloca);
        v.num_operands = 0;
        valref(v)
    }

    /// Helper: create a global variable ValueRef.
    fn make_global(name: &str, is_const: bool) -> ValueRef {
        let ptr_ty = Type::pointer(0);
        let prefix = if is_const { "const_" } else { "" };
        let mut v = llvm_native_core::value::Value::new(ptr_ty).named(&format!("{}{}", prefix, name));
        v.subclass = SubclassKind::GlobalVariable;
        valref(v)
    }

    /// Helper: create a constant i32 value.
    fn make_constant_i32(name: &str, val: i32) -> ValueRef {
        let mut v = llvm_native_core::value::Value::new(Type::i32()).named(name);
        v.subclass = SubclassKind::Constant;
        // Store value in the name for later parsing
        v.name = format!("{}", val);
        valref(v)
    }

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

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

    // -----------------------------------------------------------------------
    // 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);
    }

    // -----------------------------------------------------------------------
    // 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
        );
        assert_eq!(
            ModRefInfo::union(ModRefInfo::NoModRef, ModRefInfo::NoModRef),
            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 ptr = make_ptr_val("ptr");
        let loc = MemoryLocation::new(Rc::clone(&ptr), 8);
        assert!(Rc::ptr_eq(&loc.ptr, &ptr));
        assert_eq!(loc.size, 8);
        assert!(loc.aa_tags.is_none());
    }

    #[test]
    fn test_memory_location_with_tags() {
        let ptr = make_ptr_val("ptr");
        let loc = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010002);
        assert_eq!(loc.tbaa_root(), Some(0x0001));
        assert_eq!(loc.tbaa_access_type(), Some(0x0002));
    }

    #[test]
    fn test_memory_location_has_size() {
        let ptr = make_ptr_val("ptr");
        assert!(MemoryLocation::new(Rc::clone(&ptr), 8).has_size());
        assert!(!MemoryLocation::new(Rc::clone(&ptr), 0).has_size());
    }

    #[test]
    fn test_memory_location_no_tags() {
        let ptr = make_ptr_val("ptr");
        let loc = MemoryLocation::new(Rc::clone(&ptr), 8);
        assert_eq!(loc.tbaa_root(), None);
        assert_eq!(loc.tbaa_access_type(), None);
    }

    // -----------------------------------------------------------------------
    // BasicAliasAnalysis tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_basic_aa_name() {
        let baa = BasicAliasAnalysis::new();
        assert_eq!(baa.name(), "BasicAA");
    }

    #[test]
    fn test_basic_aa_same_pointer_must_alias() {
        let ptr = make_ptr_val("x");
        let loc = MemoryLocation::new(Rc::clone(&ptr), 8);
        let baa = BasicAliasAnalysis::new();
        assert_eq!(baa.alias(&loc, &loc), AliasResult::MustAlias);
    }

    #[test]
    fn test_basic_aa_different_allocas_no_alias() {
        let a1 = make_alloca("a1");
        let a2 = make_alloca("a2");
        let loc1 = MemoryLocation::new(a1, 4);
        let loc2 = MemoryLocation::new(a2, 4);
        let baa = BasicAliasAnalysis::new();
        assert_eq!(baa.alias(&loc1, &loc2), AliasResult::NoAlias);
    }

    #[test]
    fn test_basic_aa_different_globals_no_alias() {
        let g1 = make_global("g1", false);
        let g2 = make_global("g2", false);
        let loc1 = MemoryLocation::new(g1, 4);
        let loc2 = MemoryLocation::new(g2, 4);
        let baa = BasicAliasAnalysis::new();
        assert_eq!(baa.alias(&loc1, &loc2), AliasResult::NoAlias);
    }

    #[test]
    fn test_basic_aa_alloca_and_global_no_alias_local() {
        let a = make_alloca("a");
        let g = make_global("g", false);
        let loc1 = MemoryLocation::new(a, 4);
        let loc2 = MemoryLocation::new(g, 4);
        let baa = BasicAliasAnalysis::new();
        assert_eq!(baa.alias(&loc1, &loc2), AliasResult::NoAlias);
    }

    // -----------------------------------------------------------------------
    // TypeBasedAliasAnalysis tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_tbaa_name() {
        let tbaa = TypeBasedAliasAnalysis::new();
        assert_eq!(tbaa.name(), "TBAA");
    }

    #[test]
    fn test_tbaa_same_tags_may_alias() {
        let ptr = make_ptr_val("x");
        let loc1 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010003);
        let loc2 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010003);
        let tbaa = TypeBasedAliasAnalysis::new();
        assert_eq!(tbaa.alias(&loc1, &loc2), AliasResult::MayAlias);
    }

    #[test]
    fn test_tbaa_different_roots_no_alias() {
        let ptr = make_ptr_val("x");
        let loc1 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010001);
        let loc2 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00020001);
        let tbaa = TypeBasedAliasAnalysis::new();
        assert_eq!(tbaa.alias(&loc1, &loc2), AliasResult::NoAlias);
    }

    #[test]
    fn test_tbaa_within_range_may_alias() {
        let ptr = make_ptr_val("x");
        let loc1 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010001);
        let loc2 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010005);
        let tbaa = TypeBasedAliasAnalysis::new();
        assert_eq!(tbaa.alias(&loc1, &loc2), AliasResult::MayAlias);
    }

    #[test]
    fn test_tbaa_noalias_far_apart() {
        let ptr = make_ptr_val("x");
        let loc1 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010001);
        let loc2 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010020);
        let tbaa = TypeBasedAliasAnalysis::new();
        assert_eq!(tbaa.alias(&loc1, &loc2), AliasResult::NoAlias);
    }

    #[test]
    fn test_tbaa_missing_tags_may_alias() {
        let ptr = make_ptr_val("x");
        let loc1 = MemoryLocation::new(Rc::clone(&ptr), 4);
        let loc2 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010001);
        let tbaa = TypeBasedAliasAnalysis::new();
        assert_eq!(tbaa.alias(&loc1, &loc2), AliasResult::MayAlias);
    }

    #[test]
    fn test_tbaa_constant_memory_tag() {
        let ptr = make_ptr_val("x");
        let loc = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00000000);
        let tbaa = TypeBasedAliasAnalysis::new();
        assert!(tbaa.points_to_constant_memory(&loc));

        let loc2 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00010001);
        assert!(!tbaa.points_to_constant_memory(&loc2));
    }

    // -----------------------------------------------------------------------
    // ScopedNoAliasAnalysis tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_scoped_noalias_name() {
        let sna = ScopedNoAliasAnalysis::new();
        assert_eq!(sna.name(), "ScopedNoAliasAA");
    }

    #[test]
    fn test_scoped_noalias_different_scopes() {
        let ptr = make_ptr_val("x");
        let loc1 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x01000000);
        let loc2 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x02000000);
        let sna = ScopedNoAliasAnalysis::new();
        assert_eq!(sna.alias(&loc1, &loc2), AliasResult::NoAlias);
    }

    #[test]
    fn test_scoped_noalias_same_scope_may_alias() {
        let ptr = make_ptr_val("x");
        let loc1 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x01000000);
        let loc2 = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x01000000);
        let sna = ScopedNoAliasAnalysis::new();
        assert_eq!(sna.alias(&loc1, &loc2), AliasResult::MayAlias);
    }

    // -----------------------------------------------------------------------
    // AliasAnalysisAggregator tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_aggregator_name() {
        let agg = AliasAnalysisAggregator::new();
        assert_eq!(agg.name(), "AggregateAA");
    }

    #[test]
    fn test_aggregator_empty_returns_may_alias() {
        let ptr = make_ptr_val("x");
        let loc = MemoryLocation::new(Rc::clone(&ptr), 8);
        let agg = AliasAnalysisAggregator::new();
        assert_eq!(agg.alias(&loc, &loc), AliasResult::MayAlias);
    }

    #[test]
    fn test_aggregator_chains_analyses() {
        let mut agg = AliasAnalysisAggregator::new();
        agg.add(Box::new(BasicAliasAnalysis::new()));
        agg.add(Box::new(TypeBasedAliasAnalysis::new()));

        let a1 = make_alloca("a1");
        let a2 = make_alloca("a2");
        let loc1 = MemoryLocation::new(a1, 4);
        let loc2 = MemoryLocation::new(a2, 4);

        assert_eq!(agg.alias(&loc1, &loc2), AliasResult::NoAlias);
    }

    #[test]
    fn test_aggregator_with_builder_pattern() {
        let ptr1 = make_ptr_val("x");
        let ptr2 = make_ptr_val("y");
        let loc1 = MemoryLocation::with_tags(Rc::clone(&ptr1), 4, 0x01000000);
        let loc2 = MemoryLocation::with_tags(Rc::clone(&ptr2), 4, 0x02000000);

        let agg = AliasAnalysisAggregator::new()
            .with(Box::new(BasicAliasAnalysis::new()))
            .with(Box::new(ScopedNoAliasAnalysis::new()));

        // Different pointers with different scopes → ScopedNoAlias returns NoAlias
        assert_eq!(agg.alias(&loc1, &loc2), AliasResult::NoAlias);
    }

    #[test]
    fn test_aggregator_points_to_constant_memory() {
        let ptr = make_ptr_val("x");
        let loc = MemoryLocation::with_tags(Rc::clone(&ptr), 4, 0x00000000);

        let mut agg = AliasAnalysisAggregator::new();
        agg.add(Box::new(TypeBasedAliasAnalysis::new()));
        assert!(agg.points_to_constant_memory(&loc));
    }

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

    #[test]
    fn test_is_identical_alloca_true() {
        let a = make_alloca("a");
        assert!(is_identical_alloca(&a, &a));
    }

    #[test]
    fn test_is_identical_alloca_different() {
        let a1 = make_alloca("a1");
        let a2 = make_alloca("a2");
        assert!(!is_identical_alloca(&a1, &a2));
    }

    #[test]
    fn test_is_identical_alloca_non_alloca() {
        let a = make_alloca("a");
        let p = make_ptr_val("p");
        assert!(!is_identical_alloca(&a, &p));
    }

    #[test]
    fn test_is_global_constant_true() {
        let g = make_global("g", true);
        assert!(is_global_constant(&g));
    }

    #[test]
    fn test_is_global_constant_false() {
        let g = make_global("g", false);
        assert!(!is_global_constant(&g));
    }

    #[test]
    fn test_get_underlying_object_alloca() {
        let a = make_alloca("a");
        let obj = get_underlying_object(&a);
        assert!(Rc::ptr_eq(&obj, &a));
    }

    #[test]
    fn test_get_underlying_object_global() {
        let g = make_global("g", false);
        let obj = get_underlying_object(&g);
        assert!(Rc::ptr_eq(&obj, &g));
    }

    #[test]
    fn test_get_memory_location_load() {
        let ptr = make_ptr_val("ptr");
        let inst = make_load(&ptr);
        let loc = get_memory_location(&inst);
        assert!(loc.is_some());
        let loc = loc.unwrap();
        assert!(Rc::ptr_eq(&loc.ptr, &ptr));
        assert_eq!(loc.size, 4); // i32 = 4 bytes
    }

    #[test]
    fn test_get_memory_location_store() {
        let val = make_ptr_val("val");
        let ptr = make_ptr_val("ptr");
        let inst = make_store(&val, &ptr);
        let loc = get_memory_location(&inst);
        assert!(loc.is_some());
        let loc = loc.unwrap();
        assert!(Rc::ptr_eq(&loc.ptr, &ptr));
    }

    #[test]
    fn test_get_memory_location_non_memory() {
        let mut v = llvm_native_core::value::Value::new(Type::i32()).named("add");
        v.subclass = SubclassKind::Instruction;
        v.opcode = Some(Opcode::Add);
        let inst = valref(v);

        let loc = get_memory_location(&inst);
        assert!(loc.is_none());
    }

    #[test]
    fn test_get_pointer_offset_alloca() {
        let a = make_alloca("a");
        assert_eq!(get_pointer_offset(&a), Some(0));
    }

    #[test]
    fn test_get_pointer_offset_global() {
        let g = make_global("g", false);
        assert_eq!(get_pointer_offset(&g), Some(0));
    }

    #[test]
    fn test_basic_alias_check_no_alias() {
        let a1 = make_alloca("a1");
        let a2 = make_alloca("a2");
        let loc1 = MemoryLocation::new(a1, 4);
        let loc2 = MemoryLocation::new(a2, 4);
        assert_eq!(basic_alias_check(&loc1, &loc2), AliasResult::NoAlias);
    }

    #[test]
    fn test_is_no_alias_true() {
        let a1 = make_alloca("a1");
        let a2 = make_alloca("a2");
        let loc1 = MemoryLocation::new(a1, 4);
        let loc2 = MemoryLocation::new(a2, 4);
        assert!(is_no_alias(&loc1, &loc2));
    }

    #[test]
    fn test_mod_ref_info_known_intrinsic_no_mod_ref() {
        let mut f_val = llvm_native_core::value::Value::new(Type::function_type_with(
            Type::double().id,
            vec![Type::double().id],
            false,
        ))
        .named("llvm.sqrt.f64");
        f_val.subclass = SubclassKind::Function;
        let func = valref(f_val);

        let mut v = llvm_native_core::value::Value::new(Type::double()).named("call");
        v.subclass = SubclassKind::Instruction;
        v.opcode = Some(Opcode::Call);
        v.operands.push(func);
        v.num_operands = 1;
        let call_inst = valref(v);

        let info = get_call_mod_ref_info(&call_inst);
        assert_eq!(info, ModRefInfo::NoModRef);
    }

    #[test]
    fn test_mod_ref_info_unknown_call_mod_ref() {
        let mut f_val =
            llvm_native_core::value::Value::new(Type::function_type_with(Type::void().id, vec![], false))
                .named("unknown_func");
        f_val.subclass = SubclassKind::Function;
        let func = valref(f_val);

        let mut v = llvm_native_core::value::Value::new(Type::void()).named("call");
        v.subclass = SubclassKind::Instruction;
        v.opcode = Some(Opcode::Call);
        v.operands.push(func);
        v.num_operands = 1;
        let call_inst = valref(v);

        let info = get_call_mod_ref_info(&call_inst);
        assert_eq!(info, ModRefInfo::ModRef);
    }

    #[test]
    fn test_get_constant_i64() {
        let c = make_constant_i32("c", 42);
        assert_eq!(get_constant_i64(&c), Some(42));
    }

    #[test]
    fn test_get_constant_i64_negative() {
        let c = make_constant_i32("c", -1);
        assert_eq!(get_constant_i64(&c), Some(-1));
    }

    #[test]
    fn test_get_constant_i64_non_constant() {
        let p = make_ptr_val("p");
        assert_eq!(get_constant_i64(&p), None);
    }
}