Add a jumptable attribute and support for creating jump-instruction tables

[tmroeder]

Summary

This patch provides a new jumptable attribute and associated CodeGen support to generate jump-instruction tables and replace function references for jumptable-annotated functions. The work of generating the tables is now done with an IR pass in CodeGen to replace address-taken functions, along with a change to AsmPrinter to generate the assembly for the tables. This is a followup to the discussion on llvmdev. See http://lists.cs.uiuc.edu/pipermail/llvmdev/2014-April/071866.html

This version of the patch has support for X86 and ARM backends, along with tests for each.

[nlewycky]

So first, a design comment. The 'jumptable' attribute itself has no IR
meaning. It doesn't change anything about the execution of the IR, it
doesn't change whether IR is valid, even. It appears to be an ABI attribute.

What's the right behaviour if you link together two modules where a
function is not "jumptable" in one but is in the other? Is it safe to apply
"jumptable" to a module that didn't have it? It looks like not. I think the
answer is that two modules needed to both have this attribute set the same
way in the two modules before merging, and that this is reasonable because
it's an ABI issue. Similarly, if you generated those two modules into .o
files, they wouldn't be ABI compatible in machine code either, right?

+ Don't do the replacement if this use is a direct call to this
function.
+​ if ((CS.isCall() || CS.isInvoke()) && !isIndirectCall(CS)) {
+​ If the use is not the called value, then replace it.
+​ if (CS.getCalledValue() != GV) {
+​ U->set(V);
+​ return true;
+ }

I think you have a bug here when the value is used both as the callee and
is also an argument. Instead you can use CS.isCallee(U); to determine
whether this particular use of your value is a use as the callee operand or
not.

"CS.isCall() || CS.isInvoke()" simplifies to "CS" used in a bool context.

+ Go through all uses of this function and replace the uses of GV with
the
+ jump-table version of the function. Get the uses as a vector before
+ replacing them, since replacing them changes the use list and
invalidates
+ the iterator otherwise.
+ std::vector<Use*> Uses;
+ for (Use &U : GV->uses())
+ Uses.push_back(&U);
+
+ for(Use *U : Uses)
+ replaceGlobalValueIndirectUse(GV, F, U);

Missing space after for.

The common way to handle the invalidation is more like:

for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E;)

{

  Use &U = *UI++;
  replaceGlobalValueIndirectUse(GV, F, U);
}

though that can probably be C++11ified now.

+ Type *Int32Ty = Type::getInt32Ty(getGlobalContext());

Nope. Let me explain what a context is for.

Suppose you have a game, and it uses a graphics library and it uses a 3d
audio library. Both of those in turn use llvm under the hood, but they
aren't aware of each other's existence. The purpose of the llvm context is
to keep "global" (or at least, "outside the Module") issues out of the
program-level global context, so that these two users can act independently
and not interfere with each other in any way.

The context for a module must match the context for everything inside it.

Finally, they're used for supporting threading. Types are pointer
comparable, if you construct the same type twice you get the same Type*.
The mapping that holds these is not locked, it's assumed that you only do
one operation on them at a time per-thread. If someone were to create two
threads each with their own LLVMContext to keep things separate, they
couldn't both call JumpInstrTables::transformType() since your function
would cause racy access to the internal map inside the global context.

+ return Functions.size() > 0;

DenseMap has an empty() method.

Nick

[tmroeder]

Thanks for the comments.

[tmroeder]

This diff fixes the problems noted in the review. PTAL.

For the for-loop invalidation problem, I didn't see any way to increment the implicit iterator early in C++11 style, so I've gone back to a standard iterator for loop to match the style of other invalidation-sensitive Use-handling loops.

Also, as I was working on these fixes, I found a problem with GlobalAlias: it doesn't support replaceUsesOfWithOnConstant, and it cannot target declaration-only functions. So, I've added some special-case handling for GlobalAlias statements that target jumptable functions. I've also added a new test case for "alias".

[tmroeder]

This version of the patch fixes the problems from the most recent review. It also adds the requirement that jumptable functions must also be unnamed_addr; this is now enforced by the Verifier. PTAL.

docs/LangRef.rst

     inlining this function is desirable (such as the "inline" keyword in
     C/C++). It is just a hint; it imposes no requirements on the
     inliner.
+``jumptable``
+    This attribute indicates that the function should be added to a
+    jump-instruction table at code-generation time, and that all address-taken
+    references to this function should be replaced with a reference to the
+    appropriate jump-instruction-table function pointer. It has no effect if the
+    -build-jump-instr-tables flag is not specified.
 ``minsize``
     This attribute suggests that optimization passes and code generator
     passes make choices that keep the code size of this function as small

include/llvm/Analysis/JumpInstrTableInfo.h

+//===- JumpInstrTableInfo.h: Info for Jump-Instruction Tables -*- C++ -*---===//
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief Information about jump-instruction tables that have been created by
+/// JumpInstrTables pass.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_JUMPINSTRTABLEINFO_H
+#define LLVM_ANALYSIS_JUMPINSTRTABLEINFO_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Pass.h"
+
+#include <vector>
+
+namespace llvm {
+class Function;
+class FunctionType;
+
+/// This class stores information about jump-instruction tables created by the
+/// JumpInstrTables pass (in lib/CodeGen/JumpInstrTables.cpp). Each table is a
+/// map from a function type to a vector of pairs. The first element of each
+/// pair is the function that has the jumptable annotation. The second element
+/// is a function that was declared by JumpInstrTables and used to replace all
+/// address-taking sites for the original function.
+///
+/// The information in this pass is used in AsmPrinter
+/// (lib/CodeGen/AsmPrinter/AsmPrinter.cpp) to generate the required assembly
+/// for the jump-instruction tables.
+class JumpInstrTableInfo : public ImmutablePass {
+public:
+  static char ID;
+
+  JumpInstrTableInfo();
+  virtual ~JumpInstrTableInfo() { }
+  const char *getPassName() const override {
+    return "Jump-Instruction Table Info";
+  }
+
+  typedef std::pair<Function *, Function *> JumpPair;
+  typedef DenseMap<FunctionType *, std::vector<JumpPair>> JumpTables;
+
+  /// Inserts an entry in a table, adding the table if it doesn't exist.
+  void insertEntry(FunctionType *TableFunTy, Function *Target, Function *Jump);
+
+  /// Gets the tables
+  const JumpTables &getTables() const { return Tables; }
+private:
+  JumpTables Tables;
+};
+}
+
+#endif /* LLVM_ANALYSIS_JUMPINSTRTABLEINFO_H */

include/llvm/Analysis/Passes.h

   // information and prints it with -analyze.
   //
   FunctionPass *createMemDepPrinter();
