99void SelectionDAG::DAGNodeDeletedListener::anchor() {}
100void SelectionDAG::DAGNodeInsertedListener::anchor() {}
102#define DEBUG_TYPE "selectiondag"
106 cl::desc(
"Gang up loads and stores generated by inlining of memcpy"));
109 cl::desc(
"Number limit for gluing ld/st of memcpy."),
125 return getValueAPF().bitwiseIsEqual(V);
147 N->getValueType(0).getVectorElementType().getSizeInBits();
148 if (
auto *Op0 = dyn_cast<ConstantSDNode>(
N->getOperand(0))) {
149 SplatVal = Op0->getAPIntValue().
trunc(EltSize);
152 if (
auto *Op0 = dyn_cast<ConstantFPSDNode>(
N->getOperand(0))) {
153 SplatVal = Op0->getValueAPF().bitcastToAPInt().
trunc(EltSize);
158 auto *BV = dyn_cast<BuildVectorSDNode>(
N);
163 unsigned SplatBitSize;
165 unsigned EltSize =
N->getValueType(0).getVectorElementType().getSizeInBits();
170 const bool IsBigEndian =
false;
171 return BV->isConstantSplat(SplatVal, SplatUndef, SplatBitSize, HasUndefs,
172 EltSize, IsBigEndian) &&
173 EltSize == SplatBitSize;
182 N =
N->getOperand(0).getNode();
191 unsigned i = 0, e =
N->getNumOperands();
194 while (i != e &&
N->getOperand(i).isUndef())
198 if (i == e)
return false;
209 unsigned EltSize =
N->getValueType(0).getScalarSizeInBits();
211 if (CN->getAPIntValue().countr_one() < EltSize)
214 if (CFPN->getValueAPF().bitcastToAPInt().countr_one() < EltSize)
222 for (++i; i != e; ++i)
223 if (
N->getOperand(i) != NotZero && !
N->getOperand(i).isUndef())
231 N =
N->getOperand(0).getNode();
240 bool IsAllUndef =
true;
253 unsigned EltSize =
N->getValueType(0).getScalarSizeInBits();
255 if (CN->getAPIntValue().countr_zero() < EltSize)
258 if (CFPN->getValueAPF().bitcastToAPInt().countr_zero() < EltSize)
285 if (!isa<ConstantSDNode>(
Op))
298 if (!isa<ConstantFPSDNode>(
Op))
306 assert(
N->getValueType(0).isVector() &&
"Expected a vector!");
308 unsigned EltSize =
N->getValueType(0).getScalarSizeInBits();
309 if (EltSize <= NewEltSize)
313 return (
N->getOperand(0).getValueType().getScalarSizeInBits() <=
318 return (
N->getOperand(0).getValueType().getScalarSizeInBits() <=
328 if (!isa<ConstantSDNode>(
Op))
331 APInt C =
Op->getAsAPIntVal().trunc(EltSize);
332 if (
Signed &&
C.trunc(NewEltSize).sext(EltSize) !=
C)
334 if (!
Signed &&
C.trunc(NewEltSize).zext(EltSize) !=
C)
345 if (
N->getNumOperands() == 0)
351 return N->getOpcode() ==
ISD::FREEZE &&
N->getOperand(0).isUndef();
354template <
typename ConstNodeType>
356 std::function<
bool(ConstNodeType *)>
Match,
359 if (
auto *
C = dyn_cast<ConstNodeType>(
Op))
367 EVT SVT =
Op.getValueType().getScalarType();
369 if (AllowUndefs &&
Op.getOperand(i).isUndef()) {
375 auto *Cst = dyn_cast<ConstNodeType>(
Op.getOperand(i));
376 if (!Cst || Cst->getValueType(0) != SVT || !
Match(Cst))
382template bool ISD::matchUnaryPredicateImpl<ConstantSDNode>(
384template bool ISD::matchUnaryPredicateImpl<ConstantFPSDNode>(
390 bool AllowUndefs,
bool AllowTypeMismatch) {
391 if (!AllowTypeMismatch &&
LHS.getValueType() !=
RHS.getValueType())
395 if (
auto *LHSCst = dyn_cast<ConstantSDNode>(
LHS))
396 if (
auto *RHSCst = dyn_cast<ConstantSDNode>(
RHS))
397 return Match(LHSCst, RHSCst);
400 if (
LHS.getOpcode() !=
RHS.getOpcode() ||
405 EVT SVT =
LHS.getValueType().getScalarType();
406 for (
unsigned i = 0, e =
LHS.getNumOperands(); i != e; ++i) {
409 bool LHSUndef = AllowUndefs && LHSOp.
isUndef();
410 bool RHSUndef = AllowUndefs && RHSOp.
isUndef();
411 auto *LHSCst = dyn_cast<ConstantSDNode>(LHSOp);
412 auto *RHSCst = dyn_cast<ConstantSDNode>(RHSOp);
413 if ((!LHSCst && !LHSUndef) || (!RHSCst && !RHSUndef))
415 if (!AllowTypeMismatch && (LHSOp.
getValueType() != SVT ||
418 if (!
Match(LHSCst, RHSCst))
425 switch (VecReduceOpcode) {
430 case ISD::VP_REDUCE_FADD:
431 case ISD::VP_REDUCE_SEQ_FADD:
435 case ISD::VP_REDUCE_FMUL:
436 case ISD::VP_REDUCE_SEQ_FMUL:
439 case ISD::VP_REDUCE_ADD:
442 case ISD::VP_REDUCE_MUL:
445 case ISD::VP_REDUCE_AND:
448 case ISD::VP_REDUCE_OR:
451 case ISD::VP_REDUCE_XOR:
454 case ISD::VP_REDUCE_SMAX:
457 case ISD::VP_REDUCE_SMIN:
460 case ISD::VP_REDUCE_UMAX:
463 case ISD::VP_REDUCE_UMIN:
466 case ISD::VP_REDUCE_FMAX:
469 case ISD::VP_REDUCE_FMIN:
472 case ISD::VP_REDUCE_FMAXIMUM:
475 case ISD::VP_REDUCE_FMINIMUM:
484#define BEGIN_REGISTER_VP_SDNODE(VPSD, ...) \
487#include "llvm/IR/VPIntrinsics.def"
495#define BEGIN_REGISTER_VP_SDNODE(VPSD, ...) case ISD::VPSD:
496#define VP_PROPERTY_BINARYOP return true;
497#define END_REGISTER_VP_SDNODE(VPSD) break;
498#include "llvm/IR/VPIntrinsics.def"
507#define BEGIN_REGISTER_VP_SDNODE(VPSD, ...) case ISD::VPSD:
508#define VP_PROPERTY_REDUCTION(STARTPOS, ...) return true;
509#define END_REGISTER_VP_SDNODE(VPSD) break;
510#include "llvm/IR/VPIntrinsics.def"
520#define BEGIN_REGISTER_VP_SDNODE(VPSD, LEGALPOS, TDNAME, MASKPOS, ...) \
523#include "llvm/IR/VPIntrinsics.def"
532#define BEGIN_REGISTER_VP_SDNODE(VPSD, LEGALPOS, TDNAME, MASKPOS, EVLPOS) \
535#include "llvm/IR/VPIntrinsics.def"
545#define BEGIN_REGISTER_VP_SDNODE(VPOPC, ...) case ISD::VPOPC:
546#define VP_PROPERTY_FUNCTIONAL_SDOPC(SDOPC) return ISD::SDOPC;
547#define END_REGISTER_VP_SDNODE(VPOPC) break;
548#include "llvm/IR/VPIntrinsics.def"
557#define BEGIN_REGISTER_VP_SDNODE(VPOPC, ...) break;
558#define VP_PROPERTY_FUNCTIONAL_SDOPC(SDOPC) case ISD::SDOPC:
559#define END_REGISTER_VP_SDNODE(VPOPC) return ISD::VPOPC;
560#include "llvm/IR/VPIntrinsics.def"
607 bool isIntegerLike) {
632 bool IsInteger =
Type.isInteger();
637 unsigned Op = Op1 | Op2;
653 bool IsInteger =
Type.isInteger();
688 ID.AddPointer(VTList.
VTs);
694 for (
const auto &
Op : Ops) {
695 ID.AddPointer(
Op.getNode());
696 ID.AddInteger(
Op.getResNo());
703 for (
const auto &
Op : Ops) {
704 ID.AddPointer(
Op.getNode());
705 ID.AddInteger(
Op.getResNo());
718 switch (
N->getOpcode()) {
727 ID.AddPointer(
C->getConstantIntValue());
728 ID.AddBoolean(
C->isOpaque());
733 ID.AddPointer(cast<ConstantFPSDNode>(
N)->getConstantFPValue());
749 ID.AddInteger(cast<RegisterSDNode>(
N)->
getReg());
752 ID.AddPointer(cast<RegisterMaskSDNode>(
N)->getRegMask());
755 ID.AddPointer(cast<SrcValueSDNode>(
N)->getValue());
759 ID.AddInteger(cast<FrameIndexSDNode>(
N)->getIndex());
763 if (cast<LifetimeSDNode>(
N)->hasOffset()) {
764 ID.AddInteger(cast<LifetimeSDNode>(
N)->
getSize());
769 ID.AddInteger(cast<PseudoProbeSDNode>(
N)->getGuid());
770 ID.AddInteger(cast<PseudoProbeSDNode>(
N)->getIndex());
771 ID.AddInteger(cast<PseudoProbeSDNode>(
N)->getAttributes());
775 ID.AddInteger(cast<JumpTableSDNode>(
N)->getIndex());
776 ID.AddInteger(cast<JumpTableSDNode>(
N)->getTargetFlags());
781 ID.AddInteger(CP->getAlign().value());
782 ID.AddInteger(CP->getOffset());
783 if (CP->isMachineConstantPoolEntry())
784 CP->getMachineCPVal()->addSelectionDAGCSEId(
ID);
786 ID.AddPointer(CP->getConstVal());
787 ID.AddInteger(CP->getTargetFlags());
799 ID.AddInteger(LD->getMemoryVT().getRawBits());
800 ID.AddInteger(LD->getRawSubclassData());
801 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
802 ID.AddInteger(LD->getMemOperand()->getFlags());
807 ID.AddInteger(ST->getMemoryVT().getRawBits());
808 ID.AddInteger(ST->getRawSubclassData());
809 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
810 ID.AddInteger(ST->getMemOperand()->getFlags());
821 case ISD::VP_STORE: {
829 case ISD::EXPERIMENTAL_VP_STRIDED_LOAD: {
836 case ISD::EXPERIMENTAL_VP_STRIDED_STORE: {
843 case ISD::VP_GATHER: {
851 case ISD::VP_SCATTER: {
940 if (
auto *MN = dyn_cast<MemIntrinsicSDNode>(
N)) {
941 ID.AddInteger(MN->getRawSubclassData());
942 ID.AddInteger(MN->getPointerInfo().getAddrSpace());
943 ID.AddInteger(MN->getMemOperand()->getFlags());
944 ID.AddInteger(MN->getMemoryVT().getRawBits());
967 if (
N->getValueType(0) == MVT::Glue)
970 switch (
N->getOpcode()) {
978 for (
unsigned i = 1, e =
N->getNumValues(); i != e; ++i)
979 if (
N->getValueType(i) == MVT::Glue)
996 if (Node.use_empty())
1011 while (!DeadNodes.
empty()) {
1020 DUL->NodeDeleted(
N,
nullptr);
1023 RemoveNodeFromCSEMaps(
N);
1054 RemoveNodeFromCSEMaps(
N);
1058 DeleteNodeNotInCSEMaps(
N);
1061void SelectionDAG::DeleteNodeNotInCSEMaps(
SDNode *
N) {
1062 assert(
N->getIterator() != AllNodes.begin() &&
1063 "Cannot delete the entry node!");
1064 assert(
N->use_empty() &&
"Cannot delete a node that is not dead!");
1073 assert(!(V->isVariadic() && isParameter));
1075 ByvalParmDbgValues.push_back(V);
1077 DbgValues.push_back(V);
1078 for (
const SDNode *Node : V->getSDNodes())
1080 DbgValMap[Node].push_back(V);
1085 if (
I == DbgValMap.end())
1087 for (
auto &Val:
I->second)
1088 Val->setIsInvalidated();
1092void SelectionDAG::DeallocateNode(
SDNode *
N) {
1116 switch (
N->getOpcode()) {
1122 EVT VT =
N->getValueType(0);
1123 assert(
N->getNumValues() == 1 &&
"Too many results!");
1125 "Wrong return type!");
1126 assert(
N->getNumOperands() == 2 &&
"Wrong number of operands!");
1127 assert(
N->getOperand(0).getValueType() ==
N->getOperand(1).getValueType() &&
1128 "Mismatched operand types!");
1130 "Wrong operand type!");
1132 "Wrong return type size");
1136 assert(
N->getNumValues() == 1 &&
"Too many results!");
1137 assert(
N->getValueType(0).isVector() &&
"Wrong return type!");
1138 assert(
N->getNumOperands() ==
N->getValueType(0).getVectorNumElements() &&
1139 "Wrong number of operands!");
1140 EVT EltVT =
N->getValueType(0).getVectorElementType();
1142 assert((
Op.getValueType() == EltVT ||
1143 (EltVT.
isInteger() &&
Op.getValueType().isInteger() &&
1144 EltVT.
bitsLE(
Op.getValueType()))) &&
1145 "Wrong operand type!");
1146 assert(
Op.getValueType() ==
N->getOperand(0).getValueType() &&
1147 "Operands must all have the same type");
1159void SelectionDAG::InsertNode(
SDNode *
N) {
1160 AllNodes.push_back(
N);
1162 N->PersistentId = NextPersistentId++;
1165 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1166 DUL->NodeInserted(
N);
1173bool SelectionDAG::RemoveNodeFromCSEMaps(
SDNode *
N) {
1174 bool Erased =
false;
1175 switch (
N->getOpcode()) {
1178 assert(CondCodeNodes[cast<CondCodeSDNode>(
N)->
get()] &&
1179 "Cond code doesn't exist!");
1180 Erased = CondCodeNodes[cast<CondCodeSDNode>(
N)->get()] !=
nullptr;
1181 CondCodeNodes[cast<CondCodeSDNode>(
N)->get()] =
nullptr;
1184 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(
N)->getSymbol());
1188 Erased = TargetExternalSymbols.erase(std::pair<std::string, unsigned>(
1193 auto *MCSN = cast<MCSymbolSDNode>(
N);
1194 Erased = MCSymbols.erase(MCSN->getMCSymbol());
1198 EVT VT = cast<VTSDNode>(
N)->getVT();
1200 Erased = ExtendedValueTypeNodes.erase(VT);
1211 Erased = CSEMap.RemoveNode(
N);
1218 if (!Erased &&
N->getValueType(
N->getNumValues()-1) != MVT::Glue &&
1233SelectionDAG::AddModifiedNodeToCSEMaps(
SDNode *
N) {
1237 SDNode *Existing = CSEMap.GetOrInsertNode(
N);
1238 if (Existing !=
N) {
1246 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1247 DUL->NodeDeleted(
N, Existing);
1248 DeleteNodeNotInCSEMaps(
N);
1254 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1255 DUL->NodeUpdated(
N);
1273 Node->intersectFlagsWith(
N->getFlags());
1293 Node->intersectFlagsWith(
N->getFlags());
1311 Node->intersectFlagsWith(
N->getFlags());
1324 : TM(tm), OptLevel(OL), EntryNode(ISD::EntryToken, 0,
DebugLoc(),
1327 InsertNode(&EntryNode);
1338 SDAGISelPass = PassPtr;
1342 LibInfo = LibraryInfo;
1348 FnVarLocs = VarLocs;
1352 assert(!UpdateListeners &&
"Dangling registered DAGUpdateListeners");
1354 OperandRecycler.clear(OperandAllocator);
1363void SelectionDAG::allnodes_clear() {
1364 assert(&*AllNodes.begin() == &EntryNode);
1365 AllNodes.remove(AllNodes.begin());
1366 while (!AllNodes.empty())
1367 DeallocateNode(&AllNodes.front());
1369 NextPersistentId = 0;
1375 SDNode *
N = CSEMap.FindNodeOrInsertPos(
ID, InsertPos);
1377 switch (
N->getOpcode()) {
1382 "debug location. Use another overload.");
1389 const SDLoc &
DL,
void *&InsertPos) {
1390 SDNode *
N = CSEMap.FindNodeOrInsertPos(
ID, InsertPos);
1392 switch (
N->getOpcode()) {
1398 if (
N->getDebugLoc() !=
DL.getDebugLoc())
1405 if (
DL.getIROrder() &&
DL.getIROrder() <
N->getIROrder())
1406 N->setDebugLoc(
DL.getDebugLoc());
1415 OperandRecycler.clear(OperandAllocator);
1416 OperandAllocator.
Reset();
1419 ExtendedValueTypeNodes.clear();
1420 ExternalSymbols.clear();
1421 TargetExternalSymbols.clear();
1424 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
nullptr);
1425 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
nullptr);
1427 EntryNode.UseList =
nullptr;
1428 InsertNode(&EntryNode);
1434 return VT.
bitsGT(
Op.getValueType())
1440std::pair<SDValue, SDValue>
1444 "Strict no-op FP extend/round not allowed.");
1451 return std::pair<SDValue, SDValue>(Res,
SDValue(Res.
getNode(), 1));
1455 return VT.
bitsGT(
Op.getValueType()) ?
1461 return VT.
bitsGT(
Op.getValueType()) ?
1467 return VT.
bitsGT(
Op.getValueType()) ?
1475 auto Type =
Op.getValueType();
1479 auto Size =
Op.getValueSizeInBits();
1490 auto Type =
Op.getValueType();
1494 auto Size =
Op.getValueSizeInBits();
1505 auto Type =
Op.getValueType();
1509 auto Size =
Op.getValueSizeInBits();
1527 EVT OpVT =
Op.getValueType();
1529 "Cannot getZeroExtendInReg FP types");
1531 "getZeroExtendInReg type should be vector iff the operand "
1535 "Vector element counts must match in getZeroExtendInReg");
1547 EVT OpVT =
Op.getValueType();
1549 "Cannot getVPZeroExtendInReg FP types");
1551 "getVPZeroExtendInReg type and operand type should be vector!");
1553 "Vector element counts must match in getZeroExtendInReg");
1592 return getNode(ISD::VP_XOR,
DL, VT, Val, TrueValue, Mask, EVL);
1603 return getNode(ISD::VP_ZERO_EXTEND,
DL, VT,
Op, Mask, EVL);
1605 return getNode(ISD::VP_TRUNCATE,
DL, VT,
Op, Mask, EVL);
1625 bool isT,
bool isO) {
1629 "getConstant with a uint64_t value that doesn't fit in the type!");
1634 bool isT,
bool isO) {
1635 return getConstant(*ConstantInt::get(*Context, Val),
DL, VT, isT, isO);
1639 EVT VT,
bool isT,
bool isO) {
1657 Elt = ConstantInt::get(*
getContext(), NewVal);
1676 "Can only handle an even split!");
1680 for (
unsigned i = 0; i != Parts; ++i)
1682 NewVal.
extractBits(ViaEltSizeInBits, i * ViaEltSizeInBits),
DL,
1683 ViaEltVT, isT, isO));
1688 unsigned ViaVecNumElts = VT.
getSizeInBits() / ViaEltSizeInBits;
1699 NewVal.
extractBits(ViaEltSizeInBits, i * ViaEltSizeInBits),
DL,
1700 ViaEltVT, isT, isO));
1705 std::reverse(EltParts.
begin(), EltParts.
end());
1724 "APInt size does not match type size!");
1733 if ((
N = FindNodeOrInsertPos(
ID,
DL, IP)))
1738 N = newSDNode<ConstantSDNode>(isT, isO, Elt, VTs);
1739 CSEMap.InsertNode(
N, IP);
1751 bool isT,
bool isO) {
1755 "getSignedConstant with a int64_t value that doesn't fit in the type!");
1762 IsTarget, IsOpaque);
1794 EVT VT,
bool isTarget) {
1809 if ((
N = FindNodeOrInsertPos(
ID,
DL, IP)))
1814 N = newSDNode<ConstantFPSDNode>(isTarget, &V, VTs);
1815 CSEMap.InsertNode(
N, IP);
1829 if (EltVT == MVT::f32)
1831 if (EltVT == MVT::f64)
1833 if (EltVT == MVT::f80 || EltVT == MVT::f128 || EltVT == MVT::ppcf128 ||
1834 EltVT == MVT::f16 || EltVT == MVT::bf16) {
1845 EVT VT, int64_t
Offset,
bool isTargetGA,
1846 unsigned TargetFlags) {
1847 assert((TargetFlags == 0 || isTargetGA) &&
1848 "Cannot set target flags on target-independent globals");
1866 ID.AddInteger(TargetFlags);
1868 if (
SDNode *E = FindNodeOrInsertPos(
ID,
DL, IP))
1871 auto *
N = newSDNode<GlobalAddressSDNode>(
1872 Opc,
DL.getIROrder(),
DL.getDebugLoc(), GV, VTs,
Offset, TargetFlags);
1873 CSEMap.InsertNode(
N, IP);
1885 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
1888 auto *
N = newSDNode<FrameIndexSDNode>(FI, VTs, isTarget);
1889 CSEMap.InsertNode(
N, IP);
1895 unsigned TargetFlags) {
1896 assert((TargetFlags == 0 || isTarget) &&
1897 "Cannot set target flags on target-independent jump tables");
1903 ID.AddInteger(TargetFlags);
1905 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
1908 auto *
N = newSDNode<JumpTableSDNode>(JTI, VTs, isTarget, TargetFlags);
1909 CSEMap.InsertNode(
N, IP);
1923 bool isTarget,
unsigned TargetFlags) {
1924 assert((TargetFlags == 0 || isTarget) &&
1925 "Cannot set target flags on target-independent globals");
1934 ID.AddInteger(Alignment->value());
1937 ID.AddInteger(TargetFlags);
1939 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
1942 auto *
N = newSDNode<ConstantPoolSDNode>(isTarget,
C, VTs,
Offset, *Alignment,
1944 CSEMap.InsertNode(
N, IP);
1953 bool isTarget,
unsigned TargetFlags) {
1954 assert((TargetFlags == 0 || isTarget) &&
1955 "Cannot set target flags on target-independent globals");
1962 ID.AddInteger(Alignment->value());
1964 C->addSelectionDAGCSEId(
ID);
1965 ID.AddInteger(TargetFlags);
1967 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
1970 auto *
N = newSDNode<ConstantPoolSDNode>(isTarget,
C, VTs,
Offset, *Alignment,
1972 CSEMap.InsertNode(
N, IP);
1982 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
1985 auto *
N = newSDNode<BasicBlockSDNode>(
MBB);
1986 CSEMap.InsertNode(
N, IP);
1993 ValueTypeNodes.size())
2000 N = newSDNode<VTSDNode>(VT);
2008 N = newSDNode<ExternalSymbolSDNode>(
false,
Sym, 0,
getVTList(VT));
2023 unsigned TargetFlags) {
2025 TargetExternalSymbols[std::pair<std::string, unsigned>(
Sym, TargetFlags)];
2027 N = newSDNode<ExternalSymbolSDNode>(
true,
Sym, TargetFlags,
getVTList(VT));
2033 if ((
unsigned)
Cond >= CondCodeNodes.size())
2034 CondCodeNodes.resize(
Cond+1);
2036 if (!CondCodeNodes[
Cond]) {
2037 auto *
N = newSDNode<CondCodeSDNode>(
Cond);
2038 CondCodeNodes[
Cond] =
N;
2046 bool ConstantFold) {
2048 "APInt size does not match type size!");
2065 bool ConstantFold) {
2066 if (EC.isScalable())
2079 const APInt &StepVal) {
2103 "Must have the same number of vector elements as mask elements!");
2105 "Invalid VECTOR_SHUFFLE");
2113 int NElts = Mask.size();
2115 [&](
int M) {
return M < (NElts * 2) && M >= -1; }) &&
2116 "Index out of range");
2124 for (
int i = 0; i != NElts; ++i)
2125 if (MaskVec[i] >= NElts) MaskVec[i] -= NElts;
2141 for (
int i = 0; i < NElts; ++i) {
2142 if (MaskVec[i] <
Offset || MaskVec[i] >= (
Offset + NElts))
2146 if (UndefElements[MaskVec[i] -
Offset]) {
2152 if (!UndefElements[i])
2156 if (
auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
2157 BlendSplat(N1BV, 0);
2158 if (
auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
2159 BlendSplat(N2BV, NElts);
2164 bool AllLHS =
true, AllRHS =
true;
2166 for (
int i = 0; i != NElts; ++i) {
2167 if (MaskVec[i] >= NElts) {
2172 }
else if (MaskVec[i] >= 0) {
2176 if (AllLHS && AllRHS)
2178 if (AllLHS && !N2Undef)
2191 bool Identity =
true, AllSame =
true;
2192 for (
int i = 0; i != NElts; ++i) {
2193 if (MaskVec[i] >= 0 && MaskVec[i] != i) Identity =
false;
2194 if (MaskVec[i] != MaskVec[0]) AllSame =
false;
2196 if (Identity && NElts)
2206 V = V->getOperand(0);
2209 if (
auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
2229 if (AllSame && SameNumElts) {
2230 EVT BuildVT = BV->getValueType(0);
2247 for (
int i = 0; i != NElts; ++i)
2248 ID.AddInteger(MaskVec[i]);
2251 if (
SDNode *E = FindNodeOrInsertPos(
ID, dl, IP))
2257 int *MaskAlloc = OperandAllocator.
Allocate<
int>(NElts);
2260 auto *
N = newSDNode<ShuffleVectorSDNode>(VTs, dl.
getIROrder(),
2262 createOperands(
N, Ops);
2264 CSEMap.InsertNode(
N, IP);
2285 ID.AddInteger(RegNo);
2287 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
2290 auto *
N = newSDNode<RegisterSDNode>(RegNo, VTs);
2292 CSEMap.InsertNode(
N, IP);
2300 ID.AddPointer(RegMask);
2302 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
2305 auto *
N = newSDNode<RegisterMaskSDNode>(RegMask);
2306 CSEMap.InsertNode(
N, IP);
2321 ID.AddPointer(Label);
2323 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
2328 createOperands(
N, Ops);
2330 CSEMap.InsertNode(
N, IP);
2336 int64_t
Offset,
bool isTarget,
2337 unsigned TargetFlags) {
2345 ID.AddInteger(TargetFlags);
2347 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
2350 auto *
N = newSDNode<BlockAddressSDNode>(Opc, VTs, BA,
Offset, TargetFlags);
2351 CSEMap.InsertNode(
N, IP);
2362 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
2365 auto *
N = newSDNode<SrcValueSDNode>(V);
2366 CSEMap.InsertNode(
N, IP);
2377 if (
SDNode *E = FindNodeOrInsertPos(
ID, IP))
2380 auto *
N = newSDNode<MDNodeSDNode>(MD);
2381 CSEMap.InsertNode(
N, IP);
2387 if (VT == V.getValueType())
2394 unsigned SrcAS,
unsigned DestAS) {
2399 ID.AddInteger(SrcAS);
2400 ID.AddInteger(DestAS);
2403 if (
SDNode *E = FindNodeOrInsertPos(
ID, dl, IP))
2407 VTs, SrcAS, DestAS);
2408 createOperands(
N, Ops);
2410 CSEMap.InsertNode(
N, IP);
2422 EVT OpTy =
Op.getValueType();
2424 if (OpTy == ShTy || OpTy.
isVector())
return Op;
2432 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
2433 EVT VT = Node->getValueType(0);
2434 SDValue Tmp1 = Node->getOperand(0);
2435 SDValue Tmp2 = Node->getOperand(1);
2436 const MaybeAlign MA(Node->getConstantOperandVal(3));
2468 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
2469 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
2480 Align RedAlign = UseABI ?
DL.getABITypeAlign(Ty) :
DL.getPrefTypeAlign(Ty);
2490 if (RedAlign > StackAlign) {
2493 unsigned NumIntermediates;
2495 NumIntermediates, RegisterVT);
2497 Align RedAlign2 = UseABI ?
DL.getABITypeAlign(Ty) :
DL.getPrefTypeAlign(Ty);
2498 if (RedAlign2 < RedAlign)
2499 RedAlign = RedAlign2;
2504 RedAlign = std::min(RedAlign, StackAlign);
2519 false,
nullptr, StackID);
2534 "Don't know how to choose the maximum size when creating a stack "
2543 Align Align = std::max(
DL.getPrefTypeAlign(Ty1),
DL.getPrefTypeAlign(Ty2));
2551 auto GetUndefBooleanConstant = [&]() {
2590 return GetUndefBooleanConstant();
2595 return GetUndefBooleanConstant();
2604 const APInt &C2 = N2C->getAPIntValue();
2606 const APInt &C1 = N1C->getAPIntValue();
2613 auto *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
2614 auto *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
2616 if (N1CFP && N2CFP) {
2621 return GetUndefBooleanConstant();
2626 return GetUndefBooleanConstant();
2632 return GetUndefBooleanConstant();
2637 return GetUndefBooleanConstant();
2642 return GetUndefBooleanConstant();
2648 return GetUndefBooleanConstant();
2677 return getSetCC(dl, VT, N2, N1, SwappedCond);
2678 }
else if ((N2CFP && N2CFP->getValueAPF().isNaN()) ||
2693 return GetUndefBooleanConstant();
2704 unsigned BitWidth =
Op.getScalarValueSizeInBits();
2712 unsigned Depth)
const {
2720 const APInt &DemandedElts,
2721 unsigned Depth)
const {
2728 unsigned Depth )
const {
2734 unsigned Depth)
const {
2739 const APInt &DemandedElts,
2740 unsigned Depth)
const {
2741 EVT VT =
Op.getValueType();
2748 for (
unsigned EltIdx = 0; EltIdx != NumElts; ++EltIdx) {
2749 if (!DemandedElts[EltIdx])
2753 KnownZeroElements.
setBit(EltIdx);
2755 return KnownZeroElements;
2765 unsigned Opcode = V.getOpcode();
2766 EVT VT = V.getValueType();
2769 "scalable demanded bits are ignored");
2781 UndefElts = V.getOperand(0).isUndef()
2790 APInt UndefLHS, UndefRHS;
2795 UndefElts = UndefLHS | UndefRHS;
2825 for (
unsigned i = 0; i != NumElts; ++i) {
2831 if (!DemandedElts[i])
2833 if (Scl && Scl !=
Op)
2843 ArrayRef<int> Mask = cast<ShuffleVectorSDNode>(V)->getMask();
2844 for (
int i = 0; i != (int)NumElts; ++i) {
2850 if (!DemandedElts[i])
2852 if (M < (
int)NumElts)
2855 DemandedRHS.
setBit(M - NumElts);
2867 auto CheckSplatSrc = [&](
SDValue Src,
const APInt &SrcElts) {
2869 return (SrcElts.popcount() == 1) ||
2871 (SrcElts & SrcUndefs).
isZero());
2873 if (!DemandedLHS.
isZero())
2874 return CheckSplatSrc(V.getOperand(0), DemandedLHS);
2875 return CheckSplatSrc(V.getOperand(1), DemandedRHS);
2879 SDValue Src = V.getOperand(0);
2881 if (Src.getValueType().isScalableVector())
2884 unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
2897 SDValue Src = V.getOperand(0);
2899 if (Src.getValueType().isScalableVector())
2901 unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
2903 APInt DemandedSrcElts = DemandedElts.
zext(NumSrcElts);
2905 UndefElts = UndefSrcElts.
trunc(NumElts);
2911 SDValue Src = V.getOperand(0);
2912 EVT SrcVT = Src.getValueType();
2922 if ((
BitWidth % SrcBitWidth) == 0) {
2924 unsigned Scale =
BitWidth / SrcBitWidth;
2926 APInt ScaledDemandedElts =
2928 for (
unsigned I = 0;
I != Scale; ++
I) {
2932 SubDemandedElts &= ScaledDemandedElts;
2936 if (!SubUndefElts.
isZero())
2950 EVT VT = V.getValueType();
2960 (AllowUndefs || !UndefElts);
2966 EVT VT = V.getValueType();
2967 unsigned Opcode = V.getOpcode();
2988 SplatIdx = (UndefElts & DemandedElts).
countr_one();
3002 auto *SVN = cast<ShuffleVectorSDNode>(V);
3003 if (!SVN->isSplat())
3005 int Idx = SVN->getSplatIndex();
3006 int NumElts = V.getValueType().getVectorNumElements();
3007 SplatIdx =
Idx % NumElts;
3008 return V.getOperand(
Idx / NumElts);
3024 if (LegalSVT.
bitsLT(SVT))
3033std::optional<ConstantRange>
3035 unsigned Depth)
const {
3038 "Unknown shift node");
3040 unsigned BitWidth = V.getScalarValueSizeInBits();
3042 if (
auto *Cst = dyn_cast<ConstantSDNode>(V.getOperand(1))) {
3043 const APInt &ShAmt = Cst->getAPIntValue();
3045 return std::nullopt;
3049 if (
auto *BV = dyn_cast<BuildVectorSDNode>(V.getOperand(1))) {
3050 const APInt *MinAmt =
nullptr, *MaxAmt =
nullptr;
3051 for (
unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) {
3052 if (!DemandedElts[i])
3054 auto *SA = dyn_cast<ConstantSDNode>(BV->getOperand(i));
3056 MinAmt = MaxAmt =
nullptr;
3059 const APInt &ShAmt = SA->getAPIntValue();
3061 return std::nullopt;
3062 if (!MinAmt || MinAmt->
ugt(ShAmt))
3064 if (!MaxAmt || MaxAmt->ult(ShAmt))
3067 assert(((!MinAmt && !MaxAmt) || (MinAmt && MaxAmt)) &&
3068 "Failed to find matching min/max shift amounts");
3069 if (MinAmt && MaxAmt)
3079 return std::nullopt;
3082std::optional<uint64_t>
3084 unsigned Depth)
const {
3087 "Unknown shift node");
3088 if (std::optional<ConstantRange> AmtRange =
3090 if (
const APInt *ShAmt = AmtRange->getSingleElement())
3091 return ShAmt->getZExtValue();
3092 return std::nullopt;
3095std::optional<uint64_t>
3097 EVT VT = V.getValueType();
3104std::optional<uint64_t>
3106 unsigned Depth)
const {
3109 "Unknown shift node");
3110 if (std::optional<ConstantRange> AmtRange =
3112 return AmtRange->getUnsignedMin().getZExtValue();
3113 return std::nullopt;
3116std::optional<uint64_t>
3118 EVT VT = V.getValueType();
3125std::optional<uint64_t>
3127 unsigned Depth)
const {
3130 "Unknown shift node");
3131 if (std::optional<ConstantRange> AmtRange =
3133 return AmtRange->getUnsignedMax().getZExtValue();
3134 return std::nullopt;
3137std::optional<uint64_t>
3139 EVT VT = V.getValueType();
3150 EVT VT =
Op.getValueType();
3165 unsigned Depth)
const {
3166 unsigned BitWidth =
Op.getScalarValueSizeInBits();
3170 if (
auto *
C = dyn_cast<ConstantSDNode>(
Op)) {
3174 if (
auto *
C = dyn_cast<ConstantFPSDNode>(
Op)) {
3184 assert((!
Op.getValueType().isFixedLengthVector() ||
3185 NumElts ==
Op.getValueType().getVectorNumElements()) &&
3186 "Unexpected vector size");
3191 unsigned Opcode =
Op.getOpcode();
3199 "Expected SPLAT_VECTOR implicit truncation");
3206 unsigned ScalarSize =
Op.getOperand(0).getScalarValueSizeInBits();
3208 "Expected SPLAT_VECTOR_PARTS scalars to cover element width");
3215 const APInt &Step =
Op.getConstantOperandAPInt(0);
3224 const APInt MinNumElts =
3230 .
umul_ov(MinNumElts, Overflow);
3234 const APInt MaxValue = (MaxNumElts - 1).
umul_ov(Step, Overflow);
3242 assert(!
Op.getValueType().isScalableVector());
3246 if (!DemandedElts[i])
3255 "Expected BUILD_VECTOR implicit truncation");
3268 assert(!
Op.getValueType().isScalableVector());
3271 APInt DemandedLHS, DemandedRHS;
3275 DemandedLHS, DemandedRHS))
3280 if (!!DemandedLHS) {
3288 if (!!DemandedRHS) {
3297 const APInt &Multiplier =
Op.getConstantOperandAPInt(0);
3302 if (
Op.getValueType().isScalableVector())
3306 EVT SubVectorVT =
Op.getOperand(0).getValueType();
3309 for (
unsigned i = 0; i != NumSubVectors; ++i) {
3311 DemandedElts.
extractBits(NumSubVectorElts, i * NumSubVectorElts);
3312 if (!!DemandedSub) {
3324 if (
Op.getValueType().isScalableVector())
3333 APInt DemandedSrcElts = DemandedElts;
3338 if (!!DemandedSubElts) {
3343 if (!!DemandedSrcElts) {
3353 if (
Op.getValueType().isScalableVector() || Src.getValueType().isScalableVector())
3356 unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
3362 if (
Op.getValueType().isScalableVector())
3366 if (DemandedElts != 1)
3377 if (
Op.getValueType().isScalableVector())
3397 if ((
BitWidth % SubBitWidth) == 0) {
3404 unsigned SubScale =
BitWidth / SubBitWidth;
3405 APInt SubDemandedElts(NumElts * SubScale, 0);
3406 for (
unsigned i = 0; i != NumElts; ++i)
3407 if (DemandedElts[i])
3408 SubDemandedElts.
setBit(i * SubScale);
3410 for (
unsigned i = 0; i != SubScale; ++i) {
3413 unsigned Shifts = IsLE ? i : SubScale - 1 - i;
3414 Known.
insertBits(Known2, SubBitWidth * Shifts);
3419 if ((SubBitWidth %
BitWidth) == 0) {
3420 assert(
Op.getValueType().isVector() &&
"Expected bitcast to vector");
3425 unsigned SubScale = SubBitWidth /
BitWidth;
3426 APInt SubDemandedElts =
3431 for (
unsigned i = 0; i != NumElts; ++i)
3432 if (DemandedElts[i]) {
3433 unsigned Shifts = IsLE ? i : NumElts - 1 - i;
3464 bool SelfMultiply =
Op.getOperand(0) ==
Op.getOperand(1);
3468 Op.getOperand(0), DemandedElts,
false,
Depth + 1);
3474 if (
Op->getFlags().hasNoSignedWrap() &&
3475 Op.getOperand(0) ==
Op.getOperand(1) &&
3502 unsigned SignBits1 =
3506 unsigned SignBits0 =
3512 assert((
Op.getResNo() == 0 ||
Op.getResNo() == 1) &&
"Unknown result");
3515 bool SelfMultiply =
Op.getOperand(0) ==
Op.getOperand(1);
3516 if (
Op.getResNo() == 0)
3523 assert((
Op.getResNo() == 0 ||
Op.getResNo() == 1) &&
"Unknown result");
3526 bool SelfMultiply =
Op.getOperand(0) ==
Op.getOperand(1);
3527 if (
Op.getResNo() == 0)
3580 if (
Op.getResNo() != 1)
3595 unsigned OpNo =
Op->isStrictFPOpcode() ? 1 : 0;
3607 bool NUW =
Op->getFlags().hasNoUnsignedWrap();
3608 bool NSW =
Op->getFlags().hasNoSignedWrap();
3615 if (std::optional<uint64_t> ShMinAmt =
3624 Op->getFlags().hasExact());
3627 if (std::optional<uint64_t> ShMinAmt =
3635 Op->getFlags().hasExact());
3640 unsigned Amt =
C->getAPIntValue().urem(
BitWidth);
3646 DemandedElts,
Depth + 1);
3671 assert((
Op.getResNo() == 0 ||
Op.getResNo() == 1) &&
"Unknown result");
3674 unsigned LoBits =
Op.getOperand(0).getScalarValueSizeInBits();
3675 unsigned HiBits =
Op.getOperand(1).getScalarValueSizeInBits();
3678 Known = Known2.
concat(Known);
3692 if (
Op.getResNo() == 0)
3700 EVT EVT = cast<VTSDNode>(
Op.getOperand(1))->getVT();
3741 !
Op.getValueType().isScalableVector()) {
3755 for (
unsigned i = 0; i != NumElts; ++i) {
3756 if (!DemandedElts[i])
3759 if (
auto *CInt = dyn_cast<ConstantInt>(Elt)) {
3765 if (
auto *CFP = dyn_cast<ConstantFP>(Elt)) {
3766 APInt Value = CFP->getValueAPF().bitcastToAPInt();
3777 if (
auto *CInt = dyn_cast<ConstantInt>(Cst)) {
3779 }
else if (
auto *CFP = dyn_cast<ConstantFP>(Cst)) {
3785 }
else if (
Op.getResNo() == 0) {
3786 KnownBits Known0(!LD->getMemoryVT().isScalableVT()
3787 ? LD->getMemoryVT().getFixedSizeInBits()
3789 EVT VT =
Op.getValueType();
3796 if (
const MDNode *MD = LD->getRanges()) {
3807 if (LD->getMemoryVT().isVector())
3808 Known0 = Known0.
trunc(LD->getMemoryVT().getScalarSizeInBits());
3825 if (
Op.getValueType().isScalableVector())
3827 EVT InVT =
Op.getOperand(0).getValueType();
3839 if (
Op.getValueType().isScalableVector())
3841 EVT InVT =
Op.getOperand(0).getValueType();
3857 if (
Op.getValueType().isScalableVector())
3859 EVT InVT =
Op.getOperand(0).getValueType();
3876 EVT VT = cast<VTSDNode>(
Op.getOperand(1))->getVT();
3879 Known.
Zero |= (~InMask);
3880 Known.
One &= (~Known.Zero);
3884 unsigned LogOfAlign =
Log2(cast<AssertAlignSDNode>(
Op)->
getAlign());
3904 Op.getOpcode() ==
ISD::ADD, Flags.hasNoSignedWrap(),
3905 Flags.hasNoUnsignedWrap(), Known, Known2);
3912 if (
Op.getResNo() == 1) {
3923 "We only compute knownbits for the difference here.");
3930 Borrow = Borrow.
trunc(1);
3944 if (
Op.getResNo() == 1) {
3955 assert(
Op.getResNo() == 0 &&
"We only compute knownbits for the sum here.");
3965 Carry = Carry.
trunc(1);
4001 const unsigned Index =
Op.getConstantOperandVal(1);
4002 const unsigned EltBitWidth =
Op.getValueSizeInBits();
4009 Known = Known.
trunc(EltBitWidth);
4025 Known = Known.
trunc(EltBitWidth);
4030 auto *ConstEltNo = dyn_cast<ConstantSDNode>(EltNo);
4031 if (ConstEltNo && ConstEltNo->getAPIntValue().ult(NumSrcElts))
4041 if (
Op.getValueType().isScalableVector())
4050 bool DemandedVal =
true;
4051 APInt DemandedVecElts = DemandedElts;
4052 auto *CEltNo = dyn_cast<ConstantSDNode>(EltNo);
4053 if (CEltNo && CEltNo->getAPIntValue().ult(NumElts)) {
4054 unsigned EltIdx = CEltNo->getZExtValue();
4055 DemandedVal = !!DemandedElts[EltIdx];
4064 if (!!DemandedVecElts) {
4082 Known = Known2.
abs();
4115 if (CstLow && CstHigh) {
4120 const APInt &ValueHigh = CstHigh->getAPIntValue();
4121 if (ValueLow.
sle(ValueHigh)) {
4124 unsigned MinSignBits = std::min(LowSignBits, HighSignBits);
4147 if (IsMax && CstLow) {
4171 EVT VT = cast<VTSDNode>(
Op.getOperand(1))->getVT();
4176 if (
Op.getResNo() == 1) {
4203 cast<AtomicSDNode>(
Op)->getMemoryVT().getScalarSizeInBits();
4205 if (
Op.getResNo() == 0) {
4229 if (
Op.getValueType().isScalableVector())