[rustc.git] / compiler / rustc_middle / src / mir / traversal.rs

use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
use rustc_data_structures::sync::OnceCell;
use rustc_index::bit_set::BitSet;
use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};

use super::*;

/// Preorder traversal of a graph.
///
/// Preorder traversal is when each node is visited after at least one of its predecessors. If you
/// are familiar with some basic graph theory, then this performs a depth first search and returns
/// nodes in order of discovery time.
///
/// ```text
///
///         A
///        / \
///       /   \
///      B     C
///       \   /
///        \ /
///         D
/// ```
///
/// A preorder traversal of this graph is either `A B D C` or `A C D B`
#[derive(Clone)]
pub struct Preorder<'a, 'tcx> {
    body: &'a Body<'tcx>,
    visited: BitSet<BasicBlock>,
    worklist: Vec<BasicBlock>,
    root_is_start_block: bool,
}

impl<'a, 'tcx> Preorder<'a, 'tcx> {
    pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> Preorder<'a, 'tcx> {
        let worklist = vec![root];

        Preorder {
            body,
            visited: BitSet::new_empty(body.basic_blocks().len()),
            worklist,
            root_is_start_block: root == START_BLOCK,
        }
    }
}

pub fn preorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Preorder<'a, 'tcx> {
    Preorder::new(body, START_BLOCK)
}

impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> {
    type Item = (BasicBlock, &'a BasicBlockData<'tcx>);

    fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
        while let Some(idx) = self.worklist.pop() {
            if !self.visited.insert(idx) {
                continue;
            }

            let data = &self.body[idx];

            if let Some(ref term) = data.terminator {
                self.worklist.extend(term.successors());
            }

            return Some((idx, data));
        }

        None
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        // All the blocks, minus the number of blocks we've visited.
        let upper = self.body.basic_blocks().len() - self.visited.count();

        let lower = if self.root_is_start_block {
            // We will visit all remaining blocks exactly once.
            upper
        } else {
            self.worklist.len()
        };

        (lower, Some(upper))
    }
}

/// Postorder traversal of a graph.
///
/// Postorder traversal is when each node is visited after all of its successors, except when the
/// successor is only reachable by a back-edge. If you are familiar with some basic graph theory,
/// then this performs a depth first search and returns nodes in order of completion time.
///
///
/// ```text
///
///         A
///        / \
///       /   \
///      B     C
///       \   /
///        \ /
///         D
/// ```
///
/// A Postorder traversal of this graph is `D B C A` or `D C B A`
pub struct Postorder<'a, 'tcx> {
    body: &'a Body<'tcx>,
    visited: BitSet<BasicBlock>,
    visit_stack: Vec<(BasicBlock, Successors<'a>)>,
    root_is_start_block: bool,
}

impl<'a, 'tcx> Postorder<'a, 'tcx> {
    pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> Postorder<'a, 'tcx> {
        let mut po = Postorder {
            body,
            visited: BitSet::new_empty(body.basic_blocks().len()),
            visit_stack: Vec::new(),
            root_is_start_block: root == START_BLOCK,
        };

        let data = &po.body[root];

        if let Some(ref term) = data.terminator {
            po.visited.insert(root);
            po.visit_stack.push((root, term.successors()));
            po.traverse_successor();
        }

        po
    }

