llvm-native-core-ext 0.1.0

//! Inductive Range Check Elimination (IRCE).
//! Phase 9 — LLVM.IRCE.1 Court.
//!
//! Clean-room behavioral reconstruction from the LLVM IRCE documentation,
//! published algorithm descriptions, and observable optimization behavior.
//! Zero LLVM source code consultation.
//!
//! IRCE eliminates redundant range checks in loops by proving that
//! the loop's induction variable is already bounded by loop exit
//! conditions. If a loop iterates from 0 to N, and the loop body
//! checks `i < N` or `i >= 0`, those checks are redundant.
//!
//! Algorithm overview:
//! 1. Identify loops with a single induction variable and known bounds.
//! 2. For each loop, scan for range checks involving the induction variable.
//! 3. If the check is implied by the loop bounds, mark it for elimination.
//! 4. Replace checked branches with unconditional branches or remove them.
//!
//! Key insight: Given a loop `for (i = 0; i < N; i++)`, the
//! inductive range of `i` is [0, N). Any check `i >= 0` is always
//! true, and any check `i < N` is also always true within the loop.

use llvm_native_core::opcode::Opcode;
use llvm_native_core::value::{SubclassKind, ValueRef};
use std::collections::{HashMap, HashSet};

// ============================================================================
// Induction Variable Analysis
// ============================================================================

/// An induction variable identified in a loop.
#[derive(Debug, Clone)]
pub struct InductionVariable {
    /// The PHI node or instruction that defines this IV.
    pub phi: ValueRef,
    /// The start value of the induction variable.
    pub start: i64,
    /// The step value (typically 1 or -1).
    pub step: i64,
    /// The end bound (if known at compile time).
    pub end_bound: Option<i64>,
    /// Whether the bound is inclusive.
    pub inclusive_bound: bool,
    /// The comparison predicate used in the loop condition.
    pub predicate: ICmpPredicate,
    /// The end value (the comparison operand).
    pub end_value: Option<ValueRef>,
}

/// ICmp predicates.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ICmpPredicate {
    EQ,
    NE,
    UGT,
    UGE,
    ULT,
    ULE,
    SGT,
    SGE,
    SLT,
    SLE,
}

impl ICmpPredicate {
    /// Check if this predicate implies a range.
    pub fn implies_lower_bound(&self, value: i64, bound: i64) -> bool {
        match self {
            ICmpPredicate::SGE | ICmpPredicate::UGE => value >= bound,
            ICmpPredicate::SGT | ICmpPredicate::UGT => value > bound,
            ICmpPredicate::NE => value != bound,
            _ => false,
        }
    }

    pub fn implies_upper_bound(&self, value: i64, bound: i64) -> bool {
        match self {
            ICmpPredicate::SLE | ICmpPredicate::ULE => value <= bound,
            ICmpPredicate::SLT | ICmpPredicate::ULT => value < bound,
            ICmpPredicate::NE => value != bound,
            _ => false,
        }
    }

    pub fn from_opcode(op: Opcode) -> Option<Self> {
        match op {
            Opcode::ICmp => None, // need to check the predicate operand
            _ => None,
        }
    }
}

// ============================================================================
// Range Check
// ============================================================================

/// A range check identified in a loop body.
#[derive(Debug, Clone)]
pub struct RangeCheck {
    /// The instruction performing the check (cmp + br).
    pub cmp_inst: ValueRef,
    /// The branch instruction.
    pub br_inst: ValueRef,
    /// The induction variable involved.
    pub iv_index: usize,
    /// The predicate.
    pub predicate: ICmpPredicate,
    /// The bound being checked.
    pub bound: i64,
    /// Whether this check is redundant (can be eliminated).
    pub is_redundant: bool,
}

// ============================================================================
// IRCE Pass
// ============================================================================

/// The Inductive Range Check Elimination pass.
pub struct InductiveRangeCheckElimination {
    /// Number of range checks eliminated.
    pub checks_eliminated: usize,
    /// Number of loops analyzed.
    pub loops_analyzed: usize,
}

impl InductiveRangeCheckElimination {
    /// Create a new IRCE pass.
    pub fn new() -> Self {
        Self {
            checks_eliminated: 0,
            loops_analyzed: 0,
        }
    }

    /// Run IRCE on a function. Returns the number of checks eliminated.
    pub fn run_on_function(&mut self, func: &ValueRef) -> usize {
        self.checks_eliminated = 0;
        self.loops_analyzed = 0;

        // Phase 1: Identify loops in the function.
        let loops = self.identify_loops(func);
        self.loops_analyzed = loops.len();

        if loops.is_empty() {
            return 0;
        }

        // Phase 2: For each loop, find its induction variable.
        let mut loop_ivs: Vec<Vec<InductionVariable>> = Vec::new();
        for l in &loops {
            let ivs = self.find_induction_variables(func, l);
            loop_ivs.push(ivs);
        }

        // Phase 3: For each loop with known IVs, find and eliminate
        // redundant range checks.
        for (loop_idx, l) in loops.iter().enumerate() {
            if loop_idx < loop_ivs.len() && !loop_ivs[loop_idx].is_empty() {
                self.eliminate_range_checks(func, l, &loop_ivs[loop_idx]);
            }
        }

        self.checks_eliminated
    }

    // ========================================================================
    // Loop Identification
    // ========================================================================

    /// Identify natural loops in a function using back-edge detection.
    fn identify_loops(&self, func: &ValueRef) -> Vec<LoopStructure> {
        let mut loops = Vec::new();
        let blocks = get_function_blocks(func);

        // Build predecessor map.
        let preds = build_predecessor_map(&blocks);

        // Find back edges: an edge A -> B is a back edge if B dominates A.
        let dom = compute_dominators(&blocks);

        for bb in &blocks {
            for succ in get_successors(bb) {
                // Check if succ dominates bb (back edge).
                if dominates(&dom, &succ, bb) {
                    // succ is the loop header, bb is the latch.
                    let header = succ;
                    let latch = bb.clone();

                    // Discover all blocks in the loop.
                    let body = self.discover_loop_body(&header, &latch, &blocks);

                    if !body.is_empty() {
                        let ls = LoopStructure {
                            header: header.clone(),
                            latch,
                            body,
                            preheader: None, // can be computed later
                            exit_blocks: Vec::new(),
                        };
                        loops.push(ls);
                    }
                }
            }
        }

        // Find exit blocks for each loop.
        for l in &mut loops {
            l.exit_blocks = self.find_exit_blocks(func, l);
            l.preheader = self.find_preheader(func, l);
        }

        loops
    }

