Add dead store elimination pass

13 files changed, 496 insertions, 25 deletions

diff --git a/compiler/rustc_middle/src/mir/tcx.rs b/compiler/rustc_middle/src/mir/tcx.rs
index c93b7a95502..f1fb484a801 100644
--- a/compiler/rustc_middle/src/mir/tcx.rs
+++ b/compiler/rustc_middle/src/mir/tcx.rs
@@ -4,6 +4,7 @@
  */
 
 use crate::mir::*;
+use crate::ty::cast::CastTy;
 use crate::ty::subst::Subst;
 use crate::ty::{self, Ty, TyCtxt};
 use rustc_hir as hir;
@@ -223,6 +224,22 @@ impl<'tcx> Rvalue<'tcx> {
             _ => RvalueInitializationState::Deep,
         }
     }
+
+    pub fn is_pointer_int_cast<D>(&self, local_decls: &D, tcx: TyCtxt<'tcx>) -> bool
+    where
+        D: HasLocalDecls<'tcx>,
+    {
+        if let Rvalue::Cast(CastKind::Misc, src_op, dest_ty) = self {
+            if let Some(CastTy::Int(_)) = CastTy::from_ty(*dest_ty) {
+                let src_ty = src_op.ty(local_decls, tcx);
+                if let Some(CastTy::FnPtr | CastTy::Ptr(_)) = CastTy::from_ty(src_ty) {
+                    return true;
+                }
+            }
+        }
+
+        false
+    }
 }
 
 impl<'tcx> Operand<'tcx> {
diff --git a/compiler/rustc_mir_dataflow/src/impls/liveness.rs b/compiler/rustc_mir_dataflow/src/impls/liveness.rs
index 5a788c153a4..4350eb6cdd3 100644
--- a/compiler/rustc_mir_dataflow/src/impls/liveness.rs
+++ b/compiler/rustc_mir_dataflow/src/impls/liveness.rs
@@ -1,8 +1,9 @@
-use rustc_index::bit_set::BitSet;
+use rustc_index::bit_set::{BitSet, ChunkedBitSet};
 use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
-use rustc_middle::mir::{self, Local, Location};
+use rustc_middle::mir::{self, Local, LocalDecls, Location, Place, StatementKind};
+use rustc_middle::ty::TyCtxt;
 
-use crate::{AnalysisDomain, Backward, CallReturnPlaces, GenKill, GenKillAnalysis};
+use crate::{Analysis, AnalysisDomain, Backward, CallReturnPlaces, GenKill, GenKillAnalysis};
 
 /// A [live-variable dataflow analysis][liveness].
 ///
@@ -98,19 +99,16 @@ where
     T: GenKill<Local>,
 {
     fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
-        let mir::Place { projection, local } = *place;
+        let local = place.local;
 
         // We purposefully do not call `super_place` here to avoid calling `visit_local` for this
         // place with one of the `Projection` variants of `PlaceContext`.
         self.visit_projection(place.as_ref(), context, location);
 
-        match DefUse::for_place(context) {
-            // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a use.
-            Some(_) if place.is_indirect() => self.0.gen(local),
-
-            Some(DefUse::Def) if projection.is_empty() => self.0.kill(local),
+        match DefUse::for_place(*place, context) {
+            Some(DefUse::Def) => self.0.kill(local),
             Some(DefUse::Use) => self.0.gen(local),
-            _ => {}
+            None => {}
         }
     }
 
@@ -118,10 +116,10 @@ where
         // Because we do not call `super_place` above, `visit_local` is only called for locals that
         // do not appear as part of  a `Place` in the MIR. This handles cases like the implicit use
         // of the return place in a `Return` terminator or the index in an `Index` projection.
-        match DefUse::for_place(context) {
+        match DefUse::for_place(local.into(), context) {
             Some(DefUse::Def) => self.0.kill(local),
             Some(DefUse::Use) => self.0.gen(local),
-            _ => {}
+            None => {}
         }
     }
 }
@@ -133,27 +131,37 @@ enum DefUse {
 }
 
 impl DefUse {
-    fn for_place(context: PlaceContext) -> Option<DefUse> {
+    fn for_place<'tcx>(place: Place<'tcx>, context: PlaceContext) -> Option<DefUse> {
         match context {
             PlaceContext::NonUse(_) => None,
 
             PlaceContext::MutatingUse(MutatingUseContext::Store | MutatingUseContext::Deinit) => {
-                Some(DefUse::Def)
+                if place.is_indirect() {
+                    // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a
+                    // use.
+                    Some(DefUse::Use)
+                } else if place.projection.is_empty() {
+                    Some(DefUse::Def)
+                } else {
+                    None
+                }
             }
 
             // Setting the discriminant is not a use because it does no reading, but it is also not
             // a def because it does not overwrite the whole place
-            PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => None,
+            PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => {
+                place.is_indirect().then_some(DefUse::Use)
+            }
 
-            // `MutatingUseContext::Call` and `MutatingUseContext::Yield` indicate that this is the
-            // destination place for a `Call` return or `Yield` resume respectively. Since this is
-            // only a `Def` when the function returns successfully, we handle this case separately
-            // in `call_return_effect` above.
+            // For the associated terminators, this is only a `Def` when the terminator returns
+            // "successfully." As such, we handle this case separately in `call_return_effect`
+            // above. However, if the place looks like `*_5`, this is still unconditionally a use of
+            // `_5`.
             PlaceContext::MutatingUse(
                 MutatingUseContext::Call
-                | MutatingUseContext::AsmOutput
-                | MutatingUseContext::Yield,
-            ) => None,
+                | MutatingUseContext::Yield
+                | MutatingUseContext::AsmOutput,
+            ) => place.is_indirect().then_some(DefUse::Use),
 
             // All other contexts are uses...
             PlaceContext::MutatingUse(
@@ -179,3 +187,133 @@ impl DefUse {
         }
     }
 }
+
+/// Like `MaybeLiveLocals`, but does not mark locals as live if they are used in a dead assignment.
+///
+/// This is basically written for dead store elimination and nothing else.
+///
+/// All of the caveats of `MaybeLiveLocals` apply.
+pub struct MaybeTransitiveLiveLocals<'a, 'tcx> {
+    always_live: &'a BitSet<Local>,
+    local_decls: &'a LocalDecls<'tcx>,
+    tcx: TyCtxt<'tcx>,
+}
+
+impl<'a, 'tcx> MaybeTransitiveLiveLocals<'a, 'tcx> {
+    /// The `always_alive` set is the set of locals to which all stores should unconditionally be
+    /// considered live.
+    ///
+    /// This should include at least all locals that are ever borrowed.
+    pub fn new(
+        always_live: &'a BitSet<Local>,
+        local_decls: &'a LocalDecls<'tcx>,
+        tcx: TyCtxt<'tcx>,
+    ) -> Self {
+        MaybeTransitiveLiveLocals { always_live, local_decls, tcx }
+    }
+}
+
+impl<'a, 'tcx> AnalysisDomain<'tcx> for MaybeTransitiveLiveLocals<'a, 'tcx> {
+    type Domain = ChunkedBitSet<Local>;
+    type Direction = Backward;
+
+    const NAME: &'static str = "transitive liveness";
+
+    fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
+        // bottom = not live
+        ChunkedBitSet::new_empty(body.local_decls.len())
+    }
+
+    fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
+        // No variables are live until we observe a use
+    }
+}
+
+struct TransferWrapper<'a>(&'a mut ChunkedBitSet<Local>);
+
+impl<'a> GenKill<Local> for TransferWrapper<'a> {
+    fn gen(&mut self, l: Local) {
+        self.0.insert(l);
+    }
+
+    fn kill(&mut self, l: Local) {
+        self.0.remove(l);
+    }
+}
+
+impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a, 'tcx> {
+    fn apply_statement_effect(
+        &self,
+        trans: &mut Self::Domain,
+        statement: &mir::Statement<'tcx>,
+        location: Location,
+    ) {
+        // Compute the place that we are storing to, if any
+        let destination = match &statement.kind {
+            StatementKind::Assign(assign) => {
+                if assign.1.is_pointer_int_cast(self.local_decls, self.tcx) {
+                    // Pointer to int casts may be side-effects due to exposing the provenance.
+                    // While the model is undecided, we should be conservative. See
+                    // <https://www.ralfj.de/blog/2022/04/11/provenance-exposed.html>
+                    None
+                } else {
+                    Some(assign.0)
+                }
+            }
+            StatementKind::SetDiscriminant { place, .. } | StatementKind::Deinit(place) => {
+                Some(**place)
+            }
+            StatementKind::FakeRead(_)
+            | StatementKind::StorageLive(_)
+            | StatementKind::StorageDead(_)
+            | StatementKind::Retag(..)
+            | StatementKind::AscribeUserType(..)
+            | StatementKind::Coverage(..)
+            | StatementKind::CopyNonOverlapping(..)
+            | StatementKind::Nop => None,
+        };
+        if let Some(destination) = destination {
+            if !destination.is_indirect()
+                && !trans.contains(destination.local)
+                && !self.always_live.contains(destination.local)
+            {
+                // This store is dead
+                return;
+            }
+        }
+        TransferFunction(&mut TransferWrapper(trans)).visit_statement(statement, location);
+    }
+
+    fn apply_terminator_effect(
+        &self,
+        trans: &mut Self::Domain,
+        terminator: &mir::Terminator<'tcx>,
+        location: Location,
+    ) {
+        TransferFunction(&mut TransferWrapper(trans)).visit_terminator(terminator, location);
+    }
+
+    fn apply_call_return_effect(
+        &self,
+        trans: &mut Self::Domain,
+        _block: mir::BasicBlock,
+        return_places: CallReturnPlaces<'_, 'tcx>,
+    ) {
+        return_places.for_each(|place| {
+            if let Some(local) = place.as_local() {
+                trans.remove(local);
+            }
+        });
+    }
+
+    fn apply_yield_resume_effect(
+        &self,
+        trans: &mut Self::Domain,
+        _resume_block: mir::BasicBlock,
+        resume_place: mir::Place<'tcx>,
+    ) {
+        if let Some(local) = resume_place.as_local() {
+            trans.remove(local);
+        }
+    }
+}
diff --git a/compiler/rustc_mir_dataflow/src/impls/mod.rs b/compiler/rustc_mir_dataflow/src/impls/mod.rs
index c9722a6df77..41cf43fc8e1 100644
--- a/compiler/rustc_mir_dataflow/src/impls/mod.rs
+++ b/compiler/rustc_mir_dataflow/src/impls/mod.rs
@@ -26,6 +26,7 @@ mod storage_liveness;
 pub use self::borrowed_locals::MaybeBorrowedLocals;
 pub use self::init_locals::MaybeInitializedLocals;
 pub use self::liveness::MaybeLiveLocals;
