[GlobalDCE] In VFE, replace the whole 'sub' expression of unused relative-pointer-based vtable slots

[fhahn]

Could you elaborate on the motivation? If it is unused, it shouldn't matter what value we put in the slot, right?

[kubamracek]

Two distinct motivations:

1. Turns out that the "relative pointer" expression, if it gets a NULL pointer replaced into it...

i32 trunc (i64 sub (i64 0, i64 ptrtoint ({ [2 x i32] }* @vtable to i64)) to i32)

...becomes invalid as a relocation expression, and so it can't actually be lowered into machine instructions.

2. To make diagnosing possible miscompiles easier, because the crash will have a unique symbol name.

[pcc]

Maybe you can set the relative offset to 0 in this case? That way, the crashing PC will point to the vtable, which should make it easier to track down the source of any problems. This would also require no runtime support (so doesn't need to be behind a flag) and also saves a PLT slot if the trap function would be in another DSO.

[kubamracek]

Maybe you can set the relative offset to 0 in this case? That way, the crashing PC will point to the vtable, which should make it easier to track down the source of any problems. This would also require no runtime support (so doesn't need to be behind a flag) and also saves a PLT slot if the trap function would be in another DSO.

Yes, that's certainly a feasible option, too. Although, may I ask what is it you don't like about the trap function approach? The patch as it is emits the trap function into the current translation unit, so I think it'll never be in another DSO, and if yes then wouldn't that be an invalid relocation again (and defeat the purpose of this change)?

I am asking because I think the implementation of the "set offset to 0" would be more complicated and more invasive -- the F->replaceNonMetadataUsesWith() step would then need to "walk up" the expression somehow and replace the outer "i32 trunc" with an "i32 0", which does not necessarily need to be the top-level entry in the array (the vtable structure for Swift classes is more complex than just a array of pointers).

[pcc]

Oh right, I missed that you were emitting the function locally. So then replace "saves a PLT slot" with "saves emitting a trap function".

The PLT slot would be possible if it were an external function and you were using dso_local_equivalent to refer to it -- I'm not sure if you're doing that in Swift or even if the Mach-O side of that is implemented.

It seems that this should depend on what kind of relocation this is (absolute or relative), rather than a module flag. Because it's always possible that you'll want both modes in the same linkage unit (e.g. LTOing together C++ and Swift), and forcing everything to use the same mode will either produce invalid relocations or unnecessary relocations.

It doesn't seem too bad to look through the use list to find any ptrtoint references and then any sub references. At that point you can replace with 0, no need to look for the trunc as well.

[fhahn]

In D109114#2980673, @pcc wrote:

It doesn't seem too bad to look through the use list to find any ptrtoint references and then any sub references. At that point you can replace with 0, no need to look for the trunc as well.

This sounds like a good option to me as well!

llvm/test/Transforms/GlobalDCE/virtual-functions-trap.ll

4 ↗

(On Diff #370120)

can you add a comment why there are multiple run lines with different numbers of globaldce invocations?

[kubamracek]

llvm/test/Transforms/GlobalDCE/virtual-functions-trap.ll

4 ↗

(On Diff #370120)

I'm going to drop that, since it looks like the way forward is to avoid emitting the trap function. The explanation why it was there is that in a previous iteration of the trap-function approach, I didn't have the if (name == kTrapFunctionName) IgnoreDependency = false change in UpdateGVDependencies, which caused a funny bug: If GlobalDCE is run exactly once, it works, fine, but the second time it runs (and in a typical full optimization pipeline it does run multiple times), it tried to eliminate the trap call as well, causing a F->replaceNonMetadataUsesWith(F) call which is invalid and asserts.

[kubamracek]

Changing the title to reflect the change in direction of this patch.

[fhahn]

Thanks for the update! Could you update the patch description? it looks empty at the moment.

llvm/lib/Transforms/IPO/GlobalDCE.cpp

427

Would it be possible to either only iterate over all users if we know that there are relative pointers or iterate over all uses once and either replace the sub with zero or the use with nullptr?

429

Can the code here (matching ptrtoint/sub) be unified with the code that matches it in getPointerAtOffset, so those patterns won't diverge?

430

the assert here seems dangerous, as nothing guards against PtrExpr having multiple users, right? PtrExpr having multiple users is valid IR, so we should probably handle this gracefully.

[kubamracek]

Can the code here (matching ptrtoint/sub) be unified with the code that matches it in getPointerAtOffset, so those patterns won't diverge?

Suggestions how to do that? The code in getPointerAtOffset is quite different, because is recurses *down into* the expression, whereas here we need to walk up by looking at users. I could move the code to be next to each other, would that be good enough?

the assert here seems dangerous, as nothing guards against PtrExpr having multiple users, right? PtrExpr having multiple users is valid IR, so we should probably handle this gracefully.

I believe the assert actually holds. At this point, we know that F is *only* referenced from vtables (either one or more) and nothing else (otherwise it wouldn't be in DeadFunctions). F can have multiple users, if there's multiple vtables, but each use is a Constant/ConstantExpr in a vtable. Unless I misunderstand something, I believe in a ConstantExpr like trunc(sub(ptrtoint(x),ptrtoint(y)) all the nodes always have a unique single user and that's the parent ConstantExpr. Therefore the ptrtoint here, which must be in the vtable expression, must always have a single user.

[kubamracek]

Would it be possible to either only iterate over all users if we know that there are relative pointers or iterate over all uses once and either replace the sub with zero or the use with nullptr?

Attempted to do this, but it complicates the implementation. Not sure if the extra complexity is worth it (we only save an extra iteration over vtables, and presumably in realistic programs that's a limited amount of those).

[fhahn]

In D109114#3007693, @kubamracek wrote:

Can the code here (matching ptrtoint/sub) be unified with the code that matches it in getPointerAtOffset, so those patterns won't diverge?

Suggestions how to do that? The code in getPointerAtOffset is quite different, because is recurses *down into* the expression, whereas here we need to walk up by looking at users. I could move the code to be next to each other, would that be good enough?

Yeah moving the matcher code to a function might help, as well as moving them next to each other.

the assert here seems dangerous, as nothing guards against PtrExpr having multiple users, right? PtrExpr having multiple users is valid IR, so we should probably handle this gracefully.

I believe the assert actually holds. At this point, we know that F is *only* referenced from vtables (either one or more) and nothing else (otherwise it wouldn't be in DeadFunctions). F can have multiple users, if there's multiple vtables, but each use is a Constant/ConstantExpr in a vtable. Unless I misunderstand something, I believe in a ConstantExpr like trunc(sub(ptrtoint(x),ptrtoint(y)) all the nodes always have a unique single user and that's the parent ConstantExpr. Therefore the ptrtoint here, which must be in the vtable expression, must always have a single user.

Sounds good, can you add a message/comment to the assert?

In D109114#3007695, @kubamracek wrote:

Would it be possible to either only iterate over all users if we know that there are relative pointers or iterate over all uses once and either replace the sub with zero or the use with nullptr?

Attempted to do this, but it complicates the implementation. Not sure if the extra complexity is worth it (we only save an extra iteration over vtables, and presumably in realistic programs that's a limited amount of those).

Agreed that it might not be too important, I'm fine with either.

[kubamracek]

Yeah moving the matcher code to a function might help, as well as moving them next to each other.

Done.

Sounds good, can you add a message/comment to the assert?

Done.

Attempted to do this, but it complicates the implementation. Not sure if the extra complexity is worth it (we only save an extra iteration over vtables, and presumably in realistic programs that's a limited amount of those).

Agreed that it might not be too important, I'm fine with either.

Moved back to iterating over users twice, I think the benefits of avoiding the extra work are small and probably not worth the complexity.

[fhahn]

LGTM, thanks!

llvm/include/llvm/Analysis/TypeMetadataUtils.h

80

shouldn't this be ///?

llvm/lib/Analysis/TypeMetadataUtils.cpp

204

it might be worth turning some of those checks into early continues instead, to reduce the nesting level.

[fhahn]

llvm/lib/Analysis/TypeMetadataUtils.cpp

206

oh and just to double check, the assert was removed intentionally?

[kubamracek]

llvm/include/llvm/Analysis/TypeMetadataUtils.h

80

Fixed (and also fixed for getPointerAtOffset).

llvm/lib/Analysis/TypeMetadataUtils.cpp

204

Yes. Much better now :)

206

Yes, I dropped it intentionally, and replaced it with a loop over all users to be more conservative.

Actually, I did end up seeing the assert fail (!) in my testing on a large codebase (compiling the Swift stdlib with VFE on), but I couldn't figure out how to isolate the exact IR that could reproduce the problem. I guess I should try harder and add it as a lit testcase...

[kubamracek]

llvm/lib/Analysis/TypeMetadataUtils.cpp

206

Added "GlobalDCE/call-with-ptrtoint.ll" that triggers the assert -- in this case, we end up with a dead function that has a ptrtoint user, which itself has zero users (!), which I assume is an expected artifact of using GlobalDCE dropping all bodies of dead functions upfront. If unexpected, then it sounds like a separate bug.

In either case, I think dropping the assert and just iterating over all users of PtrExpr is the right approach here. It also makes this helper function more robust (as it doesn't assume the assert to hold).

[fhahn]

Thanks for the update. Still LGTM, but please wait a day or 2 with committing in case there are additional comments.

llvm/lib/Analysis/TypeMetadataUtils.cpp

204

I think you could also combine both checks if (!PtrExpr || PtrExpr->getOpcode() !=...) but that's a super tiny nit.

206

Ok thanks for clarifying & adding the test.

[kubamracek]

llvm/lib/Analysis/TypeMetadataUtils.cpp

204

Fixed!

[kubamracek]

Thanks for the review!

llvm/include/llvm/Analysis/TypeMetadataUtils.h

 #include "llvm/ADT/SmallVector.h"
 #include <cstdint>
 
 namespace llvm {
 
 class CallBase;
 class CallInst;
 class Constant;
+class Function;
 class DominatorTree;
 class Instruction;
 class Module;
 
 /// The type of CFI jumptable needed for a function.
 enum CfiFunctionLinkage {
   CFL_Definition = 0,
   CFL_Declaration = 1,

 /// Given a call to the intrinsic \@llvm.type.checked.load, find all
 /// devirtualizable call sites based on the call and return them in DevirtCalls.
 void findDevirtualizableCallsForTypeCheckedLoad(
     SmallVectorImpl<DevirtCallSite> &DevirtCalls,
     SmallVectorImpl<Instruction *> &LoadedPtrs,
     SmallVectorImpl<Instruction *> &Preds, bool &HasNonCallUses,
     const CallInst *CI, DominatorTree &DT);
 
-// Processes a Constant recursively looking into elements of arrays, structs and
-// expressions to find a trivial pointer element that is located at the given
-// offset (relative to the beginning of the whole outer Constant).
-//
-// Used for example from GlobalDCE to find an entry in a C++ vtable that matches
-// a vcall offset.
-//
-// To support Swift vtables, getPointerAtOffset can see through "relative
-// pointers", i.e. (sub-)expressions of the form of:
-//
-//   @symbol = ... {
-//     i32 trunc (i64 sub (
-//       i64 ptrtoint (<type> @target to i64), i64 ptrtoint (... @symbol to i64)
-//     ) to i32)
-//   }
-//
-// For such (sub-)expressions, getPointerAtOffset returns the @target pointer.
+/// Processes a Constant recursively looking into elements of arrays, structs
+/// and expressions to find a trivial pointer element that is located at the
+/// given offset (relative to the beginning of the whole outer Constant).
+///
+/// Used for example from GlobalDCE to find an entry in a C++ vtable that
+/// matches a vcall offset.
+///
+/// To support Swift vtables, getPointerAtOffset can see through "relative
+/// pointers", i.e. (sub-)expressions of the form of:
+///
+/// @symbol = ... {
+///   i32 trunc (i64 sub (
+///     i64 ptrtoint (<type> @target to i64), i64 ptrtoint (... @symbol to i64)
+///   ) 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);
+
+} // namespace llvm
 
 #endif

llvm/lib/Analysis/TypeMetadataUtils.cpp

case Instruction::Sub: {
       return getPointerAtOffset(Operand0, Offset, M, TopLevelGlobal);
     }
     default:
       return nullptr;
     }
   }
   return nullptr;
 }
+
+void llvm::replaceRelativePointerUsersWithZero(Function *F) {
+  for (auto *U : F->users()) {
+    auto *PtrExpr = dyn_cast<ConstantExpr>(U);
+    if (!PtrExpr)
+      continue;
+    if (PtrExpr->getOpcode() != Instruction::PtrToInt)
+      continue;
+
+    for (auto *PtrToIntUser : PtrExpr->users()) {
+      auto *SubExpr = dyn_cast<ConstantExpr>(PtrExpr->user_back());
+      if (!SubExpr)
+        continue;
+      if (SubExpr->getOpcode() != Instruction::Sub)
+        continue;
+
+      SubExpr->replaceNonMetadataUsesWith(
+          ConstantInt::get(SubExpr->getType(), 0));
+    }
+  }
+}

llvm/lib/Transforms/IPO/GlobalDCE.cpp

PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
   NumFunctions += DeadFunctions.size();
   for (Function *F : DeadFunctions) {
     if (!F->use_empty()) {
       // Virtual functions might still be referenced by one or more vtables,
       // but if we've proven them to be unused then it's safe to replace the
       // virtual function pointers with null, allowing us to remove the
       // function itself.
       ++NumVFuncs;
+
+      // Detect vfuncs that are referenced as "relative pointers" which are used
+      // in Swift vtables, i.e. entries in the form of:
+      //
+      //   i32 trunc (i64 sub (i64 ptrtoint @f, i64 ptrtoint ...)) to i32)
+      //
+      // In this case, replace the whole "sub" expression with constant 0 to
+      // avoid leaving a weird sub(0, symbol) expression behind.
+      replaceRelativePointerUsersWithZero(F);
+
       F->replaceNonMetadataUsesWith(ConstantPointerNull::get(F->getType()));
     }
     EraseUnusedGlobalValue(F);
   }
 
   NumVariables += DeadGlobalVars.size();
   for (GlobalVariable *GV : DeadGlobalVars)
     EraseUnusedGlobalValue(GV);
 
   NumAliases += DeadAliases.size();

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

 ; RUN: opt < %s -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)
 
 @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),
 
   ; 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)
 ]}, 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] } { [3 x i32] [
-; CHECK-SAME:   i32 trunc (i64 sub (i64 0, i64 ptrtoint ({ [3 x i32] }* @vtable to i64)) to i32),
-; CHECK-SAME:   i32 trunc (i64 sub (i64 0, i64 ptrtoint ({ [3 x i32] }* @vtable to i64)) to i32),
-; CHECK-SAME:   i32 trunc (i64 sub (i64 0, i64 ptrtoint (void ()* @weird_ref_2 to i64)) to i32)
-; CHECK-SAME: ] }, align 8, !type !0, !type !1, !vcall_visibility !2
+; CHECK:      @vtable = internal unnamed_addr constant { [3 x i32] } zeroinitializer, align 8, !type !0, !type !1, !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 }
 
 define void @main() {
   %1 = ptrtoint { [3 x i32] }* @vtable to i64 ; to keep @vtable alive
   call void @weird_ref_2()
   ret void
 }
 
 !999 = !{i32 1, !"Virtual Function Elim", i32 1}
 !llvm.module.flags = !{!999}

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

@vtable = internal unnamed_addr constant { [4 x i32] } { [4 x i32] [
   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)
 ]}, 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 0,                                                    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 0
 ; CHECK-SAME: ] }, align 8, !type !0, !type !1, !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
 }
 

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

 ; RUN: opt < %s -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)
 
 ; 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)
 ]}, 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 0,                                                    i64 ptrtoint ({ [2 x i32] }* @vtable to i64)) to i32)
+; CHECK-SAME:   i32 0
 ; CHECK-SAME: ] }, align 8, !type !0, !type !1, !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
 }