Extend dataflow framework to support arbitrary lattices

1 files changed, 38 insertions, 75 deletions

diff --git a/compiler/rustc_mir/src/dataflow/framework/mod.rs b/compiler/rustc_mir/src/dataflow/framework/mod.rs
index a21bbacb467..eba3b88d47e 100644
--- a/compiler/rustc_mir/src/dataflow/framework/mod.rs
+++ b/compiler/rustc_mir/src/dataflow/framework/mod.rs
@@ -30,8 +30,8 @@
 //!
 //! [gen-kill]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems
 
+use std::borrow::BorrowMut;
 use std::cmp::Ordering;
-use std::io;
 
 use rustc_hir::def_id::DefId;
 use rustc_index::bit_set::{BitSet, HybridBitSet};
@@ -43,67 +43,24 @@ use rustc_target::abi::VariantIdx;
 mod cursor;
 mod direction;
 mod engine;
+pub mod fmt;
 mod graphviz;
+pub mod lattice;
 mod visitor;
 
 pub use self::cursor::{ResultsCursor, ResultsRefCursor};
 pub use self::direction::{Backward, Direction, Forward};
 pub use self::engine::{Engine, Results};
+pub use self::lattice::{JoinSemiLattice, MeetSemiLattice};
 pub use self::visitor::{visit_results, ResultsVisitor};
 pub use self::visitor::{BorrowckFlowState, BorrowckResults};
 
-/// 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
-/// powerset of values of type `Idx`. The elements of this lattice are represented with a `BitSet`
-/// and referred to as the state vector.
-///
-/// This trait also defines the initial value for the dataflow state upon entry to the
-/// `START_BLOCK`, as well as some names used to refer to this analysis when debugging.
-pub trait AnalysisDomain<'tcx>: BottomValue {
-    /// The type of the elements in the state vector.
-    type Idx: Idx;
+/// 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> {
+    type Domain: Clone + JoinSemiLattice;
 
     /// The direction of this analyis. Either `Forward` or `Backward`.
     type Direction: Direction = Forward;
@@ -114,8 +71,7 @@ pub trait AnalysisDomain<'tcx>: BottomValue {
     /// suitable as part of a filename.
     const NAME: &'static str;
 
-    /// The size of the state vector.
-    fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize;
+    fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain;
 
     /// Mutates the entry set of the `START_BLOCK` to contain the initial state for dataflow
     /// analysis.
@@ -126,12 +82,7 @@ pub trait AnalysisDomain<'tcx>: BottomValue {
     // FIXME: For backward dataflow analyses, the initial state should be applied to every basic
     // 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 generators, however.
-    fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>);
-
-    /// Prints an element in the state vector for debugging.
-    fn pretty_print_idx(&self, w: &mut impl io::Write, idx: Self::Idx) -> io::Result<()> {
-        write!(w, "{:?}", idx)
-    }
+    fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut Self::Domain);
 }
 
 /// A dataflow problem with an arbitrarily complex transfer function.
@@ -139,7 +90,7 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
     /// Updates the current dataflow state with the effect of evaluating a statement.
     fn apply_statement_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut Self::Domain,
         statement: &mir::Statement<'tcx>,
         location: Location,
     );
@@ -152,7 +103,7 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
     /// analyses should not implement this without implementing `apply_statement_effect`.
     fn apply_before_statement_effect(
         &self,
-        _state: &mut BitSet<Self::Idx>,
+        _state: &mut Self::Domain,
         _statement: &mir::Statement<'tcx>,
         _location: Location,
     ) {
@@ -166,7 +117,7 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
     /// initialized here.
     fn apply_terminator_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut Self::Domain,
         terminator: &mir::Terminator<'tcx>,
         location: Location,
     );
