1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use borrow_check::nll::type_check::AtLocation;
12 use dataflow::move_paths::{HasMoveData, MoveData};
13 use dataflow::MaybeInitializedPlaces;
14 use dataflow::{FlowAtLocation, FlowsAtLocation};
15 use rustc::infer::canonical::QueryRegionConstraint;
16 use rustc::mir::Local;
17 use rustc::mir::{BasicBlock, Location, Mir};
18 use rustc::traits::query::dropck_outlives::DropckOutlivesResult;
19 use rustc::traits::query::type_op::outlives::DropckOutlives;
20 use rustc::traits::query::type_op::TypeOp;
21 use rustc::ty::{Ty, TypeFoldable};
22 use rustc_data_structures::fx::FxHashMap;
23 use rustc_data_structures::indexed_vec::Idx;
25 use util::liveness::{LivenessResults, LiveVariableMap};
27 use super::TypeChecker;
29 /// Combines liveness analysis with initialization analysis to
30 /// determine which variables are live at which points, both due to
31 /// ordinary uses and drops. Returns a set of (ty, location) pairs
32 /// that indicate which types must be live at which point in the CFG.
33 /// This vector is consumed by `constraint_generation`.
35 /// NB. This computation requires normalization; therefore, it must be
37 pub(super) fn generate<'gcx, 'tcx, V: LiveVariableMap>(
38 cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
40 liveness: &LivenessResults<V>,
41 flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
42 move_data: &MoveData<'tcx>,
44 let mut generator = TypeLivenessGenerator {
50 drop_data: FxHashMap(),
53 for bb in mir.basic_blocks().indices() {
54 generator.add_liveness_constraints(bb);
58 struct TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx, V: LiveVariableMap>
62 'tcx: 'typeck + 'flow,
66 cx: &'gen mut TypeChecker<'typeck, 'gcx, 'tcx>,
68 liveness: &'gen LivenessResults<V>,
69 flow_inits: &'gen mut FlowAtLocation<MaybeInitializedPlaces<'flow, 'gcx, 'tcx>>,
70 move_data: &'gen MoveData<'tcx>,
71 drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>,
74 struct DropData<'tcx> {
75 dropck_result: DropckOutlivesResult<'tcx>,
76 region_constraint_data: Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>,
79 impl<'gen, 'typeck, 'flow, 'gcx, 'tcx, V:LiveVariableMap> TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx, V> {
80 /// Liveness constraints:
82 /// > If a variable V is live at point P, then all regions R in the type of V
83 /// > must include the point P.
84 fn add_liveness_constraints(&mut self, bb: BasicBlock) {
85 debug!("add_liveness_constraints(bb={:?})", bb);
89 .simulate_block(self.mir, bb, |location, live_locals| {
90 for live_local in live_locals.iter() {
91 let live_local_ty = self.mir.local_decls[live_local].ty;
92 Self::push_type_live_constraint(&mut self.cx, live_local_ty, location);
96 let mut all_live_locals: Vec<(Location, Vec<V::LiveVar>)> = vec![];
99 .simulate_block(self.mir, bb, |location, live_locals| {
100 all_live_locals.push((location, live_locals.iter().collect()));
103 "add_liveness_constraints: all_live_locals={:#?}",
107 let terminator_index = self.mir.basic_blocks()[bb].statements.len();
108 self.flow_inits.reset_to_entry_of(bb);
109 while let Some((location, live_locals)) = all_live_locals.pop() {
110 for live_local in live_locals {
112 "add_liveness_constraints: location={:?} live_local={:?}",
116 if log_enabled!(::log::Level::Debug) {
117 self.flow_inits.each_state_bit(|mpi_init| {
119 "add_liveness_constraints: location={:?} initialized={:?}",
121 &self.flow_inits.operator().move_data().move_paths[mpi_init]
126 let mpi = self.move_data.rev_lookup.find_local(live_local);
127 if let Some(initialized_child) = self.flow_inits.has_any_child_of(mpi) {
129 "add_liveness_constraints: mpi={:?} has initialized child {:?}",
130 self.move_data.move_paths[mpi],
131 self.move_data.move_paths[initialized_child]
134 let live_local_ty = self.mir.local_decls[live_local].ty;
135 self.add_drop_live_constraint(live_local, live_local_ty, location);
139 if location.statement_index == terminator_index {
141 "add_liveness_constraints: reconstruct_terminator_effect from {:#?}",
144 self.flow_inits.reconstruct_terminator_effect(location);
147 "add_liveness_constraints: reconstruct_statement_effect from {:#?}",
150 self.flow_inits.reconstruct_statement_effect(location);
152 self.flow_inits.apply_local_effect(location);
156 /// Some variable with type `live_ty` is "regular live" at
157 /// `location` -- i.e., it may be used later. This means that all
158 /// regions appearing in the type `live_ty` must be live at
160 fn push_type_live_constraint<T>(
161 cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
165 T: TypeFoldable<'tcx>,
168 "push_type_live_constraint(live_ty={:?}, location={:?})",
172 cx.tcx().for_each_free_region(&value, |live_region| {
173 if let Some(ref mut borrowck_context) = cx.borrowck_context {
174 let region_vid = borrowck_context.universal_regions.to_region_vid(live_region);
175 borrowck_context.constraints.liveness_constraints.add_element(region_vid, location);
177 if let Some(all_facts) = borrowck_context.all_facts {
178 let start_index = borrowck_context.location_table.start_index(location);
179 all_facts.region_live_at.push((region_vid, start_index));
181 let mid_index = borrowck_context.location_table.mid_index(location);
182 all_facts.region_live_at.push((region_vid, mid_index));
188 /// Some variable with type `live_ty` is "drop live" at `location`
189 /// -- i.e., it may be dropped later. This means that *some* of
190 /// the regions in its type must be live at `location`. The
191 /// precise set will depend on the dropck constraints, and in
192 /// particular this takes `#[may_dangle]` into account.
193 fn add_drop_live_constraint(
195 dropped_local: Local,
196 dropped_ty: Ty<'tcx>,
200 "add_drop_live_constraint(dropped_local={:?}, dropped_ty={:?}, location={:?})",
201 dropped_local, dropped_ty, location
204 let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
205 let cx = &mut self.cx;
206 move || Self::compute_drop_data(cx, dropped_ty)
209 if let Some(data) = &drop_data.region_constraint_data {
210 self.cx.push_region_constraints(location.boring(), data);
213 drop_data.dropck_result.report_overflows(
215 self.mir.source_info(location).span,
219 // All things in the `outlives` array may be touched by
220 // the destructor and must be live at this point.
221 for &kind in &drop_data.dropck_result.kinds {
222 Self::push_type_live_constraint(&mut self.cx, kind, location);
226 fn compute_drop_data(
227 cx: &mut TypeChecker<'_, 'gcx, 'tcx>,
228 dropped_ty: Ty<'tcx>,
229 ) -> DropData<'tcx> {
230 debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
232 let param_env = cx.param_env;
233 let (dropck_result, region_constraint_data) = param_env
234 .and(DropckOutlives::new(dropped_ty))
235 .fully_perform(cx.infcx)
240 region_constraint_data,