[WPD][lld] Test handling of vtable definition from shared libraries

[tejohnson]

Summary

Adds a lld test for a case that the handling added for dynamically
exported symbols in 1487747e990ce9f8851f3d92c3006a74134d7518 already
fixes. Because isExportDynamic returns true when the symbol is
SharedKind with default visibility, it will treat as dynamically
exported and block devirtualization when the definition of a vtable
comes from a shared library. This is desireable as it is dangerous to
devirtualize in that case, since there could be hidden overrides in the
shared library. Typically that happens when the shared library header
contains available externally definitions, which applications can
override. An example is std::error_category, which is overridden in LLVM
and causing failures after a self build with WPD enabled, because
libstdc++ contains hidden overrides of the virtual base class methods.

The regular LTO case in the new test already worked, but there are
2 fixes in this patch needed for the index-only case and the hybrid
LTO case. For the index-only case, WPD should not simply ignore
available externally vtables. A follow on fix will be made to clang to
emit type metadata for those vtables, which the new test is modeling.
For the hybrid case, we need to ensure when the module is split that any
llvm.*used globals are cloned to the regular LTO split module so
available externally vtable definitions are not prematurely deleted.

Another follow on fix will add the equivalent gold test, which requires
a small fix to the plugin to treat symbols in dynamic libraries the same
way lld already is.

[MaskRay]

(I did not know much about WholeProgramDevirt but I did spend some time to get an idea what the pass does.)

Just adding the following code

if (!VS)
      return false;

without introducing CurVS can make the new test pass as well. Is the CurVS change needed?

Also, regarding if (!VS) return false;, can TargetsForSlot.push_back(VTP.FuncVI); add an element in a previous iteration before if (!VS) return false; triggers?

lld/test/ELF/lto/devirt_vcall_vis_shared_def.ll

18

Nit: not reusing the same output filename for different opt commands may make debugging easier.

While debugging this to understand what happens, I need to run a specific ld.lld command and have to confirm the %t1.o object file is produced by the desired opt command...

35

%t5.o is the same as %t2.o

41

FileCheck /dev/null ... --allow-empty can be replaced by count 0

91

Drop ;

ditto below

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1024

(I did not have WholeProgramDevirt but I did spend some time to get an idea what the pass does.)

Just adding the following code

if (!VS)
      return false;

without introducing CurVS can make the new test pass as well. Is the CurVS change needed?

[tejohnson]

I've addressed all the test suggestions, reply to the source code question below.

In D96721#2564767, @MaskRay wrote:

(I did not know much about WholeProgramDevirt but I did spend some time to get an idea what the pass does.)

Thanks!

Just adding the following code

if (!VS)
      return false;

without introducing CurVS can make the new test pass as well. Is the CurVS change needed?

Probably, but comment further below about why I think this change is still good to have.

Also, regarding if (!VS) return false;, can TargetsForSlot.push_back(VTP.FuncVI); add an element in a previous iteration before if (!VS) return false; triggers?

It could, for another vtable compatible with the current type id, but it will be ignored. The caller doesn't do anything with TargetsForSlot if this method returns false.

lld/test/ELF/lto/devirt_vcall_vis_shared_def.ll

18

Modified everything to be unique.

35

Yep, and with the unique names used now I can also avoid re-doing the rest of the opt invocations below.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1024

For correctness reasons, I think you are right in that we could probably just ignore all available_externally vtables associated with the current type id - if we only have available_externally copies of a particular vtable then there's no way we should promote. But after thinking through this some more, it makes sense to use the new check I've added there for compile time reasons - if we have many copies of an available_externally vtable (possible since this may come from a header that is widely included), if the symbol is defined in a library and was thus marked ExternDynamic, with the new code we don't waste time walking through all copies but will return false early on the first copy (which will have public visibility).

[tejohnson]

Address comments in test

lld/test/ELF/lto/Inputs/devirt_vcall_vis_shared_def.ll