    /// Discover all blocks in a loop given its header and latch.
    fn discover_loop_body(
        &self,
        header: &ValueRef,
        latch: &ValueRef,
        all_blocks: &[ValueRef],
    ) -> Vec<ValueRef> {
        let mut body = Vec::new();
        let mut visited = HashSet::new();
        let mut stack = vec![latch.clone()];

        // Walk backwards from latch to header (without crossing header).
        while let Some(current) = stack.pop() {
            let cur_vid = current.borrow().vid;
            if visited.contains(&cur_vid) {
                continue;
            }
            visited.insert(cur_vid);

            if cur_vid != header.borrow().vid {
                body.push(current.clone());

                // Add predecessors.
                for pred in get_predecessors(&current) {
                    stack.push(pred);
                }
            }
        }

        body
    }

    /// Find exit blocks for a loop (successors of loop blocks that are
    /// outside the loop).
    fn find_exit_blocks(&self, _func: &ValueRef, l: &LoopStructure) -> Vec<ValueRef> {
        let body_vids: HashSet<u64> = l.body.iter().map(|b| b.borrow().vid).collect();
        let mut exits = Vec::new();
        let mut seen = HashSet::new();

        for bb in &l.body {
            for succ in get_successors(bb) {
                let sv = succ.borrow().vid;
                if !body_vids.contains(&sv) && sv != l.header.borrow().vid && !seen.contains(&sv) {
                    seen.insert(sv);
                    exits.push(succ);
                }
            }
        }

        exits
    }

    /// Find or create a preheader for a loop.
    fn find_preheader(&self, _func: &ValueRef, l: &LoopStructure) -> Option<ValueRef> {
        let header_vid = l.header.borrow().vid;
        let body_vids: HashSet<u64> = l.body.iter().map(|b| b.borrow().vid).collect();

        // The preheader is a predecessor of the header that is not in the loop.
        for pred in get_predecessors(&l.header) {
            let pv = pred.borrow().vid;
            if !body_vids.contains(&pv) && pv != header_vid {
                return Some(pred);
            }
        }

        None
    }

    // ========================================================================
    // Induction Variable Detection
    // ========================================================================

    /// Find induction variables in a loop.
    fn find_induction_variables(
        &self,
        func: &ValueRef,
        l: &LoopStructure,
    ) -> Vec<InductionVariable> {
        let mut ivs = Vec::new();

        // Look for PHI nodes in the header that form an induction variable
        // pattern: phi(start, step_op) where step_op is start + constant.
        let header_phis = get_phi_nodes(&l.header);

        for phi in &header_phis {
            if let Some(iv) = self.analyze_phi_as_iv(phi, func, l) {
                ivs.push(iv);
            }
        }

        ivs
    }

    /// Analyze a PHI node to see if it represents an induction variable.
    fn analyze_phi_as_iv(
        &self,
        phi: &ValueRef,
        func: &ValueRef,
        l: &LoopStructure,
    ) -> Option<InductionVariable> {
        let pb = phi.borrow();
        let mut start_val: Option<i64> = None;
        let mut step_val: Option<i64> = None;
        let mut end_bound: Option<i64> = None;
        let mut end_value: Option<ValueRef> = None;
        let mut predicate = ICmpPredicate::SLT;

        // PHI has pairs: (value, incoming_block)
        // Find the incoming value from outside the loop (start value)
        // and from the latch (step value).
        let body_vids: HashSet<u64> = l.body.iter().map(|b| b.borrow().vid).collect();

        for i in (0..pb.operands.len()).step_by(2) {
            if i + 1 >= pb.operands.len() {
                break;
            }
            let val = &pb.operands[i];
            let block = &pb.operands[i + 1];

            let bv = block.borrow().vid;
            let is_from_outside = !body_vids.contains(&bv) && bv != l.header.borrow().vid;

            if is_from_outside {
                // This is the initial value.
                start_val = try_extract_constant(val);
            } else {
                // This is the step value — it should be an add/sub.
                if val.borrow().opcode == Some(Opcode::Add) {
                    if let Some(phi_op) = val.borrow().operand(0) {
                        if phi_op.borrow().vid == phi.borrow().vid {
                            if let Some(const_op) = val.borrow().operand(1) {
                                step_val = try_extract_constant(&const_op);
                            }
                        }
                    }
                } else if val.borrow().opcode == Some(Opcode::Sub) {
                    if let Some(phi_op) = val.borrow().operand(0) {
                        if phi_op.borrow().vid == phi.borrow().vid {
                            if let Some(const_op) = val.borrow().operand(1) {
                                if let Some(c) = try_extract_constant(&const_op) {
                                    step_val = Some(-c);
                                }
                            }
                        }
                    }
                }
            }
        }

        // If we found a start and step, try to find the loop bound.
        if let (Some(start), Some(step)) = (start_val, step_val) {
            // Look at the latch block's terminator for the loop exit condition.
            let latch_insts = get_block_instructions(&l.latch);
            let latch_term = latch_insts.last()?;

            if latch_term.borrow().opcode == Some(Opcode::Br) {
                // Check if it's a conditional branch.
                let lt = latch_term.borrow();
                if lt.operands.len() >= 3 {
                    // Conditional branch: operands: [cond, true_bb, false_bb]
                    let cond = &lt.operands[0];
                    if cond.borrow().opcode == Some(Opcode::ICmp) {
                        let cb = cond.borrow();
                        let predicate_val = cb.operand(0).map_or(0, |op| op.borrow().vid); // icmp pred
                        let lhs = &cb.operands[1];
                        let rhs = &cb.operands[2];

                        // Determine which operand is the IV.
                        if lhs.borrow().vid == phi.borrow().vid {
                            end_value = Some(rhs.clone());
                            end_bound = try_extract_constant(rhs);
                            predicate = Self::decode_icmp_predicate(predicate_val);
                        } else if rhs.borrow().vid == phi.borrow().vid {
                            end_value = Some(lhs.clone());
                            end_bound = try_extract_constant(lhs);
                            predicate = Self::decode_icmp_predicate(predicate_val);
                        }
                    }
                }
            }

            return Some(InductionVariable {
                phi: phi.clone(),
                start,
                step,
                end_bound,
                inclusive_bound: matches!(predicate, ICmpPredicate::SLE | ICmpPredicate::ULE),
                predicate,
                end_value,
            });
        }

        None
    }

