Remove old `util/liveness.rs` module

The liveness dataflow analysis now lives in
`librustc_mir/dataflow/impls/liveness.rs`. The borrow-checker has an
abstraction around of "defs" and "uses" that I've made module private. I
would have moved it to `util/def_use.rs`, but there's a slightly
different abstraction used for copy propagation with that name.

7 files changed, 85 insertions, 334 deletions

diff --git a/src/librustc_mir/borrow_check/def_use.rs b/src/librustc_mir/borrow_check/def_use.rs
new file mode 100644
index 00000000000..689ec249a2f
--- /dev/null
+++ b/src/librustc_mir/borrow_check/def_use.rs
@@ -0,0 +1,78 @@
+use rustc_middle::mir::visit::{
+    MutatingUseContext, NonMutatingUseContext, NonUseContext, PlaceContext,
+};
+
+#[derive(Eq, PartialEq, Clone)]
+pub enum DefUse {
+    Def,
+    Use,
+    Drop,
+}
+
+pub fn categorize(context: PlaceContext) -> Option<DefUse> {
+    match context {
+        ///////////////////////////////////////////////////////////////////////////
+        // DEFS
+
+        PlaceContext::MutatingUse(MutatingUseContext::Store) |
+
+        // This is potentially both a def and a use...
+        PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) |
+
+        // We let Call define the result in both the success and
+        // unwind cases. This is not really correct, however it
+        // does not seem to be observable due to the way that we
+        // generate MIR. To do things properly, we would apply
+        // 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.
+        PlaceContext::NonUse(NonUseContext::StorageLive) |
+        PlaceContext::NonUse(NonUseContext::StorageDead) => Some(DefUse::Def),
+
+        ///////////////////////////////////////////////////////////////////////////
+        // REGULAR USES
+        //
+        // These are uses that occur *outside* of a drop. For the
+        // purposes of NLL, these are special in that **all** the
+        // lifetimes appearing in the variable must be live for each regular use.
+
+        PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) |
+        PlaceContext::MutatingUse(MutatingUseContext::Projection) |
+
+        // Borrows only consider their local used at the point of the borrow.
+        // This won't affect the results since we use this analysis for generators
+        // and we only care about the result at suspension points. Borrows cannot
+        // cross suspension points so this behavior is unproblematic.
+        PlaceContext::MutatingUse(MutatingUseContext::Borrow) |
+        PlaceContext::NonMutatingUse(NonMutatingUseContext::SharedBorrow) |
+        PlaceContext::NonMutatingUse(NonMutatingUseContext::ShallowBorrow) |
+        PlaceContext::NonMutatingUse(NonMutatingUseContext::UniqueBorrow) |
+
+        PlaceContext::MutatingUse(MutatingUseContext::AddressOf) |
+        PlaceContext::NonMutatingUse(NonMutatingUseContext::AddressOf) |
+        PlaceContext::NonMutatingUse(NonMutatingUseContext::Inspect) |
+        PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
+        PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) |
+        PlaceContext::NonUse(NonUseContext::AscribeUserTy) |
+        PlaceContext::MutatingUse(MutatingUseContext::Retag) =>
+            Some(DefUse::Use),
+
+        ///////////////////////////////////////////////////////////////////////////
+        // DROP USES
+        //
+        // These are uses that occur in a DROP (a MIR drop, not a
+        // call to `std::mem::drop()`). For the purposes of NLL,
+        // uses in drop are special because `#[may_dangle]`
+        // attributes can affect whether lifetimes must be live.
+
+        PlaceContext::MutatingUse(MutatingUseContext::Drop) =>
+            Some(DefUse::Drop),
+
+        // Debug info is neither def nor use.
+        PlaceContext::NonUse(NonUseContext::VarDebugInfo) => None,
+    }
+}
diff --git a/src/librustc_mir/borrow_check/diagnostics/find_use.rs b/src/librustc_mir/borrow_check/diagnostics/find_use.rs
index 6c6bde8ae2c..8d8cdfb5293 100644
--- a/src/librustc_mir/borrow_check/diagnostics/find_use.rs
+++ b/src/librustc_mir/borrow_check/diagnostics/find_use.rs
@@ -2,10 +2,10 @@ use std::collections::VecDeque;
 use std::rc::Rc;
 
 use crate::borrow_check::{
+    def_use::{self, DefUse},
     nll::ToRegionVid,
     region_infer::{Cause, RegionInferenceContext},
 };
