Auto merge of #51896 - nikomatsakis:nll-liveness-dirty-list, r=Zoxc

introduce dirty list to liveness, eliminate `ins` vector

At least in my measurements, this seems to knock much of the liveness computation off the profile.

r? @Zoxc
cc @nnethercote

10 files changed, 120 insertions, 39 deletions

diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs
index 30b87c0390a..2e95a45479c 100644
--- a/src/librustc_data_structures/indexed_set.rs
+++ b/src/librustc_data_structures/indexed_set.rs
@@ -239,14 +239,20 @@ impl<T: Idx> IdxSet<T> {
         self.words_mut().clone_from_slice(other.words());
     }
 
+    /// Set `self = self | other` and return true if `self` changed
+    /// (i.e., if new bits were added).
     pub fn union(&mut self, other: &IdxSet<T>) -> bool {
         bitwise(self.words_mut(), other.words(), &Union)
     }
 
+    /// Set `self = self - other` and return true if `self` changed.
+    /// (i.e., if any bits were removed).
     pub fn subtract(&mut self, other: &IdxSet<T>) -> bool {
         bitwise(self.words_mut(), other.words(), &Subtract)
     }
 
+    /// Set `self = self & other` and return true if `self` changed.
+    /// (i.e., if any bits were removed).
     pub fn intersect(&mut self, other: &IdxSet<T>) -> bool {
         bitwise(self.words_mut(), other.words(), &Intersect)
     }
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 5844edf000a..e4d0bc596cb 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -77,6 +77,7 @@ pub mod sync;
 pub mod owning_ref;
 pub mod tiny_list;
 pub mod sorted_map;
+pub mod work_queue;
 
 pub struct OnDrop<F: Fn()>(pub F);
 
diff --git a/src/librustc_data_structures/work_queue.rs b/src/librustc_data_structures/work_queue.rs
new file mode 100644
index 00000000000..b8e8b249bb5
--- /dev/null
+++ b/src/librustc_data_structures/work_queue.rs
@@ -0,0 +1,72 @@
+// Copyright 2016 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 indexed_set::IdxSetBuf;
+use indexed_vec::Idx;
+use std::collections::VecDeque;
+
+/// A work queue is a handy data structure for tracking work left to
+/// do. (For example, basic blocks left to process.) It is basically a
+/// de-duplicating queue; so attempting to insert X if X is already
+/// enqueued has no effect. This implementation assumes that the
+/// elements are dense indices, so it can allocate the queue to size
+/// and also use a bit set to track occupancy.
+pub struct WorkQueue<T: Idx> {
+    deque: VecDeque<T>,
+    set: IdxSetBuf<T>,
+}
+
+impl<T: Idx> WorkQueue<T> {
+    /// Create a new work queue with all the elements from (0..len).
+    #[inline]
+    pub fn with_all(len: usize) -> Self {
+        WorkQueue {
+            deque: (0..len).map(T::new).collect(),
+            set: IdxSetBuf::new_filled(len),
+        }
+    }
+
+    /// Create a new work queue that starts empty, where elements range from (0..len).
+    #[inline]
+    pub fn with_none(len: usize) -> Self {
+        WorkQueue {
+            deque: VecDeque::with_capacity(len),
+            set: IdxSetBuf::new_empty(len),
+        }
+    }
+
+    /// Attempt to enqueue `element` in the work queue. Returns false if it was already present.
+    #[inline]
+    pub fn insert(&mut self, element: T) -> bool {
+        if self.set.add(&element) {
+            self.deque.push_back(element);
+            true
+        } else {
+            false
+        }
+    }
+
+    /// Attempt to enqueue `element` in the work queue. Returns false if it was already present.
+    #[inline]
+    pub fn pop(&mut self) -> Option<T> {
+        if let Some(element) = self.deque.pop_front() {
+            self.set.remove(&element);
+            Some(element)
+        } else {
+            None
+        }
+    }
+
+    /// True if nothing is enqueued.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.deque.is_empty()
+    }
+}
diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs
index 07b160ed66f..16506800c9e 100644
--- a/src/librustc_mir/borrow_check/nll/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/mod.rs
@@ -263,13 +263,6 @@ fn dump_mir_results<'a, 'gcx, 'tcx>(
                     }
                 }
 
-                // Before each basic block, dump out the values
-                // that are live on entry to the basic block.
-                PassWhere::BeforeBlock(bb) => {
-                    let s = live_variable_set(&liveness.regular.ins[bb], &liveness.drop.ins[bb]);
-                    writeln!(out, "    | Live variables on entry to {:?}: {}", bb, s)?;
-                }
-
                 PassWhere::BeforeLocation(location) => {
                     let s = live_variable_set(
                         &regular_liveness_per_location[&location],
@@ -285,7 +278,14 @@ fn dump_mir_results<'a, 'gcx, 'tcx>(
                     )?;
                 }
 
