From 5d0f7af3dc42d7bc843858317fba3bb91c44d68f Mon Sep 17 00:00:00 2001 From: Tom Roeder Date: Thu, 5 Jun 2014 19:29:43 +0000 Subject: [PATCH] Add a new attribute called 'jumptable' that creates jump-instruction tables for functions marked with this attribute. It includes a pass that rewrites all indirect calls to jumptable functions to pass through these tables. This also adds backend support for generating the jump-instruction tables on ARM and X86. Note that since the jumptable attribute creates a second function pointer for a function, any function marked with jumptable must also be marked with unnamed_addr. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@210280 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/LangRef.rst | 8 + include/llvm-c/Core.h | 3 +- include/llvm/Analysis/JumpInstrTableInfo.h | 60 ++++ include/llvm/Analysis/Passes.h | 4 + include/llvm/Bitcode/LLVMBitCodes.h | 3 +- include/llvm/CodeGen/CommandFlags.h | 16 ++ include/llvm/CodeGen/JumpInstrTables.h | 102 +++++++ include/llvm/CodeGen/Passes.h | 2 + include/llvm/IR/Attributes.h | 1 + include/llvm/InitializePasses.h | 2 + include/llvm/LinkAllPasses.h | 2 + include/llvm/Target/TargetInstrInfo.h | 15 + include/llvm/Target/TargetOptions.h | 17 +- lib/Analysis/Analysis.cpp | 1 + lib/Analysis/CMakeLists.txt | 1 + lib/Analysis/JumpInstrTableInfo.cpp | 40 +++ lib/AsmParser/LLLexer.cpp | 1 + lib/AsmParser/LLParser.cpp | 3 + lib/AsmParser/LLToken.h | 1 + lib/Bitcode/Reader/BitcodeReader.cpp | 2 + lib/Bitcode/Writer/BitcodeWriter.cpp | 2 + lib/CodeGen/AsmPrinter/AsmPrinter.cpp | 49 ++++ lib/CodeGen/CMakeLists.txt | 1 + lib/CodeGen/JumpInstrTables.cpp | 301 +++++++++++++++++++++ lib/CodeGen/LLVMTargetMachine.cpp | 10 + lib/IR/Attributes.cpp | 3 + lib/IR/Verifier.cpp | 11 +- lib/LTO/LTOCodeGenerator.cpp | 1 + lib/Target/ARM/ARMBaseInstrInfo.cpp | 24 ++ lib/Target/ARM/ARMBaseInstrInfo.h | 7 + lib/Target/X86/X86InstrInfo.cpp | 11 + lib/Target/X86/X86InstrInfo.h | 6 + lib/Transforms/IPO/IPO.cpp | 1 + test/Bitcode/attributes.ll | 12 +- test/CodeGen/ARM/jump_tables.ll | 32 +++ test/CodeGen/Generic/stop-after.ll | 2 +- test/CodeGen/X86/jump_table_alias.ll | 33 +++ test/CodeGen/X86/jump_table_bitcast.ll | 46 ++++ test/CodeGen/X86/jump_tables.ll | 272 +++++++++++++++++++ test/Verifier/jumptable.ll | 9 + 40 files changed, 1109 insertions(+), 8 deletions(-) create mode 100644 include/llvm/Analysis/JumpInstrTableInfo.h create mode 100644 include/llvm/CodeGen/JumpInstrTables.h create mode 100644 lib/Analysis/JumpInstrTableInfo.cpp create mode 100644 lib/CodeGen/JumpInstrTables.cpp create mode 100644 test/CodeGen/ARM/jump_tables.ll create mode 100644 test/CodeGen/X86/jump_table_alias.ll create mode 100644 test/CodeGen/X86/jump_table_bitcast.ll create mode 100644 test/CodeGen/X86/jump_tables.ll create mode 100644 test/Verifier/jumptable.ll diff --git a/docs/LangRef.rst b/docs/LangRef.rst index d76fc0d3afc..6beb9652ed6 100644 --- a/docs/LangRef.rst +++ b/docs/LangRef.rst @@ -1020,6 +1020,14 @@ example: 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. Note that this creates + a new pointer for the original function, which means that code that depends + on function-pointer identity can break. So, any function annotated with + ``jumptable`` must also be ``unnamed_addr``. ``minsize`` This attribute suggests that optimization passes and code generator passes make choices that keep the code size of this function as small diff --git a/include/llvm-c/Core.h b/include/llvm-c/Core.h index f37e3f89ca3..0e78ed71fa9 100644 --- a/include/llvm-c/Core.h +++ b/include/llvm-c/Core.h @@ -166,7 +166,8 @@ typedef enum { LLVMCold = 1ULL << 34, LLVMOptimizeNone = 1ULL << 35, LLVMInAllocaAttribute = 1ULL << 36, - LLVMNonNullAttribute = 1ULL << 37 + LLVMNonNullAttribute = 1ULL << 37, + LLVMJumpTableAttribute = 1ULL << 38, */ } LLVMAttribute; diff --git a/include/llvm/Analysis/JumpInstrTableInfo.h b/include/llvm/Analysis/JumpInstrTableInfo.h new file mode 100644 index 00000000000..54760aa0246 --- /dev/null +++ b/include/llvm/Analysis/JumpInstrTableInfo.h @@ -0,0 +1,60 @@ +//===-- 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 + +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 JumpPair; + typedef DenseMap > 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 */ diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 9494b7d9ebe..fd65ae5ca5b 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -142,6 +142,10 @@ namespace llvm { // 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 diff --git a/include/llvm/Bitcode/LLVMBitCodes.h b/include/llvm/Bitcode/LLVMBitCodes.h index 04c08ab3f46..10b0f65cbc0 100644 --- a/include/llvm/Bitcode/LLVMBitCodes.h +++ b/include/llvm/Bitcode/LLVMBitCodes.h @@ -372,7 +372,8 @@ namespace bitc { ATTR_KIND_COLD = 36, ATTR_KIND_OPTIMIZE_NONE = 37, ATTR_KIND_IN_ALLOCA = 38, - ATTR_KIND_NON_NULL = 39 + ATTR_KIND_NON_NULL = 39, + ATTR_KIND_JUMP_TABLE = 40 }; } // End bitc namespace diff --git a/include/llvm/CodeGen/CommandFlags.h b/include/llvm/CodeGen/CommandFlags.h index 2956ad8ea33..449d93418a4 100644 --- a/include/llvm/CodeGen/CommandFlags.h +++ b/include/llvm/CodeGen/CommandFlags.h @@ -202,6 +202,21 @@ FunctionSections("function-sections", cl::desc("Emit functions into separate sections"), cl::init(false)); +cl::opt +JTableType("jump-table-type", + cl::desc("Choose the type of Jump-Instruction Table for jumptable."), + cl::init(JumpTable::Single), + cl::values( + clEnumValN(JumpTable::Single, "single", + "Create a single table for all jumptable functions"), + clEnumValN(JumpTable::Arity, "arity", + "Create one table per number of parameters."), + clEnumValN(JumpTable::Simplified, "simplified", + "Create one table per simplified function type."), + clEnumValN(JumpTable::Full, "full", + "Create one table per unique function type."), + clEnumValEnd)); + // Common utility function tightly tied to the options listed here. Initializes // a TargetOptions object with CodeGen flags and returns it. static inline TargetOptions InitTargetOptionsFromCodeGenFlags() { @@ -228,6 +243,7 @@ static inline TargetOptions InitTargetOptionsFromCodeGenFlags() { Options.FunctionSections = FunctionSections; Options.MCOptions = InitMCTargetOptionsFromFlags(); + Options.JTType = JTableType; return Options; } diff --git a/include/llvm/CodeGen/JumpInstrTables.h b/include/llvm/CodeGen/JumpInstrTables.h new file mode 100644 index 00000000000..22aee48b680 --- /dev/null +++ b/include/llvm/CodeGen/JumpInstrTables.h @@ -0,0 +1,102 @@ +//===-- 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" +#include "llvm/Target/TargetOptions.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(); + JumpInstrTables(JumpTable::JumpTableType JTT); + 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 + struct TableMeta { + /// The number of this table + unsigned TableNum; + + /// The current number of jump entries in the table. + unsigned Count; + }; + + typedef DenseMap 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; + + /// The type of tables to build. + JumpTable::JumpTableType JTType; +}; + +/// Creates a JumpInstrTables pass for the given type of jump table. +ModulePass *createJumpInstrTablesPass(JumpTable::JumpTableType JTT); +} + +#endif /* LLVM_CODEGEN_JUMPINSTRTABLES_H */ diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index 35210f1ab84..bf31de78b40 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -588,6 +588,8 @@ namespace llvm { /// the intrinsic for later emission to the StackMap. extern char &StackMapLivenessID; + /// createJumpInstrTables - This pass creates jump-instruction tables. + ModulePass *createJumpInstrTablesPass(); } // End llvm namespace #endif diff --git a/include/llvm/IR/Attributes.h b/include/llvm/IR/Attributes.h index 86f9cc88941..e34dc83a5ba 100644 --- a/include/llvm/IR/Attributes.h +++ b/include/llvm/IR/Attributes.h @@ -75,6 +75,7 @@ public: 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 diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index 0466d11e35a..0c840f39f52 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -146,6 +146,8 @@ void initializeInstCountPass(PassRegistry&); void initializeInstNamerPass(PassRegistry&); void initializeInternalizePassPass(PassRegistry&); void initializeIntervalPartitionPass(PassRegistry&); +void initializeJumpInstrTableInfoPass(PassRegistry&); +void initializeJumpInstrTablesPass(PassRegistry&); void initializeJumpThreadingPass(PassRegistry&); void initializeLCSSAPass(PassRegistry&); void initializeLICMPass(PassRegistry&); diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index 2616ebd1fab..b2309ffc214 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -85,6 +85,8 @@ namespace { (void) llvm::createIndVarSimplifyPass(); (void) llvm::createInstructionCombiningPass(); (void) llvm::createInternalizePass(); + (void) llvm::createJumpInstrTableInfoPass(); + (void) llvm::createJumpInstrTablesPass(); (void) llvm::createLCSSAPass(); (void) llvm::createLICMPass(); (void) llvm::createLazyValueInfoPass(); diff --git a/include/llvm/Target/TargetInstrInfo.h b/include/llvm/Target/TargetInstrInfo.h index 165b35fee2b..80ddb920d45 100644 --- a/include/llvm/Target/TargetInstrInfo.h +++ b/include/llvm/Target/TargetInstrInfo.h @@ -29,6 +29,7 @@ class MachineRegisterInfo; class MDNode; class MCInst; class MCSchedModel; +class MCSymbolRefExpr; class SDNode; class ScheduleHazardRecognizer; class SelectionDAG; @@ -321,6 +322,20 @@ public: 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). diff --git a/include/llvm/Target/TargetOptions.h b/include/llvm/Target/TargetOptions.h index 636eaf5c05e..922fae54bb8 100644 --- a/include/llvm/Target/TargetOptions.h +++ b/include/llvm/Target/TargetOptions.h @@ -39,6 +39,17 @@ namespace llvm { }; } + namespace JumpTable { + enum JumpTableType { + Single, // Use a single table for all indirect jumptable calls. + Arity, // Use one table per number of function parameters. + Simplified, // Use one table per function type, with types projected + // into 4 types: pointer to non-function, struct, + // primitive, and function pointer. + Full // Use one table per unique function type + }; + } + class TargetOptions { public: TargetOptions() @@ -54,7 +65,7 @@ namespace llvm { CompressDebugSections(false), FunctionSections(false), DataSections(false), TrapUnreachable(false), TrapFuncName(""), FloatABIType(FloatABI::Default), - AllowFPOpFusion(FPOpFusion::Standard) {} + AllowFPOpFusion(FPOpFusion::Standard), JTType(JumpTable::Single) {} /// PrintMachineCode - This flag is enabled when the -print-machineinstrs /// option is specified on the command line, and should enable debugging @@ -205,6 +216,10 @@ namespace llvm { /// the value of this option. FPOpFusion::FPOpFusionMode AllowFPOpFusion; + /// JTType - This flag specifies the type of jump-instruction table to + /// create for functions that have the jumptable attribute. + JumpTable::JumpTableType JTType; + /// Machine level options. MCTargetOptions MCOptions; }; diff --git a/lib/Analysis/Analysis.cpp b/lib/Analysis/Analysis.cpp index 01c1c7e572c..ade940a7d30 100644 --- a/lib/Analysis/Analysis.cpp +++ b/lib/Analysis/Analysis.cpp @@ -48,6 +48,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeIVUsersPass(Registry); initializeInstCountPass(Registry); initializeIntervalPartitionPass(Registry); + initializeJumpInstrTableInfoPass(Registry); initializeLazyValueInfoPass(Registry); initializeLibCallAliasAnalysisPass(Registry); initializeLintPass(Registry); diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index b546789b949..d1632fd26ac 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -25,6 +25,7 @@ add_llvm_library(LLVMAnalysis InstructionSimplify.cpp Interval.cpp IntervalPartition.cpp + JumpInstrTableInfo.cpp LazyCallGraph.cpp LazyValueInfo.cpp LibCallAliasAnalysis.cpp diff --git a/lib/Analysis/JumpInstrTableInfo.cpp b/lib/Analysis/JumpInstrTableInfo.cpp new file mode 100644 index 00000000000..b5b426533ff --- /dev/null +++ b/lib/Analysis/JumpInstrTableInfo.cpp @@ -0,0 +1,40 @@ +//===-- JumpInstrTableInfo.cpp: Info for Jump-Instruction Tables ----------===// +// +// 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()); +} + +JumpInstrTableInfo::~JumpInstrTableInfo() {} + +void JumpInstrTableInfo::insertEntry(FunctionType *TableFunTy, Function *Target, + Function *Jump) { + Tables[TableFunTy].push_back(JumpPair(Target, Jump)); +} diff --git a/lib/AsmParser/LLLexer.cpp b/lib/AsmParser/LLLexer.cpp index 44a34126e48..b9193e89e7e 100644 --- a/lib/AsmParser/LLLexer.cpp +++ b/lib/AsmParser/LLLexer.cpp @@ -583,6 +583,7 @@ lltok::Kind LLLexer::LexIdentifier() { KEYWORD(cold); KEYWORD(inlinehint); KEYWORD(inreg); + KEYWORD(jumptable); KEYWORD(minsize); KEYWORD(naked); KEYWORD(nest); diff --git a/lib/AsmParser/LLParser.cpp b/lib/AsmParser/LLParser.cpp index cbb72ef0125..f77abaca17f 100644 --- a/lib/AsmParser/LLParser.cpp +++ b/lib/AsmParser/LLParser.cpp @@ -947,6 +947,7 @@ bool LLParser::ParseFnAttributeValuePairs(AttrBuilder &B, 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; @@ -1210,6 +1211,7 @@ bool LLParser::ParseOptionalParamAttrs(AttrBuilder &B) { 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: @@ -1271,6 +1273,7 @@ bool LLParser::ParseOptionalReturnAttrs(AttrBuilder &B) { 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: diff --git a/lib/AsmParser/LLToken.h b/lib/AsmParser/LLToken.h index b6b7d824b5f..3ce09503f5a 100644 --- a/lib/AsmParser/LLToken.h +++ b/lib/AsmParser/LLToken.h @@ -107,6 +107,7 @@ namespace lltok { kw_cold, kw_inlinehint, kw_inreg, + kw_jumptable, kw_minsize, kw_naked, kw_nest, diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp index 7b018a6b655..41d1f066b51 100644 --- a/lib/Bitcode/Reader/BitcodeReader.cpp +++ b/lib/Bitcode/Reader/BitcodeReader.cpp @@ -549,6 +549,8 @@ static Attribute::AttrKind GetAttrFromCode(uint64_t Code) { 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: diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp index dddcbc6f7e0..55ed8ceb51b 100644 --- a/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -177,6 +177,8 @@ static uint64_t getAttrKindEncoding(Attribute::AttrKind Kind) { 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: diff --git a/lib/CodeGen/AsmPrinter/AsmPrinter.cpp b/lib/CodeGen/AsmPrinter/AsmPrinter.cpp index 49c2ee20c20..cb7cacbb00c 100644 --- a/lib/CodeGen/AsmPrinter/AsmPrinter.cpp +++ b/lib/CodeGen/AsmPrinter/AsmPrinter.cpp @@ -18,6 +18,7 @@ #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" @@ -889,6 +890,54 @@ bool AsmPrinter::doFinalization(Module &M) { EmitVisibility(Name, V, false); } + // Get information about jump-instruction tables to print. + JumpInstrTableInfo *JITI = getAnalysisIfAvailable(); + + if (JITI && !JITI->getTables().empty()) { + 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()); + } + + } + } + // Emit module flags. SmallVector ModuleFlags; M.getModuleFlagsMetadata(ModuleFlags); diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt index 0b492a96521..b158925f276 100644 --- a/lib/CodeGen/CMakeLists.txt +++ b/lib/CodeGen/CMakeLists.txt @@ -27,6 +27,7 @@ add_llvm_library(LLVMCodeGen InterferenceCache.cpp IntrinsicLowering.cpp JITCodeEmitter.cpp + JumpInstrTables.cpp LLVMTargetMachine.cpp LatencyPriorityQueue.cpp LexicalScopes.cpp diff --git a/lib/CodeGen/JumpInstrTables.cpp b/lib/CodeGen/JumpInstrTables.cpp new file mode 100644 index 00000000000..05a1b27c8fe --- /dev/null +++ b/lib/CodeGen/JumpInstrTables.cpp @@ -0,0 +1,301 @@ +//===-- JumpInstrTables.cpp: Jump-Instruction Tables ----------------------===// +// +// 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/IR/Verifier.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +#include + +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() { + // The default implementation uses a single table for all functions. + return new JumpInstrTables(JumpTable::Single); +} + +ModulePass *llvm::createJumpInstrTablesPass(JumpTable::JumpTableType JTT) { + return new JumpInstrTables(JTT); +} + +namespace { +static const char jump_func_prefix[] = "__llvm_jump_instr_table_"; +static const char jump_section_prefix[] = ".jump.instr.table.text."; + +// 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)) { + return !(CE->isCast() && isa(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(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(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) { + // This bitcast must have exactly one user. + if (CE->user_begin() != CE->user_end()) { + User *ParentUs = *CE->user_begin(); + if (CallInst *CI = dyn_cast(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(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. + for (Value::use_iterator 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), + JTType(JumpTable::Single) { + initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry()); +} + +JumpInstrTables::JumpInstrTables(JumpTable::JumpTableType JTT) + : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0), JTType(JTT) { + initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry()); +} + +JumpInstrTables::~JumpInstrTables() {} + +void JumpInstrTables::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); +} + +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) { + struct TableMeta Meta; + Meta.TableNum = TableCount; + Meta.Count = 0; + Metadata[FunTy] = Meta; + it = Metadata.find(FunTy); + ++NumJumpTables; + ++TableCount; + } + + it->second.Count++; + + std::string NewName(jump_func_prefix); + NewName += (Twine(it->second.TableNum) + "_" + Twine(it->second.Count)).str(); + Function *JumpFun = + Function::Create(OrigFunTy, GlobalValue::ExternalLinkage, NewName, &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); + return Metadata.end() != Metadata.find(TransTy); +} + +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 ParamTys(FunTy->getNumParams()); + FunctionType::param_iterator PI, PE; + int i = 0; + + std::vector EmptyParams; + Type *Int32Ty = Type::getInt32Ty(FunTy->getContext()); + FunctionType *VoidFnTy = FunctionType::get( + Type::getVoidTy(FunTy->getContext()), EmptyParams, false); + switch (JTType) { + case JumpTable::Single: + + return FunctionType::get(RetTy, EmptyParams, false); + case JumpTable::Arity: + // 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 JumpTable::Simplified: + // 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 JumpTable::Full: + // Don't transform this type at all. + return FunTy; + } + + return nullptr; +} + +bool JumpInstrTables::runOnModule(Module &M) { + // Make sure the module is well-formed, especially with respect to jumptable. + if (verifyModule(M)) + return false; + + JITI = &getAnalysis(); + + // Get the set of jumptable-annotated functions. + DenseMap Functions; + for (Function &F : M) { + if (F.hasFnAttribute(Attribute::JumpTable)) { + assert(F.hasUnnamedAddr() && + "Attribute 'jumptable' requires 'unnamed_addr'"); + 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 Aliases; + for (GlobalAlias &GA : M.aliases()) { + Constant *Aliasee = GA.getAliasee(); + if (Function *F = dyn_cast(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(); +} diff --git a/lib/CodeGen/LLVMTargetMachine.cpp b/lib/CodeGen/LLVMTargetMachine.cpp index a5ac0578ab8..29062434f00 100644 --- a/lib/CodeGen/LLVMTargetMachine.cpp +++ b/lib/CodeGen/LLVMTargetMachine.cpp @@ -12,11 +12,15 @@ //===----------------------------------------------------------------------===// #include "llvm/Target/TargetMachine.h" + +#include "llvm/Analysis/Passes.h" #include "llvm/CodeGen/AsmPrinter.h" +#include "llvm/CodeGen/JumpInstrTables.h" #include "llvm/CodeGen/MachineFunctionAnalysis.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/Passes.h" #include "llvm/IR/IRPrintingPasses.h" +#include "llvm/IR/Verifier.h" #include "llvm/MC/MCAsmInfo.h" #include "llvm/MC/MCContext.h" #include "llvm/MC/MCInstrInfo.h" @@ -82,6 +86,7 @@ static MCContext *addPassesToGenerateCode(LLVMTargetMachine *TM, bool DisableVerify, AnalysisID StartAfter, AnalysisID StopAfter) { + // Add internal analysis passes from the target machine. TM->addAnalysisPasses(PM); @@ -136,6 +141,11 @@ bool LLVMTargetMachine::addPassesToEmitFile(PassManagerBase &PM, bool DisableVerify, AnalysisID StartAfter, AnalysisID StopAfter) { + // Passes to handle jumptable function annotations. These can't be handled at + // JIT time, so we don't add them directly to addPassesToGenerateCode. + PM.add(createJumpInstrTableInfoPass()); + PM.add(createJumpInstrTablesPass(Options.JTType)); + // Add common CodeGen passes. MCContext *Context = addPassesToGenerateCode(this, PM, DisableVerify, StartAfter, StopAfter); diff --git a/lib/IR/Attributes.cpp b/lib/IR/Attributes.cpp index a9074bb294d..58475e2d3cb 100644 --- a/lib/IR/Attributes.cpp +++ b/lib/IR/Attributes.cpp @@ -173,6 +173,8 @@ std::string Attribute::getAsString(bool InAttrGrp) const { return "inlinehint"; if (hasAttribute(Attribute::InReg)) return "inreg"; + if (hasAttribute(Attribute::JumpTable)) + return "jumptable"; if (hasAttribute(Attribute::MinSize)) return "minsize"; if (hasAttribute(Attribute::Naked)) @@ -395,6 +397,7 @@ uint64_t AttributeImpl::getAttrMask(Attribute::AttrKind Val) { case Attribute::OptimizeNone: return 1ULL << 42; case Attribute::InAlloca: return 1ULL << 43; case Attribute::NonNull: return 1ULL << 44; + case Attribute::JumpTable: return 1ULL << 45; } llvm_unreachable("Unsupported attribute type"); } diff --git a/lib/IR/Verifier.cpp b/lib/IR/Verifier.cpp index 6da8014a22d..46beb13622d 100644 --- a/lib/IR/Verifier.cpp +++ b/lib/IR/Verifier.cpp @@ -735,7 +735,8 @@ void Verifier::VerifyAttributeTypes(AttributeSet Attrs, unsigned Idx, 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); @@ -909,6 +910,14 @@ void Verifier::VerifyFunctionAttrs(FunctionType *FT, AttributeSet Attrs, Attribute::MinSize), "Attributes 'minsize and optnone' are incompatible!", V); } + + if (Attrs.hasAttribute(AttributeSet::FunctionIndex, + Attribute::JumpTable)) { + const GlobalValue *GV = cast(V); + Assert1(GV->hasUnnamedAddr(), + "Attribute 'jumptable' requires 'unnamed_addr'", V); + + } } void Verifier::VerifyBitcastType(const Value *V, Type *DestTy, Type *SrcTy) { diff --git a/lib/LTO/LTOCodeGenerator.cpp b/lib/LTO/LTOCodeGenerator.cpp index 99236bd24ea..aa7a968d50f 100644 --- a/lib/LTO/LTOCodeGenerator.cpp +++ b/lib/LTO/LTOCodeGenerator.cpp @@ -96,6 +96,7 @@ void LTOCodeGenerator::initializeLTOPasses() { initializeConstantMergePass(R); initializeDAHPass(R); initializeInstCombinerPass(R); + initializeJumpInstrTablesPass(R); initializeSimpleInlinerPass(R); initializePruneEHPass(R); initializeGlobalDCEPass(R); diff --git a/lib/Target/ARM/ARMBaseInstrInfo.cpp b/lib/Target/ARM/ARMBaseInstrInfo.cpp index bc266e88b2d..1c6c210dae8 100644 --- a/lib/Target/ARM/ARMBaseInstrInfo.cpp +++ b/lib/Target/ARM/ARMBaseInstrInfo.cpp @@ -32,6 +32,7 @@ #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" @@ -4358,6 +4359,29 @@ breakPartialRegDependency(MachineBasicBlock::iterator MI, MI->addRegisterKilled(DReg, TRI, true); } +void ARMBaseInstrInfo::getUnconditionalBranch( + MCInst &Branch, const MCSymbolRefExpr *BranchTarget) const { + if (Subtarget.isThumb()) + Branch.setOpcode(ARM::tB); + else if (Subtarget.isThumb2()) + Branch.setOpcode(ARM::t2B); + 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; } diff --git a/lib/Target/ARM/ARMBaseInstrInfo.h b/lib/Target/ARM/ARMBaseInstrInfo.h index 4b3e74023ac..891e3ee176a 100644 --- a/lib/Target/ARM/ARMBaseInstrInfo.h +++ b/lib/Target/ARM/ARMBaseInstrInfo.h @@ -229,6 +229,13 @@ public: 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; diff --git a/lib/Target/X86/X86InstrInfo.cpp b/lib/Target/X86/X86InstrInfo.cpp index a0ee1ee57be..03bd5442d23 100644 --- a/lib/Target/X86/X86InstrInfo.cpp +++ b/lib/Target/X86/X86InstrInfo.cpp @@ -28,6 +28,7 @@ #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" @@ -5299,6 +5300,16 @@ void X86InstrInfo::getNoopForMachoTarget(MCInst &NopInst) const { 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; diff --git a/lib/Target/X86/X86InstrInfo.h b/lib/Target/X86/X86InstrInfo.h index 5f3491536d8..3f2686cb699 100644 --- a/lib/Target/X86/X86InstrInfo.h +++ b/lib/Target/X86/X86InstrInfo.h @@ -396,6 +396,12 @@ public: const SmallVectorImpl &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, diff --git a/lib/Transforms/IPO/IPO.cpp b/lib/Transforms/IPO/IPO.cpp index b4d31d8d6fc..38fd165e752 100644 --- a/lib/Transforms/IPO/IPO.cpp +++ b/lib/Transforms/IPO/IPO.cpp @@ -30,6 +30,7 @@ void llvm::initializeIPO(PassRegistry &Registry) { initializeGlobalDCEPass(Registry); initializeGlobalOptPass(Registry); initializeIPCPPass(Registry); + initializeJumpInstrTablesPass(Registry); initializeAlwaysInlinerPass(Registry); initializeSimpleInlinerPass(Registry); initializeInternalizePassPass(Registry); diff --git a/test/Bitcode/attributes.ll b/test/Bitcode/attributes.ll index 02e1bb1c4e2..49366de9836 100644 --- a/test/Bitcode/attributes.ll +++ b/test/Bitcode/attributes.ll @@ -203,7 +203,7 @@ define void @f34() ; CHECK: define void @f34() { call void @nobuiltin() nobuiltin -; CHECK: call void @nobuiltin() #24 +; CHECK: call void @nobuiltin() #25 ret void; } @@ -223,6 +223,12 @@ define nonnull i8* @f37(i8* nonnull %a) { ret i8* %a } +define void @f38() unnamed_addr jumptable { +; CHECK: define void @f38() unnamed_addr #24 + call void bitcast (void (i8*)* @f36 to void ()*)() + unreachable +} + ; CHECK: attributes #0 = { noreturn } ; CHECK: attributes #1 = { nounwind } ; CHECK: attributes #2 = { readnone } @@ -247,5 +253,5 @@ define nonnull i8* @f37(i8* nonnull %a) { ; 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 } diff --git a/test/CodeGen/ARM/jump_tables.ll b/test/CodeGen/ARM/jump_tables.ll new file mode 100644 index 00000000000..61c7e43adfe --- /dev/null +++ b/test/CodeGen/ARM/jump_tables.ll @@ -0,0 +1,32 @@ +; RUN: llc <%s -march=arm -jump-table-type=single | FileCheck --check-prefix=ARM %s +; RUN: llc <%s -march=thumb -jump-table-type=single | FileCheck --check-prefix=THUMB %s + +define void @indirect_fun() unnamed_addr 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) diff --git a/test/CodeGen/Generic/stop-after.ll b/test/CodeGen/Generic/stop-after.ll index 557e097840a..5e0e350bc7f 100644 --- a/test/CodeGen/Generic/stop-after.ll +++ b/test/CodeGen/Generic/stop-after.ll @@ -5,6 +5,6 @@ ; STOP: Loop Strength Reduction ; STOP-NEXT: Machine Function Analysis -; START: -machine-branch-prob -gc-lowering +; START: -machine-branch-prob -jump-instr-tables -gc-lowering ; START: FunctionPass Manager ; START-NEXT: Lower Garbage Collection Instructions diff --git a/test/CodeGen/X86/jump_table_alias.ll b/test/CodeGen/X86/jump_table_alias.ll new file mode 100644 index 00000000000..f3691fda221 --- /dev/null +++ b/test/CodeGen/X86/jump_table_alias.ll @@ -0,0 +1,33 @@ +; RUN: llc <%s -jump-table-type=single | FileCheck %s +target triple = "x86_64-unknown-linux-gnu" +define i32 @f() unnamed_addr 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 + diff --git a/test/CodeGen/X86/jump_table_bitcast.ll b/test/CodeGen/X86/jump_table_bitcast.ll new file mode 100644 index 00000000000..33a798f7a6b --- /dev/null +++ b/test/CodeGen/X86/jump_table_bitcast.ll @@ -0,0 +1,46 @@ +; RUN: llc <%s -jump-table-type=single | FileCheck %s +target triple = "x86_64-unknown-linux-gnu" +define i32 @f() unnamed_addr jumptable { + ret i32 0 +} + +define i32 @g(i8* %a) unnamed_addr jumptable { + ret i32 0 +} + +define void @h(void ()* %func) unnamed_addr 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 + diff --git a/test/CodeGen/X86/jump_tables.ll b/test/CodeGen/X86/jump_tables.ll new file mode 100644 index 00000000000..5a0aed0c176 --- /dev/null +++ b/test/CodeGen/X86/jump_tables.ll @@ -0,0 +1,272 @@ +; RUN: llc <%s -jump-table-type=single | FileCheck --check-prefix=SINGLE %s +; RUN: llc <%s -jump-table-type=arity | FileCheck --check-prefix=ARITY %s +; RUN: llc <%s -jump-table-type=simplified | FileCheck --check-prefix=SIMPL %s +; RUN: llc <%s -jump-table-type=full | FileCheck --check-prefix=FULL %s + +target triple = "x86_64-unknown-linux-gnu" + +%struct.fun_struct = type { i32 (...)* } + +define void @indirect_fun() unnamed_addr jumptable { + ret void +} + +define void @indirect_fun_match() unnamed_addr jumptable { + ret void +} + +define i32 @indirect_fun_i32() unnamed_addr jumptable { + ret i32 0 +} + +define i32 @indirect_fun_i32_1(i32 %a) unnamed_addr jumptable { + ret i32 %a +} + +define i32 @indirect_fun_i32_2(i32 %a, i32 %b) unnamed_addr jumptable { + ret i32 %a +} + +define i32* @indirect_fun_i32S_2(i32* %a, i32 %b) unnamed_addr jumptable { + ret i32* %a +} + +define void @indirect_fun_struct(%struct.fun_struct %fs) unnamed_addr jumptable { + ret void +} + +define void @indirect_fun_fun(i32 (...)* %fun, i32 %a) unnamed_addr jumptable { + ret void +} + +define i32 @indirect_fun_fun_ret(i32 (...)* %fun, i32 %a) unnamed_addr jumptable { + ret i32 %a +} + +define void @indirect_fun_array([19 x i8] %a) unnamed_addr jumptable { + ret void +} + +define void @indirect_fun_vec(<3 x i32> %a) unnamed_addr jumptable { + ret void +} + +define void @indirect_fun_vec_2(<4 x float> %a) unnamed_addr 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 diff --git a/test/Verifier/jumptable.ll b/test/Verifier/jumptable.ll new file mode 100644 index 00000000000..5f4cd3fe4f4 --- /dev/null +++ b/test/Verifier/jumptable.ll @@ -0,0 +1,9 @@ +; RUN: not llc <%s 2>&1 | FileCheck %s + +define i32 @f() jumptable { + ret i32 0 +} + +; CHECK: Attribute 'jumptable' requires 'unnamed_addr' +; CHECK: i32 ()* @f +; CHECK: LLVM ERROR: Broken function found, compilation aborted! -- 2.34.1