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