    fn traverse_successor(&mut self) {
        // This is quite a complex loop due to 1. the borrow checker not liking it much
        // and 2. what exactly is going on is not clear
        //
        // It does the actual traversal of the graph, while the `next` method on the iterator
        // just pops off of the stack. `visit_stack` is a stack containing pairs of nodes and
        // iterators over the successors of those nodes. Each iteration attempts to get the next
        // node from the top of the stack, then pushes that node and an iterator over the
        // successors to the top of the stack. This loop only grows `visit_stack`, stopping when
        // we reach a child that has no children that we haven't already visited.
        //
        // For a graph that looks like this:
        //
        //         A
        //        / \
        //       /   \
        //      B     C
        //      |     |
        //      |     |
        //      D     |
        //       \   /
        //        \ /
        //         E
        //
        // The state of the stack starts out with just the root node (`A` in this case);
        //     [(A, [B, C])]
        //
        // When the first call to `traverse_successor` happens, the following happens:
        //
        //     [(B, [D]),  // `B` taken from the successors of `A`, pushed to the
        //                 // top of the stack along with the successors of `B`
        //      (A, [C])]
        //
        //     [(D, [E]),  // `D` taken from successors of `B`, pushed to stack
        //      (B, []),
        //      (A, [C])]
        //
        //     [(E, []),   // `E` taken from successors of `D`, pushed to stack
        //      (D, []),
        //      (B, []),
        //      (A, [C])]
        //
        // Now that the top of the stack has no successors we can traverse, each item will
        // be popped off during iteration until we get back to `A`. This yields [E, D, B].
        //
        // When we yield `B` and call `traverse_successor`, we push `C` to the stack, but
        // since we've already visited `E`, that child isn't added to the stack. The last
        // two iterations yield `C` and finally `A` for a final traversal of [E, D, B, C, A]
        loop {
            let bb = if let Some(&mut (_, ref mut iter)) = self.visit_stack.last_mut() {
                if let Some(bb) = iter.next() {
                    bb
                } else {
                    break;
                }
            } else {
                break;
            };

            if self.visited.insert(bb) {
                if let Some(term) = &self.body[bb].terminator {
                    self.visit_stack.push((bb, term.successors()));
                }
            }
        }
    }
}

pub fn postorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Postorder<'a, 'tcx> {
    Postorder::new(body, START_BLOCK)
}

impl<'a, 'tcx> Iterator for Postorder<'a, 'tcx> {
    type Item = (BasicBlock, &'a BasicBlockData<'tcx>);

    fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
        let next = self.visit_stack.pop();
        if next.is_some() {
            self.traverse_successor();
        }

        next.map(|(bb, _)| (bb, &self.body[bb]))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        // All the blocks, minus the number of blocks we've visited.
        let upper = self.body.basic_blocks().len() - self.visited.count();

        let lower = if self.root_is_start_block {
            // We will visit all remaining blocks exactly once.
            upper
        } else {
            self.visit_stack.len()
        };

        (lower, Some(upper))
    }
}

/// Reverse postorder traversal of a graph
///
/// Reverse postorder is the reverse order of a postorder traversal.
/// This is different to a preorder traversal and represents a natural
/// linearization of control-flow.
///
/// ```text
///
///         A
///        / \
///       /   \
///      B     C
///       \   /
///        \ /
///         D
/// ```
///
/// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
/// Note that for a graph containing no loops (i.e., A DAG), this is equivalent to
/// a topological sort.
///
/// Construction of a `ReversePostorder` traversal requires doing a full
/// postorder traversal of the graph, therefore this traversal should be
/// constructed as few times as possible. Use the `reset` method to be able
/// to re-use the traversal
#[derive(Clone)]
pub struct ReversePostorder<'a, 'tcx> {
    body: &'a Body<'tcx>,
    blocks: Vec<BasicBlock>,
    idx: usize,
}

impl<'a, 'tcx> ReversePostorder<'a, 'tcx> {
    pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> ReversePostorder<'a, 'tcx> {
        let blocks: Vec<_> = Postorder::new(body, root).map(|(bb, _)| bb).collect();

        let len = blocks.len();

        ReversePostorder { body, blocks, idx: len }
    }
}

impl<'a, 'tcx> Iterator for ReversePostorder<'a, 'tcx> {
    type Item = (BasicBlock, &'a BasicBlockData<'tcx>);

    fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
        if self.idx == 0 {
            return None;
        }
        self.idx -= 1;

        self.blocks.get(self.idx).map(|&bb| (bb, &self.body[bb]))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.idx, Some(self.idx))
    }
}

impl<'a, 'tcx> ExactSizeIterator for ReversePostorder<'a, 'tcx> {}

/// Returns an iterator over all basic blocks reachable from the `START_BLOCK` in no particular
/// order.
///
/// This is clearer than writing `preorder` in cases where the order doesn't matter.
pub fn reachable<'a, 'tcx>(
    body: &'a Body<'tcx>,
) -> impl 'a + Iterator<Item = (BasicBlock, &'a BasicBlockData<'tcx>)> {
    preorder(body)
}

/// Returns a `BitSet` containing all basic blocks reachable from the `START_BLOCK`.
pub fn reachable_as_bitset<'tcx>(body: &Body<'tcx>) -> BitSet<BasicBlock> {
    let mut iter = preorder(body);
    (&mut iter).for_each(drop);
    iter.visited
}

