]>
Commit | Line | Data |
---|---|---|
c30ab7b3 | 1 | //! A number of passes which remove various redundancies in the CFG. |
3157f602 | 2 | //! |
c30ab7b3 SL |
3 | //! The `SimplifyCfg` pass gets rid of unnecessary blocks in the CFG, whereas the `SimplifyLocals` |
4 | //! gets rid of all the unnecessary local variable declarations. | |
3157f602 | 5 | //! |
c30ab7b3 SL |
6 | //! The `SimplifyLocals` pass is kinda expensive and therefore not very suitable to be run often. |
7 | //! Most of the passes should not care or be impacted in meaningful ways due to extra locals | |
94b46f34 | 8 | //! either, so running the pass once, right before codegen, should suffice. |
c30ab7b3 SL |
9 | //! |
10 | //! On the other side of the spectrum, the `SimplifyCfg` pass is considerably cheap to run, thus | |
11 | //! one should run it after every pass which may modify CFG in significant ways. This pass must | |
12 | //! also be run before any analysis passes because it removes dead blocks, and some of these can be | |
13 | //! ill-typed. | |
14 | //! | |
15 | //! The cause of this typing issue is typeck allowing most blocks whose end is not reachable have | |
16 | //! an arbitrary return type, rather than having the usual () return type (as a note, typeck's | |
17 | //! notion of reachability is in fact slightly weaker than MIR CFG reachability - see #31617). A | |
18 | //! standard example of the situation is: | |
3157f602 | 19 | //! |
3157f602 XL |
20 | //! ```rust |
21 | //! fn example() { | |
22 | //! let _a: char = { return; }; | |
23 | //! } | |
24 | //! ``` | |
25 | //! | |
c30ab7b3 SL |
26 | //! Here the block (`{ return; }`) has the return type `char`, rather than `()`, but the MIR we |
27 | //! naively generate still contains the `_a = ()` write in the unreachable block "after" the | |
28 | //! return. | |
3157f602 | 29 | |
c295e0f8 | 30 | use crate::MirPass; |
064997fb | 31 | use rustc_data_structures::fx::FxHashSet; |
e74abb32 | 32 | use rustc_index::vec::{Idx, IndexVec}; |
17df50a5 | 33 | use rustc_middle::mir::coverage::*; |
ba9703b0 XL |
34 | use rustc_middle::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor}; |
35 | use rustc_middle::mir::*; | |
f9f354fc | 36 | use rustc_middle::ty::TyCtxt; |
3dfed10e | 37 | use smallvec::SmallVec; |
cdc7bbd5 XL |
38 | use std::borrow::Cow; |
39 | use std::convert::TryInto; | |
92a42be0 | 40 | |
dfeec247 XL |
41 | pub struct SimplifyCfg { |
42 | label: String, | |
43 | } | |
a7813a04 | 44 | |
7cac9316 XL |
45 | impl SimplifyCfg { |
46 | pub fn new(label: &str) -> Self { | |
47 | SimplifyCfg { label: format!("SimplifyCfg-{}", label) } | |
92a42be0 | 48 | } |
a7813a04 XL |
49 | } |
50 | ||
a2a8927a | 51 | pub fn simplify_cfg<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { |
dc9dc135 | 52 | CfgSimplifier::new(body).simplify(); |
17df50a5 | 53 | remove_dead_blocks(tcx, body); |
cc61c64b XL |
54 | |
55 | // FIXME: Should probably be moved into some kind of pass manager | |
dc9dc135 | 56 | body.basic_blocks_mut().raw.shrink_to_fit(); |
cc61c64b XL |
57 | } |
58 | ||
e1599b0c | 59 | impl<'tcx> MirPass<'tcx> for SimplifyCfg { |
416331ca | 60 | fn name(&self) -> Cow<'_, str> { |
7cac9316 | 61 | Cow::Borrowed(&self.label) |
3157f602 | 62 | } |
3157f602 | 63 | |
17df50a5 | 64 | fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { |
5869c6ff | 65 | debug!("SimplifyCfg({:?}) - simplifying {:?}", self.label, body.source); |
17df50a5 | 66 | simplify_cfg(tcx, body); |
a7813a04 | 67 | } |
3157f602 XL |
68 | } |
69 | ||
dc9dc135 | 70 | pub struct CfgSimplifier<'a, 'tcx> { |
3157f602 | 71 | basic_blocks: &'a mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, |
dfeec247 | 72 | pred_count: IndexVec<BasicBlock, u32>, |
a7813a04 XL |
73 | } |
74 | ||
dc9dc135 | 75 | impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> { |
f9f354fc | 76 | pub fn new(body: &'a mut Body<'tcx>) -> Self { |
f2b60f7d | 77 | let mut pred_count = IndexVec::from_elem(0u32, &body.basic_blocks); |
a7813a04 | 78 | |
3157f602 XL |
79 | // we can't use mir.predecessors() here because that counts |
80 | // dead blocks, which we don't want to. | |
c30ab7b3 SL |
81 | pred_count[START_BLOCK] = 1; |
82 | ||
dc9dc135 | 83 | for (_, data) in traversal::preorder(body) { |
3157f602 | 84 | if let Some(ref term) = data.terminator { |
923072b8 | 85 | for tgt in term.successors() { |
3157f602 XL |
86 | pred_count[tgt] += 1; |
87 | } | |
a7813a04 XL |
88 | } |
89 | } | |
3157f602 | 90 | |
dc9dc135 | 91 | let basic_blocks = body.basic_blocks_mut(); |
3157f602 | 92 | |
dfeec247 | 93 | CfgSimplifier { basic_blocks, pred_count } |
a7813a04 XL |
94 | } |
95 | ||
8bb4bdeb | 96 | pub fn simplify(mut self) { |
3b2f2976 XL |
97 | self.strip_nops(); |
98 | ||
ba9703b0 XL |
99 | // Vec of the blocks that should be merged. We store the indices here, instead of the |
100 | // statements itself to avoid moving the (relatively) large statements twice. | |
101 | // We do not push the statements directly into the target block (`bb`) as that is slower | |
102 | // due to additional reallocations | |
103 | let mut merged_blocks = Vec::new(); | |
3157f602 XL |
104 | loop { |
105 | let mut changed = false; | |
106 | ||
0731742a | 107 | for bb in self.basic_blocks.indices() { |
3157f602 | 108 | if self.pred_count[bb] == 0 { |
dfeec247 | 109 | continue; |
a7813a04 XL |
110 | } |
111 | ||
3157f602 XL |
112 | debug!("simplifying {:?}", bb); |
113 | ||
dfeec247 XL |
114 | let mut terminator = |
115 | self.basic_blocks[bb].terminator.take().expect("invalid terminator state"); | |
3157f602 XL |
116 | |
117 | for successor in terminator.successors_mut() { | |
118 | self.collapse_goto_chain(successor, &mut changed); | |
a7813a04 XL |
119 | } |
120 | ||
3157f602 | 121 | let mut inner_changed = true; |
ba9703b0 | 122 | merged_blocks.clear(); |
3157f602 XL |
123 | while inner_changed { |
124 | inner_changed = false; | |
125 | inner_changed |= self.simplify_branch(&mut terminator); | |
ba9703b0 | 126 | inner_changed |= self.merge_successor(&mut merged_blocks, &mut terminator); |
3157f602 | 127 | changed |= inner_changed; |
92a42be0 | 128 | } |
92a42be0 | 129 | |
ba9703b0 XL |
130 | let statements_to_merge = |
131 | merged_blocks.iter().map(|&i| self.basic_blocks[i].statements.len()).sum(); | |
132 | ||
133 | if statements_to_merge > 0 { | |
134 | let mut statements = std::mem::take(&mut self.basic_blocks[bb].statements); | |
135 | statements.reserve(statements_to_merge); | |
136 | for &from in &merged_blocks { | |
137 | statements.append(&mut self.basic_blocks[from].statements); | |
138 | } | |
139 | self.basic_blocks[bb].statements = statements; | |
140 | } | |
141 | ||
142 | self.basic_blocks[bb].terminator = Some(terminator); | |
a7813a04 | 143 | } |
92a42be0 | 144 | |
dfeec247 XL |
145 | if !changed { |
146 | break; | |
147 | } | |
a7813a04 XL |
148 | } |
149 | } | |
a7813a04 | 150 | |
3dfed10e XL |
151 | /// This function will return `None` if |
152 | /// * the block has statements | |
153 | /// * the block has a terminator other than `goto` | |
154 | /// * the block has no terminator (meaning some other part of the current optimization stole it) | |
155 | fn take_terminator_if_simple_goto(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> { | |
156 | match self.basic_blocks[bb] { | |
3157f602 XL |
157 | BasicBlockData { |
158 | ref statements, | |
dfeec247 XL |
159 | terminator: |
160 | ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }), | |
161 | .. | |
3157f602 XL |
162 | } if statements.is_empty() => terminator.take(), |
163 | // if `terminator` is None, this means we are in a loop. In that | |
164 | // case, let all the loop collapse to its entry. | |
3dfed10e XL |
165 | _ => None, |
166 | } | |
167 | } | |
3157f602 | 168 | |
3dfed10e XL |
169 | /// Collapse a goto chain starting from `start` |
170 | fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) { | |
171 | // Using `SmallVec` here, because in some logs on libcore oli-obk saw many single-element | |
172 | // goto chains. We should probably benchmark different sizes. | |
173 | let mut terminators: SmallVec<[_; 1]> = Default::default(); | |
174 | let mut current = *start; | |
175 | while let Some(terminator) = self.take_terminator_if_simple_goto(current) { | |
5e7ed085 FG |
176 | let Terminator { kind: TerminatorKind::Goto { target }, .. } = terminator else { |
177 | unreachable!(); | |
3dfed10e XL |
178 | }; |
179 | terminators.push((current, terminator)); | |
180 | current = target; | |
181 | } | |
182 | let last = current; | |
183 | *start = last; | |
184 | while let Some((current, mut terminator)) = terminators.pop() { | |
5e7ed085 FG |
185 | let Terminator { kind: TerminatorKind::Goto { ref mut target }, .. } = terminator else { |
186 | unreachable!(); | |
3dfed10e XL |
187 | }; |
188 | *changed |= *target != last; | |
189 | *target = last; | |
190 | debug!("collapsing goto chain from {:?} to {:?}", current, target); | |
191 | ||
192 | if self.pred_count[current] == 1 { | |
193 | // This is the last reference to current, so the pred-count to | |
194 | // to target is moved into the current block. | |
195 | self.pred_count[current] = 0; | |
196 | } else { | |
197 | self.pred_count[*target] += 1; | |
198 | self.pred_count[current] -= 1; | |
92a42be0 | 199 | } |
3dfed10e | 200 | self.basic_blocks[current].terminator = Some(terminator); |
c30ab7b3 | 201 | } |
3157f602 | 202 | } |
7453a54e | 203 | |
3157f602 | 204 | // merge a block with 1 `goto` predecessor to its parent |
dfeec247 XL |
205 | fn merge_successor( |
206 | &mut self, | |
ba9703b0 | 207 | merged_blocks: &mut Vec<BasicBlock>, |
dfeec247 XL |
208 | terminator: &mut Terminator<'tcx>, |
209 | ) -> bool { | |
3157f602 | 210 | let target = match terminator.kind { |
dfeec247 XL |
211 | TerminatorKind::Goto { target } if self.pred_count[target] == 1 => target, |
212 | _ => return false, | |
3157f602 XL |
213 | }; |
214 | ||
215 | debug!("merging block {:?} into {:?}", target, terminator); | |
216 | *terminator = match self.basic_blocks[target].terminator.take() { | |
217 | Some(terminator) => terminator, | |
218 | None => { | |
219 | // unreachable loop - this should not be possible, as we | |
220 | // don't strand blocks, but handle it correctly. | |
dfeec247 | 221 | return false; |
3157f602 XL |
222 | } |
223 | }; | |
ba9703b0 XL |
224 | |
225 | merged_blocks.push(target); | |
3157f602 | 226 | self.pred_count[target] = 0; |
7453a54e | 227 | |
3157f602 XL |
228 | true |
229 | } | |
230 | ||
231 | // turn a branch with all successors identical to a goto | |
232 | fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool { | |
233 | match terminator.kind { | |
dfeec247 XL |
234 | TerminatorKind::SwitchInt { .. } => {} |
235 | _ => return false, | |
3157f602 XL |
236 | }; |
237 | ||
238 | let first_succ = { | |
923072b8 FG |
239 | if let Some(first_succ) = terminator.successors().next() { |
240 | if terminator.successors().all(|s| s == first_succ) { | |
83c7162d XL |
241 | let count = terminator.successors().count(); |
242 | self.pred_count[first_succ] -= (count - 1) as u32; | |
3157f602 XL |
243 | first_succ |
244 | } else { | |
dfeec247 | 245 | return false; |
92a42be0 | 246 | } |
3157f602 | 247 | } else { |
dfeec247 | 248 | return false; |
92a42be0 | 249 | } |
3157f602 XL |
250 | }; |
251 | ||
252 | debug!("simplifying branch {:?}", terminator); | |
253 | terminator.kind = TerminatorKind::Goto { target: first_succ }; | |
254 | true | |
255 | } | |
8bb4bdeb XL |
256 | |
257 | fn strip_nops(&mut self) { | |
258 | for blk in self.basic_blocks.iter_mut() { | |
1b1a35ee | 259 | blk.statements.retain(|stmt| !matches!(stmt.kind, StatementKind::Nop)) |
8bb4bdeb XL |
260 | } |
261 | } | |
3157f602 XL |
262 | } |
263 | ||
a2a8927a | 264 | pub fn remove_dead_blocks<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { |
5869c6ff | 265 | let reachable = traversal::reachable_as_bitset(body); |
f2b60f7d | 266 | let num_blocks = body.basic_blocks.len(); |
5869c6ff XL |
267 | if num_blocks == reachable.count() { |
268 | return; | |
3157f602 XL |
269 | } |
270 | ||
064997fb FG |
271 | let basic_blocks = body.basic_blocks.as_mut(); |
272 | let source_scopes = &body.source_scopes; | |
dfeec247 | 273 | let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect(); |
3157f602 | 274 | let mut used_blocks = 0; |
5869c6ff XL |
275 | for alive_index in reachable.iter() { |
276 | let alive_index = alive_index.index(); | |
3157f602 XL |
277 | replacements[alive_index] = BasicBlock::new(used_blocks); |
278 | if alive_index != used_blocks { | |
60c5eb7d XL |
279 | // Swap the next alive block data with the current available slot. Since |
280 | // alive_index is non-decreasing this is a valid operation. | |
3157f602 | 281 | basic_blocks.raw.swap(alive_index, used_blocks); |
92a42be0 | 282 | } |
3157f602 XL |
283 | used_blocks += 1; |
284 | } | |
17df50a5 XL |
285 | |
286 | if tcx.sess.instrument_coverage() { | |
064997fb | 287 | save_unreachable_coverage(basic_blocks, source_scopes, used_blocks); |
17df50a5 XL |
288 | } |
289 | ||
3157f602 | 290 | basic_blocks.raw.truncate(used_blocks); |
92a42be0 | 291 | |
3157f602 XL |
292 | for block in basic_blocks { |
293 | for target in block.terminator_mut().successors_mut() { | |
294 | *target = replacements[target.index()]; | |
92a42be0 | 295 | } |
92a42be0 SL |
296 | } |
297 | } | |
c30ab7b3 | 298 | |
17df50a5 XL |
299 | /// Some MIR transforms can determine at compile time that a sequences of |
300 | /// statements will never be executed, so they can be dropped from the MIR. | |
301 | /// For example, an `if` or `else` block that is guaranteed to never be executed | |
302 | /// because its condition can be evaluated at compile time, such as by const | |
303 | /// evaluation: `if false { ... }`. | |
304 | /// | |
305 | /// Those statements are bypassed by redirecting paths in the CFG around the | |
5099ac24 | 306 | /// `dead blocks`; but with `-C instrument-coverage`, the dead blocks usually |
17df50a5 XL |
307 | /// include `Coverage` statements representing the Rust source code regions to |
308 | /// be counted at runtime. Without these `Coverage` statements, the regions are | |
309 | /// lost, and the Rust source code will show no coverage information. | |
310 | /// | |
311 | /// What we want to show in a coverage report is the dead code with coverage | |
312 | /// counts of `0`. To do this, we need to save the code regions, by injecting | |
313 | /// `Unreachable` coverage statements. These are non-executable statements whose | |
314 | /// code regions are still recorded in the coverage map, representing regions | |
315 | /// with `0` executions. | |
064997fb FG |
316 | /// |
317 | /// If there are no live `Counter` `Coverage` statements remaining, we remove | |
318 | /// `Coverage` statements along with the dead blocks. Since at least one | |
319 | /// counter per function is required by LLVM (and necessary, to add the | |
320 | /// `function_hash` to the counter's call to the LLVM intrinsic | |
321 | /// `instrprof.increment()`). | |
322 | /// | |
323 | /// The `generator::StateTransform` MIR pass and MIR inlining can create | |
324 | /// atypical conditions, where all live `Counter`s are dropped from the MIR. | |
325 | /// | |
326 | /// With MIR inlining we can have coverage counters belonging to different | |
327 | /// instances in a single body, so the strategy described above is applied to | |
328 | /// coverage counters from each instance individually. | |
17df50a5 XL |
329 | fn save_unreachable_coverage( |
330 | basic_blocks: &mut IndexVec<BasicBlock, BasicBlockData<'_>>, | |
064997fb | 331 | source_scopes: &IndexVec<SourceScope, SourceScopeData<'_>>, |
17df50a5 XL |
332 | first_dead_block: usize, |
333 | ) { | |
064997fb FG |
334 | // Identify instances that still have some live coverage counters left. |
335 | let mut live = FxHashSet::default(); | |
336 | for basic_block in &basic_blocks.raw[0..first_dead_block] { | |
337 | for statement in &basic_block.statements { | |
338 | let StatementKind::Coverage(coverage) = &statement.kind else { continue }; | |
339 | let CoverageKind::Counter { .. } = coverage.kind else { continue }; | |
340 | let instance = statement.source_info.scope.inlined_instance(source_scopes); | |
341 | live.insert(instance); | |
342 | } | |
343 | } | |
344 | ||
345 | for block in &mut basic_blocks.raw[..first_dead_block] { | |
346 | for statement in &mut block.statements { | |
347 | let StatementKind::Coverage(_) = &statement.kind else { continue }; | |
348 | let instance = statement.source_info.scope.inlined_instance(source_scopes); | |
349 | if !live.contains(&instance) { | |
350 | statement.make_nop(); | |
17df50a5 | 351 | } |
064997fb FG |
352 | } |
353 | } | |
354 | ||
355 | if live.is_empty() { | |
17df50a5 XL |
356 | return; |
357 | } | |
358 | ||
064997fb FG |
359 | // Retain coverage for instances that still have some live counters left. |
360 | let mut retained_coverage = Vec::new(); | |
361 | for dead_block in &basic_blocks.raw[first_dead_block..] { | |
362 | for statement in &dead_block.statements { | |
363 | let StatementKind::Coverage(coverage) = &statement.kind else { continue }; | |
364 | let Some(code_region) = &coverage.code_region else { continue }; | |
365 | let instance = statement.source_info.scope.inlined_instance(source_scopes); | |
366 | if live.contains(&instance) { | |
367 | retained_coverage.push((statement.source_info, code_region.clone())); | |
17df50a5 XL |
368 | } |
369 | } | |
370 | } | |
371 | ||
372 | let start_block = &mut basic_blocks[START_BLOCK]; | |
064997fb FG |
373 | start_block.statements.extend(retained_coverage.into_iter().map( |
374 | |(source_info, code_region)| Statement { | |
17df50a5 | 375 | source_info, |
94222f64 | 376 | kind: StatementKind::Coverage(Box::new(Coverage { |
17df50a5 XL |
377 | kind: CoverageKind::Unreachable, |
378 | code_region: Some(code_region), | |
94222f64 | 379 | })), |
064997fb FG |
380 | }, |
381 | )); | |
17df50a5 XL |
382 | } |
383 | ||
c30ab7b3 SL |
384 | pub struct SimplifyLocals; |
385 | ||
e1599b0c | 386 | impl<'tcx> MirPass<'tcx> for SimplifyLocals { |
a2a8927a XL |
387 | fn is_enabled(&self, sess: &rustc_session::Session) -> bool { |
388 | sess.mir_opt_level() > 0 | |
389 | } | |
390 | ||
29967ef6 XL |
391 | fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) { |
392 | trace!("running SimplifyLocals on {:?}", body.source); | |
6a06907d XL |
393 | simplify_locals(body, tcx); |
394 | } | |
395 | } | |
ba9703b0 | 396 | |
6a06907d XL |
397 | pub fn simplify_locals<'tcx>(body: &mut Body<'tcx>, tcx: TyCtxt<'tcx>) { |
398 | // First, we're going to get a count of *actual* uses for every `Local`. | |
cdc7bbd5 | 399 | let mut used_locals = UsedLocals::new(body); |
ba9703b0 | 400 | |
6a06907d XL |
401 | // Next, we're going to remove any `Local` with zero actual uses. When we remove those |
402 | // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals` | |
403 | // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from | |
404 | // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a | |
405 | // fixedpoint where there are no more unused locals. | |
406 | remove_unused_definitions(&mut used_locals, body); | |
ba9703b0 | 407 | |
6a06907d | 408 | // Finally, we'll actually do the work of shrinking `body.local_decls` and remapping the `Local`s. |
cdc7bbd5 | 409 | let map = make_local_map(&mut body.local_decls, &used_locals); |
ba9703b0 | 410 | |
6a06907d XL |
411 | // Only bother running the `LocalUpdater` if we actually found locals to remove. |
412 | if map.iter().any(Option::is_none) { | |
413 | // Update references to all vars and tmps now | |
414 | let mut updater = LocalUpdater { map, tcx }; | |
f2b60f7d | 415 | updater.visit_body_preserves_cfg(body); |
ba9703b0 | 416 | |
6a06907d | 417 | body.local_decls.shrink_to_fit(); |
c30ab7b3 SL |
418 | } |
419 | } | |
420 | ||
421 | /// Construct the mapping while swapping out unused stuff out from the `vec`. | |
cdc7bbd5 | 422 | fn make_local_map<V>( |
ba9703b0 | 423 | local_decls: &mut IndexVec<Local, V>, |
cdc7bbd5 | 424 | used_locals: &UsedLocals, |
8faf50e0 | 425 | ) -> IndexVec<Local, Option<Local>> { |
cdc7bbd5 | 426 | let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, &*local_decls); |
8faf50e0 | 427 | let mut used = Local::new(0); |
29967ef6 XL |
428 | |
429 | for alive_index in local_decls.indices() { | |
cdc7bbd5 XL |
430 | // `is_used` treats the `RETURN_PLACE` and arguments as used. |
431 | if !used_locals.is_used(alive_index) { | |
432 | continue; | |
433 | } | |
434 | ||
435 | map[alive_index] = Some(used); | |
436 | if alive_index != used { | |
437 | local_decls.swap(alive_index, used); | |
c30ab7b3 | 438 | } |
cdc7bbd5 | 439 | used.increment_by(1); |
c30ab7b3 | 440 | } |
ba9703b0 | 441 | local_decls.truncate(used.index()); |
c30ab7b3 SL |
442 | map |
443 | } | |
444 | ||
29967ef6 | 445 | /// Keeps track of used & unused locals. |
cdc7bbd5 | 446 | struct UsedLocals { |
29967ef6 | 447 | increment: bool, |
cdc7bbd5 | 448 | arg_count: u32, |
29967ef6 | 449 | use_count: IndexVec<Local, u32>, |
c30ab7b3 SL |
450 | } |
451 | ||
cdc7bbd5 | 452 | impl UsedLocals { |
29967ef6 | 453 | /// Determines which locals are used & unused in the given body. |
cdc7bbd5 | 454 | fn new(body: &Body<'_>) -> Self { |
29967ef6 XL |
455 | let mut this = Self { |
456 | increment: true, | |
cdc7bbd5 | 457 | arg_count: body.arg_count.try_into().unwrap(), |
29967ef6 XL |
458 | use_count: IndexVec::from_elem(0, &body.local_decls), |
459 | }; | |
460 | this.visit_body(body); | |
461 | this | |
ba9703b0 | 462 | } |
ba9703b0 | 463 | |
29967ef6 | 464 | /// Checks if local is used. |
cdc7bbd5 XL |
465 | /// |
466 | /// Return place and arguments are always considered used. | |
29967ef6 XL |
467 | fn is_used(&self, local: Local) -> bool { |
468 | trace!("is_used({:?}): use_count: {:?}", local, self.use_count[local]); | |
cdc7bbd5 | 469 | local.as_u32() <= self.arg_count || self.use_count[local] != 0 |
29967ef6 | 470 | } |
e74abb32 | 471 | |
29967ef6 | 472 | /// Updates the use counts to reflect the removal of given statement. |
a2a8927a | 473 | fn statement_removed(&mut self, statement: &Statement<'_>) { |
29967ef6 | 474 | self.increment = false; |
e74abb32 | 475 | |
29967ef6 XL |
476 | // The location of the statement is irrelevant. |
477 | let location = Location { block: START_BLOCK, statement_index: 0 }; | |
478 | self.visit_statement(statement, location); | |
c30ab7b3 | 479 | } |
ba9703b0 | 480 | |
29967ef6 | 481 | /// Visits a left-hand side of an assignment. |
a2a8927a | 482 | fn visit_lhs(&mut self, place: &Place<'_>, location: Location) { |
29967ef6 XL |
483 | if place.is_indirect() { |
484 | // A use, not a definition. | |
485 | self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), location); | |
486 | } else { | |
cdc7bbd5 XL |
487 | // A definition. The base local itself is not visited, so this occurrence is not counted |
488 | // toward its use count. There might be other locals still, used in an indexing | |
489 | // projection. | |
29967ef6 | 490 | self.super_projection( |
6a06907d | 491 | place.as_ref(), |
29967ef6 XL |
492 | PlaceContext::MutatingUse(MutatingUseContext::Projection), |
493 | location, | |
494 | ); | |
495 | } | |
ba9703b0 XL |
496 | } |
497 | } | |
498 | ||
a2a8927a | 499 | impl<'tcx> Visitor<'tcx> for UsedLocals { |
29967ef6 XL |
500 | fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) { |
501 | match statement.kind { | |
f2b60f7d | 502 | StatementKind::Intrinsic(..) |
29967ef6 XL |
503 | | StatementKind::Retag(..) |
504 | | StatementKind::Coverage(..) | |
505 | | StatementKind::FakeRead(..) | |
506 | | StatementKind::AscribeUserType(..) => { | |
507 | self.super_statement(statement, location); | |
ba9703b0 | 508 | } |
ba9703b0 | 509 | |
29967ef6 | 510 | StatementKind::Nop => {} |
ba9703b0 | 511 | |
29967ef6 | 512 | StatementKind::StorageLive(_local) | StatementKind::StorageDead(_local) => {} |
c30ab7b3 | 513 | |
29967ef6 | 514 | StatementKind::Assign(box (ref place, ref rvalue)) => { |
923072b8 FG |
515 | if rvalue.is_safe_to_remove() { |
516 | self.visit_lhs(place, location); | |
517 | self.visit_rvalue(rvalue, location); | |
518 | } else { | |
519 | self.super_statement(statement, location); | |
520 | } | |
29967ef6 | 521 | } |
ba9703b0 | 522 | |
04454e1e FG |
523 | StatementKind::SetDiscriminant { ref place, variant_index: _ } |
524 | | StatementKind::Deinit(ref place) => { | |
29967ef6 XL |
525 | self.visit_lhs(place, location); |
526 | } | |
527 | } | |
ba9703b0 | 528 | } |
ba9703b0 | 529 | |
064997fb | 530 | fn visit_local(&mut self, local: Local, _ctx: PlaceContext, _location: Location) { |
29967ef6 | 531 | if self.increment { |
064997fb | 532 | self.use_count[local] += 1; |
29967ef6 | 533 | } else { |
064997fb FG |
534 | assert_ne!(self.use_count[local], 0); |
535 | self.use_count[local] -= 1; | |
29967ef6 | 536 | } |
e74abb32 | 537 | } |
29967ef6 | 538 | } |
e74abb32 | 539 | |
29967ef6 | 540 | /// Removes unused definitions. Updates the used locals to reflect the changes made. |
a2a8927a | 541 | fn remove_unused_definitions(used_locals: &mut UsedLocals, body: &mut Body<'_>) { |
29967ef6 XL |
542 | // The use counts are updated as we remove the statements. A local might become unused |
543 | // during the retain operation, leading to a temporary inconsistency (storage statements or | |
544 | // definitions referencing the local might remain). For correctness it is crucial that this | |
545 | // computation reaches a fixed point. | |
546 | ||
547 | let mut modified = true; | |
548 | while modified { | |
549 | modified = false; | |
550 | ||
f2b60f7d | 551 | for data in body.basic_blocks.as_mut_preserves_cfg() { |
29967ef6 XL |
552 | // Remove unnecessary StorageLive and StorageDead annotations. |
553 | data.statements.retain(|statement| { | |
554 | let keep = match &statement.kind { | |
555 | StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => { | |
556 | used_locals.is_used(*local) | |
557 | } | |
558 | StatementKind::Assign(box (place, _)) => used_locals.is_used(place.local), | |
ba9703b0 | 559 | |
04454e1e FG |
560 | StatementKind::SetDiscriminant { ref place, .. } |
561 | | StatementKind::Deinit(ref place) => used_locals.is_used(place.local), | |
29967ef6 XL |
562 | _ => true, |
563 | }; | |
ba9703b0 | 564 | |
29967ef6 XL |
565 | if !keep { |
566 | trace!("removing statement {:?}", statement); | |
567 | modified = true; | |
568 | used_locals.statement_removed(statement); | |
569 | } | |
ba9703b0 | 570 | |
29967ef6 XL |
571 | keep |
572 | }); | |
573 | } | |
c30ab7b3 | 574 | } |
ba9703b0 | 575 | } |
e74abb32 | 576 | |
ba9703b0 XL |
577 | struct LocalUpdater<'tcx> { |
578 | map: IndexVec<Local, Option<Local>>, | |
579 | tcx: TyCtxt<'tcx>, | |
580 | } | |
581 | ||
582 | impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> { | |
583 | fn tcx(&self) -> TyCtxt<'tcx> { | |
584 | self.tcx | |
c30ab7b3 | 585 | } |
e74abb32 | 586 | |
ba9703b0 XL |
587 | fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) { |
588 | *l = self.map[*l].unwrap(); | |
e74abb32 | 589 | } |
c30ab7b3 | 590 | } |