Auto merge of #86461 - crlf0710:rich_vtable, r=nikomatsakis

Refactor vtable format for upcoming trait_upcasting feature.

This modifies vtable format:
1. reordering occurrence order of methods coming from different traits
2. include `VPtr`s for supertraits where this vtable cannot be directly reused during trait upcasting.
Also, during codegen, the vtables corresponding to these newly included `VPtr` will be requested and generated.

For the cases where this vtable can directly used, now the super trait vtable has exactly the same content to some prefix of this one.

r? `@bjorn3`
cc `@RalfJung`
cc `@rust-lang/wg-traits`

15 files changed, 894 insertions, 87 deletions

diff --git a/compiler/rustc_feature/src/builtin_attrs.rs b/compiler/rustc_feature/src/builtin_attrs.rs
index b1c725ecd85..36d035cdfd3 100644
--- a/compiler/rustc_feature/src/builtin_attrs.rs
+++ b/compiler/rustc_feature/src/builtin_attrs.rs
@@ -603,6 +603,7 @@ pub const BUILTIN_ATTRIBUTES: &[BuiltinAttribute] = &[
     rustc_attr!(TEST, rustc_dump_program_clauses, AssumedUsed, template!(Word)),
     rustc_attr!(TEST, rustc_dump_env_program_clauses, AssumedUsed, template!(Word)),
     rustc_attr!(TEST, rustc_object_lifetime_default, AssumedUsed, template!(Word)),
+    rustc_attr!(TEST, rustc_dump_vtable, AssumedUsed, template!(Word)),
     rustc_attr!(TEST, rustc_dummy, Normal, template!(Word /* doesn't matter*/)),
     gated!(
         omit_gdb_pretty_printer_section, AssumedUsed, template!(Word),
diff --git a/compiler/rustc_infer/src/traits/util.rs b/compiler/rustc_infer/src/traits/util.rs
index 1cde4802a40..ce1445f8a47 100644
--- a/compiler/rustc_infer/src/traits/util.rs
+++ b/compiler/rustc_infer/src/traits/util.rs
@@ -14,17 +14,17 @@ pub fn anonymize_predicate<'tcx>(
     tcx.reuse_or_mk_predicate(pred, new)
 }
 
-struct PredicateSet<'tcx> {
+pub struct PredicateSet<'tcx> {
     tcx: TyCtxt<'tcx>,
     set: FxHashSet<ty::Predicate<'tcx>>,
 }
 
 impl PredicateSet<'tcx> {
