src/librustc_mir/util/liveness.rs

   1 //! Liveness analysis which computes liveness of MIR local variables at the boundary of basic
   2 //! blocks.
   3 //!
   4 //! This analysis considers references as being used only at the point of the
   5 //! borrow. This means that this does not track uses because of references that
   6 //! already exist:
   7 //!
   8 //! ```rust
   9 //! fn foo() {
  10 //!     x = 0;
  11 //!     // `x` is live here ...
  12 //!     GLOBAL = &x: *const u32;
  13 //!     // ... but not here, even while it can be accessed through `GLOBAL`.
  14 //!     foo();
  15 //!     x = 1;
  16 //!     // `x` is live again here, because it is assigned to `OTHER_GLOBAL`.
  17 //!     OTHER_GLOBAL = &x: *const u32;
  18 //!     // ...
  19 //! }
  20 //! ```
  21 //!
  22 //! This means that users of this analysis still have to check whether
  23 //! pre-existing references can be used to access the value (e.g., at movable
  24 //! generator yield points, all pre-existing references are invalidated, so this
  25 //! doesn't matter).
  26
  27 use rustc::mir::visit::{
  28     PlaceContext, Visitor, MutatingUseContext, NonMutatingUseContext, NonUseContext,
  29 };
  30 use rustc::mir::Local;
  31 use rustc::mir::*;
  32 use rustc::ty::{self, TyCtxt};
  33 use rustc_data_structures::bit_set::BitSet;
  34 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  35 use rustc_data_structures::work_queue::WorkQueue;
  36 use std::fs;
  37 use std::io::{self, Write};
  38 use std::path::{Path, PathBuf};
  39 use crate::transform::MirSource;
  40 use crate::util::pretty::{dump_enabled, write_basic_block, write_mir_intro};
  41
  42 pub type LiveVarSet = BitSet<Local>;
  43
  44 /// This gives the result of the liveness analysis at the boundary of
  45 /// basic blocks.
  46 ///
  47 /// The `V` type defines the set of variables that we computed
  48 /// liveness for. This is often `Local`, in which case we computed
  49 /// liveness for all variables -- but it can also be some other type,
  50 /// which indicates a subset of the variables within the graph.
  51 pub struct LivenessResult {
  52     /// Live variables on exit to each basic block. This is equal to
  53     /// the union of the `ins` for each successor.
  54     pub outs: IndexVec<BasicBlock, LiveVarSet>,
  55 }
  56
  57 /// Computes which local variables are live within the given function
  58 /// `mir`. The liveness mode `mode` determines what sorts of uses are
  59 /// considered to make a variable live (e.g., do drops count?).
  60 pub fn liveness_of_locals<'tcx>(
  61     mir: &Mir<'tcx>,
  62 ) -> LivenessResult {
  63     let num_live_vars = mir.local_decls.len();
  64
  65     let def_use: IndexVec<_, DefsUses> = mir
  66         .basic_blocks()
  67         .iter()
  68         .map(|b| block(b, num_live_vars))
  69         .collect();
  70
  71     let mut outs: IndexVec<_, LiveVarSet> = mir
  72         .basic_blocks()
  73         .indices()
  74         .map(|_| LiveVarSet::new_empty(num_live_vars))
  75         .collect();
  76
  77     let mut bits = LiveVarSet::new_empty(num_live_vars);
  78
  79     // queue of things that need to be re-processed, and a set containing
  80     // the things currently in the queue
  81     let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_all(mir.basic_blocks().len());
  82
  83     let predecessors = mir.predecessors();
  84
  85     while let Some(bb) = dirty_queue.pop() {
  86         // bits = use ∪ (bits - def)
  87         bits.overwrite(&outs[bb]);
  88         def_use[bb].apply(&mut bits);
  89
  90         // `bits` now contains the live variables on entry. Therefore,
  91         // add `bits` to the `out` set for each predecessor; if those
  92         // bits were not already present, then enqueue the predecessor
  93         // as dirty.
  94         //
  95         // (note that `union` returns true if the `self` set changed)
  96         for &pred_bb in &predecessors[bb] {
  97             if outs[pred_bb].union(&bits) {
  98                 dirty_queue.insert(pred_bb);
  99             }
 100         }
 101     }
 102
 103     LivenessResult { outs }
 104 }
 105
 106 #[derive(Eq, PartialEq, Clone)]
 107 pub enum DefUse {
 108     Def,
 109     Use,
 110     Drop,
 111 }
 112
 113 pub fn categorize<'tcx>(context: PlaceContext) -> Option<DefUse> {
 114     match context {
 115         ///////////////////////////////////////////////////////////////////////////
 116         // DEFS
 117
 118         PlaceContext::MutatingUse(MutatingUseContext::Store) |
 119
 120         // This is potentially both a def and a use...
 121         PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) |
 122
 123         // We let Call define the result in both the success and
 124         // unwind cases. This is not really correct, however it
 125         // does not seem to be observable due to the way that we
 126         // generate MIR. To do things properly, we would apply
 127         // the def in call only to the input from the success
 128         // path and not the unwind path. -nmatsakis
 129         PlaceContext::MutatingUse(MutatingUseContext::Call) |
 130
 131         // Storage live and storage dead aren't proper defines, but we can ignore
 132         // values that come before them.
 133         PlaceContext::NonUse(NonUseContext::StorageLive) |
 134         PlaceContext::NonUse(NonUseContext::StorageDead) => Some(DefUse::Def),
 135
 136         ///////////////////////////////////////////////////////////////////////////
 137         // REGULAR USES
 138         //
 139         // These are uses that occur *outside* of a drop. For the
 140         // purposes of NLL, these are special in that **all** the
 141         // lifetimes appearing in the variable must be live for each regular use.
 142
 143         PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) |
 144         PlaceContext::MutatingUse(MutatingUseContext::Projection) |
 145
 146         // Borrows only consider their local used at the point of the borrow.
 147         // This won't affect the results since we use this analysis for generators
 148         // and we only care about the result at suspension points. Borrows cannot
 149         // cross suspension points so this behavior is unproblematic.
 150         PlaceContext::MutatingUse(MutatingUseContext::Borrow) |
 151         PlaceContext::NonMutatingUse(NonMutatingUseContext::SharedBorrow) |
 152         PlaceContext::NonMutatingUse(NonMutatingUseContext::ShallowBorrow) |
 153         PlaceContext::NonMutatingUse(NonMutatingUseContext::UniqueBorrow) |
 154
 155         PlaceContext::NonMutatingUse(NonMutatingUseContext::Inspect) |
 156         PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
 157         PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) |
 158         PlaceContext::NonUse(NonUseContext::AscribeUserTy) |
 159         PlaceContext::MutatingUse(MutatingUseContext::Retag) =>
 160             Some(DefUse::Use),
 161
 162         ///////////////////////////////////////////////////////////////////////////
 163         // DROP USES
 164         //
 165         // These are uses that occur in a DROP (a MIR drop, not a
 166         // call to `std::mem::drop()`). For the purposes of NLL,
 167         // uses in drop are special because `#[may_dangle]`
 168         // attributes can affect whether lifetimes must be live.
 169
 170         PlaceContext::MutatingUse(MutatingUseContext::Drop) =>
 171             Some(DefUse::Drop),
 172     }
 173 }
 174
 175 struct DefsUsesVisitor
 176 {
 177     defs_uses: DefsUses,
 178 }
 179
 180 #[derive(Eq, PartialEq, Clone)]
 181 struct DefsUses {
 182     defs: LiveVarSet,
 183     uses: LiveVarSet,
 184 }
 185
 186 impl DefsUses {
 187     fn apply(&self, bits: &mut LiveVarSet) -> bool {
 188         bits.subtract(&self.defs) | bits.union(&self.uses)
 189     }
 190
 191     fn add_def(&mut self, index: Local) {
 192         // If it was used already in the block, remove that use
 193         // now that we found a definition.
 194         //
 195         // Example:
 196         //
 197         //     // Defs = {X}, Uses = {}
 198         //     X = 5
 199         //     // Defs = {}, Uses = {X}
 200         //     use(X)
 201         self.uses.remove(index);
 202         self.defs.insert(index);
 203     }
 204
 205     fn add_use(&mut self, index: Local) {
 206         // Inverse of above.
 207         //
 208         // Example:
 209         //
 210         //     // Defs = {}, Uses = {X}
 211         //     use(X)
 212         //     // Defs = {X}, Uses = {}
 213         //     X = 5
 214         //     // Defs = {}, Uses = {X}
 215         //     use(X)
 216         self.defs.remove(index);
 217         self.uses.insert(index);
 218     }
 219 }
 220
 221 impl<'tcx> Visitor<'tcx> for DefsUsesVisitor
 222 {
 223     fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) {
 224         match categorize(context) {
 225             Some(DefUse::Def) => self.defs_uses.add_def(local),
 226             Some(DefUse::Use) | Some(DefUse::Drop) => self.defs_uses.add_use(local),
 227             _ => (),
 228         }
 229     }
 230 }
 231
 232 fn block<'tcx>(
 233     b: &BasicBlockData<'tcx>,
 234     locals: usize,
 235 ) -> DefsUses {
 236     let mut visitor = DefsUsesVisitor {
 237         defs_uses: DefsUses {
 238             defs: LiveVarSet::new_empty(locals),
 239             uses: LiveVarSet::new_empty(locals),
 240         },
 241     };
 242
 243     let dummy_location = Location {
 244         block: BasicBlock::new(0),
 245         statement_index: 0,
 246     };
 247
 248     // Visit the various parts of the basic block in reverse. If we go
 249     // forward, the logic in `add_def` and `add_use` would be wrong.
 250     visitor.visit_terminator(b.terminator(), dummy_location);
 251     for statement in b.statements.iter().rev() {
 252         visitor.visit_statement(statement, dummy_location);
 253     }
 254
 255     visitor.defs_uses
 256 }
 257
 258 pub fn dump_mir<'a, 'tcx>(
 259     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 260     pass_name: &str,
 261     source: MirSource<'tcx>,
 262     mir: &Mir<'tcx>,
 263     result: &LivenessResult,
 264 ) {
 265     if !dump_enabled(tcx, pass_name, source) {
 266         return;
 267     }
 268     let node_path = ty::print::with_forced_impl_filename_line(|| {
 269         // see notes on #41697 below
 270         tcx.def_path_str(source.def_id())
 271     });
 272     dump_matched_mir_node(tcx, pass_name, &node_path, source, mir, result);
 273 }
 274
 275 fn dump_matched_mir_node<'a, 'tcx>(
 276     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 277     pass_name: &str,
 278     node_path: &str,
 279     source: MirSource<'tcx>,
 280     mir: &Mir<'tcx>,
 281     result: &LivenessResult,
 282 ) {
 283     let mut file_path = PathBuf::new();
 284     file_path.push(Path::new(&tcx.sess.opts.debugging_opts.dump_mir_dir));
 285     let item_id = tcx.hir().as_local_hir_id(source.def_id()).unwrap();
 286     let file_name = format!("rustc.node{}{}-liveness.mir", item_id, pass_name);
 287     file_path.push(&file_name);
 288     let _ = fs::File::create(&file_path).and_then(|mut file| {
 289         writeln!(file, "// MIR local liveness analysis for `{}`", node_path)?;
 290         writeln!(file, "// source = {:?}", source)?;
 291         writeln!(file, "// pass_name = {}", pass_name)?;
 292         writeln!(file, "")?;
 293         write_mir_fn(tcx, source, mir, &mut file, result)?;
 294         Ok(())
 295     });
 296 }
 297
 298 pub fn write_mir_fn<'a, 'tcx>(
 299     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 300     src: MirSource<'tcx>,
 301     mir: &Mir<'tcx>,
 302     w: &mut dyn Write,
 303     result: &LivenessResult,
 304 ) -> io::Result<()> {
 305     write_mir_intro(tcx, src, mir, w)?;
 306     for block in mir.basic_blocks().indices() {
 307         let print = |w: &mut dyn Write, prefix, result: &IndexVec<BasicBlock, LiveVarSet>| {
 308             let live: Vec<String> = result[block]
 309                 .iter()
 310                 .map(|local| format!("{:?}", local))
 311                 .collect();
 312             writeln!(w, "{} {{{}}}", prefix, live.join(", "))
 313         };
 314         write_basic_block(tcx, block, mir, &mut |_, _| Ok(()), w)?;
 315         print(w, "   ", &result.outs)?;
 316         if block.index() + 1 != mir.basic_blocks().len() {
 317             writeln!(w, "")?;
 318         }
 319     }
 320
 321     writeln!(w, "}}")?;
 322     Ok(())
 323 }