llvm-native-core 0.1.11

//! X86 Basic Block Utilities — analysis and manipulation primitives for
//! machine basic blocks on X86/X86-64 targets. Implements dominator tree
//! construction, post-dominator tree, dominance frontiers, loop info extraction
//! from CFG, control dependence graph, reachability analysis, block frequency
//! estimation with static heuristics, block alignment requirements, block layout
//! optimization, branch weight metadata annotation, machine block placement
//! helpers, block address taken analysis, exception handling block identification,
//! and landing pad/cleanup block classification.
//!
//! Clean-room behavioral reconstruction from:
//! - Intel® 64 and IA-32 Architectures Software Developer's Manual, Vol. 1
//!   (Chapter 6: Procedure Calls, Interrupts, and Exceptions)
//! - System V ABI: AMD64 Architecture Processor Supplement
//!   (Sections 3.6, 3.7: Exception Handling and Stack Unwinding)
//! - Microsoft x64 Exception Handling (structured exception handling)
//! - Compiler theory literature on dominance, loops, and control flow analysis
//! - "A Fast Algorithm for Finding Dominators in a Flow Graph" (Lengauer-Tarjan)
//! - "The Program Structure Tree" (Johnson-Pearson-Pingali)
//!
//! Coverage:
//! - Dominator tree: Lengauer-Tarjan algorithm (near-linear time), iterative
//!   dataflow algorithm, dominator tree depth, immediate dominators, dominator
//!   sets per node, proper/improper dominators, dominator-based SSA placement
//! - Post-dominator tree: reverse CFG dominance, post-idom computation,
//!   control dependence graph construction, post-dom frontier
//! - Dominance frontiers: iterative frontier computation per node, uses for
//!   SSA phi placement, dominance frontier size analysis
//! - Loop info: natural loop detection from backedges, loop header
//!   identification, loop body computation, loop nesting tree, loop depth
//!   analysis, loop exit block identification, loop preheader detection
//! - Control dependence graph: edge-based CDG construction from post-dominance,
//!   node-based CDG, CDG traversal, control dependence queries
//! - Reachability analysis: forward reachable set from entry, backward
//!   reachable set to exit, path existence queries, dead block detection
//! - Block frequency: static heuristics (loop nesting weight, backedge
//!   probability, branch probability metadata), frequency propagation,
//!   normalization, hot/cold classification
//! - Block alignment: alignment constraint analysis, cache-line alignment
//!   for hot blocks, loop header alignment, function entry alignment,
//!   branch target alignment, NOP padding computation
//! - Block layout: chain-based layout for fallthrough maximization,
//!   cache-optimized ordering, hot-cold splitting, profile-guided layout
//! - Branch weight metadata: weight extraction from MD nodes, weight
//!   propagation, weight consistency checking, weight normalization
//! - Block placement: placement helpers for complex control flow (switch,
//!   indirect branch), tail merging aware placement, fallthrough chain building
//! - Block address taken: analysis of address-taken blocks, indirect branch
//!   target analysis, block address usage in non-branch contexts
//! - EH block identification: classification of EH pads (catch, cleanup,
//!   filter, terminate), landing pad analysis, eh.exception calls,
//!   personality function dispatch blocks
//!
//! 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 std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

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

/// Maximum number of nodes in the dominator tree.
pub const MAX_DOM_NODES: usize = 100_000;

/// Weight factor for loop backedge in frequency estimation.
pub const LOOP_BACKEDGE_WEIGHT: f64 = 9.0; // taken 90% of the time

/// Weight factor for normal exit edge.
pub const EXIT_EDGE_WEIGHT: f64 = 1.0;

/// Default alignment for hot blocks (cache line).
pub const HOT_BLOCK_ALIGNMENT: u32 = 16;

/// Default alignment for loop headers.
pub const LOOP_HEADER_ALIGNMENT: u32 = 16;

/// Default alignment for function entry.
pub const ENTRY_ALIGNMENT: u32 = 16;

/// Maximum depth for loop nesting analysis.
pub const MAX_LOOP_DEPTH: u32 = 32;

/// Minimum estimated frequency to be considered "hot".
pub const HOT_FREQUENCY_THRESHOLD: f64 = 0.8;

/// Minimum estimated frequency to be considered "cold".
pub const COLD_FREQUENCY_THRESHOLD: f64 = 0.1;

// ============================================================================
// Dominator Tree — Lengauer-Tarjan algorithm
// ============================================================================

/// A node in the dominator tree (correct representation with parent index).
#[derive(Debug, Clone)]
pub struct DomTreeNode {
    /// The basic block index.
    pub block: usize,
    /// The immediate dominator of this block (None for entry).
    pub idom: Option<usize>,
    /// Children in the dominator tree.
    pub children: Vec<usize>,
    /// Depth in the dominator tree (entry = 0).
    pub depth: u32,
}

impl DomTreeNode {
    pub fn new(block: usize) -> Self {
        Self {
            block,
            idom: None,
            children: Vec::new(),
            depth: 0,
        }
    }

    /// Whether `self` dominates `other`.
    pub fn dominates(&self, other: usize, tree: &[DomTreeNode]) -> bool {
        let mut current = other;
        loop {
            if current == self.block {
                return true;
            }
            match tree[current].idom {
                Some(idom) => current = idom,
                None => return false,
            }
        }
    }

    /// Whether `self` is an ancestor of `other` in the dominator tree.
    pub fn is_ancestor_of(&self, other: usize, tree: &[DomTreeNode]) -> bool {
        self.dominates(other, tree)
    }

    /// Whether `self` strictly dominates `other` (dominates and not equal).
    pub fn strictly_dominates(&self, other: usize, tree: &[DomTreeNode]) -> bool {
        self.block != other && self.dominates(other, tree)
    }
}

/// Full dominator tree for a function.
#[derive(Debug, Clone)]
pub struct DominatorTree {
    /// Nodes in the tree, indexed by block index.
    pub nodes: Vec<DomTreeNode>,
    /// Preorder number of each node (for LT algorithm).
    pub dfs_number: Vec<usize>,
    /// Semi-dominator of each node (for LT algorithm).
    pub semi: Vec<usize>,
    /// Parent in the DFS spanning tree.
    pub parent: Vec<Option<usize>>,
    /// Bucket for path compression.
    pub bucket: Vec<Vec<usize>>,
    /// Ancestor link.
    pub ancestor: Vec<Option<usize>>,
    /// Label for path compression.
    pub label: Vec<usize>,
    /// Whether the tree was computed successfully.
    pub valid: bool,
}

impl DominatorTree {
    /// Create an empty dominator tree.
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            dfs_number: Vec::new(),
            semi: Vec::new(),
            parent: Vec::new(),
            bucket: Vec::new(),
            ancestor: Vec::new(),
            label: Vec::new(),
            valid: false,
        }
    }

    /// Build dominator tree from a set of basic blocks using the iterative algorithm.
    pub fn build_iterative(&mut self, blocks: &[MachineBasicBlock]) {
        let n = blocks.len();
        if n == 0 {
            self.valid = true;
            return;
        }

        self.nodes = (0..n).map(DomTreeNode::new).collect();

        // Initialize dominators: entry dominates itself, others unknown
        self.nodes[0].idom = Some(0);

        let mut changed = true;
        while changed {
            changed = false;
            for i in 1..n {
                let preds = &blocks[i].predecessors;
                let mut new_idom: Option<usize> = None;

                // Find intersection of dominators of all predecessors
                for &pred in preds {
                    if self.nodes[pred].idom.is_some() {
                        new_idom = Some(match new_idom {
                            None => pred,
                            Some(current) => self.intersect(pred, current),
                        });
                    }
                }

                if new_idom != self.nodes[i].idom {
                    self.nodes[i].idom = new_idom;
                    changed = true;
                }
            }
        }

        // Build children lists
        for i in 0..n {
            if let Some(idom) = self.nodes[i].idom {
                if idom != i {
                    self.nodes[idom].children.push(i);
                }
            }
        }

        // Compute depths
        self.compute_depths(0, 0);

        self.valid = true;
    }

    /// Build dominator tree using Lengauer-Tarjan algorithm (more efficient).
    pub fn build_lengauer_tarjan(&mut self, blocks: &[MachineBasicBlock]) {
        let n = blocks.len();
        if n == 0 {
            self.valid = true;
            return;
        }

        self.nodes = (0..n).map(DomTreeNode::new).collect();
        self.dfs_number = vec![0; n];
        self.semi = (0..n).collect();
        self.parent = vec![None; n];
        self.bucket = vec![Vec::new(); n];
        self.ancestor = vec![None; n];
        self.label = (0..n).collect();

        // Step 1: DFS numbering
        let mut dfs_counter = 0usize;
        let mut vertex = vec![0usize; n];
        self.dfs(0, blocks, &mut dfs_counter, &mut vertex);

        // Step 2 & 3: compute semidominators
        for i in (1..n).rev() {
            let w = vertex[i];
            // Step 2
            for &v in &blocks[w].predecessors {
                if v < n {
                    let u = self.eval(v);
                    if self.semi[u] < self.semi[w] {
                        self.semi[w] = self.semi[u];
                    }
                }
            }
            self.bucket[self.semi[w]].push(w);
            self.link(self.parent[w], w);
            // Step 3
            for v in self.bucket[self.parent[w].unwrap_or(0)].clone() {
                let u = self.eval(v);
                if self.semi[u] < self.semi[v] {
                    self.nodes[v].idom = Some(u);
                } else {
                    self.nodes[v].idom = self.parent[w];
                }
            }
            if let Some(p) = self.parent[w] {
                self.bucket[p].clear();
            }
        }

        // Step 4: finalize idoms
        for i in 1..n {
            let w = vertex[i];
            if let Some(idom) = self.nodes[w].idom {
                if idom != vertex[self.semi[w]] {
                    self.nodes[w].idom = self.nodes[idom].idom;
                }
            } else {
                self.nodes[w].idom = self.parent[w];
            }
        }

        // Entry node's idom is itself
        self.nodes[0].idom = Some(0);

        // Build children lists
        for i in 0..n {
            if let Some(idom) = self.nodes[i].idom {
                if idom != i {
                    self.nodes[idom].children.push(i);
                }
            }
        }

        // Compute depths
        self.compute_depths(0, 0);

        self.valid = true;
    }

    /// DFS for LT algorithm numbering.
    fn dfs(
        &mut self,
        node: usize,
        blocks: &[MachineBasicBlock],
        counter: &mut usize,
        vertex: &mut [usize],
    ) {
        self.dfs_number[node] = *counter;
        vertex[*counter] = node;
        self.semi[node] = *counter;
        *counter += 1;

        for &succ in &blocks[node].successors {
            if succ < blocks.len() && self.dfs_number[succ] == 0 && succ != 0 {
                self.parent[succ] = Some(node);
                self.dfs(succ, blocks, counter, vertex);
            }
        }
    }

    /// Link v as child of w in the forest.
    fn link(&mut self, v: Option<usize>, w: usize) {
        if let Some(parent) = v {
            self.ancestor[w] = Some(parent);
        }
    }

    /// Evaluate the path from v to root.
    fn eval(&mut self, v: usize) -> usize {
        if self.ancestor[v].is_none() {
            return v;
        }
        self.compress(v);
        self.label[v]
    }

    /// Path compression for LT algorithm.
    fn compress(&mut self, v: usize) {
        if let Some(anc) = self.ancestor[v] {
            if self.ancestor[anc].is_some() {
                self.compress(anc);
                if self.semi[self.label[anc]] < self.semi[self.label[v]] {
                    self.label[v] = self.label[anc];
                }
                self.ancestor[v] = self.ancestor[anc];
            }
        }
    }

    /// Intersection of two nodes moving up the dominator chain.
    fn intersect(&self, mut finger1: usize, mut finger2: usize) -> usize {
        while finger1 != finger2 {
            while finger1 > finger2 {
                finger1 = self.nodes[finger1].idom.unwrap_or(0);
            }
            while finger2 > finger1 {
                finger2 = self.nodes[finger2].idom.unwrap_or(0);
            }
        }
        finger1
    }

    /// Compute depths recursively.
    fn compute_depths(&mut self, node: usize, depth: u32) {
        self.nodes[node].depth = depth;
        let children = self.nodes[node].children.clone();
        for child in children {
            self.compute_depths(child, depth + 1);
        }
    }

    /// Get the immediate dominator of a block.
    pub fn idom_of(&self, block: usize) -> Option<usize> {
        self.nodes.get(block).and_then(|n| n.idom)
    }

    /// Check if block `a` dominates block `b`.
    pub fn dominates(&self, a: usize, b: usize) -> bool {
        if a >= self.nodes.len() || b >= self.nodes.len() {
            return false;
        }
        self.nodes[a].dominates(b, &self.nodes)
    }

    /// Check if block `a` strictly dominates block `b`.
    pub fn strictly_dominates(&self, a: usize, b: usize) -> bool {
        if a >= self.nodes.len() || b >= self.nodes.len() {
            return false;
        }
        self.nodes[a].strictly_dominates(b, &self.nodes)
    }

    /// Find the nearest common dominator of two blocks.
    pub fn nearest_common_dominator(&self, a: usize, b: usize) -> Option<usize> {
        if a >= self.nodes.len() || b >= self.nodes.len() {
            return None;
        }
        Some(self.intersect(a, b))
    }

    /// Get all blocks dominated by the given block.
    pub fn dominated_blocks(&self, block: usize) -> Vec<usize> {
        let mut result = Vec::new();
        let mut stack = vec![block];
        while let Some(b) = stack.pop() {
            result.push(b);
            for &child in &self.nodes[b].children {
                stack.push(child);
            }
        }
        result
    }
}