#[derive(Clone)]
pub struct ReversePostorderIter<'a, 'tcx> {
    body: &'a Body<'tcx>,
    blocks: &'a [BasicBlock],
    idx: usize,
}

impl<'a, 'tcx> Iterator for ReversePostorderIter<'a, 'tcx> {
    type Item = (BasicBlock, &'a BasicBlockData<'tcx>);

    fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
        if self.idx == 0 {
            return None;
        }
        self.idx -= 1;

        self.blocks.get(self.idx).map(|&bb| (bb, &self.body[bb]))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.idx, Some(self.idx))
    }
}

impl<'a, 'tcx> ExactSizeIterator for ReversePostorderIter<'a, 'tcx> {}

pub fn reverse_postorder<'a, 'tcx>(body: &'a Body<'tcx>) -> ReversePostorderIter<'a, 'tcx> {
    let blocks = body.postorder_cache.compute(body);

    let len = blocks.len();

    ReversePostorderIter { body, blocks, idx: len }
}

#[derive(Clone, Debug)]
pub(super) struct PostorderCache {
    cache: OnceCell<Vec<BasicBlock>>,
}

impl PostorderCache {
    #[inline]
    pub(super) fn new() -> Self {
        PostorderCache { cache: OnceCell::new() }
    }

    /// Invalidates the postorder cache.
    #[inline]
    pub(super) fn invalidate(&mut self) {
        self.cache = OnceCell::new();
    }

    /// Returns the `&[BasicBlocks]` represents the postorder graph for this MIR.
    #[inline]
    pub(super) fn compute(&self, body: &Body<'_>) -> &[BasicBlock] {
        self.cache.get_or_init(|| Postorder::new(body, START_BLOCK).map(|(bb, _)| bb).collect())
    }
}

impl<S: Encoder> Encodable<S> for PostorderCache {
    #[inline]
    fn encode(&self, _s: &mut S) {}
}

impl<D: Decoder> Decodable<D> for PostorderCache {
    #[inline]
    fn decode(_: &mut D) -> Self {
        Self::new()
    }
}

impl<CTX> HashStable<CTX> for PostorderCache {
    #[inline]
    fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {
        // do nothing
    }
}

TrivialTypeFoldableAndLiftImpls! {
    PostorderCache,
}
Commit	Line	Data
04454e1e FG	1	use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
04454e1e FG	2	use rustc_data_structures::sync::OnceCell;
e74abb32	3	use rustc_index::bit_set::BitSet;
923072b8	4	use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
54a0048b	5
c30ab7b3	6	use super::*;
54a0048b SL	7
	8	/// Preorder traversal of a graph.
	9	///
5099ac24	10	/// Preorder traversal is when each node is visited after at least one of its predecessors. If you
5e7ed085	11	/// are familiar with some basic graph theory, then this performs a depth first search and returns
5099ac24	12	/// nodes in order of discovery time.
54a0048b	13	///
a7813a04 XL	14	/// ```text
a7813a04 XL	15	///
54a0048b SL	16	/// A
	17	/// / \
	18	/// / \
	19	/// B C
	20	/// \ /
	21	/// \ /
	22	/// D
a7813a04	23	/// ```
54a0048b SL	24	///
	25	/// A preorder traversal of this graph is either `A B D C` or `A C D B`
	26	#[derive(Clone)]
dc9dc135 XL	27	pub struct Preorder<'a, 'tcx> {
dc9dc135 XL	28	body: &'a Body<'tcx>,
0bf4aa26	29	visited: BitSet<BasicBlock>,
54a0048b	30	worklist: Vec<BasicBlock>,
a1dfa0c6	31	root_is_start_block: bool,
54a0048b SL	32	}
	33
	34	impl<'a, 'tcx> Preorder<'a, 'tcx> {
dc9dc135	35	pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> Preorder<'a, 'tcx> {
54a0048b SL	36	let worklist = vec![root];
	37
	38	Preorder {
dc9dc135 XL	39	body,
dc9dc135 XL	40	visited: BitSet::new_empty(body.basic_blocks().len()),
041b39d2	41	worklist,
a1dfa0c6	42	root_is_start_block: root == START_BLOCK,
54a0048b SL	43	}
	44	}
	45	}
	46