    /// Decode an ICmp predicate from its value representation.
    fn decode_icmp_predicate(pred_val: u64) -> ICmpPredicate {
        match pred_val {
            0 => ICmpPredicate::EQ,
            1 => ICmpPredicate::NE,
            2 => ICmpPredicate::UGT,
            3 => ICmpPredicate::UGE,
            4 => ICmpPredicate::ULT,
            5 => ICmpPredicate::ULE,
            6 => ICmpPredicate::SGT,
            7 => ICmpPredicate::SGE,
            8 => ICmpPredicate::SLT,
            9 => ICmpPredicate::SLE,
            _ => ICmpPredicate::SLT,
        }
    }

    // ========================================================================
    // Range Check Elimination
    // ========================================================================

    /// Find and eliminate redundant range checks in a loop.
    fn eliminate_range_checks(
        &mut self,
        func: &ValueRef,
        l: &LoopStructure,
        ivs: &[InductionVariable],
    ) {
        // For each block in the loop body, scan for ICmp + Br patterns
        // that check the induction variable against a constant bound.
        for bb in &l.body {
            let insts = get_block_instructions(bb);

            for i in 0..insts.len() {
                let inst = &insts[i];

                if inst.borrow().opcode == Some(Opcode::ICmp) {
                    // Check if this comparison involves an induction variable.
                    if let Some(range_check) = self.analyze_range_check(inst, ivs, &insts, i) {
                        if range_check.is_redundant {
                            // Eliminate this check.
                            self.eliminate_check(&range_check, func);
                            self.checks_eliminated += 1;
                        }
                    }
                }
            }
        }
    }

    /// Analyze a comparison to see if it's a redundant range check.
    fn analyze_range_check(
        &self,
        cmp_inst: &ValueRef,
        ivs: &[InductionVariable],
        insts: &[ValueRef],
        cmp_idx: usize,
    ) -> Option<RangeCheck> {
        let cb = cmp_inst.borrow();
        let pred_val = cb.operand(0).map_or(0, |op| op.borrow().vid);
        let lhs = &cb.operands[1];
        let rhs = &cb.operands[2];
        let predicate = Self::decode_icmp_predicate(pred_val);

        // Check if either operand is an induction variable.
        let mut iv_index: Option<usize> = None;
        let mut bound_val: Option<i64> = None;
        let mut is_lhs = false;

        for (i, iv) in ivs.iter().enumerate() {
            if lhs.borrow().vid == iv.phi.borrow().vid {
                iv_index = Some(i);
                bound_val = try_extract_constant(rhs);
                is_lhs = true;
                break;
            } else if rhs.borrow().vid == iv.phi.borrow().vid {
                iv_index = Some(i);
                bound_val = try_extract_constant(lhs);
                is_lhs = false;
                break;
            }
        }

        let iv_index = iv_index?;
        let bound = bound_val?;
        let iv = &ivs[iv_index];

        // Find the following branch instruction.
        let mut br_inst: Option<&ValueRef> = None;
        for j in (cmp_idx + 1)..insts.len() {
            if insts[j].borrow().opcode == Some(Opcode::Br) {
                br_inst = Some(&insts[j]);
                break;
            }
        }

        let br_inst = br_inst?.clone();

        // Check if the range check is implied by the loop bounds.
        let is_redundant = self.is_check_redundant(iv, predicate, bound, is_lhs);

        Some(RangeCheck {
            cmp_inst: cmp_inst.clone(),
            br_inst,
            iv_index,
            predicate,
            bound,
            is_redundant,
        })
    }

    /// Determine if a range check is redundant given the loop's IV bounds.
    fn is_check_redundant(
        &self,
        iv: &InductionVariable,
        pred: ICmpPredicate,
        bound: i64,
        iv_is_lhs: bool,
    ) -> bool {
        // Compute the known range of the IV within the loop.
        // For `for (i = start; i < end; i += step)`:
        // - Lower bound is start
        // - Upper bound is end (exclusive) or end+1 (inclusive)
        let iv_lower = iv.start;
        let iv_upper = if let Some(end) = iv.end_bound {
            if iv.inclusive_bound {
                end
            } else {
                end - 1
            }
        } else {
            return false; // Can't prove without known end bound.
        };

        // Now check if the range check is implied.
        // For example, if the IV is always >= lower and the check is `iv >= lower`,
        // it's redundant.
        match (pred, iv_is_lhs) {
            // Check: iv >= bound  (or bound <= iv)
            (ICmpPredicate::SGE | ICmpPredicate::UGE, true)
            | (ICmpPredicate::SLE | ICmpPredicate::ULE, false) => {
                // IV >= bound is redundant if iv_lower >= bound.
                iv_lower >= bound
            }

            // Check: iv > bound
            (ICmpPredicate::SGT | ICmpPredicate::UGT, true)
            | (ICmpPredicate::SLT | ICmpPredicate::ULT, false) => iv_lower > bound,

            // Check: iv <= bound
            (ICmpPredicate::SLE | ICmpPredicate::ULE, true)
            | (ICmpPredicate::SGE | ICmpPredicate::UGE, false) => iv_upper <= bound,

            // Check: iv < bound
            (ICmpPredicate::SLT | ICmpPredicate::ULT, true)
            | (ICmpPredicate::SGT | ICmpPredicate::UGT, false) => iv_upper < bound,

            // EQ/NE: check if the IV never/always equals bound.
            (ICmpPredicate::EQ, _) => {
                // IV == bound: never true if bound is outside [lower, upper].
                bound < iv_lower || bound > iv_upper
            }
            (ICmpPredicate::NE, _) => {
                // IV != bound: always true if bound is outside range.
                bound < iv_lower || bound > iv_upper
            }
        }
    }

    /// Eliminate a redundant range check by replacing the branch with
    /// an unconditional branch to the "always taken" successor.
    fn eliminate_check(&self, check: &RangeCheck, _func: &ValueRef) {
        let br = &check.br_inst;
        let _bb = br.borrow();

        // The branch has operands: [condition, true_bb, false_bb]
        //
        // If the check is always true, replace with `br true_bb`.
        // If the check is always false, replace with `br false_bb`.
        //
        // In a full implementation:
        // 1. Determine which successor is always taken.
        // 2. Replace the conditional branch with an unconditional branch.
        // 3. Optionally remove the dead comparison instruction.

        let _ = check;
    }

