[llvm] Teach GlobalDCE about dso_local_equivalent

[leonardchan]

Summary

This way, C++ relative-vtables can also participate in GlobalDCE. This depends on some TypeMetadataUtils.cpp bits in D134320, but that dependency can be removed and included here if necessary.

[leonardchan]

I only stumbled upon this from a brief comment in D134320 which led to D107645. AFAICT, there isn't an easy way to statically determine which optimizations would be interesting/operate on vtables in general. Are there perhaps other ones I should consider?

[leonardchan]

*ping* any comments on this?

[pcc]

LGTM

llvm/include/llvm/Analysis/TypeMetadataUtils.h

 ///   ) to i32)
 /// }
 ///
 /// For such (sub-)expressions, getPointerAtOffset returns the @target pointer.
 Constant *getPointerAtOffset(Constant *I, uint64_t Offset, Module &M,
                              Constant *TopLevelGlobal = nullptr);
 
 /// Finds the same "relative pointer" pattern as described above, where the
-/// target is `F`, and replaces the entire pattern with a constant zero.
-void replaceRelativePointerUsersWithZero(Function *F);
+/// target is `C`, and replaces the entire pattern with a constant zero.
+void replaceRelativePointerUsersWithZero(Constant *C);
 
 } // namespace llvm
 
 #endif

llvm/lib/Analysis/TypeMetadataUtils.cpp

if (auto *C = dyn_cast<ConstantExpr>(I)) {
     }
     default:
       return nullptr;
     }
   }
   return nullptr;
 }
 
-void llvm::replaceRelativePointerUsersWithZero(Function *F) {
-  for (auto *U : F->users()) {
-    auto *PtrExpr = dyn_cast<ConstantExpr>(U);
-    if (!PtrExpr || PtrExpr->getOpcode() != Instruction::PtrToInt)
-      continue;
+static void replaceRelativePointerUserWithZero(User *U) {
+    return;
 
-    for (auto *PtrToIntUser : PtrExpr->users()) {
-      auto *SubExpr = dyn_cast<ConstantExpr>(PtrToIntUser);
-      if (!SubExpr || SubExpr->getOpcode() != Instruction::Sub)
-        continue;
+      return;
 
-      SubExpr->replaceNonMetadataUsesWith(
-          ConstantInt::get(SubExpr->getType(), 0));
-    }
-  }
+
+void llvm::replaceRelativePointerUsersWithZero(Constant *C) {
+  for (auto *U : C->users()) {
+    if (auto *Equiv = dyn_cast<DSOLocalEquivalent>(U))
+      replaceRelativePointerUsersWithZero(Equiv);
+    else
+      replaceRelativePointerUserWithZero(U);
+  }
 }

llvm/test/Transforms/GlobalDCE/virtual-functions-relative-pointers-bad.ll

 ; RUN: opt < %s -passes=globaldce -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
-declare { i8*, i1 } @llvm.type.checked.load(i8*, i32, metadata)
+declare { ptr, i1 } @llvm.type.checked.load(ptr, i32, metadata)
 
 @vtable = internal unnamed_addr constant { [3 x i32] } { [3 x i32] [
-  i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc1              to i64), i64 ptrtoint ({ [3 x i32] }* @vtable to i64)) to i32),
-  i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc2              to i64), i64 ptrtoint ({ [3 x i32] }* @vtable to i64)) to i32),
+  i32 trunc (i64 sub (i64 ptrtoint (ptr @vfunc1              to i64), i64 ptrtoint (ptr @vtable to i64)) to i32),
+  i32 trunc (i64 sub (i64 ptrtoint (ptr @vfunc2              to i64), i64 ptrtoint (ptr @vtable to i64)) to i32),
 
   ; a "bad" relative pointer because it's base is not the @vtable symbol
-  i32 trunc (i64 sub (i64 ptrtoint (void ()* @weird_ref_1         to i64), i64 ptrtoint (void ()* @weird_ref_2 to i64)) to i32)
+  i32 trunc (i64 sub (i64 ptrtoint (ptr @weird_ref_1         to i64), i64 ptrtoint (ptr @weird_ref_2 to i64)) to i32)
 ]}, align 8, !type !0, !type !1, !vcall_visibility !{i64 2}
 !0 = !{i64 0, !"vfunc1.type"}
 !1 = !{i64 4, !"vfunc2.type"}
 
 ; CHECK:      @vtable = internal unnamed_addr constant { [3 x i32] } zeroinitializer, align 8, !type !0, !type !1, !vcall_visibility !2
 
