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