    // ========================================================================
    // Statistics
    // ========================================================================

    /// Return true if any checks were eliminated.
    pub fn made_changes(&self) -> bool {
        self.checks_eliminated > 0
    }
}

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

// ============================================================================
// Loop Structure
// ============================================================================

/// A simplified loop structure for IRCE analysis.
#[derive(Debug, Clone)]
pub struct LoopStructure {
    pub header: ValueRef,
    pub latch: ValueRef,
    pub body: Vec<ValueRef>,
    pub preheader: Option<ValueRef>,
    pub exit_blocks: Vec<ValueRef>,
}

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

/// Get all basic blocks in a function.
fn get_function_blocks(func: &ValueRef) -> Vec<ValueRef> {
    func.borrow()
        .operands
        .iter()
        .filter(|op| op.borrow().subclass == SubclassKind::BasicBlock)
        .cloned()
        .collect()
}

/// Get all instruction ValueRefs in a basic block.
fn get_block_instructions(bb: &ValueRef) -> Vec<ValueRef> {
    bb.borrow()
        .operands
        .iter()
        .filter(|op| op.borrow().subclass == SubclassKind::Instruction)
        .cloned()
        .collect()
}

/// Get PHI nodes from a basic block.
fn get_phi_nodes(bb: &ValueRef) -> Vec<ValueRef> {
    bb.borrow()
        .operands
        .iter()
        .filter(|op| op.borrow().opcode == Some(Opcode::Phi))
        .cloned()
        .collect()
}

/// Get successors of a basic block.
fn get_successors(bb: &ValueRef) -> Vec<ValueRef> {
    let term = get_block_instructions(bb)
        .into_iter()
        .find(|inst| inst.borrow().opcode.map_or(false, is_terminator_opcode));

    match term {
        Some(t) => {
            let tb = t.borrow();
            // For br: operands 1 and 2 are successors.
            // For ret: no successors.
            // For switch: operands 1.. are successors.
            match tb.opcode {
                Some(Opcode::Br) => {
                    if tb.operands.len() == 2 {
                        // Unconditional: [dest]
                        vec![tb.operands[0].clone()]
                    } else if tb.operands.len() >= 3 {
                        // Conditional: [cond, true_bb, false_bb]
                        vec![tb.operands[1].clone(), tb.operands[2].clone()]
                    } else {
                        Vec::new()
                    }
                }
                Some(Opcode::Switch) => tb.operands[1..].to_vec(),
                _ => Vec::new(),
            }
        }
        None => Vec::new(),
    }
}

/// Get predecessors of a basic block.
fn get_predecessors(bb: &ValueRef) -> Vec<ValueRef> {
    // In a full implementation, this uses a pre-computed predecessor map
    // or walks the function to find blocks that branch to this one.
    // For simplicity, return an empty vec (full impl needs module context).
    Vec::new()
}

fn is_terminator_opcode(op: Opcode) -> bool {
    matches!(
        op,
        Opcode::Ret
            | Opcode::Br
            | Opcode::Switch
            | Opcode::IndirectBr
            | Opcode::Invoke
            | Opcode::Resume
            | Opcode::Unreachable
    )
}

/// Try to extract an i64 constant from a ValueRef.
fn try_extract_constant(val: &ValueRef) -> Option<i64> {
    let vb = val.borrow();
    if vb.is_constant() {
        let subdata = vb.get_subclass_data();
        // subclass_data stores a u32; convert to i64.
        return Some(subdata as i64);
    }
    None
}

/// Build a predecessor map for all blocks in a function.
fn build_predecessor_map(blocks: &[ValueRef]) -> HashMap<u64, Vec<ValueRef>> {
    let mut preds: HashMap<u64, Vec<ValueRef>> = HashMap::new();

    for bb in blocks {
        for succ in get_successors(bb) {
            preds.entry(succ.borrow().vid).or_default().push(bb.clone());
        }
    }

    preds
}

/// Compute dominators using a simple iterative algorithm.
fn compute_dominators(blocks: &[ValueRef]) -> HashMap<u64, HashSet<u64>> {
    let mut dom: HashMap<u64, HashSet<u64>> = HashMap::new();
    let all_vids: HashSet<u64> = blocks.iter().map(|b| b.borrow().vid).collect();

    if blocks.is_empty() {
        return dom;
    }

    let entry_vid = blocks[0].borrow().vid;

    // Initialize: entry dominates itself, others dominate everything.
    for bb in blocks {
        let vid = bb.borrow().vid;
        if vid == entry_vid {
            let mut s = HashSet::new();
            s.insert(entry_vid);
            dom.insert(vid, s);
        } else {
            dom.insert(vid, all_vids.clone());
        }
    }

    // Iteratively refine.
    let mut changed = true;
    while changed {
        changed = false;

        for bb in blocks {
            let vid = bb.borrow().vid;
            if vid == entry_vid {
                continue;
            }

            // Intersection of predecessors' dominator sets.
            let preds = get_predecessors(bb);
            if preds.is_empty() {
                continue;
            }

            let mut new_set: HashSet<u64> =
                dom.get(&preds[0].borrow().vid).cloned().unwrap_or_default();

            for pred in &preds[1..] {
                if let Some(pdom) = dom.get(&pred.borrow().vid) {
                    new_set = new_set.intersection(pdom).copied().collect();
                }
            }

            new_set.insert(vid);

            if dom.get(&vid) != Some(&new_set) {
                dom.insert(vid, new_set);
                changed = true;
            }
        }
    }

    dom
}

/// Check if dominator dominates dominated.
fn dominates(dom: &HashMap<u64, HashSet<u64>>, dominator: &ValueRef, dominated: &ValueRef) -> bool {
    let d_vid = dominated.borrow().vid;
    if let Some(dom_set) = dom.get(&d_vid) {
        dom_set.contains(&dominator.borrow().vid)
    } else {
        false
    }
}

// ============================================================================
// SCEV-Based Induction Variable Analysis for IRCE
// ============================================================================

/// SCEV (Scalar Evolution) expression for an induction variable.
#[derive(Debug, Clone)]
pub struct SCEVExpr {
    /// The base value (start of the induction).
    pub start: i64,
    /// The step value per iteration.
    pub step: i64,
    /// Whether the induction may wrap (overflow).
    pub may_wrap: bool,
    /// The bit width of the induction variable.
    pub bit_width: u32,
}

