-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, Location, Place, StatementKind};
-use crate::{AnalysisDomain, Backward, CallReturnPlaces, GenKill, GenKillAnalysis};
+use crate::{Analysis, AnalysisDomain, Backward, CallReturnPlaces, GenKill, GenKillAnalysis};
/// A [live-variable dataflow analysis][liveness].
///
}
impl<'tcx> AnalysisDomain<'tcx> for MaybeLiveLocals {
- type Domain = BitSet<Local>;
+ type Domain = ChunkedBitSet<Local>;
type Direction = Backward;
const NAME: &'static str = "liveness";
fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
// bottom = not live
- BitSet::new_empty(body.local_decls.len())
+ ChunkedBitSet::new_empty(body.local_decls.len())
}
fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
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 => {}
}
}
// 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 => {}
}
}
}
}
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(
}
}
}
+
+/// 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> {
+ always_live: &'a BitSet<Local>,
+}
+
+impl<'a> MaybeTransitiveLiveLocals<'a> {
+ /// 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>) -> Self {
+ MaybeTransitiveLiveLocals { always_live }
+ }
+}
+
+impl<'a, 'tcx> AnalysisDomain<'tcx> for MaybeTransitiveLiveLocals<'a> {
+ 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> {
+ 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_safe_to_remove() {
+ Some(assign.0)
+ } else {
+ None
+ }
+ }
+ 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);
+ }
+ }
+}
projects / rustc.git / blobdiff