1 use rustc::infer::canonical::QueryRegionConstraints;
2 use rustc::mir::{BasicBlock, ConstraintCategory, Local, Location, ReadOnlyBodyAndCache};
3 use rustc::traits::query::dropck_outlives::DropckOutlivesResult;
4 use rustc::traits::query::type_op::outlives::DropckOutlives;
5 use rustc::traits::query::type_op::TypeOp;
6 use rustc::ty::{Ty, TypeFoldable};
7 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
8 use rustc_index::bit_set::HybridBitSet;
11 use crate::dataflow::indexes::MovePathIndex;
12 use crate::dataflow::move_paths::MoveData;
13 use crate::dataflow::{FlowAtLocation, FlowsAtLocation, MaybeInitializedPlaces};
15 use crate::borrow_check::{
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>,
39 body: ReadOnlyBodyAndCache<'_, 'tcx>,
40 elements: &Rc<RegionValueElements>,
41 flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, '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: ReadOnlyBodyAndCache<'me, '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 FlowAtLocation<'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() {
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_for(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 in
393 /// the terminator of `block`. We need to check this to determine if a
394 /// DROP of some local variable will have an effect -- note that
395 /// drops, as they may unwind, are always terminators.
396 fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
397 // Compute the set of initialized paths at terminator of block
398 // by resetting to the start of the block and then applying
399 // the effects of all statements. This is the only way to get
400 // "just ahead" of a terminator.
401 self.flow_inits.reset_to_entry_of(block);
402 for statement_index in 0..self.body[block].statements.len() {
403 let location = Location { block, statement_index };
404 self.flow_inits.reconstruct_statement_effect(location);
405 self.flow_inits.apply_local_effect(location);
408 self.flow_inits.has_any_child_of(mpi).is_some()
411 /// Returns `true` if the path `mpi` (or some part of it) is initialized at
412 /// the exit of `block`.
414 /// **Warning:** Does not account for the result of `Call`
416 fn initialized_at_exit(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
417 self.flow_inits.reset_to_exit_of(block);
418 self.flow_inits.has_any_child_of(mpi).is_some()
421 /// Stores the result that all regions in `value` are live for the
422 /// points `live_at`.
423 fn add_use_live_facts_for(
425 value: impl TypeFoldable<'tcx>,
426 live_at: &HybridBitSet<PointIndex>,
428 debug!("add_use_live_facts_for(value={:?})", value);
430 Self::make_all_regions_live(self.elements, &mut self.typeck, value, live_at)
433 /// Some variable with type `live_ty` is "drop live" at `location`
434 /// -- i.e., it may be dropped later. This means that *some* of
435 /// the regions in its type must be live at `location`. The
436 /// precise set will depend on the dropck constraints, and in
437 /// particular this takes `#[may_dangle]` into account.
438 fn add_drop_live_facts_for(
440 dropped_local: Local,
441 dropped_ty: Ty<'tcx>,
442 drop_locations: &[Location],
443 live_at: &HybridBitSet<PointIndex>,
446 "add_drop_live_constraint(\
447 dropped_local={:?}, \
449 drop_locations={:?}, \
454 values::location_set_str(self.elements, live_at.iter()),
457 let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
458 let typeck = &mut self.typeck;
459 move || Self::compute_drop_data(typeck, dropped_ty)
462 if let Some(data) = &drop_data.region_constraint_data {
463 for &drop_location in drop_locations {
464 self.typeck.push_region_constraints(
465 drop_location.to_locations(),
466 ConstraintCategory::Boring,
472 drop_data.dropck_result.report_overflows(
473 self.typeck.infcx.tcx,
474 self.body.source_info(*drop_locations.first().unwrap()).span,
478 // All things in the `outlives` array may be touched by
479 // the destructor and must be live at this point.
480 for &kind in &drop_data.dropck_result.kinds {
481 Self::make_all_regions_live(self.elements, &mut self.typeck, kind, live_at);
483 polonius::add_var_drops_regions(&mut self.typeck, dropped_local, &kind);
487 fn make_all_regions_live(
488 elements: &RegionValueElements,
489 typeck: &mut TypeChecker<'_, 'tcx>,
490 value: impl TypeFoldable<'tcx>,
491 live_at: &HybridBitSet<PointIndex>,
493 debug!("make_all_regions_live(value={:?})", value);
495 "make_all_regions_live: live_at={}",
496 values::location_set_str(elements, live_at.iter()),
499 let tcx = typeck.tcx();
500 tcx.for_each_free_region(&value, |live_region| {
501 let live_region_vid =
502 typeck.borrowck_context.universal_regions.to_region_vid(live_region);
506 .liveness_constraints
507 .add_elements(live_region_vid, live_at);
511 fn compute_drop_data(
512 typeck: &mut TypeChecker<'_, 'tcx>,
513 dropped_ty: Ty<'tcx>,
514 ) -> DropData<'tcx> {
515 debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
517 let param_env = typeck.param_env;
518 let (dropck_result, region_constraint_data) =
519 param_env.and(DropckOutlives::new(dropped_ty)).fully_perform(typeck.infcx).unwrap();
521 DropData { dropck_result, region_constraint_data }