Auto merge of #71006 - ecstatic-morse:dataflow-bidi, r=ecstatic-morse

Use existing framework for backward dataflow analyses

This PR adds support for backward analyses to the dataflow framework and adds a new live variable analysis (based on the existing one in `librustc_mir/util/liveness.rs`). By adding these to the framework instead of having a separate API, all newly implemented backward dataflow analyses get cursors/visitors, `rustc_peek` tests, and graphviz visualizations for free. In the near-term, this makes it much easier to implement global dead-store elimination, and I believe that this will enable even more MIR optimizations in the future.

This PR makes many changes to the dataflow API, since some concepts and terminology only make sense in forward dataflow. Below is a list of the important changes.
- ~~`entry_set` -> `fixpoint` (the fixpoint for backward dataflow problems is after the block's terminator)~~
- `seek_{before,after}` -> `seek_{before,after}_primary_effect` (the unprefixed dataflow effect is now referred to as the "primary" effect instead of the "after" effect. The "before" effect remains the same, although I considered changing it to the "antecedent" effect. In both backward and forward dataflow, the "before" effect is applied prior to the "primary" effect. I feel very strongly that this is the correct choice, as it means consumers don't have to switch between `seek_before` and `seek_after` based on the direction of their analysis.
- `seek_after_assume_call_returns` is now gone. Users can use `ResultsCursor::apply_custom_effect` to emulate it.
- `visit_{statement,terminator}_exit` -> `visit_{statement,terminator}_after_primary_effect`
- `visit_{statement,terminator}` -> `visit_{statement,terminator}_before_primary_effect`

Implementing this also required refactoring the dataflow cursor implementation so it could work in both directions. This is a large percentage of the diff, since the cursor code is rather complex. The fact that the cursor is exhaustively tested in both directions should reassure whomever is unlucky enough to review this :rofl:.

In order to avoid computing the reverse CFG for forward dataflow analyses, I've added some hacks to the existing `mir::BodyAndCache` interface. I've requested changes to this interface that would let me implement this more efficiently.

r? @eddyb (feel free to reassign)
cc @rust-lang/wg-mir-opt

25 files changed, 1369 insertions, 709 deletions

diff --git a/src/librustc_codegen_ssa/mir/analyze.rs b/src/librustc_codegen_ssa/mir/analyze.rs
index a677ffea3af..9fcaf2818e8 100644
--- a/src/librustc_codegen_ssa/mir/analyze.rs
+++ b/src/librustc_codegen_ssa/mir/analyze.rs
@@ -269,7 +269,8 @@ impl<'mir, 'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> Visitor<'tcx>
 
     fn visit_local(&mut self, &local: &mir::Local, context: PlaceContext, location: Location) {
         match context {
-            PlaceContext::MutatingUse(MutatingUseContext::Call) => {
+            PlaceContext::MutatingUse(MutatingUseContext::Call)
+            | PlaceContext::MutatingUse(MutatingUseContext::Yield) => {
                 self.assign(local, location);
             }
 
diff --git a/src/librustc_middle/mir/visit.rs b/src/librustc_middle/mir/visit.rs
index d32a8d43445..97f7cccdb60 100644
--- a/src/librustc_middle/mir/visit.rs
+++ b/src/librustc_middle/mir/visit.rs
@@ -510,7 +510,7 @@ macro_rules! make_mir_visitor {
                         self.visit_operand(value, source_location);
                         self.visit_place(
                             resume_arg,
-                            PlaceContext::MutatingUse(MutatingUseContext::Store),
+                            PlaceContext::MutatingUse(MutatingUseContext::Yield),
                             source_location,
                         );
                     }
@@ -1052,6 +1052,8 @@ pub enum MutatingUseContext {
     AsmOutput,
     /// Destination of a call.
     Call,
+    /// Destination of a yield.
+    Yield,
     /// Being dropped.
     Drop,
     /// Mutable borrow.
diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs
index b95a1043d92..7d8a2b540a9 100644
--- a/src/librustc_mir/borrow_check/mod.rs
+++ b/src/librustc_mir/borrow_check/mod.rs
@@ -518,7 +518,7 @@ crate struct MirBorrowckCtxt<'cx, 'tcx> {
 impl<'cx, 'tcx> dataflow::ResultsVisitor<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx> {
     type FlowState = Flows<'cx, 'tcx>;
 
-    fn visit_statement(
+    fn visit_statement_before_primary_effect(
         &mut self,
         flow_state: &Flows<'cx, 'tcx>,
         stmt: &'cx Statement<'tcx>,
@@ -607,7 +607,7 @@ impl<'cx, 'tcx> dataflow::ResultsVisitor<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tc
         }
     }
 
-    fn visit_terminator(
+    fn visit_terminator_before_primary_effect(
         &mut self,
         flow_state: &Flows<'cx, 'tcx>,
         term: &'cx Terminator<'tcx>,
@@ -701,7 +701,7 @@ impl<'cx, 'tcx> dataflow::ResultsVisitor<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tc
         }
     }
 
-    fn visit_terminator_exit(
+    fn visit_terminator_after_primary_effect(
         &mut self,
         flow_state: &Flows<'cx, 'tcx>,
         term: &'cx Terminator<'tcx>,
diff --git a/src/librustc_mir/borrow_check/type_check/liveness/trace.rs b/src/librustc_mir/borrow_check/type_check/liveness/trace.rs
index ec52a08c7b2..41c77cf21a7 100644
--- a/src/librustc_mir/borrow_check/type_check/liveness/trace.rs
+++ b/src/librustc_mir/borrow_check/type_check/liveness/trace.rs
@@ -408,7 +408,7 @@ impl LivenessContext<'_, '_, '_, 'tcx> {
     /// 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(self.body.terminator_loc(block));
+        self.flow_inits.seek_before_primary_effect(self.body.terminator_loc(block));
         self.initialized_at_curr_loc(mpi)
     }
 
@@ -418,7 +418,7 @@ impl LivenessContext<'_, '_, '_, 'tcx> {
     /// **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(self.body.terminator_loc(block));
+        self.flow_inits.seek_after_primary_effect(self.body.terminator_loc(block));
         self.initialized_at_curr_loc(mpi)
     }
 
diff --git a/src/librustc_mir/dataflow/framework/cursor.rs b/src/librustc_mir/dataflow/framework/cursor.rs
index 39676d03740..2ae353adfc7 100644
--- a/src/librustc_mir/dataflow/framework/cursor.rs
+++ b/src/librustc_mir/dataflow/framework/cursor.rs
@@ -1,11 +1,12 @@
 //! Random access inspection of the results of a dataflow analysis.
 
 use std::borrow::Borrow;
+use std::cmp::Ordering;
 
 use rustc_index::bit_set::BitSet;
-use rustc_middle::mir::{self, BasicBlock, Location, TerminatorKind};
+use rustc_middle::mir::{self, BasicBlock, Location};
 
-use super::{Analysis, Results};
+use super::{Analysis, Direction, Effect, EffectIndex, Results};
 
 /// A `ResultsCursor` that borrows the underlying `Results`.
 pub type ResultsRefCursor<'a, 'mir, 'tcx, A> = ResultsCursor<'mir, 'tcx, A, &'a Results<'tcx, A>>;
@@ -13,9 +14,9 @@ pub type ResultsRefCursor<'a, 'mir, 'tcx, A> = ResultsCursor<'mir, 'tcx, A, &'a
 /// Allows random access inspection of the results of a dataflow analysis.
 ///
 /// This cursor only has linear performance within a basic block when its statements are visited in
-/// order. In the worst case—when statements are visited in *reverse* order—performance will be
-/// quadratic in the number of statements in the block. The order in which basic blocks are
-/// inspected has no impact on performance.
+/// the same order as the `DIRECTION` of the analysis. In the worst case—when statements are
+/// visited in *reverse* order—performance will be quadratic in the number of statements in the
+/// block. The order in which basic blocks are inspected has no impact on performance.
 ///
 /// A `ResultsCursor` can either own (the default) or borrow the dataflow results it inspects. The
 /// type of ownership is determined by `R` (see `ResultsRefCursor` above).
@@ -29,14 +30,10 @@ where
 
     pos: CursorPosition,
 
-    /// When this flag is set, the cursor is pointing at a `Call` or `Yield` terminator whose call
-    /// return or resume effect has been applied to `state`.
+    /// Indicates that `state` has been modified with a custom effect.
     ///
-    /// This flag helps to ensure that multiple calls to `seek_after_assume_success` with the
-    /// same target will result in exactly one invocation of `apply_call_return_effect`. It is
-    /// sufficient to clear this only in `seek_to_block_start`, since seeking away from a
-    /// terminator will always require a cursor reset.
-    success_effect_applied: bool,
+    /// When this flag is set, we need to reset to an entry set before doing a seek.
+    state_needs_reset: bool,
 }
 
 impl<'mir, 'tcx, A, R> ResultsCursor<'mir, 'tcx, A, R>
@@ -44,17 +41,27 @@ where
     A: Analysis<'tcx>,
     R: Borrow<Results<'tcx, A>>,
 {
-    /// Returns a new cursor for `results` that points to the start of the `START_BLOCK`.
+    /// Returns a new cursor that can inspect `results`.
     pub fn new(body: &'mir mir::Body<'tcx>, results: R) -> Self {
+        let bits_per_block = results.borrow().entry_set_for_block(mir::START_BLOCK).domain_size();
+
         ResultsCursor {
             body,
-            pos: CursorPosition::BlockStart(mir::START_BLOCK),
-            state: results.borrow().entry_sets[mir::START_BLOCK].clone(),
-            success_effect_applied: false,
             results,
+
+            // Initialize to an empty `BitSet` and set `state_needs_reset` to tell the cursor that
+            // it needs to reset to block entry before the first seek. The cursor position is
+            // immaterial.
+            state_needs_reset: true,
+            state: BitSet::new_empty(bits_per_block),
+            pos: CursorPosition::block_entry(mir::START_BLOCK),
         }
     }
 
+    pub fn body(&self) -> &'mir mir::Body<'tcx> {
+        self.body
+    }
+
     /// Returns the `Analysis` used to generate the underlying results.
     pub fn analysis(&self) -> &A {
         &self.results.borrow().analysis
@@ -72,209 +79,134 @@ where
         self.state.contains(elem)
     }
 
-    /// Resets the cursor to the start of the given basic block.
-    pub fn seek_to_block_start(&mut self, block: BasicBlock) {
-        self.state.overwrite(&self.results.borrow().entry_sets[block]);
-        self.pos = CursorPosition::BlockStart(block);
-        self.success_effect_applied = false;
-    }
-
-    /// Advances the cursor to hold all effects up to and including to the "before" effect of the
-    /// statement (or terminator) at the given location.
+    /// Resets the cursor to hold the entry set for the given basic block.
     ///
-    /// If you wish to observe the full effect of a statement or terminator, not just the "before"
-    /// effect, use `seek_after` or `seek_after_assume_success`.
-    pub fn seek_before(&mut self, target: Location) {
-        assert!(target <= self.body.terminator_loc(target.block));
-        self.seek_(target, false);
+    /// For forward dataflow analyses, this is the dataflow state prior to the first statement.
+    ///
+    /// For backward dataflow analyses, this is the dataflow state after the terminator.
+    pub(super) fn seek_to_block_entry(&mut self, block: BasicBlock) {
+        self.state.overwrite(&self.results.borrow().entry_set_for_block(block));
+        self.pos = CursorPosition::block_entry(block);
+        self.state_needs_reset = false;
     }
 
-    /// Advances the cursor to hold the full effect of all statements (and possibly closing
-    /// terminators) up to and including the `target`.
+    /// Resets the cursor to hold the state prior to the first statement in a basic block.
     ///
-    /// If the `target` is a `Call` terminator, any call return effect for that terminator will
-    /// **not** be observed. Use `seek_after_assume_success` if you wish to observe the call
-    /// return effect.
-    pub fn seek_after(&mut self, target: Location) {
-        assert!(target <= self.body.terminator_loc(target.block));
-
-        // If we have already applied the call return effect, we are currently pointing at a `Call`
-        // terminator. Unconditionally reset the dataflow cursor, since there is no way to "undo"
-        // the call return effect.
-        if self.success_effect_applied {
-            self.seek_to_block_start(target.block);
+    /// For forward analyses, this is the entry set for the given block.
+    ///
+    /// For backward analyses, this is the state that will be propagated to its
+    /// predecessors (ignoring edge-specific effects).
+    pub fn seek_to_block_start(&mut self, block: BasicBlock) {
+        if A::Direction::is_forward() {
+            self.seek_to_block_entry(block)
+        } else {
+            self.seek_after(Location { block, statement_index: 0 }, Effect::Primary)
         }
-
-        self.seek_(target, true);
     }
 
-    /// Advances the cursor to hold all effects up to and including of the statement (or
-    /// terminator) at the given location.
+    /// Resets the cursor to hold the state after the terminator in a basic block.
     ///
-    /// If the `target` is a `Call` or `Yield` terminator, any call return or resume effect for that
-    /// terminator will be observed. Use `seek_after` if you do **not** wish to observe the
-    /// "success" effect.
-    pub fn seek_after_assume_success(&mut self, target: Location) {
-        let terminator_loc = self.body.terminator_loc(target.block);
-        assert!(target.statement_index <= terminator_loc.statement_index);
-
-        self.seek_(target, true);
-
-        if target != terminator_loc || self.success_effect_applied {
-            return;
-        }
-
-        // Apply the effect of the "success" path of the terminator.
-
-        self.success_effect_applied = true;
-        let terminator = self.body.basic_blocks()[target.block].terminator();
-        match &terminator.kind {
-            TerminatorKind::Call { destination: Some((return_place, _)), func, args, .. } => {
-                self.results.borrow().analysis.apply_call_return_effect(
-                    &mut self.state,
-                    target.block,
-                    func,
-                    args,
-                    *return_place,
-                );
-            }
-            TerminatorKind::Yield { resume, resume_arg, .. } => {
-                self.results.borrow().analysis.apply_yield_resume_effect(
-                    &mut self.state,
-                    *resume,
-                    *resume_arg,
-                );
-            }
-            _ => {}
+    /// For backward analyses, this is the entry set for the given block.
+    ///
+    /// For forward analyses, this is the state that will be propagated to its
+    /// successors (ignoring edge-specific effects).
+    pub fn seek_to_block_end(&mut self, block: BasicBlock) {
+        if A::Direction::is_backward() {
+            self.seek_to_block_entry(block)
+        } else {
+            self.seek_after(self.body.terminator_loc(block), Effect::Primary)
         }
     }
 
-    fn seek_(&mut self, target: Location, apply_after_effect_at_target: bool) {
-        use CursorPosition::*;
-
-        match self.pos {
-            // Return early if we are already at the target location.
-            Before(curr) if curr == target && !apply_after_effect_at_target => return,
-            After(curr) if curr == target && apply_after_effect_at_target => return,
+    /// Advances the cursor to hold the dataflow state at `target` before its "primary" effect is
+    /// applied.
+    ///
+    /// The "before" effect at the target location *will be* applied.
+    pub fn seek_before_primary_effect(&mut self, target: Location) {
+        self.seek_after(target, Effect::Before)
+    }
 
-            // Otherwise, we must reset to the start of the target block if...
+    /// Advances the cursor to hold the dataflow state at `target` after its "primary" effect is
+    /// applied.
+    ///
+    /// The "before" effect at the target location will be applied as well.
+    pub fn seek_after_primary_effect(&mut self, target: Location) {
+        self.seek_after(target, Effect::Primary)
+    }
 
-            // we are in a different block entirely.
-            BlockStart(block) | Before(Location { block, .. }) | After(Location { block, .. })
-                if block != target.block =>
-            {
-                self.seek_to_block_start(target.block)
-            }
+    fn seek_after(&mut self, target: Location, effect: Effect) {
+        assert!(target <= self.body.terminator_loc(target.block));
 
-            // we are in the same block but have advanced past the target statement.
-            Before(curr) | After(curr) if curr.statement_index > target.statement_index => {
-                self.seek_to_block_start(target.block)
+        // Reset to the entry of the target block if any of the following are true:
+        //   - A custom effect has been applied to the cursor state.
+        //   - We are in a different block than the target.
+        //   - We are in the same block but have advanced past the target effect.
+        if self.state_needs_reset || self.pos.block != target.block {
+            self.seek_to_block_entry(target.block);
+        } else if let Some(curr_effect) = self.pos.curr_effect_index {
+            let mut ord = curr_effect.statement_index.cmp(&target.statement_index);
+            if A::Direction::is_backward() {
+                ord = ord.reverse()
             }
 
-            // we have already applied the entire effect of a statement but only wish to observe
-            // its "before" effect.
-            After(curr)
-                if curr.statement_index == target.statement_index
-                    && !apply_after_effect_at_target =>
-            {
-                self.seek_to_block_start(target.block)
+            match ord.then_with(|| curr_effect.effect.cmp(&effect)) {
+                Ordering::Equal => return,
+                Ordering::Greater => self.seek_to_block_entry(target.block),
+                Ordering::Less => {}
             }
-
-            // N.B., `success_effect_applied` is checked in `seek_after`, not here.
-            _ => (),
         }
 
-        let analysis = &self.results.borrow().analysis;
-        let block_data = &self.body.basic_blocks()[target.block];
-
         // At this point, the cursor is in the same block as the target location at an earlier
         // statement.
-        debug_assert_eq!(target.block, self.pos.block());
-
-        // Find the first statement whose transfer function has not yet been applied.
-        let first_unapplied_statement = match self.pos {
-            BlockStart(_) => 0,
-            After(Location { statement_index, .. }) => statement_index + 1,
-
-            // If we have only applied the "before" effect for the current statement, apply the
-            // remainder before continuing.
-            Before(curr) => {
-                if curr.statement_index == block_data.statements.len() {
-                    let terminator = block_data.terminator();
-                    analysis.apply_terminator_effect(&mut self.state, terminator, curr);
-                } else {
-                    let statement = &block_data.statements[curr.statement_index];
-                    analysis.apply_statement_effect(&mut self.state, statement, curr);
-                }
-
-                // If all we needed to do was go from `Before` to `After` in the same statement,
-                // we are now done.
-                if curr.statement_index == target.statement_index {
-                    debug_assert!(apply_after_effect_at_target);
-                    self.pos = After(target);
-                    return;
-                }
-
-                curr.statement_index + 1
-            }
+        debug_assert_eq!(target.block, self.pos.block);
+
+        let block_data = &self.body[target.block];
+        let next_effect = if A::Direction::is_forward() {
+            #[rustfmt::skip]
+            self.pos.curr_effect_index.map_or_else(
+                || Effect::Before.at_index(0),
+                EffectIndex::next_in_forward_order,
+            )
+        } else {
+            self.pos.curr_effect_index.map_or_else(
+                || Effect::Before.at_index(block_data.statements.len()),
+                EffectIndex::next_in_backward_order,
+            )
         };
 
-        // We have now applied all effects prior to `first_unapplied_statement`.
-
-        // Apply the effects of all statements before `target`.
-        let mut location = Location { block: target.block, statement_index: 0 };
-        for statement_index in first_unapplied_statement..target.statement_index {
-            location.statement_index = statement_index;
-            let statement = &block_data.statements[statement_index];
-            analysis.apply_before_statement_effect(&mut self.state, statement, location);
-            analysis.apply_statement_effect(&mut self.state, statement, location);
-        }
-
-        // Apply the effect of the statement (or terminator) at `target`.
-        location.statement_index = target.statement_index;
-        if target.statement_index == block_data.statements.len() {
-            let terminator = &block_data.terminator();
-            analysis.apply_before_terminator_effect(&mut self.state, terminator, location);
-
-            if apply_after_effect_at_target {
-                analysis.apply_terminator_effect(&mut self.state, terminator, location);
-                self.pos = After(target);
-            } else {
-                self.pos = Before(target);
-            }
-        } else {
-            let statement = &block_data.statements[target.statement_index];
-            analysis.apply_before_statement_effect(&mut self.state, statement, location);
+        let analysis = &self.results.borrow().analysis;
+        let target_effect_index = effect.at_index(target.statement_index);
+
+        A::Direction::apply_effects_in_range(
+            analysis,
+            &mut self.state,
+            target.block,
+            block_data,
+            next_effect..=target_effect_index,
+        );
+
+        self.pos =
+            CursorPosition { block: target.block, curr_effect_index: Some(target_effect_index) };
+    }
 
-            if apply_after_effect_at_target {
-                analysis.apply_statement_effect(&mut self.state, statement, location);
-                self.pos = After(target)
-            } else {
-                self.pos = Before(target);
-            }
-        }
+    /// Applies `f` to the cursor's internal state.
+    ///
+    /// This can be used, e.g., to apply the call return effect directly to the cursor without
+    /// creating an extra copy of the dataflow state.
+    pub fn apply_custom_effect(&mut self, f: impl FnOnce(&A, &mut BitSet<A::Idx>)) {
+        f(&self.results.borrow().analysis, &mut self.state);
+        self.state_needs_reset = true;
     }
 }
 
 #[derive(Clone, Copy, Debug)]
-enum CursorPosition {
-    /// No effects within this block have been applied.
-    BlockStart(BasicBlock),
-
-    /// Only the "before" effect of the statement (or terminator) at this location has been
-    /// applied (along with the effects of all previous statements).
-    Before(Location),
-
-    /// The effects of all statements up to and including the one at this location have been
-    /// applied.
-    After(Location),
+struct CursorPosition {
+    block: BasicBlock,
+    curr_effect_index: Option<EffectIndex>,
 }
 
 impl CursorPosition {
-    fn block(&self) -> BasicBlock {
-        match *self {
-            Self::BlockStart(block) => block,
-            Self::Before(loc) | Self::After(loc) => loc.block,
-        }
+    fn block_entry(block: BasicBlock) -> CursorPosition {
+        CursorPosition { block, curr_effect_index: None }
     }
 }
diff --git a/src/librustc_mir/dataflow/framework/direction.rs b/src/librustc_mir/dataflow/framework/direction.rs
new file mode 100644
index 00000000000..76f703ec913
--- /dev/null
+++ b/src/librustc_mir/dataflow/framework/direction.rs
@@ -0,0 +1,570 @@
+use rustc_index::bit_set::BitSet;
+use rustc_middle::mir::{self, BasicBlock, Location};
+use rustc_middle::ty::{self, TyCtxt};
+use std::ops::RangeInclusive;
+
+use super::visitor::{ResultsVisitable, ResultsVisitor};
+use super::{Analysis, Effect, EffectIndex, GenKillAnalysis, GenKillSet};
+
+pub trait Direction {
+    fn is_forward() -> bool;
+
+    fn is_backward() -> bool {
+        !Self::is_forward()
+    }
+
+    /// Applies all effects between the given `EffectIndex`s.
+    ///
+    /// `effects.start()` must precede or equal `effects.end()` in this direction.
+    fn apply_effects_in_range<A>(
+        analysis: &A,
+        state: &mut BitSet<A::Idx>,
+        block: BasicBlock,
+        block_data: &mir::BasicBlockData<'tcx>,
+        effects: RangeInclusive<EffectIndex>,
+    ) where
+        A: Analysis<'tcx>;
+
+    fn apply_effects_in_block<A>(
+        analysis: &A,
+        state: &mut BitSet<A::Idx>,
+        block: BasicBlock,
+        block_data: &mir::BasicBlockData<'tcx>,
+    ) where
+        A: Analysis<'tcx>;
+
+    fn gen_kill_effects_in_block<A>(
+        analysis: &A,
+        trans: &mut GenKillSet<A::Idx>,
+        block: BasicBlock,
+        block_data: &mir::BasicBlockData<'tcx>,
+    ) where
+        A: GenKillAnalysis<'tcx>;
+
+    fn visit_results_in_block<F, R>(
+        state: &mut F,
+        block: BasicBlock,
+        block_data: &'mir mir::BasicBlockData<'tcx>,
+        results: &R,
+        vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = F>,
+    ) where
+        R: ResultsVisitable<'tcx, FlowState = F>;
+
+    fn join_state_into_successors_of<A>(
+        analysis: &A,
+        tcx: TyCtxt<'tcx>,
+        body: &mir::Body<'tcx>,
+        dead_unwinds: Option<&BitSet<BasicBlock>>,
+        exit_state: &mut BitSet<A::Idx>,
+        block: (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
+        propagate: impl FnMut(BasicBlock, &BitSet<A::Idx>),
+    ) where
+        A: Analysis<'tcx>;
+}
+
+/// Dataflow that runs from the exit of a block (the terminator), to its entry (the first statement).
+pub struct Backward;
+
+impl Direction for Backward {
+    fn is_forward() -> bool {
+        false
+    }
+
+    fn apply_effects_in_block<A>(
+        analysis: &A,
+        state: &mut BitSet<A::Idx>,
+        block: BasicBlock,
+        block_data: &mir::BasicBlockData<'tcx>,
+    ) where
+        A: Analysis<'tcx>,
+    {
+        let terminator = block_data.terminator();
+        let location = Location { block, statement_index: block_data.statements.len() };
+        analysis.apply_before_terminator_effect(state, terminator, location);
+        analysis.apply_terminator_effect(state, terminator, location);
+
+        for (statement_index, statement) in block_data.statements.iter().enumerate().rev() {
+            let location = Location { block, statement_index };
+            analysis.apply_before_statement_effect(state, statement, location);
+            analysis.apply_statement_effect(state, statement, location);
+        }
+    }
+
+    fn gen_kill_effects_in_block<A>(
+        analysis: &A,
+        trans: &mut GenKillSet<A::Idx>,
+        block: BasicBlock,
+        block_data: &mir::BasicBlockData<'tcx>,
+    ) where
+        A: GenKillAnalysis<'tcx>,
+    {
+        let terminator = block_data.terminator();
+        let location = Location { block, statement_index: block_data.statements.len() };
+        analysis.before_terminator_effect(trans, terminator, location);
+        analysis.terminator_effect(trans, terminator, location);
+
+        for (statement_index, statement) in block_data.statements.iter().enumerate().rev() {
+            let location = Location { block, statement_index };
+            analysis.before_statement_effect(trans, statement, location);
+            analysis.statement_effect(trans, statement, location);
+        }
+    }
+
+    fn apply_effects_in_range<A>(
+        analysis: &A,
+        state: &mut BitSet<A::Idx>,
+        block: BasicBlock,
+        block_data: &mir::BasicBlockData<'tcx>,
+        effects: RangeInclusive<EffectIndex>,
+    ) where
+        A: Analysis<'tcx>,
+    {
+        let (from, to) = (*effects.start(), *effects.end());
+        let terminator_index = block_data.statements.len();
+
+        assert!(from.statement_index <= terminator_index);
+        assert!(!to.precedes_in_backward_order(from));
+
+        // Handle the statement (or terminator) at `from`.
+
+        let next_effect = match from.effect {
+            // If we need to apply the terminator effect in all or in part, do so now.
+            _ if from.statement_index == terminator_index => {
+                let location = Location { block, statement_index: from.statement_index };
+                let terminator = block_data.terminator();
+
+                if from.effect == Effect::Before {
+                    analysis.apply_before_terminator_effect(state, terminator, location);
+                    if to == Effect::Before.at_index(terminator_index) {
+                        return;
+                    }
+                }
+
+                analysis.apply_terminator_effect(state, terminator, location);
+                if to == Effect::Primary.at_index(terminator_index) {
+                    return;
+                }
+
+                // If `from.statement_index` is `0`, we will have hit one of the earlier comparisons
+                // with `to`.
+                from.statement_index - 1
+            }
+
+            Effect::Primary => {
+                let location = Location { block, statement_index: from.statement_index };
+                let statement = &block_data.statements[from.statement_index];
+
+                analysis.apply_statement_effect(state, statement, location);
+                if to == Effect::Primary.at_index(from.statement_index) {
+                    return;
+                }
+
+                from.statement_index - 1
+            }
+
+            Effect::Before => from.statement_index,
+        };
+
+        // Handle all statements between `first_unapplied_idx` and `to.statement_index`.
+
+        for statement_index in (to.statement_index..next_effect).rev().map(|i| i + 1) {
+            let location = Location { block, statement_index };
+            let statement = &block_data.statements[statement_index];
+            analysis.apply_before_statement_effect(state, statement, location);
+            analysis.apply_statement_effect(state, statement, location);
+        }
+
+        // Handle the statement at `to`.
+
+        let location = Location { block, statement_index: to.statement_index };
+        let statement = &block_data.statements[to.statement_index];
+        analysis.apply_before_statement_effect(state, statement, location);
+
+        if to.effect == Effect::Before {
+            return;
+        }
+
+        analysis.apply_statement_effect(state, statement, location);
+    }
+
+    fn visit_results_in_block<F, R>(
+        state: &mut F,
+        block: BasicBlock,
+        block_data: &'mir mir::BasicBlockData<'tcx>,
+        results: &R,
+        vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = F>,
+    ) where
+        R: ResultsVisitable<'tcx, FlowState = F>,
+    {
+        results.reset_to_block_entry(state, block);
+
+        vis.visit_block_end(&state, block_data, block);
+
+        // Terminator
+        let loc = Location { block, statement_index: block_data.statements.len() };
+        let term = block_data.terminator();
+        results.reconstruct_before_terminator_effect(state, term, loc);
+        vis.visit_terminator_before_primary_effect(state, term, loc);
+        results.reconstruct_terminator_effect(state, term, loc);
+        vis.visit_terminator_after_primary_effect(state, term, loc);
+
+        for (statement_index, stmt) in block_data.statements.iter().enumerate().rev() {
+            let loc = Location { block, statement_index };
+            results.reconstruct_before_statement_effect(state, stmt, loc);
+            vis.visit_statement_before_primary_effect(state, stmt, loc);
+            results.reconstruct_statement_effect(state, stmt, loc);
+            vis.visit_statement_after_primary_effect(state, stmt, loc);
+        }
+
+        vis.visit_block_start(state, block_data, block);
+    }
+
+    fn join_state_into_successors_of<A>(
+        analysis: &A,
+        _tcx: TyCtxt<'tcx>,
+        body: &mir::Body<'tcx>,
+        dead_unwinds: Option<&BitSet<BasicBlock>>,
+        exit_state: &mut BitSet<A::Idx>,
+        (bb, _bb_data): (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
+        mut propagate: impl FnMut(BasicBlock, &BitSet<A::Idx>),
+    ) where
+        A: Analysis<'tcx>,
+    {
+        for pred in body.predecessors()[bb].iter().copied() {
+            match body[pred].terminator().kind {
+                // Apply terminator-specific edge effects.
+                //
+                // FIXME(ecstaticmorse): Avoid cloning the exit state unconditionally.
+                mir::TerminatorKind::Call {
+                    destination: Some((return_place, dest)),
+                    ref func,
+                    ref args,
+                    ..
+                } if dest == bb => {
+                    let mut tmp = exit_state.clone();
+                    analysis.apply_call_return_effect(&mut tmp, pred, func, args, return_place);
+                    propagate(pred, &tmp);
+                }
+
+                mir::TerminatorKind::Yield { resume, resume_arg, .. } if resume == bb => {
+                    let mut tmp = exit_state.clone();
+                    analysis.apply_yield_resume_effect(&mut tmp, resume, resume_arg);
+                    propagate(pred, &tmp);
+                }
+
+                // Ignore dead unwinds.
+                mir::TerminatorKind::Call { cleanup: Some(unwind), .. }
+                | mir::TerminatorKind::Assert { cleanup: Some(unwind), .. }
+                | mir::TerminatorKind::Drop { unwind: Some(unwind), .. }
+                | mir::TerminatorKind::DropAndReplace { unwind: Some(unwind), .. }
+                | mir::TerminatorKind::FalseUnwind { unwind: Some(unwind), .. }
+                    if unwind == bb =>
+                {
+                    if dead_unwinds.map_or(true, |dead| !dead.contains(bb)) {
+                        propagate(pred, exit_state);
+                    }
+                }
+
+                _ => propagate(pred, exit_state),
+            }
+        }
+    }
+}
+
+/// Dataflow that runs from the entry of a block (the first statement), to its exit (terminator).
+pub struct Forward;
+
+impl Direction for Forward {
+    fn is_forward() -> bool {
+        true
+    }
+
+    fn apply_effects_in_block<A>(
+        analysis: &A,
+        state: &mut BitSet<A::Idx>,
+        block: BasicBlock,
+        block_data: &mir::BasicBlockData<'tcx>,
+    ) where
+        A: Analysis<'tcx>,
+    {
+        for (statement_index, statement) in block_data.statements.iter().enumerate() {
+            let location = Location { block, statement_index };
+            analysis.apply_before_statement_effect(state, statement, location);
+            analysis.apply_statement_effect(state, statement, location);
+        }
+
+        let terminator = block_data.terminator();
+        let location = Location { block, statement_index: block_data.statements.len() };
+        analysis.apply_before_terminator_effect(state, terminator, location);
+        analysis.apply_terminator_effect(state, terminator, location);
+    }
+
+    fn gen_kill_effects_in_block<A>(
+        analysis: &A,
+        trans: &mut GenKillSet<A::Idx>,
+        block: BasicBlock,
+        block_data: &mir::BasicBlockData<'tcx>,
+    ) where
+        A: GenKillAnalysis<'tcx>,
+    {
+        for (statement_index, statement) in block_data.statements.iter().enumerate() {
+            let location = Location { block, statement_index };
+            analysis.before_statement_effect(trans, statement, location);
+            analysis.statement_effect(trans, statement, location);
+        }
+
+        let terminator = block_data.terminator();
+        let location = Location { block, statement_index: block_data.statements.len() };
+        analysis.before_terminator_effect(trans, terminator, location);
+        analysis.terminator_effect(trans, terminator, location);
+    }
+
+    fn apply_effects_in_range<A>(
+        analysis: &A,
+        state: &mut BitSet<A::Idx>,
+        block: BasicBlock,
+        block_data: &mir::BasicBlockData<'tcx>,
+        effects: RangeInclusive<EffectIndex>,
+    ) where
+        A: Analysis<'tcx>,
+    {
+        let (from, to) = (*effects.start(), *effects.end());
+        let terminator_index = block_data.statements.len();
+
+        assert!(to.statement_index <= terminator_index);
+        assert!(!to.precedes_in_forward_order(from));
+
+        // If we have applied the before affect of the statement or terminator at `from` but not its
+        // after effect, do so now and start the loop below from the next statement.
+
+        let first_unapplied_index = match from.effect {
+            Effect::Before => from.statement_index,
+
+            Effect::Primary if from.statement_index == terminator_index => {
+                debug_assert_eq!(from, to);
+
+                let location = Location { block, statement_index: terminator_index };
+                let terminator = block_data.terminator();
+                analysis.apply_terminator_effect(state, terminator, location);
+                return;
+            }
+
+            Effect::Primary => {
+                let location = Location { block, statement_index: from.statement_index };
+                let statement = &block_data.statements[from.statement_index];
+                analysis.apply_statement_effect(state, statement, location);
+
+                // If we only needed to apply the after effect of the statement at `idx`, we are done.
+                if from == to {
+                    return;
+                }
+
+                from.statement_index + 1
+            }
+        };
+
+        // Handle all statements between `from` and `to` whose effects must be applied in full.
+
+        for statement_index in first_unapplied_index..to.statement_index {
+            let location = Location { block, statement_index };
+            let statement = &block_data.statements[statement_index];
+            analysis.apply_before_statement_effect(state, statement, location);
+            analysis.apply_statement_effect(state, statement, location);
+        }
+
+        // Handle the statement or terminator at `to`.
+
+        let location = Location { block, statement_index: to.statement_index };
+        if to.statement_index == terminator_index {
+            let terminator = block_data.terminator();
+            analysis.apply_before_terminator_effect(state, terminator, location);
+
+            if to.effect == Effect::Primary {
+                analysis.apply_terminator_effect(state, terminator, location);
+            }
+        } else {
+            let statement = &block_data.statements[to.statement_index];
+            analysis.apply_before_statement_effect(state, statement, location);
+
+            if to.effect == Effect::Primary {
+                analysis.apply_statement_effect(state, statement, location);
+            }
+        }
+    }
+
+    fn visit_results_in_block<F, R>(
+        state: &mut F,
+        block: BasicBlock,
+        block_data: &'mir mir::BasicBlockData<'tcx>,
+        results: &R,
+        vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = F>,
+    ) where
+        R: ResultsVisitable<'tcx, FlowState = F>,
+    {
+        results.reset_to_block_entry(state, block);
+
+        vis.visit_block_start(state, block_data, block);
+
+        for (statement_index, stmt) in block_data.statements.iter().enumerate() {
+            let loc = Location { block, statement_index };
+            results.reconstruct_before_statement_effect(state, stmt, loc);
+            vis.visit_statement_before_primary_effect(state, stmt, loc);
+            results.reconstruct_statement_effect(state, stmt, loc);
+            vis.visit_statement_after_primary_effect(state, stmt, loc);
+        }
+
+        let loc = Location { block, statement_index: block_data.statements.len() };
+        let term = block_data.terminator();
+        results.reconstruct_before_terminator_effect(state, term, loc);
+        vis.visit_terminator_before_primary_effect(state, term, loc);
+        results.reconstruct_terminator_effect(state, term, loc);
+        vis.visit_terminator_after_primary_effect(state, term, loc);
+
+        vis.visit_block_end(state, block_data, block);
+    }
+
+    fn join_state_into_successors_of<A>(
+        analysis: &A,
+        tcx: TyCtxt<'tcx>,
+        body: &mir::Body<'tcx>,
+        dead_unwinds: Option<&BitSet<BasicBlock>>,
+        exit_state: &mut BitSet<A::Idx>,
+        (bb, bb_data): (BasicBlock, &'_ mir::BasicBlockData<'tcx>),
+        mut propagate: impl FnMut(BasicBlock, &BitSet<A::Idx>),
+    ) where
+        A: Analysis<'tcx>,
+    {
+        use mir::TerminatorKind::*;
+        match bb_data.terminator().kind {
+            Return | Resume | Abort | GeneratorDrop | Unreachable => {}
+
+            Goto { target } => propagate(target, exit_state),
+
+            Assert { target, cleanup: unwind, expected: _, msg: _, cond: _ }
+            | Drop { target, unwind, location: _ }
+            | DropAndReplace { target, unwind, value: _, location: _ }
+            | FalseUnwind { real_target: target, unwind } => {
+                if let Some(unwind) = unwind {
+                    if dead_unwinds.map_or(true, |dead| !dead.contains(bb)) {
+                        propagate(unwind, exit_state);
+                    }
+                }
+
+                propagate(target, exit_state);
+            }
+
+            FalseEdges { real_target, imaginary_target } => {
+                propagate(real_target, exit_state);
+                propagate(imaginary_target, exit_state);
+            }
+
+            Yield { resume: target, drop, resume_arg, value: _ } => {
+                if let Some(drop) = drop {
+                    propagate(drop, exit_state);
+                }
+
+                analysis.apply_yield_resume_effect(exit_state, target, resume_arg);
+                propagate(target, exit_state);
+            }
+
+            Call { cleanup, destination, ref func, ref args, from_hir_call: _ } => {
+                if let Some(unwind) = cleanup {
+                    if dead_unwinds.map_or(true, |dead| !dead.contains(bb)) {
+                        propagate(unwind, exit_state);
+                    }
+                }
+
+                if let Some((dest_place, target)) = destination {
+                    // N.B.: This must be done *last*, otherwise the unwind path will see the call
+                    // return effect.
+                    analysis.apply_call_return_effect(exit_state, bb, func, args, dest_place);
+                    propagate(target, exit_state);
+                }
+            }
+
+            SwitchInt { ref targets, ref values, ref discr, switch_ty: _ } => {
+                let enum_ = discr
+                    .place()
+                    .and_then(|discr| switch_on_enum_discriminant(tcx, &body, bb_data, discr));
+                match enum_ {
+                    // If this is a switch on an enum discriminant, a custom effect may be applied
+                    // along each outgoing edge.
+                    Some((enum_place, enum_def)) => {
+                        // MIR building adds discriminants to the `values` array in the same order as they
+                        // are yielded by `AdtDef::discriminants`. We rely on this to match each
+                        // discriminant in `values` to its corresponding variant in linear time.
+                        let mut tmp = BitSet::new_empty(exit_state.domain_size());
+                        let mut discriminants = enum_def.discriminants(tcx);
+                        for (value, target) in values.iter().zip(targets.iter().copied()) {
+                            let (variant_idx, _) =
+                                discriminants.find(|&(_, discr)| discr.val == *value).expect(
+                                    "Order of `AdtDef::discriminants` differed \
+                                         from that of `SwitchInt::values`",
+                                );
+
+                            tmp.overwrite(exit_state);
+                            analysis.apply_discriminant_switch_effect(
+                                &mut tmp,
+                                bb,
+                                enum_place,
+                                enum_def,
+                                variant_idx,
+                            );
+                            propagate(target, &tmp);
+                        }
+
+                        // Move out of `tmp` so we don't accidentally use it below.
+                        std::mem::drop(tmp);
+
+                        // Propagate dataflow state along the "otherwise" edge.
+                        let otherwise = targets.last().copied().unwrap();
+                        propagate(otherwise, exit_state)
+                    }
+
+                    // Otherwise, it's just a normal `SwitchInt`, and every successor sees the same
+                    // exit state.
+                    None => {
+                        for target in targets.iter().copied() {
+                            propagate(target, exit_state);
+                        }
+                    }
+                }
+            }
+        }
+    }
+}
+
+/// Inspect a `SwitchInt`-terminated basic block to see if the condition of that `SwitchInt` is
+/// an enum discriminant.
+///
+/// We expect such blocks to have a call to `discriminant` as their last statement like so:
+///   _42 = discriminant(_1)
+///   SwitchInt(_42, ..)
+///
+/// If the basic block matches this pattern, this function returns the place corresponding to the
+/// enum (`_1` in the example above) as well as the `AdtDef` of that enum.
+fn switch_on_enum_discriminant(
+    tcx: TyCtxt<'tcx>,
+    body: &'mir mir::Body<'tcx>,
+    block: &'mir mir::BasicBlockData<'tcx>,
+    switch_on: mir::Place<'tcx>,
+) -> Option<(mir::Place<'tcx>, &'tcx ty::AdtDef)> {
+    match block.statements.last().map(|stmt| &stmt.kind) {
+        Some(mir::StatementKind::Assign(box (lhs, mir::Rvalue::Discriminant(discriminated))))
+            if *lhs == switch_on =>
+        {
+            match &discriminated.ty(body, tcx).ty.kind {
+                ty::Adt(def, _) => Some((*discriminated, def)),
+
+                // `Rvalue::Discriminant` is also used to get the active yield point for a
+                // generator, but we do not need edge-specific effects in that case. This may
+                // change in the future.
+                ty::Generator(..) => None,
+
+                t => bug!("`discriminant` called on unexpected type {:?}", t),
+            }
+        }
+
+        _ => None,
+    }
+}
diff --git a/src/librustc_mir/dataflow/framework/engine.rs b/src/librustc_mir/dataflow/framework/engine.rs
index 2a9d2d99c8a..32e569fdc35 100644
--- a/src/librustc_mir/dataflow/framework/engine.rs
+++ b/src/librustc_mir/dataflow/framework/engine.rs
@@ -9,14 +9,58 @@ use rustc_data_structures::work_queue::WorkQueue;
 use rustc_hir::def_id::DefId;
 use rustc_index::bit_set::BitSet;
 use rustc_index::vec::IndexVec;
-use rustc_middle::mir::{self, traversal, BasicBlock, Location};
+use rustc_middle::mir::{self, traversal, BasicBlock};
 use rustc_middle::ty::{self, TyCtxt};
 use rustc_span::symbol::{sym, Symbol};
 
 use super::graphviz;
-use super::{Analysis, GenKillAnalysis, GenKillSet, Results};
+use super::{
+    visit_results, Analysis, Direction, GenKillAnalysis, GenKillSet, ResultsCursor, ResultsVisitor,
+};
 use crate::util::pretty::dump_enabled;
 
+/// A dataflow analysis that has converged to fixpoint.
+pub struct Results<'tcx, A>
+where
+    A: Analysis<'tcx>,
+{
+    pub analysis: A,
+    pub(super) entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>,
+}
+
+impl<A> Results<'tcx, A>
+where
+    A: Analysis<'tcx>,
+{
+    /// Creates a `ResultsCursor` that can inspect these `Results`.
+    pub fn into_results_cursor(self, body: &'mir mir::Body<'tcx>) -> ResultsCursor<'mir, 'tcx, A> {
+        ResultsCursor::new(body, self)
+    }
+
+    /// Gets the dataflow state for the given block.
+    pub fn entry_set_for_block(&self, block: BasicBlock) -> &BitSet<A::Idx> {
+        &self.entry_sets[block]
+    }
+
+    pub fn visit_with(
+        &self,
+        body: &'mir mir::Body<'tcx>,
+        blocks: impl IntoIterator<Item = BasicBlock>,
+        vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = BitSet<A::Idx>>,
+    ) {
+        visit_results(body, blocks, self, vis)
+    }
+
+    pub fn visit_in_rpo_with(
+        &self,
+        body: &'mir mir::Body<'tcx>,
+        vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = BitSet<A::Idx>>,
+    ) {
+        let blocks = mir::traversal::reverse_postorder(body);
+        visit_results(body, blocks.map(|(bb, _)| bb), self, vis)
+    }
+}
+
 /// A solver for dataflow problems.
 pub struct Engine<'a, 'tcx, A>
 where
@@ -61,17 +105,7 @@ where
 
         for (block, block_data) in body.basic_blocks().iter_enumerated() {
             let trans = &mut trans_for_block[block];
-
-            for (i, statement) in block_data.statements.iter().enumerate() {
-                let loc = Location { block, statement_index: i };
-                analysis.before_statement_effect(trans, statement, loc);
-                analysis.statement_effect(trans, statement, loc);
-            }
-
-            let terminator = block_data.terminator();
-            let loc = Location { block, statement_index: block_data.statements.len() };
-            analysis.before_terminator_effect(trans, terminator, loc);
-            analysis.terminator_effect(trans, terminator, loc);
+            A::Direction::gen_kill_effects_in_block(&analysis, trans, block, block_data);
         }
 
         Self::new(tcx, body, def_id, analysis, Some(trans_for_block))
@@ -111,9 +145,13 @@ where
             BitSet::new_empty(bits_per_block)
         };
 
-        let mut entry_sets = IndexVec::from_elem(bottom_value_set, body.basic_blocks());
+        let mut entry_sets = IndexVec::from_elem(bottom_value_set.clone(), body.basic_blocks());
         analysis.initialize_start_block(body, &mut entry_sets[mir::START_BLOCK]);
 
+        if A::Direction::is_backward() && entry_sets[mir::START_BLOCK] != bottom_value_set {
+            bug!("`initialize_start_block` is not yet supported for backward dataflow analyses");
+        }
+
         Engine {
             analysis,
             bits_per_block,
@@ -137,251 +175,79 @@ where
     }
 
     /// Computes the fixpoint for this dataflow problem and returns it.
-    pub fn iterate_to_fixpoint(mut self) -> Results<'tcx, A> {
-        let mut temp_state = BitSet::new_empty(self.bits_per_block);
+    pub fn iterate_to_fixpoint(self) -> Results<'tcx, A> {
+        let Engine {
+            analysis,
+            bits_per_block,
+            body,
+            dead_unwinds,
+            def_id,
+            mut entry_sets,
+            tcx,
+            trans_for_block,
+            ..
+        } = self;
 
         let mut dirty_queue: WorkQueue<BasicBlock> =
-            WorkQueue::with_none(self.body.basic_blocks().len());
+            WorkQueue::with_none(body.basic_blocks().len());
 
-        for (bb, _) in traversal::reverse_postorder(self.body) {
-            dirty_queue.insert(bb);
+        if A::Direction::is_forward() {
+            for (bb, _) in traversal::reverse_postorder(body) {
+                dirty_queue.insert(bb);
+            }
+        } else {
+            // Reverse post-order on the reverse CFG may generate a better iteration order for
+            // backward dataflow analyses, but probably not enough to matter.
+            for (bb, _) in traversal::postorder(body) {
+                dirty_queue.insert(bb);
+            }
         }
 
         // Add blocks that are not reachable from START_BLOCK to the work queue. These blocks will
         // be processed after the ones added above.
-        for bb in self.body.basic_blocks().indices() {
+        //
+        // FIXME(ecstaticmorse): Is this actually necessary? In principle, we shouldn't need to
+        // know the dataflow state in unreachable basic blocks.
+        for bb in body.basic_blocks().indices() {
             dirty_queue.insert(bb);
         }
 
+        let mut state = BitSet::new_empty(bits_per_block);
         while let Some(bb) = dirty_queue.pop() {
-            let bb_data = &self.body[bb];
-            let on_entry = &self.entry_sets[bb];
+            let bb_data = &body[bb];
 
-            temp_state.overwrite(on_entry);
-            self.apply_whole_block_effect(&mut temp_state, bb, bb_data);
+            // Apply the block transfer function, using the cached one if it exists.
+            state.overwrite(&entry_sets[bb]);
+            match &trans_for_block {
+                Some(trans_for_block) => trans_for_block[bb].apply(&mut state),
+                None => A::Direction::apply_effects_in_block(&analysis, &mut state, bb, bb_data),
+            }
 
-            self.propagate_bits_into_graph_successors_of(
-                &mut temp_state,
+            A::Direction::join_state_into_successors_of(
+                &analysis,
+                tcx,
+                body,
+                dead_unwinds,
+                &mut state,
                 (bb, bb_data),
-                &mut dirty_queue,
+                |target: BasicBlock, state: &BitSet<A::Idx>| {
+                    let set_changed = analysis.join(&mut entry_sets[target], state);
+                    if set_changed {
+                        dirty_queue.insert(target);
+                    }
+                },
             );
         }
 
-        let Engine { tcx, body, def_id, trans_for_block, entry_sets, analysis, .. } = self;
         let results = Results { analysis, entry_sets };
 
-        let res = write_graphviz_results(tcx, def_id, body, &results, trans_for_block);
+        let res = write_graphviz_results(tcx, def_id, &body, &results, trans_for_block);
         if let Err(e) = res {
             warn!("Failed to write graphviz dataflow results: {}", e);
         }
 
         results
     }
-
-    /// Applies the cumulative effect of an entire block, excluding the call return effect if one
-    /// exists.
-    fn apply_whole_block_effect(
-        &self,
-        state: &mut BitSet<A::Idx>,
-        block: BasicBlock,
-        block_data: &mir::BasicBlockData<'tcx>,
-    ) {
-        // Use the cached block transfer function if available.
-        if let Some(trans_for_block) = &self.trans_for_block {
-            trans_for_block[block].apply(state);
-            return;
-        }
-
-        // Otherwise apply effects one-by-one.
-
-        for (statement_index, statement) in block_data.statements.iter().enumerate() {
-            let location = Location { block, statement_index };
-            self.analysis.apply_before_statement_effect(state, statement, location);
-            self.analysis.apply_statement_effect(state, statement, location);
-        }
-
-        let terminator = block_data.terminator();
-        let location = Location { block, statement_index: block_data.statements.len() };
-        self.analysis.apply_before_terminator_effect(state, terminator, location);
-        self.analysis.apply_terminator_effect(state, terminator, location);
-    }
-
-    fn propagate_bits_into_graph_successors_of(
-        &mut self,
-        in_out: &mut BitSet<A::Idx>,
-        (bb, bb_data): (BasicBlock, &'a mir::BasicBlockData<'tcx>),
-        dirty_list: &mut WorkQueue<BasicBlock>,
-    ) {
-        use mir::TerminatorKind::*;
-
-        match bb_data.terminator().kind {
-            Return | Resume | Abort | GeneratorDrop | Unreachable => {}
-
-            Goto { target }
-            | Assert { target, cleanup: None, .. }
-            | Drop { target, location: _, unwind: None }
-            | DropAndReplace { target, value: _, location: _, unwind: None } => {
-                self.propagate_bits_into_entry_set_for(in_out, target, dirty_list)
-            }
-
-            Yield { resume: target, drop, resume_arg, .. } => {
-                if let Some(drop) = drop {
-                    self.propagate_bits_into_entry_set_for(in_out, drop, dirty_list);
-                }
-
-                self.analysis.apply_yield_resume_effect(in_out, target, resume_arg);
-                self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
-            }
-
-            Assert { target, cleanup: Some(unwind), .. }
-            | Drop { target, location: _, unwind: Some(unwind) }
-            | DropAndReplace { target, value: _, location: _, unwind: Some(unwind) } => {
-                self.propagate_bits_into_entry_set_for(in_out, target, dirty_list);
-                if self.dead_unwinds.map_or(true, |bbs| !bbs.contains(bb)) {
-                    self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
-                }
-            }
-
-            SwitchInt { ref targets, ref values, ref discr, .. } => {
-                let Engine { tcx, body, .. } = *self;
-                let enum_ = discr
-                    .place()
-                    .and_then(|discr| switch_on_enum_discriminant(tcx, body, bb_data, discr));
-                match enum_ {
-                    // If this is a switch on an enum discriminant, a custom effect may be applied
-                    // along each outgoing edge.
-                    Some((enum_place, enum_def)) => {
-                        self.propagate_bits_into_enum_discriminant_switch_successors(
-                            in_out, bb, enum_def, enum_place, dirty_list, &*values, &*targets,
-                        );
-                    }
-
-                    // Otherwise, it's just a normal `SwitchInt`, and every successor sees the same
-                    // exit state.
-                    None => {
-                        for target in targets.iter().copied() {
-                            self.propagate_bits_into_entry_set_for(&in_out, target, dirty_list);
-                        }
-                    }
-                }
-            }
-
-            Call { cleanup, ref destination, ref func, ref args, .. } => {
-                if let Some(unwind) = cleanup {
-                    if self.dead_unwinds.map_or(true, |bbs| !bbs.contains(bb)) {
-                        self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
-                    }
-                }
-
-                if let Some((dest_place, dest_bb)) = *destination {
-                    // N.B.: This must be done *last*, otherwise the unwind path will see the call
-                    // return effect.
-                    self.analysis.apply_call_return_effect(in_out, bb, func, args, dest_place);
-                    self.propagate_bits_into_entry_set_for(in_out, dest_bb, dirty_list);
-                }
-            }
-
-            FalseEdges { real_target, imaginary_target } => {
-                self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
-                self.propagate_bits_into_entry_set_for(in_out, imaginary_target, dirty_list);
-            }
-
-            FalseUnwind { real_target, unwind } => {
-                self.propagate_bits_into_entry_set_for(in_out, real_target, dirty_list);
-                if let Some(unwind) = unwind {
-                    if self.dead_unwinds.map_or(true, |bbs| !bbs.contains(bb)) {
-                        self.propagate_bits_into_entry_set_for(in_out, unwind, dirty_list);
-                    }
-                }
-            }
-        }
-    }
-
-    fn propagate_bits_into_entry_set_for(
-        &mut self,
-        in_out: &BitSet<A::Idx>,
-        bb: BasicBlock,
-        dirty_queue: &mut WorkQueue<BasicBlock>,
-    ) {
-        let entry_set = &mut self.entry_sets[bb];
-        let set_changed = self.analysis.join(entry_set, &in_out);
-        if set_changed {
-            dirty_queue.insert(bb);
-        }
-    }
-
-    fn propagate_bits_into_enum_discriminant_switch_successors(
-        &mut self,
-        in_out: &mut BitSet<A::Idx>,
-        bb: BasicBlock,
-        enum_def: &'tcx ty::AdtDef,
-        enum_place: mir::Place<'tcx>,
-        dirty_list: &mut WorkQueue<BasicBlock>,
-        values: &[u128],
-        targets: &[BasicBlock],
-    ) {
-        // MIR building adds discriminants to the `values` array in the same order as they
-        // are yielded by `AdtDef::discriminants`. We rely on this to match each
-        // discriminant in `values` to its corresponding variant in linear time.
-        let mut tmp = BitSet::new_empty(in_out.domain_size());
-        let mut discriminants = enum_def.discriminants(self.tcx);
-        for (value, target) in values.iter().zip(targets.iter().copied()) {
-            let (variant_idx, _) = discriminants.find(|&(_, discr)| discr.val == *value).expect(
-                "Order of `AdtDef::discriminants` differed from that of `SwitchInt::values`",
-            );
-
-            tmp.overwrite(in_out);
-            self.analysis.apply_discriminant_switch_effect(
-                &mut tmp,
-                bb,
-                enum_place,
-                enum_def,
-                variant_idx,
-            );
-            self.propagate_bits_into_entry_set_for(&tmp, target, dirty_list);
-        }
-
-        std::mem::drop(tmp);
-
-        // Propagate dataflow state along the "otherwise" edge.
-        let otherwise = targets.last().copied().unwrap();
-        self.propagate_bits_into_entry_set_for(&in_out, otherwise, dirty_list);
-    }
-}
-
-/// Inspect a `SwitchInt`-terminated basic block to see if the condition of that `SwitchInt` is
-/// an enum discriminant.
-///
-/// We expect such blocks to have a call to `discriminant` as their last statement like so:
-///   _42 = discriminant(_1)
-///   SwitchInt(_42, ..)
-///
-/// If the basic block matches this pattern, this function returns the place corresponding to the
-/// enum (`_1` in the example above) as well as the `AdtDef` of that enum.
-fn switch_on_enum_discriminant(
-    tcx: TyCtxt<'tcx>,
-    body: &'mir mir::Body<'tcx>,
-    block: &'mir mir::BasicBlockData<'tcx>,
-    switch_on: mir::Place<'tcx>,
-) -> Option<(mir::Place<'tcx>, &'tcx ty::AdtDef)> {
-    match block.statements.last().map(|stmt| &stmt.kind) {
-        Some(mir::StatementKind::Assign(box (lhs, mir::Rvalue::Discriminant(discriminated))))
-            if *lhs == switch_on =>
-        {
-            match &discriminated.ty(body, tcx).ty.kind {
-                ty::Adt(def, _) => Some((*discriminated, def)),
-
-                // `Rvalue::Discriminant` is also used to get the active yield point for a
-                // generator, but we do not need edge-specific effects in that case. This may
-                // change in the future.
-                ty::Generator(..) => None,
-
-                t => bug!("`discriminant` called on unexpected type {:?}", t),
-            }
-        }
-
-        _ => None,
-    }
 }
 
 // Graphviz
@@ -431,12 +297,12 @@ where
             if let Some(trans_for_block) = block_transfer_functions {
                 Box::new(graphviz::BlockTransferFunc::new(body, trans_for_block))
             } else {
-                Box::new(graphviz::SimpleDiff::new(bits_per_block))
+                Box::new(graphviz::SimpleDiff::new(body, &results))
             }
         }
 
         // Default to the `SimpleDiff` output style.
-        _ => Box::new(graphviz::SimpleDiff::new(bits_per_block)),
+        _ => Box::new(graphviz::SimpleDiff::new(body, &results)),
     };
 
     debug!("printing dataflow results for {:?} to {}", def_id, path.display());
diff --git a/src/librustc_mir/dataflow/framework/graphviz.rs b/src/librustc_mir/dataflow/framework/graphviz.rs
index bdd41121359..e3ba26eaf8b 100644
--- a/src/librustc_mir/dataflow/framework/graphviz.rs
+++ b/src/librustc_mir/dataflow/framework/graphviz.rs
@@ -8,7 +8,7 @@ use rustc_index::bit_set::{BitSet, HybridBitSet};
 use rustc_index::vec::{Idx, IndexVec};
 use rustc_middle::mir::{self, BasicBlock, Body, Location};
 
-use super::{Analysis, GenKillSet, Results, ResultsRefCursor};
+use super::{Analysis, Direction, GenKillSet, Results, ResultsRefCursor};
 use crate::util::graphviz_safe_def_name;
 
 pub struct Formatter<'a, 'tcx, A>
@@ -49,7 +49,7 @@ pub struct CfgEdge {
     index: usize,
 }
 
-fn outgoing_edges(body: &Body<'_>, bb: BasicBlock) -> Vec<CfgEdge> {
+fn dataflow_successors(body: &Body<'tcx>, bb: BasicBlock) -> Vec<CfgEdge> {
     body[bb]
         .terminator()
         .successors()
@@ -105,7 +105,7 @@ where
         self.body
             .basic_blocks()
             .indices()
-            .flat_map(|bb| outgoing_edges(self.body, bb))
+            .flat_map(|bb| dataflow_successors(self.body, bb))
             .collect::<Vec<_>>()
             .into()
     }
@@ -192,12 +192,12 @@ where
             self.write_block_header_with_state_columns(w, block)?;
         }
 
-        // C: Entry state
+        // C: State at start of block
         self.bg = Background::Light;
         self.results.seek_to_block_start(block);
         let block_entry_state = self.results.get().clone();
 
-        self.write_row_with_full_state(w, "", "(on entry)")?;
+        self.write_row_with_full_state(w, "", "(on start)")?;
 
         // D: Statement transfer functions
         for (i, statement) in body[block].statements.iter().enumerate() {
@@ -214,37 +214,72 @@ where
 
         self.write_row_for_location(w, "T", &terminator_str, terminator_loc)?;
 
-        // F: Exit state
+        // F: State at end of block
 
         // Write the full dataflow state immediately after the terminator if it differs from the
         // state at block entry.
-        self.results.seek_after(terminator_loc);
-        if self.results.get() != &block_entry_state {
+        self.results.seek_to_block_end(block);
+        if self.results.get() != &block_entry_state || A::Direction::is_backward() {
             let after_terminator_name = match terminator.kind {
                 mir::TerminatorKind::Call { destination: Some(_), .. } => "(on unwind)",
-                _ => "(on exit)",
+                _ => "(on end)",
             };
 
             self.write_row_with_full_state(w, "", after_terminator_name)?;
         }
 
         // Write any changes caused by terminator-specific effects
-        if let mir::TerminatorKind::Call { destination: Some(_), .. } = terminator.kind {
-            let num_state_columns = self.num_state_columns();
-            self.write_row(w, "", "(on successful return)", |this, w, fmt| {
-                write!(
-                    w,
-                    r#"<td balign="left" colspan="{colspan}" {fmt} align="left">"#,
-                    colspan = num_state_columns,
-                    fmt = fmt,
-                )?;
-
-                let state_on_unwind = this.results.get().clone();
-                this.results.seek_after_assume_success(terminator_loc);
-                write_diff(w, this.results.analysis(), &state_on_unwind, this.results.get())?;
-
-                write!(w, "</td>")
-            })?;
+        let num_state_columns = self.num_state_columns();
+        match terminator.kind {
+            mir::TerminatorKind::Call {
+                destination: Some((return_place, _)),
+                ref func,
+                ref args,
+                ..
+            } => {
+                self.write_row(w, "", "(on successful return)", |this, w, fmt| {
+                    write!(
+                        w,
+                        r#"<td balign="left" colspan="{colspan}" {fmt} align="left">"#,
+                        colspan = num_state_columns,
+                        fmt = fmt,
+                    )?;
+
+                    let state_on_unwind = this.results.get().clone();
+                    this.results.apply_custom_effect(|analysis, state| {
+                        analysis.apply_call_return_effect(state, block, func, args, return_place);
+                    });
+
+                    write_diff(w, this.results.analysis(), &state_on_unwind, this.results.get())?;
+                    write!(w, "</td>")
+                })?;
+            }
+
+            mir::TerminatorKind::Yield { resume, resume_arg, .. } => {
+                self.write_row(w, "", "(on yield resume)", |this, w, fmt| {
+                    write!(
+                        w,
+                        r#"<td balign="left" colspan="{colspan}" {fmt} align="left">"#,
+                        colspan = num_state_columns,
+                        fmt = fmt,
+                    )?;
+
+                    let state_on_generator_drop = this.results.get().clone();
+                    this.results.apply_custom_effect(|analysis, state| {
+                        analysis.apply_yield_resume_effect(state, resume, resume_arg);
+                    });
+
+                    write_diff(
+                        w,
+                        this.results.analysis(),
+                        &state_on_generator_drop,
+                        this.results.get(),
+                    )?;
+                    write!(w, "</td>")
+                })?;
+            }
+
+            _ => {}
         };
 
         write!(w, "</table>")
@@ -403,18 +438,23 @@ where
 }
 
 /// Prints a single column containing the state vector immediately *after* each statement.
-pub struct SimpleDiff<T: Idx> {
-    prev_state: BitSet<T>,
-    prev_loc: Location,
+pub struct SimpleDiff<'a, 'tcx, A>
+where
+    A: Analysis<'tcx>,
+{
+    prev_state: ResultsRefCursor<'a, 'a, 'tcx, A>,
 }
 
-impl<T: Idx> SimpleDiff<T> {
-    pub fn new(bits_per_block: usize) -> Self {
-        SimpleDiff { prev_state: BitSet::new_empty(bits_per_block), prev_loc: Location::START }
+impl<A> SimpleDiff<'a, 'tcx, A>
+where
+    A: Analysis<'tcx>,
+{
+    pub fn new(body: &'a Body<'tcx>, results: &'a Results<'tcx, A>) -> Self {
+        SimpleDiff { prev_state: ResultsRefCursor::new(body, results) }
     }
 }
 
-impl<A> StateFormatter<'tcx, A> for SimpleDiff<A::Idx>
+impl<A> StateFormatter<'tcx, A> for SimpleDiff<'_, 'tcx, A>
 where
     A: Analysis<'tcx>,
 {
@@ -429,20 +469,27 @@ where
         results: &mut ResultsRefCursor<'_, '_, 'tcx, A>,
         location: Location,
     ) -> io::Result<()> {
-        if location.statement_index == 0 {
-            results.seek_to_block_start(location.block);
-            self.prev_state.overwrite(results.get());
+        if A::Direction::is_forward() {
+            if location.statement_index == 0 {
+                self.prev_state.seek_to_block_start(location.block);
+            } else {
+                self.prev_state.seek_after_primary_effect(Location {
+                    statement_index: location.statement_index - 1,
+                    ..location
+                });
+            }
         } else {
-            // Ensure that we are visiting statements in order, so `prev_state` is correct.
-            assert_eq!(self.prev_loc.successor_within_block(), location);
+            if location == results.body().terminator_loc(location.block) {
+                self.prev_state.seek_to_block_end(location.block);
+            } else {
+                self.prev_state.seek_after_primary_effect(location.successor_within_block());
+            }
         }
 
-        self.prev_loc = location;
         write!(w, r#"<td {fmt} balign="left" align="left">"#, fmt = fmt)?;
-        results.seek_after(location);
+        results.seek_after_primary_effect(location);
         let curr_state = results.get();
-        write_diff(&mut w, results.analysis(), &self.prev_state, curr_state)?;
-        self.prev_state.overwrite(curr_state);
+        write_diff(&mut w, results.analysis(), self.prev_state.get(), curr_state)?;
         write!(w, "</td>")
     }
 }
@@ -476,7 +523,7 @@ where
         location: Location,
     ) -> io::Result<()> {
         if location.statement_index == 0 {
-            results.seek_to_block_start(location.block);
+            results.seek_to_block_entry(location.block);
             self.prev_state.overwrite(results.get());
         } else {
             // Ensure that we are visiting statements in order, so `prev_state` is correct.
@@ -488,7 +535,7 @@ where
         // Before
 
         write!(w, r#"<td {fmt} align="left">"#, fmt = fmt)?;
-        results.seek_before(location);
+        results.seek_before_primary_effect(location);
         let curr_state = results.get();
         write_diff(&mut w, results.analysis(), &self.prev_state, curr_state)?;
         self.prev_state.overwrite(curr_state);
@@ -497,7 +544,7 @@ where
         // After
 
         write!(w, r#"<td {fmt} align="left">"#, fmt = fmt)?;
-        results.seek_after(location);
+        results.seek_after_primary_effect(location);
         let curr_state = results.get();
         write_diff(&mut w, results.analysis(), &self.prev_state, curr_state)?;
         self.prev_state.overwrite(curr_state);
diff --git a/src/librustc_mir/dataflow/framework/mod.rs b/src/librustc_mir/dataflow/framework/mod.rs
index 06da8799dd4..a21bbacb467 100644
--- a/src/librustc_mir/dataflow/framework/mod.rs
+++ b/src/librustc_mir/dataflow/framework/mod.rs
@@ -30,67 +30,28 @@
 //!
 //! [gen-kill]: https://en.wikipedia.org/wiki/Data-flow_analysis#Bit_vector_problems
 
+use std::cmp::Ordering;
 use std::io;
 
 use rustc_hir::def_id::DefId;
 use rustc_index::bit_set::{BitSet, HybridBitSet};
-use rustc_index::vec::{Idx, IndexVec};
+use rustc_index::vec::Idx;
 use rustc_middle::mir::{self, BasicBlock, Location};
 use rustc_middle::ty::{self, TyCtxt};
 use rustc_target::abi::VariantIdx;
 
 mod cursor;
+mod direction;
 mod engine;
 mod graphviz;
 mod visitor;
 
 pub use self::cursor::{ResultsCursor, ResultsRefCursor};
-pub use self::engine::Engine;
+pub use self::direction::{Backward, Direction, Forward};
+pub use self::engine::{Engine, Results};
 pub use self::visitor::{visit_results, ResultsVisitor};
 pub use self::visitor::{BorrowckFlowState, BorrowckResults};
 
-/// A dataflow analysis that has converged to fixpoint.
-pub struct Results<'tcx, A>
-where
-    A: Analysis<'tcx>,
-{
-    pub analysis: A,
-    entry_sets: IndexVec<BasicBlock, BitSet<A::Idx>>,
-}
-
-impl<A> Results<'tcx, A>
-where
-    A: Analysis<'tcx>,
-{
-    /// Creates a `ResultsCursor` that can inspect these `Results`.
-    pub fn into_results_cursor(self, body: &'mir mir::Body<'tcx>) -> ResultsCursor<'mir, 'tcx, A> {
-        ResultsCursor::new(body, self)
-    }
-
-    /// Gets the entry set for the given block.
-    pub fn entry_set_for_block(&self, block: BasicBlock) -> &BitSet<A::Idx> {
-        &self.entry_sets[block]
-    }
-
-    pub fn visit_with(
-        &self,
-        body: &'mir mir::Body<'tcx>,
-        blocks: impl IntoIterator<Item = BasicBlock>,
-        vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = BitSet<A::Idx>>,
-    ) {
-        visit_results(body, blocks, self, vis)
-    }
-
-    pub fn visit_in_rpo_with(
-        &self,
-        body: &'mir mir::Body<'tcx>,
-        vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = BitSet<A::Idx>>,
-    ) {
-        let blocks = mir::traversal::reverse_postorder(body);
-        visit_results(body, blocks.map(|(bb, _)| bb), self, vis)
-    }
-}
-
 /// Parameterization for the precise form of data flow that is used.
 ///
 /// `BottomValue` determines whether the initial entry set for each basic block is empty or full.
@@ -144,6 +105,9 @@ pub trait AnalysisDomain<'tcx>: BottomValue {
     /// The type of the elements in the state vector.
     type Idx: Idx;
 
+    /// The direction of this analyis. Either `Forward` or `Backward`.
+    type Direction: Direction = Forward;
+
     /// A descriptive name for this analysis. Used only for debugging.
     ///
     /// This name should be brief and contain no spaces, periods or other characters that are not
@@ -155,6 +119,13 @@ pub trait AnalysisDomain<'tcx>: BottomValue {
 
     /// Mutates the entry set of the `START_BLOCK` to contain the initial state for dataflow
     /// analysis.
+    ///
+    /// For backward analyses, initial state besides the bottom value is not yet supported. Trying
+    /// to mutate the initial state will result in a panic.
+    //
+    // FIXME: For backward dataflow analyses, the initial state should be applied to every basic
+    // block where control flow could exit the MIR body (e.g., those terminated with `return` or
+    // `resume`). It's not obvious how to handle `yield` points in generators, however.
     fn initialize_start_block(&self, body: &mir::Body<'tcx>, state: &mut BitSet<Self::Idx>);
 
     /// Prints an element in the state vector for debugging.
@@ -247,6 +218,8 @@ pub trait Analysis<'tcx>: AnalysisDomain<'tcx> {
     ///
     /// Much like `apply_call_return_effect`, this effect is only propagated along a single
     /// outgoing edge from this basic block.
+    ///
+    /// FIXME: This class of effects is not supported for backward dataflow analyses.
     fn apply_discriminant_switch_effect(
         &self,
         _state: &mut BitSet<Self::Idx>,
@@ -338,7 +311,7 @@ pub trait GenKillAnalysis<'tcx>: Analysis<'tcx> {
     /// See `Analysis::apply_yield_resume_effect`.
     fn yield_resume_effect(
         &self,
-        _trans: &mut BitSet<Self::Idx>,
+        _trans: &mut impl GenKill<Self::Idx>,
         _resume_block: BasicBlock,
         _resume_place: mir::Place<'tcx>,
     ) {
@@ -520,5 +493,64 @@ impl<T: Idx> GenKill<T> for BitSet<T> {
     }
 }
 
+// NOTE: DO NOT CHANGE VARIANT ORDER. The derived `Ord` impls rely on the current order.
+#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
+pub enum Effect {
+    /// The "before" effect (e.g., `apply_before_statement_effect`) for a statement (or
+    /// terminator).
+    Before,
+
+    /// The "primary" effect (e.g., `apply_statement_effect`) for a statement (or terminator).
+    Primary,
+}
+
+impl Effect {
+    pub const fn at_index(self, statement_index: usize) -> EffectIndex {
+        EffectIndex { effect: self, statement_index }
+    }
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+pub struct EffectIndex {
+    statement_index: usize,
+    effect: Effect,
+}
+
+impl EffectIndex {
+    fn next_in_forward_order(self) -> Self {
+        match self.effect {
+            Effect::Before => Effect::Primary.at_index(self.statement_index),
+            Effect::Primary => Effect::Before.at_index(self.statement_index + 1),
+        }
+    }
+
+    fn next_in_backward_order(self) -> Self {
+        match self.effect {
+            Effect::Before => Effect::Primary.at_index(self.statement_index),
+            Effect::Primary => Effect::Before.at_index(self.statement_index - 1),
+        }
+    }
+
+    /// Returns `true` if the effect at `self` should be applied eariler than the effect at `other`
+    /// in forward order.
+    fn precedes_in_forward_order(self, other: Self) -> bool {
+        let ord = self
+            .statement_index
+            .cmp(&other.statement_index)
+            .then_with(|| self.effect.cmp(&other.effect));
+        ord == Ordering::Less
+    }
+
+    /// Returns `true` if the effect at `self` should be applied earlier than the effect at `other`
+    /// in backward order.
+    fn precedes_in_backward_order(self, other: Self) -> bool {
+        let ord = other
+            .statement_index
+            .cmp(&self.statement_index)
+            .then_with(|| self.effect.cmp(&other.effect));
+        ord == Ordering::Less
+    }
+}
+
 #[cfg(test)]
 mod tests;
diff --git a/src/librustc_mir/dataflow/framework/tests.rs b/src/librustc_mir/dataflow/framework/tests.rs
index 8c65b7452d1..a8dce7079b7 100644
--- a/src/librustc_mir/dataflow/framework/tests.rs
+++ b/src/librustc_mir/dataflow/framework/tests.rs
@@ -1,5 +1,7 @@
 //! A test for the logic that updates the state in a `ResultsCursor` during seek.
 
+use std::marker::PhantomData;
+
 use rustc_index::bit_set::BitSet;
 use rustc_index::vec::IndexVec;
 use rustc_middle::mir::{self, BasicBlock, Location};
@@ -9,16 +11,6 @@ use rustc_span::DUMMY_SP;
 use super::*;
 use crate::dataflow::BottomValue;
 
-/// Returns `true` if the given location points to a `Call` terminator that can return
-/// successfully.
-fn is_call_terminator_non_diverging(body: &mir::Body<'_>, loc: Location) -> bool {
-    loc == body.terminator_loc(loc.block)
-        && matches!(
-            body[loc.block].terminator().kind,
-            mir::TerminatorKind::Call { destination: Some(_), ..  }
-        )
-}
-
 /// Creates a `mir::Body` with a few disconnected basic blocks.
 ///
 /// This is the `Body` that will be used by the `MockAnalysis` below. The shape of its CFG is not
@@ -79,20 +71,20 @@ fn mock_body() -> mir::Body<'static> {
 /// | Location               | Before            | After  |
 /// |------------------------|-------------------|--------|
 /// | (on_entry)             | {102}                     ||
-/// | Statement 0            | +0                | +1     |
+/// | statement 0            | +0                | +1     |
 /// | statement 1            | +2                | +3     |
 /// | `Call` terminator      | +4                | +5     |
 /// | (on unwind)            | {102,0,1,2,3,4,5}         ||
-/// | (on successful return) | +6                        ||
 ///
 /// The `102` in the block's entry set is derived from the basic block index and ensures that the
 /// expected state is unique across all basic blocks. Remember, it is generated by
 /// `mock_entry_sets`, not from actually running `MockAnalysis` to fixpoint.
-struct MockAnalysis<'tcx> {
+struct MockAnalysis<'tcx, D> {
     body: &'tcx mir::Body<'tcx>,
+    dir: PhantomData<D>,
 }
 
-impl MockAnalysis<'tcx> {
+impl<D: Direction> MockAnalysis<'tcx, D> {
     const BASIC_BLOCK_OFFSET: usize = 100;
 
     /// The entry set for each `BasicBlock` is the ID of that block offset by a fixed amount to
@@ -115,25 +107,14 @@ impl MockAnalysis<'tcx> {
     }
 
     /// Returns the index that should be added to the dataflow state at the given target.
-    ///
-    /// This index is only unique within a given basic block. `SeekAfter` and
-    /// `SeekAfterAssumeCallReturns` have the same effect unless `target` is a `Call` terminator.
-    fn effect_at_target(&self, target: SeekTarget) -> Option<usize> {
-        use SeekTarget::*;
-
-        let idx = match target {
-            BlockStart(_) => return None,
-
-            AfterAssumeCallReturns(loc) if is_call_terminator_non_diverging(self.body, loc) => {
-                loc.statement_index * 2 + 2
-            }
-
-            Before(loc) => loc.statement_index * 2,
-            After(loc) | AfterAssumeCallReturns(loc) => loc.statement_index * 2 + 1,
+    fn effect(&self, loc: EffectIndex) -> usize {
+        let idx = match loc.effect {
+            Effect::Before => loc.statement_index * 2,
+            Effect::Primary => loc.statement_index * 2 + 1,
         };
 
         assert!(idx < Self::BASIC_BLOCK_OFFSET, "Too many statements in basic block");
-        Some(idx)
+        idx
     }
 
     /// Returns the expected state at the given `SeekTarget`.
@@ -143,27 +124,48 @@ impl MockAnalysis<'tcx> {
     /// basic block.
     ///
     /// For example, the expected state when calling
-    /// `seek_before(Location { block: 2, statement_index: 2 })` would be `[102, 0, 1, 2, 3, 4]`.
+    /// `seek_before_primary_effect(Location { block: 2, statement_index: 2 })`
+    /// would be `[102, 0, 1, 2, 3, 4]`.
     fn expected_state_at_target(&self, target: SeekTarget) -> BitSet<usize> {
+        let block = target.block();
         let mut ret = BitSet::new_empty(self.bits_per_block(self.body));
-        ret.insert(Self::BASIC_BLOCK_OFFSET + target.block().index());
+        ret.insert(Self::BASIC_BLOCK_OFFSET + block.index());
 
-        if let Some(target_effect) = self.effect_at_target(target) {
-            for i in 0..=target_effect {
-                ret.insert(i);
+        let target = match target {
+            SeekTarget::BlockEntry { .. } => return ret,
+            SeekTarget::Before(loc) => Effect::Before.at_index(loc.statement_index),
+            SeekTarget::After(loc) => Effect::Primary.at_index(loc.statement_index),
+        };
+
+        let mut pos = if D::is_forward() {
+            Effect::Before.at_index(0)
+        } else {
+            Effect::Before.at_index(self.body[block].statements.len())
+        };
+
+        loop {
+            ret.insert(self.effect(pos));
+
+            if pos == target {
+                return ret;
             }
-        }
 
-        ret
+            if D::is_forward() {
+                pos = pos.next_in_forward_order();
+            } else {
+                pos = pos.next_in_backward_order();
+            }
+        }
     }
 }
 
-impl BottomValue for MockAnalysis<'tcx> {
+impl<D: Direction> BottomValue for MockAnalysis<'tcx, D> {
     const BOTTOM_VALUE: bool = false;
 }
 
-impl AnalysisDomain<'tcx> for MockAnalysis<'tcx> {
+impl<D: Direction> AnalysisDomain<'tcx> for MockAnalysis<'tcx, D> {
     type Idx = usize;
+    type Direction = D;
 
     const NAME: &'static str = "mock";
 
@@ -176,14 +178,14 @@ impl AnalysisDomain<'tcx> for MockAnalysis<'tcx> {
     }
 }
 
-impl Analysis<'tcx> for MockAnalysis<'tcx> {
+impl<D: Direction> Analysis<'tcx> for MockAnalysis<'tcx, D> {
     fn apply_statement_effect(
         &self,
         state: &mut BitSet<Self::Idx>,
         _statement: &mir::Statement<'tcx>,
         location: Location,
     ) {
-        let idx = self.effect_at_target(SeekTarget::After(location)).unwrap();
+        let idx = self.effect(Effect::Primary.at_index(location.statement_index));
         assert!(state.insert(idx));
     }
 
@@ -193,7 +195,7 @@ impl Analysis<'tcx> for MockAnalysis<'tcx> {
         _statement: &mir::Statement<'tcx>,
         location: Location,
     ) {
-        let idx = self.effect_at_target(SeekTarget::Before(location)).unwrap();
+        let idx = self.effect(Effect::Before.at_index(location.statement_index));
         assert!(state.insert(idx));
     }
 
@@ -203,7 +205,7 @@ impl Analysis<'tcx> for MockAnalysis<'tcx> {
         _terminator: &mir::Terminator<'tcx>,
         location: Location,
     ) {
-        let idx = self.effect_at_target(SeekTarget::After(location)).unwrap();
+        let idx = self.effect(Effect::Primary.at_index(location.statement_index));
         assert!(state.insert(idx));
     }
 
@@ -213,30 +215,26 @@ impl Analysis<'tcx> for MockAnalysis<'tcx> {
         _terminator: &mir::Terminator<'tcx>,
         location: Location,
     ) {
-        let idx = self.effect_at_target(SeekTarget::Before(location)).unwrap();
+        let idx = self.effect(Effect::Before.at_index(location.statement_index));
         assert!(state.insert(idx));
     }
 
     fn apply_call_return_effect(
         &self,
-        state: &mut BitSet<Self::Idx>,
-        block: BasicBlock,
+        _state: &mut BitSet<Self::Idx>,
+        _block: BasicBlock,
         _func: &mir::Operand<'tcx>,
         _args: &[mir::Operand<'tcx>],
         _return_place: mir::Place<'tcx>,
     ) {
-        let location = self.body.terminator_loc(block);
-        let idx = self.effect_at_target(SeekTarget::AfterAssumeCallReturns(location)).unwrap();
-        assert!(state.insert(idx));
     }
 }
 
 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
 enum SeekTarget {
-    BlockStart(BasicBlock),
+    BlockEntry(BasicBlock),
     Before(Location),
     After(Location),
-    AfterAssumeCallReturns(Location),
 }
 
 impl SeekTarget {
@@ -244,59 +242,35 @@ impl SeekTarget {
         use SeekTarget::*;
 
         match *self {
-            BlockStart(block) => block,
-            Before(loc) | After(loc) | AfterAssumeCallReturns(loc) => loc.block,
+            BlockEntry(block) => block,
+            Before(loc) | After(loc) => loc.block,
         }
     }
 
     /// An iterator over all possible `SeekTarget`s in a given block in order, starting with
-    /// `BlockStart`.
-    ///
-    /// This includes both `After` and `AfterAssumeCallReturns` for every `Location`.
+    /// `BlockEntry`.
     fn iter_in_block(body: &mir::Body<'_>, block: BasicBlock) -> impl Iterator<Item = Self> {
         let statements_and_terminator = (0..=body[block].statements.len())
-            .flat_map(|i| (0..3).map(move |j| (i, j)))
+            .flat_map(|i| (0..2).map(move |j| (i, j)))
             .map(move |(i, kind)| {
                 let loc = Location { block, statement_index: i };
                 match kind {
                     0 => SeekTarget::Before(loc),
                     1 => SeekTarget::After(loc),
-                    2 => SeekTarget::AfterAssumeCallReturns(loc),
                     _ => unreachable!(),
                 }
             });
 
-        std::iter::once(SeekTarget::BlockStart(block)).chain(statements_and_terminator)
+        std::iter::once(SeekTarget::BlockEntry(block)).chain(statements_and_terminator)
     }
 }
 
-#[test]
-fn cursor_seek() {
-    let body = mock_body();
-    let body = &body;
-    let analysis = MockAnalysis { body };
+fn test_cursor<D: Direction>(analysis: MockAnalysis<'tcx, D>) {
+    let body = analysis.body;
 
     let mut cursor =
         Results { entry_sets: analysis.mock_entry_sets(), analysis }.into_results_cursor(body);
 
-    // Sanity check: the mock call return effect is unique and actually being applied.
-    let call_terminator_loc = Location { block: BasicBlock::from_usize(2), statement_index: 2 };
-    assert!(is_call_terminator_non_diverging(body, call_terminator_loc));
-
-    let call_return_effect = cursor
-        .analysis()
-        .effect_at_target(SeekTarget::AfterAssumeCallReturns(call_terminator_loc))
-        .unwrap();
-    assert_ne!(
-        call_return_effect,
-        cursor.analysis().effect_at_target(SeekTarget::After(call_terminator_loc)).unwrap()
-    );
-
-    cursor.seek_after(call_terminator_loc);
-    assert!(!cursor.get().contains(call_return_effect));
-    cursor.seek_after_assume_success(call_terminator_loc);
-    assert!(cursor.get().contains(call_return_effect));
-
     let every_target = || {
         body.basic_blocks()
             .iter_enumerated()
@@ -307,10 +281,9 @@ fn cursor_seek() {
         use SeekTarget::*;
 
         match targ {
-            BlockStart(block) => cursor.seek_to_block_start(block),
-            Before(loc) => cursor.seek_before(loc),
-            After(loc) => cursor.seek_after(loc),
-            AfterAssumeCallReturns(loc) => cursor.seek_after_assume_success(loc),
+            BlockEntry(block) => cursor.seek_to_block_entry(block),
+            Before(loc) => cursor.seek_before_primary_effect(loc),
+            After(loc) => cursor.seek_after_primary_effect(loc),
         }
 
         assert_eq!(cursor.get(), &cursor.analysis().expected_state_at_target(targ));
@@ -325,8 +298,26 @@ fn cursor_seek() {
         seek_to_target(from);
 
         for to in every_target() {
+            dbg!(from);
+            dbg!(to);
             seek_to_target(to);
             seek_to_target(from);
         }
     }
 }
+
+#[test]
+fn backward_cursor() {
+    let body = mock_body();
+    let body = &body;
+    let analysis = MockAnalysis { body, dir: PhantomData::<Backward> };
+    test_cursor(analysis)
+}
+
+#[test]
+fn forward_cursor() {
+    let body = mock_body();
+    let body = &body;
+    let analysis = MockAnalysis { body, dir: PhantomData::<Forward> };
+    test_cursor(analysis)
+}
diff --git a/src/librustc_mir/dataflow/framework/visitor.rs b/src/librustc_mir/dataflow/framework/visitor.rs
index 9561b68398d..0df9322e7fe 100644
--- a/src/librustc_mir/dataflow/framework/visitor.rs
+++ b/src/librustc_mir/dataflow/framework/visitor.rs
@@ -1,50 +1,41 @@
 use rustc_index::bit_set::BitSet;
 use rustc_middle::mir::{self, BasicBlock, Location};
 
-use super::{Analysis, Results};
+use super::{Analysis, Direction, Results};
 use crate::dataflow::impls::{borrows::Borrows, EverInitializedPlaces, MaybeUninitializedPlaces};
 
 /// Calls the corresponding method in `ResultsVisitor` for every location in a `mir::Body` with the
 /// dataflow state at that location.
-pub fn visit_results<F>(
+pub fn visit_results<F, V>(
     body: &'mir mir::Body<'tcx>,
     blocks: impl IntoIterator<Item = BasicBlock>,
-    results: &impl ResultsVisitable<'tcx, FlowState = F>,
+    results: &V,
     vis: &mut impl ResultsVisitor<'mir, 'tcx, FlowState = F>,
-) {
+) where
+    V: ResultsVisitable<'tcx, FlowState = F>,
+{
     let mut state = results.new_flow_state(body);
 
     for block in blocks {
         let block_data = &body[block];
-        results.reset_to_block_start(&mut state, block);
-
-        for (statement_index, stmt) in block_data.statements.iter().enumerate() {
-            let loc = Location { block, statement_index };
-
-            results.reconstruct_before_statement_effect(&mut state, stmt, loc);
-            vis.visit_statement(&state, stmt, loc);
-
-            results.reconstruct_statement_effect(&mut state, stmt, loc);
-            vis.visit_statement_exit(&state, stmt, loc);
-        }
-
-        let loc = body.terminator_loc(block);
-        let term = block_data.terminator();
-
-        results.reconstruct_before_terminator_effect(&mut state, term, loc);
-        vis.visit_terminator(&state, term, loc);
-
-        results.reconstruct_terminator_effect(&mut state, term, loc);
-        vis.visit_terminator_exit(&state, term, loc);
+        V::Direction::visit_results_in_block(&mut state, block, block_data, results, vis);
     }
 }
 
 pub trait ResultsVisitor<'mir, 'tcx> {
     type FlowState;
 
+    fn visit_block_start(
+        &mut self,
+        _state: &Self::FlowState,
+        _block_data: &'mir mir::BasicBlockData<'tcx>,
+        _block: BasicBlock,
+    ) {
+    }
+
     /// Called with the `before_statement_effect` of the given statement applied to `state` but not
     /// its `statement_effect`.
-    fn visit_statement(
+    fn visit_statement_before_primary_effect(
         &mut self,
         _state: &Self::FlowState,
         _statement: &'mir mir::Statement<'tcx>,
@@ -54,7 +45,7 @@ pub trait ResultsVisitor<'mir, 'tcx> {
 
     /// Called with both the `before_statement_effect` and the `statement_effect` of the given
     /// statement applied to `state`.
-    fn visit_statement_exit(
+    fn visit_statement_after_primary_effect(
         &mut self,
         _state: &Self::FlowState,
         _statement: &'mir mir::Statement<'tcx>,
@@ -64,7 +55,7 @@ pub trait ResultsVisitor<'mir, 'tcx> {
 
     /// Called with the `before_terminator_effect` of the given terminator applied to `state` but not
     /// its `terminator_effect`.
-    fn visit_terminator(
+    fn visit_terminator_before_primary_effect(
         &mut self,
         _state: &Self::FlowState,
         _terminator: &'mir mir::Terminator<'tcx>,
@@ -76,13 +67,21 @@ pub trait ResultsVisitor<'mir, 'tcx> {
     /// terminator applied to `state`.
     ///
     /// The `call_return_effect` (if one exists) will *not* be applied to `state`.
-    fn visit_terminator_exit(
+    fn visit_terminator_after_primary_effect(
         &mut self,
         _state: &Self::FlowState,
         _terminator: &'mir mir::Terminator<'tcx>,
         _location: Location,
     ) {
     }
+
+    fn visit_block_end(
+        &mut self,
+        _state: &Self::FlowState,
+        _block_data: &'mir mir::BasicBlockData<'tcx>,
+        _block: BasicBlock,
+    ) {
+    }
 }
 
 /// Things that can be visited by a `ResultsVisitor`.
@@ -90,15 +89,16 @@ pub trait ResultsVisitor<'mir, 'tcx> {
 /// This trait exists so that we can visit the results of multiple dataflow analyses simultaneously.
 /// DO NOT IMPLEMENT MANUALLY. Instead, use the `impl_visitable` macro below.
 pub trait ResultsVisitable<'tcx> {
+    type Direction: Direction;
     type FlowState;
 
     /// Creates an empty `FlowState` to hold the transient state for these dataflow results.
     ///
-    /// The value of the newly created `FlowState` will be overwritten by `reset_to_block_start`
+    /// The value of the newly created `FlowState` will be overwritten by `reset_to_block_entry`
     /// before it can be observed by a `ResultsVisitor`.
     fn new_flow_state(&self, body: &mir::Body<'tcx>) -> Self::FlowState;
 
-    fn reset_to_block_start(&self, state: &mut Self::FlowState, block: BasicBlock);
+    fn reset_to_block_entry(&self, state: &mut Self::FlowState, block: BasicBlock);
 
     fn reconstruct_before_statement_effect(
         &self,
@@ -135,11 +135,13 @@ where
 {
     type FlowState = BitSet<A::Idx>;
 
+    type Direction = A::Direction;
+
     fn new_flow_state(&self, body: &mir::Body<'tcx>) -> Self::FlowState {
         BitSet::new_empty(self.analysis.bits_per_block(body))
     }
 
-    fn reset_to_block_start(&self, state: &mut Self::FlowState, block: BasicBlock) {
+    fn reset_to_block_entry(&self, state: &mut Self::FlowState, block: BasicBlock) {
         state.overwrite(&self.entry_set_for_block(block));
     }
 
@@ -204,10 +206,11 @@ macro_rules! impl_visitable {
     ( $(
         $T:ident { $( $field:ident : $A:ident ),* $(,)? }
     )* ) => { $(
-        impl<'tcx, $($A),*> ResultsVisitable<'tcx> for $T<$( Results<'tcx, $A> ),*>
+        impl<'tcx, $($A),*, D: Direction> ResultsVisitable<'tcx> for $T<$( Results<'tcx, $A> ),*>
         where
-            $( $A: Analysis<'tcx>, )*
+            $( $A: Analysis<'tcx, Direction = D>, )*
         {
+            type Direction = D;
             type FlowState = $T<$( BitSet<$A::Idx> ),*>;
 
             fn new_flow_state(&self, body: &mir::Body<'tcx>) -> Self::FlowState {
@@ -216,12 +219,12 @@ macro_rules! impl_visitable {
                 }
             }
 
-            fn reset_to_block_start(
+            fn reset_to_block_entry(
                 &self,
                 state: &mut Self::FlowState,
                 block: BasicBlock,
             ) {
-                $( state.$field.overwrite(&self.$field.entry_sets[block]); )*
+                $( state.$field.overwrite(&self.$field.entry_set_for_block(block)); )*
             }
 
             fn reconstruct_before_statement_effect(
diff --git a/src/librustc_mir/dataflow/impls/liveness.rs b/src/librustc_mir/dataflow/impls/liveness.rs
new file mode 100644
index 00000000000..5e9bec89ac0
--- /dev/null
+++ b/src/librustc_mir/dataflow/impls/liveness.rs
@@ -0,0 +1,137 @@
+use rustc_index::bit_set::BitSet;
+use rustc_middle::mir::visit::{MutatingUseContext, NonMutatingUseContext, PlaceContext, Visitor};
+use rustc_middle::mir::{self, Local, Location};
+
+use crate::dataflow::{AnalysisDomain, Backward, BottomValue, GenKill, GenKillAnalysis};
+
+/// A [live-variable dataflow analysis][liveness].
+///
+/// [liveness]: https://en.wikipedia.org/wiki/Live_variable_analysis
+pub struct MaybeLiveLocals;
+
+impl MaybeLiveLocals {
+    fn transfer_function<T>(&self, trans: &'a mut T) -> TransferFunction<'a, T> {
+        TransferFunction(trans)
+    }
+}
+
+impl BottomValue for MaybeLiveLocals {
+    // bottom = not live
+    const BOTTOM_VALUE: bool = false;
+}
+
+impl AnalysisDomain<'tcx> for MaybeLiveLocals {
+    type Idx = Local;
+    type Direction = Backward;
+
+    const NAME: &'static str = "liveness";
+
+    fn bits_per_block(&self, body: &mir::Body<'tcx>) -> usize {
+        body.local_decls.len()
+    }
+
+    fn initialize_start_block(&self, _: &mir::Body<'tcx>, _: &mut BitSet<Self::Idx>) {
+        // No variables are live until we observe a use
+    }
+}
+
+impl GenKillAnalysis<'tcx> for MaybeLiveLocals {
+    fn statement_effect(
+        &self,
+        trans: &mut impl GenKill<Self::Idx>,
+        statement: &mir::Statement<'tcx>,
+        location: Location,
+    ) {
+        self.transfer_function(trans).visit_statement(statement, location);
+    }
+
+    fn terminator_effect(
+        &self,
+        trans: &mut impl GenKill<Self::Idx>,
+        terminator: &mir::Terminator<'tcx>,
+        location: Location,
+    ) {
+        self.transfer_function(trans).visit_terminator(terminator, location);
+    }
+
+    fn call_return_effect(
+        &self,
+        trans: &mut impl GenKill<Self::Idx>,
+        _block: mir::BasicBlock,
+        _func: &mir::Operand<'tcx>,
+        _args: &[mir::Operand<'tcx>],
+        dest_place: mir::Place<'tcx>,
+    ) {
+        if let Some(local) = dest_place.as_local() {
+            trans.kill(local);
+        }
+    }
+
+    fn yield_resume_effect(
+        &self,
+        trans: &mut impl GenKill<Self::Idx>,
+        _resume_block: mir::BasicBlock,
+        resume_place: mir::Place<'tcx>,
+    ) {
+        if let Some(local) = resume_place.as_local() {
+            trans.kill(local);
+        }
+    }
+}
+
+struct TransferFunction<'a, T>(&'a mut T);
+
+impl<'tcx, T> Visitor<'tcx> for TransferFunction<'_, T>
+where
+    T: GenKill<Local>,
+{
+    fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) {
+        match DefUse::for_place(context) {
+            Some(DefUse::Def) => self.0.kill(local),
+            Some(DefUse::Use) => self.0.gen(local),
+            _ => {}
+        }
+    }
+}
+
+#[derive(Eq, PartialEq, Clone)]
+enum DefUse {
+    Def,
+    Use,
+}
+
+impl DefUse {
+    fn for_place(context: PlaceContext) -> Option<DefUse> {
+        match context {
+            PlaceContext::NonUse(_) => None,
+
+            PlaceContext::MutatingUse(MutatingUseContext::Store) => Some(DefUse::Def),
+
+            // `MutatingUseContext::Call` and `MutatingUseContext::Yield` indicate that this is the
+            // destination place for a `Call` return or `Yield` resume respectively. Since this is
+            // only a `Def` when the function returns succesfully, we handle this case separately
+            // in `call_return_effect` above.
+            PlaceContext::MutatingUse(MutatingUseContext::Call | MutatingUseContext::Yield) => None,
+
+            // All other contexts are uses...
+            PlaceContext::MutatingUse(
+                MutatingUseContext::AddressOf
+                | MutatingUseContext::AsmOutput
+                | MutatingUseContext::Borrow
+                | MutatingUseContext::Drop
+                | MutatingUseContext::Projection
+                | MutatingUseContext::Retag,
+            )
+            | PlaceContext::NonMutatingUse(
+                NonMutatingUseContext::AddressOf
+                | NonMutatingUseContext::Copy
+                | NonMutatingUseContext::Inspect
+                | NonMutatingUseContext::Move
+                | NonMutatingUseContext::Projection
+                | NonMutatingUseContext::ShallowBorrow
+                | NonMutatingUseContext::SharedBorrow
+                | NonMutatingUseContext::UniqueBorrow,
+            ) => Some(DefUse::Use),
+        }
+    }
+}
diff --git a/src/librustc_mir/dataflow/impls/mod.rs b/src/librustc_mir/dataflow/impls/mod.rs
index b5f1a2d4eb9..222ae137d96 100644
--- a/src/librustc_mir/dataflow/impls/mod.rs
+++ b/src/librustc_mir/dataflow/impls/mod.rs
@@ -21,9 +21,11 @@ use super::on_lookup_result_bits;
 use crate::dataflow::drop_flag_effects;
 
 mod borrowed_locals;
+mod liveness;
 mod storage_liveness;
 
 pub use self::borrowed_locals::*;
+pub use self::liveness::MaybeLiveLocals;
 pub use self::storage_liveness::*;
 
 pub(super) mod borrows;
diff --git a/src/librustc_mir/dataflow/impls/storage_liveness.rs b/src/librustc_mir/dataflow/impls/storage_liveness.rs
index 5d130213e1f..4c784c3f1a1 100644
--- a/src/librustc_mir/dataflow/impls/storage_liveness.rs
+++ b/src/librustc_mir/dataflow/impls/storage_liveness.rs
@@ -250,7 +250,7 @@ impl<'mir, 'tcx> dataflow::GenKillAnalysis<'tcx> for MaybeRequiresStorage<'mir,
 
     fn yield_resume_effect(
         &self,
-        trans: &mut BitSet<Self::Idx>,
+        trans: &mut impl GenKill<Self::Idx>,
         _resume_block: BasicBlock,
         resume_place: mir::Place<'tcx>,
     ) {
@@ -283,7 +283,7 @@ where
     fn visit_local(&mut self, local: &Local, context: PlaceContext, loc: Location) {
         if PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) == context {
             let mut borrowed_locals = self.borrowed_locals.borrow_mut();
-            borrowed_locals.seek_before(loc);
+            borrowed_locals.seek_before_primary_effect(loc);
             if !borrowed_locals.contains(*local) {
                 self.trans.kill(*local);
             }
diff --git a/src/librustc_mir/dataflow/mod.rs b/src/librustc_mir/dataflow/mod.rs
index d244587fcc8..a05b4a5385d 100644
--- a/src/librustc_mir/dataflow/mod.rs
+++ b/src/librustc_mir/dataflow/mod.rs
@@ -4,13 +4,14 @@ use rustc_span::symbol::{sym, Symbol};
 
 pub(crate) use self::drop_flag_effects::*;
 pub use self::framework::{
-    visit_results, Analysis, AnalysisDomain, BorrowckFlowState, BorrowckResults, BottomValue,
-    Engine, GenKill, GenKillAnalysis, Results, ResultsCursor, ResultsRefCursor, ResultsVisitor,
+    visit_results, Analysis, AnalysisDomain, Backward, BorrowckFlowState, BorrowckResults,
+    BottomValue, Engine, Forward, GenKill, GenKillAnalysis, Results, ResultsCursor,
+    ResultsRefCursor, ResultsVisitor,
 };
 pub use self::impls::{
     borrows::Borrows, DefinitelyInitializedPlaces, EverInitializedPlaces, MaybeBorrowedLocals,
-    MaybeInitializedPlaces, MaybeMutBorrowedLocals, MaybeRequiresStorage, MaybeStorageLive,
-    MaybeUninitializedPlaces,
+    MaybeInitializedPlaces, MaybeLiveLocals, MaybeMutBorrowedLocals, MaybeRequiresStorage,
+    MaybeStorageLive, MaybeUninitializedPlaces,
 };
 
 use self::move_paths::MoveData;
diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs
index ae7bbe9f36a..09f8588cee2 100644
--- a/src/librustc_mir/lib.rs
+++ b/src/librustc_mir/lib.rs
@@ -9,8 +9,9 @@ Rust MIR: a lowered representation of Rust.
 #![feature(bool_to_option)]
 #![feature(box_patterns)]
 #![feature(box_syntax)]
-#![feature(const_if_match)]
 #![feature(const_fn)]
+#![feature(const_if_match)]
+#![feature(const_loop)]
 #![feature(const_panic)]
 #![feature(crate_visibility_modifier)]
 #![feature(decl_macro)]
@@ -22,6 +23,7 @@ Rust MIR: a lowered representation of Rust.
 #![feature(trusted_len)]
 #![feature(try_blocks)]
 #![feature(associated_type_bounds)]
+#![feature(associated_type_defaults)]
 #![feature(range_is_empty)]
 #![feature(stmt_expr_attributes)]
 #![feature(trait_alias)]
diff --git a/src/librustc_mir/transform/check_consts/validation.rs b/src/librustc_mir/transform/check_consts/validation.rs
index 78cb60ea484..691903c9069 100644
--- a/src/librustc_mir/transform/check_consts/validation.rs
+++ b/src/librustc_mir/transform/check_consts/validation.rs
@@ -61,7 +61,7 @@ impl Qualifs<'mir, 'tcx> {
                 .into_results_cursor(&body)
         });
 
-        indirectly_mutable.seek_before(location);
+        indirectly_mutable.seek_before_primary_effect(location);
         indirectly_mutable.get().contains(local)
     }
 
@@ -88,7 +88,7 @@ impl Qualifs<'mir, 'tcx> {
                 .into_results_cursor(&body)
         });
 
-        needs_drop.seek_before(location);
+        needs_drop.seek_before_primary_effect(location);
         needs_drop.get().contains(local) || self.indirectly_mutable(ccx, local, location)
     }
 
@@ -115,7 +115,7 @@ impl Qualifs<'mir, 'tcx> {
                 .into_results_cursor(&body)
         });
 
-        has_mut_interior.seek_before(location);
+        has_mut_interior.seek_before_primary_effect(location);
         has_mut_interior.get().contains(local) || self.indirectly_mutable(ccx, local, location)
     }
 
@@ -161,7 +161,7 @@ impl Qualifs<'mir, 'tcx> {
                     .iterate_to_fixpoint()
                     .into_results_cursor(&ccx.body);
 
-                cursor.seek_after(return_loc);
+                cursor.seek_after_primary_effect(return_loc);
                 cursor.contains(RETURN_PLACE)
             }
         };
diff --git a/src/librustc_mir/transform/elaborate_drops.rs b/src/librustc_mir/transform/elaborate_drops.rs
index 6074619dd15..a1becf062ee 100644
--- a/src/librustc_mir/transform/elaborate_drops.rs
+++ b/src/librustc_mir/transform/elaborate_drops.rs
@@ -101,7 +101,7 @@ fn find_dead_unwinds<'tcx>(
             }
         };
 
-        flow_inits.seek_before(body.terminator_loc(bb));
+        flow_inits.seek_before_primary_effect(body.terminator_loc(bb));
         debug!(
             "find_dead_unwinds @ {:?}: path({:?})={:?}; init_data={:?}",
             bb,
@@ -131,8 +131,8 @@ struct InitializationData<'mir, 'tcx> {
 
 impl InitializationData<'_, '_> {
     fn seek_before(&mut self, loc: Location) {
-        self.inits.seek_before(loc);
-        self.uninits.seek_before(loc);
+        self.inits.seek_before_primary_effect(loc);
+        self.uninits.seek_before_primary_effect(loc);
     }
 
     fn maybe_live_dead(&self, path: MovePathIndex) -> (bool, bool) {
diff --git a/src/librustc_mir/transform/generator.rs b/src/librustc_mir/transform/generator.rs
index 00caa06a6c0..25804c2a62c 100644
--- a/src/librustc_mir/transform/generator.rs
+++ b/src/librustc_mir/transform/generator.rs
@@ -50,12 +50,13 @@
 //! Otherwise it drops all the values in scope at the last suspension point.
 
 use crate::dataflow::{self, Analysis};
-use crate::dataflow::{MaybeBorrowedLocals, MaybeRequiresStorage, MaybeStorageLive};
+use crate::dataflow::{
+    MaybeBorrowedLocals, MaybeLiveLocals, MaybeRequiresStorage, MaybeStorageLive,
+};
 use crate::transform::no_landing_pads::no_landing_pads;
 use crate::transform::simplify;
 use crate::transform::{MirPass, MirSource};
 use crate::util::dump_mir;
-use crate::util::liveness;
 use crate::util::storage;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_hir as hir;
@@ -195,7 +196,7 @@ struct SuspensionPoint<'tcx> {
     /// Which block to jump to if the generator is dropped in this state.
     drop: Option<BasicBlock>,
     /// Set of locals that have live storage while at this suspension point.
-    storage_liveness: liveness::LiveVarSet,
+    storage_liveness: BitSet<Local>,
 }
 
 struct TransformVisitor<'tcx> {
@@ -211,7 +212,7 @@ struct TransformVisitor<'tcx> {
     remap: FxHashMap<Local, (Ty<'tcx>, VariantIdx, usize)>,
 
     // A map from a suspension point in a block to the locals which have live storage at that point
-    storage_liveness: IndexVec<BasicBlock, Option<liveness::LiveVarSet>>,
+    storage_liveness: IndexVec<BasicBlock, Option<BitSet<Local>>>,
 
     // A list of suspension points, generated during the transform
     suspension_points: Vec<SuspensionPoint<'tcx>>,
@@ -418,7 +419,7 @@ struct LivenessInfo {
     /// GeneratorSavedLocal is indexed in terms of the elements in this set;
     /// i.e. GeneratorSavedLocal::new(1) corresponds to the second local
     /// included in this set.
-    live_locals: liveness::LiveVarSet,
+    live_locals: BitSet<Local>,
 
     /// The set of saved locals live at each suspension point.
     live_locals_at_suspension_points: Vec<BitSet<GeneratorSavedLocal>>,
@@ -430,7 +431,7 @@ struct LivenessInfo {
 
     /// For every suspending block, the locals which are storage-live across
     /// that suspension point.
-    storage_liveness: IndexVec<BasicBlock, Option<liveness::LiveVarSet>>,
+    storage_liveness: IndexVec<BasicBlock, Option<BitSet<Local>>>,
 }
 
 fn locals_live_across_suspend_points(
@@ -467,17 +468,22 @@ fn locals_live_across_suspend_points(
         dataflow::ResultsCursor::new(body_ref, &requires_storage_results);
 
     // Calculate the liveness of MIR locals ignoring borrows.
-    let mut live_locals = liveness::LiveVarSet::new_empty(body.local_decls.len());
-    let mut liveness = liveness::liveness_of_locals(body);
-    liveness::dump_mir(tcx, "generator_liveness", source, body_ref, &liveness);
+    let mut liveness = MaybeLiveLocals
+        .into_engine(tcx, body_ref, def_id)
+        .iterate_to_fixpoint()
+        .into_results_cursor(body_ref);
 
     let mut storage_liveness_map = IndexVec::from_elem(None, body.basic_blocks());
     let mut live_locals_at_suspension_points = Vec::new();
+    let mut live_locals_at_any_suspension_point = BitSet::new_empty(body.local_decls.len());
 
     for (block, data) in body.basic_blocks().iter_enumerated() {
         if let TerminatorKind::Yield { .. } = data.terminator().kind {
             let loc = Location { block, statement_index: data.statements.len() };
 
+            liveness.seek_to_block_end(block);
+            let mut live_locals = liveness.get().clone();
+
             if !movable {
                 // The `liveness` variable contains the liveness of MIR locals ignoring borrows.
                 // This is correct for movable generators since borrows cannot live across
@@ -489,59 +495,51 @@ fn locals_live_across_suspend_points(
                 // If a borrow is converted to a raw reference, we must also assume that it lives
                 // forever. Note that the final liveness is still bounded by the storage liveness
                 // of the local, which happens using the `intersect` operation below.
-                borrowed_locals_cursor.seek_before(loc);
-                liveness.outs[block].union(borrowed_locals_cursor.get());
+                borrowed_locals_cursor.seek_before_primary_effect(loc);
+                live_locals.union(borrowed_locals_cursor.get());
             }
 
-            storage_live.seek_before(loc);
-            let mut storage_liveness = storage_live.get().clone();
-
-            // Later passes handle the generator's `self` argument separately.
-            storage_liveness.remove(SELF_ARG);
-
             // Store the storage liveness for later use so we can restore the state
             // after a suspension point
-            storage_liveness_map[block] = Some(storage_liveness);
-
-            requires_storage_cursor.seek_before(loc);
-            let storage_required = requires_storage_cursor.get().clone();
+            storage_live.seek_before_primary_effect(loc);
+            storage_liveness_map[block] = Some(storage_live.get().clone());
 
             // Locals live are live at this point only if they are used across
             // suspension points (the `liveness` variable)
             // and their storage is required (the `storage_required` variable)
-            let mut live_locals_here = storage_required;
-            live_locals_here.intersect(&liveness.outs[block]);
+            requires_storage_cursor.seek_before_primary_effect(loc);
+            live_locals.intersect(requires_storage_cursor.get());
 
             // The generator argument is ignored.
-            live_locals_here.remove(SELF_ARG);
+            live_locals.remove(SELF_ARG);
 
-            debug!("loc = {:?}, live_locals_here = {:?}", loc, live_locals_here);
+            debug!("loc = {:?}, live_locals = {:?}", loc, live_locals);
 
             // Add the locals live at this suspension point to the set of locals which live across
             // any suspension points
-            live_locals.union(&live_locals_here);
+            live_locals_at_any_suspension_point.union(&live_locals);
 
-            live_locals_at_suspension_points.push(live_locals_here);
+            live_locals_at_suspension_points.push(live_locals);
         }
     }
-    debug!("live_locals = {:?}", live_locals);
+    debug!("live_locals_anywhere = {:?}", live_locals_at_any_suspension_point);
 
     // Renumber our liveness_map bitsets to include only the locals we are
     // saving.
     let live_locals_at_suspension_points = live_locals_at_suspension_points
         .iter()
-        .map(|live_here| renumber_bitset(&live_here, &live_locals))
+        .map(|live_here| renumber_bitset(&live_here, &live_locals_at_any_suspension_point))
         .collect();
 
     let storage_conflicts = compute_storage_conflicts(
         body_ref,
-        &live_locals,
+        &live_locals_at_any_suspension_point,
         always_live_locals.clone(),
         requires_storage_results,
     );
 
     LivenessInfo {
-        live_locals,
+        live_locals: live_locals_at_any_suspension_point,
         live_locals_at_suspension_points,
         storage_conflicts,
         storage_liveness: storage_liveness_map,
@@ -555,7 +553,7 @@ fn locals_live_across_suspend_points(
 /// `[0, 1, 2]`. Thus, if `input = [3, 5]` we would return `[1, 2]`.
 fn renumber_bitset(
     input: &BitSet<Local>,
-    stored_locals: &liveness::LiveVarSet,
+    stored_locals: &BitSet<Local>,
 ) -> BitSet<GeneratorSavedLocal> {
     assert!(stored_locals.superset(&input), "{:?} not a superset of {:?}", stored_locals, input);
     let mut out = BitSet::new_empty(stored_locals.count());
@@ -575,7 +573,7 @@ fn renumber_bitset(
 /// computation; see `GeneratorLayout` for more.
 fn compute_storage_conflicts(
     body: &'mir Body<'tcx>,
-    stored_locals: &liveness::LiveVarSet,
+    stored_locals: &BitSet<Local>,
     always_live_locals: storage::AlwaysLiveLocals,
     requires_storage: dataflow::Results<'tcx, MaybeRequiresStorage<'mir, 'tcx>>,
 ) -> BitMatrix<GeneratorSavedLocal, GeneratorSavedLocal> {
@@ -630,7 +628,7 @@ fn compute_storage_conflicts(
 
 struct StorageConflictVisitor<'mir, 'tcx, 's> {
     body: &'mir Body<'tcx>,
-    stored_locals: &'s liveness::LiveVarSet,
+    stored_locals: &'s BitSet<Local>,
     // FIXME(tmandry): Consider using sparse bitsets here once we have good
     // benchmarks for generators.
     local_conflicts: BitMatrix<Local, Local>,
@@ -639,7 +637,7 @@ struct StorageConflictVisitor<'mir, 'tcx, 's> {
 impl dataflow::ResultsVisitor<'mir, 'tcx> for StorageConflictVisitor<'mir, 'tcx, '_> {
     type FlowState = BitSet<Local>;
 
-    fn visit_statement(
+    fn visit_statement_before_primary_effect(
         &mut self,
         state: &Self::FlowState,
         _statement: &'mir Statement<'tcx>,
@@ -648,7 +646,7 @@ impl dataflow::ResultsVisitor<'mir, 'tcx> for StorageConflictVisitor<'mir, 'tcx,
         self.apply_state(state, loc);
     }
 
-    fn visit_terminator(
+    fn visit_terminator_before_primary_effect(
         &mut self,
         state: &Self::FlowState,
         _terminator: &'mir Terminator<'tcx>,
@@ -689,7 +687,7 @@ fn compute_layout<'tcx>(
 ) -> (
     FxHashMap<Local, (Ty<'tcx>, VariantIdx, usize)>,
     GeneratorLayout<'tcx>,
-    IndexVec<BasicBlock, Option<liveness::LiveVarSet>>,
+    IndexVec<BasicBlock, Option<BitSet<Local>>>,
 ) {
     // Use a liveness analysis to compute locals which are live across a suspension point
     let LivenessInfo {
diff --git a/src/librustc_mir/transform/rustc_peek.rs b/src/librustc_mir/transform/rustc_peek.rs
index b9302d58cd5..43ddc0c914c 100644
--- a/src/librustc_mir/transform/rustc_peek.rs
+++ b/src/librustc_mir/transform/rustc_peek.rs
@@ -15,7 +15,7 @@ use crate::dataflow::MaybeMutBorrowedLocals;
 use crate::dataflow::MoveDataParamEnv;
 use crate::dataflow::{Analysis, Results, ResultsCursor};
 use crate::dataflow::{
-    DefinitelyInitializedPlaces, MaybeInitializedPlaces, MaybeUninitializedPlaces,
+    DefinitelyInitializedPlaces, MaybeInitializedPlaces, MaybeLiveLocals, MaybeUninitializedPlaces,
 };
 
 pub struct SanityCheck;
@@ -36,31 +36,45 @@ impl<'tcx> MirPass<'tcx> for SanityCheck {
         let move_data = MoveData::gather_moves(body, tcx, param_env).unwrap();
         let mdpe = MoveDataParamEnv { move_data, param_env };
 
-        let flow_inits = MaybeInitializedPlaces::new(tcx, body, &mdpe)
-            .into_engine(tcx, body, def_id)
-            .iterate_to_fixpoint();
-        let flow_uninits = MaybeUninitializedPlaces::new(tcx, body, &mdpe)
-            .into_engine(tcx, body, def_id)
-            .iterate_to_fixpoint();
-        let flow_def_inits = DefinitelyInitializedPlaces::new(tcx, body, &mdpe)
-            .into_engine(tcx, body, def_id)
-            .iterate_to_fixpoint();
-        let flow_mut_borrowed = MaybeMutBorrowedLocals::mut_borrows_only(tcx, body, param_env)
-            .into_engine(tcx, body, def_id)
-            .iterate_to_fixpoint();
-
         if has_rustc_mir_with(&attributes, sym::rustc_peek_maybe_init).is_some() {
+            let flow_inits = MaybeInitializedPlaces::new(tcx, body, &mdpe)
+                .into_engine(tcx, body, def_id)
+                .iterate_to_fixpoint();
+
             sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_inits);
         }
+
         if has_rustc_mir_with(&attributes, sym::rustc_peek_maybe_uninit).is_some() {
+            let flow_uninits = MaybeUninitializedPlaces::new(tcx, body, &mdpe)
+                .into_engine(tcx, body, def_id)
+                .iterate_to_fixpoint();
+
             sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_uninits);
         }
+
         if has_rustc_mir_with(&attributes, sym::rustc_peek_definite_init).is_some() {
+            let flow_def_inits = DefinitelyInitializedPlaces::new(tcx, body, &mdpe)
+                .into_engine(tcx, body, def_id)
+                .iterate_to_fixpoint();
+
             sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_def_inits);
         }
+
         if has_rustc_mir_with(&attributes, sym::rustc_peek_indirectly_mutable).is_some() {
+            let flow_mut_borrowed = MaybeMutBorrowedLocals::mut_borrows_only(tcx, body, param_env)
+                .into_engine(tcx, body, def_id)
+                .iterate_to_fixpoint();
+
             sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_mut_borrowed);
         }
+
+        if has_rustc_mir_with(&attributes, sym::rustc_peek_liveness).is_some() {
+            let flow_liveness =
+                MaybeLiveLocals.into_engine(tcx, body, def_id).iterate_to_fixpoint();
+
+            sanity_check_via_rustc_peek(tcx, body, def_id, &attributes, &flow_liveness);
+        }
+
         if has_rustc_mir_with(&attributes, sym::stop_after_dataflow).is_some() {
             tcx.sess.fatal("stop_after_dataflow ended compilation");
         }
@@ -126,7 +140,7 @@ pub fn sanity_check_via_rustc_peek<'tcx, A>(
                 mir::Rvalue::Use(mir::Operand::Move(place) | mir::Operand::Copy(place)),
             ) => {
                 let loc = Location { block: bb, statement_index };
-                cursor.seek_before(loc);
+                cursor.seek_before_primary_effect(loc);
                 let state = cursor.get();
                 results.analysis.peek_at(tcx, *place, state, call);
             }
@@ -286,3 +300,25 @@ impl<'tcx> RustcPeekAt<'tcx> for MaybeMutBorrowedLocals<'_, 'tcx> {
         }
     }
 }
+
+impl<'tcx> RustcPeekAt<'tcx> for MaybeLiveLocals {
+    fn peek_at(
+        &self,
+        tcx: TyCtxt<'tcx>,
+        place: mir::Place<'tcx>,
+        flow_state: &BitSet<Local>,
+        call: PeekCall,
+    ) {
+        warn!("peek_at: place={:?}", place);
+        let local = if let Some(l) = place.as_local() {
+            l
+        } else {
+            tcx.sess.span_err(call.span, "rustc_peek: argument was not a local");
+            return;
+        };
+
+        if !flow_state.contains(local) {
+            tcx.sess.span_err(call.span, "rustc_peek: bit not set");
+        }
+    }
+}
diff --git a/src/librustc_mir/util/liveness.rs b/src/librustc_mir/util/liveness.rs
index c6eefcc5eca..c261219cc73 100644
--- a/src/librustc_mir/util/liveness.rs
+++ b/src/librustc_mir/util/liveness.rs
@@ -133,6 +133,7 @@ pub fn categorize(context: PlaceContext) -> Option<DefUse> {
         // the def in call only to the input from the success
         // path and not the unwind path. -nmatsakis
         PlaceContext::MutatingUse(MutatingUseContext::Call) |
+        PlaceContext::MutatingUse(MutatingUseContext::Yield) |
 
         // Storage live and storage dead aren't proper defines, but we can ignore
         // values that come before them.
diff --git a/src/librustc_span/symbol.rs b/src/librustc_span/symbol.rs
index f194506e660..a61647bfd65 100644
--- a/src/librustc_span/symbol.rs
+++ b/src/librustc_span/symbol.rs
@@ -656,6 +656,7 @@ symbols! {
         rustc_partition_reused,
         rustc_peek,
         rustc_peek_definite_init,
+        rustc_peek_liveness,
         rustc_peek_maybe_init,
         rustc_peek_maybe_uninit,
         rustc_peek_indirectly_mutable,
diff --git a/src/test/ui/mir-dataflow/liveness-ptr.rs b/src/test/ui/mir-dataflow/liveness-ptr.rs
new file mode 100644
index 00000000000..34097d7526a
--- /dev/null
+++ b/src/test/ui/mir-dataflow/liveness-ptr.rs
@@ -0,0 +1,28 @@
+#![feature(core_intrinsics, rustc_attrs)]
+
+use std::intrinsics::rustc_peek;
+
+#[rustc_mir(rustc_peek_liveness, stop_after_dataflow)]
+fn foo() -> i32 {
+    let mut x: i32;
+    let mut p: *const i32;
+
+    x = 0;
+
+    // `x` is live here since it is used in the next statement...
+    unsafe { rustc_peek(x); }
+
+    p = &x;
+
+    // ... but not here, even while it can be accessed through `p`.
+    unsafe { rustc_peek(x); } //~ ERROR rustc_peek: bit not set
+    let tmp = unsafe { *p };
+
+    x = tmp + 1;
+
+    unsafe { rustc_peek(x); }
+
+    x
+}
+
+fn main() {}
diff --git a/src/test/ui/mir-dataflow/liveness-ptr.stderr b/src/test/ui/mir-dataflow/liveness-ptr.stderr
new file mode 100644
index 00000000000..3397d0c5a12
--- /dev/null
+++ b/src/test/ui/mir-dataflow/liveness-ptr.stderr
@@ -0,0 +1,10 @@
+error: rustc_peek: bit not set
+  --> $DIR/liveness-ptr.rs:18:14
+   |
+LL |     unsafe { rustc_peek(x); }
+   |              ^^^^^^^^^^^^^
+
+error: stop_after_dataflow ended compilation
+
+error: aborting due to 2 previous errors
+
diff --git a/src/tools/clippy/clippy_lints/src/redundant_clone.rs b/src/tools/clippy/clippy_lints/src/redundant_clone.rs
index d5cace0c647..d563eb886ae 100644
--- a/src/tools/clippy/clippy_lints/src/redundant_clone.rs
+++ b/src/tools/clippy/clippy_lints/src/redundant_clone.rs
@@ -591,7 +591,7 @@ struct PossibleBorrowerMap<'a, 'tcx> {
 impl PossibleBorrowerMap<'_, '_> {
     /// Returns true if the set of borrowers of `borrowed` living at `at` matches with `borrowers`.
     fn only_borrowers(&mut self, borrowers: &[mir::Local], borrowed: mir::Local, at: mir::Location) -> bool {
-        self.maybe_live.seek_after(at);
+        self.maybe_live.seek_after_primary_effect(at);
 
         self.bitset.0.clear();
         let maybe_live = &mut self.maybe_live;