WholeProgramDevirt: Implement export/import support for unique ret val opt.

[pcc]

Summary

Depends on D29854

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

437

Document new functions

824

There are now a bunch of places where this array is being cleared. Suggest putting this in a helper method called something like CSInfo.markDevirtualized() - it will make it more explicit as to what is going on.

853

I was trying to prove to myself that Res != nullptr when isExported(), but I am having trouble doing so. isExported() will be true when the CSInfo has SummaryTypeCheckedLoadUsers or SummaryHasTypeTestAssumeUsers - these are set up when (Action == PassSummaryAction::Export). But Res will only be non-null when (Action == PassSummaryAction::Export && isa<MDString>(S.first.TypeID)).

Is there a case where we could reach here when Action == PassSummaryAction::Export but !isa<MDString>(S.first.TypeID)?

llvm/test/Transforms/WholeProgramDevirt/export-unique-ret-val.ll

34

Why check these - is there a chance they could be modified if the optimization goes wrong?

llvm/test/Transforms/WholeProgramDevirt/import.ll

46

Add comment on why the optimization can't/shouldn't be applied here.

[pcc]

• Address review comments

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

853

I think isExported() can only possibly be true for type IDs of type MDString because we only add MDStrings to MetadataByGUID (see http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/WholeProgramDevirt.cpp#1204) and we only ever set SummaryTypeCheckedLoadUsers or SummaryHasTypeTestAssumeUsers on members of MetadataByGUID.

llvm/test/Transforms/WholeProgramDevirt/export-unique-ret-val.ll

34

Yes, as with D29846 I want to make sure we aren't taking the general VCP code path.

llvm/test/Transforms/WholeProgramDevirt/import.ll

46

I refreshed this change past r296948 which added a comment at the top of this function.

[tejohnson]

LGTM

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

853

Ok thanks, missed that.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

struct CallSiteInfo {
   /// Whether any function summary contains an llvm.assume(llvm.type.test) for
   /// this slot.
   bool SummaryHasTypeTestAssumeUsers;
 
   /// CFI-specific: a vector containing the list of function summaries that use
   /// the llvm.type.checked.load intrinsic and therefore will require
   /// resolutions for llvm.type.test in order to implement CFI checks if
   /// devirtualization was unsuccessful. If devirtualization was successful, the
-  /// pass will clear this vector. If at the end of the pass the vector is
-  /// non-empty, we will need to add a use of llvm.type.test to each of the
-  /// function summaries in the vector.
+  /// pass will clear this vector by calling markDevirt(). If at the end of the
+  /// pass the vector is non-empty, we will need to add a use of llvm.type.test
+  /// to each of the function summaries in the vector.
   std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
 
   bool isExported() const {
     return SummaryHasTypeTestAssumeUsers ||
            !SummaryTypeCheckedLoadUsers.empty();
   }
+
+  /// As explained in the comment for SummaryTypeCheckedLoadUsers.
+  void markDevirt() { SummaryTypeCheckedLoadUsers.clear(); }
 };
 
 // Call site information collected for a specific VTableSlot.
 struct VTableSlotInfo {
   // The set of call sites which do not have all constant integer arguments
   // (excluding "this").
   CallSiteInfo CSInfo;
 
bool tryEvaluateFunctionsWithArgs(
       ArrayRef<uint64_t> Args);
 
   void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
                              uint64_t TheRetVal);
   bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                            CallSiteInfo &CSInfo,
                            WholeProgramDevirtResolution::ByArg *Res);
 