+pub use self::liveness::MaybeTransitiveLiveLocals;
 pub use self::storage_liveness::{MaybeRequiresStorage, MaybeStorageLive};
 
 /// `MaybeInitializedPlaces` tracks all places that might be
diff --git a/compiler/rustc_mir_transform/src/dead_store_elimination.rs b/compiler/rustc_mir_transform/src/dead_store_elimination.rs
new file mode 100644
index 00000000000..84f2ee639e4
--- /dev/null
+++ b/compiler/rustc_mir_transform/src/dead_store_elimination.rs
@@ -0,0 +1,148 @@
+//! This module implements a dead store elimination (DSE) routine.
+//!
+//! This transformation was written specifically for the needs of dest prop. Although it is
+//! perfectly sound to use it in any context that might need it, its behavior should not be changed
+//! without analyzing the interaction this will have with dest prop. Specifically, in addition to
+//! the soundness of this pass in general, dest prop needs it to satisfy two additional conditions:
+//!
+//!  1. It's idempotent, meaning that running this pass a second time immediately after running it a
+//!     first time will not cause any further changes.
+//!  2. This idempotence persists across dest prop's main transform, in other words inserting any
+//!     number of iterations of dest prop between the first and second application of this transform
+//!     will still not cause any further changes.
+//!
+
+use rustc_index::bit_set::BitSet;
+use rustc_middle::{
+    mir::{visit::Visitor, *},
+    ty::TyCtxt,
+};
+use rustc_mir_dataflow::{impls::MaybeTransitiveLiveLocals, Analysis};
+
+/// Performs the optimization on the body
+///
+/// The `borrowed` set must be a `BitSet` of all the locals that are ever borrowed in this body. It
+/// can be generated via the [`get_borrowed_locals`] function.
+pub fn eliminate<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>, borrowed: &BitSet<Local>) {
+    let mut live = MaybeTransitiveLiveLocals::new(borrowed, &body.local_decls, tcx)
+        .into_engine(tcx, body)
+        .iterate_to_fixpoint()
+        .into_results_cursor(body);
+
+    let mut patch = Vec::new();
+    for (bb, bb_data) in traversal::preorder(body) {
+        for (statement_index, statement) in bb_data.statements.iter().enumerate().rev() {
+            let loc = Location { block: bb, statement_index };
+            if let StatementKind::Assign(assign) = &statement.kind {
+                if assign.1.is_pointer_int_cast(&body.local_decls, tcx) {
+                    continue;
+                }
+            }
+            match &statement.kind {
+                StatementKind::Assign(box (place, _))
+                | StatementKind::SetDiscriminant { place: box place, .. }
+                | StatementKind::Deinit(box place) => {
+                    if !place.is_indirect() && !borrowed.contains(place.local) {
+                        live.seek_before_primary_effect(loc);
+                        if !live.get().contains(place.local) {
+                            patch.push(loc);
+                        }
+                    }
+                }
+                StatementKind::Retag(_, _)
+                | StatementKind::StorageLive(_)
+                | StatementKind::StorageDead(_)
+                | StatementKind::Coverage(_)
+                | StatementKind::CopyNonOverlapping(_)
+                | StatementKind::Nop => (),
+
+                StatementKind::FakeRead(_) | StatementKind::AscribeUserType(_, _) => {
+                    bug!("{:?} not found in this MIR phase!", &statement.kind)
+                }
+            }
+        }
+    }
+
+    if patch.is_empty() {
+        return;
+    }
+
+    let bbs = body.basic_blocks_mut();
+    for Location { block, statement_index } in patch {
+        bbs[block].statements[statement_index].make_nop();
+    }
+}
+
+pub fn get_borrowed_locals(body: &Body<'_>) -> BitSet<Local> {
+    let mut b = BorrowedLocals(BitSet::new_empty(body.local_decls.len()));
+    b.visit_body(body);
+    b.0
+}
+
+struct BorrowedLocals(BitSet<Local>);
+
+impl<'tcx> Visitor<'tcx> for BorrowedLocals {
+    fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, loc: Location) {
+        self.super_rvalue(rvalue, loc);
+        match rvalue {
+            Rvalue::AddressOf(_, borrowed_place) | Rvalue::Ref(_, _, borrowed_place) => {
+                if !borrowed_place.is_indirect() {
+                    self.0.insert(borrowed_place.local);
+                }
+            }
+
+            Rvalue::Cast(..)
+            | Rvalue::ShallowInitBox(..)
+            | Rvalue::Use(..)
+            | Rvalue::Repeat(..)
+            | Rvalue::Len(..)
+            | Rvalue::BinaryOp(..)
+            | Rvalue::CheckedBinaryOp(..)
+            | Rvalue::NullaryOp(..)
+            | Rvalue::UnaryOp(..)
+            | Rvalue::Discriminant(..)
+            | Rvalue::Aggregate(..)
+            | Rvalue::ThreadLocalRef(..) => {}
+        }
+    }
+
+    fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
+        self.super_terminator(terminator, location);
+
+        match terminator.kind {
+            TerminatorKind::Drop { place: dropped_place, .. } => {
+                if !dropped_place.is_indirect() {
+                    self.0.insert(dropped_place.local);
+                }
+            }
+
+            TerminatorKind::Abort
+            | TerminatorKind::DropAndReplace { .. }
+            | TerminatorKind::Assert { .. }
+            | TerminatorKind::Call { .. }
+            | TerminatorKind::FalseEdge { .. }
+            | TerminatorKind::FalseUnwind { .. }
+            | TerminatorKind::GeneratorDrop
+            | TerminatorKind::Goto { .. }
+            | TerminatorKind::Resume
+            | TerminatorKind::Return
+            | TerminatorKind::SwitchInt { .. }
+            | TerminatorKind::Unreachable
+            | TerminatorKind::Yield { .. }
+            | TerminatorKind::InlineAsm { .. } => {}
+        }
+    }
+}
+
+pub struct DeadStoreElimination;
+
+impl<'tcx> MirPass<'tcx> for DeadStoreElimination {
+    fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
+        sess.mir_opt_level() >= 2
+    }
+
+    fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
+        let borrowed = get_borrowed_locals(body);
+        eliminate(tcx, body, &borrowed);
+    }
+}
diff --git a/compiler/rustc_mir_transform/src/lib.rs b/compiler/rustc_mir_transform/src/lib.rs
index 571f541072a..0e57c3c6979 100644
--- a/compiler/rustc_mir_transform/src/lib.rs
+++ b/compiler/rustc_mir_transform/src/lib.rs
@@ -49,6 +49,7 @@ mod const_goto;
 mod const_prop;
 mod const_prop_lint;
 mod coverage;
