src/librustc_middle/mir/predecessors.rs

   1 //! Lazily compute the reverse control-flow graph for the MIR.
   2
   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 as serialize;
   7 use smallvec::SmallVec;
   8
   9 use crate::mir::{BasicBlock, BasicBlockData};
  10
  11 // Typically 95%+ of basic blocks have 4 or fewer predecessors.
  12 pub type Predecessors = IndexVec<BasicBlock, SmallVec<[BasicBlock; 4]>>;
  13
  14 #[derive(Clone, Debug)]
  15 pub(super) struct PredecessorCache {
  16     cache: OnceCell<Predecessors>,
  17 }
  18
  19 impl PredecessorCache {
  20     #[inline]
  21     pub(super) fn new() -> Self {
  22         PredecessorCache { cache: OnceCell::new() }
  23     }
  24
  25     /// Invalidates the predecessor cache.
  26     #[inline]
  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();
  34     }
  35
  36     /// Returns the the predecessor graph for this MIR.
  37     #[inline]
  38     pub(super) fn compute(
  39         &self,
  40         basic_blocks: &IndexVec<BasicBlock, BasicBlockData<'_>>,
  41     ) -> &Predecessors {
  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() {
  47                         preds[succ].push(bb);
  48                     }
  49                 }
  50             }
  51
  52             preds
  53         })
  54     }
  55 }
  56
  57 impl serialize::Encodable for PredecessorCache {
  58     #[inline]
  59     fn encode<S: serialize::Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
  60         serialize::Encodable::encode(&(), s)
  61     }
  62 }
  63
  64 impl serialize::Decodable for PredecessorCache {
  65     #[inline]
  66     fn decode<D: serialize::Decoder>(d: &mut D) -> Result<Self, D::Error> {
  67         serialize::Decodable::decode(d).map(|_v: ()| Self::new())
  68     }
  69 }
  70
  71 impl<CTX> HashStable<CTX> for PredecessorCache {
  72     #[inline]
  73     fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {
  74         // do nothing
  75     }
  76 }
  77
  78 CloneTypeFoldableAndLiftImpls! {
  79     PredecessorCache,
  80 }