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