Auto merge of #50520 - Zoxc:alloc-misc, r=oli-obk

Misc changes related to Miri allocations

This builds on top of https://github.com/rust-lang/rust/pull/50249

r? @oli-obk

14 files changed, 322 insertions, 318 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index edd9f0fab51..8c4ff718aa6 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -420,17 +420,6 @@ impl_stable_hash_for!(struct mir::interpret::MemoryPointer {
     offset
 });
 
-enum AllocDiscriminant {
-    Alloc,
-    Static,
-    Function,
-}
-impl_stable_hash_for!(enum self::AllocDiscriminant {
-    Alloc,
-    Static,
-    Function
-});
-
 impl<'a> HashStable<StableHashingContext<'a>> for mir::interpret::AllocId {
     fn hash_stable<W: StableHasherResult>(
         &self,
@@ -440,30 +429,29 @@ impl<'a> HashStable<StableHashingContext<'a>> for mir::interpret::AllocId {
         ty::tls::with_opt(|tcx| {
             trace!("hashing {:?}", *self);
             let tcx = tcx.expect("can't hash AllocIds during hir lowering");
-            if let Some(def_id) = tcx.interpret_interner.get_static(*self) {
-                AllocDiscriminant::Static.hash_stable(hcx, hasher);
-                trace!("hashing {:?} as static {:?}", *self, def_id);
-                def_id.hash_stable(hcx, hasher);
-            } else if let Some(alloc) = tcx.interpret_interner.get_alloc(*self) {
-                AllocDiscriminant::Alloc.hash_stable(hcx, hasher);
-                if hcx.alloc_id_recursion_tracker.insert(*self) {
-                    trace!("hashing {:?} as alloc {:#?}", *self, alloc);
-                    alloc.hash_stable(hcx, hasher);
-                    assert!(hcx.alloc_id_recursion_tracker.remove(self));
-                } else {
-                    trace!("skipping hashing of {:?} due to recursion", *self);
-                }
-            } else if let Some(inst) = tcx.interpret_interner.get_fn(*self) {
-                trace!("hashing {:?} as fn {:#?}", *self, inst);
-                AllocDiscriminant::Function.hash_stable(hcx, hasher);
-                inst.hash_stable(hcx, hasher);
-            } else {
-                bug!("no allocation for {}", self);
-            }
+            let alloc_kind = tcx.alloc_map.lock().get(*self).expect("no value for AllocId");
+            alloc_kind.hash_stable(hcx, hasher);
         });
     }
 }
 
+impl<'a, 'gcx, M: HashStable<StableHashingContext<'a>>> HashStable<StableHashingContext<'a>>
+for mir::interpret::AllocType<'gcx, M> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a>,
+                                          hasher: &mut StableHasher<W>) {
+        use mir::interpret::AllocType::*;
+
+        mem::discriminant(self).hash_stable(hcx, hasher);
+
+        match *self {
+            Function(instance) => instance.hash_stable(hcx, hasher),
+            Static(def_id) => def_id.hash_stable(hcx, hasher),
+            Memory(ref mem) => mem.hash_stable(hcx, hasher),
+        }
+    }
+}
+
 impl<'a> HashStable<StableHashingContext<'a>> for mir::interpret::Allocation {
     fn hash_stable<W: StableHasherResult>(
         &self,
diff --git a/src/librustc/mir/interpret/mod.rs b/src/librustc/mir/interpret/mod.rs
index d4f18acf8ad..6f5401f54dc 100644
--- a/src/librustc/mir/interpret/mod.rs
+++ b/src/librustc/mir/interpret/mod.rs
@@ -16,13 +16,15 @@ use std::collections::BTreeMap;
 use std::fmt;
 use mir;
 use hir::def_id::DefId;
-use ty::{self, TyCtxt};
+use ty::{self, TyCtxt, Instance};
 use ty::layout::{self, Align, HasDataLayout, Size};
 use middle::region;
 use std::iter;
 use std::io;
+use std::hash::Hash;
 use syntax::ast::Mutability;
 use rustc_serialize::{Encoder, Decoder, Decodable, Encodable};
+use rustc_data_structures::fx::FxHashMap;
 use byteorder::{WriteBytesExt, ReadBytesExt, LittleEndian, BigEndian};
 
 #[derive(Clone, Debug, PartialEq, RustcEncodable, RustcDecodable)]
@@ -150,7 +152,7 @@ impl<'tcx> MemoryPointer {
 }
 
 
-#[derive(Copy, Clone, Default, Eq, Hash, Ord, PartialEq, PartialOrd, Debug)]
+#[derive(Copy, Clone, Eq, Hash, Ord, PartialEq, PartialOrd, Debug)]
 pub struct AllocId(pub u64);
 
 impl ::rustc_serialize::UseSpecializedEncodable for AllocId {}
@@ -171,20 +173,25 @@ pub fn specialized_encode_alloc_id<
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
     alloc_id: AllocId,
 ) -> Result<(), E::Error> {
-    if let Some(alloc) = tcx.interpret_interner.get_alloc(alloc_id) {
-        trace!("encoding {:?} with {:#?}", alloc_id, alloc);
-        AllocKind::Alloc.encode(encoder)?;
-        alloc.encode(encoder)?;
-    } else if let Some(fn_instance) = tcx.interpret_interner.get_fn(alloc_id) {
-        trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
-        AllocKind::Fn.encode(encoder)?;
-        fn_instance.encode(encoder)?;
-    } else if let Some(did) = tcx.interpret_interner.get_static(alloc_id) {
-        // referring to statics doesn't need to know about their allocations, just about its DefId
-        AllocKind::Static.encode(encoder)?;
-        did.encode(encoder)?;
-    } else {
-        bug!("alloc id without corresponding allocation: {}", alloc_id);
+    let alloc_type: AllocType<'tcx, &'tcx Allocation> =
+        tcx.alloc_map.lock().get(alloc_id).expect("no value for AllocId");
+    match alloc_type {
+        AllocType::Memory(alloc) => {
+            trace!("encoding {:?} with {:#?}", alloc_id, alloc);
+            AllocKind::Alloc.encode(encoder)?;
+            alloc.encode(encoder)?;
+        }
+        AllocType::Function(fn_instance) => {
+            trace!("encoding {:?} with {:#?}", alloc_id, fn_instance);
+            AllocKind::Fn.encode(encoder)?;
+            fn_instance.encode(encoder)?;
+        }
+        AllocType::Static(did) => {
+            // referring to statics doesn't need to know about their allocations,
+            // just about its DefId
+            AllocKind::Static.encode(encoder)?;
+            did.encode(encoder)?;
+        }
     }
     Ok(())
 }
@@ -200,15 +207,14 @@ pub fn specialized_decode_alloc_id<
 ) -> Result<AllocId, D::Error> {
     match AllocKind::decode(decoder)? {
         AllocKind::Alloc => {
-            let alloc_id = tcx.interpret_interner.reserve();
+            let alloc_id = tcx.alloc_map.lock().reserve();
             trace!("creating alloc id {:?}", alloc_id);
             // insert early to allow recursive allocs
             cache(decoder, alloc_id);
 
-            let allocation = Allocation::decode(decoder)?;
+            let allocation = <&'tcx Allocation as Decodable>::decode(decoder)?;
             trace!("decoded alloc {:?} {:#?}", alloc_id, allocation);
-            let allocation = tcx.intern_const_alloc(allocation);
-            tcx.interpret_interner.intern_at_reserved(alloc_id, allocation);
+            tcx.alloc_map.lock().set_id_memory(alloc_id, allocation);
 
             Ok(alloc_id)
         },
@@ -216,7 +222,7 @@ pub fn specialized_decode_alloc_id<
             trace!("creating fn alloc id");
             let instance = ty::Instance::decode(decoder)?;
             trace!("decoded fn alloc instance: {:?}", instance);
-            let id = tcx.interpret_interner.create_fn_alloc(instance);
+            let id = tcx.alloc_map.lock().create_fn_alloc(instance);
             trace!("created fn alloc id: {:?}", id);
             cache(decoder, id);
             Ok(id)
@@ -224,7 +230,7 @@ pub fn specialized_decode_alloc_id<
         AllocKind::Static => {
             trace!("creating extern static alloc id at");
             let did = DefId::decode(decoder)?;
-            let alloc_id = tcx.interpret_interner.cache_static(did);
+            let alloc_id = tcx.alloc_map.lock().intern_static(did);
             cache(decoder, alloc_id);
             Ok(alloc_id)
         },
@@ -237,6 +243,97 @@ impl fmt::Display for AllocId {
     }
 }
 
+#[derive(Debug, Clone, Eq, PartialEq, Hash, RustcDecodable, RustcEncodable)]
+pub enum AllocType<'tcx, M> {
+    /// The alloc id is used as a function pointer
+    Function(Instance<'tcx>),
+    /// The alloc id points to a static variable
+    Static(DefId),
+    /// The alloc id points to memory
+    Memory(M)
+}
+
+pub struct AllocMap<'tcx, M> {
+    /// Lets you know what an AllocId refers to
+    id_to_type: FxHashMap<AllocId, AllocType<'tcx, M>>,
+
+    /// Used to ensure that functions and statics only get one associated AllocId
+    type_interner: FxHashMap<AllocType<'tcx, M>, AllocId>,
+
+    /// The AllocId to assign to the next requested id.
+    /// Always incremented, never gets smaller.
+    next_id: AllocId,
+}
+
+impl<'tcx, M: fmt::Debug + Eq + Hash + Clone> AllocMap<'tcx, M> {
+    pub fn new() -> Self {
+        AllocMap {
+            id_to_type: FxHashMap(),
+            type_interner: FxHashMap(),
+            next_id: AllocId(0),
+        }
+    }
+
+    /// obtains a new allocation ID that can be referenced but does not
+    /// yet have an allocation backing it.
+    pub fn reserve(
+        &mut self,
+    ) -> AllocId {
+        let next = self.next_id;
+        self.next_id.0 = self.next_id.0
+            .checked_add(1)
+            .expect("You overflowed a u64 by incrementing by 1... \
+                     You've just earned yourself a free drink if we ever meet. \
+                     Seriously, how did you do that?!");
+        next
+    }
+
+    fn intern(&mut self, alloc_type: AllocType<'tcx, M>) -> AllocId {
+        if let Some(&alloc_id) = self.type_interner.get(&alloc_type) {
+            return alloc_id;
+        }
+        let id = self.reserve();
+        debug!("creating alloc_type {:?} with id {}", alloc_type, id);
+        self.id_to_type.insert(id, alloc_type.clone());
+        self.type_interner.insert(alloc_type, id);
+        id
+    }
+
+    // FIXME: Check if functions have identity. If not, we should not intern these,
+    // but instead create a new id per use.
+    // Alternatively we could just make comparing function pointers an error.
+    pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> AllocId {
+        self.intern(AllocType::Function(instance))
+    }
+
+    pub fn get(&self, id: AllocId) -> Option<AllocType<'tcx, M>> {
+        self.id_to_type.get(&id).cloned()
+    }
+
+    pub fn unwrap_memory(&self, id: AllocId) -> M {
+        match self.get(id) {
+            Some(AllocType::Memory(mem)) => mem,
+            _ => bug!("expected allocation id {} to point to memory", id),
+        }
+    }
+
+    pub fn intern_static(&mut self, static_id: DefId) -> AllocId {
+        self.intern(AllocType::Static(static_id))
+    }
+
+    pub fn allocate(&mut self, mem: M) -> AllocId {
+        let id = self.reserve();
+        self.set_id_memory(id, mem);
+        id
+    }
+
+    pub fn set_id_memory(&mut self, id: AllocId, mem: M) {
+        if let Some(old) = self.id_to_type.insert(id, AllocType::Memory(mem)) {
+            bug!("tried to set allocation id {}, but it was already existing as {:#?}", id, old);
+        }
+    }
+}
+
 #[derive(Clone, Debug, Eq, PartialEq, Hash, RustcEncodable, RustcDecodable)]
 pub struct Allocation {
     /// The actual bytes of the allocation.
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index f42f876510d..66b08f5c3b0 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -1908,17 +1908,15 @@ pub fn print_miri_value<W: Write>(value: Value, ty: Ty, f: &mut W) -> fmt::Resul
         (Value::ByValPair(PrimVal::Ptr(ptr), PrimVal::Bytes(len)),
          &TyRef(_, &ty::TyS { sty: TyStr, .. }, _)) => {
             ty::tls::with(|tcx| {
-                let alloc = tcx
-                    .interpret_interner
-                    .get_alloc(ptr.alloc_id);
-                if let Some(alloc) = alloc {
-                    assert_eq!(len as usize as u128, len);
-                    let slice = &alloc.bytes[(ptr.offset.bytes() as usize)..][..(len as usize)];
-                    let s = ::std::str::from_utf8(slice)
-                        .expect("non utf8 str from miri");
-                    write!(f, "{:?}", s)
-                } else {
-                    write!(f, "pointer to erroneous constant {:?}, {:?}", ptr, len)
+                match tcx.alloc_map.lock().get(ptr.alloc_id) {
+                    Some(interpret::AllocType::Memory(alloc)) => {
+                        assert_eq!(len as usize as u128, len);
+                        let slice = &alloc.bytes[(ptr.offset.bytes() as usize)..][..(len as usize)];
+                        let s = ::std::str::from_utf8(slice)
+                            .expect("non utf8 str from miri");
+                        write!(f, "{:?}", s)
+                    }
+                    _ => write!(f, "pointer to erroneous constant {:?}, {:?}", ptr, len),
                 }
             })
         },
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index a3d380c3e14..82d796253bd 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -32,9 +32,9 @@ use middle::lang_items;
 use middle::resolve_lifetime::{self, ObjectLifetimeDefault};
 use middle::stability;
 use mir::{self, Mir, interpret};
+use mir::interpret::Allocation;
 use ty::subst::{Kind, Substs, Subst};
 use ty::ReprOptions;
-use ty::Instance;
 use traits;
 use traits::{Clause, Clauses, Goal, Goals};
 use ty::{self, Ty, TypeAndMut};
@@ -914,7 +914,10 @@ pub struct GlobalCtxt<'tcx> {
 
     stability_interner: Lock<FxHashSet<&'tcx attr::Stability>>,
 
-    pub interpret_interner: InterpretInterner<'tcx>,
+    /// Stores the value of constants (and deduplicates the actual memory)
+    allocation_interner: Lock<FxHashSet<&'tcx Allocation>>,
+
+    pub alloc_map: Lock<interpret::AllocMap<'tcx, &'tcx Allocation>>,
 
     layout_interner: Lock<FxHashSet<&'tcx LayoutDetails>>,
 
@@ -929,117 +932,6 @@ pub struct GlobalCtxt<'tcx> {
     output_filenames: Arc<OutputFilenames>,
 }
 
-/// Everything needed to efficiently work with interned allocations
-#[derive(Debug, Default)]
-pub struct InterpretInterner<'tcx> {
-    inner: Lock<InterpretInternerInner<'tcx>>,
-}
-
-#[derive(Debug, Default)]
-struct InterpretInternerInner<'tcx> {
-    /// Stores the value of constants (and deduplicates the actual memory)
-    allocs: FxHashSet<&'tcx interpret::Allocation>,
-
-    /// Allows obtaining function instance handles via a unique identifier
-    functions: FxHashMap<interpret::AllocId, Instance<'tcx>>,
-
-    /// Inverse map of `interpret_functions`.
-    /// Used so we don't allocate a new pointer every time we need one
-    function_cache: FxHashMap<Instance<'tcx>, interpret::AllocId>,
-
-    /// Allows obtaining const allocs via a unique identifier
-    alloc_by_id: FxHashMap<interpret::AllocId, &'tcx interpret::Allocation>,
-
-    /// Allows obtaining static def ids via a unique id
-    statics: FxHashMap<interpret::AllocId, DefId>,
-
-    /// The AllocId to assign to the next new regular allocation.
-    /// Always incremented, never gets smaller.
-    next_id: interpret::AllocId,
-
-    /// Inverse map of `statics`
-    /// Used so we don't allocate a new pointer every time we need one
-    static_cache: FxHashMap<DefId, interpret::AllocId>,
-
-    /// A cache for basic byte allocations keyed by their contents. This is used to deduplicate
-    /// allocations for string and bytestring literals.
-    literal_alloc_cache: FxHashMap<Vec<u8>, interpret::AllocId>,
-}
-
-impl<'tcx> InterpretInterner<'tcx> {
-    pub fn create_fn_alloc(&self, instance: Instance<'tcx>) -> interpret::AllocId {
-        if let Some(&alloc_id) = self.inner.borrow().function_cache.get(&instance) {
-            return alloc_id;
-        }
-        let id = self.reserve();
-        debug!("creating fn ptr: {}", id);
-        let mut inner = self.inner.borrow_mut();
-        inner.functions.insert(id, instance);
-        inner.function_cache.insert(instance, id);
-        id
-    }
-
-    pub fn get_fn(
-        &self,
-        id: interpret::AllocId,
-    ) -> Option<Instance<'tcx>> {
-        self.inner.borrow().functions.get(&id).cloned()
-    }
-
-    pub fn get_alloc(
-        &self,
-        id: interpret::AllocId,
-    ) -> Option<&'tcx interpret::Allocation> {
-        self.inner.borrow().alloc_by_id.get(&id).cloned()
-    }
-
-    pub fn cache_static(
-        &self,
-        static_id: DefId,
-    ) -> interpret::AllocId {
-        if let Some(alloc_id) = self.inner.borrow().static_cache.get(&static_id).cloned() {
-            return alloc_id;
-        }
-        let alloc_id = self.reserve();
-        let mut inner = self.inner.borrow_mut();
-        inner.static_cache.insert(static_id, alloc_id);
-        inner.statics.insert(alloc_id, static_id);
-        alloc_id
-    }
-
-    pub fn get_static(
-        &self,
-        ptr: interpret::AllocId,
-    ) -> Option<DefId> {
-        self.inner.borrow().statics.get(&ptr).cloned()
-    }
-
-    pub fn intern_at_reserved(
-        &self,
-        id: interpret::AllocId,
-        alloc: &'tcx interpret::Allocation,
-    ) {
-        if let Some(old) = self.inner.borrow_mut().alloc_by_id.insert(id, alloc) {
-            bug!("tried to intern allocation at {}, but was already existing as {:#?}", id, old);
-        }
-    }
-
-    /// obtains a new allocation ID that can be referenced but does not
-    /// yet have an allocation backing it.
-    pub fn reserve(
-        &self,
-    ) -> interpret::AllocId {
-        let mut inner = self.inner.borrow_mut();
-        let next = inner.next_id;
-        inner.next_id.0 = inner.next_id.0
-            .checked_add(1)
-            .expect("You overflowed a u64 by incrementing by 1... \
-                     You've just earned yourself a free drink if we ever meet. \
-                     Seriously, how did you do that?!");
-        next
-    }
-}
-
 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     /// Get the global TyCtxt.
     #[inline]
