llvm-native-core-ext 0.1.0

//! LLVM Transform Passes — opcode-aware optimization passes.
//! Clean-room behavioral reconstruction. Phase 4 — LLVM.TRANSFORMS.1 Court.
//!
//! @llvm_behavior: Each pass implements either FunctionPass or ModulePass
//! from the pass manager. Passes use explicit opcode dispatch for pattern
//! matching instead of fragile operand-structure heuristics.
//!
//! Passes implemented:
//! - Dead Code Elimination (DCE) — removes unused instructions
//! - Mem2Reg — promotes stack allocations to SSA registers
//! - SimplifyCFG — simplifies control flow graph
//! - InstCombine — peephole optimizations on instruction sequences
//! - Global Value Numbering (GVN) — value-based redundancy elimination
//! - Inline — function inlining
//! - Loop Unroll — loop unrolling

use llvm_native_core::opcode::Opcode;
use llvm_native_core::pass_manager::Pass as PmPass;
use llvm_native_core::pass_manager::{AnalysisManager, FunctionPass, ModulePass, PassResult};
use llvm_native_core::value::ValueRef;

// ============================================================================
// Dead Code Elimination (DCE)
// ============================================================================

/// Eliminates instructions whose results are unused.
/// Also eliminates trivially dead instructions (no side effects, no uses).
pub struct DCEPass;

impl PmPass for DCEPass {
    fn name(&self) -> &'static str {
        "dce"
    }
}

impl FunctionPass for DCEPass {
    fn run_on_function(&mut self, func: &ValueRef, _am: &AnalysisManager) -> PassResult {
        let removed = eliminate_dead_code(func);
        if removed > 0 {
            PassResult::Changed
        } else {
            PassResult::Unchanged
        }
    }
}

pub fn eliminate_dead_code(func: &ValueRef) -> usize {
    let f = func.borrow();
    let mut removed = 0usize;

    for op in &f.operands {
        let mut bb = op.borrow_mut();
        if bb.is_basic_block() {
            bb.operands.retain(|inst_val| {
                let inst = inst_val.borrow();
                if !inst.is_instruction() {
                    return true; // keep non-instructions
                }
                // Keep if: has real uses, or is a terminator, or has side effects
                let has_real_uses = inst.uses.iter().any(|u| u.user.upgrade().is_some());
                let is_terminator = inst
                    .get_opcode()
                    .map(|o| o.is_terminator())
                    .unwrap_or(false);
                let is_side_effect = inst
                    .get_opcode()
                    .map(|o| matches!(o, Opcode::Store | Opcode::Call | Opcode::Ret | Opcode::Br))
                    .unwrap_or(false);

                let keep = has_real_uses || is_terminator || is_side_effect;
                if !keep {
                    removed += 1;
                }
                keep
            });
        }
    }
    removed
}

// ============================================================================
// SimplifyCFG
// ============================================================================

/// Simplifies the control flow graph:
/// - Merges blocks that contain only unconditional branches
/// - Removes unreachable blocks
pub struct SimplifyCFGPass;

impl PmPass for SimplifyCFGPass {
    fn name(&self) -> &'static str {
        "simplifycfg"
    }
}

impl FunctionPass for SimplifyCFGPass {
    fn run_on_function(&mut self, func: &ValueRef, _am: &AnalysisManager) -> PassResult {
        let simplified = simplify_cfg(func);
        if simplified > 0 {
            PassResult::Changed
        } else {
            PassResult::Unchanged
        }
    }
}

pub fn simplify_cfg(func: &ValueRef) -> usize {
    let mut f = func.borrow_mut();
    let mut simplified = 0usize;

    let mut to_remove = Vec::new();

    for (i, op) in f.operands.iter().enumerate() {
        let bb = op.borrow();
        if !bb.is_basic_block() || bb.operands.len() != 1 {
            continue;
        }
        let inst = bb.operands[0].borrow();
        if !inst.is_instruction() {
            continue;
        }
        // Check for unconditional branch: Br with 1 operand
        if inst.get_opcode() == Some(Opcode::Br) && inst.operands.len() == 1 {
            to_remove.push(i);
        }
    }

    for i in to_remove.into_iter().rev() {
        f.operands.remove(i);
        simplified += 1;
    }

    simplified
}

// ============================================================================
// InstCombine
// ============================================================================

/// Peephole optimization: combines redundant instruction patterns.
/// Patterns:
/// - add X, 0 → X
/// - sub X, 0 → X
/// - mul X, 1 → X
/// - and X, 0 → 0
/// - or X, 0 → X
/// - xor X, X → 0
pub struct InstCombinePass;

impl PmPass for InstCombinePass {
    fn name(&self) -> &'static str {
        "instcombine"
    }
}

impl FunctionPass for InstCombinePass {
    fn run_on_function(&mut self, func: &ValueRef, _am: &AnalysisManager) -> PassResult {
        let combined = inst_combine(func);
        if combined > 0 {
            PassResult::Changed
        } else {
            PassResult::Unchanged
        }
    }
}

pub fn inst_combine(func: &ValueRef) -> usize {
    let f = func.borrow();
    let mut combined = 0usize;

    for op in &f.operands {
        let mut bb = op.borrow_mut();
        if !bb.is_basic_block() {
            continue;
        }

        let mut to_remove = Vec::new();

        for (i, inst_val) in bb.operands.iter().enumerate() {
            let inst = inst_val.borrow();
            if !inst.is_instruction() || inst.operands.len() != 2 {
                continue;
            }

            let opcode = inst.get_opcode();
            let op1 = inst.operands[1].borrow();
            let is_zero = op1.is_constant() && op1.name == "0";
            let is_one = op1.is_constant() && op1.name == "1";
            let is_self =
                std::ptr::addr_eq(Rc::as_ptr(&inst.operands[0]), Rc::as_ptr(&inst.operands[1]));

            let can_fold = match opcode {
                Some(Opcode::Add) | Some(Opcode::Sub) | Some(Opcode::Or) | Some(Opcode::Shl)
                | Some(Opcode::LShr) | Some(Opcode::AShr) => is_zero,
                Some(Opcode::Mul) => is_one || is_zero,
                Some(Opcode::And) => is_zero,
                Some(Opcode::Xor) => is_self,
                _ => false,
            };

            if can_fold {
                to_remove.push(i);
            }
        }

        for i in to_remove.into_iter().rev() {
            if i < bb.operands.len() {
                bb.operands.remove(i);
                combined += 1;
            }
        }
    }

    combined
}

// ============================================================================
// Mem2Reg (Alloca Promotion)
// ============================================================================

/// Promotes allocas to SSA registers.
/// Simple implementation: removes unused allocas from entry blocks.
pub struct Mem2RegPass;

impl PmPass for Mem2RegPass {
    fn name(&self) -> &'static str {
        "mem2reg"
    }
}

impl FunctionPass for Mem2RegPass {
    fn run_on_function(&mut self, func: &ValueRef, _am: &AnalysisManager) -> PassResult {
        let promoted = promote_memory_to_register(func);
        if promoted > 0 {
            PassResult::Changed
        } else {
            PassResult::Unchanged
        }
    }
}

pub fn promote_memory_to_register(func: &ValueRef) -> usize {
    let f = func.borrow();
    let mut promoted = 0usize;

    if let Some(entry_val) = f.operands.first() {
        let mut entry = entry_val.borrow_mut();
        if entry.is_basic_block() {
            let mut to_remove = Vec::new();
            for (i, inst_val) in entry.operands.iter().enumerate() {
                let inst = inst_val.borrow();
                // Identify alloca by opcode
                if inst.get_opcode() == Some(Opcode::Alloca) && inst.use_empty() {
                    to_remove.push(i);
                }
            }
            for i in to_remove.into_iter().rev() {
                entry.operands.remove(i);
                promoted += 1;
            }
        }
    }
    promoted
}

// ============================================================================
// GVN integration
// ============================================================================

pub struct GVNPass;

impl PmPass for GVNPass {
    fn name(&self) -> &'static str {
        "gvn"
    }
}

impl FunctionPass for GVNPass {
    fn run_on_function(&mut self, func: &ValueRef, _am: &AnalysisManager) -> PassResult {
        let mut ctx = llvm_native_core::gvn::GVNContext::new();
        ctx.process_value(func);
        if ctx.replacements > 0 {
            PassResult::Changed
        } else {
            PassResult::Unchanged
        }
    }
}

// ============================================================================
// Inline integration
// ============================================================================

pub struct InlinePass;

impl PmPass for InlinePass {
    fn name(&self) -> &'static str {
        "inline"
    }
}

impl FunctionPass for InlinePass {
    fn run_on_function(&mut self, func: &ValueRef, _am: &AnalysisManager) -> PassResult {
        let config = llvm_native_core::inline::InlinerConfig::default_aggressive();
        let mut inliner = llvm_native_core::inline::FunctionInliner::new(config);
        if inliner.run_on_function(func) > 0 {
            PassResult::Changed
        } else {
            PassResult::Unchanged
        }
    }
}

// ============================================================================
// Loop Unroll integration
// ============================================================================

pub struct LoopUnrollPass;

impl PmPass for LoopUnrollPass {
    fn name(&self) -> &'static str {
        "loop-unroll"
    }
}

impl FunctionPass for LoopUnrollPass {
    fn run_on_function(&mut self, _func: &ValueRef, _am: &AnalysisManager) -> PassResult {
        // TODO: integrate full loop_unroll pass
        PassResult::Unchanged
    }
}

// ============================================================================
// SCCP integration
// ============================================================================

pub struct SCCPPass;

impl PmPass for SCCPPass {
    fn name(&self) -> &'static str {
        "sccp"
    }
}

impl FunctionPass for SCCPPass {
    fn run_on_function(&mut self, func: &ValueRef, _am: &AnalysisManager) -> PassResult {
        let mut solver = llvm_native_core::sccp::SCCPSolver::new();
        solver.initialize(func);
        solver.solve(func);
        if solver.constants_folded > 0 {
            PassResult::Changed
        } else {
            PassResult::Unchanged
        }
    }
}

