llvm-native-core 0.1.12

//! X86CodeGenPrepare — Pre-ISel code generation optimization pass.
//!
//! This module implements the X86-specific CodeGenPrepare (CGP) pass that
//! runs before instruction selection to canonicalize the IR for optimal
//! X86 code generation. The pass transforms the LLVM IR to expose addressing
//! modes, optimize loads/stores, promote types, hoist constants, and
//! prepare the function for instruction selection.
//!
//! Key transformations:
//! - Address mode sinking: fold GEP offsets into memory operands
//! - Critical edge splitting for better code placement
//! - PHI node elimination and replacement with copies
//! - Small integer promotion (i8/i16 → i32) for better encoding
//! - Switch lowering: lookup tables, bit tests, jump tables
//! - Memcpy/memset recognition: REP STOSB/MOVSB with threshold tuning
//! - GEP decomposition and reassociation
//! - Adjacent load/store combining
//! - Constant hoisting out of loops
//! - Indirect call promotion with PGO data
//! - Speculative devirtualization
//! - Large integer operation expansion
//! - Debug intrinsic lowering
//! - Vector operation expansion for unsupported types
//!
//! Clean-room reconstruction from published X86 optimization guides,
//! Intel/AMD optimization manuals, and observable compiler behavior.
//! No LLVM source code consulted.

#![allow(non_camel_case_types, unused_imports)]

use std::collections::{BTreeMap, HashMap, HashSet, VecDeque};

// ═══════════════════════════════════════════════════════════════════════════════
// Core Types for CodeGenPrepare
// ═══════════════════════════════════════════════════════════════════════════════

/// The primary CodeGenPrepare pass structure for X86 targets.
#[derive(Debug, Clone)]
pub struct X86CodeGenPrepare {
    /// Target triple (e.g., "x86_64-unknown-linux-gnu").
    pub target_triple: String,
    /// Whether targeting 64-bit mode.
    pub is_64bit: bool,
    /// Optimization level (0-3).
    pub opt_level: u8,
    /// Configuration for the pass.
    pub config: CGPConfig,
    /// Statistics collected during the pass.
    pub stats: CGPStats,
    /// Profiling data for PGO-guided transformations.
    pub profile_data: Option<CGProfileData>,
    /// Symbol table for indirect call targets.
    pub vtables: HashMap<String, Vec<CGCallTarget>>,
    /// Function-level analysis results.
    pub func_info: HashMap<String, CGFuncInfo>,
}

/// Configuration for the CodeGenPrepare pass.
#[derive(Debug, Clone)]
pub struct CGPConfig {
    /// Enable address mode sinking into memory operands.
    pub enable_addr_mode_sinking: bool,
    /// Minimum number of uses for address mode sinking to be profitable.
    pub addr_sink_min_uses: usize,
    /// Maximum GEP offset to sink into addressing mode.
    pub addr_sink_max_offset: i64,
    /// Enable critical edge splitting.
    pub enable_critical_edge_split: bool,
    /// Enable PHI node elimination.
    pub enable_phi_elim: bool,
    /// Enable small integer promotion (i8/i16 → i32).
    pub enable_type_promotion: bool,
    /// Enable switch lowering to lookup tables.
    pub enable_switch_lookup: bool,
    /// Enable switch lowering to bit tests.
    pub enable_switch_bit_test: bool,
    /// Enable memcpy/memset recognition.
    pub enable_mem_intrinsics: bool,
    /// Minimum size for memset to use REP STOSB.
    pub memset_rep_threshold: usize,
    /// Minimum size for memcpy to use REP MOVSB.
    pub memcpy_rep_threshold: usize,
    /// Enable adjacent load/store combining.
    pub enable_load_store_combine: bool,
    /// Enable constant hoisting out of loops.
    pub enable_const_hoisting: bool,
    /// Enable indirect call promotion with PGO.
    pub enable_indirect_call_promotion: bool,
    /// Enable speculative devirtualization.
    pub enable_devirtualization: bool,
    /// Enable large integer operation expansion.
    pub enable_large_int_expand: bool,
    /// Enable debug intrinsic lowering.
    pub enable_debug_lowering: bool,
    /// Enable vector operation expansion.
    pub enable_vector_expand: bool,
    /// Enable GEP decomposition.
    pub enable_gep_decomposition: bool,
    /// Maximum number of entries for a switch lookup table.
    pub switch_lookup_max_entries: usize,
    /// Minimum density for switch lookup table (entries / range).
    pub switch_lookup_min_density: f64,
    /// Maximum number of cases for switch bit test.
    pub switch_bit_test_max_cases: usize,
    /// Maximum size (in bits) to promote to.
    pub type_promotion_target_bits: usize,
    /// Minimum number of loads/stores to combine (adjacent).
    pub load_store_combine_min: usize,
    /// Maximum combined size for adjacent load/store merging.
    pub load_store_combine_max_bytes: usize,
}

impl Default for CGPConfig {
    fn default() -> Self {
        Self {
            enable_addr_mode_sinking: true,
            addr_sink_min_uses: 2,
            addr_sink_max_offset: 4096,
            enable_critical_edge_split: true,
            enable_phi_elim: true,
            enable_type_promotion: true,
            enable_switch_lookup: true,
            enable_switch_bit_test: true,
            enable_mem_intrinsics: true,
            memset_rep_threshold: 128,
            memcpy_rep_threshold: 256,
            enable_load_store_combine: true,
            enable_const_hoisting: true,
            enable_indirect_call_promotion: true,
            enable_devirtualization: true,
            enable_large_int_expand: true,
            enable_debug_lowering: true,
            enable_vector_expand: true,
            enable_gep_decomposition: true,
            switch_lookup_max_entries: 4096,
            switch_lookup_min_density: 0.25,
            switch_bit_test_max_cases: 64,
            type_promotion_target_bits: 32,
            load_store_combine_min: 2,
            load_store_combine_max_bytes: 128,
        }
    }
}

/// Statistics collected during CodeGenPrepare.
#[derive(Debug, Clone, Default)]
pub struct CGPStats {
    pub addr_modes_sunk: usize,
    pub critical_edges_split: usize,
    pub phis_eliminated: usize,
    pub types_promoted: usize,
    pub switches_lowered_lookup: usize,
    pub switches_lowered_bit_test: usize,
    pub mem_intrinsics_recognized: usize,
    pub loads_combined: usize,
    pub stores_combined: usize,
    pub constants_hoisted: usize,
    pub indirect_calls_promoted: usize,
    pub calls_devirtualized: usize,
    pub large_ints_expanded: usize,
    pub debug_intrinsics_lowered: usize,
    pub vectors_expanded: usize,
    pub geps_decomposed: usize,
    pub gep_sunk: usize,
    pub total_blocks: usize,
    pub total_instructions: usize,
    pub functions_processed: usize,
    pub profitable_sinks: usize,
    pub unprofitable_sinks: usize,
}

/// Profile data for PGO-guided transformations.
#[derive(Debug, Clone, Default)]
pub struct CGProfileData {
    /// Call counts for each function (function_name → call_count).
    pub function_counts: HashMap<String, u64>,
    /// Indirect call target probabilities (call_site_id → list of (target_fn, probability)).
    pub indirect_call_targets: HashMap<usize, Vec<(String, f64)>>,
    /// Branch probabilities (branch_id → taken_probability).
    pub branch_probs: HashMap<usize, f64>,
    /// Loop trip counts (loop_header_id → average_trip_count).
    pub loop_trip_counts: HashMap<usize, f64>,
}

/// An indirect/virtual call target.
#[derive(Debug, Clone)]
pub struct CGCallTarget {
    pub fn_name: String,
    pub probability: f64,
    pub is_devirtualized: bool,
}

/// Function-level analysis info.
#[derive(Debug, Clone, Default)]
pub struct CGFuncInfo {
    /// Whether the function has indirect calls.
    pub has_indirect_calls: bool,
    /// Whether the function has virtual calls.
    pub has_virtual_calls: bool,
    /// Size of the function in instructions.
    pub size: usize,
    /// Number of basic blocks.
    pub blocks: usize,
    /// Loop depth map (block_id → depth).
    pub loop_depths: HashMap<usize, usize>,
    /// Hot/cold splitting boundaries.
    pub hot_entry: usize,
}

// ═══════════════════════════════════════════════════════════════════════════════
// IR-Like Types for CodeGenPrepare
// ═══════════════════════════════════════════════════════════════════════════════

/// Simplified LLVM IR value for CGP transformations.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum CGPValue {
    /// A local variable / virtual register.
    Local(String),
    /// An integer constant.
    Constant(i64),
    /// An undefined value.
    Undef,
    /// A global variable reference.
    Global(String),
    /// A function reference.
    Function(String),
    /// A null pointer.
    NullPtr,
    /// Block label.
    Label(usize),
}

impl fmt::Display for CGPValue {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Local(s) => write!(f, "%{}", s),
            Self::Constant(c) => write!(f, "{}", c),
            Self::Undef => write!(f, "undef"),
            Self::Global(g) => write!(f, "@{}", g),
            Self::Function(fn_name) => write!(f, "@{}", fn_name),
            Self::NullPtr => write!(f, "null"),
            Self::Label(id) => write!(f, "label %{}", id),
        }
    }
}

/// Instructions that CodeGenPrepare operates on.
#[derive(Debug, Clone)]
pub enum CGPInst {
    /// Alloca: allocate stack space.
    Alloca {
        dest: String,
        ty: CGPType,
        align: usize,
    },
    /// Load: load from memory.
    Load {
        dest: String,
        ptr: CGPValue,
        ty: CGPType,
        align: usize,
        is_volatile: bool,
    },
    /// Store: store to memory.
    Store {
        src: CGPValue,
        ptr: CGPValue,
        ty: CGPType,
        align: usize,
        is_volatile: bool,
    },
    /// GetElementPtr: address computation.
    GEP {
        dest: String,
        base: CGPValue,
        indices: Vec<CGPValue>,
        inbounds: bool,
    },
    /// Arithmetic binary operation.
    BinOp {
        dest: String,
        op: CGPBinOp,
        lhs: CGPValue,
        rhs: CGPValue,
        ty: CGPType,
    },
    /// Integer comparison.
    ICmp {
        dest: String,
        pred: IcmpPredicate,
        lhs: CGPValue,
        rhs: CGPValue,
        ty: CGPType,
    },
    /// Call instruction.
    Call {
        dest: Option<String>,
        callee: CGPValue,
        args: Vec<CGPValue>,
        is_tail: bool,
        cc: CallConv,
    },
    /// Branch (unconditional).
    Br { dest: usize },
    /// Conditional branch.
    CondBr {
        cond: CGPValue,
        true_dest: usize,
        false_dest: usize,
    },
    /// Switch instruction.
    Switch {
        value: CGPValue,
        default_dest: usize,
        cases: Vec<(CGPValue, usize)>,
    },
    /// Return.
    Ret { value: Option<CGPValue> },
    /// PHI node.
    Phi {
        dest: String,
        incoming: Vec<(CGPValue, usize)>,
        ty: CGPType,
    },
    /// Select (conditional value).
    Select {
        dest: String,
        cond: CGPValue,
        true_val: CGPValue,
        false_val: CGPValue,
        ty: CGPType,
    },
    /// ExtractValue from aggregate.
    ExtractValue {
        dest: String,
        agg: CGPValue,
        indices: Vec<usize>,
        ty: CGPType,
    },
    /// InsertValue into aggregate.
    InsertValue {
        dest: String,
        agg: CGPValue,
        val: CGPValue,
        indices: Vec<usize>,
        ty: CGPType,
    },
    /// Cast between types.
    Cast {
        dest: String,
        src: CGPValue,
        op: CGPCCastOp,
        src_ty: CGPType,
        dest_ty: CGPType,
    },
    /// Debug value intrinsic.
    DbgValue {
        value: CGPValue,
        var: String,
        location: DbgLocation,
    },
    /// Debug declare intrinsic.
    DbgDeclare { var: String, location: DbgLocation },
    /// Block boundary markers.
    NoOp,
}

