llvm/lib/Transforms/Utils/Evaluator.cpp

   1 //===- Evaluator.cpp - LLVM IR evaluator ----------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Function evaluator for LLVM IR.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Transforms/Utils/Evaluator.h"
  14 #include "llvm/ADT/DenseMap.h"
  15 #include "llvm/ADT/STLExtras.h"
  16 #include "llvm/ADT/SmallPtrSet.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/Analysis/ConstantFolding.h"
  19 #include "llvm/IR/BasicBlock.h"
  20 #include "llvm/IR/Constant.h"
  21 #include "llvm/IR/Constants.h"
  22 #include "llvm/IR/DataLayout.h"
  23 #include "llvm/IR/DerivedTypes.h"
  24 #include "llvm/IR/Function.h"
  25 #include "llvm/IR/GlobalAlias.h"
  26 #include "llvm/IR/GlobalValue.h"
  27 #include "llvm/IR/GlobalVariable.h"
  28 #include "llvm/IR/InstrTypes.h"
  29 #include "llvm/IR/Instruction.h"
  30 #include "llvm/IR/Instructions.h"
  31 #include "llvm/IR/IntrinsicInst.h"
  32 #include "llvm/IR/Operator.h"
  33 #include "llvm/IR/Type.h"
  34 #include "llvm/IR/User.h"
  35 #include "llvm/IR/Value.h"
  36 #include "llvm/Support/Casting.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Support/raw_ostream.h"
  39
  40 #define DEBUG_TYPE "evaluator"
  41
  42 using namespace llvm;
  43
  44 static inline bool
  45 isSimpleEnoughValueToCommit(Constant *C,
  46                             SmallPtrSetImpl<Constant *> &SimpleConstants,
  47                             const DataLayout &DL);
  48
  49 /// Return true if the specified constant can be handled by the code generator.
  50 /// We don't want to generate something like:
  51 ///   void *X = &X/42;
  52 /// because the code generator doesn't have a relocation that can handle that.
  53 ///
  54 /// This function should be called if C was not found (but just got inserted)
  55 /// in SimpleConstants to avoid having to rescan the same constants all the
  56 /// time.
  57 static bool
  58 isSimpleEnoughValueToCommitHelper(Constant *C,
  59                                   SmallPtrSetImpl<Constant *> &SimpleConstants,
  60                                   const DataLayout &DL) {
  61   // Simple global addresses are supported, do not allow dllimport or
  62   // thread-local globals.
  63   if (auto *GV = dyn_cast<GlobalValue>(C))
  64     return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();
  65
  66   // Simple integer, undef, constant aggregate zero, etc are all supported.
  67   if (C->getNumOperands() == 0 || isa<BlockAddress>(C))
  68     return true;
  69
  70   // Aggregate values are safe if all their elements are.
  71   if (isa<ConstantAggregate>(C)) {
  72     for (Value *Op : C->operands())
  73       if (!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL))
  74         return false;
  75     return true;
  76   }
  77
  78   // We don't know exactly what relocations are allowed in constant expressions,
  79   // so we allow &global+constantoffset, which is safe and uniformly supported
  80   // across targets.
  81   ConstantExpr *CE = cast<ConstantExpr>(C);
  82   switch (CE->getOpcode()) {
  83   case Instruction::BitCast:
  84     // Bitcast is fine if the casted value is fine.
  85     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
  86
  87   case Instruction::IntToPtr:
  88   case Instruction::PtrToInt:
  89     // int <=> ptr is fine if the int type is the same size as the
  90     // pointer type.
  91     if (DL.getTypeSizeInBits(CE->getType()) !=
  92         DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
  93       return false;
  94     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
  95
  96   // GEP is fine if it is simple + constant offset.
  97   case Instruction::GetElementPtr:
  98     for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
  99       if (!isa<ConstantInt>(CE->getOperand(i)))
 100         return false;
 101     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
 102
 103   case Instruction::Add:
 104     // We allow simple+cst.
 105     if (!isa<ConstantInt>(CE->getOperand(1)))
 106       return false;
 107     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
 108   }
 109   return false;
 110 }
 111
 112 static inline bool
 113 isSimpleEnoughValueToCommit(Constant *C,
 114                             SmallPtrSetImpl<Constant *> &SimpleConstants,
 115                             const DataLayout &DL) {
 116   // If we already checked this constant, we win.
 117   if (!SimpleConstants.insert(C).second)
 118     return true;
 119   // Check the constant.
 120   return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
 121 }
 122
 123 void Evaluator::MutableValue::clear() {
 124   if (auto *Agg = Val.dyn_cast<MutableAggregate *>())
 125     delete Agg;
 126   Val = nullptr;
 127 }
 128
 129 Constant *Evaluator::MutableValue::read(Type *Ty, APInt Offset,
 130                                         const DataLayout &DL) const {
 131   TypeSize TySize = DL.getTypeStoreSize(Ty);
 132   const MutableValue *V = this;
 133   while (const auto *Agg = V->Val.dyn_cast<MutableAggregate *>()) {
 134     Type *AggTy = Agg->Ty;
 135     Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
 136     if (!Index || Index->uge(Agg->Elements.size()) ||
 137         !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
 138       return nullptr;
 139
 140     V = &Agg->Elements[Index->getZExtValue()];
 141   }
 142
 143   return ConstantFoldLoadFromConst(V->Val.get<Constant *>(), Ty, Offset, DL);
 144 }
 145
 146 bool Evaluator::MutableValue::makeMutable() {
 147   Constant *C = Val.get<Constant *>();
 148   Type *Ty = C->getType();
 149   unsigned NumElements;
 150   if (auto *VT = dyn_cast<FixedVectorType>(Ty)) {
 151     NumElements = VT->getNumElements();
 152   } else if (auto *AT = dyn_cast<ArrayType>(Ty))
 153     NumElements = AT->getNumElements();
 154   else if (auto *ST = dyn_cast<StructType>(Ty))
 155     NumElements = ST->getNumElements();
 156   else
 157     return false;
 158
 159   MutableAggregate *MA = new MutableAggregate(Ty);
 160   MA->Elements.reserve(NumElements);
 161   for (unsigned I = 0; I < NumElements; ++I)
 162     MA->Elements.push_back(C->getAggregateElement(I));
 163   Val = MA;
 164   return true;
 165 }
 166
 167 bool Evaluator::MutableValue::write(Constant *V, APInt Offset,
 168                                     const DataLayout &DL) {
 169   Type *Ty = V->getType();
 170   TypeSize TySize = DL.getTypeStoreSize(Ty);
 171   MutableValue *MV = this;
 172   while (Offset != 0 ||
 173          !CastInst::isBitOrNoopPointerCastable(Ty, MV->getType(), DL)) {
 174     if (MV->Val.is<Constant *>() && !MV->makeMutable())
 175       return false;
 176
 177     MutableAggregate *Agg = MV->Val.get<MutableAggregate *>();
 178     Type *AggTy = Agg->Ty;
 179     Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
 180     if (!Index || Index->uge(Agg->Elements.size()) ||
 181         !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
 182       return false;
 183
 184     MV = &Agg->Elements[Index->getZExtValue()];
 185   }
 186
 187   Type *MVType = MV->getType();
 188   MV->clear();
 189   if (Ty->isIntegerTy() && MVType->isPointerTy())
 190     MV->Val = ConstantExpr::getIntToPtr(V, MVType);
 191   else if (Ty->isPointerTy() && MVType->isIntegerTy())
 192     MV->Val = ConstantExpr::getPtrToInt(V, MVType);
 193   else if (Ty != MVType)
 194     MV->Val = ConstantExpr::getBitCast(V, MVType);
 195   else
 196     MV->Val = V;
 197   return true;
 198 }
 199
 200 Constant *Evaluator::MutableAggregate::toConstant() const {
 201   SmallVector<Constant *, 32> Consts;
 202   for (const MutableValue &MV : Elements)
 203     Consts.push_back(MV.toConstant());
 204
 205   if (auto *ST = dyn_cast<StructType>(Ty))
 206     return ConstantStruct::get(ST, Consts);
 207   if (auto *AT = dyn_cast<ArrayType>(Ty))
 208     return ConstantArray::get(AT, Consts);
 209   assert(isa<FixedVectorType>(Ty) && "Must be vector");
 210   return ConstantVector::get(Consts);
 211 }
 212
 213 /// Return the value that would be computed by a load from P after the stores
 214 /// reflected by 'memory' have been performed.  If we can't decide, return null.
 215 Constant *Evaluator::ComputeLoadResult(Constant *P, Type *Ty) {
 216   APInt Offset(DL.getIndexTypeSizeInBits(P->getType()), 0);
 217   P = cast<Constant>(P->stripAndAccumulateConstantOffsets(
 218       DL, Offset, /* AllowNonInbounds */ true));
 219   Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(P->getType()));
 220   if (auto *GV = dyn_cast<GlobalVariable>(P))
 221     return ComputeLoadResult(GV, Ty, Offset);
 222   return nullptr;
 223 }
 224
 225 Constant *Evaluator::ComputeLoadResult(GlobalVariable *GV, Type *Ty,
 226                                        const APInt &Offset) {
 227   auto It = MutatedMemory.find(GV);
 228   if (It != MutatedMemory.end())
 229     return It->second.read(Ty, Offset, DL);
 230
 231   if (!GV->hasDefinitiveInitializer())
 232     return nullptr;
 233   return ConstantFoldLoadFromConst(GV->getInitializer(), Ty, Offset, DL);
 234 }
 235
 236 static Function *getFunction(Constant *C) {
 237   if (auto *Fn = dyn_cast<Function>(C))
 238     return Fn;
 239
 240   if (auto *Alias = dyn_cast<GlobalAlias>(C))
 241     if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
 242       return Fn;
 243   return nullptr;
 244 }
 245
 246 Function *
 247 Evaluator::getCalleeWithFormalArgs(CallBase &CB,
 248                                    SmallVectorImpl<Constant *> &Formals) {
 249   auto *V = CB.getCalledOperand()->stripPointerCasts();
 250   if (auto *Fn = getFunction(getVal(V)))
 251     return getFormalParams(CB, Fn, Formals) ? Fn : nullptr;
 252   return nullptr;
 253 }
 254
 255 bool Evaluator::getFormalParams(CallBase &CB, Function *F,
 256                                 SmallVectorImpl<Constant *> &Formals) {
 257   if (!F)
 258     return false;
 259
 260   auto *FTy = F->getFunctionType();
 261   if (FTy->getNumParams() > CB.arg_size()) {
 262     LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
 263     return false;
 264   }
 265
 266   auto ArgI = CB.arg_begin();
 267   for (Type *PTy : FTy->params()) {
 268     auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), PTy, DL);
 269     if (!ArgC) {
 270       LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
 271       return false;
 272     }
 273     Formals.push_back(ArgC);
 274     ++ArgI;
 275   }
 276   return true;
 277 }
 278
 279 /// If call expression contains bitcast then we may need to cast
 280 /// evaluated return value to a type of the call expression.
 281 Constant *Evaluator::castCallResultIfNeeded(Type *ReturnType, Constant *RV) {
 282   if (!RV || RV->getType() == ReturnType)
 283     return RV;
 284
 285   RV = ConstantFoldLoadThroughBitcast(RV, ReturnType, DL);
 286   if (!RV)
 287     LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
 288   return RV;
 289 }
 290
 291 /// Evaluate all instructions in block BB, returning true if successful, false
 292 /// if we can't evaluate it.  NewBB returns the next BB that control flows into,
 293 /// or null upon return. StrippedPointerCastsForAliasAnalysis is set to true if
 294 /// we looked through pointer casts to evaluate something.
 295 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
 296                               bool &StrippedPointerCastsForAliasAnalysis) {
 297   // This is the main evaluation loop.
 298   while (true) {
 299     Constant *InstResult = nullptr;
 300
 301     LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
 302
 303     if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
 304       if (SI->isVolatile()) {
 305         LLVM_DEBUG(dbgs() << "Store is volatile! Can not evaluate.\n");
 306         return false;  // no volatile accesses.
 307       }
 308       Constant *Ptr = getVal(SI->getOperand(1));
 309       Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
 310       if (Ptr != FoldedPtr) {
 311         LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
 312         Ptr = FoldedPtr;
 313         LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
 314       }
 315
 316       APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
 317       Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
 318           DL, Offset, /* AllowNonInbounds */ true));
 319       Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(Ptr->getType()));
 320       auto *GV = dyn_cast<GlobalVariable>(Ptr);
 321       if (!GV || !GV->hasUniqueInitializer()) {
 322         LLVM_DEBUG(dbgs() << "Store is not to global with unique initializer: "
 323                           << *Ptr << "\n");
 324         return false;
 325       }
 326
 327       // If this might be too difficult for the backend to handle (e.g. the addr
 328       // of one global variable divided by another) then we can't commit it.
 329       Constant *Val = getVal(SI->getOperand(0));
 330       if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
 331         LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
 332                           << *Val << "\n");
 333         return false;
 334       }
 335
 336       auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer());
 337       if (!Res.first->second.write(Val, Offset, DL))
 338         return false;
 339     } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
 340       if (LI->isVolatile()) {
 341         LLVM_DEBUG(
 342             dbgs() << "Found a Load! Volatile load, can not evaluate.\n");
 343         return false;  // no volatile accesses.
 344       }
 345
 346       Constant *Ptr = getVal(LI->getOperand(0));
 347       Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
 348       if (Ptr != FoldedPtr) {
 349         Ptr = FoldedPtr;
 350         LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
 351                              "folding: "
 352                           << *Ptr << "\n");
 353       }
 354       InstResult = ComputeLoadResult(Ptr, LI->getType());
 355       if (!InstResult) {
 356         LLVM_DEBUG(
 357             dbgs() << "Failed to compute load result. Can not evaluate load."
 358                       "\n");
 359         return false; // Could not evaluate load.
 360       }
 361
 362       LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
 363     } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
 364       if (AI->isArrayAllocation()) {
 365         LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
 366         return false;  // Cannot handle array allocs.
 367       }
 368       Type *Ty = AI->getAllocatedType();
 369       AllocaTmps.push_back(std::make_unique<GlobalVariable>(
 370           Ty, false, GlobalValue::InternalLinkage, UndefValue::get(Ty),
 371           AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
 372           AI->getType()->getPointerAddressSpace()));
 373       InstResult = AllocaTmps.back().get();
 374       LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
 375     } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
 376       CallBase &CB = *cast<CallBase>(&*CurInst);
 377
 378       // Debug info can safely be ignored here.
 379       if (isa<DbgInfoIntrinsic>(CB)) {
 380         LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
 381         ++CurInst;
 382         continue;
 383       }
 384
 385       // Cannot handle inline asm.
 386       if (CB.isInlineAsm()) {
 387         LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
 388         return false;
 389       }
 390
 391       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CB)) {
 392         if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
 393           if (MSI->isVolatile()) {
 394             LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
 395                               << "intrinsic.\n");
 396             return false;
 397           }
 398
 399           auto *LenC = dyn_cast<ConstantInt>(getVal(MSI->getLength()));
 400           if (!LenC) {
 401             LLVM_DEBUG(dbgs() << "Memset with unknown length.\n");
 402             return false;
 403           }
 404
 405           Constant *Ptr = getVal(MSI->getDest());
 406           APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
 407           Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
 408               DL, Offset, /* AllowNonInbounds */ true));
 409           auto *GV = dyn_cast<GlobalVariable>(Ptr);
 410           if (!GV) {
 411             LLVM_DEBUG(dbgs() << "Memset with unknown base.\n");
 412             return false;
 413           }
 414
 415           Constant *Val = getVal(MSI->getValue());
 416           APInt Len = LenC->getValue();
 417           while (Len != 0) {
 418             Constant *DestVal = ComputeLoadResult(GV, Val->getType(), Offset);
 419             if (DestVal != Val) {
 420               LLVM_DEBUG(dbgs() << "Memset is not a no-op at offset "
 421                                 << Offset << " of " << *GV << ".\n");
 422               return false;
 423             }
 424             ++Offset;
 425             --Len;
 426           }
 427
 428           LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
 429           ++CurInst;
 430           continue;
 431         }
 432
 433         if (II->isLifetimeStartOrEnd()) {
 434           LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
 435           ++CurInst;
 436           continue;
 437         }
 438
 439         if (II->getIntrinsicID() == Intrinsic::invariant_start) {
 440           // We don't insert an entry into Values, as it doesn't have a
 441           // meaningful return value.
 442           if (!II->use_empty()) {
 443             LLVM_DEBUG(dbgs()
 444                        << "Found unused invariant_start. Can't evaluate.\n");
 445             return false;
 446           }
 447           ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
 448           Value *PtrArg = getVal(II->getArgOperand(1));
 449           Value *Ptr = PtrArg->stripPointerCasts();
 450           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
 451             Type *ElemTy = GV->getValueType();
 452             if (!Size->isMinusOne() &&
 453                 Size->getValue().getLimitedValue() >=
 454                     DL.getTypeStoreSize(ElemTy)) {
 455               Invariants.insert(GV);
 456               LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
 457                                 << *GV << "\n");
 458             } else {
 459               LLVM_DEBUG(dbgs()
 460                          << "Found a global var, but can not treat it as an "
 461                             "invariant.\n");
 462             }
 463           }
 464           // Continue even if we do nothing.
 465           ++CurInst;
 466           continue;
 467         } else if (II->getIntrinsicID() == Intrinsic::assume) {
 468           LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
 469           ++CurInst;
 470           continue;
 471         } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
 472           LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
 473           ++CurInst;
 474           continue;
 475         } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
 476           LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
 477           ++CurInst;
 478           continue;
 479         } else {
 480           Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
 481           // Only attempt to getVal() if we've actually managed to strip
 482           // anything away, or else we'll call getVal() on the current
 483           // instruction.
 484           if (Stripped != &*CurInst) {
 485             InstResult = getVal(Stripped);
 486           }
 487           if (InstResult) {
 488             LLVM_DEBUG(dbgs()
 489                        << "Stripped pointer casts for alias analysis for "
 490                           "intrinsic call.\n");
 491             StrippedPointerCastsForAliasAnalysis = true;
 492             InstResult = ConstantExpr::getBitCast(InstResult, II->getType());
 493           } else {
 494             LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
 495             return false;
 496           }
 497         }
 498       }
 499
 500       if (!InstResult) {
 501         // Resolve function pointers.
 502         SmallVector<Constant *, 8> Formals;
 503         Function *Callee = getCalleeWithFormalArgs(CB, Formals);
 504         if (!Callee || Callee->isInterposable()) {
 505           LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
 506           return false; // Cannot resolve.
 507         }
 508
 509         if (Callee->isDeclaration()) {
 510           // If this is a function we can constant fold, do it.
 511           if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) {
 512             InstResult = castCallResultIfNeeded(CB.getType(), C);
 513             if (!InstResult)
 514               return false;
 515             LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
 516                               << *InstResult << "\n");
 517           } else {
 518             LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
 519             return false;
 520           }
 521         } else {
 522           if (Callee->getFunctionType()->isVarArg()) {
 523             LLVM_DEBUG(dbgs()
 524                        << "Can not constant fold vararg function call.\n");
 525             return false;
 526           }
 527
 528           Constant *RetVal = nullptr;
 529           // Execute the call, if successful, use the return value.
 530           ValueStack.emplace_back();
 531           if (!EvaluateFunction(Callee, RetVal, Formals)) {
 532             LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
 533             return false;
 534           }
 535           ValueStack.pop_back();
 536           InstResult = castCallResultIfNeeded(CB.getType(), RetVal);
 537           if (RetVal && !InstResult)
 538             return false;
 539
 540           if (InstResult) {
 541             LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
 542                               << *InstResult << "\n\n");
 543           } else {
 544             LLVM_DEBUG(dbgs()
 545                        << "Successfully evaluated function. Result: 0\n\n");
 546           }
 547         }
 548       }
 549     } else if (CurInst->isTerminator()) {
 550       LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
 551
 552       if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
 553         if (BI->isUnconditional()) {
 554           NextBB = BI->getSuccessor(0);
 555         } else {
 556           ConstantInt *Cond =
 557             dyn_cast<ConstantInt>(getVal(BI->getCondition()));
 558           if (!Cond) return false;  // Cannot determine.
 559
 560           NextBB = BI->getSuccessor(!Cond->getZExtValue());
 561         }
 562       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
 563         ConstantInt *Val =
 564           dyn_cast<ConstantInt>(getVal(SI->getCondition()));
 565         if (!Val) return false;  // Cannot determine.
 566         NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
 567       } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
 568         Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
 569         if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
 570           NextBB = BA->getBasicBlock();
 571         else
 572           return false;  // Cannot determine.
 573       } else if (isa<ReturnInst>(CurInst)) {
 574         NextBB = nullptr;
 575       } else {
 576         // invoke, unwind, resume, unreachable.
 577         LLVM_DEBUG(dbgs() << "Can not handle terminator.");
 578         return false;  // Cannot handle this terminator.
 579       }
 580
 581       // We succeeded at evaluating this block!
 582       LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
 583       return true;
 584     } else {
 585       SmallVector<Constant *> Ops;
 586       for (Value *Op : CurInst->operands())
 587         Ops.push_back(getVal(Op));
 588       InstResult = ConstantFoldInstOperands(&*CurInst, Ops, DL, TLI);
 589       if (!InstResult) {
 590         LLVM_DEBUG(dbgs() << "Cannot fold instruction: " << *CurInst << "\n");
 591         return false;
 592       }
 593       LLVM_DEBUG(dbgs() << "Folded instruction " << *CurInst << " to "
 594                         << *InstResult << "\n");
 595     }
 596
 597     if (!CurInst->use_empty()) {
 598       InstResult = ConstantFoldConstant(InstResult, DL, TLI);
 599       setVal(&*CurInst, InstResult);
 600     }
 601
 602     // If we just processed an invoke, we finished evaluating the block.
 603     if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
 604       NextBB = II->getNormalDest();
 605       LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
 606       return true;
 607     }
 608
 609     // Advance program counter.
 610     ++CurInst;
 611   }
 612 }
 613
 614 /// Evaluate a call to function F, returning true if successful, false if we
 615 /// can't evaluate it.  ActualArgs contains the formal arguments for the
 616 /// function.
 617 bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
 618                                  const SmallVectorImpl<Constant*> &ActualArgs) {
 619   assert(ActualArgs.size() == F->arg_size() && "wrong number of arguments");
 620
 621   // Check to see if this function is already executing (recursion).  If so,
 622   // bail out.  TODO: we might want to accept limited recursion.
 623   if (is_contained(CallStack, F))
 624     return false;
 625
 626   CallStack.push_back(F);
 627
 628   // Initialize arguments to the incoming values specified.
 629   unsigned ArgNo = 0;
 630   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
 631        ++AI, ++ArgNo)
 632     setVal(&*AI, ActualArgs[ArgNo]);
 633
 634   // ExecutedBlocks - We only handle non-looping, non-recursive code.  As such,
 635   // we can only evaluate any one basic block at most once.  This set keeps
 636   // track of what we have executed so we can detect recursive cases etc.
 637   SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
 638
 639   // CurBB - The current basic block we're evaluating.
 640   BasicBlock *CurBB = &F->front();
 641
 642   BasicBlock::iterator CurInst = CurBB->begin();
 643
 644   while (true) {
 645     BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
 646     LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
 647
 648     bool StrippedPointerCastsForAliasAnalysis = false;
 649
 650     if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
 651       return false;
 652
 653     if (!NextBB) {
 654       // Successfully running until there's no next block means that we found
 655       // the return.  Fill it the return value and pop the call stack.
 656       ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
 657       if (RI->getNumOperands()) {
 658         // The Evaluator can look through pointer casts as long as alias
 659         // analysis holds because it's just a simple interpreter and doesn't
 660         // skip memory accesses due to invariant group metadata, but we can't
 661         // let users of Evaluator use a value that's been gleaned looking
 662         // through stripping pointer casts.
 663         if (StrippedPointerCastsForAliasAnalysis &&
 664             !RI->getReturnValue()->getType()->isVoidTy()) {
 665           return false;
 666         }
 667         RetVal = getVal(RI->getOperand(0));
 668       }
 669       CallStack.pop_back();
 670       return true;
 671     }
 672
 673     // Okay, we succeeded in evaluating this control flow.  See if we have
 674     // executed the new block before.  If so, we have a looping function,
 675     // which we cannot evaluate in reasonable time.
 676     if (!ExecutedBlocks.insert(NextBB).second)
 677       return false;  // looped!
 678
 679     // Okay, we have never been in this block before.  Check to see if there
 680     // are any PHI nodes.  If so, evaluate them with information about where
 681     // we came from.
 682     PHINode *PN = nullptr;
 683     for (CurInst = NextBB->begin();
 684          (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
 685       setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
 686
 687     // Advance to the next block.
 688     CurBB = NextBB;
 689   }
 690 }