Merge branch 'master' into feature/core_convert_id

47 files changed, 4041 insertions, 2313 deletions

diff --git a/src/librustc_data_structures/Cargo.toml b/src/librustc_data_structures/Cargo.toml
index 23e42f6a672..fc5fe91c977 100644
--- a/src/librustc_data_structures/Cargo.toml
+++ b/src/librustc_data_structures/Cargo.toml
@@ -9,11 +9,16 @@ path = "lib.rs"
 crate-type = ["dylib"]
 
 [dependencies]
+ena = "0.9.3"
 log = "0.4"
+rustc_cratesio_shim = { path = "../librustc_cratesio_shim" }
 serialize = { path = "../libserialize" }
 cfg-if = "0.1.2"
 stable_deref_trait = "1.0.0"
 parking_lot_core = "0.2.8"
+rustc-rayon = "0.1.1"
+rustc-rayon-core = "0.1.1"
+rustc-hash = "1.0.1"
 
 [dependencies.parking_lot]
 version = "0.5"
diff --git a/src/librustc_data_structures/accumulate_vec.rs b/src/librustc_data_structures/accumulate_vec.rs
index 52306de74cb..9423e6b3256 100644
--- a/src/librustc_data_structures/accumulate_vec.rs
+++ b/src/librustc_data_structures/accumulate_vec.rs
@@ -15,11 +15,10 @@
 //!
 //! The N above is determined by Array's implementor, by way of an associated constant.
 
-use std::ops::{Deref, DerefMut};
+use std::ops::{Deref, DerefMut, RangeBounds};
 use std::iter::{self, IntoIterator, FromIterator};
 use std::slice;
 use std::vec;
-use std::collections::range::RangeArgument;
 
 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
 
@@ -47,6 +46,13 @@ impl<A: Array> AccumulateVec<A> {
         AccumulateVec::Array(ArrayVec::new())
     }
 
+    pub fn is_array(&self) -> bool {
+        match self {
+            AccumulateVec::Array(..) => true,
+            AccumulateVec::Heap(..) => false,
+        }
+    }
+
     pub fn one(el: A::Element) -> Self {
         iter::once(el).collect()
     }
@@ -74,7 +80,7 @@ impl<A: Array> AccumulateVec<A> {
     }
 
     pub fn drain<R>(&mut self, range: R) -> Drain<A>
