Auto merge of #96285 - flip1995:pk-vfe, r=nagisa

Introduce `-Zvirtual-function-elimination` codegen flag

Fixes #68262

This PR adds a codegen flag `-Zvirtual-function-elimination` to enable the VFE optimization in LLVM. To make this work, additonal  information has to be added to vtables ([`!vcall_visibility` metadata](https://llvm.org/docs/TypeMetadata.html#vcall-visibility-metadata) and a `typeid` of the trait). Furthermore, instead of just `load`ing functions, the [`llvm.type.checked.load` intrinsic](https://llvm.org/docs/LangRef.html#llvm-type-checked-load-intrinsic) has to be used to map functions to vtables.

For technical details of the changes, see the commit messages.

I also tested this flag on https://github.com/tock/tock on different boards to verify that this fixes the issue https://github.com/tock/tock/issues/2594. This flag is able to improve the size of the resulting binary by about 8k-9k bytes by removing the unused debug print functions.

[Rendered documentation update](https://github.com/flip1995/rust/blob/pk-vfe/src/doc/rustc/src/codegen-options/index.md#virtual-function-elimination)

3 files changed, 63 insertions, 15 deletions

diff --git a/compiler/rustc_codegen_ssa/src/meth.rs b/compiler/rustc_codegen_ssa/src/meth.rs
index 00f101595f2..5203ebfad75 100644
--- a/compiler/rustc_codegen_ssa/src/meth.rs
+++ b/compiler/rustc_codegen_ssa/src/meth.rs
@@ -1,6 +1,8 @@
 use crate::traits::*;
 
-use rustc_middle::ty::{self, Ty};
+use rustc_middle::ty::{self, subst::GenericArgKind, ExistentialPredicate, Ty, TyCtxt};
+use rustc_session::config::Lto;
+use rustc_symbol_mangling::typeid_for_trait_ref;
 use rustc_target::abi::call::FnAbi;
 
 #[derive(Copy, Clone, Debug)]
@@ -15,20 +17,32 @@ impl<'a, 'tcx> VirtualIndex {
         self,
         bx: &mut Bx,
         llvtable: Bx::Value,
+        ty: Ty<'tcx>,
         fn_abi: &FnAbi<'tcx, Ty<'tcx>>,
     ) -> Bx::Value {
         // Load the data pointer from the object.
-        debug!("get_fn({:?}, {:?})", llvtable, self);
-
+        debug!("get_fn({llvtable:?}, {ty:?}, {self:?})");
         let llty = bx.fn_ptr_backend_type(fn_abi);
         let llvtable = bx.pointercast(llvtable, bx.type_ptr_to(llty));
-        let ptr_align = bx.tcx().data_layout.pointer_align.abi;
-        let gep = bx.inbounds_gep(llty, llvtable, &[bx.const_usize(self.0)]);
-        let ptr = bx.load(llty, gep, ptr_align);
-        bx.nonnull_metadata(ptr);
-        // Vtable loads are invariant.
-        bx.set_invariant_load(ptr);
-        ptr
+
+        if bx.cx().sess().opts.debugging_opts.virtual_function_elimination
+            && bx.cx().sess().lto() == Lto::Fat
+        {
+            let typeid =
+                bx.typeid_metadata(typeid_for_trait_ref(bx.tcx(), get_trait_ref(bx.tcx(), ty)));
+            let vtable_byte_offset = self.0 * bx.data_layout().pointer_size.bytes();
+            let type_checked_load = bx.type_checked_load(llvtable, vtable_byte_offset, typeid);
+            let func = bx.extract_value(type_checked_load, 0);
+            bx.pointercast(func, llty)
+        } else {
+            let ptr_align = bx.tcx().data_layout.pointer_align.abi;
+            let gep = bx.inbounds_gep(llty, llvtable, &[bx.const_usize(self.0)]);
+            let ptr = bx.load(llty, gep, ptr_align);
+            bx.nonnull_metadata(ptr);
+            // Vtable loads are invariant.
+            bx.set_invariant_load(ptr);
+            ptr
+        }
     }
 
     pub fn get_usize<Bx: BuilderMethods<'a, 'tcx>>(
@@ -50,6 +64,24 @@ impl<'a, 'tcx> VirtualIndex {
     }
 }
 
+fn get_trait_ref<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> ty::PolyExistentialTraitRef<'tcx> {
+    for arg in ty.peel_refs().walk() {
+        if let GenericArgKind::Type(ty) = arg.unpack() {
+            if let ty::Dynamic(trait_refs, _) = ty.kind() {
+                return trait_refs[0].map_bound(|trait_ref| match trait_ref {
+                    ExistentialPredicate::Trait(tr) => tr,
+                    ExistentialPredicate::Projection(proj) => proj.trait_ref(tcx),
+                    ExistentialPredicate::AutoTrait(_) => {
+                        bug!("auto traits don't have functions")
+                    }
+                });
+            }
+        }
+    }
+
+    bug!("expected a `dyn Trait` ty, found {ty:?}")
+}
+
 /// Creates a dynamic vtable for the given type and vtable origin.
 /// This is used only for objects.
 ///
diff --git a/compiler/rustc_codegen_ssa/src/mir/block.rs b/compiler/rustc_codegen_ssa/src/mir/block.rs
index 03ef6d50d44..db348f2bdd5 100644
--- a/compiler/rustc_codegen_ssa/src/mir/block.rs
+++ b/compiler/rustc_codegen_ssa/src/mir/block.rs
@@ -401,7 +401,7 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
                 args = &args[..1];
                 (
                     meth::VirtualIndex::from_index(ty::COMMON_VTABLE_ENTRIES_DROPINPLACE)
-                        .get_fn(&mut bx, vtable, &fn_abi),
+                        .get_fn(&mut bx, vtable, ty, &fn_abi),
                     fn_abi,
                 )
             }
@@ -819,9 +819,12 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
                     // the data pointer as the first argument
                     match op.val {
                         Pair(data_ptr, meta) => {
-                            llfn = Some(
-                                meth::VirtualIndex::from_index(idx).get_fn(&mut bx, meta, &fn_abi),
-                            );
+                            llfn = Some(meth::VirtualIndex::from_index(idx).get_fn(
+                                &mut bx,
+                                meta,
+                                op.layout.ty,
+                                &fn_abi,
+                            ));
                             llargs.push(data_ptr);
                             continue 'make_args;
                         }
@@ -829,7 +832,12 @@ impl<'a, 'tcx, Bx: BuilderMethods<'a, 'tcx>> FunctionCx<'a, 'tcx, Bx> {
                     }
                 } else if let Ref(data_ptr, Some(meta), _) = op.val {
                     // by-value dynamic dispatch
-                    llfn = Some(meth::VirtualIndex::from_index(idx).get_fn(&mut bx, meta, &fn_abi));
+                    llfn = Some(meth::VirtualIndex::from_index(idx).get_fn(
+                        &mut bx,
+                        meta,
+                        op.layout.ty,
+                        &fn_abi,
+                    ));
                     llargs.push(data_ptr);
                     continue;
                 } else {
diff --git a/compiler/rustc_codegen_ssa/src/traits/intrinsic.rs b/compiler/rustc_codegen_ssa/src/traits/intrinsic.rs
index 02be6cd360c..7755e67938c 100644
--- a/compiler/rustc_codegen_ssa/src/traits/intrinsic.rs
+++ b/compiler/rustc_codegen_ssa/src/traits/intrinsic.rs
@@ -22,6 +22,14 @@ pub trait IntrinsicCallMethods<'tcx>: BackendTypes {
     fn expect(&mut self, cond: Self::Value, expected: bool) -> Self::Value;
     /// Trait method used to test whether a given pointer is associated with a type identifier.
     fn type_test(&mut self, pointer: Self::Value, typeid: Self::Value) -> Self::Value;
+    /// Trait method used to load a function while testing if it is associated with a type
+    /// identifier.
+    fn type_checked_load(
+        &mut self,
+        llvtable: Self::Value,
+        vtable_byte_offset: u64,
+        typeid: Self::Value,
+    ) -> Self::Value;
     /// Trait method used to inject `va_start` on the "spoofed" `VaListImpl` in
     /// Rust defined C-variadic functions.
     fn va_start(&mut self, val: Self::Value) -> Self::Value;