contrib/llvm/lib/Transforms/Utils/Evaluator.cpp

   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
  30 using namespace llvm;
  31
  32 static inline bool
  33 isSimpleEnoughValueToCommit(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.
  45 static bool
  46 isSimpleEnoughValueToCommitHelper(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
 100 static inline bool
 101 isSimpleEnoughValueToCommit(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.
 116 static 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.
 164 Constant *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.
 192 bool 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.
 536 bool 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