-    fn new(tcx: TyCtxt<'tcx>) -> Self {
+    pub fn new(tcx: TyCtxt<'tcx>) -> Self {
         Self { tcx, set: Default::default() }
     }
 
-    fn insert(&mut self, pred: ty::Predicate<'tcx>) -> bool {
+    pub fn insert(&mut self, pred: ty::Predicate<'tcx>) -> bool {
         // We have to be careful here because we want
         //
         //    for<'a> Foo<&'a i32>
diff --git a/compiler/rustc_middle/src/ty/vtable.rs b/compiler/rustc_middle/src/ty/vtable.rs
index 78109fc7b57..5904f133e78 100644
--- a/compiler/rustc_middle/src/ty/vtable.rs
+++ b/compiler/rustc_middle/src/ty/vtable.rs
@@ -1,17 +1,39 @@
 use std::convert::TryFrom;
+use std::fmt;
 
 use crate::mir::interpret::{alloc_range, AllocId, Allocation, Pointer, Scalar, ScalarMaybeUninit};
-use crate::ty::fold::TypeFoldable;
-use crate::ty::{self, DefId, SubstsRef, Ty, TyCtxt};
+use crate::ty::{self, Instance, PolyTraitRef, Ty, TyCtxt};
 use rustc_ast::Mutability;
 
-#[derive(Clone, Copy, Debug, PartialEq, HashStable)]
+#[derive(Clone, Copy, PartialEq, HashStable)]
 pub enum VtblEntry<'tcx> {
+    /// destructor of this type (used in vtable header)
     MetadataDropInPlace,
+    /// layout size of this type (used in vtable header)
     MetadataSize,
+    /// layout align of this type (used in vtable header)
     MetadataAlign,
+    /// non-dispatchable associated function that is excluded from trait object
     Vacant,
-    Method(DefId, SubstsRef<'tcx>),
+    /// dispatchable associated function
+    Method(Instance<'tcx>),
+    /// pointer to a separate supertrait vtable, can be used by trait upcasting coercion
+    TraitVPtr(PolyTraitRef<'tcx>),
+}
+
+impl<'tcx> fmt::Debug for VtblEntry<'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        // We want to call `Display` on `Instance` and `PolyTraitRef`,
+        // so we implement this manually.
+        match self {
+            VtblEntry::MetadataDropInPlace => write!(f, "MetadataDropInPlace"),
+            VtblEntry::MetadataSize => write!(f, "MetadataSize"),
+            VtblEntry::MetadataAlign => write!(f, "MetadataAlign"),
+            VtblEntry::Vacant => write!(f, "Vacant"),
+            VtblEntry::Method(instance) => write!(f, "Method({})", instance),
+            VtblEntry::TraitVPtr(trait_ref) => write!(f, "TraitVPtr({})", trait_ref),
+        }
+    }
 }
 
 pub const COMMON_VTABLE_ENTRIES: &[VtblEntry<'_>] =
@@ -36,11 +58,6 @@ impl<'tcx> TyCtxt<'tcx> {
         }
         drop(vtables_cache);
 
-        // See https://github.com/rust-lang/rust/pull/86475#discussion_r655162674
-        assert!(
-            !ty.needs_subst() && !poly_trait_ref.map_or(false, |trait_ref| trait_ref.needs_subst())
-        );
-        let param_env = ty::ParamEnv::reveal_all();
         let vtable_entries = if let Some(poly_trait_ref) = poly_trait_ref {
             let trait_ref = poly_trait_ref.with_self_ty(tcx, ty);
             let trait_ref = tcx.erase_regions(trait_ref);
@@ -50,8 +67,9 @@ impl<'tcx> TyCtxt<'tcx> {
             COMMON_VTABLE_ENTRIES
         };
 
-        let layout =
-            tcx.layout_of(param_env.and(ty)).expect("failed to build vtable representation");
+        let layout = tcx
+            .layout_of(ty::ParamEnv::reveal_all().and(ty))
+            .expect("failed to build vtable representation");
         assert!(!layout.is_unsized(), "can't create a vtable for an unsized type");
         let size = layout.size.bytes();
         let align = layout.align.abi.bytes();
@@ -79,19 +97,21 @@ impl<'tcx> TyCtxt<'tcx> {
                 VtblEntry::MetadataSize => Scalar::from_uint(size, ptr_size).into(),
                 VtblEntry::MetadataAlign => Scalar::from_uint(align, ptr_size).into(),
                 VtblEntry::Vacant => continue,
-                VtblEntry::Method(def_id, substs) => {
-                    // See https://github.com/rust-lang/rust/pull/86475#discussion_r655162674
-                    assert!(!substs.needs_subst());
-
+                VtblEntry::Method(instance) => {
                     // Prepare the fn ptr we write into the vtable.
-                    let instance =
-                        ty::Instance::resolve_for_vtable(tcx, param_env, *def_id, substs)
-                            .expect("resolution failed during building vtable representation")
-                            .polymorphize(tcx);
+                    let instance = instance.polymorphize(tcx);
                     let fn_alloc_id = tcx.create_fn_alloc(instance);
                     let fn_ptr = Pointer::from(fn_alloc_id);
                     ScalarMaybeUninit::from_pointer(fn_ptr, &tcx)
                 }
+                VtblEntry::TraitVPtr(trait_ref) => {
+                    let super_trait_ref = trait_ref.map_bound(|trait_ref| {
+                        ty::ExistentialTraitRef::erase_self_ty(tcx, trait_ref)
+                    });
+                    let supertrait_alloc_id = self.vtable_allocation(ty, Some(super_trait_ref));
+                    let vptr = Pointer::from(supertrait_alloc_id);
+                    ScalarMaybeUninit::from_pointer(vptr, &tcx)
+                }
             };
             vtable
                 .write_scalar(&tcx, alloc_range(ptr_size * idx, ptr_size), scalar)
diff --git a/compiler/rustc_mir/src/monomorphize/collector.rs b/compiler/rustc_mir/src/monomorphize/collector.rs
index 2ce7cf71116..95c4237f383 100644
--- a/compiler/rustc_mir/src/monomorphize/collector.rs
+++ b/compiler/rustc_mir/src/monomorphize/collector.rs
@@ -1116,13 +1116,13 @@ fn create_mono_items_for_vtable_methods<'tcx>(
                     | VtblEntry::MetadataSize
                     | VtblEntry::MetadataAlign
                     | VtblEntry::Vacant => None,
-                    VtblEntry::Method(def_id, substs) => ty::Instance::resolve_for_vtable(
-                        tcx,
-                        ty::ParamEnv::reveal_all(),
-                        *def_id,
-                        substs,
-                    )
-                    .filter(|instance| should_codegen_locally(tcx, instance)),
+                    VtblEntry::TraitVPtr(_) => {
+                        // all super trait items already covered, so skip them.
+                        None
+                    }
+                    VtblEntry::Method(instance) => {
+                        Some(*instance).filter(|instance| should_codegen_locally(tcx, instance))
+                    }
                 })
                 .map(|item| create_fn_mono_item(tcx, item, source));
             output.extend(methods);
diff --git a/compiler/rustc_span/src/symbol.rs b/compiler/rustc_span/src/symbol.rs
index a8f969782b2..c0f63f40853 100644
--- a/compiler/rustc_span/src/symbol.rs
+++ b/compiler/rustc_span/src/symbol.rs
@@ -1047,6 +1047,7 @@ symbols! {
         rustc_dump_env_program_clauses,
         rustc_dump_program_clauses,
         rustc_dump_user_substs,
+        rustc_dump_vtable,
         rustc_error,
         rustc_evaluate_where_clauses,
         rustc_expected_cgu_reuse,
diff --git a/compiler/rustc_trait_selection/src/lib.rs b/compiler/rustc_trait_selection/src/lib.rs
index e932b1bca7c..017a7c45bbf 100644
--- a/compiler/rustc_trait_selection/src/lib.rs
+++ b/compiler/rustc_trait_selection/src/lib.rs
@@ -31,6 +31,8 @@ extern crate rustc_data_structures;
 extern crate tracing;
 #[macro_use]
 extern crate rustc_middle;
+#[macro_use]
+extern crate smallvec;
 
 pub mod autoderef;
 pub mod infer;
diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs
index 3a80e720e8c..693384602a7 100644
--- a/compiler/rustc_trait_selection/src/traits/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/mod.rs
@@ -34,9 +34,11 @@ use rustc_middle::ty::{
     self, GenericParamDefKind, ToPredicate, Ty, TyCtxt, VtblEntry, WithConstness,
     COMMON_VTABLE_ENTRIES,
 };
-use rustc_span::Span;
+use rustc_span::{sym, Span};
+use smallvec::SmallVec;
 
 use std::fmt::Debug;
+use std::ops::ControlFlow;
 
 pub use self::FulfillmentErrorCode::*;
 pub use self::ImplSource::*;
@@ -454,6 +456,174 @@ fn subst_and_check_impossible_predicates<'tcx>(
     result
 }
 
+#[derive(Clone, Debug)]
+enum VtblSegment<'tcx> {
+    MetadataDSA,
+    TraitOwnEntries { trait_ref: ty::PolyTraitRef<'tcx>, emit_vptr: bool },
+}
+
+/// Prepare the segments for a vtable
+fn prepare_vtable_segments<'tcx, T>(
+    tcx: TyCtxt<'tcx>,
+    trait_ref: ty::PolyTraitRef<'tcx>,
+    mut segment_visitor: impl FnMut(VtblSegment<'tcx>) -> ControlFlow<T>,
+) -> Option<T> {
+    // The following constraints holds for the final arrangement.
+    // 1. The whole virtual table of the first direct super trait is included as the
+    //    the prefix. If this trait doesn't have any super traits, then this step
+    //    consists of the dsa metadata.
+    // 2. Then comes the proper pointer metadata(vptr) and all own methods for all
+    //    other super traits except those already included as part of the first
+    //    direct super trait virtual table.
+    // 3. finally, the own methods of this trait.
+
+    // This has the advantage that trait upcasting to the first direct super trait on each level
+    // is zero cost, and to another trait includes only replacing the pointer with one level indirection,
+    // while not using too much extra memory.
+
+    // For a single inheritance relationship like this,
+    //   D --> C --> B --> A
+    // The resulting vtable will consists of these segments:
+    //  DSA, A, B, C, D
+
+    // For a multiple inheritance relationship like this,
+    //   D --> C --> A
+    //           \-> B
+    // The resulting vtable will consists of these segments:
+    //  DSA, A, B, B-vptr, C, D
+
+    // For a diamond inheritance relationship like this,
+    //   D --> B --> A
+    //     \-> C -/
+    // The resulting vtable will consists of these segments:
+    //  DSA, A, B, C, C-vptr, D
+
+    // For a more complex inheritance relationship like this:
+    //   O --> G --> C --> A
+    //     \     \     \-> B
+    //     |     |-> F --> D
+    //     |           \-> E
+    //     |-> N --> J --> H
+    //           \     \-> I
+    //           |-> M --> K
+    //                 \-> L
+    // The resulting vtable will consists of these segments:
+    //  DSA, A, B, B-vptr, C, D, D-vptr, E, E-vptr, F, F-vptr, G,
+    //  H, H-vptr, I, I-vptr, J, J-vptr, K, K-vptr, L, L-vptr, M, M-vptr,
+    //  N, N-vptr, O
+
+    // emit dsa segment first.
+    if let ControlFlow::Break(v) = (segment_visitor)(VtblSegment::MetadataDSA) {
+        return Some(v);
+    }
+
+    let mut emit_vptr_on_new_entry = false;
+    let mut visited = util::PredicateSet::new(tcx);
+    let predicate = trait_ref.without_const().to_predicate(tcx);
+    let mut stack: SmallVec<[(ty::PolyTraitRef<'tcx>, _, _); 5]> =
+        smallvec![(trait_ref, emit_vptr_on_new_entry, None)];
+    visited.insert(predicate);
+
+    // the main traversal loop:
+    // basically we want to cut the inheritance directed graph into a few non-overlapping slices of nodes
+    // that each node is emited after all its descendents have been emitted.
+    // so we convert the directed graph into a tree by skipping all previously visted nodes using a visited set.
+    // this is done on the fly.
+    // Each loop run emits a slice - it starts by find a "childless" unvisited node, backtracking upwards, and it
+    // stops after it finds a node that has a next-sibling node.
+    // This next-sibling node will used as the starting point of next slice.
+
+    // Example:
+    // For a diamond inheritance relationship like this,
+    //   D#1 --> B#0 --> A#0
+    //     \-> C#1 -/
+
+    // Starting point 0 stack [D]
+    // Loop run #0: Stack after diving in is [D B A], A is "childless"
+    // after this point, all newly visited nodes won't have a vtable that equals to a prefix of this one.
+    // Loop run #0: Emiting the slice [B A] (in reverse order), B has a next-sibling node, so this slice stops here.
+    // Loop run #0: Stack after exiting out is [D C], C is the next starting point.
+    // Loop run #1: Stack after diving in is [D C], C is "childless", since its child A is skipped(already emitted).
+    // Loop run #1: Emiting the slice [D C] (in reverse order). No one has a next-sibling node.
+    // Loop run #1: Stack after exiting out is []. Now the function exits.
+
+    loop {
+        // dive deeper into the stack, recording the path
+        'diving_in: loop {
+            if let Some((inner_most_trait_ref, _, _)) = stack.last() {
+                let inner_most_trait_ref = *inner_most_trait_ref;
+                let mut direct_super_traits_iter = tcx
+                    .super_predicates_of(inner_most_trait_ref.def_id())
+                    .predicates
+                    .into_iter()
+                    .filter_map(move |(pred, _)| {
+                        pred.subst_supertrait(tcx, &inner_most_trait_ref).to_opt_poly_trait_ref()
+                    });
+
+                'diving_in_skip_visited_traits: loop {
+                    if let Some(next_super_trait) = direct_super_traits_iter.next() {
+                        if visited.insert(next_super_trait.to_predicate(tcx)) {
+                            stack.push((
+                                next_super_trait.value,
+                                emit_vptr_on_new_entry,
+                                Some(direct_super_traits_iter),
+                            ));
+                            break 'diving_in_skip_visited_traits;
+                        } else {
+                            continue 'diving_in_skip_visited_traits;
+                        }
+                    } else {
+                        break 'diving_in;
+                    }
+                }
+            }
+        }
+
+        // Other than the left-most path, vptr should be emitted for each trait.
+        emit_vptr_on_new_entry = true;
+
+        // emit innermost item, move to next sibling and stop there if possible, otherwise jump to outer level.
+        'exiting_out: loop {
+            if let Some((inner_most_trait_ref, emit_vptr, siblings_opt)) = stack.last_mut() {
+                if let ControlFlow::Break(v) = (segment_visitor)(VtblSegment::TraitOwnEntries {
+                    trait_ref: *inner_most_trait_ref,
+                    emit_vptr: *emit_vptr,
+                }) {
+                    return Some(v);
+                }
+
+                'exiting_out_skip_visited_traits: loop {
+                    if let Some(siblings) = siblings_opt {
+                        if let Some(next_inner_most_trait_ref) = siblings.next() {
+                            if visited.insert(next_inner_most_trait_ref.to_predicate(tcx)) {
+                                *inner_most_trait_ref = next_inner_most_trait_ref.value;
+                                *emit_vptr = emit_vptr_on_new_entry;
+                                break 'exiting_out;
+                            } else {
+                                continue 'exiting_out_skip_visited_traits;
+                            }
+                        }
+                    }
+                    stack.pop();
+                    continue 'exiting_out;
+                }
+            }
+            // all done
+            return None;
+        }
+    }
+}
+
+fn dump_vtable_entries<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    sp: Span,
+    trait_ref: ty::PolyTraitRef<'tcx>,
+    entries: &[VtblEntry<'tcx>],
+) {
+    let msg = format!("Vtable entries for `{}`: {:#?}", trait_ref, entries);
+    tcx.sess.struct_span_err(sp, &msg).emit();
+}
+
 /// Given a trait `trait_ref`, iterates the vtable entries
 /// that come from `trait_ref`, including its supertraits.
 fn vtable_entries<'tcx>(
@@ -462,57 +632,86 @@ fn vtable_entries<'tcx>(
 ) -> &'tcx [VtblEntry<'tcx>] {
     debug!("vtable_entries({:?})", trait_ref);
 
-    let entries = COMMON_VTABLE_ENTRIES.iter().cloned().chain(
-        supertraits(tcx, trait_ref).flat_map(move |trait_ref| {
-            let trait_methods = tcx
-                .associated_items(trait_ref.def_id())
-                .in_definition_order()
-                .filter(|item| item.kind == ty::AssocKind::Fn);
-
-            // Now list each method's DefId and InternalSubsts (for within its trait).
-            // If the method can never be called from this object, produce `Vacant`.
-            trait_methods.map(move |trait_method| {
-                debug!("vtable_entries: trait_method={:?}", trait_method);
-                let def_id = trait_method.def_id;
-
-                // Some methods cannot be called on an object; skip those.
-                if !is_vtable_safe_method(tcx, trait_ref.def_id(), &trait_method) {
-                    debug!("vtable_entries: not vtable safe");
-                    return VtblEntry::Vacant;
-                }
+    let mut entries = vec![];
 
-                // The method may have some early-bound lifetimes; add regions for those.
-                let substs = trait_ref.map_bound(|trait_ref| {
-                    InternalSubsts::for_item(tcx, def_id, |param, _| match param.kind {
-                        GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(),
-                        GenericParamDefKind::Type { .. } | GenericParamDefKind::Const { .. } => {
-                            trait_ref.substs[param.index as usize]
-                        }
-                    })
+    let vtable_segment_callback = |segment| -> ControlFlow<()> {
+        match segment {
+            VtblSegment::MetadataDSA => {
+                entries.extend(COMMON_VTABLE_ENTRIES);
+            }
+            VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => {
+                let trait_methods = tcx
+                    .associated_items(trait_ref.def_id())
+                    .in_definition_order()
+                    .filter(|item| item.kind == ty::AssocKind::Fn);
+                // Now list each method's DefId and InternalSubsts (for within its trait).
+                // If the method can never be called from this object, produce `Vacant`.
+                let own_entries = trait_methods.map(move |trait_method| {
+                    debug!("vtable_entries: trait_method={:?}", trait_method);
+                    let def_id = trait_method.def_id;
+
+                    // Some methods cannot be called on an object; skip those.
+                    if !is_vtable_safe_method(tcx, trait_ref.def_id(), &trait_method) {
+                        debug!("vtable_entries: not vtable safe");
+                        return VtblEntry::Vacant;
+                    }
+
+                    // The method may have some early-bound lifetimes; add regions for those.
+                    let substs = trait_ref.map_bound(|trait_ref| {
+                        InternalSubsts::for_item(tcx, def_id, |param, _| match param.kind {
+                            GenericParamDefKind::Lifetime => tcx.lifetimes.re_erased.into(),
+                            GenericParamDefKind::Type { .. }
+                            | GenericParamDefKind::Const { .. } => {
+                                trait_ref.substs[param.index as usize]
+                            }
+                        })
+                    });
+
+                    // The trait type may have higher-ranked lifetimes in it;
+                    // erase them if they appear, so that we get the type
+                    // at some particular call site.
+                    let substs = tcx
+                        .normalize_erasing_late_bound_regions(ty::ParamEnv::reveal_all(), substs);
+
+                    // It's possible that the method relies on where-clauses that
+                    // do not hold for this particular set of type parameters.
+                    // Note that this method could then never be called, so we
+                    // do not want to try and codegen it, in that case (see #23435).
+                    let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, substs);
+                    if impossible_predicates(tcx, predicates.predicates) {
+                        debug!("vtable_entries: predicates do not hold");
+                        return VtblEntry::Vacant;
+                    }
+
+                    let instance = ty::Instance::resolve_for_vtable(
+                        tcx,
+                        ty::ParamEnv::reveal_all(),
+                        def_id,
+                        substs,
+                    )
+                    .expect("resolution failed during building vtable representation");
+                    VtblEntry::Method(instance)
                 });
 
-                // The trait type may have higher-ranked lifetimes in it;
-                // erase them if they appear, so that we get the type
-                // at some particular call site.
-                let substs =
-                    tcx.normalize_erasing_late_bound_regions(ty::ParamEnv::reveal_all(), substs);
-
-                // It's possible that the method relies on where-clauses that
-                // do not hold for this particular set of type parameters.
-                // Note that this method could then never be called, so we
-                // do not want to try and codegen it, in that case (see #23435).
-                let predicates = tcx.predicates_of(def_id).instantiate_own(tcx, substs);
-                if impossible_predicates(tcx, predicates.predicates) {
-                    debug!("vtable_entries: predicates do not hold");
-                    return VtblEntry::Vacant;
+                entries.extend(own_entries);
+
+                if emit_vptr {
+                    entries.push(VtblEntry::TraitVPtr(trait_ref));
                 }
+            }
+        }
 
-                VtblEntry::Method(def_id, substs)
-            })
-        }),
-    );
+        ControlFlow::Continue(())
+    };
+
+    let _ = prepare_vtable_segments(tcx, trait_ref, vtable_segment_callback);
+
+    if tcx.has_attr(trait_ref.def_id(), sym::rustc_dump_vtable) {
+        let sp = tcx.def_span(trait_ref.def_id());
+        dump_vtable_entries(tcx, sp, trait_ref, &entries);
+    }
 
-    tcx.arena.alloc_from_iter(entries)
+    tcx.arena.alloc_from_iter(entries.into_iter())
 }
 
 /// Find slot base for trait methods within vtable entries of another trait
@@ -525,20 +724,82 @@ fn vtable_trait_first_method_offset<'tcx>(
 ) -> usize {
     let (trait_to_be_found, trait_owning_vtable) = key;
 
-    let mut supertraits = util::supertraits(tcx, trait_owning_vtable);
+    let vtable_segment_callback = {
+        let mut vtable_base = 0;
+
+        move |segment| {
+            match segment {
+                VtblSegment::MetadataDSA => {
+                    vtable_base += COMMON_VTABLE_ENTRIES.len();
+                }
+                VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => {
+                    if trait_ref == trait_to_be_found {
+                        return ControlFlow::Break(vtable_base);
+                    }
+                    vtable_base += util::count_own_vtable_entries(tcx, trait_ref);
+                    if emit_vptr {
+                        vtable_base += 1;
+                    }
+                }
+            }
+            ControlFlow::Continue(())
+        }
+    };
+
+    if let Some(vtable_base) =
+        prepare_vtable_segments(tcx, trait_owning_vtable, vtable_segment_callback)
+    {
+        vtable_base
+    } else {
+        bug!("Failed to find info for expected trait in vtable");
+    }
+}
+
+/// Find slot offset for trait vptr within vtable entries of another trait
+/// FIXME: This function is not yet used. Remove `#[allow(dead_code)]` when it's used in upcoming pr.
+#[allow(dead_code)]
+fn vtable_trait_vptr_slot_offset<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    key: (
+        ty::PolyTraitRef<'tcx>, // trait_to_be_found
+        ty::PolyTraitRef<'tcx>, // trait_owning_vtable
+    ),
+) -> Option<usize> {
+    let (trait_to_be_found, trait_owning_vtable) = key;
+
+    let vtable_segment_callback = {
+        let mut vptr_offset = 0;
+        move |segment| {
+            match segment {
+                VtblSegment::MetadataDSA => {
+                    vptr_offset += COMMON_VTABLE_ENTRIES.len();
+                }
+                VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => {
+                    vptr_offset += util::count_own_vtable_entries(tcx, trait_ref);
+                    if trait_ref == trait_to_be_found {
+                        if emit_vptr {
+                            return ControlFlow::Break(Some(vptr_offset));
+                        } else {
+                            return ControlFlow::Break(None);
+                        }
+                    }
 
-    // For each of the non-matching predicates that
-    // we pass over, we sum up the set of number of vtable
-    // entries, so that we can compute the offset for the selected
-    // trait.
-    let vtable_base = ty::COMMON_VTABLE_ENTRIES.len()
-        + supertraits
-            .by_ref()
-            .take_while(|t| *t != trait_to_be_found)
-            .map(|t| util::count_own_vtable_entries(tcx, t))
-            .sum::<usize>();
+                    if emit_vptr {
+                        vptr_offset += 1;
+                    }
+                }
+            }
+            ControlFlow::Continue(())
+        }
+    };
 
-    vtable_base
+    if let Some(vptr_offset) =
+        prepare_vtable_segments(tcx, trait_owning_vtable, vtable_segment_callback)
+    {
+        vptr_offset
+    } else {
+        bug!("Failed to find info for expected trait in vtable");
+    }
 }
 
 pub fn provide(providers: &mut ty::query::Providers) {
diff --git a/src/test/ui/traits/vtable/vtable-diamond.rs b/src/test/ui/traits/vtable/vtable-diamond.rs
new file mode 100644
index 00000000000..f64ae95f1d4
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-diamond.rs
@@ -0,0 +1,39 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+#[rustc_dump_vtable]
+trait A {
+    fn foo_a(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait B: A {
+    fn foo_b(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait C: A {
+    //~^ error Vtable
+    fn foo_c(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait D: B + C {
+    //~^ error Vtable
+    fn foo_d(&self) {}
+}
+
+struct S;
+
+impl A for S {}
+impl B for S {}
+impl C for S {}
+impl D for S {}
+
+fn foo(d: &dyn D) {
+    d.foo_d();
+}
+
+fn main() {
+    foo(&S);
+}
diff --git a/src/test/ui/traits/vtable/vtable-diamond.stderr b/src/test/ui/traits/vtable/vtable-diamond.stderr
new file mode 100644
index 00000000000..92a7f29536e
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-diamond.stderr
@@ -0,0 +1,35 @@
+error: Vtable entries for `<S as D>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a),
+    Method(<S as B>::foo_b),
+    Method(<S as C>::foo_c),
+    TraitVPtr(<S as C>),
+    Method(<S as D>::foo_d),
+]
+  --> $DIR/vtable-diamond.rs:21:1
+   |
+LL | / trait D: B + C {
+LL | |
+LL | |     fn foo_d(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as C>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a),
+    Method(<S as C>::foo_c),
+]
+  --> $DIR/vtable-diamond.rs:15:1
+   |
+LL | / trait C: A {
+LL | |
+LL | |     fn foo_c(&self) {}
+LL | | }
+   | |_^
+
+error: aborting due to 2 previous errors
+
diff --git a/src/test/ui/traits/vtable/vtable-multi-level.rs b/src/test/ui/traits/vtable/vtable-multi-level.rs
new file mode 100644
index 00000000000..33112b4eaaa
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-multi-level.rs
@@ -0,0 +1,122 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+//   O --> G --> C --> A
+//     \     \     \-> B
+//     |     |-> F --> D
+//     |           \-> E
+//     |-> N --> J --> H
+//           \     \-> I
+//           |-> M --> K
+//                 \-> L
+
+#[rustc_dump_vtable]
+trait A {
+    fn foo_a(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait B {
+    //~^ error Vtable
+    fn foo_b(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait C: A + B {
+    fn foo_c(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait D {
+    //~^ error Vtable
+    fn foo_d(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait E {
+    //~^ error Vtable
+    fn foo_e(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait F: D + E {
+    //~^ error Vtable
+    fn foo_f(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait G: C + F {
+    fn foo_g(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait H {
+    //~^ error Vtable
+    fn foo_h(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait I {
+    //~^ error Vtable
+    fn foo_i(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait J: H + I {
+    //~^ error Vtable
+    fn foo_j(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait K {
+    //~^ error Vtable
+    fn foo_k(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait L {
+    //~^ error Vtable
+    fn foo_l(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait M: K + L {
+    //~^ error Vtable
+    fn foo_m(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait N: J + M {
+    //~^ error Vtable
+    fn foo_n(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait O: G + N {
+    //~^ error Vtable
+    fn foo_o(&self) {}
+}
+
+struct S;
+
+impl A for S {}
+impl B for S {}
+impl C for S {}
+impl D for S {}
+impl E for S {}
+impl F for S {}
+impl G for S {}
+impl H for S {}
+impl I for S {}
+impl J for S {}
+impl K for S {}
+impl L for S {}
+impl M for S {}
+impl N for S {}
+impl O for S {}
+
+fn foo(_: &dyn O) {}
+
+fn main() {
+    foo(&S);
+}
diff --git a/src/test/ui/traits/vtable/vtable-multi-level.stderr b/src/test/ui/traits/vtable/vtable-multi-level.stderr
new file mode 100644
index 00000000000..7700db98e0b
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-multi-level.stderr
@@ -0,0 +1,214 @@
+error: Vtable entries for `<S as O>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a),
+    Method(<S as B>::foo_b),
+    TraitVPtr(<S as B>),
+    Method(<S as C>::foo_c),
+    Method(<S as D>::foo_d),
+    TraitVPtr(<S as D>),
+    Method(<S as E>::foo_e),
+    TraitVPtr(<S as E>),
+    Method(<S as F>::foo_f),
+    TraitVPtr(<S as F>),
+    Method(<S as G>::foo_g),
+    Method(<S as H>::foo_h),
+    TraitVPtr(<S as H>),
+    Method(<S as I>::foo_i),
+    TraitVPtr(<S as I>),
+    Method(<S as J>::foo_j),
+    TraitVPtr(<S as J>),
+    Method(<S as K>::foo_k),
+    TraitVPtr(<S as K>),
+    Method(<S as L>::foo_l),
+    TraitVPtr(<S as L>),
+    Method(<S as M>::foo_m),
+    TraitVPtr(<S as M>),
+    Method(<S as N>::foo_n),
+    TraitVPtr(<S as N>),
+    Method(<S as O>::foo_o),
+]
+  --> $DIR/vtable-multi-level.rs:95:1
+   |
+LL | / trait O: G + N {
+LL | |
+LL | |     fn foo_o(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as B>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as B>::foo_b),
+]
+  --> $DIR/vtable-multi-level.rs:19:1
+   |
+LL | / trait B {
+LL | |
+LL | |     fn foo_b(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as D>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as D>::foo_d),
+]
+  --> $DIR/vtable-multi-level.rs:30:1
+   |
+LL | / trait D {
+LL | |
+LL | |     fn foo_d(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as E>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as E>::foo_e),
+]
+  --> $DIR/vtable-multi-level.rs:36:1
+   |
+LL | / trait E {
+LL | |
+LL | |     fn foo_e(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as F>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as D>::foo_d),
+    Method(<S as E>::foo_e),
+    TraitVPtr(<S as E>),
+    Method(<S as F>::foo_f),
+]
+  --> $DIR/vtable-multi-level.rs:42:1
+   |
+LL | / trait F: D + E {
+LL | |
+LL | |     fn foo_f(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as H>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as H>::foo_h),
+]
+  --> $DIR/vtable-multi-level.rs:53:1
+   |
+LL | / trait H {
+LL | |
+LL | |     fn foo_h(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as I>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as I>::foo_i),
+]
+  --> $DIR/vtable-multi-level.rs:59:1
+   |
+LL | / trait I {
+LL | |
+LL | |     fn foo_i(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as J>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as H>::foo_h),
+    Method(<S as I>::foo_i),
+    TraitVPtr(<S as I>),
+    Method(<S as J>::foo_j),
+]
+  --> $DIR/vtable-multi-level.rs:65:1
+   |
+LL | / trait J: H + I {
+LL | |
+LL | |     fn foo_j(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as K>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as K>::foo_k),
+]
+  --> $DIR/vtable-multi-level.rs:71:1
+   |
+LL | / trait K {
+LL | |
+LL | |     fn foo_k(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as L>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as L>::foo_l),
+]
+  --> $DIR/vtable-multi-level.rs:77:1
+   |
+LL | / trait L {
+LL | |
+LL | |     fn foo_l(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as M>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as K>::foo_k),
+    Method(<S as L>::foo_l),
+    TraitVPtr(<S as L>),
+    Method(<S as M>::foo_m),
+]
+  --> $DIR/vtable-multi-level.rs:83:1
+   |
+LL | / trait M: K + L {
+LL | |
+LL | |     fn foo_m(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as N>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as H>::foo_h),
+    Method(<S as I>::foo_i),
+    TraitVPtr(<S as I>),
+    Method(<S as J>::foo_j),
+    Method(<S as K>::foo_k),
+    TraitVPtr(<S as K>),
+    Method(<S as L>::foo_l),
+    TraitVPtr(<S as L>),
+    Method(<S as M>::foo_m),
+    TraitVPtr(<S as M>),
+    Method(<S as N>::foo_n),
+]
+  --> $DIR/vtable-multi-level.rs:89:1
+   |
+LL | / trait N: J + M {
+LL | |
+LL | |     fn foo_n(&self) {}
+LL | | }
+   | |_^
+
+error: aborting due to 12 previous errors
+
diff --git a/src/test/ui/traits/vtable/vtable-multiple.rs b/src/test/ui/traits/vtable/vtable-multiple.rs
new file mode 100644
index 00000000000..cb0d0b72481
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-multiple.rs
@@ -0,0 +1,31 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+#[rustc_dump_vtable]
+trait A {
+    fn foo_a(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait B {
+    //~^ error Vtable
+    fn foo_b(&self) {}
+}
+
+#[rustc_dump_vtable]
+trait C: A + B {
+    //~^ error Vtable
+    fn foo_c(&self) {}
+}
+
+struct S;
+
+impl A for S {}
+impl B for S {}
+impl C for S {}
+
+fn foo(c: &dyn C) {}
+
+fn main() {
+    foo(&S);
+}
diff --git a/src/test/ui/traits/vtable/vtable-multiple.stderr b/src/test/ui/traits/vtable/vtable-multiple.stderr
new file mode 100644
index 00000000000..f51b083de25
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-multiple.stderr
@@ -0,0 +1,33 @@
+error: Vtable entries for `<S as C>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a),
+    Method(<S as B>::foo_b),
+    TraitVPtr(<S as B>),
+    Method(<S as C>::foo_c),
+]
+  --> $DIR/vtable-multiple.rs:16:1
+   |
+LL | / trait C: A + B {
+LL | |
+LL | |     fn foo_c(&self) {}
+LL | | }
+   | |_^
+
+error: Vtable entries for `<S as B>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as B>::foo_b),
+]
+  --> $DIR/vtable-multiple.rs:10:1
+   |
+LL | / trait B {
+LL | |
+LL | |     fn foo_b(&self) {}
+LL | | }
+   | |_^
+
+error: aborting due to 2 previous errors
+
diff --git a/src/test/ui/traits/vtable/vtable-vacant.rs b/src/test/ui/traits/vtable/vtable-vacant.rs
new file mode 100644
index 00000000000..ebea94171f2
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-vacant.rs
@@ -0,0 +1,28 @@
+// build-fail
+#![feature(rustc_attrs)]
+
+// B --> A
+
+#[rustc_dump_vtable]
+trait A {
+    fn foo_a1(&self) {}
+    fn foo_a2(&self) where Self: Sized {}
+}
+
+#[rustc_dump_vtable]
+trait B: A {
+    //~^ error Vtable
+    fn foo_b1(&self) {}
+    fn foo_b2() where Self: Sized {}
+}
+
+struct S;
+
+impl A for S {}
+impl B for S {}
+
+fn foo(_: &dyn B) {}
+
+fn main() {
+    foo(&S);
+}
diff --git a/src/test/ui/traits/vtable/vtable-vacant.stderr b/src/test/ui/traits/vtable/vtable-vacant.stderr
new file mode 100644
index 00000000000..768cca52689
--- /dev/null
+++ b/src/test/ui/traits/vtable/vtable-vacant.stderr
@@ -0,0 +1,20 @@
+error: Vtable entries for `<S as B>`: [
+    MetadataDropInPlace,
+    MetadataSize,
+    MetadataAlign,
+    Method(<S as A>::foo_a1),
+    Vacant,
+    Method(<S as B>::foo_b1),
+    Vacant,
+]
+  --> $DIR/vtable-vacant.rs:13:1
+   |
+LL | / trait B: A {
+LL | |
+LL | |     fn foo_b1(&self) {}
+LL | |     fn foo_b2() where Self: Sized {}
+LL | | }
+   | |_^
+
+error: aborting due to previous error
+