diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-17 12:02:58 +0000 |
commit | 698f8c2f01ea549d77d7dc3338a12e04c11057b9 (patch) | |
tree | 173a775858bd501c378080a10dca74132f05bc50 /compiler/rustc_borrowck/src/type_check/liveness | |
parent | Initial commit. (diff) | |
download | rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.tar.xz rustc-698f8c2f01ea549d77d7dc3338a12e04c11057b9.zip |
Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
4 files changed, 1027 insertions, 0 deletions
diff --git a/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs b/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs new file mode 100644 index 000000000..fda2cee43 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs @@ -0,0 +1,170 @@ +use rustc_data_structures::vec_linked_list as vll; +use rustc_index::vec::IndexVec; +use rustc_middle::mir::visit::{PlaceContext, Visitor}; +use rustc_middle::mir::{Body, Local, Location}; + +use crate::def_use::{self, DefUse}; +use crate::region_infer::values::{PointIndex, RegionValueElements}; + +/// A map that cross references each local with the locations where it +/// is defined (assigned), used, or dropped. Used during liveness +/// computation. +/// +/// We keep track only of `Local`s we'll do the liveness analysis later, +/// this means that our internal `IndexVec`s will only be sparsely populated. +/// In the time-memory trade-off between keeping compact vectors with new +/// indexes (and needing to continuously map the `Local` index to its compact +/// counterpart) and having `IndexVec`s that we only use a fraction of, time +/// (and code simplicity) was favored. The rationale is that we only keep +/// a small number of `IndexVec`s throughout the entire analysis while, in +/// contrast, we're accessing each `Local` *many* times. +pub(crate) struct LocalUseMap { + /// Head of a linked list of **definitions** of each variable -- + /// definition in this context means assignment, e.g., `x` is + /// defined in `x = y` but not `y`; that first def is the head of + /// a linked list that lets you enumerate all places the variable + /// is assigned. + first_def_at: IndexVec<Local, Option<AppearanceIndex>>, + + /// Head of a linked list of **uses** of each variable -- use in + /// this context means that the existing value of the variable is + /// read or modified. e.g., `y` is used in `x = y` but not `x`. + /// Note that `DROP(x)` terminators are excluded from this list. + first_use_at: IndexVec<Local, Option<AppearanceIndex>>, + + /// Head of a linked list of **drops** of each variable -- these + /// are a special category of uses corresponding to the drop that + /// we add for each local variable. + first_drop_at: IndexVec<Local, Option<AppearanceIndex>>, + + appearances: IndexVec<AppearanceIndex, Appearance>, +} + +struct Appearance { + point_index: PointIndex, + next: Option<AppearanceIndex>, +} + +rustc_index::newtype_index! { + pub struct AppearanceIndex { .. } +} + +impl vll::LinkElem for Appearance { + type LinkIndex = AppearanceIndex; + + fn next(elem: &Self) -> Option<AppearanceIndex> { + elem.next + } +} + +impl LocalUseMap { + pub(crate) fn build( + live_locals: &[Local], + elements: &RegionValueElements, + body: &Body<'_>, + ) -> Self { + let nones = IndexVec::from_elem_n(None, body.local_decls.len()); + let mut local_use_map = LocalUseMap { + first_def_at: nones.clone(), + first_use_at: nones.clone(), + first_drop_at: nones, + appearances: IndexVec::new(), + }; + + if live_locals.is_empty() { + return local_use_map; + } + + let mut locals_with_use_data: IndexVec<Local, bool> = + IndexVec::from_elem_n(false, body.local_decls.len()); + live_locals.iter().for_each(|&local| locals_with_use_data[local] = true); + + LocalUseMapBuild { local_use_map: &mut local_use_map, elements, locals_with_use_data } + .visit_body(&body); + + local_use_map + } + + pub(crate) fn defs(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { + vll::iter(self.first_def_at[local], &self.appearances) + .map(move |aa| self.appearances[aa].point_index) + } + + pub(crate) fn uses(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { + vll::iter(self.first_use_at[local], &self.appearances) + .map(move |aa| self.appearances[aa].point_index) + } + + pub(crate) fn drops(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ { + vll::iter(self.first_drop_at[local], &self.appearances) + .map(move |aa| self.appearances[aa].point_index) + } +} + +struct LocalUseMapBuild<'me> { + local_use_map: &'me mut LocalUseMap, + elements: &'me RegionValueElements, + + // Vector used in `visit_local` to signal which `Local`s do we need + // def/use/drop information on, constructed from `live_locals` (that + // contains the variables we'll do the liveness analysis for). + // This vector serves optimization purposes only: we could have + // obtained the same information from `live_locals` but we want to + // avoid repeatedly calling `Vec::contains()` (see `LocalUseMap` for + // the rationale on the time-memory trade-off we're favoring here). + locals_with_use_data: IndexVec<Local, bool>, +} + +impl LocalUseMapBuild<'_> { + fn insert_def(&mut self, local: Local, location: Location) { + Self::insert( + self.elements, + &mut self.local_use_map.first_def_at[local], + &mut self.local_use_map.appearances, + location, + ); + } + + fn insert_use(&mut self, local: Local, location: Location) { + Self::insert( + self.elements, + &mut self.local_use_map.first_use_at[local], + &mut self.local_use_map.appearances, + location, + ); + } + + fn insert_drop(&mut self, local: Local, location: Location) { + Self::insert( + self.elements, + &mut self.local_use_map.first_drop_at[local], + &mut self.local_use_map.appearances, + location, + ); + } + + fn insert( + elements: &RegionValueElements, + first_appearance: &mut Option<AppearanceIndex>, + appearances: &mut IndexVec<AppearanceIndex, Appearance>, + location: Location, + ) { + let point_index = elements.point_from_location(location); + let appearance_index = + appearances.push(Appearance { point_index, next: *first_appearance }); + *first_appearance = Some(appearance_index); + } +} + +impl Visitor<'_> for LocalUseMapBuild<'_> { + fn visit_local(&mut self, local: Local, context: PlaceContext, location: Location) { + if self.locals_with_use_data[local] { + match def_use::categorize(context) { + Some(DefUse::Def) => self.insert_def(local, location), + Some(DefUse::Use) => self.insert_use(local, location), + Some(DefUse::Drop) => self.insert_drop(local, location), + _ => (), + } + } + } +} diff --git a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs new file mode 100644 index 000000000..d5c401ae1 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs @@ -0,0 +1,139 @@ +use itertools::{Either, Itertools}; +use rustc_data_structures::fx::FxHashSet; +use rustc_middle::mir::{Body, Local}; +use rustc_middle::ty::{RegionVid, TyCtxt}; +use rustc_mir_dataflow::impls::MaybeInitializedPlaces; +use rustc_mir_dataflow::move_paths::MoveData; +use rustc_mir_dataflow::ResultsCursor; +use std::rc::Rc; + +use crate::{ + constraints::OutlivesConstraintSet, + facts::{AllFacts, AllFactsExt}, + location::LocationTable, + nll::ToRegionVid, + region_infer::values::RegionValueElements, + universal_regions::UniversalRegions, +}; + +use super::TypeChecker; + +mod local_use_map; +mod polonius; +mod trace; + +/// Combines liveness analysis with initialization analysis to +/// determine which variables are live at which points, both due to +/// ordinary uses and drops. Returns a set of (ty, location) pairs +/// that indicate which types must be live at which point in the CFG. +/// This vector is consumed by `constraint_generation`. +/// +/// N.B., this computation requires normalization; therefore, it must be +/// performed before +pub(super) fn generate<'mir, 'tcx>( + typeck: &mut TypeChecker<'_, 'tcx>, + body: &Body<'tcx>, + elements: &Rc<RegionValueElements>, + flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, + move_data: &MoveData<'tcx>, + location_table: &LocationTable, + use_polonius: bool, +) { + debug!("liveness::generate"); + + let free_regions = regions_that_outlive_free_regions( + typeck.infcx.num_region_vars(), + &typeck.borrowck_context.universal_regions, + &typeck.borrowck_context.constraints.outlives_constraints, + ); + let (relevant_live_locals, boring_locals) = + compute_relevant_live_locals(typeck.tcx(), &free_regions, &body); + let facts_enabled = use_polonius || AllFacts::enabled(typeck.tcx()); + + let polonius_drop_used = if facts_enabled { + let mut drop_used = Vec::new(); + polonius::populate_access_facts(typeck, body, location_table, move_data, &mut drop_used); + Some(drop_used) + } else { + None + }; + + trace::trace( + typeck, + body, + elements, + flow_inits, + move_data, + relevant_live_locals, + boring_locals, + polonius_drop_used, + ); +} + +// The purpose of `compute_relevant_live_locals` is to define the subset of `Local` +// variables for which we need to do a liveness computation. We only need +// to compute whether a variable `X` is live if that variable contains +// some region `R` in its type where `R` is not known to outlive a free +// region (i.e., where `R` may be valid for just a subset of the fn body). +fn compute_relevant_live_locals<'tcx>( + tcx: TyCtxt<'tcx>, + free_regions: &FxHashSet<RegionVid>, + body: &Body<'tcx>, +) -> (Vec<Local>, Vec<Local>) { + let (boring_locals, relevant_live_locals): (Vec<_>, Vec<_>) = + body.local_decls.iter_enumerated().partition_map(|(local, local_decl)| { + if tcx.all_free_regions_meet(&local_decl.ty, |r| { + free_regions.contains(&r.to_region_vid()) + }) { + Either::Left(local) + } else { + Either::Right(local) + } + }); + + debug!("{} total variables", body.local_decls.len()); + debug!("{} variables need liveness", relevant_live_locals.len()); + debug!("{} regions outlive free regions", free_regions.len()); + + (relevant_live_locals, boring_locals) +} + +/// Computes all regions that are (currently) known to outlive free +/// regions. For these regions, we do not need to compute +/// liveness, since the outlives constraints will ensure that they +/// are live over the whole fn body anyhow. +fn regions_that_outlive_free_regions<'tcx>( + num_region_vars: usize, + universal_regions: &UniversalRegions<'tcx>, + constraint_set: &OutlivesConstraintSet<'tcx>, +) -> FxHashSet<RegionVid> { + // Build a graph of the outlives constraints thus far. This is + // a reverse graph, so for each constraint `R1: R2` we have an + // edge `R2 -> R1`. Therefore, if we find all regions + // reachable from each free region, we will have all the + // regions that are forced to outlive some free region. + let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars); + let fr_static = universal_regions.fr_static; + let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static); + + // Stack for the depth-first search. Start out with all the free regions. + let mut stack: Vec<_> = universal_regions.universal_regions().collect(); + + // Set of all free regions, plus anything that outlives them. Initially + // just contains the free regions. + let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect(); + + // Do the DFS -- for each thing in the stack, find all things + // that outlive it and add them to the set. If they are not, + // push them onto the stack for later. + while let Some(sub_region) = stack.pop() { + stack.extend( + rev_region_graph + .outgoing_regions(sub_region) + .filter(|&r| outlives_free_region.insert(r)), + ); + } + + // Return the final set of things we visited. + outlives_free_region +} diff --git a/compiler/rustc_borrowck/src/type_check/liveness/polonius.rs b/compiler/rustc_borrowck/src/type_check/liveness/polonius.rs new file mode 100644 index 000000000..bc76a465e --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/liveness/polonius.rs @@ -0,0 +1,140 @@ +use crate::def_use::{self, DefUse}; +use crate::location::{LocationIndex, LocationTable}; +use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor}; +use rustc_middle::mir::{Body, Local, Location, Place}; +use rustc_middle::ty::subst::GenericArg; +use rustc_mir_dataflow::move_paths::{LookupResult, MoveData, MovePathIndex}; + +use super::TypeChecker; + +type VarPointRelation = Vec<(Local, LocationIndex)>; +type PathPointRelation = Vec<(MovePathIndex, LocationIndex)>; + +struct UseFactsExtractor<'me, 'tcx> { + var_defined_at: &'me mut VarPointRelation, + var_used_at: &'me mut VarPointRelation, + location_table: &'me LocationTable, + var_dropped_at: &'me mut VarPointRelation, + move_data: &'me MoveData<'tcx>, + path_accessed_at_base: &'me mut PathPointRelation, +} + +// A Visitor to walk through the MIR and extract point-wise facts +impl UseFactsExtractor<'_, '_> { + fn location_to_index(&self, location: Location) -> LocationIndex { + self.location_table.mid_index(location) + } + + fn insert_def(&mut self, local: Local, location: Location) { + debug!("UseFactsExtractor::insert_def()"); + self.var_defined_at.push((local, self.location_to_index(location))); + } + + fn insert_use(&mut self, local: Local, location: Location) { + debug!("UseFactsExtractor::insert_use()"); + self.var_used_at.push((local, self.location_to_index(location))); + } + + fn insert_drop_use(&mut self, local: Local, location: Location) { + debug!("UseFactsExtractor::insert_drop_use()"); + self.var_dropped_at.push((local, self.location_to_index(location))); + } + + fn insert_path_access(&mut self, path: MovePathIndex, location: Location) { + debug!("UseFactsExtractor::insert_path_access({:?}, {:?})", path, location); + self.path_accessed_at_base.push((path, self.location_to_index(location))); + } + + fn place_to_mpi(&self, place: &Place<'_>) -> Option<MovePathIndex> { + match self.move_data.rev_lookup.find(place.as_ref()) { + LookupResult::Exact(mpi) => Some(mpi), + LookupResult::Parent(mmpi) => mmpi, + } + } +} + +impl<'a, 'tcx> Visitor<'tcx> for UseFactsExtractor<'a, 'tcx> { + fn visit_local(&mut self, local: Local, context: PlaceContext, location: Location) { + match def_use::categorize(context) { + Some(DefUse::Def) => self.insert_def(local, location), + Some(DefUse::Use) => self.insert_use(local, location), + Some(DefUse::Drop) => self.insert_drop_use(local, location), + _ => (), + } + } + + fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, location: Location) { + self.super_place(place, context, location); + match context { + PlaceContext::NonMutatingUse(_) => { + if let Some(mpi) = self.place_to_mpi(place) { + self.insert_path_access(mpi, location); + } + } + + PlaceContext::MutatingUse(MutatingUseContext::Borrow) => { + if let Some(mpi) = self.place_to_mpi(place) { + self.insert_path_access(mpi, location); + } + } + _ => (), + } + } +} + +pub(super) fn populate_access_facts<'a, 'tcx>( + typeck: &mut TypeChecker<'a, 'tcx>, + body: &Body<'tcx>, + location_table: &LocationTable, + move_data: &MoveData<'tcx>, + dropped_at: &mut Vec<(Local, Location)>, +) { + debug!("populate_access_facts()"); + + if let Some(facts) = typeck.borrowck_context.all_facts.as_mut() { + let mut extractor = UseFactsExtractor { + var_defined_at: &mut facts.var_defined_at, + var_used_at: &mut facts.var_used_at, + var_dropped_at: &mut facts.var_dropped_at, + path_accessed_at_base: &mut facts.path_accessed_at_base, + location_table, + move_data, + }; + extractor.visit_body(&body); + + facts.var_dropped_at.extend( + dropped_at.iter().map(|&(local, location)| (local, location_table.mid_index(location))), + ); + + for (local, local_decl) in body.local_decls.iter_enumerated() { + debug!( + "add use_of_var_derefs_origin facts - local={:?}, type={:?}", + local, local_decl.ty + ); + let _prof_timer = typeck.infcx.tcx.prof.generic_activity("polonius_fact_generation"); + let universal_regions = &typeck.borrowck_context.universal_regions; + typeck.infcx.tcx.for_each_free_region(&local_decl.ty, |region| { + let region_vid = universal_regions.to_region_vid(region); + facts.use_of_var_derefs_origin.push((local, region_vid)); + }); + } + } +} + +// For every potentially drop()-touched region `region` in `local`'s type +// (`kind`), emit a Polonius `use_of_var_derefs_origin(local, origin)` fact. +pub(super) fn add_drop_of_var_derefs_origin<'tcx>( + typeck: &mut TypeChecker<'_, 'tcx>, + local: Local, + kind: &GenericArg<'tcx>, +) { + debug!("add_drop_of_var_derefs_origin(local={:?}, kind={:?}", local, kind); + if let Some(facts) = typeck.borrowck_context.all_facts.as_mut() { + let _prof_timer = typeck.infcx.tcx.prof.generic_activity("polonius_fact_generation"); + let universal_regions = &typeck.borrowck_context.universal_regions; + typeck.infcx.tcx.for_each_free_region(kind, |drop_live_region| { + let region_vid = universal_regions.to_region_vid(drop_live_region); + facts.drop_of_var_derefs_origin.push((local, region_vid)); + }); + } +} diff --git a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs new file mode 100644 index 000000000..42b577175 --- /dev/null +++ b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs @@ -0,0 +1,578 @@ +use rustc_data_structures::fx::{FxHashMap, FxHashSet}; +use rustc_index::bit_set::HybridBitSet; +use rustc_index::interval::IntervalSet; +use rustc_infer::infer::canonical::QueryRegionConstraints; +use rustc_middle::mir::{BasicBlock, Body, ConstraintCategory, Local, Location}; +use rustc_middle::ty::{Ty, TypeVisitable}; +use rustc_trait_selection::traits::query::dropck_outlives::DropckOutlivesResult; +use rustc_trait_selection::traits::query::type_op::outlives::DropckOutlives; +use rustc_trait_selection::traits::query::type_op::{TypeOp, TypeOpOutput}; +use std::rc::Rc; + +use rustc_mir_dataflow::impls::MaybeInitializedPlaces; +use rustc_mir_dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex}; +use rustc_mir_dataflow::ResultsCursor; + +use crate::{ + region_infer::values::{self, PointIndex, RegionValueElements}, + type_check::liveness::local_use_map::LocalUseMap, + type_check::liveness::polonius, + type_check::NormalizeLocation, + type_check::TypeChecker, +}; + +/// This is the heart of the liveness computation. For each variable X +/// that requires a liveness computation, it walks over all the uses +/// of X and does a reverse depth-first search ("trace") through the +/// MIR. This search stops when we find a definition of that variable. +/// The points visited in this search is the USE-LIVE set for the variable; +/// of those points is added to all the regions that appear in the variable's +/// type. +/// +/// We then also walks through each *drop* of those variables and does +/// another search, stopping when we reach a use or definition. This +/// is the DROP-LIVE set of points. Each of the points in the +/// DROP-LIVE set are to the liveness sets for regions found in the +/// `dropck_outlives` result of the variable's type (in particular, +/// this respects `#[may_dangle]` annotations). +pub(super) fn trace<'mir, 'tcx>( + typeck: &mut TypeChecker<'_, 'tcx>, + body: &Body<'tcx>, + elements: &Rc<RegionValueElements>, + flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>, + move_data: &MoveData<'tcx>, + relevant_live_locals: Vec<Local>, + boring_locals: Vec<Local>, + polonius_drop_used: Option<Vec<(Local, Location)>>, +) { + debug!("trace()"); + + let local_use_map = &LocalUseMap::build(&relevant_live_locals, elements, body); + + let cx = LivenessContext { + typeck, + body, + flow_inits, + elements, + local_use_map, + move_data, + drop_data: FxHashMap::default(), + }; + + let mut results = LivenessResults::new(cx); + + if let Some(drop_used) = polonius_drop_used { + results.add_extra_drop_facts(drop_used, relevant_live_locals.iter().copied().collect()) + } + + results.compute_for_all_locals(relevant_live_locals); + + results.dropck_boring_locals(boring_locals); +} + +/// Contextual state for the type-liveness generator. +struct LivenessContext<'me, 'typeck, 'flow, 'tcx> { + /// Current type-checker, giving us our inference context etc. + typeck: &'me mut TypeChecker<'typeck, 'tcx>, + + /// Defines the `PointIndex` mapping + elements: &'me RegionValueElements, + + /// MIR we are analyzing. + body: &'me Body<'tcx>, + + /// Mapping to/from the various indices used for initialization tracking. + move_data: &'me MoveData<'tcx>, + + /// Cache for the results of `dropck_outlives` query. + drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>, + + /// Results of dataflow tracking which variables (and paths) have been + /// initialized. + flow_inits: &'me mut ResultsCursor<'flow, 'tcx, MaybeInitializedPlaces<'flow, 'tcx>>, + + /// Index indicating where each variable is assigned, used, or + /// dropped. + local_use_map: &'me LocalUseMap, +} + +struct DropData<'tcx> { + dropck_result: DropckOutlivesResult<'tcx>, + region_constraint_data: Option<&'tcx QueryRegionConstraints<'tcx>>, +} + +struct LivenessResults<'me, 'typeck, 'flow, 'tcx> { + cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>, + + /// Set of points that define the current local. + defs: HybridBitSet<PointIndex>, + + /// Points where the current variable is "use live" -- meaning + /// that there is a future "full use" that may use its value. + use_live_at: IntervalSet<PointIndex>, + + /// Points where the current variable is "drop live" -- meaning + /// that there is no future "full use" that may use its value, but + /// there is a future drop. + drop_live_at: IntervalSet<PointIndex>, + + /// Locations where drops may occur. + drop_locations: Vec<Location>, + + /// Stack used when doing (reverse) DFS. + stack: Vec<PointIndex>, +} + +impl<'me, 'typeck, 'flow, 'tcx> LivenessResults<'me, 'typeck, 'flow, 'tcx> { + fn new(cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>) -> Self { + let num_points = cx.elements.num_points(); + LivenessResults { + cx, + defs: HybridBitSet::new_empty(num_points), + use_live_at: IntervalSet::new(num_points), + drop_live_at: IntervalSet::new(num_points), + drop_locations: vec![], + stack: vec![], + } + } + + fn compute_for_all_locals(&mut self, relevant_live_locals: Vec<Local>) { + for local in relevant_live_locals { + self.reset_local_state(); + self.add_defs_for(local); + self.compute_use_live_points_for(local); + self.compute_drop_live_points_for(local); + + let local_ty = self.cx.body.local_decls[local].ty; + + if !self.use_live_at.is_empty() { + self.cx.add_use_live_facts_for(local_ty, &self.use_live_at); + } + + if !self.drop_live_at.is_empty() { + self.cx.add_drop_live_facts_for( + local, + local_ty, + &self.drop_locations, + &self.drop_live_at, + ); + } + } + } + + // Runs dropck for locals whose liveness isn't relevant. This is + // necessary to eagerly detect unbound recursion during drop glue computation. + fn dropck_boring_locals(&mut self, boring_locals: Vec<Local>) { + for local in boring_locals { + let local_ty = self.cx.body.local_decls[local].ty; + let drop_data = self.cx.drop_data.entry(local_ty).or_insert_with({ + let typeck = &mut self.cx.typeck; + move || LivenessContext::compute_drop_data(typeck, local_ty) + }); + + drop_data.dropck_result.report_overflows( + self.cx.typeck.infcx.tcx, + self.cx.body.local_decls[local].source_info.span, + local_ty, + ); + } + } + + /// Add extra drop facts needed for Polonius. + /// + /// Add facts for all locals with free regions, since regions may outlive + /// the function body only at certain nodes in the CFG. + fn add_extra_drop_facts( + &mut self, + drop_used: Vec<(Local, Location)>, + relevant_live_locals: FxHashSet<Local>, + ) { + let locations = IntervalSet::new(self.cx.elements.num_points()); + + for (local, location) in drop_used { + if !relevant_live_locals.contains(&local) { + let local_ty = self.cx.body.local_decls[local].ty; + if local_ty.has_free_regions() { + self.cx.add_drop_live_facts_for(local, local_ty, &[location], &locations); + } + } + } + } + + /// Clear the value of fields that are "per local variable". + fn reset_local_state(&mut self) { + self.defs.clear(); + self.use_live_at.clear(); + self.drop_live_at.clear(); + self.drop_locations.clear(); + assert!(self.stack.is_empty()); + } + + /// Adds the definitions of `local` into `self.defs`. + fn add_defs_for(&mut self, local: Local) { + for def in self.cx.local_use_map.defs(local) { + debug!("- defined at {:?}", def); + self.defs.insert(def); + } + } + + /// Computes all points where local is "use live" -- meaning its + /// current value may be used later (except by a drop). This is + /// done by walking backwards from each use of `local` until we + /// find a `def` of local. + /// + /// Requires `add_defs_for(local)` to have been executed. + fn compute_use_live_points_for(&mut self, local: Local) { + debug!("compute_use_live_points_for(local={:?})", local); + + self.stack.extend(self.cx.local_use_map.uses(local)); + while let Some(p) = self.stack.pop() { + // We are live in this block from the closest to us of: + // + // * Inclusively, the block start + // * Exclusively, the previous definition (if it's in this block) + // * Exclusively, the previous live_at setting (an optimization) + let block_start = self.cx.elements.to_block_start(p); + let previous_defs = self.defs.last_set_in(block_start..=p); + let previous_live_at = self.use_live_at.last_set_in(block_start..=p); + + let exclusive_start = match (previous_defs, previous_live_at) { + (Some(a), Some(b)) => Some(std::cmp::max(a, b)), + (Some(a), None) | (None, Some(a)) => Some(a), + (None, None) => None, + }; + + if let Some(exclusive) = exclusive_start { + self.use_live_at.insert_range(exclusive + 1..=p); + + // If we have a bound after the start of the block, we should + // not add the predecessors for this block. + continue; + } else { + // Add all the elements of this block. + self.use_live_at.insert_range(block_start..=p); + + // Then add the predecessors for this block, which are the + // terminators of predecessor basic blocks. Push those onto the + // stack so that the next iteration(s) will process them. + + let block = self.cx.elements.to_location(block_start).block; + self.stack.extend( + self.cx.body.basic_blocks.predecessors()[block] + .iter() + .map(|&pred_bb| self.cx.body.terminator_loc(pred_bb)) + .map(|pred_loc| self.cx.elements.point_from_location(pred_loc)), + ); + } + } + } + + /// Computes all points where local is "drop live" -- meaning its + /// current value may be dropped later (but not used). This is + /// done by iterating over the drops of `local` where `local` (or + /// some subpart of `local`) is initialized. For each such drop, + /// we walk backwards until we find a point where `local` is + /// either defined or use-live. + /// + /// Requires `compute_use_live_points_for` and `add_defs_for` to + /// have been executed. + fn compute_drop_live_points_for(&mut self, local: Local) { + debug!("compute_drop_live_points_for(local={:?})", local); + + let mpi = self.cx.move_data.rev_lookup.find_local(local); + debug!("compute_drop_live_points_for: mpi = {:?}", mpi); + + // Find the drops where `local` is initialized. + for drop_point in self.cx.local_use_map.drops(local) { + let location = self.cx.elements.to_location(drop_point); + debug_assert_eq!(self.cx.body.terminator_loc(location.block), location,); + + if self.cx.initialized_at_terminator(location.block, mpi) { + if self.drop_live_at.insert(drop_point) { + self.drop_locations.push(location); + self.stack.push(drop_point); + } + } + } + + debug!("compute_drop_live_points_for: drop_locations={:?}", self.drop_locations); + + // Reverse DFS. But for drops, we do it a bit differently. + // The stack only ever stores *terminators of blocks*. Within + // a block, we walk back the statements in an inner loop. + while let Some(term_point) = self.stack.pop() { + self.compute_drop_live_points_for_block(mpi, term_point); + } + } + + /// Executes one iteration of the drop-live analysis loop. + /// + /// The parameter `mpi` is the `MovePathIndex` of the local variable + /// we are currently analyzing. + /// + /// The point `term_point` represents some terminator in the MIR, + /// where the local `mpi` is drop-live on entry to that terminator. + /// + /// This method adds all drop-live points within the block and -- + /// where applicable -- pushes the terminators of preceding blocks + /// onto `self.stack`. + fn compute_drop_live_points_for_block(&mut self, mpi: MovePathIndex, term_point: PointIndex) { + debug!( + "compute_drop_live_points_for_block(mpi={:?}, term_point={:?})", + self.cx.move_data.move_paths[mpi].place, + self.cx.elements.to_location(term_point), + ); + + // We are only invoked with terminators where `mpi` is + // drop-live on entry. + debug_assert!(self.drop_live_at.contains(term_point)); + + // Otherwise, scan backwards through the statements in the + // block. One of them may be either a definition or use + // live point. + let term_location = self.cx.elements.to_location(term_point); + debug_assert_eq!(self.cx.body.terminator_loc(term_location.block), term_location,); + let block = term_location.block; + let entry_point = self.cx.elements.entry_point(term_location.block); + for p in (entry_point..term_point).rev() { + debug!("compute_drop_live_points_for_block: p = {:?}", self.cx.elements.to_location(p)); + + if self.defs.contains(p) { + debug!("compute_drop_live_points_for_block: def site"); + return; + } + + if self.use_live_at.contains(p) { + debug!("compute_drop_live_points_for_block: use-live at {:?}", p); + return; + } + + if !self.drop_live_at.insert(p) { + debug!("compute_drop_live_points_for_block: already drop-live"); + return; + } + } + + let body = self.cx.body; + for &pred_block in body.basic_blocks.predecessors()[block].iter() { + debug!("compute_drop_live_points_for_block: pred_block = {:?}", pred_block,); + + // Check whether the variable is (at least partially) + // initialized at the exit of this predecessor. If so, we + // want to enqueue it on our list. If not, go check the + // next block. + // + // Note that we only need to check whether `live_local` + // became de-initialized at basic block boundaries. If it + // were to become de-initialized within the block, that + // would have been a "use-live" transition in the earlier + // loop, and we'd have returned already. + // + // NB. It's possible that the pred-block ends in a call + // which stores to the variable; in that case, the + // variable may be uninitialized "at exit" because this + // call only considers the *unconditional effects* of the + // terminator. *But*, in that case, the terminator is also + // a *definition* of the variable, in which case we want + // to stop the search anyhow. (But see Note 1 below.) + if !self.cx.initialized_at_exit(pred_block, mpi) { + debug!("compute_drop_live_points_for_block: not initialized"); + continue; + } + + let pred_term_loc = self.cx.body.terminator_loc(pred_block); + let pred_term_point = self.cx.elements.point_from_location(pred_term_loc); + + // If the terminator of this predecessor either *assigns* + // our value or is a "normal use", then stop. + if self.defs.contains(pred_term_point) { + debug!("compute_drop_live_points_for_block: defined at {:?}", pred_term_loc); + continue; + } + + if self.use_live_at.contains(pred_term_point) { + debug!("compute_drop_live_points_for_block: use-live at {:?}", pred_term_loc); + continue; + } + + // Otherwise, we are drop-live on entry to the terminator, + // so walk it. + if self.drop_live_at.insert(pred_term_point) { + debug!("compute_drop_live_points_for_block: pushed to stack"); + self.stack.push(pred_term_point); + } + } + + // Note 1. There is a weird scenario that you might imagine + // being problematic here, but which actually cannot happen. + // The problem would be if we had a variable that *is* initialized + // (but dead) on entry to the terminator, and where the current value + // will be dropped in the case of unwind. In that case, we ought to + // consider `X` to be drop-live in between the last use and call. + // Here is the example: + // + // ``` + // BB0 { + // X = ... + // use(X); // last use + // ... // <-- X ought to be drop-live here + // X = call() goto BB1 unwind BB2 + // } + // + // BB1 { + // DROP(X) + // } + // + // BB2 { + // DROP(X) + // } + // ``` + // + // However, the current code would, when walking back from BB2, + // simply stop and never explore BB0. This seems bad! But it turns + // out this code is flawed anyway -- note that the existing value of + // `X` would leak in the case where unwinding did *not* occur. + // + // What we *actually* generate is a store to a temporary + // for the call (`TMP = call()...`) and then a + // `DropAndReplace` to swap that with `X` + // (`DropAndReplace` has very particular semantics). + } +} + +impl<'tcx> LivenessContext<'_, '_, '_, 'tcx> { + /// Returns `true` if the local variable (or some part of it) is initialized at the current + /// cursor position. Callers should call one of the `seek` methods immediately before to point + /// the cursor to the desired location. + fn initialized_at_curr_loc(&self, mpi: MovePathIndex) -> bool { + let state = self.flow_inits.get(); + if state.contains(mpi) { + return true; + } + + let move_paths = &self.flow_inits.analysis().move_data().move_paths; + move_paths[mpi].find_descendant(&move_paths, |mpi| state.contains(mpi)).is_some() + } + + /// Returns `true` if the local variable (or some part of it) is initialized in + /// the terminator of `block`. We need to check this to determine if a + /// DROP of some local variable will have an effect -- note that + /// drops, as they may unwind, are always terminators. + fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool { + self.flow_inits.seek_before_primary_effect(self.body.terminator_loc(block)); + self.initialized_at_curr_loc(mpi) + } + + /// Returns `true` if the path `mpi` (or some part of it) is initialized at + /// the exit of `block`. + /// + /// **Warning:** Does not account for the result of `Call` + /// instructions. + fn initialized_at_exit(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool { + self.flow_inits.seek_after_primary_effect(self.body.terminator_loc(block)); + self.initialized_at_curr_loc(mpi) + } + + /// Stores the result that all regions in `value` are live for the + /// points `live_at`. + fn add_use_live_facts_for( + &mut self, + value: impl TypeVisitable<'tcx>, + live_at: &IntervalSet<PointIndex>, + ) { + debug!("add_use_live_facts_for(value={:?})", value); + + Self::make_all_regions_live(self.elements, &mut self.typeck, value, live_at) + } + + /// Some variable with type `live_ty` is "drop live" at `location` + /// -- i.e., it may be dropped later. This means that *some* of + /// the regions in its type must be live at `location`. The + /// precise set will depend on the dropck constraints, and in + /// particular this takes `#[may_dangle]` into account. + fn add_drop_live_facts_for( + &mut self, + dropped_local: Local, + dropped_ty: Ty<'tcx>, + drop_locations: &[Location], + live_at: &IntervalSet<PointIndex>, + ) { + debug!( + "add_drop_live_constraint(\ + dropped_local={:?}, \ + dropped_ty={:?}, \ + drop_locations={:?}, \ + live_at={:?})", + dropped_local, + dropped_ty, + drop_locations, + values::location_set_str(self.elements, live_at.iter()), + ); + + let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({ + let typeck = &mut self.typeck; + move || Self::compute_drop_data(typeck, dropped_ty) + }); + + if let Some(data) = &drop_data.region_constraint_data { + for &drop_location in drop_locations { + self.typeck.push_region_constraints( + drop_location.to_locations(), + ConstraintCategory::Boring, + data, + ); + } + } + + drop_data.dropck_result.report_overflows( + self.typeck.infcx.tcx, + self.body.source_info(*drop_locations.first().unwrap()).span, + dropped_ty, + ); + + // All things in the `outlives` array may be touched by + // the destructor and must be live at this point. + for &kind in &drop_data.dropck_result.kinds { + Self::make_all_regions_live(self.elements, &mut self.typeck, kind, live_at); + + polonius::add_drop_of_var_derefs_origin(&mut self.typeck, dropped_local, &kind); + } + } + + fn make_all_regions_live( + elements: &RegionValueElements, + typeck: &mut TypeChecker<'_, 'tcx>, + value: impl TypeVisitable<'tcx>, + live_at: &IntervalSet<PointIndex>, + ) { + debug!("make_all_regions_live(value={:?})", value); + debug!( + "make_all_regions_live: live_at={}", + values::location_set_str(elements, live_at.iter()), + ); + + let tcx = typeck.tcx(); + tcx.for_each_free_region(&value, |live_region| { + let live_region_vid = + typeck.borrowck_context.universal_regions.to_region_vid(live_region); + typeck + .borrowck_context + .constraints + .liveness_constraints + .add_elements(live_region_vid, live_at); + }); + } + + fn compute_drop_data( + typeck: &mut TypeChecker<'_, 'tcx>, + dropped_ty: Ty<'tcx>, + ) -> DropData<'tcx> { + debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,); + + let param_env = typeck.param_env; + let TypeOpOutput { output, constraints, .. } = + param_env.and(DropckOutlives::new(dropped_ty)).fully_perform(typeck.infcx).unwrap(); + + DropData { dropck_result: output, region_constraint_data: constraints } + } +} |