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;
1112use super::TypeChecker;
13use crate::constraints::OutlivesConstraintSet;
14use crate::polonius::PoloniusContext;
15use crate::region_infer::values::LivenessValues;
16use crate::universal_regions::UniversalRegions;
1718mod local_use_map;
19mod trace;
2021/// 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");
35let _timer = typeck.tcx().prof.generic_activity("borrowck_liveness");
3637let mut free_regions = regions_that_outlive_free_regions(
38typeck.infcx.num_region_vars(),
39&typeck.universal_regions,
40&typeck.constraints.outlives_constraints,
41 );
4243// 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.
49if typeck.tcx().sess.opts.unstable_opts.polonius.is_next_enabled() {
50let (_, boring_locals) =
51compute_relevant_live_locals(typeck.tcx(), &free_regions, typeck.body);
52typeck.polonius_context.as_mut().unwrap().boring_nll_locals =
53boring_locals.into_iter().collect();
54free_regions = typeck.universal_regions.universal_regions_iter().collect();
55 }
56let (relevant_live_locals, boring_locals) =
57compute_relevant_live_locals(typeck.tcx(), &free_regions, typeck.body);
5859 trace::trace(typeck, location_map, move_data, relevant_live_locals, boring_locals);
6061// Mark regions that should be live where they appear within rvalues or within a call: like
62 // args, regions, and types.
63record_regular_live_regions(
64typeck.tcx(),
65&mut typeck.constraints.liveness_constraints,
66&typeck.universal_regions,
67&mut typeck.polonius_context,
68typeck.body,
69 );
70}
7172// 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>) {
82let (boring_locals, relevant_live_locals): (Vec<_>, Vec<_>) =
83body.local_decls.iter_enumerated().partition_map(|(local, local_decl)| {
84if 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 });
9091{
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());
9495 (relevant_live_locals, boring_locals)
96}
9798/// 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.
112let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars);
113let fr_static = universal_regions.fr_static;
114let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static);
115116// Stack for the depth-first search. Start out with all the free regions.
117let mut stack: Vec<_> = universal_regions.universal_regions_iter().collect();
118119// Set of all free regions, plus anything that outlives them. Initially
120 // just contains the free regions.
121let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect();
122123// 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.
126while 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 }
133134// Return the final set of things we visited.
135outlives_free_region136}
137138/// 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) {
147let mut visitor =
148LiveVariablesVisitor { tcx, liveness_constraints, universal_regions, polonius_context };
149for (bb, data) in body.basic_blocks.iter_enumerated() {
150 visitor.visit_basic_block_data(bb, data);
151 }
152}
153154/// 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}
161162impl<'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.
165fn visit_args(&mut self, args: &GenericArgsRef<'tcx>, location: Location) {
166self.record_regions_live_at(*args, location);
167self.super_args(args);
168 }
169170/// We sometimes have `region`s within an rvalue, or within a
171 /// call. Make them live at the location where they appear.
172fn visit_region(&mut self, region: Region<'tcx>, location: Location) {
173self.record_regions_live_at(region, location);
174self.super_region(region);
175 }
176177/// We sometimes have `ty`s within an rvalue, or within a
178 /// call. Make them live at the location where they appear.
179fn visit_ty(&mut self, ty: Ty<'tcx>, ty_context: TyContext) {
180match 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) => {
189self.record_regions_live_at(ty, location);
190 }
191 }
192193self.super_ty(ty);
194 }
195}
196197impl<'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`.
200fn record_regions_live_at<T>(&mut self, value: T, location: Location)
201where
202T: 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);
205self.tcx.for_each_free_region(&value, |live_region| {
206let live_region_vid = live_region.as_var();
207self.liveness_constraints.add_location(live_region_vid, location);
208 });
209210// When using `-Zpolonius=next`, we record the variance of each live region.
211if let Some(polonius_context) = self.polonius_context {
212polonius_context.record_live_region_variance(self.tcx, self.universal_regions, value);
213 }
214 }
215}