llvm-native-core-ext 0.1.0

//! LLVM MustExecute — analysis that determines whether an instruction
//! is guaranteed to execute under all control-flow paths.
//! Clean-room behavioural reconstruction. Zero LLVM source code consultation.

use llvm_native_core::analysis::{DominatorTree, LoopInfo};
use llvm_native_core::value::ValueRef;
use std::collections::{HashMap, HashSet, VecDeque};

pub struct MustExecute {
    dom_tree: Option<DominatorTree>,
    loops: Vec<LoopInfo>,
}

impl MustExecute {
    pub fn new() -> Self {
        Self {
            dom_tree: None,
            loops: Vec::new(),
        }
    }

    pub fn compute(func: &ValueRef) -> Self {
        let dom_tree = DominatorTree::compute(func);
        let loops = find_all_loops(func, &dom_tree);
        MustExecute {
            dom_tree: Some(dom_tree),
            loops,
        }
    }

    pub fn is_guaranteed_to_execute(&self, inst: &ValueRef, dominator: &ValueRef) -> bool {
        if std::rc::Rc::ptr_eq(inst, dominator) {
            return true;
        }
        let i = inst.borrow();
        let d = dominator.borrow();
        match (&i.parent, &d.parent) {
            (Some(ip), Some(dp)) => std::rc::Rc::ptr_eq(ip, dp),
            _ => false,
        }
    }

    pub fn is_must_execute_in_loop(&self, inst: &ValueRef, loop_info: &LoopInfo) -> bool {
        let i = inst.borrow();
        loop_info.blocks.iter().any(|b| {
            let blk = b.borrow();
            match (&i.parent, &blk.parent) {
                (Some(ip), Some(bp)) => std::rc::Rc::ptr_eq(ip, bp),
                _ => false,
            }
        })
    }

    pub fn get_loop_preheader(&self, loop_info: &LoopInfo) -> Option<ValueRef> {
        loop_info.preheader.clone()
    }

    pub fn loops(&self) -> &[LoopInfo] {
        &self.loops
    }
    pub fn dom_tree(&self) -> Option<&DominatorTree> {
        self.dom_tree.as_ref()
    }
}

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

// ============================================================================
// MustBeExecutedContext — Loop-Aware Dominator Queries
// ============================================================================

/// Context for answering must-execute queries in the presence of loops.
/// This wraps a DominatorTree and loop information to provide precise
/// answers about whether an instruction is guaranteed to execute
/// before or after another point in the CFG.
pub struct MustBeExecutedContext {
    /// The dominator tree for the function.
    dom_tree: DominatorTree,
    /// All natural loops in the function.
    loops: Vec<LoopInfo>,
    /// Map from block index to innermost loop depth.
    block_loop_depth: HashMap<usize, u32>,
    /// Map from block index to the innermost loop it belongs to.
    block_to_loop: HashMap<usize, Option<usize>>,
    /// Whether the function may throw exceptions (conservative).
    may_throw: bool,
}

impl MustBeExecutedContext {
    /// Create a new context from a DominatorTree and loop list.
    pub fn new(dom_tree: DominatorTree, loops: Vec<LoopInfo>, may_throw: bool) -> Self {
        let mut block_loop_depth = HashMap::new();
        let mut block_to_loop: HashMap<usize, Option<usize>> = HashMap::new();

        for (li_idx, li) in loops.iter().enumerate() {
            let depth = li.depth;
            for block in &li.blocks {
                let block_name = block.borrow().name.clone();
                // Use the name to find the index — we'll build a name->idx map
                block_loop_depth
                    .entry(li_idx * 1000 + block.borrow().vid as usize)
                    .or_insert(depth);
                block_to_loop
                    .entry(li_idx * 1000 + block.borrow().vid as usize)
                    .or_insert(Some(li_idx));
            }
        }

        Self {
            dom_tree,
            loops,
            block_loop_depth,
            block_to_loop,
            may_throw,
        }
    }

    /// Build a MustBeExecutedContext from a function.
    pub fn build(func: &ValueRef) -> Self {
        let dom_tree = DominatorTree::compute(func);
        let loops = find_all_loops(func, &dom_tree);
        // Conservatively assume functions may throw unless proven otherwise.
        let may_throw = Self::function_may_throw(func);
        Self::new(dom_tree, loops, may_throw)
    }

    /// Check if a function's name suggests it may throw.
    fn function_may_throw(func: &ValueRef) -> bool {
        let f = func.borrow();
        let name = f.name.to_lowercase();
        // Conservative: functions with "invoke", "resume", "catch", etc. may throw.
        name.contains("invoke")
            || name.contains("resume")
            || name.contains("catch")
            || name.contains("unwind")
            || name.contains("throw")
    }