+  // Returns the global symbol name that is used to export information about the
+  // given vtable slot and list of arguments.
+  std::string getGlobalName(VTableSlot Slot, ArrayRef<uint64_t> Args,
+                            StringRef Name);
+
+  // This function is called during the export phase to create a symbol
+  // definition containing information about the given vtable slot and list of
+  // arguments.
+  void exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args, StringRef Name,
+                    Constant *C);
+
+  // This function is called during the import phase to create a reference to
+  // the symbol definition created during the export phase.
+  Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
+                         StringRef Name);
+
   void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
                             Constant *UniqueMemberAddr);
   bool tryUniqueRetValOpt(unsigned BitWidth,
                           MutableArrayRef<VirtualCallTarget> TargetsForSlot,
-                          CallSiteInfo &CSInfo);
+                          CallSiteInfo &CSInfo,
+                          WholeProgramDevirtResolution::ByArg *Res,
+                          VTableSlot Slot, ArrayRef<uint64_t> Args);
 
   void applyVirtualConstProp(CallSiteInfo &CSInfo, StringRef FnName,
                              Constant *Byte, Constant *Bit);
   bool tryVirtualConstProp(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                            VTableSlotInfo &SlotInfo,
-                           WholeProgramDevirtResolution *Res);
+                           WholeProgramDevirtResolution *Res, VTableSlot Slot);
 
   void rebuildGlobal(VTableBits &B);
 
   // Apply the summary resolution for Slot to all virtual calls in SlotInfo.
   void importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo);
 
   // If we were able to eliminate all unsafe uses for a type checked load,
   // eliminate the associated type tests by replacing them with true.
for (auto &&VCallSite : CSInfo.CallSites) {
       VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
           TheFn, VCallSite.CS.getCalledValue()->getType()));
       // This use is no longer unsafe.
       if (VCallSite.NumUnsafeUses)
         --*VCallSite.NumUnsafeUses;
     }
     if (CSInfo.isExported()) {
       IsExported = true;
-      CSInfo.SummaryTypeCheckedLoadUsers.clear();
+      CSInfo.markDevirt();
     }
   };
   Apply(SlotInfo.CSInfo);
   for (auto &P : SlotInfo.ConstCSInfo)
     Apply(P.second);
 }
 
 bool DevirtModule::trySingleImplDevirt(

 }
 
 void DevirtModule::applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
                                          uint64_t TheRetVal) {
   for (auto Call : CSInfo.CallSites)
     Call.replaceAndErase(
         "uniform-ret-val", FnName, RemarksEnabled,
         ConstantInt::get(cast<IntegerType>(Call.CS.getType()), TheRetVal));
-  CSInfo.SummaryTypeCheckedLoadUsers.clear();
+  CSInfo.markDevirt();
 }
 
 bool DevirtModule::tryUniformRetValOpt(
     MutableArrayRef<VirtualCallTarget> TargetsForSlot, CallSiteInfo &CSInfo,
     WholeProgramDevirtResolution::ByArg *Res) {
   // Uniform return value optimization. If all functions return the same
   // constant, replace all calls with that constant.
   uint64_t TheRetVal = TargetsForSlot[0].RetVal;
   for (const VirtualCallTarget &Target : TargetsForSlot)
     if (Target.RetVal != TheRetVal)
       return false;
 
   if (CSInfo.isExported()) {
     Res->TheKind = WholeProgramDevirtResolution::ByArg::UniformRetVal;
     Res->Info = TheRetVal;
   }
 
   applyUniformRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), TheRetVal);
   if (RemarksEnabled)
     for (auto &&Target : TargetsForSlot)
       Target.WasDevirt = true;
   return true;
 }
 
+std::string DevirtModule::getGlobalName(VTableSlot Slot,
+                                        ArrayRef<uint64_t> Args,
+                                        StringRef Name) {
+  std::string FullName = "__typeid_";
+  raw_string_ostream OS(FullName);
+  OS << cast<MDString>(Slot.TypeID)->getString() << '_' << Slot.ByteOffset;
+  for (uint64_t Arg : Args)
+    OS << '_' << Arg;
+  OS << '_' << Name;
+  return OS.str();
+}
+
+void DevirtModule::exportGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
+                                StringRef Name, Constant *C) {
+  GlobalAlias *GA = GlobalAlias::create(Int8Ty, 0, GlobalValue::ExternalLinkage,
+                                        getGlobalName(Slot, Args, Name), C, &M);
+  GA->setVisibility(GlobalValue::HiddenVisibility);
+}
+
+Constant *DevirtModule::importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
+                                     StringRef Name) {
+  Constant *C = M.getOrInsertGlobal(getGlobalName(Slot, Args, Name), Int8Ty);
+  auto *GV = dyn_cast<GlobalVariable>(C);
+  if (!GV)
+    return C;
+  GV->setVisibility(GlobalValue::HiddenVisibility);
+  return GV;
+}
+
 void DevirtModule::applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
                                         bool IsOne,
                                         Constant *UniqueMemberAddr) {
   for (auto &&Call : CSInfo.CallSites) {
     IRBuilder<> B(Call.CS.getInstruction());
     Value *Cmp = B.CreateICmp(IsOne ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE,
                               Call.VTable, UniqueMemberAddr);
     Cmp = B.CreateZExt(Cmp, Call.CS->getType());
     Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, Cmp);
   }
