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