Auto merge of #59953 - eddyb:soa-metadata, r=michaelwoerister

 rustc_metadata: replace Entry table with one table for each of its fields (AoS -> SoA).

In https://github.com/rust-lang/rust/pull/59789#issuecomment-481958212 I noticed that for many cross-crate queries (e.g. `predicates_of(def_id)`), we were deserializing the `rustc_metadata::schema::Entry` for `def_id` *only* to read one field (i.e. `predicates`).

But there are several such queries, and `Entry` is not particularly small (in terms of number of fields, the encoding itself is quite compact), so there is a large (and unnecessary) constant factor.

This PR replaces the (random-access) array¹ of `Entry` structures ("AoS"), with many separate arrays¹, one for each field that used to be in `Entry` ("SoA"), resulting in the ability to read individual fields separately, with negligible time overhead (in thoery), and some size overhead (as these arrays are not sparse).

In a way, the new approach is closer to incremental on-disk caches, which store each query's cached results separately, but it would take significantly more work to unify the two.

For stage1 `libcore`'s metadata blob, the size overhead is `8.44%`, and I have another commit (~~not initially included because I want to do perf runs with both~~ **EDIT**: added it now) that brings it down to `5.88%`.

¹(in the source, these arrays are called "tables", but perhaps they could use a better name)

6 files changed, 857 insertions, 876 deletions

diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index 6969d608d76..962846b0475 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -2,6 +2,7 @@
 
 use crate::cstore::{self, CrateMetadata, MetadataBlob};
 use crate::schema::*;
+use crate::table::{FixedSizeEncoding, PerDefTable};
 
 use rustc_index::vec::IndexVec;
 use rustc_data_structures::sync::{Lrc, ReadGuard};
@@ -25,9 +26,10 @@ use rustc::util::captures::Captures;
 
 use std::io;
 use std::mem;
+use std::num::NonZeroUsize;
 use std::u32;
 
-use rustc_serialize::{Decodable, Decoder, SpecializedDecoder, opaque};
+use rustc_serialize::{Decodable, Decoder, Encodable, SpecializedDecoder, opaque};
 use syntax::attr;
 use syntax::ast::{self, Ident};
 use syntax::source_map::{self, respan, Spanned};
@@ -129,20 +131,20 @@ impl<'a, 'tcx> Metadata<'a, 'tcx> for (&'a CrateMetadata, TyCtxt<'tcx>) {
     }
 }
 
-impl<'a, 'tcx, T: Decodable> Lazy<T> {
-    crate fn decode<M: Metadata<'a, 'tcx>>(self, meta: M) -> T {
-        let mut dcx = meta.decoder(self.position);
+impl<'a, 'tcx, T: Encodable + Decodable> Lazy<T> {
+    crate fn decode<M: Metadata<'a, 'tcx>>(self, metadata: M) -> T {
+        let mut dcx = metadata.decoder(self.position.get());
         dcx.lazy_state = LazyState::NodeStart(self.position);
         T::decode(&mut dcx).unwrap()
     }
 }
 
-impl<'a: 'x, 'tcx: 'x, 'x, T: Decodable> Lazy<[T]> {
+impl<'a: 'x, 'tcx: 'x, 'x, T: Encodable + Decodable> Lazy<[T]> {
     crate fn decode<M: Metadata<'a, 'tcx>>(
         self,
-        meta: M,
+        metadata: M,
     ) -> impl ExactSizeIterator<Item = T> + Captures<'a> + Captures<'tcx> + 'x {
-        let mut dcx = meta.decoder(self.position);
+        let mut dcx = metadata.decoder(self.position.get());
         dcx.lazy_state = LazyState::NodeStart(self.position);
         (0..self.meta).map(move |_| T::decode(&mut dcx).unwrap())
     }
@@ -166,13 +168,14 @@ impl<'a, 'tcx> DecodeContext<'a, 'tcx> {
         let position = match self.lazy_state {
             LazyState::NoNode => bug!("read_lazy_with_meta: outside of a metadata node"),
             LazyState::NodeStart(start) => {
+                let start = start.get();
                 assert!(distance + min_size <= start);
                 start - distance - min_size
             }
-            LazyState::Previous(last_min_end) => last_min_end + distance,
+            LazyState::Previous(last_min_end) => last_min_end.get() + distance,
         };
-        self.lazy_state = LazyState::Previous(position + min_size);
-        Ok(Lazy::from_position_and_meta(position, meta))
+        self.lazy_state = LazyState::Previous(NonZeroUsize::new(position + min_size).unwrap());
+        Ok(Lazy::from_position_and_meta(NonZeroUsize::new(position).unwrap(), meta))
     }
 }
 
@@ -235,13 +238,13 @@ impl<'a, 'tcx> TyDecoder<'tcx> for DecodeContext<'a, 'tcx> {
     }
 }
 
