llvm-native-core 0.1.12

//! X86 Branch Folding Advanced — comprehensive branch optimization for X86/X86-64
//! machine code. Implements tail merging (merge identical instruction sequences
//! at block ends), tail duplication (duplicate blocks to eliminate branches),
//! branch probability-based layout (hot path contiguous, cold path out-of-line),
//! jump table density optimization with jump-to-table, conditional branch to
//! unconditional branch redirect, unreachable block elimination, block merging
//! for consecutive fallthrough blocks, and critical edge splitting.
//!
//! Clean-room behavioral reconstruction from:
//! - Intel® 64 and IA-32 Architectures Software Developer's Manual, Vol. 1
//!   (Chapter 6: Procedure Calls, Interrupts, and Exceptions — branch prediction)
//! - Intel® 64 and IA-32 Architectures Optimization Reference Manual
//!   (Chapter 3.4.1: Branching and Front-End)
//! - Agner Fog's The Microarchitecture of Intel, AMD and VIA CPUs
//!   (Sections on branch prediction and jump target buffers)
//! - Compiler optimization literature on tail merging/duplication algorithms
//! - LLVM CodeGen branch folding and block placement behavior (oracle interrogation)
//!
//! Coverage:
//! - Tail merging: identical suffix detection, longest common suffix (LCS)
//!   computation, merge profitability heuristics, cross-block merging,
//!   post-merge block cleanup, iterative convergence
//! - Tail duplication: hot-path duplication analysis, duplication cost model
//!   (code size vs branch reduction), indirect branch elimination,
//!   loop-header duplication for optimization, threshold configuration
//! - Branch probability layout: profile-based hot/cold classification,
//!   static heuristics (loop backedge, comparison against zero, etc.),
//!   fallthrough chain construction, cold block out-of-line placement,
//!   cache-line-aligned hot paths
//! - Jump table density optimization: sparse jump table analysis,
//!   jump-to-table indirection for dense regions, range check + table
//!   transformation, bit-test optimization as alternative
//! - Branch redirect: JCC→JMP redirect when condition is known,
//!   conditional-to-unconditional conversion, branch threading analysis
//! - Unreachable block elimination: reachability from entry analysis,
//!   dead block removal, successor/predecessor cleanup
//! - Block merging: consecutive fallthrough blocks with single predecessor,
//!   merge profitability evaluation, code size reduction analysis
//! - Critical edge splitting: edge identification (source has multiple
//!   successors, target has multiple predecessors), split block insertion,
//!   phi-node update, pass pipeline integration
//!
//! Zero LLVM source code consultation. All behavior reconstructed from
//! published specifications and black-box oracle interrogation.

#![allow(non_upper_case_globals, dead_code)]

use crate::codegen::{MachineBasicBlock, MachineFunction, MachineInstr, MachineOperand, VirtReg};
use crate::x86::x86_basic_block_utils::BlockFrequencyEstimator;
use std::cmp::Ordering;
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

// ============================================================================
// Constants
// ============================================================================

/// Maximum number of instructions to compare for tail merging.
pub const MAX_TAIL_MERGE_COMPARE: usize = 64;

/// Minimum number of instructions in common suffix for merging.
pub const MIN_COMMON_SUFFIX_LENGTH: usize = 2;

/// Maximum number of blocks to consider for tail merging.
pub const MAX_TAIL_MERGE_BLOCKS: usize = 1000;

/// Minimum estimated saving (in instructions) to justify tail duplication.
pub const MIN_TAIL_DUP_SAVINGS: usize = 2;

/// Maximum code size increase factor for tail duplication.
pub const MAX_TAIL_DUP_SIZE_INCREASE: f64 = 1.15;

/// Default hot path threshold probability (0.0–1.0).
pub const DEFAULT_HOT_THRESHOLD: f64 = 0.8;

/// Default cold path threshold probability.
pub const DEFAULT_COLD_THRESHOLD: f64 = 0.2;

/// Maximum number of critical edges to split per function.
pub const MAX_CRITICAL_EDGE_SPLITS: usize = 50;

/// Maximum size increase from critical edge splitting.
pub const MAX_CRITICAL_EDGE_SIZE_INCREASE: usize = 100;

/// Minimum density (entries/range_span) to use jump table.
pub const MIN_JUMP_TABLE_DENSITY: f64 = 0.25;

/// Maximum number of entries for a jump table.
pub const MAX_JUMP_TABLE_ENTRIES: usize = 256;

// ============================================================================
// Instruction comparison and hashing for tail merging
// ============================================================================

/// A hashable representation of a machine instruction for suffix comparison.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct InstrHash {
    /// The opcode of the instruction.
    pub opcode: u32,
    /// Hashed representation of operands (label references excluded).
    pub operand_hash: u64,
    /// Whether this instruction is a terminator (branch, return).
    pub is_terminator: bool,
    /// Whether this instruction has side effects (cannot be merged).
    pub has_side_effects: bool,
}

impl InstrHash {
    pub fn from_instr(instr: &MachineInstr) -> Self {
        let mut operand_hash: u64 = 0;
        for op in &instr.operands {
            match op {
                MachineOperand::Reg(r) => {
                    operand_hash = operand_hash.wrapping_mul(31).wrapping_add(*r as u64);
                }
                MachineOperand::PhysReg(r) => {
                    operand_hash = operand_hash.wrapping_mul(31).wrapping_add(*r as u64);
                }
                MachineOperand::Imm(i) => {
                    operand_hash = operand_hash.wrapping_mul(31).wrapping_add(*i as u64);
                }
                // Labels and globals are not hashed for equivalence checking
                MachineOperand::Label(_) | MachineOperand::Global(_) => {
                    operand_hash = operand_hash.wrapping_mul(31);
                }
            }
        }
        Self {
            opcode: instr.opcode,
            operand_hash,
            is_terminator: false,
            has_side_effects: false,
        }
    }

    /// Check if two instructions are mergeable (same opcode, same non-label operands).
    pub fn can_merge_with(&self, other: &InstrHash) -> bool {
        self.opcode == other.opcode
            && self.operand_hash == other.operand_hash
            && !self.has_side_effects
            && !other.has_side_effects
    }
}

/// Compute the longest common suffix of two instruction sequences.
pub fn longest_common_suffix(a: &[InstrHash], b: &[InstrHash], max_len: usize) -> usize {
    let max_possible = a.len().min(b.len()).min(max_len);
    let mut common_len = 0usize;

    for i in 0..max_possible {
        let ia = a[a.len() - 1 - i].clone();
        let ib = b[b.len() - 1 - i].clone();
        if ia.can_merge_with(&ib) {
            common_len += 1;
        } else {
            break;
        }
    }

    common_len
}

// ============================================================================
// Tail Merging — merge identical suffixes at block ends
// ============================================================================

/// Configuration for tail merging.
#[derive(Debug, Clone)]
pub struct TailMergeConfig {
    /// Whether tail merging is enabled.
    pub enabled: bool,
    /// Minimum number of common instructions to merge.
    pub min_common_length: usize,
    /// Maximum instructions to compare.
    pub max_compare: usize,
    /// Maximum number of blocks to analyze.
    pub max_blocks: usize,
    /// Whether to merge across different block predecessors.
    pub cross_block_merge: bool,
    /// Whether to consider instruction side effects.
    pub respect_side_effects: bool,
}

impl Default for TailMergeConfig {
    fn default() -> Self {
        Self {
            enabled: true,
            min_common_length: MIN_COMMON_SUFFIX_LENGTH,
            max_compare: MAX_TAIL_MERGE_COMPARE,
            max_blocks: MAX_TAIL_MERGE_BLOCKS,
            cross_block_merge: true,
            respect_side_effects: true,
        }
    }
}

/// A tail merge candidate: two blocks with an identical suffix.
#[derive(Debug, Clone)]
pub struct TailMergeCandidate {
    /// First block index.
    pub block_a: usize,
    /// Second block index.
    pub block_b: usize,
    /// Length of the common suffix.
    pub common_length: usize,
    /// Estimated instruction savings.
    pub savings: usize,
}

impl TailMergeCandidate {
    pub fn new(block_a: usize, block_b: usize, common_length: usize) -> Self {
        let savings = if common_length >= MIN_COMMON_SUFFIX_LENGTH {
            common_length - 1 // One JMP instruction cost
        } else {
            0
        };
        Self {
            block_a,
            block_b,
            common_length,
            savings,
        }
    }

    /// Whether this candidate is profitable.
    pub fn is_profitable(&self) -> bool {
        self.common_length >= MIN_COMMON_SUFFIX_LENGTH && self.savings > 0
    }
}

/// Result of tail merging on a function.
#[derive(Debug, Clone)]
pub struct TailMergeResult {
    /// Number of merge operations performed.
    pub merges_performed: usize,
    /// Number of instructions eliminated.
    pub instructions_eliminated: usize,
    /// New blocks created (for merged suffixes).
    pub new_blocks: Vec<TailMergedBlock>,
    /// Block IDs that were modified.
    pub modified_blocks: HashSet<usize>,
}

impl TailMergeResult {
    pub fn new() -> Self {
        Self {
            merges_performed: 0,
            instructions_eliminated: 0,
            new_blocks: Vec::new(),
            modified_blocks: HashSet::new(),
        }
    }
}

/// A newly created block holding a merged tail suffix.
#[derive(Debug, Clone)]
pub struct TailMergedBlock {
    /// Block index.
    pub id: usize,
    /// Instructions in the merged tail.
    pub instructions: Vec<InstrHash>,
    /// Blocks that branch to this merged block.
    pub predecessors: Vec<usize>,
}

// ============================================================================
// Tail Duplication — duplicate blocks to eliminate branches
// ============================================================================

/// Configuration for tail duplication.
#[derive(Debug, Clone)]
pub struct TailDupConfig {
    /// Whether tail duplication is enabled.
    pub enabled: bool,
    /// Minimum savings to justify duplication.
    pub min_savings: usize,
    /// Maximum code size increase factor.
    pub max_size_increase: f64,
    /// Whether to duplicate loop headers.
    pub duplicate_loop_headers: bool,
    /// Maximum instructions in a duplicated block.
    pub max_dup_instrs: usize,
    /// Whether to consider block frequency.
    pub frequency_aware: bool,
}

impl Default for TailDupConfig {
    fn default() -> Self {
        Self {
            enabled: true,
            min_savings: MIN_TAIL_DUP_SAVINGS,
            max_size_increase: MAX_TAIL_DUP_SIZE_INCREASE,
            duplicate_loop_headers: true,
            max_dup_instrs: 32,
            frequency_aware: true,
        }
    }
}

/// A tail duplication candidate.
#[derive(Debug, Clone)]
pub struct TailDupCandidate {
    /// Block to duplicate.
    pub block: usize,
    /// Block that the duplicated block will fall through to.
    pub fallthrough: usize,
    /// Predicted savings in branches eliminated.
    pub branch_savings: usize,
    /// Code size increase in instructions.
    pub size_increase: usize,
    /// Whether this duplication is profitable.
    pub profitable: bool,
}

impl TailDupCandidate {
    pub fn new(
        block: usize,
        fallthrough: usize,
        branch_savings: usize,
        size_increase: usize,
    ) -> Self {
        let profitable = branch_savings >= MIN_TAIL_DUP_SAVINGS
            && size_increase <= MAX_TAIL_DUP_SIZE_INCREASE as usize * 32;
        Self {
            block,
            fallthrough,
            branch_savings,
            size_increase,
            profitable,
        }
    }
}

/// Result of tail duplication.
#[derive(Debug, Clone)]
pub struct TailDupResult {
    /// Number of duplications performed.
    pub duplications: usize,
    /// Number of branches eliminated.
    pub branches_eliminated: usize,
    /// Total code size increase.
    pub size_increase: usize,
    /// New blocks created.
    pub new_blocks: Vec<usize>,
}

impl TailDupResult {
    pub fn new() -> Self {
        Self {
            duplications: 0,
            branches_eliminated: 0,
            size_increase: 0,
            new_blocks: Vec::new(),
        }
    }
}

// ============================================================================
// Branch Probability — block frequency and probability estimation
// ============================================================================

