[rustc.git] / compiler / rustc_mir_dataflow / src / impls / liveness.rs

use rustc_index::bit_set::{BitSet, ChunkedBitSet};
use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
use rustc_middle::mir::{self, Local, Location, Place, StatementKind};

use crate::{Analysis, AnalysisDomain, Backward, CallReturnPlaces, GenKill, GenKillAnalysis};

/// A [live-variable dataflow analysis][liveness].
///
/// This analysis considers references as being used only at the point of the
/// borrow. In other words, this analysis does not track uses because of references that already
/// exist. See [this `mir-dataflow` test][flow-test] for an example. You almost never want to use
/// this analysis without also looking at the results of [`MaybeBorrowedLocals`].
///
/// ## Field-(in)sensitivity
///
/// As the name suggests, this analysis is field insensitive. If a projection of a variable `x` is
/// assigned to (e.g. `x.0 = 42`), it does not "define" `x` as far as liveness is concerned. In fact,
/// such an assignment is currently marked as a "use" of `x` in an attempt to be maximally
/// conservative.
///
/// [`MaybeBorrowedLocals`]: super::MaybeBorrowedLocals
/// [flow-test]: https://github.com/rust-lang/rust/blob/a08c47310c7d49cbdc5d7afb38408ba519967ecd/src/test/ui/mir-dataflow/liveness-ptr.rs
/// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
pub struct MaybeLiveLocals;

impl<'tcx> AnalysisDomain<'tcx> for MaybeLiveLocals {
    type Domain = ChunkedBitSet<Local>;
    type Direction = Backward;

    const NAME: &'static str = "liveness";

    fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
        // bottom = not live
        ChunkedBitSet::new_empty(body.local_decls.len())
    }

    fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
        // No variables are live until we observe a use
    }
}

impl<'tcx> GenKillAnalysis<'tcx> for MaybeLiveLocals {
    type Idx = Local;

    fn statement_effect(
        &self,
        trans: &mut impl GenKill<Self::Idx>,
        statement: &mir::Statement<'tcx>,
        location: Location,
    ) {
        TransferFunction(trans).visit_statement(statement, location);
    }

    fn terminator_effect(
        &self,
        trans: &mut impl GenKill<Self::Idx>,
        terminator: &mir::Terminator<'tcx>,
        location: Location,
    ) {
        TransferFunction(trans).visit_terminator(terminator, location);
    }

    fn call_return_effect(
        &self,
        trans: &mut impl GenKill<Self::Idx>,
        _block: mir::BasicBlock,
        return_places: CallReturnPlaces<'_, 'tcx>,
    ) {
        return_places.for_each(|place| {
            if let Some(local) = place.as_local() {
                trans.kill(local);
            }
        });
    }

    fn yield_resume_effect(
        &self,
        trans: &mut impl GenKill<Self::Idx>,
        _resume_block: mir::BasicBlock,
        resume_place: mir::Place<'tcx>,
    ) {
        YieldResumeEffect(trans).visit_place(
            &resume_place,
            PlaceContext::MutatingUse(MutatingUseContext::Yield),
            Location::START,
        )
    }
}

struct TransferFunction<'a, T>(&'a mut T);

impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T>
where
    T: GenKill<Local>,
{
    fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
        if let PlaceContext::MutatingUse(MutatingUseContext::Yield) = context {
            // The resume place is evaluated and assigned to only after generator resumes, so its
            // effect is handled separately in `yield_resume_effect`.
            return;
        }

        match DefUse::for_place(*place, context) {
            Some(DefUse::Def) => {
                if let PlaceContext::MutatingUse(
                    MutatingUseContext::Call | MutatingUseContext::AsmOutput,
                ) = context
                {
                    // For the associated terminators, this is only a `Def` when the terminator returns
                    // "successfully." As such, we handle this case separately in `call_return_effect`
                    // above. However, if the place looks like `*_5`, this is still unconditionally a use of
                    // `_5`.
                } else {
                    self.0.kill(place.local);
                }
            }
            Some(DefUse::Use) => self.0.gen(place.local),
            None => {}
        }

        self.visit_projection(place.as_ref(), context, location);
    }

    fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
        DefUse::apply(self.0, local.into(), context);
    }
}

struct YieldResumeEffect<'a, T>(&'a mut T);

