diff options
7 files changed, 179 insertions, 267 deletions
diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs index 84fdbb9423e..2d3800dd1dd 100644 --- a/src/librustc_mir/borrow_check/nll/mod.rs +++ b/src/librustc_mir/borrow_check/nll/mod.rs @@ -2,7 +2,6 @@ use crate::borrow_check::borrow_set::BorrowSet; use crate::borrow_check::location::{LocationIndex, LocationTable}; use crate::borrow_check::nll::facts::AllFactsExt; use crate::borrow_check::nll::type_check::{MirTypeckResults, MirTypeckRegionConstraints}; -use crate::borrow_check::nll::type_check::liveness::liveness_map::NllLivenessMap; use crate::borrow_check::nll::region_infer::values::RegionValueElements; use crate::dataflow::indexes::BorrowIndex; use crate::dataflow::move_paths::MoveData; diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/liveness_map.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/liveness_map.rs deleted file mode 100644 index b9f9d83161b..00000000000 --- a/src/librustc_mir/borrow_check/nll/type_check/liveness/liveness_map.rs +++ /dev/null @@ -1,94 +0,0 @@ -//! For the NLL computation, we need to compute liveness, but only for those -//! local variables whose types contain regions. The others are not of interest -//! to us. This file defines a new index type (LiveVar) that indexes into -//! a list of "variables whose type contain regions". It also defines a map from -//! Local to LiveVar and vice versa -- this map can be given to the -//! liveness code so that it only operates over variables with regions in their -//! types, instead of all variables. - -use crate::borrow_check::nll::ToRegionVid; -use crate::borrow_check::nll::facts::{AllFacts, AllFactsExt}; -use crate::util::liveness::LiveVariableMap; -use rustc::mir::{Local, Mir}; -use rustc::ty::{RegionVid, TyCtxt}; -use rustc_data_structures::fx::FxHashSet; -use rustc_data_structures::indexed_vec::{Idx, IndexVec}; - -/// Map between Local and LiveVar indices: the purpose of this -/// map 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). -crate struct NllLivenessMap { - /// For each local variable, contains `Some(i)` if liveness is - /// needed for this variable. - pub from_local: IndexVec<Local, Option<LiveVar>>, - - /// For each `LiveVar`, maps back to the original `Local` index. - pub to_local: IndexVec<LiveVar, Local>, -} - -impl LiveVariableMap for NllLivenessMap { - fn from_local(&self, local: Local) -> Option<Self::LiveVar> { - self.from_local[local] - } - - type LiveVar = LiveVar; - - fn from_live_var(&self, local: Self::LiveVar) -> Local { - self.to_local[local] - } - - fn num_variables(&self) -> usize { - self.to_local.len() - } -} - -impl NllLivenessMap { - crate fn compute( - tcx: TyCtxt<'_, '_, 'tcx>, - free_regions: &FxHashSet<RegionVid>, - mir: &Mir<'tcx>, - ) -> Self { - let mut to_local = IndexVec::default(); - let facts_enabled = AllFacts::enabled(tcx); - let from_local: IndexVec<Local, Option<_>> = mir.local_decls - .iter_enumerated() - .map(|(local, local_decl)| { - if tcx.all_free_regions_meet(&local_decl.ty, |r| { - free_regions.contains(&r.to_region_vid()) - }) && !facts_enabled { - // If all the regions in the type are free regions - // (or there are no regions), then we don't need - // to track liveness for this variable. - None - } else { - Some(to_local.push(local)) - } - }) - .collect(); - - debug!("{} total variables", mir.local_decls.len()); - debug!("{} variables need liveness", to_local.len()); - debug!("{} regions outlive free regions", free_regions.len()); - - Self { - from_local, - to_local, - } - } - - /// Returns `true` if there are no local variables that need liveness computation. - crate fn is_empty(&self) -> bool { - self.to_local.is_empty() - } -} - -/// Index given to each local variable for which we need to -/// compute liveness information. For many locals, we are able to -/// skip liveness information: for example, those variables whose -/// types contain no regions. -newtype_index! { - pub struct LiveVar { .. } -} diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs index e9765d2798c..9b894009885 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs @@ -1,6 +1,5 @@ use crate::borrow_check::nll::region_infer::values::{PointIndex, RegionValueElements}; -use crate::borrow_check::nll::type_check::liveness::liveness_map::{LiveVar, NllLivenessMap}; -use crate::util::liveness::{categorize, DefUse, LiveVariableMap}; +use crate::util::liveness::{categorize, DefUse}; use rustc::mir::visit::{PlaceContext, Visitor}; use rustc::mir::{Local, Location, Mir}; use rustc_data_structures::indexed_vec::{Idx, IndexVec}; @@ -9,26 +8,33 @@ use rustc_data_structures::vec_linked_list as vll; /// A map that cross references each local with the locations where it /// is defined (assigned), used, or dropped. Used during liveness /// computation. -crate struct LocalUseMap<'me> { - liveness_map: &'me NllLivenessMap, - +/// +/// 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. +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<LiveVar, Option<AppearanceIndex>>, + 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<LiveVar, Option<AppearanceIndex>>, + 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<LiveVar, Option<AppearanceIndex>>, + first_drop_at: IndexVec<Local, Option<AppearanceIndex>>, appearances: IndexVec<AppearanceIndex, Appearance>, } @@ -50,52 +56,68 @@ impl vll::LinkElem for Appearance { } } -impl LocalUseMap<'me> { +impl LocalUseMap { crate fn build( - liveness_map: &'me NllLivenessMap, + live_locals: &Vec<Local>, elements: &RegionValueElements, mir: &Mir<'_>, ) -> Self { - let nones = IndexVec::from_elem_n(None, liveness_map.num_variables()); + let nones = IndexVec::from_elem_n(None, mir.local_decls.len()); let mut local_use_map = LocalUseMap { - liveness_map, first_def_at: nones.clone(), first_use_at: nones.clone(), first_drop_at: nones, appearances: IndexVec::new(), }; + let mut locals_with_use_data: IndexVec<Local, bool> = + IndexVec::from_elem_n(false, mir.local_decls.len()); + live_locals + .iter() + .for_each(|&local| locals_with_use_data[local] = true); + LocalUseMapBuild { local_use_map: &mut local_use_map, elements, - }.visit_mir(mir); + locals_with_use_data, + } + .visit_mir(mir); local_use_map } - crate fn defs(&self, local: LiveVar) -> impl Iterator<Item = PointIndex> + '_ { + 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) } - crate fn uses(&self, local: LiveVar) -> impl Iterator<Item = PointIndex> + '_ { + 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) } - crate fn drops(&self, local: LiveVar) -> impl Iterator<Item = PointIndex> + '_ { + 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, 'map: 'me> { - local_use_map: &'me mut LocalUseMap<'map>, +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: LiveVar, location: Location) { +impl LocalUseMapBuild<'_> { + fn insert_def(&mut self, local: Local, location: Location) { Self::insert( self.elements, &mut self.local_use_map.first_def_at[local], @@ -104,7 +126,7 @@ impl LocalUseMapBuild<'_, '_> { ); } - fn insert_use(&mut self, local: LiveVar, location: Location) { + fn insert_use(&mut self, local: Local, location: Location) { Self::insert( self.elements, &mut self.local_use_map.first_use_at[local], @@ -113,7 +135,7 @@ impl LocalUseMapBuild<'_, '_> { ); } - fn insert_drop(&mut self, local: LiveVar, location: Location) { + fn insert_drop(&mut self, local: Local, location: Location) { Self::insert( self.elements, &mut self.local_use_map.first_drop_at[local], @@ -137,13 +159,13 @@ impl LocalUseMapBuild<'_, '_> { } } -impl Visitor<'tcx> for LocalUseMapBuild<'_, '_> { +impl Visitor<'tcx> for LocalUseMapBuild<'_> { fn visit_local(&mut self, &local: &Local, context: PlaceContext<'tcx>, location: Location) { - if let Some(local_with_region) = self.local_use_map.liveness_map.from_local(local) { + if self.locals_with_use_data[local] { match categorize(context) { - Some(DefUse::Def) => self.insert_def(local_with_region, location), - Some(DefUse::Use) => self.insert_use(local_with_region, location), - Some(DefUse::Drop) => self.insert_drop(local_with_region, location), + 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/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs index 28a8cad8ca2..960e75048fa 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs @@ -1,19 +1,19 @@ use crate::borrow_check::location::LocationTable; -use crate::borrow_check::nll::region_infer::values::RegionValueElements; use crate::borrow_check::nll::constraints::ConstraintSet; -use crate::borrow_check::nll::NllLivenessMap; +use crate::borrow_check::nll::facts::{AllFacts, AllFactsExt}; +use crate::borrow_check::nll::region_infer::values::RegionValueElements; use crate::borrow_check::nll::universal_regions::UniversalRegions; +use crate::borrow_check::nll::ToRegionVid; use crate::dataflow::move_paths::MoveData; -use crate::dataflow::MaybeInitializedPlaces; use crate::dataflow::FlowAtLocation; -use rustc::mir::Mir; -use rustc::ty::RegionVid; +use crate::dataflow::MaybeInitializedPlaces; +use rustc::mir::{Local, Mir}; +use rustc::ty::{RegionVid, TyCtxt}; use rustc_data_structures::fx::FxHashSet; use std::rc::Rc; use super::TypeChecker; -crate mod liveness_map; mod local_use_map; mod trace; @@ -34,16 +34,71 @@ pub(super) fn generate<'gcx, 'tcx>( location_table: &LocationTable, ) { debug!("liveness::generate"); - let free_regions = { - let borrowck_context = typeck.borrowck_context.as_ref().unwrap(); - regions_that_outlive_free_regions( - typeck.infcx.num_region_vars(), - &borrowck_context.universal_regions, - &borrowck_context.constraints.outlives_constraints, - ) + + let live_locals: Vec<Local> = if AllFacts::enabled(typeck.tcx()) { + // If "dump facts from NLL analysis" was requested perform + // the liveness analysis for all `Local`s. This case opens + // the possibility of the variables being analyzed in `trace` + // to be *any* `Local`, not just the "live" ones, so we can't + // make any assumptions past this point as to the characteristics + // of the `live_locals`. + // FIXME: Review "live" terminology past this point, we should + // not be naming the `Local`s as live. + mir.local_decls.indices().collect() + } else { + let free_regions = { + let borrowck_context = typeck.borrowck_context.as_ref().unwrap(); + regions_that_outlive_free_regions( + typeck.infcx.num_region_vars(), + &borrowck_context.universal_regions, + &borrowck_context.constraints.outlives_constraints, + ) + }; + compute_live_locals(typeck.tcx(), &free_regions, mir) }; - let liveness_map = NllLivenessMap::compute(typeck.tcx(), &free_regions, mir); - trace::trace(typeck, mir, elements, flow_inits, move_data, &liveness_map, location_table); + + if !live_locals.is_empty() { + trace::trace( + typeck, + mir, + elements, + flow_inits, + move_data, + live_locals, + location_table, + ); + } +} + +// The purpose of `compute_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_live_locals( + tcx: TyCtxt<'_, '_, 'tcx>, + free_regions: &FxHashSet<RegionVid>, + mir: &Mir<'tcx>, +) -> Vec<Local> { + let live_locals: Vec<Local> = mir + .local_decls + .iter_enumerated() + .filter_map(|(local, local_decl)| { + if tcx.all_free_regions_meet(&local_decl.ty, |r| { + free_regions.contains(&r.to_region_vid()) + }) { + None + } else { + Some(local) + } + }) + .collect(); + + debug!("{} total variables", mir.local_decls.len()); + debug!("{} variables need liveness", live_locals.len()); + debug!("{} regions outlive free regions", free_regions.len()); + + live_locals } /// Computes all regions that are (currently) known to outlive free diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs index 4a0b4b7c205..f0df7070e6b 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs @@ -1,13 +1,11 @@ use crate::borrow_check::location::LocationTable; use crate::borrow_check::nll::region_infer::values::{self, PointIndex, RegionValueElements}; -use crate::borrow_check::nll::type_check::liveness::liveness_map::{LiveVar, NllLivenessMap}; use crate::borrow_check::nll::type_check::liveness::local_use_map::LocalUseMap; use crate::borrow_check::nll::type_check::NormalizeLocation; use crate::borrow_check::nll::type_check::TypeChecker; use crate::dataflow::move_paths::indexes::MovePathIndex; use crate::dataflow::move_paths::MoveData; use crate::dataflow::{FlowAtLocation, FlowsAtLocation, MaybeInitializedPlaces}; -use crate::util::liveness::LiveVariableMap; use rustc::infer::canonical::QueryRegionConstraint; use rustc::mir::{BasicBlock, ConstraintCategory, Local, Location, Mir}; use rustc::traits::query::dropck_outlives::DropckOutlivesResult; @@ -38,16 +36,12 @@ pub(super) fn trace( elements: &Rc<RegionValueElements>, flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'gcx, 'tcx>>, move_data: &MoveData<'tcx>, - liveness_map: &NllLivenessMap, + live_locals: Vec<Local>, location_table: &LocationTable, ) { debug!("trace()"); - if liveness_map.is_empty() { - return; - } - - let local_use_map = &LocalUseMap::build(liveness_map, elements, mir); + let local_use_map = &LocalUseMap::build(&live_locals, elements, mir); let cx = LivenessContext { typeck, @@ -56,12 +50,11 @@ pub(super) fn trace( elements, local_use_map, move_data, - liveness_map, drop_data: FxHashMap::default(), location_table, }; - LivenessResults::new(cx).compute_for_all_locals(); + LivenessResults::new(cx).compute_for_all_locals(live_locals); } /// Contextual state for the type-liveness generator. @@ -93,10 +86,7 @@ where /// Index indicating where each variable is assigned, used, or /// dropped. - local_use_map: &'me LocalUseMap<'me>, - - /// Map tracking which variables need liveness computation. - liveness_map: &'me NllLivenessMap, + local_use_map: &'me LocalUseMap, /// Maps between a MIR Location and a LocationIndex location_table: &'me LocationTable, @@ -148,15 +138,12 @@ impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { } } - fn compute_for_all_locals(&mut self) { - for live_local in self.cx.liveness_map.to_local.indices() { - let local = self.cx.liveness_map.from_live_var(live_local); - debug!("local={:?} live_local={:?}", local, live_local); - + fn compute_for_all_locals(&mut self, live_locals: Vec<Local>) { + for local in live_locals { self.reset_local_state(); - self.add_defs_for(live_local); - self.compute_use_live_points_for(live_local); - self.compute_drop_live_points_for(live_local); + self.add_defs_for(local); + self.compute_use_live_points_for(local); + self.compute_drop_live_points_for(local); let local_ty = self.cx.mir.local_decls[local].ty; @@ -185,8 +172,8 @@ impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { } /// Adds the definitions of `local` into `self.defs`. - fn add_defs_for(&mut self, live_local: LiveVar) { - for def in self.cx.local_use_map.defs(live_local) { + 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); } @@ -194,14 +181,14 @@ impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { /// 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 `live_local` until we + /// done by walking backwards from each use of `local` until we /// find a `def` of local. /// - /// Requires `add_defs_for(live_local)` to have been executed. - fn compute_use_live_points_for(&mut self, live_local: LiveVar) { - debug!("compute_use_live_points_for(live_local={:?})", live_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(live_local)); + self.stack.extend(self.cx.local_use_map.uses(local)); while let Some(p) = self.stack.pop() { if self.defs.contains(p) { continue; @@ -224,15 +211,14 @@ impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { /// /// Requires `compute_use_live_points_for` and `add_defs_for` to /// have been executed. - fn compute_drop_live_points_for(&mut self, live_local: LiveVar) { - debug!("compute_drop_live_points_for(live_local={:?})", live_local); + fn compute_drop_live_points_for(&mut self, local: Local) { + debug!("compute_drop_live_points_for(local={:?})", local); - let local = self.cx.liveness_map.from_live_var(live_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(live_local) { + 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.mir.terminator_loc(location.block), location,); diff --git a/src/librustc_mir/transform/generator.rs b/src/librustc_mir/transform/generator.rs index c455d38cebc..6a71b581528 100644 --- a/src/librustc_mir/transform/generator.rs +++ b/src/librustc_mir/transform/generator.rs @@ -68,7 +68,7 @@ use crate::transform::no_landing_pads::no_landing_pads; use crate::dataflow::{do_dataflow, DebugFormatted, state_for_location}; use crate::dataflow::{MaybeStorageLive, HaveBeenBorrowedLocals}; use crate::util::dump_mir; -use crate::util::liveness::{self, IdentityMap}; +use crate::util::liveness; pub struct StateTransform; @@ -148,7 +148,7 @@ struct SuspensionPoint { state: u32, resume: BasicBlock, drop: Option<BasicBlock>, - storage_liveness: liveness::LiveVarSet<Local>, + storage_liveness: liveness::LiveVarSet, } struct TransformVisitor<'a, 'tcx: 'a> { @@ -165,7 +165,7 @@ struct TransformVisitor<'a, 'tcx: 'a> { // A map from a suspension point in a block to the locals which have live storage at that point // FIXME(eddyb) This should use `IndexVec<BasicBlock, Option<_>>`. - storage_liveness: FxHashMap<BasicBlock, liveness::LiveVarSet<Local>>, + storage_liveness: FxHashMap<BasicBlock, liveness::LiveVarSet>, // A list of suspension points, generated during the transform suspension_points: Vec<SuspensionPoint>, @@ -358,7 +358,7 @@ fn replace_result_variable<'tcx>( new_ret_local } -struct StorageIgnored(liveness::LiveVarSet<Local>); +struct StorageIgnored(liveness::LiveVarSet); impl<'tcx> Visitor<'tcx> for StorageIgnored { fn visit_statement(&mut self, @@ -379,8 +379,8 @@ fn locals_live_across_suspend_points( source: MirSource<'tcx>, movable: bool, ) -> ( - liveness::LiveVarSet<Local>, - FxHashMap<BasicBlock, liveness::LiveVarSet<Local>>, + liveness::LiveVarSet, + FxHashMap<BasicBlock, liveness::LiveVarSet>, ) { let dead_unwinds = BitSet::new_empty(mir.basic_blocks().len()); let node_id = tcx.hir().as_local_node_id(source.def_id()).unwrap(); @@ -414,14 +414,12 @@ fn locals_live_across_suspend_points( let mut set = liveness::LiveVarSet::new_empty(mir.local_decls.len()); let mut liveness = liveness::liveness_of_locals( mir, - &IdentityMap::new(mir), ); liveness::dump_mir( tcx, "generator_liveness", source, mir, - &IdentityMap::new(mir), &liveness, ); @@ -491,7 +489,7 @@ fn compute_layout<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, mir: &mut Mir<'tcx>) -> (FxHashMap<Local, (Ty<'tcx>, usize)>, GeneratorLayout<'tcx>, - FxHashMap<BasicBlock, liveness::LiveVarSet<Local>>) + FxHashMap<BasicBlock, liveness::LiveVarSet>) { // Use a liveness analysis to compute locals which are live across a suspension point let (live_locals, storage_liveness) = locals_live_across_suspend_points(tcx, diff --git a/src/librustc_mir/util/liveness.rs b/src/librustc_mir/util/liveness.rs index dcbd9aa9af2..9cda6cfdacb 100644 --- a/src/librustc_mir/util/liveness.rs +++ b/src/librustc_mir/util/liveness.rs @@ -39,7 +39,7 @@ use std::path::{Path, PathBuf}; use crate::transform::MirSource; use crate::util::pretty::{dump_enabled, write_basic_block, write_mir_intro}; -pub type LiveVarSet<V> = BitSet<V>; +pub type LiveVarSet = BitSet<Local>; /// This gives the result of the liveness analysis at the boundary of /// basic blocks. @@ -48,66 +48,27 @@ pub type LiveVarSet<V> = BitSet<V>; /// liveness for. This is often `Local`, in which case we computed /// liveness for all variables -- but it can also be some other type, /// which indicates a subset of the variables within the graph. -pub struct LivenessResult<V: Idx> { +pub struct LivenessResult { /// Live variables on exit to each basic block. This is equal to /// the union of the `ins` for each successor. - pub outs: IndexVec<BasicBlock, LiveVarSet<V>>, -} - -/// Defines the mapping to/from the MIR local variables (`Local`) to -/// the "live variable indices" we are using in a particular -/// computation. -pub trait LiveVariableMap { - type LiveVar; - - fn from_local(&self, local: Local) -> Option<Self::LiveVar>; - fn from_live_var(&self, local: Self::LiveVar) -> Local; - fn num_variables(&self) -> usize; -} - -#[derive(Debug)] -pub struct IdentityMap<'a, 'tcx: 'a> { - mir: &'a Mir<'tcx>, -} - -impl<'a, 'tcx> IdentityMap<'a, 'tcx> { - pub fn new(mir: &'a Mir<'tcx>) -> Self { - Self { mir } - } -} - -impl<'a, 'tcx> LiveVariableMap for IdentityMap<'a, 'tcx> { - type LiveVar = Local; - - fn from_local(&self, local: Local) -> Option<Self::LiveVar> { - Some(local) - } - - fn from_live_var(&self, local: Self::LiveVar) -> Local { - local - } - - fn num_variables(&self) -> usize { - self.mir.local_decls.len() - } + pub outs: IndexVec<BasicBlock, LiveVarSet>, } /// Computes which local variables are live within the given function /// `mir`. The liveness mode `mode` determines what sorts of uses are /// considered to make a variable live (e.g., do drops count?). -pub fn liveness_of_locals<'tcx, V: Idx>( +pub fn liveness_of_locals<'tcx>( mir: &Mir<'tcx>, - map: &impl LiveVariableMap<LiveVar = V>, -) -> LivenessResult<V> { - let num_live_vars = map.num_variables(); +) -> LivenessResult { + let num_live_vars = mir.local_decls.len(); - let def_use: IndexVec<_, DefsUses<V>> = mir + let def_use: IndexVec<_, DefsUses> = mir .basic_blocks() .iter() - .map(|b| block(map, b, num_live_vars)) + .map(|b| block(b, num_live_vars)) .collect(); - let mut outs: IndexVec<_, LiveVarSet<V>> = mir + let mut outs: IndexVec<_, LiveVarSet> = mir .basic_blocks() .indices() .map(|_| LiveVarSet::new_empty(num_live_vars)) @@ -211,27 +172,23 @@ pub fn categorize<'tcx>(context: PlaceContext<'tcx>) -> Option<DefUse> { } } -struct DefsUsesVisitor<'lv, V, M> -where - V: Idx, - M: LiveVariableMap<LiveVar = V> + 'lv, +struct DefsUsesVisitor { - map: &'lv M, - defs_uses: DefsUses<V>, + defs_uses: DefsUses, } #[derive(Eq, PartialEq, Clone)] -struct DefsUses<V: Idx> { - defs: LiveVarSet<V>, - uses: LiveVarSet<V>, +struct DefsUses { + defs: LiveVarSet, + uses: LiveVarSet, } -impl<V: Idx> DefsUses<V> { - fn apply(&self, bits: &mut LiveVarSet<V>) -> bool { +impl DefsUses { + fn apply(&self, bits: &mut LiveVarSet) -> bool { bits.subtract(&self.defs) | bits.union(&self.uses) } - fn add_def(&mut self, index: V) { + fn add_def(&mut self, index: Local) { // If it was used already in the block, remove that use // now that we found a definition. // @@ -245,7 +202,7 @@ impl<V: Idx> DefsUses<V> { self.defs.insert(index); } - fn add_use(&mut self, index: V) { + fn add_use(&mut self, index: Local) { // Inverse of above. // // Example: @@ -261,29 +218,22 @@ impl<V: Idx> DefsUses<V> { } } -impl<'tcx, 'lv, V, M> Visitor<'tcx> for DefsUsesVisitor<'lv, V, M> -where - V: Idx, - M: LiveVariableMap<LiveVar = V>, +impl<'tcx> Visitor<'tcx> for DefsUsesVisitor { fn visit_local(&mut self, &local: &Local, context: PlaceContext<'tcx>, _: Location) { - if let Some(v_index) = self.map.from_local(local) { - match categorize(context) { - Some(DefUse::Def) => self.defs_uses.add_def(v_index), - Some(DefUse::Use) | Some(DefUse::Drop) => self.defs_uses.add_use(v_index), - _ => (), - } + match categorize(context) { + Some(DefUse::Def) => self.defs_uses.add_def(local), + Some(DefUse::Use) | Some(DefUse::Drop) => self.defs_uses.add_use(local), + _ => (), } } } -fn block<'tcx, V: Idx>( - map: &impl LiveVariableMap<LiveVar = V>, +fn block<'tcx>( b: &BasicBlockData<'tcx>, locals: usize, -) -> DefsUses<V> { +) -> DefsUses { let mut visitor = DefsUsesVisitor { - map, defs_uses: DefsUses { defs: LiveVarSet::new_empty(locals), uses: LiveVarSet::new_empty(locals), @@ -305,13 +255,12 @@ fn block<'tcx, V: Idx>( visitor.defs_uses } -pub fn dump_mir<'a, 'tcx, V: Idx>( +pub fn dump_mir<'a, 'tcx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, pass_name: &str, source: MirSource<'tcx>, mir: &Mir<'tcx>, - map: &impl LiveVariableMap<LiveVar = V>, - result: &LivenessResult<V>, + result: &LivenessResult, ) { if !dump_enabled(tcx, pass_name, source) { return; @@ -320,17 +269,16 @@ pub fn dump_mir<'a, 'tcx, V: Idx>( // see notes on #41697 below tcx.item_path_str(source.def_id()) }); - dump_matched_mir_node(tcx, pass_name, &node_path, source, mir, map, result); + dump_matched_mir_node(tcx, pass_name, &node_path, source, mir, result); } -fn dump_matched_mir_node<'a, 'tcx, V: Idx>( +fn dump_matched_mir_node<'a, 'tcx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, pass_name: &str, node_path: &str, source: MirSource<'tcx>, mir: &Mir<'tcx>, - map: &dyn LiveVariableMap<LiveVar = V>, - result: &LivenessResult<V>, + result: &LivenessResult, ) { let mut file_path = PathBuf::new(); file_path.push(Path::new(&tcx.sess.opts.debugging_opts.dump_mir_dir)); @@ -342,25 +290,23 @@ fn dump_matched_mir_node<'a, 'tcx, V: Idx>( writeln!(file, "// source = {:?}", source)?; writeln!(file, "// pass_name = {}", pass_name)?; writeln!(file, "")?; - write_mir_fn(tcx, source, mir, map, &mut file, result)?; + write_mir_fn(tcx, source, mir, &mut file, result)?; Ok(()) }); } -pub fn write_mir_fn<'a, 'tcx, V: Idx>( +pub fn write_mir_fn<'a, 'tcx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, src: MirSource<'tcx>, mir: &Mir<'tcx>, - map: &dyn LiveVariableMap<LiveVar = V>, w: &mut dyn Write, - result: &LivenessResult<V>, + result: &LivenessResult, ) -> io::Result<()> { write_mir_intro(tcx, src, mir, w)?; for block in mir.basic_blocks().indices() { - let print = |w: &mut dyn Write, prefix, result: &IndexVec<BasicBlock, LiveVarSet<V>>| { + let print = |w: &mut dyn Write, prefix, result: &IndexVec<BasicBlock, LiveVarSet>| { let live: Vec<String> = result[block] .iter() - .map(|v| map.from_live_var(v)) .map(|local| format!("{:?}", local)) .collect(); writeln!(w, "{} {{{}}}", prefix, live.join(", ")) |