+
+  // createJumpInstrTableInfoPass - This creates a pass that stores information
+  // about the jump tables created by JumpInstrTables
+  ImmutablePass *createJumpInstrTableInfoPass();
 }
 
 #endif

include/llvm/Bitcode/LLVMBitCodes.h

     ATTR_KIND_BUILTIN = 35,
     ATTR_KIND_COLD = 36,
     ATTR_KIND_OPTIMIZE_NONE = 37,
-    ATTR_KIND_IN_ALLOCA = 38
+    ATTR_KIND_IN_ALLOCA = 38,
+    ATTR_KIND_JUMP_TABLE = 39
   };
 
 } // End bitc namespace

include/llvm/CodeGen/JumpInstrTables.h

+//===----- JumpInstrTables.h: Jump-Instruction Tables -*- C++ -*-----------===//
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief An implementation of tables consisting of jump instructions
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_JUMPINSTRTABLES_H
+#define LLVM_CODEGEN_JUMPINSTRTABLES_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+class Constant;
+class Function;
+class FunctionType;
+class JumpInstrTableInfo;
+class Module;
+
+/// A class to manage a set of jump tables indexed on function type. It looks at
+/// each function in the module to find all the functions that have the
+/// jumptable attribute set. For each such function, it creates a new
+/// jump-instruction-table function and stores the mapping in the ImmutablePass
+/// JumpInstrTableInfo.
+///
+/// These special functions get lowered in AsmPrinter to assembly of the form:
+///   .globl f
+///   .type f,@function
+///   .align 8,0x90
+/// f:
+///   jmp f_orig@PLT
+///
+/// Support for an architecture depends on two functions in TargetInstrInfo:
+/// getUnconditionalBranch, and getTrap. AsmPrinter uses these to generate the
+/// appropriate instructions for the jump statement (an unconditional branch)
+/// and for padding to make the table have a size that is a power of two. This
+/// padding uses a trap instruction to ensure that calls to this area halt the
+/// program. The default implementations of these functions call
+/// llvm_unreachable.
+class JumpInstrTables : public ModulePass {
+public:
+  static char ID;
+
+  JumpInstrTables();
+  virtual ~JumpInstrTables() { }
+  bool runOnModule(Module &M) override;
+  const char *getPassName() const override { return "Jump-Instruction Tables"; }
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  /// Creates a jump-instruction table function for the Target and adds it to
+  /// the tables.
+  Function *insertEntry(Module &M, Function *Target);
+
+  /// Checks to see if there is already a table for the given FunctionType.
+  bool hasTable(FunctionType *FunTy);
+
+private:
+  /// The metadata used while a jump table is being built
+  typedef struct TableMeta {
+    /// The number of this table
+    unsigned TableNum;
+
+    /// The current number of jump entries in the table.
+    unsigned Count;
+  } TableMetadata;
+
+  typedef DenseMap<FunctionType *, TableMetadata> JumpMap;
+
+  /// Maps the function into a subset of function types, depending on the
+  /// jump-instruction table style selected from JumpTableTypes in
+  /// JumpInstrTables.cpp. The choice of mapping determines the number of
+  /// jump-instruction tables generated by this pass. E.g., the simplest mapping
+  /// converts every function type into void f(); so, all functions end up in a
+  /// single table.
+  FunctionType *transformType(FunctionType *FunTy);
+
+  /// The current state of functions and jump entries in the table(s).
+  JumpMap Metadata;
+
+  /// The ImmutablePass that stores information about the generated tables.
+  JumpInstrTableInfo *JITI;
+
+  /// The total number of tables
+  unsigned TableCount;
+};
+}
+
+#endif /* LLVM_CODEGEN_JUMPINSTRTABLES_H */

include/llvm/CodeGen/Passes.h

   /// the intrinsic for later emission to the StackMap.
   extern char &StackMapLivenessID;
 
+  /// createJumpInstrTables - This pass creates jump-instruction tables.
+  ModulePass *createJumpInstrTablesPass();
 } // End llvm namespace
 
 #endif

include/llvm/IR/Attributes.h

     Cold,                  ///< Marks function as being in a cold path.
     InlineHint,            ///< Source said inlining was desirable
     InReg,                 ///< Force argument to be passed in register
+    JumpTable,             ///< Build jump-instruction tables and replace refs.
     MinSize,               ///< Function must be optimized for size first
     Naked,                 ///< Naked function
     Nest,                  ///< Nested function static chain

include/llvm/InitializePasses.h

 void initializeInstNamerPass(PassRegistry&);
 void initializeInternalizePassPass(PassRegistry&);
 void initializeIntervalPartitionPass(PassRegistry&);
+void initializeJumpInstrTableInfoPass(PassRegistry&);
+void initializeJumpInstrTablesPass(PassRegistry&);
 void initializeJumpThreadingPass(PassRegistry&);
 void initializeLCSSAPass(PassRegistry&);
 void initializeLICMPass(PassRegistry&);

include/llvm/LinkAllPasses.h

       (void) llvm::createIndVarSimplifyPass();
       (void) llvm::createInstructionCombiningPass();
       (void) llvm::createInternalizePass();
+      (void) llvm::createJumpInstrTableInfoPass();
+      (void) llvm::createJumpInstrTablesPass();
       (void) llvm::createLCSSAPass();
       (void) llvm::createLICMPass();
       (void) llvm::createLazyValueInfoPass();

include/llvm/Target/TargetInstrInfo.h

 class MDNode;
 class MCInst;
 class MCSchedModel;
+class MCSymbolRefExpr;
 class SDNode;
 class ScheduleHazardRecognizer;
 class SelectionDAG;

   virtual void ReplaceTailWithBranchTo(MachineBasicBlock::iterator Tail,
                                        MachineBasicBlock *NewDest) const;
 
+  /// getUnconditionalBranch - Get an instruction that performs an unconditional
+  /// branch to the given symbol.
+  virtual void
+  getUnconditionalBranch(MCInst &MI,
+                         const MCSymbolRefExpr *BranchTarget) const {
+    llvm_unreachable("Target didn't implement "
+                     "TargetInstrInfo::getUnconditionalBranch!");
+  }
+
+  /// getTrap - Get a machine trap instruction
+  virtual void getTrap(MCInst &MI) const {
+    llvm_unreachable("Target didn't implement TargetInstrInfo::getTrap!");
+  }
+
   /// isLegalToSplitMBBAt - Return true if it's legal to split the given basic
   /// block at the specified instruction (i.e. instruction would be the start
   /// of a new basic block).

lib/Analysis/Analysis.cpp

   initializeIVUsersPass(Registry);
   initializeInstCountPass(Registry);
   initializeIntervalPartitionPass(Registry);
+  initializeJumpInstrTableInfoPass(Registry);
   initializeLazyValueInfoPass(Registry);
   initializeLibCallAliasAnalysisPass(Registry);
   initializeLintPass(Registry);

