1 //! Liveness analysis which computes liveness of MIR local variables at the boundary of basic
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
11 //! // `x` is live here ...
12 //! GLOBAL = &x: *const u32;
13 //! // ... but not here, even while it can be accessed through `GLOBAL`.
16 //! // `x` is live again here, because it is assigned to `OTHER_GLOBAL`.
17 //! OTHER_GLOBAL = &x: *const u32;
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
27 use crate::transform::MirSource;
28 use crate::util::pretty::{dump_enabled, write_basic_block, write_mir_intro};
29 use rustc_data_structures::work_queue::WorkQueue;
30 use rustc_index::bit_set::BitSet;
31 use rustc_index::vec::{Idx, IndexVec};
32 use rustc_middle::mir::visit::{
33 MutatingUseContext, NonMutatingUseContext, NonUseContext, PlaceContext, Visitor,
35 use rustc_middle::mir::Local;
36 use rustc_middle::mir::*;
37 use rustc_middle::ty::{self, TyCtxt};
39 use std::io::{self, BufWriter, Write};
40 use std::path::{Path, PathBuf};
42 pub type LiveVarSet = BitSet<Local>;
44 /// This gives the result of the liveness analysis at the boundary of
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>,
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();
62 let def_use: IndexVec<_, DefsUses> =
63 body.basic_blocks().iter().map(|b| block(b, num_live_vars)).collect();
65 let mut outs: IndexVec<_, LiveVarSet> =
66 body.basic_blocks().indices().map(|_| LiveVarSet::new_empty(num_live_vars)).collect();
68 let mut bits = LiveVarSet::new_empty(num_live_vars);
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.
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);
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);
89 let predecessors = body.predecessors();
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);
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
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);
109 LivenessResult { outs }
112 #[derive(Eq, PartialEq, Clone)]
119 pub fn categorize(context: PlaceContext) -> Option<DefUse> {
121 ///////////////////////////////////////////////////////////////////////////
124 PlaceContext::MutatingUse(MutatingUseContext::Store) |
126 // This is potentially both a def and a use...
127 PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) |
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) |
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),
142 ///////////////////////////////////////////////////////////////////////////
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.
149 PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) |
150 PlaceContext::MutatingUse(MutatingUseContext::Projection) |
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) |
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) =>
170 ///////////////////////////////////////////////////////////////////////////
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.
178 PlaceContext::MutatingUse(MutatingUseContext::Drop) =>
181 // Debug info is neither def nor use.
182 PlaceContext::NonUse(NonUseContext::VarDebugInfo) => None,
186 struct DefsUsesVisitor {
190 #[derive(Eq, PartialEq, Clone)]
197 fn apply(&self, bits: &mut LiveVarSet) -> bool {
198 bits.subtract(&self.defs) | bits.union(&self.uses)
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.
207 // // Defs = {X}, Uses = {}
209 // // Defs = {}, Uses = {X}
211 self.uses.remove(index);
212 self.defs.insert(index);
215 fn add_use(&mut self, index: Local) {
220 // // Defs = {}, Uses = {X}
222 // // Defs = {X}, Uses = {}
224 // // Defs = {}, Uses = {X}
226 self.defs.remove(index);
227 self.uses.insert(index);
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 | DefUse::Drop) => self.defs_uses.add_use(local),
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),
249 let dummy_location = Location { block: BasicBlock::new(0), statement_index: 0 };
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);
261 pub fn dump_mir<'tcx>(
264 source: MirSource<'tcx>,
266 result: &LivenessResult,
268 if !dump_enabled(tcx, pass_name, source.def_id()) {
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())
275 dump_matched_mir_node(tcx, pass_name, &node_path, source, body, result);
278 fn dump_matched_mir_node<'tcx>(
282 source: MirSource<'tcx>,
284 result: &LivenessResult,
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)?;
297 write_mir_fn(tcx, source, body, &mut file, result)?;
302 pub fn write_mir_fn<'tcx>(
304 src: MirSource<'tcx>,
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(", "))
316 write_basic_block(tcx, block, body, &mut |_, _| Ok(()), w)?;
317 print(w, " ", &result.outs)?;
318 if block.index() + 1 != body.basic_blocks().len() {