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::borrow::Borrow;
  22 use std::fmt;
  23 use std::io;
  24 use std::mem;
  25 use std::path::PathBuf;
  26 use std::usize;
  27
  28 pub use self::impls::{MaybeStorageLive};
  29 pub use self::impls::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
  30 pub use self::impls::{DefinitelyInitializedPlaces, MovingOutStatements};
  31 pub use self::impls::EverInitializedPlaces;
  32 pub use self::impls::borrows::{Borrows, BorrowData};
  33 pub use self::impls::HaveBeenBorrowedLocals;
  34 pub(crate) use self::impls::borrows::{ReserveOrActivateIndex};
  35 pub use self::at_location::{FlowAtLocation, FlowsAtLocation};
  36 pub(crate) use self::drop_flag_effects::*;
  37
  38 use self::move_paths::MoveData;
  39
  40 mod at_location;
  41 mod drop_flag_effects;
  42 mod graphviz;
  43 mod impls;
  44 pub mod move_paths;
  45
  46 pub(crate) use self::move_paths::indexes;
  47
  48 pub(crate) struct DataflowBuilder<'a, 'tcx: 'a, BD> where BD: BitDenotation
  49 {
  50     node_id: ast::NodeId,
  51     flow_state: DataflowAnalysis<'a, 'tcx, BD>,
  52     print_preflow_to: Option<String>,
  53     print_postflow_to: Option<String>,
  54 }
  55
  56 /// `DebugFormatted` encapsulates the "{:?}" rendering of some
  57 /// arbitrary value. This way: you pay cost of allocating an extra
  58 /// string (as well as that of rendering up-front); in exchange, you
  59 /// don't have to hand over ownership of your value or deal with
  60 /// borrowing it.
  61 pub(crate) struct DebugFormatted(String);
  62
  63 impl DebugFormatted {
  64     pub fn new(input: &dyn fmt::Debug) -> DebugFormatted {
  65         DebugFormatted(format!("{:?}", input))
  66     }
  67 }
  68
  69 impl fmt::Debug for DebugFormatted {
  70     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
  71         write!(w, "{}", self.0)
  72     }
  73 }
  74
  75 pub(crate) trait Dataflow<BD: BitDenotation> {
  76     /// Sets up and runs the dataflow problem, using `p` to render results if
  77     /// implementation so chooses.
  78     fn dataflow<P>(&mut self, p: P) where P: Fn(&BD, BD::Idx) -> DebugFormatted {
  79         let _ = p; // default implementation does not instrument process.
  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: 'a, BD> Dataflow<BD> for DataflowBuilder<'a, 'tcx, BD> where BD: BitDenotation
  92 {
  93     fn dataflow<P>(&mut self, p: P) where P: Fn(&BD, BD::Idx) -> DebugFormatted {
  94         self.flow_state.build_sets();
  95         self.pre_dataflow_instrumentation(|c,i| p(c,i)).unwrap();
  96         self.flow_state.propagate();
  97         self.post_dataflow_instrumentation(|c,i| p(c,i)).unwrap();
  98     }
  99
 100     fn build_sets(&mut self) { self.flow_state.build_sets(); }
 101     fn propagate(&mut self) { self.flow_state.propagate(); }
 102 }
 103
 104 pub(crate) fn has_rustc_mir_with(attrs: &[ast::Attribute], name: &str) -> Option<MetaItem> {
 105     for attr in attrs {
 106         if attr.check_name("rustc_mir") {
 107             let items = attr.meta_item_list();
 108             for item in items.iter().flat_map(|l| l.iter()) {
 109                 match item.meta_item() {
 110                     Some(mi) if mi.check_name(name) => return Some(mi.clone()),
 111                     _ => continue
 112                 }
 113             }
 114         }
 115     }
 116     return None;
 117 }
 118
 119 pub struct MoveDataParamEnv<'gcx, 'tcx> {
 120     pub(crate) move_data: MoveData<'tcx>,
 121     pub(crate) param_env: ty::ParamEnv<'gcx>,
 122 }
 123
 124 pub(crate) fn do_dataflow<'a, 'gcx, 'tcx, BD, P>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 125                                                  mir: &'a Mir<'tcx>,
 126                                                  node_id: ast::NodeId,
 127                                                  attributes: &[ast::Attribute],
 128                                                  dead_unwinds: &IdxSet<BasicBlock>,
 129                                                  bd: BD,
 130                                                  p: P)
 131                                                  -> DataflowResults<BD>
 132     where BD: BitDenotation + InitialFlow,
 133           P: Fn(&BD, BD::Idx) -> DebugFormatted
 134 {
 135     let flow_state = DataflowAnalysis::new(mir, dead_unwinds, bd);
 136     flow_state.run(tcx, node_id, attributes, p)
 137 }
 138
 139 impl<'a, 'gcx: 'tcx, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation
 140 {
 141     pub(crate) fn run<P>(self,
 142                          tcx: TyCtxt<'a, 'gcx, 'tcx>,
 143                          node_id: ast::NodeId,
 144                          attributes: &[ast::Attribute],
 145                          p: P) -> DataflowResults<BD>
 146         where P: Fn(&BD, BD::Idx) -> DebugFormatted
 147     {
 148         let name_found = |sess: &Session, attrs: &[ast::Attribute], name| -> Option<String> {
 149             if let Some(item) = has_rustc_mir_with(attrs, name) {
 150                 if let Some(s) = item.value_str() {
 151                     return Some(s.to_string())
 152                 } else {
 153                     sess.span_err(
 154                         item.span,
 155                         &format!("{} attribute requires a path", item.name()));
 156                     return None;
 157                 }
 158             }
 159             return None;
 160         };
 161
 162         let print_preflow_to =
 163             name_found(tcx.sess, attributes, "borrowck_graphviz_preflow");
 164         let print_postflow_to =
 165             name_found(tcx.sess, attributes, "borrowck_graphviz_postflow");
 166
 167         let mut mbcx = DataflowBuilder {
 168             node_id,
 169             print_preflow_to, print_postflow_to, flow_state: self,
 170         };
 171
 172         mbcx.dataflow(p);
 173         mbcx.flow_state.results()
 174     }
 175 }
 176
 177 struct PropagationContext<'b, 'a: 'b, 'tcx: 'a, O> where O: 'b + BitDenotation
 178 {
 179     builder: &'b mut DataflowAnalysis<'a, 'tcx, O>,
 180     changed: bool,
 181 }
 182
 183 impl<'a, 'tcx: 'a, BD> DataflowAnalysis<'a, 'tcx, BD> where BD: BitDenotation
 184 {
 185     fn propagate(&mut self) {
 186         let mut temp = IdxSetBuf::new_empty(self.flow_state.sets.bits_per_block);
 187         let mut propcx = PropagationContext {
 188             builder: self,
 189             changed: true,
 190         };
 191         while propcx.changed {
 192             propcx.changed = false;
 193             propcx.walk_cfg(&mut temp);
 194         }
 195     }
 196
 197     fn build_sets(&mut self) {
 198         // First we need to build the entry-, gen- and kill-sets.
 199
 200         {
 201             let sets = &mut self.flow_state.sets.for_block(mir::START_BLOCK.index());
 202             self.flow_state.operator.start_block_effect(&mut sets.on_entry);
 203         }
 204
 205         for (bb, data) in self.mir.basic_blocks().iter_enumerated() {
 206             let &mir::BasicBlockData { ref statements, ref terminator, is_cleanup: _ } = data;
 207
 208             let mut interim_state;
 209             let sets = &mut self.flow_state.sets.for_block(bb.index());
 210             let track_intrablock = BD::accumulates_intrablock_state();
 211             if track_intrablock {
 212                 debug!("swapping in mutable on_entry, initially {:?}", sets.on_entry);
 213                 interim_state = sets.on_entry.to_owned();
 214                 sets.on_entry = &mut interim_state;
 215             }
 216             for j_stmt in 0..statements.len() {
 217                 let location = Location { block: bb, statement_index: j_stmt };
 218                 self.flow_state.operator.before_statement_effect(sets, location);
 219                 self.flow_state.operator.statement_effect(sets, location);
 220                 if track_intrablock {
 221                     sets.apply_local_effect();
 222                 }
 223             }
 224
 225             if terminator.is_some() {
 226                 let location = Location { block: bb, statement_index: statements.len() };
 227                 self.flow_state.operator.before_terminator_effect(sets, location);
 228                 self.flow_state.operator.terminator_effect(sets, location);
 229                 if track_intrablock {
 230                     sets.apply_local_effect();
 231                 }
 232             }
 233         }
 234     }
 235 }
 236
 237 impl<'b, 'a: 'b, 'tcx: 'a, BD> PropagationContext<'b, 'a, 'tcx, BD> where BD: BitDenotation
 238 {
 239     fn walk_cfg(&mut self, in_out: &mut IdxSet<BD::Idx>) {
 240         let mir = self.builder.mir;
 241         for (bb_idx, bb_data) in mir.basic_blocks().iter().enumerate() {
 242             let builder = &mut self.builder;
 243             {
 244                 let sets = builder.flow_state.sets.for_block(bb_idx);
 245                 debug_assert!(in_out.words().len() == sets.on_entry.words().len());
 246                 in_out.clone_from(sets.on_entry);
 247                 in_out.union(sets.gen_set);
 248                 in_out.subtract(sets.kill_set);
 249             }
 250             builder.propagate_bits_into_graph_successors_of(
 251                 in_out, &mut self.changed, (mir::BasicBlock::new(bb_idx), bb_data));
 252         }
 253     }
 254 }
 255
 256 fn dataflow_path(context: &str, prepost: &str, path: &str) -> PathBuf {
 257     format!("{}_{}", context, prepost);
 258     let mut path = PathBuf::from(path);
 259     let new_file_name = {
 260         let orig_file_name = path.file_name().unwrap().to_str().unwrap();
 261         format!("{}_{}", context, orig_file_name)
 262     };
 263     path.set_file_name(new_file_name);
 264     path
 265 }
 266
 267 impl<'a, 'tcx: 'a, BD> DataflowBuilder<'a, 'tcx, BD> where BD: BitDenotation
 268 {
 269     fn pre_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
 270         where P: Fn(&BD, BD::Idx) -> DebugFormatted
 271     {
 272         if let Some(ref path_str) = self.print_preflow_to {
 273             let path = dataflow_path(BD::name(), "preflow", path_str);
 274             graphviz::print_borrowck_graph_to(self, &path, p)
 275         } else {
 276             Ok(())
 277         }
 278     }
 279
 280     fn post_dataflow_instrumentation<P>(&self, p: P) -> io::Result<()>
 281         where P: Fn(&BD, BD::Idx) -> DebugFormatted
 282     {
 283         if let Some(ref path_str) = self.print_postflow_to {
 284             let path = dataflow_path(BD::name(), "postflow", path_str);
 285             graphviz::print_borrowck_graph_to(self, &path, p)
 286         } else{
 287             Ok(())
 288         }
 289     }
 290 }
 291
 292 /// Maps each block to a set of bits
 293 #[derive(Debug)]
 294 pub(crate) struct Bits<E:Idx> {
 295     bits: IdxSetBuf<E>,
 296 }
 297
 298 impl<E:Idx> Clone for Bits<E> {
 299     fn clone(&self) -> Self { Bits { bits: self.bits.clone() } }
 300 }
 301
 302 impl<E:Idx> Bits<E> {
 303     fn new(bits: IdxSetBuf<E>) -> Self {
 304         Bits { bits: bits }
 305     }
 306 }
 307
 308 /// DataflowResultsConsumer abstracts over walking the MIR with some
 309 /// already constructed dataflow results.
 310 ///
 311 /// It abstracts over the FlowState and also completely hides the
 312 /// underlying flow analysis results, because it needs to handle cases
 313 /// where we are combining the results of *multiple* flow analyses
 314 /// (e.g. borrows + inits + uninits).
 315 pub(crate) trait DataflowResultsConsumer<'a, 'tcx: 'a> {
 316     type FlowState: FlowsAtLocation;
 317
 318     // Observation Hooks: override (at least one of) these to get analysis feedback.
 319     fn visit_block_entry(&mut self,
 320                          _bb: BasicBlock,
 321                          _flow_state: &Self::FlowState) {}
 322
 323     fn visit_statement_entry(&mut self,
 324                              _loc: Location,
 325                              _stmt: &Statement<'tcx>,
 326                              _flow_state: &Self::FlowState) {}
 327
 328     fn visit_terminator_entry(&mut self,
 329                               _loc: Location,
 330                               _term: &Terminator<'tcx>,
 331                               _flow_state: &Self::FlowState) {}
 332
 333     // Main entry point: this drives the processing of results.
 334
 335     fn analyze_results(&mut self, flow_uninit: &mut Self::FlowState) {
 336         let flow = flow_uninit;
 337         for bb in self.mir().basic_blocks().indices() {
 338             flow.reset_to_entry_of(bb);
 339             self.process_basic_block(bb, flow);
 340         }
 341     }
 342
 343     fn process_basic_block(&mut self, bb: BasicBlock, flow_state: &mut Self::FlowState) {
 344         let BasicBlockData { ref statements, ref terminator, is_cleanup: _ } =
 345             self.mir()[bb];
 346         let mut location = Location { block: bb, statement_index: 0 };
 347         for stmt in statements.iter() {
 348             flow_state.reconstruct_statement_effect(location);
 349             self.visit_statement_entry(location, stmt, flow_state);
 350             flow_state.apply_local_effect(location);
 351             location.statement_index += 1;
 352         }
 353
 354         if let Some(ref term) = *terminator {
 355             flow_state.reconstruct_terminator_effect(location);
 356             self.visit_terminator_entry(location, term, flow_state);
 357
 358             // We don't need to apply the effect of the terminator,
 359             // since we are only visiting dataflow state on control
 360             // flow entry to the various nodes. (But we still need to
 361             // reconstruct the effect, because the visit method might
 362             // inspect it.)
 363         }
 364     }
 365
 366     // Delegated Hooks: Provide access to the MIR and process the flow state.
 367
 368     fn mir(&self) -> &'a Mir<'tcx>;
 369 }
 370
 371 pub fn state_for_location<'tcx, T: BitDenotation>(loc: Location,
 372                                                   analysis: &T,
 373                                                   result: &DataflowResults<T>,
 374                                                   mir: &Mir<'tcx>)
 375     -> IdxSetBuf<T::Idx> {
 376     let mut entry = result.sets().on_entry_set_for(loc.block.index()).to_owned();
 377
 378     {
 379         let mut sets = BlockSets {
 380             on_entry: &mut entry.clone(),
 381             kill_set: &mut entry.clone(),
 382             gen_set: &mut entry,
 383         };
 384
 385         for stmt in 0..loc.statement_index {
 386             let mut stmt_loc = loc;
 387             stmt_loc.statement_index = stmt;
 388             analysis.before_statement_effect(&mut sets, stmt_loc);
 389             analysis.statement_effect(&mut sets, stmt_loc);
 390         }
 391
 392         // Apply the pre-statement effect of the statement we're evaluating.
 393         if loc.statement_index == mir[loc.block].statements.len() {
 394             analysis.before_terminator_effect(&mut sets, loc);
 395         } else {
 396             analysis.before_statement_effect(&mut sets, loc);
 397         }
 398     }
 399
 400     entry
 401 }
 402
 403 pub struct DataflowAnalysis<'a, 'tcx: 'a, O> where O: BitDenotation
 404 {
 405     flow_state: DataflowState<O>,
 406     dead_unwinds: &'a IdxSet<mir::BasicBlock>,
 407     mir: &'a Mir<'tcx>,
 408 }
 409
 410 impl<'a, 'tcx: 'a, O> DataflowAnalysis<'a, 'tcx, O> where O: BitDenotation
 411 {
 412     pub fn results(self) -> DataflowResults<O> {
 413         DataflowResults(self.flow_state)
 414     }
 415
 416     pub fn mir(&self) -> &'a Mir<'tcx> { self.mir }
 417 }
 418
 419 pub struct DataflowResults<O>(pub(crate) DataflowState<O>) where O: BitDenotation;
 420
 421 impl<O: BitDenotation> DataflowResults<O> {
 422     pub fn sets(&self) -> &AllSets<O::Idx> {
 423         &self.0.sets
 424     }
 425
 426     pub fn operator(&self) -> &O {
 427         &self.0.operator
 428     }
 429 }
 430
 431 /// State of a dataflow analysis; couples a collection of bit sets
 432 /// with operator used to initialize and merge bits during analysis.
 433 pub struct DataflowState<O: BitDenotation>
 434 {
 435     /// All the sets for the analysis. (Factored into its
 436     /// own structure so that we can borrow it mutably
 437     /// on its own separate from other fields.)
 438     pub sets: AllSets<O::Idx>,
 439
 440     /// operator used to initialize, combine, and interpret bits.
 441     pub(crate) operator: O,
 442 }
 443
 444 impl<O: BitDenotation> DataflowState<O> {
 445     pub fn each_bit<F>(&self, words: &IdxSet<O::Idx>, f: F) where F: FnMut(O::Idx)
 446     {
 447         words.iter().for_each(f)
 448     }
 449
 450     pub(crate) fn interpret_set<'c, P>(&self,
 451                                        o: &'c O,
 452                                        words: &IdxSet<O::Idx>,
 453                                        render_idx: &P)
 454                                        -> Vec<DebugFormatted>
 455         where P: Fn(&O, O::Idx) -> DebugFormatted
 456     {
 457         let mut v = Vec::new();
 458         self.each_bit(words, |i| {
 459             v.push(render_idx(o, i));
 460         });
 461         v
 462     }
 463 }
 464
 465 #[derive(Debug)]
 466 pub struct AllSets<E: Idx> {
 467     /// Analysis bitwidth for each block.
 468     bits_per_block: usize,
 469
 470     /// Number of words associated with each block entry
 471     /// equal to bits_per_block / usize::BITS, rounded up.
 472     words_per_block: usize,
 473
 474     /// For each block, bits generated by executing the statements in
 475     /// the block. (For comparison, the Terminator for each block is
 476     /// handled in a flow-specific manner during propagation.)
 477     gen_sets: Bits<E>,
 478
 479     /// For each block, bits killed by executing the statements in the
 480     /// block. (For comparison, the Terminator for each block is
 481     /// handled in a flow-specific manner during propagation.)
 482     kill_sets: Bits<E>,
 483
 484     /// For each block, bits valid on entry to the block.
 485     on_entry_sets: Bits<E>,
 486 }
 487
 488 /// Triple of sets associated with a given block.
 489 ///
 490 /// Generally, one sets up `on_entry`, `gen_set`, and `kill_set` for
 491 /// each block individually, and then runs the dataflow analysis which
 492 /// iteratively modifies the various `on_entry` sets (but leaves the
 493 /// other two sets unchanged, since they represent the effect of the
 494 /// block, which should be invariant over the course of the analysis).
 495 ///
 496 /// It is best to ensure that the intersection of `gen_set` and
 497 /// `kill_set` is empty; otherwise the results of the dataflow will
 498 /// have a hidden dependency on what order the bits are generated and
 499 /// killed during the iteration. (This is such a good idea that the
 500 /// `fn gen` and `fn kill` methods that set their state enforce this
 501 /// for you.)
 502 #[derive(Debug)]
 503 pub struct BlockSets<'a, E: Idx> {
 504     /// Dataflow state immediately before control flow enters the given block.
 505     pub(crate) on_entry: &'a mut IdxSet<E>,
 506
 507     /// Bits that are set to 1 by the time we exit the given block.
 508     pub(crate) gen_set: &'a mut IdxSet<E>,
 509
 510     /// Bits that are set to 0 by the time we exit the given block.
 511     pub(crate) kill_set: &'a mut IdxSet<E>,
 512 }
 513
 514 impl<'a, E:Idx> BlockSets<'a, E> {
 515     fn gen(&mut self, e: &E) {
 516         self.gen_set.add(e);
 517         self.kill_set.remove(e);
 518     }
 519     fn gen_all<I>(&mut self, i: I)
 520         where I: IntoIterator,
 521               I::Item: Borrow<E>
 522     {
 523         for j in i {
 524             self.gen(j.borrow());
 525         }
 526     }
 527
 528     fn gen_all_and_assert_dead<I>(&mut self, i: I)
 529         where I: IntoIterator,
 530         I::Item: Borrow<E>
 531     {
 532         for j in i {
 533             let j = j.borrow();
 534             let retval = self.gen_set.add(j);
 535             self.kill_set.remove(j);
 536             assert!(retval);
 537         }
 538     }
 539
 540     fn kill(&mut self, e: &E) {
 541         self.gen_set.remove(e);
 542         self.kill_set.add(e);
 543     }
 544
 545     fn kill_all<I>(&mut self, i: I)
 546         where I: IntoIterator,
 547               I::Item: Borrow<E>
 548     {
 549         for j in i {
 550             self.kill(j.borrow());
 551         }
 552     }
 553
 554     fn apply_local_effect(&mut self) {
 555         self.on_entry.union(&self.gen_set);
 556         self.on_entry.subtract(&self.kill_set);
 557     }
 558 }
 559
 560 impl<E:Idx> AllSets<E> {
 561     pub fn bits_per_block(&self) -> usize { self.bits_per_block }
 562     pub fn for_block(&mut self, block_idx: usize) -> BlockSets<E> {
 563         let offset = self.words_per_block * block_idx;
 564         let range = E::new(offset)..E::new(offset + self.words_per_block);
 565         BlockSets {
 566             on_entry: self.on_entry_sets.bits.range_mut(&range),
 567             gen_set: self.gen_sets.bits.range_mut(&range),
 568             kill_set: self.kill_sets.bits.range_mut(&range),
 569         }
 570     }
 571
 572     fn lookup_set_for<'a>(&self, sets: &'a Bits<E>, block_idx: usize) -> &'a IdxSet<E> {
 573         let offset = self.words_per_block * block_idx;
 574         let range = E::new(offset)..E::new(offset + self.words_per_block);
 575         sets.bits.range(&range)
 576     }
 577     pub fn gen_set_for(&self, block_idx: usize) -> &IdxSet<E> {
 578         self.lookup_set_for(&self.gen_sets, block_idx)
 579     }
 580     pub fn kill_set_for(&self, block_idx: usize) -> &IdxSet<E> {
 581         self.lookup_set_for(&self.kill_sets, block_idx)
 582     }
 583     pub fn on_entry_set_for(&self, block_idx: usize) -> &IdxSet<E> {
 584         self.lookup_set_for(&self.on_entry_sets, block_idx)
 585     }
 586 }
 587
 588 /// Parameterization for the precise form of data flow that is used.
 589 /// `InitialFlow` handles initializing the bitvectors before any
 590 /// code is inspected by the analysis. Analyses that need more nuanced
 591 /// initialization (e.g. they need to consult the results of some other
 592 /// dataflow analysis to set up the initial bitvectors) should not
 593 /// implement this.
 594 pub trait InitialFlow {
 595     /// Specifies the initial value for each bit in the `on_entry` set
 596     fn bottom_value() -> bool;
 597 }
 598
 599 pub trait BitDenotation: BitwiseOperator {
 600     /// Specifies what index type is used to access the bitvector.
 601     type Idx: Idx;
 602
 603     /// Some analyses want to accumulate knowledge within a block when
 604     /// analyzing its statements for building the gen/kill sets. Override
 605     /// this method to return true in such cases.
 606     ///
 607     /// When this returns true, the statement-effect (re)construction
 608     /// will clone the `on_entry` state and pass along a reference via
 609     /// `sets.on_entry` to that local clone into `statement_effect` and
 610     /// `terminator_effect`).
 611     ///
 612     /// When its false, no local clone is constucted; instead a
 613     /// reference directly into `on_entry` is passed along via
 614     /// `sets.on_entry` instead, which represents the flow state at
 615     /// the block's start, not necessarily the state immediately prior
 616     /// to the statement/terminator under analysis.
 617     ///
 618     /// In either case, the passed reference is mutable; but this is a
 619     /// wart from using the `BlockSets` type in the API; the intention
 620     /// is that the `statement_effect` and `terminator_effect` methods
 621     /// mutate only the gen/kill sets.
 622     ///
 623     /// FIXME: We should consider enforcing the intention described in
 624     /// the previous paragraph by passing the three sets in separate
 625     /// parameters to encode their distinct mutabilities.
 626     fn accumulates_intrablock_state() -> bool { false }
 627
 628     /// A name describing the dataflow analysis that this
 629     /// BitDenotation is supporting.  The name should be something
 630     /// suitable for plugging in as part of a filename e.g. avoid
 631     /// space-characters or other things that tend to look bad on a
 632     /// file system, like slashes or periods. It is also better for
 633     /// the name to be reasonably short, again because it will be
 634     /// plugged into a filename.
 635     fn name() -> &'static str;
 636
 637     /// Size of each bitvector allocated for each block in the analysis.
 638     fn bits_per_block(&self) -> usize;
 639
 640     /// Mutates the entry set according to the effects that
 641     /// have been established *prior* to entering the start
 642     /// block. This can't access the gen/kill sets, because
 643     /// these won't be accounted for correctly.
 644     ///
 645     /// (For example, establishing the call arguments.)
 646     fn start_block_effect(&self, entry_set: &mut IdxSet<Self::Idx>);
 647
 648     /// Similar to `statement_effect`, except it applies
 649     /// *just before* the statement rather than *just after* it.
 650     ///
 651     /// This matters for "dataflow at location" APIs, because the
 652     /// before-statement effect is visible while visiting the
 653     /// statement, while the after-statement effect only becomes
 654     /// visible at the next statement.
 655     ///
 656     /// Both the before-statement and after-statement effects are
 657     /// applied, in that order, before moving for the next
 658     /// statement.
 659     fn before_statement_effect(&self,
 660                                _sets: &mut BlockSets<Self::Idx>,
 661                                _location: Location) {}
 662
 663     /// Mutates the block-sets (the flow sets for the given
 664     /// basic block) according to the effects of evaluating statement.
 665     ///
 666     /// This is used, in particular, for building up the
 667     /// "transfer-function" representing the overall-effect of the
 668     /// block, represented via GEN and KILL sets.
 669     ///
 670     /// The statement is identified as `bb_data[idx_stmt]`, where
 671     /// `bb_data` is the sequence of statements identified by `bb` in
 672     /// the MIR.
 673     fn statement_effect(&self,
 674                         sets: &mut BlockSets<Self::Idx>,
 675                         location: Location);
 676
 677     /// Similar to `terminator_effect`, except it applies
 678     /// *just before* the terminator rather than *just after* it.
 679     ///
 680     /// This matters for "dataflow at location" APIs, because the
 681     /// before-terminator effect is visible while visiting the
 682     /// terminator, while the after-terminator effect only becomes
 683     /// visible at the terminator's successors.
 684     ///
 685     /// Both the before-terminator and after-terminator effects are
 686     /// applied, in that order, before moving for the next
 687     /// terminator.
 688     fn before_terminator_effect(&self,
 689                                 _sets: &mut BlockSets<Self::Idx>,
 690                                 _location: Location) {}
 691
 692     /// Mutates the block-sets (the flow sets for the given
 693     /// basic block) according to the effects of evaluating
 694     /// the terminator.
 695     ///
 696     /// This is used, in particular, for building up the
 697     /// "transfer-function" representing the overall-effect of the
 698     /// block, represented via GEN and KILL sets.
 699     ///
 700     /// The effects applied here cannot depend on which branch the
 701     /// terminator took.
 702     fn terminator_effect(&self,
 703                          sets: &mut BlockSets<Self::Idx>,
 704                          location: Location);
 705
 706     /// Mutates the block-sets according to the (flow-dependent)
 707     /// effect of a successful return from a Call terminator.
 708     ///
 709     /// If basic-block BB_x ends with a call-instruction that, upon
 710     /// successful return, flows to BB_y, then this method will be
 711     /// called on the exit flow-state of BB_x in order to set up the
 712     /// entry flow-state of BB_y.
 713     ///
 714     /// This is used, in particular, as a special case during the
 715     /// "propagate" loop where all of the basic blocks are repeatedly
 716     /// visited. Since the effects of a Call terminator are
 717     /// flow-dependent, the current MIR cannot encode them via just
 718     /// GEN and KILL sets attached to the block, and so instead we add
 719     /// this extra machinery to represent the flow-dependent effect.
 720     ///
 721     /// FIXME: Right now this is a bit of a wart in the API. It might
 722     /// be better to represent this as an additional gen- and
 723     /// kill-sets associated with each edge coming out of the basic
 724     /// block.
 725     fn propagate_call_return(&self,
 726                              in_out: &mut IdxSet<Self::Idx>,
 727                              call_bb: mir::BasicBlock,
 728                              dest_bb: mir::BasicBlock,
 729                              dest_place: &mir::Place);
 730 }
 731
 732 impl<'a, 'tcx, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation
 733 {
 734     pub fn new(mir: &'a Mir<'tcx>,
 735                dead_unwinds: &'a IdxSet<mir::BasicBlock>,
 736                denotation: D) -> Self where D: InitialFlow {
 737         let bits_per_block = denotation.bits_per_block();
 738         let usize_bits = mem::size_of::<usize>() * 8;
 739         let words_per_block = (bits_per_block + usize_bits - 1) / usize_bits;
 740         let num_overall = Self::num_bits_overall(mir, bits_per_block);
 741
 742         let zeroes = Bits::new(IdxSetBuf::new_empty(num_overall));
 743         let on_entry = Bits::new(if D::bottom_value() {
 744             IdxSetBuf::new_filled(num_overall)
 745         } else {
 746             IdxSetBuf::new_empty(num_overall)
 747         });
 748
 749         DataflowAnalysis {
 750             mir,
 751             dead_unwinds,
 752             flow_state: DataflowState {
 753                 sets: AllSets {
 754                     bits_per_block,
 755                     words_per_block,
 756                     gen_sets: zeroes.clone(),
 757                     kill_sets: zeroes,
 758                     on_entry_sets: on_entry,
 759                 },
 760                 operator: denotation,
 761             }
 762         }
 763     }
 764
 765     pub fn new_from_sets(mir: &'a Mir<'tcx>,
 766                          dead_unwinds: &'a IdxSet<mir::BasicBlock>,
 767                          sets: AllSets<D::Idx>,
 768                          denotation: D) -> Self {
 769         DataflowAnalysis {
 770             mir,
 771             dead_unwinds,
 772             flow_state: DataflowState {
 773                 sets: sets,
 774                 operator: denotation,
 775             }
 776         }
 777     }
 778
 779     fn num_bits_overall(mir: &Mir, bits_per_block: usize) -> usize {
 780         let usize_bits = mem::size_of::<usize>() * 8;
 781         let words_per_block = (bits_per_block + usize_bits - 1) / usize_bits;
 782
 783         // (now rounded up to multiple of word size)
 784         let bits_per_block = words_per_block * usize_bits;
 785
 786         let num_blocks = mir.basic_blocks().len();
 787         let num_overall = num_blocks * bits_per_block;
 788         num_overall
 789     }
 790 }
 791
 792 impl<'a, 'tcx: 'a, D> DataflowAnalysis<'a, 'tcx, D> where D: BitDenotation
 793 {
 794     /// Propagates the bits of `in_out` into all the successors of `bb`,
 795     /// using bitwise operator denoted by `self.operator`.
 796     ///
 797     /// For most blocks, this is entirely uniform. However, for blocks
 798     /// that end with a call terminator, the effect of the call on the
 799     /// dataflow state may depend on whether the call returned
 800     /// successfully or unwound.
 801     ///
 802     /// To reflect this, the `propagate_call_return` method of the
 803     /// `BitDenotation` mutates `in_out` when propagating `in_out` via
 804     /// a call terminator; such mutation is performed *last*, to
 805     /// ensure its side-effects do not leak elsewhere (e.g. into
 806     /// unwind target).
 807     fn propagate_bits_into_graph_successors_of(
 808         &mut self,
 809         in_out: &mut IdxSet<D::Idx>,
 810         changed: &mut bool,
 811         (bb, bb_data): (mir::BasicBlock, &mir::BasicBlockData))
 812     {
 813         match bb_data.terminator().kind {
 814             mir::TerminatorKind::Return |
 815             mir::TerminatorKind::Resume |
 816             mir::TerminatorKind::Abort |
 817             mir::TerminatorKind::GeneratorDrop |
 818             mir::TerminatorKind::Unreachable => {}
 819             mir::TerminatorKind::Goto { ref target } |
 820             mir::TerminatorKind::Assert { ref target, cleanup: None, .. } |
 821             mir::TerminatorKind::Yield { resume: ref target, drop: None, .. } |
 822             mir::TerminatorKind::Drop { ref target, location: _, unwind: None } |
 823             mir::TerminatorKind::DropAndReplace {
 824                 ref target, value: _, location: _, unwind: None
 825             } => {
 826                 self.propagate_bits_into_entry_set_for(in_out, changed, target);
 827             }
 828             mir::TerminatorKind::Yield { resume: ref target, drop: Some(ref drop), .. } => {
 829                 self.propagate_bits_into_entry_set_for(in_out, changed, target);
 830                 self.propagate_bits_into_entry_set_for(in_out, changed, drop);
 831             }
 832             mir::TerminatorKind::Assert { ref target, cleanup: Some(ref unwind), .. } |
 833             mir::TerminatorKind::Drop { ref target, location: _, unwind: Some(ref unwind) } |
 834             mir::TerminatorKind::DropAndReplace {
 835                 ref target, value: _, location: _, unwind: Some(ref unwind)
 836             } => {
 837                 self.propagate_bits_into_entry_set_for(in_out, changed, target);
 838                 if !self.dead_unwinds.contains(&bb) {
 839                     self.propagate_bits_into_entry_set_for(in_out, changed, unwind);
 840                 }
 841             }
 842             mir::TerminatorKind::SwitchInt { ref targets, .. } => {
 843                 for target in targets {
 844                     self.propagate_bits_into_entry_set_for(in_out, changed, target);
 845                 }
 846             }
 847             mir::TerminatorKind::Call { ref cleanup, ref destination, func: _, args: _ } => {
 848                 if let Some(ref unwind) = *cleanup {
 849                     if !self.dead_unwinds.contains(&bb) {
 850                         self.propagate_bits_into_entry_set_for(in_out, changed, unwind);
 851                     }
 852                 }
 853                 if let Some((ref dest_place, ref dest_bb)) = *destination {
 854                     // N.B.: This must be done *last*, after all other
 855                     // propagation, as documented in comment above.
 856                     self.flow_state.operator.propagate_call_return(
 857                         in_out, bb, *dest_bb, dest_place);
 858                     self.propagate_bits_into_entry_set_for(in_out, changed, dest_bb);
 859                 }
 860             }
 861             mir::TerminatorKind::FalseEdges { ref real_target, ref imaginary_targets } => {
 862                 self.propagate_bits_into_entry_set_for(in_out, changed, real_target);
 863                 for target in imaginary_targets {
 864                     self.propagate_bits_into_entry_set_for(in_out, changed, target);
 865                 }
 866             }
 867             mir::TerminatorKind::FalseUnwind { ref real_target, unwind } => {
 868                 self.propagate_bits_into_entry_set_for(in_out, changed, real_target);
 869                 if let Some(ref unwind) = unwind {
 870                     if !self.dead_unwinds.contains(&bb) {
 871                         self.propagate_bits_into_entry_set_for(in_out, changed, unwind);
 872                     }
 873                 }
 874             }
 875         }
 876     }
 877
 878     fn propagate_bits_into_entry_set_for(&mut self,
 879                                          in_out: &IdxSet<D::Idx>,
 880                                          changed: &mut bool,
 881                                          bb: &mir::BasicBlock) {
 882         let entry_set = self.flow_state.sets.for_block(bb.index()).on_entry;
 883         let set_changed = bitwise(entry_set.words_mut(),
 884                                   in_out.words(),
 885                                   &self.flow_state.operator);
 886         if set_changed {
 887             *changed = true;
 888         }
 889     }
 890 }