llvm-native-core-ext 0.1.0

//! LLVM IfConversion — converts short if-then-else patterns to predicated
//! instructions, eliminating branches and improving pipeline utilization.
//! Clean-room behavioral reconstruction.
//!
//! IfConversion identifies "diamond" control-flow patterns where a
//! conditional branch chooses between two short blocks (then/else) that
//! both merge at a common successor. When the target architecture supports
//! predicated (conditional) execution or conditional moves, the branches
//! can be eliminated by converting the diamond into straight-line code:
//!
//!   Before:           After (predicated):
//!   cmp r0, r1        cmp r0, r1
//!   bne else          add.ne r2, r3, r4   ; predicated then-block
//!   add r2, r3, r4    mov.eq r2, r5       ; predicated else-block
//!   j merge
//!   else:
//!   mov r2, r5
//!   merge:
//!
//! Two strategies are supported:
//!   - **Predicated execution**: each instruction in the then/else blocks
//!     is converted to a predicated version (e.g., ADD → ADDS.NE).
//!   - **Conditional move (cmov)**: a diamond that just selects between
//!     two values is converted to a conditional move instruction.
//!
//! Algorithm:
//!   1. Scan the CFG for diamond patterns: (cond_block, then_block, else_block).
//!   2. Determine if the then/else blocks are short enough to predicate
//!      (usually ≤ 5 instructions each).
//!   3. Check whether the target supports predication / cmov.
//!   4. Convert the diamond by merging instructions into the cond block.
//!   5. Remove the then/else blocks and redirect all successors.

use llvm_native_core::codegen::{MachineBasicBlock, MachineFunction, MachineInstr, MachineOperand};
use std::collections::HashMap;

// ============================================================================
// IfConversion Pass
// ============================================================================

/// IfConversion — converts short if-then-else patterns to predicated
/// instructions or conditional moves.
pub struct IfConversion {
    /// Number of diamonds converted to predicated code.
    pub predicated: usize,
    /// Number of diamonds converted to conditional moves.
    pub cmovs: usize,
    /// Whether to prefer predication over cmov.
    pub prefer_predication: bool,
}

impl IfConversion {
    /// Create a new IfConversion pass.
    pub fn new() -> Self {
        Self {
            predicated: 0,
            cmovs: 0,
            prefer_predication: true,
        }
    }

    /// Run if-conversion on a machine function.
    /// Returns the total number of diamonds converted.
    pub fn run_on_function(&mut self, mf: &mut MachineFunction) -> usize {
        self.predicated = 0;
        self.cmovs = 0;

        let diamonds = self.find_if_blocks(mf);

        for diamond in diamonds {
            let (cond_idx, then_idx, else_idx) = diamond;

            // Check if the then and else blocks can be predicated
            let then_ok = self.can_predicate(then_idx, mf);
            let else_ok = self.can_predicate(else_idx, mf);

            if then_ok && else_ok {
                // Check if it's a simple select (one instruction in each)
                let then_len = mf.blocks[then_idx].instructions.len();
                let else_len = mf.blocks[else_idx].instructions.len();

                if then_len == 1
                    && else_len == 1
                    && self.is_simple_select(&mf.blocks[then_idx], &mf.blocks[else_idx])
                {
                    self.convert_to_cmov(mf, diamond);
                    self.cmovs += 1;
                } else if self.prefer_predication {
                    self.convert_to_predicated(mf, diamond);
                    self.predicated += 1;
                } else {
                    self.convert_to_cmov(mf, diamond);
                    self.cmovs += 1;
                }
            }
        }

        self.predicated + self.cmovs
    }

    /// Find if-then-else diamond patterns in the function.
    /// Returns a list of (cond_block_idx, then_block_idx, else_block_idx).
    fn find_if_blocks(&self, mf: &MachineFunction) -> Vec<(usize, usize, usize)> {
        let mut diamonds = Vec::new();

        for (cond_idx, cond_block) in mf.blocks.iter().enumerate() {
            // Look for conditional blocks: 2 successors
            if cond_block.successors.len() != 2 {
                continue;
            }

            let then_idx = cond_block.successors[0];
            let else_idx = cond_block.successors[1];

            if then_idx < mf.blocks.len() && else_idx < mf.blocks.len() {
                // Verify this forms a diamond: both then/else branch to same successor
                let then_succ = &mf.blocks[then_idx].successors;
                let else_succ = &mf.blocks[else_idx].successors;

                if then_succ.len() == 1 && else_succ.len() == 1 {
                    if then_succ[0] == else_succ[0] {
                        diamonds.push((cond_idx, then_idx, else_idx));
                    }
                }

                // Also handle cases where one successor is empty (falls through)
                if then_succ.len() == 1 && else_succ.is_empty() {
                    // else falls through to the merge block after then
                    diamonds.push((cond_idx, then_idx, else_idx));
                }
            }
        }

        diamonds
    }

    /// Check whether a block is short enough and suitable for predication.
    fn can_predicate(&self, bb: usize, mf: &MachineFunction) -> bool {
        if bb >= mf.blocks.len() {
            return false;
        }
        let block = &mf.blocks[bb];
        let len = block.instructions.len();

        // Must be short (≤ 5 instructions)
        if len > 5 {
            return false;
        }

        // Must not contain branches (except terminators)
        for instr in &block.instructions {
            if self.is_branch(instr) && !self.is_unconditional_branch(instr) {
                return false;
            }
        }

        // Must not have side effects that can't be predicated
        for instr in &block.instructions {
            if self.has_hard_side_effect(instr) {
                return false;
            }
        }

        true
    }

