WholeProgramDevirt: Add any unsuccessful llvm.type.checked.load devirtualizations to the list of llvm.type.test users.

[pcc]

Summary

Any unsuccessful llvm.type.checked.load devirtualizations will be translated
into uses of llvm.type.test, so we need to add the resulting llvm.type.test
intrinsics to the function summaries so that the LowerTypeTests pass will
export them.

Depends on D29782

[pcc]

• Rename the yaml input file to export.yaml so that I can use it in an upcoming change

[Prazek]

Why llvm.type.checked.load is not documented in LangRef?

[pcc]

@Prazek http://llvm.org/docs/LangRef.html#llvm-type-checked-load-intrinsic

[mehdi_amini]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1045

Might be worth adding a one line comment to describe this block

1095

I'm still not sure what/why this is done. What happens in which phase?
What is the LowerTypeTests pass exporting exactly, and for which consumer?

[Prazek]

In D29808#674669, @pcc wrote:

@Prazek http://llvm.org/docs/LangRef.html#llvm-type-checked-load-intrinsic

Thanks, weird that my search couldn't find it

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1095

Essentially this is applying the same transformation to the summary as we would make to the function itself with regular LTO.

In the exporting phase we need to figure out how each llvm.type.checked.load intrinsic will be lowered. There are two cases:

1. (not devirtualized) emit a regular virtual call and an llvm.type.test
2. (devirtualized) emit a devirtualized call without an llvm.type.test

