Method compute

cranelift/codegen/src/dominator_tree.rs:350–360

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.

(&mut self, func: &Function, cfg: &ControlFlowGraph)

    /// 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.clear();
        self.compute_spanning_tree(func);
        self.compute_domtree(cfg);
        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.