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 if self.defs.contains(p) {
212 if self.use_live_at.insert(p) {
213 self.cx.elements.push_predecessors(self.cx.body, p, &mut self.stack)
218 /// Computes all points where local is "drop live" -- meaning its
219 /// current value may be dropped later (but not used). This is
220 /// done by iterating over the drops of `local` where `local` (or
221 /// some subpart of `local`) is initialized. For each such drop,
222 /// we walk backwards until we find a point where `local` is
223 /// either defined or use-live.
225 /// Requires `compute_use_live_points_for` and `add_defs_for` to
226 /// have been executed.
227 fn compute_drop_live_points_for(&mut self, local: Local) {
228 debug!("compute_drop_live_points_for(local={:?})", local);
230 let mpi = self.cx.move_data.rev_lookup.find_local(local);
231 debug!("compute_drop_live_points_for: mpi = {:?}", mpi);
233 // Find the drops where `local` is initialized.
234 for drop_point in self.cx.local_use_map.drops(local) {
235 let location = self.cx.elements.to_location(drop_point);
236 debug_assert_eq!(self.cx.body.terminator_loc(location.block), location,);
238 if self.cx.initialized_at_terminator(location.block, mpi) {
239 if self.drop_live_at.insert(drop_point) {
240 self.drop_locations.push(location);
241 self.stack.push(drop_point);
246 debug!("compute_drop_live_points_for: drop_locations={:?}", self.drop_locations);
248 // Reverse DFS. But for drops, we do it a bit differently.
249 // The stack only ever stores *terminators of blocks*. Within
250 // a block, we walk back the statements in an inner loop.
251 while let Some(term_point) = self.stack.pop() {
252 self.compute_drop_live_points_for_block(mpi, term_point);
256 /// Executes one iteration of the drop-live analysis loop.
258 /// The parameter `mpi` is the `MovePathIndex` of the local variable
259 /// we are currently analyzing.
261 /// The point `term_point` represents some terminator in the MIR,
262 /// where the local `mpi` is drop-live on entry to that terminator.
264 /// This method adds all drop-live points within the block and --
265 /// where applicable -- pushes the terminators of preceding blocks
266 /// onto `self.stack`.
267 fn compute_drop_live_points_for_block(&mut self, mpi: MovePathIndex, term_point: PointIndex) {
269 "compute_drop_live_points_for_block(mpi={:?}, term_point={:?})",
270 self.cx.move_data.move_paths[mpi].place,
271 self.cx.elements.to_location(term_point),
274 // We are only invoked with terminators where `mpi` is
275 // drop-live on entry.
276 debug_assert!(self.drop_live_at.contains(term_point));
278 // Otherwise, scan backwards through the statements in the
279 // block. One of them may be either a definition or use
281 let term_location = self.cx.elements.to_location(term_point);
282 debug_assert_eq!(self.cx.body.terminator_loc(term_location.block), term_location,);
283 let block = term_location.block;
284 let entry_point = self.cx.elements.entry_point(term_location.block);
285 for p in (entry_point..term_point).rev() {
286 debug!("compute_drop_live_points_for_block: p = {:?}", self.cx.elements.to_location(p));
288 if self.defs.contains(p) {
289 debug!("compute_drop_live_points_for_block: def site");
293 if self.use_live_at.contains(p) {
294 debug!("compute_drop_live_points_for_block: use-live at {:?}", p);
298 if !self.drop_live_at.insert(p) {
299 debug!("compute_drop_live_points_for_block: already drop-live");
304 let body = self.cx.body;
305 for &pred_block in body.predecessors()[block].iter() {
306 debug!("compute_drop_live_points_for_block: pred_block = {:?}", pred_block,);
308 // Check whether the variable is (at least partially)
309 // initialized at the exit of this predecessor. If so, we
310 // want to enqueue it on our list. If not, go check the
313 // Note that we only need to check whether `live_local`
314 // became de-initialized at basic block boundaries. If it
315 // were to become de-initialized within the block, that
316 // would have been a "use-live" transition in the earlier
317 // loop, and we'd have returned already.
319 // NB. It's possible that the pred-block ends in a call
320 // which stores to the variable; in that case, the
321 // variable may be uninitialized "at exit" because this
322 // call only considers the *unconditional effects* of the
323 // terminator. *But*, in that case, the terminator is also
324 // a *definition* of the variable, in which case we want
325 // to stop the search anyhow. (But see Note 1 below.)
326 if !self.cx.initialized_at_exit(pred_block, mpi) {
327 debug!("compute_drop_live_points_for_block: not initialized");
331 let pred_term_loc = self.cx.body.terminator_loc(pred_block);
332 let pred_term_point = self.cx.elements.point_from_location(pred_term_loc);
334 // If the terminator of this predecessor either *assigns*
335 // our value or is a "normal use", then stop.
336 if self.defs.contains(pred_term_point) {
337 debug!("compute_drop_live_points_for_block: defined at {:?}", pred_term_loc);
341 if self.use_live_at.contains(pred_term_point) {
342 debug!("compute_drop_live_points_for_block: use-live at {:?}", pred_term_loc);
346 // Otherwise, we are drop-live on entry to the terminator,
348 if self.drop_live_at.insert(pred_term_point) {
349 debug!("compute_drop_live_points_for_block: pushed to stack");
350 self.stack.push(pred_term_point);
354 // Note 1. There is a weird scenario that you might imagine
355 // being problematic here, but which actually cannot happen.
356 // The problem would be if we had a variable that *is* initialized
357 // (but dead) on entry to the terminator, and where the current value
358 // will be dropped in the case of unwind. In that case, we ought to
359 // consider `X` to be drop-live in between the last use and call.
360 // Here is the example:
365 // use(X); // last use
366 // ... // <-- X ought to be drop-live here
367 // X = call() goto BB1 unwind BB2
379 // However, the current code would, when walking back from BB2,
380 // simply stop and never explore BB0. This seems bad! But it turns
381 // out this code is flawed anyway -- note that the existing value of
382 // `X` would leak in the case where unwinding did *not* occur.
384 // What we *actually* generate is a store to a temporary
385 // for the call (`TMP = call()...`) and then a
386 // `DropAndReplace` to swap that with `X`
387 // (`DropAndReplace` has very particular semantics).
391 impl LivenessContext<'_, '_, '_, 'tcx> {
392 /// Returns `true` if the local variable (or some part of it) is initialized at the current
393 /// cursor position. Callers should call one of the `seek` methods immediately before to point
394 /// the cursor to the desired location.
395 fn initialized_at_curr_loc(&self, mpi: MovePathIndex) -> bool {
396 let state = self.flow_inits.get();
397 if state.contains(mpi) {
401 let move_paths = &self.flow_inits.analysis().move_data().move_paths;
402 move_paths[mpi].find_descendant(&move_paths, |mpi| state.contains(mpi)).is_some()
405 /// Returns `true` if the local variable (or some part of it) is initialized in
406 /// the terminator of `block`. We need to check this to determine if a
407 /// DROP of some local variable will have an effect -- note that
408 /// drops, as they may unwind, are always terminators.
409 fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
410 self.flow_inits.seek_before_primary_effect(self.body.terminator_loc(block));
411 self.initialized_at_curr_loc(mpi)
414 /// Returns `true` if the path `mpi` (or some part of it) is initialized at
415 /// the exit of `block`.
417 /// **Warning:** Does not account for the result of `Call`
419 fn initialized_at_exit(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
420 self.flow_inits.seek_after_primary_effect(self.body.terminator_loc(block));
421 self.initialized_at_curr_loc(mpi)
424 /// Stores the result that all regions in `value` are live for the
425 /// points `live_at`.
426 fn add_use_live_facts_for(
428 value: impl TypeFoldable<'tcx>,
429 live_at: &HybridBitSet<PointIndex>,
431 debug!("add_use_live_facts_for(value={:?})", value);
433 Self::make_all_regions_live(self.elements, &mut self.typeck, value, live_at)
436 /// Some variable with type `live_ty` is "drop live" at `location`
437 /// -- i.e., it may be dropped later. This means that *some* of
438 /// the regions in its type must be live at `location`. The
439 /// precise set will depend on the dropck constraints, and in
440 /// particular this takes `#[may_dangle]` into account.
441 fn add_drop_live_facts_for(
443 dropped_local: Local,
444 dropped_ty: Ty<'tcx>,
445 drop_locations: &[Location],
446 live_at: &HybridBitSet<PointIndex>,
449 "add_drop_live_constraint(\
450 dropped_local={:?}, \
452 drop_locations={:?}, \
457 values::location_set_str(self.elements, live_at.iter()),
460 let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
461 let typeck = &mut self.typeck;
462 move || Self::compute_drop_data(typeck, dropped_ty)
465 if let Some(data) = &drop_data.region_constraint_data {
466 for &drop_location in drop_locations {
467 self.typeck.push_region_constraints(
468 drop_location.to_locations(),
469 ConstraintCategory::Boring,
475 drop_data.dropck_result.report_overflows(
476 self.typeck.infcx.tcx,
477 self.body.source_info(*drop_locations.first().unwrap()).span,
481 // All things in the `outlives` array may be touched by
482 // the destructor and must be live at this point.
483 for &kind in &drop_data.dropck_result.kinds {
484 Self::make_all_regions_live(self.elements, &mut self.typeck, kind, live_at);
486 polonius::add_drop_of_var_derefs_origin(&mut self.typeck, dropped_local, &kind);
490 fn make_all_regions_live(
491 elements: &RegionValueElements,
492 typeck: &mut TypeChecker<'_, 'tcx>,
493 value: impl TypeFoldable<'tcx>,
494 live_at: &HybridBitSet<PointIndex>,
496 debug!("make_all_regions_live(value={:?})", value);
498 "make_all_regions_live: live_at={}",
499 values::location_set_str(elements, live_at.iter()),
502 let tcx = typeck.tcx();
503 tcx.for_each_free_region(&value, |live_region| {
504 let live_region_vid =
505 typeck.borrowck_context.universal_regions.to_region_vid(live_region);
509 .liveness_constraints
510 .add_elements(live_region_vid, live_at);
514 fn compute_drop_data(
515 typeck: &mut TypeChecker<'_, 'tcx>,
516 dropped_ty: Ty<'tcx>,
517 ) -> DropData<'tcx> {
518 debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
520 let param_env = typeck.param_env;
521 let TypeOpOutput { output, constraints, .. } =
522 param_env.and(DropckOutlives::new(dropped_ty)).fully_perform(typeck.infcx).unwrap();
524 DropData { dropck_result: output, region_constraint_data: constraints }