87#define DEBUG_TYPE "dagcombine"
89STATISTIC(NodesCombined ,
"Number of dag nodes combined");
90STATISTIC(PreIndexedNodes ,
"Number of pre-indexed nodes created");
91STATISTIC(PostIndexedNodes,
"Number of post-indexed nodes created");
92STATISTIC(OpsNarrowed ,
"Number of load/op/store narrowed");
93STATISTIC(LdStFP2Int ,
"Number of fp load/store pairs transformed to int");
95STATISTIC(NumFPLogicOpsConv,
"Number of logic ops converted to fp ops");
98 "Controls whether a DAG combine is performed for a node");
102 cl::desc(
"Enable DAG combiner's use of IR alias analysis"));
106 cl::desc(
"Enable DAG combiner's use of TBAA"));
111 cl::desc(
"Only use DAG-combiner alias analysis in this"
119 cl::desc(
"Bypass the profitability model of load slicing"),
124 cl::desc(
"DAG combiner may split indexing from loads"));
128 cl::desc(
"DAG combiner enable merging multiple stores "
129 "into a wider store"));
133 cl::desc(
"Limit the number of operands to inline for Token Factors"));
137 cl::desc(
"Limit the number of times for the same StoreNode and RootNode "
138 "to bail out in store merging dependence check"));
142 cl::desc(
"DAG combiner enable reducing the width of load/op/store "
145 "combiner-reduce-load-op-store-width-force-narrowing-profitable",
147 cl::desc(
"DAG combiner force override the narrowing profitable check when "
148 "reducing the width of load/op/store sequences"));
152 cl::desc(
"DAG combiner enable load/<replace bytes>/store with "
153 "a narrower store"));
157 cl::desc(
"DAG combiner nodes consistently processed in topological order"));
161 cl::desc(
"Disable the DAG combiner"));
171 bool LegalDAG =
false;
172 bool LegalOperations =
false;
173 bool LegalTypes =
false;
175 bool DisableGenericCombines;
211 void AddUsersToWorklist(
SDNode *
N) {
217 void AddToWorklistWithUsers(SDNode *
N) {
218 AddUsersToWorklist(
N);
225 void clearAddedDanglingWorklistEntries() {
227 while (!PruningList.empty()) {
228 auto *
N = PruningList.pop_back_val();
230 recursivelyDeleteUnusedNodes(
N);
234 SDNode *getNextWorklistEntry() {
236 clearAddedDanglingWorklistEntries();
240 while (!
N && !Worklist.empty()) {
241 N = Worklist.pop_back_val();
245 assert(
N->getCombinerWorklistIndex() >= 0 &&
246 "Found a worklist entry without a corresponding map entry!");
248 N->setCombinerWorklistIndex(-2);
258 : DAG(
D), TLI(
D.getTargetLoweringInfo()),
259 STI(
D.getSubtarget().getSelectionDAGInfo()), OptLevel(OL),
261 ForCodeSize = DAG.shouldOptForSize();
262 DisableGenericCombines =
266 void ConsiderForPruning(SDNode *
N) {
268 PruningList.insert(
N);
273 void AddToWorklist(SDNode *
N,
bool IsCandidateForPruning =
true,
274 bool SkipIfCombinedBefore =
false) {
276 "Deleted Node added to Worklist");
283 if (SkipIfCombinedBefore &&
N->getCombinerWorklistIndex() == -2)
286 if (IsCandidateForPruning)
287 ConsiderForPruning(
N);
289 if (
N->getCombinerWorklistIndex() < 0) {
290 N->setCombinerWorklistIndex(Worklist.size());
291 Worklist.push_back(
N);
296 void removeFromWorklist(SDNode *
N) {
297 PruningList.remove(
N);
298 StoreRootCountMap.erase(
N);
300 int WorklistIndex =
N->getCombinerWorklistIndex();
304 if (WorklistIndex < 0)
308 Worklist[WorklistIndex] =
nullptr;
309 N->setCombinerWorklistIndex(-1);
312 void deleteAndRecombine(SDNode *
N);
313 bool recursivelyDeleteUnusedNodes(SDNode *
N);
321 return CombineTo(
N, &Res, 1, AddTo);
328 return CombineTo(
N, To, 2, AddTo);
331 SDValue CombineTo(SDNode *
N, SmallVectorImpl<SDValue> *To,
333 return CombineTo(
N, To->
data(), To->
size(), AddTo);
336 void CommitTargetLoweringOpt(
const TargetLowering::TargetLoweringOpt &TLO);
343 unsigned BitWidth =
Op.getScalarValueSizeInBits();
345 return SimplifyDemandedBits(
Op, DemandedBits);
348 bool SimplifyDemandedBits(
SDValue Op,
const APInt &DemandedBits) {
349 EVT VT =
Op.getValueType();
353 return SimplifyDemandedBits(
Op, DemandedBits, DemandedElts,
false);
359 bool SimplifyDemandedVectorElts(
SDValue Op) {
361 if (
Op.getValueType().isScalableVector())
364 unsigned NumElts =
Op.getValueType().getVectorNumElements();
366 return SimplifyDemandedVectorElts(
Op, DemandedElts);
369 bool SimplifyDemandedBits(
SDValue Op,
const APInt &DemandedBits,
370 const APInt &DemandedElts,
371 bool AssumeSingleUse =
false);
372 bool SimplifyDemandedVectorElts(
SDValue Op,
const APInt &DemandedElts,
373 bool AssumeSingleUse =
false);
375 bool CombineToPreIndexedLoadStore(SDNode *
N);
376 bool CombineToPostIndexedLoadStore(SDNode *
N);
377 SDValue SplitIndexingFromLoad(LoadSDNode *LD);
378 bool SliceUpLoad(SDNode *
N);
384 StoreSDNode *getUniqueStoreFeeding(LoadSDNode *LD, int64_t &
Offset);
386 SDValue ForwardStoreValueToDirectLoad(LoadSDNode *LD);
387 bool getTruncatedStoreValue(StoreSDNode *ST,
SDValue &Val);
388 bool extendLoadedValueToExtension(LoadSDNode *LD,
SDValue &Val);
390 void ReplaceLoadWithPromotedLoad(SDNode *
Load, SDNode *ExtLoad);
399 SDValue foldShiftToAvg(SDNode *
N,
const SDLoc &
DL);
401 SDValue foldBitwiseOpWithNeg(SDNode *
N,
const SDLoc &
DL, EVT VT);
419 SDValue visitTokenFactor(SDNode *
N);
420 SDValue visitMERGE_VALUES(SDNode *
N);
434 SDValue visitUADDO_CARRY(SDNode *
N);
435 SDValue visitSADDO_CARRY(SDNode *
N);
441 SDValue visitUSUBO_CARRY(SDNode *
N);
442 SDValue visitSSUBO_CARRY(SDNode *
N);
464 SDValue SimplifyVCastOp(SDNode *
N,
const SDLoc &
DL);
465 SDValue SimplifyVBinOp(SDNode *
N,
const SDLoc &
DL);
469 SDValue visitFunnelShift(SDNode *
N);
473 SDValue visitABS_MIN_POISON(SDNode *
N);
480 SDValue visitCTLZ_ZERO_POISON(SDNode *
N);
482 SDValue visitCTTZ_ZERO_POISON(SDNode *
N);
489 SDValue visitSIGN_EXTEND(SDNode *
N);
490 SDValue visitZERO_EXTEND(SDNode *
N);
493 SDValue visitAssertAlign(SDNode *
N);
495 SDValue visitSIGN_EXTEND_INREG(SDNode *
N);
496 SDValue visitEXTEND_VECTOR_INREG(SDNode *
N);
498 SDValue visitTRUNCATE_USAT_U(SDNode *
N);
503 SDValue visitSTRICT_FADD(SDNode *
N);
514 SDValue visitFCANONICALIZE(SDNode *
N);
534 SDValue replaceStoreOfFPConstant(StoreSDNode *ST);
535 SDValue replaceStoreOfInsertLoad(StoreSDNode *ST);
537 bool refineExtractVectorEltIntoMultipleNarrowExtractVectorElts(SDNode *
N);
538 SDValue combineStoreConcatTruncVector(StoreSDNode *
N);
540 SDValue visitATOMIC_STORE(SDNode *
N);
541 SDValue visitLIFETIME_END(SDNode *
N);
542 SDValue visitINSERT_VECTOR_ELT(SDNode *
N);
543 SDValue visitEXTRACT_VECTOR_ELT(SDNode *
N);
544 SDValue visitBUILD_VECTOR(SDNode *
N);
545 SDValue visitCONCAT_VECTORS(SDNode *
N);
546 SDValue visitVECTOR_INTERLEAVE(SDNode *
N);
547 SDValue visitEXTRACT_SUBVECTOR(SDNode *
N);
548 SDValue visitVECTOR_SHUFFLE(SDNode *
N);
549 SDValue visitSCALAR_TO_VECTOR(SDNode *
N);
550 SDValue visitINSERT_SUBVECTOR(SDNode *
N);
551 SDValue visitVECTOR_COMPRESS(SDNode *
N);
557 SDValue visitPARTIAL_REDUCE_MLA(SDNode *
N);
558 SDValue visitLOOP_DEPENDENCE_MASK(SDNode *
N);
561 SDValue visitVP_STRIDED_LOAD(SDNode *
N);
562 SDValue visitVP_STRIDED_STORE(SDNode *
N);
569 SDValue visitGET_FPENV_MEM(SDNode *
N);
570 SDValue visitSET_FPENV_MEM(SDNode *
N);
572 SDValue visitFADDForFMACombine(SDNode *
N);
573 SDValue visitFSUBForFMACombine(SDNode *
N);
574 SDValue visitFMULForFMADistributiveCombine(SDNode *
N);
576 SDValue XformToShuffleWithZero(SDNode *
N);
577 bool reassociationCanBreakAddressingModePattern(
unsigned Opc,
583 SDValue N1, SDNodeFlags Flags);
585 SDValue N1, SDNodeFlags Flags);
586 SDValue reassociateReduction(
unsigned RedOpc,
unsigned Opc,
const SDLoc &
DL,
588 SDNodeFlags Flags = SDNodeFlags());
590 SDValue visitShiftByConstant(SDNode *
N);
592 SDValue foldSelectOfConstants(SDNode *
N);
593 SDValue foldVSelectOfConstants(SDNode *
N);
594 SDValue foldBinOpIntoSelect(SDNode *BO);
596 SDValue hoistLogicOpWithSameOpcodeHands(SDNode *
N);
600 bool NotExtCompare =
false);
601 SDValue convertSelectOfFPConstantsToLoadOffset(
604 SDValue foldSignChangeInBitcast(SDNode *
N);
607 SDValue foldSelectOfBinops(SDNode *
N);
611 SDValue foldSubToUSubSat(EVT DstVT, SDNode *
N,
const SDLoc &
DL);
612 SDValue foldABSToABD(SDNode *
N,
const SDLoc &
DL);
617 SDValue unfoldMaskedMerge(SDNode *
N);
618 SDValue unfoldExtremeBitClearingToShifts(SDNode *
N);
620 const SDLoc &
DL,
bool foldBooleans);
624 SDValue &CC,
bool MatchStrict =
false)
const;
625 bool isOneUseSetCC(
SDValue N)
const;
627 SDValue foldAddToAvg(SDNode *
N,
const SDLoc &
DL);
628 SDValue foldSubToAvg(SDNode *
N,
const SDLoc &
DL);
632 SDValue SimplifyNodeWithTwoResults(SDNode *
N,
unsigned LoOp,
634 SDValue CombineConsecutiveLoads(SDNode *
N, EVT VT);
635 SDValue foldBitcastedFPLogic(SDNode *
N, SelectionDAG &DAG,
636 const TargetLowering &TLI);
637 SDValue foldPartialReduceMLAMulOp(SDNode *
N);
638 SDValue foldPartialReduceAdd(SDNode *
N);
641 SDValue CombineZExtLogicopShiftLoad(SDNode *
N);
642 SDValue combineRepeatedFPDivisors(SDNode *
N);
643 SDValue combineFMulOrFDivWithIntPow2(SDNode *
N);
644 SDValue replaceShuffleOfInsert(ShuffleVectorSDNode *Shuf);
645 SDValue mergeInsertEltWithShuffle(SDNode *
N,
unsigned InsIndex);
646 SDValue combineInsertEltToShuffle(SDNode *
N,
unsigned InsIndex);
647 SDValue combineInsertEltToLoad(SDNode *
N,
unsigned InsIndex);
657 bool KnownNeverZero =
false,
658 bool InexpensiveOnly =
false,
659 std::optional<EVT> OutVT = std::nullopt);
669 bool DemandHighBits =
true);
673 bool HasPos,
unsigned PosOpcode,
674 unsigned NegOpcode,
const SDLoc &
DL);
677 bool HasPos,
unsigned PosOpcode,
678 unsigned NegOpcode,
const SDLoc &
DL);
681 SDValue MatchLoadCombine(SDNode *
N);
682 SDValue mergeTruncStores(StoreSDNode *
N);
684 SDValue ReduceLoadOpStoreWidth(SDNode *
N);
686 SDValue TransformFPLoadStorePair(SDNode *
N);
687 SDValue convertBuildVecExtToExt(SDNode *
N);
688 SDValue convertBuildVecZextToBuildVecWithZeros(SDNode *
N);
689 SDValue reduceBuildVecExtToExtBuildVec(SDNode *
N);
690 SDValue reduceBuildVecTruncToBitCast(SDNode *
N);
691 SDValue reduceBuildVecToShuffle(SDNode *
N);
692 SDValue createBuildVecShuffle(
const SDLoc &
DL, SDNode *
N,
693 ArrayRef<int> VectorMask,
SDValue VecIn1,
694 SDValue VecIn2,
unsigned LeftIdx,
696 SDValue matchVSelectOpSizesWithSetCC(SDNode *Cast);
700 void GatherAllAliases(SDNode *
N,
SDValue OriginalChain,
701 SmallVectorImpl<SDValue> &Aliases);
704 bool mayAlias(SDNode *Op0, SDNode *Op1)
const;
716 bool findBetterNeighborChains(StoreSDNode *St);
720 bool parallelizeChainedStores(StoreSDNode *St);
726 LSBaseSDNode *MemNode;
729 int64_t OffsetFromBase;
731 MemOpLink(LSBaseSDNode *
N, int64_t
Offset)
732 : MemNode(
N), OffsetFromBase(
Offset) {}
737 StoreSource getStoreSource(
SDValue StoreVal) {
741 return StoreSource::Constant;
745 return StoreSource::Constant;
746 return StoreSource::Unknown;
749 return StoreSource::Extract;
751 return StoreSource::Load;
753 return StoreSource::Unknown;
761 bool isMulAddWithConstProfitable(SDNode *MulNode,
SDValue AddNode,
767 bool isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
768 EVT LoadResultTy, EVT &ExtVT);
773 EVT &MemVT,
unsigned ShAmt = 0);
776 bool SearchForAndLoads(SDNode *
N, SmallVectorImpl<LoadSDNode*> &Loads,
777 SmallPtrSetImpl<SDNode*> &NodesWithConsts,
778 ConstantSDNode *Mask, SDNode *&NodeToMask);
781 bool BackwardsPropagateMask(SDNode *
N);
785 SDValue getMergeStoreChains(SmallVectorImpl<MemOpLink> &StoreNodes,
797 bool mergeStoresOfConstantsOrVecElts(SmallVectorImpl<MemOpLink> &StoreNodes,
798 EVT MemVT,
unsigned NumStores,
799 bool IsConstantSrc,
bool UseVector,
805 SDNode *getStoreMergeCandidates(StoreSDNode *St,
806 SmallVectorImpl<MemOpLink> &StoreNodes);
812 bool checkMergeStoreCandidatesForDependencies(
813 SmallVectorImpl<MemOpLink> &StoreNodes,
unsigned NumStores,
818 bool hasCallInLdStChain(StoreSDNode *St, LoadSDNode *Ld);
823 unsigned getConsecutiveStores(SmallVectorImpl<MemOpLink> &StoreNodes,
824 int64_t ElementSizeBytes)
const;
828 bool tryStoreMergeOfConstants(SmallVectorImpl<MemOpLink> &StoreNodes,
829 unsigned NumConsecutiveStores,
830 EVT MemVT, SDNode *Root,
bool AllowVectors);
836 bool tryStoreMergeOfExtracts(SmallVectorImpl<MemOpLink> &StoreNodes,
837 unsigned NumConsecutiveStores, EVT MemVT,
842 bool tryStoreMergeOfLoads(SmallVectorImpl<MemOpLink> &StoreNodes,
843 unsigned NumConsecutiveStores, EVT MemVT,
844 SDNode *Root,
bool AllowVectors,
845 bool IsNonTemporalStore,
bool IsNonTemporalLoad);
850 bool mergeConsecutiveStores(StoreSDNode *St);
858 SDValue distributeTruncateThroughAnd(SDNode *
N);
864 bool hasOperation(
unsigned Opcode, EVT VT) {
865 return TLI.isOperationLegalOrCustom(Opcode, VT, LegalOperations);
868 bool hasUMin(EVT VT)
const {
869 auto LK = TLI.getTypeConversion(*DAG.getContext(), VT);
872 TLI.isOperationLegalOrCustom(
ISD::UMIN, LK.second);
879 SelectionDAG &getDAG()
const {
return DAG; }
882 EVT getShiftAmountTy(EVT LHSTy) {
883 return TLI.getShiftAmountTy(LHSTy, DAG.getDataLayout());
888 bool isTypeLegal(
const EVT &VT) {
889 if (!LegalTypes)
return true;
890 return TLI.isTypeLegal(VT);
894 EVT getSetCCResultType(EVT VT)
const {
895 return TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
898 void ExtendSetCCUses(
const SmallVectorImpl<SDNode *> &SetCCs,
909 explicit WorklistRemover(DAGCombiner &dc)
910 : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
912 void NodeDeleted(SDNode *
N, SDNode *
E)
override {
913 DC.removeFromWorklist(
N);
921 explicit WorklistInserter(DAGCombiner &dc)
922 : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
926 void NodeInserted(SDNode *
N)
override { DC.ConsiderForPruning(
N); }
936 ((DAGCombiner*)
DC)->AddToWorklist(
N);
941 return ((DAGCombiner*)
DC)->CombineTo(
N, &To[0], To.
size(), AddTo);
946 return ((DAGCombiner*)
DC)->CombineTo(
N, Res, AddTo);
951 return ((DAGCombiner*)
DC)->CombineTo(
N, Res0, Res1, AddTo);
956 return ((DAGCombiner*)
DC)->recursivelyDeleteUnusedNodes(
N);
961 return ((DAGCombiner*)
DC)->CommitTargetLoweringOpt(TLO);
968void DAGCombiner::deleteAndRecombine(
SDNode *
N) {
969 removeFromWorklist(
N);
977 if (
Op->hasOneUse() ||
Op->getNumValues() > 1)
978 AddToWorklist(
Op.getNode());
987 unsigned Bits =
Offset + std::max(
LHS.getBitWidth(),
RHS.getBitWidth());
998 SDValue &CC,
bool MatchStrict)
const {
1000 LHS =
N.getOperand(0);
1001 RHS =
N.getOperand(1);
1009 LHS =
N.getOperand(1);
1010 RHS =
N.getOperand(2);
1023 LHS =
N.getOperand(0);
1024 RHS =
N.getOperand(1);
1032bool DAGCombiner::isOneUseSetCC(
SDValue N)
const {
1034 if (isSetCCEquivalent(
N, N0, N1, N2) &&
N->hasOneUse())
1046 MaskForTy = 0xFFULL;
1049 MaskForTy = 0xFFFFULL;
1052 MaskForTy = 0xFFFFFFFFULL;
1070 bool AllowTruncation =
false) {
1072 return !(Const->isOpaque() && NoOpaques);
1075 unsigned BitWidth =
N.getScalarValueSizeInBits();
1080 if (!Const || (Const->isOpaque() && NoOpaques))
1084 if ((AllowTruncation &&
1085 Const->getAPIntValue().getActiveBits() >
BitWidth) ||
1086 (!AllowTruncation && Const->getAPIntValue().getBitWidth() !=
BitWidth))
1108bool DAGCombiner::reassociationCanBreakAddressingModePattern(
unsigned Opc,
1136 : (N1.
getOperand(0).getConstantOperandVal(0) *
1141 ScalableOffset = -ScalableOffset;
1142 if (
all_of(
N->users(), [&](SDNode *Node) {
1143 if (auto *LoadStore = dyn_cast<MemSDNode>(Node);
1144 LoadStore && LoadStore->hasUniqueMemOperand() &&
1145 LoadStore->getBasePtr().getNode() == N) {
1146 TargetLoweringBase::AddrMode AM;
1147 AM.HasBaseReg = true;
1148 AM.ScalableOffset = ScalableOffset;
1149 EVT VT = LoadStore->getMemoryVT();
1150 unsigned AS = LoadStore->getAddressSpace();
1151 Type *AccessTy = VT.getTypeForEVT(*DAG.getContext());
1152 return TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy,
1167 const APInt &C2APIntVal = C2->getAPIntValue();
1175 const APInt &C1APIntVal = C1->getAPIntValue();
1176 const APInt CombinedValueIntVal = C1APIntVal + C2APIntVal;
1179 const int64_t CombinedValue = CombinedValueIntVal.
getSExtValue();
1181 for (SDNode *Node :
N->users()) {
1188 TargetLoweringBase::AddrMode AM;
1190 AM.
BaseOffs = C2APIntVal.getSExtValue();
1192 unsigned AS =
LoadStore->getAddressSpace();
1208 for (SDNode *Node :
N->users()) {
1210 if (!LoadStore || !
LoadStore->hasUniqueMemOperand())
1215 TargetLoweringBase::AddrMode AM;
1217 AM.
BaseOffs = C2APIntVal.getSExtValue();
1219 unsigned AS =
LoadStore->getAddressSpace();
1232SDValue DAGCombiner::reassociateOpsCommutative(
unsigned Opc,
const SDLoc &
DL,
1234 SDNodeFlags Flags) {
1244 SDNodeFlags NewFlags;
1246 Flags.hasNoUnsignedWrap())
1254 return DAG.
getNode(
Opc,
DL, VT, N00, OpNode, NewFlags);
1262 return DAG.
getNode(
Opc,
DL, VT, OpNode, N01, NewFlags);
1272 if (N1 == N00 || N1 == N01)
1318 if (CC1 == CC00 && CC1 != CC01) {
1322 if (CC1 == CC01 && CC1 != CC00) {
1336 SDValue N1, SDNodeFlags Flags) {
1342 if (!
Flags.hasAllowReassociation() || !
Flags.hasNoSignedZeros())
1345 if (
SDValue Combined = reassociateOpsCommutative(
Opc,
DL, N0, N1, Flags))
1347 if (
SDValue Combined = reassociateOpsCommutative(
Opc,
DL, N1, N0, Flags))
1355SDValue DAGCombiner::reassociateReduction(
unsigned RedOpc,
unsigned Opc,
1357 SDValue N1, SDNodeFlags Flags) {
1363 SelectionDAG::FlagInserter FlagsInserter(DAG, Flags);
1381 A.getValueType() ==
C.getValueType() &&
1382 hasOperation(
Opc,
A.getValueType()) &&
1390 SelectionDAG::FlagInserter FlagsInserter(
1414 X.getValueType() !=
Y.getValueType() ||
1415 !hasOperation(
Opc,
X.getValueType()) ||
1419 (!Chain->getFlags().hasAllowReassociation() ||
1423 SelectionDAG::FlagInserter FlagsInserter(
1429 if (
SDValue V = FoldReductionChain(N0, N1))
1431 if (
SDValue V = FoldReductionChain(N1, N0))
1437SDValue DAGCombiner::CombineTo(SDNode *
N,
const SDValue *To,
unsigned NumTo,
1439 assert(
N->getNumValues() == NumTo &&
"Broken CombineTo call!");
1443 dbgs() <<
" and " << NumTo - 1 <<
" other values\n");
1444 for (
unsigned i = 0, e = NumTo; i !=
e; ++i)
1446 N->getValueType(i) == To[i].getValueType()) &&
1447 "Cannot combine value to value of different type!");
1449 WorklistRemover DeadNodes(*
this);
1453 for (
unsigned i = 0, e = NumTo; i !=
e; ++i) {
1455 AddToWorklistWithUsers(To[i].
getNode());
1463 deleteAndRecombine(
N);
1468CommitTargetLoweringOpt(
const TargetLowering::TargetLoweringOpt &TLO) {
1481 recursivelyDeleteUnusedNodes(TLO.
Old.
getNode());
1486bool DAGCombiner::SimplifyDemandedBits(
SDValue Op,
const APInt &DemandedBits,
1487 const APInt &DemandedElts,
1488 bool AssumeSingleUse) {
1489 TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
1496 AddToWorklist(
Op.getNode());
1498 CommitTargetLoweringOpt(TLO);
1505bool DAGCombiner::SimplifyDemandedVectorElts(
SDValue Op,
1506 const APInt &DemandedElts,
1507 bool AssumeSingleUse) {
1508 TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
1509 APInt KnownUndef, KnownZero;
1511 TLO, 0, AssumeSingleUse))
1515 AddToWorklist(
Op.getNode());
1517 CommitTargetLoweringOpt(TLO);
1521void DAGCombiner::ReplaceLoadWithPromotedLoad(SDNode *
Load, SDNode *ExtLoad) {
1523 EVT VT =
Load->getValueType(0);
1532 AddToWorklist(Trunc.
getNode());
1533 recursivelyDeleteUnusedNodes(
Load);
1541 EVT MemVT =
LD->getMemoryVT();
1543 :
LD->getExtensionType();
1546 LD->getChain(),
LD->getBasePtr(),
1547 MemVT,
LD->getMemOperand());
1550 unsigned Opc =
Op.getOpcode();
1554 if (
SDValue Op0 = SExtPromoteOperand(
Op.getOperand(0), PVT))
1558 if (
SDValue Op0 = ZExtPromoteOperand(
Op.getOperand(0), PVT))
1576 EVT OldVT =
Op.getValueType();
1582 AddToWorklist(NewOp.
getNode());
1585 ReplaceLoadWithPromotedLoad(
Op.getNode(), NewOp.
getNode());
1591 EVT OldVT =
Op.getValueType();
1597 AddToWorklist(NewOp.
getNode());
1600 ReplaceLoadWithPromotedLoad(
Op.getNode(), NewOp.
getNode());
1608 if (!LegalOperations)
1611 EVT VT =
Op.getValueType();
1617 unsigned Opc =
Op.getOpcode();
1625 assert(PVT != VT &&
"Don't know what type to promote to!");
1629 bool Replace0 =
false;
1631 SDValue NN0 = PromoteOperand(N0, PVT, Replace0);
1633 bool Replace1 =
false;
1635 SDValue NN1 = PromoteOperand(N1, PVT, Replace1);
1647 Replace1 &= (N0 != N1) && !N1->
hasOneUse();
1650 CombineTo(
Op.getNode(), RV);
1676 if (!LegalOperations)
1679 EVT VT =
Op.getValueType();
1685 unsigned Opc =
Op.getOpcode();
1693 assert(PVT != VT &&
"Don't know what type to promote to!");
1697 SDNodeFlags TruncFlags;
1701 N0 = SExtPromoteOperand(N0, PVT);
1703 N0 = ZExtPromoteOperand(N0, PVT);
1705 if (
Op->getFlags().hasNoUnsignedWrap()) {
1706 N0 = ZExtPromoteOperand(N0, PVT);
1708 }
else if (
Op->getFlags().hasNoSignedWrap()) {
1709 N0 = SExtPromoteOperand(N0, PVT);
1712 N0 = PromoteOperand(N0, PVT,
Replace);
1725 ReplaceLoadWithPromotedLoad(
Op.getOperand(0).getNode(), N0.
getNode());
1735 if (!LegalOperations)
1738 EVT VT =
Op.getValueType();
1744 unsigned Opc =
Op.getOpcode();
1752 assert(PVT != VT &&
"Don't know what type to promote to!");
1757 return DAG.
getNode(
Op.getOpcode(), SDLoc(
Op), VT,
Op.getOperand(0));
1762bool DAGCombiner::PromoteLoad(
SDValue Op) {
1763 if (!LegalOperations)
1769 EVT VT =
Op.getValueType();
1775 unsigned Opc =
Op.getOpcode();
1783 assert(PVT != VT &&
"Don't know what type to promote to!");
1786 SDNode *
N =
Op.getNode();
1788 EVT MemVT =
LD->getMemoryVT();
1790 :
LD->getExtensionType();
1792 LD->getChain(),
LD->getBasePtr(),
1793 MemVT,
LD->getMemOperand());
1802 AddToWorklist(
Result.getNode());
1803 recursivelyDeleteUnusedNodes(
N);
1816bool DAGCombiner::recursivelyDeleteUnusedNodes(SDNode *
N) {
1817 if (!
N->use_empty())
1820 SmallSetVector<SDNode *, 16> Nodes;
1827 if (
N->use_empty()) {
1828 for (
const SDValue &ChildN :
N->op_values())
1829 Nodes.
insert(ChildN.getNode());
1831 removeFromWorklist(
N);
1836 }
while (!Nodes.
empty());
1855 WorklistInserter AddNodes(*
this);
1857 if (UseTopologicalSorting)
1866 if (UseTopologicalSorting) {
1868 AddToWorklist(&Node,
Node.use_empty());
1870 for (SDNode &Node : DAG.
allnodes())
1871 AddToWorklist(&Node,
Node.use_empty());
1877 HandleSDNode Dummy(DAG.
getRoot());
1880 while (SDNode *
N = getNextWorklistEntry()) {
1884 if (recursivelyDeleteUnusedNodes(
N))
1887 WorklistRemover DeadNodes(*
this);
1892 SmallSetVector<SDNode *, 16> UpdatedNodes;
1895 for (SDNode *LN : UpdatedNodes)
1896 AddToWorklistWithUsers(LN);
1908 for (
const SDValue &ChildN :
N->op_values())
1909 AddToWorklist(ChildN.getNode(),
true,
1920 ChainsWithoutMergeableStores.
clear();
1931 "Node was deleted but visit returned new node!");
1939 N->getNumValues() == 1 &&
"Type mismatch");
1949 AddToWorklistWithUsers(RV.
getNode());
1955 recursivelyDeleteUnusedNodes(
N);
1959 DAG.
setRoot(Dummy.getValue());
1963SDValue DAGCombiner::visit(SDNode *
N) {
1965 switch (
N->getOpcode()) {
2116 return visitPARTIAL_REDUCE_MLA(
N);
2119 return visitLOOP_DEPENDENCE_MASK(
N);
2147#define BEGIN_REGISTER_VP_SDNODE(SDOPC, ...) case ISD::SDOPC:
2148#include "llvm/IR/VPIntrinsics.def"
2149 return visitVPOp(
N);
2155SDValue DAGCombiner::combine(SDNode *
N) {
2160 if (!DisableGenericCombines)
2166 "Node was deleted but visit returned NULL!");
2172 TargetLowering::DAGCombinerInfo
2173 DagCombineInfo(DAG, Level,
false,
this);
2181 switch (
N->getOpcode()) {
2189 RV = PromoteIntBinOp(
SDValue(
N, 0));
2194 RV = PromoteIntShiftOp(
SDValue(
N, 0));
2230 if (
unsigned NumOps =
N->getNumOperands()) {
2231 if (
N->getOperand(0).getValueType() == MVT::Other)
2232 return N->getOperand(0);
2233 if (
N->getOperand(
NumOps-1).getValueType() == MVT::Other)
2234 return N->getOperand(
NumOps-1);
2235 for (
unsigned i = 1; i <
NumOps-1; ++i)
2236 if (
N->getOperand(i).getValueType() == MVT::Other)
2237 return N->getOperand(i);
2242SDValue DAGCombiner::visitFCANONICALIZE(SDNode *
N) {
2243 SDValue Operand =
N->getOperand(0);
2255SDValue DAGCombiner::visitTokenFactor(SDNode *
N) {
2258 if (
N->getNumOperands() == 2) {
2260 return N->getOperand(0);
2262 return N->getOperand(1);
2277 AddToWorklist(*(
N->user_begin()));
2281 SmallPtrSet<SDNode*, 16> SeenOps;
2289 for (
unsigned i = 0; i < TFs.
size(); ++i) {
2294 for (
unsigned j = i;
j < TFs.
size();
j++)
2295 Ops.emplace_back(TFs[j], 0);
2302 SDNode *TF = TFs[i];
2305 switch (
Op.getOpcode()) {
2323 if (SeenOps.
insert(
Op.getNode()).second)
2334 for (
unsigned i = 1, e = TFs.
size(); i < e; i++)
2335 AddToWorklist(TFs[i]);
2345 SmallVector<unsigned, 8> OpWorkCount;
2346 SmallPtrSet<SDNode *, 16> SeenChains;
2347 bool DidPruneOps =
false;
2349 unsigned NumLeftToConsider = 0;
2351 Worklist.
push_back(std::make_pair(
Op.getNode(), NumLeftToConsider++));
2355 auto AddToWorklist = [&](
unsigned CurIdx, SDNode *
Op,
unsigned OpNumber) {
2361 unsigned OrigOpNumber = 0;
2362 while (OrigOpNumber <
Ops.size() &&
Ops[OrigOpNumber].getNode() !=
Op)
2365 "expected to find TokenFactor Operand");
2367 for (
unsigned i = CurIdx + 1; i < Worklist.
size(); ++i) {
2368 if (Worklist[i].second == OrigOpNumber) {
2369 Worklist[i].second = OpNumber;
2372 OpWorkCount[OpNumber] += OpWorkCount[OrigOpNumber];
2373 OpWorkCount[OrigOpNumber] = 0;
2374 NumLeftToConsider--;
2377 if (SeenChains.
insert(
Op).second) {
2378 OpWorkCount[OpNumber]++;
2383 for (
unsigned i = 0; i < Worklist.
size() && i < 1024; ++i) {
2385 if (NumLeftToConsider <= 1)
2387 auto CurNode = Worklist[i].first;
2388 auto CurOpNumber = Worklist[i].second;
2389 assert((OpWorkCount[CurOpNumber] > 0) &&
2390 "Node should not appear in worklist");
2391 switch (CurNode->getOpcode()) {
2397 NumLeftToConsider++;
2400 for (
const SDValue &
Op : CurNode->op_values())
2401 AddToWorklist(i,
Op.getNode(), CurOpNumber);
2407 AddToWorklist(i, CurNode->getOperand(0).getNode(), CurOpNumber);
2411 AddToWorklist(i, MemNode->getChain().getNode(), CurOpNumber);
2414 OpWorkCount[CurOpNumber]--;
2415 if (OpWorkCount[CurOpNumber] == 0)
2416 NumLeftToConsider--;
2430 if (SeenChains.
count(
Op.getNode()) == 0)
2444SDValue DAGCombiner::visitMERGE_VALUES(SDNode *
N) {
2445 WorklistRemover DeadNodes(*
this);
2451 AddUsersToWorklist(
N);
2456 }
while (!
N->use_empty());
2457 deleteAndRecombine(
N);
2465 return Const !=
nullptr && !Const->isOpaque() ? Const :
nullptr;
2475 Op =
N->getOperand(0);
2477 if (
N->getFlags().hasNoUnsignedWrap())
2478 Known.Zero.setBitsFrom(
N.getScalarValueSizeInBits());
2482 if (
N.getValueType().getScalarType() != MVT::i1 ||
2499 if (LD->isIndexed() || LD->getBasePtr().getNode() !=
N)
2501 VT = LD->getMemoryVT();
2502 AS = LD->getAddressSpace();
2504 if (ST->isIndexed() || ST->getBasePtr().getNode() !=
N)
2506 VT = ST->getMemoryVT();
2507 AS = ST->getAddressSpace();
2509 if (LD->isIndexed() || LD->getBasePtr().getNode() !=
N)
2511 VT = LD->getMemoryVT();
2512 AS = LD->getAddressSpace();
2514 if (ST->isIndexed() || ST->getBasePtr().getNode() !=
N)
2516 VT = ST->getMemoryVT();
2517 AS = ST->getAddressSpace();
2523 if (
N->isAnyAdd()) {
2532 }
else if (
N->getOpcode() ==
ISD::SUB) {
2554 bool ShouldCommuteOperands) {
2560 if (ShouldCommuteOperands)
2574 unsigned Opcode =
N->getOpcode();
2575 EVT VT =
N->getValueType(0);
2580 unsigned OpNo = ShouldCommuteOperands ? 0 : 1;
2600SDValue DAGCombiner::foldBinOpIntoSelect(SDNode *BO) {
2603 "Unexpected binary operator");
2615 unsigned SelOpNo = 0;
2652 bool CanFoldNonConst =
2658 if (!CanFoldNonConst &&
2667 if (CanFoldNonConst) {
2686 : DAG.FoldConstantArithmetic(BinOpcode,
DL, VT, {CT, CBO});
2691 : DAG.FoldConstantArithmetic(BinOpcode,
DL, VT, {CF, CBO});
2702 "Expecting add or sub");
2707 bool IsAdd =
N->getOpcode() ==
ISD::ADD;
2708 SDValue C = IsAdd ?
N->getOperand(1) :
N->getOperand(0);
2709 SDValue Z = IsAdd ?
N->getOperand(0) :
N->getOperand(1);
2715 if (Z.getOperand(0).getValueType() != MVT::i1)
2727 EVT VT =
C.getValueType();
2735SDValue DAGCombiner::foldSubToAvg(SDNode *
N,
const SDLoc &
DL) {
2740 if ((!LegalOperations || hasOperation(
ISD::AVGCEILU, VT)) &&
2745 if ((!LegalOperations || hasOperation(
ISD::AVGCEILS, VT)) &&
2756SDValue DAGCombiner::visitPTRADD(SDNode *
N) {
2766 "PTRADD with different operand types is not supported");
2777 !reassociationCanBreakAddressingModePattern(
ISD::PTRADD,
DL,
N, N0, N1)) {
2788 if ((YIsConstant && N0OneUse) || (YIsConstant && ZIsConstant)) {
2793 AddToWorklist(
Add.getNode());
2817 if (
const GlobalAddressSDNode *GA =
2832 AddToWorklist(Inner.
getNode());
2854 SDNodeFlags CommonFlags =
N->getFlags() & N1->
getFlags();
2862 if (ZIsConstant != YIsConstant) {
2866 AddToWorklist(Inner.
getNode());
2876 bool TransformCannotBreakAddrMode =
none_of(
N->users(), [&](SDNode *User) {
2877 return canFoldInAddressingMode(N, User, DAG, TLI);
2880 if (TransformCannotBreakAddrMode)
2892 "Expecting add or sub");
2896 bool IsAdd =
N->getOpcode() ==
ISD::ADD;
2897 SDValue ConstantOp = IsAdd ?
N->getOperand(1) :
N->getOperand(0);
2898 SDValue ShiftOp = IsAdd ?
N->getOperand(0) :
N->getOperand(1);
2920 {ConstantOp, DAG.getConstant(1, DL, VT)})) {
2922 Not.getOperand(0), ShAmt);
2938SDValue DAGCombiner::visitADDLike(SDNode *
N) {
2964 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
2996 if ((!LegalOperations ||
2999 X.getScalarValueSizeInBits() == 1) {
3015 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
3019 if (!reassociationCanBreakAddressingModePattern(
ISD::ADD,
DL,
N, N0, N1)) {
3031 SDNodeFlags NewFlags =
3121 auto MatchUSUBSAT = [](ConstantSDNode *
Max, ConstantSDNode *
Op) {
3122 return (!Max && !
Op) ||
3123 (
Max &&
Op &&
Max->getAPIntValue() == (-
Op->getAPIntValue()));
3164 !
N->getFlags().hasNoSignedWrap()))) {
3185 (CA * CM + CB->getAPIntValue()).getSExtValue())) {
3189 if (
N->getFlags().hasNoUnsignedWrap() &&
3193 if (
N->getFlags().hasNoSignedWrap() &&
3202 DAG.
getConstant(CA * CM + CB->getAPIntValue(),
DL, VT), Flags);
3210 (CA * CM + CB->getAPIntValue()).getSExtValue())) {
3216 if (
N->getFlags().hasNoUnsignedWrap() &&
3221 if (
N->getFlags().hasNoSignedWrap() &&
3232 DAG.
getConstant(CA * CM + CB->getAPIntValue(),
DL, VT), Flags);
3237 if (
SDValue Combined = visitADDLikeCommutative(N0, N1,
DL))
3240 if (
SDValue Combined = visitADDLikeCommutative(N1, N0,
DL))
3249SDValue DAGCombiner::foldAddToAvg(SDNode *
N,
const SDLoc &
DL) {
3275 if ((!LegalOperations || hasOperation(
ISD::AVGCEILU, VT)) &&
3282 if ((!LegalOperations || hasOperation(
ISD::AVGCEILS, VT)) &&
3293SDValue DAGCombiner::visitADD(SDNode *
N) {
3299 if (
SDValue Combined = visitADDLike(
N))
3308 if (
SDValue V = MatchRotate(N0, N1, SDLoc(
N),
true))
3342 APInt NewStep = C0 + C1;
3352 APInt NewStep = SV0 + SV1;
3360SDValue DAGCombiner::visitADDSAT(SDNode *
N) {
3361 unsigned Opcode =
N->getOpcode();
3379 return DAG.
getNode(Opcode,
DL, VT, N1, N0);
3383 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
3403 bool ForceCarryReconstruction =
false) {
3408 if (ForceCarryReconstruction && V.getValueType() == MVT::i1)
3412 V = V.getOperand(0);
3417 if (ForceCarryReconstruction)
3421 V = V.getOperand(0);
3429 if (V.getResNo() != 1)
3436 EVT VT = V->getValueType(0);
3543 if (TN->
getVT() == MVT::i1) {
3560 DAG.
getVTList(VT, Carry.getValueType()), N0,
3566SDValue DAGCombiner::visitADDC(SDNode *
N) {
3573 if (!
N->hasAnyUseOfValue(1))
3613 return V.getOperand(0);
3619SDValue DAGCombiner::visitADDO(SDNode *
N) {
3625 EVT CarryVT =
N->getValueType(1);
3629 if (!
N->hasAnyUseOfValue(1))
3636 return DAG.
getNode(
N->getOpcode(),
DL,
N->getVTList(), N1, N0);
3661 if (
SDValue Combined = visitUADDOLike(N0, N1,
N))
3664 if (
SDValue Combined = visitUADDOLike(N1, N0,
N))
3695SDValue DAGCombiner::visitADDE(SDNode *
N) {
3714SDValue DAGCombiner::visitUADDO_CARRY(SDNode *
N) {
3728 if (!LegalOperations ||
3738 AddToWorklist(CarryExt.
getNode());
3744 if (
SDValue Combined = visitUADDO_CARRYLike(N0, N1, CarryIn,
N))
3747 if (
SDValue Combined = visitUADDO_CARRYLike(N1, N0, CarryIn,
N))
3894 EVT CarryOutType =
N->getValueType(0);
3910 unsigned CarryInOperandNum =
3912 if (Opcode ==
ISD::USUBO && CarryInOperandNum != 1)
3965 EVT IntVT =
A.getValueType();
4030SDValue DAGCombiner::visitSADDO_CARRY(SDNode *
N) {
4044 if (!LegalOperations ||
4049 if (
SDValue Combined = visitSADDO_CARRYLike(N0, N1, CarryIn,
N))
4052 if (
SDValue Combined = visitSADDO_CARRYLike(N1, N0, CarryIn,
N))
4064 "Illegal truncation");
4088SDValue DAGCombiner::foldSubToUSubSat(EVT DstVT, SDNode *
N,
const SDLoc &
DL) {
4090 !(!LegalOperations || hasOperation(
ISD::USUBSAT, DstVT)))
4093 EVT SubVT =
N->getValueType(0);
4180 if ((
BitWidth - Src.getValueType().getScalarSizeInBits()) != BitWidthDiff)
4190 unsigned AndMaskWidth =
BitWidth - BitWidthDiff;
4191 if (!(AndMask.
isMask(AndMaskWidth) && XorMask.
countr_one() >= AndMaskWidth))
4226 if (
SDValue Res = CheckAndFoldMulCase(Mul0, Mul1))
4229 if (
SDValue Res = CheckAndFoldMulCase(Mul1, Mul0))
4267SDValue DAGCombiner::visitSUB(SDNode *
N) {
4287 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
4314 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
4337 if (
N->getFlags().hasNoUnsignedWrap())
4343 if (
N->getFlags().hasNoSignedWrap())
4369 if (hasOperation(NewOpc, VT))
4511 if (!reassociationCanBreakAddressingModePattern(
ISD::SUB,
DL,
N, N0, N1) &&
4549 if ((!LegalOperations || hasOperation(
ISD::ABS, VT)) &&
4559 if (GA->getGlobal() == GB->getGlobal())
4569 if (TN->
getVT() == MVT::i1) {
4628 DAG.
getVTList(VT, Carry.getValueType()), NegX, Zero,
4634 const APInt &C0Val = C0->getAPIntValue();
4637 if (
N->getFlags().hasNoUnsignedWrap() && C0Val.
isMask())
4642 if (!C0->isOpaque()) {
4643 const APInt &MaybeOnes = ~DAG.computeKnownBits(N1).Zero;
4644 if ((C0Val - MaybeOnes) == (C0Val ^ MaybeOnes))
4650 if ((!LegalOperations || hasOperation(
ISD::ABDS, VT)) &&
4662 if ((!LegalOperations || hasOperation(
ISD::ABDU, VT)) &&
4676SDValue DAGCombiner::visitSUBSAT(SDNode *
N) {
4677 unsigned Opcode =
N->getOpcode();
4698 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
4724 NarrowBits != 0 && NarrowBits < ScalarBits; NarrowBits *= 2) {
4725 unsigned Scale = ScalarBits / NarrowBits;
4753SDValue DAGCombiner::visitSUBC(SDNode *
N) {
4760 if (!
N->hasAnyUseOfValue(1))
4781SDValue DAGCombiner::visitSUBO(SDNode *
N) {
4787 EVT CarryVT =
N->getValueType(1);
4791 if (!
N->hasAnyUseOfValue(1))
4823SDValue DAGCombiner::visitSUBE(SDNode *
N) {
4835SDValue DAGCombiner::visitUSUBO_CARRY(SDNode *
N) {
4842 if (!LegalOperations ||
4850 !
N->hasAnyUseOfValue(1))
4857SDValue DAGCombiner::visitSSUBO_CARRY(SDNode *
N) {
4864 if (!LegalOperations ||
4874SDValue DAGCombiner::visitMULFIX(SDNode *
N) {
4887 return DAG.
getNode(
N->getOpcode(), SDLoc(
N), VT, N1, N0, Scale);
4896SDValue DAGCombiner::visitMUL(SDNode *
N) {
4916 bool N1IsConst =
false;
4917 bool N1IsOpaqueConst =
false;
4922 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
4927 "Splat APInt should be element width");
4937 if (N1IsConst && ConstValue1.
isZero())
4941 if (N1IsConst && ConstValue1.
isOne())
4944 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
4948 if (N1IsConst && ConstValue1.
isAllOnes())
4954 if (
SDValue LogBase2 = BuildLogBase2(N1,
DL)) {
4958 Flags.setNoUnsignedWrap(
N->getFlags().hasNoUnsignedWrap());
4961 if (
N->getFlags().hasNoSignedWrap() && N1IsConst &&
4963 Flags.setNoSignedWrap(
true);
4970 unsigned Log2Val = (-ConstValue1).logBase2();
4984 SDVTList LoHiVT = DAG.
getVTList(VT, VT);
4987 if (LoHi->hasAnyUseOfValue(1))
4990 if (LoHi->hasAnyUseOfValue(1))
5015 APInt MulC = ConstValue1.
abs();
5017 unsigned TZeros = MulC == 2 ? 0 : MulC.
countr_zero();
5019 if ((MulC - 1).isPowerOf2())
5021 else if ((MulC + 1).isPowerOf2())
5026 MathOp ==
ISD::ADD ? (MulC - 1).logBase2() : (MulC + 1).logBase2();
5029 "multiply-by-constant generated out of bounds shift");
5088 APInt NewStep = C0 * MulVal;
5094 if ((!LegalOperations || hasOperation(
ISD::ABS, VT)) &&
5107 SmallBitVector ClearMask;
5109 auto IsClearMask = [&ClearMask](ConstantSDNode *
V) {
5110 if (!V ||
V->isZero()) {
5124 for (
unsigned I = 0;
I != NumElts; ++
I)
5154 switch (
NodeType.getSimpleVT().SimpleTy) {
5155 default:
return false;
5156 case MVT::i8: LC=
isSigned ? RTLIB::SDIVREM_I8 : RTLIB::UDIVREM_I8;
break;
5157 case MVT::i16: LC=
isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16;
break;
5158 case MVT::i32: LC=
isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32;
break;
5159 case MVT::i64: LC=
isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64;
break;
5160 case MVT::i128: LC=
isSigned ? RTLIB::SDIVREM_I128:RTLIB::UDIVREM_I128;
break;
5167SDValue DAGCombiner::useDivRem(SDNode *Node) {
5168 if (
Node->use_empty())
5171 unsigned Opcode =
Node->getOpcode();
5176 EVT VT =
Node->getValueType(0);
5190 unsigned OtherOpcode = 0;
5204 for (SDNode *User : Op0->
users()) {
5211 unsigned UserOpc =
User->getOpcode();
5212 if ((UserOpc == Opcode || UserOpc == OtherOpcode || UserOpc == DivRemOpc) &&
5213 User->getOperand(0) == Op0 &&
5214 User->getOperand(1) == Op1) {
5216 if (UserOpc == OtherOpcode) {
5218 combined = DAG.
getNode(DivRemOpc, SDLoc(Node), VTs, Op0, Op1);
5219 }
else if (UserOpc == DivRemOpc) {
5222 assert(UserOpc == Opcode);
5227 CombineTo(User, combined);
5229 CombineTo(User, combined.
getValue(1));
5238 EVT VT =
N->getValueType(0);
5241 unsigned Opc =
N->getOpcode();
5260 if (N0C && N0C->
isZero())
5280SDValue DAGCombiner::visitSDIV(SDNode *
N) {
5283 EVT VT =
N->getValueType(0);
5293 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5310 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
5318 if (
SDValue V = visitSDIVLike(N0, N1,
N)) {
5325 if (!
N->getFlags().hasExact()) {
5328 AddToWorklist(
Mul.getNode());
5329 AddToWorklist(
Sub.getNode());
5330 CombineTo(RemNode,
Sub);
5351 if (
C->isZero() ||
C->isOpaque())
5353 if (
C->getAPIntValue().isPowerOf2())
5355 if (
C->getAPIntValue().isNegatedPowerOf2())
5366 EVT VT =
N->getValueType(0);
5377 if ((!
N->getFlags().hasExact() ||
BitWidth > MaxLegalDivRemBitWidth) &&
5395 AddToWorklist(Sign.
getNode());
5401 AddToWorklist(
Add.getNode());
5412 Sra = DAG.
getSelect(
DL, VT, IsOneOrAllOnes, N0, Sra);
5438SDValue DAGCombiner::visitUDIV(SDNode *
N) {
5441 EVT VT =
N->getValueType(0);
5451 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5465 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
5468 if (
SDValue V = visitUDIVLike(N0, N1,
N)) {
5475 if (!
N->getFlags().hasExact()) {
5478 AddToWorklist(
Mul.getNode());
5479 AddToWorklist(
Sub.getNode());
5480 CombineTo(RemNode,
Sub);
5505 EVT VT =
N->getValueType(0);
5510 if (
SDValue LogBase2 = BuildLogBase2(N1,
DL)) {
5511 AddToWorklist(LogBase2.getNode());
5515 AddToWorklist(Trunc.
getNode());
5525 if (
SDValue LogBase2 = BuildLogBase2(N10,
DL)) {
5526 AddToWorklist(LogBase2.getNode());
5530 AddToWorklist(Trunc.
getNode());
5532 AddToWorklist(
Add.getNode());
5560SDValue DAGCombiner::visitREM(SDNode *
N) {
5561 unsigned Opcode =
N->getOpcode();
5564 EVT VT =
N->getValueType(0);
5586 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
5599 AddToWorklist(
Add.getNode());
5616 if (
SDValue OptimizedRem = buildOptimizedSREM(N0, N1,
N))
5617 return OptimizedRem;
5621 isSigned ? visitSDIVLike(N0, N1,
N) : visitUDIVLike(N0, N1,
N);
5624 unsigned DivOpcode = isSigned ? ISD::SDIV : ISD::UDIV;
5625 if (SDNode *DivNode = DAG.getNodeIfExists(DivOpcode, N->getVTList(),
5627 CombineTo(DivNode, OptimizedDiv);
5630 AddToWorklist(OptimizedDiv.
getNode());
5631 AddToWorklist(
Mul.getNode());
5638 return DivRem.getValue(1);
5661SDValue DAGCombiner::visitMULHS(SDNode *
N) {
5664 EVT VT =
N->getValueType(0);
5677 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5720SDValue DAGCombiner::visitMULHU(SDNode *
N) {
5723 EVT VT =
N->getValueType(0);
5736 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5760 (!LegalOperations || hasOperation(
ISD::SRL, VT))) {
5761 if (
SDValue LogBase2 = BuildLogBase2(N1,
DL)) {
5776 unsigned SimpleSize =
Simple.getSizeInBits();
5797SDValue DAGCombiner::visitAVG(SDNode *
N) {
5798 unsigned Opcode =
N->getOpcode();
5801 EVT VT =
N->getValueType(0);
5812 return DAG.
getNode(Opcode,
DL,
N->getVTList(), N1, N0);
5815 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5841 X.getValueType() ==
Y.getValueType() &&
5842 hasOperation(Opcode,
X.getValueType())) {
5848 X.getValueType() ==
Y.getValueType() &&
5849 hasOperation(Opcode,
X.getValueType())) {
5880 if (IsSigned &&
Add->getFlags().hasNoSignedWrap())
5883 if (!IsSigned &&
Add->getFlags().hasNoUnsignedWrap())
5897SDValue DAGCombiner::visitABD(SDNode *
N) {
5898 unsigned Opcode =
N->getOpcode();
5901 EVT VT =
N->getValueType(0);
5911 return DAG.
getNode(Opcode,
DL,
N->getVTList(), N1, N0);
5914 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5929 (!LegalOperations || hasOperation(
ISD::ABS, VT)))
5944 EVT SmallVT =
X.getScalarValueSizeInBits() >
Y.getScalarValueSizeInBits()
5947 if (!LegalOperations || hasOperation(Opcode, SmallVT)) {
5959 EVT SmallVT =
X.getValueType();
5960 if (!LegalOperations || hasOperation(Opcode, SmallVT)) {
5962 unsigned RelevantBits =
5971 const APInt &YConst =
C->getAsAPIntVal();
5978 if (RelevantBits <= Bits && TruncatingYIsCheap) {
5992SDValue DAGCombiner::SimplifyNodeWithTwoResults(SDNode *
N,
unsigned LoOp,
5995 bool HiExists =
N->hasAnyUseOfValue(1);
5996 if (!HiExists && (!LegalOperations ||
5999 return CombineTo(
N, Res, Res);
6003 bool LoExists =
N->hasAnyUseOfValue(0);
6004 if (!LoExists && (!LegalOperations ||
6007 return CombineTo(
N, Res, Res);
6011 if (LoExists && HiExists)
6017 AddToWorklist(
Lo.getNode());
6020 (!LegalOperations ||
6022 return CombineTo(
N, LoOpt, LoOpt);
6027 AddToWorklist(
Hi.getNode());
6030 (!LegalOperations ||
6032 return CombineTo(
N, HiOpt, HiOpt);
6038SDValue DAGCombiner::visitSMUL_LOHI(SDNode *
N) {
6044 EVT VT =
N->getValueType(0);
6060 unsigned SimpleSize =
Simple.getSizeInBits();
6072 return CombineTo(
N,
Lo,
Hi);
6079SDValue DAGCombiner::visitUMUL_LOHI(SDNode *
N) {
6085 EVT VT =
N->getValueType(0);
6100 return CombineTo(
N, Zero, Zero);
6106 return CombineTo(
N, N0, Zero);
6113 unsigned SimpleSize =
Simple.getSizeInBits();
6125 return CombineTo(
N,
Lo,
Hi);
6132SDValue DAGCombiner::visitMULO(SDNode *
N) {
6138 EVT CarryVT =
N->getValueType(1);
6159 return DAG.
getNode(
N->getOpcode(),
DL,
N->getVTList(), N1, N0);
6171 N->getVTList(), N0, N0);
6178 return CombineTo(
N,
And, Cmp);
6216 unsigned Opcode0 = isSignedMinMax(N0, N1, N2, N3, CC);
6270 unsigned Opcode1 = isSignedMinMax(N00, N01, N02, N03, N0CC);
6271 if (!Opcode1 || Opcode0 == Opcode1)
6281 APInt MinCPlus1 = MinC + 1;
6282 if (-MaxC == MinCPlus1 && MinCPlus1.
isPowerOf2()) {
6288 if (MaxC == 0 && MinC != 0 && MinCPlus1.
isPowerOf2()) {
6337 unsigned BW = (C1 + 1).exactLogBase2();
6354 EVT VT =
N->getValueType(0);
6389 X.getValueType(), VT))
6403SDValue DAGCombiner::visitIMINMAX(SDNode *
N) {
6407 unsigned Opcode =
N->getOpcode();
6421 return DAG.
getNode(Opcode,
DL, VT, N1, N0);
6425 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
6429 if (
SDValue RMINMAX = reassociateOps(Opcode,
DL, N0, N1,
N->getFlags()))
6474 if (IsSatBroken || IsOpIllegal) {
6476 if (
A.isUndef() ||
B.isUndef())
6489 if (HasKnownSameSign(N0, N1)) {
6492 return DAG.
getNode(AltOpcode,
DL, VT, N0, N1);
6505 auto ReductionOpcode = [](
unsigned Opcode) {
6519 if (
SDValue SD = reassociateReduction(ReductionOpcode(Opcode), Opcode,
6520 SDLoc(
N), VT, N0, N1))
6528 return C0 > C1 ? N0 : N1;
6530 return C0 > C1 ? N1 : N0;
6539 const APInt &C1V = C1->getAPIntValue();
6558SDValue DAGCombiner::hoistLogicOpWithSameOpcodeHands(SDNode *
N) {
6561 unsigned LogicOpcode =
N->getOpcode();
6586 if (XVT !=
Y.getValueType())
6590 if ((VT.
isVector() || LegalOperations) &&
6600 SDNodeFlags LogicFlags;
6606 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6616 if (XVT !=
Y.getValueType())
6628 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6649 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6664 return DAG.
getNode(HandOpcode,
DL, VT, Logic0, Logic1, S);
6677 if (XVT.
isInteger() && XVT ==
Y.getValueType() &&
6681 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6700 assert(
X.getValueType() ==
Y.getValueType() &&
6701 "Inputs to shuffles are not the same type");
6707 if (!SVN0->hasOneUse() || !SVN1->hasOneUse() ||
6708 !SVN0->getMask().equals(SVN1->getMask()))
6744 SDValue LL, LR, RL, RR, N0CC, N1CC;
6745 if (!isSetCCEquivalent(N0, LL, LR, N0CC) ||
6746 !isSetCCEquivalent(N1, RL, RR, N1CC))
6750 "Unexpected operand types for bitwise logic op");
6753 "Unexpected operand types for setcc");
6769 if (LR == RR && CC0 == CC1 && IsInteger) {
6774 bool AndEqZero = IsAnd && CC1 ==
ISD::SETEQ && IsZero;
6776 bool AndGtNeg1 = IsAnd && CC1 ==
ISD::SETGT && IsNeg1;
6778 bool OrNeZero = !IsAnd && CC1 ==
ISD::SETNE && IsZero;
6780 bool OrLtZero = !IsAnd && CC1 ==
ISD::SETLT && IsZero;
6786 if (AndEqZero || AndGtNeg1 || OrNeZero || OrLtZero) {
6788 AddToWorklist(
Or.getNode());
6793 bool AndEqNeg1 = IsAnd && CC1 ==
ISD::SETEQ && IsNeg1;
6795 bool AndLtZero = IsAnd && CC1 ==
ISD::SETLT && IsZero;
6797 bool OrNeNeg1 = !IsAnd && CC1 ==
ISD::SETNE && IsNeg1;
6799 bool OrGtNeg1 = !IsAnd && CC1 ==
ISD::SETGT && IsNeg1;
6805 if (AndEqNeg1 || AndLtZero || OrNeNeg1 || OrGtNeg1) {
6807 AddToWorklist(
And.getNode());
6841 AddToWorklist(
Add.getNode());
6862 auto MatchDiffPow2 = [&](ConstantSDNode *C0, ConstantSDNode *C1) {
6868 return !C0->
isOpaque() && !C1->isOpaque() && (CMax - CMin).isPowerOf2();
6886 if (LL == RR && LR == RL) {
6893 if (LL == RL && LR == RR) {
6897 (!LegalOperations ||
6934 unsigned OrAndOpcode,
SelectionDAG &DAG,
bool isFMAXNUMFMINNUM_IEEE,
6935 bool isFMAXNUMFMINNUM) {
6946 isFMAXNUMFMINNUM_IEEE
6954 isFMAXNUMFMINNUM_IEEE
6972 isFMAXNUMFMINNUM_IEEE
6981 isFMAXNUMFMINNUM_IEEE
6992 (LogicOp->getOpcode() ==
ISD::AND || LogicOp->getOpcode() ==
ISD::OR) &&
6993 "Invalid Op to combine SETCC with");
6999 !
LHS->hasOneUse() || !
RHS->hasOneUse())
7006 LogicOp,
LHS.getNode(),
RHS.getNode());
7018 EVT VT = LogicOp->getValueType(0);
7041 (isFMAXNUMFMINNUM_IEEE || isFMAXNUMFMINNUM))) &&
7047 SDValue CommonValue, Operand1, Operand2;
7055 }
else if (LHS1 == RHS1) {
7068 }
else if (RHS0 == LHS1) {
7085 bool IsSigned = isSignedIntSetCC(CC);
7089 bool IsOr = (LogicOp->getOpcode() ==
ISD::OR);
7098 LogicOp->getOpcode(), DAG, isFMAXNUMFMINNUM_IEEE, isFMAXNUMFMINNUM);
7104 DAG.
getNode(NewOpcode,
DL, OpVT, Operand1, Operand2, Flags);
7105 return DAG.
getSetCC(
DL, VT, MinMaxValue, CommonValue, CC, {},
7111 if (LHS0 == LHS1 && RHS0 == RHS1 && CCL == CCR &&
7115 return DAG.
getSetCC(
DL, VT, LHS0, RHS0, CCL);
7122 LHS0 == RHS0 && LHS1C && RHS1C && OpVT.
isInteger()) {
7123 const APInt &APLhs = LHS1C->getAPIntValue();
7124 const APInt &APRhs = RHS1C->getAPIntValue();
7128 if (APLhs == (-APRhs) &&
7139 }
else if (TargetPreference &
7160 APInt Dif = MaxC - MinC;
7194 EVT CondVT =
Cond.getValueType();
7205 EVT OpVT =
T.getValueType();
7224 if (
SDValue V = foldLogicOfSetCCs(
true, N0, N1,
DL))
7241 APInt
ADDC = ADDI->getAPIntValue();
7242 APInt SRLC = SRLI->getAPIntValue();
7254 CombineTo(N0.
getNode(), NewAdd);
7267bool DAGCombiner::isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
7268 EVT LoadResultTy, EVT &ExtVT) {
7277 if (ExtVT == LoadedVT &&
7278 (!LegalOperations ||
7295 if (LegalOperations &&
7306bool DAGCombiner::isLegalNarrowLdSt(LSBaseSDNode *LDST,
7315 const unsigned ByteShAmt = ShAmt / 8;
7334 if (LdStMemVT.
bitsLT(MemVT))
7349 if (PtrType == MVT::Untyped || PtrType.
isExtended())
7359 if (LegalOperations &&
7361 Load->getAddressSpace(), ExtType,
false))
7369 if (
Load->getNumValues() > 2)
7388 if (LegalOperations &&
7390 Store->getAlign(),
Store->getAddressSpace()))
7396bool DAGCombiner::SearchForAndLoads(SDNode *
N,
7397 SmallVectorImpl<LoadSDNode*> &Loads,
7398 SmallPtrSetImpl<SDNode*> &NodesWithConsts,
7399 ConstantSDNode *Mask,
7400 SDNode *&NodeToMask) {
7404 if (
Op.getValueType().isVector())
7410 "Expected bitwise logic operation");
7411 if (!
C->getAPIntValue().isSubsetOf(
Mask->getAPIntValue()))
7416 if (!
Op.hasOneUse())
7419 switch(
Op.getOpcode()) {
7423 if (isAndLoadExtLoad(Mask,
Load,
Load->getValueType(0), ExtVT) &&
7441 unsigned ActiveBits =
Mask->getAPIntValue().countr_one();
7445 Op.getOperand(0).getValueType();
7456 if (!SearchForAndLoads(
Op.getNode(), Loads, NodesWithConsts, Mask,
7467 NodeToMask =
Op.getNode();
7470 for (
unsigned i = 0, e = NodeToMask->
getNumValues(); i < e; ++i) {
7471 MVT VT =
SDValue(NodeToMask, i).getSimpleValueType();
7472 if (VT != MVT::Glue && VT != MVT::Other) {
7474 NodeToMask =
nullptr;
7486bool DAGCombiner::BackwardsPropagateMask(SDNode *
N) {
7491 if (!
Mask->getAPIntValue().isMask())
7499 SmallPtrSet<SDNode*, 2> NodesWithConsts;
7500 SDNode *FixupNode =
nullptr;
7501 if (SearchForAndLoads(
N, Loads, NodesWithConsts, Mask, FixupNode)) {
7514 SDValue(FixupNode, 0), MaskOp);
7516 if (
And.getOpcode() == ISD ::AND)
7521 for (
auto *LogicN : NodesWithConsts) {
7527 if (LogicN->getOpcode() ==
ISD::AND &&
7546 for (
auto *
Load : Loads) {
7551 if (
And.getOpcode() == ISD ::AND)
7554 SDValue NewLoad = reduceLoadWidth(
And.getNode());
7556 "Shouldn't be masking the load if it can't be narrowed");
7570SDValue DAGCombiner::unfoldExtremeBitClearingToShifts(SDNode *
N) {
7581 unsigned OuterShift;
7582 unsigned InnerShift;
7584 auto matchMask = [&OuterShift, &InnerShift, &
Y](
SDValue M) ->
bool {
7587 OuterShift =
M->getOpcode();
7596 Y =
M->getOperand(1);
7603 else if (matchMask(N0))
7609 EVT VT =
N->getValueType(0);
7626 SDValue And0 =
And->getOperand(0), And1 =
And->getOperand(1);
7636 bool FoundNot =
false;
7639 Src = Src.getOperand(0);
7645 Src = Src.getOperand(0);
7649 if (Src.getOpcode() !=
ISD::SRL || !Src.hasOneUse())
7653 EVT SrcVT = Src.getValueType();
7662 if (!ShiftAmtC || !ShiftAmtC->getAPIntValue().ult(
BitWidth))
7666 Src = Src.getOperand(0);
7673 Src = Src.getOperand(0);
7697 EVT VT =
N->getValueType(0);
7723 unsigned LogicOpcode =
N->getOpcode();
7725 "Expected bitwise logic operation");
7727 if (!LogicOp.hasOneUse() || !ShiftOp.
hasOneUse())
7731 unsigned ShiftOpcode = ShiftOp.
getOpcode();
7732 if (LogicOp.getOpcode() != LogicOpcode ||
7744 if (LogicOp.getOperand(0).getOpcode() == ShiftOpcode &&
7745 LogicOp.getOperand(0).getOperand(1) ==
Y) {
7747 Z = LogicOp.getOperand(1);
7748 }
else if (LogicOp.getOperand(1).getOpcode() == ShiftOpcode &&
7749 LogicOp.getOperand(1).getOperand(1) ==
Y) {
7751 Z = LogicOp.getOperand(0);
7756 EVT VT =
N->getValueType(0);
7760 return DAG.
getNode(LogicOpcode,
DL, VT, NewShift, Z);
7771 unsigned LogicOpcode =
N->getOpcode();
7773 "Expected bitwise logic operation");
7774 if (LeftHand.
getOpcode() != LogicOpcode ||
7795 EVT VT =
N->getValueType(0);
7797 return DAG.
getNode(LogicOpcode,
DL, VT, CombinedShifts, W);
7809 "Must be called with ISD::OR or ISD::AND node");
7823 EVT VT = M.getValueType();
7831SDValue DAGCombiner::visitAND(SDNode *
N) {
7855 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
7872 if (BV0 && BV1 && !BV0->getSplatValue() && !BV1->getSplatValue() &&
7874 BV0->getOperand(0).getValueType() ==
7875 BV1->getOperand(0).getValueType()) {
7878 EVT EltVT = BV0->getOperand(0).getValueType();
7879 for (
unsigned I = 0;
I != NumElts; ++
I) {
7885 else if (C0 && C0->
isZero())
7887 else if (C1 && C1->isZero())
7891 else if (C1 && C1->isAllOnes())
7893 else if (BV0->getOperand(
I) == BV1->getOperand(
I))
7898 if (MergedOps.
size() == NumElts)
7907 EVT MemVT =
MLoad->getMemoryVT();
7918 MLoad->isExpandingLoad());
7919 CombineTo(
N, Frozen ? N0 : NewLoad);
7920 CombineTo(MLoad, NewLoad, NewLoad.
getValue(1));
7940 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
7953 auto MatchSubset = [](ConstantSDNode *
LHS, ConstantSDNode *
RHS) {
7954 return RHS->getAPIntValue().isSubsetOf(
LHS->getAPIntValue());
7964 APInt
Mask = ~N1C->getAPIntValue();
7990 {N0Op0.getOperand(1)})) {
8023 unsigned EltBitWidth =
Vector->getValueType(0).getScalarSizeInBits();
8024 APInt SplatValue, SplatUndef;
8025 unsigned SplatBitSize;
8032 const bool IsBigEndian =
false;
8034 Vector->isConstantSplat(SplatValue, SplatUndef, SplatBitSize,
8035 HasAnyUndefs, EltBitWidth, IsBigEndian);
8039 if (IsSplat && (SplatBitSize % EltBitWidth) == 0) {
8042 SplatValue |= SplatUndef;
8049 for (
unsigned i = 0, n = (SplatBitSize / EltBitWidth); i < n; ++i)
8050 Constant &= SplatValue.
extractBits(EltBitWidth, i * EltBitWidth);
8058 Load->getValueType(0),
Load->getMemoryVT(),
Load->getAlign(),
8067 switch (
Load->getExtensionType()) {
8068 default:
B =
false;
break;
8084 Load->getValueType(0), SDLoc(
Load),
8085 Load->getChain(),
Load->getBasePtr(),
8086 Load->getOffset(),
Load->getMemoryVT(),
8087 Load->getMemOperand());
8089 if (
Load->getNumValues() == 3) {
8091 SDValue To[] = { NewLoad.getValue(0), NewLoad.getValue(1),
8092 NewLoad.getValue(2) };
8093 CombineTo(
Load, To, 3,
true);
8095 CombineTo(
Load, NewLoad.getValue(0), NewLoad.getValue(1));
8105 if (
SDValue Shuffle = XformToShuffleWithZero(
N))
8132 EVT MemVT = GN0->getMemoryVT();
8135 if (
SDValue(GN0, 0).hasOneUse() &&
8138 SDValue Ops[] = {GN0->getChain(), GN0->getPassThru(), GN0->getMask(),
8139 GN0->getBasePtr(), GN0->getIndex(), GN0->getScale()};
8142 DAG.
getVTList(VT, MVT::Other), MemVT,
DL,
Ops, GN0->getMemOperand(),
8145 CombineTo(
N, ZExtLoad);
8146 AddToWorklist(ZExtLoad.
getNode());
8159 if (
SDValue Res = reduceLoadWidth(
N))
8168 if (BackwardsPropagateMask(
N))
8172 if (
SDValue Combined = visitANDLike(N0, N1,
N))
8177 if (
SDValue V = hoistLogicOpWithSameOpcodeHands(
N))
8208 if (
SDValue Folded = foldBitwiseOpWithNeg(
N,
DL, VT))
8230 X.getOperand(0).getScalarValueSizeInBits() == 1)
8233 X.getOperand(0).getScalarValueSizeInBits() == 1)
8248 EVT MemVT = LN0->getMemoryVT();
8255 ((!LegalOperations && LN0->isSimple()) ||
8256 TLI.
isLoadLegal(VT, MemVT, LN0->getAlign(), LN0->getAddressSpace(),
8260 LN0->getBasePtr(), MemVT, LN0->getMemOperand());
8274 if (
SDValue Shifts = unfoldExtremeBitClearingToShifts(
N))
8294 if (!
C->getAPIntValue().isMask(
8295 LHS.getOperand(0).getValueType().getScalarSizeInBits()))
8302 if (IsAndZeroExtMask(N0, N1) &&
8312 if (LegalOperations || VT.
isVector())
8325 bool DemandHighBits) {
8326 if (!LegalOperations)
8329 EVT VT =
N->getValueType(0);
8330 if (VT != MVT::i64 && VT != MVT::i32 && VT != MVT::i16)
8336 bool LookPassAnd0 =
false;
8337 bool LookPassAnd1 =
false;
8352 LookPassAnd0 =
true;
8362 LookPassAnd1 =
true;
8388 LookPassAnd0 =
true;
8402 LookPassAnd1 =
true;
8411 if (OpSizeInBits > 16) {
8415 if (DemandHighBits && !LookPassAnd0)
8422 if (!LookPassAnd1) {
8423 unsigned HighBit = DemandHighBits ? OpSizeInBits : 24;
8431 if (OpSizeInBits > 16) {
8446 if (!
N->hasOneUse())
8449 unsigned Opc =
N.getOpcode();
8467 unsigned MaskByteOffset;
8471 case 0xFF: MaskByteOffset = 0;
break;
8472 case 0xFF00: MaskByteOffset = 1;
break;
8481 case 0xFF0000: MaskByteOffset = 2;
break;
8482 case 0xFF000000: MaskByteOffset = 3;
break;
8487 if (MaskByteOffset == 0 || MaskByteOffset == 2) {
8493 if (!
C ||
C->getZExtValue() != 8)
8501 if (!
C ||
C->getZExtValue() != 8)
8507 if (MaskByteOffset != 0 && MaskByteOffset != 2)
8510 if (!
C ||
C->getZExtValue() != 8)
8515 if (MaskByteOffset != 1 && MaskByteOffset != 3)
8518 if (!
C ||
C->getZExtValue() != 8)
8522 if (Parts[MaskByteOffset])
8537 if (!
C ||
C->getAPIntValue() != 16)
8539 Parts[0] = Parts[1] =
N.getOperand(0).getOperand(0).getNode();
8554 "MatchBSwapHWordOrAndAnd: expecting i32");
8564 if (!Mask0 || !Mask1)
8575 if (!ShiftAmt0 || !ShiftAmt1)
8595 if (!LegalOperations)
8598 EVT VT =
N->getValueType(0);
8616 SDNode *Parts[4] = {};
8636 if (Parts[0] != Parts[1] || Parts[0] != Parts[2] || Parts[0] != Parts[3])
8664 if (
SDValue V = foldLogicOfSetCCs(
false, N0, N1,
DL))
8673 if (
const ConstantSDNode *N0O1C =
8675 if (
const ConstantSDNode *N1O1C =
8679 const APInt &LHSMask = N0O1C->getAPIntValue();
8680 const APInt &RHSMask = N1O1C->getAPIntValue();
8714 auto peekThroughResize = [](
SDValue V) {
8716 return V->getOperand(0);
8720 SDValue N0Resized = peekThroughResize(N0);
8722 SDValue N1Resized = peekThroughResize(N1);
8727 if (N00 == N1Resized || N01 == N1Resized)
8734 if (peekThroughResize(NotOperand) == N1Resized)
8742 if (peekThroughResize(NotOperand) == N1Resized)
8763 auto peekThroughZext = [](
SDValue V) {
8765 return V->getOperand(0);
8805 if (S0 &&
S1 && S0->getZExtValue() < BW &&
S1->getZExtValue() < BW &&
8806 S0->getZExtValue() == (BW -
S1->getZExtValue())) {
8823 Lo.getScalarValueSizeInBits() == (BW / 2) &&
8824 Lo.getValueType() ==
Hi.getValueType()) {
8840SDValue DAGCombiner::visitOR(SDNode *
N) {
8861 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
8877 if (BV0 && BV1 && !BV0->getSplatValue() && !BV1->getSplatValue() &&
8879 BV0->getOperand(0).getValueType() ==
8880 BV1->getOperand(0).getValueType()) {
8883 EVT EltVT = BV0->getOperand(0).getValueType();
8884 for (
unsigned I = 0;
I != NumElts; ++
I) {
8890 else if (C0 && C0->
isZero())
8892 else if (C1 && C1->isZero())
8896 else if (C1 && C1->isAllOnes())
8898 else if (BV0->getOperand(
I) == BV1->getOperand(
I))
8903 if (MergedOps.
size() == NumElts)
8917 if ((ZeroN00 != ZeroN01) && (ZeroN10 != ZeroN11)) {
8918 assert((!ZeroN00 || !ZeroN01) &&
"Both inputs zero!");
8919 assert((!ZeroN10 || !ZeroN11) &&
"Both inputs zero!");
8920 bool CanFold =
true;
8922 SmallVector<int, 4>
Mask(NumElts, -1);
8924 for (
int i = 0; i != NumElts; ++i) {
8925 int M0 = SV0->getMaskElt(i);
8926 int M1 = SV1->getMaskElt(i);
8929 bool M0Zero =
M0 < 0 || (ZeroN00 == (
M0 < NumElts));
8930 bool M1Zero =
M1 < 0 || (ZeroN10 == (
M1 < NumElts));
8934 if ((M0Zero &&
M1 < 0) || (M1Zero &&
M0 < 0))
8938 if (M0Zero == M1Zero) {
8943 assert((
M0 >= 0 ||
M1 >= 0) &&
"Undef index!");
8949 Mask[i] = M1Zero ?
M0 % NumElts : (
M1 % NumElts) + NumElts;
8958 return LegalShuffle;
8972 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
8983 if (
SDValue Combined = visitORLike(N0, N1,
DL))
8993 if (
SDValue BSwap = MatchBSwapHWord(
N, N0, N1))
8995 if (
SDValue BSwap = MatchBSwapHWordLow(
N, N0, N1))
9009 auto MatchIntersect = [](ConstantSDNode *C1, ConstantSDNode *C2) {
9029 if (
SDValue V = hoistLogicOpWithSameOpcodeHands(
N))
9033 if (
SDValue Rot = MatchRotate(N0, N1,
DL,
false))
9046 if (
SDValue Combined = visitADDLike(
N))
9051 if (LegalOperations || VT.
isVector())
9066 Mask =
Op.getOperand(1);
9067 return Op.getOperand(0);
9110 assert(OppShift && ExtractFrom &&
"Empty SDValue");
9138 bool IsMulOrDiv =
false;
9141 auto SelectOpcode = [&](
unsigned NeededShift,
unsigned MulOrDivVariant) {
9142 IsMulOrDiv = ExtractFrom.
getOpcode() == MulOrDivVariant;
9143 if (!IsMulOrDiv && ExtractFrom.
getOpcode() != NeededShift)
9145 Opcode = NeededShift;
9195 if (Rem != 0 || ResultAmt != OppLHSAmt)
9201 if (OppLHSAmt != ExtractFromAmt - NeededShiftAmt.
zextOrTrunc(
9210 return DAG.
getNode(Opcode,
DL, ResVT, OppShiftLHS, NewShiftNode);
9264 unsigned MaskLoBits = 0;
9266 unsigned Bits =
Log2_64(EltSize);
9268 if (NegBits >= Bits) {
9291 if (PosBits >= MaskLoBits) {
9313 if ((Pos == NegOp1) ||
9337 return Width.
getLoBits(MaskLoBits) == 0;
9338 return Width == EltSize;
9348 SDValue InnerNeg,
bool FromAdd,
9349 bool HasPos,
unsigned PosOpcode,
9350 unsigned NegOpcode,
const SDLoc &
DL) {
9361 return DAG.
getNode(HasPos ? PosOpcode : NegOpcode,
DL, VT, Shifted,
9362 HasPos ? Pos : Neg);
9375 SDValue InnerNeg,
bool FromAdd,
9376 bool HasPos,
unsigned PosOpcode,
9377 unsigned NegOpcode,
const SDLoc &
DL) {
9390 return DAG.
getNode(HasPos ? PosOpcode : NegOpcode,
DL, VT, N0, N1,
9391 HasPos ? Pos : Neg);
9436 EVT VT =
LHS.getValueType();
9441 bool HasROTL = hasOperation(
ISD::ROTL, VT);
9442 bool HasROTR = hasOperation(
ISD::ROTR, VT);
9443 bool HasFSHL = hasOperation(
ISD::FSHL, VT);
9444 bool HasFSHR = hasOperation(
ISD::FSHR, VT);
9455 if (LegalOperations && !HasROTL && !HasROTR && !HasFSHL && !HasFSHR)
9460 LHS.getOperand(0).getValueType() ==
RHS.getOperand(0).getValueType()) {
9463 MatchRotate(
LHS.getOperand(0),
RHS.getOperand(0),
DL, FromAdd))
9477 if (!LHSShift && !RHSShift)
9492 RHSShift = NewRHSShift;
9497 LHSShift = NewLHSShift;
9500 if (!RHSShift || !LHSShift)
9525 auto MatchRotateSum = [EltSizeInBits](ConstantSDNode *
LHS,
9526 ConstantSDNode *
RHS) {
9527 return (
LHS->getAPIntValue() +
RHS->getAPIntValue()) == EltSizeInBits;
9530 auto ApplyMasks = [&](
SDValue Res) {
9554 bool IsRotate = LHSShiftArg == RHSShiftArg;
9555 if (!IsRotate && !(HasFSHL || HasFSHR)) {
9564 if (CommonOp ==
Or.getOperand(0)) {
9566 Y =
Or.getOperand(1);
9569 if (CommonOp ==
Or.getOperand(1)) {
9571 Y =
Or.getOperand(0);
9578 if (matchOr(LHSShiftArg, RHSShiftArg)) {
9583 }
else if (matchOr(RHSShiftArg, LHSShiftArg)) {
9592 return ApplyMasks(Res);
9605 if (IsRotate && (HasROTL || HasROTR || !(HasFSHL || HasFSHR))) {
9606 bool UseROTL = !LegalOperations || HasROTL;
9608 UseROTL ? LHSShiftAmt : RHSShiftAmt);
9610 bool UseFSHL = !LegalOperations || HasFSHL;
9612 RHSShiftArg, UseFSHL ? LHSShiftAmt : RHSShiftAmt);
9615 return ApplyMasks(Res);
9620 if (!HasROTL && !HasROTR && !HasFSHL && !HasFSHR)
9629 SDValue LExtOp0 = LHSShiftAmt;
9630 SDValue RExtOp0 = RHSShiftAmt;
9643 if (IsRotate && (HasROTL || HasROTR)) {
9644 if (
SDValue TryL = MatchRotatePosNeg(LHSShiftArg, LHSShiftAmt, RHSShiftAmt,
9645 LExtOp0, RExtOp0, FromAdd, HasROTL,
9649 if (
SDValue TryR = MatchRotatePosNeg(RHSShiftArg, RHSShiftAmt, LHSShiftAmt,
9650 RExtOp0, LExtOp0, FromAdd, HasROTR,
9655 if (
SDValue TryL = MatchFunnelPosNeg(LHSShiftArg, RHSShiftArg, LHSShiftAmt,
9656 RHSShiftAmt, LExtOp0, RExtOp0, FromAdd,
9660 if (
SDValue TryR = MatchFunnelPosNeg(LHSShiftArg, RHSShiftArg, RHSShiftAmt,
9661 LHSShiftAmt, RExtOp0, LExtOp0, FromAdd,
9711static std::optional<SDByteProvider>
9713 std::optional<uint64_t> VectorIndex,
9714 unsigned StartingIndex = 0,
9719 return std::nullopt;
9723 if (
Depth && !
Op.hasOneUse() &&
9724 (
Op.getOpcode() !=
ISD::LOAD || !
Op.getValueType().isVector()))
9725 return std::nullopt;
9729 if (
Op.getOpcode() !=
ISD::LOAD && VectorIndex.has_value())
9730 return std::nullopt;
9732 unsigned BitWidth =
Op.getScalarValueSizeInBits();
9734 return std::nullopt;
9736 assert(Index < ByteWidth &&
"invalid index requested");
9739 switch (
Op.getOpcode()) {
9742 VectorIndex, StartingIndex, ByteMask);
9744 return std::nullopt;
9746 VectorIndex, StartingIndex, ByteMask);
9748 return std::nullopt;
9750 if (
LHS->isConstantZero())
9752 if (
RHS->isConstantZero())
9754 return std::nullopt;
9759 return std::nullopt;
9761 uint64_t BitShift = ShiftOp->getZExtValue();
9763 if (BitShift % 8 != 0)
9764 return std::nullopt;
9770 return Index < ByteShift
9780 if (NarrowBitWidth % 8 != 0)
9781 return std::nullopt;
9782 uint64_t NarrowByteWidth = NarrowBitWidth / 8;
9784 if (Index >= NarrowByteWidth)
9786 ? std::optional<SDByteProvider>(
9790 StartingIndex, ByteMask);
9794 Depth + 1, VectorIndex, StartingIndex,
9801 return std::nullopt;
9804 MaskOp->getAPIntValue().extractBitsAsZExtValue(8, Index * 8);
9806 if (MaskByte == 0x00)
9810 VectorIndex, StartingIndex, ByteMask);
9812 return std::nullopt;
9817 if (MaskByte != 0xFF && !ByteMask.empty() && !
Result->isConstantZero())
9818 ByteMask[StartingIndex] &= MaskByte;
9825 return std::nullopt;
9827 VectorIndex =
OffsetOp->getZExtValue();
9831 if (NarrowBitWidth % 8 != 0)
9832 return std::nullopt;
9833 uint64_t NarrowByteWidth = NarrowBitWidth / 8;
9836 if (Index >= NarrowByteWidth)
9837 return std::nullopt;
9845 if (*VectorIndex * NarrowByteWidth > StartingIndex)
9846 return std::nullopt;
9847 if ((*VectorIndex + 1) * NarrowByteWidth <= StartingIndex)
9848 return std::nullopt;
9851 VectorIndex, StartingIndex, ByteMask);
9855 if (!
L->isSimple() ||
L->isIndexed())
9856 return std::nullopt;
9858 unsigned NarrowBitWidth =
L->getMemoryVT().getScalarSizeInBits();
9859 if (NarrowBitWidth % 8 != 0)
9860 return std::nullopt;
9861 uint64_t NarrowByteWidth = NarrowBitWidth / 8;
9866 if (Index >= NarrowByteWidth)
9868 ? std::optional<SDByteProvider>(
9872 unsigned BPVectorIndex = VectorIndex.value_or(0U);
9877 return std::nullopt;
9892 int64_t FirstOffset) {
9894 unsigned Width = ByteOffsets.
size();
9896 return std::nullopt;
9898 bool BigEndian =
true, LittleEndian =
true;
9899 for (
unsigned i = 0; i < Width; i++) {
9900 int64_t CurrentByteOffset = ByteOffsets[i] - FirstOffset;
9903 if (!BigEndian && !LittleEndian)
9904 return std::nullopt;
9907 assert((BigEndian != LittleEndian) &&
"It should be either big endian or"
9914 switch (
Value.getOpcode()) {
9919 return Value.getOperand(0);
9946SDValue DAGCombiner::mergeTruncStores(StoreSDNode *
N) {
9957 EVT MemVT =
N->getMemoryVT();
9958 if (!(MemVT == MVT::i8 || MemVT == MVT::i16 || MemVT == MVT::i32) ||
9959 !
N->isSimple() ||
N->isIndexed())
9966 unsigned MaxWideNumBits = 64;
9967 unsigned MaxStores = MaxWideNumBits / NarrowNumBits;
9976 if (
Store->getMemoryVT() != MemVT || !
Store->isSimple() ||
9980 Chain =
Store->getChain();
9981 if (MaxStores < Stores.
size())
9985 if (Stores.
size() < 2)
9990 unsigned NumStores = Stores.
size();
9991 unsigned WideNumBits = NumStores * NarrowNumBits;
9992 if (WideNumBits != 16 && WideNumBits != 32 && WideNumBits != 64)
10000 StoreSDNode *FirstStore =
nullptr;
10001 std::optional<BaseIndexOffset>
Base;
10002 for (
auto *
Store : Stores) {
10021 if (ShiftAmtC % NarrowNumBits != 0)
10028 Offset = ShiftAmtC / NarrowNumBits;
10034 SourceValue = WideVal;
10035 else if (SourceValue != WideVal) {
10043 SourceValue = WideVal;
10052 int64_t ByteOffsetFromBase = 0;
10055 else if (!
Base->equalBaseIndex(Ptr, DAG, ByteOffsetFromBase))
10059 if (ByteOffsetFromBase < FirstOffset) {
10060 FirstStore =
Store;
10061 FirstOffset = ByteOffsetFromBase;
10067 OffsetMap[
Offset] = ByteOffsetFromBase;
10073 assert(FirstStore &&
"First store must be set");
10080 if (!Allowed || !
Fast)
10085 auto checkOffsets = [&](
bool MatchLittleEndian) {
10086 if (MatchLittleEndian) {
10087 for (
unsigned i = 0; i != NumStores; ++i)
10088 if (OffsetMap[i] != i * (NarrowNumBits / 8) + FirstOffset)
10091 for (
unsigned i = 0, j = NumStores - 1; i != NumStores; ++i, --
j)
10092 if (OffsetMap[j] != i * (NarrowNumBits / 8) + FirstOffset)
10099 bool NeedBswap =
false;
10100 bool NeedRotate =
false;
10103 if (NarrowNumBits == 8 && checkOffsets(Layout.
isBigEndian()))
10105 else if (NumStores == 2 && checkOffsets(Layout.
isBigEndian()))
10114 "Unexpected store value to merge");
10123 }
else if (NeedRotate) {
10124 assert(WideNumBits % 2 == 0 &&
"Unexpected type for rotate");
10168SDValue DAGCombiner::MatchLoadCombine(SDNode *
N) {
10170 "Can only match load combining against OR nodes");
10173 EVT VT =
N->getValueType(0);
10174 if (VT != MVT::i16 && VT != MVT::i32 && VT != MVT::i64)
10180 assert(
P.hasSrc() &&
"Must be a memory byte provider");
10183 unsigned LoadBitWidth =
Load->getMemoryVT().getScalarSizeInBits();
10185 assert(LoadBitWidth % 8 == 0 &&
10186 "can only analyze providers for individual bytes not bit");
10187 unsigned LoadByteWidth = LoadBitWidth / 8;
10192 std::optional<BaseIndexOffset>
Base;
10195 SmallPtrSet<LoadSDNode *, 8> Loads;
10196 std::optional<SDByteProvider> FirstByteProvider;
10203 unsigned ZeroExtendedBytes = 0;
10204 for (
int i = ByteWidth - 1; i >= 0; --i) {
10211 if (
P->isConstantZero()) {
10214 if (++ZeroExtendedBytes != (ByteWidth -
static_cast<unsigned>(i)))
10218 assert(
P->hasSrc() &&
"provenance should either be memory or zero");
10225 else if (Chain != LChain)
10230 int64_t ByteOffsetFromBase = 0;
10239 if (
L->getMemoryVT().isVector()) {
10240 unsigned LoadWidthInBit =
L->getMemoryVT().getScalarSizeInBits();
10241 if (LoadWidthInBit % 8 != 0)
10243 unsigned ByteOffsetFromVector =
P->SrcOffset * LoadWidthInBit / 8;
10250 else if (!
Base->equalBaseIndex(Ptr, DAG, ByteOffsetFromBase))
10254 ByteOffsetFromBase += MemoryByteOffset(*
P);
10255 ByteOffsets[i] = ByteOffsetFromBase;
10258 if (ByteOffsetFromBase < FirstOffset) {
10259 FirstByteProvider =
P;
10260 FirstOffset = ByteOffsetFromBase;
10266 assert(!Loads.
empty() &&
"All the bytes of the value must be loaded from "
10267 "memory, so there must be at least one load which produces the value");
10268 assert(
Base &&
"Base address of the accessed memory location must be set");
10271 bool NeedsZext = ZeroExtendedBytes > 0;
10282 ArrayRef(ByteOffsets).drop_back(ZeroExtendedBytes), FirstOffset);
10286 assert(FirstByteProvider &&
"must be set");
10290 if (MemoryByteOffset(*FirstByteProvider) != 0)
10298 if (LegalOperations &&
10299 !TLI.
isLoadLegal(VT, MemVT, FirstLoad->getAlign(),
10300 FirstLoad->getAddressSpace(),
10309 bool NeedsBswap = IsBigEndianTarget != *IsBigEndian;
10316 if (NeedsBswap && (LegalOperations || NeedsZext) &&
10322 if (NeedsBswap && NeedsZext && LegalOperations &&
10330 *FirstLoad->getMemOperand(), &
Fast);
10331 if (!Allowed || !
Fast)
10336 Chain, FirstLoad->getBasePtr(),
10337 FirstLoad->getPointerInfo(), MemVT, FirstLoad->getAlign());
10340 for (LoadSDNode *L : Loads)
10344 bool HasPartialMask =
false;
10346 for (
unsigned i = 0; i < ByteWidth; ++i) {
10347 CombinedMask |= (
uint64_t)ByteMasks[i] << (i * 8);
10348 if (ByteMasks[i] != 0xFF)
10349 HasPartialMask =
true;
10353 if (HasPartialMask)
10368 if (HasPartialMask)
10391SDValue DAGCombiner::unfoldMaskedMerge(SDNode *
N) {
10398 EVT VT =
N->getValueType(0);
10420 M =
And.getOperand(XorIdx ? 0 : 1);
10426 if (!matchAndXor(N0, 0, N1) && !matchAndXor(N0, 1, N1) &&
10427 !matchAndXor(N1, 0, N0) && !matchAndXor(N1, 1, N0))
10474SDValue DAGCombiner::visitXOR(SDNode *
N) {
10501 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
10513 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
10534 if (
SDValue Combined = visitADDLike(
N))
10542 isSetCCEquivalent(N0,
LHS,
RHS, CC,
true) &&
10544 N->use_begin()->getUser()->getOpcode() ==
ISD::AND)) {
10546 LHS.getValueType());
10547 if (!LegalOperations ||
10551 switch (N0Opcode) {
10568 CombineTo(
N, SetCC);
10570 recursivelyDeleteUnusedNodes(N0.
getNode());
10586 AddToWorklist(
V.getNode());
10595 if (isOneUseSetCC(N01) || isOneUseSetCC(N00)) {
10600 return DAG.
getNode(NewOpcode,
DL, VT, N00, N01);
10613 return DAG.
getNode(NewOpcode,
DL, VT, N00, N01);
10623 APInt NotYValue = ~YConst->getAPIntValue();
10639 AddToWorklist(NotX.
getNode());
10644 if (!LegalOperations || hasOperation(
ISD::ABS, VT)) {
10648 SDValue A0 =
A.getOperand(0), A1 =
A.getOperand(1);
10650 if ((A0 == S && A1 == S0) || (A1 == S && A0 == S0))
10687 if (
SDValue V = hoistLogicOpWithSameOpcodeHands(
N))
10698 if (
SDValue MM = unfoldMaskedMerge(
N))
10767 if (!LogicOp.hasOneUse())
10770 unsigned LogicOpcode = LogicOp.getOpcode();
10776 unsigned ShiftOpcode = Shift->
getOpcode();
10779 assert(C1Node &&
"Expected a shift with constant operand");
10782 const APInt *&ShiftAmtVal) {
10783 if (V.getOpcode() != ShiftOpcode || !V.hasOneUse())
10791 ShiftOp = V.getOperand(0);
10796 if (ShiftAmtVal->getBitWidth() != C1Val.
getBitWidth())
10801 bool Overflow =
false;
10802 APInt NewShiftAmt = C1Val.
uadd_ov(*ShiftAmtVal, Overflow);
10807 if (NewShiftAmt.
uge(V.getScalarValueSizeInBits()))
10815 const APInt *C0Val;
10816 if (matchFirstShift(LogicOp.getOperand(0),
X, C0Val))
10817 Y = LogicOp.getOperand(1);
10818 else if (matchFirstShift(LogicOp.getOperand(1),
X, C0Val))
10819 Y = LogicOp.getOperand(0);
10830 return DAG.
getNode(LogicOpcode,
DL, VT, NewShift1, NewShift2,
10840SDValue DAGCombiner::visitShiftByConstant(SDNode *
N) {
10860 switch (
LHS.getOpcode()) {
10884 if (!IsShiftByConstant && !IsCopyOrSelect)
10887 if (IsCopyOrSelect &&
N->hasOneUse())
10892 EVT VT =
N->getValueType(0);
10894 N->getOpcode(),
DL, VT, {LHS.getOperand(1), N->getOperand(1)})) {
10897 return DAG.
getNode(
LHS.getOpcode(),
DL, VT, NewShift, NewRHS);
10903SDValue DAGCombiner::distributeTruncateThroughAnd(SDNode *
N) {
10908 EVT TruncVT =
N->getValueType(0);
10909 if (
N->hasOneUse() &&
N->getOperand(0).hasOneUse() &&
10917 AddToWorklist(Trunc00.
getNode());
10918 AddToWorklist(Trunc01.
getNode());
10926SDValue DAGCombiner::visitRotate(SDNode *
N) {
10930 EVT VT =
N->getValueType(0);
10945 bool OutOfRange =
false;
10946 auto MatchOutOfRange = [Bitsize, &OutOfRange](ConstantSDNode *
C) {
10947 OutOfRange |=
C->getAPIntValue().uge(Bitsize);
10955 return DAG.
getNode(
N->getOpcode(), dl, VT, N0, Amt);
10960 if (RotAmtC && RotAmtC->getAPIntValue() == 8 &&
10971 if (
SDValue NewOp1 = distributeTruncateThroughAnd(N1.
getNode()))
10972 return DAG.
getNode(
N->getOpcode(), dl, VT, N0, NewOp1);
10984 bool SameSide = (
N->getOpcode() == NextOp);
10991 if (Norm1 && Norm2)
10993 CombineOp, dl, ShiftVT, {Norm1, Norm2})) {
10995 {CombinedShift, BitsizeC});
10997 ISD::UREM, dl, ShiftVT, {CombinedShift, BitsizeC});
10999 CombinedShiftNorm);
11006SDValue DAGCombiner::visitSHL(SDNode *
N) {
11023 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
11046 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
11056 if (
SDValue NewOp1 = distributeTruncateThroughAnd(N1.
getNode()))
11062 auto MatchOutOfRange = [OpSizeInBits](ConstantSDNode *
LHS,
11063 ConstantSDNode *
RHS) {
11064 APInt c1 =
LHS->getAPIntValue();
11065 APInt c2 =
RHS->getAPIntValue();
11067 return (c1 + c2).uge(OpSizeInBits);
11072 auto MatchInRange = [OpSizeInBits](ConstantSDNode *
LHS,
11073 ConstantSDNode *
RHS) {
11074 APInt c1 =
LHS->getAPIntValue();
11075 APInt c2 =
RHS->getAPIntValue();
11077 return (c1 + c2).ult(OpSizeInBits);
11099 auto MatchOutOfRange = [OpSizeInBits, InnerBitwidth](ConstantSDNode *
LHS,
11100 ConstantSDNode *
RHS) {
11101 APInt c1 =
LHS->getAPIntValue();
11102 APInt c2 =
RHS->getAPIntValue();
11104 return c2.
uge(OpSizeInBits - InnerBitwidth) &&
11105 (c1 + c2).uge(OpSizeInBits);
11112 auto MatchInRange = [OpSizeInBits, InnerBitwidth](ConstantSDNode *
LHS,
11113 ConstantSDNode *
RHS) {
11114 APInt c1 =
LHS->getAPIntValue();
11115 APInt c2 =
RHS->getAPIntValue();
11117 return c2.
uge(OpSizeInBits - InnerBitwidth) &&
11118 (c1 + c2).ult(OpSizeInBits);
11138 auto MatchEqual = [VT](ConstantSDNode *
LHS, ConstantSDNode *
RHS) {
11139 APInt c1 =
LHS->getAPIntValue();
11140 APInt c2 =
RHS->getAPIntValue();
11150 AddToWorklist(NewSHL.
getNode());
11156 auto MatchShiftAmount = [OpSizeInBits](ConstantSDNode *
LHS,
11157 ConstantSDNode *
RHS) {
11158 const APInt &LHSC =
LHS->getAPIntValue();
11159 const APInt &RHSC =
RHS->getAPIntValue();
11160 return LHSC.
ult(OpSizeInBits) && RHSC.
ult(OpSizeInBits) &&
11232 AddToWorklist(Shl0.
getNode());
11251 {Add.getOperand(1)})) {
11271 if (
SDValue NewSHL = visitShiftByConstant(
N))
11305 Flags.setNoUnsignedWrap(
N->getFlags().hasNoUnsignedWrap() &&
11318 APInt NewStep = C0 << ShlVal;
11333 "SRL or SRA node is required here!");
11342 SDValue ShiftOperand =
N->getOperand(0);
11357 if (!IsSignExt && !IsZeroExt)
11364 auto UserOfLowerBits = [NarrowVTSize](
SDNode *U) {
11369 if (!UShiftAmtSrc) {
11373 return UShiftAmt < NarrowVTSize;
11387 if (IsZeroExt && ShiftOperand.
hasOneUse() &&
11390 }
else if (IsSignExt && ShiftOperand.
hasOneUse() &&
11406 "Cannot have a multiply node with two different operand types.");
11417 if (ShiftAmt != NarrowVTSize)
11427 EVT TransformVT = NarrowVT;
11438 bool IsSigned =
N->getOpcode() ==
ISD::SRA;
11445 unsigned Opcode =
N->getOpcode();
11450 EVT VT =
N->getValueType(0);
11469SDValue DAGCombiner::visitSRA(SDNode *
N) {
11491 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
11494 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
11506 auto SumOfShifts = [&](ConstantSDNode *
LHS, ConstantSDNode *
RHS) {
11507 APInt c1 =
LHS->getAPIntValue();
11508 APInt c2 =
RHS->getAPIntValue();
11510 APInt Sum = c1 + c2;
11511 unsigned ShiftSum =
11512 Sum.
uge(OpSizeInBits) ? (OpSizeInBits - 1) : Sum.getZExtValue();
11522 "Expected matchBinaryPredicate to return one element for "
11526 ShiftValue = ShiftValues[0];
11540 APInt Sum = C1 + C2;
11544 return DAG.
getNOT(
DL, NewShift, VT);
11568 if ((ShiftAmt > 0) &&
11578 N->getValueType(0), Trunc);
11595 if (ConstantSDNode *AddC =
11612 DAG.
getConstant(AddC->getAPIntValue().lshr(ShiftAmt).trunc(
11629 if (
SDValue NewOp1 = distributeTruncateThroughAnd(N1.
getNode()))
11646 if (LargeShift->getAPIntValue() == TruncBits) {
11664 const APInt &AddVal = AddC->getAPIntValue();
11666 SDNodeFlags ShiftFlags =
N->getFlags();
11670 SDNodeFlags AddFlags = N0->
getFlags();
11685 if (
SDValue NewSRA = visitShiftByConstant(
N))
11694 if (
SDValue NarrowLoad = reduceLoadWidth(
N))
11703SDValue DAGCombiner::visitSRL(SDNode *
N) {
11720 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
11723 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
11734 auto MatchOutOfRange = [OpSizeInBits](ConstantSDNode *
LHS,
11735 ConstantSDNode *
RHS) {
11736 APInt c1 =
LHS->getAPIntValue();
11737 APInt c2 =
RHS->getAPIntValue();
11739 return (c1 + c2).uge(OpSizeInBits);
11744 auto MatchInRange = [OpSizeInBits](ConstantSDNode *
LHS,
11745 ConstantSDNode *
RHS) {
11746 APInt c1 =
LHS->getAPIntValue();
11747 APInt c2 =
RHS->getAPIntValue();
11749 return (c1 + c2).ult(OpSizeInBits);
11769 if (c1 + OpSizeInBits == InnerShiftSize) {
11770 if (c1 + c2 >= InnerShiftSize)
11780 c1 + c2 < InnerShiftSize) {
11785 OpSizeInBits - c2),
11802 auto MatchShiftAmount = [OpSizeInBits](ConstantSDNode *
LHS,
11803 ConstantSDNode *
RHS) {
11804 const APInt &LHSC =
LHS->getAPIntValue();
11805 const APInt &RHSC =
RHS->getAPIntValue();
11806 return LHSC.
ult(OpSizeInBits) && RHSC.
ult(OpSizeInBits) &&
11848 AddToWorklist(SmallShift.
getNode());
11876 APInt UnknownBits = ~Known.Zero;
11877 if (UnknownBits == 0)
return DAG.
getConstant(1, SDLoc(N0), VT);
11892 AddToWorklist(
Op.getNode());
11901 if (
SDValue NewOp1 = distributeTruncateThroughAnd(N1.
getNode()))
11931 if (N1C->
getZExtValue() == (NumElts - 1) * EltSizeInBits) {
11934 "Expected BUILD_VECTOR operand as wide as element type");
11937 LastElt = DAG.
getBitcast(IntEltVT, LastElt);
11953 const APInt &AddVal = AddC->getAPIntValue();
11955 SDNodeFlags ShiftFlags =
N->getFlags();
11959 SDNodeFlags AddFlags = N0->
getFlags();
11971 if (
SDValue NewSRL = visitShiftByConstant(
N))
11975 if (
SDValue NarrowLoad = reduceLoadWidth(
N))
12002 if (
N->hasOneUse()) {
12003 SDNode *
User = *
N->user_begin();
12011 AddToWorklist(User);
12027 X.getScalarValueSizeInBits() == HalfBW &&
12028 Y.getScalarValueSizeInBits() == HalfBW) {
12030 (!LegalOperations ||
12036 (!LegalOperations ||
12054SDValue DAGCombiner::visitFunnelShift(SDNode *
N) {
12055 EVT VT =
N->getValueType(0);
12073 return IsFSHL ? N0 : N1;
12075 auto IsUndefOrZero = [](
SDValue V) {
12084 if (Cst->getAPIntValue().uge(
BitWidth)) {
12086 return DAG.
getNode(
N->getOpcode(),
DL, VT, N0, N1,
12092 return IsFSHL ? N0 : N1;
12098 if (IsUndefOrZero(N0))
12102 if (IsUndefOrZero(N1))
12116 "ShAmt must be in [1, BW-1] for the identity fold to be valid");
12118 unsigned C0Expected = IsFSHL ? ShAmt :
BitWidth - ShAmt;
12119 unsigned C1Expected = IsFSHL ?
BitWidth - ShAmt : ShAmt;
12142 if (
LHS &&
RHS &&
LHS->isSimple() &&
RHS->isSimple() &&
12143 LHS->getAddressSpace() ==
RHS->getAddressSpace() &&
12144 (
LHS->hasNUsesOfValue(1, 0) ||
RHS->hasNUsesOfValue(1, 0)) &&
12153 RHS->getAddressSpace(), NewAlign,
12154 RHS->getMemOperand()->getFlags(), &
Fast) &&
12158 AddToWorklist(NewPtr.
getNode());
12160 VT,
DL,
RHS->getChain(), NewPtr,
12161 RHS->getPointerInfo().getWithOffset(PtrOff), NewAlign,
12162 RHS->getMemOperand()->getFlags(),
RHS->getAAInfo());
12190 if (N0 == N1 && hasOperation(RotOpc, VT))
12191 return DAG.
getNode(RotOpc,
DL, VT, N0, N2);
12200SDValue DAGCombiner::visitSHLSAT(SDNode *
N) {
12235SDValue DAGCombiner::foldABSToABD(SDNode *
N,
const SDLoc &
DL) {
12236 EVT SrcVT =
N->getValueType(0);
12239 N =
N->getOperand(0).getNode();
12241 EVT VT =
N->getValueType(0);
12248 SDValue AbsOp0 =
N->getOperand(0);
12253 auto IsNotMinSignedInt = [VT](ConstantSDNode *
C) {
12256 return !
C->getAPIntValue()
12258 .isMinSignedValue();
12274 auto CreateZextedAbd = [&](
unsigned AbdOpc) {
12283 bool AbsOpWillNSW =
12294 bool AbsOpWillNUW =
12297 if (hasOperation(
ISD::ABDU, VT) && AbsOpWillNUW)
12306 assert(!IsAdd &&
"Unexpected abs(add(x,y)) pattern");
12320 EVT MaxVT = VT0.
bitsGT(VT1) ? VT0 : VT1;
12321 if ((VT0 == MaxVT || Op0->
hasOneUse()) &&
12323 (!LegalTypes || hasOperation(ABDOpcode, MaxVT))) {
12333 if (!LegalOperations || hasOperation(ABDOpcode, VT)) {
12341SDValue DAGCombiner::visitABS(SDNode *
N) {
12343 EVT VT =
N->getValueType(0);
12377SDValue DAGCombiner::visitABS_MIN_POISON(SDNode *
N) {
12379 EVT VT =
N->getValueType(0);
12423SDValue DAGCombiner::visitCLMUL(SDNode *
N) {
12424 unsigned Opcode =
N->getOpcode();
12427 EVT VT =
N->getValueType(0);
12437 return DAG.
getNode(Opcode,
DL, VT, N1, N0);
12458SDValue DAGCombiner::visitPEXT(SDNode *
N) {
12459 EVT VT =
N->getValueType(0);
12476SDValue DAGCombiner::visitPDEP(SDNode *
N) {
12477 EVT VT =
N->getValueType(0);
12500SDValue DAGCombiner::visitBSWAP(SDNode *
N) {
12502 EVT VT =
N->getValueType(0);
12527 if (ShAmt && ShAmt->getAPIntValue().ult(BW) &&
12528 ShAmt->getZExtValue() >= (BW / 2) && (ShAmt->getZExtValue() % 8) == 0 &&
12530 (!LegalOperations || hasOperation(
ISD::BSWAP, HalfVT))) {
12532 if (
uint64_t NewShAmt = (ShAmt->getZExtValue() - (BW / 2)))
12548 if (ShAmt && ShAmt->getAPIntValue().ult(BW) &&
12549 ShAmt->getZExtValue() % 8 == 0) {
12564 if (
Known.isZero())
12570 if (BW - (LZ + TZ) == 8) {
12575 if (!LegalOperations || hasOperation(
Opc, VT)) {
12577 SDNodeFlags
Flags =
12587SDValue DAGCombiner::visitBITREVERSE(SDNode *
N) {
12589 EVT VT =
N->getValueType(0);
12623 EVT VT = Src.getValueType();
12633 bool NeedAdd =
true;
12655SDValue DAGCombiner::visitCTLZ(SDNode *
N) {
12657 EVT VT =
N->getValueType(0);
12669 if (
SDValue V = foldCTLZToCTLS(N0,
DL))
12675SDValue DAGCombiner::visitCTLZ_ZERO_POISON(SDNode *
N) {
12677 EVT VT =
N->getValueType(0);
12685 if (
SDValue V = foldCTLZToCTLS(N0,
DL))
12691SDValue DAGCombiner::visitCTTZ(SDNode *
N) {
12693 EVT VT =
N->getValueType(0);
12708SDValue DAGCombiner::visitCTTZ_ZERO_POISON(SDNode *
N) {
12710 EVT VT =
N->getValueType(0);
12720SDValue DAGCombiner::visitCTPOP(SDNode *
N) {
12722 EVT VT =
N->getValueType(0);
12734 const APInt &Amt = AmtC->getAPIntValue();
12735 if (Amt.
ult(NumBits)) {
12771 EVT VT =
LHS.getValueType();
12831SDValue DAGCombiner::foldShiftToAvg(SDNode *
N,
const SDLoc &
DL) {
12832 const unsigned Opcode =
N->getOpcode();
12836 EVT VT =
N->getValueType(0);
12837 bool IsUnsigned = Opcode ==
ISD::SRL;
12844 SDNodeFlags
Flags =
12851 if (hasOperation(FloorISD, VT))
12858SDValue DAGCombiner::foldBitwiseOpWithNeg(SDNode *
N,
const SDLoc &
DL, EVT VT) {
12859 unsigned Opc =
N->getOpcode();
12878 if ((
LHS == True &&
RHS == False) || (
LHS == False &&
RHS == True))
12884 True, DAG, LegalOperations, ForCodeSize);
12888 HandleSDNode NegTrueHandle(NegTrue);
12896 if (
LHS == NegTrue) {
12900 RHS, DAG, LegalOperations, ForCodeSize);
12902 HandleSDNode NegRHSHandle(NegRHS);
12903 if (NegRHS == False) {
12905 False, CC, TLI, DAG);
12925 EVT VT =
N->getValueType(0);
12927 VT !=
Cond.getOperand(0).getValueType())
12970SDValue DAGCombiner::foldSelectOfConstants(SDNode *
N) {
12974 EVT VT =
N->getValueType(0);
12975 EVT CondVT =
Cond.getValueType();
12986 if (CondVT != MVT::i1 || LegalOperations) {
13001 if (C1->
isZero() && C2->isOne()) {
13010 if (C1->
isOne() && C2->isZero() && CondVT == VT)
13021 assert(CondVT == MVT::i1 && !LegalOperations);
13024 if (C1->
isOne() && C2->isZero())
13032 if (C1->
isZero() && C2->isOne()) {
13039 if (C1->
isZero() && C2->isAllOnes()) {
13052 const APInt &C1Val = C1->getAPIntValue();
13053 const APInt &C2Val = C2->getAPIntValue();
13056 if (C1Val - 1 == C2Val) {
13062 if (C1Val + 1 == C2Val) {
13082 if (C2->isAllOnes()) {
13097 "Expected a (v)select");
13099 SDValue T =
N->getOperand(1),
F =
N->getOperand(2);
13100 EVT VT =
N->getValueType(0);
13136 EVT VT =
N->getValueType(0);
13200 EVT VT =
LHS.getValueType();
13202 if (LegalOperations && !hasOperation(ABDOpc, VT))
13220 bool IsTypeLegalOrPromote =
13238 IsTypeLegalOrPromote)
13254 IsTypeLegalOrPromote)
13295 std::tuple<unsigned, SDValue, SDValue>
Invalid(0, {}, {});
13297 EVT VT =
LHS.getValueType();
13318 unsigned Opcode = 0;
13363 if (!TLI.isOperationLegalOrCustom(Opcode, VT))
13366 return {Opcode,
LHS,
RHS};
13374 EVT VT =
LHS.getValueType();
13379 bool IsStrict =
Cond->isStrictFPOpcode();
13385 DAG,
DL, CC, Op0, Op1,
LHS,
RHS,
N->getFlags(), IsStrict);
13393 {
Cond.getOperand(0), NewLHS, NewRHS});
13397 return DAG.
getNode(Opcode,
DL, VT, NewLHS, NewRHS);
13432 if (!CTV || !CFV || !CCnst)
13437 if (CTV->getAPIntValue() == CFV->getAPIntValue())
13440 const APInt &CmpVal = CCnst->getAPIntValue();
13441 bool MatchesTV = CmpVal == CTV->getAPIntValue();
13442 bool MatchesFV = CmpVal == CFV->getAPIntValue();
13443 if (!MatchesTV && !MatchesFV)
13462 N->getOperand(2),
N->getOperand(3),
SDLoc(
N),
13463 N->getValueType(0), DAG,
N->getFlags());
13466SDValue DAGCombiner::visitSELECT(SDNode *
N) {
13470 EVT VT =
N->getValueType(0);
13473 SDNodeFlags
Flags =
N->getFlags();
13485 if (
SDValue V = foldSelectOfConstants(
N))
13493 CC, N1, N2,
DL, VT, DAG, Flags))
13498 if (SimplifySelectOps(
N, N1, N2))
13501 if (VT0 == MVT::i1) {
13510 bool normalizeToSequence =
13519 if (normalizeToSequence || !InnerSelect.
use_empty())
13521 InnerSelect, N2, Flags);
13524 recursivelyDeleteUnusedNodes(InnerSelect.
getNode());
13531 Cond1, N1, N2, Flags);
13532 if (normalizeToSequence || !InnerSelect.
use_empty())
13534 InnerSelect, Flags);
13537 recursivelyDeleteUnusedNodes(InnerSelect.
getNode());
13547 if (!normalizeToSequence) {
13553 if (
SDValue Combined = visitANDLike(N0, N1_0,
N)) {
13566 if (!normalizeToSequence) {
13572 if (
SDValue Combined = visitORLike(N0, N2_0,
DL))
13609 combineMinNumMaxNum(
DL, VT, Cond0, Cond1, N1, N2, CC))
13622 if (
C && NotC &&
C->getAPIntValue() == ~NotC->getAPIntValue()) {
13645 (!LegalOperations &&
13653 if (
SDValue ABD = foldSelectToABD(Cond0, Cond1, N1, N2, CC,
DL))
13656 if (
SDValue NewSel = SimplifySelect(
DL, N0, N1, N2))
13661 if (
SDValue UMin = foldSelectToUMin(Cond0, Cond1, N1, N2, CC,
DL))
13666 if (
SDValue BinOp = foldSelectOfBinops(
N))
13685 EVT VT =
N->getValueType(0);
13693 if (
LHS->getNumOperands() != 2 ||
RHS->getNumOperands() != 2)
13702 for (
int i = 0; i < NumElems / 2; ++i) {
13703 if (
Cond->getOperand(i)->isUndef())
13706 if (BottomHalf ==
nullptr)
13708 else if (
Cond->getOperand(i).getNode() != BottomHalf)
13714 for (
int i = NumElems / 2; i < NumElems; ++i) {
13715 if (
Cond->getOperand(i)->isUndef())
13718 if (TopHalf ==
nullptr)
13720 else if (
Cond->getOperand(i).getNode() != TopHalf)
13724 assert(TopHalf && BottomHalf &&
13725 "One half of the selector was all UNDEFs and the other was all the "
13726 "same value. This should have been addressed before this function.");
13729 BottomHalf->
isZero() ?
RHS->getOperand(0) :
LHS->getOperand(0),
13730 TopHalf->
isZero() ?
RHS->getOperand(1) :
LHS->getOperand(1));
13743 EVT VT = BasePtr.getValueType();
13747 SplatVal.getValueType() == VT) {
13753 if (Index.getOpcode() !=
ISD::ADD)
13780 Index = Index.getOperand(0);
13793 Index = Index.getOperand(0);
13800SDValue DAGCombiner::visitVPSCATTER(SDNode *
N) {
13831SDValue DAGCombiner::visitMSCATTER(SDNode *
N) {
13863SDValue DAGCombiner::visitMSTORE(SDNode *
N) {
13877 MST1->isSimple() && MST1->getBasePtr() == Ptr &&
13880 MST1->getMemoryVT().getStoreSize()) ||
13884 CombineTo(MST1, MST1->getChain());
13901 if (CombineToPreIndexedLoadStore(
N) || CombineToPostIndexedLoadStore(
N))
13905 Value.getValueType().isInteger() &&
13908 APInt TruncDemandedBits =
13935 Value.getOperand(0).getValueType());
13945SDValue DAGCombiner::visitVP_STRIDED_STORE(SDNode *
N) {
13950 CStride && CStride->getZExtValue() == EltVT.
getStoreSize()) {
13951 return DAG.
getStoreVP(SST->getChain(), SDLoc(
N), SST->getValue(),
13952 SST->getBasePtr(), SST->getOffset(), SST->getMask(),
13953 SST->getVectorLength(), SST->getMemoryVT(),
13954 SST->getMemOperand(), SST->getAddressingMode(),
13955 SST->isTruncatingStore(), SST->isCompressingStore());
13960SDValue DAGCombiner::visitVECTOR_COMPRESS(SDNode *
N) {
13964 SDValue Passthru =
N->getOperand(2);
13967 bool HasPassthru = !Passthru.
isUndef();
13980 unsigned NumSelected = 0;
13982 for (
unsigned I = 0;
I < NumElmts; ++
I) {
13991 Ops.push_back(VecI);
13995 for (
unsigned Rest = NumSelected; Rest < NumElmts; ++Rest) {
14001 Ops.push_back(Val);
14009SDValue DAGCombiner::visitVPGATHER(SDNode *
N) {
14037SDValue DAGCombiner::visitMGATHER(SDNode *
N) {
14050 return CombineTo(
N, PassThru, MGT->
getChain());
14069SDValue DAGCombiner::visitMLOAD(SDNode *
N) {
14086 return CombineTo(
N, NewLd, NewLd.
getValue(1));
14090 if (CombineToPreIndexedLoadStore(
N) || CombineToPostIndexedLoadStore(
N))
14096SDValue DAGCombiner::visitMHISTOGRAM(SDNode *
N) {
14106 EVT DataVT =
Index.getValueType();
14124SDValue DAGCombiner::visitPARTIAL_REDUCE_MLA(SDNode *
N) {
14125 if (
SDValue Res = foldPartialReduceMLAMulOp(
N))
14127 if (
SDValue Res = foldPartialReduceAdd(
N))
14145SDValue DAGCombiner::foldPartialReduceMLAMulOp(SDNode *
N) {
14167 bool IsMLS =
false;
14197 RHS.getValueType().getScalarType()));
14205 auto IsIntOrFPExtOpcode = [](
unsigned int Opcode) {
14209 unsigned LHSOpcode =
LHS->getOpcode();
14210 if (!IsIntOrFPExtOpcode(LHSOpcode))
14221 EVT OpVT =
Op.getValueType();
14224 if (OrigOp1.
getOpcode() == ISD::VP_MERGE)
14236 EVT AccVT = Acc.getValueType();
14247 unsigned LHSBits =
LHS.getValueType().getScalarSizeInBits();
14264 ApplyPredicate(
C, LHSExtOp);
14265 return GetMLA(NewOpcode, Acc, LHSExtOp,
C);
14268 unsigned RHSOpcode =
RHS->getOpcode();
14269 if (!IsIntOrFPExtOpcode(RHSOpcode))
14294 EVT AccElemVT = Acc.getValueType().getVectorElementType();
14296 NewOpc !=
N->getOpcode())
14306 ApplyPredicate(RHSExtOp, LHSExtOp);
14307 return GetMLA(NewOpc, Acc, LHSExtOp, RHSExtOp);
14317SDValue DAGCombiner::foldPartialReduceAdd(SDNode *
N) {
14337 bool IsMLS =
false;
14351 if (Op1IsSigned != NodeIsSigned &&
14372 if (PromOp1VT == UnextOp1VT)
14374 UnextOp1VT = PromOp1VT;
14390 : DAG.
getNode(NewOpcode,
DL, AccVT, Acc, UnextOp1, Constant);
14393SDValue DAGCombiner::visitLOOP_DEPENDENCE_MASK(SDNode *
N) {
14395 EVT VT =
N->getValueType(0);
14396 unsigned LaneOffset =
N->getConstantOperandVal(3);
14399 if (LaneOffset == 0 &&
14406SDValue DAGCombiner::visitVP_STRIDED_LOAD(SDNode *
N) {
14411 CStride && CStride->getZExtValue() == EltVT.
getStoreSize()) {
14413 SLD->getAddressingMode(), SLD->getExtensionType(), SLD->getValueType(0),
14414 SDLoc(
N), SLD->getChain(), SLD->getBasePtr(), SLD->getOffset(),
14415 SLD->getMask(), SLD->getVectorLength(), SLD->getMemoryVT(),
14416 SLD->getMemOperand(), SLD->isExpandingLoad());
14417 return CombineTo(
N, NewLd, NewLd.
getValue(1));
14424SDValue DAGCombiner::foldVSelectOfConstants(SDNode *
N) {
14428 EVT VT =
N->getValueType(0);
14429 if (!
Cond.hasOneUse() ||
Cond.getScalarValueSizeInBits() != 1 ||
14438 bool AllAddOne =
true;
14439 bool AllSubOne =
true;
14441 for (
unsigned i = 0; i != Elts; ++i) {
14464 if (AllAddOne || AllSubOne) {
14500 EVT CondVT =
Cond.getValueType();
14501 assert(CondVT.
isVector() &&
"Vector select expects a vector selector!");
14509 if (!IsTAllZero && !IsTAllOne && !IsFAllZero && !IsFAllOne)
14513 if (IsTAllZero && IsFAllZero) {
14522 Cond.getOperand(0).getValueType() == VT && VT.
isSimple() &&
14524 TValAPInt.
isOne() &&
14548 if (!IsTAllOne && !IsFAllZero &&
Cond.hasOneUse() &&
14552 if (IsTAllZero || IsFAllOne) {
14565 "Select condition no longer all-sign bits");
14568 if (IsTAllOne && IsFAllZero)
14597SDValue DAGCombiner::visitVSELECT(SDNode *
N) {
14601 EVT VT =
N->getValueType(0);
14634 bool isAbs =
false;
14653 AddToWorklist(Shift.
getNode());
14654 AddToWorklist(
Add.getNode());
14667 if (
SDValue FMinMax = combineMinNumMaxNum(
DL, VT,
LHS,
RHS, N1, N2, CC))
14684 EVT NarrowVT =
LHS.getValueType();
14692 SetCCWidth < WideWidth &&
14697 Ld->getAddressSpace(), LoadExtOpcode,
14708 DAG.
getSetCC(
DL, WideSetCCVT, WideLHS, WideRHS, CC);
14744 (OpLHS == CondLHS || OpRHS == CondLHS))
14747 if (OpRHS.getOpcode() == CondRHS.getOpcode() &&
14750 CondLHS == OpLHS) {
14754 auto MatchUADDSAT = [](ConstantSDNode *
Op, ConstantSDNode *
Cond) {
14755 return Cond->getAPIntValue() == ~Op->getAPIntValue();
14796 if (OpLHS ==
LHS) {
14811 auto MatchUSUBSAT = [](ConstantSDNode *
Op, ConstantSDNode *
Cond) {
14812 return (!
Op && !
Cond) ||
14814 Cond->getAPIntValue() == (-
Op->getAPIntValue() - 1));
14850 if (SimplifySelectOps(
N, N1, N2))
14870 if (
SDValue V = foldVSelectOfConstants(
N))
14889SDValue DAGCombiner::visitSELECT_CC(SDNode *
N) {
14913 AddToWorklist(
SCC.getNode());
14918 return SCCC->isZero() ? N3 : N2;
14922 if (
SCC->isUndef())
14928 SCC.getOperand(0),
SCC.getOperand(1), N2, N3,
14929 SCC.getOperand(2),
SCC->getFlags());
14934 if (SimplifySelectOps(
N, N2, N3))
14938 DAG,
DL, CC, N0, N1, N2, N3,
N->getFlags(),
false);
14940 return DAG.
getNode(Opcode,
DL,
N->getValueType(0), NewLHS, NewRHS,
14944 return SimplifySelectCC(
DL, N0, N1, N2, N3, CC);
14947SDValue DAGCombiner::visitSETCC(SDNode *
N) {
14956 EVT VT =
N->getValueType(0);
14963 if (PreferSetCC && Combined.getOpcode() !=
ISD::SETCC) {
14964 SDValue NewSetCC = rebuildSetCC(Combined);
14992 A.getOperand(0) ==
B.getOperand(0);
14996 B.getOperand(0) ==
A;
14999 bool IsRotate =
false;
15002 if (IsAndWithShift(N0, N1)) {
15004 ShiftOrRotate = N1;
15005 }
else if (IsAndWithShift(N1, N0)) {
15007 ShiftOrRotate = N0;
15008 }
else if (IsRotateWithOp(N0, N1)) {
15011 ShiftOrRotate = N1;
15012 }
else if (IsRotateWithOp(N1, N0)) {
15015 ShiftOrRotate = N0;
15018 if (AndOrOp && ShiftOrRotate && ShiftOrRotate.hasOneUse() &&
15023 auto GetAPIntValue = [](
SDValue Op) -> std::optional<APInt> {
15026 if (CNode ==
nullptr)
15027 return std::nullopt;
15030 std::optional<APInt> AndCMask =
15031 IsRotate ? std::nullopt : GetAPIntValue(AndOrOp.
getOperand(1));
15032 std::optional<APInt> ShiftCAmt =
15033 GetAPIntValue(ShiftOrRotate.getOperand(1));
15037 if (ShiftCAmt && (IsRotate || AndCMask) && ShiftCAmt->ult(NumBits)) {
15038 unsigned ShiftOpc = ShiftOrRotate.getOpcode();
15040 bool CanTransform = IsRotate;
15041 if (!CanTransform) {
15043 CanTransform = *ShiftCAmt == (~*AndCMask).
popcount();
15045 CanTransform &= (*ShiftCAmt + AndCMask->popcount()) == NumBits;
15053 OpVT, ShiftOpc, ShiftCAmt->isPowerOf2(), *ShiftCAmt, AndCMask);
15055 if (CanTransform && NewShiftOpc != ShiftOpc) {
15057 DAG.
getNode(NewShiftOpc,
DL, OpVT, ShiftOrRotate.getOperand(0),
15058 ShiftOrRotate.getOperand(1));
15065 NumBits - ShiftCAmt->getZExtValue())
15066 : APInt::getLowBitsSet(NumBits,
15067 NumBits - ShiftCAmt->getZExtValue());
15075 return DAG.
getSetCC(
DL, VT, NewAndOrOp, NewShiftOrRotate,
Cond);
15083SDValue DAGCombiner::visitSETCCCARRY(SDNode *
N) {
15104 if (!
N.hasOneUse())
15133 unsigned Opcode =
N->getOpcode();
15135 EVT VT =
N->getValueType(0);
15138 "Expected EXTEND dag node in input!");
15180 unsigned Opcode =
N->getOpcode();
15182 EVT VT =
N->getValueType(0);
15185 "Expected EXTEND dag node in input!");
15191 return DAG.
getNode(Opcode,
DL, VT, N0);
15210 unsigned FoldOpc = Opcode;
15233 for (
unsigned i = 0; i != NumElts; ++i) {
15235 if (
Op.isUndef()) {
15246 APInt C =
Op->getAsAPIntVal().zextOrTrunc(EVTBits);
15264 bool HasCopyToRegUses =
false;
15279 for (
unsigned i = 0; i != 2; ++i) {
15297 HasCopyToRegUses =
true;
15300 if (HasCopyToRegUses) {
15301 bool BothLiveOut =
false;
15304 BothLiveOut =
true;
15311 return !ExtendNodes.
empty();
15316void DAGCombiner::ExtendSetCCUses(
const SmallVectorImpl<SDNode *> &SetCCs,
15321 for (SDNode *SetCC : SetCCs) {
15324 for (
unsigned j = 0;
j != 2; ++
j) {
15325 SDValue SOp = SetCC->getOperand(j);
15326 if (SOp == OrigLoad)
15327 Ops.push_back(ExtLoad);
15332 Ops.push_back(SetCC->getOperand(2));
15338SDValue DAGCombiner::CombineExtLoad(SDNode *
N) {
15340 EVT DstVT =
N->getValueType(0);
15345 "Unexpected node type (not an extend)!");
15383 EVT SplitSrcVT = SrcVT;
15384 EVT SplitDstVT = DstVT;
15399 const unsigned NumSplits =
15406 for (
unsigned Idx = 0; Idx < NumSplits; Idx++) {
15407 const unsigned Offset = Idx * Stride;
15425 AddToWorklist(NewChain.
getNode());
15427 CombineTo(
N, NewValue);
15433 ExtendSetCCUses(SetCCs, N0, NewValue, (
ISD::NodeType)
N->getOpcode());
15434 CombineTo(N0.
getNode(), Trunc, NewChain);
15440SDValue DAGCombiner::CombineZExtLogicopShiftLoad(SDNode *
N) {
15442 EVT VT =
N->getValueType(0);
15443 EVT OrigVT =
N->getOperand(0).getValueType();
15465 EVT MemVT =
Load->getMemoryVT();
15487 Load->getChain(),
Load->getBasePtr(),
15488 Load->getMemoryVT(),
Load->getMemOperand());
15505 Load->getValueType(0), ExtLoad);
15510 recursivelyDeleteUnusedNodes(N0.
getNode());
15519SDValue DAGCombiner::matchVSelectOpSizesWithSetCC(SDNode *Cast) {
15520 unsigned CastOpcode = Cast->
getOpcode();
15524 "Unexpected opcode for vector select narrowing/widening");
15564 bool LegalOperations,
SDNode *
N,
15578 EVT MemVT = OldExtLoad->getMemoryVT();
15579 if ((LegalOperations || !OldExtLoad->isSimple() || VT.
isVector()) &&
15580 !TLI.
isLoadLegal(VT, MemVT, OldExtLoad->getAlign(),
15581 OldExtLoad->getAddressSpace(), ExtLoadType,
false))
15586 OldExtLoad->getBasePtr(), MemVT,
15587 OldExtLoad->getMemOperand());
15594 DAG.
getValueType(OldExtLoad->getValueType(0).getScalarType()));
15612 bool NonNegZExt =
false) {
15619 (Frozen && !
Load->hasNUsesOfValue(1, 0)))
15625 "Unexpected load type or opcode");
15643 Load->getAddressSpace(), ExtLoadType,
false))
15646 bool DoXform =
true;
15650 ExtOpc, SetCCs, TLI);
15659 unsigned OldBits,
unsigned NewBits,
15664 bool IsVariadic = Dbg->isVariadic();
15667 for (
unsigned I = 0,
E = Locs.
size();
I !=
E; ++
I) {
15672 if (
Op.getSDNode() == Old.getNode() &&
Op.getResNo() == Old.getResNo()) {
15696 for (
unsigned ArgNo : AffectedArgs)
15703 Dbg->getAdditionalDependencies(), Dbg->isIndirect(), Dbg->getDebugLoc(),
15704 Dbg->getOrder(), Dbg->isVariadic());
15706 Dbg->setIsInvalidated();
15707 Dbg->setIsEmitted();
15715 auto SalvageToOldLoadSize = [&](
SDValue Old,
SDValue New,
bool IsSigned) {
15720 unsigned VarBitsOld = Old.getValueSizeInBits();
15721 unsigned VarBitsNew = New.getValueSizeInBits();
15724 if (Dbg->isInvalidated())
15727 SalvageDbgValue(Dbg, Old, New, VarBitsOld, VarBitsNew, IsSigned);
15733 Load->getValueType(0),
Load->getMemOperand());
15742 Combiner.ExtendSetCCUses(SetCCs, N0, Res, ExtOpc);
15745 if (
N->getHasDebugValue()) {
15749 if (NoReplaceTrunc) {
15751 if (
Load->getHasDebugValue()) {
15753 SalvageToOldLoadSize(OldLoadVal, ExtLoad, IsSigned);
15784 Ld->getAddressSpace(), ExtLoadType,
false))
15791 SDValue PassThru = DAG.
getNode(ExtOpc, dl, VT, Ld->getPassThru());
15793 VT, dl, Ld->getChain(), Ld->getBasePtr(), Ld->getOffset(), Ld->getMask(),
15794 PassThru, Ld->getMemoryVT(), Ld->getMemOperand(), Ld->getAddressingMode(),
15795 ExtLoadType, Ld->isExpandingLoad());
15808 EVT MemoryVT = ALoad->getMemoryVT();
15809 if (!TLI.
isLoadLegal(VT, MemoryVT, ALoad->getAlign(),
15810 ALoad->getAddressSpace(), ExtLoadType,
true))
15818 EVT OrigVT = ALoad->getValueType(0);
15821 ExtLoadType,
SDLoc(ALoad), MemoryVT, VT, ALoad->getChain(),
15822 ALoad->getBasePtr(), ALoad->getMemOperand()));
15832 bool LegalOperations) {
15844 EVT VT =
N->getValueType(0);
15845 EVT XVT =
X.getValueType();
15861 return DAG.
getNode(ShiftOpcode,
DL, VT, NotX, ShiftAmount);
15867SDValue DAGCombiner::foldSextSetcc(SDNode *
N) {
15875 EVT VT =
N->getValueType(0);
15885 if (VT.
isVector() && !LegalOperations &&
15898 return DAG.
getSetCC(
DL, VT, N00, N01, CC, {},
15905 if (SVT == MatchingVecType) {
15922 auto IsFreeToExtend = [&](
SDValue V) {
15934 if (!Ld->isSimple() ||
15935 !TLI.
isLoadLegal(VT,
V.getValueType(), Ld->getAlign(),
15936 Ld->getAddressSpace(), LoadOpcode,
false))
15941 for (SDUse &Use :
V->uses()) {
15943 SDNode *
User =
Use.getUser();
15944 if (
Use.getResNo() != 0 || User == N0.
getNode())
15949 if (
User->getOpcode() != ExtOpcode ||
User->getValueType(0) != VT)
15955 if (IsFreeToExtend(N00) && IsFreeToExtend(N01)) {
15958 return DAG.
getSetCC(
DL, VT, Ext0, Ext1, CC, {},
15976 SDValue ExtTrueVal = (SetCCWidth == 1)
15980 if (
SDValue SCC = SimplifySelectCC(
DL, N00, N01, ExtTrueVal, Zero, CC,
true))
15993 return DAG.
getSelect(
DL, VT, SetCC, ExtTrueVal, Zero, Flags);
16000SDValue DAGCombiner::visitSIGN_EXTEND(SDNode *
N) {
16002 EVT VT =
N->getValueType(0);
16006 if (
SDValue FoldedVOp = SimplifyVCastOp(
N,
DL))
16052 if (NarrowLoad.getNode() != N0.
getNode()) {
16053 CombineTo(N0.
getNode(), NarrowLoad);
16055 AddToWorklist(oye);
16063 unsigned OpBits =
Op.getScalarValueSizeInBits();
16069 if (OpBits == DestBits) {
16075 if (OpBits < DestBits) {
16084 Flags.setNoSignedWrap(
true);
16092 if (OpBits < DestBits)
16094 else if (OpBits > DestBits)
16114 if (
SDValue ExtLoad = CombineExtLoad(
N))
16150 bool NoReplaceTruncAnd = !N0.
hasOneUse();
16151 bool NoReplaceTrunc =
SDValue(LN00, 0).hasOneUse();
16154 if (NoReplaceTruncAnd) {
16157 CombineTo(N0.
getNode(), TruncAnd);
16159 if (NoReplaceTrunc) {
16164 CombineTo(LN00, Trunc, ExtLoad.
getValue(1));
16183 if (
SDValue NewVSel = matchVSelectOpSizesWithSetCC(
N))
16214 if (NewXor.getNode() == N0.
getNode()) {
16240 "Expected extend op");
16285SDValue DAGCombiner::visitZERO_EXTEND(SDNode *
N) {
16287 EVT VT =
N->getValueType(0);
16291 if (
SDValue FoldedVOp = SimplifyVCastOp(
N,
DL))
16322 APInt TruncatedBits =
16324 APInt(
Op.getScalarValueSizeInBits(), 0) :
16325 APInt::getBitsSet(
Op.getScalarValueSizeInBits(),
16326 N0.getScalarValueSizeInBits(),
16327 std::
min(
Op.getScalarValueSizeInBits(),
16330 SDValue ZExtOrTrunc = DAG.getZExtOrTrunc(Op, DL, VT);
16331 DAG.salvageDebugInfo(*N0.getNode());
16333 return ZExtOrTrunc;
16343 if (NarrowLoad.getNode() != N0.
getNode()) {
16344 CombineTo(N0.
getNode(), NarrowLoad);
16346 AddToWorklist(oye);
16354 if (
N->getFlags().hasNonNeg()) {
16362 if (OpBits == DestBits) {
16368 if (OpBits < DestBits) {
16378 Flags.setNoSignedWrap(
true);
16379 Flags.setNoUnsignedWrap(
true);
16391 AddToWorklist(
Op.getNode());
16395 return ZExtOrTrunc;
16401 AddToWorklist(
Op.getNode());
16427 EVT SrcVT = Src.getValueType();
16456 if (
SDValue ExtLoad = CombineExtLoad(
N))
16477 bool DoXform =
true;
16484 if (isAndLoadExtLoad(AndC, LN00, LoadResultTy, ExtVT))
16500 bool NoReplaceTruncAnd = !N0.
hasOneUse();
16501 bool NoReplaceTrunc =
SDValue(LN00, 0).hasOneUse();
16504 if (NoReplaceTruncAnd) {
16507 CombineTo(N0.
getNode(), TruncAnd);
16509 if (NoReplaceTrunc) {
16514 CombineTo(LN00, Trunc, ExtLoad.
getValue(1));
16523 if (
SDValue ZExtLoad = CombineZExtLogicopShiftLoad(
N))
16536 SelectionDAG::FlagInserter FlagsInserter(DAG, N0->
getFlags());
16539 if (!LegalOperations && VT.
isVector() &&
16571 if (
SDValue SCC = SimplifySelectCC(
16591 if (ShAmtC->getAPIntValue().ugt(KnownZeroBits)) {
16612 if (
SDValue NewVSel = matchVSelectOpSizesWithSetCC(
N))
16634SDValue DAGCombiner::visitANY_EXTEND(SDNode *
N) {
16636 EVT VT =
N->getValueType(0);
16670 if (NarrowLoad.getNode() != N0.
getNode()) {
16671 CombineTo(N0.
getNode(), NarrowLoad);
16673 AddToWorklist(oye);
16699 EVT SrcVT = Src.getValueType();
16730 bool DoXform =
true;
16742 CombineTo(
N, ExtLoad);
16743 if (NoReplaceTrunc) {
16745 recursivelyDeleteUnusedNodes(LN0);
16749 CombineTo(LN0, Trunc, ExtLoad.
getValue(1));
16764 if (!LegalOperations ||
16770 CombineTo(
N, ExtLoad);
16772 recursivelyDeleteUnusedNodes(LN0);
16780 SelectionDAG::FlagInserter FlagsInserter(DAG, Flags);
16787 if (VT.
isVector() && !LegalOperations) {
16814 if (
SDValue SCC = SimplifySelectCC(
16830SDValue DAGCombiner::visitAssertExt(SDNode *
N) {
16831 unsigned Opcode =
N->getOpcode();
16855 EVT MinAssertVT = AssertVT.
bitsLT(BigA_AssertVT) ? AssertVT : BigA_AssertVT;
16870 if (AssertVT.
bitsLT(BigA_AssertVT)) {
16888 if (AssertVT.
bitsLT(BigA_AssertVT) &&
16908SDValue DAGCombiner::visitAssertAlign(SDNode *
N) {
16918 std::max(AL, AAN->getAlign()));
16929 unsigned AlignShift =
Log2(AL);
16934 if (LHSAlignShift >= AlignShift || RHSAlignShift >= AlignShift) {
16935 if (LHSAlignShift < AlignShift)
16937 if (RHSAlignShift < AlignShift)
16948SDValue DAGCombiner::visitIS_FPCLASS(SDNode *
N) {
16951 EVT VT =
N->getValueType(0);
16967 if ((Mask &
Known.KnownFPClasses) != Mask) {
16980SDValue DAGCombiner::reduceLoadWidth(SDNode *
N) {
16981 unsigned Opc =
N->getOpcode();
16985 EVT VT =
N->getValueType(0);
16995 unsigned ShAmt = 0;
17000 unsigned ShiftedOffset = 0;
17020 uint64_t MemoryWidth = LN->getMemoryVT().getScalarSizeInBits();
17021 if (MemoryWidth <= ShAmt)
17032 LN->getExtensionType() != ExtType)
17041 unsigned ActiveBits = 0;
17042 if (
Mask.isMask()) {
17043 ActiveBits =
Mask.countr_one();
17044 }
else if (
Mask.isShiftedMask(ShAmt, ActiveBits)) {
17045 ShiftedOffset = ShAmt;
17066 if (!
SRL.hasOneUse())
17079 ShAmt = SRL1C->getZExtValue();
17080 uint64_t MemoryWidth = LN->getMemoryVT().getSizeInBits();
17081 if (ShAmt >= MemoryWidth)
17106 SDNode *
Mask = *(
SRL->user_begin());
17109 unsigned Offset, ActiveBits;
17110 const APInt& ShiftMask =
Mask->getConstantOperandAPInt(1);
17111 if (ShiftMask.
isMask()) {
17117 LN->getAddressSpace(), ExtType,
false))
17127 LN->getAddressSpace(), ExtType,
false)) {
17135 N0 =
SRL.getOperand(0);
17143 unsigned ShLeftAmt = 0;
17147 ShLeftAmt = N01->getZExtValue();
17168 !isLegalNarrowLdSt(LN0, ExtType, ExtVT, ShAmt))
17174 if (FreezeNode && !FreezeNode.
hasOneUse() &&
17180 auto AdjustBigEndianShift = [&](
unsigned ShAmt) {
17181 unsigned LVTStoreBits =
17184 return LVTStoreBits - EVTStoreBits - ShAmt;
17189 unsigned PtrAdjustmentInBits =
17192 uint64_t PtrOff = PtrAdjustmentInBits / 8;
17198 AddToWorklist(NewPtr.
getNode());
17202 const MDNode *OldRanges = LN0->
getRanges();
17203 const MDNode *NewRanges =
nullptr;
17207 if (ShAmt == 0 && OldRanges) {
17215 ConstantRange TruncatedCR = CR.
truncate(BitSize);
17225 NewRanges = OldRanges;
17230 MMOMetadata(LN0->
getAAInfo(), NewRanges));
17238 WorklistRemover DeadNodes(*
this);
17242 if (FreezeNode && !FreezeNode.
hasOneUse())
17259 if (ShLeftAmt != 0) {
17271 if (ShiftedOffset != 0) {
17285SDValue DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *
N) {
17288 EVT VT =
N->getValueType(0);
17319 if ((N00Bits <= ExtVTBits ||
17332 if ((N00Bits == ExtVTBits ||
17333 (!IsZext && (N00Bits < ExtVTBits ||
17335 (!LegalOperations ||
17360 if (
SDValue NarrowLoad = reduceLoadWidth(
N))
17368 if (ShAmt->getAPIntValue().ule(VTBits - ExtVTBits)) {
17372 if (((VTBits - ExtVTBits) - ShAmt->getZExtValue()) < InSignBits)
17391 CombineTo(
N, ExtLoad);
17393 AddToWorklist(ExtLoad.
getNode());
17403 ((!LegalOperations && LN0->
isSimple()) &&
17409 CombineTo(
N, ExtLoad);
17419 if (ExtVT == Ld->getMemoryVT() && Ld->hasNUsesOfValue(1, 0) &&
17421 TLI.
isLoadLegal(VT, ExtVT, Ld->getAlign(), Ld->getAddressSpace(),
17424 VT,
DL, Ld->getChain(), Ld->getBasePtr(), Ld->getOffset(),
17425 Ld->getMask(), Ld->getPassThru(), ExtVT, Ld->getMemOperand(),
17426 Ld->getAddressingMode(),
ISD::SEXTLOAD, Ld->isExpandingLoad());
17427 CombineTo(
N, Frozen ? N0 : ExtMaskedLoad);
17428 CombineTo(Ld, ExtMaskedLoad, ExtMaskedLoad.
getValue(1));
17435 if (
SDValue(GN0, 0).hasOneUse() && ExtVT == GN0->getMemoryVT() &&
17437 SDValue Ops[] = {GN0->getChain(), GN0->getPassThru(), GN0->getMask(),
17438 GN0->getBasePtr(), GN0->getIndex(), GN0->getScale()};
17441 DAG.
getVTList(VT, MVT::Other), ExtVT,
DL,
Ops, GN0->getMemOperand(),
17444 CombineTo(
N, ExtLoad);
17446 AddToWorklist(ExtLoad.
getNode());
17469 (!LegalOperations ||
17483 bool LegalOperations) {
17484 unsigned InregOpcode =
N->getOpcode();
17488 EVT VT =
N->getValueType(0);
17490 *DAG.
getContext(), Src.getValueType().getVectorElementType());
17493 "Expected EXTEND_VECTOR_INREG dag node in input!");
17502 Src = Src.getOperand(0);
17503 if (Src.getValueType() != SrcVT)
17509 return DAG.
getNode(Opcode,
DL, VT, Src);
17512SDValue DAGCombiner::visitEXTEND_VECTOR_INREG(SDNode *
N) {
17514 EVT VT =
N->getValueType(0);
17538SDValue DAGCombiner::visitTRUNCATE_USAT_U(SDNode *
N) {
17539 EVT VT =
N->getValueType(0);
17560 unsigned NumSrcBits = In.getScalarValueSizeInBits();
17562 assert(NumSrcBits > NumDstBits &&
"Unexpected types for truncate operation");
17583 unsigned NumSrcBits = In.getScalarValueSizeInBits();
17585 assert(NumSrcBits > NumDstBits &&
"Unexpected types for truncate operation");
17606 unsigned NumSrcBits = In.getScalarValueSizeInBits();
17608 assert(NumSrcBits > NumDstBits &&
"Unexpected types for truncate operation");
17631 auto AllowedTruncateSat = [&](
unsigned Opc,
EVT SrcVT,
EVT VT) ->
bool {
17643 }
else if (Src.getOpcode() ==
ISD::UMIN) {
17655SDValue DAGCombiner::visitTRUNCATE(SDNode *
N) {
17657 EVT VT =
N->getValueType(0);
17672 return SaturatedTR;
17724 if (LegalTypes && !LegalOperations && VT.
isScalarInteger() && VT != MVT::i1 &&
17726 EVT TrTy =
N->getValueType(0);
17731 if (Src.getOpcode() ==
ISD::SRL && Src.getOperand(0)->hasOneUse()) {
17734 Src = Src.getOperand(0);
17741 EVT VecTy = Src.getOperand(0).getValueType();
17742 EVT ExTy = Src.getValueType();
17746 auto NewEltCnt = EltCnt * SizeRatio;
17751 SDValue EltNo = Src->getOperand(1);
17754 int Index = isLE ? (Elt * SizeRatio + EltOffset)
17755 : (Elt * SizeRatio + (SizeRatio - 1) - EltOffset);
17766 if (!LegalOperations ||
17789 AddToWorklist(Amt.
getNode());
17839 if (BuildVectEltTy == TruncVecEltTy) {
17843 unsigned TruncEltOffset = BuildVecNumElts / TruncVecNumElts;
17844 unsigned FirstElt = isLE ? 0 : (TruncEltOffset - 1);
17846 assert((BuildVecNumElts % TruncVecNumElts) == 0 &&
17847 "Invalid number of elements");
17850 for (
unsigned i = FirstElt, e = BuildVecNumElts; i <
e;
17851 i += TruncEltOffset)
17861 if (
SDValue Reduced = reduceLoadWidth(
N))
17884 unsigned NumDefs = 0;
17888 if (!
X.isUndef()) {
17905 if (NumDefs == 1) {
17906 assert(
V.getNode() &&
"The single defined operand is empty!");
17908 for (
unsigned i = 0, e = VTs.
size(); i != e; ++i) {
17914 AddToWorklist(
NV.getNode());
17929 (!LegalOperations ||
17957 if (
SDValue NewVSel = matchVSelectOpSizesWithSetCC(
N))
17971 if (!LegalOperations && N0.
hasOneUse() &&
17988 Flags.setNoUnsignedWrap(
true);
18013 if (!LegalOperations && N0.
hasOneUse() &&
18054 if (!LegalOperations && N0.
hasOneUse() &&
18062 bool CanFold =
false;
18070 unsigned NeededBits = SrcBits - TruncBits;
18096SDValue DAGCombiner::CombineConsecutiveLoads(SDNode *
N, EVT VT) {
18109 !LD1->hasOneUse() || !LD2->hasOneUse() ||
18110 LD1->getAddressSpace() != LD2->getAddressSpace())
18113 unsigned LD1Fast = 0;
18114 EVT LD1VT = LD1->getValueType(0);
18119 *LD1->getMemOperand(), &LD1Fast) && LD1Fast)
18120 return DAG.
getLoad(VT, SDLoc(
N), LD1->getChain(), LD1->getBasePtr(),
18121 LD1->getPointerInfo(), LD1->getAlign());
18132SDValue DAGCombiner::foldBitcastedFPLogic(SDNode *
N, SelectionDAG &DAG,
18136 EVT VT =
N->getValueType(0);
18173 auto IsBitCastOrFree = [&TLI, FPOpcode](
SDValue Op, EVT VT) {
18187 IsBitCastOrFree(LogicOp0, VT)) {
18190 NumFPLogicOpsConv++;
18199SDValue DAGCombiner::visitBITCAST(SDNode *
N) {
18201 EVT VT =
N->getValueType(0);
18226 if (!LegalOperations ||
18232 if (
C.getNode() !=
N)
18245 auto IsFreeBitcast = [VT](
SDValue V) {
18247 V.getOperand(0).getValueType() == VT) ||
18260 auto CastLoad = [
this, &VT](
SDValue N0,
const SDLoc &
DL) {
18282 if ((LegalOperations || !LN0->
isSimple()) &&
18292 if (
const MDNode *MD = LN0->
getRanges()) {
18304 if (
SDValue NewLd = CastLoad(N0, SDLoc(
N)))
18311 if (
SDValue V = foldBitcastedFPLogic(
N, DAG, TLI))
18331 AddToWorklist(NewConv.
getNode());
18334 if (N0.
getValueType() == MVT::ppcf128 && !LegalTypes) {
18341 AddToWorklist(FlipBit.
getNode());
18348 AddToWorklist(
Hi.getNode());
18350 AddToWorklist(FlipBit.
getNode());
18354 AddToWorklist(FlipBits.
getNode());
18384 AddToWorklist(
X.getNode());
18388 if (OrigXWidth < VTWidth) {
18390 AddToWorklist(
X.getNode());
18391 }
else if (OrigXWidth > VTWidth) {
18396 X.getValueType(),
X,
18398 X.getValueType()));
18399 AddToWorklist(
X.getNode());
18401 AddToWorklist(
X.getNode());
18404 if (N0.
getValueType() == MVT::ppcf128 && !LegalTypes) {
18407 AddToWorklist(Cst.
getNode());
18409 AddToWorklist(
X.getNode());
18411 AddToWorklist(XorResult.
getNode());
18415 SDLoc(XorResult)));
18416 AddToWorklist(XorResult64.
getNode());
18419 DAG.
getConstant(SignBit, SDLoc(XorResult64), MVT::i64));
18420 AddToWorklist(FlipBit.
getNode());
18423 AddToWorklist(FlipBits.
getNode());
18429 AddToWorklist(
X.getNode());
18434 AddToWorklist(Cst.
getNode());
18442 if (
SDValue CombineLD = CombineConsecutiveLoads(N0.
getNode(), VT))
18466 auto PeekThroughBitcast = [&](
SDValue Op) {
18468 Op.getOperand(0).getValueType() == VT)
18485 SmallVector<int, 8> NewMask;
18487 for (
int i = 0; i != MaskScale; ++i)
18488 NewMask.
push_back(M < 0 ? -1 : M * MaskScale + i);
18493 return LegalShuffle;
18499SDValue DAGCombiner::visitBUILD_PAIR(SDNode *
N) {
18500 EVT VT =
N->getValueType(0);
18501 return CombineConsecutiveLoads(
N, VT);
18504SDValue DAGCombiner::visitFREEZE(SDNode *
N) {
18515 while (!
N->use_empty())
18520 assert(
N->getOperand(0) == FrozenN0 &&
"Expected cycle in DAG");
18550 bool AllowMultipleMaybePoisonOperands =
18578 SmallSet<SDValue, 8> MaybePoisonOperands;
18579 SmallVector<unsigned, 8> MaybePoisonOperandNumbers;
18584 bool HadMaybePoisonOperands = !MaybePoisonOperands.
empty();
18585 bool IsNewMaybePoisonOperand = MaybePoisonOperands.
insert(
Op).second;
18586 if (IsNewMaybePoisonOperand)
18587 MaybePoisonOperandNumbers.
push_back(OpNo);
18588 if (!HadMaybePoisonOperands)
18590 if (IsNewMaybePoisonOperand && !AllowMultipleMaybePoisonOperands) {
18599 for (
unsigned OpNo : MaybePoisonOperandNumbers) {
18610 SDValue MaybePoisonOperand =
N->getOperand(0).getOperand(OpNo);
18612 if (MaybePoisonOperand.
isUndef())
18619 FrozenMaybePoisonOperand.
getOperand(0) == FrozenMaybePoisonOperand) {
18623 MaybePoisonOperand);
18659 SDNodeFlags SrcFlags = N0->
getFlags();
18660 SDNodeFlags SafeFlags;
18673 return N->getFlags().hasAllowContract();
18677SDValue DAGCombiner::visitFADDForFMACombine(SDNode *
N) {
18680 EVT VT =
N->getValueType(0);
18684 bool HasFMAD = (LegalOperations && TLI.
isFMADLegal(DAG,
N));
18692 if (!HasFMAD && !HasFMA)
18697 bool AllowFusionGlobally = HasFMAD;
18699 if (!AllowFusionGlobally && !
N->getFlags().hasAllowContract())
18717 unsigned Opcode =
N.getOpcode();
18726 return AllowFusionGlobally ||
N->getFlags().hasAllowContract();
18756 bool CanReassociate =
N->getFlags().hasAllowReassociation();
18757 if (CanReassociate) {
18762 }
else if (isFusedOp(N1) && N1.
hasOneUse()) {
18768 while (
E && isFusedOp(TmpFMA) && TmpFMA.
hasOneUse()) {
18792 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
18806 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
18819 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X,
Y,
18820 DAG.
getNode(PreferredFusedOpcode, SL, VT,
18825 if (isFusedOp(N0)) {
18849 DAG.
getNode(PreferredFusedOpcode, SL, VT,
18855 if (isFusedOp(N00)) {
18869 if (isFusedOp(N1)) {
18890 if (isFusedOp(N10)) {
18907SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *
N) {
18910 EVT VT =
N->getValueType(0);
18914 bool HasFMAD = (LegalOperations && TLI.
isFMADLegal(DAG,
N));
18922 if (!HasFMAD && !HasFMA)
18925 const SDNodeFlags
Flags =
N->getFlags();
18928 bool AllowFusionGlobally = HasFMAD;
18931 if (!AllowFusionGlobally && !
N->getFlags().hasAllowContract())
18940 bool NoSignedZero =
Flags.hasNoSignedZeros();
18947 return AllowFusionGlobally ||
N->getFlags().hasAllowContract();
18963 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
18975 if (
SDValue V = tryToFoldXSubYZ(N0, N1))
18978 if (
SDValue V = tryToFoldXYSubZ(N0, N1))
18982 if (
SDValue V = tryToFoldXYSubZ(N0, N1))
18985 if (
SDValue V = tryToFoldXSubYZ(N0, N1))
18994 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19008 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19024 PreferredFusedOpcode, SL, VT,
19046 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19069 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19082 unsigned Opcode =
N.getOpcode();
19087 if (
Aggressive &&
N->getFlags().hasAllowReassociation()) {
19088 bool CanFuse =
N->getFlags().hasAllowContract();
19091 if (CanFuse && isFusedOp(N0) &&
19092 isContractableAndReassociableFMUL(N0.
getOperand(2)) &&
19096 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19104 if (CanFuse && isFusedOp(N1) &&
19105 isContractableAndReassociableFMUL(N1.
getOperand(2)) &&
19110 PreferredFusedOpcode, SL, VT,
19112 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19118 if (isFusedOp(N0) && N0->
hasOneUse()) {
19122 if (isContractableAndReassociableFMUL(N020) &&
19128 PreferredFusedOpcode, SL, VT,
19144 if (isFusedOp(N00)) {
19146 if (isContractableAndReassociableFMUL(N002) &&
19150 PreferredFusedOpcode, SL, VT,
19154 PreferredFusedOpcode, SL, VT,
19167 if (isContractableAndReassociableFMUL(N120) &&
19173 PreferredFusedOpcode, SL, VT,
19175 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19193 if (isContractableAndReassociableFMUL(N102) &&
19199 PreferredFusedOpcode, SL, VT,
19203 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19217SDValue DAGCombiner::visitFMULForFMADistributiveCombine(SDNode *
N) {
19220 EVT VT =
N->getValueType(0);
19228 if (!
FAdd->getFlags().hasNoInfs())
19239 bool HasFMAD = LegalOperations && TLI.
isFMADLegal(DAG,
N);
19242 if (!HasFMAD && !HasFMA)
19255 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X.getOperand(0),
Y,
19257 if (
C->isMinusOne())
19258 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X.getOperand(0),
Y,
19265 if (
SDValue FMA = FuseFADD(N0, N1))
19267 if (
SDValue FMA = FuseFADD(N1, N0))
19278 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19281 if (C0->isMinusOne())
19282 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19288 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X.getOperand(0),
Y,
19290 if (C1->isMinusOne())
19291 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X.getOperand(0),
Y,
19298 if (
SDValue FMA = FuseFSUB(N0, N1))
19300 if (
SDValue FMA = FuseFSUB(N1, N0))
19306SDValue DAGCombiner::visitFADD(SDNode *
N) {
19311 EVT VT =
N->getValueType(0);
19313 SDNodeFlags
Flags =
N->getFlags();
19314 SelectionDAG::FlagInserter FlagsInserter(DAG,
N);
19324 if (N0CFP && !N1CFP)
19329 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
19334 if (N1C && N1C->
isZero())
19338 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
19344 N1, DAG, LegalOperations, ForCodeSize))
19350 N0, DAG, LegalOperations, ForCodeSize))
19357 return C &&
C->isExactlyValue(-2.0);
19361 if (isFMulNegTwo(N0)) {
19367 if (isFMulNegTwo(N1)) {
19378 if (
Flags.hasNoNaNs() && AllowNewConst) {
19391 if (
Flags.hasAllowReassociation() &&
Flags.hasNoSignedZeros() &&
19409 if (CFP01 && !CFP00 && N0.
getOperand(0) == N1) {
19430 if (CFP11 && !CFP10 && N1.
getOperand(0) == N0) {
19477 if (
Flags.hasAllowReassociation() &&
Flags.hasNoSignedZeros()) {
19480 VT, N0, N1, Flags))
19485 if (
SDValue Fused = visitFADDForFMACombine(
N)) {
19487 AddToWorklist(Fused.getNode());
19493SDValue DAGCombiner::visitSTRICT_FADD(SDNode *
N) {
19497 EVT VT =
N->getValueType(0);
19498 EVT ChainVT =
N->getValueType(1);
19500 SelectionDAG::FlagInserter FlagsInserter(DAG,
N);
19505 N1, DAG, LegalOperations, ForCodeSize)) {
19507 {Chain, N0, NegN1});
19513 N0, DAG, LegalOperations, ForCodeSize)) {
19515 {Chain, N1, NegN0});
19520SDValue DAGCombiner::visitFSUB(SDNode *
N) {
19525 EVT VT =
N->getValueType(0);
19527 const SDNodeFlags
Flags =
N->getFlags();
19528 SelectionDAG::FlagInserter FlagsInserter(DAG,
N);
19539 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
19542 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
19546 if (N1CFP && N1CFP->
isZero()) {
19554 if (
Flags.hasNoNaNs())
19559 if (N0CFP && N0CFP->
isZero()) {
19576 if (
Flags.hasAllowReassociation() &&
Flags.hasNoSignedZeros() &&
19592 if (
SDValue Fused = visitFSUBForFMACombine(
N)) {
19593 AddToWorklist(Fused.getNode());
19615SDValue DAGCombiner::combineFMulOrFDivWithIntPow2(SDNode *
N) {
19616 EVT VT =
N->getValueType(0);
19622 std::optional<int> Mantissa;
19623 auto GetConstAndPow2Ops = [&](
unsigned ConstOpIdx) {
19624 if (ConstOpIdx == 1 &&
N->getOpcode() ==
ISD::FDIV)
19641 auto IsFPConstValid = [
N, MaxExpChange, &Mantissa](ConstantFPSDNode *CFP) {
19642 if (CFP ==
nullptr)
19645 const APFloat &APF = CFP->getValueAPF();
19653 int CurExp =
ilogb(APF);
19656 N->getOpcode() ==
ISD::FMUL ? CurExp : (CurExp - MaxExpChange);
19659 N->getOpcode() ==
ISD::FDIV ? CurExp : (CurExp + MaxExpChange);
19667 Mantissa = ThisMantissa;
19669 return *Mantissa == ThisMantissa && ThisMantissa > 0;
19676 if (!GetConstAndPow2Ops(0) && !GetConstAndPow2Ops(1))
19704 NewIntVT, DAG.
getBitcast(NewIntVT, ConstOp), Shift);
19709SDValue DAGCombiner::visitFMUL(SDNode *
N) {
19713 EVT VT =
N->getValueType(0);
19715 const SDNodeFlags
Flags =
N->getFlags();
19716 SelectionDAG::FlagInserter FlagsInserter(DAG,
N);
19732 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
19735 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
19738 if (
Flags.hasAllowReassociation()) {
19764 VT, N0, N1, Flags))
19788 HandleSDNode NegN0Handle(NegN0);
19798 if (
Flags.hasNoNaNs() &&
Flags.hasNoSignedZeros() &&
19829 if (TrueOpnd->isMinusOne() && FalseOpnd->isOne() &&
19833 if (TrueOpnd->isOne() && FalseOpnd->isMinusOne())
19842 if (
SDValue Fused = visitFMULForFMADistributiveCombine(
N)) {
19843 AddToWorklist(Fused.getNode());
19849 if (
SDValue R = combineFMulOrFDivWithIntPow2(
N))
19855SDValue DAGCombiner::visitFMA(SDNode *
N) {
19862 EVT VT =
N->getValueType(0);
19865 SelectionDAG::FlagInserter FlagsInserter(DAG,
N);
19880 HandleSDNode NegN0Handle(NegN0);
19888 if (
N->getFlags().hasNoNaNs() &&
N->getFlags().hasNoInfs()) {
19889 if (
N->getFlags().hasNoSignedZeros() || (N2CFP && !N2CFP->
isNegZero())) {
19890 if (N0CFP && N0CFP->
isZero())
19892 if (N1CFP && N1CFP->
isZero())
19897 if (N0CFP && N0CFP->
isOne())
19899 if (N1CFP && N1CFP->
isOne())
19907 bool CanReassociate =
N->getFlags().hasAllowReassociation();
19908 if (CanReassociate) {
19929 if (N1CFP->
isOne())
19935 AddToWorklist(RHSNeg.
getNode());
19949 if (CanReassociate) {
19951 if (N1CFP && N0 == N2) {