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 crate::transform::MirSource;
  28 use crate::util::pretty::{dump_enabled, write_basic_block, write_mir_intro};
  29 use rustc::mir::visit::{
  30     MutatingUseContext, NonMutatingUseContext, NonUseContext, PlaceContext, Visitor,
  31 };
  32 use rustc::mir::Local;
  33 use rustc::mir::*;
  34 use rustc::ty::{self, TyCtxt};
  35 use rustc_data_structures::work_queue::WorkQueue;
  36 use rustc_index::bit_set::BitSet;
  37 use rustc_index::vec::{Idx, IndexVec};
  38 use std::fs;
  39 use std::io::{self, BufWriter, Write};
  40 use std::path::{Path, PathBuf};
  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`, including drops.
  59 pub fn liveness_of_locals(body: ReadOnlyBodyAndCache<'_, '_>) -> LivenessResult {
  60     let num_live_vars = body.local_decls.len();
  61
  62     let def_use: IndexVec<_, DefsUses> =
  63         body.basic_blocks().iter().map(|b| block(b, num_live_vars)).collect();
  64
  65     let mut outs: IndexVec<_, LiveVarSet> =
  66         body.basic_blocks().indices().map(|_| LiveVarSet::new_empty(num_live_vars)).collect();
  67
  68     let mut bits = LiveVarSet::new_empty(num_live_vars);
  69
  70     // The dirty queue contains the set of basic blocks whose entry sets have changed since they
  71     // were last processed. At the start of the analysis, we initialize the queue in post-order to
  72     // make it more likely that the entry set for a given basic block will have the effects of all
  73     // its successors in the CFG applied before it is processed.
  74     //
  75     // FIXME(ecstaticmorse): Reverse post-order on the reverse CFG may generate a better iteration
  76     // order when cycles are present, but the overhead of computing the reverse CFG may outweigh
  77     // any benefits. Benchmark this and find out.
  78     let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks().len());
  79     for (bb, _) in traversal::postorder(&body) {
  80         dirty_queue.insert(bb);
  81     }
  82
  83     // Add blocks which are not reachable from START_BLOCK to the work queue. These blocks will
  84     // be processed after the ones added above.
  85     for bb in body.basic_blocks().indices() {
  86         dirty_queue.insert(bb);
  87     }
  88
  89     let predecessors = body.predecessors();
  90
  91     while let Some(bb) = dirty_queue.pop() {
  92         // bits = use ∪ (bits - def)
  93         bits.overwrite(&outs[bb]);
  94         def_use[bb].apply(&mut bits);
  95
  96         // `bits` now contains the live variables on entry. Therefore,
  97         // add `bits` to the `out` set for each predecessor; if those
  98         // bits were not already present, then enqueue the predecessor
  99         // as dirty.
 100         //
 101         // (note that `union` returns true if the `self` set changed)
 102         for &pred_bb in &predecessors[bb] {
 103             if outs[pred_bb].union(&bits) {
 104                 dirty_queue.insert(pred_bb);
 105             }
 106         }
 107     }
 108
 109     LivenessResult { outs }
 110 }
 111
 112 #[derive(Eq, PartialEq, Clone)]
 113 pub enum DefUse {
 114     Def,
 115     Use,
 116     Drop,
 117 }
 118
 119 pub fn categorize(context: PlaceContext) -> Option<DefUse> {
 120     match context {
 121         ///////////////////////////////////////////////////////////////////////////
 122         // DEFS
 123
 124         PlaceContext::MutatingUse(MutatingUseContext::Store) |
 125
 126         // This is potentially both a def and a use...
 127         PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) |
 128
 129         // We let Call define the result in both the success and
 130         // unwind cases. This is not really correct, however it
 131         // does not seem to be observable due to the way that we
 132         // generate MIR. To do things properly, we would apply
 133         // the def in call only to the input from the success
 134         // path and not the unwind path. -nmatsakis
 135         PlaceContext::MutatingUse(MutatingUseContext::Call) |
 136
 137         // Storage live and storage dead aren't proper defines, but we can ignore
 138         // values that come before them.
 139         PlaceContext::NonUse(NonUseContext::StorageLive) |
 140         PlaceContext::NonUse(NonUseContext::StorageDead) => Some(DefUse::Def),
 141
 142         ///////////////////////////////////////////////////////////////////////////
 143         // REGULAR USES
 144         //
 145         // These are uses that occur *outside* of a drop. For the
 146         // purposes of NLL, these are special in that **all** the
 147         // lifetimes appearing in the variable must be live for each regular use.
 148
 149         PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) |
 150         PlaceContext::MutatingUse(MutatingUseContext::Projection) |
 151
 152         // Borrows only consider their local used at the point of the borrow.
 153         // This won't affect the results since we use this analysis for generators
 154         // and we only care about the result at suspension points. Borrows cannot
 155         // cross suspension points so this behavior is unproblematic.
 156         PlaceContext::MutatingUse(MutatingUseContext::Borrow) |
 157         PlaceContext::NonMutatingUse(NonMutatingUseContext::SharedBorrow) |
 158         PlaceContext::NonMutatingUse(NonMutatingUseContext::ShallowBorrow) |
 159         PlaceContext::NonMutatingUse(NonMutatingUseContext::UniqueBorrow) |
 160
 161         PlaceContext::MutatingUse(MutatingUseContext::AddressOf) |
 162         PlaceContext::NonMutatingUse(NonMutatingUseContext::AddressOf) |
 163         PlaceContext::NonMutatingUse(NonMutatingUseContext::Inspect) |
 164         PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
 165         PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) |
 166         PlaceContext::NonUse(NonUseContext::AscribeUserTy) |
 167         PlaceContext::MutatingUse(MutatingUseContext::Retag) =>
 168             Some(DefUse::Use),
 169
 170         ///////////////////////////////////////////////////////////////////////////
 171         // DROP USES
 172         //
 173         // These are uses that occur in a DROP (a MIR drop, not a
 174         // call to `std::mem::drop()`). For the purposes of NLL,
 175         // uses in drop are special because `#[may_dangle]`
 176         // attributes can affect whether lifetimes must be live.
 177
 178         PlaceContext::MutatingUse(MutatingUseContext::Drop) =>
 179             Some(DefUse::Drop),
 180
 181         // Debug info is neither def nor use.
 182         PlaceContext::NonUse(NonUseContext::VarDebugInfo) => None,
 183     }
 184 }
 185
 186 struct DefsUsesVisitor {
 187     defs_uses: DefsUses,
 188 }
 189
 190 #[derive(Eq, PartialEq, Clone)]
 191 struct DefsUses {
 192     defs: LiveVarSet,
 193     uses: LiveVarSet,
 194 }
 195
 196 impl DefsUses {
 197     fn apply(&self, bits: &mut LiveVarSet) -> bool {
 198         bits.subtract(&self.defs) | bits.union(&self.uses)
 199     }
 200
 201     fn add_def(&mut self, index: Local) {
 202         // If it was used already in the block, remove that use
 203         // now that we found a definition.
 204         //
 205         // Example:
 206         //
 207         //     // Defs = {X}, Uses = {}
 208         //     X = 5
 209         //     // Defs = {}, Uses = {X}
 210         //     use(X)
 211         self.uses.remove(index);
 212         self.defs.insert(index);
 213     }
 214
 215     fn add_use(&mut self, index: Local) {
 216         // Inverse of above.
 217         //
 218         // Example:
 219         //
 220         //     // Defs = {}, Uses = {X}
 221         //     use(X)
 222         //     // Defs = {X}, Uses = {}
 223         //     X = 5
 224         //     // Defs = {}, Uses = {X}
 225         //     use(X)
 226         self.defs.remove(index);
 227         self.uses.insert(index);
 228     }
 229 }
 230
 231 impl<'tcx> Visitor<'tcx> for DefsUsesVisitor {
 232     fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) {
 233         match categorize(context) {
 234             Some(DefUse::Def) => self.defs_uses.add_def(local),
 235             Some(DefUse::Use) | Some(DefUse::Drop) => self.defs_uses.add_use(local),
 236             _ => (),
 237         }
 238     }
 239 }
 240
 241 fn block(b: &BasicBlockData<'_>, locals: usize) -> DefsUses {
 242     let mut visitor = DefsUsesVisitor {
 243         defs_uses: DefsUses {
 244             defs: LiveVarSet::new_empty(locals),
 245             uses: LiveVarSet::new_empty(locals),
 246         },
 247     };
 248
 249     let dummy_location = Location { block: BasicBlock::new(0), statement_index: 0 };
 250
 251     // Visit the various parts of the basic block in reverse. If we go
 252     // forward, the logic in `add_def` and `add_use` would be wrong.
 253     visitor.visit_terminator(b.terminator(), dummy_location);
 254     for statement in b.statements.iter().rev() {
 255         visitor.visit_statement(statement, dummy_location);
 256     }
 257
 258     visitor.defs_uses
 259 }
 260
 261 pub fn dump_mir<'tcx>(
 262     tcx: TyCtxt<'tcx>,
 263     pass_name: &str,
 264     source: MirSource<'tcx>,
 265     body: &Body<'tcx>,
 266     result: &LivenessResult,
 267 ) {
 268     if !dump_enabled(tcx, pass_name, source) {
 269         return;
 270     }
 271     let node_path = ty::print::with_forced_impl_filename_line(|| {
 272         // see notes on #41697 below
 273         tcx.def_path_str(source.def_id())
 274     });
 275     dump_matched_mir_node(tcx, pass_name, &node_path, source, body, result);
 276 }
 277
 278 fn dump_matched_mir_node<'tcx>(
 279     tcx: TyCtxt<'tcx>,
 280     pass_name: &str,
 281     node_path: &str,
 282     source: MirSource<'tcx>,
 283     body: &Body<'tcx>,
 284     result: &LivenessResult,
 285 ) {
 286     let mut file_path = PathBuf::new();
 287     file_path.push(Path::new(&tcx.sess.opts.debugging_opts.dump_mir_dir));
 288     let item_id = tcx.hir().as_local_hir_id(source.def_id()).unwrap();
 289     let file_name = format!("rustc.node{}{}-liveness.mir", item_id, pass_name);
 290     file_path.push(&file_name);
 291     let _ = fs::File::create(&file_path).and_then(|file| {
 292         let mut file = BufWriter::new(file);
 293         writeln!(file, "// MIR local liveness analysis for `{}`", node_path)?;
 294         writeln!(file, "// source = {:?}", source)?;
 295         writeln!(file, "// pass_name = {}", pass_name)?;
 296         writeln!(file, "")?;
 297         write_mir_fn(tcx, source, body, &mut file, result)?;
 298         Ok(())
 299     });
 300 }
 301
 302 pub fn write_mir_fn<'tcx>(
 303     tcx: TyCtxt<'tcx>,
 304     src: MirSource<'tcx>,
 305     body: &Body<'tcx>,
 306     w: &mut dyn Write,
 307     result: &LivenessResult,
 308 ) -> io::Result<()> {
 309     write_mir_intro(tcx, src, body, w)?;
 310     for block in body.basic_blocks().indices() {
 311         let print = |w: &mut dyn Write, prefix, result: &IndexVec<BasicBlock, LiveVarSet>| {
 312             let live: Vec<String> =
 313                 result[block].iter().map(|local| format!("{:?}", local)).collect();
 314             writeln!(w, "{} {{{}}}", prefix, live.join(", "))
 315         };
 316         write_basic_block(tcx, block, body, &mut |_, _| Ok(()), w)?;
 317         print(w, "   ", &result.outs)?;
 318         if block.index() + 1 != body.basic_blocks().len() {
 319             writeln!(w, "")?;
 320         }
 321     }
 322
 323     writeln!(w, "}}")?;
 324     Ok(())
 325 }