Auto merge of #51660 - lqd:the-MIRnistry-of-walks, r=nikomatsakis

NLL: Walk the MIR only once for the "unused mut" lint

Turns the quadratic loop gathering local variable assignments into a single MIR walk, and brings down the number of `super_mir` calls generated from `do_mir_borrowck` to the expected levels seen in `nll::replace_regions_in_mir` and `nll::compute_regions`, i.e. on clap: 1883 `super_mir` calls instead of 8011.

The limited perf numbers I could gather on my machines look to be what we expected: `clap-check` seems to be gaining back a lot of the 7% we previously saw in `visit_mir`.

Fixes #51641.

r? @nikomatsakis

3 files changed, 84 insertions, 33 deletions

diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs
index 3d3275a6b17..115f36c149b 100644
--- a/src/librustc_mir/borrow_check/mod.rs
+++ b/src/librustc_mir/borrow_check/mod.rs
@@ -61,6 +61,7 @@ mod location;
 crate mod place_ext;
 mod prefixes;
 mod path_utils;
+mod used_muts;
 
 pub(crate) mod nll;
 
@@ -281,20 +282,7 @@ fn do_mir_borrowck<'a, 'gcx, 'tcx>(
             .filter(|&local| !mbcx.mir.local_decls[*local].is_user_variable.is_some())
             .cloned()
             .collect();
-
-    for local in temporary_used_locals {
-        for location in mbcx.mir.find_assignments(local) {
-            for moi in &mbcx.move_data.loc_map[location] {
-                let mpi = &mbcx.move_data.moves[*moi].path;
-                let path = &mbcx.move_data.move_paths[*mpi];
-                debug!("assignment of {:?} to {:?}, adding {:?} to used mutable set",
-                       path.place, local, path.place);
-                if let Place::Local(user_local) = path.place {
-                    mbcx.used_mut.insert(user_local);
-                }
-            }
-        }
-    }
+    mbcx.gather_used_muts(temporary_used_locals);
 
     debug!("mbcx.used_mut: {:?}", mbcx.used_mut);
 
diff --git a/src/librustc_mir/borrow_check/used_muts.rs b/src/librustc_mir/borrow_check/used_muts.rs
new file mode 100644
index 00000000000..dbe19bc4785
--- /dev/null
+++ b/src/librustc_mir/borrow_check/used_muts.rs
@@ -0,0 +1,64 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use rustc::mir::visit::{PlaceContext, Visitor};
+use rustc::mir::{Local, Location, Place};
+
+use rustc_data_structures::fx::FxHashSet;
+
+use borrow_check::MirBorrowckCtxt;
+use util::collect_writes::is_place_assignment;
+
+impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
+    /// Walks the MIR looking for assignments to a set of locals, as part of the unused mutable
+    /// local variables lint, to update the context's `used_mut` in a single walk.
+    crate fn gather_used_muts(&mut self, locals: FxHashSet<Local>) {
+        let mut visitor = GatherUsedMutsVisitor {
+            needles: locals,
+            mbcx: self,
+        };
+        visitor.visit_mir(visitor.mbcx.mir);
+    }
+}
+
+/// MIR visitor gathering the assignments to a set of locals, in a single walk.
+/// 'visit = the duration of the MIR walk
+struct GatherUsedMutsVisitor<'visit, 'cx: 'visit, 'gcx: 'tcx, 'tcx: 'cx> {
+    needles: FxHashSet<Local>,
+    mbcx: &'visit mut MirBorrowckCtxt<'cx, 'gcx, 'tcx>,
+}
+
+impl<'visit, 'cx, 'gcx, 'tcx> Visitor<'tcx> for GatherUsedMutsVisitor<'visit, 'cx, 'gcx, 'tcx> {
+    fn visit_local(
+        &mut self,
+        local: &Local,
+        place_context: PlaceContext<'tcx>,
+        location: Location,
+    ) {
+        if !self.needles.contains(local) {
+            return;
+        }
+
+        if is_place_assignment(&place_context) {
+            // Propagate the Local assigned at this Location as a used mutable local variable
+            for moi in &self.mbcx.move_data.loc_map[location] {
+                let mpi = &self.mbcx.move_data.moves[*moi].path;
+                let path = &self.mbcx.move_data.move_paths[*mpi];
+                debug!(
+                    "assignment of {:?} to {:?}, adding {:?} to used mutable set",
+                    path.place, local, path.place
+                );
+                if let Place::Local(user_local) = path.place {
+                    self.mbcx.used_mut.insert(user_local);
+                }
+            }
+        }
+    }
+}
diff --git a/src/librustc_mir/util/collect_writes.rs b/src/librustc_mir/util/collect_writes.rs
index f04f9233447..23f753f8569 100644
--- a/src/librustc_mir/util/collect_writes.rs
+++ b/src/librustc_mir/util/collect_writes.rs
@@ -43,25 +43,24 @@ impl<'tcx> Visitor<'tcx> for FindLocalAssignmentVisitor {
             return;
         }
 
-        match place_context {
-            PlaceContext::Store | PlaceContext::Call => {
-                self.locations.push(location);
-            }
-            PlaceContext::AsmOutput |
-            PlaceContext::Drop |
-            PlaceContext::Inspect |
-            PlaceContext::Borrow { .. } |
-            PlaceContext::Projection(..) |
-            PlaceContext::Copy |
-            PlaceContext::Move |
-            PlaceContext::StorageLive |
-            PlaceContext::StorageDead |
-            PlaceContext::Validate => {
-                // TO-DO
-                // self.super_local(local)
-            }
+        if is_place_assignment(&place_context) {
+            self.locations.push(location);
         }
     }
-    // TO-DO
-    // fn super_local()
+}
+
+/// Returns true if this place context represents an assignment statement
+crate fn is_place_assignment(place_context: &PlaceContext) -> bool {
+    match *place_context {
+        PlaceContext::Store | PlaceContext::Call | PlaceContext::AsmOutput => true,
+        PlaceContext::Drop
+        | PlaceContext::Inspect
+        | PlaceContext::Borrow { .. }
+        | PlaceContext::Projection(..)
+        | PlaceContext::Copy
+        | PlaceContext::Move
+        | PlaceContext::StorageLive
+        | PlaceContext::StorageDead
+        | PlaceContext::Validate => false,
+    }
 }