+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+%struct.A = type { i32 (...)** }
+
+@_ZTV1A = unnamed_addr constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1fEi to i8*), i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1nEi to i8*)] }, !type !0, !vcall_visibility !1
+
+define i32 @_ZN1A1fEi(%struct.A* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+define i32 @_ZN1A1nEi(%struct.A* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+attributes #0 = { noinline optnone }
+
+!0 = !{i64 16, !"_ZTS1A"}
+!1 = !{i64 0}

lld/test/ELF/lto/devirt_vcall_vis_shared_def.ll

+; REQUIRES: x86
+;; Test that symbols defined in shared libraries prevent devirtualization.
+
+;; First check that we get devirtualization when the defs are in the
+;; LTO unit.
+
+;; Index based WPD
+;; Generate unsplit module with summary for ThinLTO index-based WPD.
+; RUN: opt --thinlto-bc -o %t1a.o %s
+; RUN: opt --thinlto-bc -o %t2a.o %S/Inputs/devirt_vcall_vis_shared_def.ll
+; RUN: ld.lld %t1a.o %t2a.o -o %t3a -save-temps --lto-whole-program-visibility \
+; RUN:   -mllvm -pass-remarks=. 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t1a.o.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+;; Hybrid WPD
+;; Generate split module with summary for hybrid Thin/Regular LTO WPD.
+; RUN: opt --thinlto-bc --thinlto-split-lto-unit -o %t1b.o %s
+; RUN: opt --thinlto-bc --thinlto-split-lto-unit -o %t2b.o %S/Inputs/devirt_vcall_vis_shared_def.ll
+; RUN: ld.lld %t1b.o %t2b.o -o %t3b -save-temps --lto-whole-program-visibility \
+; RUN:   -mllvm -pass-remarks=. 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t1b.o.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+;; Regular LTO WPD
+; RUN: opt -o %t1c.o %s
+; RUN: opt -o %t2c.o %S/Inputs/devirt_vcall_vis_shared_def.ll
+; RUN: ld.lld %t1c.o %t2c.o -o %t3c -save-temps --lto-whole-program-visibility \
+; RUN:   -mllvm -pass-remarks=. 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t3c.0.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+; REMARK-DAG: single-impl: devirtualized a call to _ZN1A1nEi
+
+;; Check that WPD fails with when linking against a shared library
+;; containing the strong defs of the vtables.
+; RUN: ld.lld %t2c.o -o %t.so -shared
+
+;; Index based WPD
+; RUN: ld.lld %t1a.o %t.so -o %t4a --lto-whole-program-visibility \
+; RUN:   -mllvm -pass-remarks=. 2>&1 | count 0
+
+;; Hybrid WPD
+; RUN: ld.lld %t1b.o %t.so -o %t4b --lto-whole-program-visibility \
+; RUN:   -mllvm -pass-remarks=. 2>&1 | count 0
+
+;; Regular LTO WPD
+; RUN: ld.lld %t1c.o %t.so -o %t4c --lto-whole-program-visibility \
+; RUN:   -mllvm -pass-remarks=. 2>&1 | count 0
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+%struct.A = type { i32 (...)** }
+%struct.B = type { %struct.A }
+
+@_ZTV1A = available_externally unnamed_addr constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1fEi to i8*), i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1nEi to i8*)] }, !type !0, !vcall_visibility !2
+@_ZTV1B = linkonce_odr unnamed_addr constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.B*, i32)* @_ZN1B1fEi to i8*), i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1nEi to i8*)] }, !type !0, !type !1, !vcall_visibility !2
+
+;; Prevent the vtables from being dead code eliminated.
[e-mail] = appending global [2 x i8*] [ i8* bitcast ( { [4 x i8*] }* @_ZTV1A to i8*), i8* bitcast ( { [4 x i8*] }* @_ZTV1B to i8*)]
+
+; CHECK-IR-LABEL: define dso_local i32 @_start
+define i32 @_start(%struct.A* %obj, i32 %a) {
+entry:
+  %0 = bitcast %struct.A* %obj to i8***
+  %vtable = load i8**, i8*** %0
+  %1 = bitcast i8** %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %1, metadata !"_ZTS1A")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr i8*, i8** %vtable, i32 1
+  %2 = bitcast i8** %fptrptr to i32 (%struct.A*, i32)**
+  %fptr1 = load i32 (%struct.A*, i32)*, i32 (%struct.A*, i32)** %2, align 8
+
+  ;; Check that the call was devirtualized.
+  ; CHECK-IR: %call = tail call i32 @_ZN1A1nEi
+  ; CHECK-NODEVIRT-IR: %call = tail call i32 %fptr1
+  %call = tail call i32 %fptr1(%struct.A* nonnull %obj, i32 %a)
+
+  ret i32 %call
+}
+; CHECK-IR-LABEL: ret i32
+; CHECK-IR-LABEL: }
+
+declare i1 @llvm.type.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+define available_externally i32 @_ZN1A1fEi(%struct.A* %this, i32 %a) #0 {
+   ret i32 0
+}
+
+define available_externally i32 @_ZN1A1nEi(%struct.A* %this, i32 %a) #0 {
+   ret i32 0
+}
+
+define linkonce_odr i32 @_ZN1B1fEi(%struct.B* %this, i32 %a) #0 {
+   ret i32 0
+}
+
+;; Make sure we don't inline or otherwise optimize out the direct calls.
+attributes #0 = { noinline optnone }
+
+!0 = !{i64 16, !"_ZTS1A"}
+!1 = !{i64 16, !"_ZTS1B"}
+!2 = !{i64 0}