+  CSInfo.markDevirt();
 }
 
 bool DevirtModule::tryUniqueRetValOpt(
     unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
-    CallSiteInfo &CSInfo) {
+    CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
+    VTableSlot Slot, ArrayRef<uint64_t> Args) {
   // IsOne controls whether we look for a 0 or a 1.
   auto tryUniqueRetValOptFor = [&](bool IsOne) {
     const TypeMemberInfo *UniqueMember = nullptr;
     for (const VirtualCallTarget &Target : TargetsForSlot) {
       if (Target.RetVal == (IsOne ? 1 : 0)) {
         if (UniqueMember)
           return false;
         UniqueMember = Target.TM;
       }
     }
 
     // We should have found a unique member or bailed out by now. We already
     // checked for a uniform return value in tryUniformRetValOpt.
     assert(UniqueMember);
 
-    // Replace each call with the comparison.
     Constant *UniqueMemberAddr =
         ConstantExpr::getBitCast(UniqueMember->Bits->GV, Int8PtrTy);
     UniqueMemberAddr = ConstantExpr::getGetElementPtr(
         Int8Ty, UniqueMemberAddr,
         ConstantInt::get(Int64Ty, UniqueMember->Offset));
 
+    if (CSInfo.isExported()) {
+      Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal;
+      Res->Info = IsOne;
+
+      exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
+    }
+
+    // Replace each call with the comparison.
     applyUniqueRetValOpt(CSInfo, TargetsForSlot[0].Fn->getName(), IsOne,
                          UniqueMemberAddr);
 
     // Update devirtualization statistics for targets.
     if (RemarksEnabled)
       for (auto &&Target : TargetsForSlot)
         Target.WasDevirt = true;
 
if (RetType->getBitWidth() == 1) {
       Value *ValAddr = B.CreateBitCast(Addr, RetType->getPointerTo());
       Value *Val = B.CreateLoad(RetType, ValAddr);
       Call.replaceAndErase("virtual-const-prop", FnName, RemarksEnabled, Val);
     }
   }
 }
 
 bool DevirtModule::tryVirtualConstProp(
-    MutableArrayRef<VirtualCallTarget> TargetsForSlot,
-    VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res) {
+    MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
+    WholeProgramDevirtResolution *Res, VTableSlot Slot) {
   // This only works if the function returns an integer.
   auto RetType = dyn_cast<IntegerType>(TargetsForSlot[0].Fn->getReturnType());
   if (!RetType)
     return false;
   unsigned BitWidth = RetType->getBitWidth();
   if (BitWidth > 64)
     return false;
 
for (auto &&CSByConstantArg : SlotInfo.ConstCSInfo) {
 
     WholeProgramDevirtResolution::ByArg *ResByArg = nullptr;
     if (Res)
       ResByArg = &Res->ResByArg[CSByConstantArg.first];
 
     if (tryUniformRetValOpt(TargetsForSlot, CSByConstantArg.second, ResByArg))
       continue;
 
-    if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second))
+    if (tryUniqueRetValOpt(BitWidth, TargetsForSlot, CSByConstantArg.second,
+                           ResByArg, Slot, CSByConstantArg.first))
       continue;
 
     // Find an allocation offset in bits in all vtables associated with the
     // type.
     uint64_t AllocBefore =
         findLowestOffset(TargetsForSlot, /*IsAfter=*/false, BitWidth);
     uint64_t AllocAfter =
         findLowestOffset(TargetsForSlot, /*IsAfter=*/true, BitWidth);
