summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDylan MacKenzie <ecstaticmorse@gmail.com>2020-03-02 09:32:12 -0800
committerDylan MacKenzie <ecstaticmorse@gmail.com>2020-03-26 16:20:00 -0700
commit7108cea14ee1517898cbfcb71f59706f30a4cf18 (patch)
tree495c0e028f3239a879fa8a28d4ff4b584876b79e
parentUpdate imports from `dataflow::generic` to `dataflow` (diff)
downloadrust-7108cea14ee1517898cbfcb71f59706f30a4cf18.tar.gz
rust-7108cea14ee1517898cbfcb71f59706f30a4cf18.tar.bz2
rust-7108cea14ee1517898cbfcb71f59706f30a4cf18.tar.xz
Move `BottomValue` into `framework/mod.rs`
-rw-r--r--src/librustc_mir/dataflow/framework/mod.rs43
-rw-r--r--src/librustc_mir/dataflow/mod.rs47
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 fb4b7b9..345fb66 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;
41use rustc_index::bit_set::{BitSet, HybridBitSet}; 41use rustc_index::bit_set::{BitSet, HybridBitSet};
42use rustc_index::vec::{Idx, IndexVec}; 42use rustc_index::vec::{Idx, IndexVec};
43 43
44use crate::dataflow::BottomValue;
45
46mod cursor; 44mod cursor;
47mod engine; 45mod engine;
48mod graphviz; 46mod graphviz;
@@ -95,6 +93,47 @@ where
95 } 93 }
96} 94}
97 95
96/// Parameterization for the precise form of data flow that is used.
97///
98/// `BottomValue` determines whether the initial entry set for each basic block is empty or full.
99/// This also determines the semantics of the lattice `join` operator used to merge dataflow
100/// results, since dataflow works by starting at the bottom and moving monotonically to a fixed
101/// point.
102///
103/// This means, for propagation across the graph, that you either want to start at all-zeroes and
104/// then use Union as your merge when propagating, or you start at all-ones and then use Intersect
105/// as your merge when propagating.
106pub trait BottomValue {
107 /// Specifies the initial value for each bit in the entry set for each basic block.
108 const BOTTOM_VALUE: bool;
109
110 /// Merges `in_set` into `inout_set`, returning `true` if `inout_set` changed.
111 ///
112 /// It is almost certainly wrong to override this, since it automatically applies
113 /// * `inout_set & in_set` if `BOTTOM_VALUE == true`
114 /// * `inout_set | in_set` if `BOTTOM_VALUE == false`
115 ///
116 /// This means that if a bit is not `BOTTOM_VALUE`, it is propagated into all target blocks.
117 /// For clarity, the above statement again from a different perspective:
118 /// A bit in the block's entry set is `!BOTTOM_VALUE` if *any* predecessor block's bit value is
119 /// `!BOTTOM_VALUE`.
120 ///
121 /// There are situations where you want the opposite behaviour: propagate only if *all*
122 /// predecessor blocks's value is `!BOTTOM_VALUE`.
123 /// E.g. if you want to know whether a bit is *definitely* set at a specific location. This
124 /// means that all code paths leading to the location must have set the bit, instead of any
125 /// code path leading there.
126 ///
127 /// If you want this kind of "definitely set" analysis, you need to
128 /// 1. Invert `BOTTOM_VALUE`
129 /// 2. Reset the `entry_set` in `start_block_effect` to `!BOTTOM_VALUE`
130 /// 3. Override `join` to do the opposite from what it's doing now.
131 #[inline]
132 fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool {
133 if !Self::BOTTOM_VALUE { inout_set.union(in_set) } else { inout_set.intersect(in_set) }
134 }
135}
136
98/// Define the domain of a dataflow problem. 137/// Define the domain of a dataflow problem.
99/// 138///
100/// This trait specifies the lattice on which this analysis operates. For now, this must be a 139/// 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 737183f..d13dfb2 100644
--- a/src/librustc_mir/dataflow/mod.rs
+++ b/src/librustc_mir/dataflow/mod.rs
@@ -1,13 +1,11 @@
1use rustc::ty; 1use rustc::ty;
2use rustc_ast::ast::{self, MetaItem}; 2use rustc_ast::ast::{self, MetaItem};
3use rustc_index::bit_set::BitSet;
4use rustc_index::vec::Idx;
5use rustc_span::symbol::{sym, Symbol}; 3use rustc_span::symbol::{sym, Symbol};
6 4
7pub(crate) use self::drop_flag_effects::*; 5pub(crate) use self::drop_flag_effects::*;
8pub use self::framework::{ 6pub use self::framework::{
9 visit_results, Analysis, AnalysisDomain, BorrowckFlowState, BorrowckResults, Engine, GenKill, 7 visit_results, Analysis, AnalysisDomain, BorrowckFlowState, BorrowckResults, BottomValue,
10 GenKillAnalysis, Results, ResultsCursor, ResultsRefCursor, ResultsVisitor, 8 Engine, GenKill, GenKillAnalysis, Results, ResultsCursor, ResultsRefCursor, ResultsVisitor,
11}; 9};
12pub use self::impls::{ 10pub use self::impls::{
13 borrows::Borrows, DefinitelyInitializedPlaces, EverInitializedPlaces, MaybeBorrowedLocals, 11 borrows::Borrows, DefinitelyInitializedPlaces, EverInitializedPlaces, MaybeBorrowedLocals,
@@ -48,44 +46,3 @@ pub(crate) fn has_rustc_mir_with(attrs: &[ast::Attribute], name: Symbol) -> Opti
48 } 46 }
49 None 47 None
50} 48}
51
52/// Parameterization for the precise form of data flow that is used.
53///
54/// `BottomValue` determines whether the initial entry set for each basic block is empty or full.
55/// This also determines the semantics of the lattice `join` operator used to merge dataflow
56/// results, since dataflow works by starting at the bottom and moving monotonically to a fixed
57/// point.
58///
59/// This means, for propagation across the graph, that you either want to start at all-zeroes and
60/// then use Union as your merge when propagating, or you start at all-ones and then use Intersect
61/// as your merge when propagating.
62pub trait BottomValue {
63 /// Specifies the initial value for each bit in the entry set for each basic block.
64 const BOTTOM_VALUE: bool;
65
66 /// Merges `in_set` into `inout_set`, returning `true` if `inout_set` changed.
67 ///
68 /// It is almost certainly wrong to override this, since it automatically applies
69 /// * `inout_set & in_set` if `BOTTOM_VALUE == true`
70 /// * `inout_set | in_set` if `BOTTOM_VALUE == false`
71 ///
72 /// This means that if a bit is not `BOTTOM_VALUE`, it is propagated into all target blocks.
73 /// For clarity, the above statement again from a different perspective:
74 /// A bit in the block's entry set is `!BOTTOM_VALUE` if *any* predecessor block's bit value is
75 /// `!BOTTOM_VALUE`.
76 ///
77 /// There are situations where you want the opposite behaviour: propagate only if *all*
78 /// predecessor blocks's value is `!BOTTOM_VALUE`.
79 /// E.g. if you want to know whether a bit is *definitely* set at a specific location. This
80 /// means that all code paths leading to the location must have set the bit, instead of any
81 /// code path leading there.
82 ///
83 /// If you want this kind of "definitely set" analysis, you need to
84 /// 1. Invert `BOTTOM_VALUE`
85 /// 2. Reset the `entry_set` in `start_block_effect` to `!BOTTOM_VALUE`
86 /// 3. Override `join` to do the opposite from what it's doing now.
87 #[inline]
88 fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool {
89 if !Self::BOTTOM_VALUE { inout_set.union(in_set) } else { inout_set.intersect(in_set) }
90 }
91}