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