Skip to main content

rustc_borrowck/type_check/liveness/
mod.rs

1use itertools::{Either, Itertools};
2use rustc_data_structures::fx::FxHashSet;
3use rustc_middle::mir::visit::{TyContext, Visitor};
4use rustc_middle::mir::{Body, Local, Location, SourceInfo};
5use rustc_middle::span_bug;
6use rustc_middle::ty::relate::Relate;
7use rustc_middle::ty::{GenericArgsRef, Region, RegionVid, Ty, TyCtxt, TypeVisitable};
8use rustc_mir_dataflow::move_paths::MoveData;
9use rustc_mir_dataflow::points::DenseLocationMap;
10use tracing::debug;
11
12use super::TypeChecker;
13use crate::constraints::OutlivesConstraintSet;
14use crate::polonius::PoloniusContext;
15use crate::region_infer::values::LivenessValues;
16use crate::universal_regions::UniversalRegions;
17
18mod local_use_map;
19mod trace;
20
21/// Combines liveness analysis with initialization analysis to
22/// determine which variables are live at which points, both due to
23/// ordinary uses and drops. Returns a set of (ty, location) pairs
24/// that indicate which types must be live at which point in the CFG.
25/// This vector is consumed by `constraint_generation`.
26///
27/// N.B., this computation requires normalization; therefore, it must be
28/// performed before
29pub(super) fn generate<'tcx>(
30    typeck: &mut TypeChecker<'_, 'tcx>,
31    location_map: &DenseLocationMap,
32    move_data: &MoveData<'tcx>,
33) {
34    {
    use ::tracing::__macro_support::Callsite as _;
    static __CALLSITE: ::tracing::callsite::DefaultCallsite =
        {
            static META: ::tracing::Metadata<'static> =
                {
                    ::tracing_core::metadata::Metadata::new("event compiler/rustc_borrowck/src/type_check/liveness/mod.rs:34",
                        "rustc_borrowck::type_check::liveness",
                        ::tracing::Level::DEBUG,
                        ::tracing_core::__macro_support::Option::Some("compiler/rustc_borrowck/src/type_check/liveness/mod.rs"),
                        ::tracing_core::__macro_support::Option::Some(34u32),
                        ::tracing_core::__macro_support::Option::Some("rustc_borrowck::type_check::liveness"),
                        ::tracing_core::field::FieldSet::new(&["message"],
                            ::tracing_core::callsite::Identifier(&__CALLSITE)),
                        ::tracing::metadata::Kind::EVENT)
                };
            ::tracing::callsite::DefaultCallsite::new(&META)
        };
    let enabled =
        ::tracing::Level::DEBUG <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::DEBUG <=
                    ::tracing::level_filters::LevelFilter::current() &&
            {
                let interest = __CALLSITE.interest();
                !interest.is_never() &&
                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                        interest)
            };
    if enabled {
        (|value_set: ::tracing::field::ValueSet|
                    {
                        let meta = __CALLSITE.metadata();
                        ::tracing::Event::dispatch(meta, &value_set);
                        ;
                    })({
                #[allow(unused_imports)]
                use ::tracing::field::{debug, display, Value};
                __CALLSITE.metadata().fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&format_args!("liveness::generate")
                                            as &dyn ::tracing::field::Value))])
            });
    } else { ; }
};debug!("liveness::generate");
35    let _timer = typeck.tcx().prof.generic_activity("borrowck_liveness");
36
37    let mut free_regions = regions_that_outlive_free_regions(
38        typeck.infcx.num_region_vars(),
39        &typeck.universal_regions,
40        &typeck.constraints.outlives_constraints,
41    );
42
43    // NLLs can avoid computing some liveness data here because its constraints are
44    // location-insensitive, but that doesn't work in polonius: locals whose type contains a region
45    // that outlives a free region are not necessarily live everywhere in a flow-sensitive setting,
46    // unlike NLLs.
47    // We do record these regions in the polonius context, since they're used to differentiate
48    // relevant and boring locals, which is a key distinction used later in diagnostics.
49    if typeck.tcx().sess.opts.unstable_opts.polonius.is_next_enabled() {
50        let (_, boring_locals) =
51            compute_relevant_live_locals(typeck.tcx(), &free_regions, typeck.body);
52        typeck.polonius_context.as_mut().unwrap().boring_nll_locals =
53            boring_locals.into_iter().collect();
54        free_regions = typeck.universal_regions.universal_regions_iter().collect();
55    }
56    let (relevant_live_locals, boring_locals) =
57        compute_relevant_live_locals(typeck.tcx(), &free_regions, typeck.body);
58
59    trace::trace(typeck, location_map, move_data, relevant_live_locals, boring_locals);
60
61    // Mark regions that should be live where they appear within rvalues or within a call: like
62    // args, regions, and types.
63    record_regular_live_regions(
64        typeck.tcx(),
65        &mut typeck.constraints.liveness_constraints,
66        &typeck.universal_regions,
67        &mut typeck.polonius_context,
68        typeck.body,
69    );
70}
71
72// The purpose of `compute_relevant_live_locals` is to define the subset of `Local`
73// variables for which we need to do a liveness computation. We only need
74// to compute whether a variable `X` is live if that variable contains
75// some region `R` in its type where `R` is not known to outlive a free
76// region (i.e., where `R` may be valid for just a subset of the fn body).
77fn compute_relevant_live_locals<'tcx>(
78    tcx: TyCtxt<'tcx>,
79    free_regions: &FxHashSet<RegionVid>,
80    body: &Body<'tcx>,
81) -> (Vec<Local>, Vec<Local>) {
82    let (boring_locals, relevant_live_locals): (Vec<_>, Vec<_>) =
83        body.local_decls.iter_enumerated().partition_map(|(local, local_decl)| {
84            if tcx.all_free_regions_meet(&local_decl.ty, |r| free_regions.contains(&r.as_var())) {
85                Either::Left(local)
86            } else {
87                Either::Right(local)
88            }
89        });
90
91    {
    use ::tracing::__macro_support::Callsite as _;
    static __CALLSITE: ::tracing::callsite::DefaultCallsite =
        {
            static META: ::tracing::Metadata<'static> =
                {
                    ::tracing_core::metadata::Metadata::new("event compiler/rustc_borrowck/src/type_check/liveness/mod.rs:91",
                        "rustc_borrowck::type_check::liveness",
                        ::tracing::Level::DEBUG,
                        ::tracing_core::__macro_support::Option::Some("compiler/rustc_borrowck/src/type_check/liveness/mod.rs"),
                        ::tracing_core::__macro_support::Option::Some(91u32),
                        ::tracing_core::__macro_support::Option::Some("rustc_borrowck::type_check::liveness"),
                        ::tracing_core::field::FieldSet::new(&["message"],
                            ::tracing_core::callsite::Identifier(&__CALLSITE)),
                        ::tracing::metadata::Kind::EVENT)
                };
            ::tracing::callsite::DefaultCallsite::new(&META)
        };
    let enabled =
        ::tracing::Level::DEBUG <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::DEBUG <=
                    ::tracing::level_filters::LevelFilter::current() &&
            {
                let interest = __CALLSITE.interest();
                !interest.is_never() &&
                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                        interest)
            };
    if enabled {
        (|value_set: ::tracing::field::ValueSet|
                    {
                        let meta = __CALLSITE.metadata();
                        ::tracing::Event::dispatch(meta, &value_set);
                        ;
                    })({
                #[allow(unused_imports)]
                use ::tracing::field::{debug, display, Value};
                __CALLSITE.metadata().fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&format_args!("{0} total variables",
                                                    body.local_decls.len()) as &dyn ::tracing::field::Value))])
            });
    } else { ; }
};debug!("{} total variables", body.local_decls.len());
92    {
    use ::tracing::__macro_support::Callsite as _;
    static __CALLSITE: ::tracing::callsite::DefaultCallsite =
        {
            static META: ::tracing::Metadata<'static> =
                {
                    ::tracing_core::metadata::Metadata::new("event compiler/rustc_borrowck/src/type_check/liveness/mod.rs:92",
                        "rustc_borrowck::type_check::liveness",
                        ::tracing::Level::DEBUG,
                        ::tracing_core::__macro_support::Option::Some("compiler/rustc_borrowck/src/type_check/liveness/mod.rs"),
                        ::tracing_core::__macro_support::Option::Some(92u32),
                        ::tracing_core::__macro_support::Option::Some("rustc_borrowck::type_check::liveness"),
                        ::tracing_core::field::FieldSet::new(&["message"],
                            ::tracing_core::callsite::Identifier(&__CALLSITE)),
                        ::tracing::metadata::Kind::EVENT)
                };
            ::tracing::callsite::DefaultCallsite::new(&META)
        };
    let enabled =
        ::tracing::Level::DEBUG <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::DEBUG <=
                    ::tracing::level_filters::LevelFilter::current() &&
            {
                let interest = __CALLSITE.interest();
                !interest.is_never() &&
                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                        interest)
            };
    if enabled {
        (|value_set: ::tracing::field::ValueSet|
                    {
                        let meta = __CALLSITE.metadata();
                        ::tracing::Event::dispatch(meta, &value_set);
                        ;
                    })({
                #[allow(unused_imports)]
                use ::tracing::field::{debug, display, Value};
                __CALLSITE.metadata().fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&format_args!("{0} variables need liveness",
                                                    relevant_live_locals.len()) as
                                            &dyn ::tracing::field::Value))])
            });
    } else { ; }
};debug!("{} variables need liveness", relevant_live_locals.len());
93    {
    use ::tracing::__macro_support::Callsite as _;
    static __CALLSITE: ::tracing::callsite::DefaultCallsite =
        {
            static META: ::tracing::Metadata<'static> =
                {
                    ::tracing_core::metadata::Metadata::new("event compiler/rustc_borrowck/src/type_check/liveness/mod.rs:93",
                        "rustc_borrowck::type_check::liveness",
                        ::tracing::Level::DEBUG,
                        ::tracing_core::__macro_support::Option::Some("compiler/rustc_borrowck/src/type_check/liveness/mod.rs"),
                        ::tracing_core::__macro_support::Option::Some(93u32),
                        ::tracing_core::__macro_support::Option::Some("rustc_borrowck::type_check::liveness"),
                        ::tracing_core::field::FieldSet::new(&["message"],
                            ::tracing_core::callsite::Identifier(&__CALLSITE)),
                        ::tracing::metadata::Kind::EVENT)
                };
            ::tracing::callsite::DefaultCallsite::new(&META)
        };
    let enabled =
        ::tracing::Level::DEBUG <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::DEBUG <=
                    ::tracing::level_filters::LevelFilter::current() &&
            {
                let interest = __CALLSITE.interest();
                !interest.is_never() &&
                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                        interest)
            };
    if enabled {
        (|value_set: ::tracing::field::ValueSet|
                    {
                        let meta = __CALLSITE.metadata();
                        ::tracing::Event::dispatch(meta, &value_set);
                        ;
                    })({
                #[allow(unused_imports)]
                use ::tracing::field::{debug, display, Value};
                __CALLSITE.metadata().fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&format_args!("{0} regions outlive free regions",
                                                    free_regions.len()) as &dyn ::tracing::field::Value))])
            });
    } else { ; }
};debug!("{} regions outlive free regions", free_regions.len());
94
95    (relevant_live_locals, boring_locals)
96}
97
98/// Computes all regions that are (currently) known to outlive free
99/// regions. For these regions, we do not need to compute
100/// liveness, since the outlives constraints will ensure that they
101/// are live over the whole fn body anyhow.
102fn regions_that_outlive_free_regions<'tcx>(
103    num_region_vars: usize,
104    universal_regions: &UniversalRegions<'tcx>,
105    constraint_set: &OutlivesConstraintSet<'tcx>,
106) -> FxHashSet<RegionVid> {
107    // Build a graph of the outlives constraints thus far. This is
108    // a reverse graph, so for each constraint `R1: R2` we have an
109    // edge `R2 -> R1`. Therefore, if we find all regions
110    // reachable from each free region, we will have all the
111    // regions that are forced to outlive some free region.
112    let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars);
113    let fr_static = universal_regions.fr_static;
114    let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static);
115
116    // Stack for the depth-first search. Start out with all the free regions.
117    let mut stack: Vec<_> = universal_regions.universal_regions_iter().collect();
118
119    // Set of all free regions, plus anything that outlives them. Initially
120    // just contains the free regions.
121    let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect();
122
123    // Do the DFS -- for each thing in the stack, find all things
124    // that outlive it and add them to the set. If they are not,
125    // push them onto the stack for later.
126    while let Some(sub_region) = stack.pop() {
127        stack.extend(
128            rev_region_graph
129                .outgoing_regions(sub_region)
130                .filter(|&r| outlives_free_region.insert(r)),
131        );
132    }
133
134    // Return the final set of things we visited.
135    outlives_free_region
136}
137
138/// Some variables are "regular live" at `location` -- i.e., they may be used later. This means that
139/// all regions appearing in their type must be live at `location`.
140fn record_regular_live_regions<'tcx>(
141    tcx: TyCtxt<'tcx>,
142    liveness_constraints: &mut LivenessValues,
143    universal_regions: &UniversalRegions<'tcx>,
144    polonius_context: &mut Option<PoloniusContext>,
145    body: &Body<'tcx>,
146) {
147    let mut visitor =
148        LiveVariablesVisitor { tcx, liveness_constraints, universal_regions, polonius_context };
149    for (bb, data) in body.basic_blocks.iter_enumerated() {
150        visitor.visit_basic_block_data(bb, data);
151    }
152}
153
154/// Visitor looking for regions that should be live within rvalues or calls.
155struct LiveVariablesVisitor<'a, 'tcx> {
156    tcx: TyCtxt<'tcx>,
157    liveness_constraints: &'a mut LivenessValues,
158    universal_regions: &'a UniversalRegions<'tcx>,
159    polonius_context: &'a mut Option<PoloniusContext>,
160}
161
162impl<'a, 'tcx> Visitor<'tcx> for LiveVariablesVisitor<'a, 'tcx> {
163    /// We sometimes have `args` within an rvalue, or within a
164    /// call. Make them live at the location where they appear.
165    fn visit_args(&mut self, args: &GenericArgsRef<'tcx>, location: Location) {
166        self.record_regions_live_at(*args, location);
167        self.super_args(args);
168    }
169
170    /// We sometimes have `region`s within an rvalue, or within a
171    /// call. Make them live at the location where they appear.
172    fn visit_region(&mut self, region: Region<'tcx>, location: Location) {
173        self.record_regions_live_at(region, location);
174        self.super_region(region);
175    }
176
177    /// We sometimes have `ty`s within an rvalue, or within a
178    /// call. Make them live at the location where they appear.
179    fn visit_ty(&mut self, ty: Ty<'tcx>, ty_context: TyContext) {
180        match ty_context {
181            TyContext::ReturnTy(SourceInfo { span, .. })
182            | TyContext::YieldTy(SourceInfo { span, .. })
183            | TyContext::ResumeTy(SourceInfo { span, .. })
184            | TyContext::UserTy(span)
185            | TyContext::LocalDecl { source_info: SourceInfo { span, .. }, .. } => {
186                ::rustc_middle::util::bug::span_bug_fmt(span,
    format_args!("should not be visiting outside of the CFG: {0:?}",
        ty_context));span_bug!(span, "should not be visiting outside of the CFG: {:?}", ty_context);
187            }
188            TyContext::Location(location) => {
189                self.record_regions_live_at(ty, location);
190            }
191        }
192
193        self.super_ty(ty);
194    }
195}
196
197impl<'a, 'tcx> LiveVariablesVisitor<'a, 'tcx> {
198    /// Some variable is "regular live" at `location` -- i.e., it may be used later. This means that
199    /// all regions appearing in the type of `value` must be live at `location`.
200    fn record_regions_live_at<T>(&mut self, value: T, location: Location)
201    where
202        T: TypeVisitable<TyCtxt<'tcx>> + Relate<TyCtxt<'tcx>>,
203    {
204        {
    use ::tracing::__macro_support::Callsite as _;
    static __CALLSITE: ::tracing::callsite::DefaultCallsite =
        {
            static META: ::tracing::Metadata<'static> =
                {
                    ::tracing_core::metadata::Metadata::new("event compiler/rustc_borrowck/src/type_check/liveness/mod.rs:204",
                        "rustc_borrowck::type_check::liveness",
                        ::tracing::Level::DEBUG,
                        ::tracing_core::__macro_support::Option::Some("compiler/rustc_borrowck/src/type_check/liveness/mod.rs"),
                        ::tracing_core::__macro_support::Option::Some(204u32),
                        ::tracing_core::__macro_support::Option::Some("rustc_borrowck::type_check::liveness"),
                        ::tracing_core::field::FieldSet::new(&["message"],
                            ::tracing_core::callsite::Identifier(&__CALLSITE)),
                        ::tracing::metadata::Kind::EVENT)
                };
            ::tracing::callsite::DefaultCallsite::new(&META)
        };
    let enabled =
        ::tracing::Level::DEBUG <= ::tracing::level_filters::STATIC_MAX_LEVEL
                &&
                ::tracing::Level::DEBUG <=
                    ::tracing::level_filters::LevelFilter::current() &&
            {
                let interest = __CALLSITE.interest();
                !interest.is_never() &&
                    ::tracing::__macro_support::__is_enabled(__CALLSITE.metadata(),
                        interest)
            };
    if enabled {
        (|value_set: ::tracing::field::ValueSet|
                    {
                        let meta = __CALLSITE.metadata();
                        ::tracing::Event::dispatch(meta, &value_set);
                        ;
                    })({
                #[allow(unused_imports)]
                use ::tracing::field::{debug, display, Value};
                __CALLSITE.metadata().fields().value_set_all(&[(::tracing::__macro_support::Option::Some(&format_args!("record_regions_live_at(value={0:?}, location={1:?})",
                                                    value, location) as &dyn ::tracing::field::Value))])
            });
    } else { ; }
};debug!("record_regions_live_at(value={:?}, location={:?})", value, location);
205        self.tcx.for_each_free_region(&value, |live_region| {
206            let live_region_vid = live_region.as_var();
207            self.liveness_constraints.add_location(live_region_vid, location);
208        });
209
210        // When using `-Zpolonius=next`, we record the variance of each live region.
211        if let Some(polonius_context) = self.polonius_context {
212            polonius_context.record_live_region_variance(self.tcx, self.universal_regions, value);
213        }
214    }
215}