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