    /// Convert a diamond to predicated instructions in the cond block.
    fn convert_to_predicated(&mut self, mf: &mut MachineFunction, diamond: (usize, usize, usize)) {
        let (cond_idx, then_idx, else_idx) = diamond;

        // Get instructions from then and else blocks
        let then_instrs = mf.blocks[then_idx].instructions.clone();
        let else_instrs = mf.blocks[else_idx].instructions.clone();

        // Find the terminator in the cond block and remove it
        let cond_block = &mut mf.blocks[cond_idx];
        while !cond_block.instructions.is_empty()
            && self.is_terminator(&cond_block.instructions[cond_block.instructions.len() - 1])
        {
            cond_block.instructions.pop();
        }

        // Append predicated then-block instructions
        for mut instr in then_instrs {
            if !self.is_unconditional_branch(&instr) {
                self.predicate_instr(&mut instr, true);
                mf.blocks[cond_idx].instructions.push(instr);
            }
        }

        // Append predicated else-block instructions
        for mut instr in else_instrs {
            if !self.is_unconditional_branch(&instr) {
                self.predicate_instr(&mut instr, false);
                mf.blocks[cond_idx].instructions.push(instr);
            }
        }

        // Update cond block's successors: now it goes directly to the merge block
        let merge_name = if !mf.blocks[then_idx].successors.is_empty() {
            mf.blocks[then_idx].successors[0].clone()
        } else if !mf.blocks[else_idx].successors.is_empty() {
            mf.blocks[else_idx].successors[0].clone()
        } else {
            return;
        };

        mf.blocks[cond_idx].successors = vec![merge_name];

        // Clear then/else blocks
        mf.blocks[then_idx].instructions.clear();
        mf.blocks[then_idx].successors.clear();
        mf.blocks[else_idx].instructions.clear();
        mf.blocks[else_idx].successors.clear();
    }

    /// Convert a diamond to a conditional move.
    fn convert_to_cmov(&mut self, mf: &mut MachineFunction, diamond: (usize, usize, usize)) {
        let (cond_idx, then_idx, else_idx) = diamond;

        // For a cmov, the pattern is typically:
        //   then: mov dst, true_val
        //   else: mov dst, false_val
        // We convert to: cmov dst, true_val, false_val, cond

        let then_instr = mf.blocks[then_idx].instructions.last().cloned();
        let else_instr = mf.blocks[else_idx].instructions.last().cloned();

        if let (Some(ti), Some(ei)) = (then_instr, else_instr) {
            // Create a cmov instruction
            let mut cmov = MachineInstr::new(0xFFFF); // placeholder cmov opcode
                                                      // Then-value operands
            for op in &ti.operands {
                cmov.operands.push(op.clone());
            }
            // Else-value operands
            for op in &ei.operands {
                cmov.operands.push(op.clone());
            }

            // Remove terminator from cond block and append cmov
            let cond_block = &mut mf.blocks[cond_idx];
            while !cond_block.instructions.is_empty()
                && self.is_terminator(&cond_block.instructions[cond_block.instructions.len() - 1])
            {
                cond_block.instructions.pop();
            }
            cond_block.instructions.push(cmov);

            // Update successors to merge block
            let merge_name = if !mf.blocks[then_idx].successors.is_empty() {
                mf.blocks[then_idx].successors[0].clone()
            } else {
                return;
            };
            mf.blocks[cond_idx].successors = vec![merge_name];

            // Clear then/else
            mf.blocks[then_idx].instructions.clear();
            mf.blocks[then_idx].successors.clear();
            mf.blocks[else_idx].instructions.clear();
            mf.blocks[else_idx].successors.clear();
        }
    }

    /// Check if two blocks form a simple select pattern
    /// (both write to the same destination register).
    fn is_simple_select(
        &self,
        then_block: &MachineBasicBlock,
        else_block: &MachineBasicBlock,
    ) -> bool {
        if then_block.instructions.is_empty() || else_block.instructions.is_empty() {
            return false;
        }

        let ti = &then_block.instructions[then_block.instructions.len() - 1];
        let ei = &else_block.instructions[else_block.instructions.len() - 1];

        // Both must define a register (have a def)
        ti.def.is_some() && ei.def.is_some()
    }

    /// Mark an instruction as predicated (modify its opcode or add a flag).
    /// `when_true`: true = execute when condition is true, false = execute
    /// when condition is false.
    fn predicate_instr(&self, instr: &mut MachineInstr, when_true: bool) {
        // In a real backend, this would modify the opcode to a predicated
        // variant. Here we add a flag operand to indicate predication.
        let flag = if when_true { 1 } else { 0 };
        instr.operands.insert(0, MachineOperand::Imm(flag));
    }

    /// Check if an instruction is a terminator (branch/return).
    fn is_terminator(&self, instr: &MachineInstr) -> bool {
        self.is_branch(instr) || self.is_unconditional_branch(instr)
    }

    /// Check if an instruction is a conditional branch.
    fn is_branch(&self, instr: &MachineInstr) -> bool {
        let has_label = instr
            .operands
            .iter()
            .any(|op| matches!(op, MachineOperand::Label(_)));
        has_label && instr.operands.len() >= 2
    }

