compiler/rustc_middle/src/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::{Decodable, Decoder, Encodable, Encoder};
   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 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<S: Encoder> Encodable<S> for PredecessorCache {
  58     #[inline]
  59     fn encode(&self, _s: &mut S) {}
  60 }
  61
  62 impl<D: Decoder> Decodable<D> for PredecessorCache {
  63     #[inline]
  64     fn decode(_: &mut D) -> Self {
  65         Self::new()
  66     }
  67 }
  68
  69 impl<CTX> HashStable<CTX> for PredecessorCache {
  70     #[inline]
  71     fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {
  72         // do nothing
  73     }
  74 }
  75
  76 TrivialTypeFoldableAndLiftImpls! {
  77     PredecessorCache,
  78 }