39#define DEBUG_TYPE "evaluator"
62 if (
auto *GV = dyn_cast<GlobalValue>(
C))
63 return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();
66 if (
C->getNumOperands() == 0 || isa<BlockAddress>(
C))
70 if (isa<ConstantAggregate>(
C)) {
83 switch (CE->getOpcode()) {
84 case Instruction::BitCast:
88 case Instruction::IntToPtr:
89 case Instruction::PtrToInt:
92 if (
DL.getTypeSizeInBits(CE->getType()) !=
93 DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
98 case Instruction::GetElementPtr:
99 for (
unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
100 if (!isa<ConstantInt>(CE->getOperand(i)))
104 case Instruction::Add:
106 if (!isa<ConstantInt>(CE->getOperand(1)))
118 if (!SimpleConstants.
insert(
C).second)
124void Evaluator::MutableValue::clear() {
125 if (
auto *Agg = dyn_cast_if_present<MutableAggregate *>(Val))
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)))
141 V = &Agg->Elements[
Index->getZExtValue()];
147bool Evaluator::MutableValue::makeMutable() {
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();
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));
170 Type *Ty =
V->getType();
172 MutableValue *MV =
this;
175 if (isa<Constant *>(MV->Val) && !MV->makeMutable())
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)))
185 MV = &Agg->Elements[
Index->getZExtValue()];
188 Type *MVType = MV->getType();
194 else if (Ty != MVType)
201Constant *Evaluator::MutableAggregate::toConstant()
const {
203 for (
const MutableValue &MV : Elements)
206 if (
auto *ST = dyn_cast<StructType>(Ty))
208 if (
auto *AT = dyn_cast<ArrayType>(Ty))
210 assert(isa<FixedVectorType>(Ty) &&
"Must be vector");
218 P = cast<Constant>(
P->stripAndAccumulateConstantOffsets(
221 if (
auto *GV = dyn_cast<GlobalVariable>(
P))
222 return ComputeLoadResult(GV, Ty,
Offset);
228 auto It = MutatedMemory.find(GV);
229 if (It != MutatedMemory.end())
230 return It->second.read(Ty,
Offset, DL);
238 if (
auto *Fn = dyn_cast<Function>(
C))
241 if (
auto *Alias = dyn_cast<GlobalAlias>(
C))
242 if (
auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
248Evaluator::getCalleeWithFormalArgs(
CallBase &CB,
252 return getFormalParams(CB, Fn, Formals) ? Fn :
nullptr;
258 auto *FTy =
F->getFunctionType();
274 bool &StrippedPointerCastsForAliasAnalysis) {
279 LLVM_DEBUG(
dbgs() <<
"Evaluating Instruction: " << *CurInst <<
"\n");
281 if (
StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
282 if (
SI->isVolatile()) {
288 if (
Ptr != FoldedPtr) {
295 Ptr = cast<Constant>(
Ptr->stripAndAccumulateConstantOffsets(
298 auto *GV = dyn_cast<GlobalVariable>(
Ptr);
300 LLVM_DEBUG(
dbgs() <<
"Store is not to global with unique initializer: "
309 LLVM_DEBUG(
dbgs() <<
"Store value is too complex to evaluate store. "
315 if (!Res.first->second.write(Val,
Offset, DL))
317 }
else if (
LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
318 if (LI->isVolatile()) {
320 dbgs() <<
"Found a Load! Volatile load, can not evaluate.\n");
326 if (
Ptr != FoldedPtr) {
328 LLVM_DEBUG(
dbgs() <<
"Found a constant pointer expression, constant "
332 InstResult = ComputeLoadResult(
Ptr, LI->getType());
335 dbgs() <<
"Failed to compute load result. Can not evaluate load."
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");
346 Type *Ty = AI->getAllocatedType();
347 AllocaTmps.push_back(std::make_unique<GlobalVariable>(
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);
364 if (MSI->isVolatile()) {
370 auto *LenC = dyn_cast<ConstantInt>(getVal(MSI->getLength()));
378 Ptr = cast<Constant>(
Ptr->stripAndAccumulateConstantOffsets(
380 auto *GV = dyn_cast<GlobalVariable>(
Ptr);
386 Constant *Val = getVal(MSI->getValue());
389 if (!Val->
isNullValue() || MutatedMemory.contains(GV) ||
393 if (
Len.ugt(64 * 1024)) {
401 if (DestVal != Val) {
403 <<
Offset <<
" of " << *GV <<
".\n");
416 if (
II->isLifetimeStartOrEnd()) {
422 if (
II->getIntrinsicID() == Intrinsic::invariant_start) {
425 if (!
II->use_empty()) {
427 <<
"Found unused invariant_start. Can't evaluate.\n");
431 Value *PtrArg = getVal(
II->getArgOperand(1));
435 if (!
Size->isMinusOne() &&
436 Size->getValue().getLimitedValue() >=
437 DL.getTypeStoreSize(ElemTy)) {
438 Invariants.insert(GV);
443 <<
"Found a global var, but can not treat it as an "
450 }
else if (
II->getIntrinsicID() == Intrinsic::assume) {
454 }
else if (
II->getIntrinsicID() == Intrinsic::sideeffect) {
458 }
else if (
II->getIntrinsicID() == Intrinsic::pseudoprobe) {
467 if (Stripped != &*CurInst) {
468 InstResult = getVal(Stripped);
472 <<
"Stripped pointer casts for alias analysis for "
473 "intrinsic call.\n");
474 StrippedPointerCastsForAliasAnalysis =
true;
487 if (!Callee ||
Callee->isInterposable()) {
492 if (
Callee->isDeclaration()) {
497 << *InstResult <<
"\n");
503 if (
Callee->getFunctionType()->isVarArg()) {
505 <<
"Can not constant fold vararg function call.\n");
511 ValueStack.emplace_back();
516 ValueStack.pop_back();
520 << *InstResult <<
"\n\n");
523 <<
"Successfully evaluated function. Result: 0\n\n");
527 }
else if (CurInst->isTerminator()) {
530 if (
BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
531 if (BI->isUnconditional()) {
532 NextBB = BI->getSuccessor(0);
535 dyn_cast<ConstantInt>(getVal(BI->getCondition()));
536 if (!
Cond)
return false;
538 NextBB = BI->getSuccessor(!
Cond->getZExtValue());
540 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
542 dyn_cast<ConstantInt>(getVal(
SI->getCondition()));
543 if (!Val)
return false;
544 NextBB =
SI->findCaseValue(Val)->getCaseSuccessor();
545 }
else if (
IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
548 NextBB = BA->getBasicBlock();
551 }
else if (isa<ReturnInst>(CurInst)) {
564 for (
Value *
Op : CurInst->operands())
568 LLVM_DEBUG(
dbgs() <<
"Cannot fold instruction: " << *CurInst <<
"\n");
572 << *InstResult <<
"\n");
575 if (!CurInst->use_empty()) {
577 setVal(&*CurInst, InstResult);
582 NextBB =
II->getNormalDest();
583 LLVM_DEBUG(
dbgs() <<
"Found an invoke instruction. Finished Block.\n\n");
597 assert(ActualArgs.
size() ==
F->arg_size() &&
"wrong number of arguments");
604 CallStack.push_back(
F);
608 setVal(&Arg, ActualArgs[ArgNo]);
622 LLVM_DEBUG(
dbgs() <<
"Trying to evaluate BB: " << *CurBB <<
"\n");
624 bool StrippedPointerCastsForAliasAnalysis =
false;
626 if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
639 if (StrippedPointerCastsForAliasAnalysis &&
645 CallStack.pop_back();
652 if (!ExecutedBlocks.
insert(NextBB).second)
659 for (CurInst = NextBB->
begin();
660 (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
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.
static bool isSimpleEnoughValueToCommitHelper(Constant *C, SmallPtrSetImpl< Constant * > &SimpleConstants, const DataLayout &DL)
Return true if the specified constant can be handled by the code generator.
static bool isSimpleEnoughValueToCommit(Constant *C, SmallPtrSetImpl< Constant * > &SimpleConstants, const DataLayout &DL)
uint64_t IntrinsicInst * II
const SmallVectorImpl< MachineOperand > & Cond
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
static Function * getFunction(FunctionType *Ty, const Twine &Name, Module *M)
Class for arbitrary precision integers.
an instruction to allocate memory on the stack
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
InstListType::iterator iterator
Instruction iterators...
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...
The address of a basic block.
Conditional or Unconditional Branch instruction.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
bool isInlineAsm() const
Check if this call is an inline asm statement.
Value * getCalledOperand() const
FunctionType * getFunctionType() const
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
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)
A constant value that is initialized with an expression using other constant values.
static LLVM_ABI Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getPtrToInt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
This is the shared class of boolean and integer constants.
static LLVM_ABI Constant * get(StructType *T, ArrayRef< Constant * > V)
static LLVM_ABI Constant * get(ArrayRef< Constant * > V)
This is an important base class in LLVM.
const Constant * stripPointerCasts() const
LLVM_ABI bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
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.
@ InternalLinkage
Rename collisions when linking (static functions).
Type * getValueType() const
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.
An instruction for reading from memory.
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...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
bool isIntegerTy() const
True if this is an instance of IntegerType.
bool isVoidTy() const
Return true if this is 'void'.
static LLVM_ABI UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI const Value * stripPointerCastsForAliasAnalysis() const
Strip off pointer casts, all-zero GEPs, single-argument phi nodes and invariant group info.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
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.
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.
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.