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