[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

49

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/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 {};
   }
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, TypeIdCompatibleVtableInfo> &
   typeIdCompatibleVtableMap() const {
     return TypeIdCompatibleVtableMap;
   }
 
   /// Return an existing or new TypeIdCompatibleVtableMap entry for \p TypeId.
   /// This accessor can mutate the map and therefore should not be used in
   /// the ThinLTO backends.

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/LTO/LTO.cpp

 #include "llvm/Support/ThreadPool.h"
 #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/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
 #include "llvm/Transforms/Utils/SplitModule.h"
 
 #include <set>
 
 using namespace llvm;
 using namespace lto;
 using namespace object;
 
 #define DEBUG_TYPE "lto"
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/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 TypeIdCompatibleVtableInfo TIdInfo,
+                                 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 TypeIdCompatibleVtableInfo TIdInfo,
+    uint64_t ByteOffset) {
+  for (const TypeIdOffsetVtableInfo P : TIdInfo) {
+    // VTable initializer should have only one summary, or all copies must be
+    // linkonce/weak ODR.
+    assert(P.VTableVI.getSummaryList().size() == 1 ||
+           llvm::all_of(
+               P.VTableVI.getSummaryList(),
+               [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
+                 return GlobalValue::isLinkOnceODRLinkage(Summary->linkage()) ||
+                        GlobalValue::isWeakODRLinkage(Summary->linkage());
+               }));
+    const auto *VS = cast<GlobalVarSummary>(P.VTableVI.getSummaryList()[0].get());
+    if (!P.VTableVI.getSummaryList()[0]->isLive())
+      continue;
+    for (auto VTP : VS->vTableFuncs()) {
+      if (VTP.VTableOffset != P.AddressPointOffset + ByteOffset)
+        continue;
+
+      TargetsForSlot.push_back(VTP.FuncVI);
+    }
+  }
+
+  // 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.typeIdCompatibleVtableMap().empty())
+    return;
+
+  DenseMap<GlobalValue::GUID, std::vector<StringRef>> NameByGUID;
+  for (auto &P : ExportSummary.typeIdCompatibleVtableMap()) {
+    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.getTypeIdCompatibleVtableSummary(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/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 = linkonce_odr 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 linkonce_odr 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

 
 ; 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: [[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: typeidCompatibleVTable: (name: "_ZTS1A", summary: ((offset: 16, [[B]]), (offset: 16, [[C]])))
 ; NOENABLESPLITFLAG-DAG: typeidCompatibleVTable: (name: "_ZTS1B", summary: ((offset: 16, [[B]])))
 ; NOENABLESPLITFLAG-DAG: typeidCompatibleVTable: (name: "_ZTS1C", summary: ((offset: 16, [[C]])))
 ; Type Id on _ZTV1D should have been promoted
 ; NOENABLESPLITFLAG-DAG: typeidCompatibleVTable: (name: "1${{.*}}", summary: ((offset: 16, [[D]])))
 
-; TODO: Test index-based WPD one %t2.o once implemented.
+; 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
 ; FIXME: Fix machine verifier issues and remove -verify-machineinstrs=0. PR39436.
 ; RUN: llvm-lto2 run %t.o -save-temps -pass-remarks=. \
 ; RUN:   -verify-machineinstrs=0 \
 ; RUN:   -o %t3 \
 ; RUN:   -r=%t.o,test,px \
 ; RUN:   -r=%t.o,_ZN1A1nEi,p \
entry:
   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 @_ZN1B1fEi(%struct.B* %this, i32 %a)
-declare i32 @_ZN1A1nEi(%struct.A* %this, i32 %a)
-declare i32 @_ZN1C1fEi(%struct.C* %this, i32 %a)
-declare i32 @_ZN1D1mEi(%struct.D* %this, i32 %a)
+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/devirt3.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=typeidCompatibleVTable
+; 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=typeidCompatibleVTable
+; 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/devirt3.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: typeidCompatibleVTable: (name: "_ZTS1A", summary: ((offset: 16, [[B]]), (offset: 16, [[C]])))
+; NOENABLESPLITFLAG-DAG: typeidCompatibleVTable: (name: "_ZTS1B", summary: ((offset: 16, [[B]])))
+; NOENABLESPLITFLAG-DAG: typeidCompatibleVTable: (name: "_ZTS1C", summary: ((offset: 16, [[C]])))
+; NOENABLESPLITFLAG-DAG: typeidCompatibleVTable: (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,_ZN1D1mEi, \
+; 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,_ZN1D1mEi, \
+; 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: W _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,_ZN1D1mEi, \
+; 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,_ZTV1D, \
+; RUN:   -r=%t1.o,_ZN1D1mEi, \
+; RUN:   -r=%t1.o,_ZN1D1mEi, \
+; 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,_ZTV1D, \
+; RUN:   -r=%t1.o,_ZN1D1mEi, \
+; RUN:   -r=%t1.o,_ZN1D1mEi, \
+; 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: W _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: single-impl: devirtualized a call to _ZN1E1mEi
+; REMARK-DAG: 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*]
+@_ZTV1D = linkonce_odr constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* undef, i8* bitcast (i32 (%struct.D*, i32)* @_ZN1D1mEi to i8*)] }, !type !3
+
+define linkonce_odr i32 @_ZN1D1mEi(%struct.D* %this, i32 %a) #0 {
+   ret i32 0
+}
+
+; 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 @_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)
+
+attributes #0 = { noinline optnone }
+
+!3 = !{i64 16, !"_ZTS1D"}

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