@@ -179,7 +130,7 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
     /// analyses should not implement this without implementing `apply_terminator_effect`.
     fn apply_before_terminator_effect(
         &self,
-        _state: &mut BitSet<Self::Idx>,
+        _state: &mut Self::Domain,
         _terminator: &mir::Terminator<'tcx>,
         _location: Location,
     ) {
@@ -192,7 +143,7 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
     /// edges.
     fn apply_call_return_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut Self::Domain,
         block: BasicBlock,
         func: &mir::Operand<'tcx>,
         args: &[mir::Operand<'tcx>],
@@ -207,7 +158,7 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
     /// By default, no effects happen.
     fn apply_yield_resume_effect(
         &self,
-        _state: &mut BitSet<Self::Idx>,
+        _state: &mut Self::Domain,
         _resume_block: BasicBlock,
         _resume_place: mir::Place<'tcx>,
     ) {
@@ -222,7 +173,7 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
     /// FIXME: This class of effects is not supported for backward dataflow analyses.
     fn apply_discriminant_switch_effect(
         &self,
-        _state: &mut BitSet<Self::Idx>,
+        _state: &mut Self::Domain,
         _block: BasicBlock,
         _enum_place: mir::Place<'tcx>,
         _adt: &ty::AdtDef,
@@ -264,6 +215,8 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
 ///
 /// `Analysis` is automatically implemented for all implementers of `GenKillAnalysis`.
 pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> {
+    type Idx: Idx;
+
     /// See `Analysis::apply_statement_effect`.
     fn statement_effect(
         &self,
@@ -332,10 +285,11 @@ pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> {
 impl<A> Analysis<'tcx> for A
 where
     A: GenKillAnalysis<'tcx>,
+    A::Domain: GenKill<A::Idx> + BorrowMut<BitSet<A::Idx>>,
 {
     fn apply_statement_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut A::Domain,
         statement: &mir::Statement<'tcx>,
         location: Location,
     ) {
@@ -344,7 +298,7 @@ where
 
     fn apply_before_statement_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut A::Domain,
         statement: &mir::Statement<'tcx>,
         location: Location,
     ) {
@@ -353,7 +307,7 @@ where
 
     fn apply_terminator_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut A::Domain,
         terminator: &mir::Terminator<'tcx>,
         location: Location,
     ) {
@@ -362,7 +316,7 @@ where
 
     fn apply_before_terminator_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut A::Domain,
         terminator: &mir::Terminator<'tcx>,
         location: Location,
     ) {
@@ -371,7 +325,7 @@ where
 
     fn apply_call_return_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut A::Domain,
         block: BasicBlock,
         func: &mir::Operand<'tcx>,
         args: &[mir::Operand<'tcx>],
@@ -382,7 +336,7 @@ where
 
     fn apply_yield_resume_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut A::Domain,
         resume_block: BasicBlock,
         resume_place: mir::Place<'tcx>,
     ) {
@@ -391,7 +345,7 @@ where
 
     fn apply_discriminant_switch_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
+        state: &mut A::Domain,
         block: BasicBlock,
         enum_place: mir::Place<'tcx>,
         adt: &ty::AdtDef,
@@ -450,7 +404,7 @@ pub trait GenKill<T> {
 /// 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: Idx> {
+pub struct GenKillSet<T> {
     gen: HybridBitSet<T>,
     kill: HybridBitSet<T>,
 }
@@ -464,7 +418,6 @@ impl<T: Idx> GenKillSet<T> {
         }
     }
 
-    /// Applies this transfer function to the given state vector.
     pub fn apply(&self, state: &mut BitSet<T>) {
         state.union(&self.gen);
         state.subtract(&self.kill);
@@ -493,6 +446,16 @@ impl<T: Idx> GenKill<T> for BitSet<T> {
     }
 }
 
+impl<T: Idx> GenKill<T> for lattice::Dual<BitSet<T>> {
+    fn gen(&mut self, elem: T) {
+        self.0.insert(elem);
+    }
+
+    fn kill(&mut self, elem: T) {
+        self.0.remove(elem);
+    }
+}
+
 // NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order.
 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
 pub enum Effect {