Method eval

cranelift/codegen/src/dominator_tree.rs:433–464

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)).

(&mut self, v: u32, last_linked: u32)

    /// 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, cfg: &ControlFlowGraph) {
        // Compute semi-dominators.