-impl<'a, 'tcx, T> SpecializedDecoder<Lazy<T>> for DecodeContext<'a, 'tcx> {
+impl<'a, 'tcx, T: Encodable> SpecializedDecoder<Lazy<T>> for DecodeContext<'a, 'tcx> {
     fn specialized_decode(&mut self) -> Result<Lazy<T>, Self::Error> {
         self.read_lazy_with_meta(())
     }
 }
 
-impl<'a, 'tcx, T> SpecializedDecoder<Lazy<[T]>> for DecodeContext<'a, 'tcx> {
+impl<'a, 'tcx, T: Encodable> SpecializedDecoder<Lazy<[T]>> for DecodeContext<'a, 'tcx> {
     fn specialized_decode(&mut self) -> Result<Lazy<[T]>, Self::Error> {
         let len = self.read_usize()?;
         if len == 0 {
@@ -252,6 +255,14 @@ impl<'a, 'tcx, T> SpecializedDecoder<Lazy<[T]>> for DecodeContext<'a, 'tcx> {
     }
 }
 
+impl<'a, 'tcx, T> SpecializedDecoder<Lazy<PerDefTable<T>>> for DecodeContext<'a, 'tcx>
+    where Option<T>: FixedSizeEncoding,
+{
+    fn specialized_decode(&mut self) -> Result<Lazy<PerDefTable<T>>, Self::Error> {
+        let len = self.read_usize()?;
+        self.read_lazy_with_meta(len)
+    }
+}
 
 impl<'a, 'tcx> SpecializedDecoder<DefId> for DecodeContext<'a, 'tcx> {
     #[inline]
@@ -384,7 +395,9 @@ impl<'tcx> MetadataBlob {
     }
 
     crate fn get_rustc_version(&self) -> String {
-        Lazy::<String>::from_position(METADATA_HEADER.len() + 4).decode(self)
+        Lazy::<String>::from_position(
+            NonZeroUsize::new(METADATA_HEADER.len() + 4).unwrap(),
+        ).decode(self)
     }
 
     crate fn get_root(&self) -> CrateRoot<'tcx> {
@@ -393,7 +406,9 @@ impl<'tcx> MetadataBlob {
         let pos = (((slice[offset + 0] as u32) << 24) | ((slice[offset + 1] as u32) << 16) |
                    ((slice[offset + 2] as u32) << 8) |
                    ((slice[offset + 3] as u32) << 0)) as usize;
-        Lazy::<CrateRoot<'tcx>>::from_position(pos).decode(self)
+        Lazy::<CrateRoot<'tcx>>::from_position(
+            NonZeroUsize::new(pos).unwrap(),
+        ).decode(self)
     }
 
     crate fn list_crate_metadata(&self,
@@ -458,27 +473,20 @@ impl<'a, 'tcx> CrateMetadata {
             self.root.proc_macro_data.unwrap().decode(self).find(|x| *x == id).is_some()
     }
 
-    fn entry_unless_proc_macro(&self, id: DefIndex) -> Option<Entry<'tcx>> {
-        match self.is_proc_macro(id) {
-            true => None,
-            false => Some(self.entry(id)),
-        }
-    }
-
-    fn maybe_entry(&self, item_id: DefIndex) -> Option<Lazy<Entry<'tcx>>> {
-        self.root.entries_index.lookup(self.blob.raw_bytes(), item_id)
+    fn maybe_kind(&self, item_id: DefIndex) -> Option<EntryKind<'tcx>> {
+        self.root.per_def.kind.get(self, item_id).map(|k| k.decode(self))
     }
 
-    fn entry(&self, item_id: DefIndex) -> Entry<'tcx> {
-        match self.maybe_entry(item_id) {
-            None => {
-                bug!("entry: id not found: {:?} in crate {:?} with number {}",
-                     item_id,
-                     self.root.name,
-                     self.cnum)
-            }
-            Some(d) => d.decode(self),
-        }
+    fn kind(&self, item_id: DefIndex) -> EntryKind<'tcx> {
+        assert!(!self.is_proc_macro(item_id));
+        self.maybe_kind(item_id).unwrap_or_else(|| {
+            bug!(
+                "CrateMetadata::kind({:?}): id not found, in crate {:?} with number {}",
+                item_id,
+                self.root.name,
+                self.cnum,
+            )
+        })
     }
 
     fn local_def_id(&self, index: DefIndex) -> DefId {
@@ -514,7 +522,7 @@ impl<'a, 'tcx> CrateMetadata {
 
     crate fn def_kind(&self, index: DefIndex) -> Option<DefKind> {
         if !self.is_proc_macro(index) {
-            self.entry(index).kind.def_kind()
+            self.kind(index).def_kind()
         } else {
             Some(DefKind::Macro(
                 macro_kind(self.raw_proc_macro(index))
@@ -523,7 +531,7 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn get_span(&self, index: DefIndex, sess: &Session) -> Span {
-        self.entry(index).span.decode((self, sess))
+        self.root.per_def.span.get(self, index).unwrap().decode((self, sess))
     }
 
     crate fn load_proc_macro(&self, id: DefIndex, sess: &Session) -> SyntaxExtension {
@@ -552,12 +560,12 @@ impl<'a, 'tcx> CrateMetadata {
             helper_attrs,
             self.root.edition,
             Symbol::intern(name),
-            &self.get_attributes(&self.entry(id), sess),
+            &self.get_item_attrs(id, sess),
         )
     }
 
     crate fn get_trait_def(&self, item_id: DefIndex, sess: &Session) -> ty::TraitDef {
-        match self.entry(item_id).kind {
+        match self.kind(item_id) {
             EntryKind::Trait(data) => {
                 let data = data.decode((self, sess));
                 ty::TraitDef::new(self.local_def_id(item_id),
@@ -582,18 +590,24 @@ impl<'a, 'tcx> CrateMetadata {
     fn get_variant(
         &self,
         tcx: TyCtxt<'tcx>,
-        item: &Entry<'_>,
+        kind: &EntryKind<'_>,
         index: DefIndex,
         parent_did: DefId,
-        adt_kind: ty::AdtKind,
     ) -> ty::VariantDef {
-        let data = match item.kind {
+        let data = match kind {
             EntryKind::Variant(data) |
             EntryKind::Struct(data, _) |
             EntryKind::Union(data, _) => data.decode(self),
             _ => bug!(),
         };
 
+        let adt_kind = match kind {
+            EntryKind::Variant(_) => ty::AdtKind::Enum,
+            EntryKind::Struct(..) => ty::AdtKind::Struct,
+            EntryKind::Union(..) => ty::AdtKind::Union,
+            _ => bug!(),
+        };
+
         let variant_did = if adt_kind == ty::AdtKind::Enum {
             Some(self.local_def_id(index))
         } else {
@@ -607,14 +621,12 @@ impl<'a, 'tcx> CrateMetadata {
             variant_did,
             ctor_did,
             data.discr,
-            item.children.decode(self).map(|index| {
-                let f = self.entry(index);
-                ty::FieldDef {
+            self.root.per_def.children.get(self, index).unwrap_or(Lazy::empty())
+                .decode(self).map(|index| ty::FieldDef {
                     did: self.local_def_id(index),
                     ident: Ident::with_dummy_span(self.item_name(index)),
-                    vis: f.visibility.decode(self)
-                }
-            }).collect(),
+                    vis: self.get_visibility(index),
+                }).collect(),
             data.ctor_kind,
             adt_kind,
             parent_did,
@@ -623,28 +635,28 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn get_adt_def(&self, item_id: DefIndex, tcx: TyCtxt<'tcx>) -> &'tcx ty::AdtDef {
-        let item = self.entry(item_id);
+        let kind = self.kind(item_id);
         let did = self.local_def_id(item_id);
 
-        let (kind, repr) = match item.kind {
+        let (adt_kind, repr) = match kind {
             EntryKind::Enum(repr) => (ty::AdtKind::Enum, repr),
             EntryKind::Struct(_, repr) => (ty::AdtKind::Struct, repr),
             EntryKind::Union(_, repr) => (ty::AdtKind::Union, repr),
             _ => bug!("get_adt_def called on a non-ADT {:?}", did),
         };
 
-        let variants = if let ty::AdtKind::Enum = kind {
-            item.children
+        let variants = if let ty::AdtKind::Enum = adt_kind {
+            self.root.per_def.children.get(self, item_id).unwrap_or(Lazy::empty())
                 .decode(self)
                 .map(|index| {
-                    self.get_variant(tcx, &self.entry(index), index, did, kind)
+                    self.get_variant(tcx, &self.kind(index), index, did)
                 })
                 .collect()
         } else {
-            std::iter::once(self.get_variant(tcx, &item, item_id, did, kind)).collect()
+            std::iter::once(self.get_variant(tcx, &kind, item_id, did)).collect()
         };
 
-        tcx.alloc_adt_def(did, kind, variants, repr)
+        tcx.alloc_adt_def(did, adt_kind, variants, repr)
     }
 
     crate fn get_predicates(
@@ -652,7 +664,7 @@ impl<'a, 'tcx> CrateMetadata {
         item_id: DefIndex,
         tcx: TyCtxt<'tcx>,
     ) -> ty::GenericPredicates<'tcx> {
-        self.entry(item_id).predicates.unwrap().decode((self, tcx))
+        self.root.per_def.predicates.get(self, item_id).unwrap().decode((self, tcx))
 }
 
     crate fn get_predicates_defined_on(
@@ -660,7 +672,7 @@ impl<'a, 'tcx> CrateMetadata {
         item_id: DefIndex,
         tcx: TyCtxt<'tcx>,
     ) -> ty::GenericPredicates<'tcx> {
-        self.entry(item_id).predicates_defined_on.unwrap().decode((self, tcx))
+        self.root.per_def.predicates_defined_on.get(self, item_id).unwrap().decode((self, tcx))
     }
 
     crate fn get_super_predicates(
@@ -668,7 +680,7 @@ impl<'a, 'tcx> CrateMetadata {
         item_id: DefIndex,
         tcx: TyCtxt<'tcx>,
     ) -> ty::GenericPredicates<'tcx> {
-        let super_predicates = match self.entry(item_id).kind {
+        let super_predicates = match self.kind(item_id) {
             EntryKind::Trait(data) => data.decode(self).super_predicates,
             EntryKind::TraitAlias(data) => data.decode(self).super_predicates,
             _ => bug!("def-index does not refer to trait or trait alias"),
@@ -678,34 +690,35 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn get_generics(&self, item_id: DefIndex, sess: &Session) -> ty::Generics {
-        self.entry(item_id).generics.unwrap().decode((self, sess))
+        self.root.per_def.generics.get(self, item_id).unwrap().decode((self, sess))
     }
 
     crate fn get_type(&self, id: DefIndex, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
-        self.entry(id).ty.unwrap().decode((self, tcx))
+        self.root.per_def.ty.get(self, id).unwrap().decode((self, tcx))
     }
 
     crate fn get_stability(&self, id: DefIndex) -> Option<attr::Stability> {
         match self.is_proc_macro(id) {
             true => self.root.proc_macro_stability.clone(),
-            false => self.entry(id).stability.map(|stab| stab.decode(self)),
+            false => self.root.per_def.stability.get(self, id).map(|stab| stab.decode(self)),
         }
     }
 
     crate fn get_deprecation(&self, id: DefIndex) -> Option<attr::Deprecation> {
-        self.entry_unless_proc_macro(id)
-            .and_then(|entry| entry.deprecation.map(|depr| depr.decode(self)))
+        self.root.per_def.deprecation.get(self, id)
+            .filter(|_| !self.is_proc_macro(id))
+            .map(|depr| depr.decode(self))
     }
 
     crate fn get_visibility(&self, id: DefIndex) -> ty::Visibility {
         match self.is_proc_macro(id) {
             true => ty::Visibility::Public,
-            false => self.entry(id).visibility.decode(self),
+            false => self.root.per_def.visibility.get(self, id).unwrap().decode(self),
         }
     }
 
     fn get_impl_data(&self, id: DefIndex) -> ImplData<'tcx> {
-        match self.entry(id).kind {
+        match self.kind(id) {
             EntryKind::Impl(data) => data.decode(self),
             _ => bug!(),
         }
@@ -801,38 +814,42 @@ impl<'a, 'tcx> CrateMetadata {
         }
 
         // Find the item.
-        let item = match self.maybe_entry(id) {
+        let kind = match self.maybe_kind(id) {
             None => return,
-            Some(item) => item.decode((self, sess)),
+            Some(kind) => kind,
         };
 
         // Iterate over all children.
         let macros_only = self.dep_kind.lock().macros_only();
-        for child_index in item.children.decode((self, sess)) {
+        let children = self.root.per_def.children.get(self, id).unwrap_or(Lazy::empty());
+        for child_index in children.decode((self, sess)) {
             if macros_only {
                 continue
             }
 
             // Get the item.
-            if let Some(child) = self.maybe_entry(child_index) {
-                let child = child.decode((self, sess));
-                match child.kind {
+            if let Some(child_kind) = self.maybe_kind(child_index) {
+                match child_kind {
                     EntryKind::MacroDef(..) => {}
                     _ if macros_only => continue,
                     _ => {}
                 }
 
                 // Hand off the item to the callback.
-                match child.kind {
+                match child_kind {
                     // FIXME(eddyb) Don't encode these in children.
                     EntryKind::ForeignMod => {
-                        for child_index in child.children.decode((self, sess)) {
+                        let child_children =
+                            self.root.per_def.children.get(self, child_index)
+                                .unwrap_or(Lazy::empty());
+                        for child_index in child_children.decode((self, sess)) {
                             if let Some(kind) = self.def_kind(child_index) {
                                 callback(def::Export {
                                     res: Res::Def(kind, self.local_def_id(child_index)),
                                     ident: Ident::with_dummy_span(self.item_name(child_index)),
                                     vis: self.get_visibility(child_index),
-                                    span: self.entry(child_index).span.decode((self, sess)),
+                                    span: self.root.per_def.span.get(self, child_index).unwrap()
+                                        .decode((self, sess)),
                                 });
                             }
                         }
@@ -844,7 +861,7 @@ impl<'a, 'tcx> CrateMetadata {
                 }
 
                 let def_key = self.def_key(child_index);
-                let span = child.span.decode((self, sess));
+                let span = self.get_span(child_index, sess);
                 if let (Some(kind), Some(name)) =
                     (self.def_kind(child_index), def_key.disambiguated_data.data.get_opt_name()) {
                     let ident = Ident::from_interned_str(name);
@@ -897,7 +914,7 @@ impl<'a, 'tcx> CrateMetadata {
             }
         }
 
-        if let EntryKind::Mod(data) = item.kind {
+        if let EntryKind::Mod(data) = kind {
             for exp in data.decode((self, sess)).reexports.decode((self, sess)) {
                 match exp.res {
                     Res::Def(DefKind::Macro(..), _) => {}
@@ -911,15 +928,16 @@ impl<'a, 'tcx> CrateMetadata {
 
     crate fn is_item_mir_available(&self, id: DefIndex) -> bool {
         !self.is_proc_macro(id) &&
-        self.maybe_entry(id).and_then(|item| item.decode(self).mir).is_some()
+            self.root.per_def.mir.get(self, id).is_some()
     }
 
     crate fn get_optimized_mir(&self, tcx: TyCtxt<'tcx>, id: DefIndex) -> Body<'tcx> {
-        self.entry_unless_proc_macro(id)
-            .and_then(|entry| entry.mir.map(|mir| mir.decode((self, tcx))))
+        self.root.per_def.mir.get(self, id)
+            .filter(|_| !self.is_proc_macro(id))
             .unwrap_or_else(|| {
                 bug!("get_optimized_mir: missing MIR for `{:?}`", self.local_def_id(id))
             })
+            .decode((self, tcx))
     }
 
     crate fn get_promoted_mir(
@@ -927,15 +945,16 @@ impl<'a, 'tcx> CrateMetadata {
         tcx: TyCtxt<'tcx>,
         id: DefIndex,
     ) -> IndexVec<Promoted, Body<'tcx>> {
-        self.entry_unless_proc_macro(id)
-            .and_then(|entry| entry.promoted_mir.map(|promoted| promoted.decode((self, tcx))))
+        self.root.per_def.promoted_mir.get(self, id)
+            .filter(|_| !self.is_proc_macro(id))
             .unwrap_or_else(|| {
                 bug!("get_promoted_mir: missing MIR for `{:?}`", self.local_def_id(id))
             })
+            .decode((self, tcx))
     }
 
     crate fn mir_const_qualif(&self, id: DefIndex) -> u8 {
-        match self.entry(id).kind {
+        match self.kind(id) {
             EntryKind::Const(qualif, _) |
             EntryKind::AssocConst(AssocContainer::ImplDefault, qualif, _) |
             EntryKind::AssocConst(AssocContainer::ImplFinal, qualif, _) => {
@@ -946,12 +965,11 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn get_associated_item(&self, id: DefIndex) -> ty::AssocItem {
-        let item = self.entry(id);
         let def_key = self.def_key(id);
         let parent = self.local_def_id(def_key.parent.unwrap());
         let name = def_key.disambiguated_data.data.get_opt_name().unwrap();
 
-        let (kind, container, has_self) = match item.kind {
+        let (kind, container, has_self) = match self.kind(id) {
             EntryKind::AssocConst(container, _, _) => {
                 (ty::AssocKind::Const, container, false)
             }
@@ -971,7 +989,7 @@ impl<'a, 'tcx> CrateMetadata {
         ty::AssocItem {
             ident: Ident::from_interned_str(name),
             kind,
-            vis: item.visibility.decode(self),
+            vis: self.get_visibility(id),
             defaultness: container.defaultness(),
             def_id: self.local_def_id(id),
             container: container.with_def_id(parent),
@@ -980,11 +998,12 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn get_item_variances(&self, id: DefIndex) -> Vec<ty::Variance> {
-        self.entry(id).variances.decode(self).collect()
+        self.root.per_def.variances.get(self, id).unwrap_or(Lazy::empty())
+            .decode(self).collect()
     }
 
     crate fn get_ctor_kind(&self, node_id: DefIndex) -> CtorKind {
-        match self.entry(node_id).kind {
+        match self.kind(node_id) {
             EntryKind::Struct(data, _) |
             EntryKind::Union(data, _) |
             EntryKind::Variant(data) => data.decode(self).ctor_kind,
@@ -993,7 +1012,7 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn get_ctor_def_id(&self, node_id: DefIndex) -> Option<DefId> {
-        match self.entry(node_id).kind {
+        match self.kind(node_id) {
             EntryKind::Struct(data, _) => {
                 data.decode(self).ctor.map(|index| self.local_def_id(index))
             }
@@ -1015,8 +1034,9 @@ impl<'a, 'tcx> CrateMetadata {
             node_id
         };
 
-        let item = self.entry(item_id);
-        Lrc::from(self.get_attributes(&item, sess))
+        Lrc::from(self.root.per_def.attributes.get(self, item_id).unwrap_or(Lazy::empty())
+            .decode((self, sess))
+            .collect::<Vec<_>>())
     }
 
     crate fn get_struct_field_names(
@@ -1024,17 +1044,12 @@ impl<'a, 'tcx> CrateMetadata {
         id: DefIndex,
         sess: &Session,
     ) -> Vec<Spanned<ast::Name>> {
-        self.entry(id)
-            .children
+        self.root.per_def.children.get(self, id).unwrap_or(Lazy::empty())
             .decode(self)
             .map(|index| respan(self.get_span(index, sess), self.item_name(index)))
             .collect()
     }
 
-    fn get_attributes(&self, item: &Entry<'tcx>, sess: &Session) -> Vec<ast::Attribute> {
-        item.attributes.decode((self, sess)).collect()
-    }
-
     // Translate a DefId from the current compilation environment to a DefId
     // for an external crate.
     fn reverse_translate_def_id(&self, did: DefId) -> Option<DefId> {
@@ -1055,10 +1070,11 @@ impl<'a, 'tcx> CrateMetadata {
         tcx: TyCtxt<'tcx>,
         id: DefIndex,
     ) -> &'tcx [DefId] {
-        tcx.arena.alloc_from_iter(self.entry(id)
-                                      .inherent_impls
-                                      .decode(self)
-                                      .map(|index| self.local_def_id(index)))
+        tcx.arena.alloc_from_iter(
+            self.root.per_def.inherent_impls.get(self, id).unwrap_or(Lazy::empty())
+                .decode(self)
+                .map(|index| self.local_def_id(index))
+        )
     }
 
     crate fn get_implementations_for_trait(
@@ -1100,7 +1116,7 @@ impl<'a, 'tcx> CrateMetadata {
             _ => return None,
         }
         def_key.parent.and_then(|parent_index| {
-            match self.entry(parent_index).kind {
+            match self.kind(parent_index) {
                 EntryKind::Trait(_) |
                 EntryKind::TraitAlias(_) => Some(self.local_def_id(parent_index)),
                 _ => None,
@@ -1153,7 +1169,7 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn get_fn_param_names(&self, id: DefIndex) -> Vec<ast::Name> {
-        let param_names = match self.entry(id).kind {
+        let param_names = match self.kind(id) {
             EntryKind::Fn(data) |
             EntryKind::ForeignFn(data) => data.decode(self).param_names,
             EntryKind::Method(data) => data.decode(self).fn_data.param_names,
@@ -1176,7 +1192,7 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn get_rendered_const(&self, id: DefIndex) -> String {
-        match self.entry(id).kind {
+        match self.kind(id) {
             EntryKind::Const(_, data) |
             EntryKind::AssocConst(_, _, data) => data.decode(self).0,
             _ => bug!(),
@@ -1184,15 +1200,14 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn get_macro(&self, id: DefIndex) -> MacroDef {
-        let entry = self.entry(id);
-        match entry.kind {
+        match self.kind(id) {
             EntryKind::MacroDef(macro_def) => macro_def.decode(self),
             _ => bug!(),
         }
     }
 
     crate fn is_const_fn_raw(&self, id: DefIndex) -> bool {
-        let constness = match self.entry(id).kind {
+        let constness = match self.kind(id) {
             EntryKind::Method(data) => data.decode(self).fn_data.constness,
             EntryKind::Fn(data) => data.decode(self).constness,
             EntryKind::Variant(..) | EntryKind::Struct(..) => hir::Constness::Const,
@@ -1202,16 +1217,16 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn asyncness(&self, id: DefIndex) -> hir::IsAsync {
-         match self.entry(id).kind {
+         match self.kind(id) {
             EntryKind::Fn(data) => data.decode(self).asyncness,
             EntryKind::Method(data) => data.decode(self).fn_data.asyncness,
             EntryKind::ForeignFn(data) => data.decode(self).asyncness,
-            _ => bug!("asyncness: expect functions entry."),
+            _ => bug!("asyncness: expected function kind"),
         }
     }
 
     crate fn is_foreign_item(&self, id: DefIndex) -> bool {
-        match self.entry(id).kind {
+        match self.kind(id) {
             EntryKind::ForeignImmStatic |
             EntryKind::ForeignMutStatic |
             EntryKind::ForeignFn(_) => true,
@@ -1220,7 +1235,7 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn static_mutability(&self, id: DefIndex) -> Option<hir::Mutability> {
-        match self.entry(id).kind {
+        match self.kind(id) {
             EntryKind::ImmStatic |
             EntryKind::ForeignImmStatic => Some(hir::MutImmutable),
             EntryKind::MutStatic |
@@ -1230,7 +1245,7 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     crate fn fn_sig(&self, id: DefIndex, tcx: TyCtxt<'tcx>) -> ty::PolyFnSig<'tcx> {
-        let sig = match self.entry(id).kind {
+        let sig = match self.kind(id) {
             EntryKind::Fn(data) |
             EntryKind::ForeignFn(data) => data.decode(self).sig,
             EntryKind::Method(data) => data.decode(self).fn_data.sig,
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index 03a14f88645..f1436e4c09d 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -1,5 +1,5 @@
-use crate::index::Index;
 use crate::schema::*;
+use crate::table::{FixedSizeEncoding, PerDefTable};
 
 use rustc::middle::cstore::{LinkagePreference, NativeLibrary,
                             EncodedMetadata, ForeignModule};
@@ -15,7 +15,7 @@ use rustc::middle::exported_symbols::{ExportedSymbol, SymbolExportLevel,
 use rustc::middle::lang_items;
 use rustc::mir::{self, interpret};
 use rustc::traits::specialization_graph;
-use rustc::ty::{self, Ty, TyCtxt, ReprOptions, SymbolName};
+use rustc::ty::{self, Ty, TyCtxt, SymbolName};
 use rustc::ty::codec::{self as ty_codec, TyEncoder};
 use rustc::ty::layout::VariantIdx;
 
@@ -23,11 +23,12 @@ use rustc::session::config::{self, CrateType};
 use rustc::util::nodemap::FxHashMap;
 
 use rustc_data_structures::stable_hasher::StableHasher;
+use rustc_data_structures::sync::Lrc;
 use rustc_serialize::{Encodable, Encoder, SpecializedEncoder, opaque};
 
 use std::hash::Hash;
+use std::num::NonZeroUsize;
 use std::path::Path;
-use rustc_data_structures::sync::Lrc;
 use std::u32;
 use syntax::ast;
 use syntax::attr;
@@ -46,7 +47,7 @@ struct EncodeContext<'tcx> {
     opaque: opaque::Encoder,
     tcx: TyCtxt<'tcx>,
 
-    entries_index: Index<'tcx>,
+    per_def: PerDefTables<'tcx>,
 
     lazy_state: LazyState,
     type_shorthands: FxHashMap<Ty<'tcx>, usize>,
@@ -59,6 +60,27 @@ struct EncodeContext<'tcx> {
     source_file_cache: Lrc<SourceFile>,
 }
 
+#[derive(Default)]
+struct PerDefTables<'tcx> {
+    kind: PerDefTable<Lazy<EntryKind<'tcx>>>,
+    visibility: PerDefTable<Lazy<ty::Visibility>>,
+    span: PerDefTable<Lazy<Span>>,
+    attributes: PerDefTable<Lazy<[ast::Attribute]>>,
+    children: PerDefTable<Lazy<[DefIndex]>>,
+    stability: PerDefTable<Lazy<attr::Stability>>,
+    deprecation: PerDefTable<Lazy<attr::Deprecation>>,
+
+    ty: PerDefTable<Lazy<Ty<'tcx>>>,
+    inherent_impls: PerDefTable<Lazy<[DefIndex]>>,
+    variances: PerDefTable<Lazy<[ty::Variance]>>,
+    generics: PerDefTable<Lazy<ty::Generics>>,
+    predicates: PerDefTable<Lazy<ty::GenericPredicates<'tcx>>>,
+    predicates_defined_on: PerDefTable<Lazy<ty::GenericPredicates<'tcx>>>,
+
+    mir: PerDefTable<Lazy<mir::Body<'tcx>>>,
+    promoted_mir: PerDefTable<Lazy<IndexVec<mir::Promoted, mir::Body<'tcx>>>>,
+}
+
 macro_rules! encoder_methods {
     ($($name:ident($ty:ty);)*) => {
         $(fn $name(&mut self, value: $ty) -> Result<(), Self::Error> {
@@ -97,13 +119,13 @@ impl<'tcx> Encoder for EncodeContext<'tcx> {
     }
 }
 
-impl<'tcx, T> SpecializedEncoder<Lazy<T>> for EncodeContext<'tcx> {
+impl<'tcx, T: Encodable> SpecializedEncoder<Lazy<T>> for EncodeContext<'tcx> {
     fn specialized_encode(&mut self, lazy: &Lazy<T>) -> Result<(), Self::Error> {
         self.emit_lazy_distance(*lazy)
     }
 }
 
-impl<'tcx, T> SpecializedEncoder<Lazy<[T]>> for EncodeContext<'tcx> {
+impl<'tcx, T: Encodable> SpecializedEncoder<Lazy<[T]>> for EncodeContext<'tcx> {
     fn specialized_encode(&mut self, lazy: &Lazy<[T]>) -> Result<(), Self::Error> {
         self.emit_usize(lazy.meta)?;
         if lazy.meta == 0 {
@@ -113,6 +135,15 @@ impl<'tcx, T> SpecializedEncoder<Lazy<[T]>> for EncodeContext<'tcx> {
     }
 }
 
+impl<'tcx, T> SpecializedEncoder<Lazy<PerDefTable<T>>> for EncodeContext<'tcx>
+    where Option<T>: FixedSizeEncoding,
+{
+    fn specialized_encode(&mut self, lazy: &Lazy<PerDefTable<T>>) -> Result<(), Self::Error> {
+        self.emit_usize(lazy.meta)?;
+        self.emit_lazy_distance(*lazy)
+    }
+}
+
 impl<'tcx> SpecializedEncoder<CrateNum> for EncodeContext<'tcx> {
     #[inline]
     fn specialized_encode(&mut self, cnum: &CrateNum) -> Result<(), Self::Error> {
@@ -257,7 +288,7 @@ impl<T: Encodable> EncodeContentsForLazy<T> for T {
     }
 }
 
-impl<I, T> EncodeContentsForLazy<[T]> for I
+impl<I, T: Encodable> EncodeContentsForLazy<[T]> for I
     where I: IntoIterator,
           I::Item: EncodeContentsForLazy<T>,
 {
@@ -266,15 +297,28 @@ impl<I, T> EncodeContentsForLazy<[T]> for I
     }
 }
 
+// Shorthand for `$self.$tables.$table.set($key, $self.lazy($value))`, which would
+// normally need extra variables to avoid errors about multiple mutable borrows.
+macro_rules! record {
+    ($self:ident.$tables:ident.$table:ident[$key:expr] <- $value:expr) => {{
+        {
+            let value = $value;
+            let lazy = $self.lazy(value);
+            $self.$tables.$table.set($key, lazy);
+        }
+    }}
+}
+
 impl<'tcx> EncodeContext<'tcx> {
     fn emit_lazy_distance<T: ?Sized + LazyMeta>(
         &mut self,
         lazy: Lazy<T>,
     ) -> Result<(), <Self as Encoder>::Error> {
-        let min_end = lazy.position + T::min_size(lazy.meta);
+        let min_end = lazy.position.get() + T::min_size(lazy.meta);
         let distance = match self.lazy_state {
             LazyState::NoNode => bug!("emit_lazy_distance: outside of a metadata node"),
             LazyState::NodeStart(start) => {
+                let start = start.get();
                 assert!(min_end <= start);
                 start - min_end
             }
@@ -284,10 +328,10 @@ impl<'tcx> EncodeContext<'tcx> {
                     "make sure that the calls to `lazy*` \
                     are in the same order as the metadata fields",
                 );
-                lazy.position - last_min_end
+                lazy.position.get() - last_min_end.get()
             }
         };
-        self.lazy_state = LazyState::Previous(min_end);
+        self.lazy_state = LazyState::Previous(NonZeroUsize::new(min_end).unwrap());
         self.emit_usize(distance)
     }
 
@@ -295,43 +339,22 @@ impl<'tcx> EncodeContext<'tcx> {
         &mut self,
         value: impl EncodeContentsForLazy<T>,
     ) -> Lazy<T> {
-        let pos = self.position();
+        let pos = NonZeroUsize::new(self.position()).unwrap();
 
         assert_eq!(self.lazy_state, LazyState::NoNode);
         self.lazy_state = LazyState::NodeStart(pos);
         let meta = value.encode_contents_for_lazy(self);
         self.lazy_state = LazyState::NoNode;
 
-        assert!(pos + <T>::min_size(meta) <= self.position());
+        assert!(pos.get() + <T>::min_size(meta) <= self.position());
 
         Lazy::from_position_and_meta(pos, meta)
     }
 
-    /// Emit the data for a `DefId` to the metadata. The function to
-    /// emit the data is `op`, and it will be given `data` as
-    /// arguments. This `record` function will call `op` to generate
-    /// the `Entry` (which may point to other encoded information)
-    /// and will then record the `Lazy<Entry>` for use in the index.
-    // FIXME(eddyb) remove this.
-    fn record<DATA>(
-        &mut self,
-        id: DefId,
-        op: impl FnOnce(&mut Self, DATA) -> Entry<'tcx>,
-        data: DATA,
-    ) {
-        assert!(id.is_local());
-
-        let entry = op(self, data);
-        let entry = self.lazy(entry);
-        self.entries_index.record(id, entry);
-    }
-
     fn encode_info_for_items(&mut self) {
         let krate = self.tcx.hir().krate();
         let vis = Spanned { span: syntax_pos::DUMMY_SP, node: hir::VisibilityKind::Public };
-        self.record(DefId::local(CRATE_DEF_INDEX),
-                     EncodeContext::encode_info_for_mod,
-                     (hir::CRATE_HIR_ID, &krate.module, &krate.attrs, &vis));
+        self.encode_info_for_mod(hir::CRATE_HIR_ID, &krate.module, &krate.attrs, &vis);
         krate.visit_all_item_likes(&mut self.as_deep_visitor());
         for macro_def in &krate.exported_macros {
             self.visit_macro_def(macro_def);
@@ -475,8 +498,26 @@ impl<'tcx> EncodeContext<'tcx> {
 
 
         i = self.position();
-        let entries_index = self.entries_index.write_index(&mut self.opaque);
-        let entries_index_bytes = self.position() - i;
+        let per_def = LazyPerDefTables {
+            kind: self.per_def.kind.encode(&mut self.opaque),
+            visibility: self.per_def.visibility.encode(&mut self.opaque),
+            span: self.per_def.span.encode(&mut self.opaque),
+            attributes: self.per_def.attributes.encode(&mut self.opaque),
+            children: self.per_def.children.encode(&mut self.opaque),
+            stability: self.per_def.stability.encode(&mut self.opaque),
+            deprecation: self.per_def.deprecation.encode(&mut self.opaque),
+
+            ty: self.per_def.ty.encode(&mut self.opaque),
+            inherent_impls: self.per_def.inherent_impls.encode(&mut self.opaque),
+            variances: self.per_def.variances.encode(&mut self.opaque),
+            generics: self.per_def.generics.encode(&mut self.opaque),
+            predicates: self.per_def.predicates.encode(&mut self.opaque),
+            predicates_defined_on: self.per_def.predicates_defined_on.encode(&mut self.opaque),
+
+            mir: self.per_def.mir.encode(&mut self.opaque),
+            promoted_mir: self.per_def.promoted_mir.encode(&mut self.opaque),
+        };
+        let per_def_bytes = self.position() - i;
 
         // Encode the proc macro data
         i = self.position();
@@ -535,7 +576,7 @@ impl<'tcx> EncodeContext<'tcx> {
             impls,
             exported_symbols,
             interpret_alloc_index,
-            entries_index,
+            per_def,
         });
 
         let total_bytes = self.position();
@@ -560,7 +601,7 @@ impl<'tcx> EncodeContext<'tcx> {
             println!("  def-path table bytes: {}", def_path_table_bytes);
             println!(" proc-macro-data-bytes: {}", proc_macro_data_bytes);
             println!("            item bytes: {}", item_bytes);
-            println!("   entries index bytes: {}", entries_index_bytes);
+            println!("   per-def table bytes: {}", per_def_bytes);
             println!("            zero bytes: {}", zero_bytes);
             println!("           total bytes: {}", total_bytes);
         }
@@ -570,23 +611,21 @@ impl<'tcx> EncodeContext<'tcx> {
 }
 
 impl EncodeContext<'tcx> {
-    fn encode_variances_of(&mut self, def_id: DefId) -> Lazy<[ty::Variance]> {
+    fn encode_variances_of(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_variances_of({:?})", def_id);
-        let tcx = self.tcx;
-        self.lazy(&tcx.variances_of(def_id)[..])
+        record!(self.per_def.variances[def_id] <- &self.tcx.variances_of(def_id)[..]);
     }
 
-    fn encode_item_type(&mut self, def_id: DefId) -> Lazy<Ty<'tcx>> {
-        let tcx = self.tcx;
-        let ty = tcx.type_of(def_id);
-        debug!("EncodeContext::encode_item_type({:?}) => {:?}", def_id, ty);
-        self.lazy(ty)
+    fn encode_item_type(&mut self, def_id: DefId) {
+        debug!("EncodeContext::encode_item_type({:?})", def_id);
+        record!(self.per_def.ty[def_id] <- self.tcx.type_of(def_id));
     }
 
     fn encode_enum_variant_info(
         &mut self,
-        (enum_did, index): (DefId, VariantIdx),
-    ) -> Entry<'tcx> {
+        enum_did: DefId,
+        index: VariantIdx,
+    ) {
         let tcx = self.tcx;
         let def = tcx.adt_def(enum_did);
         let variant = &def.variants[index];
@@ -608,38 +647,32 @@ impl EncodeContext<'tcx> {
         let enum_id = tcx.hir().as_local_hir_id(enum_did).unwrap();
         let enum_vis = &tcx.hir().expect_item(enum_id).vis;
 
-        Entry {
-            kind: EntryKind::Variant(self.lazy(data)),
-            visibility: self.lazy(ty::Visibility::from_hir(enum_vis, enum_id, tcx)),
-            span: self.lazy(tcx.def_span(def_id)),
-            attributes: self.encode_attributes(&tcx.get_attrs(def_id)),
-            children: self.lazy(variant.fields.iter().map(|f| {
-                assert!(f.did.is_local());
-                f.did.index
-            })),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: Lazy::empty(),
-            variances: if variant.ctor_kind == CtorKind::Fn {
-                self.encode_variances_of(def_id)
-            } else {
-                Lazy::empty()
-            },
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-            predicates_defined_on: None,
-
-            mir: self.encode_optimized_mir(def_id),
-            promoted_mir: self.encode_promoted_mir(def_id),
+        record!(self.per_def.kind[def_id] <- EntryKind::Variant(self.lazy(data)));
+        record!(self.per_def.visibility[def_id] <-
+            ty::Visibility::from_hir(enum_vis, enum_id, self.tcx));
+        record!(self.per_def.span[def_id] <- self.tcx.def_span(def_id));
+        record!(self.per_def.attributes[def_id] <- &self.tcx.get_attrs(def_id)[..]);
+        record!(self.per_def.children[def_id] <- variant.fields.iter().map(|f| {
+            assert!(f.did.is_local());
+            f.did.index
+        }));
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
+        self.encode_item_type(def_id);
+        if variant.ctor_kind == CtorKind::Fn {
+            self.encode_variances_of(def_id);
         }
+        self.encode_generics(def_id);
+        self.encode_predicates(def_id);
+        self.encode_optimized_mir(def_id);
+        self.encode_promoted_mir(def_id);
     }
 
     fn encode_enum_variant_ctor(
         &mut self,
-        (enum_did, index): (DefId, VariantIdx),
-    ) -> Entry<'tcx> {
+        enum_did: DefId,
+        index: VariantIdx,
+    ) {
         let tcx = self.tcx;
         let def = tcx.adt_def(enum_did);
         let variant = &def.variants[index];
@@ -666,35 +699,28 @@ impl EncodeContext<'tcx> {
             ctor_vis = ty::Visibility::Restricted(DefId::local(CRATE_DEF_INDEX));
         }
 
-        Entry {
-            kind: EntryKind::Variant(self.lazy(data)),
-            visibility: self.lazy(ctor_vis),
-            span: self.lazy(tcx.def_span(def_id)),
-            attributes: Lazy::empty(),
-            children: Lazy::empty(),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: Lazy::empty(),
-            variances: if variant.ctor_kind == CtorKind::Fn {
-                self.encode_variances_of(def_id)
-            } else {
-                Lazy::empty()
-            },
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-            predicates_defined_on: None,
-
-            mir: self.encode_optimized_mir(def_id),
-            promoted_mir: self.encode_promoted_mir(def_id),
+        record!(self.per_def.kind[def_id] <- EntryKind::Variant(self.lazy(data)));
+        record!(self.per_def.visibility[def_id] <- ctor_vis);
+        record!(self.per_def.span[def_id] <- self.tcx.def_span(def_id));
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
+        self.encode_item_type(def_id);
+        if variant.ctor_kind == CtorKind::Fn {
+            self.encode_variances_of(def_id);
         }
+        self.encode_generics(def_id);
+        self.encode_predicates(def_id);
+        self.encode_optimized_mir(def_id);
+        self.encode_promoted_mir(def_id);
     }
 
     fn encode_info_for_mod(
         &mut self,
-        (id, md, attrs, vis): (hir::HirId, &hir::Mod, &[ast::Attribute], &hir::Visibility),
-    ) -> Entry<'tcx> {
+        id: hir::HirId,
+        md: &hir::Mod,
+        attrs: &[ast::Attribute],
+        vis: &hir::Visibility,
+    ) {
         let tcx = self.tcx;
         let def_id = tcx.hir().local_def_id(id);
         debug!("EncodeContext::encode_info_for_mod({:?})", def_id);
@@ -706,33 +732,23 @@ impl EncodeContext<'tcx> {
             },
         };
 
-        Entry {
-            kind: EntryKind::Mod(self.lazy(data)),
-            visibility: self.lazy(ty::Visibility::from_hir(vis, id, tcx)),
-            span: self.lazy(tcx.def_span(def_id)),
-            attributes: self.encode_attributes(attrs),
-            children: self.lazy(md.item_ids.iter().map(|item_id| {
-                tcx.hir().local_def_id(item_id.id).index
-            })),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: None,
-            inherent_impls: Lazy::empty(),
-            variances: Lazy::empty(),
-            generics: None,
-            predicates: None,
-            predicates_defined_on: None,
-
-            mir: None,
-            promoted_mir: None,
-        }
+        record!(self.per_def.kind[def_id] <- EntryKind::Mod(self.lazy(data)));
+        record!(self.per_def.visibility[def_id] <- ty::Visibility::from_hir(vis, id, self.tcx));
+        record!(self.per_def.span[def_id] <- self.tcx.def_span(def_id));
+        record!(self.per_def.attributes[def_id] <- attrs);
+        record!(self.per_def.children[def_id] <- md.item_ids.iter().map(|item_id| {
+            tcx.hir().local_def_id(item_id.id).index
+        }));
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
     }
 
     fn encode_field(
         &mut self,
-        (adt_def_id, variant_index, field_index): (DefId, VariantIdx, usize),
-    ) -> Entry<'tcx> {
+        adt_def_id: DefId,
+        variant_index: VariantIdx,
+        field_index: usize,
+    ) {
         let tcx = self.tcx;
         let variant = &tcx.adt_def(adt_def_id).variants[variant_index];
         let field = &variant.fields[field_index];
@@ -743,28 +759,18 @@ impl EncodeContext<'tcx> {
         let variant_id = tcx.hir().as_local_hir_id(variant.def_id).unwrap();
         let variant_data = tcx.hir().expect_variant_data(variant_id);
 
-        Entry {
-            kind: EntryKind::Field,
-            visibility: self.lazy(field.vis),
-            span: self.lazy(tcx.def_span(def_id)),
-            attributes: self.encode_attributes(&variant_data.fields()[field_index].attrs),
-            children: Lazy::empty(),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: Lazy::empty(),
-            variances: Lazy::empty(),
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-            predicates_defined_on: None,
-
-            mir: None,
-            promoted_mir: None,
-        }
+        record!(self.per_def.kind[def_id] <- EntryKind::Field);
+        record!(self.per_def.visibility[def_id] <- field.vis);
+        record!(self.per_def.span[def_id] <- self.tcx.def_span(def_id));
+        record!(self.per_def.attributes[def_id] <- &variant_data.fields()[field_index].attrs);
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
+        self.encode_item_type(def_id);
+        self.encode_generics(def_id);
+        self.encode_predicates(def_id);
     }
 
-    fn encode_struct_ctor(&mut self, (adt_def_id, def_id): (DefId, DefId)) -> Entry<'tcx> {
+    fn encode_struct_ctor(&mut self, adt_def_id: DefId, def_id: DefId) {
         debug!("EncodeContext::encode_struct_ctor({:?})", def_id);
         let tcx = self.tcx;
         let adt_def = tcx.adt_def(adt_def_id);
@@ -798,52 +804,38 @@ impl EncodeContext<'tcx> {
             ctor_vis = ty::Visibility::Restricted(DefId::local(CRATE_DEF_INDEX));
         }
 
-        let repr_options = get_repr_options(tcx, adt_def_id);
-
-        Entry {
-            kind: EntryKind::Struct(self.lazy(data), repr_options),
-            visibility: self.lazy(ctor_vis),
-            span: self.lazy(tcx.def_span(def_id)),
-            attributes: Lazy::empty(),
-            children: Lazy::empty(),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: Lazy::empty(),
-            variances: if variant.ctor_kind == CtorKind::Fn {
-                self.encode_variances_of(def_id)
-            } else {
-                Lazy::empty()
-            },
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-            predicates_defined_on: None,
-
-            mir: self.encode_optimized_mir(def_id),
-            promoted_mir: self.encode_promoted_mir(def_id),
+        record!(self.per_def.kind[def_id] <- EntryKind::Struct(self.lazy(data), adt_def.repr));
+        record!(self.per_def.visibility[def_id] <- ctor_vis);
+        record!(self.per_def.span[def_id] <- self.tcx.def_span(def_id));
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
+        self.encode_item_type(def_id);
+        if variant.ctor_kind == CtorKind::Fn {
+            self.encode_variances_of(def_id);
         }
+        self.encode_generics(def_id);
+        self.encode_predicates(def_id);
+        self.encode_optimized_mir(def_id);
+        self.encode_promoted_mir(def_id);
     }
 
-    fn encode_generics(&mut self, def_id: DefId) -> Lazy<ty::Generics> {
+    fn encode_generics(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_generics({:?})", def_id);
-        let tcx = self.tcx;
-        self.lazy(tcx.generics_of(def_id))
+        record!(self.per_def.generics[def_id] <- self.tcx.generics_of(def_id));
     }
 
-    fn encode_predicates(&mut self, def_id: DefId) -> Lazy<ty::GenericPredicates<'tcx>> {
+    fn encode_predicates(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_predicates({:?})", def_id);
-        let tcx = self.tcx;
-        self.lazy(&*tcx.predicates_of(def_id))
+        record!(self.per_def.predicates[def_id] <- &*self.tcx.predicates_of(def_id));
     }
 
-    fn encode_predicates_defined_on(&mut self, def_id: DefId) -> Lazy<ty::GenericPredicates<'tcx>> {
+    fn encode_predicates_defined_on(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_predicates_defined_on({:?})", def_id);
-        let tcx = self.tcx;
-        self.lazy(&*tcx.predicates_defined_on(def_id))
+        record!(self.per_def.predicates_defined_on[def_id] <-
+            &*self.tcx.predicates_defined_on(def_id))
     }
 
-    fn encode_info_for_trait_item(&mut self, def_id: DefId) -> Entry<'tcx> {
+    fn encode_info_for_trait_item(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_info_for_trait_item({:?})", def_id);
         let tcx = self.tcx;
 
@@ -860,7 +852,7 @@ impl EncodeContext<'tcx> {
                 span_bug!(ast_item.span, "traits cannot have final items"),
         };
 
-        let kind = match trait_item.kind {
+        record!(self.per_def.kind[def_id] <- match trait_item.kind {
             ty::AssocKind::Const => {
                 let rendered =
                     hir::print::to_string(self.tcx.hir(), |s| s.print_trait_item(ast_item));
@@ -869,7 +861,7 @@ impl EncodeContext<'tcx> {
                 EntryKind::AssocConst(container, ConstQualif { mir: 0 }, rendered_const)
             }
             ty::AssocKind::Method => {
-                let fn_data = if let hir::TraitItemKind::Method(method_sig, m) = &ast_item.kind {
+                let fn_data = if let hir::TraitItemKind::Method(m_sig, m) = &ast_item.kind {
                     let param_names = match *m {
                         hir::TraitMethod::Required(ref names) => {
                             self.encode_fn_param_names(names)
@@ -879,10 +871,10 @@ impl EncodeContext<'tcx> {
                         }
                     };
                     FnData {
-                        asyncness: method_sig.header.asyncness,
+                        asyncness: m_sig.header.asyncness,
                         constness: hir::Constness::NotConst,
                         param_names,
-                        sig: self.lazy(&tcx.fn_sig(def_id)),
+                        sig: self.lazy(tcx.fn_sig(def_id)),
                     }
                 } else {
                     bug!()
@@ -895,44 +887,31 @@ impl EncodeContext<'tcx> {
             }
             ty::AssocKind::Type => EntryKind::AssocType(container),
             ty::AssocKind::OpaqueTy => span_bug!(ast_item.span, "opaque type in trait"),
-        };
-
-        Entry {
-            kind,
-            visibility: self.lazy(trait_item.vis),
-            span: self.lazy(ast_item.span),
-            attributes: self.encode_attributes(&ast_item.attrs),
-            children: Lazy::empty(),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: match trait_item.kind {
-                ty::AssocKind::Const |
-                ty::AssocKind::Method => {
-                    Some(self.encode_item_type(def_id))
-                }
-                ty::AssocKind::Type => {
-                    if trait_item.defaultness.has_value() {
-                        Some(self.encode_item_type(def_id))
-                    } else {
-                        None
-                    }
+        });
+        record!(self.per_def.visibility[def_id] <- trait_item.vis);
+        record!(self.per_def.span[def_id] <- ast_item.span);
+        record!(self.per_def.attributes[def_id] <- &ast_item.attrs);
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
+        match trait_item.kind {
+            ty::AssocKind::Const |
+            ty::AssocKind::Method => {
+                self.encode_item_type(def_id);
+            }
+            ty::AssocKind::Type => {
+                if trait_item.defaultness.has_value() {
+                    self.encode_item_type(def_id);
                 }
-                ty::AssocKind::OpaqueTy => unreachable!(),
-            },
-            inherent_impls: Lazy::empty(),
-            variances: if trait_item.kind == ty::AssocKind::Method {
-                self.encode_variances_of(def_id)
-            } else {
-                Lazy::empty()
-            },
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-            predicates_defined_on: None,
-
-            mir: self.encode_optimized_mir(def_id),
-            promoted_mir: self.encode_promoted_mir(def_id),
+            }
+            ty::AssocKind::OpaqueTy => unreachable!(),
+        }
+        if trait_item.kind == ty::AssocKind::Method {
+            self.encode_variances_of(def_id);
         }
+        self.encode_generics(def_id);
+        self.encode_predicates(def_id);
+        self.encode_optimized_mir(def_id);
+        self.encode_promoted_mir(def_id);
     }
 
     fn metadata_output_only(&self) -> bool {
@@ -940,7 +919,7 @@ impl EncodeContext<'tcx> {
         !self.tcx.sess.opts.output_types.should_codegen()
     }
 
-    fn encode_info_for_impl_item(&mut self, def_id: DefId) -> Entry<'tcx> {
+    fn encode_info_for_impl_item(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_info_for_impl_item({:?})", def_id);
         let tcx = self.tcx;
 
@@ -955,7 +934,7 @@ impl EncodeContext<'tcx> {
                 span_bug!(ast_item.span, "impl items always have values (currently)"),
         };
 
-        let kind = match impl_item.kind {
+        record!(self.per_def.kind[def_id] <- match impl_item.kind {
             ty::AssocKind::Const => {
                 if let hir::ImplItemKind::Const(_, body_id) = ast_item.kind {
                     let mir = self.tcx.at(ast_item.span).mir_const_qualif(def_id).0;
@@ -973,7 +952,7 @@ impl EncodeContext<'tcx> {
                         asyncness: sig.header.asyncness,
                         constness: sig.header.constness,
                         param_names: self.encode_fn_param_names_for_body(body),
-                        sig: self.lazy(&tcx.fn_sig(def_id)),
+                        sig: self.lazy(tcx.fn_sig(def_id)),
                     }
                 } else {
                     bug!()
@@ -986,8 +965,18 @@ impl EncodeContext<'tcx> {
             }
             ty::AssocKind::OpaqueTy => EntryKind::AssocOpaqueTy(container),
             ty::AssocKind::Type => EntryKind::AssocType(container)
-        };
-
+        });
+        record!(self.per_def.visibility[def_id] <- impl_item.vis);
+        record!(self.per_def.span[def_id] <- ast_item.span);
+        record!(self.per_def.attributes[def_id] <- &ast_item.attrs);
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
+        self.encode_item_type(def_id);
+        if impl_item.kind == ty::AssocKind::Method {
+            self.encode_variances_of(def_id);
+        }
+        self.encode_generics(def_id);
+        self.encode_predicates(def_id);
         let mir = match ast_item.kind {
             hir::ImplItemKind::Const(..) => true,
             hir::ImplItemKind::Method(ref sig, _) => {
@@ -1002,29 +991,9 @@ impl EncodeContext<'tcx> {
             hir::ImplItemKind::OpaqueTy(..) |
             hir::ImplItemKind::TyAlias(..) => false,
         };
-
-        Entry {
-            kind,
-            visibility: self.lazy(impl_item.vis),
-            span: self.lazy(ast_item.span),
-            attributes: self.encode_attributes(&ast_item.attrs),
-            children: Lazy::empty(),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: Lazy::empty(),
-            variances: if impl_item.kind == ty::AssocKind::Method {
-                self.encode_variances_of(def_id)
-            } else {
-                Lazy::empty()
-            },
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-            predicates_defined_on: None,
-
-            mir: if mir { self.encode_optimized_mir(def_id) } else { None },
-            promoted_mir: if mir { self.encode_promoted_mir(def_id) } else { None },
+        if mir {
+            self.encode_optimized_mir(def_id);
+            self.encode_promoted_mir(def_id);
         }
     }
 
@@ -1045,51 +1014,44 @@ impl EncodeContext<'tcx> {
         self.lazy(param_names.iter().map(|ident| ident.name))
     }
 
-    fn encode_optimized_mir(&mut self, def_id: DefId) -> Option<Lazy<mir::Body<'tcx>>> {
+    fn encode_optimized_mir(&mut self, def_id: DefId) {
         debug!("EntryBuilder::encode_mir({:?})", def_id);
         if self.tcx.mir_keys(LOCAL_CRATE).contains(&def_id) {
-            let mir = self.tcx.optimized_mir(def_id);
-            Some(self.lazy(mir))
-        } else {
-            None
+            record!(self.per_def.mir[def_id] <- self.tcx.optimized_mir(def_id));
         }
     }
 
-    fn encode_promoted_mir(
-        &mut self,
-        def_id: DefId,
-    ) -> Option<Lazy<IndexVec<mir::Promoted, mir::Body<'tcx>>>> {
+    fn encode_promoted_mir(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_promoted_mir({:?})", def_id);
         if self.tcx.mir_keys(LOCAL_CRATE).contains(&def_id) {
-            let promoted = self.tcx.promoted_mir(def_id);
-            Some(self.lazy(promoted))
-        } else {
-            None
+            record!(self.per_def.promoted_mir[def_id] <- self.tcx.promoted_mir(def_id));
         }
     }
 
     // Encodes the inherent implementations of a structure, enumeration, or trait.
-    fn encode_inherent_implementations(&mut self, def_id: DefId) -> Lazy<[DefIndex]> {
+    fn encode_inherent_implementations(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_inherent_implementations({:?})", def_id);
         let implementations = self.tcx.inherent_impls(def_id);
-        if implementations.is_empty() {
-            Lazy::empty()
-        } else {
-            self.lazy(implementations.iter().map(|&def_id| {
+        if !implementations.is_empty() {
+            record!(self.per_def.inherent_impls[def_id] <- implementations.iter().map(|&def_id| {
                 assert!(def_id.is_local());
                 def_id.index
-            }))
+            }));
         }
     }
 
-    fn encode_stability(&mut self, def_id: DefId) -> Option<Lazy<attr::Stability>> {
+    fn encode_stability(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_stability({:?})", def_id);
-        self.tcx.lookup_stability(def_id).map(|stab| self.lazy(stab))
+        if let Some(stab) = self.tcx.lookup_stability(def_id) {
+            record!(self.per_def.stability[def_id] <- stab)
+        }
     }
 
-    fn encode_deprecation(&mut self, def_id: DefId) -> Option<Lazy<attr::Deprecation>> {
+    fn encode_deprecation(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_deprecation({:?})", def_id);
-        self.tcx.lookup_deprecation(def_id).map(|depr| self.lazy(depr))
+        if let Some(depr) = self.tcx.lookup_deprecation(def_id) {
+            record!(self.per_def.deprecation[def_id] <- depr);
+        }
     }
 
     fn encode_rendered_const_for_body(&mut self, body_id: hir::BodyId) -> Lazy<RenderedConst> {
@@ -1099,16 +1061,16 @@ impl EncodeContext<'tcx> {
         self.lazy(rendered_const)
     }
 
-    fn encode_info_for_item(&mut self, (def_id, item): (DefId, &'tcx hir::Item)) -> Entry<'tcx> {
+    fn encode_info_for_item(&mut self, def_id: DefId, item: &'tcx hir::Item) {
         let tcx = self.tcx;
 
         debug!("EncodeContext::encode_info_for_item({:?})", def_id);
 
-        let kind = match item.kind {
+        record!(self.per_def.kind[def_id] <- match item.kind {
             hir::ItemKind::Static(_, hir::MutMutable, _) => EntryKind::MutStatic,
             hir::ItemKind::Static(_, hir::MutImmutable, _) => EntryKind::ImmStatic,
             hir::ItemKind::Const(_, body_id) => {
-                let mir = tcx.at(item.span).mir_const_qualif(def_id).0;
+                let mir = self.tcx.at(item.span).mir_const_qualif(def_id).0;
                 EntryKind::Const(
                     ConstQualif { mir },
                     self.encode_rendered_const_for_body(body_id)
@@ -1125,48 +1087,48 @@ impl EncodeContext<'tcx> {
                 EntryKind::Fn(self.lazy(data))
             }
             hir::ItemKind::Mod(ref m) => {
-                return self.encode_info_for_mod((item.hir_id, m, &item.attrs, &item.vis));
+                return self.encode_info_for_mod(item.hir_id, m, &item.attrs, &item.vis);
             }
             hir::ItemKind::ForeignMod(_) => EntryKind::ForeignMod,
             hir::ItemKind::GlobalAsm(..) => EntryKind::GlobalAsm,
             hir::ItemKind::TyAlias(..) => EntryKind::Type,
             hir::ItemKind::OpaqueTy(..) => EntryKind::OpaqueTy,
-            hir::ItemKind::Enum(..) => EntryKind::Enum(get_repr_options(tcx, def_id)),
+            hir::ItemKind::Enum(..) => EntryKind::Enum(self.tcx.adt_def(def_id).repr),
             hir::ItemKind::Struct(ref struct_def, _) => {
-                let variant = tcx.adt_def(def_id).non_enum_variant();
+                let adt_def = self.tcx.adt_def(def_id);
+                let variant = adt_def.non_enum_variant();
 
                 // Encode def_ids for each field and method
                 // for methods, write all the stuff get_trait_method
                 // needs to know
-                let ctor = struct_def.ctor_hir_id()
-                    .map(|ctor_hir_id| tcx.hir().local_def_id(ctor_hir_id).index);
-
-                let repr_options = get_repr_options(tcx, def_id);
+                let ctor = struct_def.ctor_hir_id().map(|ctor_hir_id| {
+                    self.tcx.hir().local_def_id(ctor_hir_id).index
+                });
 
                 EntryKind::Struct(self.lazy(VariantData {
                     ctor_kind: variant.ctor_kind,
                     discr: variant.discr,
                     ctor,
                     ctor_sig: None,
-                }), repr_options)
+                }), adt_def.repr)
             }
             hir::ItemKind::Union(..) => {
-                let variant = tcx.adt_def(def_id).non_enum_variant();
-                let repr_options = get_repr_options(tcx, def_id);
+                let adt_def = self.tcx.adt_def(def_id);
+                let variant = adt_def.non_enum_variant();
 
                 EntryKind::Union(self.lazy(VariantData {
                     ctor_kind: variant.ctor_kind,
                     discr: variant.discr,
                     ctor: None,
                     ctor_sig: None,
-                }), repr_options)
+                }), adt_def.repr)
             }
             hir::ItemKind::Impl(_, _, defaultness, ..) => {
-                let trait_ref = tcx.impl_trait_ref(def_id);
-                let polarity = tcx.impl_polarity(def_id);
+                let trait_ref = self.tcx.impl_trait_ref(def_id);
+                let polarity = self.tcx.impl_polarity(def_id);
                 let parent = if let Some(trait_ref) = trait_ref {
-                    let trait_def = tcx.trait_def(trait_ref.def_id);
-                    trait_def.ancestors(tcx, def_id).nth(1).and_then(|node| {
+                    let trait_def = self.tcx.trait_def(trait_ref.def_id);
+                    trait_def.ancestors(self.tcx, def_id).nth(1).and_then(|node| {
                         match node {
                             specialization_graph::Node::Impl(parent) => Some(parent),
                             _ => None,
@@ -1180,8 +1142,8 @@ impl EncodeContext<'tcx> {
                 // "unsized info", else just store None
                 let coerce_unsized_info =
                     trait_ref.and_then(|t| {
-                        if Some(t.def_id) == tcx.lang_items().coerce_unsized_trait() {
-                            Some(tcx.at(item.span).coerce_unsized_info(def_id))
+                        if Some(t.def_id) == self.tcx.lang_items().coerce_unsized_trait() {
+                            Some(self.tcx.at(item.span).coerce_unsized_info(def_id))
                         } else {
                             None
                         }
@@ -1198,11 +1160,11 @@ impl EncodeContext<'tcx> {
                 EntryKind::Impl(self.lazy(data))
             }
             hir::ItemKind::Trait(..) => {
-                let trait_def = tcx.trait_def(def_id);
+                let trait_def = self.tcx.trait_def(def_id);
                 let data = TraitData {
                     unsafety: trait_def.unsafety,
                     paren_sugar: trait_def.paren_sugar,
-                    has_auto_impl: tcx.trait_is_auto(def_id),
+                    has_auto_impl: self.tcx.trait_is_auto(def_id),
                     is_marker: trait_def.is_marker,
                     super_predicates: self.lazy(&*tcx.super_predicates_of(def_id)),
                 };
@@ -1218,7 +1180,95 @@ impl EncodeContext<'tcx> {
             }
             hir::ItemKind::ExternCrate(_) |
             hir::ItemKind::Use(..) => bug!("cannot encode info for item {:?}", item),
-        };
+        });
+        record!(self.per_def.visibility[def_id] <-
+            ty::Visibility::from_hir(&item.vis, item.hir_id, tcx));
+        record!(self.per_def.span[def_id] <- item.span);
+        record!(self.per_def.attributes[def_id] <- &item.attrs);
+        // FIXME(eddyb) there should be a nicer way to do this.
+        match item.kind {
+            hir::ItemKind::ForeignMod(ref fm) => record!(self.per_def.children[def_id] <-
+                fm.items
+                    .iter()
+                    .map(|foreign_item| tcx.hir().local_def_id(
+                        foreign_item.hir_id).index)
+            ),
+            hir::ItemKind::Enum(..) => record!(self.per_def.children[def_id] <-
+                self.tcx.adt_def(def_id).variants.iter().map(|v| {
+                    assert!(v.def_id.is_local());
+                    v.def_id.index
+                })
+            ),
+            hir::ItemKind::Struct(..) |
+            hir::ItemKind::Union(..) => record!(self.per_def.children[def_id] <-
+                self.tcx.adt_def(def_id).non_enum_variant().fields.iter().map(|f| {
+                    assert!(f.did.is_local());
+                    f.did.index
+                })
+            ),
+            hir::ItemKind::Impl(..) |
+            hir::ItemKind::Trait(..) => {
+                let associated_item_def_ids = self.tcx.associated_item_def_ids(def_id);
+                record!(self.per_def.children[def_id] <-
+                    associated_item_def_ids.iter().map(|&def_id| {
+                        assert!(def_id.is_local());
+                        def_id.index
+                    })
+                );
+            }
+            _ => {}
+        }
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
+        match item.kind {
+            hir::ItemKind::Static(..) |
+            hir::ItemKind::Const(..) |
+            hir::ItemKind::Fn(..) |
+            hir::ItemKind::TyAlias(..) |
+            hir::ItemKind::OpaqueTy(..) |
+            hir::ItemKind::Enum(..) |
+            hir::ItemKind::Struct(..) |
+            hir::ItemKind::Union(..) |
+            hir::ItemKind::Impl(..) => self.encode_item_type(def_id),
+            _ => {}
+        }
+        self.encode_inherent_implementations(def_id);
+        match item.kind {
+            hir::ItemKind::Enum(..) |
+            hir::ItemKind::Struct(..) |
+            hir::ItemKind::Union(..) |
+            hir::ItemKind::Fn(..) => self.encode_variances_of(def_id),
+            _ => {}
+        }
+        match item.kind {
+            hir::ItemKind::Static(..) |
+            hir::ItemKind::Const(..) |
+            hir::ItemKind::Fn(..) |
+            hir::ItemKind::TyAlias(..) |
+            hir::ItemKind::Enum(..) |
+            hir::ItemKind::Struct(..) |
+            hir::ItemKind::Union(..) |
+            hir::ItemKind::Impl(..) |
+            hir::ItemKind::OpaqueTy(..) |
+            hir::ItemKind::Trait(..) |
+            hir::ItemKind::TraitAlias(..) => {
+                self.encode_generics(def_id);
+                self.encode_predicates(def_id);
+            }
+            _ => {}
+        }
+        // The only time that `predicates_defined_on` is used (on
+        // an external item) is for traits, during chalk lowering,
+        // so only encode it in that case as an efficiency
+        // hack. (No reason not to expand it in the future if
+        // necessary.)
+        match item.kind {
+            hir::ItemKind::Trait(..) |
+            hir::ItemKind::TraitAlias(..) => {
+                self.encode_predicates_defined_on(def_id);
+            }
+            _ => {} // not *wrong* for other kinds of items, but not needed
+        }
 
         let mir = match item.kind {
             hir::ItemKind::Static(..) | hir::ItemKind::Const(..) => true,
@@ -1233,188 +1283,48 @@ impl EncodeContext<'tcx> {
             }
             _ => false,
         };
-
-        Entry {
-            kind,
-            visibility: self.lazy(ty::Visibility::from_hir(&item.vis, item.hir_id, tcx)),
-            span: self.lazy(item.span),
-            attributes: self.encode_attributes(&item.attrs),
-            children: match item.kind {
-                hir::ItemKind::ForeignMod(ref fm) => {
-                    self.lazy(fm.items
-                        .iter()
-                        .map(|foreign_item| tcx.hir().local_def_id(
-                            foreign_item.hir_id).index))
-                }
-                hir::ItemKind::Enum(..) => {
-                    let def = self.tcx.adt_def(def_id);
-                    self.lazy(def.variants.iter().map(|v| {
-                        assert!(v.def_id.is_local());
-                        v.def_id.index
-                    }))
-                }
-                hir::ItemKind::Struct(..) |
-                hir::ItemKind::Union(..) => {
-                    let def = self.tcx.adt_def(def_id);
-                    self.lazy(def.non_enum_variant().fields.iter().map(|f| {
-                        assert!(f.did.is_local());
-                        f.did.index
-                    }))
-                }
-                hir::ItemKind::Impl(..) |
-                hir::ItemKind::Trait(..) => {
-                    self.lazy(tcx.associated_item_def_ids(def_id).iter().map(|&def_id| {
-                        assert!(def_id.is_local());
-                        def_id.index
-                    }))
-                }
-                _ => Lazy::empty(),
-            },
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: match item.kind {
-                hir::ItemKind::Static(..) |
-                hir::ItemKind::Const(..) |
-                hir::ItemKind::Fn(..) |
-                hir::ItemKind::TyAlias(..) |
-                hir::ItemKind::OpaqueTy(..) |
-                hir::ItemKind::Enum(..) |
-                hir::ItemKind::Struct(..) |
-                hir::ItemKind::Union(..) |
-                hir::ItemKind::Impl(..) => Some(self.encode_item_type(def_id)),
-                _ => None,
-            },
-            inherent_impls: self.encode_inherent_implementations(def_id),
-            variances: match item.kind {
-                hir::ItemKind::Enum(..) |
-                hir::ItemKind::Struct(..) |
-                hir::ItemKind::Union(..) |
-                hir::ItemKind::Fn(..) => self.encode_variances_of(def_id),
-                _ => Lazy::empty(),
-            },
-            generics: match item.kind {
-                hir::ItemKind::Static(..) |
-                hir::ItemKind::Const(..) |
-                hir::ItemKind::Fn(..) |
-                hir::ItemKind::TyAlias(..) |
-                hir::ItemKind::Enum(..) |
-                hir::ItemKind::Struct(..) |
-                hir::ItemKind::Union(..) |
-                hir::ItemKind::Impl(..) |
-                hir::ItemKind::OpaqueTy(..) |
-                hir::ItemKind::Trait(..) => Some(self.encode_generics(def_id)),
-                hir::ItemKind::TraitAlias(..) => Some(self.encode_generics(def_id)),
-                _ => None,
-            },
-            predicates: match item.kind {
-                hir::ItemKind::Static(..) |
-                hir::ItemKind::Const(..) |
-                hir::ItemKind::Fn(..) |
-                hir::ItemKind::TyAlias(..) |
-                hir::ItemKind::Enum(..) |
-                hir::ItemKind::Struct(..) |
-                hir::ItemKind::Union(..) |
-                hir::ItemKind::Impl(..) |
-                hir::ItemKind::OpaqueTy(..) |
-                hir::ItemKind::Trait(..) |
-                hir::ItemKind::TraitAlias(..) => Some(self.encode_predicates(def_id)),
-                _ => None,
-            },
-
-            // The only time that `predicates_defined_on` is used (on
-            // an external item) is for traits, during chalk lowering,
-            // so only encode it in that case as an efficiency
-            // hack. (No reason not to expand it in the future if
-            // necessary.)
-            predicates_defined_on: match item.kind {
-                hir::ItemKind::Trait(..) |
-                hir::ItemKind::TraitAlias(..) => Some(self.encode_predicates_defined_on(def_id)),
-                _ => None, // not *wrong* for other kinds of items, but not needed
-            },
-
-            mir: if mir { self.encode_optimized_mir(def_id) } else { None },
-            promoted_mir: if mir { self.encode_promoted_mir(def_id) } else { None },
+        if mir {
+            self.encode_optimized_mir(def_id);
+            self.encode_promoted_mir(def_id);
         }
     }
 
     /// Serialize the text of exported macros
-    fn encode_info_for_macro_def(&mut self, macro_def: &hir::MacroDef) -> Entry<'tcx> {
+    fn encode_info_for_macro_def(&mut self, macro_def: &hir::MacroDef) {
         use syntax::print::pprust;
         let def_id = self.tcx.hir().local_def_id(macro_def.hir_id);
-        Entry {
-            kind: EntryKind::MacroDef(self.lazy(MacroDef {
-                body: pprust::tts_to_string(macro_def.body.clone()),
-                legacy: macro_def.legacy,
-            })),
-            visibility: self.lazy(ty::Visibility::Public),
-            span: self.lazy(macro_def.span),
-            attributes: self.encode_attributes(&macro_def.attrs),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            children: Lazy::empty(),
-            ty: None,
-            inherent_impls: Lazy::empty(),
-            variances: Lazy::empty(),
-            generics: None,
-            predicates: None,
-            predicates_defined_on: None,
-            mir: None,
-            promoted_mir: None,
-        }
+        record!(self.per_def.kind[def_id] <- EntryKind::MacroDef(self.lazy(MacroDef {
+            body: pprust::tts_to_string(macro_def.body.clone()),
+            legacy: macro_def.legacy,
+        })));
+        record!(self.per_def.visibility[def_id] <- ty::Visibility::Public);
+        record!(self.per_def.span[def_id] <- macro_def.span);
+        record!(self.per_def.attributes[def_id] <- &macro_def.attrs);
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
     }
 
     fn encode_info_for_generic_param(
         &mut self,
         def_id: DefId,
-        entry_kind: EntryKind<'tcx>,
+        kind: EntryKind<'tcx>,
         encode_type: bool,
-    ) -> Entry<'tcx> {
-        let tcx = self.tcx;
-        Entry {
-            kind: entry_kind,
-            visibility: self.lazy(ty::Visibility::Public),
-            span: self.lazy(tcx.def_span(def_id)),
-            attributes: Lazy::empty(),
-            children: Lazy::empty(),
-            stability: None,
-            deprecation: None,
-            ty: if encode_type { Some(self.encode_item_type(def_id)) } else { None },
-            inherent_impls: Lazy::empty(),
-            variances: Lazy::empty(),
-            generics: None,
-            predicates: None,
-            predicates_defined_on: None,
-
-            mir: None,
-            promoted_mir: None,
+    ) {
+        record!(self.per_def.kind[def_id] <- kind);
+        record!(self.per_def.visibility[def_id] <- ty::Visibility::Public);
+        record!(self.per_def.span[def_id] <- self.tcx.def_span(def_id));
+        if encode_type {
+            self.encode_item_type(def_id);
         }
     }
 
-    fn encode_info_for_ty_param(
-        &mut self,
-        (def_id, encode_type): (DefId, bool),
-    ) -> Entry<'tcx> {
-        debug!("EncodeContext::encode_info_for_ty_param({:?})", def_id);
-        self.encode_info_for_generic_param(def_id, EntryKind::TypeParam, encode_type)
-    }
-
-    fn encode_info_for_const_param(
-        &mut self,
-        def_id: DefId,
-    ) -> Entry<'tcx> {
-        debug!("EncodeContext::encode_info_for_const_param({:?})", def_id);
-        self.encode_info_for_generic_param(def_id, EntryKind::ConstParam, true)
-    }
-
-    fn encode_info_for_closure(&mut self, def_id: DefId) -> Entry<'tcx> {
+    fn encode_info_for_closure(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_info_for_closure({:?})", def_id);
-        let tcx = self.tcx;
 
         let tables = self.tcx.typeck_tables_of(def_id);
         let hir_id = self.tcx.hir().as_local_hir_id(def_id).unwrap();
-        let kind = match tables.node_type(hir_id).kind {
+
+        record!(self.per_def.kind[def_id] <- match tables.node_type(hir_id).kind {
             ty::Generator(def_id, ..) => {
                 let layout = self.tcx.generator_layout(def_id);
                 let data = GeneratorData {
@@ -1429,61 +1339,32 @@ impl EncodeContext<'tcx> {
                 EntryKind::Closure(self.lazy(data))
             }
 
-            _ => bug!("closure that is neither generator nor closure")
-        };
-
-        Entry {
-            kind,
-            visibility: self.lazy(ty::Visibility::Public),
-            span: self.lazy(tcx.def_span(def_id)),
-            attributes: self.encode_attributes(&tcx.get_attrs(def_id)),
-            children: Lazy::empty(),
-            stability: None,
-            deprecation: None,
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: Lazy::empty(),
-            variances: Lazy::empty(),
-            generics: Some(self.encode_generics(def_id)),
-            predicates: None,
-            predicates_defined_on: None,
-
-            mir: self.encode_optimized_mir(def_id),
-            promoted_mir: self.encode_promoted_mir(def_id),
-        }
+            _ => bug!("closure that is neither generator nor closure"),
+        });
+        record!(self.per_def.visibility[def_id] <- ty::Visibility::Public);
+        record!(self.per_def.span[def_id] <- self.tcx.def_span(def_id));
+        record!(self.per_def.attributes[def_id] <- &self.tcx.get_attrs(def_id)[..]);
+        self.encode_item_type(def_id);
+        self.encode_generics(def_id);
+        self.encode_optimized_mir(def_id);
+        self.encode_promoted_mir(def_id);
     }
 
-    fn encode_info_for_anon_const(&mut self, def_id: DefId) -> Entry<'tcx> {
+    fn encode_info_for_anon_const(&mut self, def_id: DefId) {
         debug!("EncodeContext::encode_info_for_anon_const({:?})", def_id);
-        let tcx = self.tcx;
-        let id = tcx.hir().as_local_hir_id(def_id).unwrap();
-        let body_id = tcx.hir().body_owned_by(id);
+        let id = self.tcx.hir().as_local_hir_id(def_id).unwrap();
+        let body_id = self.tcx.hir().body_owned_by(id);
         let const_data = self.encode_rendered_const_for_body(body_id);
-        let mir = tcx.mir_const_qualif(def_id).0;
-
-        Entry {
-            kind: EntryKind::Const(ConstQualif { mir }, const_data),
-            visibility: self.lazy(ty::Visibility::Public),
-            span: self.lazy(tcx.def_span(def_id)),
-            attributes: Lazy::empty(),
-            children: Lazy::empty(),
-            stability: None,
-            deprecation: None,
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: Lazy::empty(),
-            variances: Lazy::empty(),
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-            predicates_defined_on: None,
-
-            mir: self.encode_optimized_mir(def_id),
-            promoted_mir: self.encode_promoted_mir(def_id),
-        }
-    }
+        let mir = self.tcx.mir_const_qualif(def_id).0;
 
-    fn encode_attributes(&mut self, attrs: &[ast::Attribute]) -> Lazy<[ast::Attribute]> {
-        self.lazy(attrs)
+        record!(self.per_def.kind[def_id] <- EntryKind::Const(ConstQualif { mir }, const_data));
+        record!(self.per_def.visibility[def_id] <- ty::Visibility::Public);
+        record!(self.per_def.span[def_id] <- self.tcx.def_span(def_id));
+        self.encode_item_type(def_id);
+        self.encode_generics(def_id);
+        self.encode_predicates(def_id);
+        self.encode_optimized_mir(def_id);
+        self.encode_promoted_mir(def_id);
     }
 
     fn encode_native_libraries(&mut self) -> Lazy<[NativeLibrary]> {
@@ -1657,14 +1538,16 @@ impl EncodeContext<'tcx> {
         Lazy::empty()
     }
 
-    fn encode_info_for_foreign_item(&mut self,
-                                    (def_id, nitem): (DefId, &hir::ForeignItem))
-                                    -> Entry<'tcx> {
+    fn encode_info_for_foreign_item(
+        &mut self,
+        def_id: DefId,
+        nitem: &hir::ForeignItem,
+    )  {
         let tcx = self.tcx;
 
         debug!("EncodeContext::encode_info_for_foreign_item({:?})", def_id);
 
-        let kind = match nitem.kind {
+        record!(self.per_def.kind[def_id] <- match nitem.kind {
             hir::ForeignItemKind::Fn(_, ref names, _) => {
                 let data = FnData {
                     asyncness: hir::IsAsync::NotAsync,
@@ -1677,33 +1560,23 @@ impl EncodeContext<'tcx> {
             hir::ForeignItemKind::Static(_, hir::MutMutable) => EntryKind::ForeignMutStatic,
             hir::ForeignItemKind::Static(_, hir::MutImmutable) => EntryKind::ForeignImmStatic,
             hir::ForeignItemKind::Type => EntryKind::ForeignType,
-        };
-
-        Entry {
-            kind,
-            visibility: self.lazy(ty::Visibility::from_hir(&nitem.vis, nitem.hir_id, tcx)),
-            span: self.lazy(nitem.span),
-            attributes: self.encode_attributes(&nitem.attrs),
-            children: Lazy::empty(),
-            stability: self.encode_stability(def_id),
-            deprecation: self.encode_deprecation(def_id),
-
-            ty: Some(self.encode_item_type(def_id)),
-            inherent_impls: Lazy::empty(),
-            variances: match nitem.kind {
-                hir::ForeignItemKind::Fn(..) => self.encode_variances_of(def_id),
-                _ => Lazy::empty(),
-            },
-            generics: Some(self.encode_generics(def_id)),
-            predicates: Some(self.encode_predicates(def_id)),
-            predicates_defined_on: None,
-
-            mir: None,
-            promoted_mir: None,
+        });
+        record!(self.per_def.visibility[def_id] <-
+            ty::Visibility::from_hir(&nitem.vis, nitem.hir_id, self.tcx));
+        record!(self.per_def.span[def_id] <- nitem.span);
+        record!(self.per_def.attributes[def_id] <- &nitem.attrs);
+        self.encode_stability(def_id);
+        self.encode_deprecation(def_id);
+        self.encode_item_type(def_id);
+        if let hir::ForeignItemKind::Fn(..) = nitem.kind {
+            self.encode_variances_of(def_id);
         }
+        self.encode_generics(def_id);
+        self.encode_predicates(def_id);
     }
 }
 
+// FIXME(eddyb) make metadata encoding walk over all definitions, instead of HIR.
 impl Visitor<'tcx> for EncodeContext<'tcx> {
     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
         NestedVisitorMap::OnlyBodies(&self.tcx.hir())
@@ -1715,7 +1588,7 @@ impl Visitor<'tcx> for EncodeContext<'tcx> {
     fn visit_anon_const(&mut self, c: &'tcx AnonConst) {
         intravisit::walk_anon_const(self, c);
         let def_id = self.tcx.hir().local_def_id(c.hir_id);
-        self.record(def_id, EncodeContext::encode_info_for_anon_const, def_id);
+        self.encode_info_for_anon_const(def_id);
     }
     fn visit_item(&mut self, item: &'tcx hir::Item) {
         intravisit::walk_item(self, item);
@@ -1723,24 +1596,21 @@ impl Visitor<'tcx> for EncodeContext<'tcx> {
         match item.kind {
             hir::ItemKind::ExternCrate(_) |
             hir::ItemKind::Use(..) => {} // ignore these
-            _ => self.record(def_id, EncodeContext::encode_info_for_item, (def_id, item)),
+            _ => self.encode_info_for_item(def_id, item),
         }
         self.encode_addl_info_for_item(item);
     }
     fn visit_foreign_item(&mut self, ni: &'tcx hir::ForeignItem) {
         intravisit::walk_foreign_item(self, ni);
         let def_id = self.tcx.hir().local_def_id(ni.hir_id);
-        self.record(def_id,
-                          EncodeContext::encode_info_for_foreign_item,
-                          (def_id, ni));
+        self.encode_info_for_foreign_item(def_id, ni);
     }
     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
         intravisit::walk_generics(self, generics);
         self.encode_info_for_generics(generics);
     }
     fn visit_macro_def(&mut self, macro_def: &'tcx hir::MacroDef) {
-        let def_id = self.tcx.hir().local_def_id(macro_def.hir_id);
-        self.record(def_id, EncodeContext::encode_info_for_macro_def, macro_def);
+        self.encode_info_for_macro_def(macro_def);
     }
 }
 
@@ -1748,10 +1618,10 @@ impl EncodeContext<'tcx> {
     fn encode_fields(&mut self, adt_def_id: DefId) {
         let def = self.tcx.adt_def(adt_def_id);
         for (variant_index, variant) in def.variants.iter_enumerated() {
-            for (field_index, field) in variant.fields.iter().enumerate() {
-                self.record(field.did,
-                            EncodeContext::encode_field,
-                            (adt_def_id, variant_index, field_index));
+            for (field_index, _field) in variant.fields.iter().enumerate() {
+                // FIXME(eddyb) `adt_def_id` is leftover from incremental isolation,
+                // pass `def`, `variant` or `field` instead.
+                self.encode_field(adt_def_id, variant_index, field_index);
             }
         }
     }
@@ -1762,14 +1632,14 @@ impl EncodeContext<'tcx> {
             match param.kind {
                 GenericParamKind::Lifetime { .. } => continue,
                 GenericParamKind::Type { ref default, .. } => {
-                    self.record(
+                    self.encode_info_for_generic_param(
                         def_id,
-                        EncodeContext::encode_info_for_ty_param,
-                        (def_id, default.is_some()),
+                        EntryKind::TypeParam,
+                        default.is_some(),
                     );
                 }
                 GenericParamKind::Const { .. } => {
-                    self.record(def_id, EncodeContext::encode_info_for_const_param, def_id);
+                    self.encode_info_for_generic_param(def_id, EntryKind::ConstParam, true);
                 }
             }
         }
@@ -1779,7 +1649,7 @@ impl EncodeContext<'tcx> {
         match expr.kind {
             hir::ExprKind::Closure(..) => {
                 let def_id = self.tcx.hir().local_def_id(expr.hir_id);
-                self.record(def_id, EncodeContext::encode_info_for_closure, def_id);
+                self.encode_info_for_closure(def_id);
             }
             _ => {}
         }
@@ -1810,14 +1680,14 @@ impl EncodeContext<'tcx> {
 
                 let def = self.tcx.adt_def(def_id);
                 for (i, variant) in def.variants.iter_enumerated() {
-                    self.record(variant.def_id,
-                                EncodeContext::encode_enum_variant_info,
-                                (def_id, i));
-
-                    if let Some(ctor_def_id) = variant.ctor_def_id {
-                        self.record(ctor_def_id,
-                                    EncodeContext::encode_enum_variant_ctor,
-                                    (def_id, i));
+                    // FIXME(eddyb) `def_id` is leftover from incremental isolation,
+                    // pass `def` or `variant` instead.
+                    self.encode_enum_variant_info(def_id, i);
+
+                    // FIXME(eddyb) `def_id` is leftover from incremental isolation,
+                    // pass `def`, `variant` or `ctor_def_id` instead.
+                    if let Some(_ctor_def_id) = variant.ctor_def_id {
+                        self.encode_enum_variant_ctor(def_id, i);
                     }
                 }
             }
@@ -1827,9 +1697,7 @@ impl EncodeContext<'tcx> {
                 // If the struct has a constructor, encode it.
                 if let Some(ctor_hir_id) = struct_def.ctor_hir_id() {
                     let ctor_def_id = self.tcx.hir().local_def_id(ctor_hir_id);
-                    self.record(ctor_def_id,
-                                EncodeContext::encode_struct_ctor,
-                                (def_id, ctor_def_id));
+                    self.encode_struct_ctor(def_id, ctor_def_id);
                 }
             }
             hir::ItemKind::Union(..) => {
@@ -1837,16 +1705,12 @@ impl EncodeContext<'tcx> {
             }
             hir::ItemKind::Impl(..) => {
                 for &trait_item_def_id in self.tcx.associated_item_def_ids(def_id).iter() {
-                    self.record(trait_item_def_id,
-                                EncodeContext::encode_info_for_impl_item,
-                                trait_item_def_id);
+                    self.encode_info_for_impl_item(trait_item_def_id);
                 }
             }
             hir::ItemKind::Trait(..) => {
                 for &item_def_id in self.tcx.associated_item_def_ids(def_id).iter() {
-                    self.record(item_def_id,
-                                EncodeContext::encode_info_for_trait_item,
-                                item_def_id);
+                    self.encode_info_for_trait_item(item_def_id);
                 }
             }
         }
@@ -1914,7 +1778,7 @@ crate fn encode_metadata(tcx: TyCtxt<'_>) -> EncodedMetadata {
         let mut ecx = EncodeContext {
             opaque: encoder,
             tcx,
-            entries_index: Index::new(tcx.hir().definitions().def_index_count()),
+            per_def: Default::default(),
             lazy_state: LazyState::NoNode,
             type_shorthands: Default::default(),
             predicate_shorthands: Default::default(),
@@ -1934,7 +1798,7 @@ crate fn encode_metadata(tcx: TyCtxt<'_>) -> EncodedMetadata {
 
     // Encode the root position.
     let header = METADATA_HEADER.len();
-    let pos = root.position;
+    let pos = root.position.get();
     result[header + 0] = (pos >> 24) as u8;
     result[header + 1] = (pos >> 16) as u8;
     result[header + 2] = (pos >> 8) as u8;
@@ -1942,11 +1806,3 @@ crate fn encode_metadata(tcx: TyCtxt<'_>) -> EncodedMetadata {
 
     EncodedMetadata { raw_data: result }
 }
-
-fn get_repr_options(tcx: TyCtxt<'_>, did: DefId) -> ReprOptions {
-    let ty = tcx.type_of(did);
-    match ty.kind {
-        ty::Adt(ref def, _) => return def.repr,
-        _ => bug!("{} is not an ADT", ty),
-    }
-}
diff --git a/src/librustc_metadata/index.rs b/src/librustc_metadata/index.rs
deleted file mode 100644
index 037f9d35630..00000000000
--- a/src/librustc_metadata/index.rs
+++ /dev/null
@@ -1,141 +0,0 @@
-use crate::schema::*;
-
-use rustc::hir::def_id::{DefId, DefIndex};
-use rustc_serialize::opaque::Encoder;
-use std::marker::PhantomData;
-use std::u32;
-use log::debug;
-
-/// Helper trait, for encoding to, and decoding from, a fixed number of bytes.
-trait FixedSizeEncoding {
-    const BYTE_LEN: usize;
-
-    // FIXME(eddyb) convert to and from `[u8; Self::BYTE_LEN]` instead,
-    // once that starts being allowed by the compiler (i.e. lazy normalization).
-    fn from_bytes(b: &[u8]) -> Self;
-    fn write_to_bytes(self, b: &mut [u8]);
-
-    // FIXME(eddyb) make these generic functions, or at least defaults here.
-    // (same problem as above, needs `[u8; Self::BYTE_LEN]`)
-    // For now, a macro (`fixed_size_encoding_byte_len_and_defaults`) is used.
-    fn read_from_bytes_at(b: &[u8], i: usize) -> Self;
-    fn write_to_bytes_at(self, b: &mut [u8], i: usize);
-}
-
-// HACK(eddyb) this shouldn't be needed (see comments on the methods above).
-macro_rules! fixed_size_encoding_byte_len_and_defaults {
-    ($byte_len:expr) => {
-        const BYTE_LEN: usize = $byte_len;
-        fn read_from_bytes_at(b: &[u8], i: usize) -> Self {
-            const BYTE_LEN: usize = $byte_len;
-            // HACK(eddyb) ideally this would be done with fully safe code,
-            // but slicing `[u8]` with `i * N..` is optimized worse, due to the
-            // possibility of `i * N` overflowing, than indexing `[[u8; N]]`.
-            let b = unsafe {
-                std::slice::from_raw_parts(
-                    b.as_ptr() as *const [u8; BYTE_LEN],
-                    b.len() / BYTE_LEN,
-                )
-            };
-            Self::from_bytes(&b[i])
-        }
-        fn write_to_bytes_at(self, b: &mut [u8], i: usize) {
-            const BYTE_LEN: usize = $byte_len;
-            // HACK(eddyb) ideally this would be done with fully safe code,
-            // see similar comment in `read_from_bytes_at` for why it can't yet.
-            let b = unsafe {
-                std::slice::from_raw_parts_mut(
-                    b.as_mut_ptr() as *mut [u8; BYTE_LEN],
-                    b.len() / BYTE_LEN,
-                )
-            };
-            self.write_to_bytes(&mut b[i]);
-        }
-    }
-}
-
-impl FixedSizeEncoding for u32 {
-    fixed_size_encoding_byte_len_and_defaults!(4);
-
-    fn from_bytes(b: &[u8]) -> Self {
-        let mut bytes = [0; Self::BYTE_LEN];
-        bytes.copy_from_slice(&b[..Self::BYTE_LEN]);
-        Self::from_le_bytes(bytes)
-    }
-
-    fn write_to_bytes(self, b: &mut [u8]) {
-        b[..Self::BYTE_LEN].copy_from_slice(&self.to_le_bytes());
-    }
-}
-
-/// While we are generating the metadata, we also track the position
-/// of each DefIndex. It is not required that all definitions appear
-/// in the metadata, nor that they are serialized in order, and
-/// therefore we first allocate the vector here and fill it with
-/// `u32::MAX`. Whenever an index is visited, we fill in the
-/// appropriate spot by calling `record_position`. We should never
-/// visit the same index twice.
-crate struct Index<'tcx> {
-    positions: Vec<u8>,
-    _marker: PhantomData<&'tcx ()>,
-}
-
-impl Index<'tcx> {
-    crate fn new(max_index: usize) -> Self {
-        Index {
-            positions: vec![0xff; max_index * 4],
-            _marker: PhantomData,
-        }
-    }
-
-    crate fn record(&mut self, def_id: DefId, entry: Lazy<Entry<'tcx>>) {
-        assert!(def_id.is_local());
-        self.record_index(def_id.index, entry);
-    }
-
-    fn record_index(&mut self, item: DefIndex, entry: Lazy<Entry<'tcx>>) {
-        assert!(entry.position < (u32::MAX as usize));
-        let position = entry.position as u32;
-        let array_index = item.index();
-
-        let positions = &mut self.positions;
-        assert!(u32::read_from_bytes_at(positions, array_index) == u32::MAX,
-                "recorded position for item {:?} twice, first at {:?} and now at {:?}",
-                item,
-                u32::read_from_bytes_at(positions, array_index),
-                position);
-
-        position.write_to_bytes_at(positions, array_index)
-    }
-
-    crate fn write_index(&self, buf: &mut Encoder) -> Lazy<[Self]> {
-        let pos = buf.position();
-
-        // First we write the length of the lower range ...
-        buf.emit_raw_bytes(&(self.positions.len() as u32 / 4).to_le_bytes());
-        // ... then the values.
-        buf.emit_raw_bytes(&self.positions);
-        Lazy::from_position_and_meta(pos as usize, self.positions.len() / 4 + 1)
-    }
-}
-
-impl Lazy<[Index<'tcx>]> {
-    /// Given the metadata, extract out the offset of a particular
-    /// DefIndex (if any).
-    #[inline(never)]
-    crate fn lookup(&self, bytes: &[u8], def_index: DefIndex) -> Option<Lazy<Entry<'tcx>>> {
-        let bytes = &bytes[self.position..];
-        debug!("Index::lookup: index={:?} len={:?}",
-               def_index,
-               self.meta);
-
-        let position = u32::read_from_bytes_at(bytes, 1 + def_index.index());
-        if position == u32::MAX {
-            debug!("Index::lookup: position=u32::MAX");
-            None
-        } else {
-            debug!("Index::lookup: position={:?}", position);
-            Some(Lazy::from_position(position as usize))
-        }
-    }
-}
diff --git a/src/librustc_metadata/lib.rs b/src/librustc_metadata/lib.rs
index 6aa684b1c3d..291ee23ff72 100644
--- a/src/librustc_metadata/lib.rs
+++ b/src/librustc_metadata/lib.rs
@@ -26,15 +26,15 @@ extern crate rustc_data_structures;
 
 pub mod error_codes;
 
-mod index;
 mod encoder;
 mod decoder;
+mod dependency_format;
 mod cstore_impl;
-mod schema;
-mod native_libs;
-mod link_args;
 mod foreign_modules;
-mod dependency_format;
+mod link_args;
+mod native_libs;
+mod schema;
+mod table;
 
 pub mod creader;
 pub mod cstore;
diff --git a/src/librustc_metadata/schema.rs b/src/librustc_metadata/schema.rs
index d3539e71401..96f35783278 100644
--- a/src/librustc_metadata/schema.rs
+++ b/src/librustc_metadata/schema.rs
@@ -1,4 +1,4 @@
-use crate::index;
+use crate::table::PerDefTable;
 
 use rustc::hir;
 use rustc::hir::def::{self, CtorKind};
@@ -14,12 +14,14 @@ use rustc_target::spec::{PanicStrategy, TargetTriple};
 use rustc_index::vec::IndexVec;
 use rustc_data_structures::svh::Svh;
 
+use rustc_serialize::Encodable;
 use syntax::{ast, attr};
 use syntax::edition::Edition;
 use syntax::symbol::Symbol;
 use syntax_pos::{self, Span};
 
 use std::marker::PhantomData;
+use std::num::NonZeroUsize;
 
 crate fn rustc_version() -> String {
     format!("rustc {}",
@@ -52,7 +54,7 @@ crate trait LazyMeta {
     fn min_size(meta: Self::Meta) -> usize;
 }
 
-impl<T> LazyMeta for T {
+impl<T: Encodable> LazyMeta for T {
     type Meta = ();
 
     fn min_size(_: ()) -> usize {
@@ -61,7 +63,7 @@ impl<T> LazyMeta for T {
     }
 }
 
-impl<T> LazyMeta for [T] {
+impl<T: Encodable> LazyMeta for [T] {
     type Meta = usize;
 
     fn min_size(len: usize) -> usize {
@@ -102,13 +104,13 @@ crate struct Lazy<T, Meta = <T as LazyMeta>::Meta>
     where T: ?Sized + LazyMeta<Meta = Meta>,
           Meta: 'static + Copy,
 {
-    pub position: usize,
+    pub position: NonZeroUsize,
     pub meta: Meta,
     _marker: PhantomData<T>,
 }
 
 impl<T: ?Sized + LazyMeta> Lazy<T> {
-    crate fn from_position_and_meta(position: usize, meta: T::Meta) -> Lazy<T> {
+     crate fn from_position_and_meta(position: NonZeroUsize, meta: T::Meta) -> Lazy<T> {
         Lazy {
             position,
             meta,
@@ -117,15 +119,15 @@ impl<T: ?Sized + LazyMeta> Lazy<T> {
     }
 }
 
-impl<T> Lazy<T> {
-    crate fn from_position(position: usize) -> Lazy<T> {
+impl<T: Encodable> Lazy<T> {
+    crate fn from_position(position: NonZeroUsize) -> Lazy<T> {
         Lazy::from_position_and_meta(position, ())
     }
 }
 
-impl<T> Lazy<[T]> {
+impl<T: Encodable> Lazy<[T]> {
     crate fn empty() -> Lazy<[T]> {
-        Lazy::from_position_and_meta(0, 0)
+        Lazy::from_position_and_meta(NonZeroUsize::new(1).unwrap(), 0)
     }
 }
 
@@ -147,12 +149,22 @@ crate enum LazyState {
 
     /// Inside a metadata node, and before any `Lazy`.
     /// The position is that of the node itself.
-    NodeStart(usize),
+    NodeStart(NonZeroUsize),
 
     /// Inside a metadata node, with a previous `Lazy`.
     /// The position is a conservative estimate of where that
     /// previous `Lazy` would end (see their comments).
-    Previous(usize),
+    Previous(NonZeroUsize),
+}
+
+// FIXME(#59875) `Lazy!(T)` replaces `Lazy<T>`, passing the `Meta` parameter
+// manually, instead of relying on the default, to get the correct variance.
+// Only needed when `T` itself contains a parameter (e.g. `'tcx`).
+macro_rules! Lazy {
+    (Table<$T:ty>) => {Lazy<Table<$T>, usize>};
+    (PerDefTable<$T:ty>) => {Lazy<PerDefTable<$T>, usize>};
+    ([$T:ty]) => {Lazy<[$T], usize>};
+    ($T:ty) => {Lazy<$T, ()>};
 }
 
 #[derive(RustcEncodable, RustcDecodable)]
@@ -182,10 +194,10 @@ crate struct CrateRoot<'tcx> {
     pub source_map: Lazy<[syntax_pos::SourceFile]>,
     pub def_path_table: Lazy<hir::map::definitions::DefPathTable>,
     pub impls: Lazy<[TraitImpls]>,
-    pub exported_symbols: Lazy<[(ExportedSymbol<'tcx>, SymbolExportLevel)]>,
+    pub exported_symbols: Lazy!([(ExportedSymbol<'tcx>, SymbolExportLevel)]),
     pub interpret_alloc_index: Lazy<[u32]>,
 
-    pub entries_index: Lazy<[index::Index<'tcx>]>,
+    pub per_def: LazyPerDefTables<'tcx>,
 
     /// The DefIndex's of any proc macros delcared by
     /// this crate
@@ -216,24 +228,24 @@ crate struct TraitImpls {
 }
 
 #[derive(RustcEncodable, RustcDecodable)]
-crate struct Entry<'tcx> {
-    pub kind: EntryKind<'tcx>,
-    pub visibility: Lazy<ty::Visibility>,
-    pub span: Lazy<Span>,
-    pub attributes: Lazy<[ast::Attribute]>,
-    pub children: Lazy<[DefIndex]>,
-    pub stability: Option<Lazy<attr::Stability>>,
-    pub deprecation: Option<Lazy<attr::Deprecation>>,
-
-    pub ty: Option<Lazy<Ty<'tcx>>>,
-    pub inherent_impls: Lazy<[DefIndex]>,
-    pub variances: Lazy<[ty::Variance]>,
-    pub generics: Option<Lazy<ty::Generics>>,
-    pub predicates: Option<Lazy<ty::GenericPredicates<'tcx>>>,
-    pub predicates_defined_on: Option<Lazy<ty::GenericPredicates<'tcx>>>,
-
-    pub mir: Option<Lazy<mir::Body<'tcx>>>,
-    pub promoted_mir: Option<Lazy<IndexVec<mir::Promoted, mir::Body<'tcx>>>>,
+crate struct LazyPerDefTables<'tcx> {
+    pub kind: Lazy!(PerDefTable<Lazy!(EntryKind<'tcx>)>),
+    pub visibility: Lazy!(PerDefTable<Lazy<ty::Visibility>>),
+    pub span: Lazy!(PerDefTable<Lazy<Span>>),
+    pub attributes: Lazy!(PerDefTable<Lazy<[ast::Attribute]>>),
+    pub children: Lazy!(PerDefTable<Lazy<[DefIndex]>>),
+    pub stability: Lazy!(PerDefTable<Lazy<attr::Stability>>),
+    pub deprecation: Lazy!(PerDefTable<Lazy<attr::Deprecation>>),
+
+    pub ty: Lazy!(PerDefTable<Lazy!(Ty<'tcx>)>),
+    pub inherent_impls: Lazy!(PerDefTable<Lazy<[DefIndex]>>),
+    pub variances: Lazy!(PerDefTable<Lazy<[ty::Variance]>>),
+    pub generics: Lazy!(PerDefTable<Lazy<ty::Generics>>),
+    pub predicates: Lazy!(PerDefTable<Lazy!(ty::GenericPredicates<'tcx>)>),
+    pub predicates_defined_on: Lazy!(PerDefTable<Lazy!(ty::GenericPredicates<'tcx>)>),
+
+    pub mir: Lazy!(PerDefTable<Lazy!(mir::Body<'tcx>)>),
+    pub promoted_mir: Lazy!(PerDefTable<Lazy!(IndexVec<mir::Promoted, mir::Body<'tcx>>)>),
 }
 
 #[derive(Copy, Clone, RustcEncodable, RustcDecodable)]
@@ -252,22 +264,22 @@ crate enum EntryKind<'tcx> {
     OpaqueTy,
     Enum(ReprOptions),
     Field,
-    Variant(Lazy<VariantData<'tcx>>),
-    Struct(Lazy<VariantData<'tcx>>, ReprOptions),
-    Union(Lazy<VariantData<'tcx>>, ReprOptions),
-    Fn(Lazy<FnData<'tcx>>),
-    ForeignFn(Lazy<FnData<'tcx>>),
+    Variant(Lazy!(VariantData<'tcx>)),
+    Struct(Lazy!(VariantData<'tcx>), ReprOptions),
+    Union(Lazy!(VariantData<'tcx>), ReprOptions),
+    Fn(Lazy!(FnData<'tcx>)),
+    ForeignFn(Lazy!(FnData<'tcx>)),
     Mod(Lazy<ModData>),
     MacroDef(Lazy<MacroDef>),
-    Closure(Lazy<ClosureData<'tcx>>),
-    Generator(Lazy<GeneratorData<'tcx>>),
-    Trait(Lazy<TraitData<'tcx>>),
-    Impl(Lazy<ImplData<'tcx>>),
-    Method(Lazy<MethodData<'tcx>>),
+    Closure(Lazy!(ClosureData<'tcx>)),
+    Generator(Lazy!(GeneratorData<'tcx>)),
+    Trait(Lazy!(TraitData<'tcx>)),
+    Impl(Lazy!(ImplData<'tcx>)),
+    Method(Lazy!(MethodData<'tcx>)),
     AssocType(AssocContainer),
     AssocOpaqueTy(AssocContainer),
     AssocConst(AssocContainer, ConstQualif, Lazy<RenderedConst>),
-    TraitAlias(Lazy<TraitAliasData<'tcx>>),
+    TraitAlias(Lazy!(TraitAliasData<'tcx>)),
 }
 
 /// Additional data for EntryKind::Const and EntryKind::AssocConst
@@ -297,7 +309,7 @@ crate struct FnData<'tcx> {
     pub asyncness: hir::IsAsync,
     pub constness: hir::Constness,
     pub param_names: Lazy<[ast::Name]>,
-    pub sig: Lazy<ty::PolyFnSig<'tcx>>,
+    pub sig: Lazy!(ty::PolyFnSig<'tcx>),
 }
 
 #[derive(RustcEncodable, RustcDecodable)]
@@ -308,7 +320,7 @@ crate struct VariantData<'tcx> {
     pub ctor: Option<DefIndex>,
     /// If this is a tuple struct or variant
     /// ctor, this is its "function" signature.
-    pub ctor_sig: Option<Lazy<ty::PolyFnSig<'tcx>>>,
+    pub ctor_sig: Option<Lazy!(ty::PolyFnSig<'tcx>)>,
 }
 
 #[derive(RustcEncodable, RustcDecodable)]
@@ -317,12 +329,12 @@ crate struct TraitData<'tcx> {
     pub paren_sugar: bool,
     pub has_auto_impl: bool,
     pub is_marker: bool,
-    pub super_predicates: Lazy<ty::GenericPredicates<'tcx>>,
+    pub super_predicates: Lazy!(ty::GenericPredicates<'tcx>),
 }
 
 #[derive(RustcEncodable, RustcDecodable)]
 crate struct TraitAliasData<'tcx> {
-    pub super_predicates: Lazy<ty::GenericPredicates<'tcx>>,
+    pub super_predicates: Lazy!(ty::GenericPredicates<'tcx>),
 }
 
 #[derive(RustcEncodable, RustcDecodable)]
@@ -333,7 +345,7 @@ crate struct ImplData<'tcx> {
 
     /// This is `Some` only for impls of `CoerceUnsized`.
     pub coerce_unsized_info: Option<ty::adjustment::CoerceUnsizedInfo>,
-    pub trait_ref: Option<Lazy<ty::TraitRef<'tcx>>>,
+    pub trait_ref: Option<Lazy!(ty::TraitRef<'tcx>)>,
 }
 
 
@@ -384,7 +396,7 @@ crate struct MethodData<'tcx> {
 
 #[derive(RustcEncodable, RustcDecodable)]
 crate struct ClosureData<'tcx> {
-    pub sig: Lazy<ty::PolyFnSig<'tcx>>,
+    pub sig: Lazy!(ty::PolyFnSig<'tcx>),
 }
 
 #[derive(RustcEncodable, RustcDecodable)]
diff --git a/src/librustc_metadata/table.rs b/src/librustc_metadata/table.rs
new file mode 100644
index 00000000000..e164c28c953
--- /dev/null
+++ b/src/librustc_metadata/table.rs
@@ -0,0 +1,239 @@
+use crate::decoder::Metadata;
+use crate::schema::*;
+
+use rustc::hir::def_id::{DefId, DefIndex};
+use rustc_serialize::{Encodable, opaque::Encoder};
+use std::convert::TryInto;
+use std::marker::PhantomData;
+use std::num::NonZeroUsize;
+use log::debug;
+
+/// Helper trait, for encoding to, and decoding from, a fixed number of bytes.
+/// Used mainly for Lazy positions and lengths.
+/// Unchecked invariant: `Self::default()` should encode as `[0; BYTE_LEN]`,
+/// but this has no impact on safety.
+crate trait FixedSizeEncoding: Default {
+    const BYTE_LEN: usize;
+
+    // FIXME(eddyb) convert to and from `[u8; Self::BYTE_LEN]` instead,
+    // once that starts being allowed by the compiler (i.e. lazy normalization).
+    fn from_bytes(b: &[u8]) -> Self;
+    fn write_to_bytes(self, b: &mut [u8]);
+
+    // FIXME(eddyb) make these generic functions, or at least defaults here.
+    // (same problem as above, needs `[u8; Self::BYTE_LEN]`)
+    // For now, a macro (`fixed_size_encoding_byte_len_and_defaults`) is used.
+
+    /// Read a `Self` value (encoded as `Self::BYTE_LEN` bytes),
+    /// from `&b[i * Self::BYTE_LEN..]`, returning `None` if `i`
+    /// is not in bounds, or `Some(Self::from_bytes(...))` otherwise.
+    fn maybe_read_from_bytes_at(b: &[u8], i: usize) -> Option<Self>;
+    /// Write a `Self` value (encoded as `Self::BYTE_LEN` bytes),
+    /// at `&mut b[i * Self::BYTE_LEN..]`, using `Self::write_to_bytes`.
+    fn write_to_bytes_at(self, b: &mut [u8], i: usize);
+}
+
+// HACK(eddyb) this shouldn't be needed (see comments on the methods above).
+macro_rules! fixed_size_encoding_byte_len_and_defaults {
+    ($byte_len:expr) => {
+        const BYTE_LEN: usize = $byte_len;
+        fn maybe_read_from_bytes_at(b: &[u8], i: usize) -> Option<Self> {
+            const BYTE_LEN: usize = $byte_len;
+            // HACK(eddyb) ideally this would be done with fully safe code,
+            // but slicing `[u8]` with `i * N..` is optimized worse, due to the
+            // possibility of `i * N` overflowing, than indexing `[[u8; N]]`.
+            let b = unsafe {
+                std::slice::from_raw_parts(
+                    b.as_ptr() as *const [u8; BYTE_LEN],
+                    b.len() / BYTE_LEN,
+                )
+            };
+            b.get(i).map(|b| FixedSizeEncoding::from_bytes(b))
+        }
+        fn write_to_bytes_at(self, b: &mut [u8], i: usize) {
+            const BYTE_LEN: usize = $byte_len;
+            // HACK(eddyb) ideally this would be done with fully safe code,
+            // see similar comment in `read_from_bytes_at` for why it can't yet.
+            let b = unsafe {
+                std::slice::from_raw_parts_mut(
+                    b.as_mut_ptr() as *mut [u8; BYTE_LEN],
+                    b.len() / BYTE_LEN,
+                )
+            };
+            self.write_to_bytes(&mut b[i]);
+        }
+    }
+}
+
+impl FixedSizeEncoding for u32 {
+    fixed_size_encoding_byte_len_and_defaults!(4);
+
+    fn from_bytes(b: &[u8]) -> Self {
+        let mut bytes = [0; Self::BYTE_LEN];
+        bytes.copy_from_slice(&b[..Self::BYTE_LEN]);
+        Self::from_le_bytes(bytes)
+    }
+
+    fn write_to_bytes(self, b: &mut [u8]) {
+        b[..Self::BYTE_LEN].copy_from_slice(&self.to_le_bytes());
+    }
+}
+
+// NOTE(eddyb) there could be an impl for `usize`, which would enable a more
+// generic `Lazy<T>` impl, but in the general case we might not need / want to
+// fit every `usize` in `u32`.
+impl<T: Encodable> FixedSizeEncoding for Option<Lazy<T>> {
+    fixed_size_encoding_byte_len_and_defaults!(u32::BYTE_LEN);
+
+    fn from_bytes(b: &[u8]) -> Self {
+        Some(Lazy::from_position(NonZeroUsize::new(u32::from_bytes(b) as usize)?))
+    }
+
+    fn write_to_bytes(self, b: &mut [u8]) {
+        let position = self.map_or(0, |lazy| lazy.position.get());
+        let position: u32 = position.try_into().unwrap();
+
+        position.write_to_bytes(b)
+    }
+}
+
+impl<T: Encodable> FixedSizeEncoding for Option<Lazy<[T]>> {
+    fixed_size_encoding_byte_len_and_defaults!(u32::BYTE_LEN * 2);
+
+    fn from_bytes(b: &[u8]) -> Self {
+        Some(Lazy::from_position_and_meta(
+            <Option<Lazy<T>>>::from_bytes(b)?.position,
+            u32::from_bytes(&b[u32::BYTE_LEN..]) as usize,
+        ))
+    }
+
+    fn write_to_bytes(self, b: &mut [u8]) {
+        self.map(|lazy| Lazy::<T>::from_position(lazy.position))
+            .write_to_bytes(b);
+
+        let len = self.map_or(0, |lazy| lazy.meta);
+        let len: u32 = len.try_into().unwrap();
+
+        len.write_to_bytes(&mut b[u32::BYTE_LEN..]);
+    }
+}
+
+/// Random-access table (i.e. offeringconstant-time `get`/`set`), similar to
+/// `Vec<Option<T>>`, but without requiring encoding or decoding all the values
+/// eagerly and in-order.
+/// A total of `(max_idx + 1) * <Option<T> as FixedSizeEncoding>::BYTE_LEN` bytes
+/// are used for a table, where `max_idx` is the largest index passed to `set`.
+// FIXME(eddyb) replace `Vec` with `[_]` here, such that `Box<Table<T>>` would be used
+// when building it, and `Lazy<Table<T>>` or `&Table<T>` when reading it.
+// (not sure if that is possible given that the `Vec` is being resized now)
+crate struct Table<T> where Option<T>: FixedSizeEncoding {
+    // FIXME(eddyb) store `[u8; <Option<T>>::BYTE_LEN]` instead of `u8` in `Vec`,
+    // once that starts being allowed by the compiler (i.e. lazy normalization).
+    bytes: Vec<u8>,
+    _marker: PhantomData<T>,
+}
+
+impl<T> Default for Table<T> where Option<T>: FixedSizeEncoding {
+    fn default() -> Self {
+        Table {
+            bytes: vec![],
+            _marker: PhantomData,
+        }
+    }
+}
+
+impl<T> Table<T> where Option<T>: FixedSizeEncoding {
+    crate fn set(&mut self, i: usize, value: T) {
+        // FIXME(eddyb) investigate more compact encodings for sparse tables.
+        // On the PR @michaelwoerister mentioned:
+        // > Space requirements could perhaps be optimized by using the HAMT `popcnt`
+        // > trick (i.e. divide things into buckets of 32 or 64 items and then
+        // > store bit-masks of which item in each bucket is actually serialized).
+        let needed = (i + 1) * <Option<T>>::BYTE_LEN;
+        if self.bytes.len() < needed {
+            self.bytes.resize(needed, 0);
+        }
+
+        Some(value).write_to_bytes_at(&mut self.bytes, i);
+    }
+
+    crate fn encode(&self, buf: &mut Encoder) -> Lazy<Self> {
+        let pos = buf.position();
+        buf.emit_raw_bytes(&self.bytes);
+        Lazy::from_position_and_meta(
+            NonZeroUsize::new(pos as usize).unwrap(),
+            self.bytes.len(),
+        )
+    }
+}
+
+impl<T> LazyMeta for Table<T> where Option<T>: FixedSizeEncoding {
+    type Meta = usize;
+
+    fn min_size(len: usize) -> usize {
+        len
+    }
+}
+
+impl<T> Lazy<Table<T>> where Option<T>: FixedSizeEncoding {
+    /// Given the metadata, extract out the value at a particular index (if any).
+    #[inline(never)]
+    crate fn get<'a, 'tcx, M: Metadata<'a, 'tcx>>(
+        &self,
+        metadata: M,
+        i: usize,
+    ) -> Option<T> {
+        debug!("Table::lookup: index={:?} len={:?}", i, self.meta);
+
+        let start = self.position.get();
+        let bytes = &metadata.raw_bytes()[start..start + self.meta];
+        <Option<T>>::maybe_read_from_bytes_at(bytes, i)?
+    }
+}
+
+/// Like a `Table` but using `DefIndex` instead of `usize` as keys.
+// FIXME(eddyb) replace by making `Table` behave like `IndexVec`,
+// and by using `newtype_index!` to define `DefIndex`.
+crate struct PerDefTable<T>(Table<T>) where Option<T>: FixedSizeEncoding;
+
+impl<T> Default for PerDefTable<T> where Option<T>: FixedSizeEncoding {
+    fn default() -> Self {
+        PerDefTable(Table::default())
+    }
+}
+
+impl<T> PerDefTable<T> where Option<T>: FixedSizeEncoding {
+    crate fn set(&mut self, def_id: DefId, value: T) {
+        assert!(def_id.is_local());
+        self.0.set(def_id.index.index(), value);
+    }
+
+    crate fn encode(&self, buf: &mut Encoder) -> Lazy<Self> {
+        let lazy = self.0.encode(buf);
+        Lazy::from_position_and_meta(lazy.position, lazy.meta)
+    }
+}
+
+impl<T> LazyMeta for PerDefTable<T> where Option<T>: FixedSizeEncoding {
+    type Meta = <Table<T> as LazyMeta>::Meta;
+
+    fn min_size(meta: Self::Meta) -> usize {
+        Table::<T>::min_size(meta)
+    }
+}
+
+impl<T> Lazy<PerDefTable<T>> where Option<T>: FixedSizeEncoding {
+    fn as_table(&self) -> Lazy<Table<T>> {
+        Lazy::from_position_and_meta(self.position, self.meta)
+    }
+
+    /// Given the metadata, extract out the value at a particular DefIndex (if any).
+    #[inline(never)]
+    crate fn get<'a, 'tcx, M: Metadata<'a, 'tcx>>(
+        &self,
+        metadata: M,
+        def_index: DefIndex,
+    ) -> Option<T> {
+        self.as_table().get(metadata, def_index.index())
+    }
+}