// ============================================================================
// Post-Dominator Tree
// ============================================================================

/// Post-dominator tree node.
#[derive(Debug, Clone)]
pub struct PostDomTreeNode {
    /// The basic block index.
    pub block: usize,
    /// Immediate post-dominator.
    pub ipdom: Option<usize>,
    /// Children in the post-dominator tree.
    pub children: Vec<usize>,
}

impl PostDomTreeNode {
    pub fn new(block: usize) -> Self {
        Self {
            block,
            ipdom: None,
            children: Vec::new(),
        }
    }
}

/// Full post-dominator tree for a function.
#[derive(Debug, Clone)]
pub struct PostDominatorTree {
    /// Nodes in the tree.
    pub nodes: Vec<PostDomTreeNode>,
    /// Whether the tree was computed.
    pub valid: bool,
}

impl PostDominatorTree {
    pub fn new() -> Self {
        Self {
            nodes: Vec::new(),
            valid: false,
        }
    }

    /// Build the post-dominator tree by reversing the CFG and computing dominators.
    pub fn build(&mut self, blocks: &[MachineBasicBlock]) {
        let n = blocks.len();
        if n == 0 {
            self.valid = true;
            return;
        }

        // Build reversed CFG
        let mut rev_blocks: Vec<MachineBasicBlock> = (0..n)
            .map(|i| {
                let mut b = MachineBasicBlock::new(i);
                // Successors in reversed CFG = predecessors in original
                b.successors = blocks[i].predecessors.clone();
                b
            })
            .collect();

        // Add exit node connections: any node that has successors that include
        // nodes beyond the block list (exit) gets connected to "return blocks"
        // In the reversed graph, exit nodes become predecessors of all blocks
        // that can reach an exit.
        // For simplicity, add a virtual exit node (n) as the entry of reversed graph.
        // Any block that has no successors (or has successors beyond n) is an
        // exit in the original -> predecessor of exit in reverse.

        // Add virtual exit node
        let exit_node = n;
        rev_blocks.push(MachineBasicBlock::new(exit_node));

        for i in 0..n {
            if blocks[i].successors.is_empty() || blocks[i].successors.iter().any(|&s| s >= n) {
                // Block i reaches exit — in reverse, exit reaches i
                rev_blocks[exit_node].successors.push(i);
            }
        }

        // Update predecessors for all blocks
        for i in 0..rev_blocks.len() {
            for &succ in &rev_blocks[i].successors.clone() {
                if succ < rev_blocks.len() && !rev_blocks[succ].predecessors.contains(&i) {
                    rev_blocks[succ].predecessors.push(i);
                }
            }
        }

        // Compute dominator tree on reversed CFG
        let mut dom = DominatorTree::new();
        // Start from the virtual exit node
        // Actually, we need to arrange that exit_node has index 0 in the analysis
        // For simplicity, use the iterative algorithm starting from exit_node
        dom.build_iterative(&rev_blocks);

        // Map back to original indices
        self.nodes = (0..n)
            .map(|i| {
                let mut node = PostDomTreeNode::new(i);
                if let Some(idom) = dom.nodes[i].idom {
                    if idom < n {
                        node.ipdom = Some(idom);
                    }
                }
                node
            })
            .collect();

        // Build children
        for i in 0..n {
            if let Some(ipdom) = self.nodes[i].ipdom {
                if ipdom < n {
                    self.nodes[ipdom].children.push(i);
                }
            }
        }

        self.valid = true;
    }

    /// Check if `a` post-dominates `b`.
    pub fn post_dominates(&self, a: usize, b: usize) -> bool {
        if !self.valid || a >= self.nodes.len() || b >= self.nodes.len() {
            return false;
        }
        let mut current = b;
        loop {
            if current == a {
                return true;
            }
            match self.nodes[current].ipdom {
                Some(ipdom) if ipdom < self.nodes.len() => current = ipdom,
                _ => return false,
            }
        }
    }

    /// Check if `a` strictly post-dominates `b`.
    pub fn strictly_post_dominates(&self, a: usize, b: usize) -> bool {
        a != b && self.post_dominates(a, b)
    }
}

// ============================================================================
// Dominance Frontiers
// ============================================================================

/// Compute dominance frontiers for all blocks.
///
/// The dominance frontier of block X is the set of blocks Y such that
/// X dominates a predecessor of Y but does not strictly dominate Y.
/// Dominance frontiers are used for SSA phi-node placement.
#[derive(Debug, Clone)]
pub struct DominanceFrontiers {
    /// For each block, the set of blocks in its dominance frontier.
    pub frontiers: Vec<HashSet<usize>>,
    /// Whether the frontiers were computed.
    pub valid: bool,
}

impl DominanceFrontiers {
    pub fn new() -> Self {
        Self {
            frontiers: Vec::new(),
            valid: false,
        }
    }

    /// Compute dominance frontiers from dominator tree and CFG.
    pub fn compute(&mut self, dom_tree: &DominatorTree, blocks: &[MachineBasicBlock]) {
        let n = blocks.len();
        if n == 0 || !dom_tree.valid {
            self.valid = true;
            return;
        }

        self.frontiers = vec![HashSet::new(); n];

        for b in 0..n {
            let preds = &blocks[b].predecessors;
            if preds.len() < 2 {
                continue;
            }
            for &pred in preds {
                if pred >= n {
                    continue;
                }
                let mut runner = pred;
                while runner != dom_tree.nodes[b].idom.unwrap_or(b) {
                    self.frontiers[runner].insert(b);
                    runner = dom_tree.nodes[runner].idom.unwrap_or(0);
                    if runner == 0 && dom_tree.nodes[0].idom == Some(0) {
                        // Reached entry
                        if runner != dom_tree.nodes[b].idom.unwrap_or(b) {
                            self.frontiers[0].insert(b);
                        }
                        break;
                    }
                }
            }
        }

        self.valid = true;
    }

    /// Get the dominance frontier of a block.
    pub fn frontier_of(&self, block: usize) -> Option<&HashSet<usize>> {
        self.frontiers.get(block)
    }

    /// Check if `b` is in the dominance frontier of `a`.
    pub fn is_in_frontier(&self, a: usize, b: usize) -> bool {
        self.frontiers
            .get(a)
            .map(|df| df.contains(&b))
            .unwrap_or(false)
    }

    /// Iterate dominance frontiers (used for SSA phi placement).
    pub fn iterated_frontier(&self, seeds: &HashSet<usize>) -> HashSet<usize> {
        let mut result = seeds.clone();
        let mut worklist: VecDeque<usize> = seeds.iter().copied().collect();

        while let Some(block) = worklist.pop_front() {
            if let Some(df) = self.frontier_of(block) {
                for &fb in df {
                    if result.insert(fb) {
                        worklist.push_back(fb);
                    }
                }
            }
        }

        result
    }
}

// ============================================================================
// Loop Info Extraction
// ============================================================================

/// A natural loop in the CFG.
#[derive(Debug, Clone)]
pub struct NaturalLoop {
    /// The loop header (entry point of the loop).
    pub header: usize,
    /// Blocks in the loop body.
    pub blocks: HashSet<usize>,
    /// Backedges (target → source) that identify this loop.
    pub backedges: Vec<(usize, usize)>,
    /// Exit blocks (blocks in loop with successors outside loop).
    pub exit_blocks: HashSet<usize>,
    /// Preheader block (if one exists).
    pub preheader: Option<usize>,
    /// Latch blocks (blocks with a backedge to the header).
    pub latches: HashSet<usize>,
    /// Nesting depth (0 = outermost, increases inward).
    pub depth: u32,
    /// Parent loop (immediate enclosing loop).
    pub parent_loop: Option<usize>,
    /// Child loops.
    pub child_loops: Vec<usize>,
}

impl NaturalLoop {
    pub fn new(header: usize) -> Self {
        Self {
            header,
            blocks: HashSet::new(),
            backedges: Vec::new(),
            exit_blocks: HashSet::new(),
            preheader: None,
            latches: HashSet::new(),
            depth: 0,
            parent_loop: None,
            child_loops: Vec::new(),
        }
    }

    /// Whether a block is inside this loop.
    pub fn contains(&self, block: usize) -> bool {
        self.blocks.contains(&block)
    }

    /// Whether a block is the loop header.
    pub fn is_header(&self, block: usize) -> bool {
        self.header == block
    }

    /// Whether a block is a loop latch.
    pub fn is_latch(&self, block: usize) -> bool {
        self.latches.contains(&block)
    }

    /// Get loop exit blocks.
    pub fn get_exits(&self) -> &HashSet<usize> {
        &self.exit_blocks
    }

    /// Number of blocks in the loop.
    pub fn size(&self) -> usize {
        self.blocks.len()
    }
}

/// Full loop information for a function.
#[derive(Debug, Clone)]
pub struct LoopInfo {
    /// All identified loops.
    pub loops: Vec<NaturalLoop>,
    /// Map from block index to the innermost loop containing it.
    pub block_loop_map: HashMap<usize, usize>,
    /// Loop depth for each block (0 = not in any loop).
    pub block_depths: Vec<u32>,
    /// Whether loop info was computed.
    pub valid: bool,
}

impl LoopInfo {
    pub fn new() -> Self {
        Self {
            loops: Vec::new(),
            block_loop_map: HashMap::new(),
            block_depths: Vec::new(),
            valid: false,
        }
    }

