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 void Evaluator::MutableValue::clear() {
126   if (auto *Agg = Val.dyn_cast<MutableAggregate *>())
127     delete Agg;
128   Val = nullptr;
129 }
130 
131 Constant *Evaluator::MutableValue::read(Type *Ty, APInt Offset,
132                                         const DataLayout &DL) const {
133   TypeSize TySize = DL.getTypeStoreSize(Ty);
134   const MutableValue *V = this;
135   while (const auto *Agg = V->Val.dyn_cast<MutableAggregate *>()) {
136     Type *AggTy = Agg->Ty;
137     Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
138     if (!Index || Index->uge(Agg->Elements.size()) ||
139         !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
140       return nullptr;
141 
142     V = &Agg->Elements[Index->getZExtValue()];
143   }
144 
145   return ConstantFoldLoadFromConst(V->Val.get<Constant *>(), Ty, Offset, DL);
146 }
147 
148 bool Evaluator::MutableValue::makeMutable() {
149   Constant *C = Val.get<Constant *>();
150   Type *Ty = C->getType();
151   unsigned NumElements;
152   if (auto *VT = dyn_cast<FixedVectorType>(Ty)) {
153     NumElements = VT->getNumElements();
154   } else if (auto *AT = dyn_cast<ArrayType>(Ty))
155     NumElements = AT->getNumElements();
156   else if (auto *ST = dyn_cast<StructType>(Ty))
157     NumElements = ST->getNumElements();
158   else
159     return false;
160 
161   MutableAggregate *MA = new MutableAggregate(Ty);
162   MA->Elements.reserve(NumElements);
163   for (unsigned I = 0; I < NumElements; ++I)
164     MA->Elements.push_back(C->getAggregateElement(I));
165   Val = MA;
166   return true;
167 }
168 
169 bool Evaluator::MutableValue::write(Constant *V, APInt Offset,
170                                     const DataLayout &DL) {
171   Type *Ty = V->getType();
172   TypeSize TySize = DL.getTypeStoreSize(Ty);
173   MutableValue *MV = this;
174   while (Offset != 0 ||
175          !CastInst::isBitOrNoopPointerCastable(Ty, MV->getType(), DL)) {
176     if (MV->Val.is<Constant *>() && !MV->makeMutable())
177       return false;
178 
179     MutableAggregate *Agg = MV->Val.get<MutableAggregate *>();
180     Type *AggTy = Agg->Ty;
181     Optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
182     if (!Index || Index->uge(Agg->Elements.size()) ||
183         !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
184       return false;
185 
186     MV = &Agg->Elements[Index->getZExtValue()];
187   }
188 
189   Type *MVType = MV->getType();
190   MV->clear();
191   if (Ty->isIntegerTy() && MVType->isPointerTy())
192     MV->Val = ConstantExpr::getIntToPtr(V, MVType);
193   else if (Ty->isPointerTy() && MVType->isIntegerTy())
194     MV->Val = ConstantExpr::getPtrToInt(V, MVType);
195   else if (Ty != MVType)
196     MV->Val = ConstantExpr::getBitCast(V, MVType);
197   else
198     MV->Val = V;
199   return true;
200 }
201 
202 Constant *Evaluator::MutableAggregate::toConstant() const {
203   SmallVector<Constant *, 32> Consts;
204   for (const MutableValue &MV : Elements)
205     Consts.push_back(MV.toConstant());
206 
207   if (auto *ST = dyn_cast<StructType>(Ty))
208     return ConstantStruct::get(ST, Consts);
209   if (auto *AT = dyn_cast<ArrayType>(Ty))
210     return ConstantArray::get(AT, Consts);
211   assert(isa<FixedVectorType>(Ty) && "Must be vector");
212   return ConstantVector::get(Consts);
213 }
214 
215 /// Return the value that would be computed by a load from P after the stores
216 /// reflected by 'memory' have been performed.  If we can't decide, return null.
217 Constant *Evaluator::ComputeLoadResult(Constant *P, Type *Ty) {
218   APInt Offset(DL.getIndexTypeSizeInBits(P->getType()), 0);
219   P = cast<Constant>(P->stripAndAccumulateConstantOffsets(
220       DL, Offset, /* AllowNonInbounds */ true));
221   Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(P->getType()));
222   auto *GV = dyn_cast<GlobalVariable>(P);
223   if (!GV)
224     return nullptr;
225 
226   auto It = MutatedMemory.find(GV);
227   if (It != MutatedMemory.end())
228     return It->second.read(Ty, Offset, DL);
229 
230   if (!GV->hasDefinitiveInitializer())
231     return nullptr;
232   return ConstantFoldLoadFromConst(GV->getInitializer(), Ty, Offset, DL);
233 }
234 
235 static Function *getFunction(Constant *C) {
236   if (auto *Fn = dyn_cast<Function>(C))
237     return Fn;
238 
239   if (auto *Alias = dyn_cast<GlobalAlias>(C))
240     if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
241       return Fn;
242   return nullptr;
243 }
244 
245 Function *
246 Evaluator::getCalleeWithFormalArgs(CallBase &CB,
247                                    SmallVectorImpl<Constant *> &Formals) {
248   auto *V = CB.getCalledOperand();
249   if (auto *Fn = getFunction(getVal(V)))
250     return getFormalParams(CB, Fn, Formals) ? Fn : nullptr;
251 
252   auto *CE = dyn_cast<ConstantExpr>(V);
253   if (!CE || CE->getOpcode() != Instruction::BitCast ||
254       !getFormalParams(CB, getFunction(CE->getOperand(0)), Formals))
255     return nullptr;
256 
257   return dyn_cast<Function>(
258       ConstantFoldLoadThroughBitcast(CE, CE->getOperand(0)->getType(), DL));
259 }
260 
261 bool Evaluator::getFormalParams(CallBase &CB, Function *F,
262                                 SmallVectorImpl<Constant *> &Formals) {
263   if (!F)
264     return false;
265 
266   auto *FTy = F->getFunctionType();
267   if (FTy->getNumParams() > CB.arg_size()) {
268     LLVM_DEBUG(dbgs() << "Too few arguments for function.\n");
269     return false;
270   }
271 
272   auto ArgI = CB.arg_begin();
273   for (Type *PTy : FTy->params()) {
274     auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), PTy, DL);
275     if (!ArgC) {
276       LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
277       return false;
278     }
279     Formals.push_back(ArgC);
280     ++ArgI;
281   }
282   return true;
283 }
284 
285 /// If call expression contains bitcast then we may need to cast
286 /// evaluated return value to a type of the call expression.
287 Constant *Evaluator::castCallResultIfNeeded(Value *CallExpr, Constant *RV) {
288   ConstantExpr *CE = dyn_cast<ConstantExpr>(CallExpr);
289   if (!RV || !CE || CE->getOpcode() != Instruction::BitCast)
290     return RV;
291 
292   if (auto *FT =
293           dyn_cast<FunctionType>(CE->getType()->getPointerElementType())) {
294     RV = ConstantFoldLoadThroughBitcast(RV, FT->getReturnType(), DL);
295     if (!RV)
296       LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n");
297   }
298   return RV;
299 }
300 
301 /// Evaluate all instructions in block BB, returning true if successful, false
302 /// if we can't evaluate it.  NewBB returns the next BB that control flows into,
303 /// or null upon return. StrippedPointerCastsForAliasAnalysis is set to true if
304 /// we looked through pointer casts to evaluate something.
305 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
306                               bool &StrippedPointerCastsForAliasAnalysis) {
307   // This is the main evaluation loop.
308   while (true) {
309     Constant *InstResult = nullptr;
310 
311     LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
312 
313     if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
314       if (!SI->isSimple()) {
315         LLVM_DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
316         return false;  // no volatile/atomic accesses.
317       }
318       Constant *Ptr = getVal(SI->getOperand(1));
319       Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
320       if (Ptr != FoldedPtr) {
321         LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
322         Ptr = FoldedPtr;
323         LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n");
324       }
325 
326       APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
327       Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
328           DL, Offset, /* AllowNonInbounds */ true));
329       Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(Ptr->getType()));
330       auto *GV = dyn_cast<GlobalVariable>(Ptr);
331       if (!GV || !GV->hasUniqueInitializer()) {
332         LLVM_DEBUG(dbgs() << "Store is not to global with unique initializer: "
333                           << *Ptr << "\n");
334         return false;
335       }
336 
337       // If this might be too difficult for the backend to handle (e.g. the addr
338       // of one global variable divided by another) then we can't commit it.
339       Constant *Val = getVal(SI->getOperand(0));
340       if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
341         LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
342                           << *Val << "\n");
343         return false;
344       }
345 
346       auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer());
347       if (!Res.first->second.write(Val, Offset, DL))
348         return false;
349     } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
350       InstResult = ConstantExpr::get(BO->getOpcode(),
351                                      getVal(BO->getOperand(0)),
352                                      getVal(BO->getOperand(1)));
353       LLVM_DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: "
354                         << *InstResult << "\n");
355     } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
356       InstResult = ConstantExpr::getCompare(CI->getPredicate(),
357                                             getVal(CI->getOperand(0)),
358                                             getVal(CI->getOperand(1)));
359       LLVM_DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
360                         << "\n");
361     } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
362       InstResult = ConstantExpr::getCast(CI->getOpcode(),
363                                          getVal(CI->getOperand(0)),
364                                          CI->getType());
365       LLVM_DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
366                         << "\n");
367     } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
368       InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
369                                            getVal(SI->getOperand(1)),
370                                            getVal(SI->getOperand(2)));
371       LLVM_DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
372                         << "\n");
373     } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
374       InstResult = ConstantExpr::getExtractValue(
375           getVal(EVI->getAggregateOperand()), EVI->getIndices());
376       LLVM_DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: "
377                         << *InstResult << "\n");
378     } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
379       InstResult = ConstantExpr::getInsertValue(
380           getVal(IVI->getAggregateOperand()),
381           getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
382       LLVM_DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: "
383                         << *InstResult << "\n");
384     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
385       Constant *P = getVal(GEP->getOperand(0));
386       SmallVector<Constant*, 8> GEPOps;
387       for (Use &Op : llvm::drop_begin(GEP->operands()))
388         GEPOps.push_back(getVal(Op));
389       InstResult =
390           ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
391                                          cast<GEPOperator>(GEP)->isInBounds());
392       LLVM_DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult << "\n");
393     } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
394       if (!LI->isSimple()) {
395         LLVM_DEBUG(
396             dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
397         return false;  // no volatile/atomic accesses.
398       }
399 
400       Constant *Ptr = getVal(LI->getOperand(0));
401       Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
402       if (Ptr != FoldedPtr) {
403         Ptr = FoldedPtr;
404         LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
405                              "folding: "
406                           << *Ptr << "\n");
407       }
408       InstResult = ComputeLoadResult(Ptr, LI->getType());
409       if (!InstResult) {
410         LLVM_DEBUG(
411             dbgs() << "Failed to compute load result. Can not evaluate load."
412                       "\n");
413         return false; // Could not evaluate load.
414       }
415 
416       LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
417     } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
418       if (AI->isArrayAllocation()) {
419         LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
420         return false;  // Cannot handle array allocs.
421       }
422       Type *Ty = AI->getAllocatedType();
423       AllocaTmps.push_back(std::make_unique<GlobalVariable>(
424           Ty, false, GlobalValue::InternalLinkage, UndefValue::get(Ty),
425           AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
426           AI->getType()->getPointerAddressSpace()));
427       InstResult = AllocaTmps.back().get();
428       LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
429     } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
430       CallBase &CB = *cast<CallBase>(&*CurInst);
431 
432       // Debug info can safely be ignored here.
433       if (isa<DbgInfoIntrinsic>(CB)) {
434         LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
435         ++CurInst;
436         continue;
437       }
438 
439       // Cannot handle inline asm.
440       if (CB.isInlineAsm()) {
441         LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
442         return false;
443       }
444 
445       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CB)) {
446         if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
447           if (MSI->isVolatile()) {
448             LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
449                               << "intrinsic.\n");
450             return false;
451           }
452           Constant *Ptr = getVal(MSI->getDest());
453           Constant *Val = getVal(MSI->getValue());
454           Constant *DestVal =
455               ComputeLoadResult(getVal(Ptr), MSI->getValue()->getType());
456           if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
457             // This memset is a no-op.
458             LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
459             ++CurInst;
460             continue;
461           }
462         }
463 
464         if (II->isLifetimeStartOrEnd()) {
465           LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
466           ++CurInst;
467           continue;
468         }
469 
470         if (II->getIntrinsicID() == Intrinsic::invariant_start) {
471           // We don't insert an entry into Values, as it doesn't have a
472           // meaningful return value.
473           if (!II->use_empty()) {
474             LLVM_DEBUG(dbgs()
475                        << "Found unused invariant_start. Can't evaluate.\n");
476             return false;
477           }
478           ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
479           Value *PtrArg = getVal(II->getArgOperand(1));
480           Value *Ptr = PtrArg->stripPointerCasts();
481           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
482             Type *ElemTy = GV->getValueType();
483             if (!Size->isMinusOne() &&
484                 Size->getValue().getLimitedValue() >=
485                     DL.getTypeStoreSize(ElemTy)) {
486               Invariants.insert(GV);
487               LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
488                                 << *GV << "\n");
489             } else {
490               LLVM_DEBUG(dbgs()
491                          << "Found a global var, but can not treat it as an "
492                             "invariant.\n");
493             }
494           }
495           // Continue even if we do nothing.
496           ++CurInst;
497           continue;
498         } else if (II->getIntrinsicID() == Intrinsic::assume) {
499           LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
500           ++CurInst;
501           continue;
502         } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
503           LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
504           ++CurInst;
505           continue;
506         } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
507           LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
508           ++CurInst;
509           continue;
510         } else {
511           Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
512           // Only attempt to getVal() if we've actually managed to strip
513           // anything away, or else we'll call getVal() on the current
514           // instruction.
515           if (Stripped != &*CurInst) {
516             InstResult = getVal(Stripped);
517           }
518           if (InstResult) {
519             LLVM_DEBUG(dbgs()
520                        << "Stripped pointer casts for alias analysis for "
521                           "intrinsic call.\n");
522             StrippedPointerCastsForAliasAnalysis = true;
523             InstResult = ConstantExpr::getBitCast(InstResult, II->getType());
524           } else {
525             LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
526             return false;
527           }
528         }
529       }
530 
531       if (!InstResult) {
532         // Resolve function pointers.
533         SmallVector<Constant *, 8> Formals;
534         Function *Callee = getCalleeWithFormalArgs(CB, Formals);
535         if (!Callee || Callee->isInterposable()) {
536           LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
537           return false; // Cannot resolve.
538         }
539 
540         if (Callee->isDeclaration()) {
541           // If this is a function we can constant fold, do it.
542           if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) {
543             InstResult = castCallResultIfNeeded(CB.getCalledOperand(), C);
544             if (!InstResult)
545               return false;
546             LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
547                               << *InstResult << "\n");
548           } else {
549             LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
550             return false;
551           }
552         } else {
553           if (Callee->getFunctionType()->isVarArg()) {
554             LLVM_DEBUG(dbgs()
555                        << "Can not constant fold vararg function call.\n");
556             return false;
557           }
558 
559           Constant *RetVal = nullptr;
560           // Execute the call, if successful, use the return value.
561           ValueStack.emplace_back();
562           if (!EvaluateFunction(Callee, RetVal, Formals)) {
563             LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
564             return false;
565           }
566           ValueStack.pop_back();
567           InstResult = castCallResultIfNeeded(CB.getCalledOperand(), RetVal);
568           if (RetVal && !InstResult)
569             return false;
570 
571           if (InstResult) {
572             LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
573                               << *InstResult << "\n\n");
574           } else {
575             LLVM_DEBUG(dbgs()
576                        << "Successfully evaluated function. Result: 0\n\n");
577           }
578         }
579       }
580     } else if (CurInst->isTerminator()) {
581       LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
582 
583       if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
584         if (BI->isUnconditional()) {
585           NextBB = BI->getSuccessor(0);
586         } else {
587           ConstantInt *Cond =
588             dyn_cast<ConstantInt>(getVal(BI->getCondition()));
589           if (!Cond) return false;  // Cannot determine.
590 
591           NextBB = BI->getSuccessor(!Cond->getZExtValue());
592         }
593       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
594         ConstantInt *Val =
595           dyn_cast<ConstantInt>(getVal(SI->getCondition()));
596         if (!Val) return false;  // Cannot determine.
597         NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
598       } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
599         Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
600         if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
601           NextBB = BA->getBasicBlock();
602         else
603           return false;  // Cannot determine.
604       } else if (isa<ReturnInst>(CurInst)) {
605         NextBB = nullptr;
606       } else {
607         // invoke, unwind, resume, unreachable.
608         LLVM_DEBUG(dbgs() << "Can not handle terminator.");
609         return false;  // Cannot handle this terminator.
610       }
611 
612       // We succeeded at evaluating this block!
613       LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
614       return true;
615     } else {
616       // Did not know how to evaluate this!
617       LLVM_DEBUG(
618           dbgs() << "Failed to evaluate block due to unhandled instruction."
619                     "\n");
620       return false;
621     }
622 
623     if (!CurInst->use_empty()) {
624       InstResult = ConstantFoldConstant(InstResult, DL, TLI);
625       setVal(&*CurInst, InstResult);
626     }
627 
628     // If we just processed an invoke, we finished evaluating the block.
629     if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
630       NextBB = II->getNormalDest();
631       LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
632       return true;
633     }
634 
635     // Advance program counter.
636     ++CurInst;
637   }
638 }
639 
640 /// Evaluate a call to function F, returning true if successful, false if we
641 /// can't evaluate it.  ActualArgs contains the formal arguments for the
642 /// function.
643 bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
644                                  const SmallVectorImpl<Constant*> &ActualArgs) {
645   // Check to see if this function is already executing (recursion).  If so,
646   // bail out.  TODO: we might want to accept limited recursion.
647   if (is_contained(CallStack, F))
648     return false;
649 
650   CallStack.push_back(F);
651 
652   // Initialize arguments to the incoming values specified.
653   unsigned ArgNo = 0;
654   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
655        ++AI, ++ArgNo)
656     setVal(&*AI, ActualArgs[ArgNo]);
657 
658   // ExecutedBlocks - We only handle non-looping, non-recursive code.  As such,
659   // we can only evaluate any one basic block at most once.  This set keeps
660   // track of what we have executed so we can detect recursive cases etc.
661   SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
662 
663   // CurBB - The current basic block we're evaluating.
664   BasicBlock *CurBB = &F->front();
665 
666   BasicBlock::iterator CurInst = CurBB->begin();
667 
668   while (true) {
669     BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
670     LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
671 
672     bool StrippedPointerCastsForAliasAnalysis = false;
673 
674     if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
675       return false;
676 
677     if (!NextBB) {
678       // Successfully running until there's no next block means that we found
679       // the return.  Fill it the return value and pop the call stack.
680       ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
681       if (RI->getNumOperands()) {
682         // The Evaluator can look through pointer casts as long as alias
683         // analysis holds because it's just a simple interpreter and doesn't
684         // skip memory accesses due to invariant group metadata, but we can't
685         // let users of Evaluator use a value that's been gleaned looking
686         // through stripping pointer casts.
687         if (StrippedPointerCastsForAliasAnalysis &&
688             !RI->getReturnValue()->getType()->isVoidTy()) {
689           return false;
690         }
691         RetVal = getVal(RI->getOperand(0));
692       }
693       CallStack.pop_back();
694       return true;
695     }
696 
697     // Okay, we succeeded in evaluating this control flow.  See if we have
698     // executed the new block before.  If so, we have a looping function,
699     // which we cannot evaluate in reasonable time.
700     if (!ExecutedBlocks.insert(NextBB).second)
701       return false;  // looped!
702 
703     // Okay, we have never been in this block before.  Check to see if there
704     // are any PHI nodes.  If so, evaluate them with information about where
705     // we came from.
706     PHINode *PN = nullptr;
707     for (CurInst = NextBB->begin();
708          (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
709       setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
710 
711     // Advance to the next block.
712     CurBB = NextBB;
713   }
714 }
715