Vtable format to support dyn upcasting coercion

This current design was proposed by Mario Carneiro based on previous proposals on Zulip discussion. It's a hybrid approach taking the benefits of both a "flat" design, and a "pointer"-based design.

This is implemented in #86461.

The vtable is generated by this algorithm in principle for a type T and a trait Tr:

1. First emit the header part, including MetadataDropInPlace, MetadataSize, MetadataAlign items.
2. Create a tree of all the supertraits of this TraitRef, by filtering out all of duplicates.
3. Collect a set of TraitRefs consisting the trait and its first supertrait and its first supertrait's super trait,... and so on. Call this set PrefixSet
4. Traverse the tree in post-order, for each TraitRef emit all its associated functions as either Method or Vacant entries. If this TraitRef is not in PrefixSet, emit a TraitVPtr containing a constant pointer to the vtable generated for the type T and this TraitRef.

Example

#![allow(unused)]
fn main() {
trait A {
    fn foo_a(&self) {}
}

trait B: A {
    fn foo_b(&self) {}
}

trait C: A {
    fn foo_c(&self) {}
}

trait D: B + C {
    fn foo_d(&self) {}
}
}

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),
]

Vtable entries for `<S as C>`: [
    MetadataDropInPlace,
    MetadataSize,
    MetadataAlign,
    Method(<S as A>::foo_a),
    Method(<S as C>::foo_c),
]

Runtime behavior for dyn upcasting coercion

At the codegen time, the same algorithm above is performed for the source principal trait and the source trait object type. If the target principal trait is in the PrefixSet set, this coercion is a no-op.

If the target principal trait is not in the PrefixSet, generate code that read the data pointer from the corresponding TraitVPtr slot.

Alternatives

Flat design

The vtable is generated by this algorithm in principle for a type T and a trait Tr:

1. Create a tree of all the supertraits of this TraitRef, duplicate for the cyclic cases.
2. Traverse the tree in post-order, for each TraitRef,
   1. if it has no supertrait, emit a header part, including MetadataDropInPlace, MetadataSize, MetadataAlign items.
   2. emit all its associated functions as either Method or Vacant entries.

Cons

If there is a lot of diamond inheritance that could result in exponential blowup of the vtable for example, trait A(n+1): Bn + Cn {}, trait Bn: An { fn bn(&self); }, trait Cn: An { fn cn(&self); }

the vtable for An will contain 2^n DSAs

Pointer-based design

All traits have their own vtables, and embedded all links to supertraits in the vtables

Cons

Codegen regression for single-inheritance cases, which is very widely used.