1cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines//===-- JumpInstrTables.cpp: Jump-Instruction Tables ----------------------===// 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 jump-instruction tables. 10cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// 11cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines//===----------------------------------------------------------------------===// 12cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 13cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#define DEBUG_TYPE "jt" 14cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 15cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/CodeGen/JumpInstrTables.h" 16cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 17cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/ADT/Statistic.h" 18cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/Analysis/JumpInstrTableInfo.h" 19cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/CodeGen/Passes.h" 20cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/Attributes.h" 21cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/CallSite.h" 22cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/Constants.h" 23cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/DerivedTypes.h" 24cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/Function.h" 25cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/LLVMContext.h" 26cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/Module.h" 27cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/Operator.h" 28cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/Type.h" 29cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/IR/Verifier.h" 30cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/Support/CommandLine.h" 31cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/Support/Debug.h" 32cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/Support/raw_ostream.h" 33cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 34cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include <vector> 35cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 36cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesusing namespace llvm; 37cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 38cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hineschar JumpInstrTables::ID = 0; 39cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 40cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesINITIALIZE_PASS_BEGIN(JumpInstrTables, "jump-instr-tables", 41cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines "Jump-Instruction Tables", true, true) 42cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesINITIALIZE_PASS_DEPENDENCY(JumpInstrTableInfo); 43cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesINITIALIZE_PASS_END(JumpInstrTables, "jump-instr-tables", 44cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines "Jump-Instruction Tables", true, true) 45cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 46cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesSTATISTIC(NumJumpTables, "Number of indirect call tables generated"); 47cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesSTATISTIC(NumFuncsInJumpTables, "Number of functions in the jump tables"); 48cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 49cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesModulePass *llvm::createJumpInstrTablesPass() { 50cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // The default implementation uses a single table for all functions. 51cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return new JumpInstrTables(JumpTable::Single); 52cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 53cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 54cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesModulePass *llvm::createJumpInstrTablesPass(JumpTable::JumpTableType JTT) { 55cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return new JumpInstrTables(JTT); 56cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 57cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 58cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesnamespace { 59cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesstatic const char jump_func_prefix[] = "__llvm_jump_instr_table_"; 60cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesstatic const char jump_section_prefix[] = ".jump.instr.table.text."; 61cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 62cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// Checks to see if a given CallSite is making an indirect call, including 63cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// cases where the indirect call is made through a bitcast. 64cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesbool isIndirectCall(CallSite &CS) { 65cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (CS.getCalledFunction()) 66cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return false; 67cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 68cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Check the value to see if it is merely a bitcast of a function. In 69cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // this case, it will translate to a direct function call in the resulting 70cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // assembly, so we won't treat it as an indirect call here. 71cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const Value *V = CS.getCalledValue(); 72cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) { 73cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return !(CE->isCast() && isa<Function>(CE->getOperand(0))); 74cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 75cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 76cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Otherwise, since we know it's a call, it must be an indirect call 77cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return true; 78cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 79cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 80cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// Replaces Functions and GlobalAliases with a different Value. 81cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesbool replaceGlobalValueIndirectUse(GlobalValue *GV, Value *V, Use *U) { 82cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines User *Us = U->getUser(); 83cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!Us) 84cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return false; 85cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Instruction *I = dyn_cast<Instruction>(Us)) { 86cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CallSite CS(I); 87cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 88cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Don't do the replacement if this use is a direct call to this function. 89cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // If the use is not the called value, then replace it. 90cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (CS && (isIndirectCall(CS) || CS.isCallee(U))) { 91cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return false; 92cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 93cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 94cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines U->set(V); 95cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } else if (Constant *C = dyn_cast<Constant>(Us)) { 96cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Don't replace calls to bitcasts of function symbols, since they get 97cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // translated to direct calls. 98cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Us)) { 99cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (CE->getOpcode() == Instruction::BitCast) { 100cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // This bitcast must have exactly one user. 101cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (CE->user_begin() != CE->user_end()) { 102cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines User *ParentUs = *CE->user_begin(); 103cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (CallInst *CI = dyn_cast<CallInst>(ParentUs)) { 104cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CallSite CS(CI); 105cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Use &CEU = *CE->use_begin(); 106cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (CS.isCallee(&CEU)) { 107cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return false; 108cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 109cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 110cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 111cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 112cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 113cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 114cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // GlobalAlias doesn't support replaceUsesOfWithOnConstant. And the verifier 115cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // requires alias to point to a defined function. So, GlobalAlias is handled 116cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // as a separate case in runOnModule. 117cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!isa<GlobalAlias>(C)) 118cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines C->replaceUsesOfWithOnConstant(GV, V, U); 119cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } else { 120cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines assert(false && "The Use of a Function symbol is neither an instruction nor" 121cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines " a constant"); 122cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 123cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 124cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return true; 125cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 126cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 127cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// Replaces all replaceable address-taken uses of GV with a pointer to a 128cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines// jump-instruction table entry. 129cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesvoid replaceValueWithFunction(GlobalValue *GV, Function *F) { 130cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Go through all uses of this function and replace the uses of GV with the 131cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // jump-table version of the function. Get the uses as a vector before 132cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // replacing them, since replacing them changes the use list and invalidates 133cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // the iterator otherwise. 134cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E;) { 135cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Use &U = *I++; 136cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 137cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Replacement of constants replaces all instances in the constant. So, some 138cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // uses might have already been handled by the time we reach them here. 139cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (U.get() == GV) 140cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines replaceGlobalValueIndirectUse(GV, F, &U); 141cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 142cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 143cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return; 144cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 145cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} // end anonymous namespace 146cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 147cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesJumpInstrTables::JumpInstrTables() 148cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0), 149cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JTType(JumpTable::Single) { 150cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry()); 151cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 152cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 153cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesJumpInstrTables::JumpInstrTables(JumpTable::JumpTableType JTT) 154cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0), JTType(JTT) { 155cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry()); 156cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 157cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 158cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesJumpInstrTables::~JumpInstrTables() {} 159cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 160cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesvoid JumpInstrTables::getAnalysisUsage(AnalysisUsage &AU) const { 161cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines AU.addRequired<JumpInstrTableInfo>(); 162cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 163cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 164cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesFunction *JumpInstrTables::insertEntry(Module &M, Function *Target) { 165cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines FunctionType *OrigFunTy = Target->getFunctionType(); 166cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines FunctionType *FunTy = transformType(OrigFunTy); 167cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 168cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JumpMap::iterator it = Metadata.find(FunTy); 169cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Metadata.end() == it) { 170cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines struct TableMeta Meta; 171cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Meta.TableNum = TableCount; 172cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Meta.Count = 0; 173cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Metadata[FunTy] = Meta; 174cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines it = Metadata.find(FunTy); 175cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ++NumJumpTables; 176cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ++TableCount; 177cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 178cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 179cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines it->second.Count++; 180cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 181cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines std::string NewName(jump_func_prefix); 182cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewName += (Twine(it->second.TableNum) + "_" + Twine(it->second.Count)).str(); 183cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Function *JumpFun = 184cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Function::Create(OrigFunTy, GlobalValue::ExternalLinkage, NewName, &M); 185cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // The section for this table 186cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JumpFun->setSection((jump_section_prefix + Twine(it->second.TableNum)).str()); 187cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JITI->insertEntry(FunTy, Target, JumpFun); 188cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 189cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ++NumFuncsInJumpTables; 190cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return JumpFun; 191cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 192cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 193cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesbool JumpInstrTables::hasTable(FunctionType *FunTy) { 194cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines FunctionType *TransTy = transformType(FunTy); 195cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return Metadata.end() != Metadata.find(TransTy); 196cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 197cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 198cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesFunctionType *JumpInstrTables::transformType(FunctionType *FunTy) { 199cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Returning nullptr forces all types into the same table, since all types map 200cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // to the same type 201cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Type *VoidPtrTy = Type::getInt8PtrTy(FunTy->getContext()); 202cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 203cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Ignore the return type. 204cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Type *RetTy = VoidPtrTy; 205cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines bool IsVarArg = FunTy->isVarArg(); 206cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines std::vector<Type *> ParamTys(FunTy->getNumParams()); 207cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines FunctionType::param_iterator PI, PE; 208cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines int i = 0; 209cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 210cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines std::vector<Type *> EmptyParams; 211cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Type *Int32Ty = Type::getInt32Ty(FunTy->getContext()); 212cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines FunctionType *VoidFnTy = FunctionType::get( 213cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Type::getVoidTy(FunTy->getContext()), EmptyParams, false); 214cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines switch (JTType) { 215cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines case JumpTable::Single: 216cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 217cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return FunctionType::get(RetTy, EmptyParams, false); 218cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines case JumpTable::Arity: 219cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Transform all types to void* so that all functions with the same arity 220cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // end up in the same table. 221cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE; 222cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines PI++, i++) { 223cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ParamTys[i] = VoidPtrTy; 224cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 225cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 226cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return FunctionType::get(RetTy, ParamTys, IsVarArg); 227cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines case JumpTable::Simplified: 228cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Project all parameters types to one of 3 types: composite, integer, and 229cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // function, matching the three subclasses of Type. 230cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE; 231cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ++PI, ++i) { 232cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines assert((isa<IntegerType>(*PI) || isa<FunctionType>(*PI) || 233cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines isa<CompositeType>(*PI)) && 234cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines "This type is not an Integer or a Composite or a Function"); 235cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (isa<CompositeType>(*PI)) { 236cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ParamTys[i] = VoidPtrTy; 237cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } else if (isa<FunctionType>(*PI)) { 238cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ParamTys[i] = VoidFnTy; 239cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } else if (isa<IntegerType>(*PI)) { 240cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ParamTys[i] = Int32Ty; 241cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 242cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 243cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 244cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return FunctionType::get(RetTy, ParamTys, IsVarArg); 245cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines case JumpTable::Full: 246cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Don't transform this type at all. 247cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return FunTy; 248cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 249cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 250cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return nullptr; 251cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 252cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 253cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hinesbool JumpInstrTables::runOnModule(Module &M) { 254cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Make sure the module is well-formed, especially with respect to jumptable. 255cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (verifyModule(M)) 256cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return false; 257cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 258cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines JITI = &getAnalysis<JumpInstrTableInfo>(); 259cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 260cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Get the set of jumptable-annotated functions. 261cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines DenseMap<Function *, Function *> Functions; 262cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (Function &F : M) { 263cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (F.hasFnAttribute(Attribute::JumpTable)) { 264cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines assert(F.hasUnnamedAddr() && 265cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines "Attribute 'jumptable' requires 'unnamed_addr'"); 266cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Functions[&F] = nullptr; 267cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 268cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 269cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 270cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Create the jump-table functions. 271cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (auto &KV : Functions) { 272cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Function *F = KV.first; 273cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines KV.second = insertEntry(M, F); 274cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 275cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 276cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // GlobalAlias is a special case, because the target of an alias statement 277cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // must be a defined function. So, instead of replacing a given function in 278cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // the alias, we replace all uses of aliases that target jumptable functions. 279cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Note that there's no need to create these functions, since only aliases 280cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // that target known jumptable functions are replaced, and there's no way to 281cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // put the jumptable annotation on a global alias. 282cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines DenseMap<GlobalAlias *, Function *> Aliases; 283cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (GlobalAlias &GA : M.aliases()) { 284cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Constant *Aliasee = GA.getAliasee(); 285cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (Function *F = dyn_cast<Function>(Aliasee)) { 286cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines auto it = Functions.find(F); 287cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (it != Functions.end()) { 288cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Aliases[&GA] = it->second; 289cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 290cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 291cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 292cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 293cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Replace each address taken function with its jump-instruction table entry. 294cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (auto &KV : Functions) 295cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines replaceValueWithFunction(KV.first, KV.second); 296cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 297cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (auto &KV : Aliases) 298cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines replaceValueWithFunction(KV.first, KV.second); 299cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 300cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines return !Functions.empty(); 301cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines} 302