1cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines//===-- JumpInstrTables.h: Jump-Instruction Tables --------------*- C++ -*-===// 2cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// 3cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// This file is distributed under the University of Illinois Open Source 4cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// License. See LICENSE.TXT for details. 5cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// 6cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines//===----------------------------------------------------------------------===// 7cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// 8cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// \file 9cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// \brief An implementation of tables consisting of jump instructions 10cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// 11cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines//===----------------------------------------------------------------------===// 12cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 13cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#ifndef LLVM_CODEGEN_JUMPINSTRTABLES_H 14cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#define LLVM_CODEGEN_JUMPINSTRTABLES_H 15cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 16cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/ADT/DenseMap.h" 17cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/Pass.h" 18cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/Target/TargetOptions.h" 19cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 20cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesnamespace llvm { 21cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesclass Constant; 22cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesclass Function; 23cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesclass FunctionType; 24cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesclass JumpInstrTableInfo; 25cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesclass Module; 26cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 27cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// A class to manage a set of jump tables indexed on function type. It looks at 28cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// each function in the module to find all the functions that have the 29cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// jumptable attribute set. For each such function, it creates a new 30cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// jump-instruction-table function and stores the mapping in the ImmutablePass 31cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// JumpInstrTableInfo. 32cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// 33cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// These special functions get lowered in AsmPrinter to assembly of the form: 34cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// \verbatim 35cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// .globl f 36cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// .type f,@function 37cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// .align 8,0x90 38cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// f: 39cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// jmp f_orig@PLT 40cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// \endverbatim 41cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// 42cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// Support for an architecture depends on two functions in TargetInstrInfo: 43cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// getUnconditionalBranch, and getTrap. AsmPrinter uses these to generate the 44cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// appropriate instructions for the jump statement (an unconditional branch) 45cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// and for padding to make the table have a size that is a power of two. This 46cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// padding uses a trap instruction to ensure that calls to this area halt the 47cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// program. The default implementations of these functions call 48cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// llvm_unreachable. 49cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesclass JumpInstrTables : public ModulePass { 50cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinespublic: 51cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines static char ID; 52cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 53cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JumpInstrTables(); 54cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JumpInstrTables(JumpTable::JumpTableType JTT); 55cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines virtual ~JumpInstrTables(); 56cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool runOnModule(Module &M) override; 57cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const char *getPassName() const override { return "Jump-Instruction Tables"; } 58cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override; 59cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 60cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// Creates a jump-instruction table function for the Target and adds it to 61cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// the tables. 62cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Function *insertEntry(Module &M, Function *Target); 63cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 64cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// Checks to see if there is already a table for the given FunctionType. 65cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool hasTable(FunctionType *FunTy); 66cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 67cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesprivate: 68cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// The metadata used while a jump table is being built 69cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines struct TableMeta { 70cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// The number of this table 71cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned TableNum; 72cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 73cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// The current number of jump entries in the table. 74cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned Count; 75cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines }; 76cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 77cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines typedef DenseMap<FunctionType *, struct TableMeta> JumpMap; 78cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 79cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// Maps the function into a subset of function types, depending on the 80cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// jump-instruction table style selected from JumpTableTypes in 81cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// JumpInstrTables.cpp. The choice of mapping determines the number of 82cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// jump-instruction tables generated by this pass. E.g., the simplest mapping 83cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// converts every function type into void f(); so, all functions end up in a 84cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// single table. 85cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines FunctionType *transformType(FunctionType *FunTy); 86cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 87cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// The current state of functions and jump entries in the table(s). 88cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JumpMap Metadata; 89cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 90cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// The ImmutablePass that stores information about the generated tables. 91cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JumpInstrTableInfo *JITI; 92cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 93cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// The total number of tables. 94cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines unsigned TableCount; 95cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 96cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines /// The type of tables to build. 97cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JumpTable::JumpTableType JTType; 98cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines}; 99cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 100cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// Creates a JumpInstrTables pass for the given type of jump table. 101cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesModulePass *createJumpInstrTablesPass(JumpTable::JumpTableType JTT); 102cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 103cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 104cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#endif /* LLVM_CODEGEN_JUMPINSTRTABLES_H */ 105