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