1 //! Lazily compute the reverse control-flow graph for the MIR.
3 use rustc_data_structures
::stable_hasher
::{HashStable, StableHasher}
;
4 use rustc_data_structures
::sync
::OnceCell
;
5 use rustc_index
::vec
::IndexVec
;
6 use rustc_serialize
::{Decodable, Decoder, Encodable, Encoder}
;
7 use smallvec
::SmallVec
;
9 use crate::mir
::{BasicBlock, BasicBlockData}
;
11 // Typically 95%+ of basic blocks have 4 or fewer predecessors.
12 pub type Predecessors
= IndexVec
<BasicBlock
, SmallVec
<[BasicBlock
; 4]>>;
14 #[derive(Clone, Debug)]
15 pub(super) struct PredecessorCache
{
16 cache
: OnceCell
<Predecessors
>,
19 impl PredecessorCache
{
21 pub(super) fn new() -> Self {
22 PredecessorCache { cache: OnceCell::new() }
25 /// Invalidates the predecessor cache.
27 pub(super) fn invalidate(&mut self) {
28 // Invalidating the predecessor cache requires mutating the MIR, which in turn requires a
29 // unique reference (`&mut`) to the `mir::Body`. Because of this, we can assume that all
30 // callers of `invalidate` have a unique reference to the MIR and thus to the predecessor
31 // cache. This means we never need to do synchronization when `invalidate` is called, we can
32 // simply reinitialize the `OnceCell`.
33 self.cache
= OnceCell
::new();
36 /// Returns the predecessor graph for this MIR.
38 pub(super) fn compute(
40 basic_blocks
: &IndexVec
<BasicBlock
, BasicBlockData
<'_
>>,
42 self.cache
.get_or_init(|| {
43 let mut preds
= IndexVec
::from_elem(SmallVec
::new(), basic_blocks
);
44 for (bb
, data
) in basic_blocks
.iter_enumerated() {
45 if let Some(term
) = &data
.terminator
{
46 for succ
in term
.successors() {
57 impl<S
: Encoder
> Encodable
<S
> for PredecessorCache
{
59 fn encode(&self, _s
: &mut S
) {}
62 impl<D
: Decoder
> Decodable
<D
> for PredecessorCache
{
64 fn decode(_
: &mut D
) -> Self {
69 impl<CTX
> HashStable
<CTX
> for PredecessorCache
{
71 fn hash_stable(&self, _
: &mut CTX
, _
: &mut StableHasher
) {
76 TrivialTypeTraversalAndLiftImpls
! {