rustc_middle/mir/
basic_blocks.rs

1use std::sync::{Arc, OnceLock};
2
3use rustc_data_structures::graph;
4use rustc_data_structures::graph::dominators::{Dominators, dominators};
5use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
6use rustc_index::{IndexSlice, IndexVec};
7use rustc_macros::{HashStable, TyDecodable, TyEncodable, TypeFoldable, TypeVisitable};
8use rustc_serialize::{Decodable, Decoder, Encodable, Encoder};
9use smallvec::SmallVec;
10
11use crate::mir::traversal::Postorder;
12use crate::mir::{BasicBlock, BasicBlockData, START_BLOCK};
13
14#[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable, TypeFoldable, TypeVisitable)]
15pub struct BasicBlocks<'tcx> {
16    basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>,
17    /// Use an `Arc` so we can share the cache when we clone the MIR body, as borrowck does.
18    cache: Arc<Cache>,
19}
20
21// Typically 95%+ of basic blocks have 4 or fewer predecessors.
22type Predecessors = IndexVec<BasicBlock, SmallVec<[BasicBlock; 4]>>;
23
24#[derive(Debug, Clone, Copy)]
25pub enum SwitchTargetValue {
26    // A normal switch value.
27    Normal(u128),
28    // The final "otherwise" fallback value.
29    Otherwise,
30}
31
32#[derive(Clone, Default, Debug)]
33struct Cache {
34    predecessors: OnceLock<Predecessors>,
35    reverse_postorder: OnceLock<Vec<BasicBlock>>,
36    dominators: OnceLock<Dominators<BasicBlock>>,
37}
38
39impl<'tcx> BasicBlocks<'tcx> {
40    #[inline]
41    pub fn new(basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>) -> Self {
42        BasicBlocks { basic_blocks, cache: Arc::new(Cache::default()) }
43    }
44
45    #[inline]
46    pub fn dominators(&self) -> &Dominators<BasicBlock> {
47        self.cache.dominators.get_or_init(|| dominators(self))
48    }
49
50    /// Returns predecessors for each basic block.
51    #[inline]
52    pub fn predecessors(&self) -> &Predecessors {
53        self.cache.predecessors.get_or_init(|| {
54            let mut preds = IndexVec::from_elem(SmallVec::new(), &self.basic_blocks);
55            for (bb, data) in self.basic_blocks.iter_enumerated() {
56                if let Some(term) = &data.terminator {
57                    for succ in term.successors() {
58                        preds[succ].push(bb);
59                    }
60                }
61            }
62            preds
63        })
64    }
65
66    /// Returns basic blocks in a reverse postorder.
67    ///
68    /// See [`traversal::reverse_postorder`]'s docs to learn what is preorder traversal.
69    ///
70    /// [`traversal::reverse_postorder`]: crate::mir::traversal::reverse_postorder
71    #[inline]
72    pub fn reverse_postorder(&self) -> &[BasicBlock] {
73        self.cache.reverse_postorder.get_or_init(|| {
74            let mut rpo: Vec<_> = Postorder::new(&self.basic_blocks, START_BLOCK, None).collect();
75            rpo.reverse();
76            rpo
77        })
78    }
79
80    /// Returns mutable reference to basic blocks. Invalidates CFG cache.
81    #[inline]
82    pub fn as_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
83        self.invalidate_cfg_cache();
84        &mut self.basic_blocks
85    }
86
87    /// Get mutable access to basic blocks without invalidating the CFG cache.
88    ///
89    /// By calling this method instead of e.g. [`BasicBlocks::as_mut`] you promise not to change
90    /// the CFG. This means that
91    ///
92    ///  1) The number of basic blocks remains unchanged
93    ///  2) The set of successors of each terminator remains unchanged.
94    ///  3) For each `TerminatorKind::SwitchInt`, the `targets` remains the same and the terminator
95    ///     kind is not changed.
96    ///
97    /// If any of these conditions cannot be upheld, you should call [`BasicBlocks::invalidate_cfg_cache`].
98    #[inline]
99    pub fn as_mut_preserves_cfg(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
100        &mut self.basic_blocks
101    }
102
103    /// Invalidates cached information about the CFG.
104    ///
105    /// You will only ever need this if you have also called [`BasicBlocks::as_mut_preserves_cfg`].
106    /// All other methods that allow you to mutate the basic blocks also call this method
107    /// themselves, thereby avoiding any risk of accidentally cache invalidation.
108    pub fn invalidate_cfg_cache(&mut self) {
109        if let Some(cache) = Arc::get_mut(&mut self.cache) {
110            // If we only have a single reference to this cache, clear it.
111            *cache = Cache::default();
112        } else {
113            // If we have several references to this cache, overwrite the pointer itself so other
114            // users can continue to use their (valid) cache.
115            self.cache = Arc::new(Cache::default());
116        }
117    }
118}
119
120impl<'tcx> std::ops::Deref for BasicBlocks<'tcx> {
121    type Target = IndexSlice<BasicBlock, BasicBlockData<'tcx>>;
122
123    #[inline]
124    fn deref(&self) -> &IndexSlice<BasicBlock, BasicBlockData<'tcx>> {
125        &self.basic_blocks
126    }
127}
128
129impl<'tcx> graph::DirectedGraph for BasicBlocks<'tcx> {
130    type Node = BasicBlock;
131
132    #[inline]
133    fn num_nodes(&self) -> usize {
134        self.basic_blocks.len()
135    }
136}
137
138impl<'tcx> graph::StartNode for BasicBlocks<'tcx> {
139    #[inline]
140    fn start_node(&self) -> Self::Node {
141        START_BLOCK
142    }
143}
144
145impl<'tcx> graph::Successors for BasicBlocks<'tcx> {
146    #[inline]
147    fn successors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
148        self.basic_blocks[node].terminator().successors()
149    }
150}
151
152impl<'tcx> graph::Predecessors for BasicBlocks<'tcx> {
153    #[inline]
154    fn predecessors(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> {
155        self.predecessors()[node].iter().copied()
156    }
157}
158
159// Done here instead of in `structural_impls.rs` because `Cache` is private, as is `basic_blocks`.
160TrivialTypeTraversalImpls! { Cache }
161
162impl<S: Encoder> Encodable<S> for Cache {
163    #[inline]
164    fn encode(&self, _s: &mut S) {}
165}
166
167impl<D: Decoder> Decodable<D> for Cache {
168    #[inline]
169    fn decode(_: &mut D) -> Self {
170        Default::default()
171    }
172}
173
174impl<CTX> HashStable<CTX> for Cache {
175    #[inline]
176    fn hash_stable(&self, _: &mut CTX, _: &mut StableHasher) {}
177}
rustc_middle/mir/basic_blocks.rs

rustc_middle/mir/
basic_blocks.rs
