Add a jumptable attribute + intrinsic + IR transform for jump-instruction tables

[tmroeder]

Summary

Here's a patch that implements the version of jump-instruction tables that I have been discussing on llvmdev.

It adds:

• a jumptable function attribute that maps to a jumptable entry in a special section
• an intrinsic llvm.jumptable_jump that can only occur as the sole instruction in a jumptable function
• a JumpInstrTables pass that converts address-taken functions to pass through a jump-instruction table
• codegen support + X86 backend support for lowering the intrinsic to a simple jmp f@PLT instruction
• some basic tests of the functionality

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/ISDOpcodes.h

     /// It produces a token chain as output.
     INIT_TRAMPOLINE,
 
+    /// JUMPTABLE_JUMP - This corresponds to the jumptable_jump
+    /// intrinsic. It defines an entry in a jump instruction table. It takes as
+    /// input a pointer to the original function.
+    JUMPTABLE_JUMP,
+
     /// ADJUST_TRAMPOLINE - This corresponds to the adjust_trampoline intrinsic.
     /// It takes a pointer to the trampoline and produces a (possibly) new
     /// pointer to the same trampoline with platform-specific adjustments

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/IR/Intrinsics.td

 def int_clear_cache : Intrinsic<[], [llvm_ptr_ty, llvm_ptr_ty],
                                 [], "llvm.clear_cache">;
 
+// This intrinsic supports the target-independent part of jump-instruction
+// tables. The sole argument is the function to jump to. This intrinsic can only
+// appear as the sole reachable instruction in a function with the jumptable
+// attribute, and any function with the jumptable attribute must have such a
+// call. It maps to an unconditional branch to its argument.
+def int_jumptable_jump : Intrinsic<[], [llvm_ptr_ty],
+                                   [IntrNoReturn, ReadOnly<0>],
+                                   "llvm.jumptable_jump">;
+
 //===----------------------------------------------------------------------===//
 // Target-specific intrinsics
 //===----------------------------------------------------------------------===//

include/llvm/InitializePasses.h

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

include/llvm/Transforms/IPO/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_TRANSFORMS_IPO_JUMPINSTRTABLES_H
+#define LLVM_TRANSFORMS_IPO_JUMPINSTRTABLES_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+class Constant;
+class Function;
+class FunctionType;
+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 their
+/// taken. For each such function, it creates a new jump-instruction-table
+/// function with the jumptableentry attribute (and noreturn naked optnone
+/// noinline align 8, and a section directive that maps it to the right table).
+///
+/// The calls in these special functions get lowered to jump instructions in
+/// CodeGen.
+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"; }
+
+  /// Inserts Target->JumpFun in the map and add assembly to the table for this
+  /// function type.
+  Function *insertEntry(Module &M, Function *Target);
+
+  /// Goes through each table and fills it out to a power-of-two size and
+  /// creates new Values that represent the start of each table and the mask for
+  /// each table. This method also adds the resulting tables as module asm.
+  void finishTables(Module &M);
+
+  /// Checks to see if there is already a table for the given FunctionType.
+  bool hasTable(FunctionType *FunTy);
+
+  /// Gets the base of a table associated with a given function type.
+  Constant *getStart(FunctionType *FunTy);
+
+  /// Gets the mask of a table associated with a given function type.
+  Constant *getMask(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;
+
+    // The first jump function inserted in the table.
+    Function *FirstFunction;
+
+    // The first function symbol in the table.
+    Constant *Start;
+
+    // The mask for the table.
+    Constant *Mask;
+  } TableMetadata;
+
+  typedef DenseMap<FunctionType *, TableMetadata> JumpMap;
+
+  /// Replaces all specific pointers with i8* for the purposes of method
+  /// signatures. This overapproximates the class hierarchy for the purposes of
+  /// making virtual function pointers fall in the right tables.
+  FunctionType *transformType(FunctionType *FunTy);
+
+  /// The current state of functions and jump entries in the table(s).
+  JumpMap Metadata;
+
+  /// The total number of tables
+  unsigned TableCount;
+};
+
+ModulePass *createJumpInstrTablesPass();
+}
+
+#endif /* LLVM_TRANSFORMS_IPO_JUMPINSTRTABLES_H */

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/SelectionDAG/LegalizeDAG.cpp

     if (Action == TargetLowering::Legal)
       Action = TargetLowering::Expand;
     break;