-use crate::util::liveness::{self, DefUse};
 use rustc_data_structures::fx::FxHashSet;
 use rustc_middle::mir::visit::{MirVisitable, PlaceContext, Visitor};
 use rustc_middle::mir::{Body, Local, Location};
@@ -117,7 +117,7 @@ impl<'cx, 'tcx> Visitor<'tcx> for DefUseVisitor<'cx, 'tcx> {
         });
 
         if found_it {
-            self.def_use_result = match liveness::categorize(context) {
+            self.def_use_result = match def_use::categorize(context) {
                 Some(DefUse::Def) => Some(DefUseResult::Def),
                 Some(DefUse::Use) => Some(DefUseResult::UseLive { local }),
                 Some(DefUse::Drop) => Some(DefUseResult::UseDrop { local }),
diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs
index 7d8a2b540a9..78bc659a261 100644
--- a/src/librustc_mir/borrow_check/mod.rs
+++ b/src/librustc_mir/borrow_check/mod.rs
@@ -51,6 +51,7 @@ use self::path_utils::*;
 mod borrow_set;
 mod constraint_generation;
 mod constraints;
+mod def_use;
 mod diagnostics;
 mod facts;
 mod invalidation;
diff --git a/src/librustc_mir/borrow_check/type_check/liveness/local_use_map.rs b/src/librustc_mir/borrow_check/type_check/liveness/local_use_map.rs
index 0fdf96710c6..995e3a60a0c 100644
--- a/src/librustc_mir/borrow_check/type_check/liveness/local_use_map.rs
+++ b/src/librustc_mir/borrow_check/type_check/liveness/local_use_map.rs
@@ -3,8 +3,7 @@ use rustc_index::vec::IndexVec;
 use rustc_middle::mir::visit::{PlaceContext, Visitor};
 use rustc_middle::mir::{Body, Local, Location};
 
-use crate::util::liveness::{categorize, DefUse};
-
+use crate::borrow_check::def_use::{self, DefUse};
 use crate::borrow_check::region_infer::values::{PointIndex, RegionValueElements};
 
 /// A map that cross references each local with the locations where it
@@ -160,7 +159,7 @@ impl LocalUseMapBuild<'_> {
 impl Visitor<'tcx> for LocalUseMapBuild<'_> {
     fn visit_local(&mut self, &local: &Local, context: PlaceContext, location: Location) {
         if self.locals_with_use_data[local] {
-            match categorize(context) {
+            match def_use::categorize(context) {
                 Some(DefUse::Def) => self.insert_def(local, location),
                 Some(DefUse::Use) => self.insert_use(local, location),
                 Some(DefUse::Drop) => self.insert_drop(local, location),
diff --git a/src/librustc_mir/borrow_check/type_check/liveness/polonius.rs b/src/librustc_mir/borrow_check/type_check/liveness/polonius.rs
index 2e033896ce1..d285098c52a 100644
--- a/src/librustc_mir/borrow_check/type_check/liveness/polonius.rs
+++ b/src/librustc_mir/borrow_check/type_check/liveness/polonius.rs
@@ -1,7 +1,7 @@
+use crate::borrow_check::def_use::{self, DefUse};
 use crate::borrow_check::location::{LocationIndex, LocationTable};
 use crate::dataflow::indexes::MovePathIndex;
 use crate::dataflow::move_paths::{LookupResult, MoveData};
-use crate::util::liveness::{categorize, DefUse};
 use rustc_middle::mir::visit::{MutatingUseContext, PlaceContext, Visitor};
 use rustc_middle::mir::{Body, Local, Location, Place};
 use rustc_middle::ty::subst::GenericArg;
@@ -56,7 +56,7 @@ impl UseFactsExtractor<'_> {
 
 impl Visitor<'tcx> for UseFactsExtractor<'_> {
     fn visit_local(&mut self, &local: &Local, context: PlaceContext, location: Location) {
-        match categorize(context) {
+        match def_use::categorize(context) {
             Some(DefUse::Def) => self.insert_def(local, location),
             Some(DefUse::Use) => self.insert_use(local, location),
             Some(DefUse::Drop) => self.insert_drop_use(local, location),
diff --git a/src/librustc_mir/util/liveness.rs b/src/librustc_mir/util/liveness.rs
deleted file mode 100644
index c261219cc73..00000000000
--- a/src/librustc_mir/util/liveness.rs
+++ /dev/null
@@ -1,326 +0,0 @@
-//! Liveness analysis which computes liveness of MIR local variables at the boundary of basic
-//! blocks.
-//!
-//! This analysis considers references as being used only at the point of the
-//! borrow. This means that this does not track uses because of references that
-//! already exist:
-//!
-//! ```rust
-//! fn foo() {
-//!     x = 0;
-//!     // `x` is live here ...
-//!     GLOBAL = &x: *const u32;
-//!     // ... but not here, even while it can be accessed through `GLOBAL`.
-//!     foo();
-//!     x = 1;
-//!     // `x` is live again here, because it is assigned to `OTHER_GLOBAL`.
-//!     OTHER_GLOBAL = &x: *const u32;
-//!     // ...
-//! }
-//! ```
-//!
-//! This means that users of this analysis still have to check whether
-//! pre-existing references can be used to access the value (e.g., at movable
-//! generator yield points, all pre-existing references are invalidated, so this
-//! doesn't matter).
-
-use crate::transform::MirSource;
-use crate::util::pretty::{dump_enabled, write_basic_block, write_mir_intro};
-use rustc_data_structures::work_queue::WorkQueue;
-use rustc_index::bit_set::BitSet;
-use rustc_index::vec::{Idx, IndexVec};
-use rustc_middle::mir::visit::{
-    MutatingUseContext, NonMutatingUseContext, NonUseContext, PlaceContext, Visitor,
-};
-use rustc_middle::mir::Local;
-use rustc_middle::mir::*;
-use rustc_middle::ty::{self, TyCtxt};
-use std::fs;
-use std::io::{self, BufWriter, Write};
-use std::path::{Path, PathBuf};
-
-pub type LiveVarSet = BitSet<Local>;
-
-/// This gives the result of the liveness analysis at the boundary of
-/// basic blocks.
-///
-/// The `V` type defines the set of variables that we computed
-/// liveness for. This is often `Local`, in which case we computed
-/// liveness for all variables -- but it can also be some other type,
-/// which indicates a subset of the variables within the graph.
-pub struct LivenessResult {
-    /// Live variables on exit to each basic block. This is equal to
-    /// the union of the `ins` for each successor.
-    pub outs: IndexVec<BasicBlock, LiveVarSet>,
-}
-
-/// Computes which local variables are live within the given function
-/// `mir`, including drops.
-pub fn liveness_of_locals(body: &Body<'_>) -> LivenessResult {
-    let num_live_vars = body.local_decls.len();
-
-    let def_use: IndexVec<_, DefsUses> =
-        body.basic_blocks().iter().map(|b| block(b, num_live_vars)).collect();
-
-    let mut outs: IndexVec<_, LiveVarSet> =
-        body.basic_blocks().indices().map(|_| LiveVarSet::new_empty(num_live_vars)).collect();
-
-    let mut bits = LiveVarSet::new_empty(num_live_vars);
-
-    // The dirty queue contains the set of basic blocks whose entry sets have changed since they
-    // were last processed. At the start of the analysis, we initialize the queue in post-order to
-    // make it more likely that the entry set for a given basic block will have the effects of all
-    // its successors in the CFG applied before it is processed.
-    //
-    // FIXME(ecstaticmorse): Reverse post-order on the reverse CFG may generate a better iteration
-    // order when cycles are present, but the overhead of computing the reverse CFG may outweigh
-    // any benefits. Benchmark this and find out.
-    let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_none(body.basic_blocks().len());
-    for (bb, _) in traversal::postorder(&body) {
-        dirty_queue.insert(bb);
-    }
-
-    // Add blocks which are not reachable from START_BLOCK to the work queue. These blocks will
-    // be processed after the ones added above.
-    for bb in body.basic_blocks().indices() {
-        dirty_queue.insert(bb);
-    }
-
-    let predecessors = body.predecessors();
-
-    while let Some(bb) = dirty_queue.pop() {
-        // bits = use ∪ (bits - def)
-        bits.overwrite(&outs[bb]);
-        def_use[bb].apply(&mut bits);
-
-        // `bits` now contains the live variables on entry. Therefore,
-        // add `bits` to the `out` set for each predecessor; if those
-        // bits were not already present, then enqueue the predecessor
-        // as dirty.
-        //
-        // (note that `union` returns true if the `self` set changed)
-        for &pred_bb in &predecessors[bb] {
-            if outs[pred_bb].union(&bits) {
-                dirty_queue.insert(pred_bb);
-            }
-        }
-    }
-
-    LivenessResult { outs }
-}
-
-#[derive(Eq, PartialEq, Clone)]
-pub enum DefUse {
-    Def,
-    Use,
-    Drop,
-}
-
-pub fn categorize(context: PlaceContext) -> Option<DefUse> {
-    match context {
-        ///////////////////////////////////////////////////////////////////////////
-        // DEFS
-
-        PlaceContext::MutatingUse(MutatingUseContext::Store) |
-
-        // This is potentially both a def and a use...
-        PlaceContext::MutatingUse(MutatingUseContext::AsmOutput) |
-
-        // We let Call define the result in both the success and
-        // unwind cases. This is not really correct, however it
-        // does not seem to be observable due to the way that we
-        // generate MIR. To do things properly, we would apply
-        // 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.
-        PlaceContext::NonUse(NonUseContext::StorageLive) |
-        PlaceContext::NonUse(NonUseContext::StorageDead) => Some(DefUse::Def),
-
-        ///////////////////////////////////////////////////////////////////////////
-        // REGULAR USES
-        //
-        // These are uses that occur *outside* of a drop. For the
-        // purposes of NLL, these are special in that **all** the
-        // lifetimes appearing in the variable must be live for each regular use.
-
-        PlaceContext::NonMutatingUse(NonMutatingUseContext::Projection) |
-        PlaceContext::MutatingUse(MutatingUseContext::Projection) |
-
-        // Borrows only consider their local used at the point of the borrow.
-        // This won't affect the results since we use this analysis for generators
-        // and we only care about the result at suspension points. Borrows cannot
-        // cross suspension points so this behavior is unproblematic.
-        PlaceContext::MutatingUse(MutatingUseContext::Borrow) |
-        PlaceContext::NonMutatingUse(NonMutatingUseContext::SharedBorrow) |
-        PlaceContext::NonMutatingUse(NonMutatingUseContext::ShallowBorrow) |
-        PlaceContext::NonMutatingUse(NonMutatingUseContext::UniqueBorrow) |
-
-        PlaceContext::MutatingUse(MutatingUseContext::AddressOf) |
-        PlaceContext::NonMutatingUse(NonMutatingUseContext::AddressOf) |
-        PlaceContext::NonMutatingUse(NonMutatingUseContext::Inspect) |
-        PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) |
-        PlaceContext::NonMutatingUse(NonMutatingUseContext::Move) |
-        PlaceContext::NonUse(NonUseContext::AscribeUserTy) |
-        PlaceContext::MutatingUse(MutatingUseContext::Retag) =>
-            Some(DefUse::Use),
-
-        ///////////////////////////////////////////////////////////////////////////
-        // DROP USES
-        //
-        // These are uses that occur in a DROP (a MIR drop, not a
-        // call to `std::mem::drop()`). For the purposes of NLL,
-        // uses in drop are special because `#[may_dangle]`
-        // attributes can affect whether lifetimes must be live.
-
-        PlaceContext::MutatingUse(MutatingUseContext::Drop) =>
-            Some(DefUse::Drop),
-
-        // Debug info is neither def nor use.
-        PlaceContext::NonUse(NonUseContext::VarDebugInfo) => None,
-    }
-}
-
-struct DefsUsesVisitor {
-    defs_uses: DefsUses,
-}
-
-#[derive(Eq, PartialEq, Clone)]
-struct DefsUses {
-    defs: LiveVarSet,
-    uses: LiveVarSet,
-}
-
-impl DefsUses {
-    fn apply(&self, bits: &mut LiveVarSet) -> bool {
-        bits.subtract(&self.defs) | bits.union(&self.uses)
-    }
-
-    fn add_def(&mut self, index: Local) {
-        // If it was used already in the block, remove that use
-        // now that we found a definition.
-        //
-        // Example:
-        //
-        //     // Defs = {X}, Uses = {}
-        //     X = 5
-        //     // Defs = {}, Uses = {X}
-        //     use(X)
-        self.uses.remove(index);
-        self.defs.insert(index);
-    }
-
-    fn add_use(&mut self, index: Local) {
-        // Inverse of above.
-        //
-        // Example:
-        //
-        //     // Defs = {}, Uses = {X}
-        //     use(X)
-        //     // Defs = {X}, Uses = {}
-        //     X = 5
-        //     // Defs = {}, Uses = {X}
-        //     use(X)
-        self.defs.remove(index);
-        self.uses.insert(index);
-    }
-}
-
-impl<'tcx> Visitor<'tcx> for DefsUsesVisitor {
-    fn visit_local(&mut self, &local: &Local, context: PlaceContext, _: Location) {
-        match categorize(context) {
-            Some(DefUse::Def) => self.defs_uses.add_def(local),
-            Some(DefUse::Use | DefUse::Drop) => self.defs_uses.add_use(local),
-            _ => (),
-        }
-    }
-}
-
-fn block(b: &BasicBlockData<'_>, locals: usize) -> DefsUses {
-    let mut visitor = DefsUsesVisitor {
-        defs_uses: DefsUses {
-            defs: LiveVarSet::new_empty(locals),
-            uses: LiveVarSet::new_empty(locals),
-        },
-    };
-
-    let dummy_location = Location { block: BasicBlock::new(0), statement_index: 0 };
-
-    // Visit the various parts of the basic block in reverse. If we go
-    // forward, the logic in `add_def` and `add_use` would be wrong.
-    visitor.visit_terminator(b.terminator(), dummy_location);
-    for statement in b.statements.iter().rev() {
-        visitor.visit_statement(statement, dummy_location);
-    }
-
-    visitor.defs_uses
-}
-
-pub fn dump_mir<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    pass_name: &str,
-    source: MirSource<'tcx>,
-    body: &Body<'tcx>,
-    result: &LivenessResult,
-) {
-    if !dump_enabled(tcx, pass_name, source.def_id()) {
-        return;
-    }
-    let node_path = ty::print::with_forced_impl_filename_line(|| {
-        // see notes on #41697 below
-        tcx.def_path_str(source.def_id())
-    });
-    dump_matched_mir_node(tcx, pass_name, &node_path, source, body, result);
-}
-
-fn dump_matched_mir_node<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    pass_name: &str,
-    node_path: &str,
-    source: MirSource<'tcx>,
-    body: &Body<'tcx>,
-    result: &LivenessResult,
-) {
-    let mut file_path = PathBuf::new();
-    file_path.push(Path::new(&tcx.sess.opts.debugging_opts.dump_mir_dir));
-    let item_id = tcx.hir().as_local_hir_id(source.def_id().expect_local());
-    let file_name = format!("rustc.node{}{}-liveness.mir", item_id, pass_name);
-    file_path.push(&file_name);
-    let _ = fs::File::create(&file_path).and_then(|file| {
-        let mut file = BufWriter::new(file);
-        writeln!(file, "// MIR local liveness analysis for `{}`", node_path)?;
-        writeln!(file, "// source = {:?}", source)?;
-        writeln!(file, "// pass_name = {}", pass_name)?;
-        writeln!(file)?;
-        write_mir_fn(tcx, source, body, &mut file, result)?;
-        Ok(())
-    });
-}
-
-pub fn write_mir_fn<'tcx>(
-    tcx: TyCtxt<'tcx>,
-    src: MirSource<'tcx>,
-    body: &Body<'tcx>,
-    w: &mut dyn Write,
-    result: &LivenessResult,
-) -> io::Result<()> {
-    write_mir_intro(tcx, src, body, w)?;
-    for block in body.basic_blocks().indices() {
-        let print = |w: &mut dyn Write, prefix, result: &IndexVec<BasicBlock, LiveVarSet>| {
-            let live: Vec<String> =
-                result[block].iter().map(|local| format!("{:?}", local)).collect();
-            writeln!(w, "{} {{{}}}", prefix, live.join(", "))
-        };
-        write_basic_block(tcx, block, body, &mut |_, _| Ok(()), w)?;
-        print(w, "   ", &result.outs)?;
-        if block.index() + 1 != body.basic_blocks().len() {
-            writeln!(w)?;
-        }
-    }
-
-    writeln!(w, "}}")?;
-    Ok(())
-}
diff --git a/src/librustc_mir/util/mod.rs b/src/librustc_mir/util/mod.rs
index 3e501193e8d..8bbe207c077 100644
--- a/src/librustc_mir/util/mod.rs
+++ b/src/librustc_mir/util/mod.rs
@@ -8,7 +8,6 @@ pub mod storage;
 mod alignment;
 pub mod collect_writes;
 mod graphviz;
-pub mod liveness;
 pub(crate) mod pretty;
 
 pub use self::aggregate::expand_aggregate;