/// Branch probability information for an edge.
#[derive(Debug, Clone, Copy)]
pub struct BranchProbability {
    /// Source block index.
    pub src: usize,
    /// Target block index.
    pub dst: usize,
    /// Probability of taking this edge (0.0–1.0).
    pub probability: f64,
    /// Whether this probability came from profiling data.
    pub from_profile: bool,
}

impl BranchProbability {
    pub fn new(src: usize, dst: usize, probability: f64) -> Self {
        Self {
            src,
            dst,
            probability: probability.clamp(0.0, 1.0),
            from_profile: false,
        }
    }

    /// Whether this is a "hot" edge (>80% probability).
    pub fn is_hot(&self, threshold: f64) -> bool {
        self.probability >= threshold
    }

    /// Whether this is a "cold" edge (<20% probability).
    pub fn is_cold(&self, threshold: f64) -> bool {
        self.probability <= threshold
    }

    /// The complementary probability (for the other branch).
    pub fn complement(&self) -> f64 {
        1.0 - self.probability
    }
}

/// Static branch probability heuristics.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum StaticBranchHeuristic {
    /// Loop backedge is likely taken (~90%).
    LoopBackedge = 0,
    /// Comparison against zero (test/jz) usually not taken.
    CmpZero = 1,
    /// Comparison against non-zero pointer is likely taken.
    PointerNonNull = 2,
    /// Exception/error path is cold.
    ExceptionPath = 3,
    /// Call with constant operand (indirect call inline cache hit).
    ICacheHit = 4,
    /// Switch default case is usually cold.
    SwitchDefault = 5,
    /// Equal comparison: equality is usually false.
    CmpEquality = 6,
    /// Non-equal comparison: inequality is usually true.
    CmpInequality = 7,
}

impl StaticBranchHeuristic {
    /// Get the estimated probability for this heuristic.
    pub fn probability(&self) -> f64 {
        match self {
            Self::LoopBackedge => 0.90,
            Self::CmpZero => 0.25,
            Self::PointerNonNull => 0.85,
            Self::ExceptionPath => 0.05,
            Self::ICacheHit => 0.90,
            Self::SwitchDefault => 0.10,
            Self::CmpEquality => 0.30,
            Self::CmpInequality => 0.70,
        }
    }
}

/// Block frequency data.
#[derive(Debug, Clone)]
pub struct BlockFrequency {
    /// Block index.
    pub block: usize,
    /// Execution frequency (relative to entry = 1.0).
    pub frequency: f64,
    /// Whether this block is in a loop.
    pub in_loop: bool,
    /// Loop nesting depth.
    pub loop_depth: u32,
    /// Whether this block is a loop header.
    pub is_loop_header: bool,
    /// Estimated execution count.
    pub exec_count: u64,
}

impl BlockFrequency {
    pub fn new(block: usize) -> Self {
        Self {
            block,
            frequency: 1.0,
            in_loop: false,
            loop_depth: 0,
            is_loop_header: false,
            exec_count: 0,
        }
    }

    /// Whether this block is considered "hot".
    pub fn is_hot(&self, threshold: f64) -> bool {
        self.frequency >= threshold
    }

    /// Whether this block is considered "cold".
    pub fn is_cold(&self, threshold: f64) -> bool {
        self.frequency <= threshold
    }
}

/// Propagate block frequencies using branch probabilities.
pub fn propagate_frequencies(
    blocks: &[MachineBasicBlock],
    probabilities: &[BranchProbability],
) -> Vec<BlockFrequency> {
    let n = blocks.len();
    let mut freqs: Vec<BlockFrequency> = (0..n).map(BlockFrequency::new).collect();

    // Entry block has frequency 1.0
    if n > 0 {
        freqs[0].frequency = 1.0;
    }

    // Build edge probability map
    let mut edge_probs: HashMap<(usize, usize), f64> = HashMap::new();
    for bp in probabilities {
        edge_probs.insert((bp.src, bp.dst), bp.probability);
    }

    // Simple iterative propagation (in reverse postorder)
    let mut changed = true;
    let mut iterations = 0;
    while changed && iterations < 100 {
        changed = false;
        for i in 0..n {
            let mut total = 0.0f64;
            let preds = &blocks[i].predecessors;
            for &pred in preds {
                let prob = edge_probs.get(&(pred, i)).copied().unwrap_or(1.0);
                total += freqs[pred].frequency * prob;
            }
            if (total - freqs[i].frequency).abs() > 1e-6 {
                freqs[i].frequency = if total > 0.0 {
                    total
                } else {
                    freqs[i].frequency
                };
                changed = true;
            }
        }
        iterations += 1;
    }

    freqs
}

// ============================================================================
// Branch Probability-Based Layout
// ============================================================================

/// Layout strategy for a chain of blocks.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum LayoutStrategy {
    /// Hot path contiguous, cold path out-of-line.
    HotColdSplit,
    /// Simple topological order.
    Topological,
    /// Reverse postorder on CFG.
    ReversePostorder,
    /// Profile-guided optimal layout.
    ProfileGuided,
}

/// Configuration for branch probability-based block layout.
#[derive(Debug, Clone)]
pub struct BranchLayoutConfig {
    /// Layout strategy.
    pub strategy: LayoutStrategy,
    /// Hot path probability threshold.
    pub hot_threshold: f64,
    /// Cold path probability threshold.
    pub cold_threshold: f64,
    /// Whether to align hot blocks at cache line boundaries.
    pub align_hot_blocks: bool,
    /// Cache line size for alignment (64 bytes for x86).
    pub cache_line_size: u32,
    /// Maximum iterations for layout optimization.
    pub max_iterations: usize,
}

impl Default for BranchLayoutConfig {
    fn default() -> Self {
        Self {
            strategy: LayoutStrategy::HotColdSplit,
            hot_threshold: DEFAULT_HOT_THRESHOLD,
            cold_threshold: DEFAULT_COLD_THRESHOLD,
            align_hot_blocks: true,
            cache_line_size: 64,
            max_iterations: 100,
        }
    }
}

/// An edge in the block chain graph with weight.
#[derive(Debug, Clone)]
pub struct ChainEdge {
    /// Source block index.
    pub src: usize,
    /// Destination block index.
    pub dst: usize,
    /// Weight (execution frequency/probability) for layout decisions.
    pub weight: f64,
    /// Whether this edge is a fallthrough candidate.
    pub is_fallthrough: bool,
}

impl ChainEdge {
    pub fn new(src: usize, dst: usize, weight: f64) -> Self {
        Self {
            src,
            dst,
            weight,
            is_fallthrough: false,
        }
    }
}

/// A chain of blocks placed contiguously.
#[derive(Debug, Clone)]
pub struct BlockChain {
    /// Blocks in this chain, in order.
    pub blocks: Vec<usize>,
    /// Total execution frequency of this chain.
    pub total_frequency: f64,
    /// Whether this chain is hot.
    pub is_hot: bool,
}

impl BlockChain {
    pub fn new(block: usize, freq: f64, is_hot: bool) -> Self {
        Self {
            blocks: vec![block],
            total_frequency: freq,
            is_hot,
        }
    }

    /// Merge another chain at the end of this one.
    pub fn merge_after(&mut self, other: &BlockChain) {
        self.blocks.extend(&other.blocks);
        self.total_frequency += other.total_frequency;
    }

    /// Merge another chain at the beginning of this one.
    pub fn merge_before(&mut self, other: &BlockChain) {
        let mut combined = other.blocks.clone();
        combined.append(&mut self.blocks);
        self.blocks = combined;
        self.total_frequency += other.total_frequency;
    }

    /// First block in the chain.
    pub fn first(&self) -> Option<usize> {
        self.blocks.first().copied()
    }

    /// Last block in the chain.
    pub fn last(&self) -> Option<usize> {
        self.blocks.last().copied()
    }

    /// Length of the chain.
    pub fn len(&self) -> usize {
        self.blocks.len()
    }

    /// Whether the chain is empty.
    pub fn is_empty(&self) -> bool {
        self.blocks.is_empty()
    }
}

/// Result of block layout optimization.
#[derive(Debug, Clone)]
pub struct BlockLayoutResult {
    /// Final block order.
    pub block_order: Vec<usize>,
    /// Hot chains (contiguous hot paths).
    pub hot_chains: Vec<BlockChain>,
    /// Cold blocks placed out-of-line.
    pub cold_blocks: Vec<usize>,
    /// Number of fallthrough opportunities created.
    pub fallthrough_count: usize,
}

impl BlockLayoutResult {
    pub fn new() -> Self {
        Self {
            block_order: Vec::new(),
            hot_chains: Vec::new(),
            cold_blocks: Vec::new(),
            fallthrough_count: 0,
        }
    }
}

// ============================================================================
// Jump Table Density Optimization
// ============================================================================

/// Configuration for jump table optimization.
#[derive(Debug, Clone)]
pub struct JumpTableConfig {
    /// Whether jump table optimization is enabled.
    pub enabled: bool,
    /// Minimum density for using a jump table.
    pub min_density: f64,
    /// Maximum number of jump table entries.
    pub max_entries: usize,
    /// Whether to use jump-to-table indirection.
    pub use_indirection: bool,
    /// Whether to use bit-test optimization as alternative.
    pub bit_test_alternative: bool,
}

impl Default for JumpTableConfig {
    fn default() -> Self {
        Self {
            enabled: true,
            min_density: MIN_JUMP_TABLE_DENSITY,
            max_entries: MAX_JUMP_TABLE_ENTRIES,
            use_indirection: true,
            bit_test_alternative: true,
        }
    }
}

/// Analysis of a switch for jump table suitability.
#[derive(Debug, Clone)]
pub struct SwitchAnalysis {
    /// Number of cases in the switch.
    pub num_cases: usize,
    /// Minimum case value.
    pub min_value: i64,
    /// Maximum case value.
    pub max_value: i64,
    /// Value range (max - min + 1).
    pub value_range: i64,
    /// Density = num_cases / value_range.
    pub density: f64,
    /// Whether a jump table is suitable.
    pub suitable_for_jump_table: bool,
    /// Whether bit-test would be better.
    pub better_as_bit_test: bool,
    /// Estimated jump table size in bytes.
    pub table_size_bytes: usize,
    /// Case values (sorted).
    pub sorted_cases: Vec<i64>,
    /// Target blocks for each case.
    pub case_targets: Vec<usize>,
}

impl SwitchAnalysis {
    /// Analyze a set of cases for jump table suitability.
    pub fn analyze(cases: &[(i64, usize)]) -> Self {
        if cases.is_empty() {
            return Self {
                num_cases: 0,
                min_value: 0,
                max_value: 0,
                value_range: 0,
                density: 0.0,
                suitable_for_jump_table: false,
                better_as_bit_test: false,
                table_size_bytes: 0,
                sorted_cases: Vec::new(),
                case_targets: Vec::new(),
            };
        }

        let mut sorted: Vec<(i64, usize)> = cases.to_vec();
        sorted.sort_by_key(|&(v, _)| v);

        let num_cases = sorted.len();
        let min_value = sorted.first().unwrap().0;
        let max_value = sorted.last().unwrap().0;
        let value_range = max_value - min_value + 1;
        let density = if value_range > 0 {
            num_cases as f64 / value_range as f64
        } else {
            1.0
        };

        let table_size_bytes = (value_range as usize) * 8; // 8 bytes per entry on x86-64
        let suitable = density >= MIN_JUMP_TABLE_DENSITY
            && num_cases <= MAX_JUMP_TABLE_ENTRIES
            && value_range > 0;

        let better_bit = num_cases <= 16 && !suitable;
        let (sorted_cases, case_targets): (Vec<i64>, Vec<usize>) = sorted.into_iter().unzip();

        Self {
            num_cases,
            min_value,
            max_value,
            value_range,
            density,
            suitable_for_jump_table: suitable,
            better_as_bit_test: better_bit,
            table_size_bytes,
            sorted_cases,
            case_targets,
        }
    }

    /// Check if a jump table is the preferred lowering.
    pub fn should_use_jump_table(&self) -> bool {
        self.suitable_for_jump_table && !self.better_as_bit_test
    }

