WholeProgramDevirt: Implement exporting for single-impl devirtualization.

[pcc]

Summary

Depends on D29808

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

290

How many of these fields are specific to ThinLTO? I assume at least the isExported method is ThinLTO-specific? It would be good to document that.

Also, as I'm reviewing these patches I'm getting confused as to what aspects of the implementation of the optimization are for ThinLTO, it would be good to include a rough outline of how this works for ThinLTO in this file.

609

Suggest setting IsExported to false if not, so that it will always be set by this routine.

610

Needs comment for this block or at least on why this is being cleared.

637

Do we only ever have IsExported==true and therefore reach here in the ThinLTO case? Please add note to that effect if so.

1118

What does it mean for the TypeID to not be an MDString?

[pcc]

• Address review comments

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

290

Both of the members I'm adding in this patch are ThinLTO-specific. I've added a comment here and an outline to the top of the file in D29808.

609

We need to leave this field as it is if CSInfo.isExported() is false, because a previous call to this lambda may have set it to true and we need to remember that.

610

Added to the definition of CallSiteInfo in D29808

1118

It generally means that the type ID is a distinct MDNode and is therefore local to the module. This can happen if the merged module contains a module compiled with regular LTO or a module for which we could not generate a module ID (so we weren't able to turn it into an MDString by exporting it -- see http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp#114).

Added test coverage for this case.

[tejohnson]

LGTM

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

void replaceAndErase(const Twine &OptName, const Twine &TargetName,
     // This use is no longer unsafe.
     if (NumUnsafeUses)
       --*NumUnsafeUses;
   }
 };
 
 struct CallSiteInfo {
   std::vector<VirtualCallSite> CallSites;
+  bool HasTypeTestAssumeUsers;
   std::vector<FunctionSummary *> TypeCheckedLoadUsers;
+
+  bool isExported() const {
+    return HasTypeTestAssumeUsers || !TypeCheckedLoadUsers.empty();
+  }
 };
 
 struct VTableSlotInfo {
   CallSiteInfo CSInfo;
   std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
 
   void addCallSite(Value *VTable, CallSite CS, unsigned *NumUnsafeUses);
 
void buildTypeIdentifierMap(
       std::vector<VTableBits> &Bits,
       DenseMap<Metadata *, std::set<TypeMemberInfo>> &TypeIdMap);
   Constant *getPointerAtOffset(Constant *I, uint64_t Offset);
   bool
   tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
                             const std::set<TypeMemberInfo> &TypeMemberInfos,
                             uint64_t ByteOffset);
 
-  void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn);
+  void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
+                             bool &IsExported);
   bool trySingleImplDevirt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
-                           VTableSlotInfo &SlotInfo);
+                           VTableSlotInfo &SlotInfo,
+                           WholeProgramDevirtResolution *Res);
 
   bool tryEvaluateFunctionsWithArgs(
       MutableArrayRef<VirtualCallTarget> TargetsForSlot,
       ArrayRef<uint64_t> Args);
 
   void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
                              uint64_t TheRetVal);
   bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
for (const TypeMemberInfo &TM : TypeMemberInfos) {
     TargetsForSlot.push_back({Fn, &TM});
   }
 
   // Give up if we couldn't find any targets.
   return !TargetsForSlot.empty();
 }
 
 void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
