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::visit::{
  37     PlaceContext, Visitor, MutatingUseContext, NonMutatingUseContext, NonUseContext,
  38 };
  39 use rustc::mir::Local;
  40 use rustc::mir::*;
  41 use rustc::ty::{item_path, TyCtxt};
  42 use rustc_data_structures::bit_set::BitSet;
  43 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  44 use rustc_data_structures::work_queue::WorkQueue;
  45 use std::fs;
  46 use std::io::{self, Write};
  47 use std::path::{Path, PathBuf};
  48 use transform::MirSource;
  49 use util::pretty::{dump_enabled, write_basic_block, write_mir_intro};
  50
  51 pub type LiveVarSet<V> = BitSet<V>;
  52
  53 /// This gives the result of the liveness analysis at the boundary of
  54 /// basic blocks.
  55 ///
  56 /// The `V` type defines the set of variables that we computed
  57 /// liveness for. This is often `Local`, in which case we computed
  58 /// liveness for all variables -- but it can also be some other type,
  59 /// which indicates a subset of the variables within the graph.
  60 pub struct LivenessResult<V: Idx> {
  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, LiveVarSet<V>>,
  64 }
  65
  66 /// Defines the mapping to/from the MIR local variables (`Local`) to
  67 /// the "live variable indices" we are using in a particular
  68 /// computation.
  69 pub trait LiveVariableMap {
  70     type LiveVar;
  71
  72     fn from_local(&self, local: Local) -> Option<Self::LiveVar>;
  73     fn from_live_var(&self, local: Self::LiveVar) -> Local;
  74     fn num_variables(&self) -> usize;
  75 }
  76
  77 #[derive(Debug)]
  78 pub struct IdentityMap<'a, 'tcx: 'a> {
  79     mir: &'a Mir<'tcx>,
  80 }
  81
  82 impl<'a, 'tcx> IdentityMap<'a, 'tcx> {
  83     pub fn new(mir: &'a Mir<'tcx>) -> Self {
  84         Self { mir }
  85     }
  86 }
  87
  88 impl<'a, 'tcx> LiveVariableMap for IdentityMap<'a, 'tcx> {
  89     type LiveVar = Local;
  90
  91     fn from_local(&self, local: Local) -> Option<Self::LiveVar> {
  92         Some(local)
  93     }
  94
  95     fn from_live_var(&self, local: Self::LiveVar) -> Local {
  96         local
  97     }
  98
  99     fn num_variables(&self) -> usize {
 100         self.mir.local_decls.len()
 101     }
 102 }
 103
 104 /// Compute which local variables are live within the given function
 105 /// `mir`. The liveness mode `mode` determines what sorts of uses are
 106 /// considered to make a variable live (e.g., do drops count?).
 107 pub fn liveness_of_locals<'tcx, V: Idx>(
 108     mir: &Mir<'tcx>,
 109     map: &impl LiveVariableMap<LiveVar = V>,
 110 ) -> LivenessResult<V> {
 111     let num_live_vars = map.num_variables();
 112
 113     let def_use: IndexVec<_, DefsUses<V>> = mir
 114         .basic_blocks()
 115         .iter()
 116         .map(|b| block(map, b, num_live_vars))
 117         .collect();
 118
 119     let mut outs: IndexVec<_, LiveVarSet<V>> = mir
 120         .basic_blocks()
 121         .indices()
 122         .map(|_| LiveVarSet::new_empty(num_live_vars))
 123         .collect();
 124
 125     let mut bits = LiveVarSet::new_empty(num_live_vars);
 126
 127     // queue of things that need to be re-processed, and a set containing
 128     // the things currently in the queue
 129     let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_all(mir.basic_blocks().len());
 130
 131     let predecessors = mir.predecessors();
 132
 133     while let Some(bb) = dirty_queue.pop() {
 134         // bits = use ∪ (bits - def)
 135         bits.overwrite(&outs[bb]);
 136         def_use[bb].apply(&mut bits);
 137
 138         // `bits` now contains the live variables on entry. Therefore,
 139         // add `bits` to the `out` set for each predecessor; if those
 140         // bits were not already present, then enqueue the predecessor
 141         // as dirty.
 142         //
 143         // (note that `union` returns true if the `self` set changed)
 144         for &pred_bb in &predecessors[bb] {
 145             if outs[pred_bb].union(&bits) {
 146                 dirty_queue.insert(pred_bb);
 147             }
 148         }
 149     }
 150
 151     LivenessResult { outs }
 152 }
 153
 154 #[derive(Eq, PartialEq, Clone)]
 155 pub enum DefUse {
 156     Def,
 157     Use,
 158     Drop,
 159 }
 160
 161 pub fn categorize<'tcx>(context: PlaceContext<'tcx>) -> Option<DefUse> {
 162     match context {
 163         ///////////////////////////////////////////////////////////////////////////
 164         // DEFS
 165
 166         PlaceContext::MutatingUse(MutatingUseContext::Store) |
 167
 168         // This is potentially both a def and a use...
 169         PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) |
 170
 171         // We let Call define the result in both the success and
 172         // unwind cases. This is not really correct, however it
 173         // does not seem to be observable due to the way that we
 174         // generate MIR. To do things properly, we would apply
 175         // the def in call only to the input from the success
 176         // path and not the unwind path. -nmatsakis
 177         PlaceContext::MutatingUse(MutatingUseContext::Call) |
 178
 179         // Storage live and storage dead aren't proper defines, but we can ignore
 180         // values that come before them.
 181         PlaceContext::NonUse(NonUseContext::StorageLive) |
 182         PlaceContext::NonUse(NonUseContext::StorageDead) => Some(DefUse::Def),
 183
 184         ///////////////////////////////////////////////////////////////////////////
 185         // REGULAR USES
 186         //
 187         // These are uses that occur *outside* of a drop. For the
 188         // purposes of NLL, these are special in that **all** the
 189         // lifetimes appearing in the variable must be live for each regular use.
 190
 191         PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) |
 192         PlaceContext::MutatingUse(MutatingUseContext::Projection) |
 193
 194         // Borrows only consider their local used at the point of the borrow.
 195         // This won't affect the results since we use this analysis for generators
 196         // and we only care about the result at suspension points. Borrows cannot
 197         // cross suspension points so this behavior is unproblematic.
 198         PlaceContext::MutatingUse(MutatingUseContext::Borrow(..)) |
 199         PlaceContext::NonMutatingUse(NonMutatingUseContext::SharedBorrow(..)) |
 200         PlaceContext::NonMutatingUse(NonMutatingUseContext::ShallowBorrow(..)) |
 201         PlaceContext::NonMutatingUse(NonMutatingUseContext::UniqueBorrow(..)) |
 202
 203         PlaceContext::NonMutatingUse(NonMutatingUseContext::Inspect) |
 204         PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
 205         PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) |
 206         PlaceContext::NonUse(NonUseContext::AscribeUserTy) |
 207         PlaceContext::MutatingUse(MutatingUseContext::Retag) =>
 208             Some(DefUse::Use),
 209
 210         ///////////////////////////////////////////////////////////////////////////
 211         // DROP USES
 212         //
 213         // These are uses that occur in a DROP (a MIR drop, not a
 214         // call to `std::mem::drop()`). For the purposes of NLL,
 215         // uses in drop are special because `#[may_dangle]`
 216         // attributes can affect whether lifetimes must be live.
 217
 218         PlaceContext::MutatingUse(MutatingUseContext::Drop) =>
 219             Some(DefUse::Drop),
 220     }
 221 }
 222
 223 struct DefsUsesVisitor<'lv, V, M>
 224 where
 225     V: Idx,
 226     M: LiveVariableMap<LiveVar = V> + 'lv,
 227 {
 228     map: &'lv M,
 229     defs_uses: DefsUses<V>,
 230 }
 231
 232 #[derive(Eq, PartialEq, Clone)]
 233 struct DefsUses<V: Idx> {
 234     defs: LiveVarSet<V>,
 235     uses: LiveVarSet<V>,
 236 }
 237
 238 impl<V: Idx> DefsUses<V> {
 239     fn apply(&self, bits: &mut LiveVarSet<V>) -> bool {
 240         bits.subtract(&self.defs) | bits.union(&self.uses)
 241     }
 242
 243     fn add_def(&mut self, index: V) {
 244         // If it was used already in the block, remove that use
 245         // now that we found a definition.
 246         //
 247         // Example:
 248         //
 249         //     // Defs = {X}, Uses = {}
 250         //     X = 5
 251         //     // Defs = {}, Uses = {X}
 252         //     use(X)
 253         self.uses.remove(index);
 254         self.defs.insert(index);
 255     }
 256
 257     fn add_use(&mut self, index: V) {
 258         // Inverse of above.
 259         //
 260         // Example:
 261         //
 262         //     // Defs = {}, Uses = {X}
 263         //     use(X)
 264         //     // Defs = {X}, Uses = {}
 265         //     X = 5
 266         //     // Defs = {}, Uses = {X}
 267         //     use(X)
 268         self.defs.remove(index);
 269         self.uses.insert(index);
 270     }
 271 }
 272
 273 impl<'tcx, 'lv, V, M> Visitor<'tcx> for DefsUsesVisitor<'lv, V, M>
 274 where
 275     V: Idx,
 276     M: LiveVariableMap<LiveVar = V>,
 277 {
 278     fn visit_local(&mut self, &local: &Local, context: PlaceContext<'tcx>, _: Location) {
 279         if let Some(v_index) = self.map.from_local(local) {
 280             match categorize(context) {
 281                 Some(DefUse::Def) => self.defs_uses.add_def(v_index),
 282                 Some(DefUse::Use) | Some(DefUse::Drop) => self.defs_uses.add_use(v_index),
 283                 _ => (),
 284             }
 285         }
 286     }
 287 }
 288
 289 fn block<'tcx, V: Idx>(
 290     map: &impl LiveVariableMap<LiveVar = V>,
 291     b: &BasicBlockData<'tcx>,
 292     locals: usize,
 293 ) -> DefsUses<V> {
 294     let mut visitor = DefsUsesVisitor {
 295         map,
 296         defs_uses: DefsUses {
 297             defs: LiveVarSet::new_empty(locals),
 298             uses: LiveVarSet::new_empty(locals),
 299         },
 300     };
 301
 302     let dummy_location = Location {
 303         block: BasicBlock::new(0),
 304         statement_index: 0,
 305     };
 306
 307     // Visit the various parts of the basic block in reverse. If we go
 308     // forward, the logic in `add_def` and `add_use` would be wrong.
 309     visitor.visit_terminator(BasicBlock::new(0), b.terminator(), dummy_location);
 310     for statement in b.statements.iter().rev() {
 311         visitor.visit_statement(BasicBlock::new(0), statement, dummy_location);
 312     }
 313
 314     visitor.defs_uses
 315 }
 316
 317 pub fn dump_mir<'a, 'tcx, V: Idx>(
 318     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 319     pass_name: &str,
 320     source: MirSource,
 321     mir: &Mir<'tcx>,
 322     map: &impl LiveVariableMap<LiveVar = V>,
 323     result: &LivenessResult<V>,
 324 ) {
 325     if !dump_enabled(tcx, pass_name, source) {
 326         return;
 327     }
 328     let node_path = item_path::with_forced_impl_filename_line(|| {
 329         // see notes on #41697 below
 330         tcx.item_path_str(source.def_id)
 331     });
 332     dump_matched_mir_node(tcx, pass_name, &node_path, source, mir, map, result);
 333 }
 334
 335 fn dump_matched_mir_node<'a, 'tcx, V: Idx>(
 336     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 337     pass_name: &str,
 338     node_path: &str,
 339     source: MirSource,
 340     mir: &Mir<'tcx>,
 341     map: &dyn LiveVariableMap<LiveVar = V>,
 342     result: &LivenessResult<V>,
 343 ) {
 344     let mut file_path = PathBuf::new();
 345     file_path.push(Path::new(&tcx.sess.opts.debugging_opts.dump_mir_dir));
 346     let item_id = tcx.hir().as_local_node_id(source.def_id).unwrap();
 347     let file_name = format!("rustc.node{}{}-liveness.mir", item_id, pass_name);
 348     file_path.push(&file_name);
 349     let _ = fs::File::create(&file_path).and_then(|mut file| {
 350         writeln!(file, "// MIR local liveness analysis for `{}`", node_path)?;
 351         writeln!(file, "// source = {:?}", source)?;
 352         writeln!(file, "// pass_name = {}", pass_name)?;
 353         writeln!(file, "")?;
 354         write_mir_fn(tcx, source, mir, map, &mut file, result)?;
 355         Ok(())
 356     });
 357 }
 358
 359 pub fn write_mir_fn<'a, 'tcx, V: Idx>(
 360     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 361     src: MirSource,
 362     mir: &Mir<'tcx>,
 363     map: &dyn LiveVariableMap<LiveVar = V>,
 364     w: &mut dyn Write,
 365     result: &LivenessResult<V>,
 366 ) -> io::Result<()> {
 367     write_mir_intro(tcx, src, mir, w)?;
 368     for block in mir.basic_blocks().indices() {
 369         let print = |w: &mut dyn Write, prefix, result: &IndexVec<BasicBlock, LiveVarSet<V>>| {
 370             let live: Vec<String> = result[block]
 371                 .iter()
 372                 .map(|v| map.from_live_var(v))
 373                 .map(|local| format!("{:?}", local))
 374                 .collect();
 375             writeln!(w, "{} {{{}}}", prefix, live.join(", "))
 376         };
 377         write_basic_block(tcx, block, mir, &mut |_, _| Ok(()), w)?;
 378         print(w, "   ", &result.outs)?;
 379         if block.index() + 1 != mir.basic_blocks().len() {
 380             writeln!(w, "")?;
 381         }
 382     }
 383
 384     writeln!(w, "}}")?;
 385     Ok(())
 386 }