    /// Check if an instruction is an unconditional branch.
    fn is_unconditional_branch(&self, instr: &MachineInstr) -> bool {
        let has_label = instr
            .operands
            .iter()
            .any(|op| matches!(op, MachineOperand::Label(_)));
        has_label && instr.operands.len() == 1
    }

    /// Check if an instruction has hard side effects that prevent predication.
    fn has_hard_side_effect(&self, _instr: &MachineInstr) -> bool {
        // Calls, stores, and system instructions can't be easily predicated
        // In a simplified model, we assume no hard side effects for ALU ops
        false
    }

    /// Find the block index for a given block name.
    fn find_block_idx(&self, mf: &MachineFunction, name: &str) -> Option<usize> {
        mf.blocks.iter().position(|b| b.name == name)
    }
}

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

// ============================================================================
// Condition Codes for Predication
// ============================================================================

/// Condition code for predicated execution.
/// Maps to architecture-specific condition flags.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum PredicateCondition {
    /// Always execute.
    AL,
    /// Equal (zero flag set).
    EQ,
    /// Not equal (zero flag clear).
    NE,
    /// Carry set / unsigned higher or same.
    CS,
    /// Carry clear / unsigned lower.
    CC,
    /// Negative (sign flag set).
    MI,
    /// Positive or zero (sign flag clear).
    PL,
    /// Overflow set.
    VS,
    /// Overflow clear.
    VC,
    /// Unsigned higher.
    HI,
    /// Unsigned lower or same.
    LS,
    /// Signed greater than or equal.
    GE,
    /// Signed less than.
    LT,
    /// Signed greater than.
    GT,
    /// Signed less than or equal.
    LE,
}

impl PredicateCondition {
    /// Get the inverse condition.
    pub fn inverse(self) -> Self {
        match self {
            PredicateCondition::EQ => PredicateCondition::NE,
            PredicateCondition::NE => PredicateCondition::EQ,
            PredicateCondition::CS => PredicateCondition::CC,
            PredicateCondition::CC => PredicateCondition::CS,
            PredicateCondition::MI => PredicateCondition::PL,
            PredicateCondition::PL => PredicateCondition::MI,
            PredicateCondition::VS => PredicateCondition::VC,
            PredicateCondition::VC => PredicateCondition::VS,
            PredicateCondition::HI => PredicateCondition::LS,
            PredicateCondition::LS => PredicateCondition::HI,
            PredicateCondition::GE => PredicateCondition::LT,
            PredicateCondition::LT => PredicateCondition::GE,
            PredicateCondition::GT => PredicateCondition::LE,
            PredicateCondition::LE => PredicateCondition::GT,
            PredicateCondition::AL => PredicateCondition::AL,
        }
    }

    /// Get the condition for the "true" path of an if-then-else.
    pub fn for_true_path(self) -> Self {
        self
    }

    /// Get the condition for the "false" path of an if-then-else.
    pub fn for_false_path(self) -> Self {
        self.inverse()
    }

    /// Check if this condition indicates always-execute.
    pub fn is_always(self) -> bool {
        matches!(self, PredicateCondition::AL)
    }
}

// ============================================================================
// Predicated Instruction
// ============================================================================

/// A predicated machine instruction: an instruction that only executes
/// when a given condition code is satisfied by the processor flags.
#[derive(Debug, Clone)]
pub struct PredicateInstruction {
    /// The underlying machine instruction.
    pub instr: MachineInstr,
    /// The condition under which this instruction executes.
    pub condition: PredicateCondition,
    /// Whether this is the "true" side of a conditional.
    pub is_true_path: bool,
}

impl PredicateInstruction {
    /// Create a new predicated instruction.
    pub fn new(instr: MachineInstr, condition: PredicateCondition, is_true_path: bool) -> Self {
        Self {
            instr,
            condition,
            is_true_path,
        }
    }

    /// Check if this instruction always executes.
    pub fn is_unconditional(&self) -> bool {
        self.condition.is_always()
    }

    /// Convert to a plain machine instruction with predicate flag encoded.
    pub fn into_predicated_instr(mut self) -> MachineInstr {
        // Encode the condition as an immediate operand (simplified model)
        let cond_flag = match (self.condition, self.is_true_path) {
            (PredicateCondition::AL, _) => 0,
            (cond, true) => 1 + (cond as u32) * 2,
            (cond, false) => 2 + (cond as u32) * 2,
        };
        self.instr
            .operands
            .insert(0, MachineOperand::Imm(cond_flag as i64));
        self.instr
    }
}

/// Builder for creating predicated instruction sequences.
pub struct PredicateInstrBuilder {
    /// The condition governing execution.
    pub condition: PredicateCondition,
    /// Whether we're building the true or false path.
    pub is_true_path: bool,
}

impl PredicateInstrBuilder {
    /// Create a builder for the true path.
    pub fn for_true(condition: PredicateCondition) -> Self {
        Self {
            condition,
            is_true_path: true,
        }
    }

    /// Create a builder for the false path.
    pub fn for_false(condition: PredicateCondition) -> Self {
        Self {
            condition,
            is_true_path: false,
        }
    }

    /// Predicate a machine instruction.
    pub fn predicate(&self, mut instr: MachineInstr) -> PredicateInstruction {
        PredicateInstruction::new(instr, self.condition, self.is_true_path)
    }
}

// ============================================================================
// CFG Pattern Detection
// ============================================================================