for (auto &CSByConstantArg : SlotInfo.ConstCSInfo) {
     // FIXME: We should figure out what to do about the "function name" argument
     // to the apply* functions, as the function names are unavailable during the
     // importing phase. For now we just pass the empty string. This does not
     // impact correctness because the function names are just used for remarks.
     switch (ResByArg.TheKind) {
     case WholeProgramDevirtResolution::ByArg::UniformRetVal:
       applyUniformRetValOpt(CSByConstantArg.second, "", ResByArg.Info);
       break;
+    case WholeProgramDevirtResolution::ByArg::UniqueRetVal: {
+      Constant *UniqueMemberAddr =
+          importGlobal(Slot, CSByConstantArg.first, "unique_member");
+      applyUniqueRetValOpt(CSByConstantArg.second, "", ResByArg.Info,
+                           UniqueMemberAddr);
+      break;
+    }
     default:
       break;
     }
   }
 }
 
 void DevirtModule::removeRedundantTypeTests() {
   auto True = ConstantInt::getTrue(M.getContext());
if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
       WholeProgramDevirtResolution *Res = nullptr;
       if (Action == PassSummaryAction::Export && isa<MDString>(S.first.TypeID))
         Res =
             &Summary
                  ->getTypeIdSummary(cast<MDString>(S.first.TypeID)->getString())
                  .WPDRes[S.first.ByteOffset];
 
       if (!trySingleImplDevirt(TargetsForSlot, S.second, Res) &&
-          tryVirtualConstProp(TargetsForSlot, S.second, Res))
+          tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first))
         DidVirtualConstProp = true;
 
       // Collect functions devirtualized at least for one call site for stats.
       if (RemarksEnabled)
         for (const auto &T : TargetsForSlot)
           if (T.WasDevirt)
             DevirtTargets[T.Fn->getName()] = T.Fn;
     }

llvm/test/Transforms/WholeProgramDevirt/Inputs/import-unique-ret-val0.yaml

+---
+TypeIdMap:
+  typeid2:
+    WPDRes:
+      8:
+        Kind: Indir
+        ResByArg:
+          3:
+            Kind: UniqueRetVal
+            Info: 0
+...

llvm/test/Transforms/WholeProgramDevirt/Inputs/import-unique-ret-val1.yaml

+---
+TypeIdMap:
+  typeid2:
+    WPDRes:
+      8:
+        Kind: Indir
+        ResByArg:
+          3:
+            Kind: UniqueRetVal
+            Info: 1
+...

llvm/test/Transforms/WholeProgramDevirt/export-unique-ret-val.ll

+; RUN: opt -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck %s
+; RUN: FileCheck --check-prefix=SUMMARY %s < %t
+
+; SUMMARY:     - TypeTests:
+; SUMMARY-NEXT:  TypeTestAssumeVCalls:
+
+; SUMMARY:      TypeIdMap:
+; SUMMARY-NEXT:   typeid3:
+; SUMMARY-NEXT:     TTRes:
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
+; SUMMARY-NEXT:     WPDRes:
+; SUMMARY-NEXT:       0:
+; SUMMARY-NEXT:         Kind:            Indir
+; SUMMARY-NEXT:         SingleImplName:  ''
+; SUMMARY-NEXT:         ResByArg:
+; SUMMARY-NEXT:           12,24:
+; SUMMARY-NEXT:             Kind:            UniqueRetVal
+; SUMMARY-NEXT:             Info:            0
+; SUMMARY-NEXT:   typeid4:
+; SUMMARY-NEXT:     TTRes:
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
+; SUMMARY-NEXT:     WPDRes:
+; SUMMARY-NEXT:       0:
+; SUMMARY-NEXT:         Kind:            Indir
+; SUMMARY-NEXT:         SingleImplName:  ''
+; SUMMARY-NEXT:         ResByArg:
+; SUMMARY-NEXT:           24,12:
+; SUMMARY-NEXT:             Kind:            UniqueRetVal
+; SUMMARY-NEXT:             Info:            1
+
+; CHECK: @vt3a = constant i1 (i8*, i32, i32)* @vf3a
+@vt3a = constant i1 (i8*, i32, i32)* @vf3a, !type !0
+
+; CHECK: @vt3b = constant i1 (i8*, i32, i32)* @vf3b
+@vt3b = constant i1 (i8*, i32, i32)* @vf3b, !type !0
+
+; CHECK: @vt3c = constant i1 (i8*, i32, i32)* @vf3c
+@vt3c = constant i1 (i8*, i32, i32)* @vf3c, !type !0
+
+; CHECK: @vt4a = constant i1 (i8*, i32, i32)* @vf4a
+@vt4a = constant i1 (i8*, i32, i32)* @vf4a, !type !1
+
+; CHECK: @vt4b = constant i1 (i8*, i32, i32)* @vf4b
+@vt4b = constant i1 (i8*, i32, i32)* @vf4b, !type !1
+
+; CHECK: @vt4c = constant i1 (i8*, i32, i32)* @vf4c
+@vt4c = constant i1 (i8*, i32, i32)* @vf4c, !type !1
+
+; CHECK: @__typeid_typeid3_0_12_24_unique_member = hidden alias i8, bitcast (i1 (i8*, i32, i32)** @vt3b to i8*)
+; CHECK: @__typeid_typeid4_0_24_12_unique_member = hidden alias i8, bitcast (i1 (i8*, i32, i32)** @vt4b to i8*)
+
+define i1 @vf3a(i8*, i32, i32) {
+  ret i1 true
+}
+
+define i1 @vf3b(i8*, i32, i32) {
+  ret i1 false
+}
+
+define i1 @vf3c(i8*, i32, i32) {
+  ret i1 true
+}
+
+define i1 @vf4a(i8*, i32, i32) {
+  ret i1 false
+}
+
+define i1 @vf4b(i8*, i32, i32) {
+  ret i1 true
+}
+
+define i1 @vf4c(i8*, i32, i32) {
+  ret i1 false
+}
+
+!0 = !{i32 0, !"typeid3"}
+!1 = !{i32 0, !"typeid4"}

