[ThinLTO] Implement index-based WPD

[tejohnson]

Summary

This patch adds support to the WholeProgramDevirt pass to perform
index-based WPD, which is invoked from ThinLTO during the thin link.

The ThinLTO backend (WPD import phase) behaves the same regardless of
whether the WPD decisions were made with the index-based or (the
existing) IR-based analysis.

Depends on D54815.

[pcc]

Does this correctly handle the case where the only implementation is internal? I didn't see any code handling that. In the existing implementation this is done here: http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/WholeProgramDevirt.cpp#814

[tejohnson]

In D55153#1373111, @pcc wrote:

Does this correctly handle the case where the only implementation is internal? I didn't see any code handling that. In the existing implementation this is done here: http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/WholeProgramDevirt.cpp#814

This is a good catch. I suspect I didn't hit it since I am marking all the added call edges as Hot, which means we are highly likely to import them, which will result in them getting promoted. But if we were to ever not import it would cause an issue. Let me see if I can confirm this, and the fix should be straightforward (ensure they are all treated as exported if we have references on type tests in other modules so we mark them as promoted in the index).

[tejohnson]

In D55153#1375693, @tejohnson wrote:

In D55153#1373111, @pcc wrote:

Does this correctly handle the case where the only implementation is internal? I didn't see any code handling that. In the existing implementation this is done here: http://llvm-cs.pcc.me.uk/lib/Transforms/IPO/WholeProgramDevirt.cpp#814

This is a good catch. I suspect I didn't hit it since I am marking all the added call edges as Hot, which means we are highly likely to import them, which will result in them getting promoted. But if we were to ever not import it would cause an issue. Let me see if I can confirm this, and the fix should be straightforward (ensure they are all treated as exported if we have references on type tests in other modules so we mark them as promoted in the index).

There were actually a few different issues I discovered while fixing this and writing an additional test.

First of all, we need to make note of any devirtualized targets that have type test users in a different module so that they are not subsequently internalized (since the designation of being exported is based on the GlobalResolution's Partition info which was set up based on linker resolution info). To do this we simply pass in the ExportedGUIDs set from the client that we accumulate this info into and update it based on WPD results. This also ensures we promote any local devirtualized targets used in another module.

Second of all, when the devirtualized implementation is internal and it is used by devirtualized call in another module it must be promoted (ensured by the above change), and we need to note the promoted name in the WPDRes SingleImplName. We can simply record the global promoted name in the WPDRes when we detect that we are adding a cross-module devirtualiztion.

Third, when the devirtualized implementation is internal, and all devirtualized uses are in the same module, it still might need to be promoted if it is subsequently exported by cross-module importing. The simplest and most efficient way to handle this that I came up with is to simply record the information necessary to quickly locate the corresponding WPDRes structure for each local devirt target's ValueInfo in the case where it is not yet exported by a devirtualization. Then after cross module importing, we simply check if any of these VIs has been exported by importing, and update the recorded SingleImplName.

All of these cases are checked with an additional test (devirt2.ll) that I have added.

Finally, the new devirt2.ll also checks the existing hybrid WPD for completeness. Since in that case the local targets are promoted and renamed during module splitting, and the name is based on a hash, I added some handling to llvm-lto2.cpp to enable matching of the provided resolutions based on the unpromoted name.

[tejohnson]

Handle exported symbols correctly

[tejohnson]

Ping

[pcc]

Could you please revert the changes from D54815 out of this change so that it is easier to read?

[tejohnson]

In D55153#1481171, @pcc wrote:

Could you please revert the changes from D54815 out of this change so that it is easier to read?

Yep, sorry, looks like that got messed up when I merged in some other changes awhile back. I'm working on merging in the changes I made this morning and last week to the underlying index patch, and then will update this to contain only the delta. Hopefully it will get updated later this afternoon.

[tejohnson]

Rebase

[tejohnson]

In D55153#1483153, @tejohnson wrote:

In D55153#1481171, @pcc wrote:

Could you please revert the changes from D54815 out of this change so that it is easier to read?

Yep, sorry, looks like that got messed up when I merged in some other changes awhile back. I'm working on merging in the changes I made this morning and last week to the underlying index patch, and then will update this to contain only the delta. Hopefully it will get updated later this afternoon.

I have rebased on top of the recent changes to D54815, and updated the patch so it reflects the diffs on top of that patch.

[tejohnson]

In D55153#1484537, @tejohnson wrote:

In D55153#1483153, @tejohnson wrote:

In D55153#1481171, @pcc wrote:

Could you please revert the changes from D54815 out of this change so that it is easier to read?

Yep, sorry, looks like that got messed up when I merged in some other changes awhile back. I'm working on merging in the changes I made this morning and last week to the underlying index patch, and then will update this to contain only the delta. Hopefully it will get updated later this afternoon.

I have rebased on top of the recent changes to D54815, and updated the patch so it reflects the diffs on top of that patch.

ping, @pcc can you take a look?

[pcc]

lib/Transforms/IPO/WholeProgramDevirt.cpp

882

Can't the vtable be linkonce_odr if the key function is inline?

[tejohnson]

lib/Transforms/IPO/WholeProgramDevirt.cpp

882

Good point. I have changed this to assert that all copies are ODR linkage if there is more than one. I also added this case to the new test.

[tejohnson]

Address comments.

[tejohnson]

Ping - @pcc any more comments?

[pcc]

LGTM

lib/LTO/LTO.cpp

46

nit: sort

test/ThinLTO/X86/devirt2.ll

201

Is -DAG supported with -COUNT? (Doesn't look like it: http://llvm-cs.pcc.me.uk/lib/Support/FileCheck.cpp#1046 )
I would just write this out twice.

[tejohnson]

Address comments

[foad]

This test is failing for me:

Exit Code: 1

Command Output (stderr):
--
/home/jayfoad2/llvm-debug/bin/opt: /home/jayfoad2/git/llvm-project/llvm/test/ThinLTO/X86/Inputs/devirt3.ll: error: Could not open input file: No such file or directory

--

********************
Testing Time: 2.22s
********************
Failing Tests (1):
    LLVM :: ThinLTO/X86/devirt2.ll

  Expected Passes    : 90
  Unexpected Failures: 1

Did you forget to commit devirt3.ll? Or is it a typo for devirt2.ll?

[tejohnson]

In D55153#1612316, @foad wrote:

This test is failing for me:

Exit Code: 1

Command Output (stderr):
--
/home/jayfoad2/llvm-debug/bin/opt: /home/jayfoad2/git/llvm-project/llvm/test/ThinLTO/X86/Inputs/devirt3.ll: error: Could not open input file: No such file or directory

--

********************
Testing Time: 2.22s
********************
Failing Tests (1):
    LLVM :: ThinLTO/X86/devirt2.ll

  Expected Passes    : 90
  Unexpected Failures: 1

Did you forget to commit devirt3.ll? Or is it a typo for devirt2.ll?

Sorry about that, yes it should have been devirt2.ll. I fixed this in r367680 and r367682 (there were 2 instances and I only caught the first one initially).

[saudi]

When switching from clang 9 to clang 10, we encountered a freeze in one of our games built with thin-LTO.
git bisect pointed to this commit.
Unfortunately, it is a pretty large project, and I couldn't repro that behavior in other -smaller- contexts.

Behavior:
In a call to a virtual function, a direct call is made to an address containing a single instruction : a short jump to that same instruction, causing an infinite loop:

00007FF72C7DA80C 5B                   pop         rbx  
00007FF72C7DA80D 5F                   pop         rdi  
00007FF72C7DA80E 5E                   pop         rsi  
00007FF72C7DA80F C3                   ret  
--- [path_to_file.h]
00007FF72C7DA810 EB FE                jmp         00007FF72C7DA810      # <- Infinite loop here
--- No source file -------------------------------------------------------------
00007FF72C7DA812 CC                   int         3  
00007FF72C7DA813 CC                   int         3  
00007FF72C7DA814 CC                   int         3

I noticed, looking into the output map file, that several other methods of that same class had that same address.

Our project is built clang-cl, with options -flto=thin and -Xclang -fwhole-program-vtables, andl links with pre-compiled libs that are built with MSVC.
Without -fwhole-program-vtables the bug disappears.

Notes:

• We tried applying the patch from D77421, without any luck.
• Our project links with pre-compiled libs (that were built without LTO). Would -fwhole-program-vtables be invalid to use in our case?
• The bug also occurs on the master branch.
• I tried with an assert-enabled build, no asserts were raised
• The class hierarchy has several virtual methods inlined; the others are built without LTO in a separate library.

At this point, I would like to create a simple repro, but I'm running out of ideas, as I'm not very familiar with LTO detail. Our repro involves a pretty big compilation (resulting .exe file is about 100MB, link time ~8 min).

I would be interested in suggestions about how to extract helpful information, for example:

• specific command line arguments to clang-cl.exe or lld-link.exe that would give details about devirtualization;
• a significant place to put a breakpoint in lld's code;
• command lines to run on the thin-lto generated object files;
• ... ?

Thanks!

[tejohnson]

A couple of immediate questions/ideas below:

In D55153#1982013, @saudi wrote:

When switching from clang 9 to clang 10, we encountered a freeze in one of our games built with thin-LTO.
git bisect pointed to this commit.
Unfortunately, it is a pretty large project, and I couldn't repro that behavior in other -smaller- contexts.

Behavior:
In a call to a virtual function, a direct call is made to an address containing a single instruction : a short jump to that same instruction, causing an infinite loop:

00007FF72C7DA80C 5B                   pop         rbx  
00007FF72C7DA80D 5F                   pop         rdi  
00007FF72C7DA80E 5E                   pop         rsi  
00007FF72C7DA80F C3                   ret  
--- [path_to_file.h]
00007FF72C7DA810 EB FE                jmp         00007FF72C7DA810      # <- Infinite loop here
--- No source file -------------------------------------------------------------
00007FF72C7DA812 CC                   int         3  
00007FF72C7DA813 CC                   int         3  
00007FF72C7DA814 CC                   int         3

I noticed, looking into the output map file, that several other methods of that same class had that same address.

Do you know what the original virtual call was, and whether the devirtualization seems legitimate given the class hierarchy?

Our project is built clang-cl, with options -flto=thin and -Xclang -fwhole-program-vtables, andl links with pre-compiled libs that are built with MSVC.
Without -fwhole-program-vtables the bug disappears.

Are you building with -fno-split-lto-unit? If not, you are getting hybrid regular/Thin LTO devirtualization, and this patch doesn't really apply. By default with -fwhole-program-vtables and -flto=thin, the LTO units are split into regular and thin portions, and all vtables are in the regular portion. This patch simply extended WPD to work without splitting, hence ThinLTO "index only" - i.e. no regular LTO and no IR, and only kicks in with -fno-split-lto-unit on top of the other options. The original hybrid ThinLTO WPD was implemented by @pcc, who may have some ideas as well.

Notes:

• We tried applying the patch from D77421, without any luck.
• Our project links with pre-compiled libs (that were built without LTO). Would -fwhole-program-vtables be invalid to use in our case?

It depends. Are you also compiling with -fvisibility=hidden? I believe -fwhole-program-vtables should be safe on its own, but often is combined with -fvisibility=hidden to maximize the devirtualization candidates. Setting the visibility to hidden can be dangerous if you don't have full whole program scope for LTO. I.e. if any of those pre-compiled libs inherits from the classes in the LTO objects.

• The bug also occurs on the master branch.
• I tried with an assert-enabled build, no asserts were raised
• The class hierarchy has several virtual methods inlined; the others are built without LTO in a separate library.

At this point, I would like to create a simple repro, but I'm running out of ideas, as I'm not very familiar with LTO detail. Our repro involves a pretty big compilation (resulting .exe file is about 100MB, link time ~8 min).

I would be interested in suggestions about how to extract helpful information, for example:

• specific command line arguments to clang-cl.exe or lld-link.exe that would give details about devirtualization;

Try enabling pass remarks in the LTO pipeline. For lld this would be -Wl,-mllvm,-pass-remarks=wholeprogramdevirt

• a significant place to put a breakpoint in lld's code;

This sort of depends on what you are looking for. I would start with the pass remarks and figure out what is the bad devirtualization. The WPD code is in llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp.

• command lines to run on the thin-lto generated object files;
• ... ?

Thanks!

[saudi]

Our project is built clang-cl, with options -flto=thin and -Xclang -fwhole-program-vtables, andl links with pre-compiled libs that are built with MSVC.
Without -fwhole-program-vtables the bug disappears.

Are you building with -fno-split-lto-unit? If not, you are getting hybrid regular/Thin LTO devirtualization, and this patch doesn't really apply. By default with -fwhole-program-vtables and -flto=thin, the LTO units are split into regular and thin portions, and all vtables are in the regular portion. This patch simply extended WPD to work without splitting, hence ThinLTO "index only" - i.e. no regular LTO and no IR, and only kicks in with -fno-split-lto-unit on top of the other options. The original hybrid ThinLTO WPD was implemented by @pcc, who may have some ideas as well.

I was not using -fno-split-lto-unit option; however it was unwantedly infered by the use of -Xclang before -fwhole_program_vtables : the driver didn't see the -fwhole_program_vtables and hence didn't activate -fsplit-lto-unit on cc1 argument.
This peculiar setup seems to have been hiding my problem until this patch.
Removing the -Xclang, I could repro the bug on previous commits.
I'm investigating that now.

Thank you for your time!

include/llvm/Bitcode/LLVMBitCodes.h

enum GlobalValueSummarySymtabCodes {
   // Per-module summary that also adds relative block frequency to callee info.
   // PERMODULE_RELBF: [valueid, flags, instcount, numrefs,
   //                   numrefs x valueid,
   //                   n x (valueid, relblockfreq)]
   FS_PERMODULE_RELBF = 19,
   // Index-wide flags
   FS_FLAGS = 20,
   // Maps type identifier to summary information for that type identifier.
+  // Produced by the thin link (only lives in combined index).
   // TYPE_ID: [typeid, kind, bitwidth, align, size, bitmask, inlinebits,
   //           n x (typeid, kind, name, numrba,
   //                numrba x (numarg, numarg x arg, kind, info, byte, bit))]
   FS_TYPE_ID = 21,
+  // Maps type identifier to summary information for that type identifier
+  // computed from type metadata: the valueid of each vtable definition
+  // decorated with a type metadata for that identifier, and the offset from
+  // the corresponding type metadata.
+  // Exists in the per-module summary to provide information to thin link
+  // for index-based whole program devirtualization.
+  // TYPE_ID_METADATA: [typeid, n x (valueid, offset)]
+  FS_TYPE_ID_METADATA = 22,
+  // Summarizes vtable definition for use in index-based whole program
+  // devirtualization during the thin link.
+  // PERMODULE_VTABLE_GLOBALVAR_INIT_REFS: [valueid, flags, varflags,
+  //                                        numrefs, numrefs x valueid,
+  //                                        n x (valueid, offset)]
+  FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS = 23,
 };
 
 enum MetadataCodes {
   METADATA_STRING_OLD = 1,     // MDSTRING:      [values]
   METADATA_VALUE = 2,          // VALUE:         [type num, value num]
   METADATA_NODE = 3,           // NODE:          [n x md num]
   METADATA_NAME = 4,           // STRING:        [values]
   METADATA_DISTINCT_NODE = 5,  // DISTINCT_NODE: [n x md num]

include/llvm/IR/ModuleSummaryIndex.h

public:
   uint64_t entryCount() const { return EntryCount; }
 
   /// Set the synthetic entry count for this function.
   void setEntryCount(uint64_t EC) { EntryCount = EC; }
 
   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
   ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
 
+  void addCall(EdgeTy E) { CallGraphEdgeList.push_back(E); }
+
   /// Returns the list of type identifiers used by this function in
   /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
   /// represented as GUIDs.
   ArrayRef<GlobalValue::GUID> type_tests() const {
     if (TIdInfo)
       return TIdInfo->TypeTests;
     return {};
   }
return DenseMapInfo<FunctionSummary::VFuncId>::isEqual(L.VFunc, R.VFunc) &&
            L.Args == R.Args;
   }
 
   static unsigned getHashValue(FunctionSummary::ConstVCall I) {
     return I.VFunc.GUID;
   }
 };
 
+/// Pair of function ValueInfo and offset within a vtable definition
+/// initializer array.
+using VirtFuncOffsetPair = std::pair<ValueInfo, uint64_t>;
+/// List of functions referenced by a particular vtable definition.
+using VTableFuncList = std::vector<VirtFuncOffsetPair>;
+
 /// Global variable summary information to aid decisions and
 /// implementation of importing.
 ///
 /// Global variable summary has extra flag, telling if it is
 /// modified during the program run or not. This affects ThinLTO
 /// internalization
 class GlobalVarSummary : public GlobalValueSummary {
+private:
+  /// For vtable definitions this holds the list of functions and
+  /// their corresponding offsets within the initializer array.
+  std::unique_ptr<VTableFuncList> VTableFuncs;
+
 public:
   struct GVarFlags {
     GVarFlags(bool ReadOnly = false) : ReadOnly(ReadOnly) {}
 
     unsigned ReadOnly : 1;
   } VarFlags;
 
   GlobalVarSummary(GVFlags Flags, GVarFlags VarFlags,
                    std::vector<ValueInfo> Refs)
       : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)),
         VarFlags(VarFlags) {}
 
   /// Check if this is a global variable summary.
   static bool classof(const GlobalValueSummary *GVS) {
     return GVS->getSummaryKind() == GlobalVarKind;
   }
 
   GVarFlags varflags() const { return VarFlags; }
   void setReadOnly(bool RO) { VarFlags.ReadOnly = RO; }
   bool isReadOnly() const { return VarFlags.ReadOnly; }
