1 //===-- JumpInstrTables.cpp: Jump-Instruction Tables ----------------------===//
3 // This file is distributed under the University of Illinois Open Source
4 // License. See LICENSE.TXT for details.
6 //===----------------------------------------------------------------------===//
9 /// \brief An implementation of jump-instruction tables.
11 //===----------------------------------------------------------------------===//
13 #define DEBUG_TYPE "jt"
15 #include "llvm/CodeGen/JumpInstrTables.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/Analysis/JumpInstrTableInfo.h"
18 #include "llvm/CodeGen/Passes.h"
19 #include "llvm/IR/Attributes.h"
20 #include "llvm/IR/CallSite.h"
21 #include "llvm/IR/Constants.h"
22 #include "llvm/IR/DerivedTypes.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/LLVMContext.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/IR/Operator.h"
27 #include "llvm/IR/Type.h"
28 #include "llvm/IR/Verifier.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/raw_ostream.h"
36 char JumpInstrTables::ID = 0;
38 INITIALIZE_PASS_BEGIN(JumpInstrTables, "jump-instr-tables",
39 "Jump-Instruction Tables", true, true)
40 INITIALIZE_PASS_DEPENDENCY(JumpInstrTableInfo);
41 INITIALIZE_PASS_END(JumpInstrTables, "jump-instr-tables",
42 "Jump-Instruction Tables", true, true)
44 STATISTIC(NumJumpTables, "Number of indirect call tables generated");
45 STATISTIC(NumFuncsInJumpTables, "Number of functions in the jump tables");
47 ModulePass *llvm::createJumpInstrTablesPass() {
48 // The default implementation uses a single table for all functions.
49 return new JumpInstrTables(JumpTable::Single);
52 ModulePass *llvm::createJumpInstrTablesPass(JumpTable::JumpTableType JTT) {
53 return new JumpInstrTables(JTT);
57 static const char jump_func_prefix[] = "__llvm_jump_instr_table_";
58 static const char jump_section_prefix[] = ".jump.instr.table.text.";
60 // Checks to see if a given CallSite is making an indirect call, including
61 // cases where the indirect call is made through a bitcast.
62 bool isIndirectCall(CallSite &CS) {
63 if (CS.getCalledFunction())
66 // Check the value to see if it is merely a bitcast of a function. In
67 // this case, it will translate to a direct function call in the resulting
68 // assembly, so we won't treat it as an indirect call here.
69 const Value *V = CS.getCalledValue();
70 if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
71 return !(CE->isCast() && isa<Function>(CE->getOperand(0)));
74 // Otherwise, since we know it's a call, it must be an indirect call
78 // Replaces Functions and GlobalAliases with a different Value.
79 bool replaceGlobalValueIndirectUse(GlobalValue *GV, Value *V, Use *U) {
80 User *Us = U->getUser();
83 if (Instruction *I = dyn_cast<Instruction>(Us)) {
86 // Don't do the replacement if this use is a direct call to this function.
87 // If the use is not the called value, then replace it.
88 if (CS && (isIndirectCall(CS) || CS.isCallee(U))) {
93 } else if (Constant *C = dyn_cast<Constant>(Us)) {
94 // Don't replace calls to bitcasts of function symbols, since they get
95 // translated to direct calls.
96 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Us)) {
97 if (CE->getOpcode() == Instruction::BitCast) {
98 // This bitcast must have exactly one user.
99 if (CE->user_begin() != CE->user_end()) {
100 User *ParentUs = *CE->user_begin();
101 if (CallInst *CI = dyn_cast<CallInst>(ParentUs)) {
103 Use &CEU = *CE->use_begin();
104 if (CS.isCallee(&CEU)) {
112 // GlobalAlias doesn't support replaceUsesOfWithOnConstant. And the verifier
113 // requires alias to point to a defined function. So, GlobalAlias is handled
114 // as a separate case in runOnModule.
115 if (!isa<GlobalAlias>(C))
116 C->replaceUsesOfWithOnConstant(GV, V, U);
118 llvm_unreachable("The Use of a Function symbol is neither an instruction "
125 // Replaces all replaceable address-taken uses of GV with a pointer to a
126 // jump-instruction table entry.
127 void replaceValueWithFunction(GlobalValue *GV, Function *F) {
128 // Go through all uses of this function and replace the uses of GV with the
129 // jump-table version of the function. Get the uses as a vector before
130 // replacing them, since replacing them changes the use list and invalidates
131 // the iterator otherwise.
132 for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E;) {
135 // Replacement of constants replaces all instances in the constant. So, some
136 // uses might have already been handled by the time we reach them here.
138 replaceGlobalValueIndirectUse(GV, F, &U);
143 } // end anonymous namespace
145 JumpInstrTables::JumpInstrTables()
146 : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0),
147 JTType(JumpTable::Single) {
148 initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry());
151 JumpInstrTables::JumpInstrTables(JumpTable::JumpTableType JTT)
152 : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0), JTType(JTT) {
153 initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry());
156 JumpInstrTables::~JumpInstrTables() {}
158 void JumpInstrTables::getAnalysisUsage(AnalysisUsage &AU) const {
159 AU.addRequired<JumpInstrTableInfo>();
162 Function *JumpInstrTables::insertEntry(Module &M, Function *Target) {
163 FunctionType *OrigFunTy = Target->getFunctionType();
164 FunctionType *FunTy = transformType(JTType, OrigFunTy);
166 JumpMap::iterator it = Metadata.find(FunTy);
167 if (Metadata.end() == it) {
168 struct TableMeta Meta;
169 Meta.TableNum = TableCount;
171 Metadata[FunTy] = Meta;
172 it = Metadata.find(FunTy);
179 std::string NewName(jump_func_prefix);
180 NewName += (Twine(it->second.TableNum) + "_" + Twine(it->second.Count)).str();
182 Function::Create(OrigFunTy, GlobalValue::ExternalLinkage, NewName, &M);
183 // The section for this table
184 JumpFun->setSection((jump_section_prefix + Twine(it->second.TableNum)).str());
185 JITI->insertEntry(FunTy, Target, JumpFun);
187 ++NumFuncsInJumpTables;
191 bool JumpInstrTables::hasTable(FunctionType *FunTy) {
192 FunctionType *TransTy = transformType(JTType, FunTy);
193 return Metadata.end() != Metadata.find(TransTy);
196 FunctionType *JumpInstrTables::transformType(JumpTable::JumpTableType JTT,
197 FunctionType *FunTy) {
198 // Returning nullptr forces all types into the same table, since all types map
200 Type *VoidPtrTy = Type::getInt8PtrTy(FunTy->getContext());
202 // Ignore the return type.
203 Type *RetTy = VoidPtrTy;
204 bool IsVarArg = FunTy->isVarArg();
205 std::vector<Type *> ParamTys(FunTy->getNumParams());
206 FunctionType::param_iterator PI, PE;
209 std::vector<Type *> EmptyParams;
210 Type *Int32Ty = Type::getInt32Ty(FunTy->getContext());
211 FunctionType *VoidFnTy = FunctionType::get(
212 Type::getVoidTy(FunTy->getContext()), EmptyParams, false);
214 case JumpTable::Single:
216 return FunctionType::get(RetTy, EmptyParams, false);
217 case JumpTable::Arity:
218 // Transform all types to void* so that all functions with the same arity
219 // end up in the same table.
220 for (PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE;
222 ParamTys[i] = VoidPtrTy;
225 return FunctionType::get(RetTy, ParamTys, IsVarArg);
226 case JumpTable::Simplified:
227 // Project all parameters types to one of 3 types: composite, integer, and
228 // function, matching the three subclasses of Type.
229 for (PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE;
231 assert((isa<IntegerType>(*PI) || isa<FunctionType>(*PI) ||
232 isa<CompositeType>(*PI)) &&
233 "This type is not an Integer or a Composite or a Function");
234 if (isa<CompositeType>(*PI)) {
235 ParamTys[i] = VoidPtrTy;
236 } else if (isa<FunctionType>(*PI)) {
237 ParamTys[i] = VoidFnTy;
238 } else if (isa<IntegerType>(*PI)) {
239 ParamTys[i] = Int32Ty;
243 return FunctionType::get(RetTy, ParamTys, IsVarArg);
244 case JumpTable::Full:
245 // Don't transform this type at all.
252 bool JumpInstrTables::runOnModule(Module &M) {
253 JITI = &getAnalysis<JumpInstrTableInfo>();
255 // Get the set of jumptable-annotated functions that have their address taken.
256 DenseMap<Function *, Function *> Functions;
257 for (Function &F : M) {
258 if (F.hasFnAttribute(Attribute::JumpTable) && F.hasAddressTaken()) {
259 assert(F.hasUnnamedAddr() &&
260 "Attribute 'jumptable' requires 'unnamed_addr'");
261 Functions[&F] = nullptr;
265 // Create the jump-table functions.
266 for (auto &KV : Functions) {
267 Function *F = KV.first;
268 KV.second = insertEntry(M, F);
271 // GlobalAlias is a special case, because the target of an alias statement
272 // must be a defined function. So, instead of replacing a given function in
273 // the alias, we replace all uses of aliases that target jumptable functions.
274 // Note that there's no need to create these functions, since only aliases
275 // that target known jumptable functions are replaced, and there's no way to
276 // put the jumptable annotation on a global alias.
277 DenseMap<GlobalAlias *, Function *> Aliases;
278 for (GlobalAlias &GA : M.aliases()) {
279 Constant *Aliasee = GA.getAliasee();
280 if (Function *F = dyn_cast<Function>(Aliasee)) {
281 auto it = Functions.find(F);
282 if (it != Functions.end()) {
283 Aliases[&GA] = it->second;
288 // Replace each address taken function with its jump-instruction table entry.
289 for (auto &KV : Functions)
290 replaceValueWithFunction(KV.first, KV.second);
292 for (auto &KV : Aliases)
293 replaceValueWithFunction(KV.first, KV.second);
295 return !Functions.empty();