667 lines · cpp
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-exception6//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 bool44isSimpleEnoughValueToCommit(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 the55/// time.56static bool57isSimpleEnoughValueToCommitHelper(Constant *C,58 SmallPtrSetImpl<Constant *> &SimpleConstants,59 const DataLayout &DL) {60 // Simple global addresses are supported, do not allow dllimport or61 // 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 supported79 // 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 the91 // 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 bool114isSimpleEnoughValueToCommit(Constant *C,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 else158 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 else197 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(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 stores215/// 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 237static Function *getFunction(Constant *C) {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,249 SmallVectorImpl<Constant *> &Formals) {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,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(getVal(Arg));266 return true;267}268 269/// Evaluate all instructions in block BB, returning true if successful, false270/// 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 if272/// 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 addr306 // 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()) {319 LLVM_DEBUG(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) {334 LLVM_DEBUG(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>(348 Ty, false, GlobalValue::InternalLinkage, UndefValue::get(Ty),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 zeroinitializer388 // to zero.389 if (!Val->isNullValue() || MutatedMemory.contains(GV) ||390 !GV->hasDefinitiveInitializer() ||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 a424 // meaningful return value.425 if (!II->use_empty()) {426 LLVM_DEBUG(dbgs()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 {442 LLVM_DEBUG(dbgs()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 strip465 // anything away, or else we'll call getVal() on the current466 // instruction.467 if (Stripped != &*CurInst) {468 InstResult = getVal(Stripped);469 }470 if (InstResult) {471 LLVM_DEBUG(dbgs()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.485 SmallVector<Constant *, 8> Formals;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()) {504 LLVM_DEBUG(dbgs()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 {522 LLVM_DEBUG(dbgs()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 {534 ConstantInt *Cond =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 else550 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 {563 SmallVector<Constant *> Ops;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 we593/// can't evaluate it. ActualArgs contains the formal arguments for the594/// function.595bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,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 keeps612 // 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 found631 // 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 alias635 // analysis holds because it's just a simple interpreter and doesn't636 // skip memory accesses due to invariant group metadata, but we can't637 // let users of Evaluator use a value that's been gleaned looking638 // 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 have650 // 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 there656 // are any PHI nodes. If so, evaluate them with information about where657 // 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}667