compiler/rustc_middle/src/mir/basic_blocks.rs

   1 use crate::mir::graph_cyclic_cache::GraphIsCyclicCache;
   2 use crate::mir::predecessors::{PredecessorCache, Predecessors};
   3 use crate::mir::switch_sources::{SwitchSourceCache, SwitchSources};
   4 use crate::mir::traversal::PostorderCache;
   5 use crate::mir::{BasicBlock, BasicBlockData, Successors, START_BLOCK};
   6
   7 use rustc_data_structures::graph;
   8 use rustc_data_structures::graph::dominators::{dominators, Dominators};
   9 use rustc_index::vec::IndexVec;
  10
  11 #[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable, TypeFoldable, TypeVisitable)]
  12 pub struct BasicBlocks<'tcx> {
  13     basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>,
  14     predecessor_cache: PredecessorCache,
  15     switch_source_cache: SwitchSourceCache,
  16     is_cyclic: GraphIsCyclicCache,
  17     postorder_cache: PostorderCache,
  18 }
  19
  20 impl<'tcx> BasicBlocks<'tcx> {
  21     #[inline]
  22     pub fn new(basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>) -> Self {
  23         BasicBlocks {
  24             basic_blocks,
  25             predecessor_cache: PredecessorCache::new(),
  26             switch_source_cache: SwitchSourceCache::new(),
  27             is_cyclic: GraphIsCyclicCache::new(),
  28             postorder_cache: PostorderCache::new(),
  29         }
  30     }
  31
  32     /// Returns true if control-flow graph contains a cycle reachable from the `START_BLOCK`.
  33     #[inline]
  34     pub fn is_cfg_cyclic(&self) -> bool {
  35         self.is_cyclic.is_cyclic(self)
  36     }
  37
  38     #[inline]
  39     pub fn dominators(&self) -> Dominators<BasicBlock> {
  40         dominators(&self)
  41     }
  42
  43     /// Returns predecessors for each basic block.
  44     #[inline]
  45     pub fn predecessors(&self) -> &Predecessors {
  46         self.predecessor_cache.compute(&self.basic_blocks)
  47     }
  48
  49     /// Returns basic blocks in a postorder.
  50     #[inline]
  51     pub fn postorder(&self) -> &[BasicBlock] {
  52         self.postorder_cache.compute(&self.basic_blocks)
  53     }
  54
  55     /// `switch_sources()[&(target, switch)]` returns a list of switch
  56     /// values that lead to a `target` block from a `switch` block.
  57     #[inline]
  58     pub fn switch_sources(&self) -> &SwitchSources {
  59         self.switch_source_cache.compute(&self.basic_blocks)
  60     }
  61
  62     /// Returns mutable reference to basic blocks. Invalidates CFG cache.
  63     #[inline]
  64     pub fn as_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
  65         self.invalidate_cfg_cache();
  66         &mut self.basic_blocks
  67     }
  68
  69     /// Get mutable access to basic blocks without invalidating the CFG cache.
  70     ///
  71     /// By calling this method instead of e.g. [`BasicBlocks::as_mut`] you promise not to change
  72     /// the CFG. This means that
  73     ///
  74     ///  1) The number of basic blocks remains unchanged
  75     ///  2) The set of successors of each terminator remains unchanged.
  76     ///  3) For each `TerminatorKind::SwitchInt`, the `targets` remains the same and the terminator
  77     ///     kind is not changed.
  78     ///
  79     /// If any of these conditions cannot be upheld, you should call [`BasicBlocks::invalidate_cfg_cache`].
  80     #[inline]
  81     pub fn as_mut_preserves_cfg(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
  82         &mut self.basic_blocks
  83     }
  84
  85     /// Invalidates cached information about the CFG.
  86     ///
  87     /// You will only ever need this if you have also called [`BasicBlocks::as_mut_preserves_cfg`].
  88     /// All other methods that allow you to mutate the basic blocks also call this method
  89     /// themselves, thereby avoiding any risk of accidentally cache invalidation.
  90     pub fn invalidate_cfg_cache(&mut self) {
  91         self.predecessor_cache.invalidate();
  92         self.switch_source_cache.invalidate();
  93         self.is_cyclic.invalidate();
  94         self.postorder_cache.invalidate();
  95     }
  96 }
  97
  98 impl<'tcx> std::ops::Deref for BasicBlocks<'tcx> {
  99     type Target = IndexVec<BasicBlock, BasicBlockData<'tcx>>;
 100
 101     #[inline]
 102     fn deref(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 103         &self.basic_blocks
 104     }
 105 }
 106
 107 impl<'tcx> graph::DirectedGraph for BasicBlocks<'tcx> {
 108     type Node = BasicBlock;
 109 }
 110
 111 impl<'tcx> graph::WithNumNodes for BasicBlocks<'tcx> {
 112     #[inline]
 113     fn num_nodes(&self) -> usize {
 114         self.basic_blocks.len()
 115     }
 116 }
 117
 118 impl<'tcx> graph::WithStartNode for BasicBlocks<'tcx> {
 119     #[inline]
 120     fn start_node(&self) -> Self::Node {
 121         START_BLOCK
 122     }
 123 }
 124
 125 impl<'tcx> graph::WithSuccessors for BasicBlocks<'tcx> {
 126     #[inline]
 127     fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter {
 128         self.basic_blocks[node].terminator().successors()
 129     }
 130 }
 131
 132 impl<'a, 'b> graph::GraphSuccessors<'b> for BasicBlocks<'a> {
 133     type Item = BasicBlock;
 134     type Iter = Successors<'b>;
 135 }
 136
 137 impl<'tcx, 'graph> graph::GraphPredecessors<'graph> for BasicBlocks<'tcx> {
 138     type Item = BasicBlock;
 139     type Iter = std::iter::Copied<std::slice::Iter<'graph, BasicBlock>>;
 140 }
 141
 142 impl<'tcx> graph::WithPredecessors for BasicBlocks<'tcx> {
 143     #[inline]
 144     fn predecessors(&self, node: Self::Node) -> <Self as graph::GraphPredecessors<'_>>::Iter {
 145         self.predecessors()[node].iter().copied()
 146     }
 147 }