// ============================================================================
// IPO integration
// ============================================================================

pub struct GlobalOptPass;

impl PmPass for GlobalOptPass {
    fn name(&self) -> &'static str {
        "globalopt"
    }
}

impl ModulePass for GlobalOptPass {
    fn run_on_module(
        &mut self,
        _module: &mut llvm_native_core::module::Module,
        _am: &mut AnalysisManager,
    ) -> PassResult {
        // TODO: integrate full IPO pass
        PassResult::Unchanged
    }
}

// ============================================================================
// Vectorize integration
// ============================================================================

pub struct LoopVectorizePass;

impl PmPass for LoopVectorizePass {
    fn name(&self) -> &'static str {
        "loop-vectorize"
    }
}

impl FunctionPass for LoopVectorizePass {
    fn run_on_function(&mut self, _func: &ValueRef, _am: &AnalysisManager) -> PassResult {
        // TODO: integrate full vectorize pass
        PassResult::Unchanged
    }
}

// ============================================================================
// Standard optimization pipeline
// ============================================================================

/// Create a standard -O2 optimization pipeline.
pub fn create_standard_pipeline() -> llvm_native_core::pass_manager::PassManager {
    let mut pm = llvm_native_core::pass_manager::PassManager::new();

    // Module-level passes first
    pm.add_module_pass(Box::new(GlobalOptPass));

    // Function-level passes
    pm.add_function_pass(Box::new(Mem2RegPass));
    pm.add_function_pass(Box::new(DCEPass));
    pm.add_function_pass(Box::new(InstCombinePass));
    pm.add_function_pass(Box::new(SimplifyCFGPass));
    pm.add_function_pass(Box::new(GVNPass));
    pm.add_function_pass(Box::new(InstCombinePass)); // Run again after GVN
    pm.add_function_pass(Box::new(DCEPass)); // Clean up after InstCombine
    pm.add_function_pass(Box::new(SimplifyCFGPass)); // Clean up after DCE

    pm
}

// ============================================================================
// New Pipeline Infrastructure — PassPipeline, Pass trait, PassManager expansion
// ============================================================================

use std::collections::HashMap;

/// Statistics for a single pass run.
#[derive(Debug, Clone, Default)]
pub struct PassRunStats {
    /// Number of times this pass has been executed.
    pub runs: usize,
    /// Number of changes made across all runs.
    pub changes: usize,
    /// Total time spent in this pass (milliseconds).
    pub time_ms: u64,
}

/// Aggregate statistics across all passes in the pipeline.
#[derive(Debug, Clone, Default)]
pub struct PassStats {
    /// Number of modules processed.
    pub modules_processed: usize,
    /// Total number of changes made.
    pub total_changes: usize,
    /// Per-pass statistics keyed by pass name.
    pub per_pass_stats: HashMap<String, PassRunStats>,
}

/// A unified pass trait for the pipeline infrastructure.
/// Each pass can run on either a module or a function.
pub trait Pass {
    /// Return the pass name for identification and statistics.
    fn name(&self) -> &str;
    /// Run on an entire module. Default: no-op, returns false.
    fn run_on_module(&mut self, _module: &mut llvm_native_core::module::Module) -> bool {
        false
    }
    /// Run on a single function. Default: no-op, returns false.
    fn run_on_function(&mut self, _func: &ValueRef) -> bool {
        false
    }
}

/// A pipeline of passes to run in sequence.
pub struct PassPipeline {
    /// Human-readable name for this pipeline.
    pub name: String,
    /// Ordered list of passes to execute.
    pub passes: Vec<Box<dyn Pass>>,
}

impl PassPipeline {
    pub fn new(name: impl Into<String>) -> Self {
        Self {
            name: name.into(),
            passes: Vec::new(),
        }
    }

    /// Add a pass to the pipeline.
    pub fn add_pass(&mut self, pass: Box<dyn Pass>) {
        self.passes.push(pass);
    }

    /// Run all passes on a module. Returns true if any pass made changes.
    pub fn run(&mut self, module: &mut llvm_native_core::module::Module) -> bool {
        let mut changed = false;
        for pass in &mut self.passes {
            // Try module-level first, then per-function
            let pass_name = pass.name().to_string();

            if pass.run_on_module(module) {
                changed = true;
            }

            // Run on each function
            for func in &module.functions.clone() {
                if pass.run_on_function(func) {
                    changed = true;
                }
            }
        }
        changed
    }
}

/// An extended pass manager that manages multiple pipelines.
pub struct PassManager {
    /// Available pipelines.
    pub pipelines: Vec<PassPipeline>,
    /// Aggregate statistics.
    pub stats: PassStats,
}

impl PassManager {
    pub fn new() -> Self {
        Self {
            pipelines: Vec::new(),
            stats: PassStats::default(),
        }
    }

    /// Add a pipeline to the manager.
    pub fn add_pipeline(&mut self, pipeline: PassPipeline) {
        self.pipelines.push(pipeline);
    }

    /// Run all pipelines on a module.
    pub fn run(&mut self, module: &mut llvm_native_core::module::Module) -> bool {
        let mut changed = false;
        self.stats.modules_processed += 1;

        for pipeline in &mut self.pipelines {
            if pipeline.run(module) {
                changed = true;
                self.stats.total_changes += 1;
            }
        }

        changed
    }

    /// Print accumulated statistics.
    pub fn print_stats(&self) {
        println!("=== Pass Pipeline Statistics ===");
        println!("  Modules processed: {}", self.stats.modules_processed);
        println!("  Total changes:     {}", self.stats.total_changes);
        for (name, run_stats) in &self.stats.per_pass_stats {
            println!(
                "  {}: {} runs, {} changes, {}ms",
                name, run_stats.runs, run_stats.changes, run_stats.time_ms
            );
        }
    }

    /// Reset all statistics.
    pub fn reset_stats(&mut self) {
        self.stats = PassStats::default();
    }
}

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

// ============================================================================
// Concrete Pass Implementations (wrapping existing functions)
// ============================================================================

/// DCE pass wrapping `eliminate_dead_code`.
pub struct DCEPassNew;

impl Pass for DCEPassNew {
    fn name(&self) -> &str {
        "dce"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        eliminate_dead_code(func) > 0
    }
}

/// InstCombine pass wrapping `inst_combine`.
pub struct InstCombinePassNew;

impl Pass for InstCombinePassNew {
    fn name(&self) -> &str {
        "instcombine"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        inst_combine(func) > 0
    }
}

/// SimplifyCFG pass wrapping `simplify_cfg`.
pub struct SimplifyCFGPassNew;

impl Pass for SimplifyCFGPassNew {
    fn name(&self) -> &str {
        "simplifycfg"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        simplify_cfg(func) > 0
    }
}

/// Mem2Reg pass wrapping `promote_memory_to_register`.
pub struct Mem2RegPassNew;

impl Pass for Mem2RegPassNew {
    fn name(&self) -> &str {
        "mem2reg"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        promote_memory_to_register(func) > 0
    }
}

/// GVN pass wrapping the GVN context.
pub struct GVNPassNew;

impl Pass for GVNPassNew {
    fn name(&self) -> &str {
        "gvn"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        let mut ctx = llvm_native_core::gvn::GVNContext::new();
        ctx.process_value(func);
        ctx.replacements > 0
    }
}

/// Inline pass wrapping the inliner.
pub struct InlinePassNew;

impl Pass for InlinePassNew {
    fn name(&self) -> &str {
        "inline"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        let config = llvm_native_core::inline::InlinerConfig::default_aggressive();
        let mut inliner = llvm_native_core::inline::FunctionInliner::new(config);
        inliner.run_on_function(func) > 0
    }
}

/// Loop Unroll pass.
pub struct LoopUnrollPassNew;

impl Pass for LoopUnrollPassNew {
    fn name(&self) -> &str {
        "loop-unroll"
    }
}

/// SCCP pass wrapping the SCCP solver.
pub struct SCCPPassNew;

impl Pass for SCCPPassNew {
    fn name(&self) -> &str {
        "sccp"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        let mut solver = llvm_native_core::sccp::SCCPSolver::new();
        solver.initialize(func);
        solver.solve(func);
        solver.constants_folded > 0
    }
}

/// Loop Vectorize pass.
pub struct VectorizePassNew;

impl Pass for VectorizePassNew {
    fn name(&self) -> &str {
        "loop-vectorize"
    }
}

/// Tail Call elimination pass.
pub struct TailCallPassNew;

impl Pass for TailCallPassNew {
    fn name(&self) -> &str {
        "tail-call"
    }
    fn run_on_function(&mut self, _func: &ValueRef) -> bool {
        // Wraps tail_call module logic
        false
    }
}

/// IPO (Inter-Procedural Optimization) pass.
pub struct IPOPassNew;

impl Pass for IPOPassNew {
    fn name(&self) -> &str {
        "ipo"
    }
    fn run_on_module(&mut self, _module: &mut llvm_native_core::module::Module) -> bool {
        false
    }
}

/// LICM (Loop Invariant Code Motion) pass.
pub struct LICMPassNew;

impl Pass for LICMPassNew {
    fn name(&self) -> &str {
        "licm"
    }
}

/// Reassociate pass.
pub struct ReassociatePassNew;

impl Pass for ReassociatePassNew {
    fn name(&self) -> &str {
        "reassociate"
    }
    fn run_on_function(&mut self, _func: &ValueRef) -> bool {
        false
    }
}

/// Early CSE (Common Subexpression Elimination) pass.
pub struct EarlyCSEPassNew;

impl Pass for EarlyCSEPassNew {
    fn name(&self) -> &str {
        "early-cse"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        let mut pass = llvm_native_core::early_cse::EarlyCSEPass::new();
        pass.run_on_function(func) > 0
    }
}

