src/librustc_mir/dataflow/mod.rs

   1 use rustc_span::symbol::{sym, Symbol};
   2 use syntax::ast::{self, MetaItem};
   3 use syntax::print::pprust;
   4
   5 use rustc_data_structures::work_queue::WorkQueue;
   6 use rustc_index::bit_set::{BitSet, HybridBitSet};
   7 use rustc_index::vec::Idx;
   8
   9 use rustc::mir::traversal;
  10 use rustc::mir::{self, BasicBlock, BasicBlockData, Body, Location, Statement, Terminator};
  11 use rustc::session::Session;
  12 use rustc::ty::{self, TyCtxt};
  13 use rustc_hir::def_id::DefId;
  14
  15 use std::borrow::Borrow;
  16 use std::fmt;
  17 use std::io;
  18 use std::path::PathBuf;
  19 use std::usize;
  20
  21 pub use self::at_location::{FlowAtLocation, FlowsAtLocation};
  22 pub(crate) use self::drop_flag_effects::*;
  23 pub use self::impls::borrows::Borrows;
  24 pub use self::impls::DefinitelyInitializedPlaces;
  25 pub use self::impls::EverInitializedPlaces;
  26 pub use self::impls::HaveBeenBorrowedLocals;
  27 pub use self::impls::IndirectlyMutableLocals;
  28 pub use self::impls::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
  29 pub use self::impls::{MaybeStorageLive, RequiresStorage};
  30
  31 use self::move_paths::MoveData;
  32
  33 mod at_location;
  34 pub mod drop_flag_effects;
  35 pub mod generic;
  36 mod graphviz;
  37 mod impls;
  38 pub mod move_paths;
  39
  40 pub(crate) mod indexes {
  41     pub(crate) use super::{
  42         impls::borrows::BorrowIndex,
  43         move_paths::{InitIndex, MoveOutIndex, MovePathIndex},
  44     };
  45 }
  46
  47 pub(crate) struct DataflowBuilder<'a, 'tcx, BD>
  48 where
  49     BD: BitDenotation<'tcx>,
  50 {
  51     def_id: DefId,
  52     flow_state: DataflowAnalysis<'a, 'tcx, BD>,
  53     print_preflow_to: Option<String>,
  54     print_postflow_to: Option<String>,
  55 }
  56
  57 /// `DebugFormatted` encapsulates the "{:?}" rendering of some
  58 /// arbitrary value. This way: you pay cost of allocating an extra
  59 /// string (as well as that of rendering up-front); in exchange, you
  60 /// don't have to hand over ownership of your value or deal with
  61 /// borrowing it.
  62 pub struct DebugFormatted(String);
  63
  64 impl DebugFormatted {
  65     pub fn new(input: &dyn fmt::Debug) -> DebugFormatted {
  66         DebugFormatted(format!("{:?}", input))
  67     }
  68 }
  69
  70 impl fmt::Debug for DebugFormatted {
  71     fn fmt(&self, w: &mut fmt::Formatter<'_>) -> fmt::Result {
  72         write!(w, "{}", self.0)
  73     }
  74 }
  75
  76 pub trait Dataflow<'tcx, BD: BitDenotation<'tcx>> {
  77     /// Sets up and runs the dataflow problem, using `p` to render results if
  78     /// implementation so chooses.
  79     fn dataflow<P>(&mut self, p: P)
  80     where
  81         P: Fn(&BD, BD::Idx) -> DebugFormatted,
  82     {
  83         let _ = p; // default implementation does not instrument process.
  84         self.build_sets();
  85         self.propagate();
  86     }
  87
  88     /// Sets up the entry, gen, and kill sets for this instance of a dataflow problem.
  89     fn build_sets(&mut self);
  90
  91     /// Finds a fixed-point solution to this instance of a dataflow problem.
  92     fn propagate(&mut self);
  93 }
  94
  95 impl<'a, 'tcx, BD> Dataflow<'tcx, BD> for DataflowBuilder<'a, 'tcx, BD>
  96 where
  97     BD: BitDenotation<'tcx>,
  98 {
  99     fn dataflow<P>(&mut self, p: P)
 100     where
 101         P: Fn(&BD, BD::Idx) -> DebugFormatted,
 102     {
 103         self.flow_state.build_sets();
 104         self.pre_dataflow_instrumentation(|c, i| p(c, i)).unwrap();
 105         self.flow_state.propagate();
 106         self.post_dataflow_instrumentation(|c, i| p(c, i)).unwrap();
 107     }
 108
 109     fn build_sets(&mut self) {
 110         self.flow_state.build_sets();
 111     }
 112     fn propagate(&mut self) {
 113         self.flow_state.propagate();
 114     }
 115 }
 116
 117 pub(crate) fn has_rustc_mir_with(attrs: &[ast::Attribute], name: Symbol) -> Option<MetaItem> {
 118     for attr in attrs {
 119         if attr.check_name(sym::rustc_mir) {
 120             let items = attr.meta_item_list();
 121             for item in items.iter().flat_map(|l| l.iter()) {
 122                 match item.meta_item() {
 123                     Some(mi) if mi.check_name(name) => return Some(mi.clone()),
 124                     _ => continue,
 125                 }
 126             }
 127         }
 128     }
 129     return None;
 130 }
 131
 132 pub struct MoveDataParamEnv<'tcx> {
 133     pub(crate) move_data: MoveData<'tcx>,
 134     pub(crate) param_env: ty::ParamEnv<'tcx>,
 135 }
 136
 137 pub fn do_dataflow<'a, 'tcx, BD, P>(
 138     tcx: TyCtxt<'tcx>,
 139     body: &'a Body<'tcx>,
 140     def_id: DefId,
 141     attributes: &[ast::Attribute],
 142     dead_unwinds: &BitSet<BasicBlock>,
 143     bd: BD,
 144     p: P,
 145 ) -> DataflowResults<'tcx, BD>
 146 where
 147     BD: BitDenotation<'tcx>,
 148     P: Fn(&BD, BD::Idx) -> DebugFormatted,
 149 {
 150     let flow_state = DataflowAnalysis::new(body, dead_unwinds, bd);
 151     flow_state.run(tcx, def_id, attributes, p)
 152 }
 153
 154 impl<'a, 'tcx, BD> DataflowAnalysis<'a, 'tcx, BD>
 155 where
 156     BD: BitDenotation<'tcx>,
 157 {
 158     pub(crate) fn run<P>(
 159         self,
 160         tcx: TyCtxt<'tcx>,
 161         def_id: DefId,
 162         attributes: &[ast::Attribute],
 163         p: P,
 164     ) -> DataflowResults<'tcx, BD>
 165     where
 166         P: Fn(&BD, BD::Idx) -> DebugFormatted,
 167     {
 168         let name_found = |sess: &Session, attrs: &[ast::Attribute], name| -> Option<String> {
 169             if let Some(item) = has_rustc_mir_with(attrs, name) {
 170                 if let Some(s) = item.value_str() {
 171                     return Some(s.to_string());
 172                 } else {
 173                     let path = pprust::path_to_string(&item.path);
 174                     sess.span_err(item.span, &format!("{} attribute requires a path", path));
 175                     return None;
 176                 }
 177             }
 178             return None;
 179         };
 180
 181         let print_preflow_to = name_found(tcx.sess, attributes, sym::borrowck_graphviz_preflow);
 182         let print_postflow_to = name_found(tcx.sess, attributes, sym::borrowck_graphviz_postflow);
 183
 184         let mut mbcx =
 185             DataflowBuilder { def_id, print_preflow_to, print_postflow_to, flow_state: self };
 186
 187         mbcx.dataflow(p);
 188         mbcx.flow_state.results()
 189     }
 190 }
 191
 192 struct PropagationContext<'b, 'a, 'tcx, O>
 193 where
 194     O: BitDenotation<'tcx>,
 195 {
 196     builder: &'b mut DataflowAnalysis<'a, 'tcx, O>,
 197 }
 198
 199 impl<'a, 'tcx, BD> DataflowAnalysis<'a, 'tcx, BD>
 200 where
 201     BD: BitDenotation<'tcx>,
 202 {
 203     fn propagate(&mut self) {
 204         let mut temp = BitSet::new_empty(self.flow_state.sets.bits_per_block);
 205         let mut propcx = PropagationContext { builder: self };
 206         propcx.walk_cfg(&mut temp);
 207     }
 208
 209     fn build_sets(&mut self) {
 210         // Build the transfer function for each block.
 211         for (bb, data) in self.body.basic_blocks().iter_enumerated() {
 212             let &mir::BasicBlockData { ref statements, ref terminator, is_cleanup: _ } = data;
 213
 214             let trans = self.flow_state.sets.trans_mut_for(bb.index());
 215             for j_stmt in 0..statements.len() {
 216                 let location = Location { block: bb, statement_index: j_stmt };
 217                 self.flow_state.operator.before_statement_effect(trans, location);
 218                 self.flow_state.operator.statement_effect(trans, location);
 219             }
 220
 221             if terminator.is_some() {
 222                 let location = Location { block: bb, statement_index: statements.len() };
 223                 self.flow_state.operator.before_terminator_effect(trans, location);
 224                 self.flow_state.operator.terminator_effect(trans, location);
 225             }
 226         }
 227
 228         // Initialize the flow state at entry to the start block.
 229         let on_entry = self.flow_state.sets.entry_set_mut_for(mir::START_BLOCK.index());
 230         self.flow_state.operator.start_block_effect(on_entry);
 231     }
 232 }
 233
 234 impl<'b, 'a, 'tcx, BD> PropagationContext<'b, 'a, 'tcx, BD>
 235 where
 236     BD: BitDenotation<'tcx>,
 237 {
 238     fn walk_cfg(&mut self, in_out: &mut BitSet<BD::Idx>) {
 239         let body = self.builder.body;
 240
 241         // Initialize the dirty queue in reverse post-order. This makes it more likely that the
 242         // entry state for each basic block will have the effects of its predecessors applied
 243         // before it is processed. In fact, for CFGs without back edges, this guarantees that
 244         // dataflow will converge in exactly `N` iterations, where `N` is the number of basic
 245         // blocks.
 246         let mut dirty_queue: WorkQueue<mir::BasicBlock> =
 247             WorkQueue::with_none(body.basic_blocks().len());
 248         for (bb, _) in traversal::reverse_postorder(body) {
 249             dirty_queue.insert(bb);
 250         }
 251
 252         // Add blocks which are not reachable from START_BLOCK to the work queue. These blocks will
 253         // be processed after the ones added above.
 254         for bb in body.basic_blocks().indices() {
 255             dirty_queue.insert(bb);
 256         }
 257
 258         while let Some(bb) = dirty_queue.pop() {
 259             let (on_entry, trans) = self.builder.flow_state.sets.get_mut(bb.index());
 260             debug_assert!(in_out.words().len() == on_entry.words().len());
 261             in_out.overwrite(on_entry);
 262             trans.apply(in_out);
 263
 264             let bb_data = &body[bb];
 265             self.builder.propagate_bits_into_graph_successors_of(
 266                 in_out,
 267                 (bb, bb_data),
 268                 &mut dirty_queue,
 269             );
 270         }
 271     }
 272 }
 273
 274 fn dataflow_path(context: &str, path: &str) -> PathBuf {
 275     let mut path = PathBuf::from(path);
 276     let new_file_name = {
 277         let orig_file_name = path.file_name().unwrap().to_str().unwrap();
 278         format!("{}_{}", context, orig_file_name)
 279     };
 280     path.set_file_name(new_file_name);
 281     path
 282 }
 283
 284 impl<'a, 'tcx, BD> DataflowBuilder<'a, 'tcx, BD>
 285 where
 286     BD: BitDenotation<'tcx>,
 287 {
 288     fn pre_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
 289     where
 290         P: Fn(&BD, BD::Idx) -> DebugFormatted,
 291     {
 292         if let Some(ref path_str) = self.print_preflow_to {
 293             let path = dataflow_path(BD::name(), path_str);
 294             graphviz::print_borrowck_graph_to(self, &path, p)
 295         } else {
 296             Ok(())
 297         }
 298     }
 299
 300     fn post_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
 301     where
 302         P: Fn(&BD, BD::Idx) -> DebugFormatted,
 303     {
 304         if let Some(ref path_str) = self.print_postflow_to {
 305             let path = dataflow_path(BD::name(), path_str);
 306             graphviz::print_borrowck_graph_to(self, &path, p)
 307         } else {
 308             Ok(())
 309         }
 310     }
 311 }
 312
 313 /// DataflowResultsConsumer abstracts over walking the MIR with some
 314 /// already constructed dataflow results.
 315 ///
 316 /// It abstracts over the FlowState and also completely hides the
 317 /// underlying flow analysis results, because it needs to handle cases
 318 /// where we are combining the results of *multiple* flow analyses
 319 /// (e.g., borrows + inits + uninits).
 320 pub(crate) trait DataflowResultsConsumer<'a, 'tcx: 'a> {
 321     type FlowState: FlowsAtLocation;
 322
 323     // Observation Hooks: override (at least one of) these to get analysis feedback.
 324     fn visit_block_entry(&mut self, _bb: BasicBlock, _flow_state: &Self::FlowState) {}
 325
 326     fn visit_statement_entry(
 327         &mut self,
 328         _loc: Location,
 329         _stmt: &'a Statement<'tcx>,
 330         _flow_state: &Self::FlowState,
 331     ) {
 332     }
 333
 334     fn visit_terminator_entry(
 335         &mut self,
 336         _loc: Location,
 337         _term: &'a Terminator<'tcx>,
 338         _flow_state: &Self::FlowState,
 339     ) {
 340     }
 341
 342     // Main entry point: this drives the processing of results.
 343
 344     fn analyze_results(&mut self, flow_uninit: &mut Self::FlowState) {
 345         let flow = flow_uninit;
 346         for (bb, _) in traversal::reverse_postorder(self.body()) {
 347             flow.reset_to_entry_of(bb);
 348             self.process_basic_block(bb, flow);
 349         }
 350     }
 351
 352     fn process_basic_block(&mut self, bb: BasicBlock, flow_state: &mut Self::FlowState) {
 353         self.visit_block_entry(bb, flow_state);
 354
 355         let BasicBlockData { ref statements, ref terminator, is_cleanup: _ } = self.body()[bb];
 356         let mut location = Location { block: bb, statement_index: 0 };
 357         for stmt in statements.iter() {
 358             flow_state.reconstruct_statement_effect(location);
 359             self.visit_statement_entry(location, stmt, flow_state);
 360             flow_state.apply_local_effect(location);
 361             location.statement_index += 1;
 362         }
 363
 364         if let Some(ref term) = *terminator {
 365             flow_state.reconstruct_terminator_effect(location);
 366             self.visit_terminator_entry(location, term, flow_state);
 367
 368             // We don't need to apply the effect of the terminator,
 369             // since we are only visiting dataflow state on control
 370             // flow entry to the various nodes. (But we still need to
 371             // reconstruct the effect, because the visit method might
 372             // inspect it.)
 373         }
 374     }
 375
 376     // Delegated Hooks: Provide access to the MIR and process the flow state.
 377
 378     fn body(&self) -> &'a Body<'tcx>;
 379 }
 380
 381 /// Allows iterating dataflow results in a flexible and reasonably fast way.
 382 pub struct DataflowResultsCursor<'mir, 'tcx, BD, DR = DataflowResults<'tcx, BD>>
 383 where
 384     BD: BitDenotation<'tcx>,
 385     DR: Borrow<DataflowResults<'tcx, BD>>,
 386 {
 387     flow_state: FlowAtLocation<'tcx, BD, DR>,
 388
 389     // The statement (or terminator) whose effect has been reconstructed in
 390     // flow_state.
 391     curr_loc: Option<Location>,
 392
 393     body: &'mir Body<'tcx>,
 394 }
 395
 396 pub type DataflowResultsRefCursor<'mir, 'tcx, BD> =
 397     DataflowResultsCursor<'mir, 'tcx, BD, &'mir DataflowResults<'tcx, BD>>;
 398
 399 impl<'mir, 'tcx, BD, DR> DataflowResultsCursor<'mir, 'tcx, BD, DR>
 400 where
 401     BD: BitDenotation<'tcx>,
 402     DR: Borrow<DataflowResults<'tcx, BD>>,
 403 {
 404     pub fn new(result: DR, body: &'mir Body<'tcx>) -> Self {
 405         DataflowResultsCursor { flow_state: FlowAtLocation::new(result), curr_loc: None, body }
 406     }
 407
 408     /// Seek to the given location in MIR. This method is fast if you are
 409     /// traversing your MIR statements in order.
 410     ///
 411     /// After calling `seek`, the current state will reflect all effects up to
 412     /// and including the `before_statement_effect` of the statement at location
 413     /// `loc`. The `statement_effect` of the statement at `loc` will be
 414     /// available as the current effect (see e.g. `each_gen_bit`).
 415     ///
 416     /// If `loc.statement_index` equals the number of statements in the block,
 417     /// we will reconstruct the terminator effect in the same way as described
 418     /// above.
 419     pub fn seek(&mut self, loc: Location) {
 420         if self.curr_loc.map(|cur| loc == cur).unwrap_or(false) {
 421             return;
 422         }
 423
 424         let start_index;
 425         let should_reset = match self.curr_loc {
 426             None => true,
 427             Some(cur) if loc.block != cur.block || loc.statement_index < cur.statement_index => {
 428                 true
 429             }
 430             _ => false,
 431         };
 432         if should_reset {
 433             self.flow_state.reset_to_entry_of(loc.block);
 434             start_index = 0;
 435         } else {
 436             let curr_loc = self.curr_loc.unwrap();
 437             start_index = curr_loc.statement_index;
 438             // Apply the effect from the last seek to the current state.
 439             self.flow_state.apply_local_effect(curr_loc);
 440         }
 441
 442         for stmt in start_index..loc.statement_index {
 443             let mut stmt_loc = loc;
 444             stmt_loc.statement_index = stmt;
 445             self.flow_state.reconstruct_statement_effect(stmt_loc);
 446             self.flow_state.apply_local_effect(stmt_loc);
 447         }
 448
 449         if loc.statement_index == self.body[loc.block].statements.len() {
 450             self.flow_state.reconstruct_terminator_effect(loc);
 451         } else {
 452             self.flow_state.reconstruct_statement_effect(loc);
 453         }
 454         self.curr_loc = Some(loc);
 455     }
 456
 457     /// Return whether the current state contains bit `x`.
 458     pub fn contains(&self, x: BD::Idx) -> bool {
 459         self.flow_state.contains(x)
 460     }
 461
 462     /// Iterate over each `gen` bit in the current effect (invoke `seek` first).
 463     pub fn each_gen_bit<F>(&self, f: F)
 464     where
 465         F: FnMut(BD::Idx),
 466     {
 467         self.flow_state.each_gen_bit(f)
 468     }
 469
 470     pub fn get(&self) -> &BitSet<BD::Idx> {
 471         self.flow_state.as_dense()
 472     }
 473 }
 474
 475 pub struct DataflowAnalysis<'a, 'tcx, O>
 476 where
 477     O: BitDenotation<'tcx>,
 478 {
 479     flow_state: DataflowState<'tcx, O>,
 480     dead_unwinds: &'a BitSet<mir::BasicBlock>,
 481     body: &'a Body<'tcx>,
 482 }
 483
 484 impl<'a, 'tcx, O> DataflowAnalysis<'a, 'tcx, O>
 485 where
 486     O: BitDenotation<'tcx>,
 487 {
 488     pub fn results(self) -> DataflowResults<'tcx, O> {
 489         DataflowResults(self.flow_state)
 490     }
 491
 492     pub fn body(&self) -> &'a Body<'tcx> {
 493         self.body
 494     }
 495 }
 496
 497 pub struct DataflowResults<'tcx, O>(pub(crate) DataflowState<'tcx, O>)
 498 where
 499     O: BitDenotation<'tcx>;
 500
 501 impl<'tcx, O: BitDenotation<'tcx>> DataflowResults<'tcx, O> {
 502     pub fn sets(&self) -> &AllSets<O::Idx> {
 503         &self.0.sets
 504     }
 505
 506     pub fn operator(&self) -> &O {
 507         &self.0.operator
 508     }
 509 }
 510
 511 /// State of a dataflow analysis; couples a collection of bit sets
 512 /// with operator used to initialize and merge bits during analysis.
 513 pub struct DataflowState<'tcx, O: BitDenotation<'tcx>> {
 514     /// All the sets for the analysis. (Factored into its
 515     /// own structure so that we can borrow it mutably
 516     /// on its own separate from other fields.)
 517     pub sets: AllSets<O::Idx>,
 518
 519     /// operator used to initialize, combine, and interpret bits.
 520     pub(crate) operator: O,
 521 }
 522
 523 impl<'tcx, O: BitDenotation<'tcx>> DataflowState<'tcx, O> {
 524     pub(crate) fn interpret_set<'c, P>(
 525         &self,
 526         o: &'c O,
 527         set: &BitSet<O::Idx>,
 528         render_idx: &P,
 529     ) -> Vec<DebugFormatted>
 530     where
 531         P: Fn(&O, O::Idx) -> DebugFormatted,
 532     {
 533         set.iter().map(|i| render_idx(o, i)).collect()
 534     }
 535
 536     pub(crate) fn interpret_hybrid_set<'c, P>(
 537         &self,
 538         o: &'c O,
 539         set: &HybridBitSet<O::Idx>,
 540         render_idx: &P,
 541     ) -> Vec<DebugFormatted>
 542     where
 543         P: Fn(&O, O::Idx) -> DebugFormatted,
 544     {
 545         set.iter().map(|i| render_idx(o, i)).collect()
 546     }
 547 }
 548
 549 /// A 2-tuple representing the "gen" and "kill" bitsets during
 550 /// dataflow analysis.
 551 ///
 552 /// It is best to ensure that the intersection of `gen_set` and
 553 /// `kill_set` is empty; otherwise the results of the dataflow will
 554 /// have a hidden dependency on what order the bits are generated and
 555 /// killed during the iteration. (This is such a good idea that the
 556 /// `fn gen` and `fn kill` methods that set their state enforce this
 557 /// for you.)
 558 #[derive(Debug, Clone, Copy)]
 559 pub struct GenKill<T> {
 560     pub(crate) gen_set: T,
 561     pub(crate) kill_set: T,
 562 }
 563
 564 pub type GenKillSet<T> = GenKill<HybridBitSet<T>>;
 565
 566 impl<T> GenKill<T> {
 567     /// Creates a new tuple where `gen_set == kill_set == elem`.
 568     pub(crate) fn from_elem(elem: T) -> Self
 569     where
 570         T: Clone,
 571     {
 572         GenKill { gen_set: elem.clone(), kill_set: elem }
 573     }
 574 }
 575
 576 impl<E: Idx> GenKillSet<E> {
 577     pub fn clear(&mut self) {
 578         self.gen_set.clear();
 579         self.kill_set.clear();
 580     }
 581
 582     pub fn gen(&mut self, e: E) {
 583         self.gen_set.insert(e);
 584         self.kill_set.remove(e);
 585     }
 586
 587     pub fn gen_all(&mut self, i: impl IntoIterator<Item: Borrow<E>>) {
 588         for j in i {
 589             self.gen(*j.borrow());
 590         }
 591     }
 592
 593     pub fn kill(&mut self, e: E) {
 594         self.gen_set.remove(e);
 595         self.kill_set.insert(e);
 596     }
 597
 598     pub fn kill_all(&mut self, i: impl IntoIterator<Item: Borrow<E>>) {
 599         for j in i {
 600             self.kill(*j.borrow());
 601         }
 602     }
 603
 604     /// Computes `(set ∪ gen) - kill` and assigns the result to `set`.
 605     pub(crate) fn apply(&self, set: &mut BitSet<E>) {
 606         set.union(&self.gen_set);
 607         set.subtract(&self.kill_set);
 608     }
 609 }
 610
 611 #[derive(Debug)]
 612 pub struct AllSets<E: Idx> {
 613     /// Analysis bitwidth for each block.
 614     bits_per_block: usize,
 615
 616     /// For each block, bits valid on entry to the block.
 617     on_entry: Vec<BitSet<E>>,
 618
 619     /// The transfer function of each block expressed as the set of bits
 620     /// generated and killed by executing the statements + terminator in the
 621     /// block -- with one caveat. In particular, for *call terminators*, the
 622     /// effect of storing the destination is not included, since that only takes
 623     /// effect on the **success** edge (and not the unwind edge).
 624     trans: Vec<GenKillSet<E>>,
 625 }
 626
 627 impl<E: Idx> AllSets<E> {
 628     pub fn bits_per_block(&self) -> usize {
 629         self.bits_per_block
 630     }
 631
 632     pub fn get_mut(&mut self, block_idx: usize) -> (&mut BitSet<E>, &mut GenKillSet<E>) {
 633         (&mut self.on_entry[block_idx], &mut self.trans[block_idx])
 634     }
 635
 636     pub fn trans_for(&self, block_idx: usize) -> &GenKillSet<E> {
 637         &self.trans[block_idx]
 638     }
 639     pub fn trans_mut_for(&mut self, block_idx: usize) -> &mut GenKillSet<E> {
 640         &mut self.trans[block_idx]
 641     }
 642     pub fn entry_set_for(&self, block_idx: usize) -> &BitSet<E> {
 643         &self.on_entry[block_idx]
 644     }
 645     pub fn entry_set_mut_for(&mut self, block_idx: usize) -> &mut BitSet<E> {
 646         &mut self.on_entry[block_idx]
 647     }
 648     pub fn gen_set_for(&self, block_idx: usize) -> &HybridBitSet<E> {
 649         &self.trans_for(block_idx).gen_set
 650     }
 651     pub fn kill_set_for(&self, block_idx: usize) -> &HybridBitSet<E> {
 652         &self.trans_for(block_idx).kill_set
 653     }
 654 }
 655
 656 /// Parameterization for the precise form of data flow that is used.
 657 ///
 658 /// `BottomValue` determines whether the initial entry set for each basic block is empty or full.
 659 /// This also determines the semantics of the lattice `join` operator used to merge dataflow
 660 /// results, since dataflow works by starting at the bottom and moving monotonically to a fixed
 661 /// point.
 662 ///
 663 /// This means, for propagation across the graph, that you either want to start at all-zeroes and
 664 /// then use Union as your merge when propagating, or you start at all-ones and then use Intersect
 665 /// as your merge when propagating.
 666 pub trait BottomValue {
 667     /// Specifies the initial value for each bit in the entry set for each basic block.
 668     const BOTTOM_VALUE: bool;
 669
 670     /// Merges `in_set` into `inout_set`, returning `true` if `inout_set` changed.
 671     ///
 672     /// It is almost certainly wrong to override this, since it automatically applies
 673     /// * `inout_set & in_set` if `BOTTOM_VALUE == true`
 674     /// * `inout_set | in_set` if `BOTTOM_VALUE == false`
 675     ///
 676     /// This means that if a bit is not `BOTTOM_VALUE`, it is propagated into all target blocks.
 677     /// For clarity, the above statement again from a different perspective:
 678     /// A bit in the block's entry set is `!BOTTOM_VALUE` if *any* predecessor block's bit value is
 679     /// `!BOTTOM_VALUE`.
 680     ///
 681     /// There are situations where you want the opposite behaviour: propagate only if *all*
 682     /// predecessor blocks's value is `!BOTTOM_VALUE`.
 683     /// E.g. if you want to know whether a bit is *definitely* set at a specific location. This
 684     /// means that all code paths leading to the location must have set the bit, instead of any
 685     /// code path leading there.
 686     ///
 687     /// If you want this kind of "definitely set" analysis, you need to
 688     /// 1. Invert `BOTTOM_VALUE`
 689     /// 2. Reset the `entry_set` in `start_block_effect` to `!BOTTOM_VALUE`
 690     /// 3. Override `join` to do the opposite from what it's doing now.
 691     #[inline]
 692     fn join<T: Idx>(&self, inout_set: &mut BitSet<T>, in_set: &BitSet<T>) -> bool {
 693         if Self::BOTTOM_VALUE == false {
 694             inout_set.union(in_set)
 695         } else {
 696             inout_set.intersect(in_set)
 697         }
 698     }
 699 }
 700
 701 /// A specific flavor of dataflow analysis.
 702 ///
 703 /// To run a dataflow analysis, one sets up an initial state for the
 704 /// `START_BLOCK` via `start_block_effect` and a transfer function (`trans`)
 705 /// for each block individually. The entry set for all other basic blocks is
 706 /// initialized to `Self::BOTTOM_VALUE`. The dataflow analysis then
 707 /// iteratively modifies the various entry sets (but leaves the the transfer
 708 /// function unchanged). `BottomValue::join` is used to merge the bitsets from
 709 /// two blocks (e.g. when two blocks' terminator jumps to a single block, that
 710 /// target block's state is the merged state of both incoming blocks).
 711 pub trait BitDenotation<'tcx>: BottomValue {
 712     /// Specifies what index type is used to access the bitvector.
 713     type Idx: Idx;
 714
 715     /// A name describing the dataflow analysis that this
 716     /// `BitDenotation` is supporting. The name should be something
 717     /// suitable for plugging in as part of a filename (i.e., avoid
 718     /// space-characters or other things that tend to look bad on a
 719     /// file system, like slashes or periods). It is also better for
 720     /// the name to be reasonably short, again because it will be
 721     /// plugged into a filename.
 722     fn name() -> &'static str;
 723
 724     /// Size of each bitvector allocated for each block in the analysis.
 725     fn bits_per_block(&self) -> usize;
 726
 727     /// Mutates the entry set according to the effects that
 728     /// have been established *prior* to entering the start
 729     /// block. This can't access the gen/kill sets, because
 730     /// these won't be accounted for correctly.
 731     ///
 732     /// (For example, establishing the call arguments.)
 733     fn start_block_effect(&self, entry_set: &mut BitSet<Self::Idx>);
 734
 735     /// Similar to `statement_effect`, except it applies
 736     /// *just before* the statement rather than *just after* it.
 737     ///
 738     /// This matters for "dataflow at location" APIs, because the
 739     /// before-statement effect is visible while visiting the
 740     /// statement, while the after-statement effect only becomes
 741     /// visible at the next statement.
 742     ///
 743     /// Both the before-statement and after-statement effects are
 744     /// applied, in that order, before moving for the next
 745     /// statement.
 746     fn before_statement_effect(&self, _trans: &mut GenKillSet<Self::Idx>, _location: Location) {}
 747
 748     /// Mutates the block-sets (the flow sets for the given
 749     /// basic block) according to the effects of evaluating statement.
 750     ///
 751     /// This is used, in particular, for building up the
 752     /// "transfer-function" representing the overall-effect of the
 753     /// block, represented via GEN and KILL sets.
 754     ///
 755     /// The statement is identified as `bb_data[idx_stmt]`, where
 756     /// `bb_data` is the sequence of statements identified by `bb` in
 757     /// the MIR.
 758     fn statement_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location);
 759
 760     /// Similar to `terminator_effect`, except it applies
 761     /// *just before* the terminator rather than *just after* it.
 762     ///
 763     /// This matters for "dataflow at location" APIs, because the
 764     /// before-terminator effect is visible while visiting the
 765     /// terminator, while the after-terminator effect only becomes
 766     /// visible at the terminator's successors.
 767     ///
 768     /// Both the before-terminator and after-terminator effects are
 769     /// applied, in that order, before moving for the next
 770     /// terminator.
 771     fn before_terminator_effect(&self, _trans: &mut GenKillSet<Self::Idx>, _location: Location) {}
 772
 773     /// Mutates the block-sets (the flow sets for the given
 774     /// basic block) according to the effects of evaluating
 775     /// the terminator.
 776     ///
 777     /// This is used, in particular, for building up the
 778     /// "transfer-function" representing the overall-effect of the
 779     /// block, represented via GEN and KILL sets.
 780     ///
 781     /// The effects applied here cannot depend on which branch the
 782     /// terminator took.
 783     fn terminator_effect(&self, trans: &mut GenKillSet<Self::Idx>, location: Location);
 784
 785     /// Mutates the block-sets according to the (flow-dependent)
 786     /// effect of a successful return from a Call terminator.
 787     ///
 788     /// If basic-block BB_x ends with a call-instruction that, upon
 789     /// successful return, flows to BB_y, then this method will be
 790     /// called on the exit flow-state of BB_x in order to set up the
 791     /// entry flow-state of BB_y.
 792     ///
 793     /// This is used, in particular, as a special case during the
 794     /// "propagate" loop where all of the basic blocks are repeatedly
 795     /// visited. Since the effects of a Call terminator are
 796     /// flow-dependent, the current MIR cannot encode them via just
 797     /// GEN and KILL sets attached to the block, and so instead we add
 798     /// this extra machinery to represent the flow-dependent effect.
 799     //
 800     // FIXME: right now this is a bit of a wart in the API. It might
 801     // be better to represent this as an additional gen- and
 802     // kill-sets associated with each edge coming out of the basic
 803     // block.
 804     fn propagate_call_return(
 805         &self,
 806         in_out: &mut BitSet<Self::Idx>,
 807         call_bb: mir::BasicBlock,
 808         dest_bb: mir::BasicBlock,
 809         dest_place: &mir::Place<'tcx>,
 810     );
 811 }
 812
 813 impl<'a, 'tcx, D> DataflowAnalysis<'a, 'tcx, D>
 814 where
 815     D: BitDenotation<'tcx>,
 816 {
 817     pub fn new(
 818         body: &'a Body<'tcx>,
 819         dead_unwinds: &'a BitSet<mir::BasicBlock>,
 820         denotation: D,
 821     ) -> Self {
 822         let bits_per_block = denotation.bits_per_block();
 823         let num_blocks = body.basic_blocks().len();
 824
 825         let on_entry = if D::BOTTOM_VALUE == true {
 826             vec![BitSet::new_filled(bits_per_block); num_blocks]
 827         } else {
 828             vec![BitSet::new_empty(bits_per_block); num_blocks]
 829         };
 830         let nop = GenKill::from_elem(HybridBitSet::new_empty(bits_per_block));
 831
 832         DataflowAnalysis {
 833             body,
 834             dead_unwinds,
 835             flow_state: DataflowState {
 836                 sets: AllSets { bits_per_block, on_entry, trans: vec![nop; num_blocks] },
 837                 operator: denotation,
 838             },
 839         }
 840     }
 841 }
 842
 843 impl<'a, 'tcx, D> DataflowAnalysis<'a, 'tcx, D>
 844 where
 845     D: BitDenotation<'tcx>,
 846 {
 847     /// Propagates the bits of `in_out` into all the successors of `bb`,
 848     /// using bitwise operator denoted by `self.operator`.
 849     ///
 850     /// For most blocks, this is entirely uniform. However, for blocks
 851     /// that end with a call terminator, the effect of the call on the
 852     /// dataflow state may depend on whether the call returned
 853     /// successfully or unwound.
 854     ///
 855     /// To reflect this, the `propagate_call_return` method of the
 856     /// `BitDenotation` mutates `in_out` when propagating `in_out` via
 857     /// a call terminator; such mutation is performed *last*, to
 858     /// ensure its side-effects do not leak elsewhere (e.g., into
 859     /// unwind target).
 860     fn propagate_bits_into_graph_successors_of(
 861         &mut self,
 862         in_out: &mut BitSet<D::Idx>,
 863         (bb, bb_data): (mir::BasicBlock, &mir::BasicBlockData<'tcx>),
 864         dirty_list: &mut WorkQueue<mir::BasicBlock>,
 865     ) {
 866         match bb_data.terminator().kind {
 867             mir::TerminatorKind::Return
 868             | mir::TerminatorKind::Resume
 869             | mir::TerminatorKind::Abort
 870             | mir::TerminatorKind::GeneratorDrop
 871             | mir::TerminatorKind::Unreachable => {}
 872             mir::TerminatorKind::Goto { target }
 873             | mir::TerminatorKind::Assert { target, cleanup: None, .. }
 874             | mir::TerminatorKind::Yield { resume: target, drop: None, .. }
 875             | mir::TerminatorKind::Drop { target, location: _, unwind: None }
 876             | mir::TerminatorKind::DropAndReplace { target, value: _, location: _, unwind: None } =>
 877             {
 878                 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
 879             }
 880             mir::TerminatorKind::Yield { resume: target, drop: Some(drop), .. } => {
 881                 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
 882                 self.propagate_bits_into_entry_set_for(in_out, drop, dirty_list);
 883             }
 884             mir::TerminatorKind::Assert { target, cleanup: Some(unwind), .. }
 885             | mir::TerminatorKind::Drop { target, location: _, unwind: Some(unwind) }
 886             | mir::TerminatorKind::DropAndReplace {
 887                 target,
 888                 value: _,
 889                 location: _,
 890                 unwind: Some(unwind),
 891             } => {
 892                 self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
 893                 if !self.dead_unwinds.contains(bb) {
 894                     self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
 895                 }
 896             }
 897             mir::TerminatorKind::SwitchInt { ref targets, .. } => {
 898                 for target in targets {
 899                     self.propagate_bits_into_entry_set_for(in_out, *target, dirty_list);
 900                 }
 901             }
 902             mir::TerminatorKind::Call { cleanup, ref destination, .. } => {
 903                 if let Some(unwind) = cleanup {
 904                     if !self.dead_unwinds.contains(bb) {
 905                         self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
 906                     }
 907                 }
 908                 if let Some((ref dest_place, dest_bb)) = *destination {
 909                     // N.B.: This must be done *last*, after all other
 910                     // propagation, as documented in comment above.
 911                     self.flow_state.operator.propagate_call_return(in_out, bb, dest_bb, dest_place);
 912                     self.propagate_bits_into_entry_set_for(in_out, dest_bb, dirty_list);
 913                 }
 914             }
 915             mir::TerminatorKind::FalseEdges { real_target, imaginary_target } => {
 916                 self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
 917                 self.propagate_bits_into_entry_set_for(in_out, imaginary_target, dirty_list);
 918             }
 919             mir::TerminatorKind::FalseUnwind { real_target, unwind } => {
 920                 self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
 921                 if let Some(unwind) = unwind {
 922                     if !self.dead_unwinds.contains(bb) {
 923                         self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
 924                     }
 925                 }
 926             }
 927         }
 928     }
 929
 930     fn propagate_bits_into_entry_set_for(
 931         &mut self,
 932         in_out: &BitSet<D::Idx>,
 933         bb: mir::BasicBlock,
 934         dirty_queue: &mut WorkQueue<mir::BasicBlock>,
 935     ) {
 936         let entry_set = self.flow_state.sets.entry_set_mut_for(bb.index());
 937         let set_changed = self.flow_state.operator.join(entry_set, &in_out);
 938         if set_changed {
 939             dirty_queue.insert(bb);
 940         }
 941     }
 942 }