[CodeGenCXX] Add -fforce-emit-vtables

[Prazek]

Summary

In many cases we can't devirtualize
because definition of vtable is not present. Most of the
time it is caused by inline virtual function not beeing
emitted. Forcing emitting of vtable adds a reference of these
inline virtual functions.
Note that GCC was always doing it.

[Prazek]

Add release note

[Prazek]

remove empty line

[Prazek]

Fixed comment

[Prazek]

Fixed flag passing

[amharc]

This is not sound: sometimes the forcefully emitted vtable is incorrect due to destructor aliasing. This happens e.g. in the Bullet benchmark from the llvm test suite. A simplified example follows.

For a translation unit:

struct Base {
  virtual int foo() { return 42; }
  virtual ~Base() { }
};

struct Derived : Base {
  Derived();
};

int foo() {
  Derived *der = new Derived();
  return der->foo();
}

it emits:

; Function Attrs: nounwind
declare dso_local void @_ZN7DerivedD1Ev(%struct.Derived*) unnamed_addr #6

; Function Attrs: nounwind
declare dso_local void @_ZN7DerivedD0Ev(%struct.Derived*) unnamed_addr #6

@_ZTV7Derived = linkonce_odr dso_local unnamed_addr constant { [5 x i8*] } { [5 x i8*] [i8* null, i8* bitcast ({ i8*, i8*, i8* }* @_ZTI7Derived to i8*), i8* bitcast (i32 (%struct.Base*)* @_ZN4Base3fooEv to i8*), i8* bitcast (void (%struct.Derived*)* @_ZN7DerivedD1Ev to i8*), i8* bitcast (void (%struct.Derived*)* @_ZN7DerivedD0Ev to i8*)] }, comdat, align 8

whereas for TU:

struct Base {
  virtual int foo() { return 42; }
  virtual ~Base() { }
};

struct Derived : Base {
  Derived();
};

Derived::Derived() { }

which emits the whole vtable (even without this patch):

@_ZTV7Derived = linkonce_odr dso_local unnamed_addr constant { [5 x i8*] } { [5 x i8*] [i8* null, i8* bitcast ({ i8*, i8*, i8* }* @_ZTI7Derived to i8*), i8* bitcast (i32 (%struct.Base*)* @_ZN4Base3fooEv to i8*), i8* bitcast (void (%struct.Base*)* @_ZN4BaseD2Ev to i8*), i8* bitcast (void (%struct.Derived*)* @_ZN7DerivedD0Ev to i8*)] }, comdat, align 8

Please note that the complete object destructor @_ZN7DerivedD1Ev has been RAUWed with the base object destructor @_ZN4BaseD2Ev.
Since this triggers the RAUW case (as opposed to the Alias case) in ItaniumCXXABI::emitCXXStructor, the complete object destructor is not emitted at all.