-                                         Constant *TheFn) {
+                                         Constant *TheFn, bool &IsExported) {
   auto Apply = [&](CallSiteInfo &CSInfo) {
     for (auto &&VCallSite : CSInfo.CallSites) {
       if (RemarksEnabled)
         VCallSite.emitRemark("single-impl", TheFn->getName());
       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.TypeCheckedLoadUsers.clear();
+    }
   };
   Apply(SlotInfo.CSInfo);
   for (auto &P : SlotInfo.ConstCSInfo)
     Apply(P.second);
 }
 
 bool DevirtModule::trySingleImplDevirt(
     MutableArrayRef<VirtualCallTarget> TargetsForSlot,
-    VTableSlotInfo &SlotInfo) {
+    VTableSlotInfo &SlotInfo, WholeProgramDevirtResolution *Res) {
   // See if the program contains a single implementation of this virtual
   // function.
   Function *TheFn = TargetsForSlot[0].Fn;
   for (auto &&Target : TargetsForSlot)
     if (TheFn != Target.Fn)
       return false;
 
   // If so, update each call site to call that implementation directly.
   if (RemarksEnabled)
     TargetsForSlot[0].WasDevirt = true;
-  applySingleImplDevirt(SlotInfo, TheFn);
+
+  bool IsExported = false;
+  applySingleImplDevirt(SlotInfo, TheFn, IsExported);
+  if (!IsExported)
+    return false;
+
+  // If the only implementation has local linkage, we must promote to external
+  // to make it visible to thin LTO objects.
+  if (TheFn->hasLocalLinkage()) {
+    TheFn->setLinkage(GlobalValue::ExternalLinkage);
+    TheFn->setVisibility(GlobalValue::HiddenVisibility);
+    TheFn->setName(TheFn->getName() + "$merged");
+  }
+
+  Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
+  Res->SingleImplName = TheFn->getName();
+
   return true;
 }
 
 bool DevirtModule::tryEvaluateFunctionsWithArgs(
     MutableArrayRef<VirtualCallTarget> TargetsForSlot,
     ArrayRef<uint64_t> Args) {
   // Evaluate each function and store the result in each target's RetVal
   // field.
if (Action == PassSummaryAction::Export) {
     }
 
     for (auto &P : *Summary) {
       for (auto &S : P.second) {
         auto *FS = dyn_cast<FunctionSummary>(S.get());
         if (!FS)
           continue;
         // FIXME: Only add live functions.
+        for (FunctionSummary::VFuncId VF : FS->type_test_assume_vcalls())
+          for (Metadata *MD : MetadataByGUID[VF.GUID])
+            CallSlots[{MD, VF.Offset}].CSInfo.HasTypeTestAssumeUsers = true;
         for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls())
           for (Metadata *MD : MetadataByGUID[VF.GUID])
             CallSlots[{MD, VF.Offset}].CSInfo.TypeCheckedLoadUsers.push_back(
                 FS);
         for (const FunctionSummary::ConstVCall &VC :
+             FS->type_test_assume_const_vcalls())
+          for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID])
+            CallSlots[{MD, VC.VFunc.Offset}]
+                .ConstCSInfo[VC.Args].HasTypeTestAssumeUsers = true;
+        for (const FunctionSummary::ConstVCall &VC :
              FS->type_checked_load_const_vcalls())
           for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID])
             CallSlots[{MD, VC.VFunc.Offset}]
                 .ConstCSInfo[VC.Args].TypeCheckedLoadUsers.push_back(FS);
       }
     }
   }
 
   // For each (type, offset) pair:
   bool DidVirtualConstProp = false;
   std::map<std::string, Function*> DevirtTargets;
   for (auto &S : CallSlots) {
     // Search each of the members of the type identifier for the virtual
     // function implementation at offset S.first.ByteOffset, and add to
     // TargetsForSlot.
     std::vector<VirtualCallTarget> TargetsForSlot;
     if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
                                   S.first.ByteOffset)) {
-      if (!trySingleImplDevirt(TargetsForSlot, S.second) &&
+      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))
         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/export-single-impl.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:      TypeIdMap:
+; SUMMARY-NEXT:   typeid1:
+; SUMMARY-NEXT:     TTRes:
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
+; SUMMARY-NEXT:     WPDRes:
+; SUMMARY-NEXT:       0:
+; SUMMARY-NEXT:         Kind:            SingleImpl
+; SUMMARY-NEXT:         SingleImplName:  vf1
+; SUMMARY-NEXT:         ResByArg:
+; SUMMARY-NEXT:   typeid2:
+; SUMMARY-NEXT:     TTRes:
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
+; SUMMARY-NEXT:     WPDRes:
+; SUMMARY-NEXT:       0:
+; SUMMARY-NEXT:         Kind:            SingleImpl
+; SUMMARY-NEXT:         SingleImplName:  vf2
+; SUMMARY-NEXT:         ResByArg:
+; SUMMARY-NEXT:   typeid3:
+; SUMMARY-NEXT:     TTRes:
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
+; SUMMARY-NEXT:     WPDRes:
+; SUMMARY-NEXT:       0:
+; SUMMARY-NEXT:         Kind:            SingleImpl
+; SUMMARY-NEXT:         SingleImplName:  vf3
+; SUMMARY-NEXT:         ResByArg:
+; SUMMARY-NEXT:   typeid4:
+; SUMMARY-NEXT:     TTRes:
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
+; SUMMARY-NEXT:     WPDRes:
+; SUMMARY-NEXT:       0:
+; SUMMARY-NEXT:         Kind:            SingleImpl
+; SUMMARY-NEXT:         SingleImplName:  'vf4$merged'
+; SUMMARY-NEXT:         ResByArg:
+; SUMMARY-NEXT: ...
+
+; CHECK: @vt1 = constant void (i8*)* @vf1
+@vt1 = constant void (i8*)* @vf1, !type !0
+
+; CHECK: @vt2 = constant void (i8*)* @vf2
+@vt2 = constant void (i8*)* @vf2, !type !1
+
+@vt3 = constant void (i8*)* @vf3, !type !2
+
+; CHECK: @vt4 = constant void (i8*)* @"vf4$merged"
+@vt4 = constant void (i8*)* @vf4, !type !3
+
+; CHECK: declare void @vf1(i8*)
+declare void @vf1(i8*)
+
+; CHECK: define void @vf2(i8*)
+define void @vf2(i8*) {
+  ret void
+}
+
+declare void @vf3(i8*)
+
+; CHECK: define hidden void @"vf4$merged"
+define internal void @vf4(i8*) {
+  ret void
+}
+
+!0 = !{i32 0, !"typeid1"}
+!1 = !{i32 0, !"typeid2"}
+!2 = !{i32 0, !"typeid3"}
+!3 = !{i32 0, !"typeid4"}