/// Represents a diamond pattern in the CFG.
///
/// ```text
///        cond_block
///        /        \
///   true_block  false_block
///        \        /
///       merge_block
/// ```
#[derive(Debug, Clone)]
pub struct DiamondPattern {
    /// The block that computes the condition.
    pub cond_block: usize,
    /// The block executed when the condition is true.
    pub true_block: usize,
    /// The block executed when the condition is false.
    pub false_block: usize,
    /// The merge point for both paths.
    pub merge_block: usize,
    /// The condition code derived from the compare instruction.
    pub condition: PredicateCondition,
}

/// Represents a triangle pattern in the CFG.
///
/// ```text
///        cond_block
///        /        \
///   true_block    (fallthrough)
///        \        /
///       merge_block
/// ```
#[derive(Debug, Clone)]
pub struct TrianglePattern {
    /// The block that computes the condition.
    pub cond_block: usize,
    /// The block executed when the condition is true.
    pub true_block: usize,
    /// The merge point (also the false target, fallthrough).
    pub merge_block: usize,
    /// The condition code.
    pub condition: PredicateCondition,
}

/// Represents a simple if-then (no else) pattern.
///
/// ```text
///        cond_block
///        /        \(
///   true_block    (next_layout_block)
/// ```
#[derive(Debug, Clone)]
pub struct IfThenPattern {
    /// The condition block.
    pub cond_block: usize,
    /// The block executed when condition is true.
    pub true_block: usize,
    /// The block that follows (fallthrough or branch target).
    pub next_block: usize,
    /// The condition code.
    pub condition: PredicateCondition,
}

/// Pattern matcher for CFG subgraphs.
pub struct CFGPatternMatcher;

impl CFGPatternMatcher {
    /// Find all diamond patterns in the function.
    pub fn find_diamonds(mf: &MachineFunction) -> Vec<DiamondPattern> {
        let mut diamonds = Vec::new();

        for (cond_idx, cond_block) in mf.blocks.iter().enumerate() {
            if cond_block.successors.len() != 2 {
                continue;
            }

            let succ_t = cond_block.successors[0];
            let succ_f = cond_block.successors[1];

            let true_idx = succ_t;
            let false_idx = succ_f;

            if true_idx >= mf.blocks.len() || false_idx >= mf.blocks.len() {
                continue;
            };

            let true_succs = &mf.blocks[true_idx].successors;
            let false_succs = &mf.blocks[false_idx].successors;

            // Both must have exactly one successor pointing to the same merge
            if true_succs.len() == 1 && false_succs.len() == 1 {
                if true_succs[0] == false_succs[0] {
                    let merge_idx = true_succs[0];
                    let condition = Self::infer_condition(cond_block);
                    diamonds.push(DiamondPattern {
                        cond_block: cond_idx,
                        true_block: true_idx,
                        false_block: false_idx,
                        merge_block: merge_idx,
                        condition,
                    });
                }
            }

            // Also handle: true has 1 successor to merge, false is empty
            // (the false path is fallthrough to a block after cond block)
            if true_succs.len() == 1 && false_succs.is_empty() {
                if cond_idx + 1 < mf.blocks.len() {
                    let condition = Self::infer_condition(cond_block);
                    diamonds.push(DiamondPattern {
                        cond_block: cond_idx,
                        true_block: true_idx,
                        false_block: false_idx,
                        merge_block: cond_idx + 1,
                        condition,
                    });
                }
            }
        }

        diamonds
    }

    /// Find triangle patterns.
    pub fn find_triangles(mf: &MachineFunction) -> Vec<TrianglePattern> {
        let mut triangles = Vec::new();

        for (cond_idx, cond_block) in mf.blocks.iter().enumerate() {
            if cond_block.successors.len() != 2 {
                continue;
            }

            let succ_t = cond_block.successors[0];
            let succ_f = cond_block.successors[1];

            let true_idx = succ_t;

            if true_idx >= mf.blocks.len() {
                continue;
            };

            let true_succs = &mf.blocks[true_idx].successors;

            // Triangle: true block branches to the same block as the false path
            if true_succs.len() == 1 {
                if true_succs[0] == succ_f {
                    let merge_idx = succ_f;
                    let condition = Self::infer_condition(cond_block);
                    triangles.push(TrianglePattern {
                        cond_block: cond_idx,
                        true_block: true_idx,
                        merge_block: merge_idx,
                        condition,
                    });
                }
            }
        }

        triangles
    }

    /// Find simple if-then patterns.
    pub fn find_if_thens(mf: &MachineFunction) -> Vec<IfThenPattern> {
        let mut patterns = Vec::new();

        for (cond_idx, cond_block) in mf.blocks.iter().enumerate() {
            if cond_block.successors.len() != 2 {
                continue;
            }

            let succ_t = cond_block.successors[0];
            let succ_f = cond_block.successors[1];

            let true_idx = succ_t;
            let next_idx = succ_f;

            if true_idx >= mf.blocks.len() {
                continue;
            };

            // If-then: false target is the next block in layout
            if next_idx > cond_idx && next_idx == cond_idx + 1 {
                let condition = Self::infer_condition(cond_block);
                patterns.push(IfThenPattern {
                    cond_block: cond_idx,
                    true_block: true_idx,
                    next_block: next_idx,
                    condition,
                });
            } else if cond_idx + 1 < mf.blocks.len() {
                // False path is fallthrough to next layout block
                let condition = Self::infer_condition(cond_block);
                patterns.push(IfThenPattern {
                    cond_block: cond_idx,
                    true_block: true_idx,
                    next_block: cond_idx + 1,
                    condition,
                });
            }
        }

        patterns
    }

