From 7523c7368c9e875eae6da46091cbf86c48041b89 Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Tue, 24 Oct 2017 14:20:47 -0400 Subject: introduce liveness constraints into NLL code And do a bunch of gratuitious refactoring that I did not bother to separate into nice commits. --- src/librustc_data_structures/indexed_set.rs | 12 +- src/librustc_mir/lib.rs | 1 + .../transform/nll/constraint_generation.rs | 64 +++++ src/librustc_mir/transform/nll/infer.rs | 222 ---------------- src/librustc_mir/transform/nll/mod.rs | 287 ++++++++------------- src/librustc_mir/transform/nll/region_infer.rs | 225 ++++++++++++++++ src/librustc_mir/transform/nll/renumber.rs | 132 ++++++++++ src/test/mir-opt/nll/region-liveness-basic.rs | 55 ++++ 8 files changed, 591 insertions(+), 407 deletions(-) create mode 100644 src/librustc_mir/transform/nll/constraint_generation.rs delete mode 100644 src/librustc_mir/transform/nll/infer.rs create mode 100644 src/librustc_mir/transform/nll/region_infer.rs create mode 100644 src/librustc_mir/transform/nll/renumber.rs create mode 100644 src/test/mir-opt/nll/region-liveness-basic.rs (limited to 'src') diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs index c790463e47a..c5ffb003399 100644 --- a/src/librustc_data_structures/indexed_set.rs +++ b/src/librustc_data_structures/indexed_set.rs @@ -53,11 +53,19 @@ pub struct IdxSet { } impl fmt::Debug for IdxSetBuf { - fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) } + fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { + w.debug_list() + .entries(self.iter()) + .finish() + } } impl fmt::Debug for IdxSet { - fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { self.bits.fmt(w) } + fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result { + w.debug_list() + .entries(self.iter()) + .finish() + } } impl IdxSetBuf { diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs index 7e4206e14c5..16753cee7e0 100644 --- a/src/librustc_mir/lib.rs +++ b/src/librustc_mir/lib.rs @@ -18,6 +18,7 @@ Rust MIR: a lowered representation of Rust. Also: an experiment! #![feature(box_patterns)] #![feature(box_syntax)] +#![feature(conservative_impl_trait)] #![feature(const_fn)] #![feature(core_intrinsics)] #![feature(i128_type)] diff --git a/src/librustc_mir/transform/nll/constraint_generation.rs b/src/librustc_mir/transform/nll/constraint_generation.rs new file mode 100644 index 00000000000..1c0c3b6fc33 --- /dev/null +++ b/src/librustc_mir/transform/nll/constraint_generation.rs @@ -0,0 +1,64 @@ +// 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 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc::mir::Mir; +use rustc::infer::InferCtxt; +use util::liveness::LivenessResult; + +use super::ToRegionIndex; +use super::region_infer::RegionInferenceContext; + +pub fn generate_constraints<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>, + regioncx: &mut RegionInferenceContext, + mir: &Mir<'tcx>, + liveness: &LivenessResult) +{ + ConstraintGeneration { infcx, regioncx, mir, liveness }.add_constraints(); +} + +struct ConstraintGeneration<'constrain, 'gcx: 'tcx, 'tcx: 'constrain> { + infcx: &'constrain InferCtxt<'constrain, 'gcx, 'tcx>, + regioncx: &'constrain mut RegionInferenceContext, + mir: &'constrain Mir<'tcx>, + liveness: &'constrain LivenessResult, +} + +impl<'constrain, 'gcx, 'tcx> ConstraintGeneration<'constrain, 'gcx, 'tcx> { + fn add_constraints(&mut self) { + // To start, add the liveness constraints. + self.add_liveness_constraints(); + } + + /// 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) { + let tcx = self.infcx.tcx; + + debug!("add_liveness_constraints()"); + for bb in self.mir.basic_blocks().indices() { + debug!("add_liveness_constraints: bb={:?}", bb); + + self.liveness.simulate_block(self.mir, bb, |location, live_locals| { + debug!("add_liveness_constraints: location={:?} live_locals={:?}", + location, live_locals); + + for live_local in live_locals.iter() { + let live_local_ty = self.mir.local_decls[live_local].ty; + tcx.for_each_free_region(&live_local_ty, |live_region| { + let vid = live_region.to_region_index(); + self.regioncx.add_live_point(vid, location); + }) + } + }); + } + } +} diff --git a/src/librustc_mir/transform/nll/infer.rs b/src/librustc_mir/transform/nll/infer.rs deleted file mode 100644 index e6e00f295ca..00000000000 --- a/src/librustc_mir/transform/nll/infer.rs +++ /dev/null @@ -1,222 +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 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use super::{Region, RegionIndex}; -use std::mem; -use rustc::infer::InferCtxt; -use rustc::mir::{Location, Mir}; -use rustc_data_structures::indexed_vec::{Idx, IndexVec}; -use rustc_data_structures::fx::FxHashSet; - -pub struct InferenceContext { - definitions: IndexVec, - constraints: IndexVec, - errors: IndexVec, -} - -pub struct InferenceError { - pub constraint_point: Location, - pub name: (), // FIXME(nashenas88) RegionName -} - -newtype_index!(InferenceErrorIndex); - -struct VarDefinition { - name: (), // FIXME(nashenas88) RegionName - value: Region, - capped: bool, -} - -impl VarDefinition { - pub fn new(value: Region) -> Self { - Self { - name: (), - value, - capped: false, - } - } -} - -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] -pub struct Constraint { - sub: RegionIndex, - sup: RegionIndex, - point: Location, -} - -newtype_index!(ConstraintIndex); - -impl InferenceContext { - pub fn new(values: IndexVec) -> Self { - Self { - definitions: values.into_iter().map(VarDefinition::new).collect(), - constraints: IndexVec::new(), - errors: IndexVec::new(), - } - } - - #[allow(dead_code)] - pub fn cap_var(&mut self, v: RegionIndex) { - self.definitions[v].capped = true; - } - - #[allow(dead_code)] - pub fn add_live_point(&mut self, v: RegionIndex, point: Location) { - debug!("add_live_point({:?}, {:?})", v, point); - let definition = &mut self.definitions[v]; - if definition.value.add_point(point) { - if definition.capped { - self.errors.push(InferenceError { - constraint_point: point, - name: definition.name, - }); - } - } - } - - #[allow(dead_code)] - pub fn add_outlives(&mut self, sup: RegionIndex, sub: RegionIndex, point: Location) { - debug!("add_outlives({:?}: {:?} @ {:?}", sup, sub, point); - self.constraints.push(Constraint { sup, sub, point }); - } - - #[allow(dead_code)] - pub fn region(&self, v: RegionIndex) -> &Region { - &self.definitions[v].value - } - - pub fn solve<'a, 'gcx, 'tcx>( - &mut self, - infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, - mir: &'a Mir<'tcx>, - ) -> IndexVec - where - 'gcx: 'tcx + 'a, - 'tcx: 'a, - { - let mut changed = true; - let mut dfs = Dfs::new(infcx, mir); - while changed { - changed = false; - for constraint in &self.constraints { - let sub = &self.definitions[constraint.sub].value.clone(); - let sup_def = &mut self.definitions[constraint.sup]; - debug!("constraint: {:?}", constraint); - debug!(" sub (before): {:?}", sub); - debug!(" sup (before): {:?}", sup_def.value); - - if dfs.copy(sub, &mut sup_def.value, constraint.point) { - changed = true; - if sup_def.capped { - // This is kind of a hack, but when we add a - // constraint, the "point" is always the point - // AFTER the action that induced the - // constraint. So report the error on the - // action BEFORE that. - assert!(constraint.point.statement_index > 0); - let p = Location { - block: constraint.point.block, - statement_index: constraint.point.statement_index - 1, - }; - - self.errors.push(InferenceError { - constraint_point: p, - name: sup_def.name, - }); - } - } - - debug!(" sup (after) : {:?}", sup_def.value); - debug!(" changed : {:?}", changed); - } - debug!("\n"); - } - - mem::replace(&mut self.errors, IndexVec::new()) - } -} - -struct Dfs<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> { - #[allow(dead_code)] - infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, - mir: &'a Mir<'tcx>, -} - -impl<'a, 'gcx: 'tcx, 'tcx: 'a> Dfs<'a, 'gcx, 'tcx> { - fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, mir: &'a Mir<'tcx>) -> Self { - Self { infcx, mir } - } - - fn copy( - &mut self, - from_region: &Region, - to_region: &mut Region, - start_point: Location, - ) -> bool { - let mut changed = false; - - let mut stack = vec![]; - let mut visited = FxHashSet(); - - stack.push(start_point); - while let Some(p) = stack.pop() { - debug!(" dfs: p={:?}", p); - - if !from_region.may_contain(p) { - debug!(" not in from-region"); - continue; - } - - if !visited.insert(p) { - debug!(" already visited"); - continue; - } - - changed |= to_region.add_point(p); - - let block_data = &self.mir[p.block]; - let successor_points = if p.statement_index < block_data.statements.len() { - vec![Location { - statement_index: p.statement_index + 1, - ..p - }] - } else { - block_data.terminator() - .successors() - .iter() - .map(|&basic_block| Location { - statement_index: 0, - block: basic_block, - }) - .collect::>() - }; - - if successor_points.is_empty() { - // FIXME handle free regions - // If we reach the END point in the graph, then copy - // over any skolemized end points in the `from_region` - // and make sure they are included in the `to_region`. - // for region_decl in self.infcx.tcx.tables.borrow().free_region_map() { - // // FIXME(nashenas88) figure out skolemized_end points - // let block = self.env.graph.skolemized_end(region_decl.name); - // let skolemized_end_point = Location { - // block, - // statement_index: 0, - // }; - // changed |= to_region.add_point(skolemized_end_point); - // } - } else { - stack.extend(successor_points); - } - } - - changed - } -} diff --git a/src/librustc_mir/transform/nll/mod.rs b/src/librustc_mir/transform/nll/mod.rs index fc42fd42b15..273972f6937 100644 --- a/src/librustc_mir/transform/nll/mod.rs +++ b/src/librustc_mir/transform/nll/mod.rs @@ -8,215 +8,115 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use self::infer::InferenceContext; -use rustc::ty::TypeFoldable; -use rustc::ty::subst::{Kind, Substs}; -use rustc::ty::{Ty, TyCtxt, ClosureSubsts, RegionVid, RegionKind}; -use rustc::mir::{Mir, Location, Rvalue, BasicBlock, Statement, StatementKind}; -use rustc::mir::visit::{MutVisitor, Lookup}; +use rustc::ty::{self, RegionKind, TyCtxt}; +use rustc::mir::{Location, Mir}; use rustc::mir::transform::{MirPass, MirSource}; -use rustc::infer::{self as rustc_infer, InferCtxt}; -use rustc::util::nodemap::{FxHashMap, FxHashSet}; -use rustc_data_structures::indexed_vec::{IndexVec, Idx}; -use syntax_pos::DUMMY_SP; -use std::collections::HashMap; +use rustc::infer::InferCtxt; +use rustc::util::nodemap::FxHashMap; +use rustc_data_structures::indexed_vec::Idx; +use std::collections::BTreeSet; use std::fmt; -use util::liveness; +use util::liveness::{self, LivenessResult}; use util as mir_util; use self::mir_util::PassWhere; -mod infer; +mod constraint_generation; -#[allow(dead_code)] -struct NLLVisitor<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> { - lookup_map: HashMap, - regions: IndexVec, - #[allow(dead_code)] - infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, -} +mod region_infer; +use self::region_infer::RegionInferenceContext; -impl<'a, 'gcx, 'tcx> NLLVisitor<'a, 'gcx, 'tcx> { - pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>) -> Self { - NLLVisitor { - infcx, - lookup_map: HashMap::new(), - regions: IndexVec::new(), - } - } +mod renumber; - pub fn into_results(self) -> (HashMap, IndexVec) { - (self.lookup_map, self.regions) - } - - fn renumber_regions(&mut self, value: &T) -> T where T: TypeFoldable<'tcx> { - self.infcx.tcx.fold_regions(value, &mut false, |_region, _depth| { - self.regions.push(Region::default()); - self.infcx.next_region_var(rustc_infer::MiscVariable(DUMMY_SP)) - }) - } +// MIR Pass for non-lexical lifetimes +pub struct NLL; - fn store_region(&mut self, region: &RegionKind, lookup: Lookup) { - if let RegionKind::ReVar(rid) = *region { - self.lookup_map.entry(rid).or_insert(lookup); +impl MirPass for NLL { + fn run_pass<'a, 'tcx>( + &self, + tcx: TyCtxt<'a, 'tcx, 'tcx>, + source: MirSource, + input_mir: &mut Mir<'tcx>, + ) { + if !tcx.sess.opts.debugging_opts.nll { + return; } - } - fn store_ty_regions(&mut self, ty: &Ty<'tcx>, lookup: Lookup) { - for region in ty.regions() { - self.store_region(region, lookup); - } - } + tcx.infer_ctxt().enter(|ref infcx| { + // Clone mir so we can mutate it without disturbing the rest of the compiler + let mir = &mut input_mir.clone(); - fn store_kind_regions(&mut self, kind: &'tcx Kind, lookup: Lookup) { - if let Some(ty) = kind.as_type() { - self.store_ty_regions(&ty, lookup); - } else if let Some(region) = kind.as_region() { - self.store_region(region, lookup); - } - } -} + // Replace all regions with fresh inference variables. + let num_region_variables = renumber::renumber_mir(infcx, mir); -impl<'a, 'gcx, 'tcx> MutVisitor<'tcx> for NLLVisitor<'a, 'gcx, 'tcx> { - fn visit_ty(&mut self, ty: &mut Ty<'tcx>, lookup: Lookup) { - let old_ty = *ty; - *ty = self.renumber_regions(&old_ty); - self.store_ty_regions(ty, lookup); - } + // Compute what is live where. + let liveness = &liveness::liveness_of_locals(mir); - fn visit_substs(&mut self, substs: &mut &'tcx Substs<'tcx>, location: Location) { - *substs = self.renumber_regions(&{*substs}); - let lookup = Lookup::Loc(location); - for kind in *substs { - self.store_kind_regions(kind, lookup); - } - } + // Create the region inference context, generate the constraints, + // and then solve them. + let regioncx = &mut RegionInferenceContext::new(num_region_variables); + constraint_generation::generate_constraints(infcx, regioncx, mir, liveness); + regioncx.solve(infcx, mir); - fn visit_rvalue(&mut self, rvalue: &mut Rvalue<'tcx>, location: Location) { - match *rvalue { - Rvalue::Ref(ref mut r, _, _) => { - let old_r = *r; - *r = self.renumber_regions(&old_r); - let lookup = Lookup::Loc(location); - self.store_region(r, lookup); - } - Rvalue::Use(..) | - Rvalue::Repeat(..) | - Rvalue::Len(..) | - Rvalue::Cast(..) | - Rvalue::BinaryOp(..) | - Rvalue::CheckedBinaryOp(..) | - Rvalue::UnaryOp(..) | - Rvalue::Discriminant(..) | - Rvalue::NullaryOp(..) | - Rvalue::Aggregate(..) => { - // These variants don't contain regions. - } - } - self.super_rvalue(rvalue, location); + // Dump MIR results into a file, if that is enabled. + dump_mir_results(infcx, liveness, source, regioncx, mir); + }) } +} - fn visit_closure_substs(&mut self, - substs: &mut ClosureSubsts<'tcx>, - location: Location) { - *substs = self.renumber_regions(substs); - let lookup = Lookup::Loc(location); - for kind in substs.substs { - self.store_kind_regions(kind, lookup); - } +fn dump_mir_results<'a, 'gcx, 'tcx>( + infcx: &InferCtxt<'a, 'gcx, 'tcx>, + liveness: &LivenessResult, + source: MirSource, + regioncx: &RegionInferenceContext, + mir: &Mir<'tcx>, +) { + if !mir_util::dump_enabled(infcx.tcx, "nll", source) { + return; } - fn visit_statement(&mut self, - block: BasicBlock, - statement: &mut Statement<'tcx>, - location: Location) { - if let StatementKind::EndRegion(_) = statement.kind { - statement.kind = StatementKind::Nop; - } - self.super_statement(block, statement, location); - } -} + let liveness_per_location: FxHashMap<_, _> = mir.basic_blocks() + .indices() + .flat_map(|bb| { + let mut results = vec![]; + liveness.simulate_block(&mir, bb, |location, local_set| { + results.push((location, local_set.clone())); + }); + results + }) + .collect(); + + mir_util::dump_mir(infcx.tcx, None, "nll", &0, source, mir, |pass_where, out| { + match pass_where { + // Before the CFG, dump out the values for each region variable. + PassWhere::BeforeCFG => for region in regioncx.regions() { + writeln!(out, "| {:?}: {:?}", region, regioncx.region_value(region))?; + }, + + // Before each basic block, dump out the values + // that are live on entry to the basic block. + PassWhere::BeforeBlock(bb) => { + let local_set = &liveness.ins[bb]; + writeln!(out, " | Variables live on entry to the block {:?}:", bb)?; + for local in local_set.iter() { + writeln!(out, " | - {:?}", local)?; + } + } -// MIR Pass for non-lexical lifetimes -pub struct NLL; + PassWhere::InCFG(location) => { + let local_set = &liveness_per_location[&location]; + writeln!(out, " | Live variables here: {:?}", local_set)?; + } -impl MirPass for NLL { - fn run_pass<'a, 'tcx>(&self, - tcx: TyCtxt<'a, 'tcx, 'tcx>, - source: MirSource, - input_mir: &mut Mir<'tcx>) { - if !tcx.sess.opts.debugging_opts.nll { - return; + PassWhere::AfterCFG => {} } - - tcx.infer_ctxt().enter(|infcx| { - // Clone mir so we can mutate it without disturbing the rest of the compiler - let mir = &mut input_mir.clone(); - - let mut visitor = NLLVisitor::new(&infcx); - visitor.visit_mir(mir); - - let liveness = liveness::liveness_of_locals(mir); - - let liveness_per_location: FxHashMap<_, _> = - mir - .basic_blocks() - .indices() - .flat_map(|bb| { - let mut results = vec![]; - liveness.simulate_block(&mir, bb, |location, local_set| { - results.push((location, local_set.clone())); - }); - results - }) - .collect(); - - mir_util::dump_mir(infcx.tcx, None, "nll", &0, source, mir, |pass_where, out| { - match pass_where { - // Before the CFG, dump out the values for each region variable. - PassWhere::BeforeCFG => { - for (index, value) in visitor.regions.iter_enumerated() { - writeln!(out, "| R{:03}: {:?}", index.0, value)?; - } - } - - // Before each basic block, dump out the values - // that are live on entry to the basic block. - PassWhere::BeforeBlock(bb) => { - let local_set = &liveness.ins[bb]; - writeln!(out, " | Variables live on entry to the block {:?}:", bb)?; - for local in local_set.iter() { - writeln!(out, " | - {:?}", local)?; - } - } - - PassWhere::InCFG(location) => { - let local_set = &liveness_per_location[&location]; - let mut string = String::new(); - for local in local_set.iter() { - string.push_str(&format!(", {:?}", local)); - } - if !string.is_empty() { - writeln!(out, " | Live variables here: [{}]", &string[2..])?; - } else { - writeln!(out, " | Live variables here: []")?; - } - } - - PassWhere::AfterCFG => { } - } - Ok(()) - }); - let (_lookup_map, regions) = visitor.into_results(); - let mut inference_context = InferenceContext::new(regions); - inference_context.solve(&infcx, mir); - }) - } + Ok(()) + }); } #[derive(Clone, Default, PartialEq, Eq)] pub struct Region { - points: FxHashSet, + points: BTreeSet, } impl fmt::Debug for Region { @@ -235,4 +135,25 @@ impl Region { } } -newtype_index!(RegionIndex); +newtype_index!(RegionIndex { + DEBUG_NAME = "R", +}); + +/// Right now, we piggy back on the `ReVar` to store our NLL inference +/// regions. These are indexed with `RegionIndex`. This method will +/// assert that the region is a `ReVar` and convert the internal index +/// into a `RegionIndex`. This is reasonable because in our MIR we +/// replace all free regions with inference variables. +trait ToRegionIndex { + fn to_region_index(&self) -> RegionIndex; +} + +impl ToRegionIndex for RegionKind { + fn to_region_index(&self) -> RegionIndex { + if let &ty::ReVar(vid) = self { + RegionIndex::new(vid.index as usize) + } else { + bug!("region is not an ReVar: {:?}", self) + } + } +} diff --git a/src/librustc_mir/transform/nll/region_infer.rs b/src/librustc_mir/transform/nll/region_infer.rs new file mode 100644 index 00000000000..75abd4d3ff5 --- /dev/null +++ b/src/librustc_mir/transform/nll/region_infer.rs @@ -0,0 +1,225 @@ +// 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 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use super::{Region, RegionIndex}; +use std::mem; +use rustc::infer::InferCtxt; +use rustc::mir::{Location, Mir}; +use rustc_data_structures::indexed_vec::{Idx, IndexVec}; +use rustc_data_structures::fx::FxHashSet; + +pub struct RegionInferenceContext { + definitions: IndexVec, + constraints: IndexVec, + errors: IndexVec, +} + +pub struct InferenceError { + pub constraint_point: Location, + pub name: (), // FIXME(nashenas88) RegionName +} + +newtype_index!(InferenceErrorIndex); + +#[derive(Default)] +struct VarDefinition { + name: (), // FIXME(nashenas88) RegionName + value: Region, + capped: bool, +} + +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +pub struct Constraint { + sub: RegionIndex, + sup: RegionIndex, + point: Location, +} + +newtype_index!(ConstraintIndex); + +impl RegionInferenceContext { + pub fn new(num_region_variables: usize) -> Self { + Self { + definitions: (0..num_region_variables) + .map(|_| VarDefinition::default()) + .collect(), + constraints: IndexVec::new(), + errors: IndexVec::new(), + } + } + + #[allow(dead_code)] + pub fn cap_var(&mut self, v: RegionIndex) { + self.definitions[v].capped = true; + } + + #[allow(dead_code)] + pub fn add_live_point(&mut self, v: RegionIndex, point: Location) { + debug!("add_live_point({:?}, {:?})", v, point); + let definition = &mut self.definitions[v]; + if definition.value.add_point(point) { + if definition.capped { + self.errors.push(InferenceError { + constraint_point: point, + name: definition.name, + }); + } + } + } + + #[allow(dead_code)] + pub fn add_outlives(&mut self, sup: RegionIndex, sub: RegionIndex, point: Location) { + debug!("add_outlives({:?}: {:?} @ {:?}", sup, sub, point); + self.constraints.push(Constraint { sup, sub, point }); + } + + /// Returns an iterator over all the region indices. + pub fn regions(&self) -> impl Iterator { + self.definitions.indices() + } + + /// Returns the current value for the region `v`. This is only + /// really meaningful after `solve` has executed. + pub fn region_value(&self, v: RegionIndex) -> &Region { + &self.definitions[v].value + } + + pub fn solve<'a, 'gcx, 'tcx>( + &mut self, + infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, + mir: &'a Mir<'tcx>, + ) -> IndexVec + where + 'gcx: 'tcx + 'a, + 'tcx: 'a, + { + let mut changed = true; + let mut dfs = Dfs::new(infcx, mir); + while changed { + changed = false; + for constraint in &self.constraints { + let sub = &self.definitions[constraint.sub].value.clone(); + let sup_def = &mut self.definitions[constraint.sup]; + debug!("constraint: {:?}", constraint); + debug!(" sub (before): {:?}", sub); + debug!(" sup (before): {:?}", sup_def.value); + + if dfs.copy(sub, &mut sup_def.value, constraint.point) { + changed = true; + if sup_def.capped { + // This is kind of a hack, but when we add a + // constraint, the "point" is always the point + // AFTER the action that induced the + // constraint. So report the error on the + // action BEFORE that. + assert!(constraint.point.statement_index > 0); + let p = Location { + block: constraint.point.block, + statement_index: constraint.point.statement_index - 1, + }; + + self.errors.push(InferenceError { + constraint_point: p, + name: sup_def.name, + }); + } + } + + debug!(" sup (after) : {:?}", sup_def.value); + debug!(" changed : {:?}", changed); + } + debug!("\n"); + } + + mem::replace(&mut self.errors, IndexVec::new()) + } +} + +struct Dfs<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> { + #[allow(dead_code)] infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, + mir: &'a Mir<'tcx>, +} + +impl<'a, 'gcx: 'tcx, 'tcx: 'a> Dfs<'a, 'gcx, 'tcx> { + fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, mir: &'a Mir<'tcx>) -> Self { + Self { infcx, mir } + } + + fn copy( + &mut self, + from_region: &Region, + to_region: &mut Region, + start_point: Location, + ) -> bool { + let mut changed = false; + + let mut stack = vec![]; + let mut visited = FxHashSet(); + + stack.push(start_point); + while let Some(p) = stack.pop() { + debug!(" dfs: p={:?}", p); + + if !from_region.may_contain(p) { + debug!(" not in from-region"); + continue; + } + + if !visited.insert(p) { + debug!(" already visited"); + continue; + } + + changed |= to_region.add_point(p); + + let block_data = &self.mir[p.block]; + let successor_points = if p.statement_index < block_data.statements.len() { + vec![ + Location { + statement_index: p.statement_index + 1, + ..p + }, + ] + } else { + block_data + .terminator() + .successors() + .iter() + .map(|&basic_block| { + Location { + statement_index: 0, + block: basic_block, + } + }) + .collect::>() + }; + + if successor_points.is_empty() { + // FIXME handle free regions + // If we reach the END point in the graph, then copy + // over any skolemized end points in the `from_region` + // and make sure they are included in the `to_region`. + // for region_decl in self.infcx.tcx.tables.borrow().free_region_map() { + // // FIXME(nashenas88) figure out skolemized_end points + // let block = self.env.graph.skolemized_end(region_decl.name); + // let skolemized_end_point = Location { + // block, + // statement_index: 0, + // }; + // changed |= to_region.add_point(skolemized_end_point); + // } + } else { + stack.extend(successor_points); + } + } + + changed + } +} diff --git a/src/librustc_mir/transform/nll/renumber.rs b/src/librustc_mir/transform/nll/renumber.rs new file mode 100644 index 00000000000..589179c2066 --- /dev/null +++ b/src/librustc_mir/transform/nll/renumber.rs @@ -0,0 +1,132 @@ +// 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 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc::ty::TypeFoldable; +use rustc::ty::subst::{Kind, Substs}; +use rustc::ty::{Ty, ClosureSubsts, RegionVid, RegionKind}; +use rustc::mir::{Mir, Location, Rvalue, BasicBlock, Statement, StatementKind}; +use rustc::mir::visit::{MutVisitor, Lookup}; +use rustc::infer::{self as rustc_infer, InferCtxt}; +use syntax_pos::DUMMY_SP; +use std::collections::HashMap; + +/// Replaces all free regions appearing in the MIR with fresh +/// inference variables, returning the number of variables created. +pub fn renumber_mir<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>, + mir: &mut Mir<'tcx>) + -> usize +{ + let mut visitor = NLLVisitor::new(infcx); + visitor.visit_mir(mir); + visitor.num_region_variables +} + +struct NLLVisitor<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> { + lookup_map: HashMap, + num_region_variables: usize, + infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, +} + +impl<'a, 'gcx, 'tcx> NLLVisitor<'a, 'gcx, 'tcx> { + pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>) -> Self { + NLLVisitor { + infcx, + lookup_map: HashMap::new(), + num_region_variables: 0 + } + } + + fn renumber_regions(&mut self, value: &T) -> T where T: TypeFoldable<'tcx> { + self.infcx.tcx.fold_regions(value, &mut false, |_region, _depth| { + self.num_region_variables += 1; + self.infcx.next_region_var(rustc_infer::MiscVariable(DUMMY_SP)) + }) + } + + fn store_region(&mut self, region: &RegionKind, lookup: Lookup) { + if let RegionKind::ReVar(rid) = *region { + self.lookup_map.entry(rid).or_insert(lookup); + } + } + + fn store_ty_regions(&mut self, ty: &Ty<'tcx>, lookup: Lookup) { + for region in ty.regions() { + self.store_region(region, lookup); + } + } + + fn store_kind_regions(&mut self, kind: &'tcx Kind, lookup: Lookup) { + if let Some(ty) = kind.as_type() { + self.store_ty_regions(&ty, lookup); + } else if let Some(region) = kind.as_region() { + self.store_region(region, lookup); + } + } +} + +impl<'a, 'gcx, 'tcx> MutVisitor<'tcx> for NLLVisitor<'a, 'gcx, 'tcx> { + fn visit_ty(&mut self, ty: &mut Ty<'tcx>, lookup: Lookup) { + let old_ty = *ty; + *ty = self.renumber_regions(&old_ty); + self.store_ty_regions(ty, lookup); + } + + fn visit_substs(&mut self, substs: &mut &'tcx Substs<'tcx>, location: Location) { + *substs = self.renumber_regions(&{*substs}); + let lookup = Lookup::Loc(location); + for kind in *substs { + self.store_kind_regions(kind, lookup); + } + } + + fn visit_rvalue(&mut self, rvalue: &mut Rvalue<'tcx>, location: Location) { + match *rvalue { + Rvalue::Ref(ref mut r, _, _) => { + let old_r = *r; + *r = self.renumber_regions(&old_r); + let lookup = Lookup::Loc(location); + self.store_region(r, lookup); + } + Rvalue::Use(..) | + Rvalue::Repeat(..) | + Rvalue::Len(..) | + Rvalue::Cast(..) | + Rvalue::BinaryOp(..) | + Rvalue::CheckedBinaryOp(..) | + Rvalue::UnaryOp(..) | + Rvalue::Discriminant(..) | + Rvalue::NullaryOp(..) | + Rvalue::Aggregate(..) => { + // These variants don't contain regions. + } + } + self.super_rvalue(rvalue, location); + } + + fn visit_closure_substs(&mut self, + substs: &mut ClosureSubsts<'tcx>, + location: Location) { + *substs = self.renumber_regions(substs); + let lookup = Lookup::Loc(location); + for kind in substs.substs { + self.store_kind_regions(kind, lookup); + } + } + + fn visit_statement(&mut self, + block: BasicBlock, + statement: &mut Statement<'tcx>, + location: Location) { + if let StatementKind::EndRegion(_) = statement.kind { + statement.kind = StatementKind::Nop; + } + self.super_statement(block, statement, location); + } +} diff --git a/src/test/mir-opt/nll/region-liveness-basic.rs b/src/test/mir-opt/nll/region-liveness-basic.rs new file mode 100644 index 00000000000..d1ef08cf00d --- /dev/null +++ b/src/test/mir-opt/nll/region-liveness-basic.rs @@ -0,0 +1,55 @@ +// Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// Basic test for liveness constraints: the region (`R1`) that appears +// in the type of `p` includes the points after `&v[0]` up to (but not +// including) the call to `use_x`. The `else` branch is not included. + +// compile-flags:-Znll -Zverbose +// ^^^^^^^^^ force compiler to dump more region information + +#![allow(warnings)] + +fn use_x(_: usize) -> bool { true } + +fn main() { + let mut v = [1, 2, 3]; + let p = &v[0]; + if true { + use_x(*p); + } else { + use_x(22); + } +} + +// END RUST SOURCE +// START rustc.node12.nll.0.mir +// | R1: {bb1[1], bb2[0], bb2[1]} +// ... +// let _2: &'_#1r usize; +// END rustc.node12.nll.0.mir +// START rustc.node12.nll.0.mir +// bb1: { +// | Live variables here: [_1, _3] +// _2 = &'_#0r _1[_3]; +// | Live variables here: [_2] +// switchInt(const true) -> [0u8: bb3, otherwise: bb2]; +// } +// END rustc.node12.nll.0.mir +// START rustc.node12.nll.0.mir +// bb2: { +// | Live variables here: [_2] +// StorageLive(_7); +// | Live variables here: [_2] +// _7 = (*_2); +// | Live variables here: [_7] +// _6 = const use_x(_7) -> bb4; +// } +// END rustc.node12.nll.0.mir -- cgit 1.4.1-3-g733a5