1 use rustc_index
::bit_set
::BitSet
;
5 /// Preorder traversal of a graph.
7 /// Preorder traversal is when each node is visited before any of its
21 /// A preorder traversal of this graph is either `A B D C` or `A C D B`
23 pub struct Preorder
<'a
, 'tcx
> {
25 visited
: BitSet
<BasicBlock
>,
26 worklist
: Vec
<BasicBlock
>,
27 root_is_start_block
: bool
,
30 impl<'a
, 'tcx
> Preorder
<'a
, 'tcx
> {
31 pub fn new(body
: &'a Body
<'tcx
>, root
: BasicBlock
) -> Preorder
<'a
, 'tcx
> {
32 let worklist
= vec
![root
];
36 visited
: BitSet
::new_empty(body
.basic_blocks().len()),
38 root_is_start_block
: root
== START_BLOCK
,
43 pub fn preorder
<'a
, 'tcx
>(body
: &'a Body
<'tcx
>) -> Preorder
<'a
, 'tcx
> {
44 Preorder
::new(body
, START_BLOCK
)
47 impl<'a
, 'tcx
> Iterator
for Preorder
<'a
, 'tcx
> {
48 type Item
= (BasicBlock
, &'a BasicBlockData
<'tcx
>);
50 fn next(&mut self) -> Option
<(BasicBlock
, &'a BasicBlockData
<'tcx
>)> {
51 while let Some(idx
) = self.worklist
.pop() {
52 if !self.visited
.insert(idx
) {
56 let data
= &self.body
[idx
];
58 if let Some(ref term
) = data
.terminator
{
59 self.worklist
.extend(term
.successors());
62 return Some((idx
, data
));
68 fn size_hint(&self) -> (usize, Option
<usize>) {
69 // All the blocks, minus the number of blocks we've visited.
70 let upper
= self.body
.basic_blocks().len() - self.visited
.count();
72 let lower
= if self.root_is_start_block
{
73 // We will visit all remaining blocks exactly once.
83 /// Postorder traversal of a graph.
85 /// Postorder traversal is when each node is visited after all of its
86 /// successors, except when the successor is only reachable by a back-edge
100 /// A Postorder traversal of this graph is `D B C A` or `D C B A`
101 pub struct Postorder
<'a
, 'tcx
> {
102 body
: &'a Body
<'tcx
>,
103 visited
: BitSet
<BasicBlock
>,
104 visit_stack
: Vec
<(BasicBlock
, Successors
<'a
>)>,
105 root_is_start_block
: bool
,
108 impl<'a
, 'tcx
> Postorder
<'a
, 'tcx
> {
109 pub fn new(body
: &'a Body
<'tcx
>, root
: BasicBlock
) -> Postorder
<'a
, 'tcx
> {
110 let mut po
= Postorder
{
112 visited
: BitSet
::new_empty(body
.basic_blocks().len()),
113 visit_stack
: Vec
::new(),
114 root_is_start_block
: root
== START_BLOCK
,
117 let data
= &po
.body
[root
];
119 if let Some(ref term
) = data
.terminator
{
120 po
.visited
.insert(root
);
121 po
.visit_stack
.push((root
, term
.successors()));
122 po
.traverse_successor();
128 fn traverse_successor(&mut self) {
129 // This is quite a complex loop due to 1. the borrow checker not liking it much
130 // and 2. what exactly is going on is not clear
132 // It does the actual traversal of the graph, while the `next` method on the iterator
133 // just pops off of the stack. `visit_stack` is a stack containing pairs of nodes and
134 // iterators over the successors of those nodes. Each iteration attempts to get the next
135 // node from the top of the stack, then pushes that node and an iterator over the
136 // successors to the top of the stack. This loop only grows `visit_stack`, stopping when
137 // we reach a child that has no children that we haven't already visited.
139 // For a graph that looks like this:
152 // The state of the stack starts out with just the root node (`A` in this case);
155 // When the first call to `traverse_successor` happens, the following happens:
157 // [(B, [D]), // `B` taken from the successors of `A`, pushed to the
158 // // top of the stack along with the successors of `B`
161 // [(D, [E]), // `D` taken from successors of `B`, pushed to stack
165 // [(E, []), // `E` taken from successors of `D`, pushed to stack
170 // Now that the top of the stack has no successors we can traverse, each item will
171 // be popped off during iteration until we get back to `A`. This yields [E, D, B].
173 // When we yield `B` and call `traverse_successor`, we push `C` to the stack, but
174 // since we've already visited `E`, that child isn't added to the stack. The last
175 // two iterations yield `C` and finally `A` for a final traversal of [E, D, B, C, A]
177 let bb
= if let Some(&mut (_
, ref mut iter
)) = self.visit_stack
.last_mut() {
178 if let Some(&bb
) = iter
.next() {
187 if self.visited
.insert(bb
) {
188 if let Some(term
) = &self.body
[bb
].terminator
{
189 self.visit_stack
.push((bb
, term
.successors()));
196 pub fn postorder
<'a
, 'tcx
>(body
: &'a Body
<'tcx
>) -> Postorder
<'a
, 'tcx
> {
197 Postorder
::new(body
, START_BLOCK
)
200 impl<'a
, 'tcx
> Iterator
for Postorder
<'a
, 'tcx
> {
201 type Item
= (BasicBlock
, &'a BasicBlockData
<'tcx
>);
203 fn next(&mut self) -> Option
<(BasicBlock
, &'a BasicBlockData
<'tcx
>)> {
204 let next
= self.visit_stack
.pop();
206 self.traverse_successor();
209 next
.map(|(bb
, _
)| (bb
, &self.body
[bb
]))
212 fn size_hint(&self) -> (usize, Option
<usize>) {
213 // All the blocks, minus the number of blocks we've visited.
214 let upper
= self.body
.basic_blocks().len() - self.visited
.count();
216 let lower
= if self.root_is_start_block
{
217 // We will visit all remaining blocks exactly once.
220 self.visit_stack
.len()
227 /// Reverse postorder traversal of a graph
229 /// Reverse postorder is the reverse order of a postorder traversal.
230 /// This is different to a preorder traversal and represents a natural
231 /// linearization of control-flow.
244 /// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
245 /// Note that for a graph containing no loops (i.e., A DAG), this is equivalent to
246 /// a topological sort.
248 /// Construction of a `ReversePostorder` traversal requires doing a full
249 /// postorder traversal of the graph, therefore this traversal should be
250 /// constructed as few times as possible. Use the `reset` method to be able
251 /// to re-use the traversal
253 pub struct ReversePostorder
<'a
, 'tcx
> {
254 body
: &'a Body
<'tcx
>,
255 blocks
: Vec
<BasicBlock
>,
259 impl<'a
, 'tcx
> ReversePostorder
<'a
, 'tcx
> {
260 pub fn new(body
: &'a Body
<'tcx
>, root
: BasicBlock
) -> ReversePostorder
<'a
, 'tcx
> {
261 let blocks
: Vec
<_
> = Postorder
::new(body
, root
).map(|(bb
, _
)| bb
).collect();
263 let len
= blocks
.len();
265 ReversePostorder { body, blocks, idx: len }
268 pub fn reset(&mut self) {
269 self.idx
= self.blocks
.len();
273 pub fn reverse_postorder
<'a
, 'tcx
>(body
: &'a Body
<'tcx
>) -> ReversePostorder
<'a
, 'tcx
> {
274 ReversePostorder
::new(body
, START_BLOCK
)
277 impl<'a
, 'tcx
> Iterator
for ReversePostorder
<'a
, 'tcx
> {
278 type Item
= (BasicBlock
, &'a BasicBlockData
<'tcx
>);
280 fn next(&mut self) -> Option
<(BasicBlock
, &'a BasicBlockData
<'tcx
>)> {
286 self.blocks
.get(self.idx
).map(|&bb
| (bb
, &self.body
[bb
]))
289 fn size_hint(&self) -> (usize, Option
<usize>) {
290 (self.idx
, Some(self.idx
))
294 impl<'a
, 'tcx
> ExactSizeIterator
for ReversePostorder
<'a
, 'tcx
> {}