@@ -1108,9 +1000,9 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 
     pub fn intern_const_alloc(
         self,
-        alloc: interpret::Allocation,
-    ) -> &'gcx interpret::Allocation {
-        let allocs = &mut self.interpret_interner.inner.borrow_mut().allocs;
+        alloc: Allocation,
+    ) -> &'gcx Allocation {
+        let allocs = &mut self.allocation_interner.borrow_mut();
         if let Some(alloc) = allocs.get(&alloc) {
             return alloc;
         }
@@ -1123,23 +1015,11 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     }
 
     /// Allocates a byte or string literal for `mir::interpret`
-    pub fn allocate_cached(self, bytes: &[u8]) -> interpret::AllocId {
-        // check whether we already allocated this literal or a constant with the same memory
-        if let Some(&alloc_id) = self.interpret_interner.inner.borrow()
-                                     .literal_alloc_cache.get(bytes) {
-            return alloc_id;
-        }
+    pub fn allocate_bytes(self, bytes: &[u8]) -> interpret::AllocId {
         // create an allocation that just contains these bytes
         let alloc = interpret::Allocation::from_byte_aligned_bytes(bytes);
         let alloc = self.intern_const_alloc(alloc);
-
-        // the next unique id
-        let id = self.interpret_interner.reserve();
-        // make the allocation identifiable
-        self.interpret_interner.inner.borrow_mut().alloc_by_id.insert(id, alloc);
-        // cache it for the future
-        self.interpret_interner.inner.borrow_mut().literal_alloc_cache.insert(bytes.to_owned(), id);
-        id
+        self.alloc_map.lock().allocate(alloc)
     }
 
     pub fn intern_stability(self, stab: attr::Stability) -> &'gcx attr::Stability {
@@ -1289,7 +1169,8 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             data_layout,
             layout_interner: Lock::new(FxHashSet()),
             stability_interner: Lock::new(FxHashSet()),
-            interpret_interner: Default::default(),
+            allocation_interner: Lock::new(FxHashSet()),
+            alloc_map: Lock::new(interpret::AllocMap::new()),
             tx_to_llvm_workers: Lock::new(tx),
             output_filenames: Arc::new(output_filenames.clone()),
         };