+mod dead_store_elimination;
 mod deaggregator;
 mod deduplicate_blocks;
 mod deref_separator;
@@ -481,17 +482,18 @@ fn run_optimization_passes<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
             &const_prop::ConstProp,
             //
             // Const-prop runs unconditionally, but doesn't mutate the MIR at mir-opt-level=0.
+            &const_debuginfo::ConstDebugInfo,
             &o1(simplify_branches::SimplifyConstCondition::new("after-const-prop")),
             &early_otherwise_branch::EarlyOtherwiseBranch,
             &simplify_comparison_integral::SimplifyComparisonIntegral,
             &simplify_try::SimplifyArmIdentity,
             &simplify_try::SimplifyBranchSame,
+            &dead_store_elimination::DeadStoreElimination,
             &dest_prop::DestinationPropagation,
             &o1(simplify_branches::SimplifyConstCondition::new("final")),
             &o1(remove_noop_landing_pads::RemoveNoopLandingPads),
             &o1(simplify::SimplifyCfg::new("final")),
             &nrvo::RenameReturnPlace,
-            &const_debuginfo::ConstDebugInfo,
             &simplify::SimplifyLocals,
             &multiple_return_terminators::MultipleReturnTerminators,
             &deduplicate_blocks::DeduplicateBlocks,
