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