[ThinLTO] Add summary entries for index-based WPD

[tejohnson]

Summary

If LTOUnit splitting is disabled, the module summary analysis computes
the summary information necessary to perform single implementation
devirtualization during the thin link with the index and no IR. The
information collected from the regular LTO IR in the current hybrid WPD
algorithm is summarized, including:

1. For vtable definitions, record the function pointers and their offset

within the vtable initializer (subsumes the information collected from
IR by tryFindVirtualCallTargets).

2. A record for each type metadata summarizing the vtable definitions

decorated with that metadata (subsumes the TypeIdentiferMap collected
from IR).

Also added are the necessary bitcode records, and the corresponding
assembly support.

The index-based WPD will be sent as a follow-on.

Depends on D53890.

[tejohnson]

Enable promotion of type ids in the non-split ThinLTO case and test it.

[tejohnson]

Update patch to reflect changes at head.

[davidxl]

A very high level meta question: can thinLink phase read symbol table from each module? If yes, why duplicate the symtab information into summary?

[tejohnson]

In D54815#1354816, @davidxl wrote:

A very high level meta question: can thinLink phase read symbol table from each module? If yes, why duplicate the symtab information into summary?

We do in fact require reading the IRSymtab along with the summary, e.g. the symbol strings are shared. What duplication are you concerned about? I don't think anything added in this patch would be available in the symbol table.

[davidxl]

Vtable funcs info should be in the initializers of vtable global variables right?

[tejohnson]

In D54815#1354850, @davidxl wrote:

Vtable funcs info should be in the initializers of vtable global variables right?

The IRSymtab doesn't hold the initializers of global variable symbols. It only holds the information necessary for LTO to provide information to the linkers to drive linker based symbol resolution.

As we discussed offline, one could imagine moving this information in the IRSymtab (it is currently in the IR MODULE_BLOCK), and then sharing with the summary, but this is a much bigger restructuring that would need to be considered separately. E.g. in the MODULE_BLOCK the global var prototype is in a different record than its definition initializer, and other than the string table there isn't any sharing between the info in the MODULE_BLOCK and the IRSymtab AFAIK. Before moving the initializer into the IRSymtab it would make sense to start by deduplicating other symbol information between the MODULE_BLOCK and the IRSymtab (I recall discussing this with @pcc at some point but don't recall what conclusion we came to). And then this would also require integration between the summary block and the IRSymtab which, again other than the string table, are separate entities without shared information or cross references.

One thing to note about this patch is that we already hold in the GLOBALVAR summary entry all the references to other symbols in its initializer (which are maintained as an array of essentially pointers to other summary index entries), however with the new FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS record, and as well in the in memory summary representation, we end up essentially duplicating those references for vtable defs. I could presumably come up with a way of consolidating those. I had convinced myself that there weren't enough vtable defs to warrant too much restructuring, but let me see if I can come up with a clean way to do this that doesn't bloat non-vtable globalvar summaries.

[tejohnson]

This was a mistaken commit, reverting!

[tejohnson]

Reverted in r351455.

[tejohnson]

Ping on review plus some numbers and a small improvement that I will upload shortly.