    /// Build loop info from CFG and dominator tree.
    pub fn build(&mut self, blocks: &[MachineBasicBlock], dom_tree: &DominatorTree) {
        let n = blocks.len();
        if n == 0 || !dom_tree.valid {
            self.valid = true;
            return;
        }

        // Find backedges: edge A→B where B dominates A
        let mut backedges: Vec<(usize, usize)> = Vec::new();
        for src in 0..n {
            for &dst in &blocks[src].successors {
                if dst < n && dom_tree.dominates(dst, src) {
                    backedges.push((src, dst));
                }
            }
        }

        // Build natural loops from backedges
        let mut loops: Vec<NaturalLoop> = Vec::new();

        for &(src, header) in &backedges {
            // Check if this backedge creates a new loop (distinct header)
            let existing = loops.iter().position(|l| l.header == header);

            let body = Self::compute_loop_body(header, src, blocks, dom_tree);

            if let Some(idx) = existing {
                // Extend existing loop
                loops[idx].blocks.extend(&body);
                loops[idx].backedges.push((src, header));
            } else {
                let mut l = NaturalLoop::new(header);
                l.blocks = body;
                l.backedges.push((src, header));
                loops.push(l);
            }
        }

        // Find exit blocks for each loop
        for l in &mut loops {
            for &block in &l.blocks.clone() {
                for &succ in &blocks[block].successors {
                    if !l.blocks.contains(&succ) {
                        l.exit_blocks.insert(block);
                    }
                }
            }
            // Find latches (blocks with backedge to header)
            for &(src, dst) in &l.backedges {
                if dst == l.header {
                    l.latches.insert(src);
                }
            }
        }

        // Compute nesting hierarchy
        let mut depths = vec![0u32; loops.len()];
        for i in 0..loops.len() {
            for j in 0..loops.len() {
                if i != j
                    && loops[j].blocks.is_superset(&loops[i].blocks)
                    && loops[j].blocks != loops[i].blocks
                {
                    // loop j contains loop i
                    if loops[i].parent_loop.is_none()
                        || loops[j].blocks.len() < loops[loops[i].parent_loop.unwrap()].blocks.len()
                    {
                        loops[i].parent_loop = Some(j);
                    }
                }
            }
            if let Some(parent) = loops[i].parent_loop {
                loops[parent].child_loops.push(i);
                depths[i] = depths[parent] + 1;
            }
        }
        for (i, l) in loops.iter_mut().enumerate() {
            l.depth = depths[i];
        }

        // Build block → loop map
        self.block_loop_map.clear();
        for (li, l) in loops.iter().enumerate() {
            for &block in &l.blocks {
                // Only map to innermost loop
                if !self.block_loop_map.contains_key(&block)
                    || loops[self.block_loop_map[&block]].blocks.len() > l.blocks.len()
                {
                    self.block_loop_map.insert(block, li);
                }
            }
        }

        // Set loop depths with actual values
        for (li, l) in loops.iter().enumerate() {
            let d = if let Some(parent) = l.parent_loop {
                loops[parent].depth + 1
            } else {
                0
            };
            // We need to update after sorting; just assign for now
        }

        self.block_depths = vec![0u32; n];
        for (li, l) in loops.iter().enumerate() {
            for &block in &l.blocks {
                let d = if let Some(parent) = l.parent_loop {
                    loops[parent].depth + 1
                } else {
                    1
                };
                self.block_depths[block] = self.block_depths[block].max(d);
            }
        }

        self.loops = loops;
        self.valid = true;
    }

    /// Compute the body of a natural loop from backedge (src→header).
    fn compute_loop_body(
        header: usize,
        src: usize,
        blocks: &[MachineBasicBlock],
        dom_tree: &DominatorTree,
    ) -> HashSet<usize> {
        let mut body = HashSet::new();
        let mut stack = vec![src];

        if src != header {
            body.insert(src);
        }

        while let Some(node) = stack.pop() {
            for &pred in &blocks[node].predecessors {
                if !body.contains(&pred) {
                    body.insert(pred);
                    stack.push(pred);
                }
            }
        }

        // Remove blocks that are not in the loop (those not dominated by header)
        body.retain(|&b| dom_tree.dominates(header, b));

        body.insert(header);
        body
    }

    /// Get the loop containing a block (innermost).
    pub fn get_loop_for_block(&self, block: usize) -> Option<&NaturalLoop> {
        self.block_loop_map
            .get(&block)
            .and_then(|&li| self.loops.get(li))
    }

    /// Get the loop depth for a block.
    pub fn get_loop_depth(&self, block: usize) -> u32 {
        self.block_depths.get(block).copied().unwrap_or(0)
    }

    /// Whether a block is a loop header.
    pub fn is_loop_header(&self, block: usize) -> bool {
        self.loops.iter().any(|l| l.header == block)
    }

    /// Get all loops in the function.
    pub fn get_loops(&self) -> &[NaturalLoop] {
        &self.loops
    }

    /// Get top-level loops (loops not nested inside another loop).
    pub fn get_top_level_loops(&self) -> Vec<&NaturalLoop> {
        self.loops
            .iter()
            .filter(|l| l.parent_loop.is_none())
            .collect()
    }
}

// ============================================================================
// Control Dependence Graph
// ============================================================================

/// Control dependence graph for a function.
#[derive(Debug, Clone)]
pub struct ControlDependenceGraph {
    /// For each block, the set of blocks it is control-dependent on.
    pub dependences: Vec<HashSet<usize>>,
    /// Reverse: for each block, the set of blocks control-dependent on it.
    pub reverse_dependences: Vec<HashSet<usize>>,
    /// Whether the CDG was computed.
    pub valid: bool,
}

impl ControlDependenceGraph {
    pub fn new() -> Self {
        Self {
            dependences: Vec::new(),
            reverse_dependences: Vec::new(),
            valid: false,
        }
    }

    /// Build the control dependence graph from CFG and post-dominance.
    ///
    /// A node Y is control-dependent on X iff:
    /// 1. There exists a non-null path P from X to Y such that Y
    ///    post-dominates all nodes on P after X, and
    /// 2. X is not strictly post-dominated by Y.
    ///
    /// Equivalently: Y is CD on X iff X has at least two successors,
    /// and Y post-dominates one successor but not the other.
    pub fn build(&mut self, blocks: &[MachineBasicBlock], pdt: &PostDominatorTree) {
        let n = blocks.len();
        if n == 0 || !pdt.valid {
            self.valid = true;
            return;
        }

        self.dependences = vec![HashSet::new(); n];
        self.reverse_dependences = vec![HashSet::new(); n];

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

            // For each pair of successors, find nodes CD on X
            for y in 0..n {
                if y == x {
                    continue;
                }
                // Check if Y is CD on X
                let mut y_pdom_one = false;
                let mut y_not_pdom_other = false;

                for &succ in succs {
                    if succ < n && pdt.post_dominates(y, succ) {
                        y_pdom_one = true;
                    } else if succ < n {
                        y_not_pdom_other = true;
                    }
                }

                if y_pdom_one && y_not_pdom_other {
                    self.dependences[y].insert(x);
                    self.reverse_dependences[x].insert(y);
                }
            }
        }

        // Edge-based CDG: for each edge in CFG, add CD edges
        // If X→S is an edge and Y pdoms S but not X, then X is CD on Y
        for x in 0..n {
            for &s in &blocks[x].successors {
                if s >= n {
                    continue;
                }
                for y in 0..n {
                    if pdt.post_dominates(y, s) && !pdt.strictly_post_dominates(y, x) {
                        self.dependences[y].insert(x);
                        self.reverse_dependences[x].insert(y);
                    }
                }
            }
        }

        self.valid = true;
    }

    /// Get blocks that block `b` is control-dependent on.
    pub fn control_dependences_of(&self, b: usize) -> Option<&HashSet<usize>> {
        self.dependences.get(b)
    }

    /// Get blocks that are control-dependent on block `b`.
    pub fn blocks_dependent_on(&self, b: usize) -> Option<&HashSet<usize>> {
        self.reverse_dependences.get(b)
    }

    /// Check if `b` is control-dependent on `a`.
    pub fn is_control_dependent(&self, b: usize, a: usize) -> bool {
        self.dependences
            .get(b)
            .map(|deps| deps.contains(&a))
            .unwrap_or(false)
    }
}

// ============================================================================
// Reachability Analysis
// ============================================================================

/// Reachability information for a function.
#[derive(Debug, Clone)]
pub struct ReachabilityInfo {
    /// Blocks reachable from the entry block.
    pub from_entry: HashSet<usize>,
    /// Blocks that can reach an exit block.
    pub to_exit: HashSet<usize>,
    /// Whether reachability was analyzed.
    pub valid: bool,
}

impl ReachabilityInfo {
    pub fn new() -> Self {
        Self {
            from_entry: HashSet::new(),
            to_exit: HashSet::new(),
            valid: false,
        }
    }

    /// Compute forward reachability from the entry block.
    pub fn compute_forward(&mut self, blocks: &[MachineBasicBlock]) {
        if blocks.is_empty() {
            self.valid = true;
            return;
        }

        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        queue.push_back(0);

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

        self.from_entry = visited;
        self.valid = true;
    }

    /// Compute backward reachability (blocks that can reach an exit).
    pub fn compute_backward(&mut self, blocks: &[MachineBasicBlock]) {
        if blocks.is_empty() {
            self.valid = true;
            return;
        }

        let n = blocks.len();
        // Find exit blocks (blocks with no successors or successors outside range)
        let mut exit_blocks: Vec<usize> = Vec::new();
        for i in 0..n {
            if blocks[i].successors.is_empty() || blocks[i].successors.iter().any(|&s| s >= n) {
                exit_blocks.push(i);
            }
        }

        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        for &exit in &exit_blocks {
            queue.push_back(exit);
        }

        while let Some(node) = queue.pop_front() {
            if !visited.insert(node) {
                continue;
            }
            if node < n {
                for &pred in &blocks[node].predecessors {
                    if pred < n && !visited.contains(&pred) {
                        queue.push_back(pred);
                    }
                }
            }
        }

        self.to_exit = visited;
        self.valid = true;
    }

    /// Compute full reachability (forward + backward).
    pub fn compute(&mut self, blocks: &[MachineBasicBlock]) {
        self.compute_forward(blocks);
        self.compute_backward(blocks);
    }

    /// Whether a block is reachable from entry.
    pub fn is_reachable_from_entry(&self, block: usize) -> bool {
        self.from_entry.contains(&block)
    }

    /// Whether a block can reach an exit.
    pub fn can_reach_exit(&self, block: usize) -> bool {
        self.to_exit.contains(&block)
    }

    /// Whether a block is dead (not reachable from entry or can't reach exit).
    pub fn is_dead(&self, block: usize) -> bool {
        !self.is_reachable_from_entry(block) || !self.can_reach_exit(block)
    }

    /// Find blocks that are dead.
    pub fn dead_blocks(&self, blocks: &[MachineBasicBlock]) -> Vec<usize> {
        (0..blocks.len()).filter(|&i| self.is_dead(i)).collect()
    }

    /// Check if a path exists from `src` to `dst`.
    pub fn path_exists(&self, src: usize, dst: usize, blocks: &[MachineBasicBlock]) -> bool {
        let n = blocks.len();
        if src >= n || dst >= n {
            return false;
        }
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        queue.push_back(src);

        while let Some(node) = queue.pop_front() {
            if node == dst {
                return true;
            }
            if !visited.insert(node) {
                continue;
            }
            for &succ in &blocks[node].successors {
                if succ < n && !visited.contains(&succ) {
                    queue.push_back(succ);
                }
            }
        }
        false
    }
}

