src/librustc_mir/dataflow/impls/borrows.rs

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