]>
Commit | Line | Data |
---|---|---|
b7449926 | 1 | use rustc_data_structures::fx::FxHashMap; |
dfeec247 | 2 | use rustc_index::bit_set::BitSet; |
c295e0f8 XL |
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, GenKill}; | |
9 | use rustc_mir_dataflow::{Analysis, Direction, Results}; | |
10 | use std::fmt; | |
11 | use std::iter; | |
3b2f2976 | 12 | |
c295e0f8 | 13 | use crate::{ |
74b04a01 | 14 | places_conflict, BorrowSet, PlaceConflictBias, PlaceExt, RegionInferenceContext, ToRegionVid, |
60c5eb7d | 15 | }; |
3b2f2976 | 16 | |
c295e0f8 XL |
17 | /// A tuple with named fields that can hold either the results or the transient state of the |
18 | /// dataflow analyses used by the borrow checker. | |
19 | #[derive(Debug)] | |
20 | pub struct BorrowckAnalyses<B, U, E> { | |
21 | pub borrows: B, | |
22 | pub uninits: U, | |
23 | pub ever_inits: E, | |
24 | } | |
25 | ||
26 | /// The results of the dataflow analyses used by the borrow checker. | |
27 | pub type BorrowckResults<'mir, 'tcx> = BorrowckAnalyses< | |
28 | Results<'tcx, Borrows<'mir, 'tcx>>, | |
29 | Results<'tcx, MaybeUninitializedPlaces<'mir, 'tcx>>, | |
30 | Results<'tcx, EverInitializedPlaces<'mir, 'tcx>>, | |
31 | >; | |
32 | ||
33 | /// The transient state of the dataflow analyses used by the borrow checker. | |
34 | pub type BorrowckFlowState<'mir, 'tcx> = | |
35 | <BorrowckResults<'mir, 'tcx> as ResultsVisitable<'tcx>>::FlowState; | |
36 | ||
37 | macro_rules! impl_visitable { | |
38 | ( $( | |
39 | $T:ident { $( $field:ident : $A:ident ),* $(,)? } | |
40 | )* ) => { $( | |
41 | impl<'tcx, $($A),*, D: Direction> ResultsVisitable<'tcx> for $T<$( Results<'tcx, $A> ),*> | |
42 | where | |
43 | $( $A: Analysis<'tcx, Direction = D>, )* | |
44 | { | |
45 | type Direction = D; | |
46 | type FlowState = $T<$( $A::Domain ),*>; | |
47 | ||
48 | fn new_flow_state(&self, body: &mir::Body<'tcx>) -> Self::FlowState { | |
49 | $T { | |
50 | $( $field: self.$field.analysis.bottom_value(body) ),* | |
51 | } | |
52 | } | |
53 | ||
54 | fn reset_to_block_entry( | |
55 | &self, | |
56 | state: &mut Self::FlowState, | |
57 | block: BasicBlock, | |
58 | ) { | |
59 | $( state.$field.clone_from(&self.$field.entry_set_for_block(block)); )* | |
60 | } | |
61 | ||
62 | fn reconstruct_before_statement_effect( | |
63 | &self, | |
64 | state: &mut Self::FlowState, | |
65 | stmt: &mir::Statement<'tcx>, | |
66 | loc: Location, | |
67 | ) { | |
68 | $( self.$field.analysis | |
69 | .apply_before_statement_effect(&mut state.$field, stmt, loc); )* | |
70 | } | |
71 | ||
72 | fn reconstruct_statement_effect( | |
73 | &self, | |
74 | state: &mut Self::FlowState, | |
75 | stmt: &mir::Statement<'tcx>, | |
76 | loc: Location, | |
77 | ) { | |
78 | $( self.$field.analysis | |
79 | .apply_statement_effect(&mut state.$field, stmt, loc); )* | |
80 | } | |
81 | ||
82 | fn reconstruct_before_terminator_effect( | |
83 | &self, | |
84 | state: &mut Self::FlowState, | |
85 | term: &mir::Terminator<'tcx>, | |
86 | loc: Location, | |
87 | ) { | |
88 | $( self.$field.analysis | |
89 | .apply_before_terminator_effect(&mut state.$field, term, loc); )* | |
90 | } | |
91 | ||
92 | fn reconstruct_terminator_effect( | |
93 | &self, | |
94 | state: &mut Self::FlowState, | |
95 | term: &mir::Terminator<'tcx>, | |
96 | loc: Location, | |
97 | ) { | |
98 | $( self.$field.analysis | |
99 | .apply_terminator_effect(&mut state.$field, term, loc); )* | |
100 | } | |
101 | } | |
102 | )* } | |
103 | } | |
104 | ||
105 | impl_visitable! { | |
106 | BorrowckAnalyses { borrows: B, uninits: U, ever_inits: E } | |
107 | } | |
3b2f2976 | 108 | |
e74abb32 | 109 | rustc_index::newtype_index! { |
48663c56 XL |
110 | pub struct BorrowIndex { |
111 | DEBUG_FORMAT = "bw{}" | |
112 | } | |
113 | } | |
114 | ||
ff7c6d11 XL |
115 | /// `Borrows` stores the data used in the analyses that track the flow |
116 | /// of borrows. | |
117 | /// | |
118 | /// It uniquely identifies every borrow (`Rvalue::Ref`) by a | |
119 | /// `BorrowIndex`, and maps each such index to a `BorrowData` | |
120 | /// describing the borrow. These indexes are used for representing the | |
121 | /// borrows in compact bitvectors. | |
dc9dc135 XL |
122 | pub struct Borrows<'a, 'tcx> { |
123 | tcx: TyCtxt<'tcx>, | |
124 | body: &'a Body<'tcx>, | |
ff7c6d11 | 125 | |
6a06907d | 126 | borrow_set: &'a BorrowSet<'tcx>, |
94b46f34 | 127 | borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>, |
94b46f34 XL |
128 | } |
129 | ||
b7449926 XL |
130 | struct StackEntry { |
131 | bb: mir::BasicBlock, | |
132 | lo: usize, | |
133 | hi: usize, | |
b7449926 XL |
134 | } |
135 | ||
6a06907d XL |
136 | struct OutOfScopePrecomputer<'a, 'tcx> { |
137 | visited: BitSet<mir::BasicBlock>, | |
138 | visit_stack: Vec<StackEntry>, | |
139 | body: &'a Body<'tcx>, | |
140 | regioncx: &'a RegionInferenceContext<'tcx>, | |
141 | borrows_out_of_scope_at_location: FxHashMap<Location, Vec<BorrowIndex>>, | |
142 | } | |
143 | ||
144 | impl<'a, 'tcx> OutOfScopePrecomputer<'a, 'tcx> { | |
145 | fn new(body: &'a Body<'tcx>, regioncx: &'a RegionInferenceContext<'tcx>) -> Self { | |
146 | OutOfScopePrecomputer { | |
147 | visited: BitSet::new_empty(body.basic_blocks().len()), | |
148 | visit_stack: vec![], | |
149 | body, | |
150 | regioncx, | |
151 | borrows_out_of_scope_at_location: FxHashMap::default(), | |
94b46f34 | 152 | } |
6a06907d XL |
153 | } |
154 | } | |
94b46f34 | 155 | |
6a06907d XL |
156 | impl<'tcx> OutOfScopePrecomputer<'_, 'tcx> { |
157 | fn precompute_borrows_out_of_scope( | |
158 | &mut self, | |
159 | borrow_index: BorrowIndex, | |
160 | borrow_region: RegionVid, | |
161 | location: Location, | |
162 | ) { | |
163 | // We visit one BB at a time. The complication is that we may start in the | |
164 | // middle of the first BB visited (the one containing `location`), in which | |
165 | // case we may have to later on process the first part of that BB if there | |
166 | // is a path back to its start. | |
167 | ||
168 | // For visited BBs, we record the index of the first statement processed. | |
169 | // (In fully processed BBs this index is 0.) Note also that we add BBs to | |
170 | // `visited` once they are added to `stack`, before they are actually | |
171 | // processed, because this avoids the need to look them up again on | |
172 | // completion. | |
173 | self.visited.insert(location.block); | |
174 | ||
175 | let mut first_lo = location.statement_index; | |
176 | let first_hi = self.body[location.block].statements.len(); | |
177 | ||
178 | self.visit_stack.push(StackEntry { bb: location.block, lo: first_lo, hi: first_hi }); | |
179 | ||
180 | while let Some(StackEntry { bb, lo, hi }) = self.visit_stack.pop() { | |
181 | // If we process the first part of the first basic block (i.e. we encounter that block | |
182 | // for the second time), we no longer have to visit its successors again. | |
183 | let mut finished_early = bb == location.block && hi != first_hi; | |
184 | for i in lo..=hi { | |
185 | let location = Location { block: bb, statement_index: i }; | |
186 | // If region does not contain a point at the location, then add to list and skip | |
187 | // successor locations. | |
188 | if !self.regioncx.region_contains(borrow_region, location) { | |
189 | debug!("borrow {:?} gets killed at {:?}", borrow_index, location); | |
190 | self.borrows_out_of_scope_at_location | |
191 | .entry(location) | |
192 | .or_default() | |
193 | .push(borrow_index); | |
194 | finished_early = true; | |
195 | break; | |
196 | } | |
197 | } | |
198 | ||
199 | if !finished_early { | |
200 | // Add successor BBs to the work list, if necessary. | |
201 | let bb_data = &self.body[bb]; | |
202 | debug_assert!(hi == bb_data.statements.len()); | |
203 | for &succ_bb in bb_data.terminator().successors() { | |
c295e0f8 | 204 | if !self.visited.insert(succ_bb) { |
6a06907d XL |
205 | if succ_bb == location.block && first_lo > 0 { |
206 | // `succ_bb` has been seen before. If it wasn't | |
207 | // fully processed, add its first part to `stack` | |
208 | // for processing. | |
209 | self.visit_stack.push(StackEntry { | |
b7449926 XL |
210 | bb: succ_bb, |
211 | lo: 0, | |
6a06907d | 212 | hi: first_lo - 1, |
b7449926 | 213 | }); |
6a06907d XL |
214 | |
215 | // And update this entry with 0, to represent the | |
216 | // whole BB being processed. | |
217 | first_lo = 0; | |
b7449926 | 218 | } |
6a06907d | 219 | } else { |
b7449926 XL |
220 | // succ_bb hasn't been seen before. Add it to |
221 | // `stack` for processing. | |
6a06907d | 222 | self.visit_stack.push(StackEntry { |
b7449926 XL |
223 | bb: succ_bb, |
224 | lo: 0, | |
6a06907d | 225 | hi: self.body[succ_bb].statements.len(), |
b7449926 | 226 | }); |
6a06907d XL |
227 | } |
228 | } | |
94b46f34 XL |
229 | } |
230 | } | |
6a06907d XL |
231 | |
232 | self.visited.clear(); | |
94b46f34 | 233 | } |
3b2f2976 XL |
234 | } |
235 | ||
dc9dc135 | 236 | impl<'a, 'tcx> Borrows<'a, 'tcx> { |
83c7162d | 237 | crate fn new( |
dc9dc135 XL |
238 | tcx: TyCtxt<'tcx>, |
239 | body: &'a Body<'tcx>, | |
6a06907d XL |
240 | nonlexical_regioncx: &'a RegionInferenceContext<'tcx>, |
241 | borrow_set: &'a BorrowSet<'tcx>, | |
83c7162d | 242 | ) -> Self { |
6a06907d | 243 | let mut prec = OutOfScopePrecomputer::new(body, nonlexical_regioncx); |
3dfed10e | 244 | for (borrow_index, borrow_data) in borrow_set.iter_enumerated() { |
94b46f34 | 245 | let borrow_region = borrow_data.region.to_region_vid(); |
3dfed10e | 246 | let location = borrow_data.reserve_location; |
94b46f34 | 247 | |
6a06907d | 248 | prec.precompute_borrows_out_of_scope(borrow_index, borrow_region, location); |
94b46f34 XL |
249 | } |
250 | ||
83c7162d | 251 | Borrows { |
60c5eb7d XL |
252 | tcx, |
253 | body, | |
6a06907d XL |
254 | borrow_set, |
255 | borrows_out_of_scope_at_location: prec.borrows_out_of_scope_at_location, | |
0531ce1d | 256 | } |
3b2f2976 XL |
257 | } |
258 | ||
3b2f2976 | 259 | pub fn location(&self, idx: BorrowIndex) -> &Location { |
3dfed10e | 260 | &self.borrow_set[idx].reserve_location |
3b2f2976 | 261 | } |
ea8adc8c | 262 | |
abe05a73 | 263 | /// Add all borrows to the kill set, if those borrows are out of scope at `location`. |
a1dfa0c6 | 264 | /// That means they went out of a nonlexical scope |
dfeec247 XL |
265 | fn kill_loans_out_of_scope_at_location( |
266 | &self, | |
74b04a01 | 267 | trans: &mut impl GenKill<BorrowIndex>, |
dfeec247 XL |
268 | location: Location, |
269 | ) { | |
83c7162d | 270 | // NOTE: The state associated with a given `location` |
94b46f34 XL |
271 | // reflects the dataflow on entry to the statement. |
272 | // Iterate over each of the borrows that we've precomputed | |
273 | // to have went out of scope at this location and kill them. | |
83c7162d XL |
274 | // |
275 | // We are careful always to call this function *before* we | |
276 | // set up the gen-bits for the statement or | |
29967ef6 | 277 | // terminator. That way, if the effect of the statement or |
83c7162d XL |
278 | // terminator *does* introduce a new loan of the same |
279 | // region, then setting that gen-bit will override any | |
280 | // potential kill introduced here. | |
94b46f34 | 281 | if let Some(indices) = self.borrows_out_of_scope_at_location.get(&location) { |
74b04a01 | 282 | trans.kill_all(indices.iter().copied()); |
abe05a73 | 283 | } |
ea8adc8c | 284 | } |
3b2f2976 | 285 | |
0731742a | 286 | /// Kill any borrows that conflict with `place`. |
ba9703b0 | 287 | fn kill_borrows_on_place(&self, trans: &mut impl GenKill<BorrowIndex>, place: Place<'tcx>) { |
0731742a | 288 | debug!("kill_borrows_on_place: place={:?}", place); |
dc9dc135 | 289 | |
74b04a01 XL |
290 | let other_borrows_of_local = self |
291 | .borrow_set | |
292 | .local_map | |
293 | .get(&place.local) | |
294 | .into_iter() | |
295 | .flat_map(|bs| bs.iter()) | |
296 | .copied(); | |
dfeec247 XL |
297 | |
298 | // If the borrowed place is a local with no projections, all other borrows of this | |
299 | // local must conflict. This is purely an optimization so we don't have to call | |
300 | // `places_conflict` for every borrow. | |
301 | if place.projection.is_empty() { | |
302 | if !self.body.local_decls[place.local].is_ref_to_static() { | |
303 | trans.kill_all(other_borrows_of_local); | |
0731742a | 304 | } |
dfeec247 XL |
305 | return; |
306 | } | |
0731742a | 307 | |
dfeec247 XL |
308 | // By passing `PlaceConflictBias::NoOverlap`, we conservatively assume that any given |
309 | // pair of array indices are unequal, so that when `places_conflict` returns true, we | |
310 | // will be assured that two places being compared definitely denotes the same sets of | |
311 | // locations. | |
74b04a01 | 312 | let definitely_conflicting_borrows = other_borrows_of_local.filter(|&i| { |
dfeec247 XL |
313 | places_conflict( |
314 | self.tcx, | |
315 | self.body, | |
3dfed10e | 316 | self.borrow_set[i].borrowed_place, |
dfeec247 XL |
317 | place, |
318 | PlaceConflictBias::NoOverlap, | |
319 | ) | |
320 | }); | |
dc9dc135 | 321 | |
dfeec247 | 322 | trans.kill_all(definitely_conflicting_borrows); |
0531ce1d XL |
323 | } |
324 | } | |
325 | ||
c295e0f8 | 326 | impl<'tcx> rustc_mir_dataflow::AnalysisDomain<'tcx> for Borrows<'_, 'tcx> { |
1b1a35ee | 327 | type Domain = BitSet<BorrowIndex>; |
74b04a01 XL |
328 | |
329 | const NAME: &'static str = "borrows"; | |
330 | ||
1b1a35ee XL |
331 | fn bottom_value(&self, _: &mir::Body<'tcx>) -> Self::Domain { |
332 | // bottom = nothing is reserved or activated yet; | |
333 | BitSet::new_empty(self.borrow_set.len() * 2) | |
0531ce1d XL |
334 | } |
335 | ||
1b1a35ee | 336 | fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) { |
0531ce1d | 337 | // no borrows of code region_scopes have been taken prior to |
dc9dc135 | 338 | // function execution, so this method has no effect. |
0531ce1d | 339 | } |
74b04a01 | 340 | } |
0531ce1d | 341 | |
c295e0f8 | 342 | impl<'tcx> rustc_mir_dataflow::GenKillAnalysis<'tcx> for Borrows<'_, 'tcx> { |
1b1a35ee XL |
343 | type Idx = BorrowIndex; |
344 | ||
74b04a01 XL |
345 | fn before_statement_effect( |
346 | &self, | |
347 | trans: &mut impl GenKill<Self::Idx>, | |
348 | _statement: &mir::Statement<'tcx>, | |
349 | location: Location, | |
350 | ) { | |
351 | self.kill_loans_out_of_scope_at_location(trans, location); | |
352 | } | |
ff7c6d11 | 353 | |
74b04a01 XL |
354 | fn statement_effect( |
355 | &self, | |
356 | trans: &mut impl GenKill<Self::Idx>, | |
357 | stmt: &mir::Statement<'tcx>, | |
358 | location: Location, | |
359 | ) { | |
3b2f2976 | 360 | match stmt.kind { |
ba9703b0 XL |
361 | mir::StatementKind::Assign(box (lhs, ref rhs)) => { |
362 | if let mir::Rvalue::Ref(_, _, place) = *rhs { | |
b7449926 XL |
363 | if place.ignore_borrow( |
364 | self.tcx, | |
dc9dc135 | 365 | self.body, |
b7449926 XL |
366 | &self.borrow_set.locals_state_at_exit, |
367 | ) { | |
368 | return; | |
369 | } | |
3dfed10e | 370 | let index = self.borrow_set.get_index_of(&location).unwrap_or_else(|| { |
0531ce1d XL |
371 | panic!("could not find BorrowIndex for location {:?}", location); |
372 | }); | |
373 | ||
3dfed10e | 374 | trans.gen(index); |
ff7c6d11 | 375 | } |
e1599b0c XL |
376 | |
377 | // Make sure there are no remaining borrows for variables | |
378 | // that are assigned over. | |
379 | self.kill_borrows_on_place(trans, lhs); | |
ff7c6d11 XL |
380 | } |
381 | ||
382 | mir::StatementKind::StorageDead(local) => { | |
383 | // Make sure there are no remaining borrows for locals that | |
384 | // are gone out of scope. | |
ba9703b0 | 385 | self.kill_borrows_on_place(trans, Place::from(local)); |
ff7c6d11 XL |
386 | } |
387 | ||
ba9703b0 | 388 | mir::StatementKind::LlvmInlineAsm(ref asm) => { |
cdc7bbd5 | 389 | for (output, kind) in iter::zip(&*asm.outputs, &asm.asm.outputs) { |
ff7c6d11 | 390 | if !kind.is_indirect && !kind.is_rw { |
ba9703b0 | 391 | self.kill_borrows_on_place(trans, *output); |
ff7c6d11 | 392 | } |
3b2f2976 XL |
393 | } |
394 | } | |
395 | ||
dfeec247 XL |
396 | mir::StatementKind::FakeRead(..) |
397 | | mir::StatementKind::SetDiscriminant { .. } | |
398 | | mir::StatementKind::StorageLive(..) | |
399 | | mir::StatementKind::Retag { .. } | |
400 | | mir::StatementKind::AscribeUserType(..) | |
3dfed10e | 401 | | mir::StatementKind::Coverage(..) |
6a06907d | 402 | | mir::StatementKind::CopyNonOverlapping(..) |
dfeec247 | 403 | | mir::StatementKind::Nop => {} |
3b2f2976 | 404 | } |
ff7c6d11 | 405 | } |
abe05a73 | 406 | |
74b04a01 XL |
407 | fn before_terminator_effect( |
408 | &self, | |
409 | trans: &mut impl GenKill<Self::Idx>, | |
410 | _terminator: &mir::Terminator<'tcx>, | |
411 | location: Location, | |
412 | ) { | |
dc9dc135 | 413 | self.kill_loans_out_of_scope_at_location(trans, location); |
ff7c6d11 XL |
414 | } |
415 | ||
74b04a01 XL |
416 | fn terminator_effect( |
417 | &self, | |
f9f354fc XL |
418 | trans: &mut impl GenKill<Self::Idx>, |
419 | teminator: &mir::Terminator<'tcx>, | |
420 | _location: Location, | |
74b04a01 | 421 | ) { |
f9f354fc XL |
422 | if let mir::TerminatorKind::InlineAsm { operands, .. } = &teminator.kind { |
423 | for op in operands { | |
424 | if let mir::InlineAsmOperand::Out { place: Some(place), .. } | |
425 | | mir::InlineAsmOperand::InOut { out_place: Some(place), .. } = *op | |
426 | { | |
427 | self.kill_borrows_on_place(trans, place); | |
428 | } | |
429 | } | |
430 | } | |
74b04a01 | 431 | } |
ff7c6d11 | 432 | |
74b04a01 | 433 | fn call_return_effect( |
0731742a | 434 | &self, |
74b04a01 XL |
435 | _trans: &mut impl GenKill<Self::Idx>, |
436 | _block: mir::BasicBlock, | |
437 | _func: &mir::Operand<'tcx>, | |
438 | _args: &[mir::Operand<'tcx>], | |
ba9703b0 | 439 | _dest_place: mir::Place<'tcx>, |
0731742a | 440 | ) { |
ff7c6d11 XL |
441 | } |
442 | } | |
443 | ||
1b1a35ee XL |
444 | impl DebugWithContext<Borrows<'_, '_>> for BorrowIndex { |
445 | fn fmt_with(&self, ctxt: &Borrows<'_, '_>, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
446 | write!(f, "{:?}", ctxt.location(*self)) | |
447 | } | |
3b2f2976 | 448 | } |