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 ↗

(On Diff #87949)

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

1095 ↗

(On Diff #87949)

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 ↗

(On Diff #87949)

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 ↗

(On Diff #87949)

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 ↗

(On Diff #87949)

Correct.

[mehdi_amini]

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

1095 ↗

(On Diff #87949)

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 ↗

(On Diff #87949)

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 ↗

(On Diff #87949)

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

960 ↗

(On Diff #88279)

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.

1015 ↗

(On Diff #88279)

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?

1029 ↗

(On Diff #88279)

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

1015 ↗

(On Diff #88279)

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).

1029 ↗

(On Diff #88279)

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

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

Looks good, thanks for the fix.

llvm/trunk/include/llvm/IR/ModuleSummaryIndex.h

public:
 
   /// Returns the list of virtual calls made by this function using
   /// llvm.type.checked.load intrinsics with all constant integer arguments.
   ArrayRef<ConstVCall> type_checked_load_const_vcalls() const {
     if (TIdInfo)
       return TIdInfo->TypeCheckedLoadConstVCalls;
     return {};
   }
+
+  /// 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) {
+    if (!TIdInfo)
+      TIdInfo = llvm::make_unique<TypeIdInfo>();
+    TIdInfo->TypeTests.push_back(Guid);
+  }
 };
 
 template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
   static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
   static FunctionSummary::VFuncId getTombstoneKey() {
     return {0, uint64_t(-2)};
   }
   static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R) {

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

 // - Uniform return value optimization: if the conditions for virtual constant
 //   propagation hold and each function returns the same constant value, replace
 //   each virtual call with that constant.
 // - Unique return value optimization for i1 return values: if the conditions
 //   for virtual constant propagation hold and a single vtable's function
 //   returns 0, or a single vtable's function returns 1, replace each virtual
 //   call with a comparison of the vptr against that vtable's address.
 //
+// This pass is intended to be used during the regular and thin LTO pipelines.
+// During regular LTO, the pass determines the best optimization for each
+// virtual call and applies the resolutions directly to virtual calls that are
+// eligible for virtual call optimization (i.e. calls that use either of the
+// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics). During
+// ThinLTO, the pass operates in two phases:
+// - Export phase: this is run during the thin link over a single merged module
+//   that contains all vtables with !type metadata that participate in the link.
+//   The pass computes a resolution for each virtual call and stores it in the
+//   type identifier summary.
+// - Import phase: this is run during the thin backends over the individual
+//   modules. The pass applies the resolutions previously computed during the
+//   import phase to each eligible virtual call.
+//
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/iterator_range.h"
if (NumUnsafeUses)
       --*NumUnsafeUses;
   }
 };
 
 // Call site information collected for a specific VTableSlot and possibly a list
 // of constant integer arguments. The grouping by arguments is handled by the
 // VTableSlotInfo class.
 struct CallSiteInfo {
+  /// The set of call sites for this slot. Used during regular LTO and the
+  /// 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.
+
+  /// 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;
 };
 
 // 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 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 ||
+  // Normally if there are no users of the devirtualization intrinsics in the
+  // module, this pass has nothing to do. But if we are exporting, we also need
+  // to handle any users that appear only in the function summaries.
+  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;
 
+  // Collect information from summary about which calls to try to devirtualize.
+  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.SummaryTypeCheckedLoadUsers.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]
+                .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))
-      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;
     }
 
+    // CFI-specific: 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.SummaryTypeCheckedLoadUsers)
+        FS->addTypeTest(GUID);
+      for (auto &CCS : S.second.ConstCSInfo)
+        for (auto FS : CCS.second.SummaryTypeCheckedLoadUsers)
+          FS->addTypeTest(GUID);
+    }
+  }
+
   if (RemarksEnabled) {
     // Generate remarks for each devirtualized function.
     for (const auto &DT : DevirtTargets) {
       Function *F = DT.second;
       DISubprogram *SP = F->getSubprogram();
       emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F, SP,
                              Twine("devirtualized ") + F->getName());
     }

llvm/trunk/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/trunk/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"}