]>
Commit | Line | Data |
---|---|---|
54a0048b SL |
1 | // Copyright 2016 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | use std::vec; | |
12 | ||
13 | use rustc_data_structures::bitvec::BitVector; | |
3157f602 | 14 | use rustc_data_structures::indexed_vec::Idx; |
54a0048b | 15 | |
c30ab7b3 | 16 | use super::*; |
54a0048b SL |
17 | |
18 | /// Preorder traversal of a graph. | |
19 | /// | |
20 | /// Preorder traversal is when each node is visited before an of it's | |
21 | /// successors | |
22 | /// | |
a7813a04 XL |
23 | /// ```text |
24 | /// | |
54a0048b SL |
25 | /// A |
26 | /// / \ | |
27 | /// / \ | |
28 | /// B C | |
29 | /// \ / | |
30 | /// \ / | |
31 | /// D | |
a7813a04 | 32 | /// ``` |
54a0048b SL |
33 | /// |
34 | /// A preorder traversal of this graph is either `A B D C` or `A C D B` | |
35 | #[derive(Clone)] | |
36 | pub struct Preorder<'a, 'tcx: 'a> { | |
37 | mir: &'a Mir<'tcx>, | |
38 | visited: BitVector, | |
39 | worklist: Vec<BasicBlock>, | |
40 | } | |
41 | ||
42 | impl<'a, 'tcx> Preorder<'a, 'tcx> { | |
43 | pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> Preorder<'a, 'tcx> { | |
44 | let worklist = vec![root]; | |
45 | ||
46 | Preorder { | |
041b39d2 | 47 | mir, |
3157f602 | 48 | visited: BitVector::new(mir.basic_blocks().len()), |
041b39d2 | 49 | worklist, |
54a0048b SL |
50 | } |
51 | } | |
52 | } | |
53 | ||
54 | pub fn preorder<'a, 'tcx>(mir: &'a Mir<'tcx>) -> Preorder<'a, 'tcx> { | |
55 | Preorder::new(mir, START_BLOCK) | |
56 | } | |
57 | ||
58 | impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> { | |
59 | type Item = (BasicBlock, &'a BasicBlockData<'tcx>); | |
60 | ||
61 | fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> { | |
62 | while let Some(idx) = self.worklist.pop() { | |
63 | if !self.visited.insert(idx.index()) { | |
64 | continue; | |
65 | } | |
66 | ||
3157f602 | 67 | let data = &self.mir[idx]; |
54a0048b SL |
68 | |
69 | if let Some(ref term) = data.terminator { | |
70 | for &succ in term.successors().iter() { | |
71 | self.worklist.push(succ); | |
72 | } | |
73 | } | |
74 | ||
75 | return Some((idx, data)); | |
76 | } | |
77 | ||
78 | None | |
79 | } | |
80 | } | |
81 | ||
82 | /// Postorder traversal of a graph. | |
83 | /// | |
84 | /// Postorder traversal is when each node is visited after all of it's | |
85 | /// successors, except when the successor is only reachable by a back-edge | |
86 | /// | |
a7813a04 XL |
87 | /// |
88 | /// ```text | |
89 | /// | |
54a0048b SL |
90 | /// A |
91 | /// / \ | |
92 | /// / \ | |
93 | /// B C | |
94 | /// \ / | |
95 | /// \ / | |
96 | /// D | |
a7813a04 | 97 | /// ``` |
54a0048b SL |
98 | /// |
99 | /// A Postorder traversal of this graph is `D B C A` or `D C B A` | |
100 | pub struct Postorder<'a, 'tcx: 'a> { | |
101 | mir: &'a Mir<'tcx>, | |
102 | visited: BitVector, | |
103 | visit_stack: Vec<(BasicBlock, vec::IntoIter<BasicBlock>)> | |
104 | } | |
105 | ||
106 | impl<'a, 'tcx> Postorder<'a, 'tcx> { | |
107 | pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> Postorder<'a, 'tcx> { | |
108 | let mut po = Postorder { | |
041b39d2 | 109 | mir, |
3157f602 | 110 | visited: BitVector::new(mir.basic_blocks().len()), |
54a0048b SL |
111 | visit_stack: Vec::new() |
112 | }; | |
113 | ||
114 | ||
3157f602 | 115 | let data = &po.mir[root]; |
54a0048b SL |
116 | |
117 | if let Some(ref term) = data.terminator { | |
118 | po.visited.insert(root.index()); | |
119 | ||
120 | let succs = term.successors().into_owned().into_iter(); | |
121 | ||
122 | po.visit_stack.push((root, succs)); | |
123 | po.traverse_successor(); | |
124 | } | |
125 | ||
126 | po | |
127 | } | |
128 | ||
129 | fn traverse_successor(&mut self) { | |
130 | // This is quite a complex loop due to 1. the borrow checker not liking it much | |
131 | // and 2. what exactly is going on is not clear | |
132 | // | |
133 | // It does the actual traversal of the graph, while the `next` method on the iterator | |
134 | // just pops off of the stack. `visit_stack` is a stack containing pairs of nodes and | |
135 | // iterators over the sucessors of those nodes. Each iteration attempts to get the next | |
136 | // node from the top of the stack, then pushes that node and an iterator over the | |
137 | // successors to the top of the stack. This loop only grows `visit_stack`, stopping when | |
138 | // we reach a child that has no children that we haven't already visited. | |
139 | // | |
140 | // For a graph that looks like this: | |
141 | // | |
142 | // A | |
143 | // / \ | |
144 | // / \ | |
145 | // B C | |
146 | // | | | |
147 | // | | | |
148 | // D | | |
149 | // \ / | |
150 | // \ / | |
151 | // E | |
152 | // | |
153 | // The state of the stack starts out with just the root node (`A` in this case); | |
154 | // [(A, [B, C])] | |
155 | // | |
156 | // When the first call to `traverse_sucessor` happens, the following happens: | |
157 | // | |
158 | // [(B, [D]), // `B` taken from the successors of `A`, pushed to the | |
159 | // // top of the stack along with the successors of `B` | |
160 | // (A, [C])] | |
161 | // | |
162 | // [(D, [E]), // `D` taken from successors of `B`, pushed to stack | |
163 | // (B, []), | |
164 | // (A, [C])] | |
165 | // | |
166 | // [(E, []), // `E` taken from successors of `D`, pushed to stack | |
167 | // (D, []), | |
168 | // (B, []), | |
169 | // (A, [C])] | |
170 | // | |
171 | // Now that the top of the stack has no successors we can traverse, each item will | |
172 | // be popped off during iteration until we get back to `A`. This yeilds [E, D, B]. | |
173 | // | |
174 | // When we yield `B` and call `traverse_successor`, we push `C` to the stack, but | |
175 | // since we've already visited `E`, that child isn't added to the stack. The last | |
176 | // two iterations yield `C` and finally `A` for a final traversal of [E, D, B, C, A] | |
177 | loop { | |
178 | let bb = if let Some(&mut (_, ref mut iter)) = self.visit_stack.last_mut() { | |
179 | if let Some(bb) = iter.next() { | |
180 | bb | |
181 | } else { | |
182 | break; | |
183 | } | |
184 | } else { | |
185 | break; | |
186 | }; | |
187 | ||
188 | if self.visited.insert(bb.index()) { | |
3157f602 | 189 | if let Some(ref term) = self.mir[bb].terminator { |
54a0048b SL |
190 | let succs = term.successors().into_owned().into_iter(); |
191 | self.visit_stack.push((bb, succs)); | |
192 | } | |
193 | } | |
194 | } | |
195 | } | |
196 | } | |
197 | ||
198 | pub fn postorder<'a, 'tcx>(mir: &'a Mir<'tcx>) -> Postorder<'a, 'tcx> { | |
199 | Postorder::new(mir, START_BLOCK) | |
200 | } | |
201 | ||
202 | impl<'a, 'tcx> Iterator for Postorder<'a, 'tcx> { | |
203 | type Item = (BasicBlock, &'a BasicBlockData<'tcx>); | |
204 | ||
205 | fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> { | |
206 | let next = self.visit_stack.pop(); | |
207 | if next.is_some() { | |
208 | self.traverse_successor(); | |
209 | } | |
210 | ||
3157f602 | 211 | next.map(|(bb, _)| (bb, &self.mir[bb])) |
54a0048b SL |
212 | } |
213 | } | |
214 | ||
215 | /// Reverse postorder traversal of a graph | |
216 | /// | |
217 | /// Reverse postorder is the reverse order of a postorder traversal. | |
218 | /// This is different to a preorder traversal and represents a natural | |
3b2f2976 | 219 | /// linearization of control-flow. |
54a0048b | 220 | /// |
a7813a04 XL |
221 | /// ```text |
222 | /// | |
54a0048b SL |
223 | /// A |
224 | /// / \ | |
225 | /// / \ | |
226 | /// B C | |
227 | /// \ / | |
228 | /// \ / | |
229 | /// D | |
a7813a04 | 230 | /// ``` |
54a0048b SL |
231 | /// |
232 | /// A reverse postorder traversal of this graph is either `A B C D` or `A C B D` | |
233 | /// Note that for a graph containing no loops (i.e. A DAG), this is equivalent to | |
234 | /// a topological sort. | |
235 | /// | |
236 | /// Construction of a `ReversePostorder` traversal requires doing a full | |
237 | /// postorder traversal of the graph, therefore this traversal should be | |
238 | /// constructed as few times as possible. Use the `reset` method to be able | |
239 | /// to re-use the traversal | |
240 | #[derive(Clone)] | |
241 | pub struct ReversePostorder<'a, 'tcx: 'a> { | |
242 | mir: &'a Mir<'tcx>, | |
243 | blocks: Vec<BasicBlock>, | |
244 | idx: usize | |
245 | } | |
246 | ||
247 | impl<'a, 'tcx> ReversePostorder<'a, 'tcx> { | |
248 | pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> ReversePostorder<'a, 'tcx> { | |
249 | let blocks : Vec<_> = Postorder::new(mir, root).map(|(bb, _)| bb).collect(); | |
250 | ||
251 | let len = blocks.len(); | |
252 | ||
253 | ReversePostorder { | |
041b39d2 XL |
254 | mir, |
255 | blocks, | |
54a0048b SL |
256 | idx: len |
257 | } | |
258 | } | |
259 | ||
260 | pub fn reset(&mut self) { | |
261 | self.idx = self.blocks.len(); | |
262 | } | |
263 | } | |
264 | ||
265 | ||
266 | pub fn reverse_postorder<'a, 'tcx>(mir: &'a Mir<'tcx>) -> ReversePostorder<'a, 'tcx> { | |
267 | ReversePostorder::new(mir, START_BLOCK) | |
268 | } | |
269 | ||
270 | impl<'a, 'tcx> Iterator for ReversePostorder<'a, 'tcx> { | |
271 | type Item = (BasicBlock, &'a BasicBlockData<'tcx>); | |
272 | ||
273 | fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> { | |
274 | if self.idx == 0 { return None; } | |
275 | self.idx -= 1; | |
276 | ||
3157f602 | 277 | self.blocks.get(self.idx).map(|&bb| (bb, &self.mir[bb])) |
54a0048b SL |
278 | } |
279 | } |