From cdb95b0f215fb3590dc86223712b5bbcf126582f Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Fri, 28 Sep 2018 14:35:43 -0400 Subject: [PATCH] build up the placeholder indices as we go Avoids a linear walk over the regions at the end. --- src/librustc_mir/borrow_check/nll/mod.rs | 4 ++ .../borrow_check/nll/region_infer/mod.rs | 12 +---- .../borrow_check/nll/region_infer/values.rs | 4 +- .../borrow_check/nll/type_check/mod.rs | 51 ++++++++++++------- .../borrow_check/nll/type_check/relate_tys.rs | 3 ++ 5 files changed, 43 insertions(+), 31 deletions(-) diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs index b9f22c7402a..723b0e6fff6 100644 --- a/src/librustc_mir/borrow_check/nll/mod.rs +++ b/src/librustc_mir/borrow_check/nll/mod.rs @@ -107,6 +107,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( // Run the MIR type-checker. let MirTypeckResults { constraints, + placeholder_indices, universal_region_relations, } = type_check::type_check( infcx, @@ -122,6 +123,8 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( elements, ); + let placeholder_indices = Rc::new(placeholder_indices); + if let Some(all_facts) = &mut all_facts { all_facts .universal_region @@ -150,6 +153,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( let mut regioncx = RegionInferenceContext::new( var_origins, universal_regions, + placeholder_indices, universal_region_relations, mir, outlives_constraints, diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs index b11369116d4..4a8f011b606 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs @@ -183,6 +183,7 @@ impl<'tcx> RegionInferenceContext<'tcx> { pub(crate) fn new( var_infos: VarInfos, universal_regions: Rc>, + placeholder_indices: Rc, universal_region_relations: Rc>, _mir: &Mir<'tcx>, outlives_constraints: ConstraintSet, @@ -196,22 +197,13 @@ pub(crate) fn new( .map(|info| RegionDefinition::new(info.universe, info.origin)) .collect(); - // Compute the max universe used anywhere amongst the regions. - let placeholder_indices: PlaceholderIndices = definitions - .iter() - .filter_map(|d| match d.origin { - NLLRegionVariableOrigin::Placeholder(placeholder) => Some(placeholder), - _ => None, - }) - .collect(); - let constraints = Rc::new(outlives_constraints); // freeze constraints let constraint_graph = Rc::new(constraints.graph(definitions.len())); let fr_static = universal_regions.fr_static; let constraint_sccs = Rc::new(constraints.compute_sccs(&constraint_graph, fr_static)); let mut scc_values = - RegionValues::new(elements, universal_regions.len(), placeholder_indices); + RegionValues::new(elements, universal_regions.len(), &placeholder_indices); for region in liveness_constraints.rows() { let scc = constraint_sccs.scc(region); 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 6407661d292..07372c19c46 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/values.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/values.rs @@ -302,13 +302,13 @@ impl RegionValues { crate fn new( elements: &Rc, num_universal_regions: usize, - placeholder_indices: PlaceholderIndices, + placeholder_indices: &Rc, ) -> Self { let num_placeholders = placeholder_indices.len(); Self { elements: elements.clone(), points: SparseBitMatrix::new(elements.num_points), - placeholder_indices: Rc::new(placeholder_indices), + placeholder_indices: placeholder_indices.clone(), free_regions: SparseBitMatrix::new(num_universal_regions), placeholders: SparseBitMatrix::new(num_placeholders), } 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 ef4cc3452b1..99ac80862b1 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs @@ -15,7 +15,9 @@ use borrow_check::location::LocationTable; use borrow_check::nll::constraints::{ConstraintCategory, ConstraintSet, OutlivesConstraint}; use borrow_check::nll::facts::AllFacts; -use borrow_check::nll::region_infer::values::{LivenessValues, RegionValueElements}; +use borrow_check::nll::region_infer::values::LivenessValues; +use borrow_check::nll::region_infer::values::PlaceholderIndices; +use borrow_check::nll::region_infer::values::RegionValueElements; use borrow_check::nll::region_infer::{ClosureRegionRequirementsExt, TypeTest}; use borrow_check::nll::renumber; use borrow_check::nll::type_check::free_region_relations::{ @@ -42,13 +44,13 @@ use rustc::ty::fold::TypeFoldable; use rustc::ty::subst::Subst; use rustc::ty::{self, CanonicalTy, RegionVid, ToPolyTraitRef, Ty, TyCtxt, TyKind}; -use std::{fmt, iter}; use std::rc::Rc; +use std::{fmt, iter}; use syntax_pos::{Span, DUMMY_SP}; use transform::{MirPass, MirSource}; -use rustc_data_structures::fx::FxHashSet; use either::Either; +use rustc_data_structures::fx::FxHashSet; macro_rules! span_mirbug { ($context:expr, $elem:expr, $($message:tt)*) => ({ @@ -128,6 +130,7 @@ pub(crate) fn type_check<'gcx, 'tcx>( outlives_constraints: ConstraintSet::default(), type_tests: Vec::default(), }; + let mut placeholder_indices = PlaceholderIndices::default(); let CreateResult { universal_region_relations, @@ -147,6 +150,7 @@ pub(crate) fn type_check<'gcx, 'tcx>( borrow_set, all_facts, constraints: &mut constraints, + placeholder_indices: &mut placeholder_indices, }; type_check_internal( @@ -162,12 +166,15 @@ pub(crate) fn type_check<'gcx, 'tcx>( cx.equate_inputs_and_outputs(mir, universal_regions, &normalized_inputs_and_output); liveness::generate(cx, mir, elements, flow_inits, move_data, location_table); - cx.borrowck_context.as_mut().map(|bcx| translate_outlives_facts(bcx)); + cx.borrowck_context + .as_mut() + .map(|bcx| translate_outlives_facts(bcx)); }, ); MirTypeckResults { constraints, + placeholder_indices, universal_region_relations, } } @@ -210,21 +217,25 @@ fn type_check_internal<'a, 'gcx, 'tcx, R>( fn translate_outlives_facts(cx: &mut BorrowCheckContext) { if let Some(facts) = cx.all_facts { let location_table = cx.location_table; - facts.outlives.extend( - cx.constraints.outlives_constraints.iter().flat_map(|constraint: &OutlivesConstraint| { - if let Some(from_location) = constraint.locations.from_location() { - Either::Left(iter::once(( - constraint.sup, - constraint.sub, - location_table.mid_index(from_location), - ))) - } else { - Either::Right(location_table.all_points().map(move |location| { - (constraint.sup, constraint.sub, location) - })) - } - }) - ); + facts + .outlives + .extend(cx.constraints.outlives_constraints.iter().flat_map( + |constraint: &OutlivesConstraint| { + if let Some(from_location) = constraint.locations.from_location() { + Either::Left(iter::once(( + constraint.sup, + constraint.sub, + location_table.mid_index(from_location), + ))) + } else { + Either::Right( + location_table + .all_points() + .map(move |location| (constraint.sup, constraint.sub, location)), + ) + } + }, + )); } } @@ -718,10 +729,12 @@ struct BorrowCheckContext<'a, 'tcx: 'a> { all_facts: &'a mut Option, borrow_set: &'a BorrowSet<'tcx>, constraints: &'a mut MirTypeckRegionConstraints<'tcx>, + placeholder_indices: &'a mut PlaceholderIndices, } crate struct MirTypeckResults<'tcx> { crate constraints: MirTypeckRegionConstraints<'tcx>, + crate placeholder_indices: PlaceholderIndices, crate universal_region_relations: Rc>, } diff --git a/src/librustc_mir/borrow_check/nll/type_check/relate_tys.rs b/src/librustc_mir/borrow_check/nll/type_check/relate_tys.rs index 8addafaedad..4e8dbf8498e 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/relate_tys.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/relate_tys.rs @@ -217,6 +217,9 @@ fn next_existential_region_var(&mut self) -> ty::Region<'tcx> { fn next_placeholder_region(&mut self, placeholder: ty::Placeholder) -> ty::Region<'tcx> { let origin = NLLRegionVariableOrigin::Placeholder(placeholder); + if let Some(borrowck_context) = &mut self.borrowck_context { + borrowck_context.placeholder_indices.insert(placeholder); + } self.infcx.next_nll_region_var(origin) } -- 2.44.0