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, 174 insertions, 0 deletions

diff --git a/src/doc/unstable-book/src/compiler-flags/virtual-function-elimination.md b/src/doc/unstable-book/src/compiler-flags/virtual-function-elimination.md
new file mode 100644
index 00000000000..c6516d838dd
--- /dev/null
+++ b/src/doc/unstable-book/src/compiler-flags/virtual-function-elimination.md
@@ -0,0 +1,39 @@
+# `virtual-function-elimination`
+
+This option controls whether LLVM runs the Virtual Function Elimination (VFE)
+optimization. This optimization in only available with LTO, so this flag can
+only be passed if [`-Clto`][Clto] is also passed.
+
+VFE makes it possible to remove functions from vtables that are never
+dynamically called by the rest of the code. Without this flag, LLVM makes the
+really conservative assumption, that if any function in a vtable is called, no
+function that is referenced by this vtable can be removed. With this flag
+additional information are given to LLVM, so that it can determine which
+functions are actually called and remove the unused functions.
+
+## Limitations
+
+At the time of writing this flag may remove vtable functions too eagerly. One
+such example is in this code:
+
+```rust
+trait Foo { fn foo(&self) { println!("foo") } }
+
+impl Foo for usize {}
+
+pub struct FooBox(Box<dyn Foo>);
+
+pub fn make_foo() -> FooBox { FooBox(Box::new(0)) }
+
+#[inline]
+pub fn f(a: FooBox) { a.0.foo() }
+```
+
+In the above code the `Foo` trait is private, so an assumption is made that its
+functions can only be seen/called from the current crate and can therefore get
+optimized out, if unused. However, with `make_foo` you can produce a wrapped
+`dyn Foo` type outside of the current crate, which can then be used in `f`. Due
+to inlining of `f`, `Foo::foo` can then be called from a foreign crate. This can
+lead to miscompilations.
+
+[Clto]: https://doc.rust-lang.org/rustc/codegen-options/index.html#lto
diff --git a/src/test/codegen/virtual-function-elimination-32bit.rs b/src/test/codegen/virtual-function-elimination-32bit.rs
new file mode 100644
index 00000000000..6f963363a99
--- /dev/null
+++ b/src/test/codegen/virtual-function-elimination-32bit.rs
@@ -0,0 +1,35 @@
+// compile-flags: -Zvirtual-function-elimination -Clto -O -Csymbol-mangling-version=v0
+// ignore-64bit
+
+// CHECK: @vtable.0 = {{.*}}, !type ![[TYPE0:[0-9]+]], !vcall_visibility ![[VCALL_VIS0:[0-9]+]]
+
+#![crate_type = "lib"]
+
+trait T {
+    // CHECK-LABEL: ; <virtual_function_elimination_32bit::S as virtual_function_elimination_32bit::T>::used
+    fn used(&self) -> i32 {
+        1
+    }
+    // CHECK-LABEL-NOT: {{.*}}::unused
+    fn unused(&self) -> i32 {
+        2
+    }
+}
+
+#[derive(Copy, Clone)]
+struct S;
+
+impl T for S {}
+
+fn taking_t(t: &dyn T) -> i32 {
+    // CHECK: @llvm.type.checked.load({{.*}}, i32 12, metadata !"[[MANGLED_TYPE0:[0-9a-zA-Z_]+]]")
+    t.used()
+}
+
+pub fn main() {
+    let s = S;
+    taking_t(&s);
+}
+
+// CHECK: ![[TYPE0]] = !{i32 0, !"[[MANGLED_TYPE0]]"}
+// CHECK: ![[VCALL_VIS0]] = !{i64 2}
diff --git a/src/test/codegen/virtual-function-elimination.rs b/src/test/codegen/virtual-function-elimination.rs
new file mode 100644
index 00000000000..4cf7e12fee2
--- /dev/null
+++ b/src/test/codegen/virtual-function-elimination.rs
@@ -0,0 +1,100 @@
+// compile-flags: -Zvirtual-function-elimination -Clto -O -Csymbol-mangling-version=v0
+// ignore-32bit
+
+// CHECK: @vtable.0 = {{.*}}, !type ![[TYPE0:[0-9]+]], !vcall_visibility ![[VCALL_VIS0:[0-9]+]]
+// CHECK: @vtable.1 = {{.*}}, !type ![[TYPE1:[0-9]+]], !vcall_visibility ![[VCALL_VIS0:[0-9]+]]
+// CHECK: @vtable.2 = {{.*}}, !type ![[TYPE2:[0-9]+]], !vcall_visibility ![[VCALL_VIS2:[0-9]+]]
+
+#![crate_type = "lib"]
+#![allow(incomplete_features)]
+#![feature(unsized_locals)]
+
+use std::rc::Rc;
+
+trait T {
+    // CHECK-LABEL: ; <virtual_function_elimination::S as virtual_function_elimination::T>::used
+    fn used(&self) -> i32 {
+        1
+    }
+    // CHECK-LABEL: ; <virtual_function_elimination::S as virtual_function_elimination::T>::used_through_sub_trait
+    fn used_through_sub_trait(&self) -> i32 {
+        3
+    }
+    // CHECK-LABEL: ; <virtual_function_elimination::S as virtual_function_elimination::T>::by_rc
+    fn by_rc(self: Rc<Self>) -> i32 {
+        self.used() + self.used()
+    }
+    // CHECK-LABEL-NOT: {{.*}}::unused
+    fn unused(&self) -> i32 {
+        2
+    }
+    // CHECK-LABEL-NOT: {{.*}}::by_rc_unused
+    fn by_rc_unused(self: Rc<Self>) -> i32 {
+        self.by_rc()
+    }
+}
+
+trait U: T {
+    // CHECK-LABEL: ; <virtual_function_elimination::S as virtual_function_elimination::U>::subtrait_used
+    fn subtrait_used(&self) -> i32 {
+        4
+    }
+    // CHECK-LABEL-NOT: {{.*}}::subtrait_unused
+    fn subtrait_unused(&self) -> i32 {
+        5
+    }
+}
+
+pub trait V {
+    // CHECK-LABEL: ; <virtual_function_elimination::S as virtual_function_elimination::V>::public_function
+    fn public_function(&self) -> i32;
+}
+
+#[derive(Copy, Clone)]
+struct S;
+
+impl T for S {}
+
+impl U for S {}
+
+impl V for S {
+    fn public_function(&self) -> i32 {
+        6
+    }
+}
+
+fn taking_t(t: &dyn T) -> i32 {
+    // CHECK: @llvm.type.checked.load({{.*}}, i32 24, metadata !"[[MANGLED_TYPE0:[0-9a-zA-Z_]+]]")
+    t.used()
+}
+
+fn taking_rc_t(t: Rc<dyn T>) -> i32 {
+    // CHECK: @llvm.type.checked.load({{.*}}, i32 40, metadata !"[[MANGLED_TYPE0:[0-9a-zA-Z_]+]]")
+    t.by_rc()
+}
+
+fn taking_u(u: &dyn U) -> i32 {
+    // CHECK: @llvm.type.checked.load({{.*}}, i32 64, metadata !"[[MANGLED_TYPE1:[0-9a-zA-Z_]+]]")
+    // CHECK: @llvm.type.checked.load({{.*}}, i32 24, metadata !"[[MANGLED_TYPE1:[0-9a-zA-Z_]+]]")
+    // CHECK: @llvm.type.checked.load({{.*}}, i32 32, metadata !"[[MANGLED_TYPE1:[0-9a-zA-Z_]+]]")
+    u.subtrait_used() + u.used() + u.used_through_sub_trait()
+}
+
+pub fn taking_v(v: &dyn V) -> i32 {
+    // CHECK: @llvm.type.checked.load({{.*}}, i32 24, metadata !"NtCsfRpWlKdQPZn_28virtual_function_elimination1V")
+    v.public_function()
+}
+
+pub fn main() {
+    let s = S;
+    taking_t(&s);
+    taking_rc_t(Rc::new(s));
+    taking_u(&s);
+    taking_v(&s);
+}
+
+// CHECK: ![[TYPE0]] = !{i64 0, !"[[MANGLED_TYPE0]]"}
+// CHECK: ![[VCALL_VIS0]] = !{i64 2}
+// CHECK: ![[TYPE1]] = !{i64 0, !"[[MANGLED_TYPE1]]"}
+// CHECK: ![[TYPE2]] = !{i64 0, !"NtCsfRpWlKdQPZn_28virtual_function_elimination1V"}
+// CHECK: ![[VCALL_VIS2]] = !{i64 1}