96void SelectionDAG::DAGNodeDeletedListener::anchor() {}
97void SelectionDAG::DAGNodeInsertedListener::anchor() {}
99#define DEBUG_TYPE "selectiondag"
103 cl::desc(
"Gang up loads and stores generated by inlining of memcpy"));
106 cl::desc(
"Number limit for gluing ld/st of memcpy."),
122 return getValueAPF().bitwiseIsEqual(V);
145 N->getValueType(0).getVectorElementType().getSizeInBits();
146 if (
auto *Op0 = dyn_cast<ConstantSDNode>(
N->getOperand(0))) {
147 SplatVal = Op0->getAPIntValue().
trunc(EltSize);
150 if (
auto *Op0 = dyn_cast<ConstantFPSDNode>(
N->getOperand(0))) {
151 SplatVal = Op0->getValueAPF().bitcastToAPInt().
trunc(EltSize);
156 auto *BV = dyn_cast<BuildVectorSDNode>(
N);
161 unsigned SplatBitSize;
163 unsigned EltSize =
N->getValueType(0).getVectorElementType().getSizeInBits();
164 return BV->isConstantSplat(SplatVal, SplatUndef, SplatBitSize, HasUndefs,
166 EltSize == SplatBitSize;
175 N =
N->getOperand(0).getNode();
184 unsigned i = 0, e =
N->getNumOperands();
187 while (i != e &&
N->getOperand(i).isUndef())
191 if (i == e)
return false;
202 unsigned EltSize =
N->getValueType(0).getScalarSizeInBits();
204 if (CN->getAPIntValue().countr_one() < EltSize)
207 if (CFPN->getValueAPF().bitcastToAPInt().countr_one() < EltSize)
215 for (++i; i != e; ++i)
216 if (
N->getOperand(i) != NotZero && !
N->getOperand(i).isUndef())
224 N =
N->getOperand(0).getNode();
233 bool IsAllUndef =
true;
234 for (
const SDValue &Op :
N->op_values()) {
246 unsigned EltSize =
N->getValueType(0).getScalarSizeInBits();
248 if (CN->getAPIntValue().countr_zero() < EltSize)
251 if (CFPN->getValueAPF().bitcastToAPInt().countr_zero() < EltSize)
275 for (
const SDValue &Op :
N->op_values()) {
278 if (!isa<ConstantSDNode>(Op))
288 for (
const SDValue &Op :
N->op_values()) {
291 if (!isa<ConstantFPSDNode>(Op))
299 assert(
N->getValueType(0).isVector() &&
"Expected a vector!");
301 unsigned EltSize =
N->getValueType(0).getScalarSizeInBits();
302 if (EltSize <= NewEltSize)
306 return (
N->getOperand(0).getValueType().getScalarSizeInBits() <=
311 return (
N->getOperand(0).getValueType().getScalarSizeInBits() <=
318 for (
const SDValue &Op :
N->op_values()) {
321 if (!isa<ConstantSDNode>(Op))
324 APInt C = cast<ConstantSDNode>(Op)->getAPIntValue().trunc(EltSize);
325 if (
Signed &&
C.trunc(NewEltSize).sext(EltSize) !=
C)
327 if (!
Signed &&
C.trunc(NewEltSize).zext(EltSize) !=
C)
338 if (
N->getNumOperands() == 0)
340 return all_of(
N->op_values(), [](
SDValue Op) { return Op.isUndef(); });
344 return N->getOpcode() ==
ISD::FREEZE &&
N->getOperand(0).isUndef();
351 if (
auto *Cst = dyn_cast<ConstantSDNode>(Op))
359 EVT SVT = Op.getValueType().getScalarType();
360 for (
unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
361 if (AllowUndefs && Op.getOperand(i).isUndef()) {
367 auto *Cst = dyn_cast<ConstantSDNode>(Op.getOperand(i));
368 if (!Cst || Cst->getValueType(0) != SVT || !
Match(Cst))
377 bool AllowUndefs,
bool AllowTypeMismatch) {
378 if (!AllowTypeMismatch &&
LHS.getValueType() !=
RHS.getValueType())
382 if (
auto *LHSCst = dyn_cast<ConstantSDNode>(
LHS))
383 if (
auto *RHSCst = dyn_cast<ConstantSDNode>(
RHS))
384 return Match(LHSCst, RHSCst);
387 if (
LHS.getOpcode() !=
RHS.getOpcode() ||
392 EVT SVT =
LHS.getValueType().getScalarType();
393 for (
unsigned i = 0, e =
LHS.getNumOperands(); i != e; ++i) {
396 bool LHSUndef = AllowUndefs && LHSOp.
isUndef();
397 bool RHSUndef = AllowUndefs && RHSOp.
isUndef();
398 auto *LHSCst = dyn_cast<ConstantSDNode>(LHSOp);
399 auto *RHSCst = dyn_cast<ConstantSDNode>(RHSOp);
400 if ((!LHSCst && !LHSUndef) || (!RHSCst && !RHSUndef))
402 if (!AllowTypeMismatch && (LHSOp.
getValueType() != SVT ||
405 if (!
Match(LHSCst, RHSCst))
412 switch (VecReduceOpcode) {
417 case ISD::VP_REDUCE_FADD:
418 case ISD::VP_REDUCE_SEQ_FADD:
422 case ISD::VP_REDUCE_FMUL:
423 case ISD::VP_REDUCE_SEQ_FMUL:
426 case ISD::VP_REDUCE_ADD:
429 case ISD::VP_REDUCE_MUL:
432 case ISD::VP_REDUCE_AND:
435 case ISD::VP_REDUCE_OR:
438 case ISD::VP_REDUCE_XOR:
441 case ISD::VP_REDUCE_SMAX:
444 case ISD::VP_REDUCE_SMIN:
447 case ISD::VP_REDUCE_UMAX:
450 case ISD::VP_REDUCE_UMIN:
453 case ISD::VP_REDUCE_FMAX:
456 case ISD::VP_REDUCE_FMIN:
465#define BEGIN_REGISTER_VP_SDNODE(VPSD, ...) \
468#include "llvm/IR/VPIntrinsics.def"
476#define BEGIN_REGISTER_VP_SDNODE(VPSD, ...) case ISD::VPSD:
477#define VP_PROPERTY_BINARYOP return true;
478#define END_REGISTER_VP_SDNODE(VPSD) break;
479#include "llvm/IR/VPIntrinsics.def"
488#define BEGIN_REGISTER_VP_SDNODE(VPSD, ...) case ISD::VPSD:
489#define VP_PROPERTY_REDUCTION(STARTPOS, ...) return true;
490#define END_REGISTER_VP_SDNODE(VPSD) break;
491#include "llvm/IR/VPIntrinsics.def"
501#define BEGIN_REGISTER_VP_SDNODE(VPSD, LEGALPOS, TDNAME, MASKPOS, ...) \
504#include "llvm/IR/VPIntrinsics.def"
513#define BEGIN_REGISTER_VP_SDNODE(VPSD, LEGALPOS, TDNAME, MASKPOS, EVLPOS) \
516#include "llvm/IR/VPIntrinsics.def"
526#define BEGIN_REGISTER_VP_SDNODE(VPOPC, ...) case ISD::VPOPC:
527#define VP_PROPERTY_FUNCTIONAL_SDOPC(SDOPC) return ISD::SDOPC;
528#define END_REGISTER_VP_SDNODE(VPOPC) break;
529#include "llvm/IR/VPIntrinsics.def"
538#define BEGIN_REGISTER_VP_SDNODE(VPOPC, ...) break;
539#define VP_PROPERTY_FUNCTIONAL_SDOPC(SDOPC) case ISD::SDOPC:
540#define END_REGISTER_VP_SDNODE(VPOPC) return ISD::VPOPC;
541#include "llvm/IR/VPIntrinsics.def"
588 bool isIntegerLike) {
613 bool IsInteger =
Type.isInteger();
618 unsigned Op = Op1 | Op2;
634 bool IsInteger =
Type.isInteger();
669 ID.AddPointer(VTList.
VTs);
675 for (
const auto &Op : Ops) {
676 ID.AddPointer(Op.getNode());
677 ID.AddInteger(Op.getResNo());
684 for (
const auto &Op : Ops) {
685 ID.AddPointer(Op.getNode());
686 ID.AddInteger(Op.getResNo());
699 switch (
N->getOpcode()) {
708 ID.AddPointer(
C->getConstantIntValue());
709 ID.AddBoolean(
C->isOpaque());
714 ID.AddPointer(cast<ConstantFPSDNode>(
N)->getConstantFPValue());
730 ID.AddInteger(cast<RegisterSDNode>(
N)->
getReg());
733 ID.AddPointer(cast<RegisterMaskSDNode>(
N)->getRegMask());
736 ID.AddPointer(cast<SrcValueSDNode>(
N)->getValue());
740 ID.AddInteger(cast<FrameIndexSDNode>(
N)->getIndex());
744 if (cast<LifetimeSDNode>(
N)->hasOffset()) {
745 ID.AddInteger(cast<LifetimeSDNode>(
N)->
getSize());
750 ID.AddInteger(cast<PseudoProbeSDNode>(
N)->getGuid());
751 ID.AddInteger(cast<PseudoProbeSDNode>(
N)->getIndex());
752 ID.AddInteger(cast<PseudoProbeSDNode>(
N)->getAttributes());
756 ID.AddInteger(cast<JumpTableSDNode>(
N)->getIndex());
757 ID.AddInteger(cast<JumpTableSDNode>(
N)->getTargetFlags());
762 ID.AddInteger(CP->getAlign().value());
763 ID.AddInteger(CP->getOffset());
764 if (CP->isMachineConstantPoolEntry())
765 CP->getMachineCPVal()->addSelectionDAGCSEId(
ID);
767 ID.AddPointer(CP->getConstVal());
768 ID.AddInteger(CP->getTargetFlags());
780 ID.AddInteger(LD->getMemoryVT().getRawBits());
781 ID.AddInteger(LD->getRawSubclassData());
782 ID.AddInteger(LD->getPointerInfo().getAddrSpace());
783 ID.AddInteger(LD->getMemOperand()->getFlags());
788 ID.AddInteger(ST->getMemoryVT().getRawBits());
789 ID.AddInteger(ST->getRawSubclassData());
790 ID.AddInteger(ST->getPointerInfo().getAddrSpace());
791 ID.AddInteger(ST->getMemOperand()->getFlags());
802 case ISD::VP_STORE: {
810 case ISD::EXPERIMENTAL_VP_STRIDED_LOAD: {
817 case ISD::EXPERIMENTAL_VP_STRIDED_STORE: {
824 case ISD::VP_GATHER: {
832 case ISD::VP_SCATTER: {
897 for (
unsigned i = 0, e =
N->getValueType(0).getVectorNumElements();
922 if (
auto *MN = dyn_cast<MemIntrinsicSDNode>(
N)) {
923 ID.AddInteger(MN->getRawSubclassData());
924 ID.AddInteger(MN->getPointerInfo().getAddrSpace());
925 ID.AddInteger(MN->getMemOperand()->getFlags());
948 if (
N->getValueType(0) == MVT::Glue)
951 switch (
N->getOpcode()) {
959 for (
unsigned i = 1, e =
N->getNumValues(); i != e; ++i)
960 if (
N->getValueType(i) == MVT::Glue)
977 if (Node.use_empty())
992 while (!DeadNodes.
empty()) {
1001 DUL->NodeDeleted(
N,
nullptr);
1004 RemoveNodeFromCSEMaps(
N);
1035 RemoveNodeFromCSEMaps(
N);
1039 DeleteNodeNotInCSEMaps(
N);
1042void SelectionDAG::DeleteNodeNotInCSEMaps(
SDNode *
N) {
1043 assert(
N->getIterator() != AllNodes.begin() &&
1044 "Cannot delete the entry node!");
1045 assert(
N->use_empty() &&
"Cannot delete a node that is not dead!");
1054 assert(!(V->isVariadic() && isParameter));
1056 ByvalParmDbgValues.push_back(V);
1058 DbgValues.push_back(V);
1059 for (
const SDNode *Node : V->getSDNodes())
1061 DbgValMap[Node].push_back(V);
1066 if (
I == DbgValMap.end())
1068 for (
auto &Val:
I->second)
1069 Val->setIsInvalidated();
1073void SelectionDAG::DeallocateNode(
SDNode *
N) {
1097 switch (
N->getOpcode()) {
1101 EVT VT =
N->getValueType(0);
1102 assert(
N->getNumValues() == 1 &&
"Too many results!");
1104 "Wrong return type!");
1105 assert(
N->getNumOperands() == 2 &&
"Wrong number of operands!");
1106 assert(
N->getOperand(0).getValueType() ==
N->getOperand(1).getValueType() &&
1107 "Mismatched operand types!");
1109 "Wrong operand type!");
1111 "Wrong return type size");
1115 assert(
N->getNumValues() == 1 &&
"Too many results!");
1116 assert(
N->getValueType(0).isVector() &&
"Wrong return type!");
1117 assert(
N->getNumOperands() ==
N->getValueType(0).getVectorNumElements() &&
1118 "Wrong number of operands!");
1119 EVT EltVT =
N->getValueType(0).getVectorElementType();
1120 for (
const SDUse &Op :
N->ops()) {
1121 assert((Op.getValueType() == EltVT ||
1122 (EltVT.
isInteger() && Op.getValueType().isInteger() &&
1123 EltVT.
bitsLE(Op.getValueType()))) &&
1124 "Wrong operand type!");
1125 assert(Op.getValueType() ==
N->getOperand(0).getValueType() &&
1126 "Operands must all have the same type");
1138void SelectionDAG::InsertNode(
SDNode *
N) {
1139 AllNodes.push_back(
N);
1141 N->PersistentId = NextPersistentId++;
1144 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1145 DUL->NodeInserted(
N);
1152bool SelectionDAG::RemoveNodeFromCSEMaps(
SDNode *
N) {
1153 bool Erased =
false;
1154 switch (
N->getOpcode()) {
1157 assert(CondCodeNodes[cast<CondCodeSDNode>(
N)->
get()] &&
1158 "Cond code doesn't exist!");
1159 Erased = CondCodeNodes[cast<CondCodeSDNode>(
N)->get()] !=
nullptr;
1160 CondCodeNodes[cast<CondCodeSDNode>(
N)->get()] =
nullptr;
1163 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(
N)->getSymbol());
1167 Erased = TargetExternalSymbols.erase(std::pair<std::string, unsigned>(
1172 auto *MCSN = cast<MCSymbolSDNode>(
N);
1173 Erased = MCSymbols.erase(MCSN->getMCSymbol());
1177 EVT VT = cast<VTSDNode>(
N)->getVT();
1179 Erased = ExtendedValueTypeNodes.erase(VT);
1190 Erased = CSEMap.RemoveNode(
N);
1197 if (!Erased &&
N->getValueType(
N->getNumValues()-1) != MVT::Glue &&
1212SelectionDAG::AddModifiedNodeToCSEMaps(
SDNode *
N) {
1216 SDNode *Existing = CSEMap.GetOrInsertNode(
N);
1217 if (Existing !=
N) {
1224 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1225 DUL->NodeDeleted(
N, Existing);
1226 DeleteNodeNotInCSEMaps(
N);
1232 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next)
1233 DUL->NodeUpdated(
N);
1251 Node->intersectFlagsWith(
N->getFlags());
1271 Node->intersectFlagsWith(
N->getFlags());
1289 Node->intersectFlagsWith(
N->getFlags());
1294 Type *Ty = VT == MVT::iPTR ?
1303 : TM(tm), OptLevel(OL),
1306 InsertNode(&EntryNode);
1317 SDAGISelPass = PassPtr;
1321 LibInfo = LibraryInfo;
1326 FnVarLocs = VarLocs;
1330 assert(!UpdateListeners &&
"Dangling registered DAGUpdateListeners");
1332 OperandRecycler.clear(OperandAllocator);
1341void SelectionDAG::allnodes_clear() {
1342 assert(&*AllNodes.begin() == &EntryNode);
1343 AllNodes.remove(AllNodes.begin());
1344 while (!AllNodes.empty())
1345 DeallocateNode(&AllNodes.front());
1347 NextPersistentId = 0;
1353 SDNode *
N = CSEMap.FindNodeOrInsertPos(
ID, InsertPos);
1355 switch (
N->getOpcode()) {
1360 "debug location. Use another overload.");
1367 const SDLoc &
DL,
void *&InsertPos) {
1368 SDNode *
N = CSEMap.FindNodeOrInsertPos(
ID, InsertPos);
1370 switch (
N->getOpcode()) {
1376 if (
N->getDebugLoc() !=
DL.getDebugLoc())
1383 if (
DL.getIROrder() &&
DL.getIROrder() <
N->getIROrder())
1384 N->setDebugLoc(
DL.getDebugLoc());
1393 OperandRecycler.clear(OperandAllocator);
1394 OperandAllocator.
Reset();
1397 ExtendedValueTypeNodes.clear();
1398 ExternalSymbols.clear();
1399 TargetExternalSymbols.clear();
1402 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(),
1404 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(),
1405 static_cast<SDNode*
>(
nullptr));
1407 EntryNode.UseList =
nullptr;
1408 InsertNode(&EntryNode);
1414 return VT.
bitsGT(Op.getValueType())
1420std::pair<SDValue, SDValue>
1424 "Strict no-op FP extend/round not allowed.");
1426 VT.
bitsGT(Op.getValueType())
1431 return std::pair<SDValue, SDValue>(Res,
SDValue(Res.
getNode(), 1));
1435 return VT.
bitsGT(Op.getValueType()) ?
1441 return VT.
bitsGT(Op.getValueType()) ?
1447 return VT.
bitsGT(Op.getValueType()) ?
1454 if (VT.
bitsLE(Op.getValueType()))
1462 EVT OpVT = Op.getValueType();
1464 "Cannot getZeroExtendInReg FP types");
1466 "getZeroExtendInReg type should be vector iff the operand "
1470 "Vector element counts must match in getZeroExtendInReg");
1508 return getNode(ISD::VP_XOR,
DL, VT, Val, TrueValue, Mask, EVL);
1518 if (VT.
bitsGT(Op.getValueType()))
1519 return getNode(ISD::VP_ZERO_EXTEND,
DL, VT, Op, Mask, EVL);
1520 if (VT.
bitsLT(Op.getValueType()))
1521 return getNode(ISD::VP_TRUNCATE,
DL, VT, Op, Mask, EVL);
1541 bool isT,
bool isO) {
1545 "getConstant with a uint64_t value that doesn't fit in the type!");
1550 bool isT,
bool isO) {
1555 EVT VT,
bool isT,
bool isO) {
1587 "Can only handle an even split!");
1591 for (
unsigned i = 0; i != Parts; ++i)
1593 NewVal.
extractBits(ViaEltSizeInBits, i * ViaEltSizeInBits),
DL,
1594 ViaEltVT, isT, isO));
1599 unsigned ViaVecNumElts = VT.
getSizeInBits() / ViaEltSizeInBits;
1610 NewVal.
extractBits(ViaEltSizeInBits, i * ViaEltSizeInBits),
DL,
1611 ViaEltVT, isT, isO));
1616 std::reverse(EltParts.
begin(), EltParts.
end());
1635 "APInt size does not match type size!");
1643 if ((
N = FindNodeOrInsertPos(
ID,
DL, IP)))
1648 N = newSDNode<ConstantSDNode>(isT, isO, Elt, EltVT);
1649 CSEMap.InsertNode(
N, IP);
1666 const SDLoc &
DL,
bool LegalTypes) {
1683 EVT VT,
bool isTarget) {
1697 if ((
N = FindNodeOrInsertPos(
ID,
DL, IP)))
1702 N = newSDNode<ConstantFPSDNode>(isTarget, &V, EltVT);
1703 CSEMap.InsertNode(
N, IP);
1717 if (EltVT == MVT::f32)
1719 if (EltVT == MVT::f64)
1721 if (EltVT == MVT::f80 || EltVT == MVT::f128 || EltVT == MVT::ppcf128 ||
1722 EltVT == MVT::f16 || EltVT == MVT::bf16) {
1733 EVT VT, int64_t
Offset,
bool isTargetGA,
1734 unsigned TargetFlags) {
1735 assert((TargetFlags == 0 || isTargetGA) &&
1736 "Cannot set target flags on target-independent globals");
1753 ID.AddInteger(TargetFlags);
1758 auto *
N = newSDNode<GlobalAddressSDNode>(
1759 Opc,
DL.getIROrder(),
DL.getDebugLoc(), GV, VT,
Offset, TargetFlags);
1760 CSEMap.InsertNode(
N, IP);
1771 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
1774 auto *
N = newSDNode<FrameIndexSDNode>(FI, VT, isTarget);
1775 CSEMap.InsertNode(
N, IP);
1781 unsigned TargetFlags) {
1782 assert((TargetFlags == 0 || isTarget) &&
1783 "Cannot set target flags on target-independent jump tables");
1788 ID.AddInteger(TargetFlags);
1790 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
1793 auto *
N = newSDNode<JumpTableSDNode>(JTI, VT, isTarget, TargetFlags);
1794 CSEMap.InsertNode(
N, IP);
1801 bool isTarget,
unsigned TargetFlags) {
1802 assert((TargetFlags == 0 || isTarget) &&
1803 "Cannot set target flags on target-independent globals");
1814 ID.AddInteger(TargetFlags);
1816 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
1821 CSEMap.InsertNode(
N, IP);
1830 bool isTarget,
unsigned TargetFlags) {
1831 assert((TargetFlags == 0 || isTarget) &&
1832 "Cannot set target flags on target-independent globals");
1840 C->addSelectionDAGCSEId(
ID);
1841 ID.AddInteger(TargetFlags);
1843 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
1848 CSEMap.InsertNode(
N, IP);
1854 unsigned TargetFlags) {
1859 ID.AddInteger(TargetFlags);
1861 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
1864 auto *
N = newSDNode<TargetIndexSDNode>(
Index, VT,
Offset, TargetFlags);
1865 CSEMap.InsertNode(
N, IP);
1875 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
1878 auto *
N = newSDNode<BasicBlockSDNode>(
MBB);
1879 CSEMap.InsertNode(
N, IP);
1886 ValueTypeNodes.size())
1893 N = newSDNode<VTSDNode>(VT);
1901 N = newSDNode<ExternalSymbolSDNode>(
false,
Sym, 0, VT);
1910 N = newSDNode<MCSymbolSDNode>(
Sym, VT);
1916 unsigned TargetFlags) {
1918 TargetExternalSymbols[std::pair<std::string, unsigned>(
Sym, TargetFlags)];
1920 N = newSDNode<ExternalSymbolSDNode>(
true,
Sym, TargetFlags, VT);
1926 if ((
unsigned)
Cond >= CondCodeNodes.size())
1927 CondCodeNodes.resize(
Cond+1);
1929 if (!CondCodeNodes[
Cond]) {
1930 auto *
N = newSDNode<CondCodeSDNode>(
Cond);
1931 CondCodeNodes[
Cond] =
N;
1941 "Immediate does not fit VT");
1948 if (Attr.isValid()) {
1950 if (std::optional<unsigned> VScaleMax = Attr.getVScaleRangeMax())
1951 if (*VScaleMax == VScaleMin)
1961 if (EC.isScalable())
1997 "Must have the same number of vector elements as mask elements!");
1999 "Invalid VECTOR_SHUFFLE");
2007 int NElts = Mask.size();
2009 [&](
int M) {
return M < (NElts * 2) && M >= -1; }) &&
2010 "Index out of range");
2018 for (
int i = 0; i != NElts; ++i)
2019 if (MaskVec[i] >= NElts) MaskVec[i] -= NElts;
2035 for (
int i = 0; i < NElts; ++i) {
2036 if (MaskVec[i] <
Offset || MaskVec[i] >= (
Offset + NElts))
2040 if (UndefElements[MaskVec[i] -
Offset]) {
2046 if (!UndefElements[i])
2050 if (
auto *N1BV = dyn_cast<BuildVectorSDNode>(N1))
2051 BlendSplat(N1BV, 0);
2052 if (
auto *N2BV = dyn_cast<BuildVectorSDNode>(N2))
2053 BlendSplat(N2BV, NElts);
2058 bool AllLHS =
true, AllRHS =
true;
2060 for (
int i = 0; i != NElts; ++i) {
2061 if (MaskVec[i] >= NElts) {
2066 }
else if (MaskVec[i] >= 0) {
2070 if (AllLHS && AllRHS)
2072 if (AllLHS && !N2Undef)
2085 bool Identity =
true, AllSame =
true;
2086 for (
int i = 0; i != NElts; ++i) {
2087 if (MaskVec[i] >= 0 && MaskVec[i] != i) Identity =
false;
2088 if (MaskVec[i] != MaskVec[0]) AllSame =
false;
2090 if (Identity && NElts)
2100 V = V->getOperand(0);
2103 if (
auto *BV = dyn_cast<BuildVectorSDNode>(V)) {
2105 SDValue Splat = BV->getSplatValue(&UndefElements);
2115 if (Splat && UndefElements.
none()) {
2120 if (
auto *
C = dyn_cast<ConstantSDNode>(Splat))
2126 if (AllSame && SameNumElts) {
2127 EVT BuildVT = BV->getValueType(0);
2143 for (
int i = 0; i != NElts; ++i)
2144 ID.AddInteger(MaskVec[i]);
2153 int *MaskAlloc = OperandAllocator.
Allocate<
int>(NElts);
2156 auto *
N = newSDNode<ShuffleVectorSDNode>(VT,
dl.
getIROrder(),
2158 createOperands(
N, Ops);
2160 CSEMap.InsertNode(
N, IP);
2180 ID.AddInteger(RegNo);
2182 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
2185 auto *
N = newSDNode<RegisterSDNode>(RegNo, VT);
2187 CSEMap.InsertNode(
N, IP);
2195 ID.AddPointer(RegMask);
2197 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
2200 auto *
N = newSDNode<RegisterMaskSDNode>(RegMask);
2201 CSEMap.InsertNode(
N, IP);
2216 ID.AddPointer(Label);
2218 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
2223 createOperands(
N, Ops);
2225 CSEMap.InsertNode(
N, IP);
2231 int64_t
Offset,
bool isTarget,
2232 unsigned TargetFlags) {
2239 ID.AddInteger(TargetFlags);
2241 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
2244 auto *
N = newSDNode<BlockAddressSDNode>(Opc, VT, BA,
Offset, TargetFlags);
2245 CSEMap.InsertNode(
N, IP);
2256 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
2259 auto *
N = newSDNode<SrcValueSDNode>(V);
2260 CSEMap.InsertNode(
N, IP);
2271 if (
SDNode *
E = FindNodeOrInsertPos(
ID, IP))
2274 auto *
N = newSDNode<MDNodeSDNode>(MD);
2275 CSEMap.InsertNode(
N, IP);
2281 if (VT == V.getValueType())
2288 unsigned SrcAS,
unsigned DestAS) {
2292 ID.AddInteger(SrcAS);
2293 ID.AddInteger(DestAS);
2301 createOperands(
N, Ops);
2303 CSEMap.InsertNode(
N, IP);
2315 EVT OpTy = Op.getValueType();
2317 if (OpTy == ShTy || OpTy.
isVector())
return Op;
2325 const Value *V = cast<SrcValueSDNode>(Node->getOperand(2))->getValue();
2326 EVT VT = Node->getValueType(0);
2327 SDValue Tmp1 = Node->getOperand(0);
2328 SDValue Tmp2 = Node->getOperand(1);
2329 const MaybeAlign MA(Node->getConstantOperandVal(3));
2361 const Value *VD = cast<SrcValueSDNode>(Node->getOperand(3))->getValue();
2362 const Value *VS = cast<SrcValueSDNode>(Node->getOperand(4))->getValue();
2373 Align RedAlign = UseABI ?
DL.getABITypeAlign(Ty) :
DL.getPrefTypeAlign(Ty);
2383 if (RedAlign > StackAlign) {
2386 unsigned NumIntermediates;
2388 NumIntermediates, RegisterVT);
2390 Align RedAlign2 = UseABI ?
DL.getABITypeAlign(Ty) :
DL.getPrefTypeAlign(Ty);
2391 if (RedAlign2 < RedAlign)
2392 RedAlign = RedAlign2;
2407 false,
nullptr, StackID);
2422 "Don't know how to choose the maximum size when creating a stack "
2431 Align Align = std::max(
DL.getPrefTypeAlign(Ty1),
DL.getPrefTypeAlign(Ty2));
2439 auto GetUndefBooleanConstant = [&]() {
2478 return GetUndefBooleanConstant();
2483 return GetUndefBooleanConstant();
2492 const APInt &C2 = N2C->getAPIntValue();
2494 const APInt &C1 = N1C->getAPIntValue();
2501 auto *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
2502 auto *N2CFP = dyn_cast<ConstantFPSDNode>(N2);
2504 if (N1CFP && N2CFP) {
2509 return GetUndefBooleanConstant();
2514 return GetUndefBooleanConstant();
2520 return GetUndefBooleanConstant();
2525 return GetUndefBooleanConstant();
2530 return GetUndefBooleanConstant();
2536 return GetUndefBooleanConstant();
2565 return getSetCC(
dl, VT, N2, N1, SwappedCond);
2566 }
else if ((N2CFP && N2CFP->getValueAPF().isNaN()) ||
2581 return GetUndefBooleanConstant();
2592 unsigned BitWidth = Op.getScalarValueSizeInBits();
2600 unsigned Depth)
const {
2608 const APInt &DemandedElts,
2609 unsigned Depth)
const {
2616 unsigned Depth )
const {
2622 unsigned Depth)
const {
2627 const APInt &DemandedElts,
2628 unsigned Depth)
const {
2629 EVT VT = Op.getValueType();
2636 for (
unsigned EltIdx = 0; EltIdx != NumElts; ++EltIdx) {
2637 if (!DemandedElts[EltIdx])
2641 KnownZeroElements.
setBit(EltIdx);
2643 return KnownZeroElements;
2653 unsigned Opcode = V.getOpcode();
2654 EVT VT = V.getValueType();
2657 "scalable demanded bits are ignored");
2669 UndefElts = V.getOperand(0).isUndef()
2678 APInt UndefLHS, UndefRHS;
2683 UndefElts = UndefLHS | UndefRHS;
2713 for (
unsigned i = 0; i != NumElts; ++i) {
2719 if (!DemandedElts[i])
2721 if (Scl && Scl != Op)
2731 ArrayRef<int> Mask = cast<ShuffleVectorSDNode>(V)->getMask();
2732 for (
int i = 0; i != (int)NumElts; ++i) {
2738 if (!DemandedElts[i])
2740 if (M < (
int)NumElts)
2743 DemandedRHS.
setBit(M - NumElts);
2755 auto CheckSplatSrc = [&](
SDValue Src,
const APInt &SrcElts) {
2757 return (SrcElts.popcount() == 1) ||
2759 (SrcElts & SrcUndefs).
isZero());
2761 if (!DemandedLHS.
isZero())
2762 return CheckSplatSrc(V.getOperand(0), DemandedLHS);
2763 return CheckSplatSrc(V.getOperand(1), DemandedRHS);
2767 SDValue Src = V.getOperand(0);
2769 if (Src.getValueType().isScalableVector())
2772 unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
2785 SDValue Src = V.getOperand(0);
2787 if (Src.getValueType().isScalableVector())
2789 unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
2791 APInt DemandedSrcElts = DemandedElts.
zext(NumSrcElts);
2793 UndefElts = UndefSrcElts.
trunc(NumElts);
2799 SDValue Src = V.getOperand(0);
2800 EVT SrcVT = Src.getValueType();
2810 if ((
BitWidth % SrcBitWidth) == 0) {
2812 unsigned Scale =
BitWidth / SrcBitWidth;
2814 APInt ScaledDemandedElts =
2816 for (
unsigned I = 0;
I != Scale; ++
I) {
2820 SubDemandedElts &= ScaledDemandedElts;
2824 if (!SubUndefElts.
isZero())
2838 EVT VT = V.getValueType();
2848 (AllowUndefs || !UndefElts);
2854 EVT VT = V.getValueType();
2855 unsigned Opcode = V.getOpcode();
2876 SplatIdx = (UndefElts & DemandedElts).
countr_one();
2890 auto *SVN = cast<ShuffleVectorSDNode>(V);
2891 if (!SVN->isSplat())
2893 int Idx = SVN->getSplatIndex();
2894 int NumElts = V.getValueType().getVectorNumElements();
2895 SplatIdx =
Idx % NumElts;
2896 return V.getOperand(
Idx / NumElts);
2912 if (LegalSVT.
bitsLT(SVT))
2923 const APInt &DemandedElts)
const {
2926 "Unknown shift node");
2927 unsigned BitWidth = V.getScalarValueSizeInBits();
2930 const APInt &ShAmt = SA->getAPIntValue();
2941 "Unknown shift node");
2944 unsigned BitWidth = V.getScalarValueSizeInBits();
2945 auto *BV = dyn_cast<BuildVectorSDNode>(V.getOperand(1));
2948 const APInt *MinShAmt =
nullptr;
2949 for (
unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) {
2950 if (!DemandedElts[i])
2952 auto *SA = dyn_cast<ConstantSDNode>(BV->getOperand(i));
2956 const APInt &ShAmt = SA->getAPIntValue();
2959 if (MinShAmt && MinShAmt->
ule(ShAmt))
2970 "Unknown shift node");
2973 unsigned BitWidth = V.getScalarValueSizeInBits();
2974 auto *BV = dyn_cast<BuildVectorSDNode>(V.getOperand(1));
2977 const APInt *MaxShAmt =
nullptr;
2978 for (
unsigned i = 0, e = BV->getNumOperands(); i != e; ++i) {
2979 if (!DemandedElts[i])
2981 auto *SA = dyn_cast<ConstantSDNode>(BV->getOperand(i));
2985 const APInt &ShAmt = SA->getAPIntValue();
2988 if (MaxShAmt && MaxShAmt->
uge(ShAmt))
2999 EVT VT = Op.getValueType();
3014 unsigned Depth)
const {
3015 unsigned BitWidth = Op.getScalarValueSizeInBits();
3019 if (
auto *
C = dyn_cast<ConstantSDNode>(Op)) {
3023 if (
auto *
C = dyn_cast<ConstantFPSDNode>(Op)) {
3033 assert((!Op.getValueType().isFixedLengthVector() ||
3034 NumElts == Op.getValueType().getVectorNumElements()) &&
3035 "Unexpected vector size");
3040 unsigned Opcode = Op.getOpcode();
3048 "Expected SPLAT_VECTOR implicit truncation");
3055 assert(!Op.getValueType().isScalableVector());
3058 for (
unsigned i = 0, e = Op.getNumOperands(); i != e; ++i) {
3059 if (!DemandedElts[i])
3068 "Expected BUILD_VECTOR implicit truncation");
3081 assert(!Op.getValueType().isScalableVector());
3084 APInt DemandedLHS, DemandedRHS;
3088 DemandedLHS, DemandedRHS))
3093 if (!!DemandedLHS) {
3101 if (!!DemandedRHS) {
3110 const APInt &Multiplier = Op.getConstantOperandAPInt(0);
3115 if (Op.getValueType().isScalableVector())
3119 EVT SubVectorVT = Op.getOperand(0).getValueType();
3121 unsigned NumSubVectors = Op.getNumOperands();
3122 for (
unsigned i = 0; i != NumSubVectors; ++i) {
3124 DemandedElts.
extractBits(NumSubVectorElts, i * NumSubVectorElts);
3125 if (!!DemandedSub) {
3126 SDValue Sub = Op.getOperand(i);
3137 if (Op.getValueType().isScalableVector())
3141 SDValue Src = Op.getOperand(0);
3142 SDValue Sub = Op.getOperand(1);
3146 APInt DemandedSrcElts = DemandedElts;
3151 if (!!DemandedSubElts) {
3156 if (!!DemandedSrcElts) {
3164 SDValue Src = Op.getOperand(0);
3166 if (Op.getValueType().isScalableVector() || Src.getValueType().isScalableVector())
3169 unsigned NumSrcElts = Src.getValueType().getVectorNumElements();
3175 if (Op.getValueType().isScalableVector())
3179 if (DemandedElts != 1)
3182 SDValue N0 = Op.getOperand(0);
3190 if (Op.getValueType().isScalableVector())
3193 SDValue N0 = Op.getOperand(0);
3210 if ((
BitWidth % SubBitWidth) == 0) {
3217 unsigned SubScale =
BitWidth / SubBitWidth;
3218 APInt SubDemandedElts(NumElts * SubScale, 0);
3219 for (
unsigned i = 0; i != NumElts; ++i)
3220 if (DemandedElts[i])
3221 SubDemandedElts.
setBit(i * SubScale);
3223 for (
unsigned i = 0; i != SubScale; ++i) {
3226 unsigned Shifts = IsLE ? i : SubScale - 1 - i;
3227 Known.
insertBits(Known2, SubBitWidth * Shifts);
3232 if ((SubBitWidth %
BitWidth) == 0) {
3233 assert(Op.getValueType().isVector() &&
"Expected bitcast to vector");
3238 unsigned SubScale = SubBitWidth /
BitWidth;
3239 APInt SubDemandedElts =
3244 for (
unsigned i = 0; i != NumElts; ++i)
3245 if (DemandedElts[i]) {
3246 unsigned Shifts = IsLE ? i : NumElts - 1 - i;
3277 bool SelfMultiply = Op.getOperand(0) == Op.getOperand(1);
3281 Op.getOperand(0), DemandedElts,
false,
Depth + 1);
3287 if (Op->getFlags().hasNoSignedWrap() &&
3288 Op.getOperand(0) == Op.getOperand(1) &&
3306 assert((Op.getResNo() == 0 || Op.getResNo() == 1) &&
"Unknown result");
3309 bool SelfMultiply = Op.getOperand(0) == Op.getOperand(1);
3310 if (Op.getResNo() == 0)
3317 assert((Op.getResNo() == 0 || Op.getResNo() == 1) &&
"Unknown result");
3320 bool SelfMultiply = Op.getOperand(0) == Op.getOperand(1);
3321 if (Op.getResNo() == 0)
3360 if (Op.getResNo() != 1)
3375 unsigned OpNo = Op->isStrictFPOpcode() ? 1 : 0;
3389 if (
const APInt *ShMinAmt =
3399 if (
const APInt *ShMinAmt =
3411 unsigned Amt =
C->getAPIntValue().urem(
BitWidth);
3417 DemandedElts,
Depth + 1);
3442 assert((Op.getResNo() == 0 || Op.getResNo() == 1) &&
"Unknown result");
3445 unsigned LoBits = Op.getOperand(0).getScalarValueSizeInBits();
3446 unsigned HiBits = Op.getOperand(1).getScalarValueSizeInBits();
3449 Known = Known2.
concat(Known);
3463 if (Op.getResNo() == 0)
3471 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
3512 !Op.getValueType().isScalableVector()) {
3526 for (
unsigned i = 0; i != NumElts; ++i) {
3527 if (!DemandedElts[i])
3530 if (
auto *CInt = dyn_cast<ConstantInt>(Elt)) {
3536 if (
auto *CFP = dyn_cast<ConstantFP>(Elt)) {
3537 APInt Value = CFP->getValueAPF().bitcastToAPInt();
3548 if (
auto *CInt = dyn_cast<ConstantInt>(Cst)) {
3550 }
else if (
auto *CFP = dyn_cast<ConstantFP>(Cst)) {
3558 EVT VT = LD->getMemoryVT();
3562 EVT VT = LD->getValueType(0);
3574 EVT MemVT = LD->getMemoryVT();
3586 if (Op.getValueType().isScalableVector())
3588 EVT InVT = Op.getOperand(0).getValueType();
3600 if (Op.getValueType().isScalableVector())
3602 EVT InVT = Op.getOperand(0).getValueType();
3618 if (Op.getValueType().isScalableVector())
3620 EVT InVT = Op.getOperand(0).getValueType();
3637 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
3640 Known.
Zero |= (~InMask);
3641 Known.
One &= (~Known.Zero);
3645 unsigned LogOfAlign =
Log2(cast<AssertAlignSDNode>(Op)->
getAlign());
3665 Flags.hasNoSignedWrap(), Known, Known2);
3672 if (Op.getResNo() == 1) {
3682 assert(Op.getResNo() == 0 &&
3683 "We only compute knownbits for the difference here.");
3699 if (Op.getResNo() == 1) {
3710 assert(Op.getResNo() == 0 &&
"We only compute knownbits for the sum here.");
3758 const unsigned Index = Op.getConstantOperandVal(1);
3759 const unsigned EltBitWidth = Op.getValueSizeInBits();
3766 Known = Known.
trunc(EltBitWidth);
3770 SDValue InVec = Op.getOperand(0);
3771 SDValue EltNo = Op.getOperand(1);
3782 Known = Known.
trunc(EltBitWidth);
3787 auto *ConstEltNo = dyn_cast<ConstantSDNode>(EltNo);
3788 if (ConstEltNo && ConstEltNo->getAPIntValue().ult(NumSrcElts))
3798 if (Op.getValueType().isScalableVector())
3804 SDValue InVec = Op.getOperand(0);
3805 SDValue InVal = Op.getOperand(1);
3806 SDValue EltNo = Op.getOperand(2);
3807 bool DemandedVal =
true;
3808 APInt DemandedVecElts = DemandedElts;
3809 auto *CEltNo = dyn_cast<ConstantSDNode>(EltNo);
3810 if (CEltNo && CEltNo->getAPIntValue().ult(NumElts)) {
3811 unsigned EltIdx = CEltNo->getZExtValue();
3812 DemandedVal = !!DemandedElts[EltIdx];
3821 if (!!DemandedVecElts) {
3839 Known = Known2.
abs();
3870 if (CstLow && CstHigh) {
3875 const APInt &ValueHigh = CstHigh->getAPIntValue();
3876 if (ValueLow.
sle(ValueHigh)) {
3879 unsigned MinSignBits = std::min(LowSignBits, HighSignBits);
3902 if (IsMax && CstLow) {
3914 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
3919 if (Op.getResNo() == 1) {
3946 cast<AtomicSDNode>(Op)->getMemoryVT().getScalarSizeInBits();
3948 if (Op.getResNo() == 0) {
3969 if (Op.getValueType().isScalableVector())
4067 return Const->getAPIntValue().zextOrTrunc(
BitWidth).isPowerOf2();
4073 if (
C &&
C->getAPIntValue() == 1)
4081 if (
C &&
C->getAPIntValue().isSignMask())
4088 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(E))
4089 return C->getAPIntValue().zextOrTrunc(BitWidth).isPowerOf2();
4097 if (
C->getAPIntValue().zextOrTrunc(
BitWidth).isPowerOf2())
4112 EVT VT = Op.getValueType();
4124 unsigned Depth)
const {
4125 EVT VT = Op.getValueType();
4130 unsigned FirstAnswer = 1;
4132 if (
auto *
C = dyn_cast<ConstantSDNode>(Op)) {
4133 const APInt &Val =
C->getAPIntValue();
4143 unsigned Opcode = Op.getOpcode();
4147 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
4148 return VTBits-Tmp+1;
4150 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits();
4157 unsigned NumSrcBits = Op.getOperand(0).getValueSizeInBits();
4159 if (NumSrcSignBits > (NumSrcBits - VTBits))
4160 return NumSrcSignBits - (NumSrcBits - VTBits);
4166 for (
unsigned i = 0, e = Op.getNumOperands(); (i < e) && (Tmp > 1); ++i) {
4167 if (!DemandedElts[i])
4174 APInt T =
C->getAPIntValue().trunc(VTBits);
4175 Tmp2 =
T.getNumSignBits();
4179 if (
SrcOp.getValueSizeInBits() != VTBits) {
4181 "Expected BUILD_VECTOR implicit truncation");
4182 unsigned ExtraBits =
SrcOp.getValueSizeInBits() - VTBits;
4183 Tmp2 = (Tmp2 > ExtraBits ? Tmp2 - ExtraBits : 1);
4186 Tmp = std::min(Tmp, Tmp2);
4193 APInt DemandedLHS, DemandedRHS;
4197 DemandedLHS, DemandedRHS))
4200 Tmp = std::numeric_limits<unsigned>::max();
4203 if (!!DemandedRHS) {
4205 Tmp = std::min(Tmp, Tmp2);
4210 assert(Tmp <= VTBits &&
"Failed to determine minimum sign bits");
4217 SDValue N0 = Op.getOperand(0);
4226 if (VTBits == SrcBits)
4232 if ((SrcBits % VTBits) == 0) {
4235 unsigned Scale = SrcBits / VTBits;
4236 APInt SrcDemandedElts =
4246 for (
unsigned i = 0; i != NumElts; ++i)
4247 if (DemandedElts[i]) {
4248 unsigned SubOffset = i % Scale;
4249 SubOffset = (IsLE ? ((Scale - 1) - SubOffset) : SubOffset);
4250 SubOffset = SubOffset * VTBits;
4251 if (Tmp <= SubOffset)
4253 Tmp2 = std::min(Tmp2, Tmp - SubOffset);
4262 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarSizeInBits();
4263 return VTBits - Tmp + 1;
4265 Tmp = VTBits - Op.getOperand(0).getScalarValueSizeInBits();
4269 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarSizeInBits();
4272 return std::max(Tmp, Tmp2);
4276 SDValue Src = Op.getOperand(0);
4277 EVT SrcVT = Src.getValueType();
4285 if (
const APInt *ShAmt =
4287 Tmp = std::min<uint64_t>(Tmp + ShAmt->getZExtValue(), VTBits);
4290 if (
const APInt *ShAmt =
4294 if (ShAmt->ult(Tmp))
4295 return Tmp - ShAmt->getZExtValue();
4305 FirstAnswer = std::min(Tmp, Tmp2);
4315 if (Tmp == 1)
return 1;
4317 return std::min(Tmp, Tmp2);
4320 if (Tmp == 1)
return 1;
4322 return std::min(Tmp, Tmp2);
4334 if (CstLow && CstHigh) {
4339 Tmp2 = CstHigh->getAPIntValue().getNumSignBits();
4340 return std::min(Tmp, Tmp2);
4349 return std::min(Tmp, Tmp2);
4357 return std::min(Tmp, Tmp2);
4368 if (Op.getResNo() != 1)
4382 unsigned OpNo = Op->isStrictFPOpcode() ? 1 : 0;
4399 unsigned RotAmt =
C->getAPIntValue().urem(VTBits);
4403 RotAmt = (VTBits - RotAmt) % VTBits;
4407 if (Tmp > (RotAmt + 1))
return (Tmp - RotAmt);
4415 if (Tmp == 1)
return 1;
4420 if (CRHS->isAllOnes()) {
4426 if ((Known.
Zero | 1).isAllOnes())
4436 if (Tmp2 == 1)
return 1;
4437 return std::min(Tmp, Tmp2) - 1;
4440 if (Tmp2 == 1)
return 1;
4445 if (CLHS->isZero()) {
4450 if ((Known.
Zero | 1).isAllOnes())