cranelift_codegen/

dominator_tree.rs

//! A Dominator Tree represented as mappings of Blocks to their immediate dominator.

use crate::entity::SecondaryMap;
use crate::flowgraph::{BlockPredecessor, ControlFlowGraph};
use crate::ir::{Block, Function, Layout, ProgramPoint};
use crate::packed_option::PackedOption;
use crate::timing;
use alloc::vec::Vec;
use core::cmp;
use core::cmp::Ordering;
use core::mem;

mod simple;

pub use simple::SimpleDominatorTree;

/// A directed graph over a function's basic blocks, used to drive the generic
/// (post-)dominator tree computation shared by [`DominatorTree`] and
/// `PostDominatorTree`.
///
/// The `successors`/`predecessors` methods are in the *analysis* direction:
/// `successors` is the direction the spanning-tree DFS walks away from the
/// roots, and `predecessors` is the direction used while computing
/// semidominators. For the forward dominator tree (see `ForwardGraph`) this is
/// just the control-flow graph. For the post-dominator tree it is the
/// *reversed* control-flow graph, augmented with a virtual sink that sits above
/// the function's exit blocks; the spanning tree's existing virtual root (node
/// 0) plays the role of that sink.
pub(crate) trait DomTreeGraph {
    /// The number of blocks in the underlying function, used to size the
    /// per-block maps.
    fn num_blocks(&self) -> usize;

    /// The roots of the (post-)dominator forest: the blocks that are direct
    /// children of the virtual root/sink.
    ///
    /// For the dominator tree this is the entry block; for the post-dominator
    /// tree these are the function's exit blocks.
    fn roots(&self) -> impl Iterator<Item = Block>;

    /// The successors of `block`.
    fn successors(&self, block: Block) -> impl Iterator<Item = Block>;

    /// The predecessors of `block`.
    fn predecessors(&self, block: Block) -> impl Iterator<Item = Block>;
}

/// The forward control-flow graph, used to compute the standard
/// `DominatorTree`.
struct ForwardGraph<'a> {
    func: &'a Function,
    cfg: &'a ControlFlowGraph,
}

impl DomTreeGraph for ForwardGraph<'_> {
    fn num_blocks(&self) -> usize {
        self.func.dfg.num_blocks()
    }

    fn roots(&self) -> impl Iterator<Item = Block> {
        self.func.layout.entry_block().into_iter()
    }

    fn successors(&self, block: Block) -> impl Iterator<Item = Block> {
        // Heuristic: chase the children in reverse. This puts the first
        // successor block first in the postorder, all other things being equal,
        // which tends to prioritize loop backedges over out-edges, putting the
        // edge-block closer to the loop body and minimizing live-ranges in
        // linear instruction space. This heuristic doesn't have any effect on
        // the computation of dominators, and is purely for other consumers of
        // the postorder we cache here.
        self.func.block_successors(block).rev()
    }

    fn predecessors(&self, block: Block) -> impl Iterator<Item = Block> {
        self.cfg
            .pred_iter(block)
            .map(|pred: BlockPredecessor| pred.block)
    }
}

/// Spanning tree node, used during domtree computation.
#[derive(Clone, Default)]
struct SpanningTreeNode {
    /// This node's block in function CFG.
    block: PackedOption<Block>,
    /// Node's ancestor in the spanning tree.
    /// Gets invalidated during semi-dominator computation.
    ancestor: u32,
    /// The smallest semi value discovered on any semi-dominator path
    /// that went through the node up till the moment.
    /// Gets updated in the course of semi-dominator computation.
    label: u32,
    /// Semidominator value for the node.
    semi: u32,
    /// Immediate dominator value for the node.
    /// Initialized to node's ancestor in the spanning tree.
    idom: u32,
}

/// DFS preorder number for unvisited nodes and the virtual root in the spanning tree.
const NOT_VISITED: u32 = 0;

/// Spanning tree, in CFG preorder.
/// Node 0 is the virtual root and doesn't have a corresponding block.
/// It's not required because function's CFG in Cranelift always have
/// a singular root, but helps to avoid additional checks.
/// Numbering nodes from 0 also follows the convention in
/// `SimpleDominatorTree`.
#[derive(Clone, Default)]
struct SpanningTree {
    nodes: Vec<SpanningTreeNode>,
}

impl SpanningTree {
    fn new() -> Self {
        // Include the virtual root.
        Self {
            nodes: vec![Default::default()],
        }
    }

