neo-decompiler 0.10.1

//! Dominance analysis for SSA construction.
//!
//! Computes immediate dominators, dominator tree, and dominance frontiers
//! using the Cooper-Harvey-Kennedy iterative algorithm.

use std::collections::{BTreeMap, BTreeSet};

use crate::decompiler::cfg::{BlockId, Cfg};

mod algorithm;
mod frontier;
mod traversal;

#[cfg(test)]
mod tests;

/// Dominance information computed from a CFG.
///
/// This includes immediate dominators, the dominator tree, and dominance frontiers
/// needed for SSA construction.
#[derive(Debug, Clone)]
pub struct DominanceInfo {
    /// Immediate dominator for each block.
    ///
    /// `None` for the entry block (which has no dominator).
    pub idom: BTreeMap<BlockId, Option<BlockId>>,

    /// Dominator tree: parent -> children.
    pub dominator_tree: BTreeMap<BlockId, Vec<BlockId>>,

    /// Dominance frontier for each block.
    ///
    /// Used to determine where to insert φ nodes.
    pub dominance_frontier: BTreeMap<BlockId, BTreeSet<BlockId>>,
}

impl DominanceInfo {
    /// Create a new empty dominance info.
    #[must_use]
    pub fn new() -> Self {
        Self {
            idom: BTreeMap::new(),
            dominator_tree: BTreeMap::new(),
            dominance_frontier: BTreeMap::new(),
        }
    }

    /// Get the immediate dominator of a block.
    ///
    /// Returns `None` for the entry block (which has no dominator).
    #[must_use]
    pub fn idom(&self, block: BlockId) -> Option<BlockId> {
        let idom = self.idom.get(&block).copied().flatten();
        if idom == Some(block) {
            None
        } else {
            idom
        }
    }

    /// Get all blocks that this block dominates (children in dominator tree).
    #[must_use]
    pub fn children(&self, block: BlockId) -> &[BlockId] {
        self.dominator_tree
            .get(&block)
            .map(Vec::as_slice)
            .unwrap_or(&[])
    }

    /// Get the dominance frontier of a block as a vector.
    #[must_use]
    pub fn dominance_frontier_vec(&self, block: BlockId) -> Vec<BlockId> {
        self.dominance_frontier
            .get(&block)
            .map(|set| set.iter().copied().collect())
            .unwrap_or_default()
    }

    /// Check if `a` strictly dominates `b`.
    #[must_use]
    pub fn strictly_dominates(&self, a: BlockId, b: BlockId) -> bool {
        if a == b {
            return false;
        }
        let mut current = self.idom(b);
        while let Some(idom) = current {
            if idom == a {
                return true;
            }
            current = self.idom(idom);
        }
        false
    }
}

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

/// Compute dominance information for a CFG.
///
/// Uses the Cooper-Harvey-Kennedy iterative algorithm:
/// 1. Initialize: entry dominates itself, others unknown
/// 2. Iterate: Intersect dominators of predecessors until convergence
/// 3. Build dominator tree from immediate dominator relationships
/// 4. Compute dominance frontiers for φ node insertion
///
/// Complexity: O(n²) worst case, but typically much faster for structured code.
#[must_use]
pub fn compute(cfg: &Cfg) -> DominanceInfo {
    if cfg.blocks().count() == 0 {
        return DominanceInfo::new();
    }

    let idom = algorithm::compute_immediate_dominators(cfg);
    let dominator_tree = algorithm::build_dominator_tree(&idom);
    let dominance_frontier = frontier::compute_df(cfg, &idom);

    DominanceInfo {
        idom,
        dominator_tree,
        dominance_frontier,
    }
}