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