32#define DEBUG_TYPE "sccp"
45 bool UndefAllowed =
true) {
72 return isa<LoadInst>(
I);
77 if (V->getType()->isStructTy()) {
81 std::vector<Constant *> ConstVals;
82 auto *ST = cast<StructType>(V->getType());
83 for (
unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
98 assert(Const &&
"Constant is nullptr here!");
104 CallBase *CB = dyn_cast<CallBase>(V);
115 <<
" as a constant\n");
119 LLVM_DEBUG(
dbgs() <<
" Constant: " << *Const <<
" = " << *V <<
'\n');
122 V->replaceAllUsesWith(Const);
130 if (!isa<OverflowingBinaryOperator>(Inst))
133 auto GetRange = [&Solver, &InsertedValues](
Value *Op) {
134 if (
auto *Const = dyn_cast<ConstantInt>(Op))
136 if (isa<Constant>(Op) || InsertedValues.
contains(Op)) {
137 unsigned Bitwidth = Op->getType()->getScalarSizeInBits();
138 return ConstantRange::getFull(Bitwidth);
145 bool Changed =
false;
150 if (NUWRange.contains(RangeA)) {
158 if (NSWRange.contains(RangeA)) {
172 auto isNonNegative = [&Solver](
Value *V) {
175 if (
auto *
C = dyn_cast<Constant>(V)) {
176 auto *CInt = dyn_cast<ConstantInt>(
C);
177 return CInt && !CInt->isNegative();
180 return IV.isConstantRange(
false) &&
181 IV.getConstantRange().isAllNonNegative();
188 case Instruction::SExt: {
191 if (InsertedValues.
count(Op0) || !isNonNegative(Op0))
196 case Instruction::AShr: {
199 if (InsertedValues.
count(Op0) || !isNonNegative(Op0))
201 NewInst = BinaryOperator::CreateLShr(Op0, Inst.
getOperand(1),
"", &Inst);
204 case Instruction::SDiv:
205 case Instruction::SRem: {
208 if (InsertedValues.
count(Op0) || InsertedValues.
count(Op1) ||
209 !isNonNegative(Op0) || !isNonNegative(Op1))
211 auto NewOpcode = Inst.
getOpcode() == Instruction::SDiv ? Instruction::UDiv
221 assert(NewInst &&
"Expected replacement instruction");
223 InsertedValues.
insert(NewInst);
234 bool MadeChanges =
false;
236 if (Inst.getType()->isVoidTy())
240 Inst.eraseFromParent();
257 bool HasNonFeasibleEdges =
false;
260 FeasibleSuccessors.
insert(Succ);
262 HasNonFeasibleEdges =
true;
266 if (!HasNonFeasibleEdges)
271 assert((isa<BranchInst>(TI) || isa<SwitchInst>(TI) ||
272 isa<IndirectBrInst>(TI)) &&
273 "Terminator must be a br, switch or indirectbr");
275 if (FeasibleSuccessors.
size() == 0) {
280 Succ->removePredecessor(BB);
281 if (SeenSuccs.
insert(Succ).second)
287 }
else if (FeasibleSuccessors.
size() == 1) {
291 bool HaveSeenOnlyFeasibleSuccessor =
false;
293 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
296 HaveSeenOnlyFeasibleSuccessor =
true;
300 Succ->removePredecessor(BB);
307 }
else if (FeasibleSuccessors.
size() > 1) {
314 if (!FeasibleSuccessors.
contains(DefaultDest)) {
315 if (!NewUnreachableBB) {
322 SI->setDefaultDest(NewUnreachableBB);
327 for (
auto CI =
SI->case_begin(); CI !=
SI->case_end();) {
328 if (FeasibleSuccessors.
contains(CI->getCaseSuccessor())) {
374 TrackedMultipleRetVals;
403 using Edge = std::pair<BasicBlock *, BasicBlock *>;
427 bool MayIncludeUndef =
false);
430 assert(!V->getType()->isStructTy() &&
"structs should use mergeInValue");
431 return markConstant(ValueState[V], V,
C);
449 assert(!V->getType()->isStructTy() &&
450 "non-structs should use markConstant");
451 return mergeInValue(ValueState[V], V, MergeWithV, Opts);
458 assert(!V->getType()->isStructTy() &&
"Should use getStructValueState");
466 if (
auto *
C = dyn_cast<Constant>(V))
477 assert(V->getType()->isStructTy() &&
"Should use getValueState");
478 assert(i < cast<StructType>(V->getType())->getNumElements() &&
479 "Invalid element #");
481 auto I = StructValueState.
insert(
488 if (
auto *
C = dyn_cast<Constant>(V)) {
489 Constant *Elt =
C->getAggregateElement(i);
513 if (BBExecutable.count(
I->getParent()))
518 void addAdditionalUser(
Value *V,
User *U) {
519 auto Iter = AdditionalUsers.
insert({V, {}});
520 Iter.first->second.insert(U);
524 void markUsersAsChanged(
Value *
I) {
529 if (isa<Function>(
I)) {
530 for (
User *U :
I->users()) {
531 if (
auto *CB = dyn_cast<CallBase>(U))
532 handleCallResult(*CB);
535 for (
User *U :
I->users())
536 if (
auto *UI = dyn_cast<Instruction>(U))
537 operandChangedState(UI);
540 auto Iter = AdditionalUsers.
find(
I);
541 if (Iter != AdditionalUsers.
end()) {
545 for (
User *U : Iter->second)
546 if (
auto *UI = dyn_cast<Instruction>(U))
549 operandChangedState(UI);
552 void handleCallOverdefined(
CallBase &CB);
553 void handleCallResult(
CallBase &CB);
554 void handleCallArguments(
CallBase &CB);
580 markOverdefined(&CPI);
581 visitTerminator(CPI);
597 visitTerminator(CBI);
612 AnalysisResults.
insert({&
F, std::move(
A)});
620 auto A = AnalysisResults.
find(
I->getParent()->getParent());
621 if (
A == AnalysisResults.
end())
623 return A->second.PredInfo->getPredicateInfoFor(
I);
627 auto A = AnalysisResults.
find(&
F);
628 assert(
A != AnalysisResults.
end() &&
A->second.LI &&
629 "Need LoopInfo analysis results for function.");
630 return *
A->second.LI;
634 auto A = AnalysisResults.
find(&
F);
635 assert(
A != AnalysisResults.
end() &&
"Need analysis results for function.");
642 :
DL(
DL), GetTLI(GetTLI), Ctx(Ctx) {}
654 if (
auto *STy = dyn_cast<StructType>(
F->getReturnType())) {
656 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
657 TrackedMultipleRetVals.
insert(
659 }
else if (!
F->getReturnType()->isVoidTy())
664 MustPreserveReturnsInFunctions.
insert(
F);
668 return MustPreserveReturnsInFunctions.
count(
F);
672 TrackingIncomingArguments.
insert(
F);
676 return TrackingIncomingArguments.
count(
F);
684 return BBExecutable.count(BB);
690 std::vector<ValueLatticeElement> StructValues;
691 auto *STy = dyn_cast<StructType>(V->getType());
692 assert(STy &&
"getStructLatticeValueFor() can be called only on structs");
693 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
694 auto I = StructValueState.
find(std::make_pair(V, i));
695 assert(
I != StructValueState.
end() &&
"Value not in valuemap!");
696 StructValues.push_back(
I->second);
704 assert(!V->getType()->isStructTy() &&
705 "Should use getStructLatticeValueFor");
709 "V not found in ValueState nor Paramstate map!");
714 return TrackedRetVals;
718 return TrackedGlobals;
722 return MRVFunctionsTracked;
726 if (
auto *STy = dyn_cast<StructType>(V->getType()))
727 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
728 markOverdefined(getStructValueState(V, i), V);
730 markOverdefined(ValueState[V], V);
738 return TrackingIncomingArguments;
746 BBExecutable.erase(&BB);
750 bool ResolvedUndefs =
true;
751 while (ResolvedUndefs) {
753 ResolvedUndefs =
false;
760 bool ResolvedUndefs =
true;
761 while (ResolvedUndefs) {
763 ResolvedUndefs =
false;
773 if (!BBExecutable.insert(BB).second)
776 BBWorkList.push_back(BB);
781 if (
IV.isOverdefined())
782 return OverdefinedInstWorkList.push_back(V);
783 InstWorkList.push_back(V);
788 pushToWorkList(
IV, V);
793 if (!
IV.markConstant(
C, MayIncludeUndef))
796 pushToWorkList(
IV, V);
801 if (!
IV.markOverdefined())
805 if (
auto *
F = dyn_cast<Function>(V))
dbgs()
806 <<
"Function '" <<
F->getName() <<
"'\n";
807 else dbgs() << *V <<
'\n');
809 pushToWorkList(
IV, V);
815 const auto &It = TrackedMultipleRetVals.find(std::make_pair(
F, i));
816 assert(It != TrackedMultipleRetVals.end());
830 if (CR.getSingleElement())
838 assert(!Args.empty() &&
"Specialization without arguments");
839 assert(
F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
840 "Functions should have the same number of arguments");
842 auto Iter = Args.begin();
844 Argument *OldArg = Args[0].Formal->getParent()->arg_begin();
845 for (
auto End =
F->arg_end(); NewArg != End; ++NewArg, ++OldArg) {
850 if (Iter != Args.end() && OldArg == Iter->Formal) {
852 markConstant(NewArg, Iter->Actual);
854 }
else if (ValueState.count(OldArg)) {
863 auto &NewValue = ValueState[NewArg];
864 NewValue = ValueState[OldArg];
865 pushToWorkList(NewValue, NewArg);
880 if (
IV.mergeIn(MergeWithV, Opts)) {
881 pushToWorkList(
IV, V);
882 LLVM_DEBUG(
dbgs() <<
"Merged " << MergeWithV <<
" into " << *V <<
" : "
890 if (!KnownFeasibleEdges.
insert(Edge(Source, Dest)).second)
898 <<
" -> " << Dest->
getName() <<
'\n');
908void SCCPInstVisitor::getFeasibleSuccessors(
Instruction &TI,
911 if (
auto *BI = dyn_cast<BranchInst>(&TI)) {
912 if (BI->isUnconditional()) {
923 Succs[0] = Succs[1] =
true;
928 Succs[CI->
isZero()] =
true;
938 if (
auto *SI = dyn_cast<SwitchInst>(&TI)) {
939 if (!
SI->getNumCases()) {
945 Succs[
SI->findCaseValue(CI)->getSuccessorIndex()] =
true;
953 for (
const auto &Case :
SI->cases()) {
954 const APInt &CaseValue = Case.getCaseValue()->getValue();
955 if (
Range.contains(CaseValue))
956 Succs[Case.getSuccessorIndex()] =
true;
960 Succs[
SI->case_default()->getSuccessorIndex()] =
true;
972 if (
auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
985 "Block address of a different function ?");
986 for (
unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
988 if (IBR->getDestination(i) ==
T) {
1001 if (isa<CallBrInst>(&TI)) {
1006 LLVM_DEBUG(
dbgs() <<
"Unknown terminator instruction: " << TI <<
'\n');
1016 return KnownFeasibleEdges.
count(Edge(
From, To));
1036void SCCPInstVisitor::visitPHINode(
PHINode &PN) {
1040 return (
void)markOverdefined(&PN);
1042 if (getValueState(&PN).isOverdefined())
1048 return (
void)markOverdefined(&PN);
1050 unsigned NumActiveIncoming = 0;
1064 NumActiveIncoming++;
1074 mergeInValue(&PN, PhiState,
1076 NumActiveIncoming + 1));
1082void SCCPInstVisitor::visitReturnInst(
ReturnInst &
I) {
1083 if (
I.getNumOperands() == 0)
1087 Value *ResultOp =
I.getOperand(0);
1091 auto TFRVI = TrackedRetVals.find(
F);
1092 if (TFRVI != TrackedRetVals.end()) {
1093 mergeInValue(TFRVI->second,
F, getValueState(ResultOp));
1099 if (!TrackedMultipleRetVals.empty()) {
1100 if (
auto *STy = dyn_cast<StructType>(ResultOp->
getType()))
1101 if (MRVFunctionsTracked.count(
F))
1102 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1103 mergeInValue(TrackedMultipleRetVals[std::make_pair(
F, i)],
F,
1104 getStructValueState(ResultOp, i));
1108void SCCPInstVisitor::visitTerminator(
Instruction &TI) {
1110 getFeasibleSuccessors(TI, SuccFeasible);
1115 for (
unsigned i = 0, e = SuccFeasible.
size(); i != e; ++i)
1116 if (SuccFeasible[i])
1120void SCCPInstVisitor::visitCastInst(
CastInst &
I) {
1123 if (ValueState[&
I].isOverdefined())
1133 markConstant(&
I,
C);
1134 }
else if (
I.getDestTy()->isIntegerTy() &&
1135 I.getSrcTy()->isIntOrIntVectorTy()) {
1136 auto &LV = getValueState(&
I);
1139 Type *DestTy =
I.getDestTy();
1145 if (
I.getOpcode() == Instruction::BitCast &&
1146 I.getOperand(0)->getType()->isVectorTy() &&
1148 return (
void)markOverdefined(&
I);
1151 OpRange.
castOp(
I.getOpcode(),
DL.getTypeSizeInBits(DestTy));
1154 markOverdefined(&
I);
1163 addAdditionalUser(
LHS, &EVI);
1164 addAdditionalUser(
RHS, &EVI);
1165 if (
L.isUnknownOrUndef() ||
R.isUnknownOrUndef())
1175 assert(
Idx == 1 &&
"Index can only be 0 or 1");
1180 markOverdefined(&EVI);
1188 return (
void)markOverdefined(&EVI);
1192 if (ValueState[&EVI].isOverdefined())
1193 return (
void)markOverdefined(&EVI);
1197 return (
void)markOverdefined(&EVI);
1202 if (
auto *WO = dyn_cast<WithOverflowInst>(AggVal))
1203 return handleExtractOfWithOverflow(EVI, WO, i);
1205 mergeInValue(getValueState(&EVI), &EVI, EltVal);
1208 return (
void)markOverdefined(&EVI);
1213 auto *STy = dyn_cast<StructType>(IVI.
getType());
1215 return (
void)markOverdefined(&IVI);
1220 return (
void)markOverdefined(&IVI);
1224 if (IVI.getNumIndices() != 1)
1225 return (
void)markOverdefined(&IVI);
1227 Value *Aggr = IVI.getAggregateOperand();
1228 unsigned Idx = *IVI.idx_begin();
1231 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1235 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
1239 Value *Val = IVI.getInsertedValueOperand();
1242 markOverdefined(getStructValueState(&IVI, i), &IVI);
1245 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
1250void SCCPInstVisitor::visitSelectInst(
SelectInst &
I) {
1253 if (
I.getType()->isStructTy())
1254 return (
void)markOverdefined(&
I);
1258 if (ValueState[&
I].isOverdefined())
1259 return (
void)markOverdefined(&
I);
1266 Value *OpVal = CondCB->isZero() ?
I.getFalseValue() :
I.getTrueValue();
1267 mergeInValue(&
I, getValueState(OpVal));
1277 bool Changed = ValueState[&
I].mergeIn(TVal);
1278 Changed |= ValueState[&
I].mergeIn(FVal);
1280 pushToWorkListMsg(ValueState[&
I], &
I);
1284void SCCPInstVisitor::visitUnaryOperator(
Instruction &
I) {
1291 return (
void)markOverdefined(&
I);
1300 return (
void)markConstant(
IV, &
I,
C);
1302 markOverdefined(&
I);
1306void SCCPInstVisitor::visitBinaryOperator(
Instruction &
I) {
1311 if (
IV.isOverdefined())
1319 return (
void)markOverdefined(&
I);
1329 auto *
C = dyn_cast_or_null<Constant>(R);
1338 return (
void)mergeInValue(&
I, NewV);
1343 if (!
I.getType()->isIntegerTy())
1344 return markOverdefined(&
I);
1358void SCCPInstVisitor::visitCmpInst(
CmpInst &
I) {
1362 return (
void)markOverdefined(&
I);
1364 Value *Op1 =
I.getOperand(0);
1365 Value *Op2 =
I.getOperand(1);
1369 auto V1State = getValueState(Op1);
1370 auto V2State = getValueState(Op2);
1376 mergeInValue(&
I, CV);
1385 markOverdefined(&
I);
1392 return (
void)markOverdefined(&
I);
1397 for (
unsigned i = 0, e =
I.getNumOperands(); i != e; ++i) {
1403 return (
void)markOverdefined(&
I);
1410 return (
void)markOverdefined(&
I);
1417 markConstant(&
I,
C);
1420void SCCPInstVisitor::visitStoreInst(
StoreInst &SI) {
1422 if (
SI.getOperand(0)->getType()->isStructTy())
1425 if (TrackedGlobals.empty() || !isa<GlobalVariable>(
SI.getOperand(1)))
1429 auto I = TrackedGlobals.find(GV);
1430 if (
I == TrackedGlobals.end())
1434 mergeInValue(
I->second, GV, getValueState(
SI.getOperand(0)),
1436 if (
I->second.isOverdefined())
1437 TrackedGlobals.erase(
I);
1441 if (
MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1442 if (
I->getType()->isIntegerTy())
1445 if (
I->hasMetadata(LLVMContext::MD_nonnull))
1453void SCCPInstVisitor::visitLoadInst(
LoadInst &
I) {
1456 if (
I.getType()->isStructTy() ||
I.isVolatile())
1457 return (
void)markOverdefined(&
I);
1461 if (ValueState[&
I].isOverdefined())
1462 return (
void)markOverdefined(&
I);
1474 if (isa<ConstantPointerNull>(
Ptr)) {
1476 return (
void)markOverdefined(
IV, &
I);
1482 if (
auto *GV = dyn_cast<GlobalVariable>(
Ptr)) {
1483 if (!TrackedGlobals.empty()) {
1485 auto It = TrackedGlobals.find(GV);
1486 if (It != TrackedGlobals.end()) {
1495 return (
void)markConstant(
IV, &
I,
C);
1502void SCCPInstVisitor::visitCallBase(
CallBase &CB) {
1503 handleCallResult(CB);
1504 handleCallArguments(CB);
1507void SCCPInstVisitor::handleCallOverdefined(
CallBase &CB) {
1516 return (
void)markOverdefined(&CB);
1523 if (
A.get()->getType()->isStructTy())
1524 return markOverdefined(&CB);
1525 if (
A.get()->getType()->isMetadataTy())
1532 return (
void)markOverdefined(&CB);
1538 return (
void)markOverdefined(&CB);
1543 return (
void)markConstant(&CB,
C);
1550void SCCPInstVisitor::handleCallArguments(
CallBase &CB) {
1555 if (TrackingIncomingArguments.count(
F)) {
1564 if (AI->hasByValAttr() && !
F->onlyReadsMemory()) {
1565 markOverdefined(&*AI);
1569 if (
auto *STy = dyn_cast<StructType>(AI->getType())) {
1570 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1572 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
1581void SCCPInstVisitor::handleCallResult(
CallBase &CB) {
1584 if (
auto *II = dyn_cast<IntrinsicInst>(&CB)) {
1585 if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
1586 if (ValueState[&CB].isOverdefined())
1592 assert(PI &&
"Missing predicate info for ssa.copy");
1594 const std::optional<PredicateConstraint> &Constraint =
1595 PI->getConstraint();
1597 mergeInValue(ValueState[&CB], &CB, CopyOfVal);
1602 Value *OtherOp = Constraint->OtherOp;
1605 if (getValueState(OtherOp).isUnknown()) {
1606 addAdditionalUser(OtherOp, &CB);
1614 ConstantRange::getFull(
DL.getTypeSizeInBits(CopyOf->
getType()));
1624 auto NewCR = ImposedCR.intersectWith(CopyOfCR);
1628 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
1636 addAdditionalUser(OtherOp, &CB);
1645 addAdditionalUser(OtherOp, &CB);
1646 mergeInValue(
IV, &CB, CondVal);
1650 addAdditionalUser(OtherOp, &CB);
1651 mergeInValue(
IV, &CB,
1656 return (
void)mergeInValue(
IV, &CB, CopyOfVal);
1664 for (
Value *Op : II->args()) {
1678 if (!
F ||
F->isDeclaration())
1679 return handleCallOverdefined(CB);
1682 if (
auto *STy = dyn_cast<StructType>(
F->getReturnType())) {
1683 if (!MRVFunctionsTracked.count(
F))
1684 return handleCallOverdefined(CB);
1688 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1689 mergeInValue(getStructValueState(&CB, i), &CB,
1690 TrackedMultipleRetVals[std::make_pair(
F, i)],
1693 auto TFRVI = TrackedRetVals.find(
F);
1694 if (TFRVI == TrackedRetVals.end())
1695 return handleCallOverdefined(CB);
1704 while (!BBWorkList.empty() || !InstWorkList.empty() ||
1705 !OverdefinedInstWorkList.empty()) {
1708 while (!OverdefinedInstWorkList.empty()) {
1709 Value *
I = OverdefinedInstWorkList.pop_back_val();
1720 markUsersAsChanged(
I);
1724 while (!InstWorkList.empty()) {
1725 Value *
I = InstWorkList.pop_back_val();
1736 if (
I->getType()->isStructTy() || !getValueState(
I).isOverdefined())
1737 markUsersAsChanged(
I);
1741 while (!BBWorkList.empty()) {
1767 bool MadeChange =
false;
1769 if (!BBExecutable.count(&BB))
1774 if (
I.getType()->isVoidTy())
1777 if (
auto *STy = dyn_cast<StructType>(
I.getType())) {
1781 if (
auto *CB = dyn_cast<CallBase>(&
I))
1783 if (MRVFunctionsTracked.count(
F))
1788 if (isa<ExtractValueInst>(
I) || isa<InsertValueInst>(
I))
1792 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1795 markOverdefined(LV, &
I);
1811 if (
auto *CB = dyn_cast<CallBase>(&
I))
1813 if (TrackedRetVals.count(
F))
1816 if (isa<LoadInst>(
I)) {
1823 markOverdefined(&
I);
1829 <<
"\nResolved undefs in " <<
F.getName() <<
'\n');
1847 return Visitor->addAnalysis(
F, std::move(
A));
1851 return Visitor->markBlockExecutable(BB);
1855 return Visitor->getPredicateInfoFor(
I);
1859 return Visitor->getLoopInfo(
F);
1865 Visitor->trackValueOfGlobalVariable(GV);
1869 Visitor->addTrackedFunction(
F);
1873 Visitor->addToMustPreserveReturnsInFunctions(
F);
1877 return Visitor->mustPreserveReturn(
F);
1881 Visitor->addArgumentTrackedFunction(
F);
1885 return Visitor->isArgumentTrackedFunction(
F);
1891 return Visitor->resolvedUndefsIn(
F);
1895 Visitor->solveWhileResolvedUndefsIn(M);
1900 Visitor->solveWhileResolvedUndefsIn(WorkList);
1904 return Visitor->isBlockExecutable(BB);
1908 return Visitor->isEdgeFeasible(
From, To);
1911std::vector<ValueLatticeElement>
1913 return Visitor->getStructLatticeValueFor(V);
1917 return Visitor->removeLatticeValueFor(V);
1921 return Visitor->getLatticeValueFor(V);
1926 return Visitor->getTrackedRetVals();
1931 return Visitor->getTrackedGlobals();
1935 return Visitor->getMRVFunctionsTracked();
1941 return Visitor->isStructLatticeConstant(
F, STy);
1945 return Visitor->getConstant(LV);
1949 return Visitor->getArgumentTrackedFunctions();
1954 Visitor->markArgInFuncSpecialization(
F, Args);
1958 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.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
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.
static Constant * getGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList, bool InBounds=false, std::optional< unsigned > InRangeIndex=std::nullopt, Type *OnlyIfReducedTy=nullptr)
Getelementptr form.
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.
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
An instruction for ordering other memory operations.
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.
bool isExceptionalTerminator() const
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.
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.
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 LoopInfo & getLoopInfo(Function &F)
const PredicateBase * getPredicateInfoFor(Instruction *I)
std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
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) const
SCCPInstVisitor(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
DomTreeUpdater getDTU(Function &F)
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 markArgInFuncSpecialization(Function *F, const SmallVectorImpl< ArgInfo > &Args)
void addTrackedFunction(Function *F)
SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions()
void solveWhileResolvedUndefsIn(Module &M)
void trackValueOfGlobalVariable(GlobalVariable *GV)
const SmallPtrSet< Function *, 16 > getMRVFunctionsTracked()
void addAnalysis(Function &F, AnalysisResultsForFn A)
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals()
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)
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 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 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.
Constant * getConstant(const ValueLatticeElement &LV) const
Helper to return a Constant if LV is either a constant or a constant range with a single element.
void solveWhileResolvedUndefsIn(Module &M)
const PredicateBase * getPredicateInfoFor(Instruction *I)
const LoopInfo & getLoopInfo(Function &F)
bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
DomTreeUpdater getDTU(Function &F)
void addArgumentTrackedFunction(Function *F)
void addAnalysis(Function &F, AnalysisResultsForFn A)
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.
bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
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 ...
static bool isConstant(const ValueLatticeElement &LV)
void markArgInFuncSpecialization(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Mark the constant arguments of a new function specialization.
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.
bool wouldInstructionBeTriviallyDead(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 * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
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.
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.
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.
Helper struct for bundling up the analysis results per function for IPSCCP.
Struct to control some aspects related to merging constant ranges.
MergeOptions & setMaxWidenSteps(unsigned Steps=1)
MergeOptions & setCheckWiden(bool V=true)