Auto merge of #97158 - JakobDegen:dse, r=tmiasko,cjgillot

Split dead store elimination off dest prop

This splits off a part of #96451 . I've added this in as its own pass for now, so that it actually runs, can be tested, etc. In the dest prop PR, I'll stop invoking this as its own pass, so that it doesn't get invoked twice.

r? `@tmiasko`

2 files changed, 161 insertions, 22 deletions

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