[ThinLTO/WPD] Handle function alias in vtable correctly

[tejohnson]

Summary

We were not summarizing a function alias in the vtable, leading to
incorrect WPD in some cases, and missing WPD in others.

Specifically, we would end up ignoring function aliases as they aren't
summarized, so we could incorrectly devirtualize if there was a single
other non-alias function in a compatible vtable. And if there was only
one implementation, but it was an alias, we would not be able to
identify and perform the single implementation devirtualization.

Handling the alias summary correctly also required fixing the handling
in mustBeUnreachableFunction, so that it is not incorrectly ignored.

Regular LTO is conservatively correct because it will skip
devirtualizing when any pointer within a vtable is not a function.
However, it needs additional work to be able to take advantage of
function alias within the vtable that is in fact the only
implementation. For that reason, the Regular LTO testing in the second
test case is currently disabled, and will be enabled along with a follow
on enhancement fix for Regular LTO WPD.

[mingmingl]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

380–382

399–402

For my understanding, is this conservative change orthogonal with function aliases in vtable (since auto *FS = dyn_cast<FunctionSummary>(Summary->getBaseObject()) should be true for an alias)?

llvm/test/ThinLTO/X86/devirt_function_alias.ll

27

48

63

[xur]

LGTM.

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

399–402

It's related, but not strictly necessary for this case now that we get the base object of the summary a couple lines above. Without either of these fixes, we would incorrectly return true from this function for an alias.

llvm/test/ThinLTO/X86/devirt_function_alias.ll

27

