1 use syntax::ast::{self, MetaItem};
3 use rustc_data_structures::bit_set::{BitSet, BitSetOperator, HybridBitSet};
4 use rustc_data_structures::indexed_vec::Idx;
5 use rustc_data_structures::work_queue::WorkQueue;
7 use rustc::hir::def_id::DefId;
8 use rustc::ty::{self, TyCtxt};
9 use rustc::mir::{self, Mir, BasicBlock, BasicBlockData, Location, Statement, Terminator};
10 use rustc::mir::traversal;
11 use rustc::session::Session;
13 use std::borrow::Borrow;
16 use std::path::PathBuf;
19 pub use self::impls::{MaybeStorageLive};
20 pub use self::impls::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
21 pub use self::impls::DefinitelyInitializedPlaces;
22 pub use self::impls::EverInitializedPlaces;
23 pub use self::impls::borrows::Borrows;
24 pub use self::impls::HaveBeenBorrowedLocals;
25 pub use self::at_location::{FlowAtLocation, FlowsAtLocation};
26 pub(crate) use self::drop_flag_effects::*;
28 use self::move_paths::MoveData;
31 pub mod drop_flag_effects;
36 pub(crate) use self::move_paths::indexes;
38 pub(crate) struct DataflowBuilder<'a, 'tcx: 'a, BD>
40 BD: BitDenotation<'tcx>
43 flow_state: DataflowAnalysis<'a, 'tcx, BD>,
44 print_preflow_to: Option<String>,
45 print_postflow_to: Option<String>,
48 /// `DebugFormatted` encapsulates the "{:?}" rendering of some
49 /// arbitrary value. This way: you pay cost of allocating an extra
50 /// string (as well as that of rendering up-front); in exchange, you
51 /// don't have to hand over ownership of your value or deal with
53 pub(crate) struct DebugFormatted(String);
56 pub fn new(input: &dyn fmt::Debug) -> DebugFormatted {
57 DebugFormatted(format!("{:?}", input))
61 impl fmt::Debug for DebugFormatted {
62 fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
63 write!(w, "{}", self.0)
67 pub(crate) trait Dataflow<'tcx, BD: BitDenotation<'tcx>> {
68 /// Sets up and runs the dataflow problem, using `p` to render results if
69 /// implementation so chooses.
70 fn dataflow<P>(&mut self, p: P) where P: Fn(&BD, BD::Idx) -> DebugFormatted {
71 let _ = p; // default implementation does not instrument process.
76 /// Sets up the entry, gen, and kill sets for this instance of a dataflow problem.
77 fn build_sets(&mut self);
79 /// Finds a fixed-point solution to this instance of a dataflow problem.
80 fn propagate(&mut self);
83 impl<'a, 'tcx: 'a, BD> Dataflow<'tcx, BD> for DataflowBuilder<'a, 'tcx, BD>
85 BD: BitDenotation<'tcx>
87 fn dataflow<P>(&mut self, p: P) where P: Fn(&BD, BD::Idx) -> DebugFormatted {
88 self.flow_state.build_sets();
89 self.pre_dataflow_instrumentation(|c,i| p(c,i)).unwrap();
90 self.flow_state.propagate();
91 self.post_dataflow_instrumentation(|c,i| p(c,i)).unwrap();
94 fn build_sets(&mut self) { self.flow_state.build_sets(); }
95 fn propagate(&mut self) { self.flow_state.propagate(); }
98 pub(crate) fn has_rustc_mir_with(attrs: &[ast::Attribute], name: &str) -> Option<MetaItem> {
100 if attr.check_name("rustc_mir") {
101 let items = attr.meta_item_list();
102 for item in items.iter().flat_map(|l| l.iter()) {
103 match item.meta_item() {
104 Some(mi) if mi.check_name(name) => return Some(mi.clone()),
113 pub struct MoveDataParamEnv<'gcx, 'tcx> {
114 pub(crate) move_data: MoveData<'tcx>,
115 pub(crate) param_env: ty::ParamEnv<'gcx>,
118 pub(crate) fn do_dataflow<'a, 'gcx, 'tcx, BD, P>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
121 attributes: &[ast::Attribute],
122 dead_unwinds: &BitSet<BasicBlock>,
125 -> DataflowResults<'tcx, BD>
126 where BD: BitDenotation<'tcx> + InitialFlow,
127 P: Fn(&BD, BD::Idx) -> DebugFormatted
129 let flow_state = DataflowAnalysis::new(mir, dead_unwinds, bd);
130 flow_state.run(tcx, def_id, attributes, p)
133 impl<'a, 'gcx: 'tcx, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation<'tcx>
135 pub(crate) fn run<P>(self,
136 tcx: TyCtxt<'a, 'gcx, 'tcx>,
138 attributes: &[ast::Attribute],
139 p: P) -> DataflowResults<'tcx, BD>
140 where P: Fn(&BD, BD::Idx) -> DebugFormatted
142 let name_found = |sess: &Session, attrs: &[ast::Attribute], name| -> Option<String> {
143 if let Some(item) = has_rustc_mir_with(attrs, name) {
144 if let Some(s) = item.value_str() {
145 return Some(s.to_string())
149 &format!("{} attribute requires a path", item.path));
156 let print_preflow_to =
157 name_found(tcx.sess, attributes, "borrowck_graphviz_preflow");
158 let print_postflow_to =
159 name_found(tcx.sess, attributes, "borrowck_graphviz_postflow");
161 let mut mbcx = DataflowBuilder {
163 print_preflow_to, print_postflow_to, flow_state: self,
167 mbcx.flow_state.results()
171 struct PropagationContext<'b, 'a: 'b, 'tcx: 'a, O> where O: 'b + BitDenotation<'tcx>
173 builder: &'b mut DataflowAnalysis<'a, 'tcx, O>,
176 impl<'a, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation<'tcx>
178 fn propagate(&mut self) {
179 let mut temp = BitSet::new_empty(self.flow_state.sets.bits_per_block);
180 let mut propcx = PropagationContext {
183 propcx.walk_cfg(&mut temp);
186 fn build_sets(&mut self) {
187 // First we need to build the entry-, gen- and kill-sets.
190 let sets = &mut self.flow_state.sets.for_block(mir::START_BLOCK.index());
191 self.flow_state.operator.start_block_effect(&mut sets.on_entry);
194 for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
195 let &mir::BasicBlockData { ref statements, ref terminator, is_cleanup: _ } = data;
197 let mut interim_state;
198 let sets = &mut self.flow_state.sets.for_block(bb.index());
199 let track_intrablock = BD::accumulates_intrablock_state();
200 if track_intrablock {
201 debug!("swapping in mutable on_entry, initially {:?}", sets.on_entry);
202 interim_state = sets.on_entry.to_owned();
203 sets.on_entry = &mut interim_state;
205 for j_stmt in 0..statements.len() {
206 let location = Location { block: bb, statement_index: j_stmt };
207 self.flow_state.operator.before_statement_effect(sets, location);
208 self.flow_state.operator.statement_effect(sets, location);
209 if track_intrablock {
210 sets.apply_local_effect();
214 if terminator.is_some() {
215 let location = Location { block: bb, statement_index: statements.len() };
216 self.flow_state.operator.before_terminator_effect(sets, location);
217 self.flow_state.operator.terminator_effect(sets, location);
218 if track_intrablock {
219 sets.apply_local_effect();
226 impl<'b, 'a: 'b, 'tcx: 'a, BD> PropagationContext<'b, 'a, 'tcx, BD> where BD: BitDenotation<'tcx>
228 fn walk_cfg(&mut self, in_out: &mut BitSet<BD::Idx>) {
229 let mut dirty_queue: WorkQueue<mir::BasicBlock> =
230 WorkQueue::with_all(self.builder.mir.basic_blocks().len());
231 let mir = self.builder.mir;
232 while let Some(bb) = dirty_queue.pop() {
233 let bb_data = &mir[bb];
235 let sets = self.builder.flow_state.sets.for_block(bb.index());
236 debug_assert!(in_out.words().len() == sets.on_entry.words().len());
237 in_out.overwrite(sets.on_entry);
238 in_out.union(sets.gen_set);
239 in_out.subtract(sets.kill_set);
241 self.builder.propagate_bits_into_graph_successors_of(
242 in_out, (bb, bb_data), &mut dirty_queue);
247 fn dataflow_path(context: &str, path: &str) -> PathBuf {
248 let mut path = PathBuf::from(path);
249 let new_file_name = {
250 let orig_file_name = path.file_name().unwrap().to_str().unwrap();
251 format!("{}_{}", context, orig_file_name)
253 path.set_file_name(new_file_name);
257 impl<'a, 'tcx: 'a, BD> DataflowBuilder<'a, 'tcx, BD> where BD: BitDenotation<'tcx>
259 fn pre_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
260 where P: Fn(&BD, BD::Idx) -> DebugFormatted
262 if let Some(ref path_str) = self.print_preflow_to {
263 let path = dataflow_path(BD::name(), path_str);
264 graphviz::print_borrowck_graph_to(self, &path, p)
270 fn post_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
271 where P: Fn(&BD, BD::Idx) -> DebugFormatted
273 if let Some(ref path_str) = self.print_postflow_to {
274 let path = dataflow_path(BD::name(), path_str);
275 graphviz::print_borrowck_graph_to(self, &path, p)
282 /// DataflowResultsConsumer abstracts over walking the MIR with some
283 /// already constructed dataflow results.
285 /// It abstracts over the FlowState and also completely hides the
286 /// underlying flow analysis results, because it needs to handle cases
287 /// where we are combining the results of *multiple* flow analyses
288 /// (e.g., borrows + inits + uninits).
289 pub(crate) trait DataflowResultsConsumer<'a, 'tcx: 'a> {
290 type FlowState: FlowsAtLocation;
292 // Observation Hooks: override (at least one of) these to get analysis feedback.
293 fn visit_block_entry(&mut self,
295 _flow_state: &Self::FlowState) {}
297 fn visit_statement_entry(&mut self,
299 _stmt: &Statement<'tcx>,
300 _flow_state: &Self::FlowState) {}
302 fn visit_terminator_entry(&mut self,
304 _term: &Terminator<'tcx>,
305 _flow_state: &Self::FlowState) {}
307 // Main entry point: this drives the processing of results.
309 fn analyze_results(&mut self, flow_uninit: &mut Self::FlowState) {
310 let flow = flow_uninit;
311 for (bb, _) in traversal::reverse_postorder(self.mir()) {
312 flow.reset_to_entry_of(bb);
313 self.process_basic_block(bb, flow);
317 fn process_basic_block(&mut self, bb: BasicBlock, flow_state: &mut Self::FlowState) {
318 let BasicBlockData { ref statements, ref terminator, is_cleanup: _ } =
320 let mut location = Location { block: bb, statement_index: 0 };
321 for stmt in statements.iter() {
322 flow_state.reconstruct_statement_effect(location);
323 self.visit_statement_entry(location, stmt, flow_state);
324 flow_state.apply_local_effect(location);
325 location.statement_index += 1;
328 if let Some(ref term) = *terminator {
329 flow_state.reconstruct_terminator_effect(location);
330 self.visit_terminator_entry(location, term, flow_state);
332 // We don't need to apply the effect of the terminator,
333 // since we are only visiting dataflow state on control
334 // flow entry to the various nodes. (But we still need to
335 // reconstruct the effect, because the visit method might
340 // Delegated Hooks: Provide access to the MIR and process the flow state.
342 fn mir(&self) -> &'a Mir<'tcx>;
345 pub fn state_for_location<'tcx, T: BitDenotation<'tcx>>(loc: Location,
347 result: &DataflowResults<'tcx, T>,
350 let mut on_entry = result.sets().on_entry_set_for(loc.block.index()).to_owned();
351 let mut kill_set = on_entry.to_hybrid();
352 let mut gen_set = kill_set.clone();
355 let mut sets = BlockSets {
356 on_entry: &mut on_entry,
357 kill_set: &mut kill_set,
358 gen_set: &mut gen_set,
361 for stmt in 0..loc.statement_index {
362 let mut stmt_loc = loc;
363 stmt_loc.statement_index = stmt;
364 analysis.before_statement_effect(&mut sets, stmt_loc);
365 analysis.statement_effect(&mut sets, stmt_loc);
368 // Apply the pre-statement effect of the statement we're evaluating.
369 if loc.statement_index == mir[loc.block].statements.len() {
370 analysis.before_terminator_effect(&mut sets, loc);
372 analysis.before_statement_effect(&mut sets, loc);
379 pub struct DataflowAnalysis<'a, 'tcx: 'a, O> where O: BitDenotation<'tcx>
381 flow_state: DataflowState<'tcx, O>,
382 dead_unwinds: &'a BitSet<mir::BasicBlock>,
386 impl<'a, 'tcx: 'a, O> DataflowAnalysis<'a, 'tcx, O> where O: BitDenotation<'tcx>
388 pub fn results(self) -> DataflowResults<'tcx, O> {
389 DataflowResults(self.flow_state)
392 pub fn mir(&self) -> &'a Mir<'tcx> { self.mir }
395 pub struct DataflowResults<'tcx, O>(pub(crate) DataflowState<'tcx, O>) where O: BitDenotation<'tcx>;
397 impl<'tcx, O: BitDenotation<'tcx>> DataflowResults<'tcx, O> {
398 pub fn sets(&self) -> &AllSets<O::Idx> {
402 pub fn operator(&self) -> &O {
407 /// State of a dataflow analysis; couples a collection of bit sets
408 /// with operator used to initialize and merge bits during analysis.
409 pub struct DataflowState<'tcx, O: BitDenotation<'tcx>>
411 /// All the sets for the analysis. (Factored into its
412 /// own structure so that we can borrow it mutably
413 /// on its own separate from other fields.)
414 pub sets: AllSets<O::Idx>,
416 /// operator used to initialize, combine, and interpret bits.
417 pub(crate) operator: O,
420 impl<'tcx, O: BitDenotation<'tcx>> DataflowState<'tcx, O> {
421 pub(crate) fn interpret_set<'c, P>(&self,
423 set: &BitSet<O::Idx>,
425 -> Vec<DebugFormatted>
426 where P: Fn(&O, O::Idx) -> DebugFormatted
428 set.iter().map(|i| render_idx(o, i)).collect()
431 pub(crate) fn interpret_hybrid_set<'c, P>(&self,
433 set: &HybridBitSet<O::Idx>,
435 -> Vec<DebugFormatted>
436 where P: Fn(&O, O::Idx) -> DebugFormatted
438 set.iter().map(|i| render_idx(o, i)).collect()
443 pub struct AllSets<E: Idx> {
444 /// Analysis bitwidth for each block.
445 bits_per_block: usize,
447 /// For each block, bits valid on entry to the block.
448 on_entry_sets: Vec<BitSet<E>>,
450 /// For each block, bits generated by executing the statements +
451 /// terminator in the block -- with one caveat. In particular, for
452 /// *call terminators*, the effect of storing the destination is
453 /// not included, since that only takes effect on the **success**
454 /// edge (and not the unwind edge).
455 gen_sets: Vec<HybridBitSet<E>>,
457 /// For each block, bits killed 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 kill_sets: Vec<HybridBitSet<E>>,
465 /// Triple of sets associated with a given block.
467 /// Generally, one sets up `on_entry`, `gen_set`, and `kill_set` for
468 /// each block individually, and then runs the dataflow analysis which
469 /// iteratively modifies the various `on_entry` sets (but leaves the
470 /// other two sets unchanged, since they represent the effect of the
471 /// block, which should be invariant over the course of the analysis).
473 /// It is best to ensure that the intersection of `gen_set` and
474 /// `kill_set` is empty; otherwise the results of the dataflow will
475 /// have a hidden dependency on what order the bits are generated and
476 /// killed during the iteration. (This is such a good idea that the
477 /// `fn gen` and `fn kill` methods that set their state enforce this
480 pub struct BlockSets<'a, E: Idx> {
481 /// Dataflow state immediately before control flow enters the given block.
482 pub(crate) on_entry: &'a mut BitSet<E>,
484 /// Bits that are set to 1 by the time we exit the given block. Hybrid
485 /// because it usually contains only 0 or 1 elements.
486 pub(crate) gen_set: &'a mut HybridBitSet<E>,
488 /// Bits that are set to 0 by the time we exit the given block. Hybrid
489 /// because it usually contains only 0 or 1 elements.
490 pub(crate) kill_set: &'a mut HybridBitSet<E>,
493 impl<'a, E:Idx> BlockSets<'a, E> {
494 fn gen(&mut self, e: E) {
495 self.gen_set.insert(e);
496 self.kill_set.remove(e);
498 fn gen_all<I>(&mut self, i: I)
499 where I: IntoIterator,
503 self.gen(*j.borrow());
507 fn kill(&mut self, e: E) {
508 self.gen_set.remove(e);
509 self.kill_set.insert(e);
512 fn kill_all<I>(&mut self, i: I)
513 where I: IntoIterator,
517 self.kill(*j.borrow());
521 fn apply_local_effect(&mut self) {
522 self.on_entry.union(self.gen_set);
523 self.on_entry.subtract(self.kill_set);
527 impl<E:Idx> AllSets<E> {
528 pub fn bits_per_block(&self) -> usize { self.bits_per_block }
529 pub fn for_block(&mut self, block_idx: usize) -> BlockSets<'_, E> {
531 on_entry: &mut self.on_entry_sets[block_idx],
532 gen_set: &mut self.gen_sets[block_idx],
533 kill_set: &mut self.kill_sets[block_idx],
537 pub fn on_entry_set_for(&self, block_idx: usize) -> &BitSet<E> {
538 &self.on_entry_sets[block_idx]
540 pub fn gen_set_for(&self, block_idx: usize) -> &HybridBitSet<E> {
541 &self.gen_sets[block_idx]
543 pub fn kill_set_for(&self, block_idx: usize) -> &HybridBitSet<E> {
544 &self.kill_sets[block_idx]
548 /// Parameterization for the precise form of data flow that is used.
549 /// `InitialFlow` handles initializing the bitvectors before any
550 /// code is inspected by the analysis. Analyses that need more nuanced
551 /// initialization (e.g., they need to consult the results of some other
552 /// dataflow analysis to set up the initial bitvectors) should not
554 pub trait InitialFlow {
555 /// Specifies the initial value for each bit in the `on_entry` set
556 fn bottom_value() -> bool;
559 pub trait BitDenotation<'tcx>: BitSetOperator {
560 /// Specifies what index type is used to access the bitvector.
563 /// Some analyses want to accumulate knowledge within a block when
564 /// analyzing its statements for building the gen/kill sets. Override
565 /// this method to return true in such cases.
567 /// When this returns true, the statement-effect (re)construction
568 /// will clone the `on_entry` state and pass along a reference via
569 /// `sets.on_entry` to that local clone into `statement_effect` and
570 /// `terminator_effect`).
572 /// When it's false, no local clone is constructed; instead a
573 /// reference directly into `on_entry` is passed along via
574 /// `sets.on_entry` instead, which represents the flow state at
575 /// the block's start, not necessarily the state immediately prior
576 /// to the statement/terminator under analysis.
578 /// In either case, the passed reference is mutable, but this is a
579 /// wart from using the `BlockSets` type in the API; the intention
580 /// is that the `statement_effect` and `terminator_effect` methods
581 /// mutate only the gen/kill sets.
583 // FIXME: we should consider enforcing the intention described in
584 // the previous paragraph by passing the three sets in separate
585 // parameters to encode their distinct mutabilities.
586 fn accumulates_intrablock_state() -> bool { false }
588 /// A name describing the dataflow analysis that this
589 /// `BitDenotation` is supporting. The name should be something
590 /// suitable for plugging in as part of a filename (i.e., avoid
591 /// space-characters or other things that tend to look bad on a
592 /// file system, like slashes or periods). It is also better for
593 /// the name to be reasonably short, again because it will be
594 /// plugged into a filename.
595 fn name() -> &'static str;
597 /// Size of each bitvector allocated for each block in the analysis.
598 fn bits_per_block(&self) -> usize;
600 /// Mutates the entry set according to the effects that
601 /// have been established *prior* to entering the start
602 /// block. This can't access the gen/kill sets, because
603 /// these won't be accounted for correctly.
605 /// (For example, establishing the call arguments.)
606 fn start_block_effect(&self, entry_set: &mut BitSet<Self::Idx>);
608 /// Similar to `statement_effect`, except it applies
609 /// *just before* the statement rather than *just after* it.
611 /// This matters for "dataflow at location" APIs, because the
612 /// before-statement effect is visible while visiting the
613 /// statement, while the after-statement effect only becomes
614 /// visible at the next statement.
616 /// Both the before-statement and after-statement effects are
617 /// applied, in that order, before moving for the next
619 fn before_statement_effect(&self,
620 _sets: &mut BlockSets<'_, Self::Idx>,
621 _location: Location) {}
623 /// Mutates the block-sets (the flow sets for the given
624 /// basic block) according to the effects of evaluating statement.
626 /// This is used, in particular, for building up the
627 /// "transfer-function" representing the overall-effect of the
628 /// block, represented via GEN and KILL sets.
630 /// The statement is identified as `bb_data[idx_stmt]`, where
631 /// `bb_data` is the sequence of statements identified by `bb` in
633 fn statement_effect(&self,
634 sets: &mut BlockSets<'_, Self::Idx>,
637 /// Similar to `terminator_effect`, except it applies
638 /// *just before* the terminator rather than *just after* it.
640 /// This matters for "dataflow at location" APIs, because the
641 /// before-terminator effect is visible while visiting the
642 /// terminator, while the after-terminator effect only becomes
643 /// visible at the terminator's successors.
645 /// Both the before-terminator and after-terminator effects are
646 /// applied, in that order, before moving for the next
648 fn before_terminator_effect(&self,
649 _sets: &mut BlockSets<'_, Self::Idx>,
650 _location: Location) {}
652 /// Mutates the block-sets (the flow sets for the given
653 /// basic block) according to the effects of evaluating
656 /// This is used, in particular, for building up the
657 /// "transfer-function" representing the overall-effect of the
658 /// block, represented via GEN and KILL sets.
660 /// The effects applied here cannot depend on which branch the
662 fn terminator_effect(&self,
663 sets: &mut BlockSets<'_, Self::Idx>,
666 /// Mutates the block-sets according to the (flow-dependent)
667 /// effect of a successful return from a Call terminator.
669 /// If basic-block BB_x ends with a call-instruction that, upon
670 /// successful return, flows to BB_y, then this method will be
671 /// called on the exit flow-state of BB_x in order to set up the
672 /// entry flow-state of BB_y.
674 /// This is used, in particular, as a special case during the
675 /// "propagate" loop where all of the basic blocks are repeatedly
676 /// visited. Since the effects of a Call terminator are
677 /// flow-dependent, the current MIR cannot encode them via just
678 /// GEN and KILL sets attached to the block, and so instead we add
679 /// this extra machinery to represent the flow-dependent effect.
681 // FIXME: right now this is a bit of a wart in the API. It might
682 // be better to represent this as an additional gen- and
683 // kill-sets associated with each edge coming out of the basic
685 fn propagate_call_return(
687 in_out: &mut BitSet<Self::Idx>,
688 call_bb: mir::BasicBlock,
689 dest_bb: mir::BasicBlock,
690 dest_place: &mir::Place<'tcx>,
694 impl<'a, 'tcx, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation<'tcx>
696 pub fn new(mir: &'a Mir<'tcx>,
697 dead_unwinds: &'a BitSet<mir::BasicBlock>,
698 denotation: D) -> Self where D: InitialFlow {
699 let bits_per_block = denotation.bits_per_block();
700 let num_blocks = mir.basic_blocks().len();
702 let on_entry_sets = if D::bottom_value() {
703 vec![BitSet::new_filled(bits_per_block); num_blocks]
705 vec![BitSet::new_empty(bits_per_block); num_blocks]
707 let gen_sets = vec![HybridBitSet::new_empty(bits_per_block); num_blocks];
708 let kill_sets = gen_sets.clone();
713 flow_state: DataflowState {
720 operator: denotation,
726 impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation<'tcx> {
727 /// Propagates the bits of `in_out` into all the successors of `bb`,
728 /// using bitwise operator denoted by `self.operator`.
730 /// For most blocks, this is entirely uniform. However, for blocks
731 /// that end with a call terminator, the effect of the call on the
732 /// dataflow state may depend on whether the call returned
733 /// successfully or unwound.
735 /// To reflect this, the `propagate_call_return` method of the
736 /// `BitDenotation` mutates `in_out` when propagating `in_out` via
737 /// a call terminator; such mutation is performed *last*, to
738 /// ensure its side-effects do not leak elsewhere (e.g., into
740 fn propagate_bits_into_graph_successors_of(
742 in_out: &mut BitSet<D::Idx>,
743 (bb, bb_data): (mir::BasicBlock, &mir::BasicBlockData<'tcx>),
744 dirty_list: &mut WorkQueue<mir::BasicBlock>)
746 match bb_data.terminator().kind {
747 mir::TerminatorKind::Return |
748 mir::TerminatorKind::Resume |
749 mir::TerminatorKind::Abort |
750 mir::TerminatorKind::GeneratorDrop |
751 mir::TerminatorKind::Unreachable => {}
752 mir::TerminatorKind::Goto { target } |
753 mir::TerminatorKind::Assert { target, cleanup: None, .. } |
754 mir::TerminatorKind::Yield { resume: target, drop: None, .. } |
755 mir::TerminatorKind::Drop { target, location: _, unwind: None } |
756 mir::TerminatorKind::DropAndReplace {
757 target, value: _, location: _, unwind: None
759 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
761 mir::TerminatorKind::Yield { resume: target, drop: Some(drop), .. } => {
762 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
763 self.propagate_bits_into_entry_set_for(in_out, drop, dirty_list);
765 mir::TerminatorKind::Assert { target, cleanup: Some(unwind), .. } |
766 mir::TerminatorKind::Drop { target, location: _, unwind: Some(unwind) } |
767 mir::TerminatorKind::DropAndReplace {
768 target, value: _, location: _, unwind: Some(unwind)
770 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
771 if !self.dead_unwinds.contains(bb) {
772 self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
775 mir::TerminatorKind::SwitchInt { ref targets, .. } => {
776 for target in targets {
777 self.propagate_bits_into_entry_set_for(in_out, *target, dirty_list);
780 mir::TerminatorKind::Call { cleanup, ref destination, .. } => {
781 if let Some(unwind) = cleanup {
782 if !self.dead_unwinds.contains(bb) {
783 self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
786 if let Some((ref dest_place, dest_bb)) = *destination {
787 // N.B.: This must be done *last*, after all other
788 // propagation, as documented in comment above.
789 self.flow_state.operator.propagate_call_return(
790 in_out, bb, dest_bb, dest_place);
791 self.propagate_bits_into_entry_set_for(in_out, dest_bb, dirty_list);
794 mir::TerminatorKind::FalseEdges { real_target, ref imaginary_targets } => {
795 self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
796 for target in imaginary_targets {
797 self.propagate_bits_into_entry_set_for(in_out, *target, dirty_list);
800 mir::TerminatorKind::FalseUnwind { real_target, unwind } => {
801 self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
802 if let Some(unwind) = unwind {
803 if !self.dead_unwinds.contains(bb) {
804 self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
811 fn propagate_bits_into_entry_set_for(&mut self,
812 in_out: &BitSet<D::Idx>,
814 dirty_queue: &mut WorkQueue<mir::BasicBlock>) {
815 let entry_set = &mut self.flow_state.sets.for_block(bb.index()).on_entry;
816 let set_changed = self.flow_state.operator.join(entry_set, &in_out);
818 dirty_queue.insert(bb);