Support whole program devirtualization

[tmandry]

When doing LTO, LLVM supports a devirtualization pass that converts some indirect calls to static, inlineable calls. This can unlock a lot of optimizations when dynamic dispatch is used frequently in a program.

I don't know how hard this would be to support in Rust. Clang has a flag -fwhole-program-vtables which we would need to emulate. From there it seems like it might "just work". I'm opening this issue to start collecting more information.

I also found #11915 which mentions this, but not sure if any of the information there is still accurate.

[sanxiyn]

In LLVM terms, this means emitting type metadata and using llvm.type.test.

[flip1995]

I'd be interested to look into this issue. Since I'm not that familiar with this part of the compiler (but want to get more familiar with it) I first wanted to ask what would be involved in fixing this.

AFAICT to fix this, a flag would have to be added to the compiler and if that flag is set, (some) types would have to be marked with the !vcall_visibility metadata when lowering to LLVM IR. We should be able to query the visibility of items with the TyCtxt::visibility query which we would then use to convert to the corresponding !vcall_visibility like this:

rustc_middle::ty::Visibility	!vcall_visibility
Public	0 (Public)
Restricted	2 (Translation Unit)
Invisible	1 (Linkage Unit)

@tmandry could you give me some pointers where to start with this issue? Do you have an estimate how much work would be involved here?

[bjorn3]

rustc_middle::ty::Visibility	!vcall_visibility
[...]	[...]
Restricted	2 (Translation Unit)
Invisible	1 (Linkage Unit)

This is not correct. A trait marked as invisible or restricted can still used by a foreign codegen unit or a foreign shared library. For example if it is used by a public generic or #[inline] function. It can also be implemented for downstream types if there is a blanket implementation.

[flip1995]

Ah right of course, so it has to depend on the visibility of the trait and its implementors. So if the trait is public, or if there are any generics involved or blanket impls exist, than it should be marked as !vcall_visibility=0 (pub). But if the trait is not public and only specific implementations exist and the types of those specific impls are restricted, translation unit or linkage unit could be chosen.

[Aaron1011]

It looks like we're already getting some form of this for free. The following code:

trait Foo {
    fn my_method(&self) {}
}

impl Foo for bool {
    fn my_method(&self) {
        std::process::abort();
    }
}

#[inline(never)]
pub fn use_it(val: &dyn Foo) {
    val.my_method();
}

pub fn main() {
    use_it(&true);
}

results in the following optimized LLVM IR for use_it:

; playground::use_it
; Function Attrs: noinline noreturn nonlazybind uwtable
define internal fastcc void @_ZN10playground6use_it17h9abb7f0a088ea9f2E() unnamed_addr #4 {
start:
; call std::process::abort
  tail call void @_ZN3std7process5abort17h887d510ab1f66ceaE() #10
  unreachable
}

[bjorn3]

This only happens when use_it isn't public. Notice how the llvm ir for use_it doesn't have any arguments. I think LLVM propagates the argument into use_it as it is constant, sees a load of a function pointer from an immutable vtable, replaces the load with a constant representing the actual function pointer and then turns the indirect call to the function pointer into a regular direct call.

[hudson-ayers]

Using the code you shared, I still see a vtable in the final binary: https://rust.godbolt.org/z/qzb6o9MKG . Were you using a different version of Rust, or different set of compilation flags to achieve this?