87#define DEBUG_TYPE "dagcombine"
89STATISTIC(NodesCombined ,
"Number of dag nodes combined");
90STATISTIC(PreIndexedNodes ,
"Number of pre-indexed nodes created");
91STATISTIC(PostIndexedNodes,
"Number of post-indexed nodes created");
92STATISTIC(OpsNarrowed ,
"Number of load/op/store narrowed");
93STATISTIC(LdStFP2Int ,
"Number of fp load/store pairs transformed to int");
95STATISTIC(NumFPLogicOpsConv,
"Number of logic ops converted to fp ops");
98 "Controls whether a DAG combine is performed for a node");
102 cl::desc(
"Enable DAG combiner's use of IR alias analysis"));
106 cl::desc(
"Enable DAG combiner's use of TBAA"));
111 cl::desc(
"Only use DAG-combiner alias analysis in this"
119 cl::desc(
"Bypass the profitability model of load slicing"),
124 cl::desc(
"DAG combiner may split indexing from loads"));
128 cl::desc(
"DAG combiner enable merging multiple stores "
129 "into a wider store"));
133 cl::desc(
"Limit the number of operands to inline for Token Factors"));
137 cl::desc(
"Limit the number of times for the same StoreNode and RootNode "
138 "to bail out in store merging dependence check"));
142 cl::desc(
"DAG combiner enable reducing the width of load/op/store "
145 "combiner-reduce-load-op-store-width-force-narrowing-profitable",
147 cl::desc(
"DAG combiner force override the narrowing profitable check when "
148 "reducing the width of load/op/store sequences"));
152 cl::desc(
"DAG combiner enable load/<replace bytes>/store with "
153 "a narrower store"));
157 cl::desc(
"DAG combiner nodes consistently processed in topological order"));
161 cl::desc(
"Disable the DAG combiner"));
171 bool LegalDAG =
false;
172 bool LegalOperations =
false;
173 bool LegalTypes =
false;
175 bool DisableGenericCombines;
211 void AddUsersToWorklist(
SDNode *
N) {
217 void AddToWorklistWithUsers(SDNode *
N) {
218 AddUsersToWorklist(
N);
225 void clearAddedDanglingWorklistEntries() {
227 while (!PruningList.empty()) {
228 auto *
N = PruningList.pop_back_val();
230 recursivelyDeleteUnusedNodes(
N);
234 SDNode *getNextWorklistEntry() {
236 clearAddedDanglingWorklistEntries();
240 while (!
N && !Worklist.empty()) {
241 N = Worklist.pop_back_val();
245 assert(
N->getCombinerWorklistIndex() >= 0 &&
246 "Found a worklist entry without a corresponding map entry!");
248 N->setCombinerWorklistIndex(-2);
258 : DAG(
D), TLI(
D.getTargetLoweringInfo()),
259 STI(
D.getSubtarget().getSelectionDAGInfo()), OptLevel(OL),
261 ForCodeSize = DAG.shouldOptForSize();
262 DisableGenericCombines =
266 void ConsiderForPruning(SDNode *
N) {
268 PruningList.insert(
N);
273 void AddToWorklist(SDNode *
N,
bool IsCandidateForPruning =
true,
274 bool SkipIfCombinedBefore =
false) {
276 "Deleted Node added to Worklist");
283 if (SkipIfCombinedBefore &&
N->getCombinerWorklistIndex() == -2)
286 if (IsCandidateForPruning)
287 ConsiderForPruning(
N);
289 if (
N->getCombinerWorklistIndex() < 0) {
290 N->setCombinerWorklistIndex(Worklist.size());
291 Worklist.push_back(
N);
296 void removeFromWorklist(SDNode *
N) {
297 PruningList.remove(
N);
298 StoreRootCountMap.erase(
N);
300 int WorklistIndex =
N->getCombinerWorklistIndex();
304 if (WorklistIndex < 0)
308 Worklist[WorklistIndex] =
nullptr;
309 N->setCombinerWorklistIndex(-1);
312 void deleteAndRecombine(SDNode *
N);
313 bool recursivelyDeleteUnusedNodes(SDNode *
N);
321 return CombineTo(
N, &Res, 1, AddTo);
328 return CombineTo(
N, To, 2, AddTo);
331 SDValue CombineTo(SDNode *
N, SmallVectorImpl<SDValue> *To,
333 return CombineTo(
N, To->
data(), To->
size(), AddTo);
336 void CommitTargetLoweringOpt(
const TargetLowering::TargetLoweringOpt &TLO);
343 unsigned BitWidth =
Op.getScalarValueSizeInBits();
345 return SimplifyDemandedBits(
Op, DemandedBits);
348 bool SimplifyDemandedBits(
SDValue Op,
const APInt &DemandedBits) {
349 EVT VT =
Op.getValueType();
353 return SimplifyDemandedBits(
Op, DemandedBits, DemandedElts,
false);
359 bool SimplifyDemandedVectorElts(
SDValue Op) {
361 if (
Op.getValueType().isScalableVector())
364 unsigned NumElts =
Op.getValueType().getVectorNumElements();
366 return SimplifyDemandedVectorElts(
Op, DemandedElts);
369 bool SimplifyDemandedBits(
SDValue Op,
const APInt &DemandedBits,
370 const APInt &DemandedElts,
371 bool AssumeSingleUse =
false);
372 bool SimplifyDemandedVectorElts(
SDValue Op,
const APInt &DemandedElts,
373 bool AssumeSingleUse =
false);
375 bool CombineToPreIndexedLoadStore(SDNode *
N);
376 bool CombineToPostIndexedLoadStore(SDNode *
N);
377 SDValue SplitIndexingFromLoad(LoadSDNode *LD);
378 bool SliceUpLoad(SDNode *
N);
384 StoreSDNode *getUniqueStoreFeeding(LoadSDNode *LD, int64_t &
Offset);
386 SDValue ForwardStoreValueToDirectLoad(LoadSDNode *LD);
387 bool getTruncatedStoreValue(StoreSDNode *ST,
SDValue &Val);
388 bool extendLoadedValueToExtension(LoadSDNode *LD,
SDValue &Val);
390 void ReplaceLoadWithPromotedLoad(SDNode *
Load, SDNode *ExtLoad);
399 SDValue foldShiftToAvg(SDNode *
N,
const SDLoc &
DL);
401 SDValue foldBitwiseOpWithNeg(SDNode *
N,
const SDLoc &
DL, EVT VT);
419 SDValue visitTokenFactor(SDNode *
N);
420 SDValue visitMERGE_VALUES(SDNode *
N);
434 SDValue visitUADDO_CARRY(SDNode *
N);
435 SDValue visitSADDO_CARRY(SDNode *
N);
441 SDValue visitUSUBO_CARRY(SDNode *
N);
442 SDValue visitSSUBO_CARRY(SDNode *
N);
464 SDValue SimplifyVCastOp(SDNode *
N,
const SDLoc &
DL);
465 SDValue SimplifyVBinOp(SDNode *
N,
const SDLoc &
DL);
469 SDValue visitFunnelShift(SDNode *
N);
473 SDValue visitABS_MIN_POISON(SDNode *
N);
480 SDValue visitCTLZ_ZERO_POISON(SDNode *
N);
482 SDValue visitCTTZ_ZERO_POISON(SDNode *
N);
489 SDValue visitSIGN_EXTEND(SDNode *
N);
490 SDValue visitZERO_EXTEND(SDNode *
N);
493 SDValue visitAssertAlign(SDNode *
N);
495 SDValue visitSIGN_EXTEND_INREG(SDNode *
N);
496 SDValue visitEXTEND_VECTOR_INREG(SDNode *
N);
498 SDValue visitTRUNCATE_USAT_U(SDNode *
N);
503 SDValue visitSTRICT_FADD(SDNode *
N);
514 SDValue visitFCANONICALIZE(SDNode *
N);
534 SDValue replaceStoreOfFPConstant(StoreSDNode *ST);
535 SDValue replaceStoreOfInsertLoad(StoreSDNode *ST);
537 bool refineExtractVectorEltIntoMultipleNarrowExtractVectorElts(SDNode *
N);
538 SDValue combineStoreConcatTruncVector(StoreSDNode *
N);
540 SDValue visitATOMIC_STORE(SDNode *
N);
541 SDValue visitLIFETIME_END(SDNode *
N);
542 SDValue visitINSERT_VECTOR_ELT(SDNode *
N);
543 SDValue visitEXTRACT_VECTOR_ELT(SDNode *
N);
544 SDValue visitBUILD_VECTOR(SDNode *
N);
545 SDValue visitCONCAT_VECTORS(SDNode *
N);
546 SDValue visitVECTOR_INTERLEAVE(SDNode *
N);
547 SDValue visitEXTRACT_SUBVECTOR(SDNode *
N);
548 SDValue visitVECTOR_SHUFFLE(SDNode *
N);
549 SDValue visitSCALAR_TO_VECTOR(SDNode *
N);
550 SDValue visitINSERT_SUBVECTOR(SDNode *
N);
551 SDValue visitVECTOR_COMPRESS(SDNode *
N);
557 SDValue visitPARTIAL_REDUCE_MLA(SDNode *
N);
558 SDValue visitLOOP_DEPENDENCE_MASK(SDNode *
N);
561 SDValue visitVP_STRIDED_LOAD(SDNode *
N);
562 SDValue visitVP_STRIDED_STORE(SDNode *
N);
569 SDValue visitGET_FPENV_MEM(SDNode *
N);
570 SDValue visitSET_FPENV_MEM(SDNode *
N);
572 SDValue visitFADDForFMACombine(SDNode *
N);
573 SDValue visitFSUBForFMACombine(SDNode *
N);
574 SDValue visitFMULForFMADistributiveCombine(SDNode *
N);
576 SDValue XformToShuffleWithZero(SDNode *
N);
577 bool reassociationCanBreakAddressingModePattern(
unsigned Opc,
583 SDValue N1, SDNodeFlags Flags);
585 SDValue N1, SDNodeFlags Flags);
586 SDValue reassociateReduction(
unsigned RedOpc,
unsigned Opc,
const SDLoc &
DL,
588 SDNodeFlags Flags = SDNodeFlags());
590 SDValue visitShiftByConstant(SDNode *
N);
592 SDValue foldSelectOfConstants(SDNode *
N);
593 SDValue foldVSelectOfConstants(SDNode *
N);
594 SDValue foldBinOpIntoSelect(SDNode *BO);
596 SDValue hoistLogicOpWithSameOpcodeHands(SDNode *
N);
600 bool NotExtCompare =
false);
601 SDValue convertSelectOfFPConstantsToLoadOffset(
604 SDValue foldSignChangeInBitcast(SDNode *
N);
607 SDValue foldSelectOfBinops(SDNode *
N);
611 SDValue foldSubToUSubSat(EVT DstVT, SDNode *
N,
const SDLoc &
DL);
612 SDValue foldABSToABD(SDNode *
N,
const SDLoc &
DL);
617 SDValue unfoldMaskedMerge(SDNode *
N);
618 SDValue unfoldExtremeBitClearingToShifts(SDNode *
N);
620 const SDLoc &
DL,
bool foldBooleans);
624 SDValue &CC,
bool MatchStrict =
false)
const;
625 bool isOneUseSetCC(
SDValue N)
const;
627 SDValue foldAddToAvg(SDNode *
N,
const SDLoc &
DL);
628 SDValue foldSubToAvg(SDNode *
N,
const SDLoc &
DL);
632 SDValue SimplifyNodeWithTwoResults(SDNode *
N,
unsigned LoOp,
634 SDValue CombineConsecutiveLoads(SDNode *
N, EVT VT);
635 SDValue foldBitcastedFPLogic(SDNode *
N, SelectionDAG &DAG,
636 const TargetLowering &TLI);
637 SDValue foldPartialReduceMLAMulOp(SDNode *
N);
638 SDValue foldPartialReduceAdd(SDNode *
N);
641 SDValue CombineZExtLogicopShiftLoad(SDNode *
N);
642 SDValue combineRepeatedFPDivisors(SDNode *
N);
643 SDValue combineFMulOrFDivWithIntPow2(SDNode *
N);
644 SDValue replaceShuffleOfInsert(ShuffleVectorSDNode *Shuf);
645 SDValue mergeInsertEltWithShuffle(SDNode *
N,
unsigned InsIndex);
646 SDValue combineInsertEltToShuffle(SDNode *
N,
unsigned InsIndex);
647 SDValue combineInsertEltToLoad(SDNode *
N,
unsigned InsIndex);
657 bool KnownNeverZero =
false,
658 bool InexpensiveOnly =
false,
659 std::optional<EVT> OutVT = std::nullopt);
669 bool DemandHighBits =
true);
673 bool HasPos,
unsigned PosOpcode,
674 unsigned NegOpcode,
const SDLoc &
DL);
677 bool HasPos,
unsigned PosOpcode,
678 unsigned NegOpcode,
const SDLoc &
DL);
681 SDValue MatchLoadCombine(SDNode *
N);
682 SDValue mergeTruncStores(StoreSDNode *
N);
684 SDValue ReduceLoadOpStoreWidth(SDNode *
N);
686 SDValue TransformFPLoadStorePair(SDNode *
N);
687 SDValue convertBuildVecExtToExt(SDNode *
N);
688 SDValue convertBuildVecZextToBuildVecWithZeros(SDNode *
N);
689 SDValue reduceBuildVecExtToExtBuildVec(SDNode *
N);
690 SDValue reduceBuildVecTruncToBitCast(SDNode *
N);
691 SDValue reduceBuildVecToShuffle(SDNode *
N);
692 SDValue createBuildVecShuffle(
const SDLoc &
DL, SDNode *
N,
693 ArrayRef<int> VectorMask,
SDValue VecIn1,
694 SDValue VecIn2,
unsigned LeftIdx,
696 SDValue matchVSelectOpSizesWithSetCC(SDNode *Cast);
700 void GatherAllAliases(SDNode *
N,
SDValue OriginalChain,
701 SmallVectorImpl<SDValue> &Aliases);
704 bool mayAlias(SDNode *Op0, SDNode *Op1)
const;
716 bool findBetterNeighborChains(StoreSDNode *St);
720 bool parallelizeChainedStores(StoreSDNode *St);
726 LSBaseSDNode *MemNode;
729 int64_t OffsetFromBase;
731 MemOpLink(LSBaseSDNode *
N, int64_t
Offset)
732 : MemNode(
N), OffsetFromBase(
Offset) {}
737 StoreSource getStoreSource(
SDValue StoreVal) {
741 return StoreSource::Constant;
745 return StoreSource::Constant;
746 return StoreSource::Unknown;
749 return StoreSource::Extract;
751 return StoreSource::Load;
753 return StoreSource::Unknown;
761 bool isMulAddWithConstProfitable(SDNode *MulNode,
SDValue AddNode,
767 bool isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
768 EVT LoadResultTy, EVT &ExtVT);
773 EVT &MemVT,
unsigned ShAmt = 0);
776 bool SearchForAndLoads(SDNode *
N, SmallVectorImpl<LoadSDNode*> &Loads,
777 SmallPtrSetImpl<SDNode*> &NodesWithConsts,
778 ConstantSDNode *Mask, SDNode *&NodeToMask);
781 bool BackwardsPropagateMask(SDNode *
N);
785 SDValue getMergeStoreChains(SmallVectorImpl<MemOpLink> &StoreNodes,
797 bool mergeStoresOfConstantsOrVecElts(SmallVectorImpl<MemOpLink> &StoreNodes,
798 EVT MemVT,
unsigned NumStores,
799 bool IsConstantSrc,
bool UseVector,
805 SDNode *getStoreMergeCandidates(StoreSDNode *St,
806 SmallVectorImpl<MemOpLink> &StoreNodes);
812 bool checkMergeStoreCandidatesForDependencies(
813 SmallVectorImpl<MemOpLink> &StoreNodes,
unsigned NumStores,
818 bool hasCallInLdStChain(StoreSDNode *St, LoadSDNode *Ld);
823 unsigned getConsecutiveStores(SmallVectorImpl<MemOpLink> &StoreNodes,
824 int64_t ElementSizeBytes)
const;
828 bool tryStoreMergeOfConstants(SmallVectorImpl<MemOpLink> &StoreNodes,
829 unsigned NumConsecutiveStores,
830 EVT MemVT, SDNode *Root,
bool AllowVectors);
836 bool tryStoreMergeOfExtracts(SmallVectorImpl<MemOpLink> &StoreNodes,
837 unsigned NumConsecutiveStores, EVT MemVT,
842 bool tryStoreMergeOfLoads(SmallVectorImpl<MemOpLink> &StoreNodes,
843 unsigned NumConsecutiveStores, EVT MemVT,
844 SDNode *Root,
bool AllowVectors,
845 bool IsNonTemporalStore,
bool IsNonTemporalLoad);
850 bool mergeConsecutiveStores(StoreSDNode *St);
858 SDValue distributeTruncateThroughAnd(SDNode *
N);
864 bool hasOperation(
unsigned Opcode, EVT VT) {
865 return TLI.isOperationLegalOrCustom(Opcode, VT, LegalOperations);
868 bool hasUMin(EVT VT)
const {
869 auto LK = TLI.getTypeConversion(*DAG.getContext(), VT);
872 TLI.isOperationLegalOrCustom(
ISD::UMIN, LK.second);
879 SelectionDAG &getDAG()
const {
return DAG; }
882 EVT getShiftAmountTy(EVT LHSTy) {
883 return TLI.getShiftAmountTy(LHSTy, DAG.getDataLayout());
888 bool isTypeLegal(
const EVT &VT) {
889 if (!LegalTypes)
return true;
890 return TLI.isTypeLegal(VT);
894 EVT getSetCCResultType(EVT VT)
const {
895 return TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
898 void ExtendSetCCUses(
const SmallVectorImpl<SDNode *> &SetCCs,
909 explicit WorklistRemover(DAGCombiner &dc)
910 : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
912 void NodeDeleted(SDNode *
N, SDNode *
E)
override {
913 DC.removeFromWorklist(
N);
921 explicit WorklistInserter(DAGCombiner &dc)
922 : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
926 void NodeInserted(SDNode *
N)
override { DC.ConsiderForPruning(
N); }
936 ((DAGCombiner*)
DC)->AddToWorklist(
N);
941 return ((DAGCombiner*)
DC)->CombineTo(
N, &To[0], To.
size(), AddTo);
946 return ((DAGCombiner*)
DC)->CombineTo(
N, Res, AddTo);
951 return ((DAGCombiner*)
DC)->CombineTo(
N, Res0, Res1, AddTo);
956 return ((DAGCombiner*)
DC)->recursivelyDeleteUnusedNodes(
N);
961 return ((DAGCombiner*)
DC)->CommitTargetLoweringOpt(TLO);
968void DAGCombiner::deleteAndRecombine(
SDNode *
N) {
969 removeFromWorklist(
N);
977 if (
Op->hasOneUse() ||
Op->getNumValues() > 1)
978 AddToWorklist(
Op.getNode());
987 unsigned Bits =
Offset + std::max(
LHS.getBitWidth(),
RHS.getBitWidth());
998 SDValue &CC,
bool MatchStrict)
const {
1000 LHS =
N.getOperand(0);
1001 RHS =
N.getOperand(1);
1009 LHS =
N.getOperand(1);
1010 RHS =
N.getOperand(2);
1023 LHS =
N.getOperand(0);
1024 RHS =
N.getOperand(1);
1032bool DAGCombiner::isOneUseSetCC(
SDValue N)
const {
1034 if (isSetCCEquivalent(
N, N0, N1, N2) &&
N->hasOneUse())
1046 MaskForTy = 0xFFULL;
1049 MaskForTy = 0xFFFFULL;
1052 MaskForTy = 0xFFFFFFFFULL;
1070 bool AllowTruncation =
false) {
1072 return !(Const->isOpaque() && NoOpaques);
1075 unsigned BitWidth =
N.getScalarValueSizeInBits();
1080 if (!Const || (Const->isOpaque() && NoOpaques))
1084 if ((AllowTruncation &&
1085 Const->getAPIntValue().getActiveBits() >
BitWidth) ||
1086 (!AllowTruncation && Const->getAPIntValue().getBitWidth() !=
BitWidth))
1108bool DAGCombiner::reassociationCanBreakAddressingModePattern(
unsigned Opc,
1136 : (N1.
getOperand(0).getConstantOperandVal(0) *
1141 ScalableOffset = -ScalableOffset;
1142 if (
all_of(
N->users(), [&](SDNode *Node) {
1143 if (auto *LoadStore = dyn_cast<MemSDNode>(Node);
1144 LoadStore && LoadStore->hasUniqueMemOperand() &&
1145 LoadStore->getBasePtr().getNode() == N) {
1146 TargetLoweringBase::AddrMode AM;
1147 AM.HasBaseReg = true;
1148 AM.ScalableOffset = ScalableOffset;
1149 EVT VT = LoadStore->getMemoryVT();
1150 unsigned AS = LoadStore->getAddressSpace();
1151 Type *AccessTy = VT.getTypeForEVT(*DAG.getContext());
1152 return TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy,
1167 const APInt &C2APIntVal = C2->getAPIntValue();
1175 const APInt &C1APIntVal = C1->getAPIntValue();
1176 const APInt CombinedValueIntVal = C1APIntVal + C2APIntVal;
1179 const int64_t CombinedValue = CombinedValueIntVal.
getSExtValue();
1181 for (SDNode *Node :
N->users()) {
1188 TargetLoweringBase::AddrMode AM;
1190 AM.
BaseOffs = C2APIntVal.getSExtValue();
1192 unsigned AS =
LoadStore->getAddressSpace();
1208 for (SDNode *Node :
N->users()) {
1210 if (!LoadStore || !
LoadStore->hasUniqueMemOperand())
1215 TargetLoweringBase::AddrMode AM;
1217 AM.
BaseOffs = C2APIntVal.getSExtValue();
1219 unsigned AS =
LoadStore->getAddressSpace();
1232SDValue DAGCombiner::reassociateOpsCommutative(
unsigned Opc,
const SDLoc &
DL,
1234 SDNodeFlags Flags) {
1244 SDNodeFlags NewFlags;
1246 Flags.hasNoUnsignedWrap())
1254 return DAG.
getNode(
Opc,
DL, VT, N00, OpNode, NewFlags);
1262 return DAG.
getNode(
Opc,
DL, VT, OpNode, N01, NewFlags);
1272 if (N1 == N00 || N1 == N01)
1318 if (CC1 == CC00 && CC1 != CC01) {
1322 if (CC1 == CC01 && CC1 != CC00) {
1336 SDValue N1, SDNodeFlags Flags) {
1342 if (!
Flags.hasAllowReassociation() || !
Flags.hasNoSignedZeros())
1345 if (
SDValue Combined = reassociateOpsCommutative(
Opc,
DL, N0, N1, Flags))
1347 if (
SDValue Combined = reassociateOpsCommutative(
Opc,
DL, N1, N0, Flags))
1355SDValue DAGCombiner::reassociateReduction(
unsigned RedOpc,
unsigned Opc,
1357 SDValue N1, SDNodeFlags Flags) {
1363 SelectionDAG::FlagInserter FlagsInserter(DAG, Flags);
1381 A.getValueType() ==
C.getValueType() &&
1382 hasOperation(
Opc,
A.getValueType()) &&
1390 SelectionDAG::FlagInserter FlagsInserter(
1414 X.getValueType() !=
Y.getValueType() ||
1415 !hasOperation(
Opc,
X.getValueType()) ||
1419 (!Chain->getFlags().hasAllowReassociation() ||
1423 SelectionDAG::FlagInserter FlagsInserter(
1429 if (
SDValue V = FoldReductionChain(N0, N1))
1431 if (
SDValue V = FoldReductionChain(N1, N0))
1437SDValue DAGCombiner::CombineTo(SDNode *
N,
const SDValue *To,
unsigned NumTo,
1439 assert(
N->getNumValues() == NumTo &&
"Broken CombineTo call!");
1443 dbgs() <<
" and " << NumTo - 1 <<
" other values\n");
1444 for (
unsigned i = 0, e = NumTo; i !=
e; ++i)
1446 N->getValueType(i) == To[i].getValueType()) &&
1447 "Cannot combine value to value of different type!");
1449 WorklistRemover DeadNodes(*
this);
1453 for (
unsigned i = 0, e = NumTo; i !=
e; ++i) {
1455 AddToWorklistWithUsers(To[i].
getNode());
1463 deleteAndRecombine(
N);
1468CommitTargetLoweringOpt(
const TargetLowering::TargetLoweringOpt &TLO) {
1481 recursivelyDeleteUnusedNodes(TLO.
Old.
getNode());
1486bool DAGCombiner::SimplifyDemandedBits(
SDValue Op,
const APInt &DemandedBits,
1487 const APInt &DemandedElts,
1488 bool AssumeSingleUse) {
1489 TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
1496 AddToWorklist(
Op.getNode());
1498 CommitTargetLoweringOpt(TLO);
1505bool DAGCombiner::SimplifyDemandedVectorElts(
SDValue Op,
1506 const APInt &DemandedElts,
1507 bool AssumeSingleUse) {
1508 TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
1509 APInt KnownUndef, KnownZero;
1511 TLO, 0, AssumeSingleUse))
1515 AddToWorklist(
Op.getNode());
1517 CommitTargetLoweringOpt(TLO);
1521void DAGCombiner::ReplaceLoadWithPromotedLoad(SDNode *
Load, SDNode *ExtLoad) {
1523 EVT VT =
Load->getValueType(0);
1532 AddToWorklist(Trunc.
getNode());
1533 recursivelyDeleteUnusedNodes(
Load);
1541 EVT MemVT =
LD->getMemoryVT();
1543 :
LD->getExtensionType();
1546 LD->getChain(),
LD->getBasePtr(),
1547 MemVT,
LD->getMemOperand());
1550 unsigned Opc =
Op.getOpcode();
1554 if (
SDValue Op0 = SExtPromoteOperand(
Op.getOperand(0), PVT))
1558 if (
SDValue Op0 = ZExtPromoteOperand(
Op.getOperand(0), PVT))
1576 EVT OldVT =
Op.getValueType();
1582 AddToWorklist(NewOp.
getNode());
1585 ReplaceLoadWithPromotedLoad(
Op.getNode(), NewOp.
getNode());
1591 EVT OldVT =
Op.getValueType();
1597 AddToWorklist(NewOp.
getNode());
1600 ReplaceLoadWithPromotedLoad(
Op.getNode(), NewOp.
getNode());
1608 if (!LegalOperations)
1611 EVT VT =
Op.getValueType();
1617 unsigned Opc =
Op.getOpcode();
1625 assert(PVT != VT &&
"Don't know what type to promote to!");
1629 bool Replace0 =
false;
1631 SDValue NN0 = PromoteOperand(N0, PVT, Replace0);
1633 bool Replace1 =
false;
1635 SDValue NN1 = PromoteOperand(N1, PVT, Replace1);
1647 Replace1 &= (N0 != N1) && !N1->
hasOneUse();
1650 CombineTo(
Op.getNode(), RV);
1676 if (!LegalOperations)
1679 EVT VT =
Op.getValueType();
1685 unsigned Opc =
Op.getOpcode();
1693 assert(PVT != VT &&
"Don't know what type to promote to!");
1697 SDNodeFlags TruncFlags;
1701 N0 = SExtPromoteOperand(N0, PVT);
1703 N0 = ZExtPromoteOperand(N0, PVT);
1705 if (
Op->getFlags().hasNoUnsignedWrap()) {
1706 N0 = ZExtPromoteOperand(N0, PVT);
1708 }
else if (
Op->getFlags().hasNoSignedWrap()) {
1709 N0 = SExtPromoteOperand(N0, PVT);
1712 N0 = PromoteOperand(N0, PVT,
Replace);
1725 ReplaceLoadWithPromotedLoad(
Op.getOperand(0).getNode(), N0.
getNode());
1735 if (!LegalOperations)
1738 EVT VT =
Op.getValueType();
1744 unsigned Opc =
Op.getOpcode();
1752 assert(PVT != VT &&
"Don't know what type to promote to!");
1757 return DAG.
getNode(
Op.getOpcode(), SDLoc(
Op), VT,
Op.getOperand(0));
1762bool DAGCombiner::PromoteLoad(
SDValue Op) {
1763 if (!LegalOperations)
1769 EVT VT =
Op.getValueType();
1775 unsigned Opc =
Op.getOpcode();
1783 assert(PVT != VT &&
"Don't know what type to promote to!");
1786 SDNode *
N =
Op.getNode();
1788 EVT MemVT =
LD->getMemoryVT();
1790 :
LD->getExtensionType();
1792 LD->getChain(),
LD->getBasePtr(),
1793 MemVT,
LD->getMemOperand());
1802 AddToWorklist(
Result.getNode());
1803 recursivelyDeleteUnusedNodes(
N);
1816bool DAGCombiner::recursivelyDeleteUnusedNodes(SDNode *
N) {
1817 if (!
N->use_empty())
1820 SmallSetVector<SDNode *, 16> Nodes;
1827 if (
N->use_empty()) {
1828 for (
const SDValue &ChildN :
N->op_values())
1829 Nodes.
insert(ChildN.getNode());
1831 removeFromWorklist(
N);
1836 }
while (!Nodes.
empty());
1855 WorklistInserter AddNodes(*
this);
1857 if (UseTopologicalSorting)
1866 if (UseTopologicalSorting) {
1868 AddToWorklist(&Node,
Node.use_empty());
1870 for (SDNode &Node : DAG.
allnodes())
1871 AddToWorklist(&Node,
Node.use_empty());
1877 HandleSDNode Dummy(DAG.
getRoot());
1880 while (SDNode *
N = getNextWorklistEntry()) {
1884 if (recursivelyDeleteUnusedNodes(
N))
1887 WorklistRemover DeadNodes(*
this);
1892 SmallSetVector<SDNode *, 16> UpdatedNodes;
1895 for (SDNode *LN : UpdatedNodes)
1896 AddToWorklistWithUsers(LN);
1908 for (
const SDValue &ChildN :
N->op_values())
1909 AddToWorklist(ChildN.getNode(),
true,
1920 ChainsWithoutMergeableStores.
clear();
1931 "Node was deleted but visit returned new node!");
1939 N->getNumValues() == 1 &&
"Type mismatch");
1949 AddToWorklistWithUsers(RV.
getNode());
1955 recursivelyDeleteUnusedNodes(
N);
1959 DAG.
setRoot(Dummy.getValue());
1963SDValue DAGCombiner::visit(SDNode *
N) {
1965 switch (
N->getOpcode()) {
2116 return visitPARTIAL_REDUCE_MLA(
N);
2119 return visitLOOP_DEPENDENCE_MASK(
N);
2147#define BEGIN_REGISTER_VP_SDNODE(SDOPC, ...) case ISD::SDOPC:
2148#include "llvm/IR/VPIntrinsics.def"
2149 return visitVPOp(
N);
2155SDValue DAGCombiner::combine(SDNode *
N) {
2160 if (!DisableGenericCombines)
2166 "Node was deleted but visit returned NULL!");
2172 TargetLowering::DAGCombinerInfo
2173 DagCombineInfo(DAG, Level,
false,
this);
2181 switch (
N->getOpcode()) {
2189 RV = PromoteIntBinOp(
SDValue(
N, 0));
2194 RV = PromoteIntShiftOp(
SDValue(
N, 0));
2230 if (
unsigned NumOps =
N->getNumOperands()) {
2231 if (
N->getOperand(0).getValueType() == MVT::Other)
2232 return N->getOperand(0);
2233 if (
N->getOperand(
NumOps-1).getValueType() == MVT::Other)
2234 return N->getOperand(
NumOps-1);
2235 for (
unsigned i = 1; i <
NumOps-1; ++i)
2236 if (
N->getOperand(i).getValueType() == MVT::Other)
2237 return N->getOperand(i);
2242SDValue DAGCombiner::visitFCANONICALIZE(SDNode *
N) {
2243 SDValue Operand =
N->getOperand(0);
2255SDValue DAGCombiner::visitTokenFactor(SDNode *
N) {
2258 if (
N->getNumOperands() == 2) {
2260 return N->getOperand(0);
2262 return N->getOperand(1);
2277 AddToWorklist(*(
N->user_begin()));
2281 SmallPtrSet<SDNode*, 16> SeenOps;
2289 for (
unsigned i = 0; i < TFs.
size(); ++i) {
2294 for (
unsigned j = i;
j < TFs.
size();
j++)
2295 Ops.emplace_back(TFs[j], 0);
2302 SDNode *TF = TFs[i];
2305 switch (
Op.getOpcode()) {
2323 if (SeenOps.
insert(
Op.getNode()).second)
2334 for (
unsigned i = 1, e = TFs.
size(); i < e; i++)
2335 AddToWorklist(TFs[i]);
2345 SmallVector<unsigned, 8> OpWorkCount;
2346 SmallPtrSet<SDNode *, 16> SeenChains;
2347 bool DidPruneOps =
false;
2349 unsigned NumLeftToConsider = 0;
2351 Worklist.
push_back(std::make_pair(
Op.getNode(), NumLeftToConsider++));
2355 auto AddToWorklist = [&](
unsigned CurIdx, SDNode *
Op,
unsigned OpNumber) {
2361 unsigned OrigOpNumber = 0;
2362 while (OrigOpNumber <
Ops.size() &&
Ops[OrigOpNumber].getNode() !=
Op)
2365 "expected to find TokenFactor Operand");
2367 for (
unsigned i = CurIdx + 1; i < Worklist.
size(); ++i) {
2368 if (Worklist[i].second == OrigOpNumber) {
2369 Worklist[i].second = OpNumber;
2372 OpWorkCount[OpNumber] += OpWorkCount[OrigOpNumber];
2373 OpWorkCount[OrigOpNumber] = 0;
2374 NumLeftToConsider--;
2377 if (SeenChains.
insert(
Op).second) {
2378 OpWorkCount[OpNumber]++;
2383 for (
unsigned i = 0; i < Worklist.
size() && i < 1024; ++i) {
2385 if (NumLeftToConsider <= 1)
2387 auto CurNode = Worklist[i].first;
2388 auto CurOpNumber = Worklist[i].second;
2389 assert((OpWorkCount[CurOpNumber] > 0) &&
2390 "Node should not appear in worklist");
2391 switch (CurNode->getOpcode()) {
2397 NumLeftToConsider++;
2400 for (
const SDValue &
Op : CurNode->op_values())
2401 AddToWorklist(i,
Op.getNode(), CurOpNumber);
2407 AddToWorklist(i, CurNode->getOperand(0).getNode(), CurOpNumber);
2411 AddToWorklist(i, MemNode->getChain().getNode(), CurOpNumber);
2414 OpWorkCount[CurOpNumber]--;
2415 if (OpWorkCount[CurOpNumber] == 0)
2416 NumLeftToConsider--;
2430 if (SeenChains.
count(
Op.getNode()) == 0)
2444SDValue DAGCombiner::visitMERGE_VALUES(SDNode *
N) {
2445 WorklistRemover DeadNodes(*
this);
2451 AddUsersToWorklist(
N);
2456 }
while (!
N->use_empty());
2457 deleteAndRecombine(
N);
2465 return Const !=
nullptr && !Const->isOpaque() ? Const :
nullptr;
2475 Op =
N->getOperand(0);
2477 if (
N->getFlags().hasNoUnsignedWrap())
2478 Known.Zero.setBitsFrom(
N.getScalarValueSizeInBits());
2482 if (
N.getValueType().getScalarType() != MVT::i1 ||
2499 if (LD->isIndexed() || LD->getBasePtr().getNode() !=
N)
2501 VT = LD->getMemoryVT();
2502 AS = LD->getAddressSpace();
2504 if (ST->isIndexed() || ST->getBasePtr().getNode() !=
N)
2506 VT = ST->getMemoryVT();
2507 AS = ST->getAddressSpace();
2509 if (LD->isIndexed() || LD->getBasePtr().getNode() !=
N)
2511 VT = LD->getMemoryVT();
2512 AS = LD->getAddressSpace();
2514 if (ST->isIndexed() || ST->getBasePtr().getNode() !=
N)
2516 VT = ST->getMemoryVT();
2517 AS = ST->getAddressSpace();
2523 if (
N->isAnyAdd()) {
2532 }
else if (
N->getOpcode() ==
ISD::SUB) {
2554 bool ShouldCommuteOperands) {
2560 if (ShouldCommuteOperands)
2574 unsigned Opcode =
N->getOpcode();
2575 EVT VT =
N->getValueType(0);
2580 unsigned OpNo = ShouldCommuteOperands ? 0 : 1;
2600SDValue DAGCombiner::foldBinOpIntoSelect(SDNode *BO) {
2603 "Unexpected binary operator");
2615 unsigned SelOpNo = 0;
2652 bool CanFoldNonConst =
2658 if (!CanFoldNonConst &&
2667 if (CanFoldNonConst) {
2686 : DAG.FoldConstantArithmetic(BinOpcode,
DL, VT, {CT, CBO});
2691 : DAG.FoldConstantArithmetic(BinOpcode,
DL, VT, {CF, CBO});
2702 "Expecting add or sub");
2707 bool IsAdd =
N->getOpcode() ==
ISD::ADD;
2708 SDValue C = IsAdd ?
N->getOperand(1) :
N->getOperand(0);
2709 SDValue Z = IsAdd ?
N->getOperand(0) :
N->getOperand(1);
2715 if (Z.getOperand(0).getValueType() != MVT::i1)
2727 EVT VT =
C.getValueType();
2735SDValue DAGCombiner::foldSubToAvg(SDNode *
N,
const SDLoc &
DL) {
2740 if ((!LegalOperations || hasOperation(
ISD::AVGCEILU, VT)) &&
2745 if ((!LegalOperations || hasOperation(
ISD::AVGCEILS, VT)) &&
2756SDValue DAGCombiner::visitPTRADD(SDNode *
N) {
2766 "PTRADD with different operand types is not supported");
2777 !reassociationCanBreakAddressingModePattern(
ISD::PTRADD,
DL,
N, N0, N1)) {
2788 if ((YIsConstant && N0OneUse) || (YIsConstant && ZIsConstant)) {
2793 AddToWorklist(
Add.getNode());
2817 if (
const GlobalAddressSDNode *GA =
2832 AddToWorklist(Inner.
getNode());
2854 SDNodeFlags CommonFlags =
N->getFlags() & N1->
getFlags();
2862 if (ZIsConstant != YIsConstant) {
2866 AddToWorklist(Inner.
getNode());
2876 bool TransformCannotBreakAddrMode =
none_of(
N->users(), [&](SDNode *User) {
2877 return canFoldInAddressingMode(N, User, DAG, TLI);
2880 if (TransformCannotBreakAddrMode)
2892 "Expecting add or sub");
2896 bool IsAdd =
N->getOpcode() ==
ISD::ADD;
2897 SDValue ConstantOp = IsAdd ?
N->getOperand(1) :
N->getOperand(0);
2898 SDValue ShiftOp = IsAdd ?
N->getOperand(0) :
N->getOperand(1);
2920 {ConstantOp, DAG.getConstant(1, DL, VT)})) {
2922 Not.getOperand(0), ShAmt);
2938SDValue DAGCombiner::visitADDLike(SDNode *
N) {
2964 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
2996 if ((!LegalOperations ||
2999 X.getScalarValueSizeInBits() == 1) {
3015 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
3019 if (!reassociationCanBreakAddressingModePattern(
ISD::ADD,
DL,
N, N0, N1)) {
3031 SDNodeFlags NewFlags =
3121 auto MatchUSUBSAT = [](ConstantSDNode *
Max, ConstantSDNode *
Op) {
3122 return (!Max && !
Op) ||
3123 (
Max &&
Op &&
Max->getAPIntValue() == (-
Op->getAPIntValue()));
3164 !
N->getFlags().hasNoSignedWrap()))) {
3185 (CA * CM + CB->getAPIntValue()).getSExtValue())) {
3189 if (
N->getFlags().hasNoUnsignedWrap() &&
3193 if (
N->getFlags().hasNoSignedWrap() &&
3202 DAG.
getConstant(CA * CM + CB->getAPIntValue(),
DL, VT), Flags);
3210 (CA * CM + CB->getAPIntValue()).getSExtValue())) {
3216 if (
N->getFlags().hasNoUnsignedWrap() &&
3221 if (
N->getFlags().hasNoSignedWrap() &&
3232 DAG.
getConstant(CA * CM + CB->getAPIntValue(),
DL, VT), Flags);
3237 if (
SDValue Combined = visitADDLikeCommutative(N0, N1,
DL))
3240 if (
SDValue Combined = visitADDLikeCommutative(N1, N0,
DL))
3249SDValue DAGCombiner::foldAddToAvg(SDNode *
N,
const SDLoc &
DL) {
3275 if ((!LegalOperations || hasOperation(
ISD::AVGCEILU, VT)) &&
3282 if ((!LegalOperations || hasOperation(
ISD::AVGCEILS, VT)) &&
3293SDValue DAGCombiner::visitADD(SDNode *
N) {
3299 if (
SDValue Combined = visitADDLike(
N))
3308 if (
SDValue V = MatchRotate(N0, N1, SDLoc(
N),
true))
3342 APInt NewStep = C0 + C1;
3352 APInt NewStep = SV0 + SV1;
3360SDValue DAGCombiner::visitADDSAT(SDNode *
N) {
3361 unsigned Opcode =
N->getOpcode();
3379 return DAG.
getNode(Opcode,
DL, VT, N1, N0);
3383 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
3403 bool ForceCarryReconstruction =
false) {
3408 if (ForceCarryReconstruction && V.getValueType() == MVT::i1)
3412 V = V.getOperand(0);
3417 if (ForceCarryReconstruction)
3421 V = V.getOperand(0);
3429 if (V.getResNo() != 1)
3436 EVT VT = V->getValueType(0);
3543 if (TN->
getVT() == MVT::i1) {
3560 DAG.
getVTList(VT, Carry.getValueType()), N0,
3566SDValue DAGCombiner::visitADDC(SDNode *
N) {
3573 if (!
N->hasAnyUseOfValue(1))
3613 return V.getOperand(0);
3619SDValue DAGCombiner::visitADDO(SDNode *
N) {
3625 EVT CarryVT =
N->getValueType(1);
3629 if (!
N->hasAnyUseOfValue(1))
3636 return DAG.
getNode(
N->getOpcode(),
DL,
N->getVTList(), N1, N0);
3661 if (
SDValue Combined = visitUADDOLike(N0, N1,
N))
3664 if (
SDValue Combined = visitUADDOLike(N1, N0,
N))
3695SDValue DAGCombiner::visitADDE(SDNode *
N) {
3714SDValue DAGCombiner::visitUADDO_CARRY(SDNode *
N) {
3728 if (!LegalOperations ||
3738 AddToWorklist(CarryExt.
getNode());
3744 if (
SDValue Combined = visitUADDO_CARRYLike(N0, N1, CarryIn,
N))
3747 if (
SDValue Combined = visitUADDO_CARRYLike(N1, N0, CarryIn,
N))
3894 EVT CarryOutType =
N->getValueType(0);
3910 unsigned CarryInOperandNum =
3912 if (Opcode ==
ISD::USUBO && CarryInOperandNum != 1)
3965 EVT IntVT =
A.getValueType();
4030SDValue DAGCombiner::visitSADDO_CARRY(SDNode *
N) {
4044 if (!LegalOperations ||
4049 if (
SDValue Combined = visitSADDO_CARRYLike(N0, N1, CarryIn,
N))
4052 if (
SDValue Combined = visitSADDO_CARRYLike(N1, N0, CarryIn,
N))
4064 "Illegal truncation");
4088SDValue DAGCombiner::foldSubToUSubSat(EVT DstVT, SDNode *
N,
const SDLoc &
DL) {
4090 !(!LegalOperations || hasOperation(
ISD::USUBSAT, DstVT)))
4093 EVT SubVT =
N->getValueType(0);
4180 if ((
BitWidth - Src.getValueType().getScalarSizeInBits()) != BitWidthDiff)
4190 unsigned AndMaskWidth =
BitWidth - BitWidthDiff;
4191 if (!(AndMask.
isMask(AndMaskWidth) && XorMask.
countr_one() >= AndMaskWidth))
4226 if (
SDValue Res = CheckAndFoldMulCase(Mul0, Mul1))
4229 if (
SDValue Res = CheckAndFoldMulCase(Mul1, Mul0))
4267SDValue DAGCombiner::visitSUB(SDNode *
N) {
4287 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
4314 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
4337 if (
N->getFlags().hasNoUnsignedWrap())
4343 if (
N->getFlags().hasNoSignedWrap())
4369 if (hasOperation(NewOpc, VT))
4511 if (!reassociationCanBreakAddressingModePattern(
ISD::SUB,
DL,
N, N0, N1) &&
4549 if ((!LegalOperations || hasOperation(
ISD::ABS, VT)) &&
4559 if (GA->getGlobal() == GB->getGlobal())
4569 if (TN->
getVT() == MVT::i1) {
4628 DAG.
getVTList(VT, Carry.getValueType()), NegX, Zero,
4634 const APInt &C0Val = C0->getAPIntValue();
4637 if (
N->getFlags().hasNoUnsignedWrap() && C0Val.
isMask())
4642 if (!C0->isOpaque()) {
4643 const APInt &MaybeOnes = ~DAG.computeKnownBits(N1).Zero;
4644 if ((C0Val - MaybeOnes) == (C0Val ^ MaybeOnes))
4650 if ((!LegalOperations || hasOperation(
ISD::ABDS, VT)) &&
4662 if ((!LegalOperations || hasOperation(
ISD::ABDU, VT)) &&
4676SDValue DAGCombiner::visitSUBSAT(SDNode *
N) {
4677 unsigned Opcode =
N->getOpcode();
4698 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
4724 NarrowBits != 0 && NarrowBits < ScalarBits; NarrowBits *= 2) {
4725 unsigned Scale = ScalarBits / NarrowBits;
4753SDValue DAGCombiner::visitSUBC(SDNode *
N) {
4760 if (!
N->hasAnyUseOfValue(1))
4781SDValue DAGCombiner::visitSUBO(SDNode *
N) {
4787 EVT CarryVT =
N->getValueType(1);
4791 if (!
N->hasAnyUseOfValue(1))
4823SDValue DAGCombiner::visitSUBE(SDNode *
N) {
4835SDValue DAGCombiner::visitUSUBO_CARRY(SDNode *
N) {
4842 if (!LegalOperations ||
4850 !
N->hasAnyUseOfValue(1))
4857SDValue DAGCombiner::visitSSUBO_CARRY(SDNode *
N) {
4864 if (!LegalOperations ||
4874SDValue DAGCombiner::visitMULFIX(SDNode *
N) {
4887 return DAG.
getNode(
N->getOpcode(), SDLoc(
N), VT, N1, N0, Scale);
4896SDValue DAGCombiner::visitMUL(SDNode *
N) {
4916 bool N1IsConst =
false;
4917 bool N1IsOpaqueConst =
false;
4922 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
4927 "Splat APInt should be element width");
4937 if (N1IsConst && ConstValue1.
isZero())
4941 if (N1IsConst && ConstValue1.
isOne())
4944 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
4948 if (N1IsConst && ConstValue1.
isAllOnes())
4954 if (
SDValue LogBase2 = BuildLogBase2(N1,
DL)) {
4958 Flags.setNoUnsignedWrap(
N->getFlags().hasNoUnsignedWrap());
4961 if (
N->getFlags().hasNoSignedWrap() && N1IsConst &&
4963 Flags.setNoSignedWrap(
true);
4970 unsigned Log2Val = (-ConstValue1).logBase2();
4984 SDVTList LoHiVT = DAG.
getVTList(VT, VT);
4987 if (LoHi->hasAnyUseOfValue(1))
4990 if (LoHi->hasAnyUseOfValue(1))
5015 APInt MulC = ConstValue1.
abs();
5017 unsigned TZeros = MulC == 2 ? 0 : MulC.
countr_zero();
5019 if ((MulC - 1).isPowerOf2())
5021 else if ((MulC + 1).isPowerOf2())
5026 MathOp ==
ISD::ADD ? (MulC - 1).logBase2() : (MulC + 1).logBase2();
5029 "multiply-by-constant generated out of bounds shift");
5033 TZeros ? DAG.
getNode(MathOp,
DL, VT, Shl,
5088 APInt NewStep = C0 * MulVal;
5094 if ((!LegalOperations || hasOperation(
ISD::ABS, VT)) &&
5107 SmallBitVector ClearMask;
5109 auto IsClearMask = [&ClearMask](ConstantSDNode *
V) {
5110 if (!V ||
V->isZero()) {
5124 for (
unsigned I = 0;
I != NumElts; ++
I)
5151 EVT NodeType =
Node->getValueType(0);
5152 if (!NodeType.isSimple())
5154 switch (NodeType.getSimpleVT().SimpleTy) {
5155 default:
return false;
5156 case MVT::i8: LC=
isSigned ? RTLIB::SDIVREM_I8 : RTLIB::UDIVREM_I8;
break;
5157 case MVT::i16: LC=
isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16;
break;
5158 case MVT::i32: LC=
isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32;
break;
5159 case MVT::i64: LC=
isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64;
break;
5160 case MVT::i128: LC=
isSigned ? RTLIB::SDIVREM_I128:RTLIB::UDIVREM_I128;
break;
5167SDValue DAGCombiner::useDivRem(SDNode *Node) {
5168 if (
Node->use_empty())
5171 unsigned Opcode =
Node->getOpcode();
5176 EVT VT =
Node->getValueType(0);
5190 unsigned OtherOpcode = 0;
5204 for (SDNode *User : Op0->
users()) {
5211 unsigned UserOpc =
User->getOpcode();
5212 if ((UserOpc == Opcode || UserOpc == OtherOpcode || UserOpc == DivRemOpc) &&
5213 User->getOperand(0) == Op0 &&
5214 User->getOperand(1) == Op1) {
5216 if (UserOpc == OtherOpcode) {
5218 combined = DAG.
getNode(DivRemOpc, SDLoc(Node), VTs, Op0, Op1);
5219 }
else if (UserOpc == DivRemOpc) {
5222 assert(UserOpc == Opcode);
5227 CombineTo(User, combined);
5229 CombineTo(User, combined.
getValue(1));
5238 EVT VT =
N->getValueType(0);
5241 unsigned Opc =
N->getOpcode();
5260 if (N0C && N0C->
isZero())
5280SDValue DAGCombiner::visitSDIV(SDNode *
N) {
5283 EVT VT =
N->getValueType(0);
5293 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5310 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
5318 if (
SDValue V = visitSDIVLike(N0, N1,
N)) {
5325 if (!
N->getFlags().hasExact()) {
5328 AddToWorklist(
Mul.getNode());
5329 AddToWorklist(
Sub.getNode());
5330 CombineTo(RemNode,
Sub);
5351 if (
C->isZero() ||
C->isOpaque())
5353 if (
C->getAPIntValue().isPowerOf2())
5355 if (
C->getAPIntValue().isNegatedPowerOf2())
5366 EVT VT =
N->getValueType(0);
5377 if ((!
N->getFlags().hasExact() ||
BitWidth > MaxLegalDivRemBitWidth) &&
5395 AddToWorklist(Sign.
getNode());
5401 AddToWorklist(
Add.getNode());
5412 Sra = DAG.
getSelect(
DL, VT, IsOneOrAllOnes, N0, Sra);
5438SDValue DAGCombiner::visitUDIV(SDNode *
N) {
5441 EVT VT =
N->getValueType(0);
5451 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5465 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
5468 if (
SDValue V = visitUDIVLike(N0, N1,
N)) {
5475 if (!
N->getFlags().hasExact()) {
5478 AddToWorklist(
Mul.getNode());
5479 AddToWorklist(
Sub.getNode());
5480 CombineTo(RemNode,
Sub);
5505 EVT VT =
N->getValueType(0);
5510 if (
SDValue LogBase2 = BuildLogBase2(N1,
DL)) {
5511 AddToWorklist(LogBase2.getNode());
5515 AddToWorklist(Trunc.
getNode());
5525 if (
SDValue LogBase2 = BuildLogBase2(N10,
DL)) {
5526 AddToWorklist(LogBase2.getNode());
5530 AddToWorklist(Trunc.
getNode());
5532 AddToWorklist(
Add.getNode());
5560SDValue DAGCombiner::visitREM(SDNode *
N) {
5561 unsigned Opcode =
N->getOpcode();
5564 EVT VT =
N->getValueType(0);
5586 if (
SDValue NewSel = foldBinOpIntoSelect(
N))
5599 AddToWorklist(
Add.getNode());
5616 if (
SDValue OptimizedRem = buildOptimizedSREM(N0, N1,
N))
5617 return OptimizedRem;
5621 isSigned ? visitSDIVLike(N0, N1,
N) : visitUDIVLike(N0, N1,
N);
5624 unsigned DivOpcode = isSigned ? ISD::SDIV : ISD::UDIV;
5625 if (SDNode *DivNode = DAG.getNodeIfExists(DivOpcode, N->getVTList(),
5627 CombineTo(DivNode, OptimizedDiv);
5630 AddToWorklist(OptimizedDiv.
getNode());
5631 AddToWorklist(
Mul.getNode());
5638 return DivRem.getValue(1);
5661SDValue DAGCombiner::visitMULHS(SDNode *
N) {
5664 EVT VT =
N->getValueType(0);
5677 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5720SDValue DAGCombiner::visitMULHU(SDNode *
N) {
5723 EVT VT =
N->getValueType(0);
5736 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5760 (!LegalOperations || hasOperation(
ISD::SRL, VT))) {
5761 if (
SDValue LogBase2 = BuildLogBase2(N1,
DL)) {
5776 unsigned SimpleSize =
Simple.getSizeInBits();
5797SDValue DAGCombiner::visitAVG(SDNode *
N) {
5798 unsigned Opcode =
N->getOpcode();
5801 EVT VT =
N->getValueType(0);
5812 return DAG.
getNode(Opcode,
DL,
N->getVTList(), N1, N0);
5815 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5841 X.getValueType() ==
Y.getValueType() &&
5842 hasOperation(Opcode,
X.getValueType())) {
5848 X.getValueType() ==
Y.getValueType() &&
5849 hasOperation(Opcode,
X.getValueType())) {
5880 if (IsSigned &&
Add->getFlags().hasNoSignedWrap())
5883 if (!IsSigned &&
Add->getFlags().hasNoUnsignedWrap())
5897SDValue DAGCombiner::visitABD(SDNode *
N) {
5898 unsigned Opcode =
N->getOpcode();
5901 EVT VT =
N->getValueType(0);
5911 return DAG.
getNode(Opcode,
DL,
N->getVTList(), N1, N0);
5914 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
5929 (!LegalOperations || hasOperation(
ISD::ABS, VT)))
5944 EVT SmallVT =
X.getScalarValueSizeInBits() >
Y.getScalarValueSizeInBits()
5947 if (!LegalOperations || hasOperation(Opcode, SmallVT)) {
5959 EVT SmallVT =
X.getValueType();
5960 if (!LegalOperations || hasOperation(Opcode, SmallVT)) {
5962 unsigned RelevantBits =
5971 const APInt &YConst =
C->getAsAPIntVal();
5978 if (RelevantBits <= Bits && TruncatingYIsCheap) {
5992SDValue DAGCombiner::SimplifyNodeWithTwoResults(SDNode *
N,
unsigned LoOp,
5995 bool HiExists =
N->hasAnyUseOfValue(1);
5996 if (!HiExists && (!LegalOperations ||
5999 return CombineTo(
N, Res, Res);
6003 bool LoExists =
N->hasAnyUseOfValue(0);
6004 if (!LoExists && (!LegalOperations ||
6007 return CombineTo(
N, Res, Res);
6011 if (LoExists && HiExists)
6017 AddToWorklist(
Lo.getNode());
6020 (!LegalOperations ||
6022 return CombineTo(
N, LoOpt, LoOpt);
6027 AddToWorklist(
Hi.getNode());
6030 (!LegalOperations ||
6032 return CombineTo(
N, HiOpt, HiOpt);
6038SDValue DAGCombiner::visitSMUL_LOHI(SDNode *
N) {
6044 EVT VT =
N->getValueType(0);
6060 unsigned SimpleSize =
Simple.getSizeInBits();
6072 return CombineTo(
N,
Lo,
Hi);
6079SDValue DAGCombiner::visitUMUL_LOHI(SDNode *
N) {
6085 EVT VT =
N->getValueType(0);
6100 return CombineTo(
N, Zero, Zero);
6106 return CombineTo(
N, N0, Zero);
6113 unsigned SimpleSize =
Simple.getSizeInBits();
6125 return CombineTo(
N,
Lo,
Hi);
6132SDValue DAGCombiner::visitMULO(SDNode *
N) {
6138 EVT CarryVT =
N->getValueType(1);
6159 return DAG.
getNode(
N->getOpcode(),
DL,
N->getVTList(), N1, N0);
6171 N->getVTList(), N0, N0);
6178 return CombineTo(
N,
And, Cmp);
6216 unsigned Opcode0 = isSignedMinMax(N0, N1, N2, N3, CC);
6270 unsigned Opcode1 = isSignedMinMax(N00, N01, N02, N03, N0CC);
6271 if (!Opcode1 || Opcode0 == Opcode1)
6281 APInt MinCPlus1 = MinC + 1;
6282 if (-MaxC == MinCPlus1 && MinCPlus1.
isPowerOf2()) {
6288 if (MaxC == 0 && MinC != 0 && MinCPlus1.
isPowerOf2()) {
6337 unsigned BW = (C1 + 1).exactLogBase2();
6354 EVT VT =
N->getValueType(0);
6389 X.getValueType(), VT))
6403SDValue DAGCombiner::visitIMINMAX(SDNode *
N) {
6407 unsigned Opcode =
N->getOpcode();
6421 return DAG.
getNode(Opcode,
DL, VT, N1, N0);
6425 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))
6429 if (
SDValue RMINMAX = reassociateOps(Opcode,
DL, N0, N1,
N->getFlags()))
6474 if (IsSatBroken || IsOpIllegal) {
6476 if (
A.isUndef() ||
B.isUndef())
6489 if (HasKnownSameSign(N0, N1)) {
6492 return DAG.
getNode(AltOpcode,
DL, VT, N0, N1);
6505 auto ReductionOpcode = [](
unsigned Opcode) {
6519 if (
SDValue SD = reassociateReduction(ReductionOpcode(Opcode), Opcode,
6520 SDLoc(
N), VT, N0, N1))
6528 return C0 > C1 ? N0 : N1;
6530 return C0 > C1 ? N1 : N0;
6539 const APInt &C1V = C1->getAPIntValue();
6558SDValue DAGCombiner::hoistLogicOpWithSameOpcodeHands(SDNode *
N) {
6561 unsigned LogicOpcode =
N->getOpcode();
6586 if (XVT !=
Y.getValueType())
6590 if ((VT.
isVector() || LegalOperations) &&
6600 SDNodeFlags LogicFlags;
6606 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6616 if (XVT !=
Y.getValueType())
6628 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6649 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6664 return DAG.
getNode(HandOpcode,
DL, VT, Logic0, Logic1, S);
6677 if (XVT.
isInteger() && XVT ==
Y.getValueType() &&
6681 return DAG.
getNode(HandOpcode,
DL, VT, Logic);
6700 assert(
X.getValueType() ==
Y.getValueType() &&
6701 "Inputs to shuffles are not the same type");
6707 if (!SVN0->hasOneUse() || !SVN1->hasOneUse() ||
6708 !SVN0->getMask().equals(SVN1->getMask()))
6744 SDValue LL, LR, RL, RR, N0CC, N1CC;
6745 if (!isSetCCEquivalent(N0, LL, LR, N0CC) ||
6746 !isSetCCEquivalent(N1, RL, RR, N1CC))
6750 "Unexpected operand types for bitwise logic op");
6753 "Unexpected operand types for setcc");
6769 if (LR == RR && CC0 == CC1 && IsInteger) {
6774 bool AndEqZero = IsAnd && CC1 ==
ISD::SETEQ && IsZero;
6776 bool AndGtNeg1 = IsAnd && CC1 ==
ISD::SETGT && IsNeg1;
6778 bool OrNeZero = !IsAnd && CC1 ==
ISD::SETNE && IsZero;
6780 bool OrLtZero = !IsAnd && CC1 ==
ISD::SETLT && IsZero;
6786 if (AndEqZero || AndGtNeg1 || OrNeZero || OrLtZero) {
6788 AddToWorklist(
Or.getNode());
6793 bool AndEqNeg1 = IsAnd && CC1 ==
ISD::SETEQ && IsNeg1;
6795 bool AndLtZero = IsAnd && CC1 ==
ISD::SETLT && IsZero;
6797 bool OrNeNeg1 = !IsAnd && CC1 ==
ISD::SETNE && IsNeg1;
6799 bool OrGtNeg1 = !IsAnd && CC1 ==
ISD::SETGT && IsNeg1;
6805 if (AndEqNeg1 || AndLtZero || OrNeNeg1 || OrGtNeg1) {
6807 AddToWorklist(
And.getNode());
6841 AddToWorklist(
Add.getNode());
6862 auto MatchDiffPow2 = [&](ConstantSDNode *C0, ConstantSDNode *C1) {
6868 return !C0->
isOpaque() && !C1->isOpaque() && (CMax - CMin).isPowerOf2();
6886 if (LL == RR && LR == RL) {
6893 if (LL == RL && LR == RR) {
6897 (!LegalOperations ||
6934 unsigned OrAndOpcode,
SelectionDAG &DAG,
bool isFMAXNUMFMINNUM_IEEE,
6935 bool isFMAXNUMFMINNUM) {
6946 isFMAXNUMFMINNUM_IEEE
6954 isFMAXNUMFMINNUM_IEEE
6972 isFMAXNUMFMINNUM_IEEE
6981 isFMAXNUMFMINNUM_IEEE
6992 (LogicOp->getOpcode() ==
ISD::AND || LogicOp->getOpcode() ==
ISD::OR) &&
6993 "Invalid Op to combine SETCC with");
6999 !
LHS->hasOneUse() || !
RHS->hasOneUse())
7006 LogicOp,
LHS.getNode(),
RHS.getNode());
7018 EVT VT = LogicOp->getValueType(0);
7041 (isFMAXNUMFMINNUM_IEEE || isFMAXNUMFMINNUM))) &&
7047 SDValue CommonValue, Operand1, Operand2;
7055 }
else if (LHS1 == RHS1) {
7068 }
else if (RHS0 == LHS1) {
7085 bool IsSigned = isSignedIntSetCC(CC);
7089 bool IsOr = (LogicOp->getOpcode() ==
ISD::OR);
7098 LogicOp->getOpcode(), DAG, isFMAXNUMFMINNUM_IEEE, isFMAXNUMFMINNUM);
7104 DAG.
getNode(NewOpcode,
DL, OpVT, Operand1, Operand2, Flags);
7105 return DAG.
getSetCC(
DL, VT, MinMaxValue, CommonValue, CC, {},
7111 if (LHS0 == LHS1 && RHS0 == RHS1 && CCL == CCR &&
7115 return DAG.
getSetCC(
DL, VT, LHS0, RHS0, CCL);
7122 LHS0 == RHS0 && LHS1C && RHS1C && OpVT.
isInteger()) {
7123 const APInt &APLhs = LHS1C->getAPIntValue();
7124 const APInt &APRhs = RHS1C->getAPIntValue();
7128 if (APLhs == (-APRhs) &&
7139 }
else if (TargetPreference &
7160 APInt Dif = MaxC - MinC;
7194 EVT CondVT =
Cond.getValueType();
7205 EVT OpVT =
T.getValueType();
7224 if (
SDValue V = foldLogicOfSetCCs(
true, N0, N1,
DL))
7241 APInt
ADDC = ADDI->getAPIntValue();
7242 APInt SRLC = SRLI->getAPIntValue();
7254 CombineTo(N0.
getNode(), NewAdd);
7267bool DAGCombiner::isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
7268 EVT LoadResultTy, EVT &ExtVT) {
7277 if (ExtVT == LoadedVT &&
7278 (!LegalOperations ||
7295 if (LegalOperations &&
7306bool DAGCombiner::isLegalNarrowLdSt(LSBaseSDNode *LDST,
7315 const unsigned ByteShAmt = ShAmt / 8;
7334 if (LdStMemVT.
bitsLT(MemVT))
7349 if (PtrType == MVT::Untyped || PtrType.
isExtended())
7359 if (LegalOperations &&
7361 Load->getAddressSpace(), ExtType,
false))
7369 if (
Load->getNumValues() > 2)
7388 if (LegalOperations &&
7390 Store->getAlign(),
Store->getAddressSpace()))
7396bool DAGCombiner::SearchForAndLoads(SDNode *
N,
7397 SmallVectorImpl<LoadSDNode*> &Loads,
7398 SmallPtrSetImpl<SDNode*> &NodesWithConsts,
7399 ConstantSDNode *Mask,
7400 SDNode *&NodeToMask) {
7404 if (
Op.getValueType().isVector())
7410 "Expected bitwise logic operation");
7411 if (!
C->getAPIntValue().isSubsetOf(
Mask->getAPIntValue()))
7416 if (!
Op.hasOneUse())
7419 switch(
Op.getOpcode()) {
7423 if (isAndLoadExtLoad(Mask,
Load,
Load->getValueType(0), ExtVT) &&
7441 unsigned ActiveBits =
Mask->getAPIntValue().countr_one();
7445 Op.getOperand(0).getValueType();
7456 if (!SearchForAndLoads(
Op.getNode(), Loads, NodesWithConsts, Mask,
7467 NodeToMask =
Op.getNode();
7470 for (
unsigned i = 0, e = NodeToMask->
getNumValues(); i < e; ++i) {
7471 MVT VT =
SDValue(NodeToMask, i).getSimpleValueType();
7472 if (VT != MVT::Glue && VT != MVT::Other) {
7474 NodeToMask =
nullptr;
7486bool DAGCombiner::BackwardsPropagateMask(SDNode *
N) {
7491 if (!
Mask->getAPIntValue().isMask())
7499 SmallPtrSet<SDNode*, 2> NodesWithConsts;
7500 SDNode *FixupNode =
nullptr;
7501 if (SearchForAndLoads(
N, Loads, NodesWithConsts, Mask, FixupNode)) {
7514 SDValue(FixupNode, 0), MaskOp);
7516 if (
And.getOpcode() == ISD ::AND)
7521 for (
auto *LogicN : NodesWithConsts) {
7527 if (LogicN->getOpcode() ==
ISD::AND &&
7546 for (
auto *
Load : Loads) {
7551 if (
And.getOpcode() == ISD ::AND)
7554 SDValue NewLoad = reduceLoadWidth(
And.getNode());
7556 "Shouldn't be masking the load if it can't be narrowed");
7570SDValue DAGCombiner::unfoldExtremeBitClearingToShifts(SDNode *
N) {
7581 unsigned OuterShift;
7582 unsigned InnerShift;
7584 auto matchMask = [&OuterShift, &InnerShift, &
Y](
SDValue M) ->
bool {
7587 OuterShift =
M->getOpcode();
7596 Y =
M->getOperand(1);
7603 else if (matchMask(N0))
7609 EVT VT =
N->getValueType(0);
7626 SDValue And0 =
And->getOperand(0), And1 =
And->getOperand(1);
7636 bool FoundNot =
false;
7639 Src = Src.getOperand(0);
7645 Src = Src.getOperand(0);
7649 if (Src.getOpcode() !=
ISD::SRL || !Src.hasOneUse())
7653 EVT SrcVT = Src.getValueType();
7662 if (!ShiftAmtC || !ShiftAmtC->getAPIntValue().ult(
BitWidth))
7666 Src = Src.getOperand(0);
7673 Src = Src.getOperand(0);
7697 EVT VT =
N->getValueType(0);
7723 unsigned LogicOpcode =
N->getOpcode();
7725 "Expected bitwise logic operation");
7727 if (!LogicOp.hasOneUse() || !ShiftOp.
hasOneUse())
7731 unsigned ShiftOpcode = ShiftOp.
getOpcode();
7732 if (LogicOp.getOpcode() != LogicOpcode ||
7744 if (LogicOp.getOperand(0).getOpcode() == ShiftOpcode &&
7745 LogicOp.getOperand(0).getOperand(1) ==
Y) {
7747 Z = LogicOp.getOperand(1);
7748 }
else if (LogicOp.getOperand(1).getOpcode() == ShiftOpcode &&
7749 LogicOp.getOperand(1).getOperand(1) ==
Y) {
7751 Z = LogicOp.getOperand(0);
7756 EVT VT =
N->getValueType(0);
7760 return DAG.
getNode(LogicOpcode,
DL, VT, NewShift, Z);
7771 unsigned LogicOpcode =
N->getOpcode();
7773 "Expected bitwise logic operation");
7774 if (LeftHand.
getOpcode() != LogicOpcode ||
7795 EVT VT =
N->getValueType(0);
7797 return DAG.
getNode(LogicOpcode,
DL, VT, CombinedShifts, W);
7809 "Must be called with ISD::OR or ISD::AND node");
7823 EVT VT = M.getValueType();
7831SDValue DAGCombiner::visitAND(SDNode *
N) {
7855 if (
SDValue FoldedVOp = SimplifyVBinOp(
N,
DL))