compiler/rustc_borrowck/src/dataflow.rs

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