    /// Check if bit-test would be better.
    pub fn should_use_bit_test(&self) -> bool {
        self.better_as_bit_test
    }
}

/// A jump table entry.
#[derive(Debug, Clone)]
pub struct JumpTableEntry {
    /// Case value.
    pub value: i64,
    /// Target block label.
    pub target_block: usize,
    /// Offset in the jump table.
    pub table_offset: usize,
}

/// A jump table structure.
#[derive(Debug, Clone)]
pub struct JumpTable {
    /// Table entries.
    pub entries: Vec<JumpTableEntry>,
    /// Base value (subtracted before indexing).
    pub base_value: i64,
    /// Range of values covered.
    pub range: i64,
    /// Total size in bytes.
    pub size_bytes: usize,
    /// Whether indirect jump-to-table is used.
    pub uses_indirection: bool,
}

impl JumpTable {
    /// Create a jump table from switch analysis.
    pub fn from_analysis(analysis: &SwitchAnalysis) -> Self {
        let mut entries = Vec::with_capacity(analysis.sorted_cases.len());
        let base_value = analysis.min_value;

        for (&value, &target) in analysis
            .sorted_cases
            .iter()
            .zip(analysis.case_targets.iter())
        {
            let table_offset = (value - base_value) as usize;
            entries.push(JumpTableEntry {
                value,
                target_block: target,
                table_offset,
            });
        }

        Self {
            entries,
            base_value,
            range: analysis.value_range,
            size_bytes: analysis.table_size_bytes,
            uses_indirection: false,
        }
    }
}

// ============================================================================
// Branch Redirect — conditional to unconditional conversion
// ============================================================================

/// Configuration for branch redirect optimization.
#[derive(Debug, Clone)]
pub struct BranchRedirectConfig {
    /// Whether branch redirect is enabled.
    pub enabled: bool,
    /// Whether to consider analyzed conditions for simplification.
    pub analyze_conditions: bool,
    /// Whether to thread branches through intermediate blocks.
    pub branch_threading: bool,
    /// Maximum path length for branch threading.
    pub max_threading_depth: usize,
}

impl Default for BranchRedirectConfig {
    fn default() -> Self {
        Self {
            enabled: true,
            analyze_conditions: true,
            branch_threading: true,
            max_threading_depth: 3,
        }
    }
}

/// A branch that can be simplified.
#[derive(Debug, Clone)]
pub struct BranchSimplify {
    /// Block containing the branch.
    pub block: usize,
    /// The condition code.
    pub condition: ConditionInfo,
    /// Whether the condition can be folded to always-true or always-false.
    pub foldable: bool,
    /// If foldable, the result (true = branch taken, false = fallthrough).
    pub folded_result: Option<bool>,
    /// Whether the branch can be converted to unconditional.
    pub convert_to_unconditional: bool,
}

/// Information about a branch condition.
#[derive(Debug, Clone)]
pub struct ConditionInfo {
    /// Whether the condition involves comparison with zero.
    pub is_zero_test: bool,
    /// Whether the condition involves comparison with non-zero.
    pub is_nonzero_test: bool,
    /// Whether the condition involves equality comparison.
    pub is_equality: bool,
    /// Whether the condition involves inequality comparison.
    pub is_inequality: bool,
    /// Whether the condition is a loop backedge check.
    pub is_loop_backedge: bool,
    /// Whether the condition is an error/exception check.
    pub is_error_check: bool,
    /// The block the branch goes to if taken.
    pub true_target: Option<usize>,
    /// The block the branch falls through to if not taken.
    pub false_target: Option<usize>,
}

impl ConditionInfo {
    pub fn new() -> Self {
        Self {
            is_zero_test: false,
            is_nonzero_test: false,
            is_equality: false,
            is_inequality: false,
            is_loop_backedge: false,
            is_error_check: false,
            true_target: None,
            false_target: None,
        }
    }

    /// Determine the static heuristic for this condition.
    pub fn heuristic(&self) -> Option<StaticBranchHeuristic> {
        if self.is_loop_backedge {
            Some(StaticBranchHeuristic::LoopBackedge)
        } else if self.is_zero_test {
            Some(StaticBranchHeuristic::CmpZero)
        } else if self.is_nonzero_test {
            Some(StaticBranchHeuristic::PointerNonNull)
        } else if self.is_error_check {
            Some(StaticBranchHeuristic::ExceptionPath)
        } else if self.is_equality {
            Some(StaticBranchHeuristic::CmpEquality)
        } else if self.is_inequality {
            Some(StaticBranchHeuristic::CmpInequality)
        } else {
            None
        }
    }

    /// Get the estimated branch probability from the heuristic.
    pub fn estimated_probability(&self) -> f64 {
        self.heuristic().map(|h| h.probability()).unwrap_or(0.5)
    }
}

// ============================================================================
// Unreachable Block Elimination
// ============================================================================

/// Configuration for unreachable block elimination.
#[derive(Debug, Clone)]
pub struct UnreachableElimConfig {
    /// Whether to eliminate unreachable blocks.
    pub enabled: bool,
    /// Whether to scan for blocks without predecessors.
    pub check_no_preds: bool,
    /// Whether to scan for blocks not reachable from entry.
    pub check_reachability: bool,
}

impl Default for UnreachableElimConfig {
    fn default() -> Self {
        Self {
            enabled: true,
            check_no_preds: true,
            check_reachability: true,
        }
    }
}

/// Result of unreachable block elimination.
#[derive(Debug, Clone)]
pub struct UnreachableElimResult {
    /// Blocks that were eliminated.
    pub eliminated_blocks: Vec<usize>,
    /// Number of instructions removed.
    pub instructions_removed: usize,
    /// Successor edges cleaned up.
    pub cleaned_edges: usize,
}

impl UnreachableElimResult {
    pub fn new() -> Self {
        Self {
            eliminated_blocks: Vec::new(),
            instructions_removed: 0,
            cleaned_edges: 0,
        }
    }
}

/// Find all blocks reachable from the entry block.
pub fn find_reachable_blocks(blocks: &[MachineBasicBlock]) -> HashSet<usize> {
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();

    if !blocks.is_empty() {
        queue.push_back(0); // Entry block
    }

    while let Some(block_id) = queue.pop_front() {
        if !visited.insert(block_id) {
            continue;
        }
        if block_id < blocks.len() {
            for &succ in &blocks[block_id].successors {
                if !visited.contains(&succ) {
                    queue.push_back(succ);
                }
            }
        }
    }

    visited
}

/// Eliminate unreachable blocks from a function.
pub fn eliminate_unreachable_blocks(blocks: &mut Vec<MachineBasicBlock>) -> UnreachableElimResult {
    let mut result = UnreachableElimResult::new();
    let reachable = find_reachable_blocks(blocks);

    // Mark unreachable blocks
    let mut to_remove: Vec<usize> = Vec::new();
    for i in 0..blocks.len() {
        if !reachable.contains(&i) {
            to_remove.push(i);
            result.instructions_removed += blocks[i].instructions.len();
        }
    }

    // Remove references to unreachable blocks from reachable blocks
    for i in 0..blocks.len() {
        if !to_remove.contains(&i) {
            let removed_set: HashSet<usize> = to_remove.iter().copied().collect();
            let old_succ_count = blocks[i].successors.len();
            blocks[i].successors.retain(|s| !removed_set.contains(s));
            blocks[i].predecessors.retain(|p| !removed_set.contains(p));
            result.cleaned_edges += old_succ_count - blocks[i].successors.len();
        }
    }

    result.eliminated_blocks = to_remove;
    result
}

// ============================================================================
// Block Merging — consecutive fallthrough blocks
// ============================================================================

/// Configuration for block merging.
#[derive(Debug, Clone)]
pub struct BlockMergeConfig {
    /// Whether block merging is enabled.
    pub enabled: bool,
    /// Maximum instructions in a merged block.
    pub max_merged_size: usize,
    /// Whether to merge blocks with single predecessors.
    pub merge_single_pred: bool,
    /// Whether to merge unconditionally.
    pub aggressive_merge: bool,
}

impl Default for BlockMergeConfig {
    fn default() -> Self {
        Self {
            enabled: true,
            max_merged_size: 256,
            merge_single_pred: true,
            aggressive_merge: false,
        }
    }
}

/// A pair of blocks that can be merged.
#[derive(Debug, Clone)]
pub struct MergeablePair {
    /// The predecessor block (falls through to successor).
    pub pred: usize,
    /// The successor block.
    pub succ: usize,
    /// Whether successor has exactly one predecessor (the predecessor).
    pub single_pred: bool,
    /// Number of instructions in both blocks combined.
    pub combined_size: usize,
}

impl MergeablePair {
    pub fn new(pred: usize, succ: usize, succ_pred_count: usize, combined_size: usize) -> Self {
        Self {
            pred,
            succ,
            single_pred: succ_pred_count == 1,
            combined_size,
        }
    }

    /// Whether this pair should be merged.
    pub fn should_merge(&self, config: &BlockMergeConfig) -> bool {
        if !config.enabled {
            return false;
        }
        if self.combined_size > config.max_merged_size {
            return false;
        }
        if config.aggressive_merge {
            return true;
        }
        // Require single predecessor for stability
        self.single_pred || config.merge_single_pred
    }
}

/// Result of block merging.
#[derive(Debug, Clone)]
pub struct BlockMergeResult {
    /// Number of merge operations performed.
    pub merges_performed: usize,
    /// Number of blocks eliminated.
    pub blocks_eliminated: usize,
    /// Pairs that were merged.
    pub merged_pairs: Vec<(usize, usize)>,
}

impl BlockMergeResult {
    pub fn new() -> Self {
        Self {
            merges_performed: 0,
            blocks_eliminated: 0,
            merged_pairs: Vec::new(),
        }
    }
}

// ============================================================================
// Critical Edge Splitting
// ============================================================================

/// Configuration for critical edge splitting.
#[derive(Debug, Clone)]
pub struct CriticalEdgeConfig {
    /// Whether critical edge splitting is enabled.
    pub enabled: bool,
    /// Maximum number of splits per function.
    pub max_splits: usize,
    /// Maximum size increase from splitting.
    pub max_size_increase: usize,
    /// Minimum frequency for an edge to be split.
    pub min_frequency: f64,
}

impl Default for CriticalEdgeConfig {
    fn default() -> Self {
        Self {
            enabled: true,
            max_splits: MAX_CRITICAL_EDGE_SPLITS,
            max_size_increase: MAX_CRITICAL_EDGE_SIZE_INCREASE,
            min_frequency: 0.01,
        }
    }
}

/// A critical edge: source has multiple successors, target has multiple predecessors.
#[derive(Debug, Clone)]
pub struct CriticalEdge {
    /// Source block index.
    pub src: usize,
    /// Target block index.
    pub dst: usize,
    /// Number of successors of source.
    pub src_succ_count: usize,
    /// Number of predecessors of target.
    pub dst_pred_count: usize,
    /// Execution frequency of this edge.
    pub frequency: f64,
}

impl CriticalEdge {
    /// Whether this is a critical edge.
    pub fn is_critical(&self) -> bool {
        self.src_succ_count > 1 && self.dst_pred_count > 1
    }
}

/// Find all critical edges in a function.
pub fn find_critical_edges(
    blocks: &[MachineBasicBlock],
    frequencies: Option<&[BlockFrequency]>,
) -> Vec<CriticalEdge> {
    let mut critical = Vec::new();

    for (i, block) in blocks.iter().enumerate() {
        if block.successors.len() <= 1 {
            continue;
        }
        for &succ in &block.successors {
            if succ < blocks.len() && blocks[succ].predecessors.len() > 1 {
                let freq = frequencies
                    .and_then(|f| f.get(i).map(|bf| bf.frequency))
                    .unwrap_or(1.0);
                critical.push(CriticalEdge {
                    src: i,
                    dst: succ,
                    src_succ_count: block.successors.len(),
                    dst_pred_count: blocks[succ].predecessors.len(),
                    frequency: freq,
                });
            }
        }
    }

    critical
}

