76#include <initializer_list>
89#define DEBUG_TYPE "dagcombine"
91STATISTIC(NodesCombined ,
"Number of dag nodes combined");
92STATISTIC(PreIndexedNodes ,
"Number of pre-indexed nodes created");
93STATISTIC(PostIndexedNodes,
"Number of post-indexed nodes created");
94STATISTIC(OpsNarrowed ,
"Number of load/op/store narrowed");
95STATISTIC(LdStFP2Int ,
"Number of fp load/store pairs transformed to int");
97STATISTIC(NumFPLogicOpsConv,
"Number of logic ops converted to fp ops");
100 "Controls whether a DAG combine is performed for a node");
104template <
typename RangeT = std::initializer_list<const MemSDNode *>>
105static const MDNode *getCommonMemCacheHint(
const RangeT &Nodes) {
106 auto Begin = Nodes.begin();
107 if (Begin == Nodes.end())
110 const MDNode *MemCacheHint = (*Begin)->getMemCacheHint();
112 return Node->getMemCacheHint() == MemCacheHint;
120 const TargetLowering &TLI;
121 const SelectionDAGTargetInfo *STI;
124 bool LegalDAG =
false;
125 bool LegalOperations =
false;
126 bool LegalTypes =
false;
128 bool DisableGenericCombines;
144 SmallSetVector<SDNode *, 32> PruningList;
152 DenseMap<SDNode *, std::pair<SDNode *, unsigned>> StoreRootCountMap;
155 BatchAAResults *BatchAA;
160 SmallPtrSet<SDNode *, 4> ChainsWithoutMergeableStores;
164 void AddUsersToWorklist(SDNode *
N) {
165 for (SDNode *Node :
N->users())
170 void AddToWorklistWithUsers(SDNode *
N) {
171 AddUsersToWorklist(
N);
178 void clearAddedDanglingWorklistEntries() {
180 while (!PruningList.empty()) {
181 auto *
N = PruningList.pop_back_val();
183 recursivelyDeleteUnusedNodes(
N);
187 SDNode *getNextWorklistEntry() {
189 clearAddedDanglingWorklistEntries();
193 while (!
N && !Worklist.empty()) {
194 N = Worklist.pop_back_val();
198 assert(
N->getCombinerWorklistIndex() >= 0 &&
199 "Found a worklist entry without a corresponding map entry!");
201 N->setCombinerWorklistIndex(-2);
211 : DAG(
D), TLI(
D.getTargetLoweringInfo()),
212 STI(
D.getSubtarget().getSelectionDAGInfo()), OptLevel(OL),
214 ForCodeSize = DAG.shouldOptForSize();
215 DisableGenericCombines = DAG.getSelectionDAGOptions().combiner_disabled ||
216 (STI && STI->disableGenericCombines(OptLevel));
219 void ConsiderForPruning(SDNode *
N) {
221 PruningList.insert(
N);
226 void AddToWorklist(SDNode *
N,
bool IsCandidateForPruning =
true,
227 bool SkipIfCombinedBefore =
false) {
229 "Deleted Node added to Worklist");
236 if (SkipIfCombinedBefore &&
N->getCombinerWorklistIndex() == -2)
239 if (IsCandidateForPruning)
240 ConsiderForPruning(
N);
242 if (
N->getCombinerWorklistIndex() < 0) {
243 N->setCombinerWorklistIndex(Worklist.size());
244 Worklist.push_back(
N);
249 void removeFromWorklist(SDNode *
N) {
250 PruningList.remove(
N);
251 StoreRootCountMap.erase(
N);
253 int WorklistIndex =
N->getCombinerWorklistIndex();
257 if (WorklistIndex < 0)
261 Worklist[WorklistIndex] =
nullptr;
262 N->setCombinerWorklistIndex(-1);
265 void deleteAndRecombine(SDNode *
N);
266 bool recursivelyDeleteUnusedNodes(SDNode *
N);
274 return CombineTo(
N, &Res, 1, AddTo);
281 return CombineTo(
N, To, 2, AddTo);
284 SDValue CombineTo(SDNode *
N, SmallVectorImpl<SDValue> *To,
286 return CombineTo(
N, To->
data(), To->
size(), AddTo);
289 void CommitTargetLoweringOpt(
const TargetLowering::TargetLoweringOpt &TLO);
296 unsigned BitWidth =
Op.getScalarValueSizeInBits();
298 return SimplifyDemandedBits(
Op, DemandedBits);
301 bool SimplifyDemandedBits(
SDValue Op,
const APInt &DemandedBits) {
302 EVT VT =
Op.getValueType();
306 return SimplifyDemandedBits(
Op, DemandedBits, DemandedElts,
false);
312 bool SimplifyDemandedVectorElts(
SDValue Op) {
314 if (
Op.getValueType().isScalableVector())
317 unsigned NumElts =
Op.getValueType().getVectorNumElements();
319 return SimplifyDemandedVectorElts(
Op, DemandedElts);
322 bool SimplifyDemandedBits(
SDValue Op,
const APInt &DemandedBits,
323 const APInt &DemandedElts,
324 bool AssumeSingleUse =
false);
325 bool SimplifyDemandedVectorElts(
SDValue Op,
const APInt &DemandedElts,
326 bool AssumeSingleUse =
false);
328 bool CombineToPreIndexedLoadStore(SDNode *
N);
329 bool CombineToPostIndexedLoadStore(SDNode *
N);
330 SDValue SplitIndexingFromLoad(LoadSDNode *LD);
331 bool SliceUpLoad(SDNode *
N);
337 StoreSDNode *getUniqueStoreFeeding(LoadSDNode *LD, int64_t &
Offset);
339 SDValue ForwardStoreValueToDirectLoad(LoadSDNode *LD);
340 bool getTruncatedStoreValue(StoreSDNode *ST,
SDValue &Val);
341 bool extendLoadedValueToExtension(LoadSDNode *LD,
SDValue &Val);
343 void ReplaceLoadWithPromotedLoad(SDNode *
Load, SDNode *ExtLoad);
352 SDValue foldShiftToAvg(SDNode *
N,
const SDLoc &
DL);
354 SDValue foldBitwiseOpWithNeg(SDNode *
N,
const SDLoc &
DL, EVT VT);
372 SDValue visitTokenFactor(SDNode *
N);
373 SDValue visitGET_ROUNDING(SDNode *
N);
374 SDValue visitMERGE_VALUES(SDNode *
N);
388 SDValue visitUADDO_CARRY(SDNode *
N);
389 SDValue visitSADDO_CARRY(SDNode *
N);
395 SDValue visitUSUBO_CARRY(SDNode *
N);
396 SDValue visitSSUBO_CARRY(SDNode *
N);
419 SDValue SimplifyVCastOp(SDNode *
N,
const SDLoc &
DL);
420 SDValue SimplifyVBinOp(SDNode *
N,
const SDLoc &
DL);
424 SDValue visitFunnelShift(SDNode *
N);
428 SDValue visitABS_MIN_POISON(SDNode *
N);
435 SDValue visitCTLZ_ZERO_POISON(SDNode *
N);
437 SDValue visitCTTZ_ZERO_POISON(SDNode *
N);
445 SDValue visitSIGN_EXTEND(SDNode *
N);
446 SDValue visitZERO_EXTEND(SDNode *
N);
449 SDValue visitAssertAlign(SDNode *
N);
451 SDValue visitSIGN_EXTEND_INREG(SDNode *
N);
452 SDValue visitEXTEND_VECTOR_INREG(SDNode *
N);
454 SDValue visitTRUNCATE_USAT_U(SDNode *
N);
459 SDValue visitSTRICT_FADD(SDNode *
N);
470 SDValue visitFCANONICALIZE(SDNode *
N);
475 SDValue visitFP_TO_INT_SAT(SDNode *
N);
491 SDValue replaceStoreOfFPConstant(StoreSDNode *ST);
492 SDValue replaceStoreOfInsertLoad(StoreSDNode *ST);
494 bool refineExtractVectorEltIntoMultipleNarrowExtractVectorElts(SDNode *
N);
495 SDValue combineStoreConcatTruncVector(StoreSDNode *
N);
497 SDValue visitATOMIC_STORE(SDNode *
N);
498 SDValue visitLIFETIME_END(SDNode *
N);
499 SDValue visitINSERT_VECTOR_ELT(SDNode *
N);
500 SDValue visitEXTRACT_VECTOR_ELT(SDNode *
N);
501 SDValue visitBUILD_VECTOR(SDNode *
N);
502 SDValue visitCONCAT_VECTORS(SDNode *
N);
503 SDValue visitVECTOR_INTERLEAVE(SDNode *
N);
504 SDValue visitVECTOR_DEINTERLEAVE(SDNode *
N);
505 SDValue visitEXTRACT_SUBVECTOR(SDNode *
N);
506 SDValue visitVECTOR_SHUFFLE(SDNode *
N);
507 SDValue visitSCALAR_TO_VECTOR(SDNode *
N);
508 SDValue visitINSERT_SUBVECTOR(SDNode *
N);
509 SDValue visitVECTOR_COMPRESS(SDNode *
N);
515 SDValue visitPARTIAL_REDUCE_MLA(SDNode *
N);
516 SDValue visitLOOP_DEPENDENCE_MASK(SDNode *
N);
519 SDValue visitVP_STRIDED_LOAD(SDNode *
N);
520 SDValue visitVP_STRIDED_STORE(SDNode *
N);
527 SDValue visitGET_FPENV_MEM(SDNode *
N);
528 SDValue visitSET_FPENV_MEM(SDNode *
N);
530 SDValue visitFADDForFMACombine(SDNode *
N);
531 SDValue visitFSUBForFMACombine(SDNode *
N);
532 SDValue visitFMULForFMADistributiveCombine(SDNode *
N);
534 SDValue XformToShuffleWithZero(SDNode *
N);
535 bool reassociationCanBreakAddressingModePattern(
unsigned Opc,
541 SDValue N1, SDNodeFlags Flags);
543 SDValue N1, SDNodeFlags Flags);
544 SDValue reassociateReduction(
unsigned RedOpc,
unsigned Opc,
const SDLoc &
DL,
546 SDNodeFlags Flags = SDNodeFlags());
548 SDValue visitShiftByConstant(SDNode *
N);
550 SDValue foldSelectOfConstants(SDNode *
N);
551 SDValue foldVSelectOfConstants(SDNode *
N);
552 SDValue foldBinOpIntoSelect(SDNode *BO);
554 SDValue hoistLogicOpWithSameOpcodeHands(SDNode *
N);
558 bool NotExtCompare =
false);
559 SDValue convertSelectOfFPConstantsToLoadOffset(
562 SDValue foldSignChangeInBitcast(SDNode *
N);
565 SDValue foldSelectOfBinops(SDNode *
N);
569 SDValue foldSubToUSubSat(EVT DstVT, SDNode *
N,
const SDLoc &
DL);
570 SDValue foldABSToABD(SDNode *
N,
const SDLoc &
DL);
575 SDValue unfoldMaskedMerge(SDNode *
N);
576 SDValue unfoldExtremeBitClearingToShifts(SDNode *
N);
578 const SDLoc &
DL,
bool foldBooleans);
582 SDValue &
CC,
bool MatchStrict =
false)
const;
583 bool isOneUseSetCC(
SDValue N)
const;
585 SDValue foldAddToAvg(SDNode *
N,
const SDLoc &
DL);
586 SDValue foldSubToAvg(SDNode *
N,
const SDLoc &
DL);
590 SDValue SimplifyNodeWithTwoResults(SDNode *
N,
unsigned LoOp,
592 SDValue CombineConsecutiveLoads(SDNode *
N, EVT VT);
593 SDValue foldBitcastedFPLogic(SDNode *
N, SelectionDAG &DAG,
594 const TargetLowering &TLI);
595 SDValue foldPartialReduceMLAMulOp(SDNode *
N);
596 SDValue foldPartialReduceAdd(SDNode *
N);
599 SDValue CombineZExtLogicopShiftLoad(SDNode *
N);
600 SDValue combineRepeatedFPDivisors(SDNode *
N);
601 SDValue combineFMulOrFDivWithIntPow2(SDNode *
N);
602 SDValue replaceShuffleOfInsert(ShuffleVectorSDNode *Shuf);
603 SDValue mergeInsertEltWithShuffle(SDNode *
N,
unsigned InsIndex);
604 SDValue combineInsertEltToShuffle(SDNode *
N,
unsigned InsIndex);
605 SDValue combineInsertEltToLoad(SDNode *
N,
unsigned InsIndex);
615 bool KnownNeverZero =
false,
616 bool InexpensiveOnly =
false,
617 std::optional<EVT> OutVT = std::nullopt);
627 bool DemandHighBits =
true);
631 bool HasPos,
unsigned PosOpcode,
632 unsigned NegOpcode,
const SDLoc &
DL);
635 bool HasPos,
unsigned PosOpcode,
636 unsigned NegOpcode,
const SDLoc &
DL);
639 SDValue MatchLoadCombine(SDNode *
N);
640 SDValue mergeTruncStores(StoreSDNode *
N);
642 SDValue ReduceLoadOpStoreWidth(SDNode *
N);
644 SDValue TransformFPLoadStorePair(SDNode *
N);
645 SDValue convertBuildVecExtToExt(SDNode *
N);
646 SDValue convertBuildVecZextToBuildVecWithZeros(SDNode *
N);
647 SDValue reduceBuildVecExtToExtBuildVec(SDNode *
N);
648 SDValue reduceBuildVecTruncToBitCast(SDNode *
N);
649 SDValue reduceBuildVecToShuffle(SDNode *
N);
650 SDValue createBuildVecShuffle(
const SDLoc &
DL, SDNode *
N,
651 ArrayRef<int> VectorMask,
SDValue VecIn1,
652 SDValue VecIn2,
unsigned LeftIdx,
654 SDValue matchVSelectOpSizesWithSetCC(SDNode *Cast);
658 void GatherAllAliases(SDNode *
N,
SDValue OriginalChain,
659 SmallVectorImpl<SDValue> &Aliases);
662 bool mayAlias(SDNode *Op0, SDNode *Op1)
const;
674 bool findBetterNeighborChains(StoreSDNode *St);
678 bool parallelizeChainedStores(StoreSDNode *St);
684 LSBaseSDNode *MemNode;
687 int64_t OffsetFromBase;
689 MemOpLink(LSBaseSDNode *
N, int64_t
Offset)
690 : MemNode(
N), OffsetFromBase(
Offset) {}
695 StoreSource getStoreSource(
SDValue StoreVal) {
699 return StoreSource::Constant;
703 return StoreSource::Constant;
704 return StoreSource::Unknown;
707 return StoreSource::Extract;
709 return StoreSource::Load;
711 return StoreSource::Unknown;
719 bool isMulAddWithConstProfitable(SDNode *MulNode,
SDValue AddNode,
725 bool isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
726 EVT LoadResultTy, EVT &ExtVT);
731 EVT &MemVT,
unsigned ShAmt = 0);
734 bool SearchForAndLoads(SDNode *
N, SmallVectorImpl<LoadSDNode*> &Loads,
735 SmallPtrSetImpl<SDNode*> &NodesWithConsts,
736 ConstantSDNode *Mask, SDNode *&NodeToMask);
739 bool BackwardsPropagateMask(SDNode *
N);
743 SDValue getMergeStoreChains(SmallVectorImpl<MemOpLink> &StoreNodes,
756 bool mergeStoresOfConstantsOrVecElts(SmallVectorImpl<MemOpLink> &StoreNodes,
757 EVT MemVT,
unsigned NumStores,
758 bool IsConstantSrc,
bool UseVector,
764 SDNode *getStoreMergeCandidates(StoreSDNode *St,
765 SmallVectorImpl<MemOpLink> &StoreNodes);
771 bool checkMergeStoreCandidatesForDependencies(
772 SmallVectorImpl<MemOpLink> &StoreNodes,
unsigned NumStores,
777 bool hasCallInLdStChain(StoreSDNode *St, LoadSDNode *Ld);
782 unsigned getConsecutiveStores(SmallVectorImpl<MemOpLink> &StoreNodes,
783 int64_t ElementSizeBytes)
const;
787 bool tryStoreMergeOfConstants(SmallVectorImpl<MemOpLink> &StoreNodes,
788 unsigned NumConsecutiveStores,
789 EVT MemVT, SDNode *Root,
bool AllowVectors);
795 bool tryStoreMergeOfExtracts(SmallVectorImpl<MemOpLink> &StoreNodes,
796 unsigned NumConsecutiveStores, EVT MemVT,
801 bool tryStoreMergeOfLoads(SmallVectorImpl<MemOpLink> &StoreNodes,
802 unsigned NumConsecutiveStores, EVT MemVT,
803 SDNode *Root,
bool AllowVectors,
804 bool IsNonTemporalStore,
bool IsNonTemporalLoad);
809 bool mergeConsecutiveStores(StoreSDNode *St);
817 SDValue distributeTruncateThroughAnd(SDNode *
N);
823 bool hasOperation(
unsigned Opcode, EVT VT) {
824 return TLI.isOperationLegalOrCustom(Opcode, VT, LegalOperations);
827 bool hasUMin(EVT VT)
const {
828 auto LK = TLI.getTypeConversion(*DAG.getContext(), VT);
831 TLI.isOperationLegalOrCustom(
ISD::UMIN, LK.second);
838 SelectionDAG &getDAG()
const {
return DAG; }
841 EVT getShiftAmountTy(EVT LHSTy) {
842 return TLI.getShiftAmountTy(LHSTy, DAG.getDataLayout());
847 bool isTypeLegal(
const EVT &VT) {
848 if (!LegalTypes)
return true;
849 return TLI.isTypeLegal(VT);
853 EVT getSetCCResultType(EVT VT)
const {
854 return TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
857 void ExtendSetCCUses(
const SmallVectorImpl<SDNode *> &SetCCs,
868 explicit WorklistRemover(DAGCombiner &dc)
869 : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
871 void NodeDeleted(SDNode *
N, SDNode *
E)
override {
872 DC.removeFromWorklist(
N);
880 explicit WorklistInserter(DAGCombiner &dc)
881 : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
885 void NodeInserted(SDNode *
N)
override { DC.ConsiderForPruning(
N); }
895 ((DAGCombiner*)
DC)->AddToWorklist(
N);
900 return ((DAGCombiner*)
DC)->CombineTo(
N, &To[0], To.
size(), AddTo);
905 return ((DAGCombiner*)
DC)->CombineTo(
N, Res, AddTo);
910 return ((DAGCombiner*)
DC)->CombineTo(
N, Res0, Res1, AddTo);
915 return ((DAGCombiner*)
DC)->recursivelyDeleteUnusedNodes(
N);
920 return ((DAGCombiner*)
DC)->CommitTargetLoweringOpt(TLO);
927void DAGCombiner::deleteAndRecombine(
SDNode *
N) {
928 removeFromWorklist(
N);
936 if (
Op->hasOneUse() ||
Op->getNumValues() > 1)
937 AddToWorklist(
Op.getNode());
946 unsigned Bits =
Offset + std::max(
LHS.getBitWidth(),
RHS.getBitWidth());
959 LHS =
N.getOperand(0);
960 RHS =
N.getOperand(1);
961 CC =
N.getOperand(2);
968 LHS =
N.getOperand(1);
969 RHS =
N.getOperand(2);
970 CC =
N.getOperand(3);
982 LHS =
N.getOperand(0);
983 RHS =
N.getOperand(1);
984 CC =
N.getOperand(4);
991bool DAGCombiner::isOneUseSetCC(
SDValue N)
const {
993 if (isSetCCEquivalent(
N, N0, N1, N2) &&
N->hasOneUse())
1005 MaskForTy = 0xFFULL;
1008 MaskForTy = 0xFFFFULL;
1011 MaskForTy = 0xFFFFFFFFULL;
1029 bool AllowTruncation =
false) {
1031 return !(Const->isOpaque() && NoOpaques);
1034 unsigned BitWidth =
N.getScalarValueSizeInBits();
1039 if (!Const || (Const->isOpaque() && NoOpaques))
1043 if ((AllowTruncation &&
1044 Const->getAPIntValue().getActiveBits() >
BitWidth) ||
1045 (!AllowTruncation && Const->getAPIntValue().getBitWidth() !=
BitWidth))
1062 return Opts.combiner_split_load_index &&
1067bool DAGCombiner::reassociationCanBreakAddressingModePattern(
unsigned Opc,
1095 : (N1.
getOperand(0).getConstantOperandVal(0) *
1100 ScalableOffset = -ScalableOffset;
1101 if (
all_of(
N->users(), [&](SDNode *Node) {
1102 if (auto *LoadStore = dyn_cast<MemSDNode>(Node);
1103 LoadStore && LoadStore->hasUniqueMemOperand() &&
1104 LoadStore->getBasePtr().getNode() == N) {
1105 TargetLoweringBase::AddrMode AM;
1106 AM.HasBaseReg = true;
1107 AM.ScalableOffset = ScalableOffset;
1108 EVT VT = LoadStore->getMemoryVT();
1109 unsigned AS = LoadStore->getAddressSpace();
1110 Type *AccessTy = VT.getTypeForEVT(*DAG.getContext());
1111 return TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy,
1126 const APInt &C2APIntVal = C2->getAPIntValue();
1134 const APInt &C1APIntVal =
C1->getAPIntValue();
1135 const APInt CombinedValueIntVal = C1APIntVal + C2APIntVal;
1138 const int64_t CombinedValue = CombinedValueIntVal.
getSExtValue();
1140 for (SDNode *Node :
N->users()) {
1147 TargetLoweringBase::AddrMode AM;
1149 AM.
BaseOffs = C2APIntVal.getSExtValue();
1151 unsigned AS =
LoadStore->getAddressSpace();
1167 for (SDNode *Node :
N->users()) {
1169 if (!LoadStore || !
LoadStore->hasUniqueMemOperand())
1174 TargetLoweringBase::AddrMode AM;
1176 AM.
BaseOffs = C2APIntVal.getSExtValue();
1178 unsigned AS =
LoadStore->getAddressSpace();
1191SDValue DAGCombiner::reassociateOpsCommutative(
unsigned Opc,
const SDLoc &
DL,
1193 SDNodeFlags Flags) {
1203 SDNodeFlags NewFlags;
1205 Flags.hasNoUnsignedWrap())
1213 return DAG.
getNode(
Opc,
DL, VT, N00, OpNode, NewFlags);
1221 return DAG.
getNode(
Opc,
DL, VT, OpNode, N01, NewFlags);
1231 if (N1 == N00 || N1 == N01)
1277 if (CC1 == CC00 && CC1 != CC01) {
1281 if (CC1 == CC01 && CC1 != CC00) {
1295 SDValue N1, SDNodeFlags Flags) {
1301 if (!
Flags.hasAllowReassociation() || !
Flags.hasNoSignedZeros())
1304 if (
SDValue Combined = reassociateOpsCommutative(
Opc,
DL, N0, N1, Flags))
1306 if (
SDValue Combined = reassociateOpsCommutative(
Opc,
DL, N1, N0, Flags))
1314SDValue DAGCombiner::reassociateReduction(
unsigned RedOpc,
unsigned Opc,
1316 SDValue N1, SDNodeFlags Flags) {
1322 SelectionDAG::FlagInserter FlagsInserter(DAG, Flags);
1340 A.getValueType() ==
C.getValueType() &&
1341 hasOperation(
Opc,
A.getValueType()) &&
1349 SelectionDAG::FlagInserter FlagsInserter(
1373 X.getValueType() !=
Y.getValueType() ||
1374 !hasOperation(
Opc,
X.getValueType()) ||
1378 (!Chain->getFlags().hasAllowReassociation() ||
1382 SelectionDAG::FlagInserter FlagsInserter(
1388 if (
SDValue V = FoldReductionChain(N0, N1))
1390 if (
SDValue V = FoldReductionChain(N1, N0))
1396SDValue DAGCombiner::CombineTo(SDNode *
N,
const SDValue *To,
unsigned NumTo,
1398 assert(
N->getNumValues() == NumTo &&
"Broken CombineTo call!");
1402 dbgs() <<
" and " << NumTo - 1 <<
" other values\n");
1403 for (
unsigned i = 0, e = NumTo; i !=
e; ++i)
1405 N->getValueType(i) == To[i].getValueType()) &&
1406 "Cannot combine value to value of different type!");
1408 WorklistRemover DeadNodes(*
this);
1412 for (
unsigned i = 0, e = NumTo; i !=
e; ++i) {
1414 AddToWorklistWithUsers(To[i].
getNode());
1422 deleteAndRecombine(
N);
1427CommitTargetLoweringOpt(
const TargetLowering::TargetLoweringOpt &TLO) {
1440 recursivelyDeleteUnusedNodes(TLO.
Old.
getNode());
1445bool DAGCombiner::SimplifyDemandedBits(
SDValue Op,
const APInt &DemandedBits,
1446 const APInt &DemandedElts,
1447 bool AssumeSingleUse) {
1448 TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
1455 AddToWorklist(
Op.getNode());
1457 CommitTargetLoweringOpt(TLO);
1464bool DAGCombiner::SimplifyDemandedVectorElts(
SDValue Op,
1465 const APInt &DemandedElts,
1466 bool AssumeSingleUse) {
1467 TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
1468 APInt KnownUndef, KnownZero;
1470 TLO, 0, AssumeSingleUse))
1474 AddToWorklist(
Op.getNode());
1476 CommitTargetLoweringOpt(TLO);
1480void DAGCombiner::ReplaceLoadWithPromotedLoad(SDNode *
Load, SDNode *ExtLoad) {
1482 EVT VT =
Load->getValueType(0);
1491 AddToWorklist(Trunc.
getNode());
1492 recursivelyDeleteUnusedNodes(
Load);
1500 EVT MemVT =
LD->getMemoryVT();
1502 :
LD->getExtensionType();
1505 LD->getChain(),
LD->getBasePtr(),
1506 MemVT,
LD->getMemOperand());
1509 unsigned Opc =
Op.getOpcode();
1513 if (
SDValue Op0 = SExtPromoteOperand(
Op.getOperand(0), PVT))
1517 if (
SDValue Op0 = ZExtPromoteOperand(
Op.getOperand(0), PVT))
1535 EVT OldVT =
Op.getValueType();
1541 AddToWorklist(NewOp.
getNode());
1544 ReplaceLoadWithPromotedLoad(
Op.getNode(), NewOp.
getNode());
1550 EVT OldVT =
Op.getValueType();
1556 AddToWorklist(NewOp.
getNode());
1559 ReplaceLoadWithPromotedLoad(
Op.getNode(), NewOp.
getNode());
1567 if (!LegalOperations)
1570 EVT VT =
Op.getValueType();
1576 unsigned Opc =
Op.getOpcode();
1584 assert(PVT != VT &&
"Don't know what type to promote to!");
1588 bool Replace0 =
false;
1590 SDValue NN0 = PromoteOperand(N0, PVT, Replace0);
1592 bool Replace1 =
false;
1594 SDValue NN1 = PromoteOperand(N1, PVT, Replace1);
1606 Replace1 &= (N0 != N1) && !N1->
hasOneUse();
1609 CombineTo(
Op.getNode(), RV);
1635 if (!LegalOperations)
1638 EVT VT =
Op.getValueType();
1644 unsigned Opc =
Op.getOpcode();
1652 assert(PVT != VT &&
"Don't know what type to promote to!");
1656 SDNodeFlags TruncFlags;
1660 N0 = SExtPromoteOperand(N0, PVT);
1662 N0 = ZExtPromoteOperand(N0, PVT);
1664 if (
Op->getFlags().hasNoUnsignedWrap()) {
1665 N0 = ZExtPromoteOperand(N0, PVT);
1667 }
else if (
Op->getFlags().hasNoSignedWrap()) {
1668 N0 = SExtPromoteOperand(N0, PVT);
1671 N0 = PromoteOperand(N0, PVT,
Replace);
1684 ReplaceLoadWithPromotedLoad(
Op.getOperand(0).getNode(), N0.
getNode());
1694 if (!LegalOperations)
1697 EVT VT =
Op.getValueType();
1703 unsigned Opc =
Op.getOpcode();
1711 assert(PVT != VT &&
"Don't know what type to promote to!");
1716 return DAG.
getNode(
Op.getOpcode(), SDLoc(
Op), VT,
Op.getOperand(0));
1721bool DAGCombiner::PromoteLoad(
SDValue Op) {
1722 if (!LegalOperations)
1728 EVT VT =
Op.getValueType();
1734 unsigned Opc =
Op.getOpcode();
1742 assert(PVT != VT &&
"Don't know what type to promote to!");
1745 SDNode *
N =
Op.getNode();
1747 EVT MemVT =
LD->getMemoryVT();
1749 :
LD->getExtensionType();
1751 LD->getChain(),
LD->getBasePtr(),
1752 MemVT,
LD->getMemOperand());
1761 AddToWorklist(
Result.getNode());
1762 recursivelyDeleteUnusedNodes(
N);
1775bool DAGCombiner::recursivelyDeleteUnusedNodes(SDNode *
N) {
1776 if (!
N->use_empty())
1779 SmallSetVector<SDNode *, 16> Nodes;
1786 if (
N->use_empty()) {
1787 for (
const SDValue &ChildN :
N->op_values())
1788 Nodes.
insert(ChildN.getNode());
1790 removeFromWorklist(
N);
1795 }
while (!Nodes.
empty());
1811 bool UseTopologicalSorting =
1814 WorklistInserter AddNodes(*
this);
1816 if (UseTopologicalSorting)
1825 if (UseTopologicalSorting) {
1827 AddToWorklist(&Node,
Node.use_empty());
1829 for (SDNode &Node : DAG.
allnodes())
1830 AddToWorklist(&Node,
Node.use_empty());
1836 HandleSDNode Dummy(DAG.
getRoot());
1839 while (SDNode *
N = getNextWorklistEntry()) {
1843 if (recursivelyDeleteUnusedNodes(
N))
1846 WorklistRemover DeadNodes(*
this);
1851 SmallSetVector<SDNode *, 16> UpdatedNodes;
1854 for (SDNode *LN : UpdatedNodes)
1855 AddToWorklistWithUsers(LN);
1867 for (
const SDValue &ChildN :
N->op_values())
1868 AddToWorklist(ChildN.getNode(),
true,
1879 ChainsWithoutMergeableStores.
clear();
1890 "Node was deleted but visit returned new node!");
1898 N->getNumValues() == 1 &&
"Type mismatch");
1908 AddToWorklistWithUsers(RV.
getNode());
1914 recursivelyDeleteUnusedNodes(
N);
1918 DAG.
setRoot(Dummy.getValue());
1922SDValue DAGCombiner::visit(SDNode *
N) {
1924 switch (
N->getOpcode()) {
2082 return visitPARTIAL_REDUCE_MLA(
N);
2085 return visitLOOP_DEPENDENCE_MASK(
N);
2113#define BEGIN_REGISTER_VP_SDNODE(SDOPC, ...) case ISD::SDOPC:
2114#include "llvm/IR/VPIntrinsics.def"
2115 return visitVPOp(
N);
2121SDValue DAGCombiner::combine(SDNode *
N) {
2126 if (!DisableGenericCombines)
2132 "Node was deleted but visit returned NULL!");
2138 TargetLowering::DAGCombinerInfo
2139 DagCombineInfo(DAG, Level,
false,
this);
2147 switch (
N->getOpcode()) {
2155 RV = PromoteIntBinOp(
SDValue(
N, 0));
2160 RV = PromoteIntShiftOp(
SDValue(
N, 0));
2196 if (
unsigned NumOps =
N->getNumOperands()) {
2197 if (
N->getOperand(0).getValueType() == MVT::Other)
2198 return N->getOperand(0);
2199 if (
N->getOperand(
NumOps-1).getValueType() == MVT::Other)
2200 return N->getOperand(
NumOps-1);
2201 for (
unsigned i = 1; i <
NumOps-1; ++i)
2202 if (
N->getOperand(i).getValueType() == MVT::Other)
2203 return N->getOperand(i);
2208SDValue DAGCombiner::visitFCANONICALIZE(SDNode *
N) {
2209 SDValue Operand =
N->getOperand(0);
2221SDValue DAGCombiner::visitGET_ROUNDING(SDNode *
N) {
2227 if (!
Mode ||
Mode->getZExtValue() > 3)
2235SDValue DAGCombiner::visitTokenFactor(SDNode *
N) {
2238 if (
N->getNumOperands() == 2) {
2240 return N->getOperand(0);
2242 return N->getOperand(1);
2252 if (
N->getNumOperands() > Opts.combiner_tokenfactor_inline_limit)
2259 AddToWorklist(*(
N->user_begin()));
2263 SmallPtrSet<SDNode*, 16> SeenOps;
2271 for (
unsigned i = 0; i < TFs.
size(); ++i) {
2275 if (
Ops.size() > Opts.combiner_tokenfactor_inline_limit) {
2276 for (
unsigned j = i;
j < TFs.
size();
j++)
2277 Ops.emplace_back(TFs[j], 0);
2284 SDNode *TF = TFs[i];
2287 switch (
Op.getOpcode()) {
2305 if (SeenOps.
insert(
Op.getNode()).second)
2316 for (
unsigned i = 1, e = TFs.
size(); i < e; i++)
2317 AddToWorklist(TFs[i]);
2327 SmallVector<unsigned, 8> OpWorkCount;
2328 SmallPtrSet<SDNode *, 16> SeenChains;
2329 bool DidPruneOps =
false;
2331 unsigned NumLeftToConsider = 0;
2333 Worklist.
push_back(std::make_pair(
Op.getNode(), NumLeftToConsider++));
2337 auto AddToWorklist = [&](
unsigned CurIdx, SDNode *
Op,
unsigned OpNumber) {
2343 unsigned OrigOpNumber = 0;
2344 while (OrigOpNumber <
Ops.size() &&
Ops[OrigOpNumber].getNode() !=
Op)
2347 "expected to find TokenFactor Operand");
2349 for (
unsigned i = CurIdx + 1; i < Worklist.
size(); ++i) {
2350 if (Worklist[i].second == OrigOpNumber) {
2351 Worklist[i].second = OpNumber;
2354 OpWorkCount[OpNumber] += OpWorkCount[OrigOpNumber];
2355 OpWorkCount[OrigOpNumber] = 0;
2356 NumLeftToConsider--;
2359 if (SeenChains.
insert(
Op).second) {
2360 OpWorkCount[OpNumber]++;
2365 for (
unsigned i = 0; i < Worklist.
size() && i < 1024; ++i) {
2367 if (NumLeftToConsider <= 1)
2369 auto CurNode = Worklist[i].first;
2370 auto CurOpNumber = Worklist[i].second;
2371 assert((OpWorkCount[CurOpNumber] > 0) &&
2372 "Node should not appear in worklist");
2373 switch (CurNode->getOpcode()) {
2379 NumLeftToConsider++;
2382 for (
const SDValue &
Op : CurNode->op_values())
2383 AddToWorklist(i,
Op.getNode(), CurOpNumber);
2389 AddToWorklist(i, CurNode->getOperand(0).getNode(), CurOpNumber);
2393 AddToWorklist(i, MemNode->getChain().getNode(), CurOpNumber);
2396 OpWorkCount[CurOpNumber]--;
2397 if (OpWorkCount[CurOpNumber] == 0)
2398 NumLeftToConsider--;
2412 if (SeenChains.
count(
Op.getNode()) == 0)
2426SDValue DAGCombiner::visitMERGE_VALUES(SDNode *
N) {
2427 WorklistRemover DeadNodes(*
this);
2433 AddUsersToWorklist(
N);
2438 }
while (!
N->use_empty());
2439 deleteAndRecombine(
N);
2447 return Const !=
nullptr && !Const->isOpaque() ? Const :
nullptr;
2457 Op =
N->getOperand(0);
2459 if (
N->getFlags().hasNoUnsignedWrap())
2460 Known.Zero.setBitsFrom(
N.getScalarValueSizeInBits());
2464 if (
N.getValueType().getScalarType() != MVT::i1 ||
2480 if (LD->isIndexed() || LD->getBasePtr().getNode() !=
N)
2482 VT = LD->getMemoryVT();
2483 AS = LD->getAddressSpace();
2485 if (ST->isIndexed() || ST->getBasePtr().getNode() !=
N)
2487 VT = ST->getMemoryVT();
2488 AS = ST->getAddressSpace();
2490 if (LD->isIndexed() || LD->getBasePtr().getNode() !=
N)
2492 VT = LD->getMemoryVT();
2493 AS = LD->getAddressSpace();
2495 if (ST->isIndexed() || ST->getBasePtr().getNode() !=
N)
2497 VT = ST->getMemoryVT();
2498 AS = ST->getAddressSpace();
2504 if (
N->isAnyAdd()) {
2513 }
else if (
N->getOpcode() ==
ISD::SUB) {
2535 bool ShouldCommuteOperands) {
2541 if (ShouldCommuteOperands)
2555 unsigned Opcode =
N->getOpcode();
2556 EVT VT =
N->getValueType(0);
2561 unsigned OpNo = ShouldCommuteOperands ? 0 : 1;
2563 TLI.shouldFoldSelectWithIdentityConstant(Opcode, VT, SelOpcode, N0,
2571 TLI.shouldFoldSelectWithIdentityConstant(Opcode, VT, SelOpcode, N0,
2581SDValue DAGCombiner::foldBinOpIntoSelect(SDNode *BO) {
2584 "Unexpected binary operator");
2596 unsigned SelOpNo = 0;
2633 bool CanFoldNonConst =
2639 if (!CanFoldNonConst &&
2648 if (CanFoldNonConst) {
2667 : DAG.FoldConstantArithmetic(BinOpcode,
DL, VT, {CT, CBO});
2672 : DAG.FoldConstantArithmetic(BinOpcode,
DL, VT, {CF, CBO});
2683 "Expecting add or sub");
2688 bool IsAdd =
N->getOpcode() ==
ISD::ADD;
2689 SDValue C = IsAdd ?
N->getOperand(1) :
N->getOperand(0);
2690 SDValue Z = IsAdd ?
N->getOperand(0) :
N->getOperand(1);
2696 if (Z.getOperand(0).getValueType() != MVT::i1)
2709 EVT VT =
C.getValueType();
2717SDValue DAGCombiner::foldSubToAvg(SDNode *
N,
const SDLoc &
DL) {
2722 if ((!LegalOperations || hasOperation(
ISD::AVGCEILU, VT)) &&
2727 if ((!LegalOperations || hasOperation(
ISD::AVGCEILS, VT)) &&
2738SDValue DAGCombiner::visitPTRADD(SDNode *
N) {
2748 "PTRADD with different operand types is not supported");
2759 !reassociationCanBreakAddressingModePattern(
ISD::PTRADD,
DL,
N, N0, N1)) {
2770 if ((YIsConstant && N0OneUse) || (YIsConstant && ZIsConstant)) {
2775 AddToWorklist(
Add.getNode());
2799 if (
const GlobalAddressSDNode *GA =
2814 AddToWorklist(Inner.
getNode());
2836 SDNodeFlags CommonFlags =
N->getFlags() & N1->
getFlags();
2844 if (ZIsConstant != YIsConstant) {
2848 AddToWorklist(Inner.
getNode());
2858 bool TransformCannotBreakAddrMode =
none_of(
N->users(), [&](SDNode *User) {
2859 return canFoldInAddressingMode(N, User, DAG, TLI);
2862 if (TransformCannotBreakAddrMode)
2874 "Expecting add or sub");
2878 bool IsAdd =
N->getOpcode() ==
ISD::ADD;
2879 SDValue ConstantOp = IsAdd ?
N->getOperand(1) :
N->getOperand(0);
2880 SDValue ShiftOp = IsAdd ?
N->getOperand(0) :
N->getOperand(1);
2902 {ConstantOp, DAG.getConstant(1, DL, VT)})) {
2904 Not.getOperand(0), ShAmt);
2920SDValue DAGCombiner::visitADDLike(SDNode *
N) {
2936 N->getOpcode() ==
ISD::ADD ?
N->getFlags() : SDNodeFlags()))
2949 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
2981 if ((!LegalOperations ||
2984 X.getScalarValueSizeInBits() == 1) {
3000 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
3004 if (!reassociationCanBreakAddressingModePattern(
ISD::ADD,
DL,
N, N0, N1)) {
3016 SDNodeFlags NewFlags =
3106 auto MatchUSUBSAT = [](ConstantSDNode *
Max, ConstantSDNode *
Op) {
3107 return (!Max && !
Op) ||
3108 (
Max &&
Op &&
Max->getAPIntValue() == (-
Op->getAPIntValue()));
3149 !
N->getFlags().hasNoSignedWrap()))) {
3170 (CA * CM + CB->getAPIntValue()).getSExtValue())) {
3174 if (
N->getFlags().hasNoUnsignedWrap() &&
3178 if (
N->getFlags().hasNoSignedWrap() &&
3187 DAG.
getConstant(CA * CM + CB->getAPIntValue(),
DL, VT), Flags);
3195 (CA * CM + CB->getAPIntValue()).getSExtValue())) {
3201 if (
N->getFlags().hasNoUnsignedWrap() &&
3206 if (
N->getFlags().hasNoSignedWrap() &&
3217 DAG.
getConstant(CA * CM + CB->getAPIntValue(),
DL, VT), Flags);
3222 if (
SDValue Combined = visitADDLikeCommutative(N0, N1,
DL))
3225 if (
SDValue Combined = visitADDLikeCommutative(N1, N0,
DL))
3234SDValue DAGCombiner::foldAddToAvg(SDNode *
N,
const SDLoc &
DL) {
3260 if ((!LegalOperations || hasOperation(
ISD::AVGCEILU, VT)) &&
3267 if ((!LegalOperations || hasOperation(
ISD::AVGCEILS, VT)) &&
3278SDValue DAGCombiner::visitADD(SDNode *
N) {
3284 if (
SDValue Combined = visitADDLike(
N))
3293 if (
SDValue V = MatchRotate(N0, N1, SDLoc(
N),
true))
3327 APInt NewStep =
C0 +
C1;
3337 APInt NewStep = SV0 + SV1;
3345SDValue DAGCombiner::visitADDSAT(SDNode *
N) {
3346 unsigned Opcode =
N->getOpcode();
3364 return DAG.
getNode(Opcode,
DL, VT, N1, N0);
3368 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
3388 bool ForceCarryReconstruction =
false) {
3393 if (ForceCarryReconstruction &&
V.getValueType() == MVT::i1)
3397 V =
V.getOperand(0);
3402 if (ForceCarryReconstruction)
3406 V =
V.getOperand(0);
3414 if (
V.getResNo() != 1)
3421 EVT VT =
V->getValueType(0);
3422 if (!
TLI.isOperationLegalOrCustom(
V.getOpcode(), VT))
3429 TLI.getBooleanContents(
V.getValueType()) ==
3528 if (TN->
getVT() == MVT::i1) {
3545 DAG.
getVTList(VT, Carry.getValueType()), N0,
3551SDValue DAGCombiner::visitADDC(SDNode *
N) {
3558 if (!
N->hasAnyUseOfValue(1))
3598 return V.getOperand(0);
3604SDValue DAGCombiner::visitADDO(SDNode *
N) {
3610 EVT CarryVT =
N->getValueType(1);
3614 if (!
N->hasAnyUseOfValue(1))
3626 return DAG.
getNode(
N->getOpcode(),
DL,
N->getVTList(), N1, N0);
3651 if (
SDValue Combined = visitUADDOLike(N0, N1,
N))
3654 if (
SDValue Combined = visitUADDOLike(N1, N0,
N))
3685SDValue DAGCombiner::visitADDE(SDNode *
N) {
3704SDValue DAGCombiner::visitUADDO_CARRY(SDNode *
N) {
3718 if (!LegalOperations ||
3728 AddToWorklist(CarryExt.
getNode());
3734 if (
SDValue Combined = visitUADDO_CARRYLike(N0, N1, CarryIn,
N))
3737 if (
SDValue Combined = visitUADDO_CARRYLike(N1, N0, CarryIn,
N))
3884 EVT CarryOutType =
N->getValueType(0);
3900 unsigned CarryInOperandNum =
3902 if (Opcode ==
ISD::USUBO && CarryInOperandNum != 1)
3954 EVT IntVT =
A.getValueType();
3957 if (IntVT.
isVector() || !
TLI.isOperationLegalOrCustom(
3965 if (
TLI.getBooleanContents(IntVT) !=
4029SDValue DAGCombiner::visitSADDO_CARRY(SDNode *
N) {
4043 if (!LegalOperations ||
4048 if (
SDValue Combined = visitSADDO_CARRYLike(N0, N1, CarryIn,
N))
4051 if (
SDValue Combined = visitSADDO_CARRYLike(N1, N0, CarryIn,
N))
4063 "Illegal truncation");
4087SDValue DAGCombiner::foldSubToUSubSat(EVT DstVT, SDNode *
N,
const SDLoc &
DL) {
4089 !(!LegalOperations || hasOperation(
ISD::USUBSAT, DstVT)))
4092 EVT SubVT =
N->getValueType(0);
4179 if ((
BitWidth - Src.getValueType().getScalarSizeInBits()) != BitWidthDiff)
4189 unsigned AndMaskWidth =
BitWidth - BitWidthDiff;
4190 if (!(AndMask.
isMask(AndMaskWidth) && XorMask.
countr_one() >= AndMaskWidth))
4225 if (
SDValue Res = CheckAndFoldMulCase(Mul0, Mul1))
4228 if (
SDValue Res = CheckAndFoldMulCase(Mul1, Mul0))
4266SDValue DAGCombiner::visitSUB(SDNode *
N) {
4287 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
4316 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
4339 if (
N->getFlags().hasNoUnsignedWrap())
4345 if (
N->getFlags().hasNoSignedWrap())
4374 if (hasOperation(NewOpc, VT) ||
4517 if (!reassociationCanBreakAddressingModePattern(
ISD::SUB,
DL,
N, N0, N1) &&
4555 if ((!LegalOperations || hasOperation(
ISD::ABS, VT)) &&
4565 if (GA->getGlobal() == GB->getGlobal())
4575 if (TN->
getVT() == MVT::i1) {
4640 const APInt &C0Val =
C0->getAPIntValue();
4643 if (
N->getFlags().hasNoUnsignedWrap() && C0Val.
isMask())
4648 if (!
C0->isOpaque()) {
4649 const APInt &MaybeOnes = ~DAG.computeKnownBits(N1).Zero;
4650 if ((C0Val - MaybeOnes) == (C0Val ^ MaybeOnes))
4656 if ((!LegalOperations || hasOperation(
ISD::ABDS, VT)) &&
4662 if ((!LegalOperations || hasOperation(
ISD::ABDS, VT)) &&
4668 if ((!LegalOperations || hasOperation(
ISD::ABDU, VT)) &&
4674 if ((!LegalOperations || hasOperation(
ISD::ABDU, VT)) &&
4682SDValue DAGCombiner::visitSUBSAT(SDNode *
N) {
4683 unsigned Opcode =
N->getOpcode();
4704 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
4730 NarrowBits != 0 && NarrowBits < ScalarBits; NarrowBits *= 2) {
4731 unsigned Scale = ScalarBits / NarrowBits;
4759SDValue DAGCombiner::visitSUBC(SDNode *
N) {
4766 if (!
N->hasAnyUseOfValue(1))
4787SDValue DAGCombiner::visitSUBO(SDNode *
N) {
4793 EVT CarryVT =
N->getValueType(1);
4797 if (!
N->hasAnyUseOfValue(1))
4834SDValue DAGCombiner::visitSUBE(SDNode *
N) {
4846SDValue DAGCombiner::visitUSUBO_CARRY(SDNode *
N) {
4853 if (!LegalOperations ||
4861 !
N->hasAnyUseOfValue(1))
4868SDValue DAGCombiner::visitSSUBO_CARRY(SDNode *
N) {
4875 if (!LegalOperations ||
4885SDValue DAGCombiner::visitMULFIX(SDNode *
N) {
4898 return DAG.
getNode(
N->getOpcode(), SDLoc(
N), VT, N1, N0, Scale);
4907SDValue DAGCombiner::visitMUL(SDNode *
N) {
4930 bool N1IsConst =
false;
4931 bool N1IsOpaqueConst =
false;
4936 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
4941 "Splat APInt should be element width");
4951 if (N1IsConst && ConstValue1.
isZero())
4955 if (N1IsConst && ConstValue1.
isOne())
4958 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
4962 if (N1IsConst && ConstValue1.
isAllOnes())
4968 if (
SDValue LogBase2 = BuildLogBase2(N1,
DL)) {
4972 Flags.setNoUnsignedWrap(
N->getFlags().hasNoUnsignedWrap());
4975 if (
N->getFlags().hasNoSignedWrap() && N1IsConst &&
4977 Flags.setNoSignedWrap(
true);
4984 unsigned Log2Val = (-ConstValue1).logBase2();
4998 SDVTList LoHiVT = DAG.
getVTList(VT, VT);
5001 if (LoHi->hasAnyUseOfValue(1))
5004 if (LoHi->hasAnyUseOfValue(1))
5029 APInt MulC = ConstValue1.
abs();
5031 unsigned TZeros = MulC == 2 ? 0 : MulC.
countr_zero();
5033 if ((MulC - 1).isPowerOf2())
5035 else if ((MulC + 1).isPowerOf2())
5040 MathOp ==
ISD::ADD ? (MulC - 1).logBase2() : (MulC + 1).logBase2();
5043 "multiply-by-constant generated out of bounds shift");
5092 if (!
C0.isPowerOf2() ||
C1.isPowerOf2() ||
5102 APInt NewStep =
C0 * MulVal;
5108 if ((!LegalOperations || hasOperation(
ISD::ABS, VT)) &&
5121 SmallBitVector ClearMask;
5123 auto IsClearMask = [&ClearMask](ConstantSDNode *
V) {
5124 if (!
V ||
V->isZero()) {
5138 for (
unsigned I = 0;
I != NumElts; ++
I)
5168 switch (
NodeType.getSimpleVT().SimpleTy) {
5169 default:
return false;
5170 case MVT::i8: LC=
isSigned ? RTLIB::SDIVREM_I8 : RTLIB::UDIVREM_I8;
break;
5171 case MVT::i16: LC=
isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16;
break;
5172 case MVT::i32: LC=
isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32;
break;
5173 case MVT::i64: LC=
isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64;
break;
5174 case MVT::i128: LC=
isSigned ? RTLIB::SDIVREM_I128:RTLIB::UDIVREM_I128;
break;
5181SDValue DAGCombiner::useDivRem(SDNode *Node) {
5182 if (
Node->use_empty())
5185 unsigned Opcode =
Node->getOpcode();
5190 EVT VT =
Node->getValueType(0);
5204 unsigned OtherOpcode = 0;
5218 for (SDNode *User : Op0->
users()) {
5225 unsigned UserOpc =
User->getOpcode();
5226 if ((UserOpc == Opcode || UserOpc == OtherOpcode || UserOpc == DivRemOpc) &&
5227 User->getOperand(0) == Op0 &&
5228 User->getOperand(1) == Op1) {
5230 if (UserOpc == OtherOpcode) {
5232 combined = DAG.
getNode(DivRemOpc, SDLoc(Node), VTs, Op0, Op1);
5233 }
else if (UserOpc == DivRemOpc) {
5236 assert(UserOpc == Opcode);
5241 CombineTo(User, combined);
5243 CombineTo(User, combined.
getValue(1));
5252 EVT VT =
N->getValueType(0);
5255 unsigned Opc =
N->getOpcode();
5274 if (N0C && N0C->
isZero())
5294SDValue DAGCombiner::visitSDIV(SDNode *
N) {
5297 EVT VT =
N->getValueType(0);
5308 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5325 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
5333 if (
SDValue V = visitSDIVLike(N0, N1,
N)) {
5340 if (!
N->getFlags().hasExact()) {
5343 AddToWorklist(
Mul.getNode());
5344 AddToWorklist(
Sub.getNode());
5345 CombineTo(RemNode,
Sub);
5366 if (
C->isZero() ||
C->isOpaque())
5368 if (
C->getAPIntValue().isPowerOf2())
5370 if (
C->getAPIntValue().isNegatedPowerOf2())
5381 EVT VT =
N->getValueType(0);
5392 if ((!
N->getFlags().hasExact() ||
BitWidth > MaxLegalDivRemBitWidth) &&
5410 AddToWorklist(
Sign.getNode());
5416 AddToWorklist(
Add.getNode());
5427 Sra = DAG.
getSelect(
DL, VT, IsOneOrAllOnes, N0, Sra);
5453SDValue DAGCombiner::visitUDIV(SDNode *
N) {
5456 EVT VT =
N->getValueType(0);
5467 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5481 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
5484 if (
SDValue V = visitUDIVLike(N0, N1,
N)) {
5491 if (!
N->getFlags().hasExact()) {
5494 AddToWorklist(
Mul.getNode());
5495 AddToWorklist(
Sub.getNode());
5496 CombineTo(RemNode,
Sub);
5521 EVT VT =
N->getValueType(0);
5526 if (
SDValue LogBase2 = BuildLogBase2(N1,
DL)) {
5527 AddToWorklist(LogBase2.getNode());
5531 AddToWorklist(Trunc.
getNode());
5541 if (
SDValue LogBase2 = BuildLogBase2(N10,
DL)) {
5542 AddToWorklist(LogBase2.getNode());
5546 AddToWorklist(Trunc.
getNode());
5548 AddToWorklist(
Add.getNode());
5576SDValue DAGCombiner::visitREM(SDNode *
N) {
5577 unsigned Opcode =
N->getOpcode();
5580 EVT VT =
N->getValueType(0);
5603 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
5616 AddToWorklist(
Add.getNode());
5633 if (
SDValue OptimizedRem = buildOptimizedSREM(N0, N1,
N))
5634 return OptimizedRem;
5638 isSigned ? visitSDIVLike(N0, N1,
N) : visitUDIVLike(N0, N1,
N);
5641 if (SDNode *DivNode = DAG.getNodeIfExists(DivOpcode, N->getVTList(),
5643 CombineTo(DivNode, OptimizedDiv);
5646 AddToWorklist(OptimizedDiv.
getNode());
5647 AddToWorklist(
Mul.getNode());
5670 return DivRem.getValue(1);
5693SDValue DAGCombiner::visitMULHS(SDNode *
N) {
5696 EVT VT =
N->getValueType(0);
5709 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5752SDValue DAGCombiner::visitMULHU(SDNode *
N) {
5755 EVT VT =
N->getValueType(0);
5768 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5792 (!LegalOperations || hasOperation(
ISD::SRL, VT))) {
5793 if (
SDValue LogBase2 = BuildLogBase2(N1,
DL)) {
5808 unsigned SimpleSize =
Simple.getSizeInBits();
5829SDValue DAGCombiner::visitAVGSUB(SDNode *
N) {
5830 unsigned Opcode =
N->getOpcode();
5833 EVT VT =
N->getValueType(0);
5841 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5857SDValue DAGCombiner::visitAVG(SDNode *
N) {
5858 unsigned Opcode =
N->getOpcode();
5861 EVT VT =
N->getValueType(0);
5872 return DAG.
getNode(Opcode,
DL,
N->getVTList(), N1, N0);
5875 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5901 X.getValueType() ==
Y.getValueType() &&
5902 hasOperation(Opcode,
X.getValueType())) {
5908 X.getValueType() ==
Y.getValueType() &&
5909 hasOperation(Opcode,
X.getValueType())) {
5943 (
Add->getFlags().hasNoSignedWrap() ||
5945 Add->getOperand(1))))
5949 if (!IsSigned &&
Add->getFlags().hasNoUnsignedWrap())
5963SDValue DAGCombiner::visitABD(SDNode *
N) {
5964 unsigned Opcode =
N->getOpcode();
5967 EVT VT =
N->getValueType(0);
5977 return DAG.
getNode(Opcode,
DL,
N->getVTList(), N1, N0);
5980 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5995 (!LegalOperations || hasOperation(
ISD::ABS, VT)))
6018 EVT SmallVT =
X.getScalarValueSizeInBits() >
Y.getScalarValueSizeInBits()
6021 if (!LegalOperations || hasOperation(Opcode, SmallVT)) {
6033 EVT SmallVT =
X.getValueType();
6034 if (!LegalOperations || hasOperation(Opcode, SmallVT)) {
6036 unsigned RelevantBits =
6045 const APInt &YConst =
C->getAsAPIntVal();
6052 if (RelevantBits <= Bits && TruncatingYIsCheap) {
6066SDValue DAGCombiner::SimplifyNodeWithTwoResults(SDNode *
N,
unsigned LoOp,
6069 bool HiExists =
N->hasAnyUseOfValue(1);
6070 if (!HiExists && (!LegalOperations ||
6073 return CombineTo(
N, Res, Res);
6077 bool LoExists =
N->hasAnyUseOfValue(0);
6078 if (!LoExists && (!LegalOperations ||
6081 return CombineTo(
N, Res, Res);
6085 if (LoExists && HiExists)
6091 AddToWorklist(
Lo.getNode());
6094 (!LegalOperations ||
6096 return CombineTo(
N, LoOpt, LoOpt);
6101 AddToWorklist(
Hi.getNode());
6104 (!LegalOperations ||
6106 return CombineTo(
N, HiOpt, HiOpt);
6112SDValue DAGCombiner::visitSMUL_LOHI(SDNode *
N) {
6118 EVT VT =
N->getValueType(0);
6135 unsigned SimpleSize =
Simple.getSizeInBits();
6147 return CombineTo(
N,
Lo,
Hi);
6154SDValue DAGCombiner::visitUMUL_LOHI(SDNode *
N) {
6160 EVT VT =
N->getValueType(0);
6182 return CombineTo(
N, N0,
Zero);
6189 unsigned SimpleSize =
Simple.getSizeInBits();
6201 return CombineTo(
N,
Lo,
Hi);
6208SDValue DAGCombiner::visitMULO(SDNode *
N) {
6214 EVT CarryVT =
N->getValueType(1);
6227 return DAG.
getNode(
N->getOpcode(),
DL,
N->getVTList(), N1, N0);
6239 N->getVTList(), N0, N0);
6246 return CombineTo(
N,
And, Cmp);
6284 unsigned Opcode0 = isSignedMinMax(N0, N1, N2, N3,
CC);
6338 unsigned Opcode1 = isSignedMinMax(N00, N01, N02, N03, N0CC);
6339 if (!Opcode1 || Opcode0 == Opcode1)
6349 APInt MinCPlus1 = MinC + 1;
6350 if (-MaxC == MinCPlus1 && MinCPlus1.
isPowerOf2()) {
6356 if (MaxC == 0 && MinC != 0 && MinCPlus1.
isPowerOf2()) {
6405 unsigned BW = (
C1 + 1).exactLogBase2();
6427 EVT VT =
N->getValueType(0);
6460 X.getValueType(), VT))
6474SDValue DAGCombiner::visitIMINMAX(SDNode *
N) {
6478 unsigned Opcode =
N->getOpcode();
6492 return DAG.
getNode(Opcode,
DL, VT, N1, N0);
6496 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
6500 if (
SDValue RMINMAX = reassociateOps(Opcode,
DL, N0, N1,
N->getFlags()))
6545 if (IsSatBroken || IsOpIllegal) {
6547 if (
A.isUndef() ||
B.isUndef())
6560 if (HasKnownSameSign(N0, N1)) {
6563 return DAG.
getNode(AltOpcode,
DL, VT, N0, N1);
6576 auto ReductionOpcode = [](
unsigned Opcode) {
6590 if (
SDValue SD = reassociateReduction(ReductionOpcode(Opcode), Opcode,
6591 SDLoc(
N), VT, N0, N1))
6599 return C0 >
C1 ? N0 : N1;
6601 return C0 >
C1 ? N1 : N0;
6610 const APInt &C1V =
C1->getAPIntValue();
6629SDValue DAGCombiner::hoistLogicOpWithSameOpcodeHands(SDNode *
N) {
6632 unsigned LogicOpcode =
N->getOpcode();
6657 if (XVT !=
Y.getValueType())
6661 if ((VT.
isVector() || LegalOperations) &&
6671 SDNodeFlags LogicFlags;
6677 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6687 if (XVT !=
Y.getValueType())
6699 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6720 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6735 return DAG.
getNode(HandOpcode,
DL, VT, Logic0, Logic1, S);
6748 if (XVT.
isInteger() && XVT ==
Y.getValueType() &&
6752 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6771 assert(
X.getValueType() ==
Y.getValueType() &&
6772 "Inputs to shuffles are not the same type");
6778 if (!SVN0->hasOneUse() || !SVN1->hasOneUse() ||
6779 !SVN0->getMask().equals(SVN1->getMask()))
6815 SDValue LL, LR, RL, RR, N0CC, N1CC;
6816 if (!isSetCCEquivalent(N0, LL, LR, N0CC) ||
6817 !isSetCCEquivalent(N1, RL, RR, N1CC))
6821 "Unexpected operand types for bitwise logic op");
6824 "Unexpected operand types for setcc");
6840 if (LR == RR && CC0 == CC1 && IsInteger) {
6845 bool AndEqZero = IsAnd && CC1 ==
ISD::SETEQ && IsZero;
6847 bool AndGtNeg1 = IsAnd && CC1 ==
ISD::SETGT && IsNeg1;
6849 bool OrNeZero = !IsAnd && CC1 ==
ISD::SETNE && IsZero;
6851 bool OrLtZero = !IsAnd && CC1 ==
ISD::SETLT && IsZero;
6857 if (AndEqZero || AndGtNeg1 || OrNeZero || OrLtZero) {
6859 AddToWorklist(
Or.getNode());
6864 bool AndEqNeg1 = IsAnd && CC1 ==
ISD::SETEQ && IsNeg1;
6866 bool AndLtZero = IsAnd && CC1 ==
ISD::SETLT && IsZero;
6868 bool OrNeNeg1 = !IsAnd && CC1 ==
ISD::SETNE && IsNeg1;
6870 bool OrGtNeg1 = !IsAnd && CC1 ==
ISD::SETGT && IsNeg1;
6876 if (AndEqNeg1 || AndLtZero || OrNeNeg1 || OrGtNeg1) {
6878 AddToWorklist(
And.getNode());
6912 AddToWorklist(
Add.getNode());
6933 auto MatchDiffPow2 = [&](ConstantSDNode *
C0, ConstantSDNode *
C1) {
6939 return !
C0->isOpaque() && !
C1->isOpaque() && (CMax - CMin).isPowerOf2();
6957 if (LL == RR && LR == RL) {
6964 if (LL == RL && LR == RR) {
6968 (!LegalOperations ||
6993 if (
TLI.isOperationLegalOrCustom(IEEEOp, VT) &&
6997 if (
TLI.isOperationLegalOrCustom(PreferredOp, VT))
7004 unsigned OrAndOpcode,
SelectionDAG &DAG,
bool isFMAXNUMFMINNUM_IEEE,
7005 bool isFMAXNUMFMINNUM,
bool isFMAXIMUMNUMFMINIMUMNUM,
7006 bool isPSEUDOFMAXFMIN) {
7051 if (isFMAXIMUMNUMFMINIMUMNUM)
7055 if (isFMAXNUMFMINNUM)
7057 if (isFMAXNUMFMINNUM_IEEE)
7065 (LogicOp->getOpcode() ==
ISD::AND || LogicOp->getOpcode() ==
ISD::OR) &&
7066 "Invalid Op to combine SETCC with");
7072 !
LHS->hasOneUse() || !
RHS->hasOneUse())
7079 LogicOp,
LHS.getNode(),
RHS.getNode());
7091 EVT VT = LogicOp->getValueType(0);
7107 bool isFMAXNUMFMINNUM =
TLI.isOperationLegalOrCustom(
ISD::FMAXNUM, OpVT) &&
7110 bool isFMAXIMUMNUMFMINIMUMNUM =
7113 TLI.isProfitableToCombineMinNumMaxNum(OpVT);
7114 bool isPSEUDOFMAXFMIN =
7122 (isFMAXNUMFMINNUM_IEEE || isFMAXNUMFMINNUM ||
7123 isFMAXIMUMNUMFMINIMUMNUM || isPSEUDOFMAXFMIN))) &&
7129 SDValue CommonValue, Operand1, Operand2;
7137 }
else if (LHS1 == RHS1) {
7150 }
else if (RHS0 == LHS1) {
7167 bool IsSigned = isSignedIntSetCC(
CC);
7171 bool IsOr = (LogicOp->getOpcode() ==
ISD::OR);
7185 LogicOp->getOpcode(), DAG, isFMAXNUMFMINNUM_IEEE, isFMAXNUMFMINNUM,
7186 isFMAXIMUMNUMFMINIMUMNUM, isPSEUDOFMAXFMIN);
7193 DAG.
getNode(NewOpcode,
DL, OpVT, Operand1, Operand2, Flags);
7194 return DAG.
getSetCC(
DL, VT, MinMaxValue, CommonValue,
CC, {},
7200 if (LHS0 == LHS1 && RHS0 == RHS1 && CCL == CCR &&
7204 return DAG.
getSetCC(
DL, VT, LHS0, RHS0, CCL);
7211 LHS0 == RHS0 && LHS1C && RHS1C && OpVT.
isInteger()) {
7212 const APInt &APLhs = LHS1C->getAPIntValue();
7213 const APInt &APRhs = RHS1C->getAPIntValue();
7217 if (APLhs == (-APRhs) &&
7228 }
else if (TargetPreference &
7249 APInt Dif = MaxC - MinC;
7283 EVT CondVT =
Cond.getValueType();
7284 if (
TLI.getBooleanContents(CondVT) !=
7294 EVT OpVT =
T.getValueType();
7313 if (
SDValue V = foldLogicOfSetCCs(
true, N0, N1,
DL))
7330 APInt
ADDC = ADDI->getAPIntValue();
7331 APInt SRLC = SRLI->getAPIntValue();
7343 CombineTo(N0.
getNode(), NewAdd);
7356bool DAGCombiner::isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
7357 EVT LoadResultTy, EVT &ExtVT) {
7366 if (ExtVT == LoadedVT &&
7367 (!LegalOperations ||
7384 if (LegalOperations &&
7395bool DAGCombiner::isLegalNarrowLdSt(LSBaseSDNode *LDST,
7404 const unsigned ByteShAmt = ShAmt / 8;
7423 if (LdStMemVT.
bitsLT(MemVT))
7438 if (PtrType == MVT::Untyped || PtrType.
isExtended())
7448 if (LegalOperations &&
7450 Load->getAddressSpace(), ExtType,
false))
7458 if (
Load->getNumValues() > 2)
7477 if (LegalOperations &&
7479 Store->getAlign(),
Store->getAddressSpace()))
7485bool DAGCombiner::SearchForAndLoads(SDNode *
N,
7486 SmallVectorImpl<LoadSDNode*> &Loads,
7487 SmallPtrSetImpl<SDNode*> &NodesWithConsts,
7488 ConstantSDNode *Mask,
7489 SDNode *&NodeToMask) {
7493 if (
Op.getValueType().isVector())
7499 "Expected bitwise logic operation");
7500 if (!
C->getAPIntValue().isSubsetOf(
Mask->getAPIntValue()))
7505 if (!
Op.hasOneUse())
7508 switch(
Op.getOpcode()) {
7512 if (isAndLoadExtLoad(Mask,
Load,
Load->getValueType(0), ExtVT) &&
7530 unsigned ActiveBits =
Mask->getAPIntValue().countr_one();
7534 Op.getOperand(0).getValueType();
7545 if (!SearchForAndLoads(
Op.getNode(), Loads, NodesWithConsts, Mask,
7556 NodeToMask =
Op.getNode();
7559 for (
unsigned i = 0, e = NodeToMask->
getNumValues(); i < e; ++i) {
7560 MVT VT =
SDValue(NodeToMask, i).getSimpleValueType();
7561 if (VT != MVT::Glue && VT != MVT::Other) {
7563 NodeToMask =
nullptr;
7575bool DAGCombiner::BackwardsPropagateMask(SDNode *
N) {
7580 if (!
Mask->getAPIntValue().isMask())
7588 SmallPtrSet<SDNode*, 2> NodesWithConsts;
7589 SDNode *FixupNode =
nullptr;
7590 if (SearchForAndLoads(
N, Loads, NodesWithConsts, Mask, FixupNode)) {
7603 SDValue(FixupNode, 0), MaskOp);
7605 if (
And.getOpcode() == ISD ::AND)
7610 for (
auto *LogicN : NodesWithConsts) {
7616 if (LogicN->getOpcode() ==
ISD::AND &&
7635 for (
auto *
Load : Loads) {
7640 if (
And.getOpcode() == ISD ::AND)
7643 SDValue NewLoad = reduceLoadWidth(
And.getNode());
7645 "Shouldn't be masking the load if it can't be narrowed");
7659SDValue DAGCombiner::unfoldExtremeBitClearingToShifts(SDNode *
N) {
7670 unsigned OuterShift;
7671 unsigned InnerShift;
7673 auto matchMask = [&OuterShift, &InnerShift, &
Y](
SDValue M) ->
bool {
7676 OuterShift =
M->getOpcode();
7685 Y =
M->getOperand(1);
7692 else if (matchMask(N0))
7698 EVT VT =
N->getValueType(0);
7715 SDValue And0 =
And->getOperand(0), And1 =
And->getOperand(1);
7725 bool FoundNot =
false;
7728 Src = Src.getOperand(0);
7734 Src = Src.getOperand(0);
7738 if (Src.getOpcode() !=
ISD::SRL || !Src.hasOneUse())
7742 EVT SrcVT = Src.getValueType();
7744 if (!
TLI.isTypeLegal(SrcVT))
7751 if (!ShiftAmtC || !ShiftAmtC->getAPIntValue().ult(
BitWidth))
7755 Src = Src.getOperand(0);
7762 Src = Src.getOperand(0);
7765 if (!
TLI.hasBitTest(Src, ShiftAmt))
7786 EVT VT =
N->getValueType(0);
7812 unsigned LogicOpcode =
N->getOpcode();
7814 "Expected bitwise logic operation");
7816 if (!LogicOp.hasOneUse() || !ShiftOp.
hasOneUse())
7820 unsigned ShiftOpcode = ShiftOp.
getOpcode();
7821 if (LogicOp.getOpcode() != LogicOpcode ||
7833 if (LogicOp.getOperand(0).getOpcode() == ShiftOpcode &&
7834 LogicOp.getOperand(0).getOperand(1) ==
Y) {
7836 Z = LogicOp.getOperand(1);
7837 }
else if (LogicOp.getOperand(1).getOpcode() == ShiftOpcode &&
7838 LogicOp.getOperand(1).getOperand(1) ==
Y) {
7840 Z = LogicOp.getOperand(0);
7845 EVT VT =
N->getValueType(0);
7849 return DAG.
getNode(LogicOpcode,
DL, VT, NewShift, Z);
7860 unsigned LogicOpcode =
N->getOpcode();
7862 "Expected bitwise logic operation");
7863 if (LeftHand.
getOpcode() != LogicOpcode ||
7884 EVT VT =
N->getValueType(0);
7886 return DAG.
getNode(LogicOpcode,
DL, VT, CombinedShifts, W);
7898 "Must be called with ISD::OR or ISD::AND node");
7912 EVT VT = M.getValueType();
7920SDValue DAGCombiner::visitAND(SDNode *
N) {
7944 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
7961 if (BV0 && BV1 && !BV0->getSplatValue() && !BV1->getSplatValue() &&
7963 BV0->getOperand(0).getValueType() ==
7964 BV1->getOperand(0).getValueType()) {
7967 EVT EltVT = BV0->getOperand(0).getValueType();
7968 for (
unsigned I = 0;
I != NumElts; ++
I) {
7973 C0->getAPIntValue() &
C1->getAPIntValue(),
DL, EltVT));
7974 else if (
C0 &&
C0->isZero())
7976 else if (
C1 &&
C1->isZero())
7978 else if (
C0 &&
C0->isAllOnes())
7980 else if (
C1 &&
C1->isAllOnes())
7982 else if (BV0->getOperand(
I) == BV1->getOperand(
I))
7987 if (MergedOps.
size() == NumElts)
7996 EVT MemVT =
MLoad->getMemoryVT();
8007 MLoad->isExpandingLoad());
8008 CombineTo(
N, Frozen ? N0 : NewLoad);
8009 CombineTo(MLoad, NewLoad, NewLoad.
getValue(1));
8029 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
8042 auto MatchSubset = [](ConstantSDNode *
LHS, ConstantSDNode *
RHS) {
8043 return RHS->getAPIntValue().isSubsetOf(
LHS->getAPIntValue());
8053 APInt
Mask = ~N1C->getAPIntValue();
8079 {N0Op0.getOperand(1)})) {
8112 unsigned EltBitWidth =
Vector->getValueType(0).getScalarSizeInBits();
8113 APInt SplatValue, SplatUndef;
8114 unsigned SplatBitSize;
8121 const bool IsBigEndian =
false;
8123 Vector->isConstantSplat(SplatValue, SplatUndef, SplatBitSize,
8124 HasAnyUndefs, EltBitWidth, IsBigEndian);
8128 if (IsSplat && (SplatBitSize % EltBitWidth) == 0) {
8131 SplatValue |= SplatUndef;
8138 for (
unsigned i = 0, n = (SplatBitSize / EltBitWidth); i < n; ++i)
8139 Constant &= SplatValue.
extractBits(EltBitWidth, i * EltBitWidth);
8147 Load->getValueType(0),
Load->getMemoryVT(),
Load->getAlign(),
8156 switch (
Load->getExtensionType()) {
8157 default:
B =
false;
break;
8173 Load->getValueType(0), SDLoc(
Load),
8174 Load->getChain(),
Load->getBasePtr(),
8175 Load->getOffset(),
Load->getMemoryVT(),
8176 Load->getMemOperand());
8178 if (
Load->getNumValues() == 3) {
8180 SDValue To[] = { NewLoad.getValue(0), NewLoad.getValue(1),
8181 NewLoad.getValue(2) };
8182 CombineTo(
Load, To, 3,
true);
8184 CombineTo(
Load, NewLoad.getValue(0), NewLoad.getValue(1));
8194 if (
SDValue Shuffle = XformToShuffleWithZero(
N))
8221 EVT MemVT = GN0->getMemoryVT();
8224 if (
SDValue(GN0, 0).hasOneUse() &&
8227 SDValue Ops[] = {GN0->getChain(), GN0->getPassThru(), GN0->getMask(),
8228 GN0->getBasePtr(), GN0->getIndex(), GN0->getScale()};
8231 DAG.
getVTList(VT, MVT::Other), MemVT,
DL,
Ops, GN0->getMemOperand(),
8234 CombineTo(
N, ZExtLoad);
8235 AddToWorklist(ZExtLoad.
getNode());
8248 if (
SDValue Res = reduceLoadWidth(
N))
8257 if (BackwardsPropagateMask(
N))
8261 if (
SDValue Combined = visitANDLike(N0, N1,
N))
8266 if (
SDValue V = hoistLogicOpWithSameOpcodeHands(
N))
8319 X.getOperand(0).getScalarValueSizeInBits() == 1)
8322 X.getOperand(0).getScalarValueSizeInBits() == 1)
8337 EVT MemVT = LN0->getMemoryVT();
8344 ((!LegalOperations && LN0->isSimple()) ||
8345 TLI.
isLoadLegal(VT, MemVT, LN0->getAlign(), LN0->getAddressSpace(),
8349 LN0->getBasePtr(), MemVT, LN0->getMemOperand());
8363 if (
SDValue Shifts = unfoldExtremeBitClearingToShifts(
N))
8383 if (!
C->getAPIntValue().isMask(
8384 LHS.getOperand(0).getValueType().getScalarSizeInBits()))
8391 if (IsAndZeroExtMask(N0, N1) &&
8401 if (LegalOperations || VT.
isVector())
8414 bool DemandHighBits) {
8415 if (!LegalOperations)
8418 EVT VT =
N->getValueType(0);
8419 if (VT != MVT::i64 && VT != MVT::i32 && VT != MVT::i16)
8425 bool LookPassAnd0 =
false;
8426 bool LookPassAnd1 =
false;
8441 LookPassAnd0 =
true;
8451 LookPassAnd1 =
true;
8477 LookPassAnd0 =
true;
8491 LookPassAnd1 =
true;
8500 if (OpSizeInBits > 16) {
8504 if (DemandHighBits && !LookPassAnd0)
8511 if (!LookPassAnd1) {
8512 unsigned HighBit = DemandHighBits ? OpSizeInBits : 24;
8520 if (OpSizeInBits > 16) {
8535 if (!
N->hasOneUse())
8538 unsigned Opc =
N.getOpcode();
8556 unsigned MaskByteOffset;
8560 case 0xFF: MaskByteOffset = 0;
break;
8561 case 0xFF00: MaskByteOffset = 1;
break;
8570 case 0xFF0000: MaskByteOffset = 2;
break;
8571 case 0xFF000000: MaskByteOffset = 3;
break;
8576 if (MaskByteOffset == 0 || MaskByteOffset == 2) {
8582 if (!
C ||
C->getZExtValue() != 8)
8590 if (!
C ||
C->getZExtValue() != 8)
8596 if (MaskByteOffset != 0 && MaskByteOffset != 2)
8599 if (!
C ||
C->getZExtValue() != 8)
8604 if (MaskByteOffset != 1 && MaskByteOffset != 3)
8607 if (!
C ||
C->getZExtValue() != 8)
8611 if (Parts[MaskByteOffset])
8626 if (!
C ||
C->getAPIntValue() != 16)
8628 Parts[0] = Parts[1] =
N.getOperand(0).getOperand(0).getNode();
8643 "MatchBSwapHWordOrAndAnd: expecting i32");
8653 if (!Mask0 || !Mask1)
8664 if (!ShiftAmt0 || !ShiftAmt1)
8684 if (!LegalOperations)
8687 EVT VT =
N->getValueType(0);
8705 SDNode *Parts[4] = {};
8725 if (Parts[0] != Parts[1] || Parts[0] != Parts[2] || Parts[0] != Parts[3])
8753 if (
SDValue V = foldLogicOfSetCCs(
false, N0, N1,
DL))
8762 if (
const ConstantSDNode *N0O1C =
8764 if (
const ConstantSDNode *N1O1C =
8768 const APInt &LHSMask = N0O1C->getAPIntValue();
8769 const APInt &RHSMask = N1O1C->getAPIntValue();
8803 auto peekThroughResize = [](
SDValue V) {
8805 return V->getOperand(0);
8809 SDValue N0Resized = peekThroughResize(N0);
8811 SDValue N1Resized = peekThroughResize(N1);
8816 if (N00 == N1Resized || N01 == N1Resized)
8823 if (peekThroughResize(NotOperand) == N1Resized)
8831 if (peekThroughResize(NotOperand) == N1Resized)
8857 auto peekThroughZext = [](
SDValue V) {
8859 return V->getOperand(0);
8899 if (S0 &&
S1 && S0->getZExtValue() < BW &&
S1->getZExtValue() < BW &&
8900 S0->getZExtValue() == (BW -
S1->getZExtValue())) {
8917 Lo.getScalarValueSizeInBits() == (BW / 2) &&
8918 Lo.getValueType() ==
Hi.getValueType()) {
8934SDValue DAGCombiner::visitOR(SDNode *
N) {
8956 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
8972 if (BV0 && BV1 && !BV0->getSplatValue() && !BV1->getSplatValue() &&
8974 BV0->getOperand(0).getValueType() ==
8975 BV1->getOperand(0).getValueType()) {
8978 EVT EltVT = BV0->getOperand(0).getValueType();
8979 for (
unsigned I = 0;
I != NumElts; ++
I) {
8984 C0->getAPIntValue() |
C1->getAPIntValue(),
DL, EltVT));
8985 else if (
C0 &&
C0->isZero())
8987 else if (
C1 &&
C1->isZero())
8989 else if (
C0 &&
C0->isAllOnes())
8991 else if (
C1 &&
C1->isAllOnes())
8993 else if (BV0->getOperand(
I) == BV1->getOperand(
I))
8998 if (MergedOps.
size() == NumElts)
9012 if ((ZeroN00 != ZeroN01) && (ZeroN10 != ZeroN11)) {
9013 assert((!ZeroN00 || !ZeroN01) &&
"Both inputs zero!");
9014 assert((!ZeroN10 || !ZeroN11) &&
"Both inputs zero!");
9015 bool CanFold =
true;
9017 SmallVector<int, 4>
Mask(NumElts, -1);
9019 for (
int i = 0; i != NumElts; ++i) {
9020 int M0 = SV0->getMaskElt(i);
9021 int M1 = SV1->getMaskElt(i);
9024 bool M0Zero =
M0 < 0 || (ZeroN00 == (
M0 < NumElts));
9025 bool M1Zero =
M1 < 0 || (ZeroN10 == (
M1 < NumElts));
9029 if ((M0Zero &&
M1 < 0) || (M1Zero &&
M0 < 0))
9033 if (M0Zero == M1Zero) {
9038 assert((
M0 >= 0 ||
M1 >= 0) &&
"Undef index!");
9044 Mask[i] = M1Zero ?
M0 % NumElts : (
M1 % NumElts) + NumElts;
9053 return LegalShuffle;
9067 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
9078 if (
SDValue Combined = visitORLike(N0, N1,
DL))
9088 if (
SDValue BSwap = MatchBSwapHWord(
N, N0, N1))
9090 if (
SDValue BSwap = MatchBSwapHWordLow(
N, N0, N1))
9104 auto MatchIntersect = [](ConstantSDNode *
C1, ConstantSDNode *C2) {
9105 return !
C1 || !C2 ||
C1->getAPIntValue().intersects(C2->getAPIntValue());
9124 if (
SDValue V = hoistLogicOpWithSameOpcodeHands(
N))
9128 if (
SDValue Rot = MatchRotate(N0, N1,
DL,
false))
9141 if (
SDValue Combined = visitADDLike(
N))
9146 if (LegalOperations || VT.
isVector())
9161 Mask =
Op.getOperand(1);
9162 return Op.getOperand(0);
9205 assert(OppShift && ExtractFrom &&
"Empty SDValue");
9233 bool IsMulOrDiv =
false;
9236 auto SelectOpcode = [&](
unsigned NeededShift,
unsigned MulOrDivVariant) {
9237 IsMulOrDiv = ExtractFrom.
getOpcode() == MulOrDivVariant;
9238 if (!IsMulOrDiv && ExtractFrom.
getOpcode() != NeededShift)
9240 Opcode = NeededShift;
9290 if (Rem != 0 || ResultAmt != OppLHSAmt)
9296 if (OppLHSAmt != ExtractFromAmt - NeededShiftAmt.
zextOrTrunc(
9305 return DAG.
getNode(Opcode,
DL, ResVT, OppShiftLHS, NewShiftNode);
9359 unsigned MaskLoBits = 0;
9361 unsigned Bits =
Log2_64(EltSize);
9363 if (NegBits >= Bits) {
9386 if (PosBits >= MaskLoBits) {
9408 if ((Pos == NegOp1) ||
9432 return Width.
getLoBits(MaskLoBits) == 0;
9433 return Width == EltSize;
9443 SDValue InnerNeg,
bool FromAdd,
9444 bool HasPos,
unsigned PosOpcode,
9445 unsigned NegOpcode,
const SDLoc &
DL) {
9456 return DAG.
getNode(HasPos ? PosOpcode : NegOpcode,
DL, VT, Shifted,
9457 HasPos ? Pos : Neg);
9470 SDValue InnerNeg,
bool FromAdd,
9471 bool HasPos,
unsigned PosOpcode,
9472 unsigned NegOpcode,
const SDLoc &
DL) {
9485 return DAG.
getNode(HasPos ? PosOpcode : NegOpcode,
DL, VT, N0, N1,
9486 HasPos ? Pos : Neg);
9531 EVT VT =
LHS.getValueType();
9536 bool HasROTL = hasOperation(
ISD::ROTL, VT);
9537 bool HasROTR = hasOperation(
ISD::ROTR, VT);
9538 bool HasFSHL = hasOperation(
ISD::FSHL, VT);
9539 bool HasFSHR = hasOperation(
ISD::FSHR, VT);
9550 if (LegalOperations && !HasROTL && !HasROTR && !HasFSHL && !HasFSHR)
9555 LHS.getOperand(0).getValueType() ==
RHS.getOperand(0).getValueType()) {
9558 MatchRotate(
LHS.getOperand(0),
RHS.getOperand(0),
DL, FromAdd))
9572 if (!LHSShift && !RHSShift)
9587 RHSShift = NewRHSShift;
9592 LHSShift = NewLHSShift;
9595 if (!RHSShift || !LHSShift)
9620 auto MatchRotateSum = [EltSizeInBits](ConstantSDNode *
LHS,
9621 ConstantSDNode *
RHS) {
9622 return (
LHS->getAPIntValue() +
RHS->getAPIntValue()) == EltSizeInBits;
9625 auto ApplyMasks = [&](
SDValue Res) {
9649 bool IsRotate = LHSShiftArg == RHSShiftArg;
9650 if (!IsRotate && !(HasFSHL || HasFSHR)) {
9659 if (CommonOp ==
Or.getOperand(0)) {
9661 Y =
Or.getOperand(1);
9664 if (CommonOp ==
Or.getOperand(1)) {
9666 Y =
Or.getOperand(0);
9673 if (matchOr(LHSShiftArg, RHSShiftArg)) {
9678 }
else if (matchOr(RHSShiftArg, LHSShiftArg)) {
9687 return ApplyMasks(Res);
9700 if (IsRotate && (HasROTL || HasROTR || !(HasFSHL || HasFSHR))) {
9701 bool UseROTL = !LegalOperations || HasROTL;
9703 UseROTL ? LHSShiftAmt : RHSShiftAmt);
9705 bool UseFSHL = !LegalOperations || HasFSHL;
9707 RHSShiftArg, UseFSHL ? LHSShiftAmt : RHSShiftAmt);
9710 return ApplyMasks(Res);
9715 if (!HasROTL && !HasROTR && !HasFSHL && !HasFSHR)
9724 SDValue LExtOp0 = LHSShiftAmt;
9725 SDValue RExtOp0 = RHSShiftAmt;
9738 if (IsRotate && (HasROTL || HasROTR)) {
9739 if (
SDValue TryL = MatchRotatePosNeg(LHSShiftArg, LHSShiftAmt, RHSShiftAmt,
9740 LExtOp0, RExtOp0, FromAdd, HasROTL,
9744 if (
SDValue TryR = MatchRotatePosNeg(RHSShiftArg, RHSShiftAmt, LHSShiftAmt,
9745 RExtOp0, LExtOp0, FromAdd, HasROTR,
9750 if (
SDValue TryL = MatchFunnelPosNeg(LHSShiftArg, RHSShiftArg, LHSShiftAmt,
9751 RHSShiftAmt, LExtOp0, RExtOp0, FromAdd,
9755 if (
SDValue TryR = MatchFunnelPosNeg(LHSShiftArg, RHSShiftArg, RHSShiftAmt,
9756 LHSShiftAmt, RExtOp0, LExtOp0, FromAdd,
9806static std::optional<SDByteProvider>
9808 std::optional<uint64_t> VectorIndex,
9809 unsigned StartingIndex = 0,
9814 return std::nullopt;
9818 if (
Depth && !
Op.hasOneUse() &&
9819 (
Op.getOpcode() !=
ISD::LOAD || !
Op.getValueType().isVector()))
9820 return std::nullopt;
9824 if (
Op.getOpcode() !=
ISD::LOAD && VectorIndex.has_value())
9825 return std::nullopt;
9827 unsigned BitWidth =
Op.getScalarValueSizeInBits();
9829 return std::nullopt;
9831 assert(Index < ByteWidth &&
"invalid index requested");
9834 switch (
Op.getOpcode()) {
9837 VectorIndex, StartingIndex, ByteMask);
9839 return std::nullopt;
9841 VectorIndex, StartingIndex, ByteMask);
9843 return std::nullopt;
9845 if (
LHS->isConstantZero())
9847 if (
RHS->isConstantZero())
9849 return std::nullopt;
9854 return std::nullopt;
9856 uint64_t BitShift = ShiftOp->getZExtValue();
9858 if (BitShift % 8 != 0)
9859 return std::nullopt;
9865 return Index < ByteShift
9875 if (NarrowBitWidth % 8 != 0)
9876 return std::nullopt;
9877 uint64_t NarrowByteWidth = NarrowBitWidth / 8;
9879 if (Index >= NarrowByteWidth)
9881 ? std::optional<SDByteProvider>(
9885 StartingIndex, ByteMask);
9889 Depth + 1, VectorIndex, StartingIndex,
9896 return std::nullopt;
9899 MaskOp->getAPIntValue().extractBitsAsZExtValue(8, Index * 8);
9901 if (MaskByte == 0x00)
9905 VectorIndex, StartingIndex, ByteMask);
9907 return std::nullopt;
9912 if (MaskByte != 0xFF && !ByteMask.empty() && !
Result->isConstantZero())
9913 ByteMask[StartingIndex] &= MaskByte;
9920 return std::nullopt;
9922 VectorIndex =
OffsetOp->getZExtValue();
9926 if (NarrowBitWidth % 8 != 0)
9927 return std::nullopt;
9928 uint64_t NarrowByteWidth = NarrowBitWidth / 8;
9931 if (Index >= NarrowByteWidth)
9932 return std::nullopt;
9940 if (*VectorIndex * NarrowByteWidth > StartingIndex)
9941 return std::nullopt;
9942 if ((*VectorIndex + 1) * NarrowByteWidth <= StartingIndex)
9943 return std::nullopt;
9946 VectorIndex, StartingIndex, ByteMask);
9950 if (!
L->isSimple() ||
L->isIndexed())
9951 return std::nullopt;
9953 unsigned NarrowBitWidth =
L->getMemoryVT().getScalarSizeInBits();
9954 if (NarrowBitWidth % 8 != 0)
9955 return std::nullopt;
9956 uint64_t NarrowByteWidth = NarrowBitWidth / 8;
9961 if (Index >= NarrowByteWidth)
9963 ? std::optional<SDByteProvider>(
9967 unsigned BPVectorIndex = VectorIndex.value_or(0U);
9972 return std::nullopt;
9987 int64_t FirstOffset) {
9989 unsigned Width = ByteOffsets.
size();
9991 return std::nullopt;
9993 bool BigEndian =
true, LittleEndian =
true;
9994 for (
unsigned i = 0; i < Width; i++) {
9995 int64_t CurrentByteOffset = ByteOffsets[i] - FirstOffset;
9998 if (!BigEndian && !LittleEndian)
9999 return std::nullopt;
10002 assert((BigEndian != LittleEndian) &&
"It should be either big endian or"
10009 switch (
Value.getOpcode()) {
10014 return Value.getOperand(0);
10041SDValue DAGCombiner::mergeTruncStores(StoreSDNode *
N) {
10052 EVT MemVT =
N->getMemoryVT();
10053 if (!(MemVT == MVT::i8 || MemVT == MVT::i16 || MemVT == MVT::i32) ||
10054 !
N->isSimple() ||
N->isIndexed())
10061 unsigned MaxWideNumBits = 64;
10062 unsigned MaxStores = MaxWideNumBits / NarrowNumBits;
10073 if (
Store->getMemoryVT() != MemVT)
10078 Chain =
Store->getChain();
10079 if (MaxStores < Stores.
size())
10083 if (Stores.
size() < 2)
10088 unsigned NumStores = Stores.
size();
10089 unsigned WideNumBits = NumStores * NarrowNumBits;
10090 if (WideNumBits != 16 && WideNumBits != 32 && WideNumBits != 64)
10098 StoreSDNode *FirstStore =
nullptr;
10099 std::optional<BaseIndexOffset>
Base;
10100 for (
auto *
Store : Stores) {
10119 if (ShiftAmtC % NarrowNumBits != 0)
10126 Offset = ShiftAmtC / NarrowNumBits;
10132 SourceValue = WideVal;
10133 else if (SourceValue != WideVal) {
10141 SourceValue = WideVal;
10150 int64_t ByteOffsetFromBase = 0;
10153 else if (!
Base->equalBaseIndex(Ptr, DAG, ByteOffsetFromBase))
10157 if (ByteOffsetFromBase < FirstOffset) {
10158 FirstStore =
Store;
10159 FirstOffset = ByteOffsetFromBase;
10165 OffsetMap[
Offset] = ByteOffsetFromBase;
10171 assert(FirstStore &&
"First store must be set");
10178 if (!Allowed || !
Fast)
10183 auto checkOffsets = [&](
bool MatchLittleEndian) {
10184 if (MatchLittleEndian) {
10185 for (
unsigned i = 0; i != NumStores; ++i)
10186 if (OffsetMap[i] != i * (NarrowNumBits / 8) + FirstOffset)
10189 for (
unsigned i = 0, j = NumStores - 1; i != NumStores; ++i, --
j)
10190 if (OffsetMap[j] != i * (NarrowNumBits / 8) + FirstOffset)
10197 bool NeedBswap =
false;
10198 bool NeedRotate =
false;
10201 if (NarrowNumBits == 8 && checkOffsets(Layout.
isBigEndian()))
10203 else if (NumStores == 2 && checkOffsets(Layout.
isBigEndian()))
10212 "Unexpected store value to merge");
10221 }
else if (NeedRotate) {
10222 assert(WideNumBits % 2 == 0 &&
"Unexpected type for rotate");
10227 const MDNode *MemCacheHint = getCommonMemCacheHint(Stores);
10233 MMOMetadata(AAMDNodes(),
nullptr, MemCacheHint));
10270SDValue DAGCombiner::MatchLoadCombine(SDNode *
N) {
10272 "Can only match load combining against OR nodes");
10275 EVT VT =
N->getValueType(0);
10276 if (VT != MVT::i16 && VT != MVT::i32 && VT != MVT::i64)
10282 assert(
P.hasSrc() &&
"Must be a memory byte provider");
10285 unsigned LoadBitWidth =
Load->getMemoryVT().getScalarSizeInBits();
10287 assert(LoadBitWidth % 8 == 0 &&
10288 "can only analyze providers for individual bytes not bit");
10289 unsigned LoadByteWidth = LoadBitWidth / 8;
10294 std::optional<BaseIndexOffset>
Base;
10297 SmallPtrSet<LoadSDNode *, 8> Loads;
10298 std::optional<SDByteProvider> FirstByteProvider;
10305 unsigned ZeroExtendedBytes = 0;
10306 for (
int i = ByteWidth - 1; i >= 0; --i) {
10313 if (
P->isConstantZero()) {
10316 if (++ZeroExtendedBytes != (ByteWidth -
static_cast<unsigned>(i)))
10320 assert(
P->hasSrc() &&
"provenance should either be memory or zero");
10327 else if (Chain != LChain)
10332 int64_t ByteOffsetFromBase = 0;
10341 if (
L->getMemoryVT().isVector()) {
10342 unsigned LoadWidthInBit =
L->getMemoryVT().getScalarSizeInBits();
10343 if (LoadWidthInBit % 8 != 0)
10345 unsigned ByteOffsetFromVector =
P->SrcOffset * LoadWidthInBit / 8;
10352 else if (!
Base->equalBaseIndex(Ptr, DAG, ByteOffsetFromBase))
10356 ByteOffsetFromBase += MemoryByteOffset(*
P);
10357 ByteOffsets[i] = ByteOffsetFromBase;
10360 if (ByteOffsetFromBase < FirstOffset) {
10361 FirstByteProvider =
P;
10362 FirstOffset = ByteOffsetFromBase;
10368 assert(!Loads.
empty() &&
"All the bytes of the value must be loaded from "
10369 "memory, so there must be at least one load which produces the value");
10370 assert(
Base &&
"Base address of the accessed memory location must be set");
10373 bool NeedsZext = ZeroExtendedBytes > 0;
10384 ArrayRef(ByteOffsets).drop_back(ZeroExtendedBytes), FirstOffset);
10388 assert(FirstByteProvider &&
"must be set");
10392 if (MemoryByteOffset(*FirstByteProvider) != 0)
10400 if (LegalOperations &&
10402 FirstLoad->getAddressSpace(),
10411 bool NeedsBswap = IsBigEndianTarget != *IsBigEndian;
10418 if (NeedsBswap && (LegalOperations || NeedsZext) &&
10424 if (NeedsBswap && NeedsZext && LegalOperations &&
10432 *FirstLoad->getMemOperand(), &
Fast);
10433 if (!Allowed || !
Fast)
10436 const MDNode *MemCacheHint = getCommonMemCacheHint(Loads);
10440 FirstLoad->getBasePtr(), FirstLoad->getPointerInfo(), MemVT,
10442 MMOMetadata(AAMDNodes(),
nullptr, MemCacheHint));
10445 for (LoadSDNode *L : Loads)
10449 bool HasPartialMask =
false;
10451 for (
unsigned i = 0; i < ByteWidth; ++i) {
10452 CombinedMask |= (
uint64_t)ByteMasks[i] << (i * 8);
10453 if (ByteMasks[i] != 0xFF)
10454 HasPartialMask =
true;
10458 if (HasPartialMask)
10473 if (HasPartialMask)
10496SDValue DAGCombiner::unfoldMaskedMerge(SDNode *
N) {
10503 EVT VT =
N->getValueType(0);
10525 M =
And.getOperand(XorIdx ? 0 : 1);
10531 if (!matchAndXor(N0, 0, N1) && !matchAndXor(N0, 1, N1) &&
10532 !matchAndXor(N1, 0, N0) && !matchAndXor(N1, 1, N0))
10579SDValue DAGCombiner::visitXOR(SDNode *
N) {
10606 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
10618 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
10639 if (
SDValue Combined = visitADDLike(
N))
10647 isSetCCEquivalent(N0,
LHS,
RHS,
CC,
true) &&
10649 N->use_begin()->getUser()->getOpcode() ==
ISD::AND)) {
10651 LHS.getValueType());
10652 if (!LegalOperations ||
10656 switch (N0Opcode) {
10673 CombineTo(
N, SetCC);
10675 recursivelyDeleteUnusedNodes(N0.
getNode());
10691 AddToWorklist(
V.getNode());
10700 if (isOneUseSetCC(N01) || isOneUseSetCC(N00)) {
10705 return DAG.
getNode(NewOpcode,
DL, VT, N00, N01);
10718 return DAG.
getNode(NewOpcode,
DL, VT, N00, N01);
10728 APInt NotYValue = ~YConst->getAPIntValue();
10744 AddToWorklist(NotX.
getNode());
10749 if (!LegalOperations || hasOperation(
ISD::ABS, VT)) {
10753 SDValue A0 =
A.getOperand(0), A1 =
A.getOperand(1);
10755 if ((A0 == S && A1 == S0) || (A1 == S && A0 == S0))
10792 if (
SDValue V = hoistLogicOpWithSameOpcodeHands(
N))
10803 if (
SDValue MM = unfoldMaskedMerge(
N))
10872 if (!LogicOp.hasOneUse())
10875 unsigned LogicOpcode = LogicOp.getOpcode();
10881 unsigned ShiftOpcode = Shift->
getOpcode();
10884 assert(C1Node &&
"Expected a shift with constant operand");
10887 const APInt *&ShiftAmtVal) {
10888 if (
V.getOpcode() != ShiftOpcode || !
V.hasOneUse())
10896 ShiftOp =
V.getOperand(0);
10901 if (ShiftAmtVal->getBitWidth() != C1Val.
getBitWidth())
10906 bool Overflow =
false;
10907 APInt NewShiftAmt = C1Val.
uadd_ov(*ShiftAmtVal, Overflow);
10912 if (NewShiftAmt.
uge(
V.getScalarValueSizeInBits()))
10920 const APInt *C0Val;
10921 if (matchFirstShift(LogicOp.getOperand(0),
X, C0Val))
10922 Y = LogicOp.getOperand(1);
10923 else if (matchFirstShift(LogicOp.getOperand(1),
X, C0Val))
10924 Y = LogicOp.getOperand(0);
10935 return DAG.
getNode(LogicOpcode,
DL, VT, NewShift1, NewShift2,
10945SDValue DAGCombiner::visitShiftByConstant(SDNode *
N) {
10965 switch (
LHS.getOpcode()) {
10989 if (!IsShiftByConstant && !IsCopyOrSelect)
10992 if (IsCopyOrSelect &&
N->hasOneUse())
10997 EVT VT =
N->getValueType(0);
10999 N->getOpcode(),
DL, VT, {LHS.getOperand(1), N->getOperand(1)})) {
11002 return DAG.
getNode(
LHS.getOpcode(),
DL, VT, NewShift, NewRHS);
11008SDValue DAGCombiner::distributeTruncateThroughAnd(SDNode *
N) {
11013 EVT TruncVT =
N->getValueType(0);
11014 if (
N->hasOneUse() &&
N->getOperand(0).hasOneUse() &&
11022 AddToWorklist(Trunc00.
getNode());
11023 AddToWorklist(Trunc01.
getNode());
11031SDValue DAGCombiner::visitRotate(SDNode *
N) {
11035 EVT VT =
N->getValueType(0);
11050 bool OutOfRange =
false;
11051 auto MatchOutOfRange = [Bitsize, &OutOfRange](ConstantSDNode *
C) {
11052 OutOfRange |=
C->getAPIntValue().uge(Bitsize);
11060 return DAG.
getNode(
N->getOpcode(), dl, VT, N0, Amt);
11065 if (RotAmtC && RotAmtC->getAPIntValue() == 8 &&
11076 if (
SDValue NewOp1 = distributeTruncateThroughAnd(N1.
getNode()))
11077 return DAG.
getNode(
N->getOpcode(), dl, VT, N0, NewOp1);
11089 bool SameSide = (
N->getOpcode() == NextOp);
11096 if (Norm1 && Norm2)
11098 CombineOp, dl, ShiftVT, {Norm1, Norm2})) {
11100 {CombinedShift, BitsizeC});
11102 ISD::UREM, dl, ShiftVT, {CombinedShift, BitsizeC});
11104 CombinedShiftNorm);
11111SDValue DAGCombiner::visitSHL(SDNode *
N) {
11129 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
11152 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
11162 if (
SDValue NewOp1 = distributeTruncateThroughAnd(N1.
getNode()))
11168 auto MatchOutOfRange = [OpSizeInBits](ConstantSDNode *
LHS,
11169 ConstantSDNode *
RHS) {
11170 APInt c1 =
LHS->getAPIntValue();
11171 APInt c2 =
RHS->getAPIntValue();
11173 return (c1 + c2).uge(OpSizeInBits);
11178 auto MatchInRange = [OpSizeInBits](ConstantSDNode *
LHS,
11179 ConstantSDNode *
RHS) {
11180 APInt c1 =
LHS->getAPIntValue();
11181 APInt c2 =
RHS->getAPIntValue();
11183 return (c1 + c2).ult(OpSizeInBits);
11205 auto MatchOutOfRange = [OpSizeInBits, InnerBitwidth](ConstantSDNode *
LHS,
11206 ConstantSDNode *
RHS) {
11207 APInt c1 =
LHS->getAPIntValue();
11208 APInt c2 =
RHS->getAPIntValue();
11210 return c2.
uge(OpSizeInBits - InnerBitwidth) &&
11211 (c1 + c2).uge(OpSizeInBits);
11218 auto MatchInRange = [OpSizeInBits, InnerBitwidth](ConstantSDNode *
LHS,
11219 ConstantSDNode *
RHS) {
11220 APInt c1 =
LHS->getAPIntValue();
11221 APInt c2 =
RHS->getAPIntValue();
11223 return c2.
uge(OpSizeInBits - InnerBitwidth) &&
11224 (c1 + c2).ult(OpSizeInBits);
11244 auto MatchEqual = [VT](ConstantSDNode *
LHS, ConstantSDNode *
RHS) {
11245 APInt c1 =
LHS->getAPIntValue();
11246 APInt c2 =
RHS->getAPIntValue();
11256 AddToWorklist(NewSHL.
getNode());
11262 auto MatchShiftAmount = [OpSizeInBits](ConstantSDNode *
LHS,
11263 ConstantSDNode *
RHS) {
11264 const APInt &LHSC =
LHS->getAPIntValue();
11265 const APInt &RHSC =
RHS->getAPIntValue();
11266 return LHSC.
ult(OpSizeInBits) && RHSC.
ult(OpSizeInBits) &&
11338 AddToWorklist(Shl0.
getNode());
11357 {Add.getOperand(1)})) {
11377 if (
SDValue NewSHL = visitShiftByConstant(
N))
11411 Flags.setNoUnsignedWrap(
N->getFlags().hasNoUnsignedWrap() &&
11423 if (ShlVal.
ult(
C0.getBitWidth())) {
11424 APInt NewStep =
C0 << ShlVal;
11439 "SRL or SRA node is required here!");
11448 SDValue ShiftOperand =
N->getOperand(0);
11463 if (!IsSignExt && !IsZeroExt)
11470 auto UserOfLowerBits = [NarrowVTSize](
SDNode *U) {
11475 if (!UShiftAmtSrc) {
11479 return UShiftAmt < NarrowVTSize;
11486 TLI.isOperationLegalOrCustom(MulLoHiOp, NarrowVT) &&
11493 if (IsZeroExt && ShiftOperand.
hasOneUse() &&
11496 }
else if (IsSignExt && ShiftOperand.
hasOneUse() &&
11512 "Cannot have a multiply node with two different operand types.");
11523 if (ShiftAmt != NarrowVTSize)
11533 EVT TransformVT = NarrowVT;
11535 TransformVT =
TLI.getLegalTypeToTransformTo(*DAG.
getContext(), NarrowVT);
11539 if (!
TLI.isOperationLegalOrCustom(MulhOpcode, TransformVT))
11544 bool IsSigned =
N->getOpcode() ==
ISD::SRA;
11551 unsigned Opcode =
N->getOpcode();
11556 EVT VT =
N->getValueType(0);
11575SDValue DAGCombiner::visitSRA(SDNode *
N) {
11598 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
11601 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
11613 auto SumOfShifts = [&](ConstantSDNode *
LHS, ConstantSDNode *
RHS) {
11614 APInt c1 =
LHS->getAPIntValue();
11615 APInt c2 =
RHS->getAPIntValue();
11617 APInt Sum = c1 + c2;
11618 unsigned ShiftSum =
11619 Sum.
uge(OpSizeInBits) ? (OpSizeInBits - 1) : Sum.getZExtValue();
11629 "Expected matchBinaryPredicate to return one element for "
11633 ShiftValue = ShiftValues[0];
11647 APInt Sum =
C1 + C2;
11651 return DAG.
getNOT(
DL, NewShift, VT);
11675 if ((ShiftAmt > 0) &&
11685 N->getValueType(0), Trunc);
11702 if (ConstantSDNode *AddC =
11719 DAG.
getConstant(AddC->getAPIntValue().lshr(ShiftAmt).trunc(
11736 if (
SDValue NewOp1 = distributeTruncateThroughAnd(N1.
getNode()))
11753 if (LargeShift->getAPIntValue() == TruncBits) {
11771 const APInt &AddVal = AddC->getAPIntValue();
11773 SDNodeFlags ShiftFlags =
N->getFlags();
11777 SDNodeFlags AddFlags = N0->
getFlags();
11792 if (
SDValue NewSRA = visitShiftByConstant(
N))
11801 if (
SDValue NarrowLoad = reduceLoadWidth(
N))
11810SDValue DAGCombiner::visitSRL(SDNode *
N) {
11828 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
11831 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
11842 auto MatchOutOfRange = [OpSizeInBits](ConstantSDNode *
LHS,
11843 ConstantSDNode *
RHS) {
11844 APInt c1 =
LHS->getAPIntValue();
11845 APInt c2 =
RHS->getAPIntValue();
11847 return (c1 + c2).uge(OpSizeInBits);
11852 auto MatchInRange = [OpSizeInBits](ConstantSDNode *
LHS,
11853 ConstantSDNode *
RHS) {
11854 APInt c1 =
LHS->getAPIntValue();
11855 APInt c2 =
RHS->getAPIntValue();
11857 return (c1 + c2).ult(OpSizeInBits);
11877 if (c1 + OpSizeInBits == InnerShiftSize) {
11878 if (c1 + c2 >= InnerShiftSize)
11888 c1 + c2 < InnerShiftSize) {
11893 OpSizeInBits - c2),
11910 auto MatchShiftAmount = [OpSizeInBits](ConstantSDNode *
LHS,
11911 ConstantSDNode *
RHS) {
11912 const APInt &LHSC =
LHS->getAPIntValue();
11913 const APInt &RHSC =
RHS->getAPIntValue();
11914 return LHSC.
ult(OpSizeInBits) && RHSC.
ult(OpSizeInBits) &&
11956 AddToWorklist(SmallShift.
getNode());
11984 APInt UnknownBits = ~Known.Zero;
11985 if (UnknownBits == 0)
return DAG.
getConstant(1, SDLoc(N0), VT);
12000 AddToWorklist(
Op.getNode());
12009 if (
SDValue NewOp1 = distributeTruncateThroughAnd(N1.
getNode()))
12039 if (N1C->
getZExtValue() == (NumElts - 1) * EltSizeInBits) {
12042 "Expected BUILD_VECTOR operand as wide as element type");
12045 LastElt = DAG.
getBitcast(IntEltVT, LastElt);
12061 const APInt &AddVal = AddC->getAPIntValue();
12063 SDNodeFlags ShiftFlags =
N->getFlags();
12067 SDNodeFlags AddFlags = N0->
getFlags();
12079 if (
SDValue NewSRL = visitShiftByConstant(
N))
12083 if (
SDValue NarrowLoad = reduceLoadWidth(
N))
12110 if (
N->hasOneUse()) {
12111 SDNode *
User = *
N->user_begin();
12119 AddToWorklist(User);
12135 X.getScalarValueSizeInBits() == HalfBW &&
12136 Y.getScalarValueSizeInBits() == HalfBW) {
12138 (!LegalOperations ||
12144 (!LegalOperations ||
12162SDValue DAGCombiner::visitFunnelShift(SDNode *
N) {
12163 EVT VT =
N->getValueType(0);
12181 return IsFSHL ? N0 : N1;
12183 auto IsUndefOrZero = [](
SDValue V) {
12192 if (Cst->getAPIntValue().uge(
BitWidth)) {
12194 return DAG.
getNode(
N->getOpcode(),
DL, VT, N0, N1,
12200 return IsFSHL ? N0 : N1;
12206 if (IsUndefOrZero(N0))
12210 if (IsUndefOrZero(N1))
12224 "ShAmt must be in [1, BW-1] for the identity fold to be valid");
12226 unsigned C0Expected = IsFSHL ? ShAmt :
BitWidth - ShAmt;
12227 unsigned C1Expected = IsFSHL ?
BitWidth - ShAmt : ShAmt;
12250 if (
LHS &&
RHS &&
LHS->isSimple() &&
RHS->isSimple() &&
12251 LHS->getAddressSpace() ==
RHS->getAddressSpace() &&
12252 (
LHS->hasNUsesOfValue(1, 0) ||
RHS->hasNUsesOfValue(1, 0)) &&
12261 RHS->getAddressSpace(), NewAlign,
12262 RHS->getMemOperand()->getFlags(), &
Fast) &&
12266 AddToWorklist(NewPtr.
getNode());
12267 const MDNode *MemCacheHint = getCommonMemCacheHint({
LHS,
RHS});
12269 VT,
DL,
RHS->getChain(), NewPtr,
12270 RHS->getPointerInfo().getWithOffset(PtrOff), NewAlign,
12271 RHS->getMemOperand()->getFlags(),
12272 MMOMetadata(
RHS->getAAInfo(),
nullptr, MemCacheHint));
12300 if (N0 == N1 && hasOperation(RotOpc, VT))
12301 return DAG.
getNode(RotOpc,
DL, VT, N0, N2);
12310SDValue DAGCombiner::visitSHLSAT(SDNode *
N) {
12345SDValue DAGCombiner::foldABSToABD(SDNode *
N,
const SDLoc &
DL) {
12346 EVT SrcVT =
N->getValueType(0);
12349 N =
N->getOperand(0).getNode();
12351 EVT VT =
N->getValueType(0);
12358 SDValue AbsOp0 =
N->getOperand(0);
12363 auto IsNotMinSignedInt = [VT](ConstantSDNode *
C) {
12366 return !
C->getAPIntValue()
12368 .isMinSignedValue();
12384 auto CreateZextedAbd = [&](
unsigned AbdOpc) {
12411 assert(!IsAdd &&
"Unexpected abs(add(x,y)) pattern");
12425 EVT MaxVT = VT0.
bitsGT(VT1) ? VT0 : VT1;
12426 if ((VT0 == MaxVT || Op0->
hasOneUse()) &&
12428 (!LegalTypes || hasOperation(ABDOpcode, MaxVT))) {
12438 if (!LegalOperations || hasOperation(ABDOpcode, VT)) {
12446SDValue DAGCombiner::visitABS(SDNode *
N) {
12448 EVT VT =
N->getValueType(0);
12482SDValue DAGCombiner::visitABS_MIN_POISON(SDNode *
N) {
12484 EVT VT =
N->getValueType(0);
12528SDValue DAGCombiner::visitCLMUL(SDNode *
N) {
12529 unsigned Opcode =
N->getOpcode();
12532 EVT VT =
N->getValueType(0);
12542 return DAG.
getNode(Opcode,
DL, VT, N1, N0);
12563SDValue DAGCombiner::visitPEXT(SDNode *
N) {
12564 EVT VT =
N->getValueType(0);
12581SDValue DAGCombiner::visitPDEP(SDNode *
N) {
12582 EVT VT =
N->getValueType(0);
12605SDValue DAGCombiner::visitBSWAP(SDNode *
N) {
12607 EVT VT =
N->getValueType(0);
12632 if (ShAmt && ShAmt->getAPIntValue().ult(BW) &&
12633 ShAmt->getZExtValue() >= (BW / 2) && (ShAmt->getZExtValue() % 8) == 0 &&
12635 (!LegalOperations || hasOperation(
ISD::BSWAP, HalfVT))) {
12637 if (
uint64_t NewShAmt = (ShAmt->getZExtValue() - (BW / 2)))
12653 if (ShAmt && ShAmt->getAPIntValue().ult(BW) &&
12654 ShAmt->getZExtValue() % 8 == 0) {
12669 if (
Known.isZero())
12675 if (BW - (LZ + TZ) == 8) {
12680 if (!LegalOperations || hasOperation(
Opc, VT)) {
12682 SDNodeFlags
Flags =
12692SDValue DAGCombiner::visitBITREVERSE(SDNode *
N) {
12694 EVT VT =
N->getValueType(0);
12728 EVT VT = Src.getValueType();
12738 bool NeedAdd =
true;
12760SDValue DAGCombiner::visitCTLZ(SDNode *
N) {
12762 EVT VT =
N->getValueType(0);
12780SDValue DAGCombiner::visitCTLZ_ZERO_POISON(SDNode *
N) {
12782 EVT VT =
N->getValueType(0);
12796SDValue DAGCombiner::visitCTTZ(SDNode *
N) {
12798 EVT VT =
N->getValueType(0);
12813SDValue DAGCombiner::visitCTTZ_ZERO_POISON(SDNode *
N) {
12815 EVT VT =
N->getValueType(0);
12825SDValue DAGCombiner::visitPARITY(SDNode *
N) {
12827 EVT VT =
N->getValueType(0);
12836SDValue DAGCombiner::visitCTPOP(SDNode *
N) {
12838 EVT VT =
N->getValueType(0);
12850 const APInt &Amt = AmtC->getAPIntValue();
12851 if (Amt.
ult(NumBits)) {
12887 EVT VT =
LHS.getValueType();
12892 TLI.isProfitableToCombineMinNumMaxNum(VT) &&
12918 if (
TLI.isOperationLegalOrCustom(IEEEOpcode, VT))
12922 if (
TLI.isOperationLegalOrCustom(Opcode, TransformVT))
12933 if (
TLI.isOperationLegalOrCustom(IEEEOpcode, VT))
12937 if (
TLI.isOperationLegalOrCustom(Opcode, TransformVT))
12948SDValue DAGCombiner::foldShiftToAvg(SDNode *
N,
const SDLoc &
DL) {
12949 const unsigned Opcode =
N->getOpcode();
12953 EVT VT =
N->getValueType(0);
12954 bool IsUnsigned = Opcode ==
ISD::SRL;
12961 SDNodeFlags
Flags =
12968 if (hasOperation(FloorISD, VT))
12977 if (hasOperation(SubISD, VT))
12984SDValue DAGCombiner::foldBitwiseOpWithNeg(SDNode *
N,
const SDLoc &
DL, EVT VT) {
12985 unsigned Opc =
N->getOpcode();
13010 True, DAG, LegalOperations, ForCodeSize);
13014 HandleSDNode NegTrueHandle(NegTrue);
13022 if (
LHS == NegTrue) {
13026 RHS, DAG, LegalOperations, ForCodeSize);
13028 HandleSDNode NegRHSHandle(NegRHS);
13029 if (NegRHS ==
False) {
13051 EVT VT =
N->getValueType(0);
13053 VT !=
Cond.getOperand(0).getValueType())
13079 if (!
TLI.convertSelectOfConstantsToMath(VT))
13096SDValue DAGCombiner::foldSelectOfConstants(SDNode *
N) {
13100 EVT VT =
N->getValueType(0);
13101 EVT CondVT =
Cond.getValueType();
13112 if (CondVT != MVT::i1 || LegalOperations) {
13127 if (
C1->isZero() && C2->isOne()) {
13136 if (
C1->isOne() && C2->isZero() && CondVT == VT)
13147 assert(CondVT == MVT::i1 && !LegalOperations);
13150 if (
C1->isOne() && C2->isZero())
13154 if (
C1->isAllOnes() && C2->isZero())
13158 if (
C1->isZero() && C2->isOne()) {
13165 if (
C1->isZero() && C2->isAllOnes()) {
13178 const APInt &C1Val =
C1->getAPIntValue();
13179 const APInt &C2Val = C2->getAPIntValue();
13182 if (C1Val - 1 == C2Val) {
13188 if (C1Val + 1 == C2Val) {
13202 if (
C1->isAllOnes()) {
13208 if (C2->isAllOnes()) {
13223 "Expected a (v)select");
13225 SDValue T =
N->getOperand(1),
F =
N->getOperand(2);
13226 EVT VT =
N->getValueType(0);
13262 EVT VT =
N->getValueType(0);
13325 EVT VT =
LHS.getValueType();
13327 if (LegalOperations && !hasOperation(ABDOpc, VT))
13342 return !
C->getAPIntValue().isMinSignedValue();
13348 bool IsTypeLegalOrPromote =
13366 IsTypeLegalOrPromote)
13382 IsTypeLegalOrPromote)
13398 EVT VT =
True.getValueType();
13423 std::tuple<unsigned, SDValue, SDValue>
Invalid(0, {}, {});
13425 EVT VT =
LHS.getValueType();
13446 unsigned Opcode = 0;
13491 if (!
TLI.isOperationLegalOrCustom(Opcode, VT))
13494 return {Opcode,
LHS,
RHS};
13502 EVT VT =
LHS.getValueType();
13507 bool IsStrict =
Cond->isStrictFPOpcode();
13512 DAG,
DL,
CC, Op0, Op1,
LHS,
RHS,
N->getFlags(), IsStrict);
13520 {
Cond.getOperand(0), NewLHS, NewRHS});
13524 return DAG.
getNode(Opcode,
DL, VT, NewLHS, NewRHS);
13559 if (!CTV || !CFV || !CCnst)
13564 if (CTV->getAPIntValue() == CFV->getAPIntValue())
13567 const APInt &CmpVal = CCnst->getAPIntValue();
13568 bool MatchesTV = CmpVal == CTV->getAPIntValue();
13569 bool MatchesFV = CmpVal == CFV->getAPIntValue();
13570 if (!MatchesTV && !MatchesFV)
13589 N->getOperand(2),
N->getOperand(3),
SDLoc(
N),
13590 N->getValueType(0), DAG,
N->getFlags());
13593SDValue DAGCombiner::visitSELECT(SDNode *
N) {
13597 EVT VT =
N->getValueType(0);
13600 SDNodeFlags
Flags =
N->getFlags();
13612 if (
SDValue V = foldSelectOfConstants(
N))
13620 CC, N1, N2,
DL, VT, DAG, Flags))
13625 if (SimplifySelectOps(
N, N1, N2))
13628 if (VT0 == MVT::i1) {
13637 bool normalizeToSequence =
13646 if (normalizeToSequence || !InnerSelect.
use_empty())
13648 InnerSelect, N2, Flags);
13651 recursivelyDeleteUnusedNodes(InnerSelect.
getNode());
13658 Cond1, N1, N2, Flags);
13659 if (normalizeToSequence || !InnerSelect.
use_empty())
13661 InnerSelect, Flags);
13664 recursivelyDeleteUnusedNodes(InnerSelect.
getNode());
13674 if (!normalizeToSequence) {
13680 if (
SDValue Combined = visitANDLike(N0, N1_0,
N)) {
13693 if (!normalizeToSequence) {
13699 if (
SDValue Combined = visitORLike(N0, N2_0,
DL))
13736 combineMinNumMaxNum(
DL, VT, Cond0, Cond1, N1, N2,
CC))
13749 if (
C && NotC &&
C->getAPIntValue() == ~NotC->getAPIntValue()) {
13772 (!LegalOperations &&
13780 if (
SDValue ABD = foldSelectToABD(Cond0, Cond1, N1, N2,
CC,
DL))
13783 if (
SDValue NewSel = SimplifySelect(
DL, N0, N1, N2))
13793 if (
SDValue BinOp = foldSelectOfBinops(
N))
13812 EVT VT =
N->getValueType(0);
13820 if (
LHS->getNumOperands() != 2 ||
RHS->getNumOperands() != 2)
13829 for (
int i = 0; i < NumElems / 2; ++i) {
13830 if (
Cond->getOperand(i)->isUndef())
13833 if (BottomHalf ==
nullptr)
13835 else if (
Cond->getOperand(i).getNode() != BottomHalf)
13841 for (
int i = NumElems / 2; i < NumElems; ++i) {
13842 if (
Cond->getOperand(i)->isUndef())
13845 if (TopHalf ==
nullptr)
13847 else if (
Cond->getOperand(i).getNode() != TopHalf)
13851 assert(TopHalf && BottomHalf &&
13852 "One half of the selector was all UNDEFs and the other was all the "
13853 "same value. This should have been addressed before this function.");
13856 BottomHalf->
isZero() ?
RHS->getOperand(0) :
LHS->getOperand(0),
13857 TopHalf->
isZero() ?
RHS->getOperand(1) :
LHS->getOperand(1));
13870 EVT VT = BasePtr.getValueType();
13874 SplatVal.getValueType() == VT) {
13880 if (Index.getOpcode() !=
ISD::ADD)
13905 if (
TLI.shouldRemoveExtendFromGSIndex(Index, DataVT)) {
13907 Index = Index.getOperand(0);
13919 TLI.shouldRemoveExtendFromGSIndex(Index, DataVT)) {
13920 Index = Index.getOperand(0);
13927SDValue DAGCombiner::visitVPSCATTER(SDNode *
N) {
13958SDValue DAGCombiner::visitMSCATTER(SDNode *
N) {
13994 if (Mask.getValueType().getScalarSizeInBits() != 1)
13998 unsigned NumOnes = 0;
13999 auto Op = Mask->op_begin();
14000 for (;
Op != Mask->op_end(); ++
Op) {
14009 for (;
Op != Mask->op_end(); ++
Op)
14018 Mask.getOperand(1).getValueType().getSizeInBits() <= 64)
14019 return Mask.getConstantOperandVal(1);
14024SDValue DAGCombiner::visitMSTORE(SDNode *
N) {
14030 EVT VT =
Value.getValueType();
14039 MST1->isSimple() && MST1->getBasePtr() == Ptr &&
14042 MST1->getMemoryVT().getStoreSize()) ||
14046 CombineTo(MST1, MST1->getChain());
14070 unsigned IsFast = 0;
14089 if (CombineToPreIndexedLoadStore(
N) || CombineToPostIndexedLoadStore(
N))
14095 APInt TruncDemandedBits =
14122 Value.getOperand(0).getValueType());
14132SDValue DAGCombiner::visitVP_STRIDED_STORE(SDNode *
N) {
14137 CStride && CStride->getZExtValue() == EltVT.
getStoreSize()) {
14138 return DAG.
getStoreVP(SST->getChain(), SDLoc(
N), SST->getValue(),
14139 SST->getBasePtr(), SST->getOffset(), SST->getMask(),
14140 SST->getVectorLength(), SST->getMemoryVT(),
14141 SST->getMemOperand(), SST->getAddressingMode(),
14142 SST->isTruncatingStore(), SST->isCompressingStore());
14147SDValue DAGCombiner::visitVECTOR_COMPRESS(SDNode *
N) {
14151 SDValue Passthru =
N->getOperand(2);
14154 bool HasPassthru = !Passthru.
isUndef();
14167 unsigned NumSelected = 0;
14169 for (
unsigned I = 0;
I < NumElmts; ++
I) {
14178 Ops.push_back(VecI);
14182 for (
unsigned Rest = NumSelected; Rest < NumElmts; ++Rest) {
14188 Ops.push_back(Val);
14196SDValue DAGCombiner::visitVPGATHER(SDNode *
N) {
14224SDValue DAGCombiner::visitMGATHER(SDNode *
N) {
14237 return CombineTo(
N, PassThru, MGT->
getChain());
14256SDValue DAGCombiner::visitMLOAD(SDNode *
N) {
14274 return CombineTo(
N, NewLd, NewLd.
getValue(1));
14278 if (CombineToPreIndexedLoadStore(
N) || CombineToPostIndexedLoadStore(
N))
14284SDValue DAGCombiner::visitMHISTOGRAM(SDNode *
N) {
14294 EVT DataVT =
Index.getValueType();
14312SDValue DAGCombiner::visitPARTIAL_REDUCE_MLA(SDNode *
N) {
14313 if (
SDValue Res = foldPartialReduceMLAMulOp(
N))
14315 if (
SDValue Res = foldPartialReduceAdd(
N))
14333SDValue DAGCombiner::foldPartialReduceMLAMulOp(SDNode *
N) {
14355 bool IsMLS =
false;
14385 RHS.getValueType().getScalarType()));
14393 auto IsIntOrFPExtOpcode = [](
unsigned int Opcode) {
14397 unsigned LHSOpcode =
LHS->getOpcode();
14398 if (!IsIntOrFPExtOpcode(LHSOpcode))
14409 EVT OpVT =
Op.getValueType();
14412 if (OrigOp1.
getOpcode() == ISD::VP_MERGE)
14424 EVT AccVT = Acc.getValueType();
14435 unsigned LHSBits =
LHS.getValueType().getScalarSizeInBits();
14452 ApplyPredicate(
C, LHSExtOp);
14453 return GetMLA(NewOpcode, Acc, LHSExtOp,
C);
14456 unsigned RHSOpcode =
RHS->getOpcode();
14457 if (!IsIntOrFPExtOpcode(RHSOpcode))
14482 EVT AccElemVT = Acc.getValueType().getVectorElementType();
14484 NewOpc !=
N->getOpcode())
14494 ApplyPredicate(RHSExtOp, LHSExtOp);
14495 return GetMLA(NewOpc, Acc, LHSExtOp, RHSExtOp);
14505SDValue DAGCombiner::foldPartialReduceAdd(SDNode *
N) {
14525 bool IsMLS =
false;
14539 if (Op1IsSigned != NodeIsSigned &&
14560 if (PromOp1VT == UnextOp1VT)
14562 UnextOp1VT = PromOp1VT;
14578 : DAG.
getNode(NewOpcode,
DL, AccVT, Acc, UnextOp1, Constant);
14581SDValue DAGCombiner::visitLOOP_DEPENDENCE_MASK(SDNode *
N) {
14583 EVT VT =
N->getValueType(0);
14584 unsigned LaneOffset =
N->getConstantOperandVal(3);
14587 if (LaneOffset == 0 &&
14594SDValue DAGCombiner::visitVP_STRIDED_LOAD(SDNode *
N) {
14599 CStride && CStride->getZExtValue() == EltVT.
getStoreSize()) {
14601 SLD->getAddressingMode(), SLD->getExtensionType(), SLD->getValueType(0),
14602 SDLoc(
N), SLD->getChain(), SLD->getBasePtr(), SLD->getOffset(),
14603 SLD->getMask(), SLD->getVectorLength(), SLD->getMemoryVT(),
14604 SLD->getMemOperand(), SLD->isExpandingLoad());
14605 return CombineTo(
N, NewLd, NewLd.
getValue(1));
14612SDValue DAGCombiner::foldVSelectOfConstants(SDNode *
N) {
14616 EVT VT =
N->getValueType(0);
14617 if (!
Cond.hasOneUse() ||
Cond.getScalarValueSizeInBits() != 1 ||
14626 bool AllAddOne =
true;
14627 bool AllSubOne =
true;
14629 for (
unsigned i = 0; i != Elts; ++i) {
14652 if (AllAddOne || AllSubOne) {
14685 if (!
TLI.isTypeLegal(VT))
14688 EVT CondVT =
Cond.getValueType();
14689 assert(CondVT.
isVector() &&
"Vector select expects a vector selector!");
14697 if (!IsTAllZero && !IsTAllOne && !IsFAllZero && !IsFAllOne)
14701 if (IsTAllZero && IsFAllZero) {
14710 Cond.getOperand(0).getValueType() == VT && VT.
isSimple() &&
14712 TValAPInt.
isOne() &&
14736 if (!IsTAllOne && !IsFAllZero &&
Cond.hasOneUse() &&
14740 if (IsTAllZero || IsFAllOne) {
14753 "Select condition no longer all-sign bits");
14756 if (IsTAllOne && IsFAllZero)
14785SDValue DAGCombiner::visitVSELECT(SDNode *
N) {
14789 EVT VT =
N->getValueType(0);
14822 bool isAbs =
false;
14841 AddToWorklist(Shift.
getNode());
14842 AddToWorklist(
Add.getNode());
14872 EVT NarrowVT =
LHS.getValueType();
14880 SetCCWidth < WideWidth &&
14885 Ld->getAddressSpace(), LoadExtOpcode,
14932 (OpLHS == CondLHS || OpRHS == CondLHS))
14935 if (OpRHS.getOpcode() == CondRHS.getOpcode() &&
14938 CondLHS == OpLHS) {
14942 auto MatchUADDSAT = [](ConstantSDNode *
Op, ConstantSDNode *
Cond) {
14943 return Cond->getAPIntValue() == ~Op->getAPIntValue();
14984 if (OpLHS ==
LHS) {
14999 auto MatchUSUBSAT = [](ConstantSDNode *
Op, ConstantSDNode *
Cond) {
15000 return (!
Op && !
Cond) ||
15002 Cond->getAPIntValue() == (-
Op->getAPIntValue() - 1));
15038 if (SimplifySelectOps(
N, N1, N2))
15058 if (
SDValue V = foldVSelectOfConstants(
N))
15077SDValue DAGCombiner::visitSELECT_CC(SDNode *
N) {
15100 AddToWorklist(
SCC.getNode());
15105 return SCCC->isZero() ? N3 : N2;
15109 if (
SCC->isUndef())
15115 SCC.getOperand(0),
SCC.getOperand(1), N2, N3,
15116 SCC.getOperand(2),
SCC->getFlags());
15121 if (SimplifySelectOps(
N, N2, N3))
15125 DAG,
DL,
CC, N0, N1, N2, N3,
N->getFlags(),
false);
15127 return DAG.
getNode(Opcode,
DL,
N->getValueType(0), NewLHS, NewRHS,
15131 return SimplifySelectCC(
DL, N0, N1, N2, N3,
CC);
15134SDValue DAGCombiner::visitSETCC(SDNode *
N) {
15143 EVT VT =
N->getValueType(0);
15150 if (PreferSetCC && Combined.getOpcode() !=
ISD::SETCC) {
15151 SDValue NewSetCC = rebuildSetCC(Combined);
15179 A.getOperand(0) ==
B.getOperand(0);
15183 B.getOperand(0) ==
A;
15186 bool IsRotate =
false;
15189 if (IsAndWithShift(N0, N1)) {
15191 ShiftOrRotate = N1;
15192 }
else if (IsAndWithShift(N1, N0)) {
15194 ShiftOrRotate = N0;
15195 }
else if (IsRotateWithOp(N0, N1)) {
15198 ShiftOrRotate = N1;
15199 }
else if (IsRotateWithOp(N1, N0)) {
15202 ShiftOrRotate = N0;
15205 if (AndOrOp && ShiftOrRotate && ShiftOrRotate.hasOneUse() &&
15210 auto GetAPIntValue = [](
SDValue Op) -> std::optional<APInt> {
15213 if (CNode ==
nullptr)
15214 return std::nullopt;
15217 std::optional<APInt> AndCMask =
15218 IsRotate ? std::nullopt : GetAPIntValue(AndOrOp.
getOperand(1));
15219 std::optional<APInt> ShiftCAmt =
15220 GetAPIntValue(ShiftOrRotate.getOperand(1));
15224 if (ShiftCAmt && (IsRotate || AndCMask) && ShiftCAmt->ult(NumBits)) {
15225 unsigned ShiftOpc = ShiftOrRotate.getOpcode();
15227 bool CanTransform = IsRotate;
15228 if (!CanTransform) {
15230 CanTransform = *ShiftCAmt == (~*AndCMask).
popcount();
15232 CanTransform &= (*ShiftCAmt + AndCMask->popcount()) == NumBits;
15240 bool MayTransformRotate =
15241 !ShiftCAmt->isZero() && NumBits % ShiftCAmt->getZExtValue() == 0;
15244 OpVT, ShiftOpc, MayTransformRotate, *ShiftCAmt, AndCMask);
15246 if (CanTransform && NewShiftOpc != ShiftOpc) {
15248 DAG.
getNode(NewShiftOpc,
DL, OpVT, ShiftOrRotate.getOperand(0),
15249 ShiftOrRotate.getOperand(1));
15256 NumBits - ShiftCAmt->getZExtValue())
15257 : APInt::getLowBitsSet(NumBits,
15258 NumBits - ShiftCAmt->getZExtValue());
15266 return DAG.
getSetCC(
DL, VT, NewAndOrOp, NewShiftOrRotate,
Cond);
15274SDValue DAGCombiner::visitSETCCCARRY(SDNode *
N) {
15295 if (!
N.hasOneUse())
15324 unsigned Opcode =
N->getOpcode();
15326 EVT VT =
N->getValueType(0);
15329 "Expected EXTEND dag node in input!");
15371 unsigned Opcode =
N->getOpcode();
15373 EVT VT =
N->getValueType(0);
15376 "Expected EXTEND dag node in input!");
15382 return DAG.
getNode(Opcode,
DL, VT, N0);
15401 unsigned FoldOpc = Opcode;
15414 if (!(VT.
isVector() && (!LegalTypes ||
TLI.isTypeLegal(SVT)) &&
15428 TLI.getBooleanContents(VT) ==
15431 for (
unsigned i = 0; i != NumElts; ++i) {
15433 if (
Op.isUndef()) {
15444 APInt C =
Op->getAsAPIntVal().zextOrTrunc(EVTBits);
15462 bool HasCopyToRegUses =
false;
15477 for (
unsigned i = 0; i != 2; ++i) {
15495 HasCopyToRegUses =
true;
15498 if (HasCopyToRegUses) {
15499 bool BothLiveOut =
false;
15502 BothLiveOut =
true;
15509 return !ExtendNodes.
empty();
15514void DAGCombiner::ExtendSetCCUses(
const SmallVectorImpl<SDNode *> &SetCCs,
15519 for (SDNode *SetCC : SetCCs) {
15522 for (
unsigned j = 0;
j != 2; ++
j) {
15523 SDValue SOp = SetCC->getOperand(j);
15524 if (SOp == OrigLoad)
15525 Ops.push_back(ExtLoad);
15530 Ops.push_back(SetCC->getOperand(2));
15536SDValue DAGCombiner::CombineExtLoad(SDNode *
N) {
15538 EVT DstVT =
N->getValueType(0);
15543 "Unexpected node type (not an extend)!");
15581 EVT SplitSrcVT = SrcVT;
15582 EVT SplitDstVT = DstVT;
15597 const unsigned NumSplits =
15604 for (
unsigned Idx = 0;
Idx < NumSplits;
Idx++) {
15608 ExtType, SDLoc(LN0), SplitDstVT, LN0->
getChain(), BasePtr,
15623 AddToWorklist(NewChain.
getNode());
15625 CombineTo(
N, NewValue);
15631 ExtendSetCCUses(SetCCs, N0, NewValue, (
ISD::NodeType)
N->getOpcode());
15632 CombineTo(N0.
getNode(), Trunc, NewChain);
15638SDValue DAGCombiner::CombineZExtLogicopShiftLoad(SDNode *
N) {
15640 EVT VT =
N->getValueType(0);
15641 EVT OrigVT =
N->getOperand(0).getValueType();
15663 EVT MemVT =
Load->getMemoryVT();
15685 Load->getChain(),
Load->getBasePtr(),
15686 Load->getMemoryVT(),
Load->getMemOperand());
15703 Load->getValueType(0), ExtLoad);
15708 recursivelyDeleteUnusedNodes(N0.
getNode());
15717SDValue DAGCombiner::matchVSelectOpSizesWithSetCC(SDNode *Cast) {
15718 unsigned CastOpcode = Cast->
getOpcode();
15722 "Unexpected opcode for vector select narrowing/widening");
15762 bool LegalOperations,
SDNode *
N,
15776 EVT MemVT = OldExtLoad->getMemoryVT();
15777 if ((LegalOperations || !OldExtLoad->isSimple() || VT.
isVector()) &&
15778 !
TLI.isLoadLegal(VT, MemVT, OldExtLoad->getAlign(),
15779 OldExtLoad->getAddressSpace(), ExtLoadType,
false))
15784 OldExtLoad->getBasePtr(), MemVT,
15785 OldExtLoad->getMemOperand());
15792 DAG.
getValueType(OldExtLoad->getValueType(0).getScalarType()));
15810 bool NonNegZExt =
false) {
15817 (Frozen && !
Load->hasNUsesOfValue(1, 0)))
15823 "Unexpected load type or opcode");
15840 !
TLI.isLoadLegal(VT,
Load->getValueType(0),
Load->getAlign(),
15841 Load->getAddressSpace(), ExtLoadType,
false))
15844 bool DoXform =
true;
15848 ExtOpc, SetCCs,
TLI);
15850 DoXform &=
TLI.isVectorLoadExtDesirable(
SDValue(
N, 0));
15857 unsigned OldBits,
unsigned NewBits,
15862 bool IsVariadic = Dbg->isVariadic();
15865 for (
unsigned I = 0,
E = Locs.
size();
I !=
E; ++
I) {
15870 if (
Op.getSDNode() == Old.getNode() &&
Op.getResNo() == Old.getResNo()) {
15894 for (
unsigned ArgNo : AffectedArgs)
15901 Dbg->getAdditionalDependencies(), Dbg->isIndirect(), Dbg->getDebugLoc(),
15902 Dbg->getOrder(), Dbg->isVariadic());
15904 Dbg->setIsInvalidated();
15905 Dbg->setIsEmitted();
15913 auto SalvageToOldLoadSize = [&](
SDValue Old,
SDValue New,
bool IsSigned) {
15918 unsigned VarBitsOld = Old.getValueSizeInBits();
15919 unsigned VarBitsNew = New.getValueSizeInBits();
15922 if (Dbg->isInvalidated())
15925 SalvageDbgValue(Dbg, Old, New, VarBitsOld, VarBitsNew, IsSigned);
15931 Load->getValueType(0),
Load->getMemOperand());
15940 Combiner.ExtendSetCCUses(SetCCs, N0, Res, ExtOpc);
15943 if (
N->getHasDebugValue()) {
15947 if (NoReplaceTrunc) {
15949 if (
Load->getHasDebugValue()) {
15951 SalvageToOldLoadSize(OldLoadVal, ExtLoad, IsSigned);
15981 !
TLI.isLoadLegalOrCustom(VT, Ld->getValueType(0), Ld->getAlign(),
15982 Ld->getAddressSpace(), ExtLoadType,
false))
15985 if (!
TLI.isVectorLoadExtDesirable(
SDValue(
N, 0)))
15989 SDValue PassThru = DAG.
getNode(ExtOpc, dl, VT, Ld->getPassThru());
15991 VT, dl, Ld->getChain(), Ld->getBasePtr(), Ld->getOffset(), Ld->getMask(),
15992 PassThru, Ld->getMemoryVT(), Ld->getMemOperand(), Ld->getAddressingMode(),
15993 ExtLoadType, Ld->isExpandingLoad());
16006 EVT MemoryVT = ALoad->getMemoryVT();
16007 if (!
TLI.isLoadLegal(VT, MemoryVT, ALoad->getAlign(),
16008 ALoad->getAddressSpace(), ExtLoadType,
true))
16016 EVT OrigVT = ALoad->getValueType(0);
16019 ExtLoadType,
SDLoc(ALoad), MemoryVT, VT, ALoad->getChain(),
16020 ALoad->getBasePtr(), ALoad->getMemOperand()));
16030 bool LegalOperations) {
16042 EVT VT =
N->getValueType(0);
16043 EVT XVT =
X.getValueType();
16054 if (!
TLI.shouldAvoidTransformToShift(VT, ShCt)) {
16059 return DAG.
getNode(ShiftOpcode,
DL, VT, NotX, ShiftAmount);
16065SDValue DAGCombiner::foldSextSetcc(SDNode *
N) {
16073 EVT VT =
N->getValueType(0);
16083 if (VT.
isVector() && !LegalOperations &&
16103 if (SVT == MatchingVecType) {
16120 auto IsFreeToExtend = [&](
SDValue V) {
16132 if (!Ld->isSimple() ||
16134 Ld->getAddressSpace(), LoadOpcode,
false))
16139 for (SDUse &Use :
V->uses()) {
16141 SDNode *
User =
Use.getUser();
16142 if (
Use.getResNo() != 0 || User == N0.
getNode())
16147 if (
User->getOpcode() != ExtOpcode ||
User->getValueType(0) != VT)
16153 if (IsFreeToExtend(N00) && IsFreeToExtend(N01)) {
16174 SDValue ExtTrueVal = (SetCCWidth == 1)
16178 if (
SDValue SCC = SimplifySelectCC(
DL, N00, N01, ExtTrueVal,
Zero,
CC,
true))
16198SDValue DAGCombiner::visitSIGN_EXTEND(SDNode *
N) {
16200 EVT VT =
N->getValueType(0);
16204 if (
SDValue FoldedVOp = SimplifyVCastOp(
N,
DL))
16250 if (NarrowLoad.getNode() != N0.
getNode()) {
16251 CombineTo(N0.
getNode(), NarrowLoad);
16253 AddToWorklist(oye);
16261 unsigned OpBits =
Op.getScalarValueSizeInBits();
16267 if (OpBits == DestBits) {
16273 if (OpBits < DestBits) {
16282 Flags.setNoSignedWrap(
true);
16290 if (OpBits < DestBits)
16292 else if (OpBits > DestBits)
16312 if (
SDValue ExtLoad = CombineExtLoad(
N))
16348 bool NoReplaceTruncAnd = !N0.
hasOneUse();
16349 bool NoReplaceTrunc =
SDValue(LN00, 0).hasOneUse();
16352 if (NoReplaceTruncAnd) {
16355 CombineTo(N0.
getNode(), TruncAnd);
16357 if (NoReplaceTrunc) {
16362 CombineTo(LN00, Trunc, ExtLoad.
getValue(1));
16381 if (
SDValue NewVSel = matchVSelectOpSizesWithSetCC(
N))
16412 if (NewXor.getNode() == N0.
getNode()) {
16438 "Expected extend op");
16483SDValue DAGCombiner::visitZERO_EXTEND(SDNode *
N) {
16485 EVT VT =
N->getValueType(0);
16489 if (
SDValue FoldedVOp = SimplifyVCastOp(
N,
DL))
16520 APInt TruncatedBits =
16522 APInt(
Op.getScalarValueSizeInBits(), 0) :
16523 APInt::getBitsSet(
Op.getScalarValueSizeInBits(),
16524 N0.getScalarValueSizeInBits(),
16525 std::
min(
Op.getScalarValueSizeInBits(),
16528 SDValue ZExtOrTrunc = DAG.getZExtOrTrunc(Op, DL, VT);
16529 DAG.salvageDebugInfo(*N0.getNode());
16531 return ZExtOrTrunc;
16541 if (NarrowLoad.getNode() != N0.
getNode()) {
16542 CombineTo(N0.
getNode(), NarrowLoad);
16544 AddToWorklist(oye);
16552 if (
N->getFlags().hasNonNeg()) {
16560 if (OpBits == DestBits) {
16566 if (OpBits < DestBits) {
16576 Flags.setNoSignedWrap(
true);
16577 Flags.setNoUnsignedWrap(
true);
16589 AddToWorklist(
Op.getNode());
16593 return ZExtOrTrunc;
16599 AddToWorklist(
Op.getNode());
16625 EVT SrcVT = Src.getValueType();
16654 if (
SDValue ExtLoad = CombineExtLoad(
N))
16675 bool DoXform =
true;
16682 if (isAndLoadExtLoad(AndC, LN00, LoadResultTy, ExtVT))
16698 bool NoReplaceTruncAnd = !N0.
hasOneUse();
16699 bool NoReplaceTrunc =
SDValue(LN00, 0).hasOneUse();
16702 if (NoReplaceTruncAnd) {
16705 CombineTo(N0.
getNode(), TruncAnd);
16707 if (NoReplaceTrunc) {
16712 CombineTo(LN00, Trunc, ExtLoad.
getValue(1));
16721 if (
SDValue ZExtLoad = CombineZExtLogicopShiftLoad(
N))
16734 SelectionDAG::FlagInserter FlagsInserter(DAG, N0->
getFlags());
16737 if (!LegalOperations && VT.
isVector() &&
16789 if (ShAmtC->getAPIntValue().ugt(KnownZeroBits)) {
16810 if (
SDValue NewVSel = matchVSelectOpSizesWithSetCC(
N))
16842SDValue DAGCombiner::visitANY_EXTEND(SDNode *
N) {
16844 EVT VT =
N->getValueType(0);
16878 if (NarrowLoad.getNode() != N0.
getNode()) {
16879 CombineTo(N0.
getNode(), NarrowLoad);
16881 AddToWorklist(oye);
16907 EVT SrcVT = Src.getValueType();
16945 bool DoXform =
true;
16961 if (NoReplaceTrunc) {
16963 recursivelyDeleteUnusedNodes(N0.
getNode());
16966 CombineTo(LN0, Trunc, ExtLoad.
getValue(1));
16982 if (!LegalOperations ||
16988 CombineTo(
N, ExtLoad);
16990 recursivelyDeleteUnusedNodes(LN0);
16998 SelectionDAG::FlagInserter FlagsInserter(DAG, Flags);
17005 if (VT.
isVector() && !LegalOperations) {
17032 if (
SDValue SCC = SimplifySelectCC(
17047SDValue DAGCombiner::visitAssertExt(SDNode *
N) {
17048 unsigned Opcode =
N->getOpcode();
17072 EVT MinAssertVT = AssertVT.
bitsLT(BigA_AssertVT) ? AssertVT : BigA_AssertVT;
17087 if (AssertVT.
bitsLT(BigA_AssertVT)) {
17105 if (AssertVT.
bitsLT(BigA_AssertVT) &&
17125SDValue DAGCombiner::visitAssertAlign(SDNode *
N) {
17135 std::max(AL, AAN->getAlign()));
17146 unsigned AlignShift =
Log2(AL);
17151 if (LHSAlignShift >= AlignShift || RHSAlignShift >= AlignShift) {
17152 if (LHSAlignShift < AlignShift)
17154 if (RHSAlignShift < AlignShift)
17165SDValue DAGCombiner::visitIS_FPCLASS(SDNode *
N) {
17168 EVT VT =
N->getValueType(0);
17178 if ((~Mask &
Known.getKnownFPClasses()) ==
fcNone)
17184 if ((Mask &
Known.getKnownFPClasses()) != Mask) {
17197SDValue DAGCombiner::reduceLoadWidth(SDNode *
N) {
17198 unsigned Opc =
N->getOpcode();
17202 EVT VT =
N->getValueType(0);
17212 unsigned ShAmt = 0;
17217 unsigned ShiftedOffset = 0;
17237 uint64_t MemoryWidth = LN->getMemoryVT().getScalarSizeInBits();
17238 if (MemoryWidth <= ShAmt)
17249 LN->getExtensionType() != ExtType)
17258 unsigned ActiveBits = 0;
17259 if (
Mask.isMask()) {
17260 ActiveBits =
Mask.countr_one();
17261 }
else if (
Mask.isShiftedMask(ShAmt, ActiveBits)) {
17262 ShiftedOffset = ShAmt;
17283 if (!
SRL.hasOneUse())
17296 ShAmt = SRL1C->getZExtValue();
17297 uint64_t MemoryWidth = LN->getMemoryVT().getSizeInBits();
17298 if (ShAmt >= MemoryWidth)
17323 SDNode *
Mask = *(
SRL->user_begin());
17326 unsigned Offset, ActiveBits;
17327 const APInt& ShiftMask =
Mask->getConstantOperandAPInt(1);
17328 if (ShiftMask.
isMask()) {
17334 LN->getAddressSpace(), ExtType,
false))
17344 LN->getAddressSpace(), ExtType,
false)) {
17352 N0 =
SRL.getOperand(0);
17360 unsigned ShLeftAmt = 0;
17364 ShLeftAmt = N01->getZExtValue();
17385 !isLegalNarrowLdSt(LN0, ExtType, ExtVT, ShAmt))
17391 if (FreezeNode && !FreezeNode.
hasOneUse() &&
17397 auto AdjustBigEndianShift = [&](
unsigned ShAmt) {
17398 unsigned LVTStoreBits =
17401 return LVTStoreBits - EVTStoreBits - ShAmt;
17406 unsigned PtrAdjustmentInBits =
17409 uint64_t PtrOff = PtrAdjustmentInBits / 8;
17415 AddToWorklist(NewPtr.
getNode());
17419 const MDNode *OldRanges = LN0->
getRanges();
17420 const MDNode *NewRanges =
nullptr;
17424 if (ShAmt == 0 && OldRanges) {
17432 ConstantRange TruncatedCR = CR.
truncate(BitSize);
17442 NewRanges = OldRanges;
17456 WorklistRemover DeadNodes(*
this);
17460 if (FreezeNode && !FreezeNode.
hasOneUse())
17477 if (ShLeftAmt != 0) {
17489 if (ShiftedOffset != 0) {
17503SDValue DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *
N) {
17506 EVT VT =
N->getValueType(0);
17537 if ((N00Bits <= ExtVTBits ||
17550 if ((N00Bits == ExtVTBits ||
17551 (!IsZext && (N00Bits < ExtVTBits ||
17553 (!LegalOperations ||
17578 if (
SDValue NarrowLoad = reduceLoadWidth(
N))
17586 if (ShAmt->getAPIntValue().ule(VTBits - ExtVTBits)) {
17590 if (((VTBits - ExtVTBits) - ShAmt->getZExtValue()) < InSignBits)
17609 CombineTo(
N, ExtLoad);
17611 AddToWorklist(ExtLoad.
getNode());
17621 ((!LegalOperations && LN0->
isSimple()) &&
17627 CombineTo(
N, ExtLoad);
17637 if (ExtVT == Ld->getMemoryVT() && Ld->hasNUsesOfValue(1, 0) &&
17639 TLI.
isLoadLegal(VT, ExtVT, Ld->getAlign(), Ld->getAddressSpace(),
17642 VT,
DL, Ld->getChain(), Ld->getBasePtr(), Ld->getOffset(),
17643 Ld->getMask(), Ld->getPassThru(), ExtVT, Ld->getMemOperand(),
17644 Ld->getAddressingMode(),
ISD::SEXTLOAD, Ld->isExpandingLoad());
17645 CombineTo(
N, Frozen ? N0 : ExtMaskedLoad);
17646 CombineTo(Ld, ExtMaskedLoad, ExtMaskedLoad.
getValue(1));
17653 if (
SDValue(GN0, 0).hasOneUse() && ExtVT == GN0->getMemoryVT() &&
17655 SDValue Ops[] = {GN0->getChain(), GN0->getPassThru(), GN0->getMask(),
17656 GN0->getBasePtr(), GN0->getIndex(), GN0->getScale()};
17659 DAG.
getVTList(VT, MVT::Other), ExtVT,
DL,
Ops, GN0->getMemOperand(),
17662 CombineTo(
N, ExtLoad);
17664 AddToWorklist(ExtLoad.
getNode());
17687 (!LegalOperations ||
17701 bool LegalOperations) {
17702 unsigned InregOpcode =
N->getOpcode();
17706 EVT VT =
N->getValueType(0);
17708 *DAG.
getContext(), Src.getValueType().getVectorElementType());
17711 "Expected EXTEND_VECTOR_INREG dag node in input!");
17720 Src = Src.getOperand(0);
17721 if (Src.getValueType() != SrcVT)
17724 if (LegalOperations && !
TLI.isOperationLegal(Opcode, VT))
17727 return DAG.
getNode(Opcode,
DL, VT, Src);
17730SDValue DAGCombiner::visitEXTEND_VECTOR_INREG(SDNode *
N) {
17732 EVT VT =
N->getValueType(0);
17756SDValue DAGCombiner::visitTRUNCATE_USAT_U(SDNode *
N) {
17757 EVT VT =
N->getValueType(0);
17778 unsigned NumSrcBits = In.getScalarValueSizeInBits();
17780 assert(NumSrcBits > NumDstBits &&
"Unexpected types for truncate operation");
17801 unsigned NumSrcBits = In.getScalarValueSizeInBits();
17803 assert(NumSrcBits > NumDstBits &&
"Unexpected types for truncate operation");
17824 unsigned NumSrcBits = In.getScalarValueSizeInBits();
17826 assert(NumSrcBits > NumDstBits &&
"Unexpected types for truncate operation");
17849 auto AllowedTruncateSat = [&](
unsigned Opc,
EVT SrcVT,
EVT VT) ->
bool {
17850 return (
TLI.isOperationLegalOrCustom(
Opc, SrcVT) &&
17851 TLI.isTypeDesirableForOp(
Opc, VT));
17861 }
else if (Src.getOpcode() ==
ISD::UMIN) {
17873SDValue DAGCombiner::visitTRUNCATE(SDNode *
N) {
17875 EVT VT =
N->getValueType(0);
17890 return SaturatedTR;
17943 if (LegalTypes && !LegalOperations && VT.
isScalarInteger() && VT != MVT::i1 &&
17945 EVT TrTy =
N->getValueType(0);
17950 if (Src.getOpcode() ==
ISD::SRL && Src.getOperand(0)->hasOneUse()) {
17953 Src = Src.getOperand(0);
17960 EVT VecTy = Src.getOperand(0).getValueType();
17961 EVT ExTy = Src.getValueType();
17965 auto NewEltCnt = EltCnt * SizeRatio;
17970 SDValue EltNo = Src->getOperand(1);
17973 int Index = isLE ? (Elt * SizeRatio + EltOffset)
17974 : (Elt * SizeRatio + (SizeRatio - 1) - EltOffset);
17985 if (!LegalOperations ||
18008 AddToWorklist(Amt.
getNode());
18058 if (BuildVectEltTy == TruncVecEltTy) {
18062 unsigned TruncEltOffset = BuildVecNumElts / TruncVecNumElts;
18063 unsigned FirstElt = isLE ? 0 : (TruncEltOffset - 1);
18065 assert((BuildVecNumElts % TruncVecNumElts) == 0 &&
18066 "Invalid number of elements");
18069 for (
unsigned i = FirstElt, e = BuildVecNumElts; i <
e;
18070 i += TruncEltOffset)
18080 if (
SDValue Reduced = reduceLoadWidth(
N))
18103 unsigned NumDefs = 0;
18107 if (!
X.isUndef()) {
18124 if (NumDefs == 1) {
18125 assert(
V.getNode() &&
"The single defined operand is empty!");
18127 for (
unsigned i = 0, e = VTs.
size(); i != e; ++i) {
18133 AddToWorklist(
NV.getNode());
18148 (!LegalOperations ||
18176 if (
SDValue NewVSel = matchVSelectOpSizesWithSetCC(
N))
18190 if (!LegalOperations && N0.
hasOneUse() &&
18207 Flags.setNoUnsignedWrap(
true);
18232 if (!LegalOperations && N0.
hasOneUse() &&
18273 if (!LegalOperations && N0.
hasOneUse() &&
18281 bool CanFold =
false;
18289 unsigned NeededBits = SrcBits - TruncBits;
18315SDValue DAGCombiner::CombineConsecutiveLoads(SDNode *
N, EVT VT) {
18328 !LD1->hasOneUse() || !LD2->hasOneUse() ||
18329 LD1->getAddressSpace() != LD2->getAddressSpace())
18332 unsigned LD1Fast = 0;
18333 EVT LD1VT = LD1->getValueType(0);
18338 *LD1->getMemOperand(), &LD1Fast) && LD1Fast)
18340 VT, SDLoc(
N), LD1->getChain(), LD1->getBasePtr(), LD1->getPointerInfo(),
18342 MMOMetadata(AAMDNodes(),
nullptr, getCommonMemCacheHint({LD1, LD2})));
18353SDValue DAGCombiner::foldBitcastedFPLogic(SDNode *
N, SelectionDAG &DAG,
18357 EVT VT =
N->getValueType(0);
18394 auto IsBitCastOrFree = [&
TLI, FPOpcode](
SDValue Op, EVT VT) {
18408 IsBitCastOrFree(LogicOp0, VT)) {
18411 NumFPLogicOpsConv++;
18420SDValue DAGCombiner::visitBITCAST(SDNode *
N) {
18422 EVT VT =
N->getValueType(0);
18447 if (!LegalOperations ||
18453 if (
C.getNode() !=
N)
18466 auto IsFreeBitcast = [VT](
SDValue V) {
18468 V.getOperand(0).getValueType() == VT) ||
18481 auto CastLoad = [
this, &VT](
SDValue N0,
const SDLoc &
DL) {
18503 if ((LegalOperations || !LN0->
isSimple()) &&
18513 if (
const MDNode *MD = LN0->
getRanges()) {
18525 if (
SDValue NewLd = CastLoad(N0, SDLoc(
N)))
18552 AddToWorklist(NewConv.
getNode());
18555 if (N0.
getValueType() == MVT::ppcf128 && !LegalTypes) {
18562 AddToWorklist(FlipBit.
getNode());
18569 AddToWorklist(
Hi.getNode());
18571 AddToWorklist(FlipBit.
getNode());
18575 AddToWorklist(FlipBits.
getNode());
18605 AddToWorklist(
X.getNode());
18609 if (OrigXWidth < VTWidth) {
18611 AddToWorklist(
X.getNode());
18612 }
else if (OrigXWidth > VTWidth) {
18617 X.getValueType(),
X,
18619 X.getValueType()));
18620 AddToWorklist(
X.getNode());
18622 AddToWorklist(
X.getNode());
18625 if (N0.
getValueType() == MVT::ppcf128 && !LegalTypes) {
18628 AddToWorklist(Cst.
getNode());
18630 AddToWorklist(
X.getNode());
18632 AddToWorklist(XorResult.
getNode());
18636 SDLoc(XorResult)));
18637 AddToWorklist(XorResult64.
getNode());
18640 DAG.
getConstant(SignBit, SDLoc(XorResult64), MVT::i64));
18641 AddToWorklist(FlipBit.
getNode());
18644 AddToWorklist(FlipBits.
getNode());
18650 AddToWorklist(
X.getNode());
18655 AddToWorklist(Cst.
getNode());
18663 if (
SDValue CombineLD = CombineConsecutiveLoads(N0.
getNode(), VT))
18693 auto PeekThroughBitcast = [&](
SDValue Op) {
18695 Op.getOperand(0).getValueType() == VT)
18712 SmallVector<int, 8> NewMask;
18714 for (
int i = 0; i != MaskScale; ++i)
18715 NewMask.
push_back(M < 0 ? -1 : M * MaskScale + i);
18720 return LegalShuffle;
18726SDValue DAGCombiner::visitBUILD_PAIR(SDNode *
N) {
18727 EVT VT =
N->getValueType(0);
18728 return CombineConsecutiveLoads(
N, VT);
18731SDValue DAGCombiner::visitFREEZE(SDNode *
N) {
18742 while (!
N->use_empty())
18747 assert(
N->getOperand(0) == FrozenN0 &&
"Expected cycle in DAG");
18777 bool AllowMultipleMaybePoisonOperands =
18805 SmallSet<SDValue, 8> MaybePoisonOperands;
18806 SmallVector<unsigned, 8> MaybePoisonOperandNumbers;
18811 bool HadMaybePoisonOperands = !MaybePoisonOperands.
empty();
18812 bool IsNewMaybePoisonOperand = MaybePoisonOperands.
insert(
Op).second;
18813 if (IsNewMaybePoisonOperand)
18814 MaybePoisonOperandNumbers.
push_back(OpNo);
18815 if (!HadMaybePoisonOperands)
18817 if (IsNewMaybePoisonOperand && !AllowMultipleMaybePoisonOperands) {
18826 for (
unsigned OpNo : MaybePoisonOperandNumbers) {
18837 SDValue MaybePoisonOperand =
N->getOperand(0).getOperand(OpNo);
18839 if (MaybePoisonOperand.
isUndef())
18846 FrozenMaybePoisonOperand.
getOperand(0) == FrozenMaybePoisonOperand) {
18850 MaybePoisonOperand);
18886 SDNodeFlags SrcFlags = N0->
getFlags();
18887 SDNodeFlags SafeFlags;
18900 return N->getFlags().hasAllowContract();
18904SDValue DAGCombiner::visitFADDForFMACombine(SDNode *
N) {
18907 EVT VT =
N->getValueType(0);
18919 if (!HasFMAD && !HasFMA)
18924 bool AllowFusionGlobally = HasFMAD;
18926 if (!AllowFusionGlobally && !
N->getFlags().hasAllowContract())
18944 unsigned Opcode =
N.getOpcode();
18953 return AllowFusionGlobally ||
N->getFlags().hasAllowContract();
18983 bool CanReassociate =
N->getFlags().hasAllowReassociation();
18984 if (CanReassociate) {
18989 }
else if (isFusedOp(N1) && N1.
hasOneUse()) {
18995 while (
E && isFusedOp(TmpFMA) && TmpFMA.
hasOneUse()) {
19019 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19033 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19046 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X,
Y,
19047 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19052 if (isFusedOp(N0)) {
19076 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19082 if (isFusedOp(N00)) {
19096 if (isFusedOp(N1)) {
19117 if (isFusedOp(N10)) {
19134SDValue DAGCombiner::visitFSUBForFMACombine(SDNode *
N) {
19137 EVT VT =
N->getValueType(0);
19149 if (!HasFMAD && !HasFMA)
19152 const SDNodeFlags
Flags =
N->getFlags();
19155 bool AllowFusionGlobally = HasFMAD;
19158 if (!AllowFusionGlobally && !
N->getFlags().hasAllowContract())
19167 bool NoSignedZero =
Flags.hasNoSignedZeros();
19174 return AllowFusionGlobally ||
N->getFlags().hasAllowContract();
19190 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19202 if (
SDValue V = tryToFoldXSubYZ(N0, N1))
19205 if (
SDValue V = tryToFoldXYSubZ(N0, N1))
19209 if (
SDValue V = tryToFoldXYSubZ(N0, N1))
19212 if (
SDValue V = tryToFoldXSubYZ(N0, N1))
19221 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19235 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19251 PreferredFusedOpcode, SL, VT,
19273 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19296 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19309 unsigned Opcode =
N.getOpcode();
19314 if (
Aggressive &&
N->getFlags().hasAllowReassociation()) {
19315 bool CanFuse =
N->getFlags().hasAllowContract();
19318 if (CanFuse && isFusedOp(N0) &&
19319 isContractableAndReassociableFMUL(N0.
getOperand(2)) &&
19323 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19331 if (CanFuse && isFusedOp(N1) &&
19332 isContractableAndReassociableFMUL(N1.
getOperand(2)) &&
19337 PreferredFusedOpcode, SL, VT,
19339 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19345 if (isFusedOp(N0) && N0->
hasOneUse()) {
19349 if (isContractableAndReassociableFMUL(N020) &&
19355 PreferredFusedOpcode, SL, VT,
19371 if (isFusedOp(N00)) {
19373 if (isContractableAndReassociableFMUL(N002) &&
19377 PreferredFusedOpcode, SL, VT,
19381 PreferredFusedOpcode, SL, VT,
19394 if (isContractableAndReassociableFMUL(N120) &&
19400 PreferredFusedOpcode, SL, VT,
19402 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19420 if (isContractableAndReassociableFMUL(N102) &&
19426 PreferredFusedOpcode, SL, VT,
19430 DAG.
getNode(PreferredFusedOpcode, SL, VT,
19444SDValue DAGCombiner::visitFMULForFMADistributiveCombine(SDNode *
N) {
19447 EVT VT =
N->getValueType(0);
19455 if (!
FAdd->getFlags().hasNoInfs())
19469 if (!HasFMAD && !HasFMA)
19482 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X.getOperand(0),
Y,
19484 if (
C->isMinusOne())
19485 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X.getOperand(0),
Y,
19492 if (
SDValue FMA = FuseFADD(N0, N1))
19494 if (
SDValue FMA = FuseFADD(N1, N0))
19505 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19508 if (
C0->isMinusOne())
19509 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
19515 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X.getOperand(0),
Y,
19517 if (
C1->isMinusOne())
19518 return DAG.
getNode(PreferredFusedOpcode, SL, VT,
X.getOperand(0),
Y,
19525 if (
SDValue FMA = FuseFSUB(N0, N1))
19527 if (
SDValue FMA = FuseFSUB(N1, N0))
19533SDValue DAGCombiner::visitFADD(SDNode *
N) {
19538 EVT VT =
N->getValueType(0);
19540 SDNodeFlags
Flags =
N->getFlags();
19541 SelectionDAG::FlagInserter FlagsInserter(DAG,
N);
19552 if (N0CFP && !N1CFP)
19557 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
19562 if (N1C && N1C->
isZero())
19567 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
19573 N1, DAG, LegalOperations, ForCodeSize))
19579 N0, DAG, LegalOperations, ForCodeSize))
19586 return C &&
C->isExactlyValue(-2.0);
19590 if (isFMulNegTwo(N0)) {
19596 if (isFMulNegTwo(N1)) {
19607 if (
Flags.hasNoNaNs() && AllowNewConst) {
19620 if (
Flags.hasAllowReassociation() &&
Flags.hasNoSignedZeros() &&
19633 !N0CFP && !N1CFP) {