1 //! Compute dominators of a control-flow graph.
2 //!
3 //! # The Dominance Relation
4 //!
5 //! In a directed graph with a root node **R**, a node **A** is said to *dominate* a
6 //! node **B** iff every path from **R** to **B** contains **A**.
7 //!
8 //! The node **A** is said to *strictly dominate* the node **B** iff **A** dominates
9 //! **B** and **A ≠ B**.
10 //!
11 //! The node **A** is said to be the *immediate dominator* of a node **B** iff it
12 //! strictly dominates **B** and there does not exist any node **C** where **A**
13 //! dominates **C** and **C** dominates **B**.
14
15 use std::cmp::Ordering;
16 use std::collections::{hash_map::Iter, HashMap, HashSet};
17 use std::hash::Hash;
18
19 use crate::visit::{DfsPostOrder, GraphBase, IntoNeighbors, Visitable, Walker};
20
21 /// The dominance relation for some graph and root.
22 #[derive(Debug, Clone)]
23 pub struct Dominators<N>
24 where
25 N: Copy + Eq + Hash,
26 {
27 root: N,
28 dominators: HashMap<N, N>,
29 }
30
31 impl<N> Dominators<N>
32 where
33 N: Copy + Eq + Hash,
34 {
35 /// Get the root node used to construct these dominance relations.
root(&self) -> N36 pub fn root(&self) -> N {
37 self.root
38 }
39
40 /// Get the immediate dominator of the given node.
41 ///
42 /// Returns `None` for any node that is not reachable from the root, and for
43 /// the root itself.
immediate_dominator(&self, node: N) -> Option<N>44 pub fn immediate_dominator(&self, node: N) -> Option<N> {
45 if node == self.root {
46 None
47 } else {
48 self.dominators.get(&node).cloned()
49 }
50 }
51
52 /// Iterate over the given node's strict dominators.
53 ///
54 /// If the given node is not reachable from the root, then `None` is
55 /// returned.
strict_dominators(&self, node: N) -> Option<DominatorsIter<N>>56 pub fn strict_dominators(&self, node: N) -> Option<DominatorsIter<N>> {
57 if self.dominators.contains_key(&node) {
58 Some(DominatorsIter {
59 dominators: self,
60 node: self.immediate_dominator(node),
61 })
62 } else {
63 None
64 }
65 }
66
67 /// Iterate over all of the given node's dominators (including the given
68 /// node itself).
69 ///
70 /// If the given node is not reachable from the root, then `None` is
71 /// returned.
dominators(&self, node: N) -> Option<DominatorsIter<N>>72 pub fn dominators(&self, node: N) -> Option<DominatorsIter<N>> {
73 if self.dominators.contains_key(&node) {
74 Some(DominatorsIter {
75 dominators: self,
76 node: Some(node),
77 })
78 } else {
79 None
80 }
81 }
82
83 /// Iterate over all nodes immediately dominated by the given node (not
84 /// including the given node itself).
immediately_dominated_by(&self, node: N) -> DominatedByIter<N>85 pub fn immediately_dominated_by(&self, node: N) -> DominatedByIter<N> {
86 DominatedByIter {
87 iter: self.dominators.iter(),
88 node,
89 }
90 }
91 }
92
93 /// Iterator for a node's dominators.
94 #[derive(Debug, Clone)]
95 pub struct DominatorsIter<'a, N>
96 where
97 N: 'a + Copy + Eq + Hash,
98 {
99 dominators: &'a Dominators<N>,
100 node: Option<N>,
101 }
102
103 impl<'a, N> Iterator for DominatorsIter<'a, N>
104 where
105 N: 'a + Copy + Eq + Hash,
106 {
107 type Item = N;
108
next(&mut self) -> Option<Self::Item>109 fn next(&mut self) -> Option<Self::Item> {
110 let next = self.node.take();
111 if let Some(next) = next {
112 self.node = self.dominators.immediate_dominator(next);
113 }
114 next
115 }
116 }
117
118 /// Iterator for nodes dominated by a given node.
119 #[derive(Debug, Clone)]
120 pub struct DominatedByIter<'a, N>
121 where
122 N: 'a + Copy + Eq + Hash,
123 {
124 iter: Iter<'a, N, N>,
125 node: N,
126 }
127
128 impl<'a, N> Iterator for DominatedByIter<'a, N>
129 where
130 N: 'a + Copy + Eq + Hash,
131 {
132 type Item = N;
133
next(&mut self) -> Option<Self::Item>134 fn next(&mut self) -> Option<Self::Item> {
135 for next in self.iter.by_ref() {
136 if next.1 == &self.node {
137 return Some(*next.0);
138 }
139 }
140 None
141 }
size_hint(&self) -> (usize, Option<usize>)142 fn size_hint(&self) -> (usize, Option<usize>) {
143 let (_, upper) = self.iter.size_hint();
144 (0, upper)
145 }
146 }
147
148 /// The undefined dominator sentinel, for when we have not yet discovered a
149 /// node's dominator.
150 const UNDEFINED: usize = ::std::usize::MAX;
151
152 /// This is an implementation of the engineered ["Simple, Fast Dominance
153 /// Algorithm"][0] discovered by Cooper et al.
154 ///
155 /// This algorithm is **O(|V|²)**, and therefore has slower theoretical running time
156 /// than the Lengauer-Tarjan algorithm (which is **O(|E| log |V|)**. However,
157 /// Cooper et al found it to be faster in practice on control flow graphs of up
158 /// to ~30,000 vertices.
159 ///
160 /// [0]: http://www.hipersoft.rice.edu/grads/publications/dom14.pdf
simple_fast<G>(graph: G, root: G::NodeId) -> Dominators<G::NodeId> where G: IntoNeighbors + Visitable, <G as GraphBase>::NodeId: Eq + Hash,161 pub fn simple_fast<G>(graph: G, root: G::NodeId) -> Dominators<G::NodeId>
162 where
163 G: IntoNeighbors + Visitable,
164 <G as GraphBase>::NodeId: Eq + Hash,
165 {
166 let (post_order, predecessor_sets) = simple_fast_post_order(graph, root);
167 let length = post_order.len();
168 debug_assert!(length > 0);
169 debug_assert!(post_order.last() == Some(&root));
170
171 // From here on out we use indices into `post_order` instead of actual
172 // `NodeId`s wherever possible. This greatly improves the performance of
173 // this implementation, but we have to pay a little bit of upfront cost to
174 // convert our data structures to play along first.
175
176 // Maps a node to its index into `post_order`.
177 let node_to_post_order_idx: HashMap<_, _> = post_order
178 .iter()
179 .enumerate()
180 .map(|(idx, &node)| (node, idx))
181 .collect();
182
183 // Maps a node's `post_order` index to its set of predecessors's indices
184 // into `post_order` (as a vec).
185 let idx_to_predecessor_vec =
186 predecessor_sets_to_idx_vecs(&post_order, &node_to_post_order_idx, predecessor_sets);
187
188 let mut dominators = vec![UNDEFINED; length];
189 dominators[length - 1] = length - 1;
190
191 let mut changed = true;
192 while changed {
193 changed = false;
194
195 // Iterate in reverse post order, skipping the root.
196
197 for idx in (0..length - 1).rev() {
198 debug_assert!(post_order[idx] != root);
199
200 // Take the intersection of every predecessor's dominator set; that
201 // is the current best guess at the immediate dominator for this
202 // node.
203
204 let new_idom_idx = {
205 let mut predecessors = idx_to_predecessor_vec[idx]
206 .iter()
207 .filter(|&&p| dominators[p] != UNDEFINED);
208 let new_idom_idx = predecessors.next().expect(
209 "Because the root is initialized to dominate itself, and is the \
210 first node in every path, there must exist a predecessor to this \
211 node that also has a dominator",
212 );
213 predecessors.fold(*new_idom_idx, |new_idom_idx, &predecessor_idx| {
214 intersect(&dominators, new_idom_idx, predecessor_idx)
215 })
216 };
217
218 debug_assert!(new_idom_idx < length);
219
220 if new_idom_idx != dominators[idx] {
221 dominators[idx] = new_idom_idx;
222 changed = true;
223 }
224 }
225 }
226
227 // All done! Translate the indices back into proper `G::NodeId`s.
228
229 debug_assert!(!dominators.iter().any(|&dom| dom == UNDEFINED));
230
231 Dominators {
232 root,
233 dominators: dominators
234 .into_iter()
235 .enumerate()
236 .map(|(idx, dom_idx)| (post_order[idx], post_order[dom_idx]))
237 .collect(),
238 }
239 }
240
intersect(dominators: &[usize], mut finger1: usize, mut finger2: usize) -> usize241 fn intersect(dominators: &[usize], mut finger1: usize, mut finger2: usize) -> usize {
242 loop {
243 match finger1.cmp(&finger2) {
244 Ordering::Less => finger1 = dominators[finger1],
245 Ordering::Greater => finger2 = dominators[finger2],
246 Ordering::Equal => return finger1,
247 }
248 }
249 }
250
predecessor_sets_to_idx_vecs<N>( post_order: &[N], node_to_post_order_idx: &HashMap<N, usize>, mut predecessor_sets: HashMap<N, HashSet<N>>, ) -> Vec<Vec<usize>> where N: Copy + Eq + Hash,251 fn predecessor_sets_to_idx_vecs<N>(
252 post_order: &[N],
253 node_to_post_order_idx: &HashMap<N, usize>,
254 mut predecessor_sets: HashMap<N, HashSet<N>>,
255 ) -> Vec<Vec<usize>>
256 where
257 N: Copy + Eq + Hash,
258 {
259 post_order
260 .iter()
261 .map(|node| {
262 predecessor_sets
263 .remove(node)
264 .map(|predecessors| {
265 predecessors
266 .into_iter()
267 .map(|p| *node_to_post_order_idx.get(&p).unwrap())
268 .collect()
269 })
270 .unwrap_or_default()
271 })
272 .collect()
273 }
274
275 type PredecessorSets<NodeId> = HashMap<NodeId, HashSet<NodeId>>;
276
simple_fast_post_order<G>( graph: G, root: G::NodeId, ) -> (Vec<G::NodeId>, PredecessorSets<G::NodeId>) where G: IntoNeighbors + Visitable, <G as GraphBase>::NodeId: Eq + Hash,277 fn simple_fast_post_order<G>(
278 graph: G,
279 root: G::NodeId,
280 ) -> (Vec<G::NodeId>, PredecessorSets<G::NodeId>)
281 where
282 G: IntoNeighbors + Visitable,
283 <G as GraphBase>::NodeId: Eq + Hash,
284 {
285 let mut post_order = vec![];
286 let mut predecessor_sets = HashMap::new();
287
288 for node in DfsPostOrder::new(graph, root).iter(graph) {
289 post_order.push(node);
290
291 for successor in graph.neighbors(node) {
292 predecessor_sets
293 .entry(successor)
294 .or_insert_with(HashSet::new)
295 .insert(node);
296 }
297 }
298
299 (post_order, predecessor_sets)
300 }
301
302 #[cfg(test)]
303 mod tests {
304 use super::*;
305
306 #[test]
test_iter_dominators()307 fn test_iter_dominators() {
308 let doms: Dominators<u32> = Dominators {
309 root: 0,
310 dominators: [(2, 1), (1, 0), (0, 0)].iter().cloned().collect(),
311 };
312
313 let all_doms: Vec<_> = doms.dominators(2).unwrap().collect();
314 assert_eq!(vec![2, 1, 0], all_doms);
315
316 assert_eq!(None::<()>, doms.dominators(99).map(|_| unreachable!()));
317
318 let strict_doms: Vec<_> = doms.strict_dominators(2).unwrap().collect();
319 assert_eq!(vec![1, 0], strict_doms);
320
321 assert_eq!(
322 None::<()>,
323 doms.strict_dominators(99).map(|_| unreachable!())
324 );
325
326 let dom_by: Vec<_> = doms.immediately_dominated_by(1).collect();
327 assert_eq!(vec![2], dom_by);
328 assert_eq!(None, doms.immediately_dominated_by(99).next());
329 }
330 }
331