compiler/rustc_borrowck/src/dataflow.rs

   1 use rustc_data_structures::fx::FxHashMap;
   2 use rustc_index::bit_set::BitSet;
   3 use rustc_middle::mir::{self, BasicBlock, Body, Location, Place};
   4 use rustc_middle::ty::RegionVid;
   5 use rustc_middle::ty::TyCtxt;
   6 use rustc_mir_dataflow::impls::{EverInitializedPlaces, MaybeUninitializedPlaces};
   7 use rustc_mir_dataflow::ResultsVisitable;
   8 use rustc_mir_dataflow::{self, fmt::DebugWithContext, CallReturnPlaces, GenKill};
   9 use rustc_mir_dataflow::{Analysis, Direction, Results};
  10 use std::fmt;
  11
  12 use crate::{
  13     places_conflict, BorrowSet, PlaceConflictBias, PlaceExt, RegionInferenceContext, ToRegionVid,
  14 };
  15
  16 /// A tuple with named fields that can hold either the results or the transient state of the
  17 /// dataflow analyses used by the borrow checker.
  18 #[derive(Debug)]
  19 pub struct BorrowckAnalyses<B, U, E> {
  20     pub borrows: B,
  21     pub uninits: U,
  22     pub ever_inits: E,
  23 }
  24
  25 /// The results of the dataflow analyses used by the borrow checker.
  26 pub type BorrowckResults<'mir, 'tcx> = BorrowckAnalyses<
  27     Results<'tcx, Borrows<'mir, 'tcx>>,
  28     Results<'tcx, MaybeUninitializedPlaces<'mir, 'tcx>>,
  29     Results<'tcx, EverInitializedPlaces<'mir, 'tcx>>,
  30 >;
  31
  32 /// The transient state of the dataflow analyses used by the borrow checker.
  33 pub type BorrowckFlowState<'mir, 'tcx> =
  34     <BorrowckResults<'mir, 'tcx> as ResultsVisitable<'tcx>>::FlowState;
  35
  36 macro_rules! impl_visitable {
  37     ( $(
  38         $T:ident { $( $field:ident : $A:ident ),* $(,)? }
  39     )* ) => { $(
  40         impl<'tcx, $($A),*, D: Direction> ResultsVisitable<'tcx> for $T<$( Results<'tcx, $A> ),*>
  41         where
  42             $( $A: Analysis<'tcx, Direction = D>, )*
  43         {
  44             type Direction = D;
  45             type FlowState = $T<$( $A::Domain ),*>;
  46
  47             fn new_flow_state(&self, body: &mir::Body<'tcx>) -> Self::FlowState {
  48                 $T {
  49                     $( $field: self.$field.analysis.bottom_value(body) ),*
  50                 }
  51             }
  52
  53             fn reset_to_block_entry(
  54                 &self,
  55                 state: &mut Self::FlowState,
  56                 block: BasicBlock,
  57             ) {
  58                 $( state.$field.clone_from(&self.$field.entry_set_for_block(block)); )*
  59             }
  60
  61             fn reconstruct_before_statement_effect(
  62                 &self,
  63                 state: &mut Self::FlowState,
  64                 stmt: &mir::Statement<'tcx>,
  65                 loc: Location,
  66             ) {
  67                 $( self.$field.analysis
  68                     .apply_before_statement_effect(&mut state.$field, stmt, loc); )*
  69             }
  70
  71             fn reconstruct_statement_effect(
  72                 &self,
  73                 state: &mut Self::FlowState,
  74                 stmt: &mir::Statement<'tcx>,
  75                 loc: Location,
  76             ) {
  77                 $( self.$field.analysis
  78                     .apply_statement_effect(&mut state.$field, stmt, loc); )*
  79             }
  80
  81             fn reconstruct_before_terminator_effect(
  82                 &self,
  83                 state: &mut Self::FlowState,
  84                 term: &mir::Terminator<'tcx>,
  85                 loc: Location,
  86             ) {
  87                 $( self.$field.analysis
  88                     .apply_before_terminator_effect(&mut state.$field, term, loc); )*
  89             }
  90
  91             fn reconstruct_terminator_effect(
  92                 &self,
  93                 state: &mut Self::FlowState,
  94                 term: &mir::Terminator<'tcx>,
  95                 loc: Location,
  96             ) {
  97                 $( self.$field.analysis
  98                     .apply_terminator_effect(&mut state.$field, term, loc); )*
  99             }
 100         }
 101     )* }
 102 }
 103
 104 impl_visitable! {
 105     BorrowckAnalyses { borrows: B, uninits: U, ever_inits: E }
 106 }
 107
 108 rustc_index::newtype_index! {
 109     pub struct BorrowIndex {
 110         DEBUG_FORMAT = "bw{}"
 111     }
 112 }
 113
 114 /// `Borrows` stores the data used in the analyses that track the flow
 115 /// of borrows.
 116 ///
 117 /// It uniquely identifies every borrow (`Rvalue::Ref`) by a
 118 /// `BorrowIndex`, and maps each such index to a `BorrowData`
 119 /// describing the borrow. These indexes are used for representing the
 120 /// borrows in compact bitvectors.
 121 pub struct Borrows<'a, 'tcx> {
 122     tcx: TyCtxt<'tcx>,
 123     body: &'a Body<'tcx>,
 124
 125     borrow_set: &'a BorrowSet<'tcx>,
 126     borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>,
 127 }
 128
 129 struct StackEntry {
 130     bb: mir::BasicBlock,
 131     lo: usize,
 132     hi: usize,
 133 }
 134
 135 struct OutOfScopePrecomputer<'a, 'tcx> {
 136     visited: BitSet<mir::BasicBlock>,
 137     visit_stack: Vec<StackEntry>,
 138     body: &'a Body<'tcx>,
 139     regioncx: &'a RegionInferenceContext<'tcx>,
 140     borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>,
 141 }
 142
 143 impl<'a, 'tcx> OutOfScopePrecomputer<'a, 'tcx> {
 144     fn new(body: &'a Body<'tcx>, regioncx: &'a RegionInferenceContext<'tcx>) -> Self {
 145         OutOfScopePrecomputer {
 146             visited: BitSet::new_empty(body.basic_blocks.len()),
 147             visit_stack: vec![],
 148             body,
 149             regioncx,
 150             borrows_out_of_scope_at_location: FxHashMap::default(),
 151         }
 152     }
 153 }
 154
 155 impl<'tcx> OutOfScopePrecomputer<'_, 'tcx> {
 156     fn precompute_borrows_out_of_scope(
 157         &mut self,
 158         borrow_index: BorrowIndex,
 159         borrow_region: RegionVid,
 160         location: Location,
 161     ) {
 162         // We visit one BB at a time. The complication is that we may start in the
 163         // middle of the first BB visited (the one containing `location`), in which
 164         // case we may have to later on process the first part of that BB if there
 165         // is a path back to its start.
 166
 167         // For visited BBs, we record the index of the first statement processed.
 168         // (In fully processed BBs this index is 0.) Note also that we add BBs to
 169         // `visited` once they are added to `stack`, before they are actually
 170         // processed, because this avoids the need to look them up again on
 171         // completion.
 172         self.visited.insert(location.block);
 173
 174         let mut first_lo = location.statement_index;
 175         let first_hi = self.body[location.block].statements.len();
 176
 177         self.visit_stack.push(StackEntry { bb: location.block, lo: first_lo, hi: first_hi });
 178
 179         while let Some(StackEntry { bb, lo, hi }) = self.visit_stack.pop() {
 180             // If we process the first part of the first basic block (i.e. we encounter that block
 181             // for the second time), we no longer have to visit its successors again.
 182             let mut finished_early = bb == location.block && hi != first_hi;
 183             for i in lo..=hi {
 184                 let location = Location { block: bb, statement_index: i };
 185                 // If region does not contain a point at the location, then add to list and skip
 186                 // successor locations.
 187                 if !self.regioncx.region_contains(borrow_region, location) {
 188                     debug!("borrow {:?} gets killed at {:?}", borrow_index, location);
 189                     self.borrows_out_of_scope_at_location
 190                         .entry(location)
 191                         .or_default()
 192                         .push(borrow_index);
 193                     finished_early = true;
 194                     break;
 195                 }
 196             }
 197
 198             if !finished_early {
 199                 // Add successor BBs to the work list, if necessary.
 200                 let bb_data = &self.body[bb];
 201                 debug_assert!(hi == bb_data.statements.len());
 202                 for succ_bb in bb_data.terminator().successors() {
 203                     if !self.visited.insert(succ_bb) {
 204                         if succ_bb == location.block && first_lo > 0 {
 205                             // `succ_bb` has been seen before. If it wasn't
 206                             // fully processed, add its first part to `stack`
 207                             // for processing.
 208                             self.visit_stack.push(StackEntry {
 209                                 bb: succ_bb,
 210                                 lo: 0,
 211                                 hi: first_lo - 1,
 212                             });
 213
 214                             // And update this entry with 0, to represent the
 215                             // whole BB being processed.
 216                             first_lo = 0;
 217                         }
 218                     } else {
 219                         // succ_bb hasn't been seen before. Add it to
 220                         // `stack` for processing.
 221                         self.visit_stack.push(StackEntry {
 222                             bb: succ_bb,
 223                             lo: 0,
 224                             hi: self.body[succ_bb].statements.len(),
 225                         });
 226                     }
 227                 }
 228             }
 229         }
 230
 231         self.visited.clear();
 232     }
 233 }
 234
 235 impl<'a, 'tcx> Borrows<'a, 'tcx> {
 236     pub(crate) fn new(
 237         tcx: TyCtxt<'tcx>,
 238         body: &'a Body<'tcx>,
 239         nonlexical_regioncx: &'a RegionInferenceContext<'tcx>,
 240         borrow_set: &'a BorrowSet<'tcx>,
 241     ) -> Self {
 242         let mut prec = OutOfScopePrecomputer::new(body, nonlexical_regioncx);
 243         for (borrow_index, borrow_data) in borrow_set.iter_enumerated() {
 244             let borrow_region = borrow_data.region.to_region_vid();
 245             let location = borrow_data.reserve_location;
 246
 247             prec.precompute_borrows_out_of_scope(borrow_index, borrow_region, location);
 248         }
 249
 250         Borrows {
 251             tcx,
 252             body,
 253             borrow_set,
 254             borrows_out_of_scope_at_location: prec.borrows_out_of_scope_at_location,
 255         }
 256     }
 257
 258     pub fn location(&self, idx: BorrowIndex) -> &Location {
 259         &self.borrow_set[idx].reserve_location
 260     }
 261
 262     /// Add all borrows to the kill set, if those borrows are out of scope at `location`.
 263     /// That means they went out of a nonlexical scope
 264     fn kill_loans_out_of_scope_at_location(
 265         &self,
 266         trans: &mut impl GenKill<BorrowIndex>,
 267         location: Location,
 268     ) {
 269         // NOTE: The state associated with a given `location`
 270         // reflects the dataflow on entry to the statement.
 271         // Iterate over each of the borrows that we've precomputed
 272         // to have went out of scope at this location and kill them.
 273         //
 274         // We are careful always to call this function *before* we
 275         // set up the gen-bits for the statement or
 276         // terminator. That way, if the effect of the statement or
 277         // terminator *does* introduce a new loan of the same
 278         // region, then setting that gen-bit will override any
 279         // potential kill introduced here.
 280         if let Some(indices) = self.borrows_out_of_scope_at_location.get(&location) {
 281             trans.kill_all(indices.iter().copied());
 282         }
 283     }
 284
 285     /// Kill any borrows that conflict with `place`.
 286     fn kill_borrows_on_place(&self, trans: &mut impl GenKill<BorrowIndex>, place: Place<'tcx>) {
 287         debug!("kill_borrows_on_place: place={:?}", place);
 288
 289         let other_borrows_of_local = self
 290             .borrow_set
 291             .local_map
 292             .get(&place.local)
 293             .into_iter()
 294             .flat_map(|bs| bs.iter())
 295             .copied();
 296
 297         // If the borrowed place is a local with no projections, all other borrows of this
 298         // local must conflict. This is purely an optimization so we don't have to call
 299         // `places_conflict` for every borrow.
 300         if place.projection.is_empty() {
 301             if !self.body.local_decls[place.local].is_ref_to_static() {
 302                 trans.kill_all(other_borrows_of_local);
 303             }
 304             return;
 305         }
 306
 307         // By passing `PlaceConflictBias::NoOverlap`, we conservatively assume that any given
 308         // pair of array indices are unequal, so that when `places_conflict` returns true, we
 309         // will be assured that two places being compared definitely denotes the same sets of
 310         // locations.
 311         let definitely_conflicting_borrows = other_borrows_of_local.filter(|&i| {
 312             places_conflict(
 313                 self.tcx,
 314                 self.body,
 315                 self.borrow_set[i].borrowed_place,
 316                 place,
 317                 PlaceConflictBias::NoOverlap,
 318             )
 319         });
 320
 321         trans.kill_all(definitely_conflicting_borrows);
 322     }
 323 }
 324
 325 impl<'tcx> rustc_mir_dataflow::AnalysisDomain<'tcx> for Borrows<'_, 'tcx> {
 326     type Domain = BitSet<BorrowIndex>;
 327
 328     const NAME: &'static str = "borrows";
 329
 330     fn bottom_value(&self, _: &mir::Body<'tcx>) -> Self::Domain {
 331         // bottom = nothing is reserved or activated yet;
 332         BitSet::new_empty(self.borrow_set.len() * 2)
 333     }
 334
 335     fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
 336         // no borrows of code region_scopes have been taken prior to
 337         // function execution, so this method has no effect.
 338     }
 339 }
 340
 341 impl<'tcx> rustc_mir_dataflow::GenKillAnalysis<'tcx> for Borrows<'_, 'tcx> {
 342     type Idx = BorrowIndex;
 343
 344     fn before_statement_effect(
 345         &self,
 346         trans: &mut impl GenKill<Self::Idx>,
 347         _statement: &mir::Statement<'tcx>,
 348         location: Location,
 349     ) {
 350         self.kill_loans_out_of_scope_at_location(trans, location);
 351     }
 352
 353     fn statement_effect(
 354         &self,
 355         trans: &mut impl GenKill<Self::Idx>,
 356         stmt: &mir::Statement<'tcx>,
 357         location: Location,
 358     ) {
 359         match stmt.kind {
 360             mir::StatementKind::Assign(box (lhs, ref rhs)) => {
 361                 if let mir::Rvalue::Ref(_, _, place) = *rhs {
 362                     if place.ignore_borrow(
 363                         self.tcx,
 364                         self.body,
 365                         &self.borrow_set.locals_state_at_exit,
 366                     ) {
 367                         return;
 368                     }
 369                     let index = self.borrow_set.get_index_of(&location).unwrap_or_else(|| {
 370                         panic!("could not find BorrowIndex for location {:?}", location);
 371                     });
 372
 373                     trans.gen(index);
 374                 }
 375
 376                 // Make sure there are no remaining borrows for variables
 377                 // that are assigned over.
 378                 self.kill_borrows_on_place(trans, lhs);
 379             }
 380
 381             mir::StatementKind::StorageDead(local) => {
 382                 // Make sure there are no remaining borrows for locals that
 383                 // are gone out of scope.
 384                 self.kill_borrows_on_place(trans, Place::from(local));
 385             }
 386
 387             mir::StatementKind::FakeRead(..)
 388             | mir::StatementKind::SetDiscriminant { .. }
 389             | mir::StatementKind::Deinit(..)
 390             | mir::StatementKind::StorageLive(..)
 391             | mir::StatementKind::Retag { .. }
 392             | mir::StatementKind::AscribeUserType(..)
 393             | mir::StatementKind::Coverage(..)
 394             | mir::StatementKind::Intrinsic(..)
 395             | mir::StatementKind::Nop => {}
 396         }
 397     }
 398
 399     fn before_terminator_effect(
 400         &self,
 401         trans: &mut impl GenKill<Self::Idx>,
 402         _terminator: &mir::Terminator<'tcx>,
 403         location: Location,
 404     ) {
 405         self.kill_loans_out_of_scope_at_location(trans, location);
 406     }
 407
 408     fn terminator_effect(
 409         &self,
 410         trans: &mut impl GenKill<Self::Idx>,
 411         terminator: &mir::Terminator<'tcx>,
 412         _location: Location,
 413     ) {
 414         if let mir::TerminatorKind::InlineAsm { operands, .. } = &terminator.kind {
 415             for op in operands {
 416                 if let mir::InlineAsmOperand::Out { place: Some(place), .. }
 417                 | mir::InlineAsmOperand::InOut { out_place: Some(place), .. } = *op
 418                 {
 419                     self.kill_borrows_on_place(trans, place);
 420                 }
 421             }
 422         }
 423     }
 424
 425     fn call_return_effect(
 426         &self,
 427         _trans: &mut impl GenKill<Self::Idx>,
 428         _block: mir::BasicBlock,
 429         _return_places: CallReturnPlaces<'_, 'tcx>,
 430     ) {
 431     }
 432 }
 433
 434 impl DebugWithContext<Borrows<'_, '_>> for BorrowIndex {
 435     fn fmt_with(&self, ctxt: &Borrows<'_, '_>, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 436         write!(f, "{:?}", ctxt.location(*self))
 437     }
 438 }