LLVM 17.0.0git
Evaluator.cpp
Go to the documentation of this file.
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
14#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/STLExtras.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"
24#include "llvm/IR/Function.h"
25#include "llvm/IR/GlobalAlias.h"
26#include "llvm/IR/GlobalValue.h"
28#include "llvm/IR/InstrTypes.h"
29#include "llvm/IR/Instruction.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"
37#include "llvm/Support/Debug.h"
39
40#define DEBUG_TYPE "evaluator"
41
42using namespace llvm;
43
44static inline bool
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
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
112static inline bool
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
123void Evaluator::MutableValue::clear() {
124 if (auto *Agg = Val.dyn_cast<MutableAggregate *>())
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 = V->Val.dyn_cast<MutableAggregate *>()) {
134 Type *AggTy = Agg->Ty;
135 std::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
146bool 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
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(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 std::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
200Constant *Evaluator::MutableAggregate::toConstant() const {
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.
215Constant *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
225Constant *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
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
246Function *
247Evaluator::getCalleeWithFormalArgs(CallBase &CB,
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
255bool Evaluator::getFormalParams(CallBase &CB, Function *F,
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.
281Constant *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.
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>(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(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 (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
340 if (LI->isVolatile()) {
342 dbgs() << "Found a Load! Volatile load, can not evaluate.\n");
343 return false; // no volatile accesses.
344 }
345
346 Constant *Ptr = getVal(LI->getOperand(0));
347 Constant *FoldedPtr = ConstantFoldConstant(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(Ptr, LI->getType());
355 if (!InstResult) {
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>(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(std::make_unique<GlobalVariable>(
371 AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
372 AI->getType()->getPointerAddressSpace()));
373 InstResult = AllocaTmps.back().get();
374 LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
375 } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
376 CallBase &CB = *cast<CallBase>(&*CurInst);
377
378 // Debug info can safely be ignored here.
379 if (isa<DbgInfoIntrinsic>(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>(&CB)) {
392 if (MemSetInst *MSI = dyn_cast<MemSetInst>(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>(getVal(MSI->getLength()));
400 if (!LenC) {
401 LLVM_DEBUG(dbgs() << "Memset with unknown length.\n");
402 return false;
403 }
404
405 Constant *Ptr = getVal(MSI->getDest());
406 APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
407 Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
408 DL, Offset, /* AllowNonInbounds */ true));
409 auto *GV = dyn_cast<GlobalVariable>(Ptr);
410 if (!GV) {
411 LLVM_DEBUG(dbgs() << "Memset with unknown base.\n");
412 return false;
413 }
414
415 Constant *Val = getVal(MSI->getValue());
416 APInt Len = LenC->getValue();
417 while (Len != 0) {
418 Constant *DestVal = ComputeLoadResult(GV, Val->getType(), Offset);
419 if (DestVal != Val) {
420 LLVM_DEBUG(dbgs() << "Memset is not a no-op at offset "
421 << Offset << " of " << *GV << ".\n");
422 return false;
423 }
424 ++Offset;
425 --Len;
426 }
427
428 LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
429 ++CurInst;
430 continue;
431 }
432
433 if (II->isLifetimeStartOrEnd()) {
434 LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
435 ++CurInst;
436 continue;
437 }
438
439 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
440 // We don't insert an entry into Values, as it doesn't have a
441 // meaningful return value.
442 if (!II->use_empty()) {
444 << "Found unused invariant_start. Can't evaluate.\n");
445 return false;
446 }
447 ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
448 Value *PtrArg = getVal(II->getArgOperand(1));
449 Value *Ptr = PtrArg->stripPointerCasts();
450 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
451 Type *ElemTy = GV->getValueType();
452 if (!Size->isMinusOne() &&
453 Size->getValue().getLimitedValue() >=
454 DL.getTypeStoreSize(ElemTy)) {
455 Invariants.insert(GV);
456 LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
457 << *GV << "\n");
458 } else {
460 << "Found a global var, but can not treat it as an "
461 "invariant.\n");
462 }
463 }
464 // Continue even if we do nothing.
465 ++CurInst;
466 continue;
467 } else if (II->getIntrinsicID() == Intrinsic::assume) {
468 LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
469 ++CurInst;
470 continue;
471 } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
472 LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
473 ++CurInst;
474 continue;
475 } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
476 LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
477 ++CurInst;
478 continue;
479 } else {
480 Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
481 // Only attempt to getVal() if we've actually managed to strip
482 // anything away, or else we'll call getVal() on the current
483 // instruction.
484 if (Stripped != &*CurInst) {
485 InstResult = getVal(Stripped);
486 }
487 if (InstResult) {
489 << "Stripped pointer casts for alias analysis for "
490 "intrinsic call.\n");
491 StrippedPointerCastsForAliasAnalysis = true;
492 InstResult = ConstantExpr::getBitCast(InstResult, II->getType());
493 } else {
494 LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
495 return false;
496 }
497 }
498 }
499
500 if (!InstResult) {
501 // Resolve function pointers.
503 Function *Callee = getCalleeWithFormalArgs(CB, Formals);
504 if (!Callee || Callee->isInterposable()) {
505 LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
506 return false; // Cannot resolve.
507 }
508
509 if (Callee->isDeclaration()) {
510 // If this is a function we can constant fold, do it.
511 if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) {
512 InstResult = castCallResultIfNeeded(CB.getType(), C);
513 if (!InstResult)
514 return false;
515 LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
516 << *InstResult << "\n");
517 } else {
518 LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
519 return false;
520 }
521 } else {
522 if (Callee->getFunctionType()->isVarArg()) {
524 << "Can not constant fold vararg function call.\n");
525 return false;
526 }
527
528 Constant *RetVal = nullptr;
529 // Execute the call, if successful, use the return value.
530 ValueStack.emplace_back();
531 if (!EvaluateFunction(Callee, RetVal, Formals)) {
532 LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
533 return false;
534 }
535 ValueStack.pop_back();
536 InstResult = castCallResultIfNeeded(CB.getType(), RetVal);
537 if (RetVal && !InstResult)
538 return false;
539
540 if (InstResult) {
541 LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
542 << *InstResult << "\n\n");
543 } else {
545 << "Successfully evaluated function. Result: 0\n\n");
546 }
547 }
548 }
549 } else if (CurInst->isTerminator()) {
550 LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
551
552 if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
553 if (BI->isUnconditional()) {
554 NextBB = BI->getSuccessor(0);
555 } else {
557 dyn_cast<ConstantInt>(getVal(BI->getCondition()));
558 if (!Cond) return false; // Cannot determine.
559
560 NextBB = BI->getSuccessor(!Cond->getZExtValue());
561 }
562 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
563 ConstantInt *Val =
564 dyn_cast<ConstantInt>(getVal(SI->getCondition()));
565 if (!Val) return false; // Cannot determine.
566 NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
567 } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
568 Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
569 if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
570 NextBB = BA->getBasicBlock();
571 else
572 return false; // Cannot determine.
573 } else if (isa<ReturnInst>(CurInst)) {
574 NextBB = nullptr;
575 } else {
576 // invoke, unwind, resume, unreachable.
577 LLVM_DEBUG(dbgs() << "Can not handle terminator.");
578 return false; // Cannot handle this terminator.
579 }
580
581 // We succeeded at evaluating this block!
582 LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
583 return true;
584 } else {
586 for (Value *Op : CurInst->operands())
587 Ops.push_back(getVal(Op));
588 InstResult = ConstantFoldInstOperands(&*CurInst, Ops, DL, TLI);
589 if (!InstResult) {
590 LLVM_DEBUG(dbgs() << "Cannot fold instruction: " << *CurInst << "\n");
591 return false;
592 }
593 LLVM_DEBUG(dbgs() << "Folded instruction " << *CurInst << " to "
594 << *InstResult << "\n");
595 }
596
597 if (!CurInst->use_empty()) {
598 InstResult = ConstantFoldConstant(InstResult, DL, TLI);
599 setVal(&*CurInst, InstResult);
600 }
601
602 // If we just processed an invoke, we finished evaluating the block.
603 if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
604 NextBB = II->getNormalDest();
605 LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
606 return true;
607 }
608
609 // Advance program counter.
610 ++CurInst;
611 }
612}
613
614/// Evaluate a call to function F, returning true if successful, false if we
615/// can't evaluate it. ActualArgs contains the formal arguments for the
616/// function.
618 const SmallVectorImpl<Constant*> &ActualArgs) {
619 assert(ActualArgs.size() == F->arg_size() && "wrong number of arguments");
620
621 // Check to see if this function is already executing (recursion). If so,
622 // bail out. TODO: we might want to accept limited recursion.
623 if (is_contained(CallStack, F))
624 return false;
625
626 CallStack.push_back(F);
627
628 // Initialize arguments to the incoming values specified.
629 for (const auto &[ArgNo, Arg] : llvm::enumerate(F->args()))
630 setVal(&Arg, ActualArgs[ArgNo]);
631
632 // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
633 // we can only evaluate any one basic block at most once. This set keeps
634 // track of what we have executed so we can detect recursive cases etc.
635 SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
636
637 // CurBB - The current basic block we're evaluating.
638 BasicBlock *CurBB = &F->front();
639
640 BasicBlock::iterator CurInst = CurBB->begin();
641
642 while (true) {
643 BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
644 LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
645
646 bool StrippedPointerCastsForAliasAnalysis = false;
647
648 if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
649 return false;
650
651 if (!NextBB) {
652 // Successfully running until there's no next block means that we found
653 // the return. Fill it the return value and pop the call stack.
654 ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
655 if (RI->getNumOperands()) {
656 // The Evaluator can look through pointer casts as long as alias
657 // analysis holds because it's just a simple interpreter and doesn't
658 // skip memory accesses due to invariant group metadata, but we can't
659 // let users of Evaluator use a value that's been gleaned looking
660 // through stripping pointer casts.
661 if (StrippedPointerCastsForAliasAnalysis &&
662 !RI->getReturnValue()->getType()->isVoidTy()) {
663 return false;
664 }
665 RetVal = getVal(RI->getOperand(0));
666 }
667 CallStack.pop_back();
668 return true;
669 }
670
671 // Okay, we succeeded in evaluating this control flow. See if we have
672 // executed the new block before. If so, we have a looping function,
673 // which we cannot evaluate in reasonable time.
674 if (!ExecutedBlocks.insert(NextBB).second)
675 return false; // looped!
676
677 // Okay, we have never been in this block before. Check to see if there
678 // are any PHI nodes. If so, evaluate them with information about where
679 // we came from.
680 PHINode *PN = nullptr;
681 for (CurInst = NextBB->begin();
682 (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
683 setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
684
685 // Advance to the next block.
686 CurBB = NextBB;
687 }
688}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu Simplify well known AMD library false FunctionCallee Callee
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
SmallVector< MachineOperand, 4 > Cond
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
uint64_t Size
static bool isSimpleEnoughValueToCommitHelper(Constant *C, SmallPtrSetImpl< Constant * > &SimpleConstants, const DataLayout &DL)
Return true if the specified constant can be handled by the code generator.
Definition: Evaluator.cpp:58
static bool isSimpleEnoughValueToCommit(Constant *C, SmallPtrSetImpl< Constant * > &SimpleConstants, const DataLayout &DL)
Definition: Evaluator.cpp:113
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:236
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define P(N)
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
Class for arbitrary precision integers.
Definition: APInt.h:75
an instruction to allocate memory on the stack
Definition: Instructions.h:58
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:323
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
The address of a basic block.
Definition: Constants.h:879
Conditional or Unconditional Branch instruction.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
bool isInlineAsm() const
Check if this call is an inline asm statement.
Definition: InstrTypes.h:1476
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
Definition: InstrTypes.h:1328
Value * getCalledOperand() const
Definition: InstrTypes.h:1401
unsigned arg_size() const
Definition: InstrTypes.h:1351
static bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)
Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.
static Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1242
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:1002
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2206
static Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2192
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2220
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1307
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1349
This is an important base class in LLVM.
Definition: Constant.h:41
const Constant * stripPointerCasts() const
Definition: Constant.h:213
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
bool EvaluateFunction(Function *F, Constant *&RetVal, const SmallVectorImpl< Constant * > &ActualArgs)
Evaluate a call to function F, returning true if successful, false if we can't evaluate it.
Definition: Evaluator.cpp:617
FunctionType * getFunctionType()
Definition: DerivedTypes.h:182
bool isVarArg() const
Definition: DerivedTypes.h:123
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:55
Type * getValueType() const
Definition: GlobalValue.h:292
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
bool hasUniqueInitializer() const
hasUniqueInitializer - Whether the global variable has an initializer, and any changes made to the in...
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
Indirect Branch Instruction.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Invoke instruction.
An instruction for reading from memory.
Definition: Instructions.h:177
This class wraps the llvm.memset and llvm.memset.inline intrinsics.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
Return a value (possibly void), from a function.
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
Multiway switch.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:258
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:231
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:140
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1731
Value * getOperand(unsigned i) const
Definition: User.h:169
unsigned getNumOperands() const
Definition: User.h:191
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:687
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
const Value * stripPointerCastsForAliasAnalysis() const
Strip off pointer casts, all-zero GEPs, single-argument phi nodes and invariant group info.
Definition: Value.cpp:703
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:406
Constant * ConstantFoldLoadThroughBitcast(Constant *C, Type *DestTy, const DataLayout &DL)
ConstantFoldLoadThroughBitcast - try to cast constant to destination type returning null if unsuccess...
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
Definition: STLExtras.h:2430
Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant * > Operands, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...
Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldConstant - Fold the constant using the specified DataLayout.
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Constant * ConstantFoldLoadFromConst(Constant *C, Type *Ty, const APInt &Offset, const DataLayout &DL)
Extract value of C at the given Offset reinterpreted as Ty.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1976