diff options
| -rw-r--r-- | src/librustc_mir/dataflow/framework/mod.rs | 43 | ||||
| -rw-r--r-- | src/librustc_mir/dataflow/mod.rs | 47 |
2 files changed, 43 insertions, 47 deletions
diff --git a/src/librustc_mir/dataflow/framework/mod.rs b/src/librustc_mir/dataflow/framework/mod.rs index fb4b7b9c5be..345fb665b32 100644 --- a/src/librustc_mir/dataflow/framework/mod.rs +++ b/src/librustc_mir/dataflow/framework/mod.rs @@ -41,8 +41,6 @@ use rustc_hir::def_id::DefId; use rustc_index::bit_set::{BitSet, HybridBitSet}; use rustc_index::vec::{Idx, IndexVec}; -use crate::dataflow::BottomValue; - mod cursor; mod engine; mod graphviz; @@ -95,6 +93,47 @@ where } } +/// Parameterization for the precise form of data flow that is used. +/// +/// `BottomValue` determines whether the initial entry set for each basic block is empty or full. +/// This also determines the semantics of the lattice `join` operator used to merge dataflow +/// results, since dataflow works by starting at the bottom and moving monotonically to a fixed +/// point. +/// +/// This means, for propagation across the graph, that you either want to start at all-zeroes and +/// then use Union as your merge when propagating, or you start at all-ones and then use Intersect +/// as your merge when propagating. +pub trait BottomValue { + /// Specifies the initial value for each bit in the entry set for each basic block. + const BOTTOM_VALUE: bool; + + /// Merges `in_set` into `inout_set`, returning `true` if `inout_set` changed. + /// + /// It is almost certainly wrong to override this, since it automatically applies + /// * `inout_set & in_set` if `BOTTOM_VALUE == true` + /// * `inout_set | in_set` if `BOTTOM_VALUE == false` + /// + /// This means that if a bit is not `BOTTOM_VALUE`, it is propagated into all target blocks. + /// For clarity, the above statement again from a different perspective: + /// A bit in the block's entry set is `!BOTTOM_VALUE` if *any* predecessor block's bit value is + /// `!BOTTOM_VALUE`. + /// + /// There are situations where you want the opposite behaviour: propagate only if *all* + /// predecessor blocks's value is `!BOTTOM_VALUE`. + /// E.g. if you want to know whether a bit is *definitely* set at a specific location. This + /// means that all code paths leading to the location must have set the bit, instead of any + /// code path leading there. + /// + /// If you want this kind of "definitely set" analysis, you need to + /// 1. Invert `BOTTOM_VALUE` + /// 2. Reset the `entry_set` in `start_block_effect` to `!BOTTOM_VALUE` + /// 3. Override `join` to do the opposite from what it's doing now. + #[inline] + fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool { + if !Self::BOTTOM_VALUE { inout_set.union(in_set) } else { inout_set.intersect(in_set) } + } +} + /// Define the domain of a dataflow problem. /// /// This trait specifies the lattice on which this analysis operates. For now, this must be a diff --git a/src/librustc_mir/dataflow/mod.rs b/src/librustc_mir/dataflow/mod.rs index 737183f8dc3..d13dfb26980 100644 --- a/src/librustc_mir/dataflow/mod.rs +++ b/src/librustc_mir/dataflow/mod.rs @@ -1,13 +1,11 @@ use rustc::ty; use rustc_ast::ast::{self, MetaItem}; -use rustc_index::bit_set::BitSet; -use rustc_index::vec::Idx; use rustc_span::symbol::{sym, Symbol}; pub(crate) use self::drop_flag_effects::*; pub use self::framework::{ - visit_results, Analysis, AnalysisDomain, BorrowckFlowState, BorrowckResults, Engine, GenKill, - GenKillAnalysis, Results, ResultsCursor, ResultsRefCursor, ResultsVisitor, + visit_results, Analysis, AnalysisDomain, BorrowckFlowState, BorrowckResults, BottomValue, + Engine, GenKill, GenKillAnalysis, Results, ResultsCursor, ResultsRefCursor, ResultsVisitor, }; pub use self::impls::{ borrows::Borrows, DefinitelyInitializedPlaces, EverInitializedPlaces, MaybeBorrowedLocals, @@ -48,44 +46,3 @@ pub(crate) fn has_rustc_mir_with(attrs: &[ast::Attribute], name: Symbol) -> Opti } None } - -/// Parameterization for the precise form of data flow that is used. -/// -/// `BottomValue` determines whether the initial entry set for each basic block is empty or full. -/// This also determines the semantics of the lattice `join` operator used to merge dataflow -/// results, since dataflow works by starting at the bottom and moving monotonically to a fixed -/// point. -/// -/// This means, for propagation across the graph, that you either want to start at all-zeroes and -/// then use Union as your merge when propagating, or you start at all-ones and then use Intersect -/// as your merge when propagating. -pub trait BottomValue { - /// Specifies the initial value for each bit in the entry set for each basic block. - const BOTTOM_VALUE: bool; - - /// Merges `in_set` into `inout_set`, returning `true` if `inout_set` changed. - /// - /// It is almost certainly wrong to override this, since it automatically applies - /// * `inout_set & in_set` if `BOTTOM_VALUE == true` - /// * `inout_set | in_set` if `BOTTOM_VALUE == false` - /// - /// This means that if a bit is not `BOTTOM_VALUE`, it is propagated into all target blocks. - /// For clarity, the above statement again from a different perspective: - /// A bit in the block's entry set is `!BOTTOM_VALUE` if *any* predecessor block's bit value is - /// `!BOTTOM_VALUE`. - /// - /// There are situations where you want the opposite behaviour: propagate only if *all* - /// predecessor blocks's value is `!BOTTOM_VALUE`. - /// E.g. if you want to know whether a bit is *definitely* set at a specific location. This - /// means that all code paths leading to the location must have set the bit, instead of any - /// code path leading there. - /// - /// If you want this kind of "definitely set" analysis, you need to - /// 1. Invert `BOTTOM_VALUE` - /// 2. Reset the `entry_set` in `start_block_effect` to `!BOTTOM_VALUE` - /// 3. Override `join` to do the opposite from what it's doing now. - #[inline] - fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool { - if !Self::BOTTOM_VALUE { inout_set.union(in_set) } else { inout_set.intersect(in_set) } - } -} |