Auto merge of #59540 - Zoxc:the-arena-2, r=michaelwoerister

Use arenas to avoid Lrc in queries #1

Based on https://github.com/rust-lang/rust/pull/59536.

23 files changed, 107 insertions, 89 deletions

diff --git a/src/librustc/arena.rs b/src/librustc/arena.rs
index e9751a23f12..1cc6500d038 100644
--- a/src/librustc/arena.rs
+++ b/src/librustc/arena.rs
@@ -16,6 +16,48 @@ macro_rules! arena_types {
             )>,
             [few] mir_keys: rustc::util::nodemap::DefIdSet,
             [decode] specialization_graph: rustc::traits::specialization_graph::Graph,
+            [] region_scope_tree: rustc::middle::region::ScopeTree,
+            [] item_local_set: rustc::util::nodemap::ItemLocalSet,
+            [decode] mir_const_qualif: rustc_data_structures::bit_set::BitSet<rustc::mir::Local>,
+            [] trait_impls_of: rustc::ty::trait_def::TraitImpls,
+            [] dropck_outlives:
+                rustc::infer::canonical::Canonical<'tcx,
+                    rustc::infer::canonical::QueryResponse<'tcx,
+                        rustc::traits::query::dropck_outlives::DropckOutlivesResult<'tcx>
+                    >
+                >,
+            [] normalize_projection_ty:
+                rustc::infer::canonical::Canonical<'tcx,
+                    rustc::infer::canonical::QueryResponse<'tcx,
+                        rustc::traits::query::normalize::NormalizationResult<'tcx>
+                    >
+                >,
+            [] implied_outlives_bounds:
+                rustc::infer::canonical::Canonical<'tcx,
+                    rustc::infer::canonical::QueryResponse<'tcx,
+                        Vec<rustc::traits::query::outlives_bounds::OutlivesBound<'tcx>>
+                    >
+                >,
+            [] type_op_subtype:
+                rustc::infer::canonical::Canonical<'tcx,
+                    rustc::infer::canonical::QueryResponse<'tcx, ()>
+                >,
+            [] type_op_normalize_poly_fn_sig:
+                rustc::infer::canonical::Canonical<'tcx,
+                    rustc::infer::canonical::QueryResponse<'tcx, rustc::ty::PolyFnSig<'tcx>>
+                >,
+            [] type_op_normalize_fn_sig:
+                rustc::infer::canonical::Canonical<'tcx,
+                    rustc::infer::canonical::QueryResponse<'tcx, rustc::ty::FnSig<'tcx>>
+                >,
+            [] type_op_normalize_predicate:
+                rustc::infer::canonical::Canonical<'tcx,
+                    rustc::infer::canonical::QueryResponse<'tcx, rustc::ty::Predicate<'tcx>>
+                >,
+            [] type_op_normalize_ty:
+                rustc::infer::canonical::Canonical<'tcx,
+                    rustc::infer::canonical::QueryResponse<'tcx, rustc::ty::Ty<'tcx>>
+                >,
         ], $tcx);
     )
 }
diff --git a/src/librustc/infer/canonical/mod.rs b/src/librustc/infer/canonical/mod.rs
index 39b84fabff6..fe6b8ac1cdc 100644
--- a/src/librustc/infer/canonical/mod.rs
+++ b/src/librustc/infer/canonical/mod.rs
@@ -23,7 +23,6 @@
 
 use crate::infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin};
 use rustc_data_structures::indexed_vec::IndexVec;
-use rustc_data_structures::sync::Lrc;
 use rustc_macros::HashStable;
 use serialize::UseSpecializedDecodable;
 use smallvec::SmallVec;
@@ -186,7 +185,7 @@ pub struct QueryResponse<'tcx, R> {
 pub type Canonicalized<'gcx, V> = Canonical<'gcx, <V as Lift<'gcx>>::Lifted>;
 
 pub type CanonicalizedQueryResponse<'gcx, T> =
-    Lrc<Canonical<'gcx, QueryResponse<'gcx, <T as Lift<'gcx>>::Lifted>>>;
+    &'gcx Canonical<'gcx, QueryResponse<'gcx, <T as Lift<'gcx>>::Lifted>>;
 
 /// Indicates whether or not we were able to prove the query to be
 /// true.
diff --git a/src/librustc/infer/canonical/query_response.rs b/src/librustc/infer/canonical/query_response.rs
index 008882fd500..e605aae0fae 100644
--- a/src/librustc/infer/canonical/query_response.rs
+++ b/src/librustc/infer/canonical/query_response.rs
@@ -7,6 +7,7 @@
 //!
 //! [c]: https://rust-lang.github.io/rustc-guide/traits/canonicalization.html
 