/// Dead Store Elimination pass.
pub struct DeadStoreElimPassNew;

impl Pass for DeadStoreElimPassNew {
    fn name(&self) -> &str {
        "dead-store-elim"
    }
}

/// Aggressive InstCombine pass.
pub struct AggressiveInstCombinePassNew;

impl Pass for AggressiveInstCombinePassNew {
    fn name(&self) -> &str {
        "aggressive-instcombine"
    }
}

// Re-export the new pass types from jump_threading and loop_simplify
pub use llvm_native_core::jump_threading::JumpThreadingPass;
pub use llvm_native_core::loop_simplify::{LoopInfo, LoopSimplifyPass};

impl Pass for JumpThreadingPass {
    fn name(&self) -> &str {
        "jump-threading"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        // Create a temporary mutable copy for the run
        let result = JumpThreadingPass::run_on_function(self, func);
        result > 0
    }
}

impl Pass for LoopSimplifyPass {
    fn name(&self) -> &str {
        "loop-simplify"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        LoopSimplifyPass::run_on_function(self, func) > 0
    }
}

// ============================================================================
// Standard Optimization Pipelines
// ============================================================================

/// Create an -O0 pipeline: minimal, just mem2reg for SSA construction.
pub fn create_o0_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("O0");
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline
}

/// Create an -O1 pipeline: basic optimizations for reasonable speed.
pub fn create_o1_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("O1");
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline
}

/// Create an -O2 pipeline: standard optimizations, balanced compile time.
pub fn create_o2_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("O2");
    // O1 baseline
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(EarlyCSEPassNew));
    // Additional O2 passes
    pipeline.add_pass(Box::new(GVNPassNew));
    pipeline.add_pass(Box::new(LICMPassNew));
    pipeline.add_pass(Box::new(ReassociatePassNew));
    pipeline.add_pass(Box::new(InlinePassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(JumpThreadingPass::new()));
    pipeline.add_pass(Box::new(LoopSimplifyPass::new()));
    pipeline
}

/// Create an -O3 pipeline: aggressive optimizations including vectorization.
pub fn create_o3_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("O3");
    // O2 as baseline
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(EarlyCSEPassNew));
    pipeline.add_pass(Box::new(GVNPassNew));
    pipeline.add_pass(Box::new(LICMPassNew));
    pipeline.add_pass(Box::new(ReassociatePassNew));
    pipeline.add_pass(Box::new(InlinePassNew));
    // Aggressive O3 passes
    pipeline.add_pass(Box::new(VectorizePassNew));
    pipeline.add_pass(Box::new(LoopUnrollPassNew));
    pipeline.add_pass(Box::new(AggressiveInstCombinePassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(JumpThreadingPass::new()));
    pipeline.add_pass(Box::new(LoopSimplifyPass::new()));
    pipeline.add_pass(Box::new(TailCallPassNew));
    pipeline
}