lib/Analysis/CMakeLists.txt

   InstructionSimplify.cpp
   Interval.cpp
   IntervalPartition.cpp
+  JumpInstrTableInfo.cpp
   LazyCallGraph.cpp
   LazyValueInfo.cpp
   LibCallAliasAnalysis.cpp

lib/Analysis/JumpInstrTableInfo.cpp

+//===- JumpInstrTableInfo.cpp: Info for Jump-Instruction Tables -*- C++ -*-===//
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief Information about jump-instruction tables that have been created by
+/// JumpInstrTables pass.
+///
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "jiti"
+
+#include "llvm/Analysis/JumpInstrTableInfo.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Type.h"
+
+using namespace llvm;
+
+INITIALIZE_PASS(JumpInstrTableInfo, "jump-instr-table-info",
+                "Jump-Instruction Table Info", true, true);
+char JumpInstrTableInfo::ID = 0;
+
+ImmutablePass *llvm::createJumpInstrTableInfoPass() {
+  return new JumpInstrTableInfo();
+}
+
+JumpInstrTableInfo::JumpInstrTableInfo()
+  : ImmutablePass(ID),
+  Tables() {
+    initializeJumpInstrTableInfoPass(*PassRegistry::getPassRegistry());
+}
+
+void JumpInstrTableInfo::insertEntry(FunctionType *TableFunTy, Function *Target,
+                                     Function *Jump) {
+  Tables[TableFunTy].push_back(JumpPair(Target, Jump));
+}

lib/AsmParser/LLLexer.cpp

   KEYWORD(cold);
   KEYWORD(inlinehint);
   KEYWORD(inreg);
+  KEYWORD(jumptable);
   KEYWORD(minsize);
   KEYWORD(naked);
   KEYWORD(nest);

lib/AsmParser/LLParser.cpp

     case lltok::kw_builtin:           B.addAttribute(Attribute::Builtin); break;
     case lltok::kw_cold:              B.addAttribute(Attribute::Cold); break;
     case lltok::kw_inlinehint:        B.addAttribute(Attribute::InlineHint); break;
+    case lltok::kw_jumptable:         B.addAttribute(Attribute::JumpTable); break;
     case lltok::kw_minsize:           B.addAttribute(Attribute::MinSize); break;
     case lltok::kw_naked:             B.addAttribute(Attribute::Naked); break;
     case lltok::kw_nobuiltin:         B.addAttribute(Attribute::NoBuiltin); break;

     case lltok::kw_alwaysinline:
     case lltok::kw_builtin:
     case lltok::kw_inlinehint:
+    case lltok::kw_jumptable:
     case lltok::kw_minsize:
     case lltok::kw_naked:
     case lltok::kw_nobuiltin:

     case lltok::kw_builtin:
     case lltok::kw_cold:
     case lltok::kw_inlinehint:
+    case lltok::kw_jumptable:
     case lltok::kw_minsize:
     case lltok::kw_naked:
     case lltok::kw_nobuiltin:

lib/AsmParser/LLToken.h

     kw_cold,
     kw_inlinehint,
     kw_inreg,
+    kw_jumptable,
     kw_minsize,
     kw_naked,
     kw_nest,

lib/Bitcode/Reader/BitcodeReader.cpp

     return Attribute::InlineHint;
   case bitc::ATTR_KIND_IN_REG:
     return Attribute::InReg;
+  case bitc::ATTR_KIND_JUMP_TABLE:
+    return Attribute::JumpTable;
   case bitc::ATTR_KIND_MIN_SIZE:
     return Attribute::MinSize;
   case bitc::ATTR_KIND_NAKED:

lib/Bitcode/Writer/BitcodeWriter.cpp

     return bitc::ATTR_KIND_INLINE_HINT;
   case Attribute::InReg:
     return bitc::ATTR_KIND_IN_REG;
+  case Attribute::JumpTable:
+    return bitc::ATTR_KIND_JUMP_TABLE;
   case Attribute::MinSize:
     return bitc::ATTR_KIND_MIN_SIZE;
   case Attribute::Naked:

lib/CodeGen/AsmPrinter/AsmPrinter.cpp

 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/JumpInstrTableInfo.h"
 #include "llvm/CodeGen/GCMetadataPrinter.h"
 #include "llvm/CodeGen/MachineConstantPool.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"

     }
   }
 
+
+  // Get information about jump-instruction tables to print.
+  JumpInstrTableInfo *JITI = getAnalysisIfAvailable<JumpInstrTableInfo>();
+
+  if (JITI && JITI->getTables().size() > 0) {
+    unsigned Arch = Triple(getTargetTriple()).getArch();
+    bool IsThumb = (Arch == Triple::thumb || Arch == Triple::thumbeb);
+    MCInst TrapInst;
+    TM.getInstrInfo()->getTrap(TrapInst);
+    for (const auto &KV : JITI->getTables()) {
+      uint64_t Count = 0;
+      for (const auto &FunPair : KV.second) {
+        // Emit the function labels to make this be a function entry point.
+        MCSymbol *FunSym =
+          OutContext.GetOrCreateSymbol(FunPair.second->getName());
+        OutStreamer.EmitSymbolAttribute(FunSym, MCSA_Global);
+        // FIXME: JumpTableInstrInfo should store information about the required
+        // alignment of table entries and the size of the padding instruction.
+        EmitAlignment(3);
+        if (IsThumb)
+          OutStreamer.EmitThumbFunc(FunSym);
+        if (MAI->hasDotTypeDotSizeDirective())
+          OutStreamer.EmitSymbolAttribute(FunSym, MCSA_ELF_TypeFunction);
+        OutStreamer.EmitLabel(FunSym);
+
+        // Emit the jump instruction to transfer control to the original
+        // function.
+        MCInst JumpToFun;
+        MCSymbol *TargetSymbol =
+          OutContext.GetOrCreateSymbol(FunPair.first->getName());
+        const MCSymbolRefExpr *TargetSymRef =
+          MCSymbolRefExpr::Create(TargetSymbol, MCSymbolRefExpr::VK_PLT,
+                                  OutContext);
+        TM.getInstrInfo()->getUnconditionalBranch(JumpToFun, TargetSymRef);
+        OutStreamer.EmitInstruction(JumpToFun, getSubtargetInfo());
+        ++Count;
+      }
+
+      // Emit enough padding instructions to fill up to the next power of two.
+      // This assumes that the trap instruction takes 8 bytes or fewer.
+      uint64_t Remaining = NextPowerOf2(Count) - Count;
+      for (uint64_t C = 0; C < Remaining; ++C) {
+        EmitAlignment(3);
+        OutStreamer.EmitInstruction(TrapInst, getSubtargetInfo());
+      }
+
+    }
+  }
+
   GCModuleInfo *MI = getAnalysisIfAvailable<GCModuleInfo>();
   assert(MI && "AsmPrinter didn't require GCModuleInfo?");
   for (GCModuleInfo::iterator I = MI->end(), E = MI->begin(); I != E; )

