Auto merge of #48611 - michaelwoerister:share-generics2, r=alexcrichton

Don't recompute SymbolExportLevel for upstream crates.

The data collected in #48373 suggests that we can avoid generating up to 30% of the LLVM definitions by only instantiating function monomorphizations once with a given crate graph. Some more data, collected with a [proof-of-concept implementation](https://github.com/michaelwoerister/rust/commits/share-generics) of re-using monomorphizations, which is less efficient than the MIR-only RLIB approach, suggests that it's still around 25% LLVM definitions that we can save.

So far, this PR only cleans up handling of symbol export status. Too early to review still.

26 files changed, 413 insertions, 271 deletions

diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 5f6a7c452c4..84fdeba4ab3 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -556,7 +556,7 @@ define_dep_nodes!( <'tcx>
     [] RvaluePromotableMap(DefId),
     [] ImplParent(DefId),
     [] TraitOfItem(DefId),
-    [] IsExportedSymbol(DefId),
+    [] IsReachableNonGeneric(DefId),
     [] IsMirAvailable(DefId),
     [] ItemAttrs(DefId),
     [] FnArgNames(DefId),
@@ -574,7 +574,7 @@ define_dep_nodes!( <'tcx>
     [] GetPanicStrategy(CrateNum),
     [] IsNoBuiltins(CrateNum),
     [] ImplDefaultness(DefId),
-    [] ExportedSymbolIds(CrateNum),
+    [] ReachableNonGenerics(CrateNum),
     [] NativeLibraries(CrateNum),
     [] PluginRegistrarFn(CrateNum),
     [] DeriveRegistrarFn(CrateNum),
diff --git a/src/librustc/middle/cstore.rs b/src/librustc/middle/cstore.rs
index bdb5ad525a7..5dbe2ef516c 100644
--- a/src/librustc/middle/cstore.rs
+++ b/src/librustc/middle/cstore.rs
@@ -32,7 +32,6 @@ use ich;
 use ty::{self, TyCtxt};
 use session::{Session, CrateDisambiguator};
 use session::search_paths::PathKind;
-use util::nodemap::NodeSet;
 
 use std::any::Any;
 use std::collections::BTreeMap;
@@ -258,8 +257,7 @@ pub trait CrateStore {
     // utility functions
     fn encode_metadata<'a, 'tcx>(&self,
                                  tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                                 link_meta: &LinkMeta,
-                                 reachable: &NodeSet)
+                                 link_meta: &LinkMeta)
                                  -> EncodedMetadata;
     fn metadata_encoding_version(&self) -> &[u8];
 }
@@ -342,8 +340,7 @@ impl CrateStore for DummyCrateStore {
     fn extern_mod_stmt_cnum_untracked(&self, emod_id: ast::NodeId) -> Option<CrateNum> { None }
     fn encode_metadata<'a, 'tcx>(&self,
                                  tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                                 link_meta: &LinkMeta,
-                                 reachable: &NodeSet)
+                                 link_meta: &LinkMeta)
                                  -> EncodedMetadata {
         bug!("encode_metadata")
     }
diff --git a/src/librustc/middle/exported_symbols.rs b/src/librustc/middle/exported_symbols.rs
index d650dbe88b5..b1418792490 100644
--- a/src/librustc/middle/exported_symbols.rs
+++ b/src/librustc/middle/exported_symbols.rs
@@ -8,12 +8,16 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use hir::def_id::{DefId, LOCAL_CRATE};
+use std::cmp;
+use ty;
+
 /// The SymbolExportLevel of a symbols specifies from which kinds of crates
 /// the symbol will be exported. `C` symbols will be exported from any
 /// kind of crate, including cdylibs which export very few things.
 /// `Rust` will only be exported if the crate produced is a Rust
 /// dylib.
-#[derive(Eq, PartialEq, Debug, Copy, Clone)]
+#[derive(Eq, PartialEq, Debug, Copy, Clone, RustcEncodable, RustcDecodable)]
 pub enum SymbolExportLevel {
     C,
     Rust,
@@ -34,3 +38,58 @@ impl SymbolExportLevel {
         }
     }
 }
+
+#[derive(Eq, PartialEq, Debug, Copy, Clone, RustcEncodable, RustcDecodable)]
+pub enum ExportedSymbol {
+    NonGeneric(DefId),
+    NoDefId(ty::SymbolName),
+}
+
+impl ExportedSymbol {
+    pub fn symbol_name(&self, tcx: ty::TyCtxt) -> ty::SymbolName {
+        match *self {
+            ExportedSymbol::NonGeneric(def_id) => {
+                tcx.symbol_name(ty::Instance::mono(tcx, def_id))
+            }
+            ExportedSymbol::NoDefId(symbol_name) => {
+                symbol_name
+            }
+        }
+    }
+
+    pub fn compare_stable(&self, tcx: ty::TyCtxt, other: &ExportedSymbol) -> cmp::Ordering {
+        match *self {
+            ExportedSymbol::NonGeneric(self_def_id) => {
+                match *other {
+                    ExportedSymbol::NonGeneric(other_def_id) => {
+                        tcx.def_path_hash(self_def_id).cmp(&tcx.def_path_hash(other_def_id))
+                    }
+                    ExportedSymbol::NoDefId(_) => {
+                        cmp::Ordering::Less
+                    }
+                }
+            }
+            ExportedSymbol::NoDefId(self_symbol_name) => {
+                match *other {
+                    ExportedSymbol::NonGeneric(_) => {
+                        cmp::Ordering::Greater
+                    }
+                    ExportedSymbol::NoDefId(ref other_symbol_name) => {
+                        self_symbol_name.cmp(other_symbol_name)
+                    }
+                }
+            }
+        }
+    }
+}
+
+impl_stable_hash_for!(enum self::ExportedSymbol {
+    NonGeneric(def_id),
+    NoDefId(symbol_name)
+});
+
+pub fn metadata_symbol_name(tcx: ty::TyCtxt) -> String {
+    format!("rust_metadata_{}_{}",
+            tcx.original_crate_name(LOCAL_CRATE),
+            tcx.crate_disambiguator(LOCAL_CRATE).to_fingerprint().to_hex())
+}
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index a7f065d57ae..47a3580e867 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -46,7 +46,7 @@ use ty::layout::{LayoutDetails, TargetDataLayout};
 use ty::maps;
 use ty::steal::Steal;
 use ty::BindingMode;
-use util::nodemap::{NodeMap, NodeSet, DefIdSet, ItemLocalMap};
+use util::nodemap::{NodeMap, DefIdSet, ItemLocalMap};
 use util::nodemap::{FxHashMap, FxHashSet};
 use rustc_data_structures::accumulate_vec::AccumulateVec;
 use rustc_data_structures::stable_hasher::{HashStable, hash_stable_hashmap,
@@ -1417,10 +1417,10 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 }
 
 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
-    pub fn encode_metadata(self, link_meta: &LinkMeta, reachable: &NodeSet)
+    pub fn encode_metadata(self, link_meta: &LinkMeta)
         -> EncodedMetadata
     {
-        self.cstore.encode_metadata(self, link_meta, reachable)
+        self.cstore.encode_metadata(self, link_meta)
     }
 }
 
@@ -2460,4 +2460,12 @@ pub fn provide(providers: &mut ty::maps::Providers) {
         assert_eq!(cnum, LOCAL_CRATE);
         Lrc::new(tcx.sess.features_untracked().clone())
     };
