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}
207

Provided by KDAB

Privacy Policy
Learn Rust with the experts
Find out more