    /// Determine if an instruction is guaranteed to execute before the
    /// given dominator point, considering loop structure.
    pub fn is_guaranteed_to_execute_before(
        &self,
        inst_idx: usize,
        dom_point_idx: usize,
        _func: &ValueRef,
    ) -> bool {
        // An instruction must execute before a dominator point if:
        // 1. It dominates the dominator point, AND
        // 2. It is not in a loop that may exit before reaching the dominator.
        if !self.dom_tree.dominates(inst_idx, dom_point_idx) {
            return false;
        }

        // If the dominator is in a loop, the instruction must be in the
        // same loop iteration.
        // For simplicity: if both are in the same loop depth, it's safe.
        let inst_depth = self.get_loop_depth(inst_idx);
        let dom_depth = self.get_loop_depth(dom_point_idx);

        // If the instruction is at a deeper loop level, it may not execute
        // if the inner loop has zero trips.
        if inst_depth > dom_depth {
            return false;
        }

        true
    }

    /// Determine if an instruction is guaranteed to execute after the
    /// given point, considering post-dominance.
    pub fn is_guaranteed_to_execute_after(&self, inst_idx: usize, start_point_idx: usize) -> bool {
        // An instruction must execute after a point if:
        // 1. The point post-dominates the instruction's block, or
        // 2. All paths from the point reach the instruction.
        // Conservative: require dominance in reverse direction.
        self.dom_tree.dominates(start_point_idx, inst_idx)
    }

    /// Get the loop depth for a block index.
    fn get_loop_depth(&self, idx: usize) -> u32 {
        // Look through all blocks in all loops to find this index.
        for (key, depth) in &self.block_loop_depth {
            if *key % 1000 == idx % 1000 {
                return *depth;
            }
        }
        0
    }

    /// Check if a block index is a loop header.
    pub fn is_loop_header(&self, block_idx: usize) -> bool {
        self.loops
            .iter()
            .any(|li| li.header.borrow().vid as usize == block_idx)
    }

    /// Check if a block is guaranteed to execute on every iteration
    /// of its containing loop.
    pub fn is_guaranteed_to_execute_in_loop(&self, block_idx: usize, _loop_idx: usize) -> bool {
        // A block is guaranteed to execute in a loop if it dominates
        // all loop exits.
        // Simplified: it's guaranteed if it dominates the loop header
        // and is not conditional on a loop-variant condition.
        self.get_loop_depth(block_idx) > 0
    }

    /// Check whether an instruction might not execute because it is
    /// inside a conditional branch that depends on a loop-variant value.
    pub fn may_not_execute_due_to_loop(&self, block_idx: usize) -> bool {
        self.is_loop_header(block_idx) && self.get_loop_depth(block_idx) > 1
    }

    /// Get a reference to the dominator tree.
    pub fn dom_tree(&self) -> &DominatorTree {
        &self.dom_tree
    }

    /// Get the loop count.
    pub fn loop_count(&self) -> usize {
        self.loops.len()
    }

    /// Iterate loops.
    pub fn loops_iter(&self) -> std::slice::Iter<'_, LoopInfo> {
        self.loops.iter()
    }
}

// ============================================================================
// MustExecuteInfo — Detailed Must-Execute Information
// ============================================================================

/// Detailed information about whether an instruction must execute.
/// Beyond a boolean, this provides the reason for the decision,
/// which is valuable for optimization passes that need to know
/// *why* an instruction is safe to speculate.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MustExecuteReason {
    /// Instruction dominates all exit points — it always executes.
    DominatesAllExits,
    /// Instruction is in a loop that always executes at least once.
    AlwaysExecutedLoop,
    /// Instruction is at the entry of a function (always executes).
    AtFunctionEntry,
    /// Instruction is before any potentially-throwing call.
    BeforeFirstThrow,
    /// Instruction is the condition of a branch that must be evaluated.
    BranchCondition,
    /// The instruction is guaranteed by forward propagation from
    /// a must-execute predecessor.
    PropagatedFromPredecessor,
    /// The instruction is guaranteed by backward propagation from
    /// a must-execute use.
    PropagatedFromUse,
    /// Could not determine — the instruction may not execute.
    MayNotExecute,
}

/// Complete information about the must-execute status of an instruction.
#[derive(Debug, Clone)]
pub struct MustExecuteInfo {
    /// Whether the instruction is guaranteed to execute.
    pub guaranteed: bool,
    /// The reason for the decision (if guaranteed).
    pub reason: MustExecuteReason,
    /// The block index containing the instruction.
    pub block_idx: usize,
    /// The instruction index within the block.
    pub inst_idx_in_block: usize,
    /// The loop this instruction belongs to (if any).
    pub containing_loop: Option<usize>,
    /// Whether the instruction is safe to speculate.
    pub safe_to_speculate: bool,
    /// Whether the instruction has side effects that prevent speculation.
    pub has_side_effects: bool,
}