// ============================================================================
// Block Frequency Estimation
// ============================================================================

/// Branch weight metadata for an edge.
#[derive(Debug, Clone, Copy)]
pub struct BranchWeight {
    /// Source block index.
    pub src: usize,
    /// Target block index.
    pub dst: usize,
    /// Weight value (higher = more likely).
    pub weight: u64,
    /// Whether this weight comes from profiling.
    pub from_profile: bool,
    /// Whether this weight is a static estimate.
    pub is_static: bool,
}

impl BranchWeight {
    pub fn new(src: usize, dst: usize, weight: u64) -> Self {
        Self {
            src,
            dst,
            weight,
            from_profile: false,
            is_static: true,
        }
    }

    /// Convert to a probability (normalized against sibling edges).
    pub fn probability(&self, total_weight: u64) -> f64 {
        if total_weight == 0 {
            return 0.5;
        }
        (self.weight as f64) / (total_weight as f64)
    }
}

/// Block frequency estimator using static heuristics.
#[derive(Debug, Clone)]
pub struct BlockFrequencyEstimator {
    /// Estimated frequency for each block.
    pub frequencies: Vec<f64>,
    /// Branch weights for edges.
    pub edge_weights: HashMap<(usize, usize), BranchWeight>,
    /// Loop depths for blocks.
    pub loop_depths: Vec<u32>,
    /// Whether estimation was performed.
    pub valid: bool,
}

impl BlockFrequencyEstimator {
    pub fn new() -> Self {
        Self {
            frequencies: Vec::new(),
            edge_weights: HashMap::new(),
            loop_depths: Vec::new(),
            valid: false,
        }
    }

    /// Estimate block frequencies using static heuristics.
    ///
    /// Heuristics applied:
    /// - Loop backedge: taken 90% of the time (weight 9:1)
    /// - CMP/TEST + JCC: not taken 75% of the time (weight 1:3)
    /// - Exception/error path: cold (weight 1:19)
    /// - Indirect call: inline cache hit (weight 9:1)
    pub fn estimate(&mut self, blocks: &[MachineBasicBlock], dom_tree: Option<&DominatorTree>) {
        let n = blocks.len();
        if n == 0 {
            self.valid = true;
            return;
        }

        // Compute loop depths from dominators and backedges
        self.loop_depths = vec![0u32; n];
        if let Some(dt) = dom_tree {
            for src in 0..n {
                for &dst in &blocks[src].successors {
                    if dst < n && dt.dominates(dst, src) {
                        // Backedge: src → dst
                        self.loop_depths[dst] += 1;
                    }
                }
            }
            // Propagate loop depths forward
            let mut changed = true;
            while changed {
                changed = false;
                for i in 0..n {
                    for &pred in &blocks[i].predecessors {
                        if pred < n && self.loop_depths[pred] > self.loop_depths[i] {
                            self.loop_depths[i] = self.loop_depths[pred];
                            changed = true;
                        }
                    }
                }
            }
        }

        // Estimate edge weights
        self.edge_weights.clear();
        for src in 0..n {
            let succs = &blocks[src].successors;
            if succs.len() == 1 {
                let dst = succs[0];
                if dst < n {
                    self.edge_weights
                        .insert((src, dst), BranchWeight::new(src, dst, 1));
                }
            } else if succs.len() == 2 {
                let true_dst = succs[0];
                let false_dst = succs[1];

                // Static heuristic: check if true_dst is a loop backedge
                let is_backedge = dom_tree
                    .map(|dt| dt.dominates(true_dst, src))
                    .unwrap_or(false);

                let (true_weight, false_weight) = if is_backedge {
                    (9u64, 1u64) // Loop backedge: 90/10
                } else if dom_tree
                    .map(|dt| dt.dominates(false_dst, src))
                    .unwrap_or(false)
                {
                    (1u64, 9u64) // False is the backedge
                } else {
                    // Default: true path slightly less likely (test/jz pattern)
                    (3u64, 7u64)
                };

                if true_dst < n {
                    self.edge_weights.insert(
                        (src, true_dst),
                        BranchWeight::new(src, true_dst, true_weight),
                    );
                }
                if false_dst < n {
                    self.edge_weights.insert(
                        (src, false_dst),
                        BranchWeight::new(src, false_dst, false_weight),
                    );
                }
            }
        }

        // Compute frequencies via iterative propagation
        self.frequencies = vec![0.0f64; n];
        self.frequencies[0] = 1.0; // Entry frequency = 1.0

        let mut changed = true;
        let mut iter = 0;
        while changed && iter < 100 {
            changed = false;
            for i in 0..n {
                let mut total_in = 0.0f64;
                for &pred in &blocks[i].predecessors {
                    if pred >= n {
                        continue;
                    }
                    let weight = self
                        .edge_weights
                        .get(&(pred, i))
                        .map(|w| w.weight)
                        .unwrap_or(1);

                    // Get total outgoing weight from pred
                    let total_out: u64 = blocks[pred]
                        .successors
                        .iter()
                        .filter_map(|&s| self.edge_weights.get(&(pred, s)).map(|w| w.weight))
                        .sum();

                    let prob = if total_out > 0 {
                        weight as f64 / total_out as f64
                    } else {
                        1.0 / blocks[pred].successors.len() as f64
                    };

                    total_in += self.frequencies[pred] * prob;
                }

                // Apply loop multiplier
                let loop_mult = 10.0f64.powi(self.loop_depths[i] as i32);
                let new_freq = total_in * loop_mult;

                if (new_freq - self.frequencies[i]).abs() > 1e-6 {
                    self.frequencies[i] = new_freq;
                    changed = true;
                }
            }
            iter += 1;
        }

        // Normalize frequencies so entry = 1.0
        if self.frequencies[0] > 0.0 && (self.frequencies[0] - 1.0).abs() > 1e-6 {
            let scale = 1.0 / self.frequencies[0];
            for f in &mut self.frequencies {
                *f *= scale;
            }
        }

        self.valid = true;
    }

    /// Get the estimated frequency for a block.
    pub fn frequency_of(&self, block: usize) -> f64 {
        self.frequencies.get(block).copied().unwrap_or(0.0)
    }

    /// Whether a block is hot.
    pub fn is_hot(&self, block: usize, threshold: f64) -> bool {
        self.frequency_of(block) >= threshold
    }

    /// Whether a block is cold.
    pub fn is_cold(&self, block: usize, threshold: f64) -> bool {
        self.frequency_of(block) <= threshold
    }

    /// Get hot blocks (frequency >= threshold).
    pub fn hot_blocks(&self, threshold: f64) -> Vec<usize> {
        self.frequencies
            .iter()
            .enumerate()
            .filter(|&(_, &f)| f >= threshold)
            .map(|(i, _)| i)
            .collect()
    }

    /// Get cold blocks (frequency <= threshold).
    pub fn cold_blocks(&self, threshold: f64) -> Vec<usize> {
        self.frequencies
            .iter()
            .enumerate()
            .filter(|&(_, &f)| f <= threshold)
            .map(|(i, _)| i)
            .collect()
    }
}

// ============================================================================
// Block Alignment Requirements
// ============================================================================

/// Alignment requirement for a basic block.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct BlockAlignment {
    /// Required alignment (power of 2, 0 = no requirement).
    pub alignment: u32,
    /// Whether this block is a function entry.
    pub is_entry: bool,
    /// Whether this block is a loop header.
    pub is_loop_header: bool,
    /// Whether this block is a hot path target.
    pub is_hot_target: bool,
    /// Whether this block is a branch target (jump destination).
    pub is_branch_target: bool,
    /// Whether this block is an exception landing pad.
    pub is_eh_pad: bool,
    /// Whether this block is the start of a cold region.
    pub is_cold_region_start: bool,
}

impl BlockAlignment {
    pub fn new() -> Self {
        Self {
            alignment: 0,
            is_entry: false,
            is_loop_header: false,
            is_hot_target: false,
            is_branch_target: false,
            is_eh_pad: false,
            is_cold_region_start: false,
        }
    }

    /// Determine the alignment requirement for a block.
    pub fn determine(&mut self) -> u32 {
        if self.is_entry {
            self.alignment = ENTRY_ALIGNMENT;
        } else if self.is_loop_header {
            self.alignment = LOOP_HEADER_ALIGNMENT;
        } else if self.is_hot_target {
            self.alignment = HOT_BLOCK_ALIGNMENT;
        } else if self.is_eh_pad {
            self.alignment = 4; // EH pads don't need heavy alignment
        } else {
            self.alignment = 0; // No alignment requirement
        }
        self.alignment
    }
}

/// Compute block alignment requirements for all blocks.
#[derive(Debug, Clone)]
pub struct BlockAlignmentInfo {
    /// Alignment for each block.
    pub alignments: Vec<BlockAlignment>,
    /// Whether alignment was computed.
    pub valid: bool,
}

impl BlockAlignmentInfo {
    pub fn new() -> Self {
        Self {
            alignments: Vec::new(),
            valid: false,
        }
    }

    /// Compute alignment for each block based on CFG properties.
    pub fn compute(
        &mut self,
        blocks: &[MachineBasicBlock],
        loop_info: Option<&LoopInfo>,
        freq_est: Option<&BlockFrequencyEstimator>,
    ) {
        let n = blocks.len();
        if n == 0 {
            self.valid = true;
            return;
        }

        self.alignments = vec![BlockAlignment::new(); n];

        // Entry alignment
        if n > 0 {
            self.alignments[0].is_entry = true;
            self.alignments[0].alignment = ENTRY_ALIGNMENT;
        }

        // Loop header alignment
        if let Some(li) = loop_info {
            for l in &li.loops {
                if l.header < n {
                    self.alignments[l.header].is_loop_header = true;
                    self.alignments[l.header].alignment = self.alignments[l.header]
                        .alignment
                        .max(LOOP_HEADER_ALIGNMENT);
                }
            }
        }

        // Branch target alignment (blocks with >1 predecessor)
        for i in 0..n {
            if blocks[i].predecessors.len() > 1 {
                self.alignments[i].is_branch_target = true;
                self.alignments[i].alignment =
                    self.alignments[i].alignment.max(HOT_BLOCK_ALIGNMENT);
            }
        }

        // Hot block alignment
        if let Some(fe) = freq_est {
            let hot_threshold = HOT_FREQUENCY_THRESHOLD;
            for i in 0..n {
                if fe.is_hot(i, hot_threshold) && blocks[i].predecessors.len() > 1 {
                    self.alignments[i].is_hot_target = true;
                    self.alignments[i].alignment =
                        self.alignments[i].alignment.max(HOT_BLOCK_ALIGNMENT);
                }
            }
        }

        self.valid = true;
    }

    /// Get alignment for a specific block.
    pub fn alignment_of(&self, block: usize) -> u32 {
        self.alignments.get(block).map(|a| a.alignment).unwrap_or(0)
    }
}

// ============================================================================
// Block Layout Optimization
// ============================================================================

/// Configuration for block layout optimization.
#[derive(Debug, Clone)]
pub struct BlockLayoutConfig {
    /// Whether to split hot and cold blocks.
    pub hot_cold_split: bool,
    /// Hot frequency threshold.
    pub hot_threshold: f64,
    /// Cold frequency threshold.
    pub cold_threshold: f64,
    /// Whether to chain blocks for fallthrough.
    pub chain_fallthrough: bool,
    /// Whether to consider branch weights.
    pub use_branch_weights: bool,
    /// Maximum chain length.
    pub max_chain_length: usize,
}