-                PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
+                // After each basic block, dump out the values
+                // that are live on exit from the basic block.
+                PassWhere::AfterTerminator(bb) => {
+                    let s = live_variable_set(&liveness.regular.outs[bb], &liveness.drop.outs[bb]);
+                    writeln!(out, "    | Live variables on exit from {:?}: {}", bb, s)?;
+                }
+
+                PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
             }
             Ok(())
         },
diff --git a/src/librustc_mir/util/liveness.rs b/src/librustc_mir/util/liveness.rs
index 34f8141141d..4630cdae47d 100644
--- a/src/librustc_mir/util/liveness.rs
+++ b/src/librustc_mir/util/liveness.rs
@@ -37,6 +37,7 @@ use rustc::mir::*;
 use rustc::mir::visit::{PlaceContext, Visitor};
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
 use rustc_data_structures::indexed_set::IdxSetBuf;
+use rustc_data_structures::work_queue::WorkQueue;
 use util::pretty::{dump_enabled, write_basic_block, write_mir_intro};
 use rustc::ty::item_path;
 use rustc::mir::visit::MirVisitable;
@@ -55,9 +56,6 @@ pub struct LivenessResult {
     /// Liveness mode in use when these results were computed.
     pub mode: LivenessMode,
 
-    /// Live variables on entry to each basic block.
-    pub ins: IndexVec<BasicBlock, LocalSet>,
-
     /// Live variables on exit to each basic block. This is equal to
     /// the union of the `ins` for each successor.
     pub outs: IndexVec<BasicBlock, LocalSet>,
@@ -124,37 +122,38 @@ pub fn liveness_of_locals<'tcx>(mir: &Mir<'tcx>, mode: LivenessMode) -> Liveness
         .map(|b| block(mode, b, locals))
         .collect();
 
-    let mut ins: IndexVec<_, _> = mir.basic_blocks()
+    let mut outs: IndexVec<_, _> = mir.basic_blocks()
         .indices()
         .map(|_| LocalSet::new_empty(locals))
         .collect();
-    let mut outs = ins.clone();
 
-    let mut changed = true;
     let mut bits = LocalSet::new_empty(locals);
-    while changed {
-        changed = false;
-
-        for b in mir.basic_blocks().indices().rev() {
-            // outs[b] = ∪ {ins of successors}
-            bits.clear();
-            for &successor in mir.basic_blocks()[b].terminator().successors() {
-                bits.union(&ins[successor]);
-            }
-            outs[b].overwrite(&bits);
 
-            // bits = use ∪ (bits - def)
-            def_use[b].apply(&mut bits);
+    // queue of things that need to be re-processed, and a set containing
+    // the things currently in the queue
+    let mut dirty_queue: WorkQueue<BasicBlock> = WorkQueue::with_all(mir.basic_blocks().len());
+
+    let predecessors = mir.predecessors();
 
-            // update bits on entry and flag if they have changed
-            if ins[b] != bits {
-                ins[b].overwrite(&bits);
-                changed = true;
+    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 { mode, ins, outs }
+    LivenessResult { mode, outs }
 }
 
 impl LivenessResult {
@@ -195,8 +194,6 @@ impl LivenessResult {
             statement_defs_uses.apply(&mut bits);
             callback(statement_location, &bits);
         }
-
-        assert_eq!(bits, self.ins[block]);
     }
 
     fn defs_uses<'tcx, V>(&self, mir: &Mir<'tcx>, location: Location, thing: &V) -> DefsUses
@@ -438,7 +435,6 @@ pub fn write_mir_fn<'a, 'tcx>(
                 .collect();
             writeln!(w, "{} {{{}}}", prefix, live.join(", "))
         };
-        print(w, "   ", &result.ins)?;
         write_basic_block(tcx, block, mir, &mut |_, _| Ok(()), w)?;
         print(w, "   ", &result.outs)?;
         if block.index() + 1 != mir.basic_blocks().len() {
diff --git a/src/librustc_mir/util/pretty.rs b/src/librustc_mir/util/pretty.rs
index 8176c644dd7..6472e588bc6 100644
--- a/src/librustc_mir/util/pretty.rs
+++ b/src/librustc_mir/util/pretty.rs
@@ -44,6 +44,9 @@ pub enum PassWhere {
 
     /// We just dumped the given statement or terminator.
     AfterLocation(Location),
+
+    /// We just dumped the terminator for a block but not the closing `}`.
+    AfterTerminator(BasicBlock),
 }
 
 /// If the session is properly configured, dumps a human-readable
@@ -351,6 +354,7 @@ where
     })?;
 
     extra_data(PassWhere::AfterLocation(current_location), w)?;
+    extra_data(PassWhere::AfterTerminator(block), w)?;
 
     writeln!(w, "{}}}", INDENT)
 }