+  case ISD::JUMPTABLE_JUMP:
   case ISD::INIT_TRAMPOLINE:
   case ISD::ADJUST_TRAMPOLINE:
   case ISD::FRAMEADDR:

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

   case Intrinsic::var_annotation:
     // Discard annotate attributes
     return 0;
+  case Intrinsic::jumptable_jump: {
+    SDValue Ops[2];
+    Ops[0] = getRoot();
+    Ops[1] = getValue(I.getArgOperand(0)->stripPointerCasts());
+
+    Res = DAG.getNode(ISD::JUMPTABLE_JUMP, sdl, MVT::Other, Ops, 2);
 
+    DAG.setRoot(Res);
+    return 0;
+  }
   case Intrinsic::init_trampoline: {
     const Function *F = cast<Function>(I.getArgOperand(1)->stripPointerCasts());
 

lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

   case ISD::BR_CC:                      return "br_cc";
   case ISD::CALLSEQ_START:              return "callseq_start";
   case ISD::CALLSEQ_END:                return "callseq_end";
+  case ISD::JUMPTABLE_JUMP:             return "jumptable_jump";
 
     // Other operators
   case ISD::LOAD:                       return "load";

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

       Assert1(!BlockAddress::lookup(Entry)->isConstantUsed(),
               "blockaddress may not be used with the entry block!", Entry);
     }
+
+    if (Attrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::JumpTable)) {
+      // Jump-instruction tables can only have a single basic block with a
+      // single call instruction in them, followed by unreachable. And that call
+      // instruction must also have the jumptable attribute set.
+      Assert1(F.size() == 1,
+              "A jumptable function can only have one basic block", &F);
+      Assert1(Entry->size() == 2,
+              "A jumptable function must have exactly two instructions",
+              Entry);
+      Assert1(F.getSection() != ".text",
+              "A jumptable function cannot be in the .text section", &F);
+
+      const Instruction &CI = Entry->front();
+      Assert1(isa<CallInst>(CI),
+              "The first instruction in a jumptable function must be a call",
+              &F);
+
+      const Instruction &UnI = Entry->back();
+      Assert1(
+          isa<UnreachableInst>(UnI),
+          "The second instruction in a jumptable function must be unreachable",
+          &F);
+    }
   }
 
   // If this function is actually an intrinsic, verify that it is only used in

             "llvm.init_trampoline parameter #2 must resolve to a function.",
             &CI);
     break;
