src/librustc_mir/dataflow/mod.rs

   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.
   4 //
   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.
  10
  11 use syntax::ast::{self, MetaItem};
  12
  13 use rustc_data_structures::indexed_set::{IdxSet, IdxSetBuf};
  14 use rustc_data_structures::indexed_vec::Idx;
  15 use rustc_data_structures::bitslice::{bitwise, BitwiseOperator};
  16
  17 use rustc::ty::{self, TyCtxt};
  18 use rustc::mir::{self, Mir, BasicBlock, BasicBlockData, Location, Statement, Terminator};
  19 use rustc::session::Session;
  20
  21 use std::fmt::{self, Debug};
  22 use std::io;
  23 use std::mem;
  24 use std::path::PathBuf;
  25 use std::usize;
  26
  27 pub use self::impls::{MaybeStorageLive};
  28 pub use self::impls::{MaybeInitializedLvals, MaybeUninitializedLvals};
  29 pub use self::impls::{DefinitelyInitializedLvals};
  30 pub use self::impls::borrows::{Borrows, BorrowData, BorrowIndex};
  31 pub(crate) use self::drop_flag_effects::*;
  32
  33 use self::move_paths::MoveData;
  34
  35 mod drop_flag_effects;
  36 mod graphviz;
  37 mod impls;
  38 pub mod move_paths;
  39
  40 pub(crate) use self::move_paths::indexes;
  41
  42 pub(crate) struct DataflowBuilder<'a, 'tcx: 'a, BD> where BD: BitDenotation
  43 {
  44     node_id: ast::NodeId,
  45     flow_state: DataflowAnalysis<'a, 'tcx, BD>,
  46     print_preflow_to: Option<String>,
  47     print_postflow_to: Option<String>,
  48 }
  49
  50 pub trait Dataflow<BD: BitDenotation> {
  51     /// Sets up and runs the dataflow problem, using `p` to render results if
  52     /// implementation so chooses.
  53     fn dataflow<P>(&mut self, p: P) where P: Fn(&BD, BD::Idx) -> &Debug {
  54         let _ = p; // default implementation does not instrument process.
  55         self.build_sets();
  56         self.propagate();
  57     }
  58
  59     /// Sets up the entry, gen, and kill sets for this instance of a dataflow problem.
  60     fn build_sets(&mut self);
  61
  62     /// Finds a fixed-point solution to this instance of a dataflow problem.
  63     fn propagate(&mut self);
  64 }
  65
  66 impl<'a, 'tcx: 'a, BD> Dataflow<BD> for DataflowBuilder<'a, 'tcx, BD> where BD: BitDenotation
  67 {
  68     fn dataflow<P>(&mut self, p: P) where P: Fn(&BD, BD::Idx) -> &Debug {
  69         self.flow_state.build_sets();
  70         self.pre_dataflow_instrumentation(|c,i| p(c,i)).unwrap();
  71         self.flow_state.propagate();
  72         self.post_dataflow_instrumentation(|c,i| p(c,i)).unwrap();
  73     }
  74
  75     fn build_sets(&mut self) { self.flow_state.build_sets(); }
  76     fn propagate(&mut self) { self.flow_state.propagate(); }
  77 }
  78
  79 pub(crate) fn has_rustc_mir_with(attrs: &[ast::Attribute], name: &str) -> Option<MetaItem> {
  80     for attr in attrs {
  81         if attr.check_name("rustc_mir") {
  82             let items = attr.meta_item_list();
  83             for item in items.iter().flat_map(|l| l.iter()) {
  84                 match item.meta_item() {
  85                     Some(mi) if mi.check_name(name) => return Some(mi.clone()),
  86                     _ => continue
  87                 }
  88             }
  89         }
  90     }
  91     return None;
  92 }
  93
  94 pub struct MoveDataParamEnv<'tcx> {
  95     pub(crate) move_data: MoveData<'tcx>,
  96     pub(crate) param_env: ty::ParamEnv<'tcx>,
  97 }
  98
  99 pub(crate) fn do_dataflow<'a, 'tcx, BD, P>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 100                                 mir: &Mir<'tcx>,
 101                                 node_id: ast::NodeId,
 102                                 attributes: &[ast::Attribute],
 103                                 dead_unwinds: &IdxSet<BasicBlock>,
 104                                 bd: BD,
 105                                 p: P)
 106                                 -> DataflowResults<BD>
 107     where BD: BitDenotation,
 108           P: Fn(&BD, BD::Idx) -> &fmt::Debug
 109 {
 110     let name_found = |sess: &Session, attrs: &[ast::Attribute], name| -> Option<String> {
 111         if let Some(item) = has_rustc_mir_with(attrs, name) {
 112             if let Some(s) = item.value_str() {
 113                 return Some(s.to_string())
 114             } else {
 115                 sess.span_err(
 116                     item.span,
 117                     &format!("{} attribute requires a path", item.name()));
 118                 return None;
 119             }
 120         }
 121         return None;
 122     };
 123
 124     let print_preflow_to =
 125         name_found(tcx.sess, attributes, "borrowck_graphviz_preflow");
 126     let print_postflow_to =
 127         name_found(tcx.sess, attributes, "borrowck_graphviz_postflow");
 128
 129     let mut mbcx = DataflowBuilder {
 130         node_id,
 131         print_preflow_to,
 132         print_postflow_to,
 133         flow_state: DataflowAnalysis::new(tcx, mir, dead_unwinds, bd),
 134     };
 135
 136     mbcx.dataflow(p);
 137     mbcx.flow_state.results()
 138 }
 139
 140 struct PropagationContext<'b, 'a: 'b, 'tcx: 'a, O> where O: 'b + BitDenotation
 141 {
 142     builder: &'b mut DataflowAnalysis<'a, 'tcx, O>,
 143     changed: bool,
 144 }
 145
 146 impl<'a, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation
 147 {
 148     fn propagate(&mut self) {
 149         let mut temp = IdxSetBuf::new_empty(self.flow_state.sets.bits_per_block);
 150         let mut propcx = PropagationContext {
 151             builder: self,
 152             changed: true,
 153         };
 154         while propcx.changed {
 155             propcx.changed = false;
 156             propcx.reset(&mut temp);
 157             propcx.walk_cfg(&mut temp);
 158         }
 159     }
 160
 161     fn build_sets(&mut self) {
 162         // First we need to build the entry-, gen- and kill-sets. The
 163         // gather_moves information provides a high-level mapping from
 164         // mir-locations to the MoveOuts (and those correspond
 165         // directly to gen-sets here). But we still need to figure out
 166         // the kill-sets.
 167
 168         {
 169             let sets = &mut self.flow_state.sets.for_block(mir::START_BLOCK.index());
 170             self.flow_state.operator.start_block_effect(sets);
 171         }
 172
 173         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
 174             let &mir::BasicBlockData { ref statements, ref terminator, is_cleanup: _ } = data;
 175
 176             let sets = &mut self.flow_state.sets.for_block(bb.index());
 177             for j_stmt in 0..statements.len() {
 178                 let location = Location { block: bb, statement_index: j_stmt };
 179                 self.flow_state.operator.statement_effect(sets, location);
 180             }
 181
 182             if terminator.is_some() {
 183                 let location = Location { block: bb, statement_index: statements.len() };
 184                 self.flow_state.operator.terminator_effect(sets, location);
 185             }
 186         }
 187     }
 188 }
 189
 190 impl<'b, 'a: 'b, 'tcx: 'a, BD> PropagationContext<'b, 'a, 'tcx, BD> where BD: BitDenotation
 191 {
 192     fn reset(&mut self, bits: &mut IdxSet<BD::Idx>) {
 193         let e = if BD::bottom_value() {!0} else {0};
 194         for b in bits.words_mut() {
 195             *b = e;
 196         }
 197     }
 198
 199     fn walk_cfg(&mut self, in_out: &mut IdxSet<BD::Idx>) {
 200         let mir = self.builder.mir;
 201         for (bb_idx, bb_data) in mir.basic_blocks().iter().enumerate() {
 202             let builder = &mut self.builder;
 203             {
 204                 let sets = builder.flow_state.sets.for_block(bb_idx);
 205                 debug_assert!(in_out.words().len() == sets.on_entry.words().len());
 206                 in_out.clone_from(sets.on_entry);
 207                 in_out.union(sets.gen_set);
 208                 in_out.subtract(sets.kill_set);
 209             }
 210             builder.propagate_bits_into_graph_successors_of(
 211                 in_out, &mut self.changed, (mir::BasicBlock::new(bb_idx), bb_data));
 212         }
 213     }
 214 }
 215
 216 fn dataflow_path(context: &str, prepost: &str, path: &str) -> PathBuf {
 217     format!("{}_{}", context, prepost);
 218     let mut path = PathBuf::from(path);
 219     let new_file_name = {
 220         let orig_file_name = path.file_name().unwrap().to_str().unwrap();
 221         format!("{}_{}", context, orig_file_name)
 222     };
 223     path.set_file_name(new_file_name);
 224     path
 225 }
 226
 227 impl<'a, 'tcx: 'a, BD> DataflowBuilder<'a, 'tcx, BD> where BD: BitDenotation
 228 {
 229     fn pre_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
 230         where P: Fn(&BD, BD::Idx) -> &Debug
 231     {
 232         if let Some(ref path_str) = self.print_preflow_to {
 233             let path = dataflow_path(BD::name(), "preflow", path_str);
 234             graphviz::print_borrowck_graph_to(self, &path, p)
 235         } else {
 236             Ok(())
 237         }
 238     }
 239
 240     fn post_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
 241         where P: Fn(&BD, BD::Idx) -> &Debug
 242     {
 243         if let Some(ref path_str) = self.print_postflow_to {
 244             let path = dataflow_path(BD::name(), "postflow", path_str);
 245             graphviz::print_borrowck_graph_to(self, &path, p)
 246         } else{
 247             Ok(())
 248         }
 249     }
 250 }
 251
 252 /// Maps each block to a set of bits
 253 #[derive(Debug)]
 254 struct Bits<E:Idx> {
 255     bits: IdxSetBuf<E>,
 256 }
 257
 258 impl<E:Idx> Clone for Bits<E> {
 259     fn clone(&self) -> Self { Bits { bits: self.bits.clone() } }
 260 }
 261
 262 impl<E:Idx> Bits<E> {
 263     fn new(bits: IdxSetBuf<E>) -> Self {
 264         Bits { bits: bits }
 265     }
 266 }
 267
 268 /// DataflowResultsConsumer abstracts over walking the MIR with some
 269 /// already constructed dataflow results.
 270 ///
 271 /// It abstracts over the FlowState and also completely hides the
 272 /// underlying flow analysis results, because it needs to handle cases
 273 /// where we are combining the results of *multiple* flow analyses
 274 /// (e.g. borrows + inits + uninits).
 275 pub trait DataflowResultsConsumer<'a, 'tcx: 'a> {
 276     type FlowState;
 277
 278     // Observation Hooks: override (at least one of) these to get analysis feedback.
 279     fn visit_block_entry(&mut self,
 280                          _bb: BasicBlock,
 281                          _flow_state: &Self::FlowState) {}
 282
 283     fn visit_statement_entry(&mut self,
 284                              _loc: Location,
 285                              _stmt: &Statement<'tcx>,
 286                              _flow_state: &Self::FlowState) {}
 287
 288     fn visit_terminator_entry(&mut self,
 289                               _loc: Location,
 290                               _term: &Terminator<'tcx>,
 291                               _flow_state: &Self::FlowState) {}
 292
 293     // Main entry point: this drives the processing of results.
 294
 295     fn analyze_results(&mut self, flow_uninit: &mut Self::FlowState) {
 296         let flow = flow_uninit;
 297         for bb in self.mir().basic_blocks().indices() {
 298             self.reset_to_entry_of(bb, flow);
 299             self.process_basic_block(bb, flow);
 300         }
 301     }
 302
 303     fn process_basic_block(&mut self, bb: BasicBlock, flow_state: &mut Self::FlowState) {
 304         let BasicBlockData { ref statements, ref terminator, is_cleanup: _ } =
 305             self.mir()[bb];
 306         let mut location = Location { block: bb, statement_index: 0 };
 307         for stmt in statements.iter() {
 308             self.reconstruct_statement_effect(location, flow_state);
 309             self.visit_statement_entry(location, stmt, flow_state);
 310             self.apply_local_effect(location, flow_state);
 311             location.statement_index += 1;
 312         }
 313
 314         if let Some(ref term) = *terminator {
 315             self.reconstruct_terminator_effect(location, flow_state);
 316             self.visit_terminator_entry(location, term, flow_state);
 317
 318             // We don't need to apply the effect of the terminator,
 319             // since we are only visiting dataflow state on control
 320             // flow entry to the various nodes. (But we still need to
 321             // reconstruct the effect, because the visit method might
 322             // inspect it.)
 323         }
 324     }
 325
 326     // Delegated Hooks: Provide access to the MIR and process the flow state.
 327
 328     fn mir(&self) -> &'a Mir<'tcx>;
 329
 330     // reset the state bitvector to represent the entry to block `bb`.
 331     fn reset_to_entry_of(&mut self,
 332                          bb: BasicBlock,
 333                          flow_state: &mut Self::FlowState);
 334
 335     // build gen + kill sets for statement at `loc`.
 336     fn reconstruct_statement_effect(&mut self,
 337                                     loc: Location,
 338                                     flow_state: &mut Self::FlowState);
 339
 340     // build gen + kill sets for terminator for `loc`.
 341     fn reconstruct_terminator_effect(&mut self,
 342                                      loc: Location,
 343                                      flow_state: &mut Self::FlowState);
 344
 345     // apply current gen + kill sets to `flow_state`.
 346     //
 347     // (`bb` and `stmt_idx` parameters can be ignored if desired by
 348     // client. For the terminator, the `stmt_idx` will be the number
 349     // of statements in the block.)
 350     fn apply_local_effect(&mut self,
 351                           loc: Location,
 352                           flow_state: &mut Self::FlowState);
 353 }
 354
 355 pub fn state_for_location<T: BitDenotation>(loc: Location,
 356                                             analysis: &T,
 357                                             result: &DataflowResults<T>)
 358     -> IdxSetBuf<T::Idx> {
 359     let mut entry = result.sets().on_entry_set_for(loc.block.index()).to_owned();
 360
 361     {
 362         let mut sets = BlockSets {
 363             on_entry: &mut entry.clone(),
 364             kill_set: &mut entry.clone(),
 365             gen_set: &mut entry,
 366         };
 367
 368         for stmt in 0..loc.statement_index {
 369             let mut stmt_loc = loc;
 370             stmt_loc.statement_index = stmt;
 371             analysis.statement_effect(&mut sets, stmt_loc);
 372         }
 373     }
 374
 375     entry
 376 }
 377
 378 pub struct DataflowAnalysis<'a, 'tcx: 'a, O> where O: BitDenotation
 379 {
 380     flow_state: DataflowState<O>,
 381     dead_unwinds: &'a IdxSet<mir::BasicBlock>,
 382     mir: &'a Mir<'tcx>,
 383 }
 384
 385 impl<'a, 'tcx: 'a, O> DataflowAnalysis<'a, 'tcx, O> where O: BitDenotation
 386 {
 387     pub fn results(self) -> DataflowResults<O> {
 388         DataflowResults(self.flow_state)
 389     }
 390
 391     pub fn mir(&self) -> &'a Mir<'tcx> { self.mir }
 392 }
 393
 394 pub struct DataflowResults<O>(pub(crate) DataflowState<O>) where O: BitDenotation;
 395
 396 impl<O: BitDenotation> DataflowResults<O> {
 397     pub fn sets(&self) -> &AllSets<O::Idx> {
 398         &self.0.sets
 399     }
 400
 401     pub fn operator(&self) -> &O {
 402         &self.0.operator
 403     }
 404 }
 405
 406 /// State of a dataflow analysis; couples a collection of bit sets
 407 /// with operator used to initialize and merge bits during analysis.
 408 pub struct DataflowState<O: BitDenotation>
 409 {
 410     /// All the sets for the analysis. (Factored into its
 411     /// own structure so that we can borrow it mutably
 412     /// on its own separate from other fields.)
 413     pub sets: AllSets<O::Idx>,
 414
 415     /// operator used to initialize, combine, and interpret bits.
 416     pub(crate) operator: O,
 417 }
 418
 419 impl<O: BitDenotation> DataflowState<O> {
 420     pub fn each_bit<F>(&self, words: &IdxSet<O::Idx>, f: F) where F: FnMut(O::Idx)
 421     {
 422         let bits_per_block = self.operator.bits_per_block();
 423         words.each_bit(bits_per_block, f)
 424     }
 425
 426     pub fn interpret_set<'c, P>(&self,
 427                                 o: &'c O,
 428                                 words: &IdxSet<O::Idx>,
 429                                 render_idx: &P)
 430                                 -> Vec<&'c Debug>
 431         where P: Fn(&O, O::Idx) -> &Debug
 432     {
 433         let mut v = Vec::new();
 434         self.each_bit(words, |i| {
 435             v.push(render_idx(o, i));
 436         });
 437         v
 438     }
 439 }
 440
 441 #[derive(Debug)]
 442 pub struct AllSets<E: Idx> {
 443     /// Analysis bitwidth for each block.
 444     bits_per_block: usize,
 445
 446     /// Number of words associated with each block entry
 447     /// equal to bits_per_block / usize::BITS, rounded up.
 448     words_per_block: usize,
 449
 450     /// For each block, bits generated by executing the statements in
 451     /// the block. (For comparison, the Terminator for each block is
 452     /// handled in a flow-specific manner during propagation.)
 453     gen_sets: Bits<E>,
 454
 455     /// For each block, bits killed by executing the statements in the
 456     /// block. (For comparison, the Terminator for each block is
 457     /// handled in a flow-specific manner during propagation.)
 458     kill_sets: Bits<E>,
 459
 460     /// For each block, bits valid on entry to the block.
 461     on_entry_sets: Bits<E>,
 462 }
 463
 464 /// Triple of sets associated with a given block.
 465 ///
 466 /// Generally, one sets up `on_entry`, `gen_set`, and `kill_set` for
 467 /// each block individually, and then runs the dataflow analysis which
 468 /// iteratively modifies the various `on_entry` sets (but leaves the
 469 /// other two sets unchanged, since they represent the effect of the
 470 /// block, which should be invariant over the course of the analysis).
 471 ///
 472 /// It is best to ensure that the intersection of `gen_set` and
 473 /// `kill_set` is empty; otherwise the results of the dataflow will
 474 /// have a hidden dependency on what order the bits are generated and
 475 /// killed during the iteration. (This is such a good idea that the
 476 /// `fn gen` and `fn kill` methods that set their state enforce this
 477 /// for you.)
 478 pub struct BlockSets<'a, E: Idx> {
 479     /// Dataflow state immediately before control flow enters the given block.
 480     pub(crate) on_entry: &'a mut IdxSet<E>,
 481
 482     /// Bits that are set to 1 by the time we exit the given block.
 483     pub(crate) gen_set: &'a mut IdxSet<E>,
 484
 485     /// Bits that are set to 0 by the time we exit the given block.
 486     pub(crate) kill_set: &'a mut IdxSet<E>,
 487 }
 488
 489 impl<'a, E:Idx> BlockSets<'a, E> {
 490     fn gen(&mut self, e: &E) {
 491         self.gen_set.add(e);
 492         self.kill_set.remove(e);
 493     }
 494     fn kill(&mut self, e: &E) {
 495         self.gen_set.remove(e);
 496         self.kill_set.add(e);
 497     }
 498 }
 499
 500 impl<E:Idx> AllSets<E> {
 501     pub fn bits_per_block(&self) -> usize { self.bits_per_block }
 502     pub fn for_block(&mut self, block_idx: usize) -> BlockSets<E> {
 503         let offset = self.words_per_block * block_idx;
 504         let range = E::new(offset)..E::new(offset + self.words_per_block);
 505         BlockSets {
 506             on_entry: self.on_entry_sets.bits.range_mut(&range),
 507             gen_set: self.gen_sets.bits.range_mut(&range),
 508             kill_set: self.kill_sets.bits.range_mut(&range),
 509         }
 510     }
 511
 512     fn lookup_set_for<'a>(&self, sets: &'a Bits<E>, block_idx: usize) -> &'a IdxSet<E> {
 513         let offset = self.words_per_block * block_idx;
 514         let range = E::new(offset)..E::new(offset + self.words_per_block);
 515         sets.bits.range(&range)
 516     }
 517     pub fn gen_set_for(&self, block_idx: usize) -> &IdxSet<E> {
 518         self.lookup_set_for(&self.gen_sets, block_idx)
 519     }
 520     pub fn kill_set_for(&self, block_idx: usize) -> &IdxSet<E> {
 521         self.lookup_set_for(&self.kill_sets, block_idx)
 522     }
 523     pub fn on_entry_set_for(&self, block_idx: usize) -> &IdxSet<E> {
 524         self.lookup_set_for(&self.on_entry_sets, block_idx)
 525     }
 526 }
 527
 528 /// Parameterization for the precise form of data flow that is used.
 529 pub trait DataflowOperator: BitwiseOperator {
 530     /// Specifies the initial value for each bit in the `on_entry` set
 531     fn bottom_value() -> bool;
 532 }
 533
 534 pub trait BitDenotation: DataflowOperator {
 535     /// Specifies what index type is used to access the bitvector.
 536     type Idx: Idx;
 537
 538     /// A name describing the dataflow analysis that this
 539     /// BitDenotation is supporting.  The name should be something
 540     /// suitable for plugging in as part of a filename e.g. avoid
 541     /// space-characters or other things that tend to look bad on a
 542     /// file system, like slashes or periods. It is also better for
 543     /// the name to be reasonably short, again because it will be
 544     /// plugged into a filename.
 545     fn name() -> &'static str;
 546
 547     /// Size of each bitvector allocated for each block in the analysis.
 548     fn bits_per_block(&self) -> usize;
 549
 550     /// Mutates the block-sets (the flow sets for the given
 551     /// basic block) according to the effects that have been
 552     /// established *prior* to entering the start block.
 553     ///
 554     /// (For example, establishing the call arguments.)
 555     ///
 556     /// (Typically this should only modify `sets.on_entry`, since the
 557     /// gen and kill sets should reflect the effects of *executing*
 558     /// the start block itself.)
 559     fn start_block_effect(&self, sets: &mut BlockSets<Self::Idx>);
 560
 561     /// Mutates the block-sets (the flow sets for the given
 562     /// basic block) according to the effects of evaluating statement.
 563     ///
 564     /// This is used, in particular, for building up the
 565     /// "transfer-function" representing the overall-effect of the
 566     /// block, represented via GEN and KILL sets.
 567     ///
 568     /// The statement is identified as `bb_data[idx_stmt]`, where
 569     /// `bb_data` is the sequence of statements identified by `bb` in
 570     /// the MIR.
 571     fn statement_effect(&self,
 572                         sets: &mut BlockSets<Self::Idx>,
 573                         location: Location);
 574
 575     /// Mutates the block-sets (the flow sets for the given
 576     /// basic block) according to the effects of evaluating
 577     /// the terminator.
 578     ///
 579     /// This is used, in particular, for building up the
 580     /// "transfer-function" representing the overall-effect of the
 581     /// block, represented via GEN and KILL sets.
 582     ///
 583     /// The effects applied here cannot depend on which branch the
 584     /// terminator took.
 585     fn terminator_effect(&self,
 586                          sets: &mut BlockSets<Self::Idx>,
 587                          location: Location);
 588
 589     /// Mutates the block-sets according to the (flow-dependent)
 590     /// effect of a successful return from a Call terminator.
 591     ///
 592     /// If basic-block BB_x ends with a call-instruction that, upon
 593     /// successful return, flows to BB_y, then this method will be
 594     /// called on the exit flow-state of BB_x in order to set up the
 595     /// entry flow-state of BB_y.
 596     ///
 597     /// This is used, in particular, as a special case during the
 598     /// "propagate" loop where all of the basic blocks are repeatedly
 599     /// visited. Since the effects of a Call terminator are
 600     /// flow-dependent, the current MIR cannot encode them via just
 601     /// GEN and KILL sets attached to the block, and so instead we add
 602     /// this extra machinery to represent the flow-dependent effect.
 603     ///
 604     /// FIXME: Right now this is a bit of a wart in the API. It might
 605     /// be better to represent this as an additional gen- and
 606     /// kill-sets associated with each edge coming out of the basic
 607     /// block.
 608     fn propagate_call_return(&self,
 609                              in_out: &mut IdxSet<Self::Idx>,
 610                              call_bb: mir::BasicBlock,
 611                              dest_bb: mir::BasicBlock,
 612                              dest_lval: &mir::Lvalue);
 613 }
 614
 615 impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation
 616 {
 617     pub fn new(_tcx: TyCtxt<'a, 'tcx, 'tcx>,
 618                mir: &'a Mir<'tcx>,
 619                dead_unwinds: &'a IdxSet<mir::BasicBlock>,
 620                denotation: D) -> Self {
 621         let bits_per_block = denotation.bits_per_block();
 622         let usize_bits = mem::size_of::<usize>() * 8;
 623         let words_per_block = (bits_per_block + usize_bits - 1) / usize_bits;
 624
 625         // (now rounded up to multiple of word size)
 626         let bits_per_block = words_per_block * usize_bits;
 627
 628         let num_blocks = mir.basic_blocks().len();
 629         let num_overall = num_blocks * bits_per_block;
 630
 631         let zeroes = Bits::new(IdxSetBuf::new_empty(num_overall));
 632         let on_entry = Bits::new(if D::bottom_value() {
 633             IdxSetBuf::new_filled(num_overall)
 634         } else {
 635             IdxSetBuf::new_empty(num_overall)
 636         });
 637
 638         DataflowAnalysis {
 639             mir,
 640             dead_unwinds,
 641             flow_state: DataflowState {
 642                 sets: AllSets {
 643                     bits_per_block,
 644                     words_per_block,
 645                     gen_sets: zeroes.clone(),
 646                     kill_sets: zeroes,
 647                     on_entry_sets: on_entry,
 648                 },
 649                 operator: denotation,
 650             },
 651         }
 652
 653     }
 654 }
 655
 656 impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation
 657 {
 658     /// Propagates the bits of `in_out` into all the successors of `bb`,
 659     /// using bitwise operator denoted by `self.operator`.
 660     ///
 661     /// For most blocks, this is entirely uniform. However, for blocks
 662     /// that end with a call terminator, the effect of the call on the
 663     /// dataflow state may depend on whether the call returned
 664     /// successfully or unwound.
 665     ///
 666     /// To reflect this, the `propagate_call_return` method of the
 667     /// `BitDenotation` mutates `in_out` when propagating `in_out` via
 668     /// a call terminator; such mutation is performed *last*, to
 669     /// ensure its side-effects do not leak elsewhere (e.g. into
 670     /// unwind target).
 671     fn propagate_bits_into_graph_successors_of(
 672         &mut self,
 673         in_out: &mut IdxSet<D::Idx>,
 674         changed: &mut bool,
 675         (bb, bb_data): (mir::BasicBlock, &mir::BasicBlockData))
 676     {
 677         match bb_data.terminator().kind {
 678             mir::TerminatorKind::Return |
 679             mir::TerminatorKind::Resume |
 680             mir::TerminatorKind::GeneratorDrop |
 681             mir::TerminatorKind::Unreachable => {}
 682             mir::TerminatorKind::Goto { ref target } |
 683             mir::TerminatorKind::Assert { ref target, cleanup: None, .. } |
 684             mir::TerminatorKind::Yield { resume: ref target, drop: None, .. } |
 685             mir::TerminatorKind::Drop { ref target, location: _, unwind: None } |
 686             mir::TerminatorKind::DropAndReplace {
 687                 ref target, value: _, location: _, unwind: None
 688             } => {
 689                 self.propagate_bits_into_entry_set_for(in_out, changed, target);
 690             }
 691             mir::TerminatorKind::Yield { resume: ref target, drop: Some(ref drop), .. } => {
 692                 self.propagate_bits_into_entry_set_for(in_out, changed, target);
 693                 self.propagate_bits_into_entry_set_for(in_out, changed, drop);
 694             }
 695             mir::TerminatorKind::Assert { ref target, cleanup: Some(ref unwind), .. } |
 696             mir::TerminatorKind::Drop { ref target, location: _, unwind: Some(ref unwind) } |
 697             mir::TerminatorKind::DropAndReplace {
 698                 ref target, value: _, location: _, unwind: Some(ref unwind)
 699             } => {
 700                 self.propagate_bits_into_entry_set_for(in_out, changed, target);
 701                 if !self.dead_unwinds.contains(&bb) {
 702                     self.propagate_bits_into_entry_set_for(in_out, changed, unwind);
 703                 }
 704             }
 705             mir::TerminatorKind::SwitchInt { ref targets, .. } => {
 706                 for target in targets {
 707                     self.propagate_bits_into_entry_set_for(in_out, changed, target);
 708                 }
 709             }
 710             mir::TerminatorKind::Call { ref cleanup, ref destination, func: _, args: _ } => {
 711                 if let Some(ref unwind) = *cleanup {
 712                     if !self.dead_unwinds.contains(&bb) {
 713                         self.propagate_bits_into_entry_set_for(in_out, changed, unwind);
 714                     }
 715                 }
 716                 if let Some((ref dest_lval, ref dest_bb)) = *destination {
 717                     // N.B.: This must be done *last*, after all other
 718                     // propagation, as documented in comment above.
 719                     self.flow_state.operator.propagate_call_return(
 720                         in_out, bb, *dest_bb, dest_lval);
 721                     self.propagate_bits_into_entry_set_for(in_out, changed, dest_bb);
 722                 }
 723             }
 724         }
 725     }
 726
 727     fn propagate_bits_into_entry_set_for(&mut self,
 728                                          in_out: &IdxSet<D::Idx>,
 729                                          changed: &mut bool,
 730                                          bb: &mir::BasicBlock) {
 731         let entry_set = self.flow_state.sets.for_block(bb.index()).on_entry;
 732         let set_changed = bitwise(entry_set.words_mut(),
 733                                   in_out.words(),
 734                                   &self.flow_state.operator);
 735         if set_changed {
 736             *changed = true;
 737         }
 738     }
 739 }