+
+  void setVTableFuncs(VTableFuncList Funcs) {
+    assert(!VTableFuncs);
+    VTableFuncs = llvm::make_unique<VTableFuncList>(std::move(Funcs));
+  }
+
+  ArrayRef<VirtFuncOffsetPair> vTableFuncs() const {
+    if (VTableFuncs)
+      return *VTableFuncs;
+    return {};
+  }
 };
 
 struct TypeTestResolution {
   /// Specifies which kind of type check we should emit for this byte array.
   /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
   /// details on each kind of check; the enumerators are described with
   /// reference to that document.
   enum Kind {

 /// a particular module, and provide efficient access to their summary.
 using GVSummaryMapTy = DenseMap<GlobalValue::GUID, GlobalValueSummary *>;
 
 /// Map of a type GUID to type id string and summary (multimap used
 /// in case of GUID conflicts).
 using TypeIdSummaryMapTy =
     std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>;
 
+/// Holds information about vtable definitions decorated with type metadata:
+/// the vtable definition value and its offset in the corresponding type
+/// metadata.
+using TypeIdOffsetGVPair = std::pair<uint64_t, ValueInfo>;
+/// List of vtable definitions decorated by the same type id metadata,
+/// and their corresponding offsets in the type id metadata.
+using TypeIdGVInfo = std::vector<TypeIdOffsetGVPair>;
+
 /// Class to hold module path string table and global value map,
 /// and encapsulate methods for operating on them.
 class ModuleSummaryIndex {
 private:
   /// Map from value name to list of summary instances for values of that
   /// name (may be duplicates in the COMDAT case, e.g.).
   GlobalValueSummaryMapTy GlobalValueMap;
 
   /// Holds strings for combined index, mapping to the corresponding module ID.
   ModulePathStringTableTy ModulePathStringTable;
 
   /// Mapping from type identifier GUIDs to type identifier and its summary
-  /// information.
+  /// information. Produced by thin link.
   TypeIdSummaryMapTy TypeIdMap;
 
+  /// Mapping from type identifier to information about vtables decorated
+  /// with that type identifier's metadata. Produced by per module summary
+  /// analysis and consumed by thin link.
+  std::map<std::string, TypeIdGVInfo> TypeIdMetadataMap;
+
   /// Mapping from original ID to GUID. If original ID can map to multiple
   /// GUIDs, it will be mapped to 0.
   std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
 
   /// Indicates that summary-based GlobalValue GC has run, and values with
   /// GVFlags::Live==false are really dead. Otherwise, all values must be
   /// considered live.
   bool WithGlobalValueDeadStripping = false;
public:
   const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
     auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
     for (auto It = TidIter.first; It != TidIter.second; ++It)
       if (It->second.first == TypeId)
         return &It->second.second;
     return nullptr;
   }
 
+  TypeIdSummary *getTypeIdSummary(StringRef TypeId) {
+    return const_cast<TypeIdSummary *>(
+        static_cast<const ModuleSummaryIndex *>(this)->getTypeIdSummary(
+            TypeId));
+  }
+
+  const std::map<std::string, TypeIdGVInfo> &typeIdMetadataMap() const {
+    return TypeIdMetadataMap;
+  }
+
+  /// Return an existing or new TypeIdMetadataMap entry for \p TypeId.
+  /// This accessor can mutate the map and therefore should not be used in
+  /// the ThinLTO backends.
+  TypeIdGVInfo &getOrInsertTypeIdMetadataSummary(StringRef TypeId) {
+    return TypeIdMetadataMap[TypeId];
+  }
+
+  /// For the given \p TypeId, this returns either a pointer to the
+  /// TypeIdMetadataMap entry (if present in the summary map) or null
+  /// (if not present). This may be used when importing.
+  const TypeIdGVInfo *getTypeIdMetadataSummary(StringRef TypeId) const {
+    auto I = TypeIdMetadataMap.find(TypeId);
+    if (I == TypeIdMetadataMap.end())
+      return nullptr;
+    return &I->second;
+  }
+
   /// Collect for the given module the list of functions it defines
   /// (GUID -> Summary).
   void collectDefinedFunctionsForModule(StringRef ModulePath,
                                         GVSummaryMapTy &GVSummaryMap) const;
 
   /// Collect for each module the list of Summaries it defines (GUID ->
   /// Summary).
   void collectDefinedGVSummariesPerModule(

include/llvm/Transforms/IPO/WholeProgramDevirt.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
 #define LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H
 
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/IPO/FunctionImport.h"
 #include <cassert>
 #include <cstdint>
+#include <set>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
 template <typename T> class ArrayRef;
 template <typename T> class MutableArrayRef;
 class Function;
 class GlobalVariable;
 class ModuleSummaryIndex;
+struct ValueInfo;
 
 namespace wholeprogramdevirt {
 
 // A bit vector that keeps track of which bits are used. We use this to
 // pack constant values compactly before and after each virtual table.
 struct AccumBitVector {
   std::vector<uint8_t> Bytes;
 
struct WholeProgramDevirtPass : public PassInfoMixin<WholeProgramDevirtPass> {
   WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary,
                          const ModuleSummaryIndex *ImportSummary)
       : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
     assert(!(ExportSummary && ImportSummary));
   }
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 };
 
+struct VTableSlotSummary {
+  StringRef TypeID;
+  uint64_t ByteOffset;
+};
+
+/// Perform index-based whole program devirtualization on the \p Summary
+/// index. Any devirtualized targets used by a type test in another module
+/// are added to the \p ExportedGUIDs set. For any local devirtualized targets
+/// only used within the defining module, the information necessary for
+/// locating the corresponding WPD resolution is recorded for the ValueInfo
+/// in case it is exported by cross module importing (in which case the
+/// devirtualized target name will need adjustment).
+void runWholeProgramDevirtOnIndex(
+    ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
+    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
+
+/// Call after cross-module importing to update the recorded single impl
+/// devirt target names for any locals that were exported.
+void updateIndexWPDForExports(
+    ModuleSummaryIndex &Summary,
+    StringMap<FunctionImporter::ExportSetTy> &ExportLists,
+    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H

lib/Analysis/ModuleSummaryAnalysis.cpp

auto FuncSummary = llvm::make_unique<FunctionSummary>(
       TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
       TypeTestAssumeConstVCalls.takeVector(),
       TypeCheckedLoadConstVCalls.takeVector());
   if (NonRenamableLocal)
     CantBePromoted.insert(F.getGUID());
   Index.addGlobalValueSummary(F, std::move(FuncSummary));
 }
 
-static void
-computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
-                       DenseSet<GlobalValue::GUID> &CantBePromoted) {
+/// Find function pointers referenced within the given vtable initializer
+/// (or subset of an initializer) \p I. The starting offset of \p I within
+/// the vtable initializer is \p StartingOffset. Any discovered function
+/// pointers are added to \p VTableFuncs along with their cumulative offset
+/// within the initializer.
+static void findFuncPointers(const Constant *I, uint64_t StartingOffset,
+                             const Module &M, ModuleSummaryIndex &Index,
+                             VTableFuncList &VTableFuncs) {
+  // First check if this is a function pointer.
+  if (I->getType()->isPointerTy()) {
+    auto Fn = dyn_cast<Function>(I->stripPointerCasts());
+    // We can disregard __cxa_pure_virtual as a possible call target, as
+    // calls to pure virtuals are UB.
+    if (Fn && Fn->getName() != "__cxa_pure_virtual")
+      VTableFuncs.push_back(
+          std::make_pair(Index.getOrInsertValueInfo(Fn), StartingOffset));
+    return;
+  }
+
+  // Walk through the elements in the constant struct or array and recursively
+  // look for virtual function pointers.
+  const DataLayout &DL = M.getDataLayout();
+  if (auto *C = dyn_cast<ConstantStruct>(I)) {
+    StructType *STy = dyn_cast<StructType>(C->getType());
+    assert(STy);
+    const StructLayout *SL = DL.getStructLayout(C->getType());
+
+    for (StructType::element_iterator EB = STy->element_begin(), EI = EB,
+                                      EE = STy->element_end();
+         EI != EE; ++EI) {
+      auto Offset = SL->getElementOffset(EI - EB);
+      unsigned Op = SL->getElementContainingOffset(Offset);
+      findFuncPointers(cast<Constant>(I->getOperand(Op)),
+                       StartingOffset + Offset, M, Index, VTableFuncs);
+    }
+  } else if (auto *C = dyn_cast<ConstantArray>(I)) {
+    ArrayType *ATy = C->getType();
+    Type *EltTy = ATy->getElementType();
+    uint64_t EltSize = DL.getTypeAllocSize(EltTy);
+    for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
+      findFuncPointers(cast<Constant>(I->getOperand(i)),
+                       StartingOffset + i * EltSize, M, Index, VTableFuncs);
+    }
+  }
+}
+
+// Identify the function pointers referenced by vtable definition \p V.
+static void computeVTableFuncs(ModuleSummaryIndex &Index,
+                               const GlobalVariable &V, const Module &M,
+                               VTableFuncList &VTableFuncs) {
+  if (!V.isConstant())
+    return;
+
+  findFuncPointers(V.getInitializer(), /*StartingOffset=*/0, M, Index,
+                   VTableFuncs);
+
+#ifndef NDEBUG
+  // Validate that the VTableFuncs list is ordered by offset.
+  uint64_t PrevOffset = 0;
+  for (auto &P : VTableFuncs) {
+    // The findVFuncPointers traversal should have encountered the
+    // functions in offset order. We need to use ">=" since PrevOffset
+    // starts at 0.
+    assert(P.second >= PrevOffset);
+    PrevOffset = P.second;
+  }
+#endif
+}
+
+/// Record vtable definition \p V for each type metadata it references.
+static void recordTypeIdMetadataReferences(ModuleSummaryIndex &Index,
+                                           const GlobalVariable &V,
+                                           SmallVectorImpl<MDNode *> &Types) {
+  for (MDNode *Type : Types) {
+    auto TypeID = Type->getOperand(1).get();
+
+    uint64_t Offset =
+        cast<ConstantInt>(
+            cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
+            ->getZExtValue();
+
+    if (auto *TypeId = dyn_cast<MDString>(TypeID))
+      Index.getOrInsertTypeIdMetadataSummary(TypeId->getString())
+          .push_back({Offset, Index.getOrInsertValueInfo(&V)});
+  }
+}
+
+static void computeVariableSummary(ModuleSummaryIndex &Index,
+                                   const GlobalVariable &V,
+                                   DenseSet<GlobalValue::GUID> &CantBePromoted,
+                                   const Module &M,
+                                   SmallVectorImpl<MDNode *> &Types) {
   SetVector<ValueInfo> RefEdges;
   SmallPtrSet<const User *, 8> Visited;
   bool HasBlockAddress = findRefEdges(Index, &V, RefEdges, Visited);
   bool NonRenamableLocal = isNonRenamableLocal(V);
   GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal,
                                     /* Live = */ false, V.isDSOLocal());
 
+  VTableFuncList VTableFuncs;
+  // If splitting is not enabled, then we compute the summary information
+  // necessary for index-based whole program devirtualization.
+  if (!Index.enableSplitLTOUnit()) {
+    Types.clear();
+    V.getMetadata(LLVMContext::MD_type, Types);
+    if (!Types.empty()) {
+      // Identify the function pointers referenced by this vtable definition.
+      computeVTableFuncs(Index, V, M, VTableFuncs);
+
+      // Record this vtable definition for each type metadata it references.
+      recordTypeIdMetadataReferences(Index, V, Types);
+    }
+  }
+
   // Don't mark variables we won't be able to internalize as read-only.
   GlobalVarSummary::GVarFlags VarFlags(
       !V.hasComdat() && !V.hasAppendingLinkage() && !V.isInterposable() &&
       !V.hasAvailableExternallyLinkage() && !V.hasDLLExportStorageClass());
   auto GVarSummary = llvm::make_unique<GlobalVarSummary>(Flags, VarFlags,
                                                          RefEdges.takeVector());
   if (NonRenamableLocal)
     CantBePromoted.insert(V.getGUID());
   if (HasBlockAddress)
     GVarSummary->setNotEligibleToImport();
+  if (!VTableFuncs.empty())
+    GVarSummary->setVTableFuncs(VTableFuncs);
   Index.addGlobalValueSummary(V, std::move(GVarSummary));
 }
 
 static void
 computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
                     DenseSet<GlobalValue::GUID> &CantBePromoted) {
   bool NonRenamableLocal = isNonRenamableLocal(A);
   GlobalValueSummary::GVFlags Flags(A.getLinkage(), NonRenamableLocal,
for (auto &F : M) {
 
     computeFunctionSummary(Index, M, F, BFI, PSI, DT,
                            !LocalsUsed.empty() || HasLocalInlineAsmSymbol,
                            CantBePromoted, IsThinLTO);
   }
 
   // Compute summaries for all variables defined in module, and save in the
   // index.
+  SmallVector<MDNode *, 2> Types;
   for (const GlobalVariable &G : M.globals()) {
     if (G.isDeclaration())
       continue;
-    computeVariableSummary(Index, G, CantBePromoted);
+    computeVariableSummary(Index, G, CantBePromoted, M, Types);
   }
 
   // Compute summaries for all aliases defined in module, and save in the
   // index.
   for (const GlobalAlias &A : M.aliases())
     computeAliasSummary(Index, A, CantBePromoted);
 
   for (auto *V : LocalsUsed) {

lib/AsmParser/LLLexer.cpp

#define KEYWORD(STR)                                                           \
   KEYWORD(calls);
   KEYWORD(callee);
   KEYWORD(hotness);
   KEYWORD(unknown);
   KEYWORD(hot);
   KEYWORD(critical);
   KEYWORD(relbf);
   KEYWORD(variable);
+  KEYWORD(vTableFuncs);
+  KEYWORD(virtFunc);
   KEYWORD(aliasee);
   KEYWORD(refs);
   KEYWORD(typeIdInfo);
   KEYWORD(typeTests);
   KEYWORD(typeTestAssumeVCalls);
   KEYWORD(typeCheckedLoadVCalls);
   KEYWORD(typeTestAssumeConstVCalls);
   KEYWORD(typeCheckedLoadConstVCalls);
   KEYWORD(vFuncId);
   KEYWORD(offset);
   KEYWORD(args);
   KEYWORD(typeid);
+  KEYWORD(typeidMetadata);
   KEYWORD(summary);
   KEYWORD(typeTestRes);
   KEYWORD(kind);
   KEYWORD(unsat);
   KEYWORD(byteArray);
   KEYWORD(inline);
   KEYWORD(single);
   KEYWORD(allOnes);

lib/AsmParser/LLParser.h

bool ParseConstVCallList(
         lltok::Kind Kind,
         std::vector<FunctionSummary::ConstVCall> &ConstVCallList);
     using IdToIndexMapType =
         std::map<unsigned, std::vector<std::pair<unsigned, LocTy>>>;
     bool ParseConstVCall(FunctionSummary::ConstVCall &ConstVCall,
                          IdToIndexMapType &IdToIndexMap, unsigned Index);
     bool ParseVFuncId(FunctionSummary::VFuncId &VFuncId,
                       IdToIndexMapType &IdToIndexMap, unsigned Index);
+    bool ParseOptionalVTableFuncs(VTableFuncList &VTableFuncs);
     bool ParseOptionalRefs(std::vector<ValueInfo> &Refs);
     bool ParseTypeIdEntry(unsigned ID);
     bool ParseTypeIdSummary(TypeIdSummary &TIS);
+    bool ParseTypeIdMetadataEntry(unsigned ID);
     bool ParseTypeTestResolution(TypeTestResolution &TTRes);
     bool ParseOptionalWpdResolutions(
         std::map<uint64_t, WholeProgramDevirtResolution> &WPDResMap);
     bool ParseWpdRes(WholeProgramDevirtResolution &WPDRes);
     bool ParseOptionalResByArg(
         std::map<std::vector<uint64_t>, WholeProgramDevirtResolution::ByArg>
             &ResByArg);
     bool ParseArgs(std::vector<uint64_t> &Args);

lib/AsmParser/LLParser.cpp

bool LLParser::ParseSummaryEntry() {
   switch (Lex.getKind()) {
   case lltok::kw_gv:
     return ParseGVEntry(SummaryID);
   case lltok::kw_module:
     return ParseModuleEntry(SummaryID);
   case lltok::kw_typeid:
     return ParseTypeIdEntry(SummaryID);
     break;
+  case lltok::kw_typeidMetadata:
+    return ParseTypeIdMetadataEntry(SummaryID);
+    break;
   default:
     return Error(Lex.getLoc(), "unexpected summary kind");
   }
   Lex.setIgnoreColonInIdentifiers(false);
   return false;
 }
 
 static bool isValidVisibilityForLinkage(unsigned V, unsigned L) {
bool LLParser::ParseTypeIdSummary(TypeIdSummary &TIS) {
   }
 
   if (ParseToken(lltok::rparen, "expected ')' here"))
     return true;
 
   return false;
 }
 
+static ValueInfo EmptyVI =
+    ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8);
+
+/// TypeIdMetadataEntry
+///   ::= 'typeidMetadata' ':' '(' 'name' ':' STRINGCONSTANT ',' TypeIdGVInfo
+///   ')'
+bool LLParser::ParseTypeIdMetadataEntry(unsigned ID) {
+  assert(Lex.getKind() == lltok::kw_typeidMetadata);
+  Lex.Lex();
+
+  std::string Name;
+  if (ParseToken(lltok::colon, "expected ':' here") ||
+      ParseToken(lltok::lparen, "expected '(' here") ||
+      ParseToken(lltok::kw_name, "expected 'name' here") ||
+      ParseToken(lltok::colon, "expected ':' here") ||
+      ParseStringConstant(Name))
+    return true;
+
+  TypeIdGVInfo &TI = Index->getOrInsertTypeIdMetadataSummary(Name);
+  if (ParseToken(lltok::comma, "expected ',' here") ||
+      ParseToken(lltok::kw_summary, "expected 'summary' here") ||
+      ParseToken(lltok::colon, "expected ':' here") ||
+      ParseToken(lltok::lparen, "expected '(' here"))
+    return true;
+
+  IdToIndexMapType IdToIndexMap;
+  // Parse each call edge
+  do {
+    uint64_t Offset;
+    if (ParseToken(lltok::lparen, "expected '(' here") ||
+        ParseToken(lltok::kw_offset, "expected 'offset' here") ||
+        ParseToken(lltok::colon, "expected ':' here") || ParseUInt64(Offset) ||
+        ParseToken(lltok::comma, "expected ',' here"))
+      return true;
+
+    LocTy Loc = Lex.getLoc();
+    unsigned GVId;
+    ValueInfo VI;
+    if (ParseGVReference(VI, GVId))
+      return true;
+
+    // Keep track of the TypeIdGVInfo array index needing a forward reference.
+    // We will save the location of the ValueInfo needing an update, but
+    // can only do so once the std::vector is finalized.
+    if (VI == EmptyVI)
+      IdToIndexMap[GVId].push_back(std::make_pair(TI.size(), Loc));
+    TI.push_back({Offset, VI});
+
+    if (ParseToken(lltok::rparen, "expected ')' in call"))
+      return true;
+  } while (EatIfPresent(lltok::comma));
+
+  // Now that the TI vector is finalized, it is safe to save the locations
+  // of any forward GV references that need updating later.
+  for (auto I : IdToIndexMap) {
+    for (auto P : I.second) {
+      assert(TI[P.first].second == EmptyVI &&
+             "Forward referenced ValueInfo expected to be empty");
+      auto FwdRef = ForwardRefValueInfos.insert(std::make_pair(
+          I.first, std::vector<std::pair<ValueInfo *, LocTy>>()));
+      FwdRef.first->second.push_back(
+          std::make_pair(&TI[P.first].second, P.second));
+    }
+  }
+
+  if (ParseToken(lltok::rparen, "expected ')' here") ||
+      ParseToken(lltok::rparen, "expected ')' here"))
+    return true;
+
+  // Check if this ID was forward referenced, and if so, update the
+  // corresponding GUIDs.
+  auto FwdRefTIDs = ForwardRefTypeIds.find(ID);
+  if (FwdRefTIDs != ForwardRefTypeIds.end()) {
+    for (auto TIDRef : FwdRefTIDs->second) {
+      assert(!*TIDRef.first &&
+             "Forward referenced type id GUID expected to be 0");
+      *TIDRef.first = GlobalValue::getGUID(Name);
+    }
+    ForwardRefTypeIds.erase(FwdRefTIDs);
+  }
+
+  return false;
+}
+
 /// TypeTestResolution
 ///   ::= 'typeTestRes' ':' '(' 'kind' ':'
 ///         ( 'unsat' | 'byteArray' | 'inline' | 'single' | 'allOnes' ) ','
 ///         'sizeM1BitWidth' ':' SizeM1BitWidth [',' 'alignLog2' ':' UInt64]?
 ///         [',' 'sizeM1' ':' UInt64]? [',' 'bitMask' ':' UInt8]?
 ///         [',' 'inlinesBits' ':' UInt64]? ')'
 bool LLParser::ParseTypeTestResolution(TypeTestResolution &TTRes) {
   if (ParseToken(lltok::kw_typeTestRes, "expected 'typeTestRes' here") ||
bool LLParser::ParseVariableSummary(std::string Name, GlobalValue::GUID GUID,
   Lex.Lex();
 
   StringRef ModulePath;
   GlobalValueSummary::GVFlags GVFlags = GlobalValueSummary::GVFlags(
       /*Linkage=*/GlobalValue::ExternalLinkage, /*NotEligibleToImport=*/false,
       /*Live=*/false, /*IsLocal=*/false);
   GlobalVarSummary::GVarFlags GVarFlags(/*ReadOnly*/ false);
   std::vector<ValueInfo> Refs;
+  VTableFuncList VTableFuncs;
   if (ParseToken(lltok::colon, "expected ':' here") ||
       ParseToken(lltok::lparen, "expected '(' here") ||
       ParseModuleReference(ModulePath) ||
       ParseToken(lltok::comma, "expected ',' here") || ParseGVFlags(GVFlags) ||
       ParseToken(lltok::comma, "expected ',' here") ||
       ParseGVarFlags(GVarFlags))
     return true;
 
-  // Parse optional refs field
-  if (EatIfPresent(lltok::comma)) {
+  // Parse optional fields
+  while (EatIfPresent(lltok::comma)) {
+    switch (Lex.getKind()) {
+    case lltok::kw_vTableFuncs:
+      if (ParseOptionalVTableFuncs(VTableFuncs))
+        return true;
+      break;
+    case lltok::kw_refs:
       if (ParseOptionalRefs(Refs))
         return true;
+      break;
+    default:
+      return Error(Lex.getLoc(), "expected optional variable summary field");
+    }
   }
 
   if (ParseToken(lltok::rparen, "expected ')' here"))
     return true;
 
   auto GS =
       llvm::make_unique<GlobalVarSummary>(GVFlags, GVarFlags, std::move(Refs));
 
   GS->setModulePath(ModulePath);
+  GS->setVTableFuncs(std::move(VTableFuncs));
 
   AddGlobalValueToIndex(Name, GUID, (GlobalValue::LinkageTypes)GVFlags.Linkage,
                         ID, std::move(GS));
 
   return false;
 }
 
 /// AliasSummary
case lltok::kw_critical:
     break;
   default:
     return Error(Lex.getLoc(), "invalid call edge hotness");
   }
   Lex.Lex();
   return false;
 }
 
+/// OptionalVTableFuncs
+///   := 'vTableFuncs' ':' '(' VTableFunc [',' VTableFunc]* ')'
+/// VTableFunc ::= '(' 'virtFunc' ':' GVReference ',' 'offset' ':' UInt64 ')'
+bool LLParser::ParseOptionalVTableFuncs(VTableFuncList &VTableFuncs) {
+  assert(Lex.getKind() == lltok::kw_vTableFuncs);
+  Lex.Lex();
+
+  if (ParseToken(lltok::colon, "expected ':' in vTableFuncs") |
+      ParseToken(lltok::lparen, "expected '(' in vTableFuncs"))
+    return true;
+
+  IdToIndexMapType IdToIndexMap;
+  // Parse each virtual function pair
+  do {
+    ValueInfo VI;
+    if (ParseToken(lltok::lparen, "expected '(' in vTableFunc") ||
+        ParseToken(lltok::kw_virtFunc, "expected 'callee' in vTableFunc") ||
+        ParseToken(lltok::colon, "expected ':'"))
+      return true;
+
+    LocTy Loc = Lex.getLoc();
+    unsigned GVId;
+    if (ParseGVReference(VI, GVId))
+      return true;
+
+    uint64_t Offset;
+    if (ParseToken(lltok::comma, "expected comma") ||
+        ParseToken(lltok::kw_offset, "expected offset") ||
+        ParseToken(lltok::colon, "expected ':'") || ParseUInt64(Offset))
+      return true;
+
+    // Keep track of the VTableFuncs array index needing a forward reference.
+    // We will save the location of the ValueInfo needing an update, but
+    // can only do so once the std::vector is finalized.
+    if (VI == EmptyVI)
+      IdToIndexMap[GVId].push_back(std::make_pair(VTableFuncs.size(), Loc));
+    VTableFuncs.push_back(std::make_pair(VI, Offset));
+
+    if (ParseToken(lltok::rparen, "expected ')' in vTableFunc"))
+      return true;
+  } while (EatIfPresent(lltok::comma));
+
+  // Now that the VTableFuncs vector is finalized, it is safe to save the
+  // locations of any forward GV references that need updating later.
+  for (auto I : IdToIndexMap) {
+    for (auto P : I.second) {
+      assert(VTableFuncs[P.first].first == EmptyVI &&
+             "Forward referenced ValueInfo expected to be empty");
+      auto FwdRef = ForwardRefValueInfos.insert(std::make_pair(
+          I.first, std::vector<std::pair<ValueInfo *, LocTy>>()));
+      FwdRef.first->second.push_back(
+          std::make_pair(&VTableFuncs[P.first].first, P.second));
+    }
+  }
+
+  if (ParseToken(lltok::rparen, "expected ')' in vTableFuncs"))
+    return true;
+
+  return false;
+}
+
 /// OptionalRefs
 ///   := 'refs' ':' '(' GVReference [',' GVReference]* ')'
 bool LLParser::ParseOptionalRefs(std::vector<ValueInfo> &Refs) {
   assert(Lex.getKind() == lltok::kw_refs);
   Lex.Lex();
 
   if (ParseToken(lltok::colon, "expected ':' in refs") |
       ParseToken(lltok::lparen, "expected '(' in refs"))

lib/AsmParser/LLToken.h

enum Kind {
   kw_calls,
   kw_callee,
   kw_hotness,
   kw_unknown,
   kw_hot,
   kw_critical,
   kw_relbf,
   kw_variable,
+  kw_vTableFuncs,
+  kw_virtFunc,
   kw_aliasee,
   kw_refs,
   kw_typeIdInfo,
   kw_typeTests,
   kw_typeTestAssumeVCalls,
   kw_typeCheckedLoadVCalls,
   kw_typeTestAssumeConstVCalls,
   kw_typeCheckedLoadConstVCalls,
   kw_vFuncId,
   kw_offset,
   kw_args,
   kw_typeid,
+  kw_typeidMetadata,
   kw_summary,
   kw_typeTestRes,
   kw_kind,
   kw_unsat,
   kw_byteArray,
   kw_inline,
   kw_single,
   kw_allOnes,

lib/Bitcode/Reader/BitcodeReader.cpp

Error parseValueSymbolTable(
       DenseMap<unsigned, GlobalValue::LinkageTypes> &ValueIdToLinkageMap);
   std::vector<ValueInfo> makeRefList(ArrayRef<uint64_t> Record);
   std::vector<FunctionSummary::EdgeTy> makeCallList(ArrayRef<uint64_t> Record,
                                                     bool IsOldProfileFormat,
                                                     bool HasProfile,
                                                     bool HasRelBF);
   Error parseEntireSummary(unsigned ID);
   Error parseModuleStringTable();
+  void parseTypeIdMetadataSummaryRecord(ArrayRef<uint64_t> Record);
+  void parseTypeIdGVInfo(ArrayRef<uint64_t> Record, size_t &Slot,
+                         TypeIdGVInfo &TypeId);
 
   std::pair<ValueInfo, GlobalValue::GUID>
   getValueInfoFromValueId(unsigned ValueId);
 
   void addThisModule();
   ModuleSummaryIndex::ModuleInfo *getThisModule();
 };
 
static void parseTypeIdSummaryRecord(ArrayRef<uint64_t> Record,
   TypeId.TTRes.SizeM1 = Record[Slot++];
   TypeId.TTRes.BitMask = Record[Slot++];
   TypeId.TTRes.InlineBits = Record[Slot++];
 
   while (Slot < Record.size())
     parseWholeProgramDevirtResolution(Record, Strtab, Slot, TypeId);
 }
 
+void ModuleSummaryIndexBitcodeReader::parseTypeIdGVInfo(
+    ArrayRef<uint64_t> Record, size_t &Slot, TypeIdGVInfo &TypeId) {
+  uint64_t Offset = Record[Slot++];
+  ValueInfo Callee = getValueInfoFromValueId(Record[Slot++]).first;
+  TypeId.push_back({Offset, Callee});
+}
+
+void ModuleSummaryIndexBitcodeReader::parseTypeIdMetadataSummaryRecord(
+    ArrayRef<uint64_t> Record) {
+  size_t Slot = 0;
+  TypeIdGVInfo &TypeId = TheIndex.getOrInsertTypeIdMetadataSummary(
+      {Strtab.data() + Record[Slot], static_cast<size_t>(Record[Slot + 1])});
+  Slot += 2;
+
+  while (Slot < Record.size())
+    parseTypeIdGVInfo(Record, Slot, TypeId);
+}
+
 static void setImmutableRefs(std::vector<ValueInfo> &Refs, unsigned Count) {
   // Read-only refs are in the end of the refs list.
   for (unsigned RefNo = Refs.size() - Count; RefNo < Refs.size(); ++RefNo)
     Refs[RefNo].setReadOnly();
 }
 
 // Eagerly parse the entire summary block. This populates the GlobalValueSummary
 // objects in the index.
case bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS: {
       auto FS =
           llvm::make_unique<GlobalVarSummary>(Flags, GVF, std::move(Refs));
       FS->setModulePath(getThisModule()->first());
       auto GUID = getValueInfoFromValueId(ValueID);
       FS->setOriginalName(GUID.second);
       TheIndex.addGlobalValueSummary(GUID.first, std::move(FS));
       break;
     }
+    // FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS: [valueid, flags, varflags,
+    //                        numrefs, numrefs x valueid,
+    //                        n x (valueid, offset)]
+    case bitc::FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS: {
+      unsigned ValueID = Record[0];
+      uint64_t RawFlags = Record[1];
+      GlobalVarSummary::GVarFlags GVF = getDecodedGVarFlags(Record[2]);
+      unsigned NumRefs = Record[3];
+      unsigned RefListStartIndex = 4;
+      unsigned VTableListStartIndex = RefListStartIndex + NumRefs;
+      auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
+      std::vector<ValueInfo> Refs = makeRefList(
+          ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
+      VTableFuncList VTableFuncs;
+      for (unsigned I = VTableListStartIndex, E = Record.size(); I != E; ++I) {
+        ValueInfo Callee = getValueInfoFromValueId(Record[I]).first;
+        uint64_t Offset = Record[++I];
+        VTableFuncs.push_back({Callee, Offset});
+      }
+      auto VS =
+          llvm::make_unique<GlobalVarSummary>(Flags, GVF, std::move(Refs));
+      VS->setModulePath(getThisModule()->first());
+      VS->setVTableFuncs(VTableFuncs);
+      auto GUID = getValueInfoFromValueId(ValueID);
+      VS->setOriginalName(GUID.second);
+      TheIndex.addGlobalValueSummary(GUID.first, std::move(VS));
+      break;
+    }
     // FS_COMBINED: [valueid, modid, flags, instcount, fflags, numrefs,
     //               numrefs x valueid, n x (valueid)]
     // FS_COMBINED_PROFILE: [valueid, modid, flags, instcount, fflags, numrefs,
     //                       numrefs x valueid, n x (valueid, hotness)]
     case bitc::FS_COMBINED:
     case bitc::FS_COMBINED_PROFILE: {
       unsigned ValueID = Record[0];
       uint64_t ModuleId = Record[1];
case bitc::FS_CFI_FUNCTION_DECLS: {
         CfiFunctionDecls.insert(
             {Strtab.data() + Record[I], static_cast<size_t>(Record[I + 1])});
       break;
     }
 
     case bitc::FS_TYPE_ID:
       parseTypeIdSummaryRecord(Record, Strtab, TheIndex);
       break;
+
+    case bitc::FS_TYPE_ID_METADATA:
+      parseTypeIdMetadataSummaryRecord(Record);
+      break;
     }
   }
   llvm_unreachable("Exit infinite loop");
 }
 
 // Parse the  module string table block into the Index.
 // This populates the ModulePathStringTable map in the index.
 Error ModuleSummaryIndexBitcodeReader::parseModuleStringTable() {

lib/Bitcode/Writer/BitcodeWriter.cpp

private:
   void writePerModuleFunctionSummaryRecord(SmallVector<uint64_t, 64> &NameVals,
                                            GlobalValueSummary *Summary,
                                            unsigned ValueID,
                                            unsigned FSCallsAbbrev,
                                            unsigned FSCallsProfileAbbrev,
                                            const Function &F);
   void writeModuleLevelReferences(const GlobalVariable &V,
                                   SmallVector<uint64_t, 64> &NameVals,
-                                  unsigned FSModRefsAbbrev);
+                                  unsigned FSModRefsAbbrev,
+                                  unsigned FSModVTableRefsAbbrev);
 
   void assignValueId(GlobalValue::GUID ValGUID) {
     GUIDToValueIdMap[ValGUID] = ++GlobalValueId;
   }
 
   unsigned getValueId(GlobalValue::GUID ValGUID) {
     const auto &VMI = GUIDToValueIdMap.find(ValGUID);
     // Expect that any GUID value had a value Id assigned by an
static void writeTypeIdSummaryRecord(SmallVector<uint64_t, 64> &NameVals,
   NameVals.push_back(Summary.TTRes.BitMask);
   NameVals.push_back(Summary.TTRes.InlineBits);
 
   for (auto &W : Summary.WPDRes)
     writeWholeProgramDevirtResolution(NameVals, StrtabBuilder, W.first,
                                       W.second);
 }
 
+static void writeTypeIdMetadataSummaryRecord(
+    SmallVector<uint64_t, 64> &NameVals, StringTableBuilder &StrtabBuilder,
+    const std::string &Id, const TypeIdGVInfo &Summary, ValueEnumerator &VE) {
+  NameVals.push_back(StrtabBuilder.add(Id));
+  NameVals.push_back(Id.size());
+
+  for (auto &P : Summary) {
+    NameVals.push_back(P.first);
+    NameVals.push_back(VE.getValueID(P.second.getValue()));
+  }
+}
+
 // Helper to emit a single function summary record.
 void ModuleBitcodeWriterBase::writePerModuleFunctionSummaryRecord(
     SmallVector<uint64_t, 64> &NameVals, GlobalValueSummary *Summary,
     unsigned ValueID, unsigned FSCallsAbbrev, unsigned FSCallsProfileAbbrev,
     const Function &F) {
   NameVals.push_back(ValueID);
 
   FunctionSummary *FS = cast<FunctionSummary>(Summary);
void ModuleBitcodeWriterBase::writePerModuleFunctionSummaryRecord(
   Stream.EmitRecord(Code, NameVals, FSAbbrev);
   NameVals.clear();
 }
 
 // Collect the global value references in the given variable's initializer,
 // and emit them in a summary record.
 void ModuleBitcodeWriterBase::writeModuleLevelReferences(
     const GlobalVariable &V, SmallVector<uint64_t, 64> &NameVals,
-    unsigned FSModRefsAbbrev) {
+    unsigned FSModRefsAbbrev, unsigned FSModVTableRefsAbbrev) {
   auto VI = Index->getValueInfo(V.getGUID());
   if (!VI || VI.getSummaryList().empty()) {
     // Only declarations should not have a summary (a declaration might however
     // have a summary if the def was in module level asm).
     assert(V.isDeclaration());
     return;
   }
   auto *Summary = VI.getSummaryList()[0].get();
   NameVals.push_back(VE.getValueID(&V));
   GlobalVarSummary *VS = cast<GlobalVarSummary>(Summary);
   NameVals.push_back(getEncodedGVSummaryFlags(VS->flags()));
   NameVals.push_back(getEncodedGVarFlags(VS->varflags()));
 
+  auto VTableFuncs = VS->vTableFuncs();
+  if (!VTableFuncs.empty())
+    NameVals.push_back(VS->refs().size());
+
   unsigned SizeBeforeRefs = NameVals.size();
   for (auto &RI : VS->refs())
     NameVals.push_back(VE.getValueID(RI.getValue()));
   // Sort the refs for determinism output, the vector returned by FS->refs() has
   // been initialized from a DenseSet.
   llvm::sort(NameVals.begin() + SizeBeforeRefs, NameVals.end());
 
+  if (!VTableFuncs.empty()) {
+    // VTableFuncs pairs should already be sorted by offset.
+    for (auto &P : VTableFuncs) {
+      NameVals.push_back(VE.getValueID(P.first.getValue()));
+      NameVals.push_back(P.second);
+    }
+  }
+
+  if (VTableFuncs.empty())
     Stream.EmitRecord(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS, NameVals,
                       FSModRefsAbbrev);
+  else
+    Stream.EmitRecord(bitc::FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS, NameVals,
+                      FSModVTableRefsAbbrev);
   NameVals.clear();
 }
 
 // Current version for the summary.
 // This is bumped whenever we introduce changes in the way some record are
 // interpreted, like flags for instance.
 static const uint64_t INDEX_VERSION = 6;
 
void ModuleBitcodeWriterBase::writePerModuleGlobalValueSummary() {
   Abbv = std::make_shared<BitCodeAbbrev>();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // flags
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));  // valueids
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
   unsigned FSModRefsAbbrev = Stream.EmitAbbrev(std::move(Abbv));
 
+  // Abbrev for FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS.
+  Abbv = std::make_shared<BitCodeAbbrev>();
+  Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // flags
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // numrefs
+  // numrefs x valueid, n x (valueid , offset)
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
+  unsigned FSModVTableRefsAbbrev = Stream.EmitAbbrev(std::move(Abbv));
+
   // Abbrev for FS_ALIAS.
   Abbv = std::make_shared<BitCodeAbbrev>();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_ALIAS));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));   // flags
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
   unsigned FSAliasAbbrev = Stream.EmitAbbrev(std::move(Abbv));
 
+  // Abbrev for FS_TYPE_ID_METADATA
+  Abbv = std::make_shared<BitCodeAbbrev>();
+  Abbv->Add(BitCodeAbbrevOp(bitc::FS_TYPE_ID_METADATA));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // typeid strtab index
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // typeid length
+  // n x (valueid , offset)
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
+  unsigned TypeIdMetadataAbbrev = Stream.EmitAbbrev(std::move(Abbv));
+
   SmallVector<uint64_t, 64> NameVals;
   // Iterate over the list of functions instead of the Index to
   // ensure the ordering is stable.
   for (const Function &F : M) {
     // Summary emission does not support anonymous functions, they have to
     // renamed using the anonymous function renaming pass.
     if (!F.hasName())
       report_fatal_error("Unexpected anonymous function when writing summary");
 
     ValueInfo VI = Index->getValueInfo(F.getGUID());
     if (!VI || VI.getSummaryList().empty()) {
       // Only declarations should not have a summary (a declaration might
       // however have a summary if the def was in module level asm).
       assert(F.isDeclaration());
       continue;
     }
     auto *Summary = VI.getSummaryList()[0].get();
     writePerModuleFunctionSummaryRecord(NameVals, Summary, VE.getValueID(&F),
                                         FSCallsAbbrev, FSCallsProfileAbbrev, F);
   }
 
   // Capture references from GlobalVariable initializers, which are outside
   // of a function scope.
   for (const GlobalVariable &G : M.globals())
-    writeModuleLevelReferences(G, NameVals, FSModRefsAbbrev);
+    writeModuleLevelReferences(G, NameVals, FSModRefsAbbrev,
+                               FSModVTableRefsAbbrev);
 
   for (const GlobalAlias &A : M.aliases()) {
     auto *Aliasee = A.getBaseObject();
     if (!Aliasee->hasName())
       // Nameless function don't have an entry in the summary, skip it.
       continue;
     auto AliasId = VE.getValueID(&A);
     auto AliaseeId = VE.getValueID(Aliasee);
     NameVals.push_back(AliasId);
     auto *Summary = Index->getGlobalValueSummary(A);
     AliasSummary *AS = cast<AliasSummary>(Summary);
     NameVals.push_back(getEncodedGVSummaryFlags(AS->flags()));
     NameVals.push_back(AliaseeId);
     Stream.EmitRecord(bitc::FS_ALIAS, NameVals, FSAliasAbbrev);
     NameVals.clear();
   }
 
+  if (!Index->typeIdMetadataMap().empty()) {
+    for (auto &S : Index->typeIdMetadataMap()) {
+      writeTypeIdMetadataSummaryRecord(NameVals, StrtabBuilder, S.first,
+                                       S.second, VE);
+      Stream.EmitRecord(bitc::FS_TYPE_ID_METADATA, NameVals,
+                        TypeIdMetadataAbbrev);
+      NameVals.clear();
+    }
+  }
+
   Stream.ExitBlock();
 }
 
 /// Emit the combined summary section into the combined index file.
 void IndexBitcodeWriter::writeCombinedGlobalValueSummary() {
   Stream.EnterSubblock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID, 3);
   Stream.EmitRecord(bitc::FS_VERSION, ArrayRef<uint64_t>{INDEX_VERSION});
 

lib/IR/AsmWriter.cpp

void SlotTracker::processIndex() {
 
   // Start numbering the TypeIds after the GUIDs.
   TypeIdNext = GUIDNext;
 
   for (auto TidIter = TheIndex->typeIds().begin();
        TidIter != TheIndex->typeIds().end(); TidIter++)
     CreateTypeIdSlot(TidIter->second.first);
 
+  for (auto &TId : TheIndex->typeIdMetadataMap())
+    CreateGUIDSlot(GlobalValue::getGUID(TId.first));
+
   ST_DEBUG("end processIndex!\n");
 }
 
 void SlotTracker::processGlobalObjectMetadata(const GlobalObject &GO) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
   GO.getAllMetadata(MDs);
   for (auto &MD : MDs)
     CreateMetadataSlot(MD.second);
public:
 
   void printModuleSummaryIndex();
   void printSummaryInfo(unsigned Slot, const ValueInfo &VI);
   void printSummary(const GlobalValueSummary &Summary);
   void printAliasSummary(const AliasSummary *AS);
   void printGlobalVarSummary(const GlobalVarSummary *GS);
   void printFunctionSummary(const FunctionSummary *FS);
   void printTypeIdSummary(const TypeIdSummary &TIS);
+  void printTypeIdMetadataSummary(const TypeIdGVInfo &TI);
   void printTypeTestResolution(const TypeTestResolution &TTRes);
   void printArgs(const std::vector<uint64_t> &Args);
   void printWPDRes(const WholeProgramDevirtResolution &WPDRes);
   void printTypeIdInfo(const FunctionSummary::TypeIdInfo &TIDInfo);
   void printVFuncId(const FunctionSummary::VFuncId VFId);
   void
   printNonConstVCalls(const std::vector<FunctionSummary::VFuncId> VCallList,
                       const char *Tag);
void AssemblyWriter::printModuleSummaryIndex() {
   // Print the TypeIdMap entries.
   for (auto TidIter = TheIndex->typeIds().begin();
        TidIter != TheIndex->typeIds().end(); TidIter++) {
     Out << "^" << Machine.getTypeIdSlot(TidIter->second.first)
         << " = typeid: (name: \"" << TidIter->second.first << "\"";
     printTypeIdSummary(TidIter->second.second);
     Out << ") ; guid = " << TidIter->first << "\n";
   }
+
+  // Print the TypeIdMetadataMap entries.
+  for (auto &TId : TheIndex->typeIdMetadataMap()) {
+    auto GUID = GlobalValue::getGUID(TId.first);
+    Out << "^" << Machine.getGUIDSlot(GUID) << " = typeidMetadata: (name: \""
+        << TId.first << "\"";
+    printTypeIdMetadataSummary(TId.second);
+    Out << ") ; guid = " << GUID << "\n";
+  }
 }
 
 static const char *
 getWholeProgDevirtResKindName(WholeProgramDevirtResolution::Kind K) {
   switch (K) {
   case WholeProgramDevirtResolution::Indir:
     return "indir";
   case WholeProgramDevirtResolution::SingleImpl:
for (auto &WPDRes : TIS.WPDRes) {
       printWPDRes(WPDRes.second);
       Out << ")";
     }
     Out << ")";
   }
   Out << ")";
 }
 
+void AssemblyWriter::printTypeIdMetadataSummary(const TypeIdGVInfo &TI) {
+  Out << ", summary: (";
+  FieldSeparator FS;
+  for (auto &P : TI) {
+    Out << FS;
+    Out << "(offset: " << P.first << ", ";
+    Out << "^" << Machine.getGUIDSlot(P.second.getGUID());
+    Out << ")";
+  }
+  Out << ")";
+}
+
 void AssemblyWriter::printArgs(const std::vector<uint64_t> &Args) {
   Out << "args: (";
   FieldSeparator FS;
   for (auto arg : Args) {
     Out << FS;
     Out << arg;
   }
   Out << ")";
void AssemblyWriter::printAliasSummary(const AliasSummary *AS) {
   if (AS->hasAliasee())
     Out << "^" << Machine.getGUIDSlot(SummaryToGUIDMap[&AS->getAliasee()]);
   else
     Out << "null";
 }
 
 void AssemblyWriter::printGlobalVarSummary(const GlobalVarSummary *GS) {
   Out << ", varFlags: (readonly: " << GS->VarFlags.ReadOnly << ")";
+
+  auto VTableFuncs = GS->vTableFuncs();
+  if (!VTableFuncs.empty()) {
+    Out << ", vTableFuncs: (";
+    FieldSeparator FS;
+    for (auto &P : VTableFuncs) {
+      Out << FS;
+      Out << "(virtFunc: ^" << Machine.getGUIDSlot(P.first.getGUID())
+          << ", offset: " << P.second;
+      Out << ")";
+    }
+    Out << ")";
+  }
 }
 
 static std::string getLinkageName(GlobalValue::LinkageTypes LT) {
   switch (LT) {
   case GlobalValue::ExternalLinkage:
     return "external";
   case GlobalValue::PrivateLinkage:
     return "private";

lib/LTO/LTO.cpp

 #include "llvm/Support/Threading.h"
 #include "llvm/Support/VCSRevision.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
+#include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/Utils/SplitModule.h"
 
 #include <set>
 
 using namespace llvm;
 using namespace lto;
 using namespace object;
 
StringMap<FunctionImporter::ImportMapTy> ImportLists(
       ThinLTO.ModuleMap.size());
   StringMap<FunctionImporter::ExportSetTy> ExportLists(
       ThinLTO.ModuleMap.size());
   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
 
   if (DumpThinCGSCCs)
     ThinLTO.CombinedIndex.dumpSCCs(outs());
 
+  std::set<GlobalValue::GUID> ExportedGUIDs;
+
+  // Perform index-based WPD. This will return immediately if there are
+  // no index entries in the typeIdMetadata map (e.g. if we are instead
+  // performing IR-based WPD in hybrid regular/thin LTO mode).
+  std::map<ValueInfo, std::vector<VTableSlotSummary>> LocalWPDTargetsMap;
+  runWholeProgramDevirtOnIndex(ThinLTO.CombinedIndex, ExportedGUIDs,
+                               LocalWPDTargetsMap);
+
   if (Conf.OptLevel > 0)
     ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
                              ImportLists, ExportLists);
 
+  // Update local devirtualized targets that were exported by cross-module
+  // importing
+  updateIndexWPDForExports(ThinLTO.CombinedIndex, ExportLists,
+                           LocalWPDTargetsMap);
+
   // Figure out which symbols need to be internalized. This also needs to happen
   // at -O0 because summary-based DCE is implemented using internalization, and
   // we must apply DCE consistently with the full LTO module in order to avoid
   // undefined references during the final link.
-  std::set<GlobalValue::GUID> ExportedGUIDs;
   for (auto &Res : GlobalResolutions) {
     // If the symbol does not have external references or it is not prevailing,
     // then not need to mark it as exported from a ThinLTO partition.
     if (Res.second.Partition != GlobalResolution::External ||
         !Res.second.isPrevailingIRSymbol())
       continue;
     auto GUID = GlobalValue::getGUID(
         GlobalValue::dropLLVMManglingEscape(Res.second.IRName));

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

if (ThinLinkOS) {
     W2.writeModule(*MergedM, /*ShouldPreserveUseListOrder=*/false,
                    &MergedMIndex);
     W2.writeSymtab();
     W2.writeStrtab();
     *ThinLinkOS << Buffer;
   }
 }
 
-// Returns whether this module needs to be split because splitting is
-// enabled and it uses type metadata.
-bool requiresSplit(Module &M) {
-  // First check if the LTO Unit splitting has been enabled.
+// Check if the LTO Unit splitting has been enabled.
+bool enableSplitLTOUnit(Module &M) {
   bool EnableSplitLTOUnit = false;
   if (auto *MD = mdconst::extract_or_null<ConstantInt>(
           M.getModuleFlag("EnableSplitLTOUnit")))
     EnableSplitLTOUnit = MD->getZExtValue();
-  if (!EnableSplitLTOUnit)
-    return false;
+  return EnableSplitLTOUnit;
+}
 
-  // Module only needs to be split if it contains type metadata.
+// Returns whether this module needs to be split because it uses type metadata.
+bool hasTypeMetadata(Module &M) {
   for (auto &GO : M.global_objects()) {
     if (GO.hasMetadata(LLVMContext::MD_type))
       return true;
   }
-
   return false;
 }
 
 void writeThinLTOBitcode(raw_ostream &OS, raw_ostream *ThinLinkOS,
                          function_ref<AAResults &(Function &)> AARGetter,
                          Module &M, const ModuleSummaryIndex *Index) {
-  // Split module if splitting is enabled and it contains any type metadata.
-  if (requiresSplit(M))
+  std::unique_ptr<ModuleSummaryIndex> NewIndex = nullptr;
+  // See if this module has any type metadata. If so, we try to split it
+  // or at least promote type ids to enable WPD.
+  if (hasTypeMetadata(M)) {
+    if (enableSplitLTOUnit(M))
       return splitAndWriteThinLTOBitcode(OS, ThinLinkOS, AARGetter, M);
+    else {
+      // Promote type ids as needed for index-based WPD.
+      std::string ModuleId = getUniqueModuleId(&M);
+      if (!ModuleId.empty()) {
+        promoteTypeIds(M, ModuleId);
+        // Need to rebuild the index so that it contains type metadata
+        // for the newly promoted type ids.
+        // FIXME: Probably should not bother building the index at all
+        // in the caller of writeThinLTOBitcode (which does so via the
+        // ModuleSummaryIndexAnalysis pass), since we have to rebuild it
+        // anyway whenever there is type metadata (here or in
+        // splitAndWriteThinLTOBitcode). Just always build it once via the
+        // buildModuleSummaryIndex when Module(s) are ready.
+        ProfileSummaryInfo PSI(M);
+        NewIndex = llvm::make_unique<ModuleSummaryIndex>(
+            buildModuleSummaryIndex(M, nullptr, &PSI));
+        Index = NewIndex.get();
+      }
+    }
+  }
 
-  // Otherwise we can just write it out as a regular module.
+  // Write it out as an unsplit ThinLTO module.
 
   // Save the module hash produced for the full bitcode, which will
   // be used in the backends, and use that in the minimized bitcode
   // produced for the full link.
   ModuleHash ModHash = {{0}};
   WriteBitcodeToFile(M, OS, /*ShouldPreserveUseListOrder=*/false, Index,
                      /*GenerateHash=*/true, &ModHash);
   // If a minimized bitcode module was requested for the thin link, only

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.
+// 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:
+// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics).
+//
+// During hybrid Regular/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.
 //
+// During ThinLTO, the pass operates in two phases:
+// - Export phase: this is run during the thin link over the index which
+//   contains a summary of all vtables with !type metadata that participate in
+//   the link. It computes a resolution for each virtual call and stores it in
+//   the type identifier summary. Only single implementation devirtualization
+//   is supported.
+// - Import phase: (same as with hybrid case above).
+//
 //===----------------------------------------------------------------------===//
 
 #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/MapVector.h"
static cl::opt<std::string> ClWriteSummary(
     cl::Hidden);
 
 static cl::opt<unsigned>
     ClThreshold("wholeprogramdevirt-branch-funnel-threshold", cl::Hidden,
                 cl::init(10), cl::ZeroOrMore,
                 cl::desc("Maximum number of call targets per "
                          "call site to enable branch funnels"));
 
+static cl::opt<bool>
+    PrintSummaryDevirt("wholeprogramdevirt-print-index-based", cl::Hidden,
+                       cl::init(false), cl::ZeroOrMore,
+                       cl::desc("Print index-based devirtualization messages"));
+
 // Find the minimum offset that we may store a value of size Size bits at. If
 // IsAfter is set, look for an offset before the object, otherwise look for an
 // offset after the object.
 uint64_t
 wholeprogramdevirt::findLowestOffset(ArrayRef<VirtualCallTarget> Targets,
                                      bool IsAfter, uint64_t Size) {
   // Find a minimum offset taking into account only vtable sizes.
   uint64_t MinByte = 0;
return DenseMapInfo<Metadata *>::getHashValue(I.TypeID) ^
            DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);
   }
   static bool isEqual(const VTableSlot &LHS,
                       const VTableSlot &RHS) {
     return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
   }
 };
 
+template <> struct DenseMapInfo<VTableSlotSummary> {
+  static VTableSlotSummary getEmptyKey() {
+    return {DenseMapInfo<StringRef>::getEmptyKey(),
+            DenseMapInfo<uint64_t>::getEmptyKey()};
+  }
+  static VTableSlotSummary getTombstoneKey() {
+    return {DenseMapInfo<StringRef>::getTombstoneKey(),
+            DenseMapInfo<uint64_t>::getTombstoneKey()};
+  }
+  static unsigned getHashValue(const VTableSlotSummary &I) {
+    return DenseMapInfo<StringRef>::getHashValue(I.TypeID) ^
+           DenseMapInfo<uint64_t>::getHashValue(I.ByteOffset);
+  }
+  static bool isEqual(const VTableSlotSummary &LHS,
+                      const VTableSlotSummary &RHS) {
+    return LHS.TypeID == RHS.TypeID && LHS.ByteOffset == RHS.ByteOffset;
+  }
+};
+
 } // end namespace llvm
 
 namespace {
 
 // A virtual call site. VTable is the loaded virtual table pointer, and CS is
 // the indirect virtual call.
 struct VirtualCallSite {
   Value *VTable;
struct CallSiteInfo {
   /// 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 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;
+  std::vector<FunctionSummary *> SummaryTypeTestAssumeUsers;
 
   bool isExported() const {
     return SummaryHasTypeTestAssumeUsers ||
            !SummaryTypeCheckedLoadUsers.empty();
   }
 
   void markSummaryHasTypeTestAssumeUsers() {
     SummaryHasTypeTestAssumeUsers = true;
     AllCallSitesDevirted = false;
   }
 
   void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {
     SummaryTypeCheckedLoadUsers.push_back(FS);
     AllCallSitesDevirted = false;
   }
 
+  void addSummaryTypeTestAssumeUser(FunctionSummary *FS) {
+    SummaryTypeTestAssumeUsers.push_back(FS);
+    markSummaryHasTypeTestAssumeUsers();
+  }
+
   void markDevirt() {
     AllCallSitesDevirted = true;
 
     // As explained in the comment for SummaryTypeCheckedLoadUsers.
     SummaryTypeCheckedLoadUsers.clear();
   }
 };
 
struct DevirtModule {
   // Lower the module using the action and summary passed as command line
   // arguments. For testing purposes only.
   static bool
   runForTesting(Module &M, function_ref<AAResults &(Function &)> AARGetter,
                 function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
                 function_ref<DominatorTree &(Function &)> LookupDomTree);
 };
 
+struct DevirtIndex {
+  ModuleSummaryIndex &ExportSummary;
+  // The set in which to record GUIDs exported from their module by
+  // devirtualization, used by client to ensure they are not internalized.
+  std::set<GlobalValue::GUID> &ExportedGUIDs;
+  // A map in which to record the information necessary to locate the WPD
+  // resolution for local targets in case they are exported by cross module
+  // importing.
+  std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap;
+
+  MapVector<VTableSlotSummary, VTableSlotInfo> CallSlots;
+
+  DevirtIndex(
+      ModuleSummaryIndex &ExportSummary,
+      std::set<GlobalValue::GUID> &ExportedGUIDs,
+      std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap)
+      : ExportSummary(ExportSummary), ExportedGUIDs(ExportedGUIDs),
+        LocalWPDTargetsMap(LocalWPDTargetsMap) {}
+
+  bool tryFindVirtualCallTargets(std::vector<ValueInfo> &TargetsForSlot,
+                                 const TypeIdGVInfo TypeIdGVInfo,
+                                 uint64_t ByteOffset);
+
+  bool trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
+                           VTableSlotSummary &SlotSummary,
+                           VTableSlotInfo &SlotInfo,
+                           WholeProgramDevirtResolution *Res,
+                           std::set<ValueInfo> &DevirtTargets);
+
+  void run();
+};
+
 struct WholeProgramDevirt : public ModulePass {
   static char ID;
 
   bool UseCommandLine = false;
 
   ModuleSummaryIndex *ExportSummary;
   const ModuleSummaryIndex *ImportSummary;
 
PreservedAnalyses WholeProgramDevirtPass::run(Module &M,
   };
   if (!DevirtModule(M, AARGetter, OREGetter, LookupDomTree, ExportSummary,
                     ImportSummary)
            .run())
     return PreservedAnalyses::all();
   return PreservedAnalyses::none();
 }
 
+namespace llvm {
+void runWholeProgramDevirtOnIndex(
+    ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
+    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
+  DevirtIndex(Summary, ExportedGUIDs, LocalWPDTargetsMap).run();
+}
+
+void updateIndexWPDForExports(
+    ModuleSummaryIndex &Summary,
+    StringMap<FunctionImporter::ExportSetTy> &ExportLists,
+    std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap) {
+  for (auto &T : LocalWPDTargetsMap) {
+    auto &VI = T.first;
+    // This was enforced earlier during trySingleImplDevirt.
+    assert(VI.getSummaryList().size() == 1 &&
+           "Devirt of local target has more than one copy");
+    auto &S = VI.getSummaryList()[0];
+    const auto &ExportList = ExportLists.find(S->modulePath());
+    if (ExportList == ExportLists.end() ||
+        !ExportList->second.count(VI.getGUID()))
+      continue;
+
+    // It's been exported by a cross module import.
+    for (auto &SlotSummary : T.second) {
+      auto *TIdSum = Summary.getTypeIdSummary(SlotSummary.TypeID);
+      assert(TIdSum);
+      auto WPDRes = TIdSum->WPDRes.find(SlotSummary.ByteOffset);
+      assert(WPDRes != TIdSum->WPDRes.end());
+      WPDRes->second.SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
+          WPDRes->second.SingleImplName,
+          Summary.getModuleHash(S->modulePath()));
+    }
+  }
+}
+
+} // end namespace llvm
+
 bool DevirtModule::runForTesting(
     Module &M, function_ref<AAResults &(Function &)> AARGetter,
     function_ref<OptimizationRemarkEmitter &(Function *)> OREGetter,
     function_ref<DominatorTree &(Function &)> LookupDomTree) {
   ModuleSummaryIndex Summary(/*HaveGVs=*/false);
 
   // Handle the command-line summary arguments. This code is for testing
   // purposes only, so we handle errors directly.
for (const TypeMemberInfo &TM : TypeMemberInfos) {
 
     TargetsForSlot.push_back({Fn, &TM});
   }
 
   // Give up if we couldn't find any targets.
   return !TargetsForSlot.empty();
 }
 
+bool DevirtIndex::tryFindVirtualCallTargets(
+    std::vector<ValueInfo> &TargetsForSlot, const TypeIdGVInfo TypeIdGVInfo,
+    uint64_t ByteOffset) {
+  for (const TypeIdOffsetGVPair P : TypeIdGVInfo) {
+    // VTable initializer should have only one summary (i.e. not be
+    // linkonce/weak).
+    assert(P.second.getSummaryList().size() == 1);
+    const auto *VS = cast<GlobalVarSummary>(P.second.getSummaryList()[0].get());
+    if (!P.second.getSummaryList()[0]->isLive())
+      continue;
+    for (auto VTP : VS->vTableFuncs()) {
+      if (VTP.second != P.first + ByteOffset)
+        continue;
+
+      TargetsForSlot.push_back(VTP.first);
+    }
+  }
+
+  // Give up if we couldn't find any targets.
+  return !TargetsForSlot.empty();
+}
+
 void DevirtModule::applySingleImplDevirt(VTableSlotInfo &SlotInfo,
                                          Constant *TheFn, bool &IsExported) {
   auto Apply = [&](CallSiteInfo &CSInfo) {
     for (auto &&VCallSite : CSInfo.CallSites) {
       if (RemarksEnabled)
         VCallSite.emitRemark("single-impl",
                              TheFn->stripPointerCasts()->getName(), OREGetter);
       VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
bool DevirtModule::trySingleImplDevirt(
   }
 
   Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
   Res->SingleImplName = TheFn->getName();
 
   return true;
 }
 
+bool DevirtIndex::trySingleImplDevirt(MutableArrayRef<ValueInfo> TargetsForSlot,
+                                      VTableSlotSummary &SlotSummary,
+                                      VTableSlotInfo &SlotInfo,
+                                      WholeProgramDevirtResolution *Res,
+                                      std::set<ValueInfo> &DevirtTargets) {
+  // See if the program contains a single implementation of this virtual
+  // function.
+  auto TheFn = TargetsForSlot[0];
+  for (auto &&Target : TargetsForSlot)
+    if (TheFn != Target)
+      return false;
+
+  // Don't devirtualize if we don't have target definition.
+  auto Size = TheFn.getSummaryList().size();
+  if (!Size)
+    return false;
+
+  // If the summary list contains multiple summaries where at least one is
+  // a local, give up, as we won't know which (possibly promoted) name to use.
+  for (auto &S : TheFn.getSummaryList())
+    if (GlobalValue::isLocalLinkage(S->linkage()) && Size > 1)
+      return false;
+
+  // Collect functions devirtualized at least for one call site for stats.
+  if (PrintSummaryDevirt)
+    DevirtTargets.insert(TheFn);
+
+  auto &S = TheFn.getSummaryList()[0];
+  bool IsExported = false;
+
+  // Insert calls into the summary index so that the devirtualized targets
+  // are eligible for import.
+  // FIXME: Annotate type tests with hotness. For now, mark these as hot
+  // to better ensure we have the opportunity to inline them.
+  CalleeInfo CI(CalleeInfo::HotnessType::Hot, /* RelBF = */ 0);
+  auto AddCalls = [&](CallSiteInfo &CSInfo) {
+    for (auto *FS : CSInfo.SummaryTypeCheckedLoadUsers) {
+      FS->addCall({TheFn, CI});
+      IsExported |= S->modulePath() != FS->modulePath();
+    }
+    for (auto *FS : CSInfo.SummaryTypeTestAssumeUsers) {
+      FS->addCall({TheFn, CI});
+      IsExported |= S->modulePath() != FS->modulePath();
+    }
+  };
+  AddCalls(SlotInfo.CSInfo);
+  for (auto &P : SlotInfo.ConstCSInfo)
+    AddCalls(P.second);
+
+  if (IsExported)
+    ExportedGUIDs.insert(TheFn.getGUID());
+
+  // Record in summary for use in devirtualization during the ThinLTO import
+  // step.
+  Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
+  if (GlobalValue::isLocalLinkage(S->linkage())) {
+    if (IsExported)
+      // If target is a local function and we are exporting it by
+      // devirtualizing a call in another module, we need to record the
+      // promoted name.
+      Res->SingleImplName = ModuleSummaryIndex::getGlobalNameForLocal(
+          TheFn.name(), ExportSummary.getModuleHash(S->modulePath()));
+    else {
+      LocalWPDTargetsMap[TheFn].push_back(SlotSummary);
+      Res->SingleImplName = TheFn.name();
+    }
+  } else
+    Res->SingleImplName = TheFn.name();
+
+  // Name will be empty if this thin link driven off of serialized combined
+  // index (e.g. llvm-lto). However, WPD is not supported/invoked for the
+  // legacy LTO API anyway.
+  assert(!Res->SingleImplName.empty());
+
+  return true;
+}
+
 void DevirtModule::tryICallBranchFunnel(
     MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
     WholeProgramDevirtResolution *Res, VTableSlot Slot) {
   Triple T(M.getTargetTriple());
   if (T.getArch() != Triple::x86_64)
     return;
 
   if (TargetsForSlot.size() > ClThreshold)
for (DevirtCallSite Call : DevirtCalls) {
                                                    &NumUnsafeUses);
     }
 
     CI->eraseFromParent();
   }
 }
 
 void DevirtModule::importResolution(VTableSlot Slot, VTableSlotInfo &SlotInfo) {
+  auto *TypeId = dyn_cast<MDString>(Slot.TypeID);
+  if (!TypeId)
+    return;
   const TypeIdSummary *TidSummary =
-      ImportSummary->getTypeIdSummary(cast<MDString>(Slot.TypeID)->getString());
+      ImportSummary->getTypeIdSummary(TypeId->getString());
   if (!TidSummary)
     return;
   auto ResI = TidSummary->WPDRes.find(Slot.ByteOffset);
   if (ResI == TidSummary->WPDRes.end())
     return;
   const WholeProgramDevirtResolution &Res = ResI->second;
 
   if (Res.TheKind == WholeProgramDevirtResolution::SingleImpl) {
+    assert(!Res.SingleImplName.empty());
     // The type of the function in the declaration is irrelevant because every
     // call site will cast it to the correct type.
     Constant *SingleImpl =
         cast<Constant>(M.getOrInsertFunction(Res.SingleImplName,
                                              Type::getVoidTy(M.getContext()))
                            .getCallee());
 
     // This is the import phase so we should not be exporting anything.
bool DevirtModule::run() {
   if (RemarksEnabled) {
     // Generate remarks for each devirtualized function.
     for (const auto &DT : DevirtTargets) {
       Function *F = DT.second;
 
       using namespace ore;
       OREGetter(F).emit(OptimizationRemark(DEBUG_TYPE, "Devirtualized", F)
                         << "devirtualized "
-                        << NV("FunctionName", F->getName()));
+                        << NV("FunctionName", DT.first));
     }
   }
 
   removeRedundantTypeTests();
 
   // Rebuild each global we touched as part of virtual constant propagation to
   // include the before and after bytes.
   if (DidVirtualConstProp)
     for (VTableBits &B : Bits)
       rebuildGlobal(B);
 
   return true;
 }
+
+void DevirtIndex::run() {
+  if (ExportSummary.typeIdMetadataMap().empty())
+    return;
+
+  DenseMap<GlobalValue::GUID, std::vector<StringRef>> NameByGUID;
+  for (auto &P : ExportSummary.typeIdMetadataMap()) {
+    NameByGUID[GlobalValue::getGUID(P.first)].push_back(P.first);
+  }
+
+  // Collect information from summary about which calls to try to devirtualize.
+  for (auto &P : ExportSummary) {
+    for (auto &S : P.second.SummaryList) {
+      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 (StringRef Name : NameByGUID[VF.GUID]) {
+          CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeTestAssumeUser(FS);
+        }
+      }
+      for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
+        for (StringRef Name : NameByGUID[VF.GUID]) {
+          CallSlots[{Name, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
+        }
+      }
+      for (const FunctionSummary::ConstVCall &VC :
+           FS->type_test_assume_const_vcalls()) {
+        for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
+          CallSlots[{Name, VC.VFunc.Offset}]
+              .ConstCSInfo[VC.Args]
+              .addSummaryTypeTestAssumeUser(FS);
+        }
+      }
+      for (const FunctionSummary::ConstVCall &VC :
+           FS->type_checked_load_const_vcalls()) {
+        for (StringRef Name : NameByGUID[VC.VFunc.GUID]) {
+          CallSlots[{Name, VC.VFunc.Offset}]
+              .ConstCSInfo[VC.Args]
+              .addSummaryTypeCheckedLoadUser(FS);
+        }
+      }
+    }
+  }
+
+  std::set<ValueInfo> DevirtTargets;
+  // For each (type, offset) pair:
+  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<ValueInfo> TargetsForSlot;
+    auto *TidSummary = ExportSummary.getTypeIdMetadataSummary(S.first.TypeID);
+    assert(TidSummary);
+    if (tryFindVirtualCallTargets(TargetsForSlot, *TidSummary,
+                                  S.first.ByteOffset)) {
+      WholeProgramDevirtResolution *Res =
+          &ExportSummary.getOrInsertTypeIdSummary(S.first.TypeID)
+               .WPDRes[S.first.ByteOffset];
+
+      if (!trySingleImplDevirt(TargetsForSlot, S.first, S.second, Res,
+                               DevirtTargets))
+        continue;
+    }
+  }
+
+  // Optionally have the thin link print message for each devirtualized
+  // function.
+  if (PrintSummaryDevirt)
+    for (const auto &DT : DevirtTargets)
+      errs() << "Devirtualized call to " << DT << "\n";
+
+  return;
+}

test/Assembler/thinlto-vtable-summary.ll

+; Test summary parsing of index-based WPD related summary fields
+; RUN: llvm-as %s -o - | llvm-dis -o %t.ll
+; RUN: grep "^\^" %s >%t2
+; RUN: grep "^\^" %t.ll >%t3
+; Expect that the summary information is the same after round-trip through
+; llvm-as and llvm-dis.
+; RUN: diff %t2 %t3
+
+source_filename = "thinlto-vtable-summary.ll"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+%struct.A = type { i32 (...)** }
+%struct.B = type { %struct.A }
+%struct.C = type { %struct.A }
+
+@_ZTV1B = constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.B*, i32)* @_ZN1B1fEi to i8*), i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1nEi to i8*)] }, !type !0, !type !1
+@_ZTV1C = constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.C*, i32)* @_ZN1C1fEi to i8*), i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1nEi to i8*)] }, !type !0, !type !2
+
+declare i32 @_ZN1B1fEi(%struct.B*, i32)
+
+declare i32 @_ZN1A1nEi(%struct.A*, i32)
+
+declare i32 @_ZN1C1fEi(%struct.C*, i32)
+
+!0 = !{i64 16, !"_ZTS1A"}
+!1 = !{i64 16, !"_ZTS1B"}
+!2 = !{i64 16, !"_ZTS1C"}
+
+^0 = module: (path: "<stdin>", hash: (0, 0, 0, 0, 0))
+^1 = gv: (name: "_ZN1A1nEi") ; guid = 1621563287929432257
+^2 = gv: (name: "_ZTV1B", summaries: (variable: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), varFlags: (readonly: 0), vTableFuncs: ((virtFunc: ^3, offset: 16), (virtFunc: ^1, offset: 24)), refs: (^3, ^1)))) ; guid = 5283576821522790367
+^3 = gv: (name: "_ZN1B1fEi") ; guid = 7162046368816414394
+^4 = gv: (name: "_ZTV1C", summaries: (variable: (module: ^0, flags: (linkage: external, notEligibleToImport: 0, live: 0, dsoLocal: 0), varFlags: (readonly: 0), vTableFuncs: ((virtFunc: ^5, offset: 16), (virtFunc: ^1, offset: 24)), refs: (^1, ^5)))) ; guid = 13624023785555846296
+^5 = gv: (name: "_ZN1C1fEi") ; guid = 14876272565662207556
+^6 = typeidMetadata: (name: "_ZTS1A", summary: ((offset: 16, ^2), (offset: 16, ^4))) ; guid = 7004155349499253778
+^7 = typeidMetadata: (name: "_ZTS1B", summary: ((offset: 16, ^2))) ; guid = 6203814149063363976
+^8 = typeidMetadata: (name: "_ZTS1C", summary: ((offset: 16, ^4))) ; guid = 1884921850105019584

