LLVM 22.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/Type.h"
33#include "llvm/IR/User.h"
34#include "llvm/IR/Value.h"
36#include "llvm/Support/Debug.h"
38
39#define DEBUG_TYPE "evaluator"
40
41using namespace llvm;
42
43static inline bool
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
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>(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>(C))
67 return true;
68
69 // Aggregate values are safe if all their elements are.
70 if (isa<ConstantAggregate>(C)) {
71 for (Value *Op : C->operands())
72 if (!isSimpleEnoughValueToCommit(cast<Constant>(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>(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(CE->getOperand(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(CE->getType()) !=
93 DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
94 return false;
95 return isSimpleEnoughValueToCommit(CE->getOperand(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>(CE->getOperand(i)))
101 return false;
102 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
103
104 case Instruction::Add:
105 // We allow simple+cst.
106 if (!isa<ConstantInt>(CE->getOperand(1)))
107 return false;
108 return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
109 }
110 return false;
111}
112
113static inline bool
115 SmallPtrSetImpl<Constant *> &SimpleConstants,
116 const DataLayout &DL) {
117 // If we already checked this constant, we win.
118 if (!SimpleConstants.insert(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 *>(V->Val)) {
135 Type *AggTy = Agg->Ty;
136 std::optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
137 if (!Index || Index->uge(Agg->Elements.size()) ||
138 !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy)))
139 return nullptr;
140
141 V = &Agg->Elements[Index->getZExtValue()];
142 }
143
144 return ConstantFoldLoadFromConst(cast<Constant *>(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>(Ty)) {
152 NumElements = VT->getNumElements();
153 } else if (auto *AT = dyn_cast<ArrayType>(Ty))
154 NumElements = AT->getNumElements();
155 else if (auto *ST = dyn_cast<StructType>(Ty))
156 NumElements = ST->getNumElements();
157 else
158 return false;
159
160 MutableAggregate *MA = new MutableAggregate(Ty);
161 MA->Elements.reserve(NumElements);
162 for (unsigned I = 0; I < NumElements; ++I)
163 MA->Elements.push_back(C->getAggregateElement(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(Ty, MV->getType(), DL)) {
175 if (isa<Constant *>(MV->Val) && !MV->makeMutable())
176 return false;
177
178 MutableAggregate *Agg = cast<MutableAggregate *>(MV->Val);
179 Type *AggTy = Agg->Ty;
180 std::optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset);
181 if (!Index || Index->uge(Agg->Elements.size()) ||
182 !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(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(V, MVType);
192 else if (Ty->isPointerTy() && MVType->isIntegerTy())
193 MV->Val = ConstantExpr::getPtrToInt(V, MVType);
194 else if (Ty != MVType)
195 MV->Val = ConstantExpr::getBitCast(V, MVType);
196 else
197 MV->Val = V;
198 return true;
199}
200
201Constant *Evaluator::MutableAggregate::toConstant() const {
203 for (const MutableValue &MV : Elements)
204 Consts.push_back(MV.toConstant());
205
206 if (auto *ST = dyn_cast<StructType>(Ty))
207 return ConstantStruct::get(ST, Consts);
208 if (auto *AT = dyn_cast<ArrayType>(Ty))
209 return ConstantArray::get(AT, Consts);
210 assert(isa<FixedVectorType>(Ty) && "Must be vector");
211 return ConstantVector::get(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(P->getType()), 0);
218 P = cast<Constant>(P->stripAndAccumulateConstantOffsets(
219 DL, Offset, /* AllowNonInbounds */ true));
220 Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(P->getType()));
221 if (auto *GV = dyn_cast<GlobalVariable>(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(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(GV->getInitializer(), Ty, Offset, DL);
235}
236
238 if (auto *Fn = dyn_cast<Function>(C))
239 return Fn;
240
241 if (auto *Alias = dyn_cast<GlobalAlias>(C))
242 if (auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
243 return Fn;
244 return nullptr;
245}
246
247Function *
248Evaluator::getCalleeWithFormalArgs(CallBase &CB,
250 auto *V = CB.getCalledOperand()->stripPointerCasts();
251 if (auto *Fn = getFunction(getVal(V)))
252 return getFormalParams(CB, Fn, Formals) ? Fn : nullptr;
253 return nullptr;
254}
255
256bool Evaluator::getFormalParams(CallBase &CB, Function *F,
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(getVal(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>(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(SI->getOperand(1));
287 Constant *FoldedPtr = ConstantFoldConstant(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(Ptr->getType()), 0);
295 Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
296 DL, Offset, /* AllowNonInbounds */ true));
297 Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(Ptr->getType()));
298 auto *GV = dyn_cast<GlobalVariable>(Ptr);
299 if (!GV || !GV->hasUniqueInitializer()) {
300 LLVM_DEBUG(dbgs() << "Store is not to global with unique initializer: "
301 << *Ptr << "\n");
302 return false;
303 }
304
305 // If this might be too difficult for the backend to handle (e.g. the addr
306 // of one global variable divided by another) then we can't commit it.
307 Constant *Val = getVal(SI->getOperand(0));
308 if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
309 LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. "
310 << *Val << "\n");
311 return false;
312 }
313
314 auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer());
315 if (!Res.first->second.write(Val, Offset, DL))
316 return false;
317 } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
318 if (LI->isVolatile()) {
320 dbgs() << "Found a Load! Volatile load, can not evaluate.\n");
321 return false; // no volatile accesses.
322 }
323
324 Constant *Ptr = getVal(LI->getOperand(0));
325 Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI);
326 if (Ptr != FoldedPtr) {
327 Ptr = FoldedPtr;
328 LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant "
329 "folding: "
330 << *Ptr << "\n");
331 }
332 InstResult = ComputeLoadResult(Ptr, LI->getType());
333 if (!InstResult) {
335 dbgs() << "Failed to compute load result. Can not evaluate load."
336 "\n");
337 return false; // Could not evaluate load.
338 }
339
340 LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
341 } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
342 if (AI->isArrayAllocation()) {
343 LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
344 return false; // Cannot handle array allocs.
345 }
346 Type *Ty = AI->getAllocatedType();
347 AllocaTmps.push_back(std::make_unique<GlobalVariable>(
349 AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal,
350 AI->getType()->getPointerAddressSpace()));
351 InstResult = AllocaTmps.back().get();
352 LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
353 } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
354 CallBase &CB = *cast<CallBase>(&*CurInst);
355
356 // Cannot handle inline asm.
357 if (CB.isInlineAsm()) {
358 LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
359 return false;
360 }
361
362 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CB)) {
363 if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
364 if (MSI->isVolatile()) {
365 LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset "
366 << "intrinsic.\n");
367 return false;
368 }
369
370 auto *LenC = dyn_cast<ConstantInt>(getVal(MSI->getLength()));
371 if (!LenC) {
372 LLVM_DEBUG(dbgs() << "Memset with unknown length.\n");
373 return false;
374 }
375
376 Constant *Ptr = getVal(MSI->getDest());
377 APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0);
378 Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets(
379 DL, Offset, /* AllowNonInbounds */ true));
380 auto *GV = dyn_cast<GlobalVariable>(Ptr);
381 if (!GV) {
382 LLVM_DEBUG(dbgs() << "Memset with unknown base.\n");
383 return false;
384 }
385
386 Constant *Val = getVal(MSI->getValue());
387 // Avoid the byte-per-byte scan if we're memseting a zeroinitializer
388 // to zero.
389 if (!Val->isNullValue() || MutatedMemory.contains(GV) ||
391 !GV->getInitializer()->isNullValue()) {
392 APInt Len = LenC->getValue();
393 if (Len.ugt(64 * 1024)) {
394 LLVM_DEBUG(dbgs() << "Not evaluating large memset of size "
395 << Len << "\n");
396 return false;
397 }
398
399 while (Len != 0) {
400 Constant *DestVal = ComputeLoadResult(GV, Val->getType(), Offset);
401 if (DestVal != Val) {
402 LLVM_DEBUG(dbgs() << "Memset is not a no-op at offset "
403 << Offset << " of " << *GV << ".\n");
404 return false;
405 }
406 ++Offset;
407 --Len;
408 }
409 }
410
411 LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n");
412 ++CurInst;
413 continue;
414 }
415
416 if (II->isLifetimeStartOrEnd()) {
417 LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
418 ++CurInst;
419 continue;
420 }
421
422 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
423 // We don't insert an entry into Values, as it doesn't have a
424 // meaningful return value.
425 if (!II->use_empty()) {
427 << "Found unused invariant_start. Can't evaluate.\n");
428 return false;
429 }
430 ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
431 Value *PtrArg = getVal(II->getArgOperand(1));
432 Value *Ptr = PtrArg->stripPointerCasts();
433 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
434 Type *ElemTy = GV->getValueType();
435 if (!Size->isMinusOne() &&
436 Size->getValue().getLimitedValue() >=
437 DL.getTypeStoreSize(ElemTy)) {
438 Invariants.insert(GV);
439 LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: "
440 << *GV << "\n");
441 } else {
443 << "Found a global var, but can not treat it as an "
444 "invariant.\n");
445 }
446 }
447 // Continue even if we do nothing.
448 ++CurInst;
449 continue;
450 } else if (II->getIntrinsicID() == Intrinsic::assume) {
451 LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n");
452 ++CurInst;
453 continue;
454 } else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
455 LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n");
456 ++CurInst;
457 continue;
458 } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
459 LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n");
460 ++CurInst;
461 continue;
462 } else {
463 Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis();
464 // Only attempt to getVal() if we've actually managed to strip
465 // anything away, or else we'll call getVal() on the current
466 // instruction.
467 if (Stripped != &*CurInst) {
468 InstResult = getVal(Stripped);
469 }
470 if (InstResult) {
472 << "Stripped pointer casts for alias analysis for "
473 "intrinsic call.\n");
474 StrippedPointerCastsForAliasAnalysis = true;
475 InstResult = ConstantExpr::getBitCast(InstResult, II->getType());
476 } else {
477 LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n");
478 return false;
479 }
480 }
481 }
482
483 if (!InstResult) {
484 // Resolve function pointers.
486 Function *Callee = getCalleeWithFormalArgs(CB, Formals);
487 if (!Callee || Callee->isInterposable()) {
488 LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n");
489 return false; // Cannot resolve.
490 }
491
492 if (Callee->isDeclaration()) {
493 // If this is a function we can constant fold, do it.
494 if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) {
495 InstResult = C;
496 LLVM_DEBUG(dbgs() << "Constant folded function call. Result: "
497 << *InstResult << "\n");
498 } else {
499 LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n");
500 return false;
501 }
502 } else {
503 if (Callee->getFunctionType()->isVarArg()) {
505 << "Can not constant fold vararg function call.\n");
506 return false;
507 }
508
509 Constant *RetVal = nullptr;
510 // Execute the call, if successful, use the return value.
511 ValueStack.emplace_back();
512 if (!EvaluateFunction(Callee, RetVal, Formals)) {
513 LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n");
514 return false;
515 }
516 ValueStack.pop_back();
517 InstResult = RetVal;
518 if (InstResult) {
519 LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: "
520 << *InstResult << "\n\n");
521 } else {
523 << "Successfully evaluated function. Result: 0\n\n");
524 }
525 }
526 }
527 } else if (CurInst->isTerminator()) {
528 LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n");
529
530 if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
531 if (BI->isUnconditional()) {
532 NextBB = BI->getSuccessor(0);
533 } else {
535 dyn_cast<ConstantInt>(getVal(BI->getCondition()));
536 if (!Cond) return false; // Cannot determine.
537
538 NextBB = BI->getSuccessor(!Cond->getZExtValue());
539 }
540 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
541 ConstantInt *Val =
542 dyn_cast<ConstantInt>(getVal(SI->getCondition()));
543 if (!Val) return false; // Cannot determine.
544 NextBB = SI->findCaseValue(Val)->getCaseSuccessor();
545 } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
546 Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
547 if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
548 NextBB = BA->getBasicBlock();
549 else
550 return false; // Cannot determine.
551 } else if (isa<ReturnInst>(CurInst)) {
552 NextBB = nullptr;
553 } else {
554 // invoke, unwind, resume, unreachable.
555 LLVM_DEBUG(dbgs() << "Can not handle terminator.");
556 return false; // Cannot handle this terminator.
557 }
558
559 // We succeeded at evaluating this block!
560 LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n");
561 return true;
562 } else {
564 for (Value *Op : CurInst->operands())
565 Ops.push_back(getVal(Op));
566 InstResult = ConstantFoldInstOperands(&*CurInst, Ops, DL, TLI);
567 if (!InstResult) {
568 LLVM_DEBUG(dbgs() << "Cannot fold instruction: " << *CurInst << "\n");
569 return false;
570 }
571 LLVM_DEBUG(dbgs() << "Folded instruction " << *CurInst << " to "
572 << *InstResult << "\n");
573 }
574
575 if (!CurInst->use_empty()) {
576 InstResult = ConstantFoldConstant(InstResult, DL, TLI);
577 setVal(&*CurInst, InstResult);
578 }
579
580 // If we just processed an invoke, we finished evaluating the block.
581 if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
582 NextBB = II->getNormalDest();
583 LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
584 return true;
585 }
586
587 // Advance program counter.
588 ++CurInst;
589 }
590}
591
592/// Evaluate a call to function F, returning true if successful, false if we
593/// can't evaluate it. ActualArgs contains the formal arguments for the
594/// function.
596 const SmallVectorImpl<Constant*> &ActualArgs) {
597 assert(ActualArgs.size() == F->arg_size() && "wrong number of arguments");
598
599 // Check to see if this function is already executing (recursion). If so,
600 // bail out. TODO: we might want to accept limited recursion.
601 if (is_contained(CallStack, F))
602 return false;
603
604 CallStack.push_back(F);
605
606 // Initialize arguments to the incoming values specified.
607 for (const auto &[ArgNo, Arg] : llvm::enumerate(F->args()))
608 setVal(&Arg, ActualArgs[ArgNo]);
609
610 // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
611 // we can only evaluate any one basic block at most once. This set keeps
612 // track of what we have executed so we can detect recursive cases etc.
613 SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
614
615 // CurBB - The current basic block we're evaluating.
616 BasicBlock *CurBB = &F->front();
617
618 BasicBlock::iterator CurInst = CurBB->begin();
619
620 while (true) {
621 BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
622 LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
623
624 bool StrippedPointerCastsForAliasAnalysis = false;
625
626 if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
627 return false;
628
629 if (!NextBB) {
630 // Successfully running until there's no next block means that we found
631 // the return. Fill it the return value and pop the call stack.
632 ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
633 if (RI->getNumOperands()) {
634 // The Evaluator can look through pointer casts as long as alias
635 // analysis holds because it's just a simple interpreter and doesn't
636 // skip memory accesses due to invariant group metadata, but we can't
637 // let users of Evaluator use a value that's been gleaned looking
638 // through stripping pointer casts.
639 if (StrippedPointerCastsForAliasAnalysis &&
640 !RI->getReturnValue()->getType()->isVoidTy()) {
641 return false;
642 }
643 RetVal = getVal(RI->getOperand(0));
644 }
645 CallStack.pop_back();
646 return true;
647 }
648
649 // Okay, we succeeded in evaluating this control flow. See if we have
650 // executed the new block before. If so, we have a looping function,
651 // which we cannot evaluate in reasonable time.
652 if (!ExecutedBlocks.insert(NextBB).second)
653 return false; // looped!
654
655 // Okay, we have never been in this block before. Check to see if there
656 // are any PHI nodes. If so, evaluate them with information about where
657 // we came from.
658 PHINode *PN = nullptr;
659 for (CurInst = NextBB->begin();
660 (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
661 setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
662
663 // Advance to the next block.
664 CurBB = NextBB;
665 }
666}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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:57
static bool isSimpleEnoughValueToCommit(Constant *C, SmallPtrSetImpl< Constant * > &SimpleConstants, const DataLayout &DL)
Definition: Evaluator.cpp:114
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
uint64_t IntrinsicInst * II
#define P(N)
const SmallVectorImpl< MachineOperand > & Cond
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.
#define LLVM_DEBUG(...)
Definition: Debug.h:119
static Function * getFunction(FunctionType *Ty, const Twine &Name, Module *M)
Class for arbitrary precision integers.
Definition: APInt.h:78
an instruction to allocate memory on the stack
Definition: Instructions.h:64
LLVM Basic Block Representation.
Definition: BasicBlock.h:62
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:459
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:170
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:233
The address of a basic block.
Definition: Constants.h:899
Conditional or Unconditional Branch instruction.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1116
bool isInlineAsm() const
Check if this call is an inline asm statement.
Definition: InstrTypes.h:1415
Value * getCalledOperand() const
Definition: InstrTypes.h:1340
FunctionType * getFunctionType() const
Definition: InstrTypes.h:1205
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
Definition: InstrTypes.h:1283
static LLVM_ABI 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 LLVM_ABI Constant * get(ArrayType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1314
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:1120
static LLVM_ABI Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2314
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2300
static LLVM_ABI Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2328
This is the shared class of boolean and integer constants.
Definition: Constants.h:87
static LLVM_ABI Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1380
static LLVM_ABI Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1423
This is an important base class in LLVM.
Definition: Constant.h:43
const Constant * stripPointerCasts() const
Definition: Constant.h:219
LLVM_ABI bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:90
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
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:595
@ InternalLinkage
Rename collisions when linking (static functions).
Definition: GlobalValue.h:60
Type * getValueType() const
Definition: GlobalValue.h:298
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:49
Invoke instruction.
An instruction for reading from memory.
Definition: Instructions.h:180
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:380
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:401
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:541
size_t size() const
Definition: SmallVector.h:79
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:574
void push_back(const T &Elt)
Definition: SmallVector.h:414
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1197
An instruction for storing to memory.
Definition: Instructions.h:296
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:267
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:240
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
static LLVM_ABI UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1866
Value * getOperand(unsigned i) const
Definition: User.h:232
unsigned getNumOperands() const
Definition: User.h:254
LLVM Value Representation.
Definition: Value.h:75
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
Definition: Value.cpp:701
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:322
LLVM_ABI const Value * stripPointerCastsForAliasAnalysis() const
Strip off pointer casts, all-zero GEPs, single-argument phi nodes and invariant group info.
Definition: Value.cpp:717
@ 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:477
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition: STLExtras.h:2491
LLVM_ABI Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant * > Operands, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...
LLVM_ABI Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldConstant - Fold the constant using the specified DataLayout.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:207
LLVM_ABI 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:1916
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.