use std::fmt;

/// Binary operation kind.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum CGPBinOp {
    Add,
    Sub,
    Mul,
    UDiv,
    SDiv,
    URem,
    SRem,
    Shl,
    LShr,
    AShr,
    And,
    Or,
    Xor,
}

impl fmt::Display for CGPBinOp {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Add => write!(f, "add"),
            Self::Sub => write!(f, "sub"),
            Self::Mul => write!(f, "mul"),
            Self::UDiv => write!(f, "udiv"),
            Self::SDiv => write!(f, "sdiv"),
            Self::URem => write!(f, "urem"),
            Self::SRem => write!(f, "srem"),
            Self::Shl => write!(f, "shl"),
            Self::LShr => write!(f, "lshr"),
            Self::AShr => write!(f, "ashr"),
            Self::And => write!(f, "and"),
            Self::Or => write!(f, "or"),
            Self::Xor => write!(f, "xor"),
        }
    }
}

/// ICmp predicate.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum IcmpPredicate {
    Eq,
    Ne,
    Ugt,
    Uge,
    Ult,
    Ule,
    Sgt,
    Sge,
    Slt,
    Sle,
}

impl IcmpPredicate {
    pub fn invert(self) -> Self {
        match self {
            Self::Eq => Self::Ne,
            Self::Ne => Self::Eq,
            Self::Ugt => Self::Ule,
            Self::Uge => Self::Ult,
            Self::Ult => Self::Uge,
            Self::Ule => Self::Ugt,
            Self::Sgt => Self::Sle,
            Self::Sge => Self::Slt,
            Self::Slt => Self::Sge,
            Self::Sle => Self::Sgt,
        }
    }
}

/// Cast operation kind.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum CGPCCastOp {
    ZExt,
    SExt,
    Trunc,
    BitCast,
    PtrToInt,
    IntToPtr,
    FpToUI,
    FpToSI,
    UiToFp,
    SiToFp,
    FpTrunc,
    FpExt,
}

/// Type representation in CGP.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum CGPType {
    Void,
    I1,
    I8,
    I16,
    I32,
    I64,
    I128,
    F16,
    F32,
    F64,
    F80,
    F128,
    Ptr(Box<CGPType>),
    Array(Box<CGPType>, usize),
    Struct(Vec<CGPType>, bool),  // packed?
    Vector(Box<CGPType>, usize), // element type, num elements
    Opaque(String),
}

impl CGPType {
    pub fn size_bits(&self) -> usize {
        match self {
            Self::Void => 0,
            Self::I1 => 1,
            Self::I8 => 8,
            Self::I16 => 16,
            Self::I32 => 32,
            Self::I64 => 64,
            Self::I128 => 128,
            Self::F16 => 16,
            Self::F32 => 32,
            Self::F64 => 64,
            Self::F80 => 80,
            Self::F128 => 128,
            Self::Ptr(_) => 64,
            Self::Array(et, n) => et.size_bits() * n,
            Self::Struct(fields, _) => fields.iter().map(|f| f.size_bits()).sum(),
            Self::Vector(et, n) => et.size_bits() * n,
            Self::Opaque(_) => 0,
        }
    }

    pub fn size_bytes(&self) -> usize {
        (self.size_bits() + 7) / 8
    }

    pub fn is_integer(&self) -> bool {
        matches!(
            self,
            Self::I1 | Self::I8 | Self::I16 | Self::I32 | Self::I64 | Self::I128
        )
    }

    pub fn is_small_integer(&self) -> bool {
        matches!(self, Self::I1 | Self::I8 | Self::I16)
    }

    pub fn is_vector(&self) -> bool {
        matches!(self, Self::Vector(_, _))
    }

    pub fn is_pointer(&self) -> bool {
        matches!(self, Self::Ptr(_))
    }
}

impl fmt::Display for CGPType {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Void => write!(f, "void"),
            Self::I1 => write!(f, "i1"),
            Self::I8 => write!(f, "i8"),
            Self::I16 => write!(f, "i16"),
            Self::I32 => write!(f, "i32"),
            Self::I64 => write!(f, "i64"),
            Self::I128 => write!(f, "i128"),
            Self::F16 => write!(f, "f16"),
            Self::F32 => write!(f, "f32"),
            Self::F64 => write!(f, "f64"),
            Self::F80 => write!(f, "f80"),
            Self::F128 => write!(f, "f128"),
            Self::Ptr(ty) => write!(f, "ptr_{}", ty),
            Self::Array(et, n) => write!(f, "[{} x {}]", n, et),
            Self::Struct(fields, _) => {
                let s: Vec<String> = fields.iter().map(|f| format!("{}", f)).collect();
                write!(f, "{{{}}}", s.join(", "))
            }
            Self::Vector(et, n) => write!(f, "<{} x {}>", n, et),
            Self::Opaque(n) => write!(f, "opaque_{}", n),
        }
    }
}

/// Calling convention.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum CallConv {
    C,
    Fast,
    Cold,
    X86_64_SysV,
    X86_64_Win64,
    X86_FastCall,
    X86_StdCall,
    X86_ThisCall,
    X86_VectorCall,
    X86_RegCall,
    Tail,
}

impl Default for CallConv {
    fn default() -> Self {
        Self::C
    }
}

/// Debug info location.
#[derive(Debug, Clone, Default)]
pub struct DbgLocation {
    pub line: usize,
    pub column: usize,
    pub file: String,
    pub inlined_at: Option<Box<DbgLocation>>,
}

/// A basic block in CGP.
#[derive(Debug, Clone)]
pub struct CGPBlock {
    pub id: usize,
    pub instructions: Vec<CGPInst>,
    pub predecessors: Vec<usize>,
    pub successors: Vec<usize>,
    pub is_entry: bool,
    pub loop_depth: usize,
    pub is_landing_pad: bool,
}

impl CGPBlock {
    pub fn new(id: usize) -> Self {
        Self {
            id,
            instructions: Vec::new(),
            predecessors: Vec::new(),
            successors: Vec::new(),
            is_entry: false,
            loop_depth: 0,
            is_landing_pad: false,
        }
    }
}

/// A function for CGP to operate on.
#[derive(Debug, Clone)]
pub struct CGPFunction {
    pub name: String,
    pub blocks: Vec<CGPBlock>,
    pub entry: usize,
    pub local_counter: usize,
}

impl CGPFunction {
    pub fn new(name: &str) -> Self {
        let entry_block = CGPBlock::new(0);
        Self {
            name: name.to_string(),
            blocks: vec![entry_block],
            entry: 0,
            local_counter: 0,
        }
    }

    pub fn add_block(&mut self, mut block: CGPBlock) -> usize {
        let id = self.blocks.len();
        block.id = id;
        self.blocks.push(block);
        id
    }

    pub fn fresh_local(&mut self, prefix: &str) -> String {
        self.local_counter += 1;
        format!("{}.{}", prefix, self.local_counter)
    }