impl<'tcx, T> Visitor<'tcx> for YieldResumeEffect<'_, T>
where
    T: GenKill<Local>,
{
    fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
        DefUse::apply(self.0, *place, context);
        self.visit_projection(place.as_ref(), context, location);
    }

    fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
        DefUse::apply(self.0, local.into(), context);
    }
}

#[derive(Eq, PartialEq, Clone)]
enum DefUse {
    Def,
    Use,
}

impl DefUse {
    fn apply<'tcx>(trans: &mut impl GenKill<Local>, place: Place<'tcx>, context: PlaceContext) {
        match DefUse::for_place(place, context) {
            Some(DefUse::Def) => trans.kill(place.local),
            Some(DefUse::Use) => trans.gen(place.local),
            None => {}
        }
    }

    fn for_place<'tcx>(place: Place<'tcx>, context: PlaceContext) -> Option<DefUse> {
        match context {
            PlaceContext::NonUse(_) => None,

            PlaceContext::MutatingUse(
                MutatingUseContext::Call
                | MutatingUseContext::Yield
                | MutatingUseContext::AsmOutput
                | MutatingUseContext::Store
                | MutatingUseContext::Deinit,
            ) => {
                if place.is_indirect() {
                    // Treat derefs as a use of the base local. `*p = 4` is not a def of `p` but a
                    // use.
                    Some(DefUse::Use)
                } else if place.projection.is_empty() {
                    Some(DefUse::Def)
                } else {
                    None
                }
            }

            // Setting the discriminant is not a use because it does no reading, but it is also not
            // a def because it does not overwrite the whole place
            PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => {
                place.is_indirect().then_some(DefUse::Use)
            }

            // All other contexts are uses...
            PlaceContext::MutatingUse(
                MutatingUseContext::AddressOf
                | MutatingUseContext::Borrow
                | MutatingUseContext::Drop
                | MutatingUseContext::Retag,
            )
            | PlaceContext::NonMutatingUse(
                NonMutatingUseContext::AddressOf
                | NonMutatingUseContext::Copy
                | NonMutatingUseContext::Inspect
                | NonMutatingUseContext::Move
                | NonMutatingUseContext::ShallowBorrow
                | NonMutatingUseContext::SharedBorrow
                | NonMutatingUseContext::UniqueBorrow,
            ) => Some(DefUse::Use),

            PlaceContext::MutatingUse(MutatingUseContext::Projection)
            | PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) => {
                unreachable!("A projection could be a def or a use and must be handled separately")
            }
        }
    }
}

/// Like `MaybeLiveLocals`, but does not mark locals as live if they are used in a dead assignment.
///
/// This is basically written for dead store elimination and nothing else.
///
/// All of the caveats of `MaybeLiveLocals` apply.
pub struct MaybeTransitiveLiveLocals<'a> {
    always_live: &'a BitSet<Local>,
}

impl<'a> MaybeTransitiveLiveLocals<'a> {
    /// The `always_alive` set is the set of locals to which all stores should unconditionally be
    /// considered live.
    ///
    /// This should include at least all locals that are ever borrowed.
    pub fn new(always_live: &'a BitSet<Local>) -> Self {
        MaybeTransitiveLiveLocals { always_live }
    }
}

impl<'a, 'tcx> AnalysisDomain<'tcx> for MaybeTransitiveLiveLocals<'a> {
    type Domain = ChunkedBitSet<Local>;
    type Direction = Backward;

    const NAME: &'static str = "transitive liveness";

    fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
        // bottom = not live
        ChunkedBitSet::new_empty(body.local_decls.len())
    }

    fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
        // No variables are live until we observe a use
    }
}

impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
    fn apply_statement_effect(
        &self,
        trans: &mut Self::Domain,
        statement: &mir::Statement<'tcx>,
        location: Location,
    ) {
        // Compute the place that we are storing to, if any
        let destination = match &statement.kind {
            StatementKind::Assign(assign) => {
                if assign.1.is_safe_to_remove() {
                    Some(assign.0)
                } else {
                    None
                }
            }
            StatementKind::SetDiscriminant { place, .. } | StatementKind::Deinit(place) => {
                Some(**place)
            }
            StatementKind::FakeRead(_)
            | StatementKind::StorageLive(_)
            | StatementKind::StorageDead(_)
            | StatementKind::Retag(..)
            | StatementKind::AscribeUserType(..)
            | StatementKind::Coverage(..)
            | StatementKind::Intrinsic(..)
            | StatementKind::Nop => None,
        };
        if let Some(destination) = destination {
            if !destination.is_indirect()
                && !trans.contains(destination.local)
                && !self.always_live.contains(destination.local)
            {
                // This store is dead
                return;
            }
        }
        TransferFunction(trans).visit_statement(statement, location);
    }

    fn apply_terminator_effect(
        &self,
        trans: &mut Self::Domain,
        terminator: &mir::Terminator<'tcx>,
        location: Location,
    ) {
        TransferFunction(trans).visit_terminator(terminator, location);
    }

    fn apply_call_return_effect(
        &self,
        trans: &mut Self::Domain,
        _block: mir::BasicBlock,
        return_places: CallReturnPlaces<'_, 'tcx>,
    ) {
        return_places.for_each(|place| {
            if let Some(local) = place.as_local() {
                trans.remove(local);
            }
        });
    }

    fn apply_yield_resume_effect(
        &self,
        trans: &mut Self::Domain,
        _resume_block: mir::BasicBlock,
        resume_place: mir::Place<'tcx>,
    ) {
        YieldResumeEffect(trans).visit_place(
            &resume_place,
            PlaceContext::MutatingUse(MutatingUseContext::Yield),
            Location::START,
        )
    }
}
Commit	Line	Data
923072b8	1	use rustc_index::bit_set::{BitSet, ChunkedBitSet};
f9f354fc	2	use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
923072b8	3	use rustc_middle::mir::{self, Local, Location, Place, StatementKind};
f9f354fc	4
923072b8	5	use crate::{Analysis, AnalysisDomain, Backward, CallReturnPlaces, GenKill, GenKillAnalysis};
f9f354fc XL	6
	7	/// A [live-variable dataflow analysis][liveness].
	8	///
	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
29967ef6	11	/// exist. See [this `mir-dataflow` test][flow-test] for an example. You almost never want to use
f9f354fc XL	12	/// this analysis without also looking at the results of [`MaybeBorrowedLocals`].
f9f354fc XL	13	///
c295e0f8 XL	14	/// ## Field-(in)sensitivity
	15	///
	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
	19	/// conservative.
	20	///
fc512014	21	/// [`MaybeBorrowedLocals`]: super::MaybeBorrowedLocals
f9f354fc XL	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;
	25
a2a8927a	26	impl<'tcx> AnalysisDomain<'tcx> for MaybeLiveLocals {
923072b8	27	type Domain = ChunkedBitSet<Local>;
f9f354fc XL	28	type Direction = Backward;
	29
	30	const NAME: &'static str = "liveness";
	31
1b1a35ee XL	32	fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
1b1a35ee XL	33	// bottom = not live
923072b8	34	ChunkedBitSet::new_empty(body.local_decls.len())
f9f354fc XL	35	}
f9f354fc XL	36
1b1a35ee	37	fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
f9f354fc XL	38	// No variables are live until we observe a use
	39	}
	40	}
	41