    fn with_capacity(capacity: usize) -> Self {
        // Include the virtual root.
        let mut nodes = Vec::with_capacity(capacity + 1);
        nodes.push(Default::default());
        Self { nodes }
    }

    fn len(&self) -> usize {
        self.nodes.len()
    }

    fn reserve(&mut self, capacity: usize) {
        // Virtual root should be already included.
        self.nodes.reserve(capacity);
    }

    fn clear(&mut self) {
        self.nodes.resize(1, Default::default());
    }

    /// Returns pre_number for the new node.
    fn push(&mut self, ancestor: u32, block: Block) -> u32 {
        // Virtual root should be already included.
        debug_assert!(!self.nodes.is_empty());

        let pre_number = self.nodes.len() as u32;

        self.nodes.push(SpanningTreeNode {
            block: block.into(),
            ancestor,
            label: pre_number,
            semi: pre_number,
            idom: ancestor,
        });

        pre_number
    }
}

impl core::ops::Index<u32> for SpanningTree {
    type Output = SpanningTreeNode;

    fn index(&self, idx: u32) -> &Self::Output {
        &self.nodes[idx as usize]
    }
}

impl core::ops::IndexMut<u32> for SpanningTree {
    fn index_mut(&mut self, idx: u32) -> &mut Self::Output {
        &mut self.nodes[idx as usize]
    }
}

/// Traversal event to compute both preorder spanning tree
/// and postorder block list. Can't use `Dfs` from traversals.rs
/// here because of the need for parent links.
enum TraversalEvent {
    Enter(u32, Block),
    Exit(Block),
}

/// Dominator tree node. We keep one of these per block.
#[derive(Clone, Default)]
struct DominatorTreeNode {
    /// Immediate dominator for the block, `None` for unreachable blocks.
    idom: PackedOption<Block>,
    /// Preorder traversal number, zero for unreachable blocks.
    pre_number: u32,
    /// This block's index in the CFG post-order, meaningless for unreachable
    /// blocks.
    post_number: u32,

    /// First child node in the domtree.
    child: PackedOption<Block>,

    /// Next sibling node in the domtree. This linked list is ordered according to the CFG RPO
    /// (i.e. decreasing CFG post-order number).
    sibling: PackedOption<Block>,

    /// Sequence number for this node in a pre-order traversal of the dominator tree.
    /// Unreachable blocks have number 0, the entry block is 1.
    dom_pre_number: u32,

    /// Maximum `dom_pre_number` for the sub-tree of the dominator tree that is rooted at this node.
    /// This is always >= `dom_pre_number`.
    dom_pre_max: u32,
}

/// The dominator tree for a single function,
/// computed using Semi-NCA algorithm.
pub struct DominatorTree {
    /// DFS spanning tree.
    stree: SpanningTree,
    /// List of CFG blocks in postorder.
    postorder: Vec<Block>,
    /// Dominator tree nodes.
    nodes: SecondaryMap<Block, DominatorTreeNode>,

    /// Stack for building the spanning tree.
    dfs_worklist: Vec<TraversalEvent>,
    /// Stack used for processing semidominator paths
    /// in link-eval procedure.
    eval_worklist: Vec<u32>,

    valid: bool,
}

impl core::fmt::Debug for DominatorTree {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        if !self.is_valid() {
            return f.write_str("DominatorTree { <invalid> }");
        }

        let mut s = f.debug_tuple("DominatorTree");

        if let Some((mut root, _)) = self.nodes.iter().find(|n| n.1.pre_number != NOT_VISITED) {
            loop {
                if let Some(b) = self.idom(root)
                    && b != root
                {
                    root = b;
                } else {
                    break;
                }
            }

            fn fmt_block(domtree: &DominatorTree, block: Block) -> impl core::fmt::Debug {
                core::fmt::from_fn(move |f| {
                    let children = domtree
                        .children(block)
                        .map(|c| fmt_block(domtree, c))
                        .collect::<Vec<_>>();
                    let mut s = f.debug_tuple(&format!("{block}"));
                    if !children.is_empty() {
                        s.field(&children);
                    }
                    s.finish()
                })
            }

            s.field(&fmt_block(self, root));
        }

        s.finish()
    }
}

/// Methods for querying the dominator tree.
impl DominatorTree {
    /// Is `block` reachable from the entry block?
    pub fn is_reachable(&self, block: Block) -> bool {
        self.nodes[block].pre_number != NOT_VISITED
    }