test/ThinLTO/X86/Inputs/devirt2.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+%struct.A = type { i32 (...)** }
+%struct.B = type { %struct.A }
+%struct.C = type { %struct.A }
+%struct.D = type { i32 (...)** }
+%struct.E = type { i32 (...)** }
+
+@_ZTV1B = constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.B*, i32)* @_ZN1B1fEi to i8*), i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1nEi to i8*)] }, !type !0, !type !1
+@_ZTV1C = constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.C*, i32)* @_ZN1C1fEi to i8*), i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1nEi to i8*)] }, !type !0, !type !2
+@_ZTV1D = constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.D*, i32)* @_ZN1D1mEi to i8*)] }, !type !3
+@_ZTV1E = constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.E*, i32)* @_ZN1E1mEi to i8*)] }, !type !4
+
+define i32 @_ZN1B1fEi(%struct.B* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+define internal i32 @_ZN1A1nEi(%struct.A* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+define i32 @_ZN1C1fEi(%struct.C* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+define i32 @_ZN1D1mEi(%struct.D* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+define internal i32 @_ZN1E1mEi(%struct.E* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+define i32 @test2(%struct.E* %obj, i32 %a) {
+entry:
+  %0 = bitcast %struct.E* %obj to i8***
+  %vtable2 = load i8**, i8*** %0
+  %1 = bitcast i8** %vtable2 to i8*
+  %p2 = call i1 @llvm.type.test(i8* %1, metadata !"_ZTS1E")
+  call void @llvm.assume(i1 %p2)
+
+  %2 = bitcast i8** %vtable2 to i32 (%struct.E*, i32)**
+  %fptr33 = load i32 (%struct.E*, i32)*, i32 (%struct.E*, i32)** %2, align 8
+
+  %call4 = tail call i32 %fptr33(%struct.E* nonnull %obj, i32 %a)
+  ret i32 %call4
+}
+
+attributes #0 = { noinline optnone }
+
+declare i1 @llvm.type.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{i64 16, !"_ZTS1A"}
+!1 = !{i64 16, !"_ZTS1B"}
+!2 = !{i64 16, !"_ZTS1C"}
+!3 = !{i64 16, !"_ZTS1D"}
+!4 = !{i64 16, !"_ZTS1E"}

test/ThinLTO/X86/devirt.ll

+; REQUIRES: x86-registered-target
+
+; Test devirtualization through the thin link and backend.
+
+; Generate split module with summary for hybrid Thin/Regular LTO WPD.
+; RUN: opt -thinlto-bc -thinlto-split-lto-unit -o %t.o %s
+
+; Check that we have module flag showing splitting enabled, and that we don't
+; generate summary information needed for index-based WPD.
+; RUN: llvm-modextract -b -n=0 %t.o -o %t.o.0
+; RUN: llvm-dis -o - %t.o.0 | FileCheck %s --check-prefix=ENABLESPLITFLAG --implicit-check-not=vTableFuncs --implicit-check-not=typeidMetadata
+; RUN: llvm-modextract -b -n=1 %t.o -o %t.o.1
+; RUN: llvm-dis -o - %t.o.1 | FileCheck %s --check-prefix=ENABLESPLITFLAG --implicit-check-not=vTableFuncs --implicit-check-not=typeidMetadata
+; ENABLESPLITFLAG: !{i32 1, !"EnableSplitLTOUnit", i32 1}
+
+; Generate unsplit module with summary for ThinLTO index-based WPD.
+; RUN: opt -thinlto-bc -o %t2.o %s
+
+; Check that we don't have module flag when splitting not enabled for ThinLTO,
+; and that we generate summary information needed for index-based WPD.
+; RUN: llvm-dis -o - %t2.o | FileCheck %s --check-prefix=NOENABLESPLITFLAG
+; NOENABLESPLITFLAG-DAG: !{i32 1, !"EnableSplitLTOUnit", i32 0}
+; NOENABLESPLITFLAG-DAG: [[An:\^[0-9]+]] = gv: (name: "_ZN1A1nEi"
+; NOENABLESPLITFLAG-DAG: [[Bf:\^[0-9]+]] = gv: (name: "_ZN1B1fEi"
+; NOENABLESPLITFLAG-DAG: [[Cf:\^[0-9]+]] = gv: (name: "_ZN1C1fEi"
+; NOENABLESPLITFLAG-DAG: [[Dm:\^[0-9]+]] = gv: (name: "_ZN1D1mEi"
+; NOENABLESPLITFLAG-DAG: [[B:\^[0-9]+]] = gv: (name: "_ZTV1B", {{.*}} vTableFuncs: ((virtFunc: [[Bf]], offset: 16), (virtFunc: [[An]], offset: 24)), refs: ([[Bf]], [[An]])
+; NOENABLESPLITFLAG-DAG: [[C:\^[0-9]+]] = gv: (name: "_ZTV1C", {{.*}} vTableFuncs: ((virtFunc: [[Cf]], offset: 16), (virtFunc: [[An]], offset: 24)), refs: ([[An]], [[Cf]])
+; NOENABLESPLITFLAG-DAG: [[D:\^[0-9]+]] = gv: (name: "_ZTV1D", {{.*}} vTableFuncs: ((virtFunc: [[Dm]], offset: 16)), refs: ([[Dm]])
+; NOENABLESPLITFLAG-DAG: typeidMetadata: (name: "_ZTS1A", summary: ((offset: 16, [[B]]), (offset: 16, [[C]])))
+; NOENABLESPLITFLAG-DAG: typeidMetadata: (name: "_ZTS1B", summary: ((offset: 16, [[B]])))
+; NOENABLESPLITFLAG-DAG: typeidMetadata: (name: "_ZTS1C", summary: ((offset: 16, [[C]])))
+; Type Id on _ZTV1D should have been promoted
+; NOENABLESPLITFLAG-DAG: typeidMetadata: (name: "1${{.*}}", summary: ((offset: 16, [[D]])))
+
+; Legacy PM, Index based WPD
+; RUN: llvm-lto2 run %t2.o -save-temps -pass-remarks=. \
+; RUN:   -o %t3 \
+; RUN:   -r=%t2.o,test,px \
+; RUN:   -r=%t2.o,_ZN1A1nEi,p \
+; RUN:   -r=%t2.o,_ZN1B1fEi,p \
+; RUN:   -r=%t2.o,_ZN1C1fEi,p \
+; RUN:   -r=%t2.o,_ZN1D1mEi,p \
+; RUN:   -r=%t2.o,_ZTV1B,px \
+; RUN:   -r=%t2.o,_ZTV1C,px \
+; RUN:   -r=%t2.o,_ZTV1D,px 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t3.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+; New PM, Index based WPD
+; RUN: llvm-lto2 run %t2.o -save-temps -use-new-pm -pass-remarks=. \
+; RUN:   -o %t3 \
+; RUN:   -r=%t2.o,test,px \
+; RUN:   -r=%t2.o,_ZN1A1nEi,p \
+; RUN:   -r=%t2.o,_ZN1B1fEi,p \
+; RUN:   -r=%t2.o,_ZN1C1fEi,p \
+; RUN:   -r=%t2.o,_ZN1D1mEi,p \
+; RUN:   -r=%t2.o,_ZTV1B,px \
+; RUN:   -r=%t2.o,_ZTV1C,px \
+; RUN:   -r=%t2.o,_ZTV1D,px 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t3.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+; Legacy PM
+; RUN: llvm-lto2 run %t.o -save-temps -pass-remarks=. \
+; RUN:   -o %t3 \
+; RUN:   -r=%t.o,test,px \
+; RUN:   -r=%t.o,_ZN1A1nEi,p \
+; RUN:   -r=%t.o,_ZN1B1fEi,p \
+; RUN:   -r=%t.o,_ZN1C1fEi,p \
+; RUN:   -r=%t.o,_ZN1D1mEi,p \
+; RUN:   -r=%t.o,_ZTV1B, \
+; RUN:   -r=%t.o,_ZTV1C, \
+; RUN:   -r=%t.o,_ZTV1D, \
+; RUN:   -r=%t.o,_ZN1A1nEi, \
+; RUN:   -r=%t.o,_ZN1B1fEi, \
+; RUN:   -r=%t.o,_ZN1C1fEi, \
+; RUN:   -r=%t.o,_ZN1D1mEi, \
+; RUN:   -r=%t.o,_ZTV1B,px \
+; RUN:   -r=%t.o,_ZTV1C,px \
+; RUN:   -r=%t.o,_ZTV1D,px 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t3.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+; New PM
+; RUN: llvm-lto2 run %t.o -save-temps -use-new-pm -pass-remarks=. \
+; RUN:   -o %t3 \
+; RUN:   -r=%t.o,test,px \
+; RUN:   -r=%t.o,_ZN1A1nEi,p \
+; RUN:   -r=%t.o,_ZN1B1fEi,p \
+; RUN:   -r=%t.o,_ZN1C1fEi,p \
+; RUN:   -r=%t.o,_ZN1D1mEi,p \
+; RUN:   -r=%t.o,_ZTV1B, \
+; RUN:   -r=%t.o,_ZTV1C, \
+; RUN:   -r=%t.o,_ZTV1D, \
+; RUN:   -r=%t.o,_ZN1A1nEi, \
+; RUN:   -r=%t.o,_ZN1B1fEi, \
+; RUN:   -r=%t.o,_ZN1C1fEi, \
+; RUN:   -r=%t.o,_ZN1D1mEi, \
+; RUN:   -r=%t.o,_ZTV1B,px \
+; RUN:   -r=%t.o,_ZTV1C,px \
+; RUN:   -r=%t.o,_ZTV1D,px 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t3.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+; REMARK-DAG: single-impl: devirtualized a call to _ZN1A1nEi
+; REMARK-DAG: single-impl: devirtualized a call to _ZN1D1mEi
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+%struct.A = type { i32 (...)** }
+%struct.B = type { %struct.A }
+%struct.C = type { %struct.A }
+%struct.D = type { i32 (...)** }
+
+@_ZTV1B = constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.B*, i32)* @_ZN1B1fEi to i8*), i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1nEi to i8*)] }, !type !0, !type !1
+@_ZTV1C = constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.C*, i32)* @_ZN1C1fEi to i8*), i8* bitcast (i32 (%struct.A*, i32)* @_ZN1A1nEi to i8*)] }, !type !0, !type !2
+@_ZTV1D = constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.D*, i32)* @_ZN1D1mEi to i8*)] }, !type !3
+
+
+; CHECK-IR-LABEL: define i32 @test
+define i32 @test(%struct.A* %obj, %struct.D* %obj2, i32 %a) {
+entry:
+  %0 = bitcast %struct.A* %obj to i8***
+  %vtable = load i8**, i8*** %0
+  %1 = bitcast i8** %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %1, metadata !"_ZTS1A")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr i8*, i8** %vtable, i32 1
+  %2 = bitcast i8** %fptrptr to i32 (%struct.A*, i32)**
+  %fptr1 = load i32 (%struct.A*, i32)*, i32 (%struct.A*, i32)** %2, align 8
+
+  ; Check that the call was devirtualized.
+  ; CHECK-IR: %call = tail call i32 @_ZN1A1nEi
+  %call = tail call i32 %fptr1(%struct.A* nonnull %obj, i32 %a)
+
+  %3 = bitcast i8** %vtable to i32 (%struct.A*, i32)**
+  %fptr22 = load i32 (%struct.A*, i32)*, i32 (%struct.A*, i32)** %3, align 8
+
+  ; We still have to call it as virtual.
+  ; CHECK-IR: %call3 = tail call i32 %fptr22
+  %call3 = tail call i32 %fptr22(%struct.A* nonnull %obj, i32 %call)
+
+  %4 = bitcast %struct.D* %obj2 to i8***
+  %vtable2 = load i8**, i8*** %4
+  %5 = bitcast i8** %vtable2 to i8*
+  %p2 = call i1 @llvm.type.test(i8* %5, metadata !4)
+  call void @llvm.assume(i1 %p2)
+
+  %6 = bitcast i8** %vtable2 to i32 (%struct.D*, i32)**
+  %fptr33 = load i32 (%struct.D*, i32)*, i32 (%struct.D*, i32)** %6, align 8
+
+  ; Check that the call was devirtualized.
+  ; CHECK-IR: %call4 = tail call i32 @_ZN1D1mEi
+  %call4 = tail call i32 %fptr33(%struct.D* nonnull %obj2, i32 %call3)
+  ret i32 %call4
+}
+; CHECK-IR-LABEL: ret i32
+; CHECK-IR-LABEL: }
+
+declare i1 @llvm.type.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+define i32 @_ZN1B1fEi(%struct.B* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+define i32 @_ZN1A1nEi(%struct.A* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+define i32 @_ZN1C1fEi(%struct.C* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+define i32 @_ZN1D1mEi(%struct.D* %this, i32 %a) #0 {
+   ret i32 0;
+}
+
+; Make sure we don't inline or otherwise optimize out the direct calls.
+attributes #0 = { noinline optnone }
+
+!0 = !{i64 16, !"_ZTS1A"}
+!1 = !{i64 16, !"_ZTS1B"}
+!2 = !{i64 16, !"_ZTS1C"}
+!3 = !{i64 16, !4}
+!4 = distinct !{}

test/ThinLTO/X86/devirt2.ll

+; REQUIRES: x86-registered-target
+
+; Test devirtualization requiring promotion of local targets.
+
+; Generate split module with summary for hybrid Thin/Regular LTO WPD.
+; RUN: opt -thinlto-bc -thinlto-split-lto-unit -o %t1.o %s
+; RUN: opt -thinlto-bc -thinlto-split-lto-unit -o %t2.o %p/Inputs/devirt2.ll
+
+; Check that we have module flag showing splitting enabled, and that we don't
+; generate summary information needed for index-based WPD.
+; RUN: llvm-modextract -b -n=0 %t2.o -o %t2.o.0
+; RUN: llvm-dis -o - %t2.o.0 | FileCheck %s --check-prefix=ENABLESPLITFLAG --implicit-check-not=vTableFuncs --implicit-check-not=typeidMetadata
+; RUN: llvm-modextract -b -n=1 %t2.o -o %t2.o.1
+; RUN: llvm-dis -o - %t2.o.1 | FileCheck %s --check-prefix=ENABLESPLITFLAG --implicit-check-not=vTableFuncs --implicit-check-not=typeidMetadata
+; ENABLESPLITFLAG: !{i32 1, !"EnableSplitLTOUnit", i32 1}
+
+; Generate unsplit module with summary for ThinLTO index-based WPD.
+; RUN: opt -thinlto-bc -o %t3.o %s
+; RUN: opt -thinlto-bc -o %t4.o %p/Inputs/devirt2.ll
+
+; Check that we don't have module flag when splitting not enabled for ThinLTO,
+; and that we generate summary information needed for index-based WPD.
+; RUN: llvm-dis -o - %t4.o | FileCheck %s --check-prefix=NOENABLESPLITFLAG
+; NOENABLESPLITFLAG-DAG: !{i32 1, !"EnableSplitLTOUnit", i32 0}
+; NOENABLESPLITFLAG-DAG: [[An:\^[0-9]+]] = gv: (name: "_ZN1A1nEi"
+; NOENABLESPLITFLAG-DAG: [[Bf:\^[0-9]+]] = gv: (name: "_ZN1B1fEi"
+; NOENABLESPLITFLAG-DAG: [[Cf:\^[0-9]+]] = gv: (name: "_ZN1C1fEi"
+; NOENABLESPLITFLAG-DAG: [[Dm:\^[0-9]+]] = gv: (name: "_ZN1D1mEi"
+; NOENABLESPLITFLAG-DAG: [[B:\^[0-9]+]] = gv: (name: "_ZTV1B", {{.*}} vTableFuncs: ((virtFunc: [[Bf]], offset: 16), (virtFunc: [[An]], offset: 24)), refs: ([[Bf]], [[An]])
+; NOENABLESPLITFLAG-DAG: [[C:\^[0-9]+]] = gv: (name: "_ZTV1C", {{.*}} vTableFuncs: ((virtFunc: [[Cf]], offset: 16), (virtFunc: [[An]], offset: 24)), refs: ([[An]], [[Cf]])
+; NOENABLESPLITFLAG-DAG: [[D:\^[0-9]+]] = gv: (name: "_ZTV1D", {{.*}} vTableFuncs: ((virtFunc: [[Dm]], offset: 16)), refs: ([[Dm]])
+; NOENABLESPLITFLAG-DAG: typeidMetadata: (name: "_ZTS1A", summary: ((offset: 16, [[B]]), (offset: 16, [[C]])))
+; NOENABLESPLITFLAG-DAG: typeidMetadata: (name: "_ZTS1B", summary: ((offset: 16, [[B]])))
+; NOENABLESPLITFLAG-DAG: typeidMetadata: (name: "_ZTS1C", summary: ((offset: 16, [[C]])))
+; NOENABLESPLITFLAG-DAG: typeidMetadata: (name: "_ZTS1D", summary: ((offset: 16, [[D]])))
+
+; Legacy PM, Index based WPD
+; RUN: llvm-lto2 run %t3.o %t4.o -save-temps -pass-remarks=. \
+; RUN:   -wholeprogramdevirt-print-index-based \
+; RUN:   -o %t5 \
+; RUN:   -r=%t3.o,test,px \
+; RUN:   -r=%t3.o,_ZTV1B, \
+; RUN:   -r=%t3.o,_ZTV1C, \
+; RUN:   -r=%t3.o,_ZTV1D, \
+; RUN:   -r=%t3.o,test2, \
+; RUN:   -r=%t4.o,_ZN1B1fEi,p \
+; RUN:   -r=%t4.o,_ZN1C1fEi,p \
+; RUN:   -r=%t4.o,_ZN1D1mEi,p \
+; RUN:   -r=%t4.o,test2,px \
+; RUN:   -r=%t4.o,_ZTV1B,px \
+; RUN:   -r=%t4.o,_ZTV1C,px \
+; RUN:   -r=%t4.o,_ZTV1D,px \
+; RUN:   -r=%t4.o,_ZTV1E,px 2>&1 | FileCheck %s --check-prefix=REMARK --check-prefix=PRINT
+; RUN: llvm-dis %t5.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR1
+; RUN: llvm-dis %t5.2.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR2
+; RUN: nm %t5.1 | FileCheck %s --check-prefix=NM-INDEX1
+; RUN: nm %t5.2 | FileCheck %s --check-prefix=NM-INDEX2
+
+; New PM, Index based WPD
+; RUN: llvm-lto2 run %t3.o %t4.o -save-temps -use-new-pm -pass-remarks=. \
+; RUN:   -wholeprogramdevirt-print-index-based \
+; RUN:   -o %t5 \
+; RUN:   -r=%t3.o,test,px \
+; RUN:   -r=%t3.o,_ZTV1B, \
+; RUN:   -r=%t3.o,_ZTV1C, \
+; RUN:   -r=%t3.o,_ZTV1D, \
+; RUN:   -r=%t3.o,test2, \
+; RUN:   -r=%t4.o,_ZN1B1fEi,p \
+; RUN:   -r=%t4.o,_ZN1C1fEi,p \
+; RUN:   -r=%t4.o,_ZN1D1mEi,p \
+; RUN:   -r=%t4.o,test2,px \
+; RUN:   -r=%t4.o,_ZTV1B,px \
+; RUN:   -r=%t4.o,_ZTV1C,px \
+; RUN:   -r=%t4.o,_ZTV1D,px \
+; RUN:   -r=%t4.o,_ZTV1E,px 2>&1 | FileCheck %s --check-prefix=REMARK --check-prefix=PRINT
+; RUN: llvm-dis %t5.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR1
+; RUN: llvm-dis %t5.2.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR2
+; RUN: nm %t5.1 | FileCheck %s --check-prefix=NM-INDEX1
+; RUN: nm %t5.2 | FileCheck %s --check-prefix=NM-INDEX2
+
+; NM-INDEX1-DAG: U _ZN1A1nEi.llvm.
+; NM-INDEX1-DAG: U _ZN1E1mEi.llvm.
+; NM-INDEX1-DAG: U _ZN1D1mEi
+
+; NM-INDEX2-DAG: T _ZN1A1nEi.llvm.
+; NM-INDEX2-DAG: T _ZN1E1mEi.llvm.
+; NM-INDEX2-DAG: T _ZN1D1mEi
+; NM-INDEX2-DAG: t _ZN1B1fEi
+; NM-INDEX2-DAG: t _ZN1C1fEi
+
+; Index based WPD, distributed backends
+; RUN: llvm-lto2 run %t3.o %t4.o -save-temps -use-new-pm \
+; RUN:   -thinlto-distributed-indexes -wholeprogramdevirt-print-index-based \
+; RUN:   -o %t5 \
+; RUN:   -r=%t3.o,test,px \
+; RUN:   -r=%t3.o,_ZTV1B, \
+; RUN:   -r=%t3.o,_ZTV1C, \
+; RUN:   -r=%t3.o,_ZTV1D, \
+; RUN:   -r=%t3.o,test2, \
+; RUN:   -r=%t4.o,_ZN1B1fEi,p \
+; RUN:   -r=%t4.o,_ZN1C1fEi,p \
+; RUN:   -r=%t4.o,_ZN1D1mEi,p \
+; RUN:   -r=%t4.o,test2,px \
+; RUN:   -r=%t4.o,_ZTV1B,px \
+; RUN:   -r=%t4.o,_ZTV1C,px \
+; RUN:   -r=%t4.o,_ZTV1D,px \
+; RUN:   -r=%t4.o,_ZTV1E,px 2>&1 | FileCheck %s --check-prefix=PRINT
+
+; PRINT-DAG: Devirtualized call to {{.*}} (_ZN1A1nEi)
+; PRINT-DAG: Devirtualized call to {{.*}} (_ZN1E1mEi)
+; PRINT-DAG: Devirtualized call to {{.*}} (_ZN1D1mEi)
+
+; Legacy PM
+; RUN: llvm-lto2 run %t1.o %t2.o -save-temps -pass-remarks=. \
+; RUN:   -o %t5 \
+; RUN:   -r=%t1.o,test,px \
+; RUN:   -r=%t1.o,_ZTV1B, \
+; RUN:   -r=%t1.o,_ZTV1C, \
+; RUN:   -r=%t1.o,_ZTV1D, \
+; RUN:   -r=%t1.o,test2, \
+; RUN:   -r=%t2.o,_ZN1A1nEi,p \
+; RUN:   -r=%t2.o,_ZN1B1fEi,p \
+; RUN:   -r=%t2.o,_ZN1C1fEi,p \
+; RUN:   -r=%t2.o,_ZN1D1mEi,p \
+; RUN:   -r=%t2.o,_ZN1E1mEi,p \
+; RUN:   -r=%t2.o,_ZTV1B, \
+; RUN:   -r=%t2.o,_ZTV1C, \
+; RUN:   -r=%t2.o,_ZTV1D, \
+; RUN:   -r=%t2.o,_ZTV1E, \
+; RUN:   -r=%t2.o,test2,px \
+; RUN:   -r=%t2.o,_ZN1A1nEi, \
+; RUN:   -r=%t2.o,_ZN1B1fEi, \
+; RUN:   -r=%t2.o,_ZN1C1fEi, \
+; RUN:   -r=%t2.o,_ZN1D1mEi, \
+; RUN:   -r=%t2.o,_ZN1E1mEi, \
+; RUN:   -r=%t2.o,_ZTV1B,px \
+; RUN:   -r=%t2.o,_ZTV1C,px \
+; RUN:   -r=%t2.o,_ZTV1D,px \
+; RUN:   -r=%t2.o,_ZTV1E,px 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t5.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR1
+; RUN: llvm-dis %t5.2.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR2
+; RUN: nm %t5.1 | FileCheck %s --check-prefix=NM-HYBRID1
+; RUN: nm %t5.2 | FileCheck %s --check-prefix=NM-HYBRID2
+
+; New PM
+; RUN: llvm-lto2 run %t1.o %t2.o -save-temps -use-new-pm -pass-remarks=. \
+; RUN:   -o %t5 \
+; RUN:   -r=%t1.o,test,px \
+; RUN:   -r=%t1.o,_ZTV1B, \
+; RUN:   -r=%t1.o,_ZTV1C, \
+; RUN:   -r=%t1.o,_ZTV1D, \
+; RUN:   -r=%t1.o,test2, \
+; RUN:   -r=%t2.o,_ZN1A1nEi,p \
+; RUN:   -r=%t2.o,_ZN1B1fEi,p \
+; RUN:   -r=%t2.o,_ZN1C1fEi,p \
+; RUN:   -r=%t2.o,_ZN1D1mEi,p \
+; RUN:   -r=%t2.o,_ZN1E1mEi,p \
+; RUN:   -r=%t2.o,_ZTV1B, \
+; RUN:   -r=%t2.o,_ZTV1C, \
+; RUN:   -r=%t2.o,_ZTV1D, \
+; RUN:   -r=%t2.o,_ZTV1E, \
+; RUN:   -r=%t2.o,test2,px \
+; RUN:   -r=%t2.o,_ZN1A1nEi, \
+; RUN:   -r=%t2.o,_ZN1B1fEi, \
+; RUN:   -r=%t2.o,_ZN1C1fEi, \
+; RUN:   -r=%t2.o,_ZN1D1mEi, \
+; RUN:   -r=%t2.o,_ZN1E1mEi, \
+; RUN:   -r=%t2.o,_ZTV1B,px \
+; RUN:   -r=%t2.o,_ZTV1C,px \
+; RUN:   -r=%t2.o,_ZTV1D,px \
+; RUN:   -r=%t2.o,_ZTV1E,px 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: llvm-dis %t5.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR1
+; RUN: llvm-dis %t5.2.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR2
+; RUN: nm %t5.1 | FileCheck %s --check-prefix=NM-HYBRID1
+; RUN: nm %t5.2 | FileCheck %s --check-prefix=NM-HYBRID2
+
+; NM-HYBRID1-DAG: U _ZN1A1nEi$
+; NM-HYBRID1-DAG: U _ZN1E1mEi$
+; NM-HYBRID1-DAG: U _ZN1D1mEi
+
+; NM-HYBRID2-DAG: T _ZN1A1nEi$
+; NM-HYBRID2-DAG: T _ZN1E1mEi$
+; NM-HYBRID2-DAG: T _ZN1D1mEi
+; NM-HYBRID2-DAG: T _ZN1B1fEi
+; NM-HYBRID2-DAG: T _ZN1C1fEi
+
+; REMARK-DAG: single-impl: devirtualized a call to _ZN1A1nEi
+; REMARK-DAG: single-impl: devirtualized a call to _ZN1D1mEi
+; We should devirt call to _ZN1E1mEi once in importing module and once
+; in original (exporting) module.
+; REMARK-DAG-COUNT-2: single-impl: devirtualized a call to _ZN1E1mEi
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+%struct.A = type { i32 (...)** }
+%struct.B = type { %struct.A }
+%struct.C = type { %struct.A }
+%struct.D = type { i32 (...)** }
+%struct.E = type { i32 (...)** }
+
+@_ZTV1B = external constant [4 x i8*]
+@_ZTV1C = external constant [4 x i8*]
+@_ZTV1D = external constant [3 x i8*]
+
+; CHECK-IR1-LABEL: define i32 @test
+define i32 @test(%struct.A* %obj, %struct.D* %obj2, %struct.E* %obj3, i32 %a) {
+entry:
+  %0 = bitcast %struct.A* %obj to i8***
+  %vtable = load i8**, i8*** %0
+  %1 = bitcast i8** %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %1, metadata !"_ZTS1A")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr i8*, i8** %vtable, i32 1
+  %2 = bitcast i8** %fptrptr to i32 (%struct.A*, i32)**
+  %fptr1 = load i32 (%struct.A*, i32)*, i32 (%struct.A*, i32)** %2, align 8
+
+  ; Check that the call was devirtualized. Ignore extra character before
+  ; symbol name which would happen if it was promoted during module
+  ; splitting for hybrid WPD.
+  ; CHECK-IR1: %call = tail call i32 bitcast (void ()* @{{.*}}_ZN1A1nEi
+  %call = tail call i32 %fptr1(%struct.A* nonnull %obj, i32 %a)
+
+  %3 = bitcast i8** %vtable to i32 (%struct.A*, i32)**
+  %fptr22 = load i32 (%struct.A*, i32)*, i32 (%struct.A*, i32)** %3, align 8
+
+  ; We still have to call it as virtual.
+  ; CHECK-IR1: %call3 = tail call i32 %fptr22
+  %call3 = tail call i32 %fptr22(%struct.A* nonnull %obj, i32 %call)
+
+  %4 = bitcast %struct.D* %obj2 to i8***
+  %vtable2 = load i8**, i8*** %4
+  %5 = bitcast i8** %vtable2 to i8*
+  %p2 = call i1 @llvm.type.test(i8* %5, metadata !"_ZTS1D")
+  call void @llvm.assume(i1 %p2)
+
+  %6 = bitcast i8** %vtable2 to i32 (%struct.D*, i32)**
+  %fptr33 = load i32 (%struct.D*, i32)*, i32 (%struct.D*, i32)** %6, align 8
+
+  ; Check that the call was devirtualized.
+  ; CHECK-IR1: %call4 = tail call i32 bitcast (void ()* @_ZN1D1mEi
+  %call4 = tail call i32 %fptr33(%struct.D* nonnull %obj2, i32 %call3)
+
+  %call5 = tail call i32 @test2(%struct.E* nonnull %obj3, i32 %call4)
+  ret i32 %call5
+}
+; CHECK-IR1-LABEL: ret i32
+; CHECK-IR1-LABEL: }
+
+; CHECK-IR2: define i32 @test2
+; CHECK-IR2-NEXT: entry:
+; Check that the call was devirtualized. Ignore extra character before
+; symbol name which would happen if it was promoted during module
+; splitting for hybrid WPD.
+; CHECK-IR2-NEXT:   %call4 = tail call i32 @{{.*}}_ZN1E1mEi
+
+declare i1 @llvm.type.test(i8*, metadata)
+declare void @llvm.assume(i1)
+declare i32 @test2(%struct.E* %obj, i32 %a)

test/ThinLTO/X86/nodevirt-nonpromoted-typeid.ll

+; REQUIRES: x86-registered-target
+
+; Test that index-only devirtualization handles and ignores any
+; type metadata that could not be summarized (because it was internal
+; and could not be promoted due to the fact that the module has
+; no external symbols and therefore could not be assigned a unique
+; identifier). In this case we should simply not get the type
+; metadata summary entries, and no promotion will occur.
+
+; Generate unsplit module with summary for ThinLTO index-based WPD.
+; RUN: opt -thinlto-bc -thinlto-split-lto-unit=false -o %t2.o %s
+
+; Check that we don't have module flag when splitting not enabled for ThinLTO,
+; and that we generate summary information needed for index-based WPD.
+; RUN: llvm-dis -o - %t2.o | FileCheck %s --check-prefix=DIS
+; DIS-NOT: typeIdInfo
+; DIS-NOT: typeidMetadata
+
+; Legacy PM, Index based WPD
+; RUN: llvm-lto2 run %t2.o -save-temps -pass-remarks=. \
+; RUN:   -o %t3 \
+; RUN:   -r=%t2.o,test,plx \
+; RUN:   -r=%t2.o,_ZN1D1mEi,
+; RUN: llvm-dis %t3.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+; New PM, Index based WPD
+; RUN: llvm-lto2 run %t2.o -save-temps -use-new-pm -pass-remarks=. \
+; RUN:   -o %t3 \
+; RUN:   -r=%t2.o,test,plx \
+; RUN:   -r=%t2.o,_ZN1D1mEi,
+; RUN: llvm-dis %t3.1.4.opt.bc -o - | FileCheck %s --check-prefix=CHECK-IR
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-grtev4-linux-gnu"
+
+%struct.D = type { i32 (...)** }
+
+@_ZTV1D = internal constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.D*, i32)* @_ZN1D1mEi to i8*)] }, !type !3
+
+; CHECK-IR-LABEL: define weak_odr dso_local i32 @test
+define weak_odr i32 @test(%struct.D* %obj2, i32 %a) {
+entry:
+  %0 = bitcast %struct.D* %obj2 to i8***
+  %vtable2 = load i8**, i8*** %0
+  %1 = bitcast i8** %vtable2 to i8*
+  %p2 = call i1 @llvm.type.test(i8* %1, metadata !4)
+  call void @llvm.assume(i1 %p2)
+
+  %2 = bitcast i8** %vtable2 to i32 (%struct.D*, i32)**
+  %fptr33 = load i32 (%struct.D*, i32)*, i32 (%struct.D*, i32)** %2, align 8
+
+  ; Check that the call was not devirtualized.
+  ; CHECK-IR: %call4 = tail call i32 %fptr33
+  %call4 = tail call i32 %fptr33(%struct.D* nonnull %obj2, i32 0)
+  ret i32 %call4
+}
+; CHECK-IR-LABEL: ret i32
+; CHECK-IR-LABEL: }
+
+declare i1 @llvm.type.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+declare i32 @_ZN1D1mEi(%struct.D* %this, i32 %a)
+
+!3 = !{i64 16, !4}
+!4 = distinct !{}

tools/llvm-bcanalyzer/llvm-bcanalyzer.cpp

#define STRINGIFY_CODE(PREFIX, CODE)                                           \
   case bitc::FULL_LTO_GLOBALVAL_SUMMARY_BLOCK_ID:
     switch (CodeID) {
     default:
       return nullptr;
       STRINGIFY_CODE(FS, PERMODULE)
       STRINGIFY_CODE(FS, PERMODULE_PROFILE)
       STRINGIFY_CODE(FS, PERMODULE_RELBF)
       STRINGIFY_CODE(FS, PERMODULE_GLOBALVAR_INIT_REFS)
+      STRINGIFY_CODE(FS, PERMODULE_VTABLE_GLOBALVAR_INIT_REFS)
       STRINGIFY_CODE(FS, COMBINED)
       STRINGIFY_CODE(FS, COMBINED_PROFILE)
       STRINGIFY_CODE(FS, COMBINED_GLOBALVAR_INIT_REFS)
       STRINGIFY_CODE(FS, ALIAS)
       STRINGIFY_CODE(FS, COMBINED_ALIAS)
       STRINGIFY_CODE(FS, COMBINED_ORIGINAL_NAME)
       STRINGIFY_CODE(FS, VERSION)
       STRINGIFY_CODE(FS, FLAGS)
       STRINGIFY_CODE(FS, TYPE_TESTS)
       STRINGIFY_CODE(FS, TYPE_TEST_ASSUME_VCALLS)
       STRINGIFY_CODE(FS, TYPE_CHECKED_LOAD_VCALLS)
       STRINGIFY_CODE(FS, TYPE_TEST_ASSUME_CONST_VCALL)
       STRINGIFY_CODE(FS, TYPE_CHECKED_LOAD_CONST_VCALL)
       STRINGIFY_CODE(FS, VALUE_GUID)
       STRINGIFY_CODE(FS, CFI_FUNCTION_DEFS)
       STRINGIFY_CODE(FS, CFI_FUNCTION_DECLS)
       STRINGIFY_CODE(FS, TYPE_ID)
+      STRINGIFY_CODE(FS, TYPE_ID_METADATA)
     }
   case bitc::METADATA_ATTACHMENT_ID:
     switch(CodeID) {
     default:return nullptr;
       STRINGIFY_CODE(METADATA, ATTACHMENT)
     }
   case bitc::METADATA_BLOCK_ID:
     switch(CodeID) {

tools/llvm-lto2/llvm-lto2.cpp

static int run(int argc, char **argv) {
   for (std::string F : InputFilenames) {
     std::unique_ptr<MemoryBuffer> MB = check(MemoryBuffer::getFile(F), F);
     std::unique_ptr<InputFile> Input =
         check(InputFile::create(MB->getMemBufferRef()), F);
 
     std::vector<SymbolResolution> Res;
     for (const InputFile::Symbol &Sym : Input->symbols()) {
       auto I = CommandLineResolutions.find({F, Sym.getName()});
+      // If it isn't found, look for "$", which would have been added
+      // (followed by a hash) when the symbol was promoted during module
+      // splitting if it was defined in one part and used in the other.
+      // Try looking up the symbol name before the "$".
+      if (I == CommandLineResolutions.end()) {
+        auto SplitName = Sym.getName().rsplit("$");
+        I = CommandLineResolutions.find({F, SplitName.first});
+      }
       if (I == CommandLineResolutions.end()) {
         llvm::errs() << argv[0] << ": missing symbol resolution for " << F
                      << ',' << Sym.getName() << '\n';
         HasErrors = true;
       } else {
         Res.push_back(I->second.front());
         I->second.pop_front();
         if (I->second.empty())