compiler/rustc_middle/src/mir/basic_blocks.rs

   1 use crate::mir::traversal::Postorder;
   2 use crate::mir::{BasicBlock, BasicBlockData, Successors, Terminator, TerminatorKind, START_BLOCK};
   3
   4 use rustc_data_structures::fx::FxHashMap;
   5 use rustc_data_structures::graph;
   6 use rustc_data_structures::graph::dominators::{dominators, Dominators};
   7 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
   8 use rustc_data_structures::sync::OnceCell;
   9 use rustc_index::vec::IndexVec;
  10 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
  11 use smallvec::SmallVec;
  12
  13 #[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable, TypeFoldable, TypeVisitable)]
  14 pub struct BasicBlocks<'tcx> {
  15     basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>,
  16     cache: Cache,
  17 }
  18
  19 // Typically 95%+ of basic blocks have 4 or fewer predecessors.
  20 pub type Predecessors = IndexVec<BasicBlock, SmallVec<[BasicBlock; 4]>>;
  21
  22 pub type SwitchSources = FxHashMap<(BasicBlock, BasicBlock), SmallVec<[Option<u128>; 1]>>;
  23
  24 #[derive(Clone, Default, Debug)]
  25 struct Cache {
  26     predecessors: OnceCell<Predecessors>,
  27     switch_sources: OnceCell<SwitchSources>,
  28     is_cyclic: OnceCell<bool>,
  29     postorder: OnceCell<Vec<BasicBlock>>,
  30 }
  31
  32 impl<'tcx> BasicBlocks<'tcx> {
  33     #[inline]
  34     pub fn new(basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>) -> Self {
  35         BasicBlocks { basic_blocks, cache: Cache::default() }
  36     }
  37
  38     /// Returns true if control-flow graph contains a cycle reachable from the `START_BLOCK`.
  39     #[inline]
  40     pub fn is_cfg_cyclic(&self) -> bool {
  41         *self.cache.is_cyclic.get_or_init(|| graph::is_cyclic(self))
  42     }
  43
  44     #[inline]
  45     pub fn dominators(&self) -> Dominators<BasicBlock> {
  46         dominators(&self)
  47     }
  48
  49     /// Returns predecessors for each basic block.
  50     #[inline]
  51     pub fn predecessors(&self) -> &Predecessors {
  52         self.cache.predecessors.get_or_init(|| {
  53             let mut preds = IndexVec::from_elem(SmallVec::new(), &self.basic_blocks);
  54             for (bb, data) in self.basic_blocks.iter_enumerated() {
  55                 if let Some(term) = &data.terminator {
  56                     for succ in term.successors() {
  57                         preds[succ].push(bb);
  58                     }
  59                 }
  60             }
  61             preds
  62         })
  63     }
  64
  65     /// Returns basic blocks in a postorder.
  66     #[inline]
  67     pub fn postorder(&self) -> &[BasicBlock] {
  68         self.cache.postorder.get_or_init(|| {
  69             Postorder::new(&self.basic_blocks, START_BLOCK).map(|(bb, _)| bb).collect()
  70         })
  71     }
  72
  73     /// `switch_sources()[&(target, switch)]` returns a list of switch
  74     /// values that lead to a `target` block from a `switch` block.
  75     #[inline]
  76     pub fn switch_sources(&self) -> &SwitchSources {
  77         self.cache.switch_sources.get_or_init(|| {
  78             let mut switch_sources: SwitchSources = FxHashMap::default();
  79             for (bb, data) in self.basic_blocks.iter_enumerated() {
  80                 if let Some(Terminator {
  81                     kind: TerminatorKind::SwitchInt { targets, .. }, ..
  82                 }) = &data.terminator
  83                 {
  84                     for (value, target) in targets.iter() {
  85                         switch_sources.entry((target, bb)).or_default().push(Some(value));
  86                     }
  87                     switch_sources.entry((targets.otherwise(), bb)).or_default().push(None);
  88                 }
  89             }
  90             switch_sources
  91         })
  92     }
  93
  94     /// Returns mutable reference to basic blocks. Invalidates CFG cache.
  95     #[inline]
  96     pub fn as_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
  97         self.invalidate_cfg_cache();
  98         &mut self.basic_blocks
  99     }
 100
 101     /// Get mutable access to basic blocks without invalidating the CFG cache.
 102     ///
 103     /// By calling this method instead of e.g. [`BasicBlocks::as_mut`] you promise not to change
 104     /// the CFG. This means that
 105     ///
 106     ///  1) The number of basic blocks remains unchanged
 107     ///  2) The set of successors of each terminator remains unchanged.
 108     ///  3) For each `TerminatorKind::SwitchInt`, the `targets` remains the same and the terminator
 109     ///     kind is not changed.
 110     ///
 111     /// If any of these conditions cannot be upheld, you should call [`BasicBlocks::invalidate_cfg_cache`].
 112     #[inline]
 113     pub fn as_mut_preserves_cfg(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 114         &mut self.basic_blocks
 115     }
 116
 117     /// Invalidates cached information about the CFG.
 118     ///
 119     /// You will only ever need this if you have also called [`BasicBlocks::as_mut_preserves_cfg`].
 120     /// All other methods that allow you to mutate the basic blocks also call this method
 121     /// themselves, thereby avoiding any risk of accidentally cache invalidation.
 122     pub fn invalidate_cfg_cache(&mut self) {
 123         self.cache = Cache::default();
 124     }
 125 }
 126
 127 impl<'tcx> std::ops::Deref for BasicBlocks<'tcx> {
 128     type Target = IndexVec<BasicBlock, BasicBlockData<'tcx>>;
 129
 130     #[inline]
 131     fn deref(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 132         &self.basic_blocks
 133     }
 134 }
 135
 136 impl<'tcx> graph::DirectedGraph for BasicBlocks<'tcx> {
 137     type Node = BasicBlock;
 138 }
 139
 140 impl<'tcx> graph::WithNumNodes for BasicBlocks<'tcx> {
 141     #[inline]
 142     fn num_nodes(&self) -> usize {
 143         self.basic_blocks.len()
 144     }
 145 }
 146
 147 impl<'tcx> graph::WithStartNode for BasicBlocks<'tcx> {
 148     #[inline]
 149     fn start_node(&self) -> Self::Node {
 150         START_BLOCK
 151     }
 152 }
 153
 154 impl<'tcx> graph::WithSuccessors for BasicBlocks<'tcx> {
 155     #[inline]
 156     fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter {
 157         self.basic_blocks[node].terminator().successors()
 158     }
 159 }
 160
 161 impl<'a, 'b> graph::GraphSuccessors<'b> for BasicBlocks<'a> {
 162     type Item = BasicBlock;
 163     type Iter = Successors<'b>;
 164 }
 165
 166 impl<'tcx, 'graph> graph::GraphPredecessors<'graph> for BasicBlocks<'tcx> {
 167     type Item = BasicBlock;
 168     type Iter = std::iter::Copied<std::slice::Iter<'graph, BasicBlock>>;
 169 }
 170
 171 impl<'tcx> graph::WithPredecessors for BasicBlocks<'tcx> {
 172     #[inline]
 173     fn predecessors(&self, node: Self::Node) -> <Self as graph::GraphPredecessors<'_>>::Iter {
 174         self.predecessors()[node].iter().copied()
 175     }
 176 }
 177
 178 TrivialTypeTraversalAndLiftImpls! {
 179     Cache,
 180 }
 181
 182 impl<S: Encoder> Encodable<S> for Cache {
 183     #[inline]
 184     fn encode(&self, _s: &mut S) {}
 185 }
 186
 187 impl<D: Decoder> Decodable<D> for Cache {
 188     #[inline]
 189     fn decode(_: &mut D) -> Self {
 190         Default::default()
 191     }
 192 }
 193
 194 impl<CTX> HashStable<CTX> for Cache {
 195     #[inline]
 196     fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {}
 197 }