| //===- Evaluator.cpp - LLVM IR evaluator ----------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // Function evaluator for LLVM IR. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "llvm/Transforms/Utils/Evaluator.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/Analysis/ConstantFolding.h" |
| #include "llvm/IR/BasicBlock.h" |
| #include "llvm/IR/Constant.h" |
| #include "llvm/IR/Constants.h" |
| #include "llvm/IR/DataLayout.h" |
| #include "llvm/IR/DerivedTypes.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/IR/GlobalAlias.h" |
| #include "llvm/IR/GlobalValue.h" |
| #include "llvm/IR/GlobalVariable.h" |
| #include "llvm/IR/InstrTypes.h" |
| #include "llvm/IR/Instruction.h" |
| #include "llvm/IR/Instructions.h" |
| #include "llvm/IR/IntrinsicInst.h" |
| #include "llvm/IR/Operator.h" |
| #include "llvm/IR/Type.h" |
| #include "llvm/IR/User.h" |
| #include "llvm/IR/Value.h" |
| #include "llvm/Support/Casting.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/raw_ostream.h" |
| |
| #define DEBUG_TYPE "evaluator" |
| |
| using namespace llvm; |
| |
| static inline bool |
| isSimpleEnoughValueToCommit(Constant *C, |
| SmallPtrSetImpl<Constant *> &SimpleConstants, |
| const DataLayout &DL); |
| |
| /// Return true if the specified constant can be handled by the code generator. |
| /// We don't want to generate something like: |
| /// void *X = &X/42; |
| /// because the code generator doesn't have a relocation that can handle that. |
| /// |
| /// This function should be called if C was not found (but just got inserted) |
| /// in SimpleConstants to avoid having to rescan the same constants all the |
| /// time. |
| static bool |
| isSimpleEnoughValueToCommitHelper(Constant *C, |
| SmallPtrSetImpl<Constant *> &SimpleConstants, |
| const DataLayout &DL) { |
| // Simple global addresses are supported, do not allow dllimport or |
| // thread-local globals. |
| if (auto *GV = dyn_cast<GlobalValue>(C)) |
| return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal(); |
| |
| // Simple integer, undef, constant aggregate zero, etc are all supported. |
| if (C->getNumOperands() == 0 || isa<BlockAddress>(C)) |
| return true; |
| |
| // Aggregate values are safe if all their elements are. |
| if (isa<ConstantAggregate>(C)) { |
| for (Value *Op : C->operands()) |
| if (!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL)) |
| return false; |
| return true; |
| } |
| |
| // We don't know exactly what relocations are allowed in constant expressions, |
| // so we allow &global+constantoffset, which is safe and uniformly supported |
| // across targets. |
| ConstantExpr *CE = cast<ConstantExpr>(C); |
| switch (CE->getOpcode()) { |
| case Instruction::BitCast: |
| // Bitcast is fine if the casted value is fine. |
| return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
| |
| case Instruction::IntToPtr: |
| case Instruction::PtrToInt: |
| // int <=> ptr is fine if the int type is the same size as the |
| // pointer type. |
| if (DL.getTypeSizeInBits(CE->getType()) != |
| DL.getTypeSizeInBits(CE->getOperand(0)->getType())) |
| return false; |
| return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
| |
| // GEP is fine if it is simple + constant offset. |
| case Instruction::GetElementPtr: |
| for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) |
| if (!isa<ConstantInt>(CE->getOperand(i))) |
| return false; |
| return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
| |
| case Instruction::Add: |
| // We allow simple+cst. |
| if (!isa<ConstantInt>(CE->getOperand(1))) |
| return false; |
| return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); |
| } |
| return false; |
| } |
| |
| static inline bool |
| isSimpleEnoughValueToCommit(Constant *C, |
| SmallPtrSetImpl<Constant *> &SimpleConstants, |
| const DataLayout &DL) { |
| // If we already checked this constant, we win. |
| if (!SimpleConstants.insert(C).second) |
| return true; |
| // Check the constant. |
| return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL); |
| } |
| |
| void Evaluator::MutableValue::clear() { |
| if (auto *Agg = Val.dyn_cast<MutableAggregate *>()) |
| delete Agg; |
| Val = nullptr; |
| } |
| |
| Constant *Evaluator::MutableValue::read(Type *Ty, APInt Offset, |
| const DataLayout &DL) const { |
| TypeSize TySize = DL.getTypeStoreSize(Ty); |
| const MutableValue *V = this; |
| while (const auto *Agg = V->Val.dyn_cast<MutableAggregate *>()) { |
| Type *AggTy = Agg->Ty; |
| std::optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset); |
| if (!Index || Index->uge(Agg->Elements.size()) || |
| !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy))) |
| return nullptr; |
| |
| V = &Agg->Elements[Index->getZExtValue()]; |
| } |
| |
| return ConstantFoldLoadFromConst(V->Val.get<Constant *>(), Ty, Offset, DL); |
| } |
| |
| bool Evaluator::MutableValue::makeMutable() { |
| Constant *C = Val.get<Constant *>(); |
| Type *Ty = C->getType(); |
| unsigned NumElements; |
| if (auto *VT = dyn_cast<FixedVectorType>(Ty)) { |
| NumElements = VT->getNumElements(); |
| } else if (auto *AT = dyn_cast<ArrayType>(Ty)) |
| NumElements = AT->getNumElements(); |
| else if (auto *ST = dyn_cast<StructType>(Ty)) |
| NumElements = ST->getNumElements(); |
| else |
| return false; |
| |
| MutableAggregate *MA = new MutableAggregate(Ty); |
| MA->Elements.reserve(NumElements); |
| for (unsigned I = 0; I < NumElements; ++I) |
| MA->Elements.push_back(C->getAggregateElement(I)); |
| Val = MA; |
| return true; |
| } |
| |
| bool Evaluator::MutableValue::write(Constant *V, APInt Offset, |
| const DataLayout &DL) { |
| Type *Ty = V->getType(); |
| TypeSize TySize = DL.getTypeStoreSize(Ty); |
| MutableValue *MV = this; |
| while (Offset != 0 || |
| !CastInst::isBitOrNoopPointerCastable(Ty, MV->getType(), DL)) { |
| if (MV->Val.is<Constant *>() && !MV->makeMutable()) |
| return false; |
| |
| MutableAggregate *Agg = MV->Val.get<MutableAggregate *>(); |
| Type *AggTy = Agg->Ty; |
| std::optional<APInt> Index = DL.getGEPIndexForOffset(AggTy, Offset); |
| if (!Index || Index->uge(Agg->Elements.size()) || |
| !TypeSize::isKnownLE(TySize, DL.getTypeStoreSize(AggTy))) |
| return false; |
| |
| MV = &Agg->Elements[Index->getZExtValue()]; |
| } |
| |
| Type *MVType = MV->getType(); |
| MV->clear(); |
| if (Ty->isIntegerTy() && MVType->isPointerTy()) |
| MV->Val = ConstantExpr::getIntToPtr(V, MVType); |
| else if (Ty->isPointerTy() && MVType->isIntegerTy()) |
| MV->Val = ConstantExpr::getPtrToInt(V, MVType); |
| else if (Ty != MVType) |
| MV->Val = ConstantExpr::getBitCast(V, MVType); |
| else |
| MV->Val = V; |
| return true; |
| } |
| |
| Constant *Evaluator::MutableAggregate::toConstant() const { |
| SmallVector<Constant *, 32> Consts; |
| for (const MutableValue &MV : Elements) |
| Consts.push_back(MV.toConstant()); |
| |
| if (auto *ST = dyn_cast<StructType>(Ty)) |
| return ConstantStruct::get(ST, Consts); |
| if (auto *AT = dyn_cast<ArrayType>(Ty)) |
| return ConstantArray::get(AT, Consts); |
| assert(isa<FixedVectorType>(Ty) && "Must be vector"); |
| return ConstantVector::get(Consts); |
| } |
| |
| /// Return the value that would be computed by a load from P after the stores |
| /// reflected by 'memory' have been performed. If we can't decide, return null. |
| Constant *Evaluator::ComputeLoadResult(Constant *P, Type *Ty) { |
| APInt Offset(DL.getIndexTypeSizeInBits(P->getType()), 0); |
| P = cast<Constant>(P->stripAndAccumulateConstantOffsets( |
| DL, Offset, /* AllowNonInbounds */ true)); |
| Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(P->getType())); |
| if (auto *GV = dyn_cast<GlobalVariable>(P)) |
| return ComputeLoadResult(GV, Ty, Offset); |
| return nullptr; |
| } |
| |
| Constant *Evaluator::ComputeLoadResult(GlobalVariable *GV, Type *Ty, |
| const APInt &Offset) { |
| auto It = MutatedMemory.find(GV); |
| if (It != MutatedMemory.end()) |
| return It->second.read(Ty, Offset, DL); |
| |
| if (!GV->hasDefinitiveInitializer()) |
| return nullptr; |
| return ConstantFoldLoadFromConst(GV->getInitializer(), Ty, Offset, DL); |
| } |
| |
| static Function *getFunction(Constant *C) { |
| if (auto *Fn = dyn_cast<Function>(C)) |
| return Fn; |
| |
| if (auto *Alias = dyn_cast<GlobalAlias>(C)) |
| if (auto *Fn = dyn_cast<Function>(Alias->getAliasee())) |
| return Fn; |
| return nullptr; |
| } |
| |
| Function * |
| Evaluator::getCalleeWithFormalArgs(CallBase &CB, |
| SmallVectorImpl<Constant *> &Formals) { |
| auto *V = CB.getCalledOperand()->stripPointerCasts(); |
| if (auto *Fn = getFunction(getVal(V))) |
| return getFormalParams(CB, Fn, Formals) ? Fn : nullptr; |
| return nullptr; |
| } |
| |
| bool Evaluator::getFormalParams(CallBase &CB, Function *F, |
| SmallVectorImpl<Constant *> &Formals) { |
| if (!F) |
| return false; |
| |
| auto *FTy = F->getFunctionType(); |
| if (FTy->getNumParams() > CB.arg_size()) { |
| LLVM_DEBUG(dbgs() << "Too few arguments for function.\n"); |
| return false; |
| } |
| |
| auto ArgI = CB.arg_begin(); |
| for (Type *PTy : FTy->params()) { |
| auto *ArgC = ConstantFoldLoadThroughBitcast(getVal(*ArgI), PTy, DL); |
| if (!ArgC) { |
| LLVM_DEBUG(dbgs() << "Can not convert function argument.\n"); |
| return false; |
| } |
| Formals.push_back(ArgC); |
| ++ArgI; |
| } |
| return true; |
| } |
| |
| /// If call expression contains bitcast then we may need to cast |
| /// evaluated return value to a type of the call expression. |
| Constant *Evaluator::castCallResultIfNeeded(Type *ReturnType, Constant *RV) { |
| if (!RV || RV->getType() == ReturnType) |
| return RV; |
| |
| RV = ConstantFoldLoadThroughBitcast(RV, ReturnType, DL); |
| if (!RV) |
| LLVM_DEBUG(dbgs() << "Failed to fold bitcast call expr\n"); |
| return RV; |
| } |
| |
| /// Evaluate all instructions in block BB, returning true if successful, false |
| /// if we can't evaluate it. NewBB returns the next BB that control flows into, |
| /// or null upon return. StrippedPointerCastsForAliasAnalysis is set to true if |
| /// we looked through pointer casts to evaluate something. |
| bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB, |
| bool &StrippedPointerCastsForAliasAnalysis) { |
| // This is the main evaluation loop. |
| while (true) { |
| Constant *InstResult = nullptr; |
| |
| LLVM_DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n"); |
| |
| if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) { |
| if (SI->isVolatile()) { |
| LLVM_DEBUG(dbgs() << "Store is volatile! Can not evaluate.\n"); |
| return false; // no volatile accesses. |
| } |
| Constant *Ptr = getVal(SI->getOperand(1)); |
| Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI); |
| if (Ptr != FoldedPtr) { |
| LLVM_DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr); |
| Ptr = FoldedPtr; |
| LLVM_DEBUG(dbgs() << "; To: " << *Ptr << "\n"); |
| } |
| |
| APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0); |
| Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets( |
| DL, Offset, /* AllowNonInbounds */ true)); |
| Offset = Offset.sextOrTrunc(DL.getIndexTypeSizeInBits(Ptr->getType())); |
| auto *GV = dyn_cast<GlobalVariable>(Ptr); |
| if (!GV || !GV->hasUniqueInitializer()) { |
| LLVM_DEBUG(dbgs() << "Store is not to global with unique initializer: " |
| << *Ptr << "\n"); |
| return false; |
| } |
| |
| // If this might be too difficult for the backend to handle (e.g. the addr |
| // of one global variable divided by another) then we can't commit it. |
| Constant *Val = getVal(SI->getOperand(0)); |
| if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) { |
| LLVM_DEBUG(dbgs() << "Store value is too complex to evaluate store. " |
| << *Val << "\n"); |
| return false; |
| } |
| |
| auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer()); |
| if (!Res.first->second.write(Val, Offset, DL)) |
| return false; |
| } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) { |
| if (LI->isVolatile()) { |
| LLVM_DEBUG( |
| dbgs() << "Found a Load! Volatile load, can not evaluate.\n"); |
| return false; // no volatile accesses. |
| } |
| |
| Constant *Ptr = getVal(LI->getOperand(0)); |
| Constant *FoldedPtr = ConstantFoldConstant(Ptr, DL, TLI); |
| if (Ptr != FoldedPtr) { |
| Ptr = FoldedPtr; |
| LLVM_DEBUG(dbgs() << "Found a constant pointer expression, constant " |
| "folding: " |
| << *Ptr << "\n"); |
| } |
| InstResult = ComputeLoadResult(Ptr, LI->getType()); |
| if (!InstResult) { |
| LLVM_DEBUG( |
| dbgs() << "Failed to compute load result. Can not evaluate load." |
| "\n"); |
| return false; // Could not evaluate load. |
| } |
| |
| LLVM_DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n"); |
| } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) { |
| if (AI->isArrayAllocation()) { |
| LLVM_DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n"); |
| return false; // Cannot handle array allocs. |
| } |
| Type *Ty = AI->getAllocatedType(); |
| AllocaTmps.push_back(std::make_unique<GlobalVariable>( |
| Ty, false, GlobalValue::InternalLinkage, UndefValue::get(Ty), |
| AI->getName(), /*TLMode=*/GlobalValue::NotThreadLocal, |
| AI->getType()->getPointerAddressSpace())); |
| InstResult = AllocaTmps.back().get(); |
| LLVM_DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n"); |
| } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) { |
| CallBase &CB = *cast<CallBase>(&*CurInst); |
| |
| // Debug info can safely be ignored here. |
| if (isa<DbgInfoIntrinsic>(CB)) { |
| LLVM_DEBUG(dbgs() << "Ignoring debug info.\n"); |
| ++CurInst; |
| continue; |
| } |
| |
| // Cannot handle inline asm. |
| if (CB.isInlineAsm()) { |
| LLVM_DEBUG(dbgs() << "Found inline asm, can not evaluate.\n"); |
| return false; |
| } |
| |
| if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(&CB)) { |
| if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) { |
| if (MSI->isVolatile()) { |
| LLVM_DEBUG(dbgs() << "Can not optimize a volatile memset " |
| << "intrinsic.\n"); |
| return false; |
| } |
| |
| auto *LenC = dyn_cast<ConstantInt>(getVal(MSI->getLength())); |
| if (!LenC) { |
| LLVM_DEBUG(dbgs() << "Memset with unknown length.\n"); |
| return false; |
| } |
| |
| Constant *Ptr = getVal(MSI->getDest()); |
| APInt Offset(DL.getIndexTypeSizeInBits(Ptr->getType()), 0); |
| Ptr = cast<Constant>(Ptr->stripAndAccumulateConstantOffsets( |
| DL, Offset, /* AllowNonInbounds */ true)); |
| auto *GV = dyn_cast<GlobalVariable>(Ptr); |
| if (!GV) { |
| LLVM_DEBUG(dbgs() << "Memset with unknown base.\n"); |
| return false; |
| } |
| |
| Constant *Val = getVal(MSI->getValue()); |
| APInt Len = LenC->getValue(); |
| while (Len != 0) { |
| Constant *DestVal = ComputeLoadResult(GV, Val->getType(), Offset); |
| if (DestVal != Val) { |
| LLVM_DEBUG(dbgs() << "Memset is not a no-op at offset " |
| << Offset << " of " << *GV << ".\n"); |
| return false; |
| } |
| ++Offset; |
| --Len; |
| } |
| |
| LLVM_DEBUG(dbgs() << "Ignoring no-op memset.\n"); |
| ++CurInst; |
| continue; |
| } |
| |
| if (II->isLifetimeStartOrEnd()) { |
| LLVM_DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n"); |
| ++CurInst; |
| continue; |
| } |
| |
| if (II->getIntrinsicID() == Intrinsic::invariant_start) { |
| // We don't insert an entry into Values, as it doesn't have a |
| // meaningful return value. |
| if (!II->use_empty()) { |
| LLVM_DEBUG(dbgs() |
| << "Found unused invariant_start. Can't evaluate.\n"); |
| return false; |
| } |
| ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0)); |
| Value *PtrArg = getVal(II->getArgOperand(1)); |
| Value *Ptr = PtrArg->stripPointerCasts(); |
| if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { |
| Type *ElemTy = GV->getValueType(); |
| if (!Size->isMinusOne() && |
| Size->getValue().getLimitedValue() >= |
| DL.getTypeStoreSize(ElemTy)) { |
| Invariants.insert(GV); |
| LLVM_DEBUG(dbgs() << "Found a global var that is an invariant: " |
| << *GV << "\n"); |
| } else { |
| LLVM_DEBUG(dbgs() |
| << "Found a global var, but can not treat it as an " |
| "invariant.\n"); |
| } |
| } |
| // Continue even if we do nothing. |
| ++CurInst; |
| continue; |
| } else if (II->getIntrinsicID() == Intrinsic::assume) { |
| LLVM_DEBUG(dbgs() << "Skipping assume intrinsic.\n"); |
| ++CurInst; |
| continue; |
| } else if (II->getIntrinsicID() == Intrinsic::sideeffect) { |
| LLVM_DEBUG(dbgs() << "Skipping sideeffect intrinsic.\n"); |
| ++CurInst; |
| continue; |
| } else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) { |
| LLVM_DEBUG(dbgs() << "Skipping pseudoprobe intrinsic.\n"); |
| ++CurInst; |
| continue; |
| } else { |
| Value *Stripped = CurInst->stripPointerCastsForAliasAnalysis(); |
| // Only attempt to getVal() if we've actually managed to strip |
| // anything away, or else we'll call getVal() on the current |
| // instruction. |
| if (Stripped != &*CurInst) { |
| InstResult = getVal(Stripped); |
| } |
| if (InstResult) { |
| LLVM_DEBUG(dbgs() |
| << "Stripped pointer casts for alias analysis for " |
| "intrinsic call.\n"); |
| StrippedPointerCastsForAliasAnalysis = true; |
| InstResult = ConstantExpr::getBitCast(InstResult, II->getType()); |
| } else { |
| LLVM_DEBUG(dbgs() << "Unknown intrinsic. Cannot evaluate.\n"); |
| return false; |
| } |
| } |
| } |
| |
| if (!InstResult) { |
| // Resolve function pointers. |
| SmallVector<Constant *, 8> Formals; |
| Function *Callee = getCalleeWithFormalArgs(CB, Formals); |
| if (!Callee || Callee->isInterposable()) { |
| LLVM_DEBUG(dbgs() << "Can not resolve function pointer.\n"); |
| return false; // Cannot resolve. |
| } |
| |
| if (Callee->isDeclaration()) { |
| // If this is a function we can constant fold, do it. |
| if (Constant *C = ConstantFoldCall(&CB, Callee, Formals, TLI)) { |
| InstResult = castCallResultIfNeeded(CB.getType(), C); |
| if (!InstResult) |
| return false; |
| LLVM_DEBUG(dbgs() << "Constant folded function call. Result: " |
| << *InstResult << "\n"); |
| } else { |
| LLVM_DEBUG(dbgs() << "Can not constant fold function call.\n"); |
| return false; |
| } |
| } else { |
| if (Callee->getFunctionType()->isVarArg()) { |
| LLVM_DEBUG(dbgs() |
| << "Can not constant fold vararg function call.\n"); |
| return false; |
| } |
| |
| Constant *RetVal = nullptr; |
| // Execute the call, if successful, use the return value. |
| ValueStack.emplace_back(); |
| if (!EvaluateFunction(Callee, RetVal, Formals)) { |
| LLVM_DEBUG(dbgs() << "Failed to evaluate function.\n"); |
| return false; |
| } |
| ValueStack.pop_back(); |
| InstResult = castCallResultIfNeeded(CB.getType(), RetVal); |
| if (RetVal && !InstResult) |
| return false; |
| |
| if (InstResult) { |
| LLVM_DEBUG(dbgs() << "Successfully evaluated function. Result: " |
| << *InstResult << "\n\n"); |
| } else { |
| LLVM_DEBUG(dbgs() |
| << "Successfully evaluated function. Result: 0\n\n"); |
| } |
| } |
| } |
| } else if (CurInst->isTerminator()) { |
| LLVM_DEBUG(dbgs() << "Found a terminator instruction.\n"); |
| |
| if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) { |
| if (BI->isUnconditional()) { |
| NextBB = BI->getSuccessor(0); |
| } else { |
| ConstantInt *Cond = |
| dyn_cast<ConstantInt>(getVal(BI->getCondition())); |
| if (!Cond) return false; // Cannot determine. |
| |
| NextBB = BI->getSuccessor(!Cond->getZExtValue()); |
| } |
| } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) { |
| ConstantInt *Val = |
| dyn_cast<ConstantInt>(getVal(SI->getCondition())); |
| if (!Val) return false; // Cannot determine. |
| NextBB = SI->findCaseValue(Val)->getCaseSuccessor(); |
| } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) { |
| Value *Val = getVal(IBI->getAddress())->stripPointerCasts(); |
| if (BlockAddress *BA = dyn_cast<BlockAddress>(Val)) |
| NextBB = BA->getBasicBlock(); |
| else |
| return false; // Cannot determine. |
| } else if (isa<ReturnInst>(CurInst)) { |
| NextBB = nullptr; |
| } else { |
| // invoke, unwind, resume, unreachable. |
| LLVM_DEBUG(dbgs() << "Can not handle terminator."); |
| return false; // Cannot handle this terminator. |
| } |
| |
| // We succeeded at evaluating this block! |
| LLVM_DEBUG(dbgs() << "Successfully evaluated block.\n"); |
| return true; |
| } else { |
| SmallVector<Constant *> Ops; |
| for (Value *Op : CurInst->operands()) |
| Ops.push_back(getVal(Op)); |
| InstResult = ConstantFoldInstOperands(&*CurInst, Ops, DL, TLI); |
| if (!InstResult) { |
| LLVM_DEBUG(dbgs() << "Cannot fold instruction: " << *CurInst << "\n"); |
| return false; |
| } |
| LLVM_DEBUG(dbgs() << "Folded instruction " << *CurInst << " to " |
| << *InstResult << "\n"); |
| } |
| |
| if (!CurInst->use_empty()) { |
| InstResult = ConstantFoldConstant(InstResult, DL, TLI); |
| setVal(&*CurInst, InstResult); |
| } |
| |
| // If we just processed an invoke, we finished evaluating the block. |
| if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) { |
| NextBB = II->getNormalDest(); |
| LLVM_DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n"); |
| return true; |
| } |
| |
| // Advance program counter. |
| ++CurInst; |
| } |
| } |
| |
| /// Evaluate a call to function F, returning true if successful, false if we |
| /// can't evaluate it. ActualArgs contains the formal arguments for the |
| /// function. |
| bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal, |
| const SmallVectorImpl<Constant*> &ActualArgs) { |
| assert(ActualArgs.size() == F->arg_size() && "wrong number of arguments"); |
| |
| // Check to see if this function is already executing (recursion). If so, |
| // bail out. TODO: we might want to accept limited recursion. |
| if (is_contained(CallStack, F)) |
| return false; |
| |
| CallStack.push_back(F); |
| |
| // Initialize arguments to the incoming values specified. |
| for (const auto &[ArgNo, Arg] : llvm::enumerate(F->args())) |
| setVal(&Arg, ActualArgs[ArgNo]); |
| |
| // ExecutedBlocks - We only handle non-looping, non-recursive code. As such, |
| // we can only evaluate any one basic block at most once. This set keeps |
| // track of what we have executed so we can detect recursive cases etc. |
| SmallPtrSet<BasicBlock*, 32> ExecutedBlocks; |
| |
| // CurBB - The current basic block we're evaluating. |
| BasicBlock *CurBB = &F->front(); |
| |
| BasicBlock::iterator CurInst = CurBB->begin(); |
| |
| while (true) { |
| BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings. |
| LLVM_DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n"); |
| |
| bool StrippedPointerCastsForAliasAnalysis = false; |
| |
| if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis)) |
| return false; |
| |
| if (!NextBB) { |
| // Successfully running until there's no next block means that we found |
| // the return. Fill it the return value and pop the call stack. |
| ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator()); |
| if (RI->getNumOperands()) { |
| // The Evaluator can look through pointer casts as long as alias |
| // analysis holds because it's just a simple interpreter and doesn't |
| // skip memory accesses due to invariant group metadata, but we can't |
| // let users of Evaluator use a value that's been gleaned looking |
| // through stripping pointer casts. |
| if (StrippedPointerCastsForAliasAnalysis && |
| !RI->getReturnValue()->getType()->isVoidTy()) { |
| return false; |
| } |
| RetVal = getVal(RI->getOperand(0)); |
| } |
| CallStack.pop_back(); |
| return true; |
| } |
| |
| // Okay, we succeeded in evaluating this control flow. See if we have |
| // executed the new block before. If so, we have a looping function, |
| // which we cannot evaluate in reasonable time. |
| if (!ExecutedBlocks.insert(NextBB).second) |
| return false; // looped! |
| |
| // Okay, we have never been in this block before. Check to see if there |
| // are any PHI nodes. If so, evaluate them with information about where |
| // we came from. |
| PHINode *PN = nullptr; |
| for (CurInst = NextBB->begin(); |
| (PN = dyn_cast<PHINode>(CurInst)); ++CurInst) |
| setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB))); |
| |
| // Advance to the next block. |
| CurBB = NextBB; |
| } |
| } |
