Method compute_spanning_tree

cranelift/codegen/src/dominator_tree.rs:382–427

Reset all internal data structures, build spanning tree and compute a post-order of the control flow graph.

(&mut self, func: &Function)

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

        if let Some(block) = func.layout.entry_block() {
            self.dfs_worklist.push(TraversalEvent::Enter(0, block));
        }

        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;

                    // Use the same traversal heuristics as in traversals.rs.
                    self.dfs_worklist.extend(
                        func.block_successors(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.
                            .rev()
                            // 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.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),