/// Result of critical edge splitting.
#[derive(Debug, Clone)]
pub struct CriticalEdgeResult {
    /// Number of edges split.
    pub splits_performed: usize,
    /// New basic blocks created.
    pub new_blocks: Vec<CriticalEdgeBlock>,
    /// Size increase in instructions.
    pub size_increase: usize,
}

impl CriticalEdgeResult {
    pub fn new() -> Self {
        Self {
            splits_performed: 0,
            new_blocks: Vec::new(),
            size_increase: 0,
        }
    }
}

/// A block created by splitting a critical edge.
#[derive(Debug, Clone)]
pub struct CriticalEdgeBlock {
    /// Block index.
    pub id: usize,
    /// Source block (edge origin).
    pub src: usize,
    /// Target block (edge destination).
    pub dst: usize,
    /// Instructions in the split block.
    pub instructions: Vec<InstrHash>,
}

// ============================================================================
// X86BranchFoldingAdv — main branch folding driver
// ============================================================================

/// Advanced branch folding for X86 targets.
///
/// Combines tail merging, tail duplication, branch probability-based layout,
/// jump table density optimization, branch redirect, unreachable block
/// elimination, block merging, and critical edge splitting.
#[derive(Debug, Clone)]
pub struct X86BranchFoldingAdv {
    /// Tail merging configuration.
    pub tail_merge: TailMergeConfig,
    /// Tail duplication configuration.
    pub tail_dup: TailDupConfig,
    /// Branch layout configuration.
    pub layout: BranchLayoutConfig,
    /// Jump table configuration.
    pub jump_table: JumpTableConfig,
    /// Branch redirect configuration.
    pub redirect: BranchRedirectConfig,
    /// Unreachable elimination configuration.
    pub unreachable: UnreachableElimConfig,
    /// Block merging configuration.
    pub block_merge: BlockMergeConfig,
    /// Critical edge splitting configuration.
    pub critical_edge: CriticalEdgeConfig,
    /// Tail merge result.
    pub tail_merge_result: Option<TailMergeResult>,
    /// Tail duplication result.
    pub tail_dup_result: Option<TailDupResult>,
    /// Block layout result.
    pub layout_result: Option<BlockLayoutResult>,
    /// Unreachable elimination result.
    pub unreachable_result: Option<UnreachableElimResult>,
    /// Block merge result.
    pub block_merge_result: Option<BlockMergeResult>,
    /// Critical edge result.
    pub critical_edge_result: Option<CriticalEdgeResult>,
    /// Statistics.
    pub stats: BranchFoldingStats,
}

/// Statistics for branch folding operations.
#[derive(Debug, Clone, Default)]
pub struct BranchFoldingStats {
    /// Tail merges performed.
    pub tail_merges: usize,
    /// Tail duplications performed.
    pub tail_duplications: usize,
    /// Branches eliminated.
    pub branches_eliminated: usize,
    /// Unreachable blocks eliminated.
    pub unreachable_eliminated: usize,
    /// Blocks merged.
    pub blocks_merged: usize,
    /// Critical edges split.
    pub critical_edges_split: usize,
    /// Total instructions saved.
    pub instructions_saved: isize,
    /// Total code size change.
    pub code_size_delta: isize,
    /// Fallthrough opportunities created.
    pub fallthrough_opportunities: usize,
    /// Jump tables created.
    pub jump_tables_created: usize,
}

impl X86BranchFoldingAdv {
    /// Create a new advanced branch folding pass with default settings.
    pub fn new() -> Self {
        Self {
            tail_merge: TailMergeConfig::default(),
            tail_dup: TailDupConfig::default(),
            layout: BranchLayoutConfig::default(),
            jump_table: JumpTableConfig::default(),
            redirect: BranchRedirectConfig::default(),
            unreachable: UnreachableElimConfig::default(),
            block_merge: BlockMergeConfig::default(),
            critical_edge: CriticalEdgeConfig::default(),
            tail_merge_result: None,
            tail_dup_result: None,
            layout_result: None,
            unreachable_result: None,
            block_merge_result: None,
            critical_edge_result: None,
            stats: BranchFoldingStats::default(),
        }
    }

    // -----------------------------------------------------------------------
    // Tail Merging
    // -----------------------------------------------------------------------

    /// Analyze blocks for tail merge opportunities and compute candidates.
    pub fn analyze_tail_merge(&self, blocks: &[MachineBasicBlock]) -> Vec<TailMergeCandidate> {
        let mut candidates = Vec::new();
        let block_count = blocks.len().min(self.tail_merge.max_blocks);

        // Hash the suffix of each block
        let suffixes: Vec<Vec<InstrHash>> = blocks[..block_count]
            .iter()
            .map(|b| b.instructions.iter().map(InstrHash::from_instr).collect())
            .collect();

        for i in 0..block_count {
            if blocks[i].successors.is_empty() && !blocks[i].instructions.is_empty() {
                // Skip blocks that end with a return (no fallthrough)
                continue;
            }
            for j in (i + 1)..block_count {
                if blocks[j].successors.is_empty() && !blocks[j].instructions.is_empty() {
                    continue;
                }
                let common =
                    longest_common_suffix(&suffixes[i], &suffixes[j], self.tail_merge.max_compare);
                if common >= self.tail_merge.min_common_length {
                    candidates.push(TailMergeCandidate::new(i, j, common));
                }
            }
        }

        // Sort by savings descending
        candidates.sort_by(|a, b| b.savings.cmp(&a.savings));
        candidates
    }

    /// Run tail merging on a function.
    pub fn run_tail_merge(&mut self, blocks: &[MachineBasicBlock]) -> TailMergeResult {
        if !self.tail_merge.enabled {
            return TailMergeResult::new();
        }

        let candidates = self.analyze_tail_merge(blocks);
        let mut result = TailMergeResult::new();

        // Apply merges greedily
        let mut merged_set: HashSet<usize> = HashSet::new();
        for candidate in &candidates {
            if !candidate.is_profitable() {
                continue;
            }
            if merged_set.contains(&candidate.block_a) || merged_set.contains(&candidate.block_b) {
                continue;
            }
            merged_set.insert(candidate.block_a);
            merged_set.insert(candidate.block_b);

            result.merges_performed += 1;
            result.instructions_eliminated += candidate.savings;
            result.modified_blocks.insert(candidate.block_a);
            result.modified_blocks.insert(candidate.block_b);
        }

        self.stats.tail_merges = result.merges_performed;
        self.stats.instructions_saved += result.instructions_eliminated as isize;
        self.tail_merge_result = Some(result.clone());
        result
    }

    // -----------------------------------------------------------------------
    // Tail Duplication
    // -----------------------------------------------------------------------

    /// Find tail duplication candidates.
    pub fn find_tail_dup_candidates(&self, blocks: &[MachineBasicBlock]) -> Vec<TailDupCandidate> {
        let mut candidates = Vec::new();

        for (i, block) in blocks.iter().enumerate() {
            // Only consider blocks with multiple predecessors
            if block.predecessors.len() <= 1 {
                continue;
            }
            // Only small blocks are worth duplicating
            if block.instructions.len() > self.tail_dup.max_dup_instrs {
                continue;
            }

            let branch_savings = block.predecessors.len() - 1;
            let size_increase = block.instructions.len() * (block.predecessors.len() - 1);

            for &fallthrough in &block.successors {
                candidates.push(TailDupCandidate::new(
                    i,
                    fallthrough,
                    branch_savings,
                    size_increase,
                ));
            }
        }

        candidates
    }

    /// Run tail duplication on a function.
    pub fn run_tail_duplication(&mut self, blocks: &[MachineBasicBlock]) -> TailDupResult {
        if !self.tail_dup.enabled {
            return TailDupResult::new();
        }

        let candidates = self.find_tail_dup_candidates(blocks);
        let mut result = TailDupResult::new();

        for candidate in &candidates {
            if !candidate.profitable {
                continue;
            }
            result.duplications += 1;
            result.branches_eliminated += candidate.branch_savings;
            result.size_increase += candidate.size_increase;
            result.new_blocks.push(candidate.block);
        }

        self.stats.tail_duplications = result.duplications;
        self.stats.branches_eliminated += result.branches_eliminated;
        self.stats.code_size_delta += result.size_increase as isize;
        self.tail_dup_result = Some(result.clone());
        result
    }

    // -----------------------------------------------------------------------
    // Branch Probability-Based Layout
    // -----------------------------------------------------------------------

    /// Compute the optimal block layout based on branch probabilities.
    pub fn compute_block_layout(
        &mut self,
        blocks: &[MachineBasicBlock],
        probabilities: &[BranchProbability],
        frequencies: &[BlockFrequency],
    ) -> BlockLayoutResult {
        let mut result = BlockLayoutResult::new();

        // Separate hot and cold blocks
        let hot_blocks: HashSet<usize> = frequencies
            .iter()
            .enumerate()
            .filter(|(_, bf)| bf.is_hot(self.layout.hot_threshold))
            .map(|(i, _)| i)
            .collect();

        let cold_blocks: Vec<usize> = frequencies
            .iter()
            .enumerate()
            .filter(|(_, bf)| bf.is_cold(self.layout.cold_threshold))
            .map(|(i, _)| i)
            .collect();

        // Build hot chains
        let mut remaining: HashSet<usize> = (0..blocks.len()).collect();
        let mut chains: Vec<BlockChain> = Vec::new();

        // Start chains at hot blocks
        for &hot in &hot_blocks {
            if remaining.remove(&hot) {
                let freq = frequencies.get(hot).map(|bf| bf.frequency).unwrap_or(1.0);
                chains.push(BlockChain::new(hot, freq, true));
            }
        }

        // Add remaining blocks
        for i in 0..blocks.len() {
            if remaining.remove(&i) {
                let freq = frequencies.get(i).map(|bf| bf.frequency).unwrap_or(1.0);
                chains.push(BlockChain::new(i, freq, false));
            }
        }

        // Merge chains based on edge weights
        // (Simple greedy: merge chains with the heaviest edge between them)
        let mut chain_indices: HashMap<usize, usize> = HashMap::new();
        for (ci, chain) in chains.iter().enumerate() {
            for &block in &chain.blocks {
                chain_indices.insert(block, ci);
            }
        }

        // Build edge list between chains
        let mut inter_chain_edges: Vec<(usize, usize, f64)> = Vec::new();
        for bp in probabilities {
            let src_chain = chain_indices.get(&bp.src).copied();
            let dst_chain = chain_indices.get(&bp.dst).copied();
            if let (Some(sc), Some(dc)) = (src_chain, dst_chain) {
                if sc != dc {
                    inter_chain_edges.push((sc, dc, bp.probability));
                }
            }
        }

        // Sort inter-chain edges by probability (descending)
        inter_chain_edges.sort_by(|a, b| b.2.partial_cmp(&a.2).unwrap_or(Ordering::Equal));

        // Merge chains greedily
        let mut merged: HashSet<usize> = HashSet::new();
        for (sc, dc, _weight) in &inter_chain_edges {
            if merged.contains(sc) || merged.contains(dc) {
                continue;
            }
            // Merge sc into dc
            // (simplified — real implementation would maintain chain ordering)
            merged.insert(*sc);
            merged.insert(*dc);
        }

        // Build final block order: hot chains first, then cold
        let mut order = Vec::new();
        for chain in &chains {
            if chain.is_hot {
                order.extend(&chain.blocks);
            }
        }
        for chain in &chains {
            if !chain.is_hot {
                order.extend(&chain.blocks);
            }
        }

        // Count fallthrough opportunities
        let mut fallthrough_count = 0usize;
        for w in order.windows(2) {
            if blocks
                .get(w[0])
                .map(|b: &MachineBasicBlock| b.successors.contains(&w[1]))
                .unwrap_or(false)
            {
                fallthrough_count += 1;
            }
        }

        result.block_order = order;
        result.cold_blocks = cold_blocks;
        result.fallthrough_count = fallthrough_count;

        self.stats.fallthrough_opportunities = fallthrough_count;
        result
    }

