1 // Copyright 2012-2016 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 use syntax::ast::{self, MetaItem};
13 use rustc_data_structures::bitslice::{bitwise, BitwiseOperator};
14 use rustc_data_structures::indexed_set::{HybridIdxSet, IdxSet};
15 use rustc_data_structures::indexed_vec::Idx;
16 use rustc_data_structures::work_queue::WorkQueue;
18 use rustc::ty::{self, TyCtxt};
19 use rustc::mir::{self, Mir, BasicBlock, BasicBlockData, Location, Statement, Terminator};
20 use rustc::mir::traversal;
21 use rustc::session::Session;
23 use std::borrow::Borrow;
26 use std::path::PathBuf;
29 pub use self::impls::{MaybeStorageLive};
30 pub use self::impls::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
31 pub use self::impls::DefinitelyInitializedPlaces;
32 pub use self::impls::EverInitializedPlaces;
33 pub use self::impls::borrows::Borrows;
34 pub use self::impls::HaveBeenBorrowedLocals;
35 pub use self::at_location::{FlowAtLocation, FlowsAtLocation};
36 pub(crate) use self::drop_flag_effects::*;
38 use self::move_paths::MoveData;
41 pub mod drop_flag_effects;
46 pub(crate) use self::move_paths::indexes;
48 pub(crate) struct DataflowBuilder<'a, 'tcx: 'a, BD> where BD: BitDenotation
51 flow_state: DataflowAnalysis<'a, 'tcx, BD>,
52 print_preflow_to: Option<String>,
53 print_postflow_to: Option<String>,
56 /// `DebugFormatted` encapsulates the "{:?}" rendering of some
57 /// arbitrary value. This way: you pay cost of allocating an extra
58 /// string (as well as that of rendering up-front); in exchange, you
59 /// don't have to hand over ownership of your value or deal with
61 pub(crate) struct DebugFormatted(String);
64 pub fn new(input: &dyn fmt::Debug) -> DebugFormatted {
65 DebugFormatted(format!("{:?}", input))
69 impl fmt::Debug for DebugFormatted {
70 fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
71 write!(w, "{}", self.0)
75 pub(crate) trait Dataflow<BD: BitDenotation> {
76 /// Sets up and runs the dataflow problem, using `p` to render results if
77 /// implementation so chooses.
78 fn dataflow<P>(&mut self, p: P) where P: Fn(&BD, BD::Idx) -> DebugFormatted {
79 let _ = p; // default implementation does not instrument process.
84 /// Sets up the entry, gen, and kill sets for this instance of a dataflow problem.
85 fn build_sets(&mut self);
87 /// Finds a fixed-point solution to this instance of a dataflow problem.
88 fn propagate(&mut self);
91 impl<'a, 'tcx: 'a, BD> Dataflow<BD> for DataflowBuilder<'a, 'tcx, BD> where BD: BitDenotation
93 fn dataflow<P>(&mut self, p: P) where P: Fn(&BD, BD::Idx) -> DebugFormatted {
94 self.flow_state.build_sets();
95 self.pre_dataflow_instrumentation(|c,i| p(c,i)).unwrap();
96 self.flow_state.propagate();
97 self.post_dataflow_instrumentation(|c,i| p(c,i)).unwrap();
100 fn build_sets(&mut self) { self.flow_state.build_sets(); }
101 fn propagate(&mut self) { self.flow_state.propagate(); }
104 pub(crate) fn has_rustc_mir_with(attrs: &[ast::Attribute], name: &str) -> Option<MetaItem> {
106 if attr.check_name("rustc_mir") {
107 let items = attr.meta_item_list();
108 for item in items.iter().flat_map(|l| l.iter()) {
109 match item.meta_item() {
110 Some(mi) if mi.check_name(name) => return Some(mi.clone()),
119 pub struct MoveDataParamEnv<'gcx, 'tcx> {
120 pub(crate) move_data: MoveData<'tcx>,
121 pub(crate) param_env: ty::ParamEnv<'gcx>,
124 pub(crate) fn do_dataflow<'a, 'gcx, 'tcx, BD, P>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
126 node_id: ast::NodeId,
127 attributes: &[ast::Attribute],
128 dead_unwinds: &IdxSet<BasicBlock>,
131 -> DataflowResults<BD>
132 where BD: BitDenotation + InitialFlow,
133 P: Fn(&BD, BD::Idx) -> DebugFormatted
135 let flow_state = DataflowAnalysis::new(mir, dead_unwinds, bd);
136 flow_state.run(tcx, node_id, attributes, p)
139 impl<'a, 'gcx: 'tcx, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation
141 pub(crate) fn run<P>(self,
142 tcx: TyCtxt<'a, 'gcx, 'tcx>,
143 node_id: ast::NodeId,
144 attributes: &[ast::Attribute],
145 p: P) -> DataflowResults<BD>
146 where P: Fn(&BD, BD::Idx) -> DebugFormatted
148 let name_found = |sess: &Session, attrs: &[ast::Attribute], name| -> Option<String> {
149 if let Some(item) = has_rustc_mir_with(attrs, name) {
150 if let Some(s) = item.value_str() {
151 return Some(s.to_string())
155 &format!("{} attribute requires a path", item.ident));
162 let print_preflow_to =
163 name_found(tcx.sess, attributes, "borrowck_graphviz_preflow");
164 let print_postflow_to =
165 name_found(tcx.sess, attributes, "borrowck_graphviz_postflow");
167 let mut mbcx = DataflowBuilder {
169 print_preflow_to, print_postflow_to, flow_state: self,
173 mbcx.flow_state.results()
177 struct PropagationContext<'b, 'a: 'b, 'tcx: 'a, O> where O: 'b + BitDenotation
179 builder: &'b mut DataflowAnalysis<'a, 'tcx, O>,
182 impl<'a, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation
184 fn propagate(&mut self) {
185 let mut temp = IdxSet::new_empty(self.flow_state.sets.bits_per_block);
186 let mut propcx = PropagationContext {
189 propcx.walk_cfg(&mut temp);
192 fn build_sets(&mut self) {
193 // First we need to build the entry-, gen- and kill-sets.
196 let sets = &mut self.flow_state.sets.for_block(mir::START_BLOCK.index());
197 self.flow_state.operator.start_block_effect(&mut sets.on_entry);
200 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
201 let &mir::BasicBlockData { ref statements, ref terminator, is_cleanup: _ } = data;
203 let mut interim_state;
204 let sets = &mut self.flow_state.sets.for_block(bb.index());
205 let track_intrablock = BD::accumulates_intrablock_state();
206 if track_intrablock {
207 debug!("swapping in mutable on_entry, initially {:?}", sets.on_entry);
208 interim_state = sets.on_entry.to_owned();
209 sets.on_entry = &mut interim_state;
211 for j_stmt in 0..statements.len() {
212 let location = Location { block: bb, statement_index: j_stmt };
213 self.flow_state.operator.before_statement_effect(sets, location);
214 self.flow_state.operator.statement_effect(sets, location);
215 if track_intrablock {
216 sets.apply_local_effect();
220 if terminator.is_some() {
221 let location = Location { block: bb, statement_index: statements.len() };
222 self.flow_state.operator.before_terminator_effect(sets, location);
223 self.flow_state.operator.terminator_effect(sets, location);
224 if track_intrablock {
225 sets.apply_local_effect();
232 impl<'b, 'a: 'b, 'tcx: 'a, BD> PropagationContext<'b, 'a, 'tcx, BD> where BD: BitDenotation
234 fn walk_cfg(&mut self, in_out: &mut IdxSet<BD::Idx>) {
235 let mut dirty_queue: WorkQueue<mir::BasicBlock> =
236 WorkQueue::with_all(self.builder.mir.basic_blocks().len());
237 let mir = self.builder.mir;
238 while let Some(bb) = dirty_queue.pop() {
239 let bb_data = &mir[bb];
241 let sets = self.builder.flow_state.sets.for_block(bb.index());
242 debug_assert!(in_out.words().len() == sets.on_entry.words().len());
243 in_out.overwrite(sets.on_entry);
244 in_out.union(sets.gen_set);
245 in_out.subtract(sets.kill_set);
247 self.builder.propagate_bits_into_graph_successors_of(
248 in_out, (bb, bb_data), &mut dirty_queue);
253 fn dataflow_path(context: &str, prepost: &str, path: &str) -> PathBuf {
254 format!("{}_{}", context, prepost);
255 let mut path = PathBuf::from(path);
256 let new_file_name = {
257 let orig_file_name = path.file_name().unwrap().to_str().unwrap();
258 format!("{}_{}", context, orig_file_name)
260 path.set_file_name(new_file_name);
264 impl<'a, 'tcx: 'a, BD> DataflowBuilder<'a, 'tcx, BD> where BD: BitDenotation
266 fn pre_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
267 where P: Fn(&BD, BD::Idx) -> DebugFormatted
269 if let Some(ref path_str) = self.print_preflow_to {
270 let path = dataflow_path(BD::name(), "preflow", path_str);
271 graphviz::print_borrowck_graph_to(self, &path, p)
277 fn post_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
278 where P: Fn(&BD, BD::Idx) -> DebugFormatted
280 if let Some(ref path_str) = self.print_postflow_to {
281 let path = dataflow_path(BD::name(), "postflow", path_str);
282 graphviz::print_borrowck_graph_to(self, &path, p)
289 /// DataflowResultsConsumer abstracts over walking the MIR with some
290 /// already constructed dataflow results.
292 /// It abstracts over the FlowState and also completely hides the
293 /// underlying flow analysis results, because it needs to handle cases
294 /// where we are combining the results of *multiple* flow analyses
295 /// (e.g. borrows + inits + uninits).
296 pub(crate) trait DataflowResultsConsumer<'a, 'tcx: 'a> {
297 type FlowState: FlowsAtLocation;
299 // Observation Hooks: override (at least one of) these to get analysis feedback.
300 fn visit_block_entry(&mut self,
302 _flow_state: &Self::FlowState) {}
304 fn visit_statement_entry(&mut self,
306 _stmt: &Statement<'tcx>,
307 _flow_state: &Self::FlowState) {}
309 fn visit_terminator_entry(&mut self,
311 _term: &Terminator<'tcx>,
312 _flow_state: &Self::FlowState) {}
314 // Main entry point: this drives the processing of results.
316 fn analyze_results(&mut self, flow_uninit: &mut Self::FlowState) {
317 let flow = flow_uninit;
318 for (bb, _) in traversal::reverse_postorder(self.mir()) {
319 flow.reset_to_entry_of(bb);
320 self.process_basic_block(bb, flow);
324 fn process_basic_block(&mut self, bb: BasicBlock, flow_state: &mut Self::FlowState) {
325 let BasicBlockData { ref statements, ref terminator, is_cleanup: _ } =
327 let mut location = Location { block: bb, statement_index: 0 };
328 for stmt in statements.iter() {
329 flow_state.reconstruct_statement_effect(location);
330 self.visit_statement_entry(location, stmt, flow_state);
331 flow_state.apply_local_effect(location);
332 location.statement_index += 1;
335 if let Some(ref term) = *terminator {
336 flow_state.reconstruct_terminator_effect(location);
337 self.visit_terminator_entry(location, term, flow_state);
339 // We don't need to apply the effect of the terminator,
340 // since we are only visiting dataflow state on control
341 // flow entry to the various nodes. (But we still need to
342 // reconstruct the effect, because the visit method might
347 // Delegated Hooks: Provide access to the MIR and process the flow state.
349 fn mir(&self) -> &'a Mir<'tcx>;
352 pub fn state_for_location<'tcx, T: BitDenotation>(loc: Location,
354 result: &DataflowResults<T>,
357 let mut on_entry = result.sets().on_entry_set_for(loc.block.index()).to_owned();
358 let mut kill_set = on_entry.to_hybrid();
359 let mut gen_set = kill_set.clone();
362 let mut sets = BlockSets {
363 on_entry: &mut on_entry,
364 kill_set: &mut kill_set,
365 gen_set: &mut gen_set,
368 for stmt in 0..loc.statement_index {
369 let mut stmt_loc = loc;
370 stmt_loc.statement_index = stmt;
371 analysis.before_statement_effect(&mut sets, stmt_loc);
372 analysis.statement_effect(&mut sets, stmt_loc);
375 // Apply the pre-statement effect of the statement we're evaluating.
376 if loc.statement_index == mir[loc.block].statements.len() {
377 analysis.before_terminator_effect(&mut sets, loc);
379 analysis.before_statement_effect(&mut sets, loc);
386 pub struct DataflowAnalysis<'a, 'tcx: 'a, O> where O: BitDenotation
388 flow_state: DataflowState<O>,
389 dead_unwinds: &'a IdxSet<mir::BasicBlock>,
393 impl<'a, 'tcx: 'a, O> DataflowAnalysis<'a, 'tcx, O> where O: BitDenotation
395 pub fn results(self) -> DataflowResults<O> {
396 DataflowResults(self.flow_state)
399 pub fn mir(&self) -> &'a Mir<'tcx> { self.mir }
402 pub struct DataflowResults<O>(pub(crate) DataflowState<O>) where O: BitDenotation;
404 impl<O: BitDenotation> DataflowResults<O> {
405 pub fn sets(&self) -> &AllSets<O::Idx> {
409 pub fn operator(&self) -> &O {
414 /// State of a dataflow analysis; couples a collection of bit sets
415 /// with operator used to initialize and merge bits during analysis.
416 pub struct DataflowState<O: BitDenotation>
418 /// All the sets for the analysis. (Factored into its
419 /// own structure so that we can borrow it mutably
420 /// on its own separate from other fields.)
421 pub sets: AllSets<O::Idx>,
423 /// operator used to initialize, combine, and interpret bits.
424 pub(crate) operator: O,
427 impl<O: BitDenotation> DataflowState<O> {
428 pub(crate) fn interpret_set<'c, P>(&self,
430 set: &IdxSet<O::Idx>,
432 -> Vec<DebugFormatted>
433 where P: Fn(&O, O::Idx) -> DebugFormatted
435 set.iter().map(|i| render_idx(o, i)).collect()
438 pub(crate) fn interpret_hybrid_set<'c, P>(&self,
440 set: &HybridIdxSet<O::Idx>,
442 -> Vec<DebugFormatted>
443 where P: Fn(&O, O::Idx) -> DebugFormatted
445 set.iter().map(|i| render_idx(o, i)).collect()
450 pub struct AllSets<E: Idx> {
451 /// Analysis bitwidth for each block.
452 bits_per_block: usize,
454 /// For each block, bits valid on entry to the block.
455 on_entry_sets: Vec<IdxSet<E>>,
457 /// For each block, bits generated by executing the statements +
458 /// terminator in the block -- with one caveat. In particular, for
459 /// *call terminators*, the effect of storing the destination is
460 /// not included, since that only takes effect on the **success**
461 /// edge (and not the unwind edge).
462 gen_sets: Vec<HybridIdxSet<E>>,
464 /// For each block, bits killed by executing the statements +
465 /// terminator in the block -- with one caveat. In particular, for
466 /// *call terminators*, the effect of storing the destination is
467 /// not included, since that only takes effect on the **success**
468 /// edge (and not the unwind edge).
469 kill_sets: Vec<HybridIdxSet<E>>,
472 /// Triple of sets associated with a given block.
474 /// Generally, one sets up `on_entry`, `gen_set`, and `kill_set` for
475 /// each block individually, and then runs the dataflow analysis which
476 /// iteratively modifies the various `on_entry` sets (but leaves the
477 /// other two sets unchanged, since they represent the effect of the
478 /// block, which should be invariant over the course of the analysis).
480 /// It is best to ensure that the intersection of `gen_set` and
481 /// `kill_set` is empty; otherwise the results of the dataflow will
482 /// have a hidden dependency on what order the bits are generated and
483 /// killed during the iteration. (This is such a good idea that the
484 /// `fn gen` and `fn kill` methods that set their state enforce this
487 pub struct BlockSets<'a, E: Idx> {
488 /// Dataflow state immediately before control flow enters the given block.
489 pub(crate) on_entry: &'a mut IdxSet<E>,
491 /// Bits that are set to 1 by the time we exit the given block. Hybrid
492 /// because it usually contains only 0 or 1 elements.
493 pub(crate) gen_set: &'a mut HybridIdxSet<E>,
495 /// Bits that are set to 0 by the time we exit the given block. Hybrid
496 /// because it usually contains only 0 or 1 elements.
497 pub(crate) kill_set: &'a mut HybridIdxSet<E>,
500 impl<'a, E:Idx> BlockSets<'a, E> {
501 fn gen(&mut self, e: &E) {
503 self.kill_set.remove(e);
505 fn gen_all<I>(&mut self, i: I)
506 where I: IntoIterator,
510 self.gen(j.borrow());
514 fn kill(&mut self, e: &E) {
515 self.gen_set.remove(e);
516 self.kill_set.add(e);
519 fn kill_all<I>(&mut self, i: I)
520 where I: IntoIterator,
524 self.kill(j.borrow());
528 fn apply_local_effect(&mut self) {
529 self.on_entry.union(self.gen_set);
530 self.on_entry.subtract(self.kill_set);
534 impl<E:Idx> AllSets<E> {
535 pub fn bits_per_block(&self) -> usize { self.bits_per_block }
536 pub fn for_block(&mut self, block_idx: usize) -> BlockSets<E> {
538 on_entry: &mut self.on_entry_sets[block_idx],
539 gen_set: &mut self.gen_sets[block_idx],
540 kill_set: &mut self.kill_sets[block_idx],
544 pub fn on_entry_set_for(&self, block_idx: usize) -> &IdxSet<E> {
545 &self.on_entry_sets[block_idx]
547 pub fn gen_set_for(&self, block_idx: usize) -> &HybridIdxSet<E> {
548 &self.gen_sets[block_idx]
550 pub fn kill_set_for(&self, block_idx: usize) -> &HybridIdxSet<E> {
551 &self.kill_sets[block_idx]
555 /// Parameterization for the precise form of data flow that is used.
556 /// `InitialFlow` handles initializing the bitvectors before any
557 /// code is inspected by the analysis. Analyses that need more nuanced
558 /// initialization (e.g. they need to consult the results of some other
559 /// dataflow analysis to set up the initial bitvectors) should not
561 pub trait InitialFlow {
562 /// Specifies the initial value for each bit in the `on_entry` set
563 fn bottom_value() -> bool;
566 pub trait BitDenotation: BitwiseOperator {
567 /// Specifies what index type is used to access the bitvector.
570 /// Some analyses want to accumulate knowledge within a block when
571 /// analyzing its statements for building the gen/kill sets. Override
572 /// this method to return true in such cases.
574 /// When this returns true, the statement-effect (re)construction
575 /// will clone the `on_entry` state and pass along a reference via
576 /// `sets.on_entry` to that local clone into `statement_effect` and
577 /// `terminator_effect`).
579 /// When it's false, no local clone is constructed; instead a
580 /// reference directly into `on_entry` is passed along via
581 /// `sets.on_entry` instead, which represents the flow state at
582 /// the block's start, not necessarily the state immediately prior
583 /// to the statement/terminator under analysis.
585 /// In either case, the passed reference is mutable; but this is a
586 /// wart from using the `BlockSets` type in the API; the intention
587 /// is that the `statement_effect` and `terminator_effect` methods
588 /// mutate only the gen/kill sets.
590 /// FIXME: We should consider enforcing the intention described in
591 /// the previous paragraph by passing the three sets in separate
592 /// parameters to encode their distinct mutabilities.
593 fn accumulates_intrablock_state() -> bool { false }
595 /// A name describing the dataflow analysis that this
596 /// BitDenotation is supporting. The name should be something
597 /// suitable for plugging in as part of a filename e.g. avoid
598 /// space-characters or other things that tend to look bad on a
599 /// file system, like slashes or periods. It is also better for
600 /// the name to be reasonably short, again because it will be
601 /// plugged into a filename.
602 fn name() -> &'static str;
604 /// Size of each bitvector allocated for each block in the analysis.
605 fn bits_per_block(&self) -> usize;
607 /// Mutates the entry set according to the effects that
608 /// have been established *prior* to entering the start
609 /// block. This can't access the gen/kill sets, because
610 /// these won't be accounted for correctly.
612 /// (For example, establishing the call arguments.)
613 fn start_block_effect(&self, entry_set: &mut IdxSet<Self::Idx>);
615 /// Similar to `statement_effect`, except it applies
616 /// *just before* the statement rather than *just after* it.
618 /// This matters for "dataflow at location" APIs, because the
619 /// before-statement effect is visible while visiting the
620 /// statement, while the after-statement effect only becomes
621 /// visible at the next statement.
623 /// Both the before-statement and after-statement effects are
624 /// applied, in that order, before moving for the next
626 fn before_statement_effect(&self,
627 _sets: &mut BlockSets<Self::Idx>,
628 _location: Location) {}
630 /// Mutates the block-sets (the flow sets for the given
631 /// basic block) according to the effects of evaluating statement.
633 /// This is used, in particular, for building up the
634 /// "transfer-function" representing the overall-effect of the
635 /// block, represented via GEN and KILL sets.
637 /// The statement is identified as `bb_data[idx_stmt]`, where
638 /// `bb_data` is the sequence of statements identified by `bb` in
640 fn statement_effect(&self,
641 sets: &mut BlockSets<Self::Idx>,
644 /// Similar to `terminator_effect`, except it applies
645 /// *just before* the terminator rather than *just after* it.
647 /// This matters for "dataflow at location" APIs, because the
648 /// before-terminator effect is visible while visiting the
649 /// terminator, while the after-terminator effect only becomes
650 /// visible at the terminator's successors.
652 /// Both the before-terminator and after-terminator effects are
653 /// applied, in that order, before moving for the next
655 fn before_terminator_effect(&self,
656 _sets: &mut BlockSets<Self::Idx>,
657 _location: Location) {}
659 /// Mutates the block-sets (the flow sets for the given
660 /// basic block) according to the effects of evaluating
663 /// This is used, in particular, for building up the
664 /// "transfer-function" representing the overall-effect of the
665 /// block, represented via GEN and KILL sets.
667 /// The effects applied here cannot depend on which branch the
669 fn terminator_effect(&self,
670 sets: &mut BlockSets<Self::Idx>,
673 /// Mutates the block-sets according to the (flow-dependent)
674 /// effect of a successful return from a Call terminator.
676 /// If basic-block BB_x ends with a call-instruction that, upon
677 /// successful return, flows to BB_y, then this method will be
678 /// called on the exit flow-state of BB_x in order to set up the
679 /// entry flow-state of BB_y.
681 /// This is used, in particular, as a special case during the
682 /// "propagate" loop where all of the basic blocks are repeatedly
683 /// visited. Since the effects of a Call terminator are
684 /// flow-dependent, the current MIR cannot encode them via just
685 /// GEN and KILL sets attached to the block, and so instead we add
686 /// this extra machinery to represent the flow-dependent effect.
688 /// FIXME: Right now this is a bit of a wart in the API. It might
689 /// be better to represent this as an additional gen- and
690 /// kill-sets associated with each edge coming out of the basic
692 fn propagate_call_return(&self,
693 in_out: &mut IdxSet<Self::Idx>,
694 call_bb: mir::BasicBlock,
695 dest_bb: mir::BasicBlock,
696 dest_place: &mir::Place);
699 impl<'a, 'tcx, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation
701 pub fn new(mir: &'a Mir<'tcx>,
702 dead_unwinds: &'a IdxSet<mir::BasicBlock>,
703 denotation: D) -> Self where D: InitialFlow {
704 let bits_per_block = denotation.bits_per_block();
705 let num_blocks = mir.basic_blocks().len();
707 let on_entry_sets = if D::bottom_value() {
708 vec![IdxSet::new_filled(bits_per_block); num_blocks]
710 vec![IdxSet::new_empty(bits_per_block); num_blocks]
712 let gen_sets = vec![HybridIdxSet::new_empty(bits_per_block); num_blocks];
713 let kill_sets = gen_sets.clone();
718 flow_state: DataflowState {
725 operator: denotation,
730 pub fn new_from_sets(mir: &'a Mir<'tcx>,
731 dead_unwinds: &'a IdxSet<mir::BasicBlock>,
732 sets: AllSets<D::Idx>,
733 denotation: D) -> Self {
737 flow_state: DataflowState {
739 operator: denotation,
745 impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation
747 /// Propagates the bits of `in_out` into all the successors of `bb`,
748 /// using bitwise operator denoted by `self.operator`.
750 /// For most blocks, this is entirely uniform. However, for blocks
751 /// that end with a call terminator, the effect of the call on the
752 /// dataflow state may depend on whether the call returned
753 /// successfully or unwound.
755 /// To reflect this, the `propagate_call_return` method of the
756 /// `BitDenotation` mutates `in_out` when propagating `in_out` via
757 /// a call terminator; such mutation is performed *last*, to
758 /// ensure its side-effects do not leak elsewhere (e.g. into
760 fn propagate_bits_into_graph_successors_of(
762 in_out: &mut IdxSet<D::Idx>,
763 (bb, bb_data): (mir::BasicBlock, &mir::BasicBlockData),
764 dirty_list: &mut WorkQueue<mir::BasicBlock>)
766 match bb_data.terminator().kind {
767 mir::TerminatorKind::Return |
768 mir::TerminatorKind::Resume |
769 mir::TerminatorKind::Abort |
770 mir::TerminatorKind::GeneratorDrop |
771 mir::TerminatorKind::Unreachable => {}
772 mir::TerminatorKind::Goto { target } |
773 mir::TerminatorKind::Assert { target, cleanup: None, .. } |
774 mir::TerminatorKind::Yield { resume: target, drop: None, .. } |
775 mir::TerminatorKind::Drop { target, location: _, unwind: None } |
776 mir::TerminatorKind::DropAndReplace {
777 target, value: _, location: _, unwind: None
779 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
781 mir::TerminatorKind::Yield { resume: target, drop: Some(drop), .. } => {
782 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
783 self.propagate_bits_into_entry_set_for(in_out, drop, dirty_list);
785 mir::TerminatorKind::Assert { target, cleanup: Some(unwind), .. } |
786 mir::TerminatorKind::Drop { target, location: _, unwind: Some(unwind) } |
787 mir::TerminatorKind::DropAndReplace {
788 target, value: _, location: _, unwind: Some(unwind)
790 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
791 if !self.dead_unwinds.contains(&bb) {
792 self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
795 mir::TerminatorKind::SwitchInt { ref targets, .. } => {
796 for target in targets {
797 self.propagate_bits_into_entry_set_for(in_out, *target, dirty_list);
800 mir::TerminatorKind::Call { cleanup, ref destination, func: _, args: _ } => {
801 if let Some(unwind) = cleanup {
802 if !self.dead_unwinds.contains(&bb) {
803 self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
806 if let Some((ref dest_place, dest_bb)) = *destination {
807 // N.B.: This must be done *last*, after all other
808 // propagation, as documented in comment above.
809 self.flow_state.operator.propagate_call_return(
810 in_out, bb, dest_bb, dest_place);
811 self.propagate_bits_into_entry_set_for(in_out, dest_bb, dirty_list);
814 mir::TerminatorKind::FalseEdges { real_target, ref imaginary_targets } => {
815 self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
816 for target in imaginary_targets {
817 self.propagate_bits_into_entry_set_for(in_out, *target, dirty_list);
820 mir::TerminatorKind::FalseUnwind { real_target, unwind } => {
821 self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
822 if let Some(unwind) = unwind {
823 if !self.dead_unwinds.contains(&bb) {
824 self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
831 fn propagate_bits_into_entry_set_for(&mut self,
832 in_out: &IdxSet<D::Idx>,
834 dirty_queue: &mut WorkQueue<mir::BasicBlock>) {
835 let entry_set = self.flow_state.sets.for_block(bb.index()).on_entry;
836 let set_changed = bitwise(entry_set.words_mut(),
838 &self.flow_state.operator);
840 dirty_queue.insert(bb);