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 core::u32;
16
17use alloc::vec::Vec;
18
19use crate::{Block, VecExt};
20
21// Helper
22fn merge_sets(
23    idom: &[Block], // map from Block to Block
24    block_to_rpo: &[Option<u32>],
25    mut node1: Block,
26    mut node2: Block,
27) -> Block {
28    while node1 != node2 {
29        if node1.is_invalid() || node2.is_invalid() {
30            return Block::invalid();
31        }
32        let rpo1 = block_to_rpo[node1.index()].unwrap();
33        let rpo2 = block_to_rpo[node2.index()].unwrap();
34        if rpo1 > rpo2 {
35            node1 = idom[node1.index()];
36        } else if rpo2 > rpo1 {
37            node2 = idom[node2.index()];
38        }
39    }
40    debug_assert!(node1 == node2);
41    node1
42}
43
44pub fn calculate<'a, PredFn: Fn(Block) -> &'a [Block]>(
45    num_blocks: usize,
46    preds: PredFn,
47    post_ord: &[Block],
48    block_to_rpo_scratch: &mut Vec<Option<u32>>,
49    out: &mut Vec<Block>,
50    start: Block,
51) {
52    // We have post_ord, which is the postorder sequence.
53    // Compute maps from RPO to block number and vice-versa.
54    let block_to_rpo = block_to_rpo_scratch.repopulate(num_blocks, None);
55    for (i, rpo_block) in post_ord.iter().rev().enumerate() {
56        block_to_rpo[rpo_block.index()] = Some(i as u32);
57    }
58
59    let idom = out.repopulate(num_blocks, Block::invalid());
60    // The start node must have itself as a parent.
61    idom[start.index()] = start;
62
63    let mut changed = true;
64    while changed {
65        changed = false;
66        // Consider blocks in reverse postorder. Skip any that are unreachable.
67        for &node in post_ord.iter().rev() {
68            let rponum = block_to_rpo[node.index()].unwrap();
69
70            let mut parent = Block::invalid();
71            for &pred in preds(node).iter() {
72                let pred_rpo = match block_to_rpo[pred.index()] {
73                    None => {
74                        // Skip unreachable preds.
75                        continue;
76                    }
77                    Some(r) => r,
78                };
79                if pred_rpo < rponum {
80                    parent = pred;
81                    break;
82                }
83            }
84
85            if parent.is_valid() {
86                for &pred in preds(node).iter() {
87                    if pred == parent {
88                        continue;
89                    }
90                    if idom[pred.index()].is_invalid() {
91                        continue;
92                    }
93                    parent = merge_sets(&idom, &block_to_rpo[..], parent, pred);
94                }
95            }
96
97            if parent.is_valid() && parent != idom[node.index()] {
98                idom[node.index()] = parent;
99                changed = true;
100            }
101        }
102    }
103
104    // Now set the start node's dominator-tree parent to "invalid";
105    // this allows the loop in `dominates` to terminate.
106    idom[start.index()] = Block::invalid();
107}
108
109pub fn dominates(idom: &[Block], a: Block, mut b: Block) -> bool {
110    loop {
111        if a == b {
112            return true;
113        }
114        if b.is_invalid() {
115            return false;
116        }
117        b = idom[b.index()];
118    }
119}
regalloc2/domtree.rs

regalloc2/
domtree.rs
