src/librustc_mir/util/liveness.rs

   1 // Copyright 2017 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 //! Liveness analysis which computes liveness of MIR local variables at the boundary of basic blocks
  12 //!
  13 //! This analysis considers references as being used only at the point of the
  14 //! borrow. This means that this does not track uses because of references that
  15 //! already exist:
  16 //!
  17 //! ```Rust
  18 //!     fn foo() {
  19 //!         x = 0;
  20 //!         // `x` is live here
  21 //!         GLOBAL = &x: *const u32;
  22 //!         // but not here, even while it can be accessed through `GLOBAL`.
  23 //!         foo();
  24 //!         x = 1;
  25 //!         // `x` is live again here, because it is assigned to `OTHER_GLOBAL`
  26 //!         OTHER_GLOBAL = &x: *const u32;
  27 //!         // ...
  28 //!     }
  29 //! ```
  30 //!
  31 //! This means that users of this analysis still have to check whether
  32 //! pre-existing references can be used to access the value (e.g. at movable
  33 //! generator yield points, all pre-existing references are invalidated, so this
  34 //! doesn't matter).
  35
  36 use rustc::mir::*;
  37 use rustc::mir::visit::{PlaceContext, Visitor};
  38 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  39 use rustc_data_structures::indexed_set::IdxSetBuf;
  40 use rustc_data_structures::work_queue::WorkQueue;
  41 use util::pretty::{dump_enabled, write_basic_block, write_mir_intro};
  42 use rustc::ty::item_path;
  43 use rustc::mir::Local;
  44 use rustc::mir::visit::MirVisitable;
  45 use std::path::{Path, PathBuf};
  46 use std::fs;
  47 use rustc::ty::TyCtxt;
  48 use std::io::{self, Write};
  49 use transform::MirSource;
  50
  51 pub type LocalSet<V: Idx> = IdxSetBuf<V>;
  52
  53 /// This gives the result of the liveness analysis at the boundary of
  54 /// basic blocks. You can use `simulate_block` to obtain the
  55 /// intra-block results.
  56 pub struct LivenessResult<V: Idx> {
  57     /// Liveness mode in use when these results were computed.
  58     pub mode: LivenessMode,
  59
  60     /// Live variables on exit to each basic block. This is equal to
  61     /// the union of the `ins` for each successor.
  62     pub outs: IndexVec<BasicBlock, LocalSet<V>>,
  63 }
  64
  65 trait LiveVariableMap {
  66     type LiveVar;
  67
  68     fn from_local(&self, local: Local) -> Option<Self::LiveVar>;
  69     fn from_live_var(&self, local: Self::LiveVar) -> Local;
  70 }
  71
  72 #[derive(Eq, PartialEq, Clone)]
  73 struct IdentityMap;
  74
  75 impl LiveVariableMap for IdentityMap {
  76     type LiveVar = Local;
  77
  78     fn from_local(&self, local: Local) -> Option<Self::LiveVar> {
  79         Some(local)
  80     }
  81
  82     fn from_live_var(&self, local: Self::LiveVar) -> Local {
  83         local
  84     }
  85 }
  86
  87 #[derive(Copy, Clone, Debug)]
  88 pub struct LivenessMode {
  89     /// If true, then we will consider "regular uses" of a variable to be live.
  90     /// For example, if the user writes `foo(x)`, then this is a regular use of
  91     /// the variable `x`.
  92     pub include_regular_use: bool,
  93
  94     /// If true, then we will consider (implicit) drops of a variable
  95     /// to be live.  For example, if the user writes `{ let x =
  96     /// vec![...]; .. }`, then the drop at the end of the block is an
  97     /// implicit drop.
  98     ///
  99     /// NB. Despite its name, a call like `::std::mem::drop(x)` is
 100     /// **not** considered a drop for this purposes, but rather a
 101     /// regular use.
 102     pub include_drops: bool,
 103 }
 104
 105 /// A combination of liveness results, used in NLL.
 106 pub struct LivenessResults<V: Idx> {
 107     /// Liveness results where a regular use makes a variable X live,
 108     /// but not a drop.
 109     pub regular: LivenessResult<V>,
 110
 111     /// Liveness results where a drop makes a variable X live,
 112     /// but not a regular use.
 113     pub drop: LivenessResult<V>,
 114 }
 115
 116 impl<V: Idx> LivenessResults<V> {
 117     pub fn compute<'tcx>(mir: &Mir<'tcx>, map: &dyn LiveVariableMap<LiveVar = V>) -> LivenessResults<V> {
 118         LivenessResults {
 119             regular: liveness_of_locals(
 120                 &mir,
 121                 LivenessMode {
 122                     include_regular_use: true,
 123                     include_drops: false,
 124                 },
 125             ),
 126
 127             drop: liveness_of_locals(
 128                 &mir,
 129                 LivenessMode {
 130                     include_regular_use: false,
 131                     include_drops: true,
 132                 },
 133             ),
 134         }
 135     }
 136 }
 137
 138 /// Compute which local variables are live within the given function
 139 /// `mir`. The liveness mode `mode` determines what sorts of uses are
 140 /// considered to make a variable live (e.g., do drops count?).
 141 pub fn liveness_of_locals<'tcx, V: Idx>(mir: &Mir<'tcx>, mode: LivenessMode) -> LivenessResult<V> {
 142     let locals = mir.local_decls.len();
 143     let def_use: IndexVec<_, _> = mir.basic_blocks()
 144         .iter()
 145         .map(|b| block(mode, b, locals))
 146         .collect();
 147
 148     let mut outs: IndexVec<_, _> = mir.basic_blocks()
 149         .indices()
 150         .map(|_| LocalSet::new_empty(locals))
 151         .collect();
 152
 153     let mut bits = LocalSet::new_empty(locals);
 154
 155     // queue of things that need to be re-processed, and a set containing
 156     // the things currently in the queue
 157     let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_all(mir.basic_blocks().len());
 158
 159     let predecessors = mir.predecessors();
 160
 161     while let Some(bb) = dirty_queue.pop() {
 162         // bits = use ∪ (bits - def)
 163         bits.overwrite(&outs[bb]);
 164         def_use[bb].apply(&mut bits);
 165
 166         // `bits` now contains the live variables on entry. Therefore,
 167         // add `bits` to the `out` set for each predecessor; if those
 168         // bits were not already present, then enqueue the predecessor
 169         // as dirty.
 170         //
 171         // (note that `union` returns true if the `self` set changed)
 172         for &pred_bb in &predecessors[bb] {
 173             if outs[pred_bb].union(&bits) {
 174                 dirty_queue.insert(pred_bb);
 175             }
 176         }
 177     }
 178
 179     LivenessResult { mode, outs }
 180 }
 181
 182 impl<V> LivenessResult<V>
 183 where V:Idx
 184 {
 185     /// Walks backwards through the statements/terminator in the given
 186     /// basic block `block`.  At each point within `block`, invokes
 187     /// the callback `op` with the current location and the set of
 188     /// variables that are live on entry to that location.
 189     pub fn simulate_block<'tcx, OP>(&self, mir: &Mir<'tcx>, block: BasicBlock, mut callback: OP)
 190     where
 191         OP: FnMut(Location, &LocalSet<V>),
 192     {
 193         let data = &mir[block];
 194
 195         // Get a copy of the bits on exit from the block.
 196         let mut bits = self.outs[block].clone();
 197
 198         // Start with the maximal statement index -- i.e., right before
 199         // the terminator executes.
 200         let mut statement_index = data.statements.len();
 201
 202         // Compute liveness right before terminator and invoke callback.
 203         let terminator_location = Location {
 204             block,
 205             statement_index,
 206         };
 207         let locals = mir.local_decls.len();
 208         let mut visitor = DefsUsesVisitor {
 209             mode: self.mode,
 210             defs_uses: DefsUses {
 211                 defs: LocalSet::new_empty(locals),
 212                 uses: LocalSet::new_empty(locals),
 213                 map: &IdentityMap {},
 214             },
 215         };
 216         // Visit the various parts of the basic block in reverse. If we go
 217         // forward, the logic in `add_def` and `add_use` would be wrong.
 218         visitor.update_bits_and_do_callback(terminator_location, &data.terminator, &mut bits,
 219                                             &mut callback);
 220
 221         // Compute liveness before each statement (in rev order) and invoke callback.
 222         for statement in data.statements.iter().rev() {
 223             statement_index -= 1;
 224             let statement_location = Location {
 225                 block,
 226                 statement_index,
 227             };
 228             visitor.defs_uses.clear();
 229             visitor.update_bits_and_do_callback(statement_location, statement, &mut bits,
 230                                                 &mut callback);
 231         }
 232     }
 233 }
 234
 235 #[derive(Eq, PartialEq, Clone)]
 236 pub enum DefUse {
 237     Def,
 238     Use,
 239 }
 240
 241 pub fn categorize<'tcx>(context: PlaceContext<'tcx>, mode: LivenessMode) -> Option<DefUse> {
 242     match context {
 243         ///////////////////////////////////////////////////////////////////////////
 244         // DEFS
 245
 246         PlaceContext::Store |
 247
 248         // This is potentially both a def and a use...
 249         PlaceContext::AsmOutput |
 250
 251         // We let Call define the result in both the success and
 252         // unwind cases. This is not really correct, however it
 253         // does not seem to be observable due to the way that we
 254         // generate MIR. See the test case
 255         // `mir-opt/nll/liveness-call-subtlety.rs`. To do things
 256         // properly, we would apply the def in call only to the
 257         // input from the success path and not the unwind
 258         // path. -nmatsakis
 259         PlaceContext::Call |
 260
 261         // Storage live and storage dead aren't proper defines, but we can ignore
 262         // values that come before them.
 263         PlaceContext::StorageLive |
 264         PlaceContext::StorageDead => Some(DefUse::Def),
 265
 266         ///////////////////////////////////////////////////////////////////////////
 267         // REGULAR USES
 268         //
 269         // These are uses that occur *outside* of a drop. For the
 270         // purposes of NLL, these are special in that **all** the
 271         // lifetimes appearing in the variable must be live for each regular use.
 272
 273         PlaceContext::Projection(..) |
 274
 275         // Borrows only consider their local used at the point of the borrow.
 276         // This won't affect the results since we use this analysis for generators
 277         // and we only care about the result at suspension points. Borrows cannot
 278         // cross suspension points so this behavior is unproblematic.
 279         PlaceContext::Borrow { .. } |
 280
 281         PlaceContext::Inspect |
 282         PlaceContext::Copy |
 283         PlaceContext::Move |
 284         PlaceContext::Validate => {
 285             if mode.include_regular_use {
 286                 Some(DefUse::Use)
 287             } else {
 288                 None
 289             }
 290         }
 291
 292         ///////////////////////////////////////////////////////////////////////////
 293         // DROP USES
 294         //
 295         // These are uses that occur in a DROP (a MIR drop, not a
 296         // call to `std::mem::drop()`). For the purposes of NLL,
 297         // uses in drop are special because `#[may_dangle]`
 298         // attributes can affect whether lifetimes must be live.
 299
 300         PlaceContext::Drop => {
 301             if mode.include_drops {
 302                 Some(DefUse::Use)
 303             } else {
 304                 None
 305             }
 306         }
 307     }
 308 }
 309
 310 struct DefsUsesVisitor<'lv> {
 311     mode: LivenessMode,
 312     defs_uses: DefsUses<'lv>,
 313 }
 314
 315 #[derive(Eq, PartialEq, Clone)]
 316 struct DefsUses<'lv>
 317 {
 318     defs: LocalSet<Local>,
 319     uses: LocalSet<Local>,
 320     map: &'lv dyn LiveVariableMap<LiveVar=Local>,
 321 }
 322
 323 impl<'lv> DefsUses<'lv> {
 324     fn clear(&mut self) {
 325         self.uses.clear();
 326         self.defs.clear();
 327     }
 328
 329     fn apply(&self, bits: &mut LocalSet<Local>) -> bool {
 330         bits.subtract(&self.defs) | bits.union(&self.uses)
 331     }
 332
 333     fn add_def(&mut self, index: Local) {
 334         // If it was used already in the block, remove that use
 335         // now that we found a definition.
 336         //
 337         // Example:
 338         //
 339         //     // Defs = {X}, Uses = {}
 340         //     X = 5
 341         //     // Defs = {}, Uses = {X}
 342         //     use(X)
 343         if let Some(v_index) = self.map.from_local(index) {
 344             self.uses.remove(&v_index);
 345             self.defs.add(&v_index);
 346         }
 347     }
 348
 349     fn add_use(&mut self, index: Local) {
 350         // Inverse of above.
 351         //
 352         // Example:
 353         //
 354         //     // Defs = {}, Uses = {X}
 355         //     use(X)
 356         //     // Defs = {X}, Uses = {}
 357         //     X = 5
 358         //     // Defs = {}, Uses = {X}
 359         //     use(X)
 360         if let Some(v_index) = self.map.from_local(index) {
 361             self.defs.remove(&v_index);
 362             self.uses.add(&v_index);
 363         }
 364     }
 365 }
 366
 367 impl<'lv> DefsUsesVisitor<'lv>
 368 {
 369     /// Update `bits` with the effects of `value` and call `callback`. We
 370     /// should always visit in reverse order. This method assumes that we have
 371     /// not visited anything before; if you have, clear `bits` first.
 372     fn update_bits_and_do_callback<'tcx, OP>(&mut self, location: Location,
 373                                              value: &impl MirVisitable<'tcx>, bits: &mut LocalSet<Local>,
 374                                              callback: &mut OP)
 375     where
 376         OP: FnMut(Location, &LocalSet<Local>),
 377     {
 378         value.apply(location, self);
 379         self.defs_uses.apply(bits);
 380         callback(location, bits);
 381     }
 382 }
 383
 384 impl<'tcx, 'lv> Visitor<'tcx> for DefsUsesVisitor<'lv> {
 385     fn visit_local(&mut self, &local: &Local, context: PlaceContext<'tcx>, _: Location) {
 386         match categorize(context, self.mode) {
 387             Some(DefUse::Def) => {
 388                 self.defs_uses.add_def(local);
 389             }
 390
 391             Some(DefUse::Use) => {
 392                 self.defs_uses.add_use(local);
 393             }
 394
 395             None => {}
 396         }
 397     }
 398 }
 399
 400 fn block<'tcx, 'lv>(mode: LivenessMode, b: &BasicBlockData<'tcx>, locals: usize) -> DefsUses<'lv> {
 401     let mut visitor = DefsUsesVisitor {
 402         mode,
 403         defs_uses: DefsUses {
 404             defs: LocalSet::new_empty(locals),
 405             uses: LocalSet::new_empty(locals),
 406             map: &IdentityMap {},
 407         },
 408     };
 409
 410     let dummy_location = Location {
 411         block: BasicBlock::new(0),
 412         statement_index: 0,
 413     };
 414
 415     // Visit the various parts of the basic block in reverse. If we go
 416     // forward, the logic in `add_def` and `add_use` would be wrong.
 417     visitor.visit_terminator(BasicBlock::new(0), b.terminator(), dummy_location);
 418     for statement in b.statements.iter().rev() {
 419         visitor.visit_statement(BasicBlock::new(0), statement, dummy_location);
 420     }
 421
 422     visitor.defs_uses
 423 }
 424
 425 pub fn dump_mir<'a, 'tcx, V: Idx>(
 426     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 427     pass_name: &str,
 428     source: MirSource,
 429     mir: &Mir<'tcx>,
 430     result: &LivenessResult<Local>,
 431 ) {
 432     if !dump_enabled(tcx, pass_name, source) {
 433         return;
 434     }
 435     let node_path = item_path::with_forced_impl_filename_line(|| {
 436         // see notes on #41697 below
 437         tcx.item_path_str(source.def_id)
 438     });
 439     dump_matched_mir_node(tcx, pass_name, &node_path, source, mir, result);
 440 }
 441
 442 fn dump_matched_mir_node<'a, 'tcx, V: Idx>(
 443     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 444     pass_name: &str,
 445     node_path: &str,
 446     source: MirSource,
 447     mir: &Mir<'tcx>,
 448     result: &LivenessResult<V>,
 449 ) {
 450     let mut file_path = PathBuf::new();
 451     file_path.push(Path::new(&tcx.sess.opts.debugging_opts.dump_mir_dir));
 452     let item_id = tcx.hir.as_local_node_id(source.def_id).unwrap();
 453     let file_name = format!("rustc.node{}{}-liveness.mir", item_id, pass_name);
 454     file_path.push(&file_name);
 455     let _ = fs::File::create(&file_path).and_then(|mut file| {
 456         writeln!(file, "// MIR local liveness analysis for `{}`", node_path)?;
 457         writeln!(file, "// source = {:?}", source)?;
 458         writeln!(file, "// pass_name = {}", pass_name)?;
 459         writeln!(file, "")?;
 460         write_mir_fn(tcx, source, mir, &mut file, result)?;
 461         Ok(())
 462     });
 463 }
 464
 465 pub fn write_mir_fn<'a, 'tcx, V :Idx>(
 466     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 467     src: MirSource,
 468     mir: &Mir<'tcx>,
 469     w: &mut dyn Write,
 470     result: &LivenessResult<V>,
 471 ) -> io::Result<()> {
 472     write_mir_intro(tcx, src, mir, w)?;
 473     for block in mir.basic_blocks().indices() {
 474         let print = |w: &mut dyn Write, prefix, result: &IndexVec<BasicBlock, LocalSet<V>>| {
 475             let live: Vec<String> = mir.local_decls
 476                 .indices()
 477                 .filter(|i| result[block].contains(i))
 478                 .map(|i| format!("{:?}", i))
 479                 .collect();
 480             writeln!(w, "{} {{{}}}", prefix, live.join(", "))
 481         };
 482         write_basic_block(tcx, block, mir, &mut |_, _| Ok(()), w)?;
 483         print(w, "   ", &result.outs)?;
 484         if block.index() + 1 != mir.basic_blocks().len() {
 485             writeln!(w, "")?;
 486         }
 487     }
 488
 489     writeln!(w, "}}")?;
 490     Ok(())
 491 }