1 use rustc_index::bit_set::BitSet;
5 /// Preorder traversal of a graph.
7 /// Preorder traversal is when each node is visited before an of it's
21 /// A preorder traversal of this graph is either `A B D C` or `A C D B`
23 pub struct Preorder<'a, 'tcx> {
25 visited: BitSet<BasicBlock>,
26 worklist: Vec<BasicBlock>,
27 root_is_start_block: bool,
30 impl<'a, 'tcx> Preorder<'a, 'tcx> {
31 pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> Preorder<'a, 'tcx> {
32 let worklist = vec![root];
36 visited: BitSet::new_empty(body.basic_blocks().len()),
38 root_is_start_block: root == START_BLOCK,
43 pub fn preorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Preorder<'a, 'tcx> {
44 Preorder::new(body, START_BLOCK)
47 impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> {
48 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
50 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
51 while let Some(idx) = self.worklist.pop() {
52 if !self.visited.insert(idx) {
56 let data = &self.body[idx];
58 if let Some(ref term) = data.terminator {
59 self.worklist.extend(term.successors());
62 return Some((idx, data));
68 fn size_hint(&self) -> (usize, Option<usize>) {
69 // All the blocks, minus the number of blocks we've visited.
70 let upper = self.body.basic_blocks().len() - self.visited.count();
72 let lower = if self.root_is_start_block {
73 // We will visit all remaining blocks exactly once.
83 /// Postorder traversal of a graph.
85 /// Postorder traversal is when each node is visited after all of it's
86 /// successors, except when the successor is only reachable by a back-edge
100 /// A Postorder traversal of this graph is `D B C A` or `D C B A`
101 pub struct Postorder<'a, 'tcx> {
102 body: &'a Body<'tcx>,
103 visited: BitSet<BasicBlock>,
104 visit_stack: Vec<(BasicBlock, Successors<'a>)>,
105 root_is_start_block: bool,
108 impl<'a, 'tcx> Postorder<'a, 'tcx> {
109 pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> Postorder<'a, 'tcx> {
110 let mut po = Postorder {
112 visited: BitSet::new_empty(body.basic_blocks().len()),
113 visit_stack: Vec::new(),
114 root_is_start_block: root == START_BLOCK,
118 let data = &po.body[root];
120 if let Some(ref term) = data.terminator {
121 po.visited.insert(root);
122 po.visit_stack.push((root, term.successors()));
123 po.traverse_successor();
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
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 successors 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.
140 // For a graph that looks like this:
153 // The state of the stack starts out with just the root node (`A` in this case);
156 // When the first call to `traverse_successor` happens, the following happens:
158 // [(B, [D]), // `B` taken from the successors of `A`, pushed to the
159 // // top of the stack along with the successors of `B`
162 // [(D, [E]), // `D` taken from successors of `B`, pushed to stack
166 // [(E, []), // `E` taken from successors of `D`, pushed to stack
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 yields [E, D, B].
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]
178 let bb = if let Some(&mut (_, ref mut iter)) = self.visit_stack.last_mut() {
179 if let Some(&bb) = iter.next() {
188 if self.visited.insert(bb) {
189 if let Some(term) = &self.body[bb].terminator {
190 self.visit_stack.push((bb, term.successors()));
197 pub fn postorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Postorder<'a, 'tcx> {
198 Postorder::new(body, START_BLOCK)
201 impl<'a, 'tcx> Iterator for Postorder<'a, 'tcx> {
202 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
204 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
205 let next = self.visit_stack.pop();
207 self.traverse_successor();
210 next.map(|(bb, _)| (bb, &self.body[bb]))
213 fn size_hint(&self) -> (usize, Option<usize>) {
214 // All the blocks, minus the number of blocks we've visited.
215 let upper = self.body.basic_blocks().len() - self.visited.count();
217 let lower = if self.root_is_start_block {
218 // We will visit all remaining blocks exactly once.
221 self.visit_stack.len()
228 /// Reverse postorder traversal of a graph
230 /// Reverse postorder is the reverse order of a postorder traversal.
231 /// This is different to a preorder traversal and represents a natural
232 /// linearization of control-flow.
245 /// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
246 /// Note that for a graph containing no loops (i.e., A DAG), this is equivalent to
247 /// a topological sort.
249 /// Construction of a `ReversePostorder` traversal requires doing a full
250 /// postorder traversal of the graph, therefore this traversal should be
251 /// constructed as few times as possible. Use the `reset` method to be able
252 /// to re-use the traversal
254 pub struct ReversePostorder<'a, 'tcx> {
255 body: &'a Body<'tcx>,
256 blocks: Vec<BasicBlock>,
260 impl<'a, 'tcx> ReversePostorder<'a, 'tcx> {
261 pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> ReversePostorder<'a, 'tcx> {
262 let blocks : Vec<_> = Postorder::new(body, root).map(|(bb, _)| bb).collect();
264 let len = blocks.len();
273 pub fn reset(&mut self) {
274 self.idx = self.blocks.len();
279 pub fn reverse_postorder<'a, 'tcx>(body: &'a Body<'tcx>) -> ReversePostorder<'a, 'tcx> {
280 ReversePostorder::new(body, START_BLOCK)
283 impl<'a, 'tcx> Iterator for ReversePostorder<'a, 'tcx> {
284 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
286 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
287 if self.idx == 0 { return None; }
290 self.blocks.get(self.idx).map(|&bb| (bb, &self.body[bb]))
293 fn size_hint(&self) -> (usize, Option<usize>) {
294 (self.idx, Some(self.idx))
298 impl<'a, 'tcx> ExactSizeIterator for ReversePostorder<'a, 'tcx> {}