1 use rustc_middle
::mir
::{self, Body, Location, Place}
;
2 use rustc_middle
::ty
::RegionVid
;
3 use rustc_middle
::ty
::TyCtxt
;
5 use rustc_data_structures
::fx
::FxHashMap
;
6 use rustc_index
::bit_set
::BitSet
;
8 use crate::borrow_check
::{
9 places_conflict
, BorrowSet
, PlaceConflictBias
, PlaceExt
, RegionInferenceContext
, ToRegionVid
,
11 use crate::dataflow
::BottomValue
;
12 use crate::dataflow
::{self, GenKill}
;
16 rustc_index
::newtype_index
! {
17 pub struct BorrowIndex
{
22 /// `Borrows` stores the data used in the analyses that track the flow
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
> {
33 borrow_set
: Rc
<BorrowSet
<'tcx
>>,
34 borrows_out_of_scope_at_location
: FxHashMap
<Location
, Vec
<BorrowIndex
>>,
36 /// NLL region inference context with which NLL queries should be resolved
37 _nonlexical_regioncx
: Rc
<RegionInferenceContext
<'tcx
>>,
44 first_part_only
: bool
,
47 fn precompute_borrows_out_of_scope
<'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
,
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.
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
65 let mut visited
= FxHashMap
::default();
66 visited
.insert(location
.block
, location
.statement_index
);
68 let mut stack
= vec
![];
69 stack
.push(StackEntry
{
71 lo
: location
.statement_index
,
72 hi
: body
[location
.block
].statements
.len(),
73 first_part_only
: false,
76 while let Some(StackEntry { bb, lo, hi, first_part_only }
) = stack
.pop() {
77 let mut finished_early
= first_part_only
;
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;
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() {
98 // `succ_bb` has been seen before. If it wasn't
99 // fully processed, add its first part to `stack`
102 stack
.push(StackEntry
{
106 first_part_only
: true,
109 // And update this entry with 0, to represent the
110 // whole BB being processed.
114 // succ_bb hasn't been seen before. Add it to
115 // `stack` for processing.
116 stack
.push(StackEntry
{
119 hi
: body
[succ_bb
].statements
.len(),
120 first_part_only
: false,
122 // Insert 0 for this BB, to represent the whole BB
131 impl<'a
, 'tcx
> Borrows
<'a
, 'tcx
> {
134 body
: &'a Body
<'tcx
>,
135 nonlexical_regioncx
: Rc
<RegionInferenceContext
<'tcx
>>,
136 borrow_set
: &Rc
<BorrowSet
<'tcx
>>,
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
;
143 precompute_borrows_out_of_scope(
145 &nonlexical_regioncx
,
146 &mut borrows_out_of_scope_at_location
,
156 borrow_set
: borrow_set
.clone(),
157 borrows_out_of_scope_at_location
,
158 _nonlexical_regioncx
: nonlexical_regioncx
,
162 pub fn location(&self, idx
: BorrowIndex
) -> &Location
{
163 &self.borrow_set
[idx
].reserve_location
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(
170 trans
: &mut impl GenKill
<BorrowIndex
>,
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.
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());
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
);
193 let other_borrows_of_local
= self
198 .flat_map(|bs
| bs
.iter())
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
);
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
215 let definitely_conflicting_borrows
= other_borrows_of_local
.filter(|&i
| {
219 self.borrow_set
[i
].borrowed_place
,
221 PlaceConflictBias
::NoOverlap
,
225 trans
.kill_all(definitely_conflicting_borrows
);
229 impl<'tcx
> dataflow
::AnalysisDomain
<'tcx
> for Borrows
<'_
, 'tcx
> {
230 type Idx
= BorrowIndex
;
232 const NAME
: &'
static str = "borrows";
234 fn bits_per_block(&self, _
: &mir
::Body
<'tcx
>) -> usize {
235 self.borrow_set
.len() * 2
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.
243 fn pretty_print_idx(&self, w
: &mut impl std
::io
::Write
, idx
: Self::Idx
) -> std
::io
::Result
<()> {
244 write
!(w
, "{:?}", self.location(idx
))
248 impl<'tcx
> dataflow
::GenKillAnalysis
<'tcx
> for Borrows
<'_
, 'tcx
> {
249 fn before_statement_effect(
251 trans
: &mut impl GenKill
<Self::Idx
>,
252 _statement
: &mir
::Statement
<'tcx
>,
255 self.kill_loans_out_of_scope_at_location(trans
, location
);
260 trans
: &mut impl GenKill
<Self::Idx
>,
261 stmt
: &mir
::Statement
<'tcx
>,
265 mir
::StatementKind
::Assign(box (lhs
, ref rhs
)) => {
266 if let mir
::Rvalue
::Ref(_
, _
, place
) = *rhs
{
267 if place
.ignore_borrow(
270 &self.borrow_set
.locals_state_at_exit
,
274 let index
= self.borrow_set
.get_index_of(&location
).unwrap_or_else(|| {
275 panic
!("could not find BorrowIndex for location {:?}", location
);
281 // Make sure there are no remaining borrows for variables
282 // that are assigned over.
283 self.kill_borrows_on_place(trans
, lhs
);
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
));
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
);
300 mir
::StatementKind
::FakeRead(..)
301 | mir
::StatementKind
::SetDiscriminant { .. }
302 | mir
::StatementKind
::StorageLive(..)
303 | mir
::StatementKind
::Retag { .. }
304 | mir
::StatementKind
::AscribeUserType(..)
305 | mir
::StatementKind
::Coverage(..)
306 | mir
::StatementKind
::Nop
=> {}
310 fn before_terminator_effect(
312 trans
: &mut impl GenKill
<Self::Idx
>,
313 _terminator
: &mir
::Terminator
<'tcx
>,
316 self.kill_loans_out_of_scope_at_location(trans
, location
);
319 fn terminator_effect(
321 trans
: &mut impl GenKill
<Self::Idx
>,
322 teminator
: &mir
::Terminator
<'tcx
>,
325 if let mir
::TerminatorKind
::InlineAsm { operands, .. }
= &teminator
.kind
{
327 if let mir
::InlineAsmOperand
::Out { place: Some(place), .. }
328 | mir
::InlineAsmOperand
::InOut { out_place: Some(place), .. }
= *op
330 self.kill_borrows_on_place(trans
, place
);
336 fn call_return_effect(
338 _trans
: &mut impl GenKill
<Self::Idx
>,
339 _block
: mir
::BasicBlock
,
340 _func
: &mir
::Operand
<'tcx
>,
341 _args
: &[mir
::Operand
<'tcx
>],
342 _dest_place
: mir
::Place
<'tcx
>,
347 impl<'a
, 'tcx
> BottomValue
for Borrows
<'a
, 'tcx
> {
348 /// bottom = nothing is reserved or activated yet;
349 const BOTTOM_VALUE
: bool
= false;