dc9dc135 XL	47	pub fn preorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Preorder<'a, 'tcx> {
dc9dc135 XL	48	Preorder::new(body, START_BLOCK)
54a0048b SL	49	}
	50
	51	impl<'a, 'tcx> Iterator for Preorder<'a, 'tcx> {
	52	type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
	53
	54	fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
	55	while let Some(idx) = self.worklist.pop() {
8faf50e0	56	if !self.visited.insert(idx) {
54a0048b SL	57	continue;
	58	}
	59
dc9dc135	60	let data = &self.body[idx];
54a0048b SL	61
54a0048b SL	62	if let Some(ref term) = data.terminator {
8faf50e0	63	self.worklist.extend(term.successors());
54a0048b SL	64	}
	65
	66	return Some((idx, data));
	67	}
	68
	69	None
	70	}
0531ce1d XL	71
	72	fn size_hint(&self) -> (usize, Option<usize>) {
	73	// All the blocks, minus the number of blocks we've visited.
dc9dc135	74	let upper = self.body.basic_blocks().len() - self.visited.count();
0531ce1d	75
a1dfa0c6 XL	76	let lower = if self.root_is_start_block {
	77	// We will visit all remaining blocks exactly once.
	78	upper
	79	} else {
	80	self.worklist.len()
	81	};
	82
	83	(lower, Some(upper))
0531ce1d	84	}
54a0048b SL	85	}
	86
	87	/// Postorder traversal of a graph.
	88	///
5099ac24 FG	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.
54a0048b	92	///
a7813a04 XL	93	///
	94	/// ```text
	95	///
54a0048b SL	96	/// A
	97	/// / \
	98	/// / \
	99	/// B C
	100	/// \ /
	101	/// \ /
	102	/// D
a7813a04	103	/// ```
54a0048b SL	104	///
54a0048b SL	105	/// A Postorder traversal of this graph is `D B C A` or `D C B A`
dc9dc135 XL	106	pub struct Postorder<'a, 'tcx> {
dc9dc135 XL	107	body: &'a Body<'tcx>,
0bf4aa26	108	visited: BitSet<BasicBlock>,
a1dfa0c6 XL	109	visit_stack: Vec<(BasicBlock, Successors<'a>)>,
a1dfa0c6 XL	110	root_is_start_block: bool,
54a0048b SL	111	}
	112
	113	impl<'a, 'tcx> Postorder<'a, 'tcx> {
dc9dc135	114	pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> Postorder<'a, 'tcx> {
54a0048b	115	let mut po = Postorder {
dc9dc135 XL	116	body,
dc9dc135 XL	117	visited: BitSet::new_empty(body.basic_blocks().len()),
a1dfa0c6 XL	118	visit_stack: Vec::new(),
a1dfa0c6 XL	119	root_is_start_block: root == START_BLOCK,
54a0048b SL	120	};
54a0048b SL	121
dc9dc135	122	let data = &po.body[root];
54a0048b SL	123
54a0048b SL	124	if let Some(ref term) = data.terminator {
8faf50e0	125	po.visited.insert(root);
83c7162d	126	po.visit_stack.push((root, term.successors()));
54a0048b SL	127	po.traverse_successor();
	128	}
	129
	130	po
	131	}
	132
	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
	136	//
	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
a1dfa0c6	139	// iterators over the successors of those nodes. Each iteration attempts to get the next
54a0048b SL	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.
	143	//
	144	// For a graph that looks like this:
	145	//
	146	// A
	147	// / \
	148	// / \
	149	// B C
	150	// \| \|
	151	// \| \|
	152	// D \|
	153	// \ /
	154	// \ /
	155	// E
	156	//
	157	// The state of the stack starts out with just the root node (`A` in this case);
	158	// [(A, [B, C])]
	159	//
a1dfa0c6	160	// When the first call to `traverse_successor` happens, the following happens:
54a0048b SL	161	//
	162	// [(B, [D]), // `B` taken from the successors of `A`, pushed to the
	163	// // top of the stack along with the successors of `B`
	164	// (A, [C])]
	165	//
	166	// [(D, [E]), // `D` taken from successors of `B`, pushed to stack
	167	// (B, []),
	168	// (A, [C])]
	169	//
	170	// [(E, []), // `E` taken from successors of `D`, pushed to stack
	171	// (D, []),
	172	// (B, []),
	173	// (A, [C])]
	174	//
	175	// Now that the top of the stack has no successors we can traverse, each item will
b7449926	176	// be popped off during iteration until we get back to `A`. This yields [E, D, B].
54a0048b SL	177	//
	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]
	181	loop {
	182	let bb = if let Some(&mut (_, ref mut iter)) = self.visit_stack.last_mut() {
923072b8	183	if let Some(bb) = iter.next() {
54a0048b SL	184	bb
	185	} else {
	186	break;
	187	}
	188	} else {
	189	break;
	190	};
	191
8faf50e0	192	if self.visited.insert(bb) {
dc9dc135	193	if let Some(term) = &self.body[bb].terminator {
83c7162d	194	self.visit_stack.push((bb, term.successors()));
54a0048b SL	195	}
	196	}
	197	}
	198	}
	199	}
	200
