move Instance to rustc and use it in the collector

24 files changed, 522 insertions, 432 deletions

diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 254cae61152..399af258e92 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -89,6 +89,7 @@ pub enum DepNode<D: Clone + Debug> {
     // things read/modify that MIR.
     MirKrate,
     Mir(D),
+    MirShim(Vec<D>),
 
     BorrowCheckKrate,
     BorrowCheck(D),
@@ -258,6 +259,10 @@ impl<D: Clone + Debug> DepNode<D> {
             IntrinsicCheck(ref d) => op(d).map(IntrinsicCheck),
             MatchCheck(ref d) => op(d).map(MatchCheck),
             Mir(ref d) => op(d).map(Mir),
+            MirShim(ref def_ids) => {
+                let def_ids: Option<Vec<E>> = def_ids.iter().map(op).collect();
+                def_ids.map(MirShim)
+            }
             BorrowCheck(ref d) => op(d).map(BorrowCheck),
             RvalueCheck(ref d) => op(d).map(RvalueCheck),
             StabilityCheck(ref d) => op(d).map(StabilityCheck),
diff --git a/src/librustc/ty/instance.rs b/src/librustc/ty/instance.rs
new file mode 100644
index 00000000000..fdcfb3ebd3c
--- /dev/null
+++ b/src/librustc/ty/instance.rs
@@ -0,0 +1,105 @@
+// 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 dep_graph::DepNode;
+use hir::def_id::DefId;
+use ty::{self, Ty, TypeFoldable, Substs};
+use util::ppaux;
+
+use std::borrow::Cow;
+use std::fmt;
+use syntax::ast;
+
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
+pub struct Instance<'tcx> {
+    pub def: InstanceDef<'tcx>,
+    pub substs: &'tcx Substs<'tcx>,
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
+pub enum InstanceDef<'tcx> {
+    Item(DefId),
+    // <fn() as FnTrait>::call_*
+    FnPtrShim(DefId, Ty<'tcx>),
+}
+
+impl<'tcx> InstanceDef<'tcx> {
+    #[inline]
+    pub fn def_id(&self) -> DefId {
+        match *self {
+            InstanceDef::Item(def_id) |
+            InstanceDef::FnPtrShim(def_id, _)
+                => def_id
+        }
+    }
+
+    #[inline]
+    pub fn def_ty<'a>(&self, tcx: ty::TyCtxt<'a, 'tcx, 'tcx>) -> Ty<'tcx> {
+        tcx.item_type(self.def_id())
+    }
+
+    #[inline]
+    pub fn attrs<'a>(&self, tcx: ty::TyCtxt<'a, 'tcx, 'tcx>) -> Cow<'tcx, [ast::Attribute]> {
+        tcx.get_attrs(self.def_id())
+    }
+
+    pub(crate) fn dep_node(&self) -> DepNode<DefId> {
+        // HACK: def-id binning, project-style; someone replace this with
+        // real on-demand.
+        let ty = match self {
+            &InstanceDef::FnPtrShim(_, ty) => Some(ty),
+            _ => None
+        }.into_iter();
+
+        DepNode::MirShim(
+            Some(self.def_id()).into_iter().chain(
+                ty.flat_map(|t| t.walk()).flat_map(|t| match t.sty {
+                   ty::TyAdt(adt_def, _) => Some(adt_def.did),
+                   ty::TyProjection(ref proj) => Some(proj.trait_ref.def_id),
+                   _ => None,
+               })
+            ).collect()
+        )
+    }
+}
+
+impl<'tcx> fmt::Display for Instance<'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self.def {
+            InstanceDef::Item(def) => {
+                ppaux::parameterized(f, self.substs, def, &[])
+            }
+            InstanceDef::FnPtrShim(def, ty) => {
+                ppaux::parameterized(f, self.substs, def, &[])?;
+                write!(f, " - shim({:?})", ty)
+            }
+        }
+    }
+}
+
+impl<'a, 'b, 'tcx> Instance<'tcx> {
+    pub fn new(def_id: DefId, substs: &'tcx Substs<'tcx>)
+               -> Instance<'tcx> {
+        assert!(substs.is_normalized_for_trans() && !substs.has_escaping_regions(),
+                "substs of instance {:?} not normalized for trans: {:?}",
+                def_id, substs);
+        Instance { def: InstanceDef::Item(def_id), substs: substs }
+    }
+
+    pub fn mono(tcx: ty::TyCtxt<'a, 'tcx, 'b>, def_id: DefId) -> Instance<'tcx> {
+        Instance::new(def_id, tcx.global_tcx().empty_substs_for_def_id(def_id))
+    }
+
+    #[inline]
+    pub fn def_id(&self) -> DefId {
+        self.def.def_id()
+    }
+}
diff --git a/src/librustc/ty/maps.rs b/src/librustc/ty/maps.rs
index af05c0c4311..ac8c38c7d58 100644
--- a/src/librustc/ty/maps.rs
+++ b/src/librustc/ty/maps.rs
@@ -9,7 +9,7 @@
 // except according to those terms.
 
 use dep_graph::{DepGraph, DepNode, DepTrackingMap, DepTrackingMapConfig};
-use hir::def_id::{CrateNum, DefId};
+use hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
 use middle::const_val::ConstVal;
 use mir;
 use ty::{self, Ty, TyCtxt};
@@ -24,6 +24,16 @@ trait Key {
     fn default_span(&self, tcx: TyCtxt) -> Span;
 }
 
+impl<'tcx> Key for ty::InstanceDef<'tcx> {
+    fn map_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+
+    fn default_span(&self, tcx: TyCtxt) -> Span {
+        tcx.def_span(self.def_id())
+    }
+}
+
 impl Key for CrateNum {
     fn map_crate(&self) -> CrateNum {
         *self
@@ -83,9 +93,9 @@ impl<'tcx> Value<'tcx> for Ty<'tcx> {
     }
 }
 
-pub struct CycleError<'a> {
+pub struct CycleError<'a, 'tcx: 'a> {
     span: Span,
-    cycle: RefMut<'a, [(Span, Query)]>,
+    cycle: RefMut<'a, [(Span, Query<'tcx>)]>,
 }
 
 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
@@ -110,8 +120,8 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         err.emit();
     }
 