impl Default for BlockLayoutConfig {
    fn default() -> Self {
        Self {
            hot_cold_split: true,
            hot_threshold: HOT_FREQUENCY_THRESHOLD,
            cold_threshold: COLD_FREQUENCY_THRESHOLD,
            chain_fallthrough: true,
            use_branch_weights: true,
            max_chain_length: 100,
        }
    }
}

/// A chain of blocks that are placed contiguously.
#[derive(Debug, Clone)]
pub struct LayoutChain {
    /// Blocks in order.
    pub blocks: Vec<usize>,
    /// First block.
    pub head: usize,
    /// Last block.
    pub tail: usize,
    /// Total execution frequency.
    pub total_freq: f64,
    /// Whether this chain is hot.
    pub is_hot: bool,
}

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

    pub fn merge_with(&mut self, other: &LayoutChain) {
        self.blocks.extend(&other.blocks);
        self.tail = other.tail;
        self.total_freq += other.total_freq;
    }
}

/// Result of block layout optimization.
#[derive(Debug, Clone)]
pub struct BlockLayoutResult {
    /// Optimal block ordering.
    pub order: Vec<usize>,
    /// Number of fallthrough edges created.
    pub fallthrough_count: usize,
    /// Whether hot/cold splitting was applied.
    pub hot_cold_split: bool,
    /// Whether the layout is valid.
    pub valid: bool,
}

impl BlockLayoutResult {
    pub fn new() -> Self {
        Self {
            order: Vec::new(),
            fallthrough_count: 0,
            hot_cold_split: false,
            valid: false,
        }
    }
}

/// Compute optimal block layout using chain-based algorithm.
pub fn compute_block_layout(
    blocks: &[MachineBasicBlock],
    freq_est: &BlockFrequencyEstimator,
    config: &BlockLayoutConfig,
) -> BlockLayoutResult {
    let n = blocks.len();
    if n == 0 {
        return BlockLayoutResult {
            valid: true,
            ..BlockLayoutResult::new()
        };
    }

    let mut result = BlockLayoutResult::new();

    // Classify blocks as hot/cold
    let hot_blocks: HashSet<usize> = (0..n)
        .filter(|&i| freq_est.is_hot(i, config.hot_threshold))
        .collect();
    let cold_blocks: HashSet<usize> = (0..n)
        .filter(|&i| freq_est.is_cold(i, config.cold_threshold) && !hot_blocks.contains(&i))
        .collect();

    // Build chains starting from hot blocks
    let mut chains: Vec<LayoutChain> = Vec::new();
    let mut placed: HashSet<usize> = HashSet::new();

    for &hot in &hot_blocks {
        if placed.contains(&hot) {
            continue;
        }
        let mut chain = LayoutChain::new(hot, freq_est.frequency_of(hot), true);
        placed.insert(hot);

        // Extend chain forward through hot successors
        let mut current = hot;
        loop {
            let succs = &blocks[current].successors;
            // Find the hottest successor not yet placed
            let best_succ = succs
                .iter()
                .filter(|&&s| s < n && !placed.contains(&s) && hot_blocks.contains(&s))
                .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 {
                if chain.blocks.len() < config.max_chain_length {
                    chain.blocks.push(succ);
                    chain.tail = succ;
                    chain.total_freq += freq_est.frequency_of(succ);
                    placed.insert(succ);
                    current = succ;
                    continue;
                }
            }
            break;
        }

        chains.push(chain);
    }

    // Add remaining blocks as individual chains
    for i in 0..n {
        if !placed.contains(&i) {
            let is_hot = hot_blocks.contains(&i);
            chains.push(LayoutChain::new(i, freq_est.frequency_of(i), is_hot));
            placed.insert(i);
        }
    }

    // Build final order: hot chains first, then others
    for chain in &chains {
        if chain.is_hot || !config.hot_cold_split {
            result.order.extend(&chain.blocks);
        }
    }
    for chain in &chains {
        if !chain.is_hot && config.hot_cold_split {
            result.order.extend(&chain.blocks);
        }
    }

    // Count fallthrough edges
    for w in result.order.windows(2) {
        if blocks[w[0]].successors.contains(&w[1]) {
            result.fallthrough_count += 1;
        }
    }

    result.hot_cold_split = config.hot_cold_split;
    result.valid = true;
    result
}

// ============================================================================
// Branch Weight Metadata Annotation
// ============================================================================

/// Branch weight metadata for an edge pair (taken weight, not-taken weight).
#[derive(Debug, Clone, Copy)]
pub struct BranchWeightMeta {
    /// Weight for the taken branch.
    pub taken_weight: u64,
    /// Weight for the not-taken (fallthrough) branch.
    pub fallthrough_weight: u64,
    /// Whether these weights come from profiling.
    pub from_profile: bool,
}

impl BranchWeightMeta {
    pub fn new(taken: u64, fallthrough: u64) -> Self {
        Self {
            taken_weight: taken,
            fallthrough_weight: fallthrough,
            from_profile: false,
        }
    }

    /// Total weight.
    pub fn total(&self) -> u64 {
        self.taken_weight + self.fallthrough_weight
    }

    /// Probability of taking the branch.
    pub fn taken_probability(&self) -> f64 {
        let total = self.total();
        if total == 0 {
            return 0.5;
        }
        self.taken_weight as f64 / total as f64
    }

    /// Probability of falling through.
    pub fn fallthrough_probability(&self) -> f64 {
        1.0 - self.taken_probability()
    }

    /// Normalize weights to small integers.
    pub fn normalize(&self) -> Self {
        let total = self.total();
        if total == 0 {
            return Self::new(0, 0);
        }
        // Scale to at most u32::MAX
        let scale = (u32::MAX as u64) / total.max(1);
        Self {
            taken_weight: self.taken_weight * scale,
            fallthrough_weight: self.fallthrough_weight * scale,
            from_profile: self.from_profile,
        }
    }

    /// Create from static heuristic.
    pub fn from_heuristic(taken_prob: f64) -> Self {
        let taken = (taken_prob * 1000.0) as u64;
        let fallthrough = 1000 - taken;
        Self::new(taken, fallthrough)
    }
}

/// Manager for branch weight metadata.
#[derive(Debug, Clone)]
pub struct BranchWeightManager {
    /// Weights for each block's branch.
    pub weights: HashMap<usize, BranchWeightMeta>,
    /// Whether weights were analyzed.
    pub valid: bool,
}

impl BranchWeightManager {
    pub fn new() -> Self {
        Self {
            weights: HashMap::new(),
            valid: false,
        }
    }

    /// Extract or estimate branch weights for all conditional branches.
    pub fn analyze(
        &mut self,
        blocks: &[MachineBasicBlock],
        freq_est: Option<&BlockFrequencyEstimator>,
    ) {
        for (i, block) in blocks.iter().enumerate() {
            if block.successors.len() != 2 {
                continue;
            }
            let true_dst = block.successors[0];
            let false_dst = block.successors[1];

            // Try to get weights from frequency estimator
            if let Some(fe) = freq_est {
                let true_freq = fe.frequency_of(true_dst);
                let false_freq = fe.frequency_of(false_dst);
                let total = true_freq + false_freq;
                if total > 0.0 {
                    let taken = (true_freq / total * 1000.0) as u64;
                    let fallthrough = 1000 - taken;
                    self.weights
                        .insert(i, BranchWeightMeta::new(taken.max(1), fallthrough.max(1)));
                }
            }

            // Fallback: static heuristic
            if !self.weights.contains_key(&i) {
                let meta = BranchWeightMeta::from_heuristic(0.3); // Default: unlikely taken
                self.weights.insert(i, meta);
            }
        }

        self.valid = true;
    }

    /// Get the branch weight metadata for a block.
    pub fn weight_for(&self, block: usize) -> Option<&BranchWeightMeta> {
        self.weights.get(&block)
    }

    /// Set branch weight for a block.
    pub fn set_weight(&mut self, block: usize, weight: BranchWeightMeta) {
        self.weights.insert(block, weight);
    }

    /// Check weight consistency across interconnected blocks.
    pub fn check_consistency(&self, blocks: &[MachineBasicBlock]) -> Vec<String> {
        let mut issues = Vec::new();

        for (i, block) in blocks.iter().enumerate() {
            if let Some(w) = self.weights.get(&i) {
                if w.taken_weight == 0 && w.fallthrough_weight == 0 {
                    issues.push(format!("Block {} has zero branch weights", i));
                }
                if block.successors.len() != 2 {
                    issues.push(format!(
                        "Block {} has branch weights but {} successors",
                        i,
                        block.successors.len()
                    ));
                }
            }
        }

        issues
    }
}

// ============================================================================
// Block Address Taken Analysis
// ============================================================================

/// Information about a block whose address is taken.
#[derive(Debug, Clone)]
pub struct AddressTakenBlock {
    /// Block index.
    pub block: usize,
    /// Whether the address is used in a branch (indirect jump target).
    pub used_in_branch: bool,
    /// Whether the address is used in a non-branch context (data usage).
    pub used_as_data: bool,
    /// Function that takes the address (if applicable).
    pub taken_by_fn: Option<String>,
    /// Whether this is a potential indirect call target.
    pub is_indirect_call_target: bool,
}

impl AddressTakenBlock {
    pub fn new(block: usize) -> Self {
        Self {
            block,
            used_in_branch: false,
            used_as_data: false,
            taken_by_fn: None,
            is_indirect_call_target: false,
        }
    }
}

/// Analysis of blocks with addresses taken.
#[derive(Debug, Clone)]
pub struct AddressTakenAnalysis {
    /// Blocks whose addresses are taken.
    pub address_taken: Vec<AddressTakenBlock>,
    /// Set of blocks used as indirect jump targets.
    pub indirect_jump_targets: HashSet<usize>,
    /// Set of blocks used as indirect call targets.
    pub indirect_call_targets: HashSet<usize>,
    /// Whether analysis was performed.
    pub valid: bool,
}

impl AddressTakenAnalysis {
    pub fn new() -> Self {
        Self {
            address_taken: Vec::new(),
            indirect_jump_targets: HashSet::new(),
            indirect_call_targets: HashSet::new(),
            valid: false,
        }
    }

    /// Analyze blocks for address-taken usage.
    pub fn analyze(&mut self, blocks: &[MachineBasicBlock]) {
        let n = blocks.len();

        // In a full implementation, this would scan machine instructions for
        // patterns that take block addresses (LEA with block label, indirect
        // JMP/CALL with block label operand, MOV from label, etc.)
        //
        // For this clean-room reconstruction, we note that blocks that are
        // targets of multiple indirect branches or appear in jump tables
        // have their addresses taken.

        // Simple heuristic: blocks with >1 predecessor AND predecessors
        // that have indirect branches may have address taken
        for i in 0..n {
            let pred_count = blocks[i].predecessors.len();
            if pred_count > 0 {
                let mut block_info = AddressTakenBlock::new(i);

                // Check if any predecessor has indirect terminator
                for &pred in &blocks[i].predecessors {
                    if pred >= n {
                        continue;
                    }
                    // Heuristic: predecessor with >2 successors may use
                    // jump table (indirect addressing of targets)
                    if blocks[pred].successors.len() > 2 {
                        block_info.used_in_branch = true;
                        self.indirect_jump_targets.insert(i);
                    }
                    // Heuristic: if predecessor has many instructions and
                    // block is a loop header, likely indirect call target
                    if blocks[pred].instructions.len() > 10 && pred_count > 2 {
                        block_info.is_indirect_call_target = true;
                        self.indirect_call_targets.insert(i);
                    }
                }

                if block_info.used_in_branch || block_info.is_indirect_call_target {
                    self.address_taken.push(block_info);
                }
            }
        }

        self.valid = true;
    }

