diff options
17 files changed, 161 insertions, 657 deletions
diff --git a/compiler/rustc_borrowck/src/dataflow.rs b/compiler/rustc_borrowck/src/dataflow.rs index 5ea48d3fc7e..89ff12c1479 100644 --- a/compiler/rustc_borrowck/src/dataflow.rs +++ b/compiler/rustc_borrowck/src/dataflow.rs @@ -1,13 +1,11 @@ use rustc_data_structures::fx::FxIndexMap; use rustc_data_structures::graph; use rustc_index::bit_set::BitSet; -use rustc_middle::mir::{ - self, BasicBlock, Body, CallReturnPlaces, Location, Place, TerminatorEdges, -}; +use rustc_middle::mir::{self, BasicBlock, Body, 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, AnalysisDomain, Forward, GenKill, Results, ResultsVisitable}; +use rustc_mir_dataflow::{Analysis, Forward, GenKill, Results, ResultsVisitable}; use tracing::debug; use crate::{BorrowSet, PlaceConflictBias, PlaceExt, RegionInferenceContext, places_conflict}; @@ -22,9 +20,9 @@ pub(crate) struct BorrowckResults<'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 AnalysisDomain<'tcx>>::Domain, - pub(crate) uninits: <MaybeUninitializedPlaces<'a, 'tcx> as AnalysisDomain<'tcx>>::Domain, - pub(crate) ever_inits: <EverInitializedPlaces<'a, 'tcx> as AnalysisDomain<'tcx>>::Domain, + 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, } impl<'a, 'tcx> ResultsVisitable<'tcx> for BorrowckResults<'a, 'tcx> { @@ -427,7 +425,7 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> { /// That means they went out of a nonlexical scope fn kill_loans_out_of_scope_at_location( &self, - trans: &mut impl GenKill<BorrowIndex>, + trans: &mut <Self as Analysis<'tcx>>::Domain, location: Location, ) { // NOTE: The state associated with a given `location` @@ -447,7 +445,11 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> { } /// Kill any borrows that conflict with `place`. - fn kill_borrows_on_place(&self, trans: &mut impl GenKill<BorrowIndex>, place: Place<'tcx>) { + fn kill_borrows_on_place( + &self, + trans: &mut <Self as Analysis<'tcx>>::Domain, + place: Place<'tcx>, + ) { debug!("kill_borrows_on_place: place={:?}", place); let other_borrows_of_local = self @@ -486,7 +488,14 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> { } } -impl<'tcx> rustc_mir_dataflow::AnalysisDomain<'tcx> for Borrows<'_, 'tcx> { +/// Forward dataflow computation of the set of borrows that are in scope at a particular location. +/// - we gen the introduced loans +/// - we kill loans on locals going out of (regular) scope +/// - we kill the loans going out of their region's NLL scope: in NLL terms, the frontier where a +/// region stops containing the CFG points reachable from the issuing location. +/// - we also kill loans of conflicting places when overwriting a shared path: e.g. borrows of +/// `a.b.c` when `a` is overwritten. +impl<'tcx> rustc_mir_dataflow::Analysis<'tcx> for Borrows<'_, 'tcx> { type Domain = BitSet<BorrowIndex>; const NAME: &'static str = "borrows"; @@ -500,34 +509,19 @@ impl<'tcx> rustc_mir_dataflow::AnalysisDomain<'tcx> for Borrows<'_, 'tcx> { // no borrows of code region_scopes have been taken prior to // function execution, so this method has no effect. } -} - -/// Forward dataflow computation of the set of borrows that are in scope at a particular location. -/// - we gen the introduced loans -/// - we kill loans on locals going out of (regular) scope -/// - we kill the loans going out of their region's NLL scope: in NLL terms, the frontier where a -/// region stops containing the CFG points reachable from the issuing location. -/// - we also kill loans of conflicting places when overwriting a shared path: e.g. borrows of -/// `a.b.c` when `a` is overwritten. -impl<'tcx> rustc_mir_dataflow::GenKillAnalysis<'tcx> for Borrows<'_, 'tcx> { - type Idx = BorrowIndex; - - fn domain_size(&self, _: &mir::Body<'tcx>) -> usize { - self.borrow_set.len() - } - fn before_statement_effect( + fn apply_before_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, _statement: &mir::Statement<'tcx>, location: Location, ) { self.kill_loans_out_of_scope_at_location(trans, location); } - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, stmt: &mir::Statement<'tcx>, location: Location, ) { @@ -573,7 +567,7 @@ impl<'tcx> rustc_mir_dataflow::GenKillAnalysis<'tcx> for Borrows<'_, 'tcx> { } } - fn before_terminator_effect( + fn apply_before_terminator_effect( &mut self, trans: &mut Self::Domain, _terminator: &mir::Terminator<'tcx>, @@ -582,7 +576,7 @@ impl<'tcx> rustc_mir_dataflow::GenKillAnalysis<'tcx> for Borrows<'_, 'tcx> { self.kill_loans_out_of_scope_at_location(trans, location); } - fn terminator_effect<'mir>( + fn apply_terminator_effect<'mir>( &mut self, trans: &mut Self::Domain, terminator: &'mir mir::Terminator<'tcx>, @@ -599,14 +593,6 @@ impl<'tcx> rustc_mir_dataflow::GenKillAnalysis<'tcx> for Borrows<'_, 'tcx> { } terminator.edges() } - - fn call_return_effect( - &mut self, - _trans: &mut Self::Domain, - _block: mir::BasicBlock, - _return_places: CallReturnPlaces<'_, 'tcx>, - ) { - } } impl<C> DebugWithContext<C> for BorrowIndex {} diff --git a/compiler/rustc_const_eval/src/check_consts/resolver.rs b/compiler/rustc_const_eval/src/check_consts/resolver.rs index eb5024c36f4..74eb6b37fbb 100644 --- a/compiler/rustc_const_eval/src/check_consts/resolver.rs +++ b/compiler/rustc_const_eval/src/check_consts/resolver.rs @@ -11,7 +11,7 @@ use rustc_middle::mir::{ self, BasicBlock, CallReturnPlaces, Local, Location, Statement, StatementKind, TerminatorEdges, }; use rustc_mir_dataflow::fmt::DebugWithContext; -use rustc_mir_dataflow::{Analysis, AnalysisDomain, JoinSemiLattice}; +use rustc_mir_dataflow::{Analysis, JoinSemiLattice}; use super::{ConstCx, Qualif, qualifs}; @@ -310,7 +310,7 @@ impl JoinSemiLattice for State { } } -impl<'tcx, Q> AnalysisDomain<'tcx> for FlowSensitiveAnalysis<'_, '_, 'tcx, Q> +impl<'tcx, Q> Analysis<'tcx> for FlowSensitiveAnalysis<'_, '_, 'tcx, Q> where Q: Qualif, { @@ -328,12 +328,7 @@ where fn initialize_start_block(&self, _body: &mir::Body<'tcx>, state: &mut Self::Domain) { self.transfer_function(state).initialize_state(); } -} -impl<'tcx, Q> Analysis<'tcx> for FlowSensitiveAnalysis<'_, '_, 'tcx, Q> -where - Q: Qualif, -{ fn apply_statement_effect( &mut self, state: &mut Self::Domain, diff --git a/compiler/rustc_middle/src/mir/basic_blocks.rs b/compiler/rustc_middle/src/mir/basic_blocks.rs index 4602c918160..3eb563d7d6e 100644 --- a/compiler/rustc_middle/src/mir/basic_blocks.rs +++ b/compiler/rustc_middle/src/mir/basic_blocks.rs @@ -26,7 +26,6 @@ type SwitchSources = FxHashMap<(BasicBlock, BasicBlock), SmallVec<[Option<u128>; struct Cache { predecessors: OnceLock<Predecessors>, switch_sources: OnceLock<SwitchSources>, - is_cyclic: OnceLock<bool>, reverse_postorder: OnceLock<Vec<BasicBlock>>, dominators: OnceLock<Dominators<BasicBlock>>, } @@ -37,12 +36,6 @@ impl<'tcx> BasicBlocks<'tcx> { BasicBlocks { basic_blocks, cache: Cache::default() } } - /// Returns true if control-flow graph contains a cycle reachable from the `START_BLOCK`. - #[inline] - pub fn is_cfg_cyclic(&self) -> bool { - *self.cache.is_cyclic.get_or_init(|| graph::is_cyclic(self)) - } - pub fn dominators(&self) -> &Dominators<BasicBlock> { self.cache.dominators.get_or_init(|| dominators(self)) } diff --git a/compiler/rustc_mir_dataflow/src/framework/cursor.rs b/compiler/rustc_mir_dataflow/src/framework/cursor.rs index 7cfaef22689..5ebb343f4e1 100644 --- a/compiler/rustc_mir_dataflow/src/framework/cursor.rs +++ b/compiler/rustc_mir_dataflow/src/framework/cursor.rs @@ -7,7 +7,6 @@ use rustc_index::bit_set::BitSet; use rustc_middle::mir::{self, BasicBlock, Location}; use super::{Analysis, Direction, Effect, EffectIndex, Results}; -use crate::framework::BitSetExt; /// Allows random access inspection of the results of a dataflow analysis. /// @@ -221,16 +220,6 @@ where } } -impl<'mir, 'tcx, A> ResultsCursor<'mir, 'tcx, A> -where - A: crate::GenKillAnalysis<'tcx>, - A::Domain: BitSetExt<A::Idx>, -{ - pub fn contains(&self, elem: A::Idx) -> bool { - self.get().contains(elem) - } -} - #[derive(Clone, Copy, Debug)] struct CursorPosition { block: BasicBlock, diff --git a/compiler/rustc_mir_dataflow/src/framework/direction.rs b/compiler/rustc_mir_dataflow/src/framework/direction.rs index 88a9a78f8ad..3e01f0512c4 100644 --- a/compiler/rustc_mir_dataflow/src/framework/direction.rs +++ b/compiler/rustc_mir_dataflow/src/framework/direction.rs @@ -5,7 +5,7 @@ use rustc_middle::mir::{ }; use super::visitor::{ResultsVisitable, ResultsVisitor}; -use super::{Analysis, Effect, EffectIndex, GenKillAnalysis, GenKillSet, SwitchIntTarget}; +use super::{Analysis, Effect, EffectIndex, SwitchIntTarget}; pub trait Direction { const IS_FORWARD: bool; @@ -29,19 +29,10 @@ pub trait Direction { state: &mut A::Domain, block: BasicBlock, block_data: &'mir mir::BasicBlockData<'tcx>, - statement_effect: Option<&dyn Fn(BasicBlock, &mut A::Domain)>, ) -> TerminatorEdges<'mir, 'tcx> where A: Analysis<'tcx>; - fn gen_kill_statement_effects_in_block<'tcx, A>( - analysis: &mut A, - trans: &mut GenKillSet<A::Idx>, - block: BasicBlock, - block_data: &mir::BasicBlockData<'tcx>, - ) where - A: GenKillAnalysis<'tcx>; - fn visit_results_in_block<'mir, 'tcx, D, R>( state: &mut D, block: BasicBlock, @@ -73,7 +64,6 @@ impl Direction for Backward { state: &mut A::Domain, block: BasicBlock, block_data: &'mir mir::BasicBlockData<'tcx>, - statement_effect: Option<&dyn Fn(BasicBlock, &mut A::Domain)>, ) -> TerminatorEdges<'mir, 'tcx> where A: Analysis<'tcx>, @@ -82,31 +72,12 @@ impl Direction for Backward { let location = Location { block, statement_index: block_data.statements.len() }; analysis.apply_before_terminator_effect(state, terminator, location); let edges = analysis.apply_terminator_effect(state, terminator, location); - if let Some(statement_effect) = statement_effect { - statement_effect(block, state) - } else { - for (statement_index, statement) in block_data.statements.iter().enumerate().rev() { - let location = Location { block, statement_index }; - analysis.apply_before_statement_effect(state, statement, location); - analysis.apply_statement_effect(state, statement, location); - } - } - edges - } - - fn gen_kill_statement_effects_in_block<'tcx, A>( - analysis: &mut A, - trans: &mut GenKillSet<A::Idx>, - block: BasicBlock, - block_data: &mir::BasicBlockData<'tcx>, - ) where - A: GenKillAnalysis<'tcx>, - { for (statement_index, statement) in block_data.statements.iter().enumerate().rev() { let location = Location { block, statement_index }; - analysis.before_statement_effect(trans, statement, location); - analysis.statement_effect(trans, statement, location); + analysis.apply_before_statement_effect(state, statement, location); + analysis.apply_statement_effect(state, statement, location); } + edges } fn apply_effects_in_range<'tcx, A>( @@ -330,42 +301,21 @@ impl Direction for Forward { state: &mut A::Domain, block: BasicBlock, block_data: &'mir mir::BasicBlockData<'tcx>, - statement_effect: Option<&dyn Fn(BasicBlock, &mut A::Domain)>, ) -> TerminatorEdges<'mir, 'tcx> where A: Analysis<'tcx>, { - if let Some(statement_effect) = statement_effect { - statement_effect(block, state) - } else { - for (statement_index, statement) in block_data.statements.iter().enumerate() { - let location = Location { block, statement_index }; - analysis.apply_before_statement_effect(state, statement, location); - analysis.apply_statement_effect(state, statement, location); - } + for (statement_index, statement) in block_data.statements.iter().enumerate() { + let location = Location { block, statement_index }; + analysis.apply_before_statement_effect(state, statement, location); + analysis.apply_statement_effect(state, statement, location); } - let terminator = block_data.terminator(); let location = Location { block, statement_index: block_data.statements.len() }; analysis.apply_before_terminator_effect(state, terminator, location); analysis.apply_terminator_effect(state, terminator, location) } - fn gen_kill_statement_effects_in_block<'tcx, A>( - analysis: &mut A, - trans: &mut GenKillSet<A::Idx>, - block: BasicBlock, - block_data: &mir::BasicBlockData<'tcx>, - ) where - A: GenKillAnalysis<'tcx>, - { - for (statement_index, statement) in block_data.statements.iter().enumerate() { - let location = Location { block, statement_index }; - analysis.before_statement_effect(trans, statement, location); - analysis.statement_effect(trans, statement, location); - } - } - fn apply_effects_in_range<'tcx, A>( analysis: &mut A, state: &mut A::Domain, diff --git a/compiler/rustc_mir_dataflow/src/framework/engine.rs b/compiler/rustc_mir_dataflow/src/framework/engine.rs index 9d50e57d668..cbd1083d037 100644 --- a/compiler/rustc_mir_dataflow/src/framework/engine.rs +++ b/compiler/rustc_mir_dataflow/src/framework/engine.rs @@ -5,7 +5,7 @@ use std::path::PathBuf; use rustc_data_structures::work_queue::WorkQueue; use rustc_hir::def_id::DefId; -use rustc_index::{Idx, IndexVec}; +use rustc_index::IndexVec; use rustc_middle::bug; use rustc_middle::mir::{self, BasicBlock, create_dump_file, dump_enabled, traversal}; use rustc_middle::ty::TyCtxt; @@ -16,15 +16,13 @@ use {rustc_ast as ast, rustc_graphviz as dot}; use super::fmt::DebugWithContext; use super::{ - Analysis, AnalysisDomain, Direction, GenKill, GenKillAnalysis, GenKillSet, JoinSemiLattice, - ResultsCursor, ResultsVisitor, graphviz, visit_results, + Analysis, Direction, JoinSemiLattice, ResultsCursor, ResultsVisitor, graphviz, visit_results, }; use crate::errors::{ DuplicateValuesFor, PathMustEndInFilename, RequiresAnArgument, UnknownFormatter, }; -use crate::framework::BitSetExt; -type EntrySets<'tcx, A> = IndexVec<BasicBlock, <A as AnalysisDomain<'tcx>>::Domain>; +type EntrySets<'tcx, A> = IndexVec<BasicBlock, <A as Analysis<'tcx>>::Domain>; /// A dataflow analysis that has converged to fixpoint. #[derive(Clone)] @@ -82,53 +80,6 @@ where entry_sets: IndexVec<BasicBlock, A::Domain>, pass_name: Option<&'static str>, analysis: A, - - /// Cached, cumulative transfer functions for each block. - // - // FIXME(ecstaticmorse): This boxed `Fn` trait object is invoked inside a tight loop for - // gen/kill problems on cyclic CFGs. This is not ideal, but it doesn't seem to degrade - // performance in practice. I've tried a few ways to avoid this, but they have downsides. See - // the message for the commit that added this FIXME for more information. - apply_statement_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>, -} - -impl<'mir, 'tcx, A, D, T> Engine<'mir, 'tcx, A> -where - A: GenKillAnalysis<'tcx, Idx = T, Domain = D>, - D: Clone + JoinSemiLattice + GenKill<T> + BitSetExt<T>, - T: Idx, -{ - /// Creates a new `Engine` to solve a gen-kill dataflow problem. - pub fn new_gen_kill(tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>, mut analysis: A) -> Self { - // If there are no back-edges in the control-flow graph, we only ever need to apply the - // transfer function for each block exactly once (assuming that we process blocks in RPO). - // - // In this case, there's no need to compute the block transfer functions ahead of time. - if !body.basic_blocks.is_cfg_cyclic() { - return Self::new(tcx, body, analysis, None); - } - - // Otherwise, compute and store the cumulative transfer function for each block. - - let identity = GenKillSet::identity(analysis.domain_size(body)); - let mut trans_for_block = IndexVec::from_elem(identity, &body.basic_blocks); - - for (block, block_data) in body.basic_blocks.iter_enumerated() { - let trans = &mut trans_for_block[block]; - A::Direction::gen_kill_statement_effects_in_block( - &mut analysis, - trans, - block, - block_data, - ); - } - - let apply_trans = Box::new(move |bb: BasicBlock, state: &mut A::Domain| { - trans_for_block[bb].apply(state); - }); - - Self::new(tcx, body, analysis, Some(apply_trans as Box<_>)) - } } impl<'mir, 'tcx, A, D> Engine<'mir, 'tcx, A> @@ -138,19 +89,7 @@ where { /// Creates a new `Engine` to solve a dataflow problem with an arbitrary transfer /// function. - /// - /// Gen-kill problems should use `new_gen_kill`, which will coalesce transfer functions for - /// better performance. - pub fn new_generic(tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>, analysis: A) -> Self { - Self::new(tcx, body, analysis, None) - } - - fn new( - tcx: TyCtxt<'tcx>, - body: &'mir mir::Body<'tcx>, - analysis: A, - apply_statement_trans_for_block: Option<Box<dyn Fn(BasicBlock, &mut A::Domain)>>, - ) -> Self { + pub(crate) fn new(tcx: TyCtxt<'tcx>, body: &'mir mir::Body<'tcx>, analysis: A) -> Self { let mut entry_sets = IndexVec::from_fn_n(|_| analysis.bottom_value(body), body.basic_blocks.len()); analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]); @@ -160,7 +99,7 @@ where bug!("`initialize_start_block` is not yet supported for backward dataflow analyses"); } - Engine { analysis, tcx, body, pass_name: None, entry_sets, apply_statement_trans_for_block } + Engine { analysis, tcx, body, pass_name: None, entry_sets } } /// Adds an identifier to the graphviz output for this particular run of a dataflow analysis. @@ -177,14 +116,7 @@ where where A::Domain: DebugWithContext<A>, { - let Engine { - mut analysis, - body, - mut entry_sets, - tcx, - apply_statement_trans_for_block, - pass_name, - } = self; + let Engine { mut analysis, body, mut entry_sets, tcx, pass_name } = self; let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks.len()); @@ -213,13 +145,8 @@ where state.clone_from(&entry_sets[bb]); // Apply the block transfer function, using the cached one if it exists. - let edges = A::Direction::apply_effects_in_block( - &mut analysis, - &mut state, - bb, - bb_data, - apply_statement_trans_for_block.as_deref(), - ); + let edges = + A::Direction::apply_effects_in_block(&mut analysis, &mut state, bb, bb_data); A::Direction::join_state_into_successors_of( &mut analysis, diff --git a/compiler/rustc_mir_dataflow/src/framework/mod.rs b/compiler/rustc_mir_dataflow/src/framework/mod.rs index d0472e35fe0..959f1ea5340 100644 --- a/compiler/rustc_mir_dataflow/src/framework/mod.rs +++ b/compiler/rustc_mir_dataflow/src/framework/mod.rs @@ -1,9 +1,11 @@ //! A framework that can express both [gen-kill] and generic dataflow problems. //! -//! To use this framework, implement either the [`Analysis`] or the -//! [`GenKillAnalysis`] trait. If your transfer function can be expressed with only gen/kill -//! operations, prefer `GenKillAnalysis` since it will run faster while iterating to fixpoint. The -//! `impls` module contains several examples of gen/kill dataflow analyses. +//! To use this framework, implement the [`Analysis`] trait. There used to be a `GenKillAnalysis` +//! alternative trait for gen-kill analyses that would pre-compute the transfer function for each +//! block. It was intended as an optimization, but it ended up not being any faster than +//! `Analysis`. +//! +//! The `impls` module contains several examples of dataflow analyses. //! //! Create an `Engine` for your analysis using the `into_engine` method on the `Analysis` trait, //! then call `iterate_to_fixpoint`. From there, you can use a `ResultsCursor` to inspect the @@ -87,11 +89,26 @@ impl<T: Idx> BitSetExt<T> for ChunkedBitSet<T> { } } -/// Defines the domain of a dataflow problem. +/// A dataflow problem with an arbitrarily complex transfer function. +/// +/// This trait specifies the lattice on which this analysis operates (the domain), its +/// initial value at the entry point of each basic block, and various operations. +/// +/// # Convergence +/// +/// When implementing this trait it's possible to choose a transfer function such that the analysis +/// does not reach fixpoint. To guarantee convergence, your transfer functions must maintain the +/// following invariant: +/// +/// > If the dataflow state **before** some point in the program changes to be greater +/// than the prior state **before** that point, the dataflow state **after** that point must +/// also change to be greater than the prior state **after** that point. /// -/// This trait specifies the lattice on which this analysis operates (the domain) as well as its -/// initial value at the entry point of each basic block. -pub trait AnalysisDomain<'tcx> { +/// This invariant guarantees that the dataflow state at a given point in the program increases +/// monotonically until fixpoint is reached. Note that this monotonicity requirement only applies +/// to the same point in the program at different points in time. The dataflow state at a given +/// point in the program may or may not be greater than the state at any preceding point. +pub trait Analysis<'tcx> { /// The type that holds the dataflow state at any given point in the program. type Domain: Clone + JoinSemiLattice; @@ -116,25 +133,7 @@ pub trait AnalysisDomain<'tcx> { // block where control flow could exit the MIR body (e.g., those terminated with `return` or // `resume`). It's not obvious how to handle `yield` points in coroutines, however. fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain); -} -/// A dataflow problem with an arbitrarily complex transfer function. -/// -/// # Convergence -/// -/// When implementing this trait directly (not via [`GenKillAnalysis`]), it's possible to choose a -/// transfer function such that the analysis does not reach fixpoint. To guarantee convergence, -/// your transfer functions must maintain the following invariant: -/// -/// > If the dataflow state **before** some point in the program changes to be greater -/// than the prior state **before** that point, the dataflow state **after** that point must -/// also change to be greater than the prior state **after** that point. -/// -/// This invariant guarantees that the dataflow state at a given point in the program increases -/// monotonically until fixpoint is reached. Note that this monotonicity requirement only applies -/// to the same point in the program at different points in time. The dataflow state at a given -/// point in the program may or may not be greater than the state at any preceding point. -pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { /// Updates the current dataflow state with the effect of evaluating a statement. fn apply_statement_effect( &mut self, @@ -165,10 +164,12 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { /// initialized here. fn apply_terminator_effect<'mir>( &mut self, - state: &mut Self::Domain, + _state: &mut Self::Domain, terminator: &'mir mir::Terminator<'tcx>, - location: Location, - ) -> TerminatorEdges<'mir, 'tcx>; + _location: Location, + ) -> TerminatorEdges<'mir, 'tcx> { + terminator.edges() + } /// Updates the current dataflow state with an effect that occurs immediately *before* the /// given terminator. @@ -193,10 +194,11 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { /// edges. fn apply_call_return_effect( &mut self, - state: &mut Self::Domain, - block: BasicBlock, - return_places: CallReturnPlaces<'_, 'tcx>, - ); + _state: &mut Self::Domain, + _block: BasicBlock, + _return_places: CallReturnPlaces<'_, 'tcx>, + ) { + } /// Updates the current dataflow state with the effect of taking a particular branch in a /// `SwitchInt` terminator. @@ -223,9 +225,7 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { /// Creates an `Engine` to find the fixpoint for this dataflow problem. /// - /// You shouldn't need to override this outside this module, since the combination of the - /// default impl and the one for all `A: GenKillAnalysis` will do the right thing. - /// Its purpose is to enable method chaining like so: + /// You shouldn't need to override this. Its purpose is to enable method chaining like so: /// /// ```ignore (cross-crate-imports) /// let results = MyAnalysis::new(tcx, body) @@ -242,164 +242,11 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> { where Self: Sized, { - Engine::new_generic(tcx, body, self) - } -} - -/// A gen/kill dataflow problem. -/// -/// Each method in this trait has a corresponding one in `Analysis`. However, the first two methods -/// here only allow modification of the dataflow state via "gen" and "kill" operations. By defining -/// transfer functions for each statement in this way, the transfer function for an entire basic -/// block can be computed efficiently. The remaining methods match up with `Analysis` exactly. -/// -/// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis` via a blanket -/// impl below. -pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> { - type Idx: Idx; - - fn domain_size(&self, body: &mir::Body<'tcx>) -> usize; - - /// See `Analysis::apply_statement_effect`. Note how the second arg differs. - fn statement_effect( - &mut self, - trans: &mut impl GenKill<Self::Idx>, - statement: &mir::Statement<'tcx>, - location: Location, - ); - - /// See `Analysis::apply_before_statement_effect`. Note how the second arg - /// differs. - fn before_statement_effect( - &mut self, - _trans: &mut impl GenKill<Self::Idx>, - _statement: &mir::Statement<'tcx>, - _location: Location, - ) { - } - - /// See `Analysis::apply_terminator_effect`. - fn terminator_effect<'mir>( - &mut self, - trans: &mut Self::Domain, - terminator: &'mir mir::Terminator<'tcx>, - location: Location, - ) -> TerminatorEdges<'mir, 'tcx>; - - /// See `Analysis::apply_before_terminator_effect`. - fn before_terminator_effect( - &mut self, - _trans: &mut Self::Domain, - _terminator: &mir::Terminator<'tcx>, - _location: Location, - ) { - } - - /* Edge-specific effects */ - - /// See `Analysis::apply_call_return_effect`. - fn call_return_effect( - &mut self, - trans: &mut Self::Domain, - block: BasicBlock, - return_places: CallReturnPlaces<'_, 'tcx>, - ); - - /// See `Analysis::apply_switch_int_edge_effects`. - fn switch_int_edge_effects<G: GenKill<Self::Idx>>( - &mut self, - _block: BasicBlock, - _discr: &mir::Operand<'tcx>, - _edge_effects: &mut impl SwitchIntEdgeEffects<G>, - ) { - } -} - -// Blanket impl: any impl of `GenKillAnalysis` automatically impls `Analysis`. -impl<'tcx, A> Analysis<'tcx> for A -where - A: GenKillAnalysis<'tcx>, - A::Domain: GenKill<A::Idx> + BitSetExt<A::Idx>, -{ - fn apply_statement_effect( - &mut self, - state: &mut A::Domain, - statement: &mir::Statement<'tcx>, - location: Location, - ) { - self.statement_effect(state, statement, location); - } - - fn apply_before_statement_effect( - &mut self, - state: &mut A::Domain, - statement: &mir::Statement<'tcx>, - location: Location, - ) { - self.before_statement_effect(state, statement, location); - } - - fn apply_terminator_effect<'mir>( - &mut self, - state: &mut A::Domain, - terminator: &'mir mir::Terminator<'tcx>, - location: Location, - ) -> TerminatorEdges<'mir, 'tcx> { - self.terminator_effect(state, terminator, location) - } - - fn apply_before_terminator_effect( - &mut self, - state: &mut A::Domain, - terminator: &mir::Terminator<'tcx>, - location: Location, - ) { - self.before_terminator_effect(state, terminator, location); - } - - /* Edge-specific effects */ - - fn apply_call_return_effect( - &mut self, - state: &mut A::Domain, - block: BasicBlock, - return_places: CallReturnPlaces<'_, 'tcx>, - ) { - self.call_return_effect(state, block, return_places); - } - - fn apply_switch_int_edge_effects( - &mut self, - block: BasicBlock, - discr: &mir::Operand<'tcx>, - edge_effects: &mut impl SwitchIntEdgeEffects<A::Domain>, - ) { - self.switch_int_edge_effects(block, discr, edge_effects); - } - - /* Extension methods */ - #[inline] - fn into_engine<'mir>( - self, - tcx: TyCtxt<'tcx>, - body: &'mir mir::Body<'tcx>, - ) -> Engine<'mir, 'tcx, Self> - where - Self: Sized, - { - Engine::new_gen_kill(tcx, body, self) + Engine::new(tcx, body, self) } } /// The legal operations for a transfer function in a gen/kill problem. -/// -/// This abstraction exists because there are two different contexts in which we call the methods in -/// `GenKillAnalysis`. Sometimes we need to store a single transfer function that can be efficiently -/// applied multiple times, such as when computing the cumulative transfer function for each block. -/// These cases require a `GenKillSet`, which in turn requires two `BitSet`s of storage. Oftentimes, -/// however, we only need to apply an effect once. In *these* cases, it is more efficient to pass the -/// `BitSet` representing the state vector directly into the `*_effect` methods as opposed to -/// building up a `GenKillSet` and then throwing it away. pub trait GenKill<T> { /// Inserts `elem` into the state vector. fn gen_(&mut self, elem: T); @@ -422,44 +269,6 @@ pub trait GenKill<T> { } } -/// Stores a transfer function for a gen/kill problem. -/// -/// Calling `gen_`/`kill` on a `GenKillSet` will "build up" a transfer function so that it can be -/// applied multiple times efficiently. When there are multiple calls to `gen_` and/or `kill` for -/// the same element, the most recent one takes precedence. -#[derive(Clone)] -pub struct GenKillSet<T> { - gen_: HybridBitSet<T>, - kill: HybridBitSet<T>, -} - -impl<T: Idx> GenKillSet<T> { - /// Creates a new transfer function that will leave the dataflow state unchanged. - pub fn identity(universe: usize) -> Self { - GenKillSet { - gen_: HybridBitSet::new_empty(universe), - kill: HybridBitSet::new_empty(universe), - } - } - - pub fn apply(&self, state: &mut impl BitSetExt<T>) { - state.union(&self.gen_); - state.subtract(&self.kill); - } -} - -impl<T: Idx> GenKill<T> for GenKillSet<T> { - fn gen_(&mut self, elem: T) { - self.gen_.insert(elem); - self.kill.remove(elem); - } - - fn kill(&mut self, elem: T) { - self.kill.insert(elem); - self.gen_.remove(elem); - } -} - impl<T: Idx> GenKill<T> for BitSet<T> { fn gen_(&mut self, elem: T) { self.insert(elem); diff --git a/compiler/rustc_mir_dataflow/src/framework/tests.rs b/compiler/rustc_mir_dataflow/src/framework/tests.rs index 1861f4cffc7..14fb6dfb50c 100644 --- a/compiler/rustc_mir_dataflow/src/framework/tests.rs +++ b/compiler/rustc_mir_dataflow/src/framework/tests.rs @@ -154,7 +154,7 @@ impl<D: Direction> MockAnalysis<'_, D> { } } -impl<'tcx, D: Direction> AnalysisDomain<'tcx> for MockAnalysis<'tcx, D> { +impl<'tcx, D: Direction> Analysis<'tcx> for MockAnalysis<'tcx, D> { type Domain = BitSet<usize>; type Direction = D; @@ -167,9 +167,7 @@ impl<'tcx, D: Direction> AnalysisDomain<'tcx> for MockAnalysis<'tcx, D> { fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) { unimplemented!("This is never called since `MockAnalysis` is never iterated to fixpoint"); } -} -impl<'tcx, D: Direction> Analysis<'tcx> for MockAnalysis<'tcx, D> { fn apply_statement_effect( &mut self, state: &mut Self::Domain, @@ -210,14 +208,6 @@ impl<'tcx, D: Direction> Analysis<'tcx> for MockAnalysis<'tcx, D> { let idx = self.effect(Effect::Before.at_index(location.statement_index)); assert!(state.insert(idx)); } - - fn apply_call_return_effect( - &mut self, - _state: &mut Self::Domain, - _block: BasicBlock, - _return_places: CallReturnPlaces<'_, 'tcx>, - ) { - } } #[derive(Clone, Copy, Debug, PartialEq, Eq)] diff --git a/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs b/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs index 8b082ef2667..859019fd1f6 100644 --- a/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs +++ b/compiler/rustc_mir_dataflow/src/impls/borrowed_locals.rs @@ -2,7 +2,7 @@ use rustc_index::bit_set::BitSet; use rustc_middle::mir::visit::Visitor; use rustc_middle::mir::*; -use crate::{AnalysisDomain, GenKill, GenKillAnalysis}; +use crate::{Analysis, GenKill}; /// A dataflow analysis that tracks whether a pointer or reference could possibly exist that points /// to a given local. This analysis ignores fake borrows, so it should not be used by @@ -20,7 +20,7 @@ impl MaybeBorrowedLocals { } } -impl<'tcx> AnalysisDomain<'tcx> for MaybeBorrowedLocals { +impl<'tcx> Analysis<'tcx> for MaybeBorrowedLocals { type Domain = BitSet<Local>; const NAME: &'static str = "maybe_borrowed_locals"; @@ -32,25 +32,17 @@ impl<'tcx> AnalysisDomain<'tcx> for MaybeBorrowedLocals { fn initialize_start_block(&self, _: &Body<'tcx>, _: &mut Self::Domain) { // No locals are aliased on function entry } -} - -impl<'tcx> GenKillAnalysis<'tcx> for MaybeBorrowedLocals { - type Idx = Local; - fn domain_size(&self, body: &Body<'tcx>) -> usize { - body.local_decls.len() - } - - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, statement: &Statement<'tcx>, location: Location, ) { self.transfer_function(trans).visit_statement(statement, location); } - fn terminator_effect<'mir>( + fn apply_terminator_effect<'mir>( &mut self, trans: &mut Self::Domain, terminator: &'mir Terminator<'tcx>, @@ -59,14 +51,6 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeBorrowedLocals { self.transfer_function(trans).visit_terminator(terminator, location); terminator.edges() } - - fn call_return_effect( - &mut self, - _trans: &mut Self::Domain, - _block: BasicBlock, - _return_places: CallReturnPlaces<'_, 'tcx>, - ) { - } } /// A `Visitor` that defines the transfer function for `MaybeBorrowedLocals`. diff --git a/compiler/rustc_mir_dataflow/src/impls/initialized.rs b/compiler/rustc_mir_dataflow/src/impls/initialized.rs index 25e8726cf61..9bb50d1e056 100644 --- a/compiler/rustc_mir_dataflow/src/impls/initialized.rs +++ b/compiler/rustc_mir_dataflow/src/impls/initialized.rs @@ -11,9 +11,8 @@ use crate::elaborate_drops::DropFlagState; use crate::framework::SwitchIntEdgeEffects; use crate::move_paths::{HasMoveData, InitIndex, InitKind, LookupResult, MoveData, MovePathIndex}; use crate::{ - AnalysisDomain, GenKill, GenKillAnalysis, MaybeReachable, drop_flag_effects, - drop_flag_effects_for_function_entry, drop_flag_effects_for_location, lattice, - on_all_children_bits, on_lookup_result_bits, + Analysis, GenKill, MaybeReachable, drop_flag_effects, drop_flag_effects_for_function_entry, + drop_flag_effects_for_location, lattice, on_all_children_bits, on_lookup_result_bits, }; /// `MaybeInitializedPlaces` tracks all places that might be @@ -270,7 +269,7 @@ impl<'tcx> HasMoveData<'tcx> for EverInitializedPlaces<'_, 'tcx> { impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> { fn update_bits( - trans: &mut impl GenKill<MovePathIndex>, + trans: &mut <Self as Analysis<'tcx>>::Domain, path: MovePathIndex, state: DropFlagState, ) { @@ -283,7 +282,7 @@ impl<'a, 'tcx> MaybeInitializedPlaces<'a, 'tcx> { impl<'tcx> MaybeUninitializedPlaces<'_, 'tcx> { fn update_bits( - trans: &mut impl GenKill<MovePathIndex>, + trans: &mut <Self as Analysis<'tcx>>::Domain, path: MovePathIndex, state: DropFlagState, ) { @@ -296,7 +295,7 @@ impl<'tcx> MaybeUninitializedPlaces<'_, 'tcx> { impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> { fn update_bits( - trans: &mut impl GenKill<MovePathIndex>, + trans: &mut <Self as Analysis<'tcx>>::Domain, path: MovePathIndex, state: DropFlagState, ) { @@ -307,7 +306,7 @@ impl<'a, 'tcx> DefinitelyInitializedPlaces<'a, 'tcx> { } } -impl<'tcx> AnalysisDomain<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { +impl<'tcx> Analysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { /// There can be many more `MovePathIndex` than there are locals in a MIR body. /// We use a chunked bitset to avoid paying too high a memory footprint. type Domain = MaybeReachable<ChunkedBitSet<MovePathIndex>>; @@ -327,18 +326,10 @@ impl<'tcx> AnalysisDomain<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { state.gen_(path); }); } -} - -impl<'tcx> GenKillAnalysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { - type Idx = MovePathIndex; - fn domain_size(&self, _: &Body<'tcx>) -> usize { - self.move_data().move_paths.len() - } - - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, statement: &mir::Statement<'tcx>, location: Location, ) { @@ -360,7 +351,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { } } - fn terminator_effect<'mir>( + fn apply_terminator_effect<'mir>( &mut self, state: &mut Self::Domain, terminator: &'mir mir::Terminator<'tcx>, @@ -380,7 +371,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { edges } - fn call_return_effect( + fn apply_call_return_effect( &mut self, trans: &mut Self::Domain, _block: mir::BasicBlock, @@ -399,11 +390,11 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { }); } - fn switch_int_edge_effects<G: GenKill<Self::Idx>>( + fn apply_switch_int_edge_effects( &mut self, block: mir::BasicBlock, discr: &mir::Operand<'tcx>, - edge_effects: &mut impl SwitchIntEdgeEffects<G>, + edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>, ) { if !self.tcx.sess.opts.unstable_opts.precise_enum_drop_elaboration { return; @@ -442,7 +433,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeInitializedPlaces<'_, 'tcx> { } } -impl<'tcx> AnalysisDomain<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { +impl<'tcx> Analysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { /// There can be many more `MovePathIndex` than there are locals in a MIR body. /// We use a chunked bitset to avoid paying too high a memory footprint. type Domain = ChunkedBitSet<MovePathIndex>; @@ -464,18 +455,10 @@ impl<'tcx> AnalysisDomain<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { state.remove(path); }); } -} - -impl<'tcx> GenKillAnalysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { - type Idx = MovePathIndex; - fn domain_size(&self, _: &Body<'tcx>) -> usize { - self.move_data().move_paths.len() - } - - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, _statement: &mir::Statement<'tcx>, location: Location, ) { @@ -487,7 +470,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { // mutable borrow occurs. Places cannot become uninitialized through a mutable reference. } - fn terminator_effect<'mir>( + fn apply_terminator_effect<'mir>( &mut self, trans: &mut Self::Domain, terminator: &'mir mir::Terminator<'tcx>, @@ -505,7 +488,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { } } - fn call_return_effect( + fn apply_call_return_effect( &mut self, trans: &mut Self::Domain, _block: mir::BasicBlock, @@ -524,11 +507,11 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { }); } - fn switch_int_edge_effects<G: GenKill<Self::Idx>>( + fn apply_switch_int_edge_effects( &mut self, block: mir::BasicBlock, discr: &mir::Operand<'tcx>, - edge_effects: &mut impl SwitchIntEdgeEffects<G>, + edge_effects: &mut impl SwitchIntEdgeEffects<Self::Domain>, ) { if !self.tcx.sess.opts.unstable_opts.precise_enum_drop_elaboration { return; @@ -571,7 +554,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeUninitializedPlaces<'_, 'tcx> { } } -impl<'a, 'tcx> AnalysisDomain<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> { +impl<'a, 'tcx> Analysis<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> { /// Use set intersection as the join operator. type Domain = lattice::Dual<BitSet<MovePathIndex>>; @@ -591,18 +574,10 @@ impl<'a, 'tcx> AnalysisDomain<'tcx> for DefinitelyInitializedPlaces<'a, 'tcx> { state.0.insert(path); }); } -} - -impl<'tcx> GenKillAnalysis<'tcx> for DefinitelyInitializedPlaces<'_, 'tcx> { - type Idx = MovePathIndex; - fn domain_size(&self, _: &Body<'tcx>) -> usize { - self.move_data().move_paths.len() - } - - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, _statement: &mir::Statement<'tcx>, location: Location, ) { @@ -611,7 +586,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for DefinitelyInitializedPlaces<'_, 'tcx> { }) } - fn terminator_effect<'mir>( + fn apply_terminator_effect<'mir>( &mut self, trans: &mut Self::Domain, terminator: &'mir mir::Terminator<'tcx>, @@ -623,7 +598,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for DefinitelyInitializedPlaces<'_, 'tcx> { terminator.edges() } - fn call_return_effect( + fn apply_call_return_effect( &mut self, trans: &mut Self::Domain, _block: mir::BasicBlock, @@ -643,7 +618,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for DefinitelyInitializedPlaces<'_, 'tcx> { } } -impl<'tcx> AnalysisDomain<'tcx> for EverInitializedPlaces<'_, 'tcx> { +impl<'tcx> Analysis<'tcx> for EverInitializedPlaces<'_, 'tcx> { /// There can be many more `InitIndex` than there are locals in a MIR body. /// We use a chunked bitset to avoid paying too high a memory footprint. type Domain = ChunkedBitSet<InitIndex>; @@ -660,19 +635,11 @@ impl<'tcx> AnalysisDomain<'tcx> for EverInitializedPlaces<'_, 'tcx> { state.insert(InitIndex::new(arg_init)); } } -} - -impl<'tcx> GenKillAnalysis<'tcx> for EverInitializedPlaces<'_, 'tcx> { - type Idx = InitIndex; - - fn domain_size(&self, _: &Body<'tcx>) -> usize { - self.move_data().inits.len() - } #[instrument(skip(self, trans), level = "debug")] - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, stmt: &mir::Statement<'tcx>, location: Location, ) { @@ -698,7 +665,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for EverInitializedPlaces<'_, 'tcx> { } #[instrument(skip(self, trans, terminator), level = "debug")] - fn terminator_effect<'mir>( + fn apply_terminator_effect<'mir>( &mut self, trans: &mut Self::Domain, terminator: &'mir mir::Terminator<'tcx>, @@ -720,7 +687,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for EverInitializedPlaces<'_, 'tcx> { terminator.edges() } - fn call_return_effect( + fn apply_call_return_effect( &mut self, trans: &mut Self::Domain, block: mir::BasicBlock, diff --git a/compiler/rustc_mir_dataflow/src/impls/liveness.rs b/compiler/rustc_mir_dataflow/src/impls/liveness.rs index 1559c131a37..e06c1f2bb49 100644 --- a/compiler/rustc_mir_dataflow/src/impls/liveness.rs +++ b/compiler/rustc_mir_dataflow/src/impls/liveness.rs @@ -4,7 +4,7 @@ use rustc_middle::mir::{ self, CallReturnPlaces, Local, Location, Place, StatementKind, TerminatorEdges, }; -use crate::{Analysis, AnalysisDomain, Backward, GenKill, GenKillAnalysis}; +use crate::{Analysis, Backward, GenKill}; /// A [live-variable dataflow analysis][liveness]. /// @@ -25,7 +25,7 @@ use crate::{Analysis, AnalysisDomain, Backward, GenKill, GenKillAnalysis}; /// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis pub struct MaybeLiveLocals; -impl<'tcx> AnalysisDomain<'tcx> for MaybeLiveLocals { +impl<'tcx> Analysis<'tcx> for MaybeLiveLocals { type Domain = BitSet<Local>; type Direction = Backward; @@ -39,25 +39,17 @@ impl<'tcx> AnalysisDomain<'tcx> for MaybeLiveLocals { fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) { // No variables are live until we observe a use } -} - -impl<'tcx> GenKillAnalysis<'tcx> for MaybeLiveLocals { - type Idx = Local; - - fn domain_size(&self, body: &mir::Body<'tcx>) -> usize { - body.local_decls.len() - } - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, statement: &mir::Statement<'tcx>, location: Location, ) { TransferFunction(trans).visit_statement(statement, location); } - fn terminator_effect<'mir>( + fn apply_terminator_effect<'mir>( &mut self, trans: &mut Self::Domain, terminator: &'mir mir::Terminator<'tcx>, @@ -67,7 +59,7 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeLiveLocals { terminator.edges() } - fn call_return_effect( + fn apply_call_return_effect( &mut self, trans: &mut Self::Domain, _block: mir::BasicBlock, @@ -89,12 +81,9 @@ impl<'tcx> GenKillAnalysis<'tcx> for MaybeLiveLocals { } } -pub struct TransferFunction<'a, T>(pub &'a mut T); +pub struct TransferFunction<'a>(pub &'a mut BitSet<Local>); -impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T> -where - T: GenKill<Local>, -{ +impl<'tcx> Visitor<'tcx> for TransferFunction<'_> { fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) { if let PlaceContext::MutatingUse(MutatingUseContext::Yield) = context { // The resume place is evaluated and assigned to only after coroutine resumes, so its @@ -108,10 +97,10 @@ where MutatingUseContext::Call | MutatingUseContext::AsmOutput, ) = context { - // For the associated terminators, this is only a `Def` when the terminator returns - // "successfully." As such, we handle this case separately in `call_return_effect` - // above. However, if the place looks like `*_5`, this is still unconditionally a use of - // `_5`. + // For the associated terminators, this is only a `Def` when the terminator + // returns "successfully." As such, we handle this case separately in + // `call_return_effect` above. However, if the place looks like `*_5`, this is + // still unconditionally a use of `_5`. } else { self.0.kill(place.local); } @@ -128,12 +117,9 @@ where } } -struct YieldResumeEffect<'a, T>(&'a mut T); +struct YieldResumeEffect<'a>(&'a mut BitSet<Local>); -impl<'tcx, T> Visitor<'tcx> for YieldResumeEffect<'_, T> -where - T: GenKill<Local>, -{ +impl<'tcx> Visitor<'tcx> for YieldResumeEffect<'_> { fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) { DefUse::apply(self.0, *place, context); self.visit_projection(place.as_ref(), context, location); @@ -151,7 +137,7 @@ enum DefUse { } impl DefUse { - fn apply(trans: &mut impl GenKill<Local>, place: Place<'_>, context: PlaceContext) { + fn apply(trans: &mut BitSet<Local>, place: Place<'_>, context: PlaceContext) { match DefUse::for_place(place, context) { Some(DefUse::Def) => trans.kill(place.local), Some(DefUse::Use) => trans.gen_(place.local), @@ -231,7 +217,7 @@ impl<'a> MaybeTransitiveLiveLocals<'a> { } } -impl<'a, 'tcx> AnalysisDomain<'tcx> for MaybeTransitiveLiveLocals<'a> { +impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> { type Domain = BitSet<Local>; type Direction = Backward; @@ -245,9 +231,7 @@ impl<'a, 'tcx> AnalysisDomain<'tcx> for MaybeTransitiveLiveLocals<'a> { fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) { // No variables are live until we observe a use } -} -impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> { fn apply_statement_effect( &mut self, trans: &mut Self::Domain, diff --git a/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs b/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs index 34ac5809a2e..c5fd2a631ff 100644 --- a/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs +++ b/compiler/rustc_mir_dataflow/src/impls/storage_liveness.rs @@ -5,7 +5,7 @@ use rustc_middle::mir::visit::{NonMutatingUseContext, PlaceContext, Visitor}; use rustc_middle::mir::*; use super::MaybeBorrowedLocals; -use crate::{GenKill, ResultsCursor}; +use crate::{Analysis, GenKill, ResultsCursor}; pub struct MaybeStorageLive<'a> { always_live_locals: Cow<'a, BitSet<Local>>, @@ -17,7 +17,7 @@ impl<'a> MaybeStorageLive<'a> { } } -impl<'a, 'tcx> crate::AnalysisDomain<'tcx> for MaybeStorageLive<'a> { +impl<'a, 'tcx> Analysis<'tcx> for MaybeStorageLive<'a> { type Domain = BitSet<Local>; const NAME: &'static str = "maybe_storage_live"; @@ -37,18 +37,10 @@ impl<'a, 'tcx> crate::AnalysisDomain<'tcx> for MaybeStorageLive<'a> { on_entry.insert(arg); } } -} - -impl<'a, 'tcx> crate::GenKillAnalysis<'tcx> for MaybeStorageLive<'a> { - type Idx = Local; - fn domain_size(&self, body: &Body<'tcx>) -> usize { - body.local_decls.len() - } - - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, stmt: &Statement<'tcx>, _: Location, ) { @@ -58,25 +50,6 @@ impl<'a, 'tcx> crate::GenKillAnalysis<'tcx> for MaybeStorageLive<'a> { _ => (), } } - - fn terminator_effect<'mir>( - &mut self, - _trans: &mut Self::Domain, - terminator: &'mir Terminator<'tcx>, - _: Location, - ) -> TerminatorEdges<'mir, 'tcx> { - // Terminators have no effect - terminator.edges() - } - - fn call_return_effect( - &mut self, - _trans: &mut Self::Domain, - _block: BasicBlock, - _return_places: CallReturnPlaces<'_, 'tcx>, - ) { - // Nothing to do when a call returns successfully - } } pub struct MaybeStorageDead<'a> { @@ -89,7 +62,7 @@ impl<'a> MaybeStorageDead<'a> { } } -impl<'a, 'tcx> crate::AnalysisDomain<'tcx> for MaybeStorageDead<'a> { +impl<'a, 'tcx> Analysis<'tcx> for MaybeStorageDead<'a> { type Domain = BitSet<Local>; const NAME: &'static str = "maybe_storage_dead"; @@ -108,18 +81,10 @@ impl<'a, 'tcx> crate::AnalysisDomain<'tcx> for MaybeStorageDead<'a> { } } } -} - -impl<'a, 'tcx> crate::GenKillAnalysis<'tcx> for MaybeStorageDead<'a> { - type Idx = Local; - - fn domain_size(&self, body: &Body<'tcx>) -> usize { - body.local_decls.len() - } - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, stmt: &Statement<'tcx>, _: Location, ) { @@ -129,25 +94,6 @@ impl<'a, 'tcx> crate::GenKillAnalysis<'tcx> for MaybeStorageDead<'a> { _ => (), } } - - fn terminator_effect<'mir>( - &mut self, - _: &mut Self::Domain, - terminator: &'mir Terminator<'tcx>, - _: Location, - ) -> TerminatorEdges<'mir, 'tcx> { - // Terminators have no effect - terminator.edges() - } - - fn call_return_effect( - &mut self, - _trans: &mut Self::Domain, - _block: BasicBlock, - _return_places: CallReturnPlaces<'_, 'tcx>, - ) { - // Nothing to do when a call returns successfully - } } type BorrowedLocalsResults<'mir, 'tcx> = ResultsCursor<'mir, 'tcx, MaybeBorrowedLocals>; @@ -164,7 +110,7 @@ impl<'mir, 'tcx> MaybeRequiresStorage<'mir, 'tcx> { } } -impl<'tcx> crate::AnalysisDomain<'tcx> for MaybeRequiresStorage<'_, 'tcx> { +impl<'tcx> Analysis<'tcx> for MaybeRequiresStorage<'_, 'tcx> { type Domain = BitSet<Local>; const NAME: &'static str = "requires_storage"; @@ -181,23 +127,15 @@ impl<'tcx> crate::AnalysisDomain<'tcx> for MaybeRequiresStorage<'_, 'tcx> { on_entry.insert(arg); } } -} - -impl<'tcx> crate::GenKillAnalysis<'tcx> for MaybeRequiresStorage<'_, 'tcx> { - type Idx = Local; - fn domain_size(&self, body: &Body<'tcx>) -> usize { - body.local_decls.len() - } - - fn before_statement_effect( + fn apply_before_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, stmt: &Statement<'tcx>, loc: Location, ) { // If a place is borrowed in a statement, it needs storage for that statement. - self.borrowed_locals.mut_analysis().statement_effect(trans, stmt, loc); + self.borrowed_locals.mut_analysis().apply_statement_effect(trans, stmt, loc); match &stmt.kind { StatementKind::StorageDead(l) => trans.kill(*l), @@ -223,9 +161,9 @@ impl<'tcx> crate::GenKillAnalysis<'tcx> for MaybeRequiresStorage<'_, 'tcx> { } } - fn statement_effect( + fn apply_statement_effect( &mut self, - trans: &mut impl GenKill<Self::Idx>, + trans: &mut Self::Domain, _: &Statement<'tcx>, loc: Location, ) { @@ -234,7 +172,7 @@ impl<'tcx> crate::GenKillAnalysis<'tcx> for MaybeRequiresStorage<'_, 'tcx> { self.check_for_move(trans, loc); } - fn before_terminator_effect( + fn apply_before_terminator_effect( &mut self, trans: &mut Self::Domain, terminator: &Terminator<'tcx>, @@ -292,7 +230,7 @@ impl<'tcx> crate::GenKillAnalysis<'tcx> for MaybeRequiresStorage<'_, 'tcx> { } } - fn terminator_effect<'t>( + fn apply_terminator_effect<'t>( &mut self, trans: &mut Self::Domain, terminator: &'t Terminator<'tcx>, @@ -333,7 +271,7 @@ impl<'tcx> crate::GenKillAnalysis<'tcx> for MaybeRequiresStorage<'_, 'tcx> { terminator.edges() } - fn call_return_effect( + fn apply_call_return_effect( &mut self, trans: &mut Self::Domain, _block: BasicBlock, @@ -345,26 +283,23 @@ impl<'tcx> crate::GenKillAnalysis<'tcx> for MaybeRequiresStorage<'_, 'tcx> { impl<'tcx> MaybeRequiresStorage<'_, 'tcx> { /// Kill locals that are fully moved and have not been borrowed. - fn check_for_move(&mut self, trans: &mut impl GenKill<Local>, loc: Location) { + fn check_for_move(&mut self, trans: &mut <Self as Analysis<'tcx>>::Domain, loc: Location) { let body = self.borrowed_locals.body(); let mut visitor = MoveVisitor { trans, borrowed_locals: &mut self.borrowed_locals }; visitor.visit_location(body, loc); } } -struct MoveVisitor<'a, 'mir, 'tcx, T> { +struct MoveVisitor<'a, 'mir, 'tcx> { borrowed_locals: &'a mut BorrowedLocalsResults<'mir, 'tcx>, - trans: &'a mut T, + trans: &'a mut BitSet<Local>, } -impl<'tcx, T> Visitor<'tcx> for MoveVisitor<'_, '_, 'tcx, T> -where - T: GenKill<Local>, -{ +impl<'tcx> Visitor<'tcx> for MoveVisitor<'_, '_, 'tcx> { fn visit_local(&mut self, local: Local, context: PlaceContext, loc: Location) { if PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) == context { self.borrowed_locals.seek_before_primary_effect(loc); - if !self.borrowed_locals.contains(local) { + if !self.borrowed_locals.get().contains(local) { self.trans.kill(local); } } diff --git a/compiler/rustc_mir_dataflow/src/lib.rs b/compiler/rustc_mir_dataflow/src/lib.rs index cd926c07641..b284f0308f9 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, AnalysisDomain, Backward, Direction, Engine, Forward, GenKill, GenKillAnalysis, - JoinSemiLattice, MaybeReachable, Results, ResultsCursor, ResultsVisitable, ResultsVisitor, - SwitchIntEdgeEffects, fmt, graphviz, lattice, visit_results, + Analysis, Backward, Direction, Engine, Forward, GenKill, JoinSemiLattice, MaybeReachable, + Results, ResultsCursor, ResultsVisitable, ResultsVisitor, SwitchIntEdgeEffects, fmt, graphviz, + lattice, visit_results, }; use self::move_paths::MoveData; diff --git a/compiler/rustc_mir_dataflow/src/value_analysis.rs b/compiler/rustc_mir_dataflow/src/value_analysis.rs index aa09fe1dd45..faee40faa3f 100644 --- a/compiler/rustc_mir_dataflow/src/value_analysis.rs +++ b/compiler/rustc_mir_dataflow/src/value_analysis.rs @@ -51,7 +51,7 @@ use tracing::debug; use crate::fmt::DebugWithContext; use crate::lattice::{HasBottom, HasTop}; -use crate::{Analysis, AnalysisDomain, JoinSemiLattice, SwitchIntEdgeEffects}; +use crate::{Analysis, JoinSemiLattice, SwitchIntEdgeEffects}; pub trait ValueAnalysis<'tcx> { /// For each place of interest, the analysis tracks a value of the given type. @@ -334,7 +334,7 @@ pub trait ValueAnalysis<'tcx> { pub struct ValueAnalysisWrapper<T>(pub T); -impl<'tcx, T: ValueAnalysis<'tcx>> AnalysisDomain<'tcx> for ValueAnalysisWrapper<T> { +impl<'tcx, T: ValueAnalysis<'tcx>> Analysis<'tcx> for ValueAnalysisWrapper<T> { type Domain = State<T::Value>; const NAME: &'static str = T::NAME; @@ -351,12 +351,7 @@ impl<'tcx, T: ValueAnalysis<'tcx>> AnalysisDomain<'tcx> for ValueAnalysisWrapper state.flood(PlaceRef { local: arg, projection: &[] }, self.0.map()); } } -} -impl<'tcx, T> Analysis<'tcx> for ValueAnalysisWrapper<T> -where - T: ValueAnalysis<'tcx>, -{ fn apply_statement_effect( &mut self, state: &mut Self::Domain, diff --git a/compiler/rustc_mir_transform/src/elaborate_drops.rs b/compiler/rustc_mir_transform/src/elaborate_drops.rs index c35aec42408..f4ac4d9fee6 100644 --- a/compiler/rustc_mir_transform/src/elaborate_drops.rs +++ b/compiler/rustc_mir_transform/src/elaborate_drops.rs @@ -133,7 +133,7 @@ impl InitializationData<'_, '_> { } fn maybe_live_dead(&self, path: MovePathIndex) -> (bool, bool) { - (self.inits.contains(path), self.uninits.contains(path)) + (self.inits.get().contains(path), self.uninits.get().contains(path)) } } diff --git a/compiler/rustc_mir_transform/src/ref_prop.rs b/compiler/rustc_mir_transform/src/ref_prop.rs index a62a892716f..53e53d9d5ba 100644 --- a/compiler/rustc_mir_transform/src/ref_prop.rs +++ b/compiler/rustc_mir_transform/src/ref_prop.rs @@ -179,7 +179,7 @@ fn compute_replacement<'tcx>( } else { // This is a proper dereference. We can only allow it if `target` is live. maybe_dead.seek_after_primary_effect(loc); - let maybe_dead = maybe_dead.contains(target.local); + let maybe_dead = maybe_dead.get().contains(target.local); !maybe_dead } }; diff --git a/src/tools/clippy/clippy_utils/src/mir/possible_borrower.rs b/src/tools/clippy/clippy_utils/src/mir/possible_borrower.rs index 6bb434a466f..a00196c4b51 100644 --- a/src/tools/clippy/clippy_utils/src/mir/possible_borrower.rs +++ b/src/tools/clippy/clippy_utils/src/mir/possible_borrower.rs @@ -213,7 +213,7 @@ impl<'b, 'tcx> PossibleBorrowerMap<'b, 'tcx> { self.bitset.0.clear(); let maybe_live = &mut self.maybe_live; if let Some(bitset) = self.map.get(&borrowed) { - for b in bitset.iter().filter(move |b| maybe_live.contains(*b)) { + for b in bitset.iter().filter(move |b| maybe_live.get().contains(*b)) { self.bitset.0.insert(b); } } else { @@ -238,6 +238,6 @@ impl<'b, 'tcx> PossibleBorrowerMap<'b, 'tcx> { pub fn local_is_alive_at(&mut self, local: mir::Local, at: mir::Location) -> bool { self.maybe_live.seek_after_primary_effect(at); - self.maybe_live.contains(local) + self.maybe_live.get().contains(local) } } |