1 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
2 use rustc_data_structures::sync::OnceCell;
3 use rustc_index::bit_set::BitSet;
4 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
8 /// Preorder traversal of a graph.
10 /// Preorder traversal is when each node is visited after at least one of its predecessors. If you
11 /// are familiar with some basic graph theory, then this performs a depth first search and returns
12 /// nodes in order of discovery time.
25 /// A preorder traversal of this graph is either `A B D C` or `A C D B`
27 pub struct Preorder<'a, 'tcx> {
29 visited: BitSet<BasicBlock>,
30 worklist: Vec<BasicBlock>,
31 root_is_start_block: bool,
34 impl<'a, 'tcx> Preorder<'a, 'tcx> {
35 pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> Preorder<'a, 'tcx> {
36 let worklist = vec![root];
40 visited: BitSet::new_empty(body.basic_blocks.len()),
42 root_is_start_block: root == START_BLOCK,
47 pub fn preorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Preorder<'a, 'tcx> {
48 Preorder::new(body, START_BLOCK)
51 impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> {
52 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
54 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
55 while let Some(idx) = self.worklist.pop() {
56 if !self.visited.insert(idx) {
60 let data = &self.body[idx];
62 if let Some(ref term) = data.terminator {
63 self.worklist.extend(term.successors());
66 return Some((idx, data));
72 fn size_hint(&self) -> (usize, Option<usize>) {
73 // All the blocks, minus the number of blocks we've visited.
74 let upper = self.body.basic_blocks.len() - self.visited.count();
76 let lower = if self.root_is_start_block {
77 // We will visit all remaining blocks exactly once.
87 /// Postorder traversal of a graph.
89 /// Postorder traversal is when each node is visited after all of its successors, except when the
90 /// successor is only reachable by a back-edge. If you are familiar with some basic graph theory,
91 /// then this performs a depth first search and returns nodes in order of completion time.
105 /// A Postorder traversal of this graph is `D B C A` or `D C B A`
106 pub struct Postorder<'a, 'tcx> {
107 basic_blocks: &'a IndexVec<BasicBlock, BasicBlockData<'tcx>>,
108 visited: BitSet<BasicBlock>,
109 visit_stack: Vec<(BasicBlock, Successors<'a>)>,
110 root_is_start_block: bool,
113 impl<'a, 'tcx> Postorder<'a, 'tcx> {
115 basic_blocks: &'a IndexVec<BasicBlock, BasicBlockData<'tcx>>,
117 ) -> Postorder<'a, 'tcx> {
118 let mut po = Postorder {
120 visited: BitSet::new_empty(basic_blocks.len()),
121 visit_stack: Vec::new(),
122 root_is_start_block: root == START_BLOCK,
125 let data = &po.basic_blocks[root];
127 if let Some(ref term) = data.terminator {
128 po.visited.insert(root);
129 po.visit_stack.push((root, term.successors()));
130 po.traverse_successor();
136 fn traverse_successor(&mut self) {
137 // This is quite a complex loop due to 1. the borrow checker not liking it much
138 // and 2. what exactly is going on is not clear
140 // It does the actual traversal of the graph, while the `next` method on the iterator
141 // just pops off of the stack. `visit_stack` is a stack containing pairs of nodes and
142 // iterators over the successors of those nodes. Each iteration attempts to get the next
143 // node from the top of the stack, then pushes that node and an iterator over the
144 // successors to the top of the stack. This loop only grows `visit_stack`, stopping when
145 // we reach a child that has no children that we haven't already visited.
147 // For a graph that looks like this:
160 // The state of the stack starts out with just the root node (`A` in this case);
163 // When the first call to `traverse_successor` happens, the following happens:
165 // [(B, [D]), // `B` taken from the successors of `A`, pushed to the
166 // // top of the stack along with the successors of `B`
169 // [(D, [E]), // `D` taken from successors of `B`, pushed to stack
173 // [(E, []), // `E` taken from successors of `D`, pushed to stack
178 // Now that the top of the stack has no successors we can traverse, each item will
179 // be popped off during iteration until we get back to `A`. This yields [E, D, B].
181 // When we yield `B` and call `traverse_successor`, we push `C` to the stack, but
182 // since we've already visited `E`, that child isn't added to the stack. The last
183 // two iterations yield `C` and finally `A` for a final traversal of [E, D, B, C, A]
185 let bb = if let Some(&mut (_, ref mut iter)) = self.visit_stack.last_mut() {
186 if let Some(bb) = iter.next() {
195 if self.visited.insert(bb) {
196 if let Some(term) = &self.basic_blocks[bb].terminator {
197 self.visit_stack.push((bb, term.successors()));
204 pub fn postorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Postorder<'a, 'tcx> {
205 Postorder::new(&body.basic_blocks, START_BLOCK)
208 impl<'a, 'tcx> Iterator for Postorder<'a, 'tcx> {
209 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
211 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
212 let next = self.visit_stack.pop();
214 self.traverse_successor();
217 next.map(|(bb, _)| (bb, &self.basic_blocks[bb]))
220 fn size_hint(&self) -> (usize, Option<usize>) {
221 // All the blocks, minus the number of blocks we've visited.
222 let upper = self.basic_blocks.len() - self.visited.count();
224 let lower = if self.root_is_start_block {
225 // We will visit all remaining blocks exactly once.
228 self.visit_stack.len()
235 /// Reverse postorder traversal of a graph
237 /// Reverse postorder is the reverse order of a postorder traversal.
238 /// This is different to a preorder traversal and represents a natural
239 /// linearization of control-flow.
252 /// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
253 /// Note that for a graph containing no loops (i.e., A DAG), this is equivalent to
254 /// a topological sort.
256 /// Construction of a `ReversePostorder` traversal requires doing a full
257 /// postorder traversal of the graph, therefore this traversal should be
258 /// constructed as few times as possible. Use the `reset` method to be able
259 /// to re-use the traversal
261 pub struct ReversePostorder<'a, 'tcx> {
262 body: &'a Body<'tcx>,
263 blocks: Vec<BasicBlock>,
267 impl<'a, 'tcx> ReversePostorder<'a, 'tcx> {
268 pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> ReversePostorder<'a, 'tcx> {
269 let blocks: Vec<_> = Postorder::new(&body.basic_blocks, root).map(|(bb, _)| bb).collect();
270 let len = blocks.len();
271 ReversePostorder { body, blocks, idx: len }
275 impl<'a, 'tcx> Iterator for ReversePostorder<'a, 'tcx> {
276 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
278 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
284 self.blocks.get(self.idx).map(|&bb| (bb, &self.body[bb]))
287 fn size_hint(&self) -> (usize, Option<usize>) {
288 (self.idx, Some(self.idx))
292 impl<'a, 'tcx> ExactSizeIterator for ReversePostorder<'a, 'tcx> {}
294 /// Returns an iterator over all basic blocks reachable from the `START_BLOCK` in no particular
297 /// This is clearer than writing `preorder` in cases where the order doesn't matter.
298 pub fn reachable<'a, 'tcx>(
299 body: &'a Body<'tcx>,
300 ) -> impl 'a + Iterator<Item = (BasicBlock, &'a BasicBlockData<'tcx>)> {
304 /// Returns a `BitSet` containing all basic blocks reachable from the `START_BLOCK`.
305 pub fn reachable_as_bitset(body: &Body<'_>) -> BitSet<BasicBlock> {
306 let mut iter = preorder(body);
307 (&mut iter).for_each(drop);
312 pub struct ReversePostorderIter<'a, 'tcx> {
313 body: &'a Body<'tcx>,
314 blocks: &'a [BasicBlock],
318 impl<'a, 'tcx> Iterator for ReversePostorderIter<'a, 'tcx> {
319 type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
321 fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
327 self.blocks.get(self.idx).map(|&bb| (bb, &self.body[bb]))
330 fn size_hint(&self) -> (usize, Option<usize>) {
331 (self.idx, Some(self.idx))
335 impl<'a, 'tcx> ExactSizeIterator for ReversePostorderIter<'a, 'tcx> {}
337 pub fn reverse_postorder<'a, 'tcx>(body: &'a Body<'tcx>) -> ReversePostorderIter<'a, 'tcx> {
338 let blocks = body.basic_blocks.postorder();
339 let len = blocks.len();
340 ReversePostorderIter { body, blocks, idx: len }
343 #[derive(Clone, Debug)]
344 pub(super) struct PostorderCache {
345 cache: OnceCell<Vec<BasicBlock>>,
348 impl PostorderCache {
350 pub(super) fn new() -> Self {
351 PostorderCache { cache: OnceCell::new() }
354 /// Invalidates the postorder cache.
356 pub(super) fn invalidate(&mut self) {
357 self.cache = OnceCell::new();
360 /// Returns the `&[BasicBlocks]` represents the postorder graph for this MIR.
362 pub(super) fn compute(&self, body: &IndexVec<BasicBlock, BasicBlockData<'_>>) -> &[BasicBlock] {
363 self.cache.get_or_init(|| Postorder::new(body, START_BLOCK).map(|(bb, _)| bb).collect())
367 impl<S: Encoder> Encodable<S> for PostorderCache {
369 fn encode(&self, _s: &mut S) {}
372 impl<D: Decoder> Decodable<D> for PostorderCache {
374 fn decode(_: &mut D) -> Self {
379 impl<CTX> HashStable<CTX> for PostorderCache {
381 fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {
386 TrivialTypeTraversalAndLiftImpls! {