This change is necessary to correctly handle case 1. By adding the type ID to the list of type tests, we cause the exporting LowerTypeTests pass to export the summary information for that type ID (i.e. it will fill in the TypeTestResolution field in TypeIdSummary). That information will be consumed by the importing LowerTypeTests pass in the thin backend, after the importing WholeProgramDevirt pass has transformed the llvm.type.checked.load into an llvm.type.test (based on the WholeProgramDevirtResolution's Indir resolution for the type ID).

In case 2 the TypeCheckedLoadUsers vector will be cleared (see D29811) so this code will end up not adding the type test to the summary.

[mehdi_amini]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1095

I think I may just get it now, but still not totally sure: the llvm.type.test in case 1 is useful for CFI only right?

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1095

Correct.

[mehdi_amini]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1095

OK, so I'd really like that anything that is done for CFI is clearly identified/documented as such (when in a context that deals with devirt), otherwise it makes it hard to understand what's going on without having both in mind.
It is absolutely non-intuitive to me when reviewing (or for a reader of) WholeProgramDevirt.cpp that these specific actions are performed only for CFI purpose (technically we should be able to *not* do these when CFI isn't enabled by the way).

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1095

I would have thought that the references to "llvm.type.checked.load" would have made this clear enough (per the langref link mentioned earlier, the intrinsic is specific to CFI). But okay, I'll try to put something here with a summary of how llvm.type.checked.load intrinsics are handled by this pass.

[mehdi_amini]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1095

You don't need to put a lot of description, I was imagining just having "CFI-only" appearing somewhere, like:

// If we are exporting and any (CFI-specific) llvm.type.checked.load intrinsics
//...

Or

// For CFI purpose, if we are exporting and any llvm.type.checked.load intrinsics
//...

It seems obvious to me *now* that the "checked" in the name of the intrinsic refers to CFI, but at first glance I was trying to related this to devirtualization, and especially to some kind of guarded speculative devirtualization (which didn't make sense here, but was enough to get me confused).

[pcc]

Depends on D29744

• Refresh, address review comments

[pcc]

Ping.

[tejohnson]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1026–1027

I guess the early return here was for the case when there could not be any devirtualization - suggest adding a comment that in the Export case we still need to go through and handle the non-devirtualized llvm.type.checked.load intrinsics.

1080–1083

Is it worth skipping this check in the case where we previously had an early return above, but now will come through here in the Export case?

1094

How do we know which were not devirtualized? We fall through to here even after the above code which does devirtualizaton.

[pcc]

• Address review comments

[pcc]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1080–1083

If we would have early returned before, we will need to run this check in order to try to export any type IDs. There is no code to handle exporting right now, but it will be added separately later (see D29811).

1094

The idea is that if devirtualization was successful we will clear the TypeCheckedLoadUsers vector. I have added a comment explaining this.

[tejohnson]

LGTM
Thanks for adding all the comments, that is helpful!

[grimar]

llvm/trunk/lib/Transforms/IPO/WholeProgramDevirt.cpp

1114 ↗

(On Diff #90556)

Had to add brackets to compile this under MSVS2015, please see r297451.
I am not sure I did correct thing commiting the change though, http://llvm.org/docs/GettingStartedVS.html says:
"You will need Visual Studio 2015 or higher, with the latest Update installed.", and I don't thing I have any updates installed.
That is the only place in whole LLVM which does not compile for me now though.

[pcc]

llvm/trunk/lib/Transforms/IPO/WholeProgramDevirt.cpp

1114 ↗

(On Diff #90556)

Looks good, thanks for the fix.

llvm/include/llvm/IR/ModuleSummaryIndex.h

ArrayRef<ConstVCall> type_test_assume_const_vcalls() const {
     return TypeTestAssumeConstVCalls;
   }
 
   /// Returns the list of virtual calls made by this function using
   /// llvm.type.checked.load intrinsics with constant integer arguments.
   ArrayRef<ConstVCall> type_checked_load_const_vcalls() const {
     return TypeCheckedLoadConstVCalls;
   }
+
+  /// Add a type test to the summary. This is used by WholeProgramDevirt if we
+  /// were unable to devirtualize a checked call.
+  void addTypeTest(GlobalValue::GUID Guid) { TypeTests.push_back(Guid); }
 };
 
 template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
   static inline FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
   static inline FunctionSummary::VFuncId getTombstoneKey() { return {0, uint64_t(-2)}; }
   static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R) {
     return L.GUID == R.GUID && L.Offset == R.Offset;
   }

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;
+  std::vector<FunctionSummary *> TypeCheckedLoadUsers;
 };
 
 struct VTableSlotInfo {
   CallSiteInfo CSInfo;
   std::map<std::vector<uint64_t>, CallSiteInfo> ConstCSInfo;
 
   void addCallSite(Value *VTable, CallSite CS, unsigned *NumUnsafeUses);
 

 
 bool DevirtModule::run() {
   Function *TypeTestFunc =
       M.getFunction(Intrinsic::getName(Intrinsic::type_test));
   Function *TypeCheckedLoadFunc =
       M.getFunction(Intrinsic::getName(Intrinsic::type_checked_load));
   Function *AssumeFunc = M.getFunction(Intrinsic::getName(Intrinsic::assume));
 
-  if ((!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
+  if (Action != PassSummaryAction::Export &&
+      (!TypeTestFunc || TypeTestFunc->use_empty() || !AssumeFunc ||
        AssumeFunc->use_empty()) &&
       (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()))
     return false;
 
   if (TypeTestFunc && AssumeFunc)
     scanTypeTestUsers(TypeTestFunc, AssumeFunc);
 
   if (TypeCheckedLoadFunc)
     scanTypeCheckedLoadUsers(TypeCheckedLoadFunc);
 
   // Rebuild type metadata into a map for easy lookup.
   std::vector<VTableBits> Bits;
   DenseMap<Metadata *, std::set<TypeMemberInfo>> TypeIdMap;
   buildTypeIdentifierMap(Bits, TypeIdMap);
   if (TypeIdMap.empty())
     return true;
 
+  if (Action == PassSummaryAction::Export) {
+    DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
+    for (auto &P : TypeIdMap) {
+      if (auto *TypeId = dyn_cast<MDString>(P.first))
+        MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
+            TypeId);
+    }
+
+    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_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_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))
-      continue;
-
+    if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
+                                  S.first.ByteOffset)) {
       if (!trySingleImplDevirt(TargetsForSlot, S.second) &&
           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;
     }
 
+    // If we are exporting and any llvm.type.checked.load intrinsics were *not*
+    // devirtualized, we need to add the resulting llvm.type.test intrinsics to
+    // the function summaries so that the LowerTypeTests pass will export them.
+    if (Action == PassSummaryAction::Export && isa<MDString>(S.first.TypeID)) {
+      auto GUID =
+          GlobalValue::getGUID(cast<MDString>(S.first.TypeID)->getString());
+      for (auto FS : S.second.CSInfo.TypeCheckedLoadUsers)
+        FS->addTypeTest(GUID);
+      for (auto &CCS : S.second.ConstCSInfo)
+        for (auto FS : CCS.second.TypeCheckedLoadUsers)
+          FS->addTypeTest(GUID);
+    }
+  }
+
   if (RemarksEnabled) {
     // Generate remarks for each devirtualized function.
     for (const auto &DT : DevirtTargets) {
       Function *F = DT.second;
       DISubprogram *SP = F->getSubprogram();
       DebugLoc DL = SP ? DebugLoc::get(SP->getScopeLine(), 0, SP) : DebugLoc();
       emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F, DL,
                              Twine("devirtualized ") + F->getName());

llvm/test/Transforms/WholeProgramDevirt/Inputs/export.yaml

+---
+GlobalValueMap:
+  42:
+    - TypeTestAssumeVCalls:
+        - GUID: 14276520915468743435  # typeid1
+          Offset: 0
+      TypeCheckedLoadVCalls:
+        - GUID: 15427464259790519041  # typeid2
+          Offset: 0
+      TypeTestAssumeConstVCalls:
+        - VFunc:
+            GUID: 3515965990081467659  # typeid3
+            Offset: 0
+          Args: [12, 24]
+      TypeCheckedLoadConstVCalls:
+        - VFunc:
+            GUID: 17525413373118030901  # typeid4
+            Offset: 0
+          Args: [24, 12]
+...

llvm/test/Transforms/WholeProgramDevirt/export-unsuccessful-checked.ll

+; RUN: opt -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -o /dev/null %s
+; RUN: FileCheck %s < %t
+
+; CHECK:     - TypeTests:
+; CHECK-NEXT:   - 15427464259790519041
+; CHECK-NEXT:   - 17525413373118030901
+; CHECK-NEXT:  TypeTestAssumeVCalls:
+
+@vt1a = constant void (i8*)* @vf1a, !type !0
+@vt1b = constant void (i8*)* @vf1b, !type !0
+@vt2a = constant void (i8*)* @vf2a, !type !1
+@vt2b = constant void (i8*)* @vf2b, !type !1
+@vt3a = constant void (i8*)* @vf3a, !type !2
+@vt3b = constant void (i8*)* @vf3b, !type !2
+@vt4a = constant void (i8*)* @vf4a, !type !3
+@vt4b = constant void (i8*)* @vf4b, !type !3
+
+declare void @vf1a(i8*)
+declare void @vf1b(i8*)
+declare void @vf2a(i8*)
+declare void @vf2b(i8*)
+declare void @vf3a(i8*)
+declare void @vf3b(i8*)
+declare void @vf4a(i8*)
+declare void @vf4b(i8*)
+
+!0 = !{i32 0, !"typeid1"}
+!1 = !{i32 0, !"typeid2"}
+!2 = !{i32 0, !"typeid3"}
+!3 = !{i32 0, !"typeid4"}