/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/Evaluator.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- Evaluator.cpp - LLVM IR evaluator ----------------------------------===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // Function evaluator for LLVM IR. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #include "llvm/Transforms/Utils/Evaluator.h" |
14 | | #include "llvm/ADT/DenseMap.h" |
15 | | #include "llvm/ADT/STLExtras.h" |
16 | | #include "llvm/ADT/SmallPtrSet.h" |
17 | | #include "llvm/ADT/SmallVector.h" |
18 | | #include "llvm/Analysis/ConstantFolding.h" |
19 | | #include "llvm/IR/BasicBlock.h" |
20 | | #include "llvm/IR/CallSite.h" |
21 | | #include "llvm/IR/Constant.h" |
22 | | #include "llvm/IR/Constants.h" |
23 | | #include "llvm/IR/DataLayout.h" |
24 | | #include "llvm/IR/DerivedTypes.h" |
25 | | #include "llvm/IR/Function.h" |
26 | | #include "llvm/IR/GlobalAlias.h" |
27 | | #include "llvm/IR/GlobalValue.h" |
28 | | #include "llvm/IR/GlobalVariable.h" |
29 | | #include "llvm/IR/InstrTypes.h" |
30 | | #include "llvm/IR/Instruction.h" |
31 | | #include "llvm/IR/Instructions.h" |
32 | | #include "llvm/IR/IntrinsicInst.h" |
33 | | #include "llvm/IR/Intrinsics.h" |
34 | | #include "llvm/IR/Operator.h" |
35 | | #include "llvm/IR/Type.h" |
36 | | #include "llvm/IR/User.h" |
37 | | #include "llvm/IR/Value.h" |
38 | | #include "llvm/Support/Casting.h" |
39 | | #include "llvm/Support/Debug.h" |
40 | | #include "llvm/Support/raw_ostream.h" |
41 | | #include <iterator> |
42 | | |
43 | | #define DEBUG_TYPE "evaluator" |
44 | | |
45 | | using namespace llvm; |
46 | | |
47 | | static inline bool |
48 | | isSimpleEnoughValueToCommit(Constant *C, |
49 | | SmallPtrSetImpl<Constant *> &SimpleConstants, |
50 | | const DataLayout &DL); |
51 | | |
52 | | /// Return true if the specified constant can be handled by the code generator. |
53 | | /// We don't want to generate something like: |
54 | | /// void *X = &X/42; |
55 | | /// because the code generator doesn't have a relocation that can handle that. |
56 | | /// |
57 | | /// This function should be called if C was not found (but just got inserted) |
58 | | /// in SimpleConstants to avoid having to rescan the same constants all the |
59 | | /// time. |
60 | | static bool |
61 | | isSimpleEnoughValueToCommitHelper(Constant *C, |
62 | | SmallPtrSetImpl<Constant *> &SimpleConstants, |
63 | 1.96k | const DataLayout &DL) { |
64 | 1.96k | // Simple global addresses are supported, do not allow dllimport or |
65 | 1.96k | // thread-local globals. |
66 | 1.96k | if (auto *GV = dyn_cast<GlobalValue>(C)) |
67 | 274 | return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal()270 ; |
68 | 1.68k | |
69 | 1.68k | // Simple integer, undef, constant aggregate zero, etc are all supported. |
70 | 1.68k | if (C->getNumOperands() == 0 || isa<BlockAddress>(C)350 ) |
71 | 1.33k | return true; |
72 | 350 | |
73 | 350 | // Aggregate values are safe if all their elements are. |
74 | 350 | if (isa<ConstantAggregate>(C)) { |
75 | 1 | for (Value *Op : C->operands()) |
76 | 2 | if (!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL)) |
77 | 0 | return false; |
78 | 1 | return true; |
79 | 349 | } |
80 | 349 | |
81 | 349 | // We don't know exactly what relocations are allowed in constant expressions, |
82 | 349 | // so we allow &global+constantoffset, which is safe and uniformly supported |
83 | 349 | // across targets. |
84 | 349 | ConstantExpr *CE = cast<ConstantExpr>(C); |
85 | 349 | switch (CE->getOpcode()) { |
86 | 349 | case Instruction::BitCast: |
87 | 60 | // Bitcast is fine if the casted value is fine. |
88 | 60 | return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
89 | 349 | |
90 | 349 | case Instruction::IntToPtr: |
91 | 23 | case Instruction::PtrToInt: |
92 | 23 | // int <=> ptr is fine if the int type is the same size as the |
93 | 23 | // pointer type. |
94 | 23 | if (DL.getTypeSizeInBits(CE->getType()) != |
95 | 23 | DL.getTypeSizeInBits(CE->getOperand(0)->getType())) |
96 | 2 | return false; |
97 | 21 | return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
98 | 21 | |
99 | 21 | // GEP is fine if it is simple + constant offset. |
100 | 263 | case Instruction::GetElementPtr: |
101 | 905 | for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i642 ) |
102 | 642 | if (!isa<ConstantInt>(CE->getOperand(i))) |
103 | 0 | return false; |
104 | 263 | return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
105 | 263 | |
106 | 263 | case Instruction::Add: |
107 | 0 | // We allow simple+cst. |
108 | 0 | if (!isa<ConstantInt>(CE->getOperand(1))) |
109 | 0 | return false; |
110 | 0 | return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
111 | 3 | } |
112 | 3 | return false; |
113 | 3 | } |
114 | | |
115 | | static inline bool |
116 | | isSimpleEnoughValueToCommit(Constant *C, |
117 | | SmallPtrSetImpl<Constant *> &SimpleConstants, |
118 | 4.22k | const DataLayout &DL) { |
119 | 4.22k | // If we already checked this constant, we win. |
120 | 4.22k | if (!SimpleConstants.insert(C).second) |
121 | 2.26k | return true; |
122 | 1.96k | // Check the constant. |
123 | 1.96k | return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL); |
124 | 1.96k | } |
125 | | |
126 | | /// Return true if this constant is simple enough for us to understand. In |
127 | | /// particular, if it is a cast to anything other than from one pointer type to |
128 | | /// another pointer type, we punt. We basically just support direct accesses to |
129 | | /// globals and GEP's of globals. This should be kept up to date with |
130 | | /// CommitValueTo. |
131 | 3.90k | static bool isSimpleEnoughPointerToCommit(Constant *C) { |
132 | 3.90k | // Conservatively, avoid aggregate types. This is because we don't |
133 | 3.90k | // want to worry about them partially overlapping other stores. |
134 | 3.90k | if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType()) |
135 | 0 | return false; |
136 | 3.90k | |
137 | 3.90k | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) |
138 | 676 | // Do not allow weak/*_odr/linkonce linkage or external globals. |
139 | 676 | return GV->hasUniqueInitializer(); |
140 | 3.22k | |
141 | 3.22k | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { |
142 | 3.22k | // Handle a constantexpr gep. |
143 | 3.22k | if (CE->getOpcode() == Instruction::GetElementPtr && |
144 | 3.22k | isa<GlobalVariable>(CE->getOperand(0))3.17k && |
145 | 3.22k | cast<GEPOperator>(CE)->isInBounds()3.17k ) { |
146 | 3.17k | GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); |
147 | 3.17k | // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or |
148 | 3.17k | // external globals. |
149 | 3.17k | if (!GV->hasUniqueInitializer()) |
150 | 2 | return false; |
151 | 3.17k | |
152 | 3.17k | // The first index must be zero. |
153 | 3.17k | ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin())); |
154 | 3.17k | if (!CI || !CI->isZero()) return false0 ; |
155 | 3.17k | |
156 | 3.17k | // The remaining indices must be compile-time known integers within the |
157 | 3.17k | // notional bounds of the corresponding static array types. |
158 | 3.17k | if (!CE->isGEPWithNoNotionalOverIndexing()) |
159 | 0 | return false; |
160 | 3.17k | |
161 | 3.17k | return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); |
162 | 3.17k | |
163 | 3.17k | // A constantexpr bitcast from a pointer to another pointer is a no-op, |
164 | 3.17k | // and we know how to evaluate it by moving the bitcast from the pointer |
165 | 3.17k | // operand to the value operand. |
166 | 3.17k | } else if (53 CE->getOpcode() == Instruction::BitCast53 && |
167 | 53 | isa<GlobalVariable>(CE->getOperand(0))47 ) { |
168 | 42 | // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or |
169 | 42 | // external globals. |
170 | 42 | return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer(); |
171 | 42 | } |
172 | 11 | } |
173 | 11 | |
174 | 11 | return false; |
175 | 11 | } |
176 | | |
177 | | /// Apply 'Func' to Ptr. If this returns nullptr, introspect the pointer's |
178 | | /// type and walk down through the initial elements to obtain additional |
179 | | /// pointers to try. Returns the first non-null return value from Func, or |
180 | | /// nullptr if the type can't be introspected further. |
181 | | static Constant * |
182 | | evaluateBitcastFromPtr(Constant *Ptr, const DataLayout &DL, |
183 | | const TargetLibraryInfo *TLI, |
184 | 108 | std::function<Constant *(Constant *)> Func) { |
185 | 108 | Constant *Val; |
186 | 166 | while (!(Val = Func(Ptr))) { |
187 | 121 | // If Ty is a struct, we can convert the pointer to the struct |
188 | 121 | // into a pointer to its first member. |
189 | 121 | // FIXME: This could be extended to support arrays as well. |
190 | 121 | Type *Ty = cast<PointerType>(Ptr->getType())->getElementType(); |
191 | 121 | if (!isa<StructType>(Ty)) |
192 | 63 | break; |
193 | 58 | |
194 | 58 | IntegerType *IdxTy = IntegerType::get(Ty->getContext(), 32); |
195 | 58 | Constant *IdxZero = ConstantInt::get(IdxTy, 0, false); |
196 | 58 | Constant *const IdxList[] = {IdxZero, IdxZero}; |
197 | 58 | |
198 | 58 | Ptr = ConstantExpr::getGetElementPtr(Ty, Ptr, IdxList); |
199 | 58 | if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) |
200 | 58 | Ptr = FoldedPtr; |
201 | 58 | } |
202 | 108 | return Val; |
203 | 108 | } |
204 | | |
205 | 162 | static Constant *getInitializer(Constant *C) { |
206 | 162 | auto *GV = dyn_cast<GlobalVariable>(C); |
207 | 162 | return GV && GV->hasDefinitiveInitializer() ? GV->getInitializer()143 : nullptr19 ; |
208 | 162 | } |
209 | | |
210 | | /// Return the value that would be computed by a load from P after the stores |
211 | | /// reflected by 'memory' have been performed. If we can't decide, return null. |
212 | 895 | Constant *Evaluator::ComputeLoadResult(Constant *P) { |
213 | 895 | // If this memory location has been recently stored, use the stored value: it |
214 | 895 | // is the most up-to-date. |
215 | 965 | auto findMemLoc = [this](Constant *Ptr) { |
216 | 965 | DenseMap<Constant *, Constant *>::const_iterator I = |
217 | 965 | MutatedMemory.find(Ptr); |
218 | 965 | return I != MutatedMemory.end() ? I->second641 : nullptr324 ; |
219 | 965 | }; |
220 | 895 | |
221 | 895 | if (Constant *Val = findMemLoc(P)) |
222 | 634 | return Val; |
223 | 261 | |
224 | 261 | // Access it. |
225 | 261 | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) { |
226 | 87 | if (GV->hasDefinitiveInitializer()) |
227 | 69 | return GV->getInitializer(); |
228 | 18 | return nullptr; |
229 | 18 | } |
230 | 174 | |
231 | 174 | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) { |
232 | 171 | switch (CE->getOpcode()) { |
233 | 171 | // Handle a constantexpr getelementptr. |
234 | 171 | case Instruction::GetElementPtr: |
235 | 103 | if (auto *I = getInitializer(CE->getOperand(0))) |
236 | 99 | return ConstantFoldLoadThroughGEPConstantExpr(I, CE); |
237 | 4 | break; |
238 | 4 | // Handle a constantexpr bitcast. |
239 | 66 | case Instruction::BitCast: |
240 | 66 | // We're evaluating a load through a pointer that was bitcast to a |
241 | 66 | // different type. See if the "from" pointer has recently been stored. |
242 | 66 | // If it hasn't, we may still be able to find a stored pointer by |
243 | 66 | // introspecting the type. |
244 | 66 | Constant *Val = |
245 | 66 | evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, findMemLoc); |
246 | 66 | if (!Val) |
247 | 59 | Val = getInitializer(CE->getOperand(0)); |
248 | 66 | if (Val) |
249 | 51 | return ConstantFoldLoadThroughBitcast( |
250 | 51 | Val, P->getType()->getPointerElementType(), DL); |
251 | 15 | break; |
252 | 171 | } |
253 | 171 | } |
254 | 24 | |
255 | 24 | return nullptr; // don't know how to evaluate. |
256 | 24 | } |
257 | | |
258 | 4.35k | static Function *getFunction(Constant *C) { |
259 | 4.35k | if (auto *Fn = dyn_cast<Function>(C)) |
260 | 4.35k | return Fn; |
261 | 4 | |
262 | 4 | if (auto *Alias = dyn_cast<GlobalAlias>(C)) |
263 | 1 | if (auto *Fn = dyn_cast<Function>(Alias->getAliasee())) |
264 | 1 | return Fn; |
265 | 3 | return nullptr; |
266 | 3 | } |
267 | | |
268 | | Function * |
269 | | Evaluator::getCalleeWithFormalArgs(CallSite &CS, |
270 | 4.35k | SmallVector<Constant *, 8> &Formals) { |
271 | 4.35k | auto *V = CS.getCalledValue(); |
272 | 4.35k | if (auto *Fn = getFunction(getVal(V))) |
273 | 4.34k | return getFormalParams(CS, Fn, Formals) ? Fn4.34k : nullptr4 ; |
274 | 3 | |
275 | 3 | auto *CE = dyn_cast<ConstantExpr>(V); |
276 | 3 | if (!CE || CE->getOpcode() != Instruction::BitCast || |
277 | 3 | !getFormalParams(CS, getFunction(CE->getOperand(0)), Formals)) |
278 | 0 | return nullptr; |
279 | 3 | |
280 | 3 | return dyn_cast<Function>( |
281 | 3 | ConstantFoldLoadThroughBitcast(CE, CE->getOperand(0)->getType(), DL)); |
282 | 3 | } |
283 | | |
284 | | bool Evaluator::getFormalParams(CallSite &CS, Function *F, |
285 | 4.35k | SmallVector<Constant *, 8> &Formals) { |
286 | 4.35k | if (!F) |
287 | 0 | return false; |
288 | 4.35k | |
289 | 4.35k | auto *FTy = F->getFunctionType(); |
290 | 4.35k | if (FTy->getNumParams() > CS.getNumArgOperands()) { |
291 | 0 | LLVM_DEBUG(dbgs() << "Too few arguments for function.\n"); |
292 | 0 | return false; |
293 | 0 | } |
294 | 4.35k | |
295 | 4.35k | auto ArgI = CS.arg_begin(); |
296 | 9.63k | for (auto ParI = FTy->param_begin(), ParE = FTy->param_end(); ParI != ParE; |
297 | 5.29k | ++ParI5.28k ) { |
298 | 5.29k | auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), *ParI, DL); |
299 | 5.29k | if (!ArgC) { |
300 | 4 | LLVM_DEBUG(dbgs() << "Can not convert function argument.\n"); |
301 | 4 | return false; |
302 | 4 | } |
303 | 5.28k | Formals.push_back(ArgC); |
304 | 5.28k | ++ArgI; |
305 | 5.28k | } |
306 | 4.35k | return true4.34k ; |
307 | 4.35k | } |
308 | | |
309 | | /// If call expression contains bitcast then we may need to cast |
310 | | /// evaluated return value to a type of the call expression. |
311 | 2.63k | Constant *Evaluator::castCallResultIfNeeded(Value *CallExpr, Constant *RV) { |
312 | 2.63k | ConstantExpr *CE = dyn_cast<ConstantExpr>(CallExpr); |
313 | 2.63k | if (!RV || !CE1.99k || CE->getOpcode() != Instruction::BitCast2 ) |
314 | 2.63k | return RV; |
315 | 2 | |
316 | 2 | if (auto *FT = |
317 | 2 | dyn_cast<FunctionType>(CE->getType()->getPointerElementType())) { |
318 | 2 | RV = ConstantFoldLoadThroughBitcast(RV, FT->getReturnType(), DL); |
319 | 2 | if (!RV) |
320 | 2 | LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n"); |
321 | 2 | } |
322 | 2 | return RV; |
323 | 2 | } |
324 | | |
325 | | /// Evaluate all instructions in block BB, returning true if successful, false |
326 | | /// if we can't evaluate it. NewBB returns the next BB that control flows into, |
327 | | /// or null upon return. |
328 | | bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, |
329 | 4.98k | BasicBlock *&NextBB) { |
330 | 4.98k | // This is the main evaluation loop. |
331 | 19.0k | while (true) { |
332 | 19.0k | Constant *InstResult = nullptr; |
333 | 19.0k | |
334 | 19.0k | LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n"); |
335 | 19.0k | |
336 | 19.0k | if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) { |
337 | 3.93k | if (!SI->isSimple()) { |
338 | 32 | LLVM_DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n"); |
339 | 32 | return false; // no volatile/atomic accesses. |
340 | 32 | } |
341 | 3.90k | Constant *Ptr = getVal(SI->getOperand(1)); |
342 | 3.90k | if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) { |
343 | 3.22k | LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr); |
344 | 3.22k | Ptr = FoldedPtr; |
345 | 3.22k | LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n"); |
346 | 3.22k | } |
347 | 3.90k | if (!isSimpleEnoughPointerToCommit(Ptr)) { |
348 | 20 | // If this is too complex for us to commit, reject it. |
349 | 20 | LLVM_DEBUG( |
350 | 20 | dbgs() << "Pointer is too complex for us to evaluate store."); |
351 | 20 | return false; |
352 | 20 | } |
353 | 3.88k | |
354 | 3.88k | Constant *Val = getVal(SI->getOperand(0)); |
355 | 3.88k | |
356 | 3.88k | // If this might be too difficult for the backend to handle (e.g. the addr |
357 | 3.88k | // of one global variable divided by another) then we can't commit it. |
358 | 3.88k | if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) { |
359 | 13 | LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. " |
360 | 13 | << *Val << "\n"); |
361 | 13 | return false; |
362 | 13 | } |
363 | 3.86k | |
364 | 3.86k | if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) { |
365 | 3.20k | if (CE->getOpcode() == Instruction::BitCast) { |
366 | 42 | LLVM_DEBUG(dbgs() |
367 | 42 | << "Attempting to resolve bitcast on constant ptr.\n"); |
368 | 42 | // If we're evaluating a store through a bitcast, then we need |
369 | 42 | // to pull the bitcast off the pointer type and push it onto the |
370 | 42 | // stored value. In order to push the bitcast onto the stored value, |
371 | 42 | // a bitcast from the pointer's element type to Val's type must be |
372 | 42 | // legal. If it's not, we can try introspecting the type to find a |
373 | 42 | // legal conversion. |
374 | 42 | |
375 | 96 | auto castValTy = [&](Constant *P) -> Constant * { |
376 | 96 | Type *Ty = cast<PointerType>(P->getType())->getElementType(); |
377 | 96 | if (Constant *FV = ConstantFoldLoadThroughBitcast(Val, Ty, DL)) { |
378 | 38 | Ptr = P; |
379 | 38 | return FV; |
380 | 38 | } |
381 | 58 | return nullptr; |
382 | 58 | }; |
383 | 42 | |
384 | 42 | Constant *NewVal = |
385 | 42 | evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, castValTy); |
386 | 42 | if (!NewVal) { |
387 | 4 | LLVM_DEBUG(dbgs() << "Failed to bitcast constant ptr, can not " |
388 | 4 | "evaluate.\n"); |
389 | 4 | return false; |
390 | 4 | } |
391 | 38 | |
392 | 38 | Val = NewVal; |
393 | 38 | LLVM_DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n"); |
394 | 38 | } |
395 | 3.20k | } |
396 | 3.86k | |
397 | 3.86k | MutatedMemory[Ptr] = Val; |
398 | 15.0k | } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) { |
399 | 256 | InstResult = ConstantExpr::get(BO->getOpcode(), |
400 | 256 | getVal(BO->getOperand(0)), |
401 | 256 | getVal(BO->getOperand(1))); |
402 | 256 | LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " |
403 | 256 | << *InstResult << "\n"); |
404 | 14.8k | } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) { |
405 | 142 | InstResult = ConstantExpr::getCompare(CI->getPredicate(), |
406 | 142 | getVal(CI->getOperand(0)), |
407 | 142 | getVal(CI->getOperand(1))); |
408 | 142 | LLVM_DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult |
409 | 142 | << "\n"); |
410 | 14.6k | } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) { |
411 | 1.36k | InstResult = ConstantExpr::getCast(CI->getOpcode(), |
412 | 1.36k | getVal(CI->getOperand(0)), |
413 | 1.36k | CI->getType()); |
414 | 1.36k | LLVM_DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult |
415 | 1.36k | << "\n"); |
416 | 13.3k | } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) { |
417 | 24 | InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)), |
418 | 24 | getVal(SI->getOperand(1)), |
419 | 24 | getVal(SI->getOperand(2))); |
420 | 24 | LLVM_DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult |
421 | 24 | << "\n"); |
422 | 13.2k | } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) { |
423 | 2 | InstResult = ConstantExpr::getExtractValue( |
424 | 2 | getVal(EVI->getAggregateOperand()), EVI->getIndices()); |
425 | 2 | LLVM_DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: " |
426 | 2 | << *InstResult << "\n"); |
427 | 13.2k | } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) { |
428 | 23 | InstResult = ConstantExpr::getInsertValue( |
429 | 23 | getVal(IVI->getAggregateOperand()), |
430 | 23 | getVal(IVI->getInsertedValueOperand()), IVI->getIndices()); |
431 | 23 | LLVM_DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: " |
432 | 23 | << *InstResult << "\n"); |
433 | 13.2k | } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) { |
434 | 2.34k | Constant *P = getVal(GEP->getOperand(0)); |
435 | 2.34k | SmallVector<Constant*, 8> GEPOps; |
436 | 2.34k | for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); |
437 | 9.08k | i != e; ++i6.74k ) |
438 | 6.74k | GEPOps.push_back(getVal(*i)); |
439 | 2.34k | InstResult = |
440 | 2.34k | ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps, |
441 | 2.34k | cast<GEPOperator>(GEP)->isInBounds()); |
442 | 2.34k | LLVM_DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult << "\n"); |
443 | 10.9k | } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) { |
444 | 783 | if (!LI->isSimple()) { |
445 | 4 | LLVM_DEBUG( |
446 | 4 | dbgs() << "Found a Load! Not a simple load, can not evaluate.\n"); |
447 | 4 | return false; // no volatile/atomic accesses. |
448 | 4 | } |
449 | 779 | |
450 | 779 | Constant *Ptr = getVal(LI->getOperand(0)); |
451 | 779 | if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) { |
452 | 136 | Ptr = FoldedPtr; |
453 | 136 | LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant " |
454 | 136 | "folding: " |
455 | 136 | << *Ptr << "\n"); |
456 | 136 | } |
457 | 779 | InstResult = ComputeLoadResult(Ptr); |
458 | 779 | if (!InstResult) { |
459 | 64 | LLVM_DEBUG( |
460 | 64 | dbgs() << "Failed to compute load result. Can not evaluate load." |
461 | 64 | "\n"); |
462 | 64 | return false; // Could not evaluate load. |
463 | 64 | } |
464 | 715 | |
465 | 715 | LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n"); |
466 | 10.1k | } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) { |
467 | 1.72k | if (AI->isArrayAllocation()) { |
468 | 0 | LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n"); |
469 | 0 | return false; // Cannot handle array allocs. |
470 | 0 | } |
471 | 1.72k | Type *Ty = AI->getAllocatedType(); |
472 | 1.72k | AllocaTmps.push_back(llvm::make_unique<GlobalVariable>( |
473 | 1.72k | Ty, false, GlobalValue::InternalLinkage, UndefValue::get(Ty), |
474 | 1.72k | AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal, |
475 | 1.72k | AI->getType()->getPointerAddressSpace())); |
476 | 1.72k | InstResult = AllocaTmps.back().get(); |
477 | 1.72k | LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n"); |
478 | 8.40k | } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)3.11k ) { |
479 | 5.32k | CallSite CS(&*CurInst); |
480 | 5.32k | |
481 | 5.32k | // Debug info can safely be ignored here. |
482 | 5.32k | if (isa<DbgInfoIntrinsic>(CS.getInstruction())) { |
483 | 0 | LLVM_DEBUG(dbgs() << "Ignoring debug info.\n"); |
484 | 0 | ++CurInst; |
485 | 0 | continue; |
486 | 0 | } |
487 | 5.32k | |
488 | 5.32k | // Cannot handle inline asm. |
489 | 5.32k | if (isa<InlineAsm>(CS.getCalledValue())) { |
490 | 4 | LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n"); |
491 | 4 | return false; |
492 | 4 | } |
493 | 5.32k | |
494 | 5.32k | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) { |
495 | 971 | if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) { |
496 | 116 | if (MSI->isVolatile()) { |
497 | 0 | LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset " |
498 | 0 | << "intrinsic.\n"); |
499 | 0 | return false; |
500 | 0 | } |
501 | 116 | Constant *Ptr = getVal(MSI->getDest()); |
502 | 116 | Constant *Val = getVal(MSI->getValue()); |
503 | 116 | Constant *DestVal = ComputeLoadResult(getVal(Ptr)); |
504 | 116 | if (Val->isNullValue() && DestVal && DestVal->isNullValue()113 ) { |
505 | 106 | // This memset is a no-op. |
506 | 106 | LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n"); |
507 | 106 | ++CurInst; |
508 | 106 | continue; |
509 | 106 | } |
510 | 865 | } |
511 | 865 | |
512 | 865 | if (II->isLifetimeStartOrEnd()) { |
513 | 719 | LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n"); |
514 | 719 | ++CurInst; |
515 | 719 | continue; |
516 | 719 | } |
517 | 146 | |
518 | 146 | if (II->getIntrinsicID() == Intrinsic::invariant_start) { |
519 | 119 | // We don't insert an entry into Values, as it doesn't have a |
520 | 119 | // meaningful return value. |
521 | 119 | if (!II->use_empty()) { |
522 | 3 | LLVM_DEBUG(dbgs() |
523 | 3 | << "Found unused invariant_start. Can't evaluate.\n"); |
524 | 3 | return false; |
525 | 3 | } |
526 | 116 | ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0)); |
527 | 116 | Value *PtrArg = getVal(II->getArgOperand(1)); |
528 | 116 | Value *Ptr = PtrArg->stripPointerCasts(); |
529 | 116 | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { |
530 | 116 | Type *ElemTy = GV->getValueType(); |
531 | 116 | if (!Size->isMinusOne() && |
532 | 116 | Size->getValue().getLimitedValue() >= |
533 | 115 | DL.getTypeStoreSize(ElemTy)) { |
534 | 113 | Invariants.insert(GV); |
535 | 113 | LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: " |
536 | 113 | << *GV << "\n"); |
537 | 113 | } else { |
538 | 3 | LLVM_DEBUG(dbgs() |
539 | 3 | << "Found a global var, but can not treat it as an " |
540 | 3 | "invariant.\n"); |
541 | 3 | } |
542 | 116 | } |
543 | 116 | // Continue even if we do nothing. |
544 | 116 | ++CurInst; |
545 | 116 | continue; |
546 | 116 | } else if (27 II->getIntrinsicID() == Intrinsic::assume27 ) { |
547 | 1 | LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n"); |
548 | 1 | ++CurInst; |
549 | 1 | continue; |
550 | 26 | } else if (II->getIntrinsicID() == Intrinsic::sideeffect) { |
551 | 1 | LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n"); |
552 | 1 | ++CurInst; |
553 | 1 | continue; |
554 | 1 | } |
555 | 25 | |
556 | 25 | LLVM_DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n"); |
557 | 25 | return false; |
558 | 25 | } |
559 | 4.35k | |
560 | 4.35k | // Resolve function pointers. |
561 | 4.35k | SmallVector<Constant *, 8> Formals; |
562 | 4.35k | Function *Callee = getCalleeWithFormalArgs(CS, Formals); |
563 | 4.35k | if (!Callee || Callee->isInterposable()4.34k ) { |
564 | 4 | LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n"); |
565 | 4 | return false; // Cannot resolve. |
566 | 4 | } |
567 | 4.34k | |
568 | 4.34k | if (Callee->isDeclaration()) { |
569 | 707 | // If this is a function we can constant fold, do it. |
570 | 707 | if (Constant *C = ConstantFoldCall(cast<CallBase>(CS.getInstruction()), |
571 | 2 | Callee, Formals, TLI)) { |
572 | 2 | InstResult = castCallResultIfNeeded(CS.getCalledValue(), C); |
573 | 2 | if (!InstResult) |
574 | 0 | return false; |
575 | 2 | LLVM_DEBUG(dbgs() << "Constant folded function call. Result: " |
576 | 2 | << *InstResult << "\n"); |
577 | 705 | } else { |
578 | 705 | LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n"); |
579 | 705 | return false; |
580 | 705 | } |
581 | 3.64k | } else { |
582 | 3.64k | if (Callee->getFunctionType()->isVarArg()) { |
583 | 0 | LLVM_DEBUG(dbgs() << "Can not constant fold vararg function call.\n"); |
584 | 0 | return false; |
585 | 0 | } |
586 | 3.64k | |
587 | 3.64k | Constant *RetVal = nullptr; |
588 | 3.64k | // Execute the call, if successful, use the return value. |
589 | 3.64k | ValueStack.emplace_back(); |
590 | 3.64k | if (!EvaluateFunction(Callee, RetVal, Formals)) { |
591 | 1.00k | LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n"); |
592 | 1.00k | return false; |
593 | 1.00k | } |
594 | 2.63k | ValueStack.pop_back(); |
595 | 2.63k | InstResult = castCallResultIfNeeded(CS.getCalledValue(), RetVal); |
596 | 2.63k | if (RetVal && !InstResult1.98k ) |
597 | 0 | return false; |
598 | 2.63k | |
599 | 2.63k | if (InstResult) { |
600 | 1.98k | LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: " |
601 | 1.98k | << *InstResult << "\n\n"); |
602 | 1.98k | } else { |
603 | 646 | LLVM_DEBUG(dbgs() |
604 | 646 | << "Successfully evaluated function. Result: 0\n\n"); |
605 | 646 | } |
606 | 2.63k | } |
607 | 4.34k | } else if (3.07k CurInst->isTerminator()3.07k ) { |
608 | 3.07k | LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n"); |
609 | 3.07k | |
610 | 3.07k | if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) { |
611 | 259 | if (BI->isUnconditional()) { |
612 | 106 | NextBB = BI->getSuccessor(0); |
613 | 153 | } else { |
614 | 153 | ConstantInt *Cond = |
615 | 153 | dyn_cast<ConstantInt>(getVal(BI->getCondition())); |
616 | 153 | if (!Cond) return false0 ; // Cannot determine. |
617 | 153 | |
618 | 153 | NextBB = BI->getSuccessor(!Cond->getZExtValue()); |
619 | 153 | } |
620 | 2.81k | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) { |
621 | 0 | ConstantInt *Val = |
622 | 0 | dyn_cast<ConstantInt>(getVal(SI->getCondition())); |
623 | 0 | if (!Val) return false; // Cannot determine. |
624 | 0 | NextBB = SI->findCaseValue(Val)->getCaseSuccessor(); |
625 | 2.81k | } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) { |
626 | 0 | Value *Val = getVal(IBI->getAddress())->stripPointerCasts(); |
627 | 0 | if (BlockAddress *BA = dyn_cast<BlockAddress>(Val)) |
628 | 0 | NextBB = BA->getBasicBlock(); |
629 | 0 | else |
630 | 0 | return false; // Cannot determine. |
631 | 2.81k | } else if (isa<ReturnInst>(CurInst)) { |
632 | 2.81k | NextBB = nullptr; |
633 | 2.81k | } else { |
634 | 0 | // invoke, unwind, resume, unreachable. |
635 | 0 | LLVM_DEBUG(dbgs() << "Can not handle terminator."); |
636 | 0 | return false; // Cannot handle this terminator. |
637 | 0 | } |
638 | 3.07k | |
639 | 3.07k | // We succeeded at evaluating this block! |
640 | 3.07k | LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n"); |
641 | 3.07k | return true; |
642 | 3.07k | } else { |
643 | 0 | // Did not know how to evaluate this! |
644 | 0 | LLVM_DEBUG( |
645 | 0 | dbgs() << "Failed to evaluate block due to unhandled instruction." |
646 | 0 | "\n"); |
647 | 0 | return false; |
648 | 0 | } |
649 | 13.0k | |
650 | 13.0k | if (!CurInst->use_empty()) { |
651 | 6.67k | if (auto *FoldedInstResult = ConstantFoldConstant(InstResult, DL, TLI)) |
652 | 3.65k | InstResult = FoldedInstResult; |
653 | 6.67k | |
654 | 6.67k | setVal(&*CurInst, InstResult); |
655 | 6.67k | } |
656 | 13.0k | |
657 | 13.0k | // If we just processed an invoke, we finished evaluating the block. |
658 | 13.0k | if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) { |
659 | 29 | NextBB = II->getNormalDest(); |
660 | 29 | LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n"); |
661 | 29 | return true; |
662 | 29 | } |
663 | 13.0k | |
664 | 13.0k | // Advance program counter. |
665 | 13.0k | ++CurInst; |
666 | 13.0k | } |
667 | 4.98k | } |
668 | | |
669 | | /// Evaluate a call to function F, returning true if successful, false if we |
670 | | /// can't evaluate it. ActualArgs contains the formal arguments for the |
671 | | /// function. |
672 | | bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal, |
673 | 4.74k | const SmallVectorImpl<Constant*> &ActualArgs) { |
674 | 4.74k | // Check to see if this function is already executing (recursion). If so, |
675 | 4.74k | // bail out. TODO: we might want to accept limited recursion. |
676 | 4.74k | if (is_contained(CallStack, F)) |
677 | 0 | return false; |
678 | 4.74k | |
679 | 4.74k | CallStack.push_back(F); |
680 | 4.74k | |
681 | 4.74k | // Initialize arguments to the incoming values specified. |
682 | 4.74k | unsigned ArgNo = 0; |
683 | 9.46k | for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; |
684 | 4.74k | ++AI, ++ArgNo4.71k ) |
685 | 4.71k | setVal(&*AI, ActualArgs[ArgNo]); |
686 | 4.74k | |
687 | 4.74k | // ExecutedBlocks - We only handle non-looping, non-recursive code. As such, |
688 | 4.74k | // we can only evaluate any one basic block at most once. This set keeps |
689 | 4.74k | // track of what we have executed so we can detect recursive cases etc. |
690 | 4.74k | SmallPtrSet<BasicBlock*, 32> ExecutedBlocks; |
691 | 4.74k | |
692 | 4.74k | // CurBB - The current basic block we're evaluating. |
693 | 4.74k | BasicBlock *CurBB = &F->front(); |
694 | 4.74k | |
695 | 4.74k | BasicBlock::iterator CurInst = CurBB->begin(); |
696 | 4.74k | |
697 | 4.98k | while (true) { |
698 | 4.98k | BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings. |
699 | 4.98k | LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n"); |
700 | 4.98k | |
701 | 4.98k | if (!EvaluateBlock(CurInst, NextBB)) |
702 | 1.88k | return false; |
703 | 3.10k | |
704 | 3.10k | if (!NextBB) { |
705 | 2.81k | // Successfully running until there's no next block means that we found |
706 | 2.81k | // the return. Fill it the return value and pop the call stack. |
707 | 2.81k | ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator()); |
708 | 2.81k | if (RI->getNumOperands()) |
709 | 2.07k | RetVal = getVal(RI->getOperand(0)); |
710 | 2.81k | CallStack.pop_back(); |
711 | 2.81k | return true; |
712 | 2.81k | } |
713 | 288 | |
714 | 288 | // Okay, we succeeded in evaluating this control flow. See if we have |
715 | 288 | // executed the new block before. If so, we have a looping function, |
716 | 288 | // which we cannot evaluate in reasonable time. |
717 | 288 | if (!ExecutedBlocks.insert(NextBB).second) |
718 | 48 | return false; // looped! |
719 | 240 | |
720 | 240 | // Okay, we have never been in this block before. Check to see if there |
721 | 240 | // are any PHI nodes. If so, evaluate them with information about where |
722 | 240 | // we came from. |
723 | 240 | PHINode *PN = nullptr; |
724 | 240 | for (CurInst = NextBB->begin(); |
725 | 366 | (PN = dyn_cast<PHINode>(CurInst)); ++CurInst126 ) |
726 | 126 | setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB))); |
727 | 240 | |
728 | 240 | // Advance to the next block. |
729 | 240 | CurBB = NextBB; |
730 | 240 | } |
731 | 4.74k | } |