40 #define DEBUG_TYPE "evaluator"
63 if (
auto *GV = dyn_cast<GlobalValue>(
C))
64 return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();
67 if (
C->getNumOperands() == 0 || isa<BlockAddress>(
C))
71 if (isa<ConstantAggregate>(
C)) {
82 switch (CE->getOpcode()) {
83 case Instruction::BitCast:
87 case Instruction::IntToPtr:
88 case Instruction::PtrToInt:
91 if (
DL.getTypeSizeInBits(CE->getType()) !=
92 DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
97 case Instruction::GetElementPtr:
98 for (
unsigned i = 1,
e = CE->getNumOperands();
i !=
e; ++
i)
99 if (!isa<ConstantInt>(CE->getOperand(
i)))
105 if (!isa<ConstantInt>(CE->getOperand(1)))
117 if (!SimpleConstants.
insert(
C).second)
124 if (
auto *Agg = Val.dyn_cast<MutableAggregate *>())
132 const MutableValue *V =
this;
133 while (
const auto *Agg = V->Val.dyn_cast<MutableAggregate *>()) {
134 Type *AggTy = Agg->Ty;
136 if (!
Index ||
Index->uge(Agg->Elements.size()) ||
140 V = &Agg->Elements[
Index->getZExtValue()];
146 bool Evaluator::MutableValue::makeMutable() {
148 Type *Ty =
C->getType();
149 unsigned NumElements;
150 if (
auto *VT = dyn_cast<FixedVectorType>(Ty)) {
151 NumElements = VT->getNumElements();
152 }
else if (
auto *AT = dyn_cast<ArrayType>(Ty))
153 NumElements = AT->getNumElements();
154 else if (
auto *
ST = dyn_cast<StructType>(Ty))
155 NumElements =
ST->getNumElements();
159 MutableAggregate *MA =
new MutableAggregate(Ty);
160 MA->Elements.reserve(NumElements);
161 for (
unsigned I = 0;
I < NumElements; ++
I)
162 MA->Elements.push_back(
C->getAggregateElement(
I));
171 MutableValue *MV =
this;
172 while (Offset != 0 ||
174 if (MV->Val.is<
Constant *>() && !MV->makeMutable())
177 MutableAggregate *Agg = MV->Val.get<MutableAggregate *>();
178 Type *AggTy = Agg->Ty;
180 if (!
Index ||
Index->uge(Agg->Elements.size()) ||
184 MV = &Agg->Elements[
Index->getZExtValue()];
187 Type *MVType = MV->getType();
193 else if (Ty != MVType)
200 Constant *Evaluator::MutableAggregate::toConstant()
const {
202 for (
const MutableValue &MV : Elements)
203 Consts.push_back(MV.toConstant());
205 if (
auto *
ST = dyn_cast<StructType>(Ty))
207 if (
auto *AT = dyn_cast<ArrayType>(Ty))
209 assert(isa<FixedVectorType>(Ty) &&
"Must be vector");
217 P = cast<Constant>(
P->stripAndAccumulateConstantOffsets(
220 auto *GV = dyn_cast<GlobalVariable>(
P);
224 auto It = MutatedMemory.find(GV);
225 if (It != MutatedMemory.end())
226 return It->second.read(Ty, Offset, DL);
228 if (!GV->hasDefinitiveInitializer())
234 if (
auto *Fn = dyn_cast<Function>(
C))
237 if (
auto *Alias = dyn_cast<GlobalAlias>(
C))
238 if (
auto *Fn = dyn_cast<Function>(Alias->getAliasee()))
244 Evaluator::getCalleeWithFormalArgs(
CallBase &CB,
248 return getFormalParams(CB, Fn, Formals) ? Fn :
nullptr;
257 auto *FTy =
F->getFunctionType();
258 if (FTy->getNumParams() > CB.
arg_size()) {
264 for (
Type *PTy : FTy->params()) {
270 Formals.push_back(ArgC);
293 bool &StrippedPointerCastsForAliasAnalysis) {
298 LLVM_DEBUG(
dbgs() <<
"Evaluating Instruction: " << *CurInst <<
"\n");
300 if (
StoreInst *
SI = dyn_cast<StoreInst>(CurInst)) {
301 if (!
SI->isSimple()) {
307 if (Ptr != FoldedPtr) {
308 LLVM_DEBUG(
dbgs() <<
"Folding constant ptr expression: " << *Ptr);
317 auto *GV = dyn_cast<GlobalVariable>(Ptr);
318 if (!GV || !GV->hasUniqueInitializer()) {
319 LLVM_DEBUG(
dbgs() <<
"Store is not to global with unique initializer: "
328 LLVM_DEBUG(
dbgs() <<
"Store value is too complex to evaluate store. "
333 auto Res = MutatedMemory.try_emplace(GV, GV->getInitializer());
334 if (!Res.first->second.write(Val, Offset, DL))
336 }
else if (
BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
338 getVal(BO->getOperand(0)),
339 getVal(BO->getOperand(1)));
341 << *InstResult <<
"\n");
342 }
else if (
CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
344 getVal(CI->getOperand(0)),
345 getVal(CI->getOperand(1)));
346 LLVM_DEBUG(
dbgs() <<
"Found a CmpInst! Simplifying: " << *InstResult
348 }
else if (
CastInst *CI = dyn_cast<CastInst>(CurInst)) {
350 getVal(CI->getOperand(0)),
354 }
else if (
SelectInst *
SI = dyn_cast<SelectInst>(CurInst)) {
356 getVal(
SI->getOperand(1)),
357 getVal(
SI->getOperand(2)));
358 LLVM_DEBUG(
dbgs() <<
"Found a Select! Simplifying: " << *InstResult
360 }
else if (
auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
362 getVal(EVI->getAggregateOperand()), EVI->getIndices());
364 << *InstResult <<
"\n");
365 }
else if (
auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
367 getVal(IVI->getAggregateOperand()),
368 getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
370 << *InstResult <<
"\n");
375 GEPOps.push_back(getVal(
Op));
378 cast<GEPOperator>(
GEP)->isInBounds());
379 LLVM_DEBUG(
dbgs() <<
"Found a GEP! Simplifying: " << *InstResult <<
"\n");
380 }
else if (
LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
381 if (!LI->isSimple()) {
383 dbgs() <<
"Found a Load! Not a simple load, can not evaluate.\n");
387 Constant *Ptr = getVal(LI->getOperand(0));
389 if (Ptr != FoldedPtr) {
391 LLVM_DEBUG(
dbgs() <<
"Found a constant pointer expression, constant "
395 InstResult = ComputeLoadResult(Ptr, LI->getType());
398 dbgs() <<
"Failed to compute load result. Can not evaluate load."
404 }
else if (
AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
405 if (AI->isArrayAllocation()) {
406 LLVM_DEBUG(
dbgs() <<
"Found an array alloca. Can not evaluate.\n");
409 Type *Ty = AI->getAllocatedType();
410 AllocaTmps.push_back(std::make_unique<GlobalVariable>(
413 AI->getType()->getPointerAddressSpace()));
414 InstResult = AllocaTmps.back().get();
415 LLVM_DEBUG(
dbgs() <<
"Found an alloca. Result: " << *InstResult <<
"\n");
416 }
else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
417 CallBase &CB = *cast<CallBase>(&*CurInst);
420 if (isa<DbgInfoIntrinsic>(CB)) {
433 if (
MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
434 if (MSI->isVolatile()) {
439 Constant *Ptr = getVal(MSI->getDest());
440 Constant *Val = getVal(MSI->getValue());
442 ComputeLoadResult(getVal(Ptr), MSI->getValue()->
getType());
451 if (II->isLifetimeStartOrEnd()) {
457 if (II->getIntrinsicID() == Intrinsic::invariant_start) {
460 if (!II->use_empty()) {
462 <<
"Found unused invariant_start. Can't evaluate.\n");
466 Value *PtrArg = getVal(II->getArgOperand(1));
469 Type *ElemTy = GV->getValueType();
470 if (!
Size->isMinusOne() &&
471 Size->getValue().getLimitedValue() >=
472 DL.getTypeStoreSize(ElemTy)) {
473 Invariants.insert(GV);
478 <<
"Found a global var, but can not treat it as an "
485 }
else if (II->getIntrinsicID() == Intrinsic::assume) {
489 }
else if (II->getIntrinsicID() == Intrinsic::sideeffect) {
493 }
else if (II->getIntrinsicID() == Intrinsic::pseudoprobe) {
502 if (Stripped != &*CurInst) {
503 InstResult = getVal(Stripped);
507 <<
"Stripped pointer casts for alias analysis for "
508 "intrinsic call.\n");
509 StrippedPointerCastsForAliasAnalysis =
true;
522 if (!Callee ||
Callee->isInterposable()) {
527 if (
Callee->isDeclaration()) {
530 InstResult = castCallResultIfNeeded(CB.
getType(),
C);
534 << *InstResult <<
"\n");
542 <<
"Can not constant fold vararg function call.\n");
548 ValueStack.emplace_back();
553 ValueStack.pop_back();
554 InstResult = castCallResultIfNeeded(CB.
getType(), RetVal);
555 if (RetVal && !InstResult)
560 << *InstResult <<
"\n\n");
563 <<
"Successfully evaluated function. Result: 0\n\n");
567 }
else if (CurInst->isTerminator()) {
570 if (
BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
571 if (BI->isUnconditional()) {
572 NextBB = BI->getSuccessor(0);
575 dyn_cast<ConstantInt>(getVal(BI->getCondition()));
576 if (!
Cond)
return false;
578 NextBB = BI->getSuccessor(!
Cond->getZExtValue());
580 }
else if (
SwitchInst *
SI = dyn_cast<SwitchInst>(CurInst)) {
582 dyn_cast<ConstantInt>(getVal(
SI->getCondition()));
583 if (!Val)
return false;
584 NextBB =
SI->findCaseValue(Val)->getCaseSuccessor();
585 }
else if (
IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
588 NextBB = BA->getBasicBlock();
591 }
else if (isa<ReturnInst>(CurInst)) {
605 dbgs() <<
"Failed to evaluate block due to unhandled instruction."
610 if (!CurInst->use_empty()) {
612 setVal(&*CurInst, InstResult);
616 if (
InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
617 NextBB = II->getNormalDest();
618 LLVM_DEBUG(
dbgs() <<
"Found an invoke instruction. Finished Block.\n\n");
632 assert(ActualArgs.size() ==
F->arg_size() &&
"wrong number of arguments");
639 CallStack.push_back(
F);
645 setVal(&*AI, ActualArgs[ArgNo]);
659 LLVM_DEBUG(
dbgs() <<
"Trying to evaluate BB: " << *CurBB <<
"\n");
661 bool StrippedPointerCastsForAliasAnalysis =
false;
663 if (!EvaluateBlock(CurInst, NextBB, StrippedPointerCastsForAliasAnalysis))
676 if (StrippedPointerCastsForAliasAnalysis &&
682 CallStack.pop_back();
689 if (!ExecutedBlocks.
insert(NextBB).second)
696 for (CurInst = NextBB->
begin();
697 (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)