Replace Rc with Lrc for shared data

86 files changed, 435 insertions, 413 deletions

diff --git a/src/Cargo.lock b/src/Cargo.lock
index 2cc647c49c6..7b4bfecea3f 100644
--- a/src/Cargo.lock
+++ b/src/Cargo.lock
@@ -1407,6 +1407,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 name = "proc_macro"
 version = "0.0.0"
 dependencies = [
+ "rustc_data_structures 0.0.0",
  "rustc_errors 0.0.0",
  "syntax 0.0.0",
  "syntax_pos 0.0.0",
@@ -1833,6 +1834,7 @@ dependencies = [
  "graphviz 0.0.0",
  "log 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc 0.0.0",
+ "rustc_data_structures 0.0.0",
  "rustc_errors 0.0.0",
  "rustc_mir 0.0.0",
  "syntax 0.0.0",
@@ -2029,6 +2031,7 @@ dependencies = [
  "rustc 0.0.0",
  "rustc_const_eval 0.0.0",
  "rustc_const_math 0.0.0",
+ "rustc_data_structures 0.0.0",
  "rustc_errors 0.0.0",
  "syntax 0.0.0",
  "syntax_pos 0.0.0",
@@ -2054,6 +2057,7 @@ name = "rustc_privacy"
 version = "0.0.0"
 dependencies = [
  "rustc 0.0.0",
+ "rustc_data_structures 0.0.0",
  "rustc_typeck 0.0.0",
  "syntax 0.0.0",
  "syntax_pos 0.0.0",
@@ -2445,6 +2449,7 @@ version = "0.0.0"
 dependencies = [
  "fmt_macros 0.0.0",
  "proc_macro 0.0.0",
+ "rustc_data_structures 0.0.0",
  "rustc_errors 0.0.0",
  "syntax 0.0.0",
  "syntax_pos 0.0.0",
diff --git a/src/libproc_macro/Cargo.toml b/src/libproc_macro/Cargo.toml
index cfd83e348a8..c1b2622520b 100644
--- a/src/libproc_macro/Cargo.toml
+++ b/src/libproc_macro/Cargo.toml
@@ -11,3 +11,4 @@ crate-type = ["dylib"]
 syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
 rustc_errors = { path = "../librustc_errors" }
+rustc_data_structures = { path = "../librustc_data_structures" }
diff --git a/src/libproc_macro/lib.rs b/src/libproc_macro/lib.rs
index b18bb5a24b6..cf1d4024373 100644
--- a/src/libproc_macro/lib.rs
+++ b/src/libproc_macro/lib.rs
@@ -43,6 +43,7 @@
 extern crate syntax;
 extern crate syntax_pos;
 extern crate rustc_errors;
+extern crate rustc_data_structures;
 
 mod diagnostic;
 
@@ -50,7 +51,7 @@ mod diagnostic;
 pub use diagnostic::{Diagnostic, Level};
 
 use std::{ascii, fmt, iter};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::str::FromStr;
 
 use syntax::ast;
@@ -306,7 +307,7 @@ pub struct LineColumn {
 #[unstable(feature = "proc_macro", issue = "38356")]
 #[derive(Clone)]
 pub struct SourceFile {
-    filemap: Rc<FileMap>,
+    filemap: Lrc<FileMap>,
 }
 
 impl SourceFile {
@@ -356,7 +357,7 @@ impl fmt::Debug for SourceFile {
 #[unstable(feature = "proc_macro", issue = "38356")]
 impl PartialEq for SourceFile {
     fn eq(&self, other: &Self) -> bool {
-        Rc::ptr_eq(&self.filemap, &other.filemap)
+        Lrc::ptr_eq(&self.filemap, &other.filemap)
     }
 }
 
diff --git a/src/librustc/dep_graph/graph.rs b/src/librustc/dep_graph/graph.rs
index 61a8fb09118..07c6c85b89d 100644
--- a/src/librustc/dep_graph/graph.rs
+++ b/src/librustc/dep_graph/graph.rs
@@ -13,10 +13,10 @@ use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
                                            StableHashingContextProvider};
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
+use rustc_data_structures::sync::Lrc;
 use std::cell::{Ref, RefCell};
 use std::env;
 use std::hash::Hash;
-use std::rc::Rc;
 use ty::TyCtxt;
 use util::common::{ProfileQueriesMsg, profq_msg};
 
@@ -32,13 +32,13 @@ use super::prev::PreviousDepGraph;
 
 #[derive(Clone)]
 pub struct DepGraph {
-    data: Option<Rc<DepGraphData>>,
+    data: Option<Lrc<DepGraphData>>,
 
     // A vector mapping depnodes from the current graph to their associated
     // result value fingerprints. Do not rely on the length of this vector
     // being the same as the number of nodes in the graph. The vector can
     // contain an arbitrary number of zero-entries at the end.
-    fingerprints: Rc<RefCell<IndexVec<DepNodeIndex, Fingerprint>>>
+    fingerprints: Lrc<RefCell<IndexVec<DepNodeIndex, Fingerprint>>>
 }
 
 
@@ -102,7 +102,7 @@ impl DepGraph {
         let fingerprints = IndexVec::from_elem_n(Fingerprint::ZERO,
                                                  (prev_graph_node_count * 115) / 100);
         DepGraph {
-            data: Some(Rc::new(DepGraphData {
+            data: Some(Lrc::new(DepGraphData {
                 previous_work_products: RefCell::new(FxHashMap()),
                 work_products: RefCell::new(FxHashMap()),
                 dep_node_debug: RefCell::new(FxHashMap()),
@@ -111,14 +111,14 @@ impl DepGraph {
                 colors: RefCell::new(DepNodeColorMap::new(prev_graph_node_count)),
                 loaded_from_cache: RefCell::new(FxHashMap()),
             })),
-            fingerprints: Rc::new(RefCell::new(fingerprints)),
+            fingerprints: Lrc::new(RefCell::new(fingerprints)),
         }
     }
 
     pub fn new_disabled() -> DepGraph {
         DepGraph {
             data: None,
-            fingerprints: Rc::new(RefCell::new(IndexVec::new())),
+            fingerprints: Lrc::new(RefCell::new(IndexVec::new())),
         }
     }
 
diff --git a/src/librustc/ich/caching_codemap_view.rs b/src/librustc/ich/caching_codemap_view.rs
index 3caf308d652..e5bf384d253 100644
--- a/src/librustc/ich/caching_codemap_view.rs
+++ b/src/librustc/ich/caching_codemap_view.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::codemap::CodeMap;
 use syntax_pos::{BytePos, FileMap};
 
@@ -18,7 +18,7 @@ struct CacheEntry {
     line_number: usize,
     line_start: BytePos,
     line_end: BytePos,
-    file: Rc<FileMap>,
+    file: Lrc<FileMap>,
     file_index: usize,
 }
 
@@ -51,7 +51,7 @@ impl<'cm> CachingCodemapView<'cm> {
 
     pub fn byte_pos_to_line_and_col(&mut self,
                                     pos: BytePos)
-                                    -> Option<(Rc<FileMap>, usize, BytePos)> {
+                                    -> Option<(Lrc<FileMap>, usize, BytePos)> {
         self.time_stamp += 1;
 
         // Check if the position is in one of the cached lines
diff --git a/src/librustc/lint/mod.rs b/src/librustc/lint/mod.rs
index a51d06c06ed..edea87c888c 100644
--- a/src/librustc/lint/mod.rs
+++ b/src/librustc/lint/mod.rs
@@ -31,7 +31,7 @@
 pub use self::Level::*;
 pub use self::LintSource::*;
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 use errors::{DiagnosticBuilder, DiagnosticId};
 use hir::def_id::{CrateNum, LOCAL_CRATE};
@@ -505,7 +505,7 @@ pub fn struct_lint_level<'a>(sess: &'a Session,
 }
 
 fn lint_levels<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, cnum: CrateNum)
-    -> Rc<LintLevelMap>
+    -> Lrc<LintLevelMap>
 {
     assert_eq!(cnum, LOCAL_CRATE);
     let mut builder = LintLevelMapBuilder {
@@ -518,7 +518,7 @@ fn lint_levels<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, cnum: CrateNum)
         intravisit::walk_crate(builder, krate);
     });
 
-    Rc::new(builder.levels.build_map())
+    Lrc::new(builder.levels.build_map())
 }
 
 struct LintLevelMapBuilder<'a, 'tcx: 'a> {
diff --git a/src/librustc/middle/cstore.rs b/src/librustc/middle/cstore.rs
index 9708afd2045..7f068e8f71b 100644
--- a/src/librustc/middle/cstore.rs
+++ b/src/librustc/middle/cstore.rs
@@ -37,13 +37,13 @@ use util::nodemap::NodeSet;
 use std::any::Any;
 use std::collections::BTreeMap;
 use std::path::{Path, PathBuf};
-use std::rc::Rc;
 use rustc_data_structures::owning_ref::ErasedBoxRef;
 use syntax::ast;
 use syntax::ext::base::SyntaxExtension;
 use syntax::symbol::Symbol;
 use syntax_pos::Span;
 use rustc_back::target::Target;
+use rustc_data_structures::sync::Lrc;
 
 pub use self::NativeLibraryKind::*;
 
@@ -139,7 +139,7 @@ pub struct NativeLibrary {
 
 pub enum LoadedMacro {
     MacroDef(ast::Item),
-    ProcMacro(Rc<SyntaxExtension>),
+    ProcMacro(Lrc<SyntaxExtension>),
 }
 
 #[derive(Copy, Clone, Debug)]
@@ -206,7 +206,7 @@ pub struct ExternConstBody<'tcx> {
 
 #[derive(Clone)]
 pub struct ExternBodyNestedBodies {
-    pub nested_bodies: Rc<BTreeMap<hir::BodyId, hir::Body>>,
+    pub nested_bodies: Lrc<BTreeMap<hir::BodyId, hir::Body>>,
 
     // It would require a lot of infrastructure to enable stable-hashing Bodies
     // from other crates, so we hash on export and just store the fingerprint
@@ -225,7 +225,7 @@ pub struct ExternBodyNestedBodies {
 /// (it'd break incremental compilation) and should only be called pre-HIR (e.g.
 /// during resolve)
 pub trait CrateStore {
-    fn crate_data_as_rc_any(&self, krate: CrateNum) -> Rc<Any>;
+    fn crate_data_as_rc_any(&self, krate: CrateNum) -> Lrc<Any>;
 
     // access to the metadata loader
     fn metadata_loader(&self) -> &MetadataLoader;
@@ -234,7 +234,7 @@ pub trait CrateStore {
     fn def_key(&self, def: DefId) -> DefKey;
     fn def_path(&self, def: DefId) -> hir_map::DefPath;
     fn def_path_hash(&self, def: DefId) -> hir_map::DefPathHash;
-    fn def_path_table(&self, cnum: CrateNum) -> Rc<DefPathTable>;
+    fn def_path_table(&self, cnum: CrateNum) -> Lrc<DefPathTable>;
 
     // "queries" used in resolve that aren't tracked for incremental compilation
     fn visibility_untracked(&self, def: DefId) -> ty::Visibility;
@@ -297,7 +297,7 @@ pub struct DummyCrateStore;
 
 #[allow(unused_variables)]
 impl CrateStore for DummyCrateStore {
-    fn crate_data_as_rc_any(&self, krate: CrateNum) -> Rc<Any>
+    fn crate_data_as_rc_any(&self, krate: CrateNum) -> Lrc<Any>
         { bug!("crate_data_as_rc_any") }
     // item info
     fn visibility_untracked(&self, def: DefId) -> ty::Visibility { bug!("visibility") }
@@ -325,7 +325,7 @@ impl CrateStore for DummyCrateStore {
     fn def_path_hash(&self, def: DefId) -> hir_map::DefPathHash {
         bug!("def_path_hash")
     }
-    fn def_path_table(&self, cnum: CrateNum) -> Rc<DefPathTable> {
+    fn def_path_table(&self, cnum: CrateNum) -> Lrc<DefPathTable> {
         bug!("def_path_table")
     }
     fn struct_field_names_untracked(&self, def: DefId) -> Vec<ast::Name> {
@@ -398,7 +398,7 @@ pub fn used_crates(tcx: TyCtxt, prefer: LinkagePreference)
         })
         .collect::<Vec<_>>();
     let mut ordering = tcx.postorder_cnums(LOCAL_CRATE);
-    Rc::make_mut(&mut ordering).reverse();
+    Lrc::make_mut(&mut ordering).reverse();
     libs.sort_by_key(|&(a, _)| {
         ordering.iter().position(|x| *x == a)
     });
diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index 7db75a51668..b65046022b7 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -27,7 +27,7 @@ use middle::region;
 use ty::{self, TyCtxt, adjustment};
 
 use hir::{self, PatKind};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::ast;
 use syntax::ptr::P;
 use syntax_pos::Span;
@@ -279,7 +279,7 @@ impl<'a, 'tcx> ExprUseVisitor<'a, 'tcx, 'tcx> {
                param_env: ty::ParamEnv<'tcx>,
                region_scope_tree: &'a region::ScopeTree,
                tables: &'a ty::TypeckTables<'tcx>,
-               rvalue_promotable_map: Option<Rc<ItemLocalSet>>)
+               rvalue_promotable_map: Option<Lrc<ItemLocalSet>>)
                -> Self
     {
         ExprUseVisitor {
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 45b595adfe7..c532427cc9b 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -85,6 +85,7 @@ use syntax::ast;
 use syntax_pos::Span;
 
 use std::fmt;
+use rustc_data_structures::sync::Lrc;
 use std::rc::Rc;
 use util::nodemap::ItemLocalSet;
 
@@ -286,7 +287,7 @@ pub struct MemCategorizationContext<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
     pub region_scope_tree: &'a region::ScopeTree,
     pub tables: &'a ty::TypeckTables<'tcx>,
-    rvalue_promotable_map: Option<Rc<ItemLocalSet>>,
+    rvalue_promotable_map: Option<Lrc<ItemLocalSet>>,
     infcx: Option<&'a InferCtxt<'a, 'gcx, 'tcx>>,
 }
 
@@ -395,7 +396,7 @@ impl<'a, 'tcx> MemCategorizationContext<'a, 'tcx, 'tcx> {
     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                region_scope_tree: &'a region::ScopeTree,
                tables: &'a ty::TypeckTables<'tcx>,
-               rvalue_promotable_map: Option<Rc<ItemLocalSet>>)
+               rvalue_promotable_map: Option<Lrc<ItemLocalSet>>)
                -> MemCategorizationContext<'a, 'tcx, 'tcx> {
         MemCategorizationContext {
             tcx,
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index e11609ea9b7..749685182a8 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -18,7 +18,7 @@
 use hir::map as hir_map;
 use hir::def::Def;
 use hir::def_id::{DefId, CrateNum};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use ty::{self, TyCtxt};
 use ty::maps::Providers;
 use middle::privacy;
@@ -377,7 +377,7 @@ impl<'a, 'tcx: 'a> ItemLikeVisitor<'tcx> for CollectPrivateImplItemsVisitor<'a,
 // We introduce a new-type here, so we can have a specialized HashStable
 // implementation for it.
 #[derive(Clone)]
-pub struct ReachableSet(pub Rc<NodeSet>);
+pub struct ReachableSet(pub Lrc<NodeSet>);
 
 
 fn reachable_set<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum) -> ReachableSet {
@@ -425,7 +425,7 @@ fn reachable_set<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum) ->
     reachable_context.propagate();
 
     // Return the set of reachable symbols.
-    ReachableSet(Rc::new(reachable_context.reachable_symbols))
+    ReachableSet(Lrc::new(reachable_context.reachable_symbols))
 }
 
 pub fn provide(providers: &mut Providers) {
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 3ce4ab04777..812ee0dc72f 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -20,7 +20,7 @@ use ty;
 
 use std::fmt;
 use std::mem;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::codemap;
 use syntax::ast;
 use syntax_pos::{Span, DUMMY_SP};
@@ -1436,7 +1436,7 @@ impl<'a, 'tcx> Visitor<'tcx> for RegionResolutionVisitor<'a, 'tcx> {
 }
 
 fn region_scope_tree<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
-    -> Rc<ScopeTree>
+    -> Lrc<ScopeTree>
 {
     let closure_base_def_id = tcx.closure_base_def_id(def_id);
     if closure_base_def_id != def_id {
@@ -1478,7 +1478,7 @@ fn region_scope_tree<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
         ScopeTree::default()
     };
 
-    Rc::new(scope_tree)
+    Lrc::new(scope_tree)
 }
 
 pub fn provide(providers: &mut Providers) {
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index 5201df2119d..f8fb2e5a1c8 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -23,7 +23,7 @@ use ty::{self, TyCtxt};
 
 use std::cell::Cell;
 use std::mem::replace;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::ast;
 use syntax::attr;
 use syntax::ptr::P;
@@ -212,10 +212,10 @@ struct NamedRegionMap {
 
 /// See `NamedRegionMap`.
 pub struct ResolveLifetimes {
-    defs: FxHashMap<LocalDefId, Rc<FxHashMap<ItemLocalId, Region>>>,
-    late_bound: FxHashMap<LocalDefId, Rc<FxHashSet<ItemLocalId>>>,
+    defs: FxHashMap<LocalDefId, Lrc<FxHashMap<ItemLocalId, Region>>>,
+    late_bound: FxHashMap<LocalDefId, Lrc<FxHashSet<ItemLocalId>>>,
     object_lifetime_defaults:
-        FxHashMap<LocalDefId, Rc<FxHashMap<ItemLocalId, Rc<Vec<ObjectLifetimeDefault>>>>>,
+        FxHashMap<LocalDefId, Lrc<FxHashMap<ItemLocalId, Lrc<Vec<ObjectLifetimeDefault>>>>>,
 }
 
 impl_stable_hash_for!(struct ::middle::resolve_lifetime::ResolveLifetimes {
@@ -376,7 +376,7 @@ pub fn provide(providers: &mut ty::maps::Providers) {
 fn resolve_lifetimes<'tcx>(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     for_krate: CrateNum,
-) -> Rc<ResolveLifetimes> {
+) -> Lrc<ResolveLifetimes> {
     assert_eq!(for_krate, LOCAL_CRATE);
 
     let named_region_map = krate(tcx);
@@ -385,29 +385,29 @@ fn resolve_lifetimes<'tcx>(
     for (k, v) in named_region_map.defs {
         let hir_id = tcx.hir.node_to_hir_id(k);
         let map = defs.entry(hir_id.owner_local_def_id())
-            .or_insert_with(|| Rc::new(FxHashMap()));
-        Rc::get_mut(map).unwrap().insert(hir_id.local_id, v);
+            .or_insert_with(|| Lrc::new(FxHashMap()));
+        Lrc::get_mut(map).unwrap().insert(hir_id.local_id, v);
     }
     let mut late_bound = FxHashMap();
     for k in named_region_map.late_bound {
         let hir_id = tcx.hir.node_to_hir_id(k);
         let map = late_bound
             .entry(hir_id.owner_local_def_id())
-            .or_insert_with(|| Rc::new(FxHashSet()));
-        Rc::get_mut(map).unwrap().insert(hir_id.local_id);
+            .or_insert_with(|| Lrc::new(FxHashSet()));
+        Lrc::get_mut(map).unwrap().insert(hir_id.local_id);
     }
     let mut object_lifetime_defaults = FxHashMap();
     for (k, v) in named_region_map.object_lifetime_defaults {
         let hir_id = tcx.hir.node_to_hir_id(k);
         let map = object_lifetime_defaults
             .entry(hir_id.owner_local_def_id())
-            .or_insert_with(|| Rc::new(FxHashMap()));
-        Rc::get_mut(map)
+            .or_insert_with(|| Lrc::new(FxHashMap()));
+        Lrc::get_mut(map)
             .unwrap()
-            .insert(hir_id.local_id, Rc::new(v));
+            .insert(hir_id.local_id, Lrc::new(v));
     }
 
-    Rc::new(ResolveLifetimes {
+    Lrc::new(ResolveLifetimes {
         defs,
         late_bound,
         object_lifetime_defaults,
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index 475946468fa..7c9feb506af 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -16,6 +16,7 @@ use graphviz::IntoCow;
 use middle::const_val::ConstVal;
 use middle::region;
 use rustc_const_math::{ConstUsize, ConstInt, ConstMathErr};
+use rustc_data_structures::sync::{Lrc};
 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
 use rustc_data_structures::control_flow_graph::dominators::{Dominators, dominators};
 use rustc_data_structures::control_flow_graph::{GraphPredecessors, GraphSuccessors};
@@ -36,7 +37,6 @@ use std::cell::Ref;
 use std::fmt::{self, Debug, Formatter, Write};
 use std::{iter, mem, u32};
 use std::ops::{Index, IndexMut};
-use std::rc::Rc;
 use std::vec::IntoIter;
 use syntax::ast::{self, Name};
 use syntax::symbol::InternedString;
@@ -1970,10 +1970,10 @@ pub struct UnsafetyViolation {
 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 pub struct UnsafetyCheckResult {
     /// Violations that are propagated *upwards* from this function
-    pub violations: Rc<[UnsafetyViolation]>,
+    pub violations: Lrc<[UnsafetyViolation]>,
     /// unsafe blocks in this function, along with whether they are used. This is
     /// used for the "unused_unsafe" lint.
-    pub unsafe_blocks: Rc<[(ast::NodeId, bool)]>,
+    pub unsafe_blocks: Lrc<[(ast::NodeId, bool)]>,
 }
 
 /// The layout of generator state
diff --git a/src/librustc/session/mod.rs b/src/librustc/session/mod.rs
index 2437eaadc6d..db699349be6 100644
--- a/src/librustc/session/mod.rs
+++ b/src/librustc/session/mod.rs
@@ -25,6 +25,8 @@ use ty::tls;
 use util::nodemap::{FxHashMap, FxHashSet};
 use util::common::{duration_to_secs_str, ErrorReported};
 
+use rustc_data_structures::sync::Lrc;
+
 use syntax::ast::NodeId;
 use errors::{self, DiagnosticBuilder, DiagnosticId};
 use errors::emitter::{Emitter, EmitterWriter};
@@ -48,7 +50,6 @@ use std::env;
 use std::fmt;
 use std::io::Write;
 use std::path::{Path, PathBuf};
-use std::rc::Rc;
 use std::sync::{Once, ONCE_INIT};
 use std::time::Duration;
 
@@ -896,14 +897,14 @@ pub fn build_session(sopts: config::Options,
     build_session_with_codemap(sopts,
                                local_crate_source_file,
                                registry,
-                               Rc::new(codemap::CodeMap::new(file_path_mapping)),
+                               Lrc::new(codemap::CodeMap::new(file_path_mapping)),
                                None)
 }
 
 pub fn build_session_with_codemap(sopts: config::Options,
                                   local_crate_source_file: Option<PathBuf>,
                                   registry: errors::registry::Registry,
-                                  codemap: Rc<codemap::CodeMap>,
+                                  codemap: Lrc<codemap::CodeMap>,
                                   emitter_dest: Option<Box<Write + Send>>)
                                   -> Session {
     // FIXME: This is not general enough to make the warning lint completely override
@@ -971,7 +972,7 @@ pub fn build_session_with_codemap(sopts: config::Options,
 pub fn build_session_(sopts: config::Options,
                       local_crate_source_file: Option<PathBuf>,
                       span_diagnostic: errors::Handler,
-                      codemap: Rc<codemap::CodeMap>)
+                      codemap: Lrc<codemap::CodeMap>)
                       -> Session {
     let host = match Target::search(config::host_triple()) {
         Ok(t) => t,
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 76d3c7f1506..b9ae4599d80 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -27,6 +27,7 @@ use ty::{self, AdtKind, Ty, TyCtxt, TypeFoldable, ToPredicate};
 use ty::error::{ExpectedFound, TypeError};
 use infer::{InferCtxt};
 
+use rustc_data_structures::sync::Lrc;
 use std::rc::Rc;
 use syntax::ast;
 use syntax_pos::{Span, DUMMY_SP};
@@ -740,11 +741,11 @@ fn substitute_normalize_and_test_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx
 fn vtable_methods<'a, 'tcx>(
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
     trait_ref: ty::PolyTraitRef<'tcx>)
-    -> Rc<Vec<Option<(DefId, &'tcx Substs<'tcx>)>>>
+    -> Lrc<Vec<Option<(DefId, &'tcx Substs<'tcx>)>>>
 {
     debug!("vtable_methods({:?})", trait_ref);
 
-    Rc::new(
+    Lrc::new(
         supertraits(tcx, trait_ref).flat_map(move |trait_ref| {
             let trait_methods = tcx.associated_items(trait_ref.def_id())
                 .filter(|item| item.kind == ty::AssociatedKind::Method);
diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs
index 5dfeb1bb429..43940d7cea3 100644
--- a/src/librustc/traits/specialize/mod.rs
+++ b/src/librustc/traits/specialize/mod.rs
@@ -30,7 +30,7 @@ use traits::{self, Reveal, ObligationCause};
 use traits::select::IntercrateAmbiguityCause;
 use ty::{self, TyCtxt, TypeFoldable};
 use syntax_pos::DUMMY_SP;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 use lint;
 
@@ -308,7 +308,7 @@ impl SpecializesCache {
 // Query provider for `specialization_graph_of`.
 pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                                       trait_id: DefId)
-                                                      -> Rc<specialization_graph::Graph> {
+                                                      -> Lrc<specialization_graph::Graph> {
     let mut sg = specialization_graph::Graph::new();
 
     let mut trait_impls = Vec::new();
@@ -392,7 +392,7 @@ pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx
         }
     }
 
-    Rc::new(sg)
+    Lrc::new(sg)
 }
 
 /// Recovers the "impl X for Y" signature from `impl_def_id` and returns it as a
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index a10169e13e6..a9b38d6a8d8 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -17,7 +17,7 @@ use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
 use traits;
 use ty::{self, TyCtxt, TypeFoldable};
 use ty::fast_reject::{self, SimplifiedType};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::ast::Name;
 use util::nodemap::{DefIdMap, FxHashMap};
 
@@ -327,7 +327,7 @@ impl<'a, 'gcx, 'tcx> Node {
 
 pub struct Ancestors {
     trait_def_id: DefId,
-    specialization_graph: Rc<Graph>,
+    specialization_graph: Lrc<Graph>,
     current_source: Option<Node>,
 }
 
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index a39d63d05ee..3ad8df879f2 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -55,6 +55,7 @@ use rustc_data_structures::stable_hasher::{HashStable, hash_stable_hashmap,
 use arena::{TypedArena, DroplessArena};
 use rustc_const_math::{ConstInt, ConstUsize};
 use rustc_data_structures::indexed_vec::IndexVec;
+use rustc_data_structures::sync::Lrc;
 use std::any::Any;
 use std::borrow::Borrow;
 use std::cell::{Cell, RefCell};
@@ -64,7 +65,6 @@ use std::hash::{Hash, Hasher};
 use std::mem;
 use std::ops::Deref;
 use std::iter;
-use std::rc::Rc;
 use std::sync::mpsc;
 use std::sync::Arc;
 use syntax::abi;
@@ -397,9 +397,9 @@ pub struct TypeckTables<'tcx> {
 
     /// Set of trait imports actually used in the method resolution.
     /// This is used for warning unused imports. During type
-    /// checking, this `Rc` should not be cloned: it must have a ref-count
+    /// checking, this `Lrc` should not be cloned: it must have a ref-count
     /// of 1 so that we can insert things into the set mutably.
-    pub used_trait_imports: Rc<DefIdSet>,
+    pub used_trait_imports: Lrc<DefIdSet>,
 
     /// If any errors occurred while type-checking this body,
     /// this field will be set to `true`.
@@ -426,7 +426,7 @@ impl<'tcx> TypeckTables<'tcx> {
             liberated_fn_sigs: ItemLocalMap(),
             fru_field_types: ItemLocalMap(),
             cast_kinds: ItemLocalMap(),
-            used_trait_imports: Rc::new(DefIdSet()),
+            used_trait_imports: Lrc::new(DefIdSet()),
             tainted_by_errors: false,
             free_region_map: FreeRegionMap::new(),
         }
@@ -816,11 +816,11 @@ pub struct GlobalCtxt<'tcx> {
     /// Map indicating what traits are in scope for places where this
     /// is relevant; generated by resolve.
     trait_map: FxHashMap<DefIndex,
-                         Rc<FxHashMap<ItemLocalId,
-                                      Rc<StableVec<TraitCandidate>>>>>,
+                         Lrc<FxHashMap<ItemLocalId,
+                                       Lrc<StableVec<TraitCandidate>>>>>,
 
     /// Export map produced by name resolution.
-    export_map: FxHashMap<DefId, Rc<Vec<Export>>>,
+    export_map: FxHashMap<DefId, Lrc<Vec<Export>>>,
 
     pub hir: hir_map::Map<'tcx>,
 
@@ -833,7 +833,7 @@ pub struct GlobalCtxt<'tcx> {
     // Records the free variables refrenced by every closure
     // expression. Do not track deps for this, just recompute it from
     // scratch every time.
-    freevars: FxHashMap<DefId, Rc<Vec<hir::Freevar>>>,
+    freevars: FxHashMap<DefId, Lrc<Vec<hir::Freevar>>>,
 
     maybe_unused_trait_imports: FxHashSet<DefId>,
 
@@ -1153,7 +1153,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         providers[LOCAL_CRATE] = local_providers;
 
         let def_path_hash_to_def_id = if s.opts.build_dep_graph() {
-            let upstream_def_path_tables: Vec<(CrateNum, Rc<_>)> = cstore
+            let upstream_def_path_tables: Vec<(CrateNum, Lrc<_>)> = cstore
                 .crates_untracked()
                 .iter()
                 .map(|&cnum| (cnum, cstore.def_path_table(cnum)))
@@ -1188,10 +1188,10 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         for (k, v) in resolutions.trait_map {
             let hir_id = hir.node_to_hir_id(k);
             let map = trait_map.entry(hir_id.owner)
-                .or_insert_with(|| Rc::new(FxHashMap()));
-            Rc::get_mut(map).unwrap()
+                .or_insert_with(|| Lrc::new(FxHashMap()));
+            Lrc::get_mut(map).unwrap()
                             .insert(hir_id.local_id,
-                                    Rc::new(StableVec::new(v)));
+                                    Lrc::new(StableVec::new(v)));
         }
 
         tls::enter_global(GlobalCtxt {
@@ -1204,10 +1204,10 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             types: common_types,
             trait_map,
             export_map: resolutions.export_map.into_iter().map(|(k, v)| {
-                (k, Rc::new(v))
+                (k, Lrc::new(v))
             }).collect(),
             freevars: resolutions.freevars.into_iter().map(|(k, v)| {
-                (hir.local_def_id(k), Rc::new(v))
+                (hir.local_def_id(k), Lrc::new(v))
             }).collect(),
             maybe_unused_trait_imports:
                 resolutions.maybe_unused_trait_imports
@@ -1243,15 +1243,15 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         self.sess.consider_optimizing(&cname, msg)
     }
 
-    pub fn lang_items(self) -> Rc<middle::lang_items::LanguageItems> {
+    pub fn lang_items(self) -> Lrc<middle::lang_items::LanguageItems> {
         self.get_lang_items(LOCAL_CRATE)
     }
 
-    pub fn stability(self) -> Rc<stability::Index<'tcx>> {
+    pub fn stability(self) -> Lrc<stability::Index<'tcx>> {
         self.stability_index(LOCAL_CRATE)
     }
 
-    pub fn crates(self) -> Rc<Vec<CrateNum>> {
+    pub fn crates(self) -> Lrc<Vec<CrateNum>> {
         self.all_crate_nums(LOCAL_CRATE)
     }
 
@@ -1312,7 +1312,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 
     // Note that this is *untracked* and should only be used within the query
     // system if the result is otherwise tracked through queries
-    pub fn crate_data_as_rc_any(self, cnum: CrateNum) -> Rc<Any> {
+    pub fn crate_data_as_rc_any(self, cnum: CrateNum) -> Lrc<Any> {
         self.cstore.crate_data_as_rc_any(cnum)
     }
 
@@ -2264,7 +2264,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         lint::struct_lint_level(self.sess, lint, level, src, None, msg)
     }
 
-    pub fn in_scope_traits(self, id: HirId) -> Option<Rc<StableVec<TraitCandidate>>> {
+    pub fn in_scope_traits(self, id: HirId) -> Option<Lrc<StableVec<TraitCandidate>>> {
         self.in_scope_traits_map(id.owner)
             .and_then(|map| map.get(&id.local_id).cloned())
     }
@@ -2281,7 +2281,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     }
 
     pub fn object_lifetime_defaults(self, id: HirId)
-        -> Option<Rc<Vec<ObjectLifetimeDefault>>>
+        -> Option<Lrc<Vec<ObjectLifetimeDefault>>>
     {
         self.object_lifetime_defaults_map(id.owner)
             .and_then(|map| map.get(&id.local_id).cloned())
@@ -2352,7 +2352,7 @@ pub fn provide(providers: &mut ty::maps::Providers) {
         // Once red/green incremental compilation lands we should be able to
         // remove this because while the crate changes often the lint level map
         // will change rarely.
-        tcx.dep_graph.with_ignore(|| Rc::new(middle::lang_items::collect(tcx)))
+        tcx.dep_graph.with_ignore(|| Lrc::new(middle::lang_items::collect(tcx)))
     };
     providers.freevars = |tcx, id| tcx.gcx.freevars.get(&id).cloned();
     providers.maybe_unused_trait_import = |tcx, id| {
@@ -2360,12 +2360,12 @@ pub fn provide(providers: &mut ty::maps::Providers) {
     };
     providers.maybe_unused_extern_crates = |tcx, cnum| {
         assert_eq!(cnum, LOCAL_CRATE);
-        Rc::new(tcx.maybe_unused_extern_crates.clone())
+        Lrc::new(tcx.maybe_unused_extern_crates.clone())
     };
 
     providers.stability_index = |tcx, cnum| {
         assert_eq!(cnum, LOCAL_CRATE);
-        Rc::new(stability::Index::new(tcx))
+        Lrc::new(stability::Index::new(tcx))
     };
     providers.lookup_stability = |tcx, id| {
         assert_eq!(id.krate, LOCAL_CRATE);
@@ -2383,11 +2383,11 @@ pub fn provide(providers: &mut ty::maps::Providers) {
     };
     providers.all_crate_nums = |tcx, cnum| {
         assert_eq!(cnum, LOCAL_CRATE);
-        Rc::new(tcx.cstore.crates_untracked())
+        Lrc::new(tcx.cstore.crates_untracked())
     };
     providers.postorder_cnums = |tcx, cnum| {
         assert_eq!(cnum, LOCAL_CRATE);
-        Rc::new(tcx.cstore.postorder_cnums_untracked())
+        Lrc::new(tcx.cstore.postorder_cnums_untracked())
     };
     providers.output_filenames = |tcx, cnum| {
         assert_eq!(cnum, LOCAL_CRATE);
diff --git a/src/librustc/ty/maps/mod.rs b/src/librustc/ty/maps/mod.rs
index be1d255afa1..6edb1d9be35 100644
--- a/src/librustc/ty/maps/mod.rs
+++ b/src/librustc/ty/maps/mod.rs
@@ -46,7 +46,7 @@ use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use rustc_data_structures::stable_hasher::StableVec;
 
 use std::ops::Deref;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::sync::Arc;
 use syntax_pos::{Span, DUMMY_SP};
 use syntax_pos::symbol::InternedString;
@@ -119,17 +119,17 @@ define_maps! { <'tcx>
 
     /// Get a map with the variance of every item; use `item_variance`
     /// instead.
-    [] fn crate_variances: crate_variances(CrateNum) -> Rc<ty::CrateVariancesMap>,
+    [] fn crate_variances: crate_variances(CrateNum) -> Lrc<ty::CrateVariancesMap>,
 
     /// Maps from def-id of a type or region parameter to its
     /// (inferred) variance.
-    [] fn variances_of: ItemVariances(DefId) -> Rc<Vec<ty::Variance>>,
+    [] fn variances_of: ItemVariances(DefId) -> Lrc<Vec<ty::Variance>>,
 
     /// Maps from def-id of a type to its (inferred) outlives.
     [] fn inferred_outlives_of: InferredOutlivesOf(DefId) -> Vec<ty::Predicate<'tcx>>,
 
     /// Maps from an impl/trait def-id to a list of the def-ids of its items
-    [] fn associated_item_def_ids: AssociatedItemDefIds(DefId) -> Rc<Vec<DefId>>,
+    [] fn associated_item_def_ids: AssociatedItemDefIds(DefId) -> Lrc<Vec<DefId>>,
 
     /// Maps from a trait item to the trait item "descriptor"
     [] fn associated_item: AssociatedItems(DefId) -> ty::AssociatedItem,
@@ -140,17 +140,17 @@ define_maps! { <'tcx>
     /// Maps a DefId of a type to a list of its inherent impls.
     /// Contains implementations of methods that are inherent to a type.
     /// Methods in these implementations don't need to be exported.
-    [] fn inherent_impls: InherentImpls(DefId) -> Rc<Vec<DefId>>,
+    [] fn inherent_impls: InherentImpls(DefId) -> Lrc<Vec<DefId>>,
 
     /// Set of all the def-ids in this crate that have MIR associated with
     /// them. This includes all the body owners, but also things like struct
     /// constructors.
-    [] fn mir_keys: mir_keys(CrateNum) -> Rc<DefIdSet>,
+    [] fn mir_keys: mir_keys(CrateNum) -> Lrc<DefIdSet>,
 
     /// Maps DefId's that have an associated Mir to the result
     /// of the MIR qualify_consts pass. The actual meaning of
     /// the value isn't known except to the pass itself.
-    [] fn mir_const_qualif: MirConstQualif(DefId) -> (u8, Rc<IdxSetBuf<mir::Local>>),
+    [] fn mir_const_qualif: MirConstQualif(DefId) -> (u8, Lrc<IdxSetBuf<mir::Local>>),
 
     /// Fetch the MIR for a given def-id right after it's built - this includes
     /// unreachable code.
@@ -185,13 +185,13 @@ define_maps! { <'tcx>
 
     [] fn typeck_tables_of: TypeckTables(DefId) -> &'tcx ty::TypeckTables<'tcx>,
 
-    [] fn used_trait_imports: UsedTraitImports(DefId) -> Rc<DefIdSet>,
+    [] fn used_trait_imports: UsedTraitImports(DefId) -> Lrc<DefIdSet>,
 
     [] fn has_typeck_tables: HasTypeckTables(DefId) -> bool,
 
     [] fn coherent_trait: CoherenceCheckTrait(DefId) -> (),
 
-    [] fn borrowck: BorrowCheck(DefId) -> Rc<BorrowCheckResult>,
+    [] fn borrowck: BorrowCheck(DefId) -> Lrc<BorrowCheckResult>,
 
     /// Borrow checks the function body. If this is a closure, returns
     /// additional requirements that the closure's creator must verify.
@@ -216,13 +216,13 @@ define_maps! { <'tcx>
         -> Result<(), ErrorReported>,
 
     /// Performs the privacy check and computes "access levels".
-    [] fn privacy_access_levels: PrivacyAccessLevels(CrateNum) -> Rc<AccessLevels>,
+    [] fn privacy_access_levels: PrivacyAccessLevels(CrateNum) -> Lrc<AccessLevels>,
 
     [] fn reachable_set: reachability_dep_node(CrateNum) -> ReachableSet,
 
     /// Per-body `region::ScopeTree`. The `DefId` should be the owner-def-id for the body;
     /// in the case of closures, this will be redirected to the enclosing function.
-    [] fn region_scope_tree: RegionScopeTree(DefId) -> Rc<region::ScopeTree>,
+    [] fn region_scope_tree: RegionScopeTree(DefId) -> Lrc<region::ScopeTree>,
 
     [] fn mir_shims: mir_shim_dep_node(ty::InstanceDef<'tcx>) -> &'tcx mir::Mir<'tcx>,
 
@@ -233,22 +233,22 @@ define_maps! { <'tcx>
     [] fn def_span: DefSpan(DefId) -> Span,
     [] fn lookup_stability: LookupStability(DefId) -> Option<&'tcx attr::Stability>,
     [] fn lookup_deprecation_entry: LookupDeprecationEntry(DefId) -> Option<DeprecationEntry>,
-    [] fn item_attrs: ItemAttrs(DefId) -> Rc<[ast::Attribute]>,
+    [] fn item_attrs: ItemAttrs(DefId) -> Lrc<[ast::Attribute]>,
     [] 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) -> Rc<ItemLocalSet>,
+    [] fn rvalue_promotable_map: RvaluePromotableMap(DefId) -> Lrc<ItemLocalSet>,
     [] fn is_mir_available: IsMirAvailable(DefId) -> bool,
     [] fn vtable_methods: vtable_methods_node(ty::PolyTraitRef<'tcx>)
-                          -> Rc<Vec<Option<(DefId, &'tcx Substs<'tcx>)>>>,
+                          -> Lrc<Vec<Option<(DefId, &'tcx Substs<'tcx>)>>>,
 
     [] fn trans_fulfill_obligation: fulfill_obligation_dep_node(
         (ty::ParamEnv<'tcx>, ty::PolyTraitRef<'tcx>)) -> Vtable<'tcx, ()>,
-    [] fn trait_impls_of: TraitImpls(DefId) -> Rc<ty::trait_def::TraitImpls>,
-    [] fn specialization_graph_of: SpecializationGraph(DefId) -> Rc<specialization_graph::Graph>,
+    [] fn trait_impls_of: TraitImpls(DefId) -> Lrc<ty::trait_def::TraitImpls>,
+    [] fn specialization_graph_of: SpecializationGraph(DefId) -> Lrc<specialization_graph::Graph>,
     [] fn is_object_safe: ObjectSafety(DefId) -> bool,
 
     // Get the ParameterEnvironment for a given item; this environment
@@ -270,7 +270,7 @@ define_maps! { <'tcx>
                                             ty::layout::LayoutError<'tcx>>,
 
     [] fn dylib_dependency_formats: DylibDepFormats(CrateNum)
-                                    -> Rc<Vec<(CrateNum, LinkagePreference)>>,
+                                    -> Lrc<Vec<(CrateNum, LinkagePreference)>>,
 
     [fatal_cycle] fn is_panic_runtime: IsPanicRuntime(CrateNum) -> bool,
     [fatal_cycle] fn is_compiler_builtins: IsCompilerBuiltins(CrateNum) -> bool,
@@ -280,17 +280,17 @@ define_maps! { <'tcx>
     [fatal_cycle] fn panic_strategy: GetPanicStrategy(CrateNum) -> PanicStrategy,
     [fatal_cycle] fn is_no_builtins: IsNoBuiltins(CrateNum) -> bool,
 
-    [] fn extern_crate: ExternCrate(DefId) -> Rc<Option<ExternCrate>>,
+    [] fn extern_crate: ExternCrate(DefId) -> Lrc<Option<ExternCrate>>,
 
     [] fn specializes: specializes_node((DefId, DefId)) -> bool,
     [] fn in_scope_traits_map: InScopeTraits(DefIndex)
-        -> Option<Rc<FxHashMap<ItemLocalId, Rc<StableVec<TraitCandidate>>>>>,
-    [] fn module_exports: ModuleExports(DefId) -> Option<Rc<Vec<Export>>>,
-    [] fn lint_levels: lint_levels_node(CrateNum) -> Rc<lint::LintLevelMap>,
+        -> Option<Lrc<FxHashMap<ItemLocalId, Lrc<StableVec<TraitCandidate>>>>>,
+    [] fn module_exports: ModuleExports(DefId) -> Option<Lrc<Vec<Export>>>,
+    [] fn lint_levels: lint_levels_node(CrateNum) -> Lrc<lint::LintLevelMap>,
 
     [] fn impl_defaultness: ImplDefaultness(DefId) -> hir::Defaultness,
-    [] fn exported_symbol_ids: ExportedSymbolIds(CrateNum) -> Rc<DefIdSet>,
-    [] fn native_libraries: NativeLibraries(CrateNum) -> Rc<Vec<NativeLibrary>>,
+    [] fn exported_symbol_ids: ExportedSymbolIds(CrateNum) -> Lrc<DefIdSet>,
+    [] fn native_libraries: NativeLibraries(CrateNum) -> Lrc<Vec<NativeLibrary>>,
     [] fn plugin_registrar_fn: PluginRegistrarFn(CrateNum) -> Option<DefId>,
     [] fn derive_registrar_fn: DeriveRegistrarFn(CrateNum) -> Option<DefId>,
     [] fn crate_disambiguator: CrateDisambiguator(CrateNum) -> CrateDisambiguator,
@@ -298,48 +298,48 @@ define_maps! { <'tcx>
     [] fn original_crate_name: OriginalCrateName(CrateNum) -> Symbol,
 
     [] fn implementations_of_trait: implementations_of_trait_node((CrateNum, DefId))
-        -> Rc<Vec<DefId>>,
+        -> Lrc<Vec<DefId>>,
     [] fn all_trait_implementations: AllTraitImplementations(CrateNum)
-        -> Rc<Vec<DefId>>,
+        -> Lrc<Vec<DefId>>,
 
     [] fn is_dllimport_foreign_item: IsDllimportForeignItem(DefId) -> bool,
     [] fn is_statically_included_foreign_item: IsStaticallyIncludedForeignItem(DefId) -> bool,
     [] fn native_library_kind: NativeLibraryKind(DefId)
         -> Option<NativeLibraryKind>,
-    [] fn link_args: link_args_node(CrateNum) -> Rc<Vec<String>>,
+    [] fn link_args: link_args_node(CrateNum) -> Lrc<Vec<String>>,
 
     // Lifetime resolution. See `middle::resolve_lifetimes`.
-    [] fn resolve_lifetimes: ResolveLifetimes(CrateNum) -> Rc<ResolveLifetimes>,
+    [] fn resolve_lifetimes: ResolveLifetimes(CrateNum) -> Lrc<ResolveLifetimes>,
     [] fn named_region_map: NamedRegion(DefIndex) ->
-        Option<Rc<FxHashMap<ItemLocalId, Region>>>,
+        Option<Lrc<FxHashMap<ItemLocalId, Region>>>,
     [] fn is_late_bound_map: IsLateBound(DefIndex) ->
-        Option<Rc<FxHashSet<ItemLocalId>>>,
+        Option<Lrc<FxHashSet<ItemLocalId>>>,
     [] fn object_lifetime_defaults_map: ObjectLifetimeDefaults(DefIndex)
-        -> Option<Rc<FxHashMap<ItemLocalId, Rc<Vec<ObjectLifetimeDefault>>>>>,
+        -> Option<Lrc<FxHashMap<ItemLocalId, Lrc<Vec<ObjectLifetimeDefault>>>>>,
 
     [] fn visibility: Visibility(DefId) -> ty::Visibility,
     [] fn dep_kind: DepKind(CrateNum) -> DepKind,
     [] fn crate_name: CrateName(CrateNum) -> Symbol,
-    [] fn item_children: ItemChildren(DefId) -> Rc<Vec<Export>>,
+    [] fn item_children: ItemChildren(DefId) -> Lrc<Vec<Export>>,
     [] fn extern_mod_stmt_cnum: ExternModStmtCnum(DefId) -> Option<CrateNum>,
 
-    [] fn get_lang_items: get_lang_items_node(CrateNum) -> Rc<LanguageItems>,
-    [] fn defined_lang_items: DefinedLangItems(CrateNum) -> Rc<Vec<(DefId, usize)>>,
-    [] fn missing_lang_items: MissingLangItems(CrateNum) -> Rc<Vec<LangItem>>,
+    [] fn get_lang_items: get_lang_items_node(CrateNum) -> Lrc<LanguageItems>,
+    [] fn defined_lang_items: DefinedLangItems(CrateNum) -> Lrc<Vec<(DefId, usize)>>,
+    [] fn missing_lang_items: MissingLangItems(CrateNum) -> Lrc<Vec<LangItem>>,
     [] fn extern_const_body: ExternConstBody(DefId) -> ExternConstBody<'tcx>,
     [] fn visible_parent_map: visible_parent_map_node(CrateNum)
-        -> Rc<DefIdMap<DefId>>,
+        -> Lrc<DefIdMap<DefId>>,
     [] fn missing_extern_crate_item: MissingExternCrateItem(CrateNum) -> bool,
-    [] fn used_crate_source: UsedCrateSource(CrateNum) -> Rc<CrateSource>,
-    [] fn postorder_cnums: postorder_cnums_node(CrateNum) -> Rc<Vec<CrateNum>>,
+    [] fn used_crate_source: UsedCrateSource(CrateNum) -> Lrc<CrateSource>,
+    [] fn postorder_cnums: postorder_cnums_node(CrateNum) -> Lrc<Vec<CrateNum>>,
 
-    [] fn freevars: Freevars(DefId) -> Option<Rc<Vec<hir::Freevar>>>,
+    [] fn freevars: Freevars(DefId) -> Option<Lrc<Vec<hir::Freevar>>>,
     [] fn maybe_unused_trait_import: MaybeUnusedTraitImport(DefId) -> bool,
     [] fn maybe_unused_extern_crates: maybe_unused_extern_crates_node(CrateNum)
-        -> Rc<Vec<(DefId, Span)>>,
+        -> Lrc<Vec<(DefId, Span)>>,
 
-    [] fn stability_index: stability_index_node(CrateNum) -> Rc<stability::Index<'tcx>>,
-    [] fn all_crate_nums: all_crate_nums_node(CrateNum) -> Rc<Vec<CrateNum>>,
+    [] fn stability_index: stability_index_node(CrateNum) -> Lrc<stability::Index<'tcx>>,
+    [] fn all_crate_nums: all_crate_nums_node(CrateNum) -> Lrc<Vec<CrateNum>>,
 
     [] fn exported_symbols: ExportedSymbols(CrateNum)
         -> Arc<Vec<(String, Option<DefId>, SymbolExportLevel)>>,
@@ -368,8 +368,8 @@ define_maps! { <'tcx>
         substitute_normalize_and_test_predicates_node((DefId, &'tcx Substs<'tcx>)) -> bool,
 
     [] fn target_features_whitelist:
-        target_features_whitelist_node(CrateNum) -> Rc<FxHashSet<String>>,
-    [] fn target_features_enabled: TargetFeaturesEnabled(DefId) -> Rc<Vec<String>>,
+        target_features_whitelist_node(CrateNum) -> Lrc<FxHashSet<String>>,
+    [] fn target_features_enabled: TargetFeaturesEnabled(DefId) -> Lrc<Vec<String>>,
 
     // Get an estimate of the size of an InstanceDef based on its MIR for CGU partitioning.
     [] fn instance_def_size_estimate: instance_def_size_estimate_dep_node(ty::InstanceDef<'tcx>)
diff --git a/src/librustc/ty/maps/on_disk_cache.rs b/src/librustc/ty/maps/on_disk_cache.rs
index 17b44f6959f..65f2d476475 100644
--- a/src/librustc/ty/maps/on_disk_cache.rs
+++ b/src/librustc/ty/maps/on_disk_cache.rs
@@ -17,6 +17,7 @@ use hir::map::definitions::DefPathHash;
 use ich::{CachingCodemapView, Fingerprint};
 use mir;
 use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::sync::Lrc;
 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
 use rustc_serialize::{Decodable, Decoder, Encodable, Encoder, opaque,
                       SpecializedDecoder, SpecializedEncoder,
@@ -24,7 +25,6 @@ use rustc_serialize::{Decodable, Decoder, Encodable, Encoder, opaque,
 use session::{CrateDisambiguator, Session};
 use std::cell::RefCell;
 use std::mem;
-use std::rc::Rc;
 use syntax::ast::NodeId;
 use syntax::codemap::{CodeMap, StableFilemapId};
 use syntax_pos::{BytePos, Span, DUMMY_SP, FileMap};
@@ -65,7 +65,7 @@ pub struct OnDiskCache<'sess> {
     file_index_to_stable_id: FxHashMap<FileMapIndex, StableFilemapId>,
 
     // These two fields caches that are populated lazily during decoding.
-    file_index_to_file: RefCell<FxHashMap<FileMapIndex, Rc<FileMap>>>,
+    file_index_to_file: RefCell<FxHashMap<FileMapIndex, Lrc<FileMap>>>,
     synthetic_expansion_infos: RefCell<FxHashMap<AbsoluteBytePos, SyntaxContext>>,
 
     // A map from dep-node to the position of the cached query result in
@@ -421,12 +421,12 @@ struct CacheDecoder<'a, 'tcx: 'a, 'x> {
     codemap: &'x CodeMap,
     cnum_map: &'x IndexVec<CrateNum, Option<CrateNum>>,
     synthetic_expansion_infos: &'x RefCell<FxHashMap<AbsoluteBytePos, SyntaxContext>>,
-    file_index_to_file: &'x RefCell<FxHashMap<FileMapIndex, Rc<FileMap>>>,
+    file_index_to_file: &'x RefCell<FxHashMap<FileMapIndex, Lrc<FileMap>>>,
     file_index_to_stable_id: &'x FxHashMap<FileMapIndex, StableFilemapId>,
 }
 
 impl<'a, 'tcx, 'x> CacheDecoder<'a, 'tcx, 'x> {
-    fn file_index_to_file(&self, index: FileMapIndex) -> Rc<FileMap> {
+    fn file_index_to_file(&self, index: FileMapIndex) -> Lrc<FileMap> {
         let CacheDecoder {
             ref file_index_to_file,
             ref file_index_to_stable_id,
@@ -710,7 +710,7 @@ struct CacheEncoder<'enc, 'a, 'tcx, E>
 impl<'enc, 'a, 'tcx, E> CacheEncoder<'enc, 'a, 'tcx, E>
     where E: 'enc + ty_codec::TyEncoder
 {
-    fn filemap_index(&mut self, filemap: Rc<FileMap>) -> FileMapIndex {
+    fn filemap_index(&mut self, filemap: Lrc<FileMap>) -> FileMapIndex {
         self.file_to_file_index[&(&*filemap as *const FileMap)]
     }
 
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 88422a3ef82..9ba33a57c20 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -43,7 +43,7 @@ use std::fmt;
 use std::hash::{Hash, Hasher};
 use std::iter::FromIterator;
 use std::ops::Deref;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::slice;
 use std::vec::IntoIter;
 use std::mem;
@@ -125,7 +125,7 @@ mod sty;
 /// *on-demand* infrastructure.
 #[derive(Clone)]
 pub struct CrateAnalysis {
-    pub access_levels: Rc<AccessLevels>,
+    pub access_levels: Lrc<AccessLevels>,
     pub name: String,
     pub glob_map: Option<hir::GlobMap>,
 }
@@ -337,10 +337,10 @@ pub struct CrateVariancesMap {
     /// For each item with generics, maps to a vector of the variance
     /// of its generics.  If an item has no generics, it will have no
     /// entry.
-    pub variances: FxHashMap<DefId, Rc<Vec<ty::Variance>>>,
+    pub variances: FxHashMap<DefId, Lrc<Vec<ty::Variance>>>,
 
     /// An empty vector, useful for cloning.
-    pub empty_variance: Rc<Vec<ty::Variance>>,
+    pub empty_variance: Lrc<Vec<ty::Variance>>,
 }
 
 impl Variance {
@@ -2198,7 +2198,7 @@ impl BorrowKind {
 
 #[derive(Debug, Clone)]
 pub enum Attributes<'gcx> {
-    Owned(Rc<[ast::Attribute]>),
+    Owned(Lrc<[ast::Attribute]>),
     Borrowed(&'gcx [ast::Attribute])
 }
 
@@ -2627,7 +2627,7 @@ fn adt_dtorck_constraint<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
 fn associated_item_def_ids<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                      def_id: DefId)
-                                     -> Rc<Vec<DefId>> {
+                                     -> Lrc<Vec<DefId>> {
     let id = tcx.hir.as_local_node_id(def_id).unwrap();
     let item = tcx.hir.expect_item(id);
     let vec: Vec<_> = match item.node {
@@ -2646,7 +2646,7 @@ fn associated_item_def_ids<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         hir::ItemTraitAlias(..) => vec![],
         _ => span_bug!(item.span, "associated_item_def_ids: not impl or trait")
     };
-    Rc::new(vec)
+    Lrc::new(vec)
 }
 
 fn def_span<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> Span {
@@ -2760,7 +2760,7 @@ pub fn provide(providers: &mut ty::maps::Providers) {
 /// (constructing this map requires touching the entire crate).
 #[derive(Clone, Debug)]
 pub struct CrateInherentImpls {
-    pub inherent_impls: DefIdMap<Rc<Vec<DefId>>>,
+    pub inherent_impls: DefIdMap<Lrc<Vec<DefId>>>,
 }
 
 /// A set of constraints that need to be satisfied in order for
diff --git a/src/librustc/ty/trait_def.rs b/src/librustc/ty/trait_def.rs
index 0fbf9f1bd58..62d3c8dc87d 100644
--- a/src/librustc/ty/trait_def.rs
+++ b/src/librustc/ty/trait_def.rs
@@ -20,7 +20,7 @@ use ty::{Ty, TyCtxt};
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
                                            StableHasherResult};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 /// A trait's definition with type information.
 pub struct TraitDef {
@@ -142,7 +142,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 // Query provider for `trait_impls_of`.
 pub(super) fn trait_impls_of_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                                 trait_id: DefId)
-                                                -> Rc<TraitImpls> {
+                                                -> Lrc<TraitImpls> {
     let mut remote_impls = Vec::new();
 
     // Traits defined in the current crate can't have impls in upstream
@@ -180,7 +180,7 @@ pub(super) fn trait_impls_of_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         }
     }
 
-    Rc::new(TraitImpls {
+    Lrc::new(TraitImpls {
         blanket_impls: blanket_impls,
         non_blanket_impls: non_blanket_impls,
     })
diff --git a/src/librustc_borrowck/Cargo.toml b/src/librustc_borrowck/Cargo.toml
index 8522fe11fe1..3368bbf3855 100644
--- a/src/librustc_borrowck/Cargo.toml
+++ b/src/librustc_borrowck/Cargo.toml
@@ -17,3 +17,4 @@ graphviz = { path = "../libgraphviz" }
 rustc = { path = "../librustc" }
 rustc_mir = { path = "../librustc_mir" }
 rustc_errors = { path = "../librustc_errors" }
+rustc_data_structures = { path = "../librustc_data_structures" }
\ No newline at end of file
diff --git a/src/librustc_borrowck/borrowck/mod.rs b/src/librustc_borrowck/borrowck/mod.rs
index 58818d0ce80..4fe6ee45295 100644
--- a/src/librustc_borrowck/borrowck/mod.rs
+++ b/src/librustc_borrowck/borrowck/mod.rs
@@ -44,6 +44,7 @@ use rustc::util::nodemap::FxHashSet;
 use std::cell::RefCell;
 use std::fmt;
 use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::hash::{Hash, Hasher};
 use syntax::ast;
 use syntax_pos::{MultiSpan, Span};
@@ -86,7 +87,7 @@ pub struct AnalysisData<'a, 'tcx: 'a> {
 }
 
 fn borrowck<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, owner_def_id: DefId)
-    -> Rc<BorrowCheckResult>
+    -> Lrc<BorrowCheckResult>
 {
     debug!("borrowck(body_owner_def_id={:?})", owner_def_id);
 
@@ -99,7 +100,7 @@ fn borrowck<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, owner_def_id: DefId)
             // those things (notably the synthesized constructors from
             // tuple structs/variants) do not have an associated body
             // and do not need borrowchecking.
-            return Rc::new(BorrowCheckResult {
+            return Lrc::new(BorrowCheckResult {
                 used_mut_nodes: FxHashSet(),
             })
         }
@@ -145,7 +146,7 @@ fn borrowck<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, owner_def_id: DefId)
     }
     unused::check(&mut bccx, body);
 
-    Rc::new(BorrowCheckResult {
+    Lrc::new(BorrowCheckResult {
         used_mut_nodes: bccx.used_mut_nodes.into_inner(),
     })
 }
@@ -243,7 +244,7 @@ pub struct BorrowckCtxt<'a, 'tcx: 'a> {
     // Some in `borrowck_fn` and cleared later
     tables: &'a ty::TypeckTables<'tcx>,
 
-    region_scope_tree: Rc<region::ScopeTree>,
+    region_scope_tree: Lrc<region::ScopeTree>,
 
     owner_def_id: DefId,
 
diff --git a/src/librustc_borrowck/lib.rs b/src/librustc_borrowck/lib.rs
index be173db23a5..2bdee3198f2 100644
--- a/src/librustc_borrowck/lib.rs
+++ b/src/librustc_borrowck/lib.rs
@@ -23,6 +23,7 @@
 extern crate syntax;
 extern crate syntax_pos;
 extern crate rustc_errors as errors;
+extern crate rustc_data_structures;
 
 // for "clarity", rename the graphviz crate to dot; graphviz within `borrowck`
 // refers to the borrowck-specific graphviz adapter traits.
diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs
index 2ae800e8cdc..15afea19213 100644
--- a/src/librustc_driver/driver.rs
+++ b/src/librustc_driver/driver.rs
@@ -49,7 +49,7 @@ use std::fs;
 use std::io::{self, Write};
 use std::iter;
 use std::path::{Path, PathBuf};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::sync::mpsc;
 use syntax::{self, ast, attr, diagnostics, visit};
 use syntax::ext::base::ExtCtxt;
@@ -621,7 +621,7 @@ pub fn phase_2_configure_and_expand<F>(sess: &Session,
                 },
 
                 analysis: ty::CrateAnalysis {
-                    access_levels: Rc::new(AccessLevels::default()),
+                    access_levels: Lrc::new(AccessLevels::default()),
                     name: crate_name.to_string(),
                     glob_map: if resolver.make_glob_map { Some(resolver.glob_map) } else { None },
                 },
diff --git a/src/librustc_driver/lib.rs b/src/librustc_driver/lib.rs
index 22c26b06430..4d1ec111c47 100644
--- a/src/librustc_driver/lib.rs
+++ b/src/librustc_driver/lib.rs
@@ -62,6 +62,7 @@ use pretty::{PpMode, UserIdentifiedItem};
 use rustc_resolve as resolve;
 use rustc_save_analysis as save;
 use rustc_save_analysis::DumpHandler;
+use rustc_data_structures::sync::Lrc;
 use rustc::session::{self, config, Session, build_session, CompileResult};
 use rustc::session::CompileIncomplete;
 use rustc::session::config::{Input, PrintRequest, ErrorOutputType};
@@ -92,7 +93,6 @@ use std::mem;
 use std::panic;
 use std::path::{PathBuf, Path};
 use std::process::{self, Command, Stdio};
-use std::rc::Rc;
 use std::str;
 use std::sync::atomic::{AtomicBool, ATOMIC_BOOL_INIT, Ordering};
 use std::sync::{Once, ONCE_INIT};
@@ -482,7 +482,7 @@ pub fn run_compiler<'a>(args: &[String],
     };
 
     let loader = file_loader.unwrap_or(box RealFileLoader);
-    let codemap = Rc::new(CodeMap::with_file_loader(loader, sopts.file_path_mapping()));
+    let codemap = Lrc::new(CodeMap::with_file_loader(loader, sopts.file_path_mapping()));
     let mut sess = session::build_session_with_codemap(
         sopts, input_file_path.clone(), descriptions, codemap, emitter_dest,
     );
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index 665a71a9089..becdbb54e5b 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -28,7 +28,7 @@ use rustc_metadata::cstore::CStore;
 use rustc::hir::map as hir_map;
 use rustc::session::{self, config};
 use rustc::session::config::{OutputFilenames, OutputTypes};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::ast;
 use syntax::abi::Abi;
 use syntax::codemap::{CodeMap, FilePathMapping, FileName};
@@ -105,8 +105,8 @@ fn test_env<F>(source_string: &str,
     let sess = session::build_session_(options,
                                        None,
                                        diagnostic_handler,
-                                       Rc::new(CodeMap::new(FilePathMapping::empty())));
-    let cstore = Rc::new(CStore::new(::get_trans(&sess).metadata_loader()));
+                                       Lrc::new(CodeMap::new(FilePathMapping::empty())));
+    let cstore = CStore::new(::get_trans(&sess).metadata_loader());
     rustc_lint::register_builtins(&mut sess.lint_store.borrow_mut(), Some(&sess));
     let input = config::Input::Str {
         name: FileName::Anon,
@@ -128,7 +128,7 @@ fn test_env<F>(source_string: &str,
     };
 
     let arenas = ty::AllArenas::new();
-    let hir_map = hir_map::map_crate(&sess, &*cstore, &mut hir_forest, &defs);
+    let hir_map = hir_map::map_crate(&sess, &cstore, &mut hir_forest, &defs);
 
     // run just enough stuff to build a tcx:
     let (tx, _rx) = mpsc::channel();
@@ -140,7 +140,7 @@ fn test_env<F>(source_string: &str,
         outputs: OutputTypes::new(&[]),
     };
     TyCtxt::create_and_enter(&sess,
-                             &*cstore,
+                             &cstore,
                              ty::maps::Providers::default(),
                              ty::maps::Providers::default(),
                              &arenas,
diff --git a/src/librustc_errors/emitter.rs b/src/librustc_errors/emitter.rs
index 0bd9b7268cb..33fce7b1968 100644
--- a/src/librustc_errors/emitter.rs
+++ b/src/librustc_errors/emitter.rs
@@ -16,10 +16,10 @@ use {Level, CodeSuggestion, DiagnosticBuilder, SubDiagnostic, CodeMapper, Diagno
 use snippet::{Annotation, AnnotationType, Line, MultilineAnnotation, StyledString, Style};
 use styled_buffer::StyledBuffer;
 
+use rustc_data_structures::sync::Lrc;
 use std::borrow::Cow;
 use std::io::prelude::*;
 use std::io;
-use std::rc::Rc;
 use term;
 use std::collections::{HashMap, HashSet};
 use std::cmp::min;
@@ -106,7 +106,7 @@ impl ColorConfig {
 
 pub struct EmitterWriter {
     dst: Destination,
-    cm: Option<Rc<CodeMapper>>,
+    cm: Option<Lrc<CodeMapper>>,
     short_message: bool,
     teach: bool,
     error_codes: HashSet<String>,
@@ -114,7 +114,7 @@ pub struct EmitterWriter {
 }
 
 struct FileWithAnnotatedLines {
-    file: Rc<FileMap>,
+    file: Lrc<FileMap>,
     lines: Vec<Line>,
     multiline_depth: usize,
 }
@@ -148,7 +148,7 @@ impl Drop for EmitterWriter {
 
 impl EmitterWriter {
     pub fn stderr(color_config: ColorConfig,
-                  code_map: Option<Rc<CodeMapper>>,
+                  code_map: Option<Lrc<CodeMapper>>,
                   short_message: bool,
                   teach: bool)
                   -> EmitterWriter {
@@ -175,7 +175,7 @@ impl EmitterWriter {
     }
 
     pub fn new(dst: Box<Write + Send>,
-               code_map: Option<Rc<CodeMapper>>,
+               code_map: Option<Lrc<CodeMapper>>,
                short_message: bool,
                teach: bool)
                -> EmitterWriter {
@@ -204,7 +204,7 @@ impl EmitterWriter {
 
     fn preprocess_annotations(&mut self, msp: &MultiSpan) -> Vec<FileWithAnnotatedLines> {
         fn add_annotation_to_file(file_vec: &mut Vec<FileWithAnnotatedLines>,
-                                  file: Rc<FileMap>,
+                                  file: Lrc<FileMap>,
                                   line_index: usize,
                                   ann: Annotation) {
 
@@ -336,7 +336,7 @@ impl EmitterWriter {
 
     fn render_source_line(&self,
                           buffer: &mut StyledBuffer,
-                          file: Rc<FileMap>,
+                          file: Lrc<FileMap>,
                           line: &Line,
                           width_offset: usize,
                           code_offset: usize) -> Vec<(usize, Style)> {
diff --git a/src/librustc_errors/lib.rs b/src/librustc_errors/lib.rs
index 236698ed2d4..3eea311a5af 100644
--- a/src/librustc_errors/lib.rs
+++ b/src/librustc_errors/lib.rs
@@ -35,13 +35,13 @@ use self::Level::*;
 
 use emitter::{Emitter, EmitterWriter};
 
+use rustc_data_structures::sync::Lrc;
 use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::stable_hasher::StableHasher;
 
 use std::borrow::Cow;
 use std::cell::{RefCell, Cell};
 use std::mem;
-use std::rc::Rc;
 use std::{error, fmt};
 use std::sync::atomic::AtomicUsize;
 use std::sync::atomic::Ordering::SeqCst;
@@ -110,7 +110,7 @@ pub trait CodeMapper {
     fn span_to_filename(&self, sp: Span) -> FileName;
     fn merge_spans(&self, sp_lhs: Span, sp_rhs: Span) -> Option<Span>;
     fn call_span_if_macro(&self, sp: Span) -> Span;
-    fn ensure_filemap_source_present(&self, file_map: Rc<FileMap>) -> bool;
+    fn ensure_filemap_source_present(&self, file_map: Lrc<FileMap>) -> bool;
     fn doctest_offset_line(&self, line: usize) -> usize;
 }
 
@@ -287,7 +287,7 @@ impl Handler {
     pub fn with_tty_emitter(color_config: ColorConfig,
                             can_emit_warnings: bool,
                             treat_err_as_bug: bool,
-                            cm: Option<Rc<CodeMapper>>)
+                            cm: Option<Lrc<CodeMapper>>)
                             -> Handler {
         Handler::with_tty_emitter_and_flags(
             color_config,
@@ -300,7 +300,7 @@ impl Handler {
     }
 
     pub fn with_tty_emitter_and_flags(color_config: ColorConfig,
-                                      cm: Option<Rc<CodeMapper>>,
+                                      cm: Option<Lrc<CodeMapper>>,
                                       flags: HandlerFlags)
                                       -> Handler {
         let emitter = Box::new(EmitterWriter::stderr(color_config, cm, false, false));
diff --git a/src/librustc_metadata/creader.rs b/src/librustc_metadata/creader.rs
index 246f5c9255e..876e7e8dc31 100644
--- a/src/librustc_metadata/creader.rs
+++ b/src/librustc_metadata/creader.rs
@@ -14,6 +14,7 @@ use cstore::{self, CStore, CrateSource, MetadataBlob};
 use locator::{self, CratePaths};
 use native_libs::relevant_lib;
 use schema::CrateRoot;
+use rustc_data_structures::sync::Lrc;
 
 use rustc::hir::def_id::{CrateNum, CRATE_DEF_INDEX};
 use rustc::hir::svh::Svh;
@@ -32,7 +33,6 @@ use rustc::hir::map::Definitions;
 use std::cell::{RefCell, Cell};
 use std::ops::Deref;
 use std::path::PathBuf;
-use std::rc::Rc;
 use std::{cmp, fs};
 
 use syntax::ast;
@@ -79,7 +79,7 @@ struct ExtensionCrate {
 }
 
 enum PMDSource {
-    Registered(Rc<cstore::CrateMetadata>),
+    Registered(Lrc<cstore::CrateMetadata>),
     Owned(Library),
 }
 
@@ -194,7 +194,7 @@ impl<'a> CrateLoader<'a> {
                       span: Span,
                       lib: Library,
                       dep_kind: DepKind)
-                      -> (CrateNum, Rc<cstore::CrateMetadata>) {
+                      -> (CrateNum, Lrc<cstore::CrateMetadata>) {
         info!("register crate `extern crate {} as {}`", name, ident);
         let crate_root = lib.metadata.get_root();
         self.verify_no_symbol_conflicts(span, &crate_root);
@@ -237,7 +237,7 @@ impl<'a> CrateLoader<'a> {
         let mut cmeta = cstore::CrateMetadata {
             name,
             extern_crate: Cell::new(None),
-            def_path_table: Rc::new(def_path_table),
+            def_path_table: Lrc::new(def_path_table),
             exported_symbols,
             trait_impls,
             proc_macros: crate_root.macro_derive_registrar.map(|_| {
@@ -274,7 +274,7 @@ impl<'a> CrateLoader<'a> {
 
         cmeta.dllimport_foreign_items = dllimports;
 
-        let cmeta = Rc::new(cmeta);
+        let cmeta = Lrc::new(cmeta);
         self.cstore.set_crate_data(cnum, cmeta.clone());
         (cnum, cmeta)
     }
@@ -287,7 +287,7 @@ impl<'a> CrateLoader<'a> {
                      span: Span,
                      path_kind: PathKind,
                      mut dep_kind: DepKind)
-                     -> (CrateNum, Rc<cstore::CrateMetadata>) {
+                     -> (CrateNum, Lrc<cstore::CrateMetadata>) {
         info!("resolving crate `extern crate {} as {}`", name, ident);
         let result = if let Some(cnum) = self.existing_match(name, hash, path_kind) {
             LoadResult::Previous(cnum)
@@ -513,7 +513,7 @@ impl<'a> CrateLoader<'a> {
     /// custom derive (and other macro-1.1 style features) are implemented via
     /// executables and custom IPC.
     fn load_derive_macros(&mut self, root: &CrateRoot, dylib: Option<PathBuf>, span: Span)
-                          -> Vec<(ast::Name, Rc<SyntaxExtension>)> {
+                          -> Vec<(ast::Name, Lrc<SyntaxExtension>)> {
         use std::{env, mem};
         use proc_macro::TokenStream;
         use proc_macro::__internal::Registry;
@@ -541,7 +541,7 @@ impl<'a> CrateLoader<'a> {
             mem::transmute::<*mut u8, fn(&mut Registry)>(sym)
         };
 
-        struct MyRegistrar(Vec<(ast::Name, Rc<SyntaxExtension>)>);
+        struct MyRegistrar(Vec<(ast::Name, Lrc<SyntaxExtension>)>);
 
         impl Registry for MyRegistrar {
             fn register_custom_derive(&mut self,
@@ -551,7 +551,7 @@ impl<'a> CrateLoader<'a> {
                 let attrs = attributes.iter().cloned().map(Symbol::intern).collect::<Vec<_>>();
                 let derive = ProcMacroDerive::new(expand, attrs.clone());
                 let derive = SyntaxExtension::ProcMacroDerive(Box::new(derive), attrs);
-                self.0.push((Symbol::intern(trait_name), Rc::new(derive)));
+                self.0.push((Symbol::intern(trait_name), Lrc::new(derive)));
             }
 
             fn register_attr_proc_macro(&mut self,
@@ -560,7 +560,7 @@ impl<'a> CrateLoader<'a> {
                 let expand = SyntaxExtension::AttrProcMacro(
                     Box::new(AttrProcMacro { inner: expand })
                 );
-                self.0.push((Symbol::intern(name), Rc::new(expand)));
+                self.0.push((Symbol::intern(name), Lrc::new(expand)));
             }
 
             fn register_bang_proc_macro(&mut self,
@@ -569,7 +569,7 @@ impl<'a> CrateLoader<'a> {
                 let expand = SyntaxExtension::ProcMacro(
                     Box::new(BangProcMacro { inner: expand })
                 );
-                self.0.push((Symbol::intern(name), Rc::new(expand)));
+                self.0.push((Symbol::intern(name), Lrc::new(expand)));
             }
         }
 
diff --git a/src/librustc_metadata/cstore.rs b/src/librustc_metadata/cstore.rs
index f3d0b38cfc0..8b59eec0190 100644
--- a/src/librustc_metadata/cstore.rs
+++ b/src/librustc_metadata/cstore.rs
@@ -23,7 +23,7 @@ use rustc_data_structures::indexed_vec::IndexVec;
 use rustc::util::nodemap::{FxHashMap, FxHashSet, NodeMap};
 
 use std::cell::{RefCell, Cell};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use rustc_data_structures::owning_ref::ErasedBoxRef;
 use syntax::{ast, attr};
 use syntax::ext::base::SyntaxExtension;
@@ -52,7 +52,7 @@ pub struct ImportedFileMap {
     /// The end of this FileMap within the codemap of its original crate
     pub original_end_pos: syntax_pos::BytePos,
     /// The imported FileMap's representation within the local codemap
-    pub translated_filemap: Rc<syntax_pos::FileMap>,
+    pub translated_filemap: Lrc<syntax_pos::FileMap>,
 }
 
 pub struct CrateMetadata {
@@ -67,7 +67,7 @@ pub struct CrateMetadata {
     pub cnum_map: RefCell<CrateNumMap>,
     pub cnum: CrateNum,
     pub codemap_import_info: RefCell<Vec<ImportedFileMap>>,
-    pub attribute_cache: RefCell<[Vec<Option<Rc<[ast::Attribute]>>>; 2]>,
+    pub attribute_cache: RefCell<[Vec<Option<Lrc<[ast::Attribute]>>>; 2]>,
 
     pub root: schema::CrateRoot,
 
@@ -76,7 +76,7 @@ pub struct CrateMetadata {
     /// hashmap, which gives the reverse mapping.  This allows us to
     /// quickly retrace a `DefPath`, which is needed for incremental
     /// compilation support.
-    pub def_path_table: Rc<DefPathTable>,
+    pub def_path_table: Lrc<DefPathTable>,
 
     pub exported_symbols: FxHashSet<DefIndex>,
 
@@ -85,13 +85,13 @@ pub struct CrateMetadata {
     pub dep_kind: Cell<DepKind>,
     pub source: CrateSource,
 
-    pub proc_macros: Option<Vec<(ast::Name, Rc<SyntaxExtension>)>>,
+    pub proc_macros: Option<Vec<(ast::Name, Lrc<SyntaxExtension>)>>,
     // Foreign items imported from a dylib (Windows only)
     pub dllimport_foreign_items: FxHashSet<DefIndex>,
 }
 
 pub struct CStore {
-    metas: RefCell<IndexVec<CrateNum, Option<Rc<CrateMetadata>>>>,
+    metas: RefCell<IndexVec<CrateNum, Option<Lrc<CrateMetadata>>>>,
     /// Map from NodeId's of local extern crate statements to crate numbers
     extern_mod_crate_map: RefCell<NodeMap<CrateNum>>,
     pub metadata_loader: Box<MetadataLoader>,
@@ -110,11 +110,11 @@ impl CStore {
         CrateNum::new(self.metas.borrow().len() + 1)
     }
 
-    pub fn get_crate_data(&self, cnum: CrateNum) -> Rc<CrateMetadata> {
+    pub fn get_crate_data(&self, cnum: CrateNum) -> Lrc<CrateMetadata> {
         self.metas.borrow()[cnum].clone().unwrap()
     }
 
-    pub fn set_crate_data(&self, cnum: CrateNum, data: Rc<CrateMetadata>) {
+    pub fn set_crate_data(&self, cnum: CrateNum, data: Lrc<CrateMetadata>) {
         use rustc_data_structures::indexed_vec::Idx;
         let mut met = self.metas.borrow_mut();
         while met.len() <= cnum.index() {
@@ -124,7 +124,7 @@ impl CStore {
     }
 
     pub fn iter_crate_data<I>(&self, mut i: I)
-        where I: FnMut(CrateNum, &Rc<CrateMetadata>)
+        where I: FnMut(CrateNum, &Lrc<CrateMetadata>)
     {
         for (k, v) in self.metas.borrow().iter_enumerated() {
             if let &Some(ref v) = v {
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index c1340d0a28a..7b8194d9eab 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -30,7 +30,7 @@ use rustc::hir::map::definitions::DefPathTable;
 use rustc::util::nodemap::{NodeSet, DefIdMap};
 
 use std::any::Any;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 use syntax::ast;
 use syntax::attr;
@@ -112,12 +112,12 @@ provide! { <'tcx> tcx, def_id, other, cdata,
         let _ = cdata;
         tcx.calculate_dtor(def_id, &mut |_,_| Ok(()))
     }
-    variances_of => { Rc::new(cdata.get_item_variances(def_id.index)) }
+    variances_of => { Lrc::new(cdata.get_item_variances(def_id.index)) }
     associated_item_def_ids => {
         let mut result = vec![];
         cdata.each_child_of_item(def_id.index,
           |child| result.push(child.def.def_id()), tcx.sess);
-        Rc::new(result)
+        Lrc::new(result)
     }
     associated_item => { cdata.get_associated_item(def_id.index) }
     impl_trait_ref => { cdata.get_impl_trait(def_id.index, tcx) }
@@ -137,11 +137,11 @@ provide! { <'tcx> tcx, def_id, other, cdata,
         mir
     }
     mir_const_qualif => {
-        (cdata.mir_const_qualif(def_id.index), Rc::new(IdxSetBuf::new_empty(0)))
+        (cdata.mir_const_qualif(def_id.index), Lrc::new(IdxSetBuf::new_empty(0)))
     }
     typeck_tables_of => { cdata.item_body_tables(def_id.index, tcx) }
     fn_sig => { cdata.fn_sig(def_id.index, tcx) }
-    inherent_impls => { Rc::new(cdata.get_inherent_implementations_for_type(def_id.index)) }
+    inherent_impls => { Lrc::new(cdata.get_inherent_implementations_for_type(def_id.index)) }
     is_const_fn => { cdata.is_const_fn(def_id.index) }
     is_foreign_item => { cdata.is_foreign_item(def_id.index) }
     describe_def => { cdata.get_def(def_id.index) }
@@ -169,18 +169,18 @@ provide! { <'tcx> tcx, def_id, other, cdata,
     }
     is_mir_available => { cdata.is_item_mir_available(def_id.index) }
 
-    dylib_dependency_formats => { Rc::new(cdata.get_dylib_dependency_formats()) }
+    dylib_dependency_formats => { Lrc::new(cdata.get_dylib_dependency_formats()) }
     is_panic_runtime => { cdata.is_panic_runtime(tcx.sess) }
     is_compiler_builtins => { cdata.is_compiler_builtins(tcx.sess) }
     has_global_allocator => { cdata.has_global_allocator() }
     is_sanitizer_runtime => { cdata.is_sanitizer_runtime(tcx.sess) }
     is_profiler_runtime => { cdata.is_profiler_runtime(tcx.sess) }
     panic_strategy => { cdata.panic_strategy() }
-    extern_crate => { Rc::new(cdata.extern_crate.get()) }
+    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 => { Rc::new(cdata.get_exported_symbols()) }
-    native_libraries => { Rc::new(cdata.get_native_libraries(tcx.sess)) }
+    exported_symbol_ids => { Lrc::new(cdata.get_exported_symbols()) }
+    native_libraries => { Lrc::new(cdata.get_native_libraries(tcx.sess)) }
     plugin_registrar_fn => {
         cdata.root.plugin_registrar_fn.map(|index| {
             DefId { krate: def_id.krate, index }
@@ -199,13 +199,13 @@ provide! { <'tcx> tcx, def_id, other, cdata,
         let mut result = vec![];
         let filter = Some(other);
         cdata.get_implementations_for_trait(filter, &mut result);
-        Rc::new(result)
+        Lrc::new(result)
     }
 
     all_trait_implementations => {
         let mut result = vec![];
         cdata.get_implementations_for_trait(None, &mut result);
-        Rc::new(result)
+        Lrc::new(result)
     }
 
     is_dllimport_foreign_item => {
@@ -217,10 +217,10 @@ provide! { <'tcx> tcx, def_id, other, cdata,
     item_children => {
         let mut result = vec![];
         cdata.each_child_of_item(def_id.index, |child| result.push(child), tcx.sess);
-        Rc::new(result)
+        Lrc::new(result)
     }
-    defined_lang_items => { Rc::new(cdata.get_lang_items()) }
-    missing_lang_items => { Rc::new(cdata.get_missing_lang_items()) }
+    defined_lang_items => { Lrc::new(cdata.get_lang_items()) }
+    missing_lang_items => { Lrc::new(cdata.get_missing_lang_items()) }
 
     extern_const_body => {
         debug!("item_body({:?}): inlining item", def_id);
@@ -234,7 +234,7 @@ provide! { <'tcx> tcx, def_id, other, cdata,
         }
     }
 
-    used_crate_source => { Rc::new(cdata.source.clone()) }
+    used_crate_source => { Lrc::new(cdata.source.clone()) }
 
     has_copy_closures => { cdata.has_copy_closures(tcx.sess) }
     has_clone_closures => { cdata.has_clone_closures(tcx.sess) }
@@ -276,11 +276,11 @@ pub fn provide<'tcx>(providers: &mut Providers<'tcx>) {
         },
         native_libraries: |tcx, cnum| {
             assert_eq!(cnum, LOCAL_CRATE);
-            Rc::new(native_libs::collect(tcx))
+            Lrc::new(native_libs::collect(tcx))
         },
         link_args: |tcx, cnum| {
             assert_eq!(cnum, LOCAL_CRATE);
-            Rc::new(link_args::collect(tcx))
+            Lrc::new(link_args::collect(tcx))
         },
 
         // Returns a map from a sufficiently visible external item (i.e. an
@@ -362,7 +362,7 @@ pub fn provide<'tcx>(providers: &mut Providers<'tcx>) {
                 }
             }
 
-            Rc::new(visible_parent_map)
+            Lrc::new(visible_parent_map)
         },
 
         ..*providers
@@ -370,7 +370,7 @@ pub fn provide<'tcx>(providers: &mut Providers<'tcx>) {
 }
 
 impl CrateStore for cstore::CStore {
-    fn crate_data_as_rc_any(&self, krate: CrateNum) -> Rc<Any> {
+    fn crate_data_as_rc_any(&self, krate: CrateNum) -> Lrc<Any> {
         self.get_crate_data(krate)
     }
 
@@ -443,7 +443,7 @@ impl CrateStore for cstore::CStore {
         self.get_crate_data(def.krate).def_path_hash(def.index)
     }
 
-    fn def_path_table(&self, cnum: CrateNum) -> Rc<DefPathTable> {
+    fn def_path_table(&self, cnum: CrateNum) -> Lrc<DefPathTable> {
         self.get_crate_data(cnum).def_path_table.clone()
     }
 
@@ -467,7 +467,7 @@ impl CrateStore for cstore::CStore {
         } else if data.name == "proc_macro" &&
                   self.get_crate_data(id.krate).item_name(id.index) == "quote" {
             let ext = SyntaxExtension::ProcMacro(Box::new(::proc_macro::__internal::Quoter));
-            return LoadedMacro::ProcMacro(Rc::new(ext));
+            return LoadedMacro::ProcMacro(Lrc::new(ext));
         }
 
         let (name, def) = data.get_macro(id.index);
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index 06728b2e625..0c6a286e227 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -13,6 +13,7 @@
 use cstore::{self, CrateMetadata, MetadataBlob, NativeLibrary};
 use schema::*;
 
+use rustc_data_structures::sync::Lrc;
 use rustc::hir::map::{DefKey, DefPath, DefPathData, DefPathHash};
 use rustc::hir;
 use rustc::middle::cstore::{LinkagePreference, ExternConstBody,
@@ -33,7 +34,6 @@ use std::cell::Ref;
 use std::collections::BTreeMap;
 use std::io;
 use std::mem;
-use std::rc::Rc;
 use std::u32;
 
 use rustc_serialize::{Decodable, Decoder, SpecializedDecoder, opaque};
@@ -773,12 +773,12 @@ impl<'a, 'tcx> CrateMetadata {
                                                    .map(|body| (body.id(), body))
                                                    .collect();
             ExternBodyNestedBodies {
-                nested_bodies: Rc::new(nested_bodies),
+                nested_bodies: Lrc::new(nested_bodies),
                 fingerprint: ast.stable_bodies_hash,
             }
         } else {
             ExternBodyNestedBodies {
-                nested_bodies: Rc::new(BTreeMap::new()),
+                nested_bodies: Lrc::new(BTreeMap::new()),
                 fingerprint: Fingerprint::ZERO,
             }
         }
@@ -868,11 +868,11 @@ impl<'a, 'tcx> CrateMetadata {
         }
     }
 
-    pub fn get_item_attrs(&self, node_id: DefIndex, sess: &Session) -> Rc<[ast::Attribute]> {
+    pub fn get_item_attrs(&self, node_id: DefIndex, sess: &Session) -> Lrc<[ast::Attribute]> {
         let (node_as, node_index) =
             (node_id.address_space().index(), node_id.as_array_index());
         if self.is_proc_macro(node_id) {
-            return Rc::new([]);
+            return Lrc::new([]);
         }
 
         if let Some(&Some(ref val)) =
@@ -888,7 +888,7 @@ impl<'a, 'tcx> CrateMetadata {
         if def_key.disambiguated_data.data == DefPathData::StructCtor {
             item = self.entry(def_key.parent.unwrap());
         }
-        let result: Rc<[ast::Attribute]> = Rc::from(self.get_attributes(&item, sess));
+        let result: Lrc<[ast::Attribute]> = Lrc::from(self.get_attributes(&item, sess));
         let vec_ = &mut self.attribute_cache.borrow_mut()[node_as];
         if vec_.len() < node_index + 1 {
             vec_.resize(node_index + 1, None);
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index d140b135416..d3f046c5544 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -36,7 +36,7 @@ use std::hash::Hash;
 use std::io::prelude::*;
 use std::io::Cursor;
 use std::path::Path;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::u32;
 use syntax::ast::{self, CRATE_NODE_ID};
 use syntax::codemap::Spanned;
@@ -60,7 +60,7 @@ pub struct EncodeContext<'a, 'tcx: 'a> {
     predicate_shorthands: FxHashMap<ty::Predicate<'tcx>, usize>,
 
     // This is used to speed up Span encoding.
-    filemap_cache: Rc<FileMap>,
+    filemap_cache: Lrc<FileMap>,
 }
 
 macro_rules! encoder_methods {
@@ -342,7 +342,7 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
                                 adapted.name.hash(&mut hasher);
                                 hasher.finish()
                             };
-                            Rc::new(adapted)
+                            Lrc::new(adapted)
                         }
                     },
                     // expanded code, not from a file
diff --git a/src/librustc_mir/borrow_check/error_reporting.rs b/src/librustc_mir/borrow_check/error_reporting.rs
index 34551e8e76f..182c9b75196 100644
--- a/src/librustc_mir/borrow_check/error_reporting.rs
+++ b/src/librustc_mir/borrow_check/error_reporting.rs
@@ -14,8 +14,7 @@ use rustc::mir::{BorrowKind, Field, Local, LocalKind, Location, Operand};
 use rustc::mir::{Place, ProjectionElem, Rvalue, Statement, StatementKind};
 use rustc::ty::{self, RegionKind};
 use rustc_data_structures::indexed_vec::Idx;
-
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 use super::{MirBorrowckCtxt, Context};
 use super::{InitializationRequiringAction, PrefixSet};
@@ -444,7 +443,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
         &mut self,
         context: Context,
         name: &String,
-        _scope_tree: &Rc<ScopeTree>,
+        _scope_tree: &Lrc<ScopeTree>,
         borrow: &BorrowData<'tcx>,
         drop_span: Span,
         borrow_span: Span,
@@ -466,7 +465,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
     fn report_scoped_temporary_value_does_not_live_long_enough(
         &mut self,
         context: Context,
-        _scope_tree: &Rc<ScopeTree>,
+        _scope_tree: &Lrc<ScopeTree>,
         borrow: &BorrowData<'tcx>,
         drop_span: Span,
         _borrow_span: Span,
@@ -490,7 +489,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
         &mut self,
         context: Context,
         name: &String,
-        scope_tree: &Rc<ScopeTree>,
+        scope_tree: &Lrc<ScopeTree>,
         borrow: &BorrowData<'tcx>,
         drop_span: Span,
         borrow_span: Span,
@@ -512,7 +511,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
     fn report_unscoped_temporary_value_does_not_live_long_enough(
         &mut self,
         context: Context,
-        scope_tree: &Rc<ScopeTree>,
+        scope_tree: &Lrc<ScopeTree>,
         borrow: &BorrowData<'tcx>,
         drop_span: Span,
         _borrow_span: Span,
diff --git a/src/librustc_mir/dataflow/impls/borrows.rs b/src/librustc_mir/dataflow/impls/borrows.rs
index 8ab4035cf4a..533bad18c38 100644
--- a/src/librustc_mir/dataflow/impls/borrows.rs
+++ b/src/librustc_mir/dataflow/impls/borrows.rs
@@ -22,6 +22,7 @@ use rustc::util::nodemap::{FxHashMap, FxHashSet};
 use rustc_data_structures::bitslice::{BitwiseOperator};
 use rustc_data_structures::indexed_set::{IdxSet};
 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
+use rustc_data_structures::sync::Lrc;
 
 use dataflow::{BitDenotation, BlockSets, InitialFlow};
 pub use dataflow::indexes::{BorrowIndex, ReserveOrActivateIndex};
@@ -44,7 +45,7 @@ use std::rc::Rc;
 pub struct Borrows<'a, 'gcx: 'tcx, 'tcx: 'a> {
     tcx: TyCtxt<'a, 'gcx, 'tcx>,
     mir: &'a Mir<'tcx>,
-    scope_tree: Rc<region::ScopeTree>,
+    scope_tree: Lrc<region::ScopeTree>,
     root_scope: Option<region::Scope>,
 
     /// The fundamental map relating bitvector indexes to the borrows
@@ -273,7 +274,7 @@ impl<'a, 'gcx, 'tcx> Borrows<'a, 'gcx, 'tcx> {
 
     pub fn borrows(&self) -> &IndexVec<BorrowIndex, BorrowData<'tcx>> { &self.borrows }
 
-    pub fn scope_tree(&self) -> &Rc<region::ScopeTree> { &self.scope_tree }
+    pub fn scope_tree(&self) -> &Lrc<region::ScopeTree> { &self.scope_tree }
 
     pub fn location(&self, idx: BorrowIndex) -> &Location {
         &self.borrows[idx].location
diff --git a/src/librustc_mir/hair/cx/mod.rs b/src/librustc_mir/hair/cx/mod.rs
index 725a1b845e7..44c41356117 100644
--- a/src/librustc_mir/hair/cx/mod.rs
+++ b/src/librustc_mir/hair/cx/mod.rs
@@ -31,7 +31,7 @@ use syntax::attr;
 use syntax::symbol::Symbol;
 use rustc::hir;
 use rustc_const_math::{ConstInt, ConstUsize};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 #[derive(Clone)]
 pub struct Cx<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
@@ -44,7 +44,7 @@ pub struct Cx<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
     /// Identity `Substs` for use with const-evaluation.
     pub identity_substs: &'gcx Substs<'gcx>,
 
-    pub region_scope_tree: Rc<region::ScopeTree>,
+    pub region_scope_tree: Lrc<region::ScopeTree>,
     pub tables: &'a ty::TypeckTables<'gcx>,
 
     /// This is `Constness::Const` if we are compiling a `static`,
diff --git a/src/librustc_mir/transform/check_unsafety.rs b/src/librustc_mir/transform/check_unsafety.rs
index 3524255e037..0bef9f0602d 100644
--- a/src/librustc_mir/transform/check_unsafety.rs
+++ b/src/librustc_mir/transform/check_unsafety.rs
@@ -10,6 +10,7 @@
 
 use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::indexed_vec::IndexVec;
+use rustc_data_structures::sync::Lrc;
 
 use rustc::ty::maps::Providers;
 use rustc::ty::{self, TyCtxt};
@@ -22,7 +23,6 @@ use rustc::mir::visit::{PlaceContext, Visitor};
 use syntax::ast;
 use syntax::symbol::Symbol;
 
-use std::rc::Rc;
 use util;
 
 pub struct UnsafetyChecker<'a, 'tcx: 'a> {
@@ -338,8 +338,8 @@ fn unsafety_check_result<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
         ClearCrossCrate::Clear => {
             debug!("unsafety_violations: {:?} - remote, skipping", def_id);
             return UnsafetyCheckResult {
-                violations: Rc::new([]),
-                unsafe_blocks: Rc::new([])
+                violations: Lrc::new([]),
+                unsafe_blocks: Lrc::new([])
             }
         }
     };
diff --git a/src/librustc_mir/transform/mod.rs b/src/librustc_mir/transform/mod.rs
index 54a7a0eafe0..e933a6cd700 100644
--- a/src/librustc_mir/transform/mod.rs
+++ b/src/librustc_mir/transform/mod.rs
@@ -18,8 +18,8 @@ use rustc::ty::steal::Steal;
 use rustc::hir;
 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
 use rustc::util::nodemap::DefIdSet;
+use rustc_data_structures::sync::Lrc;
 use std::borrow::Cow;
-use std::rc::Rc;
 use syntax::ast;
 use syntax_pos::Span;
 
@@ -67,7 +67,7 @@ fn is_mir_available<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> boo
 /// Finds the full set of def-ids within the current crate that have
 /// MIR associated with them.
 fn mir_keys<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, krate: CrateNum)
-                      -> Rc<DefIdSet> {
+                      -> Lrc<DefIdSet> {
     assert_eq!(krate, LOCAL_CRATE);
 
     let mut set = DefIdSet();
@@ -102,7 +102,7 @@ fn mir_keys<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, krate: CrateNum)
         set: &mut set,
     }.as_deep_visitor());
 
-    Rc::new(set)
+    Lrc::new(set)
 }
 
 fn mir_built<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId) -> &'tcx Steal<Mir<'tcx>> {
diff --git a/src/librustc_mir/transform/qualify_consts.rs b/src/librustc_mir/transform/qualify_consts.rs
index a8a7831c823..0b0ce1fb4d4 100644
--- a/src/librustc_mir/transform/qualify_consts.rs
+++ b/src/librustc_mir/transform/qualify_consts.rs
@@ -36,7 +36,7 @@ use syntax::feature_gate::UnstableFeatures;
 use syntax_pos::{Span, DUMMY_SP};
 
 use std::fmt;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::usize;
 
 use transform::{MirPass, MirSource};
@@ -319,7 +319,7 @@ impl<'a, 'tcx> Qualifier<'a, 'tcx, 'tcx> {
     }
 
     /// Qualify a whole const, static initializer or const fn.
-    fn qualify_const(&mut self) -> (Qualif, Rc<IdxSetBuf<Local>>) {
+    fn qualify_const(&mut self) -> (Qualif, Lrc<IdxSetBuf<Local>>) {
         debug!("qualifying {} {:?}", self.mode, self.def_id);
 
         let mir = self.mir;
@@ -436,7 +436,7 @@ impl<'a, 'tcx> Qualifier<'a, 'tcx, 'tcx> {
             }
         }
 
-        (self.qualif, Rc::new(promoted_temps))
+        (self.qualif, Lrc::new(promoted_temps))
     }
 }
 
@@ -1121,7 +1121,7 @@ pub fn provide(providers: &mut Providers) {
 
 fn mir_const_qualif<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                               def_id: DefId)
-                              -> (u8, Rc<IdxSetBuf<Local>>) {
+                              -> (u8, Lrc<IdxSetBuf<Local>>) {
     // NB: This `borrow()` is guaranteed to be valid (i.e., the value
     // cannot yet be stolen), because `mir_validated()`, which steals
     // from `mir_const(), forces this query to execute before
@@ -1130,7 +1130,7 @@ fn mir_const_qualif<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
     if mir.return_ty().references_error() {
         tcx.sess.delay_span_bug(mir.span, "mir_const_qualif: Mir had errors");
-        return (Qualif::NOT_CONST.bits(), Rc::new(IdxSetBuf::new_empty(0)));
+        return (Qualif::NOT_CONST.bits(), Lrc::new(IdxSetBuf::new_empty(0)));
     }
 
     let mut qualifier = Qualifier::new(tcx, def_id, mir, Mode::Const);
diff --git a/src/librustc_passes/Cargo.toml b/src/librustc_passes/Cargo.toml
index 776f330a58b..e87e976eac3 100644
--- a/src/librustc_passes/Cargo.toml
+++ b/src/librustc_passes/Cargo.toml
@@ -13,6 +13,7 @@ log = "0.4"
 rustc = { path = "../librustc" }
 rustc_const_eval = { path = "../librustc_const_eval" }
 rustc_const_math = { path = "../librustc_const_math" }
+rustc_data_structures = { path = "../librustc_data_structures" }
 syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
 rustc_errors = { path = "../librustc_errors" }
diff --git a/src/librustc_passes/consts.rs b/src/librustc_passes/consts.rs
index 60637bb6182..b93b759fdf8 100644
--- a/src/librustc_passes/consts.rs
+++ b/src/librustc_passes/consts.rs
@@ -45,7 +45,7 @@ use rustc::util::common::ErrorReported;
 use rustc::util::nodemap::{ItemLocalSet, NodeSet};
 use rustc::lint::builtin::CONST_ERR;
 use rustc::hir::{self, PatKind, RangeEnd};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::ast;
 use syntax_pos::{Span, DUMMY_SP};
 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
@@ -83,7 +83,7 @@ fn const_is_rvalue_promotable_to_static<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
 fn rvalue_promotable_map<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                    def_id: DefId)
-                                   -> Rc<ItemLocalSet>
+                                   -> Lrc<ItemLocalSet>
 {
     let outer_def_id = tcx.closure_base_def_id(def_id);
     if outer_def_id != def_id {
@@ -108,7 +108,7 @@ fn rvalue_promotable_map<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let body_id = tcx.hir.body_owned_by(node_id);
     visitor.visit_nested_body(body_id);
 
-    Rc::new(visitor.result)
+    Lrc::new(visitor.result)
 }
 
 struct CheckCrateVisitor<'a, 'tcx: 'a> {
diff --git a/src/librustc_passes/lib.rs b/src/librustc_passes/lib.rs
index 6b9f407cbdb..8bd95982887 100644
--- a/src/librustc_passes/lib.rs
+++ b/src/librustc_passes/lib.rs
@@ -25,6 +25,7 @@
 extern crate rustc;
 extern crate rustc_const_eval;
 extern crate rustc_const_math;
+extern crate rustc_data_structures;
 
 #[macro_use]
 extern crate log;
diff --git a/src/librustc_privacy/Cargo.toml b/src/librustc_privacy/Cargo.toml
index c65312e9a83..62eab40f3ec 100644
--- a/src/librustc_privacy/Cargo.toml
+++ b/src/librustc_privacy/Cargo.toml
@@ -13,3 +13,4 @@ rustc = { path = "../librustc" }
 rustc_typeck = { path = "../librustc_typeck" }
 syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
+rustc_data_structures = { path = "../librustc_data_structures" }
\ No newline at end of file
diff --git a/src/librustc_privacy/lib.rs b/src/librustc_privacy/lib.rs
index 2ddee0fc08d..95be691b30c 100644
--- a/src/librustc_privacy/lib.rs
+++ b/src/librustc_privacy/lib.rs
@@ -19,6 +19,7 @@
 #[macro_use] extern crate syntax;
 extern crate rustc_typeck;
 extern crate syntax_pos;
+extern crate rustc_data_structures;
 
 use rustc::hir::{self, PatKind};
 use rustc::hir::def::Def;
@@ -38,7 +39,7 @@ use syntax_pos::hygiene::SyntaxContext;
 
 use std::cmp;
 use std::mem::replace;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 mod diagnostics;
 
@@ -1646,13 +1647,13 @@ pub fn provide(providers: &mut Providers) {
     };
 }
 
-pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Rc<AccessLevels> {
+pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Lrc<AccessLevels> {
     tcx.privacy_access_levels(LOCAL_CRATE)
 }
 
 fn privacy_access_levels<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                    krate: CrateNum)
-                                   -> Rc<AccessLevels> {
+                                   -> Lrc<AccessLevels> {
     assert_eq!(krate, LOCAL_CRATE);
 
     let krate = tcx.hir.krate();
@@ -1726,7 +1727,7 @@ fn privacy_access_levels<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         krate.visit_all_item_likes(&mut DeepVisitor::new(&mut visitor));
     }
 
-    Rc::new(visitor.access_levels)
+    Lrc::new(visitor.access_levels)
 }
 
 __build_diagnostic_array! { librustc_privacy, DIAGNOSTICS }
diff --git a/src/librustc_resolve/build_reduced_graph.rs b/src/librustc_resolve/build_reduced_graph.rs
index c55bf395d71..b9899f49914 100644
--- a/src/librustc_resolve/build_reduced_graph.rs
+++ b/src/librustc_resolve/build_reduced_graph.rs
@@ -27,7 +27,7 @@ use rustc::hir::def_id::{BUILTIN_MACROS_CRATE, CRATE_DEF_INDEX, LOCAL_CRATE, Def
 use rustc::ty;
 
 use std::cell::Cell;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 use syntax::ast::{Name, Ident};
 use syntax::attr;
@@ -575,7 +575,7 @@ impl<'a> Resolver<'a> {
         }
     }
 
-    pub fn get_macro(&mut self, def: Def) -> Rc<SyntaxExtension> {
+    pub fn get_macro(&mut self, def: Def) -> Lrc<SyntaxExtension> {
         let def_id = match def {
             Def::Macro(def_id, ..) => def_id,
             _ => panic!("Expected Def::Macro(..)"),
@@ -589,7 +589,7 @@ impl<'a> Resolver<'a> {
             LoadedMacro::ProcMacro(ext) => return ext,
         };
 
-        let ext = Rc::new(macro_rules::compile(&self.session.parse_sess,
+        let ext = Lrc::new(macro_rules::compile(&self.session.parse_sess,
                                                &self.session.features,
                                                &macro_def));
         self.macro_map.insert(def_id, ext.clone());
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index 42bcc62f291..317bd9217b5 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -70,7 +70,7 @@ use std::collections::BTreeSet;
 use std::fmt;
 use std::iter;
 use std::mem::replace;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 use resolve_imports::{ImportDirective, ImportDirectiveSubclass, NameResolution, ImportResolver};
 use macros::{InvocationData, LegacyBinding, LegacyScope, MacroBinding};
@@ -1118,7 +1118,7 @@ impl<'a> NameBinding<'a> {
         }
     }
 
-    fn get_macro(&self, resolver: &mut Resolver<'a>) -> Rc<SyntaxExtension> {
+    fn get_macro(&self, resolver: &mut Resolver<'a>) -> Lrc<SyntaxExtension> {
         resolver.get_macro(self.def_ignoring_ambiguity())
     }
 
@@ -1324,7 +1324,7 @@ pub struct Resolver<'a> {
     global_macros: FxHashMap<Name, &'a NameBinding<'a>>,
     pub all_macros: FxHashMap<Name, Def>,
     lexical_macro_resolutions: Vec<(Ident, &'a Cell<LegacyScope<'a>>)>,
-    macro_map: FxHashMap<DefId, Rc<SyntaxExtension>>,
+    macro_map: FxHashMap<DefId, Lrc<SyntaxExtension>>,
     macro_defs: FxHashMap<Mark, DefId>,
     local_macro_def_scopes: FxHashMap<NodeId, Module<'a>>,
     macro_exports: Vec<Export>,
diff --git a/src/librustc_resolve/macros.rs b/src/librustc_resolve/macros.rs
index 080ef3252a6..81cc5e59bbb 100644
--- a/src/librustc_resolve/macros.rs
+++ b/src/librustc_resolve/macros.rs
@@ -40,7 +40,7 @@ use syntax_pos::{Span, DUMMY_SP};
 
 use std::cell::Cell;
 use std::mem;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 #[derive(Clone)]
 pub struct InvocationData<'a> {
@@ -185,7 +185,7 @@ impl<'a> base::Resolver for Resolver<'a> {
         invocation.expansion.set(visitor.legacy_scope);
     }
 
-    fn add_builtin(&mut self, ident: ast::Ident, ext: Rc<SyntaxExtension>) {
+    fn add_builtin(&mut self, ident: ast::Ident, ext: Lrc<SyntaxExtension>) {
         let def_id = DefId {
             krate: BUILTIN_MACROS_CRATE,
             index: DefIndex::from_array_index(self.macro_map.len(),
@@ -293,7 +293,7 @@ impl<'a> base::Resolver for Resolver<'a> {
     }
 
     fn resolve_invoc(&mut self, invoc: &mut Invocation, scope: Mark, force: bool)
-                     -> Result<Option<Rc<SyntaxExtension>>, Determinacy> {
+                     -> Result<Option<Lrc<SyntaxExtension>>, Determinacy> {
         let def = match invoc.kind {
             InvocationKind::Attr { attr: None, .. } => return Ok(None),
             _ => self.resolve_invoc_to_def(invoc, scope, force)?,
@@ -316,7 +316,7 @@ impl<'a> base::Resolver for Resolver<'a> {
     }
 
     fn resolve_macro(&mut self, scope: Mark, path: &ast::Path, kind: MacroKind, force: bool)
-                     -> Result<Rc<SyntaxExtension>, Determinacy> {
+                     -> Result<Lrc<SyntaxExtension>, Determinacy> {
         self.resolve_macro_to_def(scope, path, kind, force).map(|def| {
             self.unused_macros.remove(&def.def_id());
             self.get_macro(def)
@@ -743,7 +743,7 @@ impl<'a> Resolver<'a> {
         }
 
         let def_id = self.definitions.local_def_id(item.id);
-        let ext = Rc::new(macro_rules::compile(&self.session.parse_sess,
+        let ext = Lrc::new(macro_rules::compile(&self.session.parse_sess,
                                                &self.session.features,
                                                item));
         self.macro_map.insert(def_id, ext);
diff --git a/src/librustc_trans/attributes.rs b/src/librustc_trans/attributes.rs
index 57cd47063dc..ffa3f7f4011 100644
--- a/src/librustc_trans/attributes.rs
+++ b/src/librustc_trans/attributes.rs
@@ -10,7 +10,6 @@
 //! Set and unset common attributes on LLVM values.
 
 use std::ffi::{CStr, CString};
-use std::rc::Rc;
 
 use rustc::hir::Unsafety;
 use rustc::hir::def_id::{DefId, LOCAL_CRATE};
@@ -18,6 +17,7 @@ use rustc::session::config::Sanitizer;
 use rustc::ty::TyCtxt;
 use rustc::ty::maps::Providers;
 use rustc_data_structures::fx::FxHashSet;
+use rustc_data_structures::sync::Lrc;
 
 use llvm::{self, Attribute, ValueRef};
 use llvm::AttributePlace::Function;
@@ -140,7 +140,7 @@ fn cstr(s: &'static str) -> &CStr {
 pub fn provide(providers: &mut Providers) {
     providers.target_features_whitelist = |tcx, cnum| {
         assert_eq!(cnum, LOCAL_CRATE);
-        Rc::new(llvm_util::target_feature_whitelist(tcx.sess)
+        Lrc::new(llvm_util::target_feature_whitelist(tcx.sess)
             .iter()
             .map(|c| c.to_string())
             .collect())
@@ -173,7 +173,7 @@ pub fn provide(providers: &mut Providers) {
             }
             from_target_feature(tcx, attr, &whitelist, &mut target_features);
         }
-        Rc::new(target_features)
+        Lrc::new(target_features)
     };
 }
 
diff --git a/src/librustc_trans/back/symbol_export.rs b/src/librustc_trans/back/symbol_export.rs
index 989ef8a9537..68c0ba02650 100644
--- a/src/librustc_trans/back/symbol_export.rs
+++ b/src/librustc_trans/back/symbol_export.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::sync::Arc;
 
 use base;
@@ -64,7 +64,7 @@ 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);
-        Rc::new(tcx.exported_symbols(cnum)
+        Lrc::new(tcx.exported_symbols(cnum)
             .iter()
             .filter_map(|&(_, id, level)| {
                 id.and_then(|id| {
diff --git a/src/librustc_trans/lib.rs b/src/librustc_trans/lib.rs
index 6c281ab5e7a..6cb9d2027c7 100644
--- a/src/librustc_trans/lib.rs
+++ b/src/librustc_trans/lib.rs
@@ -73,8 +73,8 @@ pub use llvm_util::target_features;
 
 use std::any::Any;
 use std::path::PathBuf;
-use std::rc::Rc;
 use std::sync::mpsc;
+use rustc_data_structures::sync::Lrc;
 
 use rustc::dep_graph::DepGraph;
 use rustc::hir::def_id::CrateNum;
@@ -394,11 +394,11 @@ struct CrateInfo {
     profiler_runtime: Option<CrateNum>,
     sanitizer_runtime: Option<CrateNum>,
     is_no_builtins: FxHashSet<CrateNum>,
-    native_libraries: FxHashMap<CrateNum, Rc<Vec<NativeLibrary>>>,
+    native_libraries: FxHashMap<CrateNum, Lrc<Vec<NativeLibrary>>>,
     crate_name: FxHashMap<CrateNum, String>,
-    used_libraries: Rc<Vec<NativeLibrary>>,
-    link_args: Rc<Vec<String>>,
-    used_crate_source: FxHashMap<CrateNum, Rc<CrateSource>>,
+    used_libraries: Lrc<Vec<NativeLibrary>>,
+    link_args: Lrc<Vec<String>>,
+    used_crate_source: FxHashMap<CrateNum, Lrc<CrateSource>>,
     used_crates_static: Vec<(CrateNum, LibSource)>,
     used_crates_dynamic: Vec<(CrateNum, LibSource)>,
 }
diff --git a/src/librustc_trans_utils/trans_crate.rs b/src/librustc_trans_utils/trans_crate.rs
index 9943a9bd398..419371ba3e3 100644
--- a/src/librustc_trans_utils/trans_crate.rs
+++ b/src/librustc_trans_utils/trans_crate.rs
@@ -26,10 +26,10 @@ use std::io::prelude::*;
 use std::io::{self, Cursor};
 use std::fs::File;
 use std::path::Path;
-use std::rc::Rc;
 use std::sync::mpsc;
 
 use rustc_data_structures::owning_ref::{ErasedBoxRef, OwningRef};
+use rustc_data_structures::sync::Lrc;
 use ar::{Archive, Builder, Header};
 use flate2::Compression;
 use flate2::write::DeflateEncoder;
@@ -199,7 +199,7 @@ impl TransCrate for MetadataOnlyTransCrate {
     fn provide(&self, providers: &mut Providers) {
         ::symbol_names::provide(providers);
         providers.target_features_enabled = |_tcx, _id| {
-            Rc::new(Vec::new()) // Just a dummy
+            Lrc::new(Vec::new()) // Just a dummy
         };
     }
     fn provide_extern(&self, _providers: &mut Providers) {}
diff --git a/src/librustc_typeck/check/generator_interior.rs b/src/librustc_typeck/check/generator_interior.rs
index 2e45e3b1f35..c50ee13723f 100644
--- a/src/librustc_typeck/check/generator_interior.rs
+++ b/src/librustc_typeck/check/generator_interior.rs
@@ -18,7 +18,7 @@ use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
 use rustc::hir::{self, Pat, PatKind, Expr};
 use rustc::middle::region;
 use rustc::ty::{self, Ty, GeneratorInterior};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax_pos::Span;
 use super::FnCtxt;
 use util::nodemap::FxHashMap;
@@ -26,7 +26,7 @@ use util::nodemap::FxHashMap;
 struct InteriorVisitor<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
     types: FxHashMap<Ty<'tcx>, usize>,
-    region_scope_tree: Rc<region::ScopeTree>,
+    region_scope_tree: Lrc<region::ScopeTree>,
     expr_count: usize,
 }
 
diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs
index af86570309d..f7bb1a6a232 100644
--- a/src/librustc_typeck/check/method/mod.rs
+++ b/src/librustc_typeck/check/method/mod.rs
@@ -25,7 +25,7 @@ use syntax_pos::Span;
 
 use rustc::hir;
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 pub use self::MethodError::*;
 pub use self::CandidateSource::*;
@@ -165,7 +165,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         if let Some(import_id) = pick.import_id {
             let import_def_id = self.tcx.hir.local_def_id(import_id);
             debug!("used_trait_import: {:?}", import_def_id);
-            Rc::get_mut(&mut self.tables.borrow_mut().used_trait_imports)
+            Lrc::get_mut(&mut self.tables.borrow_mut().used_trait_imports)
                                         .unwrap().insert(import_def_id);
         }
 
@@ -364,7 +364,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         if let Some(import_id) = pick.import_id {
             let import_def_id = self.tcx.hir.local_def_id(import_id);
             debug!("used_trait_import: {:?}", import_def_id);
-            Rc::get_mut(&mut self.tables.borrow_mut().used_trait_imports)
+            Lrc::get_mut(&mut self.tables.borrow_mut().used_trait_imports)
                                         .unwrap().insert(import_def_id);
         }
 
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index df3d081f898..db5a458bb8c 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -110,7 +110,7 @@ use util::common::{ErrorReported, indenter};
 use util::nodemap::{DefIdMap, DefIdSet, FxHashMap, NodeMap};
 
 use std::cell::{Cell, RefCell, Ref, RefMut};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::collections::hash_map::Entry;
 use std::cmp;
 use std::fmt::Display;
@@ -814,7 +814,7 @@ fn has_typeck_tables<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 
 fn used_trait_imports<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                               def_id: DefId)
-                              -> Rc<DefIdSet> {
+                              -> Lrc<DefIdSet> {
     tcx.typeck_tables_of(def_id).used_trait_imports.clone()
 }
 
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index b5bf59fef9a..cfe8aa99bfa 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -96,7 +96,7 @@ use rustc::ty::adjustment;
 
 use std::mem;
 use std::ops::Deref;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::ast;
 use syntax_pos::Span;
 use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
@@ -189,7 +189,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 pub struct RegionCtxt<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     pub fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
 
-    pub region_scope_tree: Rc<region::ScopeTree>,
+    pub region_scope_tree: Lrc<region::ScopeTree>,
 
     outlives_environment: OutlivesEnvironment<'tcx>,
 
diff --git a/src/librustc_typeck/check/writeback.rs b/src/librustc_typeck/check/writeback.rs
index 5e102c7a445..862b15743c7 100644
--- a/src/librustc_typeck/check/writeback.rs
+++ b/src/librustc_typeck/check/writeback.rs
@@ -24,7 +24,7 @@ use rustc::util::nodemap::DefIdSet;
 use syntax::ast;
 use syntax_pos::Span;
 use std::mem;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 ///////////////////////////////////////////////////////////////////////////
 // Entry point
@@ -49,7 +49,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
 
         let used_trait_imports = mem::replace(
             &mut self.tables.borrow_mut().used_trait_imports,
-            Rc::new(DefIdSet()),
+            Lrc::new(DefIdSet()),
         );
         debug!(
             "used_trait_imports({:?}) = {:?}",
diff --git a/src/librustc_typeck/coherence/inherent_impls.rs b/src/librustc_typeck/coherence/inherent_impls.rs
index 2b81c82bc29..d43ab0d3713 100644
--- a/src/librustc_typeck/coherence/inherent_impls.rs
+++ b/src/librustc_typeck/coherence/inherent_impls.rs
@@ -24,7 +24,7 @@ use rustc::hir::itemlikevisit::ItemLikeVisitor;
 use rustc::ty::{self, CrateInherentImpls, TyCtxt};
 use rustc::util::nodemap::DefIdMap;
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::ast;
 use syntax_pos::Span;
 
@@ -48,7 +48,7 @@ pub fn crate_inherent_impls<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 /// On-demand query: yields a vector of the inherent impls for a specific type.
 pub fn inherent_impls<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                 ty_def_id: DefId)
-                                -> Rc<Vec<DefId>> {
+                                -> Lrc<Vec<DefId>> {
     assert!(ty_def_id.is_local());
 
     // NB. Until we adopt the red-green dep-tracking algorithm (see
@@ -67,7 +67,7 @@ pub fn inherent_impls<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     // [the plan]: https://github.com/rust-lang/rust-roadmap/issues/4
 
     thread_local! {
-        static EMPTY_DEF_ID_VEC: Rc<Vec<DefId>> = Rc::new(vec![])
+        static EMPTY_DEF_ID_VEC: Lrc<Vec<DefId>> = Lrc::new(vec![])
     }
 
     let result = tcx.dep_graph.with_ignore(|| {
@@ -284,11 +284,11 @@ impl<'a, 'tcx> InherentCollect<'a, 'tcx> {
             let impl_def_id = self.tcx.hir.local_def_id(item.id);
             let mut rc_vec = self.impls_map.inherent_impls
                                            .entry(def_id)
-                                           .or_insert_with(|| Rc::new(vec![]));
+                                           .or_insert_with(|| Lrc::new(vec![]));
 
             // At this point, there should not be any clones of the
-            // `Rc`, so we can still safely push into it in place:
-            Rc::get_mut(&mut rc_vec).unwrap().push(impl_def_id);
+            // `Lrc`, so we can still safely push into it in place:
+            Lrc::get_mut(&mut rc_vec).unwrap().push(impl_def_id);
         } else {
             struct_span_err!(self.tcx.sess,
                              item.span,
diff --git a/src/librustc_typeck/variance/mod.rs b/src/librustc_typeck/variance/mod.rs
index 003ee6f2599..da243650c83 100644
--- a/src/librustc_typeck/variance/mod.rs
+++ b/src/librustc_typeck/variance/mod.rs
@@ -16,7 +16,7 @@ use rustc::hir;
 use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
 use rustc::ty::{self, CrateVariancesMap, TyCtxt};
 use rustc::ty::maps::Providers;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 /// Defines the `TermsContext` basically houses an arena where we can
 /// allocate terms.
@@ -43,16 +43,16 @@ pub fn provide(providers: &mut Providers) {
 }
 
 fn crate_variances<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum)
-                             -> Rc<CrateVariancesMap> {
+                             -> Lrc<CrateVariancesMap> {
     assert_eq!(crate_num, LOCAL_CRATE);
     let mut arena = arena::TypedArena::new();
     let terms_cx = terms::determine_parameters_to_be_inferred(tcx, &mut arena);
     let constraints_cx = constraints::add_constraints_from_crate(terms_cx);
-    Rc::new(solve::solve_constraints(constraints_cx))
+    Lrc::new(solve::solve_constraints(constraints_cx))
 }
 
 fn variances_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_def_id: DefId)
-                            -> Rc<Vec<ty::Variance>> {
+                            -> Lrc<Vec<ty::Variance>> {
     let id = tcx.hir.as_local_node_id(item_def_id).expect("expected local def-id");
     let unsupported = || {
         // Variance not relevant.
diff --git a/src/librustc_typeck/variance/solve.rs b/src/librustc_typeck/variance/solve.rs
index 434e8ce148f..340a7b1d08e 100644
--- a/src/librustc_typeck/variance/solve.rs
+++ b/src/librustc_typeck/variance/solve.rs
@@ -18,7 +18,7 @@
 use rustc::hir::def_id::DefId;
 use rustc::ty;
 use rustc_data_structures::fx::FxHashMap;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 use super::constraints::*;
 use super::terms::*;
@@ -51,7 +51,7 @@ pub fn solve_constraints(constraints_cx: ConstraintContext) -> ty::CrateVariance
     };
     solutions_cx.solve();
     let variances = solutions_cx.create_map();
-    let empty_variance = Rc::new(Vec::new());
+    let empty_variance = Lrc::new(Vec::new());
 
     ty::CrateVariancesMap { variances, empty_variance }
 }
@@ -88,7 +88,7 @@ impl<'a, 'tcx> SolveContext<'a, 'tcx> {
         }
     }
 
-    fn create_map(&self) -> FxHashMap<DefId, Rc<Vec<ty::Variance>>> {
+    fn create_map(&self) -> FxHashMap<DefId, Lrc<Vec<ty::Variance>>> {
         let tcx = self.terms_cx.tcx;
 
         let solutions = &self.solutions;
@@ -109,7 +109,7 @@ impl<'a, 'tcx> SolveContext<'a, 'tcx> {
                 }
             }
 
-            (def_id, Rc::new(variances))
+            (def_id, Lrc::new(variances))
         }).collect()
     }
 
diff --git a/src/librustdoc/clean/inline.rs b/src/librustdoc/clean/inline.rs
index b382ba7f22d..090adc27ef0 100644
--- a/src/librustdoc/clean/inline.rs
+++ b/src/librustdoc/clean/inline.rs
@@ -12,8 +12,8 @@
 
 use std::collections::BTreeMap;
 use std::io;
-use std::rc::Rc;
 use std::iter::once;
+use rustc_data_structures::sync::Lrc;
 
 use syntax::ast;
 use rustc::hir;
@@ -409,7 +409,7 @@ fn build_module(cx: &DocContext, did: DefId) -> clean::Module {
 }
 
 struct InlinedConst {
-    nested_bodies: Rc<BTreeMap<hir::BodyId, hir::Body>>
+    nested_bodies: Lrc<BTreeMap<hir::BodyId, hir::Body>>
 }
 
 impl hir::print::PpAnn for InlinedConst {
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 870b5383852..f9f1c330494 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -55,6 +55,7 @@ use rustc_const_math::ConstInt;
 use std::default::Default;
 use std::{mem, slice, vec};
 use std::iter::{FromIterator, once};
+use rustc_data_structures::sync::Lrc;
 use std::rc::Rc;
 use std::cell::RefCell;
 use std::sync::Arc;
@@ -3899,7 +3900,7 @@ pub fn path_to_def(tcx: &TyCtxt, path: &[&str]) -> Option<DefId> {
                 None => return None,
             };
 
-            for item in mem::replace(&mut items, Rc::new(vec![])).iter() {
+            for item in mem::replace(&mut items, Lrc::new(vec![])).iter() {
                 if item.ident.name == *segment {
                     if path_it.peek().is_none() {
                         return match item.def {
diff --git a/src/librustdoc/core.rs b/src/librustdoc/core.rs
index 9ee0937f425..1e0fafc8d9d 100644
--- a/src/librustdoc/core.rs
+++ b/src/librustdoc/core.rs
@@ -31,6 +31,7 @@ use errors::emitter::ColorConfig;
 
 use std::cell::{RefCell, Cell};
 use std::mem;
+use rustc_data_structures::sync::Lrc;
 use std::rc::Rc;
 use std::path::PathBuf;
 
@@ -148,7 +149,7 @@ pub fn run_core(search_paths: SearchPaths,
         ..config::basic_options().clone()
     };
 
-    let codemap = Rc::new(codemap::CodeMap::new(sessopts.file_path_mapping()));
+    let codemap = Lrc::new(codemap::CodeMap::new(sessopts.file_path_mapping()));
     let diagnostic_handler = errors::Handler::with_tty_emitter(ColorConfig::Auto,
                                                                true,
                                                                false,
@@ -202,7 +203,7 @@ pub fn run_core(search_paths: SearchPaths,
         maybe_unused_extern_crates: resolver.maybe_unused_extern_crates.clone(),
     };
     let analysis = ty::CrateAnalysis {
-        access_levels: Rc::new(AccessLevels::default()),
+        access_levels: Lrc::new(AccessLevels::default()),
         name: name.to_string(),
         glob_map: if resolver.make_glob_map { Some(resolver.glob_map.clone()) } else { None },
     };
diff --git a/src/librustdoc/test.rs b/src/librustdoc/test.rs
index 12c4076c9a5..f4c9d556c8a 100644
--- a/src/librustdoc/test.rs
+++ b/src/librustdoc/test.rs
@@ -15,8 +15,8 @@ use std::io;
 use std::path::{Path, PathBuf};
 use std::panic::{self, AssertUnwindSafe};
 use std::process::Command;
-use std::rc::Rc;
 use std::str;
+use rustc_data_structures::sync::Lrc;
 use std::sync::{Arc, Mutex};
 
 use testing;
@@ -72,7 +72,7 @@ pub fn run(input_path: &Path,
         ..config::basic_options().clone()
     };
 
-    let codemap = Rc::new(CodeMap::new(sessopts.file_path_mapping()));
+    let codemap = Lrc::new(CodeMap::new(sessopts.file_path_mapping()));
     let handler =
         errors::Handler::with_tty_emitter(ColorConfig::Auto,
                                           true, false,
@@ -82,7 +82,7 @@ pub fn run(input_path: &Path,
         sessopts, Some(input_path.to_owned()), handler, codemap.clone(),
     );
     let trans = rustc_driver::get_trans(&sess);
-    let cstore = Rc::new(CStore::new(trans.metadata_loader()));
+    let cstore = CStore::new(trans.metadata_loader());
     rustc_lint::register_builtins(&mut sess.lint_store.borrow_mut(), Some(&sess));
     sess.parse_sess.config =
         config::build_configuration(&sess, config::parse_cfgspecs(cfgs.clone()));
@@ -119,7 +119,7 @@ pub fn run(input_path: &Path,
                                        linker);
 
     {
-        let map = hir::map::map_crate(&sess, &*cstore, &mut hir_forest, &defs);
+        let map = hir::map::map_crate(&sess, &cstore, &mut hir_forest, &defs);
         let krate = map.krate();
         let mut hir_collector = HirCollector {
             sess: &sess,
@@ -230,7 +230,7 @@ fn run_test(test: &str, cratename: &str, filename: &FileName, line: usize,
         }
     }
     let data = Arc::new(Mutex::new(Vec::new()));
-    let codemap = Rc::new(CodeMap::new_doctest(
+    let codemap = Lrc::new(CodeMap::new_doctest(
         sessopts.file_path_mapping(), filename.clone(), line as isize - line_offset as isize
     ));
     let emitter = errors::emitter::EmitterWriter::new(box Sink(data.clone()),
@@ -247,7 +247,7 @@ fn run_test(test: &str, cratename: &str, filename: &FileName, line: usize,
         sessopts, None, diagnostic_handler, codemap,
     );
     let trans = rustc_driver::get_trans(&sess);
-    let cstore = Rc::new(CStore::new(trans.metadata_loader()));
+    let cstore = CStore::new(trans.metadata_loader());
     rustc_lint::register_builtins(&mut sess.lint_store.borrow_mut(), Some(&sess));
 
     let outdir = Mutex::new(TempDir::new("rustdoctest").ok().expect("rustdoc needs a tempdir"));
@@ -462,7 +462,7 @@ pub struct Collector {
     opts: TestOptions,
     maybe_sysroot: Option<PathBuf>,
     position: Span,
-    codemap: Option<Rc<CodeMap>>,
+    codemap: Option<Lrc<CodeMap>>,
     filename: Option<PathBuf>,
     linker: Option<PathBuf>,
 }
@@ -470,7 +470,7 @@ pub struct Collector {
 impl Collector {
     pub fn new(cratename: String, cfgs: Vec<String>, libs: SearchPaths, externs: Externs,
                use_headers: bool, opts: TestOptions, maybe_sysroot: Option<PathBuf>,
-               codemap: Option<Rc<CodeMap>>, filename: Option<PathBuf>,
+               codemap: Option<Lrc<CodeMap>>, filename: Option<PathBuf>,
                linker: Option<PathBuf>) -> Collector {
         Collector {
             tests: Vec::new(),
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 40000bc378e..10b8e121f83 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -30,7 +30,7 @@ use tokenstream::{ThinTokenStream, TokenStream};
 use serialize::{self, Encoder, Decoder};
 use std::collections::HashSet;
 use std::fmt;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::u32;
 
 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
@@ -1274,7 +1274,7 @@ pub enum LitKind {
     /// A string literal (`"foo"`)
     Str(Symbol, StrStyle),
     /// A byte string (`b"foo"`)
-    ByteStr(Rc<Vec<u8>>),
+    ByteStr(Lrc<Vec<u8>>),
     /// A byte char (`b'f'`)
     Byte(u8),
     /// A character literal (`'a'`)
diff --git a/src/libsyntax/codemap.rs b/src/libsyntax/codemap.rs
index fcd2b236213..53ddbfbfd4a 100644
--- a/src/libsyntax/codemap.rs
+++ b/src/libsyntax/codemap.rs
@@ -24,11 +24,11 @@ pub use self::ExpnFormat::*;
 
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::stable_hasher::StableHasher;
+use rustc_data_structures::sync::Lrc;
 use std::cell::{RefCell, Ref};
 use std::cmp;
 use std::hash::Hash;
 use std::path::{Path, PathBuf};
-use std::rc::Rc;
 
 use std::env;
 use std::fs;
@@ -126,12 +126,12 @@ impl StableFilemapId {
 //
 
 pub struct CodeMap {
-    pub(super) files: RefCell<Vec<Rc<FileMap>>>,
+    pub(super) files: RefCell<Vec<Lrc<FileMap>>>,
     file_loader: Box<FileLoader>,
     // This is used to apply the file path remapping as specified via
     // --remap-path-prefix to all FileMaps allocated within this CodeMap.
     path_mapping: FilePathMapping,
-    stable_id_to_filemap: RefCell<FxHashMap<StableFilemapId, Rc<FileMap>>>,
+    stable_id_to_filemap: RefCell<FxHashMap<StableFilemapId, Lrc<FileMap>>>,
     /// In case we are in a doctest, replace all file names with the PathBuf,
     /// and add the given offsets to the line info
     doctest_offset: Option<(FileName, isize)>,
@@ -177,7 +177,7 @@ impl CodeMap {
         self.file_loader.file_exists(path)
     }
 
-    pub fn load_file(&self, path: &Path) -> io::Result<Rc<FileMap>> {
+    pub fn load_file(&self, path: &Path) -> io::Result<Lrc<FileMap>> {
         let src = self.file_loader.read_file(path)?;
         let filename = if let Some((ref name, _)) = self.doctest_offset {
             name.clone()
@@ -187,11 +187,11 @@ impl CodeMap {
         Ok(self.new_filemap(filename, src))
     }
 
-    pub fn files(&self) -> Ref<Vec<Rc<FileMap>>> {
+    pub fn files(&self) -> Ref<Vec<Lrc<FileMap>>> {
         self.files.borrow()
     }
 
-    pub fn filemap_by_stable_id(&self, stable_id: StableFilemapId) -> Option<Rc<FileMap>> {
+    pub fn filemap_by_stable_id(&self, stable_id: StableFilemapId) -> Option<Lrc<FileMap>> {
         self.stable_id_to_filemap.borrow().get(&stable_id).map(|fm| fm.clone())
     }
 
@@ -207,7 +207,7 @@ impl CodeMap {
 
     /// Creates a new filemap without setting its line information. If you don't
     /// intend to set the line information yourself, you should use new_filemap_and_lines.
-    pub fn new_filemap(&self, filename: FileName, src: String) -> Rc<FileMap> {
+    pub fn new_filemap(&self, filename: FileName, src: String) -> Lrc<FileMap> {
         let start_pos = self.next_start_pos();
         let mut files = self.files.borrow_mut();
 
@@ -225,7 +225,7 @@ impl CodeMap {
             },
             other => (other, false),
         };
-        let filemap = Rc::new(FileMap::new(
+        let filemap = Lrc::new(FileMap::new(
             filename,
             was_remapped,
             unmapped_path,
@@ -243,7 +243,7 @@ impl CodeMap {
     }
 
     /// Creates a new filemap and sets its line information.
-    pub fn new_filemap_and_lines(&self, filename: &Path, src: &str) -> Rc<FileMap> {
+    pub fn new_filemap_and_lines(&self, filename: &Path, src: &str) -> Lrc<FileMap> {
         let fm = self.new_filemap(filename.to_owned().into(), src.to_owned());
         let mut byte_pos: u32 = fm.start_pos.0;
         for line in src.lines() {
@@ -271,7 +271,7 @@ impl CodeMap {
                                 mut file_local_lines: Vec<BytePos>,
                                 mut file_local_multibyte_chars: Vec<MultiByteChar>,
                                 mut file_local_non_narrow_chars: Vec<NonNarrowChar>)
-                                -> Rc<FileMap> {
+                                -> Lrc<FileMap> {
         let start_pos = self.next_start_pos();
         let mut files = self.files.borrow_mut();
 
@@ -290,7 +290,7 @@ impl CodeMap {
             *swc = *swc + start_pos;
         }
 
-        let filemap = Rc::new(FileMap {
+        let filemap = Lrc::new(FileMap {
             name: filename,
             name_was_remapped,
             unmapped_path: None,
@@ -398,7 +398,7 @@ impl CodeMap {
     }
 
     // If the relevant filemap is empty, we don't return a line number.
-    pub fn lookup_line(&self, pos: BytePos) -> Result<FileMapAndLine, Rc<FileMap>> {
+    pub fn lookup_line(&self, pos: BytePos) -> Result<FileMapAndLine, Lrc<FileMap>> {
         let idx = self.lookup_filemap_idx(pos);
 
         let files = self.files.borrow();
@@ -730,7 +730,7 @@ impl CodeMap {
         }
     }
 
-    pub fn get_filemap(&self, filename: &FileName) -> Option<Rc<FileMap>> {
+    pub fn get_filemap(&self, filename: &FileName) -> Option<Lrc<FileMap>> {
         for fm in self.files.borrow().iter() {
             if *filename == fm.name {
                 return Some(fm.clone());
@@ -827,7 +827,7 @@ impl CodeMapper for CodeMap {
         }
         sp
     }
-    fn ensure_filemap_source_present(&self, file_map: Rc<FileMap>) -> bool {
+    fn ensure_filemap_source_present(&self, file_map: Lrc<FileMap>) -> bool {
         file_map.add_external_src(
             || match file_map.name {
                 FileName::Real(ref name) => self.file_loader.read_file(name).ok(),
@@ -883,7 +883,7 @@ impl FilePathMapping {
 mod tests {
     use super::*;
     use std::borrow::Cow;
-    use std::rc::Rc;
+    use rustc_data_structures::sync::Lrc;
 
     #[test]
     fn t1 () {
@@ -1104,7 +1104,7 @@ mod tests {
     /// `substring` in `source_text`.
     trait CodeMapExtension {
         fn span_substr(&self,
-                    file: &Rc<FileMap>,
+                    file: &Lrc<FileMap>,
                     source_text: &str,
                     substring: &str,
                     n: usize)
@@ -1113,7 +1113,7 @@ mod tests {
 
     impl CodeMapExtension for CodeMap {
         fn span_substr(&self,
-                    file: &Rc<FileMap>,
+                    file: &Lrc<FileMap>,
                     source_text: &str,
                     substring: &str,
                     n: usize)
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 520ec942e42..7b333270d04 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -28,6 +28,7 @@ use std::collections::HashMap;
 use std::iter;
 use std::path::PathBuf;
 use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::default::Default;
 use tokenstream::{self, TokenStream};
 
@@ -615,15 +616,15 @@ pub trait Resolver {
     fn is_whitelisted_legacy_custom_derive(&self, name: Name) -> bool;
 
     fn visit_expansion(&mut self, mark: Mark, expansion: &Expansion, derives: &[Mark]);
-    fn add_builtin(&mut self, ident: ast::Ident, ext: Rc<SyntaxExtension>);
+    fn add_builtin(&mut self, ident: ast::Ident, ext: Lrc<SyntaxExtension>);
 
     fn resolve_imports(&mut self);
     // Resolves attribute and derive legacy macros from `#![plugin(..)]`.
     fn find_legacy_attr_invoc(&mut self, attrs: &mut Vec<Attribute>) -> Option<Attribute>;
     fn resolve_invoc(&mut self, invoc: &mut Invocation, scope: Mark, force: bool)
-                     -> Result<Option<Rc<SyntaxExtension>>, Determinacy>;
+                     -> Result<Option<Lrc<SyntaxExtension>>, Determinacy>;
     fn resolve_macro(&mut self, scope: Mark, path: &ast::Path, kind: MacroKind, force: bool)
-                     -> Result<Rc<SyntaxExtension>, Determinacy>;
+                     -> Result<Lrc<SyntaxExtension>, Determinacy>;
     fn check_unused_macros(&self);
 }
 
@@ -642,16 +643,16 @@ impl Resolver for DummyResolver {
     fn is_whitelisted_legacy_custom_derive(&self, _name: Name) -> bool { false }
 
     fn visit_expansion(&mut self, _invoc: Mark, _expansion: &Expansion, _derives: &[Mark]) {}
-    fn add_builtin(&mut self, _ident: ast::Ident, _ext: Rc<SyntaxExtension>) {}
+    fn add_builtin(&mut self, _ident: ast::Ident, _ext: Lrc<SyntaxExtension>) {}
 
     fn resolve_imports(&mut self) {}
     fn find_legacy_attr_invoc(&mut self, _attrs: &mut Vec<Attribute>) -> Option<Attribute> { None }
     fn resolve_invoc(&mut self, _invoc: &mut Invocation, _scope: Mark, _force: bool)
-                     -> Result<Option<Rc<SyntaxExtension>>, Determinacy> {
+                     -> Result<Option<Lrc<SyntaxExtension>>, Determinacy> {
         Err(Determinacy::Determined)
     }
     fn resolve_macro(&mut self, _scope: Mark, _path: &ast::Path, _kind: MacroKind,
-                     _force: bool) -> Result<Rc<SyntaxExtension>, Determinacy> {
+                     _force: bool) -> Result<Lrc<SyntaxExtension>, Determinacy> {
         Err(Determinacy::Determined)
     }
     fn check_unused_macros(&self) {}
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index d4d9dfb01da..377f47a3ea5 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -305,7 +305,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
             let (expansion, new_invocations) = if let Some(ext) = ext {
                 if let Some(ext) = ext {
                     let dummy = invoc.expansion_kind.dummy(invoc.span()).unwrap();
-                    let expansion = self.expand_invoc(invoc, ext).unwrap_or(dummy);
+                    let expansion = self.expand_invoc(invoc, &*ext).unwrap_or(dummy);
                     self.collect_invocations(expansion, &[])
                 } else if let InvocationKind::Attr { attr: None, traits, item } = invoc.kind {
                     if !item.derive_allowed() {
@@ -437,7 +437,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
         }
     }
 
-    fn expand_invoc(&mut self, invoc: Invocation, ext: Rc<SyntaxExtension>) -> Option<Expansion> {
+    fn expand_invoc(&mut self, invoc: Invocation, ext: &SyntaxExtension) -> Option<Expansion> {
         let result = match invoc.kind {
             InvocationKind::Bang { .. } => self.expand_bang_invoc(invoc, ext)?,
             InvocationKind::Attr { .. } => self.expand_attr_invoc(invoc, ext)?,
@@ -463,7 +463,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
 
     fn expand_attr_invoc(&mut self,
                          invoc: Invocation,
-                         ext: Rc<SyntaxExtension>)
+                         ext: &SyntaxExtension)
                          -> Option<Expansion> {
         let Invocation { expansion_kind: kind, .. } = invoc;
         let (attr, item) = match invoc.kind {
@@ -521,7 +521,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
     /// Expand a macro invocation. Returns the result of expansion.
     fn expand_bang_invoc(&mut self,
                          invoc: Invocation,
-                         ext: Rc<SyntaxExtension>)
+                         ext: &SyntaxExtension)
                          -> Option<Expansion> {
         let (mark, kind) = (invoc.expansion_data.mark, invoc.expansion_kind);
         let (mac, ident, span) = match invoc.kind {
@@ -654,7 +654,7 @@ impl<'a, 'b> MacroExpander<'a, 'b> {
     /// Expand a derive invocation. Returns the result of expansion.
     fn expand_derive_invoc(&mut self,
                            invoc: Invocation,
-                           ext: Rc<SyntaxExtension>)
+                           ext: &SyntaxExtension)
                            -> Option<Expansion> {
         let Invocation { expansion_kind: kind, .. } = invoc;
         let (path, item) = match invoc.kind {
diff --git a/src/libsyntax/ext/source_util.rs b/src/libsyntax/ext/source_util.rs
index ec4e6ced1b2..d6dce63ea5e 100644
--- a/src/libsyntax/ext/source_util.rs
+++ b/src/libsyntax/ext/source_util.rs
@@ -24,7 +24,7 @@ use util::small_vector::SmallVector;
 use std::fs::File;
 use std::io::prelude::*;
 use std::path::PathBuf;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 // These macros all relate to the file system; they either return
 // the column/row/filename of the expression, or they include
@@ -184,7 +184,7 @@ pub fn expand_include_bytes(cx: &mut ExtCtxt, sp: Span, tts: &[tokenstream::Toke
             // dependency information, but don't enter it's contents
             cx.codemap().new_filemap_and_lines(&file, "");
 
-            base::MacEager::expr(cx.expr_lit(sp, ast::LitKind::ByteStr(Rc::new(bytes))))
+            base::MacEager::expr(cx.expr_lit(sp, ast::LitKind::ByteStr(Lrc::new(bytes))))
         }
     }
 }
diff --git a/src/libsyntax/ext/tt/macro_rules.rs b/src/libsyntax/ext/tt/macro_rules.rs
index 5254c751e6b..728b3e4076d 100644
--- a/src/libsyntax/ext/tt/macro_rules.rs
+++ b/src/libsyntax/ext/tt/macro_rules.rs
@@ -29,7 +29,8 @@ use tokenstream::{TokenStream, TokenTree};
 use std::cell::RefCell;
 use std::collections::HashMap;
 use std::collections::hash_map::Entry;
-use std::rc::Rc;
+
+use rustc_data_structures::sync::Lrc;
 
 pub struct ParserAnyMacro<'a> {
     parser: Parser<'a>,
@@ -199,7 +200,7 @@ pub fn compile(sess: &ParseSess, features: &RefCell<Features>, def: &ast::Item)
     // ...quasiquoting this would be nice.
     // These spans won't matter, anyways
     let argument_gram = vec![
-        quoted::TokenTree::Sequence(DUMMY_SP, Rc::new(quoted::SequenceRepetition {
+        quoted::TokenTree::Sequence(DUMMY_SP, Lrc::new(quoted::SequenceRepetition {
             tts: vec![
                 quoted::TokenTree::MetaVarDecl(DUMMY_SP, lhs_nm, ast::Ident::from_str("tt")),
                 quoted::TokenTree::Token(DUMMY_SP, token::FatArrow),
@@ -210,7 +211,7 @@ pub fn compile(sess: &ParseSess, features: &RefCell<Features>, def: &ast::Item)
             num_captures: 2,
         })),
         // to phase into semicolon-termination instead of semicolon-separation
-        quoted::TokenTree::Sequence(DUMMY_SP, Rc::new(quoted::SequenceRepetition {
+        quoted::TokenTree::Sequence(DUMMY_SP, Lrc::new(quoted::SequenceRepetition {
             tts: vec![quoted::TokenTree::Token(DUMMY_SP, token::Semi)],
             separator: None,
             op: quoted::KleeneOp::ZeroOrMore,
diff --git a/src/libsyntax/ext/tt/quoted.rs b/src/libsyntax/ext/tt/quoted.rs
index 982b60b81e4..c9d7f78c2e3 100644
--- a/src/libsyntax/ext/tt/quoted.rs
+++ b/src/libsyntax/ext/tt/quoted.rs
@@ -19,7 +19,7 @@ use tokenstream;
 
 use std::cell::RefCell;
 use std::iter::Peekable;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 /// Contains the sub-token-trees of a "delimited" token tree, such as the contents of `(`. Note
 /// that the delimiter itself might be `NoDelim`.
@@ -89,9 +89,9 @@ pub enum KleeneOp {
 #[derive(Debug, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 pub enum TokenTree {
     Token(Span, token::Token),
-    Delimited(Span, Rc<Delimited>),
+    Delimited(Span, Lrc<Delimited>),
     /// A kleene-style repetition sequence
-    Sequence(Span, Rc<SequenceRepetition>),
+    Sequence(Span, Lrc<SequenceRepetition>),
     /// E.g. `$var`
     MetaVar(Span, ast::Ident),
     /// E.g. `$var:expr`. This is only used in the left hand side of MBE macros.
@@ -278,7 +278,7 @@ where
                 let name_captures = macro_parser::count_names(&sequence);
                 TokenTree::Sequence(
                     span,
-                    Rc::new(SequenceRepetition {
+                    Lrc::new(SequenceRepetition {
                         tts: sequence,
                         separator,
                         op,
@@ -324,7 +324,7 @@ where
         // descend into the delimited set and further parse it.
         tokenstream::TokenTree::Delimited(span, delimited) => TokenTree::Delimited(
             span,
-            Rc::new(Delimited {
+            Lrc::new(Delimited {
                 delim: delimited.delim,
                 tts: parse(delimited.tts.into(), expect_matchers, sess, features, attrs),
             }),
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index d51b0d0ae3e..7883c4bbc16 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -20,6 +20,7 @@ use tokenstream::{TokenStream, TokenTree, Delimited};
 use util::small_vector::SmallVector;
 
 use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::mem;
 use std::ops::Add;
 use std::collections::HashMap;
@@ -27,12 +28,12 @@ use std::collections::HashMap;
 // An iterator over the token trees in a delimited token tree (`{ ... }`) or a sequence (`$(...)`).
 enum Frame {
     Delimited {
-        forest: Rc<quoted::Delimited>,
+        forest: Lrc<quoted::Delimited>,
         idx: usize,
         span: Span,
     },
     Sequence {
-        forest: Rc<quoted::SequenceRepetition>,
+        forest: Lrc<quoted::SequenceRepetition>,
         idx: usize,
         sep: Option<Token>,
     },
@@ -40,7 +41,7 @@ enum Frame {
 
 impl Frame {
     fn new(tts: Vec<quoted::TokenTree>) -> Frame {
-        let forest = Rc::new(quoted::Delimited { delim: token::NoDelim, tts: tts });
+        let forest = Lrc::new(quoted::Delimited { delim: token::NoDelim, tts: tts });
         Frame::Delimited { forest: forest, idx: 0, span: DUMMY_SP }
     }
 }
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 1963ab45f1a..bc1854d3cd8 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -29,7 +29,7 @@ use tokenstream::*;
 use util::small_vector::SmallVector;
 use util::move_map::MoveMap;
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 pub trait Folder : Sized {
     // Any additions to this trait should happen in form
@@ -580,7 +580,7 @@ pub fn noop_fold_token<T: Folder>(t: token::Token, fld: &mut T) -> token::Token
         token::Ident(id) => token::Ident(fld.fold_ident(id)),
         token::Lifetime(id) => token::Lifetime(fld.fold_ident(id)),
         token::Interpolated(nt) => {
-            let nt = match Rc::try_unwrap(nt) {
+            let nt = match Lrc::try_unwrap(nt) {
                 Ok(nt) => nt,
                 Err(nt) => (*nt).clone(),
             };
diff --git a/src/libsyntax/json.rs b/src/libsyntax/json.rs
index 57f07ff33f5..eed3c691405 100644
--- a/src/libsyntax/json.rs
+++ b/src/libsyntax/json.rs
@@ -26,7 +26,7 @@ use errors::{DiagnosticBuilder, SubDiagnostic, CodeSuggestion, CodeMapper};
 use errors::DiagnosticId;
 use errors::emitter::{Emitter, EmitterWriter};
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::io::{self, Write};
 use std::vec;
 use std::sync::{Arc, Mutex};
@@ -36,7 +36,7 @@ use rustc_serialize::json::{as_json, as_pretty_json};
 pub struct JsonEmitter {
     dst: Box<Write + Send>,
     registry: Option<Registry>,
-    cm: Rc<CodeMapper + 'static>,
+    cm: Lrc<CodeMapper + 'static>,
     pretty: bool,
     /// Whether "approximate suggestions" are enabled in the config
     approximate_suggestions: bool,
@@ -45,7 +45,7 @@ pub struct JsonEmitter {
 
 impl JsonEmitter {
     pub fn stderr(registry: Option<Registry>,
-                  code_map: Rc<CodeMap>,
+                  code_map: Lrc<CodeMap>,
                   pretty: bool,
                   approximate_suggestions: bool) -> JsonEmitter {
         JsonEmitter {
@@ -60,13 +60,13 @@ impl JsonEmitter {
 
     pub fn basic(pretty: bool) -> JsonEmitter {
         let file_path_mapping = FilePathMapping::empty();
-        JsonEmitter::stderr(None, Rc::new(CodeMap::new(file_path_mapping)),
+        JsonEmitter::stderr(None, Lrc::new(CodeMap::new(file_path_mapping)),
                             pretty, false)
     }
 
     pub fn new(dst: Box<Write + Send>,
                registry: Option<Registry>,
-               code_map: Rc<CodeMap>,
+               code_map: Lrc<CodeMap>,
                pretty: bool,
                approximate_suggestions: bool) -> JsonEmitter {
         JsonEmitter {
diff --git a/src/libsyntax/parse/lexer/mod.rs b/src/libsyntax/parse/lexer/mod.rs
index 11ab84a5729..b5368b3ecab 100644
--- a/src/libsyntax/parse/lexer/mod.rs
+++ b/src/libsyntax/parse/lexer/mod.rs
@@ -20,7 +20,7 @@ use std_unicode::property::Pattern_White_Space;
 use std::borrow::Cow;
 use std::char;
 use std::mem::replace;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 pub mod comments;
 mod tokentrees;
@@ -48,7 +48,7 @@ pub struct StringReader<'a> {
     pub col: CharPos,
     /// The current character (which has been read from self.pos)
     pub ch: Option<char>,
-    pub filemap: Rc<syntax_pos::FileMap>,
+    pub filemap: Lrc<syntax_pos::FileMap>,
     /// If Some, stop reading the source at this position (inclusive).
     pub terminator: Option<BytePos>,
     /// Whether to record new-lines and multibyte chars in filemap.
@@ -61,7 +61,7 @@ pub struct StringReader<'a> {
     pub fatal_errs: Vec<DiagnosticBuilder<'a>>,
     // cache a direct reference to the source text, so that we don't have to
     // retrieve it via `self.filemap.src.as_ref().unwrap()` all the time.
-    source_text: Rc<String>,
+    source_text: Lrc<String>,
     /// Stack of open delimiters and their spans. Used for error message.
     token: token::Token,
     span: Span,
@@ -152,13 +152,13 @@ impl<'a> StringReader<'a> {
 
 impl<'a> StringReader<'a> {
     /// For comments.rs, which hackily pokes into next_pos and ch
-    pub fn new_raw(sess: &'a ParseSess, filemap: Rc<syntax_pos::FileMap>) -> Self {
+    pub fn new_raw(sess: &'a ParseSess, filemap: Lrc<syntax_pos::FileMap>) -> Self {
         let mut sr = StringReader::new_raw_internal(sess, filemap);
         sr.bump();
         sr
     }
 
-    fn new_raw_internal(sess: &'a ParseSess, filemap: Rc<syntax_pos::FileMap>) -> Self {
+    fn new_raw_internal(sess: &'a ParseSess, filemap: Lrc<syntax_pos::FileMap>) -> Self {
         if filemap.src.is_none() {
             sess.span_diagnostic.bug(&format!("Cannot lex filemap without source: {}",
                                               filemap.name));
@@ -187,7 +187,7 @@ impl<'a> StringReader<'a> {
         }
     }
 
-    pub fn new(sess: &'a ParseSess, filemap: Rc<syntax_pos::FileMap>) -> Self {
+    pub fn new(sess: &'a ParseSess, filemap: Lrc<syntax_pos::FileMap>) -> Self {
         let mut sr = StringReader::new_raw(sess, filemap);
         if sr.advance_token().is_err() {
             sr.emit_fatal_errors();
@@ -1747,9 +1747,7 @@ mod tests {
     use std::collections::HashSet;
     use std::io;
     use std::path::PathBuf;
-    use std::rc::Rc;
-
-    fn mk_sess(cm: Rc<CodeMap>) -> ParseSess {
+    fn mk_sess(cm: Lrc<CodeMap>) -> ParseSess {
         let emitter = errors::emitter::EmitterWriter::new(Box::new(io::sink()),
                                                           Some(cm.clone()),
                                                           false,
@@ -1776,7 +1774,7 @@ mod tests {
 
     #[test]
     fn t1() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         let mut string_reader = setup(&cm,
                                       &sh,
@@ -1820,7 +1818,7 @@ mod tests {
 
     #[test]
     fn doublecolonparsing() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         check_tokenization(setup(&cm, &sh, "a b".to_string()),
                            vec![mk_ident("a"), token::Whitespace, mk_ident("b")]);
@@ -1828,7 +1826,7 @@ mod tests {
 
     #[test]
     fn dcparsing_2() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         check_tokenization(setup(&cm, &sh, "a::b".to_string()),
                            vec![mk_ident("a"), token::ModSep, mk_ident("b")]);
@@ -1836,7 +1834,7 @@ mod tests {
 
     #[test]
     fn dcparsing_3() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         check_tokenization(setup(&cm, &sh, "a ::b".to_string()),
                            vec![mk_ident("a"), token::Whitespace, token::ModSep, mk_ident("b")]);
@@ -1844,7 +1842,7 @@ mod tests {
 
     #[test]
     fn dcparsing_4() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         check_tokenization(setup(&cm, &sh, "a:: b".to_string()),
                            vec![mk_ident("a"), token::ModSep, token::Whitespace, mk_ident("b")]);
@@ -1852,7 +1850,7 @@ mod tests {
 
     #[test]
     fn character_a() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         assert_eq!(setup(&cm, &sh, "'a'".to_string()).next_token().tok,
                    token::Literal(token::Char(Symbol::intern("a")), None));
@@ -1860,7 +1858,7 @@ mod tests {
 
     #[test]
     fn character_space() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         assert_eq!(setup(&cm, &sh, "' '".to_string()).next_token().tok,
                    token::Literal(token::Char(Symbol::intern(" ")), None));
@@ -1868,7 +1866,7 @@ mod tests {
 
     #[test]
     fn character_escaped() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         assert_eq!(setup(&cm, &sh, "'\\n'".to_string()).next_token().tok,
                    token::Literal(token::Char(Symbol::intern("\\n")), None));
@@ -1876,7 +1874,7 @@ mod tests {
 
     #[test]
     fn lifetime_name() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         assert_eq!(setup(&cm, &sh, "'abc".to_string()).next_token().tok,
                    token::Lifetime(Ident::from_str("'abc")));
@@ -1884,7 +1882,7 @@ mod tests {
 
     #[test]
     fn raw_string() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         assert_eq!(setup(&cm, &sh, "r###\"\"#a\\b\x00c\"\"###".to_string())
                        .next_token()
@@ -1894,7 +1892,7 @@ mod tests {
 
     #[test]
     fn literal_suffixes() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         macro_rules! test {
             ($input: expr, $tok_type: ident, $tok_contents: expr) => {{
@@ -1938,7 +1936,7 @@ mod tests {
 
     #[test]
     fn nested_block_comments() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         let mut lexer = setup(&cm, &sh, "/* /* */ */'a'".to_string());
         match lexer.next_token().tok {
@@ -1951,7 +1949,7 @@ mod tests {
 
     #[test]
     fn crlf_comments() {
-        let cm = Rc::new(CodeMap::new(FilePathMapping::empty()));
+        let cm = Lrc::new(CodeMap::new(FilePathMapping::empty()));
         let sh = mk_sess(cm.clone());
         let mut lexer = setup(&cm, &sh, "// test\r\n/// test\r\n".to_string());
         let comment = lexer.next_token();
diff --git a/src/libsyntax/parse/mod.rs b/src/libsyntax/parse/mod.rs
index 06eb64e157c..1d9af682fec 100644
--- a/src/libsyntax/parse/mod.rs
+++ b/src/libsyntax/parse/mod.rs
@@ -10,6 +10,7 @@
 
 //! The main parser interface
 
+use rustc_data_structures::sync::Lrc;
 use ast::{self, CrateConfig};
 use codemap::{CodeMap, FilePathMapping};
 use syntax_pos::{self, Span, FileMap, NO_EXPANSION, FileName};
@@ -25,7 +26,6 @@ use std::cell::RefCell;
 use std::collections::HashSet;
 use std::iter;
 use std::path::{Path, PathBuf};
-use std::rc::Rc;
 use std::str;
 
 pub type PResult<'a, T> = Result<T, DiagnosticBuilder<'a>>;
@@ -52,12 +52,12 @@ pub struct ParseSess {
     pub non_modrs_mods: RefCell<Vec<(ast::Ident, Span)>>,
     /// Used to determine and report recursive mod inclusions
     included_mod_stack: RefCell<Vec<PathBuf>>,
-    code_map: Rc<CodeMap>,
+    code_map: Lrc<CodeMap>,
 }
 
 impl ParseSess {
     pub fn new(file_path_mapping: FilePathMapping) -> Self {
-        let cm = Rc::new(CodeMap::new(file_path_mapping));
+        let cm = Lrc::new(CodeMap::new(file_path_mapping));
         let handler = Handler::with_tty_emitter(ColorConfig::Auto,
                                                 true,
                                                 false,
@@ -65,7 +65,7 @@ impl ParseSess {
         ParseSess::with_span_handler(handler, cm)
     }
 
-    pub fn with_span_handler(handler: Handler, code_map: Rc<CodeMap>) -> ParseSess {
+    pub fn with_span_handler(handler: Handler, code_map: Lrc<CodeMap>) -> ParseSess {
         ParseSess {
             span_diagnostic: handler,
             unstable_features: UnstableFeatures::from_environment(),
@@ -183,7 +183,7 @@ pub fn new_sub_parser_from_file<'a>(sess: &'a ParseSess,
 }
 
 /// Given a filemap and config, return a parser
-pub fn filemap_to_parser(sess: & ParseSess, filemap: Rc<FileMap>, ) -> Parser {
+pub fn filemap_to_parser(sess: & ParseSess, filemap: Lrc<FileMap>) -> Parser {
     let end_pos = filemap.end_pos;
     let mut parser = stream_to_parser(sess, filemap_to_stream(sess, filemap, None));
 
@@ -206,7 +206,7 @@ pub fn new_parser_from_tts(sess: &ParseSess, tts: Vec<TokenTree>) -> Parser {
 /// Given a session and a path and an optional span (for error reporting),
 /// add the path to the session's codemap and return the new filemap.
 fn file_to_filemap(sess: &ParseSess, path: &Path, spanopt: Option<Span>)
-                   -> Rc<FileMap> {
+                   -> Lrc<FileMap> {
     match sess.codemap().load_file(path) {
         Ok(filemap) => filemap,
         Err(e) => {
@@ -220,7 +220,7 @@ fn file_to_filemap(sess: &ParseSess, path: &Path, spanopt: Option<Span>)
 }
 
 /// Given a filemap, produce a sequence of token-trees
-pub fn filemap_to_stream(sess: &ParseSess, filemap: Rc<FileMap>, override_span: Option<Span>)
+pub fn filemap_to_stream(sess: &ParseSess, filemap: Lrc<FileMap>, override_span: Option<Span>)
                          -> TokenStream {
     let mut srdr = lexer::StringReader::new(sess, filemap);
     srdr.override_span = override_span;
@@ -422,7 +422,7 @@ pub fn lit_token(lit: token::Lit, suf: Option<Symbol>, diag: Option<(Span, &Hand
             (true, Some(LitKind::ByteStr(byte_str_lit(&i.as_str()))))
         }
         token::ByteStrRaw(i, _) => {
-            (true, Some(LitKind::ByteStr(Rc::new(i.to_string().into_bytes()))))
+            (true, Some(LitKind::ByteStr(Lrc::new(i.to_string().into_bytes()))))
         }
     }
 }
@@ -496,7 +496,7 @@ pub fn byte_lit(lit: &str) -> (u8, usize) {
     }
 }
 
-pub fn byte_str_lit(lit: &str) -> Rc<Vec<u8>> {
+pub fn byte_str_lit(lit: &str) -> Lrc<Vec<u8>> {
     let mut res = Vec::with_capacity(lit.len());
 
     // FIXME #8372: This could be a for-loop if it didn't borrow the iterator
@@ -553,7 +553,7 @@ pub fn byte_str_lit(lit: &str) -> Rc<Vec<u8>> {
         }
     }
 
-    Rc::new(res)
+    Lrc::new(res)
 }
 
 pub fn integer_lit(s: &str, suffix: Option<Symbol>, diag: Option<(Span, &Handler)>)
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index 7fbe781e9a1..097a2eb89fd 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -27,7 +27,7 @@ use tokenstream;
 
 use std::cell::Cell;
 use std::{cmp, fmt};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Debug, Copy)]
 pub enum BinOpToken {
@@ -180,7 +180,7 @@ pub enum Token {
 
     // The `LazyTokenStream` is a pure function of the `Nonterminal`,
     // and so the `LazyTokenStream` can be ignored by Eq, Hash, etc.
-    Interpolated(Rc<(Nonterminal, LazyTokenStream)>),
+    Interpolated(Lrc<(Nonterminal, LazyTokenStream)>),
     // Can be expanded into several tokens.
     /// Doc comment
     DocComment(ast::Name),
@@ -200,7 +200,7 @@ pub enum Token {
 
 impl Token {
     pub fn interpolated(nt: Nonterminal) -> Token {
-        Token::Interpolated(Rc::new((nt, LazyTokenStream::new())))
+        Token::Interpolated(Lrc::new((nt, LazyTokenStream::new())))
     }
 
     /// Returns `true` if the token starts with '>'.
diff --git a/src/libsyntax/test.rs b/src/libsyntax/test.rs
index e732ac3a635..39306229c82 100644
--- a/src/libsyntax/test.rs
+++ b/src/libsyntax/test.rs
@@ -21,7 +21,6 @@ use std::mem;
 use std::vec;
 use attr::{self, HasAttrs};
 use syntax_pos::{self, DUMMY_SP, NO_EXPANSION, Span, FileMap, BytePos};
-use std::rc::Rc;
 
 use codemap::{self, CodeMap, ExpnInfo, NameAndSpan, MacroAttribute, dummy_spanned};
 use errors;
diff --git a/src/libsyntax/test_snippet.rs b/src/libsyntax/test_snippet.rs
index 3b4bba24d77..772334e3ef1 100644
--- a/src/libsyntax/test_snippet.rs
+++ b/src/libsyntax/test_snippet.rs
@@ -13,7 +13,7 @@ use errors::Handler;
 use errors::emitter::EmitterWriter;
 use std::io;
 use std::io::prelude::*;
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use std::str;
 use std::sync::{Arc, Mutex};
 use std::path::Path;
@@ -48,7 +48,7 @@ impl<T: Write> Write for Shared<T> {
 fn test_harness(file_text: &str, span_labels: Vec<SpanLabel>, expected_output: &str) {
     let output = Arc::new(Mutex::new(Vec::new()));
 
-    let code_map = Rc::new(CodeMap::new(FilePathMapping::empty()));
+    let code_map = Lrc::new(CodeMap::new(FilePathMapping::empty()));
     code_map.new_filemap_and_lines(Path::new("test.rs"), &file_text);
 
     let primary_span = make_span(&file_text, &span_labels[0].start, &span_labels[0].end);
diff --git a/src/libsyntax/util/rc_slice.rs b/src/libsyntax/util/rc_slice.rs
index d6939d71129..520b7a48e30 100644
--- a/src/libsyntax/util/rc_slice.rs
+++ b/src/libsyntax/util/rc_slice.rs
@@ -10,14 +10,14 @@
 
 use std::fmt;
 use std::ops::{Deref, Range};
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult,
                                            HashStable};
 
 #[derive(Clone)]
 pub struct RcSlice<T> {
-    data: Rc<Box<[T]>>,
+    data: Lrc<Box<[T]>>,
     offset: u32,
     len: u32,
 }
@@ -27,7 +27,7 @@ impl<T> RcSlice<T> {
         RcSlice {
             offset: 0,
             len: vec.len() as u32,
-            data: Rc::new(vec.into_boxed_slice()),
+            data: Lrc::new(vec.into_boxed_slice()),
         }
     }
 
diff --git a/src/libsyntax_ext/Cargo.toml b/src/libsyntax_ext/Cargo.toml
index 1c470240288..d8eeb5ed255 100644
--- a/src/libsyntax_ext/Cargo.toml
+++ b/src/libsyntax_ext/Cargo.toml
@@ -14,3 +14,4 @@ proc_macro = { path = "../libproc_macro" }
 rustc_errors = { path = "../librustc_errors" }
 syntax = { path = "../libsyntax" }
 syntax_pos = { path = "../libsyntax_pos" }
+rustc_data_structures = { path = "../librustc_data_structures" }
\ No newline at end of file
diff --git a/src/libsyntax_ext/deriving/mod.rs b/src/libsyntax_ext/deriving/mod.rs
index 8159893e784..6bc4ee0b399 100644
--- a/src/libsyntax_ext/deriving/mod.rs
+++ b/src/libsyntax_ext/deriving/mod.rs
@@ -10,7 +10,7 @@
 
 //! The compiler code necessary to implement the `#[derive]` extensions.
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::ast;
 use syntax::ext::base::{Annotatable, ExtCtxt, SyntaxExtension, Resolver};
 use syntax::ext::build::AstBuilder;
@@ -65,7 +65,7 @@ macro_rules! derive_traits {
             $(
                 resolver.add_builtin(
                     ast::Ident::with_empty_ctxt(Symbol::intern($name)),
-                    Rc::new(SyntaxExtension::BuiltinDerive($func))
+                    Lrc::new(SyntaxExtension::BuiltinDerive($func))
                 );
             )*
         }
diff --git a/src/libsyntax_ext/lib.rs b/src/libsyntax_ext/lib.rs
index 82d6ee5afa0..772dec72ab9 100644
--- a/src/libsyntax_ext/lib.rs
+++ b/src/libsyntax_ext/lib.rs
@@ -23,6 +23,7 @@ extern crate fmt_macros;
 extern crate syntax;
 extern crate syntax_pos;
 extern crate proc_macro;
+extern crate rustc_data_structures;
 extern crate rustc_errors as errors;
 
 mod asm;
@@ -44,7 +45,7 @@ pub mod deriving;
 
 pub mod proc_macro_impl;
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 use syntax::ast;
 use syntax::ext::base::{MacroExpanderFn, NormalTT, NamedSyntaxExtension};
 use syntax::symbol::Symbol;
@@ -55,7 +56,7 @@ pub fn register_builtins(resolver: &mut syntax::ext::base::Resolver,
     deriving::register_builtin_derives(resolver);
 
     let mut register = |name, ext| {
-        resolver.add_builtin(ast::Ident::with_empty_ctxt(name), Rc::new(ext));
+        resolver.add_builtin(ast::Ident::with_empty_ctxt(name), Lrc::new(ext));
     };
 
     macro_rules! register {
diff --git a/src/libsyntax_pos/lib.rs b/src/libsyntax_pos/lib.rs
index e2c6b1b0c92..9f746adbe65 100644
--- a/src/libsyntax_pos/lib.rs
+++ b/src/libsyntax_pos/lib.rs
@@ -33,9 +33,9 @@ use std::fmt;
 use std::hash::{Hasher, Hash};
 use std::ops::{Add, Sub};
 use std::path::PathBuf;
-use std::rc::Rc;
 
 use rustc_data_structures::stable_hasher::StableHasher;
+use rustc_data_structures::sync::Lrc;
 
 extern crate rustc_data_structures;
 
@@ -678,7 +678,7 @@ pub struct FileMap {
     /// Indicates which crate this FileMap was imported from.
     pub crate_of_origin: u32,
     /// The complete source code
-    pub src: Option<Rc<String>>,
+    pub src: Option<Lrc<String>>,
     /// The source code's hash
     pub src_hash: u128,
     /// The external source code (used for external crates, which will have a `None`
@@ -864,7 +864,7 @@ impl FileMap {
             name_was_remapped,
             unmapped_path: Some(unmapped_path),
             crate_of_origin: 0,
-            src: Some(Rc::new(src)),
+            src: Some(Lrc::new(src)),
             src_hash,
             external_src: RefCell::new(ExternalSource::Unneeded),
             start_pos,
@@ -1127,7 +1127,7 @@ impl Sub for CharPos {
 #[derive(Debug, Clone)]
 pub struct Loc {
     /// Information about the original source
-    pub file: Rc<FileMap>,
+    pub file: Lrc<FileMap>,
     /// The (1-based) line number
     pub line: usize,
     /// The (0-based) column offset
@@ -1144,14 +1144,14 @@ pub struct LocWithOpt {
     pub filename: FileName,
     pub line: usize,
     pub col: CharPos,
-    pub file: Option<Rc<FileMap>>,
+    pub file: Option<Lrc<FileMap>>,
 }
 
 // used to be structural records. Better names, anyone?
 #[derive(Debug)]
-pub struct FileMapAndLine { pub fm: Rc<FileMap>, pub line: usize }
+pub struct FileMapAndLine { pub fm: Lrc<FileMap>, pub line: usize }
 #[derive(Debug)]
-pub struct FileMapAndBytePos { pub fm: Rc<FileMap>, pub pos: BytePos }
+pub struct FileMapAndBytePos { pub fm: Lrc<FileMap>, pub pos: BytePos }
 
 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 pub struct LineInfo {
@@ -1166,7 +1166,7 @@ pub struct LineInfo {
 }
 
 pub struct FileLines {
-    pub file: Rc<FileMap>,
+    pub file: Lrc<FileMap>,
     pub lines: Vec<LineInfo>
 }
 
diff --git a/src/test/run-pass-fulldeps/issue-35829.rs b/src/test/run-pass-fulldeps/issue-35829.rs
index f17a0494a69..07d4bd2fe15 100644
--- a/src/test/run-pass-fulldeps/issue-35829.rs
+++ b/src/test/run-pass-fulldeps/issue-35829.rs
@@ -13,6 +13,7 @@
 #![feature(quote, rustc_private)]
 
 extern crate syntax;
+extern crate rustc_data_structures;
 
 use syntax::ext::base::{ExtCtxt, DummyResolver};
 use syntax::ext::expand::ExpansionConfig;
@@ -23,7 +24,7 @@ use syntax::ast::{Expr, ExprKind, LitKind, StrStyle, RangeLimits};
 use syntax::symbol::Symbol;
 use syntax::ptr::P;
 
-use std::rc::Rc;
+use rustc_data_structures::sync::Lrc;
 
 fn main() {
     let parse_sess = ParseSess::new(FilePathMapping::empty());
@@ -33,12 +34,12 @@ fn main() {
 
     // check byte string
     let byte_string = quote_expr!(&cx, b"one");
-    let byte_string_lit_kind = LitKind::ByteStr(Rc::new(b"one".to_vec()));
+    let byte_string_lit_kind = LitKind::ByteStr(Lrc::new(b"one".to_vec()));
     assert_eq!(byte_string.node, ExprKind::Lit(P(dummy_spanned(byte_string_lit_kind))));
 
     // check raw byte string
     let raw_byte_string = quote_expr!(&cx, br###"#"two"#"###);
-    let raw_byte_string_lit_kind = LitKind::ByteStr(Rc::new(b"#\"two\"#".to_vec()));
+    let raw_byte_string_lit_kind = LitKind::ByteStr(Lrc::new(b"#\"two\"#".to_vec()));
     assert_eq!(raw_byte_string.node, ExprKind::Lit(P(dummy_spanned(raw_byte_string_lit_kind))));
 
     // check dotdoteq