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
42using namespace llvm;
43
44static inline bool
45isSimpleEnoughValueToCommit(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.
57static bool
58isSimpleEnoughValueToCommitHelper(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>(Val: 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>(Val: C))
68 return true;
69
70 // Aggregate values are safe if all their elements are.
71 if (isa<ConstantAggregate>(Val: C)) {
72 for (Value *Op : C->operands())
73 if (!isSimpleEnoughValueToCommit(C: cast<Constant>(Val: 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>(Val: C);
82 switch (CE->getOpcode()) {
83 case Instruction::BitCast:
84 // Bitcast is fine if the casted value is fine.
85 return isSimpleEnoughValueToCommit(C: CE->getOperand(i_nocapture: 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(Ty: CE->getType()) !=
92 DL.getTypeSizeInBits(Ty: CE->getOperand(i_nocapture: 0)->getType()))
93 return false;
94 return isSimpleEnoughValueToCommit(C: CE->getOperand(i_nocapture: 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>(Val: CE->getOperand(i_nocapture: i)))
100 return false;
101 return isSimpleEnoughValueToCommit(C: CE->getOperand(i_nocapture: 0), SimpleConstants, DL);
102
103 case Instruction::Add:
104 // We allow simple+cst.
105 if (!isa<ConstantInt>(Val: CE->getOperand(i_nocapture: 1)))
106 return false;
107 return isSimpleEnoughValueToCommit(C: CE->getOperand(i_nocapture: 0), SimpleConstants, DL);
108 }
109 return false;
110}
111
112static inline bool
113isSimpleEnoughValueToCommit(Constant *C,
114 SmallPtrSetImpl<Constant *> &SimpleConstants,
115 const DataLayout &DL) {
116 // If we already checked this constant, we win.
117 if (!SimpleConstants.insert(Ptr: C).second)
118 return true;
119 // Check the constant.
120 return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
121}
122
123void Evaluator::MutableValue::clear() {
124 if (auto *Agg = dyn_cast_if_present<MutableAggregate *>(Val))
125 delete Agg;
126 Val = nullptr;
127}
128
129Constant *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 = dyn_cast_if_present<MutableAggregate *>(Val: V->Val)) {
134 Type *AggTy = Agg->Ty;
135 std::optional<APInt> Index = DL.getGEPIndexForOffset(ElemTy&: AggTy, Offset);
136 if (!Index || Index->uge(RHS: Agg->Elements.size()) ||
137 !TypeSize::isKnownLE(LHS: TySize, RHS: DL.getTypeStoreSize(Ty: AggTy)))
138 return nullptr;
139
140 V = &Agg->Elements[Index->getZExtValue()];
141 }
142
143 return ConstantFoldLoadFromConst(C: cast<Constant *>(Val: V->Val), Ty, Offset, DL);
144}
145
146bool Evaluator::MutableValue::makeMutable() {
147 Constant *C = cast<Constant *>(Val);
148 Type *Ty = C->getType();
149 unsigned NumElements;
150 if (auto *VT = dyn_cast<FixedVectorType>(Val: Ty)) {
151 NumElements = VT->getNumElements();
152 } else if (auto *AT = dyn_cast<ArrayType>(Val: Ty))
153 NumElements = AT->getNumElements();
154 else if (auto *ST = dyn_cast<StructType>(Val: Ty))
155 NumElements = ST->getNumElements();
156 else
157 return false;
158
159 MutableAggregate *MA = new MutableAggregate(Ty);
160 MA->Elements.reserve(N: NumElements);
161 for (unsigned I = 0; I < NumElements; ++I)
162 MA->Elements.push_back(Elt: C->getAggregateElement(Elt: I));
163 Val = MA;
164 return true;
165}
166
167bool 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(SrcTy: Ty, DestTy: MV->getType(), DL)) {
174 if (isa<Constant *>(Val: MV->Val) && !MV->makeMutable())
175 return false;
176
177 MutableAggregate *Agg = cast<MutableAggregate *>(Val&: MV->Val);
178 Type *AggTy = Agg->Ty;
179 std::optional<APInt> Index = DL.getGEPIndexForOffset(ElemTy&: AggTy, Offset);
180 if (!Index || Index->uge(RHS: Agg->Elements.size()) ||
181 !TypeSize::isKnownLE(LHS: TySize, RHS: DL.getTypeStoreSize(Ty: 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(C: V, Ty: MVType);
191 else if (Ty->isPointerTy() && MVType->isIntegerTy())
192 MV->Val = ConstantExpr::getPtrToInt(C: V, Ty: MVType);
193 else if (Ty != MVType)
194 MV->Val = ConstantExpr::getBitCast(C: V, Ty: MVType);
195 else
196 MV->Val = V;
197 return true;
198}
199
200Constant *Evaluator::MutableAggregate::toConstant() const {
201 SmallVector<Constant *, 32> Consts;
202 for (const MutableValue &MV : Elements)
203 Consts.push_back(Elt: MV.toConstant());
204
205 if (auto *ST = dyn_cast<StructType>(Val: Ty))
206 return ConstantStruct::get(T: ST, V: Consts);
207 if (auto *AT = dyn_cast<ArrayType>(Val: Ty))
208 return ConstantArray::get(T: AT, V: Consts);
209 assert(isa<FixedVectorType>(Ty) && "Must be vector");
210 return ConstantVector::get(V: 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.
215Constant *Evaluator::ComputeLoadResult(Constant *P, Type *Ty) {
216 APInt Offset(DL.getIndexTypeSizeInBits(Ty: P->getType()), 0);
217 P = cast<Constant>(Val: P->stripAndAccumulateConstantOffsets(
218 DL, Offset, /* AllowNonInbounds */ true));
219 Offset = Offset.sextOrTrunc(width: DL.getIndexTypeSizeInBits(Ty: P->getType()));
220 if (auto *GV = dyn_cast<GlobalVariable>(Val: P))
221 return ComputeLoadResult(GV, Ty, Offset);
222 return nullptr;
223}
224
225Constant *Evaluator::ComputeLoadResult(GlobalVariable *GV, Type *Ty,
226 const APInt &Offset) {
227 auto It = MutatedMemory.find(Val: 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(C: GV->getInitializer(), Ty, Offset, DL);
234}
235
236static Function *getFunction(Constant *C) {
237 if (auto *Fn = dyn_cast<Function>(Val: C))
238 return Fn;
239
240 if (auto *Alias = dyn_cast<GlobalAlias>(Val: C))
241 if (auto *Fn = dyn_cast<Function>(Val: Alias->getAliasee()))
242 return Fn;
243 return nullptr;
244}
245
246Function *
247Evaluator::getCalleeWithFormalArgs(CallBase &CB,
248 SmallVectorImpl<Constant *> &Formals) {
249 auto *V = CB.getCalledOperand()->stripPointerCasts();
250 if (auto *Fn = getFunction(C: getVal(V)))
251 return getFormalParams(CB, F: Fn, Formals) ? Fn : nullptr;
252 return nullptr;
253}
254
255bool 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(C: getVal(V: *ArgI), DestTy: PTy, DL);
269 if (!ArgC) {
270 LLVM_DEBUG(dbgs() << "Can not convert function argument.\n");
271 return false;
272 }
273 Formals.push_back(Elt: 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.
281Constant *Evaluator::castCallResultIfNeeded(Type *ReturnType, Constant *RV) {
282 if (!RV || RV->getType() == ReturnType)
283 return RV;
284
285 RV = ConstantFoldLoadThroughBitcast(C: RV, DestTy: 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.
295bool 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>(Val&: CurInst)) {
304 if (SI->isVolatile()) {
305 LLVM_DEBUG(dbgs() << "Store is volatile! Can not evaluate.\n");
306 return false; // no volatile accesses.
307 }
308 Constant *Ptr = getVal(V: SI->getOperand(i_nocapture: 1));
309 Constant *FoldedPtr = ConstantFoldConstant(C: 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(Ty: Ptr->getType()), 0);
317 Ptr = cast<Constant>(Val: Ptr->stripAndAccumulateConstantOffsets(
318 DL, Offset, /* AllowNonInbounds */ true));
319 Offset = Offset.sextOrTrunc(width: DL.getIndexTypeSizeInBits(Ty: Ptr->getType()));
320 auto *GV = dyn_cast<GlobalVariable>(Val: 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(V: SI->getOperand(i_nocapture: 0));
330 if (!isSimpleEnoughValueToCommit(C: 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(Key: GV, Args: GV->getInitializer());
337 if (!Res.first->second.write(V: Val, Offset, DL))
338 return false;
339 } else if (LoadInst *LI = dyn_cast<LoadInst>(Val&: CurInst)) {
340 if (LI->isVolatile()) {
341 LLVM_DEBUG(
342 dbgs() << "Found a Load! Volatile load, can not evaluate.\n");
343 return false; // no volatile accesses.
344 }
345
346 Constant *Ptr = getVal(V: LI->getOperand(i_nocapture: 0));
347 Constant *FoldedPtr = ConstantFoldConstant(C: Ptr, DL, TLI);
348 if (Ptr != FoldedPtr) {
349 Ptr = FoldedPtr;
350 LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
351 "folding: "
352 << *Ptr << "\n");
353 }
354 InstResult = ComputeLoadResult(P: Ptr, Ty: LI->getType());
355 if (!InstResult) {
356 LLVM_DEBUG(
357 dbgs() << "Failed to compute load result. Can not evaluate load."
358 "\n");
359 return false; // Could not evaluate load.
360 }
361
362 LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
363 } else if (AllocaInst *AI = dyn_cast<AllocaInst>(Val&: CurInst)) {
364 if (AI->isArrayAllocation()) {
365 LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
366 return false; // Cannot handle array allocs.
367 }
368 Type *Ty = AI->getAllocatedType();
369 AllocaTmps.push_back(Elt: std::make_unique<GlobalVariable>(
370 args&: Ty, args: false, args: GlobalValue::InternalLinkage, args: UndefValue::get(T: Ty),
371 args: AI->getName(), /*TLMode=*/args: GlobalValue::NotThreadLocal,
372 args: AI->getType()->getPointerAddressSpace()));
373 InstResult = AllocaTmps.back().get();
374 LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
375 } else if (isa<CallInst>(Val: CurInst) || isa<InvokeInst>(Val: CurInst)) {
376 CallBase &CB = *cast<CallBase>(Val: &*CurInst);
377
378 // Debug info can safely be ignored here.
379 if (isa<DbgInfoIntrinsic>(Val: CB)) {
380 LLVM_DEBUG(dbgs() << "Ignoring debug info.\n");
381 ++CurInst;
382 continue;
383 }
384
385 // Cannot handle inline asm.
386 if (CB.isInlineAsm()) {
387 LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
388 return false;
389 }
390
391 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Val: &CB)) {
392 if (MemSetInst *MSI = dyn_cast<MemSetInst>(Val: II)) {
393 if (MSI->isVolatile()) {
394 LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
395 << "intrinsic.\n");
396 return false;
397 }
398
399 auto *LenC = dyn_cast<ConstantInt>(Val: getVal(V: MSI->getLength()));
400 if (!LenC) {
401 LLVM_DEBUG(dbgs() << "Memset with unknown length.\n");
402 return false;
403 }
404
405 Constant *Ptr = getVal(V: MSI->getDest());
406 APInt Offset(DL.getIndexTypeSizeInBits(Ty: Ptr->getType()), 0);
407 Ptr = cast<Constant>(Val: Ptr->stripAndAccumulateConstantOffsets(
408 DL, Offset, /* AllowNonInbounds */ true));
409 auto *GV = dyn_cast<GlobalVariable>(Val: Ptr);
410 if (!GV) {
411 LLVM_DEBUG(dbgs() << "Memset with unknown base.\n");
412 return false;
413 }
414
415 Constant *Val = getVal(V: MSI->getValue());
416 // Avoid the byte-per-byte scan if we're memseting a zeroinitializer
417 // to zero.
418 if (!Val->isNullValue() || MutatedMemory.contains(Val: GV) ||
419 !GV->hasDefinitiveInitializer() ||
420 !GV->getInitializer()->isNullValue()) {
421 APInt Len = LenC->getValue();
422 if (Len.ugt(RHS: 64 * 1024)) {
423 LLVM_DEBUG(dbgs() << "Not evaluating large memset of size "
424 << Len << "\n");
425 return false;
426 }
427
428 while (Len != 0) {
429 Constant *DestVal = ComputeLoadResult(GV, Ty: Val->getType(), Offset);
430 if (DestVal != Val) {
431 LLVM_DEBUG(dbgs() << "Memset is not a no-op at offset "
432 << Offset << " of " << *GV << ".\n");
433 return false;
434 }
435 ++Offset;
436 --Len;
437 }
438 }
439
440 LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
441 ++CurInst;
442 continue;
443 }
444
445 if (II->isLifetimeStartOrEnd()) {
446 LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
447 ++CurInst;
448 continue;
449 }
450
451 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
452 // We don't insert an entry into Values, as it doesn't have a
453 // meaningful return value.
454 if (!II->use_empty()) {
455 LLVM_DEBUG(dbgs()
456 << "Found unused invariant_start. Can't evaluate.\n");
457 return false;
458 }
459 ConstantInt *Size = cast<ConstantInt>(Val: II->getArgOperand(i: 0));
460 Value *PtrArg = getVal(V: II->getArgOperand(i: 1));
461 Value *Ptr = PtrArg->stripPointerCasts();
462 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Val: Ptr)) {
463 Type *ElemTy = GV->getValueType();
464 if (!Size->isMinusOne() &&
465 Size->getValue().getLimitedValue() >=
466 DL.getTypeStoreSize(Ty: ElemTy)) {
467 Invariants.insert(Ptr: GV);
468 LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
469 << *GV << "\n");
470 } else {
471 LLVM_DEBUG(dbgs()
472 << "Found a global var, but can not treat it as an "
473 "invariant.\n");
474 }
475 }
476 // Continue even if we do nothing.
477 ++CurInst;
478 continue;
479 } else if (II->getIntrinsicID() == Intrinsic::assume) {
480 LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
481 ++CurInst;
482 continue;
483 } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
484 LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
485 ++CurInst;
486 continue;
487 } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
488 LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
489 ++CurInst;
490 continue;
491 } else {
492 Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
493 // Only attempt to getVal() if we've actually managed to strip
494 // anything away, or else we'll call getVal() on the current
495 // instruction.
496 if (Stripped != &*CurInst) {
497 InstResult = getVal(V: Stripped);
498 }
499 if (InstResult) {
500 LLVM_DEBUG(dbgs()
501 << "Stripped pointer casts for alias analysis for "
502 "intrinsic call.\n");
503 StrippedPointerCastsForAliasAnalysis = true;
504 InstResult = ConstantExpr::getBitCast(C: InstResult, Ty: II->getType());
505 } else {
506 LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
507 return false;
508 }
509 }
510 }
511
512 if (!InstResult) {
513 // Resolve function pointers.
514 SmallVector<Constant *, 8> Formals;
515 Function *Callee = getCalleeWithFormalArgs(CB, Formals);
516 if (!Callee || Callee->isInterposable()) {
517 LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
518 return false; // Cannot resolve.
519 }
520
521 if (Callee->isDeclaration()) {
522 // If this is a function we can constant fold, do it.
523 if (Constant *C = ConstantFoldCall(Call: &CB, F: Callee, Operands: Formals, TLI)) {
524 InstResult = castCallResultIfNeeded(ReturnType: CB.getType(), RV: C);
525 if (!InstResult)
526 return false;
527 LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
528 << *InstResult << "\n");
529 } else {
530 LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
531 return false;
532 }
533 } else {
534 if (Callee->getFunctionType()->isVarArg()) {
535 LLVM_DEBUG(dbgs()
536 << "Can not constant fold vararg function call.\n");
537 return false;
538 }
539
540 Constant *RetVal = nullptr;
541 // Execute the call, if successful, use the return value.
542 ValueStack.emplace_back();
543 if (!EvaluateFunction(F: Callee, RetVal, ActualArgs: Formals)) {
544 LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
545 return false;
546 }
547 ValueStack.pop_back();
548 InstResult = castCallResultIfNeeded(ReturnType: CB.getType(), RV: RetVal);
549 if (RetVal && !InstResult)
550 return false;
551
552 if (InstResult) {
553 LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
554 << *InstResult << "\n\n");
555 } else {
556 LLVM_DEBUG(dbgs()
557 << "Successfully evaluated function. Result: 0\n\n");
558 }
559 }
560 }
561 } else if (CurInst->isTerminator()) {
562 LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
563
564 if (BranchInst *BI = dyn_cast<BranchInst>(Val&: CurInst)) {
565 if (BI->isUnconditional()) {
566 NextBB = BI->getSuccessor(i: 0);
567 } else {
568 ConstantInt *Cond =
569 dyn_cast<ConstantInt>(Val: getVal(V: BI->getCondition()));
570 if (!Cond) return false; // Cannot determine.
571
572 NextBB = BI->getSuccessor(i: !Cond->getZExtValue());
573 }
574 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(Val&: CurInst)) {
575 ConstantInt *Val =
576 dyn_cast<ConstantInt>(Val: getVal(V: SI->getCondition()));
577 if (!Val) return false; // Cannot determine.
578 NextBB = SI->findCaseValue(C: Val)->getCaseSuccessor();
579 } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(Val&: CurInst)) {
580 Value *Val = getVal(V: IBI->getAddress())->stripPointerCasts();
581 if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
582 NextBB = BA->getBasicBlock();
583 else
584 return false; // Cannot determine.
585 } else if (isa<ReturnInst>(Val: CurInst)) {
586 NextBB = nullptr;
587 } else {
588 // invoke, unwind, resume, unreachable.
589 LLVM_DEBUG(dbgs() << "Can not handle terminator.");
590 return false; // Cannot handle this terminator.
591 }
592
593 // We succeeded at evaluating this block!
594 LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
595 return true;
596 } else {
597 SmallVector<Constant *> Ops;
598 for (Value *Op : CurInst->operands())
599 Ops.push_back(Elt: getVal(V: Op));
600 InstResult = ConstantFoldInstOperands(I: &*CurInst, Ops, DL, TLI);
601 if (!InstResult) {
602 LLVM_DEBUG(dbgs() << "Cannot fold instruction: " << *CurInst << "\n");
603 return false;
604 }
605 LLVM_DEBUG(dbgs() << "Folded instruction " << *CurInst << " to "
606 << *InstResult << "\n");
607 }
608
609 if (!CurInst->use_empty()) {
610 InstResult = ConstantFoldConstant(C: InstResult, DL, TLI);
611 setVal(V: &*CurInst, C: InstResult);
612 }
613
614 // If we just processed an invoke, we finished evaluating the block.
615 if (InvokeInst *II = dyn_cast<InvokeInst>(Val&: CurInst)) {
616 NextBB = II->getNormalDest();
617 LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
618 return true;
619 }
620
621 // Advance program counter.
622 ++CurInst;
623 }
624}
625
626/// Evaluate a call to function F, returning true if successful, false if we
627/// can't evaluate it. ActualArgs contains the formal arguments for the
628/// function.
629bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
630 const SmallVectorImpl<Constant*> &ActualArgs) {
631 assert(ActualArgs.size() == F->arg_size() && "wrong number of arguments");
632
633 // Check to see if this function is already executing (recursion). If so,
634 // bail out. TODO: we might want to accept limited recursion.
635 if (is_contained(Range&: CallStack, Element: F))
636 return false;
637
638 CallStack.push_back(Elt: F);
639
640 // Initialize arguments to the incoming values specified.
641 for (const auto &[ArgNo, Arg] : llvm::enumerate(First: F->args()))
642 setVal(V: &Arg, C: ActualArgs[ArgNo]);
643
644 // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
645 // we can only evaluate any one basic block at most once. This set keeps
646 // track of what we have executed so we can detect recursive cases etc.
647 SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
648
649 // CurBB - The current basic block we're evaluating.
650 BasicBlock *CurBB = &F->front();
651
652 BasicBlock::iterator CurInst = CurBB->begin();
653
654 while (true) {
655 BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
656 LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
657
658 bool StrippedPointerCastsForAliasAnalysis = false;
659
660 if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
661 return false;
662
663 if (!NextBB) {
664 // Successfully running until there's no next block means that we found
665 // the return. Fill it the return value and pop the call stack.
666 ReturnInst *RI = cast<ReturnInst>(Val: CurBB->getTerminator());
667 if (RI->getNumOperands()) {
668 // The Evaluator can look through pointer casts as long as alias
669 // analysis holds because it's just a simple interpreter and doesn't
670 // skip memory accesses due to invariant group metadata, but we can't
671 // let users of Evaluator use a value that's been gleaned looking
672 // through stripping pointer casts.
673 if (StrippedPointerCastsForAliasAnalysis &&
674 !RI->getReturnValue()->getType()->isVoidTy()) {
675 return false;
676 }
677 RetVal = getVal(V: RI->getOperand(i_nocapture: 0));
678 }
679 CallStack.pop_back();
680 return true;
681 }
682
683 // Okay, we succeeded in evaluating this control flow. See if we have
684 // executed the new block before. If so, we have a looping function,
685 // which we cannot evaluate in reasonable time.
686 if (!ExecutedBlocks.insert(Ptr: NextBB).second)
687 return false; // looped!
688
689 // Okay, we have never been in this block before. Check to see if there
690 // are any PHI nodes. If so, evaluate them with information about where
691 // we came from.
692 PHINode *PN = nullptr;
693 for (CurInst = NextBB->begin();
694 (PN = dyn_cast<PHINode>(Val&: CurInst)); ++CurInst)
695 setVal(V: PN, C: getVal(V: PN->getIncomingValueForBlock(BB: CurBB)));
696
697 // Advance to the next block.
698 CurBB = NextBB;
699 }
700}
701