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, 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 /// ## Enums and `SetDiscriminant`
  22 ///
  23 /// Assigning a literal value to an `enum` (e.g. `Option<i32>`), does not result in a simple
  24 /// assignment of the form `_1 = /*...*/` in the MIR. For example, the following assignment to `x`:
  25 ///
  26 /// ```
  27 /// x = Some(4);
  28 /// ```
  29 ///
  30 /// compiles to this MIR
  31 ///
  32 /// ```
  33 /// ((_1 as Some).0: i32) = const 4_i32;
  34 /// discriminant(_1) = 1;
  35 /// ```
  36 ///
  37 /// However, `MaybeLiveLocals` **does** mark `x` (`_1`) as "killed" after a statement like this.
  38 /// That's because it treats the `SetDiscriminant` operation as a definition of `x`, even though
  39 /// the writes that actually initialized the locals happened earlier.
  40 ///
  41 /// This makes `MaybeLiveLocals` unsuitable for certain classes of optimization normally associated
  42 /// with a live variables analysis, notably dead-store elimination. It's a dirty hack, but it works
  43 /// okay for the generator state transform (currently the main consumuer of this analysis).
  44 ///
  45 /// [`MaybeBorrowedLocals`]: super::MaybeBorrowedLocals
  46 /// [flow-test]: https://github.com/rust-lang/rust/blob/a08c47310c7d49cbdc5d7afb38408ba519967ecd/src/test/ui/mir-dataflow/liveness-ptr.rs
  47 /// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
  48 pub struct MaybeLiveLocals;
  49
  50 impl MaybeLiveLocals {
  51     fn transfer_function<T>(&self, trans: &'a mut T) -> TransferFunction<'a, T> {
  52         TransferFunction(trans)
  53     }
  54 }
  55
  56 impl AnalysisDomain<'tcx> for MaybeLiveLocals {
  57     type Domain = BitSet<Local>;
  58     type Direction = Backward;
  59
  60     const NAME: &'static str = "liveness";
  61
  62     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
  63         // bottom = not live
  64         BitSet::new_empty(body.local_decls.len())
  65     }
  66
  67     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
  68         // No variables are live until we observe a use
  69     }
  70 }
  71
  72 impl GenKillAnalysis<'tcx> for MaybeLiveLocals {
  73     type Idx = Local;
  74
  75     fn statement_effect(
  76         &self,
  77         trans: &mut impl GenKill<Self::Idx>,
  78         statement: &mir::Statement<'tcx>,
  79         location: Location,
  80     ) {
  81         self.transfer_function(trans).visit_statement(statement, location);
  82     }
  83
  84     fn terminator_effect(
  85         &self,
  86         trans: &mut impl GenKill<Self::Idx>,
  87         terminator: &mir::Terminator<'tcx>,
  88         location: Location,
  89     ) {
  90         self.transfer_function(trans).visit_terminator(terminator, location);
  91     }
  92
  93     fn call_return_effect(
  94         &self,
  95         trans: &mut impl GenKill<Self::Idx>,
  96         _block: mir::BasicBlock,
  97         _func: &mir::Operand<'tcx>,
  98         _args: &[mir::Operand<'tcx>],
  99         dest_place: mir::Place<'tcx>,
 100     ) {
 101         if let Some(local) = dest_place.as_local() {
 102             trans.kill(local);
 103         }
 104     }
 105
 106     fn yield_resume_effect(
 107         &self,
 108         trans: &mut impl GenKill<Self::Idx>,
 109         _resume_block: mir::BasicBlock,
 110         resume_place: mir::Place<'tcx>,
 111     ) {
 112         if let Some(local) = resume_place.as_local() {
 113             trans.kill(local);
 114         }
 115     }
 116 }
 117
 118 struct TransferFunction<'a, T>(&'a mut T);
 119
 120 impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T>
 121 where
 122     T: GenKill<Local>,
 123 {
 124     fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
 125         let mir::Place { projection, local } = *place;
 126
 127         // We purposefully do not call `super_place` here to avoid calling `visit_local` for this
 128         // place with one of the `Projection` variants of `PlaceContext`.
 129         self.visit_projection(place.as_ref(), context, location);
 130
 131         match DefUse::for_place(context) {
 132             // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a use.
 133             Some(_) if place.is_indirect() => self.0.gen(local),
 134
 135             Some(DefUse::Def) if projection.is_empty() => self.0.kill(local),
 136             Some(DefUse::Use) => self.0.gen(local),
 137             _ => {}
 138         }
 139     }
 140
 141     fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) {
 142         // Because we do not call `super_place` above, `visit_local` is only called for locals that
 143         // do not appear as part of  a `Place` in the MIR. This handles cases like the implicit use
 144         // of the return place in a `Return` terminator or the index in an `Index` projection.
 145         match DefUse::for_place(context) {
 146             Some(DefUse::Def) => self.0.kill(local),
 147             Some(DefUse::Use) => self.0.gen(local),
 148             _ => {}
 149         }
 150     }
 151 }
 152
 153 #[derive(Eq, PartialEq, Clone)]
 154 enum DefUse {
 155     Def,
 156     Use,
 157 }
 158
 159 impl DefUse {
 160     fn for_place(context: PlaceContext) -> Option<DefUse> {
 161         match context {
 162             PlaceContext::NonUse(_) => None,
 163
 164             PlaceContext::MutatingUse(MutatingUseContext::Store) => Some(DefUse::Def),
 165
 166             // `MutatingUseContext::Call` and `MutatingUseContext::Yield` indicate that this is the
 167             // destination place for a `Call` return or `Yield` resume respectively. Since this is
 168             // only a `Def` when the function returns successfully, we handle this case separately
 169             // in `call_return_effect` above.
 170             PlaceContext::MutatingUse(MutatingUseContext::Call | MutatingUseContext::Yield) => None,
 171
 172             // All other contexts are uses...
 173             PlaceContext::MutatingUse(
 174                 MutatingUseContext::AddressOf
 175                 | MutatingUseContext::AsmOutput
 176                 | MutatingUseContext::Borrow
 177                 | MutatingUseContext::Drop
 178                 | MutatingUseContext::Retag,
 179             )
 180             | PlaceContext::NonMutatingUse(
 181                 NonMutatingUseContext::AddressOf
 182                 | NonMutatingUseContext::Copy
 183                 | NonMutatingUseContext::Inspect
 184                 | NonMutatingUseContext::Move
 185                 | NonMutatingUseContext::ShallowBorrow
 186                 | NonMutatingUseContext::SharedBorrow
 187                 | NonMutatingUseContext::UniqueBorrow,
 188             ) => Some(DefUse::Use),
 189
 190             PlaceContext::MutatingUse(MutatingUseContext::Projection)
 191             | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
 192                 unreachable!("A projection could be a def or a use and must be handled separately")
 193             }
 194         }
 195     }
 196 }