compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs

   1 pub use super::*;
   2
   3 use crate::{CallReturnPlaces, GenKill, Results, ResultsRefCursor};
   4 use rustc_middle::mir::visit::{NonMutatingUseContext, PlaceContext, Visitor};
   5 use rustc_middle::mir::*;
   6 use std::borrow::Cow;
   7 use std::cell::RefCell;
   8
   9 #[derive(Clone)]
  10 pub struct MaybeStorageLive<'a> {
  11     always_live_locals: Cow<'a, BitSet<Local>>,
  12 }
  13
  14 impl<'a> MaybeStorageLive<'a> {
  15     pub fn new(always_live_locals: Cow<'a, BitSet<Local>>) -> Self {
  16         MaybeStorageLive { always_live_locals }
  17     }
  18 }
  19
  20 impl<'tcx, 'a> crate::AnalysisDomain<'tcx> for MaybeStorageLive<'a> {
  21     type Domain = BitSet<Local>;
  22
  23     const NAME: &'static str = "maybe_storage_live";
  24
  25     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
  26         // bottom = dead
  27         BitSet::new_empty(body.local_decls.len())
  28     }
  29
  30     fn initialize_start_block(&self, body: &mir::Body<'tcx>, on_entry: &mut Self::Domain) {
  31         assert_eq!(body.local_decls.len(), self.always_live_locals.domain_size());
  32         for local in self.always_live_locals.iter() {
  33             on_entry.insert(local);
  34         }
  35
  36         for arg in body.args_iter() {
  37             on_entry.insert(arg);
  38         }
  39     }
  40 }
  41
  42 impl<'tcx, 'a> crate::GenKillAnalysis<'tcx> for MaybeStorageLive<'a> {
  43     type Idx = Local;
  44
  45     fn statement_effect(
  46         &self,
  47         trans: &mut impl GenKill<Self::Idx>,
  48         stmt: &mir::Statement<'tcx>,
  49         _: Location,
  50     ) {
  51         match stmt.kind {
  52             StatementKind::StorageLive(l) => trans.gen(l),
  53             StatementKind::StorageDead(l) => trans.kill(l),
  54             _ => (),
  55         }
  56     }
  57
  58     fn terminator_effect(
  59         &self,
  60         _trans: &mut impl GenKill<Self::Idx>,
  61         _: &mir::Terminator<'tcx>,
  62         _: Location,
  63     ) {
  64         // Terminators have no effect
  65     }
  66
  67     fn call_return_effect(
  68         &self,
  69         _trans: &mut impl GenKill<Self::Idx>,
  70         _block: BasicBlock,
  71         _return_places: CallReturnPlaces<'_, 'tcx>,
  72     ) {
  73         // Nothing to do when a call returns successfully
  74     }
  75 }
  76
  77 type BorrowedLocalsResults<'a, 'tcx> = ResultsRefCursor<'a, 'a, 'tcx, MaybeBorrowedLocals>;
  78
  79 /// Dataflow analysis that determines whether each local requires storage at a
  80 /// given location; i.e. whether its storage can go away without being observed.
  81 pub struct MaybeRequiresStorage<'mir, 'tcx> {
  82     body: &'mir Body<'tcx>,
  83     borrowed_locals: RefCell<BorrowedLocalsResults<'mir, 'tcx>>,
  84 }
  85
  86 impl<'mir, 'tcx> MaybeRequiresStorage<'mir, 'tcx> {
  87     pub fn new(
  88         body: &'mir Body<'tcx>,
  89         borrowed_locals: &'mir Results<'tcx, MaybeBorrowedLocals>,
  90     ) -> Self {
  91         MaybeRequiresStorage {
  92             body,
  93             borrowed_locals: RefCell::new(ResultsRefCursor::new(&body, borrowed_locals)),
  94         }
  95     }
  96 }
  97
  98 impl<'mir, 'tcx> crate::AnalysisDomain<'tcx> for MaybeRequiresStorage<'mir, 'tcx> {
  99     type Domain = BitSet<Local>;
 100
 101     const NAME: &'static str = "requires_storage";
 102
 103     fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
 104         // bottom = dead
 105         BitSet::new_empty(body.local_decls.len())
 106     }
 107
 108     fn initialize_start_block(&self, body: &mir::Body<'tcx>, on_entry: &mut Self::Domain) {
 109         // The resume argument is live on function entry (we don't care about
 110         // the `self` argument)
 111         for arg in body.args_iter().skip(1) {
 112             on_entry.insert(arg);
 113         }
 114     }
 115 }
 116
 117 impl<'mir, 'tcx> crate::GenKillAnalysis<'tcx> for MaybeRequiresStorage<'mir, 'tcx> {
 118     type Idx = Local;
 119
 120     fn before_statement_effect(
 121         &self,
 122         trans: &mut impl GenKill<Self::Idx>,
 123         stmt: &mir::Statement<'tcx>,
 124         loc: Location,
 125     ) {
 126         // If a place is borrowed in a statement, it needs storage for that statement.
 127         self.borrowed_locals.borrow().analysis().statement_effect(trans, stmt, loc);
 128
 129         match &stmt.kind {
 130             StatementKind::StorageDead(l) => trans.kill(*l),
 131
 132             // If a place is assigned to in a statement, it needs storage for that statement.
 133             StatementKind::Assign(box (place, _))
 134             | StatementKind::SetDiscriminant { box place, .. }
 135             | StatementKind::Deinit(box place) => {
 136                 trans.gen(place.local);
 137             }
 138
 139             // Nothing to do for these. Match exhaustively so this fails to compile when new
 140             // variants are added.
 141             StatementKind::AscribeUserType(..)
 142             | StatementKind::Coverage(..)
 143             | StatementKind::FakeRead(..)
 144             | StatementKind::Nop
 145             | StatementKind::Retag(..)
 146             | StatementKind::Intrinsic(..)
 147             | StatementKind::StorageLive(..) => {}
 148         }
 149     }
 150
 151     fn statement_effect(
 152         &self,
 153         trans: &mut impl GenKill<Self::Idx>,
 154         _: &mir::Statement<'tcx>,
 155         loc: Location,
 156     ) {
 157         // If we move from a place then it only stops needing storage *after*
 158         // that statement.
 159         self.check_for_move(trans, loc);
 160     }
 161
 162     fn before_terminator_effect(
 163         &self,
 164         trans: &mut impl GenKill<Self::Idx>,
 165         terminator: &mir::Terminator<'tcx>,
 166         loc: Location,
 167     ) {
 168         // If a place is borrowed in a terminator, it needs storage for that terminator.
 169         self.borrowed_locals.borrow().analysis().terminator_effect(trans, terminator, loc);
 170
 171         match &terminator.kind {
 172             TerminatorKind::Call { destination, .. } => {
 173                 trans.gen(destination.local);
 174             }
 175
 176             // Note that we do *not* gen the `resume_arg` of `Yield` terminators. The reason for
 177             // that is that a `yield` will return from the function, and `resume_arg` is written
 178             // only when the generator is later resumed. Unlike `Call`, this doesn't require the
 179             // place to have storage *before* the yield, only after.
 180             TerminatorKind::Yield { .. } => {}
 181
 182             TerminatorKind::InlineAsm { operands, .. } => {
 183                 for op in operands {
 184                     match op {
 185                         InlineAsmOperand::Out { place, .. }
 186                         | InlineAsmOperand::InOut { out_place: place, .. } => {
 187                             if let Some(place) = place {
 188                                 trans.gen(place.local);
 189                             }
 190                         }
 191                         InlineAsmOperand::In { .. }
 192                         | InlineAsmOperand::Const { .. }
 193                         | InlineAsmOperand::SymFn { .. }
 194                         | InlineAsmOperand::SymStatic { .. } => {}
 195                     }
 196                 }
 197             }
 198
 199             // Nothing to do for these. Match exhaustively so this fails to compile when new
 200             // variants are added.
 201             TerminatorKind::Abort
 202             | TerminatorKind::Assert { .. }
 203             | TerminatorKind::Drop { .. }
 204             | TerminatorKind::DropAndReplace { .. }
 205             | TerminatorKind::FalseEdge { .. }
 206             | TerminatorKind::FalseUnwind { .. }
 207             | TerminatorKind::GeneratorDrop
 208             | TerminatorKind::Goto { .. }
 209             | TerminatorKind::Resume
 210             | TerminatorKind::Return
 211             | TerminatorKind::SwitchInt { .. }
 212             | TerminatorKind::Unreachable => {}
 213         }
 214     }
 215
 216     fn terminator_effect(
 217         &self,
 218         trans: &mut impl GenKill<Self::Idx>,
 219         terminator: &mir::Terminator<'tcx>,
 220         loc: Location,
 221     ) {
 222         match terminator.kind {
 223             // For call terminators the destination requires storage for the call
 224             // and after the call returns successfully, but not after a panic.
 225             // Since `propagate_call_unwind` doesn't exist, we have to kill the
 226             // destination here, and then gen it again in `call_return_effect`.
 227             TerminatorKind::Call { destination, .. } => {
 228                 trans.kill(destination.local);
 229             }
 230
 231             // The same applies to InlineAsm outputs.
 232             TerminatorKind::InlineAsm { ref operands, .. } => {
 233                 CallReturnPlaces::InlineAsm(operands).for_each(|place| trans.kill(place.local));
 234             }
 235
 236             // Nothing to do for these. Match exhaustively so this fails to compile when new
 237             // variants are added.
 238             TerminatorKind::Yield { .. }
 239             | TerminatorKind::Abort
 240             | TerminatorKind::Assert { .. }
 241             | TerminatorKind::Drop { .. }
 242             | TerminatorKind::DropAndReplace { .. }
 243             | TerminatorKind::FalseEdge { .. }
 244             | TerminatorKind::FalseUnwind { .. }
 245             | TerminatorKind::GeneratorDrop
 246             | TerminatorKind::Goto { .. }
 247             | TerminatorKind::Resume
 248             | TerminatorKind::Return
 249             | TerminatorKind::SwitchInt { .. }
 250             | TerminatorKind::Unreachable => {}
 251         }
 252
 253         self.check_for_move(trans, loc);
 254     }
 255
 256     fn call_return_effect(
 257         &self,
 258         trans: &mut impl GenKill<Self::Idx>,
 259         _block: BasicBlock,
 260         return_places: CallReturnPlaces<'_, 'tcx>,
 261     ) {
 262         return_places.for_each(|place| trans.gen(place.local));
 263     }
 264
 265     fn yield_resume_effect(
 266         &self,
 267         trans: &mut impl GenKill<Self::Idx>,
 268         _resume_block: BasicBlock,
 269         resume_place: mir::Place<'tcx>,
 270     ) {
 271         trans.gen(resume_place.local);
 272     }
 273 }
 274
 275 impl<'mir, 'tcx> MaybeRequiresStorage<'mir, 'tcx> {
 276     /// Kill locals that are fully moved and have not been borrowed.
 277     fn check_for_move(&self, trans: &mut impl GenKill<Local>, loc: Location) {
 278         let mut visitor = MoveVisitor { trans, borrowed_locals: &self.borrowed_locals };
 279         visitor.visit_location(&self.body, loc);
 280     }
 281 }
 282
 283 struct MoveVisitor<'a, 'mir, 'tcx, T> {
 284     borrowed_locals: &'a RefCell<BorrowedLocalsResults<'mir, 'tcx>>,
 285     trans: &'a mut T,
 286 }
 287
 288 impl<'a, 'mir, 'tcx, T> Visitor<'tcx> for MoveVisitor<'a, 'mir, 'tcx, T>
 289 where
 290     T: GenKill<Local>,
 291 {
 292     fn visit_local(&mut self, local: Local, context: PlaceContext, loc: Location) {
 293         if PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) == context {
 294             let mut borrowed_locals = self.borrowed_locals.borrow_mut();
 295             borrowed_locals.seek_before_primary_effect(loc);
 296             if !borrowed_locals.contains(local) {
 297                 self.trans.kill(local);
 298             }
 299         }
 300     }
 301 }