1 use rustc_data_structures
::fx
::{FxHashMap, FxHashSet}
;
2 use rustc_index
::bit_set
::HybridBitSet
;
3 use rustc_infer
::infer
::canonical
::QueryRegionConstraints
;
4 use rustc_middle
::mir
::{BasicBlock, Body, ConstraintCategory, Local, Location}
;
5 use rustc_middle
::ty
::{Ty, TypeFoldable}
;
6 use rustc_trait_selection
::traits
::query
::dropck_outlives
::DropckOutlivesResult
;
7 use rustc_trait_selection
::traits
::query
::type_op
::outlives
::DropckOutlives
;
8 use rustc_trait_selection
::traits
::query
::type_op
::TypeOp
;
11 use crate::dataflow
::impls
::MaybeInitializedPlaces
;
12 use crate::dataflow
::indexes
::MovePathIndex
;
13 use crate::dataflow
::move_paths
::{HasMoveData, MoveData}
;
14 use crate::dataflow
::ResultsCursor
;
16 use crate::borrow_check
::{
17 region_infer
::values
::{self, PointIndex, RegionValueElements}
,
18 type_check
::liveness
::local_use_map
::LocalUseMap
,
19 type_check
::liveness
::polonius
,
20 type_check
::NormalizeLocation
,
21 type_check
::TypeChecker
,
24 /// This is the heart of the liveness computation. For each variable X
25 /// that requires a liveness computation, it walks over all the uses
26 /// of X and does a reverse depth-first search ("trace") through the
27 /// MIR. This search stops when we find a definition of that variable.
28 /// The points visited in this search is the USE-LIVE set for the variable;
29 /// of those points is added to all the regions that appear in the variable's
32 /// We then also walks through each *drop* of those variables and does
33 /// another search, stopping when we reach a use or definition. This
34 /// is the DROP-LIVE set of points. Each of the points in the
35 /// DROP-LIVE set are to the liveness sets for regions found in the
36 /// `dropck_outlives` result of the variable's type (in particular,
37 /// this respects `#[may_dangle]` annotations).
39 typeck
: &mut TypeChecker
<'_
, 'tcx
>,
41 elements
: &Rc
<RegionValueElements
>,
42 flow_inits
: &mut ResultsCursor
<'mir
, 'tcx
, MaybeInitializedPlaces
<'mir
, 'tcx
>>,
43 move_data
: &MoveData
<'tcx
>,
44 live_locals
: Vec
<Local
>,
45 polonius_drop_used
: Option
<Vec
<(Local
, Location
)>>,
49 let local_use_map
= &LocalUseMap
::build(&live_locals
, elements
, body
);
51 let cx
= LivenessContext
{
58 drop_data
: FxHashMap
::default(),
61 let mut results
= LivenessResults
::new(cx
);
63 if let Some(drop_used
) = polonius_drop_used
{
64 results
.add_extra_drop_facts(drop_used
, live_locals
.iter().copied().collect())
67 results
.compute_for_all_locals(live_locals
);
70 /// Contextual state for the type-liveness generator.
71 struct LivenessContext
<'me
, 'typeck
, 'flow
, 'tcx
> {
72 /// Current type-checker, giving us our inference context etc.
73 typeck
: &'me
mut TypeChecker
<'typeck
, 'tcx
>,
75 /// Defines the `PointIndex` mapping
76 elements
: &'me RegionValueElements
,
78 /// MIR we are analyzing.
79 body
: &'me Body
<'tcx
>,
81 /// Mapping to/from the various indices used for initialization tracking.
82 move_data
: &'me MoveData
<'tcx
>,
84 /// Cache for the results of `dropck_outlives` query.
85 drop_data
: FxHashMap
<Ty
<'tcx
>, DropData
<'tcx
>>,
87 /// Results of dataflow tracking which variables (and paths) have been
89 flow_inits
: &'me
mut ResultsCursor
<'flow
, 'tcx
, MaybeInitializedPlaces
<'flow
, 'tcx
>>,
91 /// Index indicating where each variable is assigned, used, or
93 local_use_map
: &'me LocalUseMap
,
96 struct DropData
<'tcx
> {
97 dropck_result
: DropckOutlivesResult
<'tcx
>,
98 region_constraint_data
: Option
<Rc
<QueryRegionConstraints
<'tcx
>>>,
101 struct LivenessResults
<'me
, 'typeck
, 'flow
, 'tcx
> {
102 cx
: LivenessContext
<'me
, 'typeck
, 'flow
, 'tcx
>,
104 /// Set of points that define the current local.
105 defs
: HybridBitSet
<PointIndex
>,
107 /// Points where the current variable is "use live" -- meaning
108 /// that there is a future "full use" that may use its value.
109 use_live_at
: HybridBitSet
<PointIndex
>,
111 /// Points where the current variable is "drop live" -- meaning
112 /// that there is no future "full use" that may use its value, but
113 /// there is a future drop.
114 drop_live_at
: HybridBitSet
<PointIndex
>,
116 /// Locations where drops may occur.
117 drop_locations
: Vec
<Location
>,
119 /// Stack used when doing (reverse) DFS.
120 stack
: Vec
<PointIndex
>,
123 impl LivenessResults
<'me
, 'typeck
, 'flow
, 'tcx
> {
124 fn new(cx
: LivenessContext
<'me
, 'typeck
, 'flow
, 'tcx
>) -> Self {
125 let num_points
= cx
.elements
.num_points();
128 defs
: HybridBitSet
::new_empty(num_points
),
129 use_live_at
: HybridBitSet
::new_empty(num_points
),
130 drop_live_at
: HybridBitSet
::new_empty(num_points
),
131 drop_locations
: vec
![],
136 fn compute_for_all_locals(&mut self, live_locals
: Vec
<Local
>) {
137 for local
in live_locals
{
138 self.reset_local_state();
139 self.add_defs_for(local
);
140 self.compute_use_live_points_for(local
);
141 self.compute_drop_live_points_for(local
);
143 let local_ty
= self.cx
.body
.local_decls
[local
].ty
;
145 if !self.use_live_at
.is_empty() {
146 self.cx
.add_use_live_facts_for(local_ty
, &self.use_live_at
);
149 if !self.drop_live_at
.is_empty() {
150 self.cx
.add_drop_live_facts_for(
153 &self.drop_locations
,
160 /// Add extra drop facts needed for Polonius.
162 /// Add facts for all locals with free regions, since regions may outlive
163 /// the function body only at certain nodes in the CFG.
164 fn add_extra_drop_facts(
166 drop_used
: Vec
<(Local
, Location
)>,
167 live_locals
: FxHashSet
<Local
>,
169 let locations
= HybridBitSet
::new_empty(self.cx
.elements
.num_points());
171 for (local
, location
) in drop_used
{
172 if !live_locals
.contains(&local
) {
173 let local_ty
= self.cx
.body
.local_decls
[local
].ty
;
174 if local_ty
.has_free_regions() {
175 self.cx
.add_drop_live_facts_for(local
, local_ty
, &[location
], &locations
);
181 /// Clear the value of fields that are "per local variable".
182 fn reset_local_state(&mut self) {
184 self.use_live_at
.clear();
185 self.drop_live_at
.clear();
186 self.drop_locations
.clear();
187 assert
!(self.stack
.is_empty());
190 /// Adds the definitions of `local` into `self.defs`.
191 fn add_defs_for(&mut self, local
: Local
) {
192 for def
in self.cx
.local_use_map
.defs(local
) {
193 debug
!("- defined at {:?}", def
);
194 self.defs
.insert(def
);
198 /// Computes all points where local is "use live" -- meaning its
199 /// current value may be used later (except by a drop). This is
200 /// done by walking backwards from each use of `local` until we
201 /// find a `def` of local.
203 /// Requires `add_defs_for(local)` to have been executed.
204 fn compute_use_live_points_for(&mut self, local
: Local
) {
205 debug
!("compute_use_live_points_for(local={:?})", local
);
207 self.stack
.extend(self.cx
.local_use_map
.uses(local
));
208 while let Some(p
) = self.stack
.pop() {
209 if self.defs
.contains(p
) {
213 if self.use_live_at
.insert(p
) {
214 self.cx
.elements
.push_predecessors(self.cx
.body
, p
, &mut self.stack
)
219 /// Computes all points where local is "drop live" -- meaning its
220 /// current value may be dropped later (but not used). This is
221 /// done by iterating over the drops of `local` where `local` (or
222 /// some subpart of `local`) is initialized. For each such drop,
223 /// we walk backwards until we find a point where `local` is
224 /// either defined or use-live.
226 /// Requires `compute_use_live_points_for` and `add_defs_for` to
227 /// have been executed.
228 fn compute_drop_live_points_for(&mut self, local
: Local
) {
229 debug
!("compute_drop_live_points_for(local={:?})", local
);
231 let mpi
= self.cx
.move_data
.rev_lookup
.find_local(local
);
232 debug
!("compute_drop_live_points_for: mpi = {:?}", mpi
);
234 // Find the drops where `local` is initialized.
235 for drop_point
in self.cx
.local_use_map
.drops(local
) {
236 let location
= self.cx
.elements
.to_location(drop_point
);
237 debug_assert_eq
!(self.cx
.body
.terminator_loc(location
.block
), location
,);
239 if self.cx
.initialized_at_terminator(location
.block
, mpi
) {
240 if self.drop_live_at
.insert(drop_point
) {
241 self.drop_locations
.push(location
);
242 self.stack
.push(drop_point
);
247 debug
!("compute_drop_live_points_for: drop_locations={:?}", self.drop_locations
);
249 // Reverse DFS. But for drops, we do it a bit differently.
250 // The stack only ever stores *terminators of blocks*. Within
251 // a block, we walk back the statements in an inner loop.
252 while let Some(term_point
) = self.stack
.pop() {
253 self.compute_drop_live_points_for_block(mpi
, term_point
);
257 /// Executes one iteration of the drop-live analysis loop.
259 /// The parameter `mpi` is the `MovePathIndex` of the local variable
260 /// we are currently analyzing.
262 /// The point `term_point` represents some terminator in the MIR,
263 /// where the local `mpi` is drop-live on entry to that terminator.
265 /// This method adds all drop-live points within the block and --
266 /// where applicable -- pushes the terminators of preceding blocks
267 /// onto `self.stack`.
268 fn compute_drop_live_points_for_block(&mut self, mpi
: MovePathIndex
, term_point
: PointIndex
) {
270 "compute_drop_live_points_for_block(mpi={:?}, term_point={:?})",
271 self.cx
.move_data
.move_paths
[mpi
].place
,
272 self.cx
.elements
.to_location(term_point
),
275 // We are only invoked with terminators where `mpi` is
276 // drop-live on entry.
277 debug_assert
!(self.drop_live_at
.contains(term_point
));
279 // Otherwise, scan backwards through the statements in the
280 // block. One of them may be either a definition or use
282 let term_location
= self.cx
.elements
.to_location(term_point
);
283 debug_assert_eq
!(self.cx
.body
.terminator_loc(term_location
.block
), term_location
,);
284 let block
= term_location
.block
;
285 let entry_point
= self.cx
.elements
.entry_point(term_location
.block
);
286 for p
in (entry_point
..term_point
).rev() {
287 debug
!("compute_drop_live_points_for_block: p = {:?}", self.cx
.elements
.to_location(p
));
289 if self.defs
.contains(p
) {
290 debug
!("compute_drop_live_points_for_block: def site");
294 if self.use_live_at
.contains(p
) {
295 debug
!("compute_drop_live_points_for_block: use-live at {:?}", p
);
299 if !self.drop_live_at
.insert(p
) {
300 debug
!("compute_drop_live_points_for_block: already drop-live");
305 let body
= self.cx
.body
;
306 for &pred_block
in body
.predecessors()[block
].iter() {
307 debug
!("compute_drop_live_points_for_block: pred_block = {:?}", pred_block
,);
309 // Check whether the variable is (at least partially)
310 // initialized at the exit of this predecessor. If so, we
311 // want to enqueue it on our list. If not, go check the
314 // Note that we only need to check whether `live_local`
315 // became de-initialized at basic block boundaries. If it
316 // were to become de-initialized within the block, that
317 // would have been a "use-live" transition in the earlier
318 // loop, and we'd have returned already.
320 // NB. It's possible that the pred-block ends in a call
321 // which stores to the variable; in that case, the
322 // variable may be uninitialized "at exit" because this
323 // call only considers the *unconditional effects* of the
324 // terminator. *But*, in that case, the terminator is also
325 // a *definition* of the variable, in which case we want
326 // to stop the search anyhow. (But see Note 1 below.)
327 if !self.cx
.initialized_at_exit(pred_block
, mpi
) {
328 debug
!("compute_drop_live_points_for_block: not initialized");
332 let pred_term_loc
= self.cx
.body
.terminator_loc(pred_block
);
333 let pred_term_point
= self.cx
.elements
.point_from_location(pred_term_loc
);
335 // If the terminator of this predecessor either *assigns*
336 // our value or is a "normal use", then stop.
337 if self.defs
.contains(pred_term_point
) {
338 debug
!("compute_drop_live_points_for_block: defined at {:?}", pred_term_loc
);
342 if self.use_live_at
.contains(pred_term_point
) {
343 debug
!("compute_drop_live_points_for_block: use-live at {:?}", pred_term_loc
);
347 // Otherwise, we are drop-live on entry to the terminator,
349 if self.drop_live_at
.insert(pred_term_point
) {
350 debug
!("compute_drop_live_points_for_block: pushed to stack");
351 self.stack
.push(pred_term_point
);
355 // Note 1. There is a weird scenario that you might imagine
356 // being problematic here, but which actually cannot happen.
357 // The problem would be if we had a variable that *is* initialized
358 // (but dead) on entry to the terminator, and where the current value
359 // will be dropped in the case of unwind. In that case, we ought to
360 // consider `X` to be drop-live in between the last use and call.
361 // Here is the example:
366 // use(X); // last use
367 // ... // <-- X ought to be drop-live here
368 // X = call() goto BB1 unwind BB2
380 // However, the current code would, when walking back from BB2,
381 // simply stop and never explore BB0. This seems bad! But it turns
382 // out this code is flawed anyway -- note that the existing value of
383 // `X` would leak in the case where unwinding did *not* occur.
385 // What we *actually* generate is a store to a temporary
386 // for the call (`TMP = call()...`) and then a
387 // `DropAndReplace` to swap that with `X`
388 // (`DropAndReplace` has very particular semantics).
392 impl LivenessContext
<'_
, '_
, '_
, 'tcx
> {
393 /// Returns `true` if the local variable (or some part of it) is initialized at the current
394 /// cursor position. Callers should call one of the `seek` methods immediately before to point
395 /// the cursor to the desired location.
396 fn initialized_at_curr_loc(&self, mpi
: MovePathIndex
) -> bool
{
397 let state
= self.flow_inits
.get();
398 if state
.contains(mpi
) {
402 let move_paths
= &self.flow_inits
.analysis().move_data().move_paths
;
403 move_paths
[mpi
].find_descendant(&move_paths
, |mpi
| state
.contains(mpi
)).is_some()
406 /// Returns `true` if the local variable (or some part of it) is initialized in
407 /// the terminator of `block`. We need to check this to determine if a
408 /// DROP of some local variable will have an effect -- note that
409 /// drops, as they may unwind, are always terminators.
410 fn initialized_at_terminator(&mut self, block
: BasicBlock
, mpi
: MovePathIndex
) -> bool
{
411 self.flow_inits
.seek_before_primary_effect(self.body
.terminator_loc(block
));
412 self.initialized_at_curr_loc(mpi
)
415 /// Returns `true` if the path `mpi` (or some part of it) is initialized at
416 /// the exit of `block`.
418 /// **Warning:** Does not account for the result of `Call`
420 fn initialized_at_exit(&mut self, block
: BasicBlock
, mpi
: MovePathIndex
) -> bool
{
421 self.flow_inits
.seek_after_primary_effect(self.body
.terminator_loc(block
));
422 self.initialized_at_curr_loc(mpi
)
425 /// Stores the result that all regions in `value` are live for the
426 /// points `live_at`.
427 fn add_use_live_facts_for(
429 value
: impl TypeFoldable
<'tcx
>,
430 live_at
: &HybridBitSet
<PointIndex
>,
432 debug
!("add_use_live_facts_for(value={:?})", value
);
434 Self::make_all_regions_live(self.elements
, &mut self.typeck
, value
, live_at
)
437 /// Some variable with type `live_ty` is "drop live" at `location`
438 /// -- i.e., it may be dropped later. This means that *some* of
439 /// the regions in its type must be live at `location`. The
440 /// precise set will depend on the dropck constraints, and in
441 /// particular this takes `#[may_dangle]` into account.
442 fn add_drop_live_facts_for(
444 dropped_local
: Local
,
445 dropped_ty
: Ty
<'tcx
>,
446 drop_locations
: &[Location
],
447 live_at
: &HybridBitSet
<PointIndex
>,
450 "add_drop_live_constraint(\
451 dropped_local={:?}, \
453 drop_locations={:?}, \
458 values
::location_set_str(self.elements
, live_at
.iter()),
461 let drop_data
= self.drop_data
.entry(dropped_ty
).or_insert_with({
462 let typeck
= &mut self.typeck
;
463 move || Self::compute_drop_data(typeck
, dropped_ty
)
466 if let Some(data
) = &drop_data
.region_constraint_data
{
467 for &drop_location
in drop_locations
{
468 self.typeck
.push_region_constraints(
469 drop_location
.to_locations(),
470 ConstraintCategory
::Boring
,
476 drop_data
.dropck_result
.report_overflows(
477 self.typeck
.infcx
.tcx
,
478 self.body
.source_info(*drop_locations
.first().unwrap()).span
,
482 // All things in the `outlives` array may be touched by
483 // the destructor and must be live at this point.
484 for &kind
in &drop_data
.dropck_result
.kinds
{
485 Self::make_all_regions_live(self.elements
, &mut self.typeck
, kind
, live_at
);
487 polonius
::add_drop_of_var_derefs_origin(&mut self.typeck
, dropped_local
, &kind
);
491 fn make_all_regions_live(
492 elements
: &RegionValueElements
,
493 typeck
: &mut TypeChecker
<'_
, 'tcx
>,
494 value
: impl TypeFoldable
<'tcx
>,
495 live_at
: &HybridBitSet
<PointIndex
>,
497 debug
!("make_all_regions_live(value={:?})", value
);
499 "make_all_regions_live: live_at={}",
500 values
::location_set_str(elements
, live_at
.iter()),
503 let tcx
= typeck
.tcx();
504 tcx
.for_each_free_region(&value
, |live_region
| {
505 let live_region_vid
=
506 typeck
.borrowck_context
.universal_regions
.to_region_vid(live_region
);
510 .liveness_constraints
511 .add_elements(live_region_vid
, live_at
);
515 fn compute_drop_data(
516 typeck
: &mut TypeChecker
<'_
, 'tcx
>,
517 dropped_ty
: Ty
<'tcx
>,
518 ) -> DropData
<'tcx
> {
519 debug
!("compute_drop_data(dropped_ty={:?})", dropped_ty
,);
521 let param_env
= typeck
.param_env
;
522 let (dropck_result
, region_constraint_data
) =
523 param_env
.and(DropckOutlives
::new(dropped_ty
)).fully_perform(typeck
.infcx
).unwrap();
525 DropData { dropck_result, region_constraint_data }