    /// Get the CFG post-order of blocks that was used to compute the dominator tree.
    ///
    /// Note that this post-order is not updated automatically when the CFG is modified. It is
    /// computed from scratch and cached by `compute()`.
    pub fn cfg_postorder(&self) -> &[Block] {
        debug_assert!(self.is_valid());
        &self.postorder
    }

    /// Get an iterator over CFG reverse post-order of blocks used to compute the dominator tree.
    ///
    /// Note that the post-order is not updated automatically when the CFG is modified. It is
    /// computed from scratch and cached by `compute()`.
    pub fn cfg_rpo(&self) -> impl Iterator<Item = &Block> {
        debug_assert!(self.is_valid());
        self.postorder.iter().rev()
    }

    /// Returns the immediate dominator of `block`.
    ///
    /// `block_a` is said to *dominate* `block_b` if all control flow paths from the function
    /// entry to `block_b` must go through `block_a`.
    ///
    /// The *immediate dominator* is the dominator that is closest to `block`. All other dominators
    /// also dominate the immediate dominator.
    ///
    /// This returns `None` if `block` is not reachable from the entry block, or if it is the entry block
    /// which has no dominators.
    pub fn idom(&self, block: Block) -> Option<Block> {
        self.nodes[block].idom.into()
    }

    /// Returns `true` if `a` dominates `b`.
    ///
    /// This means that every control-flow path from the function entry to `b` must go through `a`.
    ///
    /// Dominance is ill defined for unreachable blocks. This function can always determine
    /// dominance for instructions in the same block, but otherwise returns `false` if either block
    /// is unreachable.
    ///
    /// An instruction is considered to dominate itself.
    /// A block is also considered to dominate itself.
    pub fn dominates<A, B>(&self, a: A, b: B, layout: &Layout) -> bool
    where
        A: Into<ProgramPoint>,
        B: Into<ProgramPoint>,
    {
        let a = a.into();
        let b = b.into();
        match a {
            ProgramPoint::Block(block_a) => match b {
                ProgramPoint::Block(block_b) => self.block_dominates(block_a, block_b),
                ProgramPoint::Inst(inst_b) => {
                    let block_b = layout
                        .inst_block(inst_b)
                        .expect("Instruction not in layout.");
                    self.block_dominates(block_a, block_b)
                }
            },
            ProgramPoint::Inst(inst_a) => {
                let block_a: Block = layout
                    .inst_block(inst_a)
                    .expect("Instruction not in layout.");
                match b {
                    ProgramPoint::Block(block_b) => {
                        block_a != block_b && self.block_dominates(block_a, block_b)
                    }
                    ProgramPoint::Inst(inst_b) => {
                        let block_b = layout
                            .inst_block(inst_b)
                            .expect("Instruction not in layout.");
                        if block_a == block_b {
                            layout.pp_cmp(a, b) != Ordering::Greater
                        } else {
                            self.block_dominates(block_a, block_b)
                        }
                    }
                }
            }
        }
    }

    /// Returns `true` if `block_a` dominates `block_b`.
    ///
    /// A block is considered to dominate itself.
    /// This uses preorder numbers for O(1) constant time performance.
    pub fn block_dominates(&self, block_a: Block, block_b: Block) -> bool {
        let na = &self.nodes[block_a];
        let nb = &self.nodes[block_b];
        na.dom_pre_number <= nb.dom_pre_number && na.dom_pre_max >= nb.dom_pre_max
    }

    /// Returns `true` if the CFG edge `from -> to` is a retreating edge.
    ///
    /// A retreating edge is one that goes from a block to one of its ancestors
    /// in the depth-first spanning tree used to compute this dominator tree, or
    /// to itself. Every cycle in the CFG contains at least one retreating edge,
    /// including irreducible cycles, which have no back edge whose target
    /// dominates its source. In a reducible CFG, the retreating edges are
    /// exactly its back edges.
    ///
    /// Both blocks must be reachable.
    pub fn is_retreating_edge(&self, from: Block, to: Block) -> bool {
        debug_assert!(self.is_reachable(from));
        debug_assert!(self.is_reachable(to));
        self.nodes[to].post_number >= self.nodes[from].post_number
    }

