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/CallSite.h"
  21 #include "llvm/IR/Constant.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/DataLayout.h"
  24 #include "llvm/IR/DerivedTypes.h"
  25 #include "llvm/IR/Function.h"
  26 #include "llvm/IR/GlobalAlias.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 /// Apply 'Func' to Ptr. If this returns nullptr, introspect the pointer's
 178 /// type and walk down through the initial elements to obtain additional
 179 /// pointers to try. Returns the first non-null return value from Func, or
 180 /// nullptr if the type can't be introspected further.
 181 static Constant *
 182 evaluateBitcastFromPtr(Constant *Ptr, const DataLayout &DL,
 183                        const TargetLibraryInfo *TLI,
 184                        std::function<Constant *(Constant *)> Func) {
 185   Constant *Val;
 186   while (!(Val = Func(Ptr))) {
 187     // If Ty is a struct, we can convert the pointer to the struct
 188     // into a pointer to its first member.
 189     // FIXME: This could be extended to support arrays as well.
 190     Type *Ty = cast<PointerType>(Ptr->getType())->getElementType();
 191     if (!isa<StructType>(Ty))
 192       break;
 193
 194     IntegerType *IdxTy = IntegerType::get(Ty->getContext(), 32);
 195     Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
 196     Constant *const IdxList[] = {IdxZero, IdxZero};
 197
 198     Ptr = ConstantExpr::getGetElementPtr(Ty, Ptr, IdxList);
 199     if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI))
 200       Ptr = FoldedPtr;
 201   }
 202   return Val;
 203 }
 204
 205 static Constant *getInitializer(Constant *C) {
 206   auto *GV = dyn_cast<GlobalVariable>(C);
 207   return GV && GV->hasDefinitiveInitializer() ? GV->getInitializer() : nullptr;
 208 }
 209
 210 /// Return the value that would be computed by a load from P after the stores
 211 /// reflected by 'memory' have been performed.  If we can't decide, return null.
 212 Constant *Evaluator::ComputeLoadResult(Constant *P) {
 213   // If this memory location has been recently stored, use the stored value: it
 214   // is the most up-to-date.
 215   auto findMemLoc = [this](Constant *Ptr) {
 216     DenseMap<Constant *, Constant *>::const_iterator I =
 217         MutatedMemory.find(Ptr);
 218     return I != MutatedMemory.end() ? I->second : nullptr;
 219   };
 220
 221   if (Constant *Val = findMemLoc(P))
 222     return Val;
 223
 224   // Access it.
 225   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
 226     if (GV->hasDefinitiveInitializer())
 227       return GV->getInitializer();
 228     return nullptr;
 229   }
 230
 231   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P)) {
 232     switch (CE->getOpcode()) {
 233     // Handle a constantexpr getelementptr.
 234     case Instruction::GetElementPtr:
 235       if (auto *I = getInitializer(CE->getOperand(0)))
 236         return ConstantFoldLoadThroughGEPConstantExpr(I, CE);
 237       break;
 238     // Handle a constantexpr bitcast.
 239     case Instruction::BitCast:
 240       // We're evaluating a load through a pointer that was bitcast to a
 241       // different type. See if the "from" pointer has recently been stored.
 242       // If it hasn't, we may still be able to find a stored pointer by
 243       // introspecting the type.
 244       Constant *Val =
 245           evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, findMemLoc);
 246       if (!Val)
 247         Val = getInitializer(CE->getOperand(0));
 248       if (Val)
 249         return ConstantFoldLoadThroughBitcast(
 250             Val, P->getType()->getPointerElementType(), DL);
 251       break;
 252     }
 253   }
 254
 255   return nullptr;  // don't know how to evaluate.
 256 }
 257
 258 static Function *getFunction(Constant *C) {
 259   if (auto *Fn = dyn_cast<Function>(C))
 260     return Fn;
 261
 262   if (auto *Alias = dyn_cast<GlobalAlias>(C))
 263     if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
 264       return Fn;
 265   return nullptr;
 266 }
 267
 268 Function *
 269 Evaluator::getCalleeWithFormalArgs(CallSite &CS,
 270                                    SmallVector<Constant *, 8> &Formals) {
 271   auto *V = CS.getCalledValue();
 272   if (auto *Fn = getFunction(getVal(V)))
 273     return getFormalParams(CS, Fn, Formals) ? Fn : nullptr;
 274
 275   auto *CE = dyn_cast<ConstantExpr>(V);
 276   if (!CE || CE->getOpcode() != Instruction::BitCast ||
 277       !getFormalParams(CS, getFunction(CE->getOperand(0)), Formals))
 278     return nullptr;
 279
 280   return dyn_cast<Function>(
 281       ConstantFoldLoadThroughBitcast(CE, CE->getOperand(0)->getType(), DL));
 282 }
 283
 284 bool Evaluator::getFormalParams(CallSite &CS, Function *F,
 285                                 SmallVector<Constant *, 8> &Formals) {
 286   if (!F)
 287     return false;
 288
 289   auto *FTy = F->getFunctionType();
 290   if (FTy->getNumParams() > CS.getNumArgOperands()) {
 291     LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
 292     return false;
 293   }
 294
 295   auto ArgI = CS.arg_begin();
 296   for (auto ParI = FTy->param_begin(), ParE = FTy->param_end(); ParI != ParE;
 297        ++ParI) {
 298     auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), *ParI, DL);
 299     if (!ArgC) {
 300       LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
 301       return false;
 302     }
 303     Formals.push_back(ArgC);
 304     ++ArgI;
 305   }
 306   return true;
 307 }
 308
 309 /// If call expression contains bitcast then we may need to cast
 310 /// evaluated return value to a type of the call expression.
 311 Constant *Evaluator::castCallResultIfNeeded(Value *CallExpr, Constant *RV) {
 312   ConstantExpr *CE = dyn_cast<ConstantExpr>(CallExpr);
 313   if (!RV || !CE || CE->getOpcode() != Instruction::BitCast)
 314     return RV;
 315
 316   if (auto *FT =
 317           dyn_cast<FunctionType>(CE->getType()->getPointerElementType())) {
 318     RV = ConstantFoldLoadThroughBitcast(RV, FT->getReturnType(), DL);
 319     if (!RV)
 320       LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
 321   }
 322   return RV;
 323 }
 324
 325 /// Evaluate all instructions in block BB, returning true if successful, false
 326 /// if we can't evaluate it.  NewBB returns the next BB that control flows into,
 327 /// or null upon return.
 328 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst,
 329                               BasicBlock *&NextBB) {
 330   // This is the main evaluation loop.
 331   while (true) {
 332     Constant *InstResult = nullptr;
 333
 334     LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
 335
 336     if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
 337       if (!SI->isSimple()) {
 338         LLVM_DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
 339         return false;  // no volatile/atomic accesses.
 340       }
 341       Constant *Ptr = getVal(SI->getOperand(1));
 342       if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
 343         LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
 344         Ptr = FoldedPtr;
 345         LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
 346       }
 347       if (!isSimpleEnoughPointerToCommit(Ptr)) {
 348         // If this is too complex for us to commit, reject it.
 349         LLVM_DEBUG(
 350             dbgs() << "Pointer is too complex for us to evaluate store.");
 351         return false;
 352       }
 353
 354       Constant *Val = getVal(SI->getOperand(0));
 355
 356       // If this might be too difficult for the backend to handle (e.g. the addr
 357       // of one global variable divided by another) then we can't commit it.
 358       if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
 359         LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
 360                           << *Val << "\n");
 361         return false;
 362       }
 363
 364       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
 365         if (CE->getOpcode() == Instruction::BitCast) {
 366           LLVM_DEBUG(dbgs()
 367                      << "Attempting to resolve bitcast on constant ptr.\n");
 368           // If we're evaluating a store through a bitcast, then we need
 369           // to pull the bitcast off the pointer type and push it onto the
 370           // stored value. In order to push the bitcast onto the stored value,
 371           // a bitcast from the pointer's element type to Val's type must be
 372           // legal. If it's not, we can try introspecting the type to find a
 373           // legal conversion.
 374
 375           auto castValTy = [&](Constant *P) -> Constant * {
 376             Type *Ty = cast<PointerType>(P->getType())->getElementType();
 377             if (Constant *FV = ConstantFoldLoadThroughBitcast(Val, Ty, DL)) {
 378               Ptr = P;
 379               return FV;
 380             }
 381             return nullptr;
 382           };
 383
 384           Constant *NewVal =
 385               evaluateBitcastFromPtr(CE->getOperand(0), DL, TLI, castValTy);
 386           if (!NewVal) {
 387             LLVM_DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
 388                                  "evaluate.\n");
 389             return false;
 390           }
 391
 392           Val = NewVal;
 393           LLVM_DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
 394         }
 395       }
 396
 397       MutatedMemory[Ptr] = Val;
 398     } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
 399       InstResult = ConstantExpr::get(BO->getOpcode(),
 400                                      getVal(BO->getOperand(0)),
 401                                      getVal(BO->getOperand(1)));
 402       LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "
 403                         << *InstResult << "\n");
 404     } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
 405       InstResult = ConstantExpr::getCompare(CI->getPredicate(),
 406                                             getVal(CI->getOperand(0)),
 407                                             getVal(CI->getOperand(1)));
 408       LLVM_DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
 409                         << "\n");
 410     } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
 411       InstResult = ConstantExpr::getCast(CI->getOpcode(),
 412                                          getVal(CI->getOperand(0)),
 413                                          CI->getType());
 414       LLVM_DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
 415                         << "\n");
 416     } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
 417       InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
 418                                            getVal(SI->getOperand(1)),
 419                                            getVal(SI->getOperand(2)));
 420       LLVM_DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
 421                         << "\n");
 422     } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
 423       InstResult = ConstantExpr::getExtractValue(
 424           getVal(EVI->getAggregateOperand()), EVI->getIndices());
 425       LLVM_DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: "
 426                         << *InstResult << "\n");
 427     } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
 428       InstResult = ConstantExpr::getInsertValue(
 429           getVal(IVI->getAggregateOperand()),
 430           getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
 431       LLVM_DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: "
 432                         << *InstResult << "\n");
 433     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
 434       Constant *P = getVal(GEP->getOperand(0));
 435       SmallVector<Constant*, 8> GEPOps;
 436       for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
 437            i != e; ++i)
 438         GEPOps.push_back(getVal(*i));
 439       InstResult =
 440           ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
 441                                          cast<GEPOperator>(GEP)->isInBounds());
 442       LLVM_DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult << "\n");
 443     } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
 444       if (!LI->isSimple()) {
 445         LLVM_DEBUG(
 446             dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
 447         return false;  // no volatile/atomic accesses.
 448       }
 449
 450       Constant *Ptr = getVal(LI->getOperand(0));
 451       if (auto *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI)) {
 452         Ptr = FoldedPtr;
 453         LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
 454                              "folding: "
 455                           << *Ptr << "\n");
 456       }
 457       InstResult = ComputeLoadResult(Ptr);
 458       if (!InstResult) {
 459         LLVM_DEBUG(
 460             dbgs() << "Failed to compute load result. Can not evaluate load."
 461                       "\n");
 462         return false; // Could not evaluate load.
 463       }
 464
 465       LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
 466     } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
 467       if (AI->isArrayAllocation()) {
 468         LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
 469         return false;  // Cannot handle array allocs.
 470       }
 471       Type *Ty = AI->getAllocatedType();
 472       AllocaTmps.push_back(std::make_unique<GlobalVariable>(
 473           Ty, false, GlobalValue::InternalLinkage, UndefValue::get(Ty),
 474           AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
 475           AI->getType()->getPointerAddressSpace()));
 476       InstResult = AllocaTmps.back().get();
 477       LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
 478     } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
 479       CallSite CS(&*CurInst);
 480
 481       // Debug info can safely be ignored here.
 482       if (isa<DbgInfoIntrinsic>(CS.getInstruction())) {
 483         LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
 484         ++CurInst;
 485         continue;
 486       }
 487
 488       // Cannot handle inline asm.
 489       if (isa<InlineAsm>(CS.getCalledValue())) {
 490         LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
 491         return false;
 492       }
 493
 494       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
 495         if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
 496           if (MSI->isVolatile()) {
 497             LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
 498                               << "intrinsic.\n");
 499             return false;
 500           }
 501           Constant *Ptr = getVal(MSI->getDest());
 502           Constant *Val = getVal(MSI->getValue());
 503           Constant *DestVal = ComputeLoadResult(getVal(Ptr));
 504           if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
 505             // This memset is a no-op.
 506             LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
 507             ++CurInst;
 508             continue;
 509           }
 510         }
 511
 512         if (II->isLifetimeStartOrEnd()) {
 513           LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
 514           ++CurInst;
 515           continue;
 516         }
 517
 518         if (II->getIntrinsicID() == Intrinsic::invariant_start) {
 519           // We don't insert an entry into Values, as it doesn't have a
 520           // meaningful return value.
 521           if (!II->use_empty()) {
 522             LLVM_DEBUG(dbgs()
 523                        << "Found unused invariant_start. Can't evaluate.\n");
 524             return false;
 525           }
 526           ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
 527           Value *PtrArg = getVal(II->getArgOperand(1));
 528           Value *Ptr = PtrArg->stripPointerCasts();
 529           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
 530             Type *ElemTy = GV->getValueType();
 531             if (!Size->isMinusOne() &&
 532                 Size->getValue().getLimitedValue() >=
 533                     DL.getTypeStoreSize(ElemTy)) {
 534               Invariants.insert(GV);
 535               LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
 536                                 << *GV << "\n");
 537             } else {
 538               LLVM_DEBUG(dbgs()
 539                          << "Found a global var, but can not treat it as an "
 540                             "invariant.\n");
 541             }
 542           }
 543           // Continue even if we do nothing.
 544           ++CurInst;
 545           continue;
 546         } else if (II->getIntrinsicID() == Intrinsic::assume) {
 547           LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
 548           ++CurInst;
 549           continue;
 550         } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
 551           LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
 552           ++CurInst;
 553           continue;
 554         }
 555
 556         LLVM_DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
 557         return false;
 558       }
 559
 560       // Resolve function pointers.
 561       SmallVector<Constant *, 8> Formals;
 562       Function *Callee = getCalleeWithFormalArgs(CS, Formals);
 563       if (!Callee || Callee->isInterposable()) {
 564         LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
 565         return false;  // Cannot resolve.
 566       }
 567
 568       if (Callee->isDeclaration()) {
 569         // If this is a function we can constant fold, do it.
 570         if (Constant *C = ConstantFoldCall(cast<CallBase>(CS.getInstruction()),
 571                                            Callee, Formals, TLI)) {
 572           InstResult = castCallResultIfNeeded(CS.getCalledValue(), C);
 573           if (!InstResult)
 574             return false;
 575           LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
 576                             << *InstResult << "\n");
 577         } else {
 578           LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
 579           return false;
 580         }
 581       } else {
 582         if (Callee->getFunctionType()->isVarArg()) {
 583           LLVM_DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
 584           return false;
 585         }
 586
 587         Constant *RetVal = nullptr;
 588         // Execute the call, if successful, use the return value.
 589         ValueStack.emplace_back();
 590         if (!EvaluateFunction(Callee, RetVal, Formals)) {
 591           LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
 592           return false;
 593         }
 594         ValueStack.pop_back();
 595         InstResult = castCallResultIfNeeded(CS.getCalledValue(), RetVal);
 596         if (RetVal && !InstResult)
 597           return false;
 598
 599         if (InstResult) {
 600           LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
 601                             << *InstResult << "\n\n");
 602         } else {
 603           LLVM_DEBUG(dbgs()
 604                      << "Successfully evaluated function. Result: 0\n\n");
 605         }
 606       }
 607     } else if (CurInst->isTerminator()) {
 608       LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
 609
 610       if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
 611         if (BI->isUnconditional()) {
 612           NextBB = BI->getSuccessor(0);
 613         } else {
 614           ConstantInt *Cond =
 615             dyn_cast<ConstantInt>(getVal(BI->getCondition()));
 616           if (!Cond) return false;  // Cannot determine.
 617
 618           NextBB = BI->getSuccessor(!Cond->getZExtValue());
 619         }
 620       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
 621         ConstantInt *Val =
 622           dyn_cast<ConstantInt>(getVal(SI->getCondition()));
 623         if (!Val) return false;  // Cannot determine.
 624         NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
 625       } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
 626         Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
 627         if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
 628           NextBB = BA->getBasicBlock();
 629         else
 630           return false;  // Cannot determine.
 631       } else if (isa<ReturnInst>(CurInst)) {
 632         NextBB = nullptr;
 633       } else {
 634         // invoke, unwind, resume, unreachable.
 635         LLVM_DEBUG(dbgs() << "Can not handle terminator.");
 636         return false;  // Cannot handle this terminator.
 637       }
 638
 639       // We succeeded at evaluating this block!
 640       LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
 641       return true;
 642     } else {
 643       // Did not know how to evaluate this!
 644       LLVM_DEBUG(
 645           dbgs() << "Failed to evaluate block due to unhandled instruction."
 646                     "\n");
 647       return false;
 648     }
 649
 650     if (!CurInst->use_empty()) {
 651       if (auto *FoldedInstResult = ConstantFoldConstant(InstResult, DL, TLI))
 652         InstResult = FoldedInstResult;
 653
 654       setVal(&*CurInst, InstResult);
 655     }
 656
 657     // If we just processed an invoke, we finished evaluating the block.
 658     if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
 659       NextBB = II->getNormalDest();
 660       LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
 661       return true;
 662     }
 663
 664     // Advance program counter.
 665     ++CurInst;
 666   }
 667 }
 668
 669 /// Evaluate a call to function F, returning true if successful, false if we
 670 /// can't evaluate it.  ActualArgs contains the formal arguments for the
 671 /// function.
 672 bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
 673                                  const SmallVectorImpl<Constant*> &ActualArgs) {
 674   // Check to see if this function is already executing (recursion).  If so,
 675   // bail out.  TODO: we might want to accept limited recursion.
 676   if (is_contained(CallStack, F))
 677     return false;
 678
 679   CallStack.push_back(F);
 680
 681   // Initialize arguments to the incoming values specified.
 682   unsigned ArgNo = 0;
 683   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
 684        ++AI, ++ArgNo)
 685     setVal(&*AI, ActualArgs[ArgNo]);
 686
 687   // ExecutedBlocks - We only handle non-looping, non-recursive code.  As such,
 688   // we can only evaluate any one basic block at most once.  This set keeps
 689   // track of what we have executed so we can detect recursive cases etc.
 690   SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
 691
 692   // CurBB - The current basic block we're evaluating.
 693   BasicBlock *CurBB = &F->front();
 694
 695   BasicBlock::iterator CurInst = CurBB->begin();
 696
 697   while (true) {
 698     BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
 699     LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
 700
 701     if (!EvaluateBlock(CurInst, NextBB))
 702       return false;
 703
 704     if (!NextBB) {
 705       // Successfully running until there's no next block means that we found
 706       // the return.  Fill it the return value and pop the call stack.
 707       ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
 708       if (RI->getNumOperands())
 709         RetVal = getVal(RI->getOperand(0));
 710       CallStack.pop_back();
 711       return true;
 712     }
 713
 714     // Okay, we succeeded in evaluating this control flow.  See if we have
 715     // executed the new block before.  If so, we have a looping function,
 716     // which we cannot evaluate in reasonable time.
 717     if (!ExecutedBlocks.insert(NextBB).second)
 718       return false;  // looped!
 719
 720     // Okay, we have never been in this block before.  Check to see if there
 721     // are any PHI nodes.  If so, evaluate them with information about where
 722     // we came from.
 723     PHINode *PN = nullptr;
 724     for (CurInst = NextBB->begin();
 725          (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
 726       setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
 727
 728     // Advance to the next block.
 729     CurBB = NextBB;
 730   }
 731 }