regalloc2/
domtree.rs

1/*
2 * Derives from the dominator tree implementation in regalloc.rs, which is
3 * licensed under the Apache Public License 2.0 with LLVM Exception. See:
4 * https://github.com/bytecodealliance/regalloc.rs
5 */
6
7// This is an implementation of the algorithm described in
8//
9//   A Simple, Fast Dominance Algorithm
10//   Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy
11//   Department of Computer Science, Rice University, Houston, Texas, USA
12//   TR-06-33870
13//   https://www.cs.rice.edu/~keith/EMBED/dom.pdf
14
15use crate::Block;
16
17// Helper
18fn merge_sets(
19    idom: &[Block], // map from Block to Block
20    block_to_rpo: &[Option<u32>],
21    mut node1: Block,
22    mut node2: Block,
23) -> Block {
24    while node1 != node2 {
25        if node1.is_invalid() || node2.is_invalid() {
26            return Block::invalid();
27        }
28        let rpo1 = block_to_rpo[node1.index()].unwrap();
29        let rpo2 = block_to_rpo[node2.index()].unwrap();
30        if rpo1 > rpo2 {
31            node1 = idom[node1.index()];
32        } else if rpo2 > rpo1 {
33            node2 = idom[node2.index()];
34        }
35    }
36    debug_assert!(node1 == node2);
37    node1
38}
39
40pub fn calculate<'a, PredFn: Fn(Block) -> &'a [Block]>(
41    num_blocks: usize,
42    preds: PredFn,
43    post_ord: &[Block],
44    start: Block,
45) -> Vec<Block> {
46    // We have post_ord, which is the postorder sequence.
47
48    // Compute maps from RPO to block number and vice-versa.
49    let mut block_to_rpo = vec![None; num_blocks];
50    block_to_rpo.resize(num_blocks, None);
51    for (i, rpo_block) in post_ord.iter().rev().enumerate() {
52        block_to_rpo[rpo_block.index()] = Some(i as u32);
53    }
54
55    let mut idom = vec![Block::invalid(); num_blocks];
56
57    // The start node must have itself as a parent.
58    idom[start.index()] = start;
59
60    let mut changed = true;
61    while changed {
62        changed = false;
63        // Consider blocks in reverse postorder. Skip any that are unreachable.
64        for &node in post_ord.iter().rev() {
65            let rponum = block_to_rpo[node.index()].unwrap();
66
67            let mut parent = Block::invalid();
68            for &pred in preds(node).iter() {
69                let pred_rpo = match block_to_rpo[pred.index()] {
70                    Some(r) => r,
71                    None => {
72                        // Skip unreachable preds.
73                        continue;
74                    }
75                };
76                if pred_rpo < rponum {
77                    parent = pred;
78                    break;
79                }
80            }
81
82            if parent.is_valid() {
83                for &pred in preds(node).iter() {
84                    if pred == parent {
85                        continue;
86                    }
87                    if idom[pred.index()].is_invalid() {
88                        continue;
89                    }
90                    parent = merge_sets(&idom, &block_to_rpo[..], parent, pred);
91                }
92            }
93
94            if parent.is_valid() && parent != idom[node.index()] {
95                idom[node.index()] = parent;
96                changed = true;
97            }
98        }
99    }
100
101    // Now set the start node's dominator-tree parent to "invalid";
102    // this allows the loop in `dominates` to terminate.
103    idom[start.index()] = Block::invalid();
104
105    idom
106}
107
108pub fn dominates(idom: &[Block], a: Block, mut b: Block) -> bool {
109    loop {
110        if a == b {
111            return true;
112        }
113        if b.is_invalid() {
114            return false;
115        }
116        b = idom[b.index()];
117    }
118}
regalloc2/domtree.rs

regalloc2/
domtree.rs
