diff options
| -rw-r--r-- | compiler/rustc_borrowck/src/dataflow.rs | 101 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/nll.rs | 10 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/polonius/loan_liveness.rs | 270 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/polonius/mod.rs | 31 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/mod.rs | 37 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/region_infer/values.rs | 57 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/type_check/liveness/mod.rs | 18 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/type_check/liveness/trace.rs | 33 | ||||
| -rw-r--r-- | tests/crashes/127628.rs | 14 |
9 files changed, 386 insertions, 185 deletions
diff --git a/compiler/rustc_borrowck/src/dataflow.rs b/compiler/rustc_borrowck/src/dataflow.rs index a7a6f2da509..7511a55b03a 100644 --- a/compiler/rustc_borrowck/src/dataflow.rs +++ b/compiler/rustc_borrowck/src/dataflow.rs @@ -187,19 +187,28 @@ struct OutOfScopePrecomputer<'a, 'tcx> { borrows_out_of_scope_at_location: FxIndexMap<Location, Vec<BorrowIndex>>, } -impl<'a, 'tcx> OutOfScopePrecomputer<'a, 'tcx> { - fn new(body: &'a Body<'tcx>, regioncx: &'a RegionInferenceContext<'tcx>) -> Self { - OutOfScopePrecomputer { +impl<'tcx> OutOfScopePrecomputer<'_, 'tcx> { + fn compute( + body: &Body<'tcx>, + regioncx: &RegionInferenceContext<'tcx>, + borrow_set: &BorrowSet<'tcx>, + ) -> FxIndexMap<Location, Vec<BorrowIndex>> { + let mut prec = OutOfScopePrecomputer { visited: DenseBitSet::new_empty(body.basic_blocks.len()), visit_stack: vec![], body, regioncx, borrows_out_of_scope_at_location: FxIndexMap::default(), + }; + for (borrow_index, borrow_data) in borrow_set.iter_enumerated() { + let borrow_region = borrow_data.region; + let location = borrow_data.reserve_location; + prec.precompute_borrows_out_of_scope(borrow_index, borrow_region, location); } + + prec.borrows_out_of_scope_at_location } -} -impl<'tcx> OutOfScopePrecomputer<'_, 'tcx> { fn precompute_borrows_out_of_scope( &mut self, borrow_index: BorrowIndex, @@ -280,15 +289,7 @@ pub fn calculate_borrows_out_of_scope_at_location<'tcx>( regioncx: &RegionInferenceContext<'tcx>, borrow_set: &BorrowSet<'tcx>, ) -> FxIndexMap<Location, Vec<BorrowIndex>> { - let mut prec = OutOfScopePrecomputer::new(body, regioncx); - for (borrow_index, borrow_data) in borrow_set.iter_enumerated() { - let borrow_region = borrow_data.region; - let location = borrow_data.reserve_location; - - prec.precompute_borrows_out_of_scope(borrow_index, borrow_region, location); - } - - prec.borrows_out_of_scope_at_location + OutOfScopePrecomputer::compute(body, regioncx, borrow_set) } struct PoloniusOutOfScopePrecomputer<'a, 'tcx> { @@ -300,19 +301,30 @@ struct PoloniusOutOfScopePrecomputer<'a, 'tcx> { loans_out_of_scope_at_location: FxIndexMap<Location, Vec<BorrowIndex>>, } -impl<'a, 'tcx> PoloniusOutOfScopePrecomputer<'a, 'tcx> { - fn new(body: &'a Body<'tcx>, regioncx: &'a RegionInferenceContext<'tcx>) -> Self { - Self { +impl<'tcx> PoloniusOutOfScopePrecomputer<'_, 'tcx> { + fn compute( + body: &Body<'tcx>, + regioncx: &RegionInferenceContext<'tcx>, + borrow_set: &BorrowSet<'tcx>, + ) -> FxIndexMap<Location, Vec<BorrowIndex>> { + // The in-tree polonius analysis computes loans going out of scope using the + // set-of-loans model. + let mut prec = PoloniusOutOfScopePrecomputer { visited: DenseBitSet::new_empty(body.basic_blocks.len()), visit_stack: vec![], body, regioncx, loans_out_of_scope_at_location: FxIndexMap::default(), + }; + for (loan_idx, loan_data) in borrow_set.iter_enumerated() { + let issuing_region = loan_data.region; + let loan_issued_at = loan_data.reserve_location; + prec.precompute_loans_out_of_scope(loan_idx, issuing_region, loan_issued_at); } + + prec.loans_out_of_scope_at_location } -} -impl<'tcx> PoloniusOutOfScopePrecomputer<'_, 'tcx> { /// Loans are in scope while they are live: whether they are contained within any live region. /// In the location-insensitive analysis, a loan will be contained in a region if the issuing /// region can reach it in the subset graph. So this is a reachability problem. @@ -325,10 +337,17 @@ impl<'tcx> PoloniusOutOfScopePrecomputer<'_, 'tcx> { let sccs = self.regioncx.constraint_sccs(); let universal_regions = self.regioncx.universal_regions(); + // The loop below was useful for the location-insensitive analysis but shouldn't be + // impactful in the location-sensitive case. It seems that it does, however, as without it a + // handful of tests fail. That likely means some liveness or outlives data related to choice + // regions is missing + // FIXME: investigate the impact of loans traversing applied member constraints and why some + // tests fail otherwise. + // // We first handle the cases where the loan doesn't go out of scope, depending on the // issuing region's successors. for successor in graph::depth_first_search(&self.regioncx.region_graph(), issuing_region) { - // 1. Via applied member constraints + // Via applied member constraints // // The issuing region can flow into the choice regions, and they are either: // - placeholders or free regions themselves, @@ -346,14 +365,6 @@ impl<'tcx> PoloniusOutOfScopePrecomputer<'_, 'tcx> { return; } } - - // 2. Via regions that are live at all points: placeholders and free regions. - // - // If the issuing region outlives such a region, its loan escapes the function and - // cannot go out of scope. We can early return. - if self.regioncx.is_region_live_at_all_points(successor) { - return; - } } let first_block = loan_issued_at.block; @@ -461,34 +472,12 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> { regioncx: &RegionInferenceContext<'tcx>, borrow_set: &'a BorrowSet<'tcx>, ) -> Self { - let mut borrows_out_of_scope_at_location = - calculate_borrows_out_of_scope_at_location(body, regioncx, borrow_set); - - // The in-tree polonius analysis computes loans going out of scope using the set-of-loans - // model, and makes sure they're identical to the existing computation of the set-of-points - // model. - if tcx.sess.opts.unstable_opts.polonius.is_next_enabled() { - let mut polonius_prec = PoloniusOutOfScopePrecomputer::new(body, regioncx); - for (loan_idx, loan_data) in borrow_set.iter_enumerated() { - let issuing_region = loan_data.region; - let loan_issued_at = loan_data.reserve_location; - - polonius_prec.precompute_loans_out_of_scope( - loan_idx, - issuing_region, - loan_issued_at, - ); - } - - assert_eq!( - borrows_out_of_scope_at_location, polonius_prec.loans_out_of_scope_at_location, - "polonius loan scopes differ from NLL borrow scopes, for body {:?}", - body.span, - ); - - borrows_out_of_scope_at_location = polonius_prec.loans_out_of_scope_at_location; - } - + let borrows_out_of_scope_at_location = + if !tcx.sess.opts.unstable_opts.polonius.is_next_enabled() { + calculate_borrows_out_of_scope_at_location(body, regioncx, borrow_set) + } else { + PoloniusOutOfScopePrecomputer::compute(body, regioncx, borrow_set) + }; Borrows { tcx, body, borrow_set, borrows_out_of_scope_at_location } } diff --git a/compiler/rustc_borrowck/src/nll.rs b/compiler/rustc_borrowck/src/nll.rs index aa0bfd72147..35264bd1a70 100644 --- a/compiler/rustc_borrowck/src/nll.rs +++ b/compiler/rustc_borrowck/src/nll.rs @@ -103,7 +103,7 @@ pub(crate) fn compute_regions<'a, 'tcx>( constraints, universal_region_relations, opaque_type_values, - mut polonius_context, + polonius_context, } = type_check::type_check( infcx, body, @@ -142,10 +142,10 @@ pub(crate) fn compute_regions<'a, 'tcx>( location_map, ); - // If requested for `-Zpolonius=next`, convert NLL constraints to localized outlives - // constraints. - let localized_outlives_constraints = polonius_context.as_mut().map(|polonius_context| { - polonius_context.create_localized_constraints(infcx.tcx, ®ioncx, body) + // If requested for `-Zpolonius=next`, convert NLL constraints to localized outlives constraints + // and use them to compute loan liveness. + let localized_outlives_constraints = polonius_context.as_ref().map(|polonius_context| { + polonius_context.compute_loan_liveness(infcx.tcx, &mut regioncx, body, borrow_set) }); // If requested: dump NLL facts, and run legacy polonius analysis. diff --git a/compiler/rustc_borrowck/src/polonius/loan_liveness.rs b/compiler/rustc_borrowck/src/polonius/loan_liveness.rs new file mode 100644 index 00000000000..c519453652f --- /dev/null +++ b/compiler/rustc_borrowck/src/polonius/loan_liveness.rs @@ -0,0 +1,270 @@ +use std::collections::{BTreeMap, BTreeSet}; + +use rustc_data_structures::fx::{FxHashMap, FxHashSet, FxIndexSet}; +use rustc_middle::mir::visit::Visitor; +use rustc_middle::mir::{ + Body, Local, Location, Place, Rvalue, Statement, StatementKind, Terminator, TerminatorKind, +}; +use rustc_middle::ty::{RegionVid, TyCtxt}; +use rustc_mir_dataflow::points::PointIndex; + +use super::{LiveLoans, LocalizedOutlivesConstraintSet}; +use crate::dataflow::BorrowIndex; +use crate::region_infer::values::LivenessValues; +use crate::{BorrowSet, PlaceConflictBias, places_conflict}; + +/// With the full graph of constraints, we can compute loan reachability, stop at kills, and trace +/// loan liveness throughout the CFG. +pub(super) fn compute_loan_liveness<'tcx>( + tcx: TyCtxt<'tcx>, + body: &Body<'tcx>, + liveness: &LivenessValues, + borrow_set: &BorrowSet<'tcx>, + localized_outlives_constraints: &LocalizedOutlivesConstraintSet, +) -> LiveLoans { + let mut live_loans = LiveLoans::new(borrow_set.len()); + + // FIXME: it may be preferable for kills to be encoded in the edges themselves, to simplify and + // likely make traversal (and constraint generation) more efficient. We also display kills on + // edges when visualizing the constraint graph anyways. + let kills = collect_kills(body, tcx, borrow_set); + + let graph = index_constraints(&localized_outlives_constraints); + let mut visited = FxHashSet::default(); + let mut stack = Vec::new(); + + // Compute reachability per loan by traversing each loan's subgraph starting from where it is + // introduced. + for (loan_idx, loan) in borrow_set.iter_enumerated() { + visited.clear(); + stack.clear(); + + let start_node = LocalizedNode { + region: loan.region, + point: liveness.point_from_location(loan.reserve_location), + }; + stack.push(start_node); + + while let Some(node) = stack.pop() { + if !visited.insert(node) { + continue; + } + + // Record the loan as being live on entry to this point. + live_loans.insert(node.point, loan_idx); + + // Here, we have a conundrum. There's currently a weakness in our theory, in that + // we're using a single notion of reachability to represent what used to be _two_ + // different transitive closures. It didn't seem impactful when coming up with the + // single-graph and reachability through space (regions) + time (CFG) concepts, but in + // practice the combination of time-traveling with kills is more impactful than + // initially anticipated. + // + // Kills should prevent a loan from reaching its successor points in the CFG, but not + // while time-traveling: we're not actually at that CFG point, but looking for + // predecessor regions that contain the loan. One of the two TCs we had pushed the + // transitive subset edges to each point instead of having backward edges, and the + // problem didn't exist before. In the abstract, naive reachability is not enough to + // model this, we'd need a slightly different solution. For example, maybe with a + // two-step traversal: + // - at each point we first traverse the subgraph (and possibly time-travel) looking for + // exit nodes while ignoring kills, + // - and then when we're back at the current point, we continue normally. + // + // Another (less annoying) subtlety is that kills and the loan use-map are + // flow-insensitive. Kills can actually appear in places before a loan is introduced, or + // at a location that is actually unreachable in the CFG from the introduction point, + // and these can also be encountered during time-traveling. + // + // The simplest change that made sense to "fix" the issues above is taking into + // account kills that are: + // - reachable from the introduction point + // - encountered during forward traversal. Note that this is not transitive like the + // two-step traversal described above: only kills encountered on exit via a backward + // edge are ignored. + // + // In our test suite, there are a couple of cases where kills are encountered while + // time-traveling, however as far as we can tell, always in cases where they would be + // unreachable. We have reason to believe that this is a property of the single-graph + // approach (but haven't proved it yet): + // - reachable kills while time-traveling would also be encountered via regular + // traversal + // - it makes _some_ sense to ignore unreachable kills, but subtleties around dead code + // in general need to be better thought through (like they were for NLLs). + // - ignoring kills is a conservative approximation: the loan is still live and could + // cause false positive errors at another place access. Soundness issues in this + // domain should look more like the absence of reachability instead. + // + // This is enough in practice to pass tests, and therefore is what we have implemented + // for now. + // + // FIXME: all of the above. Analyze potential unsoundness, possibly in concert with a + // borrowck implementation in a-mir-formality, fuzzing, or manually crafting + // counter-examples. + + // Continuing traversal will depend on whether the loan is killed at this point, and + // whether we're time-traveling. + let current_location = liveness.location_from_point(node.point); + let is_loan_killed = + kills.get(¤t_location).is_some_and(|kills| kills.contains(&loan_idx)); + + for succ in outgoing_edges(&graph, node) { + // If the loan is killed at this point, it is killed _on exit_. But only during + // forward traversal. + if is_loan_killed { + let destination = liveness.location_from_point(succ.point); + if current_location.is_predecessor_of(destination, body) { + continue; + } + } + stack.push(succ); + } + } + } + + live_loans +} + +/// The localized constraint graph is currently the per-node map of its physical edges. In the +/// future, we'll add logical edges to model constraints that hold at all points in the CFG. +type LocalizedConstraintGraph = FxHashMap<LocalizedNode, FxIndexSet<LocalizedNode>>; + +/// A node in the graph to be traversed, one of the two vertices of a localized outlives constraint. +#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] +struct LocalizedNode { + region: RegionVid, + point: PointIndex, +} + +/// Traverses the constraints and returns the indexable graph of edges per node. +fn index_constraints(constraints: &LocalizedOutlivesConstraintSet) -> LocalizedConstraintGraph { + let mut edges = LocalizedConstraintGraph::default(); + for constraint in &constraints.outlives { + let source = LocalizedNode { region: constraint.source, point: constraint.from }; + let target = LocalizedNode { region: constraint.target, point: constraint.to }; + edges.entry(source).or_default().insert(target); + } + + edges +} + +/// Returns the outgoing edges of a given node, not its transitive closure. +fn outgoing_edges( + graph: &LocalizedConstraintGraph, + node: LocalizedNode, +) -> impl Iterator<Item = LocalizedNode> + use<'_> { + graph.get(&node).into_iter().flat_map(|edges| edges.iter().copied()) +} + +/// Traverses the MIR and collects kills. +fn collect_kills<'tcx>( + body: &Body<'tcx>, + tcx: TyCtxt<'tcx>, + borrow_set: &BorrowSet<'tcx>, +) -> BTreeMap<Location, BTreeSet<BorrowIndex>> { + let mut collector = KillsCollector { borrow_set, tcx, body, kills: BTreeMap::default() }; + for (block, data) in body.basic_blocks.iter_enumerated() { + collector.visit_basic_block_data(block, data); + } + collector.kills +} + +struct KillsCollector<'a, 'tcx> { + body: &'a Body<'tcx>, + tcx: TyCtxt<'tcx>, + borrow_set: &'a BorrowSet<'tcx>, + + /// The set of loans killed at each location. + kills: BTreeMap<Location, BTreeSet<BorrowIndex>>, +} + +// This visitor has a similar structure to the `Borrows` dataflow computation with respect to kills, +// and the datalog polonius fact generation for the `loan_killed_at` relation. +impl<'tcx> KillsCollector<'_, 'tcx> { + /// Records the borrows on the specified place as `killed`. For example, when assigning to a + /// local, or on a call's return destination. + fn record_killed_borrows_for_place(&mut self, place: Place<'tcx>, location: Location) { + // For the reasons described in graph traversal, we also filter out kills + // unreachable from the loan's introduction point, as they would stop traversal when + // e.g. checking for reachability in the subset graph through invariance constraints + // higher up. + let filter_unreachable_kills = |loan| { + let introduction = self.borrow_set[loan].reserve_location; + let reachable = introduction.is_predecessor_of(location, self.body); + reachable + }; + + let other_borrows_of_local = self + .borrow_set + .local_map + .get(&place.local) + .into_iter() + .flat_map(|bs| bs.iter()) + .copied(); + + // If the borrowed place is a local with no projections, all other borrows of this + // local must conflict. This is purely an optimization so we don't have to call + // `places_conflict` for every borrow. + if place.projection.is_empty() { + if !self.body.local_decls[place.local].is_ref_to_static() { + self.kills + .entry(location) + .or_default() + .extend(other_borrows_of_local.filter(|&loan| filter_unreachable_kills(loan))); + } + return; + } + + // By passing `PlaceConflictBias::NoOverlap`, we conservatively assume that any given + // pair of array indices are not equal, so that when `places_conflict` returns true, we + // will be assured that two places being compared definitely denotes the same sets of + // locations. + let definitely_conflicting_borrows = other_borrows_of_local + .filter(|&i| { + places_conflict( + self.tcx, + self.body, + self.borrow_set[i].borrowed_place, + place, + PlaceConflictBias::NoOverlap, + ) + }) + .filter(|&loan| filter_unreachable_kills(loan)); + + self.kills.entry(location).or_default().extend(definitely_conflicting_borrows); + } + + /// Records the borrows on the specified local as `killed`. + fn record_killed_borrows_for_local(&mut self, local: Local, location: Location) { + if let Some(borrow_indices) = self.borrow_set.local_map.get(&local) { + self.kills.entry(location).or_default().extend(borrow_indices.iter()); + } + } +} + +impl<'tcx> Visitor<'tcx> for KillsCollector<'_, 'tcx> { + fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) { + // Make sure there are no remaining borrows for locals that have gone out of scope. + if let StatementKind::StorageDead(local) = statement.kind { + self.record_killed_borrows_for_local(local, location); + } + + self.super_statement(statement, location); + } + + fn visit_assign(&mut self, place: &Place<'tcx>, rvalue: &Rvalue<'tcx>, location: Location) { + // When we see `X = ...`, then kill borrows of `(*X).foo` and so forth. + self.record_killed_borrows_for_place(*place, location); + self.super_assign(place, rvalue, location); + } + + fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) { + // A `Call` terminator's return value can be a local which has borrows, so we need to record + // those as killed as well. + if let TerminatorKind::Call { destination, .. } = terminator.kind { + self.record_killed_borrows_for_place(destination, location); + } + + self.super_terminator(terminator, location); + } +} diff --git a/compiler/rustc_borrowck/src/polonius/mod.rs b/compiler/rustc_borrowck/src/polonius/mod.rs index 7d0f9397021..52a5f75d8a2 100644 --- a/compiler/rustc_borrowck/src/polonius/mod.rs +++ b/compiler/rustc_borrowck/src/polonius/mod.rs @@ -37,6 +37,7 @@ mod constraints; mod dump; pub(crate) mod legacy; mod liveness_constraints; +mod loan_liveness; mod typeck_constraints; use std::collections::BTreeMap; @@ -49,8 +50,12 @@ use rustc_mir_dataflow::points::PointIndex; pub(crate) use self::constraints::*; pub(crate) use self::dump::dump_polonius_mir; use self::liveness_constraints::create_liveness_constraints; +use self::loan_liveness::compute_loan_liveness; use self::typeck_constraints::convert_typeck_constraints; -use crate::RegionInferenceContext; +use crate::dataflow::BorrowIndex; +use crate::{BorrowSet, RegionInferenceContext}; + +pub(crate) type LiveLoans = SparseBitMatrix<PointIndex, BorrowIndex>; /// This struct holds the data needed to create the Polonius localized constraints. pub(crate) struct PoloniusContext { @@ -82,14 +87,20 @@ impl PoloniusContext { Self { live_region_variances: BTreeMap::new(), live_regions: None } } - /// Creates a constraint set for `-Zpolonius=next` by: + /// Computes live loans using the set of loans model for `-Zpolonius=next`. + /// + /// First, creates a constraint graph combining regions and CFG points, by: /// - converting NLL typeck constraints to be localized /// - encoding liveness constraints - pub(crate) fn create_localized_constraints<'tcx>( + /// + /// Then, this graph is traversed, and combined with kills, reachability is recorded as loan + /// liveness, to be used by the loan scope and active loans computations. + pub(crate) fn compute_loan_liveness<'tcx>( &self, tcx: TyCtxt<'tcx>, - regioncx: &RegionInferenceContext<'tcx>, + regioncx: &mut RegionInferenceContext<'tcx>, body: &Body<'tcx>, + borrow_set: &BorrowSet<'tcx>, ) -> LocalizedOutlivesConstraintSet { let mut localized_outlives_constraints = LocalizedOutlivesConstraintSet::default(); convert_typeck_constraints( @@ -113,8 +124,16 @@ impl PoloniusContext { &mut localized_outlives_constraints, ); - // FIXME: here, we can trace loan reachability in the constraint graph and record this as loan - // liveness for the next step in the chain, the NLL loan scope and active loans computations. + // Now that we have a complete graph, we can compute reachability to trace the liveness of + // loans for the next step in the chain, the NLL loan scope and active loans computations. + let live_loans = compute_loan_liveness( + tcx, + body, + regioncx.liveness_constraints(), + borrow_set, + &localized_outlives_constraints, + ); + regioncx.record_live_loans(live_loans); localized_outlives_constraints } diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs index c177538ee17..d2268c4779d 100644 --- a/compiler/rustc_borrowck/src/region_infer/mod.rs +++ b/compiler/rustc_borrowck/src/region_infer/mod.rs @@ -31,6 +31,7 @@ use crate::constraints::{ConstraintSccIndex, OutlivesConstraint, OutlivesConstra use crate::dataflow::BorrowIndex; use crate::diagnostics::{RegionErrorKind, RegionErrors, UniverseInfo}; use crate::member_constraints::{MemberConstraintSet, NllMemberConstraintIndex}; +use crate::polonius::LiveLoans; use crate::polonius::legacy::PoloniusOutput; use crate::region_infer::reverse_sccs::ReverseSccGraph; use crate::region_infer::values::{LivenessValues, RegionElement, RegionValues, ToElementIndex}; @@ -2171,28 +2172,6 @@ impl<'tcx> RegionInferenceContext<'tcx> { self.constraint_graph.region_graph(&self.constraints, self.universal_regions().fr_static) } - /// Returns whether the given region is considered live at all points: whether it is a - /// placeholder or a free region. - pub(crate) fn is_region_live_at_all_points(&self, region: RegionVid) -> bool { - // FIXME: there must be a cleaner way to find this information. At least, when - // higher-ranked subtyping is abstracted away from the borrowck main path, we'll only - // need to check whether this is a universal region. - let origin = self.region_definition(region).origin; - let live_at_all_points = matches!( - origin, - NllRegionVariableOrigin::Placeholder(_) | NllRegionVariableOrigin::FreeRegion - ); - live_at_all_points - } - - /// Returns whether the `loan_idx` is live at the given `location`: whether its issuing - /// region is contained within the type of a variable that is live at this point. - /// Note: for now, the sets of live loans is only available when using `-Zpolonius=next`. - pub(crate) fn is_loan_live_at(&self, loan_idx: BorrowIndex, location: Location) -> bool { - let point = self.liveness_constraints.point_from_location(location); - self.liveness_constraints.is_loan_live_at(loan_idx, point) - } - /// Returns the representative `RegionVid` for a given SCC. /// See `RegionTracker` for how a region variable ID is chosen. /// @@ -2208,6 +2187,20 @@ impl<'tcx> RegionInferenceContext<'tcx> { pub(crate) fn liveness_constraints(&self) -> &LivenessValues { &self.liveness_constraints } + + /// When using `-Zpolonius=next`, records the given live loans for the loan scopes and active + /// loans dataflow computations. + pub(crate) fn record_live_loans(&mut self, live_loans: LiveLoans) { + self.liveness_constraints.record_live_loans(live_loans); + } + + /// Returns whether the `loan_idx` is live at the given `location`: whether its issuing + /// region is contained within the type of a variable that is live at this point. + /// Note: for now, the sets of live loans is only available when using `-Zpolonius=next`. + pub(crate) fn is_loan_live_at(&self, loan_idx: BorrowIndex, location: Location) -> bool { + let point = self.liveness_constraints.point_from_location(location); + self.liveness_constraints.is_loan_live_at(loan_idx, point) + } } impl<'tcx> RegionDefinition<'tcx> { diff --git a/compiler/rustc_borrowck/src/region_infer/values.rs b/compiler/rustc_borrowck/src/region_infer/values.rs index 11fb125ca22..f1bcb353dc6 100644 --- a/compiler/rustc_borrowck/src/region_infer/values.rs +++ b/compiler/rustc_borrowck/src/region_infer/values.rs @@ -11,6 +11,7 @@ use rustc_mir_dataflow::points::{DenseLocationMap, PointIndex}; use tracing::debug; use crate::BorrowIndex; +use crate::polonius::LiveLoans; rustc_index::newtype_index! { /// A single integer representing a `ty::Placeholder`. @@ -50,29 +51,8 @@ pub(crate) struct LivenessValues { /// region is live, only that it is. points: Option<SparseIntervalMatrix<RegionVid, PointIndex>>, - /// When using `-Zpolonius=next`, for each point: the loans flowing into the live regions at - /// that point. - pub(crate) loans: Option<LiveLoans>, -} - -/// Data used to compute the loans that are live at a given point in the CFG, when using -/// `-Zpolonius=next`. -pub(crate) struct LiveLoans { - /// The set of loans that flow into a given region. When individual regions are marked as live - /// in the CFG, these inflowing loans are recorded as live. - pub(crate) inflowing_loans: SparseBitMatrix<RegionVid, BorrowIndex>, - - /// The set of loans that are live at a given point in the CFG. - pub(crate) live_loans: SparseBitMatrix<PointIndex, BorrowIndex>, -} - -impl LiveLoans { - pub(crate) fn new(num_loans: usize) -> Self { - LiveLoans { - live_loans: SparseBitMatrix::new(num_loans), - inflowing_loans: SparseBitMatrix::new(num_loans), - } - } + /// When using `-Zpolonius=next`, the set of loans that are live at a given point in the CFG. + live_loans: Option<LiveLoans>, } impl LivenessValues { @@ -82,7 +62,7 @@ impl LivenessValues { live_regions: None, points: Some(SparseIntervalMatrix::new(location_map.num_points())), location_map, - loans: None, + live_loans: None, } } @@ -95,7 +75,7 @@ impl LivenessValues { live_regions: Some(Default::default()), points: None, location_map, - loans: None, + live_loans: None, } } @@ -129,13 +109,6 @@ impl LivenessValues { } else if self.location_map.point_in_range(point) { self.live_regions.as_mut().unwrap().insert(region); } - - // When available, record the loans flowing into this region as live at the given point. - if let Some(loans) = self.loans.as_mut() { - if let Some(inflowing) = loans.inflowing_loans.row(region) { - loans.live_loans.union_row(point, inflowing); - } - } } /// Records `region` as being live at all the given `points`. @@ -146,17 +119,6 @@ impl LivenessValues { } else if points.iter().any(|point| self.location_map.point_in_range(point)) { self.live_regions.as_mut().unwrap().insert(region); } - - // When available, record the loans flowing into this region as live at the given points. - if let Some(loans) = self.loans.as_mut() { - if let Some(inflowing) = loans.inflowing_loans.row(region) { - if !inflowing.is_empty() { - for point in points.iter() { - loans.live_loans.union_row(point, inflowing); - } - } - } - } } /// Records `region` as being live at all the control-flow points. @@ -213,12 +175,17 @@ impl LivenessValues { self.location_map.to_location(point) } + /// When using `-Zpolonius=next`, records the given live loans for the loan scopes and active + /// loans dataflow computations. + pub(crate) fn record_live_loans(&mut self, live_loans: LiveLoans) { + self.live_loans = Some(live_loans); + } + /// When using `-Zpolonius=next`, returns whether the `loan_idx` is live at the given `point`. pub(crate) fn is_loan_live_at(&self, loan_idx: BorrowIndex, point: PointIndex) -> bool { - self.loans + self.live_loans .as_ref() .expect("Accessing live loans requires `-Zpolonius=next`") - .live_loans .contains(point, loan_idx) } } diff --git a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs index f23602d0358..4e0b2a4e296 100644 --- a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs +++ b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs @@ -38,11 +38,19 @@ pub(super) fn generate<'a, 'tcx>( ) { debug!("liveness::generate"); - let free_regions = regions_that_outlive_free_regions( - typeck.infcx.num_region_vars(), - &typeck.universal_regions, - &typeck.constraints.outlives_constraints, - ); + // NLLs can avoid computing some liveness data here because its constraints are + // location-insensitive, but that doesn't work in polonius: locals whose type contains a region + // that outlives a free region are not necessarily live everywhere in a flow-sensitive setting, + // unlike NLLs. + let free_regions = if !typeck.tcx().sess.opts.unstable_opts.polonius.is_next_enabled() { + regions_that_outlive_free_regions( + typeck.infcx.num_region_vars(), + &typeck.universal_regions, + &typeck.constraints.outlives_constraints, + ) + } else { + typeck.universal_regions.universal_regions_iter().collect() + }; let (relevant_live_locals, boring_locals) = compute_relevant_live_locals(typeck.tcx(), &free_regions, body); diff --git a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs index 4c0d3138f2d..c564d85616e 100644 --- a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs +++ b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs @@ -16,7 +16,7 @@ use rustc_trait_selection::traits::query::type_op::{DropckOutlives, TypeOp, Type use tracing::debug; use crate::polonius; -use crate::region_infer::values::{self, LiveLoans}; +use crate::region_infer::values; use crate::type_check::liveness::local_use_map::LocalUseMap; use crate::type_check::{NormalizeLocation, TypeChecker}; @@ -44,37 +44,6 @@ pub(super) fn trace<'a, 'tcx>( boring_locals: Vec<Local>, ) { let local_use_map = &LocalUseMap::build(&relevant_live_locals, location_map, body); - - // When using `-Zpolonius=next`, compute the set of loans that can reach a given region. - if typeck.tcx().sess.opts.unstable_opts.polonius.is_next_enabled() { - let borrow_set = &typeck.borrow_set; - let mut live_loans = LiveLoans::new(borrow_set.len()); - let outlives_constraints = &typeck.constraints.outlives_constraints; - let graph = outlives_constraints.graph(typeck.infcx.num_region_vars()); - let region_graph = - graph.region_graph(outlives_constraints, typeck.universal_regions.fr_static); - - // Traverse each issuing region's constraints, and record the loan as flowing into the - // outlived region. - for (loan, issuing_region_data) in borrow_set.iter_enumerated() { - for succ in rustc_data_structures::graph::depth_first_search( - ®ion_graph, - issuing_region_data.region, - ) { - // We don't need to mention that a loan flows into its issuing region. - if succ == issuing_region_data.region { - continue; - } - - live_loans.inflowing_loans.insert(succ, loan); - } - } - - // Store the inflowing loans in the liveness constraints: they will be used to compute live - // loans when liveness data is recorded there. - typeck.constraints.liveness_constraints.loans = Some(live_loans); - }; - let cx = LivenessContext { typeck, body, diff --git a/tests/crashes/127628.rs b/tests/crashes/127628.rs deleted file mode 100644 index f11ab3f7e8d..00000000000 --- a/tests/crashes/127628.rs +++ /dev/null @@ -1,14 +0,0 @@ -//@ known-bug: #127628 -//@ compile-flags: -Zpolonius=next - -use std::io::{self, Read}; - -pub struct Container<'a> { - reader: &'a mut dyn Read, -} - -impl<'a> Container { - pub fn wrap<'s>(reader: &'s mut dyn io::Read) -> Container<'s> { - Container { reader: reader } - } -} |