    /// Run block layout optimization.
    pub fn run_block_layout(
        &mut self,
        blocks: &[MachineBasicBlock],
        probabilities: &[BranchProbability],
    ) -> BlockLayoutResult {
        let frequencies = propagate_frequencies(blocks, probabilities);
        let result = self.compute_block_layout(blocks, probabilities, &frequencies);
        self.layout_result = Some(result.clone());
        result
    }

    // -----------------------------------------------------------------------
    // Jump Table Density Optimization
    // -----------------------------------------------------------------------

    /// Analyze a switch case list for jump table suitability.
    pub fn analyze_switch(&self, cases: &[(i64, usize)]) -> SwitchAnalysis {
        SwitchAnalysis::analyze(cases)
    }

    /// Build a jump table from switch analysis.
    pub fn build_jump_table(&mut self, analysis: &SwitchAnalysis) -> Option<JumpTable> {
        if !analysis.should_use_jump_table() {
            return None;
        }
        let mut table = JumpTable::from_analysis(analysis);
        if self.jump_table.use_indirection && analysis.value_range > 64 {
            table.uses_indirection = true;
        }
        self.stats.jump_tables_created += 1;
        Some(table)
    }

    // -----------------------------------------------------------------------
    // Branch Redirect
    // -----------------------------------------------------------------------

    /// Analyze a branch for possible simplification.
    pub fn analyze_branch(
        &self,
        block: &MachineBasicBlock,
        block_idx: usize,
    ) -> Option<BranchSimplify> {
        if !self.redirect.enabled {
            return None;
        }

        // Check if the block ends with a conditional branch
        // For simplicity, we check if the block has 2 successors
        if block.successors.len() != 2 {
            return None;
        }

        let true_target = block.successors.first().copied();
        let false_target = block.successors.get(1).copied();

        let mut condition = ConditionInfo::new();
        condition.true_target = true_target;
        condition.false_target = false_target;

        // Determine if condition is foldable
        // (In practice, would analyze the last instruction for test/cmp patterns)
        let foldable = false; // Conservative: assume not foldable without analysis

        Some(BranchSimplify {
            block: block_idx,
            condition,
            foldable,
            folded_result: None,
            convert_to_unconditional: false,
        })
    }

    // -----------------------------------------------------------------------
    // Unreachable Block Elimination
    // -----------------------------------------------------------------------

    /// Run unreachable block elimination.
    pub fn run_unreachable_elim(
        &mut self,
        blocks: &mut Vec<MachineBasicBlock>,
    ) -> UnreachableElimResult {
        if !self.unreachable.enabled {
            return UnreachableElimResult::new();
        }

        let result = eliminate_unreachable_blocks(blocks);
        self.stats.unreachable_eliminated = result.eliminated_blocks.len();
        self.stats.instructions_saved += result.instructions_removed as isize;
        self.unreachable_result = Some(result.clone());
        result
    }

    // -----------------------------------------------------------------------
    // Block Merging
    // -----------------------------------------------------------------------

    /// Find pairs of blocks that can be merged (consecutive fallthrough).
    pub fn find_mergeable_pairs(&self, blocks: &[MachineBasicBlock]) -> Vec<MergeablePair> {
        let mut pairs = Vec::new();

        for (i, block) in blocks.iter().enumerate() {
            // Block must fall through to exactly one successor
            if block.successors.len() != 1 {
                continue;
            }
            let succ = block.successors[0];
            if succ >= blocks.len() {
                continue;
            }

            let succ_pred_count = blocks[succ].predecessors.len();
            let combined_size = block.instructions.len() + blocks[succ].instructions.len();

            pairs.push(MergeablePair::new(i, succ, succ_pred_count, combined_size));
        }

        pairs
    }

    /// Run block merging.
    pub fn run_block_merge(&mut self, blocks: &[MachineBasicBlock]) -> BlockMergeResult {
        let mut result = BlockMergeResult::new();

        if !self.block_merge.enabled {
            return result;
        }

        let pairs = self.find_mergeable_pairs(blocks);

        // Greedily merge pairs
        let mut merged_blocks: HashSet<usize> = HashSet::new();
        for pair in &pairs {
            if !pair.should_merge(&self.block_merge) {
                continue;
            }
            if merged_blocks.contains(&pair.pred) || merged_blocks.contains(&pair.succ) {
                continue;
            }
            merged_blocks.insert(pair.pred);
            merged_blocks.insert(pair.succ);
            result.merges_performed += 1;
            result.blocks_eliminated += 1;
            result.merged_pairs.push((pair.pred, pair.succ));
        }

        self.stats.blocks_merged = result.blocks_eliminated;
        self.block_merge_result = Some(result.clone());
        result
    }

    // -----------------------------------------------------------------------
    // Critical Edge Splitting
    // -----------------------------------------------------------------------

    /// Run critical edge splitting.
    pub fn run_critical_edge_splitting(
        &mut self,
        blocks: &[MachineBasicBlock],
        frequencies: Option<&[BlockFrequency]>,
    ) -> CriticalEdgeResult {
        let mut result = CriticalEdgeResult::new();

        if !self.critical_edge.enabled {
            return result;
        }

        let critical_edges = find_critical_edges(blocks, frequencies);

        for edge in &critical_edges {
            if !edge.is_critical() {
                continue;
            }
            if result.splits_performed >= self.critical_edge.max_splits {
                break;
            }
            if result.size_increase >= self.critical_edge.max_size_increase {
                break;
            }
            if edge.frequency < self.critical_edge.min_frequency {
                continue;
            }

            result.splits_performed += 1;
            // Each split adds a JMP instruction (5 bytes + block overhead)
            result.size_increase += 8;
            result.new_blocks.push(CriticalEdgeBlock {
                id: blocks.len() + result.new_blocks.len(),
                src: edge.src,
                dst: edge.dst,
                instructions: Vec::new(),
            });
        }

        self.stats.critical_edges_split = result.splits_performed;
        self.stats.code_size_delta += result.size_increase as isize;
        self.critical_edge_result = Some(result.clone());
        result
    }

    // -----------------------------------------------------------------------
    // Pipeline: run all optimizations in order
    // -----------------------------------------------------------------------

    /// Run the full branch folding pipeline on a function.
    pub fn run_pipeline(
        &mut self,
        blocks: &mut Vec<MachineBasicBlock>,
        probabilities: Option<&[BranchProbability]>,
    ) {
        // 1. Eliminate unreachable blocks
        self.run_unreachable_elim(blocks);

        // 2. Merge consecutive blocks
        self.run_block_merge(blocks);

        // 3. Tail merging
        self.run_tail_merge(blocks);

        // 4. Tail duplication
        self.run_tail_duplication(blocks);

        // 5. Critical edge splitting
        let _freqs: Option<Vec<BlockFrequency>> = probabilities.map(|probs| {
            let mut fb = Vec::new();
            for bp in probs {
                while fb.len() <= bp.src.max(bp.dst) {
                    fb.push(BlockFrequency::new(fb.len()));
                }
            }
            fb
        });
        self.run_critical_edge_splitting(blocks, _freqs.as_ref().map(|v| v.as_slice()));

        // 6. Block layout (informational only — actual reordering done elsewhere)
        if let Some(probs) = probabilities {
            self.run_block_layout(blocks, probs);
        }
    }
}

// ============================================================================
// Builder/factory functions
// ============================================================================

/// Create a default advanced branch folding pass.
pub fn make_x86_branch_folding_adv() -> X86BranchFoldingAdv {
    X86BranchFoldingAdv::new()
}

/// Create a branch folding pass with aggressive tail merging.
pub fn make_x86_branch_folding_adv_aggressive() -> X86BranchFoldingAdv {
    let mut bf = X86BranchFoldingAdv::new();
    bf.tail_merge.min_common_length = 1;
    bf.tail_merge.cross_block_merge = true;
    bf.tail_dup.min_savings = 1;
    bf.block_merge.aggressive_merge = true;
    bf
}

/// Create a branch folding pass optimized for code size.
pub fn make_x86_branch_folding_adv_size_opt() -> X86BranchFoldingAdv {
    let mut bf = X86BranchFoldingAdv::new();
    bf.tail_merge.min_common_length = 1;
    bf.tail_dup.enabled = false; // Duplication increases size
    bf.block_merge.aggressive_merge = true;
    bf.critical_edge.enabled = false; // Edge splitting increases size
    bf
}

/// Create a branch folding pass optimized for performance.
pub fn make_x86_branch_folding_adv_perf_opt() -> X86BranchFoldingAdv {
    let mut bf = X86BranchFoldingAdv::new();
    bf.tail_merge.enabled = true;
    bf.tail_dup.enabled = true;
    bf.tail_dup.min_savings = 1;
    bf.layout.strategy = LayoutStrategy::HotColdSplit;
    bf.layout.align_hot_blocks = true;
    bf.critical_edge.enabled = true;
    bf
}

/// Create a branch folding pass with custom hot/cold thresholds.
pub fn make_x86_branch_folding_adv_thresholds(
    hot_threshold: f64,
    cold_threshold: f64,
) -> X86BranchFoldingAdv {
    let mut bf = X86BranchFoldingAdv::new();
    bf.layout.hot_threshold = hot_threshold;
    bf.layout.cold_threshold = cold_threshold;
    bf
}

// ============================================================================
// Detailed Tail Merging Algorithm
// ============================================================================

/// A group of blocks that share a common tail suffix.
#[derive(Debug, Clone)]
pub struct TailMergeGroup {
    /// Blocks in this merge group.
    pub blocks: Vec<usize>,
    /// The common suffix instructions (shared by all blocks in the group).
    pub common_suffix: Vec<InstrHash>,
    /// Length of the common suffix.
    pub suffix_length: usize,
    /// The newly created block holding the merged tail.
    pub merged_block_id: Option<usize>,
}

impl TailMergeGroup {
    pub fn new(blocks: Vec<usize>, common_suffix: Vec<InstrHash>) -> Self {
        let suffix_length = common_suffix.len();
        Self {
            blocks,
            common_suffix,
            suffix_length,
            merged_block_id: None,
        }
    }

    /// Estimated savings from merging this group.
    pub fn estimated_savings(&self) -> usize {
        if self.blocks.len() < 2 {
            return 0;
        }
        // Each block (except one) saves the common suffix, but pays one JMP
        (self.blocks.len() - 1) * (self.suffix_length.saturating_sub(1))
    }
}

/// Find tail merge groups among a set of blocks.
/// Returns groups sorted by estimated savings (descending).
pub fn find_tail_merge_groups(
    blocks: &[MachineBasicBlock],
    config: &TailMergeConfig,
) -> Vec<TailMergeGroup> {
    let n = blocks.len().min(config.max_blocks);
    let mut groups: Vec<TailMergeGroup> = Vec::new();

    // Compute instruction hashes for each block
    let block_hashes: Vec<Vec<InstrHash>> = blocks[..n]
        .iter()
        .map(|b| b.instructions.iter().map(InstrHash::from_instr).collect())
        .collect();

    // Compare each pair of blocks that could merge
    let mut merged_into_group: HashSet<usize> = HashSet::new();

    for i in 0..n {
        if merged_into_group.contains(&i) {
            continue;
        }
        if blocks[i].successors.is_empty() {
            continue; // Don't merge return blocks
        }

        // Find all blocks that share a suffix with block i
        let mut group_blocks = vec![i];
        let mut group_suffix: Option<Vec<InstrHash>> = None;

        for j in (i + 1)..n {
            if merged_into_group.contains(&j) {
                continue;
            }
            if blocks[j].successors.is_empty() {
                continue;
            }

            let common_len =
                longest_common_suffix(&block_hashes[i], &block_hashes[j], config.max_compare);

            if common_len >= config.min_common_length {
                let suffix: Vec<InstrHash> =
                    block_hashes[i][block_hashes[i].len() - common_len..].to_vec();

                match &group_suffix {
                    None => {
                        group_suffix = Some(suffix);
                        group_blocks.push(j);
                        merged_into_group.insert(j);
                    }
                    Some(existing) => {
                        // Check if new block's suffix matches the group suffix
                        let suffix2: Vec<InstrHash> =
                            block_hashes[j][block_hashes[j].len() - common_len..].to_vec();
                        // Find commonality between existing group suffix and this suffix
                        let shared = longest_common_suffix(existing, &suffix2, config.max_compare);
                        if shared >= config.min_common_length {
                            let new_suffix = existing[existing.len() - shared..].to_vec();
                            group_suffix = Some(new_suffix);
                            group_blocks.push(j);
                            merged_into_group.insert(j);
                        }
                    }
                }
            }
        }

        if group_blocks.len() >= 2 {
            if let Some(suffix) = group_suffix {
                merged_into_group.insert(i);
                groups.push(TailMergeGroup::new(group_blocks, suffix));
            }
        }
    }

    // Sort by estimated savings descending
    groups.sort_by(|a, b| b.estimated_savings().cmp(&a.estimated_savings()));
    groups
}