It was on purpose because I was trying to match both "devirtualized" and "Devirtualized" (there are multiple messages on success, one is capitalized and the other isn't. I made this more explicit in the pattern.

48

see above

63

see above

[tejohnson]

Address comments

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

 /// the vtable initializer is \p StartingOffset. Any discovered function
 /// pointers are added to \p VTableFuncs along with their cumulative offset
 /// within the initializer.
 static void findFuncPointers(const Constant *I, uint64_t StartingOffset,
                              const Module &M, ModuleSummaryIndex &Index,
                              VTableFuncList &VTableFuncs) {
   // First check if this is a function pointer.
   if (I->getType()->isPointerTy()) {
-    auto Fn = dyn_cast<Function>(I->stripPointerCasts());
+    auto C = I->stripPointerCasts();
+    auto A = dyn_cast<GlobalAlias>(C);
+    if (isa<Function>(C) || (A && isa<Function>(A->getAliasee()))) {
+      auto GV = dyn_cast<GlobalValue>(C);
+      assert(GV);
       // We can disregard __cxa_pure_virtual as a possible call target, as
       // calls to pure virtuals are UB.
-    if (Fn && Fn->getName() != "__cxa_pure_virtual")
-      VTableFuncs.push_back({Index.getOrInsertValueInfo(Fn), StartingOffset});
+      if (GV && GV->getName() != "__cxa_pure_virtual")
+        VTableFuncs.push_back({Index.getOrInsertValueInfo(GV), StartingOffset});
       return;
     }
+  }
 
   // Walk through the elements in the constant struct or array and recursively
   // look for virtual function pointers.
   const DataLayout &DL = M.getDataLayout();
   if (auto *C = dyn_cast<ConstantStruct>(I)) {
     StructType *STy = dyn_cast<StructType>(C->getType());
     assert(STy);
     const StructLayout *SL = DL.getStructLayout(C->getType());

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

 } // end namespace llvm
 
 namespace {
 
 // Returns true if the function must be unreachable based on ValueInfo.
 //
 // In particular, identifies a function as unreachable in the following
 // conditions
 //   1) All summaries are live.
 //   2) All function summaries indicate it's unreachable
+//   3) There is no non-function with the same GUID (which is rare)
 bool mustBeUnreachableFunction(ValueInfo TheFnVI) {
   if ((!TheFnVI) || TheFnVI.getSummaryList().empty()) {
     // Returns false if ValueInfo is absent, or the summary list is empty
     // (e.g., function declarations).
     return false;
   }
 
   for (const auto &Summary : TheFnVI.getSummaryList()) {
     // Conservatively returns false if any non-live functions are seen.
     // In general either all summaries should be live or all should be dead.
     if (!Summary->isLive())
       return false;
-    if (auto *FS = dyn_cast<FunctionSummary>(Summary.get())) {
+    if (auto *FS = dyn_cast<FunctionSummary>(Summary->getBaseObject())) {
       if (!FS->fflags().MustBeUnreachable)
         return false;
     }
-    // Do nothing if a non-function has the same GUID (which is rare).
-    // This is correct since non-function summaries are not relevant.
+    // Be conservative if a non-function has the same GUID (which is rare).
+    else
+      return false;
   }
   // All function summaries are live and all of them agree that the function is
   // unreachble.
   return true;
 }
 
 // A virtual call site. VTable is the loaded virtual table pointer, and CS is
 // the indirect virtual call.
 struct VirtualCallSite {

llvm/test/ThinLTO/X86/devirt_function_alias.ll

+; REQUIRES: x86-registered-target
+
+;; Ensure we don't incorrectly devirtualization when one vtable contains an
+;; alias (i.e. ensure analysis does not improperly ignore this implementation).
+
+;; Test pure ThinLTO
+
+;; Generate unsplit module with summary for ThinLTO index-based WPD.
+; RUN: opt -thinlto-bc -o %t1.o %s
+
+;; Check that we have properly recorded the alias in the vtable summary.
+; RUN llvm-dis -o - %t1.o | FileCheck %s --check-prefix SUMMARY
+; SUMMARY: gv: (name: "_ZTV1D", {{.*}} vTableFuncs: ((virtFunc: ^[[ALIAS:([0-9]+)]], offset: 16))
+; SUMMARY: ^[[ALIAS]] = gv: (name: "_ZN1D1mEiAlias"
+
+; RUN: llvm-lto2 run %t1.o -save-temps -pass-remarks=. \
+; RUN:   -whole-program-visibility \
+; RUN:   -wholeprogramdevirt-print-index-based \
+; RUN:   -o %t2 \
+; RUN:   -r=%t1.o,test,px \
+; RUN:   -r=%t1.o,_ZTV1D,px \
+; RUN:   -r=%t1.o,_ZN1D1mEi,px \
+; RUN:   -r=%t1.o,_ZN1D1mEiAlias,px \
+; RUN:   -r=%t1.o,_ZTV1B,px \
+; RUN:   -r=%t1.o,_ZN1B1mEi,px \
+; RUN:   2>&1 | FileCheck %s --implicit-check-not {{[Dd]}}evirtualized --allow-empty
+; RUN: llvm-dis %t2.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+;; Test hybrid Thin/Regular LTO
+
+;; Generate split module with summary for hybrid Thin/Regular LTO WPD.
+; RUN: opt -thinlto-bc -thinlto-split-lto-unit -o %t3.o %s
+
+; RUN: llvm-lto2 run %t3.o -save-temps -pass-remarks=. \
+; RUN:   -whole-program-visibility \
+; RUN:   -o %t4 \
+; RUN:   -r=%t3.o,test,px \
+; RUN:   -r=%t3.o,_ZTV1D, \
+; RUN:   -r=%t3.o,_ZTV1D,px \
+; RUN:   -r=%t3.o,_ZN1D1mEi,px \
+; RUN:   -r=%t3.o,_ZN1D1mEiAlias,px \
+; RUN:   -r=%t3.o,_ZN1D1mEiAlias, \
+; RUN:   -r=%t3.o,_ZTV1B, \
+; RUN:   -r=%t3.o,_ZTV1B,px \
+; RUN:   -r=%t3.o,_ZN1B1mEi,px \
+; RUN:   -r=%t3.o,_ZN1B1mEi, \
+; RUN:   2>&1 | FileCheck %s --implicit-check-not {{[Dd]}}evirtualized --allow-empty
+; RUN: llvm-dis %t4.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+;; Test Regular LTO
+
+; RUN: opt -o %t5.o %s
+; RUN: llvm-lto2 run %t5.o -save-temps -pass-remarks=. \
+; RUN:   -whole-program-visibility \
+; RUN:   -o %t6 \
+; RUN:   -r=%t5.o,test,px \
+; RUN:   -r=%t5.o,_ZTV1D,px \
+; RUN:   -r=%t5.o,_ZN1D1mEi,px \
+; RUN:   -r=%t5.o,_ZN1D1mEiAlias,px \
+; RUN:   -r=%t5.o,_ZTV1B,px \
+; RUN:   -r=%t5.o,_ZN1B1mEi,px \
+; RUN:   2>&1 | FileCheck %s --implicit-check-not {{[Dd]}}evirtualized --allow-empty
+; RUN: llvm-dis %t6.0.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+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.D = type { ptr }
+%struct.B = type { %struct.D }
+
+@_ZTV1D = constant { [3 x ptr] } { [3 x ptr] [ptr null, ptr undef, ptr @_ZN1D1mEiAlias] }, !type !0
+@_ZTV1B = constant { [3 x ptr] } { [3 x ptr] [ptr null, ptr undef, ptr @_ZN1B1mEi] }, !type !0, !type !1
+
+
+define i32 @_ZN1D1mEi(ptr %this, i32 %a) {
+   ret i32 0;
+}
+
+@_ZN1D1mEiAlias = unnamed_addr alias i32 (ptr, i32), ptr @_ZN1D1mEi
+
+define i32 @_ZN1B1mEi(ptr %this, i32 %a) {
+   ret i32 0;
+}
+
+; CHECK-IR-LABEL: define i32 @test
+define i32 @test(ptr %obj2, i32 %a) {
+entry:
+  %vtable2 = load ptr, ptr %obj2
+  %p2 = call i1 @llvm.type.test(ptr %vtable2, metadata !"_ZTS1D")
+  call void @llvm.assume(i1 %p2)
+
+  %fptr33 = load ptr, ptr %vtable2, align 8
+
+  ;; Confirm the call was not devirtualized.
+  ;; CHECK-IR: %call4 = tail call i32 %fptr33
+  %call4 = tail call i32 %fptr33(ptr nonnull %obj2, i32 %a)
+  ret i32 %call4
+}
+; CHECK-IR-LABEL: ret i32
+; CHECK-IR-LABEL: }
+
+declare i1 @llvm.type.test(ptr, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{i64 16, !"_ZTS1D"}
+!1 = !{i64 16, !"_ZTS1B"}

llvm/test/ThinLTO/X86/devirt_function_alias2.ll

+; REQUIRES: x86-registered-target
+
+;; Check for successful devirtualization when vtable contains an alias,
+;; and there is a single implementation.
+
+;; Test pure ThinLTO
+
+;; Generate unsplit module with summary for ThinLTO index-based WPD.
+; RUN: opt -thinlto-bc -o %t1.o %s
+
+;; Check that we have properly recorded the alias in the vtable summary.
+; RUN: llvm-dis -o - %t1.o | FileCheck %s --check-prefix SUMMARY
+; SUMMARY: gv: (name: "_ZTV1D", {{.*}} vTableFuncs: ((virtFunc: ^[[ALIAS:([0-9]+)]], offset: 16))
+; SUMMARY: ^[[ALIAS]] = gv: (name: "_ZN1D1mEiAlias"
+
+; RUN: llvm-lto2 run %t1.o -save-temps -pass-remarks=. \
+; RUN:   -whole-program-visibility \
+; RUN:   -wholeprogramdevirt-print-index-based \
+; RUN:   -o %t2 \
+; RUN:   -r=%t1.o,test,px \
+; RUN:   -r=%t1.o,_ZTV1D,px \
+; RUN:   -r=%t1.o,_ZN1D1mEi,px \
+; RUN:   -r=%t1.o,_ZN1D1mEiAlias,px \
+; RUN:   2>&1 | FileCheck %s --check-prefix=REMARK --check-prefix=PRINT
+; RUN: llvm-dis %t2.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR1
+
+; PRINT-DAG: Devirtualized call to {{.*}} (_ZN1D1mEiAlias)
+; REMARK-DAG: single-impl: devirtualized a call to _ZN1D1mEiAlias
+
+;; Test hybrid Thin/Regular LTO
+
+;; Generate split module with summary for hybrid Thin/Regular LTO WPD.
+; RUN: opt -thinlto-bc -thinlto-split-lto-unit -o %t3.o %s
+
+; RUN: llvm-lto2 run %t3.o -save-temps -pass-remarks=. \
+; RUN:   -whole-program-visibility \
+; RUN:   -o %t4 \
+; RUN:   -r=%t3.o,test,px \
+; RUN:   -r=%t3.o,_ZTV1D, \
+; RUN:   -r=%t3.o,_ZTV1D,px \
+; RUN:   -r=%t3.o,_ZN1D1mEi,px \
+; RUN:   -r=%t3.o,_ZN1D1mEiAlias,px \
+; RUN:   -r=%t3.o,_ZN1D1mEiAlias, \
+; RUN:   2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t4.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR1
+
+;; TODO: Enable the below lines once Regular LTO support for devirtualizing
+;; aliases in the vtable is supported.
+;; Test Regular LTO
+; RUN opt -o %t5.o %s
+; RUN llvm-lto2 run %t5.o -save-temps -pass-remarks=. \
+; RUN   -whole-program-visibility \
+; RUN   -o %t6 \
+; RUN   -r=%t5.o,test,px \
+; RUN   -r=%t5.o,_ZTV1D,px \
+; RUN   -r=%t5.o,_ZN1D1mEi,px \
+; RUN   -r=%t5.o,_ZN1D1mEiAlias,px \
+; RUN   2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN llvm-dis %t6.0.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR1
+
+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.D = type { ptr }
+
+@_ZTV1D = constant { [3 x ptr] } { [3 x ptr] [ptr null, ptr undef, ptr @_ZN1D1mEiAlias] }, !type !3
+
+define i32 @_ZN1D1mEi(ptr %this, i32 %a) {
+   ret i32 0;
+}
+
+@_ZN1D1mEiAlias = unnamed_addr alias i32 (ptr, i32), ptr @_ZN1D1mEi
+
+; CHECK-IR1-LABEL: define i32 @test
+define i32 @test(ptr %obj2, i32 %a) {
+entry:
+  %vtable2 = load ptr, ptr %obj2
+  %p2 = call i1 @llvm.type.test(ptr %vtable2, metadata !"_ZTS1D")
+  call void @llvm.assume(i1 %p2)
+
+  %fptr33 = load ptr, ptr %vtable2, align 8
+
+  ;; Check that the call was devirtualized.
+  ;; CHECK-IR1: %call4 = tail call i32 @_ZN1D1mEi
+  %call4 = tail call i32 %fptr33(ptr nonnull %obj2, i32 %a)
+  ret i32 %call4
+}
+; CHECK-IR1-LABEL: ret i32
+; CHECK-IR1-LABEL: }
+
+declare i1 @llvm.type.test(ptr, metadata)
+declare void @llvm.assume(i1)
+
+!3 = !{i64 16, !"_ZTS1D"}