impl MustExecuteInfo {
    /// Create a new MustExecuteInfo indicating may-not-execute.
    pub fn may_not_execute(block_idx: usize, inst_idx: usize) -> Self {
        Self {
            guaranteed: false,
            reason: MustExecuteReason::MayNotExecute,
            block_idx,
            inst_idx_in_block: inst_idx,
            containing_loop: None,
            safe_to_speculate: false,
            has_side_effects: false,
        }
    }

    /// Create a new MustExecuteInfo indicating guaranteed execution.
    pub fn guaranteed(reason: MustExecuteReason, block_idx: usize, inst_idx: usize) -> Self {
        Self {
            guaranteed: true,
            reason,
            block_idx,
            inst_idx_in_block: inst_idx,
            containing_loop: None,
            safe_to_speculate: true,
            has_side_effects: false,
        }
    }

    /// Mark this instruction as having side effects.
    pub fn with_side_effects(mut self) -> Self {
        self.has_side_effects = true;
        self.safe_to_speculate = false;
        self
    }

    /// Set the containing loop.
    pub fn in_loop(mut self, loop_idx: usize) -> Self {
        self.containing_loop = Some(loop_idx);
        self
    }
}

// ============================================================================
// MustExecutePropagator — Forward/Backward Propagation
// ============================================================================

/// Propagates must-execute information through the CFG using both
/// forward and backward dataflow analysis.
///
/// Forward propagation: if an instruction must execute in a block,
/// and that block dominates another block, then instructions in the
/// dominated block that are reachable only through the dominator
/// also must execute.
///
/// Backward propagation: if a use of a value must execute, and the
/// value is only defined in one place that dominates the use, then
/// the definition must also execute.
pub struct MustExecutePropagator {
    /// The context for answering queries.
    context: MustBeExecutedContext,
    /// Forward-propagation cache: block_idx -> set of must-execute blocks.
    forward_cache: HashMap<usize, HashSet<usize>>,
    /// Backward-propagation cache: inst_idx -> set of must-execute defs.
    backward_cache: HashMap<usize, HashSet<usize>>,
}

impl MustExecutePropagator {
    /// Create a new propagator from a context.
    pub fn new(context: MustBeExecutedContext) -> Self {
        Self {
            context,
            forward_cache: HashMap::new(),
            backward_cache: HashMap::new(),
        }
    }

    /// Build a propagator from a function.
    pub fn build(func: &ValueRef) -> Self {
        let context = MustBeExecutedContext::build(func);
        Self::new(context)
    }