    /// Whether a block's address is taken.
    pub fn is_address_taken(&self, block: usize) -> bool {
        self.address_taken.iter().any(|at| at.block == block)
    }

    /// Whether a block is an indirect jump target.
    pub fn is_indirect_jump_target(&self, block: usize) -> bool {
        self.indirect_jump_targets.contains(&block)
    }

    /// Whether a block is an indirect call target.
    pub fn is_indirect_call_target(&self, block: usize) -> bool {
        self.indirect_call_targets.contains(&block)
    }

    /// Get blocks with addresses taken.
    pub fn address_taken_blocks(&self) -> &[AddressTakenBlock] {
        &self.address_taken
    }
}

// ============================================================================
// Exception Handling Block Identification
// ============================================================================

/// Classification of an exception handling block.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum EHBlockKind {
    /// Normal block (not EH-related).
    Normal,
    /// Landing pad: entry point for exception handling.
    LandingPad,
    /// Catch handler: catches a specific exception type.
    Catch,
    /// Cleanup handler: executes during stack unwinding.
    Cleanup,
    /// Filter handler: selects among catch handlers.
    Filter,
    /// Catch-all handler: catches any exception.
    CatchAll,
    /// Terminate handler: calls std::terminate.
    Terminate,
    /// Rethrow handler: rethrows the current exception.
    Rethrow,
    /// Resume handler: resumes after a landing pad.
    Resume,
    /// Exception dispatch: dispatches to catch/cleanup handlers.
    Dispatch,
}

impl EHBlockKind {
    /// Whether this block is any kind of exception handling block.
    pub fn is_eh_block(&self) -> bool {
        !matches!(self, Self::Normal)
    }

    /// Whether this is a landing pad.
    pub fn is_landing_pad(&self) -> bool {
        matches!(self, Self::LandingPad)
    }

    /// Whether this block can catch exceptions.
    pub fn can_catch(&self) -> bool {
        matches!(self, Self::Catch | Self::CatchAll)
    }

    /// Whether this block performs cleanup.
    pub fn is_cleanup(&self) -> bool {
        matches!(self, Self::Cleanup)
    }
}

/// Information about an EH block.
#[derive(Debug, Clone)]
pub struct EHBlockInfo {
    /// Block index.
    pub block: usize,
    /// Classification.
    pub kind: EHBlockKind,
    /// Associated personality function (if any).
    pub personality_function: Option<String>,
    /// Exception types caught (for Catch blocks).
    pub caught_types: Vec<String>,
    /// Landing pad ID (if this is a landing pad).
    pub landing_pad_id: Option<u32>,
    /// Cleanup action (for Cleanup blocks).
    pub cleanup_action: Option<String>,
    /// Whether this block has an invoke instruction.
    pub has_invoke: bool,
    /// Whether this block has a resume instruction.
    pub has_resume: bool,
    /// Whether this block has a catchswitch.
    pub has_catchswitch: bool,
}

impl EHBlockInfo {
    pub fn new(block: usize, kind: EHBlockKind) -> Self {
        Self {
            block,
            kind,
            personality_function: None,
            caught_types: Vec::new(),
            landing_pad_id: None,
            cleanup_action: None,
            has_invoke: false,
            has_resume: false,
            has_catchswitch: false,
        }
    }
}

/// Full exception handling analysis for a function.
#[derive(Debug, Clone)]
pub struct EHAnalysis {
    /// EH info for each block.
    pub blocks: Vec<EHBlockInfo>,
    /// Landing pad blocks.
    pub landing_pads: Vec<usize>,
    /// Catch blocks.
    pub catch_blocks: Vec<usize>,
    /// Cleanup blocks.
    pub cleanup_blocks: Vec<usize>,
    /// Personality function name.
    pub personality_function: Option<String>,
    /// Whether the function has any EH.
    pub has_eh: bool,
    /// Whether analysis was performed.
    pub valid: bool,
}

impl EHAnalysis {
    pub fn new() -> Self {
        Self {
            blocks: Vec::new(),
            landing_pads: Vec::new(),
            catch_blocks: Vec::new(),
            cleanup_blocks: Vec::new(),
            personality_function: None,
            has_eh: false,
            valid: false,
        }
    }

    /// Analyze a function for EH-related blocks.
    pub fn analyze(&mut self, blocks: &[MachineBasicBlock]) {
        let n = blocks.len();
        if n == 0 {
            self.valid = true;
            return;
        }

        self.blocks = (0..n)
            .map(|i| EHBlockInfo::new(i, EHBlockKind::Normal))
            .collect();

        for i in 0..n {
            // Classification heuristics based on block properties:
            // - Landing pads typically have multiple predecessors (normal + EH edges)
            // - Catch blocks follow landing pads in the CFG
            // - Cleanup blocks have specific edge patterns

            let pred_count = blocks[i].predecessors.len();

            // Landing pad detection: multiple predecessors, some from EH dispatch
            if pred_count >= 2 {
                // Check if any predecessor is an invoke site (has 2+ successors)
                let has_eh_pred = blocks[i]
                    .predecessors
                    .iter()
                    .any(|&p| p < n && blocks[p].successors.len() >= 2);

                if has_eh_pred {
                    self.blocks[i].kind = EHBlockKind::LandingPad;
                    self.blocks[i].landing_pad_id = Some(i as u32);
                    self.landing_pads.push(i);
                    self.has_eh = true;
                }
            }

            // Catch block detection: single predecessor (a dispatch block)
            // and the block contains type-specific code
            if pred_count == 1 {
                let pred = blocks[i].predecessors[0];
                if pred < n && self.blocks[pred].kind.is_eh_block() {
                    // Heuristic: this could be a catch block
                    if self.blocks[i].kind == EHBlockKind::Normal {
                        self.blocks[i].kind = EHBlockKind::Catch;
                        self.catch_blocks.push(i);
                    }
                }
            }

            // Cleanup block: targets of EH dispatch without type checking
            if self.blocks[i].kind == EHBlockKind::LandingPad {
                // Landing pads that don't branch to catch blocks are cleanup
                let has_catch_succ = blocks[i]
                    .successors
                    .iter()
                    .any(|&s| s < n && self.blocks[s].kind == EHBlockKind::Catch);
                if !has_catch_succ && !blocks[i].successors.is_empty() {
                    self.blocks[i].kind = EHBlockKind::Cleanup;
                    self.cleanup_blocks.push(i);
                }
            }
        }

        self.valid = true;
    }

    /// Whether a block is any type of EH block.
    pub fn is_eh_block(&self, block: usize) -> bool {
        self.blocks
            .get(block)
            .map(|b| b.kind.is_eh_block())
            .unwrap_or(false)
    }

    /// Whether a block is a landing pad.
    pub fn is_landing_pad(&self, block: usize) -> bool {
        self.blocks
            .get(block)
            .map(|b| b.kind.is_landing_pad())
            .unwrap_or(false)
    }

    /// Get all EH blocks.
    pub fn eh_blocks(&self) -> Vec<usize> {
        self.blocks
            .iter()
            .enumerate()
            .filter(|(_, b)| b.kind.is_eh_block())
            .map(|(i, _)| i)
            .collect()
    }

    /// Get blocks that can catch exceptions.
    pub fn catching_blocks(&self) -> Vec<usize> {
        self.blocks
            .iter()
            .enumerate()
            .filter(|(_, b)| b.kind.can_catch())
            .map(|(i, _)| i)
            .collect()
    }
}

// ============================================================================
// X86BBUtils — main basic block utility library
// ============================================================================

/// Comprehensive basic block analysis and manipulation for X86 targets.
///
/// Provides dominator tree construction, post-dominance, dominance frontiers,
/// loop info, control dependence graph, reachability, block frequency
/// estimation, block alignment, block layout, branch weight metadata,
/// block address analysis, and EH block identification.
#[derive(Debug, Clone)]
pub struct X86BBUtils {
    /// Dominator tree.
    pub dom_tree: DominatorTree,
    /// Post-dominator tree.
    pub post_dom_tree: PostDominatorTree,
    /// Dominance frontiers.
    pub dom_frontiers: DominanceFrontiers,
    /// Loop info.
    pub loop_info: LoopInfo,
    /// Control dependence graph.
    pub cdg: ControlDependenceGraph,
    /// Reachability info.
    pub reachability: ReachabilityInfo,
    /// Block frequency estimator.
    pub freq_estimator: BlockFrequencyEstimator,
    /// Block alignment info.
    pub alignment: BlockAlignmentInfo,
    /// Branch weight manager.
    pub branch_weights: BranchWeightManager,
    /// Address taken analysis.
    pub address_taken: AddressTakenAnalysis,
    /// EH analysis.
    pub eh_analysis: EHAnalysis,
    /// Whether full analysis has been performed.
    pub analyzed: bool,
}

impl X86BBUtils {
    /// Create a new basic block utility with empty analysis.
    pub fn new() -> Self {
        Self {
            dom_tree: DominatorTree::new(),
            post_dom_tree: PostDominatorTree::new(),
            dom_frontiers: DominanceFrontiers::new(),
            loop_info: LoopInfo::new(),
            cdg: ControlDependenceGraph::new(),
            reachability: ReachabilityInfo::new(),
            freq_estimator: BlockFrequencyEstimator::new(),
            alignment: BlockAlignmentInfo::new(),
            branch_weights: BranchWeightManager::new(),
            address_taken: AddressTakenAnalysis::new(),
            eh_analysis: EHAnalysis::new(),
            analyzed: false,
        }
    }

    /// Run full analysis on a function's basic blocks.
    pub fn analyze(&mut self, blocks: &[MachineBasicBlock]) {
        // 1. Dominator tree (iterative algorithm for robustness)
        self.dom_tree.build_iterative(blocks);

        // 2. Post-dominator tree
        self.post_dom_tree.build(blocks);

        // 3. Dominance frontiers
        self.dom_frontiers.compute(&self.dom_tree, blocks);

        // 4. Loop info
        self.loop_info.build(blocks, &self.dom_tree);

        // 5. Control dependence graph
        self.cdg.build(blocks, &self.post_dom_tree);

        // 6. Reachability
        self.reachability.compute(blocks);

        // 7. Block frequency estimation
        self.freq_estimator.estimate(blocks, Some(&self.dom_tree));

        // 8. Block alignment
        self.alignment
            .compute(blocks, Some(&self.loop_info), Some(&self.freq_estimator));

        // 9. Branch weight metadata
        self.branch_weights
            .analyze(blocks, Some(&self.freq_estimator));

        // 10. Address taken analysis
        self.address_taken.analyze(blocks);

        // 11. EH block identification
        self.eh_analysis.analyze(blocks);

        self.analyzed = true;
    }

    /// Build dominator tree (iterative).
    pub fn build_dominator_tree(&mut self, blocks: &[MachineBasicBlock]) {
        self.dom_tree.build_iterative(blocks);
    }

    /// Build dominator tree (Lengauer-Tarjan).
    pub fn build_dominator_tree_lt(&mut self, blocks: &[MachineBasicBlock]) {
        self.dom_tree.build_lengauer_tarjan(blocks);
    }

    /// Build post-dominator tree.
    pub fn build_post_dominator_tree(&mut self, blocks: &[MachineBasicBlock]) {
        self.post_dom_tree.build(blocks);
    }

    /// Compute dominance frontiers.
    pub fn compute_dominance_frontiers(&mut self, blocks: &[MachineBasicBlock]) {
        self.dom_frontiers.compute(&self.dom_tree, blocks);
    }