    /// Infer predicate condition from the compare instruction in a block.
    fn infer_condition(block: &MachineBasicBlock) -> PredicateCondition {
        // Look for compare-like instructions and derive condition
        if block.instructions.len() < 1 {
            return PredicateCondition::AL;
        }

        let last_instr = &block.instructions[block.instructions.len() - 1];

        // Heuristic: if the last instruction has a label operand, it's a
        // conditional branch. Infer condition from opcode pattern.
        let has_label = last_instr
            .operands
            .iter()
            .any(|op| matches!(op, MachineOperand::Label(_)));

        if has_label {
            // Check for compare in second-to-last position
            if block.instructions.len() >= 2 {
                let cmp = &block.instructions[block.instructions.len() - 2];
                // Infer from opcode: even → EQ, odd → NE
                if cmp.opcode % 2 == 0 {
                    PredicateCondition::EQ
                } else {
                    PredicateCondition::NE
                }
            } else {
                PredicateCondition::NE
            }
        } else {
            // No explicit branch — check for implicit condition via def/use
            PredicateCondition::AL
        }
    }
}

// ============================================================================
// Profitability Analysis
// ============================================================================

/// Cost model for evaluating if-conversion profitability.
#[derive(Debug, Clone)]
pub struct IfConversionCost {
    /// Estimated cycles saved by eliminating the branch.
    pub branch_cycles_saved: u32,
    /// Estimated cycles added by predicate overhead.
    pub predication_overhead: u32,
    /// Estimated code size reduction in bytes.
    pub code_size_delta: i64,
    /// Whether predication is profitable.
    pub is_profitable: bool,
}

impl Default for IfConversionCost {
    fn default() -> Self {
        Self {
            branch_cycles_saved: 0,
            predication_overhead: 0,
            code_size_delta: 0,
            is_profitable: false,
        }
    }
}

/// IfConverter with profitability analysis — evaluates whether to
/// predicate, use cmov, or leave branches as-is.
///
/// Applies a cost model:
///   - Branch mispredict penalty: ~15-20 cycles on modern CPUs
///   - Predicated instruction overhead: 1 cycle per predicated instruction
///   - Code size: predicated code may be larger or smaller
///   - Critical path: predication may increase latency if both paths execute
pub struct IfConverter {
    /// Base if-conversion pass.
    pub base: IfConversion,
    /// Maximum instructions per path for predication (exceeding → too costly).
    pub max_pred_instructions: usize,
    /// Estimated branch misprediction penalty in cycles.
    pub mispredict_penalty: u32,
    /// Minimum savings for predication to be profitable.
    pub min_savings: u32,
    /// Number of profitable conversions performed.
    pub profitable_conversions: usize,
    /// Number of unprofitable conversions skipped.
    pub skipped_conversions: usize,
    /// Detailed costs for each decision.
    pub cost_history: Vec<IfConversionCost>,
}

impl IfConverter {
    /// Create a new IfConverter.
    pub fn new() -> Self {
        Self {
            base: IfConversion::new(),
            max_pred_instructions: 5,
            mispredict_penalty: 16,
            min_savings: 2,
            profitable_conversions: 0,
            skipped_conversions: 0,
            cost_history: Vec::new(),
        }
    }

    /// Run if-conversion with profitability analysis.
    pub fn run_on_function(&mut self, mf: &mut MachineFunction) -> usize {
        self.profitable_conversions = 0;
        self.skipped_conversions = 0;
        self.cost_history.clear();

        // Step 1: Find all candidates
        let diamonds = CFGPatternMatcher::find_diamonds(mf);
        let triangles = CFGPatternMatcher::find_triangles(mf);
        let if_thens = CFGPatternMatcher::find_if_thens(mf);

        // Step 2: Evaluate each diamond
        for diamond in &diamonds {
            let cost = self.evaluate_diamond(mf, diamond);
            self.cost_history.push(cost.clone());

            if cost.is_profitable {
                // Perform the conversion
                let diamond_tuple = (diamond.cond_block, diamond.true_block, diamond.false_block);
                self.convert_diamond(mf, diamond);
                self.profitable_conversions += 1;
            } else {
                self.skipped_conversions += 1;
            }
        }

        // Step 3: Evaluate each triangle
        for triangle in &triangles {
            let cost = self.evaluate_triangle(mf, triangle);
            self.cost_history.push(cost.clone());

            if cost.is_profitable {
                self.convert_triangle(mf, triangle);
                self.profitable_conversions += 1;
            } else {
                self.skipped_conversions += 1;
            }
        }

        // Step 4: Evaluate each if-then
        for if_then in &if_thens {
            let cost = self.evaluate_if_then(mf, if_then);
            self.cost_history.push(cost.clone());

            if cost.is_profitable {
                self.convert_if_then(mf, if_then);
                self.profitable_conversions += 1;
            } else {
                self.skipped_conversions += 1;
            }
        }

        self.profitable_conversions
    }