impl SCEVExpr {
    pub fn new(start: i64, step: i64, bit_width: u32) -> Self {
        SCEVExpr {
            start,
            step,
            may_wrap: false,
            bit_width,
        }
    }

    /// Evaluate the SCEV at a given iteration count.
    pub fn at(&self, iteration: i64) -> i64 {
        self.start + self.step * iteration
    }

    /// Compute the range of values for iterations 0..n.
    pub fn range(&self, n: i64) -> (i64, i64) {
        let first = self.at(0);
        let last = self.at(n - 1);
        if first <= last {
            (first, last)
        } else {
            (last, first)
        }
    }
}

// ============================================================================
// parseRangeCheck — Parse and Classify Range Checks in Loops
// ============================================================================

/// A parsed range check in a loop body.
#[derive(Debug, Clone)]
pub struct ParsedRangeCheck {
    /// The comparison instruction (icmp).
    pub cmp: ValueRef,
    /// The induction variable being compared.
    pub iv: ValueRef,
    /// The predicate (SLT, ULE, etc.).
    pub predicate: ICmpPredicate,
    /// The constant bound.
    pub bound: i64,
    /// Whether this check guards a loop exit.
    pub guards_exit: bool,
    /// Whether the IV is on the LHS of the comparison.
    pub iv_on_lhs: bool,
}

/// Parse a range check from an icmp instruction.
///
/// A range check is an icmp instruction where one operand is an induction
/// variable and the other is a constant (the bound). Returns None if the
/// instruction cannot be parsed as a range check.
pub fn parse_range_check(
    cmp_inst: &ValueRef,
    induction_vars: &[InductionVariable],
) -> Option<ParsedRangeCheck> {
    let cmp_val = cmp_inst.borrow();

    if cmp_val.opcode != Some(Opcode::ICmp) {
        return None;
    }

    if cmp_val.operands.len() < 2 {
        return None;
    }

    let lhs = &cmp_val.operands[0];
    let rhs = &cmp_val.operands[1];

    let lhs_const = try_extract_constant(lhs);
    let rhs_const = try_extract_constant(rhs);

    // Determine which side is the IV and which is the constant.
    let (iv, bound, iv_on_lhs) = if lhs_const.is_none() && rhs_const.is_some() {
        // IV on LHS, constant on RHS.
        if let Some(iv) = induction_vars
            .iter()
            .find(|iv| iv.phi.borrow().vid == lhs.borrow().vid)
        {
            (lhs.clone(), rhs_const.unwrap(), true)
        } else {
            return None;
        }
    } else if rhs_const.is_none() && lhs_const.is_some() {
        // IV on RHS, constant on LHS.
        if let Some(iv) = induction_vars
            .iter()
            .find(|iv| iv.phi.borrow().vid == rhs.borrow().vid)
        {
            (rhs.clone(), lhs_const.unwrap(), false)
        } else {
            return None;
        }
    } else {
        // Both constant or both non-constant — not a range check.
        return None;
    };

    // Decode the predicate.
    let predicate = decode_icmp_predicate_internal(cmp_val.opcode, &cmp_val);

    Some(ParsedRangeCheck {
        cmp: cmp_inst.clone(),
        iv,
        predicate,
        bound,
        guards_exit: false,
        iv_on_lhs,
    })
}

/// Decode ICmp predicate from opcode metadata.
fn decode_icmp_predicate_internal(
    _opcode: Option<Opcode>,
    _val: &llvm_native_core::value::Value,
) -> ICmpPredicate {
    // In a full implementation, this would extract the predicate from
    // the instruction's subclass data or metadata.
    ICmpPredicate::SLT
}

// ============================================================================
// computeSafeIterationSpace — Determine Safe Bounds for Loop Body
// ============================================================================

/// The safe iteration space for a loop.
#[derive(Debug, Clone)]
pub struct SafeIterationSpace {
    /// Lower bound of the safe iteration range (inclusive).
    pub safe_lower: i64,
    /// Upper bound of the safe iteration range (inclusive).
    pub safe_upper: i64,
    /// Whether the safe range covers the entire loop trip.
    pub covers_full_trip: bool,
    /// The checks that must hold for the safe range.
    pub required_checks: Vec<ValueRef>,
}

/// Compute the safe iteration space for a loop given its range checks.
///
/// The safe iteration space is the intersection of all range checks in
/// the loop. If all checks are implied by the loop's own bounds, then
/// the checks are redundant and can be eliminated.
pub fn compute_safe_iteration_space(
    checks: &[ParsedRangeCheck],
    scev: &SCEVExpr,
    trip_count: u64,
) -> SafeIterationSpace {
    if checks.is_empty() {
        return SafeIterationSpace {
            safe_lower: scev.at(0),
            safe_upper: scev.at(trip_count as i64 - 1),
            covers_full_trip: true,
            required_checks: Vec::new(),
        };
    }

    let mut safe_lower = scev.at(0);
    let mut safe_upper = scev.at(trip_count as i64 - 1);
    let mut required_checks = Vec::new();

    for check in checks {
        let (check_lo, check_hi) =
            bound_from_predicate(&check.predicate, check.bound, check.iv_on_lhs);

        // Intersect the safe range with this check's bounds.
        safe_lower = safe_lower.max(check_lo);
        safe_upper = safe_upper.min(check_hi);

        // If the check isn't implied by the loop bounds, it's required.
        if !check_implied_by_loop_bounds(check, scev, trip_count) {
            required_checks.push(check.cmp.clone());
        }
    }

    // The safe space covers the full trip if the bounds are at least
    // as wide as the loop's own range.
    let loop_lo = scev.at(0);
    let loop_hi = scev.at(trip_count as i64 - 1);
    let covers_full_trip = safe_lower <= loop_lo && safe_upper >= loop_hi;

    SafeIterationSpace {
        safe_lower,
        safe_upper,
        covers_full_trip,
        required_checks,
    }
}

