Allow for re-using monomorphizations from upstream crates.

13 files changed, 195 insertions, 38 deletions

diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index d1f3736556c..9172c3067ac 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -657,6 +657,9 @@ define_dep_nodes!( <'tcx>
     [] ProgramClausesFor(DefId),
     [] WasmImportModuleMap(CrateNum),
     [] ForeignModules(CrateNum),
+
+    [] UpstreamMonomorphizations(CrateNum),
+    [] UpstreamMonomorphizationsFor(DefId),
 );
 
 trait DepNodeParams<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> : fmt::Debug {
diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index f37f2aa9e2d..f8691349025 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -53,8 +53,21 @@ for &'gcx ty::Slice<T>
     }
 }
 
-impl<'a, 'gcx> HashStable<StableHashingContext<'a>>
-for ty::subst::Kind<'gcx> {
+impl<'a, 'gcx, T> ToStableHashKey<StableHashingContext<'a>> for &'gcx ty::Slice<T>
+    where T: HashStable<StableHashingContext<'a>>
+{
+    type KeyType = Fingerprint;
+
+    #[inline]
+    fn to_stable_hash_key(&self, hcx: &StableHashingContext<'a>) -> Fingerprint {
+        let mut hasher = StableHasher::new();
+        let mut hcx: StableHashingContext<'a> = hcx.clone();
+        self.hash_stable(&mut hcx, &mut hasher);
+        hasher.finish()
+    }
+}
+
+impl<'a, 'gcx> HashStable<StableHashingContext<'a>> for ty::subst::Kind<'gcx> {
     fn hash_stable<W: StableHasherResult>(&self,
                                           hcx: &mut StableHashingContext<'a>,
                                           hasher: &mut StableHasher<W>) {
diff --git a/src/librustc/session/config.rs b/src/librustc/session/config.rs
index 59d1a298eaa..312df69d318 100644
--- a/src/librustc/session/config.rs
+++ b/src/librustc/session/config.rs
@@ -1304,6 +1304,8 @@ options! {DebuggingOptions, DebuggingSetter, basic_debugging_options,
           "embed LLVM bitcode in object files"),
     strip_debuginfo_if_disabled: Option<bool> = (None, parse_opt_bool, [TRACKED],
         "tell the linker to strip debuginfo when building without debuginfo enabled."),
+    share_generics: Option<bool> = (None, parse_opt_bool, [TRACKED],
+          "make the current crate share its generic instantiations"),
 }
 
 pub fn default_lib_output() -> CrateType {
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 3326af21bd6..8a58dad2924 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -1499,6 +1499,14 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             self.sess.opts.debugging_opts.mir_emit_validate > 0 ||
             self.use_mir()
     }
+
+    #[inline]
+    pub fn share_generics(self) -> bool {
+        match self.sess.opts.debugging_opts.share_generics {
+            Some(true) => true,
+            Some(false) | None => false,
+        }
+    }
 }
 
 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
diff --git a/src/librustc/ty/maps/config.rs b/src/librustc/ty/maps/config.rs
index a08cd57b1f7..16866636cd9 100644
--- a/src/librustc/ty/maps/config.rs
+++ b/src/librustc/ty/maps/config.rs
@@ -131,6 +131,12 @@ impl<'tcx> QueryDescription<'tcx> for queries::coherent_trait<'tcx> {
     }
 }
 