    /// Build loop info.
    pub fn build_loop_info(&mut self, blocks: &[MachineBasicBlock]) {
        self.loop_info.build(blocks, &self.dom_tree);
    }

    /// Build control dependence graph.
    pub fn build_cdg(&mut self, blocks: &[MachineBasicBlock]) {
        self.cdg.build(blocks, &self.post_dom_tree);
    }

    /// Compute reachability.
    pub fn compute_reachability(&mut self, blocks: &[MachineBasicBlock]) {
        self.reachability.compute(blocks);
    }

    /// Estimate block frequencies.
    pub fn estimate_frequencies(&mut self, blocks: &[MachineBasicBlock]) {
        self.freq_estimator.estimate(blocks, Some(&self.dom_tree));
    }

    /// Run EH analysis.
    pub fn analyze_eh(&mut self, blocks: &[MachineBasicBlock]) {
        self.eh_analysis.analyze(blocks);
    }

    /// Compute optimal block layout.
    pub fn compute_layout(
        &self,
        blocks: &[MachineBasicBlock],
        config: Option<BlockLayoutConfig>,
    ) -> BlockLayoutResult {
        let cfg = config.unwrap_or_default();
        compute_block_layout(blocks, &self.freq_estimator, &cfg)
    }

    /// Get dominator tree.
    pub fn get_dom_tree(&self) -> &DominatorTree {
        &self.dom_tree
    }

    /// Get post-dominator tree.
    pub fn get_post_dom_tree(&self) -> &PostDominatorTree {
        &self.post_dom_tree
    }

    /// Get loop info.
    pub fn get_loop_info(&self) -> &LoopInfo {
        &self.loop_info
    }

    /// Get frequency estimator.
    pub fn get_freq_estimator(&self) -> &BlockFrequencyEstimator {
        &self.freq_estimator
    }

    /// Get reachability info.
    pub fn get_reachability(&self) -> &ReachabilityInfo {
        &self.reachability
    }

    /// Get EH analysis.
    pub fn get_eh_analysis(&self) -> &EHAnalysis {
        &self.eh_analysis
    }

    /// Check if a block is dead.
    pub fn is_block_dead(&self, block: usize) -> bool {
        self.reachability.is_dead(block)
    }

    /// Get loop depth of a block.
    pub fn loop_depth_of(&self, block: usize) -> u32 {
        self.loop_info.get_loop_depth(block)
    }

    /// Get block frequency.
    pub fn block_frequency(&self, block: usize) -> f64 {
        self.freq_estimator.frequency_of(block)
    }

    /// Get block alignment.
    pub fn block_alignment(&self, block: usize) -> u32 {
        self.alignment.alignment_of(block)
    }

    /// Whether a block is a landing pad.
    pub fn is_landing_pad(&self, block: usize) -> bool {
        self.eh_analysis.is_landing_pad(block)
    }

    /// Whether a block's address is taken.
    pub fn is_address_taken(&self, block: usize) -> bool {
        self.address_taken.is_address_taken(block)
    }
}

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

/// Create a new X86BBUtils with default configuration.
pub fn make_x86_bb_utils() -> X86BBUtils {
    X86BBUtils::new()
}

/// Create and run full analysis on blocks.
pub fn make_x86_bb_utils_analyzed(blocks: &[MachineBasicBlock]) -> X86BBUtils {
    let mut utils = X86BBUtils::new();
    utils.analyze(blocks);
    utils
}