/// Compute the bounds implied by a predicate and constant.
fn bound_from_predicate(pred: &ICmpPredicate, bound: i64, iv_on_lhs: bool) -> (i64, i64) {
    // Default: full i32 range.
    let full_lo = i32::MIN as i64;
    let full_hi = i32::MAX as i64;

    match (pred, iv_on_lhs) {
        // IV < K: IV in [full_lo, K-1]
        (ICmpPredicate::SLT, true) | (ICmpPredicate::ULT, true) => (full_lo, bound - 1),
        // K < IV: IV in [K+1, full_hi]
        (ICmpPredicate::SLT, false) | (ICmpPredicate::ULT, false) => (bound + 1, full_hi),
        // IV <= K: IV in [full_lo, K]
        (ICmpPredicate::SLE, true) | (ICmpPredicate::ULE, true) => (full_lo, bound),
        // K <= IV: IV in [K, full_hi]
        (ICmpPredicate::SLE, false) | (ICmpPredicate::ULE, false) => (bound, full_hi),
        // IV > K: IV in [K+1, full_hi]
        (ICmpPredicate::SGT, true) | (ICmpPredicate::UGT, true) => (bound + 1, full_hi),
        // K > IV: IV in [full_lo, K-1]
        (ICmpPredicate::SGT, false) | (ICmpPredicate::UGT, false) => (full_lo, bound - 1),
        // IV >= K: IV in [K, full_hi]
        (ICmpPredicate::SGE, true) | (ICmpPredicate::UGE, true) => (bound, full_hi),
        // K >= IV: IV in [full_lo, K]
        (ICmpPredicate::SGE, false) | (ICmpPredicate::UGE, false) => (full_lo, bound),
        // IV == K: IV in [K, K]
        (ICmpPredicate::EQ, _) => (bound, bound),
        // IV != K: IV in [full_lo, full_hi]
        (ICmpPredicate::NE, _) => (full_lo, full_hi),
    }
}

/// Check if a range check is implied by the loop bounds.
fn check_implied_by_loop_bounds(
    check: &ParsedRangeCheck,
    scev: &SCEVExpr,
    trip_count: u64,
) -> bool {
    let (lo, hi) = scev.range(trip_count as i64);
    let (check_lo, check_hi) = bound_from_predicate(&check.predicate, check.bound, check.iv_on_lhs);

    // The check is implied if the loop's full range is within the check's range.
    lo >= check_lo && hi <= check_hi
}

// ============================================================================
// rewriteLoopWithBounds — Transform Loop Using Computed Bounds
// ============================================================================

/// Configuration for loop rewriting.
#[derive(Debug, Clone)]
pub struct LoopRewriteConfig {
    /// Whether to add explicit bounds checks in the preheader.
    pub add_preheader_checks: bool,
    /// Whether to widen the induction variable to i64 for overflow safety.
    pub widen_iv: bool,
    /// Maximum iteration count for unrolling during rewrite.
    pub max_unroll: u32,
}

impl Default for LoopRewriteConfig {
    fn default() -> Self {
        LoopRewriteConfig {
            add_preheader_checks: true,
            widen_iv: false,
            max_unroll: 0,
        }
    }
}

/// Result of rewriting a loop with bounds.
#[derive(Debug, Clone)]
pub struct LoopRewriteResult {
    /// The rewritten loop header.
    pub new_header: Option<ValueRef>,
    /// Number of checks eliminated.
    pub checks_eliminated: usize,
    /// Whether the rewrite was successful.
    pub success: bool,
}

/// Rewrite a loop to use safe computed bounds instead of range checks.
///
/// This is the core transformation: given a loop and its safe iteration
/// space, eliminate redundant range checks and (optionally) add a single
/// bounds check in the preheader.
pub fn rewrite_loop_with_bounds(
    _loop_structure: &LoopStructure,
    safe_space: &SafeIterationSpace,
    scev: &SCEVExpr,
    config: &LoopRewriteConfig,
) -> LoopRewriteResult {
    let mut result = LoopRewriteResult {
        new_header: None,
        checks_eliminated: 0,
        success: false,
    };

    // If the safe space covers the full trip, all range checks can be
    // eliminated.
    if safe_space.covers_full_trip {
        result.checks_eliminated = safe_space.required_checks.len();
        result.success = true;
        return result;
    }

    // Otherwise, we need to add a preheader check for the intersection
    // of all remaining required checks.
    if config.add_preheader_checks {
        // Compute a single preheader check that covers all required checks.
        let preheader_check_lo = safe_space.safe_lower;
        let preheader_check_hi = safe_space.safe_upper;

        // If the preheader check is meaningful (narrows the range),
        // the transformation is profitable.
        let loop_lo = scev.at(0);
        let loop_hi = scev.at(safe_space.safe_upper.max(0) as i64);

        if preheader_check_lo > loop_lo || preheader_check_hi < loop_hi {
            // The preheader check provides value.
            result.checks_eliminated = safe_space.required_checks.len().saturating_sub(1);
            result.success = true;
        }
    }

    result
}

// ============================================================================
// IRCE Profitability Model
// ============================================================================

/// Profitability analysis for inductive range check elimination.
#[derive(Debug, Clone)]
pub struct IRCEProfitability {
    /// Estimated number of dynamic instructions saved per loop iteration.
    pub insns_saved_per_iter: u64,
    /// Number of checks that can be eliminated.
    pub eliminable_checks: usize,
    /// Whether the elimination is definitely profitable.
    pub is_profitable: bool,
    /// Whether the elimination is trivially safe.
    pub is_trivially_safe: bool,
}

impl InductiveRangeCheckElimination {
    /// Evaluate profitability of eliminating range checks in a loop.
    ///
    /// Factors considered:
    /// - Trip count: higher trip counts make elimination more valuable
    /// - Check frequency: how many checks per iteration
    /// - Branch misprediction cost: each eliminated check avoids a branch
    /// - Code size: eliminating checks reduces code size
    pub fn evaluate_profitability(
        &self,
        checks: &[ParsedRangeCheck],
        trip_count: u64,
        _scev: &SCEVExpr,
    ) -> IRCEProfitability {
        let eliminable_count = checks
            .iter()
            .filter(|c| check_implied_by_loop_bounds(c, _scev, trip_count))
            .count();

        // Each eliminated check saves:
        // - One icmp instruction
        // - One conditional branch
        // Per iteration: ~2 instructions saved
        let insns_saved_per_iter = (eliminable_count as u64) * 2;

        // Total dynamic savings = per-iteration * trip count
        let _total_dynamic_savings = insns_saved_per_iter * trip_count;

        // Heuristic: profitable if at least one check can be eliminated
        // and trip count > 1.
        let is_profitable = eliminable_count > 0 && trip_count > 1;

        // Trivially safe if all checks are implied by loop bounds.
        let is_trivially_safe = eliminable_count == checks.len();

        IRCEProfitability {
            insns_saved_per_iter,
            eliminable_checks: eliminable_count,
            is_profitable,
            is_trivially_safe,
        }
    }

