diff options
| author | bors <bors@rust-lang.org> | 2018-08-28 10:58:10 +0000 |
|---|---|---|
| committer | bors <bors@rust-lang.org> | 2018-08-28 10:58:10 +0000 |
| commit | 83ddc33347cade429fdb47509818e775a67c1af6 (patch) | |
| tree | 79b4b9e46b5127dbaae17128ffedc1b17c5bd414 | |
| parent | 59e52b1b969545e6b7b8595913dc2e1a741d495d (diff) | |
| parent | 8d231ec872aa7ede20faf70e988ebfbded351b53 (diff) | |
| download | rust-83ddc33347cade429fdb47509818e775a67c1af6.tar.gz rust-83ddc33347cade429fdb47509818e775a67c1af6.zip | |
Auto merge of #53314 - nikomatsakis:nll-invert-liveness, r=pnkfelix
NLL: experiment with inverting liveness I got inspired to see what would happen here. Fixes #52460 r? @pnkfelix
21 files changed, 1001 insertions, 608 deletions
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs index 86e521727c5..0840f333c87 100644 --- a/src/librustc/mir/mod.rs +++ b/src/librustc/mir/mod.rs @@ -194,12 +194,12 @@ impl<'tcx> Mir<'tcx> { } #[inline] - pub fn predecessors(&self) -> ReadGuard<IndexVec<BasicBlock, Vec<BasicBlock>>> { + pub fn predecessors(&self) -> ReadGuard<'_, IndexVec<BasicBlock, Vec<BasicBlock>>> { self.cache.predecessors(self) } #[inline] - pub fn predecessors_for(&self, bb: BasicBlock) -> ReadGuard<Vec<BasicBlock>> { + pub fn predecessors_for(&self, bb: BasicBlock) -> ReadGuard<'_, Vec<BasicBlock>> { ReadGuard::map(self.predecessors(), |p| &p[bb]) } @@ -328,6 +328,14 @@ impl<'tcx> Mir<'tcx> { pub fn return_ty(&self) -> Ty<'tcx> { self.local_decls[RETURN_PLACE].ty } + + /// Get the location of the terminator for the given block + pub fn terminator_loc(&self, bb: BasicBlock) -> Location { + Location { + block: bb, + statement_index: self[bb].statements.len(), + } + } } #[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable)] diff --git a/src/librustc_data_structures/graph/dominators/mod.rs b/src/librustc_data_structures/graph/dominators/mod.rs index e54147cbe7c..9b7f4cec47b 100644 --- a/src/librustc_data_structures/graph/dominators/mod.rs +++ b/src/librustc_data_structures/graph/dominators/mod.rs @@ -38,13 +38,13 @@ pub fn dominators_given_rpo<G: ControlFlowGraph>( // compute the post order index (rank) for each node let mut post_order_rank: IndexVec<G::Node, usize> = - IndexVec::from_elem_n(usize::default(), graph.num_nodes()); + (0..graph.num_nodes()).map(|_| 0).collect(); for (index, node) in rpo.iter().rev().cloned().enumerate() { post_order_rank[node] = index; } let mut immediate_dominators: IndexVec<G::Node, Option<G::Node>> = - IndexVec::from_elem_n(Option::default(), graph.num_nodes()); + (0..graph.num_nodes()).map(|_| None).collect(); immediate_dominators[start_node] = Some(start_node); let mut changed = true; diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs index 533b7f5e0af..936dec92409 100644 --- a/src/librustc_data_structures/lib.rs +++ b/src/librustc_data_structures/lib.rs @@ -20,6 +20,8 @@ html_favicon_url = "https://www.rust-lang.org/favicon.ico", html_root_url = "https://doc.rust-lang.org/nightly/")] +#![feature(in_band_lifetimes)] +#![feature(impl_header_lifetime_elision)] #![feature(unboxed_closures)] #![feature(fn_traits)] #![feature(unsize)] @@ -86,6 +88,7 @@ pub mod thin_vec; pub mod transitive_relation; pub mod tuple_slice; pub use ena::unify; +pub mod vec_linked_list; pub mod work_queue; pub mod fingerprint; diff --git a/src/librustc_data_structures/vec_linked_list.rs b/src/librustc_data_structures/vec_linked_list.rs new file mode 100644 index 00000000000..390dca6b905 --- /dev/null +++ b/src/librustc_data_structures/vec_linked_list.rs @@ -0,0 +1,83 @@ +// Copyright 2014 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. + +use indexed_vec::{Idx, IndexVec}; + +pub fn iter<Ls>( + first: Option<Ls::LinkIndex>, + links: &'a Ls, +) -> impl Iterator<Item = Ls::LinkIndex> + 'a +where + Ls: Links, +{ + VecLinkedListIterator { + links: links, + current: first, + } +} + +pub struct VecLinkedListIterator<Ls> +where + Ls: Links, +{ + links: Ls, + current: Option<Ls::LinkIndex>, +} + +impl<Ls> Iterator for VecLinkedListIterator<Ls> +where + Ls: Links, +{ + type Item = Ls::LinkIndex; + + fn next(&mut self) -> Option<Ls::LinkIndex> { + if let Some(c) = self.current { + self.current = <Ls as Links>::next(&self.links, c); + Some(c) + } else { + None + } + } +} + +pub trait Links { + type LinkIndex: Copy; + + fn next(links: &Self, index: Self::LinkIndex) -> Option<Self::LinkIndex>; +} + +impl<Ls> Links for &Ls +where + Ls: Links, +{ + type LinkIndex = Ls::LinkIndex; + + fn next(links: &Self, index: Ls::LinkIndex) -> Option<Ls::LinkIndex> { + <Ls as Links>::next(links, index) + } +} + +pub trait LinkElem { + type LinkIndex: Copy; + + fn next(elem: &Self) -> Option<Self::LinkIndex>; +} + +impl<L, E> Links for IndexVec<L, E> +where + E: LinkElem<LinkIndex = L>, + L: Idx, +{ + type LinkIndex = L; + + fn next(links: &Self, index: L) -> Option<L> { + <E as LinkElem>::next(&links[index]) + } +} diff --git a/src/librustc_mir/borrow_check/flows.rs b/src/librustc_mir/borrow_check/flows.rs index 90dc96cbd3c..192fa2b9eea 100644 --- a/src/librustc_mir/borrow_check/flows.rs +++ b/src/librustc_mir/borrow_check/flows.rs @@ -89,6 +89,10 @@ impl<'b, 'gcx, 'tcx> FlowsAtLocation for Flows<'b, 'gcx, 'tcx> { each_flow!(self, reset_to_entry_of(bb)); } + fn reset_to_exit_of(&mut self, bb: BasicBlock) { + each_flow!(self, reset_to_exit_of(bb)); + } + fn reconstruct_statement_effect(&mut self, location: Location) { each_flow!(self, reconstruct_statement_effect(location)); } diff --git a/src/librustc_mir/borrow_check/nll/explain_borrow/find_use.rs b/src/librustc_mir/borrow_check/nll/explain_borrow/find_use.rs index aa88fa11174..a35117f2e35 100644 --- a/src/librustc_mir/borrow_check/nll/explain_borrow/find_use.rs +++ b/src/librustc_mir/borrow_check/nll/explain_borrow/find_use.rs @@ -17,7 +17,7 @@ use rustc::mir::visit::{MirVisitable, PlaceContext, Visitor}; use rustc::mir::{Local, Location, Mir}; use rustc::ty::{RegionVid, TyCtxt}; use rustc_data_structures::fx::FxHashSet; -use util::liveness::{self, DefUse, LivenessMode}; +use util::liveness::{self, DefUse}; crate fn find<'tcx>( mir: &Mir<'tcx>, @@ -32,10 +32,6 @@ crate fn find<'tcx>( tcx, region_vid, start_point, - liveness_mode: LivenessMode { - include_regular_use: true, - include_drops: true, - }, }; uf.find() @@ -47,7 +43,6 @@ struct UseFinder<'cx, 'gcx: 'tcx, 'tcx: 'cx> { tcx: TyCtxt<'cx, 'gcx, 'tcx>, region_vid: RegionVid, start_point: Location, - liveness_mode: LivenessMode, } impl<'cx, 'gcx, 'tcx> UseFinder<'cx, 'gcx, 'tcx> { @@ -108,7 +103,6 @@ impl<'cx, 'gcx, 'tcx> UseFinder<'cx, 'gcx, 'tcx> { mir: self.mir, tcx: self.tcx, region_vid: self.region_vid, - liveness_mode: self.liveness_mode, def_use_result: None, }; @@ -122,7 +116,6 @@ struct DefUseVisitor<'cx, 'gcx: 'tcx, 'tcx: 'cx> { mir: &'cx Mir<'tcx>, tcx: TyCtxt<'cx, 'gcx, 'tcx>, region_vid: RegionVid, - liveness_mode: LivenessMode, def_use_result: Option<DefUseResult>, } @@ -146,23 +139,12 @@ impl<'cx, 'gcx, 'tcx> Visitor<'tcx> for DefUseVisitor<'cx, 'gcx, 'tcx> { }); if found_it { - match liveness::categorize(context, self.liveness_mode) { - Some(DefUse::Def) => { - self.def_use_result = Some(DefUseResult::Def); - } - - Some(DefUse::Use) => { - self.def_use_result = if context.is_drop() { - Some(DefUseResult::UseDrop { local }) - } else { - Some(DefUseResult::UseLive { local }) - }; - } - - None => { - self.def_use_result = None; - } - } + self.def_use_result = match liveness::categorize(context) { + Some(DefUse::Def) => Some(DefUseResult::Def), + Some(DefUse::Use) => Some(DefUseResult::UseLive { local }), + Some(DefUse::Drop) => Some(DefUseResult::UseDrop { local }), + None => None, + }; } } } diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs index 40df78d6bfd..b80f9784d6f 100644 --- a/src/librustc_mir/borrow_check/nll/mod.rs +++ b/src/librustc_mir/borrow_check/nll/mod.rs @@ -12,7 +12,7 @@ use borrow_check::borrow_set::BorrowSet; use borrow_check::location::{LocationIndex, LocationTable}; use borrow_check::nll::facts::AllFactsExt; use borrow_check::nll::type_check::{MirTypeckResults, MirTypeckRegionConstraints}; -use borrow_check::nll::type_check::liveness::liveness_map::{NllLivenessMap, LocalWithRegion}; +use borrow_check::nll::type_check::liveness::liveness_map::NllLivenessMap; use borrow_check::nll::region_infer::values::RegionValueElements; use dataflow::indexes::BorrowIndex; use dataflow::move_paths::MoveData; @@ -22,9 +22,7 @@ use rustc::hir::def_id::DefId; use rustc::infer::InferCtxt; use rustc::mir::{ClosureOutlivesSubject, ClosureRegionRequirements, Mir}; use rustc::ty::{self, RegionKind, RegionVid}; -use rustc::util::nodemap::FxHashMap; use rustc_errors::Diagnostic; -use std::collections::BTreeSet; use std::fmt::Debug; use std::env; use std::io; @@ -32,12 +30,11 @@ use std::path::PathBuf; use std::rc::Rc; use std::str::FromStr; use transform::MirSource; -use util::liveness::{LivenessResults, LiveVarSet}; use self::mir_util::PassWhere; use polonius_engine::{Algorithm, Output}; use util as mir_util; -use util::pretty::{self, ALIGN}; +use util::pretty; mod constraint_generation; pub mod explain_borrow; @@ -111,8 +108,6 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( let MirTypeckResults { constraints, universal_region_relations, - liveness, - liveness_map, } = type_check::type_check( infcx, param_env, @@ -205,8 +200,6 @@ 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_map, MirSource::item(def_id), &mir, ®ioncx, @@ -222,8 +215,6 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( fn dump_mir_results<'a, 'gcx, 'tcx>( infcx: &InferCtxt<'a, 'gcx, 'tcx>, - liveness: &LivenessResults<LocalWithRegion>, - liveness_map: &NllLivenessMap, source: MirSource, mir: &Mir<'tcx>, regioncx: &RegionInferenceContext, @@ -233,34 +224,6 @@ fn dump_mir_results<'a, 'gcx, 'tcx>( return; } - let regular_liveness_per_location: FxHashMap<_, _> = mir - .basic_blocks() - .indices() - .flat_map(|bb| { - let mut results = vec![]; - liveness - .regular - .simulate_block(&mir, bb, liveness_map, |location, local_set| { - results.push((location, local_set.clone())); - }); - results - }) - .collect(); - - let drop_liveness_per_location: FxHashMap<_, _> = mir - .basic_blocks() - .indices() - .flat_map(|bb| { - let mut results = vec![]; - liveness - .drop - .simulate_block(&mir, bb, liveness_map, |location, local_set| { - results.push((location, local_set.clone())); - }); - results - }) - .collect(); - mir_util::dump_mir( infcx.tcx, None, @@ -283,26 +246,10 @@ fn dump_mir_results<'a, 'gcx, 'tcx>( } } - PassWhere::BeforeLocation(location) => { - let s = live_variable_set( - ®ular_liveness_per_location[&location], - &drop_liveness_per_location[&location], - ); - writeln!( - out, - "{:ALIGN$} | Live variables on entry to {:?}: {}", - "", - location, - s, - ALIGN = ALIGN - )?; + PassWhere::BeforeLocation(_) => { } - // After each basic block, dump out the values - // that are live on exit from the basic block. - PassWhere::AfterTerminator(bb) => { - let s = live_variable_set(&liveness.regular.outs[bb], &liveness.drop.outs[bb]); - writeln!(out, " | Live variables on exit from {:?}: {}", bb, s)?; + PassWhere::AfterTerminator(_) => { } PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {} @@ -420,33 +367,3 @@ impl ToRegionVid for RegionVid { self } } - -fn live_variable_set( - regular: &LiveVarSet<LocalWithRegion>, - drops: &LiveVarSet<LocalWithRegion> -) -> String { - // sort and deduplicate: - let all_locals: BTreeSet<_> = regular.iter().chain(drops.iter()).collect(); - - // construct a string with each local, including `(drop)` if it is - // only dropped, versus a regular use. - let mut string = String::new(); - for local in all_locals { - string.push_str(&format!("{:?}", local)); - - if !regular.contains(&local) { - assert!(drops.contains(&local)); - string.push_str(" (drop)"); - } - - string.push_str(", "); - } - - let len = if string.is_empty() { - 0 - } else { - string.len() - 2 - }; - - format!("[{}]", &string[..len]) -} diff --git a/src/librustc_mir/borrow_check/nll/region_infer/values.rs b/src/librustc_mir/borrow_check/nll/region_infer/values.rs index 8db5809e53f..ae5d5790673 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/values.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/values.rs @@ -10,7 +10,7 @@ use rustc::mir::{BasicBlock, Location, Mir}; use rustc::ty::{self, RegionVid}; -use rustc_data_structures::bitvec::SparseBitMatrix; +use rustc_data_structures::bitvec::{BitArray, SparseBitMatrix}; use rustc_data_structures::indexed_vec::Idx; use rustc_data_structures::indexed_vec::IndexVec; use std::fmt::Debug; @@ -20,13 +20,18 @@ use std::rc::Rc; crate struct RegionValueElements { /// For each basic block, how many points are contained within? statements_before_block: IndexVec<BasicBlock, usize>, + + /// Map backward from each point to the basic block that it + /// belongs to. + basic_blocks: IndexVec<PointIndex, BasicBlock>, + num_points: usize, } impl RegionValueElements { crate fn new(mir: &Mir<'_>) -> Self { let mut num_points = 0; - let statements_before_block = mir + let statements_before_block: IndexVec<BasicBlock, usize> = mir .basic_blocks() .iter() .map(|block_data| { @@ -41,14 +46,25 @@ impl RegionValueElements { ); debug!("RegionValueElements: num_points={:#?}", num_points); + let mut basic_blocks = IndexVec::with_capacity(num_points); + for (bb, bb_data) in mir.basic_blocks().iter_enumerated() { + basic_blocks.extend((0 .. bb_data.statements.len() + 1).map(|_| bb)); + } + Self { statements_before_block, + basic_blocks, num_points, } } + /// Total number of point indices + crate fn num_points(&self) -> usize { + self.num_points + } + /// Converts a `Location` into a `PointIndex`. O(1). - fn point_from_location(&self, location: Location) -> PointIndex { + crate fn point_from_location(&self, location: Location) -> PointIndex { let Location { block, statement_index, @@ -57,39 +73,50 @@ impl RegionValueElements { PointIndex::new(start_index + statement_index) } - /// Converts a `PointIndex` back to a location. O(N) where N is - /// the number of blocks; could be faster if we ever cared. - crate fn to_location(&self, i: PointIndex) -> Location { - let point_index = i.index(); - - // Find the basic block. We have a vector with the - // starting index of the statement in each block. Imagine - // we have statement #22, and we have a vector like: - // - // [0, 10, 20] - // - // In that case, this represents point_index 2 of - // basic block BB2. We know this because BB0 accounts for - // 0..10, BB1 accounts for 11..20, and BB2 accounts for - // 20... - // - // To compute this, we could do a binary search, but - // because I am lazy we instead iterate through to find - // the last point where the "first index" (0, 10, or 20) - // was less than the statement index (22). In our case, this will - // be (BB2, 20). - // - // Nit: we could do a binary search here but I'm too lazy. - let (block, &first_index) = self - .statements_before_block - .iter_enumerated() - .filter(|(_, first_index)| **first_index <= point_index) - .last() - .unwrap(); - - Location { - block, - statement_index: point_index - first_index, + /// Converts a `Location` into a `PointIndex`. O(1). + crate fn entry_point(&self, block: BasicBlock) -> PointIndex { + let start_index = self.statements_before_block[block]; + PointIndex::new(start_index) + } + + /// Converts a `PointIndex` back to a location. O(1). + crate fn to_location(&self, index: PointIndex) -> Location { + assert!(index.index() < self.num_points); + let block = self.basic_blocks[index]; + let start_index = self.statements_before_block[block]; + let statement_index = index.index() - start_index; + Location { block, statement_index } + } + + /// Sometimes we get point-indices back from bitsets that may be + /// out of range (because they round up to the nearest 2^N number + /// of bits). Use this function to filter such points out if you + /// like. + crate fn point_in_range(&self, index: PointIndex) -> bool { + index.index() < self.num_points + } + + /// Pushes all predecessors of `index` onto `stack`. + crate fn push_predecessors( + &self, + mir: &Mir<'_>, + index: PointIndex, + stack: &mut Vec<PointIndex>, + ) { + let Location { block, statement_index } = self.to_location(index); + if statement_index == 0 { + // If this is a basic block head, then the predecessors are + // the the terminators of other basic blocks + stack.extend( + mir + .predecessors_for(block) + .iter() + .map(|&pred_bb| mir.terminator_loc(pred_bb)) + .map(|pred_loc| self.point_from_location(pred_loc)), + ); + } else { + // Otherwise, the pred is just the previous statement + stack.push(PointIndex::new(index.index() - 1)); } } } @@ -151,6 +178,13 @@ impl<N: Idx> LivenessValues<N> { self.points.add(row, index) } + /// Adds all the elements in the given bit array into the given + /// region. Returns true if any of them are newly added. + crate fn add_elements(&mut self, row: N, locations: &BitArray<PointIndex>) -> bool { + debug!("LivenessValues::add_elements(row={:?}, locations={:?})", row, locations); + self.points.merge_into(row, locations) + } + /// Adds all the control-flow points to the values for `r`. crate fn add_all_points(&mut self, row: N) { self.points.add_all(row); @@ -169,6 +203,7 @@ impl<N: Idx> LivenessValues<N> { .row(r) .into_iter() .flat_map(|set| set.iter()) + .take_while(|&p| self.elements.point_in_range(p)) .map(|p| self.elements.to_location(p)) .map(RegionElement::Location), ) @@ -277,7 +312,11 @@ impl<N: Idx> RegionValues<N> { self.points .row(r) .into_iter() - .flat_map(move |set| set.iter().map(move |p| self.elements.to_location(p))) + .flat_map(move |set| { + set.iter() + .take_while(move |&p| self.elements.point_in_range(p)) + .map(move |p| self.elements.to_location(p)) + }) } /// Returns just the universal regions that are contained in a given region's value. @@ -366,6 +405,19 @@ impl ToElementIndex for ty::UniverseIndex { } } +crate fn location_set_str( + elements: &RegionValueElements, + points: impl IntoIterator<Item = PointIndex>, +) -> String { + region_value_str( + points + .into_iter() + .take_while(|&p| elements.point_in_range(p)) + .map(|p| elements.to_location(p)) + .map(RegionElement::Location), + ) +} + fn region_value_str(elements: impl IntoIterator<Item = RegionElement>) -> String { let mut result = String::new(); result.push_str("{"); 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 index 89e8c76b22f..15affbbc27a 100644 --- 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 @@ -10,9 +10,9 @@ //! 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 +//! 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 LocalWithRegion and vice versa -- this map can be given to the +//! 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. @@ -23,7 +23,7 @@ use rustc_data_structures::fx::FxHashSet; use rustc_data_structures::indexed_vec::{Idx, IndexVec}; use util::liveness::LiveVariableMap; -/// Map between Local and LocalWithRegion indices: the purpose of this +/// 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 @@ -32,10 +32,10 @@ use util::liveness::LiveVariableMap; crate struct NllLivenessMap { /// For each local variable, contains `Some(i)` if liveness is /// needed for this variable. - pub from_local: IndexVec<Local, Option<LocalWithRegion>>, + pub from_local: IndexVec<Local, Option<LiveVar>>, - /// For each `LocalWithRegion`, maps back to the original `Local` index. - pub to_local: IndexVec<LocalWithRegion, Local>, + /// For each `LiveVar`, maps back to the original `Local` index. + pub to_local: IndexVec<LiveVar, Local>, } impl LiveVariableMap for NllLivenessMap { @@ -43,7 +43,7 @@ impl LiveVariableMap for NllLivenessMap { self.from_local[local] } - type LiveVar = LocalWithRegion; + type LiveVar = LiveVar; fn from_live_var(&self, local: Self::LiveVar) -> Local { self.to_local[local] @@ -93,5 +93,10 @@ impl NllLivenessMap { } } -/// Index given to each local variable whose type contains a region. -newtype_index!(LocalWithRegion); +/// 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!( + 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 new file mode 100644 index 00000000000..73d285c2f2e --- /dev/null +++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/local_use_map.rs @@ -0,0 +1,159 @@ +// 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. + +use borrow_check::nll::region_infer::values::{PointIndex, RegionValueElements}; +use borrow_check::nll::type_check::liveness::liveness_map::{LiveVar, NllLivenessMap}; +use rustc::mir::visit::{PlaceContext, Visitor}; +use rustc::mir::{Local, Location, Mir}; +use rustc_data_structures::indexed_vec::{Idx, IndexVec}; +use rustc_data_structures::vec_linked_list as vll; +use util::liveness::{categorize, DefUse, LiveVariableMap}; + +/// 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, + + /// 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>>, + + /// 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>>, + + /// 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>>, + + appearances: IndexVec<AppearanceIndex, Appearance>, +} + +struct Appearance { + point_index: PointIndex, + next: Option<AppearanceIndex>, +} + +newtype_index!(AppearanceIndex); + +impl vll::LinkElem for Appearance { + type LinkIndex = AppearanceIndex; + + fn next(elem: &Self) -> Option<AppearanceIndex> { + elem.next + } +} + +impl LocalUseMap<'me> { + crate fn build( + liveness_map: &'me NllLivenessMap, + elements: &RegionValueElements, + mir: &Mir<'_>, + ) -> Self { + let nones = IndexVec::from_elem_n(None, liveness_map.num_variables()); + 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(), + }; + + LocalUseMapBuild { + local_use_map: &mut local_use_map, + elements, + }.visit_mir(mir); + + local_use_map + } + + crate fn defs(&self, local: LiveVar) -> 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> + '_ { + 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> + '_ { + 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>, + elements: &'me RegionValueElements, +} + +impl LocalUseMapBuild<'_, '_> { + fn insert_def(&mut self, local: LiveVar, 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: LiveVar, 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: LiveVar, 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<'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) { + 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), + _ => (), + } + } + } +} 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 a9b69cfe761..b3fc73e9b7b 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 @@ -8,26 +8,23 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. +use borrow_check::nll::region_infer::values::RegionValueElements; use borrow_check::nll::constraints::ConstraintSet; -use borrow_check::nll::type_check::AtLocation; -use borrow_check::nll::{LocalWithRegion, NllLivenessMap}; +use borrow_check::nll::NllLivenessMap; use borrow_check::nll::universal_regions::UniversalRegions; -use dataflow::move_paths::{HasMoveData, MoveData}; +use dataflow::move_paths::MoveData; use dataflow::MaybeInitializedPlaces; -use dataflow::{FlowAtLocation, FlowsAtLocation}; -use rustc::infer::canonical::QueryRegionConstraint; -use rustc::mir::{BasicBlock, Location, Mir}; -use rustc::traits::query::dropck_outlives::DropckOutlivesResult; -use rustc::traits::query::type_op::outlives::DropckOutlives; -use rustc::traits::query::type_op::TypeOp; -use rustc::ty::{RegionVid, Ty, TypeFoldable}; -use rustc_data_structures::fx::{FxHashMap, FxHashSet}; +use dataflow::FlowAtLocation; +use rustc::mir::Mir; +use rustc::ty::RegionVid; +use rustc_data_structures::fx::FxHashSet; use std::rc::Rc; -use util::liveness::{LiveVariableMap, LivenessResults}; use super::TypeChecker; crate mod liveness_map; +mod local_use_map; +mod trace; /// Combines liveness analysis with initialization analysis to /// determine which variables are live at which points, both due to @@ -38,40 +35,23 @@ crate mod liveness_map; /// NB. This computation requires normalization; therefore, it must be /// performed before pub(super) fn generate<'gcx, 'tcx>( - cx: &mut TypeChecker<'_, 'gcx, 'tcx>, + typeck: &mut TypeChecker<'_, 'gcx, 'tcx>, mir: &Mir<'tcx>, + elements: &Rc<RegionValueElements>, flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>, move_data: &MoveData<'tcx>, -) -> (LivenessResults<LocalWithRegion>, NllLivenessMap) { +) { + debug!("liveness::generate"); let free_regions = { - let borrowck_context = cx.borrowck_context.as_ref().unwrap(); + let borrowck_context = typeck.borrowck_context.as_ref().unwrap(); regions_that_outlive_free_regions( - cx.infcx.num_region_vars(), + typeck.infcx.num_region_vars(), &borrowck_context.universal_regions, &borrowck_context.constraints.outlives_constraints, ) }; - let liveness_map = NllLivenessMap::compute(cx.tcx(), &free_regions, mir); - let liveness = LivenessResults::compute(mir, &liveness_map); - - // For everything else, it is only live where it is actually used. - if !liveness_map.is_empty() { - let mut generator = TypeLivenessGenerator { - cx, - mir, - liveness: &liveness, - flow_inits, - move_data, - drop_data: FxHashMap(), - map: &liveness_map, - }; - - for bb in mir.basic_blocks().indices() { - generator.add_liveness_constraints(bb); - } - } - - (liveness, liveness_map) + let liveness_map = NllLivenessMap::compute(typeck.tcx(), &free_regions, mir); + trace::trace(typeck, mir, elements, flow_inits, move_data, &liveness_map); } /// Compute all regions that are (currently) known to outlive free @@ -112,198 +92,3 @@ fn regions_that_outlive_free_regions( // Return the final set of things we visited. outlives_free_region } - -struct TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx> -where - 'typeck: 'gen, - 'flow: 'gen, - 'tcx: 'typeck + 'flow, - 'gcx: 'tcx, -{ - cx: &'gen mut TypeChecker<'typeck, 'gcx, 'tcx>, - mir: &'gen Mir<'tcx>, - 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> { - dropck_result: DropckOutlivesResult<'tcx>, - region_constraint_data: Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>, -} - -impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx> { - /// Liveness constraints: - /// - /// > If a variable V is live at point P, then all regions R in the type of V - /// > must include the point P. - fn add_liveness_constraints(&mut self, bb: BasicBlock) { - debug!("add_liveness_constraints(bb={:?})", bb); - - self.liveness - .regular - .simulate_block(self.mir, bb, self.map, |location, live_locals| { - for live_local in live_locals.iter() { - 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<LocalWithRegion>)> = vec![]; - self.liveness - .drop - .simulate_block(self.mir, bb, self.map, |location, live_locals| { - all_live_locals.push((location, live_locals.iter().collect())); - }); - debug!( - "add_liveness_constraints: all_live_locals={:#?}", - all_live_locals - ); - - let terminator_index = self.mir.basic_blocks()[bb].statements.len(); - self.flow_inits.reset_to_entry_of(bb); - while let Some((location, live_locals)) = all_live_locals.pop() { - for live_local in live_locals { - debug!( - "add_liveness_constraints: location={:?} live_local={:?}", - location, live_local - ); - - if log_enabled!(::log::Level::Debug) { - self.flow_inits.each_state_bit(|mpi_init| { - debug!( - "add_liveness_constraints: location={:?} initialized={:?}", - location, - &self.flow_inits.operator().move_data().move_paths[mpi_init] - ); - }); - } - - 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 {:?}", - self.move_data.move_paths[mpi], - self.move_data.move_paths[initialized_child] - ); - - 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); - } - } - - if location.statement_index == terminator_index { - debug!( - "add_liveness_constraints: reconstruct_terminator_effect from {:#?}", - location - ); - self.flow_inits.reconstruct_terminator_effect(location); - } else { - debug!( - "add_liveness_constraints: reconstruct_statement_effect from {:#?}", - location - ); - self.flow_inits.reconstruct_statement_effect(location); - } - self.flow_inits.apply_local_effect(location); - } - } - - /// Some variable with type `live_ty` is "regular live" at - /// `location` -- i.e., it may be used later. This means that all - /// regions appearing in the type `live_ty` must be live at - /// `location`. - fn push_type_live_constraint<T>( - cx: &mut TypeChecker<'_, 'gcx, 'tcx>, - value: T, - location: Location, - ) where - T: TypeFoldable<'tcx>, - { - debug!( - "push_type_live_constraint(live_ty={:?}, location={:?})", - value, location - ); - - cx.tcx().for_each_free_region(&value, |live_region| { - if let Some(ref mut borrowck_context) = cx.borrowck_context { - let region_vid = borrowck_context - .universal_regions - .to_region_vid(live_region); - borrowck_context - .constraints - .liveness_constraints - .add_element(region_vid, location); - - if let Some(all_facts) = borrowck_context.all_facts { - let start_index = borrowck_context.location_table.start_index(location); - all_facts.region_live_at.push((region_vid, start_index)); - - let mid_index = borrowck_context.location_table.mid_index(location); - all_facts.region_live_at.push((region_vid, mid_index)); - } - } - }); - } - - /// 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_constraint( - &mut self, - dropped_local: LocalWithRegion, - dropped_ty: Ty<'tcx>, - location: Location, - ) { - debug!( - "add_drop_live_constraint(dropped_local={:?}, dropped_ty={:?}, location={:?})", - dropped_local, dropped_ty, location - ); - - let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({ - let cx = &mut self.cx; - move || Self::compute_drop_data(cx, dropped_ty) - }); - - if let Some(data) = &drop_data.region_constraint_data { - self.cx.push_region_constraints(location.boring(), data); - } - - drop_data.dropck_result.report_overflows( - self.cx.infcx.tcx, - self.mir.source_info(location).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::push_type_live_constraint(&mut self.cx, kind, location); - } - } - - fn compute_drop_data( - cx: &mut TypeChecker<'_, 'gcx, 'tcx>, - dropped_ty: Ty<'tcx>, - ) -> DropData<'tcx> { - debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,); - - let param_env = cx.param_env; - let (dropck_result, region_constraint_data) = param_env - .and(DropckOutlives::new(dropped_ty)) - .fully_perform(cx.infcx) - .unwrap(); - - DropData { - dropck_result, - region_constraint_data, - } - } -} 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 new file mode 100644 index 00000000000..79589ce9733 --- /dev/null +++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs @@ -0,0 +1,553 @@ +// Copyright 2017 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. + +use borrow_check::nll::region_infer::values::{self, PointIndex, RegionValueElements}; +use borrow_check::nll::type_check::liveness::liveness_map::{LiveVar, NllLivenessMap}; +use borrow_check::nll::type_check::liveness::local_use_map::LocalUseMap; +use borrow_check::nll::type_check::AtLocation; +use borrow_check::nll::type_check::TypeChecker; +use dataflow::move_paths::indexes::MovePathIndex; +use dataflow::move_paths::MoveData; +use dataflow::{FlowAtLocation, FlowsAtLocation, MaybeInitializedPlaces}; +use rustc::infer::canonical::QueryRegionConstraint; +use rustc::mir::{BasicBlock, Local, Location, Mir}; +use rustc::traits::query::dropck_outlives::DropckOutlivesResult; +use rustc::traits::query::type_op::outlives::DropckOutlives; +use rustc::traits::query::type_op::TypeOp; +use rustc::ty::{Ty, TypeFoldable}; +use rustc_data_structures::bitvec::BitArray; +use rustc_data_structures::fx::FxHashMap; +use std::rc::Rc; +use util::liveness::LiveVariableMap; + +/// 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( + typeck: &mut TypeChecker<'_, 'gcx, 'tcx>, + mir: &Mir<'tcx>, + elements: &Rc<RegionValueElements>, + flow_inits: &mut FlowAtLocation<MaybeInitializedPlaces<'_, 'gcx, 'tcx>>, + move_data: &MoveData<'tcx>, + liveness_map: &NllLivenessMap, +) { + debug!("trace()"); + + if liveness_map.is_empty() { + return; + } + + let local_use_map = &LocalUseMap::build(liveness_map, elements, mir); + + let cx = LivenessContext { + typeck, + mir, + flow_inits, + elements, + local_use_map, + move_data, + liveness_map, + drop_data: FxHashMap::default(), + }; + + LivenessResults::new(cx).compute_for_all_locals(); +} + +/// Contextual state for the type-liveness generator. +struct LivenessContext<'me, 'typeck, 'flow, 'gcx, 'tcx> +where + 'typeck: 'me, + 'flow: 'me, + 'tcx: 'typeck + 'flow, + 'gcx: 'tcx, +{ + /// Current type-checker, giving us our inference context etc. + typeck: &'me mut TypeChecker<'typeck, 'gcx, 'tcx>, + + /// Defines the `PointIndex` mapping + elements: &'me RegionValueElements, + + /// MIR we are analyzing. + mir: &'me Mir<'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 FlowAtLocation<MaybeInitializedPlaces<'flow, 'gcx, 'tcx>>, + + /// 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, +} + +struct DropData<'tcx> { + dropck_result: DropckOutlivesResult<'tcx>, + region_constraint_data: Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>, +} + +struct LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> +where + 'typeck: 'me, + 'flow: 'me, + 'tcx: 'typeck + 'flow, + 'gcx: 'tcx, +{ + cx: LivenessContext<'me, 'typeck, 'flow, 'gcx, 'tcx>, + + /// Set of points that define the current local. + defs: BitArray<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: BitArray<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: BitArray<PointIndex>, + + /// Locations where drops may occur. + drop_locations: Vec<Location>, + + /// Stack used when doing (reverse) DFS. + stack: Vec<PointIndex>, +} + +impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { + fn new(cx: LivenessContext<'me, 'typeck, 'flow, 'gcx, 'tcx>) -> Self { + let num_points = cx.elements.num_points(); + LivenessResults { + cx, + defs: BitArray::new(num_points), + use_live_at: BitArray::new(num_points), + drop_live_at: BitArray::new(num_points), + drop_locations: vec![], + stack: vec![], + } + } + + 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); + + 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); + + let local_ty = self.cx.mir.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, + ); + } + } + } + + /// 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, live_local: LiveVar) { + for def in self.cx.local_use_map.defs(live_local) { + debug!("- defined at {:?}", def); + self.defs.insert(def); + } + } + + /// Compute 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 + /// 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); + + self.stack.extend(self.cx.local_use_map.uses(live_local)); + while let Some(p) = self.stack.pop() { + if self.defs.contains(p) { + continue; + } + + if self.use_live_at.insert(p) { + self.cx + .elements + .push_predecessors(self.cx.mir, p, &mut self.stack) + } + } + } + + /// Compute 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, live_local: LiveVar) { + debug!("compute_drop_live_points_for(live_local={:?})", live_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) { + let location = self.cx.elements.to_location(drop_point); + debug_assert_eq!(self.cx.mir.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. + 'next_block: 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.mir.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; + } + } + + for &pred_block in self.cx.mir.predecessors_for(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.mir.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 LivenessContext<'_, '_, '_, '_, 'tcx> { + /// 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 { + // Compute the set of initialized paths at terminator of block + // by resetting to the start of the block and then applying + // the effects of all statements. This is the only way to get + // "just ahead" of a terminator. + self.flow_inits.reset_to_entry_of(block); + for statement_index in 0..self.mir[block].statements.len() { + let location = Location { + block, + statement_index, + }; + self.flow_inits.reconstruct_statement_effect(location); + self.flow_inits.apply_local_effect(location); + } + + self.flow_inits.has_any_child_of(mpi).is_some() + } + + /// 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.reset_to_exit_of(block); + self.flow_inits.has_any_child_of(mpi).is_some() + } + + /// Store the result that all regions in `value` are live for the + /// points `live_at`. + fn add_use_live_facts_for( + &mut self, + value: impl TypeFoldable<'tcx>, + live_at: &BitArray<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: &BitArray<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.boring(), data); + } + } + + drop_data.dropck_result.report_overflows( + self.typeck.infcx.tcx, + self.mir.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); + } + } + + fn make_all_regions_live( + elements: &RegionValueElements, + typeck: &mut TypeChecker<'_, '_, 'tcx>, + value: impl TypeFoldable<'tcx>, + live_at: &BitArray<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 borrowck_context = typeck.borrowck_context.as_mut().unwrap(); + let live_region_vid = borrowck_context + .universal_regions + .to_region_vid(live_region); + borrowck_context + .constraints + .liveness_constraints + .add_elements(live_region_vid, live_at); + + if let Some(_) = borrowck_context.all_facts { + bug!("polonius liveness facts not implemented yet") + } + }); + } + + fn compute_drop_data( + typeck: &mut TypeChecker<'_, 'gcx, 'tcx>, + dropped_ty: Ty<'tcx>, + ) -> DropData<'tcx> { + debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,); + + let param_env = typeck.param_env; + let (dropck_result, region_constraint_data) = param_env + .and(DropckOutlives::new(dropped_ty)) + .fully_perform(typeck.infcx) + .unwrap(); + + DropData { + dropck_result, + region_constraint_data, + } + } +} 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 27417466c68..3a5857f775f 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs @@ -18,9 +18,7 @@ use borrow_check::nll::facts::AllFacts; use borrow_check::nll::region_infer::values::{LivenessValues, RegionValueElements}; use borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest}; use borrow_check::nll::type_check::free_region_relations::{CreateResult, UniversalRegionRelations}; -use borrow_check::nll::type_check::liveness::liveness_map::NllLivenessMap; use borrow_check::nll::universal_regions::UniversalRegions; -use borrow_check::nll::LocalWithRegion; use borrow_check::nll::ToRegionVid; use dataflow::move_paths::MoveData; use dataflow::FlowAtLocation; @@ -43,7 +41,6 @@ use std::fmt; use std::rc::Rc; use syntax_pos::{Span, DUMMY_SP}; use transform::{MirPass, MirSource}; -use util::liveness::LivenessResults; use rustc_data_structures::fx::FxHashSet; use rustc_data_structures::indexed_vec::Idx; @@ -143,7 +140,7 @@ pub(crate) fn type_check<'gcx, 'tcx>( all_facts, ); - let (liveness, liveness_map) = { + { let mut borrowck_context = BorrowCheckContext { universal_regions, location_table, @@ -169,16 +166,14 @@ pub(crate) fn type_check<'gcx, 'tcx>( &universal_region_relations, &normalized_inputs_and_output, ); - liveness::generate(cx, mir, flow_inits, move_data) + liveness::generate(cx, mir, elements, flow_inits, move_data); }, - ) - }; + ); + } MirTypeckResults { constraints, universal_region_relations, - liveness, - liveness_map, } } @@ -672,8 +667,6 @@ struct BorrowCheckContext<'a, 'tcx: 'a> { crate struct MirTypeckResults<'tcx> { crate constraints: MirTypeckRegionConstraints<'tcx>, crate universal_region_relations: Rc<UniversalRegionRelations<'tcx>>, - crate liveness: LivenessResults<LocalWithRegion>, - crate liveness_map: NllLivenessMap, } /// A collection of region constraints that must be satisfied for the diff --git a/src/librustc_mir/dataflow/at_location.rs b/src/librustc_mir/dataflow/at_location.rs index 1f7faa21a12..d97c0c9b430 100644 --- a/src/librustc_mir/dataflow/at_location.rs +++ b/src/librustc_mir/dataflow/at_location.rs @@ -28,6 +28,15 @@ pub trait FlowsAtLocation { /// Reset the state bitvector to represent the entry to block `bb`. fn reset_to_entry_of(&mut self, bb: BasicBlock); + /// Reset the state bitvector to represent the exit of the + /// terminator of block `bb`. + /// + /// **Important:** In the case of a `Call` terminator, these + /// effects do *not* include the result of storing the destination + /// of the call, since that is edge-dependent (in other words, the + /// effects don't apply to the unwind edge). + fn reset_to_exit_of(&mut self, bb: BasicBlock); + /// Build gen + kill sets for statement at `loc`. /// /// Note that invoking this method alone does not change the @@ -142,6 +151,12 @@ impl<BD> FlowsAtLocation for FlowAtLocation<BD> self.curr_state.overwrite(self.base_results.sets().on_entry_set_for(bb.index())); } + fn reset_to_exit_of(&mut self, bb: BasicBlock) { + self.reset_to_entry_of(bb); + self.curr_state.union(self.base_results.sets().gen_set_for(bb.index())); + self.curr_state.subtract(self.base_results.sets().kill_set_for(bb.index())); + } + fn reconstruct_statement_effect(&mut self, loc: Location) { self.stmt_gen.clear(); self.stmt_kill.clear(); diff --git a/src/librustc_mir/dataflow/mod.rs b/src/librustc_mir/dataflow/mod.rs index 48d34997868..fd6569feb5c 100644 --- a/src/librustc_mir/dataflow/mod.rs +++ b/src/librustc_mir/dataflow/mod.rs @@ -454,14 +454,18 @@ pub struct AllSets<E: Idx> { /// For each block, bits valid on entry to the block. on_entry_sets: Vec<IdxSet<E>>, - /// For each block, bits generated by executing the statements in - /// the block. (For comparison, the Terminator for each block is - /// handled in a flow-specific manner during propagation.) + /// For each block, bits generated by executing the statements + + /// terminator in the block -- with one caveat. In particular, for + /// *call terminators*, the effect of storing the destination is + /// not included, since that only takes effect on the **success** + /// edge (and not the unwind edge). gen_sets: Vec<HybridIdxSet<E>>, - /// For each block, bits killed by executing the statements in the - /// block. (For comparison, the Terminator for each block is - /// handled in a flow-specific manner during propagation.) + /// For each block, bits killed by executing the statements + + /// terminator in the block -- with one caveat. In particular, for + /// *call terminators*, the effect of storing the destination is + /// not included, since that only takes effect on the **success** + /// edge (and not the unwind edge). kill_sets: Vec<HybridIdxSet<E>>, } diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs index da29c900b8f..cfa84264b1f 100644 --- a/src/librustc_mir/lib.rs +++ b/src/librustc_mir/lib.rs @@ -17,6 +17,7 @@ Rust MIR: a lowered representation of Rust. Also: an experiment! #![cfg_attr(not(stage0), feature(nll))] #![cfg_attr(not(stage0), feature(infer_outlives_requirements))] #![feature(in_band_lifetimes)] +#![feature(impl_header_lifetime_elision)] #![feature(slice_patterns)] #![feature(slice_sort_by_cached_key)] #![feature(box_patterns)] diff --git a/src/librustc_mir/transform/generator.rs b/src/librustc_mir/transform/generator.rs index db588884d8e..e9afa7df5c4 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, IdentityMap, LivenessMode}; +use util::liveness::{self, IdentityMap}; use rustc_data_structures::indexed_vec::Idx; use rustc_data_structures::indexed_set::IdxSet; use std::collections::HashMap; @@ -402,10 +402,6 @@ fn locals_live_across_suspend_points<'a, 'tcx,>(tcx: TyCtxt<'a, 'tcx, 'tcx>, 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( diff --git a/src/librustc_mir/util/liveness.rs b/src/librustc_mir/util/liveness.rs index 04fa516a655..3ae470e1d4b 100644 --- a/src/librustc_mir/util/liveness.rs +++ b/src/librustc_mir/util/liveness.rs @@ -33,7 +33,6 @@ //! generator yield points, all pre-existing references are invalidated, so this //! doesn't matter). -use rustc::mir::visit::MirVisitable; use rustc::mir::visit::{PlaceContext, Visitor}; use rustc::mir::Local; use rustc::mir::*; @@ -50,17 +49,13 @@ use util::pretty::{dump_enabled, write_basic_block, write_mir_intro}; pub type LiveVarSet<V> = IdxSet<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. +/// basic blocks. /// /// 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, LiveVarSet<V>>, @@ -104,68 +99,11 @@ impl<'a, 'tcx> LiveVariableMap for IdentityMap<'a, 'tcx> { } } -#[derive(Copy, Clone, Debug)] -pub struct LivenessMode { - /// If true, then we will consider "regular uses" of a variable to be live. - /// For example, if the user writes `foo(x)`, then this is a regular use of - /// the variable `x`. - pub include_regular_use: bool, - - /// If true, then we will consider (implicit) drops of a variable - /// to be live. For example, if the user writes `{ let x = - /// vec![...]; .. }`, then the drop at the end of the block is an - /// implicit drop. - /// - /// NB. Despite its name, a call like `::std::mem::drop(x)` is - /// **not** considered a drop for this purposes, but rather a - /// regular use. - pub include_drops: bool, -} - -/// A combination of liveness results, used in NLL. -pub struct LivenessResults<V: Idx> { - /// Liveness results where a regular use makes a variable X live, - /// but not a drop. - pub regular: LivenessResult<V>, - - /// Liveness results where a drop makes a variable X live, - /// but not a regular use. - pub drop: LivenessResult<V>, -} - -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, - LivenessMode { - include_regular_use: true, - include_drops: false, - }, - map, - ), - - drop: liveness_of_locals( - &mir, - LivenessMode { - include_regular_use: false, - include_drops: true, - }, - map, - ), - } - } -} - /// 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, V: Idx>( mir: &Mir<'tcx>, - mode: LivenessMode, map: &impl LiveVariableMap<LiveVar = V>, ) -> LivenessResult<V> { let num_live_vars = map.num_variables(); @@ -173,7 +111,7 @@ pub fn liveness_of_locals<'tcx, V: Idx>( let def_use: IndexVec<_, DefsUses<V>> = mir .basic_blocks() .iter() - .map(|b| block(mode, map, b, num_live_vars)) + .map(|b| block(map, b, num_live_vars)) .collect(); let mut outs: IndexVec<_, LiveVarSet<V>> = mir @@ -208,80 +146,17 @@ pub fn liveness_of_locals<'tcx, V: Idx>( } } - LivenessResult { mode, outs } -} - -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, - map: &impl LiveVariableMap<LiveVar = V>, - mut callback: OP, - ) where - OP: FnMut(Location, &LiveVarSet<V>), - { - let data = &mir[block]; - - // Get a copy of the bits on exit from the block. - let mut bits = self.outs[block].clone(); - - // Start with the maximal statement index -- i.e., right before - // the terminator executes. - let mut statement_index = data.statements.len(); - - // Compute liveness right before terminator and invoke callback. - let terminator_location = Location { - block, - statement_index, - }; - let num_live_vars = map.num_variables(); - let mut visitor = DefsUsesVisitor { - mode: self.mode, - map, - defs_uses: DefsUses { - 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, - ); - - // Compute liveness before each statement (in rev order) and invoke callback. - for statement in data.statements.iter().rev() { - statement_index -= 1; - let statement_location = Location { - block, - statement_index, - }; - visitor.defs_uses.clear(); - visitor.update_bits_and_do_callback( - statement_location, - statement, - &mut bits, - &mut callback, - ); - } - } + LivenessResult { outs } } #[derive(Eq, PartialEq, Clone)] pub enum DefUse { Def, Use, + Drop, } -pub fn categorize<'tcx>(context: PlaceContext<'tcx>, mode: LivenessMode) -> Option<DefUse> { +pub fn categorize<'tcx>(context: PlaceContext<'tcx>) -> Option<DefUse> { match context { /////////////////////////////////////////////////////////////////////////// // DEFS @@ -322,13 +197,8 @@ pub fn categorize<'tcx>(context: PlaceContext<'tcx>, mode: LivenessMode) -> Opti PlaceContext::Inspect | PlaceContext::Copy | PlaceContext::Move | - PlaceContext::Validate => { - if mode.include_regular_use { - Some(DefUse::Use) - } else { - None - } - } + PlaceContext::Validate => + Some(DefUse::Use), /////////////////////////////////////////////////////////////////////////// // DROP USES @@ -338,13 +208,8 @@ pub fn categorize<'tcx>(context: PlaceContext<'tcx>, mode: LivenessMode) -> Opti // uses in drop are special because `#[may_dangle]` // attributes can affect whether lifetimes must be live. - PlaceContext::Drop => { - if mode.include_drops { - Some(DefUse::Use) - } else { - None - } - } + PlaceContext::Drop => + Some(DefUse::Drop), } } @@ -353,7 +218,6 @@ where V: Idx, M: LiveVariableMap<LiveVar = V> + 'lv, { - mode: LivenessMode, map: &'lv M, defs_uses: DefsUses<V>, } @@ -365,11 +229,6 @@ struct DefsUses<V: Idx> { } impl<V: Idx> DefsUses<V> { - fn clear(&mut self) { - self.uses.clear(); - self.defs.clear(); - } - fn apply(&self, bits: &mut LiveVarSet<V>) -> bool { bits.subtract(&self.defs) | bits.union(&self.uses) } @@ -404,29 +263,6 @@ impl<V: Idx> DefsUses<V> { } } -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 LiveVarSet<V>, - callback: &mut OP, - ) where - OP: FnMut(Location, &LiveVarSet<V>), - { - value.apply(location, self); - self.defs_uses.apply(bits); - callback(location, bits); - } -} - impl<'tcx, 'lv, V, M> Visitor<'tcx> for DefsUsesVisitor<'lv, V, M> where V: Idx, @@ -434,23 +270,21 @@ where { fn visit_local(&mut self, &local: &Local, context: PlaceContext<'tcx>, _: Location) { if let Some(v_index) = self.map.from_local(local) { - match categorize(context, self.mode) { + match categorize(context) { Some(DefUse::Def) => self.defs_uses.add_def(v_index), - Some(DefUse::Use) => self.defs_uses.add_use(v_index), - None => (), + Some(DefUse::Use) | Some(DefUse::Drop) => self.defs_uses.add_use(v_index), + _ => (), } } } } 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: LiveVarSet::new_empty(locals), @@ -526,7 +360,8 @@ pub fn write_mir_fn<'a, 'tcx, V: Idx>( 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 live: Vec<String> = result[block].iter() + let live: Vec<String> = result[block] + .iter() .map(|v| map.from_live_var(v)) .map(|local| format!("{:?}", local)) .collect(); diff --git a/src/test/mir-opt/nll/named-lifetimes-basic.rs b/src/test/mir-opt/nll/named-lifetimes-basic.rs index adc0249a40c..ffc5603bb16 100644 --- a/src/test/mir-opt/nll/named-lifetimes-basic.rs +++ b/src/test/mir-opt/nll/named-lifetimes-basic.rs @@ -34,15 +34,15 @@ fn main() { // | '_#4r | Local | ['_#4r] // | // | Inferred Region Values -// | '_#0r | U0 | {bb0[0..=127], '_#0r} -// | '_#1r | U0 | {bb0[0..=127], '_#1r} -// | '_#2r | U0 | {bb0[0..=127], '_#2r} -// | '_#3r | U0 | {bb0[0..=127], '_#3r} -// | '_#4r | U0 | {bb0[0..=127], '_#4r} -// | '_#5r | U0 | {bb0[0..=127], '_#1r} -// | '_#6r | U0 | {bb0[0..=127], '_#2r} -// | '_#7r | U0 | {bb0[0..=127], '_#1r} -// | '_#8r | U0 | {bb0[0..=127], '_#3r} +// | '_#0r | U0 | {bb0[0..=1], '_#0r} +// | '_#1r | U0 | {bb0[0..=1], '_#1r} +// | '_#2r | U0 | {bb0[0..=1], '_#2r} +// | '_#3r | U0 | {bb0[0..=1], '_#3r} +// | '_#4r | U0 | {bb0[0..=1], '_#4r} +// | '_#5r | U0 | {bb0[0..=1], '_#1r} +// | '_#6r | U0 | {bb0[0..=1], '_#2r} +// | '_#7r | U0 | {bb0[0..=1], '_#1r} +// | '_#8r | U0 | {bb0[0..=1], '_#3r} // | // ... // fn use_x(_1: &'_#5r mut i32, _2: &'_#6r u32, _3: &'_#7r u32, _4: &'_#8r u32) -> bool { diff --git a/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.rs b/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.rs index 5538eca3629..808114f3fa9 100644 --- a/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.rs +++ b/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.rs @@ -8,10 +8,8 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -//compile-flags: -Z emit-end-regions -Zborrowck=mir - - #![allow(warnings)] +#![feature(nll)] struct Wrap<'p> { p: &'p mut i32 } diff --git a/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.stderr b/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.stderr index 327454ee60e..6fc26d502d3 100644 --- a/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.stderr +++ b/src/test/ui/nll/maybe-initialized-drop-implicit-fragment-drop.stderr @@ -1,5 +1,5 @@ error[E0506]: cannot assign to `x` because it is borrowed - --> $DIR/maybe-initialized-drop-implicit-fragment-drop.rs:32:5 + --> $DIR/maybe-initialized-drop-implicit-fragment-drop.rs:30:5 | LL | let wrap = Wrap { p: &mut x }; | ------ borrow of `x` occurs here |