HomePhabricator

Dead Virtual Function Elimination

Description

Dead Virtual Function Elimination

Currently, it is hard for the compiler to remove unused C++ virtual
functions, because they are all referenced from vtables, which are referenced
by constructors. This means that if the constructor is called from any live
code, then we keep every virtual function in the final link, even if there
are no call sites which can use it.

This patch allows unused virtual functions to be removed during LTO (and
regular compilation in limited circumstances) by using type metadata to match
virtual function call sites to the vtable slots they might load from. This
information can then be used in the global dead code elimination pass instead
of the references from vtables to virtual functions, to more accurately
determine which functions are reachable.

To make this transformation safe, I have changed clang's code-generation to
always load virtual function pointers using the llvm.type.checked.load
intrinsic, instead of regular load instructions. I originally tried writing
this using clang's existing code-generation, which uses the llvm.type.test
and llvm.assume intrinsics after doing a normal load. However, it is possible
for optimisations to obscure the relationship between the GEP, load and
llvm.type.test, causing GlobalDCE to fail to find virtual function call
sites.

The existing linkage and visibility types don't accurately describe the scope
in which a virtual call could be made which uses a given vtable. This is
wider than the visibility of the type itself, because a virtual function call
could be made using a more-visible base class. I've added a new
!vcall_visibility metadata type to represent this, described in
TypeMetadata.rst. The internalization pass and libLTO have been updated to
change this metadata when linking is performed.

This doesn't currently work with ThinLTO, because it needs to see every call
to llvm.type.checked.load in the linkage unit. It might be possible to
extend this optimisation to be able to use the ThinLTO summary, as was done
for devirtualization, but until then that combination is rejected in the
clang driver.

To test this, I've written a fuzzer which generates random C++ programs with
complex class inheritance graphs, and virtual functions called through object
and function pointers of different types. The programs are spread across
multiple translation units and DSOs to test the different visibility
restrictions.

I've also tried doing bootstrap builds of LLVM to test this. This isn't
ideal, because only classes in anonymous namespaces can be optimised with
-fvisibility=default, and some parts of LLVM (plugins and bugpoint) do not
work correctly with -fvisibility=hidden. However, there are only 12 test
failures when building with -fvisibility=hidden (and an unmodified compiler),
and this change does not cause any new failures for either value of
-fvisibility.

On the 7 C++ sub-benchmarks of SPEC2006, this gives a geomean code-size
reduction of ~6%, over a baseline compiled with "-O2 -flto
-fvisibility=hidden -fwhole-program-vtables". The best cases are reductions
of ~14% in 450.soplex and 483.xalancbmk, and there are no code size
increases.

I've also run this on a set of 8 mbed-os examples compiled for Armv7M, which
show a geomean size reduction of ~3%, again with no size increases.