+  case Intrinsic::jumptable_jump:
+    // FIXME: make sure this instruction is the only instruction in a jumptable
+    // function.
+    Assert1(isa<Function>(CI.getArgOperand(0)->stripPointerCasts()),
+            "llvm.jump_instr_table_entry parameter must resolve to a function.",
+            &CI);
+    break;
   case Intrinsic::prefetch:
     Assert1(isa<ConstantInt>(CI.getArgOperand(1)) &&
             isa<ConstantInt>(CI.getArgOperand(2)) &&

lib/LTO/LTOCodeGenerator.cpp

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

lib/Target/X86/X86ISelDAGToDAG.cpp

       Parent->getOpcode() != ISD::INTRINSIC_VOID && // nontemporal stores
       Parent->getOpcode() != X86ISD::TLSCALL && // Fixme
       Parent->getOpcode() != X86ISD::EH_SJLJ_SETJMP && // setjmp
-      Parent->getOpcode() != X86ISD::EH_SJLJ_LONGJMP) { // longjmp
+      Parent->getOpcode() != X86ISD::EH_SJLJ_LONGJMP && // longjmp
+      Parent->getOpcode() != X86ISD::JUMPTABLE_JUMP) {// jumptable_jump
     unsigned AddrSpace =
       cast<MemSDNode>(Parent)->getPointerInfo().getAddrSpace();
     // AddrSpace 256 -> GS, 257 -> FS.

lib/Target/X86/X86ISelLowering.h

       // EH_SJLJ_LONGJMP - SjLj exception handling longjmp.
       EH_SJLJ_LONGJMP,
 
+      // JUMPTABLE_JUMP - An unconditional jump to a function in a jump table.
+      JUMPTABLE_JUMP,
+
       /// TC_RETURN - Tail call return. See X86TargetLowering::LowerCall for
       /// the list of operands.
       TC_RETURN,

     SDValue LowerEH_RETURN(SDValue Op, SelectionDAG &DAG) const;
     SDValue lowerEH_SJLJ_SETJMP(SDValue Op, SelectionDAG &DAG) const;
     SDValue lowerEH_SJLJ_LONGJMP(SDValue Op, SelectionDAG &DAG) const;
+    SDValue LowerJUMPTABLE_JUMP(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerINIT_TRAMPOLINE(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerFLT_ROUNDS_(SDValue Op, SelectionDAG &DAG) const;
     SDValue LowerSIGN_EXTEND_INREG(SDValue Op, SelectionDAG &DAG) const;

     MachineBasicBlock *emitEHSjLjLongJmp(MachineInstr *MI,
                                          MachineBasicBlock *MBB) const;
 
+    MachineBasicBlock *emitJumpTableJump(MachineInstr *MI,
+                                         MachineBasicBlock *MBB) const;
+
     MachineBasicBlock *emitFMA3Instr(MachineInstr *MI,
                                      MachineBasicBlock *MBB) const;
 

lib/Target/X86/X86ISelLowering.cpp

   setOperationAction(ISD::EH_SJLJ_SETJMP, MVT::i32, Custom);
   setOperationAction(ISD::EH_SJLJ_LONGJMP, MVT::Other, Custom);
 
+  setOperationAction(ISD::JUMPTABLE_JUMP, getPointerTy(), Custom);
+
   // Darwin ABI issue.
   setOperationAction(ISD::ConstantPool    , MVT::i32  , Custom);
   setOperationAction(ISD::JumpTable       , MVT::i32  , Custom);

   return SDValue();
 }
 
+SDValue
+X86TargetLowering::LowerJUMPTABLE_JUMP(SDValue Op,
+                                       SelectionDAG &DAG) const {
+  SDLoc dl(Op);
+  return DAG.getNode(X86ISD::JUMPTABLE_JUMP, dl, MVT::Other, Op.getOperand(0),
+                     Op.getOperand(1));
+}
+
 // ConstantPool, JumpTable, GlobalAddress, and ExternalSymbol are lowered as
 // their target countpart wrapped in the X86ISD::Wrapper node. Suppose N is
 // one of the above mentioned nodes. It has to be wrapped because otherwise

   case ISD::INTRINSIC_WO_CHAIN: return LowerINTRINSIC_WO_CHAIN(Op, DAG);
   case ISD::INTRINSIC_VOID:
   case ISD::INTRINSIC_W_CHAIN:  return LowerINTRINSIC_W_CHAIN(Op, Subtarget, DAG);
+  case ISD::JUMPTABLE_JUMP:     return LowerJUMPTABLE_JUMP(Op, DAG);
   case ISD::RETURNADDR:         return LowerRETURNADDR(Op, DAG);
   case ISD::FRAMEADDR:          return LowerFRAMEADDR(Op, DAG);
   case ISD::FRAME_TO_ARGS_OFFSET:

   return MBB;
 }
 
+MachineBasicBlock *
+X86TargetLowering::emitJumpTableJump(MachineInstr *MI,
+                                     MachineBasicBlock *MBB) const {
+  DebugLoc DL = MI->getDebugLoc();
+  const TargetInstrInfo *TII = getTargetMachine().getInstrInfo();
+  const GlobalValue *GV = MI->getOperand(3).getGlobal();
+  BuildMI(MBB, DL, TII->get(X86::JMP_4))
+      .addGlobalAddress(GV, MI->getOperand(3).getOffset(), X86II::MO_PLT);
+
+  MI->eraseFromParent();
+  return MBB;
+}
+
 // Replace 213-type (isel default) FMA3 instructions with 231-type for
 // accumulator loops. Writing back to the accumulator allows the coalescer
-// to remove extra copies in the loop.   
+// to remove extra copies in the loop.
 MachineBasicBlock *
 X86TargetLowering::emitFMA3Instr(MachineInstr *MI,
                                  MachineBasicBlock *MBB) const {

   case X86::EH_SjLj_LongJmp64:
     return emitEHSjLjLongJmp(MI, BB);
 
+  case X86::JUMPTABLE_JUMP32:
+  case X86::JUMPTABLE_JUMP64:
+    return emitJumpTableJump(MI, BB);
   case TargetOpcode::STACKMAP:
   case TargetOpcode::PATCHPOINT:
     return emitPatchPoint(MI, BB);

lib/Target/X86/X86InstrCompiler.td

 }
 } // SchedRW
 