// ============================================================================
// Detailed Tail Duplication Algorithm
// ============================================================================

/// Detailed cost-benefit analysis for tail duplication.
#[derive(Debug, Clone)]
pub struct TailDupCostModel {
    /// Cost per byte of code increase.
    pub cost_per_byte: f64,
    /// Benefit per eliminated branch.
    pub benefit_per_branch: f64,
    /// Benefit per improved fallthrough.
    pub benefit_per_fallthrough: f64,
    /// Maximum duplication size in instructions.
    pub max_dup_size: usize,
    /// Whether to account for cache effects.
    pub account_cache: bool,
    /// L1 instruction cache size (for ICache pressure modeling).
    pub l1_icache_size: usize,
}

impl Default for TailDupCostModel {
    fn default() -> Self {
        Self {
            cost_per_byte: 0.1,
            benefit_per_branch: 3.0,
            benefit_per_fallthrough: 1.5,
            max_dup_size: 32,
            account_cache: true,
            l1_icache_size: 32 * 1024,
        }
    }
}

impl TailDupCostModel {
    /// Evaluate whether duplicating a block is profitable.
    pub fn evaluate(
        &self,
        block_size: usize,
        num_preds: usize,
        num_branches_eliminated: usize,
        creates_fallthrough: bool,
    ) -> (bool, f64) {
        if block_size > self.max_dup_size {
            return (false, -1.0);
        }

        let code_cost = block_size as f64 * (num_preds - 1) as f64 * self.cost_per_byte;
        let branch_benefit = num_branches_eliminated as f64 * self.benefit_per_branch;
        let fallthrough_benefit = if creates_fallthrough {
            self.benefit_per_fallthrough
        } else {
            0.0
        };

        let net_benefit = branch_benefit + fallthrough_benefit - code_cost;
        (net_benefit > 0.0, net_benefit)
    }

    /// Estimate the ICache pressure impact of duplicating a block.
    pub fn icache_impact(&self, total_code_size: usize, dup_size: usize) -> f64 {
        if !self.account_cache {
            return 0.0;
        }
        if total_code_size > self.l1_icache_size {
            // Already exceeding L1 ICache — duplication is costly
            return dup_size as f64 * 0.5;
        }
        let remaining = self.l1_icache_size - total_code_size;
        if dup_size as f64 > remaining as f64 * 0.1 {
            // Duplication uses more than 10% of remaining cache
            return dup_size as f64 * 0.2;
        }
        0.0
    }
}

// ============================================================================
// Branch Threading Analysis
// ============================================================================

/// A path through the CFG that can be threaded (two branches unified).
#[derive(Debug, Clone)]
pub struct ThreadablePath {
    /// Blocks on the threading path (in order).
    pub path: Vec<usize>,
    /// Whether the path is profitable to thread.
    pub profitable: bool,
    /// Number of jumps eliminated by threading.
    pub jumps_eliminated: usize,
    /// Whether threading creates a fallthrough opportunity.
    pub creates_fallthrough: bool,
    /// Estimated net code size change.
    pub net_size_change: isize,
}

impl ThreadablePath {
    pub fn new(path: Vec<usize>) -> Self {
        Self {
            path,
            profitable: false,
            jumps_eliminated: 0,
            creates_fallthrough: false,
            net_size_change: 0,
        }
    }

    /// Length of the path.
    pub fn len(&self) -> usize {
        self.path.len()
    }

    /// Whether the path is empty.
    pub fn is_empty(&self) -> bool {
        self.path.is_empty()
    }
}

/// Find threadable paths through the CFG.
/// A path is threadable when:
///   A branches conditionally to B, B branches unconditionally to C
///   → we can redirect A to branch directly to C when the B condition is met.
pub fn find_threadable_paths(
    blocks: &[MachineBasicBlock],
    max_depth: usize,
) -> Vec<ThreadablePath> {
    let n = blocks.len();
    let mut paths = Vec::new();

    for src in 0..n {
        // Find paths starting from conditional branches (blocks with 2 successors)
        if blocks[src].successors.len() != 2 {
            continue;
        }

        for &mid in &blocks[src].successors {
            if mid >= n {
                continue;
            }
            // Middle block must have exactly 1 successor (unconditional jump)
            if blocks[mid].successors.len() != 1 {
                continue;
            }
            // Middle block must have only one predecessor (or we're creating duplicate)
            if blocks[mid].predecessors.len() != 1 {
                continue;
            }

            let dst = blocks[mid].successors[0];
            if dst >= n || dst == src {
                continue;
            }

            // Check if threading would be beneficial:
            // - The middle block must be small (just a branch)
            if blocks[mid].instructions.len() > max_depth {
                continue;
            }

            let mut path = ThreadablePath::new(vec![src, mid, dst]);
            path.jumps_eliminated = 1;
            path.profitable = blocks[mid].instructions.len() <= 3;
            path.net_size_change = -(blocks[mid].instructions.len() as isize);
            paths.push(path);
        }
    }

    // Sort by profitability (most jumps eliminated first)
    paths.sort_by(|a, b| b.jumps_eliminated.cmp(&a.jumps_eliminated));
    paths
}

// ============================================================================
// Conditional-to-Unconditional Branch Conversion
// ============================================================================

/// Result of analyzing whether a conditional branch can become unconditional.
#[derive(Debug, Clone)]
pub struct CondToUncondResult {
    /// The block containing the conditional branch.
    pub block: usize,
    /// Whether conversion is possible.
    pub can_convert: bool,
    /// If convertible, the target of the new unconditional branch.
    pub new_target: Option<usize>,
    /// The target that becomes unreachable (needs cleanup).
    pub unreachable_target: Option<usize>,
    /// Reason if conversion is not possible.
    pub reason: Option<String>,
}

impl CondToUncondResult {
    pub fn convertible(block: usize, new_target: usize, unreachable: usize) -> Self {
        Self {
            block,
            can_convert: true,
            new_target: Some(new_target),
            unreachable_target: Some(unreachable),
            reason: None,
        }
    }

    pub fn not_convertible(block: usize, reason: String) -> Self {
        Self {
            block,
            can_convert: false,
            new_target: None,
            unreachable_target: None,
            reason: Some(reason),
        }
    }
}

/// Analyze conditional branches for possible conversion to unconditional.
///
/// A conditional branch can become unconditional when:
/// 1. Both targets are the same block (redundant branch)
/// 2. The condition is known at compile time (constant folding)
/// 3. One target is unreachable (dead code)
pub fn analyze_cond_to_uncond(
    blocks: &[MachineBasicBlock],
    reachable: &HashSet<usize>,
) -> Vec<CondToUncondResult> {
    let n = blocks.len();
    let mut results = Vec::new();

    for i in 0..n {
        let succs = &blocks[i].successors;
        if succs.len() != 2 {
            continue;
        }

        let true_target = succs[0];
        let false_target = succs[1];

        // Case 1: Both targets are the same
        if true_target == false_target {
            results.push(CondToUncondResult::convertible(i, true_target, true_target));
            continue;
        }

        // Case 2: True target is unreachable
        if true_target < n && !reachable.contains(&true_target) {
            results.push(CondToUncondResult::convertible(
                i,
                false_target,
                true_target,
            ));
            continue;
        }

        // Case 3: False target is unreachable
        if false_target < n && !reachable.contains(&false_target) {
            results.push(CondToUncondResult::convertible(
                i,
                true_target,
                false_target,
            ));
            continue;
        }

        // Not convertible
        results.push(CondToUncondResult::not_convertible(
            i,
            "Both targets are distinct and reachable".to_string(),
        ));
    }

    results
}

// ============================================================================
// Branch Prediction Metadata Propagation
// ============================================================================

/// Branch prediction hint (for static branch prediction).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BranchPredictionHint {
    /// No prediction hint.
    None,
    /// Likely taken (forward branch not taken pattern).
    LikelyTaken,
    /// Likely not taken.
    LikelyNotTaken,
    /// Loop branch (strongly taken).
    LoopBranch,
    /// Error/unlikely path (strongly not taken).
    UnlikelyPath,
}

impl BranchPredictionHint {
    /// Get the static branch prediction probability.
    pub fn probability(&self) -> f64 {
        match self {
            Self::None => 0.5,
            Self::LikelyTaken => 0.8,
            Self::LikelyNotTaken => 0.2,
            Self::LoopBranch => 0.95,
            Self::UnlikelyPath => 0.05,
        }
    }

    /// Get a hint from block and CFG properties.
    pub fn infer(
        block: usize,
        target: usize,
        blocks: &[MachineBasicBlock],
        dom_tree: Option<&crate::x86::x86_basic_block_utils::DominatorTree>,
    ) -> Self {
        // If target dominates block, it's likely a loop backedge
        if let Some(dt) = dom_tree {
            if dt.dominates(target, block) {
                return Self::LoopBranch;
            }
        }

        // If target is below block in CFG order (forward branch), less likely
        if target > block && target < blocks.len() {
            return Self::LikelyNotTaken;
        }

        Self::None
    }
}

// ============================================================================
// Fallthrough Chain Builder
// ============================================================================

/// A fallthrough chain: a sequence of blocks where each falls through to the next.
#[derive(Debug, Clone)]
pub struct FallthroughChain {
    /// Blocks in the chain, in order.
    pub blocks: Vec<usize>,
    /// Total execution frequency of blocks in the chain.
    pub total_freq: f64,
    /// Number of unconditional jumps eliminated.
    pub jumps_eliminated: usize,
}

impl FallthroughChain {
    pub fn new(block: usize, freq: f64) -> Self {
        Self {
            blocks: vec![block],
            total_freq: freq,
            jumps_eliminated: 0,
        }
    }

    /// Try to extend the chain by adding a successor that follows the last block.
    pub fn try_extend(
        &mut self,
        blocks: &[MachineBasicBlock],
        freq_est: &BlockFrequencyEstimator,
        placed: &HashSet<usize>,
        max_len: usize,
    ) -> bool {
        if self.blocks.len() >= max_len {
            return false;
        }

        let last = *self.blocks.last().unwrap();
        if last >= blocks.len() {
            return false;
        }

        // The best successor to add is one that:
        // 1. Is not already placed
        // 2. Follows naturally from last (is a successor of last)
        // 3. Has exactly one predecessor (so no other paths merge here)
        let best_succ = blocks[last]
            .successors
            .iter()
            .filter(|&&s| s < blocks.len() && !placed.contains(&s))
            .filter(|&&s| blocks[s].predecessors.len() == 1)
            .max_by(|&&a, &&b| {
                freq_est
                    .frequency_of(a)
                    .partial_cmp(&freq_est.frequency_of(b))
                    .unwrap_or(std::cmp::Ordering::Equal)
            });

        if let Some(&succ) = best_succ {
            self.blocks.push(succ);
            self.total_freq += freq_est.frequency_of(succ);
            // If the last block had an unconditional jump to succ, we eliminated it
            if blocks[last].successors.len() == 1 && blocks[last].successors[0] == succ {
                self.jumps_eliminated += 1;
            }
            true
        } else {
            false
        }
    }

    /// Compute the net benefit of this chain.
    pub fn net_benefit(&self) -> f64 {
        // Benefit: eliminated jumps * weight + fallthrough efficiency
        let jump_benefit = self.jumps_eliminated as f64 * 2.0;
        let freq_benefit = self.total_freq * 0.5;
        jump_benefit + freq_benefit
    }
}