dc9dc135 XL	201	pub fn postorder<'a, 'tcx>(body: &'a Body<'tcx>) -> Postorder<'a, 'tcx> {
dc9dc135 XL	202	Postorder::new(body, START_BLOCK)
54a0048b SL	203	}
	204
	205	impl<'a, 'tcx> Iterator for Postorder<'a, 'tcx> {
	206	type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
	207
	208	fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
	209	let next = self.visit_stack.pop();
	210	if next.is_some() {
	211	self.traverse_successor();
	212	}
	213
dc9dc135	214	next.map(\|(bb, _)\| (bb, &self.body[bb]))
54a0048b	215	}
0531ce1d XL	216
	217	fn size_hint(&self) -> (usize, Option<usize>) {
	218	// All the blocks, minus the number of blocks we've visited.
dc9dc135	219	let upper = self.body.basic_blocks().len() - self.visited.count();
0531ce1d	220
a1dfa0c6 XL	221	let lower = if self.root_is_start_block {
	222	// We will visit all remaining blocks exactly once.
	223	upper
	224	} else {
	225	self.visit_stack.len()
	226	};
	227
	228	(lower, Some(upper))
0531ce1d	229	}
54a0048b SL	230	}
	231
	232	/// Reverse postorder traversal of a graph
	233	///
	234	/// Reverse postorder is the reverse order of a postorder traversal.
	235	/// This is different to a preorder traversal and represents a natural
3b2f2976	236	/// linearization of control-flow.
54a0048b	237	///
a7813a04 XL	238	/// ```text
a7813a04 XL	239	///
54a0048b SL	240	/// A
	241	/// / \
	242	/// / \
	243	/// B C
	244	/// \ /
	245	/// \ /
	246	/// D
a7813a04	247	/// ```
54a0048b SL	248	///
54a0048b SL	249	/// A reverse postorder traversal of this graph is either `A B C D` or `A C B D`
0731742a	250	/// Note that for a graph containing no loops (i.e., A DAG), this is equivalent to
54a0048b SL	251	/// a topological sort.
	252	///
	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
	257	#[derive(Clone)]
dc9dc135 XL	258	pub struct ReversePostorder<'a, 'tcx> {
dc9dc135 XL	259	body: &'a Body<'tcx>,
54a0048b	260	blocks: Vec<BasicBlock>,
dfeec247	261	idx: usize,
54a0048b SL	262	}
	263
	264	impl<'a, 'tcx> ReversePostorder<'a, 'tcx> {
dc9dc135	265	pub fn new(body: &'a Body<'tcx>, root: BasicBlock) -> ReversePostorder<'a, 'tcx> {
dfeec247	266	let blocks: Vec<_> = Postorder::new(body, root).map(\|(bb, _)\| bb).collect();
54a0048b SL	267
	268	let len = blocks.len();
	269
dfeec247	270	ReversePostorder { body, blocks, idx: len }
54a0048b	271	}
54a0048b SL	272	}
54a0048b SL	273
54a0048b SL	274	impl<'a, 'tcx> Iterator for ReversePostorder<'a, 'tcx> {
	275	type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
	276
	277	fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
dfeec247 XL	278	if self.idx == 0 {
	279	return None;
	280	}
54a0048b SL	281	self.idx -= 1;
54a0048b SL	282
dc9dc135	283	self.blocks.get(self.idx).map(\|&bb\| (bb, &self.body[bb]))
54a0048b	284	}
0531ce1d XL	285
	286	fn size_hint(&self) -> (usize, Option<usize>) {
	287	(self.idx, Some(self.idx))
	288	}
