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