-        where R: RangeArgument<usize>
+        where R: RangeBounds<usize>
     {
         match *self {
             AccumulateVec::Array(ref mut v) => {
@@ -218,7 +224,7 @@ impl<A> Encodable for AccumulateVec<A>
     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
         s.emit_seq(self.len(), |s| {
             for (i, e) in self.iter().enumerate() {
-                try!(s.emit_seq_elt(i, |s| e.encode(s)));
+                s.emit_seq_elt(i, |s| e.encode(s))?;
             }
             Ok(())
         })
@@ -230,8 +236,7 @@ impl<A> Decodable for AccumulateVec<A>
           A::Element: Decodable {
     fn decode<D: Decoder>(d: &mut D) -> Result<AccumulateVec<A>, D::Error> {
         d.read_seq(|d, len| {
-            Ok(try!((0..len).map(|i| d.read_seq_elt(i, |d| Decodable::decode(d))).collect()))
+            (0..len).map(|i| d.read_seq_elt(i, |d| Decodable::decode(d))).collect()
         })
     }
 }
-
diff --git a/src/librustc_data_structures/array_vec.rs b/src/librustc_data_structures/array_vec.rs
index 57fc78ef531..56bb9613242 100644
--- a/src/librustc_data_structures/array_vec.rs
+++ b/src/librustc_data_structures/array_vec.rs
@@ -12,15 +12,15 @@
 
 use std::marker::Unsize;
 use std::iter::Extend;
-use std::ptr::{self, drop_in_place, Shared};
+use std::ptr::{self, drop_in_place, NonNull};
 use std::ops::{Deref, DerefMut, Range};
 use std::hash::{Hash, Hasher};
 use std::slice;
 use std::fmt;
 use std::mem;
-use std::collections::range::RangeArgument;
-use std::collections::Bound::{Excluded, Included, Unbounded};
 use std::mem::ManuallyDrop;
+use std::ops::Bound::{Excluded, Included, Unbounded};
+use std::ops::RangeBounds;
 
 pub unsafe trait Array {
     type Element;
@@ -106,7 +106,7 @@ impl<A: Array> ArrayVec<A> {
     }
 
     pub fn drain<R>(&mut self, range: R) -> Drain<A>
-        where R: RangeArgument<usize>
+        where R: RangeBounds<usize>
     {
         // Memory safety
         //
@@ -119,12 +119,12 @@ impl<A: Array> ArrayVec<A> {
         // the hole, and the vector length is restored to the new length.
         //
         let len = self.len();
-        let start = match range.start() {
+        let start = match range.start_bound() {
             Included(&n) => n,
             Excluded(&n) => n + 1,
             Unbounded    => 0,
         };
-        let end = match range.end() {
+        let end = match range.end_bound() {
             Included(&n) => n + 1,
             Excluded(&n) => n,
             Unbounded    => len,
@@ -146,7 +146,7 @@ impl<A: Array> ArrayVec<A> {
                 tail_start: end,
                 tail_len: len - end,
                 iter: range_slice.iter(),
-                array_vec: Shared::from(self),
+                array_vec: NonNull::from(self),
             }
         }
     }
@@ -207,7 +207,7 @@ pub struct Iter<A: Array> {
 
 impl<A: Array> Drop for Iter<A> {
     fn drop(&mut self) {
-        for _ in self {}
+        self.for_each(drop);
     }
 }
 
@@ -232,7 +232,7 @@ pub struct Drain<'a, A: Array>
     tail_start: usize,
     tail_len: usize,
     iter: slice::Iter<'a, ManuallyDrop<A::Element>>,
-    array_vec: Shared<ArrayVec<A>>,
+    array_vec: NonNull<ArrayVec<A>>,
 }
 
 impl<'a, A: Array> Iterator for Drain<'a, A> {
@@ -251,7 +251,7 @@ impl<'a, A: Array> Iterator for Drain<'a, A> {
 impl<'a, A: Array> Drop for Drain<'a, A> {
     fn drop(&mut self) {
         // exhaust self first
-        while let Some(_) = self.next() {}
+        self.for_each(drop);
 
         if self.tail_len > 0 {
             unsafe {
diff --git a/src/librustc_data_structures/base_n.rs b/src/librustc_data_structures/base_n.rs
index d333b6393b9..d3b47daa5b4 100644
--- a/src/librustc_data_structures/base_n.rs
+++ b/src/librustc_data_structures/base_n.rs
@@ -17,7 +17,7 @@ pub const MAX_BASE: usize = 64;
 pub const ALPHANUMERIC_ONLY: usize = 62;
 pub const CASE_INSENSITIVE: usize = 36;
 
-const BASE_64: &'static [u8; MAX_BASE as usize] =
+const BASE_64: &[u8; MAX_BASE as usize] =
     b"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ@$";
 
 #[inline]
@@ -37,7 +37,8 @@ pub fn push_str(mut n: u128, base: usize, output: &mut String) {
             break;
         }
     }
-    &mut s[0..index].reverse();
+    s[0..index].reverse();
+
     output.push_str(str::from_utf8(&s[0..index]).unwrap());
 }
 
diff --git a/src/librustc_data_structures/bitslice.rs b/src/librustc_data_structures/bitslice.rs
index 7665bfd5b11..a63033c4365 100644
--- a/src/librustc_data_structures/bitslice.rs
+++ b/src/librustc_data_structures/bitslice.rs
@@ -24,12 +24,13 @@ pub trait BitSlice {
 
 impl BitSlice for [Word] {
     /// Clears bit at `idx` to 0; returns true iff this changed `self.`
+    #[inline]
     fn clear_bit(&mut self, idx: usize) -> bool {
         let words = self;
         debug!("clear_bit: words={} idx={}",
-               bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx));
+               bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
         let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
-        debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
+        debug!("word={} bit_in_word={} bit_mask=0x{:x}", word, bit_in_word, bit_mask);
         let oldv = words[word];
         let newv = oldv & !bit_mask;
         words[word] = newv;
@@ -37,10 +38,11 @@ impl BitSlice for [Word] {
     }
 
     /// Sets bit at `idx` to 1; returns true iff this changed `self.`
+    #[inline]
     fn set_bit(&mut self, idx: usize) -> bool {
         let words = self;
         debug!("set_bit: words={} idx={}",
-               bits_to_string(words, words.len() * mem::size_of::<Word>()), bit_str(idx));
+               bits_to_string(words, words.len() * mem::size_of::<Word>() * 8), idx);
         let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
         debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
         let oldv = words[word];
@@ -50,6 +52,7 @@ impl BitSlice for [Word] {
     }
 
     /// Extracts value of bit at `idx` in `self`.
+    #[inline]
     fn get_bit(&self, idx: usize) -> bool {
         let words = self;
         let BitLookup { word, bit_mask, .. } = bit_lookup(idx);
@@ -72,14 +75,7 @@ fn bit_lookup(bit: usize) -> BitLookup {
     let word = bit / word_bits;
     let bit_in_word = bit % word_bits;
     let bit_mask = 1 << bit_in_word;
-    BitLookup { word: word, bit_in_word: bit_in_word, bit_mask: bit_mask }
-}
-
-
-fn bit_str(bit: Word) -> String {
-    let byte = bit >> 3;
-    let lobits = 1 << (bit & 0b111);
-    format!("[{}:{}-{:02x}]", bit, byte, lobits)
+    BitLookup { word, bit_in_word, bit_mask }
 }
 
 pub fn bits_to_string(words: &[Word], bits: usize) -> String {
@@ -92,29 +88,30 @@ pub fn bits_to_string(words: &[Word], bits: usize) -> String {
     let mut i = 0;
     for &word in words.iter() {
         let mut v = word;
-        loop { // for each byte in `v`:
+        for _ in 0..mem::size_of::<Word>() { // for each byte in `v`:
             let remain = bits - i;
             // If less than a byte remains, then mask just that many bits.
             let mask = if remain <= 8 { (1 << remain) - 1 } else { 0xFF };
             assert!(mask <= 0xFF);
             let byte = v & mask;
 
-            result.push(sep);
-            result.push_str(&format!("{:02x}", byte));
+            result.push_str(&format!("{}{:02x}", sep, byte));
 
             if remain <= 8 { break; }
             v >>= 8;
             i += 8;
             sep = '-';
         }
+        sep = '|';
     }
     result.push(']');
-    return result
+
+    result
 }
 
 #[inline]
-pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
-                                   in_vec: &[usize],
+pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [Word],
+                                   in_vec: &[Word],
                                    op: &Op) -> bool {
     assert_eq!(out_vec.len(), in_vec.len());
     let mut changed = false;
@@ -129,21 +126,21 @@ pub fn bitwise<Op:BitwiseOperator>(out_vec: &mut [usize],
 
 pub trait BitwiseOperator {
     /// Applies some bit-operation pointwise to each of the bits in the two inputs.
-    fn join(&self, pred1: usize, pred2: usize) -> usize;
+    fn join(&self, pred1: Word, pred2: Word) -> Word;
 }
 
 pub struct Intersect;
 impl BitwiseOperator for Intersect {
     #[inline]
-    fn join(&self, a: usize, b: usize) -> usize { a & b }
+    fn join(&self, a: Word, b: Word) -> Word { a & b }
 }
 pub struct Union;
 impl BitwiseOperator for Union {
     #[inline]
-    fn join(&self, a: usize, b: usize) -> usize { a | b }
+    fn join(&self, a: Word, b: Word) -> Word { a | b }
 }
 pub struct Subtract;
 impl BitwiseOperator for Subtract {
     #[inline]
-    fn join(&self, a: usize, b: usize) -> usize { a & !b }
+    fn join(&self, a: Word, b: Word) -> Word { a & !b }
 }
diff --git a/src/librustc_data_structures/bitvec.rs b/src/librustc_data_structures/bitvec.rs
index 94edaa746f9..49ab3e58812 100644
--- a/src/librustc_data_structures/bitvec.rs
+++ b/src/librustc_data_structures/bitvec.rs
@@ -8,19 +8,78 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::iter::FromIterator;
+use indexed_vec::{Idx, IndexVec};
+use std::marker::PhantomData;
 
-/// A very simple BitVector type.
+type Word = u128;
+const WORD_BITS: usize = 128;
+
+/// A very simple BitArray type.
+///
+/// It does not support resizing after creation; use `BitVector` for that.
 #[derive(Clone, Debug, PartialEq)]
-pub struct BitVector {
-    data: Vec<u64>,
+pub struct BitArray<C: Idx> {
+    data: Vec<Word>,
+    marker: PhantomData<C>,
 }
 
-impl BitVector {
+#[derive(Clone, Debug, PartialEq)]
+pub struct BitVector<C: Idx> {
+    data: BitArray<C>,
+}
+
+impl<C: Idx> BitVector<C> {
+    pub fn grow(&mut self, num_bits: C) {
+        self.data.grow(num_bits)
+    }
+
+    pub fn new() -> BitVector<C> {
+        BitVector {
+            data: BitArray::new(0),
+        }
+    }
+
+    pub fn with_capacity(bits: usize) -> BitVector<C> {
+        BitVector {
+            data: BitArray::new(bits),
+        }
+    }
+
+    /// Returns true if the bit has changed.
     #[inline]
-    pub fn new(num_bits: usize) -> BitVector {
-        let num_words = u64s(num_bits);
-        BitVector { data: vec![0; num_words] }
+    pub fn insert(&mut self, bit: C) -> bool {
+        self.grow(bit);
+        self.data.insert(bit)
+    }
+
+    #[inline]
+    pub fn contains(&self, bit: C) -> bool {
+        let (word, mask) = word_mask(bit);
+        if let Some(word) = self.data.data.get(word) {
+            (word & mask) != 0
+        } else {
+            false
+        }
+    }
+}
+
+impl<C: Idx> BitArray<C> {
+    // Do not make this method public, instead switch your use case to BitVector.
+    #[inline]
+    fn grow(&mut self, num_bits: C) {
+        let num_words = words(num_bits);
+        if self.data.len() <= num_words {
+            self.data.resize(num_words + 1, 0)
+        }
+    }
+
+    #[inline]
+    pub fn new(num_bits: usize) -> BitArray<C> {
+        let num_words = words(num_bits);
+        BitArray {
+            data: vec![0; num_words],
+            marker: PhantomData,
+        }
     }
 
     #[inline]
@@ -34,15 +93,30 @@ impl BitVector {
         self.data.iter().map(|e| e.count_ones() as usize).sum()
     }
 
+    /// True if `self` contains the bit `bit`.
     #[inline]
-    pub fn contains(&self, bit: usize) -> bool {
+    pub fn contains(&self, bit: C) -> bool {
         let (word, mask) = word_mask(bit);
         (self.data[word] & mask) != 0
     }
 
+    /// True if `self` contains all the bits in `other`.
+    ///
+    /// The two vectors must have the same length.
+    #[inline]
+    pub fn contains_all(&self, other: &BitArray<C>) -> bool {
+        assert_eq!(self.data.len(), other.data.len());
+        self.data.iter().zip(&other.data).all(|(a, b)| (a & b) == *b)
+    }
+
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.data.iter().all(|a| *a == 0)
+    }
+
     /// Returns true if the bit has changed.
     #[inline]
-    pub fn insert(&mut self, bit: usize) -> bool {
+    pub fn insert(&mut self, bit: C) -> bool {
         let (word, mask) = word_mask(bit);
         let data = &mut self.data[word];
         let value = *data;
@@ -51,8 +125,26 @@ impl BitVector {
         new_value != value
     }
 
+    /// Sets all bits to true.
+    pub fn insert_all(&mut self) {
+        for data in &mut self.data {
+            *data = u128::max_value();
+        }
+    }
+
+    /// Returns true if the bit has changed.
+    #[inline]
+    pub fn remove(&mut self, bit: C) -> bool {
+        let (word, mask) = word_mask(bit);
+        let data = &mut self.data[word];
+        let value = *data;
+        let new_value = value & !mask;
+        *data = new_value;
+        new_value != value
+    }
+
     #[inline]
-    pub fn insert_all(&mut self, all: &BitVector) -> bool {
+    pub fn merge(&mut self, all: &BitArray<C>) -> bool {
         assert!(self.data.len() == all.data.len());
         let mut changed = false;
         for (i, j) in self.data.iter_mut().zip(&all.data) {
@@ -65,41 +157,35 @@ impl BitVector {
         changed
     }
 
-    #[inline]
-    pub fn grow(&mut self, num_bits: usize) {
-        let num_words = u64s(num_bits);
-        if self.data.len() < num_words {
-            self.data.resize(num_words, 0)
-        }
-    }
-
     /// Iterates over indexes of set bits in a sorted order
     #[inline]
-    pub fn iter<'a>(&'a self) -> BitVectorIter<'a> {
-        BitVectorIter {
+    pub fn iter<'a>(&'a self) -> BitIter<'a, C> {
+        BitIter {
             iter: self.data.iter(),
             current: 0,
             idx: 0,
+            marker: PhantomData,
         }
     }
 }
 
-pub struct BitVectorIter<'a> {
-    iter: ::std::slice::Iter<'a, u64>,
-    current: u64,
+pub struct BitIter<'a, C: Idx> {
+    iter: ::std::slice::Iter<'a, Word>,
+    current: Word,
     idx: usize,
+    marker: PhantomData<C>
 }
 
-impl<'a> Iterator for BitVectorIter<'a> {
-    type Item = usize;
-    fn next(&mut self) -> Option<usize> {
+impl<'a, C: Idx> Iterator for BitIter<'a, C> {
+    type Item = C;
+    fn next(&mut self) -> Option<C> {
         while self.current == 0 {
             self.current = if let Some(&i) = self.iter.next() {
                 if i == 0 {
-                    self.idx += 64;
+                    self.idx += WORD_BITS;
                     continue;
                 } else {
-                    self.idx = u64s(self.idx) * 64;
+                    self.idx = words(self.idx) * WORD_BITS;
                     i
                 }
             } else {
@@ -110,28 +196,13 @@ impl<'a> Iterator for BitVectorIter<'a> {
         self.current >>= offset;
         self.current >>= 1; // shift otherwise overflows for 0b1000_0000_…_0000
         self.idx += offset + 1;
-        return Some(self.idx - 1);
-    }
-}
 
-impl FromIterator<bool> for BitVector {
-    fn from_iter<I>(iter: I) -> BitVector where I: IntoIterator<Item=bool> {
-        let iter = iter.into_iter();
-        let (len, _) = iter.size_hint();
-        // Make the minimum length for the bitvector 64 bits since that's
-        // the smallest non-zero size anyway.
-        let len = if len < 64 { 64 } else { len };
-        let mut bv = BitVector::new(len);
-        for (idx, val) in iter.enumerate() {
-            if idx > len {
-                bv.grow(idx);
-            }
-            if val {
-                bv.insert(idx);
-            }
-        }
+        Some(C::new(self.idx - 1))
+    }
 
-        bv
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let (_, upper) = self.iter.size_hint();
+        (0, upper)
     }
 }
 
@@ -139,35 +210,38 @@ impl FromIterator<bool> for BitVector {
 /// one gigantic bitvector. In other words, it is as if you have
 /// `rows` bitvectors, each of length `columns`.
 #[derive(Clone, Debug)]
-pub struct BitMatrix {
+pub struct BitMatrix<R: Idx, C: Idx> {
     columns: usize,
-    vector: Vec<u64>,
+    vector: Vec<Word>,
+    phantom: PhantomData<(R, C)>,
 }
 
-impl BitMatrix {
+impl<R: Idx, C: Idx> BitMatrix<R, C> {
     /// Create a new `rows x columns` matrix, initially empty.
-    pub fn new(rows: usize, columns: usize) -> BitMatrix {
+    pub fn new(rows: usize, columns: usize) -> BitMatrix<R, C> {
         // For every element, we need one bit for every other
-        // element. Round up to an even number of u64s.
-        let u64s_per_row = u64s(columns);
+        // element. Round up to an even number of words.
+        let words_per_row = words(columns);
         BitMatrix {
             columns,
-            vector: vec![0; rows * u64s_per_row],
+            vector: vec![0; rows * words_per_row],
+            phantom: PhantomData,
         }
     }
 
     /// The range of bits for a given row.
-    fn range(&self, row: usize) -> (usize, usize) {
-        let u64s_per_row = u64s(self.columns);
-        let start = row * u64s_per_row;
-        (start, start + u64s_per_row)
+    fn range(&self, row: R) -> (usize, usize) {
+        let row = row.index();
+        let words_per_row = words(self.columns);
+        let start = row * words_per_row;
+        (start, start + words_per_row)
     }
 
     /// Sets the cell at `(row, column)` to true. Put another way, add
     /// `column` to the bitset for `row`.
     ///
-    /// Returns true if this changed the matrix, and false otherwies.
-    pub fn add(&mut self, row: usize, column: usize) -> bool {
+    /// Returns true if this changed the matrix, and false otherwise.
+    pub fn add(&mut self, row: R, column: R) -> bool {
         let (start, _) = self.range(row);
         let (word, mask) = word_mask(column);
         let vector = &mut self.vector[..];
@@ -181,7 +255,7 @@ impl BitMatrix {
     /// the matrix cell at `(row, column)` true?  Put yet another way,
     /// if the matrix represents (transitive) reachability, can
     /// `row` reach `column`?
-    pub fn contains(&self, row: usize, column: usize) -> bool {
+    pub fn contains(&self, row: R, column: R) -> bool {
         let (start, _) = self.range(row);
         let (word, mask) = word_mask(column);
         (self.vector[start + word] & mask) != 0
@@ -191,18 +265,18 @@ impl BitMatrix {
     /// is an O(n) operation where `n` is the number of elements
     /// (somewhat independent from the actual size of the
     /// intersection, in particular).
-    pub fn intersection(&self, a: usize, b: usize) -> Vec<usize> {
+    pub fn intersection(&self, a: R, b: R) -> Vec<C> {
         let (a_start, a_end) = self.range(a);
         let (b_start, b_end) = self.range(b);
         let mut result = Vec::with_capacity(self.columns);
         for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
             let mut v = self.vector[i] & self.vector[j];
-            for bit in 0..64 {
+            for bit in 0..WORD_BITS {
                 if v == 0 {
                     break;
                 }
                 if v & 0x1 != 0 {
-                    result.push(base * 64 + bit);
+                    result.push(C::new(base * WORD_BITS + bit));
                 }
                 v >>= 1;
             }
@@ -217,7 +291,7 @@ impl BitMatrix {
     /// you have an edge `write -> read`, because in that case
     /// `write` can reach everything that `read` can (and
     /// potentially more).
-    pub fn merge(&mut self, read: usize, write: usize) -> bool {
+    pub fn merge(&mut self, read: R, write: R) -> bool {
         let (read_start, read_end) = self.range(read);
         let (write_start, write_end) = self.range(write);
         let vector = &mut self.vector[..];
@@ -226,38 +300,138 @@ impl BitMatrix {
             let v1 = vector[write_index];
             let v2 = v1 | vector[read_index];
             vector[write_index] = v2;
-            changed = changed | (v1 != v2);
+            changed |= v1 != v2;
         }
         changed
     }
 
     /// Iterates through all the columns set to true in a given row of
     /// the matrix.
-    pub fn iter<'a>(&'a self, row: usize) -> BitVectorIter<'a> {
+    pub fn iter<'a>(&'a self, row: R) -> BitIter<'a, C> {
         let (start, end) = self.range(row);
-        BitVectorIter {
+        BitIter {
             iter: self.vector[start..end].iter(),
             current: 0,
             idx: 0,
+            marker: PhantomData,
         }
     }
 }
 
+/// A moderately sparse bit matrix: rows are appended lazily, but columns
+/// within appended rows are instantiated fully upon creation.
+#[derive(Clone, Debug)]
+pub struct SparseBitMatrix<R, C>
+where
+    R: Idx,
+    C: Idx,
+{
+    columns: usize,
+    vector: IndexVec<R, BitArray<C>>,
+}
+
+impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
+    /// Create a new empty sparse bit matrix with no rows or columns.
+    pub fn new(columns: usize) -> Self {
+        Self {
+            columns,
+            vector: IndexVec::new(),
+        }
+    }
+
+    fn ensure_row(&mut self, row: R) {
+        let columns = self.columns;
+        self.vector
+            .ensure_contains_elem(row, || BitArray::new(columns));
+    }
+
+    /// Sets the cell at `(row, column)` to true. Put another way, insert
+    /// `column` to the bitset for `row`.
+    ///
+    /// Returns true if this changed the matrix, and false otherwise.
+    pub fn add(&mut self, row: R, column: C) -> bool {
+        self.ensure_row(row);
+        self.vector[row].insert(column)
+    }
+
+    /// Do the bits from `row` contain `column`? Put another way, is
+    /// the matrix cell at `(row, column)` true?  Put yet another way,
+    /// if the matrix represents (transitive) reachability, can
+    /// `row` reach `column`?
+    pub fn contains(&self, row: R, column: C) -> bool {
+        self.vector.get(row).map_or(false, |r| r.contains(column))
+    }
+
+    /// Add the bits from row `read` to the bits from row `write`,
+    /// return true if anything changed.
+    ///
+    /// This is used when computing transitive reachability because if
+    /// you have an edge `write -> read`, because in that case
+    /// `write` can reach everything that `read` can (and
+    /// potentially more).
+    pub fn merge(&mut self, read: R, write: R) -> bool {
+        if read == write || self.vector.get(read).is_none() {
+            return false;
+        }
+
+        self.ensure_row(write);
+        let (bitvec_read, bitvec_write) = self.vector.pick2_mut(read, write);
+        bitvec_write.merge(bitvec_read)
+    }
+
+    /// Merge a row, `from`, into the `into` row.
+    pub fn merge_into(&mut self, into: R, from: &BitArray<C>) -> bool {
+        self.ensure_row(into);
+        self.vector[into].merge(from)
+    }
+
+    /// Add all bits to the given row.
+    pub fn add_all(&mut self, row: R) {
+        self.ensure_row(row);
+        self.vector[row].insert_all();
+    }
+
+    /// Number of elements in the matrix.
+    pub fn len(&self) -> usize {
+        self.vector.len()
+    }
+
+    pub fn rows(&self) -> impl Iterator<Item = R> {
+        self.vector.indices()
+    }
+
+    /// Iterates through all the columns set to true in a given row of
+    /// the matrix.
+    pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
+        self.vector.get(row).into_iter().flat_map(|r| r.iter())
+    }
+
+    /// Iterates through each row and the accompanying bit set.
+    pub fn iter_enumerated<'a>(&'a self) -> impl Iterator<Item = (R, &'a BitArray<C>)> + 'a {
+        self.vector.iter_enumerated()
+    }
+
+    pub fn row(&self, row: R) -> Option<&BitArray<C>> {
+        self.vector.get(row)
+    }
+}
+
 #[inline]
-fn u64s(elements: usize) -> usize {
-    (elements + 63) / 64
+fn words<C: Idx>(elements: C) -> usize {
+    (elements.index() + WORD_BITS - 1) / WORD_BITS
 }
 
 #[inline]
-fn word_mask(index: usize) -> (usize, u64) {
-    let word = index / 64;
-    let mask = 1 << (index % 64);
+fn word_mask<C: Idx>(index: C) -> (usize, Word) {
+    let index = index.index();
+    let word = index / WORD_BITS;
+    let mask = 1 << (index % WORD_BITS);
     (word, mask)
 }
 
 #[test]
 fn bitvec_iter_works() {
-    let mut bitvec = BitVector::new(100);
+    let mut bitvec: BitArray<usize> = BitArray::new(100);
     bitvec.insert(1);
     bitvec.insert(10);
     bitvec.insert(19);
@@ -267,14 +441,15 @@ fn bitvec_iter_works() {
     bitvec.insert(65);
     bitvec.insert(66);
     bitvec.insert(99);
-    assert_eq!(bitvec.iter().collect::<Vec<_>>(),
-               [1, 10, 19, 62, 63, 64, 65, 66, 99]);
+    assert_eq!(
+        bitvec.iter().collect::<Vec<_>>(),
+        [1, 10, 19, 62, 63, 64, 65, 66, 99]
+    );
 }
 
-
 #[test]
 fn bitvec_iter_works_2() {
-    let mut bitvec = BitVector::new(319);
+    let mut bitvec: BitArray<usize> = BitArray::new(319);
     bitvec.insert(0);
     bitvec.insert(127);
     bitvec.insert(191);
@@ -285,14 +460,14 @@ fn bitvec_iter_works_2() {
 
 #[test]
 fn union_two_vecs() {
-    let mut vec1 = BitVector::new(65);
-    let mut vec2 = BitVector::new(65);
+    let mut vec1: BitArray<usize> = BitArray::new(65);
+    let mut vec2: BitArray<usize> = BitArray::new(65);
     assert!(vec1.insert(3));
     assert!(!vec1.insert(3));
     assert!(vec2.insert(5));
     assert!(vec2.insert(64));
-    assert!(vec1.insert_all(&vec2));
-    assert!(!vec1.insert_all(&vec2));
+    assert!(vec1.merge(&vec2));
+    assert!(!vec1.merge(&vec2));
     assert!(vec1.contains(3));
     assert!(!vec1.contains(4));
     assert!(vec1.contains(5));
@@ -302,25 +477,25 @@ fn union_two_vecs() {
 
 #[test]
 fn grow() {
-    let mut vec1 = BitVector::new(65);
-    for index in 0 .. 65 {
+    let mut vec1: BitVector<usize> = BitVector::with_capacity(65);
+    for index in 0..65 {
         assert!(vec1.insert(index));
         assert!(!vec1.insert(index));
     }
     vec1.grow(128);
 
     // Check if the bits set before growing are still set
-    for index in 0 .. 65 {
+    for index in 0..65 {
         assert!(vec1.contains(index));
     }
 
     // Check if the new bits are all un-set
-    for index in 65 .. 128 {
+    for index in 65..128 {
         assert!(!vec1.contains(index));
     }
 
     // Check that we can set all new bits without running out of bounds
-    for index in 65 .. 128 {
+    for index in 65..128 {
         assert!(vec1.insert(index));
         assert!(!vec1.insert(index));
     }
@@ -328,7 +503,7 @@ fn grow() {
 
 #[test]
 fn matrix_intersection() {
-    let mut vec1 = BitMatrix::new(200, 200);
+    let mut vec1: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
 
     // (*) Elements reachable from both 2 and 65.
 
@@ -359,7 +534,49 @@ fn matrix_intersection() {
 
 #[test]
 fn matrix_iter() {
-    let mut matrix = BitMatrix::new(64, 100);
+    let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
+    matrix.add(3, 22);
+    matrix.add(3, 75);
+    matrix.add(2, 99);
+    matrix.add(4, 0);
+    matrix.merge(3, 5);
+
+    let expected = [99];
+    let mut iter = expected.iter();
+    for i in matrix.iter(2) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    for i in matrix.iter(3) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [0];
+    let mut iter = expected.iter();
+    for i in matrix.iter(4) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+
+    let expected = [22, 75];
+    let mut iter = expected.iter();
+    for i in matrix.iter(5) {
+        let j = *iter.next().unwrap();
+        assert_eq!(i, j);
+    }
+    assert!(iter.next().is_none());
+}
+
+#[test]
+fn sparse_matrix_iter() {
+    let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
     matrix.add(3, 22);
     matrix.add(3, 75);
     matrix.add(2, 99);
diff --git a/src/librustc_data_structures/blake2b.rs b/src/librustc_data_structures/blake2b.rs
deleted file mode 100644
index 6b8bf8df0d3..00000000000
--- a/src/librustc_data_structures/blake2b.rs
+++ /dev/null
@@ -1,363 +0,0 @@
-// 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.
-
-
-// An implementation of the Blake2b cryptographic hash function.
-// The implementation closely follows: https://tools.ietf.org/html/rfc7693
-//
-// "BLAKE2 is a cryptographic hash function faster than MD5, SHA-1, SHA-2, and
-//  SHA-3, yet is at least as secure as the latest standard SHA-3."
-// according to their own website :)
-//
-// Indeed this implementation is two to three times as fast as our SHA-256
-// implementation. If you have the luxury of being able to use crates from
-// crates.io, you can go there and find still faster implementations.
-
-use std::mem;
-use std::slice;
-
-#[repr(C)]
-struct Blake2bCtx {
-    b: [u8; 128],
-    h: [u64; 8],
-    t: [u64; 2],
-    c: usize,
-    outlen: u16,
-    finalized: bool,
-
-    #[cfg(debug_assertions)]
-    fnv_hash: u64,
-}
-
-#[cfg(debug_assertions)]
-impl ::std::fmt::Debug for Blake2bCtx {
-    fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
-        write!(fmt, "{:x}", self.fnv_hash)
-    }
-}
-
-#[cfg(not(debug_assertions))]
-impl ::std::fmt::Debug for Blake2bCtx {
-    fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
-        write!(fmt, "Enable debug_assertions() for more info.")
-    }
-}
-
-#[inline(always)]
-fn b2b_g(v: &mut [u64; 16],
-         a: usize,
-         b: usize,
-         c: usize,
-         d: usize,
-         x: u64,
-         y: u64)
-{
-    v[a] = v[a].wrapping_add(v[b]).wrapping_add(x);
-    v[d] = (v[d] ^ v[a]).rotate_right(32);
-    v[c] = v[c].wrapping_add(v[d]);
-    v[b] = (v[b] ^ v[c]).rotate_right(24);
-    v[a] = v[a].wrapping_add(v[b]).wrapping_add(y);
-    v[d] = (v[d] ^ v[a]).rotate_right(16);
-    v[c] = v[c].wrapping_add(v[d]);
-    v[b] = (v[b] ^ v[c]).rotate_right(63);
-}
-
-// Initialization vector
-const BLAKE2B_IV: [u64; 8] = [
-   0x6A09E667F3BCC908, 0xBB67AE8584CAA73B,
-   0x3C6EF372FE94F82B, 0xA54FF53A5F1D36F1,
-   0x510E527FADE682D1, 0x9B05688C2B3E6C1F,
-   0x1F83D9ABFB41BD6B, 0x5BE0CD19137E2179
-];
-
-fn blake2b_compress(ctx: &mut Blake2bCtx, last: bool) {
-
-    const SIGMA: [[usize; 16]; 12] = [
-        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ],
-        [14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 ],
-        [11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4 ],
-        [7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8 ],
-        [9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13 ],
-        [2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9 ],
-        [12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11 ],
-        [13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10 ],
-        [6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5 ],
-        [10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0 ],
-        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ],
-        [14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 ]
-    ];
-
-    let mut v: [u64; 16] = [
-        ctx.h[0],
-        ctx.h[1],
-        ctx.h[2],
-        ctx.h[3],
-        ctx.h[4],
-        ctx.h[5],
-        ctx.h[6],
-        ctx.h[7],
-
-        BLAKE2B_IV[0],
-        BLAKE2B_IV[1],
-        BLAKE2B_IV[2],
-        BLAKE2B_IV[3],
-        BLAKE2B_IV[4],
-        BLAKE2B_IV[5],
-        BLAKE2B_IV[6],
-        BLAKE2B_IV[7],
-    ];
-
-    v[12] ^= ctx.t[0]; // low 64 bits of offset
-    v[13] ^= ctx.t[1]; // high 64 bits
-    if last {
-        v[14] = !v[14];
-    }
-
-    {
-        // Re-interpret the input buffer in the state as an array
-        // of little-endian u64s, converting them to machine
-        // endianness. It's OK to modify the buffer in place
-        // since this is the last time  this data will be accessed
-        // before it's overwritten.
-
-        let m: &mut [u64; 16] = unsafe {
-            let b: &mut [u8; 128] = &mut ctx.b;
-            ::std::mem::transmute(b)
-        };
-
-        if cfg!(target_endian = "big") {
-            for word in &mut m[..] {
-                *word = u64::from_le(*word);
-            }
-        }
-
-        for i in 0 .. 12 {
-            b2b_g(&mut v, 0, 4,  8, 12, m[SIGMA[i][ 0]], m[SIGMA[i][ 1]]);
-            b2b_g(&mut v, 1, 5,  9, 13, m[SIGMA[i][ 2]], m[SIGMA[i][ 3]]);
-            b2b_g(&mut v, 2, 6, 10, 14, m[SIGMA[i][ 4]], m[SIGMA[i][ 5]]);
-            b2b_g(&mut v, 3, 7, 11, 15, m[SIGMA[i][ 6]], m[SIGMA[i][ 7]]);
-            b2b_g(&mut v, 0, 5, 10, 15, m[SIGMA[i][ 8]], m[SIGMA[i][ 9]]);
-            b2b_g(&mut v, 1, 6, 11, 12, m[SIGMA[i][10]], m[SIGMA[i][11]]);
-            b2b_g(&mut v, 2, 7,  8, 13, m[SIGMA[i][12]], m[SIGMA[i][13]]);
-            b2b_g(&mut v, 3, 4,  9, 14, m[SIGMA[i][14]], m[SIGMA[i][15]]);
-        }
-    }
-
-    for i in 0 .. 8 {
-        ctx.h[i] ^= v[i] ^ v[i + 8];
-    }
-}
-
-fn blake2b_new(outlen: usize, key: &[u8]) -> Blake2bCtx {
-    assert!(outlen > 0 && outlen <= 64 && key.len() <= 64);
-
-    let mut ctx = Blake2bCtx {
-        b: [0; 128],
-        h: BLAKE2B_IV,
-        t: [0; 2],
-        c: 0,
-        outlen: outlen as u16,
-        finalized: false,
-
-        #[cfg(debug_assertions)]
-        fnv_hash: 0xcbf29ce484222325,
-    };
-
-    ctx.h[0] ^= 0x01010000 ^ ((key.len() << 8) as u64) ^ (outlen as u64);
-
-    if key.len() > 0 {
-       blake2b_update(&mut ctx, key);
-       ctx.c = ctx.b.len();
-    }
-
-    ctx
-}
-
-fn blake2b_update(ctx: &mut Blake2bCtx, mut data: &[u8]) {
-    assert!(!ctx.finalized, "Blake2bCtx already finalized");
-
-    let mut bytes_to_copy = data.len();
-    let mut space_in_buffer = ctx.b.len() - ctx.c;
-
-    while bytes_to_copy > space_in_buffer {
-        checked_mem_copy(data, &mut ctx.b[ctx.c .. ], space_in_buffer);
-
-        ctx.t[0] = ctx.t[0].wrapping_add(ctx.b.len() as u64);
-        if ctx.t[0] < (ctx.b.len() as u64) {
-            ctx.t[1] += 1;
-        }
-        blake2b_compress(ctx, false);
-        ctx.c = 0;
-
-        data = &data[space_in_buffer .. ];
-        bytes_to_copy -= space_in_buffer;
-        space_in_buffer = ctx.b.len();
-    }
-
-    if bytes_to_copy > 0 {
-        checked_mem_copy(data, &mut ctx.b[ctx.c .. ], bytes_to_copy);
-        ctx.c += bytes_to_copy;
-    }
-
-    #[cfg(debug_assertions)]
-    {
-        // compute additional FNV hash for simpler to read debug output
-        const MAGIC_PRIME: u64 = 0x00000100000001b3;
-
-        for &byte in data {
-            ctx.fnv_hash = (ctx.fnv_hash ^ byte as u64).wrapping_mul(MAGIC_PRIME);
-        }
-    }
-}
-
-fn blake2b_final(ctx: &mut Blake2bCtx)
-{
-    assert!(!ctx.finalized, "Blake2bCtx already finalized");
-
-    ctx.t[0] = ctx.t[0].wrapping_add(ctx.c as u64);
-    if ctx.t[0] < ctx.c as u64 {
-        ctx.t[1] += 1;
-    }
-
-    while ctx.c < 128 {
-        ctx.b[ctx.c] = 0;
-        ctx.c += 1;
-    }
-
-    blake2b_compress(ctx, true);
-
-    // Modify our buffer to little-endian format as it will be read
-    // as a byte array. It's OK to modify the buffer in place since
-    // this is the last time this data will be accessed.
-    if cfg!(target_endian = "big") {
-        for word in &mut ctx.h {
-            *word = word.to_le();
-        }
-    }
-
-    ctx.finalized = true;
-}
-
-#[inline(always)]
-fn checked_mem_copy<T1, T2>(from: &[T1], to: &mut [T2], byte_count: usize) {
-    let from_size = from.len() * mem::size_of::<T1>();
-    let to_size = to.len() * mem::size_of::<T2>();
-    assert!(from_size >= byte_count);
-    assert!(to_size >= byte_count);
-    let from_byte_ptr = from.as_ptr() as * const u8;
-    let to_byte_ptr = to.as_mut_ptr() as * mut u8;
-    unsafe {
-        ::std::ptr::copy_nonoverlapping(from_byte_ptr, to_byte_ptr, byte_count);
-    }
-}
-
-pub fn blake2b(out: &mut [u8], key: &[u8],  data: &[u8])
-{
-    let mut ctx = blake2b_new(out.len(), key);
-    blake2b_update(&mut ctx, data);
-    blake2b_final(&mut ctx);
-    checked_mem_copy(&ctx.h, out, ctx.outlen as usize);
-}
-
-pub struct Blake2bHasher(Blake2bCtx);
-
-impl ::std::hash::Hasher for Blake2bHasher {
-    fn write(&mut self, bytes: &[u8]) {
-        blake2b_update(&mut self.0, bytes);
-    }
-
-    fn finish(&self) -> u64 {
-        assert!(self.0.outlen == 8,
-                "Hasher initialized with incompatible output length");
-        u64::from_le(self.0.h[0])
-    }
-}
-
-impl Blake2bHasher {
-    pub fn new(outlen: usize, key: &[u8]) -> Blake2bHasher {
-        Blake2bHasher(blake2b_new(outlen, key))
-    }
-
-    pub fn finalize(&mut self) -> &[u8] {
-        if !self.0.finalized {
-            blake2b_final(&mut self.0);
-        }
-        debug_assert!(mem::size_of_val(&self.0.h) >= self.0.outlen as usize);
-        let raw_ptr = (&self.0.h[..]).as_ptr() as * const u8;
-        unsafe {
-            slice::from_raw_parts(raw_ptr, self.0.outlen as usize)
-        }
-    }
-}
-
-impl ::std::fmt::Debug for Blake2bHasher {
-    fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> Result<(), ::std::fmt::Error> {
-        write!(fmt, "{:?}", self.0)
-    }
-}
-
-#[cfg(test)]
-fn selftest_seq(out: &mut [u8], seed: u32)
-{
-   let mut a: u32 = 0xDEAD4BADu32.wrapping_mul(seed);
-   let mut b: u32 = 1;
-
-   for i in 0 .. out.len() {
-       let t: u32 = a.wrapping_add(b);
-       a = b;
-       b = t;
-       out[i] = ((t >> 24) & 0xFF) as u8;
-   }
-}
-
-#[test]
-fn blake2b_selftest()
-{
-    use std::hash::Hasher;
-
-    // grand hash of hash results
-    const BLAKE2B_RES: [u8; 32] = [
-        0xC2, 0x3A, 0x78, 0x00, 0xD9, 0x81, 0x23, 0xBD,
-        0x10, 0xF5, 0x06, 0xC6, 0x1E, 0x29, 0xDA, 0x56,
-        0x03, 0xD7, 0x63, 0xB8, 0xBB, 0xAD, 0x2E, 0x73,
-        0x7F, 0x5E, 0x76, 0x5A, 0x7B, 0xCC, 0xD4, 0x75
-    ];
-
-    // parameter sets
-    const B2B_MD_LEN: [usize; 4] = [20, 32, 48, 64];
-    const B2B_IN_LEN: [usize; 6] = [0, 3, 128, 129, 255, 1024];
-
-    let mut data = [0u8; 1024];
-    let mut md = [0u8; 64];
-    let mut key = [0u8; 64];
-
-    let mut hasher = Blake2bHasher::new(32, &[]);
-
-    for i in 0 .. 4 {
-       let outlen = B2B_MD_LEN[i];
-       for j in 0 .. 6 {
-            let inlen = B2B_IN_LEN[j];
-
-            selftest_seq(&mut data[.. inlen], inlen as u32); // unkeyed hash
-            blake2b(&mut md[.. outlen], &[], &data[.. inlen]);
-            hasher.write(&md[.. outlen]); // hash the hash
-
-            selftest_seq(&mut key[0 .. outlen], outlen as u32); // keyed hash
-            blake2b(&mut md[.. outlen], &key[.. outlen], &data[.. inlen]);
-            hasher.write(&md[.. outlen]); // hash the hash
-       }
-    }
-
-    // compute and compare the hash of hashes
-    let md = hasher.finalize();
-    for i in 0 .. 32 {
-        assert_eq!(md[i], BLAKE2B_RES[i]);
-    }
-}
diff --git a/src/librustc_data_structures/const_cstr.rs b/src/librustc_data_structures/const_cstr.rs
new file mode 100644
index 00000000000..4589d973b6a
--- /dev/null
+++ b/src/librustc_data_structures/const_cstr.rs
@@ -0,0 +1,42 @@
+// 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.
+
+/// This macro creates a zero-overhead &CStr by adding a NUL terminator to
+/// the string literal passed into it at compile-time. Use it like:
+///
+/// ```
+///     let some_const_cstr = const_cstr!("abc");
+/// ```
+///
+/// The above is roughly equivalent to:
+///
+/// ```
+///     let some_const_cstr = CStr::from_bytes_with_nul(b"abc\0").unwrap()
+/// ```
+///
+/// Note that macro only checks the string literal for internal NULs if
+/// debug-assertions are enabled in order to avoid runtime overhead in release
+/// builds.
+#[macro_export]
+macro_rules! const_cstr {
+    ($s:expr) => ({
+        use std::ffi::CStr;
+
+        let str_plus_nul = concat!($s, "\0");
+
+        if cfg!(debug_assertions) {
+            CStr::from_bytes_with_nul(str_plus_nul.as_bytes()).unwrap()
+        } else {
+            unsafe {
+                CStr::from_bytes_with_nul_unchecked(str_plus_nul.as_bytes())
+            }
+        }
+    })
+}
diff --git a/src/librustc_data_structures/control_flow_graph/mod.rs b/src/librustc_data_structures/control_flow_graph/mod.rs
deleted file mode 100644
index 7bf776675c6..00000000000
--- a/src/librustc_data_structures/control_flow_graph/mod.rs
+++ /dev/null
@@ -1,42 +0,0 @@
-// 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 super::indexed_vec::Idx;
-
-pub mod dominators;
-pub mod iterate;
-mod reference;
-
-#[cfg(test)]
-mod test;
-
-pub trait ControlFlowGraph
-    where Self: for<'graph> GraphPredecessors<'graph, Item=<Self as ControlFlowGraph>::Node>,
-          Self: for<'graph> GraphSuccessors<'graph, Item=<Self as ControlFlowGraph>::Node>
-{
-    type Node: Idx;
-
-    fn num_nodes(&self) -> usize;
-    fn start_node(&self) -> Self::Node;
-    fn predecessors<'graph>(&'graph self, node: Self::Node)
-                            -> <Self as GraphPredecessors<'graph>>::Iter;
-    fn successors<'graph>(&'graph self, node: Self::Node)
-                            -> <Self as GraphSuccessors<'graph>>::Iter;
-}
-
-pub trait GraphPredecessors<'graph> {
-    type Item;
-    type Iter: Iterator<Item = Self::Item>;
-}
-
-pub trait GraphSuccessors<'graph> {
-    type Item;
-    type Iter: Iterator<Item = Self::Item>;
-}
diff --git a/src/librustc_data_structures/fingerprint.rs b/src/librustc_data_structures/fingerprint.rs
new file mode 100644
index 00000000000..aa9ddda2b93
--- /dev/null
+++ b/src/librustc_data_structures/fingerprint.rs
@@ -0,0 +1,111 @@
+// 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 std::mem;
+use stable_hasher;
+use serialize;
+use serialize::opaque::{EncodeResult, Encoder, Decoder};
+
+#[derive(Eq, PartialEq, Ord, PartialOrd, Hash, Debug, Clone, Copy)]
+pub struct Fingerprint(u64, u64);
+
+impl Fingerprint {
+
+    pub const ZERO: Fingerprint = Fingerprint(0, 0);
+
+    #[inline]
+    pub fn from_smaller_hash(hash: u64) -> Fingerprint {
+        Fingerprint(hash, hash)
+    }
+
+    #[inline]
+    pub fn to_smaller_hash(&self) -> u64 {
+        self.0
+    }
+
+    #[inline]
+    pub fn as_value(&self) -> (u64, u64) {
+        (self.0, self.1)
+    }
+
+    #[inline]
+    pub fn combine(self, other: Fingerprint) -> Fingerprint {
+        // See https://stackoverflow.com/a/27952689 on why this function is
+        // implemented this way.
+        Fingerprint(
+            self.0.wrapping_mul(3).wrapping_add(other.0),
+            self.1.wrapping_mul(3).wrapping_add(other.1)
+        )
+    }
+
+    // Combines two hashes in an order independent way. Make sure this is what
+    // you want.
+    #[inline]
+    pub fn combine_commutative(self, other: Fingerprint) -> Fingerprint {
+        let a = (self.1 as u128) << 64 | self.0 as u128;
+        let b = (other.1 as u128) << 64 | other.0 as u128;
+
+        let c = a.wrapping_add(b);
+
+        Fingerprint((c >> 64) as u64, c as u64)
+    }
+
+    pub fn to_hex(&self) -> String {
+        format!("{:x}{:x}", self.0, self.1)
+    }
+
+    pub fn encode_opaque(&self, encoder: &mut Encoder) -> EncodeResult {
+        let bytes: [u8; 16] = unsafe { mem::transmute([self.0.to_le(), self.1.to_le()]) };
+
+        encoder.emit_raw_bytes(&bytes);
+        Ok(())
+    }
+
+    pub fn decode_opaque<'a>(decoder: &mut Decoder<'a>) -> Result<Fingerprint, String> {
+        let mut bytes = [0; 16];
+
+        decoder.read_raw_bytes(&mut bytes)?;
+
+        let [l, r]: [u64; 2] = unsafe { mem::transmute(bytes) };
+
+        Ok(Fingerprint(u64::from_le(l), u64::from_le(r)))
+    }
+}
+
+impl ::std::fmt::Display for Fingerprint {
+    fn fmt(&self, formatter: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
+        write!(formatter, "{:x}-{:x}", self.0, self.1)
+    }
+}
+
+impl stable_hasher::StableHasherResult for Fingerprint {
+    fn finish(hasher: stable_hasher::StableHasher<Self>) -> Self {
+        let (_0, _1) = hasher.finalize();
+        Fingerprint(_0, _1)
+    }
+}
+
+impl_stable_hash_via_hash!(Fingerprint);
+
+impl serialize::UseSpecializedEncodable for Fingerprint { }
+
+impl serialize::UseSpecializedDecodable for Fingerprint { }
+
+impl serialize::SpecializedEncoder<Fingerprint> for serialize::opaque::Encoder {
+    fn specialized_encode(&mut self, f: &Fingerprint) -> Result<(), Self::Error> {
+        f.encode_opaque(self)
+    }
+}
+
+impl<'a> serialize::SpecializedDecoder<Fingerprint> for serialize::opaque::Decoder<'a> {
+    fn specialized_decode(&mut self) -> Result<Fingerprint, Self::Error> {
+        Fingerprint::decode_opaque(self)
+    }
+}
diff --git a/src/librustc_data_structures/flock.rs b/src/librustc_data_structures/flock.rs
index ff1ebb11b72..3f248dadb66 100644
--- a/src/librustc_data_structures/flock.rs
+++ b/src/librustc_data_structures/flock.rs
@@ -254,8 +254,8 @@ mod imp {
     type ULONG_PTR = usize;
 
     type LPOVERLAPPED = *mut OVERLAPPED;
-    const LOCKFILE_EXCLUSIVE_LOCK: DWORD = 0x00000002;
-    const LOCKFILE_FAIL_IMMEDIATELY: DWORD = 0x00000001;
+    const LOCKFILE_EXCLUSIVE_LOCK: DWORD = 0x0000_0002;
+    const LOCKFILE_FAIL_IMMEDIATELY: DWORD = 0x0000_0001;
 
     const FILE_SHARE_DELETE: DWORD = 0x4;
     const FILE_SHARE_READ: DWORD = 0x1;
diff --git a/src/librustc_data_structures/fx.rs b/src/librustc_data_structures/fx.rs
index 5bf25437763..3bf3170d1df 100644
--- a/src/librustc_data_structures/fx.rs
+++ b/src/librustc_data_structures/fx.rs
@@ -10,11 +10,11 @@
 
 use std::collections::{HashMap, HashSet};
 use std::default::Default;
-use std::hash::{Hasher, Hash, BuildHasherDefault};
-use std::ops::BitXor;
+use std::hash::Hash;
 
-pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;
-pub type FxHashSet<V> = HashSet<V, BuildHasherDefault<FxHasher>>;
+pub use rustc_hash::FxHashMap;
+pub use rustc_hash::FxHashSet;
+pub use rustc_hash::FxHasher;
 
 #[allow(non_snake_case)]
 pub fn FxHashMap<K: Hash + Eq, V>() -> FxHashMap<K, V> {
@@ -26,84 +26,3 @@ pub fn FxHashSet<V: Hash + Eq>() -> FxHashSet<V> {
     HashSet::default()
 }
 
-/// A speedy hash algorithm for use within rustc. The hashmap in liballoc
-/// by default uses SipHash which isn't quite as speedy as we want. In the
-/// compiler we're not really worried about DOS attempts, so we use a fast
-/// non-cryptographic hash.
-///
-/// This is the same as the algorithm used by Firefox -- which is a homespun
-/// one not based on any widely-known algorithm -- though modified to produce
-/// 64-bit hash values instead of 32-bit hash values. It consistently
-/// out-performs an FNV-based hash within rustc itself -- the collision rate is
-/// similar or slightly worse than FNV, but the speed of the hash function
-/// itself is much higher because it works on up to 8 bytes at a time.
-pub struct FxHasher {
-    hash: usize
-}
-
-#[cfg(target_pointer_width = "32")]
-const K: usize = 0x9e3779b9;
-#[cfg(target_pointer_width = "64")]
-const K: usize = 0x517cc1b727220a95;
-
-impl Default for FxHasher {
-    #[inline]
-    fn default() -> FxHasher {
-        FxHasher { hash: 0 }
-    }
-}
-
-impl FxHasher {
-    #[inline]
-    fn add_to_hash(&mut self, i: usize) {
-        self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);
-    }
-}
-
-impl Hasher for FxHasher {
-    #[inline]
-    fn write(&mut self, bytes: &[u8]) {
-        for byte in bytes {
-            let i = *byte;
-            self.add_to_hash(i as usize);
-        }
-    }
-
-    #[inline]
-    fn write_u8(&mut self, i: u8) {
-        self.add_to_hash(i as usize);
-    }
-
-    #[inline]
-    fn write_u16(&mut self, i: u16) {
-        self.add_to_hash(i as usize);
-    }
-
-    #[inline]
-    fn write_u32(&mut self, i: u32) {
-        self.add_to_hash(i as usize);
-    }
-
-    #[cfg(target_pointer_width = "32")]
-    #[inline]
-    fn write_u64(&mut self, i: u64) {
-        self.add_to_hash(i as usize);
-        self.add_to_hash((i >> 32) as usize);
-    }
-
-    #[cfg(target_pointer_width = "64")]
-    #[inline]
-    fn write_u64(&mut self, i: u64) {
-        self.add_to_hash(i as usize);
-    }
-
-    #[inline]
-    fn write_usize(&mut self, i: usize) {
-        self.add_to_hash(i);
-    }
-
-    #[inline]
-    fn finish(&self) -> u64 {
-        self.hash as u64
-    }
-}
diff --git a/src/librustc_data_structures/control_flow_graph/dominators/mod.rs b/src/librustc_data_structures/graph/dominators/mod.rs
index dc487f1162c..e54147cbe7c 100644
--- a/src/librustc_data_structures/control_flow_graph/dominators/mod.rs
+++ b/src/librustc_data_structures/graph/dominators/mod.rs
@@ -14,9 +14,9 @@
 //! Rice Computer Science TS-06-33870
 //! <https://www.cs.rice.edu/~keith/EMBED/dom.pdf>
 
-use super::ControlFlowGraph;
+use super::super::indexed_vec::{Idx, IndexVec};
 use super::iterate::reverse_post_order;
-use super::super::indexed_vec::{IndexVec, Idx};
+use super::ControlFlowGraph;
 
 use std::fmt;
 
@@ -29,15 +29,16 @@ pub fn dominators<G: ControlFlowGraph>(graph: &G) -> Dominators<G::Node> {
     dominators_given_rpo(graph, &rpo)
 }
 
-pub fn dominators_given_rpo<G: ControlFlowGraph>(graph: &G,
-                                                 rpo: &[G::Node])
-                                                 -> Dominators<G::Node> {
+pub fn dominators_given_rpo<G: ControlFlowGraph>(
+    graph: &G,
+    rpo: &[G::Node],
+) -> Dominators<G::Node> {
     let start_node = graph.start_node();
     assert_eq!(rpo[0], start_node);
 
     // compute the post order index (rank) for each node
-    let mut post_order_rank: IndexVec<G::Node, usize> = IndexVec::from_elem_n(usize::default(),
-                                                                              graph.num_nodes());
+    let mut post_order_rank: IndexVec<G::Node, usize> =
+        IndexVec::from_elem_n(usize::default(), graph.num_nodes());
     for (index, node) in rpo.iter().rev().cloned().enumerate() {
         post_order_rank[node] = index;
     }
@@ -56,10 +57,12 @@ pub fn dominators_given_rpo<G: ControlFlowGraph>(graph: &G,
                 if immediate_dominators[pred].is_some() {
                     // (*)
                     // (*) dominators for `pred` have been calculated
-                    new_idom = intersect_opt(&post_order_rank,
-                                             &immediate_dominators,
-                                             new_idom,
-                                             Some(pred));
+                    new_idom = intersect_opt(
+                        &post_order_rank,
+                        &immediate_dominators,
+                        new_idom,
+                        Some(pred),
+                    );
                 }
             }
 
@@ -76,11 +79,12 @@ pub fn dominators_given_rpo<G: ControlFlowGraph>(graph: &G,
     }
 }
 
-fn intersect_opt<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
-                            immediate_dominators: &IndexVec<Node, Option<Node>>,
-                            node1: Option<Node>,
-                            node2: Option<Node>)
-                            -> Option<Node> {
+fn intersect_opt<Node: Idx>(
+    post_order_rank: &IndexVec<Node, usize>,
+    immediate_dominators: &IndexVec<Node, Option<Node>>,
+    node1: Option<Node>,
+    node2: Option<Node>,
+) -> Option<Node> {
     match (node1, node2) {
         (None, None) => None,
         (Some(n), None) | (None, Some(n)) => Some(n),
@@ -88,11 +92,12 @@ fn intersect_opt<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
     }
 }
 
-fn intersect<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
-                        immediate_dominators: &IndexVec<Node, Option<Node>>,
-                        mut node1: Node,
-                        mut node2: Node)
-                        -> Node {
+fn intersect<Node: Idx>(
+    post_order_rank: &IndexVec<Node, usize>,
+    immediate_dominators: &IndexVec<Node, Option<Node>>,
+    mut node1: Node,
+    mut node2: Node,
+) -> Node {
     while node1 != node2 {
         while post_order_rank[node1] < post_order_rank[node2] {
             node1 = immediate_dominators[node1].unwrap();
@@ -102,7 +107,8 @@ fn intersect<Node: Idx>(post_order_rank: &IndexVec<Node, usize>,
             node2 = immediate_dominators[node2].unwrap();
         }
     }
-    return node1;
+
+    node1
 }
 
 #[derive(Clone, Debug)]
@@ -175,12 +181,14 @@ impl<Node: Idx> DominatorTree<Node> {
 }
 
 impl<Node: Idx> fmt::Debug for DominatorTree<Node> {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
-        fmt::Debug::fmt(&DominatorTreeNode {
-                            tree: self,
-                            node: self.root,
-                        },
-                        fmt)
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Debug::fmt(
+            &DominatorTreeNode {
+                tree: self,
+                node: self.root,
+            },
+            fmt,
+        )
     }
 }
 
@@ -190,15 +198,13 @@ struct DominatorTreeNode<'tree, Node: Idx> {
 }
 
 impl<'tree, Node: Idx> fmt::Debug for DominatorTreeNode<'tree, Node> {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
         let subtrees: Vec<_> = self.tree
             .children(self.node)
             .iter()
-            .map(|&child| {
-                DominatorTreeNode {
-                    tree: self.tree,
-                    node: child,
-                }
+            .map(|&child| DominatorTreeNode {
+                tree: self.tree,
+                node: child,
             })
             .collect();
         fmt.debug_tuple("")
diff --git a/src/librustc_data_structures/control_flow_graph/dominators/test.rs b/src/librustc_data_structures/graph/dominators/test.rs
index 0af878cac2d..0af878cac2d 100644
--- a/src/librustc_data_structures/control_flow_graph/dominators/test.rs
+++ b/src/librustc_data_structures/graph/dominators/test.rs
diff --git a/src/librustc_data_structures/graph/implementation/mod.rs b/src/librustc_data_structures/graph/implementation/mod.rs
new file mode 100644
index 00000000000..baac7565868
--- /dev/null
+++ b/src/librustc_data_structures/graph/implementation/mod.rs
@@ -0,0 +1,417 @@
+// Copyright 2012-2014 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.
+
+//! A graph module for use in dataflow, region resolution, and elsewhere.
+//!
+//! # Interface details
+//!
+//! You customize the graph by specifying a "node data" type `N` and an
+//! "edge data" type `E`. You can then later gain access (mutable or
+//! immutable) to these "user-data" bits. Currently, you can only add
+//! nodes or edges to the graph. You cannot remove or modify them once
+//! added. This could be changed if we have a need.
+//!
+//! # Implementation details
+//!
+//! The main tricky thing about this code is the way that edges are
+//! stored. The edges are stored in a central array, but they are also
+//! threaded onto two linked lists for each node, one for incoming edges
+//! and one for outgoing edges. Note that every edge is a member of some
+//! incoming list and some outgoing list.  Basically you can load the
+//! first index of the linked list from the node data structures (the
+//! field `first_edge`) and then, for each edge, load the next index from
+//! the field `next_edge`). Each of those fields is an array that should
+//! be indexed by the direction (see the type `Direction`).
+
+use bitvec::BitArray;
+use std::fmt::Debug;
+use std::usize;
+use snapshot_vec::{SnapshotVec, SnapshotVecDelegate};
+
+#[cfg(test)]
+mod tests;
+
+pub struct Graph<N, E> {
+    nodes: SnapshotVec<Node<N>>,
+    edges: SnapshotVec<Edge<E>>,
+}
+
+pub struct Node<N> {
+    first_edge: [EdgeIndex; 2], // see module comment
+    pub data: N,
+}
+
+#[derive(Debug)]
+pub struct Edge<E> {
+    next_edge: [EdgeIndex; 2], // see module comment
+    source: NodeIndex,
+    target: NodeIndex,
+    pub data: E,
+}
+
+impl<N> SnapshotVecDelegate for Node<N> {
+    type Value = Node<N>;
+    type Undo = ();
+
+    fn reverse(_: &mut Vec<Node<N>>, _: ()) {}
+}
+
+impl<N> SnapshotVecDelegate for Edge<N> {
+    type Value = Edge<N>;
+    type Undo = ();
+
+    fn reverse(_: &mut Vec<Edge<N>>, _: ()) {}
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
+pub struct NodeIndex(pub usize);
+
+#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
+pub struct EdgeIndex(pub usize);
+
+pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX);
+
+// Use a private field here to guarantee no more instances are created:
+#[derive(Copy, Clone, Debug, PartialEq)]
+pub struct Direction {
+    repr: usize,
+}
+
+pub const OUTGOING: Direction = Direction { repr: 0 };
+
+pub const INCOMING: Direction = Direction { repr: 1 };
+
+impl NodeIndex {
+    /// Returns unique id (unique with respect to the graph holding associated node).
+    pub fn node_id(self) -> usize {
+        self.0
+    }
+}
+
+impl<N: Debug, E: Debug> Graph<N, E> {
+    pub fn new() -> Graph<N, E> {
+        Graph {
+            nodes: SnapshotVec::new(),
+            edges: SnapshotVec::new(),
+        }
+    }
+
+    pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> {
+        Graph {
+            nodes: SnapshotVec::with_capacity(nodes),
+            edges: SnapshotVec::with_capacity(edges),
+        }
+    }
+
+    // # Simple accessors
+
+    #[inline]
+    pub fn all_nodes(&self) -> &[Node<N>] {
+        &self.nodes
+    }
+
+    #[inline]
+    pub fn len_nodes(&self) -> usize {
+        self.nodes.len()
+    }
+
+    #[inline]
+    pub fn all_edges(&self) -> &[Edge<E>] {
+        &self.edges
+    }
+
+    #[inline]
+    pub fn len_edges(&self) -> usize {
+        self.edges.len()
+    }
+
+    // # Node construction
+
+    pub fn next_node_index(&self) -> NodeIndex {
+        NodeIndex(self.nodes.len())
+    }
+
+    pub fn add_node(&mut self, data: N) -> NodeIndex {
+        let idx = self.next_node_index();
+        self.nodes.push(Node {
+            first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
+            data,
+        });
+        idx
+    }
+
+    pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N {
+        &mut self.nodes[idx.0].data
+    }
+
+    pub fn node_data(&self, idx: NodeIndex) -> &N {
+        &self.nodes[idx.0].data
+    }
+
+    pub fn node(&self, idx: NodeIndex) -> &Node<N> {
+        &self.nodes[idx.0]
+    }
+
+    // # Edge construction and queries
+
+    pub fn next_edge_index(&self) -> EdgeIndex {
+        EdgeIndex(self.edges.len())
+    }
+
+    pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex {
+        debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
+
+        let idx = self.next_edge_index();
+
+        // read current first of the list of edges from each node
+        let source_first = self.nodes[source.0].first_edge[OUTGOING.repr];
+        let target_first = self.nodes[target.0].first_edge[INCOMING.repr];
+
+        // create the new edge, with the previous firsts from each node
+        // as the next pointers
+        self.edges.push(Edge {
+            next_edge: [source_first, target_first],
+            source,
+            target,
+            data,
+        });
+
+        // adjust the firsts for each node target be the next object.
+        self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
+        self.nodes[target.0].first_edge[INCOMING.repr] = idx;
+
+        idx
+    }
+
+    pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> {
+        &self.edges[idx.0]
+    }
+
+    // # Iterating over nodes, edges
+
+    pub fn enumerated_nodes(&self) -> impl Iterator<Item = (NodeIndex, &Node<N>)> {
+        self.nodes
+            .iter()
+            .enumerate()
+            .map(|(idx, n)| (NodeIndex(idx), n))
+    }
+
+    pub fn enumerated_edges(&self) -> impl Iterator<Item = (EdgeIndex, &Edge<E>)> {
+        self.edges
+            .iter()
+            .enumerate()
+            .map(|(idx, e)| (EdgeIndex(idx), e))
+    }
+
+    pub fn each_node<'a>(&'a self, mut f: impl FnMut(NodeIndex, &'a Node<N>) -> bool) -> bool {
+        //! Iterates over all edges defined in the graph.
+        self.enumerated_nodes()
+            .all(|(node_idx, node)| f(node_idx, node))
+    }
+
+    pub fn each_edge<'a>(&'a self, mut f: impl FnMut(EdgeIndex, &'a Edge<E>) -> bool) -> bool {
+        //! Iterates over all edges defined in the graph
+        self.enumerated_edges()
+            .all(|(edge_idx, edge)| f(edge_idx, edge))
+    }
+
+    pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
+        self.adjacent_edges(source, OUTGOING)
+    }
+
+    pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
+        self.adjacent_edges(source, INCOMING)
+    }
+
+    pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N, E> {
+        let first_edge = self.node(source).first_edge[direction.repr];
+        AdjacentEdges {
+            graph: self,
+            direction,
+            next: first_edge,
+        }
+    }
+
+    pub fn successor_nodes<'a>(
+        &'a self,
+        source: NodeIndex,
+    ) -> impl Iterator<Item = NodeIndex> + 'a {
+        self.outgoing_edges(source).targets()
+    }
+
+    pub fn predecessor_nodes<'a>(
+        &'a self,
+        target: NodeIndex,
+    ) -> impl Iterator<Item = NodeIndex> + 'a {
+        self.incoming_edges(target).sources()
+    }
+
+    pub fn depth_traverse<'a>(
+        &'a self,
+        start: NodeIndex,
+        direction: Direction,
+    ) -> DepthFirstTraversal<'a, N, E> {
+        DepthFirstTraversal::with_start_node(self, start, direction)
+    }
+
+    pub fn nodes_in_postorder(
+        &self,
+        direction: Direction,
+        entry_node: NodeIndex,
+    ) -> Vec<NodeIndex> {
+        let mut visited = BitArray::new(self.len_nodes());
+        let mut stack = vec![];
+        let mut result = Vec::with_capacity(self.len_nodes());
+        let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
+            if visited.insert(node.0) {
+                stack.push((node, self.adjacent_edges(node, direction)));
+            }
+        };
+
+        for node in Some(entry_node)
+            .into_iter()
+            .chain(self.enumerated_nodes().map(|(node, _)| node))
+        {
+            push_node(&mut stack, node);
+            while let Some((node, mut iter)) = stack.pop() {
+                if let Some((_, child)) = iter.next() {
+                    let target = child.source_or_target(direction);
+                    // the current node needs more processing, so
+                    // add it back to the stack
+                    stack.push((node, iter));
+                    // and then push the new node
+                    push_node(&mut stack, target);
+                } else {
+                    result.push(node);
+                }
+            }
+        }
+
+        assert_eq!(result.len(), self.len_nodes());
+        result
+    }
+}
+
+// # Iterators
+
+pub struct AdjacentEdges<'g, N, E>
+where
+    N: 'g,
+    E: 'g,
+{
+    graph: &'g Graph<N, E>,
+    direction: Direction,
+    next: EdgeIndex,
+}
+
+impl<'g, N: Debug, E: Debug> AdjacentEdges<'g, N, E> {
+    fn targets(self) -> impl Iterator<Item = NodeIndex> + 'g {
+        self.into_iter().map(|(_, edge)| edge.target)
+    }
+
+    fn sources(self) -> impl Iterator<Item = NodeIndex> + 'g {
+        self.into_iter().map(|(_, edge)| edge.source)
+    }
+}
+
+impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
+    type Item = (EdgeIndex, &'g Edge<E>);
+
+    fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
+        let edge_index = self.next;
+        if edge_index == INVALID_EDGE_INDEX {
+            return None;
+        }
+
+        let edge = self.graph.edge(edge_index);
+        self.next = edge.next_edge[self.direction.repr];
+        Some((edge_index, edge))
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        // At most, all the edges in the graph.
+        (0, Some(self.graph.len_edges()))
+    }
+}
+
+pub struct DepthFirstTraversal<'g, N, E>
+where
+    N: 'g,
+    E: 'g,
+{
+    graph: &'g Graph<N, E>,
+    stack: Vec<NodeIndex>,
+    visited: BitArray<usize>,
+    direction: Direction,
+}
+
+impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
+    pub fn with_start_node(
+        graph: &'g Graph<N, E>,
+        start_node: NodeIndex,
+        direction: Direction,
+    ) -> Self {
+        let mut visited = BitArray::new(graph.len_nodes());
+        visited.insert(start_node.node_id());
+        DepthFirstTraversal {
+            graph,
+            stack: vec![start_node],
+            visited,
+            direction,
+        }
+    }
+
+    fn visit(&mut self, node: NodeIndex) {
+        if self.visited.insert(node.node_id()) {
+            self.stack.push(node);
+        }
+    }
+}
+
+impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
+    type Item = NodeIndex;
+
+    fn next(&mut self) -> Option<NodeIndex> {
+        let next = self.stack.pop();
+        if let Some(idx) = next {
+            for (_, edge) in self.graph.adjacent_edges(idx, self.direction) {
+                let target = edge.source_or_target(self.direction);
+                self.visit(target);
+            }
+        }
+        next
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        // We will visit every node in the graph exactly once.
+        let remaining = self.graph.len_nodes() - self.visited.count();
+        (remaining, Some(remaining))
+    }
+}
+
+impl<'g, N: Debug, E: Debug> ExactSizeIterator for DepthFirstTraversal<'g, N, E> {}
+
+impl<E> Edge<E> {
+    pub fn source(&self) -> NodeIndex {
+        self.source
+    }
+
+    pub fn target(&self) -> NodeIndex {
+        self.target
+    }
+
+    pub fn source_or_target(&self, direction: Direction) -> NodeIndex {
+        if direction == OUTGOING {
+            self.target
+        } else {
+            self.source
+        }
+    }
+}
diff --git a/src/librustc_data_structures/graph/tests.rs b/src/librustc_data_structures/graph/implementation/tests.rs
index 007704357af..3814827b5df 100644
--- a/src/librustc_data_structures/graph/tests.rs
+++ b/src/librustc_data_structures/graph/implementation/tests.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use graph::*;
+use graph::implementation::*;
 use std::fmt::Debug;
 
 type TestGraph = Graph<&'static str, &'static str>;
diff --git a/src/librustc_data_structures/control_flow_graph/iterate/mod.rs b/src/librustc_data_structures/graph/iterate/mod.rs
index 2d70b406342..3afdc88d602 100644
--- a/src/librustc_data_structures/control_flow_graph/iterate/mod.rs
+++ b/src/librustc_data_structures/graph/iterate/mod.rs
@@ -8,20 +8,24 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use super::ControlFlowGraph;
 use super::super::indexed_vec::IndexVec;
+use super::{DirectedGraph, WithSuccessors, WithNumNodes};
 
 #[cfg(test)]
 mod test;
 
-pub fn post_order_from<G: ControlFlowGraph>(graph: &G, start_node: G::Node) -> Vec<G::Node> {
+pub fn post_order_from<G: DirectedGraph + WithSuccessors + WithNumNodes>(
+    graph: &G,
+    start_node: G::Node,
+) -> Vec<G::Node> {
     post_order_from_to(graph, start_node, None)
 }
 
-pub fn post_order_from_to<G: ControlFlowGraph>(graph: &G,
-                                               start_node: G::Node,
-                                               end_node: Option<G::Node>)
-                                               -> Vec<G::Node> {
+pub fn post_order_from_to<G: DirectedGraph + WithSuccessors + WithNumNodes>(
+    graph: &G,
+    start_node: G::Node,
+    end_node: Option<G::Node>,
+) -> Vec<G::Node> {
     let mut visited: IndexVec<G::Node, bool> = IndexVec::from_elem_n(false, graph.num_nodes());
     let mut result: Vec<G::Node> = Vec::with_capacity(graph.num_nodes());
     if let Some(end_node) = end_node {
@@ -31,10 +35,12 @@ pub fn post_order_from_to<G: ControlFlowGraph>(graph: &G,
     result
 }
 
-fn post_order_walk<G: ControlFlowGraph>(graph: &G,
-                                        node: G::Node,
-                                        result: &mut Vec<G::Node>,
-                                        visited: &mut IndexVec<G::Node, bool>) {
+fn post_order_walk<G: DirectedGraph + WithSuccessors + WithNumNodes>(
+    graph: &G,
+    node: G::Node,
+    result: &mut Vec<G::Node>,
+    visited: &mut IndexVec<G::Node, bool>,
+) {
     if visited[node] {
         return;
     }
@@ -47,7 +53,10 @@ fn post_order_walk<G: ControlFlowGraph>(graph: &G,
     result.push(node);
 }
 
-pub fn reverse_post_order<G: ControlFlowGraph>(graph: &G, start_node: G::Node) -> Vec<G::Node> {
+pub fn reverse_post_order<G: DirectedGraph + WithSuccessors + WithNumNodes>(
+    graph: &G,
+    start_node: G::Node,
+) -> Vec<G::Node> {
     let mut vec = post_order_from(graph, start_node);
     vec.reverse();
     vec
diff --git a/src/librustc_data_structures/control_flow_graph/iterate/test.rs b/src/librustc_data_structures/graph/iterate/test.rs
index 100881ddfdd..100881ddfdd 100644
--- a/src/librustc_data_structures/control_flow_graph/iterate/test.rs
+++ b/src/librustc_data_structures/graph/iterate/test.rs
diff --git a/src/librustc_data_structures/graph/mod.rs b/src/librustc_data_structures/graph/mod.rs
index 56d5f5ffa3f..7265e4e8c7c 100644
--- a/src/librustc_data_structures/graph/mod.rs
+++ b/src/librustc_data_structures/graph/mod.rs
@@ -1,4 +1,4 @@
-// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
+// 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.
 //
@@ -8,444 +8,72 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! A graph module for use in dataflow, region resolution, and elsewhere.
-//!
-//! # Interface details
-//!
-//! You customize the graph by specifying a "node data" type `N` and an
-//! "edge data" type `E`. You can then later gain access (mutable or
-//! immutable) to these "user-data" bits. Currently, you can only add
-//! nodes or edges to the graph. You cannot remove or modify them once
-//! added. This could be changed if we have a need.
-//!
-//! # Implementation details
-//!
-//! The main tricky thing about this code is the way that edges are
-//! stored. The edges are stored in a central array, but they are also
-//! threaded onto two linked lists for each node, one for incoming edges
-//! and one for outgoing edges. Note that every edge is a member of some
-//! incoming list and some outgoing list.  Basically you can load the
-//! first index of the linked list from the node data structures (the
-//! field `first_edge`) and then, for each edge, load the next index from
-//! the field `next_edge`). Each of those fields is an array that should
-//! be indexed by the direction (see the type `Direction`).
+use super::indexed_vec::Idx;
 
-use bitvec::BitVector;
-use std::fmt::Debug;
-use std::usize;
-use snapshot_vec::{SnapshotVec, SnapshotVecDelegate};
+pub mod dominators;
+pub mod implementation;
+pub mod iterate;
+mod reference;
+pub mod scc;
 
 #[cfg(test)]
-mod tests;
+mod test;
 
-pub struct Graph<N, E> {
-    nodes: SnapshotVec<Node<N>>,
-    edges: SnapshotVec<Edge<E>>,
+pub trait DirectedGraph {
+    type Node: Idx;
 }
 
-pub struct Node<N> {
-    first_edge: [EdgeIndex; 2], // see module comment
-    pub data: N,
+pub trait WithNumNodes: DirectedGraph {
+    fn num_nodes(&self) -> usize;
 }
 
-#[derive(Debug)]
-pub struct Edge<E> {
-    next_edge: [EdgeIndex; 2], // see module comment
-    source: NodeIndex,
-    target: NodeIndex,
-    pub data: E,
-}
-
-impl<N> SnapshotVecDelegate for Node<N> {
-    type Value = Node<N>;
-    type Undo = ();
-
-    fn reverse(_: &mut Vec<Node<N>>, _: ()) {}
-}
-
-impl<N> SnapshotVecDelegate for Edge<N> {
-    type Value = Edge<N>;
-    type Undo = ();
-
-    fn reverse(_: &mut Vec<Edge<N>>, _: ()) {}
-}
-
-#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
-pub struct NodeIndex(pub usize);
-
-#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
-pub struct EdgeIndex(pub usize);
-
-pub const INVALID_EDGE_INDEX: EdgeIndex = EdgeIndex(usize::MAX);
-
-// Use a private field here to guarantee no more instances are created:
-#[derive(Copy, Clone, Debug, PartialEq)]
-pub struct Direction {
-    repr: usize,
-}
-
-pub const OUTGOING: Direction = Direction { repr: 0 };
-
-pub const INCOMING: Direction = Direction { repr: 1 };
-
-impl NodeIndex {
-    /// Returns unique id (unique with respect to the graph holding associated node).
-    pub fn node_id(&self) -> usize {
-        self.0
-    }
-}
-
-impl<N: Debug, E: Debug> Graph<N, E> {
-    pub fn new() -> Graph<N, E> {
-        Graph {
-            nodes: SnapshotVec::new(),
-            edges: SnapshotVec::new(),
-        }
-    }
-
-    pub fn with_capacity(nodes: usize, edges: usize) -> Graph<N, E> {
-        Graph {
-            nodes: SnapshotVec::with_capacity(nodes),
-            edges: SnapshotVec::with_capacity(edges),
-        }
-    }
-
-    // # Simple accessors
-
-    #[inline]
-    pub fn all_nodes(&self) -> &[Node<N>] {
-        &self.nodes
-    }
-
-    #[inline]
-    pub fn len_nodes(&self) -> usize {
-        self.nodes.len()
-    }
-
-    #[inline]
-    pub fn all_edges(&self) -> &[Edge<E>] {
-        &self.edges
-    }
-
-    #[inline]
-    pub fn len_edges(&self) -> usize {
-        self.edges.len()
-    }
-
-    // # Node construction
-
-    pub fn next_node_index(&self) -> NodeIndex {
-        NodeIndex(self.nodes.len())
-    }
-
-    pub fn add_node(&mut self, data: N) -> NodeIndex {
-        let idx = self.next_node_index();
-        self.nodes.push(Node {
-            first_edge: [INVALID_EDGE_INDEX, INVALID_EDGE_INDEX],
-            data,
-        });
-        idx
-    }
-
-    pub fn mut_node_data(&mut self, idx: NodeIndex) -> &mut N {
-        &mut self.nodes[idx.0].data
-    }
-
-    pub fn node_data(&self, idx: NodeIndex) -> &N {
-        &self.nodes[idx.0].data
-    }
-
-    pub fn node(&self, idx: NodeIndex) -> &Node<N> {
-        &self.nodes[idx.0]
-    }
-
-    // # Edge construction and queries
-
-    pub fn next_edge_index(&self) -> EdgeIndex {
-        EdgeIndex(self.edges.len())
-    }
-
-    pub fn add_edge(&mut self, source: NodeIndex, target: NodeIndex, data: E) -> EdgeIndex {
-        debug!("graph: add_edge({:?}, {:?}, {:?})", source, target, data);
-
-        let idx = self.next_edge_index();
-
-        // read current first of the list of edges from each node
-        let source_first = self.nodes[source.0].first_edge[OUTGOING.repr];
-        let target_first = self.nodes[target.0].first_edge[INCOMING.repr];
-
-        // create the new edge, with the previous firsts from each node
-        // as the next pointers
-        self.edges.push(Edge {
-            next_edge: [source_first, target_first],
-            source,
-            target,
-            data,
-        });
-
-        // adjust the firsts for each node target be the next object.
-        self.nodes[source.0].first_edge[OUTGOING.repr] = idx;
-        self.nodes[target.0].first_edge[INCOMING.repr] = idx;
-
-        return idx;
-    }
-
-    pub fn edge(&self, idx: EdgeIndex) -> &Edge<E> {
-        &self.edges[idx.0]
-    }
-
-    // # Iterating over nodes, edges
-
-    pub fn enumerated_nodes(&self) -> EnumeratedNodes<N> {
-        EnumeratedNodes {
-            iter: self.nodes.iter().enumerate()
-        }
-    }
-
-    pub fn enumerated_edges(&self) -> EnumeratedEdges<E> {
-        EnumeratedEdges {
-            iter: self.edges.iter().enumerate()
-        }
-    }
-
-    pub fn each_node<'a, F>(&'a self, mut f: F) -> bool
-        where F: FnMut(NodeIndex, &'a Node<N>) -> bool
-    {
-        //! Iterates over all edges defined in the graph.
-        self.enumerated_nodes().all(|(node_idx, node)| f(node_idx, node))
-    }
-
-    pub fn each_edge<'a, F>(&'a self, mut f: F) -> bool
-        where F: FnMut(EdgeIndex, &'a Edge<E>) -> bool
-    {
-        //! Iterates over all edges defined in the graph
-        self.enumerated_edges().all(|(edge_idx, edge)| f(edge_idx, edge))
-    }
-
-    pub fn outgoing_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
-        self.adjacent_edges(source, OUTGOING)
-    }
-
-    pub fn incoming_edges(&self, source: NodeIndex) -> AdjacentEdges<N, E> {
-        self.adjacent_edges(source, INCOMING)
-    }
-
-    pub fn adjacent_edges(&self, source: NodeIndex, direction: Direction) -> AdjacentEdges<N, E> {
-        let first_edge = self.node(source).first_edge[direction.repr];
-        AdjacentEdges {
-            graph: self,
-            direction,
-            next: first_edge,
-        }
-    }
-
-    pub fn successor_nodes(&self, source: NodeIndex) -> AdjacentTargets<N, E> {
-        self.outgoing_edges(source).targets()
-    }
-
-    pub fn predecessor_nodes(&self, target: NodeIndex) -> AdjacentSources<N, E> {
-        self.incoming_edges(target).sources()
-    }
-
-    pub fn depth_traverse<'a>(&'a self,
-                              start: NodeIndex,
-                              direction: Direction)
-                              -> DepthFirstTraversal<'a, N, E> {
-        DepthFirstTraversal::with_start_node(self, start, direction)
-    }
-
-    pub fn nodes_in_postorder<'a>(&'a self,
-                                  direction: Direction,
-                                  entry_node: NodeIndex)
-                                  -> Vec<NodeIndex>
-    {
-        let mut visited = BitVector::new(self.len_nodes());
-        let mut stack = vec![];
-        let mut result = Vec::with_capacity(self.len_nodes());
-        let mut push_node = |stack: &mut Vec<_>, node: NodeIndex| {
-            if visited.insert(node.0) {
-                stack.push((node, self.adjacent_edges(node, direction)));
-            }
-        };
-
-        for node in Some(entry_node).into_iter()
-            .chain(self.enumerated_nodes().map(|(node, _)| node))
-        {
-            push_node(&mut stack, node);
-            while let Some((node, mut iter)) = stack.pop() {
-                if let Some((_, child)) = iter.next() {
-                    let target = child.source_or_target(direction);
-                    // the current node needs more processing, so
-                    // add it back to the stack
-                    stack.push((node, iter));
-                    // and then push the new node
-                    push_node(&mut stack, target);
-                } else {
-                    result.push(node);
-                }
-            }
-        }
-
-        assert_eq!(result.len(), self.len_nodes());
-        result
-    }
-}
-
-// # Iterators
-
-pub struct EnumeratedNodes<'g, N>
-    where N: 'g,
-{
-    iter: ::std::iter::Enumerate<::std::slice::Iter<'g, Node<N>>>
-}
-
-impl<'g, N: Debug> Iterator for EnumeratedNodes<'g, N> {
-    type Item = (NodeIndex, &'g Node<N>);
-
-    fn next(&mut self) -> Option<(NodeIndex, &'g Node<N>)> {
-        self.iter.next().map(|(idx, n)| (NodeIndex(idx), n))
-    }
-}
-
-pub struct EnumeratedEdges<'g, E>
-    where E: 'g,
+pub trait WithSuccessors: DirectedGraph
+where
+    Self: for<'graph> GraphSuccessors<'graph, Item = <Self as DirectedGraph>::Node>,
 {
-    iter: ::std::iter::Enumerate<::std::slice::Iter<'g, Edge<E>>>
+    fn successors<'graph>(
+        &'graph self,
+        node: Self::Node,
+    ) -> <Self as GraphSuccessors<'graph>>::Iter;
 }
 
-impl<'g, E: Debug> Iterator for EnumeratedEdges<'g, E> {
-    type Item = (EdgeIndex, &'g Edge<E>);
-
-    fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
-        self.iter.next().map(|(idx, e)| (EdgeIndex(idx), e))
-    }
+pub trait GraphSuccessors<'graph> {
+    type Item;
+    type Iter: Iterator<Item = Self::Item>;
 }
 
-pub struct AdjacentEdges<'g, N, E>
-    where N: 'g,
-          E: 'g
+pub trait WithPredecessors: DirectedGraph
+where
+    Self: for<'graph> GraphPredecessors<'graph, Item = <Self as DirectedGraph>::Node>,
 {
-    graph: &'g Graph<N, E>,
-    direction: Direction,
-    next: EdgeIndex,
-}
-
-impl<'g, N, E> AdjacentEdges<'g, N, E> {
-    fn targets(self) -> AdjacentTargets<'g, N, E> {
-        AdjacentTargets { edges: self }
-    }
-
-    fn sources(self) -> AdjacentSources<'g, N, E> {
-        AdjacentSources { edges: self }
-    }
+    fn predecessors<'graph>(
+        &'graph self,
+        node: Self::Node,
+    ) -> <Self as GraphPredecessors<'graph>>::Iter;
 }
 
-impl<'g, N: Debug, E: Debug> Iterator for AdjacentEdges<'g, N, E> {
-    type Item = (EdgeIndex, &'g Edge<E>);
-
-    fn next(&mut self) -> Option<(EdgeIndex, &'g Edge<E>)> {
-        let edge_index = self.next;
-        if edge_index == INVALID_EDGE_INDEX {
-            return None;
-        }
-
-        let edge = self.graph.edge(edge_index);
-        self.next = edge.next_edge[self.direction.repr];
-        Some((edge_index, edge))
-    }
+pub trait GraphPredecessors<'graph> {
+    type Item;
+    type Iter: Iterator<Item = Self::Item>;
 }
 
-pub struct AdjacentTargets<'g, N, E>
-    where N: 'g,
-          E: 'g
-{
-    edges: AdjacentEdges<'g, N, E>,
+pub trait WithStartNode: DirectedGraph {
+    fn start_node(&self) -> Self::Node;
 }
 
-impl<'g, N: Debug, E: Debug> Iterator for AdjacentTargets<'g, N, E> {
-    type Item = NodeIndex;
-
-    fn next(&mut self) -> Option<NodeIndex> {
-        self.edges.next().map(|(_, edge)| edge.target)
-    }
-}
-
-pub struct AdjacentSources<'g, N, E>
-    where N: 'g,
-          E: 'g
+pub trait ControlFlowGraph:
+    DirectedGraph + WithStartNode + WithPredecessors + WithStartNode + WithSuccessors + WithNumNodes
 {
-    edges: AdjacentEdges<'g, N, E>,
-}
-
-impl<'g, N: Debug, E: Debug> Iterator for AdjacentSources<'g, N, E> {
-    type Item = NodeIndex;
-
-    fn next(&mut self) -> Option<NodeIndex> {
-        self.edges.next().map(|(_, edge)| edge.source)
-    }
+    // convenient trait
 }
 
-pub struct DepthFirstTraversal<'g, N, E>
-    where N: 'g,
-          E: 'g
+impl<T> ControlFlowGraph for T
+where
+    T: DirectedGraph
+        + WithStartNode
+        + WithPredecessors
+        + WithStartNode
+        + WithSuccessors
+        + WithNumNodes,
 {
-    graph: &'g Graph<N, E>,
-    stack: Vec<NodeIndex>,
-    visited: BitVector,
-    direction: Direction,
-}
-
-impl<'g, N: Debug, E: Debug> DepthFirstTraversal<'g, N, E> {
-    pub fn with_start_node(graph: &'g Graph<N, E>,
-                           start_node: NodeIndex,
-                           direction: Direction)
-                           -> Self {
-        let mut visited = BitVector::new(graph.len_nodes());
-        visited.insert(start_node.node_id());
-        DepthFirstTraversal {
-            graph,
-            stack: vec![start_node],
-            visited,
-            direction,
-        }
-    }
-
-    fn visit(&mut self, node: NodeIndex) {
-        if self.visited.insert(node.node_id()) {
-            self.stack.push(node);
-        }
-    }
-}
-
-impl<'g, N: Debug, E: Debug> Iterator for DepthFirstTraversal<'g, N, E> {
-    type Item = NodeIndex;
-
-    fn next(&mut self) -> Option<NodeIndex> {
-        let next = self.stack.pop();
-        if let Some(idx) = next {
-            for (_, edge) in self.graph.adjacent_edges(idx, self.direction) {
-                let target = edge.source_or_target(self.direction);
-                self.visit(target);
-            }
-        }
-        next
-    }
-}
-
-impl<E> Edge<E> {
-    pub fn source(&self) -> NodeIndex {
-        self.source
-    }
-
-    pub fn target(&self) -> NodeIndex {
-        self.target
-    }
-
-    pub fn source_or_target(&self, direction: Direction) -> NodeIndex {
-        if direction == OUTGOING {
-            self.target
-        } else {
-            self.source
-        }
-    }
 }
diff --git a/src/librustc_data_structures/control_flow_graph/reference.rs b/src/librustc_data_structures/graph/reference.rs
index 3b8b01f2ff4..a7b763db8da 100644
--- a/src/librustc_data_structures/control_flow_graph/reference.rs
+++ b/src/librustc_data_structures/graph/reference.rs
@@ -10,34 +10,42 @@
 
 use super::*;
 
-impl<'graph, G: ControlFlowGraph> ControlFlowGraph for &'graph G {
+impl<'graph, G: DirectedGraph> DirectedGraph for &'graph G {
     type Node = G::Node;
+}
 
+impl<'graph, G: WithNumNodes> WithNumNodes for &'graph G {
     fn num_nodes(&self) -> usize {
         (**self).num_nodes()
     }
+}
 
+impl<'graph, G: WithStartNode> WithStartNode for &'graph G {
     fn start_node(&self) -> Self::Node {
         (**self).start_node()
     }
+}
+
+impl<'graph, G: WithSuccessors> WithSuccessors for &'graph G {
+    fn successors<'iter>(&'iter self, node: Self::Node) -> <Self as GraphSuccessors<'iter>>::Iter {
+        (**self).successors(node)
+    }
+}
 
+impl<'graph, G: WithPredecessors> WithPredecessors for &'graph G {
     fn predecessors<'iter>(&'iter self,
                            node: Self::Node)
                            -> <Self as GraphPredecessors<'iter>>::Iter {
         (**self).predecessors(node)
     }
-
-    fn successors<'iter>(&'iter self, node: Self::Node) -> <Self as GraphSuccessors<'iter>>::Iter {
-        (**self).successors(node)
-    }
 }
 
-impl<'iter, 'graph, G: ControlFlowGraph> GraphPredecessors<'iter> for &'graph G {
+impl<'iter, 'graph, G: WithPredecessors> GraphPredecessors<'iter> for &'graph G {
     type Item = G::Node;
     type Iter = <G as GraphPredecessors<'iter>>::Iter;
 }
 
-impl<'iter, 'graph, G: ControlFlowGraph> GraphSuccessors<'iter> for &'graph G {
+impl<'iter, 'graph, G: WithSuccessors> GraphSuccessors<'iter> for &'graph G {
     type Item = G::Node;
     type Iter = <G as GraphSuccessors<'iter>>::Iter;
 }
diff --git a/src/librustc_data_structures/graph/scc/mod.rs b/src/librustc_data_structures/graph/scc/mod.rs
new file mode 100644
index 00000000000..a989a540102
--- /dev/null
+++ b/src/librustc_data_structures/graph/scc/mod.rs
@@ -0,0 +1,361 @@
+// Copyright 2017 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.
+
+//! Routine to compute the strongly connected components (SCCs) of a
+//! graph, as well as the resulting DAG if each SCC is replaced with a
+//! node in the graph. This uses Tarjan's algorithm that completes in
+//! O(n) time.
+
+use fx::FxHashSet;
+use graph::{DirectedGraph, WithNumNodes, WithSuccessors};
+use indexed_vec::{Idx, IndexVec};
+use std::ops::Range;
+
+mod test;
+
+/// Strongly connected components (SCC) of a graph. The type `N` is
+/// the index type for the graph nodes and `S` is the index type for
+/// the SCCs. We can map from each node to the SCC that it
+/// participates in, and we also have the successors of each SCC.
+pub struct Sccs<N: Idx, S: Idx> {
+    /// For each node, what is the SCC index of the SCC to which it
+    /// belongs.
+    scc_indices: IndexVec<N, S>,
+
+    /// Data about each SCC.
+    scc_data: SccData<S>,
+}
+
+struct SccData<S: Idx> {
+    /// For each SCC, the range of `all_successors` where its
+    /// successors can be found.
+    ranges: IndexVec<S, Range<usize>>,
+
+    /// Contains the succcessors for all the Sccs, concatenated. The
+    /// range of indices corresponding to a given SCC is found in its
+    /// SccData.
+    all_successors: Vec<S>,
+}
+
+impl<N: Idx, S: Idx> Sccs<N, S> {
+    pub fn new(graph: &(impl DirectedGraph<Node = N> + WithNumNodes + WithSuccessors)) -> Self {
+        SccsConstruction::construct(graph)
+    }
+
+    /// Returns the number of SCCs in the graph.
+    pub fn num_sccs(&self) -> usize {
+        self.scc_data.len()
+    }
+
+    /// Returns an iterator over the SCCs in the graph.
+    pub fn all_sccs(&self) -> impl Iterator<Item = S> {
+        (0 .. self.scc_data.len()).map(S::new)
+    }
+
+    /// Returns the SCC to which a node `r` belongs.
+    pub fn scc(&self, r: N) -> S {
+        self.scc_indices[r]
+    }
+
+    /// Returns the successors of the given SCC.
+    pub fn successors(&self, scc: S) -> &[S] {
+        self.scc_data.successors(scc)
+    }
+}
+
+impl<S: Idx> SccData<S> {
+    /// Number of SCCs,
+    fn len(&self) -> usize {
+        self.ranges.len()
+    }
+
+    /// Returns the successors of the given SCC.
+    fn successors(&self, scc: S) -> &[S] {
+        // Annoyingly, `range` does not implement `Copy`, so we have
+        // to do `range.start..range.end`:
+        let range = &self.ranges[scc];
+        &self.all_successors[range.start..range.end]
+    }
+
+    /// Creates a new SCC with `successors` as its successors and
+    /// returns the resulting index.
+    fn create_scc(&mut self, successors: impl IntoIterator<Item = S>) -> S {
+        // Store the successors on `scc_successors_vec`, remembering
+        // the range of indices.
+        let all_successors_start = self.all_successors.len();
+        self.all_successors.extend(successors);
+        let all_successors_end = self.all_successors.len();
+
+        debug!(
+            "create_scc({:?}) successors={:?}",
+            self.ranges.len(),
+            &self.all_successors[all_successors_start..all_successors_end],
+        );
+
+        self.ranges.push(all_successors_start..all_successors_end)
+    }
+}
+
+struct SccsConstruction<'c, G: DirectedGraph + WithNumNodes + WithSuccessors + 'c, S: Idx> {
+    graph: &'c G,
+
+    /// The state of each node; used during walk to record the stack
+    /// and after walk to record what cycle each node ended up being
+    /// in.
+    node_states: IndexVec<G::Node, NodeState<G::Node, S>>,
+
+    /// The stack of nodes that we are visiting as part of the DFS.
+    node_stack: Vec<G::Node>,
+
+    /// The stack of successors: as we visit a node, we mark our
+    /// position in this stack, and when we encounter a successor SCC,
+    /// we push it on the stack. When we complete an SCC, we can pop
+    /// everything off the stack that was found along the way.
+    successors_stack: Vec<S>,
+
+    /// A set used to strip duplicates. As we accumulate successors
+    /// into the successors_stack, we sometimes get duplicate entries.
+    /// We use this set to remove those -- we also keep its storage
+    /// around between successors to amortize memory allocation costs.
+    duplicate_set: FxHashSet<S>,
+
+    scc_data: SccData<S>,
+}
+
+#[derive(Copy, Clone, Debug)]
+enum NodeState<N, S> {
+    /// This node has not yet been visited as part of the DFS.
+    ///
+    /// After SCC construction is complete, this state ought to be
+    /// impossible.
+    NotVisited,
+
+    /// This node is currently being walk as part of our DFS. It is on
+    /// the stack at the depth `depth`.
+    ///
+    /// After SCC construction is complete, this state ought to be
+    /// impossible.
+    BeingVisited { depth: usize },
+
+    /// Indicates that this node is a member of the given cycle.
+    InCycle { scc_index: S },
+
+    /// Indicates that this node is a member of whatever cycle
+    /// `parent` is a member of. This state is transient: whenever we
+    /// see it, we try to overwrite it with the current state of
+    /// `parent` (this is the "path compression" step of a union-find
+    /// algorithm).
+    InCycleWith { parent: N },
+}
+
+#[derive(Copy, Clone, Debug)]
+enum WalkReturn<S> {
+    Cycle { min_depth: usize },
+    Complete { scc_index: S },
+}
+
+impl<'c, G, S> SccsConstruction<'c, G, S>
+where
+    G: DirectedGraph + WithNumNodes + WithSuccessors,
+    S: Idx,
+{
+    /// Identifies SCCs in the graph `G` and computes the resulting
+    /// DAG. This uses a variant of [Tarjan's
+    /// algorithm][wikipedia]. The high-level summary of the algorithm
+    /// is that we do a depth-first search. Along the way, we keep a
+    /// stack of each node whose successors are being visited. We
+    /// track the depth of each node on this stack (there is no depth
+    /// if the node is not on the stack). When we find that some node
+    /// N with depth D can reach some other node N' with lower depth
+    /// D' (i.e., D' < D), we know that N, N', and all nodes in
+    /// between them on the stack are part of an SCC.
+    ///
+    /// [wikipedia]: https://bit.ly/2EZIx84
+    fn construct(graph: &'c G) -> Sccs<G::Node, S> {
+        let num_nodes = graph.num_nodes();
+
+        let mut this = Self {
+            graph,
+            node_states: IndexVec::from_elem_n(NodeState::NotVisited, num_nodes),
+            node_stack: Vec::with_capacity(num_nodes),
+            successors_stack: Vec::new(),
+            scc_data: SccData {
+                ranges: IndexVec::new(),
+                all_successors: Vec::new(),
+            },
+            duplicate_set: FxHashSet::default(),
+        };
+
+        let scc_indices = (0..num_nodes)
+            .map(G::Node::new)
+            .map(|node| match this.walk_node(0, node) {
+                WalkReturn::Complete { scc_index } => scc_index,
+                WalkReturn::Cycle { min_depth } => panic!(
+                    "`walk_node(0, {:?})` returned cycle with depth {:?}",
+                    node, min_depth
+                ),
+            })
+            .collect();
+
+        Sccs {
+            scc_indices,
+            scc_data: this.scc_data,
+        }
+    }
+
+    /// Visit a node during the DFS. We first examine its current
+    /// state -- if it is not yet visited (`NotVisited`), we can push
+    /// it onto the stack and start walking its successors.
+    ///
+    /// If it is already on the DFS stack it will be in the state
+    /// `BeingVisited`. In that case, we have found a cycle and we
+    /// return the depth from the stack.
+    ///
+    /// Otherwise, we are looking at a node that has already been
+    /// completely visited. We therefore return `WalkReturn::Complete`
+    /// with its associated SCC index.
+    fn walk_node(&mut self, depth: usize, node: G::Node) -> WalkReturn<S> {
+        debug!("walk_node(depth = {:?}, node = {:?})", depth, node);
+        match self.find_state(node) {
+            NodeState::InCycle { scc_index } => WalkReturn::Complete { scc_index },
+
+            NodeState::BeingVisited { depth: min_depth } => WalkReturn::Cycle { min_depth },
+
+            NodeState::NotVisited => self.walk_unvisited_node(depth, node),
+
+            NodeState::InCycleWith { parent } => panic!(
+                "`find_state` returned `InCycleWith({:?})`, which ought to be impossible",
+                parent
+            ),
+        }
+    }
+
+    /// Fetches the state of the node `r`. If `r` is recorded as being
+    /// in a cycle with some other node `r2`, then fetches the state
+    /// of `r2` (and updates `r` to reflect current result). This is
+    /// basically the "find" part of a standard union-find algorithm
+    /// (with path compression).
+    fn find_state(&mut self, r: G::Node) -> NodeState<G::Node, S> {
+        debug!("find_state(r = {:?} in state {:?})", r, self.node_states[r]);
+        match self.node_states[r] {
+            NodeState::InCycle { scc_index } => NodeState::InCycle { scc_index },
+            NodeState::BeingVisited { depth } => NodeState::BeingVisited { depth },
+            NodeState::NotVisited => NodeState::NotVisited,
+            NodeState::InCycleWith { parent } => {
+                let parent_state = self.find_state(parent);
+                debug!("find_state: parent_state = {:?}", parent_state);
+                match parent_state {
+                    NodeState::InCycle { .. } => {
+                        self.node_states[r] = parent_state;
+                        parent_state
+                    }
+
+                    NodeState::BeingVisited { depth } => {
+                        self.node_states[r] = NodeState::InCycleWith {
+                            parent: self.node_stack[depth],
+                        };
+                        parent_state
+                    }
+
+                    NodeState::NotVisited | NodeState::InCycleWith { .. } => {
+                        panic!("invalid parent state: {:?}", parent_state)
+                    }
+                }
+            }
+        }
+    }
+
+    /// Walks a node that has never been visited before.
+    fn walk_unvisited_node(&mut self, depth: usize, node: G::Node) -> WalkReturn<S> {
+        debug!(
+            "walk_unvisited_node(depth = {:?}, node = {:?})",
+            depth, node
+        );
+
+        debug_assert!(match self.node_states[node] {
+            NodeState::NotVisited => true,
+            _ => false,
+        });
+
+        // Push `node` onto the stack.
+        self.node_states[node] = NodeState::BeingVisited { depth };
+        self.node_stack.push(node);
+
+        // Walk each successor of the node, looking to see if any of
+        // them can reach a node that is presently on the stack. If
+        // so, that means they can also reach us.
+        let mut min_depth = depth;
+        let mut min_cycle_root = node;
+        let successors_len = self.successors_stack.len();
+        for successor_node in self.graph.successors(node) {
+            debug!(
+                "walk_unvisited_node: node = {:?} successor_ode = {:?}",
+                node, successor_node
+            );
+            match self.walk_node(depth + 1, successor_node) {
+                WalkReturn::Cycle {
+                    min_depth: successor_min_depth,
+                } => {
+                    // Track the minimum depth we can reach.
+                    assert!(successor_min_depth <= depth);
+                    if successor_min_depth < min_depth {
+                        debug!(
+                            "walk_unvisited_node: node = {:?} successor_min_depth = {:?}",
+                            node, successor_min_depth
+                        );
+                        min_depth = successor_min_depth;
+                        min_cycle_root = successor_node;
+                    }
+                }
+
+                WalkReturn::Complete {
+                    scc_index: successor_scc_index,
+                } => {
+                    // Push the completed SCC indices onto
+                    // the `successors_stack` for later.
+                    debug!(
+                        "walk_unvisited_node: node = {:?} successor_scc_index = {:?}",
+                        node, successor_scc_index
+                    );
+                    self.successors_stack.push(successor_scc_index);
+                }
+            }
+        }
+
+        // Completed walk, remove `node` from the stack.
+        let r = self.node_stack.pop();
+        debug_assert_eq!(r, Some(node));
+
+        // If `min_depth == depth`, then we are the root of the
+        // cycle: we can't reach anyone further down the stack.
+        if min_depth == depth {
+            // Note that successor stack may have duplicates, so we
+            // want to remove those:
+            let deduplicated_successors = {
+                let duplicate_set = &mut self.duplicate_set;
+                duplicate_set.clear();
+                self.successors_stack
+                    .drain(successors_len..)
+                    .filter(move |&i| duplicate_set.insert(i))
+            };
+            let scc_index = self.scc_data.create_scc(deduplicated_successors);
+            self.node_states[node] = NodeState::InCycle { scc_index };
+            WalkReturn::Complete { scc_index }
+        } else {
+            // We are not the head of the cycle. Return back to our
+            // caller. They will take ownership of the
+            // `self.successors` data that we pushed.
+            self.node_states[node] = NodeState::InCycleWith {
+                parent: min_cycle_root,
+            };
+            WalkReturn::Cycle { min_depth }
+        }
+    }
+}
diff --git a/src/librustc_data_structures/graph/scc/test.rs b/src/librustc_data_structures/graph/scc/test.rs
new file mode 100644
index 00000000000..405e1b3a617
--- /dev/null
+++ b/src/librustc_data_structures/graph/scc/test.rs
@@ -0,0 +1,180 @@
+// 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.
+
+#![cfg(test)]
+
+use graph::test::TestGraph;
+use super::*;
+
+#[test]
+fn diamond() {
+    let graph = TestGraph::new(0, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 4);
+    assert_eq!(sccs.num_sccs(), 4);
+}
+
+#[test]
+fn test_big_scc() {
+    // The order in which things will be visited is important to this
+    // test.
+    //
+    // We will visit:
+    //
+    // 0 -> 1 -> 2 -> 0
+    //
+    // and at this point detect a cycle. 2 will return back to 1 which
+    // will visit 3. 3 will visit 2 before the cycle is complete, and
+    // hence it too will return a cycle.
+
+    /*
++-> 0
+|   |
+|   v
+|   1 -> 3
+|   |    |
+|   v    |
++-- 2 <--+
+     */
+    let graph = TestGraph::new(0, &[
+        (0, 1),
+        (1, 2),
+        (1, 3),
+        (2, 0),
+        (3, 2),
+    ]);
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 1);
+}
+
+#[test]
+fn test_three_sccs() {
+    /*
+    0
+    |
+    v
++-> 1    3
+|   |    |
+|   v    |
++-- 2 <--+
+     */
+    let graph = TestGraph::new(0, &[
+        (0, 1),
+        (1, 2),
+        (2, 1),
+        (3, 2),
+    ]);
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 3);
+    assert_eq!(sccs.scc(0), 1);
+    assert_eq!(sccs.scc(1), 0);
+    assert_eq!(sccs.scc(2), 0);
+    assert_eq!(sccs.scc(3), 2);
+    assert_eq!(sccs.successors(0), &[]);
+    assert_eq!(sccs.successors(1), &[0]);
+    assert_eq!(sccs.successors(2), &[0]);
+}
+
+#[test]
+fn test_find_state_2() {
+    // The order in which things will be visited is important to this
+    // test. It tests part of the `find_state` behavior. Here is the
+    // graph:
+    //
+    //
+    //       /----+
+    //     0 <--+ |
+    //     |    | |
+    //     v    | |
+    // +-> 1 -> 3 4
+    // |   |      |
+    // |   v      |
+    // +-- 2 <----+
+
+    let graph = TestGraph::new(0, &[
+        (0, 1),
+        (0, 4),
+        (1, 2),
+        (1, 3),
+        (2, 1),
+        (3, 0),
+        (4, 2),
+    ]);
+
+    // For this graph, we will start in our DFS by visiting:
+    //
+    // 0 -> 1 -> 2 -> 1
+    //
+    // and at this point detect a cycle. The state of 2 will thus be
+    // `InCycleWith { 1 }`.  We will then visit the 1 -> 3 edge, which
+    // will attempt to visit 0 as well, thus going to the state
+    // `InCycleWith { 0 }`. Finally, node 1 will complete; the lowest
+    // depth of any successor was 3 which had depth 0, and thus it
+    // will be in the state `InCycleWith { 3 }`.
+    //
+    // When we finally traverse the `0 -> 4` edge and then visit node 2,
+    // the states of the nodes are:
+    //
+    // 0 BeingVisited { 0 }
+    // 1 InCycleWith { 3 }
+    // 2 InCycleWith { 1 }
+    // 3 InCycleWith { 0 }
+    //
+    // and hence 4 will traverse the links, finding an ultimate depth of 0.
+    // If will also collapse the states to the following:
+    //
+    // 0 BeingVisited { 0 }
+    // 1 InCycleWith { 3 }
+    // 2 InCycleWith { 1 }
+    // 3 InCycleWith { 0 }
+
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 1);
+    assert_eq!(sccs.scc(0), 0);
+    assert_eq!(sccs.scc(1), 0);
+    assert_eq!(sccs.scc(2), 0);
+    assert_eq!(sccs.scc(3), 0);
+    assert_eq!(sccs.scc(4), 0);
+    assert_eq!(sccs.successors(0), &[]);
+}
+
+#[test]
+fn test_find_state_3() {
+    /*
+      /----+
+    0 <--+ |
+    |    | |
+    v    | |
++-> 1 -> 3 4 5
+|   |      | |
+|   v      | |
++-- 2 <----+-+
+     */
+    let graph = TestGraph::new(0, &[
+        (0, 1),
+        (0, 4),
+        (1, 2),
+        (1, 3),
+        (2, 1),
+        (3, 0),
+        (4, 2),
+        (5, 2),
+    ]);
+    let sccs: Sccs<_, usize> = Sccs::new(&graph);
+    assert_eq!(sccs.num_sccs(), 2);
+    assert_eq!(sccs.scc(0), 0);
+    assert_eq!(sccs.scc(1), 0);
+    assert_eq!(sccs.scc(2), 0);
+    assert_eq!(sccs.scc(3), 0);
+    assert_eq!(sccs.scc(4), 0);
+    assert_eq!(sccs.scc(5), 1);
+    assert_eq!(sccs.successors(0), &[]);
+    assert_eq!(sccs.successors(1), &[0]);
+}
diff --git a/src/librustc_data_structures/control_flow_graph/test.rs b/src/librustc_data_structures/graph/test.rs
index f04b536bc18..b72d011c99b 100644
--- a/src/librustc_data_structures/control_flow_graph/test.rs
+++ b/src/librustc_data_structures/graph/test.rs
@@ -13,7 +13,7 @@ use std::cmp::max;
 use std::slice;
 use std::iter;
 
-use super::{ControlFlowGraph, GraphPredecessors, GraphSuccessors};
+use super::*;
 
 pub struct TestGraph {
     num_nodes: usize,
@@ -33,34 +33,42 @@ impl TestGraph {
         for &(source, target) in edges {
             graph.num_nodes = max(graph.num_nodes, source + 1);
             graph.num_nodes = max(graph.num_nodes, target + 1);
-            graph.successors.entry(source).or_insert(vec![]).push(target);
-            graph.predecessors.entry(target).or_insert(vec![]).push(source);
+            graph.successors.entry(source).or_default().push(target);
+            graph.predecessors.entry(target).or_default().push(source);
         }
         for node in 0..graph.num_nodes {
-            graph.successors.entry(node).or_insert(vec![]);
-            graph.predecessors.entry(node).or_insert(vec![]);
+            graph.successors.entry(node).or_default();
+            graph.predecessors.entry(node).or_default();
         }
         graph
     }
 }
 
-impl ControlFlowGraph for TestGraph {
+impl DirectedGraph for TestGraph {
     type Node = usize;
+}
 
+impl WithStartNode for TestGraph {
     fn start_node(&self) -> usize {
         self.start_node
     }
+}
 
+impl WithNumNodes for TestGraph {
     fn num_nodes(&self) -> usize {
         self.num_nodes
     }
+}
 
+impl WithPredecessors for TestGraph {
     fn predecessors<'graph>(&'graph self,
                             node: usize)
                             -> <Self as GraphPredecessors<'graph>>::Iter {
         self.predecessors[&node].iter().cloned()
     }
+}
 
+impl WithSuccessors for TestGraph {
     fn successors<'graph>(&'graph self, node: usize) -> <Self as GraphSuccessors<'graph>>::Iter {
         self.successors[&node].iter().cloned()
     }
diff --git a/src/librustc_data_structures/indexed_set.rs b/src/librustc_data_structures/indexed_set.rs
index 223e08de826..a7672d1ffe8 100644
--- a/src/librustc_data_structures/indexed_set.rs
+++ b/src/librustc_data_structures/indexed_set.rs
@@ -8,6 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use array_vec::ArrayVec;
 use std::borrow::{Borrow, BorrowMut, ToOwned};
 use std::fmt;
 use std::iter;
@@ -25,6 +26,8 @@ use rustc_serialize;
 ///
 /// In other words, `T` is the type used to index into the bitvector
 /// this type uses to represent the set of object it holds.
+///
+/// The representation is dense, using one bit per possible element.
 #[derive(Eq, PartialEq)]
 pub struct IdxSetBuf<T: Idx> {
     _pd: PhantomData<fn(&T)>,
@@ -59,16 +62,13 @@ impl<T: Idx> rustc_serialize::Decodable for IdxSetBuf<T> {
 
 // pnkfelix wants to have this be `IdxSet<T>([Word]) and then pass
 // around `&mut IdxSet<T>` or `&IdxSet<T>`.
-//
-// WARNING: Mapping a `&IdxSetBuf<T>` to `&IdxSet<T>` (at least today)
-// requires a transmute relying on representation guarantees that may
-// not hold in the future.
 
 /// Represents a set (or packed family of sets), of some element type
 /// E, where each E is identified by some unique index type `T`.
 ///
 /// In other words, `T` is the type used to index into the bitslice
 /// this type uses to represent the set of object it holds.
+#[repr(transparent)]
 pub struct IdxSet<T: Idx> {
     _pd: PhantomData<fn(&T)>,
     bits: [Word],
@@ -93,6 +93,8 @@ impl<T: Idx> ToOwned for IdxSet<T> {
     }
 }
 
+const BITS_PER_WORD: usize = mem::size_of::<Word>() * 8;
+
 impl<T: Idx> fmt::Debug for IdxSetBuf<T> {
     fn fmt(&self, w: &mut fmt::Formatter) -> fmt::Result {
         w.debug_list()
@@ -111,8 +113,7 @@ impl<T: Idx> fmt::Debug for IdxSet<T> {
 
 impl<T: Idx> IdxSetBuf<T> {
     fn new(init: Word, universe_size: usize) -> Self {
-        let bits_per_word = mem::size_of::<Word>() * 8;
-        let num_words = (universe_size + (bits_per_word - 1)) / bits_per_word;
+        let num_words = (universe_size + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
         IdxSetBuf {
             _pd: Default::default(),
             bits: vec![init; num_words],
@@ -121,7 +122,9 @@ impl<T: Idx> IdxSetBuf<T> {
 
     /// Creates set holding every element whose index falls in range 0..universe_size.
     pub fn new_filled(universe_size: usize) -> Self {
-        Self::new(!0, universe_size)
+        let mut result = Self::new(!0, universe_size);
+        result.trim_to(universe_size);
+        result
     }
 
     /// Creates set holding no elements.
@@ -132,11 +135,11 @@ impl<T: Idx> IdxSetBuf<T> {
 
 impl<T: Idx> IdxSet<T> {
     unsafe fn from_slice(s: &[Word]) -> &Self {
-        mem::transmute(s) // (see above WARNING)
+        &*(s as *const [Word] as *const Self)
     }
 
     unsafe fn from_slice_mut(s: &mut [Word]) -> &mut Self {
-        mem::transmute(s) // (see above WARNING)
+        &mut *(s as *mut [Word] as *mut Self)
     }
 }
 
@@ -161,6 +164,16 @@ impl<T: Idx> IdxSet<T> {
         }
     }
 
+    /// Duplicates as a hybrid set.
+    pub fn to_hybrid(&self) -> HybridIdxSetBuf<T> {
+        // This universe_size may be slightly larger than the one specified
+        // upon creation, due to rounding up to a whole word. That's ok.
+        let universe_size = self.bits.len() * BITS_PER_WORD;
+
+        // Note: we currently don't bother trying to make a Sparse set.
+        HybridIdxSetBuf::Dense(self.to_owned(), universe_size)
+    }
+
     /// Removes all elements
     pub fn clear(&mut self) {
         for b in &mut self.bits {
@@ -168,6 +181,34 @@ impl<T: Idx> IdxSet<T> {
         }
     }
 
+    /// Sets all elements up to `universe_size`
+    pub fn set_up_to(&mut self, universe_size: usize) {
+        for b in &mut self.bits {
+            *b = !0;
+        }
+        self.trim_to(universe_size);
+    }
+
+    /// Clear all elements above `universe_size`.
+    fn trim_to(&mut self, universe_size: usize) {
+        // `trim_block` is the first block where some bits have
+        // to be cleared.
+        let trim_block = universe_size / BITS_PER_WORD;
+
+        // all the blocks above it have to be completely cleared.
+        if trim_block < self.bits.len() {
+            for b in &mut self.bits[trim_block+1..] {
+                *b = 0;
+            }
+
+            // at that block, the `universe_size % BITS_PER_WORD` lsbs
+            // should remain.
+            let remaining_bits = universe_size % BITS_PER_WORD;
+            let mask = (1<<remaining_bits)-1;
+            self.bits[trim_block] &= mask;
+        }
+    }
+
     /// Removes `elem` from the set `self`; returns true iff this changed `self`.
     pub fn remove(&mut self, elem: &T) -> bool {
         self.bits.clear_bit(elem.index())
@@ -201,18 +242,60 @@ impl<T: Idx> IdxSet<T> {
         &mut self.bits
     }
 
-    pub fn clone_from(&mut self, other: &IdxSet<T>) {
+    /// Efficiently overwrite `self` with `other`. Panics if `self` and `other`
+    /// don't have the same length.
+    pub fn overwrite(&mut self, other: &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)
     }
 
+    /// Like `union()`, but takes a `SparseIdxSetBuf` argument.
+    fn union_sparse(&mut self, other: &SparseIdxSetBuf<T>) -> bool {
+        let mut changed = false;
+        for elem in other.iter() {
+            changed |= self.add(&elem);
+        }
+        changed
+    }
+
+    /// Like `union()`, but takes a `HybridIdxSetBuf` argument.
+    pub fn union_hybrid(&mut self, other: &HybridIdxSetBuf<T>) -> bool {
+        match other {
+            HybridIdxSetBuf::Sparse(sparse, _) => self.union_sparse(sparse),
+            HybridIdxSetBuf::Dense(dense, _) => self.union(dense),
+        }
+    }
+
+    /// 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)
     }
 
+    /// Like `subtract()`, but takes a `SparseIdxSetBuf` argument.
+    fn subtract_sparse(&mut self, other: &SparseIdxSetBuf<T>) -> bool {
+        let mut changed = false;
+        for elem in other.iter() {
+            changed |= self.remove(&elem);
+        }
+        changed
+    }
+
+    /// Like `subtract()`, but takes a `HybridIdxSetBuf` argument.
+    pub fn subtract_hybrid(&mut self, other: &HybridIdxSetBuf<T>) -> bool {
+        match other {
+            HybridIdxSetBuf::Sparse(sparse, _) => self.subtract_sparse(sparse),
+            HybridIdxSetBuf::Dense(dense, _) => self.subtract(dense),
+        }
+    }
+
+    /// 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)
     }
@@ -224,95 +307,252 @@ impl<T: Idx> IdxSet<T> {
             _pd: PhantomData,
         }
     }
+}
 
-    /// Calls `f` on each index value held in this set, up to the
-    /// bound `max_bits` on the size of universe of indexes.
-    pub fn each_bit<F>(&self, max_bits: usize, f: F) where F: FnMut(T) {
-        each_bit(self, max_bits, f)
+pub struct Iter<'a, T: Idx> {
+    cur: Option<(Word, usize)>,
+    iter: iter::Enumerate<slice::Iter<'a, Word>>,
+    _pd: PhantomData<fn(&T)>,
+}
+
+impl<'a, T: Idx> Iterator for Iter<'a, T> {
+    type Item = T;
+
+    fn next(&mut self) -> Option<T> {
+        loop {
+            if let Some((ref mut word, offset)) = self.cur {
+                let bit_pos = word.trailing_zeros() as usize;
+                if bit_pos != BITS_PER_WORD {
+                    let bit = 1 << bit_pos;
+                    *word ^= bit;
+                    return Some(T::new(bit_pos + offset))
+                }
+            }
+
+            let (i, word) = self.iter.next()?;
+            self.cur = Some((*word, BITS_PER_WORD * i));
+        }
+    }
+}
+
+const SPARSE_MAX: usize = 8;
+
+/// A sparse index set with a maximum of SPARSE_MAX elements. Used by
+/// HybridIdxSetBuf; do not use directly.
+///
+/// The elements are stored as an unsorted vector with no duplicates.
+#[derive(Clone, Debug)]
+pub struct SparseIdxSetBuf<T: Idx>(ArrayVec<[T; SPARSE_MAX]>);
+
+impl<T: Idx> SparseIdxSetBuf<T> {
+    fn new() -> Self {
+        SparseIdxSetBuf(ArrayVec::new())
+    }
+
+    fn len(&self) -> usize {
+        self.0.len()
+    }
+
+    fn contains(&self, elem: &T) -> bool {
+        self.0.contains(elem)
+    }
+
+    fn add(&mut self, elem: &T) -> bool {
+        // Ensure there are no duplicates.
+        if self.0.contains(elem) {
+            false
+        } else {
+            self.0.push(*elem);
+            true
+        }
     }
 
-    /// Removes all elements from this set.
-    pub fn reset_to_empty(&mut self) {
-        for word in self.words_mut() { *word = 0; }
+    fn remove(&mut self, elem: &T) -> bool {
+        if let Some(i) = self.0.iter().position(|e| e == elem) {
+            // Swap the found element to the end, then pop it.
+            let len = self.0.len();
+            self.0.swap(i, len - 1);
+            self.0.pop();
+            true
+        } else {
+            false
+        }
     }
 
-    pub fn elems(&self, universe_size: usize) -> Elems<T> {
-        Elems { i: 0, set: self, universe_size: universe_size }
+    fn to_dense(&self, universe_size: usize) -> IdxSetBuf<T> {
+        let mut dense = IdxSetBuf::new_empty(universe_size);
+        for elem in self.0.iter() {
+            dense.add(elem);
+        }
+        dense
+    }
+
+    fn iter(&self) -> SparseIter<T> {
+        SparseIter {
+            iter: self.0.iter(),
+        }
     }
 }
 
-pub struct Elems<'a, T: Idx> { i: usize, set: &'a IdxSet<T>, universe_size: usize }
+pub struct SparseIter<'a, T: Idx> {
+    iter: slice::Iter<'a, T>,
+}
 
-impl<'a, T: Idx> Iterator for Elems<'a, T> {
+impl<'a, T: Idx> Iterator for SparseIter<'a, T> {
     type Item = T;
+
     fn next(&mut self) -> Option<T> {
-        if self.i >= self.universe_size { return None; }
-        let mut i = self.i;
-        loop {
-            if i >= self.universe_size {
-                self.i = i; // (mark iteration as complete.)
-                return None;
-            }
-            if self.set.contains(&T::new(i)) {
-                self.i = i + 1; // (next element to start at.)
-                return Some(T::new(i));
-            }
-            i = i + 1;
-        }
+        self.iter.next().map(|e| *e)
     }
 }
 
-fn each_bit<T: Idx, F>(words: &IdxSet<T>, max_bits: usize, mut f: F) where F: FnMut(T) {
-    let usize_bits: usize = mem::size_of::<usize>() * 8;
-
-    for (word_index, &word) in words.words().iter().enumerate() {
-        if word != 0 {
-            let base_index = word_index * usize_bits;
-            for offset in 0..usize_bits {
-                let bit = 1 << offset;
-                if (word & bit) != 0 {
-                    // NB: we round up the total number of bits
-                    // that we store in any given bit set so that
-                    // it is an even multiple of usize::BITS. This
-                    // means that there may be some stray bits at
-                    // the end that do not correspond to any
-                    // actual value; that's why we first check
-                    // that we are in range of bits_per_block.
-                    let bit_index = base_index + offset as usize;
-                    if bit_index >= max_bits {
-                        return;
-                    } else {
-                        f(Idx::new(bit_index));
+/// Like IdxSetBuf, but with a hybrid representation: sparse when there are few
+/// elements in the set, but dense when there are many. It's especially
+/// efficient for sets that typically have a small number of elements, but a
+/// large `universe_size`, and are cleared frequently.
+#[derive(Clone, Debug)]
+pub enum HybridIdxSetBuf<T: Idx> {
+    Sparse(SparseIdxSetBuf<T>, usize),
+    Dense(IdxSetBuf<T>, usize),
+}
+
+impl<T: Idx> HybridIdxSetBuf<T> {
+    pub fn new_empty(universe_size: usize) -> Self {
+        HybridIdxSetBuf::Sparse(SparseIdxSetBuf::new(), universe_size)
+    }
+
+    fn universe_size(&mut self) -> usize {
+        match *self {
+            HybridIdxSetBuf::Sparse(_, size) => size,
+            HybridIdxSetBuf::Dense(_, size) => size,
+        }
+    }
+
+    pub fn clear(&mut self) {
+        let universe_size = self.universe_size();
+        *self = HybridIdxSetBuf::new_empty(universe_size);
+    }
+
+    /// Returns true iff set `self` contains `elem`.
+    pub fn contains(&self, elem: &T) -> bool {
+        match self {
+            HybridIdxSetBuf::Sparse(sparse, _) => sparse.contains(elem),
+            HybridIdxSetBuf::Dense(dense, _) => dense.contains(elem),
+        }
+    }
+
+    /// Adds `elem` to the set `self`.
+    pub fn add(&mut self, elem: &T) -> bool {
+        match self {
+            HybridIdxSetBuf::Sparse(sparse, _) if sparse.len() < SPARSE_MAX => {
+                // The set is sparse and has space for `elem`.
+                sparse.add(elem)
+            }
+            HybridIdxSetBuf::Sparse(sparse, _) if sparse.contains(elem) => {
+                // The set is sparse and does not have space for `elem`, but
+                // that doesn't matter because `elem` is already present.
+                false
+            }
+            HybridIdxSetBuf::Sparse(_, _) => {
+                // The set is sparse and full. Convert to a dense set.
+                //
+                // FIXME: This code is awful, but I can't work out how else to
+                //        appease the borrow checker.
+                let dummy = HybridIdxSetBuf::Sparse(SparseIdxSetBuf::new(), 0);
+                match mem::replace(self, dummy) {
+                    HybridIdxSetBuf::Sparse(sparse, universe_size) => {
+                        let mut dense = sparse.to_dense(universe_size);
+                        let changed = dense.add(elem);
+                        assert!(changed);
+                        mem::replace(self, HybridIdxSetBuf::Dense(dense, universe_size));
+                        changed
                     }
+                    _ => panic!("impossible"),
                 }
             }
+
+            HybridIdxSetBuf::Dense(dense, _) => dense.add(elem),
+        }
+    }
+
+    /// Removes `elem` from the set `self`.
+    pub fn remove(&mut self, elem: &T) -> bool {
+        // Note: we currently don't bother going from Dense back to Sparse.
+        match self {
+            HybridIdxSetBuf::Sparse(sparse, _) => sparse.remove(elem),
+            HybridIdxSetBuf::Dense(dense, _) => dense.remove(elem),
+        }
+    }
+
+    /// Converts to a dense set, consuming itself in the process.
+    pub fn to_dense(self) -> IdxSetBuf<T> {
+        match self {
+            HybridIdxSetBuf::Sparse(sparse, universe_size) => sparse.to_dense(universe_size),
+            HybridIdxSetBuf::Dense(dense, _) => dense,
+        }
+    }
+
+    /// Iteration order is unspecified.
+    pub fn iter(&self) -> HybridIter<T> {
+        match self {
+            HybridIdxSetBuf::Sparse(sparse, _) => HybridIter::Sparse(sparse.iter()),
+            HybridIdxSetBuf::Dense(dense, _) => HybridIter::Dense(dense.iter()),
         }
     }
 }
 
-pub struct Iter<'a, T: Idx> {
-    cur: Option<(Word, usize)>,
-    iter: iter::Enumerate<slice::Iter<'a, Word>>,
-    _pd: PhantomData<fn(&T)>,
+pub enum HybridIter<'a, T: Idx> {
+    Sparse(SparseIter<'a, T>),
+    Dense(Iter<'a, T>),
 }
 
-impl<'a, T: Idx> Iterator for Iter<'a, T> {
+impl<'a, T: Idx> Iterator for HybridIter<'a, T> {
     type Item = T;
 
     fn next(&mut self) -> Option<T> {
-        let word_bits = mem::size_of::<Word>() * 8;
-        loop {
-            if let Some((ref mut word, offset)) = self.cur {
-                let bit_pos = word.trailing_zeros() as usize;
-                if bit_pos != word_bits {
-                    let bit = 1 << bit_pos;
-                    *word ^= bit;
-                    return Some(T::new(bit_pos + offset))
-                }
-            }
+        match self {
+            HybridIter::Sparse(sparse) => sparse.next(),
+            HybridIter::Dense(dense) => dense.next(),
+        }
+    }
+}
 
-            let (i, word) = self.iter.next()?;
-            self.cur = Some((*word, word_bits * i));
+#[test]
+fn test_trim_to() {
+    use std::cmp;
+
+    for i in 0..256 {
+        let mut idx_buf: IdxSetBuf<usize> = IdxSetBuf::new_filled(128);
+        idx_buf.trim_to(i);
+
+        let elems: Vec<usize> = idx_buf.iter().collect();
+        let expected: Vec<usize> = (0..cmp::min(i, 128)).collect();
+        assert_eq!(elems, expected);
+    }
+}
+
+#[test]
+fn test_set_up_to() {
+    for i in 0..128 {
+        for mut idx_buf in
+            vec![IdxSetBuf::new_empty(128), IdxSetBuf::new_filled(128)]
+            .into_iter()
+        {
+            idx_buf.set_up_to(i);
+
+            let elems: Vec<usize> = idx_buf.iter().collect();
+            let expected: Vec<usize> = (0..i).collect();
+            assert_eq!(elems, expected);
         }
     }
 }
+
+#[test]
+fn test_new_filled() {
+    for i in 0..128 {
+        let idx_buf = IdxSetBuf::new_filled(i);
+        let elems: Vec<usize> = idx_buf.iter().collect();
+        let expected: Vec<usize> = (0..i).collect();
+        assert_eq!(elems, expected);
+    }
+}
diff --git a/src/librustc_data_structures/indexed_vec.rs b/src/librustc_data_structures/indexed_vec.rs
index 753f12f400b..c358f2f852e 100644
--- a/src/librustc_data_structures/indexed_vec.rs
+++ b/src/librustc_data_structures/indexed_vec.rs
@@ -8,13 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::collections::range::RangeArgument;
 use std::fmt::Debug;
 use std::iter::{self, FromIterator};
 use std::slice;
 use std::marker::PhantomData;
-use std::ops::{Index, IndexMut, Range};
+use std::ops::{Index, IndexMut, Range, RangeBounds};
 use std::fmt;
+use std::hash::Hash;
 use std::vec;
 use std::u32;
 
@@ -23,18 +23,28 @@ use rustc_serialize as serialize;
 /// Represents some newtyped `usize` wrapper.
 ///
 /// (purpose: avoid mixing indexes for different bitvector domains.)
-pub trait Idx: Copy + 'static + Eq + Debug {
+pub trait Idx: Copy + 'static + Ord + Debug + Hash {
     fn new(idx: usize) -> Self;
+
     fn index(self) -> usize;
+
+    fn increment_by(&mut self, amount: usize) {
+        let v = self.index() + amount;
+        *self = Self::new(v);
+    }
 }
 
 impl Idx for usize {
+    #[inline]
     fn new(idx: usize) -> Self { idx }
+    #[inline]
     fn index(self) -> usize { self }
 }
 
 impl Idx for u32 {
+    #[inline]
     fn new(idx: usize) -> Self { assert!(idx <= u32::MAX as usize); idx as u32 }
+    #[inline]
     fn index(self) -> usize { self as usize }
 }
 
@@ -73,16 +83,47 @@ macro_rules! newtype_index {
         pub struct $type($($pub)* u32);
 
         impl Idx for $type {
+            #[inline]
             fn new(value: usize) -> Self {
                 assert!(value < ($max) as usize);
                 $type(value as u32)
             }
 
+            #[inline]
             fn index(self) -> usize {
                 self.0 as usize
             }
         }
 
+        impl ::std::iter::Step for $type {
+            fn steps_between(start: &Self, end: &Self) -> Option<usize> {
+                <usize as ::std::iter::Step>::steps_between(
+                    &Idx::index(*start),
+                    &Idx::index(*end),
+                )
+            }
+
+            fn replace_one(&mut self) -> Self {
+                ::std::mem::replace(self, Self::new(1))
+            }
+
+            fn replace_zero(&mut self) -> Self {
+                ::std::mem::replace(self, Self::new(0))
+            }
+
+            fn add_one(&self) -> Self {
+                Self::new(Idx::index(*self) + 1)
+            }
+
+            fn sub_one(&self) -> Self {
+                Self::new(Idx::index(*self) - 1)
+            }
+
+            fn add_usize(&self, u: usize) -> Option<Self> {
+                Idx::index(*self).checked_add(u).map(Self::new)
+            }
+        }
+
         newtype_index!(
             @handle_debug
             @derives      [$($derives,)*]
@@ -204,7 +245,7 @@ macro_rules! newtype_index {
                           $($tokens)*);
     );
 
-    // The case where no derives are added, but encodable is overriden. Don't
+    // The case where no derives are added, but encodable is overridden. Don't
     // derive serialization traits
     (@pub          [$($pub:tt)*]
      @type         [$type:ident]
@@ -324,7 +365,7 @@ macro_rules! newtype_index {
     );
 }
 
-#[derive(Clone, PartialEq, Eq)]
+#[derive(Clone, PartialEq, Eq, Hash)]
 pub struct IndexVec<I: Idx, T> {
     pub raw: Vec<T>,
     _marker: PhantomData<fn(&I)>
@@ -363,6 +404,11 @@ impl<I: Idx, T> IndexVec<I, T> {
     }
 
     #[inline]
+    pub fn from_raw(raw: Vec<T>) -> Self {
+        IndexVec { raw, _marker: PhantomData }
+    }
+
+    #[inline]
     pub fn with_capacity(capacity: usize) -> Self {
         IndexVec { raw: Vec::with_capacity(capacity), _marker: PhantomData }
     }
@@ -442,13 +488,13 @@ impl<I: Idx, T> IndexVec<I, T> {
     }
 
     #[inline]
-    pub fn drain<'a, R: RangeArgument<usize>>(
+    pub fn drain<'a, R: RangeBounds<usize>>(
         &'a mut self, range: R) -> impl Iterator<Item=T> + 'a {
         self.raw.drain(range)
     }
 
     #[inline]
-    pub fn drain_enumerated<'a, R: RangeArgument<usize>>(
+    pub fn drain_enumerated<'a, R: RangeBounds<usize>>(
         &'a mut self, range: R) -> impl Iterator<Item=(I, T)> + 'a {
         self.raw.drain(range).enumerate().map(IntoIdx { _marker: PhantomData })
     }
@@ -464,8 +510,8 @@ impl<I: Idx, T> IndexVec<I, T> {
     }
 
     #[inline]
-    pub fn swap(&mut self, a: usize, b: usize) {
-        self.raw.swap(a, b)
+    pub fn swap(&mut self, a: I, b: I) {
+        self.raw.swap(a.index(), b.index())
     }
 
     #[inline]
@@ -482,13 +528,53 @@ impl<I: Idx, T> IndexVec<I, T> {
     pub fn get_mut(&mut self, index: I) -> Option<&mut T> {
         self.raw.get_mut(index.index())
     }
+
+    /// Return mutable references to two distinct elements, a and b. Panics if a == b.
+    #[inline]
+    pub fn pick2_mut(&mut self, a: I, b: I) -> (&mut T, &mut T) {
+        let (ai, bi) = (a.index(), b.index());
+        assert!(ai != bi);
+
+        if ai < bi {
+            let (c1, c2) = self.raw.split_at_mut(bi);
+            (&mut c1[ai], &mut c2[0])
+        } else {
+            let (c2, c1) = self.pick2_mut(b, a);
+            (c1, c2)
+        }
+    }
+
+    pub fn convert_index_type<Ix: Idx>(self) -> IndexVec<Ix, T> {
+        IndexVec {
+            raw: self.raw,
+            _marker: PhantomData,
+        }
+    }
 }
 
 impl<I: Idx, T: Clone> IndexVec<I, T> {
+    /// Grows the index vector so that it contains an entry for
+    /// `elem`; if that is already true, then has no
+    /// effect. Otherwise, inserts new values as needed by invoking
+    /// `fill_value`.
+    #[inline]
+    pub fn ensure_contains_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
+        let min_new_len = elem.index() + 1;
+        if self.len() < min_new_len {
+            self.raw.resize_with(min_new_len, fill_value);
+        }
+    }
+
     #[inline]
     pub fn resize(&mut self, new_len: usize, value: T) {
         self.raw.resize(new_len, value)
     }
+
+    #[inline]
+    pub fn resize_to_elem(&mut self, elem: I, fill_value: impl FnMut() -> T) {
+        let min_new_len = elem.index() + 1;
+        self.raw.resize_with(min_new_len, fill_value);
+    }
 }
 
 impl<I: Idx, T: Ord> IndexVec<I, T> {
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 24048e606df..5699512326a 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -19,27 +19,22 @@
 #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
       html_favicon_url = "https://www.rust-lang.org/favicon.ico",
       html_root_url = "https://doc.rust-lang.org/nightly/")]
-#![deny(warnings)]
 
-#![feature(shared)]
-#![feature(collections_range)]
-#![feature(nonzero)]
 #![feature(unboxed_closures)]
 #![feature(fn_traits)]
 #![feature(unsize)]
-#![feature(i128_type)]
-#![feature(i128)]
-#![feature(conservative_impl_trait)]
 #![feature(specialization)]
 #![feature(optin_builtin_traits)]
-#![feature(underscore_lifetimes)]
 #![feature(macro_vis_matcher)]
+#![cfg_attr(not(stage0), feature(nll))]
 #![feature(allow_internal_unstable)]
+#![feature(vec_resize_with)]
 
 #![cfg_attr(unix, feature(libc))]
 #![cfg_attr(test, feature(test))]
 
 extern crate core;
+extern crate ena;
 #[macro_use]
 extern crate log;
 extern crate serialize as rustc_serialize; // used by deriving
@@ -49,33 +44,63 @@ extern crate parking_lot;
 #[macro_use]
 extern crate cfg_if;
 extern crate stable_deref_trait;
+extern crate rustc_rayon as rayon;
+extern crate rustc_rayon_core as rayon_core;
+extern crate rustc_hash;
+extern crate serialize;
+
+// See librustc_cratesio_shim/Cargo.toml for a comment explaining this.
+#[allow(unused_extern_crates)]
+extern crate rustc_cratesio_shim;
 
 pub use rustc_serialize::hex::ToHex;
 
-pub mod array_vec;
+pub mod svh;
 pub mod accumulate_vec;
-pub mod small_vec;
+pub mod array_vec;
 pub mod base_n;
 pub mod bitslice;
 pub mod bitvec;
-pub mod blake2b;
+pub mod const_cstr;
+pub mod flock;
+pub mod fx;
 pub mod graph;
 pub mod indexed_set;
 pub mod indexed_vec;
 pub mod obligation_forest;
+pub mod owning_ref;
+pub mod ptr_key;
 pub mod sip128;
+pub mod small_c_str;
+pub mod small_vec;
 pub mod snapshot_map;
-pub mod snapshot_vec;
-pub mod stable_hasher;
+pub use ena::snapshot_vec;
+pub mod sorted_map;
+#[macro_use] pub mod stable_hasher;
+pub mod sync;
+pub mod tiny_list;
+pub mod thin_vec;
 pub mod transitive_relation;
-pub mod unify;
-pub mod fx;
 pub mod tuple_slice;
-pub mod veccell;
-pub mod control_flow_graph;
-pub mod flock;
-pub mod sync;
-pub mod owning_ref;
+pub use ena::unify;
+pub mod work_queue;
+pub mod fingerprint;
+
+pub struct OnDrop<F: Fn()>(pub F);
+
+impl<F: Fn()> OnDrop<F> {
+      /// Forgets the function which prevents it from running.
+      /// Ensure that the function owns no memory, otherwise it will be leaked.
+      pub fn disable(self) {
+            std::mem::forget(self);
+      }
+}
+
+impl<F: Fn()> Drop for OnDrop<F> {
+      fn drop(&mut self) {
+            (self.0)();
+      }
+}
 
 // See comments in src/librustc/lib.rs
 #[doc(hidden)]
diff --git a/src/librustc_data_structures/obligation_forest/mod.rs b/src/librustc_data_structures/obligation_forest/mod.rs
index 02cae52166a..7ef88852685 100644
--- a/src/librustc_data_structures/obligation_forest/mod.rs
+++ b/src/librustc_data_structures/obligation_forest/mod.rs
@@ -41,7 +41,7 @@ pub trait ObligationProcessor {
 
     fn process_obligation(&mut self,
                           obligation: &mut Self::Obligation)
-                          -> Result<Option<Vec<Self::Obligation>>, Self::Error>;
+                          -> ProcessResult<Self::Obligation, Self::Error>;
 
     /// As we do the cycle check, we invoke this callback when we
     /// encounter an actual cycle. `cycle` is an iterator that starts
@@ -57,6 +57,14 @@ pub trait ObligationProcessor {
         where I: Clone + Iterator<Item=&'c Self::Obligation>;
 }
 
+/// The result type used by `process_obligation`.
+#[derive(Debug)]
+pub enum ProcessResult<O, E> {
+    Unchanged,
+    Changed(Vec<O>),
+    Error(E),
+}
+
 pub struct ObligationForest<O: ForestObligation> {
     /// The list of obligations. In between calls to
     /// `process_obligations`, this list only contains nodes in the
@@ -75,9 +83,6 @@ pub struct ObligationForest<O: ForestObligation> {
     done_cache: FxHashSet<O::Predicate>,
     /// An cache of the nodes in `nodes`, indexed by predicate.
     waiting_cache: FxHashMap<O::Predicate, NodeIndex>,
-    /// A list of the obligations added in snapshots, to allow
-    /// for their removal.
-    cache_list: Vec<O::Predicate>,
     scratch: Option<Vec<usize>>,
 }
 
@@ -86,13 +91,14 @@ struct Node<O> {
     obligation: O,
     state: Cell<NodeState>,
 
-    /// Obligations that depend on this obligation for their
-    /// completion. They must all be in a non-pending state.
-    dependents: Vec<NodeIndex>,
     /// The parent of a node - the original obligation of
     /// which it is a subobligation. Except for error reporting,
-    /// this is just another member of `dependents`.
+    /// it is just like any member of `dependents`.
     parent: Option<NodeIndex>,
+
+    /// Obligations that depend on this obligation for their
+    /// completion. They must all be in a non-pending state.
+    dependents: Vec<NodeIndex>,
 }
 
 /// The state of one node in some tree within the forest. This
@@ -139,8 +145,8 @@ pub struct Outcome<O, E> {
 
     /// If true, then we saw no successful obligations, which means
     /// there is no point in further iteration. This is based on the
-    /// assumption that when trait matching returns `Err` or
-    /// `Ok(None)`, those results do not affect environmental
+    /// assumption that when trait matching returns `Error` or
+    /// `Unchanged`, those results do not affect environmental
     /// inference state. (Note that if we invoke `process_obligations`
     /// with no pending obligations, stalled will be true.)
     pub stalled: bool,
@@ -158,7 +164,6 @@ impl<O: ForestObligation> ObligationForest<O> {
             nodes: vec![],
             done_cache: FxHashSet(),
             waiting_cache: FxHashMap(),
-            cache_list: vec![],
             scratch: Some(vec![]),
         }
     }
@@ -189,15 +194,18 @@ impl<O: ForestObligation> ObligationForest<O> {
             Entry::Occupied(o) => {
                 debug!("register_obligation_at({:?}, {:?}) - duplicate of {:?}!",
                        obligation, parent, o.get());
+                let node = &mut self.nodes[o.get().get()];
                 if let Some(parent) = parent {
-                    if self.nodes[o.get().get()].dependents.contains(&parent) {
-                        debug!("register_obligation_at({:?}, {:?}) - duplicate subobligation",
-                               obligation, parent);
-                    } else {
-                        self.nodes[o.get().get()].dependents.push(parent);
+                    // If the node is already in `waiting_cache`, it's already
+                    // been marked with a parent. (It's possible that parent
+                    // has been cleared by `apply_rewrites`, though.) So just
+                    // dump `parent` into `node.dependents`... unless it's
+                    // already in `node.dependents` or `node.parent`.
+                    if !node.dependents.contains(&parent) && Some(parent) != node.parent {
+                        node.dependents.push(parent);
                     }
                 }
-                if let NodeState::Error = self.nodes[o.get().get()].state.get() {
+                if let NodeState::Error = node.state.get() {
                     Err(())
                 } else {
                     Ok(())
@@ -207,7 +215,6 @@ impl<O: ForestObligation> ObligationForest<O> {
                 debug!("register_obligation_at({:?}, {:?}) - ok, new index is {}",
                        obligation, parent, self.nodes.len());
                 v.insert(NodeIndex::new(self.nodes.len()));
-                self.cache_list.push(obligation.as_predicate().clone());
                 self.nodes.push(Node::new(parent, obligation));
                 Ok(())
             }
@@ -234,13 +241,13 @@ impl<O: ForestObligation> ObligationForest<O> {
     }
 
     /// Returns the set of obligations that are in a pending state.
-    pub fn pending_obligations(&self) -> Vec<O>
-        where O: Clone
+    pub fn map_pending_obligations<P, F>(&self, f: F) -> Vec<P>
+        where F: Fn(&O) -> P
     {
         self.nodes
             .iter()
             .filter(|n| n.state.get() == NodeState::Pending)
-            .map(|n| n.obligation.clone())
+            .map(|n| f(&n.obligation))
             .collect()
     }
 
@@ -275,11 +282,11 @@ impl<O: ForestObligation> ObligationForest<O> {
                    result);
 
             match result {
-                Ok(None) => {
-                    // no change in state
+                ProcessResult::Unchanged => {
+                    // No change in state.
                 }
-                Ok(Some(children)) => {
-                    // if we saw a Some(_) result, we are not (yet) stalled
+                ProcessResult::Changed(children) => {
+                    // We are not (yet) stalled.
                     stalled = false;
                     self.nodes[index].state.set(NodeState::Success);
 
@@ -295,7 +302,7 @@ impl<O: ForestObligation> ObligationForest<O> {
                         }
                     }
                 }
-                Err(err) => {
+                ProcessResult::Error(err) => {
                     stalled = false;
                     let backtrace = self.error_at(index);
                     errors.push(Error {
@@ -377,10 +384,7 @@ impl<O: ForestObligation> ObligationForest<O> {
             NodeState::Success => {
                 node.state.set(NodeState::OnDfsStack);
                 stack.push(index);
-                if let Some(parent) = node.parent {
-                    self.find_cycles_from_node(stack, processor, parent.get());
-                }
-                for dependent in &node.dependents {
+                for dependent in node.parent.iter().chain(node.dependents.iter()) {
                     self.find_cycles_from_node(stack, processor, dependent.get());
                 }
                 stack.pop();
@@ -415,13 +419,7 @@ impl<O: ForestObligation> ObligationForest<O> {
             }
         }
 
-        loop {
-            // non-standard `while let` to bypass #6393
-            let i = match error_stack.pop() {
-                Some(i) => i,
-                None => break
-            };
-
+        while let Some(i) = error_stack.pop() {
             let node = &self.nodes[i];
 
             match node.state.get() {
@@ -430,7 +428,7 @@ impl<O: ForestObligation> ObligationForest<O> {
             }
 
             error_stack.extend(
-                node.dependents.iter().cloned().chain(node.parent).map(|x| x.get())
+                node.parent.iter().chain(node.dependents.iter()).map(|x| x.get())
             );
         }
 
@@ -440,11 +438,7 @@ impl<O: ForestObligation> ObligationForest<O> {
 
     #[inline]
     fn mark_neighbors_as_waiting_from(&self, node: &Node<O>) {
-        if let Some(parent) = node.parent {
-            self.mark_as_waiting_from(&self.nodes[parent.get()]);
-        }
-
-        for dependent in &node.dependents {
+        for dependent in node.parent.iter().chain(node.dependents.iter()) {
             self.mark_as_waiting_from(&self.nodes[dependent.get()]);
         }
     }
@@ -502,9 +496,14 @@ impl<O: ForestObligation> ObligationForest<O> {
                     }
                 }
                 NodeState::Done => {
-                    self.waiting_cache.remove(self.nodes[i].obligation.as_predicate());
-                    // FIXME(HashMap): why can't I get my key back?
-                    self.done_cache.insert(self.nodes[i].obligation.as_predicate().clone());
+                    // Avoid cloning the key (predicate) in case it exists in the waiting cache
+                    if let Some((predicate, _)) = self.waiting_cache
+                        .remove_entry(self.nodes[i].obligation.as_predicate())
+                    {
+                        self.done_cache.insert(predicate);
+                    } else {
+                        self.done_cache.insert(self.nodes[i].obligation.as_predicate().clone());
+                    }
                     node_rewrites[i] = nodes_len;
                     dead_nodes += 1;
                 }
@@ -574,7 +573,7 @@ impl<O: ForestObligation> ObligationForest<O> {
         }
 
         let mut kill_list = vec![];
-        for (predicate, index) in self.waiting_cache.iter_mut() {
+        for (predicate, index) in &mut self.waiting_cache {
             let new_index = node_rewrites[index.get()];
             if new_index >= nodes_len {
                 kill_list.push(predicate.clone());
@@ -591,8 +590,8 @@ impl<O> Node<O> {
     fn new(parent: Option<NodeIndex>, obligation: O) -> Node<O> {
         Node {
             obligation,
-            parent,
             state: Cell::new(NodeState::Pending),
+            parent,
             dependents: vec![],
         }
     }
diff --git a/src/librustc_data_structures/obligation_forest/node_index.rs b/src/librustc_data_structures/obligation_forest/node_index.rs
index a72cc6b57ea..d89bd22ec96 100644
--- a/src/librustc_data_structures/obligation_forest/node_index.rs
+++ b/src/librustc_data_structures/obligation_forest/node_index.rs
@@ -8,20 +8,22 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use core::nonzero::NonZero;
+use std::num::NonZeroU32;
 use std::u32;
 
 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 pub struct NodeIndex {
-    index: NonZero<u32>,
+    index: NonZeroU32,
 }
 
 impl NodeIndex {
+    #[inline]
     pub fn new(value: usize) -> NodeIndex {
         assert!(value < (u32::MAX as usize));
-        NodeIndex { index: NonZero::new((value as u32) + 1).unwrap() }
+        NodeIndex { index: NonZeroU32::new((value as u32) + 1).unwrap() }
     }
 
+    #[inline]
     pub fn get(self) -> usize {
         (self.index.get() - 1) as usize
     }
diff --git a/src/librustc_data_structures/obligation_forest/test.rs b/src/librustc_data_structures/obligation_forest/test.rs
index a95b2b84b34..527a1ef0ec4 100644
--- a/src/librustc_data_structures/obligation_forest/test.rs
+++ b/src/librustc_data_structures/obligation_forest/test.rs
@@ -10,7 +10,7 @@
 
 #![cfg(test)]
 
-use super::{ObligationForest, ObligationProcessor, Outcome, Error};
+use super::{Error, ObligationForest, ObligationProcessor, Outcome, ProcessResult};
 
 use std::fmt;
 use std::marker::PhantomData;
@@ -31,7 +31,7 @@ struct ClosureObligationProcessor<OF, BF, O, E> {
 
 #[allow(non_snake_case)]
 fn C<OF, BF, O>(of: OF, bf: BF) -> ClosureObligationProcessor<OF, BF, O, &'static str>
-    where OF: FnMut(&mut O) -> Result<Option<Vec<O>>, &'static str>,
+    where OF: FnMut(&mut O) -> ProcessResult<O, &'static str>,
           BF: FnMut(&[O])
 {
     ClosureObligationProcessor {
@@ -44,7 +44,7 @@ fn C<OF, BF, O>(of: OF, bf: BF) -> ClosureObligationProcessor<OF, BF, O, &'stati
 impl<OF, BF, O, E> ObligationProcessor for ClosureObligationProcessor<OF, BF, O, E>
     where O: super::ForestObligation + fmt::Debug,
           E: fmt::Debug,
-          OF: FnMut(&mut O) -> Result<Option<Vec<O>>, E>,
+          OF: FnMut(&mut O) -> ProcessResult<O, E>,
           BF: FnMut(&[O])
 {
     type Obligation = O;
@@ -52,7 +52,7 @@ impl<OF, BF, O, E> ObligationProcessor for ClosureObligationProcessor<OF, BF, O,
 
     fn process_obligation(&mut self,
                           obligation: &mut Self::Obligation)
-                          -> Result<Option<Vec<Self::Obligation>>, Self::Error>
+                          -> ProcessResult<Self::Obligation, Self::Error>
     {
         (self.process_obligation)(obligation)
     }
@@ -78,9 +78,9 @@ fn push_pop() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["A.1", "A.2", "A.3"])),
-                "B" => Err("B is for broken"),
-                "C" => Ok(Some(vec![])),
+                "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
+                "B" => ProcessResult::Error("B is for broken"),
+                "C" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -101,10 +101,10 @@ fn push_pop() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.1" => Ok(None),
-                "A.2" => Ok(None),
-                "A.3" => Ok(Some(vec!["A.3.i"])),
-                "D" => Ok(Some(vec!["D.1", "D.2"])),
+                "A.1" => ProcessResult::Unchanged,
+                "A.2" => ProcessResult::Unchanged,
+                "A.3" => ProcessResult::Changed(vec!["A.3.i"]),
+                "D" => ProcessResult::Changed(vec!["D.1", "D.2"]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -119,11 +119,11 @@ fn push_pop() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.1" => Ok(Some(vec![])),
-                "A.2" => Err("A is for apple"),
-                "A.3.i" => Ok(Some(vec![])),
-                "D.1" => Ok(Some(vec!["D.1.i"])),
-                "D.2" => Ok(Some(vec!["D.2.i"])),
+                "A.1" => ProcessResult::Changed(vec![]),
+                "A.2" => ProcessResult::Error("A is for apple"),
+                "A.3.i" => ProcessResult::Changed(vec![]),
+                "D.1" => ProcessResult::Changed(vec!["D.1.i"]),
+                "D.2" => ProcessResult::Changed(vec!["D.2.i"]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -138,8 +138,8 @@ fn push_pop() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D.1.i" => Err("D is for dumb"),
-                "D.2.i" => Ok(Some(vec![])),
+                "D.1.i" => ProcessResult::Error("D is for dumb"),
+                "D.2.i" => ProcessResult::Changed(vec![]),
                 _ => panic!("unexpected obligation {:?}", obligation),
             }
         }, |_| {}));
@@ -167,7 +167,7 @@ fn success_in_grandchildren() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["A.1", "A.2", "A.3"])),
+                "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -177,9 +177,9 @@ fn success_in_grandchildren() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.1" => Ok(Some(vec![])),
-                "A.2" => Ok(Some(vec!["A.2.i", "A.2.ii"])),
-                "A.3" => Ok(Some(vec![])),
+                "A.1" => ProcessResult::Changed(vec![]),
+                "A.2" => ProcessResult::Changed(vec!["A.2.i", "A.2.ii"]),
+                "A.3" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -189,8 +189,8 @@ fn success_in_grandchildren() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.2.i" => Ok(Some(vec!["A.2.i.a"])),
-                "A.2.ii" => Ok(Some(vec![])),
+                "A.2.i" => ProcessResult::Changed(vec!["A.2.i.a"]),
+                "A.2.ii" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -200,7 +200,7 @@ fn success_in_grandchildren() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.2.i.a" => Ok(Some(vec![])),
+                "A.2.i.a" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_| {}));
@@ -223,7 +223,7 @@ fn to_errors_no_throw() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["A.1", "A.2", "A.3"])),
+                "A" => ProcessResult::Changed(vec!["A.1", "A.2", "A.3"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -244,7 +244,7 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["A.1", "A.2"])),
+                "A" => ProcessResult::Changed(vec!["A.1", "A.2"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -254,8 +254,8 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A.1" => Ok(Some(vec!["D"])),
-                "A.2" => Ok(Some(vec!["D"])),
+                "A.1" => ProcessResult::Changed(vec!["D"]),
+                "A.2" => ProcessResult::Changed(vec!["D"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -266,7 +266,7 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D" => { d_count += 1; Ok(Some(vec![])) },
+                "D" => { d_count += 1; ProcessResult::Changed(vec![]) },
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -281,7 +281,7 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A'" => Ok(Some(vec!["A'.1", "A'.2"])),
+                "A'" => ProcessResult::Changed(vec!["A'.1", "A'.2"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -291,8 +291,8 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A'.1" => Ok(Some(vec!["D'", "A'"])),
-                "A'.2" => Ok(Some(vec!["D'"])),
+                "A'.1" => ProcessResult::Changed(vec!["D'", "A'"]),
+                "A'.2" => ProcessResult::Changed(vec!["D'"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -303,7 +303,7 @@ fn diamond() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D'" => { d_count += 1; Err("operation failed") },
+                "D'" => { d_count += 1; ProcessResult::Error("operation failed") },
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -329,7 +329,7 @@ fn done_dependency() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A: Sized" | "B: Sized" | "C: Sized" => Ok(Some(vec![])),
+                "A: Sized" | "B: Sized" | "C: Sized" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -340,11 +340,11 @@ fn done_dependency() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "(A,B,C): Sized" => Ok(Some(vec![
+                "(A,B,C): Sized" => ProcessResult::Changed(vec![
                     "A: Sized",
                     "B: Sized",
                     "C: Sized"
-                        ])),
+                        ]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -367,10 +367,10 @@ fn orphan() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Ok(Some(vec!["D", "E"])),
-                "B" => Ok(None),
-                "C1" => Ok(Some(vec![])),
-                "C2" => Ok(Some(vec![])),
+                "A" => ProcessResult::Changed(vec!["D", "E"]),
+                "B" => ProcessResult::Unchanged,
+                "C1" => ProcessResult::Changed(vec![]),
+                "C2" => ProcessResult::Changed(vec![]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -380,8 +380,8 @@ fn orphan() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D" | "E" => Ok(None),
-                "B" => Ok(Some(vec!["D"])),
+                "D" | "E" => ProcessResult::Unchanged,
+                "B" => ProcessResult::Changed(vec!["D"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -391,8 +391,8 @@ fn orphan() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D" => Ok(None),
-                "E" => Err("E is for error"),
+                "D" => ProcessResult::Unchanged,
+                "E" => ProcessResult::Error("E is for error"),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -405,7 +405,7 @@ fn orphan() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "D" => Err("D is dead"),
+                "D" => ProcessResult::Error("D is dead"),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -429,8 +429,8 @@ fn simultaneous_register_and_error() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Err("An error"),
-                "B" => Ok(Some(vec!["A"])),
+                "A" => ProcessResult::Error("An error"),
+                "B" => ProcessResult::Changed(vec!["A"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
@@ -447,8 +447,8 @@ fn simultaneous_register_and_error() {
     let Outcome { completed: ok, errors: err, .. } =
         forest.process_obligations(&mut C(|obligation| {
             match *obligation {
-                "A" => Err("An error"),
-                "B" => Ok(Some(vec!["A"])),
+                "A" => ProcessResult::Error("An error"),
+                "B" => ProcessResult::Changed(vec!["A"]),
                 _ => unreachable!(),
             }
         }, |_|{}));
diff --git a/src/librustc_data_structures/owning_ref/mod.rs b/src/librustc_data_structures/owning_ref/mod.rs
index 23e0733748b..02640a71010 100644
--- a/src/librustc_data_structures/owning_ref/mod.rs
+++ b/src/librustc_data_structures/owning_ref/mod.rs
@@ -243,6 +243,7 @@ fn main() {
 ```
 */
 
+use std::mem;
 pub use stable_deref_trait::{StableDeref as StableAddress, CloneStableDeref as CloneStableAddress};
 
 /// An owning reference.
@@ -279,7 +280,7 @@ pub struct OwningRefMut<O, T: ?Sized> {
 pub trait Erased {}
 impl<T> Erased for T {}
 
-/// Helper trait for erasing the concrete type of what an owner derferences to,
+/// Helper trait for erasing the concrete type of what an owner dereferences to,
 /// for example `Box<T> -> Box<Erased>`. This would be unneeded with
 /// higher kinded types support in the language.
 pub unsafe trait IntoErased<'a> {
@@ -289,10 +290,20 @@ pub unsafe trait IntoErased<'a> {
     fn into_erased(self) -> Self::Erased;
 }
 
-/// Helper trait for erasing the concrete type of what an owner derferences to,
+/// Helper trait for erasing the concrete type of what an owner dereferences to,
+/// for example `Box<T> -> Box<Erased + Send>`. This would be unneeded with
+/// higher kinded types support in the language.
+pub unsafe trait IntoErasedSend<'a> {
+    /// Owner with the dereference type substituted to `Erased + Send`.
+    type Erased: Send;
+    /// Perform the type erasure.
+    fn into_erased_send(self) -> Self::Erased;
+}
+
+/// Helper trait for erasing the concrete type of what an owner dereferences to,
 /// for example `Box<T> -> Box<Erased + Send + Sync>`. This would be unneeded with
 /// higher kinded types support in the language.
-pub unsafe trait IntoErasedSendSync<'a>: Send + Sync {
+pub unsafe trait IntoErasedSendSync<'a> {
     /// Owner with the dereference type substituted to `Erased + Send + Sync`.
     type Erased: Send + Sync;
     /// Perform the type erasure.
@@ -472,6 +483,18 @@ impl<O, T: ?Sized> OwningRef<O, T> {
         }
     }
 
+    /// Erases the concrete base type of the owner with a trait object which implements `Send`.
+    ///
+    /// This allows mixing of owned references with different owner base types.
+    pub fn erase_send_owner<'a>(self) -> OwningRef<O::Erased, T>
+        where O: IntoErasedSend<'a>,
+    {
+        OwningRef {
+            reference: self.reference,
+            owner: self.owner.into_erased_send(),
+        }
+    }
+
     /// Erases the concrete base type of the owner with a trait object which implements `Send` and `Sync`.
     ///
     /// This allows mixing of owned references with different owner base types.
@@ -979,7 +1002,7 @@ impl<O, T: ?Sized> Debug for OwningRef<O, T>
     where O: Debug,
           T: Debug,
 {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f,
                "OwningRef {{ owner: {:?}, reference: {:?} }}",
                self.owner(),
@@ -991,7 +1014,7 @@ impl<O, T: ?Sized> Debug for OwningRefMut<O, T>
     where O: Debug,
           T: Debug,
 {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f,
                "OwningRefMut {{ owner: {:?}, reference: {:?} }}",
                self.owner(),
@@ -1023,8 +1046,8 @@ unsafe impl<O, T: ?Sized> Send for OwningRefMut<O, T>
 unsafe impl<O, T: ?Sized> Sync for OwningRefMut<O, T>
     where O: Sync, for<'a> (&'a mut T): Sync {}
 
-impl Debug for Erased {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+impl Debug for dyn Erased {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "<Erased>",)
     }
 }
@@ -1143,47 +1166,59 @@ pub type MutexGuardRefMut<'a, T, U = T> = OwningRefMut<MutexGuard<'a, T>, U>;
 pub type RwLockWriteGuardRefMut<'a, T, U = T> = OwningRef<RwLockWriteGuard<'a, T>, U>;
 
 unsafe impl<'a, T: 'a> IntoErased<'a> for Box<T> {
-    type Erased = Box<Erased + 'a>;
+    type Erased = Box<dyn Erased + 'a>;
     fn into_erased(self) -> Self::Erased {
         self
     }
 }
 unsafe impl<'a, T: 'a> IntoErased<'a> for Rc<T> {
-    type Erased = Rc<Erased + 'a>;
+    type Erased = Rc<dyn Erased + 'a>;
     fn into_erased(self) -> Self::Erased {
         self
     }
 }
 unsafe impl<'a, T: 'a> IntoErased<'a> for Arc<T> {
-    type Erased = Arc<Erased + 'a>;
+    type Erased = Arc<dyn Erased + 'a>;
     fn into_erased(self) -> Self::Erased {
         self
     }
 }
 
-unsafe impl<'a, T: Send + Sync + 'a> IntoErasedSendSync<'a> for Box<T> {
-    type Erased = Box<Erased + Send + Sync + 'a>;
-    fn into_erased_send_sync(self) -> Self::Erased {
+unsafe impl<'a, T: Send + 'a> IntoErasedSend<'a> for Box<T> {
+    type Erased = Box<dyn Erased + Send + 'a>;
+    fn into_erased_send(self) -> Self::Erased {
         self
     }
 }
 
+unsafe impl<'a, T: Send + 'a> IntoErasedSendSync<'a> for Box<T> {
+    type Erased = Box<dyn Erased + Sync + Send + 'a>;
+    fn into_erased_send_sync(self) -> Self::Erased {
+        let result: Box<dyn Erased + Send + 'a> = self;
+        // This is safe since Erased can always implement Sync
+        // Only the destructor is available and it takes &mut self
+        unsafe {
+            mem::transmute(result)
+        }
+    }
+}
+
 unsafe impl<'a, T: Send + Sync + 'a> IntoErasedSendSync<'a> for Arc<T> {
-    type Erased = Arc<Erased + Send + Sync + 'a>;
+    type Erased = Arc<dyn Erased + Send + Sync + 'a>;
     fn into_erased_send_sync(self) -> Self::Erased {
         self
     }
 }
 
 /// Typedef of a owning reference that uses an erased `Box` as the owner.
-pub type ErasedBoxRef<U> = OwningRef<Box<Erased>, U>;
+pub type ErasedBoxRef<U> = OwningRef<Box<dyn Erased>, U>;
 /// Typedef of a owning reference that uses an erased `Rc` as the owner.
-pub type ErasedRcRef<U> = OwningRef<Rc<Erased>, U>;
+pub type ErasedRcRef<U> = OwningRef<Rc<dyn Erased>, U>;
 /// Typedef of a owning reference that uses an erased `Arc` as the owner.
-pub type ErasedArcRef<U> = OwningRef<Arc<Erased>, U>;
+pub type ErasedArcRef<U> = OwningRef<Arc<dyn Erased>, U>;
 
 /// Typedef of a mutable owning reference that uses an erased `Box` as the owner.
-pub type ErasedBoxRefMut<U> = OwningRefMut<Box<Erased>, U>;
+pub type ErasedBoxRefMut<U> = OwningRefMut<Box<dyn Erased>, U>;
 
 #[cfg(test)]
 mod tests {
@@ -1408,8 +1443,8 @@ mod tests {
             let c: OwningRef<Rc<Vec<u8>>, [u8]> = unsafe {a.map_owner(Rc::new)};
             let d: OwningRef<Rc<Box<[u8]>>, [u8]> = unsafe {b.map_owner(Rc::new)};
 
-            let e: OwningRef<Rc<Erased>, [u8]> = c.erase_owner();
-            let f: OwningRef<Rc<Erased>, [u8]> = d.erase_owner();
+            let e: OwningRef<Rc<dyn Erased>, [u8]> = c.erase_owner();
+            let f: OwningRef<Rc<dyn Erased>, [u8]> = d.erase_owner();
 
             let _g = e.clone();
             let _h = f.clone();
@@ -1425,8 +1460,8 @@ mod tests {
             let c: OwningRef<Box<Vec<u8>>, [u8]> = a.map_owner_box();
             let d: OwningRef<Box<Box<[u8]>>, [u8]> = b.map_owner_box();
 
-            let _e: OwningRef<Box<Erased>, [u8]> = c.erase_owner();
-            let _f: OwningRef<Box<Erased>, [u8]> = d.erase_owner();
+            let _e: OwningRef<Box<dyn Erased>, [u8]> = c.erase_owner();
+            let _f: OwningRef<Box<dyn Erased>, [u8]> = d.erase_owner();
         }
 
         #[test]
@@ -1434,7 +1469,7 @@ mod tests {
             use std::any::Any;
 
             let x = Box::new(123_i32);
-            let y: Box<Any> = x;
+            let y: Box<dyn Any> = x;
 
             OwningRef::new(y).try_map(|x| x.downcast_ref::<i32>().ok_or(())).is_ok();
         }
@@ -1444,7 +1479,7 @@ mod tests {
             use std::any::Any;
 
             let x = Box::new(123_i32);
-            let y: Box<Any> = x;
+            let y: Box<dyn Any> = x;
 
             OwningRef::new(y).try_map(|x| x.downcast_ref::<i32>().ok_or(())).is_err();
         }
@@ -1808,8 +1843,8 @@ mod tests {
             let c: OwningRefMut<Box<Vec<u8>>, [u8]> = unsafe {a.map_owner(Box::new)};
             let d: OwningRefMut<Box<Box<[u8]>>, [u8]> = unsafe {b.map_owner(Box::new)};
 
-            let _e: OwningRefMut<Box<Erased>, [u8]> = c.erase_owner();
-            let _f: OwningRefMut<Box<Erased>, [u8]> = d.erase_owner();
+            let _e: OwningRefMut<Box<dyn Erased>, [u8]> = c.erase_owner();
+            let _f: OwningRefMut<Box<dyn Erased>, [u8]> = d.erase_owner();
         }
 
         #[test]
@@ -1822,8 +1857,8 @@ mod tests {
             let c: OwningRefMut<Box<Vec<u8>>, [u8]> = a.map_owner_box();
             let d: OwningRefMut<Box<Box<[u8]>>, [u8]> = b.map_owner_box();
 
-            let _e: OwningRefMut<Box<Erased>, [u8]> = c.erase_owner();
-            let _f: OwningRefMut<Box<Erased>, [u8]> = d.erase_owner();
+            let _e: OwningRefMut<Box<dyn Erased>, [u8]> = c.erase_owner();
+            let _f: OwningRefMut<Box<dyn Erased>, [u8]> = d.erase_owner();
         }
 
         #[test]
@@ -1831,7 +1866,7 @@ mod tests {
             use std::any::Any;
 
             let x = Box::new(123_i32);
-            let y: Box<Any> = x;
+            let y: Box<dyn Any> = x;
 
             OwningRefMut::new(y).try_map_mut(|x| x.downcast_mut::<i32>().ok_or(())).is_ok();
         }
@@ -1841,7 +1876,7 @@ mod tests {
             use std::any::Any;
 
             let x = Box::new(123_i32);
-            let y: Box<Any> = x;
+            let y: Box<dyn Any> = x;
 
             OwningRefMut::new(y).try_map_mut(|x| x.downcast_mut::<i32>().ok_or(())).is_err();
         }
@@ -1851,7 +1886,7 @@ mod tests {
             use std::any::Any;
 
             let x = Box::new(123_i32);
-            let y: Box<Any> = x;
+            let y: Box<dyn Any> = x;
 
             OwningRefMut::new(y).try_map(|x| x.downcast_ref::<i32>().ok_or(())).is_ok();
         }
@@ -1861,7 +1896,7 @@ mod tests {
             use std::any::Any;
 
             let x = Box::new(123_i32);
-            let y: Box<Any> = x;
+            let y: Box<dyn Any> = x;
 
             OwningRefMut::new(y).try_map(|x| x.downcast_ref::<i32>().ok_or(())).is_err();
         }
diff --git a/src/librustc_data_structures/ptr_key.rs b/src/librustc_data_structures/ptr_key.rs
new file mode 100644
index 00000000000..6835dab38df
--- /dev/null
+++ b/src/librustc_data_structures/ptr_key.rs
@@ -0,0 +1,45 @@
+// 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 std::{hash, ptr};
+use std::ops::Deref;
+
+/// A wrapper around reference that compares and hashes like a pointer.
+/// Can be used as a key in sets/maps indexed by pointers to avoid `unsafe`.
+#[derive(Debug)]
+pub struct PtrKey<'a, T: 'a>(pub &'a T);
+
+impl<'a, T> Clone for PtrKey<'a, T> {
+    fn clone(&self) -> Self { *self }
+}
+
+impl<'a, T> Copy for PtrKey<'a, T> {}
+
+impl<'a, T> PartialEq for PtrKey<'a, T> {
+    fn eq(&self, rhs: &Self) -> bool {
+        ptr::eq(self.0, rhs.0)
+    }
+}
+
+impl<'a, T> Eq for PtrKey<'a, T> {}
+
+impl<'a, T> hash::Hash for PtrKey<'a, T> {
+    fn hash<H: hash::Hasher>(&self, hasher: &mut H) {
+        (self.0 as *const T).hash(hasher)
+    }
+}
+
+impl<'a, T> Deref for PtrKey<'a, T> {
+    type Target = T;
+
+    fn deref(&self) -> &Self::Target {
+        self.0
+    }
+}
diff --git a/src/librustc_data_structures/small_c_str.rs b/src/librustc_data_structures/small_c_str.rs
new file mode 100644
index 00000000000..b0ad83e4979
--- /dev/null
+++ b/src/librustc_data_structures/small_c_str.rs
@@ -0,0 +1,131 @@
+// 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 std::ffi;
+use std::ops::Deref;
+
+const SIZE: usize = 38;
+
+/// Like SmallVec but for C strings.
+#[derive(Clone)]
+pub enum SmallCStr {
+    OnStack {
+        data: [u8; SIZE],
+        len_with_nul: u8,
+    },
+    OnHeap {
+        data: ffi::CString,
+    }
+}
+
+impl SmallCStr {
+    #[inline]
+    pub fn new(s: &str) -> SmallCStr {
+        if s.len() < SIZE {
+            let mut data = [0; SIZE];
+            data[.. s.len()].copy_from_slice(s.as_bytes());
+            let len_with_nul = s.len() + 1;
+
+            // Make sure once that this is a valid CStr
+            if let Err(e) = ffi::CStr::from_bytes_with_nul(&data[.. len_with_nul]) {
+                panic!("The string \"{}\" cannot be converted into a CStr: {}", s, e);
+            }
+
+            SmallCStr::OnStack {
+                data,
+                len_with_nul: len_with_nul as u8,
+            }
+        } else {
+            SmallCStr::OnHeap {
+                data: ffi::CString::new(s).unwrap()
+            }
+        }
+    }
+
+    #[inline]
+    pub fn as_c_str(&self) -> &ffi::CStr {
+        match *self {
+            SmallCStr::OnStack { ref data, len_with_nul } => {
+                unsafe {
+                    let slice = &data[.. len_with_nul as usize];
+                    ffi::CStr::from_bytes_with_nul_unchecked(slice)
+                }
+            }
+            SmallCStr::OnHeap { ref data } => {
+                data.as_c_str()
+            }
+        }
+    }
+
+    #[inline]
+    pub fn len_with_nul(&self) -> usize {
+        match *self {
+            SmallCStr::OnStack { len_with_nul, .. } => {
+                len_with_nul as usize
+            }
+            SmallCStr::OnHeap { ref data } => {
+                data.as_bytes_with_nul().len()
+            }
+        }
+    }
+}
+
+impl Deref for SmallCStr {
+    type Target = ffi::CStr;
+
+    fn deref(&self) -> &ffi::CStr {
+        self.as_c_str()
+    }
+}
+
+
+#[test]
+fn short() {
+    const TEXT: &str = "abcd";
+    let reference = ffi::CString::new(TEXT.to_string()).unwrap();
+
+    let scs = SmallCStr::new(TEXT);
+
+    assert_eq!(scs.len_with_nul(), TEXT.len() + 1);
+    assert_eq!(scs.as_c_str(), reference.as_c_str());
+    assert!(if let SmallCStr::OnStack { .. } = scs { true } else { false });
+}
+
+#[test]
+fn empty() {
+    const TEXT: &str = "";
+    let reference = ffi::CString::new(TEXT.to_string()).unwrap();
+
+    let scs = SmallCStr::new(TEXT);
+
+    assert_eq!(scs.len_with_nul(), TEXT.len() + 1);
+    assert_eq!(scs.as_c_str(), reference.as_c_str());
+    assert!(if let SmallCStr::OnStack { .. } = scs { true } else { false });
+}
+
+#[test]
+fn long() {
+    const TEXT: &str = "01234567890123456789012345678901234567890123456789\
+                        01234567890123456789012345678901234567890123456789\
+                        01234567890123456789012345678901234567890123456789";
+    let reference = ffi::CString::new(TEXT.to_string()).unwrap();
+
+    let scs = SmallCStr::new(TEXT);
+
+    assert_eq!(scs.len_with_nul(), TEXT.len() + 1);
+    assert_eq!(scs.as_c_str(), reference.as_c_str());
+    assert!(if let SmallCStr::OnHeap { .. } = scs { true } else { false });
+}
+
+#[test]
+#[should_panic]
+fn internal_nul() {
+    let _ = SmallCStr::new("abcd\0def");
+}
diff --git a/src/librustc_data_structures/small_vec.rs b/src/librustc_data_structures/small_vec.rs
index 74738e61b44..6f101b20d88 100644
--- a/src/librustc_data_structures/small_vec.rs
+++ b/src/librustc_data_structures/small_vec.rs
@@ -29,6 +29,8 @@ use array_vec::Array;
 
 pub struct SmallVec<A: Array>(AccumulateVec<A>);
 
+pub type OneVector<T> = SmallVec<[T; 1]>;
+
 impl<A> Clone for SmallVec<A>
     where A: Array,
           A::Element: Clone {
@@ -50,6 +52,10 @@ impl<A: Array> SmallVec<A> {
         SmallVec(AccumulateVec::new())
     }
 
+    pub fn is_array(&self) -> bool {
+        self.0.is_array()
+    }
+
     pub fn with_capacity(cap: usize) -> Self {
         let mut vec = SmallVec::new();
         vec.reserve(cap);
@@ -167,8 +173,9 @@ impl<A: Array> Extend<A::Element> for SmallVec<A> {
     fn extend<I: IntoIterator<Item=A::Element>>(&mut self, iter: I) {
         let iter = iter.into_iter();
         self.reserve(iter.size_hint().0);
-        for el in iter {
-            self.push(el);
+        match self.0 {
+            AccumulateVec::Heap(ref mut vec) => vec.extend(iter),
+            _ => iter.for_each(|el| self.push(el))
         }
     }
 }
@@ -193,7 +200,7 @@ impl<A> Encodable for SmallVec<A>
     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
         s.emit_seq(self.len(), |s| {
             for (i, e) in self.iter().enumerate() {
-                try!(s.emit_seq_elt(i, |s| e.encode(s)));
+                s.emit_seq_elt(i, |s| e.encode(s))?;
             }
             Ok(())
         })
@@ -206,10 +213,190 @@ impl<A> Decodable for SmallVec<A>
     fn decode<D: Decoder>(d: &mut D) -> Result<SmallVec<A>, D::Error> {
         d.read_seq(|d, len| {
             let mut vec = SmallVec::with_capacity(len);
+            // FIXME(#48994) - could just be collected into a Result<SmallVec, D::Error>
             for i in 0..len {
-                vec.push(try!(d.read_seq_elt(i, |d| Decodable::decode(d))));
+                vec.push(d.read_seq_elt(i, |d| Decodable::decode(d))?);
             }
             Ok(vec)
         })
     }
 }
+
+#[cfg(test)]
+mod tests {
+    extern crate test;
+    use self::test::Bencher;
+
+    use super::*;
+
+    #[test]
+    fn test_len() {
+        let v: OneVector<isize> = OneVector::new();
+        assert_eq!(0, v.len());
+
+        assert_eq!(1, OneVector::one(1).len());
+        assert_eq!(5, OneVector::many(vec![1, 2, 3, 4, 5]).len());
+    }
+
+    #[test]
+    fn test_push_get() {
+        let mut v = OneVector::new();
+        v.push(1);
+        assert_eq!(1, v.len());
+        assert_eq!(1, v[0]);
+        v.push(2);
+        assert_eq!(2, v.len());
+        assert_eq!(2, v[1]);
+        v.push(3);
+        assert_eq!(3, v.len());
+        assert_eq!(3, v[2]);
+    }
+
+    #[test]
+    fn test_from_iter() {
+        let v: OneVector<isize> = (vec![1, 2, 3]).into_iter().collect();
+        assert_eq!(3, v.len());
+        assert_eq!(1, v[0]);
+        assert_eq!(2, v[1]);
+        assert_eq!(3, v[2]);
+    }
+
+    #[test]
+    fn test_move_iter() {
+        let v = OneVector::new();
+        let v: Vec<isize> = v.into_iter().collect();
+        assert_eq!(v, Vec::new());
+
+        let v = OneVector::one(1);
+        assert_eq!(v.into_iter().collect::<Vec<_>>(), [1]);
+
+        let v = OneVector::many(vec![1, 2, 3]);
+        assert_eq!(v.into_iter().collect::<Vec<_>>(), [1, 2, 3]);
+    }
+
+    #[test]
+    #[should_panic]
+    fn test_expect_one_zero() {
+        let _: isize = OneVector::new().expect_one("");
+    }
+
+    #[test]
+    #[should_panic]
+    fn test_expect_one_many() {
+        OneVector::many(vec![1, 2]).expect_one("");
+    }
+
+    #[test]
+    fn test_expect_one_one() {
+        assert_eq!(1, OneVector::one(1).expect_one(""));
+        assert_eq!(1, OneVector::many(vec![1]).expect_one(""));
+    }
+
+    #[bench]
+    fn fill_small_vec_1_10_with_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 1]> = SmallVec::with_capacity(10);
+
+            sv.extend(0..10);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_1_10_wo_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 1]> = SmallVec::new();
+
+            sv.extend(0..10);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_8_10_with_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 8]> = SmallVec::with_capacity(10);
+
+            sv.extend(0..10);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_8_10_wo_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 8]> = SmallVec::new();
+
+            sv.extend(0..10);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_32_10_with_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 32]> = SmallVec::with_capacity(10);
+
+            sv.extend(0..10);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_32_10_wo_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 32]> = SmallVec::new();
+
+            sv.extend(0..10);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_1_50_with_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 1]> = SmallVec::with_capacity(50);
+
+            sv.extend(0..50);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_1_50_wo_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 1]> = SmallVec::new();
+
+            sv.extend(0..50);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_8_50_with_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 8]> = SmallVec::with_capacity(50);
+
+            sv.extend(0..50);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_8_50_wo_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 8]> = SmallVec::new();
+
+            sv.extend(0..50);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_32_50_with_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 32]> = SmallVec::with_capacity(50);
+
+            sv.extend(0..50);
+        })
+    }
+
+    #[bench]
+    fn fill_small_vec_32_50_wo_cap(b: &mut Bencher) {
+        b.iter(|| {
+            let mut sv: SmallVec<[usize; 32]> = SmallVec::new();
+
+            sv.extend(0..50);
+        })
+    }
+}
diff --git a/src/librustc_data_structures/snapshot_map/mod.rs b/src/librustc_data_structures/snapshot_map/mod.rs
index cd7143ad3ce..5030bf98dff 100644
--- a/src/librustc_data_structures/snapshot_map/mod.rs
+++ b/src/librustc_data_structures/snapshot_map/mod.rs
@@ -45,6 +45,11 @@ impl<K, V> SnapshotMap<K, V>
         }
     }
 
+    pub fn clear(&mut self) {
+        self.map.clear();
+        self.undo_log.clear();
+    }
+
     pub fn insert(&mut self, key: K, value: V) -> bool {
         match self.map.insert(key.clone(), value) {
             None => {
@@ -62,6 +67,12 @@ impl<K, V> SnapshotMap<K, V>
         }
     }
 
+    pub fn insert_noop(&mut self) {
+        if !self.undo_log.is_empty() {
+            self.undo_log.push(UndoLog::Noop);
+        }
+    }
+
     pub fn remove(&mut self, key: K) -> bool {
         match self.map.remove(&key) {
             Some(old_value) => {
@@ -81,7 +92,7 @@ impl<K, V> SnapshotMap<K, V>
     pub fn snapshot(&mut self) -> Snapshot {
         self.undo_log.push(UndoLog::OpenSnapshot);
         let len = self.undo_log.len() - 1;
-        Snapshot { len: len }
+        Snapshot { len }
     }
 
     fn assert_open_snapshot(&self, snapshot: &Snapshot) {
@@ -92,8 +103,8 @@ impl<K, V> SnapshotMap<K, V>
         });
     }
 
-    pub fn commit(&mut self, snapshot: Snapshot) {
-        self.assert_open_snapshot(&snapshot);
+    pub fn commit(&mut self, snapshot: &Snapshot) {
+        self.assert_open_snapshot(snapshot);
         if snapshot.len == 0 {
             // The root snapshot.
             self.undo_log.truncate(0);
@@ -124,8 +135,8 @@ impl<K, V> SnapshotMap<K, V>
         }
     }
 
-    pub fn rollback_to(&mut self, snapshot: Snapshot) {
-        self.assert_open_snapshot(&snapshot);
+    pub fn rollback_to(&mut self, snapshot: &Snapshot) {
+        self.assert_open_snapshot(snapshot);
         while self.undo_log.len() > snapshot.len + 1 {
             let entry = self.undo_log.pop().unwrap();
             self.reverse(entry);
diff --git a/src/librustc_data_structures/snapshot_map/test.rs b/src/librustc_data_structures/snapshot_map/test.rs
index 4114082839b..b163e0fe420 100644
--- a/src/librustc_data_structures/snapshot_map/test.rs
+++ b/src/librustc_data_structures/snapshot_map/test.rs
@@ -20,7 +20,7 @@ fn basic() {
     map.insert(44, "fourty-four");
     assert_eq!(map[&44], "fourty-four");
     assert_eq!(map.get(&33), None);
-    map.rollback_to(snapshot);
+    map.rollback_to(&snapshot);
     assert_eq!(map[&22], "twenty-two");
     assert_eq!(map.get(&33), None);
     assert_eq!(map.get(&44), None);
@@ -33,7 +33,7 @@ fn out_of_order() {
     map.insert(22, "twenty-two");
     let snapshot1 = map.snapshot();
     let _snapshot2 = map.snapshot();
-    map.rollback_to(snapshot1);
+    map.rollback_to(&snapshot1);
 }
 
 #[test]
@@ -43,8 +43,8 @@ fn nested_commit_then_rollback() {
     let snapshot1 = map.snapshot();
     let snapshot2 = map.snapshot();
     map.insert(22, "thirty-three");
-    map.commit(snapshot2);
+    map.commit(&snapshot2);
     assert_eq!(map[&22], "thirty-three");
-    map.rollback_to(snapshot1);
+    map.rollback_to(&snapshot1);
     assert_eq!(map[&22], "twenty-two");
 }
diff --git a/src/librustc_data_structures/snapshot_vec.rs b/src/librustc_data_structures/snapshot_vec.rs
deleted file mode 100644
index 2da91918288..00000000000
--- a/src/librustc_data_structures/snapshot_vec.rs
+++ /dev/null
@@ -1,230 +0,0 @@
-// Copyright 2014 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.
-
-//! A utility class for implementing "snapshottable" things; a snapshottable data structure permits
-//! you to take a snapshot (via `start_snapshot`) and then, after making some changes, elect either
-//! to rollback to the start of the snapshot or commit those changes.
-//!
-//! This vector is intended to be used as part of an abstraction, not serve as a complete
-//! abstraction on its own. As such, while it will roll back most changes on its own, it also
-//! supports a `get_mut` operation that gives you an arbitrary mutable pointer into the vector. To
-//! ensure that any changes you make this with this pointer are rolled back, you must invoke
-//! `record` to record any changes you make and also supplying a delegate capable of reversing
-//! those changes.
-use self::UndoLog::*;
-
-use std::mem;
-use std::ops;
-
-pub enum UndoLog<D: SnapshotVecDelegate> {
-    /// Indicates where a snapshot started.
-    OpenSnapshot,
-
-    /// Indicates a snapshot that has been committed.
-    CommittedSnapshot,
-
-    /// New variable with given index was created.
-    NewElem(usize),
-
-    /// Variable with given index was changed *from* the given value.
-    SetElem(usize, D::Value),
-
-    /// Extensible set of actions
-    Other(D::Undo),
-}
-
-pub struct SnapshotVec<D: SnapshotVecDelegate> {
-    values: Vec<D::Value>,
-    undo_log: Vec<UndoLog<D>>,
-}
-
-// Snapshots are tokens that should be created/consumed linearly.
-pub struct Snapshot {
-    // Length of the undo log at the time the snapshot was taken.
-    length: usize,
-}
-
-pub trait SnapshotVecDelegate {
-    type Value;
-    type Undo;
-
-    fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
-}
-
-impl<D: SnapshotVecDelegate> SnapshotVec<D> {
-    pub fn new() -> SnapshotVec<D> {
-        SnapshotVec {
-            values: Vec::new(),
-            undo_log: Vec::new(),
-        }
-    }
-
-    pub fn with_capacity(n: usize) -> SnapshotVec<D> {
-        SnapshotVec {
-            values: Vec::with_capacity(n),
-            undo_log: Vec::new(),
-        }
-    }
-
-    fn in_snapshot(&self) -> bool {
-        !self.undo_log.is_empty()
-    }
-
-    pub fn record(&mut self, action: D::Undo) {
-        if self.in_snapshot() {
-            self.undo_log.push(Other(action));
-        }
-    }
-
-    pub fn len(&self) -> usize {
-        self.values.len()
-    }
-
-    pub fn push(&mut self, elem: D::Value) -> usize {
-        let len = self.values.len();
-        self.values.push(elem);
-
-        if self.in_snapshot() {
-            self.undo_log.push(NewElem(len));
-        }
-
-        len
-    }
-
-    pub fn get(&self, index: usize) -> &D::Value {
-        &self.values[index]
-    }
-
-    /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone
-    /// automatically, so you should be sure call `record()` with some sort of suitable undo
-    /// action.
-    pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
-        &mut self.values[index]
-    }
-
-    /// Updates the element at the given index. The old value will saved (and perhaps restored) if
-    /// a snapshot is active.
-    pub fn set(&mut self, index: usize, new_elem: D::Value) {
-        let old_elem = mem::replace(&mut self.values[index], new_elem);
-        if self.in_snapshot() {
-            self.undo_log.push(SetElem(index, old_elem));
-        }
-    }
-
-    pub fn start_snapshot(&mut self) -> Snapshot {
-        let length = self.undo_log.len();
-        self.undo_log.push(OpenSnapshot);
-        Snapshot { length: length }
-    }
-
-    pub fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[UndoLog<D>] {
-        &self.undo_log[snapshot.length..]
-    }
-
-    fn assert_open_snapshot(&self, snapshot: &Snapshot) {
-        // Or else there was a failure to follow a stack discipline:
-        assert!(self.undo_log.len() > snapshot.length);
-
-        // Invariant established by start_snapshot():
-        assert!(match self.undo_log[snapshot.length] {
-            OpenSnapshot => true,
-            _ => false,
-        });
-    }
-
-    pub fn rollback_to(&mut self, snapshot: Snapshot) {
-        debug!("rollback_to({})", snapshot.length);
-
-        self.assert_open_snapshot(&snapshot);
-
-        while self.undo_log.len() > snapshot.length + 1 {
-            match self.undo_log.pop().unwrap() {
-                OpenSnapshot => {
-                    // This indicates a failure to obey the stack discipline.
-                    panic!("Cannot rollback an uncommitted snapshot");
-                }
-
-                CommittedSnapshot => {
-                    // This occurs when there are nested snapshots and
-                    // the inner is committed but outer is rolled back.
-                }
-
-                NewElem(i) => {
-                    self.values.pop();
-                    assert!(self.values.len() == i);
-                }
-
-                SetElem(i, v) => {
-                    self.values[i] = v;
-                }
-
-                Other(u) => {
-                    D::reverse(&mut self.values, u);
-                }
-            }
-        }
-
-        let v = self.undo_log.pop().unwrap();
-        assert!(match v {
-            OpenSnapshot => true,
-            _ => false,
-        });
-        assert!(self.undo_log.len() == snapshot.length);
-    }
-
-    /// Commits all changes since the last snapshot. Of course, they
-    /// can still be undone if there is a snapshot further out.
-    pub fn commit(&mut self, snapshot: Snapshot) {
-        debug!("commit({})", snapshot.length);
-
-        self.assert_open_snapshot(&snapshot);
-
-        if snapshot.length == 0 {
-            // The root snapshot.
-            self.undo_log.truncate(0);
-        } else {
-            self.undo_log[snapshot.length] = CommittedSnapshot;
-        }
-    }
-}
-
-impl<D: SnapshotVecDelegate> ops::Deref for SnapshotVec<D> {
-    type Target = [D::Value];
-    fn deref(&self) -> &[D::Value] {
-        &*self.values
-    }
-}
-
-impl<D: SnapshotVecDelegate> ops::DerefMut for SnapshotVec<D> {
-    fn deref_mut(&mut self) -> &mut [D::Value] {
-        &mut *self.values
-    }
-}
-
-impl<D: SnapshotVecDelegate> ops::Index<usize> for SnapshotVec<D> {
-    type Output = D::Value;
-    fn index(&self, index: usize) -> &D::Value {
-        self.get(index)
-    }
-}
-
-impl<D: SnapshotVecDelegate> ops::IndexMut<usize> for SnapshotVec<D> {
-    fn index_mut(&mut self, index: usize) -> &mut D::Value {
-        self.get_mut(index)
-    }
-}
-
-impl<D: SnapshotVecDelegate> Extend<D::Value> for SnapshotVec<D> {
-    fn extend<T>(&mut self, iterable: T) where T: IntoIterator<Item=D::Value> {
-        for item in iterable {
-            self.push(item);
-        }
-    }
-}
diff --git a/src/librustc_data_structures/sorted_map.rs b/src/librustc_data_structures/sorted_map.rs
new file mode 100644
index 00000000000..730b13a0584
--- /dev/null
+++ b/src/librustc_data_structures/sorted_map.rs
@@ -0,0 +1,489 @@
+// 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 std::borrow::Borrow;
+use std::cmp::Ordering;
+use std::convert::From;
+use std::mem;
+use std::ops::{RangeBounds, Bound, Index, IndexMut};
+
+/// `SortedMap` is a data structure with similar characteristics as BTreeMap but
+/// slightly different trade-offs: lookup, inseration, and removal are O(log(N))
+/// and elements can be iterated in order cheaply.
+///
+/// `SortedMap` can be faster than a `BTreeMap` for small sizes (<50) since it
+/// stores data in a more compact way. It also supports accessing contiguous
+/// ranges of elements as a slice, and slices of already sorted elements can be
+/// inserted efficiently.
+#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Debug, RustcEncodable,
+         RustcDecodable)]
+pub struct SortedMap<K: Ord, V> {
+    data: Vec<(K,V)>
+}
+
+impl<K: Ord, V> SortedMap<K, V> {
+
+    #[inline]
+    pub fn new() -> SortedMap<K, V> {
+        SortedMap {
+            data: vec![]
+        }
+    }
+
+    /// Construct a `SortedMap` from a presorted set of elements. This is faster
+    /// than creating an empty map and then inserting the elements individually.
+    ///
+    /// It is up to the caller to make sure that the elements are sorted by key
+    /// and that there are no duplicates.
+    #[inline]
+    pub fn from_presorted_elements(elements: Vec<(K, V)>) -> SortedMap<K, V>
+    {
+        debug_assert!(elements.windows(2).all(|w| w[0].0 < w[1].0));
+
+        SortedMap {
+            data: elements
+        }
+    }
+
+    #[inline]
+    pub fn insert(&mut self, key: K, mut value: V) -> Option<V> {
+        match self.lookup_index_for(&key) {
+            Ok(index) => {
+                let slot = unsafe {
+                    self.data.get_unchecked_mut(index)
+                };
+                mem::swap(&mut slot.1, &mut value);
+                Some(value)
+            }
+            Err(index) => {
+                self.data.insert(index, (key, value));
+                None
+            }
+        }
+    }
+
+    #[inline]
+    pub fn remove(&mut self, key: &K) -> Option<V> {
+        match self.lookup_index_for(key) {
+            Ok(index) => {
+                Some(self.data.remove(index).1)
+            }
+            Err(_) => {
+                None
+            }
+        }
+    }
+
+    #[inline]
+    pub fn get(&self, key: &K) -> Option<&V> {
+        match self.lookup_index_for(key) {
+            Ok(index) => {
+                unsafe {
+                    Some(&self.data.get_unchecked(index).1)
+                }
+            }
+            Err(_) => {
+                None
+            }
+        }
+    }
+
+    #[inline]
+    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
+        match self.lookup_index_for(key) {
+            Ok(index) => {
+                unsafe {
+                    Some(&mut self.data.get_unchecked_mut(index).1)
+                }
+            }
+            Err(_) => {
+                None
+            }
+        }
+    }
+
+    #[inline]
+    pub fn clear(&mut self) {
+        self.data.clear();
+    }
+
+    /// Iterate over elements, sorted by key
+    #[inline]
+    pub fn iter(&self) -> ::std::slice::Iter<(K, V)> {
+        self.data.iter()
+    }
+
+    /// Iterate over the keys, sorted
+    #[inline]
+    pub fn keys(&self) -> impl Iterator<Item=&K> + ExactSizeIterator {
+        self.data.iter().map(|&(ref k, _)| k)
+    }
+
+    /// Iterate over values, sorted by key
+    #[inline]
+    pub fn values(&self) -> impl Iterator<Item=&V> + ExactSizeIterator {
+        self.data.iter().map(|&(_, ref v)| v)
+    }
+
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.data.len()
+    }
+
+    #[inline]
+    pub fn range<R>(&self, range: R) -> &[(K, V)]
+        where R: RangeBounds<K>
+    {
+        let (start, end) = self.range_slice_indices(range);
+        (&self.data[start .. end])
+    }
+
+    #[inline]
+    pub fn remove_range<R>(&mut self, range: R)
+        where R: RangeBounds<K>
+    {
+        let (start, end) = self.range_slice_indices(range);
+        self.data.splice(start .. end, ::std::iter::empty());
+    }
+
+    /// Mutate all keys with the given function `f`. This mutation must not
+    /// change the sort-order of keys.
+    #[inline]
+    pub fn offset_keys<F>(&mut self, f: F)
+        where F: Fn(&mut K)
+    {
+        self.data.iter_mut().map(|&mut (ref mut k, _)| k).for_each(f);
+    }
+
+    /// Inserts a presorted range of elements into the map. If the range can be
+    /// inserted as a whole in between to existing elements of the map, this
+    /// will be faster than inserting the elements individually.
+    ///
+    /// It is up to the caller to make sure that the elements are sorted by key
+    /// and that there are no duplicates.
+    #[inline]
+    pub fn insert_presorted(&mut self, mut elements: Vec<(K, V)>) {
+        if elements.is_empty() {
+            return
+        }
+
+        debug_assert!(elements.windows(2).all(|w| w[0].0 < w[1].0));
+
+        let start_index = self.lookup_index_for(&elements[0].0);
+
+        let drain = match start_index {
+            Ok(index) => {
+                let mut drain = elements.drain(..);
+                self.data[index] = drain.next().unwrap();
+                drain
+            }
+            Err(index) => {
+                if index == self.data.len() ||
+                   elements.last().unwrap().0 < self.data[index].0 {
+                    // We can copy the whole range without having to mix with
+                    // existing elements.
+                    self.data.splice(index .. index, elements.drain(..));
+                    return
+                }
+
+                let mut drain = elements.drain(..);
+                self.data.insert(index, drain.next().unwrap());
+                drain
+            }
+        };
+
+        // Insert the rest
+        for (k, v) in drain {
+            self.insert(k, v);
+        }
+    }
+
+    /// Looks up the key in `self.data` via `slice::binary_search()`.
+    #[inline(always)]
+    fn lookup_index_for(&self, key: &K) -> Result<usize, usize> {
+        self.data.binary_search_by(|&(ref x, _)| x.cmp(key))
+    }
+
+    #[inline]
+    fn range_slice_indices<R>(&self, range: R) -> (usize, usize)
+        where R: RangeBounds<K>
+    {
+        let start = match range.start_bound() {
+            Bound::Included(ref k) => {
+                match self.lookup_index_for(k) {
+                    Ok(index) | Err(index) => index
+                }
+            }
+            Bound::Excluded(ref k) => {
+                match self.lookup_index_for(k) {
+                    Ok(index) => index + 1,
+                    Err(index) => index,
+                }
+            }
+            Bound::Unbounded => 0,
+        };
+
+        let end = match range.end_bound() {
+            Bound::Included(ref k) => {
+                match self.lookup_index_for(k) {
+                    Ok(index) => index + 1,
+                    Err(index) => index,
+                }
+            }
+            Bound::Excluded(ref k) => {
+                match self.lookup_index_for(k) {
+                    Ok(index) | Err(index) => index,
+                }
+            }
+            Bound::Unbounded => self.data.len(),
+        };
+
+        (start, end)
+    }
+}
+
+impl<K: Ord, V> IntoIterator for SortedMap<K, V> {
+    type Item = (K, V);
+    type IntoIter = ::std::vec::IntoIter<(K, V)>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.data.into_iter()
+    }
+}
+
+impl<K: Ord, V, Q: Borrow<K>> Index<Q> for SortedMap<K, V> {
+    type Output = V;
+    fn index(&self, index: Q) -> &Self::Output {
+        let k: &K = index.borrow();
+        self.get(k).unwrap()
+    }
+}
+
+impl<K: Ord, V, Q: Borrow<K>> IndexMut<Q> for SortedMap<K, V> {
+    fn index_mut(&mut self, index: Q) -> &mut Self::Output {
+        let k: &K = index.borrow();
+        self.get_mut(k).unwrap()
+    }
+}
+
+impl<K: Ord, V, I: Iterator<Item=(K, V)>> From<I> for SortedMap<K, V> {
+    fn from(data: I) -> Self {
+        let mut data: Vec<(K, V)> = data.collect();
+        data.sort_unstable_by(|&(ref k1, _), &(ref k2, _)| k1.cmp(k2));
+        data.dedup_by(|&mut (ref k1, _), &mut (ref k2, _)| {
+            k1.cmp(k2) == Ordering::Equal
+        });
+        SortedMap {
+            data
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::SortedMap;
+
+    #[test]
+    fn test_insert_and_iter() {
+        let mut map = SortedMap::new();
+        let mut expected = Vec::new();
+
+        for x in 0 .. 100 {
+            assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected);
+
+            let x = 1000 - x * 2;
+            map.insert(x, x);
+            expected.insert(0, (x, x));
+        }
+    }
+
+    #[test]
+    fn test_get_and_index() {
+        let mut map = SortedMap::new();
+        let mut expected = Vec::new();
+
+        for x in 0 .. 100 {
+            let x = 1000 - x;
+            if x & 1 == 0 {
+                map.insert(x, x);
+            }
+            expected.push(x);
+        }
+
+        for mut x in expected {
+            if x & 1 == 0 {
+                assert_eq!(map.get(&x), Some(&x));
+                assert_eq!(map.get_mut(&x), Some(&mut x));
+                assert_eq!(map[&x], x);
+                assert_eq!(&mut map[&x], &mut x);
+            } else {
+                assert_eq!(map.get(&x), None);
+                assert_eq!(map.get_mut(&x), None);
+            }
+        }
+    }
+
+    #[test]
+    fn test_range() {
+        let mut map = SortedMap::new();
+        map.insert(1, 1);
+        map.insert(3, 3);
+        map.insert(6, 6);
+        map.insert(9, 9);
+
+        let keys = |s: &[(_, _)]| {
+            s.into_iter().map(|e| e.0).collect::<Vec<u32>>()
+        };
+
+        for start in 0 .. 11 {
+            for end in 0 .. 11 {
+                if end < start {
+                    continue
+                }
+
+                let mut expected = vec![1, 3, 6, 9];
+                expected.retain(|&x| x >= start && x < end);
+
+                assert_eq!(keys(map.range(start..end)), expected, "range = {}..{}", start, end);
+            }
+        }
+    }
+
+
+    #[test]
+    fn test_offset_keys() {
+        let mut map = SortedMap::new();
+        map.insert(1, 1);
+        map.insert(3, 3);
+        map.insert(6, 6);
+
+        map.offset_keys(|k| *k += 1);
+
+        let mut expected = SortedMap::new();
+        expected.insert(2, 1);
+        expected.insert(4, 3);
+        expected.insert(7, 6);
+
+        assert_eq!(map, expected);
+    }
+
+    fn keys(s: SortedMap<u32, u32>) -> Vec<u32> {
+        s.into_iter().map(|(k, _)| k).collect::<Vec<u32>>()
+    }
+
+    fn elements(s: SortedMap<u32, u32>) -> Vec<(u32, u32)> {
+        s.into_iter().collect::<Vec<(u32, u32)>>()
+    }
+
+    #[test]
+    fn test_remove_range() {
+        let mut map = SortedMap::new();
+        map.insert(1, 1);
+        map.insert(3, 3);
+        map.insert(6, 6);
+        map.insert(9, 9);
+
+        for start in 0 .. 11 {
+            for end in 0 .. 11 {
+                if end < start {
+                    continue
+                }
+
+                let mut expected = vec![1, 3, 6, 9];
+                expected.retain(|&x| x < start || x >= end);
+
+                let mut map = map.clone();
+                map.remove_range(start .. end);
+
+                assert_eq!(keys(map), expected, "range = {}..{}", start, end);
+            }
+        }
+    }
+
+    #[test]
+    fn test_remove() {
+        let mut map = SortedMap::new();
+        let mut expected = Vec::new();
+
+        for x in 0..10 {
+            map.insert(x, x);
+            expected.push((x, x));
+        }
+
+        for x in 0 .. 10 {
+            let mut map = map.clone();
+            let mut expected = expected.clone();
+
+            assert_eq!(map.remove(&x), Some(x));
+            expected.remove(x as usize);
+
+            assert_eq!(map.iter().cloned().collect::<Vec<_>>(), expected);
+        }
+    }
+
+    #[test]
+    fn test_insert_presorted_non_overlapping() {
+        let mut map = SortedMap::new();
+        map.insert(2, 0);
+        map.insert(8, 0);
+
+        map.insert_presorted(vec![(3, 0), (7, 0)]);
+
+        let expected = vec![2, 3, 7, 8];
+        assert_eq!(keys(map), expected);
+    }
+
+    #[test]
+    fn test_insert_presorted_first_elem_equal() {
+        let mut map = SortedMap::new();
+        map.insert(2, 2);
+        map.insert(8, 8);
+
+        map.insert_presorted(vec![(2, 0), (7, 7)]);
+
+        let expected = vec![(2, 0), (7, 7), (8, 8)];
+        assert_eq!(elements(map), expected);
+    }
+
+    #[test]
+    fn test_insert_presorted_last_elem_equal() {
+        let mut map = SortedMap::new();
+        map.insert(2, 2);
+        map.insert(8, 8);
+
+        map.insert_presorted(vec![(3, 3), (8, 0)]);
+
+        let expected = vec![(2, 2), (3, 3), (8, 0)];
+        assert_eq!(elements(map), expected);
+    }
+
+    #[test]
+    fn test_insert_presorted_shuffle() {
+        let mut map = SortedMap::new();
+        map.insert(2, 2);
+        map.insert(7, 7);
+
+        map.insert_presorted(vec![(1, 1), (3, 3), (8, 8)]);
+
+        let expected = vec![(1, 1), (2, 2), (3, 3), (7, 7), (8, 8)];
+        assert_eq!(elements(map), expected);
+    }
+
+    #[test]
+    fn test_insert_presorted_at_end() {
+        let mut map = SortedMap::new();
+        map.insert(1, 1);
+        map.insert(2, 2);
+
+        map.insert_presorted(vec![(3, 3), (8, 8)]);
+
+        let expected = vec![(1, 1), (2, 2), (3, 3), (8, 8)];
+        assert_eq!(elements(map), expected);
+    }
+}
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index d82b712b5b1..9f1c7dac119 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -165,29 +165,6 @@ impl<W> Hasher for StableHasher<W> {
     }
 }
 
-
-/// Something that can provide a stable hashing context.
-pub trait StableHashingContextProvider {
-    type ContextType;
-    fn create_stable_hashing_context(&self) -> Self::ContextType;
-}
-
-impl<'a, T: StableHashingContextProvider> StableHashingContextProvider for &'a T {
-    type ContextType = T::ContextType;
-
-    fn create_stable_hashing_context(&self) -> Self::ContextType {
-        (**self).create_stable_hashing_context()
-    }
-}
-
-impl<'a, T: StableHashingContextProvider> StableHashingContextProvider for &'a mut T {
-    type ContextType = T::ContextType;
-
-    fn create_stable_hashing_context(&self) -> Self::ContextType {
-        (**self).create_stable_hashing_context()
-    }
-}
-
 /// Something that implements `HashStable<CTX>` can be hashed in a way that is
 /// stable across multiple compilation sessions.
 pub trait HashStable<CTX> {
@@ -206,13 +183,16 @@ pub trait ToStableHashKey<HCX> {
 
 // Implement HashStable by just calling `Hash::hash()`. This works fine for
 // self-contained values that don't depend on the hashing context `CTX`.
+#[macro_export]
 macro_rules! impl_stable_hash_via_hash {
     ($t:ty) => (
-        impl<CTX> HashStable<CTX> for $t {
+        impl<CTX> $crate::stable_hasher::HashStable<CTX> for $t {
             #[inline]
-            fn hash_stable<W: StableHasherResult>(&self,
-                                                  _: &mut CTX,
-                                                  hasher: &mut StableHasher<W>) {
+            fn hash_stable<W: $crate::stable_hasher::StableHasherResult>(
+                &self,
+                _: &mut CTX,
+                hasher: &mut $crate::stable_hasher::StableHasher<W>
+            ) {
                 ::std::hash::Hash::hash(self, hasher);
             }
         }
@@ -259,6 +239,14 @@ impl<CTX> HashStable<CTX> for f64 {
     }
 }
 
+impl<CTX> HashStable<CTX> for ::std::cmp::Ordering {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        (*self as i8).hash_stable(ctx, hasher);
+    }
+}
+
 impl<T1: HashStable<CTX>, CTX> HashStable<CTX> for (T1,) {
     fn hash_stable<W: StableHasherResult>(&self,
                                           ctx: &mut CTX,
diff --git a/src/librustc_data_structures/svh.rs b/src/librustc_data_structures/svh.rs
new file mode 100644
index 00000000000..94f132562b5
--- /dev/null
+++ b/src/librustc_data_structures/svh.rs
@@ -0,0 +1,84 @@
+// Copyright 2012-2014 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.
+
+//! Calculation and management of a Strict Version Hash for crates
+//!
+//! The SVH is used for incremental compilation to track when HIR
+//! nodes have changed between compilations, and also to detect
+//! mismatches where we have two versions of the same crate that were
+//! compiled from distinct sources.
+
+use std::fmt;
+use std::hash::{Hash, Hasher};
+use serialize::{Encodable, Decodable, Encoder, Decoder};
+
+use stable_hasher;
+
+#[derive(Copy, Clone, PartialEq, Eq, Debug)]
+pub struct Svh {
+    hash: u64,
+}
+
+impl Svh {
+    /// Create a new `Svh` given the hash. If you actually want to
+    /// compute the SVH from some HIR, you want the `calculate_svh`
+    /// function found in `librustc_incremental`.
+    pub fn new(hash: u64) -> Svh {
+        Svh { hash: hash }
+    }
+
+    pub fn as_u64(&self) -> u64 {
+        self.hash
+    }
+
+    pub fn to_string(&self) -> String {
+        format!("{:016x}", self.hash)
+    }
+}
+
+impl Hash for Svh {
+    fn hash<H>(&self, state: &mut H) where H: Hasher {
+        self.hash.to_le().hash(state);
+    }
+}
+
+impl fmt::Display for Svh {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.pad(&self.to_string())
+    }
+}
+
+impl Encodable for Svh {
+    fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
+        s.emit_u64(self.as_u64().to_le())
+    }
+}
+
+impl Decodable for Svh {
+    fn decode<D: Decoder>(d: &mut D) -> Result<Svh, D::Error> {
+        d.read_u64()
+         .map(u64::from_le)
+         .map(Svh::new)
+    }
+}
+
+impl<T> stable_hasher::HashStable<T> for Svh {
+    #[inline]
+    fn hash_stable<W: stable_hasher::StableHasherResult>(
+        &self,
+        ctx: &mut T,
+        hasher: &mut stable_hasher::StableHasher<W>
+    ) {
+        let Svh {
+            hash
+        } = *self;
+        hash.hash_stable(ctx, hasher);
+    }
+}
diff --git a/src/librustc_data_structures/sync.rs b/src/librustc_data_structures/sync.rs
index b1ab4eaa069..d4c6b1c2ced 100644
--- a/src/librustc_data_structures/sync.rs
+++ b/src/librustc_data_structures/sync.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! This mdoule defines types which are thread safe if cfg!(parallel_queries) is true.
+//! This module defines types which are thread safe if cfg!(parallel_queries) is true.
 //!
 //! `Lrc` is an alias of either Rc or Arc.
 //!
@@ -26,20 +26,44 @@
 //!
 //! `MTLock` is a mutex which disappears if cfg!(parallel_queries) is false.
 //!
-//! `rustc_global!` gives us a way to declare variables which are intended to be
-//! global for the current rustc session. This currently maps to thread-locals,
-//! since rustdoc uses the rustc libraries in multiple threads.
-//! These globals should eventually be moved into the `Session` structure.
+//! `MTRef` is a immutable refernce if cfg!(parallel_queries), and an mutable reference otherwise.
 //!
 //! `rustc_erase_owner!` erases a OwningRef owner into Erased or Erased + Send + Sync
 //! depending on the value of cfg!(parallel_queries).
 
+use std::collections::HashMap;
+use std::hash::{Hash, BuildHasher};
 use std::cmp::Ordering;
+use std::marker::PhantomData;
 use std::fmt::Debug;
 use std::fmt::Formatter;
 use std::fmt;
+use std::ops::{Deref, DerefMut};
 use owning_ref::{Erased, OwningRef};
 
+pub fn serial_join<A, B, RA, RB>(oper_a: A, oper_b: B) -> (RA, RB)
+    where A: FnOnce() -> RA,
+          B: FnOnce() -> RB
+{
+    (oper_a(), oper_b())
+}
+
+pub struct SerialScope;
+
+impl SerialScope {
+    pub fn spawn<F>(&self, f: F)
+        where F: FnOnce(&SerialScope)
+    {
+        f(self)
+    }
+}
+
+pub fn serial_scope<F, R>(f: F) -> R
+    where F: FnOnce(&SerialScope) -> R
+{
+    f(&SerialScope)
+}
+
 cfg_if! {
     if #[cfg(not(parallel_queries))] {
         pub auto trait Send {}
@@ -55,19 +79,58 @@ cfg_if! {
             }
         }
 
-        pub type MetadataRef = OwningRef<Box<Erased>, [u8]>;
+        pub use self::serial_join as join;
+        pub use self::serial_scope as scope;
+
+        pub use std::iter::Iterator as ParallelIterator;
+
+        pub fn par_iter<T: IntoIterator>(t: T) -> T::IntoIter {
+            t.into_iter()
+        }
+
+        pub type MetadataRef = OwningRef<Box<dyn Erased>, [u8]>;
 
         pub use std::rc::Rc as Lrc;
+        pub use std::rc::Weak as Weak;
         pub use std::cell::Ref as ReadGuard;
         pub use std::cell::RefMut as WriteGuard;
         pub use std::cell::RefMut as LockGuard;
 
-        pub use std::cell::RefCell as RwLock;
+        use std::cell::RefCell as InnerRwLock;
         use std::cell::RefCell as InnerLock;
 
         use std::cell::Cell;
 
         #[derive(Debug)]
+        pub struct WorkerLocal<T>(OneThread<T>);
+
+        impl<T> WorkerLocal<T> {
+            /// Creates a new worker local where the `initial` closure computes the
+            /// value this worker local should take for each thread in the thread pool.
+            #[inline]
+            pub fn new<F: FnMut(usize) -> T>(mut f: F) -> WorkerLocal<T> {
+                WorkerLocal(OneThread::new(f(0)))
+            }
+
+            /// Returns the worker-local value for each thread
+            #[inline]
+            pub fn into_inner(self) -> Vec<T> {
+                vec![OneThread::into_inner(self.0)]
+            }
+        }
+
+        impl<T> Deref for WorkerLocal<T> {
+            type Target = T;
+
+            #[inline(always)]
+            fn deref(&self) -> &T {
+                &*self.0
+            }
+        }
+
+        pub type MTRef<'a, T> = &'a mut T;
+
+        #[derive(Debug)]
         pub struct MTLock<T>(T);
 
         impl<T> MTLock<T> {
@@ -92,13 +155,8 @@ cfg_if! {
             }
 
             #[inline(always)]
-            pub fn borrow(&self) -> &T {
-                &self.0
-            }
-
-            #[inline(always)]
-            pub fn borrow_mut(&self) -> &T {
-                &self.0
+            pub fn lock_mut(&mut self) -> &mut T {
+                &mut self.0
             }
         }
 
@@ -159,15 +217,58 @@ cfg_if! {
 
         pub use parking_lot::MutexGuard as LockGuard;
 
-        use parking_lot;
-
         pub use std::sync::Arc as Lrc;
+        pub use std::sync::Weak as Weak;
+
+        pub type MTRef<'a, T> = &'a T;
+
+        #[derive(Debug)]
+        pub struct MTLock<T>(Lock<T>);
+
+        impl<T> MTLock<T> {
+            #[inline(always)]
+            pub fn new(inner: T) -> Self {
+                MTLock(Lock::new(inner))
+            }
 
-        pub use self::Lock as MTLock;
+            #[inline(always)]
+            pub fn into_inner(self) -> T {
+                self.0.into_inner()
+            }
+
+            #[inline(always)]
+            pub fn get_mut(&mut self) -> &mut T {
+                self.0.get_mut()
+            }
+
+            #[inline(always)]
+            pub fn lock(&self) -> LockGuard<T> {
+                self.0.lock()
+            }
+
+            #[inline(always)]
+            pub fn lock_mut(&self) -> LockGuard<T> {
+                self.lock()
+            }
+        }
 
         use parking_lot::Mutex as InnerLock;
+        use parking_lot::RwLock as InnerRwLock;
+
+        use std;
+        use std::thread;
+        pub use rayon::{join, scope};
 
-        pub type MetadataRef = OwningRef<Box<Erased + Send + Sync>, [u8]>;
+        pub use rayon_core::WorkerLocal;
+
+        pub use rayon::iter::ParallelIterator;
+        use rayon::iter::IntoParallelIterator;
+
+        pub fn par_iter<T: IntoParallelIterator>(t: T) -> T::Iter {
+            t.into_par_iter()
+        }
+
+        pub type MetadataRef = OwningRef<Box<dyn Erased + Send + Sync>, [u8]>;
 
         /// This makes locks panic if they are already held.
         /// It is only useful when you are running in a single thread
@@ -177,7 +278,7 @@ cfg_if! {
         macro_rules! rustc_erase_owner {
             ($v:expr) => {{
                 let v = $v;
-                ::rustc_data_structures::sync::assert_send_sync_val(&v);
+                ::rustc_data_structures::sync::assert_send_val(&v);
                 v.erase_send_sync_owner()
             }}
         }
@@ -222,70 +323,150 @@ cfg_if! {
                 self.0.lock().take()
             }
         }
+    }
+}
 
-        #[derive(Debug)]
-        pub struct RwLock<T>(parking_lot::RwLock<T>);
+pub fn assert_sync<T: ?Sized + Sync>() {}
+pub fn assert_send_val<T: ?Sized + Send>(_t: &T) {}
+pub fn assert_send_sync_val<T: ?Sized + Sync + Send>(_t: &T) {}
 
-        impl<T> RwLock<T> {
-            #[inline(always)]
-            pub fn new(inner: T) -> Self {
-                RwLock(parking_lot::RwLock::new(inner))
-            }
+pub trait HashMapExt<K, V> {
+    /// Same as HashMap::insert, but it may panic if there's already an
+    /// entry for `key` with a value not equal to `value`
+    fn insert_same(&mut self, key: K, value: V);
+}
 
-            #[inline(always)]
-            pub fn borrow(&self) -> ReadGuard<T> {
-                if ERROR_CHECKING {
-                    self.0.try_read().expect("lock was already held")
-                } else {
-                    self.0.read()
-                }
-            }
+impl<K: Eq + Hash, V: Eq, S: BuildHasher> HashMapExt<K, V> for HashMap<K, V, S> {
+    fn insert_same(&mut self, key: K, value: V) {
+        self.entry(key).and_modify(|old| assert!(*old == value)).or_insert(value);
+    }
+}
 
-            #[inline(always)]
-            pub fn borrow_mut(&self) -> WriteGuard<T> {
-                if ERROR_CHECKING {
-                    self.0.try_write().expect("lock was already held")
-                } else {
-                    self.0.write()
-                }
-            }
+/// A type whose inner value can be written once and then will stay read-only
+// This contains a PhantomData<T> since this type conceptually owns a T outside the Mutex once
+// initialized. This ensures that Once<T> is Sync only if T is. If we did not have PhantomData<T>
+// we could send a &Once<Cell<bool>> to multiple threads and call `get` on it to get access
+// to &Cell<bool> on those threads.
+pub struct Once<T>(Lock<Option<T>>, PhantomData<T>);
+
+impl<T> Once<T> {
+    /// Creates an Once value which is uninitialized
+    #[inline(always)]
+    pub fn new() -> Self {
+        Once(Lock::new(None), PhantomData)
+    }
+
+    /// Consumes the value and returns Some(T) if it was initialized
+    #[inline(always)]
+    pub fn into_inner(self) -> Option<T> {
+        self.0.into_inner()
+    }
+
+    /// Tries to initialize the inner value to `value`.
+    /// Returns `None` if the inner value was uninitialized and `value` was consumed setting it
+    /// otherwise if the inner value was already set it returns `value` back to the caller
+    #[inline]
+    pub fn try_set(&self, value: T) -> Option<T> {
+        let mut lock = self.0.lock();
+        if lock.is_some() {
+            return Some(value);
         }
+        *lock = Some(value);
+        None
+    }
 
-        // FIXME: Probably a bad idea
-        impl<T: Clone> Clone for RwLock<T> {
-            #[inline]
-            fn clone(&self) -> Self {
-                RwLock::new(self.borrow().clone())
-            }
+    /// Tries to initialize the inner value to `value`.
+    /// Returns `None` if the inner value was uninitialized and `value` was consumed setting it
+    /// otherwise if the inner value was already set it asserts that `value` is equal to the inner
+    /// value and then returns `value` back to the caller
+    #[inline]
+    pub fn try_set_same(&self, value: T) -> Option<T> where T: Eq {
+        let mut lock = self.0.lock();
+        if let Some(ref inner) = *lock {
+            assert!(*inner == value);
+            return Some(value);
         }
+        *lock = Some(value);
+        None
     }
-}
 
-pub fn assert_sync<T: ?Sized + Sync>() {}
-pub fn assert_send_sync_val<T: ?Sized + Sync + Send>(_t: &T) {}
+    /// Tries to initialize the inner value to `value` and panics if it was already initialized
+    #[inline]
+    pub fn set(&self, value: T) {
+        assert!(self.try_set(value).is_none());
+    }
 
-#[macro_export]
-#[allow_internal_unstable]
-macro_rules! rustc_global {
-    // empty (base case for the recursion)
-    () => {};
-
-    // process multiple declarations
-    ($(#[$attr:meta])* $vis:vis static $name:ident: $t:ty = $init:expr; $($rest:tt)*) => (
-        thread_local!($(#[$attr])* $vis static $name: $t = $init);
-        rustc_global!($($rest)*);
-    );
-
-    // handle a single declaration
-    ($(#[$attr:meta])* $vis:vis static $name:ident: $t:ty = $init:expr) => (
-        thread_local!($(#[$attr])* $vis static $name: $t = $init);
-    );
-}
+    /// Tries to initialize the inner value by calling the closure while ensuring that no-one else
+    /// can access the value in the mean time by holding a lock for the duration of the closure.
+    /// If the value was already initialized the closure is not called and `false` is returned,
+    /// otherwise if the value from the closure initializes the inner value, `true` is returned
+    #[inline]
+    pub fn init_locking<F: FnOnce() -> T>(&self, f: F) -> bool {
+        let mut lock = self.0.lock();
+        if lock.is_some() {
+            return false;
+        }
+        *lock = Some(f());
+        true
+    }
+
+    /// Tries to initialize the inner value by calling the closure without ensuring that no-one
+    /// else can access it. This mean when this is called from multiple threads, multiple
+    /// closures may concurrently be computing a value which the inner value should take.
+    /// Only one of these closures are used to actually initialize the value.
+    /// If some other closure already set the value,
+    /// we return the value our closure computed wrapped in a `Option`.
+    /// If our closure set the value, `None` is returned.
+    /// If the value is already initialized, the closure is not called and `None` is returned.
+    #[inline]
+    pub fn init_nonlocking<F: FnOnce() -> T>(&self, f: F) -> Option<T> {
+        if self.0.lock().is_some() {
+            None
+        } else {
+            self.try_set(f())
+        }
+    }
 
-#[macro_export]
-macro_rules! rustc_access_global {
-    ($name:path, $callback:expr) => {
-        $name.with($callback)
+    /// Tries to initialize the inner value by calling the closure without ensuring that no-one
+    /// else can access it. This mean when this is called from multiple threads, multiple
+    /// closures may concurrently be computing a value which the inner value should take.
+    /// Only one of these closures are used to actually initialize the value.
+    /// If some other closure already set the value, we assert that it our closure computed
+    /// a value equal to the value aready set and then
+    /// we return the value our closure computed wrapped in a `Option`.
+    /// If our closure set the value, `None` is returned.
+    /// If the value is already initialized, the closure is not called and `None` is returned.
+    #[inline]
+    pub fn init_nonlocking_same<F: FnOnce() -> T>(&self, f: F) -> Option<T> where T: Eq {
+        if self.0.lock().is_some() {
+            None
+        } else {
+            self.try_set_same(f())
+        }
+    }
+
+    /// Tries to get a reference to the inner value, returns `None` if it is not yet initialized
+    #[inline(always)]
+    pub fn try_get(&self) -> Option<&T> {
+        let lock = &*self.0.lock();
+        if let Some(ref inner) = *lock {
+            // This is safe since we won't mutate the inner value
+            unsafe { Some(&*(inner as *const T)) }
+        } else {
+            None
+        }
+    }
+
+    /// Gets reference to the inner value, panics if it is not yet initialized
+    #[inline(always)]
+    pub fn get(&self) -> &T {
+        self.try_get().expect("value was not set")
+    }
+
+    /// Gets reference to the inner value, panics if it is not yet initialized
+    #[inline(always)]
+    pub fn borrow(&self) -> &T {
+        self.get()
     }
 }
 
@@ -369,6 +550,18 @@ impl<T> Lock<T> {
 
     #[cfg(parallel_queries)]
     #[inline(always)]
+    pub fn try_lock(&self) -> Option<LockGuard<T>> {
+        self.0.try_lock()
+    }
+
+    #[cfg(not(parallel_queries))]
+    #[inline(always)]
+    pub fn try_lock(&self) -> Option<LockGuard<T>> {
+        self.0.try_borrow_mut().ok()
+    }
+
+    #[cfg(parallel_queries)]
+    #[inline(always)]
     pub fn lock(&self) -> LockGuard<T> {
         if ERROR_CHECKING {
             self.0.try_lock().expect("lock was already held")
@@ -384,6 +577,11 @@ impl<T> Lock<T> {
     }
 
     #[inline(always)]
+    pub fn with_lock<F: FnOnce(&mut T) -> R, R>(&self, f: F) -> R {
+        f(&mut *self.lock())
+    }
+
+    #[inline(always)]
     pub fn borrow(&self) -> LockGuard<T> {
         self.lock()
     }
@@ -394,6 +592,13 @@ impl<T> Lock<T> {
     }
 }
 
+impl<T: Default> Default for Lock<T> {
+    #[inline]
+    fn default() -> Self {
+        Lock::new(T::default())
+    }
+}
+
 // FIXME: Probably a bad idea
 impl<T: Clone> Clone for Lock<T> {
     #[inline]
@@ -401,3 +606,148 @@ impl<T: Clone> Clone for Lock<T> {
         Lock::new(self.borrow().clone())
     }
 }
+
+#[derive(Debug)]
+pub struct RwLock<T>(InnerRwLock<T>);
+
+impl<T> RwLock<T> {
+    #[inline(always)]
+    pub fn new(inner: T) -> Self {
+        RwLock(InnerRwLock::new(inner))
+    }
+
+    #[inline(always)]
+    pub fn into_inner(self) -> T {
+        self.0.into_inner()
+    }
+
+    #[inline(always)]
+    pub fn get_mut(&mut self) -> &mut T {
+        self.0.get_mut()
+    }
+
+    #[cfg(not(parallel_queries))]
+    #[inline(always)]
+    pub fn read(&self) -> ReadGuard<T> {
+        self.0.borrow()
+    }
+
+    #[cfg(parallel_queries)]
+    #[inline(always)]
+    pub fn read(&self) -> ReadGuard<T> {
+        if ERROR_CHECKING {
+            self.0.try_read().expect("lock was already held")
+        } else {
+            self.0.read()
+        }
+    }
+
+    #[inline(always)]
+    pub fn with_read_lock<F: FnOnce(&T) -> R, R>(&self, f: F) -> R {
+        f(&*self.read())
+    }
+
+    #[cfg(not(parallel_queries))]
+    #[inline(always)]
+    pub fn try_write(&self) -> Result<WriteGuard<T>, ()> {
+        self.0.try_borrow_mut().map_err(|_| ())
+    }
+
+    #[cfg(parallel_queries)]
+    #[inline(always)]
+    pub fn try_write(&self) -> Result<WriteGuard<T>, ()> {
+        self.0.try_write().ok_or(())
+    }
+
+    #[cfg(not(parallel_queries))]
+    #[inline(always)]
+    pub fn write(&self) -> WriteGuard<T> {
+        self.0.borrow_mut()
+    }
+
+    #[cfg(parallel_queries)]
+    #[inline(always)]
+    pub fn write(&self) -> WriteGuard<T> {
+        if ERROR_CHECKING {
+            self.0.try_write().expect("lock was already held")
+        } else {
+            self.0.write()
+        }
+    }
+
+    #[inline(always)]
+    pub fn with_write_lock<F: FnOnce(&mut T) -> R, R>(&self, f: F) -> R {
+        f(&mut *self.write())
+    }
+
+    #[inline(always)]
+    pub fn borrow(&self) -> ReadGuard<T> {
+        self.read()
+    }
+
+    #[inline(always)]
+    pub fn borrow_mut(&self) -> WriteGuard<T> {
+        self.write()
+    }
+}
+
+// FIXME: Probably a bad idea
+impl<T: Clone> Clone for RwLock<T> {
+    #[inline]
+    fn clone(&self) -> Self {
+        RwLock::new(self.borrow().clone())
+    }
+}
+
+/// A type which only allows its inner value to be used in one thread.
+/// It will panic if it is used on multiple threads.
+#[derive(Copy, Clone, Hash, Debug, Eq, PartialEq)]
+pub struct OneThread<T> {
+    #[cfg(parallel_queries)]
+    thread: thread::ThreadId,
+    inner: T,
+}
+
+#[cfg(parallel_queries)]
+unsafe impl<T> std::marker::Sync for OneThread<T> {}
+#[cfg(parallel_queries)]
+unsafe impl<T> std::marker::Send for OneThread<T> {}
+
+impl<T> OneThread<T> {
+    #[inline(always)]
+    fn check(&self) {
+        #[cfg(parallel_queries)]
+        assert_eq!(thread::current().id(), self.thread);
+    }
+
+    #[inline(always)]
+    pub fn new(inner: T) -> Self {
+        OneThread {
+            #[cfg(parallel_queries)]
+            thread: thread::current().id(),
+            inner,
+        }
+    }
+
+    #[inline(always)]
+    pub fn into_inner(value: Self) -> T {
+        value.check();
+        value.inner
+    }
+}
+
+impl<T> Deref for OneThread<T> {
+    type Target = T;
+
+    fn deref(&self) -> &T {
+        self.check();
+        &self.inner
+    }
+}
+
+impl<T> DerefMut for OneThread<T> {
+    fn deref_mut(&mut self) -> &mut T {
+        self.check();
+        &mut self.inner
+    }
+}
diff --git a/src/librustc_data_structures/thin_vec.rs b/src/librustc_data_structures/thin_vec.rs
new file mode 100644
index 00000000000..546686b46b8
--- /dev/null
+++ b/src/librustc_data_structures/thin_vec.rs
@@ -0,0 +1,59 @@
+// 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.
+
+/// A vector type optimized for cases where this size is usually 0 (c.f. `SmallVector`).
+/// The `Option<Box<..>>` wrapping allows us to represent a zero sized vector with `None`,
+/// which uses only a single (null) pointer.
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
+pub struct ThinVec<T>(Option<Box<Vec<T>>>);
+
+impl<T> ThinVec<T> {
+    pub fn new() -> Self {
+        ThinVec(None)
+    }
+}
+
+impl<T> From<Vec<T>> for ThinVec<T> {
+    fn from(vec: Vec<T>) -> Self {
+        if vec.is_empty() {
+            ThinVec(None)
+        } else {
+            ThinVec(Some(Box::new(vec)))
+        }
+    }
+}
+
+impl<T> Into<Vec<T>> for ThinVec<T> {
+    fn into(self) -> Vec<T> {
+        match self {
+            ThinVec(None) => Vec::new(),
+            ThinVec(Some(vec)) => *vec,
+        }
+    }
+}
+
+impl<T> ::std::ops::Deref for ThinVec<T> {
+    type Target = [T];
+    fn deref(&self) -> &[T] {
+        match *self {
+            ThinVec(None) => &[],
+            ThinVec(Some(ref vec)) => vec,
+        }
+    }
+}
+
+impl<T> Extend<T> for ThinVec<T> {
+    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
+        match *self {
+            ThinVec(Some(ref mut vec)) => vec.extend(iter),
+            ThinVec(None) => *self = iter.into_iter().collect::<Vec<_>>().into(),
+        }
+    }
+}
diff --git a/src/librustc_data_structures/tiny_list.rs b/src/librustc_data_structures/tiny_list.rs
new file mode 100644
index 00000000000..e1bfdf35b27
--- /dev/null
+++ b/src/librustc_data_structures/tiny_list.rs
@@ -0,0 +1,269 @@
+// 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.
+
+
+//! A singly-linked list.
+//!
+//! Using this data structure only makes sense under very specific
+//! circumstances:
+//!
+//! - If you have a list that rarely stores more than one element, then this
+//!   data-structure can store the element without allocating and only uses as
+//!   much space as a `Option<(T, usize)>`. If T can double as the `Option`
+//!   discriminant, it will even only be as large as `T, usize`.
+//!
+//! If you expect to store more than 1 element in the common case, steer clear
+//! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`.
+
+use std::mem;
+
+#[derive(Clone, Hash, Debug, PartialEq)]
+pub struct TinyList<T: PartialEq> {
+    head: Option<Element<T>>
+}
+
+impl<T: PartialEq> TinyList<T> {
+
+    #[inline]
+    pub fn new() -> TinyList<T> {
+        TinyList {
+            head: None
+        }
+    }
+
+    #[inline]
+    pub fn new_single(data: T) -> TinyList<T> {
+        TinyList {
+            head: Some(Element {
+                data,
+                next: None,
+            })
+        }
+    }
+
+    #[inline]
+    pub fn insert(&mut self, data: T) {
+        self.head = Some(Element {
+            data,
+            next: mem::replace(&mut self.head, None).map(Box::new),
+        });
+    }
+
+    #[inline]
+    pub fn remove(&mut self, data: &T) -> bool {
+        self.head = match self.head {
+            Some(ref mut head) if head.data == *data => {
+                mem::replace(&mut head.next, None).map(|x| *x)
+            }
+            Some(ref mut head) => return head.remove_next(data),
+            None => return false,
+        };
+        true
+    }
+
+    #[inline]
+    pub fn contains(&self, data: &T) -> bool {
+        if let Some(ref head) = self.head {
+            head.contains(data)
+        } else {
+            false
+        }
+    }
+
+    #[inline]
+    pub fn len(&self) -> usize {
+        if let Some(ref head) = self.head {
+            head.len()
+        } else {
+            0
+        }
+    }
+}
+
+#[derive(Clone, Hash, Debug, PartialEq)]
+struct Element<T: PartialEq> {
+    data: T,
+    next: Option<Box<Element<T>>>,
+}
+
+impl<T: PartialEq> Element<T> {
+
+    fn remove_next(&mut self, data: &T) -> bool {
+        let new_next = if let Some(ref mut next) = self.next {
+            if next.data != *data {
+                return next.remove_next(data)
+            } else {
+                mem::replace(&mut next.next, None)
+            }
+        } else {
+            return false
+        };
+
+        self.next = new_next;
+
+        true
+    }
+
+    fn len(&self) -> usize {
+        if let Some(ref next) = self.next {
+            1 + next.len()
+        } else {
+            1
+        }
+    }
+
+    fn contains(&self, data: &T) -> bool {
+        if self.data == *data {
+            return true
+        }
+
+        if let Some(ref next) = self.next {
+            next.contains(data)
+        } else {
+            false
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    extern crate test;
+    use self::test::Bencher;
+
+    #[test]
+    fn test_contains_and_insert() {
+        fn do_insert(i : u32) -> bool {
+            i % 2 == 0
+        }
+
+        let mut list = TinyList::new();
+
+        for i in 0 .. 10 {
+            for j in 0 .. i {
+                if do_insert(j) {
+                    assert!(list.contains(&j));
+                } else {
+                    assert!(!list.contains(&j));
+                }
+            }
+
+            assert!(!list.contains(&i));
+
+            if do_insert(i) {
+                list.insert(i);
+                assert!(list.contains(&i));
+            }
+        }
+    }
+
+    #[test]
+    fn test_remove_first() {
+        let mut list = TinyList::new();
+        list.insert(1);
+        list.insert(2);
+        list.insert(3);
+        list.insert(4);
+        assert_eq!(list.len(), 4);
+
+        assert!(list.remove(&4));
+        assert!(!list.contains(&4));
+
+        assert_eq!(list.len(), 3);
+        assert!(list.contains(&1));
+        assert!(list.contains(&2));
+        assert!(list.contains(&3));
+    }
+
+    #[test]
+    fn test_remove_last() {
+        let mut list = TinyList::new();
+        list.insert(1);
+        list.insert(2);
+        list.insert(3);
+        list.insert(4);
+        assert_eq!(list.len(), 4);
+
+        assert!(list.remove(&1));
+        assert!(!list.contains(&1));
+
+        assert_eq!(list.len(), 3);
+        assert!(list.contains(&2));
+        assert!(list.contains(&3));
+        assert!(list.contains(&4));
+    }
+
+    #[test]
+    fn test_remove_middle() {
+        let mut list = TinyList::new();
+        list.insert(1);
+        list.insert(2);
+        list.insert(3);
+        list.insert(4);
+        assert_eq!(list.len(), 4);
+
+        assert!(list.remove(&2));
+        assert!(!list.contains(&2));
+
+        assert_eq!(list.len(), 3);
+        assert!(list.contains(&1));
+        assert!(list.contains(&3));
+        assert!(list.contains(&4));
+    }
+
+    #[test]
+    fn test_remove_single() {
+        let mut list = TinyList::new();
+        list.insert(1);
+        assert_eq!(list.len(), 1);
+
+        assert!(list.remove(&1));
+        assert!(!list.contains(&1));
+
+        assert_eq!(list.len(), 0);
+    }
+
+    #[bench]
+    fn bench_insert_empty(b: &mut Bencher) {
+        b.iter(|| {
+            let mut list = TinyList::new();
+            list.insert(1);
+        })
+    }
+
+    #[bench]
+    fn bench_insert_one(b: &mut Bencher) {
+        b.iter(|| {
+            let mut list = TinyList::new_single(0);
+            list.insert(1);
+        })
+    }
+
+    #[bench]
+    fn bench_remove_empty(b: &mut Bencher) {
+        b.iter(|| {
+            TinyList::new().remove(&1)
+        });
+    }
+
+    #[bench]
+    fn bench_remove_unknown(b: &mut Bencher) {
+        b.iter(|| {
+            TinyList::new_single(0).remove(&1)
+        });
+    }
+
+    #[bench]
+    fn bench_remove_one(b: &mut Bencher) {
+        b.iter(|| {
+            TinyList::new_single(1).remove(&1)
+        });
+    }
+}
diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index ba7ab0c07c6..2acc29acb0c 100644
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -10,16 +10,16 @@
 
 use bitvec::BitMatrix;
 use fx::FxHashMap;
+use sync::Lock;
 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
 use stable_hasher::{HashStable, StableHasher, StableHasherResult};
-use std::cell::RefCell;
 use std::fmt::Debug;
 use std::hash::Hash;
 use std::mem;
 
 
 #[derive(Clone, Debug)]
-pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash + Clone> {
+pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash> {
     // List of elements. This is used to map from a T to a usize.
     elements: Vec<T>,
 
@@ -32,14 +32,14 @@ pub struct TransitiveRelation<T: Clone + Debug + Eq + Hash + Clone> {
 
     // This is a cached transitive closure derived from the edges.
     // Currently, we build it lazilly and just throw out any existing
-    // copy whenever a new edge is added. (The RefCell is to permit
+    // copy whenever a new edge is added. (The Lock is to permit
     // the lazy computation.) This is kind of silly, except for the
     // fact its size is tied to `self.elements.len()`, so I wanted to
     // wait before building it up to avoid reallocating as new edges
     // are added with new elements. Perhaps better would be to ask the
     // user for a batch of edges to minimize this effect, but I
     // already wrote the code this way. :P -nmatsakis
-    closure: RefCell<Option<BitMatrix>>,
+    closure: Lock<Option<BitMatrix<usize, usize>>>,
 }
 
 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable, Debug)]
@@ -51,13 +51,13 @@ struct Edge {
     target: Index,
 }
 
-impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> {
+impl<T: Clone + Debug + Eq + Hash> TransitiveRelation<T> {
     pub fn new() -> TransitiveRelation<T> {
         TransitiveRelation {
             elements: vec![],
             map: FxHashMap(),
             edges: vec![],
-            closure: RefCell::new(None),
+            closure: Lock::new(None),
         }
     }
 
@@ -72,21 +72,20 @@ impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> {
     fn add_index(&mut self, a: T) -> Index {
         let &mut TransitiveRelation {
             ref mut elements,
-            ref closure,
+            ref mut closure,
             ref mut map,
             ..
         } = self;
 
-        map.entry(a.clone())
+        *map.entry(a.clone())
            .or_insert_with(|| {
                elements.push(a);
 
                // if we changed the dimensions, clear the cache
-               *closure.borrow_mut() = None;
+               *closure.get_mut() = None;
 
                Index(elements.len() - 1)
            })
-           .clone()
     }
 
     /// Applies the (partial) function to each edge and returns a new
@@ -98,14 +97,7 @@ impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> {
     {
         let mut result = TransitiveRelation::new();
         for edge in &self.edges {
-            let r = f(&self.elements[edge.source.0]).and_then(|source| {
-                f(&self.elements[edge.target.0]).and_then(|target| {
-                    Some(result.add(source, target))
-                })
-            });
-            if r.is_none() {
-                return None;
-            }
+            result.add(f(&self.elements[edge.source.0])?, f(&self.elements[edge.target.0])?);
         }
         Some(result)
     }
@@ -122,7 +114,7 @@ impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> {
             self.edges.push(edge);
 
             // added an edge, clear the cache
-            *self.closure.borrow_mut() = None;
+            *self.closure.get_mut() = None;
         }
     }
 
@@ -354,7 +346,7 @@ impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> {
     }
 
     fn with_closure<OP, R>(&self, op: OP) -> R
-        where OP: FnOnce(&BitMatrix) -> R
+        where OP: FnOnce(&BitMatrix<usize, usize>) -> R
     {
         let mut closure_cell = self.closure.borrow_mut();
         let mut closure = closure_cell.take();
@@ -366,13 +358,13 @@ impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> {
         result
     }
 
-    fn compute_closure(&self) -> BitMatrix {
+    fn compute_closure(&self) -> BitMatrix<usize, usize> {
         let mut matrix = BitMatrix::new(self.elements.len(),
                                         self.elements.len());
         let mut changed = true;
         while changed {
             changed = false;
-            for edge in self.edges.iter() {
+            for edge in &self.edges {
                 // add an edge from S -> T
                 changed |= matrix.add(edge.source.0, edge.target.0);
 
@@ -396,7 +388,7 @@ impl<T: Clone + Debug + Eq + Hash + Clone> TransitiveRelation<T> {
 /// - Input: `[a, b, x]`. Output: `[a, x]`.
 /// - Input: `[b, a, x]`. Output: `[b, a, x]`.
 /// - Input: `[a, x, b, y]`. Output: `[a, x]`.
-fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix) {
+fn pare_down(candidates: &mut Vec<usize>, closure: &BitMatrix<usize, usize>) {
     let mut i = 0;
     while i < candidates.len() {
         let candidate_i = candidates[i];
@@ -443,7 +435,7 @@ impl<T> Decodable for TransitiveRelation<T>
                               .enumerate()
                               .map(|(index, elem)| (elem.clone(), Index(index)))
                               .collect();
-            Ok(TransitiveRelation { elements, edges, map, closure: RefCell::new(None) })
+            Ok(TransitiveRelation { elements, edges, map, closure: Lock::new(None) })
         })
     }
 }
diff --git a/src/librustc_data_structures/unify/mod.rs b/src/librustc_data_structures/unify/mod.rs
deleted file mode 100644
index 5411ae0257a..00000000000
--- a/src/librustc_data_structures/unify/mod.rs
+++ /dev/null
@@ -1,363 +0,0 @@
-// Copyright 2012-2014 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 std::marker;
-use std::fmt::Debug;
-use std::marker::PhantomData;
-use snapshot_vec as sv;
-
-#[cfg(test)]
-mod tests;
-
-/// This trait is implemented by any type that can serve as a type
-/// variable. We call such variables *unification keys*. For example,
-/// this trait is implemented by `IntVid`, which represents integral
-/// variables.
-///
-/// Each key type has an associated value type `V`. For example, for
-/// `IntVid`, this is `Option<IntVarValue>`, representing some
-/// (possibly not yet known) sort of integer.
-///
-/// Clients are expected to provide implementations of this trait; you
-/// can see some examples in the `test` module.
-pub trait UnifyKey: Copy + Clone + Debug + PartialEq {
-    type Value: Clone + PartialEq + Debug;
-
-    fn index(&self) -> u32;
-
-    fn from_index(u: u32) -> Self;
-
-    fn tag(k: Option<Self>) -> &'static str;
-}
-
-/// This trait is implemented for unify values that can be
-/// combined. This relation should be a monoid.
-pub trait Combine {
-    fn combine(&self, other: &Self) -> Self;
-}
-
-impl Combine for () {
-    fn combine(&self, _other: &()) {}
-}
-
-/// Value of a unification key. We implement Tarjan's union-find
-/// algorithm: when two keys are unified, one of them is converted
-/// into a "redirect" pointing at the other. These redirects form a
-/// DAG: the roots of the DAG (nodes that are not redirected) are each
-/// associated with a value of type `V` and a rank. The rank is used
-/// to keep the DAG relatively balanced, which helps keep the running
-/// time of the algorithm under control. For more information, see
-/// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
-#[derive(PartialEq,Clone,Debug)]
-pub struct VarValue<K: UnifyKey> {
-    parent: K, // if equal to self, this is a root
-    value: K::Value, // value assigned (only relevant to root)
-    rank: u32, // max depth (only relevant to root)
-}
-
-/// Table of unification keys and their values.
-pub struct UnificationTable<K: UnifyKey> {
-    /// Indicates the current value of each key.
-    values: sv::SnapshotVec<Delegate<K>>,
-}
-
-/// At any time, users may snapshot a unification table.  The changes
-/// made during the snapshot may either be *committed* or *rolled back*.
-pub struct Snapshot<K: UnifyKey> {
-    // Link snapshot to the key type `K` of the table.
-    marker: marker::PhantomData<K>,
-    snapshot: sv::Snapshot,
-}
-
-#[derive(Copy, Clone)]
-struct Delegate<K>(PhantomData<K>);
-
-impl<K: UnifyKey> VarValue<K> {
-    fn new_var(key: K, value: K::Value) -> VarValue<K> {
-        VarValue::new(key, value, 0)
-    }
-
-    fn new(parent: K, value: K::Value, rank: u32) -> VarValue<K> {
-        VarValue {
-            parent: parent, // this is a root
-            value,
-            rank,
-        }
-    }
-
-    fn redirect(self, to: K) -> VarValue<K> {
-        VarValue { parent: to, ..self }
-    }
-
-    fn root(self, rank: u32, value: K::Value) -> VarValue<K> {
-        VarValue {
-            rank,
-            value,
-            ..self
-        }
-    }
-
-    /// Returns the key of this node. Only valid if this is a root
-    /// node, which you yourself must ensure.
-    fn key(&self) -> K {
-        self.parent
-    }
-
-    fn parent(&self, self_key: K) -> Option<K> {
-        self.if_not_self(self.parent, self_key)
-    }
-
-    fn if_not_self(&self, key: K, self_key: K) -> Option<K> {
-        if key == self_key { None } else { Some(key) }
-    }
-}
-
-/// We can't use V:LatticeValue, much as I would like to,
-/// because frequently the pattern is that V=Option<U> for some
-/// other type parameter U, and we have no way to say
-/// Option<U>:LatticeValue.
-
-impl<K: UnifyKey> UnificationTable<K> {
-    pub fn new() -> UnificationTable<K> {
-        UnificationTable { values: sv::SnapshotVec::new() }
-    }
-
-    /// Starts a new snapshot. Each snapshot must be either
-    /// rolled back or committed in a "LIFO" (stack) order.
-    pub fn snapshot(&mut self) -> Snapshot<K> {
-        Snapshot {
-            marker: marker::PhantomData::<K>,
-            snapshot: self.values.start_snapshot(),
-        }
-    }
-
-    /// Reverses all changes since the last snapshot. Also
-    /// removes any keys that have been created since then.
-    pub fn rollback_to(&mut self, snapshot: Snapshot<K>) {
-        debug!("{}: rollback_to()", UnifyKey::tag(None::<K>));
-        self.values.rollback_to(snapshot.snapshot);
-    }
-
-    /// Commits all changes since the last snapshot. Of course, they
-    /// can still be undone if there is a snapshot further out.
-    pub fn commit(&mut self, snapshot: Snapshot<K>) {
-        debug!("{}: commit()", UnifyKey::tag(None::<K>));
-        self.values.commit(snapshot.snapshot);
-    }
-
-    pub fn new_key(&mut self, value: K::Value) -> K {
-        let len = self.values.len();
-        let key: K = UnifyKey::from_index(len as u32);
-        self.values.push(VarValue::new_var(key, value));
-        debug!("{}: created new key: {:?}", UnifyKey::tag(None::<K>), key);
-        key
-    }
-
-    /// Find the root node for `vid`. This uses the standard
-    /// union-find algorithm with path compression:
-    /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
-    ///
-    /// NB. This is a building-block operation and you would probably
-    /// prefer to call `probe` below.
-    fn get(&mut self, vid: K) -> VarValue<K> {
-        let index = vid.index() as usize;
-        let mut value: VarValue<K> = self.values.get(index).clone();
-        match value.parent(vid) {
-            Some(redirect) => {
-                let root: VarValue<K> = self.get(redirect);
-                if root.key() != redirect {
-                    // Path compression
-                    value.parent = root.key();
-                    self.values.set(index, value);
-                }
-                root
-            }
-            None => value,
-        }
-    }
-
-    fn is_root(&self, key: K) -> bool {
-        let index = key.index() as usize;
-        self.values.get(index).parent(key).is_none()
-    }
-
-    /// Sets the value for `vid` to `new_value`. `vid` MUST be a root
-    /// node! This is an internal operation used to impl other things.
-    fn set(&mut self, key: K, new_value: VarValue<K>) {
-        assert!(self.is_root(key));
-
-        debug!("Updating variable {:?} to {:?}", key, new_value);
-
-        let index = key.index() as usize;
-        self.values.set(index, new_value);
-    }
-
-    /// Either redirects `node_a` to `node_b` or vice versa, depending
-    /// on the relative rank. The value associated with the new root
-    /// will be `new_value`.
-    ///
-    /// NB: This is the "union" operation of "union-find". It is
-    /// really more of a building block. If the values associated with
-    /// your key are non-trivial, you would probably prefer to call
-    /// `unify_var_var` below.
-    fn unify(&mut self, root_a: VarValue<K>, root_b: VarValue<K>, new_value: K::Value) -> K {
-        debug!("unify(root_a(id={:?}, rank={:?}), root_b(id={:?}, rank={:?}))",
-               root_a.key(),
-               root_a.rank,
-               root_b.key(),
-               root_b.rank);
-
-        if root_a.rank > root_b.rank {
-            // a has greater rank, so a should become b's parent,
-            // i.e., b should redirect to a.
-            self.redirect_root(root_a.rank, root_b, root_a, new_value)
-        } else if root_a.rank < root_b.rank {
-            // b has greater rank, so a should redirect to b.
-            self.redirect_root(root_b.rank, root_a, root_b, new_value)
-        } else {
-            // If equal, redirect one to the other and increment the
-            // other's rank.
-            self.redirect_root(root_a.rank + 1, root_a, root_b, new_value)
-        }
-    }
-
-    fn redirect_root(&mut self,
-                     new_rank: u32,
-                     old_root: VarValue<K>,
-                     new_root: VarValue<K>,
-                     new_value: K::Value)
-                     -> K {
-        let old_root_key = old_root.key();
-        let new_root_key = new_root.key();
-        self.set(old_root_key, old_root.redirect(new_root_key));
-        self.set(new_root_key, new_root.root(new_rank, new_value));
-        new_root_key
-    }
-}
-
-impl<K: UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
-    type Value = VarValue<K>;
-    type Undo = ();
-
-    fn reverse(_: &mut Vec<VarValue<K>>, _: ()) {}
-}
-
-/// # Base union-find algorithm, where we are just making sets
-
-impl<'tcx, K: UnifyKey> UnificationTable<K>
-    where K::Value: Combine
-{
-    pub fn union(&mut self, a_id: K, b_id: K) -> K {
-        let node_a = self.get(a_id);
-        let node_b = self.get(b_id);
-        let a_id = node_a.key();
-        let b_id = node_b.key();
-        if a_id != b_id {
-            let new_value = node_a.value.combine(&node_b.value);
-            self.unify(node_a, node_b, new_value)
-        } else {
-            a_id
-        }
-    }
-
-    pub fn find(&mut self, id: K) -> K {
-        self.get(id).key()
-    }
-
-    pub fn find_value(&mut self, id: K) -> K::Value {
-        self.get(id).value
-    }
-
-    #[cfg(test)]
-    fn unioned(&mut self, a_id: K, b_id: K) -> bool {
-        self.find(a_id) == self.find(b_id)
-    }
-}
-
-/// # Non-subtyping unification
-///
-/// Code to handle keys which carry a value, like ints,
-/// floats---anything that doesn't have a subtyping relationship we
-/// need to worry about.
-
-impl<'tcx, K, V> UnificationTable<K>
-    where K: UnifyKey<Value = Option<V>>,
-          V: Clone + PartialEq + Debug
-{
-    pub fn unify_var_var(&mut self, a_id: K, b_id: K) -> Result<K, (V, V)> {
-        let node_a = self.get(a_id);
-        let node_b = self.get(b_id);
-        let a_id = node_a.key();
-        let b_id = node_b.key();
-
-        if a_id == b_id {
-            return Ok(a_id);
-        }
-
-        let combined = {
-            match (&node_a.value, &node_b.value) {
-                (&None, &None) => None,
-                (&Some(ref v), &None) |
-                (&None, &Some(ref v)) => Some(v.clone()),
-                (&Some(ref v1), &Some(ref v2)) => {
-                    if *v1 != *v2 {
-                        return Err((v1.clone(), v2.clone()));
-                    }
-                    Some(v1.clone())
-                }
-            }
-        };
-
-        Ok(self.unify(node_a, node_b, combined))
-    }
-
-    /// Sets the value of the key `a_id` to `b`. Because simple keys do not have any subtyping
-    /// relationships, if `a_id` already has a value, it must be the same as `b`.
-    pub fn unify_var_value(&mut self, a_id: K, b: V) -> Result<(), (V, V)> {
-        let mut node_a = self.get(a_id);
-
-        match node_a.value {
-            None => {
-                node_a.value = Some(b);
-                self.set(node_a.key(), node_a);
-                Ok(())
-            }
-
-            Some(ref a_t) => {
-                if *a_t == b {
-                    Ok(())
-                } else {
-                    Err((a_t.clone(), b))
-                }
-            }
-        }
-    }
-
-    pub fn has_value(&mut self, id: K) -> bool {
-        self.get(id).value.is_some()
-    }
-
-    pub fn probe(&mut self, a_id: K) -> Option<V> {
-        self.get(a_id).value
-    }
-
-    pub fn unsolved_variables(&mut self) -> Vec<K> {
-        self.values
-            .iter()
-            .filter_map(|vv| {
-                if vv.value.is_some() {
-                    None
-                } else {
-                    Some(vv.key())
-                }
-            })
-            .collect()
-    }
-}
diff --git a/src/librustc_data_structures/unify/tests.rs b/src/librustc_data_structures/unify/tests.rs
deleted file mode 100644
index f29a7132e83..00000000000
--- a/src/librustc_data_structures/unify/tests.rs
+++ /dev/null
@@ -1,205 +0,0 @@
-// Copyright 2015 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.
-
-#![allow(non_snake_case)]
-
-extern crate test;
-use self::test::Bencher;
-use unify::{UnifyKey, UnificationTable};
-
-#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
-struct UnitKey(u32);
-
-impl UnifyKey for UnitKey {
-    type Value = ();
-    fn index(&self) -> u32 {
-        self.0
-    }
-    fn from_index(u: u32) -> UnitKey {
-        UnitKey(u)
-    }
-    fn tag(_: Option<UnitKey>) -> &'static str {
-        "UnitKey"
-    }
-}
-
-#[test]
-fn basic() {
-    let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
-    let k1 = ut.new_key(());
-    let k2 = ut.new_key(());
-    assert_eq!(ut.unioned(k1, k2), false);
-    ut.union(k1, k2);
-    assert_eq!(ut.unioned(k1, k2), true);
-}
-
-#[test]
-fn big_array() {
-    let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
-    let mut keys = Vec::new();
-    const MAX: usize = 1 << 15;
-
-    for _ in 0..MAX {
-        keys.push(ut.new_key(()));
-    }
-
-    for i in 1..MAX {
-        let l = keys[i - 1];
-        let r = keys[i];
-        ut.union(l, r);
-    }
-
-    for i in 0..MAX {
-        assert!(ut.unioned(keys[0], keys[i]));
-    }
-}
-
-#[bench]
-fn big_array_bench(b: &mut Bencher) {
-    let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
-    let mut keys = Vec::new();
-    const MAX: usize = 1 << 15;
-
-    for _ in 0..MAX {
-        keys.push(ut.new_key(()));
-    }
-
-
-    b.iter(|| {
-        for i in 1..MAX {
-            let l = keys[i - 1];
-            let r = keys[i];
-            ut.union(l, r);
-        }
-
-        for i in 0..MAX {
-            assert!(ut.unioned(keys[0], keys[i]));
-        }
-    })
-}
-
-#[test]
-fn even_odd() {
-    let mut ut: UnificationTable<UnitKey> = UnificationTable::new();
-    let mut keys = Vec::new();
-    const MAX: usize = 1 << 10;
-
-    for i in 0..MAX {
-        let key = ut.new_key(());
-        keys.push(key);
-
-        if i >= 2 {
-            ut.union(key, keys[i - 2]);
-        }
-    }
-
-    for i in 1..MAX {
-        assert!(!ut.unioned(keys[i - 1], keys[i]));
-    }
-
-    for i in 2..MAX {
-        assert!(ut.unioned(keys[i - 2], keys[i]));
-    }
-}
-
-#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
-struct IntKey(u32);
-
-impl UnifyKey for IntKey {
-    type Value = Option<i32>;
-    fn index(&self) -> u32 {
-        self.0
-    }
-    fn from_index(u: u32) -> IntKey {
-        IntKey(u)
-    }
-    fn tag(_: Option<IntKey>) -> &'static str {
-        "IntKey"
-    }
-}
-
-/// Test unifying a key whose value is `Some(_)`  with a key whose value is `None`.
-/// Afterwards both should be `Some(_)`.
-#[test]
-fn unify_key_Some_key_None() {
-    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
-    let k1 = ut.new_key(Some(22));
-    let k2 = ut.new_key(None);
-    assert!(ut.unify_var_var(k1, k2).is_ok());
-    assert_eq!(ut.probe(k2), Some(22));
-    assert_eq!(ut.probe(k1), Some(22));
-}
-
-/// Test unifying a key whose value is `None`  with a key whose value is `Some(_)`.
-/// Afterwards both should be `Some(_)`.
-#[test]
-fn unify_key_None_key_Some() {
-    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
-    let k1 = ut.new_key(Some(22));
-    let k2 = ut.new_key(None);
-    assert!(ut.unify_var_var(k2, k1).is_ok());
-    assert_eq!(ut.probe(k2), Some(22));
-    assert_eq!(ut.probe(k1), Some(22));
-}
-
-/// Test unifying a key whose value is `Some(x)` with a key whose value is `Some(y)`.
-/// This should yield an error.
-#[test]
-fn unify_key_Some_x_key_Some_y() {
-    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
-    let k1 = ut.new_key(Some(22));
-    let k2 = ut.new_key(Some(23));
-    assert_eq!(ut.unify_var_var(k1, k2), Err((22, 23)));
-    assert_eq!(ut.unify_var_var(k2, k1), Err((23, 22)));
-    assert_eq!(ut.probe(k1), Some(22));
-    assert_eq!(ut.probe(k2), Some(23));
-}
-
-/// Test unifying a key whose value is `Some(x)` with a key whose value is `Some(x)`.
-/// This should be ok.
-#[test]
-fn unify_key_Some_x_key_Some_x() {
-    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
-    let k1 = ut.new_key(Some(22));
-    let k2 = ut.new_key(Some(22));
-    assert!(ut.unify_var_var(k1, k2).is_ok());
-    assert_eq!(ut.probe(k1), Some(22));
-    assert_eq!(ut.probe(k2), Some(22));
-}
-
-/// Test unifying a key whose value is `None` with a value is `x`.
-/// Afterwards key should be `x`.
-#[test]
-fn unify_key_None_val() {
-    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
-    let k1 = ut.new_key(None);
-    assert!(ut.unify_var_value(k1, 22).is_ok());
-    assert_eq!(ut.probe(k1), Some(22));
-}
-
-/// Test unifying a key whose value is `Some(x)` with the value `y`.
-/// This should yield an error.
-#[test]
-fn unify_key_Some_x_val_y() {
-    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
-    let k1 = ut.new_key(Some(22));
-    assert_eq!(ut.unify_var_value(k1, 23), Err((22, 23)));
-    assert_eq!(ut.probe(k1), Some(22));
-}
-
-/// Test unifying a key whose value is `Some(x)` with the value `x`.
-/// This should be ok.
-#[test]
-fn unify_key_Some_x_val_x() {
-    let mut ut: UnificationTable<IntKey> = UnificationTable::new();
-    let k1 = ut.new_key(Some(22));
-    assert!(ut.unify_var_value(k1, 22).is_ok());
-    assert_eq!(ut.probe(k1), Some(22));
-}
diff --git a/src/librustc_data_structures/veccell/mod.rs b/src/librustc_data_structures/veccell/mod.rs
deleted file mode 100644
index 054eee8829a..00000000000
--- a/src/librustc_data_structures/veccell/mod.rs
+++ /dev/null
@@ -1,47 +0,0 @@
-// Copyright 2012-2014 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 std::cell::UnsafeCell;
-use std::mem;
-
-pub struct VecCell<T> {
-    data: UnsafeCell<Vec<T>>,
-}
-
-impl<T> VecCell<T> {
-    pub fn with_capacity(capacity: usize) -> VecCell<T> {
-        VecCell { data: UnsafeCell::new(Vec::with_capacity(capacity)) }
-    }
-
-    #[inline]
-    pub fn push(&self, data: T) -> usize {
-        // The logic here, and in `swap` below, is that the `push`
-        // method on the vector will not recursively access this
-        // `VecCell`. Therefore, we can temporarily obtain mutable
-        // access, secure in the knowledge that even if aliases exist
-        // -- indeed, even if aliases are reachable from within the
-        // vector -- they will not be used for the duration of this
-        // particular fn call. (Note that we also are relying on the
-        // fact that `VecCell` is not `Sync`.)
-        unsafe {
-            let v = self.data.get();
-            (*v).push(data);
-            (*v).len()
-        }
-    }
-
-    pub fn swap(&self, mut data: Vec<T>) -> Vec<T> {
-        unsafe {
-            let v = self.data.get();
-            mem::swap(&mut *v, &mut data);
-        }
-        data
-    }
-}
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()
+    }
+}