Use new dataflow framework for drop elaboration and borrow checking

8 files changed, 166 insertions, 312 deletions

diff --git a/src/librustc_mir/borrow_check/flows.rs b/src/librustc_mir/borrow_check/flows.rs
deleted file mode 100644
index 57c544fda0c..00000000000
--- a/src/librustc_mir/borrow_check/flows.rs
+++ /dev/null
@@ -1,142 +0,0 @@
-//! Manages the dataflow bits required for borrowck.
-//!
-//! FIXME: this might be better as a "generic" fixed-point combinator,
-//! but is not as ugly as it is right now.
-
-use rustc::mir::{BasicBlock, Location};
-use rustc_index::bit_set::BitIter;
-
-use crate::borrow_check::location::LocationIndex;
-
-use crate::borrow_check::nll::PoloniusOutput;
-
-use crate::dataflow::indexes::BorrowIndex;
-use crate::dataflow::move_paths::HasMoveData;
-use crate::dataflow::Borrows;
-use crate::dataflow::EverInitializedPlaces;
-use crate::dataflow::MaybeUninitializedPlaces;
-use crate::dataflow::{FlowAtLocation, FlowsAtLocation};
-use either::Either;
-use std::fmt;
-use std::rc::Rc;
-
-crate struct Flows<'b, 'tcx> {
-    borrows: FlowAtLocation<'tcx, Borrows<'b, 'tcx>>,
-    pub uninits: FlowAtLocation<'tcx, MaybeUninitializedPlaces<'b, 'tcx>>,
-    pub ever_inits: FlowAtLocation<'tcx, EverInitializedPlaces<'b, 'tcx>>,
-
-    /// Polonius Output
-    pub polonius_output: Option<Rc<PoloniusOutput>>,
-}
-
-impl<'b, 'tcx> Flows<'b, 'tcx> {
-    crate fn new(
-        borrows: FlowAtLocation<'tcx, Borrows<'b, 'tcx>>,
-        uninits: FlowAtLocation<'tcx, MaybeUninitializedPlaces<'b, 'tcx>>,
-        ever_inits: FlowAtLocation<'tcx, EverInitializedPlaces<'b, 'tcx>>,
-        polonius_output: Option<Rc<PoloniusOutput>>,
-    ) -> Self {
-        Flows { borrows, uninits, ever_inits, polonius_output }
-    }
-
-    crate fn borrows_in_scope(
-        &self,
-        location: LocationIndex,
-    ) -> impl Iterator<Item = BorrowIndex> + '_ {
-        if let Some(ref polonius) = self.polonius_output {
-            Either::Left(polonius.errors_at(location).iter().cloned())
-        } else {
-            Either::Right(self.borrows.iter_incoming())
-        }
-    }
-
-    crate fn with_outgoing_borrows(&self, op: impl FnOnce(BitIter<'_, BorrowIndex>)) {
-        self.borrows.with_iter_outgoing(op)
-    }
-}
-
-macro_rules! each_flow {
-    ($this:ident, $meth:ident($arg:ident)) => {
-        FlowAtLocation::$meth(&mut $this.borrows, $arg);
-        FlowAtLocation::$meth(&mut $this.uninits, $arg);
-        FlowAtLocation::$meth(&mut $this.ever_inits, $arg);
-    };
-}
-
-impl<'b, 'tcx> FlowsAtLocation for Flows<'b, 'tcx> {
-    fn reset_to_entry_of(&mut self, bb: BasicBlock) {
-        each_flow!(self, reset_to_entry_of(bb));
-    }
-
-    fn reset_to_exit_of(&mut self, bb: BasicBlock) {
-        each_flow!(self, reset_to_exit_of(bb));
-    }
-
-    fn reconstruct_statement_effect(&mut self, location: Location) {
-        each_flow!(self, reconstruct_statement_effect(location));
-    }
-
-    fn reconstruct_terminator_effect(&mut self, location: Location) {
-        each_flow!(self, reconstruct_terminator_effect(location));
-    }
-
-    fn apply_local_effect(&mut self, location: Location) {
-        each_flow!(self, apply_local_effect(location));
-    }
-}
-
-impl<'b, 'tcx> fmt::Display for Flows<'b, 'tcx> {
-    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
-        let mut s = String::new();
-
-        s.push_str("borrows in effect: [");
-        let mut saw_one = false;
-        self.borrows.each_state_bit(|borrow| {
-            if saw_one {
-                s.push_str(", ");
-            };
-            saw_one = true;
-            let borrow_data = &self.borrows.operator().borrows()[borrow];
-            s.push_str(&borrow_data.to_string());
-        });
-        s.push_str("] ");
-
-        s.push_str("borrows generated: [");
-        let mut saw_one = false;
-        self.borrows.each_gen_bit(|borrow| {
-            if saw_one {
-                s.push_str(", ");
-            };
-            saw_one = true;
-            let borrow_data = &self.borrows.operator().borrows()[borrow];
-            s.push_str(&borrow_data.to_string());
-        });
-        s.push_str("] ");
-
-        s.push_str("uninits: [");
-        let mut saw_one = false;
-        self.uninits.each_state_bit(|mpi_uninit| {
-            if saw_one {
-                s.push_str(", ");
-            };
-            saw_one = true;
-            let move_path = &self.uninits.operator().move_data().move_paths[mpi_uninit];
-            s.push_str(&move_path.to_string());
-        });
-        s.push_str("] ");
-
-        s.push_str("ever_init: [");
-        let mut saw_one = false;
-        self.ever_inits.each_state_bit(|mpi_ever_init| {
-            if saw_one {
-                s.push_str(", ");
-            };
-            saw_one = true;
-            let ever_init = &self.ever_inits.operator().move_data().inits[mpi_ever_init];
-            s.push_str(&format!("{:?}", ever_init));
-        });
-        s.push_str("]");
-
-        fmt::Display::fmt(&s, fmt)
-    }
-}
diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs
index e528159fcef..95e21f34533 100644
--- a/src/librustc_mir/borrow_check/mod.rs
+++ b/src/librustc_mir/borrow_check/mod.rs
@@ -4,8 +4,8 @@ use rustc::infer::InferCtxt;
 use rustc::lint::builtin::MUTABLE_BORROW_RESERVATION_CONFLICT;
 use rustc::lint::builtin::UNUSED_MUT;
 use rustc::mir::{
-    read_only, Body, BodyAndCache, ClearCrossCrate, Local, Location, Mutability, Operand, Place,
-    PlaceElem, PlaceRef, ReadOnlyBodyAndCache,
+    read_only, traversal, Body, BodyAndCache, ClearCrossCrate, Local, Location, Mutability,
+    Operand, Place, PlaceElem, PlaceRef, ReadOnlyBodyAndCache,
 };
 use rustc::mir::{AggregateKind, BasicBlock, BorrowCheckResult, BorrowKind};
 use rustc::mir::{Field, ProjectionElem, Promoted, Rvalue, Statement, StatementKind};