    /// Determine if IRCE should be applied to a loop.
    ///
    /// Combines profitability and safety analysis to make the final decision.
    pub fn should_apply_irce(
        &self,
        checks: &[ParsedRangeCheck],
        trip_count: u64,
        scev: &SCEVExpr,
    ) -> bool {
        if checks.is_empty() {
            return false;
        }

        let profit = self.evaluate_profitability(checks, trip_count, scev);

        if !profit.is_profitable {
            return false;
        }

        // Additional safety constraint: if SCEV may wrap, only apply
        // if trivially safe (all checks implied by bounds).
        if scev.may_wrap && !profit.is_trivially_safe {
            return false;
        }

        true
    }

    /// Compute the SCEV expression for an induction variable.
    pub fn compute_scev_for_iv(&self, iv: &InductionVariable, _bit_width: u32) -> SCEVExpr {
        let start = iv.start;
        let step = iv.step;

        // Determine if wrapping may occur based on bit width and step.
        let may_wrap = if step > 0 {
            // For positive step, check if start + step * max_trip overflows.
            let max_val = start.saturating_add(step.saturating_mul(1_000_000));
            max_val > i32::MAX as i64
        } else {
            let min_val = start.saturating_add(step.saturating_mul(1_000_000));
            min_val < i32::MIN as i64
        };

        SCEVExpr {
            start,
            step,
            may_wrap,
            bit_width: _bit_width,
        }
    }

    /// Run full IRCE on a function with profitability model.
    ///
    /// This is the enhanced version that:
    /// 1. Identifies loops and induction variables
    /// 2. Computes SCEV for each IV
    /// 3. Parses range checks in each loop
    /// 4. Evaluates profitability
    /// 5. Eliminates checks and rewrites loops
    pub fn run_with_profitability(&mut self, func: &ValueRef) -> usize {
        self.checks_eliminated = 0;
        self.loops_analyzed = 0;

        let loops = self.identify_loops(func);

        for l in &loops {
            self.loops_analyzed += 1;

            // Find induction variables.
            let ivs = self.find_induction_variables(func, l);
            if ivs.is_empty() {
                continue;
            }

            // Compute SCEV for the primary IV.
            let scev = self.compute_scev_for_iv(&ivs[0], 32);

            // Get trip count: estimate from induction variable bounds.
            let trip_count = if let Some(bound) = ivs[0].end_bound {
                let start = ivs[0].start;
                let step = ivs[0].step;
                if step != 0 {
                    ((bound - start) / step).unsigned_abs()
                } else {
                    0
                }
            } else {
                0
            };
            if trip_count == 0 {
                continue;
            }

            // Parse range checks.
            let mut checks: Vec<ParsedRangeCheck> = Vec::new();
            for block in &l.body {
                let insts = get_block_instructions(block);
                for inst in &insts {
                    if let Some(check) = parse_range_check(inst, &ivs) {
                        checks.push(check);
                    }
                }
            }

            if checks.is_empty() {
                continue;
            }

            // Evaluate profitability.
            if !self.should_apply_irce(&checks, trip_count, &scev) {
                continue;
            }

            // Compute safe iteration space.
            let safe_space = compute_safe_iteration_space(&checks, &scev, trip_count);

            // Rewrite the loop.
            let config = LoopRewriteConfig::default();
            let loop_struct = LoopStructure {
                header: l.header.clone(),
                latch: l.latch.clone(),
                body: l.body.clone(),
                preheader: l.preheader.clone(),
                exit_blocks: l.exit_blocks.clone(),
            };

            let rewrite_result =
                rewrite_loop_with_bounds(&loop_struct, &safe_space, &scev, &config);

            if rewrite_result.success {
                self.checks_eliminated += rewrite_result.checks_eliminated;
            }
        }

        self.checks_eliminated
    }

    /// Analyze and collect all range checks in a loop body.
    pub fn collect_range_checks(
        &self,
        loop_structure: &LoopStructure,
        ivs: &[InductionVariable],
    ) -> Vec<ParsedRangeCheck> {
        let mut checks = Vec::new();

        for block in &loop_structure.body {
            let insts = get_block_instructions(block);
            for inst in &insts {
                if let Some(check) = parse_range_check(inst, ivs) {
                    checks.push(check);
                }
            }
        }

        checks
    }

    /// Find range checks that guard loop exits.
    ///
    /// A range check guards a loop exit if it controls a branch that
    /// exits the loop when the check fails.
    pub fn find_exit_guarding_checks(
        &self,
        checks: &[ParsedRangeCheck],
        exit_blocks: &[ValueRef],
    ) -> Vec<ParsedRangeCheck> {
        let exit_vids: HashSet<u64> = exit_blocks.iter().map(|b| b.borrow().vid).collect();

        checks
            .iter()
            .filter(|check| {
                let cmp = check.cmp.borrow();
                // Check if this cmp's user is a branch to an exit block.
                cmp.uses.iter().any(|u| {
                    match u.user.upgrade() { Some(user) => {
                        let user_val = user.borrow();
                        if user_val.opcode == Some(Opcode::Br) {
                            user_val
                                .operands
                                .iter()
                                .skip(1)
                                .any(|succ| exit_vids.contains(&succ.borrow().vid))
                        } else {
                            false
                        }
                    } _ => {
                        false
                    }}
                })
            })
            .cloned()
            .collect()
    }
}

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

#[cfg(test)]
mod tests {
    use super::*;
    use llvm_native_core::basic_block::new_basic_block;
    use llvm_native_core::constants;
    use llvm_native_core::function::new_function;
    use llvm_native_core::instruction;
    use llvm_native_core::types::Type;

    fn build_simple_func() -> ValueRef {
        let func = new_function("simple", Type::void(), &[]);
        let entry = new_basic_block("entry");
        entry.borrow_mut().push_operand(instruction::ret_void());
        func.borrow_mut().push_operand(entry.clone());
        func
    }

