src/librustc_mir/dataflow/impls/borrows.rs

   1 use borrow_check::borrow_set::{BorrowSet, BorrowData};
   2 use borrow_check::place_ext::PlaceExt;
   3
   4 use rustc::mir::{self, Location, Place, Mir};
   5 use rustc::ty::TyCtxt;
   6 use rustc::ty::RegionVid;
   7
   8 use rustc_data_structures::bit_set::{BitSet, BitSetOperator};
   9 use rustc_data_structures::fx::FxHashMap;
  10 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  11
  12 use dataflow::{BitDenotation, BlockSets, InitialFlow};
  13 pub use dataflow::indexes::BorrowIndex;
  14 use borrow_check::nll::region_infer::RegionInferenceContext;
  15 use borrow_check::nll::ToRegionVid;
  16 use borrow_check::places_conflict;
  17
  18 use std::rc::Rc;
  19
  20 /// `Borrows` stores the data used in the analyses that track the flow
  21 /// of borrows.
  22 ///
  23 /// It uniquely identifies every borrow (`Rvalue::Ref`) by a
  24 /// `BorrowIndex`, and maps each such index to a `BorrowData`
  25 /// describing the borrow. These indexes are used for representing the
  26 /// borrows in compact bitvectors.
  27 pub struct Borrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
  28     tcx: TyCtxt<'a, 'gcx, 'tcx>,
  29     mir: &'a Mir<'tcx>,
  30
  31     borrow_set: Rc<BorrowSet<'tcx>>,
  32     borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>,
  33
  34     /// NLL region inference context with which NLL queries should be resolved
  35     _nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>,
  36 }
  37
  38 struct StackEntry {
  39     bb: mir::BasicBlock,
  40     lo: usize,
  41     hi: usize,
  42     first_part_only: bool
  43 }
  44
  45 fn precompute_borrows_out_of_scope<'tcx>(
  46     mir: &Mir<'tcx>,
  47     regioncx: &Rc<RegionInferenceContext<'tcx>>,
  48     borrows_out_of_scope_at_location: &mut FxHashMap<Location, Vec<BorrowIndex>>,
  49     borrow_index: BorrowIndex,
  50     borrow_region: RegionVid,
  51     location: Location,
  52 ) {
  53     // We visit one BB at a time. The complication is that we may start in the
  54     // middle of the first BB visited (the one containing `location`), in which
  55     // case we may have to later on process the first part of that BB if there
  56     // is a path back to its start.
  57
  58     // For visited BBs, we record the index of the first statement processed.
  59     // (In fully processed BBs this index is 0.) Note also that we add BBs to
  60     // `visited` once they are added to `stack`, before they are actually
  61     // processed, because this avoids the need to look them up again on
  62     // completion.
  63     let mut visited = FxHashMap::default();
  64     visited.insert(location.block, location.statement_index);
  65
  66     let mut stack = vec![];
  67     stack.push(StackEntry {
  68         bb: location.block,
  69         lo: location.statement_index,
  70         hi: mir[location.block].statements.len(),
  71         first_part_only: false,
  72     });
  73
  74     while let Some(StackEntry { bb, lo, hi, first_part_only }) = stack.pop() {
  75         let mut finished_early = first_part_only;
  76         for i in lo ..= hi {
  77             let location = Location { block: bb, statement_index: i };
  78             // If region does not contain a point at the location, then add to list and skip
  79             // successor locations.
  80             if !regioncx.region_contains(borrow_region, location) {
  81                 debug!("borrow {:?} gets killed at {:?}", borrow_index, location);
  82                 borrows_out_of_scope_at_location
  83                     .entry(location)
  84                     .or_default()
  85                     .push(borrow_index);
  86                 finished_early = true;
  87                 break;
  88             }
  89         }
  90
  91         if !finished_early {
  92             // Add successor BBs to the work list, if necessary.
  93             let bb_data = &mir[bb];
  94             assert!(hi == bb_data.statements.len());
  95             for &succ_bb in bb_data.terminator.as_ref().unwrap().successors() {
  96                 visited.entry(succ_bb)
  97                     .and_modify(|lo| {
  98                         // `succ_bb` has been seen before. If it wasn't
  99                         // fully processed, add its first part to `stack`
 100                         // for processing.
 101                         if *lo > 0 {
 102                             stack.push(StackEntry {
 103                                 bb: succ_bb,
 104                                 lo: 0,
 105                                 hi: *lo - 1,
 106                                 first_part_only: true,
 107                             });
 108                         }
 109                         // And update this entry with 0, to represent the
 110                         // whole BB being processed.
 111                         *lo = 0;
 112                     })
 113                     .or_insert_with(|| {
 114                         // succ_bb hasn't been seen before. Add it to
 115                         // `stack` for processing.
 116                         stack.push(StackEntry {
 117                             bb: succ_bb,
 118                             lo: 0,
 119                             hi: mir[succ_bb].statements.len(),
 120                             first_part_only: false,
 121                         });
 122                         // Insert 0 for this BB, to represent the whole BB
 123                         // being processed.
 124                         0
 125                     });
 126             }
 127         }
 128     }
 129 }
 130
 131 impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
 132     crate fn new(
 133         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 134         mir: &'a Mir<'tcx>,
 135         nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>,
 136         borrow_set: &Rc<BorrowSet<'tcx>>,
 137     ) -> Self {
 138         let mut borrows_out_of_scope_at_location = FxHashMap::default();
 139         for (borrow_index, borrow_data) in borrow_set.borrows.iter_enumerated() {
 140             let borrow_region = borrow_data.region.to_region_vid();
 141             let location = borrow_set.borrows[borrow_index].reserve_location;
 142
 143             precompute_borrows_out_of_scope(mir, &nonlexical_regioncx,
 144                                             &mut borrows_out_of_scope_at_location,
 145                                             borrow_index, borrow_region, location);
 146         }
 147
 148         Borrows {
 149             tcx: tcx,
 150             mir: mir,
 151             borrow_set: borrow_set.clone(),
 152             borrows_out_of_scope_at_location,
 153             _nonlexical_regioncx: nonlexical_regioncx,
 154         }
 155     }
 156
 157     crate fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrow_set.borrows }
 158
 159     pub fn location(&self, idx: BorrowIndex) -> &Location {
 160         &self.borrow_set.borrows[idx].reserve_location
 161     }
 162
 163     /// Add all borrows to the kill set, if those borrows are out of scope at `location`.
 164     /// That means they went out of a nonlexical scope
 165     fn kill_loans_out_of_scope_at_location(&self,
 166                                            sets: &mut BlockSets<BorrowIndex>,
 167                                            location: Location) {
 168         // NOTE: The state associated with a given `location`
 169         // reflects the dataflow on entry to the statement.
 170         // Iterate over each of the borrows that we've precomputed
 171         // to have went out of scope at this location and kill them.
 172         //
 173         // We are careful always to call this function *before* we
 174         // set up the gen-bits for the statement or
 175         // termanator. That way, if the effect of the statement or
 176         // terminator *does* introduce a new loan of the same
 177         // region, then setting that gen-bit will override any
 178         // potential kill introduced here.
 179         if let Some(indices) = self.borrows_out_of_scope_at_location.get(&location) {
 180             sets.kill_all(indices);
 181         }
 182     }
 183
 184     /// Kill any borrows that conflict with `place`.
 185     fn kill_borrows_on_place(
 186         &self,
 187         sets: &mut BlockSets<BorrowIndex>,
 188         place: &Place<'tcx>
 189     ) {
 190         debug!("kill_borrows_on_place: place={:?}", place);
 191         // Handle the `Place::Local(..)` case first and exit early.
 192         if let Place::Local(local) = place {
 193             if let Some(borrow_indices) = self.borrow_set.local_map.get(&local) {
 194                 debug!("kill_borrows_on_place: borrow_indices={:?}", borrow_indices);
 195                 sets.kill_all(borrow_indices);
 196                 return;
 197             }
 198         }
 199
 200         // Otherwise, look at all borrows that are live and if they conflict with the assignment
 201         // into our place then we can kill them.
 202         let mut borrows = sets.on_entry.clone();
 203         let _ = borrows.union(sets.gen_set);
 204         for borrow_index in borrows.iter() {
 205             let borrow_data = &self.borrows()[borrow_index];
 206             debug!(
 207                 "kill_borrows_on_place: borrow_index={:?} borrow_data={:?}",
 208                 borrow_index, borrow_data,
 209             );
 210
 211             // By passing `PlaceConflictBias::NoOverlap`, we conservatively assume that any given
 212             // pair of array indices are unequal, so that when `places_conflict` returns true, we
 213             // will be assured that two places being compared definitely denotes the same sets of
 214             // locations.
 215             if places_conflict::places_conflict(
 216                 self.tcx,
 217                 self.mir,
 218                 place,
 219                 &borrow_data.borrowed_place,
 220                 places_conflict::PlaceConflictBias::NoOverlap,
 221             ) {
 222                 debug!(
 223                     "kill_borrows_on_place: (kill) borrow_index={:?} borrow_data={:?}",
 224                     borrow_index, borrow_data,
 225                 );
 226                 sets.kill(borrow_index);
 227             }
 228         }
 229     }
 230 }
 231
 232 impl<'a, 'gcx, 'tcx> BitDenotation<'tcx> for Borrows<'a, 'gcx, 'tcx> {
 233     type Idx = BorrowIndex;
 234     fn name() -> &'static str { "borrows" }
 235     fn bits_per_block(&self) -> usize {
 236         self.borrow_set.borrows.len() * 2
 237     }
 238
 239     fn start_block_effect(&self, _entry_set: &mut BitSet<BorrowIndex>) {
 240         // no borrows of code region_scopes have been taken prior to
 241         // function execution, so this method has no effect on
 242         // `_sets`.
 243     }
 244
 245     fn before_statement_effect(&self,
 246                                sets: &mut BlockSets<BorrowIndex>,
 247                                location: Location) {
 248         debug!("Borrows::before_statement_effect sets: {:?} location: {:?}", sets, location);
 249         self.kill_loans_out_of_scope_at_location(sets, location);
 250     }
 251
 252     fn statement_effect(&self, sets: &mut BlockSets<BorrowIndex>, location: Location) {
 253         debug!("Borrows::statement_effect: sets={:?} location={:?}", sets, location);
 254
 255         let block = &self.mir.basic_blocks().get(location.block).unwrap_or_else(|| {
 256             panic!("could not find block at location {:?}", location);
 257         });
 258         let stmt = block.statements.get(location.statement_index).unwrap_or_else(|| {
 259             panic!("could not find statement at location {:?}");
 260         });
 261
 262         debug!("Borrows::statement_effect: stmt={:?}", stmt);
 263         match stmt.kind {
 264             mir::StatementKind::Assign(ref lhs, ref rhs) => {
 265                 // Make sure there are no remaining borrows for variables
 266                 // that are assigned over.
 267                 self.kill_borrows_on_place(sets, lhs);
 268
 269                 if let mir::Rvalue::Ref(_, _, ref place) = **rhs {
 270                     if place.ignore_borrow(
 271                         self.tcx,
 272                         self.mir,
 273                         &self.borrow_set.locals_state_at_exit,
 274                     ) {
 275                         return;
 276                     }
 277                     let index = self.borrow_set.location_map.get(&location).unwrap_or_else(|| {
 278                         panic!("could not find BorrowIndex for location {:?}", location);
 279                     });
 280
 281                     sets.gen(*index);
 282                 }
 283             }
 284
 285             mir::StatementKind::StorageDead(local) => {
 286                 // Make sure there are no remaining borrows for locals that
 287                 // are gone out of scope.
 288                 self.kill_borrows_on_place(sets, &Place::Local(local));
 289             }
 290
 291             mir::StatementKind::InlineAsm { ref outputs, ref asm, .. } => {
 292                 for (output, kind) in outputs.iter().zip(&asm.outputs) {
 293                     if !kind.is_indirect && !kind.is_rw {
 294                         self.kill_borrows_on_place(sets, output);
 295                     }
 296                 }
 297             }
 298
 299             mir::StatementKind::FakeRead(..) |
 300             mir::StatementKind::SetDiscriminant { .. } |
 301             mir::StatementKind::StorageLive(..) |
 302             mir::StatementKind::Retag { .. } |
 303             mir::StatementKind::AscribeUserType(..) |
 304             mir::StatementKind::Nop => {}
 305
 306         }
 307     }
 308
 309     fn before_terminator_effect(&self,
 310                                 sets: &mut BlockSets<BorrowIndex>,
 311                                 location: Location) {
 312         debug!("Borrows::before_terminator_effect sets: {:?} location: {:?}", sets, location);
 313         self.kill_loans_out_of_scope_at_location(sets, location);
 314     }
 315
 316     fn terminator_effect(&self, _: &mut BlockSets<BorrowIndex>, _: Location) {}
 317
 318     fn propagate_call_return(
 319         &self,
 320         _in_out: &mut BitSet<BorrowIndex>,
 321         _call_bb: mir::BasicBlock,
 322         _dest_bb: mir::BasicBlock,
 323         _dest_place: &mir::Place<'tcx>,
 324     ) {
 325     }
 326 }
 327
 328 impl<'a, 'gcx, 'tcx> BitSetOperator for Borrows<'a, 'gcx, 'tcx> {
 329     #[inline]
 330     fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool {
 331         inout_set.union(in_set) // "maybe" means we union effects of both preds
 332     }
 333 }
 334
 335 impl<'a, 'gcx, 'tcx> InitialFlow for Borrows<'a, 'gcx, 'tcx> {
 336     #[inline]
 337     fn bottom_value() -> bool {
 338         false // bottom = nothing is reserved or activated yet
 339     }
 340 }