54a0048b	289	}
0531ce1d XL	290
0531ce1d XL	291	impl<'a, 'tcx> ExactSizeIterator for ReversePostorder<'a, 'tcx> {}
3dfed10e XL	292
	293	/// Returns an iterator over all basic blocks reachable from the `START_BLOCK` in no particular
	294	/// order.
	295	///
	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>)> {
	300	preorder(body)
	301	}
	302
	303	/// Returns a `BitSet` containing all basic blocks reachable from the `START_BLOCK`.
a2a8927a	304	pub fn reachable_as_bitset<'tcx>(body: &Body<'tcx>) -> BitSet<BasicBlock> {
3dfed10e XL	305	let mut iter = preorder(body);
	306	(&mut iter).for_each(drop);
	307	iter.visited
	308	}
04454e1e FG	309
	310	#[derive(Clone)]
	311	pub struct ReversePostorderIter<'a, 'tcx> {
	312	body: &'a Body<'tcx>,
923072b8	313	blocks: &'a [BasicBlock],
04454e1e FG	314	idx: usize,
	315	}
	316
	317	impl<'a, 'tcx> Iterator for ReversePostorderIter<'a, 'tcx> {
	318	type Item = (BasicBlock, &'a BasicBlockData<'tcx>);
	319
	320	fn next(&mut self) -> Option<(BasicBlock, &'a BasicBlockData<'tcx>)> {
	321	if self.idx == 0 {
	322	return None;
	323	}
	324	self.idx -= 1;
	325
	326	self.blocks.get(self.idx).map(\|&bb\| (bb, &self.body[bb]))
	327	}
	328
	329	fn size_hint(&self) -> (usize, Option<usize>) {
	330	(self.idx, Some(self.idx))
	331	}
	332	}
	333
	334	impl<'a, 'tcx> ExactSizeIterator for ReversePostorderIter<'a, 'tcx> {}
	335
	336	pub fn reverse_postorder<'a, 'tcx>(body: &'a Body<'tcx>) -> ReversePostorderIter<'a, 'tcx> {
	337	let blocks = body.postorder_cache.compute(body);
	338
	339	let len = blocks.len();
	340
	341	ReversePostorderIter { body, blocks, idx: len }
	342	}
	343
	344	#[derive(Clone, Debug)]
	345	pub(super) struct PostorderCache {
	346	cache: OnceCell<Vec<BasicBlock>>,
	347	}
	348
	349	impl PostorderCache {
	350	#[inline]
	351	pub(super) fn new() -> Self {
	352	PostorderCache { cache: OnceCell::new() }
	353	}
	354
	355	/// Invalidates the postorder cache.
	356	#[inline]
	357	pub(super) fn invalidate(&mut self) {
	358	self.cache = OnceCell::new();
	359	}
	360
923072b8	361	/// Returns the `&[BasicBlocks]` represents the postorder graph for this MIR.
04454e1e	362	#[inline]
923072b8	363	pub(super) fn compute(&self, body: &Body<'_>) -> &[BasicBlock] {
04454e1e FG	364	self.cache.get_or_init(\|\| Postorder::new(body, START_BLOCK).map(\|(bb, _)\| bb).collect())
	365	}
	366	}
	367
923072b8	368	impl<S: Encoder> Encodable<S> for PostorderCache {
04454e1e	369	#[inline]
923072b8	370	fn encode(&self, _s: &mut S) {}
04454e1e FG	371	}
04454e1e FG	372
923072b8	373	impl<D: Decoder> Decodable<D> for PostorderCache {
04454e1e FG	374	#[inline]
	375	fn decode(_: &mut D) -> Self {
	376	Self::new()
	377	}
	378	}
	379
	380	impl<CTX> HashStable<CTX> for PostorderCache {
	381	#[inline]
	382	fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {
	383	// do nothing
	384	}
	385	}
	386
	387	TrivialTypeFoldableAndLiftImpls! {
	388	PostorderCache,
	389	}