rustc_middle/mir/
basic_blocks.rs

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

rustc_middle/mir/
basic_blocks.rs