    /// Evaluate the profitability of converting a diamond.
    fn evaluate_diamond(&self, mf: &MachineFunction, diamond: &DiamondPattern) -> IfConversionCost {
        let true_len = mf.blocks[diamond.true_block].instructions.len();
        let false_len = mf.blocks[diamond.false_block].instructions.len();

        if true_len > self.max_pred_instructions || false_len > self.max_pred_instructions {
            return IfConversionCost::default();
        }

        // Branch cycles saved: 1 taken branch (~2-3 cycles) + mispredict avoided
        let predicated_instrs = (true_len + false_len) as u32;
        let branch_cycles_saved = self.mispredict_penalty / 2 + 3;
        let predication_overhead = predicated_instrs;
        let code_size_delta = (predicated_instrs as i64) - 4; // -4 for removed branch + labels

        let is_profitable = branch_cycles_saved > predication_overhead
            || branch_cycles_saved.saturating_sub(predication_overhead) >= self.min_savings;

        IfConversionCost {
            branch_cycles_saved,
            predication_overhead,
            code_size_delta,
            is_profitable,
        }
    }

    /// Evaluate a triangle pattern.
    fn evaluate_triangle(
        &self,
        mf: &MachineFunction,
        triangle: &TrianglePattern,
    ) -> IfConversionCost {
        let true_len = mf.blocks[triangle.true_block].instructions.len();

        if true_len > self.max_pred_instructions {
            return IfConversionCost::default();
        }

        let branch_cycles_saved = self.mispredict_penalty / 2 + 2;
        let predication_overhead = true_len as u32;
        let code_size_delta = (true_len as i64) - 3;
        let is_profitable = branch_cycles_saved + 2 > predication_overhead;

        IfConversionCost {
            branch_cycles_saved,
            predication_overhead,
            code_size_delta,
            is_profitable,
        }
    }

    /// Evaluate an if-then pattern.
    fn evaluate_if_then(&self, mf: &MachineFunction, if_then: &IfThenPattern) -> IfConversionCost {
        let true_len = mf.blocks[if_then.true_block].instructions.len();

        if true_len > self.max_pred_instructions {
            return IfConversionCost::default();
        }

        let branch_cycles_saved = self.mispredict_penalty / 2 + 1;
        let predication_overhead = true_len as u32;
        let code_size_delta = (true_len as i64) - 2;
        let is_profitable = branch_cycles_saved >= predication_overhead;

        IfConversionCost {
            branch_cycles_saved,
            predication_overhead,
            code_size_delta,
            is_profitable,
        }
    }

    /// Convert a diamond pattern to predicated code.
    fn convert_diamond(&self, mf: &mut MachineFunction, diamond: &DiamondPattern) {
        // Clone data first to avoid borrowing conflicts
        let true_instrs: Vec<MachineInstr> = mf.blocks[diamond.true_block]
            .instructions
            .iter()
            .filter(|instr| {
                !instr
                    .operands
                    .iter()
                    .any(|op| matches!(op, MachineOperand::Label(_)))
            })
            .cloned()
            .collect();
        let false_instrs: Vec<MachineInstr> = mf.blocks[diamond.false_block]
            .instructions
            .iter()
            .filter(|instr| {
                !instr
                    .operands
                    .iter()
                    .any(|op| matches!(op, MachineOperand::Label(_)))
            })
            .cloned()
            .collect();
        let merge_idx = diamond.merge_block;

        // Now mutate the cond block
        let cond_block = &mut mf.blocks[diamond.cond_block];

        // Remove branch terminator from cond block
        while !cond_block.instructions.is_empty() {
            let last = cond_block.instructions.last().unwrap();
            let has_label = last
                .operands
                .iter()
                .any(|op| matches!(op, MachineOperand::Label(_)));
            if has_label {
                cond_block.instructions.pop();
            } else {
                break;
            }
        }

        // Append predicated true-block instructions
        let true_builder = PredicateInstrBuilder::for_true(diamond.condition);
        for instr in &true_instrs {
            let pred_instr = true_builder.predicate(instr.clone());
            cond_block
                .instructions
                .push(pred_instr.into_predicated_instr());
        }

        // Append predicated false-block instructions
        let false_builder = PredicateInstrBuilder::for_false(diamond.condition);
        for instr in &false_instrs {
            let pred_instr = false_builder.predicate(instr.clone());
            cond_block
                .instructions
                .push(pred_instr.into_predicated_instr());
        }

        // Update successors to merge block
        cond_block.successors = vec![merge_idx];

        // Clear true/false blocks
        mf.blocks[diamond.true_block].instructions.clear();
        mf.blocks[diamond.true_block].successors.clear();
        mf.blocks[diamond.false_block].instructions.clear();
        mf.blocks[diamond.false_block].successors.clear();
    }

    /// Convert a triangle pattern to predicated code.
    fn convert_triangle(&self, mf: &mut MachineFunction, triangle: &TrianglePattern) {
        // Clone true block instructions first
        let true_instrs: Vec<MachineInstr> = mf.blocks[triangle.true_block]
            .instructions
            .iter()
            .filter(|instr| {
                !instr
                    .operands
                    .iter()
                    .any(|op| matches!(op, MachineOperand::Label(_)))
            })
            .cloned()
            .collect();

        let cond_block = &mut mf.blocks[triangle.cond_block];

        // Remove branch terminator
        while !cond_block.instructions.is_empty() {
            let last = cond_block.instructions.last().unwrap();
            let has_label = last
                .operands
                .iter()
                .any(|op| matches!(op, MachineOperand::Label(_)));
            if has_label {
                cond_block.instructions.pop();
            } else {
                break;
            }
        }

        // Append predicated true-block instructions
        let true_builder = PredicateInstrBuilder::for_true(triangle.condition);
        for instr in &true_instrs {
            let pred_instr = true_builder.predicate(instr.clone());
            cond_block
                .instructions
                .push(pred_instr.into_predicated_instr());
        }

        // Update successors
        cond_block.successors = vec![triangle.merge_block];

        // Clear true block
        mf.blocks[triangle.true_block].instructions.clear();
        mf.blocks[triangle.true_block].successors.clear();
    }