+use crate::arena::ArenaAllocatable;
 use crate::infer::canonical::substitute::substitute_value;
 use crate::infer::canonical::{
     Canonical, CanonicalVarValues, CanonicalizedQueryResponse, Certainty,
@@ -17,7 +18,6 @@ use crate::infer::InferCtxtBuilder;
 use crate::infer::{InferCtxt, InferOk, InferResult};
 use rustc_data_structures::indexed_vec::Idx;
 use rustc_data_structures::indexed_vec::IndexVec;
-use rustc_data_structures::sync::Lrc;
 use std::fmt::Debug;
 use syntax_pos::DUMMY_SP;
 use crate::traits::query::{Fallible, NoSolution};
@@ -54,6 +54,7 @@ impl<'cx, 'gcx, 'tcx> InferCtxtBuilder<'cx, 'gcx, 'tcx> {
     where
         K: TypeFoldable<'tcx>,
         R: Debug + Lift<'gcx> + TypeFoldable<'tcx>,
+        Canonical<'gcx, <QueryResponse<'gcx, R> as Lift<'gcx>>::Lifted>: ArenaAllocatable,
     {
         self.enter_with_canonical(
             DUMMY_SP,
@@ -99,6 +100,7 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
     ) -> Fallible<CanonicalizedQueryResponse<'gcx, T>>
     where
         T: Debug + Lift<'gcx> + TypeFoldable<'tcx>,
+        Canonical<'gcx, <QueryResponse<'gcx, T> as Lift<'gcx>>::Lifted>: ArenaAllocatable,
     {
         let query_response = self.make_query_response(inference_vars, answer, fulfill_cx)?;
         let canonical_result = self.canonicalize_response(&query_response);
@@ -108,7 +110,7 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
             canonical_result
         );
 
-        Ok(Lrc::new(canonical_result))
+        Ok(self.tcx.arena.alloc(canonical_result))
     }
 
     /// A version of `make_canonicalized_query_response` that does
diff --git a/src/librustc/middle/expr_use_visitor.rs b/src/librustc/middle/expr_use_visitor.rs
index 52f105b8c40..6900be55769 100644
--- a/src/librustc/middle/expr_use_visitor.rs
+++ b/src/librustc/middle/expr_use_visitor.rs
@@ -17,7 +17,6 @@ use crate::middle::region;
 use crate::ty::{self, DefIdTree, TyCtxt, adjustment};
 
 use crate::hir::{self, PatKind};
-use rustc_data_structures::sync::Lrc;
 use std::rc::Rc;
 use syntax::ptr::P;
 use syntax_pos::Span;
@@ -272,7 +271,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<Lrc<ItemLocalSet>>)
+               rvalue_promotable_map: Option<&'tcx ItemLocalSet>)
                -> Self
     {
         ExprUseVisitor {
diff --git a/src/librustc/middle/mem_categorization.rs b/src/librustc/middle/mem_categorization.rs
index 25fa19558de..6ca1e0ea84a 100644
--- a/src/librustc/middle/mem_categorization.rs
+++ b/src/librustc/middle/mem_categorization.rs
@@ -77,7 +77,6 @@ use syntax_pos::Span;
 use std::borrow::Cow;
 use std::fmt;
 use std::hash::{Hash, Hasher};
-use rustc_data_structures::sync::Lrc;
 use rustc_data_structures::indexed_vec::Idx;
 use std::rc::Rc;
 use crate::util::nodemap::ItemLocalSet;
@@ -290,7 +289,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<Lrc<ItemLocalSet>>,
+    rvalue_promotable_map: Option<&'tcx ItemLocalSet>,
     infcx: Option<&'a InferCtxt<'a, 'gcx, 'tcx>>,
 }
 
@@ -400,7 +399,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<Lrc<ItemLocalSet>>)
+               rvalue_promotable_map: Option<&'tcx ItemLocalSet>)
                -> MemCategorizationContext<'a, 'tcx, 'tcx> {
         MemCategorizationContext {
             tcx,
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index 9a5af8a2537..f9491a1e8f4 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -12,7 +12,6 @@ use crate::ty;
 
 use std::mem;
 use std::fmt;
-use rustc_data_structures::sync::Lrc;
 use rustc_macros::HashStable;
 use syntax::source_map;
 use syntax::ast;
@@ -1329,7 +1328,7 @@ impl<'a, 'tcx> Visitor<'tcx> for RegionResolutionVisitor<'a, 'tcx> {
 }
 
 fn region_scope_tree<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
-    -> Lrc<ScopeTree>
+    -> &'tcx ScopeTree
 {
     let closure_base_def_id = tcx.closure_base_def_id(def_id);
     if closure_base_def_id != def_id {
@@ -1371,7 +1370,7 @@ fn region_scope_tree<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
         ScopeTree::default()
     };
 
-    Lrc::new(scope_tree)
+    tcx.arena.alloc(scope_tree)
 }
 
 pub fn provide(providers: &mut Providers<'_>) {
diff --git a/src/librustc/query/mod.rs b/src/librustc/query/mod.rs
index 1861420b408..eaf9fd1bc76 100644
--- a/src/librustc/query/mod.rs
+++ b/src/librustc/query/mod.rs
@@ -91,7 +91,7 @@ rustc_queries! {
         /// 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.
-        query mir_const_qualif(key: DefId) -> (u8, Lrc<BitSet<mir::Local>>) {
+        query mir_const_qualif(key: DefId) -> (u8, &'tcx BitSet<mir::Local>) {
             cache { key.is_local() }
         }
 
@@ -174,7 +174,7 @@ rustc_queries! {
 
         /// Returns the inferred outlives predicates (e.g., for `struct
         /// Foo<'a, T> { x: &'a T }`, this would return `T: 'a`).
-        query inferred_outlives_of(_: DefId) -> Lrc<Vec<ty::Predicate<'tcx>>> {}
+        query inferred_outlives_of(_: DefId) -> &'tcx [ty::Predicate<'tcx>] {}
 
         /// Maps from the `DefId` of a trait to the list of
         /// super-predicates. This is a subset of the full list of
@@ -456,7 +456,7 @@ rustc_queries! {
 
         /// Per-body `region::ScopeTree`. The `DefId` should be the owner `DefId` for the body;
         /// in the case of closures, this will be redirected to the enclosing function.
-        query region_scope_tree(_: DefId) -> Lrc<region::ScopeTree> {}
+        query region_scope_tree(_: DefId) -> &'tcx region::ScopeTree {}
 
         query mir_shims(key: ty::InstanceDef<'tcx>) -> &'tcx mir::Mir<'tcx> {
             no_force
@@ -504,7 +504,7 @@ rustc_queries! {
             }
             cache { true }
         }
-        query rvalue_promotable_map(key: DefId) -> Lrc<ItemLocalSet> {
+        query rvalue_promotable_map(key: DefId) -> &'tcx ItemLocalSet {
             desc { |tcx|
                 "checking which parts of `{}` are promotable to static",
                 tcx.def_path_str(key)
@@ -540,7 +540,7 @@ rustc_queries! {
     }
 
     TypeChecking {
-        query trait_impls_of(key: DefId) -> Lrc<ty::trait_def::TraitImpls> {
+        query trait_impls_of(key: DefId) -> &'tcx ty::trait_def::TraitImpls {
             desc { |tcx| "trait impls of `{}`", tcx.def_path_str(key) }
         }
         query specialization_graph_of(_: DefId) -> &'tcx specialization_graph::Graph {}
@@ -892,7 +892,7 @@ rustc_queries! {
         query normalize_projection_ty(
             goal: CanonicalProjectionGoal<'tcx>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, NormalizationResult<'tcx>>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, NormalizationResult<'tcx>>>,
             NoSolution,
         > {
             no_force
@@ -910,7 +910,7 @@ rustc_queries! {
         query implied_outlives_bounds(
             goal: CanonicalTyGoal<'tcx>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>,
             NoSolution,
         > {
             no_force
@@ -921,7 +921,7 @@ rustc_queries! {
         query dropck_outlives(
             goal: CanonicalTyGoal<'tcx>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, DropckOutlivesResult<'tcx>>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, DropckOutlivesResult<'tcx>>>,
             NoSolution,
         > {
             no_force
@@ -940,7 +940,7 @@ rustc_queries! {
         query evaluate_goal(
             goal: traits::ChalkCanonicalGoal<'tcx>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>,
             NoSolution
         > {
             no_force
@@ -951,7 +951,7 @@ rustc_queries! {
         query type_op_ascribe_user_type(
             goal: CanonicalTypeOpAscribeUserTypeGoal<'tcx>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>,
             NoSolution,
         > {
             no_force
@@ -962,7 +962,7 @@ rustc_queries! {
         query type_op_eq(
             goal: CanonicalTypeOpEqGoal<'tcx>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>,
             NoSolution,
         > {
             no_force
@@ -973,7 +973,7 @@ rustc_queries! {
         query type_op_subtype(
             goal: CanonicalTypeOpSubtypeGoal<'tcx>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>,
             NoSolution,
         > {
             no_force
@@ -984,7 +984,7 @@ rustc_queries! {
         query type_op_prove_predicate(
             goal: CanonicalTypeOpProvePredicateGoal<'tcx>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, ()>>,
             NoSolution,
         > {
             no_force
@@ -995,7 +995,7 @@ rustc_queries! {
         query type_op_normalize_ty(
             goal: CanonicalTypeOpNormalizeGoal<'tcx, Ty<'tcx>>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, Ty<'tcx>>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Ty<'tcx>>>,
             NoSolution,
         > {
             no_force
@@ -1006,7 +1006,7 @@ rustc_queries! {
         query type_op_normalize_predicate(
             goal: CanonicalTypeOpNormalizeGoal<'tcx, ty::Predicate<'tcx>>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, ty::Predicate<'tcx>>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, ty::Predicate<'tcx>>>,
             NoSolution,
         > {
             no_force
@@ -1017,7 +1017,7 @@ rustc_queries! {
         query type_op_normalize_poly_fn_sig(
             goal: CanonicalTypeOpNormalizeGoal<'tcx, ty::PolyFnSig<'tcx>>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, ty::PolyFnSig<'tcx>>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, ty::PolyFnSig<'tcx>>>,
             NoSolution,
         > {
             no_force
@@ -1028,7 +1028,7 @@ rustc_queries! {
         query type_op_normalize_fn_sig(
             goal: CanonicalTypeOpNormalizeGoal<'tcx, ty::FnSig<'tcx>>
         ) -> Result<
-            Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, ty::FnSig<'tcx>>>>,
+            &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, ty::FnSig<'tcx>>>,
             NoSolution,
         > {
             no_force
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index f2c77b1bfab..f6bfd90668a 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -1120,11 +1120,7 @@ pub struct CratePredicatesMap<'tcx> {
     /// For each struct with outlive bounds, maps to a vector of the
     /// predicate of its outlive bounds. If an item has no outlives
     /// bounds, it will have no entry.
-    pub predicates: FxHashMap<DefId, Lrc<Vec<ty::Predicate<'tcx>>>>,
-
-    /// An empty vector, useful for cloning.
-    #[stable_hasher(ignore)]
-    pub empty_predicate: Lrc<Vec<ty::Predicate<'tcx>>>,
+    pub predicates: FxHashMap<DefId, &'tcx [ty::Predicate<'tcx>]>,
 }
 
 impl<'tcx> AsRef<Predicate<'tcx>> for Predicate<'tcx> {
diff --git a/src/librustc/ty/trait_def.rs b/src/librustc/ty/trait_def.rs
index 58f21893de1..a0b409bc400 100644
--- a/src/librustc/ty/trait_def.rs
+++ b/src/librustc/ty/trait_def.rs
@@ -10,7 +10,6 @@ use crate::ty::{Ty, TyCtxt};
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
                                            StableHasherResult};
-use rustc_data_structures::sync::Lrc;
 use rustc_macros::HashStable;
 
 /// A trait's definition with type information.
@@ -151,7 +150,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)
-                                                -> Lrc<TraitImpls> {
+                                                -> &'tcx TraitImpls {
     let mut impls = TraitImpls::default();
 
     {
@@ -188,7 +187,7 @@ pub(super) fn trait_impls_of_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         }
     }
 
-    Lrc::new(impls)
+    tcx.arena.alloc(impls)
 }
 
 impl<'a> HashStable<StableHashingContext<'a>> for TraitImpls {
diff --git a/src/librustc_borrowck/borrowck/mod.rs b/src/librustc_borrowck/borrowck/mod.rs
index 540f374bcf9..65a550b1b89 100644
--- a/src/librustc_borrowck/borrowck/mod.rs
+++ b/src/librustc_borrowck/borrowck/mod.rs
@@ -228,7 +228,7 @@ pub struct BorrowckCtxt<'a, 'tcx: 'a> {
     // Some in `borrowck_fn` and cleared later
     tables: &'a ty::TypeckTables<'tcx>,
 
-    region_scope_tree: Lrc<region::ScopeTree>,
+    region_scope_tree: &'tcx region::ScopeTree,
 
     owner_def_id: DefId,
 
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index 1a1b933ccf3..53f06baaa9d 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -131,7 +131,7 @@ provide! { <'tcx> tcx, def_id, other, cdata,
         mir
     }
     mir_const_qualif => {
-        (cdata.mir_const_qualif(def_id.index), Lrc::new(BitSet::new_empty(0)))
+        (cdata.mir_const_qualif(def_id.index), tcx.arena.alloc(BitSet::new_empty(0)))
     }
     fn_sig => { cdata.fn_sig(def_id.index, tcx) }
     inherent_impls => { Lrc::new(cdata.get_inherent_implementations_for_type(def_id.index)) }
diff --git a/src/librustc_mir/borrow_check/error_reporting.rs b/src/librustc_mir/borrow_check/error_reporting.rs
index 12dcea7bd59..54fecb4ad60 100644
--- a/src/librustc_mir/borrow_check/error_reporting.rs
+++ b/src/librustc_mir/borrow_check/error_reporting.rs
@@ -17,7 +17,6 @@ use rustc::ty::layout::VariantIdx;
 use rustc::ty::print::Print;
 use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::indexed_vec::Idx;
-use rustc_data_structures::sync::Lrc;
 use rustc_errors::{Applicability, DiagnosticBuilder};
 use syntax_pos::Span;
 use syntax::source_map::CompilerDesugaringKind;
@@ -811,7 +810,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
         &mut self,
         context: Context,
         name: &str,
-        scope_tree: &Lrc<ScopeTree>,
+        scope_tree: &'tcx ScopeTree,
         borrow: &BorrowData<'tcx>,
         drop_span: Span,
         borrow_spans: UseSpans,
@@ -1000,7 +999,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
     fn report_temporary_value_does_not_live_long_enough(
         &mut self,
         context: Context,
-        scope_tree: &Lrc<ScopeTree>,
+        scope_tree: &'tcx ScopeTree,
         borrow: &BorrowData<'tcx>,
         drop_span: Span,
         borrow_spans: UseSpans,
diff --git a/src/librustc_mir/hair/cx/mod.rs b/src/librustc_mir/hair/cx/mod.rs
index 71c6489d63f..7aed0bace8c 100644
--- a/src/librustc_mir/hair/cx/mod.rs
+++ b/src/librustc_mir/hair/cx/mod.rs
@@ -18,7 +18,6 @@ use syntax::ast;
 use syntax::attr;
 use syntax::symbol::Symbol;
 use rustc::hir;
-use rustc_data_structures::sync::Lrc;
 use crate::hair::constant::{lit_to_const, LitToConstError};
 
 #[derive(Clone)]
@@ -32,7 +31,7 @@ pub struct Cx<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
     /// Identity `InternalSubsts` for use with const-evaluation.
     pub identity_substs: &'gcx InternalSubsts<'gcx>,
 
-    pub region_scope_tree: Lrc<region::ScopeTree>,
+    pub region_scope_tree: &'gcx 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/qualify_consts.rs b/src/librustc_mir/transform/qualify_consts.rs
index bbcdd2c1812..18ad89be3c3 100644
--- a/src/librustc_mir/transform/qualify_consts.rs
+++ b/src/librustc_mir/transform/qualify_consts.rs
@@ -7,7 +7,6 @@
 use rustc_data_structures::bit_set::BitSet;
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_data_structures::fx::FxHashSet;
-use rustc_data_structures::sync::Lrc;
 use rustc_target::spec::abi::Abi;
 use rustc::hir;
 use rustc::hir::def_id::DefId;
@@ -833,7 +832,7 @@ impl<'a, 'tcx> Checker<'a, 'tcx> {
     }
 
     /// Check a whole const, static initializer or const fn.
-    fn check_const(&mut self) -> (u8, Lrc<BitSet<Local>>) {
+    fn check_const(&mut self) -> (u8, &'tcx BitSet<Local>) {
         debug!("const-checking {} {:?}", self.mode, self.def_id);
 
         let mir = self.mir;
@@ -907,8 +906,6 @@ impl<'a, 'tcx> Checker<'a, 'tcx> {
             }
         }
 
-        let promoted_temps = Lrc::new(promoted_temps);
-
         let mut qualifs = self.qualifs_in_local(RETURN_PLACE);
 
         // Account for errors in consts by using the
@@ -917,7 +914,7 @@ impl<'a, 'tcx> Checker<'a, 'tcx> {
             qualifs = self.qualifs_in_any_value_of_ty(mir.return_ty());
         }
 
-        (qualifs.encode_to_bits(), promoted_temps)
+        (qualifs.encode_to_bits(), self.tcx.arena.alloc(promoted_temps))
     }
 }
 
@@ -1433,7 +1430,7 @@ pub fn provide(providers: &mut Providers<'_>) {
 
 fn mir_const_qualif<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                               def_id: DefId)
-                              -> (u8, Lrc<BitSet<Local>>) {
+                              -> (u8, &'tcx BitSet<Local>) {
     // N.B., 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
@@ -1442,7 +1439,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 (1 << IsNotPromotable::IDX, Lrc::new(BitSet::new_empty(0)));
+        return (1 << IsNotPromotable::IDX, tcx.arena.alloc(BitSet::new_empty(0)));
     }
 
     Checker::new(tcx, def_id, mir, Mode::Const).check_const()
diff --git a/src/librustc_passes/rvalue_promotion.rs b/src/librustc_passes/rvalue_promotion.rs
index 2a423cc4166..ce54035fe67 100644
--- a/src/librustc_passes/rvalue_promotion.rs
+++ b/src/librustc_passes/rvalue_promotion.rs
@@ -25,7 +25,6 @@ use rustc::ty::query::Providers;
 use rustc::ty::subst::{InternalSubsts, SubstsRef};
 use rustc::util::nodemap::{ItemLocalSet, HirIdSet};
 use rustc::hir;
-use rustc_data_structures::sync::Lrc;
 use syntax_pos::{Span, DUMMY_SP};
 use log::debug;
 use Promotability::*;
@@ -53,7 +52,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)
-                                   -> Lrc<ItemLocalSet>
+                                   -> &'tcx ItemLocalSet
 {
     let outer_def_id = tcx.closure_base_def_id(def_id);
     if outer_def_id != def_id {
@@ -77,7 +76,7 @@ fn rvalue_promotable_map<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
     let body_id = tcx.hir().body_owned_by(hir_id);
     let _ = visitor.check_nested_body(body_id);
 
-    Lrc::new(visitor.result)
+    tcx.arena.alloc(visitor.result)
 }
 
 struct CheckCrateVisitor<'a, 'tcx: 'a> {
diff --git a/src/librustc_traits/chalk_context/mod.rs b/src/librustc_traits/chalk_context/mod.rs
index 334f510d10d..04cd632b297 100644
--- a/src/librustc_traits/chalk_context/mod.rs
+++ b/src/librustc_traits/chalk_context/mod.rs
@@ -36,7 +36,6 @@ use rustc::ty::{self, TyCtxt, InferConst};
 use rustc::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
 use rustc::ty::query::Providers;
 use rustc::ty::subst::{Kind, UnpackedKind};
-use rustc_data_structures::sync::Lrc;
 use rustc::mir::interpret::ConstValue;
 use syntax_pos::DUMMY_SP;
 
@@ -677,7 +676,7 @@ crate fn evaluate_goal<'a, 'tcx>(
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
     goal: ChalkCanonicalGoal<'tcx>
 ) -> Result<
-    Lrc<Canonical<'tcx, QueryResponse<'tcx, ()>>>,
+    &'tcx Canonical<'tcx, QueryResponse<'tcx, ()>>,
     traits::query::NoSolution
 > {
     use crate::lowering::Lower;
@@ -718,6 +717,6 @@ crate fn evaluate_goal<'a, 'tcx>(
 
     debug!("evaluate_goal: solution = {:?}", solution);
 
-    solution.map(|ok| Ok(Lrc::new(ok)))
-        .unwrap_or(Err(traits::query::NoSolution))
+    solution.map(|ok| Ok(&*tcx.arena.alloc(ok)))
+            .unwrap_or(Err(traits::query::NoSolution))
 }
diff --git a/src/librustc_traits/dropck_outlives.rs b/src/librustc_traits/dropck_outlives.rs
index 49fcb7cd833..737bf6f9e84 100644
--- a/src/librustc_traits/dropck_outlives.rs
+++ b/src/librustc_traits/dropck_outlives.rs
@@ -7,7 +7,6 @@ use rustc::ty::query::Providers;
 use rustc::ty::subst::{Subst, InternalSubsts};
 use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt};
 use rustc::util::nodemap::FxHashSet;
-use rustc_data_structures::sync::Lrc;
 use syntax::source_map::{Span, DUMMY_SP};
 
 crate fn provide(p: &mut Providers<'_>) {
@@ -21,7 +20,7 @@ crate fn provide(p: &mut Providers<'_>) {
 fn dropck_outlives<'tcx>(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     canonical_goal: CanonicalTyGoal<'tcx>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, DropckOutlivesResult<'tcx>>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, DropckOutlivesResult<'tcx>>>, NoSolution> {
     debug!("dropck_outlives(goal={:#?})", canonical_goal);
 
     tcx.infer_ctxt().enter_with_canonical(
diff --git a/src/librustc_traits/implied_outlives_bounds.rs b/src/librustc_traits/implied_outlives_bounds.rs
index dad45130062..b1688a7fbbb 100644
--- a/src/librustc_traits/implied_outlives_bounds.rs
+++ b/src/librustc_traits/implied_outlives_bounds.rs
@@ -15,8 +15,6 @@ use smallvec::{SmallVec, smallvec};
 use syntax::source_map::DUMMY_SP;
 use rustc::traits::FulfillmentContext;
 
-use rustc_data_structures::sync::Lrc;
-
 crate fn provide(p: &mut Providers<'_>) {
     *p = Providers {
         implied_outlives_bounds,
@@ -28,7 +26,7 @@ fn implied_outlives_bounds<'tcx>(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     goal: CanonicalTyGoal<'tcx>,
 ) -> Result<
-        Lrc<Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>>,
+        &'tcx Canonical<'tcx, canonical::QueryResponse<'tcx, Vec<OutlivesBound<'tcx>>>>,
         NoSolution,
 > {
     tcx.infer_ctxt()
diff --git a/src/librustc_traits/normalize_projection_ty.rs b/src/librustc_traits/normalize_projection_ty.rs
index 38f7a21e66c..3ff04bc2853 100644
--- a/src/librustc_traits/normalize_projection_ty.rs
+++ b/src/librustc_traits/normalize_projection_ty.rs
@@ -4,7 +4,6 @@ use rustc::traits::query::{normalize::NormalizationResult, CanonicalProjectionGo
 use rustc::traits::{self, ObligationCause, SelectionContext, TraitEngineExt};
 use rustc::ty::query::Providers;
 use rustc::ty::{ParamEnvAnd, TyCtxt};
-use rustc_data_structures::sync::Lrc;
 use std::sync::atomic::Ordering;
 use syntax_pos::DUMMY_SP;
 
@@ -18,7 +17,7 @@ crate fn provide(p: &mut Providers<'_>) {
 fn normalize_projection_ty<'tcx>(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     goal: CanonicalProjectionGoal<'tcx>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, NormalizationResult<'tcx>>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, NormalizationResult<'tcx>>>, NoSolution> {
     debug!("normalize_provider(goal={:#?})", goal);
 
     tcx.sess
diff --git a/src/librustc_traits/type_op.rs b/src/librustc_traits/type_op.rs
index 30fbdbdeb44..ea37024b84f 100644
--- a/src/librustc_traits/type_op.rs
+++ b/src/librustc_traits/type_op.rs
@@ -17,7 +17,6 @@ use rustc::ty::subst::{Kind, Subst, UserSubsts, UserSelfTy};
 use rustc::ty::{
     FnSig, Lift, ParamEnv, ParamEnvAnd, PolyFnSig, Predicate, Ty, TyCtxt, TypeFoldable, Variance,
 };
-use rustc_data_structures::sync::Lrc;
 use std::fmt;
 use syntax_pos::DUMMY_SP;
 
@@ -38,7 +37,7 @@ crate fn provide(p: &mut Providers<'_>) {
 fn type_op_ascribe_user_type<'tcx>(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, AscribeUserType<'tcx>>>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, ()>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, ()>>, NoSolution> {
     tcx.infer_ctxt()
         .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| {
             let (
@@ -170,7 +169,7 @@ impl AscribeUserTypeCx<'me, 'gcx, 'tcx> {
 fn type_op_eq<'tcx>(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Eq<'tcx>>>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, ()>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, ()>>, NoSolution> {
     tcx.infer_ctxt()
         .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| {
             let (param_env, Eq { a, b }) = key.into_parts();
@@ -200,7 +199,7 @@ where
 fn type_op_normalize_ty(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Ty<'tcx>>>>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>, NoSolution> {
     tcx.infer_ctxt()
         .enter_canonical_trait_query(&canonicalized, type_op_normalize)
 }
@@ -208,7 +207,7 @@ fn type_op_normalize_ty(
 fn type_op_normalize_predicate(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Predicate<'tcx>>>>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, Predicate<'tcx>>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, Predicate<'tcx>>>, NoSolution> {
     tcx.infer_ctxt()
         .enter_canonical_trait_query(&canonicalized, type_op_normalize)
 }
@@ -216,7 +215,7 @@ fn type_op_normalize_predicate(
 fn type_op_normalize_fn_sig(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<FnSig<'tcx>>>>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, FnSig<'tcx>>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, FnSig<'tcx>>>, NoSolution> {
     tcx.infer_ctxt()
         .enter_canonical_trait_query(&canonicalized, type_op_normalize)
 }
@@ -224,7 +223,7 @@ fn type_op_normalize_fn_sig(
 fn type_op_normalize_poly_fn_sig(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<PolyFnSig<'tcx>>>>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, PolyFnSig<'tcx>>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, PolyFnSig<'tcx>>>, NoSolution> {
     tcx.infer_ctxt()
         .enter_canonical_trait_query(&canonicalized, type_op_normalize)
 }
@@ -232,7 +231,7 @@ fn type_op_normalize_poly_fn_sig(
 fn type_op_subtype<'tcx>(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Subtype<'tcx>>>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, ()>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, ()>>, NoSolution> {
     tcx.infer_ctxt()
         .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| {
             let (param_env, Subtype { sub, sup }) = key.into_parts();
@@ -246,7 +245,7 @@ fn type_op_subtype<'tcx>(
 fn type_op_prove_predicate<'tcx>(
     tcx: TyCtxt<'_, 'tcx, 'tcx>,
     canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, ProvePredicate<'tcx>>>,
-) -> Result<Lrc<Canonical<'tcx, QueryResponse<'tcx, ()>>>, NoSolution> {
+) -> Result<&'tcx Canonical<'tcx, QueryResponse<'tcx, ()>>, NoSolution> {
     tcx.infer_ctxt()
         .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| {
             let (param_env, ProvePredicate { predicate }) = key.into_parts();
diff --git a/src/librustc_typeck/check/generator_interior.rs b/src/librustc_typeck/check/generator_interior.rs
index 0866c57616e..08809917ba2 100644
--- a/src/librustc_typeck/check/generator_interior.rs
+++ b/src/librustc_typeck/check/generator_interior.rs
@@ -8,7 +8,6 @@ use rustc::hir::intravisit::{self, Visitor, NestedVisitorMap};
 use rustc::hir::{self, Pat, PatKind, Expr};
 use rustc::middle::region;
 use rustc::ty::{self, Ty};
-use rustc_data_structures::sync::Lrc;
 use syntax_pos::Span;
 use super::FnCtxt;
 use crate::util::nodemap::FxHashMap;
@@ -16,7 +15,7 @@ use crate::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: Lrc<region::ScopeTree>,
+    region_scope_tree: &'gcx region::ScopeTree,
     expr_count: usize,
 }
 
diff --git a/src/librustc_typeck/check/regionck.rs b/src/librustc_typeck/check/regionck.rs
index a03d33a3ef5..353b9ac6cc3 100644
--- a/src/librustc_typeck/check/regionck.rs
+++ b/src/librustc_typeck/check/regionck.rs
@@ -86,7 +86,6 @@ use rustc::ty::{self, Ty};
 
 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
 use rustc::hir::{self, PatKind};
-use rustc_data_structures::sync::Lrc;
 use std::mem;
 use std::ops::Deref;
 use std::rc::Rc;
@@ -195,7 +194,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: Lrc<region::ScopeTree>,
+    pub region_scope_tree: &'gcx region::ScopeTree,
 
     outlives_environment: OutlivesEnvironment<'tcx>,
 
diff --git a/src/librustc_typeck/outlives/mod.rs b/src/librustc_typeck/outlives/mod.rs
index 913990ee878..e3e2fe7106a 100644
--- a/src/librustc_typeck/outlives/mod.rs
+++ b/src/librustc_typeck/outlives/mod.rs
@@ -23,7 +23,7 @@ pub fn provide(providers: &mut Providers<'_>) {
 fn inferred_outlives_of<'a, 'tcx>(
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
     item_def_id: DefId,
-) -> Lrc<Vec<ty::Predicate<'tcx>>> {
+) -> &'tcx [ty::Predicate<'tcx>] {
     let id = tcx
         .hir()
         .as_local_hir_id(item_def_id)
@@ -37,8 +37,8 @@ fn inferred_outlives_of<'a, 'tcx>(
                 let predicates = crate_map
                     .predicates
                     .get(&item_def_id)
-                    .unwrap_or(&crate_map.empty_predicate)
-                    .clone();
+                    .map(|p| *p)
+                    .unwrap_or(&[]);
 
                 if tcx.has_attr(item_def_id, "rustc_outlives") {
                     let mut pred: Vec<String> = predicates
@@ -63,10 +63,10 @@ fn inferred_outlives_of<'a, 'tcx>(
                 predicates
             }
 
-            _ => Lrc::new(Vec::new()),
+            _ => &[],
         },
 
-        _ => Lrc::new(Vec::new()),
+        _ => &[],
     }
 }
 
@@ -96,7 +96,7 @@ fn inferred_outlives_crate<'tcx>(
     let predicates = global_inferred_outlives
         .iter()
         .map(|(&def_id, set)| {
-            let vec: Vec<ty::Predicate<'tcx>> = set
+            let predicates = tcx.arena.alloc_from_iter(set
                 .iter()
                 .filter_map(
                     |ty::OutlivesPredicate(kind1, region2)| match kind1.unpack() {
@@ -115,14 +115,11 @@ fn inferred_outlives_crate<'tcx>(
                             None
                         }
                     },
-                ).collect();
-            (def_id, Lrc::new(vec))
+                ));
+            (def_id, &*predicates)
         }).collect();
 
-    let empty_predicate = Lrc::new(Vec::new());
-
     Lrc::new(ty::CratePredicatesMap {
         predicates,
-        empty_predicate,
     })
 }