]>
Commit | Line | Data |
---|---|---|
f035d41b XL |
1 | //! Finding the dominators in a control-flow graph. |
2 | //! | |
a2a8927a XL |
3 | //! Algorithm based on Loukas Georgiadis, |
4 | //! "Linear-Time Algorithms for Dominators and Related Problems", | |
5 | //! <ftp://ftp.cs.princeton.edu/techreports/2005/737.pdf> | |
6 | //! | |
7 | //! Additionally useful is the original Lengauer-Tarjan paper on this subject, | |
8 | //! "A Fast Algorithm for Finding Dominators in a Flowgraph" | |
9 | //! Thomas Lengauer and Robert Endre Tarjan. | |
10 | //! <https://www.cs.princeton.edu/courses/archive/spr03/cs423/download/dominators.pdf> | |
3157f602 | 11 | |
8faf50e0 | 12 | use super::ControlFlowGraph; |
dfeec247 | 13 | use rustc_index::vec::{Idx, IndexVec}; |
29967ef6 | 14 | use std::cmp::Ordering; |
3157f602 | 15 | |
3157f602 | 16 | #[cfg(test)] |
416331ca | 17 | mod tests; |
3157f602 | 18 | |
a2a8927a XL |
19 | struct PreOrderFrame<Iter> { |
20 | pre_order_idx: PreorderIndex, | |
21 | iter: Iter, | |
3157f602 XL |
22 | } |
23 | ||
a2a8927a XL |
24 | rustc_index::newtype_index! { |
25 | struct PreorderIndex { .. } | |
26 | } | |
3157f602 | 27 | |
a2a8927a | 28 | pub fn dominators<G: ControlFlowGraph>(graph: G) -> Dominators<G::Node> { |
3157f602 | 29 | // compute the post order index (rank) for each node |
5869c6ff | 30 | let mut post_order_rank = IndexVec::from_elem_n(0, graph.num_nodes()); |
3157f602 | 31 | |
a2a8927a XL |
32 | // We allocate capacity for the full set of nodes, because most of the time |
33 | // most of the nodes *are* reachable. | |
34 | let mut parent: IndexVec<PreorderIndex, PreorderIndex> = | |
35 | IndexVec::with_capacity(graph.num_nodes()); | |
36 | ||
37 | let mut stack = vec![PreOrderFrame { | |
38 | pre_order_idx: PreorderIndex::new(0), | |
39 | iter: graph.successors(graph.start_node()), | |
40 | }]; | |
41 | let mut pre_order_to_real: IndexVec<PreorderIndex, G::Node> = | |
42 | IndexVec::with_capacity(graph.num_nodes()); | |
43 | let mut real_to_pre_order: IndexVec<G::Node, Option<PreorderIndex>> = | |
44 | IndexVec::from_elem_n(None, graph.num_nodes()); | |
45 | pre_order_to_real.push(graph.start_node()); | |
46 | parent.push(PreorderIndex::new(0)); // the parent of the root node is the root for now. | |
47 | real_to_pre_order[graph.start_node()] = Some(PreorderIndex::new(0)); | |
48 | let mut post_order_idx = 0; | |
49 | ||
50 | // Traverse the graph, collecting a number of things: | |
51 | // | |
52 | // * Preorder mapping (to it, and back to the actual ordering) | |
53 | // * Postorder mapping (used exclusively for rank_partial_cmp on the final product) | |
54 | // * Parents for each vertex in the preorder tree | |
55 | // | |
56 | // These are all done here rather than through one of the 'standard' | |
57 | // graph traversals to help make this fast. | |
58 | 'recurse: while let Some(frame) = stack.last_mut() { | |
59 | while let Some(successor) = frame.iter.next() { | |
60 | if real_to_pre_order[successor].is_none() { | |
61 | let pre_order_idx = pre_order_to_real.push(successor); | |
62 | real_to_pre_order[successor] = Some(pre_order_idx); | |
63 | parent.push(frame.pre_order_idx); | |
64 | stack.push(PreOrderFrame { pre_order_idx, iter: graph.successors(successor) }); | |
3157f602 | 65 | |
a2a8927a | 66 | continue 'recurse; |
3157f602 XL |
67 | } |
68 | } | |
a2a8927a XL |
69 | post_order_rank[pre_order_to_real[frame.pre_order_idx]] = post_order_idx; |
70 | post_order_idx += 1; | |
71 | ||
72 | stack.pop(); | |
3157f602 XL |
73 | } |
74 | ||
a2a8927a XL |
75 | let reachable_vertices = pre_order_to_real.len(); |
76 | ||
77 | let mut idom = IndexVec::from_elem_n(PreorderIndex::new(0), reachable_vertices); | |
78 | let mut semi = IndexVec::from_fn_n(std::convert::identity, reachable_vertices); | |
79 | let mut label = semi.clone(); | |
80 | let mut bucket = IndexVec::from_elem_n(vec![], reachable_vertices); | |
81 | let mut lastlinked = None; | |
3157f602 | 82 | |
a2a8927a XL |
83 | // We loop over vertices in reverse preorder. This implements the pseudocode |
84 | // of the simple Lengauer-Tarjan algorithm. A few key facts are noted here | |
85 | // which are helpful for understanding the code (full proofs and such are | |
86 | // found in various papers, including one cited at the top of this file). | |
87 | // | |
88 | // For each vertex w (which is not the root), | |
89 | // * semi[w] is a proper ancestor of the vertex w (i.e., semi[w] != w) | |
90 | // * idom[w] is an ancestor of semi[w] (i.e., idom[w] may equal semi[w]) | |
91 | // | |
92 | // An immediate dominator of w (idom[w]) is a vertex v where v dominates w | |
93 | // and every other dominator of w dominates v. (Every vertex except the root has | |
94 | // a unique immediate dominator.) | |
95 | // | |
96 | // A semidominator for a given vertex w (semi[w]) is the vertex v with minimum | |
97 | // preorder number such that there exists a path from v to w in which all elements (other than w) have | |
98 | // preorder numbers greater than w (i.e., this path is not the tree path to | |
99 | // w). | |
100 | for w in (PreorderIndex::new(1)..PreorderIndex::new(reachable_vertices)).rev() { | |
101 | // Optimization: process buckets just once, at the start of the | |
102 | // iteration. Do not explicitly empty the bucket (even though it will | |
103 | // not be used again), to save some instructions. | |
104 | // | |
105 | // The bucket here contains the vertices whose semidominator is the | |
106 | // vertex w, which we are guaranteed to have found: all vertices who can | |
107 | // be semidominated by w must have a preorder number exceeding w, so | |
108 | // they have been placed in the bucket. | |
109 | // | |
110 | // We compute a partial set of immediate dominators here. | |
111 | let z = parent[w]; | |
112 | for &v in bucket[z].iter() { | |
113 | // This uses the result of Lemma 5 from section 2 from the original | |
114 | // 1979 paper, to compute either the immediate or relative dominator | |
115 | // for a given vertex v. | |
116 | // | |
117 | // eval returns a vertex y, for which semi[y] is minimum among | |
118 | // vertices semi[v] +> y *> v. Note that semi[v] = z as we're in the | |
119 | // z bucket. | |
120 | // | |
121 | // Given such a vertex y, semi[y] <= semi[v] and idom[y] = idom[v]. | |
122 | // If semi[y] = semi[v], though, idom[v] = semi[v]. | |
123 | // | |
124 | // Using this, we can either set idom[v] to be: | |
125 | // * semi[v] (i.e. z), if semi[y] is z | |
126 | // * idom[y], otherwise | |
127 | // | |
128 | // We don't directly set to idom[y] though as it's not necessarily | |
129 | // known yet. The second preorder traversal will cleanup by updating | |
130 | // the idom for any that were missed in this pass. | |
131 | let y = eval(&mut parent, lastlinked, &semi, &mut label, v); | |
132 | idom[v] = if semi[y] < z { y } else { z }; | |
3157f602 XL |
133 | } |
134 | ||
a2a8927a XL |
135 | // This loop computes the semi[w] for w. |
136 | semi[w] = w; | |
137 | for v in graph.predecessors(pre_order_to_real[w]) { | |
138 | let v = real_to_pre_order[v].unwrap(); | |
139 | ||
140 | // eval returns a vertex x from which semi[x] is minimum among | |
141 | // vertices semi[v] +> x *> v. | |
142 | // | |
143 | // From Lemma 4 from section 2, we know that the semidominator of a | |
144 | // vertex w is the minimum (by preorder number) vertex of the | |
145 | // following: | |
146 | // | |
147 | // * direct predecessors of w with preorder number less than w | |
148 | // * semidominators of u such that u > w and there exists (v, w) | |
149 | // such that u *> v | |
150 | // | |
151 | // This loop therefore identifies such a minima. Note that any | |
152 | // semidominator path to w must have all but the first vertex go | |
153 | // through vertices numbered greater than w, so the reverse preorder | |
154 | // traversal we are using guarantees that all of the information we | |
155 | // might need is available at this point. | |
156 | // | |
157 | // The eval call will give us semi[x], which is either: | |
158 | // | |
159 | // * v itself, if v has not yet been processed | |
160 | // * A possible 'best' semidominator for w. | |
161 | let x = eval(&mut parent, lastlinked, &semi, &mut label, v); | |
162 | semi[w] = std::cmp::min(semi[w], semi[x]); | |
163 | } | |
164 | // semi[w] is now semidominator(w) and won't change any more. | |
165 | ||
166 | // Optimization: Do not insert into buckets if parent[w] = semi[w], as | |
167 | // we then immediately know the idom. | |
168 | // | |
169 | // If we don't yet know the idom directly, then push this vertex into | |
170 | // our semidominator's bucket, where it will get processed at a later | |
171 | // stage to compute its immediate dominator. | |
172 | if parent[w] != semi[w] { | |
173 | bucket[semi[w]].push(w); | |
174 | } else { | |
175 | idom[w] = parent[w]; | |
3157f602 | 176 | } |
a2a8927a XL |
177 | |
178 | // Optimization: We share the parent array between processed and not | |
179 | // processed elements; lastlinked represents the divider. | |
180 | lastlinked = Some(w); | |
3157f602 | 181 | } |
b7449926 | 182 | |
a2a8927a XL |
183 | // Finalize the idoms for any that were not fully settable during initial |
184 | // traversal. | |
185 | // | |
186 | // If idom[w] != semi[w] then we know that we've stored vertex y from above | |
187 | // into idom[w]. It is known to be our 'relative dominator', which means | |
188 | // that it's one of w's ancestors and has the same immediate dominator as w, | |
189 | // so use that idom. | |
190 | for w in PreorderIndex::new(1)..PreorderIndex::new(reachable_vertices) { | |
191 | if idom[w] != semi[w] { | |
192 | idom[w] = idom[idom[w]]; | |
193 | } | |
194 | } | |
195 | ||
196 | let mut immediate_dominators = IndexVec::from_elem_n(None, graph.num_nodes()); | |
197 | for (idx, node) in pre_order_to_real.iter_enumerated() { | |
198 | immediate_dominators[*node] = Some(pre_order_to_real[idom[idx]]); | |
199 | } | |
200 | ||
201 | Dominators { post_order_rank, immediate_dominators } | |
202 | } | |
203 | ||
204 | /// Evaluate the link-eval virtual forest, providing the currently minimum semi | |
205 | /// value for the passed `node` (which may be itself). | |
206 | /// | |
207 | /// This maintains that for every vertex v, `label[v]` is such that: | |
208 | /// | |
209 | /// ```text | |
210 | /// semi[eval(v)] = min { semi[label[u]] | root_in_forest(v) +> u *> v } | |
211 | /// ``` | |
212 | /// | |
213 | /// where `+>` is a proper ancestor and `*>` is just an ancestor. | |
214 | #[inline] | |
215 | fn eval( | |
216 | ancestor: &mut IndexVec<PreorderIndex, PreorderIndex>, | |
217 | lastlinked: Option<PreorderIndex>, | |
218 | semi: &IndexVec<PreorderIndex, PreorderIndex>, | |
219 | label: &mut IndexVec<PreorderIndex, PreorderIndex>, | |
220 | node: PreorderIndex, | |
221 | ) -> PreorderIndex { | |
222 | if is_processed(node, lastlinked) { | |
223 | compress(ancestor, lastlinked, semi, label, node); | |
224 | label[node] | |
225 | } else { | |
226 | node | |
227 | } | |
228 | } | |
229 | ||
230 | #[inline] | |
231 | fn is_processed(v: PreorderIndex, lastlinked: Option<PreorderIndex>) -> bool { | |
232 | if let Some(ll) = lastlinked { v >= ll } else { false } | |
233 | } | |
234 | ||
235 | #[inline] | |
236 | fn compress( | |
237 | ancestor: &mut IndexVec<PreorderIndex, PreorderIndex>, | |
238 | lastlinked: Option<PreorderIndex>, | |
239 | semi: &IndexVec<PreorderIndex, PreorderIndex>, | |
240 | label: &mut IndexVec<PreorderIndex, PreorderIndex>, | |
241 | v: PreorderIndex, | |
242 | ) { | |
243 | assert!(is_processed(v, lastlinked)); | |
244 | let u = ancestor[v]; | |
245 | if is_processed(u, lastlinked) { | |
246 | compress(ancestor, lastlinked, semi, label, u); | |
247 | if semi[label[u]] < semi[label[v]] { | |
248 | label[v] = label[u]; | |
249 | } | |
250 | ancestor[v] = ancestor[u]; | |
251 | } | |
3157f602 XL |
252 | } |
253 | ||
254 | #[derive(Clone, Debug)] | |
255 | pub struct Dominators<N: Idx> { | |
256 | post_order_rank: IndexVec<N, usize>, | |
257 | immediate_dominators: IndexVec<N, Option<N>>, | |
258 | } | |
259 | ||
260 | impl<Node: Idx> Dominators<Node> { | |
6a06907d XL |
261 | pub fn dummy() -> Self { |
262 | Self { post_order_rank: IndexVec::new(), immediate_dominators: IndexVec::new() } | |
263 | } | |
264 | ||
3157f602 XL |
265 | pub fn is_reachable(&self, node: Node) -> bool { |
266 | self.immediate_dominators[node].is_some() | |
267 | } | |
268 | ||
269 | pub fn immediate_dominator(&self, node: Node) -> Node { | |
270 | assert!(self.is_reachable(node), "node {:?} is not reachable", node); | |
271 | self.immediate_dominators[node].unwrap() | |
272 | } | |
273 | ||
9fa01778 | 274 | pub fn dominators(&self, node: Node) -> Iter<'_, Node> { |
3157f602 | 275 | assert!(self.is_reachable(node), "node {:?} is not reachable", node); |
dfeec247 | 276 | Iter { dominators: self, node: Some(node) } |
3157f602 XL |
277 | } |
278 | ||
279 | pub fn is_dominated_by(&self, node: Node, dom: Node) -> bool { | |
280 | // FIXME -- could be optimized by using post-order-rank | |
281 | self.dominators(node).any(|n| n == dom) | |
282 | } | |
29967ef6 XL |
283 | |
284 | /// Provide deterministic ordering of nodes such that, if any two nodes have a dominator | |
285 | /// relationship, the dominator will always precede the dominated. (The relative ordering | |
286 | /// of two unrelated nodes will also be consistent, but otherwise the order has no | |
287 | /// meaning.) This method cannot be used to determine if either Node dominates the other. | |
288 | pub fn rank_partial_cmp(&self, lhs: Node, rhs: Node) -> Option<Ordering> { | |
289 | self.post_order_rank[lhs].partial_cmp(&self.post_order_rank[rhs]) | |
290 | } | |
3157f602 XL |
291 | } |
292 | ||
9fa01778 | 293 | pub struct Iter<'dom, Node: Idx> { |
3157f602 XL |
294 | dominators: &'dom Dominators<Node>, |
295 | node: Option<Node>, | |
296 | } | |
297 | ||
298 | impl<'dom, Node: Idx> Iterator for Iter<'dom, Node> { | |
299 | type Item = Node; | |
300 | ||
301 | fn next(&mut self) -> Option<Self::Item> { | |
302 | if let Some(node) = self.node { | |
303 | let dom = self.dominators.immediate_dominator(node); | |
304 | if dom == node { | |
305 | self.node = None; // reached the root | |
306 | } else { | |
307 | self.node = Some(dom); | |
308 | } | |
ba9703b0 | 309 | Some(node) |
3157f602 | 310 | } else { |
ba9703b0 | 311 | None |
3157f602 XL |
312 | } |
313 | } | |
314 | } |