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