a2a8927a	42	impl<'tcx> GenKillAnalysis<'tcx> for MaybeLiveLocals {
1b1a35ee XL	43	type Idx = Local;
1b1a35ee XL	44
f9f354fc XL	45	fn statement_effect(
	46	&self,
	47	trans: &mut impl GenKill<Self::Idx>,
	48	statement: &mir::Statement<'tcx>,
	49	location: Location,
	50	) {
f2b60f7d	51	TransferFunction(trans).visit_statement(statement, location);
f9f354fc XL	52	}
	53
	54	fn terminator_effect(
	55	&self,
	56	trans: &mut impl GenKill<Self::Idx>,
	57	terminator: &mir::Terminator<'tcx>,
	58	location: Location,
	59	) {
f2b60f7d	60	TransferFunction(trans).visit_terminator(terminator, location);
f9f354fc XL	61	}
	62
	63	fn call_return_effect(
	64	&self,
	65	trans: &mut impl GenKill<Self::Idx>,
	66	_block: mir::BasicBlock,
a2a8927a	67	return_places: CallReturnPlaces<'_, 'tcx>,
f9f354fc	68	) {
a2a8927a XL	69	return_places.for_each(\|place\| {
	70	if let Some(local) = place.as_local() {
	71	trans.kill(local);
	72	}
	73	});
f9f354fc XL	74	}
	75
	76	fn yield_resume_effect(
	77	&self,
	78	trans: &mut impl GenKill<Self::Idx>,
	79	_resume_block: mir::BasicBlock,
	80	resume_place: mir::Place<'tcx>,
	81	) {
f2b60f7d FG	82	YieldResumeEffect(trans).visit_place(
	83	&resume_place,
	84	PlaceContext::MutatingUse(MutatingUseContext::Yield),
	85	Location::START,
	86	)
f9f354fc XL	87	}
	88	}
	89
	90	struct TransferFunction<'a, T>(&'a mut T);
	91
	92	impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T>
	93	where
	94	T: GenKill<Local>,
	95	{
f035d41b	96	fn visit_place(&mut self, place: &mir::Place<'tcx>, context: PlaceContext, location: Location) {
f2b60f7d FG	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`.
	100	return;
	101	}
f035d41b	102
923072b8	103	match DefUse::for_place(*place, context) {
f2b60f7d FG	104	Some(DefUse::Def) => {
	105	if let PlaceContext::MutatingUse(
	106	MutatingUseContext::Call \| MutatingUseContext::AsmOutput,
	107	) = context
	108	{
	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
	112	// `_5`.
	113	} else {
	114	self.0.kill(place.local);
	115	}
	116	}
	117	Some(DefUse::Use) => self.0.gen(place.local),
923072b8	118	None => {}
f035d41b	119	}
f2b60f7d FG	120
f2b60f7d FG	121	self.visit_projection(place.as_ref(), context, location);
f035d41b XL	122	}
f035d41b XL	123
064997fb	124	fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
f2b60f7d FG	125	DefUse::apply(self.0, local.into(), context);
	126	}
	127	}
	128
	129	struct YieldResumeEffect<'a, T>(&'a mut T);
	130
	131	impl<'tcx, T> Visitor<'tcx> for YieldResumeEffect<'_, T>
	132	where
	133	T: GenKill<Local>,
	134	{
	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);
	138	}
	139
	140	fn visit_local(&mut self, local: Local, context: PlaceContext, _: Location) {
	141	DefUse::apply(self.0, local.into(), context);
f9f354fc XL	142	}
	143	}
	144
	145	#[derive(Eq, PartialEq, Clone)]
	146	enum DefUse {
	147	Def,
	148	Use,
	149	}
	150
	151	impl DefUse {
f2b60f7d FG	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),
	156	None => {}
	157	}
	158	}
	159
923072b8	160	fn for_place<'tcx>(place: Place<'tcx>, context: PlaceContext) -> Option<DefUse> {
f9f354fc XL	161	match context {
	162	PlaceContext::NonUse(_) => None,
	163
f2b60f7d FG	164	PlaceContext::MutatingUse(
	165	MutatingUseContext::Call
	166	\| MutatingUseContext::Yield
	167	\| MutatingUseContext::AsmOutput
	168	\| MutatingUseContext::Store
	169	\| MutatingUseContext::Deinit,
	170	) => {
923072b8 FG	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
	173	// use.
	174	Some(DefUse::Use)
	175	} else if place.projection.is_empty() {
	176	Some(DefUse::Def)
	177	} else {
	178	None
	179	}
04454e1e FG	180	}
	181
	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
923072b8 FG	184	PlaceContext::MutatingUse(MutatingUseContext::SetDiscriminant) => {
	185	place.is_indirect().then_some(DefUse::Use)
	186	}
f9f354fc	187
f9f354fc XL	188	// All other contexts are uses...
	189	PlaceContext::MutatingUse(
	190	MutatingUseContext::AddressOf
f9f354fc XL	191	\| MutatingUseContext::Borrow
f9f354fc XL	192	\| MutatingUseContext::Drop
f9f354fc XL	193	\| MutatingUseContext::Retag,
	194	)
	195	\| PlaceContext::NonMutatingUse(
	196	NonMutatingUseContext::AddressOf
	197	\| NonMutatingUseContext::Copy
	198	\| NonMutatingUseContext::Inspect
	199	\| NonMutatingUseContext::Move
f9f354fc XL	200	\| NonMutatingUseContext::ShallowBorrow
	201	\| NonMutatingUseContext::SharedBorrow
	202	\| NonMutatingUseContext::UniqueBorrow,
	203	) => Some(DefUse::Use),
f035d41b XL	204
	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")
	208	}
f9f354fc XL	209	}
	210	}
	211	}
923072b8 FG	212
	213	/// Like `MaybeLiveLocals`, but does not mark locals as live if they are used in a dead assignment.
	214	///
	215	/// This is basically written for dead store elimination and nothing else.
	216	///
	217	/// All of the caveats of `MaybeLiveLocals` apply.
	218	pub struct MaybeTransitiveLiveLocals<'a> {
	219	always_live: &'a BitSet<Local>,
	220	}
	221
	222	impl<'a> MaybeTransitiveLiveLocals<'a> {
	223	/// The `always_alive` set is the set of locals to which all stores should unconditionally be
	224	/// considered live.
	225	///
	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 }
	229	}
	230	}
	231
	232	impl<'a, 'tcx> AnalysisDomain<'tcx> for MaybeTransitiveLiveLocals<'a> {
	233	type Domain = ChunkedBitSet<Local>;
	234	type Direction = Backward;
	235
	236	const NAME: &'static str = "transitive liveness";
	237
	238	fn bottom_value(&self, body: &mir::Body<'tcx>) -> Self::Domain {
	239	// bottom = not live
	240	ChunkedBitSet::new_empty(body.local_decls.len())
	241	}
	242
	243	fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut Self::Domain) {
	244	// No variables are live until we observe a use
	245	}
	246	}
	247
923072b8 FG	248	impl<'a, 'tcx> Analysis<'tcx> for MaybeTransitiveLiveLocals<'a> {
	249	fn apply_statement_effect(
	250	&self,
	251	trans: &mut Self::Domain,
	252	statement: &mir::Statement<'tcx>,
	253	location: Location,
	254	) {
	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() {
	259	Some(assign.0)
	260	} else {
	261	None
	262	}
	263	}
	264	StatementKind::SetDiscriminant { place, .. } \| StatementKind::Deinit(place) => {
	265	Some(**place)
	266	}
	267	StatementKind::FakeRead(_)
	268	\| StatementKind::StorageLive(_)
	269	\| StatementKind::StorageDead(_)
	270	\| StatementKind::Retag(..)
	271	\| StatementKind::AscribeUserType(..)
	272	\| StatementKind::Coverage(..)
f2b60f7d	273	\| StatementKind::Intrinsic(..)
923072b8 FG	274	\| StatementKind::Nop => None,
	275	};
	276	if let Some(destination) = destination {
	277	if !destination.is_indirect()
	278	&& !trans.contains(destination.local)
	279	&& !self.always_live.contains(destination.local)
	280	{
	281	// This store is dead
	282	return;
	283	}
	284	}
064997fb	285	TransferFunction(trans).visit_statement(statement, location);
923072b8 FG	286	}
	287
	288	fn apply_terminator_effect(
	289	&self,
	290	trans: &mut Self::Domain,
	291	terminator: &mir::Terminator<'tcx>,
	292	location: Location,
	293	) {
064997fb	294	TransferFunction(trans).visit_terminator(terminator, location);
923072b8 FG	295	}
	296
	297	fn apply_call_return_effect(
	298	&self,
	299	trans: &mut Self::Domain,
	300	_block: mir::BasicBlock,
	301	return_places: CallReturnPlaces<'_, 'tcx>,
	302	) {
	303	return_places.for_each(\|place\| {
	304	if let Some(local) = place.as_local() {
	305	trans.remove(local);
	306	}
	307	});
	308	}
	309
	310	fn apply_yield_resume_effect(
	311	&self,
	312	trans: &mut Self::Domain,
	313	_resume_block: mir::BasicBlock,
	314	resume_place: mir::Place<'tcx>,
	315	) {
f2b60f7d FG	316	YieldResumeEffect(trans).visit_place(
	317	&resume_place,
	318	PlaceContext::MutatingUse(MutatingUseContext::Yield),
	319	Location::START,
	320	)
923072b8 FG	321	}
923072b8 FG	322	}