src/librustc_mir/dataflow/mod.rs

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