lib/CodeGen/CMakeLists.txt

   InterferenceCache.cpp
   IntrinsicLowering.cpp
   JITCodeEmitter.cpp
+  JumpInstrTables.cpp
   LLVMTargetMachine.cpp
   LatencyPriorityQueue.cpp
   LexicalScopes.cpp

lib/CodeGen/JumpInstrTables.cpp

+//===- JumpInstrTables.cpp: Jump-Instruction Tables -*- C++ -*-------------===//
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// \brief An implementation of jump-instruction tables.
+///
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "jt"
+
+#include "llvm/CodeGen/JumpInstrTables.h"
+
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/JumpInstrTableInfo.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/Type.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <vector>
+
+using namespace llvm;
+
+char JumpInstrTables::ID = 0;
+
+INITIALIZE_PASS_BEGIN(JumpInstrTables, "jump-instr-tables",
+                      "Jump-Instruction Tables", true, true);
+INITIALIZE_PASS_DEPENDENCY(JumpInstrTableInfo);
+INITIALIZE_PASS_END(JumpInstrTables, "jump-instr-tables",
+                    "Jump-Instruction Tables", true, true);
+
+STATISTIC(NumJumpTables, "Number of indirect call tables generated");
+STATISTIC(NumFuncsInJumpTables, "Number of functions in the jump tables");
+
+ModulePass *llvm::createJumpInstrTablesPass() {
+  return new JumpInstrTables();
+}
+
+namespace {
+/// Different versions of jump tables, as used by the command-line parameter
+/// JumpTableType.
+enum JumpTableTypes { jump_single_table, jump_arity_table,
+  jump_simplified_type_table, jump_full_type_table };
+
+static const char jump_func_prefix[] = "__llvm_jump_instr_table_";
+static const char jump_section_prefix[] = ".jump.instr.table.text.";
+
+/// The algorithm used to split up tables by type
+static cl::opt<JumpTableTypes>
+JumpTableType(cl::desc("Function jump table type:"),
+              cl::values(clEnumVal(jump_single_table,
+                                   "A single table for all indirect calls"),
+                         clEnumVal(jump_arity_table,
+                                   "One table per number of parameters"),
+                         clEnumVal(jump_simplified_type_table,
+                                   "One table per function type with types"
+                                   " projected into: pointer to non-function,"
+                                   " struct, primitive, and function pointer"),
+                         clEnumVal(jump_full_type_table,
+                                   "One table per function type"),
+                         clEnumValEnd));
+
+// Checks to see if a given CallSite is making an indirect call, including
+// cases where the indirect call is made through a bitcast.
+bool isIndirectCall(CallSite &CS) {
+  if (CS.getCalledFunction())
+    return false;
+
+  // Check the value to see if it is merely a bitcast of a function. In
+  // this case, it will translate to a direct function call in the resulting
+  // assembly, so we won't treat it as an indirect call here.
+  const Value *V = CS.getCalledValue();
+  if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
+    return !(CE->isCast() && isa<Function>(CE->getOperand(0)));
+  }
+
+  // Otherwise, since we know it's a call, it must be an indirect call
+  return true;
+}
+
+// Replaces Functions and GlobalAliases with a different Value.
+bool replaceGlobalValueIndirectUse(GlobalValue *GV, Value *V, Use *U) {
+  User *Us = U->getUser();
+  if (!Us)
+    return false;
+  if (Instruction *I = dyn_cast<Instruction>(Us)) {
+    CallSite CS(I);
+
+    // Don't do the replacement if this use is a direct call to this function.
+    // If the use is not the called value, then replace it.
+    if (CS && (isIndirectCall(CS) || CS.isCallee(U))) {
+      return false;
+    }
+
+    U->set(V);
+  } else if (Constant *C = dyn_cast<Constant>(Us)) {
+    // Don't replace calls to bitcasts of function symbols, since they get
+    // translated to direct calls.
+    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Us)) {
+      if (CE->getOpcode() == Instruction::BitCast) {
+        // This bitcast must have exactly one user.
+        if (CE->user_begin() != CE->user_end()) {
+          User *ParentUs = *CE->user_begin();
+          if (CallInst *CI = dyn_cast<CallInst>(ParentUs)) {
+            CallSite CS(CI);
+            Use &CEU = *CE->use_begin();
+            if (CS.isCallee(&CEU)) {
+              return false;
+            }
+          }
+        }
+      }
+    }
+
+    // GlobalAlias doesn't support replaceUsesOfWithOnConstant. And the verifier
+    // requires alias to point to a defined function. So, GlobalAlias is handled
+    // as a separate case in runOnModule.
+    if (!isa<GlobalAlias>(C))
+      C->replaceUsesOfWithOnConstant(GV, V, U);
+  } else {
+    assert(false && "The Use of a Function symbol is neither an instruction nor"
+           " a constant");
+  }
+
+  return true;
+}
+
+// Replaces all replaceable address-taken uses of GV with a pointer to a
+// jump-instruction table entry.
+void replaceValueWithFunction(GlobalValue *GV, Function *F) {
+  // Go through all uses of this function and replace the uses of GV with the
+  // jump-table version of the function. Get the uses as a vector before
+  // replacing them, since replacing them changes the use list and invalidates
+  // the iterator otherwise.
+  Value::use_iterator I, E;
+  for (I = GV->use_begin(), E = GV->use_end(); I != E;) {
+    Use &U = *I++;
+
+    // Replacement of constants replaces all instances in the constant. So, some
+    // uses might have already been handled by the time we reach them here.
+    if (U.get() == GV)
+      replaceGlobalValueIndirectUse(GV, F, &U);
+  }
+
+  return;
+}
+} // end anonymous namespace
+
+JumpInstrTables::JumpInstrTables()
+  : ModulePass(ID),
+  Metadata(),
+  JITI(nullptr),
+  TableCount(0) {
+  initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry());
+}
+
+void JumpInstrTables::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<JumpInstrTableInfo>();
+}
+
+Function *JumpInstrTables::insertEntry(Module &M, Function *Target) {
+  FunctionType *OrigFunTy = Target->getFunctionType();
+  FunctionType *FunTy = transformType(OrigFunTy);
+
+  JumpMap::iterator it = Metadata.find(FunTy);
+  if (Metadata.end() == it) {
+    TableMetadata Meta;
+    Meta.TableNum = TableCount;
+    Meta.Count = 0;
+    Metadata[FunTy] = Meta;
+    it = Metadata.find(FunTy);
+    ++NumJumpTables;
+    ++TableCount;
+  }
+
+  it->second.Count++;
+
+  Twine NewName = jump_func_prefix + Twine(it->second.TableNum) + "_"
+      + Twine(it->second.Count);
+  Function *JumpFun = Function::Create(OrigFunTy, GlobalValue::ExternalLinkage,
+                                       NewName.str(), &M);
+  // The section for this table
+  JumpFun->setSection((jump_section_prefix + Twine(it->second.TableNum)).str());
+  JITI->insertEntry(FunTy, Target, JumpFun);
+
+  ++NumFuncsInJumpTables;
+  return JumpFun;
+}
+
+bool JumpInstrTables::hasTable(FunctionType *FunTy) {
+  FunctionType *TransTy = transformType(FunTy);
+  JumpMap::iterator it = Metadata.find(TransTy);
+  return Metadata.end() != it;
+}
+
+FunctionType *JumpInstrTables::transformType(FunctionType *FunTy) {
+  // Returning nullptr forces all types into the same table, since all types map
+  // to the same type
+  Type *VoidPtrTy = Type::getInt8PtrTy(FunTy->getContext());
+
+  // Ignore the return type.
+  Type *RetTy = VoidPtrTy;
+  bool IsVarArg = FunTy->isVarArg();
+  std::vector<Type *> ParamTys(FunTy->getNumParams());
+  FunctionType::param_iterator PI, PE;
+  int i = 0;
+
+  std::vector<Type *> EmptyParams;
+  Type *Int32Ty = Type::getInt32Ty(FunTy->getContext());
+  FunctionType *VoidFnTy = FunctionType::get(
+      Type::getVoidTy(FunTy->getContext()), EmptyParams, false);
+  switch (JumpTableType) {
+  case jump_single_table:
+
+    return FunctionType::get(RetTy, EmptyParams, false);
+  case jump_arity_table:
+    // Transform all types to void* so that all functions with the same arity
+    // end up in the same table.
+    for (PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE;
+         PI++, i++) {
+      ParamTys[i] = VoidPtrTy;
+    }
+
+    return FunctionType::get(RetTy, ParamTys, IsVarArg);
+  case jump_simplified_type_table:
+    // Project all parameters types to one of 3 types: composite, integer, and
+    // function, matching the three subclasses of Type.
+    for(PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE;
+        ++PI, ++i) {
+      assert((isa<IntegerType>(*PI) || isa<FunctionType>(*PI) ||
+              isa<CompositeType>(*PI)) && "This type is not an Integer or a"
+             " Composite or a Function");
+      if (isa<CompositeType>(*PI)) {
+        ParamTys[i] = VoidPtrTy;
+      } else if (isa<FunctionType>(*PI)) {
+        ParamTys[i] = VoidFnTy;
+      } else if (isa<IntegerType>(*PI)) {
+        ParamTys[i] = Int32Ty;
+      }
+    }
+
+    return FunctionType::get(RetTy, ParamTys, IsVarArg);
+  case jump_full_type_table:
+    // Don't transform this type at all.
+    return FunTy;
+  }
+
+  return nullptr;
+}
+
+bool JumpInstrTables::runOnModule(Module &M) {
+  JITI = &getAnalysis<JumpInstrTableInfo>();
+
+  // Get all the functions that have their address taken, and compute the
+  // size of a table needed to hold all these functions.
+  //
+  // Get the set of address taken functions and all the types they represent,
+  // including all incoming external functions.
+  DenseMap<Function *, Function *> Functions;
+  for (Function &F : M) {
+    if (F.hasFnAttribute(Attribute::JumpTable)) {
+      Functions[&F] = NULL;
+    }
+  }
+
+  // Create the jump-table functions.
+  for (auto &KV : Functions) {
+    Function *F = KV.first;
+    KV.second = insertEntry(M, F);
+  }
+
+  // GlobalAlias is a special case, because the target of an alias statement
+  // must be a defined function. So, instead of replacing a given function in
+  // the alias, we replace all uses of aliases that target jumptable functions.
+  // Note that there's no need to create these functions, since only aliases
+  // that target known jumptable functions are replaced, and there's no way to
+  // put the jumptable annotation on a global alias.
+  DenseMap<GlobalAlias *, Function *> Aliases;
+  for (GlobalAlias &GA : M.aliases()) {
+    Constant *Aliasee = GA.getAliasee();
+    if (Function *F = dyn_cast<Function>(Aliasee)) {
+      auto it = Functions.find(F);
+      if (it != Functions.end()) {
+        Aliases[&GA] = it->second;
+      }
+    }
+  }
+
+  // Replace each address taken function with its jump-instruction table entry.
+  for (auto &KV : Functions)
+    replaceValueWithFunction(KV.first, KV.second);
+
+  for (auto &KV : Aliases)
+    replaceValueWithFunction(KV.first, KV.second);
+
+  return !Functions.empty();
+}

