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 if (!isa<OverflowingBinaryOperator>(Inst))
113 auto GetRange = [&Solver, &InsertedValues](
Value *
Op) {
114 if (
auto *Const = dyn_cast<ConstantInt>(
Op))
117 unsigned Bitwidth =
Op->getType()->getScalarSizeInBits();
118 return ConstantRange::getFull(Bitwidth);
125 bool Changed =
false;
130 if (NUWRange.contains(RangeA)) {
138 if (NSWRange.contains(RangeA)) {
152 auto isNonNegative = [&Solver](
Value *V) {
155 if (
auto *
C = dyn_cast<Constant>(V)) {
156 auto *CInt = dyn_cast<ConstantInt>(
C);
157 return CInt && !CInt->isNegative();
160 return IV.isConstantRange(
false) &&
161 IV.getConstantRange().isAllNonNegative();
168 case Instruction::SExt: {
171 if (InsertedValues.
count(Op0) || !isNonNegative(Op0))
176 case Instruction::AShr: {
179 if (InsertedValues.
count(Op0) || !isNonNegative(Op0))
181 NewInst = BinaryOperator::CreateLShr(Op0, Inst.
getOperand(1),
"", &Inst);
184 case Instruction::SDiv:
185 case Instruction::SRem: {
188 if (InsertedValues.
count(Op0) || InsertedValues.
count(Op1) ||
189 !isNonNegative(Op0) || !isNonNegative(Op1))
191 auto NewOpcode = Inst.
getOpcode() == Instruction::SDiv ? Instruction::UDiv
201 assert(NewInst &&
"Expected replacement instruction");
203 InsertedValues.
insert(NewInst);
214 bool MadeChanges =
false;
216 if (Inst.getType()->isVoidTy())
220 Inst.eraseFromParent();
237 bool HasNonFeasibleEdges =
false;
240 FeasibleSuccessors.
insert(Succ);
242 HasNonFeasibleEdges =
true;
246 if (!HasNonFeasibleEdges)
251 assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
252 isa<IndirectBrInst>(TI)) &&
253 "Terminator must be a br, switch or indirectbr");
255 if (FeasibleSuccessors.
size() == 0) {
260 Succ->removePredecessor(BB);
261 if (SeenSuccs.
insert(Succ).second)
267 }
else if (FeasibleSuccessors.
size() == 1) {
271 bool HaveSeenOnlyFeasibleSuccessor =
false;
273 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
276 HaveSeenOnlyFeasibleSuccessor =
true;
280 Succ->removePredecessor(BB);
287 }
else if (FeasibleSuccessors.
size() > 1) {
293 BasicBlock *DefaultDest = SI->getDefaultDest();
294 if (!FeasibleSuccessors.
contains(DefaultDest)) {
295 if (!NewUnreachableBB) {
302 SI->setDefaultDest(NewUnreachableBB);
307 for (
auto CI = SI->case_begin(); CI != SI->case_end();) {
308 if (FeasibleSuccessors.
contains(CI->getCaseSuccessor())) {
354 TrackedMultipleRetVals;
387 using Edge = std::pair<BasicBlock *, BasicBlock *>;
412 bool MayIncludeUndef =
false);
415 assert(!V->getType()->isStructTy() &&
"structs should use mergeInValue");
416 return markConstant(ValueState[V], V,
C);
434 assert(!V->getType()->isStructTy() &&
435 "non-structs should use markConstant");
436 return mergeInValue(ValueState[V], V, MergeWithV, Opts);
443 assert(!V->getType()->isStructTy() &&
"Should use getStructValueState");
451 if (
auto *
C = dyn_cast<Constant>(V))
462 assert(V->getType()->isStructTy() &&
"Should use getValueState");
463 assert(i < cast<StructType>(V->getType())->getNumElements() &&
464 "Invalid element #");
466 auto I = StructValueState.
insert(
473 if (
auto *
C = dyn_cast<Constant>(V)) {
474 Constant *Elt =
C->getAggregateElement(i);
492 while (!ToInvalidate.
empty()) {
498 if (!BBExecutable.count(Inst->
getParent()))
504 if (
auto *RetInst = dyn_cast<ReturnInst>(Inst)) {
505 Function *
F = RetInst->getParent()->getParent();
506 if (
auto It = TrackedRetVals.
find(
F); It != TrackedRetVals.
end()) {
509 }
else if (MRVFunctionsTracked.
count(
F)) {
510 auto *STy = cast<StructType>(
F->getReturnType());
511 for (
unsigned I = 0,
E = STy->getNumElements();
I !=
E; ++
I)
515 }
else if (
auto *STy = dyn_cast<StructType>(Inst->
getType())) {
516 for (
unsigned I = 0,
E = STy->getNumElements();
I !=
E; ++
I) {
517 if (
auto It = StructValueState.
find({Inst, I});
518 It != StructValueState.
end()) {
523 }
else if (
auto It = ValueState.
find(Inst); It != ValueState.
end()) {
531 for (
User *U : V->users())
532 if (
auto *UI = dyn_cast<Instruction>(U))
535 auto It = AdditionalUsers.
find(V);
536 if (It != AdditionalUsers.
end())
537 for (
User *U : It->second)
538 if (
auto *UI = dyn_cast<Instruction>(U))
556 if (BBExecutable.count(
I->getParent()))
561 void addAdditionalUser(
Value *V,
User *U) {
562 auto Iter = AdditionalUsers.
insert({V, {}});
563 Iter.first->second.insert(U);
567 void markUsersAsChanged(
Value *
I) {
572 if (isa<Function>(
I)) {
573 for (
User *U :
I->users()) {
574 if (
auto *CB = dyn_cast<CallBase>(U))
575 handleCallResult(*CB);
578 for (
User *U :
I->users())
579 if (
auto *UI = dyn_cast<Instruction>(U))
580 operandChangedState(UI);
583 auto Iter = AdditionalUsers.
find(
I);
584 if (Iter != AdditionalUsers.
end()) {
588 for (
User *U : Iter->second)
589 if (
auto *UI = dyn_cast<Instruction>(U))
592 operandChangedState(UI);
595 void handleCallOverdefined(
CallBase &CB);
596 void handleCallResult(
CallBase &CB);
597 void handleCallArguments(
CallBase &CB);
624 markOverdefined(&CPI);
625 visitTerminator(CPI);
641 visitTerminator(CBI);
656 FnPredicateInfo.
insert({&
F, std::make_unique<PredicateInfo>(
F, DT, AC)});
664 auto It = FnPredicateInfo.
find(
I->getParent()->getParent());
665 if (It == FnPredicateInfo.
end())
667 return It->second->getPredicateInfoFor(
I);
673 :
DL(
DL), GetTLI(GetTLI), Ctx(Ctx) {}
685 if (
auto *STy = dyn_cast<StructType>(
F->getReturnType())) {
687 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
688 TrackedMultipleRetVals.
insert(
690 }
else if (!
F->getReturnType()->isVoidTy())
695 MustPreserveReturnsInFunctions.
insert(
F);
699 return MustPreserveReturnsInFunctions.
count(
F);
703 TrackingIncomingArguments.
insert(
F);
707 return TrackingIncomingArguments.
count(
F);
717 return BBExecutable.count(BB);
723 std::vector<ValueLatticeElement> StructValues;
724 auto *STy = dyn_cast<StructType>(V->getType());
725 assert(STy &&
"getStructLatticeValueFor() can be called only on structs");
726 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
727 auto I = StructValueState.
find(std::make_pair(V, i));
728 assert(
I != StructValueState.
end() &&
"Value not in valuemap!");
729 StructValues.push_back(
I->second);
742 assert(!
F->getReturnType()->isVoidTy() &&
743 (TrackedRetVals.
count(
F) || MRVFunctionsTracked.
count(
F)) &&
744 "All non void specializations should be tracked");
746 handleCallResult(*Call);
750 assert(!V->getType()->isStructTy() &&
751 "Should use getStructLatticeValueFor");
755 "V not found in ValueState nor Paramstate map!");
760 return TrackedRetVals;
764 return TrackedGlobals;
768 return MRVFunctionsTracked;
772 if (
auto *STy = dyn_cast<StructType>(V->getType()))
773 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
774 markOverdefined(getStructValueState(V, i), V);
776 markOverdefined(ValueState[V], V);
786 return TrackingIncomingArguments;
794 BBExecutable.erase(&BB);
798 bool ResolvedUndefs =
true;
799 while (ResolvedUndefs) {
801 ResolvedUndefs =
false;
808 bool ResolvedUndefs =
true;
809 while (ResolvedUndefs) {
811 ResolvedUndefs =
false;
818 bool ResolvedUndefs =
true;
819 while (ResolvedUndefs) {
821 ResolvedUndefs =
false;
823 if (
auto *
I = dyn_cast<Instruction>(V))
833 if (!BBExecutable.insert(BB).second)
836 BBWorkList.push_back(BB);
841 if (
IV.isOverdefined()) {
842 if (OverdefinedInstWorkList.empty() || OverdefinedInstWorkList.back() != V)
843 OverdefinedInstWorkList.push_back(V);
846 if (InstWorkList.empty() || InstWorkList.back() != V)
847 InstWorkList.push_back(V);
852 pushToWorkList(
IV, V);
857 if (!
IV.markConstant(
C, MayIncludeUndef))
860 pushToWorkList(
IV, V);
865 if (!
IV.markOverdefined())
869 if (
auto *
F = dyn_cast<Function>(V))
dbgs()
870 <<
"Function '" <<
F->getName() <<
"'\n";
871 else dbgs() << *V <<
'\n');
873 pushToWorkList(
IV, V);
879 const auto &It = TrackedMultipleRetVals.find(std::make_pair(
F, i));
880 assert(It != TrackedMultipleRetVals.end());
892 assert(
C->getType() == Ty &&
"Type mismatch");
898 if (CR.getSingleElement())
906 if (V->getType()->isStructTy()) {
910 std::vector<Constant *> ConstVals;
911 auto *ST = cast<StructType>(V->getType());
912 for (
unsigned I = 0,
E = ST->getNumElements();
I !=
E; ++
I) {
926 assert(Const &&
"Constant is nullptr here!");
932 assert(!Args.empty() &&
"Specialization without arguments");
933 assert(
F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
934 "Functions should have the same number of arguments");
936 auto Iter = Args.begin();
939 for (
auto End =
F->arg_end(); NewArg !=
End; ++NewArg, ++OldArg) {
946 if (Iter != Args.end() && Iter->Formal == &*OldArg) {
947 if (
auto *STy = dyn_cast<StructType>(NewArg->
getType())) {
948 for (
unsigned I = 0,
E = STy->getNumElements();
I !=
E; ++
I) {
953 ValueState[&*NewArg].markConstant(Iter->Actual);
957 if (
auto *STy = dyn_cast<StructType>(NewArg->
getType())) {
958 for (
unsigned I = 0,
E = STy->getNumElements();
I !=
E; ++
I) {
960 NewValue = StructValueState[{&*OldArg,
I}];
964 NewValue = ValueState[&*OldArg];
980 if (
IV.mergeIn(MergeWithV, Opts)) {
981 pushToWorkList(
IV, V);
982 LLVM_DEBUG(
dbgs() <<
"Merged " << MergeWithV <<
" into " << *V <<
" : "
990 if (!KnownFeasibleEdges.
insert(Edge(Source, Dest)).second)
998 <<
" -> " << Dest->
getName() <<
'\n');
1008void SCCPInstVisitor::getFeasibleSuccessors(
Instruction &TI,
1011 if (
auto *BI = dyn_cast<BranchInst>(&TI)) {
1012 if (BI->isUnconditional()) {
1018 ConstantInt *CI = getConstantInt(BCValue, BI->getCondition()->getType());
1023 Succs[0] = Succs[1] =
true;
1028 Succs[CI->
isZero()] =
true;
1039 if (
auto *SI = dyn_cast<SwitchInst>(&TI)) {
1040 if (!
SI->getNumCases()) {
1046 getConstantInt(SCValue,
SI->getCondition()->getType())) {
1047 Succs[
SI->findCaseValue(CI)->getSuccessorIndex()] =
true;
1055 for (
const auto &Case :
SI->cases()) {
1056 const APInt &CaseValue = Case.getCaseValue()->getValue();
1057 if (
Range.contains(CaseValue))
1058 Succs[Case.getSuccessorIndex()] =
true;
1062 Succs[
SI->case_default()->getSuccessorIndex()] =
true;
1074 if (
auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
1078 getConstant(IBRValue, IBR->getAddress()->getType()));
1088 "Block address of a different function ?");
1089 for (
unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
1091 if (IBR->getDestination(i) ==
T) {
1102 LLVM_DEBUG(
dbgs() <<
"Unknown terminator instruction: " << TI <<
'\n');
1112 return KnownFeasibleEdges.
count(Edge(
From, To));
1132void SCCPInstVisitor::visitPHINode(
PHINode &PN) {
1136 return (
void)markOverdefined(&PN);
1138 if (getValueState(&PN).isOverdefined())
1144 return (
void)markOverdefined(&PN);
1146 unsigned NumActiveIncoming = 0;
1160 NumActiveIncoming++;
1170 mergeInValue(&PN, PhiState,
1172 NumActiveIncoming + 1));
1178void SCCPInstVisitor::visitReturnInst(
ReturnInst &
I) {
1179 if (
I.getNumOperands() == 0)
1183 Value *ResultOp =
I.getOperand(0);
1187 auto TFRVI = TrackedRetVals.find(
F);
1188 if (TFRVI != TrackedRetVals.end()) {
1189 mergeInValue(TFRVI->second,
F, getValueState(ResultOp));
1195 if (!TrackedMultipleRetVals.empty()) {
1196 if (
auto *STy = dyn_cast<StructType>(ResultOp->
getType()))
1197 if (MRVFunctionsTracked.count(
F))
1198 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1199 mergeInValue(TrackedMultipleRetVals[std::make_pair(
F, i)],
F,
1200 getStructValueState(ResultOp, i));
1204void SCCPInstVisitor::visitTerminator(
Instruction &TI) {
1206 getFeasibleSuccessors(TI, SuccFeasible);
1211 for (
unsigned i = 0, e = SuccFeasible.
size(); i != e; ++i)
1212 if (SuccFeasible[i])
1216void SCCPInstVisitor::visitCastInst(
CastInst &
I) {
1219 if (ValueState[&
I].isOverdefined())
1229 markConstant(&
I,
C);
1230 }
else if (
I.getDestTy()->isIntegerTy() &&
1231 I.getSrcTy()->isIntOrIntVectorTy()) {
1232 auto &LV = getValueState(&
I);
1235 Type *DestTy =
I.getDestTy();
1241 if (
I.getOpcode() == Instruction::BitCast &&
1242 I.getOperand(0)->getType()->isVectorTy() &&
1244 return (
void)markOverdefined(&
I);
1247 OpRange.
castOp(
I.getOpcode(),
DL.getTypeSizeInBits(DestTy));
1250 markOverdefined(&
I);
1259 addAdditionalUser(
LHS, &EVI);
1260 addAdditionalUser(
RHS, &EVI);
1261 if (
L.isUnknownOrUndef() ||
R.isUnknownOrUndef())
1271 assert(
Idx == 1 &&
"Index can only be 0 or 1");
1276 markOverdefined(&EVI);
1284 return (
void)markOverdefined(&EVI);
1288 if (ValueState[&EVI].isOverdefined())
1289 return (
void)markOverdefined(&EVI);
1293 return (
void)markOverdefined(&EVI);
1298 if (
auto *WO = dyn_cast<WithOverflowInst>(AggVal))
1299 return handleExtractOfWithOverflow(EVI, WO, i);
1301 mergeInValue(getValueState(&EVI), &EVI, EltVal);
1304 return (
void)markOverdefined(&EVI);
1309 auto *STy = dyn_cast<StructType>(IVI.
getType());
1311 return (
void)markOverdefined(&IVI);
1316 return (
void)markOverdefined(&IVI);
1320 if (IVI.getNumIndices() != 1)
1321 return (
void)markOverdefined(&IVI);
1323 Value *Aggr = IVI.getAggregateOperand();
1324 unsigned Idx = *IVI.idx_begin();
1327 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1331 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
1335 Value *Val = IVI.getInsertedValueOperand();
1338 markOverdefined(getStructValueState(&IVI, i), &IVI);
1341 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
1346void SCCPInstVisitor::visitSelectInst(
SelectInst &
I) {
1349 if (
I.getType()->isStructTy())
1350 return (
void)markOverdefined(&
I);
1354 if (ValueState[&
I].isOverdefined())
1355 return (
void)markOverdefined(&
I);
1362 getConstantInt(
CondValue,
I.getCondition()->getType())) {
1363 Value *OpVal = CondCB->isZero() ?
I.getFalseValue() :
I.getTrueValue();
1364 mergeInValue(&
I, getValueState(OpVal));
1374 bool Changed = ValueState[&
I].mergeIn(TVal);
1375 Changed |= ValueState[&
I].mergeIn(FVal);
1377 pushToWorkListMsg(ValueState[&
I], &
I);
1381void SCCPInstVisitor::visitUnaryOperator(
Instruction &
I) {
1388 return (
void)markOverdefined(&
I);
1397 return (
void)markConstant(
IV, &
I,
C);
1399 markOverdefined(&
I);
1402void SCCPInstVisitor::visitFreezeInst(
FreezeInst &
I) {
1405 if (
I.getType()->isStructTy())
1406 return (
void)markOverdefined(&
I);
1413 return (
void)markOverdefined(&
I);
1423 markOverdefined(&
I);
1427void SCCPInstVisitor::visitBinaryOperator(
Instruction &
I) {
1432 if (
IV.isOverdefined())
1440 return (
void)markOverdefined(&
I);
1452 auto *
C = dyn_cast_or_null<Constant>(R);
1461 return (
void)mergeInValue(&
I, NewV);
1466 if (!
I.getType()->isIntegerTy())
1467 return markOverdefined(&
I);
1481void SCCPInstVisitor::visitCmpInst(
CmpInst &
I) {
1485 return (
void)markOverdefined(&
I);
1487 Value *Op1 =
I.getOperand(0);
1488 Value *Op2 =
I.getOperand(1);
1492 auto V1State = getValueState(Op1);
1493 auto V2State = getValueState(Op2);
1499 mergeInValue(&
I, CV);
1508 markOverdefined(&
I);
1515 return (
void)markOverdefined(&
I);
1520 for (
unsigned i = 0, e =
I.getNumOperands(); i != e; ++i) {
1526 return (
void)markOverdefined(&
I);
1533 return (
void)markOverdefined(&
I);
1537 markConstant(&
I,
C);
1540void SCCPInstVisitor::visitStoreInst(
StoreInst &SI) {
1542 if (
SI.getOperand(0)->getType()->isStructTy())
1545 if (TrackedGlobals.empty() || !isa<GlobalVariable>(
SI.getOperand(1)))
1549 auto I = TrackedGlobals.find(GV);
1550 if (
I == TrackedGlobals.end())
1554 mergeInValue(
I->second, GV, getValueState(
SI.getOperand(0)),
1556 if (
I->second.isOverdefined())
1557 TrackedGlobals.erase(
I);
1561 if (
MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1562 if (
I->getType()->isIntegerTy())
1565 if (
I->hasMetadata(LLVMContext::MD_nonnull))
1573void SCCPInstVisitor::visitLoadInst(
LoadInst &
I) {
1576 if (
I.getType()->isStructTy() ||
I.isVolatile())
1577 return (
void)markOverdefined(&
I);
1581 if (ValueState[&
I].isOverdefined())
1582 return (
void)markOverdefined(&
I);
1594 if (isa<ConstantPointerNull>(
Ptr)) {
1596 return (
void)markOverdefined(
IV, &
I);
1602 if (
auto *GV = dyn_cast<GlobalVariable>(
Ptr)) {
1603 if (!TrackedGlobals.empty()) {
1605 auto It = TrackedGlobals.find(GV);
1606 if (It != TrackedGlobals.end()) {
1615 return (
void)markConstant(
IV, &
I,
C);
1622void SCCPInstVisitor::visitCallBase(
CallBase &CB) {
1623 handleCallResult(CB);
1624 handleCallArguments(CB);
1627void SCCPInstVisitor::handleCallOverdefined(
CallBase &CB) {
1636 return (
void)markOverdefined(&CB);
1643 if (
A.get()->getType()->isStructTy())
1644 return markOverdefined(&CB);
1645 if (
A.get()->getType()->isMetadataTy())
1652 return (
void)markOverdefined(&CB);
1658 return (
void)markOverdefined(&CB);
1663 return (
void)markConstant(&CB,
C);
1670void SCCPInstVisitor::handleCallArguments(
CallBase &CB) {
1675 if (TrackingIncomingArguments.count(
F)) {
1684 if (AI->hasByValAttr() && !
F->onlyReadsMemory()) {
1685 markOverdefined(&*AI);
1689 if (
auto *STy = dyn_cast<StructType>(AI->getType())) {
1690 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1692 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
1701void SCCPInstVisitor::handleCallResult(
CallBase &CB) {
1704 if (
auto *II = dyn_cast<IntrinsicInst>(&CB)) {
1705 if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1706 if (ValueState[&CB].isOverdefined())
1712 assert(PI &&
"Missing predicate info for ssa.copy");
1714 const std::optional<PredicateConstraint> &Constraint =
1715 PI->getConstraint();
1717 mergeInValue(ValueState[&CB], &CB, CopyOfVal);
1722 Value *OtherOp = Constraint->OtherOp;
1725 if (getValueState(OtherOp).isUnknown()) {
1726 addAdditionalUser(OtherOp, &CB);
1734 ConstantRange::getFull(
DL.getTypeSizeInBits(CopyOf->
getType()));
1744 auto NewCR = ImposedCR.intersectWith(CopyOfCR);
1748 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
1756 addAdditionalUser(OtherOp, &CB);
1765 addAdditionalUser(OtherOp, &CB);
1766 mergeInValue(
IV, &CB, CondVal);
1770 addAdditionalUser(OtherOp, &CB);
1771 mergeInValue(
IV, &CB,
1776 return (
void)mergeInValue(
IV, &CB, CopyOfVal);
1784 for (
Value *
Op : II->args()) {
1800 if (!
F ||
F->isDeclaration())
1801 return handleCallOverdefined(CB);
1804 if (
auto *STy = dyn_cast<StructType>(
F->getReturnType())) {
1805 if (!MRVFunctionsTracked.count(
F))
1806 return handleCallOverdefined(CB);
1810 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1811 mergeInValue(getStructValueState(&CB, i), &CB,
1812 TrackedMultipleRetVals[std::make_pair(
F, i)],
1815 auto TFRVI = TrackedRetVals.find(
F);
1816 if (TFRVI == TrackedRetVals.end())
1817 return handleCallOverdefined(CB);
1826 while (!BBWorkList.empty() || !InstWorkList.empty() ||
1827 !OverdefinedInstWorkList.empty()) {
1830 while (!OverdefinedInstWorkList.empty()) {
1831 Value *
I = OverdefinedInstWorkList.pop_back_val();
1843 markUsersAsChanged(
I);
1847 while (!InstWorkList.empty()) {
1848 Value *
I = InstWorkList.pop_back_val();
1860 if (
I->getType()->isStructTy() || !getValueState(
I).isOverdefined())
1861 markUsersAsChanged(
I);
1865 while (!BBWorkList.empty()) {
1879 if (
I.getType()->isVoidTy())
1882 if (
auto *STy = dyn_cast<StructType>(
I.getType())) {
1886 if (
auto *CB = dyn_cast<CallBase>(&
I))
1888 if (MRVFunctionsTracked.count(
F))
1893 if (isa<ExtractValueInst>(
I) || isa<InsertValueInst>(
I))
1897 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1900 markOverdefined(LV, &
I);
1916 if (
auto *CB = dyn_cast<CallBase>(&
I))
1918 if (TrackedRetVals.count(
F))
1921 if (isa<LoadInst>(
I)) {
1928 markOverdefined(&
I);
1946 bool MadeChange =
false;
1948 if (!BBExecutable.count(&BB))
1956 <<
"\nResolved undefs in " <<
F.getName() <<
'\n');
1975 Visitor->addPredicateInfo(
F, DT, AC);
1979 return Visitor->markBlockExecutable(BB);
1983 return Visitor->getPredicateInfoFor(
I);
1987 Visitor->trackValueOfGlobalVariable(GV);
1991 Visitor->addTrackedFunction(
F);
1995 Visitor->addToMustPreserveReturnsInFunctions(
F);
1999 return Visitor->mustPreserveReturn(
F);
2003 Visitor->addArgumentTrackedFunction(
F);
2007 return Visitor->isArgumentTrackedFunction(
F);
2013 return Visitor->resolvedUndefsIn(
F);
2017 Visitor->solveWhileResolvedUndefsIn(M);
2022 Visitor->solveWhileResolvedUndefsIn(WorkList);
2026 Visitor->solveWhileResolvedUndefs();
2030 return Visitor->isBlockExecutable(BB);
2034 return Visitor->isEdgeFeasible(
From, To);
2037std::vector<ValueLatticeElement>
2039 return Visitor->getStructLatticeValueFor(V);
2043 return Visitor->removeLatticeValueFor(V);
2047 Visitor->resetLatticeValueFor(Call);
2051 return Visitor->getLatticeValueFor(V);
2056 return Visitor->getTrackedRetVals();
2061 return Visitor->getTrackedGlobals();
2065 return Visitor->getMRVFunctionsTracked();
2071 return Visitor->isStructLatticeConstant(
F, STy);
2076 return Visitor->getConstant(LV, Ty);
2080 return Visitor->getConstantOrNull(V);
2084 return Visitor->getArgumentTrackedFunctions();
2089 Visitor->setLatticeValueForSpecializationArguments(
F, Args);
2093 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 std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
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=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
The address of a basic block.
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
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 Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
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
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
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.
#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)