Skip to main content

rustc_mir_transform/
simplify.rs

1//! A number of passes which remove various redundancies in the CFG.
2//!
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.
5//!
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
8//! either, so running the pass once, right before codegen, should suffice.
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:
19//!
20//! ```rust
21//!   fn example() {
22//!       let _a: char = { return; };
23//!   }
24//! ```
25//!
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.
29//!
30//! **WARNING**: This is one of the few optimizations that runs on built and analysis MIR, and
31//! so its effects may affect the type-checking, borrow-checking, and other analysis of MIR.
32//! We must be extremely careful to only apply optimizations that preserve UB and all
33//! non-determinism, since changes here can affect which programs compile in an insta-stable way.
34//! The normal logic that a program with UB can be changed to do anything does not apply to
35//! pre-"runtime" MIR!
36
37use itertools::Itertools as _;
38use rustc_data_structures::thin_vec::ThinVec;
39use rustc_index::bit_set::DenseBitSet;
40use rustc_index::{Idx, IndexSlice, IndexVec};
41use rustc_middle::mir::visit::{MutVisitor, MutatingUseContext, PlaceContext, Visitor};
42use rustc_middle::mir::*;
43use rustc_middle::ty::TyCtxt;
44use rustc_mir_dataflow::debuginfo::debuginfo_locals;
45use rustc_span::DUMMY_SP;
46use smallvec::SmallVec;
47use tracing::{debug, trace};
48
49use crate::PassPolicy;
50
51pub(super) enum SimplifyCfg {
52    Initial,
53    PromoteConsts,
54    RemoveFalseEdges,
55    /// Runs at the beginning of "analysis to runtime" lowering, *before* drop elaboration.
56    PostAnalysis,
57    /// Runs at the end of "analysis to runtime" lowering, *after* drop elaboration.
58    /// This is before the main optimization passes on runtime MIR kick in.
59    PreOptimizations,
60    Final,
61    MakeShim,
62    AfterUnreachableEnumBranching,
63}
64
65impl SimplifyCfg {
66    fn name(&self) -> &'static str {
67        match self {
68            SimplifyCfg::Initial => "SimplifyCfg-initial",
69            SimplifyCfg::PromoteConsts => "SimplifyCfg-promote-consts",
70            SimplifyCfg::RemoveFalseEdges => "SimplifyCfg-remove-false-edges",
71            SimplifyCfg::PostAnalysis => "SimplifyCfg-post-analysis",
72            SimplifyCfg::PreOptimizations => "SimplifyCfg-pre-optimizations",
73            SimplifyCfg::Final => "SimplifyCfg-final",
74            SimplifyCfg::MakeShim => "SimplifyCfg-make_shim",
75            SimplifyCfg::AfterUnreachableEnumBranching => {
76                "SimplifyCfg-after-unreachable-enum-branching"
77            }
78        }
79    }
80}
81
82pub(super) fn simplify_cfg<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
83    if CfgSimplifier::new(tcx, body).simplify() {
84        // `simplify` returns that it changed something. We must invalidate the CFG caches as they
85        // are not consistent with the modified CFG any more.
86        body.basic_blocks.invalidate_cfg_cache();
87    }
88    remove_dead_blocks(body);
89
90    // FIXME: Should probably be moved into some kind of pass manager
91    body.basic_blocks.as_mut_preserves_cfg().shrink_to_fit();
92}
93
94impl<'tcx> crate::MirPass<'tcx> for SimplifyCfg {
95    fn name(&self) -> &'static str {
96        self.name()
97    }
98
99    fn policy(&self, _ctx: &crate::PassCtx<'_>) -> PassPolicy {
100        PassPolicy::optional(true)
101    }
102
103    fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
104        debug!("SimplifyCfg({:?}) - simplifying {:?}", self.name(), body.source);
105        simplify_cfg(tcx, body);
106    }
107}
108
109struct CfgSimplifier<'a, 'tcx> {
110    preserve_switch_reads: bool,
111    basic_blocks: &'a mut IndexSlice<BasicBlock, BasicBlockData<'tcx>>,
112    pred_count: IndexVec<BasicBlock, u32>,
113}
114
115impl<'a, 'tcx> CfgSimplifier<'a, 'tcx> {
116    fn new(tcx: TyCtxt<'tcx>, body: &'a mut Body<'tcx>) -> Self {
117        let mut pred_count = IndexVec::from_elem(0u32, &body.basic_blocks);
118
119        // we can't use mir.predecessors() here because that counts
120        // dead blocks, which we don't want to.
121        pred_count[START_BLOCK] = 1;
122
123        for (_, data) in traversal::preorder(body) {
124            if let Some(ref term) = data.terminator {
125                for tgt in term.successors() {
126                    pred_count[tgt] += 1;
127                }
128            }
129        }
130
131        // Preserve `SwitchInt` reads on built and analysis MIR, or if `-Zmir-preserve-ub`.
132        let preserve_switch_reads = matches!(body.phase, MirPhase::Built | MirPhase::Analysis(_))
133            || tcx.sess.opts.unstable_opts.mir_preserve_ub;
134        // Do not clear caches yet. The caller to `simplify` will do it if anything changed.
135        let basic_blocks = body.basic_blocks.as_mut_preserves_cfg();
136
137        CfgSimplifier { preserve_switch_reads, basic_blocks, pred_count }
138    }
139
140    /// Returns whether we actually simplified anything. In that case, the caller *must* invalidate
141    /// the CFG caches of the MIR body.
142    #[must_use]
143    fn simplify(mut self) -> bool {
144        self.strip_nops();
145
146        // Vec of the blocks that should be merged. We store the indices here, instead of the
147        // statements itself to avoid moving the (relatively) large statements twice.
148        // We do not push the statements directly into the target block (`bb`) as that is slower
149        // due to additional reallocations
150        let mut merged_blocks: Vec<BasicBlock> = Vec::new();
151        let mut outer_changed = false;
152        loop {
153            let mut changed = false;
154
155            for bb in self.basic_blocks.indices() {
156                if self.pred_count[bb] == 0 {
157                    continue;
158                }
159
160                debug!("simplifying {:?}", bb);
161
162                let mut terminator = self.take_terminator(bb).expect("invalid terminator state");
163
164                terminator.successors_mut(|successor| {
165                    self.collapse_goto_chain(successor, &mut changed);
166                });
167
168                let mut inner_changed = true;
169                merged_blocks.clear();
170                while inner_changed {
171                    inner_changed = false;
172                    inner_changed |= self.simplify_branch(&mut terminator);
173                    inner_changed |= self.merge_successor(&mut merged_blocks, &mut terminator);
174                    changed |= inner_changed;
175                }
176
177                let statements_to_merge =
178                    merged_blocks.iter().map(|&i| self.basic_blocks[i].statements.len()).sum();
179
180                if statements_to_merge > 0 {
181                    let mut statements = std::mem::take(&mut self.basic_blocks[bb].statements);
182                    statements.reserve(statements_to_merge);
183                    let mut parent_bb_last_debuginfos =
184                        std::mem::take(&mut self.basic_blocks[bb].after_last_stmt_debuginfos);
185                    for &from in &merged_blocks {
186                        if let Some(stmt) = self.basic_blocks[from].statements.first_mut() {
187                            stmt.debuginfos.prepend(&mut parent_bb_last_debuginfos);
188                        }
189                        statements.append(&mut self.basic_blocks[from].statements);
190                        parent_bb_last_debuginfos =
191                            std::mem::take(&mut self.basic_blocks[from].after_last_stmt_debuginfos);
192                    }
193                    self.basic_blocks[bb].statements = statements;
194                    self.basic_blocks[bb].after_last_stmt_debuginfos = parent_bb_last_debuginfos;
195                }
196
197                self.basic_blocks[bb].terminator = Some(terminator);
198            }
199
200            if !changed {
201                break;
202            }
203
204            outer_changed = true;
205        }
206
207        outer_changed
208    }
209
210    /// Replaces the terminator of a basic block with a dummy value.
211    fn take_terminator(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
212        if has_dummy_terminator(&self.basic_blocks[bb]) {
213            return None;
214        }
215        let dummy_terminator = Terminator {
216            source_info: SourceInfo { span: DUMMY_SP, scope: SourceScope::ZERO },
217            kind: TerminatorKind::Goto { target: BasicBlock::MAX, loop_hint_attrs: ThinVec::new() },
218        };
219        std::mem::replace(&mut self.basic_blocks[bb].terminator, Some(dummy_terminator))
220    }
221
222    /// This function will return `None` if
223    /// * the block has statements
224    /// * the block has a terminator other than `goto`
225    /// * the block has no terminator (meaning some other part of the current optimization stole it)
226    fn take_terminator_if_simple_goto(&mut self, bb: BasicBlock) -> Option<Terminator<'tcx>> {
227        match self.basic_blocks[bb] {
228            BasicBlockData {
229                ref statements,
230                terminator:
231                    ref mut terminator @ Some(Terminator { kind: TerminatorKind::Goto { .. }, .. }),
232                ..
233            } if statements.is_empty() => self.take_terminator(bb),
234            // if `terminator` is None, this means we are in a loop. In that
235            // case, let all the loop collapse to its entry.
236            _ => None,
237        }
238    }
239
240    /// Collapse a goto chain starting from `start`
241    fn collapse_goto_chain(&mut self, start: &mut BasicBlock, changed: &mut bool) {
242        // Using `SmallVec` here, because in some logs on libcore oli-obk saw many single-element
243        // goto chains. We should probably benchmark different sizes.
244        let mut terminators: SmallVec<[_; 1]> = Default::default();
245        let mut current = *start;
246        // If each successor has only one predecessor, it's a trivial goto chain.
247        // We can move all debuginfos to the last basic block.
248        let mut trivial_goto_chain = true;
249        while let Some(terminator) = self.take_terminator_if_simple_goto(current) {
250            let Terminator { kind: TerminatorKind::Goto { target, .. }, .. } = terminator else {
251                unreachable!();
252            };
253            trivial_goto_chain &= self.pred_count[target] == 1;
254            terminators.push((current, terminator));
255            current = target;
256        }
257        let last = current;
258        *changed |= *start != last;
259        *start = last;
260        while let Some((current, mut terminator)) = terminators.pop() {
261            let Terminator { kind: TerminatorKind::Goto { ref mut target, .. }, .. } = terminator
262            else {
263                unreachable!();
264            };
265            if trivial_goto_chain {
266                let mut pred_debuginfos =
267                    std::mem::take(&mut self.basic_blocks[current].after_last_stmt_debuginfos);
268                let debuginfos = if let Some(stmt) = self.basic_blocks[last].statements.first_mut()
269                {
270                    &mut stmt.debuginfos
271                } else {
272                    &mut self.basic_blocks[last].after_last_stmt_debuginfos
273                };
274                debuginfos.prepend(&mut pred_debuginfos);
275            }
276            *changed |= *target != last;
277            *target = last;
278            debug!("collapsing goto chain from {:?} to {:?}", current, target);
279
280            if self.pred_count[current] == 1 {
281                // This is the last reference to current, so the pred-count to
282                // to target is moved into the current block.
283                self.pred_count[current] = 0;
284            } else {
285                self.pred_count[*target] += 1;
286                self.pred_count[current] -= 1;
287            }
288            self.basic_blocks[current].terminator = Some(terminator);
289        }
290    }
291
292    // merge a block with 1 `goto` predecessor to its parent
293    fn merge_successor(
294        &mut self,
295        merged_blocks: &mut Vec<BasicBlock>,
296        terminator: &mut Terminator<'tcx>,
297    ) -> bool {
298        let target = match terminator.kind {
299            TerminatorKind::Goto { target, .. } if self.pred_count[target] == 1 => target,
300            _ => return false,
301        };
302
303        debug!("merging block {:?} into {:?}", target, terminator);
304        *terminator = match self.take_terminator(target) {
305            Some(terminator) => terminator,
306            None => {
307                // unreachable loop - this should not be possible, as we
308                // don't strand blocks, but handle it correctly.
309                return false;
310            }
311        };
312
313        merged_blocks.push(target);
314        self.pred_count[target] = 0;
315
316        true
317    }
318
319    // turn a branch with all successors identical to a goto
320    fn simplify_branch(&mut self, terminator: &mut Terminator<'tcx>) -> bool {
321        // Removing a `SwitchInt` terminator may remove reads that result in UB,
322        // so we must not apply this optimization before borrowck or when
323        // `-Zmir-preserve-ub` is set.
324        if self.preserve_switch_reads {
325            return false;
326        }
327
328        let TerminatorKind::SwitchInt { .. } = terminator.kind else {
329            return false;
330        };
331
332        let Ok(first_succ) = terminator.successors().all_equal_value() else {
333            return false;
334        };
335
336        let count = terminator.successors().count();
337        self.pred_count[first_succ] -= (count - 1) as u32;
338
339        debug!("simplifying branch {:?}", terminator);
340        terminator.kind = TerminatorKind::goto(first_succ);
341        true
342    }
343
344    fn strip_nops(&mut self) {
345        for blk in self.basic_blocks.iter_mut() {
346            blk.strip_nops();
347        }
348    }
349}
350
351pub(super) fn simplify_duplicate_switch_targets(terminator: &mut Terminator<'_>) {
352    if let TerminatorKind::SwitchInt { targets, .. } = &mut terminator.kind {
353        let otherwise = targets.otherwise();
354        if targets.iter().any(|t| t.1 == otherwise) {
355            *targets = SwitchTargets::new(
356                targets.iter().filter(|t| t.1 != otherwise),
357                targets.otherwise(),
358            );
359        }
360    }
361}
362
363pub(super) fn remove_dead_blocks(body: &mut Body<'_>) {
364    let should_deduplicate_unreachable = |bbdata: &BasicBlockData<'_>| {
365        // CfgSimplifier::simplify leaves behind some unreachable basic blocks with
366        // dummy terminator. Those blocks will be deleted by remove_dead_blocks, but we run just
367        // before then so we need to handle missing terminators.
368        // We also need to prevent confusing cleanup and non-cleanup blocks. In practice we
369        // don't emit empty unreachable cleanup blocks, so this simple check suffices.
370        !has_dummy_terminator(bbdata) && bbdata.is_empty_unreachable() && !bbdata.is_cleanup
371    };
372
373    let reachable = traversal::reachable_as_bitset(body);
374    let empty_unreachable_blocks = body
375        .basic_blocks
376        .iter_enumerated()
377        .filter(|(bb, bbdata)| should_deduplicate_unreachable(bbdata) && reachable.contains(*bb))
378        .count();
379
380    let num_blocks = body.basic_blocks.len();
381    if num_blocks == reachable.count() && empty_unreachable_blocks <= 1 {
382        return;
383    }
384
385    let basic_blocks = body.basic_blocks.as_mut();
386
387    let mut replacements: Vec<_> = (0..num_blocks).map(BasicBlock::new).collect();
388    let mut orig_index = 0;
389    let mut used_index = 0;
390    let mut kept_unreachable = None;
391    let mut deduplicated_unreachable = false;
392    basic_blocks.raw.retain(|bbdata| {
393        let orig_bb = BasicBlock::new(orig_index);
394        if !reachable.contains(orig_bb) {
395            orig_index += 1;
396            return false;
397        }
398
399        let used_bb = BasicBlock::new(used_index);
400        if should_deduplicate_unreachable(bbdata) {
401            let kept_unreachable = *kept_unreachable.get_or_insert(used_bb);
402            if kept_unreachable != used_bb {
403                replacements[orig_index] = kept_unreachable;
404                deduplicated_unreachable = true;
405                orig_index += 1;
406                return false;
407            }
408        }
409
410        replacements[orig_index] = used_bb;
411        used_index += 1;
412        orig_index += 1;
413        true
414    });
415
416    // If we deduplicated unreachable blocks we erase their source_info as we
417    // can no longer attribute their code to a particular location in the
418    // source.
419    if deduplicated_unreachable {
420        basic_blocks[kept_unreachable.unwrap()].terminator_mut().source_info =
421            SourceInfo { span: DUMMY_SP, scope: OUTERMOST_SOURCE_SCOPE };
422    }
423
424    for block in basic_blocks {
425        block.terminator_mut().successors_mut(|target| *target = replacements[target.index()]);
426    }
427}
428
429fn has_dummy_terminator(bbdata: &BasicBlockData<'_>) -> bool {
430    match bbdata.terminator().kind {
431        TerminatorKind::Goto { target, .. } => target == BasicBlock::MAX,
432        _ => false,
433    }
434}
435
436pub(super) enum SimplifyLocals {
437    BeforeConstProp,
438    AfterGVN,
439    Final,
440}
441
442impl<'tcx> crate::MirPass<'tcx> for SimplifyLocals {
443    fn name(&self) -> &'static str {
444        match &self {
445            SimplifyLocals::BeforeConstProp => "SimplifyLocals-before-const-prop",
446            SimplifyLocals::AfterGVN => "SimplifyLocals-after-value-numbering",
447            SimplifyLocals::Final => "SimplifyLocals-final",
448        }
449    }
450
451    fn policy(&self, ctx: &crate::PassCtx<'_>) -> PassPolicy {
452        PassPolicy::optional(ctx.mir_opt_level() >= 1)
453    }
454
455    fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
456        trace!("running SimplifyLocals on {:?}", body.source);
457
458        // First, we're going to get a count of *actual* uses for every `Local`.
459        let mut used_locals = UsedLocals::new(body);
460
461        // Next, we're going to remove any `Local` with zero actual uses. When we remove those
462        // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
463        // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
464        // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
465        // fixedpoint where there are no more unused locals.
466        remove_unused_definitions_helper(&mut used_locals, body);
467
468        // Finally, we'll actually do the work of shrinking `body.local_decls` and remapping the
469        // `Local`s.
470        let map = make_local_map(&mut body.local_decls, &used_locals);
471
472        // Only bother running the `LocalUpdater` if we actually found locals to remove.
473        if map.iter().any(Option::is_none) {
474            // Update references to all vars and tmps now
475            let mut updater = LocalUpdater { map, tcx };
476            updater.visit_body_preserves_cfg(body);
477
478            body.local_decls.shrink_to_fit();
479        }
480    }
481}
482
483pub(super) fn remove_unused_definitions<'tcx>(body: &mut Body<'tcx>) {
484    // First, we're going to get a count of *actual* uses for every `Local`.
485    let mut used_locals = UsedLocals::new(body);
486
487    // Next, we're going to remove any `Local` with zero actual uses. When we remove those
488    // `Locals`, we're also going to subtract any uses of other `Locals` from the `used_locals`
489    // count. For example, if we removed `_2 = discriminant(_1)`, then we'll subtract one from
490    // `use_counts[_1]`. That in turn might make `_1` unused, so we loop until we hit a
491    // fixedpoint where there are no more unused locals.
492    remove_unused_definitions_helper(&mut used_locals, body);
493}
494
495/// Construct the mapping while swapping out unused stuff out from the `vec`.
496fn make_local_map<V>(
497    local_decls: &mut IndexVec<Local, V>,
498    used_locals: &UsedLocals,
499) -> IndexVec<Local, Option<Local>> {
500    let mut map: IndexVec<Local, Option<Local>> = IndexVec::from_elem(None, local_decls);
501    let mut used = Local::ZERO;
502
503    for alive_index in local_decls.indices() {
504        // `is_used` treats the `RETURN_PLACE` and arguments as used.
505        if !used_locals.is_used(alive_index) {
506            continue;
507        }
508
509        map[alive_index] = Some(used);
510        if alive_index != used {
511            local_decls.swap(alive_index, used);
512        }
513        used.increment_by(1);
514    }
515    local_decls.truncate(used.index());
516    map
517}
518
519/// Keeps track of used & unused locals.
520struct UsedLocals {
521    increment: bool,
522    use_count: IndexVec<Local, u32>,
523    always_used: DenseBitSet<Local>,
524}
525
526impl UsedLocals {
527    /// Determines which locals are used & unused in the given body.
528    fn new(body: &Body<'_>) -> Self {
529        let mut always_used = debuginfo_locals(body);
530        always_used.insert(RETURN_PLACE);
531        for arg in body.args_iter() {
532            always_used.insert(arg);
533        }
534        let mut this = Self {
535            increment: true,
536            use_count: IndexVec::from_elem(0, &body.local_decls),
537            always_used,
538        };
539        this.visit_body(body);
540        this
541    }
542
543    /// Checks if local is used.
544    ///
545    /// Return place, arguments, var debuginfo are always considered used.
546    fn is_used(&self, local: Local) -> bool {
547        trace!(
548            "is_used({:?}): use_count: {:?}, always_used: {}",
549            local,
550            self.use_count[local],
551            self.always_used.contains(local)
552        );
553        // To keep things simple, we don't handle debugging information here, these are in DSE.
554        self.always_used.contains(local) || self.use_count[local] != 0
555    }
556
557    /// Updates the use counts to reflect the removal of given statement.
558    fn statement_removed(&mut self, statement: &Statement<'_>) {
559        self.increment = false;
560
561        // The location of the statement is irrelevant.
562        let location = Location::START;
563        self.visit_statement(statement, location);
564    }
565
566    /// Visits a left-hand side of an assignment.
567    fn visit_lhs(&mut self, place: &Place<'_>, location: Location) {
568        if place.is_indirect() {
569            // A use, not a definition.
570            self.visit_place(place, PlaceContext::MutatingUse(MutatingUseContext::Store), location);
571        } else {
572            // A definition. The base local itself is not visited, so this occurrence is not counted
573            // toward its use count. There might be other locals still, used in an indexing
574            // projection.
575            self.super_projection(
576                place.as_ref(),
577                PlaceContext::MutatingUse(MutatingUseContext::Projection),
578                location,
579            );
580        }
581    }
582}
583
584impl<'tcx> Visitor<'tcx> for UsedLocals {
585    fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
586        match statement.kind {
587            StatementKind::Intrinsic(..)
588            | StatementKind::Coverage(..)
589            | StatementKind::FakeRead(..)
590            | StatementKind::PlaceMention(..)
591            | StatementKind::AscribeUserType(..) => {
592                self.super_statement(statement, location);
593            }
594
595            StatementKind::ConstEvalCounter
596            | StatementKind::Nop
597            | StatementKind::StorageLive(..)
598            | StatementKind::StorageDead(..) => {}
599            StatementKind::Assign((ref place, ref rvalue)) => {
600                if rvalue.is_safe_to_remove() {
601                    self.visit_lhs(place, location);
602                    self.visit_rvalue(rvalue, location);
603                } else {
604                    self.super_statement(statement, location);
605                }
606            }
607
608            StatementKind::SetDiscriminant { ref place, variant_index: _ }
609            | StatementKind::BackwardIncompatibleDropHint { ref place, reason: _ } => {
610                self.visit_lhs(place, location);
611            }
612        }
613    }
614
615    fn visit_local(&mut self, local: Local, ctx: PlaceContext, _location: Location) {
616        if matches!(ctx, PlaceContext::NonUse(_)) {
617            return;
618        }
619        if self.increment {
620            self.use_count[local] += 1;
621        } else {
622            assert_ne!(self.use_count[local], 0);
623            self.use_count[local] -= 1;
624        }
625    }
626}
627
628/// Removes unused definitions. Updates the used locals to reflect the changes made.
629fn remove_unused_definitions_helper(used_locals: &mut UsedLocals, body: &mut Body<'_>) {
630    // The use counts are updated as we remove the statements. A local might become unused
631    // during the retain operation, leading to a temporary inconsistency (storage statements or
632    // definitions referencing the local might remain). For correctness it is crucial that this
633    // computation reaches a fixed point.
634
635    let mut modified = true;
636    while modified {
637        modified = false;
638
639        for data in body.basic_blocks.as_mut_preserves_cfg() {
640            // Remove unnecessary StorageLive and StorageDead annotations.
641            for statement in data.statements.iter_mut() {
642                let keep_statement = match &statement.kind {
643                    StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
644                        used_locals.is_used(*local)
645                    }
646                    StatementKind::Assign((place, _)) => used_locals.is_used(place.local),
647                    StatementKind::SetDiscriminant { place, .. }
648                    | StatementKind::BackwardIncompatibleDropHint { place, .. } => {
649                        used_locals.is_used(place.local)
650                    }
651                    _ => continue,
652                };
653                if keep_statement {
654                    continue;
655                }
656                trace!("removing statement {:?}", statement);
657                modified = true;
658                used_locals.statement_removed(statement);
659                statement.make_nop(true);
660            }
661            data.strip_nops();
662        }
663    }
664}
665
666struct LocalUpdater<'tcx> {
667    map: IndexVec<Local, Option<Local>>,
668    tcx: TyCtxt<'tcx>,
669}
670
671impl<'tcx> MutVisitor<'tcx> for LocalUpdater<'tcx> {
672    fn tcx(&self) -> TyCtxt<'tcx> {
673        self.tcx
674    }
675
676    fn visit_statement_debuginfo(
677        &mut self,
678        stmt_debuginfo: &mut StmtDebugInfo<'tcx>,
679        location: Location,
680    ) {
681        match stmt_debuginfo {
682            StmtDebugInfo::AssignRef(local, place) => {
683                if place.as_ref().accessed_locals().any(|local| self.map[local].is_none()) {
684                    *stmt_debuginfo = StmtDebugInfo::InvalidAssign(*local);
685                }
686            }
687            StmtDebugInfo::InvalidAssign(_) => {}
688        }
689        self.super_statement_debuginfo(stmt_debuginfo, location);
690    }
691
692    fn visit_local(&mut self, l: &mut Local, _: PlaceContext, _: Location) {
693        *l = self.map[*l].unwrap();
694    }
695}
696
697pub(crate) struct UsedInStmtLocals {
698    pub(crate) locals: DenseBitSet<Local>,
699}
700
701impl UsedInStmtLocals {
702    pub(crate) fn new(body: &Body<'_>) -> Self {
703        let mut this = Self { locals: DenseBitSet::new_empty(body.local_decls.len()) };
704        this.visit_body(body);
705        this
706    }
707
708    pub(crate) fn remove_unused_storage_annotations<'tcx>(&self, body: &mut Body<'tcx>) {
709        for data in body.basic_blocks.as_mut_preserves_cfg() {
710            // Remove unnecessary StorageLive and StorageDead annotations.
711            for statement in data.statements.iter_mut() {
712                let keep_statement = match &statement.kind {
713                    StatementKind::StorageLive(local) | StatementKind::StorageDead(local) => {
714                        self.locals.contains(*local)
715                    }
716                    _ => continue,
717                };
718                if keep_statement {
719                    continue;
720                }
721                statement.make_nop(true);
722            }
723        }
724    }
725}
726
727impl<'tcx> Visitor<'tcx> for UsedInStmtLocals {
728    fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
729        if matches!(context, PlaceContext::NonUse(_)) {
730            return;
731        }
732        self.locals.insert(local);
733    }
734}