]>
Commit | Line | Data |
---|---|---|
f035d41b XL |
1 | //! Finding the dominators in a control-flow graph. |
2 | //! | |
3 | //! Algorithm based on Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy, | |
4 | //! "A Simple, Fast Dominance Algorithm", | |
5 | //! Rice Computer Science TS-06-33870, | |
6 | //! <https://www.cs.rice.edu/~keith/EMBED/dom.pdf>. | |
3157f602 | 7 | |
3157f602 | 8 | use super::iterate::reverse_post_order; |
8faf50e0 | 9 | use super::ControlFlowGraph; |
dfeec247 | 10 | use rustc_index::vec::{Idx, IndexVec}; |
29967ef6 | 11 | use std::cmp::Ordering; |
3157f602 | 12 | |
3157f602 | 13 | #[cfg(test)] |
416331ca | 14 | mod tests; |
3157f602 | 15 | |
60c5eb7d | 16 | pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> { |
3157f602 | 17 | let start_node = graph.start_node(); |
60c5eb7d | 18 | let rpo = reverse_post_order(&graph, start_node); |
3157f602 XL |
19 | dominators_given_rpo(graph, &rpo) |
20 | } | |
21 | ||
5869c6ff XL |
22 | fn dominators_given_rpo<G: ControlFlowGraph>(graph: G, rpo: &[G::Node]) -> Dominators<G::Node> { |
23 | let start_node = graph.start_node(); | |
3157f602 XL |
24 | assert_eq!(rpo[0], start_node); |
25 | ||
26 | // compute the post order index (rank) for each node | |
5869c6ff | 27 | let mut post_order_rank = IndexVec::from_elem_n(0, graph.num_nodes()); |
3157f602 XL |
28 | for (index, node) in rpo.iter().rev().cloned().enumerate() { |
29 | post_order_rank[node] = index; | |
30 | } | |
31 | ||
5869c6ff | 32 | let mut immediate_dominators = IndexVec::from_elem_n(None, graph.num_nodes()); |
3157f602 XL |
33 | immediate_dominators[start_node] = Some(start_node); |
34 | ||
35 | let mut changed = true; | |
36 | while changed { | |
37 | changed = false; | |
38 | ||
39 | for &node in &rpo[1..] { | |
40 | let mut new_idom = None; | |
5869c6ff | 41 | for pred in graph.predecessors(node) { |
3157f602 | 42 | if immediate_dominators[pred].is_some() { |
3157f602 | 43 | // (*) dominators for `pred` have been calculated |
e74abb32 XL |
44 | new_idom = Some(if let Some(new_idom) = new_idom { |
45 | intersect(&post_order_rank, &immediate_dominators, new_idom, pred) | |
46 | } else { | |
47 | pred | |
48 | }); | |
3157f602 XL |
49 | } |
50 | } | |
51 | ||
52 | if new_idom != immediate_dominators[node] { | |
53 | immediate_dominators[node] = new_idom; | |
54 | changed = true; | |
55 | } | |
56 | } | |
57 | } | |
58 | ||
dfeec247 | 59 | Dominators { post_order_rank, immediate_dominators } |
3157f602 XL |
60 | } |
61 | ||
8faf50e0 XL |
62 | fn intersect<Node: Idx>( |
63 | post_order_rank: &IndexVec<Node, usize>, | |
64 | immediate_dominators: &IndexVec<Node, Option<Node>>, | |
65 | mut node1: Node, | |
66 | mut node2: Node, | |
67 | ) -> Node { | |
3157f602 XL |
68 | while node1 != node2 { |
69 | while post_order_rank[node1] < post_order_rank[node2] { | |
70 | node1 = immediate_dominators[node1].unwrap(); | |
71 | } | |
72 | ||
73 | while post_order_rank[node2] < post_order_rank[node1] { | |
74 | node2 = immediate_dominators[node2].unwrap(); | |
75 | } | |
76 | } | |
b7449926 XL |
77 | |
78 | node1 | |
3157f602 XL |
79 | } |
80 | ||
81 | #[derive(Clone, Debug)] | |
82 | pub struct Dominators<N: Idx> { | |
83 | post_order_rank: IndexVec<N, usize>, | |
84 | immediate_dominators: IndexVec<N, Option<N>>, | |
85 | } | |
86 | ||
87 | impl<Node: Idx> Dominators<Node> { | |
6a06907d XL |
88 | pub fn dummy() -> Self { |
89 | Self { post_order_rank: IndexVec::new(), immediate_dominators: IndexVec::new() } | |
90 | } | |
91 | ||
3157f602 XL |
92 | pub fn is_reachable(&self, node: Node) -> bool { |
93 | self.immediate_dominators[node].is_some() | |
94 | } | |
95 | ||
96 | pub fn immediate_dominator(&self, node: Node) -> Node { | |
97 | assert!(self.is_reachable(node), "node {:?} is not reachable", node); | |
98 | self.immediate_dominators[node].unwrap() | |
99 | } | |
100 | ||
9fa01778 | 101 | pub fn dominators(&self, node: Node) -> Iter<'_, Node> { |
3157f602 | 102 | assert!(self.is_reachable(node), "node {:?} is not reachable", node); |
dfeec247 | 103 | Iter { dominators: self, node: Some(node) } |
3157f602 XL |
104 | } |
105 | ||
106 | pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool { | |
107 | // FIXME -- could be optimized by using post-order-rank | |
108 | self.dominators(node).any(|n| n == dom) | |
109 | } | |
29967ef6 XL |
110 | |
111 | /// Provide deterministic ordering of nodes such that, if any two nodes have a dominator | |
112 | /// relationship, the dominator will always precede the dominated. (The relative ordering | |
113 | /// of two unrelated nodes will also be consistent, but otherwise the order has no | |
114 | /// meaning.) This method cannot be used to determine if either Node dominates the other. | |
115 | pub fn rank_partial_cmp(&self, lhs: Node, rhs: Node) -> Option<Ordering> { | |
116 | self.post_order_rank[lhs].partial_cmp(&self.post_order_rank[rhs]) | |
117 | } | |
3157f602 XL |
118 | } |
119 | ||
9fa01778 | 120 | pub struct Iter<'dom, Node: Idx> { |
3157f602 XL |
121 | dominators: &'dom Dominators<Node>, |
122 | node: Option<Node>, | |
123 | } | |
124 | ||
125 | impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> { | |
126 | type Item = Node; | |
127 | ||
128 | fn next(&mut self) -> Option<Self::Item> { | |
129 | if let Some(node) = self.node { | |
130 | let dom = self.dominators.immediate_dominator(node); | |
131 | if dom == node { | |
132 | self.node = None; // reached the root | |
133 | } else { | |
134 | self.node = Some(dom); | |
135 | } | |
ba9703b0 | 136 | Some(node) |
3157f602 | 137 | } else { |
ba9703b0 | 138 | None |
3157f602 XL |
139 | } |
140 | } | |
141 | } |