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, 975 insertions, 0 deletions

diff --git a/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/cfg_build.rs b/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/cfg_build.rs
new file mode 100644
index 000000000..a2c23db16
--- /dev/null
+++ b/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/cfg_build.rs
@@ -0,0 +1,560 @@
+use super::{
+    for_each_consumable, record_consumed_borrow::ConsumedAndBorrowedPlaces, DropRangesBuilder,
+    NodeInfo, PostOrderId, TrackedValue, TrackedValueIndex,
+};
+use hir::{
+    intravisit::{self, Visitor},
+    Body, Expr, ExprKind, Guard, HirId, LoopIdError,
+};
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_hir as hir;
+use rustc_index::vec::IndexVec;
+use rustc_middle::{
+    hir::map::Map,
+    ty::{TyCtxt, TypeckResults},
+};
+use std::mem::swap;
+
+/// Traverses the body to find the control flow graph and locations for the
+/// relevant places are dropped or reinitialized.
+///
+/// The resulting structure still needs to be iterated to a fixed point, which
+/// can be done with propagate_to_fixpoint in cfg_propagate.
+pub(super) fn build_control_flow_graph<'tcx>(
+    hir: Map<'tcx>,
+    tcx: TyCtxt<'tcx>,
+    typeck_results: &TypeckResults<'tcx>,
+    consumed_borrowed_places: ConsumedAndBorrowedPlaces,
+    body: &'tcx Body<'tcx>,
+    num_exprs: usize,
+) -> (DropRangesBuilder, FxHashSet<HirId>) {
+    let mut drop_range_visitor =
+        DropRangeVisitor::new(hir, tcx, typeck_results, consumed_borrowed_places, num_exprs);
+    intravisit::walk_body(&mut drop_range_visitor, body);
+
+    drop_range_visitor.drop_ranges.process_deferred_edges();
+    if let Some(filename) = &tcx.sess.opts.unstable_opts.dump_drop_tracking_cfg {
+        super::cfg_visualize::write_graph_to_file(&drop_range_visitor.drop_ranges, filename, tcx);
+    }
+
+    (drop_range_visitor.drop_ranges, drop_range_visitor.places.borrowed_temporaries)
+}
+
+/// This struct is used to gather the information for `DropRanges` to determine the regions of the
+/// HIR tree for which a value is dropped.
+///
+/// We are interested in points where a variables is dropped or initialized, and the control flow
+/// of the code. We identify locations in code by their post-order traversal index, so it is
+/// important for this traversal to match that in `RegionResolutionVisitor` and `InteriorVisitor`.
+///
+/// We make several simplifying assumptions, with the goal of being more conservative than
+/// necessary rather than less conservative (since being less conservative is unsound, but more
+/// conservative is still safe). These assumptions are:
+///
+/// 1. Moving a variable `a` counts as a move of the whole variable.
+/// 2. Moving a partial path like `a.b.c` is ignored.
+/// 3. Reinitializing through a field (e.g. `a.b.c = 5`) counts as a reinitialization of all of
+///    `a`.
+///
+/// Some examples:
+///
+/// Rule 1:
+/// ```rust
+/// let mut a = (vec![0], vec![0]);
+/// drop(a);
+/// // `a` is not considered initialized.
+/// ```
+///
+/// Rule 2:
+/// ```rust
+/// let mut a = (vec![0], vec![0]);
+/// drop(a.0);
+/// drop(a.1);
+/// // `a` is still considered initialized.
+/// ```
+///
+/// Rule 3:
+/// ```compile_fail,E0382
+/// let mut a = (vec![0], vec![0]);
+/// drop(a);
+/// a.1 = vec![1];
+/// // all of `a` is considered initialized
+/// ```
+
+struct DropRangeVisitor<'a, 'tcx> {
+    hir: Map<'tcx>,
+    places: ConsumedAndBorrowedPlaces,
+    drop_ranges: DropRangesBuilder,
+    expr_index: PostOrderId,
+    tcx: TyCtxt<'tcx>,
+    typeck_results: &'a TypeckResults<'tcx>,
+    label_stack: Vec<(Option<rustc_ast::Label>, PostOrderId)>,
+}
+
+impl<'a, 'tcx> DropRangeVisitor<'a, 'tcx> {
+    fn new(
+        hir: Map<'tcx>,
+        tcx: TyCtxt<'tcx>,
+        typeck_results: &'a TypeckResults<'tcx>,
+        places: ConsumedAndBorrowedPlaces,
+        num_exprs: usize,
+    ) -> Self {
+        debug!("consumed_places: {:?}", places.consumed);
+        let drop_ranges = DropRangesBuilder::new(
+            places.consumed.iter().flat_map(|(_, places)| places.iter().cloned()),
+            hir,
+            num_exprs,
+        );
+        Self {
+            hir,
+            places,
+            drop_ranges,
+            expr_index: PostOrderId::from_u32(0),
+            typeck_results,
+            tcx,
+            label_stack: vec![],
+        }
+    }
+
+    fn record_drop(&mut self, value: TrackedValue) {
+        if self.places.borrowed.contains(&value) {
+            debug!("not marking {:?} as dropped because it is borrowed at some point", value);
+        } else {
+            debug!("marking {:?} as dropped at {:?}", value, self.expr_index);
+            let count = self.expr_index;
+            self.drop_ranges.drop_at(value, count);
+        }
+    }
+
+    /// ExprUseVisitor's consume callback doesn't go deep enough for our purposes in all
+    /// expressions. This method consumes a little deeper into the expression when needed.
+    fn consume_expr(&mut self, expr: &hir::Expr<'_>) {
+        debug!("consuming expr {:?}, count={:?}", expr.kind, self.expr_index);
+        let places = self
+            .places
+            .consumed
+            .get(&expr.hir_id)
+            .map_or(vec![], |places| places.iter().cloned().collect());
+        for place in places {
+            trace!(?place, "consuming place");
+            for_each_consumable(self.hir, place, |value| self.record_drop(value));
+        }
+    }
+
+    /// Marks an expression as being reinitialized.
+    ///
+    /// Note that we always approximated on the side of things being more
+    /// initialized than they actually are, as opposed to less. In cases such
+    /// as `x.y = ...`, we would consider all of `x` as being initialized
+    /// instead of just the `y` field.
+    ///
+    /// This is because it is always safe to consider something initialized
+    /// even when it is not, but the other way around will cause problems.
+    ///
+    /// In the future, we will hopefully tighten up these rules to be more
+    /// precise.
+    fn reinit_expr(&mut self, expr: &hir::Expr<'_>) {
+        // Walk the expression to find the base. For example, in an expression
+        // like `*a[i].x`, we want to find the `a` and mark that as
+        // reinitialized.
+        match expr.kind {
+            ExprKind::Path(hir::QPath::Resolved(
+                _,
+                hir::Path { res: hir::def::Res::Local(hir_id), .. },
+            )) => {
+                // This is the base case, where we have found an actual named variable.
+
+                let location = self.expr_index;
+                debug!("reinitializing {:?} at {:?}", hir_id, location);
+                self.drop_ranges.reinit_at(TrackedValue::Variable(*hir_id), location);
+            }
+
+            ExprKind::Field(base, _) => self.reinit_expr(base),
+
+            // Most expressions do not refer to something where we need to track
+            // reinitializations.
+            //
+            // Some of these may be interesting in the future
+            ExprKind::Path(..)
+            | ExprKind::Box(..)
+            | ExprKind::ConstBlock(..)
+            | ExprKind::Array(..)
+            | ExprKind::Call(..)
+            | ExprKind::MethodCall(..)
+            | ExprKind::Tup(..)
+            | ExprKind::Binary(..)
+            | ExprKind::Unary(..)
+            | ExprKind::Lit(..)
+            | ExprKind::Cast(..)
+            | ExprKind::Type(..)
+            | ExprKind::DropTemps(..)
+            | ExprKind::Let(..)
+            | ExprKind::If(..)
+            | ExprKind::Loop(..)
+            | ExprKind::Match(..)
+            | ExprKind::Closure { .. }
+            | ExprKind::Block(..)
+            | ExprKind::Assign(..)
+            | ExprKind::AssignOp(..)
+            | ExprKind::Index(..)
+            | ExprKind::AddrOf(..)
+            | ExprKind::Break(..)
+            | ExprKind::Continue(..)
+            | ExprKind::Ret(..)
+            | ExprKind::InlineAsm(..)
+            | ExprKind::Struct(..)
+            | ExprKind::Repeat(..)
+            | ExprKind::Yield(..)
+            | ExprKind::Err => (),
+        }
+    }
+
+    /// For an expression with an uninhabited return type (e.g. a function that returns !),
+    /// this adds a self edge to to the CFG to model the fact that the function does not
+    /// return.
+    fn handle_uninhabited_return(&mut self, expr: &Expr<'tcx>) {
+        let ty = self.typeck_results.expr_ty(expr);
+        let ty = self.tcx.erase_regions(ty);
+        let m = self.tcx.parent_module(expr.hir_id).to_def_id();
+        let param_env = self.tcx.param_env(m.expect_local());
+        if self.tcx.is_ty_uninhabited_from(m, ty, param_env) {
+            // This function will not return. We model this fact as an infinite loop.
+            self.drop_ranges.add_control_edge(self.expr_index + 1, self.expr_index + 1);
+        }
+    }
+
+    /// Map a Destination to an equivalent expression node
+    ///
+    /// The destination field of a Break or Continue expression can target either an
+    /// expression or a block. The drop range analysis, however, only deals in
+    /// expression nodes, so blocks that might be the destination of a Break or Continue
+    /// will not have a PostOrderId.
+    ///
+    /// If the destination is an expression, this function will simply return that expression's
+    /// hir_id. If the destination is a block, this function will return the hir_id of last
+    /// expression in the block.
+    fn find_target_expression_from_destination(
+        &self,
+        destination: hir::Destination,
+    ) -> Result<HirId, LoopIdError> {
+        destination.target_id.map(|target| {
+            let node = self.hir.get(target);
+            match node {
+                hir::Node::Expr(_) => target,
+                hir::Node::Block(b) => find_last_block_expression(b),
+                hir::Node::Param(..)
+                | hir::Node::Item(..)
+                | hir::Node::ForeignItem(..)
+                | hir::Node::TraitItem(..)
+                | hir::Node::ImplItem(..)
+                | hir::Node::Variant(..)
+                | hir::Node::Field(..)
+                | hir::Node::AnonConst(..)
+                | hir::Node::Stmt(..)
+                | hir::Node::PathSegment(..)
+                | hir::Node::Ty(..)
+                | hir::Node::TypeBinding(..)
+                | hir::Node::TraitRef(..)
+                | hir::Node::Pat(..)
+                | hir::Node::Arm(..)
+                | hir::Node::Local(..)
+                | hir::Node::Ctor(..)
+                | hir::Node::Lifetime(..)
+                | hir::Node::GenericParam(..)
+                | hir::Node::Crate(..)
+                | hir::Node::Infer(..) => bug!("Unsupported branch target: {:?}", node),
+            }
+        })
+    }
+}
+
+fn find_last_block_expression(block: &hir::Block<'_>) -> HirId {
+    block.expr.map_or_else(
+        // If there is no tail expression, there will be at least one statement in the
+        // block because the block contains a break or continue statement.
+        || block.stmts.last().unwrap().hir_id,
+        |expr| expr.hir_id,
+    )
+}
+
+impl<'a, 'tcx> Visitor<'tcx> for DropRangeVisitor<'a, 'tcx> {
+    fn visit_expr(&mut self, expr: &'tcx Expr<'tcx>) {
+        let mut reinit = None;
+        match expr.kind {
+            ExprKind::Assign(lhs, rhs, _) => {
+                self.visit_expr(lhs);
+                self.visit_expr(rhs);
+
+                reinit = Some(lhs);
+            }
+
+            ExprKind::If(test, if_true, if_false) => {
+                self.visit_expr(test);
+
+                let fork = self.expr_index;
+
+                self.drop_ranges.add_control_edge(fork, self.expr_index + 1);
+                self.visit_expr(if_true);
+                let true_end = self.expr_index;
+
+                self.drop_ranges.add_control_edge(fork, self.expr_index + 1);
+                if let Some(if_false) = if_false {
+                    self.visit_expr(if_false);
+                }
+
+                self.drop_ranges.add_control_edge(true_end, self.expr_index + 1);
+            }
+            ExprKind::Match(scrutinee, arms, ..) => {
+                // We walk through the match expression almost like a chain of if expressions.
+                // Here's a diagram to follow along with:
+                //
+                //           ┌─┐
+                //     match │A│ {
+                //       ┌───┴─┘
+                //       │
+                //      ┌▼┌───►┌─┐   ┌─┐
+                //      │B│ if │C│ =>│D│,
+                //      └─┘    ├─┴──►└─┴──────┐
+                //          ┌──┘              │
+                //       ┌──┘                 │
+                //       │                    │
+                //      ┌▼┌───►┌─┐   ┌─┐      │
+                //      │E│ if │F│ =>│G│,     │
+                //      └─┘    ├─┴──►└─┴┐     │
+                //             │        │     │
+                //     }       ▼        ▼     │
+                //     ┌─┐◄───────────────────┘
+                //     │H│
+                //     └─┘
+                //
+                // The order we want is that the scrutinee (A) flows into the first pattern (B),
+                // which flows into the guard (C). Then the guard either flows into the arm body
+                // (D) or into the start of the next arm (E). Finally, the body flows to the end
+                // of the match block (H).
+                //
+                // The subsequent arms follow the same ordering. First we go to the pattern, then
+                // the guard (if present, otherwise it flows straight into the body), then into
+                // the body and then to the end of the match expression.
+                //
+                // The comments below show which edge is being added.
+                self.visit_expr(scrutinee);
+
+                let (guard_exit, arm_end_ids) = arms.iter().fold(
+                    (self.expr_index, vec![]),
+                    |(incoming_edge, mut arm_end_ids), hir::Arm { pat, body, guard, .. }| {
+                        // A -> B, or C -> E
+                        self.drop_ranges.add_control_edge(incoming_edge, self.expr_index + 1);
+                        self.visit_pat(pat);
+                        // B -> C and E -> F are added implicitly due to the traversal order.
+                        match guard {
+                            Some(Guard::If(expr)) => self.visit_expr(expr),
+                            Some(Guard::IfLet(let_expr)) => {
+                                self.visit_let_expr(let_expr);
+                            }
+                            None => (),
+                        }
+                        // Likewise, C -> D and F -> G are added implicitly.
+
+                        // Save C, F, so we can add the other outgoing edge.
+                        let to_next_arm = self.expr_index;
+
+                        // The default edge does not get added since we also have an explicit edge,
+                        // so we also need to add an edge to the next node as well.
+                        //
+                        // This adds C -> D, F -> G
+                        self.drop_ranges.add_control_edge(self.expr_index, self.expr_index + 1);
+                        self.visit_expr(body);
+
+                        // Save the end of the body so we can add the exit edge once we know where
+                        // the exit is.
+                        arm_end_ids.push(self.expr_index);
+
+                        // Pass C to the next iteration, as well as vec![D]
+                        //
+                        // On the last round through, we pass F and vec![D, G] so that we can
+                        // add all the exit edges.
+                        (to_next_arm, arm_end_ids)
+                    },
+                );
+                // F -> H
+                self.drop_ranges.add_control_edge(guard_exit, self.expr_index + 1);
+
+                arm_end_ids.into_iter().for_each(|arm_end| {
+                    // D -> H, G -> H
+                    self.drop_ranges.add_control_edge(arm_end, self.expr_index + 1)
+                });
+            }
+
+            ExprKind::Loop(body, label, ..) => {
+                let loop_begin = self.expr_index + 1;
+                self.label_stack.push((label, loop_begin));
+                if body.stmts.is_empty() && body.expr.is_none() {
+                    // For empty loops we won't have updated self.expr_index after visiting the
+                    // body, meaning we'd get an edge from expr_index to expr_index + 1, but
+                    // instead we want an edge from expr_index + 1 to expr_index + 1.
+                    self.drop_ranges.add_control_edge(loop_begin, loop_begin);
+                } else {
+                    self.visit_block(body);
+                    self.drop_ranges.add_control_edge(self.expr_index, loop_begin);
+                }
+                self.label_stack.pop();
+            }
+            // Find the loop entry by searching through the label stack for either the last entry
+            // (if label is none), or the first entry where the label matches this one. The Loop
+            // case maintains this stack mapping labels to the PostOrderId for the loop entry.
+            ExprKind::Continue(hir::Destination { label, .. }, ..) => self
+                .label_stack
+                .iter()
+                .rev()
+                .find(|(loop_label, _)| label.is_none() || *loop_label == label)
+                .map_or((), |(_, target)| {
+                    self.drop_ranges.add_control_edge(self.expr_index, *target)
+                }),
+
+            ExprKind::Break(destination, ..) => {
+                // destination either points to an expression or to a block. We use
+                // find_target_expression_from_destination to use the last expression of the block
+                // if destination points to a block.
+                //
+                // We add an edge to the hir_id of the expression/block we are breaking out of, and
+                // then in process_deferred_edges we will map this hir_id to its PostOrderId, which
+                // will refer to the end of the block due to the post order traversal.
+                self.find_target_expression_from_destination(destination).map_or((), |target| {
+                    self.drop_ranges.add_control_edge_hir_id(self.expr_index, target)
+                })
+            }
+
+            ExprKind::Call(f, args) => {
+                self.visit_expr(f);
+                for arg in args {
+                    self.visit_expr(arg);
+                }
+
+                self.handle_uninhabited_return(expr);
+            }
+            ExprKind::MethodCall(_, exprs, _) => {
+                for expr in exprs {
+                    self.visit_expr(expr);
+                }
+
+                self.handle_uninhabited_return(expr);
+            }
+
+            ExprKind::AddrOf(..)
+            | ExprKind::Array(..)
+            | ExprKind::AssignOp(..)
+            | ExprKind::Binary(..)
+            | ExprKind::Block(..)
+            | ExprKind::Box(..)
+            | ExprKind::Cast(..)
+            | ExprKind::Closure { .. }
+            | ExprKind::ConstBlock(..)
+            | ExprKind::DropTemps(..)
+            | ExprKind::Err
+            | ExprKind::Field(..)
+            | ExprKind::Index(..)
+            | ExprKind::InlineAsm(..)
+            | ExprKind::Let(..)
+            | ExprKind::Lit(..)
+            | ExprKind::Path(..)
+            | ExprKind::Repeat(..)
+            | ExprKind::Ret(..)
+            | ExprKind::Struct(..)
+            | ExprKind::Tup(..)
+            | ExprKind::Type(..)
+            | ExprKind::Unary(..)
+            | ExprKind::Yield(..) => intravisit::walk_expr(self, expr),
+        }
+
+        self.expr_index = self.expr_index + 1;
+        self.drop_ranges.add_node_mapping(expr.hir_id, self.expr_index);
+        self.consume_expr(expr);
+        if let Some(expr) = reinit {
+            self.reinit_expr(expr);
+        }
+    }
+
+    fn visit_pat(&mut self, pat: &'tcx hir::Pat<'tcx>) {
+        intravisit::walk_pat(self, pat);
+
+        // Increment expr_count here to match what InteriorVisitor expects.
+        self.expr_index = self.expr_index + 1;
+    }
+}
+
+impl DropRangesBuilder {
+    fn new(
+        tracked_values: impl Iterator<Item = TrackedValue>,
+        hir: Map<'_>,
+        num_exprs: usize,
+    ) -> Self {
+        let mut tracked_value_map = FxHashMap::<_, TrackedValueIndex>::default();
+        let mut next = <_>::from(0u32);
+        for value in tracked_values {
+            for_each_consumable(hir, value, |value| {
+                if !tracked_value_map.contains_key(&value) {
+                    tracked_value_map.insert(value, next);
+                    next = next + 1;
+                }
+            });
+        }
+        debug!("hir_id_map: {:?}", tracked_value_map);
+        let num_values = tracked_value_map.len();
+        Self {
+            tracked_value_map,
+            nodes: IndexVec::from_fn_n(|_| NodeInfo::new(num_values), num_exprs + 1),
+            deferred_edges: <_>::default(),
+            post_order_map: <_>::default(),
+        }
+    }
+
+    fn tracked_value_index(&self, tracked_value: TrackedValue) -> TrackedValueIndex {
+        *self.tracked_value_map.get(&tracked_value).unwrap()
+    }
+
+    /// Adds an entry in the mapping from HirIds to PostOrderIds
+    ///
+    /// Needed so that `add_control_edge_hir_id` can work.
+    fn add_node_mapping(&mut self, node_hir_id: HirId, post_order_id: PostOrderId) {
+        self.post_order_map.insert(node_hir_id, post_order_id);
+    }
+
+    /// Like add_control_edge, but uses a hir_id as the target.
+    ///
+    /// This can be used for branches where we do not know the PostOrderId of the target yet,
+    /// such as when handling `break` or `continue`.
+    fn add_control_edge_hir_id(&mut self, from: PostOrderId, to: HirId) {
+        self.deferred_edges.push((from, to));
+    }
+
+    fn drop_at(&mut self, value: TrackedValue, location: PostOrderId) {
+        let value = self.tracked_value_index(value);
+        self.node_mut(location).drops.push(value);
+    }
+
+    fn reinit_at(&mut self, value: TrackedValue, location: PostOrderId) {
+        let value = match self.tracked_value_map.get(&value) {
+            Some(value) => *value,
+            // If there's no value, this is never consumed and therefore is never dropped. We can
+            // ignore this.
+            None => return,
+        };
+        self.node_mut(location).reinits.push(value);
+    }
+
+    /// Looks up PostOrderId for any control edges added by HirId and adds a proper edge for them.
+    ///
+    /// Should be called after visiting the HIR but before solving the control flow, otherwise some
+    /// edges will be missed.
+    fn process_deferred_edges(&mut self) {
+        trace!("processing deferred edges. post_order_map={:#?}", self.post_order_map);
+        let mut edges = vec![];
+        swap(&mut edges, &mut self.deferred_edges);
+        edges.into_iter().for_each(|(from, to)| {
+            trace!("Adding deferred edge from {:?} to {:?}", from, to);
+            let to = *self.post_order_map.get(&to).expect("Expression ID not found");
+            trace!("target edge PostOrderId={:?}", to);
+            self.add_control_edge(from, to)
+        });
+    }
+}
diff --git a/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/cfg_propagate.rs b/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/cfg_propagate.rs
new file mode 100644
index 000000000..139d17d2e
--- /dev/null
+++ b/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/cfg_propagate.rs
@@ -0,0 +1,92 @@
+use super::{DropRangesBuilder, PostOrderId};
+use rustc_index::{bit_set::BitSet, vec::IndexVec};
+use std::collections::BTreeMap;
+
+impl DropRangesBuilder {
+    pub fn propagate_to_fixpoint(&mut self) {
+        trace!("before fixpoint: {:#?}", self);
+        let preds = self.compute_predecessors();
+
+        trace!("predecessors: {:#?}", preds.iter_enumerated().collect::<BTreeMap<_, _>>());
+
+        let mut new_state = BitSet::new_empty(self.num_values());
+        let mut changed_nodes = BitSet::new_empty(self.nodes.len());
+        let mut unchanged_mask = BitSet::new_filled(self.nodes.len());
+        changed_nodes.insert(0u32.into());
+
+        let mut propagate = || {
+            let mut changed = false;
+            unchanged_mask.insert_all();
+            for id in self.nodes.indices() {
+                trace!("processing {:?}, changed_nodes: {:?}", id, changed_nodes);
+                // Check if any predecessor has changed, and if not then short-circuit.
+                //
+                // We handle the start node specially, since it doesn't have any predecessors,
+                // but we need to start somewhere.
+                if match id.index() {
+                    0 => !changed_nodes.contains(id),
+                    _ => !preds[id].iter().any(|pred| changed_nodes.contains(*pred)),
+                } {
+                    trace!("short-circuiting because none of {:?} have changed", preds[id]);
+                    unchanged_mask.remove(id);
+                    continue;
+                }
+
+                if id.index() == 0 {
+                    new_state.clear();
+                } else {
+                    // If we are not the start node and we have no predecessors, treat
+                    // everything as dropped because there's no way to get here anyway.
+                    new_state.insert_all();
+                };
+
+                for pred in &preds[id] {
+                    new_state.intersect(&self.nodes[*pred].drop_state);
+                }
+
+                for drop in &self.nodes[id].drops {
+                    new_state.insert(*drop);
+                }
+
+                for reinit in &self.nodes[id].reinits {
+                    new_state.remove(*reinit);
+                }
+
+                if self.nodes[id].drop_state.intersect(&new_state) {
+                    changed_nodes.insert(id);
+                    changed = true;
+                } else {
+                    unchanged_mask.remove(id);
+                }
+            }
+
+            changed_nodes.intersect(&unchanged_mask);
+            changed
+        };
+
+        while propagate() {
+            trace!("drop_state changed, re-running propagation");
+        }
+
+        trace!("after fixpoint: {:#?}", self);
+    }
+
+    fn compute_predecessors(&self) -> IndexVec<PostOrderId, Vec<PostOrderId>> {
+        let mut preds = IndexVec::from_fn_n(|_| vec![], self.nodes.len());
+        for (id, node) in self.nodes.iter_enumerated() {
+            // If the node has no explicit successors, we assume that control
+            // will from this node into the next one.
+            //
+            // If there are successors listed, then we assume that all
+            // possible successors are given and we do not include the default.
+            if node.successors.len() == 0 && id.index() != self.nodes.len() - 1 {
+                preds[id + 1].push(id);
+            } else {
+                for succ in &node.successors {
+                    preds[*succ].push(id);
+                }
+            }
+        }
+        preds
+    }
+}
diff --git a/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/cfg_visualize.rs b/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/cfg_visualize.rs
new file mode 100644
index 000000000..c0a0bfe8e
--- /dev/null
+++ b/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/cfg_visualize.rs
@@ -0,0 +1,91 @@
+//! Implementation of GraphWalk for DropRanges so we can visualize the control
+//! flow graph when needed for debugging.
+
+use rustc_graphviz as dot;
+use rustc_middle::ty::TyCtxt;
+
+use super::{DropRangesBuilder, PostOrderId};
+
+/// Writes the CFG for DropRangesBuilder to a .dot file for visualization.
+///
+/// It is not normally called, but is kept around to easily add debugging
+/// code when needed.
+pub(super) fn write_graph_to_file(
+    drop_ranges: &DropRangesBuilder,
+    filename: &str,
+    tcx: TyCtxt<'_>,
+) {
+    dot::render(
+        &DropRangesGraph { drop_ranges, tcx },
+        &mut std::fs::File::create(filename).unwrap(),
+    )
+    .unwrap();
+}
+
+struct DropRangesGraph<'a, 'tcx> {
+    drop_ranges: &'a DropRangesBuilder,
+    tcx: TyCtxt<'tcx>,
+}
+
+impl<'a> dot::GraphWalk<'a> for DropRangesGraph<'_, '_> {
+    type Node = PostOrderId;
+
+    type Edge = (PostOrderId, PostOrderId);
+
+    fn nodes(&'a self) -> dot::Nodes<'a, Self::Node> {
+        self.drop_ranges.nodes.iter_enumerated().map(|(i, _)| i).collect()
+    }
+
+    fn edges(&'a self) -> dot::Edges<'a, Self::Edge> {
+        self.drop_ranges
+            .nodes
+            .iter_enumerated()
+            .flat_map(|(i, node)| {
+                if node.successors.len() == 0 {
+                    vec![(i, i + 1)]
+                } else {
+                    node.successors.iter().map(move |&s| (i, s)).collect()
+                }
+            })
+            .collect()
+    }
+
+    fn source(&'a self, edge: &Self::Edge) -> Self::Node {
+        edge.0
+    }
+
+    fn target(&'a self, edge: &Self::Edge) -> Self::Node {
+        edge.1
+    }
+}
+
+impl<'a> dot::Labeller<'a> for DropRangesGraph<'_, '_> {
+    type Node = PostOrderId;
+
+    type Edge = (PostOrderId, PostOrderId);
+
+    fn graph_id(&'a self) -> dot::Id<'a> {
+        dot::Id::new("drop_ranges").unwrap()
+    }
+
+    fn node_id(&'a self, n: &Self::Node) -> dot::Id<'a> {
+        dot::Id::new(format!("id{}", n.index())).unwrap()
+    }
+
+    fn node_label(&'a self, n: &Self::Node) -> dot::LabelText<'a> {
+        dot::LabelText::LabelStr(
+            format!(
+                "{n:?}: {}",
+                self.drop_ranges
+                    .post_order_map
+                    .iter()
+                    .find(|(_hir_id, &post_order_id)| post_order_id == *n)
+                    .map_or("<unknown>".into(), |(hir_id, _)| self
+                        .tcx
+                        .hir()
+                        .node_to_string(*hir_id))
+            )
+            .into(),
+        )
+    }
+}
diff --git a/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/record_consumed_borrow.rs b/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/record_consumed_borrow.rs
new file mode 100644
index 000000000..ded0888c3
--- /dev/null
+++ b/compiler/rustc_typeck/src/check/generator_interior/drop_ranges/record_consumed_borrow.rs
@@ -0,0 +1,232 @@
+use super::TrackedValue;
+use crate::{
+    check::FnCtxt,
+    expr_use_visitor::{self, ExprUseVisitor},
+};
+use hir::{def_id::DefId, Body, HirId, HirIdMap};
+use rustc_data_structures::fx::FxHashSet;
+use rustc_hir as hir;
+use rustc_middle::hir::place::{PlaceBase, Projection, ProjectionKind};
+use rustc_middle::ty::{ParamEnv, TyCtxt};
+
+pub(super) fn find_consumed_and_borrowed<'a, 'tcx>(
+    fcx: &'a FnCtxt<'a, 'tcx>,
+    def_id: DefId,
+    body: &'tcx Body<'tcx>,
+) -> ConsumedAndBorrowedPlaces {
+    let mut expr_use_visitor = ExprUseDelegate::new(fcx.tcx, fcx.param_env);
+    expr_use_visitor.consume_body(fcx, def_id, body);
+    expr_use_visitor.places
+}
+
+pub(super) struct ConsumedAndBorrowedPlaces {
+    /// Records the variables/expressions that are dropped by a given expression.
+    ///
+    /// The key is the hir-id of the expression, and the value is a set or hir-ids for variables
+    /// or values that are consumed by that expression.
+    ///
+    /// Note that this set excludes "partial drops" -- for example, a statement like `drop(x.y)` is
+    /// not considered a drop of `x`, although it would be a drop of `x.y`.
+    pub(super) consumed: HirIdMap<FxHashSet<TrackedValue>>,
+
+    /// A set of hir-ids of values or variables that are borrowed at some point within the body.
+    pub(super) borrowed: FxHashSet<TrackedValue>,
+
+    /// A set of hir-ids of values or variables that are borrowed at some point within the body.
+    pub(super) borrowed_temporaries: FxHashSet<HirId>,
+}
+
+/// Works with ExprUseVisitor to find interesting values for the drop range analysis.
+///
+/// Interesting values are those that are either dropped or borrowed. For dropped values, we also
+/// record the parent expression, which is the point where the drop actually takes place.
+struct ExprUseDelegate<'tcx> {
+    tcx: TyCtxt<'tcx>,
+    param_env: ParamEnv<'tcx>,
+    places: ConsumedAndBorrowedPlaces,
+}
+
+impl<'tcx> ExprUseDelegate<'tcx> {
+    fn new(tcx: TyCtxt<'tcx>, param_env: ParamEnv<'tcx>) -> Self {
+        Self {
+            tcx,
+            param_env,
+            places: ConsumedAndBorrowedPlaces {
+                consumed: <_>::default(),
+                borrowed: <_>::default(),
+                borrowed_temporaries: <_>::default(),
+            },
+        }
+    }
+
+    fn consume_body(&mut self, fcx: &'_ FnCtxt<'_, 'tcx>, def_id: DefId, body: &'tcx Body<'tcx>) {
+        // Run ExprUseVisitor to find where values are consumed.
+        ExprUseVisitor::new(
+            self,
+            &fcx.infcx,
+            def_id.expect_local(),
+            fcx.param_env,
+            &fcx.typeck_results.borrow(),
+        )
+        .consume_body(body);
+    }
+
+    fn mark_consumed(&mut self, consumer: HirId, target: TrackedValue) {
+        self.places.consumed.entry(consumer).or_insert_with(|| <_>::default());
+
+        debug!(?consumer, ?target, "mark_consumed");
+        self.places.consumed.get_mut(&consumer).map(|places| places.insert(target));
+    }
+
+    fn borrow_place(&mut self, place_with_id: &expr_use_visitor::PlaceWithHirId<'tcx>) {
+        self.places
+            .borrowed
+            .insert(TrackedValue::from_place_with_projections_allowed(place_with_id));
+
+        // Ordinarily a value is consumed by it's parent, but in the special case of a
+        // borrowed RValue, we create a reference that lives as long as the temporary scope
+        // for that expression (typically, the innermost statement, but sometimes the enclosing
+        // block). We record this fact here so that later in generator_interior
+        // we can use the correct scope.
+        //
+        // We special case borrows through a dereference (`&*x`, `&mut *x` where `x` is
+        // some rvalue expression), since these are essentially a copy of a pointer.
+        // In other words, this borrow does not refer to the
+        // temporary (`*x`), but to the referent (whatever `x` is a borrow of).
+        //
+        // We were considering that we might encounter problems down the line if somehow,
+        // some part of the compiler were to look at this result and try to use it to
+        // drive a borrowck-like analysis (this does not currently happen, as of this writing).
+        // But even this should be fine, because the lifetime of the dereferenced reference
+        // found in the rvalue is only significant as an intermediate 'link' to the value we
+        // are producing, and we separately track whether that value is live over a yield.
+        // Example:
+        //
+        // ```notrust
+        // fn identity<T>(x: &mut T) -> &mut T { x }
+        // let a: A = ...;
+        // let y: &'y mut A = &mut *identity(&'a mut a);
+        //                    ^^^^^^^^^^^^^^^^^^^^^^^^^ the borrow we are talking about
+        // ```
+        //
+        // The expression `*identity(...)` is a deref of an rvalue,
+        // where the `identity(...)` (the rvalue) produces a return type
+        // of `&'rv mut A`, where `'a: 'rv`. We then assign this result to
+        // `'y`, resulting in (transitively) `'a: 'y` (i.e., while `y` is in use,
+        // `a` will be considered borrowed).  Other parts of the code will ensure
+        // that if `y` is live over a yield, `&'y mut A` appears in the generator
+        // state. If `'y` is live, then any sound region analysis must conclude
+        // that `'a` is also live. So if this causes a bug, blame some other
+        // part of the code!
+        let is_deref = place_with_id
+            .place
+            .projections
+            .iter()
+            .any(|Projection { kind, .. }| *kind == ProjectionKind::Deref);
+
+        if let (false, PlaceBase::Rvalue) = (is_deref, place_with_id.place.base) {
+            self.places.borrowed_temporaries.insert(place_with_id.hir_id);
+        }
+    }
+}
+
+impl<'tcx> expr_use_visitor::Delegate<'tcx> for ExprUseDelegate<'tcx> {
+    fn consume(
+        &mut self,
+        place_with_id: &expr_use_visitor::PlaceWithHirId<'tcx>,
+        diag_expr_id: HirId,
+    ) {
+        let hir = self.tcx.hir();
+        let parent = match hir.find_parent_node(place_with_id.hir_id) {
+            Some(parent) => parent,
+            None => place_with_id.hir_id,
+        };
+        debug!(
+            "consume {:?}; diag_expr_id={}, using parent {}",
+            place_with_id,
+            hir.node_to_string(diag_expr_id),
+            hir.node_to_string(parent)
+        );
+        place_with_id
+            .try_into()
+            .map_or((), |tracked_value| self.mark_consumed(parent, tracked_value));
+    }
+
+    fn borrow(
+        &mut self,
+        place_with_id: &expr_use_visitor::PlaceWithHirId<'tcx>,
+        diag_expr_id: HirId,
+        bk: rustc_middle::ty::BorrowKind,
+    ) {
+        debug!(
+            "borrow: place_with_id = {place_with_id:?}, diag_expr_id={diag_expr_id:?}, \
+            borrow_kind={bk:?}"
+        );
+
+        self.borrow_place(place_with_id);
+    }
+
+    fn copy(
+        &mut self,
+        place_with_id: &expr_use_visitor::PlaceWithHirId<'tcx>,
+        _diag_expr_id: HirId,
+    ) {
+        debug!("copy: place_with_id = {place_with_id:?}");
+
+        self.places
+            .borrowed
+            .insert(TrackedValue::from_place_with_projections_allowed(place_with_id));
+
+        // For copied we treat this mostly like a borrow except that we don't add the place
+        // to borrowed_temporaries because the copy is consumed.
+    }
+
+    fn mutate(
+        &mut self,
+        assignee_place: &expr_use_visitor::PlaceWithHirId<'tcx>,
+        diag_expr_id: HirId,
+    ) {
+        debug!("mutate {assignee_place:?}; diag_expr_id={diag_expr_id:?}");
+
+        if assignee_place.place.base == PlaceBase::Rvalue
+            && assignee_place.place.projections.is_empty()
+        {
+            // Assigning to an Rvalue is illegal unless done through a dereference. We would have
+            // already gotten a type error, so we will just return here.
+            return;
+        }
+
+        // If the type being assigned needs dropped, then the mutation counts as a borrow
+        // since it is essentially doing `Drop::drop(&mut x); x = new_value;`.
+        if assignee_place.place.base_ty.needs_drop(self.tcx, self.param_env) {
+            self.places
+                .borrowed
+                .insert(TrackedValue::from_place_with_projections_allowed(assignee_place));
+        }
+    }
+
+    fn bind(
+        &mut self,
+        binding_place: &expr_use_visitor::PlaceWithHirId<'tcx>,
+        diag_expr_id: HirId,
+    ) {
+        debug!("bind {binding_place:?}; diag_expr_id={diag_expr_id:?}");
+    }
+
+    fn fake_read(
+        &mut self,
+        place_with_id: &expr_use_visitor::PlaceWithHirId<'tcx>,
+        cause: rustc_middle::mir::FakeReadCause,
+        diag_expr_id: HirId,
+    ) {
+        debug!(
+            "fake_read place_with_id={place_with_id:?}; cause={cause:?}; diag_expr_id={diag_expr_id:?}"
+        );
+
+        // fake reads happen in places like the scrutinee of a match expression.
+        // we treat those as a borrow, much like a copy: the idea is that we are
+        // transiently creating a `&T` ref that we can read from to observe the current
+        // value (this `&T` is immediately dropped afterwards).
+        self.borrow_place(place_with_id);
+    }
+}