+    providers.is_panic_runtime = |tcx, cnum| {
+        assert_eq!(cnum, LOCAL_CRATE);
+        attr::contains_name(tcx.hir.krate_attrs(), "panic_runtime")
+    };
+    providers.is_compiler_builtins = |tcx, cnum| {
+        assert_eq!(cnum, LOCAL_CRATE);
+        attr::contains_name(tcx.hir.krate_attrs(), "compiler_builtins")
+    };
 }
diff --git a/src/librustc/ty/maps/config.rs b/src/librustc/ty/maps/config.rs
index c91b30440e5..cfc552bdc85 100644
--- a/src/librustc/ty/maps/config.rs
+++ b/src/librustc/ty/maps/config.rs
@@ -212,9 +212,9 @@ impl<'tcx> QueryDescription<'tcx> for queries::item_attrs<'tcx> {
     }
 }
 
-impl<'tcx> QueryDescription<'tcx> for queries::is_exported_symbol<'tcx> {
+impl<'tcx> QueryDescription<'tcx> for queries::is_reachable_non_generic<'tcx> {
     fn describe(_: TyCtxt, _: DefId) -> String {
-        bug!("is_exported_symbol")
+        bug!("is_reachable_non_generic")
     }
 }
 
@@ -383,7 +383,7 @@ impl<'tcx> QueryDescription<'tcx> for queries::is_sanitizer_runtime<'tcx> {
     }
 }
 
-impl<'tcx> QueryDescription<'tcx> for queries::exported_symbol_ids<'tcx> {
+impl<'tcx> QueryDescription<'tcx> for queries::reachable_non_generics<'tcx> {
     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
         format!("looking up the exported symbols of a crate")
     }
diff --git a/src/librustc/ty/maps/mod.rs b/src/librustc/ty/maps/mod.rs
index c211713db6b..2ef97b2673d 100644
--- a/src/librustc/ty/maps/mod.rs
+++ b/src/librustc/ty/maps/mod.rs
@@ -26,7 +26,7 @@ use middle::region;
 use middle::resolve_lifetime::{ResolveLifetimes, Region, ObjectLifetimeDefault};
 use middle::stability::{self, DeprecationEntry};
 use middle::lang_items::{LanguageItems, LangItem};
-use middle::exported_symbols::SymbolExportLevel;
+use middle::exported_symbols::{SymbolExportLevel, ExportedSymbol};
 use mir::mono::{CodegenUnit, Stats};
 use mir;
 use session::{CompileResult, CrateDisambiguator};
@@ -238,7 +238,6 @@ define_maps! { <'tcx>
     [] fn fn_arg_names: FnArgNames(DefId) -> Vec<ast::Name>,
     [] fn impl_parent: ImplParent(DefId) -> Option<DefId>,
     [] fn trait_of_item: TraitOfItem(DefId) -> Option<DefId>,
-    [] fn is_exported_symbol: IsExportedSymbol(DefId) -> bool,
     [] fn item_body_nested_bodies: ItemBodyNestedBodies(DefId) -> ExternBodyNestedBodies,
     [] fn const_is_rvalue_promotable_to_static: ConstIsRvaluePromotableToStatic(DefId) -> bool,
     [] fn rvalue_promotable_map: RvaluePromotableMap(DefId) -> Lrc<ItemLocalSet>,
@@ -290,7 +289,23 @@ define_maps! { <'tcx>
     [] fn lint_levels: lint_levels_node(CrateNum) -> Lrc<lint::LintLevelMap>,
 
     [] fn impl_defaultness: ImplDefaultness(DefId) -> hir::Defaultness,
-    [] fn exported_symbol_ids: ExportedSymbolIds(CrateNum) -> Lrc<DefIdSet>,
+
+    // The DefIds of all non-generic functions and statics in the given crate
+    // that can be reached from outside the crate.
+    //
+    // We expect this items to be available for being linked to.
+    //
+    // This query can also be called for LOCAL_CRATE. In this case it will
+    // compute which items will be reachable to other crates, taking into account
+    // the kind of crate that is currently compiled. Crates with only a
+    // C interface have fewer reachable things.
+    //
+    // Does not include external symbols that don't have a corresponding DefId,
+    // like the compiler-generated `main` function and so on.
+    [] fn reachable_non_generics: ReachableNonGenerics(CrateNum) -> Lrc<DefIdSet>,
+    [] fn is_reachable_non_generic: IsReachableNonGeneric(DefId) -> bool,
+
+
     [] fn native_libraries: NativeLibraries(CrateNum) -> Lrc<Vec<NativeLibrary>>,
     [] fn plugin_registrar_fn: PluginRegistrarFn(CrateNum) -> Option<DefId>,
     [] fn derive_registrar_fn: DeriveRegistrarFn(CrateNum) -> Option<DefId>,
@@ -343,7 +358,7 @@ define_maps! { <'tcx>
     [] fn all_crate_nums: all_crate_nums_node(CrateNum) -> Lrc<Vec<CrateNum>>,
 
     [] fn exported_symbols: ExportedSymbols(CrateNum)
-        -> Arc<Vec<(String, Option<DefId>, SymbolExportLevel)>>,
+        -> Arc<Vec<(ExportedSymbol, SymbolExportLevel)>>,
     [] fn collect_and_partition_translation_items:
         collect_and_partition_translation_items_node(CrateNum)
         -> (Arc<DefIdSet>, Arc<Vec<Arc<CodegenUnit<'tcx>>>>),
diff --git a/src/librustc/ty/maps/plumbing.rs b/src/librustc/ty/maps/plumbing.rs
index 3443b9b61b2..13f286d6a26 100644
--- a/src/librustc/ty/maps/plumbing.rs
+++ b/src/librustc/ty/maps/plumbing.rs
@@ -851,7 +851,7 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
         DepKind::RvaluePromotableMap => { force!(rvalue_promotable_map, def_id!()); }
         DepKind::ImplParent => { force!(impl_parent, def_id!()); }
         DepKind::TraitOfItem => { force!(trait_of_item, def_id!()); }
-        DepKind::IsExportedSymbol => { force!(is_exported_symbol, def_id!()); }
+        DepKind::IsReachableNonGeneric => { force!(is_reachable_non_generic, def_id!()); }
         DepKind::IsMirAvailable => { force!(is_mir_available, def_id!()); }
         DepKind::ItemAttrs => { force!(item_attrs, def_id!()); }
         DepKind::FnArgNames => { force!(fn_arg_names, def_id!()); }
@@ -868,7 +868,7 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
         DepKind::GetPanicStrategy => { force!(panic_strategy, krate!()); }
         DepKind::IsNoBuiltins => { force!(is_no_builtins, krate!()); }
         DepKind::ImplDefaultness => { force!(impl_defaultness, def_id!()); }
-        DepKind::ExportedSymbolIds => { force!(exported_symbol_ids, krate!()); }
+        DepKind::ReachableNonGenerics => { force!(reachable_non_generics, krate!()); }
         DepKind::NativeLibraries => { force!(native_libraries, krate!()); }
         DepKind::PluginRegistrarFn => { force!(plugin_registrar_fn, krate!()); }
         DepKind::DeriveRegistrarFn => { force!(derive_registrar_fn, krate!()); }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index f6f4e1ceb15..a7c55880e2e 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -2806,7 +2806,7 @@ impl<'tcx> DtorckConstraint<'tcx> {
     }
 }
 
-#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, RustcEncodable, RustcDecodable)]
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, RustcEncodable, RustcDecodable)]
 pub struct SymbolName {
     // FIXME: we don't rely on interning or equality here - better have
     // this be a `&'tcx str`.
@@ -2817,6 +2817,14 @@ impl_stable_hash_for!(struct self::SymbolName {
     name
 });
 
+impl SymbolName {
+    pub fn new(name: &str) -> SymbolName {
+        SymbolName {
+            name: Symbol::intern(name).as_str()
+        }
+    }
+}
+
 impl Deref for SymbolName {
     type Target = str;
 
@@ -2828,3 +2836,9 @@ impl fmt::Display for SymbolName {
         fmt::Display::fmt(&self.name, fmt)
     }
 }
+
+impl fmt::Debug for SymbolName {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Display::fmt(&self.name, fmt)
+    }
+}
diff --git a/src/librustc_metadata/creader.rs b/src/librustc_metadata/creader.rs
index 876e7e8dc31..789ecd0f613 100644
--- a/src/librustc_metadata/creader.rs
+++ b/src/librustc_metadata/creader.rs
@@ -225,9 +225,6 @@ impl<'a> CrateLoader<'a> {
             crate_root.def_path_table.decode((&metadata, self.sess))
         });
 
