/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Transforms/Utils/Evaluator.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- Evaluator.cpp - LLVM IR evaluator ----------------------------------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // Function evaluator for LLVM IR. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #include "llvm/Transforms/Utils/Evaluator.h" |
15 | | #include "llvm/Analysis/ConstantFolding.h" |
16 | | #include "llvm/IR/BasicBlock.h" |
17 | | #include "llvm/IR/CallSite.h" |
18 | | #include "llvm/IR/Constants.h" |
19 | | #include "llvm/IR/DataLayout.h" |
20 | | #include "llvm/IR/DerivedTypes.h" |
21 | | #include "llvm/IR/DiagnosticPrinter.h" |
22 | | #include "llvm/IR/GlobalVariable.h" |
23 | | #include "llvm/IR/Instructions.h" |
24 | | #include "llvm/IR/IntrinsicInst.h" |
25 | | #include "llvm/IR/Operator.h" |
26 | | #include "llvm/Support/Debug.h" |
27 | | #include "llvm/Support/raw_ostream.h" |
28 | | |
29 | | #define DEBUG_TYPE "evaluator" |
30 | | |
31 | | using namespace llvm; |
32 | | |
33 | | static inline bool |
34 | | isSimpleEnoughValueToCommit(Constant *C, |
35 | | SmallPtrSetImpl<Constant *> &SimpleConstants, |
36 | | const DataLayout &DL); |
37 | | |
38 | | /// Return true if the specified constant can be handled by the code generator. |
39 | | /// We don't want to generate something like: |
40 | | /// void *X = &X/42; |
41 | | /// because the code generator doesn't have a relocation that can handle that. |
42 | | /// |
43 | | /// This function should be called if C was not found (but just got inserted) |
44 | | /// in SimpleConstants to avoid having to rescan the same constants all the |
45 | | /// time. |
46 | | static bool |
47 | | isSimpleEnoughValueToCommitHelper(Constant *C, |
48 | | SmallPtrSetImpl<Constant *> &SimpleConstants, |
49 | 708 | const DataLayout &DL) { |
50 | 708 | // Simple global addresses are supported, do not allow dllimport or |
51 | 708 | // thread-local globals. |
52 | 708 | if (auto *GV = dyn_cast<GlobalValue>(C)) |
53 | 214 | return !GV->hasDLLImportStorageClass() && 214 !GV->isThreadLocal()210 ; |
54 | 494 | |
55 | 494 | // Simple integer, undef, constant aggregate zero, etc are all supported. |
56 | 494 | if (494 C->getNumOperands() == 0 || 494 isa<BlockAddress>(C)257 ) |
57 | 237 | return true; |
58 | 257 | |
59 | 257 | // Aggregate values are safe if all their elements are. |
60 | 257 | if (257 isa<ConstantAggregate>(C)257 ) { |
61 | 1 | for (Value *Op : C->operands()) |
62 | 2 | if (2 !isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL)2 ) |
63 | 0 | return false; |
64 | 1 | return true; |
65 | 1 | } |
66 | 256 | |
67 | 256 | // We don't know exactly what relocations are allowed in constant expressions, |
68 | 256 | // so we allow &global+constantoffset, which is safe and uniformly supported |
69 | 256 | // across targets. |
70 | 256 | ConstantExpr *CE = cast<ConstantExpr>(C); |
71 | 256 | switch (CE->getOpcode()) { |
72 | 49 | case Instruction::BitCast: |
73 | 49 | // Bitcast is fine if the casted value is fine. |
74 | 49 | return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
75 | 256 | |
76 | 4 | case Instruction::IntToPtr: |
77 | 4 | case Instruction::PtrToInt: |
78 | 4 | // int <=> ptr is fine if the int type is the same size as the |
79 | 4 | // pointer type. |
80 | 4 | if (DL.getTypeSizeInBits(CE->getType()) != |
81 | 4 | DL.getTypeSizeInBits(CE->getOperand(0)->getType())) |
82 | 2 | return false; |
83 | 2 | return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
84 | 2 | |
85 | 2 | // GEP is fine if it is simple + constant offset. |
86 | 201 | case Instruction::GetElementPtr: |
87 | 649 | for (unsigned i = 1, e = CE->getNumOperands(); i != e649 ; ++i448 ) |
88 | 448 | if (448 !isa<ConstantInt>(CE->getOperand(i))448 ) |
89 | 0 | return false; |
90 | 201 | return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
91 | 201 | |
92 | 0 | case Instruction::Add: |
93 | 0 | // We allow simple+cst. |
94 | 0 | if (!isa<ConstantInt>(CE->getOperand(1))) |
95 | 0 | return false; |
96 | 0 | return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
97 | 2 | } |
98 | 2 | return false; |
99 | 2 | } |
100 | | |
101 | | static inline bool |
102 | | isSimpleEnoughValueToCommit(Constant *C, |
103 | | SmallPtrSetImpl<Constant *> &SimpleConstants, |
104 | 1.64k | const DataLayout &DL) { |
105 | 1.64k | // If we already checked this constant, we win. |
106 | 1.64k | if (!SimpleConstants.insert(C).second) |
107 | 937 | return true; |
108 | 708 | // Check the constant. |
109 | 708 | return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL); |
110 | 708 | } |
111 | | |
112 | | /// Return true if this constant is simple enough for us to understand. In |
113 | | /// particular, if it is a cast to anything other than from one pointer type to |
114 | | /// another pointer type, we punt. We basically just support direct accesses to |
115 | | /// globals and GEP's of globals. This should be kept up to date with |
116 | | /// CommitValueTo. |
117 | 1.40k | static bool isSimpleEnoughPointerToCommit(Constant *C) { |
118 | 1.40k | // Conservatively, avoid aggregate types. This is because we don't |
119 | 1.40k | // want to worry about them partially overlapping other stores. |
120 | 1.40k | if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType()) |
121 | 0 | return false; |
122 | 1.40k | |
123 | 1.40k | if (GlobalVariable *1.40k GV1.40k = dyn_cast<GlobalVariable>(C)) |
124 | 1.40k | // Do not allow weak/*_odr/linkonce linkage or external globals. |
125 | 109 | return GV->hasUniqueInitializer(); |
126 | 1.29k | |
127 | 1.29k | if (ConstantExpr *1.29k CE1.29k = dyn_cast<ConstantExpr>(C)) { |
128 | 1.29k | // Handle a constantexpr gep. |
129 | 1.29k | if (CE->getOpcode() == Instruction::GetElementPtr && |
130 | 1.29k | isa<GlobalVariable>(CE->getOperand(0)) && |
131 | 1.29k | cast<GEPOperator>(CE)->isInBounds()1.29k ) { |
132 | 1.29k | GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); |
133 | 1.29k | // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or |
134 | 1.29k | // external globals. |
135 | 1.29k | if (!GV->hasUniqueInitializer()) |
136 | 2 | return false; |
137 | 1.28k | |
138 | 1.28k | // The first index must be zero. |
139 | 1.28k | ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin())); |
140 | 1.28k | if (!CI || 1.28k !CI->isZero()1.28k ) return false0 ; |
141 | 1.28k | |
142 | 1.28k | // The remaining indices must be compile-time known integers within the |
143 | 1.28k | // notional bounds of the corresponding static array types. |
144 | 1.28k | if (1.28k !CE->isGEPWithNoNotionalOverIndexing()1.28k ) |
145 | 0 | return false; |
146 | 1.28k | |
147 | 1.28k | return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); |
148 | 1.28k | |
149 | 1.28k | // A constantexpr bitcast from a pointer to another pointer is a no-op, |
150 | 1.28k | // and we know how to evaluate it by moving the bitcast from the pointer |
151 | 1.28k | // operand to the value operand. |
152 | 1 | } else if (1 CE->getOpcode() == Instruction::BitCast && |
153 | 1 | isa<GlobalVariable>(CE->getOperand(0))1 ) { |
154 | 1 | // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or |
155 | 1 | // external globals. |
156 | 1 | return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer(); |
157 | 1 | } |
158 | 0 | } |
159 | 0 |
|
160 | 0 | return false; |
161 | 0 | } |
162 | | |
163 | | /// Return the value that would be computed by a load from P after the stores |
164 | | /// reflected by 'memory' have been performed. If we can't decide, return null. |
165 | 279 | Constant *Evaluator::ComputeLoadResult(Constant *P) { |
166 | 279 | // If this memory location has been recently stored, use the stored value: it |
167 | 279 | // is the most up-to-date. |
168 | 279 | DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P); |
169 | 279 | if (I != MutatedMemory.end()279 ) return I->second207 ; |
170 | 72 | |
171 | 72 | // Access it. |
172 | 72 | if (GlobalVariable *72 GV72 = dyn_cast<GlobalVariable>(P)) { |
173 | 47 | if (GV->hasDefinitiveInitializer()) |
174 | 35 | return GV->getInitializer(); |
175 | 12 | return nullptr; |
176 | 12 | } |
177 | 25 | |
178 | 25 | // Handle a constantexpr getelementptr. |
179 | 25 | if (ConstantExpr *25 CE25 = dyn_cast<ConstantExpr>(P)) |
180 | 22 | if (22 CE->getOpcode() == Instruction::GetElementPtr && |
181 | 22 | isa<GlobalVariable>(CE->getOperand(0))22 ) { |
182 | 22 | GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0)); |
183 | 22 | if (GV->hasDefinitiveInitializer()) |
184 | 18 | return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); |
185 | 7 | } |
186 | 7 | |
187 | 7 | return nullptr; // don't know how to evaluate. |
188 | 7 | } |
189 | | |
190 | | /// Evaluate all instructions in block BB, returning true if successful, false |
191 | | /// if we can't evaluate it. NewBB returns the next BB that control flows into, |
192 | | /// or null upon return. |
193 | | bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, |
194 | 1.56k | BasicBlock *&NextBB) { |
195 | 1.56k | // This is the main evaluation loop. |
196 | 5.52k | while (15.52k ) { |
197 | 5.52k | Constant *InstResult = nullptr; |
198 | 5.52k | |
199 | 5.52k | DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n"); |
200 | 5.52k | |
201 | 5.52k | if (StoreInst *SI5.52k = dyn_cast<StoreInst>(CurInst)) { |
202 | 1.40k | if (!SI->isSimple()1.40k ) { |
203 | 0 | DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n"); |
204 | 0 | return false; // no volatile/atomic accesses. |
205 | 0 | } |
206 | 1.40k | Constant *Ptr = getVal(SI->getOperand(1)); |
207 | 1.40k | if (auto *FoldedPtr1.40k = ConstantFoldConstant(Ptr, DL, TLI)) { |
208 | 1.29k | DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr); |
209 | 1.29k | Ptr = FoldedPtr; |
210 | 1.29k | DEBUG(dbgs() << "; To: " << *Ptr << "\n"); |
211 | 1.29k | } |
212 | 1.40k | if (!isSimpleEnoughPointerToCommit(Ptr)1.40k ) { |
213 | 9 | // If this is too complex for us to commit, reject it. |
214 | 9 | DEBUG(dbgs() << "Pointer is too complex for us to evaluate store."); |
215 | 9 | return false; |
216 | 9 | } |
217 | 1.39k | |
218 | 1.39k | Constant *Val = getVal(SI->getOperand(0)); |
219 | 1.39k | |
220 | 1.39k | // If this might be too difficult for the backend to handle (e.g. the addr |
221 | 1.39k | // of one global variable divided by another) then we can't commit it. |
222 | 1.39k | if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)1.39k ) { |
223 | 12 | DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val |
224 | 12 | << "\n"); |
225 | 12 | return false; |
226 | 12 | } |
227 | 1.37k | |
228 | 1.37k | if (ConstantExpr *1.37k CE1.37k = dyn_cast<ConstantExpr>(Ptr)) { |
229 | 1.28k | if (CE->getOpcode() == Instruction::BitCast1.28k ) { |
230 | 1 | DEBUG(dbgs() << "Attempting to resolve bitcast on constant ptr.\n"); |
231 | 1 | // If we're evaluating a store through a bitcast, then we need |
232 | 1 | // to pull the bitcast off the pointer type and push it onto the |
233 | 1 | // stored value. |
234 | 1 | Ptr = CE->getOperand(0); |
235 | 1 | |
236 | 1 | Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType(); |
237 | 1 | |
238 | 1 | // In order to push the bitcast onto the stored value, a bitcast |
239 | 1 | // from NewTy to Val's type must be legal. If it's not, we can try |
240 | 1 | // introspecting NewTy to find a legal conversion. |
241 | 2 | while (!Val->getType()->canLosslesslyBitCastTo(NewTy)2 ) { |
242 | 1 | // If NewTy is a struct, we can convert the pointer to the struct |
243 | 1 | // into a pointer to its first member. |
244 | 1 | // FIXME: This could be extended to support arrays as well. |
245 | 1 | if (StructType *STy1 = dyn_cast<StructType>(NewTy)) { |
246 | 1 | NewTy = STy->getTypeAtIndex(0U); |
247 | 1 | |
248 | 1 | IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32); |
249 | 1 | Constant *IdxZero = ConstantInt::get(IdxTy, 0, false); |
250 | 1 | Constant * const IdxList[] = {IdxZero, IdxZero}; |
251 | 1 | |
252 | 1 | Ptr = ConstantExpr::getGetElementPtr(nullptr, Ptr, IdxList); |
253 | 1 | if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) |
254 | 1 | Ptr = FoldedPtr; |
255 | 1 | |
256 | 1 | // If we can't improve the situation by introspecting NewTy, |
257 | 1 | // we have to give up. |
258 | 0 | } else { |
259 | 0 | DEBUG(dbgs() << "Failed to bitcast constant ptr, can not " |
260 | 0 | "evaluate.\n"); |
261 | 0 | return false; |
262 | 0 | } |
263 | 1 | } |
264 | 1 | |
265 | 1 | // If we found compatible types, go ahead and push the bitcast |
266 | 1 | // onto the stored value. |
267 | 1 | Val = ConstantExpr::getBitCast(Val, NewTy); |
268 | 1 | |
269 | 1 | DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n"); |
270 | 1 | } |
271 | 1.28k | } |
272 | 1.37k | |
273 | 1.37k | MutatedMemory[Ptr] = Val; |
274 | 5.52k | } else if (BinaryOperator *4.12k BO4.12k = dyn_cast<BinaryOperator>(CurInst)) { |
275 | 196 | InstResult = ConstantExpr::get(BO->getOpcode(), |
276 | 196 | getVal(BO->getOperand(0)), |
277 | 196 | getVal(BO->getOperand(1))); |
278 | 196 | DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " << *InstResult |
279 | 196 | << "\n"); |
280 | 4.12k | } else if (CmpInst *3.92k CI3.92k = dyn_cast<CmpInst>(CurInst)) { |
281 | 96 | InstResult = ConstantExpr::getCompare(CI->getPredicate(), |
282 | 96 | getVal(CI->getOperand(0)), |
283 | 96 | getVal(CI->getOperand(1))); |
284 | 96 | DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult |
285 | 96 | << "\n"); |
286 | 3.92k | } else if (CastInst *3.83k CI3.83k = dyn_cast<CastInst>(CurInst)) { |
287 | 259 | InstResult = ConstantExpr::getCast(CI->getOpcode(), |
288 | 259 | getVal(CI->getOperand(0)), |
289 | 259 | CI->getType()); |
290 | 259 | DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult |
291 | 259 | << "\n"); |
292 | 3.83k | } else if (SelectInst *3.57k SI3.57k = dyn_cast<SelectInst>(CurInst)) { |
293 | 8 | InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)), |
294 | 8 | getVal(SI->getOperand(1)), |
295 | 8 | getVal(SI->getOperand(2))); |
296 | 8 | DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult |
297 | 8 | << "\n"); |
298 | 3.57k | } else if (auto *3.56k EVI3.56k = dyn_cast<ExtractValueInst>(CurInst)) { |
299 | 338 | InstResult = ConstantExpr::getExtractValue( |
300 | 338 | getVal(EVI->getAggregateOperand()), EVI->getIndices()); |
301 | 338 | DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: " << *InstResult |
302 | 338 | << "\n"); |
303 | 3.56k | } else if (auto *3.22k IVI3.22k = dyn_cast<InsertValueInst>(CurInst)) { |
304 | 175 | InstResult = ConstantExpr::getInsertValue( |
305 | 175 | getVal(IVI->getAggregateOperand()), |
306 | 175 | getVal(IVI->getInsertedValueOperand()), IVI->getIndices()); |
307 | 175 | DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: " << *InstResult |
308 | 175 | << "\n"); |
309 | 3.22k | } else if (GetElementPtrInst *3.05k GEP3.05k = dyn_cast<GetElementPtrInst>(CurInst)) { |
310 | 742 | Constant *P = getVal(GEP->getOperand(0)); |
311 | 742 | SmallVector<Constant*, 8> GEPOps; |
312 | 742 | for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); |
313 | 2.36k | i != e2.36k ; ++i1.62k ) |
314 | 1.62k | GEPOps.push_back(getVal(*i)); |
315 | 742 | InstResult = |
316 | 742 | ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps, |
317 | 742 | cast<GEPOperator>(GEP)->isInBounds()); |
318 | 742 | DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult |
319 | 742 | << "\n"); |
320 | 3.05k | } else if (LoadInst *2.30k LI2.30k = dyn_cast<LoadInst>(CurInst)) { |
321 | 275 | |
322 | 275 | if (!LI->isSimple()275 ) { |
323 | 0 | DEBUG(dbgs() << "Found a Load! Not a simple load, can not evaluate.\n"); |
324 | 0 | return false; // no volatile/atomic accesses. |
325 | 0 | } |
326 | 275 | |
327 | 275 | Constant *Ptr = getVal(LI->getOperand(0)); |
328 | 275 | if (auto *FoldedPtr275 = ConstantFoldConstant(Ptr, DL, TLI)) { |
329 | 204 | Ptr = FoldedPtr; |
330 | 204 | DEBUG(dbgs() << "Found a constant pointer expression, constant " |
331 | 204 | "folding: " << *Ptr << "\n"); |
332 | 204 | } |
333 | 275 | InstResult = ComputeLoadResult(Ptr); |
334 | 275 | if (!InstResult275 ) { |
335 | 16 | DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load." |
336 | 16 | "\n"); |
337 | 16 | return false; // Could not evaluate load. |
338 | 16 | } |
339 | 259 | |
340 | 259 | DEBUG259 (dbgs() << "Evaluated load: " << *InstResult << "\n"); |
341 | 2.30k | } else if (AllocaInst *2.03k AI2.03k = dyn_cast<AllocaInst>(CurInst)) { |
342 | 75 | if (AI->isArrayAllocation()75 ) { |
343 | 0 | DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n"); |
344 | 0 | return false; // Cannot handle array allocs. |
345 | 0 | } |
346 | 75 | Type *Ty = AI->getAllocatedType(); |
347 | 75 | AllocaTmps.push_back( |
348 | 75 | make_unique<GlobalVariable>(Ty, false, GlobalValue::InternalLinkage, |
349 | 75 | UndefValue::get(Ty), AI->getName())); |
350 | 75 | InstResult = AllocaTmps.back().get(); |
351 | 75 | DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n"); |
352 | 2.03k | } else if (1.95k isa<CallInst>(CurInst) || 1.95k isa<InvokeInst>(CurInst)751 ) { |
353 | 1.21k | CallSite CS(&*CurInst); |
354 | 1.21k | |
355 | 1.21k | // Debug info can safely be ignored here. |
356 | 1.21k | if (isa<DbgInfoIntrinsic>(CS.getInstruction())1.21k ) { |
357 | 2 | DEBUG(dbgs() << "Ignoring debug info.\n"); |
358 | 2 | ++CurInst; |
359 | 2 | continue; |
360 | 2 | } |
361 | 1.21k | |
362 | 1.21k | // Cannot handle inline asm. |
363 | 1.21k | if (1.21k isa<InlineAsm>(CS.getCalledValue())1.21k ) { |
364 | 4 | DEBUG(dbgs() << "Found inline asm, can not evaluate.\n"); |
365 | 4 | return false; |
366 | 4 | } |
367 | 1.21k | |
368 | 1.21k | if (IntrinsicInst *1.21k II1.21k = dyn_cast<IntrinsicInst>(CS.getInstruction())) { |
369 | 26 | if (MemSetInst *MSI26 = dyn_cast<MemSetInst>(II)) { |
370 | 4 | if (MSI->isVolatile()4 ) { |
371 | 0 | DEBUG(dbgs() << "Can not optimize a volatile memset " << |
372 | 0 | "intrinsic.\n"); |
373 | 0 | return false; |
374 | 0 | } |
375 | 4 | Constant *Ptr = getVal(MSI->getDest()); |
376 | 4 | Constant *Val = getVal(MSI->getValue()); |
377 | 4 | Constant *DestVal = ComputeLoadResult(getVal(Ptr)); |
378 | 4 | if (Val->isNullValue() && 4 DestVal4 && DestVal->isNullValue()1 ) { |
379 | 1 | // This memset is a no-op. |
380 | 1 | DEBUG(dbgs() << "Ignoring no-op memset.\n"); |
381 | 1 | ++CurInst; |
382 | 1 | continue; |
383 | 1 | } |
384 | 25 | } |
385 | 25 | |
386 | 25 | if (25 II->getIntrinsicID() == Intrinsic::lifetime_start || |
387 | 25 | II->getIntrinsicID() == Intrinsic::lifetime_end23 ) { |
388 | 4 | DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n"); |
389 | 4 | ++CurInst; |
390 | 4 | continue; |
391 | 4 | } |
392 | 21 | |
393 | 21 | if (21 II->getIntrinsicID() == Intrinsic::invariant_start21 ) { |
394 | 15 | // We don't insert an entry into Values, as it doesn't have a |
395 | 15 | // meaningful return value. |
396 | 15 | if (!II->use_empty()15 ) { |
397 | 3 | DEBUG(dbgs() << "Found unused invariant_start. Can't evaluate.\n"); |
398 | 3 | return false; |
399 | 3 | } |
400 | 12 | ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0)); |
401 | 12 | Value *PtrArg = getVal(II->getArgOperand(1)); |
402 | 12 | Value *Ptr = PtrArg->stripPointerCasts(); |
403 | 12 | if (GlobalVariable *GV12 = dyn_cast<GlobalVariable>(Ptr)) { |
404 | 12 | Type *ElemTy = GV->getValueType(); |
405 | 12 | if (!Size->isMinusOne() && |
406 | 11 | Size->getValue().getLimitedValue() >= |
407 | 12 | DL.getTypeStoreSize(ElemTy)) { |
408 | 9 | Invariants.insert(GV); |
409 | 9 | DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV |
410 | 9 | << "\n"); |
411 | 12 | } else { |
412 | 3 | DEBUG(dbgs() << "Found a global var, but can not treat it as an " |
413 | 3 | "invariant.\n"); |
414 | 3 | } |
415 | 12 | } |
416 | 15 | // Continue even if we do nothing. |
417 | 15 | ++CurInst; |
418 | 15 | continue; |
419 | 6 | } else if (6 II->getIntrinsicID() == Intrinsic::assume6 ) { |
420 | 1 | DEBUG(dbgs() << "Skipping assume intrinsic.\n"); |
421 | 6 | ++CurInst; |
422 | 6 | continue; |
423 | 6 | } |
424 | 5 | |
425 | 5 | DEBUG5 (dbgs() << "Unknown intrinsic. Can not evaluate.\n"); |
426 | 5 | return false; |
427 | 5 | } |
428 | 1.18k | |
429 | 1.18k | // Resolve function pointers. |
430 | 1.18k | Function *Callee = dyn_cast<Function>(getVal(CS.getCalledValue())); |
431 | 1.18k | if (!Callee || 1.18k Callee->isInterposable()1.18k ) { |
432 | 2 | DEBUG(dbgs() << "Can not resolve function pointer.\n"); |
433 | 2 | return false; // Cannot resolve. |
434 | 2 | } |
435 | 1.18k | |
436 | 1.18k | SmallVector<Constant*, 8> Formals; |
437 | 2.72k | for (User::op_iterator i = CS.arg_begin(), e = CS.arg_end(); i != e2.72k ; ++i1.54k ) |
438 | 1.54k | Formals.push_back(getVal(*i)); |
439 | 1.18k | |
440 | 1.18k | if (Callee->isDeclaration()1.18k ) { |
441 | 175 | // If this is a function we can constant fold, do it. |
442 | 175 | if (Constant *C175 = ConstantFoldCall(CS, Callee, Formals, TLI)) { |
443 | 1 | InstResult = C; |
444 | 1 | DEBUG(dbgs() << "Constant folded function call. Result: " << |
445 | 1 | *InstResult << "\n"); |
446 | 175 | } else { |
447 | 174 | DEBUG(dbgs() << "Can not constant fold function call.\n"); |
448 | 174 | return false; |
449 | 174 | } |
450 | 1.00k | } else { |
451 | 1.00k | if (Callee->getFunctionType()->isVarArg()1.00k ) { |
452 | 0 | DEBUG(dbgs() << "Can not constant fold vararg function call.\n"); |
453 | 0 | return false; |
454 | 0 | } |
455 | 1.00k | |
456 | 1.00k | Constant *RetVal = nullptr; |
457 | 1.00k | // Execute the call, if successful, use the return value. |
458 | 1.00k | ValueStack.emplace_back(); |
459 | 1.00k | if (!EvaluateFunction(Callee, RetVal, Formals)1.00k ) { |
460 | 597 | DEBUG(dbgs() << "Failed to evaluate function.\n"); |
461 | 597 | return false; |
462 | 597 | } |
463 | 411 | ValueStack.pop_back(); |
464 | 411 | InstResult = RetVal; |
465 | 411 | |
466 | 411 | if (InstResult411 ) { |
467 | 293 | DEBUG(dbgs() << "Successfully evaluated function. Result: " |
468 | 293 | << *InstResult << "\n\n"); |
469 | 411 | } else { |
470 | 118 | DEBUG(dbgs() << "Successfully evaluated function. Result: 0\n\n"); |
471 | 118 | } |
472 | 1.00k | } |
473 | 1.95k | } else if (742 isa<TerminatorInst>(CurInst)742 ) { |
474 | 742 | DEBUG(dbgs() << "Found a terminator instruction.\n"); |
475 | 742 | |
476 | 742 | if (BranchInst *BI742 = dyn_cast<BranchInst>(CurInst)) { |
477 | 191 | if (BI->isUnconditional()191 ) { |
478 | 100 | NextBB = BI->getSuccessor(0); |
479 | 191 | } else { |
480 | 91 | ConstantInt *Cond = |
481 | 91 | dyn_cast<ConstantInt>(getVal(BI->getCondition())); |
482 | 91 | if (!Cond91 ) return false0 ; // Cannot determine. |
483 | 91 | |
484 | 91 | NextBB = BI->getSuccessor(!Cond->getZExtValue()); |
485 | 91 | } |
486 | 742 | } else if (SwitchInst *551 SI551 = dyn_cast<SwitchInst>(CurInst)) { |
487 | 0 | ConstantInt *Val = |
488 | 0 | dyn_cast<ConstantInt>(getVal(SI->getCondition())); |
489 | 0 | if (!Val0 ) return false0 ; // Cannot determine. |
490 | 0 | NextBB = SI->findCaseValue(Val)->getCaseSuccessor(); |
491 | 551 | } else if (IndirectBrInst *551 IBI551 = dyn_cast<IndirectBrInst>(CurInst)) { |
492 | 0 | Value *Val = getVal(IBI->getAddress())->stripPointerCasts(); |
493 | 0 | if (BlockAddress *BA = dyn_cast<BlockAddress>(Val)) |
494 | 0 | NextBB = BA->getBasicBlock(); |
495 | 0 | else |
496 | 0 | return false; // Cannot determine. |
497 | 551 | } else if (551 isa<ReturnInst>(CurInst)551 ) { |
498 | 551 | NextBB = nullptr; |
499 | 551 | } else { |
500 | 0 | // invoke, unwind, resume, unreachable. |
501 | 0 | DEBUG(dbgs() << "Can not handle terminator."); |
502 | 551 | return false; // Cannot handle this terminator. |
503 | 551 | } |
504 | 742 | |
505 | 742 | // We succeeded at evaluating this block! |
506 | 742 | DEBUG742 (dbgs() << "Successfully evaluated block.\n"); |
507 | 742 | return true; |
508 | 0 | } else { |
509 | 0 | // Did not know how to evaluate this! |
510 | 0 | DEBUG(dbgs() << "Failed to evaluate block due to unhandled instruction." |
511 | 4.12k | "\n"); |
512 | 4.12k | return false; |
513 | 4.12k | } |
514 | 3.93k | |
515 | 3.93k | if (3.93k !CurInst->use_empty()3.93k ) { |
516 | 1.99k | if (auto *FoldedInstResult = ConstantFoldConstant(InstResult, DL, TLI)) |
517 | 928 | InstResult = FoldedInstResult; |
518 | 1.99k | |
519 | 1.99k | setVal(&*CurInst, InstResult); |
520 | 1.99k | } |
521 | 3.93k | |
522 | 3.93k | // If we just processed an invoke, we finished evaluating the block. |
523 | 3.93k | if (InvokeInst *II3.93k = dyn_cast<InvokeInst>(CurInst)) { |
524 | 1 | NextBB = II->getNormalDest(); |
525 | 1 | DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n"); |
526 | 1 | return true; |
527 | 1 | } |
528 | 3.93k | |
529 | 3.93k | // Advance program counter. |
530 | 3.93k | ++CurInst; |
531 | 3.93k | } |
532 | 1.56k | } |
533 | | |
534 | | /// Evaluate a call to function F, returning true if successful, false if we |
535 | | /// can't evaluate it. ActualArgs contains the formal arguments for the |
536 | | /// function. |
537 | | bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal, |
538 | 1.40k | const SmallVectorImpl<Constant*> &ActualArgs) { |
539 | 1.40k | // Check to see if this function is already executing (recursion). If so, |
540 | 1.40k | // bail out. TODO: we might want to accept limited recursion. |
541 | 1.40k | if (is_contained(CallStack, F)) |
542 | 0 | return false; |
543 | 1.40k | |
544 | 1.40k | CallStack.push_back(F); |
545 | 1.40k | |
546 | 1.40k | // Initialize arguments to the incoming values specified. |
547 | 1.40k | unsigned ArgNo = 0; |
548 | 2.92k | for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; |
549 | 1.51k | ++AI, ++ArgNo) |
550 | 1.51k | setVal(&*AI, ActualArgs[ArgNo]); |
551 | 1.40k | |
552 | 1.40k | // ExecutedBlocks - We only handle non-looping, non-recursive code. As such, |
553 | 1.40k | // we can only evaluate any one basic block at most once. This set keeps |
554 | 1.40k | // track of what we have executed so we can detect recursive cases etc. |
555 | 1.40k | SmallPtrSet<BasicBlock*, 32> ExecutedBlocks; |
556 | 1.40k | |
557 | 1.40k | // CurBB - The current basic block we're evaluating. |
558 | 1.40k | BasicBlock *CurBB = &F->front(); |
559 | 1.40k | |
560 | 1.40k | BasicBlock::iterator CurInst = CurBB->begin(); |
561 | 1.40k | |
562 | 1.56k | while (11.56k ) { |
563 | 1.56k | BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings. |
564 | 1.56k | DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n"); |
565 | 1.56k | |
566 | 1.56k | if (!EvaluateBlock(CurInst, NextBB)) |
567 | 822 | return false; |
568 | 743 | |
569 | 743 | if (743 !NextBB743 ) { |
570 | 551 | // Successfully running until there's no next block means that we found |
571 | 551 | // the return. Fill it the return value and pop the call stack. |
572 | 551 | ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator()); |
573 | 551 | if (RI->getNumOperands()) |
574 | 383 | RetVal = getVal(RI->getOperand(0)); |
575 | 551 | CallStack.pop_back(); |
576 | 551 | return true; |
577 | 551 | } |
578 | 192 | |
579 | 192 | // Okay, we succeeded in evaluating this control flow. See if we have |
580 | 192 | // executed the new block before. If so, we have a looping function, |
581 | 192 | // which we cannot evaluate in reasonable time. |
582 | 192 | if (192 !ExecutedBlocks.insert(NextBB).second192 ) |
583 | 32 | return false; // looped! |
584 | 160 | |
585 | 160 | // Okay, we have never been in this block before. Check to see if there |
586 | 160 | // are any PHI nodes. If so, evaluate them with information about where |
587 | 160 | // we came from. |
588 | 160 | PHINode *PN = nullptr; |
589 | 160 | for (CurInst = NextBB->begin(); |
590 | 246 | (PN = dyn_cast<PHINode>(CurInst))246 ; ++CurInst86 ) |
591 | 86 | setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB))); |
592 | 1.56k | |
593 | 1.56k | // Advance to the next block. |
594 | 1.56k | CurBB = NextBB; |
595 | 1.56k | } |
596 | 1.40k | } |
597 | | |