+let hasSideEffects = 1, isBarrier = 1, isCodeGenOnly = 1,
+    usesCustomInserter = 1, isTerminator = 1 in {
+  def JUMPTABLE_JUMP64 : I<0, Pseudo, (outs), (ins i64mem:$buf),
+                           "#JUMPTABLE_JUMP64",
+         [(X86jumptable_jump addr:$buf)]>,
+             Requires<[In64BitMode]>;
+  def JUMPTABLE_JUMP32 : I<0, Pseudo, (outs), (ins i32mem:$buf),
+                           "#JUMPTABLE_JUMP32",
+         [(X86jumptable_jump addr:$buf)]>,
+             Requires<[Not64BitMode]>;
+}
+
 let isBranch = 1, isTerminator = 1, isCodeGenOnly = 1 in {
   def EH_SjLj_Setup : I<0, Pseudo, (outs), (ins brtarget:$dst),
                         "#EH_SjLj_Setup\t$dst", []>;

lib/Target/X86/X86InstrInfo.cpp

 
     // Handle unconditional branches.
     if (I->getOpcode() == X86::JMP_4) {
+      // A JMP that has something other than MBB as a target can't be handled by
+      // this analysis. E.g., jmp indirect_fun@PLT. This is created by the
+      // llvm.jumptable_jump intrinsic.
+      if (!I->getOperand(0).isMBB())
+        continue;
+
       UnCondBrIter = I;
 
       if (!AllowModify) {

lib/Target/X86/X86InstrInfo.td

                                 SDTypeProfile<0, 1, [SDTCisPtrTy<0>]>,
                                 [SDNPHasChain, SDNPSideEffect]>;
 
+def X86jumptable_jump : SDNode<"X86ISD::JUMPTABLE_JUMP",
+             SDTypeProfile<0, 1, [SDTCisPtrTy<0>]>,
+             [SDNPHasChain, SDNPSideEffect]>;
+
 def X86tcret : SDNode<"X86ISD::TC_RETURN", SDT_X86TCRET,
                         [SDNPHasChain,  SDNPOptInGlue, SDNPVariadic]>;
 

lib/Transforms/IPO/CMakeLists.txt

   InlineSimple.cpp
   Inliner.cpp
   Internalize.cpp
+  JumpInstrTables.cpp
   LoopExtractor.cpp
   MergeFunctions.cpp
   PartialInlining.cpp

lib/Transforms/IPO/IPO.cpp

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

lib/Transforms/IPO/JumpInstrTables.cpp

+//===- JumpTables.cpp: Inline Assembly Jump 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/ADT/SmallString.h"
+#include "llvm/ADT/Statistic.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/InlineAsm.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Mangler.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/MathExtras.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/IPO/JumpInstrTables.h"
+
+#include <vector>
+
+using namespace llvm;
+
+char JumpInstrTables::ID = 0;
+
+INITIALIZE_PASS(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");
+STATISTIC(JumpTableSize, "Total size of all jump tables");
+
+ModulePass *llvm::createJumpInstrTablesPass() {
+  return new JumpInstrTables();
+}
+
+/// 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));
+
+JumpInstrTables::JumpInstrTables()
+  : ModulePass(ID),
+  Metadata(),
+  TableCount(0) {
+  initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry());
+}
+
+
+
+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;
+    Meta.FirstFunction = NULL;
+    Meta.Start = NULL;
+    Meta.Mask = NULL;
+    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);
+  if (it->second.FirstFunction == NULL)
+    it->second.FirstFunction = JumpFun;
+  JumpFun->setCallingConv(CallingConv::C); // C calling convention
+  // The section for this table
+  JumpFun->setSection((jump_section_prefix + Twine(it->second.TableNum)).str());
+  JumpFun->setAlignment(8); // align on 8-byte boundary
+
+  // The jump function has many attributes:
+  JumpFun->addFnAttr(Attribute::JumpTable); // it's part of a jump table
+  JumpFun->addFnAttr(Attribute::Naked); // no preamble/postamble
+  JumpFun->addFnAttr(Attribute::NoDuplicate); // don't duplicate calls
+  JumpFun->addFnAttr(Attribute::NoInline); // never inline
+  JumpFun->addFnAttr(Attribute::NoReturn); // it doesn't ever return
+  JumpFun->addFnAttr(Attribute::NoUnwind); // it doesn't unwind the stack
+  JumpFun->addFnAttr(Attribute::OptimizeNone); // don't optimize it
+  JumpFun->addFnAttr(Attribute::ReadNone); // it doesn't read memory at all
+
+  // Cast the function to void ()* so that we avoid any arguments being set up
+  // for this call. So, the IR for the jump function is:
+  // tail call void ()* (bitcast type @f to void ()*)
+  // unreachable
+
+  BasicBlock *BB = BasicBlock::Create(M.getContext(), "entry", JumpFun);
+  IRBuilder<> Builder(BB);
+
+  // Cast to i8* type for the intrinsic call.
+  Type *VoidPtrTy = Type::getInt8PtrTy(getGlobalContext());
+  Value *CastFun = Builder.CreateBitCast(Target, VoidPtrTy);
+  Function *JumpTableJumpFun =
+      Intrinsic::getDeclaration(&M, Intrinsic::jumptable_jump);
+  Builder.CreateCall(JumpTableJumpFun, CastFun);
+  Builder.CreateUnreachable();
+
+  ++NumFuncsInJumpTables;
+  return JumpFun;
+}
+
+void JumpInstrTables::finishTables(Module &M) {
+  Type *Int64Ty = Type::getInt64Ty(M.getContext());
+  Type *VoidPtrTy = Type::getInt8PtrTy(M.getContext());
+  Type *VoidTy = Type::getVoidTy(M.getContext());
+  FunctionType *PaddingFunTy = FunctionType::get(VoidTy, false);
+  Function *TrapFun = Intrinsic::getDeclaration(&M, Intrinsic::trap);
+
+  JumpMap::iterator MI, ME;
+  int PaddingCount = 0;
+  for (MI = Metadata.begin(), ME = Metadata.end(); MI != ME; MI++) {
+    // Fill out the remainder of the table with llvm.trap intrinsics to get to
+    // the next power of two. Depending on the size of this instruction, this
+    // might go beyond the power-of-two boundary.
+    // FIXME: figure out how to make this padding more precise.
+    uint64_t m = NextPowerOf2(MI->second.Count);
+
+    Twine Name("__jump_instr_table_padding_");
+    Name = Name + Twine(PaddingCount);
+    ++PaddingCount;
+
+    // Create a new function for the padding.
+    Function *PaddingFun = Function::Create(PaddingFunTy,
+                                            GlobalValue::ExternalLinkage,
+                                            Name.str(), &M);
+    PaddingFun->setSection(
+        (jump_section_prefix + Twine(MI->second.TableNum)).str());
+    PaddingFun->setAlignment(8);
+    PaddingFun->addFnAttr(Attribute::Naked); // no preamble/postamble
+    PaddingFun->addFnAttr(Attribute::NoDuplicate); // don't duplicate calls
+    PaddingFun->addFnAttr(Attribute::NoInline); // never inline
+    PaddingFun->addFnAttr(Attribute::NoReturn); // it doesn't ever return
+    PaddingFun->addFnAttr(Attribute::NoUnwind); // it doesn't unwind the stack
+    PaddingFun->addFnAttr(Attribute::OptimizeNone); // don't optimize it
+    PaddingFun->addFnAttr(Attribute::ReadNone); // it doesn't read memory at all
+
+    BasicBlock *PaddingBB = BasicBlock::Create(M.getContext(), "entry",
+                                               PaddingFun);
+    IRBuilder<> Builder(PaddingBB);
+    for (uint64_t i = MI->second.Count; i < m; i++) {
+      Builder.CreateCall(TrapFun);
+    }
+
+    // Can't reach the terminator.
+    Builder.CreateUnreachable();
+
+    // This assumes that each instruction in the table takes up 8 bytes.
+    int64_t alignment = (int64_t)m << 3;
+    JumpTableSize += (int)alignment;
+    MI->second.FirstFunction->setAlignment(static_cast<unsigned>(alignment));
+
+    Constant *JumpTableStartValue =
+        ConstantExpr::getBitCast(MI->second.FirstFunction, VoidPtrTy);
+
+    // Multiply by 8, since the entries in the table are 8-byte aligned. Also
+    // mask off the bottom 3 bits.
+    int64_t MaskValue = ((m << 3) - 1) & -8;
+    Constant *JumpTableMaskValue = ConstantInt::get(Int64Ty, MaskValue);
+
+    MI->second.Start = JumpTableStartValue;
+    MI->second.Mask = JumpTableMaskValue;
+  }
+}
+
+bool JumpInstrTables::hasTable(FunctionType *FunTy) {
+  FunctionType *TransTy = transformType(FunTy);
+  JumpMap::iterator it = Metadata.find(TransTy);
+  return Metadata.end() != it;
+}
+
+Constant *JumpInstrTables::getStart(FunctionType *FunTy) {
+  FunctionType *TransTy = transformType(FunTy);
+  JumpMap::iterator it = Metadata.find(TransTy);
+  assert(Metadata.end() != it && "Could not find this function type.");
+  return it->second.Start;
+}
+
+Constant *JumpInstrTables::getMask(FunctionType *FunTy) {
+  FunctionType *TransTy = transformType(FunTy);
+  JumpMap::iterator it = Metadata.find(TransTy);
+  assert(Metadata.end() != it && "Could not find this function type.");
+  return it->second.Mask;
+}
+
+FunctionType *JumpInstrTables::transformType(FunctionType *FunTy) {
+  // Returning NULL forces all types into the same table, since all types map
+  // to the same type
+  Type *VoidPtrTy = Type::getInt8PtrTy(getGlobalContext());
+
+  // 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(getGlobalContext());
+  FunctionType *VoidFnTy = FunctionType::get(
+      Type::getVoidTy(getGlobalContext()), 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 NULL;
+}
+
+// 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)) {
+    const Value *Op = CE->getOperand(0);
+    return !isa<Function>(Op) && !isa<GlobalAlias>(Op);
+  }
+
+  // Otherwise, since we know it's a call, it must be an indirect call
+  return true;
+}
+
+// Replaces Function GlobalValues with a different Value.
+bool replaceGlobalValueIndirectUse(GlobalValue *GV, Value *V, Use *U) {
+  User *Us = U->getUser();
+  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 ((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;
+      }
+
+      return false;
+    }
+
+    Us->replaceUsesOfWith(GV, 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) {
+        // The first user of this cast must exist, because a cast is not a viable
+        // top-level entity.
+        User *ParentUs = *CE->user_begin();
+        if (isa<CallInst>(ParentUs))
+          return false;
+      }
+    }
+
+    C->replaceUsesOfWithOnConstant(GV, V, U);
+  } else {
+    assert(false && "It's neither a 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.
+  Value::use_iterator UI = GV->use_begin();
+
+  // Make sure we don't try to replace calls in the same User multiple times,
+  // since the first replacement will replace all the Users.
+  while (GV->use_end() != UI) {
+    Use &U = *UI;
+
+    if (!replaceGlobalValueIndirectUse(GV, F, &U)) {
+      UI++;
+    } else {
+      // Get the new head of the use list. This will have changed, since we
+      // changed the uses of f.
+      UI = GV->use_begin();
+    }
+  }
+
+  return;
+}
+
+bool JumpInstrTables::runOnModule(Module &M) {
+  // 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.hasAddressTaken(NULL)) {
+      Functions[&F] = NULL;
+    }
+  }
+
+  // Create the jump-table functions.
+  for (auto &KV : Functions) {
+    Function *F = KV.first;
+    KV.second = insertEntry(M, F);
+  }
+
+  // Replace each address taken function with its jump-instruction table entry.
+  for (auto &KV : Functions) {
+    replaceValueWithFunction(KV.first, KV.second);
+  }
+
+  finishTables(M);
+  return Functions.size() > 0;
+}

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/X86/jumptable_jump.ll