-        let exported_symbols = crate_root.exported_symbols
-                                         .decode((&metadata, self.sess))
-                                         .collect();
         let trait_impls = crate_root
             .impls
             .decode((&metadata, self.sess))
@@ -238,7 +235,6 @@ impl<'a> CrateLoader<'a> {
             name,
             extern_crate: Cell::new(None),
             def_path_table: Lrc::new(def_path_table),
-            exported_symbols,
             trait_impls,
             proc_macros: crate_root.macro_derive_registrar.map(|_| {
                 self.load_derive_macros(&crate_root, dylib.clone().map(|p| p.0), span)
diff --git a/src/librustc_metadata/cstore.rs b/src/librustc_metadata/cstore.rs
index 8b59eec0190..2e95c23b4ae 100644
--- a/src/librustc_metadata/cstore.rs
+++ b/src/librustc_metadata/cstore.rs
@@ -78,8 +78,6 @@ pub struct CrateMetadata {
     /// compilation support.
     pub def_path_table: Lrc<DefPathTable>,
 
-    pub exported_symbols: FxHashSet<DefIndex>,
-
     pub trait_impls: FxHashMap<(u32, DefIndex), schema::LazySeq<DefIndex>>,
 
     pub dep_kind: Cell<DepKind>,
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index 7b8194d9eab..0b50f5c4496 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -18,6 +18,7 @@ use rustc::ty::maps::QueryConfig;
 use rustc::middle::cstore::{CrateStore, DepKind,
                             MetadataLoader, LinkMeta,
                             LoadedMacro, EncodedMetadata, NativeLibraryKind};
+use rustc::middle::exported_symbols::ExportedSymbol;
 use rustc::middle::stability::DeprecationEntry;
 use rustc::hir::def;
 use rustc::session::{CrateDisambiguator, Session};
@@ -27,10 +28,11 @@ use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE, CRATE_DEF_INDEX};
 use rustc::hir::map::{DefKey, DefPath, DefPathHash};
 use rustc::hir::map::blocks::FnLikeNode;
 use rustc::hir::map::definitions::DefPathTable;
-use rustc::util::nodemap::{NodeSet, DefIdMap};
+use rustc::util::nodemap::DefIdMap;
 
 use std::any::Any;
 use rustc_data_structures::sync::Lrc;
+use std::sync::Arc;
 
 use syntax::ast;
 use syntax::attr;
@@ -160,9 +162,6 @@ provide! { <'tcx> tcx, def_id, other, cdata,
     fn_arg_names => { cdata.get_fn_arg_names(def_id.index) }
     impl_parent => { cdata.get_parent_impl(def_id.index) }
     trait_of_item => { cdata.get_trait_of_item(def_id.index) }
-    is_exported_symbol => {
-        cdata.exported_symbols.contains(&def_id.index)
-    }
     item_body_nested_bodies => { cdata.item_body_nested_bodies(def_id.index) }
     const_is_rvalue_promotable_to_static => {
         cdata.const_is_rvalue_promotable_to_static(def_id.index)
@@ -179,7 +178,21 @@ provide! { <'tcx> tcx, def_id, other, cdata,
     extern_crate => { Lrc::new(cdata.extern_crate.get()) }
     is_no_builtins => { cdata.is_no_builtins(tcx.sess) }
     impl_defaultness => { cdata.get_impl_defaultness(def_id.index) }
-    exported_symbol_ids => { Lrc::new(cdata.get_exported_symbols()) }
+    reachable_non_generics => {
+        let reachable_non_generics = tcx
+            .exported_symbols(cdata.cnum)
+            .iter()
+            .filter_map(|&(exported_symbol, _)| {
+                if let ExportedSymbol::NonGeneric(def_id) = exported_symbol {
+                    return Some(def_id)
+                } else {
+                    None
+                }
+            })
+            .collect();
+
+        Lrc::new(reachable_non_generics)
+    }
     native_libraries => { Lrc::new(cdata.get_native_libraries(tcx.sess)) }
     plugin_registrar_fn => {
         cdata.root.plugin_registrar_fn.map(|index| {
@@ -238,6 +251,19 @@ provide! { <'tcx> tcx, def_id, other, cdata,
 
     has_copy_closures => { cdata.has_copy_closures(tcx.sess) }
     has_clone_closures => { cdata.has_clone_closures(tcx.sess) }
+
+    exported_symbols => {
+        let cnum = cdata.cnum;
+        assert!(cnum != LOCAL_CRATE);
+
+        // If this crate is a custom derive crate, then we're not even going to
+        // link those in so we skip those crates.
+        if cdata.root.macro_derive_registrar.is_some() {
+            return Arc::new(Vec::new())
+        }
+
+        Arc::new(cdata.exported_symbols())
+    }
 }
 
 pub fn provide<'tcx>(providers: &mut Providers<'tcx>) {
@@ -520,11 +546,10 @@ impl CrateStore for cstore::CStore {
 
     fn encode_metadata<'a, 'tcx>(&self,
                                  tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                                 link_meta: &LinkMeta,
-                                 reachable: &NodeSet)
+                                 link_meta: &LinkMeta)
                                  -> EncodedMetadata
     {
-        encoder::encode_metadata(tcx, link_meta, reachable)
+        encoder::encode_metadata(tcx, link_meta)
     }
 
     fn metadata_encoding_version(&self) -> &[u8]
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index 0c6a286e227..60a0d4e03b5 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -18,6 +18,7 @@ use rustc::hir::map::{DefKey, DefPath, DefPathData, DefPathHash};
 use rustc::hir;
 use rustc::middle::cstore::{LinkagePreference, ExternConstBody,
                             ExternBodyNestedBodies};
+use rustc::middle::exported_symbols::{ExportedSymbol, SymbolExportLevel};
 use rustc::hir::def::{self, Def, CtorKind};
 use rustc::hir::def_id::{CrateNum, DefId, DefIndex,
                          CRATE_DEF_INDEX, LOCAL_CRATE};
@@ -27,7 +28,6 @@ use rustc::mir;
 use rustc::session::Session;
 use rustc::ty::{self, Ty, TyCtxt};
 use rustc::ty::codec::TyDecoder;
-use rustc::util::nodemap::DefIdSet;
 use rustc::mir::Mir;
 
 use std::cell::Ref;
@@ -1006,10 +1006,10 @@ impl<'a, 'tcx> CrateMetadata {
         arg_names.decode(self).collect()
     }
 
-    pub fn get_exported_symbols(&self) -> DefIdSet {
-        self.exported_symbols
-            .iter()
-            .map(|&index| self.local_def_id(index))
+    pub fn exported_symbols(&self) -> Vec<(ExportedSymbol, SymbolExportLevel)> {
+        self.root
+            .exported_symbols
+            .decode(self)
             .collect()
     }
 
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index d3f046c5544..d19ab894591 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -20,14 +20,16 @@ use rustc::hir::def_id::{CrateNum, CRATE_DEF_INDEX, DefIndex, DefId, LOCAL_CRATE
 use rustc::hir::map::definitions::DefPathTable;
 use rustc::ich::Fingerprint;
 use rustc::middle::dependency_format::Linkage;
+use rustc::middle::exported_symbols::{ExportedSymbol, SymbolExportLevel,
+                                      metadata_symbol_name};
 use rustc::middle::lang_items;
 use rustc::mir;
 use rustc::traits::specialization_graph;
-use rustc::ty::{self, Ty, TyCtxt, ReprOptions};
+use rustc::ty::{self, Ty, TyCtxt, ReprOptions, SymbolName};
 use rustc::ty::codec::{self as ty_codec, TyEncoder};
 
 use rustc::session::config::{self, CrateTypeProcMacro};
-use rustc::util::nodemap::{FxHashMap, NodeSet};
+use rustc::util::nodemap::FxHashMap;
 
 use rustc_data_structures::stable_hasher::StableHasher;
 use rustc_serialize::{Encodable, Encoder, SpecializedEncoder, opaque};
@@ -53,7 +55,6 @@ pub struct EncodeContext<'a, 'tcx: 'a> {
     opaque: opaque::Encoder<'a>,
     pub tcx: TyCtxt<'a, 'tcx, 'tcx>,
     link_meta: &'a LinkMeta,
-    exported_symbols: &'a NodeSet,
 
     lazy_state: LazyState,
     type_shorthands: FxHashMap<Ty<'tcx>, usize>,
@@ -395,9 +396,10 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
 
         // Encode exported symbols info.
         i = self.position();
+        let exported_symbols = self.tcx.exported_symbols(LOCAL_CRATE);
         let exported_symbols = self.tracked(
             IsolatedEncoder::encode_exported_symbols,
-            self.exported_symbols);
+            &exported_symbols);
         let exported_symbols_bytes = self.position() - i;
 
         // Encode and index the items.
@@ -1388,9 +1390,25 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> {
     // middle::reachable module but filters out items that either don't have a
     // symbol associated with them (they weren't translated) or if they're an FFI
     // definition (as that's not defined in this crate).
-    fn encode_exported_symbols(&mut self, exported_symbols: &NodeSet) -> LazySeq<DefIndex> {
-        let tcx = self.tcx;
-        self.lazy_seq(exported_symbols.iter().map(|&id| tcx.hir.local_def_id(id).index))
+    fn encode_exported_symbols(&mut self,
+                               exported_symbols: &[(ExportedSymbol, SymbolExportLevel)])
+                               -> LazySeq<(ExportedSymbol, SymbolExportLevel)> {
+
+        // The metadata symbol name is special. It should not show up in
+        // downstream crates.
+        let metadata_symbol_name = SymbolName::new(&metadata_symbol_name(self.tcx));
+
+        self.lazy_seq(exported_symbols
+            .iter()
+            .filter(|&&(ref exported_symbol, _)| {
+                match *exported_symbol {
+                    ExportedSymbol::NoDefId(symbol_name) => {
+                        symbol_name != metadata_symbol_name
+                    },
+                    _ => true,
+                }
+            })
+            .cloned())
     }
 
     fn encode_dylib_dependency_formats(&mut self, _: ()) -> LazySeq<Option<LinkagePreference>> {
@@ -1663,8 +1681,7 @@ impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ImplVisitor<'a, 'tcx> {
 // generated regardless of trailing bytes that end up in it.
 
 pub fn encode_metadata<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
-                                 link_meta: &LinkMeta,
-                                 exported_symbols: &NodeSet)
+                                 link_meta: &LinkMeta)
                                  -> EncodedMetadata
 {
     let mut cursor = Cursor::new(vec![]);
@@ -1678,7 +1695,6 @@ pub fn encode_metadata<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             opaque: opaque::Encoder::new(&mut cursor),
             tcx,
             link_meta,
-            exported_symbols,
             lazy_state: LazyState::NoNode,
             type_shorthands: Default::default(),
             predicate_shorthands: Default::default(),
diff --git a/src/librustc_metadata/schema.rs b/src/librustc_metadata/schema.rs
index c542f65dcec..ce94e4f912f 100644
--- a/src/librustc_metadata/schema.rs
+++ b/src/librustc_metadata/schema.rs
@@ -16,6 +16,7 @@ use rustc::hir::def::{self, CtorKind};
 use rustc::hir::def_id::{DefIndex, DefId, CrateNum};
 use rustc::ich::StableHashingContext;
 use rustc::middle::cstore::{DepKind, LinkagePreference, NativeLibrary};
+use rustc::middle::exported_symbols::{ExportedSymbol, SymbolExportLevel};
 use rustc::middle::lang_items;
 use rustc::mir;
 use rustc::session::CrateDisambiguator;
@@ -202,7 +203,8 @@ pub struct CrateRoot {
     pub codemap: LazySeq<syntax_pos::FileMap>,
     pub def_path_table: Lazy<hir::map::definitions::DefPathTable>,
     pub impls: LazySeq<TraitImpls>,
-    pub exported_symbols: LazySeq<DefIndex>,
+    pub exported_symbols: LazySeq<(ExportedSymbol, SymbolExportLevel)>,
+
     pub index: LazySeq<index::Index>,
 }
 
diff --git a/src/librustc_mir/monomorphize/collector.rs b/src/librustc_mir/monomorphize/collector.rs
index eb4ba21489c..10c2f9f758f 100644
--- a/src/librustc_mir/monomorphize/collector.rs
+++ b/src/librustc_mir/monomorphize/collector.rs
@@ -736,7 +736,7 @@ fn should_monomorphize_locally<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, instance:
         }
         Some(_) => true,
         None => {
-            if tcx.is_exported_symbol(def_id) ||
+            if tcx.is_reachable_non_generic(def_id) ||
                 tcx.is_foreign_item(def_id)
             {
                 // We can link to the item in question, no instance needed
@@ -984,7 +984,7 @@ impl<'b, 'a, 'v> RootCollector<'b, 'a, 'v> {
             }
             MonoItemCollectionMode::Lazy => {
                 self.entry_fn == Some(def_id) ||
-                self.tcx.is_exported_symbol(def_id) ||
+                self.tcx.is_reachable_non_generic(def_id) ||
                 attr::contains_name(&self.tcx.get_attrs(def_id),
                                     "rustc_std_internal_symbol")
             }
diff --git a/src/librustc_mir/monomorphize/partitioning.rs b/src/librustc_mir/monomorphize/partitioning.rs
index 2b558e71483..d65c1e03298 100644
--- a/src/librustc_mir/monomorphize/partitioning.rs
+++ b/src/librustc_mir/monomorphize/partitioning.rs
@@ -363,7 +363,7 @@ fn place_root_translation_items<'a, 'tcx, I>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                     can_be_internalized = false;
                                     Visibility::Hidden
                                 } else if def_id.is_local() {
-                                    if tcx.is_exported_symbol(def_id) {
+                                    if tcx.is_reachable_non_generic(def_id) {
                                         can_be_internalized = false;
                                         default_visibility(def_id)
                                     } else {
@@ -385,7 +385,7 @@ fn place_root_translation_items<'a, 'tcx, I>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                         (Linkage::External, visibility)
                     }
                     MonoItem::Static(def_id) => {
-                        let visibility = if tcx.is_exported_symbol(def_id) {
+                        let visibility = if tcx.is_reachable_non_generic(def_id) {
                             can_be_internalized = false;
                             default_visibility(def_id)
                         } else {
@@ -395,7 +395,7 @@ fn place_root_translation_items<'a, 'tcx, I>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                     }
                     MonoItem::GlobalAsm(node_id) => {
                         let def_id = tcx.hir.local_def_id(node_id);
-                        let visibility = if tcx.is_exported_symbol(def_id) {
+                        let visibility = if tcx.is_reachable_non_generic(def_id) {
                             can_be_internalized = false;
                             default_visibility(def_id)
                         } else {
diff --git a/src/librustc_trans/back/linker.rs b/src/librustc_trans/back/linker.rs
index a3ff39a47a2..3fe667f1543 100644
--- a/src/librustc_trans/back/linker.rs
+++ b/src/librustc_trans/back/linker.rs
@@ -768,9 +768,9 @@ fn exported_symbols(tcx: TyCtxt, crate_type: CrateType) -> Vec<String> {
     let mut symbols = Vec::new();
 
     let export_threshold = symbol_export::crates_export_threshold(&[crate_type]);
-    for &(ref name, _, level) in tcx.exported_symbols(LOCAL_CRATE).iter() {
+    for &(symbol, level) in tcx.exported_symbols(LOCAL_CRATE).iter() {
         if level.is_below_threshold(export_threshold) {
-            symbols.push(name.clone());
+            symbols.push(symbol.symbol_name(tcx).to_string());
         }
     }
 
@@ -782,9 +782,9 @@ fn exported_symbols(tcx: TyCtxt, crate_type: CrateType) -> Vec<String> {
         // For each dependency that we are linking to statically ...
         if *dep_format == Linkage::Static {
             // ... we add its symbol list to our export list.
-            for &(ref name, _, level) in tcx.exported_symbols(cnum).iter() {
+            for &(symbol, level) in tcx.exported_symbols(cnum).iter() {
                 if level.is_below_threshold(export_threshold) {
-                    symbols.push(name.clone());
+                    symbols.push(symbol.symbol_name(tcx).to_string());
                 }
             }
         }
diff --git a/src/librustc_trans/back/lto.rs b/src/librustc_trans/back/lto.rs
index 3f9e9191cf0..f79651cef3e 100644
--- a/src/librustc_trans/back/lto.rs
+++ b/src/librustc_trans/back/lto.rs
@@ -113,7 +113,7 @@ pub(crate) fn run(cgcx: &CodegenContext,
         Lto::No => panic!("didn't request LTO but we're doing LTO"),
     };
 
-    let symbol_filter = &|&(ref name, _, level): &(String, _, SymbolExportLevel)| {
+    let symbol_filter = &|&(ref name, level): &(String, SymbolExportLevel)| {
         if level.is_below_threshold(export_threshold) {
             let mut bytes = Vec::with_capacity(name.len() + 1);
             bytes.extend(name.bytes());
diff --git a/src/librustc_trans/back/symbol_export.rs b/src/librustc_trans/back/symbol_export.rs
index 55ef4e7ed3a..739ae768ca2 100644
--- a/src/librustc_trans/back/symbol_export.rs
+++ b/src/librustc_trans/back/symbol_export.rs
@@ -11,33 +11,27 @@
 use rustc_data_structures::sync::Lrc;
 use std::sync::Arc;
 
-use base;
 use monomorphize::Instance;
+use rustc::hir;
 use rustc::hir::def_id::CrateNum;
 use rustc::hir::def_id::{DefId, LOCAL_CRATE};
-use rustc::middle::exported_symbols::SymbolExportLevel;
+use rustc::middle::exported_symbols::{SymbolExportLevel, ExportedSymbol, metadata_symbol_name};
 use rustc::session::config;
-use rustc::ty::TyCtxt;
+use rustc::ty::{TyCtxt, SymbolName};
 use rustc::ty::maps::Providers;
-use rustc::util::nodemap::FxHashMap;
+use rustc::util::nodemap::{FxHashMap, DefIdSet};
 use rustc_allocator::ALLOCATOR_METHODS;
 use syntax::attr;
 
 pub type ExportedSymbols = FxHashMap<
     CrateNum,
-    Arc<Vec<(String, Option<DefId>, SymbolExportLevel)>>,
+    Arc<Vec<(String, SymbolExportLevel)>>,
 >;
 
 pub fn threshold(tcx: TyCtxt) -> SymbolExportLevel {
     crates_export_threshold(&tcx.sess.crate_types.borrow())
 }
 
-pub fn metadata_symbol_name(tcx: TyCtxt) -> String {
-    format!("rust_metadata_{}_{}",
-            tcx.crate_name(LOCAL_CRATE),
-            tcx.crate_disambiguator(LOCAL_CRATE).to_fingerprint().to_hex())
-}
-
 fn crate_export_threshold(crate_type: config::CrateType) -> SymbolExportLevel {
     match crate_type {
         config::CrateTypeExecutable |
@@ -60,140 +54,203 @@ pub fn crates_export_threshold(crate_types: &[config::CrateType])
     }
 }
 
-pub fn provide(providers: &mut Providers) {
-    providers.exported_symbol_ids = |tcx, cnum| {
-        let export_threshold = threshold(tcx);
-        Lrc::new(tcx.exported_symbols(cnum)
-            .iter()
-            .filter_map(|&(_, id, level)| {
-                id.and_then(|id| {
-                    if level.is_below_threshold(export_threshold) {
-                        Some(id)
+fn reachable_non_generics_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                                             cnum: CrateNum)
+                                             -> Lrc<DefIdSet>
+{
+    assert_eq!(cnum, LOCAL_CRATE);
+
+    if !tcx.sess.opts.output_types.should_trans() {
+        return Lrc::new(DefIdSet())
+    }
+
+    let export_threshold = threshold(tcx);
+
+    // We already collect all potentially reachable non-generic items for
+    // `exported_symbols`. Now we just filter them down to what is actually
+    // exported for the given crate we are compiling.
+    let reachable_non_generics = tcx
+        .exported_symbols(LOCAL_CRATE)
+        .iter()
+        .filter_map(|&(exported_symbol, level)| {
+            if let ExportedSymbol::NonGeneric(def_id) = exported_symbol {
+                if level.is_below_threshold(export_threshold) {
+                    return Some(def_id)
+                }
+            }
+
+            None
+        })
+        .collect();
+
+    Lrc::new(reachable_non_generics)
+}
+
+fn is_reachable_non_generic_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                                               def_id: DefId)
+                                               -> bool {
+    tcx.reachable_non_generics(def_id.krate).contains(&def_id)
+}
+
+fn exported_symbols_provider_local<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                                             cnum: CrateNum)
+                                             -> Arc<Vec<(ExportedSymbol,
+                                                         SymbolExportLevel)>>
+{
+    assert_eq!(cnum, LOCAL_CRATE);
+
+    if !tcx.sess.opts.output_types.should_trans() {
+        return Arc::new(vec![])
+    }
+
+    // Check to see if this crate is a "special runtime crate". These
+    // crates, implementation details of the standard library, typically
+    // have a bunch of `pub extern` and `#[no_mangle]` functions as the
+    // ABI between them. We don't want their symbols to have a `C`
+    // export level, however, as they're just implementation details.
+    // Down below we'll hardwire all of the symbols to the `Rust` export
+    // level instead.
+    let special_runtime_crate = tcx.is_panic_runtime(LOCAL_CRATE) ||
+        tcx.is_compiler_builtins(LOCAL_CRATE);
+
+    let reachable_non_generics: DefIdSet = tcx.reachable_set(LOCAL_CRATE).0
+        .iter()
+        .filter_map(|&node_id| {
+            // We want to ignore some FFI functions that are not exposed from
+            // this crate. Reachable FFI functions can be lumped into two
+            // categories:
+            //
+            // 1. Those that are included statically via a static library
+            // 2. Those included otherwise (e.g. dynamically or via a framework)
+            //
+            // Although our LLVM module is not literally emitting code for the
+            // statically included symbols, it's an export of our library which
+            // needs to be passed on to the linker and encoded in the metadata.
+            //
+            // As a result, if this id is an FFI item (foreign item) then we only
+            // let it through if it's included statically.
+            match tcx.hir.get(node_id) {
+                hir::map::NodeForeignItem(..) => {
+                    let def_id = tcx.hir.local_def_id(node_id);
+                    if tcx.is_statically_included_foreign_item(def_id) {
+                        Some(def_id)
                     } else {
                         None
                     }
-                })
-            })
-            .collect())
-    };
-
-    providers.is_exported_symbol = |tcx, id| {
-        tcx.exported_symbol_ids(id.krate).contains(&id)
-    };
-
-    providers.exported_symbols = |tcx, cnum| {
-        assert_eq!(cnum, LOCAL_CRATE);
-        let local_exported_symbols = base::find_exported_symbols(tcx);
-
-        let mut local_crate: Vec<_> = local_exported_symbols
-            .iter()
-            .map(|&node_id| {
-                tcx.hir.local_def_id(node_id)
-            })
-            .map(|def_id| {
-                let name = tcx.symbol_name(Instance::mono(tcx, def_id));
-                let export_level = export_level(tcx, def_id);
-                debug!("EXPORTED SYMBOL (local): {} ({:?})", name, export_level);
-                (str::to_owned(&name), Some(def_id), export_level)
-            })
-            .collect();
-
-        if let Some(_) = *tcx.sess.entry_fn.borrow() {
-            local_crate.push(("main".to_string(),
-                              None,
-                              SymbolExportLevel::C));
-        }
+                }
+
+                // Only consider nodes that actually have exported symbols.
+                hir::map::NodeItem(&hir::Item {
+                    node: hir::ItemStatic(..),
+                    ..
+                }) |
+                hir::map::NodeItem(&hir::Item {
+                    node: hir::ItemFn(..), ..
+                }) |
+                hir::map::NodeImplItem(&hir::ImplItem {
+                    node: hir::ImplItemKind::Method(..),
+                    ..
+                }) => {
+                    let def_id = tcx.hir.local_def_id(node_id);
+                    let generics = tcx.generics_of(def_id);
+                    if (generics.parent_types == 0 && generics.types.is_empty()) &&
+                        // Functions marked with #[inline] are only ever translated
+                        // with "internal" linkage and are never exported.
+                        !Instance::mono(tcx, def_id).def.requires_local(tcx) {
+                        Some(def_id)
+                    } else {
+                        None
+                    }
+                }
 
-        if tcx.sess.allocator_kind.get().is_some() {
-            for method in ALLOCATOR_METHODS {
-                local_crate.push((format!("__rust_{}", method.name),
-                                  None,
-                                  SymbolExportLevel::Rust));
+                _ => None
             }
-        }
+        })
+        .collect();
 
-        if let Some(id) = tcx.sess.derive_registrar_fn.get() {
-            let def_id = tcx.hir.local_def_id(id);
-            let disambiguator = tcx.sess.local_crate_disambiguator();
-            let registrar = tcx.sess.generate_derive_registrar_symbol(disambiguator);
-            local_crate.push((registrar, Some(def_id), SymbolExportLevel::C));
-        }
+    let mut symbols: Vec<_> = reachable_non_generics
+        .iter()
+        .map(|&def_id| {
+            let export_level = if special_runtime_crate {
+                let name = tcx.symbol_name(Instance::mono(tcx, def_id));
+                // We can probably do better here by just ensuring that
+                // it has hidden visibility rather than public
+                // visibility, as this is primarily here to ensure it's
+                // not stripped during LTO.
+                //
+                // In general though we won't link right if these
+                // symbols are stripped, and LTO currently strips them.
+                if &*name == "rust_eh_personality" ||
+                   &*name == "rust_eh_register_frames" ||
+                   &*name == "rust_eh_unregister_frames" {
+                    SymbolExportLevel::C
+                } else {
+                    SymbolExportLevel::Rust
+                }
+            } else {
+                tcx.symbol_export_level(def_id)
+            };
+            debug!("EXPORTED SYMBOL (local): {} ({:?})",
+                   tcx.symbol_name(Instance::mono(tcx, def_id)),
+                   export_level);
+            (ExportedSymbol::NonGeneric(def_id), export_level)
+        })
+        .collect();
+
+    if let Some(id) = tcx.sess.derive_registrar_fn.get() {
+        let def_id = tcx.hir.local_def_id(id);
+        symbols.push((ExportedSymbol::NonGeneric(def_id), SymbolExportLevel::C));
+    }
+
+    if let Some(id) = tcx.sess.plugin_registrar_fn.get() {
+        let def_id = tcx.hir.local_def_id(id);
+        symbols.push((ExportedSymbol::NonGeneric(def_id), SymbolExportLevel::C));
+    }
+
+    if let Some(_) = *tcx.sess.entry_fn.borrow() {
+        let symbol_name = "main".to_string();
+        let exported_symbol = ExportedSymbol::NoDefId(SymbolName::new(&symbol_name));
+
+        symbols.push((exported_symbol, SymbolExportLevel::C));
+    }
+
+    if tcx.sess.allocator_kind.get().is_some() {
+        for method in ALLOCATOR_METHODS {
+            let symbol_name = format!("__rust_{}", method.name);
+            let exported_symbol = ExportedSymbol::NoDefId(SymbolName::new(&symbol_name));
 
-        if tcx.sess.crate_types.borrow().contains(&config::CrateTypeDylib) {
-            local_crate.push((metadata_symbol_name(tcx),
-                              None,
-                              SymbolExportLevel::Rust));
+            symbols.push((exported_symbol, SymbolExportLevel::Rust));
         }
+    }
+
+    if tcx.sess.crate_types.borrow().contains(&config::CrateTypeDylib) {
+        let symbol_name = metadata_symbol_name(tcx);
+        let exported_symbol = ExportedSymbol::NoDefId(SymbolName::new(&symbol_name));
 
-        // Sort so we get a stable incr. comp. hash.
-        local_crate.sort_unstable_by(|&(ref name1, ..), &(ref name2, ..)| {
-            name1.cmp(name2)
-        });
+        symbols.push((exported_symbol, SymbolExportLevel::Rust));
+    }
 
-        Arc::new(local_crate)
-    };
+    // Sort so we get a stable incr. comp. hash.
+    symbols.sort_unstable_by(|&(ref symbol1, ..), &(ref symbol2, ..)| {
+        symbol1.compare_stable(tcx, symbol2)
+    });
 
-    providers.symbol_export_level = export_level;
+    Arc::new(symbols)
 }
 
-pub fn provide_extern(providers: &mut Providers) {
-    providers.exported_symbols = |tcx, cnum| {
-        // If this crate is a plugin and/or a custom derive crate, then
-        // we're not even going to link those in so we skip those crates.
-        if tcx.plugin_registrar_fn(cnum).is_some() ||
-           tcx.derive_registrar_fn(cnum).is_some() {
-            return Arc::new(Vec::new())
-        }
+pub fn provide(providers: &mut Providers) {
+    providers.reachable_non_generics = reachable_non_generics_provider;
+    providers.is_reachable_non_generic = is_reachable_non_generic_provider;
+    providers.exported_symbols = exported_symbols_provider_local;
+    providers.symbol_export_level = symbol_export_level_provider;
+}
 
-        // Check to see if this crate is a "special runtime crate". These
-        // crates, implementation details of the standard library, typically
-        // have a bunch of `pub extern` and `#[no_mangle]` functions as the
-        // ABI between them. We don't want their symbols to have a `C`
-        // export level, however, as they're just implementation details.
-        // Down below we'll hardwire all of the symbols to the `Rust` export
-        // level instead.
-        let special_runtime_crate =
-            tcx.is_panic_runtime(cnum) || tcx.is_compiler_builtins(cnum);
-
-        let mut crate_exports: Vec<_> = tcx
-            .exported_symbol_ids(cnum)
-            .iter()
-            .map(|&def_id| {
-                let name = tcx.symbol_name(Instance::mono(tcx, def_id));
-                let export_level = if special_runtime_crate {
-                    // We can probably do better here by just ensuring that
-                    // it has hidden visibility rather than public
-                    // visibility, as this is primarily here to ensure it's
-                    // not stripped during LTO.
-                    //
-                    // In general though we won't link right if these
-                    // symbols are stripped, and LTO currently strips them.
-                    if &*name == "rust_eh_personality" ||
-                       &*name == "rust_eh_register_frames" ||
-                       &*name == "rust_eh_unregister_frames" {
-                        SymbolExportLevel::C
-                    } else {
-                        SymbolExportLevel::Rust
-                    }
-                } else {
-                    export_level(tcx, def_id)
-                };
-                debug!("EXPORTED SYMBOL (re-export): {} ({:?})", name, export_level);
-                (str::to_owned(&name), Some(def_id), export_level)
-            })
-            .collect();
-
-        // Sort so we get a stable incr. comp. hash.
-        crate_exports.sort_unstable_by(|&(ref name1, ..), &(ref name2, ..)| {
-            name1.cmp(name2)
-        });
-
-        Arc::new(crate_exports)
-    };
-    providers.symbol_export_level = export_level;
+pub fn provide_extern(providers: &mut Providers) {
+    providers.is_reachable_non_generic = is_reachable_non_generic_provider;
+    providers.symbol_export_level = symbol_export_level_provider;
 }
 
-fn export_level(tcx: TyCtxt, sym_def_id: DefId) -> SymbolExportLevel {
+fn symbol_export_level_provider(tcx: TyCtxt, sym_def_id: DefId) -> SymbolExportLevel {
     // We export anything that's not mangled at the "C" layer as it probably has
     // to do with ABI concerns. We do not, however, apply such treatment to
     // special symbols in the standard library for various plumbing between
diff --git a/src/librustc_trans/back/write.rs b/src/librustc_trans/back/write.rs
index 78b26a37485..c0561ff0c17 100644
--- a/src/librustc_trans/back/write.rs
+++ b/src/librustc_trans/back/write.rs
@@ -1332,20 +1332,31 @@ fn start_executing_work(tcx: TyCtxt,
     let coordinator_send = tcx.tx_to_llvm_workers.clone();
     let sess = tcx.sess;
 
-    let exported_symbols = match sess.lto() {
-        Lto::No => None,
-        Lto::ThinLocal => {
-            let mut exported_symbols = FxHashMap();
-            exported_symbols.insert(LOCAL_CRATE, tcx.exported_symbols(LOCAL_CRATE));
-            Some(Arc::new(exported_symbols))
-        }
-        Lto::Yes | Lto::Fat | Lto::Thin => {
-            let mut exported_symbols = FxHashMap();
-            exported_symbols.insert(LOCAL_CRATE, tcx.exported_symbols(LOCAL_CRATE));
-            for &cnum in tcx.crates().iter() {
-                exported_symbols.insert(cnum, tcx.exported_symbols(cnum));
+    // Compute the set of symbols we need to retain when doing LTO (if we need to)
+    let exported_symbols = {
+        let mut exported_symbols = FxHashMap();
+
+        let copy_symbols = |cnum| {
+            let symbols = tcx.exported_symbols(cnum)
+                             .iter()
+                             .map(|&(s, lvl)| (s.symbol_name(tcx).to_string(), lvl))
+                             .collect();
+            Arc::new(symbols)
+        };
+
+        match sess.lto() {
+            Lto::No => None,
+            Lto::ThinLocal => {
+                exported_symbols.insert(LOCAL_CRATE, copy_symbols(LOCAL_CRATE));
+                Some(Arc::new(exported_symbols))
+            }
+            Lto::Yes | Lto::Fat | Lto::Thin => {
+                exported_symbols.insert(LOCAL_CRATE, copy_symbols(LOCAL_CRATE));
+                for &cnum in tcx.crates().iter() {
+                    exported_symbols.insert(cnum, copy_symbols(cnum));
+                }
+                Some(Arc::new(exported_symbols))
             }
-            Some(Arc::new(exported_symbols))
         }
     };
 
diff --git a/src/librustc_trans/base.rs b/src/librustc_trans/base.rs
index c0785f53937..beb7a091bdc 100644
--- a/src/librustc_trans/base.rs
+++ b/src/librustc_trans/base.rs
@@ -30,7 +30,6 @@ use super::ModuleKind;
 
 use abi;
 use back::link;
-use back::symbol_export;
 use back::write::{self, OngoingCrateTranslation, create_target_machine};
 use llvm::{ContextRef, ModuleRef, ValueRef, Vector, get_param};
 use llvm;
@@ -45,6 +44,7 @@ use rustc::ty::maps::Providers;
 use rustc::dep_graph::{DepNode, DepConstructor};
 use rustc::ty::subst::Kind;
 use rustc::middle::cstore::{self, LinkMeta, LinkagePreference};
+use rustc::middle::exported_symbols;
 use rustc::util::common::{time, print_time_passes_entry};
 use rustc::session::config::{self, NoDebugInfo};
 use rustc::session::Session;
@@ -70,7 +70,7 @@ use time_graph;
 use trans_item::{MonoItem, BaseMonoItemExt, MonoItemExt, DefPathBasedNames};
 use type_::Type;
 use type_of::LayoutLlvmExt;
-use rustc::util::nodemap::{NodeSet, FxHashMap, FxHashSet, DefIdSet};
+use rustc::util::nodemap::{FxHashMap, FxHashSet, DefIdSet};
 use CrateInfo;
 
 use std::any::Any;
@@ -89,7 +89,7 @@ use syntax::ast;
 
 use mir::operand::OperandValue;
 
-pub use rustc_trans_utils::{find_exported_symbols, check_for_rustc_errors_attr};
+pub use rustc_trans_utils::check_for_rustc_errors_attr;
 pub use rustc_mir::monomorphize::item::linkage_by_name;
 
 pub struct StatRecorder<'a, 'tcx: 'a> {
@@ -606,8 +606,7 @@ fn contains_null(s: &str) -> bool {
 
 fn write_metadata<'a, 'gcx>(tcx: TyCtxt<'a, 'gcx, 'gcx>,
                             llmod_id: &str,
-                            link_meta: &LinkMeta,
-                            exported_symbols: &NodeSet)
+                            link_meta: &LinkMeta)
                             -> (ContextRef, ModuleRef, EncodedMetadata) {
     use std::io::Write;
     use flate2::Compression;
@@ -643,7 +642,7 @@ fn write_metadata<'a, 'gcx>(tcx: TyCtxt<'a, 'gcx, 'gcx>,
                 EncodedMetadata::new());
     }
 
-    let metadata = tcx.encode_metadata(link_meta, exported_symbols);
+    let metadata = tcx.encode_metadata(link_meta);
     if kind == MetadataKind::Uncompressed {
         return (metadata_llcx, metadata_llmod, metadata);
     }
@@ -655,7 +654,7 @@ fn write_metadata<'a, 'gcx>(tcx: TyCtxt<'a, 'gcx, 'gcx>,
 
     let llmeta = C_bytes_in_context(metadata_llcx, &compressed);
     let llconst = C_struct_in_context(metadata_llcx, &[llmeta], false);
-    let name = symbol_export::metadata_symbol_name(tcx);
+    let name = exported_symbols::metadata_symbol_name(tcx);
     let buf = CString::new(name).unwrap();
     let llglobal = unsafe {
         llvm::LLVMAddGlobal(metadata_llmod, val_ty(llconst).to_ref(), buf.as_ptr())
@@ -718,13 +717,12 @@ pub fn trans_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     let crate_hash = tcx.crate_hash(LOCAL_CRATE);
     let link_meta = link::build_link_meta(crate_hash);
-    let exported_symbol_node_ids = find_exported_symbols(tcx);
 
     // Translate the metadata.
     let llmod_id = "metadata";
     let (metadata_llcx, metadata_llmod, metadata) =
         time(tcx.sess.time_passes(), "write metadata", || {
-            write_metadata(tcx, llmod_id, &link_meta, &exported_symbol_node_ids)
+            write_metadata(tcx, llmod_id, &link_meta)
         });
 
     let metadata_module = ModuleTranslation {
diff --git a/src/librustc_trans/callee.rs b/src/librustc_trans/callee.rs
index 8c40aa6a2ac..54cc561e804 100644
--- a/src/librustc_trans/callee.rs
+++ b/src/librustc_trans/callee.rs
@@ -151,7 +151,7 @@ pub fn get_fn<'a, 'tcx>(cx: &CodegenCx<'a, 'tcx>,
 
             if cx.tcx.is_translated_item(instance_def_id) {
                 if instance_def_id.is_local() {
-                    if !cx.tcx.is_exported_symbol(instance_def_id) {
+                    if !cx.tcx.is_reachable_non_generic(instance_def_id) {
                         llvm::LLVMRustSetVisibility(llfn, llvm::Visibility::Hidden);
                     }
                 } else {
diff --git a/src/librustc_trans/consts.rs b/src/librustc_trans/consts.rs
index 1608c4a87bf..fd9cb8c5a6b 100644
--- a/src/librustc_trans/consts.rs
+++ b/src/librustc_trans/consts.rs
@@ -134,7 +134,7 @@ pub fn get_static(cx: &CodegenCx, def_id: DefId) -> ValueRef {
 
                 let g = declare::define_global(cx, &sym[..], llty).unwrap();
 
-                if !cx.tcx.is_exported_symbol(def_id) {
+                if !cx.tcx.is_reachable_non_generic(def_id) {
                     unsafe {
                         llvm::LLVMRustSetVisibility(g, llvm::Visibility::Hidden);
                     }
diff --git a/src/librustc_trans/debuginfo/utils.rs b/src/librustc_trans/debuginfo/utils.rs
index 9559cd4d9ea..0a3f06b55f1 100644
--- a/src/librustc_trans/debuginfo/utils.rs
+++ b/src/librustc_trans/debuginfo/utils.rs
@@ -32,7 +32,7 @@ pub fn is_node_local_to_unit(cx: &CodegenCx, def_id: DefId) -> bool
     // visible). It might better to use the `exported_items` set from
     // `driver::CrateAnalysis` in the future, but (atm) this set is not
     // available in the translation pass.
-    !cx.tcx.is_exported_symbol(def_id)
+    !cx.tcx.is_reachable_non_generic(def_id)
 }
 
 #[allow(non_snake_case)]
diff --git a/src/librustc_trans_utils/lib.rs b/src/librustc_trans_utils/lib.rs
index bfecb201983..d636a5f2e64 100644
--- a/src/librustc_trans_utils/lib.rs
+++ b/src/librustc_trans_utils/lib.rs
@@ -44,11 +44,7 @@ extern crate rustc_data_structures;
 
 pub extern crate rustc as __rustc;
 
-use rustc::ty::{TyCtxt, Instance};
-use rustc::hir;
-use rustc::hir::def_id::LOCAL_CRATE;
-use rustc::hir::map as hir_map;
-use rustc::util::nodemap::NodeSet;
+use rustc::ty::TyCtxt;
 
 pub mod diagnostics;
 pub mod link;
@@ -70,53 +66,4 @@ pub fn check_for_rustc_errors_attr(tcx: TyCtxt) {
     }
 }
 
-/// The context provided lists a set of reachable ids as calculated by
-/// middle::reachable, but this contains far more ids and symbols than we're
-/// actually exposing from the object file. This function will filter the set in
-/// the context to the set of ids which correspond to symbols that are exposed
-/// from the object file being generated.
-///
-/// This list is later used by linkers to determine the set of symbols needed to
-/// be exposed from a dynamic library and it's also encoded into the metadata.
-pub fn find_exported_symbols<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> NodeSet {
-    tcx.reachable_set(LOCAL_CRATE).0.iter().cloned().filter(|&id| {
-        // Next, we want to ignore some FFI functions that are not exposed from
-        // this crate. Reachable FFI functions can be lumped into two
-        // categories:
-        //
-        // 1. Those that are included statically via a static library
-        // 2. Those included otherwise (e.g. dynamically or via a framework)
-        //
-        // Although our LLVM module is not literally emitting code for the
-        // statically included symbols, it's an export of our library which
-        // needs to be passed on to the linker and encoded in the metadata.
-        //
-        // As a result, if this id is an FFI item (foreign item) then we only
-        // let it through if it's included statically.
-        match tcx.hir.get(id) {
-            hir_map::NodeForeignItem(..) => {
-                let def_id = tcx.hir.local_def_id(id);
-                tcx.is_statically_included_foreign_item(def_id)
-            }
-
-            // Only consider nodes that actually have exported symbols.
-            hir_map::NodeItem(&hir::Item {
-                node: hir::ItemStatic(..), .. }) |
-            hir_map::NodeItem(&hir::Item {
-                node: hir::ItemFn(..), .. }) |
-            hir_map::NodeImplItem(&hir::ImplItem {
-                node: hir::ImplItemKind::Method(..), .. }) => {
-                let def_id = tcx.hir.local_def_id(id);
-                let generics = tcx.generics_of(def_id);
-                (generics.parent_types == 0 && generics.types.is_empty()) &&
-                // Functions marked with #[inline] are only ever translated
-                // with "internal" linkage and are never exported.
-                !Instance::mono(tcx, def_id).def.requires_local(tcx)
-            }
-
-            _ => false
-        }
-    }).collect()
-}
-
 __build_diagnostic_array! { librustc_trans_utils, DIAGNOSTICS }
diff --git a/src/librustc_trans_utils/trans_crate.rs b/src/librustc_trans_utils/trans_crate.rs
index 419371ba3e3..7b2cbe140ae 100644
--- a/src/librustc_trans_utils/trans_crate.rs
+++ b/src/librustc_trans_utils/trans_crate.rs
@@ -247,8 +247,7 @@ impl TransCrate for MetadataOnlyTransCrate {
         tcx.sess.abort_if_errors();
 
         let link_meta = build_link_meta(tcx.crate_hash(LOCAL_CRATE));
-        let exported_symbols = ::find_exported_symbols(tcx);
-        let metadata = tcx.encode_metadata(&link_meta, &exported_symbols);
+        let metadata = tcx.encode_metadata(&link_meta);
 
         box OngoingCrateTranslation {
             metadata: metadata,