src/librustc_mir/dataflow/impls/borrows.rs

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