I did some measurements to see how much overhead we add to the bitcode files for an important internal app. The overhead from adding the new records is pretty minor. Most of the increase over current non-WPD ThinLTO bitcode sizes comes from the addition of the type test instructions and the type test metadata - this just comes from enabling the options to get those in the IR (independent of which type of WPD we do we'll need those). Comparing the current hybrid WPD bitcode with the new summarized WPD bitcode, the bitcode files are actually smaller with the index summarized type info compared to that with the current hybrid WPD. I believe this is due to the overhead of splitting the LTO unit into two modules. And the size of the minimized index-only bitcode we create just for the distributed thin link process in our build system is significantly smaller with the new approach - this goes back to my finding that we aren't able to split the LTO unit in many cases so we end up having to put all the IR for some of these files into the regular LTO partition.

All sizes below are in bytes. "minimized bitcode" means the additional index-only bitcode file for a distributed thin link emitted by clang with -fthin-link-bitcode (i.e. just contains symtab, summaries, strtab).

ThinLTO baseline (no LTO unit, no WPD):
aggregate bitcode size: 21464737248
aggregate minimized bitcode: 3251583939

ThinLTO hybrid WPD (current WPD implementation):
aggregate bitcode size: 22013358720 (2.6% bigger than baseline)
aggregate minimized bitcode: 7521978208 (1039% bigger than baseline)

ThinLTO index-only WPD (this patch):
aggregate bitcode size: 7521978208 (2.3% bigger than baseline, smaller than hybrid WPD)
aggregate minimized bitcode: 850885040 (28.6% bigger than baseline, much much smaller than current hybrid WPD)

Breaking down the increase in the "minimized bitcode" from this patch:

• 3% of increase is due to the additional VTable definition record fields (the vptr ref/offset pairs)
• 13% is due to the new Type ID metadata records (was about 14% before my latest tweak to make those more efficient that I will upload shortly)
• The remainder of the increase as I noted earlier is simply due to the additional IR from the type info (which is going to be there regardless of WPD scheme).

So I don't think it is necessary to gate this on removing any redundancies of the vtable summaries with the IR bitcode, the increase from that is pretty small. And

[tejohnson]

Use an abbrev id in the bitcode for the new TYPE_ID_METADATA records.
This makes them a bit more compact.

[tejohnson]

Two clarifications below:

In D54815#1372125, @tejohnson wrote:

Ping on review plus some numbers and a small improvement that I will upload shortly.

I did some measurements to see how much overhead we add to the bitcode files for an important internal app. The overhead from adding the new records is pretty minor. Most of the increase over current non-WPD ThinLTO bitcode sizes comes from the addition of the type test instructions and the type test metadata - this just comes from enabling the options to get those in the IR (independent of which type of WPD we do we'll need those). Comparing the current hybrid WPD bitcode with the new summarized WPD bitcode, the bitcode files are actually smaller with the index summarized type info compared to that with the current hybrid WPD. I believe this is due to the overhead of splitting the LTO unit into two modules. And the size of the minimized index-only bitcode we create just for the distributed thin link process in our build system is significantly smaller with the new approach - this goes back to my finding that we aren't able to split the LTO unit in many cases so we end up having to put all the IR for some of these files into the regular LTO partition.

All sizes below are in bytes. "minimized bitcode" means the additional index-only bitcode file for a distributed thin link emitted by clang with -fthin-link-bitcode (i.e. just contains symtab, summaries, strtab).

The minimized bitcode also contains anything that needs to be compiled in the regular LTO partition. Which for the hybrid WPD means all the vtables, plus all the IR in the case when we cannot split it but have vtable defs (which is why there is such a huge increase in that for the hybrid WPD below).

ThinLTO baseline (no LTO unit, no WPD):
aggregate bitcode size: 21464737248
aggregate minimized bitcode: 3251583939

ThinLTO hybrid WPD (current WPD implementation):
aggregate bitcode size: 22013358720 (2.6% bigger than baseline)
aggregate minimized bitcode: 7521978208 (1039% bigger than baseline)

ThinLTO index-only WPD (this patch):
aggregate bitcode size: 7521978208 (2.3% bigger than baseline, smaller than hybrid WPD)
aggregate minimized bitcode: 850885040 (28.6% bigger than baseline, much much smaller than current hybrid WPD)

Breaking down the increase in the "minimized bitcode" from this patch:

• 3% of increase is due to the additional VTable definition record fields (the vptr ref/offset pairs)
• 13% is due to the new Type ID metadata records (was about 14% before my latest tweak to make those more efficient that I will upload shortly)
• The remainder of the increase as I noted earlier is simply due to the additional IR from the type info (which is going to be there regardless of WPD scheme).

For the minimized bitcode the increased IR shows up because the symtab and strtab are much larger.

So I don't think it is necessary to gate this on removing any redundancies of the vtable summaries with the IR bitcode, the increase from that is pretty small. And

[davidxl]

Thanks for the data. It is certainly a great improvement over the hybrid WPD.

[tejohnson]

Restore a couple of new tests that were lost when I updated the patch last.

[tejohnson]

Ping

[davidxl]

include/llvm/Bitcode/LLVMBitCodes.h

271

It is a little difficult to parse the comment here. Is it just mapping from type id to global value id of the vtable? Also what is 'vtable definition decorated with a type metadata?'

include/llvm/IR/ModuleSummaryIndex.h

818

Perhaps add that this is a mapping from type (id) to vtable info?

821

Why is it a one-to-many mapping?

841

TypeIdMetadataMap -- the name sounds too generic. Is it possible to rename it to carry more semantics?

1214

Returns an ArrayRef?

[tejohnson]

include/llvm/Bitcode/LLVMBitCodes.h

271

This is summarizing the type metadata described here:
https://llvm.org/docs/TypeMetadata.html

Each vtable def can be decorated with multiple type metadata that it is compatible with (due to inheritance). See the example below in test/Assembler/thinlto-vtable-summary.ll. E.g. B and C each derived from A so they each have 2 type metadata attachments. Therefore the typeIdMetadata summary for A includes both vtables.

I will try to add a more intuitive explanation, and point to the doc.

include/llvm/IR/ModuleSummaryIndex.h

818

This one does not include the type id, it is the vtable def's ValueInfo and the byte offset from one of its attached type metadata (the offset is the offset into the vtable of the address point for that type as defined in the Itanium ABI: https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general). The attached type metadata for a given vtable def are all the the types it is compatible with. It's a little hard to explain, the example in https://llvm.org/docs/TypeMetadata.html helps illustrate this. I can try to clarify and point to that doc.

821

Because each type id may be compatible with multiple vtables, due to inheritance.

841

Maybe TypeIdCompatibleVtableMap?

1214

Yeah I can change this.

[tejohnson]

Address review comments

[tejohnson]

@pcc - do you have any comments on this patch or are you ok with @davidxl completing the review?

I've done some renaming to try to make the types and variable names more intuitive. I've also added in explanations of the type metadata with pointers to the documentation in several places.

[pcc]

include/llvm/IR/ModuleSummaryIndex.h

670

Instead of declaring this and TypeIdOffsetVtablePair as a pair, would it be better to declare them as structs with appropriately named fields? Seems like it would make the usage code easier to understand.

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

447

No else after return

[tejohnson]

Implement review suggestions

[tejohnson]

ping - @pcc any more comments?

[pcc]

LGTM

lib/AsmParser/LLParser.cpp

826

Redundant break

[tejohnson]

Address review comment, and update test for recent auto hide summary changes

[Prazek]

llvm/include/llvm/IR/ModuleSummaryIndex.h

896 ↗

(On Diff #207606)

Do we care about the alphabetical order in this mapping?
If not, the map can be changed to std::unordered_map (or other llvm-specific string map), which should be faster and more memory efficient.

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

3691 ↗

(On Diff #207606)

Isn't this line redundant?

3857 ↗

(On Diff #207606)

Isn't this line redundant?

[tejohnson]

llvm/include/llvm/IR/ModuleSummaryIndex.h

896 ↗

(On Diff #207606)

We care about consistent ordering, as the iteration order will affect the order of the summary entries emitted into the bitcode. So unordered_map is not appropriate here. Ditto for StringMap.

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

3691 ↗

(On Diff #207606)

yep, will fix.

3857 ↗

(On Diff #207606)

yep will fix.

[Prazek]

llvm/include/llvm/IR/ModuleSummaryIndex.h

896 ↗

(On Diff #207606)

That's what I thought, sorry for late review and thanks for fixing other nits :)

[tejohnson]

llvm/include/llvm/IR/ModuleSummaryIndex.h

896 ↗

(On Diff #207606)

No prob, thanks for the comments. Committed fixes in r364968

[ychen]

Would be nice if this has a subsection in ThinLTO Summary in the Langref.

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

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;
   }
 
+  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(

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/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

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