@@ -2019,7 +1900,7 @@ impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
         println!("Substs interner: #{}", self.interners.substs.borrow().len());
         println!("Region interner: #{}", self.interners.region.borrow().len());
         println!("Stability interner: #{}", self.stability_interner.borrow().len());
-        println!("Interpret interner: #{}", self.interpret_interner.inner.borrow().allocs.len());
+        println!("Allocation interner: #{}", self.allocation_interner.borrow().len());
         println!("Layout interner: #{}", self.layout_interner.borrow().len());
     }
 }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 1726ed27d14..b975f9e5195 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -78,7 +78,7 @@ pub use self::binding::BindingMode;
 pub use self::binding::BindingMode::*;
 
 pub use self::context::{TyCtxt, GlobalArenas, AllArenas, tls, keep_local};
-pub use self::context::{Lift, TypeckTables, InterpretInterner};
+pub use self::context::{Lift, TypeckTables};
 
 pub use self::instance::{Instance, InstanceDef};
 
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 6bc0cb51a92..d9797bf4985 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -1861,6 +1861,14 @@ impl<'tcx> Const<'tcx> {
     }
 
     #[inline]
+    pub fn to_byval_value(&self) -> Option<Value> {
+        match self.val {
+            ConstVal::Value(val) => val.to_byval_value(),
+            _ => None,
+        }
+    }
+
+    #[inline]
     pub fn to_primval(&self) -> Option<PrimVal> {
         match self.val {
             ConstVal::Value(val) => val.to_primval(),
diff --git a/src/librustc_codegen_llvm/mir/constant.rs b/src/librustc_codegen_llvm/mir/constant.rs
index 36c1d335ec4..07fb683a84f 100644
--- a/src/librustc_codegen_llvm/mir/constant.rs
+++ b/src/librustc_codegen_llvm/mir/constant.rs
@@ -14,7 +14,7 @@ use rustc_mir::interpret::{read_target_uint, const_val_field};
 use rustc::hir::def_id::DefId;
 use rustc::mir;
 use rustc_data_structures::indexed_vec::Idx;
-use rustc::mir::interpret::{GlobalId, MemoryPointer, PrimVal, Allocation, ConstValue};
+use rustc::mir::interpret::{GlobalId, MemoryPointer, PrimVal, Allocation, ConstValue, AllocType};
 use rustc::ty::{self, Ty};
 use rustc::ty::layout::{self, HasDataLayout, LayoutOf, Scalar, Size};
 use builder::Builder;
@@ -44,38 +44,34 @@ pub fn primval_to_llvm(cx: &CodegenCx,
             }
         },
         PrimVal::Ptr(ptr) => {
-            if let Some(fn_instance) = cx.tcx.interpret_interner.get_fn(ptr.alloc_id) {
-                callee::get_fn(cx, fn_instance)
-            } else {
-                let static_ = cx
-                    .tcx
-                    .interpret_interner
-                    .get_static(ptr.alloc_id);
-                let base_addr = if let Some(def_id) = static_ {
-                    assert!(cx.tcx.is_static(def_id).is_some());
-                    consts::get_static(cx, def_id)
-                } else if let Some(alloc) = cx.tcx.interpret_interner
-                                              .get_alloc(ptr.alloc_id) {
+            let alloc_type = cx.tcx.alloc_map.lock().get(ptr.alloc_id);
+            let base_addr = match alloc_type {
+                Some(AllocType::Memory(alloc)) => {
                     let init = const_alloc_to_llvm(cx, alloc);
                     if alloc.runtime_mutability == Mutability::Mutable {
                         consts::addr_of_mut(cx, init, alloc.align, "byte_str")
                     } else {
                         consts::addr_of(cx, init, alloc.align, "byte_str")
                     }
-                } else {
-                    bug!("missing allocation {:?}", ptr.alloc_id);
-                };
-
-                let llval = unsafe { llvm::LLVMConstInBoundsGEP(
-                    consts::bitcast(base_addr, Type::i8p(cx)),
-                    &C_usize(cx, ptr.offset.bytes()),
-                    1,
-                ) };
-                if scalar.value != layout::Pointer {
-                    unsafe { llvm::LLVMConstPtrToInt(llval, llty.to_ref()) }
-                } else {
-                    consts::bitcast(llval, llty)
                 }
+                Some(AllocType::Function(fn_instance)) => {
+                    callee::get_fn(cx, fn_instance)
+                }
+                Some(AllocType::Static(def_id)) => {
+                    assert!(cx.tcx.is_static(def_id).is_some());
+                    consts::get_static(cx, def_id)
+                }
+                None => bug!("missing allocation {:?}", ptr.alloc_id),
+            };
+            let llval = unsafe { llvm::LLVMConstInBoundsGEP(
+                consts::bitcast(base_addr, Type::i8p(cx)),
+                &C_usize(cx, ptr.offset.bytes()),
+                1,
+            ) };
+            if scalar.value != layout::Pointer {
+                unsafe { llvm::LLVMConstPtrToInt(llval, llty.to_ref()) }
+            } else {
+                consts::bitcast(llval, llty)
             }
         }
     }
diff --git a/src/librustc_mir/hair/cx/mod.rs b/src/librustc_mir/hair/cx/mod.rs
index 71dd35c010d..390b82af48a 100644
--- a/src/librustc_mir/hair/cx/mod.rs
+++ b/src/librustc_mir/hair/cx/mod.rs
@@ -181,7 +181,7 @@ impl<'a, 'gcx, 'tcx> Cx<'a, 'gcx, 'tcx> {
         let lit = match *lit {
             LitKind::Str(ref s, _) => {
                 let s = s.as_str();
-                let id = self.tcx.allocate_cached(s.as_bytes());
+                let id = self.tcx.allocate_bytes(s.as_bytes());
                 let ptr = MemoryPointer::new(id, Size::from_bytes(0));
                 ConstValue::ByValPair(
                     PrimVal::Ptr(ptr),
@@ -189,7 +189,7 @@ impl<'a, 'gcx, 'tcx> Cx<'a, 'gcx, 'tcx> {
                 )
             },
             LitKind::ByteStr(ref data) => {
-                let id = self.tcx.allocate_cached(data);
+                let id = self.tcx.allocate_bytes(data);
                 let ptr = MemoryPointer::new(id, Size::from_bytes(0));
                 ConstValue::ByVal(PrimVal::Ptr(ptr))
             },
diff --git a/src/librustc_mir/hair/pattern/_match.rs b/src/librustc_mir/hair/pattern/_match.rs
index 0c2645b4c5c..70e8cd336a3 100644
--- a/src/librustc_mir/hair/pattern/_match.rs
+++ b/src/librustc_mir/hair/pattern/_match.rs
@@ -187,10 +187,7 @@ impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> {
                             .and_then(|t| t.ty.builtin_index())
                             .map_or(false, |t| t == tcx.types.u8);
                         assert!(is_array_ptr);
-                        let alloc = tcx
-                            .interpret_interner
-                            .get_alloc(ptr.alloc_id)
-                            .unwrap();
+                        let alloc = tcx.alloc_map.lock().unwrap_memory(ptr.alloc_id);
                         assert_eq!(ptr.offset.bytes(), 0);
                         // FIXME: check length
                         alloc.bytes.iter().map(|b| {
@@ -558,10 +555,7 @@ fn max_slice_length<'p, 'a: 'p, 'tcx: 'a, I>(
                         .and_then(|t| t.ty.builtin_index())
                         .map_or(false, |t| t == cx.tcx.types.u8);
                     if is_array_ptr {
-                        let alloc = cx.tcx
-                            .interpret_interner
-                            .get_alloc(ptr.alloc_id)
-                            .unwrap();
+                        let alloc = cx.tcx.alloc_map.lock().unwrap_memory(ptr.alloc_id);
                         max_fixed_len = cmp::max(max_fixed_len, alloc.bytes.len() as u64);
                     }
                 }
@@ -945,12 +939,7 @@ fn slice_pat_covered_by_constructor<'tcx>(
                     .and_then(|t| t.ty.builtin_index())
                     .map_or(false, |t| t == tcx.types.u8);
                 assert!(is_array_ptr);
-                tcx
-                    .interpret_interner
-                    .get_alloc(ptr.alloc_id)
-                    .unwrap()
-                    .bytes
-                    .as_ref()
+                tcx.alloc_map.lock().unwrap_memory(ptr.alloc_id).bytes.as_ref()
             } else {
                 bug!()
             }
@@ -1088,9 +1077,9 @@ fn specialize<'p, 'a: 'p, 'tcx: 'a>(
                             .map_or(false, |t| t == cx.tcx.types.u8);
                         assert!(is_array_ptr);
                         let data_len = cx.tcx
-                            .interpret_interner
-                            .get_alloc(ptr.alloc_id)
-                            .unwrap()
+                            .alloc_map
+                            .lock()
+                            .unwrap_memory(ptr.alloc_id)
                             .bytes
                             .len();
                         if wild_patterns.len() == data_len {
diff --git a/src/librustc_mir/hair/pattern/mod.rs b/src/librustc_mir/hair/pattern/mod.rs
index 0368e6595c1..95ff5c24ecc 100644
--- a/src/librustc_mir/hair/pattern/mod.rs
+++ b/src/librustc_mir/hair/pattern/mod.rs
@@ -20,7 +20,7 @@ use interpret::{const_val_field, const_variant_index, self};
 
 use rustc::middle::const_val::ConstVal;
 use rustc::mir::{fmt_const_val, Field, BorrowKind, Mutability};
-use rustc::mir::interpret::{PrimVal, GlobalId, ConstValue};
+use rustc::mir::interpret::{PrimVal, GlobalId, ConstValue, Value};
 use rustc::ty::{self, TyCtxt, AdtDef, Ty, Region};
 use rustc::ty::layout::Size;
 use rustc::ty::subst::{Substs, Kind};
@@ -1040,11 +1040,27 @@ pub fn compare_const_vals<'a, 'tcx>(
     ty: Ty<'tcx>,
 ) -> Option<Ordering> {
     trace!("compare_const_vals: {:?}, {:?}", a, b);
+
+    let from_bool = |v: bool| {
+        if v {
+            Some(Ordering::Equal)
+        } else {
+            None
+        }
+    };
+
+    let fallback = || from_bool(a == b);
+
+    // Use the fallback if any type differs
+    if a.ty != b.ty || a.ty != ty {
+        return fallback();
+    }
+
     // FIXME: This should use assert_bits(ty) instead of use_bits
     // but triggers possibly bugs due to mismatching of arrays and slices
     if let (Some(a), Some(b)) = (a.to_bits(ty), b.to_bits(ty)) {
         use ::rustc_apfloat::Float;
-        match ty.sty {
+        return match ty.sty {
             ty::TyFloat(ast::FloatTy::F32) => {
                 let l = ::rustc_apfloat::ieee::Single::from_bits(a);
                 let r = ::rustc_apfloat::ieee::Single::from_bits(b);
@@ -1062,13 +1078,36 @@ pub fn compare_const_vals<'a, 'tcx>(
             },
             _ => Some(a.cmp(&b)),
         }
-    } else {
-        if a == b {
-            Some(Ordering::Equal)
-        } else {
-            None
+    }
+
+    if let ty::TyRef(_, rty, _) = ty.sty {
+        if let ty::TyStr = rty.sty {
+            match (a.to_byval_value(), b.to_byval_value()) {
+                (
+                    Some(Value::ByValPair(
+                        PrimVal::Ptr(ptr_a),
+                        PrimVal::Bytes(size_a))
+                    ),
+                    Some(Value::ByValPair(
+                        PrimVal::Ptr(ptr_b),
+                        PrimVal::Bytes(size_b))
+                    )
+                ) if size_a == size_b => {
+                    if ptr_a.offset == Size::from_bytes(0) && ptr_b.offset == Size::from_bytes(0) {
+                        let map = tcx.alloc_map.lock();
+                        let alloc_a = map.unwrap_memory(ptr_a.alloc_id);
+                        let alloc_b = map.unwrap_memory(ptr_b.alloc_id);
+                        if alloc_a.bytes.len() as u64 == size_a as u64 {
+                            return from_bool(alloc_a == alloc_b);
+                        }
+                    }
+                }
+                _ => (),
+            }
         }
     }
+
+    fallback()
 }
 
 // FIXME: Combine with rustc_mir::hair::cx::const_eval_literal
@@ -1083,7 +1122,7 @@ fn lit_to_const<'a, 'tcx>(lit: &'tcx ast::LitKind,
     let lit = match *lit {
         LitKind::Str(ref s, _) => {
             let s = s.as_str();
-            let id = tcx.allocate_cached(s.as_bytes());
+            let id = tcx.allocate_bytes(s.as_bytes());
             let ptr = MemoryPointer::new(id, Size::from_bytes(0));
             ConstValue::ByValPair(
                 PrimVal::Ptr(ptr),
@@ -1091,7 +1130,7 @@ fn lit_to_const<'a, 'tcx>(lit: &'tcx ast::LitKind,
             )
         },
         LitKind::ByteStr(ref data) => {
-            let id = tcx.allocate_cached(data);
+            let id = tcx.allocate_bytes(data);
             let ptr = MemoryPointer::new(id, Size::from_bytes(0));
             ConstValue::ByVal(PrimVal::Ptr(ptr))
         },
diff --git a/src/librustc_mir/interpret/const_eval.rs b/src/librustc_mir/interpret/const_eval.rs
index c5143817030..1b4cde2f6ca 100644
--- a/src/librustc_mir/interpret/const_eval.rs
+++ b/src/librustc_mir/interpret/const_eval.rs
@@ -377,8 +377,9 @@ impl<'mir, 'tcx> super::Machine<'mir, 'tcx> for CompileTimeEvaluator {
     ) -> EvalResult<'tcx, AllocId> {
         Ok(ecx
             .tcx
-            .interpret_interner
-            .cache_static(cid.instance.def_id()))
+            .alloc_map
+            .lock()
+            .intern_static(cid.instance.def_id()))
     }
 
     fn box_alloc<'a>(
diff --git a/src/librustc_mir/interpret/eval_context.rs b/src/librustc_mir/interpret/eval_context.rs
index 97ea90bb4bf..15103b78ca8 100644
--- a/src/librustc_mir/interpret/eval_context.rs
+++ b/src/librustc_mir/interpret/eval_context.rs
@@ -229,7 +229,7 @@ impl<'a, 'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> EvalContext<'a, 'mir, 'tcx, M
     }
 
     pub fn str_to_value(&mut self, s: &str) -> EvalResult<'tcx, Value> {
-        let ptr = self.memory.allocate_cached(s.as_bytes());
+        let ptr = self.memory.allocate_bytes(s.as_bytes());
         Ok(Value::ByValPair(
             PrimVal::Ptr(ptr),
             PrimVal::from_u128(s.len() as u128),
@@ -1015,8 +1015,9 @@ impl<'a, 'mir, 'tcx: 'mir, M: Machine<'mir, 'tcx>> EvalContext<'a, 'mir, 'tcx, M
         if self.tcx.is_static(gid.instance.def_id()).is_some() {
             let alloc_id = self
                 .tcx
-                .interpret_interner
-                .cache_static(gid.instance.def_id());
+                .alloc_map
+                .lock()
+                .intern_static(gid.instance.def_id());
             let layout = self.layout_of(ty)?;
             let ptr = MemoryPointer::new(alloc_id, Size::from_bytes(0));
             return Ok(Value::ByRef(ptr.into(), layout.align))
diff --git a/src/librustc_mir/interpret/memory.rs b/src/librustc_mir/interpret/memory.rs
index 755eaa443b6..b2a6e2b4527 100644
--- a/src/librustc_mir/interpret/memory.rs
+++ b/src/librustc_mir/interpret/memory.rs
@@ -11,7 +11,7 @@ use rustc::middle::const_val::{ConstVal, ErrKind};
 
 use rustc_data_structures::fx::{FxHashSet, FxHashMap};
 use rustc::mir::interpret::{MemoryPointer, AllocId, Allocation, AccessKind, Value, Pointer,
-                            EvalResult, PrimVal, EvalErrorKind, GlobalId};
+                            EvalResult, PrimVal, EvalErrorKind, GlobalId, AllocType};
 pub use rustc::mir::interpret::{write_target_uint, write_target_int, read_target_uint};
 
 use super::{EvalContext, Machine};
@@ -72,12 +72,12 @@ impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
     }
 
     pub fn create_fn_alloc(&mut self, instance: Instance<'tcx>) -> MemoryPointer {
-        let id = self.tcx.interpret_interner.create_fn_alloc(instance);
+        let id = self.tcx.alloc_map.lock().create_fn_alloc(instance);
         MemoryPointer::new(id, Size::from_bytes(0))
     }
 
-    pub fn allocate_cached(&mut self, bytes: &[u8]) -> MemoryPointer {
-        let id = self.tcx.allocate_cached(bytes);
+    pub fn allocate_bytes(&mut self, bytes: &[u8]) -> MemoryPointer {
+        let id = self.tcx.allocate_bytes(bytes);
         MemoryPointer::new(id, Size::from_bytes(0))
     }
 
@@ -87,7 +87,7 @@ impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
         alloc: Allocation,
         kind: Option<MemoryKind<M::MemoryKinds>>,
     ) -> EvalResult<'tcx, AllocId> {
-        let id = self.tcx.interpret_interner.reserve();
+        let id = self.tcx.alloc_map.lock().reserve();
         M::add_lock(self, id);
         match kind {
             Some(kind @ MemoryKind::Stack) |
@@ -177,19 +177,20 @@ impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
                     "uninitializedstatic".to_string(),
                     format!("{:?}", kind),
                 ))
-            } else if self.tcx.interpret_interner.get_fn(ptr.alloc_id).is_some() {
-                return err!(DeallocatedWrongMemoryKind(
-                    "function".to_string(),
-                    format!("{:?}", kind),
-                ))
-            } else if self.tcx.interpret_interner.get_alloc(ptr.alloc_id).is_some() {
-                return err!(DeallocatedWrongMemoryKind(
-                    "static".to_string(),
-                    format!("{:?}", kind),
-                ))
             } else {
-                return err!(DoubleFree)
-            },
+                return match self.tcx.alloc_map.lock().get(ptr.alloc_id) {
+                    Some(AllocType::Function(..)) => err!(DeallocatedWrongMemoryKind(
+                        "function".to_string(),
+                        format!("{:?}", kind),
+                    )),
+                    Some(AllocType::Static(..)) |
+                    Some(AllocType::Memory(..)) => err!(DeallocatedWrongMemoryKind(
+                        "static".to_string(),
+                        format!("{:?}", kind),
+                    )),
+                    None => err!(DoubleFree)
+                }
+            }
         };
 
         let alloc_kind = self.alloc_kind.remove(&ptr.alloc_id).expect("alloc_map out of sync with alloc_kind");
@@ -312,19 +313,16 @@ impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
                 Some(alloc) => Ok(alloc),
                 None => {
                     // static alloc?
-                    if let Some(a) = self.tcx.interpret_interner.get_alloc(id) {
-                        return Ok(a);
+                    match self.tcx.alloc_map.lock().get(id) {
+                        Some(AllocType::Memory(mem)) => Ok(mem),
+                        Some(AllocType::Function(..)) => {
+                            Err(EvalErrorKind::DerefFunctionPointer.into())
+                        }
+                        Some(AllocType::Static(did)) => {
+                            self.const_eval_static(did)
+                        }
+                        None => Err(EvalErrorKind::DanglingPointerDeref.into()),
                     }
-                    // static variable?
-                    if let Some(did) = self.tcx.interpret_interner.get_static(id) {
-                        return self.const_eval_static(did);
-                    }
-                    // otherwise return an error
-                    Err(if self.tcx.interpret_interner.get_fn(id).is_some() {
-                        EvalErrorKind::DerefFunctionPointer.into()
-                    } else {
-                        EvalErrorKind::DanglingPointerDeref.into()
-                    })
                 },
             },
         }
@@ -342,12 +340,11 @@ impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
                 Some(alloc) => Ok(alloc),
                 None => {
                     // no alloc or immutable alloc? produce an error
-                    if self.tcx.interpret_interner.get_alloc(id).is_some() {
-                        err!(ModifiedConstantMemory)
-                    } else if self.tcx.interpret_interner.get_fn(id).is_some() {
-                        err!(DerefFunctionPointer)
-                    } else {
-                        err!(DanglingPointerDeref)
+                    match self.tcx.alloc_map.lock().get(id) {
+                        Some(AllocType::Memory(..)) |
+                        Some(AllocType::Static(..)) => err!(ModifiedConstantMemory),
+                        Some(AllocType::Function(..)) => err!(DerefFunctionPointer),
+                        None => err!(DanglingPointerDeref),
                     }
                 },
             },
@@ -359,10 +356,10 @@ impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
             return err!(InvalidFunctionPointer);
         }
         debug!("reading fn ptr: {}", ptr.alloc_id);
-        self.tcx
-            .interpret_interner
-            .get_fn(ptr.alloc_id)
-            .ok_or(EvalErrorKind::ExecuteMemory.into())
+        match self.tcx.alloc_map.lock().get(ptr.alloc_id) {
+            Some(AllocType::Function(instance)) => Ok(instance),
+            _ => Err(EvalErrorKind::ExecuteMemory.into()),
+        }
     }
 
     pub fn get_alloc_kind(&self, id: AllocId) -> Option<MemoryKind<M::MemoryKinds>> {
@@ -405,15 +402,20 @@ impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
                         Some(a) => (a, " (static in the process of initialization)".to_owned()),
                         None => {
                             // static alloc?
-                            match self.tcx.interpret_interner.get_alloc(id) {
-                                Some(a) => (a, "(immutable)".to_owned()),
-                                None => if let Some(func) = self.tcx.interpret_interner.get_fn(id) {
+                            match self.tcx.alloc_map.lock().get(id) {
+                                Some(AllocType::Memory(a)) => (a, "(immutable)".to_owned()),
+                                Some(AllocType::Function(func)) => {
                                     trace!("{} {}", msg, func);
                                     continue;
-                                } else {
+                                }
+                                Some(AllocType::Static(did)) => {
+                                    trace!("{} {:?}", msg, did);
+                                    continue;
+                                }
+                                None => {
                                     trace!("{} (deallocated)", msg);
                                     continue;
-                                },
+                                }
                             }
                         },
                     },
@@ -579,7 +581,7 @@ impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
             // ensure llvm knows not to put this into immutable memroy
             alloc.runtime_mutability = mutability;
             let alloc = self.tcx.intern_const_alloc(alloc);
-            self.tcx.interpret_interner.intern_at_reserved(alloc_id, alloc);
+            self.tcx.alloc_map.lock().set_id_memory(alloc_id, alloc);
             // recurse into inner allocations
             for &alloc in alloc.relocations.values() {
                 self.mark_inner_allocation_initialized(alloc, mutability)?;
diff --git a/src/librustc_mir/monomorphize/collector.rs b/src/librustc_mir/monomorphize/collector.rs
index 148b12cdc31..b181a281ef4 100644
--- a/src/librustc_mir/monomorphize/collector.rs
+++ b/src/librustc_mir/monomorphize/collector.rs
@@ -203,7 +203,7 @@ use rustc::session::config;
 use rustc::mir::{self, Location, Promoted};
 use rustc::mir::visit::Visitor as MirVisitor;
 use rustc::mir::mono::MonoItem;
-use rustc::mir::interpret::{PrimVal, GlobalId};
+use rustc::mir::interpret::{PrimVal, GlobalId, AllocType};
 
 use monomorphize::{self, Instance};
 use rustc::util::nodemap::{FxHashSet, FxHashMap, DefIdMap};
@@ -1146,24 +1146,28 @@ fn collect_miri<'a, 'tcx>(
     alloc_id: AllocId,
     output: &mut Vec<MonoItem<'tcx>>,
 ) {
-    if let Some(did) = tcx.interpret_interner.get_static(alloc_id) {
-        let instance = Instance::mono(tcx, did);
-        if should_monomorphize_locally(tcx, &instance) {
-            trace!("collecting static {:?}", did);
-            output.push(MonoItem::Static(did));
-        }
-    } else if let Some(alloc) = tcx.interpret_interner.get_alloc(alloc_id) {
-        trace!("collecting {:?} with {:#?}", alloc_id, alloc);
-        for &inner in alloc.relocations.values() {
-            collect_miri(tcx, inner, output);
+    let alloc_type = tcx.alloc_map.lock().get(alloc_id);
+    match alloc_type {
+        Some(AllocType::Static(did)) => {
+            let instance = Instance::mono(tcx, did);
+            if should_monomorphize_locally(tcx, &instance) {
+                trace!("collecting static {:?}", did);
+                output.push(MonoItem::Static(did));
+            }
         }
-    } else if let Some(fn_instance) = tcx.interpret_interner.get_fn(alloc_id) {
-        if should_monomorphize_locally(tcx, &fn_instance) {
-            trace!("collecting {:?} with {:#?}", alloc_id, fn_instance);
-            output.push(create_fn_mono_item(fn_instance));
+        Some(AllocType::Memory(alloc)) => {
+            trace!("collecting {:?} with {:#?}", alloc_id, alloc);
+            for &inner in alloc.relocations.values() {
+                collect_miri(tcx, inner, output);
+            }
+        },
+        Some(AllocType::Function(fn_instance)) => {
+            if should_monomorphize_locally(tcx, &fn_instance) {
+                trace!("collecting {:?} with {:#?}", alloc_id, fn_instance);
+                output.push(create_fn_mono_item(fn_instance));
+            }
         }
-    } else {
-        bug!("alloc id without corresponding allocation: {}", alloc_id);
+        None => bug!("alloc id without corresponding allocation: {}", alloc_id),
     }
 }