1 // Copyright 2017 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! A nice wrapper to consume dataflow results at several CFG
14 use rustc::mir::{BasicBlock, Location};
15 use rustc_data_structures::bit_set::{BitIter, BitSet, HybridBitSet};
17 use dataflow::{BitDenotation, BlockSets, DataflowResults};
18 use dataflow::move_paths::{HasMoveData, MovePathIndex};
22 /// A trait for "cartesian products" of multiple FlowAtLocation.
24 /// There's probably a way to auto-impl this, but I think
25 /// it is cleaner to have manual visitor impls.
26 pub trait FlowsAtLocation {
27 /// Reset the state bitvector to represent the entry to block `bb`.
28 fn reset_to_entry_of(&mut self, bb: BasicBlock);
30 /// Reset the state bitvector to represent the exit of the
31 /// terminator of block `bb`.
33 /// **Important:** In the case of a `Call` terminator, these
34 /// effects do *not* include the result of storing the destination
35 /// of the call, since that is edge-dependent (in other words, the
36 /// effects don't apply to the unwind edge).
37 fn reset_to_exit_of(&mut self, bb: BasicBlock);
39 /// Build gen + kill sets for statement at `loc`.
41 /// Note that invoking this method alone does not change the
42 /// `curr_state` -- you must invoke `apply_local_effect`
44 fn reconstruct_statement_effect(&mut self, loc: Location);
46 /// Build gen + kill sets for terminator for `loc`.
48 /// Note that invoking this method alone does not change the
49 /// `curr_state` -- you must invoke `apply_local_effect`
51 fn reconstruct_terminator_effect(&mut self, loc: Location);
53 /// Apply current gen + kill sets to `flow_state`.
55 /// (`loc` parameters can be ignored if desired by
56 /// client. For the terminator, the `stmt_idx` will be the number
57 /// of statements in the block.)
58 fn apply_local_effect(&mut self, loc: Location);
61 /// Represents the state of dataflow at a particular
62 /// CFG location, both before and after it is
65 /// Data flow results are typically computed only as basic block
66 /// boundaries. A `FlowInProgress` allows you to reconstruct the
67 /// effects at any point in the control-flow graph by starting with
68 /// the state at the start of the basic block (`reset_to_entry_of`)
69 /// and then replaying the effects of statements and terminators
70 /// (e.g. via `reconstruct_statement_effect` and
71 /// `reconstruct_terminator_effect`; don't forget to call
72 /// `apply_local_effect`).
73 pub struct FlowAtLocation<BD>
77 base_results: DataflowResults<BD>,
78 curr_state: BitSet<BD::Idx>,
79 stmt_gen: HybridBitSet<BD::Idx>,
80 stmt_kill: HybridBitSet<BD::Idx>,
83 impl<BD> FlowAtLocation<BD>
87 /// Iterate over each bit set in the current state.
88 pub fn each_state_bit<F>(&self, f: F)
92 self.curr_state.iter().for_each(f)
95 /// Iterate over each `gen` bit in the current effect (invoke
96 /// `reconstruct_statement_effect` or
97 /// `reconstruct_terminator_effect` first).
98 pub fn each_gen_bit<F>(&self, f: F)
102 self.stmt_gen.iter().for_each(f)
105 pub fn new(results: DataflowResults<BD>) -> Self {
106 let bits_per_block = results.sets().bits_per_block();
107 let curr_state = BitSet::new_empty(bits_per_block);
108 let stmt_gen = HybridBitSet::new_empty(bits_per_block);
109 let stmt_kill = HybridBitSet::new_empty(bits_per_block);
111 base_results: results,
112 curr_state: curr_state,
114 stmt_kill: stmt_kill,
118 /// Access the underlying operator.
119 pub fn operator(&self) -> &BD {
120 self.base_results.operator()
123 pub fn contains(&self, x: BD::Idx) -> bool {
124 self.curr_state.contains(x)
127 /// Returns an iterator over the elements present in the current state.
128 pub fn iter_incoming(&self) -> iter::Peekable<BitIter<BD::Idx>> {
129 self.curr_state.iter().peekable()
132 /// Creates a clone of the current state and applies the local
133 /// effects to the clone (leaving the state of self intact).
134 /// Invokes `f` with an iterator over the resulting state.
135 pub fn with_iter_outgoing<F>(&self, f: F)
137 F: FnOnce(BitIter<BD::Idx>),
139 let mut curr_state = self.curr_state.clone();
140 curr_state.union(&self.stmt_gen);
141 curr_state.subtract(&self.stmt_kill);
142 f(curr_state.iter());
146 impl<BD> FlowsAtLocation for FlowAtLocation<BD>
147 where BD: BitDenotation
149 fn reset_to_entry_of(&mut self, bb: BasicBlock) {
150 self.curr_state.overwrite(self.base_results.sets().on_entry_set_for(bb.index()));
153 fn reset_to_exit_of(&mut self, bb: BasicBlock) {
154 self.reset_to_entry_of(bb);
155 self.curr_state.union(self.base_results.sets().gen_set_for(bb.index()));
156 self.curr_state.subtract(self.base_results.sets().kill_set_for(bb.index()));
159 fn reconstruct_statement_effect(&mut self, loc: Location) {
160 self.stmt_gen.clear();
161 self.stmt_kill.clear();
163 let mut sets = BlockSets {
164 on_entry: &mut self.curr_state,
165 gen_set: &mut self.stmt_gen,
166 kill_set: &mut self.stmt_kill,
170 .before_statement_effect(&mut sets, loc);
172 self.apply_local_effect(loc);
174 let mut sets = BlockSets {
175 on_entry: &mut self.curr_state,
176 gen_set: &mut self.stmt_gen,
177 kill_set: &mut self.stmt_kill,
181 .statement_effect(&mut sets, loc);
184 fn reconstruct_terminator_effect(&mut self, loc: Location) {
185 self.stmt_gen.clear();
186 self.stmt_kill.clear();
188 let mut sets = BlockSets {
189 on_entry: &mut self.curr_state,
190 gen_set: &mut self.stmt_gen,
191 kill_set: &mut self.stmt_kill,
195 .before_terminator_effect(&mut sets, loc);
197 self.apply_local_effect(loc);
199 let mut sets = BlockSets {
200 on_entry: &mut self.curr_state,
201 gen_set: &mut self.stmt_gen,
202 kill_set: &mut self.stmt_kill,
206 .terminator_effect(&mut sets, loc);
209 fn apply_local_effect(&mut self, _loc: Location) {
210 self.curr_state.union(&self.stmt_gen);
211 self.curr_state.subtract(&self.stmt_kill);
216 impl<'tcx, T> FlowAtLocation<T>
218 T: HasMoveData<'tcx> + BitDenotation<Idx = MovePathIndex>,
220 pub fn has_any_child_of(&self, mpi: T::Idx) -> Option<T::Idx> {
221 // We process `mpi` before the loop below, for two reasons:
222 // - it's a little different from the loop case (we don't traverse its
224 // - ~99% of the time the loop isn't reached, and this code is hot, so
225 // we don't want to allocate `todo` unnecessarily.
226 if self.contains(mpi) {
229 let move_data = self.operator().move_data();
230 let move_path = &move_data.move_paths[mpi];
231 let mut todo = if let Some(child) = move_path.first_child {
237 while let Some(mpi) = todo.pop() {
238 if self.contains(mpi) {
241 let move_path = &move_data.move_paths[mpi];
242 if let Some(child) = move_path.first_child {
245 // After we've processed the original `mpi`, we should always
246 // traverse the siblings of any of its children.
247 if let Some(sibling) = move_path.next_sibling {