    /// Convert an if-then pattern to predicated code.
    fn convert_if_then(&self, mf: &mut MachineFunction, if_then: &IfThenPattern) {
        // Clone true block instructions first
        let true_instrs: Vec<MachineInstr> = mf.blocks[if_then.true_block]
            .instructions
            .iter()
            .filter(|instr| {
                !instr
                    .operands
                    .iter()
                    .any(|op| matches!(op, MachineOperand::Label(_)))
            })
            .cloned()
            .collect();

        let cond_block = &mut mf.blocks[if_then.cond_block];

        // Remove branch terminator
        while !cond_block.instructions.is_empty() {
            let last = cond_block.instructions.last().unwrap();
            let has_label = last
                .operands
                .iter()
                .any(|op| matches!(op, MachineOperand::Label(_)));
            if has_label {
                cond_block.instructions.pop();
            } else {
                break;
            }
        }

        // Append predicated true-block instructions
        let true_builder = PredicateInstrBuilder::for_true(if_then.condition);
        for instr in &true_instrs {
            let pred_instr = true_builder.predicate(instr.clone());
            cond_block
                .instructions
                .push(pred_instr.into_predicated_instr());
        }

        // Update successors
        cond_block.successors = vec![if_then.next_block];

        // Clear true block
        mf.blocks[if_then.true_block].instructions.clear();
        mf.blocks[if_then.true_block].successors.clear();
    }

