1 //! A nice wrapper to consume dataflow results at several CFG
4 use rustc::mir::{BasicBlock, Location};
5 use rustc_index::bit_set::{BitIter, BitSet, HybridBitSet};
7 use crate::dataflow::{BitDenotation, DataflowResults, GenKillSet};
9 use std::borrow::Borrow;
12 /// A trait for "cartesian products" of multiple FlowAtLocation.
14 /// There's probably a way to auto-impl this, but I think
15 /// it is cleaner to have manual visitor impls.
16 pub trait FlowsAtLocation {
17 /// Reset the state bitvector to represent the entry to block `bb`.
18 fn reset_to_entry_of(&mut self, bb: BasicBlock);
20 /// Reset the state bitvector to represent the exit of the
21 /// terminator of block `bb`.
23 /// **Important:** In the case of a `Call` terminator, these
24 /// effects do *not* include the result of storing the destination
25 /// of the call, since that is edge-dependent (in other words, the
26 /// effects don't apply to the unwind edge).
27 fn reset_to_exit_of(&mut self, bb: BasicBlock);
29 /// Builds gen and kill sets for statement at `loc`.
31 /// Note that invoking this method alone does not change the
32 /// `curr_state` -- you must invoke `apply_local_effect`
34 fn reconstruct_statement_effect(&mut self, loc: Location);
36 /// Builds gen and kill sets for terminator for `loc`.
38 /// Note that invoking this method alone does not change the
39 /// `curr_state` -- you must invoke `apply_local_effect`
41 fn reconstruct_terminator_effect(&mut self, loc: Location);
43 /// Apply current gen + kill sets to `flow_state`.
45 /// (`loc` parameters can be ignored if desired by
46 /// client. For the terminator, the `stmt_idx` will be the number
47 /// of statements in the block.)
48 fn apply_local_effect(&mut self, loc: Location);
51 /// Represents the state of dataflow at a particular
52 /// CFG location, both before and after it is
55 /// Data flow results are typically computed only as basic block
56 /// boundaries. A `FlowInProgress` allows you to reconstruct the
57 /// effects at any point in the control-flow graph by starting with
58 /// the state at the start of the basic block (`reset_to_entry_of`)
59 /// and then replaying the effects of statements and terminators
60 /// (e.g., via `reconstruct_statement_effect` and
61 /// `reconstruct_terminator_effect`; don't forget to call
62 /// `apply_local_effect`).
63 pub struct FlowAtLocation<'tcx, BD, DR = DataflowResults<'tcx, BD>>
65 BD: BitDenotation<'tcx>,
66 DR: Borrow<DataflowResults<'tcx, BD>>,
69 curr_state: BitSet<BD::Idx>,
70 stmt_trans: GenKillSet<BD::Idx>,
73 impl<'tcx, BD, DR> FlowAtLocation<'tcx, BD, DR>
75 BD: BitDenotation<'tcx>,
76 DR: Borrow<DataflowResults<'tcx, BD>>,
78 /// Iterate over each bit set in the current state.
79 pub fn each_state_bit<F>(&self, f: F)
83 self.curr_state.iter().for_each(f)
86 /// Iterate over each `gen` bit in the current effect (invoke
87 /// `reconstruct_statement_effect` or
88 /// `reconstruct_terminator_effect` first).
89 pub fn each_gen_bit<F>(&self, f: F)
93 self.stmt_trans.gen_set.iter().for_each(f)
96 pub fn new(results: DR) -> Self {
97 let bits_per_block = results.borrow().sets().bits_per_block();
98 let curr_state = BitSet::new_empty(bits_per_block);
99 let stmt_trans = GenKillSet::from_elem(HybridBitSet::new_empty(bits_per_block));
100 FlowAtLocation { base_results: results, curr_state, stmt_trans }
103 /// Access the underlying operator.
104 pub fn operator(&self) -> &BD {
105 self.base_results.borrow().operator()
108 pub fn contains(&self, x: BD::Idx) -> bool {
109 self.curr_state.contains(x)
112 /// Returns an iterator over the elements present in the current state.
113 pub fn iter_incoming(&self) -> iter::Peekable<BitIter<'_, BD::Idx>> {
114 self.curr_state.iter().peekable()
117 /// Creates a clone of the current state and applies the local
118 /// effects to the clone (leaving the state of self intact).
119 /// Invokes `f` with an iterator over the resulting state.
120 pub fn with_iter_outgoing<F>(&self, f: F)
122 F: FnOnce(BitIter<'_, BD::Idx>),
124 let mut curr_state = self.curr_state.clone();
125 self.stmt_trans.apply(&mut curr_state);
126 f(curr_state.iter());
129 /// Returns a bitset of the elements present in the current state.
130 pub fn as_dense(&self) -> &BitSet<BD::Idx> {
135 impl<'tcx, BD, DR> FlowsAtLocation for FlowAtLocation<'tcx, BD, DR>
137 BD: BitDenotation<'tcx>,
138 DR: Borrow<DataflowResults<'tcx, BD>>,
140 fn reset_to_entry_of(&mut self, bb: BasicBlock) {
141 self.curr_state.overwrite(self.base_results.borrow().sets().entry_set_for(bb.index()));
144 fn reset_to_exit_of(&mut self, bb: BasicBlock) {
145 self.reset_to_entry_of(bb);
146 let trans = self.base_results.borrow().sets().trans_for(bb.index());
147 trans.apply(&mut self.curr_state)
150 fn reconstruct_statement_effect(&mut self, loc: Location) {
151 self.stmt_trans.clear();
152 self.base_results.borrow().operator().before_statement_effect(&mut self.stmt_trans, loc);
153 self.stmt_trans.apply(&mut self.curr_state);
155 self.base_results.borrow().operator().statement_effect(&mut self.stmt_trans, loc);
158 fn reconstruct_terminator_effect(&mut self, loc: Location) {
159 self.stmt_trans.clear();
160 self.base_results.borrow().operator().before_terminator_effect(&mut self.stmt_trans, loc);
161 self.stmt_trans.apply(&mut self.curr_state);
163 self.base_results.borrow().operator().terminator_effect(&mut self.stmt_trans, loc);
166 fn apply_local_effect(&mut self, _loc: Location) {
167 self.stmt_trans.apply(&mut self.curr_state)