lib/CodeGen/LLVMTargetMachine.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Target/TargetMachine.h"
+
+#include "llvm/Analysis/Passes.h"
 #include "llvm/CodeGen/AsmPrinter.h"
 #include "llvm/CodeGen/MachineFunctionAnalysis.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"

 AsmVerbose("asm-verbose", cl::desc("Add comments to directives."),
            cl::init(cl::BOU_UNSET));
 
+static cl::opt<bool>
+BuildJumpInstrTables(
+    "build-jump-instr-tables", cl::Hidden, cl::init(false),
+    cl::desc("Build jump-instruction tables for address-taken functions"));
+
 static bool getVerboseAsm() {
   switch (AsmVerbose) {
   case cl::BOU_UNSET: return TargetMachine::getAsmVerbosityDefault();

                                           bool DisableVerify,
                                           AnalysisID StartAfter,
                                           AnalysisID StopAfter) {
+  // Always create the empty jump-instruction table info.
+  PM.add(createJumpInstrTableInfoPass());
+  if (BuildJumpInstrTables)
+    PM.add(createJumpInstrTablesPass());
+
   // Add internal analysis passes from the target machine.
   TM->addAnalysisPasses(PM);
 

lib/IR/Attributes.cpp

     return "inlinehint";
   if (hasAttribute(Attribute::InReg))
     return "inreg";
+  if (hasAttribute(Attribute::JumpTable))
+    return "jumptable";
   if (hasAttribute(Attribute::MinSize))
     return "minsize";
   if (hasAttribute(Attribute::Naked))

   case Attribute::Builtin:         return 1ULL << 41;
   case Attribute::OptimizeNone:    return 1ULL << 42;
   case Attribute::InAlloca:        return 1ULL << 43;
+  case Attribute::JumpTable:       return 1ULL << 44;
   }
   llvm_unreachable("Unsupported attribute type");
 }