+@vtable2 = internal unnamed_addr constant { [3 x i32] } { [3 x i32] [
+  i32 trunc (i64 sub (i64 ptrtoint (ptr dso_local_equivalent @vfunc3 to i64), i64 ptrtoint (ptr @vtable2 to i64)) to i32),
+  i32 trunc (i64 sub (i64 ptrtoint (ptr dso_local_equivalent @vfunc4 to i64), i64 ptrtoint (ptr @vtable2 to i64)) to i32),
+
+  ; a "bad" relative pointer because it's base is not the @vtable symbol
+  i32 trunc (i64 sub (i64 ptrtoint (ptr @weird_ref_3         to i64), i64 ptrtoint (ptr @weird_ref_4 to i64)) to i32)
+]}, align 4, !type !3, !type !4, !vcall_visibility !{i64 2}
+!3 = !{i64 0, !"vfunc3.type"}
+!4 = !{i64 4, !"vfunc4.type"}
+
+; CHECK:      @vtable2 = internal unnamed_addr constant { [3 x i32] } zeroinitializer, align 4, !type !3, !type !4, !vcall_visibility !2
+
 define internal void @vfunc1() { ret void }
 define internal void @vfunc2() { ret void }
 define internal void @weird_ref_1() { ret void }
 define internal void @weird_ref_2() { ret void }
+declare void @vfunc3()
+declare void @vfunc4()
+declare void @weird_ref_3()
+declare void @weird_ref_4()
 
 define void @main() {
-  %1 = ptrtoint { [3 x i32] }* @vtable to i64 ; to keep @vtable alive
+  %1 = ptrtoint ptr @vtable to i64 ; to keep @vtable alive
   call void @weird_ref_2()
+  %2 = ptrtoint ptr @vtable2 to i64 ; to keep @vtable2 alive
+  call void @weird_ref_4()
   ret void
 }
 
 !999 = !{i32 1, !"Virtual Function Elim", i32 1}
 !llvm.module.flags = !{!999}

llvm/test/Transforms/GlobalDCE/virtual-functions-relative-pointers-gep.ll

 ; RUN: opt < %s -passes='globaldce' -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
-declare { i8*, i1 } @llvm.type.checked.load(i8*, i32, metadata)
+declare { ptr, i1 } @llvm.type.checked.load(ptr, i32, metadata)
 
 ; A vtable with "relative pointers", slots don't contain pointers to implementations, but instead have an i32 offset from the vtable itself to the implementation.
 @vtable = internal unnamed_addr constant { [4 x i32] } { [4 x i32] [
   i32 42,
   i32 1337,
-  i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc1_live              to i64), i64 ptrtoint (i32* getelementptr inbounds ({ [4 x i32] }, { [4 x i32] }* @vtable, i32 0, i32 0, i32 2) to i64)) to i32),
-  i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc2_dead              to i64), i64 ptrtoint (i32* getelementptr inbounds ({ [4 x i32] }, { [4 x i32] }* @vtable, i32 0, i32 0, i32 2) to i64)) to i32)
+  i32 trunc (i64 sub (i64 ptrtoint (ptr @vfunc1_live              to i64), i64 ptrtoint (ptr getelementptr inbounds ({ [4 x i32] }, ptr @vtable, i32 0, i32 0, i32 2) to i64)) to i32),
+  i32 trunc (i64 sub (i64 ptrtoint (ptr @vfunc2_dead              to i64), i64 ptrtoint (ptr getelementptr inbounds ({ [4 x i32] }, ptr @vtable, i32 0, i32 0, i32 2) to i64)) to i32)
 ]}, align 8, !type !0, !type !1, !vcall_visibility !{i64 2}
 !0 = !{i64 8, !"vfunc1.type"}
 !1 = !{i64 12, !"vfunc2.type"}
 
 ; CHECK:      @vtable = internal unnamed_addr constant { [4 x i32] } { [4 x i32] [
-; CHECK-SAME:   i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc1_live              to i64), i64 ptrtoint (i32* getelementptr inbounds ({ [4 x i32] }, { [4 x i32] }* @vtable, i32 0, i32 0, i32 2) to i64)) to i32),
+; CHECK-SAME:   i32 trunc (i64 sub (i64 ptrtoint (ptr @vfunc1_live              to i64), i64 ptrtoint (ptr getelementptr inbounds ({ [4 x i32] }, ptr @vtable, i32 0, i32 0, i32 2) to i64)) to i32),
 ; CHECK-SAME:   i32 0
 ; CHECK-SAME: ] }, align 8, !type !0, !type !1, !vcall_visibility !2
 
