Use branch funnels for virtual calls when retpoline mitigation is enabled.

[pcc]

Summary

The retpoline mitigation for variant 2 of CVE-2017-5715 inhibits the
branch predictor, and as a result it can lead to a measurable loss of
performance. We can reduce the performance impact of retpolined virtual
calls by replacing them with a special construct known as a branch
funnel, which is an instruction sequence that implements virtual calls
to a set of known targets using a binary tree of direct branches. This
allows the processor to speculately execute valid implementations of the
virtual function without allowing for speculative execution of of calls
to arbitrary addresses.

This patch extends the whole-program devirtualization pass to replace
certain virtual calls with calls to branch funnels, which are
represented using a new llvm.icall.jumptable intrinsic. It also extends
the LowerTypeTests pass to recognize the new intrinsic, generate code
for the branch funnels (x86_64 only for now) and lay out virtual tables
as required for each branch funnel.

The implementation supports full LTO as well as ThinLTO, and extends the
ThinLTO summary format used for whole-program devirtualization to
support branch funnels.

For more details see RFC:
http://lists.llvm.org/pipermail/llvm-dev/2018-January/120672.html

[chandlerc]

llvm/include/llvm/IR/Intrinsics.td

877

A jump table usually refers to an *indirect* jump using a table of addresses...

Maybe "search tree" or "branch funnel" or some other term would be more clear here and elsewhere?

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

Emitting all of this with (I assume) inline assembly seems like a really messy design. It makes all of this entirely x86-specific, but *this* part is completely independent of architecture.

Why not emit LLVM IR? Is there no pattern of IR that actually lowers to reasonable branches? I find that a little bit surprising, but maybe we should just fix the lowering in that case?

[pcc]

llvm/include/llvm/IR/Intrinsics.td

877

Yes, I'm a little inconsistent in the terminology in this patch. I'll go through the patch and try to consistently use "branch funnel".

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

The main reason is that we need to make sure that whatever code we generate conforms with the calling convention used for the virtual call. At this point there is no guarantee that we have correct information about the calling convention to be used here because the "source of truth" for the calling convention is the call site itself, and with ThinLTO there may not be a call site in the current module. We cannot even rely on the function prototype with ThinLTO because we may have discarded the prototype by this point. Furthermore there doesn't seem to be a point in preserving the calling convention because no matter what it is, we will always want the same code. That is what led me to the conclusion that what we need here is an IR construct that represents the notion of a branch funnel call to a function with an unknown prototype -- that is what the llvm.icall.jumptable intrinsic is.

I considered putting the implementation of this intrinsic in the backend like a regular intrinsic, but one of the problems with that is that one of the things that we need to be able to do is stitch together multiple global variables into a single global in order to implement the branch funnel as a binary search, and it is too late to do that in the backend. The LowerTypeTests pass was a convenient place to do it (since it already needs to know how to do it in order to implement llvm.type.test) but admittedly it may not be the best place. It occurred to me that it may be possible to implement the stitching together of globals in a pre-isel pass and the rest of llvm.icall.jumptable in the backend, but I think that's something that's best considered for a followup patch since it may have implications for how we implement llvm.type.test as well.

[chandlerc]

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

The more I think about this the more I think that implementing this with inline asm is just the wrong design.

I understand the challenges you're hitting here, but I think we should solve them by lowering in the backend, not in the IR. The IR really can't model the kinds of things you're doing (and it shouldn't!).

My suggestion would be to change the llvm.icall.<mumble> intrinsic or add a during-lowering intrinsic that lets you prepare the global variable stuff as necessary in the IR pass, and hand that prepared information cleanly (and abstractly) to the backend where you can effectively lower it to branch instructions. Since you are (notionally) lowering a call, you may even be able to use the intrinsic all the way into the code generator and just lower this manually with an MI pass.

Another aspect that this will improve is that you shouldn't need to embed things into naked functions at all. This should be something that you can just expand wherever it is needed into the code.

[pcc]

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

I'm not sure that I understand your proposal. Are you proposing that in the WholeProgramDevirt pass we would transform each virtual call site into an intrinsic call with the list of possible targets, and then in the backend we would lower the intrinsic call into a call to a branch funnel "function" together with its definition?

[chandlerc]

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

I'm imagining in the backend, we would lower the intrinsic call into an *inline* branch funnel across the destinations.

(I can also imagine using a pseudo instead of call to an intrinsic, but as you want to capture a call with some specific calling convention / signature / etc, using a call to an intrinsic seems a reasonable representation... if needed, you could even put the potential destinations into an operand bundle so that the formal argument list *is* actually the argument list which should be used for calling the target function.)

[pcc]

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

Are you sure you want an inline branch funnel? It will make the code more "branchy", which doesn't seem great for code size.

i.e. the two options are

call branchfunnel

branchfunnel:
cmp ...
jb target1
je target2
jmp target3

and

cmp ...
jb .Ltmp1
je .Ltmp2
call target3
jmp .Ltmp3
.Ltmp1:
call target1
jmp .Ltmp3
.Ltmp2:
call target2
.Ltmp3:

.

Putting that aside, there are problems with the idea of putting the list of targets in every intrinsic. Most importantly, it complicates matters significantly for ThinLTO. It means that each backend job would need to know the list of targets as well as the layout of the combined global that stores the vtables. We don't need that for any other purpose, so we would need to include that information in the summary just to support this. Because we are including the information in the summary, it means that any change to the class hierarchy would cause a ThinLTO cache miss. (Right now, in many cases, we can avoid a cache miss as a result of careful summary design.) In other words, this proposal would be making the code more complicated and less efficient. So it doesn't seem like a good direction to me.

I think we can both agree that lowering to inline asm isn't great. But I see a different way for this code to evolve so that it is properly layered. Essentially we would invent a new top-level entity (like a function or a global variable) that represents a thunk. There is already a need for such a top-level entity to represent CFI jump tables (currently we represent them in the same hackish way using inline asm), so to start with there would be two kinds of thunks: jump tables and branch funnels. Target specific code in the backend would lower the thunks to MI or MCInstrs.

This would have a few advantages which would be shared with your intrinsic proposal:

• the IR would be somewhat platform independent until the backend,
• thus it can be easily optimized by midlevel passes,
• the backend would be able to choose whether to emit the branch funnel inline or outline,

and most importantly for ThinLTO:

• it would support separate compilation.

Please let me know what you think.

[chandlerc]

Sorry for the delay, took me a bit to internalize what you were proposing.

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

Having separate inline branch funnels may actually be nice when there are very few targets as they may be better predicted. There is a size/speed trade-off here.

However, the separate compilation issue is very compelling. I think you can use an intrinsic to implement your proposal and get the advantages you describe without any new top-level construct:

You could define / declare a thunk IR function which contains just this intrinsic. Only one TU gets the definition which calls the intrinsic and needs the global information. The others just get a declaration. No new top-level construct, and you lower it exactly as you describe.

I'm not sure if this will directly map to the jump table case, but I'm happy for that to be dealt with in a follow-up as that is already in tree.

If this idea doesn't work, let's chat about what alternatives would work or how to model the top-level entity. I feel pretty strongly that the current code with the current amount of inline assembly is really not up to the quality that should go into the tree even as a temporary thing. There doesn't seem to be such urgency here that we can't take the time to engineer this the right way.

Also:

1. We didn't actually clean up the inline asm for the CFI jump tables despite those being in-tree for a long time, so I think it is reasonable to insist we don't make things worse.
2. This is a *much* more significant usage of inline asm, and so it seems much less reasonable as a temporary solution.

[pcc]

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

You could define / declare a thunk IR function which contains just this intrinsic. Only one TU gets the definition which calls the intrinsic and needs the global information. The others just get a declaration. No new top-level construct, and you lower it exactly as you describe.

The problem with that is: what would be the signature/calling convention of that function? That is the problem that I described on the first comment on this thread.

If this idea doesn't work, let's chat about what alternatives would work or how to model the top-level entity. I feel pretty strongly that the current code with the current amount of inline assembly is really not up to the quality that should go into the tree even as a temporary thing. There doesn't seem to be such urgency here that we can't take the time to engineer this the right way.

Also:

1. We didn't actually clean up the inline asm for the CFI jump tables despite those being in-tree for a long time, so I think it is reasonable to insist we don't make things worse.
2. This is a *much* more significant usage of inline asm, and so it seems much less reasonable as a temporary solution.

Okay, fair enough. Assuming that you agree with my objection above, I will try to sketch out a more detailed plan for how I think the new top-level entity should look in the IR.

[echristo]

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

I think you could count it as a naked function yes? I don't see a reason for a top level "thunk" entity in the IR necessarily.

[pcc]

• First draft of MI-based lowering -- tests to come

[pcc]

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

1106–1108

The main issue was that the thunk needs to be calling-convention-independent, which I thought was unrepresentable in IR, but it turns out that we can base it on a representation which is apparently used for thunks on Windows. That representation is to mark the thunk as varargs and mark the call as musttail. That is what this patch implements.

[pcc]

@chandlerc ping -- let me know whether this MI-based implementation seems reasonable to you.

[chandlerc]

In D42453#1021513, @pcc wrote:

@chandlerc ping -- let me know whether this MI-based implementation seems reasonable to you.

Thanks for the ping, I missed this while on vacation last week. Will have feedback shortly....

[chandlerc]

I've not looked at all of the stuff yet, but focusing on the MI and lowering, yeah, this looks exactly like the direction I was imagining. Do you want me to go ahead and do a full review, or do you have other cleanups you need to make first? Were there any problems you ran into with this approach (other than the need to wire everything up here) that still need to be sorted out or that I can help with?

[pcc]

The code is ready for review, but the tests still need to be updated. Up to you whether you'd like to take a look now or wait for the tests.

[chandlerc]

Did a pass over the code. Really only minor nits and naming questions. Generally, the structure and such makes a lot of sense to me now. Thanks so much for working on threading this through all the layers so nicely!

Happy to take another look when you get tests and such updated.

llvm/include/llvm/IR/ModuleSummaryIndex.h

589–590

Is it really a jump table though? You use this term throughout, so only commenting here, but I wonder if there is a better term that makes it more clear what is going on here. I'm worried people will assume this is actually implemented with a jump table as opposed to a branch funnel (or binary-ish search).

llvm/include/llvm/Target/Target.td

1146 ↗

