1 use crate::borrow_check::borrow_set::{BorrowSet, BorrowData};
2 use crate::borrow_check::place_ext::PlaceExt;
4 use rustc::mir::{self, Location, Place, PlaceBase, Body};
5 use rustc::ty::{self, TyCtxt};
6 use rustc::ty::RegionVid;
8 use rustc_data_structures::bit_set::BitSet;
9 use rustc_data_structures::fx::FxHashMap;
10 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
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;
20 pub struct BorrowIndex {
25 /// `Borrows` stores the data used in the analyses that track the flow
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> {
35 param_env: ty::ParamEnv<'tcx>,
37 borrow_set: Rc<BorrowSet<'tcx>>,
38 borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>,
40 /// NLL region inference context with which NLL queries should be resolved
41 _nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>,
51 fn precompute_borrows_out_of_scope<'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,
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.
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
69 let mut visited = FxHashMap::default();
70 visited.insert(location.block, location.statement_index);
72 let mut stack = vec![];
73 stack.push(StackEntry {
75 lo: location.statement_index,
76 hi: body[location.block].statements.len(),
77 first_part_only: false,
80 while let Some(StackEntry { bb, lo, hi, first_part_only }) = stack.pop() {
81 let mut finished_early = first_part_only;
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
92 finished_early = true;
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)
104 // `succ_bb` has been seen before. If it wasn't
105 // fully processed, add its first part to `stack`
108 stack.push(StackEntry {
112 first_part_only: true,
115 // And update this entry with 0, to represent the
116 // whole BB being processed.
120 // succ_bb hasn't been seen before. Add it to
121 // `stack` for processing.
122 stack.push(StackEntry {
125 hi: body[succ_bb].statements.len(),
126 first_part_only: false,
128 // Insert 0 for this BB, to represent the whole BB
137 impl<'a, 'tcx> Borrows<'a, 'tcx> {
140 body: &'a Body<'tcx>,
141 param_env: ty::ParamEnv<'tcx>,
142 nonlexical_regioncx: Rc<RegionInferenceContext<'tcx>>,
143 borrow_set: &Rc<BorrowSet<'tcx>>,
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;
150 precompute_borrows_out_of_scope(body, &nonlexical_regioncx,
151 &mut borrows_out_of_scope_at_location,
152 borrow_index, borrow_region, location);
159 borrow_set: borrow_set.clone(),
160 borrows_out_of_scope_at_location,
161 _nonlexical_regioncx: nonlexical_regioncx,
165 crate fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrow_set.borrows }
167 pub fn location(&self, idx: BorrowIndex) -> &Location {
168 &self.borrow_set.borrows[idx].reserve_location
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.
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);
192 /// Kill any borrows that conflict with `place`.
193 fn kill_borrows_on_place(
195 trans: &mut GenKillSet<BorrowIndex>,
198 debug!("kill_borrows_on_place: place={:?}", place);
200 if let PlaceBase::Local(local) = place.base {
201 let other_borrows_of_local = self
206 .flat_map(|bs| bs.into_iter());
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_none() {
212 trans.kill_all(other_borrows_of_local);
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
220 let definitely_conflicting_borrows = other_borrows_of_local
222 places_conflict::places_conflict(
226 &self.borrow_set.borrows[i].borrowed_place,
228 places_conflict::PlaceConflictBias::NoOverlap)
231 trans.kill_all(definitely_conflicting_borrows);
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
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.
248 fn before_statement_effect(&self,
249 trans: &mut GenKillSet<Self::Idx>,
250 location: Location) {
251 debug!("Borrows::before_statement_effect trans: {:?} location: {:?}",
253 self.kill_loans_out_of_scope_at_location(trans, location);
256 fn statement_effect(&self,
257 trans: &mut GenKillSet<Self::Idx>,
258 location: Location) {
259 debug!("Borrows::statement_effect: trans={:?} location={:?}",
262 let block = &self.body.basic_blocks().get(location.block).unwrap_or_else(|| {
263 panic!("could not find block at location {:?}", location);
265 let stmt = block.statements.get(location.statement_index).unwrap_or_else(|| {
266 panic!("could not find statement at location {:?}");
269 debug!("Borrows::statement_effect: stmt={:?}", stmt);
271 mir::StatementKind::Assign(ref lhs, ref rhs) => {
272 if let mir::Rvalue::Ref(_, _, ref place) = **rhs {
273 if place.ignore_borrow(
276 &self.borrow_set.locals_state_at_exit,
280 let index = self.borrow_set.location_map.get(&location).unwrap_or_else(|| {
281 panic!("could not find BorrowIndex for location {:?}", location);
287 // Make sure there are no remaining borrows for variables
288 // that are assigned over.
289 self.kill_borrows_on_place(trans, lhs);
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));
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);
306 mir::StatementKind::FakeRead(..) |
307 mir::StatementKind::SetDiscriminant { .. } |
308 mir::StatementKind::StorageLive(..) |
309 mir::StatementKind::Retag { .. } |
310 mir::StatementKind::AscribeUserType(..) |
311 mir::StatementKind::Nop => {}
316 fn before_terminator_effect(&self,
317 trans: &mut GenKillSet<Self::Idx>,
318 location: Location) {
319 debug!("Borrows::before_terminator_effect: trans={:?} location={:?}",
321 self.kill_loans_out_of_scope_at_location(trans, location);
324 fn terminator_effect(&self,
325 _: &mut GenKillSet<Self::Idx>,
328 fn propagate_call_return(
330 _in_out: &mut BitSet<BorrowIndex>,
331 _call_bb: mir::BasicBlock,
332 _dest_bb: mir::BasicBlock,
333 _dest_place: &mir::Place<'tcx>,
338 impl<'a, 'tcx> BottomValue for Borrows<'a, 'tcx> {
339 /// bottom = nothing is reserved or activated yet;
340 const BOTTOM_VALUE: bool = false;