+@vtable2 = internal unnamed_addr constant { [4 x i32] } { [4 x i32] [
+  i32 42,
+  i32 1337,
+  i32 trunc (i64 sub (i64 ptrtoint (ptr dso_local_equivalent @vfunc3_live_extern to i64), i64 ptrtoint (ptr getelementptr inbounds ({ [4 x i32] }, ptr @vtable2, i32 0, i32 0, i32 2) to i64)) to i32),
+  i32 trunc (i64 sub (i64 ptrtoint (ptr dso_local_equivalent @vfunc4_dead_extern to i64), i64 ptrtoint (ptr getelementptr inbounds ({ [4 x i32] }, ptr @vtable2, i32 0, i32 0, i32 2) to i64)) to i32)
+]}, align 4, !type !3, !type !4, !vcall_visibility !{i64 2}
+!3 = !{i64 8, !"vfunc3.type"}
+!4 = !{i64 12, !"vfunc4.type"}
+
+; CHECK:      @vtable2 = internal unnamed_addr constant { [4 x i32] } { [4 x i32] [
+; CHECK-SAME:   i32 trunc (i64 sub (i64 ptrtoint (ptr dso_local_equivalent @vfunc3_live_extern to i64), i64 ptrtoint (ptr getelementptr inbounds ({ [4 x i32] }, ptr @vtable2, i32 0, i32 0, i32 2) to i64)) to i32),
+; CHECK-SAME:   i32 0
+; CHECK-SAME: ] }, align 4, !type !3, !type !4, !vcall_visibility !2
+
 ; (1) vfunc1_live is referenced from @main, stays alive
 define internal void @vfunc1_live() {
   ; CHECK: define internal void @vfunc1_live(
   ret void
 }
 
 ; (2) vfunc2_dead is never referenced, gets removed and vtable slot is null'd
 define internal void @vfunc2_dead() {
   ; CHECK-NOT: define internal void @vfunc2_dead(
   ret void
 }
 
+; (3) vfunc3_live_extern is referenced from @main, stays alive
+; CHECK: declare void @vfunc3_live_extern
+declare void @vfunc3_live_extern()
+
+; (4) vfunc4_dead_extern is never referenced, gets removed and vtable slot is null'd
+; CHECK-NOT: declare void @vfunc4_dead_extern
+declare void @vfunc4_dead_extern()
+
 define void @main() {
-  %1 = ptrtoint { [4 x i32] }* @vtable to i64 ; to keep @vtable alive
-  %2 = tail call { i8*, i1 } @llvm.type.checked.load(i8* null, i32 0, metadata !"vfunc1.type")
+  %1 = ptrtoint ptr @vtable to i64 ; to keep @vtable alive
+  %2 = tail call { ptr, i1 } @llvm.type.checked.load(ptr null, i32 0, metadata !"vfunc1.type")
+  %3 = ptrtoint ptr @vtable2 to i64 ; to keep @vtable2 alive
+  %4 = tail call { ptr, i1 } @llvm.type.checked.load(ptr null, i32 0, metadata !"vfunc3.type")
   ret void
 }
 
 !999 = !{i32 1, !"Virtual Function Elim", i32 1}
 !llvm.module.flags = !{!999}

llvm/test/Transforms/GlobalDCE/virtual-functions-relative-pointers.ll

 ; RUN: opt < %s -passes=globaldce -S | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
-declare { i8*, i1 } @llvm.type.checked.load(i8*, i32, metadata)
+declare { ptr, i1 } @llvm.type.checked.load(ptr, i32, metadata)
 
 ; A vtable with "relative pointers", slots don't contain pointers to implementations, but instead have an i32 offset from the vtable itself to the implementation.
 @vtable = internal unnamed_addr constant { [2 x i32] } { [2 x i32] [
-  i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc1_live              to i64), i64 ptrtoint ({ [2 x i32] }* @vtable to i64)) to i32),
-  i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc2_dead              to i64), i64 ptrtoint ({ [2 x i32] }* @vtable to i64)) to i32)
+  i32 trunc (i64 sub (i64 ptrtoint (ptr @vfunc1_live              to i64), i64 ptrtoint (ptr @vtable to i64)) to i32),
+  i32 trunc (i64 sub (i64 ptrtoint (ptr @vfunc2_dead              to i64), i64 ptrtoint (ptr @vtable to i64)) to i32)
 ]}, align 8, !type !0, !type !1, !vcall_visibility !{i64 2}
 !0 = !{i64 0, !"vfunc1.type"}
 !1 = !{i64 4, !"vfunc2.type"}
 
 ; CHECK:      @vtable = internal unnamed_addr constant { [2 x i32] } { [2 x i32] [
-; CHECK-SAME:   i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc1_live              to i64), i64 ptrtoint ({ [2 x i32] }* @vtable to i64)) to i32),
+; CHECK-SAME:   i32 trunc (i64 sub (i64 ptrtoint (ptr @vfunc1_live              to i64), i64 ptrtoint (ptr @vtable to i64)) to i32),
 ; CHECK-SAME:   i32 0
 ; CHECK-SAME: ] }, align 8, !type !0, !type !1, !vcall_visibility !2
 
