Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 1027 insertions, 0 deletions

diff --git a/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs b/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs
new file mode 100644
index 000000000..fda2cee43
--- /dev/null
+++ b/compiler/rustc_borrowck/src/type_check/liveness/local_use_map.rs
@@ -0,0 +1,170 @@
+use rustc_data_structures::vec_linked_list as vll;
+use rustc_index::vec::IndexVec;
+use rustc_middle::mir::visit::{PlaceContext, Visitor};
+use rustc_middle::mir::{Body, Local, Location};
+
+use crate::def_use::{self, DefUse};
+use crate::region_infer::values::{PointIndex, RegionValueElements};
+
+/// A map that cross references each local with the locations where it
+/// is defined (assigned), used, or dropped. Used during liveness
+/// computation.
+///
+/// We keep track only of `Local`s we'll do the liveness analysis later,
+/// this means that our internal `IndexVec`s will only be sparsely populated.
+/// In the time-memory trade-off between keeping compact vectors with new
+/// indexes (and needing to continuously map the `Local` index to its compact
+/// counterpart) and having `IndexVec`s that we only use a fraction of, time
+/// (and code simplicity) was favored. The rationale is that we only keep
+/// a small number of `IndexVec`s throughout the entire analysis while, in
+/// contrast, we're accessing each `Local` *many* times.
+pub(crate) struct LocalUseMap {
+    /// Head of a linked list of **definitions** of each variable --
+    /// definition in this context means assignment, e.g., `x` is
+    /// defined in `x = y` but not `y`; that first def is the head of
+    /// a linked list that lets you enumerate all places the variable
+    /// is assigned.
+    first_def_at: IndexVec<Local, Option<AppearanceIndex>>,
+
+    /// Head of a linked list of **uses** of each variable -- use in
+    /// this context means that the existing value of the variable is
+    /// read or modified. e.g., `y` is used in `x = y` but not `x`.
+    /// Note that `DROP(x)` terminators are excluded from this list.
+    first_use_at: IndexVec<Local, Option<AppearanceIndex>>,
+
+    /// Head of a linked list of **drops** of each variable -- these
+    /// are a special category of uses corresponding to the drop that
+    /// we add for each local variable.
+    first_drop_at: IndexVec<Local, Option<AppearanceIndex>>,
+
+    appearances: IndexVec<AppearanceIndex, Appearance>,
+}
+
+struct Appearance {
+    point_index: PointIndex,
+    next: Option<AppearanceIndex>,
+}
+
+rustc_index::newtype_index! {
+    pub struct AppearanceIndex { .. }
+}
+
+impl vll::LinkElem for Appearance {
+    type LinkIndex = AppearanceIndex;
+
+    fn next(elem: &Self) -> Option<AppearanceIndex> {
+        elem.next
+    }
+}
+
+impl LocalUseMap {
+    pub(crate) fn build(
+        live_locals: &[Local],
+        elements: &RegionValueElements,
+        body: &Body<'_>,
+    ) -> Self {
+        let nones = IndexVec::from_elem_n(None, body.local_decls.len());
+        let mut local_use_map = LocalUseMap {
+            first_def_at: nones.clone(),
+            first_use_at: nones.clone(),
+            first_drop_at: nones,
+            appearances: IndexVec::new(),
+        };
+
+        if live_locals.is_empty() {
+            return local_use_map;
+        }
+
+        let mut locals_with_use_data: IndexVec<Local, bool> =
+            IndexVec::from_elem_n(false, body.local_decls.len());
+        live_locals.iter().for_each(|&local| locals_with_use_data[local] = true);
+
+        LocalUseMapBuild { local_use_map: &mut local_use_map, elements, locals_with_use_data }
+            .visit_body(&body);
+
+        local_use_map
+    }
+
+    pub(crate) fn defs(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
+        vll::iter(self.first_def_at[local], &self.appearances)
+            .map(move |aa| self.appearances[aa].point_index)
+    }
+
+    pub(crate) fn uses(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
+        vll::iter(self.first_use_at[local], &self.appearances)
+            .map(move |aa| self.appearances[aa].point_index)
+    }
+
+    pub(crate) fn drops(&self, local: Local) -> impl Iterator<Item = PointIndex> + '_ {
+        vll::iter(self.first_drop_at[local], &self.appearances)
+            .map(move |aa| self.appearances[aa].point_index)
+    }
+}
+
+struct LocalUseMapBuild<'me> {
+    local_use_map: &'me mut LocalUseMap,
+    elements: &'me RegionValueElements,
+
+    // Vector used in `visit_local` to signal which `Local`s do we need
+    // def/use/drop information on, constructed from `live_locals` (that
+    // contains the variables we'll do the liveness analysis for).
+    // This vector serves optimization purposes only: we could have
+    // obtained the same information from `live_locals` but we want to
+    // avoid repeatedly calling `Vec::contains()` (see `LocalUseMap` for
+    // the rationale on the time-memory trade-off we're favoring here).
+    locals_with_use_data: IndexVec<Local, bool>,
+}
+
+impl LocalUseMapBuild<'_> {
+    fn insert_def(&mut self, local: Local, location: Location) {
+        Self::insert(
+            self.elements,
+            &mut self.local_use_map.first_def_at[local],
+            &mut self.local_use_map.appearances,
+            location,
+        );
+    }
+
+    fn insert_use(&mut self, local: Local, location: Location) {
+        Self::insert(
+            self.elements,
+            &mut self.local_use_map.first_use_at[local],
+            &mut self.local_use_map.appearances,
+            location,
+        );
+    }
+
+    fn insert_drop(&mut self, local: Local, location: Location) {
+        Self::insert(
+            self.elements,
+            &mut self.local_use_map.first_drop_at[local],
+            &mut self.local_use_map.appearances,
+            location,
+        );
+    }
+
+    fn insert(
+        elements: &RegionValueElements,
+        first_appearance: &mut Option<AppearanceIndex>,
+        appearances: &mut IndexVec<AppearanceIndex, Appearance>,
+        location: Location,
+    ) {
+        let point_index = elements.point_from_location(location);
+        let appearance_index =
+            appearances.push(Appearance { point_index, next: *first_appearance });
+        *first_appearance = Some(appearance_index);
+    }
+}
+
+impl Visitor<'_> for LocalUseMapBuild<'_> {
+    fn visit_local(&mut self, local: Local, context: PlaceContext, location: Location) {
+        if self.locals_with_use_data[local] {
+            match def_use::categorize(context) {
+                Some(DefUse::Def) => self.insert_def(local, location),
+                Some(DefUse::Use) => self.insert_use(local, location),
+                Some(DefUse::Drop) => self.insert_drop(local, location),
+                _ => (),
+            }
+        }
+    }
+}
diff --git a/compiler/rustc_borrowck/src/type_check/liveness/mod.rs b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs
new file mode 100644
index 000000000..d5c401ae1
--- /dev/null
+++ b/compiler/rustc_borrowck/src/type_check/liveness/mod.rs
@@ -0,0 +1,139 @@
+use itertools::{Either, Itertools};
+use rustc_data_structures::fx::FxHashSet;
+use rustc_middle::mir::{Body, Local};
+use rustc_middle::ty::{RegionVid, TyCtxt};
+use rustc_mir_dataflow::impls::MaybeInitializedPlaces;
+use rustc_mir_dataflow::move_paths::MoveData;
+use rustc_mir_dataflow::ResultsCursor;
+use std::rc::Rc;
+
+use crate::{
+    constraints::OutlivesConstraintSet,
+    facts::{AllFacts, AllFactsExt},
+    location::LocationTable,
+    nll::ToRegionVid,
+    region_infer::values::RegionValueElements,
+    universal_regions::UniversalRegions,
+};
+
+use super::TypeChecker;
+
+mod local_use_map;
+mod polonius;
+mod trace;
+
+/// Combines liveness analysis with initialization analysis to
+/// determine which variables are live at which points, both due to
+/// ordinary uses and drops. Returns a set of (ty, location) pairs
+/// that indicate which types must be live at which point in the CFG.
+/// This vector is consumed by `constraint_generation`.
+///
+/// N.B., this computation requires normalization; therefore, it must be
+/// performed before
+pub(super) fn generate<'mir, 'tcx>(
+    typeck: &mut TypeChecker<'_, 'tcx>,
+    body: &Body<'tcx>,
+    elements: &Rc<RegionValueElements>,
+    flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>,
+    move_data: &MoveData<'tcx>,
+    location_table: &LocationTable,
+    use_polonius: bool,
+) {
+    debug!("liveness::generate");
+
+    let free_regions = regions_that_outlive_free_regions(
+        typeck.infcx.num_region_vars(),
+        &typeck.borrowck_context.universal_regions,
+        &typeck.borrowck_context.constraints.outlives_constraints,
+    );
+    let (relevant_live_locals, boring_locals) =
+        compute_relevant_live_locals(typeck.tcx(), &free_regions, &body);
+    let facts_enabled = use_polonius || AllFacts::enabled(typeck.tcx());
+
+    let polonius_drop_used = if facts_enabled {
+        let mut drop_used = Vec::new();
+        polonius::populate_access_facts(typeck, body, location_table, move_data, &mut drop_used);
+        Some(drop_used)
+    } else {
+        None
+    };
+
+    trace::trace(
+        typeck,
+        body,
+        elements,
+        flow_inits,
+        move_data,
+        relevant_live_locals,
+        boring_locals,
+        polonius_drop_used,
+    );
+}
+
+// The purpose of `compute_relevant_live_locals` is to define the subset of `Local`
+// variables for which we need to do a liveness computation. We only need
+// to compute whether a variable `X` is live if that variable contains
+// some region `R` in its type where `R` is not known to outlive a free
+// region (i.e., where `R` may be valid for just a subset of the fn body).
+fn compute_relevant_live_locals<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    free_regions: &FxHashSet<RegionVid>,
+    body: &Body<'tcx>,
+) -> (Vec<Local>, Vec<Local>) {
+    let (boring_locals, relevant_live_locals): (Vec<_>, Vec<_>) =
+        body.local_decls.iter_enumerated().partition_map(|(local, local_decl)| {
+            if tcx.all_free_regions_meet(&local_decl.ty, |r| {
+                free_regions.contains(&r.to_region_vid())
+            }) {
+                Either::Left(local)
+            } else {
+                Either::Right(local)
+            }
+        });
+
+    debug!("{} total variables", body.local_decls.len());
+    debug!("{} variables need liveness", relevant_live_locals.len());
+    debug!("{} regions outlive free regions", free_regions.len());
+
+    (relevant_live_locals, boring_locals)
+}
+
+/// Computes all regions that are (currently) known to outlive free
+/// regions. For these regions, we do not need to compute
+/// liveness, since the outlives constraints will ensure that they
+/// are live over the whole fn body anyhow.
+fn regions_that_outlive_free_regions<'tcx>(
+    num_region_vars: usize,
+    universal_regions: &UniversalRegions<'tcx>,
+    constraint_set: &OutlivesConstraintSet<'tcx>,
+) -> FxHashSet<RegionVid> {
+    // Build a graph of the outlives constraints thus far. This is
+    // a reverse graph, so for each constraint `R1: R2` we have an
+    // edge `R2 -> R1`. Therefore, if we find all regions
+    // reachable from each free region, we will have all the
+    // regions that are forced to outlive some free region.
+    let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars);
+    let fr_static = universal_regions.fr_static;
+    let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static);
+
+    // Stack for the depth-first search. Start out with all the free regions.
+    let mut stack: Vec<_> = universal_regions.universal_regions().collect();
+
+    // Set of all free regions, plus anything that outlives them. Initially
+    // just contains the free regions.
+    let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect();
+
+    // Do the DFS -- for each thing in the stack, find all things
+    // that outlive it and add them to the set. If they are not,
+    // push them onto the stack for later.
+    while let Some(sub_region) = stack.pop() {
+        stack.extend(
+            rev_region_graph
+                .outgoing_regions(sub_region)
+                .filter(|&r| outlives_free_region.insert(r)),
+        );
+    }
+
+    // Return the final set of things we visited.
+    outlives_free_region
+}
diff --git a/compiler/rustc_borrowck/src/type_check/liveness/polonius.rs b/compiler/rustc_borrowck/src/type_check/liveness/polonius.rs
new file mode 100644
index 000000000..bc76a465e
--- /dev/null
+++ b/compiler/rustc_borrowck/src/type_check/liveness/polonius.rs
@@ -0,0 +1,140 @@
+use crate::def_use::{self, DefUse};
+use crate::location::{LocationIndex, LocationTable};
+use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor};
+use rustc_middle::mir::{Body, Local, Location, Place};
+use rustc_middle::ty::subst::GenericArg;
+use rustc_mir_dataflow::move_paths::{LookupResult, MoveData, MovePathIndex};
+
+use super::TypeChecker;
+
+type VarPointRelation = Vec<(Local, LocationIndex)>;
+type PathPointRelation = Vec<(MovePathIndex, LocationIndex)>;
+
+struct UseFactsExtractor<'me, 'tcx> {
+    var_defined_at: &'me mut VarPointRelation,
+    var_used_at: &'me mut VarPointRelation,
+    location_table: &'me LocationTable,
+    var_dropped_at: &'me mut VarPointRelation,
+    move_data: &'me MoveData<'tcx>,
+    path_accessed_at_base: &'me mut PathPointRelation,
+}
+
+// A Visitor to walk through the MIR and extract point-wise facts
+impl UseFactsExtractor<'_, '_> {
+    fn location_to_index(&self, location: Location) -> LocationIndex {
+        self.location_table.mid_index(location)
+    }
+
+    fn insert_def(&mut self, local: Local, location: Location) {
+        debug!("UseFactsExtractor::insert_def()");
+        self.var_defined_at.push((local, self.location_to_index(location)));
+    }
+
+    fn insert_use(&mut self, local: Local, location: Location) {
+        debug!("UseFactsExtractor::insert_use()");
+        self.var_used_at.push((local, self.location_to_index(location)));
+    }
+
+    fn insert_drop_use(&mut self, local: Local, location: Location) {
+        debug!("UseFactsExtractor::insert_drop_use()");
+        self.var_dropped_at.push((local, self.location_to_index(location)));
+    }
+
+    fn insert_path_access(&mut self, path: MovePathIndex, location: Location) {
+        debug!("UseFactsExtractor::insert_path_access({:?}, {:?})", path, location);
+        self.path_accessed_at_base.push((path, self.location_to_index(location)));
+    }
+
+    fn place_to_mpi(&self, place: &Place<'_>) -> Option<MovePathIndex> {
+        match self.move_data.rev_lookup.find(place.as_ref()) {
+            LookupResult::Exact(mpi) => Some(mpi),
+            LookupResult::Parent(mmpi) => mmpi,
+        }
+    }
+}
+
+impl<'a, 'tcx> Visitor<'tcx> for UseFactsExtractor<'a, 'tcx> {
+    fn visit_local(&mut self, local: Local, context: PlaceContext, location: Location) {
+        match def_use::categorize(context) {
+            Some(DefUse::Def) => self.insert_def(local, location),
+            Some(DefUse::Use) => self.insert_use(local, location),
+            Some(DefUse::Drop) => self.insert_drop_use(local, location),
+            _ => (),
+        }
+    }
+
+    fn visit_place(&mut self, place: &Place<'tcx>, context: PlaceContext, location: Location) {
+        self.super_place(place, context, location);
+        match context {
+            PlaceContext::NonMutatingUse(_) => {
+                if let Some(mpi) = self.place_to_mpi(place) {
+                    self.insert_path_access(mpi, location);
+                }
+            }
+
+            PlaceContext::MutatingUse(MutatingUseContext::Borrow) => {
+                if let Some(mpi) = self.place_to_mpi(place) {
+                    self.insert_path_access(mpi, location);
+                }
+            }
+            _ => (),
+        }
+    }
+}
+
+pub(super) fn populate_access_facts<'a, 'tcx>(
+    typeck: &mut TypeChecker<'a, 'tcx>,
+    body: &Body<'tcx>,
+    location_table: &LocationTable,
+    move_data: &MoveData<'tcx>,
+    dropped_at: &mut Vec<(Local, Location)>,
+) {
+    debug!("populate_access_facts()");
+
+    if let Some(facts) = typeck.borrowck_context.all_facts.as_mut() {
+        let mut extractor = UseFactsExtractor {
+            var_defined_at: &mut facts.var_defined_at,
+            var_used_at: &mut facts.var_used_at,
+            var_dropped_at: &mut facts.var_dropped_at,
+            path_accessed_at_base: &mut facts.path_accessed_at_base,
+            location_table,
+            move_data,
+        };
+        extractor.visit_body(&body);
+
+        facts.var_dropped_at.extend(
+            dropped_at.iter().map(|&(local, location)| (local, location_table.mid_index(location))),
+        );
+
+        for (local, local_decl) in body.local_decls.iter_enumerated() {
+            debug!(
+                "add use_of_var_derefs_origin facts - local={:?}, type={:?}",
+                local, local_decl.ty
+            );
+            let _prof_timer = typeck.infcx.tcx.prof.generic_activity("polonius_fact_generation");
+            let universal_regions = &typeck.borrowck_context.universal_regions;
+            typeck.infcx.tcx.for_each_free_region(&local_decl.ty, |region| {
+                let region_vid = universal_regions.to_region_vid(region);
+                facts.use_of_var_derefs_origin.push((local, region_vid));
+            });
+        }
+    }
+}
+
+// For every potentially drop()-touched region `region` in `local`'s type
+// (`kind`), emit a Polonius `use_of_var_derefs_origin(local, origin)` fact.
+pub(super) fn add_drop_of_var_derefs_origin<'tcx>(
+    typeck: &mut TypeChecker<'_, 'tcx>,
+    local: Local,
+    kind: &GenericArg<'tcx>,
+) {
+    debug!("add_drop_of_var_derefs_origin(local={:?}, kind={:?}", local, kind);
+    if let Some(facts) = typeck.borrowck_context.all_facts.as_mut() {
+        let _prof_timer = typeck.infcx.tcx.prof.generic_activity("polonius_fact_generation");
+        let universal_regions = &typeck.borrowck_context.universal_regions;
+        typeck.infcx.tcx.for_each_free_region(kind, |drop_live_region| {
+            let region_vid = universal_regions.to_region_vid(drop_live_region);
+            facts.drop_of_var_derefs_origin.push((local, region_vid));
+        });
+    }
+}
diff --git a/compiler/rustc_borrowck/src/type_check/liveness/trace.rs b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs
new file mode 100644
index 000000000..42b577175
--- /dev/null
+++ b/compiler/rustc_borrowck/src/type_check/liveness/trace.rs
@@ -0,0 +1,578 @@
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_index::bit_set::HybridBitSet;
+use rustc_index::interval::IntervalSet;
+use rustc_infer::infer::canonical::QueryRegionConstraints;
+use rustc_middle::mir::{BasicBlock, Body, ConstraintCategory, Local, Location};
+use rustc_middle::ty::{Ty, TypeVisitable};
+use rustc_trait_selection::traits::query::dropck_outlives::DropckOutlivesResult;
+use rustc_trait_selection::traits::query::type_op::outlives::DropckOutlives;
+use rustc_trait_selection::traits::query::type_op::{TypeOp, TypeOpOutput};
+use std::rc::Rc;
+
+use rustc_mir_dataflow::impls::MaybeInitializedPlaces;
+use rustc_mir_dataflow::move_paths::{HasMoveData, MoveData, MovePathIndex};
+use rustc_mir_dataflow::ResultsCursor;
+
+use crate::{
+    region_infer::values::{self, PointIndex, RegionValueElements},
+    type_check::liveness::local_use_map::LocalUseMap,
+    type_check::liveness::polonius,
+    type_check::NormalizeLocation,
+    type_check::TypeChecker,
+};
+
+/// This is the heart of the liveness computation. For each variable X
+/// that requires a liveness computation, it walks over all the uses
+/// of X and does a reverse depth-first search ("trace") through the
+/// MIR. This search stops when we find a definition of that variable.
+/// The points visited in this search is the USE-LIVE set for the variable;
+/// of those points is added to all the regions that appear in the variable's
+/// type.
+///
+/// We then also walks through each *drop* of those variables and does
+/// another search, stopping when we reach a use or definition. This
+/// is the DROP-LIVE set of points. Each of the points in the
+/// DROP-LIVE set are to the liveness sets for regions found in the
+/// `dropck_outlives` result of the variable's type (in particular,
+/// this respects `#[may_dangle]` annotations).
+pub(super) fn trace<'mir, 'tcx>(
+    typeck: &mut TypeChecker<'_, 'tcx>,
+    body: &Body<'tcx>,
+    elements: &Rc<RegionValueElements>,
+    flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>,
+    move_data: &MoveData<'tcx>,
+    relevant_live_locals: Vec<Local>,
+    boring_locals: Vec<Local>,
+    polonius_drop_used: Option<Vec<(Local, Location)>>,
+) {
+    debug!("trace()");
+
+    let local_use_map = &LocalUseMap::build(&relevant_live_locals, elements, body);
+
+    let cx = LivenessContext {
+        typeck,
+        body,
+        flow_inits,
+        elements,
+        local_use_map,
+        move_data,
+        drop_data: FxHashMap::default(),
+    };
+
+    let mut results = LivenessResults::new(cx);
+
+    if let Some(drop_used) = polonius_drop_used {
+        results.add_extra_drop_facts(drop_used, relevant_live_locals.iter().copied().collect())
+    }
+
+    results.compute_for_all_locals(relevant_live_locals);
+
+    results.dropck_boring_locals(boring_locals);
+}
+
+/// Contextual state for the type-liveness generator.
+struct LivenessContext<'me, 'typeck, 'flow, 'tcx> {
+    /// Current type-checker, giving us our inference context etc.
+    typeck: &'me mut TypeChecker<'typeck, 'tcx>,
+
+    /// Defines the `PointIndex` mapping
+    elements: &'me RegionValueElements,
+
+    /// MIR we are analyzing.
+    body: &'me Body<'tcx>,
+
+    /// Mapping to/from the various indices used for initialization tracking.
+    move_data: &'me MoveData<'tcx>,
+
+    /// Cache for the results of `dropck_outlives` query.
+    drop_data: FxHashMap<Ty<'tcx>, DropData<'tcx>>,
+
+    /// Results of dataflow tracking which variables (and paths) have been
+    /// initialized.
+    flow_inits: &'me mut ResultsCursor<'flow, 'tcx, MaybeInitializedPlaces<'flow, 'tcx>>,
+
+    /// Index indicating where each variable is assigned, used, or
+    /// dropped.
+    local_use_map: &'me LocalUseMap,
+}
+
+struct DropData<'tcx> {
+    dropck_result: DropckOutlivesResult<'tcx>,
+    region_constraint_data: Option<&'tcx QueryRegionConstraints<'tcx>>,
+}
+
+struct LivenessResults<'me, 'typeck, 'flow, 'tcx> {
+    cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>,
+
+    /// Set of points that define the current local.
+    defs: HybridBitSet<PointIndex>,
+
+    /// Points where the current variable is "use live" -- meaning
+    /// that there is a future "full use" that may use its value.
+    use_live_at: IntervalSet<PointIndex>,
+
+    /// Points where the current variable is "drop live" -- meaning
+    /// that there is no future "full use" that may use its value, but
+    /// there is a future drop.
+    drop_live_at: IntervalSet<PointIndex>,
+
+    /// Locations where drops may occur.
+    drop_locations: Vec<Location>,
+
+    /// Stack used when doing (reverse) DFS.
+    stack: Vec<PointIndex>,
+}
+
+impl<'me, 'typeck, 'flow, 'tcx> LivenessResults<'me, 'typeck, 'flow, 'tcx> {
+    fn new(cx: LivenessContext<'me, 'typeck, 'flow, 'tcx>) -> Self {
+        let num_points = cx.elements.num_points();
+        LivenessResults {
+            cx,
+            defs: HybridBitSet::new_empty(num_points),
+            use_live_at: IntervalSet::new(num_points),
+            drop_live_at: IntervalSet::new(num_points),
+            drop_locations: vec![],
+            stack: vec![],
+        }
+    }
+
+    fn compute_for_all_locals(&mut self, relevant_live_locals: Vec<Local>) {
+        for local in relevant_live_locals {
+            self.reset_local_state();
+            self.add_defs_for(local);
+            self.compute_use_live_points_for(local);
+            self.compute_drop_live_points_for(local);
+
+            let local_ty = self.cx.body.local_decls[local].ty;
+
+            if !self.use_live_at.is_empty() {
+                self.cx.add_use_live_facts_for(local_ty, &self.use_live_at);
+            }
+
+            if !self.drop_live_at.is_empty() {
+                self.cx.add_drop_live_facts_for(
+                    local,
+                    local_ty,
+                    &self.drop_locations,
+                    &self.drop_live_at,
+                );
+            }
+        }
+    }
+
+    // Runs dropck for locals whose liveness isn't relevant. This is
+    // necessary to eagerly detect unbound recursion during drop glue computation.
+    fn dropck_boring_locals(&mut self, boring_locals: Vec<Local>) {
+        for local in boring_locals {
+            let local_ty = self.cx.body.local_decls[local].ty;
+            let drop_data = self.cx.drop_data.entry(local_ty).or_insert_with({
+                let typeck = &mut self.cx.typeck;
+                move || LivenessContext::compute_drop_data(typeck, local_ty)
+            });
+
+            drop_data.dropck_result.report_overflows(
+                self.cx.typeck.infcx.tcx,
+                self.cx.body.local_decls[local].source_info.span,
+                local_ty,
+            );
+        }
+    }
+
+    /// Add extra drop facts needed for Polonius.
+    ///
+    /// Add facts for all locals with free regions, since regions may outlive
+    /// the function body only at certain nodes in the CFG.
+    fn add_extra_drop_facts(
+        &mut self,
+        drop_used: Vec<(Local, Location)>,
+        relevant_live_locals: FxHashSet<Local>,
+    ) {
+        let locations = IntervalSet::new(self.cx.elements.num_points());
+
+        for (local, location) in drop_used {
+            if !relevant_live_locals.contains(&local) {
+                let local_ty = self.cx.body.local_decls[local].ty;
+                if local_ty.has_free_regions() {
+                    self.cx.add_drop_live_facts_for(local, local_ty, &[location], &locations);
+                }
+            }
+        }
+    }
+
+    /// Clear the value of fields that are "per local variable".
+    fn reset_local_state(&mut self) {
+        self.defs.clear();
+        self.use_live_at.clear();
+        self.drop_live_at.clear();
+        self.drop_locations.clear();
+        assert!(self.stack.is_empty());
+    }
+
+    /// Adds the definitions of `local` into `self.defs`.
+    fn add_defs_for(&mut self, local: Local) {
+        for def in self.cx.local_use_map.defs(local) {
+            debug!("- defined at {:?}", def);
+            self.defs.insert(def);
+        }
+    }
+
+    /// Computes all points where local is "use live" -- meaning its
+    /// current value may be used later (except by a drop). This is
+    /// done by walking backwards from each use of `local` until we
+    /// find a `def` of local.
+    ///
+    /// Requires `add_defs_for(local)` to have been executed.
+    fn compute_use_live_points_for(&mut self, local: Local) {
+        debug!("compute_use_live_points_for(local={:?})", local);
+
+        self.stack.extend(self.cx.local_use_map.uses(local));
+        while let Some(p) = self.stack.pop() {
+            // We are live in this block from the closest to us of:
+            //
+            //  * Inclusively, the block start
+            //  * Exclusively, the previous definition (if it's in this block)
+            //  * Exclusively, the previous live_at setting (an optimization)
+            let block_start = self.cx.elements.to_block_start(p);
+            let previous_defs = self.defs.last_set_in(block_start..=p);
+            let previous_live_at = self.use_live_at.last_set_in(block_start..=p);
+
+            let exclusive_start = match (previous_defs, previous_live_at) {
+                (Some(a), Some(b)) => Some(std::cmp::max(a, b)),
+                (Some(a), None) | (None, Some(a)) => Some(a),
+                (None, None) => None,
+            };
+
+            if let Some(exclusive) = exclusive_start {
+                self.use_live_at.insert_range(exclusive + 1..=p);
+
+                // If we have a bound after the start of the block, we should
+                // not add the predecessors for this block.
+                continue;
+            } else {
+                // Add all the elements of this block.
+                self.use_live_at.insert_range(block_start..=p);
+
+                // Then add the predecessors for this block, which are the
+                // terminators of predecessor basic blocks. Push those onto the
+                // stack so that the next iteration(s) will process them.
+
+                let block = self.cx.elements.to_location(block_start).block;
+                self.stack.extend(
+                    self.cx.body.basic_blocks.predecessors()[block]
+                        .iter()
+                        .map(|&pred_bb| self.cx.body.terminator_loc(pred_bb))
+                        .map(|pred_loc| self.cx.elements.point_from_location(pred_loc)),
+                );
+            }
+        }
+    }
+
+    /// Computes all points where local is "drop live" -- meaning its
+    /// current value may be dropped later (but not used). This is
+    /// done by iterating over the drops of `local` where `local` (or
+    /// some subpart of `local`) is initialized. For each such drop,
+    /// we walk backwards until we find a point where `local` is
+    /// either defined or use-live.
+    ///
+    /// Requires `compute_use_live_points_for` and `add_defs_for` to
+    /// have been executed.
+    fn compute_drop_live_points_for(&mut self, local: Local) {
+        debug!("compute_drop_live_points_for(local={:?})", local);
+
+        let mpi = self.cx.move_data.rev_lookup.find_local(local);
+        debug!("compute_drop_live_points_for: mpi = {:?}", mpi);
+
+        // Find the drops where `local` is initialized.
+        for drop_point in self.cx.local_use_map.drops(local) {
+            let location = self.cx.elements.to_location(drop_point);
+            debug_assert_eq!(self.cx.body.terminator_loc(location.block), location,);
+
+            if self.cx.initialized_at_terminator(location.block, mpi) {
+                if self.drop_live_at.insert(drop_point) {
+                    self.drop_locations.push(location);
+                    self.stack.push(drop_point);
+                }
+            }
+        }
+
+        debug!("compute_drop_live_points_for: drop_locations={:?}", self.drop_locations);
+
+        // Reverse DFS. But for drops, we do it a bit differently.
+        // The stack only ever stores *terminators of blocks*. Within
+        // a block, we walk back the statements in an inner loop.
+        while let Some(term_point) = self.stack.pop() {
+            self.compute_drop_live_points_for_block(mpi, term_point);
+        }
+    }
+
+    /// Executes one iteration of the drop-live analysis loop.
+    ///
+    /// The parameter `mpi` is the `MovePathIndex` of the local variable
+    /// we are currently analyzing.
+    ///
+    /// The point `term_point` represents some terminator in the MIR,
+    /// where the local `mpi` is drop-live on entry to that terminator.
+    ///
+    /// This method adds all drop-live points within the block and --
+    /// where applicable -- pushes the terminators of preceding blocks
+    /// onto `self.stack`.
+    fn compute_drop_live_points_for_block(&mut self, mpi: MovePathIndex, term_point: PointIndex) {
+        debug!(
+            "compute_drop_live_points_for_block(mpi={:?}, term_point={:?})",
+            self.cx.move_data.move_paths[mpi].place,
+            self.cx.elements.to_location(term_point),
+        );
+
+        // We are only invoked with terminators where `mpi` is
+        // drop-live on entry.
+        debug_assert!(self.drop_live_at.contains(term_point));
+
+        // Otherwise, scan backwards through the statements in the
+        // block.  One of them may be either a definition or use
+        // live point.
+        let term_location = self.cx.elements.to_location(term_point);
+        debug_assert_eq!(self.cx.body.terminator_loc(term_location.block), term_location,);
+        let block = term_location.block;
+        let entry_point = self.cx.elements.entry_point(term_location.block);
+        for p in (entry_point..term_point).rev() {
+            debug!("compute_drop_live_points_for_block: p = {:?}", self.cx.elements.to_location(p));
+
+            if self.defs.contains(p) {
+                debug!("compute_drop_live_points_for_block: def site");
+                return;
+            }
+
+            if self.use_live_at.contains(p) {
+                debug!("compute_drop_live_points_for_block: use-live at {:?}", p);
+                return;
+            }
+
+            if !self.drop_live_at.insert(p) {
+                debug!("compute_drop_live_points_for_block: already drop-live");
+                return;
+            }
+        }
+
+        let body = self.cx.body;
+        for &pred_block in body.basic_blocks.predecessors()[block].iter() {
+            debug!("compute_drop_live_points_for_block: pred_block = {:?}", pred_block,);
+
+            // Check whether the variable is (at least partially)
+            // initialized at the exit of this predecessor. If so, we
+            // want to enqueue it on our list. If not, go check the
+            // next block.
+            //
+            // Note that we only need to check whether `live_local`
+            // became de-initialized at basic block boundaries. If it
+            // were to become de-initialized within the block, that
+            // would have been a "use-live" transition in the earlier
+            // loop, and we'd have returned already.
+            //
+            // NB. It's possible that the pred-block ends in a call
+            // which stores to the variable; in that case, the
+            // variable may be uninitialized "at exit" because this
+            // call only considers the *unconditional effects* of the
+            // terminator. *But*, in that case, the terminator is also
+            // a *definition* of the variable, in which case we want
+            // to stop the search anyhow. (But see Note 1 below.)
+            if !self.cx.initialized_at_exit(pred_block, mpi) {
+                debug!("compute_drop_live_points_for_block: not initialized");
+                continue;
+            }
+
+            let pred_term_loc = self.cx.body.terminator_loc(pred_block);
+            let pred_term_point = self.cx.elements.point_from_location(pred_term_loc);
+
+            // If the terminator of this predecessor either *assigns*
+            // our value or is a "normal use", then stop.
+            if self.defs.contains(pred_term_point) {
+                debug!("compute_drop_live_points_for_block: defined at {:?}", pred_term_loc);
+                continue;
+            }
+
+            if self.use_live_at.contains(pred_term_point) {
+                debug!("compute_drop_live_points_for_block: use-live at {:?}", pred_term_loc);
+                continue;
+            }
+
+            // Otherwise, we are drop-live on entry to the terminator,
+            // so walk it.
+            if self.drop_live_at.insert(pred_term_point) {
+                debug!("compute_drop_live_points_for_block: pushed to stack");
+                self.stack.push(pred_term_point);
+            }
+        }
+
+        // Note 1. There is a weird scenario that you might imagine
+        // being problematic here, but which actually cannot happen.
+        // The problem would be if we had a variable that *is* initialized
+        // (but dead) on entry to the terminator, and where the current value
+        // will be dropped in the case of unwind. In that case, we ought to
+        // consider `X` to be drop-live in between the last use and call.
+        // Here is the example:
+        //
+        // ```
+        // BB0 {
+        //   X = ...
+        //   use(X); // last use
+        //   ...     // <-- X ought to be drop-live here
+        //   X = call() goto BB1 unwind BB2
+        // }
+        //
+        // BB1 {
+        //   DROP(X)
+        // }
+        //
+        // BB2 {
+        //   DROP(X)
+        // }
+        // ```
+        //
+        // However, the current code would, when walking back from BB2,
+        // simply stop and never explore BB0. This seems bad! But it turns
+        // out this code is flawed anyway -- note that the existing value of
+        // `X` would leak in the case where unwinding did *not* occur.
+        //
+        // What we *actually* generate is a store to a temporary
+        // for the call (`TMP = call()...`) and then a
+        // `DropAndReplace` to swap that with `X`
+        // (`DropAndReplace` has very particular semantics).
+    }
+}
+
+impl<'tcx> LivenessContext<'_, '_, '_, 'tcx> {
+    /// Returns `true` if the local variable (or some part of it) is initialized at the current
+    /// cursor position. Callers should call one of the `seek` methods immediately before to point
+    /// the cursor to the desired location.
+    fn initialized_at_curr_loc(&self, mpi: MovePathIndex) -> bool {
+        let state = self.flow_inits.get();
+        if state.contains(mpi) {
+            return true;
+        }
+
+        let move_paths = &self.flow_inits.analysis().move_data().move_paths;
+        move_paths[mpi].find_descendant(&move_paths, |mpi| state.contains(mpi)).is_some()
+    }
+
+    /// Returns `true` if the local variable (or some part of it) is initialized in
+    /// the terminator of `block`. We need to check this to determine if a
+    /// DROP of some local variable will have an effect -- note that
+    /// drops, as they may unwind, are always terminators.
+    fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
+        self.flow_inits.seek_before_primary_effect(self.body.terminator_loc(block));
+        self.initialized_at_curr_loc(mpi)
+    }
+
+    /// Returns `true` if the path `mpi` (or some part of it) is initialized at
+    /// the exit of `block`.
+    ///
+    /// **Warning:** Does not account for the result of `Call`
+    /// instructions.
+    fn initialized_at_exit(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
+        self.flow_inits.seek_after_primary_effect(self.body.terminator_loc(block));
+        self.initialized_at_curr_loc(mpi)
+    }
+
+    /// Stores the result that all regions in `value` are live for the
+    /// points `live_at`.
+    fn add_use_live_facts_for(
+        &mut self,
+        value: impl TypeVisitable<'tcx>,
+        live_at: &IntervalSet<PointIndex>,
+    ) {
+        debug!("add_use_live_facts_for(value={:?})", value);
+
+        Self::make_all_regions_live(self.elements, &mut self.typeck, value, live_at)
+    }
+
+    /// Some variable with type `live_ty` is "drop live" at `location`
+    /// -- i.e., it may be dropped later. This means that *some* of
+    /// the regions in its type must be live at `location`. The
+    /// precise set will depend on the dropck constraints, and in
+    /// particular this takes `#[may_dangle]` into account.
+    fn add_drop_live_facts_for(
+        &mut self,
+        dropped_local: Local,
+        dropped_ty: Ty<'tcx>,
+        drop_locations: &[Location],
+        live_at: &IntervalSet<PointIndex>,
+    ) {
+        debug!(
+            "add_drop_live_constraint(\
+             dropped_local={:?}, \
+             dropped_ty={:?}, \
+             drop_locations={:?}, \
+             live_at={:?})",
+            dropped_local,
+            dropped_ty,
+            drop_locations,
+            values::location_set_str(self.elements, live_at.iter()),
+        );
+
+        let drop_data = self.drop_data.entry(dropped_ty).or_insert_with({
+            let typeck = &mut self.typeck;
+            move || Self::compute_drop_data(typeck, dropped_ty)
+        });
+
+        if let Some(data) = &drop_data.region_constraint_data {
+            for &drop_location in drop_locations {
+                self.typeck.push_region_constraints(
+                    drop_location.to_locations(),
+                    ConstraintCategory::Boring,
+                    data,
+                );
+            }
+        }
+
+        drop_data.dropck_result.report_overflows(
+            self.typeck.infcx.tcx,
+            self.body.source_info(*drop_locations.first().unwrap()).span,
+            dropped_ty,
+        );
+
+        // All things in the `outlives` array may be touched by
+        // the destructor and must be live at this point.
+        for &kind in &drop_data.dropck_result.kinds {
+            Self::make_all_regions_live(self.elements, &mut self.typeck, kind, live_at);
+
+            polonius::add_drop_of_var_derefs_origin(&mut self.typeck, dropped_local, &kind);
+        }
+    }
+
+    fn make_all_regions_live(
+        elements: &RegionValueElements,
+        typeck: &mut TypeChecker<'_, 'tcx>,
+        value: impl TypeVisitable<'tcx>,
+        live_at: &IntervalSet<PointIndex>,
+    ) {
+        debug!("make_all_regions_live(value={:?})", value);
+        debug!(
+            "make_all_regions_live: live_at={}",
+            values::location_set_str(elements, live_at.iter()),
+        );
+
+        let tcx = typeck.tcx();
+        tcx.for_each_free_region(&value, |live_region| {
+            let live_region_vid =
+                typeck.borrowck_context.universal_regions.to_region_vid(live_region);
+            typeck
+                .borrowck_context
+                .constraints
+                .liveness_constraints
+                .add_elements(live_region_vid, live_at);
+        });
+    }
+
+    fn compute_drop_data(
+        typeck: &mut TypeChecker<'_, 'tcx>,
+        dropped_ty: Ty<'tcx>,
+    ) -> DropData<'tcx> {
+        debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,);
+
+        let param_env = typeck.param_env;
+        let TypeOpOutput { output, constraints, .. } =
+            param_env.and(DropckOutlives::new(dropped_ty)).fully_perform(typeck.infcx).unwrap();
+
+        DropData { dropck_result: output, region_constraint_data: constraints }
+    }
+}