33#define DEBUG_TYPE "sccp"
46 bool UndefAllowed =
true) {
73 return isa<LoadInst>(
I);
84 CallBase *CB = dyn_cast<CallBase>(V);
95 <<
" as a constant\n");
99 LLVM_DEBUG(
dbgs() <<
" Constant: " << *Const <<
" = " << *V <<
'\n');
102 V->replaceAllUsesWith(Const);
110 bool Changed =
false;
111 auto GetRange = [&Solver, &InsertedValues](
Value *
Op) {
112 if (
auto *Const = dyn_cast<ConstantInt>(
Op))
115 unsigned Bitwidth =
Op->getType()->getScalarSizeInBits();
116 return ConstantRange::getFull(Bitwidth);
122 if (isa<OverflowingBinaryOperator>(Inst)) {
129 if (NUWRange.contains(RangeA)) {
138 if (NSWRange.contains(RangeA)) {
143 }
else if (isa<ZExtInst>(Inst) && !Inst.
hasNonNeg()) {
145 if (Range.isAllNonNegative()) {
159 auto isNonNegative = [&Solver](
Value *V) {
162 if (
auto *
C = dyn_cast<Constant>(V)) {
163 auto *CInt = dyn_cast<ConstantInt>(
C);
164 return CInt && !CInt->isNegative();
167 return IV.isConstantRange(
false) &&
168 IV.getConstantRange().isAllNonNegative();
175 case Instruction::SExt: {
178 if (InsertedValues.
count(Op0) || !isNonNegative(Op0))
184 case Instruction::AShr: {
187 if (InsertedValues.
count(Op0) || !isNonNegative(Op0))
193 case Instruction::SDiv:
194 case Instruction::SRem: {
197 if (InsertedValues.
count(Op0) || InsertedValues.
count(Op1) ||
198 !isNonNegative(Op0) || !isNonNegative(Op1))
200 auto NewOpcode = Inst.
getOpcode() == Instruction::SDiv ? Instruction::UDiv
203 if (Inst.
getOpcode() == Instruction::SDiv)
212 assert(NewInst &&
"Expected replacement instruction");
214 InsertedValues.
insert(NewInst);
225 bool MadeChanges =
false;
227 if (Inst.getType()->isVoidTy())
231 Inst.eraseFromParent();
248 bool HasNonFeasibleEdges =
false;
251 FeasibleSuccessors.
insert(Succ);
253 HasNonFeasibleEdges =
true;
257 if (!HasNonFeasibleEdges)
262 assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
263 isa<IndirectBrInst>(TI)) &&
264 "Terminator must be a br, switch or indirectbr");
266 if (FeasibleSuccessors.
size() == 0) {
271 Succ->removePredecessor(BB);
272 if (SeenSuccs.
insert(Succ).second)
278 }
else if (FeasibleSuccessors.
size() == 1) {
282 bool HaveSeenOnlyFeasibleSuccessor =
false;
284 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
287 HaveSeenOnlyFeasibleSuccessor =
true;
291 Succ->removePredecessor(BB);
298 }
else if (FeasibleSuccessors.
size() > 1) {
304 BasicBlock *DefaultDest = SI->getDefaultDest();
305 if (!FeasibleSuccessors.
contains(DefaultDest)) {
306 if (!NewUnreachableBB) {
314 SI->setDefaultDest(NewUnreachableBB);
319 for (
auto CI = SI->case_begin(); CI != SI->case_end();) {
320 if (FeasibleSuccessors.
contains(CI->getCaseSuccessor())) {
366 TrackedMultipleRetVals;
399 using Edge = std::pair<BasicBlock *, BasicBlock *>;
424 bool MayIncludeUndef =
false);
427 assert(!V->getType()->isStructTy() &&
"structs should use mergeInValue");
428 return markConstant(ValueState[V], V,
C);
446 assert(!V->getType()->isStructTy() &&
447 "non-structs should use markConstant");
448 return mergeInValue(ValueState[V], V, MergeWithV, Opts);
455 assert(!V->getType()->isStructTy() &&
"Should use getStructValueState");
463 if (
auto *
C = dyn_cast<Constant>(V))
474 assert(V->getType()->isStructTy() &&
"Should use getValueState");
475 assert(i < cast<StructType>(V->getType())->getNumElements() &&
476 "Invalid element #");
478 auto I = StructValueState.
insert(
485 if (
auto *
C = dyn_cast<Constant>(V)) {
486 Constant *Elt =
C->getAggregateElement(i);
504 while (!ToInvalidate.
empty()) {
510 if (!BBExecutable.count(Inst->
getParent()))
516 if (
auto *RetInst = dyn_cast<ReturnInst>(Inst)) {
517 Function *
F = RetInst->getParent()->getParent();
518 if (
auto It = TrackedRetVals.
find(
F); It != TrackedRetVals.
end()) {
521 }
else if (MRVFunctionsTracked.
count(
F)) {
522 auto *STy = cast<StructType>(
F->getReturnType());
523 for (
unsigned I = 0, E = STy->getNumElements();
I != E; ++
I)
527 }
else if (
auto *STy = dyn_cast<StructType>(Inst->
getType())) {
528 for (
unsigned I = 0, E = STy->getNumElements();
I != E; ++
I) {
529 if (
auto It = StructValueState.
find({Inst, I});
530 It != StructValueState.
end()) {
535 }
else if (
auto It = ValueState.
find(Inst); It != ValueState.
end()) {
543 for (
User *U : V->users())
544 if (
auto *UI = dyn_cast<Instruction>(U))
547 auto It = AdditionalUsers.
find(V);
548 if (It != AdditionalUsers.
end())
549 for (
User *U : It->second)
550 if (
auto *UI = dyn_cast<Instruction>(U))
568 if (BBExecutable.count(
I->getParent()))
573 void addAdditionalUser(
Value *V,
User *U) {
574 auto Iter = AdditionalUsers.
insert({V, {}});
575 Iter.first->second.insert(U);
579 void markUsersAsChanged(
Value *
I) {
584 if (isa<Function>(
I)) {
585 for (
User *U :
I->users()) {
586 if (
auto *CB = dyn_cast<CallBase>(U))
587 handleCallResult(*CB);
590 for (
User *U :
I->users())
591 if (
auto *UI = dyn_cast<Instruction>(U))
592 operandChangedState(UI);
595 auto Iter = AdditionalUsers.
find(
I);
596 if (Iter != AdditionalUsers.
end()) {
600 for (
User *U : Iter->second)
601 if (
auto *UI = dyn_cast<Instruction>(U))
604 operandChangedState(UI);
607 void handleCallOverdefined(
CallBase &CB);
608 void handleCallResult(
CallBase &CB);
609 void handleCallArguments(
CallBase &CB);
636 markOverdefined(&CPI);
637 visitTerminator(CPI);
653 visitTerminator(CBI);
668 FnPredicateInfo.
insert({&
F, std::make_unique<PredicateInfo>(
F, DT, AC)});
676 auto It = FnPredicateInfo.
find(
I->getParent()->getParent());
677 if (It == FnPredicateInfo.
end())
679 return It->second->getPredicateInfoFor(
I);
685 :
DL(
DL), GetTLI(GetTLI), Ctx(Ctx) {}
697 if (
auto *STy = dyn_cast<StructType>(
F->getReturnType())) {
699 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
700 TrackedMultipleRetVals.
insert(
702 }
else if (!
F->getReturnType()->isVoidTy())
707 MustPreserveReturnsInFunctions.
insert(
F);
711 return MustPreserveReturnsInFunctions.
count(
F);
715 TrackingIncomingArguments.
insert(
F);
719 return TrackingIncomingArguments.
count(
F);
729 return BBExecutable.count(BB);
735 std::vector<ValueLatticeElement> StructValues;
736 auto *STy = dyn_cast<StructType>(V->getType());
737 assert(STy &&
"getStructLatticeValueFor() can be called only on structs");
738 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
739 auto I = StructValueState.
find(std::make_pair(V, i));
740 assert(
I != StructValueState.
end() &&
"Value not in valuemap!");
741 StructValues.push_back(
I->second);
754 assert(!
F->getReturnType()->isVoidTy() &&
755 (TrackedRetVals.
count(
F) || MRVFunctionsTracked.
count(
F)) &&
756 "All non void specializations should be tracked");
758 handleCallResult(*Call);
762 assert(!V->getType()->isStructTy() &&
763 "Should use getStructLatticeValueFor");
767 "V not found in ValueState nor Paramstate map!");
772 return TrackedRetVals;
776 return TrackedGlobals;
780 return MRVFunctionsTracked;
784 if (
auto *STy = dyn_cast<StructType>(V->getType()))
785 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
786 markOverdefined(getStructValueState(V, i), V);
788 markOverdefined(ValueState[V], V);
798 return TrackingIncomingArguments;
806 BBExecutable.erase(&BB);
810 bool ResolvedUndefs =
true;
811 while (ResolvedUndefs) {
813 ResolvedUndefs =
false;
820 bool ResolvedUndefs =
true;
821 while (ResolvedUndefs) {
823 ResolvedUndefs =
false;
830 bool ResolvedUndefs =
true;
831 while (ResolvedUndefs) {
833 ResolvedUndefs =
false;
835 if (
auto *
I = dyn_cast<Instruction>(V))
845 if (!BBExecutable.insert(BB).second)
848 BBWorkList.push_back(BB);
853 if (
IV.isOverdefined()) {
854 if (OverdefinedInstWorkList.empty() || OverdefinedInstWorkList.back() != V)
855 OverdefinedInstWorkList.push_back(V);
858 if (InstWorkList.empty() || InstWorkList.back() != V)
859 InstWorkList.push_back(V);
864 pushToWorkList(
IV, V);
869 if (!
IV.markConstant(
C, MayIncludeUndef))
872 pushToWorkList(
IV, V);
877 if (!
IV.markOverdefined())
881 if (
auto *
F = dyn_cast<Function>(V))
dbgs()
882 <<
"Function '" <<
F->getName() <<
"'\n";
883 else dbgs() << *V <<
'\n');
885 pushToWorkList(
IV, V);
891 const auto &It = TrackedMultipleRetVals.find(std::make_pair(
F, i));
892 assert(It != TrackedMultipleRetVals.end());
904 assert(
C->getType() == Ty &&
"Type mismatch");
910 if (CR.getSingleElement())
911 return ConstantInt::get(Ty, *CR.getSingleElement());
918 if (V->getType()->isStructTy()) {
922 std::vector<Constant *> ConstVals;
923 auto *ST = cast<StructType>(V->getType());
924 for (
unsigned I = 0,
E = ST->getNumElements();
I !=
E; ++
I) {
938 assert(Const &&
"Constant is nullptr here!");
944 assert(!Args.empty() &&
"Specialization without arguments");
945 assert(
F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
946 "Functions should have the same number of arguments");
948 auto Iter = Args.begin();
951 for (
auto End =
F->arg_end(); NewArg !=
End; ++NewArg, ++OldArg) {
958 if (Iter != Args.end() && Iter->Formal == &*OldArg) {
959 if (
auto *STy = dyn_cast<StructType>(NewArg->
getType())) {
960 for (
unsigned I = 0,
E = STy->getNumElements();
I !=
E; ++
I) {
965 ValueState[&*NewArg].markConstant(Iter->Actual);
969 if (
auto *STy = dyn_cast<StructType>(NewArg->
getType())) {
970 for (
unsigned I = 0,
E = STy->getNumElements();
I !=
E; ++
I) {
972 NewValue = StructValueState[{&*OldArg,
I}];
976 NewValue = ValueState[&*OldArg];
992 if (
IV.mergeIn(MergeWithV, Opts)) {
993 pushToWorkList(
IV, V);
994 LLVM_DEBUG(
dbgs() <<
"Merged " << MergeWithV <<
" into " << *V <<
" : "
1002 if (!KnownFeasibleEdges.
insert(Edge(Source, Dest)).second)
1010 <<
" -> " << Dest->
getName() <<
'\n');
1020void SCCPInstVisitor::getFeasibleSuccessors(
Instruction &TI,
1023 if (
auto *BI = dyn_cast<BranchInst>(&TI)) {
1024 if (BI->isUnconditional()) {
1030 ConstantInt *CI = getConstantInt(BCValue, BI->getCondition()->getType());
1035 Succs[0] = Succs[1] =
true;
1040 Succs[CI->
isZero()] =
true;
1051 if (
auto *SI = dyn_cast<SwitchInst>(&TI)) {
1052 if (!
SI->getNumCases()) {
1058 getConstantInt(SCValue,
SI->getCondition()->getType())) {
1059 Succs[
SI->findCaseValue(CI)->getSuccessorIndex()] =
true;
1067 unsigned ReachableCaseCount = 0;
1068 for (
const auto &Case :
SI->cases()) {
1069 const APInt &CaseValue = Case.getCaseValue()->getValue();
1070 if (
Range.contains(CaseValue)) {
1071 Succs[Case.getSuccessorIndex()] =
true;
1072 ++ReachableCaseCount;
1076 Succs[
SI->case_default()->getSuccessorIndex()] =
1077 Range.isSizeLargerThan(ReachableCaseCount);
1089 if (
auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
1093 getConstant(IBRValue, IBR->getAddress()->getType()));
1103 "Block address of a different function ?");
1104 for (
unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
1106 if (IBR->getDestination(i) ==
T) {
1117 LLVM_DEBUG(
dbgs() <<
"Unknown terminator instruction: " << TI <<
'\n');
1127 return KnownFeasibleEdges.
count(Edge(
From, To));
1147void SCCPInstVisitor::visitPHINode(
PHINode &PN) {
1151 return (
void)markOverdefined(&PN);
1153 if (getValueState(&PN).isOverdefined())
1159 return (
void)markOverdefined(&PN);
1161 unsigned NumActiveIncoming = 0;
1175 NumActiveIncoming++;
1185 mergeInValue(&PN, PhiState,
1187 NumActiveIncoming + 1));
1193void SCCPInstVisitor::visitReturnInst(
ReturnInst &
I) {
1194 if (
I.getNumOperands() == 0)
1198 Value *ResultOp =
I.getOperand(0);
1202 auto TFRVI = TrackedRetVals.find(
F);
1203 if (TFRVI != TrackedRetVals.end()) {
1204 mergeInValue(TFRVI->second,
F, getValueState(ResultOp));
1210 if (!TrackedMultipleRetVals.empty()) {
1211 if (
auto *STy = dyn_cast<StructType>(ResultOp->
getType()))
1212 if (MRVFunctionsTracked.count(
F))
1213 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1214 mergeInValue(TrackedMultipleRetVals[std::make_pair(
F, i)],
F,
1215 getStructValueState(ResultOp, i));
1219void SCCPInstVisitor::visitTerminator(
Instruction &TI) {
1221 getFeasibleSuccessors(TI, SuccFeasible);
1226 for (
unsigned i = 0, e = SuccFeasible.
size(); i != e; ++i)
1227 if (SuccFeasible[i])
1231void SCCPInstVisitor::visitCastInst(
CastInst &
I) {
1234 if (ValueState[&
I].isOverdefined())
1245 return (
void)markConstant(&
I,
C);
1248 if (
I.getDestTy()->isIntegerTy() &&
I.getSrcTy()->isIntOrIntVectorTy()) {
1249 auto &LV = getValueState(&
I);
1252 Type *DestTy =
I.getDestTy();
1258 if (
I.getOpcode() == Instruction::BitCast &&
1259 I.getOperand(0)->getType()->isVectorTy() &&
1261 return (
void)markOverdefined(&
I);
1264 OpRange.
castOp(
I.getOpcode(),
DL.getTypeSizeInBits(DestTy));
1267 markOverdefined(&
I);
1276 addAdditionalUser(
LHS, &EVI);
1277 addAdditionalUser(
RHS, &EVI);
1278 if (
L.isUnknownOrUndef() ||
R.isUnknownOrUndef())
1288 assert(
Idx == 1 &&
"Index can only be 0 or 1");
1293 markOverdefined(&EVI);
1301 return (
void)markOverdefined(&EVI);
1305 if (ValueState[&EVI].isOverdefined())
1306 return (
void)markOverdefined(&EVI);
1310 return (
void)markOverdefined(&EVI);
1315 if (
auto *WO = dyn_cast<WithOverflowInst>(AggVal))
1316 return handleExtractOfWithOverflow(EVI, WO, i);
1318 mergeInValue(getValueState(&EVI), &EVI, EltVal);
1321 return (
void)markOverdefined(&EVI);
1326 auto *STy = dyn_cast<StructType>(IVI.
getType());
1328 return (
void)markOverdefined(&IVI);
1333 return (
void)markOverdefined(&IVI);
1337 if (IVI.getNumIndices() != 1)
1338 return (
void)markOverdefined(&IVI);
1340 Value *Aggr = IVI.getAggregateOperand();
1341 unsigned Idx = *IVI.idx_begin();
1344 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1348 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
1352 Value *Val = IVI.getInsertedValueOperand();
1355 markOverdefined(getStructValueState(&IVI, i), &IVI);
1358 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
1363void SCCPInstVisitor::visitSelectInst(
SelectInst &
I) {
1366 if (
I.getType()->isStructTy())
1367 return (
void)markOverdefined(&
I);
1371 if (ValueState[&
I].isOverdefined())
1372 return (
void)markOverdefined(&
I);
1379 getConstantInt(CondValue,
I.getCondition()->getType())) {
1380 Value *OpVal = CondCB->isZero() ?
I.getFalseValue() :
I.getTrueValue();
1381 mergeInValue(&
I, getValueState(OpVal));
1391 bool Changed = ValueState[&
I].mergeIn(TVal);
1392 Changed |= ValueState[&
I].mergeIn(FVal);
1394 pushToWorkListMsg(ValueState[&
I], &
I);
1398void SCCPInstVisitor::visitUnaryOperator(
Instruction &
I) {
1405 return (
void)markOverdefined(&
I);
1414 return (
void)markConstant(
IV, &
I,
C);
1416 markOverdefined(&
I);
1419void SCCPInstVisitor::visitFreezeInst(
FreezeInst &
I) {
1422 if (
I.getType()->isStructTy())
1423 return (
void)markOverdefined(&
I);
1430 return (
void)markOverdefined(&
I);
1440 markOverdefined(&
I);
1444void SCCPInstVisitor::visitBinaryOperator(
Instruction &
I) {
1449 if (
IV.isOverdefined())
1457 return (
void)markOverdefined(&
I);
1469 auto *
C = dyn_cast_or_null<Constant>(R);
1478 return (
void)mergeInValue(&
I, NewV);
1483 if (!
I.getType()->isIntegerTy())
1484 return markOverdefined(&
I);
1490 auto *BO = cast<BinaryOperator>(&
I);
1491 ConstantRange R = ConstantRange::getEmpty(
I.getType()->getScalarSizeInBits());
1492 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO))
1493 R =
A.overflowingBinaryOp(BO->getOpcode(),
B, OBO->getNoWrapKind());
1495 R =
A.binaryOp(BO->getOpcode(),
B);
1504void SCCPInstVisitor::visitCmpInst(
CmpInst &
I) {
1508 return (
void)markOverdefined(&
I);
1510 Value *Op1 =
I.getOperand(0);
1511 Value *Op2 =
I.getOperand(1);
1515 auto V1State = getValueState(Op1);
1516 auto V2State = getValueState(Op2);
1522 mergeInValue(&
I, CV);
1531 markOverdefined(&
I);
1538 return (
void)markOverdefined(&
I);
1543 for (
unsigned i = 0, e =
I.getNumOperands(); i != e; ++i) {
1549 return (
void)markOverdefined(&
I);
1556 return (
void)markOverdefined(&
I);
1560 markConstant(&
I,
C);
1563void SCCPInstVisitor::visitStoreInst(
StoreInst &SI) {
1565 if (
SI.getOperand(0)->getType()->isStructTy())
1568 if (TrackedGlobals.empty() || !isa<GlobalVariable>(
SI.getOperand(1)))
1572 auto I = TrackedGlobals.find(GV);
1573 if (
I == TrackedGlobals.end())
1577 mergeInValue(
I->second, GV, getValueState(
SI.getOperand(0)),
1579 if (
I->second.isOverdefined())
1580 TrackedGlobals.erase(
I);
1584 if (
MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1585 if (
I->getType()->isIntegerTy())
1588 if (
I->hasMetadata(LLVMContext::MD_nonnull))
1596void SCCPInstVisitor::visitLoadInst(
LoadInst &
I) {
1599 if (
I.getType()->isStructTy() ||
I.isVolatile())
1600 return (
void)markOverdefined(&
I);
1604 if (ValueState[&
I].isOverdefined())
1605 return (
void)markOverdefined(&
I);
1617 if (isa<ConstantPointerNull>(
Ptr)) {
1619 return (
void)markOverdefined(
IV, &
I);
1625 if (
auto *GV = dyn_cast<GlobalVariable>(
Ptr)) {
1626 if (!TrackedGlobals.empty()) {
1628 auto It = TrackedGlobals.find(GV);
1629 if (It != TrackedGlobals.end()) {
1638 return (
void)markConstant(
IV, &
I,
C);
1645void SCCPInstVisitor::visitCallBase(
CallBase &CB) {
1646 handleCallResult(CB);
1647 handleCallArguments(CB);
1650void SCCPInstVisitor::handleCallOverdefined(
CallBase &CB) {
1659 return (
void)markOverdefined(&CB);
1666 if (
A.get()->getType()->isStructTy())
1667 return markOverdefined(&CB);
1668 if (
A.get()->getType()->isMetadataTy())
1675 return (
void)markOverdefined(&CB);
1681 return (
void)markOverdefined(&CB);
1686 return (
void)markConstant(&CB,
C);
1693void SCCPInstVisitor::handleCallArguments(
CallBase &CB) {
1698 if (TrackingIncomingArguments.count(
F)) {
1707 if (AI->hasByValAttr() && !
F->onlyReadsMemory()) {
1708 markOverdefined(&*AI);
1712 if (
auto *STy = dyn_cast<StructType>(AI->getType())) {
1713 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1715 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
1724void SCCPInstVisitor::handleCallResult(
CallBase &CB) {
1727 if (
auto *II = dyn_cast<IntrinsicInst>(&CB)) {
1728 if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1729 if (ValueState[&CB].isOverdefined())
1735 assert(PI &&
"Missing predicate info for ssa.copy");
1737 const std::optional<PredicateConstraint> &Constraint =
1738 PI->getConstraint();
1740 mergeInValue(ValueState[&CB], &CB, CopyOfVal);
1745 Value *OtherOp = Constraint->OtherOp;
1748 if (getValueState(OtherOp).isUnknown()) {
1749 addAdditionalUser(OtherOp, &CB);
1757 ConstantRange::getFull(
DL.getTypeSizeInBits(CopyOf->
getType()));
1767 auto NewCR = ImposedCR.intersectWith(CopyOfCR);
1771 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
1779 addAdditionalUser(OtherOp, &CB);
1788 addAdditionalUser(OtherOp, &CB);
1789 mergeInValue(
IV, &CB, CondVal);
1793 addAdditionalUser(OtherOp, &CB);
1794 mergeInValue(
IV, &CB,
1799 return (
void)mergeInValue(
IV, &CB, CopyOfVal);
1807 for (
Value *
Op : II->args()) {
1823 if (!
F ||
F->isDeclaration())
1824 return handleCallOverdefined(CB);
1827 if (
auto *STy = dyn_cast<StructType>(
F->getReturnType())) {
1828 if (!MRVFunctionsTracked.count(
F))
1829 return handleCallOverdefined(CB);
1833 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1834 mergeInValue(getStructValueState(&CB, i), &CB,
1835 TrackedMultipleRetVals[std::make_pair(
F, i)],
1838 auto TFRVI = TrackedRetVals.find(
F);
1839 if (TFRVI == TrackedRetVals.end())
1840 return handleCallOverdefined(CB);
1849 while (!BBWorkList.empty() || !InstWorkList.empty() ||
1850 !OverdefinedInstWorkList.empty()) {
1853 while (!OverdefinedInstWorkList.empty()) {
1854 Value *
I = OverdefinedInstWorkList.pop_back_val();
1866 markUsersAsChanged(
I);
1870 while (!InstWorkList.empty()) {
1871 Value *
I = InstWorkList.pop_back_val();
1883 if (
I->getType()->isStructTy() || !getValueState(
I).isOverdefined())
1884 markUsersAsChanged(
I);
1888 while (!BBWorkList.empty()) {
1902 if (
I.getType()->isVoidTy())
1905 if (
auto *STy = dyn_cast<StructType>(
I.getType())) {
1909 if (
auto *CB = dyn_cast<CallBase>(&
I))
1911 if (MRVFunctionsTracked.count(
F))
1916 if (isa<ExtractValueInst>(
I) || isa<InsertValueInst>(
I))
1920 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1923 markOverdefined(LV, &
I);
1939 if (
auto *CB = dyn_cast<CallBase>(&
I))
1941 if (TrackedRetVals.count(
F))
1944 if (isa<LoadInst>(
I)) {
1951 markOverdefined(&
I);
1969 bool MadeChange =
false;
1971 if (!BBExecutable.count(&BB))
1979 <<
"\nResolved undefs in " <<
F.getName() <<
'\n');
1998 Visitor->addPredicateInfo(
F, DT, AC);
2002 return Visitor->markBlockExecutable(BB);
2006 return Visitor->getPredicateInfoFor(
I);
2010 Visitor->trackValueOfGlobalVariable(GV);
2014 Visitor->addTrackedFunction(
F);
2018 Visitor->addToMustPreserveReturnsInFunctions(
F);
2022 return Visitor->mustPreserveReturn(
F);
2026 Visitor->addArgumentTrackedFunction(
F);
2030 return Visitor->isArgumentTrackedFunction(
F);
2036 return Visitor->resolvedUndefsIn(
F);
2040 Visitor->solveWhileResolvedUndefsIn(M);
2045 Visitor->solveWhileResolvedUndefsIn(WorkList);
2049 Visitor->solveWhileResolvedUndefs();
2053 return Visitor->isBlockExecutable(BB);
2057 return Visitor->isEdgeFeasible(
From, To);
2060std::vector<ValueLatticeElement>
2062 return Visitor->getStructLatticeValueFor(V);
2066 return Visitor->removeLatticeValueFor(V);
2070 Visitor->resetLatticeValueFor(Call);
2074 return Visitor->getLatticeValueFor(V);
2079 return Visitor->getTrackedRetVals();
2084 return Visitor->getTrackedGlobals();
2088 return Visitor->getMRVFunctionsTracked();
2094 return Visitor->isStructLatticeConstant(
F, STy);
2099 return Visitor->getConstant(LV, Ty);
2103 return Visitor->getConstantOrNull(V);
2107 return Visitor->getArgumentTrackedFunctions();
2112 Visitor->setLatticeValueForSpecializationArguments(
F, Args);
2116 Visitor->markFunctionUnreachable(
F);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
mir Rename Register Operands
static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts()
Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
static const unsigned MaxNumRangeExtensions
static ValueLatticeElement getValueFromMetadata(const Instruction *I)
static ConstantRange getConstantRange(const ValueLatticeElement &LV, Type *Ty, bool UndefAllowed=true)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static const uint32_t IV[8]
Class for arbitrary precision integers.
This class represents an incoming formal argument to a Function.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVMContext & getContext() const
Get the context in which this basic block lives.
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...
void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
The address of a basic block.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const
Return an operand bundle by name, if present.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
User::op_iterator arg_begin()
Return the iterator pointing to the beginning of the argument list.
bool isMustTailCall() const
Tests if this call site must be tail call optimized.
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This is the shared class of boolean and integer constants.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static ConstantInt * getFalse(LLVMContext &Context)
static ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This class represents a range of values.
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
bool isSingleElement() const
Return true if this set contains exactly one member.
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
static Constant * get(StructType *T, ArrayRef< Constant * > V)
This is an important base class in LLVM.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
An instruction for ordering other memory operations.
This class represents a freeze function that returns random concrete value if an operand is either a ...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Type * getValueType() const
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
This instruction inserts a struct field of array element value into an aggregate value.
Base class for instruction visitors.
void visit(Iterator Start, Iterator End)
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
void setNonNeg(bool b=true)
Set or clear the nneg flag on this instruction, which must be a zext instruction.
bool hasNonNeg() const LLVM_READONLY
Determine whether the the nneg flag is set.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
bool isSpecialTerminator() const
This is an important class for using LLVM in a threaded context.
@ OB_clang_arc_attachedcall
An instruction for reading from memory.
This class implements a map that also provides access to all stored values in a deterministic order.
size_type count(const KeyT &Key) const
iterator find(const KeyT &Key)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
A Module instance is used to store all the information related to an LLVM module.
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Resume the propagation of an exception.
Return a value (possibly void), from a function.
Helper class for SCCPSolver.
const PredicateBase * getPredicateInfoFor(Instruction *I)
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
bool resolvedUndef(Instruction &I)
void markFunctionUnreachable(Function *F)
bool markBlockExecutable(BasicBlock *BB)
bool resolvedUndefsIn(Function &F)
While solving the dataflow for a function, we don't compute a result for operations with an undef ope...
Constant * getConstant(const ValueLatticeElement &LV, Type *Ty) const
SCCPInstVisitor(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
const ValueLatticeElement & getLatticeValueFor(Value *V) const
void removeLatticeValueFor(Value *V)
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
void visitCallInst(CallInst &I)
void markOverdefined(Value *V)
bool isArgumentTrackedFunction(Function *F)
void addTrackedFunction(Function *F)
void solveWhileResolvedUndefs()
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
void solveWhileResolvedUndefsIn(Module &M)
void trackValueOfGlobalVariable(GlobalVariable *GV)
Constant * getConstantOrNull(Value *V) const
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)
void addToMustPreserveReturnsInFunctions(Function *F)
void addArgumentTrackedFunction(Function *F)
bool isStructLatticeConstant(Function *F, StructType *STy)
void solveWhileResolvedUndefsIn(SmallVectorImpl< Function * > &WorkList)
bool isBlockExecutable(BasicBlock *BB) const
bool mustPreserveReturn(Function *F)
void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
void visitCall(CallInst &I)
const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals()
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
bool tryToReplaceWithConstant(Value *V)
bool isStructLatticeConstant(Function *F, StructType *STy)
void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)
void solve()
Solve - Solve for constants and executable blocks.
void visit(Instruction *I)
void addTrackedFunction(Function *F)
addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
getTrackedRetVals - Get the inferred return value map.
void solveWhileResolvedUndefsIn(Module &M)
const PredicateBase * getPredicateInfoFor(Instruction *I)
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
void addArgumentTrackedFunction(Function *F)
void solveWhileResolvedUndefs()
void removeLatticeValueFor(Value *V)
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.
Constant * getConstantOrNull(Value *V) const
Return either a Constant or nullptr for a given Value.
bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
Constant * getConstant(const ValueLatticeElement &LV, Type *Ty) const
Helper to return a Constant if LV is either a constant or a constant range with a single element.
const ValueLatticeElement & getLatticeValueFor(Value *V) const
void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB) const
bool isBlockExecutable(BasicBlock *BB) const
bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Set the Lattice Value for the arguments of a specialization F.
static bool isConstant(const ValueLatticeElement &LV)
bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
static bool isOverdefined(const ValueLatticeElement &LV)
void markFunctionUnreachable(Function *F)
Mark all of the blocks in function F non-executable.
bool isArgumentTrackedFunction(Function *F)
Returns true if the given function is in the solver's set of argument-tracked functions.
SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
Return a reference to the set of argument tracked functions.
void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
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 assign(size_type NumElts, ValueParamT Elt)
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.
Class to represent struct types.
unsigned getNumElements() const
Random access to the elements.
A wrapper class to simplify modification of SwitchInst cases along with their prof branch_weights met...
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
bool isSingleValueType() const
Return true if the type is a valid type for a register in codegen.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isStructTy() const
True if this is an instance of StructType.
bool isVoidTy() const
Return true if this is 'void'.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
This class represents lattice values for constants.
static ValueLatticeElement getRange(ConstantRange CR, bool MayIncludeUndef=false)
bool isOverdefined() const
Constant * getCompare(CmpInst::Predicate Pred, Type *Ty, const ValueLatticeElement &Other, const DataLayout &DL) const
true, false or undef constants, or nullptr if the comparison cannot be evaluated.
static ValueLatticeElement getNot(Constant *C)
bool isNotConstant() const
void setNumRangeExtensions(unsigned N)
const ConstantRange & getConstantRange(bool UndefAllowed=true) const
Returns the constant range for this value.
bool isConstantRange(bool UndefAllowed=true) const
Returns true if this value is a constant range.
unsigned getNumRangeExtensions() const
bool isUnknownOrUndef() const
Constant * getConstant() const
bool mergeIn(const ValueLatticeElement &RHS, MergeOptions Opts=MergeOptions())
Updates this object to approximate both this object and RHS.
bool markConstant(Constant *V, bool MayIncludeUndef=false)
static ValueLatticeElement getOverdefined()
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
std::string getNameOrAsOperand() const
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
This class represents zero extension of integer types.
std::pair< iterator, bool > insert(const ValueT &V)
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
static bool replaceSignedInst(SCCPSolver &Solver, SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)
Try to replace signed instructions with their unsigned equivalent.
bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
auto successors(const MachineBasicBlock *BB)
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant * > Operands, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
Constant * ConstantFoldInstOperands(Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool wouldInstructionBeTriviallyDead(const Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction would have no side effects if it was not used.
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
DWARFExpression::Operation Op
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
static bool canRemoveInstruction(Instruction *I)
Constant * ConstantFoldLoadFromConstPtr(Constant *C, Type *Ty, APInt Offset, const DataLayout &DL)
Return the value that a load from C with offset Offset would produce if it is constant and determinab...
static bool refineInstruction(SCCPSolver &Solver, const SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)
Try to use Inst's value range from Solver to infer the NUW flag.
Implement std::hash so that hash_code can be used in STL containers.
Struct to control some aspects related to merging constant ranges.
MergeOptions & setMaxWidenSteps(unsigned Steps=1)
MergeOptions & setCheckWiden(bool V=true)