lib/IR/Verifier.cpp

         I->getKindAsEnum() == Attribute::Builtin ||
         I->getKindAsEnum() == Attribute::NoBuiltin ||
         I->getKindAsEnum() == Attribute::Cold ||
-        I->getKindAsEnum() == Attribute::OptimizeNone) {
+        I->getKindAsEnum() == Attribute::OptimizeNone ||
+        I->getKindAsEnum() == Attribute::JumpTable) {
       if (!isFunction) {
         CheckFailed("Attribute '" + I->getAsString() +
                     "' only applies to functions!", V);

lib/LTO/LTOCodeGenerator.cpp

   initializeConstantMergePass(R);
   initializeDAHPass(R);
   initializeInstCombinerPass(R);
+  initializeJumpInstrTablesPass(R);
   initializeSimpleInlinerPass(R);
   initializePruneEHPass(R);
   initializeGlobalDCEPass(R);

lib/Target/ARM/ARMBaseInstrInfo.h

                                       const TargetRegisterInfo*) const override;
   void breakPartialRegDependency(MachineBasicBlock::iterator, unsigned,
                                  const TargetRegisterInfo *TRI) const override;
+
+  void
+  getUnconditionalBranch(MCInst &Branch,
+                         const MCSymbolRefExpr *BranchTarget) const override;
+
+  void getTrap(MCInst &MI) const override;
+
   /// Get the number of addresses by LDM or VLDM or zero for unknown.
   unsigned getNumLDMAddresses(const MachineInstr *MI) const;
 

lib/Target/ARM/ARMBaseInstrInfo.cpp

 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCExpr.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"

   MI->addRegisterKilled(DReg, TRI, true);
 }
 
+void ARMBaseInstrInfo::
+getUnconditionalBranch(MCInst &Branch,
+                       const MCSymbolRefExpr *BranchTarget) const {
+  if (Subtarget.isThumb())
+    Branch.setOpcode(ARM::tBcc);
+  else if (Subtarget.isThumb2())
+    Branch.setOpcode(ARM::t2Bcc);
+  else
+    Branch.setOpcode(ARM::Bcc);
+  Branch.addOperand(MCOperand::CreateExpr(BranchTarget));
+  Branch.addOperand(MCOperand::CreateImm(ARMCC::AL));
+  Branch.addOperand(MCOperand::CreateReg(0));
+}
+
+void ARMBaseInstrInfo::getTrap(MCInst &MI) const {
+  if (Subtarget.isThumb())
+    MI.setOpcode(ARM::tTRAP);
+  else if (Subtarget.useNaClTrap())
+    MI.setOpcode(ARM::TRAPNaCl);
+  else
+    MI.setOpcode(ARM::TRAP);
+}
+
 bool ARMBaseInstrInfo::hasNOP() const {
   return (Subtarget.getFeatureBits() & ARM::HasV6T2Ops) != 0;
 }

lib/Target/X86/X86InstrInfo.h

                                       const SmallVectorImpl<MachineOperand> &MOs,
                                       unsigned Size, unsigned Alignment) const;
 
+  void
+  getUnconditionalBranch(MCInst &Branch,
+                         const MCSymbolRefExpr *BranchTarget) const override;
+
+  void getTrap(MCInst &MI) const override;
+
   bool isHighLatencyDef(int opc) const override;
 
   bool hasHighOperandLatency(const InstrItineraryData *ItinData,

lib/Target/X86/X86InstrInfo.cpp

 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCExpr.h"
 #include "llvm/MC/MCInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"

   NopInst.setOpcode(X86::NOOP);
 }
 