+; Similar to above, but the vtable is more aligned to how C++ relative vtables look.
+; That is, the functions may not be dso-local.
+@vtable2 = internal unnamed_addr constant { [2 x i32] } { [2 x i32] [
+  i32 trunc (i64 sub (i64 ptrtoint (ptr dso_local_equivalent @vfunc3_live_extern to i64), i64 ptrtoint (ptr @vtable2 to i64)) to i32),
+  i32 trunc (i64 sub (i64 ptrtoint (ptr dso_local_equivalent @vfunc4_dead_extern to i64), i64 ptrtoint (ptr @vtable2 to i64)) to i32)
+]}, align 4, !type !3, !type !4, !vcall_visibility !{i64 2}
+!3 = !{i64 0, !"vfunc3.type"}
+!4 = !{i64 4, !"vfunc4.type"}
+
+; CHECK:      @vtable2 = internal unnamed_addr constant { [2 x i32] } { [2 x i32] [
+; CHECK-SAME:   i32 trunc (i64 sub (i64 ptrtoint (ptr dso_local_equivalent @vfunc3_live_extern to i64), i64 ptrtoint (ptr @vtable2 to i64)) to i32),
+; CHECK-SAME:   i32 0
+; CHECK-SAME: ] }, align 4, !type !3, !type !4, !vcall_visibility !2
+
 ; (1) vfunc1_live is referenced from @main, stays alive
 define internal void @vfunc1_live() {
   ; CHECK: define internal void @vfunc1_live(
   ret void
 }
 
 ; (2) vfunc2_dead is never referenced, gets removed and vtable slot is null'd
 define internal void @vfunc2_dead() {
   ; CHECK-NOT: define internal void @vfunc2_dead(
   ret void
 }
 
+; (3) vfunc3_live_extern is referenced from @main, stays alive
+; CHECK: declare void @vfunc3_live_extern
+declare void @vfunc3_live_extern()
+
+; (4) vfunc4_dead_extern is never referenced, gets removed and vtable slot is null'd
+; CHECK-NOT: declare void @vfunc4_dead_extern
+declare void @vfunc4_dead_extern()
+
 define void @main() {
-  %1 = ptrtoint { [2 x i32] }* @vtable to i64 ; to keep @vtable alive
-  %2 = tail call { i8*, i1 } @llvm.type.checked.load(i8* null, i32 0, metadata !"vfunc1.type")
+  %1 = ptrtoint ptr @vtable to i64 ; to keep @vtable alive
+  %2 = tail call { ptr, i1 } @llvm.type.checked.load(ptr null, i32 0, metadata !"vfunc1.type")
+  %3 = ptrtoint ptr @vtable2 to i64 ; to keep @vtable2 alive
+  %4 = tail call { ptr, i1 } @llvm.type.checked.load(ptr null, i32 0, metadata !"vfunc3.type")
   ret void
 }
 
 !999 = !{i32 1, !"Virtual Function Elim", i32 1}
 !llvm.module.flags = !{!999}