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