diff options
| author | Nicholas Nethercote <n.nethercote@gmail.com> | 2024-10-10 11:46:29 +1100 |
|---|---|---|
| committer | Nicholas Nethercote <n.nethercote@gmail.com> | 2024-10-14 16:35:47 +1100 |
| commit | ba13775319fa51933da6e90053a9f96778b15b6b (patch) | |
| tree | b6dcbf79477e882167fedb687a9fe4144df62b0d /compiler/rustc_mir_dataflow/src/framework | |
| parent | 4dc1b4d0b1c0e96102f6d9b3a0ea91e46feaf8e9 (diff) | |
Merge `AnalysisDomain` into `Analysis`.
With `GenKillAnalysis` gone, there is no need for them to be separate.
Diffstat (limited to 'compiler/rustc_mir_dataflow/src/framework')
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/engine.rs | 5 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/mod.rs | 41 | ||||
| -rw-r--r-- | compiler/rustc_mir_dataflow/src/framework/tests.rs | 4 |
3 files changed, 22 insertions, 28 deletions
diff --git a/compiler/rustc_mir_dataflow/src/framework/engine.rs b/compiler/rustc_mir_dataflow/src/framework/engine.rs index d6853b6ef82..cbd1083d037 100644 --- a/compiler/rustc_mir_dataflow/src/framework/engine.rs +++ b/compiler/rustc_mir_dataflow/src/framework/engine.rs @@ -16,14 +16,13 @@ use {rustc_ast as ast, rustc_graphviz as dot}; use super::fmt::DebugWithContext; use super::{ - Analysis, AnalysisDomain, Direction, JoinSemiLattice, ResultsCursor, ResultsVisitor, graphviz, - visit_results, + Analysis, Direction, JoinSemiLattice, ResultsCursor, ResultsVisitor, graphviz, visit_results, }; use crate::errors::{ DuplicateValuesFor, PathMustEndInFilename, RequiresAnArgument, UnknownFormatter, }; -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)] diff --git a/compiler/rustc_mir_dataflow/src/framework/mod.rs b/compiler/rustc_mir_dataflow/src/framework/mod.rs index d7a62ecd2c1..4e72ffabc6e 100644 --- a/compiler/rustc_mir_dataflow/src/framework/mod.rs +++ b/compiler/rustc_mir_dataflow/src/framework/mod.rs @@ -89,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. /// -/// 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> { +/// # 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 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; @@ -118,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 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, diff --git a/compiler/rustc_mir_dataflow/src/framework/tests.rs b/compiler/rustc_mir_dataflow/src/framework/tests.rs index 1861f4cffc7..de171dbc313 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, |
