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};
8 use crate::dataflow::move_paths::{HasMoveData, MovePathIndex};
11 use std::borrow::Borrow;
13 /// A trait for "cartesian products" of multiple FlowAtLocation.
15 /// There's probably a way to auto-impl this, but I think
16 /// it is cleaner to have manual visitor impls.
17 pub trait FlowsAtLocation {
18 /// Reset the state bitvector to represent the entry to block `bb`.
19 fn reset_to_entry_of(&mut self, bb: BasicBlock);
21 /// Reset the state bitvector to represent the exit of the
22 /// terminator of block `bb`.
24 /// **Important:** In the case of a `Call` terminator, these
25 /// effects do *not* include the result of storing the destination
26 /// of the call, since that is edge-dependent (in other words, the
27 /// effects don't apply to the unwind edge).
28 fn reset_to_exit_of(&mut self, bb: BasicBlock);
30 /// Builds gen and kill sets for statement at `loc`.
32 /// Note that invoking this method alone does not change the
33 /// `curr_state` -- you must invoke `apply_local_effect`
35 fn reconstruct_statement_effect(&mut self, loc: Location);
37 /// Builds gen and kill sets for terminator for `loc`.
39 /// Note that invoking this method alone does not change the
40 /// `curr_state` -- you must invoke `apply_local_effect`
42 fn reconstruct_terminator_effect(&mut self, loc: Location);
44 /// Apply current gen + kill sets to `flow_state`.
46 /// (`loc` parameters can be ignored if desired by
47 /// client. For the terminator, the `stmt_idx` will be the number
48 /// of statements in the block.)
49 fn apply_local_effect(&mut self, loc: Location);
52 /// Represents the state of dataflow at a particular
53 /// CFG location, both before and after it is
56 /// Data flow results are typically computed only as basic block
57 /// boundaries. A `FlowInProgress` allows you to reconstruct the
58 /// effects at any point in the control-flow graph by starting with
59 /// the state at the start of the basic block (`reset_to_entry_of`)
60 /// and then replaying the effects of statements and terminators
61 /// (e.g., via `reconstruct_statement_effect` and
62 /// `reconstruct_terminator_effect`; don't forget to call
63 /// `apply_local_effect`).
64 pub struct FlowAtLocation<'tcx, BD, DR = DataflowResults<'tcx, BD>>
66 BD: BitDenotation<'tcx>,
67 DR: Borrow<DataflowResults<'tcx, BD>>,
70 curr_state: BitSet<BD::Idx>,
71 stmt_trans: GenKillSet<BD::Idx>,
74 impl<'tcx, BD, DR> FlowAtLocation<'tcx, BD, DR>
76 BD: BitDenotation<'tcx>,
77 DR: Borrow<DataflowResults<'tcx, BD>>,
79 /// Iterate over each bit set in the current state.
80 pub fn each_state_bit<F>(&self, f: F)
84 self.curr_state.iter().for_each(f)
87 /// Iterate over each `gen` bit in the current effect (invoke
88 /// `reconstruct_statement_effect` or
89 /// `reconstruct_terminator_effect` first).
90 pub fn each_gen_bit<F>(&self, f: F)
94 self.stmt_trans.gen_set.iter().for_each(f)
97 pub fn new(results: DR) -> Self {
98 let bits_per_block = results.borrow().sets().bits_per_block();
99 let curr_state = BitSet::new_empty(bits_per_block);
100 let stmt_trans = GenKillSet::from_elem(HybridBitSet::new_empty(bits_per_block));
102 base_results: results,
108 /// Access the underlying operator.
109 pub fn operator(&self) -> &BD {
110 self.base_results.borrow().operator()
113 pub fn contains(&self, x: BD::Idx) -> bool {
114 self.curr_state.contains(x)
117 /// Returns an iterator over the elements present in the current state.
118 pub fn iter_incoming(&self) -> iter::Peekable<BitIter<'_, BD::Idx>> {
119 self.curr_state.iter().peekable()
122 /// Creates a clone of the current state and applies the local
123 /// effects to the clone (leaving the state of self intact).
124 /// Invokes `f` with an iterator over the resulting state.
125 pub fn with_iter_outgoing<F>(&self, f: F)
127 F: FnOnce(BitIter<'_, BD::Idx>),
129 let mut curr_state = self.curr_state.clone();
130 self.stmt_trans.apply(&mut curr_state);
131 f(curr_state.iter());
134 /// Returns a bitset of the elements present in the current state.
135 pub fn as_dense(&self) -> &BitSet<BD::Idx> {
140 impl<'tcx, BD, DR> FlowsAtLocation for FlowAtLocation<'tcx, BD, DR>
142 BD: BitDenotation<'tcx>,
143 DR: Borrow<DataflowResults<'tcx, BD>>,
145 fn reset_to_entry_of(&mut self, bb: BasicBlock) {
146 self.curr_state.overwrite(self.base_results.borrow().sets().entry_set_for(bb.index()));
149 fn reset_to_exit_of(&mut self, bb: BasicBlock) {
150 self.reset_to_entry_of(bb);
151 let trans = self.base_results.borrow().sets().trans_for(bb.index());
152 trans.apply(&mut self.curr_state)
155 fn reconstruct_statement_effect(&mut self, loc: Location) {
156 self.stmt_trans.clear();
160 .before_statement_effect(&mut self.stmt_trans, loc);
161 self.stmt_trans.apply(&mut self.curr_state);
166 .statement_effect(&mut self.stmt_trans, loc);
169 fn reconstruct_terminator_effect(&mut self, loc: Location) {
170 self.stmt_trans.clear();
174 .before_terminator_effect(&mut self.stmt_trans, loc);
175 self.stmt_trans.apply(&mut self.curr_state);
180 .terminator_effect(&mut self.stmt_trans, loc);
183 fn apply_local_effect(&mut self, _loc: Location) {
184 self.stmt_trans.apply(&mut self.curr_state)
189 impl<'tcx, T, DR> FlowAtLocation<'tcx, T, DR>
191 T: HasMoveData<'tcx> + BitDenotation<'tcx, Idx = MovePathIndex>,
192 DR: Borrow<DataflowResults<'tcx, T>>,
194 pub fn has_any_child_of(&self, mpi: T::Idx) -> Option<T::Idx> {
195 // We process `mpi` before the loop below, for two reasons:
196 // - it's a little different from the loop case (we don't traverse its
198 // - ~99% of the time the loop isn't reached, and this code is hot, so
199 // we don't want to allocate `todo` unnecessarily.
200 if self.contains(mpi) {
203 let move_data = self.operator().move_data();
204 let move_path = &move_data.move_paths[mpi];
205 let mut todo = if let Some(child) = move_path.first_child {
211 while let Some(mpi) = todo.pop() {
212 if self.contains(mpi) {
215 let move_path = &move_data.move_paths[mpi];
216 if let Some(child) = move_path.first_child {
219 // After we've processed the original `mpi`, we should always
220 // traverse the siblings of any of its children.
221 if let Some(sibling) = move_path.next_sibling {