diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/librustc_mir/borrow_check/nll/liveness_map.rs | 77 | ||||
| -rw-r--r-- | src/librustc_mir/borrow_check/nll/mod.rs | 22 | ||||
| -rw-r--r-- | src/librustc_mir/borrow_check/nll/type_check/liveness.rs | 27 | ||||
| -rw-r--r-- | src/librustc_mir/borrow_check/nll/type_check/mod.rs | 3 | ||||
| -rw-r--r-- | src/librustc_mir/transform/generator.rs | 41 | ||||
| -rw-r--r-- | src/librustc_mir/util/liveness.rs | 245 | ||||
| -rw-r--r-- | src/test/mir-opt/nll/liveness-call-subtlety.rs | 45 | ||||
| -rw-r--r-- | src/test/mir-opt/nll/liveness-drop-intra-block.rs | 41 | ||||
| -rw-r--r-- | src/test/mir-opt/nll/liveness-interblock.rs | 48 | ||||
| -rw-r--r-- | src/test/mir-opt/nll/region-liveness-basic.rs | 58 | ||||
| -rw-r--r-- | src/test/mir-opt/nll/region-liveness-two-disjoint-uses.rs | 52 |
11 files changed, 302 insertions, 357 deletions
diff --git a/src/librustc_mir/borrow_check/nll/liveness_map.rs b/src/librustc_mir/borrow_check/nll/liveness_map.rs new file mode 100644 index 00000000000..cbd9c9a4e1a --- /dev/null +++ b/src/librustc_mir/borrow_check/nll/liveness_map.rs @@ -0,0 +1,77 @@ +// Copyright 2018 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! 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 (LocalWithRegion) that indexes into +//! a list of "variables whose type contain regions". It also defines a map from +//! Local to LocalWithRegion 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 rustc::ty::TypeFoldable; +use rustc_data_structures::indexed_vec::IndexVec; +use rustc::mir::{Mir, Local}; +use util::liveness::LiveVariableMap; + +use rustc_data_structures::indexed_vec::Idx; + +/// Map between Local and LocalWithRegion indices: this map is supplied to the +/// liveness code so that it will only analyze those variables whose types +/// contain regions. +crate struct NllLivenessMap { + /// For each local variable, contains either None (if the type has no regions) + /// or Some(i) with a suitable index. + pub from_local: IndexVec<Local, Option<LocalWithRegion>>, + /// For each LocalWithRegion, maps back to the original Local index. + pub to_local: IndexVec<LocalWithRegion, Local>, + +} + +impl LiveVariableMap for NllLivenessMap { + + fn from_local(&self, local: Local) -> Option<Self::LiveVar> { + self.from_local[local] + } + + type LiveVar = LocalWithRegion; + + fn from_live_var(&self, local: Self::LiveVar) -> Local { + self.to_local[local] + } + + fn num_variables(&self) -> usize { + self.to_local.len() + } +} + +impl NllLivenessMap { + /// Iterates over the variables in Mir and assigns each Local whose type contains + /// regions a LocalWithRegion index. Returns a map for converting back and forth. + pub fn compute(mir: &Mir) -> Self { + let mut to_local = IndexVec::default(); + let from_local: IndexVec<Local,Option<_>> = mir + .local_decls + .iter_enumerated() + .map(|(local, local_decl)| { + if local_decl.ty.has_free_regions() { + Some(to_local.push(local)) + } + else { + None + } + }).collect(); + + Self { from_local, to_local } + } +} + +/// Index given to each local variable whose type contains a region. +newtype_index!(LocalWithRegion); diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs index 5fcf46f6903..76f8fa206be 100644 --- a/src/librustc_mir/borrow_check/nll/mod.rs +++ b/src/librustc_mir/borrow_check/nll/mod.rs @@ -13,6 +13,7 @@ use borrow_check::location::{LocationIndex, LocationTable}; use borrow_check::nll::facts::AllFactsExt; use borrow_check::nll::type_check::MirTypeckRegionConstraints; use borrow_check::nll::region_infer::values::RegionValueElements; +use borrow_check::nll::liveness_map::{NllLivenessMap, LocalWithRegion}; use dataflow::indexes::BorrowIndex; use dataflow::move_paths::MoveData; use dataflow::FlowAtLocation; @@ -30,7 +31,7 @@ use std::path::PathBuf; use std::rc::Rc; use std::str::FromStr; use transform::MirSource; -use util::liveness::{LivenessResults, LocalSet}; +use util::liveness::{LivenessResults, LiveVarSet}; use self::mir_util::PassWhere; use polonius_engine::{Algorithm, Output}; @@ -45,6 +46,7 @@ crate mod region_infer; mod renumber; crate mod type_check; mod universal_regions; +crate mod liveness_map; mod constraints; @@ -103,7 +105,8 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( let elements = &Rc::new(RegionValueElements::new(mir, universal_regions.len())); // Run the MIR type-checker. - let liveness = &LivenessResults::compute(mir); + let liveness_map = NllLivenessMap::compute(&mir); + let liveness = LivenessResults::compute(mir, &liveness_map); let constraint_sets = type_check::type_check( infcx, param_env, @@ -193,7 +196,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( // write unit-tests, as well as helping with debugging. dump_mir_results( infcx, - liveness, + &liveness, MirSource::item(def_id), &mir, ®ioncx, @@ -209,7 +212,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( fn dump_mir_results<'a, 'gcx, 'tcx>( infcx: &InferCtxt<'a, 'gcx, 'tcx>, - liveness: &LivenessResults, + liveness: &LivenessResults<LocalWithRegion>, source: MirSource, mir: &Mir<'tcx>, regioncx: &RegionInferenceContext, @@ -219,6 +222,8 @@ fn dump_mir_results<'a, 'gcx, 'tcx>( return; } + let map = &NllLivenessMap::compute(mir); + let regular_liveness_per_location: FxHashMap<_, _> = mir .basic_blocks() .indices() @@ -226,7 +231,7 @@ fn dump_mir_results<'a, 'gcx, 'tcx>( let mut results = vec![]; liveness .regular - .simulate_block(&mir, bb, |location, local_set| { + .simulate_block(&mir, bb, map, |location, local_set| { results.push((location, local_set.clone())); }); results @@ -240,7 +245,7 @@ fn dump_mir_results<'a, 'gcx, 'tcx>( let mut results = vec![]; liveness .drop - .simulate_block(&mir, bb, |location, local_set| { + .simulate_block(&mir, bb, map, |location, local_set| { results.push((location, local_set.clone())); }); results @@ -405,7 +410,10 @@ impl ToRegionVid for RegionVid { } } -fn live_variable_set(regular: &LocalSet, drops: &LocalSet) -> String { +fn live_variable_set( + regular: &LiveVarSet<LocalWithRegion>, + drops: &LiveVarSet<LocalWithRegion> +) -> String { // sort and deduplicate: let all_locals: BTreeSet<_> = regular.iter().chain(drops.iter()).collect(); diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs index cd468eabd5f..2b9307db59a 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs @@ -8,12 +8,12 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +use borrow_check::nll::{NllLivenessMap, LocalWithRegion}; use borrow_check::nll::type_check::AtLocation; use dataflow::move_paths::{HasMoveData, MoveData}; use dataflow::MaybeInitializedPlaces; use dataflow::{FlowAtLocation, FlowsAtLocation}; use rustc::infer::canonical::QueryRegionConstraint; -use rustc::mir::Local; use rustc::mir::{BasicBlock, Location, Mir}; use rustc::traits::query::dropck_outlives::DropckOutlivesResult; use rustc::traits::query::type_op::outlives::DropckOutlives; @@ -21,7 +21,7 @@ use rustc::traits::query::type_op::TypeOp; use rustc::ty::{Ty, TypeFoldable}; use rustc_data_structures::fx::FxHashMap; use std::rc::Rc; -use util::liveness::LivenessResults; +use util::liveness::{LivenessResults, LiveVariableMap }; use super::TypeChecker; @@ -36,7 +36,7 @@ use super::TypeChecker; pub(super) fn generate<'gcx, 'tcx>( cx: &mut TypeChecker<'_, 'gcx, 'tcx>, mir: &Mir<'tcx>, - liveness: &LivenessResults, + liveness: &LivenessResults<LocalWithRegion>, flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>, move_data: &MoveData<'tcx>, ) { @@ -47,6 +47,7 @@ pub(super) fn generate<'gcx, 'tcx>( flow_inits, move_data, drop_data: FxHashMap(), + map: &NllLivenessMap::compute(mir), }; for bb in mir.basic_blocks().indices() { @@ -63,10 +64,11 @@ where { cx: &'gen mut TypeChecker<'typeck, 'gcx, 'tcx>, mir: &'gen Mir<'tcx>, - liveness: &'gen LivenessResults, + liveness: &'gen LivenessResults<LocalWithRegion>, flow_inits: &'gen mut FlowAtLocation<MaybeInitializedPlaces<'flow, 'gcx, 'tcx>>, move_data: &'gen MoveData<'tcx>, drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>, + map: &'gen NllLivenessMap, } struct DropData<'tcx> { @@ -84,17 +86,18 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo self.liveness .regular - .simulate_block(self.mir, bb, |location, live_locals| { + .simulate_block(self.mir, bb, self.map, |location, live_locals| { for live_local in live_locals.iter() { - let live_local_ty = self.mir.local_decls[live_local].ty; + let local = self.map.from_live_var(live_local); + let live_local_ty = self.mir.local_decls[local].ty; Self::push_type_live_constraint(&mut self.cx, live_local_ty, location); } }); - let mut all_live_locals: Vec<(Location, Vec<Local>)> = vec![]; + let mut all_live_locals: Vec<(Location, Vec<LocalWithRegion>)> = vec![]; self.liveness .drop - .simulate_block(self.mir, bb, |location, live_locals| { + .simulate_block(self.mir, bb, self.map, |location, live_locals| { all_live_locals.push((location, live_locals.iter().collect())); }); debug!( @@ -121,7 +124,8 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo }); } - let mpi = self.move_data.rev_lookup.find_local(live_local); + let local = self.map.from_live_var(live_local); + let mpi = self.move_data.rev_lookup.find_local(local); if let Some(initialized_child) = self.flow_inits.has_any_child_of(mpi) { debug!( "add_liveness_constraints: mpi={:?} has initialized child {:?}", @@ -129,7 +133,8 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo self.move_data.move_paths[initialized_child] ); - let live_local_ty = self.mir.local_decls[live_local].ty; + let local = self.map.from_live_var(live_local); + let live_local_ty = self.mir.local_decls[local].ty; self.add_drop_live_constraint(live_local, live_local_ty, location); } } @@ -190,7 +195,7 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo /// particular this takes `#[may_dangle]` into account. fn add_drop_live_constraint( &mut self, - dropped_local: Local, + dropped_local: LocalWithRegion, dropped_ty: Ty<'tcx>, location: Location, ) { diff --git a/src/librustc_mir/borrow_check/nll/type_check/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/mod.rs index e188c9d7559..e23f9b20a10 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs @@ -19,6 +19,7 @@ use borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest}; use borrow_check::nll::region_infer::values::{RegionValues, RegionValueElements}; use borrow_check::nll::universal_regions::UniversalRegions; use borrow_check::nll::ToRegionVid; +use borrow_check::nll::LocalWithRegion; use dataflow::move_paths::MoveData; use dataflow::FlowAtLocation; use dataflow::MaybeInitializedPlaces; @@ -109,7 +110,7 @@ pub(crate) fn type_check<'gcx, 'tcx>( universal_regions: &UniversalRegions<'tcx>, location_table: &LocationTable, borrow_set: &BorrowSet<'tcx>, - liveness: &LivenessResults, + liveness: &LivenessResults<LocalWithRegion>, all_facts: &mut Option<AllFacts>, flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>, move_data: &MoveData<'tcx>, diff --git a/src/librustc_mir/transform/generator.rs b/src/librustc_mir/transform/generator.rs index a6017fafcc8..a43f17e40df 100644 --- a/src/librustc_mir/transform/generator.rs +++ b/src/librustc_mir/transform/generator.rs @@ -66,7 +66,7 @@ use rustc::mir::visit::{PlaceContext, Visitor, MutVisitor}; use rustc::ty::{self, TyCtxt, AdtDef, Ty}; use rustc::ty::subst::Substs; use util::dump_mir; -use util::liveness::{self, LivenessMode}; +use util::liveness::{self, IdentityMap, LivenessMode}; use rustc_data_structures::indexed_vec::Idx; use rustc_data_structures::indexed_set::IdxSetBuf; use std::collections::HashMap; @@ -130,7 +130,7 @@ struct SuspensionPoint { state: u32, resume: BasicBlock, drop: Option<BasicBlock>, - storage_liveness: liveness::LocalSet, + storage_liveness: liveness::LiveVarSet<Local>, } struct TransformVisitor<'a, 'tcx: 'a> { @@ -145,7 +145,7 @@ struct TransformVisitor<'a, 'tcx: 'a> { remap: HashMap<Local, (Ty<'tcx>, usize)>, // A map from a suspension point in a block to the locals which have live storage at that point - storage_liveness: HashMap<BasicBlock, liveness::LocalSet>, + storage_liveness: HashMap<BasicBlock, liveness::LiveVarSet<Local>>, // A list of suspension points, generated during the transform suspension_points: Vec<SuspensionPoint>, @@ -317,7 +317,7 @@ fn replace_result_variable<'tcx>(ret_ty: Ty<'tcx>, new_ret_local } -struct StorageIgnored(liveness::LocalSet); +struct StorageIgnored(liveness::LiveVarSet<Local>); impl<'tcx> Visitor<'tcx> for StorageIgnored { fn visit_statement(&mut self, @@ -332,7 +332,7 @@ impl<'tcx> Visitor<'tcx> for StorageIgnored { } } -struct BorrowedLocals(liveness::LocalSet); +struct BorrowedLocals(liveness::LiveVarSet<Local>); fn mark_as_borrowed<'tcx>(place: &Place<'tcx>, locals: &mut BorrowedLocals) { match *place { @@ -361,12 +361,12 @@ impl<'tcx> Visitor<'tcx> for BorrowedLocals { } } -fn locals_live_across_suspend_points<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, +fn locals_live_across_suspend_points<'a, 'tcx,>(tcx: TyCtxt<'a, 'tcx, 'tcx>, mir: &Mir<'tcx>, source: MirSource, movable: bool) -> - (liveness::LocalSet, - HashMap<BasicBlock, liveness::LocalSet>) { + (liveness::LiveVarSet<Local>, + HashMap<BasicBlock, liveness::LiveVarSet<Local>>) { let dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len()); let node_id = tcx.hir.as_local_node_id(source.def_id).unwrap(); @@ -396,12 +396,23 @@ fn locals_live_across_suspend_points<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, }; // Calculate the liveness of MIR locals ignoring borrows. - let mut set = liveness::LocalSet::new_empty(mir.local_decls.len()); - let mut liveness = liveness::liveness_of_locals(mir, LivenessMode { - include_regular_use: true, - include_drops: true, - }); - liveness::dump_mir(tcx, "generator_liveness", source, mir, &liveness); + let mut set = liveness::LiveVarSet::new_empty(mir.local_decls.len()); + let mut liveness = liveness::liveness_of_locals( + mir, + LivenessMode { + include_regular_use: true, + include_drops: true, + }, + &IdentityMap::new(mir), + ); + liveness::dump_mir( + tcx, + "generator_liveness", + source, + mir, + &IdentityMap::new(mir), + &liveness, + ); let mut storage_liveness_map = HashMap::new(); @@ -468,7 +479,7 @@ fn compute_layout<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, mir: &mut Mir<'tcx>) -> (HashMap<Local, (Ty<'tcx>, usize)>, GeneratorLayout<'tcx>, - HashMap<BasicBlock, liveness::LocalSet>) + HashMap<BasicBlock, liveness::LiveVarSet<Local>>) { // 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 e1d5e302c3a..6c5b38a806e 100644 --- a/src/librustc_mir/util/liveness.rs +++ b/src/librustc_mir/util/liveness.rs @@ -33,32 +33,75 @@ //! generator yield points, all pre-existing references are invalidated, so this //! doesn't matter). -use rustc::mir::*; +use rustc::mir::visit::MirVisitable; use rustc::mir::visit::{PlaceContext, Visitor}; -use rustc_data_structures::indexed_vec::{Idx, IndexVec}; +use rustc::mir::Local; +use rustc::mir::*; +use rustc::ty::{item_path, TyCtxt}; use rustc_data_structures::indexed_set::IdxSetBuf; +use rustc_data_structures::indexed_vec::{Idx, IndexVec}; use rustc_data_structures::work_queue::WorkQueue; -use util::pretty::{dump_enabled, write_basic_block, write_mir_intro}; -use rustc::ty::item_path; -use rustc::mir::visit::MirVisitable; -use std::path::{Path, PathBuf}; use std::fs; -use rustc::ty::TyCtxt; use std::io::{self, Write}; +use std::path::{Path, PathBuf}; use transform::MirSource; +use util::pretty::{dump_enabled, write_basic_block, write_mir_intro}; -pub type LocalSet = IdxSetBuf<Local>; +pub type LiveVarSet<V> = IdxSetBuf<V>; /// This gives the result of the liveness analysis at the boundary of /// basic blocks. You can use `simulate_block` to obtain the /// intra-block results. -pub struct LivenessResult { +/// +/// The `V` type defines the set of variables that we computed +/// 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> { /// Liveness mode in use when these results were computed. pub mode: LivenessMode, /// Live variables on exit to each basic block. This is equal to /// the union of the `ins` for each successor. - pub outs: IndexVec<BasicBlock, LocalSet>, + 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() + } } #[derive(Copy, Clone, Debug)] @@ -80,18 +123,21 @@ pub struct LivenessMode { } /// A combination of liveness results, used in NLL. -pub struct LivenessResults { +pub struct LivenessResults<V: Idx> { /// Liveness results where a regular use makes a variable X live, /// but not a drop. - pub regular: LivenessResult, + pub regular: LivenessResult<V>, /// Liveness results where a drop makes a variable X live, /// but not a regular use. - pub drop: LivenessResult, + pub drop: LivenessResult<V>, } -impl LivenessResults { - pub fn compute<'tcx>(mir: &Mir<'tcx>) -> LivenessResults { +impl<V: Idx> LivenessResults<V> { + pub fn compute<'tcx>( + mir: &Mir<'tcx>, + map: &impl LiveVariableMap<LiveVar = V>, + ) -> LivenessResults<V> { LivenessResults { regular: liveness_of_locals( &mir, @@ -99,6 +145,7 @@ impl LivenessResults { include_regular_use: true, include_drops: false, }, + map, ), drop: liveness_of_locals( @@ -107,6 +154,7 @@ impl LivenessResults { include_regular_use: false, include_drops: true, }, + map, ), } } @@ -115,19 +163,26 @@ impl LivenessResults { /// Compute 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>(mir: &Mir<'tcx>, mode: LivenessMode) -> LivenessResult { - let locals = mir.local_decls.len(); - let def_use: IndexVec<_, _> = mir.basic_blocks() +pub fn liveness_of_locals<'tcx, V: Idx>( + mir: &Mir<'tcx>, + mode: LivenessMode, + map: &impl LiveVariableMap<LiveVar = V>, +) -> LivenessResult<V> { + let num_live_vars = map.num_variables(); + + let def_use: IndexVec<_, DefsUses<V>> = mir + .basic_blocks() .iter() - .map(|b| block(mode, b, locals)) + .map(|b| block(mode, map, b, num_live_vars)) .collect(); - let mut outs: IndexVec<_, _> = mir.basic_blocks() + let mut outs: IndexVec<_, LiveVarSet<V>> = mir + .basic_blocks() .indices() - .map(|_| LocalSet::new_empty(locals)) + .map(|_| LiveVarSet::new_empty(num_live_vars)) .collect(); - let mut bits = LocalSet::new_empty(locals); + let mut bits = LiveVarSet::new_empty(num_live_vars); // queue of things that need to be re-processed, and a set containing // the things currently in the queue @@ -156,14 +211,19 @@ pub fn liveness_of_locals<'tcx>(mir: &Mir<'tcx>, mode: LivenessMode) -> Liveness LivenessResult { mode, outs } } -impl LivenessResult { +impl<V: Idx> LivenessResult<V> { /// Walks backwards through the statements/terminator in the given /// basic block `block`. At each point within `block`, invokes /// the callback `op` with the current location and the set of /// variables that are live on entry to that location. - pub fn simulate_block<'tcx, OP>(&self, mir: &Mir<'tcx>, block: BasicBlock, mut callback: OP) - where - OP: FnMut(Location, &LocalSet), + pub fn simulate_block<'tcx, OP>( + &self, + mir: &Mir<'tcx>, + block: BasicBlock, + map: &impl LiveVariableMap<LiveVar = V>, + mut callback: OP, + ) where + OP: FnMut(Location, &LiveVarSet<V>), { let data = &mir[block]; @@ -179,18 +239,23 @@ impl LivenessResult { block, statement_index, }; - let locals = mir.local_decls.len(); + let num_live_vars = map.num_variables(); let mut visitor = DefsUsesVisitor { mode: self.mode, + map, defs_uses: DefsUses { - defs: LocalSet::new_empty(locals), - uses: LocalSet::new_empty(locals), + defs: LiveVarSet::new_empty(num_live_vars), + uses: LiveVarSet::new_empty(num_live_vars), }, }; // Visit the various parts of the basic block in reverse. If we go // forward, the logic in `add_def` and `add_use` would be wrong. - visitor.update_bits_and_do_callback(terminator_location, &data.terminator, &mut bits, - &mut callback); + visitor.update_bits_and_do_callback( + terminator_location, + &data.terminator, + &mut bits, + &mut callback, + ); // Compute liveness before each statement (in rev order) and invoke callback. for statement in data.statements.iter().rev() { @@ -200,8 +265,12 @@ impl LivenessResult { statement_index, }; visitor.defs_uses.clear(); - visitor.update_bits_and_do_callback(statement_location, statement, &mut bits, - &mut callback); + visitor.update_bits_and_do_callback( + statement_location, + statement, + &mut bits, + &mut callback, + ); } } } @@ -225,11 +294,9 @@ pub fn categorize<'tcx>(context: PlaceContext<'tcx>, mode: LivenessMode) -> Opti // We let Call define the result in both the success and // unwind cases. This is not really correct, however it // does not seem to be observable due to the way that we - // generate MIR. See the test case - // `mir-opt/nll/liveness-call-subtlety.rs`. To do things - // properly, we would apply the def in call only to the - // input from the success path and not the unwind - // path. -nmatsakis + // generate MIR. To do things properly, we would apply + // the def in call only to the input from the success + // path and not the unwind path. -nmatsakis PlaceContext::Call | // Storage live and storage dead aren't proper defines, but we can ignore @@ -281,28 +348,33 @@ pub fn categorize<'tcx>(context: PlaceContext<'tcx>, mode: LivenessMode) -> Opti } } -struct DefsUsesVisitor { +struct DefsUsesVisitor<'lv, V, M> +where + V: Idx, + M: LiveVariableMap<LiveVar = V> + 'lv, +{ mode: LivenessMode, - defs_uses: DefsUses, + map: &'lv M, + defs_uses: DefsUses<V>, } #[derive(Eq, PartialEq, Clone)] -struct DefsUses { - defs: LocalSet, - uses: LocalSet, +struct DefsUses<V: Idx> { + defs: LiveVarSet<V>, + uses: LiveVarSet<V>, } -impl DefsUses { +impl<V: Idx> DefsUses<V> { fn clear(&mut self) { self.uses.clear(); self.defs.clear(); } - fn apply(&self, bits: &mut LocalSet) -> bool { + fn apply(&self, bits: &mut LiveVarSet<V>) -> bool { bits.subtract(&self.defs) | bits.union(&self.uses) } - fn add_def(&mut self, index: Local) { + fn add_def(&mut self, index: V) { // If it was used already in the block, remove that use // now that we found a definition. // @@ -316,7 +388,7 @@ impl DefsUses { self.defs.add(&index); } - fn add_use(&mut self, index: Local) { + fn add_use(&mut self, index: V) { // Inverse of above. // // Example: @@ -332,15 +404,22 @@ impl DefsUses { } } -impl DefsUsesVisitor { +impl<'lv, V, M> DefsUsesVisitor<'lv, V, M> +where + V: Idx, + M: LiveVariableMap<LiveVar = V>, +{ /// Update `bits` with the effects of `value` and call `callback`. We /// should always visit in reverse order. This method assumes that we have /// not visited anything before; if you have, clear `bits` first. - fn update_bits_and_do_callback<'tcx, OP>(&mut self, location: Location, - value: &impl MirVisitable<'tcx>, bits: &mut LocalSet, - callback: &mut OP) - where - OP: FnMut(Location, &LocalSet), + fn update_bits_and_do_callback<'tcx, OP>( + &mut self, + location: Location, + value: &impl MirVisitable<'tcx>, + bits: &mut LiveVarSet<V>, + callback: &mut OP, + ) where + OP: FnMut(Location, &LiveVarSet<V>), { value.apply(location, self); self.defs_uses.apply(bits); @@ -348,28 +427,34 @@ impl DefsUsesVisitor { } } -impl<'tcx> Visitor<'tcx> for DefsUsesVisitor { +impl<'tcx, 'lv, V, M> Visitor<'tcx> for DefsUsesVisitor<'lv, V, M> +where + V: Idx, + M: LiveVariableMap<LiveVar = V>, +{ fn visit_local(&mut self, &local: &Local, context: PlaceContext<'tcx>, _: Location) { - match categorize(context, self.mode) { - Some(DefUse::Def) => { - self.defs_uses.add_def(local); + if let Some(v_index) = self.map.from_local(local) { + match categorize(context, self.mode) { + Some(DefUse::Def) => self.defs_uses.add_def(v_index), + Some(DefUse::Use) => self.defs_uses.add_use(v_index), + None => (), } - - Some(DefUse::Use) => { - self.defs_uses.add_use(local); - } - - None => {} } } } -fn block<'tcx>(mode: LivenessMode, b: &BasicBlockData<'tcx>, locals: usize) -> DefsUses { +fn block<'tcx, V: Idx>( + mode: LivenessMode, + map: &impl LiveVariableMap<LiveVar = V>, + b: &BasicBlockData<'tcx>, + locals: usize, +) -> DefsUses<V> { let mut visitor = DefsUsesVisitor { mode, + map, defs_uses: DefsUses { - defs: LocalSet::new_empty(locals), - uses: LocalSet::new_empty(locals), + defs: LiveVarSet::new_empty(locals), + uses: LiveVarSet::new_empty(locals), }, }; @@ -388,12 +473,13 @@ fn block<'tcx>(mode: LivenessMode, b: &BasicBlockData<'tcx>, locals: usize) -> D visitor.defs_uses } -pub fn dump_mir<'a, 'tcx>( +pub fn dump_mir<'a, 'tcx, V: Idx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, pass_name: &str, source: MirSource, mir: &Mir<'tcx>, - result: &LivenessResult, + map: &impl LiveVariableMap<LiveVar = V>, + result: &LivenessResult<V>, ) { if !dump_enabled(tcx, pass_name, source) { return; @@ -402,16 +488,17 @@ pub fn dump_mir<'a, 'tcx>( // see notes on #41697 below tcx.item_path_str(source.def_id) }); - dump_matched_mir_node(tcx, pass_name, &node_path, source, mir, result); + dump_matched_mir_node(tcx, pass_name, &node_path, source, mir, map, result); } -fn dump_matched_mir_node<'a, 'tcx>( +fn dump_matched_mir_node<'a, 'tcx, V: Idx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, pass_name: &str, node_path: &str, source: MirSource, mir: &Mir<'tcx>, - result: &LivenessResult, + map: &dyn LiveVariableMap<LiveVar = V>, + result: &LivenessResult<V>, ) { let mut file_path = PathBuf::new(); file_path.push(Path::new(&tcx.sess.opts.debugging_opts.dump_mir_dir)); @@ -423,25 +510,25 @@ fn dump_matched_mir_node<'a, 'tcx>( writeln!(file, "// source = {:?}", source)?; writeln!(file, "// pass_name = {}", pass_name)?; writeln!(file, "")?; - write_mir_fn(tcx, source, mir, &mut file, result)?; + write_mir_fn(tcx, source, mir, map, &mut file, result)?; Ok(()) }); } -pub fn write_mir_fn<'a, 'tcx>( +pub fn write_mir_fn<'a, 'tcx, V: Idx>( tcx: TyCtxt<'a, 'tcx, 'tcx>, src: MirSource, mir: &Mir<'tcx>, + map: &dyn LiveVariableMap<LiveVar = V>, w: &mut dyn Write, - result: &LivenessResult, + result: &LivenessResult<V>, ) -> 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, LocalSet>| { - let live: Vec<String> = mir.local_decls - .indices() - .filter(|i| result[block].contains(i)) - .map(|i| format!("{:?}", i)) + let print = |w: &mut dyn Write, prefix, result: &IndexVec<BasicBlock, LiveVarSet<V>>| { + let live: Vec<String> = result[block].iter() + .map(|v| map.from_live_var(v)) + .map(|local| format!("{:?}", local)) .collect(); writeln!(w, "{} {{{}}}", prefix, live.join(", ")) }; diff --git a/src/test/mir-opt/nll/liveness-call-subtlety.rs b/src/test/mir-opt/nll/liveness-call-subtlety.rs deleted file mode 100644 index 5fdea4208df..00000000000 --- a/src/test/mir-opt/nll/liveness-call-subtlety.rs +++ /dev/null @@ -1,45 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -// compile-flags:-Zborrowck=mir - -fn can_panic() -> Box<usize> { - Box::new(44) -} - -fn main() { - let mut x = Box::new(22); - x = can_panic(); -} - -// Check that: -// - `_1` is the variable corresponding to `x` -// and -// - `_1` is live when `can_panic` is called (because it may be dropped) -// -// END RUST SOURCE -// START rustc.main.nll.0.mir -// bb0: { -// | Live variables on entry to bb0[0]: [] -// StorageLive(_1); -// | Live variables on entry to bb0[1]: [] -// _1 = const <std::boxed::Box<T>>::new(const 22usize) -> [return: bb2, unwind: bb1]; -// | Live variables on exit from bb0: [_1 (drop)] -// } -// END rustc.main.nll.0.mir -// START rustc.main.nll.0.mir -// bb2: { -// | Live variables on entry to bb2[0]: [_1 (drop)] -// StorageLive(_2); -// | Live variables on entry to bb2[1]: [_1 (drop)] -// _2 = const can_panic() -> [return: bb3, unwind: bb4]; -// | Live variables on exit from bb2: [_1 (drop), _2] -// } -// END rustc.main.nll.0.mir diff --git a/src/test/mir-opt/nll/liveness-drop-intra-block.rs b/src/test/mir-opt/nll/liveness-drop-intra-block.rs deleted file mode 100644 index 001499b657d..00000000000 --- a/src/test/mir-opt/nll/liveness-drop-intra-block.rs +++ /dev/null @@ -1,41 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -// compile-flags:-Zborrowck=mir - -#![allow(warnings)] - -fn use_x(_: usize) -> bool { true } - -fn main() { - let mut x = 22; - loop { - // Key point: `x` not live on entry to this basic block. - x = 55; - if use_x(x) { break; } - } -} - -// END RUST SOURCE -// START rustc.main.nll.0.mir -// bb3: { -// | Live variables on entry to bb3[0]: [] -// _1 = const 55usize; -// | Live variables on entry to bb3[1]: [_1] -// StorageLive(_3); -// | Live variables on entry to bb3[2]: [_1] -// StorageLive(_4); -// | Live variables on entry to bb3[3]: [_1] -// _4 = _1; -// | Live variables on entry to bb3[4]: [_4] -// _3 = const use_x(move _4) -> [return: bb4, unwind: bb1]; -// | Live variables on exit from bb3: [_3] -// } -// END rustc.main.nll.0.mir diff --git a/src/test/mir-opt/nll/liveness-interblock.rs b/src/test/mir-opt/nll/liveness-interblock.rs deleted file mode 100644 index fbe20d76ea7..00000000000 --- a/src/test/mir-opt/nll/liveness-interblock.rs +++ /dev/null @@ -1,48 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -// compile-flags:-Zborrowck=mir - -fn cond() -> bool { false } - -fn make_live(_: usize) { } - -fn make_dead() { } - -fn main() { - let x = 5; - - if cond() { - make_live(x); - } else { - // x should be dead on entry to this block - make_dead(); - } -} - -// END RUST SOURCE -// START rustc.main.nll.0.mir -// bb3: { -// | Live variables on entry to bb3[0]: [_1] -// StorageLive(_4); -// | Live variables on entry to bb3[1]: [_1] -// _4 = _1; -// | Live variables on entry to bb3[2]: [_4] -// _3 = const make_live(move _4) -> [return: bb5, unwind: bb1]; -// | Live variables on exit from bb3: [] -// } -// END rustc.main.nll.0.mir -// START rustc.main.nll.0.mir -// bb4: { -// | Live variables on entry to bb4[0]: [] -// _5 = const make_dead() -> [return: bb6, unwind: bb1]; -// | Live variables on exit from bb4: [] -// } -// END rustc.main.nll.0.mir diff --git a/src/test/mir-opt/nll/region-liveness-basic.rs b/src/test/mir-opt/nll/region-liveness-basic.rs deleted file mode 100644 index 187d9e6ca89..00000000000 --- a/src/test/mir-opt/nll/region-liveness-basic.rs +++ /dev/null @@ -1,58 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -// Basic test for liveness constraints: the region (`R1`) that appears -// in the type of `p` includes the points after `&v[0]` up to (but not -// including) the call to `use_x`. The `else` branch is not included. - -// compile-flags:-Zborrowck=mir -Zverbose -// ^^^^^^^^^ force compiler to dump more region information - -#![allow(warnings)] - -fn use_x(_: usize) -> bool { true } - -fn main() { - let mut v = [1, 2, 3]; - let p = &v[0]; - if true { - use_x(*p); - } else { - use_x(22); - } -} - -// END RUST SOURCE -// START rustc.main.nll.0.mir -// | '_#2r | {bb2[0..=1], bb3[0..=1]} -// | '_#3r | {bb2[1], bb3[0..=1]} -// ... -// let _2: &'_#3r usize; -// END rustc.main.nll.0.mir -// START rustc.main.nll.0.mir -// bb2: { -// | Live variables on entry to bb2[0]: [_1, _3] -// _2 = &'_#2r _1[_3]; -// | Live variables on entry to bb2[1]: [_2] -// switchInt(const true) -> [false: bb4, otherwise: bb3]; -// | Live variables on exit from bb2: [_2] -// } -// END rustc.main.nll.0.mir -// START rustc.main.nll.0.mir -// bb3: { -// | Live variables on entry to bb3[0]: [_2] -// StorageLive(_7); -// | Live variables on entry to bb3[1]: [_2] -// _7 = (*_2); -// | Live variables on entry to bb3[2]: [_7] -// _6 = const use_x(move _7) -> [return: bb5, unwind: bb1]; -// | Live variables on exit from bb3: [] -// } -// END rustc.main.nll.0.mir diff --git a/src/test/mir-opt/nll/region-liveness-two-disjoint-uses.rs b/src/test/mir-opt/nll/region-liveness-two-disjoint-uses.rs deleted file mode 100644 index 62064fa94f2..00000000000 --- a/src/test/mir-opt/nll/region-liveness-two-disjoint-uses.rs +++ /dev/null @@ -1,52 +0,0 @@ -// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -// Test for the subregion constraints. In this case, the region R3 on -// `p` includes two disjoint regions of the control-flow graph. The -// borrows in `&v[0]` and `&v[1]` each (in theory) have to outlive R3, -// but only at a particular point, and hence they wind up including -// distinct regions. -// -// FIXME(#43234) -- Well, this used to be true, but we modified NLL -// for the time being to not take location into account. - -// compile-flags:-Zborrowck=mir -Zverbose -// ^^^^^^^^^ force compiler to dump more region information - -#![allow(warnings)] - -fn use_x(_: usize) -> bool { true } - -fn main() { - let mut v = [1, 2, 3]; - let mut p = &v[0]; - if true { - use_x(*p); - } else { - use_x(22); - } - - p = &v[1]; - use_x(*p); -} - -// END RUST SOURCE -// START rustc.main.nll.0.mir -// | '_#2r | {bb2[0..=1], bb3[0..=1], bb8[2..=4]} -// ... -// | '_#4r | {bb2[1], bb3[0..=1], bb8[1..=4]} -// | '_#5r | {bb2[1], bb3[0..=1], bb8[2..=4]} -// ... -// let mut _2: &'_#5r usize; -// ... -// _2 = &'_#2r _1[_3]; -// ... -// _2 = &'_#4r (*_10); -// END rustc.main.nll.0.mir |