    /// Get an iterator over the direct children of `block` in the dominator tree.
    ///
    /// These are the blocks whose immediate dominator is `block`, ordered by
    /// decreasing CFG post-order number.
    pub fn children(&self, block: Block) -> ChildIter<'_> {
        ChildIter {
            domtree: self,
            next: self.nodes[block].child,
        }
    }
}

impl DominatorTree {
    /// Allocate a new blank dominator tree. Use `compute` to compute the dominator tree for a
    /// function.
    pub fn new() -> Self {
        Self {
            stree: SpanningTree::new(),
            nodes: SecondaryMap::new(),
            postorder: Vec::new(),
            dfs_worklist: Vec::new(),
            eval_worklist: Vec::new(),
            valid: false,
        }
    }

    /// Allocate and compute a dominator tree.
    pub fn with_function(func: &Function, cfg: &ControlFlowGraph) -> Self {
        let block_capacity = func.layout.block_capacity();
        let mut domtree = Self {
            stree: SpanningTree::with_capacity(block_capacity),
            nodes: SecondaryMap::with_capacity(block_capacity),
            postorder: Vec::with_capacity(block_capacity),
            dfs_worklist: Vec::new(),
            eval_worklist: Vec::new(),
            valid: false,
        };
        domtree.compute(func, cfg);
        domtree
    }

    /// Reset and compute a CFG post-order and dominator tree,
    /// using Semi-NCA algorithm, described in the paper:
    ///
    /// Linear-Time Algorithms for Dominators and Related Problems.
    /// Loukas Georgiadis, Princeton University, November 2005.
    ///
    /// The same algorithm is used by Julia, SpiderMonkey and LLVM,
    /// the implementation is heavily inspired by them.
    pub fn compute(&mut self, func: &Function, cfg: &ControlFlowGraph) {
        let _tt = timing::domtree();
        debug_assert!(cfg.is_valid());
        self.compute_from_graph(&ForwardGraph { func, cfg });
    }

    /// Reset and compute a post-order and dominator tree over an arbitrary
    /// `DomTreeGraph`.
    ///
    /// This is the shared core used both by `DominatorTree::compute` (over the
    /// control-flow graph) and by `PostDominatorTree` (over the reversed
    /// control-flow graph augmented with a virtual sink).
    pub(crate) fn compute_from_graph(&mut self, graph: &impl DomTreeGraph) {
        self.clear();
        self.compute_spanning_tree(graph);
        self.compute_domtree(graph);
        self.compute_domtree_preorder();

        self.valid = true;
    }

    /// Clear the data structures used to represent the dominator tree. This will leave the tree in
    /// a state where `is_valid()` returns false.
    pub fn clear(&mut self) {
        self.stree.clear();
        self.nodes.clear();
        self.postorder.clear();
        self.valid = false;
    }

    /// Check if the dominator tree is in a valid state.
    ///
    /// Note that this doesn't perform any kind of validity checks. It simply checks if the
    /// `compute()` method has been called since the last `clear()`. It does not check that the
    /// dominator tree is consistent with the CFG.
    pub fn is_valid(&self) -> bool {
        self.valid
    }

    /// Reset all internal data structures, build spanning tree
    /// and compute a post-order of the control flow graph.
    fn compute_spanning_tree(&mut self, graph: &impl DomTreeGraph) {
        self.nodes.resize(graph.num_blocks());
        self.stree.reserve(graph.num_blocks());

        for root in graph.roots() {
            self.dfs_worklist.push(TraversalEvent::Enter(0, root));
        }

        loop {
            match self.dfs_worklist.pop() {
                Some(TraversalEvent::Enter(parent, block)) => {
                    let node = &mut self.nodes[block];
                    if node.pre_number != NOT_VISITED {
                        continue;
                    }

                    self.dfs_worklist.push(TraversalEvent::Exit(block));

                    let pre_number = self.stree.push(parent, block);
                    node.pre_number = pre_number;

                    // Push successors in the analysis direction. Any ordering
                    // heuristic (such as the forward graph's `.rev()`) lives in
                    // the `DomTreeGraph` implementation.
                    self.dfs_worklist.extend(
                        graph
                            .successors(block)
                            // A simple optimization: push less items to the stack.
                            .filter(|successor| self.nodes[*successor].pre_number == NOT_VISITED)
                            .map(|successor| TraversalEvent::Enter(pre_number, successor)),
                    );
                }
                Some(TraversalEvent::Exit(block)) => {
                    self.nodes[block].post_number = u32::try_from(self.postorder.len()).unwrap();
                    self.postorder.push(block);
                }
                None => break,
            }
        }
    }

