43#define DEBUG_TYPE "sccp"
88 <<
" as a constant\n");
95 if (V->getType()->isPointerTy()) {
97 if (LV.mayHaveDifferentProvenance()) {
99 bool Changed = V->replaceUsesWithIf(Const, [&](
Use &U) {
102 LLVM_DEBUG(
dbgs() <<
" Constant pointer: " << *Const <<
" = " << *V
110 LLVM_DEBUG(
dbgs() <<
" Constant: " << *Const <<
" = " << *V <<
'\n');
113 V->replaceAllUsesWith(Const);
125 if (!Callee->hasMetadata(LLVMContext::MD_implicit_ref))
133 Callee->getMetadata(LLVMContext::MD_implicit_ref, MDs);
135 Caller->addMetadata(LLVMContext::MD_implicit_ref, *MD);
144 return Const->toConstantRange();
146 unsigned Bitwidth =
Op->getType()->getScalarSizeInBits();
147 return ConstantRange::getFull(Bitwidth);
158 auto GetRange = [&Solver, &InsertedValues](
Value *
Op) {
172 if (NUWRange.contains(RangeA)) {
181 if (NSWRange.contains(RangeA)) {
188 if (
Range.isAllNonNegative()) {
193 if (TI->hasNoSignedWrap() && TI->hasNoUnsignedWrap())
197 uint64_t DestWidth = TI->getDestTy()->getScalarSizeInBits();
198 if (!TI->hasNoUnsignedWrap()) {
199 if (
Range.getActiveBits() <= DestWidth) {
200 TI->setHasNoUnsignedWrap(
true);
204 if (!TI->hasNoSignedWrap()) {
205 if (
Range.getMinSignedBits() <= DestWidth) {
206 TI->setHasNoSignedWrap(
true);
211 if (
GEP->hasNoUnsignedWrap() || !
GEP->hasNoUnsignedSignedWrap())
215 [&](
Value *V) { return GetRange(V).isAllNonNegative(); })) {
216 GEP->setNoWrapFlags(
GEP->getNoWrapFlags() |
230 auto isNonNegative = [&Solver, &InsertedValues](
Value *V) {
236 case Instruction::SIToFP:
237 case Instruction::SExt: {
240 if (!isNonNegative(Op0))
244 : Instruction::UIToFP,
249 case Instruction::AShr: {
252 if (!isNonNegative(Op0))
258 case Instruction::SDiv:
259 case Instruction::SRem: {
262 if (!isNonNegative(Op0) || !isNonNegative(Op1))
264 auto NewOpcode = Inst.
getOpcode() == Instruction::SDiv ? Instruction::UDiv
267 if (Inst.
getOpcode() == Instruction::SDiv)
276 assert(NewInst &&
"Expected replacement instruction");
278 InsertedValues.
insert(NewInst);
290 auto GetRange = [&Solver, &InsertedValues](
Value *
Op) {
305 Value *LHS = Cmp->getOperand(0);
306 Value *RHS = Cmp->getOperand(1);
307 unsigned BitWidth = LHS->getType()->getScalarSizeInBits();
321 if (!RHSLower.
icmp(Pred, LRange) || !LRange.
icmp(Pred, RHSUpper))
338 auto MatchTwoInstructionExactRangeCheck =
339 [&]() -> std::optional<ConstantRange> {
344 Value *LHS = ICmp->getOperand(0);
350 if (ICmp->isEquality()) {
361 if (
auto CR = MatchTwoInstructionExactRangeCheck()) {
366 auto ConvertCRToICmp =
367 [&](
const std::optional<ConstantRange> &NewCR) ->
Value * {
371 if (NewCR && NewCR->getEquivalentICmp(Pred, RHS)) {
374 Builder.CreateICmp(Pred,
X, ConstantInt::get(
X->getType(), RHS));
375 InsertedValues.
insert(NewICmp);
384 if (
auto *V = ConvertCRToICmp(CR->exactIntersectWith(LRange)))
387 if (
auto *V = ConvertCRToICmp(CR->exactUnionWith(LRange.
inverse())))
399 bool MadeChanges =
false;
401 if (Inst.getType()->isVoidTy())
409 Inst.eraseFromParent();
419 Inst.replaceAllUsesWith(V);
420 Inst.eraseFromParent();
431 bool HasNonFeasibleEdges =
false;
434 FeasibleSuccessors.
insert(Succ);
436 HasNonFeasibleEdges =
true;
440 if (!HasNonFeasibleEdges)
446 "Terminator must be a br, switch or indirectbr");
448 if (FeasibleSuccessors.
size() == 0) {
453 Succ->removePredecessor(BB);
454 if (SeenSuccs.
insert(Succ).second)
460 }
else if (FeasibleSuccessors.
size() == 1) {
464 bool HaveSeenOnlyFeasibleSuccessor =
false;
466 if (Succ == OnlyFeasibleSuccessor && !HaveSeenOnlyFeasibleSuccessor) {
469 HaveSeenOnlyFeasibleSuccessor =
true;
473 Succ->removePredecessor(BB);
481 }
else if (FeasibleSuccessors.
size() > 1) {
488 if (!FeasibleSuccessors.
contains(DefaultDest)) {
489 if (!NewUnreachableBB) {
499 SI->setDefaultDest(NewUnreachableBB);
504 for (
auto CI =
SI->case_begin(); CI !=
SI->case_end();) {
505 if (FeasibleSuccessors.
contains(CI->getCaseSuccessor())) {
533 Attribute OldAttr =
F->getAttributeAtIndex(AttrIndex, Attribute::Range);
537 F->addAttributeAtIndex(
544 !
F->hasAttributeAtIndex(AttrIndex, Attribute::NonNull)) {
545 F->addAttributeAtIndex(AttrIndex,
560 if (!
A.getType()->isStructTy())
596 TrackedMultipleRetVals;
628 using Edge = std::pair<BasicBlock *, BasicBlock *>;
648 void pushUsersToWorkList(
Value *V);
658 bool MayIncludeUndef =
false);
661 assert(!V->getType()->isStructTy() &&
"structs should use mergeInValue");
662 return markConstant(ValueState[V], V,
C);
694 assert(!V->getType()->isStructTy() &&
"Should use getStructValueState");
696 auto I = ValueState.try_emplace(V);
713 assert(V->getType()->isStructTy() &&
"Should use getValueState");
715 "Invalid element #");
717 auto I = StructValueState.insert(
725 Constant *Elt =
C->getAggregateElement(i);
737 template <
typename FnTy>
void forEachLatticeElement(
Value *V, FnTy Fn) {
739 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
741 return getStructValueState(
Op, i);
745 return getValueState(
Op);
756 while (!ToInvalidate.
empty()) {
759 if (!Invalidated.insert(Inst).second)
762 if (!BBExecutable.count(Inst->
getParent()))
769 Function *
F = RetInst->getParent()->getParent();
771 if (
auto It = TrackedRetVals.find(
F); It != TrackedRetVals.end()) {
774 }
else if (MRVFunctionsTracked.count(
F)) {
776 for (
unsigned I = 0, E = STy->getNumElements();
I != E; ++
I)
782 <<
F->getName() <<
"\n");
784 for (
User *U :
F->users())
786 if (CB->getCalledFunction() ==
F)
790 for (
unsigned I = 0, E = STy->getNumElements();
I != E; ++
I) {
791 if (
auto It = StructValueState.find({Inst, I});
792 It != StructValueState.end()) {
797 }
else if (
auto It = ValueState.find(Inst); It != ValueState.end()) {
809 auto It = AdditionalUsers.find(V);
810 if (It != AdditionalUsers.end())
811 for (
User *U : It->second)
827 void addAdditionalUser(
Value *V,
User *U) { AdditionalUsers[V].insert(U); }
830 void handleCallOverdefined(
CallBase &CB);
831 void handleCallResult(
CallBase &CB);
832 void handleCallArguments(
CallBase &CB);
860 markOverdefined(&CPI);
861 visitTerminator(CPI);
878 visitTerminator(CBI);
881 void visitCallBase(CallBase &CB);
882 void visitResumeInst(ResumeInst &
I) {
884 void visitUnreachableInst(UnreachableInst &
I) {
886 void visitFenceInst(FenceInst &
I) {
889 void visitInstruction(Instruction &
I);
895 FnPredicateInfo.insert({&
F, std::make_unique<PredicateInfo>(
896 F, DT, AC, PredicateInfoAllocator)});
900 auto It = FnPredicateInfo.find(&
F);
901 if (It == FnPredicateInfo.end())
907 if (BC->getType() == BC->getOperand(0)->getType()) {
908 if (It->second->getPredicateInfoFor(&Inst)) {
910 Inst.replaceAllUsesWith(
Op);
911 Inst.eraseFromParent();
924 auto It = FnPredicateInfo.find(
I->getParent()->getParent());
925 if (It == FnPredicateInfo.end())
927 return It->second->getPredicateInfoFor(
I);
933 : DL(DL), GetTLI(GetTLI), Ctx(Ctx) {}
946 MRVFunctionsTracked.insert(
F);
947 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
948 TrackedMultipleRetVals.try_emplace(std::make_pair(
F, i));
949 }
else if (!
F->getReturnType()->isVoidTy())
950 TrackedRetVals.try_emplace(
F);
954 MustPreserveReturnsInFunctions.insert(
F);
958 return MustPreserveReturnsInFunctions.count(
F);
962 TrackingIncomingArguments.insert(
F);
966 return TrackingIncomingArguments.count(
F);
970 return TrackingIncomingArguments;
980 return BBExecutable.count(BB);
986 std::vector<ValueLatticeElement> StructValues;
988 assert(STy &&
"getStructLatticeValueFor() can be called only on structs");
989 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
990 auto I = StructValueState.find(std::make_pair(V, i));
991 assert(
I != StructValueState.end() &&
"Value not in valuemap!");
992 StructValues.push_back(
I->second);
1005 assert(!
F->getReturnType()->isVoidTy() &&
1006 (TrackedRetVals.count(
F) || MRVFunctionsTracked.count(
F)) &&
1007 "All non void specializations should be tracked");
1009 handleCallResult(*
Call);
1013 assert(!V->getType()->isStructTy() &&
1014 "Should use getStructLatticeValueFor");
1015 auto I = ValueState.find(V);
1016 assert(
I != ValueState.end() &&
1017 "V not found in ValueState nor Paramstate map!");
1022 return TrackedRetVals;
1027 return TrackedGlobals;
1031 return MRVFunctionsTracked;
1036 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1037 markOverdefined(getStructValueState(V, i), V);
1039 markOverdefined(ValueState[V], V);
1043 if (
A->getType()->isIntOrIntVectorTy()) {
1044 if (std::optional<ConstantRange>
Range =
A->getRange())
1047 if (
A->hasNonNullAttr())
1054 if (
A->getType()->isStructTy())
1055 return (
void)markOverdefined(
A);
1070 BBExecutable.erase(&BB);
1074 bool ResolvedUndefs =
true;
1075 while (ResolvedUndefs) {
1077 ResolvedUndefs =
false;
1084 bool ResolvedUndefs =
true;
1085 while (ResolvedUndefs) {
1087 ResolvedUndefs =
false;
1094 bool ResolvedUndefs =
true;
1095 while (ResolvedUndefs) {
1097 ResolvedUndefs =
false;
1098 for (
Value *V : Invalidated)
1102 Invalidated.clear();
1109 if (!BBExecutable.insert(BB).second)
1112 BBWorkList.push_back(BB);
1126 InstWorkList.insert(
I);
1129void SCCPInstVisitor::pushUsersToWorkList(
Value *
V) {
1130 for (
User *U :
V->users())
1134 auto Iter = AdditionalUsers.find(
V);
1135 if (Iter != AdditionalUsers.end()) {
1139 for (
User *U : Iter->second)
1150 pushUsersToWorkList(
V);
1155 if (!
IV.markConstant(
C, MayIncludeUndef))
1158 pushUsersToWorkList(
V);
1164 if (!
IV.markNotConstant(
C))
1167 pushUsersToWorkList(
V);
1173 if (!
IV.markConstantRange(CR))
1175 LLVM_DEBUG(
dbgs() <<
"markConstantRange: " << CR <<
": " << *
V <<
'\n');
1176 pushUsersToWorkList(
V);
1181 if (!
IV.markOverdefined())
1186 <<
"Function '" <<
F->getName() <<
"'\n";
1187 else dbgs() << *
V <<
'\n');
1189 pushUsersToWorkList(
V);
1195 const auto &It = TrackedMultipleRetVals.find(std::make_pair(
F, i));
1196 assert(It != TrackedMultipleRetVals.end());
1207 assert(
C->getType() == Ty &&
"Type mismatch");
1221 if (V->getType()->isStructTy()) {
1225 std::vector<Constant *> ConstVals;
1227 for (
unsigned I = 0, E = ST->getNumElements();
I != E; ++
I) {
1241 assert(Const &&
"Constant is nullptr here!");
1247 assert(!Args.empty() &&
"Specialization without arguments");
1248 assert(
F->arg_size() == Args[0].Formal->getParent()->arg_size() &&
1249 "Functions should have the same number of arguments");
1251 auto Iter = Args.begin();
1254 for (
auto End =
F->arg_end(); NewArg !=
End; ++NewArg, ++OldArg) {
1261 if (Iter != Args.end() && Iter->Formal == &*OldArg) {
1263 for (
unsigned I = 0, E = STy->getNumElements();
I != E; ++
I) {
1265 NewValue.
markConstant(Iter->Actual->getAggregateElement(
I));
1268 ValueState[&*NewArg].markConstant(Iter->Actual);
1273 for (
unsigned I = 0, E = STy->getNumElements();
I != E; ++
I) {
1275 NewValue = StructValueState[{&*OldArg,
I}];
1279 NewValue = ValueState[&*OldArg];
1285void SCCPInstVisitor::visitInstruction(
Instruction &
I) {
1288 LLVM_DEBUG(
dbgs() <<
"SCCP: Don't know how to handle: " <<
I <<
'\n');
1289 markOverdefined(&
I);
1295 if (
IV.mergeIn(MergeWithV, Opts)) {
1296 pushUsersToWorkList(
V);
1297 LLVM_DEBUG(
dbgs() <<
"Merged " << MergeWithV <<
" into " << *
V <<
" : "
1305 if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
1313 <<
" -> " << Dest->
getName() <<
'\n');
1315 for (PHINode &PN : Dest->
phis())
1316 pushToWorkList(&PN);
1323void SCCPInstVisitor::getFeasibleSuccessors(
Instruction &TI,
1332 const ValueLatticeElement &BCValue = getValueState(BI->getCondition());
1333 ConstantInt *CI =
getConstantInt(BCValue, BI->getCondition()->getType());
1338 Succs[0] = Succs[1] =
true;
1343 Succs[CI->
isZero()] =
true;
1355 if (!
SI->getNumCases()) {
1359 const ValueLatticeElement &SCValue = getValueState(
SI->getCondition());
1360 if (ConstantInt *CI =
1362 Succs[
SI->findCaseValue(CI)->getSuccessorIndex()] =
true;
1370 unsigned ReachableCaseCount = 0;
1371 for (
const auto &Case :
SI->cases()) {
1372 const APInt &CaseValue = Case.getCaseValue()->getValue();
1374 Succs[Case.getSuccessorIndex()] =
true;
1375 ++ReachableCaseCount;
1379 Succs[
SI->case_default()->getSuccessorIndex()] =
1394 const ValueLatticeElement &IBRValue = getValueState(IBR->getAddress());
1396 getConstant(IBRValue, IBR->getAddress()->getType()));
1406 "Block address of a different function ?");
1407 for (
unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
1409 if (IBR->getDestination(i) ==
T) {
1420 LLVM_DEBUG(
dbgs() <<
"Unknown terminator instruction: " << TI <<
'\n');
1430 return KnownFeasibleEdges.count(
Edge(From, To));
1450void SCCPInstVisitor::visitPHINode(
PHINode &PN) {
1454 return (
void)markOverdefined(&PN);
1456 if (isInstFullyOverDefined(PN))
1470 forEachLatticeElement(&PN, [&](
auto GetValueState) {
1474 for (
unsigned i : FeasibleIncomingIndices) {
1484 ValueLatticeElement &PhiStateRef = GetValueState(&PN);
1485 mergeInValue(PhiStateRef, &PN, PhiState,
1486 ValueLatticeElement::MergeOptions().setMaxWidenSteps(
1487 FeasibleIncomingIndices.size() + 1));
1489 std::max((
unsigned)FeasibleIncomingIndices.size(),
1494void SCCPInstVisitor::visitReturnInst(
ReturnInst &
I) {
1495 if (
I.getNumOperands() == 0)
1499 Value *ResultOp =
I.getOperand(0);
1503 auto TFRVI = TrackedRetVals.find(
F);
1504 if (TFRVI != TrackedRetVals.end()) {
1505 mergeInValue(TFRVI->second,
F, getValueState(ResultOp));
1511 if (!TrackedMultipleRetVals.empty()) {
1513 if (MRVFunctionsTracked.count(
F))
1514 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1515 mergeInValue(TrackedMultipleRetVals[std::make_pair(
F, i)],
F,
1516 getStructValueState(ResultOp, i));
1520void SCCPInstVisitor::visitTerminator(
Instruction &TI) {
1522 getFeasibleSuccessors(TI, SuccFeasible);
1527 for (
unsigned i = 0, e = SuccFeasible.
size(); i != e; ++i)
1528 if (SuccFeasible[i])
1532void SCCPInstVisitor::visitCastInst(
CastInst &
I) {
1535 if (ValueState[&
I].isOverdefined())
1539 if (BC->getType() == BC->getOperand(0)->getType()) {
1541 handlePredicate(&
I,
I.getOperand(0), PI);
1547 const ValueLatticeElement &OpSt = getValueState(
I.getOperand(0));
1551 if (Constant *OpC =
getConstant(OpSt,
I.getOperand(0)->getType())) {
1555 auto &LV = ValueState[&
I];
1562 if (
I.getDestTy()->isIntOrIntVectorTy() &&
1563 I.getSrcTy()->isIntOrIntVectorTy() &&
1564 I.getOpcode() != Instruction::BitCast) {
1565 ConstantRange OpRange =
1567 auto &LV = getValueState(&
I);
1569 Type *DestTy =
I.getDestTy();
1573 Trunc->getNoWrapKind());
1578 markOverdefined(&
I);
1587 addAdditionalUser(
LHS, &EVI);
1588 addAdditionalUser(
RHS, &EVI);
1590 const ValueLatticeElement &
L = getValueState(
LHS);
1591 if (
L.isUnknownOrUndef())
1593 ConstantRange LR =
L.asConstantRange(Ty,
false);
1595 const ValueLatticeElement &
R = getValueState(
RHS);
1596 if (
R.isUnknownOrUndef())
1599 ConstantRange RR =
R.asConstantRange(Ty,
false);
1604 assert(Idx == 1 &&
"Index can only be 0 or 1");
1609 markOverdefined(&EVI);
1617 return (
void)markOverdefined(&EVI);
1621 if (ValueState[&EVI].isOverdefined())
1622 return (
void)markOverdefined(&EVI);
1626 return (
void)markOverdefined(&EVI);
1632 return handleExtractOfWithOverflow(EVI, WO, i);
1633 ValueLatticeElement EltVal = getStructValueState(AggVal, i);
1634 mergeInValue(ValueState[&EVI], &EVI, EltVal);
1637 return (
void)markOverdefined(&EVI);
1644 return (
void)markOverdefined(&IVI);
1648 if (ValueState[&IVI].isOverdefined())
1649 return (
void)markOverdefined(&IVI);
1654 return (
void)markOverdefined(&IVI);
1660 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
1663 ValueLatticeElement EltVal = getStructValueState(Aggr, i);
1664 mergeInValue(getStructValueState(&IVI, i), &IVI, EltVal);
1671 markOverdefined(getStructValueState(&IVI, i), &IVI);
1673 ValueLatticeElement InVal = getValueState(Val);
1674 mergeInValue(getStructValueState(&IVI, i), &IVI, InVal);
1679void SCCPInstVisitor::visitSelectInst(
SelectInst &
I) {
1682 if (isInstFullyOverDefined(
I))
1683 return (
void)markOverdefined(&
I);
1685 const ValueLatticeElement &CondValue = getValueState(
I.getCondition());
1689 if (ConstantInt *CondCB =
1691 Value *OpVal = CondCB->isZero() ?
I.getFalseValue() :
I.getTrueValue();
1692 forEachLatticeElement(&
I, [&](
auto GetValueState) {
1693 ValueLatticeElement OpValState = GetValueState(OpVal);
1694 mergeInValue(GetValueState(&
I), &
I, OpValState);
1702 forEachLatticeElement(&
I, [&](
auto GetValueState) {
1703 ValueLatticeElement TVal = GetValueState(
I.getTrueValue());
1704 ValueLatticeElement FVal = GetValueState(
I.getFalseValue());
1706 ValueLatticeElement &State = GetValueState(&
I);
1710 pushUsersToWorkListMsg(State, &
I);
1715void SCCPInstVisitor::visitUnaryOperator(
Instruction &
I) {
1716 ValueLatticeElement V0State = getValueState(
I.getOperand(0));
1718 ValueLatticeElement &
IV = ValueState[&
I];
1721 if (
IV.isOverdefined())
1722 return (
void)markOverdefined(&
I);
1731 return (
void)markConstant(
IV, &
I,
C);
1733 markOverdefined(&
I);
1736void SCCPInstVisitor::visitFreezeInst(
FreezeInst &
I) {
1739 if (
I.getType()->isStructTy())
1740 return (
void)markOverdefined(&
I);
1742 ValueLatticeElement V0State = getValueState(
I.getOperand(0));
1743 ValueLatticeElement &
IV = ValueState[&
I];
1746 if (
IV.isOverdefined())
1747 return (
void)markOverdefined(&
I);
1757 markOverdefined(&
I);
1761void SCCPInstVisitor::visitBinaryOperator(
Instruction &
I) {
1762 ValueLatticeElement V1State = getValueState(
I.getOperand(0));
1763 ValueLatticeElement V2State = getValueState(
I.getOperand(1));
1765 ValueLatticeElement &
IV = ValueState[&
I];
1766 if (
IV.isOverdefined())
1774 return (
void)markOverdefined(&
I);
1788 SimplifyQuery(DL, &
I));
1798 ValueLatticeElement NewV;
1800 return (
void)mergeInValue(ValueState[&
I], &
I, NewV);
1805 if (!
I.getType()->isIntOrIntVectorTy())
1806 return markOverdefined(&
I);
1815 ConstantRange
R =
A.binaryOp(*BO,
B);
1820void SCCPInstVisitor::visitCmpInst(
CmpInst &
I) {
1823 if (ValueState[&
I].isOverdefined())
1824 return (
void)markOverdefined(&
I);
1826 Value *Op1 =
I.getOperand(0);
1827 Value *Op2 =
I.getOperand(1);
1831 auto V1State = getValueState(Op1);
1832 auto V2State = getValueState(Op2);
1836 ValueLatticeElement CV;
1838 mergeInValue(ValueState[&
I], &
I, CV);
1847 markOverdefined(&
I);
1853 if (ValueState[&
I].isOverdefined())
1854 return (
void)markOverdefined(&
I);
1856 const ValueLatticeElement &PtrState = getValueState(
I.getPointerOperand());
1862 if (
I.hasNoUnsignedWrap() ||
1865 return (
void)markNotNull(ValueState[&
I], &
I);
1866 return (
void)markOverdefined(&
I);
1873 for (
unsigned i = 0, e =
I.getNumOperands(); i != e; ++i) {
1874 const ValueLatticeElement &State = getValueState(
I.getOperand(i));
1878 if (Constant *
C =
getConstant(State,
I.getOperand(i)->getType())) {
1883 return (
void)markOverdefined(&
I);
1891 if (PtrMayHaveDifferentProvenance)
1892 ValueState[&
I].setMayHaveDifferentProvenance(
true);
1894 markOverdefined(&
I);
1897void SCCPInstVisitor::visitAllocaInst(
AllocaInst &
I) {
1899 return (
void)markNotNull(ValueState[&
I], &
I);
1901 markOverdefined(&
I);
1904void SCCPInstVisitor::visitStoreInst(
StoreInst &
SI) {
1906 if (
SI.getOperand(0)->getType()->isStructTy())
1913 auto I = TrackedGlobals.find(GV);
1914 if (
I == TrackedGlobals.end())
1918 mergeInValue(
I->second, GV, getValueState(
SI.getOperand(0)),
1919 ValueLatticeElement::MergeOptions().setCheckWiden(
false));
1920 if (
I->second.isOverdefined())
1921 TrackedGlobals.erase(
I);
1926 if (CB->getType()->isIntOrIntVectorTy())
1927 if (std::optional<ConstantRange>
Range = CB->getRange())
1929 if (CB->getType()->isPointerTy() && CB->isReturnNonNull())
1934 if (
I->getType()->isIntOrIntVectorTy())
1935 if (
MDNode *Ranges =
I->getMetadata(LLVMContext::MD_range))
1938 if (
I->hasMetadata(LLVMContext::MD_nonnull))
1947void SCCPInstVisitor::visitLoadInst(
LoadInst &
I) {
1950 if (
I.getType()->isStructTy() ||
I.isVolatile())
1951 return (
void)markOverdefined(&
I);
1955 if (ValueState[&
I].isOverdefined())
1956 return (
void)markOverdefined(&
I);
1958 const ValueLatticeElement &PtrVal = getValueState(
I.getOperand(0));
1964 ValueLatticeElement &
IV = ValueState[&
I];
1969 return (
void)markOverdefined(
IV, &
I);
1976 if (!TrackedGlobals.empty()) {
1978 auto It = TrackedGlobals.find(GV);
1979 if (It != TrackedGlobals.end()) {
1988 return (
void)markConstant(
IV, &
I,
C);
1995void SCCPInstVisitor::visitCallBase(
CallBase &CB) {
1996 handleCallResult(CB);
1997 handleCallArguments(CB);
2000void SCCPInstVisitor::handleCallOverdefined(
CallBase &CB) {
2009 return (
void)markOverdefined(&CB);
2011 if (!
F || !
F->isDeclaration())
2016 const TargetLibraryInfo *
TLI = &GetTLI(*
F);
2019 for (
const Use &
A : CB.args()) {
2020 if (
A.get()->getType()->isStructTy())
2021 return markOverdefined(&CB);
2022 if (
A.get()->getType()->isMetadataTy())
2024 const ValueLatticeElement &State = getValueState(
A);
2029 return (
void)markOverdefined(&CB);
2035 return (
void)markOverdefined(&CB);
2049void SCCPInstVisitor::handleCallArguments(
CallBase &CB) {
2054 if (TrackingIncomingArguments.count(
F)) {
2063 if (AI->hasByValAttr() && !
F->onlyReadsMemory()) {
2064 markOverdefined(&*AI);
2069 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
2070 ValueLatticeElement CallArg = getStructValueState(*CAI, i);
2071 mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg,
2075 ValueLatticeElement CallArg =
2085 ValueLatticeElement CopyOfVal = getValueState(CopyOf);
2086 const std::optional<PredicateConstraint> &Constraint = PI->
getConstraint();
2088 mergeInValue(ValueState[
I],
I, CopyOfVal);
2093 Value *OtherOp = Constraint->OtherOp;
2096 if (getValueState(OtherOp).isUnknown()) {
2097 addAdditionalUser(OtherOp,
I);
2101 ValueLatticeElement CondVal = getValueState(OtherOp);
2102 ValueLatticeElement &
IV = ValueState[
I];
2105 ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->
getType()));
2117 if (CopyOfCR.isEmptySet())
2118 CopyOfCR = ConstantRange::getFull(CopyOfCR.getBitWidth());
2119 auto NewCR = ImposedCR.intersectWith(CopyOfCR);
2123 if (!CopyOfCR.contains(NewCR) && CopyOfCR.getSingleMissingElement())
2124 NewCR = std::move(CopyOfCR);
2131 addAdditionalUser(OtherOp,
I);
2139 addAdditionalUser(OtherOp,
I);
2142 mergeInValue(
IV,
I, CondVal);
2146 addAdditionalUser(OtherOp,
I);
2151 return (
void)mergeInValue(
IV,
I, CopyOfVal);
2154void SCCPInstVisitor::handleCallResult(
CallBase &CB) {
2158 if (
II->getIntrinsicID() == Intrinsic::vscale) {
2161 return (
void)mergeInValue(ValueState[
II],
II,
2164 if (
II->getIntrinsicID() == Intrinsic::experimental_get_vector_length) {
2165 Value *CountArg =
II->getArgOperand(0);
2166 Value *VF =
II->getArgOperand(1);
2173 ConstantRange
Count = getValueState(CountArg)
2174 .asConstantRange(CountArg->
getType(),
false)
2176 ConstantRange MaxLanes = getValueState(VF)
2177 .asConstantRange(VF->
getType(),
false)
2194 return (
void)mergeInValue(ValueState[
II],
II,
2204 const ValueLatticeElement &State = getValueState(
Op);
2213 return (
void)mergeInValue(ValueState[
II],
II,
2221 if (!
F ||
F->isDeclaration())
2222 return handleCallOverdefined(CB);
2226 if (!MRVFunctionsTracked.count(
F))
2227 return handleCallOverdefined(CB);
2231 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2232 mergeInValue(getStructValueState(&CB, i), &CB,
2233 TrackedMultipleRetVals[std::make_pair(
F, i)],
2236 auto TFRVI = TrackedRetVals.find(
F);
2237 if (TFRVI == TrackedRetVals.end())
2238 return handleCallOverdefined(CB);
2245bool SCCPInstVisitor::isInstFullyOverDefined(
Instruction &Inst) {
2250 for (
unsigned i = 0, e = STy->getNumElements(); i < e; ++i) {
2251 if (!getStructValueState(&Inst, i).isOverdefined())
2257 return getValueState(&Inst).isOverdefined();
2262 while (!BBWorkList.empty() || !InstWorkList.empty()) {
2264 while (!InstWorkList.empty()) {
2266 Invalidated.erase(
I);
2274 while (!BBWorkList.empty()) {
2276 BBVisited.insert(BB);
2290 if (
I.getType()->isVoidTy())
2299 if (MRVFunctionsTracked.count(
F))
2308 for (
unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
2311 markOverdefined(LV, &
I);
2329 if (TrackedRetVals.count(
F))
2339 markOverdefined(&
I);
2357 bool MadeChange =
false;
2359 if (!BBExecutable.count(&BB))
2367 <<
"\nResolved undefs in " <<
F.getName() <<
'\n');
2385 return Visitor->getDataLayout();
2390 Visitor->addPredicateInfo(
F, DT, AC);
2394 Visitor->removeSSACopies(
F);
2398 return Visitor->markBlockExecutable(BB);
2402 return Visitor->getPredicateInfoFor(
I);
2406 Visitor->trackValueOfGlobalVariable(GV);
2410 Visitor->addTrackedFunction(
F);
2414 Visitor->addToMustPreserveReturnsInFunctions(
F);
2418 return Visitor->mustPreserveReturn(
F);
2422 Visitor->addArgumentTrackedFunction(
F);
2426 return Visitor->isArgumentTrackedFunction(
F);
2431 return Visitor->getArgumentTrackedFunctions();
2437 return Visitor->resolvedUndefsIn(
F);
2441 Visitor->solveWhileResolvedUndefsIn(M);
2446 Visitor->solveWhileResolvedUndefsIn(WorkList);
2450 Visitor->solveWhileResolvedUndefs();
2454 return Visitor->isBlockExecutable(BB);
2458 return Visitor->isEdgeFeasible(From, To);
2461std::vector<ValueLatticeElement>
2463 return Visitor->getStructLatticeValueFor(V);
2467 return Visitor->removeLatticeValueFor(V);
2471 Visitor->resetLatticeValueFor(
Call);
2475 return Visitor->getLatticeValueFor(V);
2480 return Visitor->getTrackedRetVals();
2485 return Visitor->getTrackedGlobals();
2489 return Visitor->getMRVFunctionsTracked();
2495 Visitor->trackValueOfArgument(V);
2499 return Visitor->isStructLatticeConstant(
F, STy);
2504 return Visitor->getConstant(LV, Ty);
2508 return Visitor->getConstantOrNull(V);
2513 Visitor->setLatticeValueForSpecializationArguments(
F, Args);
2517 Visitor->markFunctionUnreachable(
F);
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
static ValueLatticeElement::MergeOptions getMaxWidenStepsOpts()
Returns MergeOptions with MaxWidenSteps set to MaxNumRangeExtensions.
static const unsigned MaxNumRangeExtensions
static ValueLatticeElement getValueFromMetadata(const Instruction *I)
std::pair< BasicBlock *, BasicBlock * > Edge
This file implements a set that has insertion order iteration characteristics.
static ConstantInt * getConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static const uint32_t IV[8]
Class for arbitrary precision integers.
unsigned countr_zero() const
Count the number of trailing zero bits.
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
an instruction to allocate memory on the stack
This class represents an incoming formal argument to a Function.
A cache of @llvm.assume calls within a function.
Functions, function parameters, and return types can have attributes to indicate how they should be t...
LLVM_ABI const ConstantRange & getRange() const
Returns the value of the range attribute.
static LLVM_ABI Attribute get(LLVMContext &Context, AttrKind Kind, uint64_t Val=0)
Return a uniquified Attribute object.
bool isValid() const
Return true if the attribute is any kind of attribute.
LLVM Basic Block Representation.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const Function * getParent() const
Return the enclosing method, or null if none.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
LLVM_ABI void removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs=false)
Update PHI nodes in this BasicBlock before removal of predecessor Pred.
LLVM_ABI unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
LLVM_ABI Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
static LLVM_ABI BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
Function * getFunction() const
BasicBlock * getBasicBlock() const
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.
LLVM_ABI bool isMustTailCall() const
Tests if this call site must be tail call optimized.
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.
static LLVM_ABI CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLE
signed less or equal
@ ICMP_ULE
unsigned less or equal
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 LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
static LLVM_ABI ConstantPointerNull * get(PointerType *T)
Static factory methods - Return objects of the specified value.
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
LLVM_ABI 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...
LLVM_ABI bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
LLVM_ABI bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other?
static LLVM_ABI ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
LLVM_ABI bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
static LLVM_ABI 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.
LLVM_ABI ConstantRange truncate(uint32_t BitWidth, unsigned NoWrapKind=0) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
LLVM_ABI bool isAllNonNegative() const
Return true if all values in this range are non-negative.
static LLVM_ABI 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...
LLVM_ABI ConstantRange multiply(const ConstantRange &Other, unsigned NoWrapKind=0) const
Return a new range representing the possible values resulting from a multiplication of a value in thi...
static LLVM_ABI ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
LLVM_ABI ConstantRange inverse() const
Return a new range that is the logical not of the current set.
LLVM_ABI bool contains(const APInt &Val) const
Return true if the specified value is in the set.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
static LLVM_ABI 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)...
LLVM_ABI 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...
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
static LLVM_ABI Constant * get(StructType *T, ArrayRef< Constant * > V)
This is an important base class in LLVM.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
static DebugLoc getTemporary()
Implements a dense probed hash-table based set.
static constexpr UpdateKind Delete
static constexpr UpdateKind Insert
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This class represents a freeze function that returns random concrete value if an operand is either a ...
static GEPNoWrapFlags noUnsignedWrap()
void applyUpdatesPermissive(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Module * getParent()
Get the module that this global value is contained inside of...
Type * getValueType() const
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
This instruction inserts a struct field of array element value into an aggregate value.
Value * getInsertedValueOperand()
Value * getAggregateOperand()
unsigned getNumIndices() const
idx_iterator idx_begin() const
Base class for instruction visitors.
void visit(Iterator Start, Iterator End)
LLVM_ABI void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
LLVM_ABI bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
LLVM_ABI void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
LLVM_ABI bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
LLVM_ABI BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
LLVM_ABI void setNonNeg(bool b=true)
Set or clear the nneg flag on this instruction, which must be a zext instruction.
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
LLVM_ABI 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.
LLVM_ABI void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
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.
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.
LLVM_ABI std::optional< PredicateConstraint > getConstraint() const
Fetch condition in the form of PredicateConstraint, if possible.
Return a value (possibly void), from a function.
Helper class for SCCPSolver.
const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals() const
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 DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals() const
const ValueLatticeElement & getLatticeValueFor(Value *V) const
void removeLatticeValueFor(Value *V)
void trackValueOfArgument(Argument *A)
void visitCallInst(CallInst &I)
void markOverdefined(Value *V)
bool isArgumentTrackedFunction(Function *F)
void addTrackedFunction(Function *F)
void solveWhileResolvedUndefs()
void solveWhileResolvedUndefsIn(Module &M)
void trackValueOfGlobalVariable(GlobalVariable *GV)
Constant * getConstantOrNull(Value *V) const
void removeSSACopies(Function &F)
const SmallPtrSet< Function *, 16 > & getMRVFunctionsTracked() const
const SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions() const
void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
ValueLatticeElement getArgAttributeVL(Argument *A)
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
const DataLayout & getDataLayout() const
SCCPSolver - This interface class is a general purpose solver for Sparse Conditional Constant Propaga...
LLVM_ABI void visitCall(CallInst &I)
LLVM_ABI void resetLatticeValueFor(CallBase *Call)
Invalidate the Lattice Value of Call and its users after specializing the call.
LLVM_ABI void trackValueOfGlobalVariable(GlobalVariable *GV)
trackValueOfGlobalVariable - Clients can use this method to inform the SCCPSolver that it should trac...
LLVM_ABI bool tryToReplaceWithConstant(Value *V)
LLVM_ABI void inferArgAttributes() const
LLVM_ABI bool isStructLatticeConstant(Function *F, StructType *STy)
LLVM_ABI void addPredicateInfo(Function &F, DominatorTree &DT, AssumptionCache &AC)
LLVM_ABI void solve()
Solve - Solve for constants and executable blocks.
LLVM_ABI void visit(Instruction *I)
LLVM_ABI void trackValueOfArgument(Argument *V)
trackValueOfArgument - Mark the specified argument overdefined unless it have range attribute.
LLVM_ABI const DenseMap< GlobalVariable *, ValueLatticeElement > & getTrackedGlobals() const
getTrackedGlobals - Get and return the set of inferred initializers for global variables.
LLVM_ABI void addTrackedFunction(Function *F)
addTrackedFunction - If the SCCP solver is supposed to track calls into and out of the specified func...
LLVM_ABI void solveWhileResolvedUndefsIn(Module &M)
LLVM_ABI const PredicateBase * getPredicateInfoFor(Instruction *I)
LLVM_ABI const SmallPtrSetImpl< Function * > & getArgumentTrackedFunctions() const
LLVM_ABI const SmallPtrSet< Function *, 16 > & getMRVFunctionsTracked() const
getMRVFunctionsTracked - Get the set of functions which return multiple values tracked by the pass.
LLVM_ABI bool resolvedUndefsIn(Function &F)
resolvedUndefsIn - While solving the dataflow for a function, we assume that branches on undef values...
LLVM_ABI const DataLayout & getDataLayout() const
LLVM_ABI void addArgumentTrackedFunction(Function *F)
static LLVM_ABI bool isReplaceableConstant(const ValueLatticeElement &LV)
LLVM_ABI void solveWhileResolvedUndefs()
LLVM_ABI void removeLatticeValueFor(Value *V)
LLVM_ABI std::vector< ValueLatticeElement > getStructLatticeValueFor(Value *V) const
LLVM_ABI Constant * getConstantOrNull(Value *V) const
Return either a Constant or nullptr for a given Value.
LLVM_ABI bool simplifyInstsInBlock(BasicBlock &BB, SmallPtrSetImpl< Value * > &InsertedValues, Statistic &InstRemovedStat, Statistic &InstReplacedStat)
LLVM_ABI 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.
LLVM_ABI const ValueLatticeElement & getLatticeValueFor(Value *V) const
LLVM_ABI void addToMustPreserveReturnsInFunctions(Function *F)
Add function to the list of functions whose return cannot be modified.
LLVM_ABI bool removeNonFeasibleEdges(BasicBlock *BB, DomTreeUpdater &DTU, BasicBlock *&NewUnreachableBB) const
LLVM_ABI bool isBlockExecutable(BasicBlock *BB) const
LLVM_ABI void inferReturnAttributes() const
LLVM_ABI bool markBlockExecutable(BasicBlock *BB)
markBlockExecutable - This method can be used by clients to mark all of the blocks that are known to ...
LLVM_ABI void setLatticeValueForSpecializationArguments(Function *F, const SmallVectorImpl< ArgInfo > &Args)
Set the Lattice Value for the arguments of a specialization F.
static LLVM_ABI bool isConstant(const ValueLatticeElement &LV)
LLVM_ABI const MapVector< Function *, ValueLatticeElement > & getTrackedRetVals() const
getTrackedRetVals - Get the inferred return value map.
LLVM_ABI bool isEdgeFeasible(BasicBlock *From, BasicBlock *To) const
LLVM_ABI bool mustPreserveReturn(Function *F)
Returns true if the return of the given function cannot be modified.
static LLVM_ABI bool isOverdefined(const ValueLatticeElement &LV)
LLVM_ABI void markFunctionUnreachable(Function *F)
Mark all of the blocks in function F non-executable.
LLVM_ABI bool isArgumentTrackedFunction(Function *F)
Returns true if the given function is in the solver's set of argument-tracked functions.
LLVM_ABI SCCPSolver(const DataLayout &DL, std::function< const TargetLibraryInfo &(Function &)> GetTLI, LLVMContext &Ctx)
LLVM_ABI void markOverdefined(Value *V)
markOverdefined - Mark the specified value overdefined.
LLVM_ABI void removeSSACopies(Function &F)
This class represents the LLVM 'select' instruction.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
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.
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
bool 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 UncondBrInst * Create(BasicBlock *Target, InsertPosition InsertBefore=nullptr)
static LLVM_ABI 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
void setMayHaveDifferentProvenance(bool V)
LLVM_ABI 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.
bool isConstantRangeIncludingUndef() const
static ValueLatticeElement getNot(Constant *C)
ConstantRange asConstantRange(unsigned BW, bool UndefAllowed=false) const
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.
static ValueLatticeElement get(Constant *C)
unsigned getNumRangeExtensions() const
Constant * getNotConstant() const
LLVM_ABI ValueLatticeElement intersect(const ValueLatticeElement &Other) const
Combine two sets of facts about the same value into a single set of facts.
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 mayHaveDifferentProvenance() const
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.
LLVM_ABI std::string getNameOrAsOperand() const
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
Represents an op.with.overflow intrinsic.
const ParentTy * getParent() const
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
@ BasicBlock
Various leaf nodes.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
cst_pred_ty< is_lowbit_mask > m_LowBitMask()
Match an integer or vector with only the low bit(s) set.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
bool match(Val *V, const Pattern &P)
auto m_Value()
Match an arbitrary value and ignore it.
cst_pred_ty< is_negated_power2 > m_NegatedPower2()
Match a integer or vector negated power-of-2.
match_combine_or< BinaryOp_match< LHS, RHS, Instruction::Add >, DisjointOr_match< LHS, RHS > > m_AddLike(const LHS &L, const RHS &R)
Match either "add" or "or disjoint".
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
static bool replaceSignedInst(SCCPSolver &Solver, SmallPtrSetImpl< Value * > &InsertedValues, Instruction &Inst)
Try to replace signed instructions with their unsigned equivalent.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
static ConstantRange getRange(Value *Op, SCCPSolver &Solver, const SmallPtrSetImpl< Value * > &InsertedValues)
Helper for getting ranges from Solver.
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...
LLVM_ABI Constant * ConstantFoldCall(const CallBase *Call, Function *F, ArrayRef< Constant * > Operands, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldCall - Attempt to constant fold a call to the specified function with the specified argum...
LLVM_ABI ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
LLVM_ABI bool canConstantFoldCallTo(const CallBase *Call, const Function *F, const TargetLibraryInfo *TLI=nullptr)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
auto dyn_cast_or_null(const Y &Val)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
LLVM_ABI Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
LLVM_ABI bool canReplacePointersInUseIfEqual(const Use &U, const Value *To, const DataLayout &DL)
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI 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.
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
static void propagateImplicitRefFromCall(CallBase *CB)
Helper for propagting !implicit.ref metadata from callee to caller before erasing a call instruction.
LLVM_ABI Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI Value * simplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
@ Sub
Subtraction of integers.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
DWARFExpression::Operation Op
LLVM_ABI 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.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI 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...
BumpPtrAllocatorImpl<> BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
LLVM_ABI Constant * ConstantFoldInstOperands(const Instruction *I, ArrayRef< Constant * > Ops, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, bool AllowNonDeterministic=true)
ConstantFoldInstOperands - Attempt to constant fold an instruction with the specified operands.
@ End
Run the machine verifier once, at the end of the pipeline.
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.
static void inferAttribute(Function *F, unsigned AttrIndex, const ValueLatticeElement &Val)
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)