+impl<'tcx> QueryDescription<'tcx> for queries::upstream_monomorphizations<'tcx> {
+    fn describe(_: TyCtxt, k: CrateNum) -> String {
+        format!("collecting available upstream monomorphizations `{:?}`", k)
+    }
+}
+
 impl<'tcx> QueryDescription<'tcx> for queries::crate_inherent_impls<'tcx> {
     fn describe(_: TyCtxt, k: CrateNum) -> String {
         format!("all inherent impls defined in crate `{:?}`", k)
diff --git a/src/librustc/ty/maps/mod.rs b/src/librustc/ty/maps/mod.rs
index 78611347077..5f093bc0b48 100644
--- a/src/librustc/ty/maps/mod.rs
+++ b/src/librustc/ty/maps/mod.rs
@@ -319,9 +319,14 @@ define_maps! { <'tcx>
     //
     // 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 reachable_non_generics: ReachableNonGenerics(CrateNum)
+        -> Lrc<DefIdMap<SymbolExportLevel>>,
     [] fn is_reachable_non_generic: IsReachableNonGeneric(DefId) -> bool,
 
+    [] fn upstream_monomorphizations: UpstreamMonomorphizations(CrateNum)
+        -> Lrc<DefIdMap<Lrc<FxHashMap<&'tcx Substs<'tcx>, CrateNum>>>>,
+    [] fn upstream_monomorphizations_for: UpstreamMonomorphizationsFor(DefId)
+        -> Option<Lrc<FxHashMap<&'tcx Substs<'tcx>, CrateNum>>>,
 
     [] fn native_libraries: NativeLibraries(CrateNum) -> Lrc<Vec<NativeLibrary>>,
 
diff --git a/src/librustc/ty/maps/plumbing.rs b/src/librustc/ty/maps/plumbing.rs
index bc5a14c96f0..b37628c390f 100644
--- a/src/librustc/ty/maps/plumbing.rs
+++ b/src/librustc/ty/maps/plumbing.rs
@@ -1094,6 +1094,13 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
         DepKind::WasmCustomSections => { force!(wasm_custom_sections, krate!()); }
         DepKind::WasmImportModuleMap => { force!(wasm_import_module_map, krate!()); }
         DepKind::ForeignModules => { force!(foreign_modules, krate!()); }
+
+        DepKind::UpstreamMonomorphizations => {
+            force!(upstream_monomorphizations, krate!());
+        }
+        DepKind::UpstreamMonomorphizationsFor => {
+            force!(upstream_monomorphizations_for, def_id!());
+        }
     }
 
     true
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index 30055bea635..51088563c7b 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -186,9 +186,9 @@ provide! { <'tcx> tcx, def_id, other, cdata,
         let reachable_non_generics = tcx
             .exported_symbols(cdata.cnum)
             .iter()
-            .filter_map(|&(exported_symbol, _)| {
+            .filter_map(|&(exported_symbol, export_level)| {
                 if let ExportedSymbol::NonGeneric(def_id) = exported_symbol {
-                    return Some(def_id)
+                    return Some((def_id, export_level))
                 } else {
                     None
                 }
diff --git a/src/librustc_mir/monomorphize/collector.rs b/src/librustc_mir/monomorphize/collector.rs
index 446ef6bd328..e93b936d4f0 100644
--- a/src/librustc_mir/monomorphize/collector.rs
+++ b/src/librustc_mir/monomorphize/collector.rs
@@ -569,7 +569,9 @@ impl<'a, 'tcx> MirVisitor<'tcx> for MirNeighborCollector<'a, 'tcx> {
                     ty::TyClosure(def_id, substs) => {
                         let instance = monomorphize::resolve_closure(
                             self.tcx, def_id, substs, ty::ClosureKind::FnOnce);
-                        self.output.push(create_fn_mono_item(instance));
+                        if should_monomorphize_locally(self.tcx, &instance) {
+                            self.output.push(create_fn_mono_item(instance));
+                        }
                     }
                     _ => bug!(),
                 }
@@ -731,14 +733,16 @@ fn should_monomorphize_locally<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, instance:
         ty::InstanceDef::Intrinsic(_) |
         ty::InstanceDef::CloneShim(..) => return true
     };
-    match tcx.hir.get_if_local(def_id) {
+
+    return 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.is_reachable_non_generic(def_id) ||
-                tcx.is_foreign_item(def_id)
+                tcx.is_foreign_item(def_id) ||
+                is_available_upstream_generic(tcx, def_id, instance.substs)
             {
                 // We can link to the item in question, no instance needed
                 // in this crate
@@ -750,6 +754,25 @@ fn should_monomorphize_locally<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, instance:
                 true
             }
         }
+    };
+
+    fn is_available_upstream_generic<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                                               def_id: DefId,
+                                               substs: &'tcx Substs<'tcx>)
+                                               -> bool {
+        debug_assert!(!def_id.is_local());
+
+        if !tcx.share_generics() {
+            return false
+        }
+
+        if substs.types().next().is_none() {
+            return false
+        }
+
+        tcx.upstream_monomorphizations_for(def_id)
+           .map(|set| set.contains_key(substs))
+           .unwrap_or(false)
     }
 }
 
diff --git a/src/librustc_mir/monomorphize/partitioning.rs b/src/librustc_mir/monomorphize/partitioning.rs
index 3789342b389..c3437c8d55b 100644
--- a/src/librustc_mir/monomorphize/partitioning.rs
+++ b/src/librustc_mir/monomorphize/partitioning.rs
@@ -301,6 +301,7 @@ fn place_root_translation_items<'a, 'tcx, I>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let mut codegen_units = FxHashMap();
     let is_incremental_build = tcx.sess.opts.incremental.is_some();
     let mut internalization_candidates = FxHashSet();
+    let share_generics = tcx.share_generics();
 
     for trans_item in trans_items {
         match trans_item.instantiation_mode(tcx) {
@@ -362,6 +363,13 @@ fn place_root_translation_items<'a, 'tcx, I>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                 if tcx.lang_items().start_fn() == Some(def_id) {
                                     can_be_internalized = false;
                                     Visibility::Hidden
+                                } else if instance.substs.types().next().is_some() {
+                                    if share_generics {
+                                        can_be_internalized = false;
+                                        Visibility::Default
+                                    } else {
+                                        Visibility::Hidden
+                                    }
                                 } else if def_id.is_local() {
                                     if tcx.is_reachable_non_generic(def_id) {
                                         can_be_internalized = false;
diff --git a/src/librustc_trans/back/symbol_export.rs b/src/librustc_trans/back/symbol_export.rs
index 9843eaf77e7..69ba55ff8a9 100644
--- a/src/librustc_trans/back/symbol_export.rs
+++ b/src/librustc_trans/back/symbol_export.rs
@@ -20,6 +20,7 @@ use rustc::middle::exported_symbols::{SymbolExportLevel, ExportedSymbol, metadat
 use rustc::session::config;
 use rustc::ty::{TyCtxt, SymbolName};
 use rustc::ty::maps::Providers;
+use rustc::ty::subst::Substs;
 use rustc::util::nodemap::{FxHashMap, DefIdMap};
 use rustc_allocator::ALLOCATOR_METHODS;
 
@@ -240,6 +241,30 @@ fn exported_symbols_provider_local<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         symbols.push((exported_symbol, SymbolExportLevel::Rust));
     }
 
+    if tcx.share_generics() {
+        use rustc::mir::mono::{Linkage, Visibility, MonoItem};
+        use rustc::ty::InstanceDef;
+
+        let (_, cgus) = tcx.collect_and_partition_translation_items(LOCAL_CRATE);
+
+        for (mono_item, &(linkage, visibility)) in cgus.iter()
+                                                       .flat_map(|cgu| cgu.items().iter()) {
+            if linkage == Linkage::External {
+                if let &MonoItem::Fn(Instance {
+                    def: InstanceDef::Item(def_id),
+                    substs,
+                }) = mono_item {
+                    if substs.types().next().is_some() {
+                        assert!(tcx.lang_items().start_fn() == Some(def_id) ||
+                                visibility == Visibility::Default);
+                        symbols.push((ExportedSymbol::Generic(def_id, substs),
+                                      SymbolExportLevel::Rust));
+                    }
+                }
+            }
+        }
+    }
+
     // Sort so we get a stable incr. comp. hash.
     symbols.sort_unstable_by(|&(ref symbol1, ..), &(ref symbol2, ..)| {
         symbol1.compare_stable(tcx, symbol2)
@@ -248,16 +273,55 @@ fn exported_symbols_provider_local<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     Arc::new(symbols)
 }
 
+fn upstream_monomorphizations_provider<'a, 'tcx>(
+    tcx: TyCtxt<'a, 'tcx, 'tcx>,
+    cnum: CrateNum)
+    -> Lrc<DefIdMap<Lrc<FxHashMap<&'tcx Substs<'tcx>, CrateNum>>>>
+{
+    debug_assert!(cnum == LOCAL_CRATE);
+
+    let cnums = tcx.all_crate_nums(LOCAL_CRATE);
+
+    let mut instances = DefIdMap();
+
+    for &cnum in cnums.iter() {
+        for &(ref exported_symbol, _) in tcx.exported_symbols(cnum).iter() {
+            if let &ExportedSymbol::Generic(def_id, substs) = exported_symbol {
+                instances.entry(def_id)
+                         .or_insert_with(|| FxHashMap())
+                         .insert(substs, cnum);
+            }
+        }
+    }
+
+    Lrc::new(instances.into_iter()
+                      .map(|(key, value)| (key, Lrc::new(value)))
+                      .collect())
+}
+
+fn upstream_monomorphizations_for_provider<'a, 'tcx>(
+    tcx: TyCtxt<'a, 'tcx, 'tcx>,
+    def_id: DefId)
+    -> Option<Lrc<FxHashMap<&'tcx Substs<'tcx>, CrateNum>>>
+{
+    debug_assert!(!def_id.is_local());
+    tcx.upstream_monomorphizations(LOCAL_CRATE)
+       .get(&def_id)
+       .cloned()
+}
+
 pub fn provide(providers: &mut Providers) {
     providers.reachable_non_generics = reachable_non_generics_provider;
     providers.is_reachable_non_generic = is_reachable_non_generic_provider_local;
     providers.exported_symbols = exported_symbols_provider_local;
     providers.symbol_export_level = symbol_export_level_provider;
+    providers.upstream_monomorphizations = upstream_monomorphizations_provider;
 }
 
 pub fn provide_extern(providers: &mut Providers) {
     providers.is_reachable_non_generic = is_reachable_non_generic_provider_extern;
     providers.symbol_export_level = symbol_export_level_provider;
+    providers.upstream_monomorphizations_for = upstream_monomorphizations_for_provider;
 }
 
 fn symbol_export_level_provider(tcx: TyCtxt, sym_def_id: DefId) -> SymbolExportLevel {
diff --git a/src/librustc_trans/callee.rs b/src/librustc_trans/callee.rs
index 1dcf349e23b..84c07abe49b 100644
--- a/src/librustc_trans/callee.rs
+++ b/src/librustc_trans/callee.rs
@@ -148,13 +148,18 @@ pub fn get_fn<'a, 'tcx>(cx: &CodegenCx<'a, 'tcx>,
         unsafe {
             llvm::LLVMRustSetLinkage(llfn, llvm::Linkage::ExternalLinkage);
 
-            if cx.tcx.is_translated_item(instance_def_id) {
-                if instance_def_id.is_local() {
-                    if !cx.tcx.is_reachable_non_generic(instance_def_id) {
+            if cx.tcx.share_generics() && instance.substs.types().next().is_some() {
+                // If this is a generic function and we are sharing generics
+                // it will always have Visibility::Default
+            } else {
+                if cx.tcx.is_translated_item(instance_def_id) {
+                    if instance_def_id.is_local() {
+                        if !cx.tcx.is_reachable_non_generic(instance_def_id) {
+                            llvm::LLVMRustSetVisibility(llfn, llvm::Visibility::Hidden);
+                        }
+                    } else {
                         llvm::LLVMRustSetVisibility(llfn, llvm::Visibility::Hidden);
                     }
-                } else {
-                    llvm::LLVMRustSetVisibility(llfn, llvm::Visibility::Hidden);
                 }
             }
         }
diff --git a/src/librustc_trans_utils/symbol_names.rs b/src/librustc_trans_utils/symbol_names.rs
index f9f93730255..af174f7ce85 100644
--- a/src/librustc_trans_utils/symbol_names.rs
+++ b/src/librustc_trans_utils/symbol_names.rs
@@ -100,7 +100,7 @@
 use rustc::middle::weak_lang_items;
 use rustc_mir::monomorphize::Instance;
 use rustc_mir::monomorphize::item::{MonoItem, MonoItemExt, InstantiationMode};
-use rustc::hir::def_id::DefId;
+use rustc::hir::def_id::{DefId, LOCAL_CRATE};
 use rustc::hir::map as hir_map;
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
 use rustc::ty::fold::TypeVisitor;
@@ -170,32 +170,45 @@ fn get_symbol_hash<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         assert!(!substs.needs_subst());
         substs.visit_with(&mut hasher);
 
-        let mut avoid_cross_crate_conflicts = false;
-
-        // If this is an instance of a generic function, we also hash in
-        // the ID of the instantiating crate. This avoids symbol conflicts
-        // in case the same instances is emitted in two crates of the same
-        // project.
-        if substs.types().next().is_some() {
-            avoid_cross_crate_conflicts = true;
-        }
-
-        // If we're dealing with an instance of a function that's inlined from
-        // another crate but we're marking it as globally shared to our
-        // compliation (aka we're not making an internal copy in each of our
-        // codegen units) then this symbol may become an exported (but hidden
-        // visibility) symbol. This means that multiple crates may do the same
-        // and we want to be sure to avoid any symbol conflicts here.
-        match MonoItem::Fn(instance).instantiation_mode(tcx) {
-            InstantiationMode::GloballyShared { may_conflict: true } => {
-                avoid_cross_crate_conflicts = true;
-            }
-            _ => {}
-        }
+        let is_generic = substs.types().next().is_some();
+        let avoid_cross_crate_conflicts =
+            // If this is an instance of a generic function, we also hash in
+            // the ID of the instantiating crate. This avoids symbol conflicts
+            // in case the same instances is emitted in two crates of the same
+            // project.
+            is_generic ||
+
+            // If we're dealing with an instance of a function that's inlined from
+            // another crate but we're marking it as globally shared to our
+            // compliation (aka we're not making an internal copy in each of our
+            // codegen units) then this symbol may become an exported (but hidden
+            // visibility) symbol. This means that multiple crates may do the same
+            // and we want to be sure to avoid any symbol conflicts here.
+            match MonoItem::Fn(instance).instantiation_mode(tcx) {
+                InstantiationMode::GloballyShared { may_conflict: true } => true,
+                _ => false,
+            };
 
         if avoid_cross_crate_conflicts {
-            hasher.hash(tcx.crate_name.as_str());
-            hasher.hash(tcx.sess.local_crate_disambiguator());
+            let instantiating_crate = if is_generic {
+                if !def_id.is_local() && tcx.share_generics() {
+                    // If we are re-using a monomorphization from another crate,
+                    // we have to compute the symbol hash accordingly.
+                    let upstream_monomorphizations =
+                        tcx.upstream_monomorphizations_for(def_id);
+
+                    upstream_monomorphizations.and_then(|monos| monos.get(&substs)
+                                                                     .cloned())
+                                              .unwrap_or(LOCAL_CRATE)
+                } else {
+                    LOCAL_CRATE
+                }
+            } else {
+                LOCAL_CRATE
+            };
+
+            hasher.hash(&tcx.original_crate_name(instantiating_crate).as_str()[..]);
+            hasher.hash(&tcx.crate_disambiguator(instantiating_crate));
         }
     });