    /// Eval-link procedure from the paper.
    /// For a predecessor V of node W returns V if V < W, otherwise the minimum of sdom(U),
    /// where U > W and U is on a semi-dominator path for W in CFG.
    /// Use path compression to bring complexity down to O(m*log(n)).
    fn eval(&mut self, v: u32, last_linked: u32) -> u32 {
        if self.stree[v].ancestor < last_linked {
            return self.stree[v].label;
        }

        // Follow semi-dominator path.
        let mut root = v;
        loop {
            self.eval_worklist.push(root);
            root = self.stree[root].ancestor;

            if self.stree[root].ancestor < last_linked {
                break;
            }
        }

        let mut prev = root;
        let root = self.stree[prev].ancestor;

        // Perform path compression. Point all ancestors to the root
        // and propagate minimal sdom(U) value from ancestors to children.
        while let Some(curr) = self.eval_worklist.pop() {
            if self.stree[prev].label < self.stree[curr].label {
                self.stree[curr].label = self.stree[prev].label;
            }

            self.stree[curr].ancestor = root;
            prev = curr;
        }

        self.stree[v].label
    }

    fn compute_domtree(&mut self, graph: &impl DomTreeGraph) {
        // Compute semi-dominators.
        for w in (1..self.stree.len() as u32).rev() {
            let w_node = &mut self.stree[w];
            let block = w_node.block.expect("Virtual root must have been excluded");
            let mut semi = w_node.ancestor;

            let last_linked = w + 1;

            for pred in graph.predecessors(block) {
                // Skip unreachable nodes.
                if self.nodes[pred].pre_number == NOT_VISITED {
                    continue;
                }

                let semi_candidate = self.eval(self.nodes[pred].pre_number, last_linked);
                semi = core::cmp::min(semi, semi_candidate);
            }

            let w_node = &mut self.stree[w];
            w_node.label = semi;
            w_node.semi = semi;
        }

        // Compute immediate dominators.
        for v in 1..self.stree.len() as u32 {
            let semi = self.stree[v].semi;
            let block = self.stree[v]
                .block
                .expect("Virtual root must have been excluded");
            let mut idom = self.stree[v].idom;

            while idom > semi {
                idom = self.stree[idom].idom;
            }

            self.stree[v].idom = idom;

            self.nodes[block].idom = self.stree[idom].block;
        }
    }

    /// Compute dominator tree preorder information.
    ///
    /// This populates child/sibling links and preorder numbers for fast dominance checks.
    fn compute_domtree_preorder(&mut self) {
        // Populate the child and sibling links.
        //
        // By following the CFG post-order and pushing to the front of the lists, we make sure that
        // sibling lists are ordered according to the CFG reverse post-order (i.e. decreasing CFG
        // post-order number).
        for &block in &self.postorder {
            if let Some(idom) = self.idom(block) {
                let sib = mem::replace(&mut self.nodes[idom].child, block.into());
                self.nodes[block].sibling = sib;
            } else {
                // Blocks without an immediate dominator are the roots of the
                // (post-)dominator forest: the entry block for the forward tree,
                // or the exit blocks for a post-dominator tree.
                self.dfs_worklist.push(TraversalEvent::Enter(0, block));
            }
        }

        // Assign pre-order numbers from a DFS of the dominator tree.
        //
        // The worklist now holds every root of the (post-)dominator forest: a
        // single entry block for the forward `DominatorTree`, but possibly many
        // (one per exit block) for a post-dominator forest. Each root begins a
        // disjoint subtree, so the numbering below assigns each its own
        // contiguous `dom_pre_number` range.
        let mut n = 0;
        while let Some(event) = self.dfs_worklist.pop() {
            if let TraversalEvent::Enter(_, block) = event {
                n += 1;
                let node = &mut self.nodes[block];
                node.dom_pre_number = n;
                node.dom_pre_max = n;
                if let Some(sibling) = node.sibling.expand() {
                    self.dfs_worklist.push(TraversalEvent::Enter(0, sibling));
                }
                if let Some(child) = node.child.expand() {
                    self.dfs_worklist.push(TraversalEvent::Enter(0, child));
                }
            }
        }

        // Propagate the `dom_pre_max` numbers up the tree.
        // The CFG post-order is topologically ordered w.r.t. dominance so a node comes after all
        // its dominator tree children.
        for &block in &self.postorder {
            if let Some(idom) = self.idom(block) {
                let pre_max = cmp::max(self.nodes[block].dom_pre_max, self.nodes[idom].dom_pre_max);
                self.nodes[idom].dom_pre_max = pre_max;
            }
        }
    }
}

