diff options
| -rw-r--r-- | compiler/rustc_borrowck/src/dataflow.rs | 160 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/lib.rs | 79 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/mod.rs | 2 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/results.rs | 4 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/lib.rs | 6 |
5 files changed, 174 insertions, 77 deletions
diff --git a/compiler/rustc_borrowck/src/dataflow.rs b/compiler/rustc_borrowck/src/dataflow.rs index d832decc170..7adc7a8863e 100644 --- a/compiler/rustc_borrowck/src/dataflow.rs +++ b/compiler/rustc_borrowck/src/dataflow.rs @@ -1,93 +1,171 @@ +use std::fmt; + use rustc_data_structures::fx::FxIndexMap; use rustc_data_structures::graph; use rustc_index::bit_set::BitSet; -use rustc_middle::mir::{self, BasicBlock, Body, Location, Place, TerminatorEdges}; +use rustc_middle::mir::{ + self, BasicBlock, Body, CallReturnPlaces, Location, Place, TerminatorEdges, +}; use rustc_middle::ty::{RegionVid, TyCtxt}; use rustc_mir_dataflow::fmt::DebugWithContext; use rustc_mir_dataflow::impls::{EverInitializedPlaces, MaybeUninitializedPlaces}; -use rustc_mir_dataflow::{Analysis, Forward, GenKill, Results, ResultsVisitable}; +use rustc_mir_dataflow::{Analysis, GenKill, JoinSemiLattice, SwitchIntEdgeEffects}; use tracing::debug; use crate::{BorrowSet, PlaceConflictBias, PlaceExt, RegionInferenceContext, places_conflict}; -/// The results of the dataflow analyses used by the borrow checker. -pub(crate) struct BorrowckResults<'a, 'tcx> { - pub(crate) borrows: Results<'tcx, Borrows<'a, 'tcx>>, - pub(crate) uninits: Results<'tcx, MaybeUninitializedPlaces<'a, 'tcx>>, - pub(crate) ever_inits: Results<'tcx, EverInitializedPlaces<'a, 'tcx>>, -} - -/// The transient state of the dataflow analyses used by the borrow checker. -#[derive(Debug)] -pub(crate) struct BorrowckDomain<'a, 'tcx> { - pub(crate) borrows: <Borrows<'a, 'tcx> as Analysis<'tcx>>::Domain, - pub(crate) uninits: <MaybeUninitializedPlaces<'a, 'tcx> as Analysis<'tcx>>::Domain, - pub(crate) ever_inits: <EverInitializedPlaces<'a, 'tcx> as Analysis<'tcx>>::Domain, +// This analysis is different to most others. Its results aren't computed with +// `iterate_to_fixpoint`, but are instead composed from the results of three sub-analyses that are +// computed individually with `iterate_to_fixpoint`. +pub(crate) struct Borrowck<'a, 'tcx> { + pub(crate) borrows: Borrows<'a, 'tcx>, + pub(crate) uninits: MaybeUninitializedPlaces<'a, 'tcx>, + pub(crate) ever_inits: EverInitializedPlaces<'a, 'tcx>, } -impl<'a, 'tcx> ResultsVisitable<'tcx> for BorrowckResults<'a, 'tcx> { - type Direction = Forward; +impl<'a, 'tcx> Analysis<'tcx> for Borrowck<'a, 'tcx> { type Domain = BorrowckDomain<'a, 'tcx>; + const NAME: &'static str = "borrowck"; + fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain { BorrowckDomain { - borrows: self.borrows.analysis.bottom_value(body), - uninits: self.uninits.analysis.bottom_value(body), - ever_inits: self.ever_inits.analysis.bottom_value(body), + borrows: self.borrows.bottom_value(body), + uninits: self.uninits.bottom_value(body), + ever_inits: self.ever_inits.bottom_value(body), } } - fn reset_to_block_entry(&self, state: &mut Self::Domain, block: BasicBlock) { - state.borrows.clone_from(self.borrows.entry_set_for_block(block)); - state.uninits.clone_from(self.uninits.entry_set_for_block(block)); - state.ever_inits.clone_from(self.ever_inits.entry_set_for_block(block)); + fn initialize_start_block(&self, _body: &mir::Body<'tcx>, _state: &mut Self::Domain) { + // This is only reachable from `iterate_to_fixpoint`, which this analysis doesn't use. + unreachable!(); } - fn reconstruct_before_statement_effect( + fn apply_before_statement_effect( &mut self, state: &mut Self::Domain, stmt: &mir::Statement<'tcx>, loc: Location, ) { - self.borrows.analysis.apply_before_statement_effect(&mut state.borrows, stmt, loc); - self.uninits.analysis.apply_before_statement_effect(&mut state.uninits, stmt, loc); - self.ever_inits.analysis.apply_before_statement_effect(&mut state.ever_inits, stmt, loc); + self.borrows.apply_before_statement_effect(&mut state.borrows, stmt, loc); + self.uninits.apply_before_statement_effect(&mut state.uninits, stmt, loc); + self.ever_inits.apply_before_statement_effect(&mut state.ever_inits, stmt, loc); } - fn reconstruct_statement_effect( + fn apply_statement_effect( &mut self, state: &mut Self::Domain, stmt: &mir::Statement<'tcx>, loc: Location, ) { - self.borrows.analysis.apply_statement_effect(&mut state.borrows, stmt, loc); - self.uninits.analysis.apply_statement_effect(&mut state.uninits, stmt, loc); - self.ever_inits.analysis.apply_statement_effect(&mut state.ever_inits, stmt, loc); + self.borrows.apply_statement_effect(&mut state.borrows, stmt, loc); + self.uninits.apply_statement_effect(&mut state.uninits, stmt, loc); + self.ever_inits.apply_statement_effect(&mut state.ever_inits, stmt, loc); } - fn reconstruct_before_terminator_effect( + fn apply_before_terminator_effect( &mut self, state: &mut Self::Domain, term: &mir::Terminator<'tcx>, loc: Location, ) { - self.borrows.analysis.apply_before_terminator_effect(&mut state.borrows, term, loc); - self.uninits.analysis.apply_before_terminator_effect(&mut state.uninits, term, loc); - self.ever_inits.analysis.apply_before_terminator_effect(&mut state.ever_inits, term, loc); + self.borrows.apply_before_terminator_effect(&mut state.borrows, term, loc); + self.uninits.apply_before_terminator_effect(&mut state.uninits, term, loc); + self.ever_inits.apply_before_terminator_effect(&mut state.ever_inits, term, loc); } - fn reconstruct_terminator_effect( + fn apply_terminator_effect<'mir>( &mut self, state: &mut Self::Domain, - term: &mir::Terminator<'tcx>, + term: &'mir mir::Terminator<'tcx>, loc: Location, + ) -> TerminatorEdges<'mir, 'tcx> { + self.borrows.apply_terminator_effect(&mut state.borrows, term, loc); + self.uninits.apply_terminator_effect(&mut state.uninits, term, loc); + self.ever_inits.apply_terminator_effect(&mut state.ever_inits, term, loc); + + // This return value doesn't matter. It's only used by `iterate_to_fixpoint`, which this + // analysis doesn't use. + TerminatorEdges::None + } + + fn apply_call_return_effect( + &mut self, + _state: &mut Self::Domain, + _block: BasicBlock, + _return_places: CallReturnPlaces<'_, 'tcx>, + ) { + // This is only reachable from `iterate_to_fixpoint`, which this analysis doesn't use. + unreachable!(); + } + + fn apply_switch_int_edge_effects( + &mut self, + _block: BasicBlock, + _discr: &mir::Operand<'tcx>, + _apply_edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>, ) { - self.borrows.analysis.apply_terminator_effect(&mut state.borrows, term, loc); - self.uninits.analysis.apply_terminator_effect(&mut state.uninits, term, loc); - self.ever_inits.analysis.apply_terminator_effect(&mut state.ever_inits, term, loc); + // This is only reachable from `iterate_to_fixpoint`, which this analysis doesn't use. + unreachable!(); } } +impl JoinSemiLattice for BorrowckDomain<'_, '_> { + fn join(&mut self, _other: &Self) -> bool { + // This is only reachable from `iterate_to_fixpoint`, which this analysis doesn't use. + unreachable!(); + } +} + +impl<'tcx, C> DebugWithContext<C> for BorrowckDomain<'_, 'tcx> +where + C: rustc_mir_dataflow::move_paths::HasMoveData<'tcx>, +{ + fn fmt_with(&self, ctxt: &C, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str("borrows: ")?; + self.borrows.fmt_with(ctxt, f)?; + f.write_str(" uninits: ")?; + self.uninits.fmt_with(ctxt, f)?; + f.write_str(" ever_inits: ")?; + self.ever_inits.fmt_with(ctxt, f)?; + Ok(()) + } + + fn fmt_diff_with(&self, old: &Self, ctxt: &C, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if self == old { + return Ok(()); + } + + if self.borrows != old.borrows { + f.write_str("borrows: ")?; + self.borrows.fmt_diff_with(&old.borrows, ctxt, f)?; + f.write_str("\n")?; + } + + if self.uninits != old.uninits { + f.write_str("uninits: ")?; + self.uninits.fmt_diff_with(&old.uninits, ctxt, f)?; + f.write_str("\n")?; + } + + if self.ever_inits != old.ever_inits { + f.write_str("ever_inits: ")?; + self.ever_inits.fmt_diff_with(&old.ever_inits, ctxt, f)?; + f.write_str("\n")?; + } + + Ok(()) + } +} + +/// The transient state of the dataflow analyses used by the borrow checker. +#[derive(Clone, Debug, PartialEq, Eq)] +pub(crate) struct BorrowckDomain<'a, 'tcx> { + pub(crate) borrows: <Borrows<'a, 'tcx> as Analysis<'tcx>>::Domain, + pub(crate) uninits: <MaybeUninitializedPlaces<'a, 'tcx> as Analysis<'tcx>>::Domain, + pub(crate) ever_inits: <EverInitializedPlaces<'a, 'tcx> as Analysis<'tcx>>::Domain, +} + rustc_index::newtype_index! { #[orderable] #[debug_format = "bw{}"] diff --git a/compiler/rustc_borrowck/src/lib.rs b/compiler/rustc_borrowck/src/lib.rs index 657e6e0907c..817d407c38c 100644 --- a/compiler/rustc_borrowck/src/lib.rs +++ b/compiler/rustc_borrowck/src/lib.rs @@ -36,13 +36,13 @@ use rustc_middle::mir::*; use rustc_middle::query::Providers; use rustc_middle::ty::{self, ParamEnv, RegionVid, TyCtxt, TypingMode}; use rustc_middle::{bug, span_bug}; -use rustc_mir_dataflow::Analysis; use rustc_mir_dataflow::impls::{ EverInitializedPlaces, MaybeInitializedPlaces, MaybeUninitializedPlaces, }; use rustc_mir_dataflow::move_paths::{ InitIndex, InitLocation, LookupResult, MoveData, MoveOutIndex, MovePathIndex, }; +use rustc_mir_dataflow::{Analysis, EntrySets, Results}; use rustc_session::lint::builtin::UNUSED_MUT; use rustc_span::{Span, Symbol}; use smallvec::SmallVec; @@ -50,7 +50,7 @@ use tracing::{debug, instrument}; use crate::borrow_set::{BorrowData, BorrowSet}; use crate::consumers::{BodyWithBorrowckFacts, ConsumerOptions}; -use crate::dataflow::{BorrowIndex, BorrowckDomain, BorrowckResults, Borrows}; +use crate::dataflow::{BorrowIndex, Borrowck, BorrowckDomain, Borrows}; use crate::diagnostics::{AccessKind, IllegalMoveOriginKind, MoveError, RegionName}; use crate::location::LocationTable; use crate::nll::PoloniusOutput; @@ -221,6 +221,10 @@ fn do_mir_borrowck<'tcx>( consumer_options, ); + // `flow_inits` is large, so we drop it as soon as possible. This reduces + // peak memory usage significantly on some benchmarks. + drop(flow_inits); + // Dump MIR results into a file, if that is enabled. This let us // write unit-tests, as well as helping with debugging. nll::dump_nll_mir(&infcx, body, ®ioncx, &opt_closure_req, &borrow_set); @@ -229,27 +233,6 @@ fn do_mir_borrowck<'tcx>( // information. nll::dump_annotation(&infcx, body, ®ioncx, &opt_closure_req, &opaque_type_values, diags); - // The various `flow_*` structures can be large. We drop `flow_inits` here - // so it doesn't overlap with the others below. This reduces peak memory - // usage significantly on some benchmarks. - drop(flow_inits); - - let flow_borrows = Borrows::new(tcx, body, ®ioncx, &borrow_set).iterate_to_fixpoint( - tcx, - body, - Some("borrowck"), - ); - let flow_uninits = MaybeUninitializedPlaces::new(tcx, body, &move_data).iterate_to_fixpoint( - tcx, - body, - Some("borrowck"), - ); - let flow_ever_inits = EverInitializedPlaces::new(body, &move_data).iterate_to_fixpoint( - tcx, - body, - Some("borrowck"), - ); - let movable_coroutine = // The first argument is the coroutine type passed by value if let Some(local) = body.local_decls.raw.get(1) @@ -334,16 +317,11 @@ fn do_mir_borrowck<'tcx>( // Compute and report region errors, if any. mbcx.report_region_errors(nll_errors); - let mut results = BorrowckResults { - ever_inits: flow_ever_inits, - uninits: flow_uninits, - borrows: flow_borrows, - }; - + let mut flow_results = get_flow_results(tcx, body, &move_data, &borrow_set, ®ioncx); rustc_mir_dataflow::visit_results( body, traversal::reverse_postorder(body).map(|(bb, _)| bb), - &mut results, + &mut flow_results, &mut mbcx, ); @@ -426,6 +404,47 @@ fn do_mir_borrowck<'tcx>( (result, body_with_facts) } +fn get_flow_results<'a, 'tcx>( + tcx: TyCtxt<'tcx>, + body: &'a Body<'tcx>, + move_data: &'a MoveData<'tcx>, + borrow_set: &'a BorrowSet<'tcx>, + regioncx: &RegionInferenceContext<'tcx>, +) -> Results<'tcx, Borrowck<'a, 'tcx>> { + // We compute these three analyses individually, but them combine them into + // a single results so that `mbcx` can visit them all together. + let borrows = Borrows::new(tcx, body, regioncx, borrow_set).iterate_to_fixpoint( + tcx, + body, + Some("borrowck"), + ); + let uninits = MaybeUninitializedPlaces::new(tcx, body, move_data).iterate_to_fixpoint( + tcx, + body, + Some("borrowck"), + ); + let ever_inits = EverInitializedPlaces::new(body, move_data).iterate_to_fixpoint( + tcx, + body, + Some("borrowck"), + ); + + let analysis = Borrowck { + borrows: borrows.analysis, + uninits: uninits.analysis, + ever_inits: ever_inits.analysis, + }; + + assert_eq!(borrows.entry_sets.len(), uninits.entry_sets.len()); + assert_eq!(borrows.entry_sets.len(), ever_inits.entry_sets.len()); + let entry_sets: EntrySets<'_, Borrowck<'_, '_>> = + itertools::izip!(borrows.entry_sets, uninits.entry_sets, ever_inits.entry_sets) + .map(|(borrows, uninits, ever_inits)| BorrowckDomain { borrows, uninits, ever_inits }) + .collect(); + + Results { analysis, entry_sets } +} + pub(crate) struct BorrowckInferCtxt<'tcx> { pub(crate) infcx: InferCtxt<'tcx>, pub(crate) reg_var_to_origin: RefCell<FxIndexMap<ty::RegionVid, RegionCtxt>>, diff --git a/compiler/rustc_mir_dataflow/src/framework/mod.rs b/compiler/rustc_mir_dataflow/src/framework/mod.rs index 8f81da8bb04..4ad68193528 100644 --- a/compiler/rustc_mir_dataflow/src/framework/mod.rs +++ b/compiler/rustc_mir_dataflow/src/framework/mod.rs @@ -55,7 +55,7 @@ mod visitor; pub use self::cursor::ResultsCursor; pub use self::direction::{Backward, Direction, Forward}; pub use self::lattice::{JoinSemiLattice, MaybeReachable}; -pub use self::results::Results; +pub use self::results::{EntrySets, Results}; pub use self::visitor::{ResultsVisitable, ResultsVisitor, visit_results}; /// Analysis domains are all bitsets of various kinds. This trait holds diff --git a/compiler/rustc_mir_dataflow/src/framework/results.rs b/compiler/rustc_mir_dataflow/src/framework/results.rs index 366fcbf33ba..2269c4ec226 100644 --- a/compiler/rustc_mir_dataflow/src/framework/results.rs +++ b/compiler/rustc_mir_dataflow/src/framework/results.rs @@ -18,7 +18,7 @@ use crate::errors::{ DuplicateValuesFor, PathMustEndInFilename, RequiresAnArgument, UnknownFormatter, }; -type EntrySets<'tcx, A> = IndexVec<BasicBlock, <A as Analysis<'tcx>>::Domain>; +pub type EntrySets<'tcx, A> = IndexVec<BasicBlock, <A as Analysis<'tcx>>::Domain>; /// A dataflow analysis that has converged to fixpoint. #[derive(Clone)] @@ -27,7 +27,7 @@ where A: Analysis<'tcx>, { pub analysis: A, - pub(super) entry_sets: EntrySets<'tcx, A>, + pub entry_sets: EntrySets<'tcx, A>, } impl<'tcx, A> Results<'tcx, A> diff --git a/compiler/rustc_mir_dataflow/src/lib.rs b/compiler/rustc_mir_dataflow/src/lib.rs index b404e3bfb72..8ebe7d59309 100644 --- a/compiler/rustc_mir_dataflow/src/lib.rs +++ b/compiler/rustc_mir_dataflow/src/lib.rs @@ -18,9 +18,9 @@ pub use self::drop_flag_effects::{ move_path_children_matching, on_all_children_bits, on_lookup_result_bits, }; pub use self::framework::{ - Analysis, Backward, Direction, Forward, GenKill, JoinSemiLattice, MaybeReachable, Results, - ResultsCursor, ResultsVisitable, ResultsVisitor, SwitchIntEdgeEffects, fmt, graphviz, lattice, - visit_results, + Analysis, Backward, Direction, EntrySets, Forward, GenKill, JoinSemiLattice, MaybeReachable, + Results, ResultsCursor, ResultsVisitable, ResultsVisitor, SwitchIntEdgeEffects, fmt, graphviz, + lattice, visit_results, }; use self::move_paths::MoveData; |