@@ -21,6 +21,7 @@ use rustc_hir::{def_id::DefId, HirId, Node};
 use rustc_index::bit_set::BitSet;
 use rustc_index::vec::IndexVec;
 
+use either::Either;
 use smallvec::SmallVec;
 use std::cell::RefCell;
 use std::collections::BTreeMap;
@@ -30,19 +31,17 @@ use std::rc::Rc;
 use rustc_span::{Span, DUMMY_SP};
 use syntax::ast::Name;
 
+use crate::dataflow;
+use crate::dataflow::generic::{Analysis, BorrowckFlowState as Flows, BorrowckResults};
 use crate::dataflow::indexes::{BorrowIndex, InitIndex, MoveOutIndex, MovePathIndex};
-use crate::dataflow::move_paths::{HasMoveData, InitLocation, LookupResult, MoveData, MoveError};
+use crate::dataflow::move_paths::{InitLocation, LookupResult, MoveData, MoveError};
 use crate::dataflow::Borrows;
-use crate::dataflow::DataflowResultsConsumer;
 use crate::dataflow::EverInitializedPlaces;
-use crate::dataflow::FlowAtLocation;
 use crate::dataflow::MoveDataParamEnv;
-use crate::dataflow::{do_dataflow, DebugFormatted};
 use crate::dataflow::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
 use crate::transform::MirSource;
 
 use self::diagnostics::{AccessKind, RegionName};
-use self::flows::Flows;
 use self::location::LocationTable;
 use self::prefixes::PrefixSet;
 use self::MutateMode::{JustWrite, WriteAndRead};
@@ -54,7 +53,6 @@ mod constraint_generation;
 mod constraints;
 mod diagnostics;
 mod facts;
-mod flows;
 mod invalidation;
 mod location;
 mod member_constraints;
@@ -70,7 +68,7 @@ mod universal_regions;
 mod used_muts;
 
 crate use borrow_set::{BorrowData, BorrowSet};
-crate use nll::ToRegionVid;
+crate use nll::{PoloniusOutput, ToRegionVid};
 crate use place_ext::PlaceExt;
 crate use places_conflict::{places_conflict, PlaceConflictBias};
 crate use region_infer::RegionInferenceContext;
