src/librustc/mir/traversal.rs

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