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