(On Diff #135173)

Does it make sense to put a comment string here to make reading the dump of MI easier? (I'm not sure, genuine question here.)

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

6049 ↗

(On Diff #135173)

SmallVector? Seems likely to have lots of cases where 8 or 16 would handle..

6064 ↗

(On Diff #135173)

Same question here.

6070–6071 ↗

(On Diff #135173)

Is it worth teaching the verifier about this and the other invariants below? Could then make this just an assert. Minor point though, and would be fine as a follow-up.

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

296

nit: I would have capitalized Icall as ICall throughout.

[pcc]

• Update tests and fix a couple of benign bugs in the code
• SmallVector
• Renaming

[pcc]

llvm/include/llvm/IR/ModuleSummaryIndex.h

589–590

Sorry, that was one of the things that I forgot to update in the code. Renamed to "branch funnel".

llvm/include/llvm/Target/Target.td

1146 ↗

(On Diff #135173)

No, the MI dump already says "ICALL_BRANCH_FUNNEL". This string is used in the asm output for instructions that survive until MC, and this one doesn't.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

6070–6071 ↗

(On Diff #135173)

This particular check can't be a verifier check because the wholeprogramdevirt pass creates IR that would not pass this check (it is later fixed up by lowertypetests). The others would be fine as verifier checks and we might do that as a followup.

[chandlerc]

This looks really, really nice. Thanks for all the hard work here!

llvm/include/llvm/Target/Target.td

1146 ↗

(On Diff #135173)

Ah, nice. Thanks for checking!

compiler-rt/test/cfi/simple-pass.cpp

 // RUN: %clangxx_cfi -o %t %s
 // RUN: %run %t
+// RUN: %clangxx_cfi -mretpoline -o %t2 %s
+// RUN: %run %t2
 
 // Tests that the CFI mechanism does not crash the program when making various
 // kinds of valid calls involving classes with various different linkages and
 // types of inheritance, and both virtual and non-virtual member functions.
 
 #include "utils.h"
 
 struct A {

llvm/include/llvm/ADT/PointerUnion.h

struct PointerLikeTypeTraits<PointerUnion3<PT1, PT2, PT3>> {
 
   // The number of bits available are the min of the two pointer types.
   enum {
     NumLowBitsAvailable = PointerLikeTypeTraits<
         typename PointerUnion3<PT1, PT2, PT3>::ValTy>::NumLowBitsAvailable
   };
 };
 
+template <typename PT1, typename PT2, typename PT3>
+bool operator<(PointerUnion3<PT1, PT2, PT3> lhs,
+               PointerUnion3<PT1, PT2, PT3> rhs) {
+  return lhs.getOpaqueValue() < rhs.getOpaqueValue();
+}
+
 /// A pointer union of four pointer types. See documentation for PointerUnion
 /// for usage.
 template <typename PT1, typename PT2, typename PT3, typename PT4>
 class PointerUnion4 {
 public:
   using InnerUnion1 = PointerUnion<PT1, PT2>;
   using InnerUnion2 = PointerUnion<PT3, PT4>;
   using ValTy = PointerUnion<InnerUnion1, InnerUnion2>;

llvm/include/llvm/IR/Intrinsics.td

 def int_type_test : Intrinsic<[llvm_i1_ty], [llvm_ptr_ty, llvm_metadata_ty],
                               [IntrNoMem]>;
 
 // Safely loads a function pointer from a virtual table pointer using type metadata.
 def int_type_checked_load : Intrinsic<[llvm_ptr_ty, llvm_i1_ty],
                                       [llvm_ptr_ty, llvm_i32_ty, llvm_metadata_ty],
                                       [IntrNoMem]>;
 
+// Create a binary search jump table that implements an indirect call to a
+// limited set of callees. This expands to inline asm that implements the jump
+// table, so it needs to be the only instruction in a naked function.
+def int_icall_jumptable : Intrinsic<[], [llvm_vararg_ty], []>;
+
 def int_load_relative: Intrinsic<[llvm_ptr_ty], [llvm_ptr_ty, llvm_anyint_ty],
                                  [IntrReadMem, IntrArgMemOnly]>;
 
 // Xray intrinsics
 //===----------------------------------------------------------------------===//
 // Custom event logging for x-ray.
 // Takes a pointer to a string and the length of the string.
 def int_xray_customevent : Intrinsic<[], [llvm_ptr_ty, llvm_i32_ty],

llvm/include/llvm/IR/ModuleSummaryIndex.h

struct TypeTestResolution {
   uint8_t BitMask = 0;
   uint64_t InlineBits = 0;
 };
 
 struct WholeProgramDevirtResolution {
   enum Kind {
     Indir,      ///< Just do a regular virtual call
     SingleImpl, ///< Single implementation devirtualization
+    JumpTable,  ///< When retpoline mitigation is enabled, use a jump table that
+                ///< is defined in the merged module. Otherwise same as Indir.
   } TheKind = Indir;
 
   std::string SingleImplName;
 
   struct ByArg {
     enum Kind {
       Indir,            ///< Just do a regular virtual call
       UniformRetVal,    ///< Uniform return value optimization

llvm/include/llvm/IR/ModuleSummaryIndexYAML.h

static void output(
     }
   }
 };
 
 template <> struct ScalarEnumerationTraits<WholeProgramDevirtResolution::Kind> {
   static void enumeration(IO &io, WholeProgramDevirtResolution::Kind &value) {
     io.enumCase(value, "Indir", WholeProgramDevirtResolution::Indir);
     io.enumCase(value, "SingleImpl", WholeProgramDevirtResolution::SingleImpl);
+    io.enumCase(value, "JumpTable", WholeProgramDevirtResolution::JumpTable);
   }
 };
 
 template <> struct MappingTraits<WholeProgramDevirtResolution> {
   static void mapping(IO &io, WholeProgramDevirtResolution &res) {
     io.mapOptional("Kind", res.TheKind);
     io.mapOptional("SingleImplName", res.SingleImplName);
     io.mapOptional("ResByArg", res.ResByArg);

llvm/lib/Transforms/IPO/LowerTypeTests.cpp

 //===- LowerTypeTests.cpp - type metadata lowering pass -------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This pass lowers type metadata and calls to the llvm.type.test intrinsic.
+// This pass lowers type metadata and calls to the llvm.type.test and
+// llvm.icall.jumptable intrinsic.
 // See http://llvm.org/docs/TypeMetadata.html for more information.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/LowerTypeTests.h"
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Analysis/TypeMetadataUtils.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalAlias.h"
bool isExported() const {
     return IsExported;
   }
 
   ArrayRef<MDNode *> types() const {
     return makeArrayRef(getTrailingObjects<MDNode *>(), NTypes);
   }
 };
 
+struct IcallJumptableTarget {
+  GlobalTypeMember *GTM;
+  uint64_t Offset;
+  Constant *Callee;
+};
+
+struct IcallJumptable final
+    : TrailingObjects<IcallJumptable, IcallJumptableTarget> {
+  static IcallJumptable *create(BumpPtrAllocator &Alloc, CallInst *CI,
+                                ArrayRef<IcallJumptableTarget> Targets) {
+    auto *Call = static_cast<IcallJumptable *>(
+        Alloc.Allocate(totalSizeToAlloc<IcallJumptableTarget>(Targets.size()),
+                       alignof(IcallJumptable)));
+    Call->CI = CI;
+    Call->NTargets = Targets.size();
+    std::uninitialized_copy(Targets.begin(), Targets.end(),
+                            Call->getTrailingObjects<IcallJumptableTarget>());
+    return Call;
+  }
+
+  CallInst *CI;
+  ArrayRef<IcallJumptableTarget> targets() const {
+    return makeArrayRef(getTrailingObjects<IcallJumptableTarget>(), NTargets);
+  }
+
+private:
+  size_t NTargets;
+};
+
 class LowerTypeTestsModule {
   Module &M;
 
   ModuleSummaryIndex *ExportSummary;
   const ModuleSummaryIndex *ImportSummary;
 
   Triple::ArchType Arch;
   Triple::OSType OS;
class LowerTypeTestsModule {
   void allocateByteArrays();
   Value *createBitSetTest(IRBuilder<> &B, const TypeIdLowering &TIL,
                           Value *BitOffset);
   void lowerTypeTestCalls(
       ArrayRef<Metadata *> TypeIds, Constant *CombinedGlobalAddr,
       const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
   Value *lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
                            const TypeIdLowering &TIL);
-  void buildBitSetsFromGlobalVariables(ArrayRef<Metadata *> TypeIds,
-                                       ArrayRef<GlobalTypeMember *> Globals);
+
+  void emitTernaryJumptable(Constant *CombinedGlobalAddr,
+                            ArrayRef<IcallJumptableTarget> Targets,
+                            raw_ostream &AsmOS, std::vector<Value *> &Args,
+                            uint64_t &LabelNo);
+  void lowerIcallJumptableCalls(
+      ArrayRef<IcallJumptable *> IcallJumptables,
+      Constant *CombinedGlobalAddr,
+      const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout);
+
+  void buildBitSetsFromGlobalVariables(
+      ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals,
+      ArrayRef<IcallJumptable *> IcallJumptables);
   unsigned getJumpTableEntrySize();
   Type *getJumpTableEntryType();
   void createJumpTableEntry(raw_ostream &AsmOS, raw_ostream &ConstraintOS,
                             Triple::ArchType JumpTableArch,
                             SmallVectorImpl<Value *> &AsmArgs, Function *Dest);
   void verifyTypeMDNode(GlobalObject *GO, MDNode *Type);
-  void buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
-                                 ArrayRef<GlobalTypeMember *> Functions);
-  void buildBitSetsFromFunctionsNative(ArrayRef<Metadata *> TypeIds,
-                                    ArrayRef<GlobalTypeMember *> Functions);
+  void
+  buildBitSetsFromFunctions(ArrayRef<Metadata *> TypeIds,
+                            ArrayRef<GlobalTypeMember *> Functions,
+                            ArrayRef<IcallJumptable *> IcallJumptables);
+  void buildBitSetsFromFunctionsNative(
+      ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions,
+      ArrayRef<IcallJumptable *> IcallJumptables);
   void buildBitSetsFromFunctionsWASM(ArrayRef<Metadata *> TypeIds,
                                      ArrayRef<GlobalTypeMember *> Functions);
-  void buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
-                                   ArrayRef<GlobalTypeMember *> Globals);
+  void
+  buildBitSetsFromDisjointSet(ArrayRef<Metadata *> TypeIds,
+                              ArrayRef<GlobalTypeMember *> Globals,
+                              ArrayRef<IcallJumptable *> IcallJumptables);
 
   void replaceWeakDeclarationWithJumpTablePtr(Function *F, Constant *JT);
   void moveInitializerToModuleConstructor(GlobalVariable *GV);
   void findGlobalVariableUsersOf(Constant *C,
                                  SmallSetVector<GlobalVariable *, 8> &Out);
 
   void createJumpTable(Function *F, ArrayRef<GlobalTypeMember *> Functions);
 
Value *LowerTypeTestsModule::lowerTypeTestCall(Metadata *TypeId, CallInst *CI,
   P->addIncoming(ConstantInt::get(Int1Ty, 0), InitialBB);
   P->addIncoming(Bit, ThenB.GetInsertBlock());
   return P;
 }
 
 /// Given a disjoint set of type identifiers and globals, lay out the globals,
 /// build the bit sets and lower the llvm.type.test calls.
 void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
-    ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) {
+    ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals,
+    ArrayRef<IcallJumptable *> IcallJumptables) {
   // Build a new global with the combined contents of the referenced globals.
   // This global is a struct whose even-indexed elements contain the original
   // contents of the referenced globals and whose odd-indexed elements contain
   // any padding required to align the next element to the next power of 2.
   std::vector<Constant *> GlobalInits;
   const DataLayout &DL = M.getDataLayout();
   for (GlobalTypeMember *G : Globals) {
     GlobalVariable *GV = cast<GlobalVariable>(G->getGlobal());
void LowerTypeTestsModule::buildBitSetsFromGlobalVariables(
 
   // Compute the offsets of the original globals within the new global.
   DenseMap<GlobalTypeMember *, uint64_t> GlobalLayout;
   for (unsigned I = 0; I != Globals.size(); ++I)
     // Multiply by 2 to account for padding elements.
     GlobalLayout[Globals[I]] = CombinedGlobalLayout->getElementOffset(I * 2);
 
   lowerTypeTestCalls(TypeIds, CombinedGlobal, GlobalLayout);
+  lowerIcallJumptableCalls(IcallJumptables, CombinedGlobal, GlobalLayout);
 
   // Build aliases pointing to offsets into the combined global for each
   // global from which we built the combined global, and replace references
   // to the original globals with references to the aliases.
   for (unsigned I = 0; I != Globals.size(); ++I) {
     GlobalVariable *GV = cast<GlobalVariable>(Globals[I]->getGlobal());
 
     // Multiply by 2 to account for padding elements.
for (CallInst *CI : TIUI.CallSites) {
       ++NumTypeTestCallsLowered;
       Value *Lowered = lowerTypeTestCall(TypeId, CI, TIL);
       CI->replaceAllUsesWith(Lowered);
       CI->eraseFromParent();
     }
   }
 }
 
+void LowerTypeTestsModule::emitTernaryJumptable(
+    Constant *CombinedGlobalAddr, ArrayRef<IcallJumptableTarget> Targets,
+    raw_ostream &AsmOS, std::vector<Value *> &Args, uint64_t &LabelNo) {
+  assert(!Targets.empty());
+
+  auto AdjR11 = [&](const IcallJumptableTarget &T) {
+    AsmOS << "leaq ${" << Args.size() << ":c}+" << T.Offset
+          << "(%rip), %r11\n";
+    Args.push_back(CombinedGlobalAddr);
+  };
+
+  if (Targets.size() == 1) {
+    AsmOS << "jmp ${" << Args.size() << ":c}@plt\n";
+    Args.push_back(Targets[0].Callee);
+    return;
+  }
+
+  if (Targets.size() == 2) {
+    AdjR11(Targets[1]);
+    AsmOS << "cmp %r11, %r10\n";
+    AsmOS << "jb ${" << Args.size() << ":c}@plt\n";
+    Args.push_back(Targets[0].Callee);
+    AsmOS << "jmp ${" << Args.size() << ":c}@plt\n";
+    Args.push_back(Targets[1].Callee);
+    return;
+  }
+
+  if (Targets.size() < 6) {
+    AdjR11(Targets[1]);
+    AsmOS << "cmp %r11, %r10\n";
+    AsmOS << "jb ${" << Args.size() << ":c}@plt\n";
+    Args.push_back(Targets[0].Callee);
+    AsmOS << "je ${" << Args.size() << ":c}@plt\n";
+    Args.push_back(Targets[1].Callee);
+    emitTernaryJumptable(CombinedGlobalAddr, Targets.slice(2),
+                         AsmOS, Args, LabelNo);
+    return;
+  }
+
+  uint64_t L = LabelNo++;
+  AdjR11(Targets[Targets.size() / 2]);
+  AsmOS << "cmp %r11, %r10\n";
+  AsmOS << "jb " << L << "f\n";
+  AsmOS << "je ${" << Args.size() << ":c}@plt\n";
+  Args.push_back(Targets[Targets.size() / 2].Callee);
+  emitTernaryJumptable(CombinedGlobalAddr,
+                       Targets.slice(Targets.size() / 2 + 1), AsmOS, Args,
+                       LabelNo);
+
+  AsmOS << L << ":\n";
+  emitTernaryJumptable(CombinedGlobalAddr, Targets.slice(0, Targets.size() / 2),
+                       AsmOS, Args, LabelNo);
+}
+
+void LowerTypeTestsModule::lowerIcallJumptableCalls(
+    ArrayRef<IcallJumptable *> IcallJumptables,
+    Constant *CombinedGlobalAddr,
+    const DenseMap<GlobalTypeMember *, uint64_t> &GlobalLayout) {
+  for (auto *JT : IcallJumptables) {
+    std::vector<IcallJumptableTarget> Targets = JT->targets();
+
+    // Adjust the offsets to be relative to the CombinedGlobalAddr.
+    for (auto &T : Targets) {
+      auto I = GlobalLayout.find(T.GTM);
+      assert(I != GlobalLayout.end());
+      T.Offset += I->second;
+    }
+    std::sort(
+        Targets.begin(), Targets.end(),
+        [](const IcallJumptableTarget &T1, const IcallJumptableTarget &T2) {
+          return T1.Offset < T2.Offset;
+        });
+
+    std::string Asm;
+    raw_string_ostream AsmOS(Asm);
+    std::vector<Value *> Args;
+    uint64_t LabelNo = 0;
+    emitTernaryJumptable(CombinedGlobalAddr, Targets, AsmOS, Args, LabelNo);
+
+    std::string Constraints;
+    if (!Args.empty()) {
+      Constraints = "s";
+      for (unsigned I = 1; I != Args.size(); ++I)
+        Constraints += ",s";
+    }
+
+    SmallVector<Type *, 16> ArgTypes;
+    ArgTypes.reserve(Args.size());
+    for (const auto &Arg : Args)
+      ArgTypes.push_back(Arg->getType());
+
+    InlineAsm *JumpTableAsm =
+        InlineAsm::get(FunctionType::get(Type::getVoidTy(M.getContext()), ArgTypes, false),
+                       AsmOS.str(), Constraints,
+                       /*hasSideEffects=*/true);
+    CallInst::Create(JumpTableAsm, Args, "", JT->CI);
+
+    JT->CI->eraseFromParent();
+  }
+}
+
 void LowerTypeTestsModule::verifyTypeMDNode(GlobalObject *GO, MDNode *Type) {
   if (Type->getNumOperands() != 2)
     report_fatal_error("All operands of type metadata must have 2 elements");
 
   if (GO->isThreadLocal())
     report_fatal_error("Bit set element may not be thread-local");
   if (isa<GlobalVariable>(GO) && GO->hasSection())
     report_fatal_error(

 
 Type *LowerTypeTestsModule::getJumpTableEntryType() {
   return ArrayType::get(Int8Ty, getJumpTableEntrySize());
 }
 
 /// Given a disjoint set of type identifiers and functions, build the bit sets
 /// and lower the llvm.type.test calls, architecture dependently.
 void LowerTypeTestsModule::buildBitSetsFromFunctions(
-    ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
+    ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions,
+    ArrayRef<IcallJumptable *> IcallJumptables) {
   if (Arch == Triple::x86 || Arch == Triple::x86_64 || Arch == Triple::arm ||
       Arch == Triple::thumb || Arch == Triple::aarch64)
-    buildBitSetsFromFunctionsNative(TypeIds, Functions);
+    buildBitSetsFromFunctionsNative(TypeIds, Functions, IcallJumptables);
   else if (Arch == Triple::wasm32 || Arch == Triple::wasm64)
     buildBitSetsFromFunctionsWASM(TypeIds, Functions);
   else
     report_fatal_error("Unsupported architecture for jump tables");
 }
 
 void LowerTypeTestsModule::moveInitializerToModuleConstructor(
     GlobalVariable *GV) {
void LowerTypeTestsModule::createJumpTable(
 
   IRB.CreateCall(JumpTableAsm, AsmArgs);
   IRB.CreateUnreachable();
 }
 
 /// Given a disjoint set of type identifiers and functions, build a jump table
 /// for the functions, build the bit sets and lower the llvm.type.test calls.
 void LowerTypeTestsModule::buildBitSetsFromFunctionsNative(
-    ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions) {
+    ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Functions,
+    ArrayRef<IcallJumptable *> IcallJumptables) {
   // Unlike the global bitset builder, the function bitset builder cannot
   // re-arrange functions in a particular order and base its calculations on the
   // layout of the functions' entry points, as we have no idea how large a
   // particular function will end up being (the size could even depend on what
   // this pass does!) Instead, we build a jump table, which is a block of code
   // consisting of one branch instruction for each of the functions in the bit
   // set that branches to the target function, and redirect any taken function
   // addresses to the corresponding jump table entry. In the object file's
Function *JumpTableFn =
                                          /* IsVarArg */ false),
                        GlobalValue::PrivateLinkage, ".cfi.jumptable", &M);
   ArrayType *JumpTableType =
       ArrayType::get(getJumpTableEntryType(), Functions.size());
   auto JumpTable =
       ConstantExpr::getPointerCast(JumpTableFn, JumpTableType->getPointerTo(0));
 
   lowerTypeTestCalls(TypeIds, JumpTable, GlobalLayout);
+  lowerIcallJumptableCalls(IcallJumptables, JumpTable, GlobalLayout);
 
   // Build aliases pointing to offsets into the jump table, and replace
   // references to the original functions with references to the aliases.
   for (unsigned I = 0; I != Functions.size(); ++I) {
     Function *F = cast<Function>(Functions[I]->getGlobal());
     bool IsDefinition = Functions[I]->isDefinition();
 
     Constant *CombinedGlobalElemPtr = ConstantExpr::getBitCast(
void LowerTypeTestsModule::buildBitSetsFromFunctionsWASM(
 
   // The indirect function table index space starts at zero, so pass a NULL
   // pointer as the subtracted "jump table" offset.
   lowerTypeTestCalls(TypeIds, ConstantPointerNull::get(Int32PtrTy),
                      GlobalLayout);
 }
 
 void LowerTypeTestsModule::buildBitSetsFromDisjointSet(
-    ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals) {
+    ArrayRef<Metadata *> TypeIds, ArrayRef<GlobalTypeMember *> Globals,
+    ArrayRef<IcallJumptable *> IcallJumptables) {
   DenseMap<Metadata *, uint64_t> TypeIdIndices;
   for (unsigned I = 0; I != TypeIds.size(); ++I)
     TypeIdIndices[TypeIds[I]] = I;
 
   // For each type identifier, build a set of indices that refer to members of
   // the type identifier.
   std::vector<std::set<uint64_t>> TypeMembers(TypeIds.size());
   unsigned GlobalIndex = 0;
+  DenseMap<GlobalTypeMember *, uint64_t> GlobalIndices;
   for (GlobalTypeMember *GTM : Globals) {
     for (MDNode *Type : GTM->types()) {
       // Type = { offset, type identifier }
-      unsigned TypeIdIndex = TypeIdIndices[Type->getOperand(1)];
-      TypeMembers[TypeIdIndex].insert(GlobalIndex);
+      auto I = TypeIdIndices.find(Type->getOperand(1));
+      if (I != TypeIdIndices.end())
+        TypeMembers[I->second].insert(GlobalIndex);
     }
+    GlobalIndices[GTM] = GlobalIndex;
     GlobalIndex++;
   }
 
+  for (IcallJumptable *JT : IcallJumptables) {
+    TypeMembers.emplace_back();
+    std::set<uint64_t> &TMSet = TypeMembers.back();
+    for (const IcallJumptableTarget &T : JT->targets())
+      TMSet.insert(GlobalIndices[T.GTM]);
+  }
+
   // Order the sets of indices by size. The GlobalLayoutBuilder works best
   // when given small index sets first.
   std::stable_sort(
       TypeMembers.begin(), TypeMembers.end(),
       [](const std::set<uint64_t> &O1, const std::set<uint64_t> &O2) {
         return O1.size() < O2.size();
       });
 
for (auto &&Offset : F) {
         report_fatal_error("Type identifier may not contain both global "
                            "variables and functions");
       *OGTMI++ = Globals[Offset];
     }
   }
 
   // Build the bitsets from this disjoint set.
   if (IsGlobalSet)
-    buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs);
+    buildBitSetsFromGlobalVariables(TypeIds, OrderedGTMs, IcallJumptables);
   else
-    buildBitSetsFromFunctions(TypeIds, OrderedGTMs);
+    buildBitSetsFromFunctions(TypeIds, OrderedGTMs, IcallJumptables);
 }
 
 /// Lower all type tests in this module.
 LowerTypeTestsModule::LowerTypeTestsModule(
     Module &M, ModuleSummaryIndex *ExportSummary,
     const ModuleSummaryIndex *ImportSummary)
     : M(M), ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
   assert(!(ExportSummary && ImportSummary));
bool LowerTypeTestsModule::runForTesting(Module &M) {
   }
 
   return Changed;
 }
 
 bool LowerTypeTestsModule::lower() {
   Function *TypeTestFunc =
       M.getFunction(Intrinsic::getName(Intrinsic::type_test));
-  if ((!TypeTestFunc || TypeTestFunc->use_empty()) && !ExportSummary &&
-      !ImportSummary)
+  Function *IcallJumptableFunc =
+      M.getFunction(Intrinsic::getName(Intrinsic::icall_jumptable));
+  if ((!TypeTestFunc || TypeTestFunc->use_empty()) &&
+      (!IcallJumptableFunc || IcallJumptableFunc->use_empty()) &&
+      !ExportSummary && !ImportSummary)
     return false;
 
   if (ImportSummary) {
     if (TypeTestFunc) {
       for (auto UI = TypeTestFunc->use_begin(), UE = TypeTestFunc->use_end();
            UI != UE;) {
         auto *CI = cast<CallInst>((*UI++).getUser());
         importTypeTest(CI);
       }
     }
 
+    if (IcallJumptableFunc && !IcallJumptableFunc->use_empty())
+      report_fatal_error(
+          "unexpected call to llvm.icall.jumptable during import phase");
+
     SmallVector<Function *, 8> Defs;
     SmallVector<Function *, 8> Decls;
     for (auto &F : M) {
       // CFI functions are either external, or promoted. A local function may
       // have the same name, but it's not the one we are looking for.
       if (F.hasLocalLinkage())
         continue;
       if (ImportSummary->cfiFunctionDefs().count(F.getName()))
         Defs.push_back(&F);
       else if (ImportSummary->cfiFunctionDecls().count(F.getName()))
         Decls.push_back(&F);
     }
 
     for (auto F : Defs)
       importFunction(F, /*isDefinition*/ true);
     for (auto F : Decls)
       importFunction(F, /*isDefinition*/ false);
 
     return true;
   }
 
   // Equivalence class set containing type identifiers and the globals that
   // reference them. This is used to partition the set of type identifiers in
   // the module into disjoint sets.
-  using GlobalClassesTy =
-      EquivalenceClasses<PointerUnion<GlobalTypeMember *, Metadata *>>;
+  using GlobalClassesTy = EquivalenceClasses<
+      PointerUnion3<GlobalTypeMember *, Metadata *, IcallJumptable *>>;
   GlobalClassesTy GlobalClasses;
 
   // Verify the type metadata and build a few data structures to let us
   // efficiently enumerate the type identifiers associated with a global:
   // a list of GlobalTypeMembers (a GlobalObject stored alongside a vector
   // of associated type metadata) and a mapping from type identifiers to their
   // list of GlobalTypeMembers and last observed index in the list of globals.
   // The indices will be used later to deterministically order the list of type
if (CfiFunctionsMD) {
           for (unsigned I = 2; I < FuncMD->getNumOperands(); ++I)
             F->addMetadata(LLVMContext::MD_type,
                            *cast<MDNode>(FuncMD->getOperand(I).get()));
         }
       }
     }
   }
 
+  DenseMap<GlobalObject *, GlobalTypeMember *> GlobalTypeMembers;
   for (GlobalObject &GO : M.global_objects()) {
     if (isa<GlobalVariable>(GO) && GO.isDeclarationForLinker())
       continue;
 
     Types.clear();
     GO.getMetadata(LLVMContext::MD_type, Types);
-    if (Types.empty())
-      continue;
 
     bool IsDefinition = !GO.isDeclarationForLinker();
     bool IsExported = false;
     if (isa<Function>(GO) && ExportedFunctions.count(GO.getName())) {
       IsDefinition |= ExportedFunctions[GO.getName()].Linkage == CFL_Definition;
       IsExported = true;
     }
 
     auto *GTM =
         GlobalTypeMember::create(Alloc, &GO, IsDefinition, IsExported, Types);
+    GlobalTypeMembers[&GO] = GTM;
     for (MDNode *Type : Types) {
       verifyTypeMDNode(&GO, Type);
       auto &Info = TypeIdInfo[Type->getOperand(1)];
       Info.Index = ++I;
       Info.RefGlobals.push_back(GTM);
     }
   }
 
for (const Use &U : TypeTestFunc->uses()) {
       auto TypeIdMDVal = dyn_cast<MetadataAsValue>(CI->getArgOperand(1));
       if (!TypeIdMDVal)
         report_fatal_error("Second argument of llvm.type.test must be metadata");
       auto TypeId = TypeIdMDVal->getMetadata();
       AddTypeIdUse(TypeId).CallSites.push_back(CI);
     }
   }
 
+  if (IcallJumptableFunc) {
+    for (const Use &U : IcallJumptableFunc->uses()) {
+      if (Arch != Triple::x86_64)
+        report_fatal_error("llvm.icall.jumptable not supported on this target");
+
+      auto CI = cast<CallInst>(U.getUser());
+
+      std::vector<IcallJumptableTarget> Targets;
+      if (CI->getNumArgOperands() % 2)
+        report_fatal_error("number of arguments should be a multiple of 2");
+
+      GlobalClassesTy::member_iterator CurSet;
+      for (unsigned I = 0; I != CI->getNumArgOperands(); I += 2) {
+        int64_t Offset;
+        auto *Base = dyn_cast<GlobalObject>(GetPointerBaseWithConstantOffset(
+            CI->getOperand(I), Offset, M.getDataLayout()));
+        if (!Base)
+          report_fatal_error("Expected jump table operand to be global value");
+
+        IcallJumptableTarget Target;
+        Target.GTM = GlobalTypeMembers[Base];
+        GlobalClassesTy::member_iterator NewSet =
+            GlobalClasses.findLeader(GlobalClasses.insert(Target.GTM));
+        if (I == 0)
+          CurSet = NewSet;
+        else
+          CurSet = GlobalClasses.unionSets(CurSet, NewSet);
+
+        Target.Offset = Offset;
+        auto *Callee = dyn_cast<Constant>(CI->getArgOperand(I + 1));
+        if (!Callee)
+          report_fatal_error("Callee must be a constant");
+        Target.Callee = Callee;
+        Targets.push_back(Target);
+      }
+
+      GlobalClasses.unionSets(CurSet,
+                              GlobalClasses.findLeader(GlobalClasses.insert(
+                                  IcallJumptable::create(Alloc, CI, Targets))));
+    }
+  }
+
   if (ExportSummary) {
     DenseMap<GlobalValue::GUID, TinyPtrVector<Metadata *>> MetadataByGUID;
     for (auto &P : TypeIdInfo) {
       if (auto *TypeId = dyn_cast<MDString>(P.first))
         MetadataByGUID[GlobalValue::getGUID(TypeId->getString())].push_back(
             TypeId);
     }
 
std::sort(Sets.begin(), Sets.end(),
               return S1.second < S2.second;
             });
 
   // For each disjoint set we found...
   for (const auto &S : Sets) {
     // Build the list of type identifiers in this disjoint set.
     std::vector<Metadata *> TypeIds;
     std::vector<GlobalTypeMember *> Globals;
+    std::vector<IcallJumptable *> IcallJumptables;
     for (GlobalClassesTy::member_iterator MI =
              GlobalClasses.member_begin(S.first);
          MI != GlobalClasses.member_end(); ++MI) {
-      if ((*MI).is<Metadata *>())
+      if (MI->is<Metadata *>())
         TypeIds.push_back(MI->get<Metadata *>());
-      else
+      else if (MI->is<GlobalTypeMember *>())
         Globals.push_back(MI->get<GlobalTypeMember *>());
+      else
+        IcallJumptables.push_back(MI->get<IcallJumptable *>());
     }
 
     // Order type identifiers by global index for determinism. This ordering is
     // stable as there is a one-to-one mapping between metadata and indices.
     std::sort(TypeIds.begin(), TypeIds.end(), [&](Metadata *M1, Metadata *M2) {
       return TypeIdInfo[M1].Index < TypeIdInfo[M2].Index;
     });
 
     // Build bitsets for this disjoint set.
-    buildBitSetsFromDisjointSet(TypeIds, Globals);
+    buildBitSetsFromDisjointSet(TypeIds, Globals, IcallJumptables);
   }
 
   allocateByteArrays();
 
   // Parse alias data to replace stand-in function declarations for aliases
   // with an alias to the intended target.
   if (ExportSummary) {
     if (NamedMDNode *AliasesMD = M.getNamedMetadata("aliases")) {

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

 // VTableSlotInfo class.
 struct CallSiteInfo {
   /// The set of call sites for this slot. Used during regular LTO and the
   /// import phase of ThinLTO (as well as the export phase of ThinLTO for any
   /// call sites that appear in the merged module itself); in each of these
   /// cases we are directly operating on the call sites at the IR level.
   std::vector<VirtualCallSite> CallSites;
 
+  /// Whether all call sites represented by this CallSiteInfo, including those
+  /// in summaries, have been devirtualized. This starts off as true because a
+  /// default constructed CallSiteInfo represents no call sites.
+  bool AllCallSitesDevirted = true;
+
   // These fields are used during the export phase of ThinLTO and reflect
   // information collected from function summaries.
 
   /// Whether any function summary contains an llvm.assume(llvm.type.test) for
   /// this slot.
-  bool SummaryHasTypeTestAssumeUsers;
+  bool SummaryHasTypeTestAssumeUsers = false;
 
   /// 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;
 
   bool isExported() const {
     return SummaryHasTypeTestAssumeUsers ||
            !SummaryTypeCheckedLoadUsers.empty();
   }
 
-  /// As explained in the comment for SummaryTypeCheckedLoadUsers.
-  void markDevirt() { SummaryTypeCheckedLoadUsers.clear(); }
+  void markSummaryHasTypeTestAssumeUsers() {
+    SummaryHasTypeTestAssumeUsers = true;
+    AllCallSitesDevirted = false;
+  }
+
+  void addSummaryTypeCheckedLoadUser(FunctionSummary *FS) {
+    SummaryTypeCheckedLoadUsers.push_back(FS);
+    AllCallSitesDevirted = false;
+  }
+
+  void markDevirt() {
+    AllCallSitesDevirted = true;
+
+    // As explained in the comment for SummaryTypeCheckedLoadUsers.
+    SummaryTypeCheckedLoadUsers.clear();
+  }
 };
 
 // Call site information collected for a specific VTableSlot.
 struct VTableSlotInfo {
   // The set of call sites which do not have all constant integer arguments
   // (excluding "this").
   CallSiteInfo CSInfo;
 
if (!CI || CI->getBitWidth() > 64)
       return CSInfo;
     Args.push_back(CI->getZExtValue());
   }
   return ConstCSInfo[Args];
 }
 
 void VTableSlotInfo::addCallSite(Value *VTable, CallSite CS,
                                  unsigned *NumUnsafeUses) {
-  findCallSiteInfo(CS).CallSites.push_back({VTable, CS, NumUnsafeUses});
+  auto &CSI = findCallSiteInfo(CS);
+  CSI.AllCallSitesDevirted = false;
+  CSI.CallSites.push_back({VTable, CS, NumUnsafeUses});
 }
 
 struct DevirtModule {
   Module &M;
   function_ref<AAResults &(Function &)> AARGetter;
 
   ModuleSummaryIndex *ExportSummary;
   const ModuleSummaryIndex *ImportSummary;
tryFindVirtualCallTargets(std::vector<VirtualCallTarget> &TargetsForSlot,
                             uint64_t ByteOffset);
 
   void applySingleImplDevirt(VTableSlotInfo &SlotInfo, Constant *TheFn,
                              bool &IsExported);
   bool trySingleImplDevirt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                            VTableSlotInfo &SlotInfo,
                            WholeProgramDevirtResolution *Res);
 
+  void applyIcallJumpTable(VTableSlotInfo &SlotInfo, Constant *JT,
+                           bool &IsExported);
+  void tryIcallJumpTable(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
+                         VTableSlotInfo &SlotInfo,
+                         WholeProgramDevirtResolution *Res, VTableSlot Slot);
+
   bool tryEvaluateFunctionsWithArgs(
       MutableArrayRef<VirtualCallTarget> TargetsForSlot,
       ArrayRef<uint64_t> Args);
 
   void applyUniformRetValOpt(CallSiteInfo &CSInfo, StringRef FnName,
                              uint64_t TheRetVal);
   bool tryUniformRetValOpt(MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                            CallSiteInfo &CSInfo,
struct DevirtModule {
   // This function is called during the import phase to create a reference to
   // the symbol definition created during the export phase.
   Constant *importGlobal(VTableSlot Slot, ArrayRef<uint64_t> Args,
                          StringRef Name);
   Constant *importConstant(VTableSlot Slot, ArrayRef<uint64_t> Args,
                            StringRef Name, IntegerType *IntTy,
                            uint32_t Storage);
 
+  Constant *getMemberAddr(const TypeMemberInfo *M);
+
   void applyUniqueRetValOpt(CallSiteInfo &CSInfo, StringRef FnName, bool IsOne,
                             Constant *UniqueMemberAddr);
   bool tryUniqueRetValOpt(unsigned BitWidth,
                           MutableArrayRef<VirtualCallTarget> TargetsForSlot,
                           CallSiteInfo &CSInfo,
                           WholeProgramDevirtResolution::ByArg *Res,
                           VTableSlot Slot, ArrayRef<uint64_t> Args);
 
for (auto &&VCallSite : CSInfo.CallSites) {
       if (RemarksEnabled)
         VCallSite.emitRemark("single-impl", TheFn->getName(), OREGetter);
       VCallSite.CS.setCalledFunction(ConstantExpr::getBitCast(
           TheFn, VCallSite.CS.getCalledValue()->getType()));
       // This use is no longer unsafe.
       if (VCallSite.NumUnsafeUses)
         --*VCallSite.NumUnsafeUses;
     }
-    if (CSInfo.isExported()) {
+    if (CSInfo.isExported())
       IsExported = true;
-      CSInfo.markDevirt();
-    }
   };
   Apply(SlotInfo.CSInfo);
   for (auto &P : SlotInfo.ConstCSInfo)
     Apply(P.second);
 }
 
 bool DevirtModule::trySingleImplDevirt(
     MutableArrayRef<VirtualCallTarget> TargetsForSlot,
bool DevirtModule::trySingleImplDevirt(
   }
 
   Res->TheKind = WholeProgramDevirtResolution::SingleImpl;
   Res->SingleImplName = TheFn->getName();
 
   return true;
 }
 
+void DevirtModule::tryIcallJumpTable(
+    MutableArrayRef<VirtualCallTarget> TargetsForSlot, VTableSlotInfo &SlotInfo,
+    WholeProgramDevirtResolution *Res, VTableSlot Slot) {
+  Triple T(M.getTargetTriple());
+  if (T.getArch() != Triple::x86_64)
+    return;
+
+  const unsigned kJumpTableThreshold = 10;
+  if (TargetsForSlot.size() > kJumpTableThreshold)
+    return;
+
+  bool HasNonDevirt = !SlotInfo.CSInfo.AllCallSitesDevirted;
+  if (!HasNonDevirt)
+    for (auto &P : SlotInfo.ConstCSInfo)
+      if (!P.second.AllCallSitesDevirted) {
+        HasNonDevirt = true;
+        break;
+      }
+
+  if (!HasNonDevirt)
+    return;
+
+  std::vector<Value *> JTArgs;
+  for (auto &T : TargetsForSlot) {
+    JTArgs.push_back(getMemberAddr(T.TM));
+    JTArgs.push_back(T.Fn);
+  }
+
+  FunctionType *FT = FunctionType::get(Type::getVoidTy(M.getContext()), {}, false);
+  Function *JT;
+  if (isa<MDString>(Slot.TypeID)) {
+    JT = Function::Create(FT, Function::ExternalLinkage,
+                          getGlobalName(Slot, {}, "jumptable"), &M);
+    JT->setVisibility(GlobalValue::HiddenVisibility);
+  } else {
+    JT = Function::Create(FT, Function::InternalLinkage, "jumptable", &M);
+  }
+  // Skip prologue.
+  // Disabled on win32 due to https://llvm.org/bugs/show_bug.cgi?id=28641#c3.
+  // Luckily, this function does not get any prologue even without the
+  // attribute.
+  if (T.getOS() != Triple::Win32)
+    JT->addFnAttr(Attribute::Naked);
+
+  BasicBlock *BB = BasicBlock::Create(M.getContext(), "", JT, nullptr);
+  Constant *Intr =
+      Intrinsic::getDeclaration(&M, llvm::Intrinsic::icall_jumptable, {});
+
+  CallInst::Create(Intr, JTArgs, "", BB);
+  ReturnInst::Create(M.getContext(), nullptr, BB);
+
+  bool IsExported = false;
+  applyIcallJumpTable(SlotInfo, JT, IsExported);
+  if (IsExported)
+    Res->TheKind = WholeProgramDevirtResolution::JumpTable;
+}
+
+void DevirtModule::applyIcallJumpTable(VTableSlotInfo &SlotInfo, Constant *JT,
+                                       bool &IsExported) {
+  auto Apply = [&](CallSiteInfo &CSInfo) {
+    if (CSInfo.isExported())
+      IsExported = true;
+    if (CSInfo.AllCallSitesDevirted)
+      return;
+    for (auto &&VCallSite : CSInfo.CallSites) {
+      CallSite CS = VCallSite.CS;
+
+      // Jump tables are only profitable if the retpoline mitigation is enabled.
+      Attribute FSAttr = CS.getCaller()->getFnAttribute("target-features");
+      if (FSAttr.hasAttribute(Attribute::None) ||
+          !FSAttr.getValueAsString().contains("+retpoline"))
+        continue;
+
+      if (RemarksEnabled)
+        VCallSite.emitRemark("jump-table", JT->getName(), OREGetter);
+
+      // Pass the address of the vtable in the nest register, which is r10 on
+      // x86_64.
+      std::vector<Type *> NewArgs;
+      NewArgs.push_back(Int8PtrTy);
+      for (Type *T : CS.getFunctionType()->params())
+        NewArgs.push_back(T);
+      PointerType *NewFT = PointerType::getUnqual(
+          FunctionType::get(CS.getFunctionType()->getReturnType(), NewArgs,
+                            CS.getFunctionType()->isVarArg()));
+
+      IRBuilder<> IRB(CS.getInstruction());
+      std::vector<Value *> Args;
+      Args.push_back(IRB.CreateBitCast(VCallSite.VTable, Int8PtrTy));
+      for (unsigned I = 0; I != CS.getNumArgOperands(); ++I)
+        Args.push_back(CS.getArgOperand(I));
+
+      CallSite NewCS;
+      if (CS.isCall())
+        NewCS = IRB.CreateCall(IRB.CreateBitCast(JT, NewFT), Args);
+      else
+        NewCS = IRB.CreateInvoke(
+            IRB.CreateBitCast(JT, NewFT),
+            cast<InvokeInst>(CS.getInstruction())->getNormalDest(),
+            cast<InvokeInst>(CS.getInstruction())->getUnwindDest(), Args);
+      NewCS.setCallingConv(CS.getCallingConv());
+
+      AttributeList Attrs = CS.getAttributes();
+      std::vector<AttributeSet> NewArgAttrs;
+      NewArgAttrs.push_back(AttributeSet::get(
+          M.getContext(),
+          ArrayRef<Attribute>{Attribute::get(M.getContext(), Attribute::Nest)}));
+      for (unsigned I = 0; I + 2 <  Attrs.getNumAttrSets(); ++I)
+        NewArgAttrs.push_back(Attrs.getParamAttributes(I));
+      NewCS.setAttributes(
+          AttributeList::get(M.getContext(), Attrs.getFnAttributes(),
+                             Attrs.getRetAttributes(), NewArgAttrs));
+
+      CS->replaceAllUsesWith(NewCS.getInstruction());
+      CS->eraseFromParent();
+
+      // This use is no longer unsafe.
+      if (VCallSite.NumUnsafeUses)
+        --*VCallSite.NumUnsafeUses;
+    }
+    // Don't mark as devirtualized because there may be callers compiled without
+    // retpoline mitigation, which would mean that they are lowered to
+    // llvm.type.test and therefore require an llvm.type.test resolution for the
+    // type identifier.
+  };
+  Apply(SlotInfo.CSInfo);
+  for (auto &P : SlotInfo.ConstCSInfo)
+    Apply(P.second);
+}
+
 bool DevirtModule::tryEvaluateFunctionsWithArgs(
     MutableArrayRef<VirtualCallTarget> TargetsForSlot,
     ArrayRef<uint64_t> Args) {
   // Evaluate each function and store the result in each target's RetVal
   // field.
   for (VirtualCallTarget &Target : TargetsForSlot) {
     if (Target.Fn->arg_size() != Args.size() + 1)
       return false;
Value *Cmp =
                      B.CreateBitCast(Call.VTable, Int8PtrTy), UniqueMemberAddr);
     Cmp = B.CreateZExt(Cmp, Call.CS->getType());
     Call.replaceAndErase("unique-ret-val", FnName, RemarksEnabled, OREGetter,
                          Cmp);
   }
   CSInfo.markDevirt();
 }
 
+Constant *DevirtModule::getMemberAddr(const TypeMemberInfo *M) {
+  Constant *C = ConstantExpr::getBitCast(M->Bits->GV, Int8PtrTy);
+  return ConstantExpr::getGetElementPtr(Int8Ty, C,
+                                        ConstantInt::get(Int64Ty, M->Offset));
+}
+
 bool DevirtModule::tryUniqueRetValOpt(
     unsigned BitWidth, MutableArrayRef<VirtualCallTarget> TargetsForSlot,
     CallSiteInfo &CSInfo, WholeProgramDevirtResolution::ByArg *Res,
     VTableSlot Slot, ArrayRef<uint64_t> Args) {
   // IsOne controls whether we look for a 0 or a 1.
   auto tryUniqueRetValOptFor = [&](bool IsOne) {
     const TypeMemberInfo *UniqueMember = nullptr;
     for (const VirtualCallTarget &Target : TargetsForSlot) {
       if (Target.RetVal == (IsOne ? 1 : 0)) {
         if (UniqueMember)
           return false;
         UniqueMember = Target.TM;
       }
     }
 
     // We should have found a unique member or bailed out by now. We already
     // checked for a uniform return value in tryUniformRetValOpt.
     assert(UniqueMember);
 
-    Constant *UniqueMemberAddr =
-        ConstantExpr::getBitCast(UniqueMember->Bits->GV, Int8PtrTy);
-    UniqueMemberAddr = ConstantExpr::getGetElementPtr(
-        Int8Ty, UniqueMemberAddr,
-        ConstantInt::get(Int64Ty, UniqueMember->Offset));
-
+    Constant *UniqueMemberAddr = getMemberAddr(UniqueMember);
     if (CSInfo.isExported()) {
       Res->TheKind = WholeProgramDevirtResolution::ByArg::UniqueRetVal;
       Res->Info = IsOne;
 
       exportGlobal(Slot, Args, "unique_member", UniqueMemberAddr);
     }
 
     // Replace each call with the comparison.
case WholeProgramDevirtResolution::ByArg::VirtualConstProp: {
                                      ResByArg.Bit);
       applyVirtualConstProp(CSByConstantArg.second, "", Byte, Bit);
       break;
     }
     default:
       break;
     }
   }
+
+  if (Res.TheKind == WholeProgramDevirtResolution::JumpTable) {
+    auto *JT = M.getOrInsertFunction(getGlobalName(Slot, {}, "jumptable"),
+                                     Type::getVoidTy(M.getContext()));
+    bool IsExported = false;
+    applyIcallJumpTable(SlotInfo, JT, IsExported);
+    assert(!IsExported);
+  }
 }
 
 void DevirtModule::removeRedundantTypeTests() {
   auto True = ConstantInt::getTrue(M.getContext());
   for (auto &&U : NumUnsafeUsesForTypeTest) {
     if (U.second == 0) {
       U.first->replaceAllUsesWith(True);
       U.first->eraseFromParent();
if (ExportSummary) {
     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 (Metadata *MD : MetadataByGUID[VF.GUID]) {
-            CallSlots[{MD, VF.Offset}].CSInfo.SummaryHasTypeTestAssumeUsers =
-                true;
+            CallSlots[{MD, VF.Offset}]
+                .CSInfo.markSummaryHasTypeTestAssumeUsers();
           }
         }
         for (FunctionSummary::VFuncId VF : FS->type_checked_load_vcalls()) {
           for (Metadata *MD : MetadataByGUID[VF.GUID]) {
-            CallSlots[{MD, VF.Offset}]
-                .CSInfo.SummaryTypeCheckedLoadUsers.push_back(FS);
+            CallSlots[{MD, VF.Offset}].CSInfo.addSummaryTypeCheckedLoadUser(FS);
           }
         }
         for (const FunctionSummary::ConstVCall &VC :
              FS->type_test_assume_const_vcalls()) {
           for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
             CallSlots[{MD, VC.VFunc.Offset}]
                 .ConstCSInfo[VC.Args]
-                .SummaryHasTypeTestAssumeUsers = true;
+                .markSummaryHasTypeTestAssumeUsers();
           }
         }
         for (const FunctionSummary::ConstVCall &VC :
              FS->type_checked_load_const_vcalls()) {
           for (Metadata *MD : MetadataByGUID[VC.VFunc.GUID]) {
             CallSlots[{MD, VC.VFunc.Offset}]
                 .ConstCSInfo[VC.Args]
-                .SummaryTypeCheckedLoadUsers.push_back(FS);
+                .addSummaryTypeCheckedLoadUser(FS);
           }
         }
       }
     }
   }
 
   // For each (type, offset) pair:
   bool DidVirtualConstProp = false;
   std::map<std::string, Function*> DevirtTargets;
   for (auto &S : CallSlots) {
     // Search each of the members of the type identifier for the virtual
     // function implementation at offset S.first.ByteOffset, and add to
     // TargetsForSlot.
     std::vector<VirtualCallTarget> TargetsForSlot;
     if (tryFindVirtualCallTargets(TargetsForSlot, TypeIdMap[S.first.TypeID],
                                   S.first.ByteOffset)) {
       WholeProgramDevirtResolution *Res = nullptr;
       if (ExportSummary && isa<MDString>(S.first.TypeID))
         Res = &ExportSummary
                    ->getOrInsertTypeIdSummary(
                        cast<MDString>(S.first.TypeID)->getString())
                    .WPDRes[S.first.ByteOffset];
 
-      if (!trySingleImplDevirt(TargetsForSlot, S.second, Res) &&
-          tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first))
-        DidVirtualConstProp = true;
+      if (!trySingleImplDevirt(TargetsForSlot, S.second, Res)) {
+        DidVirtualConstProp |=
+            tryVirtualConstProp(TargetsForSlot, S.second, Res, S.first);
+
+        tryIcallJumpTable(TargetsForSlot, S.second, Res, S.first);
+      }
 
       // Collect functions devirtualized at least for one call site for stats.
       if (RemarksEnabled)
         for (const auto &T : TargetsForSlot)
           if (T.WasDevirt)
             DevirtTargets[T.Fn->getName()] = T.Fn;
     }
 

llvm/test/Transforms/LowerTypeTests/icall-jumptable.ll

+; RUN: opt -S -lowertypetests < %s | FileCheck %s
+
+target datalayout = "e-p:64:64"
+target triple = "x86_64-unknown-linux"
+
+; CHECK: @0 = private constant { i32, [0 x i8], i32, [0 x i8], i32 } { i32 1, [0 x i8] zeroinitializer, i32 2, [0 x i8] zeroinitializer, i32 3 }
+@g1 = constant i32 1
+@g2 = constant i32 2, !type !0
+@g3 = constant i32 3, !type !0
+
+define void @f1() !type !1 {
+  ret void
+}
+
+define void @f2() !type !1 {
+  ret void
+}
+
+define void @f3() !type !1 {
+  ret void
+}
+
+define void @f4() !type !1 {
+  ret void
+}
+
+define void @f5() !type !1 {
+  ret void
+}
+
+define void @f6() !type !1 {
+  ret void
+}
+
+define void @f7() !type !1 {
+  ret void
+}
+
+define void @f8() !type !1 {
+  ret void
+}
+
+define void @f9() !type !1 {
+  ret void
+}
+
+define void @f10() !type !1 {
+  ret void
+}
+
+declare void @g1f()
+declare void @g2f()
+
+; CHECK: define void @jt2()
+define void @jt2() {
+  ; CHECK-NEXT: call void asm sideeffect "leaq ${0:c}+5(%rip), %r11\0Acmp %r11, %r10\0Ajb ${1:c}@plt\0Ajmp ${2:c}@plt\0A", "s,s,s"({ i32, [0 x i8], i32, [0 x i8], i32 }* @0, void ()* @g1f, void ()* @g2f)
+  call void (...) @llvm.icall.jumptable(
+      i32* @g1, void ()* @g1f,
+      i8* getelementptr (i8, i8* bitcast (i32* @g2 to i8*), i64 1), void ()* @g2f
+  )
+  ret void
+}
+
+; CHECK: define void @jt3()
+define void @jt3() {
+  ; CHECK-NEXT: call void asm sideeffect "leaq ${0:c}+8(%rip), %r11\0Acmp %r11, %r10\0Ajb ${1:c}@plt\0Aje ${2:c}@plt\0Ajmp ${3:c}@plt\0A", "s,s,s,s"([10 x [8 x i8]]* bitcast (void ()* @.cfi.jumptable to [10 x [8 x i8]]*), void ()* @f1, void ()* @f2, void ()* @f3)
+  call void (...) @llvm.icall.jumptable(
+      void ()* @f1, void ()* @f1,
+      void ()* @f2, void ()* @f2,
+      void ()* @f3, void ()* @f3
+  )
+  ret void
+}
+
+; CHECK: define void @jt7()
+define void @jt7() {
+  ; CHECK-NEXT: call void asm sideeffect "leaq ${0:c}+24(%rip), %r11\0Acmp %r11, %r10\0Ajb 0f\0Aje ${1:c}@plt\0Aleaq ${2:c}+40(%rip), %r11\0Acmp %r11, %r10\0Ajb ${3:c}@plt\0Aje ${4:c}@plt\0Ajmp ${5:c}@plt\0A0:\0Aleaq ${6:c}+8(%rip), %r11\0Acmp %r11, %r10\0Ajb ${7:c}@plt\0Aje ${8:c}@plt\0Ajmp ${9:c}@plt\0A", "s,s,s,s,s,s,s,s,s,s"([10 x [8 x i8]]* bitcast (void ()* @.cfi.jumptable to [10 x [8 x i8]]*), void ()* @f4, [10 x [8 x i8]]* bitcast (void ()* @.cfi.jumptable to [10 x [8 x i8]]*), void ()* @f5, void ()* @f6, void ()* @f7, [10 x [8 x i8]]* bitcast (void ()* @.cfi.jumptable to [10 x [8 x i8]]*), void ()* @f1, void ()* @f2, void ()* @f3)
+  call void (...) @llvm.icall.jumptable(
+      void ()* @f1, void ()* @f1,
+      void ()* @f2, void ()* @f2,
+      void ()* @f3, void ()* @f3,
+      void ()* @f4, void ()* @f4,
+      void ()* @f5, void ()* @f5,
+      void ()* @f6, void ()* @f6,
+      void ()* @f7, void ()* @f7
+  )
+  ret void
+}
+
+; CHECK: define void @jt10()
+define void @jt10() {
+  ; CHECK-NEXT: call void asm sideeffect "leaq ${0:c}+40(%rip), %r11\0Acmp %r11, %r10\0Ajb 0f\0Aje ${1:c}@plt\0Aleaq ${2:c}+56(%rip), %r11\0Acmp %r11, %r10\0Ajb ${3:c}@plt\0Aje ${4:c}@plt\0Aleaq ${5:c}+72(%rip), %r11\0Acmp %r11, %r10\0Ajb ${6:c}@plt\0Ajmp ${7:c}@plt\0A0:\0Aleaq ${8:c}+8(%rip), %r11\0Acmp %r11, %r10\0Ajb ${9:c}@plt\0Aje ${10:c}@plt\0Aleaq ${11:c}+24(%rip), %r11\0Acmp %r11, %r10\0Ajb ${12:c}@plt\0Aje ${13:c}@plt\0Ajmp ${14:c}@plt\0A", "s,s,s,s,s,s,s,s,s,s,s,s,s,s,s"([10 x [8 x i8]]* bitcast (void ()* @.cfi.jumptable to [10 x [8 x i8]]*), void ()* @f6, [10 x [8 x i8]]* bitcast (void ()* @.cfi.jumptable to [10 x [8 x i8]]*), void ()* @f7, void ()* @f8, [10 x [8 x i8]]* bitcast (void ()* @.cfi.jumptable to [10 x [8 x i8]]*), void ()* @f9, void ()* @f10, [10 x [8 x i8]]* bitcast (void ()* @.cfi.jumptable to [10 x [8 x i8]]*), void ()* @f1, void ()* @f2, [10 x [8 x i8]]* bitcast (void ()* @.cfi.jumptable to [10 x [8 x i8]]*), void ()* @f3, void ()* @f4, void ()* @f5)
+  call void (...) @llvm.icall.jumptable(
+      void ()* @f1, void ()* @f1,
+      void ()* @f2, void ()* @f2,
+      void ()* @f3, void ()* @f3,
+      void ()* @f4, void ()* @f4,
+      void ()* @f5, void ()* @f5,
+      void ()* @f6, void ()* @f6,
+      void ()* @f7, void ()* @f7,
+      void ()* @f8, void ()* @f8,
+      void ()* @f9, void ()* @f9,
+      void ()* @f10, void ()* @f10
+  )
+  ret void
+}
+
+define i1 @tt(i8* %ptr) {
+  %p = call i1 @llvm.type.test(i8* %ptr, metadata !"typeid1")
+  ret i1 %p
+}
+
+!0 = !{i32 0, !"typeid1"}
+!1 = !{i32 0, !"typeid2"}
+
+declare i1 @llvm.type.test(i8* %ptr, metadata %bitset) nounwind readnone
+declare void @llvm.icall.jumptable(...)

llvm/test/Transforms/WholeProgramDevirt/Inputs/import-jumptable.yaml

+---
+TypeIdMap:
+  typeid1:
+    WPDRes:
+      0:
+        Kind: JumpTable
+  typeid2:
+    WPDRes:
+      8:
+        Kind: JumpTable
+...

llvm/test/Transforms/WholeProgramDevirt/Inputs/import-vcp-jumptable.yaml

+---
+TypeIdMap:
+  typeid1:
+    WPDRes:
+      0:
+        Kind: JumpTable
+        ResByArg:
+          1:
+            Kind: VirtualConstProp
+            Info: 0
+            Byte: 42
+            Bit: 0
+  typeid2:
+    WPDRes:
+      8:
+        Kind: JumpTable
+        ResByArg:
+          3:
+            Kind: VirtualConstProp
+            Info: 0
+            Byte: 43
+            Bit: 128
+...

llvm/test/Transforms/WholeProgramDevirt/import.ll

 ; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-single-impl.yaml < %s | FileCheck --check-prefixes=CHECK,SINGLE-IMPL %s
-; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-uniform-ret-val.yaml < %s | FileCheck --check-prefixes=CHECK,UNIFORM-RET-VAL %s
-; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-unique-ret-val0.yaml < %s | FileCheck --check-prefixes=CHECK,UNIQUE-RET-VAL0 %s
-; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-unique-ret-val1.yaml < %s | FileCheck --check-prefixes=CHECK,UNIQUE-RET-VAL1 %s
-; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-vcp.yaml < %s | FileCheck --check-prefixes=CHECK,VCP,VCP-X86,VCP64 %s
+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-uniform-ret-val.yaml < %s | FileCheck --check-prefixes=CHECK,INDIR,UNIFORM-RET-VAL %s
+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-unique-ret-val0.yaml < %s | FileCheck --check-prefixes=CHECK,INDIR,UNIQUE-RET-VAL0 %s
+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-unique-ret-val1.yaml < %s | FileCheck --check-prefixes=CHECK,INDIR,UNIQUE-RET-VAL1 %s
+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-vcp.yaml < %s | FileCheck --check-prefixes=CHECK,VCP,VCP-X86,VCP64,INDIR %s
 ; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-vcp.yaml -mtriple=i686-unknown-linux -data-layout=e-p:32:32 < %s | FileCheck --check-prefixes=CHECK,VCP,VCP-X86,VCP32 %s
 ; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-vcp.yaml -mtriple=armv7-unknown-linux -data-layout=e-p:32:32 < %s | FileCheck --check-prefixes=CHECK,VCP,VCP-ARM %s
+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-vcp-jumptable.yaml < %s | FileCheck --check-prefixes=CHECK,VCP,VCP-X86,VCP64,JUMPTABLE %s
+; RUN: opt -S -wholeprogramdevirt -wholeprogramdevirt-summary-action=import -wholeprogramdevirt-read-summary=%S/Inputs/import-jumptable.yaml < %s | FileCheck --check-prefixes=CHECK,JUMPTABLE,JUMPTABLE-NOVCP %s
 
 target datalayout = "e-p:64:64"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; VCP-X86: @__typeid_typeid1_0_1_byte = external hidden global i8, !absolute_symbol !0
 ; VCP-X86: @__typeid_typeid1_0_1_bit = external hidden global i8, !absolute_symbol !1
 ; VCP-X86: @__typeid_typeid2_8_3_byte = external hidden global i8, !absolute_symbol !0
 ; VCP-X86: @__typeid_typeid2_8_3_bit = external hidden global i8, !absolute_symbol !1
 
 ; Test cases where the argument values are known and we can apply virtual
 ; constant propagation.
 
 ; CHECK: define i32 @call1
-define i32 @call1(i8* %obj) {
+define i32 @call1(i8* %obj) #0 {
   %vtableptr = bitcast i8* %obj to [3 x i8*]**
   %vtable = load [3 x i8*]*, [3 x i8*]** %vtableptr
   %vtablei8 = bitcast [3 x i8*]* %vtable to i8*
   %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid1")
   call void @llvm.assume(i1 %p)
   %fptrptr = getelementptr [3 x i8*], [3 x i8*]* %vtable, i32 0, i32 0
   %fptr = load i8*, i8** %fptrptr
   %fptr_casted = bitcast i8* %fptr to i32 (i8*, i32)*
+  ; CHECK: {{.*}} = bitcast {{.*}} to i8*
+  ; VCP: [[VT1:%.*]] = bitcast {{.*}} to i8*
   ; SINGLE-IMPL: call i32 bitcast (void ()* @singleimpl1 to i32 (i8*, i32)*)
   %result = call i32 %fptr_casted(i8* %obj, i32 1)
   ; UNIFORM-RET-VAL: ret i32 42
-  ; VCP: {{.*}} = bitcast {{.*}} to i8*
-  ; VCP: [[VT1:%.*]] = bitcast {{.*}} to i8*
   ; VCP-X86: [[GEP1:%.*]] = getelementptr i8, i8* [[VT1]], i32 ptrtoint (i8* @__typeid_typeid1_0_1_byte to i32)
   ; VCP-ARM: [[GEP1:%.*]] = getelementptr i8, i8* [[VT1]], i32 42
   ; VCP: [[BC1:%.*]] = bitcast i8* [[GEP1]] to i32*
   ; VCP: [[LOAD1:%.*]] = load i32, i32* [[BC1]]
   ; VCP: ret i32 [[LOAD1]]
+  ; JUMPTABLE-NOVCP: [[VT1:%.*]] = bitcast {{.*}} to i8*
+  ; JUMPTABLE-NOVCP: call i32 bitcast (void ()* @__typeid_typeid1_0_jumptable to i32 (i8*, i8*, i32)*)(i8* nest [[VT1]], i8* %obj, i32 1)
   ret i32 %result
 }
 
 ; Test cases where the argument values are unknown, so we cannot apply virtual
 ; constant propagation.
 
 ; CHECK: define i1 @call2
-define i1 @call2(i8* %obj) {
+define i1 @call2(i8* %obj) #0 {
+  ; JUMPTABLE: [[VT1:%.*]] = bitcast {{.*}} to i8*
   %vtableptr = bitcast i8* %obj to [1 x i8*]**
   %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
   %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
   %pair = call {i8*, i1} @llvm.type.checked.load(i8* %vtablei8, i32 8, metadata !"typeid2")
   %fptr = extractvalue {i8*, i1} %pair, 0
   %p = extractvalue {i8*, i1} %pair, 1
   ; SINGLE-IMPL: br i1 true,
   br i1 %p, label %cont, label %trap
 
 cont:
   %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)*
   ; SINGLE-IMPL: call i1 bitcast (void ()* @singleimpl2 to i1 (i8*, i32)*)
-  ; UNIFORM-RET-VAL: call i1 %
-  ; UNIQUE-RET-VAL0: call i1 %
-  ; UNIQUE-RET-VAL1: call i1 %
+  ; INDIR: call i1 %
+  ; JUMPTABLE: call i1 bitcast (void ()* @__typeid_typeid2_8_jumptable to i1 (i8*, i8*, i32)*)(i8* nest [[VT1]], i8* %obj, i32 undef)
   %result = call i1 %fptr_casted(i8* %obj, i32 undef)
   ret i1 %result
 
 trap:
   call void @llvm.trap()
   unreachable
 }
 
 ; CHECK: define i1 @call3
-define i1 @call3(i8* %obj) {
+define i1 @call3(i8* %obj) #0 {
   %vtableptr = bitcast i8* %obj to [1 x i8*]**
   %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
   %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
   %pair = call {i8*, i1} @llvm.type.checked.load(i8* %vtablei8, i32 8, metadata !"typeid2")
   %fptr = extractvalue {i8*, i1} %pair, 0
   %p = extractvalue {i8*, i1} %pair, 1
   br i1 %p, label %cont, label %trap
 
 cont:
   %fptr_casted = bitcast i8* %fptr to i1 (i8*, i32)*
   %result = call i1 %fptr_casted(i8* %obj, i32 3)
   ; UNIQUE-RET-VAL0: icmp ne i8* %vtablei8, @__typeid_typeid2_8_3_unique_member
   ; UNIQUE-RET-VAL1: icmp eq i8* %vtablei8, @__typeid_typeid2_8_3_unique_member
   ; VCP: [[VT2:%.*]] = bitcast {{.*}} to i8*
   ; VCP-X86: [[GEP2:%.*]] = getelementptr i8, i8* [[VT2]], i32 ptrtoint (i8* @__typeid_typeid2_8_3_byte to i32)
   ; VCP-ARM: [[GEP2:%.*]] = getelementptr i8, i8* [[VT2]], i32 43
   ; VCP: [[LOAD2:%.*]] = load i8, i8* [[GEP2]]
   ; VCP-X86: [[AND2:%.*]] = and i8 [[LOAD2]], ptrtoint (i8* @__typeid_typeid2_8_3_bit to i8)
   ; VCP-ARM: [[AND2:%.*]] = and i8 [[LOAD2]], -128
   ; VCP: [[ICMP2:%.*]] = icmp ne i8 [[AND2]], 0
   ; VCP: ret i1 [[ICMP2]]
+  ; JUMPTABLE-NOVCP: [[VT2:%.*]] = bitcast {{.*}} to i8*
+  ; JUMPTABLE-NOVCP: call i1 bitcast (void ()* @__typeid_typeid2_8_jumptable to i1 (i8*, i8*, i32)*)(i8* nest [[VT2]], i8* %obj, i32 3)
   ret i1 %result
 
 trap:
   call void @llvm.trap()
   unreachable
 }
 
 ; SINGLE-IMPL-DAG: declare void @singleimpl1()
 ; SINGLE-IMPL-DAG: declare void @singleimpl2()
 
 ; VCP32: !0 = !{i32 -1, i32 -1}
 ; VCP64: !0 = !{i64 0, i64 4294967296}
 
 ; VCP32: !1 = !{i32 0, i32 256}
 ; VCP64: !1 = !{i64 0, i64 256}
 
 declare void @llvm.assume(i1)
 declare void @llvm.trap()
 declare {i8*, i1} @llvm.type.checked.load(i8*, i32, metadata)
 declare i1 @llvm.type.test(i8*, metadata)
+
+attributes #0 = { "target-features"="+retpoline" }

llvm/test/Transforms/WholeProgramDevirt/jumptable.ll

+; RUN: opt -S -wholeprogramdevirt %s | FileCheck --check-prefixes=CHECK,RETP %s
+; RUN: sed -e 's,+retpoline,-retpoline,g' %s | opt -S -wholeprogramdevirt | FileCheck --check-prefixes=CHECK,NORETP %s
+; RUN: opt -wholeprogramdevirt -wholeprogramdevirt-summary-action=export -wholeprogramdevirt-read-summary=%S/Inputs/export.yaml -wholeprogramdevirt-write-summary=%t -S -o - %s | FileCheck --check-prefixes=CHECK,RETP %s
+; RUN: FileCheck --check-prefix=SUMMARY %s < %t
+
+; SUMMARY:      TypeIdMap:       
+; SUMMARY-NEXT:   typeid1:         
+; SUMMARY-NEXT:     TTRes:           
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
+; SUMMARY-NEXT:       AlignLog2:       0
+; SUMMARY-NEXT:       SizeM1:          0
+; SUMMARY-NEXT:       BitMask:         0
+; SUMMARY-NEXT:       InlineBits:      0
+; SUMMARY-NEXT:     WPDRes:          
+; SUMMARY-NEXT:       0:               
+; SUMMARY-NEXT:         Kind:            JumpTable
+; SUMMARY-NEXT:         SingleImplName:  ''
+; SUMMARY-NEXT:         ResByArg:        
+; SUMMARY-NEXT:   typeid2:         
+; SUMMARY-NEXT:     TTRes:           
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
+; SUMMARY-NEXT:       AlignLog2:       0
+; SUMMARY-NEXT:       SizeM1:          0
+; SUMMARY-NEXT:       BitMask:         0
+; SUMMARY-NEXT:       InlineBits:      0
+; SUMMARY-NEXT:     WPDRes:          
+; SUMMARY-NEXT:       0:               
+; SUMMARY-NEXT:         Kind:            Indir
+; SUMMARY-NEXT:         SingleImplName:  ''
+; SUMMARY-NEXT:         ResByArg:        
+; SUMMARY-NEXT:   typeid3:         
+; SUMMARY-NEXT:     TTRes:           
+; SUMMARY-NEXT:       Kind:            Unsat
+; SUMMARY-NEXT:       SizeM1BitWidth:  0
+; SUMMARY-NEXT:       AlignLog2:       0
+; SUMMARY-NEXT:       SizeM1:          0
+; SUMMARY-NEXT:       BitMask:         0
+; SUMMARY-NEXT:       InlineBits:      0
+; SUMMARY-NEXT:     WPDRes:          
+; SUMMARY-NEXT:       0:               
+; SUMMARY-NEXT:         Kind:            JumpTable
+; SUMMARY-NEXT:         SingleImplName:  ''
+; SUMMARY-NEXT:         ResByArg:        
+
+target datalayout = "e-p:64:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+@vt1_1 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1_1 to i8*)], !type !0
+@vt1_2 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf1_2 to i8*)], !type !0
+
+declare i32 @vf1_1(i8* %this, i32 %arg)
+declare i32 @vf1_2(i8* %this, i32 %arg)
+
+@vt2_1 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_1 to i8*)], !type !1
+@vt2_2 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_2 to i8*)], !type !1
+@vt2_3 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_3 to i8*)], !type !1
+@vt2_4 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_4 to i8*)], !type !1
+@vt2_5 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_5 to i8*)], !type !1
+@vt2_6 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_6 to i8*)], !type !1
+@vt2_7 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_7 to i8*)], !type !1
+@vt2_8 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_8 to i8*)], !type !1
+@vt2_9 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_9 to i8*)], !type !1
+@vt2_10 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_10 to i8*)], !type !1
+@vt2_11 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf2_11 to i8*)], !type !1
+
+declare i32 @vf2_1(i8* %this, i32 %arg)
+declare i32 @vf2_2(i8* %this, i32 %arg)
+declare i32 @vf2_3(i8* %this, i32 %arg)
+declare i32 @vf2_4(i8* %this, i32 %arg)
+declare i32 @vf2_5(i8* %this, i32 %arg)
+declare i32 @vf2_6(i8* %this, i32 %arg)
+declare i32 @vf2_7(i8* %this, i32 %arg)
+declare i32 @vf2_8(i8* %this, i32 %arg)
+declare i32 @vf2_9(i8* %this, i32 %arg)
+declare i32 @vf2_10(i8* %this, i32 %arg)
+declare i32 @vf2_11(i8* %this, i32 %arg)
+
+@vt3_1 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf3_1 to i8*)], !type !2
+@vt3_2 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf3_2 to i8*)], !type !2
+
+declare i32 @vf3_1(i8* %this, i32 %arg)
+declare i32 @vf3_2(i8* %this, i32 %arg)
+
+@vt4_1 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf4_1 to i8*)], !type !3
+@vt4_2 = constant [1 x i8*] [i8* bitcast (i32 (i8*, i32)* @vf4_2 to i8*)], !type !3
+
+declare i32 @vf4_1(i8* %this, i32 %arg)
+declare i32 @vf4_2(i8* %this, i32 %arg)
+
+; CHECK: define i32 @fn1
+define i32 @fn1(i8* %obj) #0 {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid1")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*, i32)*
+  ; RETP: {{.*}} = bitcast {{.*}} to i8*
+  ; RETP: [[VT1:%.*]] = bitcast {{.*}} to i8*
+  ; RETP: call i32 bitcast (void ()* @__typeid_typeid1_0_jumptable to i32 (i8*, i8*, i32)*)(i8* nest [[VT1]], i8* %obj, i32 1)
+  %result = call i32 %fptr_casted(i8* %obj, i32 1)
+  ; NORETP: call i32 %
+  ret i32 %result
+}
+
+; CHECK: define i32 @fn2
+define i32 @fn2(i8* %obj) #0 {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !"typeid2")
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*, i32)*
+  ; CHECK: call i32 %
+  %result = call i32 %fptr_casted(i8* %obj, i32 1)
+  ret i32 %result
+}
+
+; CHECK: define i32 @fn3
+define i32 @fn3(i8* %obj) #0 {
+  %vtableptr = bitcast i8* %obj to [1 x i8*]**
+  %vtable = load [1 x i8*]*, [1 x i8*]** %vtableptr
+  %vtablei8 = bitcast [1 x i8*]* %vtable to i8*
+  %p = call i1 @llvm.type.test(i8* %vtablei8, metadata !4)
+  call void @llvm.assume(i1 %p)
+  %fptrptr = getelementptr [1 x i8*], [1 x i8*]* %vtable, i32 0, i32 0
+  %fptr = load i8*, i8** %fptrptr
+  %fptr_casted = bitcast i8* %fptr to i32 (i8*, i32)*
+  ; RETP: call i32 bitcast (void ()* @jumptable to
+  ; NORETP: call i32 %
+  %result = call i32 %fptr_casted(i8* %obj, i32 1)
+  ret i32 %result
+}
+
+; CHECK: define internal void @jumptable()
+
+; CHECK: define hidden void @__typeid_typeid1_0_jumptable() [[A:#[0-9]+]]
+; CHECK-NEXT: call void (...) @llvm.icall.jumptable(i8* bitcast ([1 x i8*]* @vt1_1 to i8*), i32 (i8*, i32)* @vf1_1, i8* bitcast ([1 x i8*]* @vt1_2 to i8*), i32 (i8*, i32)* @vf1_2)
+
+declare i1 @llvm.type.test(i8*, metadata)
+declare void @llvm.assume(i1)
+
+!0 = !{i32 0, !"typeid1"}
+!1 = !{i32 0, !"typeid2"}
+!2 = !{i32 0, !"typeid3"}
+!3 = !{i32 0, !4}
+!4 = distinct !{}
+
+; CHECK: attributes [[A]] = { naked }
+
+attributes #0 = { "target-features"="+retpoline" }