+; RUN: llvm-as <%s >%t1
+; RUN: llc <%t1 | FileCheck %s
+
+declare void @llvm.jumptable_jump(i8* %f) noreturn nounwind
+
+define void @indirect2() {
+  ret void
+}
+
+define void @indirect_fun() {
+  ret void
+}
+
+define void @jump_instr_func() naked nounwind noinline optnone jumptable section "jump1" align 8 {
+; CHECK:         .align  8, 0x90
+; CHECK:         .type   jump_instr_func,@function
+; CHECK-NOT:   .cfi_startproc
+  call void @llvm.jumptable_jump(i8* bitcast (void ()* @indirect_fun to i8*))
+; CHECK:         jmp     indirect_fun@PLT
+  unreachable
+}
+; CHECK-NOT:   .cfi_endproc

test/Transforms/JumpInstrTables/jump_tables.ll

+; RUN: llvm-as <%s >%t1
+; RUN: opt -jump-instr-tables -o %t2 %t1 -stats -jump_single_table 2>&1 | FileCheck --check-prefix=SINGLE %s
+; RUN: opt -jump-instr-tables -o %t2 %t1 -stats -jump_arity_table 2>&1 | FileCheck --check-prefix=ARITY %s
+; RUN: opt -jump-instr-tables -o %t2 %t1 -stats -jump_simplified_type_table 2>&1 | FileCheck --check-prefix=SIMPL %s
+; RUN: opt -jump-instr-tables -o %t2 %t1 -stats -jump_full_type_table 2>&1 | FileCheck --check-prefix=FULL %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.fun_struct = type { i32 (...)* }
+
+@funcs = constant [12 x i8*] [
+  i8* bitcast (void ()* @indirect_fun to i8*),
+  i8* bitcast (void ()* @indirect_fun_match to i8*),
+  i8* bitcast (i32 ()* @indirect_fun_i32 to i8*),
+  i8* bitcast (i32 (i32)* @indirect_fun_i32_1 to i8*),
+  i8* bitcast (i32 (i32, i32)* @indirect_fun_i32_2 to i8*),
+  i8* bitcast (i32* (i32*, i32)* @indirect_fun_i32S_2 to i8*),
+  i8* bitcast (void (%struct.fun_struct)* @indirect_fun_struct to i8*),
+  i8* bitcast (void (i32 (...)*, i32)* @indirect_fun_fun to i8*),
+  i8* bitcast (i32 (i32 (...)*, i32)* @indirect_fun_fun_ret to i8*),
+  i8* bitcast (void ([19 x i8])* @indirect_fun_array to i8*),
+  i8* bitcast (void (<3 x i32>)* @indirect_fun_vec to i8*),
+  i8* bitcast (void (<4 x float>)* @indirect_fun_vec_2 to i8*)]
+
+define void @indirect_fun() {
+  ret void
+}
+
+define void @indirect_fun_match() {
+  ret void
+}
+
+define i32 @indirect_fun_i32() {
+  ret i32 0
+}
+
+define i32 @indirect_fun_i32_1(i32 %a) {
+  ret i32 %a
+}
+
+define i32 @indirect_fun_i32_2(i32 %a, i32 %b) {
+  ret i32 %a
+}
+
+define i32* @indirect_fun_i32S_2(i32* %a, i32 %b) {
+  ret i32* %a
+}
+
+define void @indirect_fun_struct(%struct.fun_struct %fs) {
+  ret void
+}
+
+define void @indirect_fun_fun(i32 (...)* %fun, i32 %a) {
+  ret void
+}
+
+define i32 @indirect_fun_fun_ret(i32 (...)* %fun, i32 %a) {
+  ret i32 %a
+}
+
+define void @indirect_fun_array([19 x i8] %a) {
+  ret void
+}
+
+define void @indirect_fun_vec(<3 x i32> %a) {
+  ret void
+}
+
+define void @indirect_fun_vec_2(<4 x float> %a) {
+  ret void
+}
+
+define i32 @m(void ()* %fun) {
+  call void ()* %fun()
+  ret i32 0
+}
+
+define void ()* @get_fun() {
+  ret void ()* @indirect_fun
+}
+
+define i32 @main(i32 %argc, i8** %argv) {
+  %f = call void ()* ()* @get_fun()
+  %a = call i32 @m(void ()* %f)
+  ret i32 %a
+}
+
+; XFAIL: win32
+; SINGLE:  12 jt            - Number of functions in the jump tables
+; SINGLE:   1 jt            - Number of indirect call tables generated
+; SINGLE: 128 jt            - Total size of all jump tables
+
+; ARITY:   12 jt            - Number of functions in the jump tables
+; ARITY:    3 jt            - Number of indirect call tables generated
+; ARITY:  160 jt            - Total size of all jump tables
+
+; SIMPL:   12 jt            - Number of functions in the jump tables
+; SIMPL:    5 jt            - Number of indirect call tables generated
+; SIMPL:  160 jt            - Total size of all jump tables
+
+; FULL:   12 jt            - Number of functions in the jump tables
+; FULL:   11 jt            - Number of indirect call tables generated
+; FULL:  192 jt            - Total size of all jump tables