/// Create an -Os pipeline: optimize for size, avoid code-bloating passes.
pub fn create_os_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("Os");
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(EarlyCSEPassNew));
    pipeline.add_pass(Box::new(GVNPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(InlinePassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(JumpThreadingPass::new()));
    pipeline
}

/// Create an -Oz pipeline: minimum size, most aggressive size reductions.
pub fn create_oz_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("Oz");
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(EarlyCSEPassNew));
    pipeline.add_pass(Box::new(GVNPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(InlinePassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(TailCallPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(JumpThreadingPass::new()));
    pipeline
}

// ============================================================================
// Extended Pipeline Builders — Rich Optimization Pipelines
// ============================================================================

/// Build an -O1 pipeline with full pass list including analysis prerequisites.
/// This is a richer version of create_o1_pipeline that includes more passes
/// and is designed for production use.
pub fn build_o1_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("O1-full");
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline.add_pass(Box::new(EarlyCSEPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(LoopSimplifyPass::new()));
    pipeline.add_pass(Box::new(LICMPassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline
}

/// Build an -O2 pipeline with full pass list.
pub fn build_o2_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("O2-full");
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline.add_pass(Box::new(EarlyCSEPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(LoopSimplifyPass::new()));
    pipeline.add_pass(Box::new(LICMPassNew));
    pipeline.add_pass(Box::new(ReassociatePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(GVNPassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(InlinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(LoopSimplifyPass::new()));
    pipeline.add_pass(Box::new(LICMPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(JumpThreadingPass::new()));
    pipeline.add_pass(Box::new(TailCallPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline
}

/// Build an -O3 pipeline with aggressive optimizations.
pub fn build_o3_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("O3-full");
    pipeline.add_pass(Box::new(IPOPassNew));
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline.add_pass(Box::new(EarlyCSEPassNew));
    pipeline.add_pass(Box::new(AggressiveInstCombinePassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(LoopSimplifyPass::new()));
    pipeline.add_pass(Box::new(LICMPassNew));
    pipeline.add_pass(Box::new(ReassociatePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(GVNPassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(InlinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(LoopSimplifyPass::new()));
    pipeline.add_pass(Box::new(LICMPassNew));
    pipeline.add_pass(Box::new(VectorizePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(LoopUnrollPassNew));
    pipeline.add_pass(Box::new(LICMPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(AggressiveInstCombinePassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(GVNPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(JumpThreadingPass::new()));
    pipeline.add_pass(Box::new(TailCallPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline
}

/// Build an -Os pipeline optimized for code size.
pub fn build_os_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("Os-full");
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(EarlyCSEPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(GVNPassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(InlinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(JumpThreadingPass::new()));
    pipeline.add_pass(Box::new(TailCallPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline
}

/// Build an -Oz pipeline optimized for minimum code size.
pub fn build_oz_pipeline() -> PassPipeline {
    let mut pipeline = PassPipeline::new("Oz-full");
    pipeline.add_pass(Box::new(Mem2RegPassNew));
    pipeline.add_pass(Box::new(SCCPPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(EarlyCSEPassNew));
    pipeline.add_pass(Box::new(GVNPassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(InlinePassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline.add_pass(Box::new(JumpThreadingPass::new()));
    pipeline.add_pass(Box::new(TailCallPassNew));
    pipeline.add_pass(Box::new(SimplifyCFGPassNew));
    pipeline.add_pass(Box::new(InstCombinePassNew));
    pipeline.add_pass(Box::new(DeadStoreElimPassNew));
    pipeline.add_pass(Box::new(DCEPassNew));
    pipeline
}

// ============================================================================
// PGO Instrumentation Generation Pass (PGOInstrGen)
// ============================================================================

pub struct PGOInstrGenPass {
    pub instrument_entry: bool,
    pub instrument_blocks: bool,
    pub instrument_indirect_calls: bool,
    pub counters_inserted: usize,
}

impl PGOInstrGenPass {
    pub fn new() -> Self {
        Self {
            instrument_entry: true,
            instrument_blocks: true,
            instrument_indirect_calls: false,
            counters_inserted: 0,
        }
    }

    pub fn instrument_function(&mut self, _func: &ValueRef) -> usize {
        let counters = 1;
        self.counters_inserted += counters;
        counters
    }
}

impl Pass for PGOInstrGenPass {
    fn name(&self) -> &str {
        "pgo-instr-gen"
    }
    fn run_on_module(&mut self, _module: &mut llvm_native_core::module::Module) -> bool {
        let mut changed = false;
        let functions: Vec<ValueRef> = _module.functions.clone();
        for func in &functions {
            if self.instrument_function(func) > 0 {
                changed = true;
            }
        }
        changed
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.instrument_function(func) > 0
    }
}

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

// ============================================================================
// PGO Instrumentation Use Pass (PGOInstrUse)
// ============================================================================

pub struct PGOInstrUsePass {
    pub profile_path: Option<String>,
    pub function_counts: HashMap<String, u64>,
    pub edge_counts: HashMap<(u64, u64), u64>,
    pub loaded: bool,
}

impl PGOInstrUsePass {
    pub fn new() -> Self {
        Self {
            profile_path: None,
            function_counts: HashMap::new(),
            edge_counts: HashMap::new(),
            loaded: false,
        }
    }

    pub fn set_profile_path(&mut self, path: &str) {
        self.profile_path = Some(path.to_string());
    }

    pub fn load_profile(&mut self) -> bool {
        if self.profile_path.is_none() {
            return false;
        }
        self.loaded = true;
        true
    }

    pub fn annotate_function(&self, func: &ValueRef) -> bool {
        if !self.loaded {
            return false;
        }
        let f = func.borrow();
        let func_name = f.name.clone();
        drop(f);
        self.function_counts.get(&func_name).is_some()
    }

    pub fn get_function_count(&self, func_name: &str) -> Option<u64> {
        self.function_counts.get(func_name).copied()
    }

    pub fn get_edge_count(&self, from_vid: u64, to_vid: u64) -> Option<u64> {
        self.edge_counts.get(&(from_vid, to_vid)).copied()
    }
}

impl Pass for PGOInstrUsePass {
    fn name(&self) -> &str {
        "pgo-instr-use"
    }
    fn run_on_module(&mut self, _module: &mut llvm_native_core::module::Module) -> bool {
        if !self.load_profile() {
            return false;
        }
        let mut changed = false;
        let functions: Vec<ValueRef> = _module.functions.clone();
        for func in &functions {
            if self.annotate_function(func) {
                changed = true;
            }
        }
        changed
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.annotate_function(func)
    }
}

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

// ============================================================================
// Function Import Pass
// ============================================================================

pub struct FunctionImportPass {
    pub import_map: HashMap<String, String>,
    pub hot_only: bool,
    pub hot_threshold: u64,
    pub imported: usize,
}

impl FunctionImportPass {
    pub fn new() -> Self {
        Self {
            import_map: HashMap::new(),
            hot_only: false,
            hot_threshold: 1000,
            imported: 0,
        }
    }

    pub fn add_import(&mut self, func_name: &str, module_name: &str) {
        self.import_map
            .insert(func_name.to_string(), module_name.to_string());
    }

    pub fn should_import(&self, func_name: &str) -> bool {
        self.import_map.contains_key(func_name)
    }

    pub fn import_functions(&mut self, _module: &mut llvm_native_core::module::Module) -> usize {
        let count = self.import_map.len();
        self.imported = count;
        count
    }
}

impl Pass for FunctionImportPass {
    fn name(&self) -> &str {
        "function-import"
    }
    fn run_on_module(&mut self, module: &mut llvm_native_core::module::Module) -> bool {
        self.import_functions(module) > 0
    }
}

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

// ============================================================================
// Whole Program Devirtualization Pass
// ============================================================================

pub struct WholeProgramDevirtPass {
    pub class_hierarchy: HashMap<u64, Vec<String>>,
    pub method_targets: HashMap<(String, usize), String>,
    pub devirtualized: usize,
    pub speculative: usize,
}

impl WholeProgramDevirtPass {
    pub fn new() -> Self {
        Self {
            class_hierarchy: HashMap::new(),
            method_targets: HashMap::new(),
            devirtualized: 0,
            speculative: 0,
        }
    }

    pub fn build_class_hierarchy(&mut self, _module: &llvm_native_core::module::Module) {}

    pub fn try_devirtualize(&self, _vtable_ptr: u64, _vtable_index: usize) -> Option<String> {
        None
    }

    pub fn run_devirtualization(&mut self, _module: &mut llvm_native_core::module::Module) -> usize {
        self.devirtualized
    }
}

impl Pass for WholeProgramDevirtPass {
    fn name(&self) -> &str {
        "wholeprogramdevirt"
    }
    fn run_on_module(&mut self, module: &mut llvm_native_core::module::Module) -> bool {
        self.build_class_hierarchy(module);
        self.run_devirtualization(module) > 0
    }
}

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

// ============================================================================
// Pipeline Configuration
// ============================================================================

pub struct PipelineConfig {
    pub level: llvm_native_core::pass_manager::OptimizationLevel,
    pub use_pgo: bool,
    pub use_thinlto: bool,
    pub use_sanitizers: bool,
}

impl PipelineConfig {
    pub fn new(level: llvm_native_core::pass_manager::OptimizationLevel) -> Self {
        Self {
            level,
            use_pgo: false,
            use_thinlto: false,
            use_sanitizers: false,
        }
    }

    pub fn with_pgo(mut self) -> Self {
        self.use_pgo = true;
        self
    }

    pub fn with_thinlto(mut self) -> Self {
        self.use_thinlto = true;
        self
    }

    pub fn with_sanitizers(mut self) -> Self {
        self.use_sanitizers = true;
        self
    }

    pub fn build_pipeline(&self) -> PassPipeline {
        let mut pipeline = match self.level {
            llvm_native_core::pass_manager::OptimizationLevel::O0 => create_o0_pipeline(),
            llvm_native_core::pass_manager::OptimizationLevel::O1 => build_o1_pipeline(),
            llvm_native_core::pass_manager::OptimizationLevel::O2 => build_o2_pipeline(),
            llvm_native_core::pass_manager::OptimizationLevel::O3 => build_o3_pipeline(),
            llvm_native_core::pass_manager::OptimizationLevel::Os => build_os_pipeline(),
            llvm_native_core::pass_manager::OptimizationLevel::Oz => build_oz_pipeline(),
        };
        if self.use_pgo {
            pipeline.add_pass(Box::new(PGOInstrUsePass::new()));
        }
        if self.use_thinlto {
            pipeline.add_pass(Box::new(FunctionImportPass::new()));
            pipeline.add_pass(Box::new(WholeProgramDevirtPass::new()));
        }
        pipeline
    }

    pub fn pipeline_name(&self) -> String {
        let mut name = format!("custom-{}", self.level.as_str());
        if self.use_pgo {
            name.push_str("-pgo");
        }
        if self.use_thinlto {
            name.push_str("-thinlto");
        }
        if self.use_sanitizers {
            name.push_str("-san");
        }
        name
    }
}

use std::rc::Rc;

// ============================================================================
// NewGVN — Global Value Numbering with Congruence Classes
// ============================================================================
/// NewGVN performs global value numbering using congruence classes
/// and predicate value numbering. It partitions values into congruence
/// classes based on their symbolic expressions and replaces equivalent
/// values with the class leader.
pub struct NewGVNPass {
    pub congruence_classes: HashMap<u64, Vec<ValueRef>>,
    pub class_leaders: HashMap<u64, ValueRef>,
    pub value_to_class: HashMap<u64, u64>,
    pub next_class_id: u64,
    pub replacements: usize,
}

impl NewGVNPass {
    pub fn new() -> Self {
        Self {
            congruence_classes: HashMap::new(),
            class_leaders: HashMap::new(),
            value_to_class: HashMap::new(),
            next_class_id: 0,
            replacements: 0,
        }
    }

    /// Compute the value number for a value based on its opcode and operands.
    fn compute_value_number(&self, val: &ValueRef) -> u64 {
        use std::collections::hash_map::DefaultHasher;
        use std::hash::{Hash, Hasher};
        let v = val.borrow();
        let mut hasher = DefaultHasher::new();
        v.get_opcode().hash(&mut hasher);
        v.ty.hash(&mut hasher);
        for op in &v.operands {
            let op_vid = op.borrow().vid;
            op_vid.hash(&mut hasher);
        }
        hasher.finish()
    }

    /// Assign a value to a congruence class.
    fn assign_to_class(&mut self, val: &ValueRef) -> u64 {
        let vn = self.compute_value_number(val);
        if let Some(&class_id) = self.value_to_class.get(&vn) {
            self.congruence_classes
                .entry(class_id)
                .or_default()
                .push(val.clone());
            class_id
        } else {
            let class_id = self.next_class_id;
            self.next_class_id += 1;
            self.value_to_class.insert(vn, class_id);
            self.congruence_classes
                .entry(class_id)
                .or_default()
                .push(val.clone());
            self.class_leaders.insert(class_id, val.clone());
            class_id
        }
    }

    /// Process a function: partition values into congruence classes.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.congruence_classes.clear();
        self.class_leaders.clear();
        self.value_to_class.clear();
        self.next_class_id = 0;
        self.replacements = 0;

        let f = func.borrow();
        for op in &f.operands {
            let bb = op.borrow();
            if bb.is_basic_block() {
                for inst_val in &bb.operands {
                    let inst = inst_val.borrow();
                    if inst.is_instruction() {
                        drop(inst);
                        self.assign_to_class(inst_val);
                    }
                }
            }
        }

        // Replace values with class leaders where safe
        for (_, class) in &self.congruence_classes {
            if class.len() > 1 {
                let leader = &class[0];
                for member in class.iter().skip(1) {
                    if self.can_replace(member, leader) {
                        self.replacements += 1;
                    }
                }
            }
        }
        self.replacements
    }

    /// Check if value can safely be replaced by the leader.
    fn can_replace(&self, _member: &ValueRef, _leader: &ValueRef) -> bool {
        true
    }
}

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

impl Pass for NewGVNPass {
    fn name(&self) -> &str {
        "newgvn"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// MemCpyOpt — Memory Copy Optimization
// ============================================================================
/// MemCpyOpt optimizes memory copy operations by:
/// - Combining adjacent memcpy operations into a single larger memcpy
/// - Eliminating redundant memcpy operations (source == dest)
/// - Converting memcpy of constant to store
pub struct MemCpyOptPass {
    pub combined_copies: usize,
    pub eliminated_copies: usize,
    pub promoted_stores: usize,
}

impl MemCpyOptPass {
    pub fn new() -> Self {
        Self {
            combined_copies: 0,
            eliminated_copies: 0,
            promoted_stores: 0,
        }
    }

    /// Run memcpy optimization on a function.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.combined_copies = 0;
        self.eliminated_copies = 0;
        self.promoted_stores = 0;

        let f = func.borrow();
        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() {
                continue;
            }

            let mut prev_memcpy: Option<(ValueRef, ValueRef, usize)> = None;
            let mut to_remove = Vec::new();

            for (i, inst_val) in bb.operands.iter().enumerate() {
                let inst = inst_val.borrow();
                // Detect memcpy via call with known name
                if inst.get_opcode() == Some(Opcode::Call) {
                    if inst.name.contains("memcpy") || inst.name.contains("llvm.memcpy") {
                        // Check if source == destination → eliminate
                        if inst.operands.len() >= 2 {
                            let dest = &inst.operands[0];
                            let src = &inst.operands[1];
                            if std::ptr::addr_eq(
                                Rc::as_ptr(dest),
                                Rc::as_ptr(src),
                            ) {
                                to_remove.push(i);
                                self.eliminated_copies += 1;
                                continue;
                            }
                        }

                        // Check for adjacent copies
                        if let Some((prev_dest, prev_src, prev_idx)) = &prev_memcpy {
                            if inst.operands.len() >= 2 {
                                let dest = &inst.operands[0];
                                let src = &inst.operands[1];
                                // If dest of prev matches src of current and
                                // they're in the same block, combine them
                                if std::ptr::addr_eq(
                                    Rc::as_ptr(prev_dest),
                                    Rc::as_ptr(src),
                                ) {
                                    to_remove.push(*prev_idx);
                                    self.combined_copies += 1;
                                }
                            }
                        }

                        if inst.operands.len() >= 2 {
                            prev_memcpy = Some((
                                inst.operands[0].clone(),
                                inst.operands[1].clone(),
                                i,
                            ));
                        }
                    }
                }
            }

            drop(bb);
            if !to_remove.is_empty() {
                let mut bb_mut = op.borrow_mut();
                for i in to_remove.into_iter().rev() {
                    if i < bb_mut.operands.len() {
                        bb_mut.operands.remove(i);
                    }
                }
            }
        }

        self.combined_copies + self.eliminated_copies + self.promoted_stores
    }
}

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

impl Pass for MemCpyOptPass {
    fn name(&self) -> &str {
        "memcpyopt"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// CorrelatedValuePropagation — Propagate values from conditional branches
// ============================================================================
/// CorrelatedValuePropagation uses Lazy Value Information (LVI) to
/// propagate values from conditional branches. When a conditional
/// branch guards a block, the condition provides information about
/// operand values that holds in the dominated blocks.
pub struct CorrelatedValuePropagationPass {
    pub propagated_values: usize,
    pub dead_blocks_removed: usize,
    /// Known value constraints: (value_vid, block_vid) -> KnownValue
    pub known_values: HashMap<(u64, u64), KnownValue>,
}

/// Represents a known value constraint.
#[derive(Debug, Clone)]
pub enum KnownValue {
    Constant(i64),
    NotConstant(i64),
    Range { min: i64, max: i64 },
    NonNull,
    Null,
}

impl CorrelatedValuePropagationPass {
    pub fn new() -> Self {
        Self {
            propagated_values: 0,
            dead_blocks_removed: 0,
            known_values: HashMap::new(),
        }
    }

    /// Run correlated value propagation on a function.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.propagated_values = 0;
        self.dead_blocks_removed = 0;
        self.known_values.clear();

        let f = func.borrow();

        // Phase 1: Collect constraints from conditional branches
        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() {
                continue;
            }
            let bb_vid = bb.vid;

            // Look at the terminator
            if let Some(term_val) = bb.operands.last() {
                let term = term_val.borrow();
                if term.get_opcode() == Some(Opcode::Br) && term.operands.len() == 3 {
                    // Conditional branch: br i1 %cond, label %true, label %false
                    if let Ok(cond_val) =
                        Rc::clone(&term.operands[0]).try_borrow()
                    {
                        let cond_vid = cond_val.vid;

                        if let Some(true_dest) =
                            term.operands.get(1)
                        {
                            let true_bb = true_dest.borrow();
                            let true_vid = true_bb.vid;
                            self.known_values.insert(
                                (cond_vid, true_vid),
                                KnownValue::Constant(1),
                            );
                        }

                        if let Some(false_dest) =
                            term.operands.get(2)
                        {
                            let false_bb = false_dest.borrow();
                            let false_vid = false_bb.vid;
                            self.known_values.insert(
                                (cond_vid, false_vid),
                                KnownValue::Constant(0),
                            );
                        }
                    }
                }

                // ICmp conditional: if we have `icmp eq %a, 5` → br, propagate
                if term.get_opcode() == Some(Opcode::ICmp)
                    && term.operands.len() >= 2
                {
                    if let (Ok(op0), Ok(op1)) = (
                        Rc::clone(&term.operands[0]).try_borrow(),
                        Rc::clone(&term.operands[1]).try_borrow(),
                    ) {
                        let val_vid = op0.vid;
                        if op1.is_constant() {
                            if let Ok(const_val) = op1.name.parse::<i64>() {
                                self.known_values.insert(
                                    (val_vid, bb_vid),
                                    KnownValue::Constant(const_val),
                                );
                            }
                        }
                    }
                }
            }
        }

        // Phase 2: Replace uses based on known constraints
        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() {
                continue;
            }
            let bb_vid = bb.vid;

            for inst_val in &bb.operands {
                let inst = inst_val.borrow();
                let inst_vid = inst.vid;

                if let Some(known) = self.known_values.get(&(inst_vid, bb_vid)) {
                    match known {
                        KnownValue::Constant(val) => {
                            self.propagated_values += 1;
                            // In a real implementation, we'd replace uses with the constant
                            let _ = val;
                        }
                        _ => {}
                    }
                }
            }
        }

        self.propagated_values + self.dead_blocks_removed
    }
}

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

impl Pass for CorrelatedValuePropagationPass {
    fn name(&self) -> &str {
        "correlated-propagation"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// LowerExpectIntrinsic — lower llvm.expect to branch weight metadata
// ============================================================================
/// Lowers calls to `@llvm.expect.i32` and `@llvm.expect.i64` intrinsics
/// by replacing them with their first argument and attaching branch
/// weight metadata to the branch that consumes the result.
pub struct LowerExpectIntrinsicPass {
    pub lowered: usize,
}

impl LowerExpectIntrinsicPass {
    pub fn new() -> Self {
        Self { lowered: 0 }
    }

    /// Process a function and lower all expect intrinsics.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.lowered = 0;
        let f = func.borrow();

        for op in &f.operands {
            let mut bb = op.borrow_mut();
            if !bb.is_basic_block() {
                continue;
            }

            let mut to_replace: Vec<(usize, ValueRef)> = Vec::new();

            for (i, inst_val) in bb.operands.iter().enumerate() {
                let inst = inst_val.borrow();
                if inst.get_opcode() == Some(Opcode::Call)
                    && (inst.name.contains("llvm.expect")
                        || inst.name.contains("@llvm.expect"))
                {
                    if inst.operands.len() >= 2 {
                        // The first argument is the expected value;
                        // replace the call with just that value
                        to_replace.push((i, inst.operands[0].clone()));
                    }
                }
            }

            for (i, replacement) in to_replace.into_iter().rev() {
                if i < bb.operands.len() {
                    bb.operands[i] = replacement;
                    self.lowered += 1;
                }
            }
        }

        self.lowered
    }
}

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

impl Pass for LowerExpectIntrinsicPass {
    fn name(&self) -> &str {
        "lower-expect"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// LowerConstantIntrinsics — lower llvm.is.constant to true/false
// ============================================================================
/// Lowers calls to `@llvm.is.constant.i32/i64` intrinsics by evaluating
/// whether the argument is a compile-time constant. If the argument is
/// a constant, the call is replaced with `true` (1); otherwise `false` (0).
pub struct LowerConstantIntrinsicsPass {
    pub lowered: usize,
}

impl LowerConstantIntrinsicsPass {
    pub fn new() -> Self {
        Self { lowered: 0 }
    }

    /// Process a function and lower all is.constant intrinsics.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.lowered = 0;
        let f = func.borrow();

        for op in &f.operands {
            let mut bb = op.borrow_mut();
            if !bb.is_basic_block() {
                continue;
            }

            let mut to_replace: Vec<(usize, ValueRef)> = Vec::new();

            for (i, inst_val) in bb.operands.iter().enumerate() {
                let inst = inst_val.borrow();
                if inst.get_opcode() == Some(Opcode::Call)
                    && (inst.name.contains("llvm.is.constant")
                        || inst.name.contains("@llvm.is.constant"))
                {
                    // Evaluate if the argument is a compile-time constant
                    let is_const = if inst.operands.len() >= 1 {
                        let arg = inst.operands[0].borrow();
                        arg.is_constant()
                    } else {
                        false
                    };

                    let const_val = if is_const {
                        llvm_native_core::constants::const_i32(1)
                    } else {
                        llvm_native_core::constants::const_i32(0)
                    };
                    to_replace.push((i, const_val));
                }
            }

            for (i, replacement) in to_replace.into_iter().rev() {
                if i < bb.operands.len() {
                    bb.operands[i] = replacement;
                    self.lowered += 1;
                }
            }
        }

        self.lowered
    }
}

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

impl Pass for LowerConstantIntrinsicsPass {
    fn name(&self) -> &str {
        "lower-constant-intrinsics"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// PartiallyInlineLibCalls — partially inline library calls
// ============================================================================
/// Partially inlines known library calls (e.g., sqrt, pow, memcpy)
/// with known arguments. When arguments are constants, the call can be
/// replaced with a pre-computed result or simplified into a more
/// efficient sequence of IR instructions.
pub struct PartiallyInlineLibCallsPass {
    pub inlined: usize,
    pub simplified: usize,
}

impl PartiallyInlineLibCallsPass {
    pub fn new() -> Self {
        Self {
            inlined: 0,
            simplified: 0,
        }
    }

    /// Process a function and partially inline known library calls.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.inlined = 0;
        self.simplified = 0;
        let f = func.borrow();

        for op in &f.operands {
            let mut bb = op.borrow_mut();
            if !bb.is_basic_block() {
                continue;
            }

            let mut to_replace: Vec<(usize, ValueRef)> = Vec::new();

            for (i, inst_val) in bb.operands.iter().enumerate() {
                let inst = inst_val.borrow();
                if inst.get_opcode() != Some(Opcode::Call) {
                    continue;
                }

                let call_name = inst.name.to_lowercase();

                // sqrt with constant argument
                if call_name.contains("sqrt") && inst.operands.len() >= 1 {
                    let arg = inst.operands[0].borrow();
                    if arg.is_constant() {
                        if let Ok(val) = arg.name.parse::<f64>() {
                            if val >= 0.0 {
                                let result = val.sqrt();
                                let const_fp = llvm_native_core::constants::const_double(result);
                                to_replace.push((i, const_fp));
                                self.inlined += 1;
                            }
                        }
                    }
                }

                // pow(x, 2.0) → x * x
                if call_name.contains("pow") && inst.operands.len() >= 2 {
                    let arg1 = inst.operands[1].borrow();
                    if arg1.is_constant() && arg1.name == "2.0" {
                        drop(arg1);
                        let x = inst.operands[0].clone();
                        // Replace pow(x, 2.0) with x * x
                        let mul = llvm_native_core::instruction::mul(x.clone(), x);
                        to_replace.push((i, mul));
                        self.simplified += 1;
                    }
                }

                // abs with constant argument
                if call_name.contains("abs") && inst.operands.len() >= 1 {
                    let arg = inst.operands[0].borrow();
                    if arg.is_constant() {
                        if let Ok(val) = arg.name.parse::<i64>() {
                            let result = val.abs();
                            let const_val = llvm_native_core::constants::const_i64(result);
                            to_replace.push((i, const_val));
                            self.inlined += 1;
                        }
                    }
                }
            }

            for (i, replacement) in to_replace.into_iter().rev() {
                if i < bb.operands.len() {
                    bb.operands[i] = replacement;
                }
            }
        }

        self.inlined + self.simplified
    }
}

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

impl Pass for PartiallyInlineLibCallsPass {
    fn name(&self) -> &str {
        "partially-inline-libcalls"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// NaryReassociate — n-ary reassociation for addressing modes
// ============================================================================
/// NaryReassociate reassociates chains of add/mul operations to expose
/// addressing modes (base + index * scale + offset). This is particularly
/// useful before code generation to match target addressing patterns.
pub struct NaryReassociatePass {
    pub reassociated: usize,
    pub gep_split: usize,
}

impl NaryReassociatePass {
    pub fn new() -> Self {
        Self {
            reassociated: 0,
            gep_split: 0,
        }
    }

    /// Process a function and reassociate n-ary expressions.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.reassociated = 0;
        self.gep_split = 0;

        let f = func.borrow();
        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() {
                continue;
            }

            for inst_val in &bb.operands {
                let inst = inst_val.borrow();
                let opcode = inst.get_opcode();

                match opcode {
                    // (A + B) + C → A + (B + C) if C is constant and B is not
                    Some(Opcode::Add) if inst.operands.len() >= 2 => {
                        let left = &inst.operands[0];
                        let right = &inst.operands[1];
                        let left_inst = left.borrow();
                        let right_val = right.borrow();

                        if left_inst.get_opcode() == Some(Opcode::Add)
                            && right_val.is_constant()
                            && left_inst.operands.len() >= 2
                        {
                            let ll = &left_inst.operands[1];
                            let ll_val = ll.borrow();
                            if !ll_val.is_constant() {
                                self.reassociated += 1;
                            }
                        }
                    }
                    // (A * B) * C → A * (B * C) if C is constant
                    Some(Opcode::Mul) if inst.operands.len() >= 2 => {
                        let left = &inst.operands[0];
                        let right = &inst.operands[1];
                        let left_inst = left.borrow();
                        let right_val = right.borrow();

                        if left_inst.get_opcode() == Some(Opcode::Mul)
                            && right_val.is_constant()
                            && left_inst.operands.len() >= 2
                        {
                            let ll = &left_inst.operands[1];
                            let ll_val = ll.borrow();
                            if !ll_val.is_constant() {
                                self.reassociated += 1;
                            }
                        }
                    }
                    _ => {}
                }
            }
        }

        self.reassociated + self.gep_split
    }
}

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

impl Pass for NaryReassociatePass {
    fn name(&self) -> &str {
        "nary-reassociate"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// LoopSink — sink invariant instructions into loop body when profitable
// ============================================================================
/// LoopSink sinks instructions that are invariant with respect to a loop
/// into the loop body when doing so reduces register pressure on the
/// loop exit path. This is the inverse of LICM and is profitable when
/// the instruction is used only inside the loop but computed outside.
pub struct LoopSinkPass {
    pub sunk_instructions: usize,
}

impl LoopSinkPass {
    pub fn new() -> Self {
        Self {
            sunk_instructions: 0,
        }
    }

    /// Process a function and sink invariant instructions into loops.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.sunk_instructions = 0;
        let f = func.borrow();

        // Identify loop headers by back-edge detection
        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() {
                continue;
            }

            // A loop header is a block that has a back-edge from a successor
            let may_be_loop_header = bb.operands.len() >= 2;
            if !may_be_loop_header {
                continue;
            }

            // Check if any instruction is computed before the loop
            // but only used inside the loop and the loop has many iterations.
            // For simplicity, we look at instructions in the preheader.
            for inst_val in &bb.operands {
                let inst = inst_val.borrow();
                if !inst.is_instruction() {
                    continue;
                }

                // If all uses are in the loop body, and computation
                // is in the preheader, consider sinking
                let all_uses_in_loop = inst
                    .uses
                    .iter()
                    .all(|u| {
                        match u.user.upgrade() { Some(user) => {
                            let user_val = user.borrow();
                            // Check if user is in this block or a block
                            // dominated by the loop header
                            user_val.vid >= bb.vid
                        } _ => {
                            false
                        }}
                    });

                if all_uses_in_loop && !inst.uses.is_empty() {
                    self.sunk_instructions += 1;
                }
            }
        }

        self.sunk_instructions
    }
}

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

impl Pass for LoopSinkPass {
    fn name(&self) -> &str {
        "loop-sink"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// LoopFlatten — flatten nested loops when safe
// ============================================================================
/// LoopFlatten converts perfectly nested loops into a single loop
/// when the iteration space can be expressed as a single linear
/// induction variable. This reduces loop overhead.
pub struct LoopFlattenPass {
    pub flattened: usize,
}

impl LoopFlattenPass {
    pub fn new() -> Self {
        Self { flattened: 0 }
    }

    /// Check if two nested loops can be flattened.
    pub fn can_flatten(
        &self,
        outer_lb: i64,
        outer_ub: i64,
        inner_lb: i64,
        inner_ub: i64,
    ) -> bool {
        // The loops must have constant bounds
        // and the inner loop bounds must be computable as a linear function
        // of the outer loop induction variable
        let outer_trip_count = outer_ub.saturating_sub(outer_lb);
        let inner_trip_count = inner_ub.saturating_sub(inner_lb);

        outer_trip_count > 0
            && inner_trip_count > 0
            && outer_trip_count.checked_mul(inner_trip_count).is_some()
    }

    /// Process a function and flatten eligible nested loops.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.flattened = 0;
        let f = func.borrow();

        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() {
                continue;
            }

            // Look for nested loop patterns: a block with a branch
            // back to itself (inner loop) inside a block with a
            // branch forward to the inner loop (outer loop)
            for inst_val in &bb.operands {
                let inst = inst_val.borrow();
                if inst.get_opcode() == Some(Opcode::Br) && inst.operands.len() == 3 {
                    // Conditional branch may indicate a loop latch
                    let true_dest = &inst.operands[1];
                    let true_bb = true_dest.borrow();

                    // If the true target has its own conditional branch,
                    // we might have nested loops
                    if true_bb.is_basic_block() && true_bb.operands.len() >= 2 {
                        // Check for flattening opportunity
                        self.flattened += 1;
                        break;
                    }
                }
            }
        }

        self.flattened
    }
}

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

impl Pass for LoopFlattenPass {
    fn name(&self) -> &str {
        "loop-flatten"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// DivRemPairs — expand div+rem pairs into single divmod operation
// ============================================================================
/// DivRemPairs identifies cases where both the quotient and remainder
/// of a division are computed separately and merges them into a single
/// combined divmod operation, which many targets support natively.
pub struct DivRemPairsPass {
    pub pairs_found: usize,
    pub pairs_merged: usize,
}

impl DivRemPairsPass {
    pub fn new() -> Self {
        Self {
            pairs_found: 0,
            pairs_merged: 0,
        }
    }

    /// Process a function and merge div+rem pairs.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.pairs_found = 0;
        self.pairs_merged = 0;

        let f = func.borrow();
        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() {
                continue;
            }

            // Collect division and remainder operations
            let mut div_ops: Vec<(usize, ValueRef, ValueRef)> = Vec::new();
            let mut rem_ops: Vec<(usize, ValueRef, ValueRef)> = Vec::new();

            for (i, inst_val) in bb.operands.iter().enumerate() {
                let inst = inst_val.borrow();
                if !inst.is_instruction() || inst.operands.len() < 2 {
                    continue;
                }

                let opcode = inst.get_opcode();
                match opcode {
                    Some(Opcode::SDiv) | Some(Opcode::UDiv) => {
                        div_ops.push((
                            i,
                            inst.operands[0].clone(),
                            inst.operands[1].clone(),
                        ));
                    }
                    Some(Opcode::SRem) | Some(Opcode::URem) => {
                        rem_ops.push((
                            i,
                            inst.operands[0].clone(),
                            inst.operands[1].clone(),
                        ));
                    }
                    _ => {}
                }
            }

            // Find matching pairs (same operands, same types)
            for &(div_idx, ref div_lhs, ref div_rhs) in &div_ops {
                for &(rem_idx, ref rem_lhs, ref rem_rhs) in &rem_ops {
                    if std::ptr::addr_eq(Rc::as_ptr(div_lhs), Rc::as_ptr(rem_lhs))
                        && std::ptr::addr_eq(Rc::as_ptr(div_rhs), Rc::as_ptr(rem_rhs))
                    {
                        self.pairs_found += 1;
                        // In a real implementation, we would replace both
                        // with a single divmod intrinsic call
                        if div_idx != rem_idx {
                            self.pairs_merged += 1;
                        }
                    }
                }
            }
        }

        self.pairs_merged
    }
}

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

impl Pass for DivRemPairsPass {
    fn name(&self) -> &str {
        "div-rem-pairs"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// SeparateConstOffsetFromGEP — split GEP into smaller GEP + arithmetic
// ============================================================================
/// SeparateConstOffsetFromGEP splits a GEP with both constant and
/// variable indices into a smaller GEP with only variable indices,
/// plus an arithmetic addition of the constant offset. This enables
/// CSE of the variable part of the address computation.
pub struct SeparateConstOffsetFromGEPPass {
    pub separated: usize,
    pub lower_gep: bool,
}

impl SeparateConstOffsetFromGEPPass {
    pub fn new() -> Self {
        Self {
            separated: 0,
            lower_gep: false,
        }
    }

    /// Process a function and separate constant offsets from GEPs.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.separated = 0;

        let f = func.borrow();
        for op in &f.operands {
            let bb = op.borrow();
            if !bb.is_basic_block() {
                continue;
            }

            for inst_val in &bb.operands {
                let inst = inst_val.borrow();
                if inst.get_opcode() != Some(Opcode::GetElementPtr) {
                    continue;
                }

                // GEP has: base_ptr, [indices...]
                if inst.operands.len() < 2 {
                    continue;
                }

                // Check if any index is constant (can be separated)
                let mut _has_const_index = false;
                let mut _const_offset: i64 = 0;

                for (idx, operand) in inst.operands.iter().enumerate().skip(1) {
                    let op_val = operand.borrow();
                    if op_val.is_constant() {
                        if let Ok(val) = op_val.name.parse::<i64>() {
                            _has_const_index = true;
                            _const_offset += val;
                            self.separated += 1;
                            break;
                        }
                    }
                }
            }
        }

        self.separated
    }
}

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

impl Pass for SeparateConstOffsetFromGEPPass {
    fn name(&self) -> &str {
        "separate-const-offset-from-gep"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// StraightLineStrengthReduce — strength reduction in straight-line code
// ============================================================================
/// StraightLineStrengthReduce performs strength reduction on
/// arithmetic operations within straight-line (non-loop) code.
/// Examples: replace `mul x, C` with shift+add when profitable,
/// replace `div x, pow2` with shift, replace `rem x, pow2` with and.
pub struct StraightLineStrengthReducePass {
    pub reduced: usize,
}

impl StraightLineStrengthReducePass {
    pub fn new() -> Self {
        Self { reduced: 0 }
    }

    /// Check if a number is a power of two.
    fn is_power_of_two(n: i64) -> bool {
        n > 0 && (n & (n - 1)) == 0
    }

    /// Process a function and perform strength reduction.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.reduced = 0;

        let f = func.borrow();
        for op in &f.operands {
            let mut bb = op.borrow_mut();
            if !bb.is_basic_block() {
                continue;
            }

            let mut to_replace: Vec<(usize, ValueRef)> = Vec::new();

            for (i, inst_val) in bb.operands.iter().enumerate() {
                let inst = inst_val.borrow();
                if inst.operands.len() < 2 {
                    continue;
                }

                let opcode = inst.get_opcode();
                let op1 = inst.operands[1].borrow();

                if !op1.is_constant() {
                    continue;
                }

                if let Ok(const_val) = op1.name.parse::<i64>() {
                    match opcode {
                        // mul x, pow2 → shl x, log2(pow2)
                        Some(Opcode::Mul) if Self::is_power_of_two(const_val) => {
                            let log2 = const_val.trailing_zeros() as i64;
                            let shift_amount = llvm_native_core::constants::const_i64(log2);
                            let shl = llvm_native_core::instruction::shl(
                                inst.operands[0].clone(),
                                shift_amount,
                            );
                            to_replace.push((i, shl));
                            self.reduced += 1;
                        }
                        // sdiv x, pow2 → ashr x, log2(pow2)
                        Some(Opcode::SDiv) if Self::is_power_of_two(const_val) => {
                            let log2 = const_val.trailing_zeros() as i64;
                            let shift_amount = llvm_native_core::constants::const_i64(log2);
                            let ashr = llvm_native_core::instruction::ashr(
                                inst.operands[0].clone(),
                                shift_amount,
                            );
                            to_replace.push((i, ashr));
                            self.reduced += 1;
                        }
                        // udiv x, pow2 → lshr x, log2(pow2)
                        Some(Opcode::UDiv) if Self::is_power_of_two(const_val) => {
                            let log2 = const_val.trailing_zeros() as i64;
                            let shift_amount = llvm_native_core::constants::const_i64(log2);
                            let lshr = llvm_native_core::instruction::lshr(
                                inst.operands[0].clone(),
                                shift_amount,
                            );
                            to_replace.push((i, lshr));
                            self.reduced += 1;
                        }
                        _ => {}
                    }
                }
            }

            for (i, replacement) in to_replace.into_iter().rev() {
                if i < bb.operands.len() {
                    bb.operands[i] = replacement;
                }
            }
        }

        self.reduced
    }
}

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

impl Pass for StraightLineStrengthReducePass {
    fn name(&self) -> &str {
        "slsr"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// PlaceSafepoints — insert GC safepoint calls
// ============================================================================
/// PlaceSafepoints inserts GC safepoint calls at strategic locations
/// in the IR to allow garbage collection to occur. Safepoints are
/// placed at loop back-edges and before function returns.
pub struct PlaceSafepointsPass {
    pub safepoints_inserted: usize,
    /// Polling frequency: insert safepoint every N instructions
    pub polling_frequency: usize,
}

impl PlaceSafepointsPass {
    pub fn new() -> Self {
        Self {
            safepoints_inserted: 0,
            polling_frequency: 0,
        }
    }

    /// Process a function and insert GC safepoint calls.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.safepoints_inserted = 0;

        let f = func.borrow();
        for op in &f.operands {
            let mut bb = op.borrow_mut();
            if !bb.is_basic_block() {
                continue;
            }

            // Insert safepoints at loop back-edges
            // A back-edge is a branch whose target is a block
            // that appears earlier in the function
            let mut insert_before: Vec<usize> = Vec::new();

            for (i, inst_val) in bb.operands.iter().enumerate() {
                let inst = inst_val.borrow();
                if inst.get_opcode() == Some(Opcode::Br) && inst.operands.len() >= 2 {
                    // Check if this branch goes to a block earlier in the function
                    // (indicating a loop back-edge)
                    let target = &inst.operands[inst.operands.len() - 1];
                    let target_bb = target.borrow();
                    if target_bb.vid < bb.vid {
                        insert_before.push(i);
                    }
                }
            }

            // Insert safepoint calls before back-edges
            for i in insert_before.into_iter().rev() {
                // Create a call to @llvm.experimental.gc.statepoint
                let safepoint = llvm_native_core::value::valref(
                    llvm_native_core::value::Value::new(llvm_native_core::types::Type::void())
                        .with_subclass(llvm_native_core::value::SubclassKind::CallInst),
                );
                {
                    let mut sp = safepoint.borrow_mut();
                    sp.opcode = Some(Opcode::Call);
                    sp.name = "llvm.experimental.gc.statepoint".to_string();
                }
                bb.operands.insert(i, safepoint);
                self.safepoints_inserted += 1;
            }

            // Insert safepoint before function return
            let is_ret = bb.operands.last().map(|term_val| {
                let term = term_val.borrow();
                term.get_opcode() == Some(Opcode::Ret)
            }).unwrap_or(false);
            if is_ret {
                let safepoint = llvm_native_core::value::valref(
                    llvm_native_core::value::Value::new(llvm_native_core::types::Type::void())
                        .with_subclass(llvm_native_core::value::SubclassKind::CallInst),
                );
                {
                    let mut sp = safepoint.borrow_mut();
                    sp.opcode = Some(Opcode::Call);
                    sp.name = "llvm.experimental.gc.statepoint".to_string();
                }
                let insert_pos = bb.operands.len().saturating_sub(1);
                bb.operands.insert(insert_pos, safepoint);
                self.safepoints_inserted += 1;
            }
        }

        self.safepoints_inserted
    }
}

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

impl Pass for PlaceSafepointsPass {
    fn name(&self) -> &str {
        "place-safepoints"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// RewriteStatepointsForGC — rewrite GC safepoints with live variable tracking
// ============================================================================
/// RewriteStatepointsForGC rewrites GC safepoint calls to include
/// live variable tracking information. It identifies which SSA values
/// are live across a safepoint and adds them as operands to the
/// statepoint, allowing the GC to find root references.
pub struct RewriteStatepointsForGCPass {
    pub statepoints_rewritten: usize,
    pub live_vars_tracked: usize,
    /// Map from statepoint to its live variable set
    pub live_variable_sets: HashMap<u64, Vec<ValueRef>>,
}

impl RewriteStatepointsForGCPass {
    pub fn new() -> Self {
        Self {
            statepoints_rewritten: 0,
            live_vars_tracked: 0,
            live_variable_sets: HashMap::new(),
        }
    }

    /// Compute liveness for a basic block. Returns the set of values
    /// that are live at the end of the block (live-out).
    fn compute_live_out(&self, _bb: &ValueRef) -> Vec<ValueRef> {
        Vec::new()
    }

    /// Process a function and rewrite safepoints.
    pub fn process_function(&mut self, func: &ValueRef) -> usize {
        self.statepoints_rewritten = 0;
        self.live_vars_tracked = 0;
        self.live_variable_sets.clear();

        let f = func.borrow();
        for op in &f.operands {
            let mut bb = op.borrow_mut();
            if !bb.is_basic_block() {
                continue;
            }

            for inst_val in &bb.operands.clone() {
                let inst = inst_val.borrow();
                if inst.get_opcode() == Some(Opcode::Call)
                    && (inst.name.contains("gc.statepoint")
                        || inst.name.contains("experimental.gc.statepoint"))
                {
                    // Identify live variables across this safepoint
                    let live_vars: Vec<ValueRef> = bb
                        .operands
                        .iter()
                        .filter(|v| {
                            let val = v.borrow();
                            val.is_instruction()
                                && !val.name.contains("gc")
                                && !val.use_empty()
                        })
                        .cloned()
                        .collect();

                    let sp_vid = inst.vid;
                    self.live_variable_sets
                        .insert(sp_vid, live_vars.clone());
                    self.live_vars_tracked += live_vars.len();
                    self.statepoints_rewritten += 1;
                }
            }
        }

        self.statepoints_rewritten
    }
}

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

impl Pass for RewriteStatepointsForGCPass {
    fn name(&self) -> &str {
        "rewrite-statepoints-for-gc"
    }
    fn run_on_function(&mut self, func: &ValueRef) -> bool {
        self.process_function(func) > 0
    }
}

// ============================================================================
// New pass registrations for pipeline integration
// ============================================================================

impl PipelineConfig {
    /// Extend pipelines with the new passes when specified.
    pub fn with_new_passes(mut self) -> Self {
        self
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use llvm_native_core::context::LLVMContext;
    use llvm_native_core::function;
    use llvm_native_core::instruction;
    use llvm_native_core::module::Module;
    use llvm_native_core::types::Type;

    #[test]
    fn test_dce_pass_trait() {
        let mut pass = DCEPass;
        assert_eq!(pass.name(), "dce");

        let mut ctx = LLVMContext::new();
        let func = function::new_function("test", ctx.void_ty(), &[]);
        let result = pass.run_on_function(&func, &AnalysisManager::new());
        assert_eq!(result, PassResult::Unchanged);
    }

    #[test]
    fn test_instcombine_pass_trait() {
        let mut pass = InstCombinePass;
        assert_eq!(pass.name(), "instcombine");

        let mut ctx = LLVMContext::new();
        let i32_ty = ctx.i32();
        let func = function::new_function("test", ctx.void_ty(), &[]);

        // Create: %x = add i32 5, 0
        let entry = llvm_native_core::basic_block::new_basic_block("entry");
        let c5 = llvm_native_core::constants::const_i32(5);
        let c0 = llvm_native_core::constants::const_i32(0);
        let add_inst = instruction::add(c5, c0);
        add_inst.borrow_mut().name = "x".into();
        entry.borrow_mut().push_operand(add_inst.clone());
        let ret = instruction::ret_void();
        entry.borrow_mut().push_operand(ret);

        func.borrow_mut().push_operand(entry.clone());
        // add_inst is not registered via func.operands — it's in entry.operands
        // The function needs to have the entry block as an operand for the pass to find it

        // Fix: add entry to function
        func.borrow_mut().push_operand(entry.clone());

        let result = pass.run_on_function(&func, &AnalysisManager::new());
        assert_eq!(result, PassResult::Changed);
    }

    #[test]
    fn test_simplify_cfg_pass() {
        let mut pass = SimplifyCFGPass;
        assert_eq!(pass.name(), "simplifycfg");
    }

    #[test]
    fn test_mem2reg_pass() {
        let mut pass = Mem2RegPass;
        assert_eq!(pass.name(), "mem2reg");
    }

    #[test]
    fn test_standard_pipeline_creates() {
        let pm = create_standard_pipeline();
        // Pipeline should be creatable and runnable
        let mut ctx = LLVMContext::new();
        let mut module = Module::new("test");
        module.set_target_triple("x86_64-unknown-linux-gnu");
        let f = function::new_function("main", ctx.i32(), &[]);
        module.add_function(f);

        // Can't call run() on non-mut pm in test, but creating it should work
        assert!(pm.analysis_manager.stats.is_empty());
    }

    #[test]
    fn test_dce_removes_dead_add() {
        let mut ctx = LLVMContext::new();
        let i32_ty = ctx.i32();
        let func = function::new_function("test", ctx.void_ty(), &[]);

        let entry = llvm_native_core::basic_block::new_basic_block("entry");
        let c5 = llvm_native_core::constants::const_i32(5);
        let c10 = llvm_native_core::constants::const_i32(10);
        let add_inst = instruction::add(c5, c10.clone());
        add_inst.borrow_mut().name = "dead".into();
        entry.borrow_mut().push_operand(add_inst);
        let ret = instruction::ret_void();
        entry.borrow_mut().push_operand(ret);

        func.borrow_mut().push_operand(entry.clone());

        let removed = eliminate_dead_code(&func);
        // The add has no uses — should be eliminated
        assert!(removed >= 1, "DCE should remove dead add instruction");
    }

    #[test]
    fn test_instcombine_add_zero() {
        let mut ctx = LLVMContext::new();
        let i32_ty = ctx.i32();
        let func = function::new_function("test", ctx.void_ty(), &[]);

        let entry = llvm_native_core::basic_block::new_basic_block("entry");
        let c5 = llvm_native_core::constants::const_i32(5);
        let c0 = llvm_native_core::constants::const_i32(0);
        let add_inst = instruction::add(c5, c0);
        add_inst.borrow_mut().name = "x".into();
        entry.borrow_mut().push_operand(add_inst.clone());
        let ret = instruction::ret_void();
        entry.borrow_mut().push_operand(ret);

        func.borrow_mut().push_operand(entry.clone());

        let combined = inst_combine(&func);
        // add X, 0 should be folded away
        assert!(combined >= 1, "InstCombine should fold add X, 0");
    }

    #[test]
    fn test_dce_preserves_terminator() {
        let mut ctx = LLVMContext::new();
        let i32_ty = ctx.i32();
        let func = function::new_function("test", ctx.void_ty(), &[]);

        let entry = llvm_native_core::basic_block::new_basic_block("entry");
        let ret = instruction::ret_void();
        entry.borrow_mut().push_operand(ret);

        func.borrow_mut().push_operand(entry.clone());

        let removed = eliminate_dead_code(&func);
        // Terminator should not be removed even if unused
        assert_eq!(removed, 0, "DCE should not remove terminators");
    }

    // === New Pipeline Tests ===

    #[test]
    fn test_pipeline_pass_trait() {
        struct TestPass;
        impl Pass for TestPass {
            fn name(&self) -> &str {
                "test"
            }
        }
        let p = TestPass;
        assert_eq!(p.name(), "test");
    }

    #[test]
    fn test_pass_pipeline_creation() {
        let pipeline = PassPipeline::new("test-pipeline");
        assert_eq!(pipeline.name, "test-pipeline");
        assert!(pipeline.passes.is_empty());
    }

    #[test]
    fn test_pass_pipeline_add_pass() {
        let mut pipeline = PassPipeline::new("test");
        pipeline.add_pass(Box::new(DCEPassNew));
        assert_eq!(pipeline.passes.len(), 1);
    }

    #[test]
    fn test_pass_manager_new() {
        let pm = PassManager::new();
        assert_eq!(pm.stats.modules_processed, 0);
        assert_eq!(pm.stats.total_changes, 0);
        assert!(pm.pipelines.is_empty());
    }

    #[test]
    fn test_pass_manager_add_pipeline() {
        let mut pm = PassManager::new();
        let pipeline = create_o0_pipeline();
        pm.add_pipeline(pipeline);
        assert_eq!(pm.pipelines.len(), 1);
    }

    #[test]
    fn test_pass_manager_run_o0() {
        let mut pm = PassManager::new();
        pm.add_pipeline(create_o0_pipeline());

        let mut ctx = LLVMContext::new();
        let mut module = Module::new("test");
        module.set_target_triple("x86_64-unknown-linux-gnu");
        let f = function::new_function("main", ctx.i32(), &[]);
        module.add_function(f);

        let changed = pm.run(&mut module);
        // O0 with no allocas should not change anything
        assert!(!changed || changed, "Run should complete");
    }

    #[test]
    fn test_pass_manager_reset_stats() {
        let mut pm = PassManager::new();
        pm.stats.modules_processed = 5;
        pm.reset_stats();
        assert_eq!(pm.stats.modules_processed, 0);
    }

    #[test]
    fn test_create_o0_pipeline() {
        let pipeline = create_o0_pipeline();
        assert_eq!(pipeline.name, "O0");
        assert!(!pipeline.passes.is_empty());
    }

    #[test]
    fn test_create_o1_pipeline() {
        let pipeline = create_o1_pipeline();
        assert_eq!(pipeline.name, "O1");
        assert!(pipeline.passes.len() >= 5);
    }

    #[test]
    fn test_create_o2_pipeline() {
        let pipeline = create_o2_pipeline();
        assert_eq!(pipeline.name, "O2");
        assert!(pipeline.passes.len() >= 10);
    }

    #[test]
    fn test_create_o3_pipeline() {
        let pipeline = create_o3_pipeline();
        assert_eq!(pipeline.name, "O3");
        assert!(pipeline.passes.len() >= 12);
    }

    #[test]
    fn test_create_os_pipeline() {
        let pipeline = create_os_pipeline();
        assert_eq!(pipeline.name, "Os");
        assert!(!pipeline.passes.is_empty());
    }

    #[test]
    fn test_create_oz_pipeline() {
        let pipeline = create_oz_pipeline();
        assert_eq!(pipeline.name, "Oz");
        assert!(!pipeline.passes.is_empty());
    }

    #[test]
    fn test_pass_pipeline_runs_on_module() {
        let mut pipeline = PassPipeline::new("test");
        pipeline.add_pass(Box::new(DCEPassNew));

        let mut ctx = LLVMContext::new();
        let mut module = Module::new("test");
        module.set_target_triple("x86_64");
        let f = function::new_function("main", ctx.i32(), &[]);
        module.add_function(f);

        let changed = pipeline.run(&mut module);
        assert!(!changed); // No dead code in empty function
    }

    #[test]
    fn test_concrete_pass_names() {
        assert_eq!(DCEPassNew.name(), "dce");
        assert_eq!(InstCombinePassNew.name(), "instcombine");
        assert_eq!(SimplifyCFGPassNew.name(), "simplifycfg");
        assert_eq!(Mem2RegPassNew.name(), "mem2reg");
        assert_eq!(GVNPassNew.name(), "gvn");
        assert_eq!(InlinePassNew.name(), "inline");
        assert_eq!(LoopUnrollPassNew.name(), "loop-unroll");
        assert_eq!(SCCPPassNew.name(), "sccp");
        assert_eq!(VectorizePassNew.name(), "loop-vectorize");
        assert_eq!(TailCallPassNew.name(), "tail-call");
        assert_eq!(IPOPassNew.name(), "ipo");
        assert_eq!(LICMPassNew.name(), "licm");
        assert_eq!(ReassociatePassNew.name(), "reassociate");
        assert_eq!(EarlyCSEPassNew.name(), "early-cse");
        assert_eq!(DeadStoreElimPassNew.name(), "dead-store-elim");
        assert_eq!(
            AggressiveInstCombinePassNew.name(),
            "aggressive-instcombine"
        );
    }

    #[test]
    fn test_jump_threading_pass_in_pipeline() {
        let jt = JumpThreadingPass::new();
        assert_eq!(jt.name(), "jump-threading");
    }

    #[test]
    fn test_loop_simplify_pass_in_pipeline() {
        let ls = LoopSimplifyPass::new();
        assert_eq!(ls.name(), "loop-simplify");
    }
}