WholeProgramDevirt: Implement exporting for single-impl devirtualization.

[pcc]

Summary

Depends on D29808

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

290 ↗

(On Diff #87952)

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 ↗

(On Diff #87952)

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

610 ↗

(On Diff #87952)

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

637 ↗

(On Diff #87952)

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

1118 ↗

(On Diff #87952)

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

[pcc]

• Address review comments

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

290 ↗

(On Diff #87952)

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 ↗

(On Diff #87952)

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 ↗

(On Diff #87952)

Added to the definition of CallSiteInfo in D29808

1118 ↗

(On Diff #87952)

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/trunk/lib/Transforms/IPO/WholeProgramDevirt.cpp

struct CallSiteInfo {
   /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
   /// call sites that appear in the merged module itself); in each of these
   /// cases we are directly operating on the call sites at the IR level.
   std::vector<VirtualCallSite> CallSites;
 
   // These fields are used during the export phase of ThinLTO and reflect
   // information collected from function summaries.
 
+  /// 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.
   std::vector<FunctionSummary *> SummaryTypeCheckedLoadUsers;
+
+  bool isExported() const {
+    return SummaryHasTypeTestAssumeUsers ||
+           !SummaryTypeCheckedLoadUsers.empty();
+  }
 };
 
 // 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;
 
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.SummaryTypeCheckedLoadUsers.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. We can only get here during the
+  // ThinLTO export phase.
+  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.SummaryHasTypeTestAssumeUsers =
+                true;
         for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls())
           for (Metadata *MD : MetadataByGUID[VF.GUID])
             CallSlots[{MD, VF.Offset}]
                 .CSInfo.SummaryTypeCheckedLoadUsers.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].SummaryHasTypeTestAssumeUsers = 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]
                 .SummaryTypeCheckedLoadUsers.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/trunk/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
+
+@vt5 = constant void (i8*)* @vf5, !type !4
+
+; 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
+}
+
+declare void @vf5(i8*)
+
+!0 = !{i32 0, !"typeid1"}
+!1 = !{i32 0, !"typeid2"}
+!2 = !{i32 0, !"typeid3"}
+!3 = !{i32 0, !"typeid4"}
+!4 = !{i32 0, !5}
+!5 = distinct !{}