    /// Print profitability statistics.
    pub fn print_stats(&self) {
        eprintln!(
            "IfConverter: {} profitable conversions, {} skipped",
            self.profitable_conversions, self.skipped_conversions
        );
        let total_saved: i64 = self
            .cost_history
            .iter()
            .filter(|c| c.is_profitable)
            .map(|c| c.branch_cycles_saved as i64 - c.predication_overhead as i64)
            .sum();
        eprintln!("  Estimated cycles saved: {}", total_saved);
    }
}

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

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

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

    fn make_block(name: &str, instrs: Vec<MachineInstr>, succs: Vec<usize>) -> MachineBasicBlock {
        MachineBasicBlock {
            id: 0,
            name: name.to_string(),
            instructions: instrs,
            successors: succs,
            predecessors: vec![],
            is_entry: false,
        }
    }

    fn make_instr(opcode: u32, operands: Vec<MachineOperand>) -> MachineInstr {
        let mut instr = MachineInstr::new(opcode);
        for op in operands {
            instr.operands.push(op);
        }
        instr
    }

    fn make_br(target: &str) -> MachineInstr {
        make_instr(0, vec![MachineOperand::Label(target.to_string())])
    }

    fn make_cond_br(target: &str) -> MachineInstr {
        make_instr(
            1,
            vec![
                MachineOperand::Reg(0),
                MachineOperand::Label(target.to_string()),
            ],
        )
    }

    #[test]
    fn test_new() {
        let ifc = IfConversion::new();
        assert_eq!(ifc.predicated, 0);
        assert_eq!(ifc.cmovs, 0);
    }

    #[test]
    fn test_run_on_empty_function() {
        let mut ifc = IfConversion::new();
        let mut mf = MachineFunction::new("empty");
        assert_eq!(ifc.run_on_function(&mut mf), 0);
    }

    #[test]
    fn test_run_on_single_block() {
        let mut ifc = IfConversion::new();
        let mut mf = MachineFunction::new("test");
        mf.blocks
            .push(make_block("entry", vec![make_instr(1, vec![])], vec![]));
        assert_eq!(ifc.run_on_function(&mut mf), 0);
    }

    #[test]
    fn test_find_if_blocks_no_diamond() {
        let ifc = IfConversion::new();
        let mut mf = MachineFunction::new("test");
        mf.blocks
            .push(make_block("entry", vec![make_cond_br("then")], vec![1, 2]));
        mf.blocks
            .push(make_block("then", vec![make_br("merge")], vec![3]));
        mf.blocks
            .push(make_block("else", vec![make_br("other")], vec![4]));
        mf.blocks.push(make_block("merge", vec![], vec![]));
        mf.blocks.push(make_block("other", vec![], vec![]));
        // Not a diamond: then→merge, else→other (different successors)
        let diamonds = ifc.find_if_blocks(&mf);
        assert!(diamonds.is_empty());
    }

    #[test]
    fn test_find_if_blocks_diamond() {
        let ifc = IfConversion::new();
        let mut mf = MachineFunction::new("test");
        mf.blocks
            .push(make_block("entry", vec![make_cond_br("then")], vec![1, 2]));
        mf.blocks.push(make_block(
            "then",
            vec![make_instr(2, vec![MachineOperand::Reg(0)])],
            vec![3],
        ));
        mf.blocks.push(make_block(
            "else",
            vec![make_instr(3, vec![MachineOperand::Reg(0)])],
            vec![3],
        ));
        mf.blocks.push(make_block("merge", vec![], vec![]));
        let diamonds = ifc.find_if_blocks(&mf);
        assert_eq!(diamonds.len(), 1);
        assert_eq!(diamonds[0], (0, 1, 2));
    }

    #[test]
    fn test_can_predicate_short_block() {
        let ifc = IfConversion::new();
        let mut mf = MachineFunction::new("test");
        mf.blocks.push(make_block(
            "bb",
            vec![
                make_instr(1, vec![MachineOperand::Reg(0)]),
                make_instr(2, vec![MachineOperand::Reg(1)]),
            ],
            vec![],
        ));
        assert!(ifc.can_predicate(0, &mf));
    }

    #[test]
    fn test_can_predicate_too_long() {
        let ifc = IfConversion::new();
        let mut mf = MachineFunction::new("test");
        let instrs: Vec<MachineInstr> = (0..6)
            .map(|i| make_instr(i, vec![MachineOperand::Reg(0)]))
            .collect();
        mf.blocks.push(make_block("bb", instrs, vec![]));
        assert!(!ifc.can_predicate(0, &mf));
    }

    #[test]
    fn test_is_simple_select() {
        let ifc = IfConversion::new();
        let mut then_block = make_block(
            "then",
            vec![make_instr(1, vec![MachineOperand::Reg(0)])],
            vec![],
        );
        then_block.instructions[0].def = Some(10);
        let mut else_block = make_block(
            "else",
            vec![make_instr(2, vec![MachineOperand::Reg(0)])],
            vec![],
        );
        else_block.instructions[0].def = Some(10);
        assert!(ifc.is_simple_select(&then_block, &else_block));
    }

    #[test]
    fn test_is_simple_select_no_def() {
        let ifc = IfConversion::new();
        let then_block = make_block(
            "then",
            vec![make_instr(1, vec![MachineOperand::Reg(0)])],
            vec![],
        );
        let else_block = make_block(
            "else",
            vec![make_instr(2, vec![MachineOperand::Reg(0)])],
            vec![],
        );
        assert!(!ifc.is_simple_select(&then_block, &else_block));
    }

    #[test]
    fn test_is_terminator() {
        let ifc = IfConversion::new();
        let br = make_br("L0");
        assert!(ifc.is_terminator(&br));
        let alu = make_instr(1, vec![MachineOperand::Reg(0)]);
        assert!(!ifc.is_terminator(&alu));
    }

    #[test]
    fn test_is_branch() {
        let ifc = IfConversion::new();
        let cond_br = make_cond_br("L0");
        assert!(ifc.is_branch(&cond_br));
        let uncond_br = make_br("L0");
        assert!(!ifc.is_branch(&uncond_br));
    }

    #[test]
    fn test_find_block_idx() {
        let ifc = IfConversion::new();
        let mut mf = MachineFunction::new("test");
        mf.blocks.push(make_block("bb0", vec![], vec![]));
        mf.blocks.push(make_block("bb1", vec![], vec![]));
        assert_eq!(ifc.find_block_idx(&mf, "bb0"), Some(0));
        assert_eq!(ifc.find_block_idx(&mf, "bb1"), Some(1));
        assert_eq!(ifc.find_block_idx(&mf, "nonexistent"), None);
    }

    #[test]
    fn test_convert_to_cmov() {
        let mut ifc = IfConversion::new();
        let mut mf = MachineFunction::new("test");
        mf.blocks
            .push(make_block("entry", vec![make_cond_br("then")], vec![1, 2]));
        let mut then_instr = make_instr(2, vec![MachineOperand::Reg(1)]);
        then_instr.def = Some(10);
        let mut else_instr = make_instr(3, vec![MachineOperand::Reg(2)]);
        else_instr.def = Some(10);
        mf.blocks
            .push(make_block("then", vec![then_instr], vec![3]));
        mf.blocks
            .push(make_block("else", vec![else_instr], vec![3]));
        mf.blocks.push(make_block("merge", vec![], vec![]));

        ifc.convert_to_cmov(&mut mf, (0, 1, 2));

        // entry should now have a cmov and go straight to merge
        assert_eq!(mf.blocks[0].successors, vec![3]);
        // then/else should be cleared
        assert!(mf.blocks[1].instructions.is_empty());
        assert!(mf.blocks[2].instructions.is_empty());
    }

    #[test]
    fn test_convert_to_predicated() {
        let mut ifc = IfConversion::new();
        let mut mf = MachineFunction::new("test");
        mf.blocks
            .push(make_block("entry", vec![make_cond_br("then")], vec![1, 2]));
        mf.blocks.push(make_block(
            "then",
            vec![make_instr(2, vec![MachineOperand::Reg(1)])],
            vec![3],
        ));
        mf.blocks.push(make_block(
            "else",
            vec![make_instr(3, vec![MachineOperand::Reg(2)])],
            vec![3],
        ));
        mf.blocks.push(make_block("merge", vec![], vec![]));

        ifc.convert_to_predicated(&mut mf, (0, 1, 2));

        // entry should now contain predicated instructions and go to merge
        assert!(mf.blocks[0].instructions.len() >= 2);
        assert_eq!(mf.blocks[0].successors, vec![3]);
        // then/else should be cleared
        assert!(mf.blocks[1].instructions.is_empty());
        assert!(mf.blocks[2].instructions.is_empty());
    }

    #[test]
    fn test_default() {
        let ifc = IfConversion::default();
        assert_eq!(ifc.predicated, 0);
    }
}