+void X86InstrInfo::getUnconditionalBranch(
+    MCInst &Branch, const MCSymbolRefExpr *BranchTarget) const {
+  Branch.setOpcode(X86::JMP_4);
+  Branch.addOperand(MCOperand::CreateExpr(BranchTarget));
+}
+
+void X86InstrInfo::getTrap(MCInst &MI) const {
+  MI.setOpcode(X86::TRAP);
+}
+
 bool X86InstrInfo::isHighLatencyDef(int opc) const {
   switch (opc) {
   default: return false;

lib/Transforms/IPO/IPO.cpp

   initializeGlobalDCEPass(Registry);
   initializeGlobalOptPass(Registry);
   initializeIPCPPass(Registry);
+  initializeJumpInstrTablesPass(Registry);
   initializeAlwaysInlinerPass(Registry);
   initializeSimpleInlinerPass(Registry);
   initializeInternalizePassPass(Registry);

test/Bitcode/attributes.ll

 ; CHECK: define void @f34()
 {
         call void @nobuiltin() nobuiltin
-; CHECK: call void @nobuiltin() #24
+; CHECK: call void @nobuiltin() #25
         ret void;
 }
 

         ret void
 }
 
+define void @f37() jumptable {
+; CHECK: define void @f37() #24
+    call void bitcast (void (i8*)* @f36 to void ()*)()
+    unreachable
+}
+
 ; CHECK: attributes #0 = { noreturn }
 ; CHECK: attributes #1 = { nounwind }
 ; CHECK: attributes #2 = { readnone }

 ; CHECK: attributes #21 = { sspstrong }
 ; CHECK: attributes #22 = { minsize }
 ; CHECK: attributes #23 = { noinline optnone }
-; CHECK: attributes #24 = { nobuiltin }
-
+; CHECK: attributes #24 = { jumptable }
+; CHECK: attributes #25 = { nobuiltin }

test/CodeGen/ARM/jump_tables.ll

+; RUN: llc -build-jump-instr-tables <%s -march=arm -jump_single_table | FileCheck --check-prefix=ARM %s
+; RUN: llc -build-jump-instr-tables <%s -march=thumb -jump_single_table | FileCheck --check-prefix=THUMB %s
+
+define void @indirect_fun() jumptable {
+  ret void
+}
+define void ()* @get_fun() {
+  ret void ()* @indirect_fun
+
+; ARM:         ldr     r0, [[LABEL:.*]]
+; ARM:         mov     pc, lr
+; ARM: [[LABEL]]:
+; ARM:         .long   __llvm_jump_instr_table_0_1
+
+; THUMB:         ldr     r0, [[LABEL:.*]]
+; THUMB:         bx      lr
+; THUMB: [[LABEL]]:
+; THUMB:         .long   __llvm_jump_instr_table_0_1
+}
+
+; ARM:         .globl  __llvm_jump_instr_table_0_1
+; ARM:         .align  3
+; ARM:         .type   __llvm_jump_instr_table_0_1,%function
+; ARM: __llvm_jump_instr_table_0_1:
+; ARM:         b     indirect_fun(PLT)
+
+; THUMB:         .globl  __llvm_jump_instr_table_0_1
+; THUMB:         .align  3
+; THUMB:         .thumb_func
+; THUMB:         .type   __llvm_jump_instr_table_0_1,%function
+; THUMB: __llvm_jump_instr_table_0_1:
+; THUMB:         b     indirect_fun(PLT)

test/CodeGen/X86/jump_table_alias.ll

+; RUN: llc -build-jump-instr-tables <%s -jump_single_table | FileCheck %s
+target triple = "x86_64-unknown-linux-gnu"
+define i32 @f() jumptable {
+entry:
+  ret i32 0
+}
+
+@i = alias internal i32 ()* @f
+@j = alias i32 ()* @f
+
+define i32 @main(i32 %argc, i8** %argv) {
+  %temp = alloca i32 ()*, align 8
+  store i32 ()* @i, i32()** %temp, align 8
+; CHECK: movq    $__llvm_jump_instr_table_0_1
+  %1 = load i32 ()** %temp, align 8
+; CHECK: movl    $__llvm_jump_instr_table_0_1
+  %2 = call i32 ()* %1()
+  %3 = call i32 ()* @i()
+; CHECK: callq   i
+  %4 = call i32 ()* @j()
+; CHECK: callq   j
+  ret i32 %3
+}
+
+; There should only be one table, even though there are two GlobalAliases,
+; because they both alias the same value.
+
+; CHECK:         .globl  __llvm_jump_instr_table_0_1
+; CHECK:         .align  8, 0x90
+; CHECK:         .type   __llvm_jump_instr_table_0_1,@function
+; CHECK: __llvm_jump_instr_table_0_1:
+; CHECK:         jmp     f@PLT
+

test/CodeGen/X86/jump_table_bitcast.ll

+; RUN: llc -build-jump-instr-tables <%s -jump_single_table | FileCheck %s
+target triple = "x86_64-unknown-linux-gnu"
+define i32 @f() jumptable {
+  ret i32 0
+}
+
+define i32 @g(i8* %a) jumptable {
+  ret i32 0
+}
+
+define void @h(void ()* %func) jumptable {
+  ret void
+}
+
+define i32 @main() {
+  %g = alloca i32 (...)*, align 8
+  store i32 (...)* bitcast (i32 ()* @f to i32 (...)*), i32 (...)** %g, align 8
+; CHECK: movq    $__llvm_jump_instr_table_0_[[ENTRY:1|2|3]], (%rsp)
+; CHECK: movl    $__llvm_jump_instr_table_0_[[ENTRY]], %ecx
+  %1 = load i32 (...)** %g, align 8
+  %call = call i32 (...)* %1()
+  call void (void ()*)* @h(void ()* bitcast (void (void ()*)* @h to void ()*))
+; CHECK: movl    $__llvm_jump_instr_table_0_{{1|2|3}}, %edi
+; CHECK: callq   h
+
+  %a = call i32 (i32*)* bitcast (i32 (i8*)* @g to i32(i32*)*)(i32* null)
+; CHECK: callq g
+  ret i32 %a
+}
+
+; CHECK:         .globl  __llvm_jump_instr_table_0_1
+; CHECK:         .align  8, 0x90
+; CHECK:         .type   __llvm_jump_instr_table_0_1,@function
+; CHECK: __llvm_jump_instr_table_0_1:
+; CHECK:         jmp     {{f|g|h}}@PLT
+; CHECK:         .globl  __llvm_jump_instr_table_0_2
+; CHECK:         .align  8, 0x90
+; CHECK:         .type   __llvm_jump_instr_table_0_2,@function
+; CHECK: __llvm_jump_instr_table_0_2:
+; CHECK:         jmp     {{f|g|h}}@PLT
+; CHECK:         .globl  __llvm_jump_instr_table_0_3
+; CHECK:         .align  8, 0x90
+; CHECK:         .type   __llvm_jump_instr_table_0_3,@function
+; CHECK: __llvm_jump_instr_table_0_3:
+; CHECK:         jmp     {{f|g|h}}@PLT
+

test/CodeGen/X86/jump_tables.ll

+; RUN: llc -build-jump-instr-tables <%s -jump_single_table | FileCheck --check-prefix=SINGLE %s
+; RUN: llc -build-jump-instr-tables <%s -jump_arity_table | FileCheck --check-prefix=ARITY %s
+; RUN: llc -build-jump-instr-tables <%s -jump_simplified_type_table | FileCheck --check-prefix=SIMPL %s
+; RUN: llc -build-jump-instr-tables <%s -jump_full_type_table | FileCheck --check-prefix=FULL %s
+; RUN: llc <%s | FileCheck --check-prefix=NONE %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.fun_struct = type { i32 (...)* }
+
+define void @indirect_fun() jumptable {
+  ret void
+}
+
+define void @indirect_fun_match() jumptable {
+  ret void
+}
+
+define i32 @indirect_fun_i32() jumptable {
+  ret i32 0
+}
+
+define i32 @indirect_fun_i32_1(i32 %a) jumptable {
+  ret i32 %a
+}
+
+define i32 @indirect_fun_i32_2(i32 %a, i32 %b) jumptable {
+  ret i32 %a
+}
+
+define i32* @indirect_fun_i32S_2(i32* %a, i32 %b) jumptable {
+  ret i32* %a
+}
+
+define void @indirect_fun_struct(%struct.fun_struct %fs) jumptable {
+  ret void
+}
+
+define void @indirect_fun_fun(i32 (...)* %fun, i32 %a) jumptable {
+  ret void
+}
+
+define i32 @indirect_fun_fun_ret(i32 (...)* %fun, i32 %a) jumptable {
+  ret i32 %a
+}
+
+define void @indirect_fun_array([19 x i8] %a) jumptable {
+  ret void
+}
+
+define void @indirect_fun_vec(<3 x i32> %a) jumptable {
+  ret void
+}
+
+define void @indirect_fun_vec_2(<4 x float> %a) jumptable {
+  ret void
+}
+
+define i32 @m(void ()* %fun) {
+  call void ()* %fun()
+  ret i32 0
+}
+
+define void ()* @get_fun() {
+  ret void ()* @indirect_fun
+; SINGLE: movl    $__llvm_jump_instr_table_0_
+; ARITY: movl    $__llvm_jump_instr_table_
+; SIMPL: movl    $__llvm_jump_instr_table_
+; FULL: movl    $__llvm_jump_instr_table_
+}
+
+define i32 @main(i32 %argc, i8** %argv) {
+  %f = call void ()* ()* @get_fun()
+  %a = call i32 @m(void ()* %f)
+  ret i32 %a
+}
+
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_1
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_1,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_1:
+; SINGLE-DAG:         jmp     indirect_fun_array@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_2
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_2,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_2:
+; SINGLE-DAG:         jmp     indirect_fun_i32_2@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_3
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_3,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_3:
+; SINGLE-DAG:         jmp     indirect_fun_vec_2@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_4
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_4,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_4:
+; SINGLE-DAG:         jmp     indirect_fun_i32S_2@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_5
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_5,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_5:
+; SINGLE-DAG:         jmp     indirect_fun_struct@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_6
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_6,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_6:
+; SINGLE-DAG:         jmp     indirect_fun_i32_1@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_7
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_7,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_7:
+; SINGLE-DAG:         jmp     indirect_fun_i32@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_8
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_8,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_8:
+; SINGLE-DAG:         jmp     indirect_fun_fun@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_9
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_9,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_9:
+; SINGLE-DAG:         jmp     indirect_fun_fun_ret@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_10
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_10,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_10:
+; SINGLE-DAG:         jmp     indirect_fun@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_11
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_11,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_11:
+; SINGLE-DAG:         jmp     indirect_fun_match@PLT
+; SINGLE-DAG:         .globl  __llvm_jump_instr_table_0_12
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         .type   __llvm_jump_instr_table_0_12,@function
+; SINGLE-DAG: __llvm_jump_instr_table_0_12:
+; SINGLE-DAG:         jmp     indirect_fun_vec@PLT
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         ud2
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         ud2
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         ud2
+; SINGLE-DAG:         .align  8, 0x90
+; SINGLE-DAG:         ud2
+
+
+; ARITY-DAG:         .globl  __llvm_jump_instr_table_2_1
+; ARITY-DAG:         .align  8, 0x90
+; ARITY-DAG:         .type   __llvm_jump_instr_table_2_1,@function
+; ARITY-DAG: __llvm_jump_instr_table_2_1:
+; ARITY-DAG:         jmp     indirect_fun{{.*}}@PLT
+; ARITY-DAG:         .align  8, 0x90
+; ARITY-DAG:         ud2
+; ARITY-DAG:         .globl  __llvm_jump_instr_table_0_1
+; ARITY-DAG:         .align  8, 0x90
+; ARITY-DAG:         .type   __llvm_jump_instr_table_0_1,@function
+; ARITY-DAG: __llvm_jump_instr_table_0_1:
+; ARITY-DAG:         jmp     indirect_fun{{.*}}@PLT
+; ARITY-DAG:         .globl  __llvm_jump_instr_table_1_1
+; ARITY-DAG:         .align  8, 0x90
+; ARITY-DAG:         .type   __llvm_jump_instr_table_1_1,@function
+; ARITY-DAG: __llvm_jump_instr_table_1_1:
+; ARITY-DAG:         jmp     indirect_fun{{.*}}@PLT
+
+; SIMPL-DAG:         .globl  __llvm_jump_instr_table_2_1
+; SIMPL-DAG:         .align  8, 0x90
+; SIMPL-DAG:         .type   __llvm_jump_instr_table_2_1,@function
+; SIMPL-DAG: __llvm_jump_instr_table_2_1:
+; SIMPL-DAG:         jmp     indirect_fun{{.*}}@PLT
+; SIMPL-DAG:         .align  8, 0x90
+; SIMPL-DAG:         ud2
+; SIMPL-DAG:         .globl  __llvm_jump_instr_table_0_1
+; SIMPL-DAG:         .align  8, 0x90
+; SIMPL-DAG:         .type   __llvm_jump_instr_table_0_1,@function
+; SIMPL-DAG: __llvm_jump_instr_table_0_1:
+; SIMPL-DAG:         jmp     indirect_fun{{.*}}@PLT
+; SIMPL-DAG:         .globl  __llvm_jump_instr_table_1_1
+; SIMPL-DAG:         .align  8, 0x90
+; SIMPL-DAG:         .type   __llvm_jump_instr_table_1_1,@function
+; SIMPL-DAG: __llvm_jump_instr_table_1_1:
+; SIMPL-DAG:         jmp     indirect_fun{{.*}}@PLT
+; SIMPL-DAG:         .globl  __llvm_jump_instr_table_3_1
+; SIMPL-DAG:         .align  8, 0x90
+; SIMPL-DAG:         .type   __llvm_jump_instr_table_3_1,@function
+; SIMPL-DAG: __llvm_jump_instr_table_3_1:
+; SIMPL-DAG:         jmp     indirect_fun{{.*}}@PLT
+; SIMPL-DAG:         .globl  __llvm_jump_instr_table_4_1
+; SIMPL-DAG:         .align  8, 0x90
+; SIMPL-DAG:         .type   __llvm_jump_instr_table_4_1,@function
+; SIMPL-DAG: __llvm_jump_instr_table_4_1:
+; SIMPL-DAG:         jmp     indirect_fun{{.*}}@PLT
+
+
+; FULL-DAG:        .globl  __llvm_jump_instr_table_10_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_10_1,@function
+; FULL-DAG:__llvm_jump_instr_table_10_1:
+; FULL-DAG:        jmp     indirect_fun_i32_1@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_9_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_9_1,@function
+; FULL-DAG:__llvm_jump_instr_table_9_1:
+; FULL-DAG:        jmp     indirect_fun_i32_2@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_7_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_7_1,@function
+; FULL-DAG:__llvm_jump_instr_table_7_1:
+; FULL-DAG:        jmp     indirect_fun_i32S_2@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_3_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_3_1,@function
+; FULL-DAG:__llvm_jump_instr_table_3_1:
+; FULL-DAG:        jmp     indirect_fun_vec_2@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_2_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_2_1,@function
+; FULL-DAG:__llvm_jump_instr_table_2_1:
+; FULL-DAG:        jmp     indirect_fun@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_8_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_8_1,@function
+; FULL-DAG:__llvm_jump_instr_table_8_1:
+; FULL-DAG:        jmp     indirect_fun_i32@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_1_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_1_1,@function
+; FULL-DAG:__llvm_jump_instr_table_1_1:
+; FULL-DAG:        jmp     indirect_fun_array@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_0_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_0_1,@function
+; FULL-DAG:__llvm_jump_instr_table_0_1:
+; FULL-DAG:        jmp     indirect_fun_vec@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_6_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_6_1,@function
+; FULL-DAG:__llvm_jump_instr_table_6_1:
+; FULL-DAG:        jmp     indirect_fun_struct@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_5_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_5_1,@function
+; FULL-DAG:__llvm_jump_instr_table_5_1:
+; FULL-DAG:        jmp     indirect_fun_fun@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+; FULL-DAG:        .globl  __llvm_jump_instr_table_4_1
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        .type   __llvm_jump_instr_table_4_1,@function
+; FULL-DAG:__llvm_jump_instr_table_4_1:
+; FULL-DAG:        jmp     indirect_fun_fun_ret@PLT
+; FULL-DAG:        .align  8, 0x90
+; FULL-DAG:        ud2
+
+; NONE-NOT: __llvm_jump_instr_table
+; NONE-NOT: ud2