compiler/rustc_mir_dataflow/src/impls/liveness.rs

   1 use rustc_index::bit_set::BitSet;
   2 use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
   3 use rustc_middle::mir::{self, Local, Location};
   4
   5 use crate::{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 = BitSet<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         BitSet::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 mir::Place { projection, local } = *place;
 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(context) {
 108             // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a use.
 109             Some(_) if place.is_indirect() => self.0.gen(local),
 110
 111             Some(DefUse::Def) if projection.is_empty() => self.0.kill(local),
 112             Some(DefUse::Use) => self.0.gen(local),
 113             _ => {}
 114         }
 115     }
 116
 117     fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) {
 118         // Because we do not call `super_place` above, `visit_local` is only called for locals that
 119         // do not appear as part of  a `Place` in the MIR. This handles cases like the implicit use
 120         // of the return place in a `Return` terminator or the index in an `Index` projection.
 121         match DefUse::for_place(context) {
 122             Some(DefUse::Def) => self.0.kill(local),
 123             Some(DefUse::Use) => self.0.gen(local),
 124             _ => {}
 125         }
 126     }
 127 }
 128
 129 #[derive(Eq, PartialEq, Clone)]
 130 enum DefUse {
 131     Def,
 132     Use,
 133 }
 134
 135 impl DefUse {
 136     fn for_place(context: PlaceContext) -> Option<DefUse> {
 137         match context {
 138             PlaceContext::NonUse(_) => None,
 139
 140             PlaceContext::MutatingUse(MutatingUseContext::Store | MutatingUseContext::Deinit) => {
 141                 Some(DefUse::Def)
 142             }
 143
 144             // Setting the discriminant is not a use because it does no reading, but it is also not
 145             // a def because it does not overwrite the whole place
 146             PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => None,
 147
 148             // `MutatingUseContext::Call` and `MutatingUseContext::Yield` indicate that this is the
 149             // destination place for a `Call` return or `Yield` resume respectively. Since this is
 150             // only a `Def` when the function returns successfully, we handle this case separately
 151             // in `call_return_effect` above.
 152             PlaceContext::MutatingUse(
 153                 MutatingUseContext::Call
 154                 | MutatingUseContext::AsmOutput
 155                 | MutatingUseContext::Yield,
 156             ) => None,
 157
 158             // All other contexts are uses...
 159             PlaceContext::MutatingUse(
 160                 MutatingUseContext::AddressOf
 161                 | MutatingUseContext::Borrow
 162                 | MutatingUseContext::Drop
 163                 | MutatingUseContext::Retag,
 164             )
 165             | PlaceContext::NonMutatingUse(
 166                 NonMutatingUseContext::AddressOf
 167                 | NonMutatingUseContext::Copy
 168                 | NonMutatingUseContext::Inspect
 169                 | NonMutatingUseContext::Move
 170                 | NonMutatingUseContext::ShallowBorrow
 171                 | NonMutatingUseContext::SharedBorrow
 172                 | NonMutatingUseContext::UniqueBorrow,
 173             ) => Some(DefUse::Use),
 174
 175             PlaceContext::MutatingUse(MutatingUseContext::Projection)
 176             | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
 177                 unreachable!("A projection could be a def or a use and must be handled separately")
 178             }
 179         }
 180     }
 181 }