/// Create utils with only dominator analysis (lightweight).
pub fn make_x86_bb_utils_dominators_only(blocks: &[MachineBasicBlock]) -> X86BBUtils {
    let mut utils = X86BBUtils::new();
    utils.build_dominator_tree(blocks);
    utils
}

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

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

    /// Helper: create a simple linear CFG: 0 → 1 → 2
    fn make_linear_cfg() -> Vec<MachineBasicBlock> {
        let mut b0 = MachineBasicBlock::new(0);
        b0.successors = vec![1];
        let mut b1 = MachineBasicBlock::new(1);
        b1.predecessors = vec![0];
        b1.successors = vec![2];
        let mut b2 = MachineBasicBlock::new(2);
        b2.predecessors = vec![1];
        vec![b0, b1, b2]
    }

    /// Helper: create a diamond CFG:
    ///     0
    ///    / \
    ///   1   2
    ///    \ /
    ///     3
    fn make_diamond_cfg() -> Vec<MachineBasicBlock> {
        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];
        vec![b0, b1, b2, b3]
    }

    /// Helper: create a loop CFG:
    ///     0 → 1 → 2
    ///         ↑   ↓
    ///         └───3
    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]; // Backedge to 1
        vec![b0, b1, b2, b3]
    }

    // -----------------------------------------------------------------------
    // DominatorTree tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_dom_tree_empty() {
        let mut dt = DominatorTree::new();
        dt.build_iterative(&[]);
        assert!(dt.valid);
        assert!(dt.nodes.is_empty());
    }

    #[test]
    fn test_dom_tree_linear() {
        let blocks = make_linear_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);

        assert!(dt.valid);
        assert_eq!(dt.nodes.len(), 3);
        assert_eq!(dt.idom_of(0), Some(0));
        assert_eq!(dt.idom_of(1), Some(0));
        assert_eq!(dt.idom_of(2), Some(1));
    }

    #[test]
    fn test_dom_tree_diamond() {
        let blocks = make_diamond_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);

        assert_eq!(dt.idom_of(0), Some(0));
        assert_eq!(dt.idom_of(1), Some(0));
        assert_eq!(dt.idom_of(2), Some(0));
        assert_eq!(dt.idom_of(3), Some(0));
    }

    #[test]
    fn test_dom_tree_loop() {
        let blocks = make_loop_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);

        // 0 dominates all
        // 1 dominates 2 and 3 (since 1 is loop header, 3→1 is backedge)
        assert_eq!(dt.idom_of(0), Some(0));
        assert_eq!(dt.idom_of(1), Some(0));
        assert_eq!(dt.idom_of(2), Some(1));
        assert_eq!(dt.idom_of(3), Some(2));
    }

    #[test]
    fn test_dominates() {
        let blocks = make_linear_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);

        assert!(dt.dominates(0, 0));
        assert!(dt.dominates(0, 1));
        assert!(dt.dominates(0, 2));
        assert!(dt.dominates(1, 2));
        assert!(!dt.dominates(1, 0));
        assert!(!dt.dominates(2, 0));
    }

    #[test]
    fn test_nearest_common_dominator() {
        let blocks = make_diamond_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);

        // Common dominator of 1 and 2 is 0
        assert_eq!(dt.nearest_common_dominator(1, 2), Some(0));
        // Common dominator of 1 and 3 is 0
        assert_eq!(dt.nearest_common_dominator(1, 3), Some(0));
    }

    #[test]
    fn test_dominated_blocks() {
        let blocks = make_linear_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);

        let dom_by_0 = dt.dominated_blocks(0);
        assert_eq!(dom_by_0.len(), 3);
        assert!(dom_by_0.contains(&0));
        assert!(dom_by_0.contains(&1));
        assert!(dom_by_0.contains(&2));
    }

    #[test]
    fn test_lengauer_tarjan() {
        let blocks = make_linear_cfg();
        let mut dt = DominatorTree::new();
        dt.build_lengauer_tarjan(&blocks);

        assert!(dt.valid);
        assert_eq!(dt.idom_of(1), Some(0));
        assert_eq!(dt.idom_of(2), Some(1));
    }

    #[test]
    fn test_lengauer_tarjan_diamond() {
        let blocks = make_diamond_cfg();
        let mut dt = DominatorTree::new();
        dt.build_lengauer_tarjan(&blocks);

        assert_eq!(dt.idom_of(0), Some(0));
        assert_eq!(dt.idom_of(3), Some(0));
    }

    // -----------------------------------------------------------------------
    // PostDominatorTree tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_post_dom_tree_linear() {
        let blocks = make_linear_cfg();
        let mut pdt = PostDominatorTree::new();
        pdt.build(&blocks);

        assert!(pdt.valid);
        // Block 2 post-dominates 1 (all paths from 1 go through 2)
        assert!(pdt.post_dominates(2, 1));
        // Block 1 post-dominates 0
        assert!(pdt.post_dominates(1, 0));
    }

    #[test]
    fn test_post_dom_tree_diamond() {
        let blocks = make_diamond_cfg();
        let mut pdt = PostDominatorTree::new();
        pdt.build(&blocks);

        // Block 3 post-dominates 0, 1, 2
        assert!(pdt.post_dominates(3, 0));
        assert!(pdt.post_dominates(3, 1));
        assert!(pdt.post_dominates(3, 2));
    }

    // -----------------------------------------------------------------------
    // DominanceFrontiers tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_dominance_frontiers_diamond() {
        let blocks = make_diamond_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);
        let mut df = DominanceFrontiers::new();
        df.compute(&dt, &blocks);

        assert!(df.valid);
        // Block 0 dominates both 1 and 2, but 3 is in the frontier of 0
        // because 0 dominates 1 and 2 (predecessors of 3) but not strictly 3
        // Actually: 0 strictly dominates 3? Let me think.
        // 0 dominates 3 (all paths go through 0), and 0 != 3, so yes.
        // So 3 is NOT in frontier of 0.
        // But 1 is in frontier of 0 because 0 dominates pred(1)=0, and 0
        // does not strictly dominate 1? No, 0 strictly dominates 1.
        // Hmm, this is tricky. The diamond doesn't have frontiers for 0 in this simple case.

        // For a diamond, blocks 1 and 2 have frontier {3} because they
        // dominate themselves but not strictly dominate 3.
        if let Some(frontier) = df.frontier_of(1) {
            assert!(frontier.contains(&3));
        }
        if let Some(frontier) = df.frontier_of(2) {
            assert!(frontier.contains(&3));
        }
    }

    #[test]
    fn test_iterated_frontier() {
        let blocks = make_diamond_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);
        let mut df = DominanceFrontiers::new();
        df.compute(&dt, &blocks);

        let seeds: HashSet<usize> = [1].iter().copied().collect();
        let iterated = df.iterated_frontier(&seeds);
        assert!(!iterated.is_empty());
    }

    // -----------------------------------------------------------------------
    // LoopInfo tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_loop_info_empty() {
        let mut li = LoopInfo::new();
        let dt = DominatorTree::new();
        li.build(&[], &dt);
        assert!(li.valid);
        assert!(li.loops.is_empty());
    }

    #[test]
    fn test_loop_info_linear() {
        let blocks = make_linear_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);
        let mut li = LoopInfo::new();
        li.build(&blocks, &dt);

        // Linear CFG has no loops
        assert!(li.loops.is_empty());
    }

    #[test]
    fn test_loop_info_loop() {
        let blocks = make_loop_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);
        let mut li = LoopInfo::new();
        li.build(&blocks, &dt);

        // Loop header is block 1 (dominates 3 which has backedge to 1)
        assert!(!li.loops.is_empty());
        let loop0 = &li.loops[0];
        assert!(loop0.contains(1));
        assert!(loop0.contains(2));
        assert!(loop0.contains(3));
    }

    #[test]
    fn test_is_loop_header() {
        let blocks = make_loop_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);
        let mut li = LoopInfo::new();
        li.build(&blocks, &dt);

        assert!(li.is_loop_header(1));
        assert!(!li.is_loop_header(0));
        assert!(!li.is_loop_header(2));
        assert!(!li.is_loop_header(3));
    }

    #[test]
    fn test_loop_depth() {
        let blocks = make_loop_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);
        let mut li = LoopInfo::new();
        li.build(&blocks, &dt);

        // Block 0: outside loop, depth 0
        assert_eq!(li.get_loop_depth(0), 0);
        // Blocks 1, 2, 3: inside loop
        assert!(li.get_loop_depth(1) > 0);
        assert!(li.get_loop_depth(2) > 0);
        assert!(li.get_loop_depth(3) > 0);
    }

    // -----------------------------------------------------------------------
    // ControlDependenceGraph tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_cdg_diamond() {
        let blocks = make_diamond_cfg();
        let mut pdt = PostDominatorTree::new();
        pdt.build(&blocks);
        let mut cdg = ControlDependenceGraph::new();
        cdg.build(&blocks, &pdt);

        assert!(cdg.valid);
    }

    // -----------------------------------------------------------------------
    // ReachabilityInfo tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_reachability_linear() {
        let blocks = make_linear_cfg();
        let mut ri = ReachabilityInfo::new();
        ri.compute(&blocks);

        assert!(ri.is_reachable_from_entry(0));
        assert!(ri.is_reachable_from_entry(1));
        assert!(ri.is_reachable_from_entry(2));
        assert!(ri.can_reach_exit(2));
    }

    #[test]
    fn test_reachability_unreachable() {
        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); // No predecessors

        let blocks = vec![b0, b1, b2];
        let mut ri = ReachabilityInfo::new();
        ri.compute(&blocks);

        assert!(!ri.is_reachable_from_entry(2));
        assert!(ri.is_dead(2));
    }

    #[test]
    fn test_dead_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);

        let blocks = vec![b0, b1, b2];
        let mut ri = ReachabilityInfo::new();
        ri.compute(&blocks);

        let dead = ri.dead_blocks(&blocks);
        assert!(dead.contains(&2));
    }

    #[test]
    fn test_path_exists() {
        let blocks = make_linear_cfg();
        let ri = ReachabilityInfo::new();

        assert!(ri.path_exists(0, 2, &blocks));
        assert!(!ri.path_exists(2, 0, &blocks));
    }

    // -----------------------------------------------------------------------
    // BlockFrequencyEstimator tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_freq_estimator_empty() {
        let mut fe = BlockFrequencyEstimator::new();
        fe.estimate(&[], None);
        assert!(fe.valid);
        assert!(fe.frequencies.is_empty());
    }

    #[test]
    fn test_freq_estimator_linear() {
        let blocks = make_linear_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);
        let mut fe = BlockFrequencyEstimator::new();
        fe.estimate(&blocks, Some(&dt));

        assert!(fe.valid);
        assert_eq!(fe.frequencies.len(), 3);
        // Entry = 1.0
        assert!((fe.frequency_of(0) - 1.0).abs() < 1e-6);
    }

    #[test]
    fn test_is_hot_cold() {
        let blocks = make_linear_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);
        let mut fe = BlockFrequencyEstimator::new();
        fe.estimate(&blocks, Some(&dt));

        assert!(fe.is_hot(0, 0.5));
        assert!(!fe.is_cold(0, 0.5));
    }

    // -----------------------------------------------------------------------
    // BlockAlignment tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_block_alignment_default() {
        let mut ba = BlockAlignment::new();
        assert_eq!(ba.alignment, 0);
        ba.determine();
        assert_eq!(ba.alignment, 0); // No special classification
    }

    #[test]
    fn test_block_alignment_entry() {
        let mut ba = BlockAlignment::new();
        ba.is_entry = true;
        ba.determine();
        assert_eq!(ba.alignment, ENTRY_ALIGNMENT);
    }

    #[test]
    fn test_block_alignment_loop_header() {
        let mut ba = BlockAlignment::new();
        ba.is_loop_header = true;
        ba.determine();
        assert_eq!(ba.alignment, LOOP_HEADER_ALIGNMENT);
    }

    #[test]
    fn test_alignment_info_compute() {
        let blocks = make_linear_cfg();
        let mut ai = BlockAlignmentInfo::new();
        ai.compute(&blocks, None, None);
        assert!(ai.valid);
        assert_eq!(ai.alignment_of(0), ENTRY_ALIGNMENT); // Entry
    }

    // -----------------------------------------------------------------------
    // Block layout tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_compute_block_layout_empty() {
        let fe = BlockFrequencyEstimator::new();
        let config = BlockLayoutConfig::default();
        let result = compute_block_layout(&[], &fe, &config);
        assert!(result.valid);
        assert!(result.order.is_empty());
    }

    #[test]
    fn test_compute_block_layout_linear() {
        let blocks = make_linear_cfg();
        let mut dt = DominatorTree::new();
        dt.build_iterative(&blocks);
        let mut fe = BlockFrequencyEstimator::new();
        fe.estimate(&blocks, Some(&dt));

        let config = BlockLayoutConfig::default();
        let result = compute_block_layout(&blocks, &fe, &config);
        assert!(result.valid);
        assert_eq!(result.order.len(), 3);
    }

    // -----------------------------------------------------------------------
    // BranchWeightMeta tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_branch_weight_meta_new() {
        let meta = BranchWeightMeta::new(300, 700);
        assert_eq!(meta.total(), 1000);
        assert!((meta.taken_probability() - 0.3).abs() < 1e-6);
        assert!((meta.fallthrough_probability() - 0.7).abs() < 1e-6);
    }

    #[test]
    fn test_branch_weight_from_heuristic() {
        let meta = BranchWeightMeta::from_heuristic(0.9);
        // taken ~= 900, fallthrough ~= 100 (with some rounding)
        assert!(meta.taken_weight > 500);
    }

    #[test]
    fn test_branch_weight_manager_empty() {
        let mut mgr = BranchWeightManager::new();
        mgr.analyze(&[], None);
        assert!(mgr.valid);
        assert!(mgr.weights.is_empty());
    }

    #[test]
    fn test_branch_weight_consistency() {
        let mut mgr = BranchWeightManager::new();
        let blocks = make_linear_cfg();
        mgr.analyze(&blocks, None);

        let issues = mgr.check_consistency(&blocks);
        // Linear CFG has no branches with 2 successors, so no weights
        assert!(issues.is_empty());
    }

    // -----------------------------------------------------------------------
    // AddressTakenAnalysis tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_address_taken_empty() {
        let mut ata = AddressTakenAnalysis::new();
        ata.analyze(&[]);
        assert!(ata.valid);
        assert!(ata.address_taken.is_empty());
    }

    #[test]
    fn test_address_taken_simple() {
        let blocks = make_diamond_cfg();
        let mut ata = AddressTakenAnalysis::new();
        ata.analyze(&blocks);

        // Diamond has no indirect branches, so nothing should be address-taken
        assert!(ata.address_taken.is_empty());
    }

    // -----------------------------------------------------------------------
    // EHAnalysis tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_eh_analysis_empty() {
        let mut eh = EHAnalysis::new();
        eh.analyze(&[]);
        assert!(eh.valid);
        assert!(!eh.has_eh);
    }

    #[test]
    fn test_eh_analysis_linear_no_eh() {
        let blocks = make_linear_cfg();
        let mut eh = EHAnalysis::new();
        eh.analyze(&blocks);

        // Linear CFG with no EH patterns
        assert!(!eh.has_eh);
        assert!(eh.landing_pads.is_empty());
        assert!(eh.catch_blocks.is_empty());
        assert!(eh.cleanup_blocks.is_empty());
    }

    #[test]
    fn test_eh_block_kind() {
        assert!(EHBlockKind::LandingPad.is_eh_block());
        assert!(EHBlockKind::Catch.is_eh_block());
        assert!(EHBlockKind::Cleanup.is_eh_block());
        assert!(!EHBlockKind::Normal.is_eh_block());

        assert!(EHBlockKind::Catch.can_catch());
        assert!(!EHBlockKind::Cleanup.can_catch());
        assert!(EHBlockKind::Cleanup.is_cleanup());
    }

    // -----------------------------------------------------------------------
    // X86BBUtils integration tests
    // -----------------------------------------------------------------------

    #[test]
    fn test_make_x86_bb_utils() {
        let utils = make_x86_bb_utils();
        assert!(!utils.analyzed);
    }

    #[test]
    fn test_make_x86_bb_utils_analyzed() {
        let blocks = make_linear_cfg();
        let utils = make_x86_bb_utils_analyzed(&blocks);
        assert!(utils.analyzed);
        assert!(utils.dom_tree.valid);
        assert!(utils.reachability.valid);
    }

    #[test]
    fn test_full_analysis_linear() {
        let blocks = make_linear_cfg();
        let mut utils = X86BBUtils::new();
        utils.analyze(&blocks);

        assert!(utils.analyzed);
        assert!(utils.dom_tree.valid);
        assert!(utils.post_dom_tree.valid);
        assert!(utils.dom_frontiers.valid);
        assert!(utils.loop_info.valid);
        assert!(utils.cdg.valid);
        assert!(utils.reachability.valid);
        assert!(utils.freq_estimator.valid);
        assert!(utils.alignment.valid);
    }

    #[test]
    fn test_loop_depth_of_linear() {
        let blocks = make_linear_cfg();
        let mut utils = X86BBUtils::new();
        utils.analyze(&blocks);

        assert_eq!(utils.loop_depth_of(0), 0);
        assert_eq!(utils.loop_depth_of(1), 0);
        assert_eq!(utils.loop_depth_of(2), 0);
    }

    #[test]
    fn test_loop_depth_of_loop() {
        let blocks = make_loop_cfg();
        let mut utils = X86BBUtils::new();
        utils.analyze(&blocks);

        // Block 0 is outside the loop
        assert_eq!(utils.loop_depth_of(0), 0);
        // Blocks inside loop should have depth > 0
        assert!(utils.loop_depth_of(1) > 0);
    }

    #[test]
    fn test_block_frequency() {
        let blocks = make_linear_cfg();
        let mut utils = X86BBUtils::new();
        utils.analyze(&blocks);

        let freq0 = utils.block_frequency(0);
        assert!((freq0 - 1.0).abs() < 1e-6);
    }

    #[test]
    fn test_is_block_dead() {
        let blocks = make_linear_cfg();
        let mut utils = X86BBUtils::new();
        utils.analyze(&blocks);

        assert!(!utils.is_block_dead(0));
        assert!(!utils.is_block_dead(1));
        assert!(!utils.is_block_dead(2));
    }

    #[test]
    fn test_compute_layout() {
        let blocks = make_linear_cfg();
        let mut utils = X86BBUtils::new();
        utils.analyze(&blocks);

        let result = utils.compute_layout(&blocks, None);
        assert!(result.valid);
        assert_eq!(result.order.len(), 3);
    }

    #[test]
    fn test_is_landing_pad() {
        let blocks = make_linear_cfg();
        let mut utils = X86BBUtils::new();
        utils.analyze(&blocks);

        // Linear CFG has no EH
        assert!(!utils.is_landing_pad(0));
    }

    #[test]
    fn test_dominance_frontiers_present() {
        let blocks = make_diamond_cfg();
        let mut utils = X86BBUtils::new();
        utils.analyze(&blocks);

        // All blocks must have at least one frontier
        assert!(utils.dom_frontiers.valid);
    }

    #[test]
    fn test_post_dom_tree_integration() {
        let blocks = make_diamond_cfg();
        let mut utils = X86BBUtils::new();
        utils.analyze(&blocks);

        // Block 3 should post-dominate the earlier blocks
        let pdt = utils.get_post_dom_tree();
        assert!(pdt.valid);
    }
}