Index: include/llvm/Bitcode/LLVMBitCodes.h =================================================================== --- include/llvm/Bitcode/LLVMBitCodes.h +++ include/llvm/Bitcode/LLVMBitCodes.h @@ -371,7 +371,8 @@ 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 Index: include/llvm/CodeGen/ISDOpcodes.h =================================================================== --- include/llvm/CodeGen/ISDOpcodes.h +++ include/llvm/CodeGen/ISDOpcodes.h @@ -576,6 +576,11 @@ /// 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 Index: include/llvm/IR/Attributes.h =================================================================== --- include/llvm/IR/Attributes.h +++ include/llvm/IR/Attributes.h @@ -75,6 +75,7 @@ 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 Index: include/llvm/IR/Intrinsics.td =================================================================== --- include/llvm/IR/Intrinsics.td +++ include/llvm/IR/Intrinsics.td @@ -522,6 +522,15 @@ 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 //===----------------------------------------------------------------------===// Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -144,6 +144,7 @@ void initializeInstNamerPass(PassRegistry&); void initializeInternalizePassPass(PassRegistry&); void initializeIntervalPartitionPass(PassRegistry&); +void initializeJumpInstrTablesPass(PassRegistry&); void initializeJumpThreadingPass(PassRegistry&); void initializeLCSSAPass(PassRegistry&); void initializeLICMPass(PassRegistry&); Index: include/llvm/Transforms/IPO/JumpInstrTables.h =================================================================== --- /dev/null +++ include/llvm/Transforms/IPO/JumpInstrTables.h @@ -0,0 +1,96 @@ +//===----- 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 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 */ Index: lib/AsmParser/LLLexer.cpp =================================================================== --- lib/AsmParser/LLLexer.cpp +++ lib/AsmParser/LLLexer.cpp @@ -577,6 +577,7 @@ KEYWORD(cold); KEYWORD(inlinehint); KEYWORD(inreg); + KEYWORD(jumptable); KEYWORD(minsize); KEYWORD(naked); KEYWORD(nest); Index: lib/AsmParser/LLParser.cpp =================================================================== --- lib/AsmParser/LLParser.cpp +++ lib/AsmParser/LLParser.cpp @@ -920,6 +920,7 @@ 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; @@ -1181,6 +1182,7 @@ 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: @@ -1241,6 +1243,7 @@ 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: Index: lib/AsmParser/LLToken.h =================================================================== --- lib/AsmParser/LLToken.h +++ lib/AsmParser/LLToken.h @@ -104,6 +104,7 @@ kw_cold, kw_inlinehint, kw_inreg, + kw_jumptable, kw_minsize, kw_naked, kw_nest, Index: lib/Bitcode/Reader/BitcodeReader.cpp =================================================================== --- lib/Bitcode/Reader/BitcodeReader.cpp +++ lib/Bitcode/Reader/BitcodeReader.cpp @@ -549,6 +549,8 @@ 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: Index: lib/Bitcode/Writer/BitcodeWriter.cpp =================================================================== --- lib/Bitcode/Writer/BitcodeWriter.cpp +++ lib/Bitcode/Writer/BitcodeWriter.cpp @@ -177,6 +177,8 @@ 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: Index: lib/CodeGen/SelectionDAG/LegalizeDAG.cpp =================================================================== --- lib/CodeGen/SelectionDAG/LegalizeDAG.cpp +++ lib/CodeGen/SelectionDAG/LegalizeDAG.cpp @@ -1257,6 +1257,7 @@ if (Action == TargetLowering::Legal) Action = TargetLowering::Expand; break; + case ISD::JUMPTABLE_JUMP: case ISD::INIT_TRAMPOLINE: case ISD::ADJUST_TRAMPOLINE: case ISD::FRAMEADDR: Index: lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -5224,7 +5224,16 @@ 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(I.getArgOperand(1)->stripPointerCasts()); Index: lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp =================================================================== --- lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp +++ lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp @@ -256,6 +256,7 @@ 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"; Index: lib/IR/Attributes.cpp =================================================================== --- lib/IR/Attributes.cpp +++ lib/IR/Attributes.cpp @@ -172,6 +172,8 @@ return "inlinehint"; if (hasAttribute(Attribute::InReg)) return "inreg"; + if (hasAttribute(Attribute::JumpTable)) + return "jumptable"; if (hasAttribute(Attribute::MinSize)) return "minsize"; if (hasAttribute(Attribute::Naked)) @@ -391,6 +393,7 @@ 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"); } Index: lib/IR/Verifier.cpp =================================================================== --- lib/IR/Verifier.cpp +++ lib/IR/Verifier.cpp @@ -722,7 +722,8 @@ 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); @@ -1043,6 +1044,30 @@ 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(CI), + "The first instruction in a jumptable function must be a call", + &F); + + const Instruction &UnI = Entry->back(); + Assert1( + isa(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 @@ -2352,6 +2377,13 @@ "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(CI.getArgOperand(0)->stripPointerCasts()), + "llvm.jump_instr_table_entry parameter must resolve to a function.", + &CI); + break; case Intrinsic::prefetch: Assert1(isa(CI.getArgOperand(1)) && isa(CI.getArgOperand(2)) && Index: lib/LTO/LTOCodeGenerator.cpp =================================================================== --- lib/LTO/LTOCodeGenerator.cpp +++ lib/LTO/LTOCodeGenerator.cpp @@ -97,6 +97,7 @@ initializeConstantMergePass(R); initializeDAHPass(R); initializeInstCombinerPass(R); + initializeJumpInstrTablesPass(R); initializeSimpleInlinerPass(R); initializePruneEHPass(R); initializeGlobalDCEPass(R); Index: lib/Target/X86/X86ISelDAGToDAG.cpp =================================================================== --- lib/Target/X86/X86ISelDAGToDAG.cpp +++ lib/Target/X86/X86ISelDAGToDAG.cpp @@ -1311,7 +1311,8 @@ 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(Parent)->getPointerInfo().getAddrSpace(); // AddrSpace 256 -> GS, 257 -> FS. Index: lib/Target/X86/X86ISelLowering.h =================================================================== --- lib/Target/X86/X86ISelLowering.h +++ lib/Target/X86/X86ISelLowering.h @@ -240,6 +240,9 @@ // 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, @@ -905,6 +908,7 @@ 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; @@ -982,6 +986,9 @@ MachineBasicBlock *emitEHSjLjLongJmp(MachineInstr *MI, MachineBasicBlock *MBB) const; + MachineBasicBlock *emitJumpTableJump(MachineInstr *MI, + MachineBasicBlock *MBB) const; + MachineBasicBlock *emitFMA3Instr(MachineInstr *MI, MachineBasicBlock *MBB) const; Index: lib/Target/X86/X86ISelLowering.cpp =================================================================== --- lib/Target/X86/X86ISelLowering.cpp +++ lib/Target/X86/X86ISelLowering.cpp @@ -538,6 +538,8 @@ 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); @@ -8078,6 +8080,14 @@ 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 @@ -13794,6 +13804,7 @@ 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: @@ -16156,9 +16167,22 @@ 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 { @@ -16467,6 +16491,9 @@ 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); Index: lib/Target/X86/X86InstrCompiler.td =================================================================== --- lib/Target/X86/X86InstrCompiler.td +++ lib/Target/X86/X86InstrCompiler.td @@ -191,6 +191,18 @@ } } // 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", []>; Index: lib/Target/X86/X86InstrInfo.cpp =================================================================== --- lib/Target/X86/X86InstrInfo.cpp +++ lib/Target/X86/X86InstrInfo.cpp @@ -2742,6 +2742,12 @@ // 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) { Index: lib/Target/X86/X86InstrInfo.td =================================================================== --- lib/Target/X86/X86InstrInfo.td +++ lib/Target/X86/X86InstrInfo.td @@ -227,6 +227,10 @@ 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]>; Index: lib/Transforms/IPO/CMakeLists.txt =================================================================== --- lib/Transforms/IPO/CMakeLists.txt +++ lib/Transforms/IPO/CMakeLists.txt @@ -13,6 +13,7 @@ InlineSimple.cpp Inliner.cpp Internalize.cpp + JumpInstrTables.cpp LoopExtractor.cpp MergeFunctions.cpp PartialInlining.cpp Index: lib/Transforms/IPO/IPO.cpp =================================================================== --- lib/Transforms/IPO/IPO.cpp +++ lib/Transforms/IPO/IPO.cpp @@ -30,6 +30,7 @@ initializeGlobalDCEPass(Registry); initializeGlobalOptPass(Registry); initializeIPCPPass(Registry); + initializeJumpInstrTablesPass(Registry); initializeAlwaysInlinerPass(Registry); initializeSimpleInlinerPass(Registry); initializeInternalizePassPass(Registry); Index: lib/Transforms/IPO/JumpInstrTables.cpp =================================================================== --- /dev/null +++ lib/Transforms/IPO/JumpInstrTables.cpp @@ -0,0 +1,392 @@ +//===- 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 + +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 +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(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 ParamTys(FunTy->getNumParams()); + FunctionType::param_iterator PI, PE; + int i = 0; + + std::vector 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(*PI) || isa(*PI) || + isa(*PI)) && "This type is not an Integer or a" + " Composite or a Function"); + if (isa(*PI)) { + ParamTys[i] = VoidPtrTy; + } else if (isa(*PI)) { + ParamTys[i] = VoidFnTy; + } else if (isa(*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(V)) { + const Value *Op = CE->getOperand(0); + return !isa(Op) && !isa(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(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(Us)) { + // Don't replace calls to bitcasts of function symbols, since they get + // translated to direct calls. + if (ConstantExpr *CE = dyn_cast(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(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 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; +} Index: test/Bitcode/attributes.ll =================================================================== --- test/Bitcode/attributes.ll +++ test/Bitcode/attributes.ll @@ -203,7 +203,7 @@ ; CHECK: define void @f34() { call void @nobuiltin() nobuiltin -; CHECK: call void @nobuiltin() #24 +; CHECK: call void @nobuiltin() #25 ret void; } @@ -218,6 +218,12 @@ 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 } @@ -242,5 +248,5 @@ ; 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 } Index: test/CodeGen/X86/jumptable_jump.ll =================================================================== --- /dev/null +++ test/CodeGen/X86/jumptable_jump.ll @@ -0,0 +1,22 @@ +; 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 Index: test/Transforms/JumpInstrTables/jump_tables.ll =================================================================== --- /dev/null +++ test/Transforms/JumpInstrTables/jump_tables.ll @@ -0,0 +1,103 @@ +; 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