1 //===- Evaluator.cpp - LLVM IR evaluator ----------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Function evaluator for LLVM IR.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Transforms/Utils/Evaluator.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/Analysis/ConstantFolding.h"
20 #include "llvm/IR/BasicBlock.h"
21 #include "llvm/IR/CallSite.h"
22 #include "llvm/IR/Constant.h"
23 #include "llvm/IR/Constants.h"
24 #include "llvm/IR/DataLayout.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/Function.h"
27 #include "llvm/IR/GlobalAlias.h"
28 #include "llvm/IR/GlobalValue.h"
29 #include "llvm/IR/GlobalVariable.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/Intrinsics.h"
35 #include "llvm/IR/Operator.h"
36 #include "llvm/IR/Type.h"
37 #include "llvm/IR/User.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/Support/Casting.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/raw_ostream.h"
44 #define DEBUG_TYPE "evaluator"
49 isSimpleEnoughValueToCommit(Constant *C,
50 SmallPtrSetImpl<Constant *> &SimpleConstants,
51 const DataLayout &DL);
53 /// Return true if the specified constant can be handled by the code generator.
54 /// We don't want to generate something like:
56 /// because the code generator doesn't have a relocation that can handle that.
58 /// This function should be called if C was not found (but just got inserted)
59 /// in SimpleConstants to avoid having to rescan the same constants all the
62 isSimpleEnoughValueToCommitHelper(Constant *C,
63 SmallPtrSetImpl<Constant *> &SimpleConstants,
64 const DataLayout &DL) {
65 // Simple global addresses are supported, do not allow dllimport or
66 // thread-local globals.
67 if (auto *GV = dyn_cast<GlobalValue>(C))
68 return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();
70 // Simple integer, undef, constant aggregate zero, etc are all supported.
71 if (C->getNumOperands() == 0 || isa<BlockAddress>(C))
74 // Aggregate values are safe if all their elements are.
75 if (isa<ConstantAggregate>(C)) {
76 for (Value *Op : C->operands())
77 if (!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL))
82 // We don't know exactly what relocations are allowed in constant expressions,
83 // so we allow &global+constantoffset, which is safe and uniformly supported
85 ConstantExpr *CE = cast<ConstantExpr>(C);
86 switch (CE->getOpcode()) {
87 case Instruction::BitCast:
88 // Bitcast is fine if the casted value is fine.
89 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
91 case Instruction::IntToPtr:
92 case Instruction::PtrToInt:
93 // int <=> ptr is fine if the int type is the same size as the
95 if (DL.getTypeSizeInBits(CE->getType()) !=
96 DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
98 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
100 // GEP is fine if it is simple + constant offset.
101 case Instruction::GetElementPtr:
102 for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
103 if (!isa<ConstantInt>(CE->getOperand(i)))
105 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
107 case Instruction::Add:
108 // We allow simple+cst.
109 if (!isa<ConstantInt>(CE->getOperand(1)))
111 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
117 isSimpleEnoughValueToCommit(Constant *C,
118 SmallPtrSetImpl<Constant *> &SimpleConstants,
119 const DataLayout &DL) {
120 // If we already checked this constant, we win.
121 if (!SimpleConstants.insert(C).second)
123 // Check the constant.
124 return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
127 /// Return true if this constant is simple enough for us to understand. In
128 /// particular, if it is a cast to anything other than from one pointer type to
129 /// another pointer type, we punt. We basically just support direct accesses to
130 /// globals and GEP's of globals. This should be kept up to date with
132 static bool isSimpleEnoughPointerToCommit(Constant *C) {
133 // Conservatively, avoid aggregate types. This is because we don't
134 // want to worry about them partially overlapping other stores.
135 if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType())
138 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
139 // Do not allow weak/*_odr/linkonce linkage or external globals.
140 return GV->hasUniqueInitializer();
142 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
143 // Handle a constantexpr gep.
144 if (CE->getOpcode() == Instruction::GetElementPtr &&
145 isa<GlobalVariable>(CE->getOperand(0)) &&
146 cast<GEPOperator>(CE)->isInBounds()) {
147 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
148 // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
150 if (!GV->hasUniqueInitializer())
153 // The first index must be zero.
154 ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin()));
155 if (!CI || !CI->isZero()) return false;
157 // The remaining indices must be compile-time known integers within the
158 // notional bounds of the corresponding static array types.
159 if (!CE->isGEPWithNoNotionalOverIndexing())
162 return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
164 // A constantexpr bitcast from a pointer to another pointer is a no-op,
165 // and we know how to evaluate it by moving the bitcast from the pointer
166 // operand to the value operand.
167 } else if (CE->getOpcode() == Instruction::BitCast &&
168 isa<GlobalVariable>(CE->getOperand(0))) {
169 // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
171 return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
178 static Constant *getInitializer(Constant *C) {
179 auto *GV = dyn_cast<GlobalVariable>(C);
180 return GV && GV->hasDefinitiveInitializer() ? GV->getInitializer() : nullptr;
183 /// Return the value that would be computed by a load from P after the stores
184 /// reflected by 'memory' have been performed. If we can't decide, return null.
185 Constant *Evaluator::ComputeLoadResult(Constant *P) {
186 // If this memory location has been recently stored, use the stored value: it
187 // is the most up-to-date.
188 DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P);
189 if (I != MutatedMemory.end()) return I->second;
192 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
193 if (GV->hasDefinitiveInitializer())
194 return GV->getInitializer();
198 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) {
199 switch (CE->getOpcode()) {
200 // Handle a constantexpr getelementptr.
201 case Instruction::GetElementPtr:
202 if (auto *I = getInitializer(CE->getOperand(0)))
203 return ConstantFoldLoadThroughGEPConstantExpr(I, CE);
205 // Handle a constantexpr bitcast.
206 case Instruction::BitCast:
207 Constant *Val = getVal(CE->getOperand(0));
208 auto MM = MutatedMemory.find(Val);
209 auto *I = (MM != MutatedMemory.end()) ? MM->second
210 : getInitializer(CE->getOperand(0));
212 return ConstantFoldLoadThroughBitcast(
213 I, P->getType()->getPointerElementType(), DL);
218 return nullptr; // don't know how to evaluate.
221 static Function *getFunction(Constant *C) {
222 if (auto *Fn = dyn_cast<Function>(C))
225 if (auto *Alias = dyn_cast<GlobalAlias>(C))
226 if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
232 Evaluator::getCalleeWithFormalArgs(CallSite &CS,
233 SmallVector<Constant *, 8> &Formals) {
234 auto *V = CS.getCalledValue();
235 if (auto *Fn = getFunction(getVal(V)))
236 return getFormalParams(CS, Fn, Formals) ? Fn : nullptr;
238 auto *CE = dyn_cast<ConstantExpr>(V);
239 if (!CE || CE->getOpcode() != Instruction::BitCast ||
240 !getFormalParams(CS, getFunction(CE->getOperand(0)), Formals))
243 return dyn_cast<Function>(
244 ConstantFoldLoadThroughBitcast(CE, CE->getOperand(0)->getType(), DL));
247 bool Evaluator::getFormalParams(CallSite &CS, Function *F,
248 SmallVector<Constant *, 8> &Formals) {
252 auto *FTy = F->getFunctionType();
253 if (FTy->getNumParams() > CS.getNumArgOperands()) {
254 LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
258 auto ArgI = CS.arg_begin();
259 for (auto ParI = FTy->param_begin(), ParE = FTy->param_end(); ParI != ParE;
261 auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), *ParI, DL);
263 LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
266 Formals.push_back(ArgC);
272 /// If call expression contains bitcast then we may need to cast
273 /// evaluated return value to a type of the call expression.
274 Constant *Evaluator::castCallResultIfNeeded(Value *CallExpr, Constant *RV) {
275 ConstantExpr *CE = dyn_cast<ConstantExpr>(CallExpr);
276 if (!RV || !CE || CE->getOpcode() != Instruction::BitCast)
280 dyn_cast<FunctionType>(CE->getType()->getPointerElementType())) {
281 RV = ConstantFoldLoadThroughBitcast(RV, FT->getReturnType(), DL);
283 LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
288 /// Evaluate all instructions in block BB, returning true if successful, false
289 /// if we can't evaluate it. NewBB returns the next BB that control flows into,
290 /// or null upon return.
291 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst,
292 BasicBlock *&NextBB) {
293 // This is the main evaluation loop.
295 Constant *InstResult = nullptr;
297 LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
299 if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
300 if (!SI->isSimple()) {
301 LLVM_DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
302 return false; // no volatile/atomic accesses.
304 Constant *Ptr = getVal(SI->getOperand(1));
305 if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
306 LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
308 LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
310 if (!isSimpleEnoughPointerToCommit(Ptr)) {
311 // If this is too complex for us to commit, reject it.
313 dbgs() << "Pointer is too complex for us to evaluate store.");
317 Constant *Val = getVal(SI->getOperand(0));
319 // If this might be too difficult for the backend to handle (e.g. the addr
320 // of one global variable divided by another) then we can't commit it.
321 if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
322 LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
327 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
328 if (CE->getOpcode() == Instruction::BitCast) {
330 << "Attempting to resolve bitcast on constant ptr.\n");
331 // If we're evaluating a store through a bitcast, then we need
332 // to pull the bitcast off the pointer type and push it onto the
334 Ptr = CE->getOperand(0);
336 Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType();
338 // In order to push the bitcast onto the stored value, a bitcast
339 // from NewTy to Val's type must be legal. If it's not, we can try
340 // introspecting NewTy to find a legal conversion.
342 while (!(NewVal = ConstantFoldLoadThroughBitcast(Val, NewTy, DL))) {
343 // If NewTy is a struct, we can convert the pointer to the struct
344 // into a pointer to its first member.
345 // FIXME: This could be extended to support arrays as well.
346 if (StructType *STy = dyn_cast<StructType>(NewTy)) {
347 NewTy = STy->getTypeAtIndex(0U);
349 IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32);
350 Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
351 Constant * const IdxList[] = {IdxZero, IdxZero};
353 Ptr = ConstantExpr::getGetElementPtr(nullptr, Ptr, IdxList);
354 if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI))
357 // If we can't improve the situation by introspecting NewTy,
358 // we have to give up.
360 LLVM_DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
367 LLVM_DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
371 MutatedMemory[Ptr] = Val;
372 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
373 InstResult = ConstantExpr::get(BO->getOpcode(),
374 getVal(BO->getOperand(0)),
375 getVal(BO->getOperand(1)));
376 LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "
377 << *InstResult << "\n");
378 } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
379 InstResult = ConstantExpr::getCompare(CI->getPredicate(),
380 getVal(CI->getOperand(0)),
381 getVal(CI->getOperand(1)));
382 LLVM_DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
384 } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
385 InstResult = ConstantExpr::getCast(CI->getOpcode(),
386 getVal(CI->getOperand(0)),
388 LLVM_DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
390 } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
391 InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
392 getVal(SI->getOperand(1)),
393 getVal(SI->getOperand(2)));
394 LLVM_DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
396 } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
397 InstResult = ConstantExpr::getExtractValue(
398 getVal(EVI->getAggregateOperand()), EVI->getIndices());
399 LLVM_DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: "
400 << *InstResult << "\n");
401 } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
402 InstResult = ConstantExpr::getInsertValue(
403 getVal(IVI->getAggregateOperand()),
404 getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
405 LLVM_DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: "
406 << *InstResult << "\n");
407 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
408 Constant *P = getVal(GEP->getOperand(0));
409 SmallVector<Constant*, 8> GEPOps;
410 for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
412 GEPOps.push_back(getVal(*i));
414 ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
415 cast<GEPOperator>(GEP)->isInBounds());
416 LLVM_DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult << "\n");
417 } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
418 if (!LI->isSimple()) {
420 dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
421 return false; // no volatile/atomic accesses.
424 Constant *Ptr = getVal(LI->getOperand(0));
425 if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
427 LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
431 InstResult = ComputeLoadResult(Ptr);
434 dbgs() << "Failed to compute load result. Can not evaluate load."
436 return false; // Could not evaluate load.
439 LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
440 } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
441 if (AI->isArrayAllocation()) {
442 LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
443 return false; // Cannot handle array allocs.
445 Type *Ty = AI->getAllocatedType();
446 AllocaTmps.push_back(llvm::make_unique<GlobalVariable>(
447 Ty, false, GlobalValue::InternalLinkage, UndefValue::get(Ty),
448 AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
449 AI->getType()->getPointerAddressSpace()));
450 InstResult = AllocaTmps.back().get();
451 LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
452 } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
453 CallSite CS(&*CurInst);
455 // Debug info can safely be ignored here.
456 if (isa<DbgInfoIntrinsic>(CS.getInstruction())) {
457 LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
462 // Cannot handle inline asm.
463 if (isa<InlineAsm>(CS.getCalledValue())) {
464 LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
468 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
469 if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
470 if (MSI->isVolatile()) {
471 LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
475 Constant *Ptr = getVal(MSI->getDest());
476 Constant *Val = getVal(MSI->getValue());
477 Constant *DestVal = ComputeLoadResult(getVal(Ptr));
478 if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
479 // This memset is a no-op.
480 LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
486 if (II->isLifetimeStartOrEnd()) {
487 LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
492 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
493 // We don't insert an entry into Values, as it doesn't have a
494 // meaningful return value.
495 if (!II->use_empty()) {
497 << "Found unused invariant_start. Can't evaluate.\n");
500 ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
501 Value *PtrArg = getVal(II->getArgOperand(1));
502 Value *Ptr = PtrArg->stripPointerCasts();
503 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
504 Type *ElemTy = GV->getValueType();
505 if (!Size->isMinusOne() &&
506 Size->getValue().getLimitedValue() >=
507 DL.getTypeStoreSize(ElemTy)) {
508 Invariants.insert(GV);
509 LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
513 << "Found a global var, but can not treat it as an "
517 // Continue even if we do nothing.
520 } else if (II->getIntrinsicID() == Intrinsic::assume) {
521 LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
524 } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
525 LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
530 LLVM_DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
534 // Resolve function pointers.
535 SmallVector<Constant *, 8> Formals;
536 Function *Callee = getCalleeWithFormalArgs(CS, Formals);
537 if (!Callee || Callee->isInterposable()) {
538 LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
539 return false; // Cannot resolve.
542 if (Callee->isDeclaration()) {
543 // If this is a function we can constant fold, do it.
544 if (Constant *C = ConstantFoldCall(CS, Callee, Formals, TLI)) {
545 InstResult = castCallResultIfNeeded(CS.getCalledValue(), C);
548 LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
549 << *InstResult << "\n");
551 LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
555 if (Callee->getFunctionType()->isVarArg()) {
556 LLVM_DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
560 Constant *RetVal = nullptr;
561 // Execute the call, if successful, use the return value.
562 ValueStack.emplace_back();
563 if (!EvaluateFunction(Callee, RetVal, Formals)) {
564 LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
567 ValueStack.pop_back();
568 InstResult = castCallResultIfNeeded(CS.getCalledValue(), RetVal);
569 if (RetVal && !InstResult)
573 LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
574 << *InstResult << "\n\n");
577 << "Successfully evaluated function. Result: 0\n\n");
580 } else if (CurInst->isTerminator()) {
581 LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
583 if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
584 if (BI->isUnconditional()) {
585 NextBB = BI->getSuccessor(0);
588 dyn_cast<ConstantInt>(getVal(BI->getCondition()));
589 if (!Cond) return false; // Cannot determine.
591 NextBB = BI->getSuccessor(!Cond->getZExtValue());
593 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
595 dyn_cast<ConstantInt>(getVal(SI->getCondition()));
596 if (!Val) return false; // Cannot determine.
597 NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
598 } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
599 Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
600 if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
601 NextBB = BA->getBasicBlock();
603 return false; // Cannot determine.
604 } else if (isa<ReturnInst>(CurInst)) {
607 // invoke, unwind, resume, unreachable.
608 LLVM_DEBUG(dbgs() << "Can not handle terminator.");
609 return false; // Cannot handle this terminator.
612 // We succeeded at evaluating this block!
613 LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
616 // Did not know how to evaluate this!
618 dbgs() << "Failed to evaluate block due to unhandled instruction."
623 if (!CurInst->use_empty()) {
624 if (auto *FoldedInstResult = ConstantFoldConstant(InstResult, DL, TLI))
625 InstResult = FoldedInstResult;
627 setVal(&*CurInst, InstResult);
630 // If we just processed an invoke, we finished evaluating the block.
631 if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
632 NextBB = II->getNormalDest();
633 LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
637 // Advance program counter.
642 /// Evaluate a call to function F, returning true if successful, false if we
643 /// can't evaluate it. ActualArgs contains the formal arguments for the
645 bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
646 const SmallVectorImpl<Constant*> &ActualArgs) {
647 // Check to see if this function is already executing (recursion). If so,
648 // bail out. TODO: we might want to accept limited recursion.
649 if (is_contained(CallStack, F))
652 CallStack.push_back(F);
654 // Initialize arguments to the incoming values specified.
656 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
658 setVal(&*AI, ActualArgs[ArgNo]);
660 // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
661 // we can only evaluate any one basic block at most once. This set keeps
662 // track of what we have executed so we can detect recursive cases etc.
663 SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
665 // CurBB - The current basic block we're evaluating.
666 BasicBlock *CurBB = &F->front();
668 BasicBlock::iterator CurInst = CurBB->begin();
671 BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
672 LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
674 if (!EvaluateBlock(CurInst, NextBB))
678 // Successfully running until there's no next block means that we found
679 // the return. Fill it the return value and pop the call stack.
680 ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
681 if (RI->getNumOperands())
682 RetVal = getVal(RI->getOperand(0));
683 CallStack.pop_back();
687 // Okay, we succeeded in evaluating this control flow. See if we have
688 // executed the new block before. If so, we have a looping function,
689 // which we cannot evaluate in reasonable time.
690 if (!ExecutedBlocks.insert(NextBB).second)
691 return false; // looped!
693 // Okay, we have never been in this block before. Check to see if there
694 // are any PHI nodes. If so, evaluate them with information about where
696 PHINode *PN = nullptr;
697 for (CurInst = NextBB->begin();
698 (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
699 setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
701 // Advance to the next block.