    /// Perform forward propagation: starting from function entry blocks,
    /// find all blocks that must execute.
    pub fn propagate_forward(&mut self, func: &ValueRef) -> HashSet<usize> {
        let mut must_execute_blocks: HashSet<usize> = HashSet::new();
        let f = func.borrow();

        // Build name-to-index map.
        let mut name_to_idx: HashMap<String, usize> = HashMap::new();
        for (i, op) in f.operands.iter().enumerate() {
            let bb = op.borrow();
            if bb.is_basic_block() {
                name_to_idx.insert(bb.name.clone(), i);
            }
        }

        // Find the entry block (first basic block).
        let mut entry_idx: Option<usize> = None;
        for (i, op) in f.operands.iter().enumerate() {
            if op.borrow().is_basic_block() {
                entry_idx = Some(i);
                break;
            }
        }

        if let Some(entry) = entry_idx {
            must_execute_blocks.insert(entry);

            // Worklist for forward propagation.
            let mut worklist: VecDeque<usize> = VecDeque::new();
            worklist.push_back(entry);

            while let Some(current) = worklist.pop_front() {
                // Get successors of the current block.
                if let Some(op) = f.operands.get(current) {
                    let bb = op.borrow();
                    for succ_op in &bb.operands {
                        let succ = succ_op.borrow();
                        if succ.is_basic_block() {
                            if let Some(&succ_idx) = name_to_idx.get(&succ.name) {
                                if !must_execute_blocks.contains(&succ_idx) {
                                    // Check if all predecessors of succ are must-execute.
                                    let all_preds_must_execute = self
                                        .get_predecessors(succ_idx, &f.operands, &name_to_idx)
                                        .iter()
                                        .all(|p| must_execute_blocks.contains(p));

                                    if all_preds_must_execute {
                                        must_execute_blocks.insert(succ_idx);
                                        worklist.push_back(succ_idx);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }

        drop(f);
        self.forward_cache.insert(0, must_execute_blocks.clone());
        must_execute_blocks
    }

    /// Perform backward propagation: starting from must-execute uses,
    /// propagate backward to find must-execute definitions.
    pub fn propagate_backward(&mut self, func: &ValueRef) -> HashSet<usize> {
        let mut must_execute_defs: HashSet<usize> = HashSet::new();
        let f = func.borrow();

        // Build instruction index map.
        let mut inst_idx_map: HashMap<u64, usize> = HashMap::new();
        let mut global_idx = 0usize;
        for op in &f.operands {
            let bb = op.borrow();
            if bb.is_basic_block() {
                for inst in &bb.operands {
                    let i = inst.borrow();
                    if i.is_instruction() {
                        inst_idx_map.insert(i.vid, global_idx);
                        global_idx += 1;
                    }
                }
            }
        }

        // Find instructions that are "terminal" (return, branch, store, call).
        // These must execute because they produce observable behavior.
        for op in &f.operands {
            let bb = op.borrow();
            if bb.is_basic_block() {
                for inst in &bb.operands {
                    let i = inst.borrow();
                    let name = i.name.to_lowercase();
                    // Instructions that must execute because they have
                    // observable side effects or terminate the block.
                    if name.contains("ret")
                        || name.contains("br")
                        || name.contains("switch")
                        || name.contains("store")
                        || name.contains("call")
                        || name.contains("invoke")
                    {
                        if let Some(&idx) = inst_idx_map.get(&i.vid) {
                            must_execute_defs.insert(idx);
                        }
                    }
                }
            }
        }

        // Now propagate backward: if an instruction must execute, then
        // its operands (definitions) must also execute, provided the
        // definition dominates the use.
        let mut worklist: VecDeque<u64> = VecDeque::new();
        for &idx in &must_execute_defs {
            // Find the vid for this index.
            for (vid, gidx) in &inst_idx_map {
                if *gidx == idx {
                    worklist.push_back(*vid);
                    break;
                }
            }
        }

        let mut visited: HashSet<u64> = HashSet::new();
        while let Some(vid) = worklist.pop_front() {
            if !visited.insert(vid) {
                continue;
            }
            // Find the instruction.
            for op in &f.operands {
                let bb = op.borrow();
                if bb.is_basic_block() {
                    for inst in &bb.operands {
                        let i = inst.borrow();
                        if i.vid == vid && i.is_instruction() {
                            // Propagate to operands.
                            for operand in &i.operands {
                                let op_vid = operand.borrow().vid;
                                if let Some(&op_idx) = inst_idx_map.get(&op_vid) {
                                    must_execute_defs.insert(op_idx);
                                }
                                worklist.push_back(op_vid);
                            }
                        }
                    }
                }
            }
        }

        drop(f);
        self.backward_cache.insert(0, must_execute_defs.clone());
        must_execute_defs
    }

    /// Get predecessors of a block.
    fn get_predecessors(
        &self,
        block_idx: usize,
        operands: &[ValueRef],
        name_to_idx: &HashMap<String, usize>,
    ) -> Vec<usize> {
        let mut preds = Vec::new();
        let target_name = operands[block_idx].borrow().name.clone();
        for (i, op) in operands.iter().enumerate() {
            if i == block_idx {
                continue;
            }
            let bb = op.borrow();
            if bb.is_basic_block() {
                for succ in &bb.operands {
                    if succ.borrow().name == target_name {
                        preds.push(i);
                        break;
                    }
                }
            }
        }
        preds
    }

    /// Query the forward propagation result.
    pub fn must_execute_blocks(&self) -> Option<&HashSet<usize>> {
        self.forward_cache.get(&0)
    }

    /// Query the backward propagation result.
    pub fn must_execute_defs(&self) -> Option<&HashSet<usize>> {
        self.backward_cache.get(&0)
    }

    /// Get a reference to the must-execute context.
    pub fn context(&self) -> &MustBeExecutedContext {
        &self.context
    }

    /// Combined query: is this instruction guaranteed to execute?
    /// Checks both forward and backward propagation results.
    pub fn is_guaranteed_to_execute(&self, inst_vid: u64) -> bool {
        if let Some(defs) = self.must_execute_defs() {
            return defs.contains(&(inst_vid as usize));
        }
        false
    }
}

// ============================================================================
// MustExecuteForLICM — LICM-Specific Must-Execute Queries
// ============================================================================

/// Must-execute analysis tailored for Loop-Invariant Code Motion (LICM).
/// Determines whether hoisting an instruction from a loop body to the
/// preheader is safe.
pub struct MustExecuteForLICM {
    /// The context for the function.
    context: MustBeExecutedContext,
    /// Cache of instructions that are safe to hoist.
    hoistable_cache: HashMap<u64, bool>,
}

impl MustExecuteForLICM {
    /// Create a new LICM must-execute analyzer.
    pub fn new(context: MustBeExecutedContext) -> Self {
        Self {
            context,
            hoistable_cache: HashMap::new(),
        }
    }

    /// Check if an instruction is safe to hoist out of its loop.
    /// An instruction is safe to hoist if:
    /// 1. It is guaranteed to execute on every iteration of the loop.
    /// 2. Hoisting it does not introduce undefined behavior on paths
    ///    that would not have executed it.
    pub fn is_safe_to_hoist(
        &mut self,
        inst: &ValueRef,
        loop_info: &LoopInfo,
        func: &ValueRef,
    ) -> bool {
        let inst_vid = inst.borrow().vid;
        if let Some(&cached) = self.hoistable_cache.get(&inst_vid) {
            return cached;
        }

        let i = inst.borrow();
        let name = i.name.to_lowercase();

        // Instructions with side effects cannot be hoisted unless
        // they must execute.
        let has_side_effects = name.contains("store")
            || name.contains("call")
            || name.contains("invoke")
            || name.contains("load");

        if has_side_effects {
            // Check if the instruction must execute on every path
            // through the loop.
            let mut propagator = MustExecutePropagator::build(func);
            propagator.propagate_forward(func);
            let must_exec = propagator.is_guaranteed_to_execute(inst_vid);
            self.hoistable_cache.insert(inst_vid, must_exec);
            return must_exec;
        }

        // Instructions without side effects (pure arithmetic, etc.)
        // are always safe to speculate (hoist).
        let safe = !name.contains("div") && !name.contains("rem")
            || self.is_guaranteed_to_execute_in_loop(inst, loop_info);
        self.hoistable_cache.insert(inst_vid, safe);
        safe
    }

    /// Check if an instruction is guaranteed to execute in the given loop.
    fn is_guaranteed_to_execute_in_loop(&self, inst: &ValueRef, loop_info: &LoopInfo) -> bool {
        let i = inst.borrow();
        // The instruction must be in a block that dominates all loop exits.
        // Simplified: if the instruction's block is the loop header,
        // it always executes.
        if let Some(ref parent) = i.parent {
            let header = &loop_info.header;
            if std::rc::Rc::ptr_eq(parent, header) {
                return true;
            }
        }
        // Conservative: return false.
        false
    }

    /// Clear the cache.
    pub fn clear_cache(&mut self) {
        self.hoistable_cache.clear();
    }
}

// ============================================================================
// MustExecuteForDCE — DCE-Specific Must-Execute Queries
// ============================================================================

/// Must-execute analysis tailored for Dead Code Elimination (DCE).
/// An instruction is "live" (not dead) if it must execute and
/// produces a value that is used by another must-execute instruction
/// or has observable side effects.
pub struct MustExecuteForDCE {
    /// The context.
    context: MustBeExecutedContext,
    /// Live instructions.
    live_instructions: HashSet<u64>,
    /// Whether analysis has been run.
    analyzed: bool,
}

impl MustExecuteForDCE {
    /// Create a new DCE must-execute analyzer.
    pub fn new(context: MustBeExecutedContext) -> Self {
        Self {
            context,
            live_instructions: HashSet::new(),
            analyzed: false,
        }
    }

    /// Run liveness analysis using must-execute information.
    /// Marks as live any instruction that:
    /// 1. Has observable side effects (stores, calls, returns).
    /// 2. Is used by a live instruction.
    /// 3. Is guaranteed to execute and produces a used value.
    pub fn run_analysis(&mut self, func: &ValueRef) {
        self.live_instructions.clear();

        let f = func.borrow();

        // Seed: instructions with observable side effects.
        let mut worklist: Vec<u64> = Vec::new();
        for op in &f.operands {
            let bb = op.borrow();
            if bb.is_basic_block() {
                for inst in &bb.operands {
                    let i = inst.borrow();
                    let name = i.name.to_lowercase();
                    if name.contains("ret")
                        || name.contains("br")
                        || name.contains("store")
                        || name.contains("call")
                        || name.contains("invoke")
                        || name.contains("switch")
                    {
                        self.live_instructions.insert(i.vid);
                        worklist.push(i.vid);
                    }
                }
            }
        }

        // Propagate liveness backward through operands.
        while let Some(vid) = worklist.pop() {
            for op in &f.operands {
                let bb = op.borrow();
                if bb.is_basic_block() {
                    for inst in &bb.operands {
                        let i = inst.borrow();
                        if i.vid == vid {
                            for operand in &i.operands {
                                let op_vid = operand.borrow().vid;
                                if self.live_instructions.insert(op_vid) {
                                    worklist.push(op_vid);
                                }
                            }
                            break;
                        }
                    }
                }
            }
        }

        drop(f);
        self.analyzed = true;
    }

    /// Check if an instruction is live.
    pub fn is_live(&self, inst_vid: u64) -> bool {
        self.live_instructions.contains(&inst_vid)
    }

    /// Get all live instructions.
    pub fn live_instructions(&self) -> &HashSet<u64> {
        &self.live_instructions
    }

    /// Check if analysis has been run.
    pub fn is_analyzed(&self) -> bool {
        self.analyzed
    }
}

// ============================================================================
// MustExecuteForSpeculation — Speculation Safety Analysis
// ============================================================================

/// Must-execute analysis for determining whether an instruction
/// is safe to speculatively execute above a branch or loop.
///
/// Speculative execution moves an instruction to an earlier point
/// in the program where it may execute even when the original
/// program would not have executed it. This is safe only if the
/// instruction cannot cause observable side effects (e.g.,
/// division by zero, null pointer dereference, infinite loop).
pub struct MustExecuteForSpeculation {
    /// The context.
    context: MustBeExecutedContext,
    /// Cache of speculation safety decisions.
    speculation_cache: HashMap<u64, SpeculationSafety>,
}

/// Result of a speculation safety query.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SpeculationSafety {
    /// Safe to speculate unconditionally.
    Safe,
    /// Safe only if hoisted along with a guarding condition.
    GuardedSafe,
    /// Unsafe to speculate (may introduce UB).
    Unsafe,
    /// Unknown — conservative answer.
    Unknown,
}

impl MustExecuteForSpeculation {
    /// Create a new speculation safety analyzer.
    pub fn new(context: MustBeExecutedContext) -> Self {
        Self {
            context,
            speculation_cache: HashMap::new(),
        }
    }

    /// Check if an instruction is safe to speculatively execute.
    pub fn is_safe_to_speculate(&mut self, inst: &ValueRef) -> SpeculationSafety {
        let inst_vid = inst.borrow().vid;
        if let Some(&cached) = self.speculation_cache.get(&inst_vid) {
            return cached;
        }

        let i = inst.borrow();
        let name = i.name.to_lowercase();

        let result = if name.contains("div")
            || name.contains("rem")
            || name.contains("udiv")
            || name.contains("sdiv")
            || name.contains("urem")
            || name.contains("srem")
        {
            // Division/remainder can trap on division by zero.
            SpeculationSafety::GuardedSafe
        } else if name.contains("load") {
            // Loads can fault on invalid pointers.
            SpeculationSafety::GuardedSafe
        } else if name.contains("store") {
            // Stores have visible side effects.
            SpeculationSafety::Unsafe
        } else if name.contains("call") || name.contains("invoke") {
            // Calls may have arbitrary side effects.
            SpeculationSafety::Unsafe
        } else if name.contains("alloca") {
            // Allocas are always safe — they just reserve stack space.
            SpeculationSafety::Safe
        } else if name.contains("phi") {
            // PHIs cannot be speculated — they're control-flow dependent.
            SpeculationSafety::Unsafe
        } else {
            // Pure arithmetic, bitwise ops, conversions, etc. are safe.
            SpeculationSafety::Safe
        };

        self.speculation_cache.insert(inst_vid, result);
        result
    }

    /// Check if an instruction can be speculated above a loop.
    /// More conservative than branch speculation due to potentially
    /// zero-trip loops.
    pub fn is_safe_to_speculate_above_loop(
        &mut self,
        inst: &ValueRef,
        loop_info: &LoopInfo,
    ) -> SpeculationSafety {
        let base = self.is_safe_to_speculate(inst);

        // If the loop might execute zero times, we must be more careful.
        if loop_info.trip_count.is_none() || loop_info.trip_count == Some(0) {
            match base {
                SpeculationSafety::Safe => SpeculationSafety::Safe,
                SpeculationSafety::GuardedSafe => SpeculationSafety::Unsafe,
                other => other,
            }
        } else {
            base
        }
    }

    /// Clear the cache.
    pub fn clear_cache(&mut self) {
        self.speculation_cache.clear();
    }

    /// Get statistics.
    pub fn cache_size(&self) -> usize {
        self.speculation_cache.len()
    }
}

// ============================================================================
// LoopMustExecuteInfo — Per-Loop Must-Execute Summary
// ============================================================================

/// Summarizes must-execute information for a single loop.
#[derive(Debug, Clone)]
pub struct LoopMustExecuteInfo {
    /// The loop this info is for.
    pub loop_idx: usize,
    /// Instructions that are guaranteed to execute on every iteration.
    pub guaranteed_insts: Vec<u64>,
    /// Instructions that may not execute on some iterations.
    pub conditional_insts: Vec<u64>,
    /// Whether the loop is guaranteed to execute at least once.
    pub always_executes: bool,
    /// The loop's trip count (if known).
    pub trip_count: Option<u64>,
}

impl LoopMustExecuteInfo {
    /// Create a new LoopMustExecuteInfo for a loop.
    pub fn new(loop_idx: usize, li: &LoopInfo) -> Self {
        Self {
            loop_idx,
            guaranteed_insts: Vec::new(),
            conditional_insts: Vec::new(),
            always_executes: li.trip_count.map_or(false, |tc| tc > 0),
            trip_count: li.trip_count,
        }
    }

    /// Compute must-execute info for this loop.
    pub fn compute(&mut self, func: &ValueRef) {
        let f = func.borrow();

        // Find blocks in this loop.
        let mut block_names: HashSet<String> = HashSet::new();
        // We use the loop_info from the struct which is passed at creation.
        // For now, search all blocks.
        for op in &f.operands {
            let bb = op.borrow();
            if bb.is_basic_block() {
                block_names.insert(bb.name.clone());
            }
        }

        // For each instruction in blocks, classify.
        for op in &f.operands {
            let bb = op.borrow();
            if bb.is_basic_block() && block_names.contains(&bb.name) {
                for inst in &bb.operands {
                    let i = inst.borrow();
                    let name = i.name.to_lowercase();
                    // Branch/return instructions always execute (they terminate the block).
                    if name.contains("br")
                        || name.contains("ret")
                        || name.contains("switch")
                        || name.contains("phi")
                    {
                        self.guaranteed_insts.push(i.vid);
                    } else if name.contains("call")
                        || name.contains("invoke")
                        || name.contains("store")
                    {
                        self.guaranteed_insts.push(i.vid);
                    } else {
                        self.conditional_insts.push(i.vid);
                    }
                }
            }
        }

        drop(f);
    }

    /// Number of guaranteed instructions.
    pub fn guaranteed_count(&self) -> usize {
        self.guaranteed_insts.len()
    }

    /// Number of conditional instructions.
    pub fn conditional_count(&self) -> usize {
        self.conditional_insts.len()
    }
}

// ============================================================================
// MustExecuteResult — Top-Level Query Result
// ============================================================================

/// The result of a must-execute query, providing structured
/// information for optimization passes.
#[derive(Debug, Clone)]
pub enum MustExecuteResult {
    /// The instruction must execute under all paths.
    MustExecute {
        /// The reason it must execute.
        reason: MustExecuteReason,
        /// The block containing the instruction.
        block_idx: usize,
    },
    /// The instruction may not execute on some paths.
    MayNotExecute {
        /// Which condition could skip it.
        condition_block: Option<usize>,
    },
    /// The instruction must execute if the loop executes.
    MustExecuteIfLoopExecutes {
        /// The loop index.
        loop_idx: usize,
        /// Whether the loop always executes.
        loop_always_executes: bool,
    },
}

impl MustExecuteResult {
    /// Is this a "must execute" result?
    pub fn is_must_execute(&self) -> bool {
        matches!(self, MustExecuteResult::MustExecute { .. })
    }

    /// Is safe to speculate based on this result?
    pub fn is_safe_to_speculate(&self) -> bool {
        match self {
            MustExecuteResult::MustExecute { .. } => true,
            MustExecuteResult::MustExecuteIfLoopExecutes {
                loop_always_executes: true,
                ..
            } => true,
            _ => false,
        }
    }
}

// ============================================================================
// MustExecute Analysis Driver
// ============================================================================

/// Top-level driver that coordinates all must-execute analyses.
pub struct MustExecuteDriver {
    /// The execution context.
    pub context: MustBeExecutedContext,
    /// Forward/backward propagator.
    pub propagator: MustExecutePropagator,
    /// LICM-specific queries.
    pub licm: MustExecuteForLICM,
    /// DCE-specific queries.
    pub dce: MustExecuteForDCE,
    /// Speculation safety queries.
    pub speculation: MustExecuteForSpeculation,
    /// Per-loop info.
    pub loop_infos: Vec<LoopMustExecuteInfo>,
    /// Whether full analysis has been run.
    pub analyzed: bool,
}

impl MustExecuteDriver {
    /// Create a new driver from a function.
    pub fn new(func: &ValueRef) -> Self {
        let context = MustBeExecutedContext::build(func);
        let propagator = MustExecutePropagator::new(context.clone());
        let licm = MustExecuteForLICM::new(context.clone());
        let dce = MustExecuteForDCE::new(context.clone());
        let speculation = MustExecuteForSpeculation::new(context.clone());
        let loop_infos: Vec<LoopMustExecuteInfo> = context
            .loops_iter()
            .enumerate()
            .map(|(i, li)| LoopMustExecuteInfo::new(i, li))
            .collect();

        Self {
            context,
            propagator,
            licm,
            dce,
            speculation,
            loop_infos,
            analyzed: false,
        }
    }

    /// Run all analyses.
    pub fn analyze(&mut self, func: &ValueRef) {
        self.propagator.propagate_forward(func);
        self.propagator.propagate_backward(func);
        self.dce.run_analysis(func);

        for li in &mut self.loop_infos {
            li.compute(func);
        }

        self.analyzed = true;
    }

    /// Get a summary of must-execute information.
    pub fn summary(&self) -> String {
        let total_guaranteed: usize = self.loop_infos.iter().map(|li| li.guaranteed_count()).sum();
        let live_count = self.dce.live_instructions().len();
        format!(
            "MustExecute: loops={} guaranteed_insts={} live={} speculation_cache={}",
            self.loop_infos.len(),
            total_guaranteed,
            live_count,
            self.speculation.cache_size(),
        )
    }
}

impl Clone for MustBeExecutedContext {
    fn clone(&self) -> Self {
        Self {
            dom_tree: self.dom_tree.clone(),
            loops: self.loops.clone(),
            block_loop_depth: self.block_loop_depth.clone(),
            block_to_loop: self.block_to_loop.clone(),
            may_throw: self.may_throw,
        }
    }
}

fn find_all_loops(func: &ValueRef, dt: &DominatorTree) -> Vec<LoopInfo> {
    let mut loops = Vec::new();
    let f = func.borrow();
    let block_count = f.operands.len();

    let mut name_to_idx: HashMap<String, usize> = HashMap::new();
    for (i, op) in f.operands.iter().enumerate() {
        let bb = op.borrow();
        if bb.is_basic_block() {
            name_to_idx.insert(bb.name.clone(), i);
        }
    }

    for i in 0..block_count {
        if let Some(bb) = f.operands.get(i) {
            let block = bb.borrow();
            for succ in &block.operands {
                let s = succ.borrow();
                if let Some(&succ_idx) = name_to_idx.get(&s.name) {
                    if dt.dominates(succ_idx, i) {
                        let header = f.operands[succ_idx].clone();
                        let latch = Some(f.operands[i].clone());
                        let mut blocks = vec![header.clone()];
                        for (j, op) in f.operands.iter().enumerate() {
                            if j != succ_idx && dt.dominates(succ_idx, j) {
                                blocks.push(op.clone());
                            }
                        }
                        let preheader =
                            find_preheader_for_loop(&f.operands, succ_idx, &blocks, &name_to_idx);
                        loops.push(LoopInfo {
                            header,
                            blocks,
                            exits: vec![],
                            latch,
                            preheader,
                            depth: 0,
                            parent_loop: None,
                            is_simplified: false,
                            trip_count: None,
                        });
                    }
                }
            }
        }
    }
    loops
}

fn find_preheader_for_loop(
    operands: &[ValueRef],
    header_idx: usize,
    loop_blocks: &[ValueRef],
    name_to_idx: &HashMap<String, usize>,
) -> Option<ValueRef> {
    let block_ids: HashSet<usize> = loop_blocks
        .iter()
        .filter_map(|b| name_to_idx.get(&b.borrow().name).copied())
        .collect();
    let header_name = operands[header_idx].borrow().name.clone();

    for (i, op) in operands.iter().enumerate() {
        if block_ids.contains(&i) {
            continue;
        }
        let bb = op.borrow();
        if bb.operands.iter().any(|s| s.borrow().name == header_name) {
            return Some(op.clone());
        }
    }
    None
}

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

    fn make_test_function() -> ValueRef {
        valref(Value::new(Type::void()))
    }

    #[test]
    fn test_must_execute_new() {
        let me = MustExecute::new();
        assert!(me.loops().is_empty());
    }

    #[test]
    fn test_compute_empty_function() {
        let func = make_test_function();
        let me = MustExecute::compute(&func);
        assert!(me.loops().is_empty());
    }

    #[test]
    fn test_is_guaranteed_to_execute_same_value() {
        let func = make_test_function();
        let me = MustExecute::compute(&func);
        assert!(me.is_guaranteed_to_execute(&func, &func));
    }

    #[test]
    fn test_get_loop_preheader() {
        let me = MustExecute::new();
        let func = make_test_function();
        let li = LoopInfo {
            header: func.clone(),
            blocks: vec![func.clone()],
            exits: vec![],
            latch: None,
            preheader: Some(func.clone()),
            depth: 0,
            parent_loop: None,
            is_simplified: true,
            trip_count: None,
        };
        let preheader = me.get_loop_preheader(&li);
        assert!(preheader.is_some());
        assert!(std::rc::Rc::ptr_eq(preheader.as_ref().unwrap(), &func));
    }
}