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, TypeOpOutput};
11 use rustc_mir_dataflow::impls::MaybeInitializedPlaces;
12 use rustc_mir_dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex};
13 use rustc_mir_dataflow::ResultsCursor;
16 region_infer::values::{self, PointIndex, RegionValueElements},
17 type_check::liveness::local_use_map::LocalUseMap,
18 type_check::liveness::polonius,
19 type_check::NormalizeLocation,
20 type_check::TypeChecker,
23 /// This is the heart of the liveness computation. For each variable X
24 /// that requires a liveness computation, it walks over all the uses
25 /// of X and does a reverse depth-first search ("trace") through the
26 /// MIR. This search stops when we find a definition of that variable.
27 /// The points visited in this search is the USE-LIVE set for the variable;
28 /// of those points is added to all the regions that appear in the variable's
31 /// We then also walks through each *drop* of those variables and does
32 /// another search, stopping when we reach a use or definition. This
33 /// is the DROP-LIVE set of points. Each of the points in the
34 /// DROP-LIVE set are to the liveness sets for regions found in the
35 /// `dropck_outlives` result of the variable's type (in particular,
36 /// this respects `#[may_dangle]` annotations).
38 typeck: &mut TypeChecker<'_, 'tcx>,
40 elements: &Rc<RegionValueElements>,
41 flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>,
42 move_data: &MoveData<'tcx>,
43 live_locals: Vec<Local>,
44 polonius_drop_used: Option<Vec<(Local, Location)>>,
48 let local_use_map = &LocalUseMap::build(&live_locals, elements, body);
50 let cx = LivenessContext {
57 drop_data: FxHashMap::default(),
60 let mut results = LivenessResults::new(cx);
62 if let Some(drop_used) = polonius_drop_used {
63 results.add_extra_drop_facts(drop_used, live_locals.iter().copied().collect())
66 results.compute_for_all_locals(live_locals);
69 /// Contextual state for the type-liveness generator.
70 struct LivenessContext<'me, 'typeck, 'flow, 'tcx> {
71 /// Current type-checker, giving us our inference context etc.
72 typeck: &'me mut TypeChecker<'typeck, 'tcx>,
74 /// Defines the `PointIndex` mapping
75 elements: &'me RegionValueElements,
77 /// MIR we are analyzing.
78 body: &'me Body<'tcx>,
80 /// Mapping to/from the various indices used for initialization tracking.
81 move_data: &'me MoveData<'tcx>,
83 /// Cache for the results of `dropck_outlives` query.
84 drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>,
86 /// Results of dataflow tracking which variables (and paths) have been
88 flow_inits: &'me mut ResultsCursor<'flow, 'tcx, MaybeInitializedPlaces<'flow, 'tcx>>,
90 /// Index indicating where each variable is assigned, used, or
92 local_use_map: &'me LocalUseMap,
95 struct DropData<'tcx> {
96 dropck_result: DropckOutlivesResult<'tcx>,
97 region_constraint_data: Option<Rc<QueryRegionConstraints<'tcx>>>,
100 struct LivenessResults<'me, 'typeck, 'flow, 'tcx> {
101 cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>,
103 /// Set of points that define the current local.
104 defs: HybridBitSet<PointIndex>,
106 /// Points where the current variable is "use live" -- meaning
107 /// that there is a future "full use" that may use its value.
108 use_live_at: HybridBitSet<PointIndex>,
110 /// Points where the current variable is "drop live" -- meaning
111 /// that there is no future "full use" that may use its value, but
112 /// there is a future drop.
113 drop_live_at: HybridBitSet<PointIndex>,
115 /// Locations where drops may occur.
116 drop_locations: Vec<Location>,
118 /// Stack used when doing (reverse) DFS.
119 stack: Vec<PointIndex>,
122 impl LivenessResults<'me, 'typeck, 'flow, 'tcx> {
123 fn new(cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>) -> Self {
124 let num_points = cx.elements.num_points();
127 defs: HybridBitSet::new_empty(num_points),
128 use_live_at: HybridBitSet::new_empty(num_points),
129 drop_live_at: HybridBitSet::new_empty(num_points),
130 drop_locations: vec![],
135 fn compute_for_all_locals(&mut self, live_locals: Vec<Local>) {
136 for local in live_locals {
137 self.reset_local_state();
138 self.add_defs_for(local);
139 self.compute_use_live_points_for(local);
140 self.compute_drop_live_points_for(local);
142 let local_ty = self.cx.body.local_decls[local].ty;
144 if !self.use_live_at.is_empty() {
145 self.cx.add_use_live_facts_for(local_ty, &self.use_live_at);
148 if !self.drop_live_at.is_empty() {
149 self.cx.add_drop_live_facts_for(
152 &self.drop_locations,
159 /// Add extra drop facts needed for Polonius.
161 /// Add facts for all locals with free regions, since regions may outlive
162 /// the function body only at certain nodes in the CFG.
163 fn add_extra_drop_facts(
165 drop_used: Vec<(Local, Location)>,
166 live_locals: FxHashSet<Local>,
168 let locations = HybridBitSet::new_empty(self.cx.elements.num_points());
170 for (local, location) in drop_used {
171 if !live_locals.contains(&local) {
172 let local_ty = self.cx.body.local_decls[local].ty;
173 if local_ty.has_free_regions(self.cx.typeck.tcx()) {
174 self.cx.add_drop_live_facts_for(local, local_ty, &[location], &locations);
180 /// Clear the value of fields that are "per local variable".
181 fn reset_local_state(&mut self) {
183 self.use_live_at.clear();
184 self.drop_live_at.clear();
185 self.drop_locations.clear();
186 assert!(self.stack.is_empty());
189 /// Adds the definitions of `local` into `self.defs`.
190 fn add_defs_for(&mut self, local: Local) {
191 for def in self.cx.local_use_map.defs(local) {
192 debug!("- defined at {:?}", def);
193 self.defs.insert(def);
197 /// Computes all points where local is "use live" -- meaning its
198 /// current value may be used later (except by a drop). This is
199 /// done by walking backwards from each use of `local` until we
200 /// find a `def` of local.
202 /// Requires `add_defs_for(local)` to have been executed.
203 fn compute_use_live_points_for(&mut self, local: Local) {
204 debug!("compute_use_live_points_for(local={:?})", local);
206 self.stack.extend(self.cx.local_use_map.uses(local));
207 while let Some(p) = self.stack.pop() {
208 // We are live in this block from the closest to us of:
210 // * Inclusively, the block start
211 // * Exclusively, the previous definition (if it's in this block)
212 // * Exclusively, the previous live_at setting (an optimization)
213 let block_start = self.cx.elements.to_block_start(p);
214 let previous_defs = self.defs.last_set_in(block_start..=p);
215 let previous_live_at = self.use_live_at.last_set_in(block_start..=p);
217 let exclusive_start = match (previous_defs, previous_live_at) {
218 (Some(a), Some(b)) => Some(std::cmp::max(a, b)),
219 (Some(a), None) | (None, Some(a)) => Some(a),
220 (None, None) => None,
223 if let Some(exclusive) = exclusive_start {
224 self.use_live_at.insert_range(exclusive + 1..=p);
226 // If we have a bound after the start of the block, we should
227 // not add the predecessors for this block.
230 // Add all the elements of this block.
231 self.use_live_at.insert_range(block_start..=p);
233 // Then add the predecessors for this block, which are the
234 // terminators of predecessor basic blocks. Push those onto the
235 // stack so that the next iteration(s) will process them.
237 let block = self.cx.elements.to_location(block_start).block;
239 self.cx.body.predecessors()[block]
241 .map(|&pred_bb| self.cx.body.terminator_loc(pred_bb))
242 .map(|pred_loc| self.cx.elements.point_from_location(pred_loc)),
248 /// Computes all points where local is "drop live" -- meaning its
249 /// current value may be dropped later (but not used). This is
250 /// done by iterating over the drops of `local` where `local` (or
251 /// some subpart of `local`) is initialized. For each such drop,
252 /// we walk backwards until we find a point where `local` is
253 /// either defined or use-live.
255 /// Requires `compute_use_live_points_for` and `add_defs_for` to
256 /// have been executed.
257 fn compute_drop_live_points_for(&mut self, local: Local) {
258 debug!("compute_drop_live_points_for(local={:?})", local);
260 let mpi = self.cx.move_data.rev_lookup.find_local(local);
261 debug!("compute_drop_live_points_for: mpi = {:?}", mpi);
263 // Find the drops where `local` is initialized.
264 for drop_point in self.cx.local_use_map.drops(local) {
265 let location = self.cx.elements.to_location(drop_point);
266 debug_assert_eq!(self.cx.body.terminator_loc(location.block), location,);
268 if self.cx.initialized_at_terminator(location.block, mpi) {
269 if self.drop_live_at.insert(drop_point) {
270 self.drop_locations.push(location);
271 self.stack.push(drop_point);
276 debug!("compute_drop_live_points_for: drop_locations={:?}", self.drop_locations);
278 // Reverse DFS. But for drops, we do it a bit differently.
279 // The stack only ever stores *terminators of blocks*. Within
280 // a block, we walk back the statements in an inner loop.
281 while let Some(term_point) = self.stack.pop() {
282 self.compute_drop_live_points_for_block(mpi, term_point);
286 /// Executes one iteration of the drop-live analysis loop.
288 /// The parameter `mpi` is the `MovePathIndex` of the local variable
289 /// we are currently analyzing.
291 /// The point `term_point` represents some terminator in the MIR,
292 /// where the local `mpi` is drop-live on entry to that terminator.
294 /// This method adds all drop-live points within the block and --
295 /// where applicable -- pushes the terminators of preceding blocks
296 /// onto `self.stack`.
297 fn compute_drop_live_points_for_block(&mut self, mpi: MovePathIndex, term_point: PointIndex) {
299 "compute_drop_live_points_for_block(mpi={:?}, term_point={:?})",
300 self.cx.move_data.move_paths[mpi].place,
301 self.cx.elements.to_location(term_point),
304 // We are only invoked with terminators where `mpi` is
305 // drop-live on entry.
306 debug_assert!(self.drop_live_at.contains(term_point));
308 // Otherwise, scan backwards through the statements in the
309 // block. One of them may be either a definition or use
311 let term_location = self.cx.elements.to_location(term_point);
312 debug_assert_eq!(self.cx.body.terminator_loc(term_location.block), term_location,);
313 let block = term_location.block;
314 let entry_point = self.cx.elements.entry_point(term_location.block);
315 for p in (entry_point..term_point).rev() {
316 debug!("compute_drop_live_points_for_block: p = {:?}", self.cx.elements.to_location(p));
318 if self.defs.contains(p) {
319 debug!("compute_drop_live_points_for_block: def site");
323 if self.use_live_at.contains(p) {
324 debug!("compute_drop_live_points_for_block: use-live at {:?}", p);
328 if !self.drop_live_at.insert(p) {
329 debug!("compute_drop_live_points_for_block: already drop-live");
334 let body = self.cx.body;
335 for &pred_block in body.predecessors()[block].iter() {
336 debug!("compute_drop_live_points_for_block: pred_block = {:?}", pred_block,);
338 // Check whether the variable is (at least partially)
339 // initialized at the exit of this predecessor. If so, we
340 // want to enqueue it on our list. If not, go check the
343 // Note that we only need to check whether `live_local`
344 // became de-initialized at basic block boundaries. If it
345 // were to become de-initialized within the block, that
346 // would have been a "use-live" transition in the earlier
347 // loop, and we'd have returned already.
349 // NB. It's possible that the pred-block ends in a call
350 // which stores to the variable; in that case, the
351 // variable may be uninitialized "at exit" because this
352 // call only considers the *unconditional effects* of the
353 // terminator. *But*, in that case, the terminator is also
354 // a *definition* of the variable, in which case we want
355 // to stop the search anyhow. (But see Note 1 below.)
356 if !self.cx.initialized_at_exit(pred_block, mpi) {
357 debug!("compute_drop_live_points_for_block: not initialized");
361 let pred_term_loc = self.cx.body.terminator_loc(pred_block);
362 let pred_term_point = self.cx.elements.point_from_location(pred_term_loc);
364 // If the terminator of this predecessor either *assigns*
365 // our value or is a "normal use", then stop.
366 if self.defs.contains(pred_term_point) {
367 debug!("compute_drop_live_points_for_block: defined at {:?}", pred_term_loc);
371 if self.use_live_at.contains(pred_term_point) {
372 debug!("compute_drop_live_points_for_block: use-live at {:?}", pred_term_loc);
376 // Otherwise, we are drop-live on entry to the terminator,
378 if self.drop_live_at.insert(pred_term_point) {
379 debug!("compute_drop_live_points_for_block: pushed to stack");
380 self.stack.push(pred_term_point);
384 // Note 1. There is a weird scenario that you might imagine
385 // being problematic here, but which actually cannot happen.
386 // The problem would be if we had a variable that *is* initialized
387 // (but dead) on entry to the terminator, and where the current value
388 // will be dropped in the case of unwind. In that case, we ought to
389 // consider `X` to be drop-live in between the last use and call.
390 // Here is the example:
395 // use(X); // last use
396 // ... // <-- X ought to be drop-live here
397 // X = call() goto BB1 unwind BB2
409 // However, the current code would, when walking back from BB2,
410 // simply stop and never explore BB0. This seems bad! But it turns
411 // out this code is flawed anyway -- note that the existing value of
412 // `X` would leak in the case where unwinding did *not* occur.
414 // What we *actually* generate is a store to a temporary
415 // for the call (`TMP = call()...`) and then a
416 // `DropAndReplace` to swap that with `X`
417 // (`DropAndReplace` has very particular semantics).
421 impl LivenessContext<'_, '_, '_, 'tcx> {
422 /// Returns `true` if the local variable (or some part of it) is initialized at the current
423 /// cursor position. Callers should call one of the `seek` methods immediately before to point
424 /// the cursor to the desired location.
425 fn initialized_at_curr_loc(&self, mpi: MovePathIndex) -> bool {
426 let state = self.flow_inits.get();
427 if state.contains(mpi) {
431 let move_paths = &self.flow_inits.analysis().move_data().move_paths;
432 move_paths[mpi].find_descendant(&move_paths, |mpi| state.contains(mpi)).is_some()
435 /// Returns `true` if the local variable (or some part of it) is initialized in
436 /// the terminator of `block`. We need to check this to determine if a
437 /// DROP of some local variable will have an effect -- note that
438 /// drops, as they may unwind, are always terminators.
439 fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
440 self.flow_inits.seek_before_primary_effect(self.body.terminator_loc(block));
441 self.initialized_at_curr_loc(mpi)
444 /// Returns `true` if the path `mpi` (or some part of it) is initialized at
445 /// the exit of `block`.
447 /// **Warning:** Does not account for the result of `Call`
449 fn initialized_at_exit(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
450 self.flow_inits.seek_after_primary_effect(self.body.terminator_loc(block));
451 self.initialized_at_curr_loc(mpi)
454 /// Stores the result that all regions in `value` are live for the
455 /// points `live_at`.
456 fn add_use_live_facts_for(
458 value: impl TypeFoldable<'tcx>,
459 live_at: &HybridBitSet<PointIndex>,
461 debug!("add_use_live_facts_for(value={:?})", value);
463 Self::make_all_regions_live(self.elements, &mut self.typeck, value, live_at)
466 /// Some variable with type `live_ty` is "drop live" at `location`
467 /// -- i.e., it may be dropped later. This means that *some* of
468 /// the regions in its type must be live at `location`. The
469 /// precise set will depend on the dropck constraints, and in
470 /// particular this takes `#[may_dangle]` into account.
471 fn add_drop_live_facts_for(
473 dropped_local: Local,
474 dropped_ty: Ty<'tcx>,
475 drop_locations: &[Location],
476 live_at: &HybridBitSet<PointIndex>,
479 "add_drop_live_constraint(\
480 dropped_local={:?}, \
482 drop_locations={:?}, \
487 values::location_set_str(self.elements, live_at.iter()),
490 let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
491 let typeck = &mut self.typeck;
492 move || Self::compute_drop_data(typeck, dropped_ty)
495 if let Some(data) = &drop_data.region_constraint_data {
496 for &drop_location in drop_locations {
497 self.typeck.push_region_constraints(
498 drop_location.to_locations(),
499 ConstraintCategory::Boring,
505 drop_data.dropck_result.report_overflows(
506 self.typeck.infcx.tcx,
507 self.body.source_info(*drop_locations.first().unwrap()).span,
511 // All things in the `outlives` array may be touched by
512 // the destructor and must be live at this point.
513 for &kind in &drop_data.dropck_result.kinds {
514 Self::make_all_regions_live(self.elements, &mut self.typeck, kind, live_at);
516 polonius::add_drop_of_var_derefs_origin(&mut self.typeck, dropped_local, &kind);
520 fn make_all_regions_live(
521 elements: &RegionValueElements,
522 typeck: &mut TypeChecker<'_, 'tcx>,
523 value: impl TypeFoldable<'tcx>,
524 live_at: &HybridBitSet<PointIndex>,
526 debug!("make_all_regions_live(value={:?})", value);
528 "make_all_regions_live: live_at={}",
529 values::location_set_str(elements, live_at.iter()),
532 let tcx = typeck.tcx();
533 tcx.for_each_free_region(&value, |live_region| {
534 let live_region_vid =
535 typeck.borrowck_context.universal_regions.to_region_vid(live_region);
539 .liveness_constraints
540 .add_elements(live_region_vid, live_at);
544 fn compute_drop_data(
545 typeck: &mut TypeChecker<'_, 'tcx>,
546 dropped_ty: Ty<'tcx>,
547 ) -> DropData<'tcx> {
548 debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
550 let param_env = typeck.param_env;
551 let TypeOpOutput { output, constraints, .. } =
552 param_env.and(DropckOutlives::new(dropped_ty)).fully_perform(typeck.infcx).unwrap();
554 DropData { dropck_result: output, region_constraint_data: constraints }