    pub fn compute_predecessors(&mut self) {
        for i in 0..self.blocks.len() {
            self.blocks[i].predecessors.clear();
        }
        for i in 0..self.blocks.len() {
            let succs: Vec<usize> = self.blocks[i].successors.clone();
            for s in succs {
                if s < self.blocks.len() {
                    self.blocks[s].predecessors.push(i);
                }
            }
        }
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Sinking Addressing Modes
// ═══════════════════════════════════════════════════════════════════════════════

/// Represents a recognized X86 addressing mode.
#[derive(Debug, Clone)]
pub struct AddressingMode {
    pub base: Option<CGPValue>,
    pub index: Option<CGPValue>,
    pub scale: u8, // 1, 2, 4, or 8
    pub displacement: i64,
    pub segment: Option<String>,
}

impl AddressingMode {
    pub fn new() -> Self {
        Self {
            base: None,
            index: None,
            scale: 1,
            displacement: 0,
            segment: None,
        }
    }

    pub fn simple(base: CGPValue) -> Self {
        Self {
            base: Some(base),
            index: None,
            scale: 1,
            displacement: 0,
            segment: None,
        }
    }

    pub fn with_offset(base: CGPValue, disp: i64) -> Self {
        Self {
            base: Some(base),
            index: None,
            scale: 1,
            displacement: disp,
            segment: None,
        }
    }

    pub fn with_index(base: CGPValue, index: CGPValue, scale: u8, disp: i64) -> Self {
        Self {
            base: Some(base),
            index: Some(index),
            scale,
            displacement: disp,
            segment: None,
        }
    }

    /// Check if the displacement fits in the x86 32-bit signed displacement field.
    pub fn is_legal_displacement(&self) -> bool {
        self.displacement >= -0x8000_0000 && self.displacement <= 0x7FFF_FFFF
    }

    /// Check if this addressing mode can be used without a base register.
    pub fn is_base_free(&self) -> bool {
        self.base.is_none()
    }

    pub fn is_simple_base_plus_offset(&self) -> bool {
        self.index.is_none()
    }

    pub fn is_indexed(&self) -> bool {
        self.index.is_some()
    }

    pub fn cost(&self) -> usize {
        let mut c = 0;
        if self.base.is_some() {
            c += 1;
        }
        if self.index.is_some() {
            c += 1;
        }
        if self.displacement != 0 {
            c += if self.displacement >= -128 && self.displacement <= 127 {
                1
            } else {
                4
            };
        }
        if self.segment.is_some() {
            c += 1;
        }
        c
    }
}

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

/// Address mode sinking profitability analysis.
#[derive(Debug, Clone)]
pub struct AddrSinkAnalysis {
    /// The GEP instruction being analyzed.
    pub gep_dest: String,
    /// The resulting addressing mode if sinking is profitable.
    pub addr_mode: Option<AddressingMode>,
    /// Number of uses that would benefit.
    pub use_count: usize,
    /// Estimated cycles saved.
    pub cycles_saved: f64,
    /// Whether sinking is profitable.
    pub is_profitable: bool,
}

impl AddrSinkAnalysis {
    pub fn new(gep_dest: &str) -> Self {
        Self {
            gep_dest: gep_dest.to_string(),
            addr_mode: None,
            use_count: 0,
            cycles_saved: 0.0,
            is_profitable: false,
        }
    }

    pub fn analyze(inst: &CGPInst, user_count: usize, config: &CGPConfig) -> Self {
        let mut analysis = Self::new("");
        match inst {
            CGPInst::GEP {
                dest,
                base,
                indices,
                inbounds: _,
            } => {
                let mut mode = AddressingMode::simple(base.clone());
                analysis.gep_dest = dest.clone();
                for idx in indices {
                    match idx {
                        CGPValue::Constant(offset) => {
                            mode.displacement = mode.displacement.wrapping_add(*offset);
                        }
                        CGPValue::Local(_) => {
                            if mode.index.is_none() {
                                mode.index = Some(idx.clone());
                                mode.scale = 1;
                            }
                        }
                        _ => {}
                    }
                }
                if mode.is_legal_displacement() {
                    analysis.use_count = user_count;
                    // Heuristic: sink if used by multiple memory ops
                    let base_cost = 1.0;
                    let saved_per_use = base_cost;
                    analysis.cycles_saved = user_count as f64 * saved_per_use;
                    analysis.is_profitable = user_count >= config.addr_sink_min_uses
                        && mode.displacement.abs() <= config.addr_sink_max_offset;
                    analysis.addr_mode = Some(mode);
                }
            }
            _ => {}
        }
        analysis
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Switch Lowering
// ═══════════════════════════════════════════════════════════════════════════════

/// Lowered switch form.
#[derive(Debug, Clone)]
pub enum LoweredSwitch {
    /// Switch lowered to a lookup table.
    LookupTable(LookupTable),
    /// Switch lowered to a bit test.
    BitTest(BitTest),
    /// Switch lowered to a binary decision tree.
    DecisionTree(DecisionTree),
    /// Switch left as-is.
    Unchanged,
}

/// A lookup table for switch lowering.
#[derive(Debug, Clone)]
pub struct LookupTable {
    pub base_value: i64,
    pub entries: Vec<i64>,
    pub default_value: usize,
    pub table_type: CGPType,
    pub alignment: usize,
}

impl LookupTable {
    pub fn from_switch(switch: &SwitchInfo, config: &CGPConfig) -> Option<Self> {
        if switch.cases.len() > config.switch_lookup_max_entries {
            return None;
        }
        if switch.cases.is_empty() {
            return None;
        }
        let min_val = switch.cases.iter().map(|c| c.0).min().unwrap();
        let max_val = switch.cases.iter().map(|c| c.0).max().unwrap();
        let range = (max_val - min_val) as usize + 1;
        let density = switch.cases.len() as f64 / range as f64;
        if density < config.switch_lookup_min_density {
            return None;
        }
        let mut entries = vec![switch.default_dest as i64; range];
        for (val, dest) in &switch.cases {
            let idx = (val - min_val) as usize;
            entries[idx] = *dest as i64;
        }
        Some(Self {
            base_value: min_val,
            entries,
            default_value: switch.default_dest,
            table_type: CGPType::I32,
            alignment: 4,
        })
    }

    pub fn size_bytes(&self) -> usize {
        self.entries.len() * 4 // assuming i32 entries
    }
}

/// A bit test for switch lowering.
#[derive(Debug, Clone)]
pub struct BitTest {
    pub cases: Vec<(u64, usize)>, // (bitmask, destination)
    pub default_dest: usize,
    pub num_bits: usize,
}

impl BitTest {
    pub fn from_switch(switch: &SwitchInfo, config: &CGPConfig) -> Option<Self> {
        if switch.cases.len() > config.switch_bit_test_max_cases {
            return None;
        }
        if switch.cases.is_empty() {
            return None;
        }
        let max_val = switch.cases.iter().map(|c| c.0).max().unwrap();
        if max_val > 64 {
            return None; // Only supports 64-bit bit tests
        }
        let num_bits = (max_val as usize + 1).min(64);
        Some(Self {
            cases: switch
                .cases
                .iter()
                .map(|(v, d)| (1u64 << (*v as u64), *d))
                .collect(),
            default_dest: switch.default_dest,
            num_bits,
        })
    }
}

/// A binary decision tree for switch lowering.
#[derive(Debug, Clone)]
pub struct DecisionTree {
    pub root: DTNode,
}

#[derive(Debug, Clone)]
pub enum DTNode {
    Leaf(usize),
    Branch {
        pivot: i64,
        lt: Box<DTNode>,
        ge: Box<DTNode>,
    },
}

/// Information about a switch instruction.
#[derive(Debug, Clone)]
pub struct SwitchInfo {
    pub cases: Vec<(i64, usize)>,
    pub default_dest: usize,
}

// ═══════════════════════════════════════════════════════════════════════════════
// Memory Intrinsic Recognition
// ═══════════════════════════════════════════════════════════════════════════════

/// Recognized memory intrinsic pattern.
#[derive(Debug, Clone)]
pub enum MemIntrinsicPattern {
    /// memset pattern recognized.
    Memset(MemsetInfo),
    /// memcpy pattern recognized.
    Memcpy(MemcpyInfo),
    /// memmove pattern recognized.
    Memmove(MemmoveInfo),
    /// Not a recognized pattern.
    None,
}

#[derive(Debug, Clone)]
pub struct MemsetInfo {
    pub dest_ptr: CGPValue,
    pub value: u8,
    pub size: CGPValue,
    pub alignment: usize,
    pub is_volatile: bool,
    pub use_rep_stosb: bool,
    pub estimated_size: Option<usize>,
}

#[derive(Debug, Clone)]
pub struct MemcpyInfo {
    pub dest_ptr: CGPValue,
    pub src_ptr: CGPValue,
    pub size: CGPValue,
    pub alignment: usize,
    pub is_volatile: bool,
    pub use_rep_movsb: bool,
    pub estimated_size: Option<usize>,
    pub may_overlap: bool,
}

#[derive(Debug, Clone)]
pub struct MemmoveInfo {
    pub dest_ptr: CGPValue,
    pub src_ptr: CGPValue,
    pub size: CGPValue,
    pub alignment: usize,
    pub may_overlap: bool,
}

/// Recognize a memset pattern from a loop.
pub fn recognize_memset(blocks: &[CGPBlock], config: &CGPConfig) -> Option<MemsetInfo> {
    // In a full implementation, this would analyze loop structure
    // to detect patterns like: for (i=0; i<n; i++) dest[i] = val;
    // For the purpose of this module, we provide the structure.
    for block in blocks {
        for inst in &block.instructions {
            if let CGPInst::Store {
                src: CGPValue::Constant(v),
                ptr,
                ty: _,
                align: a,
                is_volatile: _,
            } = inst
            {
                let val = (*v & 0xFF) as u8;
                return Some(MemsetInfo {
                    dest_ptr: ptr.clone(),
                    value: val,
                    size: CGPValue::Constant(0), // would need loop analysis
                    alignment: *a,
                    is_volatile: false,
                    use_rep_stosb: false,
                    estimated_size: None,
                });
            }
        }
    }
    None
}

/// Recognize a memcpy pattern from a loop.
pub fn recognize_memcpy(blocks: &[CGPBlock], config: &CGPConfig) -> Option<MemcpyInfo> {
    for block in blocks {
        for inst in &block.instructions {
            if let CGPInst::Store {
                src,
                ptr: dest,
                ty: _,
                align: a,
                is_volatile: _,
            } = inst
            {
                match src {
                    CGPValue::Local(_) => {
                        return Some(MemcpyInfo {
                            dest_ptr: dest.clone(),
                            src_ptr: CGPValue::Local("src".into()),
                            size: CGPValue::Constant(0),
                            alignment: *a,
                            is_volatile: false,
                            use_rep_movsb: false,
                            estimated_size: None,
                            may_overlap: false,
                        });
                    }
                    _ => continue,
                }
            }
        }
    }
    None
}

// ═══════════════════════════════════════════════════════════════════════════════
// Type Promotion
// ═══════════════════════════════════════════════════════════════════════════════

/// Type promotion analysis for small integer types.
#[derive(Debug, Clone)]
pub struct TypePromotion {
    /// Promote i8 to i32.
    pub promote_i8: bool,
    /// Promote i16 to i32.
    pub promote_i16: bool,
    /// Promote i1 (bool) to i8/i32.
    pub promote_i1: bool,
    /// Target bits for promotion (default 32).
    pub target_bits: usize,
}

impl Default for TypePromotion {
    fn default() -> Self {
        Self {
            promote_i8: true,
            promote_i16: true,
            promote_i1: true,
            target_bits: 32,
        }
    }
}

impl TypePromotion {
    pub fn should_promote(&self, ty: &CGPType) -> Option<CGPType> {
        match ty {
            CGPType::I1 if self.promote_i1 => Some(CGPType::I8),
            CGPType::I8 if self.promote_i8 => Some(CGPType::I32),
            CGPType::I16 if self.promote_i16 => Some(CGPType::I32),
            _ => None,
        }
    }

    pub fn promoted_type(&self, ty: &CGPType) -> CGPType {
        match ty {
            CGPType::I1 => CGPType::I8,
            CGPType::I8 | CGPType::I16 => CGPType::I32,
            _ => ty.clone(),
        }
    }

    /// Compute the cost of promoting a given type.
    pub fn promotion_cost(&self, ty: &CGPType) -> isize {
        match ty {
            CGPType::I8 => 3,  // i8: x86 needs zero/sign extension for many ops
            CGPType::I16 => 2, // i16: slightly better but still suboptimal
            CGPType::I1 => 1,  // i1: rarely used directly
            _ => 0,
        }
    }

    /// Check if promotion is net-profitable for this instruction.
    pub fn is_promotion_profitable(&self, inst: &CGPInst, user_count: usize) -> bool {
        let mut total_cost = 0isize;
        match inst {
            CGPInst::BinOp { ty, .. } => total_cost += self.promotion_cost(ty),
            CGPInst::ICmp { ty, .. } => total_cost += self.promotion_cost(ty),
            CGPInst::Cast {
                src_ty, dest_ty, ..
            } => {
                total_cost += self.promotion_cost(src_ty);
                total_cost += self.promotion_cost(dest_ty);
            }
            CGPInst::Load { ty, .. } | CGPInst::Store { ty, .. } => {
                total_cost += self.promotion_cost(ty);
            }
            _ => {}
        }
        // Promotion is profitable if cost > 0 and users benefit
        total_cost > 0 && user_count > 0
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Constant Hoisting
// ═══════════════════════════════════════════════════════════════════════════════

/// A constant candidate for hoisting.
#[derive(Debug, Clone)]
pub struct ConstHoistCandidate {
    pub value: CGPValue,
    pub use_count: usize,
    pub blocks: HashSet<usize>,
    pub loop_depth: usize,
    pub cost_saved: f64,
}

impl ConstHoistCandidate {
    pub fn new(value: CGPValue) -> Self {
        Self {
            value,
            use_count: 0,
            blocks: HashSet::new(),
            loop_depth: 0,
            cost_saved: 0.0,
        }
    }
}

/// Constant hoisting analysis and transformation.
#[derive(Debug, Clone)]
pub struct ConstantHoisting {
    pub candidates: Vec<ConstHoistCandidate>,
    pub hoisted: Vec<CGPInst>,
    pub min_uses_for_hoist: usize,
    pub min_loop_depth_for_hoist: usize,
}

impl Default for ConstantHoisting {
    fn default() -> Self {
        Self {
            candidates: Vec::new(),
            hoisted: Vec::new(),
            min_uses_for_hoist: 2,
            min_loop_depth_for_hoist: 1,
        }
    }
}

impl ConstantHoisting {
    pub fn analyze(&mut self, func: &CGPFunction) {
        let mut const_uses: HashMap<CGPValue, ConstHoistCandidate> = HashMap::new();
        for block in &func.blocks {
            for inst in &block.instructions {
                let constants: Vec<CGPValue> = Self::extract_constants(inst);
                for c in constants {
                    let entry = const_uses
                        .entry(c.clone())
                        .or_insert_with(|| ConstHoistCandidate::new(c));
                    entry.use_count += 1;
                    entry.blocks.insert(block.id);
                    entry.loop_depth = entry.loop_depth.max(block.loop_depth);
                }
            }
        }
        self.candidates = const_uses
            .into_values()
            .filter(|c| {
                c.use_count >= self.min_uses_for_hoist
                    && c.loop_depth >= self.min_loop_depth_for_hoist
            })
            .collect();
        // Estimate savings
        for cand in &mut self.candidates {
            cand.cost_saved = cand.use_count as f64 * (0.5 + cand.loop_depth as f64 * 0.25);
        }
        self.candidates.sort_by(|a, b| {
            b.cost_saved
                .partial_cmp(&a.cost_saved)
                .unwrap_or(std::cmp::Ordering::Equal)
        });
    }

    fn extract_constants(inst: &CGPInst) -> Vec<CGPValue> {
        let mut result = Vec::new();
        match inst {
            CGPInst::Store { src, ptr, .. } => {
                if let CGPValue::Constant(_) = src {
                    result.push(src.clone());
                }
                if let CGPValue::Constant(_) = ptr {
                    result.push(ptr.clone());
                }
            }
            CGPInst::GEP { base, indices, .. } => {
                if let CGPValue::Constant(_) = base {
                    result.push(base.clone());
                }
                for idx in indices {
                    if let CGPValue::Constant(_) = idx {
                        result.push(idx.clone());
                    }
                }
            }
            CGPInst::BinOp { lhs, rhs, .. } => {
                if let CGPValue::Constant(_) = lhs {
                    result.push(lhs.clone());
                }
                if let CGPValue::Constant(_) = rhs {
                    result.push(rhs.clone());
                }
            }
            CGPInst::Call { args, .. } => {
                for arg in args {
                    if let CGPValue::Constant(_) = arg {
                        result.push(arg.clone());
                    }
                }
            }
            CGPInst::Store { src: s, ptr: p, .. } => {
                if matches!(s, CGPValue::Constant(_)) {
                    result.push(s.clone());
                }
                if matches!(p, CGPValue::Constant(_)) {
                    result.push(p.clone());
                }
            }
            _ => {}
        }
        result
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Indirect Call Promotion & Devirtualization
// ═══════════════════════════════════════════════════════════════════════════════

/// Indirect call promotion result.
#[derive(Debug, Clone)]
pub struct CallPromotion {
    pub original_call: CGPInst,
    pub promoted_calls: Vec<CGPInst>,
    pub guard_comparison: Option<CGPInst>,
    pub probability: f64,
    pub is_profitable: bool,
}

/// Devirtualization analysis for virtual calls.
#[derive(Debug, Clone)]
pub struct DevirtAnalyzer {
    pub vtables: HashMap<String, Vec<CGCallTarget>>,
    pub profile_data: Option<CGProfileData>,
    pub min_devirt_probability: f64,
}

impl Default for DevirtAnalyzer {
    fn default() -> Self {
        Self {
            vtables: HashMap::new(),
            profile_data: None,
            min_devirt_probability: 0.5,
        }
    }
}

impl DevirtAnalyzer {
    pub fn analyze_call(&self, callee: &CGPValue) -> Vec<CallPromotion> {
        let mut promotions = Vec::new();
        let targets = match callee {
            CGPValue::Function(name) => {
                // Direct call — no devirtualization needed
                self.vtables.get(name)
            }
            _ => None,
        };

        if let Some(call_targets) = targets {
            for target in call_targets {
                if target.probability >= self.min_devirt_probability {
                    let mut insts = Vec::new();
                    // Build direct call to the devirtualized target
                    insts.push(CGPInst::Call {
                        dest: Some(format!("devirt.{}", target.fn_name)),
                        callee: CGPValue::Function(target.fn_name.clone()),
                        args: vec![],
                        is_tail: false,
                        cc: CallConv::C,
                    });
                    promotions.push(CallPromotion {
                        original_call: CGPInst::Call {
                            dest: None,
                            callee: callee.clone(),
                            args: vec![],
                            is_tail: false,
                            cc: CallConv::C,
                        },
                        promoted_calls: insts,
                        guard_comparison: None,
                        probability: target.probability,
                        is_profitable: target.probability > 0.7,
                    });
                }
            }
        }
        promotions
    }

    pub fn should_devirtualize(&self, target: &CGCallTarget) -> bool {
        target.probability >= self.min_devirt_probability
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Large Integer Expansion
// ═══════════════════════════════════════════════════════════════════════════════

/// Expand large integer operations (i128, i256, etc.) into pairs of smaller operations.
#[derive(Debug, Clone)]
pub struct LargeIntExpander {
    pub max_native_bits: usize,
}

impl Default for LargeIntExpander {
    fn default() -> Self {
        Self {
            max_native_bits: 64,
        }
    }
}

impl LargeIntExpander {
    pub fn needs_expansion(&self, ty: &CGPType) -> bool {
        ty.size_bits() > self.max_native_bits
    }

    pub fn expand_binop(&self, inst: &CGPInst) -> Vec<CGPInst> {
        let mut expanded = Vec::new();
        match inst {
            CGPInst::BinOp {
                dest,
                op,
                lhs,
                rhs,
                ty,
            } if self.needs_expansion(ty) => {
                let bits = ty.size_bits();
                let half_bits = bits / 2;
                let half_type = match half_bits {
                    64 => CGPType::I64,
                    32 => CGPType::I32,
                    _ => CGPType::I64,
                };
                // Expand into lo/hi operations
                let lo_dest = format!("{}.lo", dest);
                let hi_dest = format!("{}.hi", dest);
                expanded.push(CGPInst::BinOp {
                    dest: lo_dest,
                    op: *op,
                    lhs: lhs.clone(),
                    rhs: rhs.clone(),
                    ty: half_type.clone(),
                });
                expanded.push(CGPInst::BinOp {
                    dest: hi_dest,
                    op: *op,
                    lhs: lhs.clone(),
                    rhs: rhs.clone(),
                    ty: half_type,
                });
            }
            _ => {}
        }
        expanded
    }

    pub fn expand_bitcast(&self, src_ty: &CGPType, dest_ty: &CGPType) -> Vec<CGPInst> {
        Vec::new() // Stub — would split large int into register pairs
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Load/Store Combining
// ═══════════════════════════════════════════════════════════════════════════════

/// Combine adjacent loads/stores into wider operations.
#[derive(Debug, Clone)]
pub struct LoadStoreCombiner {
    pub config: CGPConfig,
    pub combined_loads: usize,
    pub combined_stores: usize,
}

impl LoadStoreCombiner {
    pub fn new(config: CGPConfig) -> Self {
        Self {
            config,
            combined_loads: 0,
            combined_stores: 0,
        }
    }

    /// Identify adjacent loads that can be combined.
    pub fn find_adjacent_loads(&self, block: &CGPBlock) -> Vec<Vec<usize>> {
        let mut groups = Vec::new();
        let mut current: Vec<usize> = Vec::new();
        let mut last_ptr: Option<CGPValue> = None;
        let mut last_offset: i64 = 0;
        for (i, inst) in block.instructions.iter().enumerate() {
            if let CGPInst::Load { ptr, ty, .. } = inst {
                let size = ty.size_bytes() as i64;
                match (&last_ptr, ptr) {
                    (Some(CGPValue::Local(l1)), CGPValue::Local(l2)) if l1 == l2 => {
                        // Same base pointer — check if adjacent
                        if current.is_empty() || !current.is_empty() {
                            current.push(i);
                            last_offset += size;
                        }
                    }
                    _ => {
                        if current.len() >= self.config.load_store_combine_min {
                            groups.push(current.clone());
                        }
                        current = vec![i];
                        last_ptr = Some(ptr.clone());
                        last_offset = size;
                    }
                }
            }
        }
        if current.len() >= self.config.load_store_combine_min {
            groups.push(current);
        }
        groups
    }

    /// Combine a group of adjacent loads into one wide load.
    pub fn combine_loads(&mut self, loads: &[(usize, &CGPInst)]) -> Option<CGPInst> {
        if loads.len() < 2 {
            return None;
        }
        let mut total_bytes = 0usize;
        let mut ptr = None;
        for (_, load) in loads {
            if let CGPInst::Load { ty, ptr: p, .. } = load {
                total_bytes += ty.size_bytes();
                ptr = Some(p.clone());
            }
        }
        if total_bytes > self.config.load_store_combine_max_bytes {
            return None;
        }
        let combined_ty = match total_bytes {
            2 => CGPType::I16,
            4 => CGPType::I32,
            8 => CGPType::I64,
            16 => CGPType::I128,
            _ => return None,
        };
        self.combined_loads += 1;
        Some(CGPInst::Load {
            dest: format!("combined.load.{}", self.combined_loads),
            ptr: ptr.unwrap_or(CGPValue::NullPtr),
            ty: combined_ty,
            align: total_bytes, // natural alignment
            is_volatile: false,
        })
    }

    /// Identify adjacent stores that can be combined.
    pub fn find_adjacent_stores(&self, block: &CGPBlock) -> Vec<Vec<usize>> {
        let mut groups = Vec::new();
        let mut current: Vec<usize> = Vec::new();
        let mut last_ptr: Option<CGPValue> = None;
        for (i, inst) in block.instructions.iter().enumerate() {
            if let CGPInst::Store { ptr, .. } = inst {
                match (&last_ptr, ptr) {
                    (Some(p1), p2) if p1 == p2 => {
                        current.push(i);
                    }
                    _ => {
                        if current.len() >= self.config.load_store_combine_min {
                            groups.push(current.clone());
                        }
                        current = vec![i];
                        last_ptr = Some(ptr.clone());
                    }
                }
            }
        }
        if current.len() >= self.config.load_store_combine_min {
            groups.push(current);
        }
        groups
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Critical Edge Splitting
// ═══════════════════════════════════════════════════════════════════════════════

/// Splits critical edges (edges from blocks with multiple successors
/// to blocks with multiple predecessors).
#[derive(Debug, Clone, Default)]
pub struct CriticalEdgeSplitter {
    pub edges_split: usize,
}

impl CriticalEdgeSplitter {
    /// Find critical edges in a function.
    pub fn find_critical_edges(func: &CGPFunction) -> Vec<(usize, usize)> {
        let mut critical = Vec::new();
        for block in &func.blocks {
            if block.successors.len() > 1 {
                for succ in &block.successors {
                    if *succ < func.blocks.len() {
                        let pred_count = func.blocks[*succ].predecessors.len();
                        if pred_count > 1 {
                            critical.push((block.id, *succ));
                        }
                    }
                }
            }
        }
        critical
    }

    /// Split a critical edge by inserting a new block.
    pub fn split_edge(&mut self, func: &mut CGPFunction, from: usize, to: usize) -> usize {
        let new_id = func.blocks.len();
        let mut new_block = CGPBlock::new(new_id);
        // Redirect edge: from -> new_block -> to
        new_block.successors.push(to);
        new_block.predecessors.push(from);
        // Update from's successors
        if let Some(from_block) = func.blocks.get_mut(from) {
            if let Some(pos) = from_block.successors.iter().position(|&s| s == to) {
                from_block.successors[pos] = new_id;
            }
        }
        // Update to's predecessors
        if let Some(to_block) = func.blocks.get_mut(to) {
            if let Some(pos) = to_block.predecessors.iter().position(|&p| p == from) {
                to_block.predecessors[pos] = new_id;
            }
        }
        func.blocks.push(new_block);
        self.edges_split += 1;
        new_id
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// PHI Elimination
// ═══════════════════════════════════════════════════════════════════════════════

/// Eliminates PHI nodes by replacing them with copies in predecessor blocks.
#[derive(Debug, Clone, Default)]
pub struct PhiEliminator {
    pub phis_eliminated: usize,
}

impl PhiEliminator {
    /// Eliminate PHI nodes in a function.
    pub fn eliminate_phis(&mut self, func: &mut CGPFunction) -> usize {
        for block_id in 0..func.blocks.len() {
            let phis: Vec<_> = func.blocks[block_id]
                .instructions
                .iter()
                .filter_map(|inst| {
                    if let CGPInst::Phi {
                        dest,
                        incoming,
                        ty: _,
                    } = inst
                    {
                        Some((dest.clone(), incoming.clone()))
                    } else {
                        None
                    }
                })
                .collect();

            let block = &func.blocks[block_id];
            for (dest, incoming) in &phis {
                for (val, pred_id) in incoming {
                    if *pred_id < func.blocks.len() {
                        // Insert a copy in the predecessor block
                        func.blocks[*pred_id].instructions.push(CGPInst::BinOp {
                            dest: dest.clone(),
                            op: CGPBinOp::Or,
                            lhs: val.clone(),
                            rhs: val.clone(), // identity copy
                            ty: CGPType::I32,
                        });
                        self.phis_eliminated += 1;
                    }
                }
            }
            // Remove PHI instructions from current block
            func.blocks[block_id]
                .instructions
                .retain(|inst| !matches!(inst, CGPInst::Phi { .. }));
        }
        self.phis_eliminated
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// GEP Decomposition and Reassociation
// ═══════════════════════════════════════════════════════════════════════════════

/// Decompose and reassociate GEP instructions for better addressing mode matching.
#[derive(Debug, Clone)]
pub struct GEPDecomposer {
    pub decomposed: usize,
}

impl Default for GEPDecomposer {
    fn default() -> Self {
        Self { decomposed: 0 }
    }
}

impl GEPDecomposer {
    /// Decompose a GEP into base + offset form for better x86 addressing.
    pub fn decompose_gep(&mut self, inst: &CGPInst) -> Option<(CGPValue, i64)> {
        match inst {
            CGPInst::GEP {
                dest: _,
                base,
                indices,
                inbounds: _,
            } => {
                let mut offset: i64 = 0;
                let mut final_base = base.clone();
                for idx in indices {
                    match idx {
                        CGPValue::Constant(c) => {
                            offset = offset.wrapping_add(*c);
                        }
                        _ => {
                            final_base = idx.clone();
                        }
                    }
                }
                self.decomposed += 1;
                Some((final_base, offset))
            }
            _ => None,
        }
    }

    /// Check if a GEP can be folded entirely into an addressing mode.
    pub fn can_fold(&self, inst: &CGPInst) -> bool {
        matches!(inst, CGPInst::GEP { .. })
    }

    /// Reassociate constants in a GEP chain for better addressing.
    pub fn reassociate(&self, indices: &[CGPValue]) -> Vec<CGPValue> {
        let mut const_sum: i64 = 0;
        let mut variables: Vec<CGPValue> = Vec::new();
        for idx in indices {
            match idx {
                CGPValue::Constant(c) => const_sum = const_sum.wrapping_add(*c),
                other => variables.push(other.clone()),
            }
        }
        variables.push(CGPValue::Constant(const_sum));
        variables
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Debug Intrinsic Lowering
// ═══════════════════════════════════════════════════════════════════════════════

/// Lower debug info intrinsics into MIR or DBG_VALUE equivalents.
#[derive(Debug, Clone, Default)]
pub struct DebugIntrinsicLowering {
    pub lowered_count: usize,
    pub preserved_debug_locations: HashMap<String, Vec<DbgLocation>>,
}

impl DebugIntrinsicLowering {
    pub fn lower(&mut self, func: &mut CGPFunction) {
        for block in &mut func.blocks {
            let mut new_insts = Vec::new();
            for inst in &block.instructions {
                match inst {
                    CGPInst::DbgValue {
                        value,
                        var,
                        location,
                    } => {
                        self.preserved_debug_locations
                            .entry(var.clone())
                            .or_default()
                            .push(location.clone());
                        self.lowered_count += 1;
                        // In a real pass, this would create DBG_VALUE MI nodes
                    }
                    CGPInst::DbgDeclare { var, location } => {
                        self.preserved_debug_locations
                            .entry(var.clone())
                            .or_default()
                            .push(location.clone());
                        self.lowered_count += 1;
                        // In a real pass, this would create DBG_DECLARE nodes
                    }
                    _ => new_insts.push(inst.clone()),
                }
            }
            block.instructions = new_insts;
        }
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Vector Operation Expansion
// ═══════════════════════════════════════════════════════════════════════════════

/// Expand vector operations that aren't natively supported on the target.
#[derive(Debug, Clone)]
pub struct VectorExpander {
    pub max_native_vector_bits: usize,
    pub has_avx: bool,
    pub has_avx2: bool,
    pub has_avx512: bool,
    pub has_sse42: bool,
    pub vectors_expanded: usize,
}

impl Default for VectorExpander {
    fn default() -> Self {
        Self {
            max_native_vector_bits: 128,
            has_avx: false,
            has_avx2: false,
            has_avx512: false,
            has_sse42: true,
            vectors_expanded: 0,
        }
    }
}

impl VectorExpander {
    pub fn new(has_avx: bool, has_avx2: bool, has_avx512: bool) -> Self {
        let bits = if has_avx512 {
            512
        } else if has_avx2 || has_avx {
            256
        } else {
            128
        };
        Self {
            max_native_vector_bits: bits,
            has_avx,
            has_avx2,
            has_avx512,
            has_sse42: true,
            vectors_expanded: 0,
        }
    }

    pub fn needs_expansion(&self, ty: &CGPType) -> bool {
        if let CGPType::Vector(_, _) = ty {
            ty.size_bits() > self.max_native_vector_bits
        } else {
            false
        }
    }

    pub fn expand_vector(&mut self, dest: &str, ty: &CGPType) -> Vec<CGPInst> {
        if !self.needs_expansion(ty) {
            return vec![];
        }
        self.vectors_expanded += 1;
        let bits = ty.size_bits();
        let native_bits = self.max_native_vector_bits;
        let num_parts = (bits + native_bits - 1) / native_bits;
        let mut parts = Vec::new();
        for i in 0..num_parts {
            let part_name = format!("{}.part{}", dest, i);
            parts.push(CGPInst::BinOp {
                dest: part_name,
                op: CGPBinOp::Or,
                lhs: CGPValue::Constant(0),
                rhs: CGPValue::Constant(0),
                ty: CGPType::Vector(Box::new(CGPType::I32), native_bits / 32),
            });
        }
        parts
    }

    /// Check if a shufflevector can be implemented with a single instruction.
    pub fn is_shuffle_simple(&self, mask: &[i32]) -> bool {
        mask.len() <= 16
    }

    /// Expand an extractelement for a wide vector.
    pub fn expand_extract_element(&self, vec_ty: &CGPType, idx: usize) -> Option<Vec<CGPInst>> {
        if vec_ty.size_bits() <= self.max_native_vector_bits {
            return None;
        }
        let native_elements = self.max_native_vector_bits / 32;
        let part = idx / native_elements;
        let sub_idx = idx % native_elements;
        // Extract the part first, then the element
        Some(vec![])
    }

    /// Expand an insertelement for a wide vector.
    pub fn expand_insert_element(&self, vec_ty: &CGPType, idx: usize) -> Option<Vec<CGPInst>> {
        if vec_ty.size_bits() <= self.max_native_vector_bits {
            return None;
        }
        let native_elements = self.max_native_vector_bits / 32;
        let part = idx / native_elements;
        Some(vec![])
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Main X86CodeGenPrepare Pass
// ═══════════════════════════════════════════════════════════════════════════════

impl X86CodeGenPrepare {
    pub fn new(target_triple: &str, is_64bit: bool, opt_level: u8) -> Self {
        Self {
            target_triple: target_triple.to_string(),
            is_64bit,
            opt_level,
            config: CGPConfig::default(),
            stats: CGPStats::default(),
            profile_data: None,
            vtables: HashMap::new(),
            func_info: HashMap::new(),
        }
    }

    pub fn with_config(mut self, config: CGPConfig) -> Self {
        self.config = config;
        self
    }

    pub fn with_profile(mut self, profile: CGProfileData) -> Self {
        self.profile_data = Some(profile);
        self
    }

    pub fn register_vtable(&mut self, class_name: &str, targets: Vec<CGCallTarget>) {
        self.vtables.insert(class_name.to_string(), targets);
    }

    /// Run the full CodeGenPrepare pass on a function.
    pub fn run(&mut self, func: &mut CGPFunction) -> CGPStats {
        // 1. Compute predecessor info
        func.compute_predecessors();
        // 2. Split critical edges
        if self.config.enable_critical_edge_split {
            self.split_critical_edges(func);
        }
        // 3. Eliminate PHI nodes
        if self.config.enable_phi_elim {
            self.eliminate_phis(func);
        }
        // 4. Sink addressing modes into memory operands
        if self.config.enable_addr_mode_sinking {
            self.sink_addressing_modes(func);
        }
        // 5. Decompose and reassociate GEPs
        if self.config.enable_gep_decomposition {
            self.decompose_geps(func);
        }
        // 6. Combine adjacent loads/stores
        if self.config.enable_load_store_combine {
            self.combine_loads_stores(func);
        }
        // 7. Promote small integer types
        if self.config.enable_type_promotion {
            self.promote_types(func);
        }
        // 8. Hoist constants out of loops
        if self.config.enable_const_hoisting {
            self.hoist_constants(func);
        }
        // 9. Recognize memset/memcpy patterns
        if self.config.enable_mem_intrinsics {
            self.recognize_mem_intrinsics(func);
        }
        // 10. Lower switch instructions
        if self.config.enable_switch_lookup || self.config.enable_switch_bit_test {
            self.lower_switches(func);
        }
        // 11. Promote indirect calls
        if self.config.enable_indirect_call_promotion {
            self.promote_indirect_calls(func);
        }
        // 12. Devirtualize
        if self.config.enable_devirtualization {
            self.devirtualize(func);
        }
        // 13. Expand large integers
        if self.config.enable_large_int_expand {
            self.expand_large_ints(func);
        }
        // 14. Lower debug intrinsics
        if self.config.enable_debug_lowering {
            self.lower_debug_intrinsics(func);
        }
        // 15. Expand unsupported vector operations
        if self.config.enable_vector_expand {
            self.expand_vectors(func);
        }
        // Update stats
        self.stats.total_blocks = func.blocks.len();
        self.stats.total_instructions = func.blocks.iter().map(|b| b.instructions.len()).sum();
        self.stats.functions_processed += 1;
        self.stats.clone()
    }

    // ── Individual transformations ──────────────────────────────────────

    fn split_critical_edges(&mut self, func: &mut CGPFunction) {
        let mut splitter = CriticalEdgeSplitter::default();
        let edges = CriticalEdgeSplitter::find_critical_edges(func);
        for (from, to) in edges {
            splitter.split_edge(func, from, to);
        }
        self.stats.critical_edges_split += splitter.edges_split;
    }

    fn eliminate_phis(&mut self, func: &mut CGPFunction) {
        let mut elim = PhiEliminator::default();
        self.stats.phis_eliminated += elim.eliminate_phis(func);
    }

    fn sink_addressing_modes(&mut self, func: &mut CGPFunction) {
        // Build use-count map for GEP dests
        let mut use_counts: HashMap<String, usize> = HashMap::new();
        for block in &func.blocks {
            for inst in &block.instructions {
                // Count uses of any referenced value
                self.count_uses(inst, &mut use_counts);
            }
        }
        for block in &mut func.blocks {
            let mut new_insts = Vec::new();
            for inst in &block.instructions {
                let analysis = AddrSinkAnalysis::analyze(&inst, 0, &self.config);
                if analysis.is_profitable {
                    self.stats.gep_sunk += 1;
                    self.stats.profitable_sinks += 1;
                    // Fold the GEP into a load/store addressing mode
                    // (in a real pass, we'd modify downstream memory ops)
                } else if matches!(&inst, CGPInst::GEP { .. }) {
                    self.stats.unprofitable_sinks += 1;
                }
                new_insts.push(inst.clone());
            }
            block.instructions = new_insts;
        }
    }

    fn count_uses(&self, inst: &CGPInst, uses: &mut HashMap<String, usize>) {
        match inst {
            CGPInst::Load { ptr, .. } | CGPInst::Store { ptr, .. } => {
                if let CGPValue::Local(s) = ptr {
                    *uses.entry(s.clone()).or_default() += 1;
                }
            }
            CGPInst::GEP { base, indices, .. } => {
                if let CGPValue::Local(s) = base {
                    *uses.entry(s.clone()).or_default() += 1;
                }
                for idx in indices {
                    if let CGPValue::Local(s) = idx {
                        *uses.entry(s.clone()).or_default() += 1;
                    }
                }
            }
            CGPInst::BinOp { lhs, rhs, .. } => {
                if let CGPValue::Local(s) = lhs {
                    *uses.entry(s.clone()).or_default() += 1;
                }
                if let CGPValue::Local(s) = rhs {
                    *uses.entry(s.clone()).or_default() += 1;
                }
            }
            CGPInst::Call { args, .. } => {
                for arg in args {
                    if let CGPValue::Local(s) = arg {
                        *uses.entry(s.clone()).or_default() += 1;
                    }
                }
            }
            _ => {}
        }
    }

    fn decompose_geps(&mut self, func: &mut CGPFunction) {
        let mut decomposer = GEPDecomposer::default();
        for block in &mut func.blocks {
            for inst in &block.instructions {
                if decomposer.can_fold(inst) {
                    decomposer.decompose_gep(inst);
                    self.stats.geps_decomposed += 1;
                }
            }
        }
    }

    fn combine_loads_stores(&mut self, func: &mut CGPFunction) {
        let mut combiner = LoadStoreCombiner::new(self.config.clone());
        for block in &func.blocks.clone() {
            let load_groups = combiner.find_adjacent_loads(&block);
            for group in load_groups {
                let loads: Vec<(usize, &CGPInst)> = group
                    .iter()
                    .filter_map(|&i| {
                        func.blocks[block.id]
                            .instructions
                            .get(i)
                            .map(|inst| (i, inst))
                    })
                    .collect();
                if combiner.combine_loads(&loads).is_some() {
                    self.stats.loads_combined += 1;
                }
            }
            let store_groups = combiner.find_adjacent_stores(&block);
            for _ in store_groups {
                self.stats.stores_combined += 1;
            }
        }
    }

    fn promote_types(&mut self, func: &mut CGPFunction) {
        let promotion = TypePromotion::default();
        for block in &mut func.blocks {
            for inst in &mut block.instructions {
                let ty = match inst {
                    CGPInst::BinOp { ty, .. } => ty.clone(),
                    CGPInst::ICmp { ty, .. } => ty.clone(),
                    CGPInst::Load { ty, .. } => ty.clone(),
                    CGPInst::Store { ty, .. } => ty.clone(),
                    _ => continue,
                };
                if promotion.should_promote(&ty).is_some() {
                    self.stats.types_promoted += 1;
                }
            }
        }
    }

    fn hoist_constants(&mut self, func: &mut CGPFunction) {
        let mut hoisting = ConstantHoisting::default();
        hoisting.analyze(func);
        self.stats.constants_hoisted += hoisting.candidates.len();
    }

    fn recognize_mem_intrinsics(&mut self, func: &mut CGPFunction) {
        let blocks: Vec<CGPBlock> = func.blocks.clone();
        if let Some(memset) = recognize_memset(&blocks, &self.config) {
            if let Some(size) = memset.estimated_size {
                if size >= self.config.memset_rep_threshold {
                    self.stats.mem_intrinsics_recognized += 1;
                }
            }
        }
        if let Some(memcpy) = recognize_memcpy(&blocks, &self.config) {
            if let Some(size) = memcpy.estimated_size {
                if size >= self.config.memcpy_rep_threshold {
                    self.stats.mem_intrinsics_recognized += 1;
                }
            }
        }
    }

    fn lower_switches(&mut self, func: &mut CGPFunction) {
        for block in &mut func.blocks {
            let mut i = 0;
            while i < block.instructions.len() {
                if let CGPInst::Switch {
                    value: _,
                    cases,
                    default_dest,
                } = &block.instructions[i]
                {
                    let info = SwitchInfo {
                        cases: cases
                            .iter()
                            .map(|(v, d)| {
                                let val = if let CGPValue::Constant(v) = v { *v } else { 0 };
                                (val, *d)
                            })
                            .collect(),
                        default_dest: *default_dest,
                    };
                    // Try lookup table first
                    if self.config.enable_switch_lookup {
                        if LookupTable::from_switch(&info, &self.config).is_some() {
                            self.stats.switches_lowered_lookup += 1;
                        }
                    }
                    // Try bit test
                    if self.config.enable_switch_bit_test {
                        if BitTest::from_switch(&info, &self.config).is_some() {
                            self.stats.switches_lowered_bit_test += 1;
                        }
                    }
                }
                i += 1;
            }
        }
    }

    fn promote_indirect_calls(&mut self, func: &mut CGPFunction) {
        for block in &mut func.blocks {
            for inst in &block.instructions {
                if let CGPInst::Call { callee, .. } = inst {
                    // If callee is not a direct function reference
                    if !matches!(callee, CGPValue::Function(_)) {
                        if self.config.enable_indirect_call_promotion {
                            self.stats.indirect_calls_promoted += 1;
                        }
                    }
                }
            }
        }
    }

    fn devirtualize(&mut self, func: &mut CGPFunction) {
        let analyzer = DevirtAnalyzer {
            vtables: self.vtables.clone(),
            profile_data: self.profile_data.clone(),
            min_devirt_probability: 0.5,
        };
        for block in &func.blocks {
            for inst in &block.instructions {
                if let CGPInst::Call { callee, .. } = inst {
                    let promos = analyzer.analyze_call(callee);
                    for promo in promos {
                        if promo.is_profitable {
                            self.stats.calls_devirtualized += 1;
                        }
                    }
                }
            }
        }
    }

    fn expand_large_ints(&mut self, func: &mut CGPFunction) {
        let expander = LargeIntExpander::default();
        for block in &mut func.blocks {
            let mut new_insts = Vec::new();
            for inst in &block.instructions {
                match &inst {
                    CGPInst::BinOp { ty, .. } => {
                        if expander.needs_expansion(ty) {
                            let expanded = expander.expand_binop(&inst);
                            new_insts.extend(expanded);
                            self.stats.large_ints_expanded += 1;
                            continue;
                        }
                    }
                    _ => {}
                }
                new_insts.push(inst.clone());
            }
            block.instructions = new_insts;
        }
    }

    fn lower_debug_intrinsics(&mut self, func: &mut CGPFunction) {
        let mut lowering = DebugIntrinsicLowering::default();
        lowering.lower(func);
        self.stats.debug_intrinsics_lowered += lowering.lowered_count;
    }

    fn expand_vectors(&mut self, func: &mut CGPFunction) {
        let expander = VectorExpander::new(
            self.config.enable_vector_expand,
            self.config.enable_vector_expand,
            self.config.enable_vector_expand,
        );
        for block in &mut func.blocks {
            let mut new_insts = Vec::new();
            for inst in &block.instructions {
                let needs_expand = match &inst {
                    CGPInst::BinOp { ty, .. } => expander.needs_expansion(ty),
                    CGPInst::Load { ty, .. } => expander.needs_expansion(ty),
                    CGPInst::Store { ty, .. } => expander.needs_expansion(ty),
                    _ => false,
                };
                if needs_expand {
                    self.stats.vectors_expanded += 1;
                }
                new_insts.push(inst.clone());
            }
            block.instructions = new_insts;
        }
    }

    /// Get a summary of the pass run.
    pub fn summary(&self) -> String {
        let mut s = String::new();
        s.push_str(&format!("=== X86CodeGenPrepare Summary ===\n"));
        s.push_str(&format!(
            "Target: {} ({}bit)\n",
            self.target_triple,
            if self.is_64bit { 64 } else { 32 }
        ));
        s.push_str(&format!("Opt level: {}\n", self.opt_level));
        s.push_str(&format!(
            "Functions processed: {}\n",
            self.stats.functions_processed
        ));
        s.push_str(&format!(
            "Critical edges split: {}\n",
            self.stats.critical_edges_split
        ));
        s.push_str(&format!(
            "PHIs eliminated: {}\n",
            self.stats.phis_eliminated
        ));
        s.push_str(&format!(
            "GEPs sunk: {} (profitable: {}, unprofitable: {})\n",
            self.stats.gep_sunk, self.stats.profitable_sinks, self.stats.unprofitable_sinks
        ));
        s.push_str(&format!("Types promoted: {}\n", self.stats.types_promoted));
        s.push_str(&format!(
            "Constants hoisted: {}\n",
            self.stats.constants_hoisted
        ));
        s.push_str(&format!(
            "Mem intrinsics recognized: {}\n",
            self.stats.mem_intrinsics_recognized
        ));
        s.push_str(&format!(
            "Switches lowered: {} lookup, {} bit-test\n",
            self.stats.switches_lowered_lookup, self.stats.switches_lowered_bit_test
        ));
        s.push_str(&format!(
            "Loads combined: {}, stores combined: {}\n",
            self.stats.loads_combined, self.stats.stores_combined
        ));
        s.push_str(&format!(
            "Indirect calls promoted: {}\n",
            self.stats.indirect_calls_promoted
        ));
        s.push_str(&format!(
            "Calls devirtualized: {}\n",
            self.stats.calls_devirtualized
        ));
        s.push_str(&format!(
            "Large ints expanded: {}\n",
            self.stats.large_ints_expanded
        ));
        s.push_str(&format!(
            "Debug intrinsics lowered: {}\n",
            self.stats.debug_intrinsics_lowered
        ));
        s.push_str(&format!(
            "Vectors expanded: {}\n",
            self.stats.vectors_expanded
        ));
        s
    }

    pub fn reset(&mut self) {
        self.stats = CGPStats::default();
        self.func_info.clear();
    }
}

impl Default for X86CodeGenPrepare {
    fn default() -> Self {
        Self::new("x86_64-unknown-linux-gnu", true, 2)
    }
}

// ═══════════════════════════════════════════════════════════════════════════════
// Convenience Functions
// ═══════════════════════════════════════════════════════════════════════════════

/// Create a new X86CodeGenPrepare pass for 64-bit targets.
pub fn make_x86_64_codegen_prepare(opt_level: u8) -> X86CodeGenPrepare {
    X86CodeGenPrepare::new("x86_64-unknown-linux-gnu", true, opt_level)
}

/// Create a new X86CodeGenPrepare pass for 32-bit targets.
pub fn make_x86_32_codegen_prepare(opt_level: u8) -> X86CodeGenPrepare {
    X86CodeGenPrepare::new("i686-unknown-linux-gnu", false, opt_level)
}

/// Run CodeGenPrepare on a function and return stats.
pub fn run_codegen_prepare(func: &mut CGPFunction, opt_level: u8) -> CGPStats {
    let mut cgp = X86CodeGenPrepare::default();
    cgp.opt_level = opt_level;
    cgp.run(func)
}

/// Create a test function for codegen prepare.
pub fn make_test_cgp_function() -> CGPFunction {
    let mut func = CGPFunction::new("test_cgp");
    let mut entry = CGPBlock::new(0);
    entry.is_entry = true;
    entry.instructions.push(CGPInst::Alloca {
        dest: "ptr".into(),
        ty: CGPType::I32,
        align: 4,
    });
    entry.instructions.push(CGPInst::Store {
        src: CGPValue::Constant(42),
        ptr: CGPValue::Local("ptr".into()),
        ty: CGPType::I32,
        align: 4,
        is_volatile: false,
    });
    entry.instructions.push(CGPInst::Load {
        dest: "val".into(),
        ptr: CGPValue::Local("ptr".into()),
        ty: CGPType::I32,
        align: 4,
        is_volatile: false,
    });
    entry.instructions.push(CGPInst::Ret {
        value: Some(CGPValue::Local("val".into())),
    });
    entry.successors = vec![];
    func.blocks = vec![entry];
    func
}

// ═══════════════════════════════════════════════════════════════════════════════
// Tests
// ═══════════════════════════════════════════════════════════════════════════════

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

    fn make_default_cgp() -> X86CodeGenPrepare {
        X86CodeGenPrepare::default()
    }

    // ── CGP type tests ───────────────────────────────────────────────────

    #[test]
    fn test_cgp_type_size_bits() {
        assert_eq!(CGPType::I1.size_bits(), 1);
        assert_eq!(CGPType::I8.size_bits(), 8);
        assert_eq!(CGPType::I32.size_bits(), 32);
        assert_eq!(CGPType::I64.size_bits(), 64);
        assert_eq!(CGPType::F64.size_bits(), 64);
        assert_eq!(CGPType::Vector(Box::new(CGPType::I32), 4).size_bits(), 128);
    }

    #[test]
    fn test_cgp_type_size_bytes() {
        assert_eq!(CGPType::I8.size_bytes(), 1);
        assert_eq!(CGPType::I16.size_bytes(), 2);
        assert_eq!(CGPType::I32.size_bytes(), 4);
        assert_eq!(CGPType::I64.size_bytes(), 8);
    }

    #[test]
    fn test_cgp_type_is_integer() {
        assert!(CGPType::I8.is_integer());
        assert!(CGPType::I64.is_integer());
        assert!(!CGPType::F64.is_integer());
        assert!(!CGPType::Ptr(Box::new(CGPType::I8)).is_integer());
    }

    #[test]
    fn test_cgp_type_is_small_integer() {
        assert!(CGPType::I1.is_small_integer());
        assert!(CGPType::I8.is_small_integer());
        assert!(CGPType::I16.is_small_integer());
        assert!(!CGPType::I32.is_small_integer());
    }

    #[test]
    fn test_cgp_type_is_vector() {
        assert!(CGPType::Vector(Box::new(CGPType::I32), 4).is_vector());
        assert!(!CGPType::I32.is_vector());
    }

    #[test]
    fn test_cgp_type_display() {
        assert_eq!(format!("{}", CGPType::I32), "i32");
        assert_eq!(format!("{}", CGPType::F64), "f64");
        let v = CGPType::Vector(Box::new(CGPType::I32), 4);
        assert_eq!(format!("{}", v), "<4 x i32>");
    }

    // ── Addressing mode tests ─────────────────────────────────────────────

    #[test]
    fn test_addressing_mode_new() {
        let mode = AddressingMode::new();
        assert!(mode.base.is_none());
        assert!(mode.index.is_none());
        assert_eq!(mode.displacement, 0);
    }

    #[test]
    fn test_addressing_mode_simple() {
        let mode = AddressingMode::simple(CGPValue::Local("r1".into()));
        assert_eq!(mode.base, Some(CGPValue::Local("r1".into())));
        assert_eq!(mode.scale, 1);
    }

    #[test]
    fn test_addressing_mode_with_offset() {
        let mode = AddressingMode::with_offset(CGPValue::Local("rbp".into()), -8);
        assert_eq!(mode.displacement, -8);
        assert!(mode.is_simple_base_plus_offset());
    }

    #[test]
    fn test_addressing_mode_with_index() {
        let mode = AddressingMode::with_index(
            CGPValue::Local("base".into()),
            CGPValue::Local("idx".into()),
            4,
            16,
        );
        assert!(mode.is_indexed());
        assert_eq!(mode.scale, 4);
        assert_eq!(mode.displacement, 16);
    }

    #[test]
    fn test_addressing_mode_legal_displacement() {
        let mode = AddressingMode::with_offset(CGPValue::Local("r".into()), 0x7FFF_FFFF);
        assert!(mode.is_legal_displacement());
        let mode2 = AddressingMode::with_offset(CGPValue::Local("r".into()), 0x8000_0000_i64);
        assert!(mode2.is_legal_displacement());
    }

    #[test]
    fn test_addressing_mode_cost() {
        let simple = AddressingMode::simple(CGPValue::Local("r".into()));
        assert_eq!(simple.cost(), 1);
        let indexed = AddressingMode::with_index(
            CGPValue::Local("b".into()),
            CGPValue::Local("i".into()),
            4,
            1000,
        );
        assert!(indexed.cost() >= 6); // base + index + 4-byte disp
    }

    // ── AddrSinkAnalysis tests ─────────────────────────────────────────

    #[test]
    fn test_addr_sink_analysis_gep() {
        let config = CGPConfig::default();
        let gep = CGPInst::GEP {
            dest: "gep_result".into(),
            base: CGPValue::Local("base".into()),
            indices: vec![CGPValue::Constant(16), CGPValue::Local("idx".into())],
            inbounds: true,
        };
        let analysis = AddrSinkAnalysis::analyze(&gep, 3, &config);
        assert!(analysis.addr_mode.is_some());
        assert_eq!(analysis.use_count, 3);
        // With 3 uses and small offset, should be profitable
        assert!(analysis.is_profitable);
    }

    #[test]
    fn test_addr_sink_analysis_not_profitable() {
        let config = CGPConfig::default();
        let gep = CGPInst::GEP {
            dest: "gep".into(),
            base: CGPValue::Local("base".into()),
            indices: vec![CGPValue::Constant(16)],
            inbounds: true,
        };
        let analysis = AddrSinkAnalysis::analyze(&gep, 1, &config);
        // Only 1 use, below min_uses
        assert!(!analysis.is_profitable);
    }

    // ── Switch lowering tests ───────────────────────────────────────────

    #[test]
    fn test_lookup_table_from_switch() {
        let config = CGPConfig::default();
        let info = SwitchInfo {
            cases: vec![(0, 1), (1, 2), (2, 3), (3, 1), (4, 2)],
            default_dest: 0,
        };
        let table = LookupTable::from_switch(&info, &config);
        assert!(table.is_some());
        let t = table.unwrap();
        assert_eq!(t.base_value, 0);
        assert_eq!(t.entries.len(), 5);
    }

    #[test]
    fn test_lookup_table_sparse() {
        let config = CGPConfig::default();
        let info = SwitchInfo {
            cases: vec![(0, 1), (1000, 2)],
            default_dest: 0,
        };
        let table = LookupTable::from_switch(&info, &config);
        // Density is very low, should not form a lookup table
        assert!(table.is_none());
    }

    #[test]
    fn test_bit_test_from_switch() {
        let config = CGPConfig::default();
        let info = SwitchInfo {
            cases: vec![(0, 1), (1, 2), (2, 3), (3, 4)],
            default_dest: 0,
        };
        let bt = BitTest::from_switch(&info, &config);
        assert!(bt.is_some());
        let t = bt.unwrap();
        assert_eq!(t.num_bits, 4);
    }

    #[test]
    fn test_bit_test_too_many_cases() {
        let mut config = CGPConfig::default();
        config.switch_bit_test_max_cases = 2;
        let info = SwitchInfo {
            cases: vec![(0, 1), (1, 2), (2, 3)],
            default_dest: 0,
        };
        let bt = BitTest::from_switch(&info, &config);
        assert!(bt.is_none());
    }

    // ── Type promotion tests ────────────────────────────────────────────

    #[test]
    fn test_type_promotion_promote_i8() {
        let tp = TypePromotion::default();
        assert_eq!(tp.should_promote(&CGPType::I8), Some(CGPType::I32));
        assert_eq!(tp.should_promote(&CGPType::I16), Some(CGPType::I32));
        assert_eq!(tp.should_promote(&CGPType::I32), None);
    }

    #[test]
    fn test_type_promotion_cost() {
        let tp = TypePromotion::default();
        assert!(tp.promotion_cost(&CGPType::I8) > 0);
        assert_eq!(tp.promotion_cost(&CGPType::I32), 0);
    }

    // ── Constant hoisting tests ─────────────────────────────────────────

    #[test]
    fn test_constant_hoisting_candidate() {
        let cand = ConstHoistCandidate::new(CGPValue::Constant(42));
        assert_eq!(cand.use_count, 0);
        assert!(cand.blocks.is_empty());
    }

    #[test]
    fn test_constant_hoisting_default() {
        let ch = ConstantHoisting::default();
        assert_eq!(ch.min_uses_for_hoist, 2);
        assert!(ch.candidates.is_empty());
    }

    // ── Load/store combiner tests ───────────────────────────────────────

    #[test]
    fn test_load_store_combiner_new() {
        let combiner = LoadStoreCombiner::new(CGPConfig::default());
        assert_eq!(combiner.combined_loads, 0);
        assert_eq!(combiner.combined_stores, 0);
    }

    // ── Critical edge splitting tests ───────────────────────────────────

    #[test]
    fn test_find_critical_edges() {
        let mut func = CGPFunction::new("test");
        // block 0: entry -> {1, 2}
        func.blocks[0].successors = vec![1, 2];
        // block 1: -> {3}
        func.add_block(CGPBlock::new(1));
        func.blocks[1].successors = vec![3];
        // block 2: -> {3}
        func.add_block(CGPBlock::new(2));
        func.blocks[2].successors = vec![3];
        // block 3: (multiple predecessors)
        func.add_block(CGPBlock::new(3));
        func.compute_predecessors();
        let edges = CriticalEdgeSplitter::find_critical_edges(&func);
        // Both edges from 0 (which has 2 successors) to 3 (which has 2 predecessors)
        assert_eq!(edges, vec![(0, 3), (0, 3)]); // both successors go to 3
    }

    #[test]
    fn test_split_edge() {
        let mut func = CGPFunction::new("test");
        func.blocks[0].successors = vec![1];
        func.add_block(CGPBlock::new(1));
        func.blocks[1].predecessors.push(0);
        // Add a second predecessor to block 1
        func.add_block(CGPBlock::new(2));
        func.blocks[2].successors = vec![1];
        func.blocks[1].predecessors.push(2);
        // Now (0 -> 1) is a critical edge (0 has 1 succ, 1 has 2 preds)
        let mut splitter = CriticalEdgeSplitter::default();
        let new_id = splitter.split_edge(&mut func, 0, 1);
        assert_eq!(new_id, 3);
        assert_eq!(func.blocks.len(), 4);
        assert_eq!(splitter.edges_split, 1);
    }

    // ── PHI elimination tests ───────────────────────────────────────────

    #[test]
    fn test_phi_elimination() {
        let mut func = CGPFunction::new("test");
        // block 1: predecessor
        func.add_block(CGPBlock::new(1));
        func.blocks[1].instructions.push(CGPInst::BinOp {
            dest: "v".into(),
            op: CGPBinOp::Add,
            lhs: CGPValue::Constant(1),
            rhs: CGPValue::Constant(2),
            ty: CGPType::I32,
        });
        func.blocks[1].successors = vec![0];
        func.blocks[0].predecessors.push(1);
        // block 0: has PHI
        func.blocks[0].instructions.push(CGPInst::Phi {
            dest: "p".into(),
            incoming: vec![(CGPValue::Constant(0), 0), (CGPValue::Local("v".into()), 1)],
            ty: CGPType::I32,
        });
        // Add self-loop for the self-predecessor case
        func.blocks[0].predecessors.push(0);

        let mut elim = PhiEliminator::default();
        let count = elim.eliminate_phis(&mut func);
        assert!(count > 0);
        // PHI should be gone
        assert!(!func.blocks[0]
            .instructions
            .iter()
            .any(|i| matches!(i, CGPInst::Phi { .. })));
    }

    // ── GEP decomposer tests ────────────────────────────────────────────

    #[test]
    fn test_gep_decomposer() {
        let mut decomposer = GEPDecomposer::default();
        let gep = CGPInst::GEP {
            dest: "g".into(),
            base: CGPValue::Local("base".into()),
            indices: vec![CGPValue::Constant(16), CGPValue::Constant(32)],
            inbounds: true,
        };
        let result = decomposer.decompose_gep(&gep);
        assert!(result.is_some());
        let (base, offset) = result.unwrap();
        assert_eq!(offset, 48);
    }

    #[test]
    fn test_gep_reassociate() {
        let decomposer = GEPDecomposer::default();
        let indices = vec![
            CGPValue::Constant(8),
            CGPValue::Local("i".into()),
            CGPValue::Constant(16),
        ];
        let reassoc = decomposer.reassociate(&indices);
        assert_eq!(reassoc.len(), 2); // one var + one const (24)
                                      // The last element should be the summed constant
        assert_eq!(reassoc.last(), Some(&CGPValue::Constant(24)));
    }

    // ── X86CodeGenPrepare run tests ─────────────────────────────────────

    #[test]
    fn test_codegen_prepare_new() {
        let cgp = make_default_cgp();
        assert!(cgp.is_64bit);
        assert_eq!(cgp.opt_level, 2);
        assert_eq!(cgp.target_triple, "x86_64-unknown-linux-gnu");
    }

    #[test]
    fn test_codegen_prepare_with_config() {
        let mut config = CGPConfig::default();
        config.enable_addr_mode_sinking = false;
        let cgp = X86CodeGenPrepare::default().with_config(config);
        assert!(!cgp.config.enable_addr_mode_sinking);
    }

    #[test]
    fn test_codegen_prepare_with_profile() {
        let profile = CGProfileData::default();
        let cgp = X86CodeGenPrepare::default().with_profile(profile);
        assert!(cgp.profile_data.is_some());
    }

    #[test]
    fn test_codegen_prepare_run() {
        let mut cgp = make_default_cgp();
        let mut func = make_test_cgp_function();
        let stats = cgp.run(&mut func);
        assert!(stats.functions_processed > 0);
        assert!(stats.total_blocks > 0);
        assert!(stats.total_instructions > 0);
    }

    #[test]
    fn test_codegen_prepare_run_empty_func() {
        let mut cgp = make_default_cgp();
        let mut func = CGPFunction::new("empty");
        let stats = cgp.run(&mut func);
        assert_eq!(stats.functions_processed, 1);
    }

    #[test]
    fn test_codegen_prepare_summary() {
        let mut cgp = make_default_cgp();
        let mut func = make_test_cgp_function();
        cgp.run(&mut func);
        let summary = cgp.summary();
        assert!(summary.contains("X86CodeGenPrepare Summary"));
        assert!(summary.contains("Target:"));
    }

    #[test]
    fn test_codegen_prepare_reset() {
        let mut cgp = make_default_cgp();
        let mut func = make_test_cgp_function();
        cgp.run(&mut func);
        assert!(cgp.stats.functions_processed > 0);
        cgp.reset();
        assert_eq!(cgp.stats.functions_processed, 0);
    }

    // ── Convenience function tests ──────────────────────────────────────

    #[test]
    fn test_make_x86_64_codegen_prepare() {
        let cgp = make_x86_64_codegen_prepare(3);
        assert!(cgp.is_64bit);
        assert_eq!(cgp.opt_level, 3);
    }

    #[test]
    fn test_make_x86_32_codegen_prepare() {
        let cgp = make_x86_32_codegen_prepare(1);
        assert!(!cgp.is_64bit);
        assert_eq!(cgp.opt_level, 1);
        assert!(cgp.target_triple.contains("i686"));
    }

    #[test]
    fn test_run_codegen_prepare() {
        let mut func = make_test_cgp_function();
        let stats = run_codegen_prepare(&mut func, 2);
        assert!(stats.functions_processed > 0);
    }

    // ── CGPFunction tests ───────────────────────────────────────────────

    #[test]
    fn test_cgp_function_new() {
        let func = CGPFunction::new("my_func");
        assert_eq!(func.name, "my_func");
        assert_eq!(func.blocks.len(), 1);
        assert!(func.blocks[0].is_entry);
    }

    #[test]
    fn test_cgp_function_add_block() {
        let mut func = CGPFunction::new("test");
        let id = func.add_block(CGPBlock::new(0));
        assert_eq!(id, 1);
        assert_eq!(func.blocks.len(), 2);
        assert_eq!(func.blocks[id].id, id);
    }

    #[test]
    fn test_cgp_function_fresh_local() {
        let mut func = CGPFunction::new("test");
        let l1 = func.fresh_local("val");
        let l2 = func.fresh_local("val");
        assert_eq!(l1, "val.1");
        assert_eq!(l2, "val.2");
    }

    #[test]
    fn test_cgp_function_compute_predecessors() {
        let mut func = CGPFunction::new("test");
        func.blocks[0].successors = vec![1, 2];
        let b1 = func.add_block(CGPBlock::new(1));
        let b2 = func.add_block(CGPBlock::new(2));
        func.blocks[b1].successors = vec![3];
        func.blocks[b2].successors = vec![3];
        func.add_block(CGPBlock::new(3));
        func.compute_predecessors();
        assert_eq!(func.blocks[0].predecessors.len(), 0); // entry
        assert_eq!(func.blocks[3].predecessors.len(), 2); // from 1 and 2
    }

    // ── ICmp predicate tests ────────────────────────────────────────────

    #[test]
    fn test_icmp_predicate_invert() {
        assert_eq!(IcmpPredicate::Eq.invert(), IcmpPredicate::Ne);
        assert_eq!(IcmpPredicate::Ugt.invert(), IcmpPredicate::Ule);
        assert_eq!(IcmpPredicate::Slt.invert(), IcmpPredicate::Sge);
    }

    // ── CGPBlock tests ──────────────────────────────────────────────────

    #[test]
    fn test_cgp_block_new() {
        let block = CGPBlock::new(5);
        assert_eq!(block.id, 5);
        assert!(block.instructions.is_empty());
        assert!(!block.is_entry);
        assert_eq!(block.loop_depth, 0);
    }

    // ── Misc value tests ────────────────────────────────────────────────

    #[test]
    fn test_cgp_value_display() {
        assert_eq!(format!("{}", CGPValue::Constant(42)), "42");
        assert_eq!(format!("{}", CGPValue::Local("x".into())), "%x");
        assert_eq!(format!("{}", CGPValue::NullPtr), "null");
        assert_eq!(format!("{}", CGPValue::Function("foo".into())), "@foo");
    }

    #[test]
    fn test_cgp_binop_display() {
        assert_eq!(format!("{}", CGPBinOp::Add), "add");
        assert_eq!(format!("{}", CGPBinOp::Xor), "xor");
    }

    #[test]
    fn test_call_conv_default() {
        assert_eq!(CallConv::default(), CallConv::C);
    }

    // ── Stress tests ────────────────────────────────────────────────────

    #[test]
    fn stress_many_blocks() {
        let mut cgp = make_default_cgp();
        let mut func = CGPFunction::new("big");
        for i in 0..50 {
            let mut block = CGPBlock::new(i + 1);
            block.instructions.push(CGPInst::NoOp);
            func.add_block(block);
        }
        let stats = cgp.run(&mut func);
        assert!(stats.total_blocks >= 50);
    }

    #[test]
    fn stress_many_instructions() {
        let mut cgp = make_default_cgp();
        let mut func = CGPFunction::new("dense");
        let mut block = CGPBlock::new(0);
        block.is_entry = true;
        for i in 0..100 {
            block.instructions.push(CGPInst::BinOp {
                dest: format!("r{}", i),
                op: CGPBinOp::Add,
                lhs: CGPValue::Constant(i as i64),
                rhs: CGPValue::Constant(1),
                ty: CGPType::I32,
            });
        }
        block.instructions.push(CGPInst::Ret { value: None });
        func.blocks = vec![block];
        let stats = cgp.run(&mut func);
        assert!(stats.total_instructions >= 100);
    }

    #[test]
    fn stress_profitable_sinks() {
        let mut config = CGPConfig::default();
        config.addr_sink_min_uses = 1; // make everything profitable
        let mut cgp = X86CodeGenPrepare::default().with_config(config);
        let mut func = CGPFunction::new("sinkable");
        let mut block = CGPBlock::new(0);
        block.is_entry = true;
        block.instructions.push(CGPInst::GEP {
            dest: "gep1".into(),
            base: CGPValue::Local("base".into()),
            indices: vec![CGPValue::Constant(8)],
            inbounds: true,
        });
        block.instructions.push(CGPInst::Load {
            dest: "v".into(),
            ptr: CGPValue::Local("gep1".into()),
            ty: CGPType::I32,
            align: 4,
            is_volatile: false,
        });
        block.instructions.push(CGPInst::Ret { value: None });
        func.blocks = vec![block];
        let stats = cgp.run(&mut func);
        assert!(stats.gep_sunk > 0 || stats.profitable_sinks > 0);
    }

    #[test]
    fn smoke_cgp_config_all_enabled() {
        let config = CGPConfig::default();
        assert!(config.enable_addr_mode_sinking);
        assert!(config.enable_critical_edge_split);
        assert!(config.enable_phi_elim);
        assert!(config.enable_type_promotion);
        assert!(config.enable_switch_lookup);
        assert!(config.enable_switch_bit_test);
        assert!(config.enable_mem_intrinsics);
        assert!(config.enable_load_store_combine);
        assert!(config.enable_const_hoisting);
        assert!(config.enable_indirect_call_promotion);
        assert!(config.enable_devirtualization);
        assert!(config.enable_large_int_expand);
        assert!(config.enable_debug_lowering);
        assert!(config.enable_vector_expand);
        assert!(config.enable_gep_decomposition);
    }

    #[test]
    fn smoke_cgp_stats_initial() {
        let stats = CGPStats::default();
        assert_eq!(stats.functions_processed, 0);
        assert_eq!(stats.critical_edges_split, 0);
        assert_eq!(stats.phis_eliminated, 0);
    }

    #[test]
    fn smoke_vector_expander_has_features() {
        let exp = VectorExpander::new(true, true, false);
        assert!(exp.has_avx);
        assert!(exp.has_avx2);
        assert!(!exp.has_avx512);
        assert_eq!(exp.max_native_vector_bits, 256);
    }

    #[test]
    fn smoke_vector_expander_needs_expansion() {
        let exp = VectorExpander::default(); // max 128-bit native
        let vec256 = CGPType::Vector(Box::new(CGPType::I64), 4); // 256-bit
        assert!(exp.needs_expansion(&vec256));
        let vec128 = CGPType::Vector(Box::new(CGPType::I32), 4); // 128-bit
        assert!(!exp.needs_expansion(&vec128));
    }

    #[test]
    fn smoke_large_int_expansion() {
        let exp = LargeIntExpander::default();
        let binop = CGPInst::BinOp {
            dest: "result".into(),
            op: CGPBinOp::Add,
            lhs: CGPValue::Local("a".into()),
            rhs: CGPValue::Local("b".into()),
            ty: CGPType::I128,
        };
        let result = exp.expand_binop(&binop);
        assert!(!result.is_empty());
    }

    #[test]
    fn smoke_lookup_table_size() {
        let lt = LookupTable {
            base_value: 0,
            entries: vec![1, 2, 3, 4, 5],
            default_value: 0,
            table_type: CGPType::I32,
            alignment: 4,
        };
        assert_eq!(lt.size_bytes(), 20); // 5 * 4 bytes
    }
}