1 use rustc_index::bit_set::{BitSet, ChunkedBitSet};
2 use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
3 use rustc_middle::mir::{self, Local, Location, Place, StatementKind};
5 use crate::{Analysis, AnalysisDomain, Backward, CallReturnPlaces, GenKill, GenKillAnalysis};
7 /// A [live-variable dataflow analysis][liveness].
9 /// This analysis considers references as being used only at the point of the
10 /// borrow. In other words, this analysis does not track uses because of references that already
11 /// exist. See [this `mir-dataflow` test][flow-test] for an example. You almost never want to use
12 /// this analysis without also looking at the results of [`MaybeBorrowedLocals`].
14 /// ## Field-(in)sensitivity
16 /// As the name suggests, this analysis is field insensitive. If a projection of a variable `x` is
17 /// assigned to (e.g. `x.0 = 42`), it does not "define" `x` as far as liveness is concerned. In fact,
18 /// such an assignment is currently marked as a "use" of `x` in an attempt to be maximally
21 /// [`MaybeBorrowedLocals`]: super::MaybeBorrowedLocals
22 /// [flow-test]: https://github.com/rust-lang/rust/blob/a08c47310c7d49cbdc5d7afb38408ba519967ecd/src/test/ui/mir-dataflow/liveness-ptr.rs
23 /// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
24 pub struct MaybeLiveLocals;
26 impl<'tcx> AnalysisDomain<'tcx> for MaybeLiveLocals {
27 type Domain = ChunkedBitSet<Local>;
28 type Direction = Backward;
30 const NAME: &'static str = "liveness";
32 fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
34 ChunkedBitSet::new_empty(body.local_decls.len())
37 fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
38 // No variables are live until we observe a use
42 impl<'tcx> GenKillAnalysis<'tcx> for MaybeLiveLocals {
47 trans: &mut impl GenKill<Self::Idx>,
48 statement: &mir::Statement<'tcx>,
51 TransferFunction(trans).visit_statement(statement, location);
56 trans: &mut impl GenKill<Self::Idx>,
57 terminator: &mir::Terminator<'tcx>,
60 TransferFunction(trans).visit_terminator(terminator, location);
63 fn call_return_effect(
65 trans: &mut impl GenKill<Self::Idx>,
66 _block: mir::BasicBlock,
67 return_places: CallReturnPlaces<'_, 'tcx>,
69 return_places.for_each(|place| {
70 if let Some(local) = place.as_local() {
76 fn yield_resume_effect(
78 trans: &mut impl GenKill<Self::Idx>,
79 _resume_block: mir::BasicBlock,
80 resume_place: mir::Place<'tcx>,
82 YieldResumeEffect(trans).visit_place(
84 PlaceContext::MutatingUse(MutatingUseContext::Yield),
90 struct TransferFunction<'a, T>(&'a mut T);
92 impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T>
96 fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
97 if let PlaceContext::MutatingUse(MutatingUseContext::Yield) = context {
98 // The resume place is evaluated and assigned to only after generator resumes, so its
99 // effect is handled separately in `yield_resume_effect`.
103 match DefUse::for_place(*place, context) {
104 Some(DefUse::Def) => {
105 if let PlaceContext::MutatingUse(
106 MutatingUseContext::Call | MutatingUseContext::AsmOutput,
109 // For the associated terminators, this is only a `Def` when the terminator returns
110 // "successfully." As such, we handle this case separately in `call_return_effect`
111 // above. However, if the place looks like `*_5`, this is still unconditionally a use of
114 self.0.kill(place.local);
117 Some(DefUse::Use) => self.0.gen(place.local),
121 self.visit_projection(place.as_ref(), context, location);
124 fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
125 DefUse::apply(self.0, local.into(), context);
129 struct YieldResumeEffect<'a, T>(&'a mut T);
131 impl<'tcx, T> Visitor<'tcx> for YieldResumeEffect<'_, T>
135 fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
136 DefUse::apply(self.0, *place, context);
137 self.visit_projection(place.as_ref(), context, location);
140 fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
141 DefUse::apply(self.0, local.into(), context);
145 #[derive(Eq, PartialEq, Clone)]
152 fn apply<'tcx>(trans: &mut impl GenKill<Local>, place: Place<'tcx>, context: PlaceContext) {
153 match DefUse::for_place(place, context) {
154 Some(DefUse::Def) => trans.kill(place.local),
155 Some(DefUse::Use) => trans.gen(place.local),
160 fn for_place<'tcx>(place: Place<'tcx>, context: PlaceContext) -> Option<DefUse> {
162 PlaceContext::NonUse(_) => None,
164 PlaceContext::MutatingUse(
165 MutatingUseContext::Call
166 | MutatingUseContext::Yield
167 | MutatingUseContext::AsmOutput
168 | MutatingUseContext::Store
169 | MutatingUseContext::Deinit,
171 if place.is_indirect() {
172 // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a
175 } else if place.projection.is_empty() {
182 // Setting the discriminant is not a use because it does no reading, but it is also not
183 // a def because it does not overwrite the whole place
184 PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => {
185 place.is_indirect().then_some(DefUse::Use)
188 // All other contexts are uses...
189 PlaceContext::MutatingUse(
190 MutatingUseContext::AddressOf
191 | MutatingUseContext::Borrow
192 | MutatingUseContext::Drop
193 | MutatingUseContext::Retag,
195 | PlaceContext::NonMutatingUse(
196 NonMutatingUseContext::AddressOf
197 | NonMutatingUseContext::Copy
198 | NonMutatingUseContext::Inspect
199 | NonMutatingUseContext::Move
200 | NonMutatingUseContext::ShallowBorrow
201 | NonMutatingUseContext::SharedBorrow
202 | NonMutatingUseContext::UniqueBorrow,
203 ) => Some(DefUse::Use),
205 PlaceContext::MutatingUse(MutatingUseContext::Projection)
206 | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
207 unreachable!("A projection could be a def or a use and must be handled separately")
213 /// Like `MaybeLiveLocals`, but does not mark locals as live if they are used in a dead assignment.
215 /// This is basically written for dead store elimination and nothing else.
217 /// All of the caveats of `MaybeLiveLocals` apply.
218 pub struct MaybeTransitiveLiveLocals<'a> {
219 always_live: &'a BitSet<Local>,
222 impl<'a> MaybeTransitiveLiveLocals<'a> {
223 /// The `always_alive` set is the set of locals to which all stores should unconditionally be
226 /// This should include at least all locals that are ever borrowed.
227 pub fn new(always_live: &'a BitSet<Local>) -> Self {
228 MaybeTransitiveLiveLocals { always_live }
232 impl<'a, 'tcx> AnalysisDomain<'tcx> for MaybeTransitiveLiveLocals<'a> {
233 type Domain = ChunkedBitSet<Local>;
234 type Direction = Backward;
236 const NAME: &'static str = "transitive liveness";
238 fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
240 ChunkedBitSet::new_empty(body.local_decls.len())
243 fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
244 // No variables are live until we observe a use
248 impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
249 fn apply_statement_effect(
251 trans: &mut Self::Domain,
252 statement: &mir::Statement<'tcx>,
255 // Compute the place that we are storing to, if any
256 let destination = match &statement.kind {
257 StatementKind::Assign(assign) => {
258 if assign.1.is_safe_to_remove() {
264 StatementKind::SetDiscriminant { place, .. } | StatementKind::Deinit(place) => {
267 StatementKind::FakeRead(_)
268 | StatementKind::StorageLive(_)
269 | StatementKind::StorageDead(_)
270 | StatementKind::Retag(..)
271 | StatementKind::AscribeUserType(..)
272 | StatementKind::Coverage(..)
273 | StatementKind::Intrinsic(..)
274 | StatementKind::Nop => None,
276 if let Some(destination) = destination {
277 if !destination.is_indirect()
278 && !trans.contains(destination.local)
279 && !self.always_live.contains(destination.local)
281 // This store is dead
285 TransferFunction(trans).visit_statement(statement, location);
288 fn apply_terminator_effect(
290 trans: &mut Self::Domain,
291 terminator: &mir::Terminator<'tcx>,
294 TransferFunction(trans).visit_terminator(terminator, location);
297 fn apply_call_return_effect(
299 trans: &mut Self::Domain,
300 _block: mir::BasicBlock,
301 return_places: CallReturnPlaces<'_, 'tcx>,
303 return_places.for_each(|place| {
304 if let Some(local) = place.as_local() {
310 fn apply_yield_resume_effect(
312 trans: &mut Self::Domain,
313 _resume_block: mir::BasicBlock,
314 resume_place: mir::Place<'tcx>,
316 YieldResumeEffect(trans).visit_place(
318 PlaceContext::MutatingUse(MutatingUseContext::Yield),