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 MaybeLiveLocals {
  27     fn transfer_function<'a, T>(&self, trans: &'a mut T) -> TransferFunction<'a, T> {
  28         TransferFunction(trans)
  29     }
  30 }
  31
  32 impl<'tcx> AnalysisDomain<'tcx> for MaybeLiveLocals {
  33     type Domain = ChunkedBitSet<Local>;
  34     type Direction = Backward;
  35
  36     const NAME: &'static str = "liveness";
  37
  38     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
  39         // bottom = not live
  40         ChunkedBitSet::new_empty(body.local_decls.len())
  41     }
  42
  43     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
  44         // No variables are live until we observe a use
  45     }
  46 }
  47
  48 impl<'tcx> GenKillAnalysis<'tcx> for MaybeLiveLocals {
  49     type Idx = Local;
  50
  51     fn statement_effect(
  52         &self,
  53         trans: &mut impl GenKill<Self::Idx>,
  54         statement: &mir::Statement<'tcx>,
  55         location: Location,
  56     ) {
  57         self.transfer_function(trans).visit_statement(statement, location);
  58     }
  59
  60     fn terminator_effect(
  61         &self,
  62         trans: &mut impl GenKill<Self::Idx>,
  63         terminator: &mir::Terminator<'tcx>,
  64         location: Location,
  65     ) {
  66         self.transfer_function(trans).visit_terminator(terminator, location);
  67     }
  68
  69     fn call_return_effect(
  70         &self,
  71         trans: &mut impl GenKill<Self::Idx>,
  72         _block: mir::BasicBlock,
  73         return_places: CallReturnPlaces<'_, 'tcx>,
  74     ) {
  75         return_places.for_each(|place| {
  76             if let Some(local) = place.as_local() {
  77                 trans.kill(local);
  78             }
  79         });
  80     }
  81
  82     fn yield_resume_effect(
  83         &self,
  84         trans: &mut impl GenKill<Self::Idx>,
  85         _resume_block: mir::BasicBlock,
  86         resume_place: mir::Place<'tcx>,
  87     ) {
  88         if let Some(local) = resume_place.as_local() {
  89             trans.kill(local);
  90         }
  91     }
  92 }
  93
  94 struct TransferFunction<'a, T>(&'a mut T);
  95
  96 impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T>
  97 where
  98     T: GenKill<Local>,
  99 {
 100     fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
 101         let local = place.local;
 102
 103         // We purposefully do not call `super_place` here to avoid calling `visit_local` for this
 104         // place with one of the `Projection` variants of `PlaceContext`.
 105         self.visit_projection(place.as_ref(), context, location);
 106
 107         match DefUse::for_place(*place, context) {
 108             Some(DefUse::Def) => self.0.kill(local),
 109             Some(DefUse::Use) => self.0.gen(local),
 110             None => {}
 111         }
 112     }
 113
 114     fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) {
 115         // Because we do not call `super_place` above, `visit_local` is only called for locals that
 116         // do not appear as part of  a `Place` in the MIR. This handles cases like the implicit use
 117         // of the return place in a `Return` terminator or the index in an `Index` projection.
 118         match DefUse::for_place(local.into(), context) {
 119             Some(DefUse::Def) => self.0.kill(local),
 120             Some(DefUse::Use) => self.0.gen(local),
 121             None => {}
 122         }
 123     }
 124 }
 125
 126 #[derive(Eq, PartialEq, Clone)]
 127 enum DefUse {
 128     Def,
 129     Use,
 130 }
 131
 132 impl DefUse {
 133     fn for_place<'tcx>(place: Place<'tcx>, context: PlaceContext) -> Option<DefUse> {
 134         match context {
 135             PlaceContext::NonUse(_) => None,
 136
 137             PlaceContext::MutatingUse(MutatingUseContext::Store | MutatingUseContext::Deinit) => {
 138                 if place.is_indirect() {
 139                     // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a
 140                     // use.
 141                     Some(DefUse::Use)
 142                 } else if place.projection.is_empty() {
 143                     Some(DefUse::Def)
 144                 } else {
 145                     None
 146                 }
 147             }
 148
 149             // Setting the discriminant is not a use because it does no reading, but it is also not
 150             // a def because it does not overwrite the whole place
 151             PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => {
 152                 place.is_indirect().then_some(DefUse::Use)
 153             }
 154
 155             // For the associated terminators, this is only a `Def` when the terminator returns
 156             // "successfully." As such, we handle this case separately in `call_return_effect`
 157             // above. However, if the place looks like `*_5`, this is still unconditionally a use of
 158             // `_5`.
 159             PlaceContext::MutatingUse(
 160                 MutatingUseContext::Call
 161                 | MutatingUseContext::Yield
 162                 | MutatingUseContext::AsmOutput,
 163             ) => place.is_indirect().then_some(DefUse::Use),
 164
 165             // All other contexts are uses...
 166             PlaceContext::MutatingUse(
 167                 MutatingUseContext::AddressOf
 168                 | MutatingUseContext::Borrow
 169                 | MutatingUseContext::Drop
 170                 | MutatingUseContext::Retag,
 171             )
 172             | PlaceContext::NonMutatingUse(
 173                 NonMutatingUseContext::AddressOf
 174                 | NonMutatingUseContext::Copy
 175                 | NonMutatingUseContext::Inspect
 176                 | NonMutatingUseContext::Move
 177                 | NonMutatingUseContext::ShallowBorrow
 178                 | NonMutatingUseContext::SharedBorrow
 179                 | NonMutatingUseContext::UniqueBorrow,
 180             ) => Some(DefUse::Use),
 181
 182             PlaceContext::MutatingUse(MutatingUseContext::Projection)
 183             | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
 184                 unreachable!("A projection could be a def or a use and must be handled separately")
 185             }
 186         }
 187     }
 188 }
 189
 190 /// Like `MaybeLiveLocals`, but does not mark locals as live if they are used in a dead assignment.
 191 ///
 192 /// This is basically written for dead store elimination and nothing else.
 193 ///
 194 /// All of the caveats of `MaybeLiveLocals` apply.
 195 pub struct MaybeTransitiveLiveLocals<'a> {
 196     always_live: &'a BitSet<Local>,
 197 }
 198
 199 impl<'a> MaybeTransitiveLiveLocals<'a> {
 200     /// The `always_alive` set is the set of locals to which all stores should unconditionally be
 201     /// considered live.
 202     ///
 203     /// This should include at least all locals that are ever borrowed.
 204     pub fn new(always_live: &'a BitSet<Local>) -> Self {
 205         MaybeTransitiveLiveLocals { always_live }
 206     }
 207 }
 208
 209 impl<'a, 'tcx> AnalysisDomain<'tcx> for MaybeTransitiveLiveLocals<'a> {
 210     type Domain = ChunkedBitSet<Local>;
 211     type Direction = Backward;
 212
 213     const NAME: &'static str = "transitive liveness";
 214
 215     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
 216         // bottom = not live
 217         ChunkedBitSet::new_empty(body.local_decls.len())
 218     }
 219
 220     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
 221         // No variables are live until we observe a use
 222     }
 223 }
 224
 225 struct TransferWrapper<'a>(&'a mut ChunkedBitSet<Local>);
 226
 227 impl<'a> GenKill<Local> for TransferWrapper<'a> {
 228     fn gen(&mut self, l: Local) {
 229         self.0.insert(l);
 230     }
 231
 232     fn kill(&mut self, l: Local) {
 233         self.0.remove(l);
 234     }
 235 }
 236
 237 impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
 238     fn apply_statement_effect(
 239         &self,
 240         trans: &mut Self::Domain,
 241         statement: &mir::Statement<'tcx>,
 242         location: Location,
 243     ) {
 244         // Compute the place that we are storing to, if any
 245         let destination = match &statement.kind {
 246             StatementKind::Assign(assign) => {
 247                 if assign.1.is_safe_to_remove() {
 248                     Some(assign.0)
 249                 } else {
 250                     None
 251                 }
 252             }
 253             StatementKind::SetDiscriminant { place, .. } | StatementKind::Deinit(place) => {
 254                 Some(**place)
 255             }
 256             StatementKind::FakeRead(_)
 257             | StatementKind::StorageLive(_)
 258             | StatementKind::StorageDead(_)
 259             | StatementKind::Retag(..)
 260             | StatementKind::AscribeUserType(..)
 261             | StatementKind::Coverage(..)
 262             | StatementKind::CopyNonOverlapping(..)
 263             | StatementKind::Nop => None,
 264         };
 265         if let Some(destination) = destination {
 266             if !destination.is_indirect()
 267                 && !trans.contains(destination.local)
 268                 && !self.always_live.contains(destination.local)
 269             {
 270                 // This store is dead
 271                 return;
 272             }
 273         }
 274         TransferFunction(&mut TransferWrapper(trans)).visit_statement(statement, location);
 275     }
 276
 277     fn apply_terminator_effect(
 278         &self,
 279         trans: &mut Self::Domain,
 280         terminator: &mir::Terminator<'tcx>,
 281         location: Location,
 282     ) {
 283         TransferFunction(&mut TransferWrapper(trans)).visit_terminator(terminator, location);
 284     }
 285
 286     fn apply_call_return_effect(
 287         &self,
 288         trans: &mut Self::Domain,
 289         _block: mir::BasicBlock,
 290         return_places: CallReturnPlaces<'_, 'tcx>,
 291     ) {
 292         return_places.for_each(|place| {
 293             if let Some(local) = place.as_local() {
 294                 trans.remove(local);
 295             }
 296         });
 297     }
 298
 299     fn apply_yield_resume_effect(
 300         &self,
 301         trans: &mut Self::Domain,
 302         _resume_block: mir::BasicBlock,
 303         resume_place: mir::Place<'tcx>,
 304     ) {
 305         if let Some(local) = resume_place.as_local() {
 306             trans.remove(local);
 307         }
 308     }
 309 }