diff --git a/src/test/mir-opt/const_debuginfo.main.ConstDebugInfo.diff b/src/test/mir-opt/const_debuginfo.main.ConstDebugInfo.diff
index bbde6ad4b63..cd4b471b28c 100644
--- a/src/test/mir-opt/const_debuginfo.main.ConstDebugInfo.diff
+++ b/src/test/mir-opt/const_debuginfo.main.ConstDebugInfo.diff
@@ -99,6 +99,7 @@
           _13 = const 64_u32;              // scope 8 at $DIR/const_debuginfo.rs:21:13: 21:22
           StorageDead(_15);                // scope 8 at $DIR/const_debuginfo.rs:21:21: 21:22
           StorageDead(_14);                // scope 8 at $DIR/const_debuginfo.rs:21:21: 21:22
+          nop;                             // scope 0 at $DIR/const_debuginfo.rs:8:11: 22:2
           StorageDead(_13);                // scope 8 at $DIR/const_debuginfo.rs:22:1: 22:2
           StorageDead(_12);                // scope 7 at $DIR/const_debuginfo.rs:22:1: 22:2
           StorageDead(_11);                // scope 6 at $DIR/const_debuginfo.rs:22:1: 22:2
diff --git a/src/test/mir-opt/dead-store-elimination/cycle.cycle.DeadStoreElimination.diff b/src/test/mir-opt/dead-store-elimination/cycle.cycle.DeadStoreElimination.diff
new file mode 100644
index 00000000000..6037f89086d
--- /dev/null
+++ b/src/test/mir-opt/dead-store-elimination/cycle.cycle.DeadStoreElimination.diff
@@ -0,0 +1,75 @@
+- // MIR for `cycle` before DeadStoreElimination
++ // MIR for `cycle` after DeadStoreElimination
+  
+  fn cycle(_1: i32, _2: i32, _3: i32) -> () {
+      debug x => _1;                       // in scope 0 at $DIR/cycle.rs:9:10: 9:15
+      debug y => _2;                       // in scope 0 at $DIR/cycle.rs:9:22: 9:27
+      debug z => _3;                       // in scope 0 at $DIR/cycle.rs:9:34: 9:39
+      let mut _0: ();                      // return place in scope 0 at $DIR/cycle.rs:9:46: 9:46
+      let mut _4: ();                      // in scope 0 at $DIR/cycle.rs:9:1: 18:2
+      let mut _5: bool;                    // in scope 0 at $DIR/cycle.rs:12:11: 12:17
+      let _6: i32;                         // in scope 0 at $DIR/cycle.rs:13:13: 13:17
+      let mut _7: i32;                     // in scope 0 at $DIR/cycle.rs:14:13: 14:14
+      let mut _8: i32;                     // in scope 0 at $DIR/cycle.rs:15:13: 15:14
+      let mut _9: i32;                     // in scope 0 at $DIR/cycle.rs:16:13: 16:17
+      let mut _10: !;                      // in scope 0 at $DIR/cycle.rs:12:5: 17:6
+      let _11: ();                         // in scope 0 at $DIR/cycle.rs:12:5: 17:6
+      let mut _12: !;                      // in scope 0 at $DIR/cycle.rs:12:5: 17:6
+      scope 1 {
+          debug temp => _6;                // in scope 1 at $DIR/cycle.rs:13:13: 13:17
+      }
+  
+      bb0: {
+          goto -> bb1;                     // scope 0 at $DIR/cycle.rs:12:5: 17:6
+      }
+  
+      bb1: {
+          StorageLive(_5);                 // scope 0 at $DIR/cycle.rs:12:11: 12:17
+          _5 = cond() -> bb2;              // scope 0 at $DIR/cycle.rs:12:11: 12:17
+                                           // mir::Constant
+                                           // + span: $DIR/cycle.rs:12:11: 12:15
+                                           // + literal: Const { ty: fn() -> bool {cond}, val: Value(Scalar(<ZST>)) }
+      }
+  
+      bb2: {
+          switchInt(move _5) -> [false: bb4, otherwise: bb3]; // scope 0 at $DIR/cycle.rs:12:11: 12:17
+      }
+  
+      bb3: {
+          StorageLive(_6);                 // scope 0 at $DIR/cycle.rs:13:13: 13:17
+-         _6 = _3;                         // scope 0 at $DIR/cycle.rs:13:20: 13:21
++         nop;                             // scope 0 at $DIR/cycle.rs:13:20: 13:21
+          StorageLive(_7);                 // scope 1 at $DIR/cycle.rs:14:13: 14:14
+-         _7 = _2;                         // scope 1 at $DIR/cycle.rs:14:13: 14:14
+-         _3 = move _7;                    // scope 1 at $DIR/cycle.rs:14:9: 14:14
++         nop;                             // scope 1 at $DIR/cycle.rs:14:13: 14:14
++         nop;                             // scope 1 at $DIR/cycle.rs:14:9: 14:14
+          StorageDead(_7);                 // scope 1 at $DIR/cycle.rs:14:13: 14:14
+          StorageLive(_8);                 // scope 1 at $DIR/cycle.rs:15:13: 15:14
+-         _8 = _1;                         // scope 1 at $DIR/cycle.rs:15:13: 15:14
+-         _2 = move _8;                    // scope 1 at $DIR/cycle.rs:15:9: 15:14
++         nop;                             // scope 1 at $DIR/cycle.rs:15:13: 15:14
++         nop;                             // scope 1 at $DIR/cycle.rs:15:9: 15:14
+          StorageDead(_8);                 // scope 1 at $DIR/cycle.rs:15:13: 15:14
+          StorageLive(_9);                 // scope 1 at $DIR/cycle.rs:16:13: 16:17
+-         _9 = _6;                         // scope 1 at $DIR/cycle.rs:16:13: 16:17
+-         _1 = move _9;                    // scope 1 at $DIR/cycle.rs:16:9: 16:17
++         nop;                             // scope 1 at $DIR/cycle.rs:16:13: 16:17
++         nop;                             // scope 1 at $DIR/cycle.rs:16:9: 16:17
+          StorageDead(_9);                 // scope 1 at $DIR/cycle.rs:16:16: 16:17
+-         _4 = const ();                   // scope 0 at $DIR/cycle.rs:12:18: 17:6
++         nop;                             // scope 0 at $DIR/cycle.rs:12:18: 17:6
+          StorageDead(_6);                 // scope 0 at $DIR/cycle.rs:17:5: 17:6
+          StorageDead(_5);                 // scope 0 at $DIR/cycle.rs:17:5: 17:6
+          goto -> bb1;                     // scope 0 at $DIR/cycle.rs:12:5: 17:6
+      }
+  
+      bb4: {
+          StorageLive(_11);                // scope 0 at $DIR/cycle.rs:12:5: 17:6
+          _0 = const ();                   // scope 0 at $DIR/cycle.rs:12:5: 17:6
+          StorageDead(_11);                // scope 0 at $DIR/cycle.rs:17:5: 17:6
+          StorageDead(_5);                 // scope 0 at $DIR/cycle.rs:17:5: 17:6
+          return;                          // scope 0 at $DIR/cycle.rs:18:2: 18:2
+      }
+  }
+  
diff --git a/src/test/mir-opt/dead-store-elimination/cycle.rs b/src/test/mir-opt/dead-store-elimination/cycle.rs
new file mode 100644
index 00000000000..b35ce0bcb5a
--- /dev/null
+++ b/src/test/mir-opt/dead-store-elimination/cycle.rs
@@ -0,0 +1,22 @@
+// unit-test: DeadStoreElimination
+
+#[inline(never)]
+fn cond() -> bool {
+    false
+}
+
+// EMIT_MIR cycle.cycle.DeadStoreElimination.diff
+fn cycle(mut x: i32, mut y: i32, mut z: i32) {
+    // This example is interesting because the non-transitive version of `MaybeLiveLocals` would
+    // report that *all* of these stores are live.
+    while cond() {
+        let temp = z;
+        z = y;
+        y = x;
+        x = temp;
+    }
+}
+
+fn main() {
+    cycle(1, 2, 3);
+}
diff --git a/src/test/mir-opt/dead-store-elimination/provenance_soundness.pointer_to_int.DeadStoreElimination.diff b/src/test/mir-opt/dead-store-elimination/provenance_soundness.pointer_to_int.DeadStoreElimination.diff
new file mode 100644
index 00000000000..2250159c816
--- /dev/null
+++ b/src/test/mir-opt/dead-store-elimination/provenance_soundness.pointer_to_int.DeadStoreElimination.diff
@@ -0,0 +1,35 @@
+- // MIR for `pointer_to_int` before DeadStoreElimination
++ // MIR for `pointer_to_int` after DeadStoreElimination
+  
+  fn pointer_to_int(_1: *mut i32) -> () {
+      debug p => _1;                       // in scope 0 at $DIR/provenance_soundness.rs:7:19: 7:20
+      let mut _0: ();                      // return place in scope 0 at $DIR/provenance_soundness.rs:7:32: 7:32
+      let _2: usize;                       // in scope 0 at $DIR/provenance_soundness.rs:8:9: 8:11
+      let mut _3: *mut i32;                // in scope 0 at $DIR/provenance_soundness.rs:8:14: 8:15
+      let mut _5: *mut i32;                // in scope 0 at $DIR/provenance_soundness.rs:9:14: 9:15
+      scope 1 {
+          debug _x => _2;                  // in scope 1 at $DIR/provenance_soundness.rs:8:9: 8:11
+          let _4: isize;                   // in scope 1 at $DIR/provenance_soundness.rs:9:9: 9:11
+          scope 2 {
+              debug _y => _4;              // in scope 2 at $DIR/provenance_soundness.rs:9:9: 9:11
+          }
+      }
+  
+      bb0: {
+          StorageLive(_2);                 // scope 0 at $DIR/provenance_soundness.rs:8:9: 8:11
+          StorageLive(_3);                 // scope 0 at $DIR/provenance_soundness.rs:8:14: 8:15
+          _3 = _1;                         // scope 0 at $DIR/provenance_soundness.rs:8:14: 8:15
+          _2 = move _3 as usize (Misc);    // scope 0 at $DIR/provenance_soundness.rs:8:14: 8:24
+          StorageDead(_3);                 // scope 0 at $DIR/provenance_soundness.rs:8:23: 8:24
+          StorageLive(_4);                 // scope 1 at $DIR/provenance_soundness.rs:9:9: 9:11
+          StorageLive(_5);                 // scope 1 at $DIR/provenance_soundness.rs:9:14: 9:15
+          _5 = _1;                         // scope 1 at $DIR/provenance_soundness.rs:9:14: 9:15
+          _4 = move _5 as isize (Misc);    // scope 1 at $DIR/provenance_soundness.rs:9:14: 9:24
+          StorageDead(_5);                 // scope 1 at $DIR/provenance_soundness.rs:9:23: 9:24
+          _0 = const ();                   // scope 0 at $DIR/provenance_soundness.rs:7:32: 10:2
+          StorageDead(_4);                 // scope 1 at $DIR/provenance_soundness.rs:10:1: 10:2
+          StorageDead(_2);                 // scope 0 at $DIR/provenance_soundness.rs:10:1: 10:2
+          return;                          // scope 0 at $DIR/provenance_soundness.rs:10:2: 10:2
+      }
+  }
+  
diff --git a/src/test/mir-opt/dead-store-elimination/provenance_soundness.retags.DeadStoreElimination.diff b/src/test/mir-opt/dead-store-elimination/provenance_soundness.retags.DeadStoreElimination.diff
new file mode 100644
index 00000000000..0bfffb6dca3
--- /dev/null
+++ b/src/test/mir-opt/dead-store-elimination/provenance_soundness.retags.DeadStoreElimination.diff
@@ -0,0 +1,14 @@
+- // MIR for `retags` before DeadStoreElimination
++ // MIR for `retags` after DeadStoreElimination
+  
+  fn retags(_1: &mut i32) -> () {
+      debug _r => _1;                      // in scope 0 at $DIR/provenance_soundness.rs:13:11: 13:13
+      let mut _0: ();                      // return place in scope 0 at $DIR/provenance_soundness.rs:13:25: 13:25
+  
+      bb0: {
+          Retag([fn entry] _1);            // scope 0 at $DIR/provenance_soundness.rs:13:1: 13:27
+          _0 = const ();                   // scope 0 at $DIR/provenance_soundness.rs:13:25: 13:27
+          return;                          // scope 0 at $DIR/provenance_soundness.rs:13:27: 13:27
+      }
+  }
+  
diff --git a/src/test/mir-opt/dead-store-elimination/provenance_soundness.rs b/src/test/mir-opt/dead-store-elimination/provenance_soundness.rs
new file mode 100644
index 00000000000..11314e99098
--- /dev/null
+++ b/src/test/mir-opt/dead-store-elimination/provenance_soundness.rs
@@ -0,0 +1,18 @@
+// unit-test: DeadStoreElimination
+// compile-flags: -Zmir-emit-retag
+
+// Test that we don't remove pointer to int casts or retags
+
+// EMIT_MIR provenance_soundness.pointer_to_int.DeadStoreElimination.diff
+fn pointer_to_int(p: *mut i32) {
+    let _x = p as usize;
+    let _y = p as isize;
+}
+
+// EMIT_MIR provenance_soundness.retags.DeadStoreElimination.diff
+fn retags(_r: &mut i32) {}
+
+fn main() {
+    pointer_to_int(&mut 5 as *mut _);
+    retags(&mut 5);
+}
diff --git a/src/test/mir-opt/dest-prop/copy_propagation_arg.arg_src.DestinationPropagation.diff b/src/test/mir-opt/dest-prop/copy_propagation_arg.arg_src.DestinationPropagation.diff
index a5d80e75053..b67e6cb4708 100644
--- a/src/test/mir-opt/dest-prop/copy_propagation_arg.arg_src.DestinationPropagation.diff
+++ b/src/test/mir-opt/dest-prop/copy_propagation_arg.arg_src.DestinationPropagation.diff
@@ -2,7 +2,7 @@
 + // MIR for `arg_src` after DestinationPropagation
   
   fn arg_src(_1: i32) -> i32 {
-      debug x => _1;                       // in scope 0 at $DIR/copy_propagation_arg.rs:27:12: 27:17
+      debug x => const 123_i32;            // in scope 0 at $DIR/copy_propagation_arg.rs:27:12: 27:17
       let mut _0: i32;                     // return place in scope 0 at $DIR/copy_propagation_arg.rs:27:27: 27:30
       let _2: i32;                         // in scope 0 at $DIR/copy_propagation_arg.rs:28:9: 28:10
       scope 1 {
diff --git a/src/test/mir-opt/dest-prop/copy_propagation_arg.bar.DestinationPropagation.diff b/src/test/mir-opt/dest-prop/copy_propagation_arg.bar.DestinationPropagation.diff
index 383f00f0125..1b8772b6a68 100644
--- a/src/test/mir-opt/dest-prop/copy_propagation_arg.bar.DestinationPropagation.diff
+++ b/src/test/mir-opt/dest-prop/copy_propagation_arg.bar.DestinationPropagation.diff
@@ -2,7 +2,7 @@
 + // MIR for `bar` after DestinationPropagation
   
   fn bar(_1: u8) -> () {
-      debug x => _1;                       // in scope 0 at $DIR/copy_propagation_arg.rs:15:8: 15:13
+      debug x => const 5_u8;               // in scope 0 at $DIR/copy_propagation_arg.rs:15:8: 15:13
       let mut _0: ();                      // return place in scope 0 at $DIR/copy_propagation_arg.rs:15:19: 15:19
       let _2: u8;                          // in scope 0 at $DIR/copy_propagation_arg.rs:16:5: 16:13
       let mut _3: u8;                      // in scope 0 at $DIR/copy_propagation_arg.rs:16:11: 16:12