    fn build_loop_func() -> ValueRef {
        let func = new_function("loop_func", Type::void(), &[]);
        let entry = new_basic_block("entry");
        let loop_hdr = new_basic_block("loop_header");
        let loop_body = new_basic_block("loop_body");
        let loop_latch = new_basic_block("loop_latch");
        let loop_exit = new_basic_block("loop_exit");

        // entry: br loop_header
        entry
            .borrow_mut()
            .push_operand(instruction::br(loop_hdr.clone()));

        // loop_header: phi, icmp, br cond loop_body loop_exit
        let i32_ty = Type::i32();
        let iv = instruction::phi(
            i32_ty.clone(),
            vec![
                (constants::const_i32(0), entry.clone()),
                (
                    llvm_native_core::value::valref(llvm_native_core::value::Value::new(llvm_native_core::types::Type::void())),
                    loop_latch.clone(),
                ), // placeholder
            ],
        );
        loop_hdr.borrow_mut().push_operand(iv.clone());

        let cmp = instruction::icmp(
            llvm_native_core::instruction::ICmpPred::Slt,
            iv.clone(),
            constants::const_i32(10),
        );
        loop_hdr.borrow_mut().push_operand(cmp.clone());
        loop_hdr.borrow_mut().push_operand(instruction::br_cond(
            cmp,
            loop_body.clone(),
            loop_exit.clone(),
        ));

        // loop_body: range check, fallthrough.
        let body_check = instruction::icmp(
            llvm_native_core::instruction::ICmpPred::Sge,
            iv,
            constants::const_i32(0),
        );
        loop_body.borrow_mut().push_operand(body_check);
        loop_body
            .borrow_mut()
            .push_operand(instruction::br(loop_latch.clone()));

        // loop_latch: increment and branch back.
        loop_latch
            .borrow_mut()
            .push_operand(instruction::br(loop_hdr.clone()));

        // loop_exit: return.
        loop_exit.borrow_mut().push_operand(instruction::ret_void());

        func.borrow_mut().push_operand(entry.clone());
        func.borrow_mut().push_operand(loop_hdr.clone());
        func.borrow_mut().push_operand(loop_body.clone());
        func.borrow_mut().push_operand(loop_latch.clone());
        func.borrow_mut().push_operand(loop_exit.clone());

        func
    }

    #[test]
    fn test_irce_new() {
        let irce = InductiveRangeCheckElimination::new();
        assert_eq!(irce.checks_eliminated, 0);
        assert_eq!(irce.loops_analyzed, 0);
    }

    #[test]
    fn test_irce_default() {
        let irce = InductiveRangeCheckElimination::default();
        assert_eq!(irce.checks_eliminated, 0);
    }

    #[test]
    fn test_run_on_simple_function() {
        let mut irce = InductiveRangeCheckElimination::new();
        let func = build_simple_func();
        let eliminated = irce.run_on_function(&func);
        // Simple function has no loops.
        assert_eq!(eliminated, 0);
    }

    #[test]
    fn test_identify_loops_simple() {
        let irce = InductiveRangeCheckElimination::new();
        let func = build_simple_func();
        let loops = irce.identify_loops(&func);
        assert!(loops.is_empty());
    }

    #[test]
    fn test_made_changes() {
        let irce = InductiveRangeCheckElimination::new();
        assert!(!irce.made_changes());
    }

    #[test]
    fn test_icmp_predicate_decode() {
        assert_eq!(
            InductiveRangeCheckElimination::decode_icmp_predicate(0),
            ICmpPredicate::EQ
        );
        assert_eq!(
            InductiveRangeCheckElimination::decode_icmp_predicate(6),
            ICmpPredicate::SGT
        );
        assert_eq!(
            InductiveRangeCheckElimination::decode_icmp_predicate(8),
            ICmpPredicate::SLT
        );
    }

    #[test]
    fn test_icmp_predicate_implies_lower() {
        assert!(ICmpPredicate::SGE.implies_lower_bound(5, 3));
        assert!(!ICmpPredicate::SGT.implies_lower_bound(5, 5));
        assert!(ICmpPredicate::SGT.implies_lower_bound(6, 5));
        assert!(ICmpPredicate::NE.implies_lower_bound(5, 3));
    }

    #[test]
    fn test_icmp_predicate_implies_upper() {
        assert!(ICmpPredicate::SLE.implies_upper_bound(3, 5));
        assert!(ICmpPredicate::SLT.implies_upper_bound(4, 5));
        assert!(!ICmpPredicate::SLT.implies_upper_bound(5, 5));
    }

    #[test]
    fn test_try_extract_constant() {
        let c = constants::const_i32(42);
        let val = try_extract_constant(&c);
        assert_eq!(val, Some(42));
    }

    #[test]
    fn test_get_phi_nodes() {
        let func = build_loop_func();
        let blocks = get_function_blocks(&func);
        let header = blocks
            .iter()
            .find(|b| b.borrow().get_name_or("") == "loop_header");
        if let Some(hdr) = header {
            let phis = get_phi_nodes(hdr);
            assert!(!phis.is_empty());
        }
    }

    #[test]
    fn test_is_terminator_opcode() {
        assert!(is_terminator_opcode(Opcode::Ret));
        assert!(is_terminator_opcode(Opcode::Br));
        assert!(!is_terminator_opcode(Opcode::Add));
    }

    #[test]
    fn test_build_predecessor_map() {
        let func = build_simple_func();
        let blocks = get_function_blocks(&func);
        let pred_map = build_predecessor_map(&blocks);
        // For a simple function with just ret, there are no successors.
        // Pred map may be empty. Just verify no panic.
        let _ = pred_map;
    }

    #[test]
    fn test_compute_dominators() {
        let func = build_simple_func();
        let blocks = get_function_blocks(&func);
        let dom = compute_dominators(&blocks);
        if !blocks.is_empty() {
            let entry_vid = blocks[0].borrow().vid;
            assert!(dom.contains_key(&entry_vid));
        }
    }

    #[test]
    fn test_dominates_self() {
        let func = build_simple_func();
        let blocks = get_function_blocks(&func);
        if !blocks.is_empty() {
            let dom = compute_dominators(&blocks);
            let entry = &blocks[0];
            assert!(dominates(&dom, entry, entry));
        }
    }

    #[test]
    fn test_loop_structure_fields() {
        let bb = new_basic_block("test");
        let ls = LoopStructure {
            header: bb.clone(),
            latch: bb.clone(),
            body: vec![bb.clone()],
            preheader: None,
            exit_blocks: Vec::new(),
        };
        assert_eq!(ls.body.len(), 1);
        assert!(ls.preheader.is_none());
    }
}