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 rustc
::mir
::visit
::{
28 PlaceContext
, Visitor
, MutatingUseContext
, NonMutatingUseContext
, NonUseContext
,
30 use rustc
::mir
::Local
;
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
;
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}
;
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(
62 let num_live_vars
= body
.local_decls
.len();
64 let def_use
: IndexVec
<_
, DefsUses
> = body
67 .map(|b
| block(b
, num_live_vars
))
70 let mut outs
: IndexVec
<_
, LiveVarSet
> = body
73 .map(|_
| LiveVarSet
::new_empty(num_live_vars
))
76 let mut bits
= LiveVarSet
::new_empty(num_live_vars
);
78 // The dirty queue contains the set of basic blocks whose entry sets have changed since they
79 // were last processed. At the start of the analysis, we initialize the queue in post-order to
80 // make it more likely that the entry set for a given basic block will have the effects of all
81 // its successors in the CFG applied before it is processed.
83 // FIXME(ecstaticmorse): Reverse post-order on the reverse CFG may generate a better iteration
84 // order when cycles are present, but the overhead of computing the reverse CFG may outweigh
85 // any benefits. Benchmark this and find out.
86 let mut dirty_queue
: WorkQueue
<BasicBlock
> = WorkQueue
::with_none(body
.basic_blocks().len());
87 for (bb
, _
) in traversal
::postorder(body
) {
88 dirty_queue
.insert(bb
);
91 // Add blocks which are not reachable from START_BLOCK to the work queue. These blocks will
92 // be processed after the ones added above.
93 for bb
in body
.basic_blocks().indices() {
94 dirty_queue
.insert(bb
);
97 let predecessors
= body
.predecessors();
99 while let Some(bb
) = dirty_queue
.pop() {
100 // bits = use ∪ (bits - def)
101 bits
.overwrite(&outs
[bb
]);
102 def_use
[bb
].apply(&mut bits
);
104 // `bits` now contains the live variables on entry. Therefore,
105 // add `bits` to the `out` set for each predecessor; if those
106 // bits were not already present, then enqueue the predecessor
109 // (note that `union` returns true if the `self` set changed)
110 for &pred_bb
in &predecessors
[bb
] {
111 if outs
[pred_bb
].union(&bits
) {
112 dirty_queue
.insert(pred_bb
);
117 LivenessResult { outs }
120 #[derive(Eq, PartialEq, Clone)]
127 pub fn categorize(context
: PlaceContext
) -> Option
<DefUse
> {
129 ///////////////////////////////////////////////////////////////////////////
132 PlaceContext
::MutatingUse(MutatingUseContext
::Store
) |
134 // This is potentially both a def and a use...
135 PlaceContext
::MutatingUse(MutatingUseContext
::AsmOutput
) |
137 // We let Call define the result in both the success and
138 // unwind cases. This is not really correct, however it
139 // does not seem to be observable due to the way that we
140 // generate MIR. To do things properly, we would apply
141 // the def in call only to the input from the success
142 // path and not the unwind path. -nmatsakis
143 PlaceContext
::MutatingUse(MutatingUseContext
::Call
) |
145 // Storage live and storage dead aren't proper defines, but we can ignore
146 // values that come before them.
147 PlaceContext
::NonUse(NonUseContext
::StorageLive
) |
148 PlaceContext
::NonUse(NonUseContext
::StorageDead
) => Some(DefUse
::Def
),
150 ///////////////////////////////////////////////////////////////////////////
153 // These are uses that occur *outside* of a drop. For the
154 // purposes of NLL, these are special in that **all** the
155 // lifetimes appearing in the variable must be live for each regular use.
157 PlaceContext
::NonMutatingUse(NonMutatingUseContext
::Projection
) |
158 PlaceContext
::MutatingUse(MutatingUseContext
::Projection
) |
160 // Borrows only consider their local used at the point of the borrow.
161 // This won't affect the results since we use this analysis for generators
162 // and we only care about the result at suspension points. Borrows cannot
163 // cross suspension points so this behavior is unproblematic.
164 PlaceContext
::MutatingUse(MutatingUseContext
::Borrow
) |
165 PlaceContext
::NonMutatingUse(NonMutatingUseContext
::SharedBorrow
) |
166 PlaceContext
::NonMutatingUse(NonMutatingUseContext
::ShallowBorrow
) |
167 PlaceContext
::NonMutatingUse(NonMutatingUseContext
::UniqueBorrow
) |
169 PlaceContext
::NonMutatingUse(NonMutatingUseContext
::Inspect
) |
170 PlaceContext
::NonMutatingUse(NonMutatingUseContext
::Copy
) |
171 PlaceContext
::NonMutatingUse(NonMutatingUseContext
::Move
) |
172 PlaceContext
::NonUse(NonUseContext
::AscribeUserTy
) |
173 PlaceContext
::MutatingUse(MutatingUseContext
::Retag
) =>
176 ///////////////////////////////////////////////////////////////////////////
179 // These are uses that occur in a DROP (a MIR drop, not a
180 // call to `std::mem::drop()`). For the purposes of NLL,
181 // uses in drop are special because `#[may_dangle]`
182 // attributes can affect whether lifetimes must be live.
184 PlaceContext
::MutatingUse(MutatingUseContext
::Drop
) =>
189 struct DefsUsesVisitor
194 #[derive(Eq, PartialEq, Clone)]
201 fn apply(&self, bits
: &mut LiveVarSet
) -> bool
{
202 bits
.subtract(&self.defs
) | bits
.union(&self.uses
)
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.
211 // // Defs = {X}, Uses = {}
213 // // Defs = {}, Uses = {X}
215 self.uses
.remove(index
);
216 self.defs
.insert(index
);
219 fn add_use(&mut self, index
: Local
) {
224 // // Defs = {}, Uses = {X}
226 // // Defs = {X}, Uses = {}
228 // // Defs = {}, Uses = {X}
230 self.defs
.remove(index
);
231 self.uses
.insert(index
);
235 impl<'tcx
> Visitor
<'tcx
> for DefsUsesVisitor
237 fn visit_local(&mut self, &local
: &Local
, context
: PlaceContext
, _
: Location
) {
238 match categorize(context
) {
239 Some(DefUse
::Def
) => self.defs_uses
.add_def(local
),
240 Some(DefUse
::Use
) | Some(DefUse
::Drop
) => self.defs_uses
.add_use(local
),
247 b
: &BasicBlockData
<'_
>,
250 let mut visitor
= DefsUsesVisitor
{
251 defs_uses
: DefsUses
{
252 defs
: LiveVarSet
::new_empty(locals
),
253 uses
: LiveVarSet
::new_empty(locals
),
257 let dummy_location
= Location
{
258 block
: BasicBlock
::new(0),
262 // Visit the various parts of the basic block in reverse. If we go
263 // forward, the logic in `add_def` and `add_use` would be wrong.
264 visitor
.visit_terminator(b
.terminator(), dummy_location
);
265 for statement
in b
.statements
.iter().rev() {
266 visitor
.visit_statement(statement
, dummy_location
);
272 pub fn dump_mir
<'tcx
>(
275 source
: MirSource
<'tcx
>,
277 result
: &LivenessResult
,
279 if !dump_enabled(tcx
, pass_name
, source
) {
282 let node_path
= ty
::print
::with_forced_impl_filename_line(|| {
283 // see notes on #41697 below
284 tcx
.def_path_str(source
.def_id())
286 dump_matched_mir_node(tcx
, pass_name
, &node_path
, source
, body
, result
);
289 fn dump_matched_mir_node
<'tcx
>(
293 source
: MirSource
<'tcx
>,
295 result
: &LivenessResult
,
297 let mut file_path
= PathBuf
::new();
298 file_path
.push(Path
::new(&tcx
.sess
.opts
.debugging_opts
.dump_mir_dir
));
299 let item_id
= tcx
.hir().as_local_hir_id(source
.def_id()).unwrap();
300 let file_name
= format
!("rustc.node{}{}-liveness.mir", item_id
, pass_name
);
301 file_path
.push(&file_name
);
302 let _
= fs
::File
::create(&file_path
).and_then(|mut file
| {
303 writeln
!(file
, "// MIR local liveness analysis for `{}`", node_path
)?
;
304 writeln
!(file
, "// source = {:?}", source
)?
;
305 writeln
!(file
, "// pass_name = {}", pass_name
)?
;
307 write_mir_fn(tcx
, source
, body
, &mut file
, result
)?
;
312 pub fn write_mir_fn
<'tcx
>(
314 src
: MirSource
<'tcx
>,
317 result
: &LivenessResult
,
318 ) -> io
::Result
<()> {
319 write_mir_intro(tcx
, src
, body
, w
)?
;
320 for block
in body
.basic_blocks().indices() {
321 let print
= |w
: &mut dyn Write
, prefix
, result
: &IndexVec
<BasicBlock
, LiveVarSet
>| {
322 let live
: Vec
<String
> = result
[block
]
324 .map(|local
| format
!("{:?}", local
))
326 writeln
!(w
, "{} {{{}}}", prefix
, live
.join(", "))
328 write_basic_block(tcx
, block
, body
, &mut |_
, _
| Ok(()), w
)?
;
329 print(w
, " ", &result
.outs
)?
;
330 if block
.index() + 1 != body
.basic_blocks().len() {