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};
7 use rustc_data_structures::graph;
8 use rustc_data_structures::graph::dominators::{dominators, Dominators};
9 use rustc_index::vec::IndexVec;
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,
20 impl<'tcx> BasicBlocks<'tcx> {
22 pub fn new(basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>) -> Self {
25 predecessor_cache: PredecessorCache::new(),
26 switch_source_cache: SwitchSourceCache::new(),
27 is_cyclic: GraphIsCyclicCache::new(),
28 postorder_cache: PostorderCache::new(),
32 /// Returns true if control-flow graph contains a cycle reachable from the `START_BLOCK`.
34 pub fn is_cfg_cyclic(&self) -> bool {
35 self.is_cyclic.is_cyclic(self)
39 pub fn dominators(&self) -> Dominators<BasicBlock> {
43 /// Returns predecessors for each basic block.
45 pub fn predecessors(&self) -> &Predecessors {
46 self.predecessor_cache.compute(&self.basic_blocks)
49 /// Returns basic blocks in a postorder.
51 pub fn postorder(&self) -> &[BasicBlock] {
52 self.postorder_cache.compute(&self.basic_blocks)
55 /// `switch_sources()[&(target, switch)]` returns a list of switch
56 /// values that lead to a `target` block from a `switch` block.
58 pub fn switch_sources(&self) -> &SwitchSources {
59 self.switch_source_cache.compute(&self.basic_blocks)
62 /// Returns mutable reference to basic blocks. Invalidates CFG cache.
64 pub fn as_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
65 self.invalidate_cfg_cache();
66 &mut self.basic_blocks
69 /// Get mutable access to basic blocks without invalidating the CFG cache.
71 /// By calling this method instead of e.g. [`BasicBlocks::as_mut`] you promise not to change
72 /// the CFG. This means that
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.
79 /// If any of these conditions cannot be upheld, you should call [`BasicBlocks::invalidate_cfg_cache`].
81 pub fn as_mut_preserves_cfg(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
82 &mut self.basic_blocks
85 /// Invalidates cached information about the CFG.
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();
98 impl<'tcx> std::ops::Deref for BasicBlocks<'tcx> {
99 type Target = IndexVec<BasicBlock, BasicBlockData<'tcx>>;
102 fn deref(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
107 impl<'tcx> graph::DirectedGraph for BasicBlocks<'tcx> {
108 type Node = BasicBlock;
111 impl<'tcx> graph::WithNumNodes for BasicBlocks<'tcx> {
113 fn num_nodes(&self) -> usize {
114 self.basic_blocks.len()
118 impl<'tcx> graph::WithStartNode for BasicBlocks<'tcx> {
120 fn start_node(&self) -> Self::Node {
125 impl<'tcx> graph::WithSuccessors for BasicBlocks<'tcx> {
127 fn successors(&self, node: Self::Node) -> <Self as graph::GraphSuccessors<'_>>::Iter {
128 self.basic_blocks[node].terminator().successors()
132 impl<'a, 'b> graph::GraphSuccessors<'b> for BasicBlocks<'a> {
133 type Item = BasicBlock;
134 type Iter = Successors<'b>;
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>>;
142 impl<'tcx> graph::WithPredecessors for BasicBlocks<'tcx> {
144 fn predecessors(&self, node: Self::Node) -> <Self as graph::GraphPredecessors<'_>>::Iter {
145 self.predecessors()[node].iter().copied()