llvm/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

if (HasTypeMetadata(&GV)) {
             computeFunctionBodyMemoryAccess(*F, AARGetter(*F)) == MAK_ReadNone)
           EligibleVirtualFns.insert(F);
       });
     }
 
   ValueToValueMapTy VMap;
   std::unique_ptr<Module> MergedM(
       CloneModule(M, VMap, [&](const GlobalValue *GV) -> bool {
+        // Clone any llvm.*used globals to ensure the included values are
+        // not deleted.
+        if (GV->getName() == "llvm.used" ||
+            GV->getName() == "llvm.compiler.used")
+          return true;
         if (const auto *C = GV->getComdat())
           if (MergedMComdats.count(C))
             return true;
         if (auto *F = dyn_cast<Function>(GV))
           return EligibleVirtualFns.count(F);
         if (auto *GVar = dyn_cast_or_null<GlobalVariable>(GV->getBaseObject()))
           return HasTypeMetadata(GVar);
         return false;

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

bool DevirtModule::tryFindVirtualCallTargets(
   // Give up if we couldn't find any targets.
   return !TargetsForSlot.empty();
 }
 
 bool DevirtIndex::tryFindVirtualCallTargets(
     std::vector<ValueInfo> &TargetsForSlot, const TypeIdCompatibleVtableInfo TIdInfo,
     uint64_t ByteOffset) {
   for (const TypeIdOffsetVtableInfo &P : TIdInfo) {
-    // Find the first non-available_externally linkage vtable initializer.
+    // Find a representative copy of the vtable initializer.
     // We can have multiple available_externally, linkonce_odr and weak_odr
-    // vtable initializers, however we want to skip available_externally as they
-    // do not have type metadata attached, and therefore the summary will not
+    // vtable initializers, however currently clang does not attach type
+    // metadata to available_externally, and therefore the summary will not
     // contain any vtable functions. We can also have multiple external
     // vtable initializers in the case of comdats, which we cannot check here.
     // The linker should give an error in this case.
     //
     // Also, handle the case of same-named local Vtables with the same path
     // and therefore the same GUID. This can happen if there isn't enough
     // distinguishing path when compiling the source file. In that case we
     // conservatively return false early.
     const GlobalVarSummary *VS = nullptr;
     bool LocalFound = false;
     for (auto &S : P.VTableVI.getSummaryList()) {
       if (GlobalValue::isLocalLinkage(S->linkage())) {
         if (LocalFound)
           return false;
         LocalFound = true;
       }
-      if (!GlobalValue::isAvailableExternallyLinkage(S->linkage())) {
-        VS = cast<GlobalVarSummary>(S->getBaseObject());
+      auto *CurVS = cast<GlobalVarSummary>(S->getBaseObject());
+      if (!CurVS->vTableFuncs().empty()) {
+        VS = CurVS;
         // We cannot perform whole program devirtualization analysis on a vtable
         // with public LTO visibility.
         if (VS->getVCallVisibility() == GlobalObject::VCallVisibilityPublic)
           return false;
-      }
-    }
+      } else
+        // Currently clang will not attach the necessary type metadata to
+        // available_externally vtables.
+        assert(GlobalValue::isAvailableExternallyLinkage(S->linkage()));
+    }
+    // There will be no VS if all copies are available_externally having no
+    // type metadata. In that case we can't safely perform WPD.
+    if (!VS)
+      return false;
     if (!VS->isLive())
       continue;
     for (auto VTP : VS->vTableFuncs()) {
       if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset)
         continue;
 
       TargetsForSlot.push_back(VTP.FuncVI);
     }