llvm/test/Transforms/WholeProgramDevirt/import.ll

 ; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-single-impl.yaml < %s | FileCheck --check-prefixes=CHECK,SINGLE-IMPL %s
 ; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-uniform-ret-val.yaml < %s | FileCheck --check-prefixes=CHECK,UNIFORM-RET-VAL %s
+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-unique-ret-val0.yaml < %s | FileCheck --check-prefixes=CHECK,UNIQUE-RET-VAL0 %s
+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-unique-ret-val1.yaml < %s | FileCheck --check-prefixes=CHECK,UNIQUE-RET-VAL1 %s
 
 target datalayout = "e-p:64:64"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Test cases where the argument values are known and we can apply virtual
 ; constant propagation.
 
 ; CHECK: define i32 @call1
define i1 @call2(i8* %obj) {
   %p = extractvalue {i8*, i1} %pair, 1
   ; SINGLE-IMPL: br i1 true,
   br i1 %p, label %cont, label %trap
 
 cont:
   %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)*
   ; SINGLE-IMPL: call i1 bitcast (void ()* @singleimpl2 to i1 (i8*, i32)*)
   ; UNIFORM-RET-VAL: call i1 %
+  ; UNIQUE-RET-VAL0: call i1 %
+  ; UNIQUE-RET-VAL1: call i1 %
   %result = call i1 %fptr_casted(i8* %obj, i32 undef)
   ret i1 %result
 
 trap:
   call void @llvm.trap()
   unreachable
 }
 
+; CHECK: define i1 @call3
+define i1 @call3(i8* %obj) {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %pair = call {i8*, i1} @llvm.type.checked.load(i8* %vtablei8, i32 8, metadata !"typeid2")
+  %fptr = extractvalue {i8*, i1} %pair, 0
+  %p = extractvalue {i8*, i1} %pair, 1
+  br i1 %p, label %cont, label %trap
+
+cont:
+  %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)*
+  %result = call i1 %fptr_casted(i8* %obj, i32 3)
+  ; UNIQUE-RET-VAL0: icmp ne i8* %vtablei8, @__typeid_typeid2_8_3_unique_member
+  ; UNIQUE-RET-VAL1: icmp eq i8* %vtablei8, @__typeid_typeid2_8_3_unique_member
+  ret i1 %result
+
+trap:
+  call void @llvm.trap()
+  unreachable
+}
+
 ; SINGLE-IMPL-DAG: declare void @singleimpl1()
 ; SINGLE-IMPL-DAG: declare void @singleimpl2()
 
 declare void @llvm.assume(i1)
 declare void @llvm.trap()
 declare {i8*, i1} @llvm.type.checked.load(i8*, i32, metadata)
 declare i1 @llvm.type.test(i8*, metadata)