compiler/rustc_mir_dataflow/src/impls/liveness.rs

   1 use rustc_index::bit_set::{BitSet, ChunkedBitSet};
   2 use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
   3 use rustc_middle::mir::{self, Local, Location, Place, StatementKind};
   4
   5 use crate::{Analysis, AnalysisDomain, Backward, CallReturnPlaces, GenKill, GenKillAnalysis};
   6
   7 /// A [live-variable dataflow analysis][liveness].
   8 ///
   9 /// This analysis considers references as being used only at the point of the
  10 /// borrow. In other words, this analysis does not track uses because of references that already
  11 /// exist. See [this `mir-dataflow` test][flow-test] for an example. You almost never want to use
  12 /// this analysis without also looking at the results of [`MaybeBorrowedLocals`].
  13 ///
  14 /// ## Field-(in)sensitivity
  15 ///
  16 /// As the name suggests, this analysis is field insensitive. If a projection of a variable `x` is
  17 /// assigned to (e.g. `x.0 = 42`), it does not "define" `x` as far as liveness is concerned. In fact,
  18 /// such an assignment is currently marked as a "use" of `x` in an attempt to be maximally
  19 /// conservative.
  20 ///
  21 /// [`MaybeBorrowedLocals`]: super::MaybeBorrowedLocals
  22 /// [flow-test]: https://github.com/rust-lang/rust/blob/a08c47310c7d49cbdc5d7afb38408ba519967ecd/src/test/ui/mir-dataflow/liveness-ptr.rs
  23 /// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
  24 pub struct MaybeLiveLocals;
  25
  26 impl<'tcx> AnalysisDomain<'tcx> for MaybeLiveLocals {
  27     type Domain = ChunkedBitSet<Local>;
  28     type Direction = Backward;
  29
  30     const NAME: &'static str = "liveness";
  31
  32     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
  33         // bottom = not live
  34         ChunkedBitSet::new_empty(body.local_decls.len())
  35     }
  36
  37     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
  38         // No variables are live until we observe a use
  39     }
  40 }
  41
  42 impl<'tcx> GenKillAnalysis<'tcx> for MaybeLiveLocals {
  43     type Idx = Local;
  44
  45     fn statement_effect(
  46         &self,
  47         trans: &mut impl GenKill<Self::Idx>,
  48         statement: &mir::Statement<'tcx>,
  49         location: Location,
  50     ) {
  51         TransferFunction(trans).visit_statement(statement, location);
  52     }
  53
  54     fn terminator_effect(
  55         &self,
  56         trans: &mut impl GenKill<Self::Idx>,
  57         terminator: &mir::Terminator<'tcx>,
  58         location: Location,
  59     ) {
  60         TransferFunction(trans).visit_terminator(terminator, location);
  61     }
  62
  63     fn call_return_effect(
  64         &self,
  65         trans: &mut impl GenKill<Self::Idx>,
  66         _block: mir::BasicBlock,
  67         return_places: CallReturnPlaces<'_, 'tcx>,
  68     ) {
  69         return_places.for_each(|place| {
  70             if let Some(local) = place.as_local() {
  71                 trans.kill(local);
  72             }
  73         });
  74     }
  75
  76     fn yield_resume_effect(
  77         &self,
  78         trans: &mut impl GenKill<Self::Idx>,
  79         _resume_block: mir::BasicBlock,
  80         resume_place: mir::Place<'tcx>,
  81     ) {
  82         YieldResumeEffect(trans).visit_place(
  83             &resume_place,
  84             PlaceContext::MutatingUse(MutatingUseContext::Yield),
  85             Location::START,
  86         )
  87     }
  88 }
  89
  90 struct TransferFunction<'a, T>(&'a mut T);
  91
  92 impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T>
  93 where
  94     T: GenKill<Local>,
  95 {
  96     fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
  97         if let PlaceContext::MutatingUse(MutatingUseContext::Yield) = context {
  98             // The resume place is evaluated and assigned to only after generator resumes, so its
  99             // effect is handled separately in `yield_resume_effect`.
 100             return;
 101         }
 102
 103         match DefUse::for_place(*place, context) {
 104             Some(DefUse::Def) => {
 105                 if let PlaceContext::MutatingUse(
 106                     MutatingUseContext::Call | MutatingUseContext::AsmOutput,
 107                 ) = context
 108                 {
 109                     // For the associated terminators, this is only a `Def` when the terminator returns
 110                     // "successfully." As such, we handle this case separately in `call_return_effect`
 111                     // above. However, if the place looks like `*_5`, this is still unconditionally a use of
 112                     // `_5`.
 113                 } else {
 114                     self.0.kill(place.local);
 115                 }
 116             }
 117             Some(DefUse::Use) => self.0.gen(place.local),
 118             None => {}
 119         }
 120
 121         self.visit_projection(place.as_ref(), context, location);
 122     }
 123
 124     fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
 125         DefUse::apply(self.0, local.into(), context);
 126     }
 127 }
 128
 129 struct YieldResumeEffect<'a, T>(&'a mut T);
 130
 131 impl<'tcx, T> Visitor<'tcx> for YieldResumeEffect<'_, T>
 132 where
 133     T: GenKill<Local>,
 134 {
 135     fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
 136         DefUse::apply(self.0, *place, context);
 137         self.visit_projection(place.as_ref(), context, location);
 138     }
 139
 140     fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
 141         DefUse::apply(self.0, local.into(), context);
 142     }
 143 }
 144
 145 #[derive(Eq, PartialEq, Clone)]
 146 enum DefUse {
 147     Def,
 148     Use,
 149 }
 150
 151 impl DefUse {
 152     fn apply(trans: &mut impl GenKill<Local>, place: Place<'_>, context: PlaceContext) {
 153         match DefUse::for_place(place, context) {
 154             Some(DefUse::Def) => trans.kill(place.local),
 155             Some(DefUse::Use) => trans.gen(place.local),
 156             None => {}
 157         }
 158     }
 159
 160     fn for_place(place: Place<'_>, context: PlaceContext) -> Option<DefUse> {
 161         match context {
 162             PlaceContext::NonUse(_) => None,
 163
 164             PlaceContext::MutatingUse(
 165                 MutatingUseContext::Call
 166                 | MutatingUseContext::Yield
 167                 | MutatingUseContext::AsmOutput
 168                 | MutatingUseContext::Store
 169                 | MutatingUseContext::Deinit,
 170             ) => {
 171                 if place.is_indirect() {
 172                     // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a
 173                     // use.
 174                     Some(DefUse::Use)
 175                 } else if place.projection.is_empty() {
 176                     Some(DefUse::Def)
 177                 } else {
 178                     None
 179                 }
 180             }
 181
 182             // Setting the discriminant is not a use because it does no reading, but it is also not
 183             // a def because it does not overwrite the whole place
 184             PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => {
 185                 place.is_indirect().then_some(DefUse::Use)
 186             }
 187
 188             // All other contexts are uses...
 189             PlaceContext::MutatingUse(
 190                 MutatingUseContext::AddressOf
 191                 | MutatingUseContext::Borrow
 192                 | MutatingUseContext::Drop
 193                 | MutatingUseContext::Retag,
 194             )
 195             | PlaceContext::NonMutatingUse(
 196                 NonMutatingUseContext::AddressOf
 197                 | NonMutatingUseContext::Copy
 198                 | NonMutatingUseContext::Inspect
 199                 | NonMutatingUseContext::Move
 200                 | NonMutatingUseContext::ShallowBorrow
 201                 | NonMutatingUseContext::SharedBorrow
 202                 | NonMutatingUseContext::UniqueBorrow,
 203             ) => Some(DefUse::Use),
 204
 205             PlaceContext::MutatingUse(MutatingUseContext::Projection)
 206             | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
 207                 unreachable!("A projection could be a def or a use and must be handled separately")
 208             }
 209         }
 210     }
 211 }
 212
 213 /// Like `MaybeLiveLocals`, but does not mark locals as live if they are used in a dead assignment.
 214 ///
 215 /// This is basically written for dead store elimination and nothing else.
 216 ///
 217 /// All of the caveats of `MaybeLiveLocals` apply.
 218 pub struct MaybeTransitiveLiveLocals<'a> {
 219     always_live: &'a BitSet<Local>,
 220 }
 221
 222 impl<'a> MaybeTransitiveLiveLocals<'a> {
 223     /// The `always_alive` set is the set of locals to which all stores should unconditionally be
 224     /// considered live.
 225     ///
 226     /// This should include at least all locals that are ever borrowed.
 227     pub fn new(always_live: &'a BitSet<Local>) -> Self {
 228         MaybeTransitiveLiveLocals { always_live }
 229     }
 230 }
 231
 232 impl<'a, 'tcx> AnalysisDomain<'tcx> for MaybeTransitiveLiveLocals<'a> {
 233     type Domain = ChunkedBitSet<Local>;
 234     type Direction = Backward;
 235
 236     const NAME: &'static str = "transitive liveness";
 237
 238     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
 239         // bottom = not live
 240         ChunkedBitSet::new_empty(body.local_decls.len())
 241     }
 242
 243     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
 244         // No variables are live until we observe a use
 245     }
 246 }
 247
 248 impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
 249     fn apply_statement_effect(
 250         &self,
 251         trans: &mut Self::Domain,
 252         statement: &mir::Statement<'tcx>,
 253         location: Location,
 254     ) {
 255         // Compute the place that we are storing to, if any
 256         let destination = match &statement.kind {
 257             StatementKind::Assign(assign) => {
 258                 if assign.1.is_safe_to_remove() {
 259                     Some(assign.0)
 260                 } else {
 261                     None
 262                 }
 263             }
 264             StatementKind::SetDiscriminant { place, .. } | StatementKind::Deinit(place) => {
 265                 Some(**place)
 266             }
 267             StatementKind::FakeRead(_)
 268             | StatementKind::StorageLive(_)
 269             | StatementKind::StorageDead(_)
 270             | StatementKind::Retag(..)
 271             | StatementKind::AscribeUserType(..)
 272             | StatementKind::Coverage(..)
 273             | StatementKind::Intrinsic(..)
 274             | StatementKind::ConstEvalCounter
 275             | StatementKind::Nop => None,
 276         };
 277         if let Some(destination) = destination {
 278             if !destination.is_indirect()
 279                 && !trans.contains(destination.local)
 280                 && !self.always_live.contains(destination.local)
 281             {
 282                 // This store is dead
 283                 return;
 284             }
 285         }
 286         TransferFunction(trans).visit_statement(statement, location);
 287     }
 288
 289     fn apply_terminator_effect(
 290         &self,
 291         trans: &mut Self::Domain,
 292         terminator: &mir::Terminator<'tcx>,
 293         location: Location,
 294     ) {
 295         TransferFunction(trans).visit_terminator(terminator, location);
 296     }
 297
 298     fn apply_call_return_effect(
 299         &self,
 300         trans: &mut Self::Domain,
 301         _block: mir::BasicBlock,
 302         return_places: CallReturnPlaces<'_, 'tcx>,
 303     ) {
 304         return_places.for_each(|place| {
 305             if let Some(local) = place.as_local() {
 306                 trans.remove(local);
 307             }
 308         });
 309     }
 310
 311     fn apply_yield_resume_effect(
 312         &self,
 313         trans: &mut Self::Domain,
 314         _resume_block: mir::BasicBlock,
 315         resume_place: mir::Place<'tcx>,
 316     ) {
 317         YieldResumeEffect(trans).visit_place(
 318             &resume_place,
 319             PlaceContext::MutatingUse(MutatingUseContext::Yield),
 320             Location::START,
 321         )
 322     }
 323 }