diff options
5 files changed, 88 insertions, 140 deletions
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 166281fd331..554338c3e00 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/values.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/values.rs @@ -20,13 +20,23 @@ 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 into to one of two possible values: + /// + /// - `None`: if this point index represents a Location with non-zero index + /// - `Some(bb)`: if this point index represents a Location with zero index + /// + /// NB. It may be better to just map back to a full `Location`. We + /// should probably try that. + basic_block_heads: IndexVec<PointIndex, Option<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,8 +51,16 @@ impl RegionValueElements { ); debug!("RegionValueElements: num_points={:#?}", num_points); + let mut basic_block_heads: IndexVec<PointIndex, Option<BasicBlock>> = + (0..num_points).map(|_| None).collect(); + for (bb, &first_point) in statements_before_block.iter_enumerated() { + let first_point = PointIndex::new(first_point); + basic_block_heads[first_point] = Some(bb); + } + Self { statements_before_block, + basic_block_heads, num_points, } } @@ -70,47 +88,55 @@ impl RegionValueElements { /// 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, + crate fn to_location(&self, index: PointIndex) -> Location { + assert!(index.index() < self.num_points); + + let mut statement_index = 0; + + for opt_bb in self.basic_block_heads.raw[..= index.index()].iter().rev() { + if let &Some(block) = opt_bb { + return Location { block, statement_index }; + } + + statement_index += 1; } - } - /// Returns an iterator of each basic block and the first point - /// index within the block; the point indices for all statements - /// within the block follow afterwards. - crate fn head_indices(&self) -> impl Iterator<Item = (BasicBlock, PointIndex)> + '_ { - self.statements_before_block - .iter_enumerated() - .map(move |(bb, &first_index)| (bb, PointIndex::new(first_index))) + bug!("did not find basic block as expected for index = {:?}", 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>, + ) { + match self.basic_block_heads[index] { + // If this is a basic block head, then the predecessors are + // the the terminators of other basic blocks + Some(bb_head) => { + stack.extend( + mir + .predecessors_for(bb_head) + .iter() + .map(|&pred_bb| mir.terminator_loc(pred_bb)) + .map(|pred_loc| self.point_from_location(pred_loc)), + ); + } + + // Otherwise, the pred is just the previous statement + None => { + stack.push(PointIndex::new(index.index() - 1)); + } + } } } @@ -196,6 +222,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), ) @@ -304,7 +331,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. @@ -400,6 +431,7 @@ crate fn location_set_str( region_value_str( points .into_iter() + .take_while(|&p| elements.point_in_range(p)) .map(|p| elements.to_location(p)) .map(RegionElement::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 d6fdd1c849c..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 @@ -24,7 +24,6 @@ use super::TypeChecker; crate mod liveness_map; mod local_use_map; -mod point_index_map; mod trace; /// Combines liveness analysis with initialization analysis to diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/point_index_map.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/point_index_map.rs deleted file mode 100644 index c2c21aa0d8d..00000000000 --- a/src/librustc_mir/borrow_check/nll/type_check/liveness/point_index_map.rs +++ /dev/null @@ -1,78 +0,0 @@ -// 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::PointIndex; -use borrow_check::nll::region_infer::values::RegionValueElements; -use rustc::mir::{BasicBlock, Location, Mir}; -use rustc_data_structures::indexed_vec::{Idx, IndexVec}; -use std::rc::Rc; - -/// A little data structure that makes it more efficient to find the -/// predecessors of each point. -crate struct PointIndexMap<'me, 'tcx> { - elements: &'me Rc<RegionValueElements>, - mir: &'me Mir<'tcx>, - basic_block_heads: IndexVec<PointIndex, Option<BasicBlock>>, -} - -impl PointIndexMap<'m, 'tcx> { - crate fn new(elements: &'m Rc<RegionValueElements>, mir: &'m Mir<'tcx>) -> Self { - let mut basic_block_heads = IndexVec::from_elem_n(None, elements.num_points()); - - for (bb, first_point) in elements.head_indices() { - basic_block_heads[first_point] = Some(bb); - } - - PointIndexMap { - elements, - mir, - basic_block_heads, - } - } - - crate fn num_points(&self) -> usize { - self.elements.num_points() - } - - crate fn location_of(&self, index: PointIndex) -> Location { - let mut statement_index = 0; - - for &opt_bb in self.basic_block_heads.raw[..= index.index()].iter().rev() { - if let Some(block) = opt_bb { - return Location { block, statement_index }; - } - - statement_index += 1; - } - - bug!("did not find basic block as expected for index = {:?}", index) - } - - crate fn push_predecessors(&self, index: PointIndex, stack: &mut Vec<PointIndex>) { - match self.basic_block_heads[index] { - // If this is a basic block head, then the predecessors are - // the the terminators of other basic blocks - Some(bb_head) => { - stack.extend( - self.mir - .predecessors_for(bb_head) - .iter() - .map(|&pred_bb| self.mir.terminator_loc(pred_bb)) - .map(|pred_loc| self.elements.point_from_location(pred_loc)), - ); - } - - // Otherwise, the pred is just the previous statement - None => { - stack.push(PointIndex::new(index.index() - 1)); - } - } - } -} diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs index 61c6d263605..79589ce9733 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs @@ -11,7 +11,6 @@ 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::liveness::point_index_map::PointIndexMap; use borrow_check::nll::type_check::AtLocation; use borrow_check::nll::type_check::TypeChecker; use dataflow::move_paths::indexes::MovePathIndex; @@ -57,7 +56,6 @@ pub(super) fn trace( } let local_use_map = &LocalUseMap::build(liveness_map, elements, mir); - let point_index_map = &PointIndexMap::new(elements, mir); let cx = LivenessContext { typeck, @@ -67,7 +65,6 @@ pub(super) fn trace( local_use_map, move_data, liveness_map, - point_index_map, drop_data: FxHashMap::default(), }; @@ -105,8 +102,6 @@ where /// dropped. local_use_map: &'me LocalUseMap<'me>, - point_index_map: &'me PointIndexMap<'me, 'tcx>, - /// Map tracking which variables need liveness computation. liveness_map: &'me NllLivenessMap, } @@ -146,7 +141,7 @@ where impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { fn new(cx: LivenessContext<'me, 'typeck, 'flow, 'gcx, 'tcx>) -> Self { - let num_points = cx.point_index_map.num_points(); + let num_points = cx.elements.num_points(); LivenessResults { cx, defs: BitArray::new(num_points), @@ -218,8 +213,8 @@ impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { if self.use_live_at.insert(p) { self.cx - .point_index_map - .push_predecessors(p, &mut self.stack) + .elements + .push_predecessors(self.cx.mir, p, &mut self.stack) } } } @@ -242,7 +237,7 @@ impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { // Find the drops where `local` is initialized. for drop_point in self.cx.local_use_map.drops(live_local) { - let location = self.cx.point_index_map.location_of(drop_point); + 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) { @@ -281,7 +276,7 @@ impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { debug!( "compute_drop_live_points_for_block(mpi={:?}, term_point={:?})", self.cx.move_data.move_paths[mpi].place, - self.cx.point_index_map.location_of(term_point), + self.cx.elements.to_location(term_point), ); // We are only invoked with terminators where `mpi` is @@ -301,7 +296,7 @@ impl LivenessResults<'me, 'typeck, 'flow, 'gcx, 'tcx> { for p in (entry_point..term_point).rev() { debug!( "compute_drop_live_points_for_block: p = {:?}", - self.cx.point_index_map.location_of(p), + self.cx.elements.to_location(p), ); if self.defs.contains(p) { 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 { |