Add initial version of codegen unit partitioning for incremental compilation.

23 files changed, 1326 insertions, 69 deletions

diff --git a/src/compiletest/runtest.rs b/src/compiletest/runtest.rs
index 75866e3cdaa..af482f781ab 100644
--- a/src/compiletest/runtest.rs
+++ b/src/compiletest/runtest.rs
@@ -1911,6 +1911,7 @@ fn run_rustdoc_test(config: &Config, props: &TestProps, testpaths: &TestPaths) {
 }
 
 fn run_codegen_units_test(config: &Config, props: &TestProps, testpaths: &TestPaths) {
+
     assert!(props.revisions.is_empty(), "revisions not relevant here");
 
     let proc_res = compile_test(config, props, testpaths);
@@ -1921,36 +1922,148 @@ fn run_codegen_units_test(config: &Config, props: &TestProps, testpaths: &TestPa
 
     check_no_compiler_crash(None, &proc_res);
 
-    let prefix = "TRANS_ITEM ";
+    const PREFIX: &'static str = "TRANS_ITEM ";
+    const CGU_MARKER: &'static str = "@@";
 
-    let actual: HashSet<String> = proc_res
+    let actual: Vec<TransItem> = proc_res
         .stdout
         .lines()
-        .filter(|line| line.starts_with(prefix))
-        .map(|s| (&s[prefix.len()..]).to_string())
+        .filter(|line| line.starts_with(PREFIX))
+        .map(str_to_trans_item)
         .collect();
 
-    let expected: HashSet<String> = errors::load_errors(&testpaths.file, None)
+    let expected: Vec<TransItem> = errors::load_errors(&testpaths.file, None)
         .iter()
-        .map(|e| e.msg.trim().to_string())
+        .map(|e| str_to_trans_item(&e.msg[..]))
         .collect();
 
-    if actual != expected {
-        let mut missing: Vec<_> = expected.difference(&actual).collect();
+    let mut missing = Vec::new();
+    let mut wrong_cgus = Vec::new();
+
+    for expected_item in &expected {
+        let actual_item_with_same_name = actual.iter()
+                                               .find(|ti| ti.name == expected_item.name);
+
+        if let Some(actual_item) = actual_item_with_same_name {
+            if !expected_item.codegen_units.is_empty() {
+                // Also check for codegen units
+                if expected_item.codegen_units != actual_item.codegen_units {
+                    wrong_cgus.push((expected_item.clone(), actual_item.clone()));
+                }
+            }
+        } else {
+            missing.push(expected_item.string.clone());
+        }
+    }
+
+    let unexpected: Vec<_> =
+        actual.iter()
+              .filter(|acgu| !expected.iter().any(|ecgu| acgu.name == ecgu.name))
+              .map(|acgu| acgu.string.clone())
+              .collect();
+
+    if !missing.is_empty() {
         missing.sort();
 
-        let mut too_much: Vec<_> = actual.difference(&expected).collect();
-        too_much.sort();
+        println!("\nThese items should have been contained but were not:\n");
+
+        for item in &missing {
+            println!("{}", item);
+        }
 
-        println!("Expected and actual sets of codegen-items differ.\n\
-                  These items should have been contained but were not:\n\n\
-                  {}\n\n\
-                  These items were contained but should not have been:\n\n\
-                  {}\n\n",
-            missing.iter().fold("".to_string(), |s1, s2| s1 + "\n" + s2),
-            too_much.iter().fold("".to_string(), |s1, s2| s1 + "\n" + s2));
+        println!("\n");
+    }
+
+    if !unexpected.is_empty() {
+        let sorted = {
+            let mut sorted = unexpected.clone();
+            sorted.sort();
+            sorted
+        };
+
+        println!("\nThese items were contained but should not have been:\n");
+
+        for item in sorted {
+            println!("{}", item);
+        }
+
+        println!("\n");
+    }
+
+    if !wrong_cgus.is_empty() {
+        wrong_cgus.sort_by_key(|pair| pair.0.name.clone());
+        println!("\nThe following items were assigned to wrong codegen units:\n");
+
+        for &(ref expected_item, ref actual_item) in &wrong_cgus {
+            println!("{}", expected_item.name);
+            println!("  expected: {}", codegen_units_to_str(&expected_item.codegen_units));
+            println!("  actual:   {}", codegen_units_to_str(&actual_item.codegen_units));
+            println!("");
+        }
+    }
+
+    if !(missing.is_empty() && unexpected.is_empty() && wrong_cgus.is_empty())
+    {
         panic!();
     }
+
+    #[derive(Clone, Eq, PartialEq)]
+    struct TransItem {
+        name: String,
+        codegen_units: HashSet<String>,
+        string: String,
+    }
+
+    // [TRANS_ITEM] name [@@ (cgu)+]
+    fn str_to_trans_item(s: &str) -> TransItem {
+        let s = if s.starts_with(PREFIX) {
+            (&s[PREFIX.len()..]).trim()
+        } else {
+            s.trim()
+        };
+
+        let full_string = format!("{}{}", PREFIX, s.trim().to_owned());
+
+        let parts: Vec<&str> = s.split(CGU_MARKER)
+                                .map(str::trim)
+                                .filter(|s| !s.is_empty())
+                                .collect();
+
+        let name = parts[0].trim();
+
+        let cgus = if parts.len() > 1 {
+            let cgus_str = parts[1];
+
+            cgus_str.split(" ")
+                    .map(str::trim)
+                    .filter(|s| !s.is_empty())
+                    .map(str::to_owned)
+                    .collect()
+        }
+        else {
+            HashSet::new()
+        };
+
+        TransItem {
+            name: name.to_owned(),
+            codegen_units: cgus,
+            string: full_string,
+        }
+    }
+
+    fn codegen_units_to_str(cgus: &HashSet<String>) -> String
+    {
+        let mut cgus: Vec<_> = cgus.iter().collect();
+        cgus.sort();
+
+        let mut string = String::new();
+        for cgu in cgus {
+            string.push_str(&cgu[..]);
+            string.push_str(" ");
+        }
+
+        string
+    }
 }
 
 fn run_incremental_test(config: &Config, props: &TestProps, testpaths: &TestPaths) {
diff --git a/src/librustc/hir/map/collector.rs b/src/librustc/hir/map/collector.rs
index 94fa393ae3d..95f9e8eaac2 100644
--- a/src/librustc/hir/map/collector.rs
+++ b/src/librustc/hir/map/collector.rs
@@ -136,9 +136,10 @@ impl<'ast> Visitor<'ast> for NodeCollector<'ast> {
             ItemDefaultImpl(..) | ItemImpl(..) =>
                 DefPathData::Impl,
             ItemEnum(..) | ItemStruct(..) | ItemTrait(..) |
-            ItemExternCrate(..) | ItemMod(..) | ItemForeignMod(..) |
-            ItemTy(..) =>
+            ItemExternCrate(..) | ItemForeignMod(..) | ItemTy(..) =>
                 DefPathData::TypeNs(i.name),
+            ItemMod(..) =>
+                DefPathData::Module(i.name),
             ItemStatic(..) | ItemConst(..) | ItemFn(..) =>
                 DefPathData::ValueNs(i.name),
             ItemUse(..) =>
diff --git a/src/librustc/hir/map/definitions.rs b/src/librustc/hir/map/definitions.rs
index 2e26fe5057e..a2f0f30b62c 100644
--- a/src/librustc/hir/map/definitions.rs
+++ b/src/librustc/hir/map/definitions.rs
@@ -147,6 +147,7 @@ pub enum DefPathData {
     Impl,
     TypeNs(ast::Name), // something in the type NS
     ValueNs(ast::Name), // something in the value NS
+    Module(ast::Name),
     MacroDef(ast::Name),
     ClosureExpr,
 
@@ -288,6 +289,7 @@ impl DefPathData {
         match *self {
             TypeNs(name) |
             ValueNs(name) |
+            Module(name) |
             MacroDef(name) |
             TypeParam(name) |
             LifetimeDef(name) |
diff --git a/src/librustc/ty/item_path.rs b/src/librustc/ty/item_path.rs
index 5c1e19aee7b..e390456a87c 100644
--- a/src/librustc/ty/item_path.rs
+++ b/src/librustc/ty/item_path.rs
@@ -147,6 +147,7 @@ impl<'tcx> TyCtxt<'tcx> {
             data @ DefPathData::Misc |
             data @ DefPathData::TypeNs(..) |
             data @ DefPathData::ValueNs(..) |
+            data @ DefPathData::Module(..) |
             data @ DefPathData::TypeParam(..) |
             data @ DefPathData::LifetimeDef(..) |
             data @ DefPathData::EnumVariant(..) |
@@ -189,7 +190,7 @@ impl<'tcx> TyCtxt<'tcx> {
         // the impl is either in the same module as the self-type or
         // as the trait.
         let self_ty = self.lookup_item_type(impl_def_id).ty;
-        let in_self_mod = match self.characteristic_def_id_of_type(self_ty) {
+        let in_self_mod = match characteristic_def_id_of_type(self_ty) {
             None => false,
             Some(ty_def_id) => self.parent_def_id(ty_def_id) == Some(parent_def_id),
         };
@@ -268,38 +269,6 @@ impl<'tcx> TyCtxt<'tcx> {
         buffer.push(&format!("<impl at {}>", span_str));
     }
 
-    /// As a heuristic, when we see an impl, if we see that the
-    /// 'self-type' is a type defined in the same module as the impl,
-    /// we can omit including the path to the impl itself. This
-    /// function tries to find a "characteristic def-id" for a
-    /// type. It's just a heuristic so it makes some questionable
-    /// decisions and we may want to adjust it later.
-    fn characteristic_def_id_of_type(&self, ty: Ty<'tcx>) -> Option<DefId> {
-        match ty.sty {
-            ty::TyStruct(adt_def, _) |
-            ty::TyEnum(adt_def, _) =>
-                Some(adt_def.did),
-
-            ty::TyTrait(ref data) =>
-                Some(data.principal_def_id()),
-
-            ty::TyBox(subty) =>
-                self.characteristic_def_id_of_type(subty),
-
-            ty::TyRawPtr(mt) |
-            ty::TyRef(_, mt) =>
-                self.characteristic_def_id_of_type(mt.ty),
-
-            ty::TyTuple(ref tys) =>
-                tys.iter()
-                   .filter_map(|ty| self.characteristic_def_id_of_type(ty))
-                   .next(),
-
-            _ =>
-                None
-        }
-    }
-
     /// Returns the def-id of `def_id`'s parent in the def tree. If
     /// this returns `None`, then `def_id` represents a crate root or
     /// inlined root.
@@ -309,6 +278,47 @@ impl<'tcx> TyCtxt<'tcx> {
     }
 }
 
+/// As a heuristic, when we see an impl, if we see that the
+/// 'self-type' is a type defined in the same module as the impl,
+/// we can omit including the path to the impl itself. This
+/// function tries to find a "characteristic def-id" for a
+/// type. It's just a heuristic so it makes some questionable
+/// decisions and we may want to adjust it later.
+pub fn characteristic_def_id_of_type<'tcx>(ty: Ty<'tcx>) -> Option<DefId> {
+    match ty.sty {
+        ty::TyStruct(adt_def, _) |
+        ty::TyEnum(adt_def, _) => Some(adt_def.did),
+
+        ty::TyTrait(ref data) => Some(data.principal_def_id()),
+
+        ty::TyArray(subty, _) |
+        ty::TySlice(subty) |
+        ty::TyBox(subty) => characteristic_def_id_of_type(subty),
+
+        ty::TyRawPtr(mt) |
+        ty::TyRef(_, mt) => characteristic_def_id_of_type(mt.ty),
+
+        ty::TyTuple(ref tys) => tys.iter()
+                                   .filter_map(|ty| characteristic_def_id_of_type(ty))
+                                   .next(),
+
+        ty::TyFnDef(def_id, _, _) |
+        ty::TyClosure(def_id, _) => Some(def_id),
+
+        ty::TyBool |
+        ty::TyChar |
+        ty::TyInt(_) |
+        ty::TyUint(_) |
+        ty::TyStr |
+        ty::TyFnPtr(_) |
+        ty::TyProjection(_) |
+        ty::TyParam(_) |
+        ty::TyInfer(_) |
+        ty::TyError |
+        ty::TyFloat(_) => None,
+    }
+}
+
 /// Unifying Trait for different kinds of item paths we might
 /// construct. The basic interface is that components get pushed: the
 /// instance can also customize how we handle the root of a crate.
diff --git a/src/librustc_llvm/lib.rs b/src/librustc_llvm/lib.rs
index 4df2da801f9..a026e546e9c 100644
--- a/src/librustc_llvm/lib.rs
+++ b/src/librustc_llvm/lib.rs
@@ -97,7 +97,7 @@ pub enum Visibility {
 // DLLExportLinkage, GhostLinkage and LinkOnceODRAutoHideLinkage.
 // LinkerPrivateLinkage and LinkerPrivateWeakLinkage are not included either;
 // they've been removed in upstream LLVM commit r203866.
-#[derive(Copy, Clone)]
+#[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub enum Linkage {
     ExternalLinkage = 0,
     AvailableExternallyLinkage = 1,
diff --git a/src/librustc_metadata/def_key.rs b/src/librustc_metadata/def_key.rs
index 95fc932f8e1..05ad333ed3a 100644
--- a/src/librustc_metadata/def_key.rs
+++ b/src/librustc_metadata/def_key.rs
@@ -31,6 +31,7 @@ pub enum DefPathData {
     Impl,
     TypeNs,
     ValueNs,
+    Module,
     MacroDef,
     ClosureExpr,
     TypeParam,
@@ -61,6 +62,7 @@ fn simplify_def_path_data(data: hir_map::DefPathData) -> DefPathData {
         hir_map::DefPathData::Impl => DefPathData::Impl,
         hir_map::DefPathData::TypeNs(_) => DefPathData::TypeNs,
         hir_map::DefPathData::ValueNs(_) => DefPathData::ValueNs,
+        hir_map::DefPathData::Module(_) => DefPathData::Module,
         hir_map::DefPathData::MacroDef(_) => DefPathData::MacroDef,
         hir_map::DefPathData::ClosureExpr => DefPathData::ClosureExpr,
         hir_map::DefPathData::TypeParam(_) => DefPathData::TypeParam,
@@ -91,6 +93,7 @@ fn recover_def_path_data(data: DefPathData, name: Option<Name>) -> hir_map::DefP
         DefPathData::Impl => hir_map::DefPathData::Impl,
         DefPathData::TypeNs => hir_map::DefPathData::TypeNs(name.unwrap()),
         DefPathData::ValueNs => hir_map::DefPathData::ValueNs(name.unwrap()),
+        DefPathData::Module => hir_map::DefPathData::Module(name.unwrap()),
         DefPathData::MacroDef => hir_map::DefPathData::MacroDef(name.unwrap()),
         DefPathData::ClosureExpr => hir_map::DefPathData::ClosureExpr,
         DefPathData::TypeParam => hir_map::DefPathData::TypeParam(name.unwrap()),
diff --git a/src/librustc_trans/base.rs b/src/librustc_trans/base.rs
index 464e5c0cf1c..f084d30e0c0 100644
--- a/src/librustc_trans/base.rs
+++ b/src/librustc_trans/base.rs
@@ -58,6 +58,7 @@ use attributes;
 use build::*;
 use builder::{Builder, noname};
 use callee::{Callee, CallArgs, ArgExprs, ArgVals};
+use partitioning;
 use cleanup::{self, CleanupMethods, DropHint};
 use closure;
 use common::{Block, C_bool, C_bytes_in_context, C_i32, C_int, C_uint, C_integral};
@@ -2958,14 +2959,60 @@ fn collect_translation_items<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>) {
         None => TransItemCollectionMode::Lazy
     };
 
-    let items = time(time_passes, "translation item collection", || {
+    let (items, inlining_map) = time(time_passes, "translation item collection", || {
         collector::collect_crate_translation_items(&ccx, collection_mode)
     });
 
+    let codegen_units = time(time_passes, "codegen unit partitioning", || {
+        partitioning::partition(ccx.tcx(), items.iter().cloned(), &inlining_map)
+    });
+
     if ccx.sess().opts.debugging_opts.print_trans_items.is_some() {
-        let mut item_keys: Vec<_> = items.iter()
-                                         .map(|i| i.to_string(ccx))
-                                         .collect();
+        let mut item_to_cgus = HashMap::new();
+
+        for cgu in codegen_units {
+            for (trans_item, linkage) in cgu.items {
+                item_to_cgus.entry(trans_item)
+                            .or_insert(Vec::new())
+                            .push((cgu.name.clone(), linkage));
+            }
+        }
+
+        let mut item_keys: Vec<_> = items
+            .iter()
+            .map(|i| {
+                let mut output = i.to_string(ccx);
+                output.push_str(" @@");
+                let mut empty = Vec::new();
+                let mut cgus = item_to_cgus.get_mut(i).unwrap_or(&mut empty);
+                cgus.as_mut_slice().sort_by_key(|&(ref name, _)| name.clone());
+                cgus.dedup();
+                for &(ref cgu_name, linkage) in cgus.iter() {
+                    output.push_str(" ");
+                    output.push_str(&cgu_name[..]);
+
+                    let linkage_abbrev = match linkage {
+                        llvm::ExternalLinkage => "External",
+                        llvm::AvailableExternallyLinkage => "Available",
+                        llvm::LinkOnceAnyLinkage => "OnceAny",
+                        llvm::LinkOnceODRLinkage => "OnceODR",
+                        llvm::WeakAnyLinkage => "WeakAny",
+                        llvm::WeakODRLinkage => "WeakODR",
+                        llvm::AppendingLinkage => "Appending",
+                        llvm::InternalLinkage => "Internal",
+                        llvm::PrivateLinkage => "Private",
+                        llvm::ExternalWeakLinkage => "ExternalWeak",
+                        llvm::CommonLinkage => "Common",
+                    };
+
+                    output.push_str("[");
+                    output.push_str(linkage_abbrev);
+                    output.push_str("]");
+                }
+                output
+            })
+            .collect();
+
         item_keys.sort();
 
         for item in item_keys {
diff --git a/src/librustc_trans/collector.rs b/src/librustc_trans/collector.rs
index c72a1a6bef3..e8437393625 100644
--- a/src/librustc_trans/collector.rs
+++ b/src/librustc_trans/collector.rs
@@ -196,7 +196,7 @@ use rustc::hir::def_id::DefId;
 use rustc::middle::lang_items::{ExchangeFreeFnLangItem, ExchangeMallocFnLangItem};
 use rustc::traits;
 use rustc::ty::subst::{self, Substs, Subst};
-use rustc::ty::{self, Ty, TypeFoldable};
+use rustc::ty::{self, Ty, TypeFoldable, TyCtxt};
 use rustc::ty::adjustment::CustomCoerceUnsized;
 use rustc::mir::repr as mir;
 use rustc::mir::visit as mir_visit;
@@ -204,14 +204,15 @@ use rustc::mir::visit::Visitor as MirVisitor;
 
 use syntax::ast::{self, NodeId};
 use syntax::codemap::DUMMY_SP;
-use syntax::errors;
+use syntax::{attr, errors};
 use syntax::parse::token;
 
-use base::custom_coerce_unsize_info;
+use base::{custom_coerce_unsize_info, llvm_linkage_by_name};
 use context::CrateContext;
 use common::{fulfill_obligation, normalize_and_test_predicates,
                     type_is_sized};
 use glue;
+use llvm;
 use meth;
 use monomorphize::{self, Instance};
 use util::nodemap::{FnvHashSet, FnvHashMap, DefIdMap};
@@ -251,9 +252,12 @@ impl<'tcx> Hash for TransItem<'tcx> {
     }
 }
 
+pub type InliningMap<'tcx> = FnvHashMap<TransItem<'tcx>, FnvHashSet<TransItem<'tcx>>>;
+
 pub fn collect_crate_translation_items<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
                                                  mode: TransItemCollectionMode)
-                                                 -> FnvHashSet<TransItem<'tcx>> {
+                                                 -> (FnvHashSet<TransItem<'tcx>>,
+                                                     InliningMap<'tcx>) {
     // We are not tracking dependencies of this pass as it has to be re-executed
     // every time no matter what.
     ccx.tcx().dep_graph.with_ignore(|| {
@@ -262,12 +266,17 @@ pub fn collect_crate_translation_items<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
         debug!("Building translation item graph, beginning at roots");
         let mut visited = FnvHashSet();
         let mut recursion_depths = DefIdMap();
+        let mut inlining_map = FnvHashMap();
 
         for root in roots {
-            collect_items_rec(ccx, root, &mut visited, &mut recursion_depths);
+            collect_items_rec(ccx,
+                              root,
+                              &mut visited,
+                              &mut recursion_depths,
+                              &mut inlining_map);
         }
 
-        visited
+        (visited, inlining_map)
     })
 }
 
@@ -297,7 +306,8 @@ fn collect_roots<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 fn collect_items_rec<'a, 'tcx: 'a>(ccx: &CrateContext<'a, 'tcx>,
                                    starting_point: TransItem<'tcx>,
                                    visited: &mut FnvHashSet<TransItem<'tcx>>,
-                                   recursion_depths: &mut DefIdMap<usize>) {
+                                   recursion_depths: &mut DefIdMap<usize>,
+                                   inlining_map: &mut InliningMap<'tcx>) {
     if !visited.insert(starting_point.clone()) {
         // We've been here already, no need to search again.
         return;
@@ -312,7 +322,11 @@ fn collect_items_rec<'a, 'tcx: 'a>(ccx: &CrateContext<'a, 'tcx>,
             find_drop_glue_neighbors(ccx, t, &mut neighbors);
             recursion_depth_reset = None;
         }
-        TransItem::Static(_) => {
+        TransItem::Static(node_id) => {
+            let def_id = ccx.tcx().map.local_def_id(node_id);
+            let ty = ccx.tcx().lookup_item_type(def_id).ty;
+            let ty = glue::get_drop_glue_type(ccx, ty);
+            neighbors.push(TransItem::DropGlue(ty));
             recursion_depth_reset = None;
         }
         TransItem::Fn(instance) => {
@@ -338,7 +352,8 @@ fn collect_items_rec<'a, 'tcx: 'a>(ccx: &CrateContext<'a, 'tcx>,
     }
 
     for neighbour in neighbors {
-        collect_items_rec(ccx, neighbour, visited, recursion_depths);
+        record_inlined_use(ccx, starting_point, neighbour, inlining_map);
+        collect_items_rec(ccx, neighbour, visited, recursion_depths, inlining_map);
     }
 
     if let Some((def_id, depth)) = recursion_depth_reset {
@@ -348,6 +363,18 @@ fn collect_items_rec<'a, 'tcx: 'a>(ccx: &CrateContext<'a, 'tcx>,
     debug!("END collect_items_rec({})", starting_point.to_string(ccx));
 }
 
+fn record_inlined_use<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
+                                caller: TransItem<'tcx>,
+                                callee: TransItem<'tcx>,
+                                inlining_map: &mut InliningMap<'tcx>) {
+    if callee.is_from_extern_crate() ||
+       callee.requests_inline(ccx.tcx()) {
+        inlining_map.entry(caller)
+                    .or_insert_with(|| FnvHashSet())
+                    .insert(callee);
+    }
+}
+
 fn check_recursion_limit<'a, 'tcx: 'a>(ccx: &CrateContext<'a, 'tcx>,
                                        instance: Instance<'tcx>,
                                        recursion_depths: &mut DefIdMap<usize>)
@@ -1315,7 +1342,7 @@ fn push_instance_as_string<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
     push_type_params(ccx, &instance.substs.types, &[], output);
 }
 
-fn def_id_to_string(ccx: &CrateContext, def_id: DefId) -> String {
+pub fn def_id_to_string(ccx: &CrateContext, def_id: DefId) -> String {
     let mut output = String::new();
     push_item_name(ccx, def_id, &mut output);
     output
@@ -1331,6 +1358,57 @@ fn type_to_string<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 
 impl<'tcx> TransItem<'tcx> {
 
+    pub fn requests_inline(&self, tcx: &TyCtxt<'tcx>) -> bool {
+        match *self {
+            TransItem::Fn(ref instance) => {
+                let attributes = tcx.get_attrs(instance.def);
+                attr::requests_inline(&attributes[..])
+            }
+            TransItem::DropGlue(..) => true,
+            TransItem::Static(..)   => false,
+        }
+    }
+
+    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 is_lazily_instantiated(&self) -> bool {
+        match *self {
+            TransItem::Fn(ref instance) => !instance.substs.types.is_empty(),
+            TransItem::DropGlue(..) => true,
+            TransItem::Static(..)   => false,
+        }
+    }
+
+    pub fn explicit_linkage(&self, tcx: &TyCtxt<'tcx>) -> Option<llvm::Linkage> {
+        let def_id = match *self {
+            TransItem::Fn(ref instance) => instance.def,
+            TransItem::Static(node_id) => tcx.map.local_def_id(node_id),
+            TransItem::DropGlue(..) => return None,
+        };
+
+        let attributes = tcx.get_attrs(def_id);
+        if let Some(name) = attr::first_attr_value_str_by_name(&attributes, "linkage") {
+            if let Some(linkage) = llvm_linkage_by_name(&name) {
+                Some(linkage)
+            } else {
+                let span = tcx.map.span_if_local(def_id);
+                if let Some(span) = span {
+                    tcx.sess.span_fatal(span, "invalid linkage specified")
+                } else {
+                    tcx.sess.fatal(&format!("invalid linkage specified: {}", name))
+                }
+            }
+        } else {
+            None
+        }
+    }
+
     pub fn to_string<'a>(&self, ccx: &CrateContext<'a, 'tcx>) -> String {
         let hir_map = &ccx.tcx().map;
 
diff --git a/src/librustc_trans/lib.rs b/src/librustc_trans/lib.rs
index cb421b6be47..f48409ec755 100644
--- a/src/librustc_trans/lib.rs
+++ b/src/librustc_trans/lib.rs
@@ -103,6 +103,7 @@ mod cabi_x86_win64;
 mod callee;
 mod cleanup;
 mod closure;
+mod collector;
 mod common;
 mod consts;
 mod context;
@@ -120,7 +121,7 @@ mod _match;
 mod meth;
 mod mir;
 mod monomorphize;
-mod collector;
+mod partitioning;
 mod symbol_names_test;
 mod tvec;
 mod type_;
diff --git a/src/librustc_trans/partitioning.rs b/src/librustc_trans/partitioning.rs
new file mode 100644
index 00000000000..f2198c0e490
--- /dev/null
+++ b/src/librustc_trans/partitioning.rs
@@ -0,0 +1,363 @@
+// 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.
+
+//! Partitioning Codegen Units for Incremental Compilation
+//! ======================================================
+//!
+//! The task of this module is to take the complete set of translation items of
+//! a crate and produce a set of codegen units from it, where a codegen unit
+//! is a named set of (translation-item, linkage) pairs. That is, this module
+//! decides which translation item appears in which codegen units with which
+//! linkage. The following paragraphs describe some of the background on the
+//! partitioning scheme.
+//!
+//! The most important opportunity for saving on compilation time with
+//! incremental compilation is to avoid re-translating and re-optimizing code.
+//! Since the unit of translation and optimization for LLVM is "modules" or, how
+//! we call them "codegen units", the particulars of how much time can be saved
+//! by incremental compilation are tightly linked to how the output program is
+//! partitioned into these codegen units prior to passing it to LLVM --
+//! especially because we have to treat codegen units as opaque entities once
+//! they are created: There is no way for us to incrementally update an existing
+//! LLVM module and so we have to build any such module from scratch if it was
+//! affected by some change in the source code.
+//!
+//! From that point of view it would make sense to maximize the number of
+//! codegen units by, for example, putting each function into its own module.
+//! That way only those modules would have to be re-compiled that were actually
+//! affected by some change, minimizing the number of functions that could have
+//! been re-used but just happened to be located in a module that is
+//! re-compiled.
+//!
+//! However, since LLVM optimization does not work across module boundaries,
+//! using such a highly granular partitioning would lead to very slow runtime
+//! code since it would effectively prohibit inlining and other inter-procedure
+//! optimizations. We want to avoid that as much as possible.
+//!
+//! Thus we end up with a trade-off: The bigger the codegen units, the better
+//! LLVM's optimizer can do its work, but also the smaller the compilation time
+//! reduction we get from incremental compilation.
+//!
+//! Ideally, we would create a partitioning such that there are few big codegen
+//! units with few interdependencies between them. For now though, we use the
+//! following heuristic to determine the partitioning:
+//!
+//! - There are two codegen units for every source-level module:
+//! - One for "stable", that is non-generic, code
+//! - One for more "volatile" code, i.e. monomorphized instances of functions
+//!   defined in that module
+//! - Code for monomorphized instances of functions from external crates gets
+//!   placed into every codegen unit that uses that instance.
+//!
+//! In order to see why this heuristic makes sense, let's take a look at when a
+//! codegen unit can get invalidated:
+//!
+//! 1. The most straightforward case is when the BODY of a function or global
+//! changes. Then any codegen unit containing the code for that item has to be
+//! re-compiled. Note that this includes all codegen units where the function
+//! has been inlined.
+//!
+//! 2. The next case is when the SIGNATURE of a function or global changes. In
+//! this case, all codegen units containing a REFERENCE to that item have to be
+//! re-compiled. This is a superset of case 1.
+//!
+//! 3. The final and most subtle case is when a REFERENCE to a generic function
+//! is added or removed somewhere. Even though the definition of the function
+//! might be unchanged, a new REFERENCE might introduce a new monomorphized
+//! instance of this function which has to be placed and compiled somewhere.
+//! Conversely, when removing a REFERENCE, it might have been the last one with
+//! that particular set of generic arguments and thus we have to remove it.
+//!
+//! From the above we see that just using one codegen unit per source-level
+//! module is not such a good idea, since just adding a REFERENCE to some
+//! generic item somewhere else would invalidate everything within the module
+//! containing the generic item. The heuristic above reduces this detrimental
+//! side-effect of references a little by at least not touching the non-generic
+//! code of the module.
+//!
+//! As another optimization, monomorphized functions from external crates get
+//! some special handling. Since we assume that the definition of such a
+//! function changes rather infrequently compared to local items, we can just
+//! instantiate external functions in every codegen unit where it is referenced
+//! -- without having to fear that doing this will cause a lot of unnecessary
+//! re-compilations. If such a reference is added or removed, the codegen unit
+//! has to be re-translated anyway.
+//! (Note that this only makes sense if external crates actually don't change
+//! frequently. For certain multi-crate projects this might not be a valid
+//! assumption).
+//!
+//! A Note on Inlining
+//! ------------------
+//! As briefly mentioned above, in order for LLVM to be able to inline a
+//! function call, the body of the function has to be available in the LLVM
+//! module where the call is made. This has a few consequences for partitioning:
+//!
+//! - The partitioning algorithm has to take care of placing functions into all
+//!   codegen units where they should be available for inlining. It also has to
+//!   decide on the correct linkage for these functions.
+//!
+//! - The partitioning algorithm has to know which functions are likely to get
+//!   inlined, so it can distribute function instantiations accordingly. Since
+//!   there is no way of knowing for sure which functions LLVM will decide to
+//!   inline in the end, we apply a heuristic here: Only functions marked with
+//!   #[inline] and (as stated above) functions from external crates are
+//!   considered for inlining by the partitioner. The current implementation
+//!   will not try to determine if a function is likely to be inlined by looking
+//!   at the functions definition.
+//!
+//! Note though that as a side-effect of creating a codegen units per
+//! source-level module, functions from the same module will be available for
+//! inlining, even when they are not marked #[inline].
+
+use collector::{InliningMap, TransItem};
+use context::CrateContext;
+use monomorphize;
+use rustc::hir::def_id::DefId;
+use rustc::hir::map::DefPathData;
+use rustc::ty::TyCtxt;
+use rustc::ty::item_path::characteristic_def_id_of_type;
+use llvm;
+use syntax::parse::token::{self, InternedString};
+use util::nodemap::{FnvHashMap, FnvHashSet};
+
+pub struct CodegenUnit<'tcx> {
+    pub name: InternedString,
+    pub items: FnvHashMap<TransItem<'tcx>, llvm::Linkage>,
+}
+
+// Anything we can't find a proper codegen unit for goes into this.
+const FALLBACK_CODEGEN_UNIT: &'static str = "__rustc_fallback_codegen_unit";
+
+pub fn partition<'tcx, I>(tcx: &TyCtxt<'tcx>,
+                          trans_items: I,
+                          inlining_map: &InliningMap<'tcx>)
+                          -> Vec<CodegenUnit<'tcx>>
+    where I: Iterator<Item = TransItem<'tcx>>
+{
+    // In the first step, we place all regular translation items into their
+    // respective 'home' codegen unit. Regular translation items are all
+    // functions and statics defined in the local crate.
+    let initial_partitioning = place_root_translation_items(tcx, trans_items);
+
+    // In the next step, we use the inlining map to determine which addtional
+    // translation items have to go into each codegen unit. These additional
+    // translation items can be drop-glue, functions from external crates, and
+    // local functions the definition of which is marked with #[inline].
+    place_inlined_translation_items(initial_partitioning, inlining_map)
+}
+
+struct InitialPartitioning<'tcx> {
+    codegen_units: Vec<CodegenUnit<'tcx>>,
+    roots: FnvHashSet<TransItem<'tcx>>,
+}
+
+fn place_root_translation_items<'tcx, I>(tcx: &TyCtxt<'tcx>,
+                                         trans_items: I)
+                                         -> InitialPartitioning<'tcx>
+    where I: Iterator<Item = TransItem<'tcx>>
+{
+    let mut roots = FnvHashSet();
+    let mut codegen_units = FnvHashMap();
+
+    for trans_item in trans_items {
+        let is_root = match trans_item {
+            TransItem::Static(..) => true,
+            TransItem::DropGlue(..) => false,
+            TransItem::Fn(_) => !trans_item.is_from_extern_crate(),
+        };
+
+        if is_root {
+            let characteristic_def_id = characteristic_def_id_of_trans_item(tcx, trans_item);
+            let is_volatile = trans_item.is_lazily_instantiated();
+
+            let codegen_unit_name = match characteristic_def_id {
+                Some(def_id) => compute_codegen_unit_name(tcx, def_id, is_volatile),
+                None => InternedString::new(FALLBACK_CODEGEN_UNIT),
+            };
+
+            let make_codegen_unit = || {
+                CodegenUnit {
+                    name: codegen_unit_name.clone(),
+                    items: FnvHashMap(),
+                }
+            };
+
+            let mut codegen_unit = codegen_units.entry(codegen_unit_name.clone())
+                                                .or_insert_with(make_codegen_unit);
+
+            let linkage = match trans_item.explicit_linkage(tcx) {
+                Some(explicit_linkage) => explicit_linkage,
+                None => {
+                    match trans_item {
+                        TransItem::Static(..) => llvm::ExternalLinkage,
+                        TransItem::DropGlue(..) => unreachable!(),
+                        // Is there any benefit to using ExternalLinkage?:
+                        TransItem::Fn(..) => llvm::WeakODRLinkage,
+                    }
+                }
+            };
+
+            codegen_unit.items.insert(trans_item, linkage);
+            roots.insert(trans_item);
+        }
+    }
+
+    InitialPartitioning {
+        codegen_units: codegen_units.into_iter()
+                                    .map(|(_, codegen_unit)| codegen_unit)
+                                    .collect(),
+        roots: roots,
+    }
+}
+
+fn place_inlined_translation_items<'tcx>(initial_partitioning: InitialPartitioning<'tcx>,
+                                         inlining_map: &InliningMap<'tcx>)
+                                         -> Vec<CodegenUnit<'tcx>> {
+    let mut final_partitioning = Vec::new();
+
+    for codegen_unit in &initial_partitioning.codegen_units[..] {
+        // Collect all items that need to be available in this codegen unit
+        let mut reachable = FnvHashSet();
+        for root in codegen_unit.items.keys() {
+            follow_inlining(*root, inlining_map, &mut reachable);
+        }
+
+        let mut final_codegen_unit = CodegenUnit {
+            name: codegen_unit.name.clone(),
+            items: FnvHashMap(),
+        };
+
+        // Add all translation items that are not already there
+        for trans_item in reachable {
+            if let Some(linkage) = codegen_unit.items.get(&trans_item) {
+                // This is a root, just copy it over
+                final_codegen_unit.items.insert(trans_item, *linkage);
+            } else {
+                if initial_partitioning.roots.contains(&trans_item) {
+                    // This item will be instantiated in some other codegen unit,
+                    // so we just add it here with AvailableExternallyLinkage
+                    final_codegen_unit.items.insert(trans_item, llvm::AvailableExternallyLinkage);
+                } else {
+                    // We can't be sure if this will also be instantiated
+                    // somewhere else, so we add an instance here with
+                    // LinkOnceODRLinkage. That way the item can be discarded if
+                    // it's not needed (inlined) after all.
+                    final_codegen_unit.items.insert(trans_item, llvm::LinkOnceODRLinkage);
+                }
+            }
+        }
+
+        final_partitioning.push(final_codegen_unit);
+    }
+
+    return final_partitioning;
+
+    fn follow_inlining<'tcx>(trans_item: TransItem<'tcx>,
+                             inlining_map: &InliningMap<'tcx>,
+                             visited: &mut FnvHashSet<TransItem<'tcx>>) {
+        if !visited.insert(trans_item) {
+            return;
+        }
+
+        if let Some(inlined_items) = inlining_map.get(&trans_item) {
+            for &inlined_item in inlined_items {
+                follow_inlining(inlined_item, inlining_map, visited);
+            }
+        }
+    }
+}
+
+fn characteristic_def_id_of_trans_item<'tcx>(tcx: &TyCtxt<'tcx>,
+                                             trans_item: TransItem<'tcx>)
+                                             -> Option<DefId> {
+    match trans_item {
+        TransItem::Fn(instance) => {
+            // 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 let Some(self_ty) = instance.substs.self_ty() {
+                // This is an implementation of a trait method.
+                return characteristic_def_id_of_type(self_ty).or(Some(instance.def));
+            }
+
+            if let Some(impl_def_id) = tcx.impl_of_method(instance.def) {
+                // This is a method within an inherent impl, find out what the
+                // self-type is:
+                let impl_self_ty = tcx.lookup_item_type(impl_def_id).ty;
+                let impl_self_ty = tcx.erase_regions(&impl_self_ty);
+                let impl_self_ty = monomorphize::apply_param_substs(tcx,
+                                                                    instance.substs,
+                                                                    &impl_self_ty);
+
+                if let Some(def_id) = characteristic_def_id_of_type(impl_self_ty) {
+                    return Some(def_id);
+                }
+            }
+
+            Some(instance.def)
+        }
+        TransItem::DropGlue(t) => characteristic_def_id_of_type(t),
+        TransItem::Static(node_id) => Some(tcx.map.local_def_id(node_id)),
+    }
+}
+
+fn compute_codegen_unit_name<'tcx>(tcx: &TyCtxt<'tcx>,
+                                   def_id: DefId,
+                                   volatile: bool)
+                                   -> InternedString {
+    // Unfortunately we cannot just use the `ty::item_path` infrastructure here
+    // because we need paths to modules and the DefIds of those are not
+    // available anymore for external items.
+    let mut mod_path = String::with_capacity(64);
+
+    let def_path = tcx.def_path(def_id);
+    mod_path.push_str(&tcx.crate_name(def_path.krate));
+
+    for part in tcx.def_path(def_id)
+                   .data
+                   .iter()
+                   .take_while(|part| {
+                        match part.data {
+                            DefPathData::Module(..) => true,
+                            _ => false,
+                        }
+                    }) {
+        mod_path.push_str("-");
+        mod_path.push_str(&part.data.as_interned_str());
+    }
+
+    if volatile {
+        mod_path.push_str(".volatile");
+    }
+
+    return token::intern_and_get_ident(&mod_path[..]);
+}
+
+impl<'tcx> CodegenUnit<'tcx> {
+    pub fn _dump<'a>(&self, ccx: &CrateContext<'a, 'tcx>) {
+        println!("CodegenUnit {} (", self.name);
+
+        let mut items: Vec<_> = self.items
+                                    .iter()
+                                    .map(|(trans_item, inst)| {
+                                        format!("{} -- ({:?})", trans_item.to_string(ccx), inst)
+                                    })
+                                    .collect();
+
+        items.as_mut_slice().sort();
+
+        for s in items {
+            println!("  {}", s);
+        }
+
+        println!(")");
+    }
+}
diff --git a/src/test/auxiliary/cgu_explicit_inlining.rs b/src/test/auxiliary/cgu_explicit_inlining.rs
new file mode 100644
index 00000000000..e4ba9fae412
--- /dev/null
+++ b/src/test/auxiliary/cgu_explicit_inlining.rs
@@ -0,0 +1,20 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![crate_type = "lib"]
+
+#[inline]
+pub fn inlined() {}
+
+#[inline(always)]
+pub fn always_inlined() {}
+
+#[inline(never)]
+pub fn never_inlined() {}
diff --git a/src/test/auxiliary/cgu_extern_drop_glue.rs b/src/test/auxiliary/cgu_extern_drop_glue.rs
new file mode 100644
index 00000000000..049bdb46579
--- /dev/null
+++ b/src/test/auxiliary/cgu_extern_drop_glue.rs
@@ -0,0 +1,17 @@
+// Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![crate_type = "lib"]
+
+pub struct Struct(pub u32);
+
+impl Drop for Struct {
+    fn drop(&mut self) {}
+}
diff --git a/src/test/auxiliary/cgu_generic_function.rs b/src/test/auxiliary/cgu_generic_function.rs
index 83bb65bc2b7..04c68748eca 100644
--- a/src/test/auxiliary/cgu_generic_function.rs
+++ b/src/test/auxiliary/cgu_generic_function.rs
@@ -12,12 +12,13 @@
 
 struct Struct(u32);
 
+#[inline(never)]
 pub fn foo<T>(x: T) -> (T, u32, i8) {
     let (x, Struct(y)) = bar(x);
     (x, y, 2)
 }
 
-
+#[inline(never)]
 fn bar<T>(x: T) -> (T, Struct) {
     let _ = not_exported_and_not_generic(0);
     (x, Struct(1))
diff --git a/src/test/codegen-units/partitioning/extern-drop-glue.rs b/src/test/codegen-units/partitioning/extern-drop-glue.rs
new file mode 100644
index 00000000000..ddf5f461aef
--- /dev/null
+++ b/src/test/codegen-units/partitioning/extern-drop-glue.rs
@@ -0,0 +1,43 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=lazy
+
+#![allow(dead_code)]
+#![crate_type="lib"]
+
+// aux-build:cgu_extern_drop_glue.rs
+extern crate cgu_extern_drop_glue;
+
+//~ TRANS_ITEM drop-glue cgu_extern_drop_glue::Struct[0] @@ extern_drop_glue[OnceODR] extern_drop_glue-mod1[OnceODR]
+
+struct LocalStruct(cgu_extern_drop_glue::Struct);
+
+//~ TRANS_ITEM fn extern_drop_glue::user[0] @@ extern_drop_glue[WeakODR]
+fn user()
+{
+    //~ TRANS_ITEM drop-glue extern_drop_glue::LocalStruct[0] @@ extern_drop_glue[OnceODR]
+    let _ = LocalStruct(cgu_extern_drop_glue::Struct(0));
+}
+
+mod mod1 {
+    use cgu_extern_drop_glue;
+
+    struct LocalStruct(cgu_extern_drop_glue::Struct);
+
+    //~ TRANS_ITEM fn extern_drop_glue::mod1[0]::user[0] @@ extern_drop_glue-mod1[WeakODR]
+    fn user()
+    {
+        //~ TRANS_ITEM drop-glue extern_drop_glue::mod1[0]::LocalStruct[0] @@ extern_drop_glue-mod1[OnceODR]
+        let _ = LocalStruct(cgu_extern_drop_glue::Struct(0));
+    }
+}
+
diff --git a/src/test/codegen-units/partitioning/extern-generic.rs b/src/test/codegen-units/partitioning/extern-generic.rs
new file mode 100644
index 00000000000..71af676b0a9
--- /dev/null
+++ b/src/test/codegen-units/partitioning/extern-generic.rs
@@ -0,0 +1,62 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=eager
+
+#![allow(dead_code)]
+#![crate_type="lib"]
+
+// aux-build:cgu_generic_function.rs
+extern crate cgu_generic_function;
+
+//~ TRANS_ITEM fn extern_generic::user[0] @@ extern_generic[WeakODR]
+fn user() {
+    let _ = cgu_generic_function::foo("abc");
+}
+
+mod mod1 {
+    use cgu_generic_function;
+
+    //~ TRANS_ITEM fn extern_generic::mod1[0]::user[0] @@ extern_generic-mod1[WeakODR]
+    fn user() {
+        let _ = cgu_generic_function::foo("abc");
+    }
+
+    mod mod1 {
+        use cgu_generic_function;
+
+        //~ TRANS_ITEM fn extern_generic::mod1[0]::mod1[0]::user[0] @@ extern_generic-mod1-mod1[WeakODR]
+        fn user() {
+            let _ = cgu_generic_function::foo("abc");
+        }
+    }
+}
+
+mod mod2 {
+    use cgu_generic_function;
+
+    //~ TRANS_ITEM fn extern_generic::mod2[0]::user[0] @@ extern_generic-mod2[WeakODR]
+    fn user() {
+        let _ = cgu_generic_function::foo("abc");
+    }
+}
+
+mod mod3 {
+    //~ TRANS_ITEM fn extern_generic::mod3[0]::non_user[0] @@ extern_generic-mod3[WeakODR]
+    fn non_user() {}
+}
+
+// Make sure the two generic functions from the extern crate get instantiated
+// privately in every module they are use in.
+//~ TRANS_ITEM fn cgu_generic_function::foo[0]<&str> @@ extern_generic[OnceODR] extern_generic-mod1[OnceODR] extern_generic-mod2[OnceODR] extern_generic-mod1-mod1[OnceODR]
+//~ TRANS_ITEM fn cgu_generic_function::bar[0]<&str> @@ extern_generic[OnceODR] extern_generic-mod1[OnceODR] extern_generic-mod2[OnceODR] extern_generic-mod1-mod1[OnceODR]
+
+//~ TRANS_ITEM drop-glue i8
diff --git a/src/test/codegen-units/partitioning/inlining-from-extern-crate.rs b/src/test/codegen-units/partitioning/inlining-from-extern-crate.rs
new file mode 100644
index 00000000000..f4732a7bcf8
--- /dev/null
+++ b/src/test/codegen-units/partitioning/inlining-from-extern-crate.rs
@@ -0,0 +1,61 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=lazy
+
+#![crate_type="lib"]
+
+// aux-build:cgu_explicit_inlining.rs
+extern crate cgu_explicit_inlining;
+
+// This test makes sure that items inlined from external crates are privately
+// instantiated in every codegen unit they are used in.
+
+//~ TRANS_ITEM fn cgu_explicit_inlining::inlined[0] @@ inlining_from_extern_crate[OnceODR] inlining_from_extern_crate-mod1[OnceODR]
+//~ TRANS_ITEM fn cgu_explicit_inlining::always_inlined[0] @@ inlining_from_extern_crate[OnceODR] inlining_from_extern_crate-mod2[OnceODR]
+
+//~ TRANS_ITEM fn inlining_from_extern_crate::user[0] @@ inlining_from_extern_crate[WeakODR]
+pub fn user()
+{
+    cgu_explicit_inlining::inlined();
+    cgu_explicit_inlining::always_inlined();
+
+    // does not generate a translation item in this crate
+    cgu_explicit_inlining::never_inlined();
+}
+
+mod mod1 {
+    use cgu_explicit_inlining;
+
+    //~ TRANS_ITEM fn inlining_from_extern_crate::mod1[0]::user[0] @@ inlining_from_extern_crate-mod1[WeakODR]
+    pub fn user()
+    {
+        cgu_explicit_inlining::inlined();
+
+        // does not generate a translation item in this crate
+        cgu_explicit_inlining::never_inlined();
+    }
+}
+
+mod mod2 {
+    use cgu_explicit_inlining;
+
+    //~ TRANS_ITEM fn inlining_from_extern_crate::mod2[0]::user[0] @@ inlining_from_extern_crate-mod2[WeakODR]
+    pub fn user()
+    {
+        cgu_explicit_inlining::always_inlined();
+
+        // does not generate a translation item in this crate
+        cgu_explicit_inlining::never_inlined();
+    }
+}
+
+//~ TRANS_ITEM drop-glue i8
diff --git a/src/test/codegen-units/partitioning/local-drop-glue.rs b/src/test/codegen-units/partitioning/local-drop-glue.rs
new file mode 100644
index 00000000000..0c500bb64f8
--- /dev/null
+++ b/src/test/codegen-units/partitioning/local-drop-glue.rs
@@ -0,0 +1,61 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=lazy
+
+#![allow(dead_code)]
+#![crate_type="lib"]
+
+//~ TRANS_ITEM drop-glue local_drop_glue::Struct[0] @@ local_drop_glue[OnceODR] local_drop_glue-mod1[OnceODR]
+struct Struct {
+    _a: u32
+}
+
+impl Drop for Struct {
+    //~ TRANS_ITEM fn local_drop_glue::{{impl}}[0]::drop[0] @@ local_drop_glue[WeakODR]
+    fn drop(&mut self) {}
+}
+
+//~ TRANS_ITEM drop-glue local_drop_glue::Outer[0] @@ local_drop_glue[OnceODR]
+struct Outer {
+    _a: Struct
+}
+
+//~ TRANS_ITEM fn local_drop_glue::user[0] @@ local_drop_glue[WeakODR]
+fn user()
+{
+    let _ = Outer {
+        _a: Struct {
+            _a: 0
+        }
+    };
+}
+
+mod mod1
+{
+    use super::Struct;
+
+    //~ TRANS_ITEM drop-glue local_drop_glue::mod1[0]::Struct2[0] @@ local_drop_glue-mod1[OnceODR]
+    struct Struct2 {
+        _a: Struct,
+        //~ TRANS_ITEM drop-glue (u32, local_drop_glue::Struct[0]) @@ local_drop_glue-mod1[OnceODR]
+        _b: (u32, Struct),
+    }
+
+    //~ TRANS_ITEM fn local_drop_glue::mod1[0]::user[0] @@ local_drop_glue-mod1[WeakODR]
+    fn user()
+    {
+        let _ = Struct2 {
+            _a: Struct { _a: 0 },
+            _b: (0, Struct { _a: 0 }),
+        };
+    }
+}
diff --git a/src/test/codegen-units/partitioning/local-generic.rs b/src/test/codegen-units/partitioning/local-generic.rs
new file mode 100644
index 00000000000..08c8ff0cb2f
--- /dev/null
+++ b/src/test/codegen-units/partitioning/local-generic.rs
@@ -0,0 +1,58 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=eager
+
+#![allow(dead_code)]
+#![crate_type="lib"]
+
+// Used in different modules/codegen units but always instantiated in the same
+// codegen unit.
+
+//~ TRANS_ITEM fn local_generic::generic[0]<u32> @@ local_generic.volatile[WeakODR]
+//~ TRANS_ITEM fn local_generic::generic[0]<u64> @@ local_generic.volatile[WeakODR]
+//~ TRANS_ITEM fn local_generic::generic[0]<char> @@ local_generic.volatile[WeakODR]
+//~ TRANS_ITEM fn local_generic::generic[0]<&str> @@ local_generic.volatile[WeakODR]
+pub fn generic<T>(x: T) -> T { x }
+
+//~ TRANS_ITEM fn local_generic::user[0] @@ local_generic[WeakODR]
+fn user() {
+    let _ = generic(0u32);
+}
+
+mod mod1 {
+    pub use super::generic;
+
+    //~ TRANS_ITEM fn local_generic::mod1[0]::user[0] @@ local_generic-mod1[WeakODR]
+    fn user() {
+        let _ = generic(0u64);
+    }
+
+    mod mod1 {
+        use super::generic;
+
+        //~ TRANS_ITEM fn local_generic::mod1[0]::mod1[0]::user[0] @@ local_generic-mod1-mod1[WeakODR]
+        fn user() {
+            let _ = generic('c');
+        }
+    }
+}
+
+mod mod2 {
+    use super::generic;
+
+    //~ TRANS_ITEM fn local_generic::mod2[0]::user[0] @@ local_generic-mod2[WeakODR]
+    fn user() {
+        let _ = generic("abc");
+    }
+}
+
+//~ TRANS_ITEM drop-glue i8
diff --git a/src/test/codegen-units/partitioning/local-inlining.rs b/src/test/codegen-units/partitioning/local-inlining.rs
new file mode 100644
index 00000000000..dfd8f725b61
--- /dev/null
+++ b/src/test/codegen-units/partitioning/local-inlining.rs
@@ -0,0 +1,54 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=lazy
+
+#![allow(dead_code)]
+#![crate_type="lib"]
+
+mod inline {
+
+    // Important: This function should show up in all codegen units where it is inlined
+    //~ TRANS_ITEM fn local_inlining::inline[0]::inlined_function[0] @@ local_inlining-inline[WeakODR] local_inlining-user1[Available] local_inlining-user2[Available]
+    #[inline(always)]
+    pub fn inlined_function()
+    {
+
+    }
+}
+
+mod user1 {
+    use super::inline;
+
+    //~ TRANS_ITEM fn local_inlining::user1[0]::foo[0] @@ local_inlining-user1[WeakODR]
+    fn foo() {
+        inline::inlined_function();
+    }
+}
+
+mod user2 {
+    use super::inline;
+
+    //~ TRANS_ITEM fn local_inlining::user2[0]::bar[0] @@ local_inlining-user2[WeakODR]
+    fn bar() {
+        inline::inlined_function();
+    }
+}
+
+mod non_user {
+
+    //~ TRANS_ITEM fn local_inlining::non_user[0]::baz[0] @@ local_inlining-non_user[WeakODR]
+    fn baz() {
+
+    }
+}
+
+//~ TRANS_ITEM drop-glue i8
diff --git a/src/test/codegen-units/partitioning/local-transitive-inlining.rs b/src/test/codegen-units/partitioning/local-transitive-inlining.rs
new file mode 100644
index 00000000000..ea3a1cd34be
--- /dev/null
+++ b/src/test/codegen-units/partitioning/local-transitive-inlining.rs
@@ -0,0 +1,54 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=lazy
+
+#![allow(dead_code)]
+#![crate_type="lib"]
+
+mod inline {
+
+    //~ TRANS_ITEM fn local_transitive_inlining::inline[0]::inlined_function[0] @@ local_transitive_inlining-inline[WeakODR] local_transitive_inlining-direct_user[Available] local_transitive_inlining-indirect_user[Available]
+    #[inline(always)]
+    pub fn inlined_function()
+    {
+
+    }
+}
+
+mod direct_user {
+    use super::inline;
+
+    //~ TRANS_ITEM fn local_transitive_inlining::direct_user[0]::foo[0] @@ local_transitive_inlining-direct_user[WeakODR] local_transitive_inlining-indirect_user[Available]
+    #[inline(always)]
+    pub fn foo() {
+        inline::inlined_function();
+    }
+}
+
+mod indirect_user {
+    use super::direct_user;
+
+    //~ TRANS_ITEM fn local_transitive_inlining::indirect_user[0]::bar[0] @@ local_transitive_inlining-indirect_user[WeakODR]
+    fn bar() {
+        direct_user::foo();
+    }
+}
+
+mod non_user {
+
+    //~ TRANS_ITEM fn local_transitive_inlining::non_user[0]::baz[0] @@ local_transitive_inlining-non_user[WeakODR]
+    fn baz() {
+
+    }
+}
+
+//~ TRANS_ITEM drop-glue i8
diff --git a/src/test/codegen-units/partitioning/methods-are-with-self-type.rs b/src/test/codegen-units/partitioning/methods-are-with-self-type.rs
new file mode 100644
index 00000000000..51d2d53f24a
--- /dev/null
+++ b/src/test/codegen-units/partitioning/methods-are-with-self-type.rs
@@ -0,0 +1,78 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=lazy
+
+#![allow(dead_code)]
+
+struct SomeType;
+
+struct SomeGenericType<T1, T2>(T1, T2);
+
+mod mod1 {
+    use super::{SomeType, SomeGenericType};
+
+    // Even though the impl is in `mod1`, the methods should end up in the
+    // parent module, since that is where their self-type is.
+    impl SomeType {
+        //~ TRANS_ITEM fn methods_are_with_self_type::mod1[0]::{{impl}}[0]::method[0] @@ methods_are_with_self_type[WeakODR]
+        fn method(&self) {}
+
+        //~ TRANS_ITEM fn methods_are_with_self_type::mod1[0]::{{impl}}[0]::associated_fn[0] @@ methods_are_with_self_type[WeakODR]
+        fn associated_fn() {}
+    }
+
+    impl<T1, T2> SomeGenericType<T1, T2> {
+        pub fn method(&self) {}
+        pub fn associated_fn(_: T1, _: T2) {}
+    }
+}
+
+trait Trait {
+    fn foo(&self);
+    fn default(&self) {}
+}
+
+// We provide an implementation of `Trait` for all types. The corresponding
+// monomorphizations should end up in whichever module the concrete `T` is.
+impl<T> Trait for T
+{
+    fn foo(&self) {}
+}
+
+mod type1 {
+    pub struct Struct;
+}
+
+mod type2 {
+    pub struct Struct;
+}
+
+//~ TRANS_ITEM fn methods_are_with_self_type::main[0]
+fn main()
+{
+    //~ TRANS_ITEM fn methods_are_with_self_type::mod1[0]::{{impl}}[1]::method[0]<u32, u64> @@ methods_are_with_self_type.volatile[WeakODR]
+    SomeGenericType(0u32, 0u64).method();
+    //~ TRANS_ITEM fn methods_are_with_self_type::mod1[0]::{{impl}}[1]::associated_fn[0]<char, &str> @@ methods_are_with_self_type.volatile[WeakODR]
+    SomeGenericType::associated_fn('c', "&str");
+
+    //~ TRANS_ITEM fn methods_are_with_self_type::{{impl}}[0]::foo[0]<methods_are_with_self_type::type1[0]::Struct[0]> @@ methods_are_with_self_type-type1.volatile[WeakODR]
+    type1::Struct.foo();
+    //~ TRANS_ITEM fn methods_are_with_self_type::{{impl}}[0]::foo[0]<methods_are_with_self_type::type2[0]::Struct[0]> @@ methods_are_with_self_type-type2.volatile[WeakODR]
+    type2::Struct.foo();
+
+    //~ TRANS_ITEM fn methods_are_with_self_type::Trait[0]::default[0]<methods_are_with_self_type::type1[0]::Struct[0]> @@ methods_are_with_self_type-type1.volatile[WeakODR]
+    type1::Struct.default();
+    //~ TRANS_ITEM fn methods_are_with_self_type::Trait[0]::default[0]<methods_are_with_self_type::type2[0]::Struct[0]> @@ methods_are_with_self_type-type2.volatile[WeakODR]
+    type2::Struct.default();
+}
+
+//~ TRANS_ITEM drop-glue i8
diff --git a/src/test/codegen-units/partitioning/regular-modules.rs b/src/test/codegen-units/partitioning/regular-modules.rs
new file mode 100644
index 00000000000..a761cab2e44
--- /dev/null
+++ b/src/test/codegen-units/partitioning/regular-modules.rs
@@ -0,0 +1,82 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=eager
+
+#![allow(dead_code)]
+#![crate_type="lib"]
+
+//~ TRANS_ITEM fn regular_modules::foo[0] @@ regular_modules[WeakODR]
+fn foo() {}
+
+//~ TRANS_ITEM fn regular_modules::bar[0] @@ regular_modules[WeakODR]
+fn bar() {}
+
+//~ TRANS_ITEM static regular_modules::BAZ[0] @@ regular_modules[External]
+static BAZ: u64 = 0;
+
+mod mod1 {
+
+    //~ TRANS_ITEM fn regular_modules::mod1[0]::foo[0] @@ regular_modules-mod1[WeakODR]
+    fn foo() {}
+    //~ TRANS_ITEM fn regular_modules::mod1[0]::bar[0] @@ regular_modules-mod1[WeakODR]
+    fn bar() {}
+    //~ TRANS_ITEM static regular_modules::mod1[0]::BAZ[0] @@ regular_modules-mod1[External]
+    static BAZ: u64 = 0;
+
+    mod mod1 {
+        //~ TRANS_ITEM fn regular_modules::mod1[0]::mod1[0]::foo[0] @@ regular_modules-mod1-mod1[WeakODR]
+        fn foo() {}
+        //~ TRANS_ITEM fn regular_modules::mod1[0]::mod1[0]::bar[0] @@ regular_modules-mod1-mod1[WeakODR]
+        fn bar() {}
+        //~ TRANS_ITEM static regular_modules::mod1[0]::mod1[0]::BAZ[0] @@ regular_modules-mod1-mod1[External]
+        static BAZ: u64 = 0;
+    }
+
+    mod mod2 {
+        //~ TRANS_ITEM fn regular_modules::mod1[0]::mod2[0]::foo[0] @@ regular_modules-mod1-mod2[WeakODR]
+        fn foo() {}
+        //~ TRANS_ITEM fn regular_modules::mod1[0]::mod2[0]::bar[0] @@ regular_modules-mod1-mod2[WeakODR]
+        fn bar() {}
+        //~ TRANS_ITEM static regular_modules::mod1[0]::mod2[0]::BAZ[0] @@ regular_modules-mod1-mod2[External]
+        static BAZ: u64 = 0;
+    }
+}
+
+mod mod2 {
+
+    //~ TRANS_ITEM fn regular_modules::mod2[0]::foo[0] @@ regular_modules-mod2[WeakODR]
+    fn foo() {}
+    //~ TRANS_ITEM fn regular_modules::mod2[0]::bar[0] @@ regular_modules-mod2[WeakODR]
+    fn bar() {}
+    //~ TRANS_ITEM static regular_modules::mod2[0]::BAZ[0] @@ regular_modules-mod2[External]
+    static BAZ: u64 = 0;
+
+    mod mod1 {
+        //~ TRANS_ITEM fn regular_modules::mod2[0]::mod1[0]::foo[0] @@ regular_modules-mod2-mod1[WeakODR]
+        fn foo() {}
+        //~ TRANS_ITEM fn regular_modules::mod2[0]::mod1[0]::bar[0] @@ regular_modules-mod2-mod1[WeakODR]
+        fn bar() {}
+        //~ TRANS_ITEM static regular_modules::mod2[0]::mod1[0]::BAZ[0] @@ regular_modules-mod2-mod1[External]
+        static BAZ: u64 = 0;
+    }
+
+    mod mod2 {
+        //~ TRANS_ITEM fn regular_modules::mod2[0]::mod2[0]::foo[0] @@ regular_modules-mod2-mod2[WeakODR]
+        fn foo() {}
+        //~ TRANS_ITEM fn regular_modules::mod2[0]::mod2[0]::bar[0] @@ regular_modules-mod2-mod2[WeakODR]
+        fn bar() {}
+        //~ TRANS_ITEM static regular_modules::mod2[0]::mod2[0]::BAZ[0] @@ regular_modules-mod2-mod2[External]
+        static BAZ: u64 = 0;
+    }
+}
+
+//~ TRANS_ITEM drop-glue i8
diff --git a/src/test/codegen-units/partitioning/statics.rs b/src/test/codegen-units/partitioning/statics.rs
new file mode 100644
index 00000000000..ac6a0c55d4f
--- /dev/null
+++ b/src/test/codegen-units/partitioning/statics.rs
@@ -0,0 +1,48 @@
+// 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.
+
+// ignore-tidy-linelength
+// compile-flags:-Zprint-trans-items=lazy
+
+#![crate_type="lib"]
+
+//~ TRANS_ITEM static statics::FOO[0] @@ statics[External]
+static FOO: u32 = 0;
+
+//~ TRANS_ITEM static statics::BAR[0] @@ statics[External]
+static BAR: u32 = 0;
+
+//~ TRANS_ITEM fn statics::function[0] @@ statics[WeakODR]
+fn function() {
+    //~ TRANS_ITEM static statics::function[0]::FOO[0] @@ statics[External]
+    static FOO: u32 = 0;
+
+    //~ TRANS_ITEM static statics::function[0]::BAR[0] @@ statics[External]
+    static BAR: u32 = 0;
+}
+
+mod mod1 {
+    //~ TRANS_ITEM static statics::mod1[0]::FOO[0] @@ statics-mod1[External]
+    static FOO: u32 = 0;
+
+    //~ TRANS_ITEM static statics::mod1[0]::BAR[0] @@ statics-mod1[External]
+    static BAR: u32 = 0;
+
+    //~ TRANS_ITEM fn statics::mod1[0]::function[0] @@ statics-mod1[WeakODR]
+    fn function() {
+        //~ TRANS_ITEM static statics::mod1[0]::function[0]::FOO[0] @@ statics-mod1[External]
+        static FOO: u32 = 0;
+
+        //~ TRANS_ITEM static statics::mod1[0]::function[0]::BAR[0] @@ statics-mod1[External]
+        static BAR: u32 = 0;
+    }
+}
+
+//~ TRANS_ITEM drop-glue i8