/// Build optimal fallthrough chains from the CFG.
pub fn build_fallthrough_chains(
    blocks: &[MachineBasicBlock],
    freq_est: &BlockFrequencyEstimator,
    max_chain_len: usize,
) -> Vec<FallthroughChain> {
    let n = blocks.len();
    if n == 0 {
        return Vec::new();
    }

    let mut chains: Vec<FallthroughChain> = Vec::new();
    let mut placed: HashSet<usize> = HashSet::new();

    // Start chains from "hot" blocks first
    let mut block_order: Vec<usize> = (0..n).collect();
    block_order.sort_by(|&a, &b| {
        freq_est
            .frequency_of(b)
            .partial_cmp(&freq_est.frequency_of(a))
            .unwrap_or(std::cmp::Ordering::Equal)
    });

    for block in block_order {
        if placed.contains(&block) {
            continue;
        }

        let mut chain = FallthroughChain::new(block, freq_est.frequency_of(block));
        placed.insert(block);

        // Extend chain greedily
        while chain.try_extend(blocks, freq_est, &placed, max_chain_len) {
            let last = *chain.blocks.last().unwrap();
            placed.insert(last);
        }

        chains.push(chain);
    }

    chains
}

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

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

    // -----------------------------------------------------------------------
    // InstrHash tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_instr_hash_equivalence() {
        let mut instr1 = MachineInstr::new(100);
        instr1.push_reg(1);
        instr1.push_imm(42);

        let mut instr2 = MachineInstr::new(100);
        instr2.push_reg(1);
        instr2.push_imm(42);

        let h1 = InstrHash::from_instr(&instr1);
        let h2 = InstrHash::from_instr(&instr2);
        assert!(h1.can_merge_with(&h2));
    }

    #[test]
    fn test_instr_hash_different_opcode() {
        let instr1 = MachineInstr::new(100);
        let instr2 = MachineInstr::new(200);
        let h1 = InstrHash::from_instr(&instr1);
        let h2 = InstrHash::from_instr(&instr2);
        assert!(!h1.can_merge_with(&h2));
    }

    #[test]
    fn test_instr_hash_different_operand() {
        let mut instr1 = MachineInstr::new(100);
        instr1.push_imm(42);
        let mut instr2 = MachineInstr::new(100);
        instr2.push_imm(99);
        let h1 = InstrHash::from_instr(&instr1);
        let h2 = InstrHash::from_instr(&instr2);
        assert!(!h1.can_merge_with(&h2));
    }

    // -----------------------------------------------------------------------
    // Longest Common Suffix tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_longest_common_suffix_empty() {
        let a: Vec<InstrHash> = vec![];
        let b: Vec<InstrHash> = vec![];
        assert_eq!(longest_common_suffix(&a, &b, 64), 0);
    }

    #[test]
    fn test_longest_common_suffix_identical() {
        let mut i1 = MachineInstr::new(1);
        i1.push_imm(10);
        let mut i2 = MachineInstr::new(2);
        i2.push_imm(20);

        let a = vec![InstrHash::from_instr(&i1), InstrHash::from_instr(&i2)];
        let b = vec![InstrHash::from_instr(&i1), InstrHash::from_instr(&i2)];
        assert_eq!(longest_common_suffix(&a, &b, 64), 2);
    }

    #[test]
    fn test_longest_common_suffix_partial() {
        let mut i1 = MachineInstr::new(1);
        i1.push_imm(10);
        let mut i2 = MachineInstr::new(2);
        i2.push_imm(20);
        let mut i3 = MachineInstr::new(3);
        i3.push_imm(30);

        let a = vec![InstrHash::from_instr(&i1), InstrHash::from_instr(&i2)];
        let b = vec![InstrHash::from_instr(&i3), InstrHash::from_instr(&i2)];
        assert_eq!(longest_common_suffix(&a, &b, 64), 1);
    }

    // -----------------------------------------------------------------------
    // TailMergeCandidate tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_tail_merge_candidate_profitable() {
        let c = TailMergeCandidate::new(0, 1, 3);
        assert!(c.is_profitable());
    }

    #[test]
    fn test_tail_merge_candidate_not_profitable() {
        let c = TailMergeCandidate::new(0, 1, 1);
        assert!(!c.is_profitable());
    }

    // -----------------------------------------------------------------------
    // TailDupCandidate tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_tail_dup_profitable() {
        let candidate = TailDupCandidate::new(0, 1, 5, 8);
        assert!(candidate.profitable);
    }

    #[test]
    fn test_tail_dup_not_profitable_low_savings() {
        let candidate = TailDupCandidate::new(0, 1, 1, 8);
        assert!(!candidate.profitable); // savings < MIN_TAIL_DUP_SAVINGS (2)
    }

    // -----------------------------------------------------------------------
    // BranchProbability tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_branch_probability_hot_cold() {
        let hot = BranchProbability::new(0, 1, 0.95);
        let cold = BranchProbability::new(0, 2, 0.05);

        assert!(hot.is_hot(0.8));
        assert!(!hot.is_cold(0.2));
        assert!(cold.is_cold(0.2));
        assert!(!cold.is_hot(0.8));
    }

    #[test]
    fn test_branch_probability_complement() {
        let bp = BranchProbability::new(0, 1, 0.7);
        assert!((bp.complement() - 0.3).abs() < 1e-9);
    }

    // -----------------------------------------------------------------------
    // StaticBranchHeuristic tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_heuristic_probabilities() {
        assert!((StaticBranchHeuristic::LoopBackedge.probability() - 0.90).abs() < 1e-9);
        assert!((StaticBranchHeuristic::CmpZero.probability() - 0.25).abs() < 1e-9);
        assert!((StaticBranchHeuristic::ExceptionPath.probability() - 0.05).abs() < 1e-9);
        assert!((StaticBranchHeuristic::CmpEquality.probability() - 0.30).abs() < 1e-9);
    }

    // -----------------------------------------------------------------------
    // BlockFrequency tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_block_frequency_hot_cold() {
        let mut bf = BlockFrequency::new(0);
        bf.frequency = 0.9;
        assert!(bf.is_hot(0.8));
        assert!(!bf.is_cold(0.2));

        bf.frequency = 0.1;
        assert!(!bf.is_hot(0.8));
        assert!(bf.is_cold(0.2));
    }

    #[test]
    fn test_propagate_frequencies_empty() {
        let blocks: Vec<MachineBasicBlock> = vec![];
        let probs: Vec<BranchProbability> = vec![];
        let freqs = propagate_frequencies(&blocks, &probs);
        assert!(freqs.is_empty());
    }

    #[test]
    fn test_propagate_frequencies_single_block() {
        let b0 = MachineBasicBlock::new(0);
        let blocks = vec![b0];
        let probs: Vec<BranchProbability> = vec![];
        let freqs = propagate_frequencies(&blocks, &probs);
        assert_eq!(freqs.len(), 1);
        assert!((freqs[0].frequency - 1.0).abs() < 1e-9);
    }

    // -----------------------------------------------------------------------
    // BlockChain tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_block_chain_new() {
        let chain = BlockChain::new(5, 3.0, true);
        assert_eq!(chain.blocks, vec![5]);
        assert!(chain.is_hot);
        assert_eq!(chain.first(), Some(5));
        assert_eq!(chain.last(), Some(5));
    }

    #[test]
    fn test_block_chain_merge_after() {
        let mut a = BlockChain::new(0, 1.0, true);
        let b = BlockChain::new(1, 0.5, false);
        a.merge_after(&b);
        assert_eq!(a.blocks, vec![0, 1]);
        assert!((a.total_frequency - 1.5).abs() < 1e-9);
    }

    #[test]
    fn test_block_chain_merge_before() {
        let mut a = BlockChain::new(3, 1.0, true);
        let b = BlockChain::new(2, 0.5, false);
        a.merge_before(&b);
        assert_eq!(a.blocks, vec![2, 3]);
    }

    // -----------------------------------------------------------------------
    // SwitchAnalysis tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_switch_analysis_empty() {
        let analysis = SwitchAnalysis::analyze(&[]);
        assert_eq!(analysis.num_cases, 0);
        assert!(!analysis.suitable_for_jump_table);
    }

    #[test]
    fn test_switch_analysis_dense() {
        let cases = vec![(1, 10), (2, 11), (3, 12), (4, 13), (5, 14)];
        let analysis = SwitchAnalysis::analyze(&cases);
        assert_eq!(analysis.num_cases, 5);
        assert_eq!(analysis.value_range, 5);
        assert!(analysis.density >= 1.0);
        assert!(analysis.should_use_jump_table());
    }

    #[test]
    fn test_switch_analysis_sparse() {
        let cases = vec![(1, 10), (100, 11), (1000, 12)];
        let analysis = SwitchAnalysis::analyze(&cases);
        assert_eq!(analysis.num_cases, 3);
        // value_range = 1000 - 1 + 1 = 1000
        // density = 3/1000 = 0.003
        assert!(analysis.density < MIN_JUMP_TABLE_DENSITY);
        assert!(!analysis.should_use_jump_table());
    }

    // -----------------------------------------------------------------------
    // JumpTable tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_jump_table_from_analysis() {
        let cases = vec![(0, 5), (1, 6), (2, 7)];
        let analysis = SwitchAnalysis::analyze(&cases);
        let table = JumpTable::from_analysis(&analysis);
        assert_eq!(table.entries.len(), 3);
        assert_eq!(table.base_value, 0);
        assert_eq!(table.range, 3);
    }

    // -----------------------------------------------------------------------
    // ConditionInfo tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_condition_info_heuristic() {
        let mut ci = ConditionInfo::new();
        assert!(ci.heuristic().is_none());

        ci.is_loop_backedge = true;
        assert_eq!(ci.heuristic(), Some(StaticBranchHeuristic::LoopBackedge));

        ci.is_loop_backedge = false;
        ci.is_zero_test = true;
        assert_eq!(ci.heuristic(), Some(StaticBranchHeuristic::CmpZero));
    }

    #[test]
    fn test_condition_estimated_probability() {
        let mut ci = ConditionInfo::new();
        assert!((ci.estimated_probability() - 0.5).abs() < 1e-9);

        ci.is_loop_backedge = true;
        assert!((ci.estimated_probability() - 0.90).abs() < 1e-9);
    }

    // -----------------------------------------------------------------------
    // Reachability tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_find_reachable_blocks_simple() {
        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1];
        let mut b1 = MachineBasicBlock::new(1);
        b1.successors = vec![2];
        let b2 = MachineBasicBlock::new(2);

        let blocks = vec![b0, b1, b2];
        let reachable = find_reachable_blocks(&blocks);
        assert_eq!(reachable.len(), 3);
        assert!(reachable.contains(&0));
        assert!(reachable.contains(&1));
        assert!(reachable.contains(&2));
    }

    #[test]
    fn test_find_reachable_blocks_with_unreachable() {
        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1];
        let b1 = MachineBasicBlock::new(1);
        // b2 has no predecessors, so unreachable
        let b2 = MachineBasicBlock::new(2);

        let blocks = vec![b0, b1, b2];
        let reachable = find_reachable_blocks(&blocks);
        assert_eq!(reachable.len(), 2);
        assert!(reachable.contains(&0));
        assert!(reachable.contains(&1));
        assert!(!reachable.contains(&2));
    }

    // -----------------------------------------------------------------------
    // Unreachable elimination tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_eliminate_unreachable_blocks() {
        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1];
        let mut b1 = MachineBasicBlock::new(1);
        b1.predecessors = vec![0];
        let b2 = MachineBasicBlock::new(2);
        // b2 is unreachable (no predecessors, no path from entry)

        let mut blocks = vec![b0, b1, b2];
        let result = eliminate_unreachable_blocks(&mut blocks);
        assert_eq!(result.eliminated_blocks.len(), 1);
        assert!(result.eliminated_blocks.contains(&2));
    }

    // -----------------------------------------------------------------------
    // Critical edge detection tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_find_critical_edges() {
        // b0 -> b1, b2  (b0 has 2 successors)
        // b1 -> b3
        // b2 -> b3       (b3 has 2 predecessors)
        // Edge b0->b2 is critical (b0 has 2 succs, b2 has 1 pred — not critical)
        // Edge b0->b1 is not critical (b1 has 1 pred)
        // Edge b1->b3 is not critical (b1 has 1 succ)
        // Edge b2->b3: b2 has 1 succ, b3 has 2 preds — not critical
        // Actually: b0 has 2 succs, b3 has 2 preds — both >1
        // So b0->b1? No, b1 has only 1 pred (b0). b0->b2? b2 has only 1 pred (b0).
        // Wait: let me reconsider:
        // b0: succs [1, 2] — 2 successors
        // b1: succs [3]     — 1 successor, preds [0] — 1 predecessor
        // b2: succs [3]     — 1 successor, preds [0] — 1 predecessor
        // b3: preds [1, 2]  — 2 predecessors

        // Edge b0->b1: src_succ_count=2, dst_pred_count=1 — not critical
        // Edge b0->b2: src_succ_count=2, dst_pred_count=1 — not critical
        // Edge b1->b3: src_succ_count=1 — not critical
        // Edge b2->b3: src_succ_count=1 — not critical

        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1, 2];
        let mut b1 = MachineBasicBlock::new(1);
        b1.predecessors = vec![0];
        b1.successors = vec![3];
        let mut b2 = MachineBasicBlock::new(2);
        b2.predecessors = vec![0];
        b2.successors = vec![3];
        let mut b3 = MachineBasicBlock::new(3);
        b3.predecessors = vec![1, 2];

        let blocks = vec![b0, b1, b2, b3];
        let edges = find_critical_edges(&blocks, None);
        assert!(edges.is_empty()); // No critical edges in this diamond
    }

    #[test]
    fn test_find_critical_edges_present() {
        // Diamond where both branch targets have multiple preds
        // b0 has 2 succs, b1 has 2 preds, b2 has 2 preds
        // This is uncommon but shows the logic

        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1, 2];
        let mut b1 = MachineBasicBlock::new(1);
        b1.predecessors = vec![0, 2]; // 2 predecessors
        let mut b2 = MachineBasicBlock::new(2);
        b2.predecessors = vec![0, 1]; // 2 predecessors
        b2.successors = vec![1];

        let blocks = vec![b0, b1, b2];
        let edges = find_critical_edges(&blocks, None);
        // b0->b1: src_succ_count=2, dst_pred_count=2 → critical
        // b0->b2: src_succ_count=2, dst_pred_count=2 → critical
        assert_eq!(edges.len(), 2);
    }

    // -----------------------------------------------------------------------
    // MergeablePair tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_mergeable_pair_single_pred() {
        let pair = MergeablePair::new(0, 1, 1, 50);
        let config = BlockMergeConfig::default();
        assert!(pair.should_merge(&config));
    }

    #[test]
    fn test_mergeable_pair_too_large() {
        let pair = MergeablePair::new(0, 1, 1, 500);
        let config = BlockMergeConfig::default();
        assert!(!pair.should_merge(&config));
    }

    #[test]
    fn test_mergeable_pair_multi_pred_no_merge() {
        // With default config, only single-pred successors should be merged
        let pair = MergeablePair::new(0, 1, 3, 50);
        let config = BlockMergeConfig::default();
        // single_pred is false (3 predecessors), so should not merge
        assert!(!pair.should_merge(&config));
    }

    // -----------------------------------------------------------------------
    // X86BranchFoldingAdv integration tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_make_branch_folding_adv() {
        let bf = make_x86_branch_folding_adv();
        assert!(bf.tail_merge.enabled);
        assert!(bf.tail_dup.enabled);
        assert!(bf.unreachable.enabled);
    }

    #[test]
    fn test_make_aggressive() {
        let bf = make_x86_branch_folding_adv_aggressive();
        assert_eq!(bf.tail_merge.min_common_length, 1);
        assert!(bf.block_merge.aggressive_merge);
    }

    #[test]
    fn test_make_size_opt() {
        let bf = make_x86_branch_folding_adv_size_opt();
        assert!(!bf.tail_dup.enabled);
        assert!(bf.block_merge.aggressive_merge);
    }

    #[test]
    fn test_make_perf_opt() {
        let bf = make_x86_branch_folding_adv_perf_opt();
        assert!(bf.critical_edge.enabled);
        assert!(bf.layout.align_hot_blocks);
    }

    #[test]
    fn test_pipeline_empty_function() {
        let mut bf = X86BranchFoldingAdv::new();
        let mut blocks: Vec<MachineBasicBlock> = vec![];
        bf.run_pipeline(&mut blocks, None);
        // Should not panic
    }

    #[test]
    fn test_analyze_tail_merge_empty() {
        let bf = X86BranchFoldingAdv::new();
        let blocks: Vec<MachineBasicBlock> = vec![];
        let candidates = bf.analyze_tail_merge(&blocks);
        assert!(candidates.is_empty());
    }

    #[test]
    fn test_build_jump_table_rejects_bad_switch() {
        let bf = X86BranchFoldingAdv::new();
        let analysis = SwitchAnalysis::analyze(&[(1, 5), (1000, 6)]);
        let table = bf.build_jump_table(&analysis);
        assert!(table.is_none());
    }

    #[test]
    fn test_find_mergeable_pairs() {
        let bf = X86BranchFoldingAdv::new();
        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1];
        b0.instructions = vec![MachineInstr::new(1)];
        let mut b1 = MachineBasicBlock::new(1);
        b1.predecessors = vec![0];
        b1.instructions = vec![MachineInstr::new(2)];

        let blocks = vec![b0, b1];
        let pairs = bf.find_mergeable_pairs(&blocks);
        assert_eq!(pairs.len(), 1);
        assert_eq!(pairs[0].pred, 0);
        assert_eq!(pairs[0].succ, 1);
    }

    #[test]
    fn test_analyze_branch_two_successors() {
        let bf = X86BranchFoldingAdv::new();
        let mut block = MachineBasicBlock::new(0);
        block.successors = vec![1, 2];

        let result = bf.analyze_branch(&block, 0);
        assert!(result.is_some());
        let branch = result.unwrap();
        assert_eq!(branch.block, 0);
        assert_eq!(branch.condition.true_target, Some(1));
        assert_eq!(branch.condition.false_target, Some(2));
    }

    #[test]
    fn test_analyze_branch_not_branch() {
        let bf = X86BranchFoldingAdv::new();
        let block = MachineBasicBlock::new(0); // No successors

        let result = bf.analyze_branch(&block, 0);
        assert!(result.is_none());
    }

    #[test]
    fn test_branch_folding_stats_default() {
        let stats = BranchFoldingStats::default();
        assert_eq!(stats.tail_merges, 0);
        assert_eq!(stats.tail_duplications, 0);
        assert_eq!(stats.instructions_saved, 0);
    }

    // -----------------------------------------------------------------------
    // TailMergeGroup tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_tail_merge_group_savings() {
        let mut i1 = MachineInstr::new(1);
        i1.push_imm(10);
        let hashes = vec![InstrHash::from_instr(&i1)];
        let group = TailMergeGroup::new(vec![0, 1], hashes);
        assert_eq!(group.blocks.len(), 2);
        assert!(group.estimated_savings() == 0); // 1 instr - 1 = 0 savings
    }

    #[test]
    fn test_tail_merge_group_multi_block() {
        let mut i1 = MachineInstr::new(1);
        i1.push_imm(10);
        let mut i2 = MachineInstr::new(2);
        i2.push_imm(20);
        let mut i3 = MachineInstr::new(3);
        i3.push_imm(30);
        let hashes = vec![
            InstrHash::from_instr(&i1),
            InstrHash::from_instr(&i2),
            InstrHash::from_instr(&i3),
        ];
        let group = TailMergeGroup::new(vec![0, 1, 2], hashes);
        assert!(group.estimated_savings() > 0);
    }

    // -----------------------------------------------------------------------
    // TailDupCostModel tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_tail_dup_cost_model_profitable() {
        let model = TailDupCostModel::default();
        let (profitable, benefit) = model.evaluate(5, 3, 2, true);
        assert!(profitable);
        assert!(benefit > 0.0);
    }

    #[test]
    fn test_tail_dup_cost_model_too_large() {
        let model = TailDupCostModel::default();
        let (profitable, _) = model.evaluate(64, 3, 2, true);
        assert!(!profitable);
    }

    #[test]
    fn test_tail_dup_cost_model_icache_impact() {
        let model = TailDupCostModel::default();
        let impact = model.icache_impact(32 * 1024 + 1, 100);
        assert!(impact > 0.0); // Exceeding L1 ICache
    }

    // -----------------------------------------------------------------------
    // ThreadablePath / Branch Threading tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_find_threadable_paths_empty() {
        let blocks: Vec<MachineBasicBlock> = vec![];
        let paths = find_threadable_paths(&blocks, 3);
        assert!(paths.is_empty());
    }

    #[test]
    fn test_threadable_path_new() {
        let path = ThreadablePath::new(vec![0, 1, 2]);
        assert_eq!(path.len(), 3);
        assert!(!path.is_empty());
        assert!(!path.profitable);
    }

    // -----------------------------------------------------------------------
    // CondToUncondResult tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_cond_to_uncond_same_targets() {
        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1, 1]; // Both targets same
        let blocks = vec![b0];
        let reachable: HashSet<usize> = [0, 1].iter().copied().collect();

        let results = analyze_cond_to_uncond(&blocks, &reachable);
        assert_eq!(results.len(), 1);
        assert!(results[0].can_convert);
    }

    #[test]
    fn test_cond_to_uncond_unreachable_target() {
        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1, 2];
        let blocks = vec![b0, MachineBasicBlock::new(1), MachineBasicBlock::new(2)];
        let reachable: HashSet<usize> = [0, 1].iter().copied().collect();

        let results = analyze_cond_to_uncond(&blocks, &reachable);
        assert_eq!(results.len(), 1);
        assert!(results[0].can_convert); // target 2 is unreachable
    }

    // -----------------------------------------------------------------------
    // BranchPredictionHint tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_branch_prediction_hint_probabilities() {
        assert!((BranchPredictionHint::LoopBranch.probability() - 0.95).abs() < 1e-9);
        assert!((BranchPredictionHint::UnlikelyPath.probability() - 0.05).abs() < 1e-9);
        assert!((BranchPredictionHint::LikelyTaken.probability() - 0.8).abs() < 1e-9);
        assert!((BranchPredictionHint::None.probability() - 0.5).abs() < 1e-9);
    }

    #[test]
    fn test_branch_prediction_hint_infer() {
        let blocks = make_loop_cfg();
        let hint = BranchPredictionHint::infer(3, 1, &blocks, None);
        // Without dom tree, forward vs backward inference
        // 3 > 1 so it's a backward branch (not forward)
        assert_eq!(hint, BranchPredictionHint::None);
    }

    // -----------------------------------------------------------------------
    // FallthroughChain tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_fallthrough_chain_new() {
        let chain = FallthroughChain::new(0, 1.5);
        assert_eq!(chain.blocks, vec![0]);
        assert!((chain.total_freq - 1.5).abs() < 1e-9);
        assert_eq!(chain.jumps_eliminated, 0);
    }

    #[test]
    fn test_build_fallthrough_chains_empty() {
        let fe = BlockFrequencyEstimator::new();
        let chains = build_fallthrough_chains(&[], &fe, 100);
        assert!(chains.is_empty());
    }

    #[test]
    fn test_fallthrough_chain_net_benefit() {
        let mut chain = FallthroughChain::new(0, 10.0);
        chain.jumps_eliminated = 2;
        let benefit = chain.net_benefit();
        assert!(benefit > 0.0);
    }

    // Helper for loop CFG used by threading tests
    fn make_loop_cfg() -> Vec<MachineBasicBlock> {
        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1];
        let mut b1 = MachineBasicBlock::new(1);
        b1.predecessors = vec![0, 3];
        b1.successors = vec![2];
        let mut b2 = MachineBasicBlock::new(2);
        b2.predecessors = vec![1];
        b2.successors = vec![3];
        let mut b3 = MachineBasicBlock::new(3);
        b3.predecessors = vec![2];
        b3.successors = vec![1];
        vec![b0, b1, b2, b3]
    }
}