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 body
: &'a Body
<'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
> {
114 pub fn new(body
: &'a Body
<'tcx
>, root
: BasicBlock
) -> Postorder
<'a
, 'tcx
> {
115 let mut po
= Postorder
{
117 visited
: BitSet
::new_empty(body
.basic_blocks().len()),
118 visit_stack
: Vec
::new(),
119 root_is_start_block
: root
== START_BLOCK
,
122 let data
= &po
.body
[root
];
124 if let Some(ref term
) = data
.terminator
{
125 po
.visited
.insert(root
);
126 po
.visit_stack
.push((root
, term
.successors()));
127 po
.traverse_successor();
133 fn traverse_successor(&mut self) {
134 // This is quite a complex loop due to 1. the borrow checker not liking it much
135 // and 2. what exactly is going on is not clear
137 // It does the actual traversal of the graph, while the `next` method on the iterator
138 // just pops off of the stack. `visit_stack` is a stack containing pairs of nodes and
139 // iterators over the successors of those nodes. Each iteration attempts to get the next
140 // node from the top of the stack, then pushes that node and an iterator over the
141 // successors to the top of the stack. This loop only grows `visit_stack`, stopping when
142 // we reach a child that has no children that we haven't already visited.
144 // For a graph that looks like this:
157 // The state of the stack starts out with just the root node (`A` in this case);
160 // When the first call to `traverse_successor` happens, the following happens:
162 // [(B, [D]), // `B` taken from the successors of `A`, pushed to the
163 // // top of the stack along with the successors of `B`
166 // [(D, [E]), // `D` taken from successors of `B`, pushed to stack
170 // [(E, []), // `E` taken from successors of `D`, pushed to stack
175 // Now that the top of the stack has no successors we can traverse, each item will
176 // be popped off during iteration until we get back to `A`. This yields [E, D, B].
178 // When we yield `B` and call `traverse_successor`, we push `C` to the stack, but
179 // since we've already visited `E`, that child isn't added to the stack. The last
180 // two iterations yield `C` and finally `A` for a final traversal of [E, D, B, C, A]
182 let bb
= if let Some(&mut (_
, ref mut iter
)) = self.visit_stack
.last_mut() {
183 if let Some(bb
) = iter
.next() {
192 if self.visited
.insert(bb
) {
193 if let Some(term
) = &self.body
[bb
].terminator
{
194 self.visit_stack
.push((bb
, term
.successors()));
201 pub fn postorder
<'a
, 'tcx
>(body
: &'a Body
<'tcx
>) -> Postorder
<'a
, 'tcx
> {
202 Postorder
::new(body
, START_BLOCK
)
205 impl<'a
, 'tcx
> Iterator
for Postorder
<'a
, 'tcx
> {
206 type Item
= (BasicBlock
, &'a BasicBlockData
<'tcx
>);
208 fn next(&mut self) -> Option
<(BasicBlock
, &'a BasicBlockData
<'tcx
>)> {
209 let next
= self.visit_stack
.pop();
211 self.traverse_successor();
214 next
.map(|(bb
, _
)| (bb
, &self.body
[bb
]))
217 fn size_hint(&self) -> (usize, Option
<usize>) {
218 // All the blocks, minus the number of blocks we've visited.
219 let upper
= self.body
.basic_blocks().len() - self.visited
.count();
221 let lower
= if self.root_is_start_block
{
222 // We will visit all remaining blocks exactly once.
225 self.visit_stack
.len()
232 /// Reverse postorder traversal of a graph
234 /// Reverse postorder is the reverse order of a postorder traversal.
235 /// This is different to a preorder traversal and represents a natural
236 /// linearization of control-flow.
249 /// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
250 /// Note that for a graph containing no loops (i.e., A DAG), this is equivalent to
251 /// a topological sort.
253 /// Construction of a `ReversePostorder` traversal requires doing a full
254 /// postorder traversal of the graph, therefore this traversal should be
255 /// constructed as few times as possible. Use the `reset` method to be able
256 /// to re-use the traversal
258 pub struct ReversePostorder
<'a
, 'tcx
> {
259 body
: &'a Body
<'tcx
>,
260 blocks
: Vec
<BasicBlock
>,
264 impl<'a
, 'tcx
> ReversePostorder
<'a
, 'tcx
> {
265 pub fn new(body
: &'a Body
<'tcx
>, root
: BasicBlock
) -> ReversePostorder
<'a
, 'tcx
> {
266 let blocks
: Vec
<_
> = Postorder
::new(body
, root
).map(|(bb
, _
)| bb
).collect();
268 let len
= blocks
.len();
270 ReversePostorder { body, blocks, idx: len }
274 impl<'a
, 'tcx
> Iterator
for ReversePostorder
<'a
, 'tcx
> {
275 type Item
= (BasicBlock
, &'a BasicBlockData
<'tcx
>);
277 fn next(&mut self) -> Option
<(BasicBlock
, &'a BasicBlockData
<'tcx
>)> {
283 self.blocks
.get(self.idx
).map(|&bb
| (bb
, &self.body
[bb
]))
286 fn size_hint(&self) -> (usize, Option
<usize>) {
287 (self.idx
, Some(self.idx
))
291 impl<'a
, 'tcx
> ExactSizeIterator
for ReversePostorder
<'a
, 'tcx
> {}
293 /// Returns an iterator over all basic blocks reachable from the `START_BLOCK` in no particular
296 /// This is clearer than writing `preorder` in cases where the order doesn't matter.
297 pub fn reachable
<'a
, 'tcx
>(
298 body
: &'a Body
<'tcx
>,
299 ) -> impl 'a
+ Iterator
<Item
= (BasicBlock
, &'a BasicBlockData
<'tcx
>)> {
303 /// Returns a `BitSet` containing all basic blocks reachable from the `START_BLOCK`.
304 pub fn reachable_as_bitset
<'tcx
>(body
: &Body
<'tcx
>) -> BitSet
<BasicBlock
> {
305 let mut iter
= preorder(body
);
306 (&mut iter
).for_each(drop
);
311 pub struct ReversePostorderIter
<'a
, 'tcx
> {
312 body
: &'a Body
<'tcx
>,
313 blocks
: &'a
[BasicBlock
],
317 impl<'a
, 'tcx
> Iterator
for ReversePostorderIter
<'a
, 'tcx
> {
318 type Item
= (BasicBlock
, &'a BasicBlockData
<'tcx
>);
320 fn next(&mut self) -> Option
<(BasicBlock
, &'a BasicBlockData
<'tcx
>)> {
326 self.blocks
.get(self.idx
).map(|&bb
| (bb
, &self.body
[bb
]))
329 fn size_hint(&self) -> (usize, Option
<usize>) {
330 (self.idx
, Some(self.idx
))
334 impl<'a
, 'tcx
> ExactSizeIterator
for ReversePostorderIter
<'a
, 'tcx
> {}
336 pub fn reverse_postorder
<'a
, 'tcx
>(body
: &'a Body
<'tcx
>) -> ReversePostorderIter
<'a
, 'tcx
> {
337 let blocks
= body
.postorder_cache
.compute(body
);
339 let len
= blocks
.len();
341 ReversePostorderIter { body, blocks, idx: len }
344 #[derive(Clone, Debug)]
345 pub(super) struct PostorderCache
{
346 cache
: OnceCell
<Vec
<BasicBlock
>>,
349 impl PostorderCache
{
351 pub(super) fn new() -> Self {
352 PostorderCache { cache: OnceCell::new() }
355 /// Invalidates the postorder cache.
357 pub(super) fn invalidate(&mut self) {
358 self.cache
= OnceCell
::new();
361 /// Returns the `&[BasicBlocks]` represents the postorder graph for this MIR.
363 pub(super) fn compute(&self, body
: &Body
<'_
>) -> &[BasicBlock
] {
364 self.cache
.get_or_init(|| Postorder
::new(body
, START_BLOCK
).map(|(bb
, _
)| bb
).collect())
368 impl<S
: Encoder
> Encodable
<S
> for PostorderCache
{
370 fn encode(&self, _s
: &mut S
) {}
373 impl<D
: Decoder
> Decodable
<D
> for PostorderCache
{
375 fn decode(_
: &mut D
) -> Self {
380 impl<CTX
> HashStable
<CTX
> for PostorderCache
{
382 fn hash_stable(&self, _
: &mut CTX
, _
: &mut StableHasher
) {
387 TrivialTypeFoldableAndLiftImpls
! {