/// An iterator that enumerates the direct children of a block in the dominator tree.
pub struct ChildIter<'a> {
    domtree: &'a DominatorTree,
    next: PackedOption<Block>,
}

impl<'a> Iterator for ChildIter<'a> {
    type Item = Block;

    fn next(&mut self) -> Option<Block> {
        let n = self.next.expand();
        if let Some(block) = n {
            self.next = self.domtree.nodes[block].sibling;
        }
        n
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::cursor::{Cursor, FuncCursor};
    use crate::ir::types::*;
    use crate::ir::{InstBuilder, TrapCode};

    #[test]
    fn empty() {
        let func = Function::new();
        let cfg = ControlFlowGraph::with_function(&func);
        debug_assert!(cfg.is_valid());
        let dtree = DominatorTree::with_function(&func, &cfg);
        assert_eq!(0, dtree.nodes.keys().count());
        assert_eq!(dtree.cfg_postorder(), &[]);
    }

    #[test]
    fn unreachable_node() {
        let mut func = Function::new();
        let block0 = func.dfg.make_block();
        let v0 = func.dfg.append_block_param(block0, I32);
        let block1 = func.dfg.make_block();
        let block2 = func.dfg.make_block();
        let trap_block = func.dfg.make_block();

        let mut cur = FuncCursor::new(&mut func);

        cur.insert_block(block0);
        cur.ins().brif(v0, block2, &[], trap_block, &[]);

        cur.insert_block(trap_block);
        cur.ins().trap(TrapCode::unwrap_user(1));

        cur.insert_block(block1);
        let v1 = cur.ins().iconst(I32, 1);
        let v2 = cur.ins().iadd(v0, v1);
        cur.ins().jump(block0, &[v2.into()]);

        cur.insert_block(block2);
        cur.ins().return_(&[v0]);

        let cfg = ControlFlowGraph::with_function(cur.func);
        let dt = DominatorTree::with_function(cur.func, &cfg);

        // Fall-through-first, prune-at-source DFT:
        //
        // block0 {
        //   brif block2 {
        //     trap
        //     block2 {
        //       return
        //     } block2
        // } block0
        assert_eq!(dt.cfg_postorder(), &[block2, trap_block, block0]);

        let v2_def = cur.func.dfg.value_def(v2).unwrap_inst();
        assert!(!dt.dominates(v2_def, block0, &cur.func.layout));
        assert!(!dt.dominates(block0, v2_def, &cur.func.layout));

        assert!(dt.block_dominates(block0, block0));
        assert!(!dt.block_dominates(block0, block1));
        assert!(dt.block_dominates(block0, block2));
        assert!(!dt.block_dominates(block1, block0));
        assert!(dt.block_dominates(block1, block1));
        assert!(!dt.block_dominates(block1, block2));
        assert!(!dt.block_dominates(block2, block0));
        assert!(!dt.block_dominates(block2, block1));
        assert!(dt.block_dominates(block2, block2));
    }

    #[test]
    fn non_zero_entry_block() {
        let mut func = Function::new();
        let block0 = func.dfg.make_block();
        let block1 = func.dfg.make_block();
        let block2 = func.dfg.make_block();
        let block3 = func.dfg.make_block();
        let cond = func.dfg.append_block_param(block3, I32);

        let mut cur = FuncCursor::new(&mut func);

        cur.insert_block(block3);
        let jmp_block3_block1 = cur.ins().jump(block1, &[]);

        cur.insert_block(block1);
        let br_block1_block0_block2 = cur.ins().brif(cond, block0, &[], block2, &[]);

        cur.insert_block(block2);
        cur.ins().jump(block0, &[]);

        cur.insert_block(block0);

        let cfg = ControlFlowGraph::with_function(cur.func);
        let dt = DominatorTree::with_function(cur.func, &cfg);

        // Fall-through-first, prune-at-source DFT:
        //
        // block3 {
        //   block3:jump block1 {
        //     block1 {
        //       block1:brif block0 {
        //         block1:jump block2 {
        //           block2 {
        //             block2:jump block0 (seen)
        //           } block2
        //         } block1:jump block2
        //         block0 {
        //         } block0
        //       } block1:brif block0
        //     } block1
        //   } block3:jump block1
        // } block3

        assert_eq!(dt.cfg_postorder(), &[block0, block2, block1, block3]);

        assert_eq!(cur.func.layout.entry_block().unwrap(), block3);
        assert_eq!(dt.idom(block3), None);
        assert_eq!(dt.idom(block1).unwrap(), block3);
        assert_eq!(dt.idom(block2).unwrap(), block1);
        assert_eq!(dt.idom(block0).unwrap(), block1);

        assert!(dt.dominates(
            br_block1_block0_block2,
            br_block1_block0_block2,
            &cur.func.layout
        ));
        assert!(!dt.dominates(br_block1_block0_block2, jmp_block3_block1, &cur.func.layout));
        assert!(dt.dominates(jmp_block3_block1, br_block1_block0_block2, &cur.func.layout));
    }

    #[test]
    fn backwards_layout() {
        let mut func = Function::new();
        let block0 = func.dfg.make_block();
        let block1 = func.dfg.make_block();
        let block2 = func.dfg.make_block();

        let mut cur = FuncCursor::new(&mut func);

        cur.insert_block(block0);
        let jmp02 = cur.ins().jump(block2, &[]);

        cur.insert_block(block1);
        let trap = cur.ins().trap(TrapCode::unwrap_user(5));

        cur.insert_block(block2);
        let jmp21 = cur.ins().jump(block1, &[]);

        let cfg = ControlFlowGraph::with_function(cur.func);
        let dt = DominatorTree::with_function(cur.func, &cfg);

        assert_eq!(cur.func.layout.entry_block(), Some(block0));
        assert_eq!(dt.idom(block0), None);
        assert_eq!(dt.idom(block1), Some(block2));
        assert_eq!(dt.idom(block2), Some(block0));

        assert!(dt.dominates(block0, block0, &cur.func.layout));
        assert!(dt.dominates(block0, jmp02, &cur.func.layout));
        assert!(dt.dominates(block0, block1, &cur.func.layout));
        assert!(dt.dominates(block0, trap, &cur.func.layout));
        assert!(dt.dominates(block0, block2, &cur.func.layout));
        assert!(dt.dominates(block0, jmp21, &cur.func.layout));

        assert!(!dt.dominates(jmp02, block0, &cur.func.layout));
        assert!(dt.dominates(jmp02, jmp02, &cur.func.layout));
        assert!(dt.dominates(jmp02, block1, &cur.func.layout));
        assert!(dt.dominates(jmp02, trap, &cur.func.layout));
        assert!(dt.dominates(jmp02, block2, &cur.func.layout));
        assert!(dt.dominates(jmp02, jmp21, &cur.func.layout));

        assert!(!dt.dominates(block1, block0, &cur.func.layout));
        assert!(!dt.dominates(block1, jmp02, &cur.func.layout));
        assert!(dt.dominates(block1, block1, &cur.func.layout));
        assert!(dt.dominates(block1, trap, &cur.func.layout));
        assert!(!dt.dominates(block1, block2, &cur.func.layout));
        assert!(!dt.dominates(block1, jmp21, &cur.func.layout));

        assert!(!dt.dominates(trap, block0, &cur.func.layout));
        assert!(!dt.dominates(trap, jmp02, &cur.func.layout));
        assert!(!dt.dominates(trap, block1, &cur.func.layout));
        assert!(dt.dominates(trap, trap, &cur.func.layout));
        assert!(!dt.dominates(trap, block2, &cur.func.layout));
        assert!(!dt.dominates(trap, jmp21, &cur.func.layout));

        assert!(!dt.dominates(block2, block0, &cur.func.layout));
        assert!(!dt.dominates(block2, jmp02, &cur.func.layout));
        assert!(dt.dominates(block2, block1, &cur.func.layout));
        assert!(dt.dominates(block2, trap, &cur.func.layout));
        assert!(dt.dominates(block2, block2, &cur.func.layout));
        assert!(dt.dominates(block2, jmp21, &cur.func.layout));

        assert!(!dt.dominates(jmp21, block0, &cur.func.layout));
        assert!(!dt.dominates(jmp21, jmp02, &cur.func.layout));
        assert!(dt.dominates(jmp21, block1, &cur.func.layout));
        assert!(dt.dominates(jmp21, trap, &cur.func.layout));
        assert!(!dt.dominates(jmp21, block2, &cur.func.layout));
        assert!(dt.dominates(jmp21, jmp21, &cur.func.layout));
    }

    #[test]
    fn retreating_edges() {
        let mut func = Function::new();
        let block0 = func.dfg.make_block();
        let v0 = func.dfg.append_block_param(block0, I32);
        let block1 = func.dfg.make_block();
        let block2 = func.dfg.make_block();
        let block3 = func.dfg.make_block();
        let block4 = func.dfg.make_block();
        let block5 = func.dfg.make_block();

        let mut cur = FuncCursor::new(&mut func);

        // An irreducible cycle between `block1` and `block2`, each of which can
        // be entered directly from `block0`.
        cur.insert_block(block0);
        cur.ins().brif(v0, block1, &[], block2, &[]);

        cur.insert_block(block1);
        cur.ins().brif(v0, block2, &[], block3, &[]);

        cur.insert_block(block2);
        cur.ins().jump(block1, &[]);

        // A natural loop with header `block3` and back edge `block4 -> block3`.
        cur.insert_block(block3);
        cur.ins().jump(block4, &[]);

        cur.insert_block(block4);
        cur.ins().brif(v0, block3, &[], block5, &[]);

        // A self-loop.
        cur.insert_block(block5);
        cur.ins().brif(v0, block5, &[], block1, &[]);

        let cfg = ControlFlowGraph::with_function(cur.func);
        let dt = DominatorTree::with_function(cur.func, &cfg);

        // Exactly one edge of the irreducible cycle retreats, depending on which
        // of its blocks the DFS entered first. Neither block dominates the
        // other.
        assert!(!dt.block_dominates(block1, block2));
        assert!(!dt.block_dominates(block2, block1));
        assert_ne!(
            dt.is_retreating_edge(block1, block2),
            dt.is_retreating_edge(block2, block1),
        );

        assert!(dt.is_retreating_edge(block4, block3));
        assert!(dt.is_retreating_edge(block5, block5));
        assert!(dt.is_retreating_edge(block5, block1));

        assert!(!dt.is_retreating_edge(block0, block1));
        assert!(!dt.is_retreating_edge(block0, block2));
        assert!(!dt.is_retreating_edge(block1, block3));
        assert!(!dt.is_retreating_edge(block3, block4));
        assert!(!dt.is_retreating_edge(block4, block5));
    }

    #[test]
    fn insts_same_block() {
        let mut func = Function::new();
        let block0 = func.dfg.make_block();

        let mut cur = FuncCursor::new(&mut func);

        cur.insert_block(block0);
        let v1 = cur.ins().iconst(I32, 1);
        let v2 = cur.ins().iadd(v1, v1);
        let v3 = cur.ins().iadd(v2, v2);
        cur.ins().return_(&[]);

        let cfg = ControlFlowGraph::with_function(cur.func);
        let dt = DominatorTree::with_function(cur.func, &cfg);

        let v1_def = cur.func.dfg.value_def(v1).unwrap_inst();
        let v2_def = cur.func.dfg.value_def(v2).unwrap_inst();
        let v3_def = cur.func.dfg.value_def(v3).unwrap_inst();

        assert!(dt.dominates(v1_def, v2_def, &cur.func.layout));
        assert!(dt.dominates(v2_def, v3_def, &cur.func.layout));
        assert!(dt.dominates(v1_def, v3_def, &cur.func.layout));

        assert!(!dt.dominates(v2_def, v1_def, &cur.func.layout));
        assert!(!dt.dominates(v3_def, v2_def, &cur.func.layout));
        assert!(!dt.dominates(v3_def, v1_def, &cur.func.layout));

        assert!(dt.dominates(v2_def, v2_def, &cur.func.layout));
        assert!(dt.dominates(block0, block0, &cur.func.layout));

        assert!(dt.dominates(block0, v1_def, &cur.func.layout));
        assert!(dt.dominates(block0, v2_def, &cur.func.layout));
        assert!(dt.dominates(block0, v3_def, &cur.func.layout));

        assert!(!dt.dominates(v1_def, block0, &cur.func.layout));
        assert!(!dt.dominates(v2_def, block0, &cur.func.layout));
        assert!(!dt.dominates(v3_def, block0, &cur.func.layout));
    }
}