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.
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.
11 use rustc_data_structures::bit_set::BitSet;
15 /// Preorder traversal of a graph.
17 /// Preorder traversal is when each node is visited before an of it's
31 /// A preorder traversal of this graph is either `A B D C` or `A C D B`
33 pub struct Preorder<'a, 'tcx: 'a> {
35 visited: BitSet<BasicBlock>,
36 worklist: Vec<BasicBlock>,
37 root_is_start_block: bool,
40 impl<'a, 'tcx> Preorder<'a, 'tcx> {
41 pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> Preorder<'a, 'tcx> {
42 let worklist = vec![root];
46 visited: BitSet::new_empty(mir.basic_blocks().len()),
48 root_is_start_block: root == START_BLOCK,
53 pub fn preorder<'a, 'tcx>(mir: &'a Mir<'tcx>) -> Preorder<'a, 'tcx> {
54 Preorder::new(mir, START_BLOCK)
57 impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> {
58 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
60 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
61 while let Some(idx) = self.worklist.pop() {
62 if !self.visited.insert(idx) {
66 let data = &self.mir[idx];
68 if let Some(ref term) = data.terminator {
69 self.worklist.extend(term.successors());
72 return Some((idx, data));
78 fn size_hint(&self) -> (usize, Option<usize>) {
79 // All the blocks, minus the number of blocks we've visited.
80 let upper = self.mir.basic_blocks().len() - self.visited.count();
82 let lower = if self.root_is_start_block {
83 // We will visit all remaining blocks exactly once.
93 /// Postorder traversal of a graph.
95 /// Postorder traversal is when each node is visited after all of it's
96 /// successors, except when the successor is only reachable by a back-edge
110 /// A Postorder traversal of this graph is `D B C A` or `D C B A`
111 pub struct Postorder<'a, 'tcx: 'a> {
113 visited: BitSet<BasicBlock>,
114 visit_stack: Vec<(BasicBlock, Successors<'a>)>,
115 root_is_start_block: bool,
118 impl<'a, 'tcx> Postorder<'a, 'tcx> {
119 pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> Postorder<'a, 'tcx> {
120 let mut po = Postorder {
122 visited: BitSet::new_empty(mir.basic_blocks().len()),
123 visit_stack: Vec::new(),
124 root_is_start_block: root == START_BLOCK,
128 let data = &po.mir[root];
130 if let Some(ref term) = data.terminator {
131 po.visited.insert(root);
132 po.visit_stack.push((root, term.successors()));
133 po.traverse_successor();
139 fn traverse_successor(&mut self) {
140 // This is quite a complex loop due to 1. the borrow checker not liking it much
141 // and 2. what exactly is going on is not clear
143 // It does the actual traversal of the graph, while the `next` method on the iterator
144 // just pops off of the stack. `visit_stack` is a stack containing pairs of nodes and
145 // iterators over the sucessors of those nodes. Each iteration attempts to get the next
146 // node from the top of the stack, then pushes that node and an iterator over the
147 // successors to the top of the stack. This loop only grows `visit_stack`, stopping when
148 // we reach a child that has no children that we haven't already visited.
150 // For a graph that looks like this:
163 // The state of the stack starts out with just the root node (`A` in this case);
166 // When the first call to `traverse_sucessor` happens, the following happens:
168 // [(B, [D]), // `B` taken from the successors of `A`, pushed to the
169 // // top of the stack along with the successors of `B`
172 // [(D, [E]), // `D` taken from successors of `B`, pushed to stack
176 // [(E, []), // `E` taken from successors of `D`, pushed to stack
181 // Now that the top of the stack has no successors we can traverse, each item will
182 // be popped off during iteration until we get back to `A`. This yields [E, D, B].
184 // When we yield `B` and call `traverse_successor`, we push `C` to the stack, but
185 // since we've already visited `E`, that child isn't added to the stack. The last
186 // two iterations yield `C` and finally `A` for a final traversal of [E, D, B, C, A]
188 let bb = if let Some(&mut (_, ref mut iter)) = self.visit_stack.last_mut() {
189 if let Some(&bb) = iter.next() {
198 if self.visited.insert(bb) {
199 if let Some(term) = &self.mir[bb].terminator {
200 self.visit_stack.push((bb, term.successors()));
207 pub fn postorder<'a, 'tcx>(mir: &'a Mir<'tcx>) -> Postorder<'a, 'tcx> {
208 Postorder::new(mir, START_BLOCK)
211 impl<'a, 'tcx> Iterator for Postorder<'a, 'tcx> {
212 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
214 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
215 let next = self.visit_stack.pop();
217 self.traverse_successor();
220 next.map(|(bb, _)| (bb, &self.mir[bb]))
223 fn size_hint(&self) -> (usize, Option<usize>) {
224 // All the blocks, minus the number of blocks we've visited.
225 let upper = self.mir.basic_blocks().len() - self.visited.count();
227 let lower = if self.root_is_start_block {
228 // We will visit all remaining blocks exactly once.
231 self.visit_stack.len()
238 /// Reverse postorder traversal of a graph
240 /// Reverse postorder is the reverse order of a postorder traversal.
241 /// This is different to a preorder traversal and represents a natural
242 /// linearization of control-flow.
255 /// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
256 /// Note that for a graph containing no loops (i.e. A DAG), this is equivalent to
257 /// a topological sort.
259 /// Construction of a `ReversePostorder` traversal requires doing a full
260 /// postorder traversal of the graph, therefore this traversal should be
261 /// constructed as few times as possible. Use the `reset` method to be able
262 /// to re-use the traversal
264 pub struct ReversePostorder<'a, 'tcx: 'a> {
266 blocks: Vec<BasicBlock>,
270 impl<'a, 'tcx> ReversePostorder<'a, 'tcx> {
271 pub fn new(mir: &'a Mir<'tcx>, root: BasicBlock) -> ReversePostorder<'a, 'tcx> {
272 let blocks : Vec<_> = Postorder::new(mir, root).map(|(bb, _)| bb).collect();
274 let len = blocks.len();
283 pub fn reset(&mut self) {
284 self.idx = self.blocks.len();
289 pub fn reverse_postorder<'a, 'tcx>(mir: &'a Mir<'tcx>) -> ReversePostorder<'a, 'tcx> {
290 ReversePostorder::new(mir, START_BLOCK)
293 impl<'a, 'tcx> Iterator for ReversePostorder<'a, 'tcx> {
294 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
296 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
297 if self.idx == 0 { return None; }
300 self.blocks.get(self.idx).map(|&bb| (bb, &self.mir[bb]))
303 fn size_hint(&self) -> (usize, Option<usize>) {
304 (self.idx, Some(self.idx))
308 impl<'a, 'tcx> ExactSizeIterator for ReversePostorder<'a, 'tcx> {}