compiler/rustc_mir_transform/src/dead_store_elimination.rs

   1 //! This module implements a dead store elimination (DSE) routine.
   2 //!
   3 //! This transformation was written specifically for the needs of dest prop. Although it is
   4 //! perfectly sound to use it in any context that might need it, its behavior should not be changed
   5 //! without analyzing the interaction this will have with dest prop. Specifically, in addition to
   6 //! the soundness of this pass in general, dest prop needs it to satisfy two additional conditions:
   7 //!
   8 //!  1. It's idempotent, meaning that running this pass a second time immediately after running it a
   9 //!     first time will not cause any further changes.
  10 //!  2. This idempotence persists across dest prop's main transform, in other words inserting any
  11 //!     number of iterations of dest prop between the first and second application of this transform
  12 //!     will still not cause any further changes.
  13 //!
  14
  15 use crate::util::is_within_packed;
  16 use rustc_index::bit_set::BitSet;
  17 use rustc_middle::mir::visit::Visitor;
  18 use rustc_middle::mir::*;
  19 use rustc_middle::ty::TyCtxt;
  20 use rustc_mir_dataflow::impls::{
  21     borrowed_locals, LivenessTransferFunction, MaybeTransitiveLiveLocals,
  22 };
  23 use rustc_mir_dataflow::Analysis;
  24
  25 /// Performs the optimization on the body
  26 ///
  27 /// The `borrowed` set must be a `BitSet` of all the locals that are ever borrowed in this body. It
  28 /// can be generated via the [`borrowed_locals`] function.
  29 pub fn eliminate<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>, borrowed: &BitSet<Local>) {
  30     let mut live = MaybeTransitiveLiveLocals::new(borrowed)
  31         .into_engine(tcx, body)
  32         .iterate_to_fixpoint()
  33         .into_results_cursor(body);
  34
  35     // For blocks with a call terminator, if an argument copy can be turned into a move,
  36     // record it as (block, argument index).
  37     let mut call_operands_to_move = Vec::new();
  38     let mut patch = Vec::new();
  39
  40     for (bb, bb_data) in traversal::preorder(body) {
  41         if let TerminatorKind::Call { ref args, .. } = bb_data.terminator().kind {
  42             let loc = Location { block: bb, statement_index: bb_data.statements.len() };
  43
  44             // Position ourselves between the evaluation of `args` and the write to `destination`.
  45             live.seek_to_block_end(bb);
  46             let mut state = live.get().clone();
  47
  48             for (index, arg) in args.iter().enumerate().rev() {
  49                 if let Operand::Copy(place) = *arg
  50                     && !place.is_indirect()
  51                     && !borrowed.contains(place.local)
  52                     && !state.contains(place.local)
  53                     // If `place` is a projection of a disaligned field in a packed ADT,
  54                     // the move may be codegened as a pointer to that field.
  55                     // Using that disaligned pointer may trigger UB in the callee,
  56                     // so do nothing.
  57                     && is_within_packed(tcx, body, place).is_none()
  58                 {
  59                     call_operands_to_move.push((bb, index));
  60                 }
  61
  62                 // Account that `arg` is read from, so we don't promote another argument to a move.
  63                 LivenessTransferFunction(&mut state).visit_operand(arg, loc);
  64             }
  65         }
  66
  67         for (statement_index, statement) in bb_data.statements.iter().enumerate().rev() {
  68             let loc = Location { block: bb, statement_index };
  69             if let StatementKind::Assign(assign) = &statement.kind {
  70                 if !assign.1.is_safe_to_remove() {
  71                     continue;
  72                 }
  73             }
  74             match &statement.kind {
  75                 StatementKind::Assign(box (place, _))
  76                 | StatementKind::SetDiscriminant { place: box place, .. }
  77                 | StatementKind::Deinit(box place) => {
  78                     if !place.is_indirect() && !borrowed.contains(place.local) {
  79                         live.seek_before_primary_effect(loc);
  80                         if !live.get().contains(place.local) {
  81                             patch.push(loc);
  82                         }
  83                     }
  84                 }
  85                 StatementKind::Retag(_, _)
  86                 | StatementKind::StorageLive(_)
  87                 | StatementKind::StorageDead(_)
  88                 | StatementKind::Coverage(_)
  89                 | StatementKind::Intrinsic(_)
  90                 | StatementKind::ConstEvalCounter
  91                 | StatementKind::PlaceMention(_)
  92                 | StatementKind::Nop => (),
  93
  94                 StatementKind::FakeRead(_) | StatementKind::AscribeUserType(_, _) => {
  95                     bug!("{:?} not found in this MIR phase!", &statement.kind)
  96                 }
  97             }
  98         }
  99     }
 100
 101     if patch.is_empty() && call_operands_to_move.is_empty() {
 102         return;
 103     }
 104
 105     let bbs = body.basic_blocks.as_mut_preserves_cfg();
 106     for Location { block, statement_index } in patch {
 107         bbs[block].statements[statement_index].make_nop();
 108     }
 109     for (block, argument_index) in call_operands_to_move {
 110         let TerminatorKind::Call { ref mut args, .. } = bbs[block].terminator_mut().kind else {
 111             bug!()
 112         };
 113         let arg = &mut args[argument_index];
 114         let Operand::Copy(place) = *arg else { bug!() };
 115         *arg = Operand::Move(place);
 116     }
 117
 118     crate::simplify::simplify_locals(body, tcx)
 119 }
 120
 121 pub struct DeadStoreElimination;
 122
 123 impl<'tcx> MirPass<'tcx> for DeadStoreElimination {
 124     fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
 125         sess.mir_opt_level() >= 2
 126     }
 127
 128     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
 129         let borrowed = borrowed_locals(body);
 130         eliminate(tcx, body, &borrowed);
 131     }
 132 }