I had hoped that this would have no effect on performance, which would allow
it to awlays be enabled (when using -fwhole-program-vtables). However, the
changes in clang to use the llvm.type.checked.load intrinsic are causing ~1%
performance regression in the C++ parts of SPEC2006. It should be possible to
recover some of this perf loss by teaching optimisations about the
llvm.type.checked.load intrinsic, which would make it worth turning this on
by default (though it's still dependent on -fwhole-program-vtables).

Differential revision: https://reviews.llvm.org/D63932

Details

Committed
ostannardOct 11 2019, 4:59 AM
Differential Revision
D63932: [GlobalDCE] Dead Virtual Function Elimination
Parents
rL374538: [FileCheck] Implement --ignore-case option.
Branches
Unknown
Tags
Unknown

Event Timeline

jgorbe added a subscriber: jgorbe.Oct 14 2019, 3:47 PM

Hi Oliver,

We have found a crash that bisects to this revision. A debug build fails an assertion here:

clang: /home/jgorbe/code/llvm/llvm/include/llvm/Support/Casting.h:264: typename llvm::cast_retty<X, Y*>::ret_type llvm::cast(Y*) [with X = llvm::Function; Y = llvm::Value; typename llvm::cast_retty<X, Y*>::ret_type = llvm::Function*]: Assertion `isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.
Stack dump:
0.	Program arguments: /home/jgorbe/code/llvm-build/bin/clang -cc1 -emit-obj -O3 -fexperimental-new-pass-manager /home/jgorbe/crash/repro.ll 
1.	Code generation

 #0 0x000055b26e932260 llvm::sys::PrintStackTrace(llvm::raw_ostream&) /home/jgorbe/code/llvm/llvm/lib/Support/Unix/Signals.inc:532:22
 #1 0x000055b26e9322f3 PrintStackTraceSignalHandler(void*) /home/jgorbe/code/llvm/llvm/lib/Support/Unix/Signals.inc:593:1
 #2 0x000055b26e930479 llvm::sys::RunSignalHandlers() /home/jgorbe/code/llvm/llvm/lib/Support/Signals.cpp:68:20
 #3 0x000055b26e931cdc SignalHandler(int) /home/jgorbe/code/llvm/llvm/lib/Support/Unix/Signals.inc:384:1
 #4 0x00007f43dc00e3a0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x123a0)
 #5 0x00007f43db09ccfb raise (/lib/x86_64-linux-gnu/libc.so.6+0x36cfb)
 #6 0x00007f43db0878ad abort (/lib/x86_64-linux-gnu/libc.so.6+0x218ad)
 #7 0x00007f43db08777f (/lib/x86_64-linux-gnu/libc.so.6+0x2177f)
 #8 0x00007f43db095542 (/lib/x86_64-linux-gnu/libc.so.6+0x2f542)
 #9 0x000055b26c251760 llvm::cast_retty<llvm::Function, llvm::Value*>::ret_type llvm::cast<llvm::Function, llvm::Value>(llvm::Value*) /home/jgorbe/code/llvm/llvm/include/llvm/Support/Casting.h:264:3
#10 0x000055b26de1cdcd llvm::TargetLoweringObjectFileELF::emitModuleMetadata(llvm::MCStreamer&, llvm::Module&) const::'lambda'(llvm::MDOperand const&)::operator()(llvm::MDOperand const&) const /home/jgorbe/code/llvm/llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp:333:39
#11 0x000055b26de1d618 llvm::TargetLoweringObjectFileELF::emitModuleMetadata(llvm::MCStreamer&, llvm::Module&) const /home/jgorbe/code/llvm/llvm/lib/CodeGen/TargetLoweringObjectFileImpl.cpp:339:34
#12 0x000055b26f8c9fa5 llvm::AsmPrinter::doFinalization(llvm::Module&) /home/jgorbe/code/llvm/llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp:1429:7
#13 0x000055b26e04604b llvm::FPPassManager::doFinalization(llvm::Module&) /home/jgorbe/code/llvm/llvm/lib/IR/LegacyPassManager.cpp:1702:13
#14 0x000055b26e04657d (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/jgorbe/code/llvm/llvm/lib/IR/LegacyPassManager.cpp:1778:13
#15 0x000055b26e046a93 llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/jgorbe/code/llvm/llvm/lib/IR/LegacyPassManager.cpp:1862:13
#16 0x000055b26e046c8b llvm::legacy::PassManager::run(llvm::Module&) /home/jgorbe/code/llvm/llvm/lib/IR/LegacyPassManager.cpp:1894:1
#17 0x000055b26f19cf36 (anonymous namespace)::EmitAssemblyHelper::EmitAssemblyWithNewPassManager(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) /home/jgorbe/code/llvm/clang/lib/CodeGen/BackendUtil.cpp:1329:55
#18 0x000055b26f19e6ec clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) /home/jgorbe/code/llvm/clang/lib/CodeGen/BackendUtil.cpp:1543:45
#19 0x000055b26f5be166 clang::CodeGenAction::ExecuteAction() /home/jgorbe/code/llvm/clang/lib/CodeGen/CodeGenAction.cpp:1080:22
#20 0x000055b26f45a0d1 clang::FrontendAction::Execute() /home/jgorbe/code/llvm/clang/lib/Frontend/FrontendAction.cpp:939:38
#21 0x000055b26f3a0697 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /home/jgorbe/code/llvm/clang/lib/Frontend/CompilerInstance.cpp:957:42
#22 0x000055b26f5ab2e2 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /home/jgorbe/code/llvm/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:290:38
#23 0x000055b26c1bb6fb cc1_main(llvm::ArrayRef<char const*>, char const*, void*) /home/jgorbe/code/llvm/clang/tools/driver/cc1_main.cpp:250:40
#24 0x000055b26c1b1669 ExecuteCC1Tool(llvm::ArrayRef<char const*>, llvm::StringRef) /home/jgorbe/code/llvm/clang/tools/driver/driver.cpp:309:64
#25 0x000055b26c1b1cbf main /home/jgorbe/code/llvm/clang/tools/driver/driver.cpp:382:26
#26 0x00007f43db08952b __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2352b)
#27 0x000055b26c1b002a _start (/home/jgorbe/code/llvm-build/bin/clang+0x8e3c02a)
{F10263089}

I'm going to go ahead and revert this patch. You should be able to reproduce the crash by running

clang  -cc1 -emit-obj -O3 -fexperimental-new-pass-manager repro.ll

on this reduced repro file. I hope the test case helps. Please let me know if you need anything else!