-    fn cycle_check<F, R>(self, span: Span, query: Query, compute: F)
-                         -> Result<R, CycleError<'a>>
+    fn cycle_check<F, R>(self, span: Span, query: Query<'gcx>, compute: F)
+                         -> Result<R, CycleError<'a, 'gcx>>
         where F: FnOnce() -> R
     {
         {
@@ -172,13 +182,20 @@ impl<'tcx> QueryDescription for queries::coherent_inherent_impls<'tcx> {
     }
 }
 
+impl<'tcx> QueryDescription for queries::mir_shims<'tcx> {
+    fn describe(tcx: TyCtxt, def: ty::InstanceDef<'tcx>) -> String {
+        format!("generating MIR shim for `{}`",
+                tcx.item_path_str(def.def_id()))
+    }
+}
+
 macro_rules! define_maps {
     (<$tcx:tt>
      $($(#[$attr:meta])*
        pub $name:ident: $node:ident($K:ty) -> $V:ty),*) => {
         pub struct Maps<$tcx> {
             providers: IndexVec<CrateNum, Providers<$tcx>>,
-            query_stack: RefCell<Vec<(Span, Query)>>,
+            query_stack: RefCell<Vec<(Span, Query<$tcx>)>>,
             $($(#[$attr])* pub $name: RefCell<DepTrackingMap<queries::$name<$tcx>>>),*
         }
 
@@ -196,11 +213,11 @@ macro_rules! define_maps {
 
         #[allow(bad_style)]
         #[derive(Copy, Clone, Debug, PartialEq, Eq)]
-        pub enum Query {
+        pub enum Query<$tcx> {
             $($(#[$attr])* $name($K)),*
         }
 
-        impl Query {
+        impl<$tcx> Query<$tcx> {
             pub fn describe(&self, tcx: TyCtxt) -> String {
                 match *self {
                     $(Query::$name(key) => queries::$name::describe(tcx, key)),*
@@ -233,7 +250,7 @@ macro_rules! define_maps {
                                   mut span: Span,
                                   key: $K,
                                   f: F)
-                                  -> Result<R, CycleError<'a>>
+                                  -> Result<R, CycleError<'a, $tcx>>
                 where F: FnOnce(&$V) -> R
             {
                 if let Some(result) = tcx.maps.$name.borrow().get(&key) {
@@ -256,7 +273,7 @@ macro_rules! define_maps {
             }
 
             pub fn try_get(tcx: TyCtxt<'a, $tcx, 'lcx>, span: Span, key: $K)
-                           -> Result<$V, CycleError<'a>> {
+                           -> Result<$V, CycleError<'a, $tcx>> {
                 Self::try_get_with(tcx, span, key, Clone::clone)
             }
 
@@ -387,7 +404,9 @@ define_maps! { <'tcx>
 
     /// Results of evaluating monomorphic constants embedded in
     /// other items, such as enum variant explicit discriminants.
-    pub monomorphic_const_eval: MonomorphicConstEval(DefId) -> Result<ConstVal<'tcx>, ()>
+    pub monomorphic_const_eval: MonomorphicConstEval(DefId) -> Result<ConstVal<'tcx>, ()>,
+
+    pub mir_shims: mir_shim(ty::InstanceDef<'tcx>) -> &'tcx RefCell<mir::Mir<'tcx>>
 }
 
 fn coherent_trait_dep_node((_, def_id): (CrateNum, DefId)) -> DepNode<DefId> {
@@ -397,3 +416,7 @@ fn coherent_trait_dep_node((_, def_id): (CrateNum, DefId)) -> DepNode<DefId> {
 fn coherent_inherent_impls_dep_node(_: CrateNum) -> DepNode<DefId> {
     DepNode::Coherence
 }
+
+fn mir_shim(instance: ty::InstanceDef) -> DepNode<DefId> {
+    instance.dep_node()
+}
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 360fa24bf36..c4192ffc697 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -73,6 +73,8 @@ pub use self::contents::TypeContents;
 pub use self::context::{TyCtxt, GlobalArenas, tls};
 pub use self::context::{Lift, TypeckTables};
 
+pub use self::instance::{Instance, InstanceDef};
+
 pub use self::trait_def::{TraitDef, TraitFlags};
 
 pub use self::maps::queries;
@@ -98,6 +100,7 @@ pub mod util;
 mod contents;
 mod context;
 mod flags;
+mod instance;
 mod structural_impls;
 mod sty;
 
@@ -2309,6 +2312,16 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         queries::mir::get(self, DUMMY_SP, did).borrow()
     }
 
+    /// Return the possibly-auto-generated MIR of a (DefId, Subst) pair.
+    pub fn instance_mir(self, instance: ty::InstanceDef<'gcx>)
+                        -> Ref<'gcx, Mir<'gcx>>
+    {
+        match instance {
+            ty::InstanceDef::Item(did) if true => self.item_mir(did),
+            _ => queries::mir_shims::get(self, DUMMY_SP, instance).borrow(),
+        }
+    }
+
     /// Given the DefId of an item, returns its MIR, borrowed immutably.
     /// Returns None if there is no MIR for the DefId
     pub fn maybe_item_mir(self, did: DefId) -> Option<Ref<'gcx, Mir<'gcx>>> {
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index fd957249909..2344305fa9a 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -398,6 +398,18 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         }
         def_id
     }
+
+    /// Given the def-id of some item that has no type parameters, make
+    /// a suitable "empty substs" for it.
+    pub fn empty_substs_for_def_id(self, item_def_id: DefId) -> &'tcx ty::Substs<'tcx> {
+        ty::Substs::for_item(self, item_def_id,
+                             |_, _| self.mk_region(ty::ReErased),
+                             |_, _| {
+            bug!("empty_substs_for_def_id: {:?} has type parameters", item_def_id)
+        })
+    }
+
+
 }
 
 pub struct TypeIdHasher<'a, 'gcx: 'a+'tcx, 'tcx: 'a, W> {
diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs
index 19028bfa531..9e6b77dbabd 100644
--- a/src/librustc_mir/lib.rs
+++ b/src/librustc_mir/lib.rs
@@ -60,5 +60,6 @@ use rustc::ty::maps::Providers;
 
 pub fn provide(providers: &mut Providers) {
     mir_map::provide(providers);
+    shim::provide(providers);
     transform::qualify_consts::provide(providers);
 }
\ No newline at end of file
diff --git a/src/librustc_mir/shim.rs b/src/librustc_mir/shim.rs
index 3705a317715..0fbd488ffa3 100644
--- a/src/librustc_mir/shim.rs
+++ b/src/librustc_mir/shim.rs
@@ -13,14 +13,31 @@ use rustc::infer;
 use rustc::mir::*;
 use rustc::mir::transform::MirSource;
 use rustc::ty;
+use rustc::ty::maps::Providers;
 
 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
 
 use syntax::ast;
 use syntax_pos::Span;
 
+use std::cell::RefCell;
 use std::iter;
 
+pub fn provide(providers: &mut Providers) {
+    providers.mir_shims = make_shim;
+}
+
+fn make_shim<'a, 'tcx>(_tcx: ty::TyCtxt<'a, 'tcx, 'tcx>,
+                       instance: ty::InstanceDef<'tcx>)
+                       -> &'tcx RefCell<Mir<'tcx>>
+{
+    match instance {
+        ty::InstanceDef::Item(..) =>
+            bug!("item {:?} passed to make_shim", instance),
+        ty::InstanceDef::FnPtrShim(..) => unimplemented!()
+    }
+}
+
 fn local_decls_for_sig<'tcx>(sig: &ty::FnSig<'tcx>)
     -> IndexVec<Local, LocalDecl<'tcx>>
 {
diff --git a/src/librustc_trans/back/symbol_export.rs b/src/librustc_trans/back/symbol_export.rs
index bea3ca8df70..005fb3533ab 100644
--- a/src/librustc_trans/back/symbol_export.rs
+++ b/src/librustc_trans/back/symbol_export.rs
@@ -11,6 +11,7 @@
 use context::SharedCrateContext;
 use monomorphize::Instance;
 use symbol_map::SymbolMap;
+use back::symbol_names::symbol_name;
 use util::nodemap::FxHashMap;
 use rustc::hir::def_id::{DefId, CrateNum, LOCAL_CRATE};
 use rustc::session::config;
@@ -106,7 +107,7 @@ impl ExportedSymbols {
                 .exported_symbols(cnum)
                 .iter()
                 .map(|&def_id| {
-                    let name = Instance::mono(scx, def_id).symbol_name(scx);
+                    let name = symbol_name(Instance::mono(scx.tcx(), def_id), scx);
                     let export_level = if special_runtime_crate {
                         // We can probably do better here by just ensuring that
                         // it has hidden visibility rather than public
@@ -218,9 +219,9 @@ fn symbol_for_def_id<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
         }
     }
 
-    let instance = Instance::mono(scx, def_id);
+    let instance = Instance::mono(scx.tcx(), def_id);
 
     symbol_map.get(TransItem::Fn(instance))
               .map(str::to_owned)
-              .unwrap_or_else(|| instance.symbol_name(scx))
+              .unwrap_or_else(|| symbol_name(instance, scx))
 }
diff --git a/src/librustc_trans/back/symbol_names.rs b/src/librustc_trans/back/symbol_names.rs
index fe58bc8f5f2..518995dfedc 100644
--- a/src/librustc_trans/back/symbol_names.rs
+++ b/src/librustc_trans/back/symbol_names.rs
@@ -168,105 +168,105 @@ fn get_symbol_hash<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
     format!("h{:016x}", hasher.finish())
 }
 
-impl<'a, 'tcx> Instance<'tcx> {
-    pub fn symbol_name(self, scx: &SharedCrateContext<'a, 'tcx>) -> String {
-        let Instance { def: def_id, substs } = self;
+pub fn symbol_name<'a, 'tcx>(instance: Instance<'tcx>,
+                             scx: &SharedCrateContext<'a, 'tcx>) -> String {
+    let def_id = instance.def_id();
+    let substs = instance.substs;
 
-        debug!("symbol_name(def_id={:?}, substs={:?})",
-               def_id, substs);
+    debug!("symbol_name(def_id={:?}, substs={:?})",
+           def_id, substs);
 
-        let node_id = scx.tcx().hir.as_local_node_id(def_id);
+    let node_id = scx.tcx().hir.as_local_node_id(def_id);
 
-        if let Some(id) = node_id {
-            if scx.sess().plugin_registrar_fn.get() == Some(id) {
-                let svh = &scx.link_meta().crate_hash;
-                let idx = def_id.index;
-                return scx.sess().generate_plugin_registrar_symbol(svh, idx);
-            }
-            if scx.sess().derive_registrar_fn.get() == Some(id) {
-                let svh = &scx.link_meta().crate_hash;
-                let idx = def_id.index;
-                return scx.sess().generate_derive_registrar_symbol(svh, idx);
-            }
+    if let Some(id) = node_id {
+        if scx.sess().plugin_registrar_fn.get() == Some(id) {
+            let svh = &scx.link_meta().crate_hash;
+            let idx = def_id.index;
+            return scx.sess().generate_plugin_registrar_symbol(svh, idx);
         }
-
-        // FIXME(eddyb) Precompute a custom symbol name based on attributes.
-        let attrs = scx.tcx().get_attrs(def_id);
-        let is_foreign = if let Some(id) = node_id {
-            match scx.tcx().hir.get(id) {
-                hir_map::NodeForeignItem(_) => true,
-                _ => false
-            }
-        } else {
-            scx.sess().cstore.is_foreign_item(def_id)
-        };
-
-        if let Some(name) = weak_lang_items::link_name(&attrs) {
-            return name.to_string();
+        if scx.sess().derive_registrar_fn.get() == Some(id) {
+            let svh = &scx.link_meta().crate_hash;
+            let idx = def_id.index;
+            return scx.sess().generate_derive_registrar_symbol(svh, idx);
         }
+    }
 
-        if is_foreign {
-            if let Some(name) = attr::first_attr_value_str_by_name(&attrs, "link_name") {
-                return name.to_string();
-            }
-            // Don't mangle foreign items.
-            return scx.tcx().item_name(def_id).as_str().to_string();
+    // FIXME(eddyb) Precompute a custom symbol name based on attributes.
+    let attrs = scx.tcx().get_attrs(def_id);
+    let is_foreign = if let Some(id) = node_id {
+        match scx.tcx().hir.get(id) {
+            hir_map::NodeForeignItem(_) => true,
+            _ => false
         }
+    } else {
+        scx.sess().cstore.is_foreign_item(def_id)
+    };
 
-        if let Some(name) = attr::find_export_name_attr(scx.sess().diagnostic(), &attrs) {
-            // Use provided name
+    if let Some(name) = weak_lang_items::link_name(&attrs) {
+        return name.to_string();
+    }
+
+    if is_foreign {
+        if let Some(name) = attr::first_attr_value_str_by_name(&attrs, "link_name") {
             return name.to_string();
         }
+        // Don't mangle foreign items.
+        return scx.tcx().item_name(def_id).as_str().to_string();
+    }
 
-        if attr::contains_name(&attrs, "no_mangle") {
-            // Don't mangle
-            return scx.tcx().item_name(def_id).as_str().to_string();
-        }
+    if let Some(name) = attr::find_export_name_attr(scx.sess().diagnostic(), &attrs) {
+        // Use provided name
+        return name.to_string();
+    }
 
-        let def_path = scx.tcx().def_path(def_id);
-
-        // We want to compute the "type" of this item. Unfortunately, some
-        // kinds of items (e.g., closures) don't have an entry in the
-        // item-type array. So walk back up the find the closest parent
-        // that DOES have an entry.
-        let mut ty_def_id = def_id;
-        let instance_ty;
-        loop {
-            let key = scx.tcx().def_key(ty_def_id);
-            match key.disambiguated_data.data {
-                DefPathData::TypeNs(_) |
-                DefPathData::ValueNs(_) => {
-                    instance_ty = scx.tcx().item_type(ty_def_id);
-                    break;
-                }
-                _ => {
-                    // if we're making a symbol for something, there ought
-                    // to be a value or type-def or something in there
-                    // *somewhere*
-                    ty_def_id.index = key.parent.unwrap_or_else(|| {
-                        bug!("finding type for {:?}, encountered def-id {:?} with no \
-                             parent", def_id, ty_def_id);
-                    });
-                }
+    if attr::contains_name(&attrs, "no_mangle") {
+        // Don't mangle
+        return scx.tcx().item_name(def_id).as_str().to_string();
+    }
+
+    let def_path = scx.tcx().def_path(def_id);
+
+    // We want to compute the "type" of this item. Unfortunately, some
+    // kinds of items (e.g., closures) don't have an entry in the
+    // item-type array. So walk back up the find the closest parent
+    // that DOES have an entry.
+    let mut ty_def_id = def_id;
+    let instance_ty;
+    loop {
+        let key = scx.tcx().def_key(ty_def_id);
+        match key.disambiguated_data.data {
+            DefPathData::TypeNs(_) |
+            DefPathData::ValueNs(_) => {
+                instance_ty = scx.tcx().item_type(ty_def_id);
+                break;
+            }
+            _ => {
+                // if we're making a symbol for something, there ought
+                // to be a value or type-def or something in there
+                // *somewhere*
+                ty_def_id.index = key.parent.unwrap_or_else(|| {
+                    bug!("finding type for {:?}, encountered def-id {:?} with no \
+                          parent", def_id, ty_def_id);
+                });
             }
         }
+    }
 
-        // Erase regions because they may not be deterministic when hashed
-        // and should not matter anyhow.
-        let instance_ty = scx.tcx().erase_regions(&instance_ty);
+    // Erase regions because they may not be deterministic when hashed
+    // and should not matter anyhow.
+    let instance_ty = scx.tcx().erase_regions(&instance_ty);
 
-        let hash = get_symbol_hash(scx, &def_path, instance_ty, Some(substs));
+    let hash = get_symbol_hash(scx, &def_path, instance_ty, Some(substs));
 
-        let mut buffer = SymbolPathBuffer {
-            names: Vec::with_capacity(def_path.data.len())
-        };
+    let mut buffer = SymbolPathBuffer {
+        names: Vec::with_capacity(def_path.data.len())
+    };
 
-        item_path::with_forced_absolute_paths(|| {
-            scx.tcx().push_item_path(&mut buffer, def_id);
-        });
+    item_path::with_forced_absolute_paths(|| {
+        scx.tcx().push_item_path(&mut buffer, def_id);
+    });
 
-        mangle(buffer.names.into_iter(), &hash)
-    }
+    mangle(buffer.names.into_iter(), &hash)
 }
 
 struct SymbolPathBuffer {
diff --git a/src/librustc_trans/base.rs b/src/librustc_trans/base.rs
index fe2b21895cc..ce767468c01 100644
--- a/src/librustc_trans/base.rs
+++ b/src/librustc_trans/base.rs
@@ -565,11 +565,11 @@ pub fn memcpy_ty<'a, 'tcx>(
 }
 
 pub fn call_memset<'a, 'tcx>(b: &Builder<'a, 'tcx>,
-                               ptr: ValueRef,
-                               fill_byte: ValueRef,
-                               size: ValueRef,
-                               align: ValueRef,
-                               volatile: bool) -> ValueRef {
+                             ptr: ValueRef,
+                             fill_byte: ValueRef,
+                             size: ValueRef,
+                             align: ValueRef,
+                             volatile: bool) -> ValueRef {
     let ptr_width = &b.ccx.sess().target.target.target_pointer_width[..];
     let intrinsic_key = format!("llvm.memset.p0i8.i{}", ptr_width);
     let llintrinsicfn = b.ccx.get_intrinsic(&intrinsic_key);
@@ -581,7 +581,7 @@ pub fn trans_instance<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, instance: Instance
     let _s = if ccx.sess().trans_stats() {
         let mut instance_name = String::new();
         DefPathBasedNames::new(ccx.tcx(), true, true)
-            .push_def_path(instance.def, &mut instance_name);
+            .push_def_path(instance.def_id(), &mut instance_name);
         Some(StatRecorder::new(ccx, instance_name))
     } else {
         None
@@ -592,7 +592,7 @@ pub fn trans_instance<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, instance: Instance
     // release builds.
     info!("trans_instance({})", instance);
 
-    let fn_ty = common::def_ty(ccx.shared(), instance.def, instance.substs);
+    let fn_ty = common::instance_ty(ccx.shared(), &instance);
     let sig = common::ty_fn_sig(ccx, fn_ty);
     let sig = ccx.tcx().erase_late_bound_regions_and_normalize(&sig);
 
@@ -607,7 +607,7 @@ pub fn trans_instance<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, instance: Instance
         attributes::emit_uwtable(lldecl, true);
     }
 
-    let mir = ccx.tcx().item_mir(instance.def);
+    let mir = ccx.tcx().instance_mir(instance.def);
     mir::trans_mir(ccx, lldecl, &mir, instance, sig);
 }
 
@@ -668,7 +668,7 @@ pub fn maybe_create_entry_wrapper(ccx: &CrateContext) {
         ccx.tcx().sess.span_fatal(span, "compilation successful");
     }
 
-    let instance = Instance::mono(ccx.shared(), main_def_id);
+    let instance = Instance::mono(ccx.tcx(), main_def_id);
 
     if !ccx.codegen_unit().contains_item(&TransItem::Fn(instance)) {
         // We want to create the wrapper in the same codegen unit as Rust's main
diff --git a/src/librustc_trans/callee.rs b/src/librustc_trans/callee.rs
index a5b42a973cf..19fc4e013fa 100644
--- a/src/librustc_trans/callee.rs
+++ b/src/librustc_trans/callee.rs
@@ -27,11 +27,12 @@ use common::{self, CrateContext};
 use cleanup::CleanupScope;
 use mir::lvalue::LvalueRef;
 use consts;
-use common::def_ty;
+use common::instance_ty;
 use declare;
 use value::Value;
 use meth;
 use monomorphize::Instance;
+use back::symbol_names::symbol_name;
 use trans_item::TransItem;
 use type_of;
 use rustc::ty::{self, Ty, TypeFoldable};
@@ -77,7 +78,8 @@ impl<'tcx> Callee<'tcx> {
             return Callee::trait_method(ccx, trait_id, def_id, substs);
         }
 
-        let fn_ty = def_ty(ccx.shared(), def_id, substs);
+        let instance = ty::Instance::new(def_id, substs);
+        let fn_ty = instance_ty(ccx.shared(), &instance);
         if let ty::TyFnDef(.., f) = fn_ty.sty {
             if f.abi() == Abi::RustIntrinsic || f.abi() == Abi::PlatformIntrinsic {
                 return Callee {
@@ -87,7 +89,7 @@ impl<'tcx> Callee<'tcx> {
             }
         }
 
-        let (llfn, ty) = get_fn(ccx, def_id, substs);
+        let (llfn, ty) = get_fn(ccx, instance);
         Callee::ptr(llfn, ty)
     }
 
@@ -104,13 +106,13 @@ impl<'tcx> Callee<'tcx> {
         match common::fulfill_obligation(ccx.shared(), DUMMY_SP, trait_ref) {
             traits::VtableImpl(vtable_impl) => {
                 let name = tcx.item_name(def_id);
-                let (def_id, substs) = traits::find_method(tcx, name, substs, &vtable_impl);
+                let instance = common::find_method(tcx, name, substs, &vtable_impl);
 
                 // Translate the function, bypassing Callee::def.
                 // That is because default methods have the same ID as the
                 // trait method used to look up the impl method that ended
                 // up here, so calling Callee::def would infinitely recurse.
-                let (llfn, ty) = get_fn(ccx, def_id, substs);
+                let (llfn, ty) = get_fn(ccx, instance);
                 Callee::ptr(llfn, ty)
             }
             traits::VtableClosure(vtable_closure) => {
@@ -125,7 +127,7 @@ impl<'tcx> Callee<'tcx> {
                     instance,
                     trait_closure_kind);
 
-                let method_ty = def_ty(ccx.shared(), def_id, substs);
+                let method_ty = instance_ty(ccx.shared(), &instance);
                 Callee::ptr(llfn, method_ty)
             }
             traits::VtableFnPointer(vtable_fn_pointer) => {
@@ -135,13 +137,13 @@ impl<'tcx> Callee<'tcx> {
                                                  trait_closure_kind,
                                                  vtable_fn_pointer.fn_ty);
 
-                let method_ty = def_ty(ccx.shared(), def_id, substs);
+                let method_ty = instance_ty(ccx.shared(), &instance);
                 Callee::ptr(llfn, method_ty)
             }
             traits::VtableObject(ref data) => {
                 Callee {
                     data: Virtual(tcx.get_vtable_index_of_object_method(data, def_id)),
-                    ty: def_ty(ccx.shared(), def_id, substs)
+                    ty: instance_ty(ccx.shared(), &Instance::new(def_id, substs))
                 }
             }
             vtable => {
@@ -183,7 +185,7 @@ fn trans_closure_method<'a, 'tcx>(ccx: &'a CrateContext<'a, 'tcx>,
                                   -> ValueRef
 {
     // If this is a closure, redirect to it.
-    let (llfn, _) = get_fn(ccx, def_id, substs.substs);
+    let (llfn, _) = get_fn(ccx, Instance::new(def_id, substs.substs));
 
     // If the closure is a Fn closure, but a FnOnce is needed (etc),
     // then adapt the self type
@@ -292,7 +294,7 @@ fn trans_fn_once_adapter_shim<'a, 'tcx>(
     let llonce_fn_ty = tcx.mk_fn_ptr(ty::Binder(sig));
 
     // Create the by-value helper.
-    let function_name = method_instance.symbol_name(ccx.shared());
+    let function_name = symbol_name(method_instance, ccx.shared());
     let lloncefn = declare::define_internal_fn(ccx, &function_name, llonce_fn_ty);
     attributes::set_frame_pointer_elimination(ccx, lloncefn);
 
@@ -438,7 +440,7 @@ fn trans_fn_pointer_shim<'a, 'tcx>(
     debug!("tuple_fn_ty: {:?}", tuple_fn_ty);
 
     //
-    let function_name = method_instance.symbol_name(ccx.shared());
+    let function_name = symbol_name(method_instance, ccx.shared());
     let llfn = declare::define_internal_fn(ccx, &function_name, tuple_fn_ty);
     attributes::set_frame_pointer_elimination(ccx, llfn);
     //
@@ -489,21 +491,17 @@ fn trans_fn_pointer_shim<'a, 'tcx>(
 /// - `def_id`: def id of the fn or method item being referenced
 /// - `substs`: values for each of the fn/method's parameters
 fn get_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
-                    def_id: DefId,
-                    substs: &'tcx Substs<'tcx>)
+                    instance: Instance<'tcx>)
                     -> (ValueRef, Ty<'tcx>) {
     let tcx = ccx.tcx();
 
-    debug!("get_fn(def_id={:?}, substs={:?})", def_id, substs);
+    debug!("get_fn(instance={:?})", instance);
 
-    assert!(!substs.needs_infer());
-    assert!(!substs.has_escaping_regions());
-    assert!(!substs.has_param_types());
-
-    let substs = tcx.normalize_associated_type(&substs);
-    let instance = Instance::new(def_id, substs);
-    let fn_ty = common::def_ty(ccx.shared(), def_id, substs);
+    assert!(!instance.substs.needs_infer());
+    assert!(!instance.substs.has_escaping_regions());
+    assert!(!instance.substs.has_param_types());
 
+    let fn_ty = common::instance_ty(ccx.shared(), &instance);
     if let Some(&llfn) = ccx.instances().borrow().get(&instance) {
         return (llfn, fn_ty);
     }
@@ -553,7 +551,7 @@ fn get_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
         assert_eq!(common::val_ty(llfn), llptrty);
         debug!("get_fn: not casting pointer!");
 
-        let attrs = ccx.tcx().get_attrs(def_id);
+        let attrs = instance.def.attrs(ccx.tcx());
         attributes::from_fn_attrs(ccx, &attrs, llfn);
 
         let is_local_def = ccx.shared().translation_items().borrow()
@@ -565,7 +563,9 @@ fn get_fn<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                 llvm::LLVMRustSetLinkage(llfn, llvm::Linkage::ExternalLinkage);
             }
         }
-        if ccx.use_dll_storage_attrs() && ccx.sess().cstore.is_dllimport_foreign_item(def_id) {
+        if ccx.use_dll_storage_attrs() &&
+            ccx.sess().cstore.is_dllimport_foreign_item(instance.def_id())
+        {
             unsafe {
                 llvm::LLVMSetDLLStorageClass(llfn, llvm::DLLStorageClass::DllImport);
             }
diff --git a/src/librustc_trans/collector.rs b/src/librustc_trans/collector.rs
index 5e6b10f826c..271f91f9adb 100644
--- a/src/librustc_trans/collector.rs
+++ b/src/librustc_trans/collector.rs
@@ -207,7 +207,7 @@ use syntax_pos::DUMMY_SP;
 use base::custom_coerce_unsize_info;
 use callee::needs_fn_once_adapter_shim;
 use context::SharedCrateContext;
-use common::{def_ty, fulfill_obligation};
+use common::{def_ty, find_method, instance_ty, fulfill_obligation};
 use glue::{self, DropGlueKind};
 use monomorphize::{self, Instance};
 use util::nodemap::{FxHashSet, FxHashMap, DefIdMap};
@@ -337,21 +337,22 @@ fn collect_items_rec<'a, 'tcx: 'a>(scx: &SharedCrateContext<'a, 'tcx>,
         }
         TransItem::Static(node_id) => {
             let def_id = scx.tcx().hir.local_def_id(node_id);
+            let instance = Instance::mono(scx.tcx(), def_id);
 
             // Sanity check whether this ended up being collected accidentally
-            debug_assert!(should_trans_locally(scx.tcx(), def_id));
+            debug_assert!(should_trans_locally(scx.tcx(), &instance));
 
-            let ty = def_ty(scx, def_id, Substs::empty());
+            let ty = instance_ty(scx, &instance);
             let ty = glue::get_drop_glue_type(scx, ty);
             neighbors.push(TransItem::DropGlue(DropGlueKind::Ty(ty)));
 
             recursion_depth_reset = None;
 
-            collect_neighbours(scx, Instance::mono(scx, def_id), &mut neighbors);
+            collect_neighbours(scx, instance, &mut neighbors);
         }
         TransItem::Fn(instance) => {
             // Sanity check whether this ended up being collected accidentally
-            debug_assert!(should_trans_locally(scx.tcx(), instance.def));
+            debug_assert!(should_trans_locally(scx.tcx(), &instance));
 
             // Keep track of the monomorphization recursion depth
             recursion_depth_reset = Some(check_recursion_limit(scx.tcx(),
@@ -395,9 +396,8 @@ fn check_recursion_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                    instance: Instance<'tcx>,
                                    recursion_depths: &mut DefIdMap<usize>)
                                    -> (DefId, usize) {
-    let recursion_depth = recursion_depths.get(&instance.def)
-                                          .map(|x| *x)
-                                          .unwrap_or(0);
+    let def_id = instance.def_id();
+    let recursion_depth = recursion_depths.get(&def_id).cloned().unwrap_or(0);
     debug!(" => recursion depth={}", recursion_depth);
 
     // Code that needs to instantiate the same function recursively
@@ -406,16 +406,16 @@ fn check_recursion_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     if recursion_depth > tcx.sess.recursion_limit.get() {
         let error = format!("reached the recursion limit while instantiating `{}`",
                             instance);
-        if let Some(node_id) = tcx.hir.as_local_node_id(instance.def) {
+        if let Some(node_id) = tcx.hir.as_local_node_id(def_id) {
             tcx.sess.span_fatal(tcx.hir.span(node_id), &error);
         } else {
             tcx.sess.fatal(&error);
         }
     }
 
-    recursion_depths.insert(instance.def, recursion_depth + 1);
+    recursion_depths.insert(def_id, recursion_depth + 1);
 
-    (instance.def, recursion_depth)
+    (def_id, recursion_depth)
 }
 
 fn check_type_length_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
@@ -438,7 +438,7 @@ fn check_type_length_limit<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         let instance_name = instance.to_string();
         let msg = format!("reached the type-length limit while instantiating `{:.64}...`",
                           instance_name);
-        let mut diag = if let Some(node_id) = tcx.hir.as_local_node_id(instance.def) {
+        let mut diag = if let Some(node_id) = tcx.hir.as_local_node_id(instance.def_id()) {
             tcx.sess.struct_span_fatal(tcx.hir.span(node_id), &msg)
         } else {
             tcx.sess.struct_fatal(&msg)
@@ -493,33 +493,24 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
                 let source_ty = operand.ty(self.mir, self.scx.tcx());
                 match source_ty.sty {
                     ty::TyClosure(def_id, substs) => {
-                        let closure_trans_item =
-                            create_fn_trans_item(self.scx,
-                                                 def_id,
-                                                 substs.substs,
-                                                 self.param_substs);
-                        self.output.push(closure_trans_item);
+                        let substs = monomorphize::apply_param_substs(
+                            self.scx, self.param_substs, &substs.substs);
+                        self.output.push(create_fn_trans_item(
+                            Instance::new(def_id, substs)
+                        ));
                     }
                     _ => bug!(),
                 }
             }
             mir::Rvalue::Box(..) => {
-                let exchange_malloc_fn_def_id =
-                    self.scx
-                        .tcx()
-                        .lang_items
-                        .require(ExchangeMallocFnLangItem)
-                        .unwrap_or_else(|e| self.scx.sess().fatal(&e));
-
-                if should_trans_locally(self.scx.tcx(), exchange_malloc_fn_def_id) {
-                    let empty_substs = self.scx.empty_substs_for_def_id(exchange_malloc_fn_def_id);
-                    let exchange_malloc_fn_trans_item =
-                        create_fn_trans_item(self.scx,
-                                             exchange_malloc_fn_def_id,
-                                             empty_substs,
-                                             self.param_substs);
-
-                    self.output.push(exchange_malloc_fn_trans_item);
+                let tcx = self.scx.tcx();
+                let exchange_malloc_fn_def_id = tcx
+                    .lang_items
+                    .require(ExchangeMallocFnLangItem)
+                    .unwrap_or_else(|e| self.scx.sess().fatal(&e));
+                let instance = Instance::mono(tcx, exchange_malloc_fn_def_id);
+                if should_trans_locally(tcx, &instance) {
+                    self.output.push(create_fn_trans_item(instance));
                 }
             }
             _ => { /* not interesting */ }
@@ -564,8 +555,7 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
                         let substs = monomorphize::apply_param_substs(self.scx,
                                                                       self.param_substs,
                                                                       &substs);
-
-                        let instance = Instance::new(def_id, substs).resolve_const(self.scx);
+                        let instance = monomorphize::resolve_const(self.scx, def_id, substs);
                         collect_neighbours(self.scx, instance, self.output);
                     }
 
@@ -586,28 +576,24 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
             //
             // Calling do_static_dispatch() here will map the def_id of
             // `std::cmp::partial_cmp` to the def_id of `i32::partial_cmp<i32>`
+
+            let callee_substs = monomorphize::apply_param_substs(self.scx,
+                                                                 self.param_substs,
+                                                                 &callee_substs);
             let dispatched = do_static_dispatch(self.scx,
                                                 callee_def_id,
-                                                callee_substs,
-                                                self.param_substs);
+                                                callee_substs);
 
             if let StaticDispatchResult::Dispatched {
-                    def_id: callee_def_id,
-                    substs: callee_substs,
-                    fn_once_adjustment,
-                } = dispatched {
+                instance, fn_once_adjustment
+            } = dispatched {
                 // if we have a concrete impl (which we might not have
                 // in the case of something compiler generated like an
                 // object shim or a closure that is handled differently),
                 // we check if the callee is something that will actually
                 // result in a translation item ...
-                if can_result_in_trans_item(self.scx.tcx(), callee_def_id) {
-                    // ... and create one if it does.
-                    let trans_item = create_fn_trans_item(self.scx,
-                                                          callee_def_id,
-                                                          callee_substs,
-                                                          self.param_substs);
-                    self.output.push(trans_item);
+                if should_trans_locally(self.scx.tcx(), &instance) {
+                    self.output.push(create_fn_trans_item(instance));
 
                     // This call will instantiate an FnOnce adapter, which drops
                     // the closure environment. Therefore we need to make sure
@@ -624,26 +610,6 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
         }
 
         self.super_operand(operand, location);
-
-        fn can_result_in_trans_item<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                                              def_id: DefId)
-                                              -> bool {
-            match tcx.item_type(def_id).sty {
-                ty::TyFnDef(def_id, _, _) => {
-                    // foreign items are linked from another library, not
-                    // translated locally.
-                    if let Some(hir_map::NodeForeignItem(_)) = tcx.hir.get_if_local(def_id) {
-                        return false;
-                    }
-                }
-                ty::TyClosure(..) => {
-                    // TODO: trans items for closures
-                }
-                _ => return false
-            }
-
-            should_trans_locally(tcx, def_id)
-        }
     }
 
     // This takes care of the "drop_in_place" intrinsic for which we otherwise
@@ -695,22 +661,30 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
 // Returns true if we should translate an instance in the local crate.
 // Returns false if we can just link to the upstream crate and therefore don't
 // need a translation item.
-fn should_trans_locally<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                                  def_id: DefId)
+fn should_trans_locally<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, instance: &Instance<'tcx>)
                                   -> bool {
-    if def_id.is_local() {
-        true
-    } else {
-        if tcx.sess.cstore.is_exported_symbol(def_id) ||
-           tcx.sess.cstore.is_foreign_item(def_id) {
-            // We can link to the item in question, no instance needed in this
-            // crate
-            false
-        } else {
-            if !tcx.sess.cstore.is_item_mir_available(def_id) {
-                bug!("Cannot create local trans-item for {:?}", def_id)
+    let def_id = match instance.def {
+        ty::InstanceDef::Item(def_id) => def_id,
+        ty::InstanceDef::FnPtrShim(..) => return true
+    };
+    match tcx.hir.get_if_local(def_id) {
+        Some(hir_map::NodeForeignItem(..)) => {
+            false // foreign items are linked against, not translated.
+        }
+        Some(_) => true,
+        None => {
+            if tcx.sess.cstore.is_exported_symbol(def_id) ||
+                tcx.sess.cstore.is_foreign_item(def_id)
+            {
+                // We can link to the item in question, no instance needed
+                // in this crate
+                false
+            } else {
+                if !tcx.sess.cstore.is_item_mir_available(def_id) {
+                    bug!("Cannot create local trans-item for {:?}", def_id)
+                }
+                true
             }
-            true
         }
     }
 }
@@ -731,14 +705,14 @@ fn find_drop_glue_neighbors<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
 
     // Make sure the BoxFreeFn lang-item gets translated if there is a boxed value.
     if ty.is_box() {
-        let def_id = scx.tcx().require_lang_item(BoxFreeFnLangItem);
-        if should_trans_locally(scx.tcx(), def_id) {
-            let box_free_fn_trans_item =
-                create_fn_trans_item(scx,
-                                     def_id,
-                                     scx.tcx().mk_substs(iter::once(Kind::from(ty.boxed_ty()))),
-                                     scx.tcx().intern_substs(&[]));
-            output.push(box_free_fn_trans_item);
+        let tcx = scx.tcx();
+        let def_id = tcx.require_lang_item(BoxFreeFnLangItem);
+        let box_free_instance = Instance::new(
+            def_id,
+            tcx.mk_substs(iter::once(Kind::from(ty.boxed_ty())))
+        );
+        if should_trans_locally(tcx, &box_free_instance) {
+            output.push(create_fn_trans_item(box_free_instance));
         }
     }
 
@@ -768,13 +742,9 @@ fn find_drop_glue_neighbors<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
             traits::VtableImpl(data) => data.substs,
             _ => bug!()
         };
-
-        if should_trans_locally(scx.tcx(), destructor.did) {
-            let trans_item = create_fn_trans_item(scx,
-                                                  destructor.did,
-                                                  substs,
-                                                  scx.tcx().intern_substs(&[]));
-            output.push(trans_item);
+        let instance = Instance::new(destructor.did, substs);
+        if should_trans_locally(scx.tcx(), &instance) {
+            output.push(create_fn_trans_item(instance));
         }
 
         // This type has a Drop implementation, we'll need the contents-only
@@ -847,72 +817,59 @@ fn find_drop_glue_neighbors<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
     }
 }
 
+enum StaticDispatchResult<'tcx> {
+    // The call could be resolved statically as going to the method with
+    // `instance`.
+    Dispatched {
+        instance: Instance<'tcx>,
+        // If this is a call to a closure that needs an FnOnce adjustment,
+        // this contains the new self type of the call (= type of the closure
+        // environment)
+        fn_once_adjustment: Option<ty::Ty<'tcx>>,
+    },
+    // This goes to somewhere that we don't know at compile-time
+    Unknown
+}
+
 fn do_static_dispatch<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
                                 fn_def_id: DefId,
-                                fn_substs: &'tcx Substs<'tcx>,
-                                param_substs: &'tcx Substs<'tcx>)
+                                fn_substs: &'tcx Substs<'tcx>)
                                 -> StaticDispatchResult<'tcx> {
-    debug!("do_static_dispatch(fn_def_id={}, fn_substs={:?}, param_substs={:?})",
+    debug!("do_static_dispatch(fn_def_id={}, fn_substs={:?})",
            def_id_to_string(scx.tcx(), fn_def_id),
-           fn_substs,
-           param_substs);
-
+           fn_substs);
     if let Some(trait_def_id) = scx.tcx().trait_of_item(fn_def_id) {
         debug!(" => trait method, attempting to find impl");
         do_static_trait_method_dispatch(scx,
                                         &scx.tcx().associated_item(fn_def_id),
                                         trait_def_id,
-                                        fn_substs,
-                                        param_substs)
+                                        fn_substs)
     } else {
         debug!(" => regular function");
         // The function is not part of an impl or trait, no dispatching
         // to be done
         StaticDispatchResult::Dispatched {
-            def_id: fn_def_id,
-            substs: fn_substs,
+            instance: Instance::new(fn_def_id, fn_substs),
             fn_once_adjustment: None,
         }
     }
 }
 
-enum StaticDispatchResult<'tcx> {
-    // The call could be resolved statically as going to the method with
-    // `def_id` and `substs`.
-    Dispatched {
-        def_id: DefId,
-        substs: &'tcx Substs<'tcx>,
-
-        // If this is a call to a closure that needs an FnOnce adjustment,
-        // this contains the new self type of the call (= type of the closure
-        // environment)
-        fn_once_adjustment: Option<ty::Ty<'tcx>>,
-    },
-    // This goes to somewhere that we don't know at compile-time
-    Unknown
-}
-
 // Given a trait-method and substitution information, find out the actual
 // implementation of the trait method.
 fn do_static_trait_method_dispatch<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
                                              trait_method: &ty::AssociatedItem,
                                              trait_id: DefId,
-                                             callee_substs: &'tcx Substs<'tcx>,
-                                             param_substs: &'tcx Substs<'tcx>)
+                                             rcvr_substs: &'tcx Substs<'tcx>)
                                              -> StaticDispatchResult<'tcx> {
     let tcx = scx.tcx();
     debug!("do_static_trait_method_dispatch(trait_method={}, \
                                             trait_id={}, \
-                                            callee_substs={:?}, \
-                                            param_substs={:?}",
+                                            rcvr_substs={:?})",
            def_id_to_string(scx.tcx(), trait_method.def_id),
            def_id_to_string(scx.tcx(), trait_id),
-           callee_substs,
-           param_substs);
+           rcvr_substs);
 
-    let rcvr_substs = monomorphize::apply_param_substs(scx,
-                                                       param_substs,
-                                                       &callee_substs);
     let trait_ref = ty::TraitRef::from_method(tcx, trait_id, rcvr_substs);
     let vtbl = fulfill_obligation(scx, DUMMY_SP, ty::Binder(trait_ref));
 
@@ -920,13 +877,8 @@ fn do_static_trait_method_dispatch<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
     // the actual function:
     match vtbl {
         traits::VtableImpl(impl_data) => {
-            let (def_id, substs) = traits::find_method(tcx,
-                                                       trait_method.name,
-                                                       rcvr_substs,
-                                                       &impl_data);
             StaticDispatchResult::Dispatched {
-                def_id: def_id,
-                substs: substs,
+                instance: find_method(tcx, trait_method.name, rcvr_substs, &impl_data),
                 fn_once_adjustment: None,
             }
         }
@@ -950,8 +902,7 @@ fn do_static_trait_method_dispatch<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
             };
 
             StaticDispatchResult::Dispatched {
-                def_id: closure_def_id,
-                substs: closure_data.substs.substs,
+                instance: Instance::new(closure_def_id, closure_data.substs.substs),
                 fn_once_adjustment: fn_once_adjustment,
             }
         }
@@ -961,7 +912,7 @@ fn do_static_trait_method_dispatch<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
             if let ty::TyFnDef(def_id, substs, _) = data.fn_ty.sty {
                 // The destination of the pointer might be something that needs
                 // further dispatching, such as a trait method, so we do that.
-                do_static_dispatch(scx, def_id, substs, param_substs)
+                do_static_dispatch(scx, def_id, substs)
             } else {
                 StaticDispatchResult::Unknown
             }
@@ -1066,28 +1017,9 @@ fn find_vtable_types_for_unsizing<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
     }
 }
 
-fn create_fn_trans_item<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
-                                  def_id: DefId,
-                                  fn_substs: &'tcx Substs<'tcx>,
-                                  param_substs: &'tcx Substs<'tcx>)
-                                  -> TransItem<'tcx> {
-    let tcx = scx.tcx();
-
-    debug!("create_fn_trans_item(def_id={}, fn_substs={:?}, param_substs={:?})",
-            def_id_to_string(tcx, def_id),
-            fn_substs,
-            param_substs);
-
-    // We only get here, if fn_def_id either designates a local item or
-    // an inlineable external item. Non-inlineable external items are
-    // ignored because we don't want to generate any code for them.
-    let concrete_substs = monomorphize::apply_param_substs(scx,
-                                                           param_substs,
-                                                           &fn_substs);
-    assert!(concrete_substs.is_normalized_for_trans(),
-            "concrete_substs not normalized for trans: {:?}",
-            concrete_substs);
-    TransItem::Fn(Instance::new(def_id, concrete_substs))
+fn create_fn_trans_item<'a, 'tcx>(instance: Instance<'tcx>) -> TransItem<'tcx> {
+    debug!("create_fn_trans_item(instance={})", instance);
+    TransItem::Fn(instance)
 }
 
 /// Creates a `TransItem` for each method that is referenced by the vtable for
@@ -1102,8 +1034,6 @@ fn create_trans_items_for_vtable_methods<'a, 'tcx>(scx: &SharedCrateContext<'a,
     if let ty::TyDynamic(ref trait_ty, ..) = trait_ty.sty {
         if let Some(principal) = trait_ty.principal() {
             let poly_trait_ref = principal.with_self_ty(scx.tcx(), impl_ty);
-            let param_substs = scx.tcx().intern_substs(&[]);
-
             assert!(!poly_trait_ref.has_escaping_regions());
 
             // Walk all methods of the trait, including those of its supertraits
@@ -1111,19 +1041,18 @@ fn create_trans_items_for_vtable_methods<'a, 'tcx>(scx: &SharedCrateContext<'a,
             let methods = methods.filter_map(|method| method)
                 .filter_map(|(def_id, substs)| {
                     if let StaticDispatchResult::Dispatched {
-                        def_id,
-                        substs,
+                        instance,
                         // We already add the drop-glue for the closure env
                         // unconditionally below.
                         fn_once_adjustment: _ ,
-                    } = do_static_dispatch(scx, def_id, substs, param_substs) {
-                        Some((def_id, substs))
+                    } = do_static_dispatch(scx, def_id, substs) {
+                        Some(instance)
                     } else {
                         None
                     }
                 })
-                .filter(|&(def_id, _)| should_trans_locally(scx.tcx(), def_id))
-                .map(|(def_id, substs)| create_fn_trans_item(scx, def_id, substs, param_substs));
+                .filter(|&instance| should_trans_locally(scx.tcx(), &instance))
+                .map(|instance| create_fn_trans_item(instance));
             output.extend(methods);
         }
         // Also add the destructor
@@ -1195,7 +1124,7 @@ impl<'b, 'a, 'v> ItemLikeVisitor<'v> for RootCollector<'b, 'a, 'v> {
                     debug!("RootCollector: ItemFn({})",
                            def_id_to_string(self.scx.tcx(), def_id));
 
-                    let instance = Instance::mono(self.scx, def_id);
+                    let instance = Instance::mono(self.scx.tcx(), def_id);
                     self.output.push(TransItem::Fn(instance));
                 }
             }
@@ -1233,7 +1162,7 @@ impl<'b, 'a, 'v> ItemLikeVisitor<'v> for RootCollector<'b, 'a, 'v> {
                     debug!("RootCollector: MethodImplItem({})",
                            def_id_to_string(self.scx.tcx(), def_id));
 
-                    let instance = Instance::mono(self.scx, def_id);
+                    let instance = Instance::mono(self.scx.tcx(), def_id);
                     self.output.push(TransItem::Fn(instance));
                 }
             }
@@ -1278,31 +1207,22 @@ fn create_trans_items_for_default_impls<'a, 'tcx>(scx: &SharedCrateContext<'a, '
 
                     // The substitutions we have are on the impl, so we grab
                     // the method type from the impl to substitute into.
-                    let impl_substs = Substs::for_item(tcx, impl_def_id,
-                                                       |_, _| tcx.mk_region(ty::ReErased),
-                                                       |_, _| tcx.types.err);
+                    let impl_substs = tcx.empty_substs_for_def_id(impl_def_id);
                     let impl_data = traits::VtableImplData {
                         impl_def_id: impl_def_id,
                         substs: impl_substs,
                         nested: vec![]
                     };
-                    let (def_id, substs) = traits::find_method(tcx,
-                                                               method.name,
-                                                               callee_substs,
-                                                               &impl_data);
+                    let instance = find_method(tcx, method.name, callee_substs, &impl_data);
 
-                    let predicates = tcx.item_predicates(def_id).predicates
-                                        .subst(tcx, substs);
+                    let predicates = tcx.item_predicates(instance.def_id()).predicates
+                        .subst(tcx, impl_substs);
                     if !traits::normalize_and_test_predicates(tcx, predicates) {
                         continue;
                     }
 
-                    if should_trans_locally(tcx, method.def_id) {
-                        let item = create_fn_trans_item(scx,
-                                                        method.def_id,
-                                                        callee_substs,
-                                                        tcx.erase_regions(&substs));
-                        output.push(item);
+                    if should_trans_locally(tcx, &instance) {
+                        output.push(create_fn_trans_item(instance));
                     }
                 }
             }
@@ -1318,7 +1238,7 @@ fn collect_neighbours<'a, 'tcx>(scx: &SharedCrateContext<'a, 'tcx>,
                                 instance: Instance<'tcx>,
                                 output: &mut Vec<TransItem<'tcx>>)
 {
-    let mir = scx.tcx().item_mir(instance.def);
+    let mir = scx.tcx().instance_mir(instance.def);
 
     let mut visitor = MirNeighborCollector {
         scx: scx,
diff --git a/src/librustc_trans/common.rs b/src/librustc_trans/common.rs
index 0e536d58a56..4389207cdf2 100644
--- a/src/librustc_trans/common.rs
+++ b/src/librustc_trans/common.rs
@@ -602,7 +602,14 @@ pub fn ty_fn_sig<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
     }
 }
 
-pub fn requests_inline(tcx: TyCtxt, def_id: DefId) -> bool {
+pub fn requests_inline<'a, 'tcx>(
+    tcx: TyCtxt<'a, 'tcx, 'tcx>,
+    instance: &ty::Instance<'tcx>
+) -> bool {
+    let def_id = match instance.def {
+        ty::InstanceDef::Item(def_id) => def_id,
+        _ => return true
+    };
     match tcx.def_key(def_id).disambiguated_data.data {
         DefPathData::StructCtor |
         DefPathData::EnumVariant(..) |
@@ -610,7 +617,6 @@ pub fn requests_inline(tcx: TyCtxt, def_id: DefId) -> bool {
         _ => attr::requests_inline(&tcx.get_attrs(def_id)[..]),
     }
 }
-
 /// Given a DefId and some Substs, produces the monomorphic item type.
 pub fn def_ty<'a, 'tcx>(shared: &SharedCrateContext<'a, 'tcx>,
                         def_id: DefId,
@@ -620,3 +626,23 @@ pub fn def_ty<'a, 'tcx>(shared: &SharedCrateContext<'a, 'tcx>,
     let ty = shared.tcx().item_type(def_id);
     monomorphize::apply_param_substs(shared, substs, &ty)
 }
+
+/// Return the substituted type of an instance.
+pub fn instance_ty<'a, 'tcx>(shared: &SharedCrateContext<'a, 'tcx>,
+                             instance: &ty::Instance<'tcx>)
+                             -> Ty<'tcx>
+{
+    let ty = instance.def.def_ty(shared.tcx());
+    monomorphize::apply_param_substs(shared, instance.substs, &ty)
+}
+
+pub fn find_method<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                             name: ast::Name,
+                             substs: &'tcx Substs<'tcx>,
+                             impl_data: &traits::VtableImplData<'tcx, ()>)
+                             -> ty::Instance<'tcx>
+{
+    let (def_id, substs) = traits::find_method(tcx, name, substs, impl_data);
+    let substs = tcx.erase_regions(&substs);
+    ty::Instance::new(def_id, substs)
+}
diff --git a/src/librustc_trans/consts.rs b/src/librustc_trans/consts.rs
index bf1d9886ae7..0c3d211912a 100644
--- a/src/librustc_trans/consts.rs
+++ b/src/librustc_trans/consts.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 
+use back::symbol_names;
 use llvm;
 use llvm::{SetUnnamedAddr};
 use llvm::{ValueRef, True};
@@ -24,7 +25,6 @@ use monomorphize::Instance;
 use type_::Type;
 use type_of;
 use rustc::ty;
-use rustc::ty::subst::Substs;
 
 use rustc::hir;
 
@@ -80,12 +80,12 @@ pub fn addr_of(ccx: &CrateContext,
 }
 
 pub fn get_static(ccx: &CrateContext, def_id: DefId) -> ValueRef {
-    let instance = Instance::mono(ccx.shared(), def_id);
+    let instance = Instance::mono(ccx.tcx(), def_id);
     if let Some(&g) = ccx.instances().borrow().get(&instance) {
         return g;
     }
 
-    let ty = common::def_ty(ccx.shared(), def_id, Substs::empty());
+    let ty = common::instance_ty(ccx.shared(), &instance);
     let g = if let Some(id) = ccx.tcx().hir.as_local_node_id(def_id) {
 
         let llty = type_of::type_of(ccx, ty);
@@ -114,7 +114,7 @@ pub fn get_static(ccx: &CrateContext, def_id: DefId) -> ValueRef {
             hir_map::NodeForeignItem(&hir::ForeignItem {
                 ref attrs, span, node: hir::ForeignItemStatic(..), ..
             }) => {
-                let sym = instance.symbol_name(ccx.shared());
+                let sym = symbol_names::symbol_name(instance, ccx.shared());
                 let g = if let Some(name) =
                         attr::first_attr_value_str_by_name(&attrs, "linkage") {
                     // If this is a static with a linkage specified, then we need to handle
@@ -174,7 +174,7 @@ pub fn get_static(ccx: &CrateContext, def_id: DefId) -> ValueRef {
 
         g
     } else {
-        let sym = instance.symbol_name(ccx.shared());
+        let sym = symbol_names::symbol_name(instance, ccx.shared());
 
         // FIXME(nagisa): perhaps the map of externs could be offloaded to llvm somehow?
         // FIXME(nagisa): investigate whether it can be changed into define_global
@@ -235,7 +235,8 @@ pub fn trans_static<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
             v
         };
 
-        let ty = common::def_ty(ccx.shared(), def_id, Substs::empty());
+        let instance = Instance::mono(ccx.tcx(), def_id);
+        let ty = common::instance_ty(ccx.shared(), &instance);
         let llty = type_of::type_of(ccx, ty);
         let g = if val_llty == llty {
             g
diff --git a/src/librustc_trans/context.rs b/src/librustc_trans/context.rs
index 52851ea995d..b7381dd07dc 100644
--- a/src/librustc_trans/context.rs
+++ b/src/librustc_trans/context.rs
@@ -546,16 +546,6 @@ impl<'b, 'tcx> SharedCrateContext<'b, 'tcx> {
         &self.translation_items
     }
 
-    /// Given the def-id of some item that has no type parameters, make
-    /// a suitable "empty substs" for it.
-    pub fn empty_substs_for_def_id(&self, item_def_id: DefId) -> &'tcx Substs<'tcx> {
-        Substs::for_item(self.tcx(), item_def_id,
-                         |_, _| self.tcx().mk_region(ty::ReErased),
-                         |_, _| {
-            bug!("empty_substs_for_def_id: {:?} has type parameters", item_def_id)
-        })
-    }
-
     pub fn metadata_symbol_name(&self) -> String {
         format!("rust_metadata_{}_{}",
                 self.link_meta().crate_name,
@@ -886,7 +876,7 @@ impl<'b, 'tcx> CrateContext<'b, 'tcx> {
     /// Given the def-id of some item that has no type parameters, make
     /// a suitable "empty substs" for it.
     pub fn empty_substs_for_def_id(&self, item_def_id: DefId) -> &'tcx Substs<'tcx> {
-        self.shared().empty_substs_for_def_id(item_def_id)
+        self.tcx().empty_substs_for_def_id(item_def_id)
     }
 
     /// Generate a new symbol name with the given prefix. This symbol name must
diff --git a/src/librustc_trans/debuginfo/mod.rs b/src/librustc_trans/debuginfo/mod.rs
index 1d4aebf135b..8e86b50b3f7 100644
--- a/src/librustc_trans/debuginfo/mod.rs
+++ b/src/librustc_trans/debuginfo/mod.rs
@@ -205,7 +205,7 @@ pub fn create_function_debug_context<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
         return FunctionDebugContext::DebugInfoDisabled;
     }
 
-    for attr in cx.tcx().get_attrs(instance.def).iter() {
+    for attr in instance.def.attrs(cx.tcx()).iter() {
         if attr.check_name("no_debug") {
             return FunctionDebugContext::FunctionWithoutDebugInfo;
         }
@@ -229,11 +229,11 @@ pub fn create_function_debug_context<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
     };
 
     // Find the enclosing function, in case this is a closure.
-    let def_key = cx.tcx().def_key(instance.def);
+    let def_key = cx.tcx().def_key(instance.def_id());
     let mut name = def_key.disambiguated_data.data.to_string();
     let name_len = name.len();
 
-    let fn_def_id = cx.tcx().closure_base_def_id(instance.def);
+    let fn_def_id = cx.tcx().closure_base_def_id(instance.def_id());
 
     // Get_template_parameters() will append a `<...>` clause to the function
     // name if necessary.
@@ -246,11 +246,11 @@ pub fn create_function_debug_context<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
                                                       &mut name);
 
     // Build the linkage_name out of the item path and "template" parameters.
-    let linkage_name = mangled_name_of_item(cx, instance.def, &name[name_len..]);
+    let linkage_name = mangled_name_of_item(cx, instance.def_id(), &name[name_len..]);
 
     let scope_line = span_start(cx, span).line;
 
-    let local_id = cx.tcx().hir.as_local_node_id(instance.def);
+    let local_id = cx.tcx().hir.as_local_node_id(instance.def_id());
     let is_local_to_unit = local_id.map_or(false, |id| is_node_local_to_unit(cx, id));
 
     let function_name = CString::new(name).unwrap();
@@ -394,7 +394,7 @@ pub fn create_function_debug_context<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
         // First, let's see if this is a method within an inherent impl. Because
         // if yes, we want to make the result subroutine DIE a child of the
         // subroutine's self-type.
-        let self_type = cx.tcx().impl_of_method(instance.def).and_then(|impl_def_id| {
+        let self_type = cx.tcx().impl_of_method(instance.def_id()).and_then(|impl_def_id| {
             // If the method does *not* belong to a trait, proceed
             if cx.tcx().trait_id_of_impl(impl_def_id).is_none() {
                 let impl_self_ty =
@@ -417,9 +417,9 @@ pub fn create_function_debug_context<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 
         self_type.unwrap_or_else(|| {
             namespace::item_namespace(cx, DefId {
-                krate: instance.def.krate,
+                krate: instance.def_id().krate,
                 index: cx.tcx()
-                         .def_key(instance.def)
+                         .def_key(instance.def_id())
                          .parent
                          .expect("get_containing_scope: missing parent?")
             })
diff --git a/src/librustc_trans/meth.rs b/src/librustc_trans/meth.rs
index a3f4168e96f..bfd9f69a922 100644
--- a/src/librustc_trans/meth.rs
+++ b/src/librustc_trans/meth.rs
@@ -21,6 +21,7 @@ use machine;
 use monomorphize::Instance;
 use type_::Type;
 use type_of::*;
+use back::symbol_names;
 use value::Value;
 use rustc::ty;
 
@@ -70,7 +71,7 @@ pub fn trans_object_shim<'a, 'tcx>(ccx: &'a CrateContext<'a, 'tcx>,
     let function_name = match callee.ty.sty {
         ty::TyFnDef(def_id, substs, _) => {
             let instance = Instance::new(def_id, substs);
-            instance.symbol_name(ccx.shared())
+            symbol_names::symbol_name(instance, ccx.shared())
         }
         _ => bug!()
     };
diff --git a/src/librustc_trans/mir/constant.rs b/src/librustc_trans/mir/constant.rs
index b6fcc990344..deb1073cf9a 100644
--- a/src/librustc_trans/mir/constant.rs
+++ b/src/librustc_trans/mir/constant.rs
@@ -30,7 +30,7 @@ use common::{C_array, C_bool, C_bytes, C_floating_f64, C_integral, C_big_integra
 use common::{C_null, C_struct, C_str_slice, C_undef, C_uint, C_vector, is_undef};
 use common::const_to_opt_u128;
 use consts;
-use monomorphize::{self, Instance};
+use monomorphize;
 use type_of;
 use type_::Type;
 use value::Value;
@@ -245,11 +245,12 @@ impl<'a, 'tcx> MirConstContext<'a, 'tcx> {
     }
 
     fn trans_def(ccx: &'a CrateContext<'a, 'tcx>,
-                 instance: Instance<'tcx>,
+                 def_id: DefId,
+                 substs: &'tcx Substs<'tcx>,
                  args: IndexVec<mir::Local, Const<'tcx>>)
                  -> Result<Const<'tcx>, ConstEvalErr<'tcx>> {
-        let instance = instance.resolve_const(ccx.shared());
-        let mir = ccx.tcx().item_mir(instance.def);
+        let instance = monomorphize::resolve_const(ccx.shared(), def_id, substs);
+        let mir = ccx.tcx().instance_mir(instance.def);
         MirConstContext::new(ccx, &mir, instance.substs, args).trans()
     }
 
@@ -332,10 +333,8 @@ impl<'a, 'tcx> MirConstContext<'a, 'tcx> {
                 mir::TerminatorKind::Call { ref func, ref args, ref destination, .. } => {
                     let fn_ty = func.ty(self.mir, tcx);
                     let fn_ty = self.monomorphize(&fn_ty);
-                    let instance = match fn_ty.sty {
-                        ty::TyFnDef(def_id, substs, _) => {
-                            Instance::new(def_id, substs)
-                        }
+                    let (def_id, substs) = match fn_ty.sty {
+                        ty::TyFnDef(def_id, substs, _) => (def_id, substs),
                         _ => span_bug!(span, "calling {:?} (of type {}) in constant",
                                        func, fn_ty)
                     };
@@ -348,7 +347,7 @@ impl<'a, 'tcx> MirConstContext<'a, 'tcx> {
                         }
                     }
                     if let Some((ref dest, target)) = *destination {
-                        match MirConstContext::trans_def(self.ccx, instance, const_args) {
+                        match MirConstContext::trans_def(self.ccx, def_id, substs, const_args) {
                             Ok(value) => self.store(dest, value, span),
                             Err(err) => if failure.is_ok() { failure = Err(err); }
                         }
@@ -485,8 +484,7 @@ impl<'a, 'tcx> MirConstContext<'a, 'tcx> {
                         }
 
                         let substs = self.monomorphize(&substs);
-                        let instance = Instance::new(def_id, substs);
-                        MirConstContext::trans_def(self.ccx, instance, IndexVec::new())
+                        MirConstContext::trans_def(self.ccx, def_id, substs, IndexVec::new())
                     }
                     mir::Literal::Promoted { index } => {
                         let mir = &self.mir.promoted[index];
@@ -588,7 +586,8 @@ impl<'a, 'tcx> MirConstContext<'a, 'tcx> {
                                 // Now create its substs [Closure, Tuple]
                                 let input = tcx.closure_type(def_id)
                                     .subst(tcx, substs.substs).input(0);
-                                let substs = tcx.mk_substs([operand.ty, input.skip_binder()]
+                                let input = tcx.erase_late_bound_regions_and_normalize(&input);
+                                let substs = tcx.mk_substs([operand.ty, input]
                                     .iter().cloned().map(Kind::from));
                                 Callee::def(self.ccx, call_once, substs)
                                     .reify(self.ccx)
@@ -935,8 +934,7 @@ impl<'a, 'tcx> MirContext<'a, 'tcx> {
                 }
 
                 let substs = self.monomorphize(&substs);
-                let instance = Instance::new(def_id, substs);
-                MirConstContext::trans_def(bcx.ccx, instance, IndexVec::new())
+                MirConstContext::trans_def(bcx.ccx, def_id, substs, IndexVec::new())
             }
             mir::Literal::Promoted { index } => {
                 let mir = &self.mir.promoted[index];
@@ -964,8 +962,8 @@ pub fn trans_static_initializer<'a, 'tcx>(
     def_id: DefId)
     -> Result<ValueRef, ConstEvalErr<'tcx>>
 {
-    let instance = Instance::mono(ccx.shared(), def_id);
-    MirConstContext::trans_def(ccx, instance, IndexVec::new()).map(|c| c.llval)
+    MirConstContext::trans_def(ccx, def_id, Substs::empty(), IndexVec::new())
+        .map(|c| c.llval)
 }
 
 /// Construct a constant value, suitable for initializing a
diff --git a/src/librustc_trans/mir/rvalue.rs b/src/librustc_trans/mir/rvalue.rs
index b6af4e52e82..bbaf0f9d35f 100644
--- a/src/librustc_trans/mir/rvalue.rs
+++ b/src/librustc_trans/mir/rvalue.rs
@@ -203,7 +203,9 @@ impl<'a, 'tcx> MirContext<'a, 'tcx> {
                                 // Now create its substs [Closure, Tuple]
                                 let input = bcx.tcx().closure_type(def_id)
                                     .subst(bcx.tcx(), substs.substs).input(0);
-                                let substs = bcx.tcx().mk_substs([operand.ty, input.skip_binder()]
+                                let input =
+                                    bcx.tcx().erase_late_bound_regions_and_normalize(&input);
+                                let substs = bcx.tcx().mk_substs([operand.ty, input]
                                     .iter().cloned().map(Kind::from));
                                 OperandValue::Immediate(
                                     Callee::def(bcx.ccx, call_once, substs)
diff --git a/src/librustc_trans/monomorphize.rs b/src/librustc_trans/monomorphize.rs
index 4b31d5b7f88..3b746af275a 100644
--- a/src/librustc_trans/monomorphize.rs
+++ b/src/librustc_trans/monomorphize.rs
@@ -15,54 +15,31 @@ use rustc::traits;
 use rustc::ty::fold::{TypeFolder, TypeFoldable};
 use rustc::ty::subst::{Subst, Substs};
 use rustc::ty::{self, Ty, TyCtxt};
-use rustc::util::ppaux;
 use rustc::util::common::MemoizationMap;
 
 use syntax::codemap::DUMMY_SP;
 
-use std::fmt;
-
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
-pub struct Instance<'tcx> {
-    pub def: DefId,
-    pub substs: &'tcx Substs<'tcx>,
-}
-
-impl<'tcx> fmt::Display for Instance<'tcx> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        ppaux::parameterized(f, &self.substs, self.def, &[])
-    }
-}
-
-impl<'a, 'tcx> Instance<'tcx> {
-    pub fn new(def_id: DefId, substs: &'tcx Substs<'tcx>)
-               -> Instance<'tcx> {
-        assert!(substs.regions().all(|&r| r == ty::ReErased));
-        Instance { def: def_id, substs: substs }
-    }
-
-    pub fn mono(scx: &SharedCrateContext<'a, 'tcx>, def_id: DefId) -> Instance<'tcx> {
-        Instance::new(def_id, scx.empty_substs_for_def_id(def_id))
-    }
-
-    /// For associated constants from traits, return the impl definition.
-    pub fn resolve_const(&self, scx: &SharedCrateContext<'a, 'tcx>) -> Self {
-        if let Some(trait_id) = scx.tcx().trait_of_item(self.def) {
-            let trait_ref = ty::TraitRef::new(trait_id, self.substs);
-            let trait_ref = ty::Binder(trait_ref);
-            let vtable = fulfill_obligation(scx, DUMMY_SP, trait_ref);
-            if let traits::VtableImpl(vtable_impl) = vtable {
-                let name = scx.tcx().item_name(self.def);
-                let ac = scx.tcx().associated_items(vtable_impl.impl_def_id)
-                    .find(|item| item.kind == ty::AssociatedKind::Const && item.name == name);
-                if let Some(ac) = ac {
-                    return Instance::new(ac.def_id, vtable_impl.substs);
-                }
+pub use rustc::ty::Instance;
+
+/// For associated constants from traits, return the impl definition.
+pub fn resolve_const<'a, 'tcx>(
+    scx: &SharedCrateContext<'a, 'tcx>, def_id: DefId, substs: &'tcx Substs<'tcx>
+) -> Instance<'tcx> {
+    if let Some(trait_id) = scx.tcx().trait_of_item(def_id) {
+        let trait_ref = ty::TraitRef::new(trait_id, substs);
+        let trait_ref = ty::Binder(trait_ref);
+        let vtable = fulfill_obligation(scx, DUMMY_SP, trait_ref);
+        if let traits::VtableImpl(vtable_impl) = vtable {
+            let name = scx.tcx().item_name(def_id);
+            let ac = scx.tcx().associated_items(vtable_impl.impl_def_id)
+                .find(|item| item.kind == ty::AssociatedKind::Const && item.name == name);
+            if let Some(ac) = ac {
+                return Instance::new(ac.def_id, vtable_impl.substs);
             }
         }
-
-        *self
     }
+
+    Instance::new(def_id, substs)
 }
 
 /// Monomorphizes a type from the AST by first applying the in-scope
diff --git a/src/librustc_trans/partitioning.rs b/src/librustc_trans/partitioning.rs
index cc9fd8f46f6..1232c6cd28e 100644
--- a/src/librustc_trans/partitioning.rs
+++ b/src/librustc_trans/partitioning.rs
@@ -110,7 +110,7 @@ use rustc::dep_graph::{DepNode, WorkProductId};
 use rustc::hir::def_id::DefId;
 use rustc::hir::map::DefPathData;
 use rustc::session::config::NUMBERED_CODEGEN_UNIT_MARKER;
-use rustc::ty::TyCtxt;
+use rustc::ty::{self, TyCtxt};
 use rustc::ty::item_path::characteristic_def_id_of_type;
 use rustc_incremental::IchHasher;
 use std::cmp::Ordering;
@@ -186,7 +186,8 @@ impl<'tcx> CodegenUnit<'tcx> {
             symbol_name.hash(&mut state);
             let exported = match item {
                TransItem::Fn(ref instance) => {
-                    let node_id = scx.tcx().hir.as_local_node_id(instance.def);
+                   let node_id =
+                       scx.tcx().hir.as_local_node_id(instance.def_id());
                     node_id.map(|node_id| exported_symbols.contains(&node_id))
                            .unwrap_or(false)
                }
@@ -241,7 +242,7 @@ impl<'tcx> CodegenUnit<'tcx> {
         fn local_node_id(tcx: TyCtxt, trans_item: TransItem) -> Option<NodeId> {
             match trans_item {
                 TransItem::Fn(instance) => {
-                    tcx.hir.as_local_node_id(instance.def)
+                    tcx.hir.as_local_node_id(instance.def_id())
                 }
                 TransItem::Static(node_id) => Some(node_id),
                 TransItem::DropGlue(_) => None,
@@ -455,17 +456,22 @@ fn characteristic_def_id_of_trans_item<'a, 'tcx>(scx: &SharedCrateContext<'a, 't
     let tcx = scx.tcx();
     match trans_item {
         TransItem::Fn(instance) => {
+            let def_id = match instance.def {
+                ty::InstanceDef::Item(def_id) => def_id,
+                ty::InstanceDef::FnPtrShim(..) => return None
+            };
+
             // If this is a method, we want to put it into the same module as
             // its self-type. If the self-type does not provide a characteristic
             // DefId, we use the location of the impl after all.
 
-            if tcx.trait_of_item(instance.def).is_some() {
+            if tcx.trait_of_item(def_id).is_some() {
                 let self_ty = instance.substs.type_at(0);
                 // This is an implementation of a trait method.
-                return characteristic_def_id_of_type(self_ty).or(Some(instance.def));
+                return characteristic_def_id_of_type(self_ty).or(Some(def_id));
             }
 
-            if let Some(impl_def_id) = tcx.impl_of_method(instance.def) {
+            if let Some(impl_def_id) = tcx.impl_of_method(def_id) {
                 // This is a method within an inherent impl, find out what the
                 // self-type is:
                 let impl_self_ty = common::def_ty(scx, impl_def_id, instance.substs);
@@ -474,7 +480,7 @@ fn characteristic_def_id_of_trans_item<'a, 'tcx>(scx: &SharedCrateContext<'a, 't
                 }
             }
 
-            Some(instance.def)
+            Some(def_id)
         }
         TransItem::DropGlue(dg) => characteristic_def_id_of_type(dg.ty()),
         TransItem::Static(node_id) => Some(tcx.hir.local_def_id(node_id)),
diff --git a/src/librustc_trans/symbol_map.rs b/src/librustc_trans/symbol_map.rs
index 880c65937e3..cd285bfaa60 100644
--- a/src/librustc_trans/symbol_map.rs
+++ b/src/librustc_trans/symbol_map.rs
@@ -97,7 +97,7 @@ impl<'tcx> SymbolMap<'tcx> {
                               trans_item: TransItem<'tcx>) -> Option<Span> {
             match trans_item {
                 TransItem::Fn(Instance { def, .. }) => {
-                    tcx.hir.as_local_node_id(def)
+                    tcx.hir.as_local_node_id(def.def_id())
                 }
                 TransItem::Static(node_id) => Some(node_id),
                 TransItem::DropGlue(_) => None,
diff --git a/src/librustc_trans/symbol_names_test.rs b/src/librustc_trans/symbol_names_test.rs
index 02e1290b577..fe551b06b3d 100644
--- a/src/librustc_trans/symbol_names_test.rs
+++ b/src/librustc_trans/symbol_names_test.rs
@@ -14,6 +14,7 @@
 //! item-path. This is used for unit testing the code that generates
 //! paths etc in all kinds of annoying scenarios.
 
+use back::symbol_names;
 use rustc::hir;
 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
 use syntax::ast;
@@ -51,8 +52,8 @@ impl<'a, 'tcx> SymbolNamesTest<'a, 'tcx> {
         for attr in tcx.get_attrs(def_id).iter() {
             if attr.check_name(SYMBOL_NAME) {
                 // for now, can only use on monomorphic names
-                let instance = Instance::mono(self.scx, def_id);
-                let name = instance.symbol_name(self.scx);
+                let instance = Instance::mono(tcx, def_id);
+                let name = symbol_names::symbol_name(instance, self.scx);
                 tcx.sess.span_err(attr.span, &format!("symbol-name({})", name));
             } else if attr.check_name(ITEM_PATH) {
                 let path = tcx.item_path_str(def_id);
@@ -86,4 +87,3 @@ impl<'a, 'tcx> Visitor<'tcx> for SymbolNamesTest<'a, 'tcx> {
         intravisit::walk_impl_item(self, ii)
     }
 }
-
diff --git a/src/librustc_trans/trans_item.rs b/src/librustc_trans/trans_item.rs
index 5ec9c2a5995..13af081e0b6 100644
--- a/src/librustc_trans/trans_item.rs
+++ b/src/librustc_trans/trans_item.rs
@@ -96,7 +96,7 @@ impl<'a, 'tcx> TransItem<'tcx> {
             }
             TransItem::Fn(instance) => {
                 let _task = ccx.tcx().dep_graph.in_task(
-                    DepNode::TransCrateItem(instance.def)); // (*)
+                    DepNode::TransCrateItem(instance.def_id())); // (*)
 
                 base::trans_instance(&ccx, instance);
             }
@@ -147,7 +147,8 @@ impl<'a, 'tcx> TransItem<'tcx> {
                         linkage: llvm::Linkage,
                         symbol_name: &str) {
         let def_id = ccx.tcx().hir.local_def_id(node_id);
-        let ty = common::def_ty(ccx.shared(), def_id, Substs::empty());
+        let instance = Instance::mono(ccx.tcx(), def_id);
+        let ty = common::instance_ty(ccx.shared(), &instance);
         let llty = type_of::type_of(ccx, ty);
 
         let g = declare::define_global(ccx, symbol_name, llty).unwrap_or_else(|| {
@@ -157,7 +158,6 @@ impl<'a, 'tcx> TransItem<'tcx> {
 
         unsafe { llvm::LLVMRustSetLinkage(g, linkage) };
 
-        let instance = Instance::mono(ccx.shared(), def_id);
         ccx.instances().borrow_mut().insert(instance, g);
         ccx.statics().borrow_mut().insert(g, def_id);
     }
@@ -169,8 +169,8 @@ impl<'a, 'tcx> TransItem<'tcx> {
         assert!(!instance.substs.needs_infer() &&
                 !instance.substs.has_param_types());
 
-        let mono_ty = common::def_ty(ccx.shared(), instance.def, instance.substs);
-        let attrs = ccx.tcx().get_attrs(instance.def);
+        let mono_ty = common::instance_ty(ccx.shared(), &instance);
+        let attrs = instance.def.attrs(ccx.tcx());
         let lldecl = declare::declare_fn(ccx, symbol_name, mono_ty);
         unsafe { llvm::LLVMRustSetLinkage(lldecl, linkage) };
         base::set_link_section(ccx, lldecl, &attrs);
@@ -180,7 +180,7 @@ impl<'a, 'tcx> TransItem<'tcx> {
         }
 
         debug!("predefine_fn: mono_ty = {:?} instance = {:?}", mono_ty, instance);
-        match ccx.tcx().def_key(instance.def).disambiguated_data.data {
+        match ccx.tcx().def_key(instance.def_id()).disambiguated_data.data {
             DefPathData::StructCtor |
             DefPathData::EnumVariant(..) |
             DefPathData::ClosureExpr => {
@@ -229,10 +229,10 @@ impl<'a, 'tcx> TransItem<'tcx> {
     pub fn compute_symbol_name(&self,
                                scx: &SharedCrateContext<'a, 'tcx>) -> String {
         match *self {
-            TransItem::Fn(instance) => instance.symbol_name(scx),
+            TransItem::Fn(instance) => symbol_names::symbol_name(instance, scx),
             TransItem::Static(node_id) => {
                 let def_id = scx.tcx().hir.local_def_id(node_id);
-                Instance::mono(scx, def_id).symbol_name(scx)
+                symbol_names::symbol_name(Instance::mono(scx.tcx(), def_id), scx)
             }
             TransItem::DropGlue(dg) => {
                 let prefix = match dg {
@@ -244,21 +244,13 @@ impl<'a, 'tcx> TransItem<'tcx> {
         }
     }
 
-    pub fn is_from_extern_crate(&self) -> bool {
-        match *self {
-            TransItem::Fn(ref instance) => !instance.def.is_local(),
-            TransItem::DropGlue(..) |
-            TransItem::Static(..)   => false,
-        }
-    }
-
     pub fn instantiation_mode(&self,
                               tcx: TyCtxt<'a, 'tcx, 'tcx>)
                               -> InstantiationMode {
         match *self {
             TransItem::Fn(ref instance) => {
                 if self.explicit_linkage(tcx).is_none() &&
-                    common::requests_inline(tcx, instance.def)
+                    common::requests_inline(tcx, instance)
                 {
                     InstantiationMode::LocalCopy
                 } else {
@@ -282,7 +274,7 @@ impl<'a, 'tcx> TransItem<'tcx> {
 
     pub fn explicit_linkage(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Option<llvm::Linkage> {
         let def_id = match *self {
-            TransItem::Fn(ref instance) => instance.def,
+            TransItem::Fn(ref instance) => instance.def_id(),
             TransItem::Static(node_id) => tcx.hir.local_def_id(node_id),
             TransItem::DropGlue(..) => return None,
         };
@@ -587,7 +579,7 @@ impl<'a, 'tcx> DefPathBasedNames<'a, 'tcx> {
     pub fn push_instance_as_string(&self,
                                    instance: Instance<'tcx>,
                                    output: &mut String) {
-        self.push_def_path(instance.def, output);
+        self.push_def_path(instance.def_id(), output);
         self.push_type_params(instance.substs, iter::empty(), output);
     }
 }