]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //===-- JumpInstrTables.cpp: Jump-Instruction Tables ----------------------===// |
2 | // | |
3 | // This file is distributed under the University of Illinois Open Source | |
4 | // License. See LICENSE.TXT for details. | |
5 | // | |
6 | //===----------------------------------------------------------------------===// | |
7 | /// | |
8 | /// \file | |
9 | /// \brief An implementation of jump-instruction tables. | |
10 | /// | |
11 | //===----------------------------------------------------------------------===// | |
12 | ||
13 | #define DEBUG_TYPE "jt" | |
14 | ||
15 | #include "llvm/CodeGen/JumpInstrTables.h" | |
1a4d82fc JJ |
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" | |
1a4d82fc JJ |
32 | #include <vector> |
33 | ||
34 | using namespace llvm; | |
35 | ||
36 | char JumpInstrTables::ID = 0; | |
37 | ||
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) | |
43 | ||
44 | STATISTIC(NumJumpTables, "Number of indirect call tables generated"); | |
45 | STATISTIC(NumFuncsInJumpTables, "Number of functions in the jump tables"); | |
46 | ||
47 | ModulePass *llvm::createJumpInstrTablesPass() { | |
48 | // The default implementation uses a single table for all functions. | |
49 | return new JumpInstrTables(JumpTable::Single); | |
50 | } | |
51 | ||
52 | ModulePass *llvm::createJumpInstrTablesPass(JumpTable::JumpTableType JTT) { | |
53 | return new JumpInstrTables(JTT); | |
54 | } | |
55 | ||
56 | namespace { | |
57 | static const char jump_func_prefix[] = "__llvm_jump_instr_table_"; | |
58 | static const char jump_section_prefix[] = ".jump.instr.table.text."; | |
59 | ||
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()) | |
64 | return false; | |
65 | ||
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))); | |
72 | } | |
73 | ||
74 | // Otherwise, since we know it's a call, it must be an indirect call | |
75 | return true; | |
76 | } | |
77 | ||
78 | // Replaces Functions and GlobalAliases with a different Value. | |
79 | bool replaceGlobalValueIndirectUse(GlobalValue *GV, Value *V, Use *U) { | |
80 | User *Us = U->getUser(); | |
81 | if (!Us) | |
82 | return false; | |
83 | if (Instruction *I = dyn_cast<Instruction>(Us)) { | |
84 | CallSite CS(I); | |
85 | ||
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))) { | |
89 | return false; | |
90 | } | |
91 | ||
92 | U->set(V); | |
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)) { | |
102 | CallSite CS(CI); | |
103 | Use &CEU = *CE->use_begin(); | |
104 | if (CS.isCallee(&CEU)) { | |
105 | return false; | |
106 | } | |
107 | } | |
108 | } | |
109 | } | |
110 | } | |
111 | ||
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); | |
117 | } else { | |
85aaf69f SL |
118 | llvm_unreachable("The Use of a Function symbol is neither an instruction " |
119 | "nor a constant"); | |
1a4d82fc JJ |
120 | } |
121 | ||
122 | return true; | |
123 | } | |
124 | ||
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;) { | |
133 | Use &U = *I++; | |
134 | ||
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. | |
137 | if (U.get() == GV) | |
138 | replaceGlobalValueIndirectUse(GV, F, &U); | |
139 | } | |
140 | ||
141 | return; | |
142 | } | |
143 | } // end anonymous namespace | |
144 | ||
145 | JumpInstrTables::JumpInstrTables() | |
146 | : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0), | |
147 | JTType(JumpTable::Single) { | |
148 | initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry()); | |
149 | } | |
150 | ||
151 | JumpInstrTables::JumpInstrTables(JumpTable::JumpTableType JTT) | |
152 | : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0), JTType(JTT) { | |
153 | initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry()); | |
154 | } | |
155 | ||
156 | JumpInstrTables::~JumpInstrTables() {} | |
157 | ||
158 | void JumpInstrTables::getAnalysisUsage(AnalysisUsage &AU) const { | |
159 | AU.addRequired<JumpInstrTableInfo>(); | |
160 | } | |
161 | ||
162 | Function *JumpInstrTables::insertEntry(Module &M, Function *Target) { | |
163 | FunctionType *OrigFunTy = Target->getFunctionType(); | |
85aaf69f | 164 | FunctionType *FunTy = transformType(JTType, OrigFunTy); |
1a4d82fc JJ |
165 | |
166 | JumpMap::iterator it = Metadata.find(FunTy); | |
167 | if (Metadata.end() == it) { | |
168 | struct TableMeta Meta; | |
169 | Meta.TableNum = TableCount; | |
170 | Meta.Count = 0; | |
171 | Metadata[FunTy] = Meta; | |
172 | it = Metadata.find(FunTy); | |
173 | ++NumJumpTables; | |
174 | ++TableCount; | |
175 | } | |
176 | ||
177 | it->second.Count++; | |
178 | ||
179 | std::string NewName(jump_func_prefix); | |
180 | NewName += (Twine(it->second.TableNum) + "_" + Twine(it->second.Count)).str(); | |
181 | Function *JumpFun = | |
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); | |
186 | ||
187 | ++NumFuncsInJumpTables; | |
188 | return JumpFun; | |
189 | } | |
190 | ||
191 | bool JumpInstrTables::hasTable(FunctionType *FunTy) { | |
85aaf69f | 192 | FunctionType *TransTy = transformType(JTType, FunTy); |
1a4d82fc JJ |
193 | return Metadata.end() != Metadata.find(TransTy); |
194 | } | |
195 | ||
85aaf69f SL |
196 | FunctionType *JumpInstrTables::transformType(JumpTable::JumpTableType JTT, |
197 | FunctionType *FunTy) { | |
1a4d82fc JJ |
198 | // Returning nullptr forces all types into the same table, since all types map |
199 | // to the same type | |
200 | Type *VoidPtrTy = Type::getInt8PtrTy(FunTy->getContext()); | |
201 | ||
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; | |
207 | int i = 0; | |
208 | ||
209 | std::vector<Type *> EmptyParams; | |
210 | Type *Int32Ty = Type::getInt32Ty(FunTy->getContext()); | |
211 | FunctionType *VoidFnTy = FunctionType::get( | |
212 | Type::getVoidTy(FunTy->getContext()), EmptyParams, false); | |
85aaf69f | 213 | switch (JTT) { |
1a4d82fc JJ |
214 | case JumpTable::Single: |
215 | ||
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; | |
221 | PI++, i++) { | |
222 | ParamTys[i] = VoidPtrTy; | |
223 | } | |
224 | ||
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; | |
230 | ++PI, ++i) { | |
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; | |
240 | } | |
241 | } | |
242 | ||
243 | return FunctionType::get(RetTy, ParamTys, IsVarArg); | |
244 | case JumpTable::Full: | |
245 | // Don't transform this type at all. | |
246 | return FunTy; | |
247 | } | |
248 | ||
249 | return nullptr; | |
250 | } | |
251 | ||
252 | bool JumpInstrTables::runOnModule(Module &M) { | |
253 | JITI = &getAnalysis<JumpInstrTableInfo>(); | |
254 | ||
85aaf69f | 255 | // Get the set of jumptable-annotated functions that have their address taken. |
1a4d82fc JJ |
256 | DenseMap<Function *, Function *> Functions; |
257 | for (Function &F : M) { | |
85aaf69f | 258 | if (F.hasFnAttribute(Attribute::JumpTable) && F.hasAddressTaken()) { |
1a4d82fc JJ |
259 | assert(F.hasUnnamedAddr() && |
260 | "Attribute 'jumptable' requires 'unnamed_addr'"); | |
261 | Functions[&F] = nullptr; | |
262 | } | |
263 | } | |
264 | ||
265 | // Create the jump-table functions. | |
266 | for (auto &KV : Functions) { | |
267 | Function *F = KV.first; | |
268 | KV.second = insertEntry(M, F); | |
269 | } | |
270 | ||
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; | |
284 | } | |
285 | } | |
286 | } | |
287 | ||
288 | // Replace each address taken function with its jump-instruction table entry. | |
289 | for (auto &KV : Functions) | |
290 | replaceValueWithFunction(KV.first, KV.second); | |
291 | ||
292 | for (auto &KV : Aliases) | |
293 | replaceValueWithFunction(KV.first, KV.second); | |
294 | ||
295 | return !Functions.empty(); | |
296 | } |