@@ -115,7 +113,6 @@ fn do_mir_borrowck<'a, 'tcx>(
     debug!("do_mir_borrowck(def_id = {:?})", def_id);
 
     let tcx = infcx.tcx;
-    let attributes = tcx.get_attrs(def_id);
     let param_env = tcx.param_env(def_id);
     let id = tcx.hir().as_local_hir_id(def_id).expect("do_mir_borrowck: non-local DefId");
 
@@ -188,16 +185,10 @@ fn do_mir_borrowck<'a, 'tcx>(
 
     let mdpe = MoveDataParamEnv { move_data, param_env };
 
-    let dead_unwinds = BitSet::new_empty(body.basic_blocks().len());
-    let mut flow_inits = FlowAtLocation::new(do_dataflow(
-        tcx,
-        &body,
-        def_id,
-        &attributes,
-        &dead_unwinds,
-        MaybeInitializedPlaces::new(tcx, &body, &mdpe),
-        |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]),
-    ));
+    let mut flow_inits = MaybeInitializedPlaces::new(tcx, &body, &mdpe)
+        .into_engine(tcx, &body, def_id)
+        .iterate_to_fixpoint()
+        .into_results_cursor(&body);
 
     let locals_are_invalidated_at_exit = tcx.hir().body_owner_kind(id).is_fn_or_closure();
     let borrow_set =
