1 use rustc_data_structures
::fx
::FxHashMap
;
2 use rustc_index
::bit_set
::BitSet
;
3 use rustc_middle
::mir
::{self, BasicBlock, Body, Location, Place}
;
4 use rustc_middle
::ty
::RegionVid
;
5 use rustc_middle
::ty
::TyCtxt
;
6 use rustc_mir_dataflow
::impls
::{EverInitializedPlaces, MaybeUninitializedPlaces}
;
7 use rustc_mir_dataflow
::ResultsVisitable
;
8 use rustc_mir_dataflow
::{self, fmt::DebugWithContext, CallReturnPlaces, GenKill}
;
9 use rustc_mir_dataflow
::{Analysis, Direction, Results}
;
13 places_conflict
, BorrowSet
, PlaceConflictBias
, PlaceExt
, RegionInferenceContext
, ToRegionVid
,
16 /// A tuple with named fields that can hold either the results or the transient state of the
17 /// dataflow analyses used by the borrow checker.
19 pub struct BorrowckAnalyses
<B
, U
, E
> {
25 /// The results of the dataflow analyses used by the borrow checker.
26 pub type BorrowckResults
<'mir
, 'tcx
> = BorrowckAnalyses
<
27 Results
<'tcx
, Borrows
<'mir
, 'tcx
>>,
28 Results
<'tcx
, MaybeUninitializedPlaces
<'mir
, 'tcx
>>,
29 Results
<'tcx
, EverInitializedPlaces
<'mir
, 'tcx
>>,
32 /// The transient state of the dataflow analyses used by the borrow checker.
33 pub type BorrowckFlowState
<'mir
, 'tcx
> =
34 <BorrowckResults
<'mir
, 'tcx
> as ResultsVisitable
<'tcx
>>::FlowState
;
36 macro_rules
! impl_visitable
{
38 $T
:ident { $( $field:ident : $A:ident ),* $(,)? }
40 impl<'tcx
, $
($A
),*, D
: Direction
> ResultsVisitable
<'tcx
> for $T
<$
( Results
<'tcx
, $A
> ),*>
42 $
( $A
: Analysis
<'tcx
, Direction
= D
>, )*
45 type FlowState
= $T
<$
( $A
::Domain
),*>;
47 fn new_flow_state(&self, body
: &mir
::Body
<'tcx
>) -> Self::FlowState
{
49 $
( $field
: self.$field
.analysis
.bottom_value(body
) ),*
53 fn reset_to_block_entry(
55 state
: &mut Self::FlowState
,
58 $
( state
.$field
.clone_from(&self.$field
.entry_set_for_block(block
)); )*
61 fn reconstruct_before_statement_effect(
63 state
: &mut Self::FlowState
,
64 stmt
: &mir
::Statement
<'tcx
>,
67 $
( self.$field
.analysis
68 .apply_before_statement_effect(&mut state
.$field
, stmt
, loc
); )*
71 fn reconstruct_statement_effect(
73 state
: &mut Self::FlowState
,
74 stmt
: &mir
::Statement
<'tcx
>,
77 $
( self.$field
.analysis
78 .apply_statement_effect(&mut state
.$field
, stmt
, loc
); )*
81 fn reconstruct_before_terminator_effect(
83 state
: &mut Self::FlowState
,
84 term
: &mir
::Terminator
<'tcx
>,
87 $
( self.$field
.analysis
88 .apply_before_terminator_effect(&mut state
.$field
, term
, loc
); )*
91 fn reconstruct_terminator_effect(
93 state
: &mut Self::FlowState
,
94 term
: &mir
::Terminator
<'tcx
>,
97 $
( self.$field
.analysis
98 .apply_terminator_effect(&mut state
.$field
, term
, loc
); )*
105 BorrowckAnalyses { borrows: B, uninits: U, ever_inits: E }
108 rustc_index
::newtype_index
! {
109 pub struct BorrowIndex
{
110 DEBUG_FORMAT
= "bw{}"
114 /// `Borrows` stores the data used in the analyses that track the flow
117 /// It uniquely identifies every borrow (`Rvalue::Ref`) by a
118 /// `BorrowIndex`, and maps each such index to a `BorrowData`
119 /// describing the borrow. These indexes are used for representing the
120 /// borrows in compact bitvectors.
121 pub struct Borrows
<'a
, 'tcx
> {
123 body
: &'a Body
<'tcx
>,
125 borrow_set
: &'a BorrowSet
<'tcx
>,
126 borrows_out_of_scope_at_location
: FxHashMap
<Location
, Vec
<BorrowIndex
>>,
135 struct OutOfScopePrecomputer
<'a
, 'tcx
> {
136 visited
: BitSet
<mir
::BasicBlock
>,
137 visit_stack
: Vec
<StackEntry
>,
138 body
: &'a Body
<'tcx
>,
139 regioncx
: &'a RegionInferenceContext
<'tcx
>,
140 borrows_out_of_scope_at_location
: FxHashMap
<Location
, Vec
<BorrowIndex
>>,
143 impl<'a
, 'tcx
> OutOfScopePrecomputer
<'a
, 'tcx
> {
144 fn new(body
: &'a Body
<'tcx
>, regioncx
: &'a RegionInferenceContext
<'tcx
>) -> Self {
145 OutOfScopePrecomputer
{
146 visited
: BitSet
::new_empty(body
.basic_blocks().len()),
150 borrows_out_of_scope_at_location
: FxHashMap
::default(),
155 impl<'tcx
> OutOfScopePrecomputer
<'_
, 'tcx
> {
156 fn precompute_borrows_out_of_scope(
158 borrow_index
: BorrowIndex
,
159 borrow_region
: RegionVid
,
162 // We visit one BB at a time. The complication is that we may start in the
163 // middle of the first BB visited (the one containing `location`), in which
164 // case we may have to later on process the first part of that BB if there
165 // is a path back to its start.
167 // For visited BBs, we record the index of the first statement processed.
168 // (In fully processed BBs this index is 0.) Note also that we add BBs to
169 // `visited` once they are added to `stack`, before they are actually
170 // processed, because this avoids the need to look them up again on
172 self.visited
.insert(location
.block
);
174 let mut first_lo
= location
.statement_index
;
175 let first_hi
= self.body
[location
.block
].statements
.len();
177 self.visit_stack
.push(StackEntry { bb: location.block, lo: first_lo, hi: first_hi }
);
179 while let Some(StackEntry { bb, lo, hi }
) = self.visit_stack
.pop() {
180 // If we process the first part of the first basic block (i.e. we encounter that block
181 // for the second time), we no longer have to visit its successors again.
182 let mut finished_early
= bb
== location
.block
&& hi
!= first_hi
;
184 let location
= Location { block: bb, statement_index: i }
;
185 // If region does not contain a point at the location, then add to list and skip
186 // successor locations.
187 if !self.regioncx
.region_contains(borrow_region
, location
) {
188 debug
!("borrow {:?} gets killed at {:?}", borrow_index
, location
);
189 self.borrows_out_of_scope_at_location
193 finished_early
= true;
199 // Add successor BBs to the work list, if necessary.
200 let bb_data
= &self.body
[bb
];
201 debug_assert
!(hi
== bb_data
.statements
.len());
202 for &succ_bb
in bb_data
.terminator().successors() {
203 if !self.visited
.insert(succ_bb
) {
204 if succ_bb
== location
.block
&& first_lo
> 0 {
205 // `succ_bb` has been seen before. If it wasn't
206 // fully processed, add its first part to `stack`
208 self.visit_stack
.push(StackEntry
{
214 // And update this entry with 0, to represent the
215 // whole BB being processed.
219 // succ_bb hasn't been seen before. Add it to
220 // `stack` for processing.
221 self.visit_stack
.push(StackEntry
{
224 hi
: self.body
[succ_bb
].statements
.len(),
231 self.visited
.clear();
235 impl<'a
, 'tcx
> Borrows
<'a
, 'tcx
> {
238 body
: &'a Body
<'tcx
>,
239 nonlexical_regioncx
: &'a RegionInferenceContext
<'tcx
>,
240 borrow_set
: &'a BorrowSet
<'tcx
>,
242 let mut prec
= OutOfScopePrecomputer
::new(body
, nonlexical_regioncx
);
243 for (borrow_index
, borrow_data
) in borrow_set
.iter_enumerated() {
244 let borrow_region
= borrow_data
.region
.to_region_vid();
245 let location
= borrow_data
.reserve_location
;
247 prec
.precompute_borrows_out_of_scope(borrow_index
, borrow_region
, location
);
254 borrows_out_of_scope_at_location
: prec
.borrows_out_of_scope_at_location
,
258 pub fn location(&self, idx
: BorrowIndex
) -> &Location
{
259 &self.borrow_set
[idx
].reserve_location
262 /// Add all borrows to the kill set, if those borrows are out of scope at `location`.
263 /// That means they went out of a nonlexical scope
264 fn kill_loans_out_of_scope_at_location(
266 trans
: &mut impl GenKill
<BorrowIndex
>,
269 // NOTE: The state associated with a given `location`
270 // reflects the dataflow on entry to the statement.
271 // Iterate over each of the borrows that we've precomputed
272 // to have went out of scope at this location and kill them.
274 // We are careful always to call this function *before* we
275 // set up the gen-bits for the statement or
276 // terminator. That way, if the effect of the statement or
277 // terminator *does* introduce a new loan of the same
278 // region, then setting that gen-bit will override any
279 // potential kill introduced here.
280 if let Some(indices
) = self.borrows_out_of_scope_at_location
.get(&location
) {
281 trans
.kill_all(indices
.iter().copied());
285 /// Kill any borrows that conflict with `place`.
286 fn kill_borrows_on_place(&self, trans
: &mut impl GenKill
<BorrowIndex
>, place
: Place
<'tcx
>) {
287 debug
!("kill_borrows_on_place: place={:?}", place
);
289 let other_borrows_of_local
= self
294 .flat_map(|bs
| bs
.iter())
297 // If the borrowed place is a local with no projections, all other borrows of this
298 // local must conflict. This is purely an optimization so we don't have to call
299 // `places_conflict` for every borrow.
300 if place
.projection
.is_empty() {
301 if !self.body
.local_decls
[place
.local
].is_ref_to_static() {
302 trans
.kill_all(other_borrows_of_local
);
307 // By passing `PlaceConflictBias::NoOverlap`, we conservatively assume that any given
308 // pair of array indices are unequal, so that when `places_conflict` returns true, we
309 // will be assured that two places being compared definitely denotes the same sets of
311 let definitely_conflicting_borrows
= other_borrows_of_local
.filter(|&i
| {
315 self.borrow_set
[i
].borrowed_place
,
317 PlaceConflictBias
::NoOverlap
,
321 trans
.kill_all(definitely_conflicting_borrows
);
325 impl<'tcx
> rustc_mir_dataflow
::AnalysisDomain
<'tcx
> for Borrows
<'_
, 'tcx
> {
326 type Domain
= BitSet
<BorrowIndex
>;
328 const NAME
: &'
static str = "borrows";
330 fn bottom_value(&self, _
: &mir
::Body
<'tcx
>) -> Self::Domain
{
331 // bottom = nothing is reserved or activated yet;
332 BitSet
::new_empty(self.borrow_set
.len() * 2)
335 fn initialize_start_block(&self, _
: &mir
::Body
<'tcx
>, _
: &mut Self::Domain
) {
336 // no borrows of code region_scopes have been taken prior to
337 // function execution, so this method has no effect.
341 impl<'tcx
> rustc_mir_dataflow
::GenKillAnalysis
<'tcx
> for Borrows
<'_
, 'tcx
> {
342 type Idx
= BorrowIndex
;
344 fn before_statement_effect(
346 trans
: &mut impl GenKill
<Self::Idx
>,
347 _statement
: &mir
::Statement
<'tcx
>,
350 self.kill_loans_out_of_scope_at_location(trans
, location
);
355 trans
: &mut impl GenKill
<Self::Idx
>,
356 stmt
: &mir
::Statement
<'tcx
>,
360 mir
::StatementKind
::Assign(box (lhs
, ref rhs
)) => {
361 if let mir
::Rvalue
::Ref(_
, _
, place
) = *rhs
{
362 if place
.ignore_borrow(
365 &self.borrow_set
.locals_state_at_exit
,
369 let index
= self.borrow_set
.get_index_of(&location
).unwrap_or_else(|| {
370 panic
!("could not find BorrowIndex for location {:?}", location
);
376 // Make sure there are no remaining borrows for variables
377 // that are assigned over.
378 self.kill_borrows_on_place(trans
, lhs
);
381 mir
::StatementKind
::StorageDead(local
) => {
382 // Make sure there are no remaining borrows for locals that
383 // are gone out of scope.
384 self.kill_borrows_on_place(trans
, Place
::from(local
));
387 mir
::StatementKind
::FakeRead(..)
388 | mir
::StatementKind
::SetDiscriminant { .. }
389 | mir
::StatementKind
::StorageLive(..)
390 | mir
::StatementKind
::Retag { .. }
391 | mir
::StatementKind
::AscribeUserType(..)
392 | mir
::StatementKind
::Coverage(..)
393 | mir
::StatementKind
::CopyNonOverlapping(..)
394 | mir
::StatementKind
::Nop
=> {}
398 fn before_terminator_effect(
400 trans
: &mut impl GenKill
<Self::Idx
>,
401 _terminator
: &mir
::Terminator
<'tcx
>,
404 self.kill_loans_out_of_scope_at_location(trans
, location
);
407 fn terminator_effect(
409 trans
: &mut impl GenKill
<Self::Idx
>,
410 terminator
: &mir
::Terminator
<'tcx
>,
413 if let mir
::TerminatorKind
::InlineAsm { operands, .. }
= &terminator
.kind
{
415 if let mir
::InlineAsmOperand
::Out { place: Some(place), .. }
416 | mir
::InlineAsmOperand
::InOut { out_place: Some(place), .. }
= *op
418 self.kill_borrows_on_place(trans
, place
);
424 fn call_return_effect(
426 _trans
: &mut impl GenKill
<Self::Idx
>,
427 _block
: mir
::BasicBlock
,
428 _return_places
: CallReturnPlaces
<'_
, 'tcx
>,
433 impl DebugWithContext
<Borrows
<'_
, '_
>> for BorrowIndex
{
434 fn fmt_with(&self, ctxt
: &Borrows
<'_
, '_
>, f
: &mut fmt
::Formatter
<'_
>) -> fmt
::Result
{
435 write
!(f
, "{:?}", ctxt
.location(*self))