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
45using namespace llvm;
46
47static inline bool
48isSimpleEnoughValueToCommit(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.
60static bool
61isSimpleEnoughValueToCommitHelper(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
115static inline bool
116isSimpleEnoughValueToCommit(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.
131static 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.
181static Constant *
182evaluateBitcastFromPtr(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
205static 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.
212Constant *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
258static 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
268Function *
269Evaluator::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
284bool 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.
311Constant *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.
328bool 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.
672bool 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}
732