@@ -233,33 +224,15 @@ fn do_mir_borrowck<'a, 'tcx>(
 
     let regioncx = Rc::new(regioncx);
 
-    let flow_borrows = FlowAtLocation::new(do_dataflow(
-        tcx,
-        &body,
-        def_id,
-        &attributes,
-        &dead_unwinds,
-        Borrows::new(tcx, &body, regioncx.clone(), &borrow_set),
-        |rs, i| DebugFormatted::new(&rs.location(i)),
-    ));
-    let flow_uninits = FlowAtLocation::new(do_dataflow(
-        tcx,
-        &body,
-        def_id,
-        &attributes,
-        &dead_unwinds,
-        MaybeUninitializedPlaces::new(tcx, &body, &mdpe),
-        |bd, i| DebugFormatted::new(&bd.move_data().move_paths[i]),
-    ));
-    let flow_ever_inits = FlowAtLocation::new(do_dataflow(
-        tcx,
-        &body,
-        def_id,
-        &attributes,
-        &dead_unwinds,
-        EverInitializedPlaces::new(tcx, &body, &mdpe),
-        |bd, i| DebugFormatted::new(&bd.move_data().inits[i]),
-    ));
+    let flow_borrows = Borrows::new(tcx, &body, regioncx.clone(), &borrow_set)
+        .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_ever_inits = EverInitializedPlaces::new(tcx, &body, &mdpe)
+        .into_engine(tcx, &body, def_id)
+        .iterate_to_fixpoint();
 
     let movable_generator = match tcx.hir().get(id) {
         Node::Expr(&hir::Expr {
@@ -294,17 +267,28 @@ fn do_mir_borrowck<'a, 'tcx>(
         local_names,
         region_names: RefCell::default(),
         next_region_name: RefCell::new(1),
+        polonius_output,
     };
 
     // Compute and report region errors, if any.
     mbcx.report_region_errors(nll_errors);
 
-    let mut state = Flows::new(flow_borrows, flow_uninits, flow_ever_inits, polonius_output);
+    let results = BorrowckResults {
+        ever_inits: flow_ever_inits,
+        uninits: flow_uninits,
+        borrows: flow_borrows,
+    };
 
     if let Some(errors) = move_errors {
         mbcx.report_move_errors(errors);
     }
-    mbcx.analyze_results(&mut state); // entry point for DataflowResultsConsumer
+
+    dataflow::generic::visit_results(
+        &*body,
+        traversal::reverse_postorder(&*body).map(|(bb, _)| bb),
+        &results,
+        &mut mbcx,
+    );
 
     // Convert any reservation warnings into lints.
     let reservation_warnings = mem::take(&mut mbcx.reservation_warnings);
@@ -500,6 +484,9 @@ crate struct MirBorrowckCtxt<'cx, 'tcx> {
 
     /// The counter for generating new region names.
     next_region_name: RefCell<usize>,
+
+    /// Results of Polonius analysis.
+    polonius_output: Option<Rc<PoloniusOutput>>,
 }
 
 // Check that:
@@ -507,24 +494,16 @@ crate struct MirBorrowckCtxt<'cx, 'tcx> {
 // 2. loans made in overlapping scopes do not conflict
 // 3. assignments do not affect things loaned out as immutable
 // 4. moves do not affect things loaned out in any way
-impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx> {
+impl<'cx, 'tcx> dataflow::generic::ResultsVisitor<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx> {
     type FlowState = Flows<'cx, 'tcx>;
 
-    fn body(&self) -> &'cx Body<'tcx> {
-        *self.body
-    }
-
-    fn visit_block_entry(&mut self, bb: BasicBlock, flow_state: &Self::FlowState) {
-        debug!("MirBorrowckCtxt::process_block({:?}): {}", bb, flow_state);
-    }
-
-    fn visit_statement_entry(
+    fn visit_statement(
         &mut self,
-        location: Location,
+        flow_state: &Flows<'cx, 'tcx>,
         stmt: &'cx Statement<'tcx>,
-        flow_state: &Self::FlowState,
+        location: Location,
     ) {
-        debug!("MirBorrowckCtxt::process_statement({:?}, {:?}): {}", location, stmt, flow_state);
+        debug!("MirBorrowckCtxt::process_statement({:?}, {:?}): {:?}", location, stmt, flow_state);
         let span = stmt.source_info.span;
 
         self.check_activations(location, span, flow_state);
@@ -607,17 +586,16 @@ impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx
         }
     }
 
-    fn visit_terminator_entry(
+    fn visit_terminator(
         &mut self,
-        location: Location,
+        flow_state: &Flows<'cx, 'tcx>,
         term: &'cx Terminator<'tcx>,
-        flow_state: &Self::FlowState,
+        loc: Location,
     ) {
-        let loc = location;
-        debug!("MirBorrowckCtxt::process_terminator({:?}, {:?}): {}", location, term, flow_state);
+        debug!("MirBorrowckCtxt::process_terminator({:?}, {:?}): {:?}", loc, term, flow_state);
         let span = term.source_info.span;
 
-        self.check_activations(location, span, flow_state);
+        self.check_activations(loc, span, flow_state);
 
         match term.kind {
             TerminatorKind::SwitchInt { ref discr, switch_ty: _, values: _, targets: _ } => {
@@ -686,19 +664,40 @@ impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx
 
             TerminatorKind::Yield { ref value, resume: _, ref resume_arg, drop: _ } => {
                 self.consume_operand(loc, (value, span), flow_state);
+                self.mutate_place(loc, (resume_arg, span), Deep, JustWrite, flow_state);
+            }
+
+            TerminatorKind::Goto { target: _ }
+            | TerminatorKind::Abort
+            | TerminatorKind::Unreachable
+            | TerminatorKind::Resume
+            | TerminatorKind::Return
+            | TerminatorKind::GeneratorDrop
+            | TerminatorKind::FalseEdges { real_target: _, imaginary_target: _ }
+            | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } => {
+                // no data used, thus irrelevant to borrowck
+            }
+        }
+    }
+
+    fn visit_terminator_exit(
+        &mut self,
+        flow_state: &Flows<'cx, 'tcx>,
+        term: &'cx Terminator<'tcx>,
+        loc: Location,
+    ) {
+        let span = term.source_info.span;
 
+        match term.kind {
+            TerminatorKind::Yield { value: _, resume: _, resume_arg: _, drop: _ } => {
                 if self.movable_generator {
                     // Look for any active borrows to locals
                     let borrow_set = self.borrow_set.clone();
-                    flow_state.with_outgoing_borrows(|borrows| {
-                        for i in borrows {
-                            let borrow = &borrow_set[i];
-                            self.check_for_local_borrow(borrow, span);
-                        }
-                    });
+                    for i in flow_state.borrows.iter() {
+                        let borrow = &borrow_set[i];
+                        self.check_for_local_borrow(borrow, span);
+                    }
                 }
-
-                self.mutate_place(loc, (resume_arg, span), Deep, JustWrite, flow_state);
             }
 
             TerminatorKind::Resume | TerminatorKind::Return | TerminatorKind::GeneratorDrop => {
@@ -707,20 +706,13 @@ impl<'cx, 'tcx> DataflowResultsConsumer<'cx, 'tcx> for MirBorrowckCtxt<'cx, 'tcx
                 // StorageDead, but we don't always emit those (notably on unwind paths),
                 // so this "extra check" serves as a kind of backup.
                 let borrow_set = self.borrow_set.clone();
-                flow_state.with_outgoing_borrows(|borrows| {
-                    for i in borrows {
-                        let borrow = &borrow_set[i];
-                        self.check_for_invalidation_at_exit(loc, borrow, span);
-                    }
-                });
-            }
-            TerminatorKind::Goto { target: _ }
-            | TerminatorKind::Abort
-            | TerminatorKind::Unreachable
-            | TerminatorKind::FalseEdges { real_target: _, imaginary_target: _ }
-            | TerminatorKind::FalseUnwind { real_target: _, unwind: _ } => {
-                // no data used, thus irrelevant to borrowck
+                for i in flow_state.borrows.iter() {
+                    let borrow = &borrow_set[i];
+                    self.check_for_invalidation_at_exit(loc, borrow, span);
+                }
             }
+
+            _ => {}
         }
     }
 }
@@ -855,6 +847,10 @@ impl InitializationRequiringAction {
 }
 
 impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
+    fn body(&self) -> &'cx Body<'tcx> {
+        *self.body
+    }
+
     /// Checks an access to the given place to see if it is allowed. Examines the set of borrows
     /// that are in scope, as well as which paths have been initialized, to ensure that (a) the
     /// place is initialized and (b) it is not borrowed in some way that would prevent this
@@ -934,8 +930,17 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         let tcx = self.infcx.tcx;
         let body = self.body;
         let body: &Body<'_> = &body;
-        let location_table = self.location_table.start_index(location);
         let borrow_set = self.borrow_set.clone();
+
+        // Use polonius output if it has been enabled.
+        let polonius_output = self.polonius_output.clone();
+        let borrows_in_scope = if let Some(polonius) = &polonius_output {
+            let location = self.location_table.start_index(location);
+            Either::Left(polonius.errors_at(location).iter().copied())
+        } else {
+            Either::Right(flow_state.borrows.iter())
+        };
+
         each_borrow_involving_path(
             self,
             tcx,
@@ -943,7 +948,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             location,
             (sd, place_span.0),
             &borrow_set,
-            flow_state.borrows_in_scope(location_table),
+            borrows_in_scope,
             |this, borrow_index, borrow| match (rw, borrow.kind) {
                 // Obviously an activation is compatible with its own
                 // reservation (or even prior activating uses of same
@@ -1473,9 +1478,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
             // initial reservation.
         }
     }
-}
 
-impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
     fn check_if_reassignment_to_immutable_state(
         &mut self,
         location: Location,
@@ -1565,21 +1568,26 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         location: Location,
         desired_action: InitializationRequiringAction,
         place_span: (PlaceRef<'cx, 'tcx>, Span),
-        maybe_uninits: &FlowAtLocation<'tcx, MaybeUninitializedPlaces<'cx, 'tcx>>,
+        maybe_uninits: &BitSet<MovePathIndex>,
         from: u32,
         to: u32,
     ) {
         if let Some(mpi) = self.move_path_for_place(place_span.0) {
-            let mut child = self.move_data.move_paths[mpi].first_child;
+            let move_paths = &self.move_data.move_paths;
+            let mut child = move_paths[mpi].first_child;
             while let Some(child_mpi) = child {
-                let child_move_place = &self.move_data.move_paths[child_mpi];
-                let child_place = &child_move_place.place;
-                let last_proj = child_place.projection.last().unwrap();
+                let child_move_path = &move_paths[child_mpi];
+                let last_proj = child_move_path.place.projection.last().unwrap();
                 if let ProjectionElem::ConstantIndex { offset, from_end, .. } = last_proj {
                     debug_assert!(!from_end, "Array constant indexing shouldn't be `from_end`.");
 
                     if (from..to).contains(offset) {
-                        if let Some(uninit_child) = maybe_uninits.has_any_child_of(child_mpi) {
+                        let uninit_child =
+                            self.move_data.find_in_move_path_or_its_descendants(child_mpi, |mpi| {
+                                maybe_uninits.contains(mpi)
+                            });
+
+                        if let Some(uninit_child) = uninit_child {
                             self.report_use_of_moved_or_uninitialized(
                                 location,
                                 desired_action,
@@ -1590,7 +1598,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
                         }
                     }
                 }
-                child = child_move_place.next_sibling;
+                child = child_move_path.next_sibling;
             }
         }
     }
@@ -1651,12 +1659,16 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
 
         debug!("check_if_path_or_subpath_is_moved place: {:?}", place_span.0);
         if let Some(mpi) = self.move_path_for_place(place_span.0) {
-            if let Some(child_mpi) = maybe_uninits.has_any_child_of(mpi) {
+            let uninit_mpi = self
+                .move_data
+                .find_in_move_path_or_its_descendants(mpi, |mpi| maybe_uninits.contains(mpi));
+
+            if let Some(uninit_mpi) = uninit_mpi {
                 self.report_use_of_moved_or_uninitialized(
                     location,
                     desired_action,
                     (place_span.0, place_span.0, place_span.1),
-                    child_mpi,
+                    uninit_mpi,
                 );
                 return; // don't bother finding other problems.
             }
diff --git a/src/librustc_mir/borrow_check/nll.rs b/src/librustc_mir/borrow_check/nll.rs
index 73718d58346..a71dfc9a778 100644
--- a/src/librustc_mir/borrow_check/nll.rs
+++ b/src/librustc_mir/borrow_check/nll.rs
@@ -20,8 +20,8 @@ use std::str::FromStr;
 use self::mir_util::PassWhere;
 use polonius_engine::{Algorithm, Output};
 
+use crate::dataflow::generic::ResultsCursor;
 use crate::dataflow::move_paths::{InitKind, InitLocation, MoveData};
-use crate::dataflow::FlowAtLocation;
 use crate::dataflow::MaybeInitializedPlaces;
 use crate::transform::MirSource;
 use crate::util as mir_util;
@@ -149,7 +149,7 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
     promoted: &IndexVec<Promoted, ReadOnlyBodyAndCache<'_, 'tcx>>,
     location_table: &LocationTable,
     param_env: ty::ParamEnv<'tcx>,
-    flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'cx, 'tcx>>,
+    flow_inits: &mut ResultsCursor<'cx, 'tcx, MaybeInitializedPlaces<'cx, 'tcx>>,
     move_data: &MoveData<'tcx>,
     borrow_set: &BorrowSet<'tcx>,
 ) -> NllOutput<'tcx> {
diff --git a/src/librustc_mir/borrow_check/type_check/liveness/mod.rs b/src/librustc_mir/borrow_check/type_check/liveness/mod.rs
index e461ce739a7..cdf962ee31a 100644
--- a/src/librustc_mir/borrow_check/type_check/liveness/mod.rs
+++ b/src/librustc_mir/borrow_check/type_check/liveness/mod.rs
@@ -3,8 +3,8 @@ use rustc::ty::{RegionVid, TyCtxt};
 use rustc_data_structures::fx::FxHashSet;
 use std::rc::Rc;
 
+use crate::dataflow::generic::ResultsCursor;
 use crate::dataflow::move_paths::MoveData;
-use crate::dataflow::FlowAtLocation;
 use crate::dataflow::MaybeInitializedPlaces;
 
 use crate::borrow_check::{
@@ -30,11 +30,11 @@ mod trace;
 ///
 /// N.B., this computation requires normalization; therefore, it must be
 /// performed before
-pub(super) fn generate<'tcx>(
+pub(super) fn generate<'mir, 'tcx>(
     typeck: &mut TypeChecker<'_, 'tcx>,
     body: ReadOnlyBodyAndCache<'_, 'tcx>,
     elements: &Rc<RegionValueElements>,
-    flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>,
+    flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>,
     move_data: &MoveData<'tcx>,
     location_table: &LocationTable,
 ) {
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 ebb925ae0cb..198f4b4b42e 100644
--- a/src/librustc_mir/borrow_check/type_check/liveness/trace.rs
+++ b/src/librustc_mir/borrow_check/type_check/liveness/trace.rs
@@ -8,9 +8,10 @@ use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_index::bit_set::HybridBitSet;
 use std::rc::Rc;
 
+use crate::dataflow::generic::ResultsCursor;
 use crate::dataflow::indexes::MovePathIndex;
-use crate::dataflow::move_paths::MoveData;
-use crate::dataflow::{FlowAtLocation, FlowsAtLocation, MaybeInitializedPlaces};
+use crate::dataflow::move_paths::{HasMoveData, MoveData};
+use crate::dataflow::MaybeInitializedPlaces;
 
 use crate::borrow_check::{
     region_infer::values::{self, PointIndex, RegionValueElements},
@@ -38,7 +39,7 @@ pub(super) fn trace(
     typeck: &mut TypeChecker<'_, 'tcx>,
     body: ReadOnlyBodyAndCache<'_, 'tcx>,
     elements: &Rc<RegionValueElements>,
-    flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>,
+    flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>,
     move_data: &MoveData<'tcx>,
     live_locals: Vec<Local>,
     polonius_drop_used: Option<Vec<(Local, Location)>>,
@@ -85,7 +86,7 @@ struct LivenessContext<'me, 'typeck, 'flow, 'tcx> {
 
     /// Results of dataflow tracking which variables (and paths) have been
     /// initialized.
-    flow_inits: &'me mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'flow, 'tcx>>,
+    flow_inits: &'me mut ResultsCursor<'flow, 'tcx, MaybeInitializedPlaces<'flow, 'tcx>>,
 
     /// Index indicating where each variable is assigned, used, or
     /// dropped.
@@ -389,23 +390,26 @@ impl LivenessResults<'me, 'typeck, 'flow, 'tcx> {
 }
 
 impl LivenessContext<'_, '_, '_, 'tcx> {
+    /// Returns `true` if the local variable (or some part of it) is initialized at the current
+    /// cursor position. Callers should call one of the `seek` methods immediately before to point
+    /// the cursor to the desired location.
+    fn initialized_at_curr_loc(&self, mpi: MovePathIndex) -> bool {
+        let state = self.flow_inits.get();
+        if state.contains(mpi) {
+            return true;
+        }
+
+        let move_paths = &self.flow_inits.analysis().move_data().move_paths;
+        move_paths[mpi].find_descendant(&move_paths, |mpi| state.contains(mpi)).is_some()
+    }
+
     /// Returns `true` if the local variable (or some part of it) is initialized in
     /// the terminator of `block`. We need to check this to determine if a
     /// DROP of some local variable will have an effect -- note that
     /// drops, as they may unwind, are always terminators.
     fn initialized_at_terminator(&mut self, block: BasicBlock, mpi: MovePathIndex) -> bool {
-        // Compute the set of initialized paths at terminator of block
-        // by resetting to the start of the block and then applying
-        // the effects of all statements. This is the only way to get
-        // "just ahead" of a terminator.
-        self.flow_inits.reset_to_entry_of(block);
-        for statement_index in 0..self.body[block].statements.len() {
-            let location = Location { block, statement_index };
-            self.flow_inits.reconstruct_statement_effect(location);
-            self.flow_inits.apply_local_effect(location);
-        }
-
-        self.flow_inits.has_any_child_of(mpi).is_some()
+        self.flow_inits.seek_before(self.body.terminator_loc(block));
+        self.initialized_at_curr_loc(mpi)
     }
 
     /// Returns `true` if the path `mpi` (or some part of it) is initialized at
@@ -414,8 +418,8 @@ 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.reset_to_exit_of(block);
-        self.flow_inits.has_any_child_of(mpi).is_some()
+        self.flow_inits.seek_after(self.body.terminator_loc(block));
+        self.initialized_at_curr_loc(mpi)
     }
 
     /// Stores the result that all regions in `value` are live for the
diff --git a/src/librustc_mir/borrow_check/type_check/mod.rs b/src/librustc_mir/borrow_check/type_check/mod.rs
index f645435cdf6..100fd7dc48d 100644
--- a/src/librustc_mir/borrow_check/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/type_check/mod.rs
@@ -34,8 +34,8 @@ use rustc_index::vec::{Idx, IndexVec};
 use rustc_span::{Span, DUMMY_SP};
 use syntax::ast;
 
+use crate::dataflow::generic::ResultsCursor;
 use crate::dataflow::move_paths::MoveData;
-use crate::dataflow::FlowAtLocation;
 use crate::dataflow::MaybeInitializedPlaces;
 use crate::transform::promote_consts::should_suggest_const_in_array_repeat_expressions_attribute;
 
@@ -114,7 +114,7 @@ mod relate_tys;
 ///   constraints for the regions in the types of variables
 /// - `flow_inits` -- results of a maybe-init dataflow analysis
 /// - `move_data` -- move-data constructed when performing the maybe-init dataflow analysis
-pub(crate) fn type_check<'tcx>(
+pub(crate) fn type_check<'mir, 'tcx>(
     infcx: &InferCtxt<'_, 'tcx>,
     param_env: ty::ParamEnv<'tcx>,
     body: ReadOnlyBodyAndCache<'_, 'tcx>,
@@ -124,7 +124,7 @@ pub(crate) fn type_check<'tcx>(
     location_table: &LocationTable,
     borrow_set: &BorrowSet<'tcx>,
     all_facts: &mut Option<AllFacts>,
-    flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'tcx>>,
+    flow_inits: &mut ResultsCursor<'mir, 'tcx, MaybeInitializedPlaces<'mir, 'tcx>>,
     move_data: &MoveData<'tcx>,
     elements: &Rc<RegionValueElements>,
 ) -> MirTypeckResults<'tcx> {
diff --git a/src/librustc_mir/dataflow/impls/borrows.rs b/src/librustc_mir/dataflow/impls/borrows.rs
index 151ae28bae2..74d1094f964 100644
--- a/src/librustc_mir/dataflow/impls/borrows.rs
+++ b/src/librustc_mir/dataflow/impls/borrows.rs
@@ -4,11 +4,9 @@ use rustc::ty::TyCtxt;
 
 use rustc_data_structures::fx::FxHashMap;
 use rustc_index::bit_set::BitSet;
-use rustc_index::vec::IndexVec;
 
 use crate::borrow_check::{
-    places_conflict, BorrowData, BorrowSet, PlaceConflictBias, PlaceExt, RegionInferenceContext,
-    ToRegionVid,
+    places_conflict, BorrowSet, PlaceConflictBias, PlaceExt, RegionInferenceContext, ToRegionVid,
 };
 use crate::dataflow::generic::{self, GenKill};
 use crate::dataflow::BottomValue;
@@ -161,10 +159,6 @@ impl<'a, 'tcx> Borrows<'a, 'tcx> {
         }
     }
 
-    crate fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> {
-        &self.borrow_set.borrows
-    }
-
     pub fn location(&self, idx: BorrowIndex) -> &Location {
         &self.borrow_set.borrows[idx].reserve_location
     }
diff --git a/src/librustc_mir/transform/elaborate_drops.rs b/src/librustc_mir/transform/elaborate_drops.rs
index 1c0b1b8c137..319b6f35f11 100644
--- a/src/librustc_mir/transform/elaborate_drops.rs
+++ b/src/librustc_mir/transform/elaborate_drops.rs
@@ -1,7 +1,7 @@
-use crate::dataflow::move_paths::{HasMoveData, LookupResult, MoveData, MovePathIndex};
-use crate::dataflow::DataflowResults;
+use crate::dataflow;
+use crate::dataflow::generic::{Analysis, Results};
+use crate::dataflow::move_paths::{LookupResult, MoveData, MovePathIndex};
 use crate::dataflow::MoveDataParamEnv;
-use crate::dataflow::{self, do_dataflow, DebugFormatted};
 use crate::dataflow::{drop_flag_effects_for_location, on_lookup_result_bits};
 use crate::dataflow::{on_all_children_bits, on_all_drop_children_bits};
 use crate::dataflow::{MaybeInitializedPlaces, MaybeUninitializedPlaces};
@@ -40,24 +40,16 @@ impl<'tcx> MirPass<'tcx> for ElaborateDrops {
             let body = &*body;
             let env = MoveDataParamEnv { move_data, param_env };
             let dead_unwinds = find_dead_unwinds(tcx, body, def_id, &env);
-            let flow_inits = do_dataflow(
-                tcx,
-                body,
-                def_id,
-                &[],
-                &dead_unwinds,
-                MaybeInitializedPlaces::new(tcx, body, &env),
-                |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]),
-            );
-            let flow_uninits = do_dataflow(
-                tcx,
-                body,
-                def_id,
-                &[],
-                &dead_unwinds,
-                MaybeUninitializedPlaces::new(tcx, body, &env),
-                |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]),
-            );
+
+            let flow_inits = MaybeInitializedPlaces::new(tcx, body, &env)
+                .into_engine(tcx, body, def_id)
+                .dead_unwinds(&dead_unwinds)
+                .iterate_to_fixpoint();
+
+            let flow_uninits = MaybeUninitializedPlaces::new(tcx, body, &env)
+                .into_engine(tcx, body, def_id)
+                .dead_unwinds(&dead_unwinds)
+                .iterate_to_fixpoint();
 
             ElaborateDropsCtxt {
                 tcx,
@@ -87,15 +79,9 @@ fn find_dead_unwinds<'tcx>(
     // We only need to do this pass once, because unwind edges can only
     // reach cleanup blocks, which can't have unwind edges themselves.
     let mut dead_unwinds = BitSet::new_empty(body.basic_blocks().len());
-    let flow_inits = do_dataflow(
-        tcx,
-        body,
-        def_id,
-        &[],
-        &dead_unwinds,
-        MaybeInitializedPlaces::new(tcx, body, &env),
-        |bd, p| DebugFormatted::new(&bd.move_data().move_paths[p]),
-    );
+    let flow_inits = MaybeInitializedPlaces::new(tcx, body, &env)
+        .into_engine(tcx, body, def_id)
+        .iterate_to_fixpoint();
     for (bb, bb_data) in body.basic_blocks().iter_enumerated() {
         let location = match bb_data.terminator().kind {
             TerminatorKind::Drop { ref location, unwind: Some(_), .. }
@@ -104,7 +90,7 @@ fn find_dead_unwinds<'tcx>(
         };
 
         let mut init_data = InitializationData {
-            live: flow_inits.sets().entry_set_for(bb.index()).to_owned(),
+            live: flow_inits.entry_set_for_block(bb).clone(),
             dead: BitSet::new_empty(env.move_data.move_paths.len()),
         };
         debug!("find_dead_unwinds @ {:?}: {:?}; init_data={:?}", bb, bb_data, init_data.live);
@@ -283,8 +269,8 @@ struct ElaborateDropsCtxt<'a, 'tcx> {
     tcx: TyCtxt<'tcx>,
     body: &'a Body<'tcx>,
     env: &'a MoveDataParamEnv<'tcx>,
-    flow_inits: DataflowResults<'tcx, MaybeInitializedPlaces<'a, 'tcx>>,
-    flow_uninits: DataflowResults<'tcx, MaybeUninitializedPlaces<'a, 'tcx>>,
+    flow_inits: Results<'tcx, MaybeInitializedPlaces<'a, 'tcx>>,
+    flow_uninits: Results<'tcx, MaybeUninitializedPlaces<'a, 'tcx>>,
     drop_flags: FxHashMap<MovePathIndex, Local>,
     patch: MirPatch<'tcx>,
 }
@@ -300,8 +286,8 @@ impl<'b, 'tcx> ElaborateDropsCtxt<'b, 'tcx> {
 
     fn initialization_data_at(&self, loc: Location) -> InitializationData {
         let mut data = InitializationData {
-            live: self.flow_inits.sets().entry_set_for(loc.block.index()).to_owned(),
-            dead: self.flow_uninits.sets().entry_set_for(loc.block.index()).to_owned(),
+            live: self.flow_inits.entry_set_for_block(loc.block).to_owned(),
+            dead: self.flow_uninits.entry_set_for_block(loc.block).to_owned(),
         };
         for stmt in 0..loc.statement_index {
             data.apply_location(