src/librustc_mir/dataflow/impls/borrows.rs

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