rustc_middle/mir/
traversal.rs

1use super::*;
2
3/// Preorder traversal of a graph.
4///
5/// Preorder traversal is when each node is visited after at least one of its predecessors. If you
6/// are familiar with some basic graph theory, then this performs a depth first search and returns
7/// nodes in order of discovery time.
8///
9/// ```text
10///
11///         A
12///        / \
13///       /   \
14///      B     C
15///       \   /
16///        \ /
17///         D
18/// ```
19///
20/// A preorder traversal of this graph is either `A B D C` or `A C D B`
21#[derive(Clone)]
22pub struct Preorder<'a, 'tcx> {
23    body: &'a Body<'tcx>,
24    visited: DenseBitSet<BasicBlock>,
25    worklist: Vec<BasicBlock>,
26    root_is_start_block: bool,
27}
28
29impl<'a, 'tcx> Preorder<'a, 'tcx> {
30    pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> Preorder<'a, 'tcx> {
31        let worklist = vec![root];
32
33        Preorder {
34            body,
35            visited: DenseBitSet::new_empty(body.basic_blocks.len()),
36            worklist,
37            root_is_start_block: root == START_BLOCK,
38        }
39    }
40}
41
42/// Preorder traversal of a graph.
43///
44/// This function creates an iterator over the `Body`'s basic blocks, that
45/// returns basic blocks in a preorder.
46///
47/// See [`Preorder`]'s docs to learn what is preorder traversal.
48pub fn preorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Preorder<'a, 'tcx> {
49    Preorder::new(body, START_BLOCK)
50}
51
52impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> {
53    type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
54
55    fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
56        while let Some(idx) = self.worklist.pop() {
57            if !self.visited.insert(idx) {
58                continue;
59            }
60
61            let data = &self.body[idx];
62
63            if let Some(ref term) = data.terminator {
64                self.worklist.extend(term.successors());
65            }
66
67            return Some((idx, data));
68        }
69
70        None
71    }
72
73    fn size_hint(&self) -> (usize, Option<usize>) {
74        // All the blocks, minus the number of blocks we've visited.
75        let upper = self.body.basic_blocks.len() - self.visited.count();
76
77        let lower = if self.root_is_start_block {
78            // We will visit all remaining blocks exactly once.
79            upper
80        } else {
81            self.worklist.len()
82        };
83
84        (lower, Some(upper))
85    }
86}
87
88/// Postorder traversal of a graph.
89///
90/// Postorder traversal is when each node is visited after all of its successors, except when the
91/// successor is only reachable by a back-edge. If you are familiar with some basic graph theory,
92/// then this performs a depth first search and returns nodes in order of completion time.
93///
94///
95/// ```text
96///
97///         A
98///        / \
99///       /   \
100///      B     C
101///       \   /
102///        \ /
103///         D
104/// ```
105///
106/// A Postorder traversal of this graph is `D B C A` or `D C B A`
107pub struct Postorder<'a, 'tcx, C> {
108    basic_blocks: &'a IndexSlice<BasicBlock, BasicBlockData<'tcx>>,
109    visited: DenseBitSet<BasicBlock>,
110    visit_stack: Vec<(BasicBlock, Successors<'a>)>,
111    root_is_start_block: bool,
112    extra: C,
113}
114
115impl<'a, 'tcx, C> Postorder<'a, 'tcx, C>
116where
117    C: Customization<'tcx>,
118{
119    pub fn new(
120        basic_blocks: &'a IndexSlice<BasicBlock, BasicBlockData<'tcx>>,
121        root: BasicBlock,
122        extra: C,
123    ) -> Postorder<'a, 'tcx, C> {
124        let mut po = Postorder {
125            basic_blocks,
126            visited: DenseBitSet::new_empty(basic_blocks.len()),
127            visit_stack: Vec::new(),
128            root_is_start_block: root == START_BLOCK,
129            extra,
130        };
131
132        po.visit(root);
133        po.traverse_successor();
134
135        po
136    }
137
138    fn visit(&mut self, bb: BasicBlock) {
139        if !self.visited.insert(bb) {
140            return;
141        }
142        let data = &self.basic_blocks[bb];
143        let successors = C::successors(data, self.extra);
144        self.visit_stack.push((bb, successors));
145    }
146
147    fn traverse_successor(&mut self) {
148        // This is quite a complex loop due to 1. the borrow checker not liking it much
149        // and 2. what exactly is going on is not clear
150        //
151        // It does the actual traversal of the graph, while the `next` method on the iterator
152        // just pops off of the stack. `visit_stack` is a stack containing pairs of nodes and
153        // iterators over the successors of those nodes. Each iteration attempts to get the next
154        // node from the top of the stack, then pushes that node and an iterator over the
155        // successors to the top of the stack. This loop only grows `visit_stack`, stopping when
156        // we reach a child that has no children that we haven't already visited.
157        //
158        // For a graph that looks like this:
159        //
160        //         A
161        //        / \
162        //       /   \
163        //      B     C
164        //      |     |
165        //      |     |
166        //      |     D
167        //       \   /
168        //        \ /
169        //         E
170        //
171        // The state of the stack starts out with just the root node (`A` in this case);
172        //     [(A, [B, C])]
173        //
174        // When the first call to `traverse_successor` happens, the following happens:
175        //
176        //     [(C, [D]),  // `C` taken from the successors of `A`, pushed to the
177        //                 // top of the stack along with the successors of `C`
178        //      (A, [B])]
179        //
180        //     [(D, [E]),  // `D` taken from successors of `C`, pushed to stack
181        //      (C, []),
182        //      (A, [B])]
183        //
184        //     [(E, []),   // `E` taken from successors of `D`, pushed to stack
185        //      (D, []),
186        //      (C, []),
187        //      (A, [B])]
188        //
189        // Now that the top of the stack has no successors we can traverse, each item will
190        // be popped off during iteration until we get back to `A`. This yields [E, D, C].
191        //
192        // When we yield `C` and call `traverse_successor`, we push `B` to the stack, but
193        // since we've already visited `E`, that child isn't added to the stack. The last
194        // two iterations yield `B` and finally `A` for a final traversal of [E, D, C, B, A]
195        while let Some(bb) = self.visit_stack.last_mut().and_then(|(_, iter)| iter.next_back()) {
196            self.visit(bb);
197        }
198    }
199}
200
201impl<'tcx, C> Iterator for Postorder<'_, 'tcx, C>
202where
203    C: Customization<'tcx>,
204{
205    type Item = BasicBlock;
206
207    fn next(&mut self) -> Option<BasicBlock> {
208        let (bb, _) = self.visit_stack.pop()?;
209        self.traverse_successor();
210
211        Some(bb)
212    }
213
214    fn size_hint(&self) -> (usize, Option<usize>) {
215        // All the blocks, minus the number of blocks we've visited.
216        let upper = self.basic_blocks.len() - self.visited.count();
217
218        let lower = if self.root_is_start_block {
219            // We will visit all remaining blocks exactly once.
220            upper
221        } else {
222            self.visit_stack.len()
223        };
224
225        (lower, Some(upper))
226    }
227}
228
229/// Postorder traversal of a graph.
230///
231/// This function creates an iterator over the `Body`'s basic blocks, that:
232/// - returns basic blocks in a postorder,
233/// - traverses the `BasicBlocks` CFG cache's reverse postorder backwards, and does not cache the
234///   postorder itself.
235///
236/// See [`Postorder`]'s docs to learn what is postorder traversal.
237pub fn postorder<'a, 'tcx>(
238    body: &'a Body<'tcx>,
239) -> impl Iterator<Item = (BasicBlock, &'a BasicBlockData<'tcx>)> + ExactSizeIterator + DoubleEndedIterator
240{
241    reverse_postorder(body).rev()
242}
243
244/// Lets us plug in some additional logic and data into a Postorder traversal. Or not.
245pub trait Customization<'tcx>: Copy {
246    fn successors<'a>(_: &'a BasicBlockData<'tcx>, _: Self) -> Successors<'a>;
247}
248
249impl<'tcx> Customization<'tcx> for () {
250    fn successors<'a>(data: &'a BasicBlockData<'tcx>, _: ()) -> Successors<'a> {
251        data.terminator().successors()
252    }
253}
254
255impl<'tcx> Customization<'tcx> for (TyCtxt<'tcx>, Instance<'tcx>) {
256    fn successors<'a>(
257        data: &'a BasicBlockData<'tcx>,
258        (tcx, instance): (TyCtxt<'tcx>, Instance<'tcx>),
259    ) -> Successors<'a> {
260        data.mono_successors(tcx, instance)
261    }
262}
263
264pub fn mono_reachable_reverse_postorder<'a, 'tcx>(
265    body: &'a Body<'tcx>,
266    tcx: TyCtxt<'tcx>,
267    instance: Instance<'tcx>,
268) -> Vec<BasicBlock> {
269    let mut iter = Postorder::new(&body.basic_blocks, START_BLOCK, (tcx, instance));
270    let mut items = Vec::with_capacity(body.basic_blocks.len());
271    while let Some(block) = iter.next() {
272        items.push(block);
273    }
274    items.reverse();
275    items
276}
277
278/// Returns an iterator over all basic blocks reachable from the `START_BLOCK` in no particular
279/// order.
280///
281/// This is clearer than writing `preorder` in cases where the order doesn't matter.
282pub fn reachable<'a, 'tcx>(
283    body: &'a Body<'tcx>,
284) -> impl 'a + Iterator<Item = (BasicBlock, &'a BasicBlockData<'tcx>)> {
285    preorder(body)
286}
287
288/// Returns a `DenseBitSet` containing all basic blocks reachable from the `START_BLOCK`.
289pub fn reachable_as_bitset(body: &Body<'_>) -> DenseBitSet<BasicBlock> {
290    let mut iter = preorder(body);
291    while let Some(_) = iter.next() {}
292    iter.visited
293}
294
295/// Reverse postorder traversal of a graph.
296///
297/// This function creates an iterator over the `Body`'s basic blocks, that:
298/// - returns basic blocks in a reverse postorder,
299/// - makes use of the `BasicBlocks` CFG cache's reverse postorder.
300///
301/// Reverse postorder is the reverse order of a postorder traversal.
302/// This is different to a preorder traversal and represents a natural
303/// linearization of control-flow.
304///
305/// ```text
306///
307///         A
308///        / \
309///       /   \
310///      B     C
311///       \   /
312///        \ /
313///         D
314/// ```
315///
316/// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
317/// Note that for a graph containing no loops (i.e., A DAG), this is equivalent to
318/// a topological sort.
319pub fn reverse_postorder<'a, 'tcx>(
320    body: &'a Body<'tcx>,
321) -> impl Iterator<Item = (BasicBlock, &'a BasicBlockData<'tcx>)> + ExactSizeIterator + DoubleEndedIterator
322{
323    body.basic_blocks.reverse_postorder().iter().map(|&bb| (bb, &body.basic_blocks[bb]))
324}
325
326/// Traversal of a [`Body`] that tries to avoid unreachable blocks in a monomorphized [`Instance`].
327///
328/// This is allowed to have false positives; blocks may be visited even if they are not actually
329/// reachable.
330///
331/// Such a traversal is mostly useful because it lets us skip lowering the `false` side
332/// of `if <T as Trait>::CONST`, as well as [`NullOp::UbChecks`].
333///
334/// [`NullOp::UbChecks`]: rustc_middle::mir::NullOp::UbChecks
335pub fn mono_reachable<'a, 'tcx>(
336    body: &'a Body<'tcx>,
337    tcx: TyCtxt<'tcx>,
338    instance: Instance<'tcx>,
339) -> MonoReachable<'a, 'tcx> {
340    MonoReachable::new(body, tcx, instance)
341}
342
343/// [`MonoReachable`] internally accumulates a [`DenseBitSet`] of visited blocks. This is just a
344/// convenience function to run that traversal then extract its set of reached blocks.
345pub fn mono_reachable_as_bitset<'a, 'tcx>(
346    body: &'a Body<'tcx>,
347    tcx: TyCtxt<'tcx>,
348    instance: Instance<'tcx>,
349) -> DenseBitSet<BasicBlock> {
350    let mut iter = mono_reachable(body, tcx, instance);
351    while let Some(_) = iter.next() {}
352    iter.visited
353}
354
355pub struct MonoReachable<'a, 'tcx> {
356    body: &'a Body<'tcx>,
357    tcx: TyCtxt<'tcx>,
358    instance: Instance<'tcx>,
359    visited: DenseBitSet<BasicBlock>,
360    // Other traversers track their worklist in a Vec. But we don't care about order, so we can
361    // store ours in a DenseBitSet and thus save allocations because DenseBitSet has a small size
362    // optimization.
363    worklist: DenseBitSet<BasicBlock>,
364}
365
366impl<'a, 'tcx> MonoReachable<'a, 'tcx> {
367    pub fn new(
368        body: &'a Body<'tcx>,
369        tcx: TyCtxt<'tcx>,
370        instance: Instance<'tcx>,
371    ) -> MonoReachable<'a, 'tcx> {
372        let mut worklist = DenseBitSet::new_empty(body.basic_blocks.len());
373        worklist.insert(START_BLOCK);
374        MonoReachable {
375            body,
376            tcx,
377            instance,
378            visited: DenseBitSet::new_empty(body.basic_blocks.len()),
379            worklist,
380        }
381    }
382
383    fn add_work(&mut self, blocks: impl IntoIterator<Item = BasicBlock>) {
384        for block in blocks.into_iter() {
385            if !self.visited.contains(block) {
386                self.worklist.insert(block);
387            }
388        }
389    }
390}
391
392impl<'a, 'tcx> Iterator for MonoReachable<'a, 'tcx> {
393    type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
394
395    fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
396        while let Some(idx) = self.worklist.iter().next() {
397            self.worklist.remove(idx);
398            if !self.visited.insert(idx) {
399                continue;
400            }
401
402            let data = &self.body[idx];
403
404            let targets = data.mono_successors(self.tcx, self.instance);
405            self.add_work(targets);
406
407            return Some((idx, data));
408        }
409
410        None
411    }
412}
rustc_middle/mir/traversal.rs

rustc_middle/mir/
traversal.rs
