diff options
| -rw-r--r-- | compiler/rustc_borrowck/src/constraint_generation.rs | 248 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/lib.rs | 22 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/nll.rs | 152 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/polonius/loan_invalidations.rs (renamed from compiler/rustc_borrowck/src/invalidation.rs) | 45 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/polonius/loan_kills.rs | 147 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/polonius/mod.rs | 188 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/type_check/liveness/mod.rs | 84 |
7 files changed, 454 insertions, 432 deletions
diff --git a/compiler/rustc_borrowck/src/constraint_generation.rs b/compiler/rustc_borrowck/src/constraint_generation.rs deleted file mode 100644 index 21d367c40cb..00000000000 --- a/compiler/rustc_borrowck/src/constraint_generation.rs +++ /dev/null @@ -1,248 +0,0 @@ -#![deny(rustc::untranslatable_diagnostic)] -#![deny(rustc::diagnostic_outside_of_impl)] -use rustc_infer::infer::InferCtxt; -use rustc_middle::mir::visit::TyContext; -use rustc_middle::mir::visit::Visitor; -use rustc_middle::mir::{ - Body, Local, Location, Place, PlaceRef, ProjectionElem, Rvalue, SourceInfo, Statement, - StatementKind, Terminator, TerminatorKind, UserTypeProjection, -}; -use rustc_middle::ty::visit::TypeVisitable; -use rustc_middle::ty::GenericArgsRef; -use rustc_middle::ty::{self, Ty, TyCtxt}; - -use crate::{ - borrow_set::BorrowSet, facts::AllFacts, location::LocationTable, places_conflict, - region_infer::values::LivenessValues, -}; - -pub(super) fn generate_constraints<'tcx>( - infcx: &InferCtxt<'tcx>, - liveness_constraints: &mut LivenessValues, - all_facts: &mut Option<AllFacts>, - location_table: &LocationTable, - body: &Body<'tcx>, - borrow_set: &BorrowSet<'tcx>, -) { - let mut cg = ConstraintGeneration { - borrow_set, - infcx, - liveness_constraints, - location_table, - all_facts, - body, - }; - - for (bb, data) in body.basic_blocks.iter_enumerated() { - cg.visit_basic_block_data(bb, data); - } -} - -/// 'cg = the duration of the constraint generation process itself. -struct ConstraintGeneration<'cg, 'tcx> { - infcx: &'cg InferCtxt<'tcx>, - all_facts: &'cg mut Option<AllFacts>, - location_table: &'cg LocationTable, - liveness_constraints: &'cg mut LivenessValues, - borrow_set: &'cg BorrowSet<'tcx>, - body: &'cg Body<'tcx>, -} - -impl<'cg, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, 'tcx> { - /// We sometimes have `args` within an rvalue, or within a - /// call. Make them live at the location where they appear. - fn visit_args(&mut self, args: &GenericArgsRef<'tcx>, location: Location) { - self.add_regular_live_constraint(*args, location); - self.super_args(args); - } - - /// We sometimes have `region` within an rvalue, or within a - /// call. Make them live at the location where they appear. - fn visit_region(&mut self, region: ty::Region<'tcx>, location: Location) { - self.add_regular_live_constraint(region, location); - self.super_region(region); - } - - /// We sometimes have `ty` within an rvalue, or within a - /// call. Make them live at the location where they appear. - fn visit_ty(&mut self, ty: Ty<'tcx>, ty_context: TyContext) { - match ty_context { - TyContext::ReturnTy(SourceInfo { span, .. }) - | TyContext::YieldTy(SourceInfo { span, .. }) - | TyContext::UserTy(span) - | TyContext::LocalDecl { source_info: SourceInfo { span, .. }, .. } => { - span_bug!(span, "should not be visiting outside of the CFG: {:?}", ty_context); - } - TyContext::Location(location) => { - self.add_regular_live_constraint(ty, location); - } - } - - self.super_ty(ty); - } - - fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) { - if let Some(all_facts) = self.all_facts { - let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation"); - all_facts.cfg_edge.push(( - self.location_table.start_index(location), - self.location_table.mid_index(location), - )); - - all_facts.cfg_edge.push(( - self.location_table.mid_index(location), - self.location_table.start_index(location.successor_within_block()), - )); - - // If there are borrows on this now dead local, we need to record them as `killed`. - if let StatementKind::StorageDead(local) = statement.kind { - record_killed_borrows_for_local( - all_facts, - self.borrow_set, - self.location_table, - 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) { - if let Some(all_facts) = self.all_facts { - let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation"); - all_facts.cfg_edge.push(( - self.location_table.start_index(location), - self.location_table.mid_index(location), - )); - - let successor_blocks = terminator.successors(); - all_facts.cfg_edge.reserve(successor_blocks.size_hint().0); - for successor_block in successor_blocks { - all_facts.cfg_edge.push(( - self.location_table.mid_index(location), - self.location_table.start_index(successor_block.start_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); - } - - fn visit_ascribe_user_ty( - &mut self, - _place: &Place<'tcx>, - _variance: ty::Variance, - _user_ty: &UserTypeProjection, - _location: Location, - ) { - } -} - -impl<'cx, 'tcx> ConstraintGeneration<'cx, 'tcx> { - /// 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 add_regular_live_constraint<T>(&mut self, live_ty: T, location: Location) - where - T: TypeVisitable<TyCtxt<'tcx>>, - { - debug!("add_regular_live_constraint(live_ty={:?}, location={:?})", live_ty, location); - - self.infcx.tcx.for_each_free_region(&live_ty, |live_region| { - let vid = live_region.as_var(); - self.liveness_constraints.add_location(vid, location); - }); - } - - /// When recording facts for Polonius, 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) { - if let Some(all_facts) = self.all_facts { - let _prof_timer = self.infcx.tcx.prof.generic_activity("polonius_fact_generation"); - - // Depending on the `Place` we're killing: - // - if it's a local, or a single deref of a local, - // we kill all the borrows on the local. - // - if it's a deeper projection, we have to filter which - // of the borrows are killed: the ones whose `borrowed_place` - // conflicts with the `place`. - match place.as_ref() { - PlaceRef { local, projection: &[] } - | PlaceRef { local, projection: &[ProjectionElem::Deref] } => { - debug!( - "Recording `killed` facts for borrows of local={:?} at location={:?}", - local, location - ); - - record_killed_borrows_for_local( - all_facts, - self.borrow_set, - self.location_table, - local, - location, - ); - } - - PlaceRef { local, projection: &[.., _] } => { - // Kill conflicting borrows of the innermost local. - debug!( - "Recording `killed` facts for borrows of \ - innermost projected local={:?} at location={:?}", - local, location - ); - - if let Some(borrow_indices) = self.borrow_set.local_map.get(&local) { - for &borrow_index in borrow_indices { - let places_conflict = places_conflict::places_conflict( - self.infcx.tcx, - self.body, - self.borrow_set[borrow_index].borrowed_place, - place, - places_conflict::PlaceConflictBias::NoOverlap, - ); - - if places_conflict { - let location_index = self.location_table.mid_index(location); - all_facts.loan_killed_at.push((borrow_index, location_index)); - } - } - } - } - } - } - } -} - -/// When recording facts for Polonius, records the borrows on the specified local as `killed`. -fn record_killed_borrows_for_local( - all_facts: &mut AllFacts, - borrow_set: &BorrowSet<'_>, - location_table: &LocationTable, - local: Local, - location: Location, -) { - if let Some(borrow_indices) = borrow_set.local_map.get(&local) { - all_facts.loan_killed_at.reserve(borrow_indices.len()); - for &borrow_index in borrow_indices { - let location_index = location_table.mid_index(location); - all_facts.loan_killed_at.push((borrow_index, location_index)); - } - } -} diff --git a/compiler/rustc_borrowck/src/lib.rs b/compiler/rustc_borrowck/src/lib.rs index 6e44f44dc18..ea36910a300 100644 --- a/compiler/rustc_borrowck/src/lib.rs +++ b/compiler/rustc_borrowck/src/lib.rs @@ -65,19 +65,18 @@ use self::path_utils::*; pub mod borrow_set; mod borrowck_errors; -mod constraint_generation; mod constraints; mod dataflow; mod def_use; mod diagnostics; mod facts; -mod invalidation; mod location; mod member_constraints; mod nll; mod path_utils; mod place_ext; mod places_conflict; +mod polonius; mod prefixes; mod region_infer; mod renumber; @@ -195,8 +194,7 @@ fn do_mir_borrowck<'tcx>( nll::replace_regions_in_mir(&infcx, param_env, &mut body_owned, &mut promoted); let body = &body_owned; // no further changes - let location_table_owned = LocationTable::new(body); - let location_table = &location_table_owned; + let location_table = LocationTable::new(body); let move_data = MoveData::gather_moves(body, tcx, param_env, |_| true); let promoted_move_data = promoted @@ -228,7 +226,7 @@ fn do_mir_borrowck<'tcx>( free_regions, body, &promoted, - location_table, + &location_table, param_env, &mut flow_inits, &mdpe.move_data, @@ -292,7 +290,7 @@ fn do_mir_borrowck<'tcx>( param_env, body: promoted_body, move_data: &move_data, - location_table, // no need to create a real one for the promoted, it is not used + location_table: &location_table, // no need to create a real one for the promoted, it is not used movable_coroutine, fn_self_span_reported: Default::default(), locals_are_invalidated_at_exit, @@ -333,7 +331,7 @@ fn do_mir_borrowck<'tcx>( param_env, body, move_data: &mdpe.move_data, - location_table, + location_table: &location_table, movable_coroutine, locals_are_invalidated_at_exit, fn_self_span_reported: Default::default(), @@ -435,7 +433,7 @@ fn do_mir_borrowck<'tcx>( promoted, borrow_set, region_inference_context: regioncx, - location_table: polonius_input.as_ref().map(|_| location_table_owned), + location_table: polonius_input.as_ref().map(|_| location_table), input_facts: polonius_input, output_facts, })) @@ -1020,9 +1018,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { flow_state: &Flows<'cx, 'tcx>, ) -> bool { let mut error_reported = false; - let tcx = self.infcx.tcx; - let body = self.body; - let borrow_set = self.borrow_set.clone(); + let borrow_set = Rc::clone(&self.borrow_set); // Use polonius output if it has been enabled. let mut polonius_output; @@ -1039,8 +1035,8 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { each_borrow_involving_path( self, - tcx, - body, + self.infcx.tcx, + self.body, location, (sd, place_span.0), &borrow_set, diff --git a/compiler/rustc_borrowck/src/nll.rs b/compiler/rustc_borrowck/src/nll.rs index 480358ef997..f12975c3f09 100644 --- a/compiler/rustc_borrowck/src/nll.rs +++ b/compiler/rustc_borrowck/src/nll.rs @@ -2,16 +2,17 @@ #![deny(rustc::diagnostic_outside_of_impl)] //! The entry point of the NLL borrow checker. +use polonius_engine::{Algorithm, Output}; use rustc_data_structures::fx::FxIndexMap; use rustc_hir::def_id::LocalDefId; use rustc_index::IndexSlice; use rustc_middle::mir::{create_dump_file, dump_enabled, dump_mir, PassWhere}; -use rustc_middle::mir::{ - Body, ClosureOutlivesSubject, ClosureRegionRequirements, LocalKind, Location, Promoted, - START_BLOCK, -}; +use rustc_middle::mir::{Body, ClosureOutlivesSubject, ClosureRegionRequirements, Promoted}; use rustc_middle::ty::print::with_no_trimmed_paths; use rustc_middle::ty::{self, OpaqueHiddenType, TyCtxt}; +use rustc_mir_dataflow::impls::MaybeInitializedPlaces; +use rustc_mir_dataflow::move_paths::MoveData; +use rustc_mir_dataflow::ResultsCursor; use rustc_span::symbol::sym; use std::env; use std::io; @@ -19,20 +20,13 @@ use std::path::PathBuf; use std::rc::Rc; use std::str::FromStr; -use polonius_engine::{Algorithm, Output}; - -use rustc_mir_dataflow::impls::MaybeInitializedPlaces; -use rustc_mir_dataflow::move_paths::{InitKind, InitLocation, MoveData}; -use rustc_mir_dataflow::ResultsCursor; - use crate::{ borrow_set::BorrowSet, - constraint_generation, consumers::ConsumerOptions, diagnostics::RegionErrors, facts::{AllFacts, AllFactsExt, RustcFacts}, - invalidation, location::LocationTable, + polonius, region_infer::{values::RegionValueElements, RegionInferenceContext}, renumber, type_check::{self, MirTypeckRegionConstraints, MirTypeckResults}, @@ -78,81 +72,6 @@ pub(crate) fn replace_regions_in_mir<'tcx>( universal_regions } -// This function populates an AllFacts instance with base facts related to -// MovePaths and needed for the move analysis. -fn populate_polonius_move_facts( - all_facts: &mut AllFacts, - move_data: &MoveData<'_>, - location_table: &LocationTable, - body: &Body<'_>, -) { - all_facts - .path_is_var - .extend(move_data.rev_lookup.iter_locals_enumerated().map(|(l, r)| (r, l))); - - for (child, move_path) in move_data.move_paths.iter_enumerated() { - if let Some(parent) = move_path.parent { - all_facts.child_path.push((child, parent)); - } - } - - let fn_entry_start = - location_table.start_index(Location { block: START_BLOCK, statement_index: 0 }); - - // initialized_at - for init in move_data.inits.iter() { - match init.location { - InitLocation::Statement(location) => { - let block_data = &body[location.block]; - let is_terminator = location.statement_index == block_data.statements.len(); - - if is_terminator && init.kind == InitKind::NonPanicPathOnly { - // We are at the terminator of an init that has a panic path, - // and where the init should not happen on panic - - for successor in block_data.terminator().successors() { - if body[successor].is_cleanup { - continue; - } - - // The initialization happened in (or rather, when arriving at) - // the successors, but not in the unwind block. - let first_statement = Location { block: successor, statement_index: 0 }; - all_facts - .path_assigned_at_base - .push((init.path, location_table.start_index(first_statement))); - } - } else { - // In all other cases, the initialization just happens at the - // midpoint, like any other effect. - all_facts - .path_assigned_at_base - .push((init.path, location_table.mid_index(location))); - } - } - // Arguments are initialized on function entry - InitLocation::Argument(local) => { - assert!(body.local_kind(local) == LocalKind::Arg); - all_facts.path_assigned_at_base.push((init.path, fn_entry_start)); - } - } - } - - for (local, path) in move_data.rev_lookup.iter_locals_enumerated() { - if body.local_kind(local) != LocalKind::Arg { - // Non-arguments start out deinitialised; we simulate this with an - // initial move: - all_facts.path_moved_at_base.push((path, fn_entry_start)); - } - } - - // moved_out_at - // deinitialisation is assumed to always happen! - all_facts - .path_moved_at_base - .extend(move_data.moves.iter().map(|mo| (mo.path, location_table.mid_index(mo.source)))); -} - /// Computes the (non-lexical) regions from the input MIR. /// /// This may result in errors being reported. @@ -203,46 +122,6 @@ pub(crate) fn compute_regions<'cx, 'tcx>( polonius_input, ); - if let Some(all_facts) = &mut all_facts { - let _prof_timer = infcx.tcx.prof.generic_activity("polonius_fact_generation"); - all_facts.universal_region.extend(universal_regions.universal_regions()); - populate_polonius_move_facts(all_facts, move_data, location_table, body); - - // Emit universal regions facts, and their relations, for Polonius. - // - // 1: universal regions are modeled in Polonius as a pair: - // - the universal region vid itself. - // - a "placeholder loan" associated to this universal region. Since they don't exist in - // the `borrow_set`, their `BorrowIndex` are synthesized as the universal region index - // added to the existing number of loans, as if they succeeded them in the set. - // - let borrow_count = borrow_set.len(); - debug!( - "compute_regions: polonius placeholders, num_universals={}, borrow_count={}", - universal_regions.len(), - borrow_count - ); - - for universal_region in universal_regions.universal_regions() { - let universal_region_idx = universal_region.index(); - let placeholder_loan_idx = borrow_count + universal_region_idx; - all_facts.placeholder.push((universal_region, placeholder_loan_idx.into())); - } - - // 2: the universal region relations `outlives` constraints are emitted as - // `known_placeholder_subset` facts. - for (fr1, fr2) in universal_region_relations.known_outlives() { - if fr1 != fr2 { - debug!( - "compute_regions: emitting polonius `known_placeholder_subset` \ - fr1={:?}, fr2={:?}", - fr1, fr2 - ); - all_facts.known_placeholder_subset.push((fr1, fr2)); - } - } - } - // Create the region inference context, taking ownership of the // region inference data that was contained in `infcx`, and the // base constraints generated by the type-check. @@ -250,7 +129,7 @@ pub(crate) fn compute_regions<'cx, 'tcx>( let MirTypeckRegionConstraints { placeholder_indices, placeholder_index_to_region: _, - mut liveness_constraints, + liveness_constraints, outlives_constraints, member_constraints, universe_causes, @@ -258,13 +137,16 @@ pub(crate) fn compute_regions<'cx, 'tcx>( } = constraints; let placeholder_indices = Rc::new(placeholder_indices); - constraint_generation::generate_constraints( - infcx, - &mut liveness_constraints, + // If requested, emit legacy polonius facts. + polonius::emit_facts( &mut all_facts, + infcx.tcx, location_table, body, borrow_set, + move_data, + &universal_regions, + &universal_region_relations, ); let mut regioncx = RegionInferenceContext::new( @@ -282,14 +164,10 @@ pub(crate) fn compute_regions<'cx, 'tcx>( live_loans, ); - // Generate various additional constraints. - invalidation::generate_invalidates(infcx.tcx, &mut all_facts, location_table, body, borrow_set); - - let def_id = body.source.def_id(); - - // Dump facts if requested. + // If requested: dump NLL facts, and run legacy polonius analysis. let polonius_output = all_facts.as_ref().and_then(|all_facts| { if infcx.tcx.sess.opts.unstable_opts.nll_facts { + let def_id = body.source.def_id(); let def_path = infcx.tcx.def_path(def_id); let dir_path = PathBuf::from(&infcx.tcx.sess.opts.unstable_opts.nll_facts_dir) .join(def_path.to_filename_friendly_no_crate()); diff --git a/compiler/rustc_borrowck/src/invalidation.rs b/compiler/rustc_borrowck/src/polonius/loan_invalidations.rs index a3db101311f..232bd741825 100644 --- a/compiler/rustc_borrowck/src/invalidation.rs +++ b/compiler/rustc_borrowck/src/polonius/loan_invalidations.rs @@ -14,34 +14,21 @@ use crate::{ ReadOrWrite, Reservation, Shallow, Write, WriteKind, }; -pub(super) fn generate_invalidates<'tcx>( +/// Emit `loan_invalidated_at` facts. +pub(super) fn emit_loan_invalidations<'tcx>( tcx: TyCtxt<'tcx>, - all_facts: &mut Option<AllFacts>, + all_facts: &mut AllFacts, location_table: &LocationTable, body: &Body<'tcx>, borrow_set: &BorrowSet<'tcx>, ) { - if all_facts.is_none() { - // Nothing to do if we don't have any facts - return; - } - - if let Some(all_facts) = all_facts { - let _prof_timer = tcx.prof.generic_activity("polonius_fact_generation"); - let dominators = body.basic_blocks.dominators(); - let mut ig = InvalidationGenerator { - all_facts, - borrow_set, - tcx, - location_table, - body: body, - dominators, - }; - ig.visit_body(body); - } + let dominators = body.basic_blocks.dominators(); + let mut visitor = + LoanInvalidationsGenerator { all_facts, borrow_set, tcx, location_table, body, dominators }; + visitor.visit_body(body); } -struct InvalidationGenerator<'cx, 'tcx> { +struct LoanInvalidationsGenerator<'cx, 'tcx> { tcx: TyCtxt<'tcx>, all_facts: &'cx mut AllFacts, location_table: &'cx LocationTable, @@ -52,7 +39,7 @@ struct InvalidationGenerator<'cx, 'tcx> { /// Visits the whole MIR and generates `invalidates()` facts. /// Most of the code implementing this was stolen from `borrow_check/mod.rs`. -impl<'cx, 'tcx> Visitor<'tcx> for InvalidationGenerator<'cx, 'tcx> { +impl<'cx, 'tcx> Visitor<'tcx> for LoanInvalidationsGenerator<'cx, 'tcx> { fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) { self.check_activations(location); @@ -214,7 +201,7 @@ impl<'cx, 'tcx> Visitor<'tcx> for InvalidationGenerator<'cx, 'tcx> { } } -impl<'cx, 'tcx> InvalidationGenerator<'cx, 'tcx> { +impl<'cx, 'tcx> LoanInvalidationsGenerator<'cx, 'tcx> { /// Simulates mutation of a place. fn mutate_place(&mut self, location: Location, place: Place<'tcx>, kind: AccessDepth) { self.access_place( @@ -348,20 +335,16 @@ impl<'cx, 'tcx> InvalidationGenerator<'cx, 'tcx> { rw: ReadOrWrite, ) { debug!( - "invalidation::check_access_for_conflict(location={:?}, place={:?}, sd={:?}, \ - rw={:?})", + "check_access_for_conflict(location={:?}, place={:?}, sd={:?}, rw={:?})", location, place, sd, rw, ); - let tcx = self.tcx; - let body = self.body; - let borrow_set = self.borrow_set; each_borrow_involving_path( self, - tcx, - body, + self.tcx, + self.body, location, (sd, place), - borrow_set, + self.borrow_set, |_| true, |this, borrow_index, borrow| { match (rw, borrow.kind) { diff --git a/compiler/rustc_borrowck/src/polonius/loan_kills.rs b/compiler/rustc_borrowck/src/polonius/loan_kills.rs new file mode 100644 index 00000000000..5df94383702 --- /dev/null +++ b/compiler/rustc_borrowck/src/polonius/loan_kills.rs @@ -0,0 +1,147 @@ +#![deny(rustc::untranslatable_diagnostic)] +#![deny(rustc::diagnostic_outside_of_impl)] +use rustc_middle::mir::visit::Visitor; +use rustc_middle::mir::{ + Body, Local, Location, Place, PlaceRef, ProjectionElem, Rvalue, Statement, StatementKind, + Terminator, TerminatorKind, +}; +use rustc_middle::ty::TyCtxt; + +use crate::{borrow_set::BorrowSet, facts::AllFacts, location::LocationTable, places_conflict}; + +/// Emit `loan_killed_at` and `cfg_edge` facts at the same time. +pub(super) fn emit_loan_kills<'tcx>( + tcx: TyCtxt<'tcx>, + all_facts: &mut AllFacts, + location_table: &LocationTable, + body: &Body<'tcx>, + borrow_set: &BorrowSet<'tcx>, +) { + let mut visitor = LoanKillsGenerator { borrow_set, tcx, location_table, all_facts, body }; + for (bb, data) in body.basic_blocks.iter_enumerated() { + visitor.visit_basic_block_data(bb, data); + } +} + +struct LoanKillsGenerator<'cx, 'tcx> { + tcx: TyCtxt<'tcx>, + all_facts: &'cx mut AllFacts, + location_table: &'cx LocationTable, + borrow_set: &'cx BorrowSet<'tcx>, + body: &'cx Body<'tcx>, +} + +impl<'cx, 'tcx> Visitor<'tcx> for LoanKillsGenerator<'cx, 'tcx> { + fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) { + // Also record CFG facts here. + self.all_facts.cfg_edge.push(( + self.location_table.start_index(location), + self.location_table.mid_index(location), + )); + + self.all_facts.cfg_edge.push(( + self.location_table.mid_index(location), + self.location_table.start_index(location.successor_within_block()), + )); + + // If there are borrows on this now dead local, we need to record them as `killed`. + 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) { + // Also record CFG facts here. + self.all_facts.cfg_edge.push(( + self.location_table.start_index(location), + self.location_table.mid_index(location), + )); + + let successor_blocks = terminator.successors(); + self.all_facts.cfg_edge.reserve(successor_blocks.size_hint().0); + for successor_block in successor_blocks { + self.all_facts.cfg_edge.push(( + self.location_table.mid_index(location), + self.location_table.start_index(successor_block.start_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); + } +} + +impl<'tcx> LoanKillsGenerator<'_, '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) { + // Depending on the `Place` we're killing: + // - if it's a local, or a single deref of a local, + // we kill all the borrows on the local. + // - if it's a deeper projection, we have to filter which + // of the borrows are killed: the ones whose `borrowed_place` + // conflicts with the `place`. + match place.as_ref() { + PlaceRef { local, projection: &[] } + | PlaceRef { local, projection: &[ProjectionElem::Deref] } => { + debug!( + "Recording `killed` facts for borrows of local={:?} at location={:?}", + local, location + ); + + self.record_killed_borrows_for_local(local, location); + } + + PlaceRef { local, projection: &[.., _] } => { + // Kill conflicting borrows of the innermost local. + debug!( + "Recording `killed` facts for borrows of \ + innermost projected local={:?} at location={:?}", + local, location + ); + + if let Some(borrow_indices) = self.borrow_set.local_map.get(&local) { + for &borrow_index in borrow_indices { + let places_conflict = places_conflict::places_conflict( + self.tcx, + self.body, + self.borrow_set[borrow_index].borrowed_place, + place, + places_conflict::PlaceConflictBias::NoOverlap, + ); + + if places_conflict { + let location_index = self.location_table.mid_index(location); + self.all_facts.loan_killed_at.push((borrow_index, location_index)); + } + } + } + } + } + } + + /// 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) { + let location_index = self.location_table.mid_index(location); + self.all_facts.loan_killed_at.reserve(borrow_indices.len()); + for &borrow_index in borrow_indices { + self.all_facts.loan_killed_at.push((borrow_index, location_index)); + } + } + } +} diff --git a/compiler/rustc_borrowck/src/polonius/mod.rs b/compiler/rustc_borrowck/src/polonius/mod.rs new file mode 100644 index 00000000000..40126d50d57 --- /dev/null +++ b/compiler/rustc_borrowck/src/polonius/mod.rs @@ -0,0 +1,188 @@ +//! Functions dedicated to fact generation for the `-Zpolonius=legacy` datalog implementation. +//! +//! Will be removed in the future, once the in-tree `-Zpolonius=next` implementation reaches feature +//! parity. + +use rustc_middle::mir::{Body, LocalKind, Location, START_BLOCK}; +use rustc_middle::ty::TyCtxt; +use rustc_mir_dataflow::move_paths::{InitKind, InitLocation, MoveData}; + +use crate::borrow_set::BorrowSet; +use crate::facts::AllFacts; +use crate::location::LocationTable; +use crate::type_check::free_region_relations::UniversalRegionRelations; +use crate::universal_regions::UniversalRegions; + +mod loan_invalidations; +mod loan_kills; + +/// When requested, emit most of the facts needed by polonius: +/// - moves and assignments +/// - universal regions and their relations +/// - CFG points and edges +/// - loan kills +/// - loan invalidations +/// +/// The rest of the facts are emitted during typeck and liveness. +pub(crate) fn emit_facts<'tcx>( + all_facts: &mut Option<AllFacts>, + tcx: TyCtxt<'tcx>, + location_table: &LocationTable, + body: &Body<'tcx>, + borrow_set: &BorrowSet<'tcx>, + move_data: &MoveData<'_>, + universal_regions: &UniversalRegions<'_>, + universal_region_relations: &UniversalRegionRelations<'_>, +) { + let Some(all_facts) = all_facts else { + // We don't do anything if there are no facts to fill. + return; + }; + let _prof_timer = tcx.prof.generic_activity("polonius_fact_generation"); + emit_move_facts(all_facts, move_data, location_table, body); + emit_universal_region_facts( + all_facts, + borrow_set, + &universal_regions, + &universal_region_relations, + ); + emit_cfg_and_loan_kills_facts(all_facts, tcx, location_table, body, borrow_set); + emit_loan_invalidations_facts(all_facts, tcx, location_table, body, borrow_set); +} + +/// Emit facts needed for move/init analysis: moves and assignments. +fn emit_move_facts( + all_facts: &mut AllFacts, + move_data: &MoveData<'_>, + location_table: &LocationTable, + body: &Body<'_>, +) { + all_facts + .path_is_var + .extend(move_data.rev_lookup.iter_locals_enumerated().map(|(l, r)| (r, l))); + + for (child, move_path) in move_data.move_paths.iter_enumerated() { + if let Some(parent) = move_path.parent { + all_facts.child_path.push((child, parent)); + } + } + + let fn_entry_start = + location_table.start_index(Location { block: START_BLOCK, statement_index: 0 }); + + // initialized_at + for init in move_data.inits.iter() { + match init.location { + InitLocation::Statement(location) => { + let block_data = &body[location.block]; + let is_terminator = location.statement_index == block_data.statements.len(); + + if is_terminator && init.kind == InitKind::NonPanicPathOnly { + // We are at the terminator of an init that has a panic path, + // and where the init should not happen on panic + + for successor in block_data.terminator().successors() { + if body[successor].is_cleanup { + continue; + } + + // The initialization happened in (or rather, when arriving at) + // the successors, but not in the unwind block. + let first_statement = Location { block: successor, statement_index: 0 }; + all_facts + .path_assigned_at_base + .push((init.path, location_table.start_index(first_statement))); + } + } else { + // In all other cases, the initialization just happens at the + // midpoint, like any other effect. + all_facts + .path_assigned_at_base + .push((init.path, location_table.mid_index(location))); + } + } + // Arguments are initialized on function entry + InitLocation::Argument(local) => { + assert!(body.local_kind(local) == LocalKind::Arg); + all_facts.path_assigned_at_base.push((init.path, fn_entry_start)); + } + } + } + + for (local, path) in move_data.rev_lookup.iter_locals_enumerated() { + if body.local_kind(local) != LocalKind::Arg { + // Non-arguments start out deinitialised; we simulate this with an + // initial move: + all_facts.path_moved_at_base.push((path, fn_entry_start)); + } + } + + // moved_out_at + // deinitialisation is assumed to always happen! + all_facts + .path_moved_at_base + .extend(move_data.moves.iter().map(|mo| (mo.path, location_table.mid_index(mo.source)))); +} + +/// Emit universal regions facts, and their relations. +fn emit_universal_region_facts( + all_facts: &mut AllFacts, + borrow_set: &BorrowSet<'_>, + universal_regions: &UniversalRegions<'_>, + universal_region_relations: &UniversalRegionRelations<'_>, +) { + // 1: universal regions are modeled in Polonius as a pair: + // - the universal region vid itself. + // - a "placeholder loan" associated to this universal region. Since they don't exist in + // the `borrow_set`, their `BorrowIndex` are synthesized as the universal region index + // added to the existing number of loans, as if they succeeded them in the set. + // + all_facts.universal_region.extend(universal_regions.universal_regions()); + let borrow_count = borrow_set.len(); + debug!( + "emit_universal_region_facts: polonius placeholders, num_universals={}, borrow_count={}", + universal_regions.len(), + borrow_count + ); + + for universal_region in universal_regions.universal_regions() { + let universal_region_idx = universal_region.index(); + let placeholder_loan_idx = borrow_count + universal_region_idx; + all_facts.placeholder.push((universal_region, placeholder_loan_idx.into())); + } + + // 2: the universal region relations `outlives` constraints are emitted as + // `known_placeholder_subset` facts. + for (fr1, fr2) in universal_region_relations.known_outlives() { + if fr1 != fr2 { + debug!( + "emit_universal_region_facts: emitting polonius `known_placeholder_subset` \ + fr1={:?}, fr2={:?}", + fr1, fr2 + ); + all_facts.known_placeholder_subset.push((fr1, fr2)); + } + } +} + +/// Emit facts about loan invalidations. +fn emit_loan_invalidations_facts<'tcx>( + all_facts: &mut AllFacts, + tcx: TyCtxt<'tcx>, + location_table: &LocationTable, + body: &Body<'tcx>, + borrow_set: &BorrowSet<'tcx>, +) { + loan_invalidations::emit_loan_invalidations(tcx, all_facts, location_table, body, borrow_set); +} + +/// Emit facts about CFG points and edges, as well as locations where loans are killed. +fn emit_cfg_and_loan_kills_facts<'tcx>( + all_facts: &mut AllFacts, + tcx: TyCtxt<'tcx>, + location_table: &LocationTable, + body: &Body<'tcx>, + borrow_set: &BorrowSet<'tcx>, +) { + loan_kills::emit_loan_kills(tcx, all_facts, location_table, body, borrow_set); +} diff --git a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs index a970dadc479..dc4695fd2b0 100644 --- a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs +++ b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs @@ -1,7 +1,9 @@ use itertools::{Either, Itertools}; use rustc_data_structures::fx::FxHashSet; -use rustc_middle::mir::{Body, Local}; -use rustc_middle::ty::{RegionVid, TyCtxt}; +use rustc_middle::mir::visit::{TyContext, Visitor}; +use rustc_middle::mir::{Body, Local, Location, SourceInfo}; +use rustc_middle::ty::visit::TypeVisitable; +use rustc_middle::ty::{GenericArgsRef, Region, RegionVid, Ty, TyCtxt}; use rustc_mir_dataflow::impls::MaybeInitializedPlaces; use rustc_mir_dataflow::move_paths::MoveData; use rustc_mir_dataflow::ResultsCursor; @@ -11,7 +13,7 @@ use crate::{ constraints::OutlivesConstraintSet, facts::{AllFacts, AllFactsExt}, location::LocationTable, - region_infer::values::RegionValueElements, + region_infer::values::{LivenessValues, RegionValueElements}, universal_regions::UniversalRegions, }; @@ -65,6 +67,14 @@ pub(super) fn generate<'mir, 'tcx>( boring_locals, polonius_drop_used, ); + + // Mark regions that should be live where they appear within rvalues or within a call: like + // args, regions, and types. + record_regular_live_regions( + typeck.tcx(), + &mut typeck.borrowck_context.constraints.liveness_constraints, + body, + ); } // The purpose of `compute_relevant_live_locals` is to define the subset of `Local` @@ -132,3 +142,71 @@ fn regions_that_outlive_free_regions<'tcx>( // Return the final set of things we visited. outlives_free_region } + +/// Some variables are "regular live" at `location` -- i.e., they may be used later. This means that +/// all regions appearing in their type must be live at `location`. +fn record_regular_live_regions<'tcx>( + tcx: TyCtxt<'tcx>, + liveness_constraints: &mut LivenessValues, + body: &Body<'tcx>, +) { + let mut visitor = LiveVariablesVisitor { tcx, liveness_constraints }; + for (bb, data) in body.basic_blocks.iter_enumerated() { + visitor.visit_basic_block_data(bb, data); + } +} + +/// Visitor looking for regions that should be live within rvalues or calls. +struct LiveVariablesVisitor<'cx, 'tcx> { + tcx: TyCtxt<'tcx>, + liveness_constraints: &'cx mut LivenessValues, +} + +impl<'cx, 'tcx> Visitor<'tcx> for LiveVariablesVisitor<'cx, 'tcx> { + /// We sometimes have `args` within an rvalue, or within a + /// call. Make them live at the location where they appear. + fn visit_args(&mut self, args: &GenericArgsRef<'tcx>, location: Location) { + self.record_regions_live_at(*args, location); + self.super_args(args); + } + + /// We sometimes have `region`s within an rvalue, or within a + /// call. Make them live at the location where they appear. + fn visit_region(&mut self, region: Region<'tcx>, location: Location) { + self.record_regions_live_at(region, location); + self.super_region(region); + } + + /// We sometimes have `ty`s within an rvalue, or within a + /// call. Make them live at the location where they appear. + fn visit_ty(&mut self, ty: Ty<'tcx>, ty_context: TyContext) { + match ty_context { + TyContext::ReturnTy(SourceInfo { span, .. }) + | TyContext::YieldTy(SourceInfo { span, .. }) + | TyContext::UserTy(span) + | TyContext::LocalDecl { source_info: SourceInfo { span, .. }, .. } => { + span_bug!(span, "should not be visiting outside of the CFG: {:?}", ty_context); + } + TyContext::Location(location) => { + self.record_regions_live_at(ty, location); + } + } + + self.super_ty(ty); + } +} + +impl<'cx, 'tcx> LiveVariablesVisitor<'cx, 'tcx> { + /// Some variable is "regular live" at `location` -- i.e., it may be used later. This means that + /// all regions appearing in the type of `value` must be live at `location`. + fn record_regions_live_at<T>(&mut self, value: T, location: Location) + where + T: TypeVisitable<TyCtxt<'tcx>>, + { + debug!("record_regions_live_at(value={:?}, location={:?})", value, location); + self.tcx.for_each_free_region(&value, |live_region| { + let live_region_vid = live_region.as_var(); + self.liveness_constraints.add_location(live_region_vid, location); + }); + } +} |