Auto merge of #89124 - cjgillot:owner-info, r=michaelwoerister

Index and hash HIR as part of lowering

Part of https://github.com/rust-lang/rust/pull/88186
~Based on https://github.com/rust-lang/rust/pull/88880 (see merge commit).~

Once HIR is lowered, it is later indexed by the `index_hir` query and hashed for `crate_hash`. This PR moves those post-processing steps to lowering itself. As a side objective, the HIR crate data structure is refactored as an `IndexVec<LocalDefId, Option<OwnerInfo<'hir>>>` where `OwnerInfo` stores all the relevant information for an HIR owner.

r? `@michaelwoerister`
cc `@petrochenkov`

28 files changed, 547 insertions, 594 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 102450188aa..6bd09931aec 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3568,6 +3568,7 @@ dependencies = [
  "rustc_errors",
  "rustc_hir",
  "rustc_index",
+ "rustc_query_system",
  "rustc_session",
  "rustc_span",
  "rustc_target",
@@ -4102,6 +4103,7 @@ dependencies = [
  "polonius-engine",
  "rand 0.8.4",
  "rand_xoshiro 0.6.0",
+ "rustc-rayon",
  "rustc-rayon-core",
  "rustc_apfloat",
  "rustc_arena",
@@ -4346,6 +4348,7 @@ dependencies = [
  "rustc_index",
  "rustc_metadata",
  "rustc_middle",
+ "rustc_query_system",
  "rustc_session",
  "rustc_span",
  "smallvec",
diff --git a/compiler/rustc_ast_lowering/Cargo.toml b/compiler/rustc_ast_lowering/Cargo.toml
index f4859ee4ae9..7989af24d99 100644
--- a/compiler/rustc_ast_lowering/Cargo.toml
+++ b/compiler/rustc_ast_lowering/Cargo.toml
@@ -14,6 +14,7 @@ rustc_hir = { path = "../rustc_hir" }
 rustc_target = { path = "../rustc_target" }
 rustc_data_structures = { path = "../rustc_data_structures" }
 rustc_index = { path = "../rustc_index" }
+rustc_query_system = { path = "../rustc_query_system" }
 rustc_span = { path = "../rustc_span" }
 rustc_errors = { path = "../rustc_errors" }
 rustc_session = { path = "../rustc_session" }
diff --git a/compiler/rustc_ast_lowering/src/expr.rs b/compiler/rustc_ast_lowering/src/expr.rs
index 6027027428e..22f93f50788 100644
--- a/compiler/rustc_ast_lowering/src/expr.rs
+++ b/compiler/rustc_ast_lowering/src/expr.rs
@@ -252,9 +252,10 @@ impl<'hir> LoweringContext<'_, 'hir> {
                     }
                     // Merge attributes into the inner expression.
                     if !e.attrs.is_empty() {
-                        let old_attrs = self.attrs.get(&ex.hir_id).map(|la| *la).unwrap_or(&[]);
+                        let old_attrs =
+                            self.attrs.get(&ex.hir_id.local_id).map(|la| *la).unwrap_or(&[]);
                         self.attrs.insert(
-                            ex.hir_id,
+                            ex.hir_id.local_id,
                             &*self.arena.alloc_from_iter(
                                 e.attrs
                                     .iter()
diff --git a/compiler/rustc_middle/src/hir/map/collector.rs b/compiler/rustc_ast_lowering/src/index.rs
index efebf73224f..dc2b1a730fb 100644
--- a/compiler/rustc_middle/src/hir/map/collector.rs
+++ b/compiler/rustc_ast_lowering/src/index.rs
@@ -1,44 +1,33 @@
-use crate::arena::Arena;
-use crate::hir::map::Map;
-use crate::hir::{IndexedHir, OwnerNodes, ParentedNode};
-use rustc_data_structures::fingerprint::Fingerprint;
 use rustc_data_structures::fx::FxHashMap;
-use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_hir as hir;
 use rustc_hir::def_id::LocalDefId;
-use rustc_hir::def_id::CRATE_DEF_ID;
 use rustc_hir::definitions;
 use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
 use rustc_hir::*;
 use rustc_index::vec::{Idx, IndexVec};
-use rustc_query_system::ich::StableHashingContext;
 use rustc_session::Session;
 use rustc_span::source_map::SourceMap;
 use rustc_span::{Span, DUMMY_SP};
 
 use std::iter::repeat;
+use tracing::debug;
 
 /// A visitor that walks over the HIR and collects `Node`s into a HIR map.
 pub(super) struct NodeCollector<'a, 'hir> {
-    arena: &'hir Arena<'hir>,
-
-    /// The crate
-    krate: &'hir Crate<'hir>,
-
     /// Source map
     source_map: &'a SourceMap,
+    bodies: &'a IndexVec<ItemLocalId, Option<&'hir Body<'hir>>>,
 
-    map: IndexVec<LocalDefId, Option<&'hir mut OwnerNodes<'hir>>>,
-    parenting: FxHashMap<LocalDefId, HirId>,
+    /// Outputs
+    nodes: IndexVec<ItemLocalId, Option<ParentedNode<'hir>>>,
+    parenting: FxHashMap<LocalDefId, ItemLocalId>,
 
     /// The parent of this node
-    parent_node: hir::HirId,
+    parent_node: hir::ItemLocalId,
 
-    current_dep_node_owner: LocalDefId,
+    owner: LocalDefId,
 
     definitions: &'a definitions::Definitions,
-
-    hcx: StableHashingContext<'a>,
 }
 
 fn insert_vec_map<K: Idx, V: Clone>(map: &mut IndexVec<K, Option<V>>, k: K, v: V) {
@@ -51,137 +40,82 @@ fn insert_vec_map<K: Idx, V: Clone>(map: &mut IndexVec<K, Option<V>>, k: K, v: V
     map[k] = Some(v);
 }
 
-fn hash_body(
-    hcx: &mut StableHashingContext<'_>,
-    item_like: impl for<'a> HashStable<StableHashingContext<'a>>,
-) -> Fingerprint {
-    let mut stable_hasher = StableHasher::new();
-    hcx.while_hashing_hir_bodies(true, |hcx| {
-        item_like.hash_stable(hcx, &mut stable_hasher);
-    });
-    stable_hasher.finish()
+pub(super) fn index_hir<'hir>(
+    sess: &Session,
+    definitions: &definitions::Definitions,
+    item: hir::OwnerNode<'hir>,
+    bodies: &IndexVec<ItemLocalId, Option<&'hir Body<'hir>>>,
+) -> (IndexVec<ItemLocalId, Option<ParentedNode<'hir>>>, FxHashMap<LocalDefId, ItemLocalId>) {
+    let mut nodes = IndexVec::new();
+    // This node's parent should never be accessed: the owner's parent is computed by the
+    // hir_owner_parent query.  Make it invalid (= ItemLocalId::MAX) to force an ICE whenever it is
+    // used.
+    nodes.push(Some(ParentedNode { parent: ItemLocalId::INVALID, node: item.into() }));
+    let mut collector = NodeCollector {
+        source_map: sess.source_map(),
+        definitions,
+        owner: item.def_id(),
+        parent_node: ItemLocalId::new(0),
+        nodes,
+        bodies,
+        parenting: FxHashMap::default(),
+    };
+
+    match item {
+        OwnerNode::Crate(citem) => collector.visit_mod(&citem, citem.inner, hir::CRATE_HIR_ID),
+        OwnerNode::Item(item) => collector.visit_item(item),
+        OwnerNode::TraitItem(item) => collector.visit_trait_item(item),
+        OwnerNode::ImplItem(item) => collector.visit_impl_item(item),
+        OwnerNode::ForeignItem(item) => collector.visit_foreign_item(item),
+    };
+
+    (collector.nodes, collector.parenting)
 }
 
 impl<'a, 'hir> NodeCollector<'a, 'hir> {
-    pub(super) fn root(
-        sess: &'a Session,
-        arena: &'hir Arena<'hir>,
-        krate: &'hir Crate<'hir>,
-        definitions: &'a definitions::Definitions,
-        hcx: StableHashingContext<'a>,
-    ) -> NodeCollector<'a, 'hir> {
-        let mut collector = NodeCollector {
-            arena,
-            krate,
-            source_map: sess.source_map(),
-            parent_node: hir::CRATE_HIR_ID,
-            current_dep_node_owner: CRATE_DEF_ID,
-            definitions,
-            hcx,
-            map: IndexVec::from_fn_n(|_| None, definitions.def_index_count()),
-            parenting: FxHashMap::default(),
-        };
-        collector.insert_owner(CRATE_DEF_ID, OwnerNode::Crate(krate.module()));
-
-        collector
-    }
-
-    pub(super) fn finalize_and_compute_crate_hash(mut self) -> IndexedHir<'hir> {
-        // Insert bodies into the map
-        for (id, body) in self.krate.bodies.iter() {
-            let bodies = &mut self.map[id.hir_id.owner].as_mut().unwrap().bodies;
-            assert!(bodies.insert(id.hir_id.local_id, body).is_none());
-        }
-        IndexedHir { map: self.map, parenting: self.parenting }
-    }
-
-    fn insert_owner(&mut self, owner: LocalDefId, node: OwnerNode<'hir>) {
-        let hash = hash_body(&mut self.hcx, node);
-
-        let mut nodes = IndexVec::new();
-        nodes.push(Some(ParentedNode { parent: ItemLocalId::new(0), node: node.into() }));
-
-        debug_assert!(self.map[owner].is_none());
-        self.map[owner] =
-            Some(self.arena.alloc(OwnerNodes { hash, nodes, bodies: FxHashMap::default() }));
-    }
-
     fn insert(&mut self, span: Span, hir_id: HirId, node: Node<'hir>) {
-        debug_assert_eq!(self.current_dep_node_owner, hir_id.owner);
+        debug_assert_eq!(self.owner, hir_id.owner);
         debug_assert_ne!(hir_id.local_id.as_u32(), 0);
 
         // Make sure that the DepNode of some node coincides with the HirId
         // owner of that node.
         if cfg!(debug_assertions) {
-            if hir_id.owner != self.current_dep_node_owner {
-                let node_str = match self.definitions.opt_hir_id_to_local_def_id(hir_id) {
-                    Some(def_id) => self.definitions.def_path(def_id).to_string_no_crate_verbose(),
-                    None => format!("{:?}", node),
-                };
-
-                span_bug!(
-                    span,
-                    "inconsistent DepNode at `{:?}` for `{}`: \
+            if hir_id.owner != self.owner {
+                panic!(
+                    "inconsistent DepNode at `{:?}` for `{:?}`: \
                      current_dep_node_owner={} ({:?}), hir_id.owner={} ({:?})",
                     self.source_map.span_to_diagnostic_string(span),
-                    node_str,
-                    self.definitions
-                        .def_path(self.current_dep_node_owner)
-                        .to_string_no_crate_verbose(),
-                    self.current_dep_node_owner,
+                    node,
+                    self.definitions.def_path(self.owner).to_string_no_crate_verbose(),
+                    self.owner,
                     self.definitions.def_path(hir_id.owner).to_string_no_crate_verbose(),
                     hir_id.owner,
                 )
             }
         }
 
-        let nodes = self.map[hir_id.owner].as_mut().unwrap();
-
-        debug_assert_eq!(self.parent_node.owner, self.current_dep_node_owner);
         insert_vec_map(
-            &mut nodes.nodes,
+            &mut self.nodes,
             hir_id.local_id,
-            ParentedNode { parent: self.parent_node.local_id, node: node },
+            ParentedNode { parent: self.parent_node, node: node },
         );
     }
 
     fn with_parent<F: FnOnce(&mut Self)>(&mut self, parent_node_id: HirId, f: F) {
+        debug_assert_eq!(parent_node_id.owner, self.owner);
         let parent_node = self.parent_node;
-        self.parent_node = parent_node_id;
+        self.parent_node = parent_node_id.local_id;
         f(self);
         self.parent_node = parent_node;
     }
 
-    fn with_dep_node_owner(&mut self, dep_node_owner: LocalDefId, f: impl FnOnce(&mut Self)) {
-        let prev_owner = self.current_dep_node_owner;
-        let prev_parent = self.parent_node;
-
-        self.current_dep_node_owner = dep_node_owner;
-        self.parent_node = HirId::make_owner(dep_node_owner);
-        f(self);
-        self.current_dep_node_owner = prev_owner;
-        self.parent_node = prev_parent;
-    }
-
     fn insert_nested(&mut self, item: LocalDefId) {
-        #[cfg(debug_assertions)]
-        {
-            let dk_parent = self.definitions.def_key(item).parent.unwrap();
-            let dk_parent = LocalDefId { local_def_index: dk_parent };
-            let dk_parent = self.definitions.local_def_id_to_hir_id(dk_parent);
-            debug_assert_eq!(
-                dk_parent.owner, self.parent_node.owner,
-                "Different parents for {:?}",
-                item
-            )
-        }
-
-        assert_eq!(self.parenting.insert(item, self.parent_node), None);
+        self.parenting.insert(item, self.parent_node);
     }
 }
 
 impl<'a, 'hir> Visitor<'hir> for NodeCollector<'a, 'hir> {
-    type Map = Map<'hir>;
+    type Map = !;
 
     /// Because we want to track parent items and so forth, enable
     /// deep walking so that we walk nested items in the context of
@@ -194,26 +128,24 @@ impl<'a, 'hir> Visitor<'hir> for NodeCollector<'a, 'hir> {
     fn visit_nested_item(&mut self, item: ItemId) {
         debug!("visit_nested_item: {:?}", item);
         self.insert_nested(item.def_id);
-        self.visit_item(self.krate.item(item));
     }
 
     fn visit_nested_trait_item(&mut self, item_id: TraitItemId) {
         self.insert_nested(item_id.def_id);
-        self.visit_trait_item(self.krate.trait_item(item_id));
     }
 
     fn visit_nested_impl_item(&mut self, item_id: ImplItemId) {
         self.insert_nested(item_id.def_id);
-        self.visit_impl_item(self.krate.impl_item(item_id));
     }
 
     fn visit_nested_foreign_item(&mut self, foreign_id: ForeignItemId) {
         self.insert_nested(foreign_id.def_id);
-        self.visit_foreign_item(self.krate.foreign_item(foreign_id));
     }
 
     fn visit_nested_body(&mut self, id: BodyId) {
-        self.visit_body(self.krate.body(id));
+        debug_assert_eq!(id.hir_id.owner, self.owner);
+        let body = self.bodies[id.hir_id.local_id].unwrap();
+        self.visit_body(body);
     }
 
     fn visit_param(&mut self, param: &'hir Param<'hir>) {
@@ -226,8 +158,8 @@ impl<'a, 'hir> Visitor<'hir> for NodeCollector<'a, 'hir> {
 
     fn visit_item(&mut self, i: &'hir Item<'hir>) {
         debug!("visit_item: {:?}", i);
-        self.insert_owner(i.def_id, OwnerNode::Item(i));
-        self.with_dep_node_owner(i.def_id, |this| {
+        debug_assert_eq!(i.def_id, self.owner);
+        self.with_parent(i.hir_id(), |this| {
             if let ItemKind::Struct(ref struct_def, _) = i.kind {
                 // If this is a tuple or unit-like struct, register the constructor.
                 if let Some(ctor_hir_id) = struct_def.ctor_hir_id() {
@@ -239,8 +171,8 @@ impl<'a, 'hir> Visitor<'hir> for NodeCollector<'a, 'hir> {
     }
 
     fn visit_foreign_item(&mut self, fi: &'hir ForeignItem<'hir>) {
-        self.insert_owner(fi.def_id, OwnerNode::ForeignItem(fi));
-        self.with_dep_node_owner(fi.def_id, |this| {
+        debug_assert_eq!(fi.def_id, self.owner);
+        self.with_parent(fi.hir_id(), |this| {
             intravisit::walk_foreign_item(this, fi);
         });
     }
@@ -257,15 +189,15 @@ impl<'a, 'hir> Visitor<'hir> for NodeCollector<'a, 'hir> {
     }
 
     fn visit_trait_item(&mut self, ti: &'hir TraitItem<'hir>) {
-        self.insert_owner(ti.def_id, OwnerNode::TraitItem(ti));
-        self.with_dep_node_owner(ti.def_id, |this| {
+        debug_assert_eq!(ti.def_id, self.owner);
+        self.with_parent(ti.hir_id(), |this| {
             intravisit::walk_trait_item(this, ti);
         });
     }
 
     fn visit_impl_item(&mut self, ii: &'hir ImplItem<'hir>) {
-        self.insert_owner(ii.def_id, OwnerNode::ImplItem(ii));
-        self.with_dep_node_owner(ii.def_id, |this| {
+        debug_assert_eq!(ii.def_id, self.owner);
+        self.with_parent(ii.hir_id(), |this| {
             intravisit::walk_impl_item(this, ii);
         });
     }
@@ -353,7 +285,8 @@ impl<'a, 'hir> Visitor<'hir> for NodeCollector<'a, 'hir> {
         s: Span,
         id: HirId,
     ) {
-        assert_eq!(self.parent_node, id);
+        assert_eq!(self.owner, id.owner);
+        assert_eq!(self.parent_node, id.local_id);
         intravisit::walk_fn(self, fk, fd, b, s, id);
     }
 
diff --git a/compiler/rustc_ast_lowering/src/item.rs b/compiler/rustc_ast_lowering/src/item.rs
index a5a4de81f12..e8747f2c5f8 100644
--- a/compiler/rustc_ast_lowering/src/item.rs
+++ b/compiler/rustc_ast_lowering/src/item.rs
@@ -10,6 +10,7 @@ use rustc_errors::struct_span_err;
 use rustc_hir as hir;
 use rustc_hir::def::{DefKind, Res};
 use rustc_hir::def_id::LocalDefId;
+use rustc_index::vec::Idx;
 use rustc_span::source_map::{respan, DesugaringKind};
 use rustc_span::symbol::{kw, sym, Ident};
 use rustc_span::Span;
@@ -99,11 +100,12 @@ impl<'hir> LoweringContext<'_, 'hir> {
     ) -> T {
         let old_len = self.in_scope_lifetimes.len();
 
-        let parent_generics = match self.owners[parent_hir_id].unwrap().expect_item().kind {
-            hir::ItemKind::Impl(hir::Impl { ref generics, .. })
-            | hir::ItemKind::Trait(_, _, ref generics, ..) => generics.params,
-            _ => &[],
-        };
+        let parent_generics =
+            match self.owners[parent_hir_id].as_ref().unwrap().node().expect_item().kind {
+                hir::ItemKind::Impl(hir::Impl { ref generics, .. })
+                | hir::ItemKind::Trait(_, _, ref generics, ..) => generics.params,
+                _ => &[],
+            };
         let lt_def_names = parent_generics.iter().filter_map(|param| match param.kind {
             hir::GenericParamKind::Lifetime { .. } => Some(param.name.normalize_to_macros_2_0()),
             _ => None,
@@ -493,7 +495,7 @@ impl<'hir> LoweringContext<'_, 'hir> {
                         let kind = hir::ItemKind::Use(path, hir::UseKind::Single);
                         let vis = this.rebuild_vis(&vis);
                         if let Some(attrs) = attrs {
-                            this.attrs.insert(hir::HirId::make_owner(new_id), attrs);
+                            this.attrs.insert(hir::ItemLocalId::new(0), attrs);
                         }
 
                         let item = hir::Item {
@@ -568,7 +570,7 @@ impl<'hir> LoweringContext<'_, 'hir> {
                         let kind =
                             this.lower_use_tree(use_tree, &prefix, id, &mut vis, &mut ident, attrs);
                         if let Some(attrs) = attrs {
-                            this.attrs.insert(hir::HirId::make_owner(new_hir_id), attrs);
+                            this.attrs.insert(hir::ItemLocalId::new(0), attrs);
                         }
 
                         let item = hir::Item {
@@ -971,7 +973,9 @@ impl<'hir> LoweringContext<'_, 'hir> {
     ) -> hir::BodyId {
         let body = hir::Body { generator_kind: self.generator_kind, params, value };
         let id = body.id();
-        self.bodies.insert(id, body);
+        debug_assert_eq!(id.hir_id.owner, self.current_hir_id_owner);
+        self.bodies.ensure_contains_elem(id.hir_id.local_id, || None);
+        self.bodies[id.hir_id.local_id] = Some(self.arena.alloc(body));
         id
     }
 
@@ -1124,7 +1128,7 @@ impl<'hir> LoweringContext<'_, 'hir> {
                 //
                 // If this is the simple case, this parameter will end up being the same as the
                 // original parameter, but with a different pattern id.
-                let stmt_attrs = this.attrs.get(&parameter.hir_id).copied();
+                let stmt_attrs = this.attrs.get(&parameter.hir_id.local_id).copied();
                 let (new_parameter_pat, new_parameter_id) = this.pat_ident(desugared_span, ident);
                 let new_parameter = hir::Param {
                     hir_id: parameter.hir_id,
diff --git a/compiler/rustc_ast_lowering/src/lib.rs b/compiler/rustc_ast_lowering/src/lib.rs
index 92b482e90ee..92e08da7a97 100644
--- a/compiler/rustc_ast_lowering/src/lib.rs
+++ b/compiler/rustc_ast_lowering/src/lib.rs
@@ -33,16 +33,18 @@
 #![feature(crate_visibility_modifier)]
 #![feature(box_patterns)]
 #![feature(iter_zip)]
+#![feature(never_type)]
 #![recursion_limit = "256"]
 
-use rustc_ast::node_id::NodeMap;
 use rustc_ast::token::{self, Token};
 use rustc_ast::tokenstream::{CanSynthesizeMissingTokens, TokenStream, TokenTree};
 use rustc_ast::visit;
 use rustc_ast::{self as ast, *};
 use rustc_ast_pretty::pprust;
 use rustc_data_structures::captures::Captures;
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::fingerprint::Fingerprint;
+use rustc_data_structures::fx::FxHashSet;
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::sync::Lrc;
 use rustc_errors::{struct_span_err, Applicability};
 use rustc_hir as hir;
@@ -52,13 +54,14 @@ use rustc_hir::definitions::{DefKey, DefPathData, Definitions};
 use rustc_hir::intravisit;
 use rustc_hir::{ConstArg, GenericArg, InferKind, ParamName};
 use rustc_index::vec::{Idx, IndexVec};
+use rustc_query_system::ich::StableHashingContext;
 use rustc_session::lint::builtin::BARE_TRAIT_OBJECTS;
 use rustc_session::lint::{BuiltinLintDiagnostics, LintBuffer};
 use rustc_session::utils::{FlattenNonterminals, NtToTokenstream};
 use rustc_session::Session;
 use rustc_span::edition::Edition;
 use rustc_span::hygiene::ExpnId;
-use rustc_span::source_map::{respan, CachingSourceMapView, DesugaringKind};
+use rustc_span::source_map::{respan, DesugaringKind};
 use rustc_span::symbol::{kw, sym, Ident, Symbol};
 use rustc_span::{Span, DUMMY_SP};
 
@@ -76,6 +79,7 @@ macro_rules! arena_vec {
 mod asm;
 mod block;
 mod expr;
+mod index;
 mod item;
 mod pat;
 mod path;
@@ -97,13 +101,14 @@ struct LoweringContext<'a, 'hir: 'a> {
     arena: &'hir Arena<'hir>,
 
     /// The items being lowered are collected here.
-    owners: IndexVec<LocalDefId, Option<hir::OwnerNode<'hir>>>,
-    bodies: BTreeMap<hir::BodyId, hir::Body<'hir>>,
+    owners: IndexVec<LocalDefId, Option<hir::OwnerInfo<'hir>>>,
+    /// Bodies inside the owner being lowered.
+    bodies: IndexVec<hir::ItemLocalId, Option<&'hir hir::Body<'hir>>>,
+    /// Attributes inside the owner being lowered.
+    attrs: BTreeMap<hir::ItemLocalId, &'hir [Attribute]>,
 
     generator_kind: Option<hir::GeneratorKind>,
 
-    attrs: BTreeMap<hir::HirId, &'hir [Attribute]>,
-
     /// When inside an `async` context, this is the `HirId` of the
     /// `task_context` local bound to the resume argument of the generator.
     task_context: Option<hir::HirId>,
@@ -152,6 +157,9 @@ struct LoweringContext<'a, 'hir: 'a> {
     item_local_id_counter: hir::ItemLocalId,
     node_id_to_hir_id: IndexVec<NodeId, Option<hir::HirId>>,
 
+    /// NodeIds that are lowered inside the current HIR owner.
+    local_node_ids: Vec<NodeId>,
+
     allow_try_trait: Option<Lrc<[Symbol]>>,
     allow_gen_future: Option<Lrc<[Symbol]>>,
 }
@@ -178,11 +186,13 @@ pub trait ResolverAstLowering {
     /// This should only return `None` during testing.
     fn definitions(&mut self) -> &mut Definitions;
 
+    fn create_stable_hashing_context(&self) -> StableHashingContext<'_>;
+
     fn lint_buffer(&mut self) -> &mut LintBuffer;
 
     fn next_node_id(&mut self) -> NodeId;
 
-    fn take_trait_map(&mut self) -> NodeMap<Vec<hir::TraitCandidate>>;
+    fn take_trait_map(&mut self, node: NodeId) -> Option<Vec<hir::TraitCandidate>>;
 
     fn opt_local_def_id(&self, node: NodeId) -> Option<LocalDefId>;
 
@@ -200,37 +210,6 @@ pub trait ResolverAstLowering {
     ) -> LocalDefId;
 }
 
-struct LoweringHasher<'a> {
-    source_map: CachingSourceMapView<'a>,
-    resolver: &'a dyn ResolverAstLowering,
-}
-
-impl<'a> rustc_span::HashStableContext for LoweringHasher<'a> {
-    #[inline]
-    fn hash_spans(&self) -> bool {
-        true
-    }
-
-    #[inline]
-    fn def_span(&self, id: LocalDefId) -> Span {
-        self.resolver.def_span(id)
-    }
-
-    #[inline]
-    fn def_path_hash(&self, def_id: DefId) -> DefPathHash {
-        self.resolver.def_path_hash(def_id)
-    }
-
-    #[inline]
-    fn span_data_to_lines_and_cols(
-        &mut self,
-        span: &rustc_span::SpanData,
-    ) -> Option<(Lrc<rustc_span::SourceFile>, usize, rustc_span::BytePos, usize, rustc_span::BytePos)>
-    {
-        self.source_map.span_data_to_lines_and_cols(span)
-    }
-}
-
 /// Context of `impl Trait` in code, which determines whether it is allowed in an HIR subtree,
 /// and if so, what meaning it has.
 #[derive(Debug)]
@@ -314,13 +293,14 @@ pub fn lower_crate<'a, 'hir>(
 ) -> &'hir hir::Crate<'hir> {
     let _prof_timer = sess.prof.verbose_generic_activity("hir_lowering");
 
+    let owners = IndexVec::from_fn_n(|_| None, resolver.definitions().def_index_count());
     LoweringContext {
         sess,
         resolver,
         nt_to_tokenstream,
         arena,
-        owners: IndexVec::default(),
-        bodies: BTreeMap::new(),
+        owners,
+        bodies: IndexVec::new(),
         attrs: BTreeMap::default(),
         catch_scope: None,
         loop_scope: None,
@@ -331,6 +311,7 @@ pub fn lower_crate<'a, 'hir>(
         current_hir_id_owner: CRATE_DEF_ID,
         item_local_id_counter: hir::ItemLocalId::new(0),
         node_id_to_hir_id: IndexVec::new(),
+        local_node_ids: Vec::new(),
         generator_kind: None,
         task_context: None,
         current_item: None,
@@ -420,13 +401,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
             hir::OwnerNode::Crate(lctx.arena.alloc(module))
         });
 
-        let mut trait_map: FxHashMap<_, FxHashMap<_, _>> = FxHashMap::default();
-        for (k, v) in self.resolver.take_trait_map().into_iter() {
-            if let Some(Some(hir_id)) = self.node_id_to_hir_id.get(k) {
-                let map = trait_map.entry(hir_id.owner).or_default();
-                map.insert(hir_id.local_id, v.into_boxed_slice());
-            }
-        }
+        let hir_hash = self.compute_hir_hash();
 
         let mut def_id_to_hir_id = IndexVec::default();
 
@@ -441,24 +416,29 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
 
         self.resolver.definitions().init_def_id_to_hir_id_mapping(def_id_to_hir_id);
 
-        #[cfg(debug_assertions)]
-        for (&id, attrs) in self.attrs.iter() {
-            // Verify that we do not store empty slices in the map.
-            if attrs.is_empty() {
-                panic!("Stored empty attributes for {:?}", id);
-            }
-        }
-
-        let krate =
-            hir::Crate { owners: self.owners, bodies: self.bodies, trait_map, attrs: self.attrs };
+        let krate = hir::Crate { owners: self.owners, hir_hash };
         self.arena.alloc(krate)
     }
 
-    fn create_stable_hashing_context(&self) -> LoweringHasher<'_> {
-        LoweringHasher {
-            source_map: CachingSourceMapView::new(self.sess.source_map()),
-            resolver: self.resolver,
-        }
+    /// Compute the hash for the HIR of the full crate.
+    /// This hash will then be part of the crate_hash which is stored in the metadata.
+    fn compute_hir_hash(&mut self) -> Fingerprint {
+        let definitions = self.resolver.definitions();
+        let mut hir_body_nodes: Vec<_> = self
+            .owners
+            .iter_enumerated()
+            .filter_map(|(def_id, info)| {
+                let info = info.as_ref()?;
+                let def_path_hash = definitions.def_path_hash(def_id);
+                Some((def_path_hash, info))
+            })
+            .collect();
+        hir_body_nodes.sort_unstable_by_key(|bn| bn.0);
+
+        let mut stable_hasher = StableHasher::new();
+        let mut hcx = self.resolver.create_stable_hashing_context();
+        hir_body_nodes.hash_stable(&mut hcx, &mut stable_hasher);
+        stable_hasher.finish()
     }
 
     fn with_hir_id_owner(
@@ -468,25 +448,91 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
     ) -> LocalDefId {
         let def_id = self.resolver.local_def_id(owner);
 
-        // Always allocate the first `HirId` for the owner itself.
-        let _old = self.node_id_to_hir_id.insert(owner, hir::HirId::make_owner(def_id));
-        debug_assert_eq!(_old, None);
-
+        let current_attrs = std::mem::take(&mut self.attrs);
+        let current_bodies = std::mem::take(&mut self.bodies);
+        let current_node_ids = std::mem::take(&mut self.local_node_ids);
         let current_owner = std::mem::replace(&mut self.current_hir_id_owner, def_id);
         let current_local_counter =
             std::mem::replace(&mut self.item_local_id_counter, hir::ItemLocalId::new(1));
 
+        // Always allocate the first `HirId` for the owner itself.
+        let _old = self.node_id_to_hir_id.insert(owner, hir::HirId::make_owner(def_id));
+        debug_assert_eq!(_old, None);
+        self.local_node_ids.push(owner);
+
         let item = f(self);
+        debug_assert_eq!(def_id, item.def_id());
+        let info = self.make_owner_info(item);
 
+        self.attrs = current_attrs;
+        self.bodies = current_bodies;
+        self.local_node_ids = current_node_ids;
         self.current_hir_id_owner = current_owner;
         self.item_local_id_counter = current_local_counter;
 
-        let _old = self.owners.insert(def_id, item);
+        let _old = self.owners.insert(def_id, info);
         debug_assert!(_old.is_none());
 
         def_id
     }
 
+    fn make_owner_info(&mut self, node: hir::OwnerNode<'hir>) -> hir::OwnerInfo<'hir> {
+        let attrs = std::mem::take(&mut self.attrs);
+        let bodies = std::mem::take(&mut self.bodies);
+        let local_node_ids = std::mem::take(&mut self.local_node_ids);
+        let trait_map = local_node_ids
+            .into_iter()
+            .filter_map(|node_id| {
+                let hir_id = self.node_id_to_hir_id[node_id]?;
+                let traits = self.resolver.take_trait_map(node_id)?;
+                Some((hir_id.local_id, traits.into_boxed_slice()))
+            })
+            .collect();
+
+        #[cfg(debug_assertions)]
+        for (&id, attrs) in attrs.iter() {
+            // Verify that we do not store empty slices in the map.
+            if attrs.is_empty() {
+                panic!("Stored empty attributes for {:?}", id);
+            }
+        }
+
+        let (hash_including_bodies, hash_without_bodies) = self.hash_owner(node, &bodies);
+        let (nodes, parenting) =
+            index::index_hir(self.sess, self.resolver.definitions(), node, &bodies);
+        let nodes = hir::OwnerNodes { hash_including_bodies, hash_without_bodies, nodes, bodies };
+        let attrs = {
+            let mut hcx = self.resolver.create_stable_hashing_context();
+            let mut stable_hasher = StableHasher::new();
+            attrs.hash_stable(&mut hcx, &mut stable_hasher);
+            let hash = stable_hasher.finish();
+            hir::AttributeMap { map: attrs, hash }
+        };
+
+        hir::OwnerInfo { nodes, parenting, attrs, trait_map }
+    }
+
+    /// Hash the HIR node twice, one deep and one shallow hash.  This allows to differentiate
+    /// queries which depend on the full HIR tree and those which only depend on the item signature.
+    fn hash_owner(
+        &mut self,
+        node: hir::OwnerNode<'hir>,
+        bodies: &IndexVec<hir::ItemLocalId, Option<&'hir hir::Body<'hir>>>,
+    ) -> (Fingerprint, Fingerprint) {
+        let mut hcx = self.resolver.create_stable_hashing_context();
+        let mut stable_hasher = StableHasher::new();
+        hcx.with_hir_bodies(true, node.def_id(), bodies, |hcx| {
+            node.hash_stable(hcx, &mut stable_hasher)
+        });
+        let hash_including_bodies = stable_hasher.finish();
+        let mut stable_hasher = StableHasher::new();
+        hcx.with_hir_bodies(false, node.def_id(), bodies, |hcx| {
+            node.hash_stable(hcx, &mut stable_hasher)
+        });
+        let hash_without_bodies = stable_hasher.finish();
+        (hash_including_bodies, hash_without_bodies)
+    }
+
     /// This method allocates a new `HirId` for the given `NodeId` and stores it in
     /// the `LoweringContext`'s `NodeId => HirId` map.
     /// Take care not to call this method if the resulting `HirId` is then not
@@ -501,6 +547,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
             let owner = self.current_hir_id_owner;
             let local_id = self.item_local_id_counter;
             self.item_local_id_counter.increment_by(1);
+            self.local_node_ids.push(ast_node_id);
             hir::HirId { owner, local_id }
         })
     }
@@ -547,7 +594,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
             allow_internal_unstable,
             reason,
             self.sess.edition(),
-            self.create_stable_hashing_context(),
+            self.resolver.create_stable_hashing_context(),
         )
     }
 
@@ -791,9 +838,10 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
         if attrs.is_empty() {
             None
         } else {
+            debug_assert_eq!(id.owner, self.current_hir_id_owner);
             let ret = self.arena.alloc_from_iter(attrs.iter().map(|a| self.lower_attr(a)));
             debug_assert!(!ret.is_empty());
-            self.attrs.insert(id, ret);
+            self.attrs.insert(id.local_id, ret);
             Some(ret)
         }
     }
@@ -819,9 +867,11 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
     }
 
     fn alias_attrs(&mut self, id: hir::HirId, target_id: hir::HirId) {
-        if let Some(&a) = self.attrs.get(&target_id) {
+        debug_assert_eq!(id.owner, self.current_hir_id_owner);
+        debug_assert_eq!(target_id.owner, self.current_hir_id_owner);
+        if let Some(&a) = self.attrs.get(&target_id.local_id) {
             debug_assert!(!a.is_empty());
-            self.attrs.insert(id, a);
+            self.attrs.insert(id.local_id, a);
         }
     }
 
@@ -2066,7 +2116,7 @@ impl<'a, 'hir> LoweringContext<'a, 'hir> {
         let hir_id = self.next_id();
         if let Some(a) = attrs {
             debug_assert!(!a.is_empty());
-            self.attrs.insert(hir_id, a);
+            self.attrs.insert(hir_id.local_id, a);
         }
         let local = hir::Local { hir_id, init, pat, source, span: self.lower_span(span), ty: None };
         self.stmt(span, hir::StmtKind::Local(self.arena.alloc(local)))
diff --git a/compiler/rustc_driver/src/pretty.rs b/compiler/rustc_driver/src/pretty.rs
index 8e8bea9525d..2e9050dd672 100644
--- a/compiler/rustc_driver/src/pretty.rs
+++ b/compiler/rustc_driver/src/pretty.rs
@@ -59,23 +59,23 @@ where
 }
 fn call_with_pp_support_hir<A, F>(ppmode: &PpHirMode, tcx: TyCtxt<'_>, f: F) -> A
 where
-    F: FnOnce(&dyn HirPrinterSupport<'_>, &hir::Crate<'_>) -> A,
+    F: FnOnce(&dyn HirPrinterSupport<'_>, hir_map::Map<'_>) -> A,
 {
     match *ppmode {
         PpHirMode::Normal => {
             let annotation = NoAnn { sess: tcx.sess, tcx: Some(tcx) };
-            f(&annotation, tcx.hir().krate())
+            f(&annotation, tcx.hir())
         }
 
         PpHirMode::Identified => {
             let annotation = IdentifiedAnnotation { sess: tcx.sess, tcx: Some(tcx) };
-            f(&annotation, tcx.hir().krate())
+            f(&annotation, tcx.hir())
         }
         PpHirMode::Typed => {
             abort_on_err(tcx.analysis(()), tcx.sess);
 
             let annotation = TypedAnnotation { tcx, maybe_typeck_results: Cell::new(None) };
-            tcx.dep_graph.with_ignore(|| f(&annotation, tcx.hir().krate()))
+            tcx.dep_graph.with_ignore(|| f(&annotation, tcx.hir()))
         }
     }
 }
@@ -443,17 +443,27 @@ pub fn print_after_hir_lowering<'tcx>(
             format!("{:#?}", krate)
         }
 
-        Hir(s) => call_with_pp_support_hir(&s, tcx, move |annotation, krate| {
+        Hir(s) => call_with_pp_support_hir(&s, tcx, move |annotation, hir_map| {
             debug!("pretty printing HIR {:?}", s);
             let sess = annotation.sess();
             let sm = sess.source_map();
-            pprust_hir::print_crate(sm, krate, src_name, src, annotation.pp_ann())
+            let attrs = |id| hir_map.attrs(id);
+            pprust_hir::print_crate(
+                sm,
+                hir_map.root_module(),
+                src_name,
+                src,
+                &attrs,
+                annotation.pp_ann(),
+            )
         }),
 
-        HirTree => call_with_pp_support_hir(&PpHirMode::Normal, tcx, move |_annotation, krate| {
-            debug!("pretty printing HIR tree");
-            format!("{:#?}", krate)
-        }),
+        HirTree => {
+            call_with_pp_support_hir(&PpHirMode::Normal, tcx, move |_annotation, hir_map| {
+                debug!("pretty printing HIR tree");
+                format!("{:#?}", hir_map.krate())
+            })
+        }
 
         _ => unreachable!(),
     };
diff --git a/compiler/rustc_hir/src/arena.rs b/compiler/rustc_hir/src/arena.rs
index f07e52e04da..1a34dd04428 100644
--- a/compiler/rustc_hir/src/arena.rs
+++ b/compiler/rustc_hir/src/arena.rs
@@ -19,6 +19,7 @@ macro_rules! arena_types {
             [] attribute: rustc_ast::Attribute,
             [] block: rustc_hir::Block<$tcx>,
             [] bare_fn_ty: rustc_hir::BareFnTy<$tcx>,
+            [] body: rustc_hir::Body<$tcx>,
             [] generic_arg: rustc_hir::GenericArg<$tcx>,
             [] generic_args: rustc_hir::GenericArgs<$tcx>,
             [] generic_bound: rustc_hir::GenericBound<$tcx>,
@@ -36,6 +37,7 @@ macro_rules! arena_types {
             [few] llvm_inline_asm: rustc_hir::LlvmInlineAsm<$tcx>,
             [] local: rustc_hir::Local<$tcx>,
             [few] mod_: rustc_hir::Mod<$tcx>,
+            [] owner_info: rustc_hir::OwnerInfo<$tcx>,
             [] param: rustc_hir::Param<$tcx>,
             [] pat: rustc_hir::Pat<$tcx>,
             [] path: rustc_hir::Path<$tcx>,
diff --git a/compiler/rustc_hir/src/hir.rs b/compiler/rustc_hir/src/hir.rs
index f0ee21645f3..b5c1e31c258 100644
--- a/compiler/rustc_hir/src/hir.rs
+++ b/compiler/rustc_hir/src/hir.rs
@@ -1,5 +1,5 @@
 use crate::def::{CtorKind, DefKind, Res};
-use crate::def_id::{DefId, CRATE_DEF_ID};
+use crate::def_id::DefId;
 crate use crate::hir_id::{HirId, ItemLocalId};
 use crate::LangItem;
 
@@ -9,6 +9,7 @@ use rustc_ast::{Attribute, FloatTy, IntTy, Label, LitKind, StrStyle, TraitObject
 pub use rustc_ast::{BorrowKind, ImplPolarity, IsAuto};
 pub use rustc_ast::{CaptureBy, Movability, Mutability};
 use rustc_ast::{InlineAsmOptions, InlineAsmTemplatePiece};
+use rustc_data_structures::fingerprint::Fingerprint;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_index::vec::IndexVec;
 use rustc_macros::HashStable_Generic;
@@ -662,49 +663,84 @@ pub struct WhereEqPredicate<'hir> {
     pub rhs_ty: &'hir Ty<'hir>,
 }
 
-/// The top-level data structure that stores the entire contents of
-/// the crate currently being compiled.
+/// HIR node coupled with its parent's id in the same HIR owner.
 ///
-/// For more details, see the [rustc dev guide].
-///
-/// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/hir.html
-#[derive(Debug)]
-pub struct Crate<'hir> {
-    pub owners: IndexVec<LocalDefId, Option<OwnerNode<'hir>>>,
-    pub bodies: BTreeMap<BodyId, Body<'hir>>,
-
-    /// Map indicating what traits are in scope for places where this
-    /// is relevant; generated by resolve.
-    pub trait_map: FxHashMap<LocalDefId, FxHashMap<ItemLocalId, Box<[TraitCandidate]>>>,
-
-    /// Collected attributes from HIR nodes.
-    pub attrs: BTreeMap<HirId, &'hir [Attribute]>,
+/// The parent is trash when the node is a HIR owner.
+#[derive(Clone, Debug)]
+pub struct ParentedNode<'tcx> {
+    pub parent: ItemLocalId,
+    pub node: Node<'tcx>,
 }
 
-impl Crate<'hir> {
-    pub fn module(&self) -> &'hir Mod<'hir> {
-        if let Some(OwnerNode::Crate(m)) = self.owners[CRATE_DEF_ID] { m } else { panic!() }
-    }
+/// Attributes owned by a HIR owner.
+#[derive(Debug)]
+pub struct AttributeMap<'tcx> {
+    pub map: BTreeMap<ItemLocalId, &'tcx [Attribute]>,
+    pub hash: Fingerprint,
+}
 
-    pub fn item(&self, id: ItemId) -> &'hir Item<'hir> {
-        self.owners[id.def_id].as_ref().unwrap().expect_item()
-    }
+impl<'tcx> AttributeMap<'tcx> {
+    pub const EMPTY: &'static AttributeMap<'static> =
+        &AttributeMap { map: BTreeMap::new(), hash: Fingerprint::ZERO };
 
-    pub fn trait_item(&self, id: TraitItemId) -> &'hir TraitItem<'hir> {
-        self.owners[id.def_id].as_ref().unwrap().expect_trait_item()
+    #[inline]
+    pub fn get(&self, id: ItemLocalId) -> &'tcx [Attribute] {
+        self.map.get(&id).copied().unwrap_or(&[])
     }
+}
 
-    pub fn impl_item(&self, id: ImplItemId) -> &'hir ImplItem<'hir> {
-        self.owners[id.def_id].as_ref().unwrap().expect_impl_item()
-    }
+/// Map of all HIR nodes inside the current owner.
+/// These nodes are mapped by `ItemLocalId` alongside the index of their parent node.
+/// The HIR tree, including bodies, is pre-hashed.
+#[derive(Debug)]
+pub struct OwnerNodes<'tcx> {
+    /// Pre-computed hash of the full HIR.
+    pub hash_including_bodies: Fingerprint,
+    /// Pre-computed hash of the item signature, sithout recursing into the body.
+    pub hash_without_bodies: Fingerprint,
+    /// Full HIR for the current owner.
+    // The zeroth node's parent should never be accessed: the owner's parent is computed by the
+    // hir_owner_parent query.  It is set to `ItemLocalId::INVALID` to force an ICE if accidentally
+    // used.
+    pub nodes: IndexVec<ItemLocalId, Option<ParentedNode<'tcx>>>,
+    /// Content of local bodies.
+    pub bodies: IndexVec<ItemLocalId, Option<&'tcx Body<'tcx>>>,
+}
+
+/// Full information resulting from lowering an AST node.
+#[derive(Debug, HashStable_Generic)]
+pub struct OwnerInfo<'hir> {
+    /// Contents of the HIR.
+    pub nodes: OwnerNodes<'hir>,
+    /// Map from each nested owner to its parent's local id.
+    pub parenting: FxHashMap<LocalDefId, ItemLocalId>,
+    /// Collected attributes of the HIR nodes.
+    pub attrs: AttributeMap<'hir>,
+    /// Map indicating what traits are in scope for places where this
+    /// is relevant; generated by resolve.
+    pub trait_map: FxHashMap<ItemLocalId, Box<[TraitCandidate]>>,
+}
 
-    pub fn foreign_item(&self, id: ForeignItemId) -> &'hir ForeignItem<'hir> {
-        self.owners[id.def_id].as_ref().unwrap().expect_foreign_item()
+impl<'tcx> OwnerInfo<'tcx> {
+    #[inline]
+    pub fn node(&self) -> OwnerNode<'tcx> {
+        use rustc_index::vec::Idx;
+        let node = self.nodes.nodes[ItemLocalId::new(0)].as_ref().unwrap().node;
+        let node = node.as_owner().unwrap(); // Indexing must ensure it is an OwnerNode.
+        node
     }
+}
 
-    pub fn body(&self, id: BodyId) -> &Body<'hir> {
-        &self.bodies[&id]
-    }
+/// The top-level data structure that stores the entire contents of
+/// the crate currently being compiled.
+///
+/// For more details, see the [rustc dev guide].
+///
+/// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/hir.html
+#[derive(Debug)]
+pub struct Crate<'hir> {
+    pub owners: IndexVec<LocalDefId, Option<OwnerInfo<'hir>>>,
+    pub hir_hash: Fingerprint,
 }
 
 /// A block of statements `{ .. }`, which may have a label (in this case the
diff --git a/compiler/rustc_hir/src/hir_id.rs b/compiler/rustc_hir/src/hir_id.rs
index 0b25ebc27bd..877871f7c3d 100644
--- a/compiler/rustc_hir/src/hir_id.rs
+++ b/compiler/rustc_hir/src/hir_id.rs
@@ -56,6 +56,10 @@ rustc_index::newtype_index! {
     pub struct ItemLocalId { .. }
 }
 rustc_data_structures::impl_stable_hash_via_hash!(ItemLocalId);
+impl ItemLocalId {
+    /// Signal local id which should never be used.
+    pub const INVALID: ItemLocalId = ItemLocalId::MAX;
+}
 
 /// The `HirId` corresponding to `CRATE_NODE_ID` and `CRATE_DEF_INDEX`.
 pub const CRATE_HIR_ID: HirId = HirId {
diff --git a/compiler/rustc_hir/src/intravisit.rs b/compiler/rustc_hir/src/intravisit.rs
index 1ac2625dd47..3e58af1f167 100644
--- a/compiler/rustc_hir/src/intravisit.rs
+++ b/compiler/rustc_hir/src/intravisit.rs
@@ -130,6 +130,28 @@ pub trait Map<'hir> {
     fn foreign_item(&self, id: ForeignItemId) -> &'hir ForeignItem<'hir>;
 }
 
+// Used when no map is actually available, forcing manual implementation of nested visitors.
+impl Map<'hir> for ! {
+    fn find(&self, _: HirId) -> Option<Node<'hir>> {
+        unreachable!()
+    }
+    fn body(&self, _: BodyId) -> &'hir Body<'hir> {
+        unreachable!()
+    }
+    fn item(&self, _: ItemId) -> &'hir Item<'hir> {
+        unreachable!()
+    }
+    fn trait_item(&self, _: TraitItemId) -> &'hir TraitItem<'hir> {
+        unreachable!()
+    }
+    fn impl_item(&self, _: ImplItemId) -> &'hir ImplItem<'hir> {
+        unreachable!()
+    }
+    fn foreign_item(&self, _: ForeignItemId) -> &'hir ForeignItem<'hir> {
+        unreachable!()
+    }
+}
+
 /// An erased version of `Map<'hir>`, using dynamic dispatch.
 /// NOTE: This type is effectively only usable with `NestedVisitorMap::None`.
 pub struct ErasedMap<'hir>(&'hir dyn Map<'hir>);
diff --git a/compiler/rustc_hir/src/lib.rs b/compiler/rustc_hir/src/lib.rs
index f5ea044e248..93224d388c0 100644
--- a/compiler/rustc_hir/src/lib.rs
+++ b/compiler/rustc_hir/src/lib.rs
@@ -2,10 +2,12 @@
 //!
 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/hir.html
 
+#![feature(const_btree_new)]
 #![feature(crate_visibility_modifier)]
 #![feature(in_band_lifetimes)]
 #![feature(once_cell)]
 #![feature(min_specialization)]
+#![feature(never_type)]
 #![recursion_limit = "256"]
 
 #[macro_use]
diff --git a/compiler/rustc_hir/src/stable_hash_impls.rs b/compiler/rustc_hir/src/stable_hash_impls.rs
index 9d5ef279dd7..6e7b765a0c4 100644
--- a/compiler/rustc_hir/src/stable_hash_impls.rs
+++ b/compiler/rustc_hir/src/stable_hash_impls.rs
@@ -1,8 +1,8 @@
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey};
 
 use crate::hir::{
-    BodyId, Expr, ForeignItem, ForeignItemId, ImplItem, ImplItemId, Item, ItemId, Mod, TraitItem,
-    TraitItemId, Ty, VisibilityKind,
+    AttributeMap, BodyId, Crate, Expr, ForeignItem, ForeignItemId, ImplItem, ImplItemId, Item,
+    ItemId, Mod, OwnerNodes, TraitCandidate, TraitItem, TraitItemId, Ty, VisibilityKind,
 };
 use crate::hir_id::{HirId, ItemLocalId};
 use rustc_span::def_id::DefPathHash;
@@ -21,6 +21,7 @@ pub trait HashStableContext:
     fn hash_hir_ty(&mut self, _: &Ty<'_>, hasher: &mut StableHasher);
     fn hash_hir_visibility_kind(&mut self, _: &VisibilityKind<'_>, hasher: &mut StableHasher);
     fn hash_hir_item_like<F: FnOnce(&mut Self)>(&mut self, f: F);
+    fn hash_hir_trait_candidate(&mut self, _: &TraitCandidate, hasher: &mut StableHasher);
 }
 
 impl<HirCtx: crate::HashStableContext> ToStableHashKey<HirCtx> for HirId {
@@ -209,3 +210,35 @@ impl<HirCtx: crate::HashStableContext> HashStable<HirCtx> for Item<'_> {
         });
     }
 }
+
+impl<HirCtx: crate::HashStableContext> HashStable<HirCtx> for OwnerNodes<'tcx> {
+    fn hash_stable(&self, hcx: &mut HirCtx, hasher: &mut StableHasher) {
+        // We ignore the `nodes` and `bodies` fields since these refer to information included in
+        // `hash` which is hashed in the collector and used for the crate hash.
+        let OwnerNodes { hash_including_bodies, hash_without_bodies: _, nodes: _, bodies: _ } =
+            *self;
+        hash_including_bodies.hash_stable(hcx, hasher);
+    }
+}
+
+impl<HirCtx: crate::HashStableContext> HashStable<HirCtx> for AttributeMap<'tcx> {
+    fn hash_stable(&self, hcx: &mut HirCtx, hasher: &mut StableHasher) {
+        // We ignore the `map` since it refers to information included in `hash` which is hashed in
+        // the collector and used for the crate hash.
+        let AttributeMap { hash, map: _ } = *self;
+        hash.hash_stable(hcx, hasher);
+    }
+}
+
+impl<HirCtx: crate::HashStableContext> HashStable<HirCtx> for Crate<'_> {
+    fn hash_stable(&self, hcx: &mut HirCtx, hasher: &mut StableHasher) {
+        let Crate { owners: _, hir_hash } = self;
+        hir_hash.hash_stable(hcx, hasher)
+    }
+}
+
+impl<HirCtx: crate::HashStableContext> HashStable<HirCtx> for TraitCandidate {
+    fn hash_stable(&self, hcx: &mut HirCtx, hasher: &mut StableHasher) {
+        hcx.hash_hir_trait_candidate(self, hasher)
+    }
+}
diff --git a/compiler/rustc_hir_pretty/src/lib.rs b/compiler/rustc_hir_pretty/src/lib.rs
index 532f1582970..9c2927111a6 100644
--- a/compiler/rustc_hir_pretty/src/lib.rs
+++ b/compiler/rustc_hir_pretty/src/lib.rs
@@ -15,7 +15,6 @@ use rustc_target::spec::abi::Abi;
 
 use std::borrow::Cow;
 use std::cell::Cell;
-use std::collections::BTreeMap;
 use std::vec;
 
 pub fn id_to_string(map: &dyn rustc_hir::intravisit::Map<'_>, hir_id: hir::HirId) -> String {
@@ -69,7 +68,7 @@ impl PpAnn for &dyn rustc_hir::intravisit::Map<'_> {
 pub struct State<'a> {
     pub s: pp::Printer,
     comments: Option<Comments<'a>>,
-    attrs: &'a BTreeMap<hir::HirId, &'a [ast::Attribute]>,
+    attrs: &'a dyn Fn(hir::HirId) -> &'a [ast::Attribute],
     ann: &'a (dyn PpAnn + 'a),
 }
 
@@ -146,17 +145,18 @@ pub const INDENT_UNIT: usize = 4;
 /// it can scan the input text for comments to copy forward.
 pub fn print_crate<'a>(
     sm: &'a SourceMap,
-    krate: &hir::Crate<'_>,
+    krate: &hir::Mod<'_>,
     filename: FileName,
     input: String,
+    attrs: &'a dyn Fn(hir::HirId) -> &'a [ast::Attribute],
     ann: &'a dyn PpAnn,
 ) -> String {
-    let mut s = State::new_from_input(sm, filename, input, &krate.attrs, ann);
+    let mut s = State::new_from_input(sm, filename, input, attrs, ann);
 
     // When printing the AST, we sometimes need to inject `#[no_std]` here.
     // Since you can't compile the HIR, it's not necessary.
 
-    s.print_mod(&krate.module(), s.attrs(hir::CRATE_HIR_ID));
+    s.print_mod(krate, (*attrs)(hir::CRATE_HIR_ID));
     s.print_remaining_comments();
     s.s.eof()
 }
@@ -166,7 +166,7 @@ impl<'a> State<'a> {
         sm: &'a SourceMap,
         filename: FileName,
         input: String,
-        attrs: &'a BTreeMap<hir::HirId, &[ast::Attribute]>,
+        attrs: &'a dyn Fn(hir::HirId) -> &'a [ast::Attribute],
         ann: &'a dyn PpAnn,
     ) -> State<'a> {
         State {
@@ -178,7 +178,7 @@ impl<'a> State<'a> {
     }
 
     fn attrs(&self, id: hir::HirId) -> &'a [ast::Attribute] {
-        self.attrs.get(&id).map_or(&[], |la| *la)
+        (self.attrs)(id)
     }
 }
 
@@ -186,8 +186,7 @@ pub fn to_string<F>(ann: &dyn PpAnn, f: F) -> String
 where
     F: FnOnce(&mut State<'_>),
 {
-    let mut printer =
-        State { s: pp::mk_printer(), comments: None, attrs: &BTreeMap::default(), ann };
+    let mut printer = State { s: pp::mk_printer(), comments: None, attrs: &|_| &[], ann };
     f(&mut printer);
     printer.s.eof()
 }
diff --git a/compiler/rustc_middle/Cargo.toml b/compiler/rustc_middle/Cargo.toml
index d06c593d394..daeccde6024 100644
--- a/compiler/rustc_middle/Cargo.toml
+++ b/compiler/rustc_middle/Cargo.toml
@@ -12,6 +12,7 @@ bitflags = "1.2.1"
 either = "1.5.0"
 gsgdt = "0.1.2"
 tracing = "0.1"
+rustc-rayon = "0.3.1"
 rustc-rayon-core = "0.3.1"
 polonius-engine = "0.13.0"
 rustc_apfloat = { path = "../rustc_apfloat" }
diff --git a/compiler/rustc_middle/src/arena.rs b/compiler/rustc_middle/src/arena.rs
index 962aea448b8..4a027cb7ebe 100644
--- a/compiler/rustc_middle/src/arena.rs
+++ b/compiler/rustc_middle/src/arena.rs
@@ -92,12 +92,6 @@ macro_rules! arena_types {
             [] tys: rustc_middle::ty::TyS<$tcx>,
             [] predicates: rustc_middle::ty::PredicateInner<$tcx>,
 
-            // HIR query types
-            [few] indexed_hir: rustc_middle::hir::IndexedHir<$tcx>,
-            [few] hir_definitions: rustc_hir::definitions::Definitions,
-            [] hir_owner: rustc_middle::hir::Owner<$tcx>,
-            [] hir_owner_nodes: rustc_middle::hir::OwnerNodes<$tcx>,
-
             // Note that this deliberately duplicates items in the `rustc_hir::arena`,
             // since we need to allocate this type on both the `rustc_hir` arena
             // (during lowering) and the `librustc_middle` arena (for decoding MIR)
diff --git a/compiler/rustc_middle/src/hir/map/mod.rs b/compiler/rustc_middle/src/hir/map/mod.rs
index c30ab4c957a..38bc01b9b53 100644
--- a/compiler/rustc_middle/src/hir/map/mod.rs
+++ b/compiler/rustc_middle/src/hir/map/mod.rs
@@ -1,6 +1,4 @@
-use self::collector::NodeCollector;
-
-use crate::hir::{AttributeMap, IndexedHir, ModuleItems, Owner};
+use crate::hir::{ModuleItems, Owner};
 use crate::ty::TyCtxt;
 use rustc_ast as ast;
 use rustc_data_structures::fingerprint::Fingerprint;
@@ -23,7 +21,6 @@ use rustc_target::spec::abi::Abi;
 use std::collections::VecDeque;
 
 pub mod blocks;
-mod collector;
 
 fn fn_decl<'hir>(node: Node<'hir>) -> Option<&'hir FnDecl<'hir>> {
     match node {
@@ -166,8 +163,8 @@ impl<'hir> Map<'hir> {
 
     pub fn items(&self) -> impl Iterator<Item = &'hir Item<'hir>> + 'hir {
         let krate = self.krate();
-        krate.owners.iter().filter_map(|owner| match owner.as_ref()? {
-            OwnerNode::Item(item) => Some(*item),
+        krate.owners.iter().filter_map(|owner| match owner.as_ref()?.node() {
+            OwnerNode::Item(item) => Some(item),
             _ => None,
         })
     }
@@ -318,7 +315,7 @@ impl<'hir> Map<'hir> {
     }
 
     pub fn get_parent_node(&self, hir_id: HirId) -> HirId {
-        self.find_parent_node(hir_id).unwrap_or(CRATE_HIR_ID)
+        self.find_parent_node(hir_id).unwrap()
     }
 
     /// Retrieves the `Node` corresponding to `id`, returning `None` if cannot be found.
@@ -381,7 +378,7 @@ impl<'hir> Map<'hir> {
     }
 
     pub fn body(&self, id: BodyId) -> &'hir Body<'hir> {
-        self.tcx.hir_owner_nodes(id.hir_id.owner).unwrap().bodies.get(&id.hir_id.local_id).unwrap()
+        self.tcx.hir_owner_nodes(id.hir_id.owner).unwrap().bodies[id.hir_id.local_id].unwrap()
     }
 
     pub fn fn_decl_by_hir_id(&self, hir_id: HirId) -> Option<&'hir FnDecl<'hir>> {
@@ -495,11 +492,41 @@ impl<'hir> Map<'hir> {
     /// crate. If you would prefer to iterate over the bodies
     /// themselves, you can do `self.hir().krate().body_ids.iter()`.
     pub fn body_owners(self) -> impl Iterator<Item = LocalDefId> + 'hir {
-        self.krate().bodies.keys().map(move |&body_id| self.body_owner_def_id(body_id))
+        self.krate()
+            .owners
+            .iter_enumerated()
+            .flat_map(move |(owner, owner_info)| {
+                let bodies = &owner_info.as_ref()?.nodes.bodies;
+                Some(bodies.iter_enumerated().filter_map(move |(local_id, body)| {
+                    if body.is_none() {
+                        return None;
+                    }
+                    let hir_id = HirId { owner, local_id };
+                    let body_id = BodyId { hir_id };
+                    Some(self.body_owner_def_id(body_id))
+                }))
+            })
+            .flatten()
     }
 
     pub fn par_body_owners<F: Fn(LocalDefId) + Sync + Send>(self, f: F) {
-        par_for_each_in(&self.krate().bodies, |(&body_id, _)| f(self.body_owner_def_id(body_id)));
+        use rustc_data_structures::sync::{par_iter, ParallelIterator};
+        #[cfg(parallel_compiler)]
+        use rustc_rayon::iter::IndexedParallelIterator;
+
+        par_iter(&self.krate().owners.raw).enumerate().for_each(|(owner, owner_info)| {
+            let owner = LocalDefId::new(owner);
+            if let Some(owner_info) = owner_info {
+                par_iter(&owner_info.nodes.bodies.raw).enumerate().for_each(|(local_id, body)| {
+                    if body.is_some() {
+                        let local_id = ItemLocalId::new(local_id);
+                        let hir_id = HirId { owner, local_id };
+                        let body_id = BodyId { hir_id };
+                        f(self.body_owner_def_id(body_id))
+                    }
+                })
+            }
+        });
     }
 
     pub fn ty_param_owner(&self, id: HirId) -> HirId {
@@ -551,9 +578,14 @@ impl<'hir> Map<'hir> {
     /// Walks the attributes in a crate.
     pub fn walk_attributes(self, visitor: &mut impl Visitor<'hir>) {
         let krate = self.krate();
-        for (&id, attrs) in krate.attrs.iter() {
-            for a in *attrs {
-                visitor.visit_attribute(id, a)
+        for (owner, info) in krate.owners.iter_enumerated() {
+            if let Some(info) = info {
+                for (&local_id, attrs) in info.attrs.map.iter() {
+                    let id = HirId { owner, local_id };
+                    for a in *attrs {
+                        visitor.visit_attribute(id, a)
+                    }
+                }
             }
         }
     }
@@ -572,7 +604,7 @@ impl<'hir> Map<'hir> {
     {
         let krate = self.krate();
         for owner in krate.owners.iter().filter_map(Option::as_ref) {
-            match owner {
+            match owner.node() {
                 OwnerNode::Item(item) => visitor.visit_item(item),
                 OwnerNode::ForeignItem(item) => visitor.visit_foreign_item(item),
                 OwnerNode::ImplItem(item) => visitor.visit_impl_item(item),
@@ -588,7 +620,7 @@ impl<'hir> Map<'hir> {
         V: itemlikevisit::ParItemLikeVisitor<'hir> + Sync + Send,
     {
         let krate = self.krate();
-        par_for_each_in(&krate.owners.raw, |owner| match owner.as_ref() {
+        par_for_each_in(&krate.owners.raw, |owner| match owner.as_ref().map(OwnerInfo::node) {
             Some(OwnerNode::Item(item)) => visitor.visit_item(item),
             Some(OwnerNode::ForeignItem(item)) => visitor.visit_foreign_item(item),
             Some(OwnerNode::ImplItem(item)) => visitor.visit_impl_item(item),
@@ -839,21 +871,21 @@ impl<'hir> Map<'hir> {
 
     pub fn expect_item(&self, id: HirId) -> &'hir Item<'hir> {
         match self.tcx.hir_owner(id.expect_owner()) {
-            Some(Owner { node: OwnerNode::Item(item) }) => item,
+            Some(Owner { node: OwnerNode::Item(item), .. }) => item,
             _ => bug!("expected item, found {}", self.node_to_string(id)),
         }
     }
 
     pub fn expect_impl_item(&self, id: HirId) -> &'hir ImplItem<'hir> {
         match self.tcx.hir_owner(id.expect_owner()) {
-            Some(Owner { node: OwnerNode::ImplItem(item) }) => item,
+            Some(Owner { node: OwnerNode::ImplItem(item), .. }) => item,
             _ => bug!("expected impl item, found {}", self.node_to_string(id)),
         }
     }
 
     pub fn expect_trait_item(&self, id: HirId) -> &'hir TraitItem<'hir> {
         match self.tcx.hir_owner(id.expect_owner()) {
-            Some(Owner { node: OwnerNode::TraitItem(item) }) => item,
+            Some(Owner { node: OwnerNode::TraitItem(item), .. }) => item,
             _ => bug!("expected trait item, found {}", self.node_to_string(id)),
         }
     }
@@ -867,7 +899,7 @@ impl<'hir> Map<'hir> {
 
     pub fn expect_foreign_item(&self, id: HirId) -> &'hir ForeignItem<'hir> {
         match self.tcx.hir_owner(id.expect_owner()) {
-            Some(Owner { node: OwnerNode::ForeignItem(item) }) => item,
+            Some(Owner { node: OwnerNode::ForeignItem(item), .. }) => item,
             _ => bug!("expected foreign item, found {}", self.node_to_string(id)),
         }
     }
@@ -1032,42 +1064,10 @@ impl<'hir> intravisit::Map<'hir> for Map<'hir> {
     }
 }
 
-pub(super) fn index_hir<'tcx>(tcx: TyCtxt<'tcx>, (): ()) -> &'tcx IndexedHir<'tcx> {
-    let _prof_timer = tcx.sess.prof.generic_activity("build_hir_map");
-
-    // We can access untracked state since we are an eval_always query.
-    let hcx = tcx.create_stable_hashing_context();
-    let mut collector = NodeCollector::root(
-        tcx.sess,
-        &**tcx.arena,
-        tcx.untracked_crate,
-        &tcx.untracked_resolutions.definitions,
-        hcx,
-    );
-    let top_mod = tcx.untracked_crate.module();
-    collector.visit_mod(top_mod, top_mod.inner, CRATE_HIR_ID);
-
-    let map = collector.finalize_and_compute_crate_hash();
-    tcx.arena.alloc(map)
-}
-
 pub(super) fn crate_hash(tcx: TyCtxt<'_>, crate_num: CrateNum) -> Svh {
-    assert_eq!(crate_num, LOCAL_CRATE);
-
-    // We can access untracked state since we are an eval_always query.
-    let mut hcx = tcx.create_stable_hashing_context();
-
-    let mut hir_body_nodes: Vec<_> = tcx
-        .index_hir(())
-        .map
-        .iter_enumerated()
-        .filter_map(|(def_id, hod)| {
-            let def_path_hash = tcx.untracked_resolutions.definitions.def_path_hash(def_id);
-            let hash = hod.as_ref()?.hash;
-            Some((def_path_hash, hash, def_id))
-        })
-        .collect();
-    hir_body_nodes.sort_unstable_by_key(|bn| bn.0);
+    debug_assert_eq!(crate_num, LOCAL_CRATE);
+    let krate = tcx.hir_crate(());
+    let hir_body_hash = krate.hir_hash;
 
     let upstream_crates = upstream_crates(tcx);
 
@@ -1087,20 +1087,27 @@ pub(super) fn crate_hash(tcx: TyCtxt<'_>, crate_num: CrateNum) -> Svh {
 
     source_file_names.sort_unstable();
 
+    let mut hcx = tcx.create_stable_hashing_context();
     let mut stable_hasher = StableHasher::new();
-    for (def_path_hash, fingerprint, def_id) in hir_body_nodes.iter() {
-        def_path_hash.0.hash_stable(&mut hcx, &mut stable_hasher);
-        fingerprint.hash_stable(&mut hcx, &mut stable_hasher);
-        AttributeMap { map: &tcx.untracked_crate.attrs, prefix: *def_id }
-            .hash_stable(&mut hcx, &mut stable_hasher);
-        if tcx.sess.opts.debugging_opts.incremental_relative_spans {
-            let span = tcx.untracked_resolutions.definitions.def_span(*def_id);
-            debug_assert_eq!(span.parent(), None);
-            span.hash_stable(&mut hcx, &mut stable_hasher);
-        }
-    }
+    hir_body_hash.hash_stable(&mut hcx, &mut stable_hasher);
     upstream_crates.hash_stable(&mut hcx, &mut stable_hasher);
     source_file_names.hash_stable(&mut hcx, &mut stable_hasher);
+    if tcx.sess.opts.debugging_opts.incremental_relative_spans {
+        let definitions = &tcx.untracked_resolutions.definitions;
+        let mut owner_spans: Vec<_> = krate
+            .owners
+            .iter_enumerated()
+            .filter_map(|(def_id, info)| {
+                let _ = info.as_ref()?;
+                let def_path_hash = definitions.def_path_hash(def_id);
+                let span = definitions.def_span(def_id);
+                debug_assert_eq!(span.parent(), None);
+                Some((def_path_hash, span))
+            })
+            .collect();
+        owner_spans.sort_unstable_by_key(|bn| bn.0);
+        owner_spans.hash_stable(&mut hcx, &mut stable_hasher);
+    }
     tcx.sess.opts.dep_tracking_hash(true).hash_stable(&mut hcx, &mut stable_hasher);
     tcx.sess.local_stable_crate_id().hash_stable(&mut hcx, &mut stable_hasher);
 
diff --git a/compiler/rustc_middle/src/hir/mod.rs b/compiler/rustc_middle/src/hir/mod.rs
index 5016c5ce954..95d7273b17b 100644
--- a/compiler/rustc_middle/src/hir/mod.rs
+++ b/compiler/rustc_middle/src/hir/mod.rs
@@ -8,28 +8,12 @@ pub mod place;
 
 use crate::ty::query::Providers;
 use crate::ty::TyCtxt;
-use rustc_ast::Attribute;
 use rustc_data_structures::fingerprint::Fingerprint;
-use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_hir::def_id::LocalDefId;
 use rustc_hir::*;
-use rustc_index::vec::{Idx, IndexVec};
 use rustc_query_system::ich::StableHashingContext;
 use rustc_span::DUMMY_SP;
-use std::collections::BTreeMap;
-
-/// Result of HIR indexing.
-#[derive(Debug)]
-pub struct IndexedHir<'hir> {
-    /// Contents of the HIR owned by each definition. None for definitions that are not HIR owners.
-    // The `mut` comes from construction time, and is harmless since we only ever hand out
-    // immutable refs to IndexedHir.
-    map: IndexVec<LocalDefId, Option<&'hir mut OwnerNodes<'hir>>>,
-    /// Map from each owner to its parent's HirId inside another owner.
-    // This map is separate from `map` to eventually allow for per-owner indexing.
-    parenting: FxHashMap<LocalDefId, HirId>,
-}
 
 /// Top-level HIR node for current owner. This only contains the node for which
 /// `HirId::local_id == 0`, and excludes bodies.
@@ -39,85 +23,14 @@ pub struct IndexedHir<'hir> {
 #[derive(Copy, Clone, Debug)]
 pub struct Owner<'tcx> {
     node: OwnerNode<'tcx>,
+    hash_without_bodies: Fingerprint,
 }
 
 impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for Owner<'tcx> {
+    #[inline]
     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
-        let Owner { node } = self;
-        hcx.while_hashing_hir_bodies(false, |hcx| node.hash_stable(hcx, hasher));
-    }
-}
-
-/// HIR node coupled with its parent's id in the same HIR owner.
-///
-/// The parent is trash when the node is a HIR owner.
-#[derive(Clone, Debug)]
-pub struct ParentedNode<'tcx> {
-    parent: ItemLocalId,
-    node: Node<'tcx>,
-}
-
-#[derive(Debug)]
-pub struct OwnerNodes<'tcx> {
-    /// Pre-computed hash of the full HIR.
-    hash: Fingerprint,
-    /// Full HIR for the current owner.
-    // The zeroth node's parent is trash, but is never accessed.
-    nodes: IndexVec<ItemLocalId, Option<ParentedNode<'tcx>>>,
-    /// Content of local bodies.
-    bodies: FxHashMap<ItemLocalId, &'tcx Body<'tcx>>,
-}
-
-impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for OwnerNodes<'tcx> {
-    fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
-        // We ignore the `nodes` and `bodies` fields since these refer to information included in
-        // `hash` which is hashed in the collector and used for the crate hash.
-        let OwnerNodes { hash, nodes: _, bodies: _ } = *self;
-        hash.hash_stable(hcx, hasher);
-    }
-}
-
-/// Attributes owner by a HIR owner. It is build as a slice inside the attributes map, restricted
-/// to the nodes whose `HirId::owner` is `prefix`.
-#[derive(Copy, Clone)]
-pub struct AttributeMap<'tcx> {
-    map: &'tcx BTreeMap<HirId, &'tcx [Attribute]>,
-    prefix: LocalDefId,
-}
-
-impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for AttributeMap<'tcx> {
-    fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
-        let range = self.range();
-
-        range.clone().count().hash_stable(hcx, hasher);
-        for (key, value) in range {
-            key.hash_stable(hcx, hasher);
-            value.hash_stable(hcx, hasher);
-        }
-    }
-}
-
-impl<'tcx> std::fmt::Debug for AttributeMap<'tcx> {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        f.debug_struct("AttributeMap")
-            .field("prefix", &self.prefix)
-            .field("range", &&self.range().collect::<Vec<_>>()[..])
-            .finish()
-    }
-}
-
-impl<'tcx> AttributeMap<'tcx> {
-    fn get(&self, id: ItemLocalId) -> &'tcx [Attribute] {
-        self.map.get(&HirId { owner: self.prefix, local_id: id }).copied().unwrap_or(&[])
-    }
-
-    fn range(&self) -> std::collections::btree_map::Range<'_, rustc_hir::HirId, &[Attribute]> {
-        let local_zero = ItemLocalId::from_u32(0);
-        let range = HirId { owner: self.prefix, local_id: local_zero }..HirId {
-            owner: LocalDefId { local_def_index: self.prefix.local_def_index + 1 },
-            local_id: local_zero,
-        };
-        self.map.range(range)
+        let Owner { node: _, hash_without_bodies } = self;
+        hash_without_bodies.hash_stable(hcx, hasher)
     }
 }
 
@@ -149,21 +62,32 @@ pub fn provide(providers: &mut Providers) {
         hir.local_def_id(hir.get_module_parent_node(hir.local_def_id_to_hir_id(id)))
     };
     providers.hir_crate = |tcx, ()| tcx.untracked_crate;
-    providers.index_hir = map::index_hir;
     providers.crate_hash = map::crate_hash;
     providers.hir_module_items = map::hir_module_items;
     providers.hir_owner = |tcx, id| {
-        let owner = tcx.index_hir(()).map[id].as_ref()?;
-        let node = owner.nodes[ItemLocalId::new(0)].as_ref().unwrap().node;
-        let node = node.as_owner().unwrap(); // Indexing must ensure it is an OwnerNode.
-        Some(Owner { node })
+        let owner = tcx.hir_crate(()).owners[id].as_ref()?;
+        let node = owner.node();
+        Some(Owner { node, hash_without_bodies: owner.nodes.hash_without_bodies })
     };
-    providers.hir_owner_nodes = |tcx, id| tcx.index_hir(()).map[id].as_deref();
+    providers.hir_owner_nodes = |tcx, id| tcx.hir_crate(()).owners[id].as_ref().map(|i| &i.nodes);
     providers.hir_owner_parent = |tcx, id| {
-        let index = tcx.index_hir(());
-        index.parenting.get(&id).copied().unwrap_or(CRATE_HIR_ID)
+        // Accessing the def_key is ok since its value is hashed as part of `id`'s DefPathHash.
+        let parent = tcx.untracked_resolutions.definitions.def_key(id).parent;
+        let parent = parent.map_or(CRATE_HIR_ID, |local_def_index| {
+            let def_id = LocalDefId { local_def_index };
+            let mut parent_hir_id =
+                tcx.untracked_resolutions.definitions.local_def_id_to_hir_id(def_id);
+            if let Some(local_id) =
+                tcx.hir_crate(()).owners[parent_hir_id.owner].as_ref().unwrap().parenting.get(&id)
+            {
+                parent_hir_id.local_id = *local_id;
+            }
+            parent_hir_id
+        });
+        parent
     };
-    providers.hir_attrs = |tcx, id| AttributeMap { map: &tcx.untracked_crate.attrs, prefix: id };
+    providers.hir_attrs =
+        |tcx, id| tcx.hir_crate(()).owners[id].as_ref().map_or(AttributeMap::EMPTY, |o| &o.attrs);
     providers.source_span = |tcx, def_id| tcx.resolutions(()).definitions.def_span(def_id);
     providers.def_span = |tcx, def_id| tcx.hir().span_if_local(def_id).unwrap_or(DUMMY_SP);
     providers.fn_arg_names = |tcx, id| {
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index 4145cbd4249..18be9817c5f 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -36,18 +36,9 @@ rustc_queries! {
     /// prefer wrappers like `tcx.visit_all_items_in_krate()`.
     query hir_crate(key: ()) -> &'tcx Crate<'tcx> {
         eval_always
-        no_hash
         desc { "get the crate HIR" }
     }
 
-    /// The indexed HIR. This can be conveniently accessed by `tcx.hir()`.
-    /// Avoid calling this query directly.
-    query index_hir(_: ()) -> &'tcx crate::hir::IndexedHir<'tcx> {
-        eval_always
-        no_hash
-        desc { "index HIR" }
-    }
-
     /// The items in a module.
     ///
     /// This can be conveniently accessed by `tcx.hir().visit_item_likes_in_module`.
@@ -62,7 +53,6 @@ rustc_queries! {
     /// This can be conveniently accessed by methods on `tcx.hir()`.
     /// Avoid calling this query directly.
     query hir_owner(key: LocalDefId) -> Option<crate::hir::Owner<'tcx>> {
-        eval_always
         desc { |tcx| "HIR owner of `{}`", tcx.def_path_str(key.to_def_id()) }
     }
 
@@ -71,7 +61,6 @@ rustc_queries! {
     /// This can be conveniently accessed by methods on `tcx.hir()`.
     /// Avoid calling this query directly.
     query hir_owner_parent(key: LocalDefId) -> hir::HirId {
-        eval_always
         desc { |tcx| "HIR parent of `{}`", tcx.def_path_str(key.to_def_id()) }
     }
 
@@ -79,8 +68,7 @@ rustc_queries! {
     ///
     /// This can be conveniently accessed by methods on `tcx.hir()`.
     /// Avoid calling this query directly.
-    query hir_owner_nodes(key: LocalDefId) -> Option<&'tcx crate::hir::OwnerNodes<'tcx>> {
-        eval_always
+    query hir_owner_nodes(key: LocalDefId) -> Option<&'tcx hir::OwnerNodes<'tcx>> {
         desc { |tcx| "HIR owner items in `{}`", tcx.def_path_str(key.to_def_id()) }
     }
 
@@ -88,8 +76,7 @@ rustc_queries! {
     ///
     /// This can be conveniently accessed by methods on `tcx.hir()`.
     /// Avoid calling this query directly.
-    query hir_attrs(key: LocalDefId) -> rustc_middle::hir::AttributeMap<'tcx> {
-        eval_always
+    query hir_attrs(key: LocalDefId) -> &'tcx hir::AttributeMap<'tcx> {
         desc { |tcx| "HIR owner attributes in `{}`", tcx.def_path_str(key.to_def_id()) }
     }
 
@@ -933,12 +920,6 @@ rustc_queries! {
 
     query def_span(def_id: DefId) -> Span {
         desc { |tcx| "looking up span for `{}`", tcx.def_path_str(def_id) }
-        // FIXME(mw): DefSpans are not really inputs since they are derived from
-        // HIR. But at the moment HIR hashing still contains some hacks that allow
-        // to make type debuginfo to be source location independent. Declaring
-        // DefSpan an input makes sure that changes to these are always detected
-        // regardless of HIR hashing.
-        eval_always
     }
 
     query def_ident_span(def_id: DefId) -> Option<Span> {
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index 83d7c307bdf..14a7e0ef170 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -1337,20 +1337,15 @@ impl<'tcx> TyCtxt<'tcx> {
 
     #[inline(always)]
     pub fn create_stable_hashing_context(self) -> StableHashingContext<'tcx> {
-        let krate = self.gcx.untracked_crate;
         let resolutions = &self.gcx.untracked_resolutions;
-
-        StableHashingContext::new(self.sess, krate, &resolutions.definitions, &*resolutions.cstore)
+        StableHashingContext::new(self.sess, &resolutions.definitions, &*resolutions.cstore)
     }
 
     #[inline(always)]
     pub fn create_no_span_stable_hashing_context(self) -> StableHashingContext<'tcx> {
-        let krate = self.gcx.untracked_crate;
         let resolutions = &self.gcx.untracked_resolutions;
-
         StableHashingContext::ignore_spans(
             self.sess,
-            krate,
             &resolutions.definitions,
             &*resolutions.cstore,
         )
@@ -2823,7 +2818,8 @@ fn ptr_eq<T, U>(t: *const T, u: *const U) -> bool {
 }
 
 pub fn provide(providers: &mut ty::query::Providers) {
-    providers.in_scope_traits_map = |tcx, id| tcx.hir_crate(()).trait_map.get(&id);
+    providers.in_scope_traits_map =
+        |tcx, id| tcx.hir_crate(()).owners[id].as_ref().map(|owner_info| &owner_info.trait_map);
     providers.resolutions = |tcx, ()| &tcx.untracked_resolutions;
     providers.module_exports = |tcx, id| tcx.resolutions(()).export_map.get(&id).map(|v| &v[..]);
     providers.crate_name = |tcx, id| {
diff --git a/compiler/rustc_mir_transform/src/coverage/mod.rs b/compiler/rustc_mir_transform/src/coverage/mod.rs
index 1c946bd2d8a..e980d3d884f 100644
--- a/compiler/rustc_mir_transform/src/coverage/mod.rs
+++ b/compiler/rustc_mir_transform/src/coverage/mod.rs
@@ -14,7 +14,6 @@ use spans::{CoverageSpan, CoverageSpans};
 
 use crate::MirPass;
 
-use rustc_data_structures::fingerprint::Fingerprint;
 use rustc_data_structures::graph::WithNumNodes;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use rustc_data_structures::sync::Lrc;
@@ -29,7 +28,6 @@ use rustc_middle::mir::{
     TerminatorKind,
 };
 use rustc_middle::ty::TyCtxt;
-use rustc_query_system::ich::StableHashingContext;
 use rustc_span::def_id::DefId;
 use rustc_span::source_map::SourceMap;
 use rustc_span::{CharPos, ExpnKind, Pos, SourceFile, Span, Symbol};
@@ -574,15 +572,13 @@ fn get_body_span<'tcx>(
 }
 
 fn hash_mir_source<'tcx>(tcx: TyCtxt<'tcx>, hir_body: &'tcx rustc_hir::Body<'tcx>) -> u64 {
+    // FIXME(cjgillot) Stop hashing HIR manually here.
     let mut hcx = tcx.create_no_span_stable_hashing_context();
-    hash(&mut hcx, &hir_body.value).to_smaller_hash()
-}
-
-fn hash(
-    hcx: &mut StableHashingContext<'tcx>,
-    node: &impl HashStable<StableHashingContext<'tcx>>,
-) -> Fingerprint {
     let mut stable_hasher = StableHasher::new();
-    node.hash_stable(hcx, &mut stable_hasher);
+    let owner = hir_body.id().hir_id.owner;
+    let bodies = &tcx.hir_owner_nodes(owner).as_ref().unwrap().bodies;
+    hcx.with_hir_bodies(false, owner, bodies, |hcx| {
+        hir_body.value.hash_stable(hcx, &mut stable_hasher)
+    });
     stable_hasher.finish()
 }
diff --git a/compiler/rustc_query_system/src/ich/hcx.rs b/compiler/rustc_query_system/src/ich/hcx.rs
index f2e935c59fc..cfef2073373 100644
--- a/compiler/rustc_query_system/src/ich/hcx.rs
+++ b/compiler/rustc_query_system/src/ich/hcx.rs
@@ -6,6 +6,7 @@ use rustc_data_structures::sync::Lrc;
 use rustc_hir as hir;
 use rustc_hir::def_id::{DefId, LocalDefId};
 use rustc_hir::definitions::{DefPathHash, Definitions};
+use rustc_index::vec::IndexVec;
 use rustc_session::cstore::CrateStore;
 use rustc_session::Session;
 use rustc_span::source_map::SourceMap;
@@ -27,7 +28,6 @@ pub struct StableHashingContext<'a> {
     cstore: &'a dyn CrateStore,
     pub(super) body_resolver: BodyResolver<'a>,
     hash_spans: bool,
-    hash_bodies: bool,
     pub(super) node_id_hashing_mode: NodeIdHashingMode,
 
     // Very often, we are hashing something that does not need the
@@ -46,24 +46,19 @@ pub enum NodeIdHashingMode {
 /// We could also just store a plain reference to the `hir::Crate` but we want
 /// to avoid that the crate is used to get untracked access to all of the HIR.
 #[derive(Clone, Copy)]
-pub(super) struct BodyResolver<'tcx>(&'tcx hir::Crate<'tcx>);
-
-impl<'tcx> BodyResolver<'tcx> {
-    /// Returns a reference to the `hir::Body` with the given `BodyId`.
-    /// **Does not do any tracking**; use carefully.
-    pub(super) fn body(self, id: hir::BodyId) -> &'tcx hir::Body<'tcx> {
-        self.0.body(id)
-    }
+pub(super) enum BodyResolver<'tcx> {
+    Forbidden,
+    Traverse {
+        hash_bodies: bool,
+        owner: LocalDefId,
+        bodies: &'tcx IndexVec<hir::ItemLocalId, Option<&'tcx hir::Body<'tcx>>>,
+    },
 }
 
 impl<'a> StableHashingContext<'a> {
-    /// The `krate` here is only used for mapping `BodyId`s to `Body`s.
-    /// Don't use it for anything else or you'll run the risk of
-    /// leaking data out of the tracking system.
     #[inline]
     fn new_with_or_without_spans(
         sess: &'a Session,
-        krate: &'a hir::Crate<'a>,
         definitions: &'a Definitions,
         cstore: &'a dyn CrateStore,
         always_ignore_spans: bool,
@@ -72,13 +67,12 @@ impl<'a> StableHashingContext<'a> {
             !always_ignore_spans && !sess.opts.debugging_opts.incremental_ignore_spans;
 
         StableHashingContext {
-            body_resolver: BodyResolver(krate),
+            body_resolver: BodyResolver::Forbidden,
             definitions,
             cstore,
             caching_source_map: None,
             raw_source_map: sess.source_map(),
             hash_spans: hash_spans_initial,
-            hash_bodies: true,
             node_id_hashing_mode: NodeIdHashingMode::HashDefPath,
         }
     }
@@ -86,13 +80,11 @@ impl<'a> StableHashingContext<'a> {
     #[inline]
     pub fn new(
         sess: &'a Session,
-        krate: &'a hir::Crate<'a>,
         definitions: &'a Definitions,
         cstore: &'a dyn CrateStore,
     ) -> Self {
         Self::new_with_or_without_spans(
             sess,
-            krate,
             definitions,
             cstore,
             /*always_ignore_spans=*/ false,
@@ -102,20 +94,41 @@ impl<'a> StableHashingContext<'a> {
     #[inline]
     pub fn ignore_spans(
         sess: &'a Session,
-        krate: &'a hir::Crate<'a>,
         definitions: &'a Definitions,
         cstore: &'a dyn CrateStore,
     ) -> Self {
         let always_ignore_spans = true;
-        Self::new_with_or_without_spans(sess, krate, definitions, cstore, always_ignore_spans)
+        Self::new_with_or_without_spans(sess, definitions, cstore, always_ignore_spans)
     }
 
+    /// Allow hashing
     #[inline]
-    pub fn while_hashing_hir_bodies<F: FnOnce(&mut Self)>(&mut self, hash_bodies: bool, f: F) {
-        let prev_hash_bodies = self.hash_bodies;
-        self.hash_bodies = hash_bodies;
+    pub fn while_hashing_hir_bodies(&mut self, hb: bool, f: impl FnOnce(&mut Self)) {
+        let prev = match &mut self.body_resolver {
+            BodyResolver::Forbidden => panic!("Hashing HIR bodies is forbidden."),
+            BodyResolver::Traverse { ref mut hash_bodies, .. } => {
+                std::mem::replace(hash_bodies, hb)
+            }
+        };
         f(self);
-        self.hash_bodies = prev_hash_bodies;
+        match &mut self.body_resolver {
+            BodyResolver::Forbidden => unreachable!(),
+            BodyResolver::Traverse { ref mut hash_bodies, .. } => *hash_bodies = prev,
+        }
+    }
+
+    #[inline]
+    pub fn with_hir_bodies(
+        &mut self,
+        hash_bodies: bool,
+        owner: LocalDefId,
+        bodies: &'a IndexVec<hir::ItemLocalId, Option<&'a hir::Body<'a>>>,
+        f: impl FnOnce(&mut Self),
+    ) {
+        let prev = self.body_resolver;
+        self.body_resolver = BodyResolver::Traverse { hash_bodies, owner, bodies };
+        f(self);
+        self.body_resolver = prev;
     }
 
     #[inline]
@@ -153,11 +166,6 @@ impl<'a> StableHashingContext<'a> {
     }
 
     #[inline]
-    pub fn hash_bodies(&self) -> bool {
-        self.hash_bodies
-    }
-
-    #[inline]
     pub fn source_map(&mut self) -> &mut CachingSourceMapView<'a> {
         match self.caching_source_map {
             Some(ref mut sm) => sm,
diff --git a/compiler/rustc_query_system/src/ich/impls_hir.rs b/compiler/rustc_query_system/src/ich/impls_hir.rs
index 04eb263a977..24f3a2e7de0 100644
--- a/compiler/rustc_query_system/src/ich/impls_hir.rs
+++ b/compiler/rustc_query_system/src/ich/impls_hir.rs
@@ -1,12 +1,11 @@
 //! This module contains `HashStable` implementations for various HIR data
 //! types in no particular order.
 
+use crate::ich::hcx::BodyResolver;
 use crate::ich::{NodeIdHashingMode, StableHashingContext};
 use rustc_data_structures::fingerprint::Fingerprint;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey};
 use rustc_hir as hir;
-use rustc_hir::definitions::DefPathHash;
-use smallvec::SmallVec;
 use std::mem;
 
 impl<'ctx> rustc_hir::HashStableContext for StableHashingContext<'ctx> {
@@ -29,8 +28,13 @@ impl<'ctx> rustc_hir::HashStableContext for StableHashingContext<'ctx> {
     #[inline]
     fn hash_body_id(&mut self, id: hir::BodyId, hasher: &mut StableHasher) {
         let hcx = self;
-        if hcx.hash_bodies() {
-            hcx.body_resolver.body(id).hash_stable(hcx, hasher);
+        match hcx.body_resolver {
+            BodyResolver::Forbidden => panic!("Hashing HIR bodies is forbidden."),
+            BodyResolver::Traverse { hash_bodies: false, .. } => {}
+            BodyResolver::Traverse { hash_bodies: true, owner, bodies } => {
+                assert_eq!(id.hir_id.owner, owner);
+                bodies[id.hir_id.local_id].unwrap().hash_stable(hcx, hasher);
+            }
         }
     }
 
@@ -115,6 +119,16 @@ impl<'ctx> rustc_hir::HashStableContext for StableHashingContext<'ctx> {
 
         self.node_id_hashing_mode = prev_hash_node_ids;
     }
+
+    #[inline]
+    fn hash_hir_trait_candidate(&mut self, tc: &hir::TraitCandidate, hasher: &mut StableHasher) {
+        self.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
+            let hir::TraitCandidate { def_id, import_ids } = tc;
+
+            def_id.hash_stable(hcx, hasher);
+            import_ids.hash_stable(hcx, hasher);
+        });
+    }
 }
 
 impl<'a> HashStable<StableHashingContext<'a>> for hir::Body<'_> {
@@ -129,27 +143,3 @@ impl<'a> HashStable<StableHashingContext<'a>> for hir::Body<'_> {
         });
     }
 }
-
-impl<'a> HashStable<StableHashingContext<'a>> for hir::TraitCandidate {
-    fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
-        hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
-            let hir::TraitCandidate { def_id, import_ids } = self;
-
-            def_id.hash_stable(hcx, hasher);
-            import_ids.hash_stable(hcx, hasher);
-        });
-    }
-}
-
-impl<'a> ToStableHashKey<StableHashingContext<'a>> for hir::TraitCandidate {
-    type KeyType = (DefPathHash, SmallVec<[DefPathHash; 1]>);
-
-    fn to_stable_hash_key(&self, hcx: &StableHashingContext<'a>) -> Self::KeyType {
-        let hir::TraitCandidate { def_id, import_ids } = self;
-
-        (
-            hcx.def_path_hash(*def_id),
-            import_ids.iter().map(|def_id| hcx.local_def_path_hash(*def_id)).collect(),
-        )
-    }
-}
diff --git a/compiler/rustc_resolve/Cargo.toml b/compiler/rustc_resolve/Cargo.toml
index f1d3315d6e6..bd27c16c732 100644
--- a/compiler/rustc_resolve/Cargo.toml
+++ b/compiler/rustc_resolve/Cargo.toml
@@ -23,6 +23,7 @@ rustc_feature = { path = "../rustc_feature" }
 rustc_hir = { path = "../rustc_hir" }
 rustc_index = { path = "../rustc_index" }
 rustc_metadata = { path = "../rustc_metadata" }
+rustc_query_system = { path = "../rustc_query_system" }
 rustc_session = { path = "../rustc_session" }
 rustc_span = { path = "../rustc_span" }
 smallvec = { version = "1.6.1", features = ["union", "may_dangle"] }
diff --git a/compiler/rustc_resolve/src/late.rs b/compiler/rustc_resolve/src/late.rs
index 95633257965..0a24e00ee4b 100644
--- a/compiler/rustc_resolve/src/late.rs
+++ b/compiler/rustc_resolve/src/late.rs
@@ -1994,7 +1994,7 @@ impl<'a: 'ast, 'b, 'ast> LateResolutionVisitor<'a, 'b, 'ast> {
                 if ns == ValueNS {
                     let item_name = path.last().unwrap().ident;
                     let traits = self.traits_in_scope(item_name, ns);
-                    self.r.trait_map.as_mut().unwrap().insert(id, traits);
+                    self.r.trait_map.insert(id, traits);
                 }
 
                 if PrimTy::from_name(path[0].ident.name).is_some() {
@@ -2479,12 +2479,12 @@ impl<'a: 'ast, 'b, 'ast> LateResolutionVisitor<'a, 'b, 'ast> {
                 // the field name so that we can do some nice error reporting
                 // later on in typeck.
                 let traits = self.traits_in_scope(ident, ValueNS);
-                self.r.trait_map.as_mut().unwrap().insert(expr.id, traits);
+                self.r.trait_map.insert(expr.id, traits);
             }
             ExprKind::MethodCall(ref segment, ..) => {
                 debug!("(recording candidate traits for expr) recording traits for {}", expr.id);
                 let traits = self.traits_in_scope(segment.ident, ValueNS);
-                self.r.trait_map.as_mut().unwrap().insert(expr.id, traits);
+                self.r.trait_map.insert(expr.id, traits);
             }
             _ => {
                 // Nothing to do.
diff --git a/compiler/rustc_resolve/src/lib.rs b/compiler/rustc_resolve/src/lib.rs
index 9652c483686..4b6585f5543 100644
--- a/compiler/rustc_resolve/src/lib.rs
+++ b/compiler/rustc_resolve/src/lib.rs
@@ -54,13 +54,14 @@ use rustc_middle::hir::exports::ExportMap;
 use rustc_middle::span_bug;
 use rustc_middle::ty::query::Providers;
 use rustc_middle::ty::{self, DefIdTree, MainDefinition, ResolverOutputs};
+use rustc_query_system::ich::StableHashingContext;
 use rustc_session::cstore::{CrateStore, MetadataLoaderDyn};
 use rustc_session::lint;
 use rustc_session::lint::{BuiltinLintDiagnostics, LintBuffer};
 use rustc_session::Session;
 use rustc_span::edition::Edition;
 use rustc_span::hygiene::{ExpnId, ExpnKind, LocalExpnId, MacroKind, SyntaxContext, Transparency};
-use rustc_span::source_map::{CachingSourceMapView, Spanned};
+use rustc_span::source_map::Spanned;
 use rustc_span::symbol::{kw, sym, Ident, Symbol};
 use rustc_span::{Span, DUMMY_SP};
 
@@ -930,7 +931,7 @@ pub struct Resolver<'a> {
     /// `CrateNum` resolutions of `extern crate` items.
     extern_crate_map: FxHashMap<LocalDefId, CrateNum>,
     export_map: ExportMap,
-    trait_map: Option<NodeMap<Vec<TraitCandidate>>>,
+    trait_map: NodeMap<Vec<TraitCandidate>>,
 
     /// A map from nodes to anonymous modules.
     /// Anonymous modules are pseudo-modules that are implicitly created around items
@@ -1177,6 +1178,10 @@ impl ResolverAstLowering for Resolver<'_> {
         &mut self.definitions
     }
 
+    fn create_stable_hashing_context(&self) -> StableHashingContext<'_> {
+        StableHashingContext::new(self.session, &self.definitions, self.crate_loader.cstore())
+    }
+
     fn lint_buffer(&mut self) -> &mut LintBuffer {
         &mut self.lint_buffer
     }
@@ -1185,8 +1190,8 @@ impl ResolverAstLowering for Resolver<'_> {
         self.next_node_id()
     }
 
-    fn take_trait_map(&mut self) -> NodeMap<Vec<TraitCandidate>> {
-        std::mem::replace(&mut self.trait_map, None).unwrap()
+    fn take_trait_map(&mut self, node: NodeId) -> Option<Vec<TraitCandidate>> {
+        self.trait_map.remove(&node)
     }
 
     fn opt_local_def_id(&self, node: NodeId) -> Option<LocalDefId> {
@@ -1245,37 +1250,6 @@ impl ResolverAstLowering for Resolver<'_> {
     }
 }
 
-struct ExpandHasher<'a, 'b> {
-    source_map: CachingSourceMapView<'a>,
-    resolver: &'a Resolver<'b>,
-}
-
-impl<'a, 'b> rustc_span::HashStableContext for ExpandHasher<'a, 'b> {
-    #[inline]
-    fn hash_spans(&self) -> bool {
-        true
-    }
-
-    #[inline]
-    fn def_span(&self, id: LocalDefId) -> Span {
-        self.resolver.def_span(id)
-    }
-
-    #[inline]
-    fn def_path_hash(&self, def_id: DefId) -> DefPathHash {
-        self.resolver.def_path_hash(def_id)
-    }
-
-    #[inline]
-    fn span_data_to_lines_and_cols(
-        &mut self,
-        span: &rustc_span::SpanData,
-    ) -> Option<(Lrc<rustc_span::SourceFile>, usize, rustc_span::BytePos, usize, rustc_span::BytePos)>
-    {
-        self.source_map.span_data_to_lines_and_cols(span)
-    }
-}
-
 impl<'a> Resolver<'a> {
     pub fn new(
         session: &'a Session,
@@ -1363,7 +1337,7 @@ impl<'a> Resolver<'a> {
             label_res_map: Default::default(),
             extern_crate_map: Default::default(),
             export_map: FxHashMap::default(),
-            trait_map: Some(NodeMap::default()),
+            trait_map: NodeMap::default(),
             underscore_disambiguator: 0,
             empty_module,
             module_map,
@@ -1456,13 +1430,6 @@ impl<'a> Resolver<'a> {
         self.arenas.new_module(parent, kind, expn_id, span, no_implicit_prelude, module_map)
     }
 
-    fn create_stable_hashing_context(&self) -> ExpandHasher<'_, 'a> {
-        ExpandHasher {
-            source_map: CachingSourceMapView::new(self.session.source_map()),
-            resolver: self,
-        }
-    }
-
     pub fn next_node_id(&mut self) -> NodeId {
         let next = self
             .next_node_id
diff --git a/src/test/ui/privacy/privacy2.stderr b/src/test/ui/privacy/privacy2.stderr
index 882f314655d..c2a33ce1f59 100644
--- a/src/test/ui/privacy/privacy2.stderr
+++ b/src/test/ui/privacy/privacy2.stderr
@@ -23,13 +23,7 @@ LL | pub fn foo() {}
 
 error: requires `sized` lang_item
 
-error: requires `sized` lang_item
-
-error: requires `sized` lang_item
-
-error: requires `sized` lang_item
-
-error: aborting due to 6 previous errors
+error: aborting due to 3 previous errors
 
 Some errors have detailed explanations: E0432, E0603.
 For more information about an error, try `rustc --explain E0432`.
diff --git a/src/test/ui/privacy/privacy3.stderr b/src/test/ui/privacy/privacy3.stderr
index 42ce456d962..22c1e48b07d 100644
--- a/src/test/ui/privacy/privacy3.stderr
+++ b/src/test/ui/privacy/privacy3.stderr
@@ -6,12 +6,6 @@ LL |     use bar::gpriv;
 
 error: requires `sized` lang_item
 
-error: requires `sized` lang_item
-
-error: requires `sized` lang_item
-
-error: requires `sized` lang_item
-
-error: aborting due to 5 previous errors
+error: aborting due to 2 previous errors
 
 For more information about this error, try `rustc --explain E0432`.