diff --git a/src/test/mir-opt/nll/liveness-call-subtlety.rs b/src/test/mir-opt/nll/liveness-call-subtlety.rs
index f41b39845a5..5fdea4208df 100644
--- a/src/test/mir-opt/nll/liveness-call-subtlety.rs
+++ b/src/test/mir-opt/nll/liveness-call-subtlety.rs
@@ -26,20 +26,20 @@ fn main() {
 //
 // END RUST SOURCE
 // START rustc.main.nll.0.mir
-//    | Live variables on entry to bb0: []
 //    bb0: {
 //            | Live variables on entry to bb0[0]: []
 //        StorageLive(_1);
 //            | Live variables on entry to bb0[1]: []
 //        _1 = const <std::boxed::Box<T>>::new(const 22usize) -> [return: bb2, unwind: bb1];
+//            | Live variables on exit from bb0: [_1 (drop)]
 //    }
 // END rustc.main.nll.0.mir
 // START rustc.main.nll.0.mir
-//    | Live variables on entry to bb2: [_1 (drop)]
 //    bb2: {
 //            | Live variables on entry to bb2[0]: [_1 (drop)]
 //        StorageLive(_2);
 //            | Live variables on entry to bb2[1]: [_1 (drop)]
 //        _2 = const can_panic() -> [return: bb3, unwind: bb4];
+//            | Live variables on exit from bb2: [_1 (drop), _2]
 //    }
 // END rustc.main.nll.0.mir
diff --git a/src/test/mir-opt/nll/liveness-drop-intra-block.rs b/src/test/mir-opt/nll/liveness-drop-intra-block.rs
index 073b44d6e33..001499b657d 100644
--- a/src/test/mir-opt/nll/liveness-drop-intra-block.rs
+++ b/src/test/mir-opt/nll/liveness-drop-intra-block.rs
@@ -25,7 +25,6 @@ fn main() {
 
 // END RUST SOURCE
 // START rustc.main.nll.0.mir
-//    | Live variables on entry to bb3: []
 //    bb3: {
 //            | Live variables on entry to bb3[0]: []
 //        _1 = const 55usize;
@@ -37,5 +36,6 @@ fn main() {
 //        _4 = _1;
 //            | Live variables on entry to bb3[4]: [_4]
 //        _3 = const use_x(move _4) -> [return: bb4, unwind: bb1];
+//            | Live variables on exit from bb3: [_3]
 //    }
 // END rustc.main.nll.0.mir
diff --git a/src/test/mir-opt/nll/liveness-interblock.rs b/src/test/mir-opt/nll/liveness-interblock.rs
index 6a874908406..fbe20d76ea7 100644
--- a/src/test/mir-opt/nll/liveness-interblock.rs
+++ b/src/test/mir-opt/nll/liveness-interblock.rs
@@ -29,7 +29,6 @@ fn main() {
 
 // END RUST SOURCE
 // START rustc.main.nll.0.mir
-//     | Live variables on entry to bb3: [_1]
 //     bb3: {
 //             | Live variables on entry to bb3[0]: [_1]
 //         StorageLive(_4);
@@ -37,12 +36,13 @@ fn main() {
 //         _4 = _1;
 //             | Live variables on entry to bb3[2]: [_4]
 //         _3 = const make_live(move _4) -> [return: bb5, unwind: bb1];
+//             | Live variables on exit from bb3: []
 //     }
 // END rustc.main.nll.0.mir
 // START rustc.main.nll.0.mir
-//     | Live variables on entry to bb4: []
 //     bb4: {
 //             | Live variables on entry to bb4[0]: []
 //         _5 = const make_dead() -> [return: bb6, unwind: bb1];
+//             | Live variables on exit from bb4: []
 //     }
 // END rustc.main.nll.0.mir
diff --git a/src/test/mir-opt/nll/region-liveness-basic.rs b/src/test/mir-opt/nll/region-liveness-basic.rs
index 75d8a6a4f6a..187d9e6ca89 100644
--- a/src/test/mir-opt/nll/region-liveness-basic.rs
+++ b/src/test/mir-opt/nll/region-liveness-basic.rs
@@ -42,6 +42,7 @@ fn main() {
 //        _2 = &'_#2r _1[_3];
 //            | Live variables on entry to bb2[1]: [_2]
 //        switchInt(const true) -> [false: bb4, otherwise: bb3];
+//            | Live variables on exit from bb2: [_2]
 //    }
 // END rustc.main.nll.0.mir
 // START rustc.main.nll.0.mir
@@ -52,5 +53,6 @@ fn main() {
 //        _7 = (*_2);
 //            | Live variables on entry to bb3[2]: [_7]
 //        _6 = const use_x(move _7) -> [return: bb5, unwind: bb1];
+//            | Live variables on exit from bb3: []
 //    }
 // END rustc.main.nll.0.mir