Because Derived lacks a key function, the vtable is linkonce_odr and any of those definitions can be picked. Hence, this code can stop linking at the whim of the linker. :(

[amharc]

I think that MarkVTableUsed should be called somewhere in Sema (possibly ActOnFinishCXXMemberDecls?) if ForceEmitVTables is on. This probably requires making ForceEmitVTables a LangOption in addition to it being a CodeGenOption.

This causes the above example to compile correctly. Moreover, I have checked that 7zip and Bullet (the llvm test suite benchmarks which failed previously) build and execute correctly with the above change.

[Prazek]

@rjmccall do you have any thoughts on the best way to solve it?

[rjmccall]

I thought we already had places in Sema that marked inline virtual methods as used, instantiated templates, etc. for devirtualization purposes when optimization was enabled. Did we rip that out?

The problem we've had over and over with devirtualization is that we have to emit a perfect v-table because LLVM lacks a lot of the key vocabulary for talking about incomplete information. For example, if something weird happens and we don't have a definition for an inline virtual method, ideally we'd just say "well, you can't devirtualize this slot", then try to fix that as incremental progress; but instead we have to get everything just right or else disable the whole optimization. Note that vague-linkage v-tables mean that we'd also need to be able to say things like "there is an object with a definition that looks like this, but its symbol is not available and you can't emit it yourself".

[Prazek]

In D47108#1109014, @rjmccall wrote:

I thought we already had places in Sema that marked inline virtual methods as used, instantiated templates, etc. for devirtualization purposes when optimization was enabled. Did we rip that out?

I only recall the emitting available_externally vtables opportunistically, that is emitting it only if all the inline virtual functions are present (and they are not hidden).
(https://reviews.llvm.org/D33437)

The problem we've had over and over with devirtualization is that we have to emit a perfect v-table because LLVM lacks a lot of the key vocabulary for talking about incomplete information. For example, if something weird happens and we don't have a definition for an inline virtual method, ideally we'd just say "well, you can't devirtualize this slot", then try to fix that as incremental progress; but instead we have to get everything just right or else disable the whole optimization. Note that vague-linkage v-tables mean that we'd also need to be able to say things like "there is an object with a definition that looks like this, but its symbol is not available and you can't emit it yourself".

That is correcty, my intention was that this flag would cause all inline virtual functions to be emitted. Can you give a hint how to achieve this in the sane way?

[rjmccall]

In D47108#1109145, @Prazek wrote:

In D47108#1109014, @rjmccall wrote:

I thought we already had places in Sema that marked inline virtual methods as used, instantiated templates, etc. for devirtualization purposes when optimization was enabled. Did we rip that out?

I only recall the emitting available_externally vtables opportunistically, that is emitting it only if all the inline virtual functions are present (and they are not hidden).
(https://reviews.llvm.org/D33437)

The problem we've had over and over with devirtualization is that we have to emit a perfect v-table because LLVM lacks a lot of the key vocabulary for talking about incomplete information. For example, if something weird happens and we don't have a definition for an inline virtual method, ideally we'd just say "well, you can't devirtualize this slot", then try to fix that as incremental progress; but instead we have to get everything just right or else disable the whole optimization. Note that vague-linkage v-tables mean that we'd also need to be able to say things like "there is an object with a definition that looks like this, but its symbol is not available and you can't emit it yourself".

That is correcty, my intention was that this flag would cause all inline virtual functions to be emitted. Can you give a hint how to achieve this in the sane way?

Well, this paragraph was really a call for extending LLVM IR, which might be outside a reasonable scope for your summer project.

Building a v-table should itself cause inline functions to be emitted in IRGen as long as they've been properly marked for instantiation and use by Sema. I don't know the right place to ensure that that happens.

[Prazek]

Fixed missing vtable commponents

[Prazek]

small update

[amharc]

clang/test/CodeGenCXX/vtable-available-externally.cpp

445

This still uses _ZN6Test187DerivedD1Ev instead of _ZN6Test184BaseD2Ev, because the triple you selected is x86_64-apple-darwin10 and -mconstructor-aliases is off by default on Darwin.

I suggest you either add -mconstructor-aliases to the compiler invocation or change the triple to literally everything else than Darwin (or CUDA). Preferably the former, as it shows clearly what we want to test here.

[Prazek]

fixed test

[amharc]

Looks good to me. Obviously, you should wait for someone more competent than me to accept it, too.

[rsmith]

I would like to see a test that virtual function definitions are properly emitted for classes instantiated from templates (and in particular, that this triggers instantiation of such virtual member functions so they can be emitted). Other than that, this looks good to me.

[Prazek]

• Fixed templates

[rsmith]

LGTM with one change.

clang/include/clang/Basic/LangOptions.def

292 ↗

(On Diff #150735)

I don't think this is benign or even compatible: if we compile a PCH with this turned off, and then try to emit code using that PCH, we can miscompile due to having not marked the contents of a vtable as used. Please change this from BENIGN_LANGOPT to just LANGOPT.

clang/docs/ClangCommandLineReference.rst

 .. option:: -fvisibility=<arg>
 
 Set the default symbol visibility for all global declarations
 
 .. option:: -fwhole-program-vtables, -fno-whole-program-vtables
 
 Enables whole-program vtable optimization. Requires -flto
 
+.. option:: -fforce-emit-vtables, -fno-force-emit-vtables
+
+In order to improve devirtualization, forces emitting of vtables even in
+modules where it isn't necessary. It causes more inline virtual functions
+to be emitted.
+
 .. option:: -fwrapv, -fno-wrapv
 
 Treat signed integer overflow as two's complement
 
 .. option:: -fwritable-strings
 
 Store string literals as writable data
 

clang/docs/UsersManual.rst

.. option:: -f[no-]strict-float-cast-overflow
    of the target's native float-to-int conversion instructions.
 
 .. option:: -fwhole-program-vtables
 
    Enable whole-program vtable optimizations, such as single-implementation
    devirtualization and virtual constant propagation, for classes with
    :doc:`hidden LTO visibility <LTOVisibility>`. Requires ``-flto``.
 
+.. option:: -fforce-emit-vtables
+
+   In order to improve devirtualization, forces emitting of vtables even in
+   modules where it isn't necessary. It causes more inline virtual functions
+   to be emitted.
+
 .. option:: -fno-assume-sane-operator-new
 
    Don't assume that the C++'s new operator is sane.
 
    This option tells the compiler to do not assume that C++'s global
    new operator will always return a pointer that does not alias any
    other pointer when the function returns.
 

clang/include/clang/Driver/Options.td

 def fvisibility_ms_compat : Flag<["-"], "fvisibility-ms-compat">, Group<f_Group>,
   HelpText<"Give global types 'default' visibility and global functions and "
            "variables 'hidden' visibility by default">;
 def fwhole_program_vtables : Flag<["-"], "fwhole-program-vtables">, Group<f_Group>,
   Flags<[CoreOption, CC1Option]>,
   HelpText<"Enables whole-program vtable optimization. Requires -flto">;
 def fno_whole_program_vtables : Flag<["-"], "fno-whole-program-vtables">, Group<f_Group>,
   Flags<[CoreOption]>;
+def fforce_emit_vtables : Flag<["-"], "fforce-emit-vtables">, Group<f_Group>,
+    Flags<[CC1Option]>,
+    HelpText<"Emits more virtual tables to improve devirtualization">;
+def fno_force_emit_vtables : Flag<["-"], "fno-force-emit-vtables">, Group<f_Group>,
+  Flags<[CoreOption]>;
 def fwrapv : Flag<["-"], "fwrapv">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Treat signed integer overflow as two's complement">;
 def fwritable_strings : Flag<["-"], "fwritable-strings">, Group<f_Group>, Flags<[CC1Option]>,
   HelpText<"Store string literals as writable data">;
 def fzero_initialized_in_bss : Flag<["-"], "fzero-initialized-in-bss">, Group<f_Group>;
 def ffunction_sections : Flag<["-"], "ffunction-sections">, Group<f_Group>,
   Flags<[CC1Option]>,
   HelpText<"Place each function in its own section (ELF Only)">;

clang/include/clang/Frontend/CodeGenOptions.def

 /// Whether to emit .debug_gnu_pubnames section instead of .debug_pubnames.
 CODEGENOPT(GnuPubnames, 1, 0)
 
 CODEGENOPT(NoPLT, 1, 0)
 
 /// Whether to embed source in DWARF debug line section.
 CODEGENOPT(EmbedSource, 1, 0)
 
+/// Whether to emit all vtables
+CODEGENOPT(ForceEmitVTables, 1, 0)
+
+
 #undef CODEGENOPT
 #undef ENUM_CODEGENOPT
 #undef VALUE_CODEGENOPT
 

clang/lib/CodeGen/ItaniumCXXABI.cpp

 }
 
 bool ItaniumCXXABI::canSpeculativelyEmitVTable(const CXXRecordDecl *RD) const {
   // We don't emit available_externally vtables if we are in -fapple-kext mode
   // because kext mode does not permit devirtualization.
   if (CGM.getLangOpts().AppleKext)
     return false;
 
-  // If we don't have any not emitted inline virtual function, and if vtable is
-  // not hidden, then we are safe to emit available_externally copy of vtable.
+  // If vtable is hidden then it is not safe to emit available_externally
+  // copy of vtable.
+  if (isVTableHidden(RD))
+    return false;
+
+  if (CGM.getCodeGenOpts().ForceEmitVTables)
+    return true;
+
+  // If we don't have any not emitted inline virtual function then we are safe
+  // to emit available_externally copy of vtable.
   // FIXME we can still emit a copy of the vtable if we
   // can emit definition of the inline functions.
-  return !hasAnyUnusedVirtualInlineFunction(RD) && !isVTableHidden(RD);
+  return !hasAnyUnusedVirtualInlineFunction(RD);
 }
 static llvm::Value *performTypeAdjustment(CodeGenFunction &CGF,
                                           Address InitialPtr,
                                           int64_t NonVirtualAdjustment,
                                           int64_t VirtualAdjustment,
                                           bool IsReturnAdjustment) {
   if (!NonVirtualAdjustment && !VirtualAdjustment)
     return InitialPtr.getPointer();

clang/lib/Driver/ToolChains/Clang.cpp

if (!Args.hasFlag(options::OPT_fstrict_return, options::OPT_fno_strict_return,
     CmdArgs.push_back("-fno-strict-return");
   if (Args.hasFlag(options::OPT_fallow_editor_placeholders,
                    options::OPT_fno_allow_editor_placeholders, false))
     CmdArgs.push_back("-fallow-editor-placeholders");
   if (Args.hasFlag(options::OPT_fstrict_vtable_pointers,
                    options::OPT_fno_strict_vtable_pointers,
                    false))
     CmdArgs.push_back("-fstrict-vtable-pointers");
+  if (Args.hasFlag(options::OPT_fforce_emit_vtables,
+                   options::OPT_fno_force_emit_vtables,
+                   false))
+    CmdArgs.push_back("-fforce-emit-vtable");
   if (!Args.hasFlag(options::OPT_foptimize_sibling_calls,
                     options::OPT_fno_optimize_sibling_calls))
     CmdArgs.push_back("-mdisable-tail-calls");
   if (Args.hasFlag(options::OPT_fno_escaping_block_tail_calls,
                    options::OPT_fescaping_block_tail_calls, false))
     CmdArgs.push_back("-fno-escaping-block-tail-calls");
 
   Args.AddLastArg(CmdArgs, options::OPT_ffine_grained_bitfield_accesses,

clang/lib/Frontend/CompilerInvocation.cpp

static bool ParseCodeGenArgs(CodeGenOptions &Opts, ArgList &Args, InputKind IK,
   Opts.NoPLT = Args.hasArg(OPT_fno_plt);
   Opts.OmitLeafFramePointer = Args.hasArg(OPT_momit_leaf_frame_pointer);
   Opts.SaveTempLabels = Args.hasArg(OPT_msave_temp_labels);
   Opts.NoDwarfDirectoryAsm = Args.hasArg(OPT_fno_dwarf_directory_asm);
   Opts.SoftFloat = Args.hasArg(OPT_msoft_float);
   Opts.StrictEnums = Args.hasArg(OPT_fstrict_enums);
   Opts.StrictReturn = !Args.hasArg(OPT_fno_strict_return);
   Opts.StrictVTablePointers = Args.hasArg(OPT_fstrict_vtable_pointers);
+  Opts.ForceEmitVTables = Args.hasArg(OPT_fforce_emit_vtables);
   Opts.UnsafeFPMath = Args.hasArg(OPT_menable_unsafe_fp_math) ||
                       Args.hasArg(OPT_cl_unsafe_math_optimizations) ||
                       Args.hasArg(OPT_cl_fast_relaxed_math);
   Opts.UnwindTables = Args.hasArg(OPT_munwind_tables);
   Opts.RelocationModel = getRelocModel(Args, Diags);
   Opts.ThreadModel = Args.getLastArgValue(OPT_mthread_model, "posix");
   if (Opts.ThreadModel != "posix" && Opts.ThreadModel != "single")
     Diags.Report(diag::err_drv_invalid_value)

clang/test/CodeGenCXX/vtable-available-externally.cpp

 // RUN: %clang_cc1 %s -I%S -triple=x86_64-apple-darwin10 -std=c++98 -emit-llvm -o %t
 // RUN: %clang_cc1 %s -I%S -triple=x86_64-apple-darwin10 -std=c++98 -O2 -disable-llvm-passes -emit-llvm -o %t.opt
+// RUN: %clang_cc1 %s -I%S -triple=x86_64-apple-darwin10 -std=c++98 -O2 -disable-llvm-passes -emit-llvm -o %t.vtable -fforce-emit-vtables
 // RUN: FileCheck --check-prefix=CHECK-TEST1 %s < %t
 // RUN: FileCheck --check-prefix=CHECK-TEST2 %s < %t
 // RUN: FileCheck --check-prefix=CHECK-TEST5 %s < %t
 // RUN: FileCheck --check-prefix=CHECK-TEST8 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST9 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST10 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST11 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST12 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST13 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST14 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST15 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST16 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST17 %s < %t.opt
+// RUN: FileCheck --check-prefix=CHECK-FORCE-EMIT %s < %t.vtable
+
 
 #include <typeinfo>
 
 // CHECK-TEST1: @_ZTVN5Test11AE = external unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN5Test11AE = available_externally unnamed_addr constant
 namespace Test1 {
 
 struct A {
   A();
   virtual void f();
   virtual ~A() { }
 };
 

 }
 
 }  // Test9
 
 namespace Test10 {
 
 // because A's key function is defined here, vtable is generated in this TU
 // CHECK-TEST10-DAG: @_ZTVN6Test101AE = unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test101AE = unnamed_addr constant
 struct A {
   virtual void foo();
   virtual void bar();
 };
 void A::foo() {}
 
 // Because key function is inline we will generate vtable as linkonce_odr.
 // CHECK-TEST10-DAG: @_ZTVN6Test101DE = linkonce_odr unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test101DE = linkonce_odr unnamed_addr constant
 struct D : A {
   void bar();
 };
 inline void D::bar() {}
 
 // Because B has outline all virtual functions, we can refer to them.
 // CHECK-TEST10-DAG: @_ZTVN6Test101BE = available_externally unnamed_addr constant
 struct B : A {
   void foo();
   void bar();
 };
 
 // C's key function (car) is outline, but C has inline virtual function so we
 // can't guarantee that we will be able to refer to bar from name
 // so (at the moment) we can't emit vtable available_externally.
 // CHECK-TEST10-DAG: @_ZTVN6Test101CE = external unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test101CE = available_externally unnamed_addr constant
 struct C : A {
   void bar() {}               // defined in body - not key function
   virtual inline void gar();  // inline in body - not key function
   virtual void car();
 };
 
 // no key function, vtable will be generated everywhere it will be used
 // CHECK-TEST10-DAG: @_ZTVN6Test101EE = linkonce_odr unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test101EE = linkonce_odr unnamed_addr constant
+
 struct E : A {};
 
 void g(A& a) {
   a.foo();
   a.bar();
 }
 
 void f() {
void g() {
   d = f();
   g(d);
 }
 }  // Test 11
 
 namespace Test12 {
 
 // CHECK-TEST12: @_ZTVN6Test121AE = external unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test121AE = available_externally unnamed_addr constant
 struct A {
   virtual void foo();
   virtual ~A() {}
 };
 // CHECK-TEST12: @_ZTVN6Test121BE = external unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test121BE = available_externally unnamed_addr constant
 struct B : A {
   void foo();
 };
 
 void g() {
   A a;
   a.foo();
   B b;
   b.foo();
 }
 }
 
 namespace Test13 {
 
 // CHECK-TEST13-DAG: @_ZTVN6Test131AE = available_externally unnamed_addr constant
 // CHECK-TEST13-DAG: @_ZTVN6Test131BE = external unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test131AE = available_externally unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test131BE = available_externally unnamed_addr constant
+
 struct A {
   virtual ~A();
 };
 struct B : A {
   virtual void f();
   void operator delete(void *);
   ~B() {}
 };

 }
 }
 
 namespace Test16 {
 // S has virtual method that is hidden, because of it we can't
 // generate available_externally vtable for it.
 // CHECK-TEST16-DAG: @_ZTVN6Test161SE = external unnamed_addr constant
 // CHECK-TEST16-DAG: @_ZTVN6Test162S2E = available_externally
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test161SE = external unnamed_addr constant
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test162S2E = available_externally
 
 struct S {
   __attribute__((visibility("hidden"))) virtual void doStuff();
 };
 
 struct S2 {
   virtual void doStuff();
   __attribute__((visibility("hidden"))) void unused();
 
 };
 
 void test() {
   S *s = new S;
   s->doStuff();
 
   S2 *s2 = new S2;
   s2->doStuff();
 }
 }
 
 namespace Test17 {
 // This test checks if we emit vtables opportunistically.
 // CHECK-TEST17-DAG: @_ZTVN6Test171AE = available_externally
 // CHECK-TEST17-DAG: @_ZTVN6Test171BE = external
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test171AE = available_externally
+// CHECK-FORCE-EMIT-DAG: @_ZTVN6Test171BE = available_externally
+// CHECK-FORCE-EMIT-DAG: define linkonce_odr void @_ZN6Test171BD1Ev(
+// CHECK-FORCE-EMIT-DAG: define linkonce_odr void @_ZN6Test171BD0Ev(
 
 struct A {
   virtual void key();
   virtual void bar() {}
 };
 
 // We won't gonna use deleting destructor for this type, which will disallow
 // emitting vtable as available_externally
 struct B {
   virtual void key();
   virtual ~B() {}
 };
 
 void testcaseA() {
   A a;
   a.bar(); // this forces to emit definition of bar
 }
 
 void testcaseB() {
   B b; // This only forces emitting of complete object destructor
 }
 
 } // namespace Test17

clang/test/CodeGenCXX/vtable-linkage.cpp

 // RUN: %clang_cc1 %s -triple=x86_64-pc-linux -emit-llvm -o %t
 // RUN: %clang_cc1 %s -triple=x86_64-pc-linux -emit-llvm -std=c++03 -o %t.03
 // RUN: %clang_cc1 %s -triple=x86_64-pc-linux -emit-llvm -std=c++11 -o %t.11
+// RUN: %clang_cc1 %s -triple=x86_64-pc-linux -emit-llvm -std=c++11 -o %t.vtables -fforce-emit-vtables -O3
 // RUN: %clang_cc1 %s -triple=x86_64-apple-darwin10 -disable-llvm-passes -O3 -emit-llvm -o %t.opt
 // RUN: FileCheck %s < %t
 // RUN: FileCheck %s < %t.03
 // RUN: FileCheck %s < %t.11
 // RUN: FileCheck --check-prefix=CHECK-OPT %s < %t.opt
+// RUN: FileCheck --check-prefix=CHECK-OPT %s < %t.vtables
 
 namespace {
   struct A {
     virtual void f() { }
   };
 }
 
 void f() { A b; }