1 use crate::borrow_check::location::LocationTable;
2 use crate::borrow_check::nll::region_infer::values::{self, PointIndex, RegionValueElements};
3 use crate::borrow_check::nll::type_check::liveness::local_use_map::LocalUseMap;
4 use crate::borrow_check::nll::type_check::NormalizeLocation;
5 use crate::borrow_check::nll::type_check::TypeChecker;
6 use crate::dataflow::indexes::MovePathIndex;
7 use crate::dataflow::move_paths::MoveData;
8 use crate::dataflow::{FlowAtLocation, FlowsAtLocation, MaybeInitializedPlaces};
9 use rustc::infer::canonical::QueryRegionConstraints;
10 use rustc::mir::{BasicBlock, ConstraintCategory, Local, Location, Body};
11 use rustc::traits::query::dropck_outlives::DropckOutlivesResult;
12 use rustc::traits::query::type_op::outlives::DropckOutlives;
13 use rustc::traits::query::type_op::TypeOp;
14 use rustc::ty::{Ty, TypeFoldable};
15 use rustc_data_structures::bit_set::HybridBitSet;
16 use rustc_data_structures::fx::FxHashMap;
19 /// This is the heart of the liveness computation. For each variable X
20 /// that requires a liveness computation, it walks over all the uses
21 /// of X and does a reverse depth-first search ("trace") through the
22 /// MIR. This search stops when we find a definition of that variable.
23 /// The points visited in this search is the USE-LIVE set for the variable;
24 /// of those points is added to all the regions that appear in the variable's
27 /// We then also walks through each *drop* of those variables and does
28 /// another search, stopping when we reach a use or definition. This
29 /// is the DROP-LIVE set of points. Each of the points in the
30 /// DROP-LIVE set are to the liveness sets for regions found in the
31 /// `dropck_outlives` result of the variable's type (in particular,
32 /// this respects `#[may_dangle]` annotations).
34 typeck: &mut TypeChecker<'_, 'tcx>,
36 elements: &Rc<RegionValueElements>,
37 flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>,
38 move_data: &MoveData<'tcx>,
39 live_locals: Vec<Local>,
40 location_table: &LocationTable,
44 let local_use_map = &LocalUseMap::build(&live_locals, elements, body);
46 let cx = LivenessContext {
53 drop_data: FxHashMap::default(),
57 LivenessResults::new(cx).compute_for_all_locals(live_locals);
60 /// Contextual state for the type-liveness generator.
61 struct LivenessContext<'me, 'typeck, 'flow, 'tcx> {
62 /// Current type-checker, giving us our inference context etc.
63 typeck: &'me mut TypeChecker<'typeck, 'tcx>,
65 /// Defines the `PointIndex` mapping
66 elements: &'me RegionValueElements,
68 /// MIR we are analyzing.
69 body: &'me Body<'tcx>,
71 /// Mapping to/from the various indices used for initialization tracking.
72 move_data: &'me MoveData<'tcx>,
74 /// Cache for the results of `dropck_outlives` query.
75 drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>,
77 /// Results of dataflow tracking which variables (and paths) have been
79 flow_inits: &'me mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'flow, 'tcx>>,
81 /// Index indicating where each variable is assigned, used, or
83 local_use_map: &'me LocalUseMap,
85 /// Maps between a MIR Location and a LocationIndex
86 location_table: &'me LocationTable,
89 struct DropData<'tcx> {
90 dropck_result: DropckOutlivesResult<'tcx>,
91 region_constraint_data: Option<Rc<QueryRegionConstraints<'tcx>>>,
94 struct LivenessResults<'me, 'typeck, 'flow, 'tcx> {
95 cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>,
97 /// Set of points that define the current local.
98 defs: HybridBitSet<PointIndex>,
100 /// Points where the current variable is "use live" -- meaning
101 /// that there is a future "full use" that may use its value.
102 use_live_at: HybridBitSet<PointIndex>,
104 /// Points where the current variable is "drop live" -- meaning
105 /// that there is no future "full use" that may use its value, but
106 /// there is a future drop.
107 drop_live_at: HybridBitSet<PointIndex>,
109 /// Locations where drops may occur.
110 drop_locations: Vec<Location>,
112 /// Stack used when doing (reverse) DFS.
113 stack: Vec<PointIndex>,
116 impl LivenessResults<'me, 'typeck, 'flow, 'tcx> {
117 fn new(cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>) -> Self {
118 let num_points = cx.elements.num_points();
121 defs: HybridBitSet::new_empty(num_points),
122 use_live_at: HybridBitSet::new_empty(num_points),
123 drop_live_at: HybridBitSet::new_empty(num_points),
124 drop_locations: vec![],
129 fn compute_for_all_locals(&mut self, live_locals: Vec<Local>) {
130 for local in live_locals {
131 self.reset_local_state();
132 self.add_defs_for(local);
133 self.compute_use_live_points_for(local);
134 self.compute_drop_live_points_for(local);
136 let local_ty = self.cx.body.local_decls[local].ty;
138 if !self.use_live_at.is_empty() {
139 self.cx.add_use_live_facts_for(local_ty, &self.use_live_at);
142 if !self.drop_live_at.is_empty() {
143 self.cx.add_drop_live_facts_for(
146 &self.drop_locations,
153 /// Clear the value of fields that are "per local variable".
154 fn reset_local_state(&mut self) {
156 self.use_live_at.clear();
157 self.drop_live_at.clear();
158 self.drop_locations.clear();
159 assert!(self.stack.is_empty());
162 /// Adds the definitions of `local` into `self.defs`.
163 fn add_defs_for(&mut self, local: Local) {
164 for def in self.cx.local_use_map.defs(local) {
165 debug!("- defined at {:?}", def);
166 self.defs.insert(def);
170 /// Computes all points where local is "use live" -- meaning its
171 /// current value may be used later (except by a drop). This is
172 /// done by walking backwards from each use of `local` until we
173 /// find a `def` of local.
175 /// Requires `add_defs_for(local)` to have been executed.
176 fn compute_use_live_points_for(&mut self, local: Local) {
177 debug!("compute_use_live_points_for(local={:?})", local);
179 self.stack.extend(self.cx.local_use_map.uses(local));
180 while let Some(p) = self.stack.pop() {
181 if self.defs.contains(p) {
185 if self.use_live_at.insert(p) {
188 .push_predecessors(self.cx.body, p, &mut self.stack)
193 /// Computes all points where local is "drop live" -- meaning its
194 /// current value may be dropped later (but not used). This is
195 /// done by iterating over the drops of `local` where `local` (or
196 /// some subpart of `local`) is initialized. For each such drop,
197 /// we walk backwards until we find a point where `local` is
198 /// either defined or use-live.
200 /// Requires `compute_use_live_points_for` and `add_defs_for` to
201 /// have been executed.
202 fn compute_drop_live_points_for(&mut self, local: Local) {
203 debug!("compute_drop_live_points_for(local={:?})", local);
205 let mpi = self.cx.move_data.rev_lookup.find_local(local);
206 debug!("compute_drop_live_points_for: mpi = {:?}", mpi);
208 // Find the drops where `local` is initialized.
209 for drop_point in self.cx.local_use_map.drops(local) {
210 let location = self.cx.elements.to_location(drop_point);
211 debug_assert_eq!(self.cx.body.terminator_loc(location.block), location,);
213 if self.cx.initialized_at_terminator(location.block, mpi) {
214 if self.drop_live_at.insert(drop_point) {
215 self.drop_locations.push(location);
216 self.stack.push(drop_point);
222 "compute_drop_live_points_for: drop_locations={:?}",
226 // Reverse DFS. But for drops, we do it a bit differently.
227 // The stack only ever stores *terminators of blocks*. Within
228 // a block, we walk back the statements in an inner loop.
229 'next_block: while let Some(term_point) = self.stack.pop() {
230 self.compute_drop_live_points_for_block(mpi, term_point);
234 /// Executes one iteration of the drop-live analysis loop.
236 /// The parameter `mpi` is the `MovePathIndex` of the local variable
237 /// we are currently analyzing.
239 /// The point `term_point` represents some terminator in the MIR,
240 /// where the local `mpi` is drop-live on entry to that terminator.
242 /// This method adds all drop-live points within the block and --
243 /// where applicable -- pushes the terminators of preceding blocks
244 /// onto `self.stack`.
245 fn compute_drop_live_points_for_block(&mut self, mpi: MovePathIndex, term_point: PointIndex) {
247 "compute_drop_live_points_for_block(mpi={:?}, term_point={:?})",
248 self.cx.move_data.move_paths[mpi].place,
249 self.cx.elements.to_location(term_point),
252 // We are only invoked with terminators where `mpi` is
253 // drop-live on entry.
254 debug_assert!(self.drop_live_at.contains(term_point));
256 // Otherwise, scan backwards through the statements in the
257 // block. One of them may be either a definition or use
259 let term_location = self.cx.elements.to_location(term_point);
261 self.cx.body.terminator_loc(term_location.block),
264 let block = term_location.block;
265 let entry_point = self.cx.elements.entry_point(term_location.block);
266 for p in (entry_point..term_point).rev() {
268 "compute_drop_live_points_for_block: p = {:?}",
269 self.cx.elements.to_location(p),
272 if self.defs.contains(p) {
273 debug!("compute_drop_live_points_for_block: def site");
277 if self.use_live_at.contains(p) {
278 debug!("compute_drop_live_points_for_block: use-live at {:?}", p);
282 if !self.drop_live_at.insert(p) {
283 debug!("compute_drop_live_points_for_block: already drop-live");
288 for &pred_block in self.cx.body.predecessors_for(block).iter() {
290 "compute_drop_live_points_for_block: pred_block = {:?}",
294 // Check whether the variable is (at least partially)
295 // initialized at the exit of this predecessor. If so, we
296 // want to enqueue it on our list. If not, go check the
299 // Note that we only need to check whether `live_local`
300 // became de-initialized at basic block boundaries. If it
301 // were to become de-initialized within the block, that
302 // would have been a "use-live" transition in the earlier
303 // loop, and we'd have returned already.
305 // NB. It's possible that the pred-block ends in a call
306 // which stores to the variable; in that case, the
307 // variable may be uninitialized "at exit" because this
308 // call only considers the *unconditional effects* of the
309 // terminator. *But*, in that case, the terminator is also
310 // a *definition* of the variable, in which case we want
311 // to stop the search anyhow. (But see Note 1 below.)
312 if !self.cx.initialized_at_exit(pred_block, mpi) {
313 debug!("compute_drop_live_points_for_block: not initialized");
317 let pred_term_loc = self.cx.body.terminator_loc(pred_block);
318 let pred_term_point = self.cx.elements.point_from_location(pred_term_loc);
320 // If the terminator of this predecessor either *assigns*
321 // our value or is a "normal use", then stop.
322 if self.defs.contains(pred_term_point) {
324 "compute_drop_live_points_for_block: defined at {:?}",
330 if self.use_live_at.contains(pred_term_point) {
332 "compute_drop_live_points_for_block: use-live at {:?}",
338 // Otherwise, we are drop-live on entry to the terminator,
340 if self.drop_live_at.insert(pred_term_point) {
341 debug!("compute_drop_live_points_for_block: pushed to stack");
342 self.stack.push(pred_term_point);
346 // Note 1. There is a weird scenario that you might imagine
347 // being problematic here, but which actually cannot happen.
348 // The problem would be if we had a variable that *is* initialized
349 // (but dead) on entry to the terminator, and where the current value
350 // will be dropped in the case of unwind. In that case, we ought to
351 // consider `X` to be drop-live in between the last use and call.
352 // Here is the example:
357 // use(X); // last use
358 // ... // <-- X ought to be drop-live here
359 // X = call() goto BB1 unwind BB2
371 // However, the current code would, when walking back from BB2,
372 // simply stop and never explore BB0. This seems bad! But it turns
373 // out this code is flawed anyway -- note that the existing value of
374 // `X` would leak in the case where unwinding did *not* occur.
376 // What we *actually* generate is a store to a temporary
377 // for the call (`TMP = call()...`) and then a
378 // `DropAndReplace` to swap that with `X`
379 // (`DropAndReplace` has very particular semantics).
383 impl LivenessContext<'_, '_, '_, 'tcx> {
384 /// Returns `true` if the local variable (or some part of it) is initialized in
385 /// the terminator of `block`. We need to check this to determine if a
386 /// DROP of some local variable will have an effect -- note that
387 /// drops, as they may unwind, are always terminators.
388 fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
389 // Compute the set of initialized paths at terminator of block
390 // by resetting to the start of the block and then applying
391 // the effects of all statements. This is the only way to get
392 // "just ahead" of a terminator.
393 self.flow_inits.reset_to_entry_of(block);
394 for statement_index in 0..self.body[block].statements.len() {
395 let location = Location {
399 self.flow_inits.reconstruct_statement_effect(location);
400 self.flow_inits.apply_local_effect(location);
403 self.flow_inits.has_any_child_of(mpi).is_some()
406 /// Returns `true` if the path `mpi` (or some part of it) is initialized at
407 /// the exit of `block`.
409 /// **Warning:** Does not account for the result of `Call`
411 fn initialized_at_exit(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
412 self.flow_inits.reset_to_exit_of(block);
413 self.flow_inits.has_any_child_of(mpi).is_some()
416 /// Stores the result that all regions in `value` are live for the
417 /// points `live_at`.
418 fn add_use_live_facts_for(
420 value: impl TypeFoldable<'tcx>,
421 live_at: &HybridBitSet<PointIndex>,
423 debug!("add_use_live_facts_for(value={:?})", value);
425 Self::make_all_regions_live(
434 /// Some variable with type `live_ty` is "drop live" at `location`
435 /// -- i.e., it may be dropped later. This means that *some* of
436 /// the regions in its type must be live at `location`. The
437 /// precise set will depend on the dropck constraints, and in
438 /// particular this takes `#[may_dangle]` into account.
439 fn add_drop_live_facts_for(
441 dropped_local: Local,
442 dropped_ty: Ty<'tcx>,
443 drop_locations: &[Location],
444 live_at: &HybridBitSet<PointIndex>,
447 "add_drop_live_constraint(\
448 dropped_local={:?}, \
450 drop_locations={:?}, \
455 values::location_set_str(self.elements, live_at.iter()),
458 let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
459 let typeck = &mut self.typeck;
460 move || Self::compute_drop_data(typeck, dropped_ty)
463 if let Some(data) = &drop_data.region_constraint_data {
464 for &drop_location in drop_locations {
466 .push_region_constraints(
467 drop_location.to_locations(),
468 ConstraintCategory::Boring,
474 drop_data.dropck_result.report_overflows(
475 self.typeck.infcx.tcx,
476 self.body.source_info(*drop_locations.first().unwrap()).span,
480 // All things in the `outlives` array may be touched by
481 // the destructor and must be live at this point.
482 for &kind in &drop_data.dropck_result.kinds {
483 Self::make_all_regions_live(
493 fn make_all_regions_live(
494 elements: &RegionValueElements,
495 typeck: &mut TypeChecker<'_, 'tcx>,
496 value: impl TypeFoldable<'tcx>,
497 live_at: &HybridBitSet<PointIndex>,
498 location_table: &LocationTable,
500 debug!("make_all_regions_live(value={:?})", value);
502 "make_all_regions_live: live_at={}",
503 values::location_set_str(elements, live_at.iter()),
506 let tcx = typeck.tcx();
507 tcx.for_each_free_region(&value, |live_region| {
508 let live_region_vid = typeck.borrowck_context
510 .to_region_vid(live_region);
511 typeck.borrowck_context
513 .liveness_constraints
514 .add_elements(live_region_vid, live_at);
516 if let Some(facts) = typeck.borrowck_context.all_facts {
517 for point in live_at.iter() {
518 let loc = elements.to_location(point);
519 facts.region_live_at.push((live_region_vid, location_table.start_index(loc)));
520 facts.region_live_at.push((live_region_vid, location_table.mid_index(loc)));
526 fn compute_drop_data(
527 typeck: &mut TypeChecker<'_, 'tcx>,
528 dropped_ty: Ty<'tcx>,
529 ) -> DropData<'tcx> {
530 debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
532 let param_env = typeck.param_env;
533 let (dropck_result, region_constraint_data) = param_env
534 .and(DropckOutlives::new(dropped_ty))
535 .fully_perform(typeck.infcx)
540 region_constraint_data,