LLVM  10.0.0svn
DAGCombiner.cpp
Go to the documentation of this file.
1 //===- DAGCombiner.cpp - Implement a DAG node combiner --------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass combines dag nodes to form fewer, simpler DAG nodes. It can be run
10 // both before and after the DAG is legalized.
11 //
12 // This pass is not a substitute for the LLVM IR instcombine pass. This pass is
13 // primarily intended to handle simplification opportunities that are implicit
14 // in the LLVM IR and exposed by the various codegen lowering phases.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/ADT/APFloat.h"
19 #include "llvm/ADT/APInt.h"
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/IntervalMap.h"
23 #include "llvm/ADT/None.h"
24 #include "llvm/ADT/Optional.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/SetVector.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
47 #include "llvm/IR/Attributes.h"
48 #include "llvm/IR/Constant.h"
49 #include "llvm/IR/DataLayout.h"
50 #include "llvm/IR/DerivedTypes.h"
51 #include "llvm/IR/Function.h"
52 #include "llvm/IR/LLVMContext.h"
53 #include "llvm/IR/Metadata.h"
54 #include "llvm/Support/Casting.h"
55 #include "llvm/Support/CodeGen.h"
57 #include "llvm/Support/Compiler.h"
58 #include "llvm/Support/Debug.h"
60 #include "llvm/Support/KnownBits.h"
66 #include <algorithm>
67 #include <cassert>
68 #include <cstdint>
69 #include <functional>
70 #include <iterator>
71 #include <string>
72 #include <tuple>
73 #include <utility>
74 
75 using namespace llvm;
76 
77 #define DEBUG_TYPE "dagcombine"
78 
79 STATISTIC(NodesCombined , "Number of dag nodes combined");
80 STATISTIC(PreIndexedNodes , "Number of pre-indexed nodes created");
81 STATISTIC(PostIndexedNodes, "Number of post-indexed nodes created");
82 STATISTIC(OpsNarrowed , "Number of load/op/store narrowed");
83 STATISTIC(LdStFP2Int , "Number of fp load/store pairs transformed to int");
84 STATISTIC(SlicedLoads, "Number of load sliced");
85 STATISTIC(NumFPLogicOpsConv, "Number of logic ops converted to fp ops");
86 
87 static cl::opt<bool>
88 CombinerGlobalAA("combiner-global-alias-analysis", cl::Hidden,
89  cl::desc("Enable DAG combiner's use of IR alias analysis"));
90 
91 static cl::opt<bool>
92 UseTBAA("combiner-use-tbaa", cl::Hidden, cl::init(true),
93  cl::desc("Enable DAG combiner's use of TBAA"));
94 
95 #ifndef NDEBUG
97 CombinerAAOnlyFunc("combiner-aa-only-func", cl::Hidden,
98  cl::desc("Only use DAG-combiner alias analysis in this"
99  " function"));
100 #endif
101 
102 /// Hidden option to stress test load slicing, i.e., when this option
103 /// is enabled, load slicing bypasses most of its profitability guards.
104 static cl::opt<bool>
105 StressLoadSlicing("combiner-stress-load-slicing", cl::Hidden,
106  cl::desc("Bypass the profitability model of load slicing"),
107  cl::init(false));
108 
109 static cl::opt<bool>
110  MaySplitLoadIndex("combiner-split-load-index", cl::Hidden, cl::init(true),
111  cl::desc("DAG combiner may split indexing from loads"));
112 
113 static cl::opt<bool>
114  EnableStoreMerging("combiner-store-merging", cl::Hidden, cl::init(true),
115  cl::desc("DAG combiner enable merging multiple stores "
116  "into a wider store"));
117 
119  "combiner-tokenfactor-inline-limit", cl::Hidden, cl::init(2048),
120  cl::desc("Limit the number of operands to inline for Token Factors"));
121 
123  "combiner-store-merge-dependence-limit", cl::Hidden, cl::init(10),
124  cl::desc("Limit the number of times for the same StoreNode and RootNode "
125  "to bail out in store merging dependence check"));
126 
127 namespace {
128 
129  class DAGCombiner {
130  SelectionDAG &DAG;
131  const TargetLowering &TLI;
133  CodeGenOpt::Level OptLevel;
134  bool LegalOperations = false;
135  bool LegalTypes = false;
136  bool ForCodeSize;
137 
138  /// Worklist of all of the nodes that need to be simplified.
139  ///
140  /// This must behave as a stack -- new nodes to process are pushed onto the
141  /// back and when processing we pop off of the back.
142  ///
143  /// The worklist will not contain duplicates but may contain null entries
144  /// due to nodes being deleted from the underlying DAG.
145  SmallVector<SDNode *, 64> Worklist;
146 
147  /// Mapping from an SDNode to its position on the worklist.
148  ///
149  /// This is used to find and remove nodes from the worklist (by nulling
150  /// them) when they are deleted from the underlying DAG. It relies on
151  /// stable indices of nodes within the worklist.
152  DenseMap<SDNode *, unsigned> WorklistMap;
153  /// This records all nodes attempted to add to the worklist since we
154  /// considered a new worklist entry. As we keep do not add duplicate nodes
155  /// in the worklist, this is different from the tail of the worklist.
156  SmallSetVector<SDNode *, 32> PruningList;
157 
158  /// Set of nodes which have been combined (at least once).
159  ///
160  /// This is used to allow us to reliably add any operands of a DAG node
161  /// which have not yet been combined to the worklist.
162  SmallPtrSet<SDNode *, 32> CombinedNodes;
163 
164  /// Map from candidate StoreNode to the pair of RootNode and count.
165  /// The count is used to track how many times we have seen the StoreNode
166  /// with the same RootNode bail out in dependence check. If we have seen
167  /// the bail out for the same pair many times over a limit, we won't
168  /// consider the StoreNode with the same RootNode as store merging
169  /// candidate again.
171 
172  // AA - Used for DAG load/store alias analysis.
173  AliasAnalysis *AA;
174 
175  /// When an instruction is simplified, add all users of the instruction to
176  /// the work lists because they might get more simplified now.
177  void AddUsersToWorklist(SDNode *N) {
178  for (SDNode *Node : N->uses())
179  AddToWorklist(Node);
180  }
181 
182  // Prune potentially dangling nodes. This is called after
183  // any visit to a node, but should also be called during a visit after any
184  // failed combine which may have created a DAG node.
185  void clearAddedDanglingWorklistEntries() {
186  // Check any nodes added to the worklist to see if they are prunable.
187  while (!PruningList.empty()) {
188  auto *N = PruningList.pop_back_val();
189  if (N->use_empty())
190  recursivelyDeleteUnusedNodes(N);
191  }
192  }
193 
194  SDNode *getNextWorklistEntry() {
195  // Before we do any work, remove nodes that are not in use.
196  clearAddedDanglingWorklistEntries();
197  SDNode *N = nullptr;
198  // The Worklist holds the SDNodes in order, but it may contain null
199  // entries.
200  while (!N && !Worklist.empty()) {
201  N = Worklist.pop_back_val();
202  }
203 
204  if (N) {
205  bool GoodWorklistEntry = WorklistMap.erase(N);
206  (void)GoodWorklistEntry;
207  assert(GoodWorklistEntry &&
208  "Found a worklist entry without a corresponding map entry!");
209  }
210  return N;
211  }
212 
213  /// Call the node-specific routine that folds each particular type of node.
214  SDValue visit(SDNode *N);
215 
216  public:
217  DAGCombiner(SelectionDAG &D, AliasAnalysis *AA, CodeGenOpt::Level OL)
218  : DAG(D), TLI(D.getTargetLoweringInfo()), Level(BeforeLegalizeTypes),
219  OptLevel(OL), AA(AA) {
220  ForCodeSize = DAG.getMachineFunction().getFunction().hasOptSize();
221 
222  MaximumLegalStoreInBits = 0;
223  for (MVT VT : MVT::all_valuetypes())
224  if (EVT(VT).isSimple() && VT != MVT::Other &&
225  TLI.isTypeLegal(EVT(VT)) &&
226  VT.getSizeInBits() >= MaximumLegalStoreInBits)
227  MaximumLegalStoreInBits = VT.getSizeInBits();
228  }
229 
230  void ConsiderForPruning(SDNode *N) {
231  // Mark this for potential pruning.
232  PruningList.insert(N);
233  }
234 
235  /// Add to the worklist making sure its instance is at the back (next to be
236  /// processed.)
237  void AddToWorklist(SDNode *N) {
239  "Deleted Node added to Worklist");
240 
241  // Skip handle nodes as they can't usefully be combined and confuse the
242  // zero-use deletion strategy.
243  if (N->getOpcode() == ISD::HANDLENODE)
244  return;
245 
246  ConsiderForPruning(N);
247 
248  if (WorklistMap.insert(std::make_pair(N, Worklist.size())).second)
249  Worklist.push_back(N);
250  }
251 
252  /// Remove all instances of N from the worklist.
253  void removeFromWorklist(SDNode *N) {
254  CombinedNodes.erase(N);
255  PruningList.remove(N);
256  StoreRootCountMap.erase(N);
257 
258  auto It = WorklistMap.find(N);
259  if (It == WorklistMap.end())
260  return; // Not in the worklist.
261 
262  // Null out the entry rather than erasing it to avoid a linear operation.
263  Worklist[It->second] = nullptr;
264  WorklistMap.erase(It);
265  }
266 
267  void deleteAndRecombine(SDNode *N);
268  bool recursivelyDeleteUnusedNodes(SDNode *N);
269 
270  /// Replaces all uses of the results of one DAG node with new values.
271  SDValue CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
272  bool AddTo = true);
273 
274  /// Replaces all uses of the results of one DAG node with new values.
275  SDValue CombineTo(SDNode *N, SDValue Res, bool AddTo = true) {
276  return CombineTo(N, &Res, 1, AddTo);
277  }
278 
279  /// Replaces all uses of the results of one DAG node with new values.
280  SDValue CombineTo(SDNode *N, SDValue Res0, SDValue Res1,
281  bool AddTo = true) {
282  SDValue To[] = { Res0, Res1 };
283  return CombineTo(N, To, 2, AddTo);
284  }
285 
286  void CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO);
287 
288  private:
289  unsigned MaximumLegalStoreInBits;
290 
291  /// Check the specified integer node value to see if it can be simplified or
292  /// if things it uses can be simplified by bit propagation.
293  /// If so, return true.
294  bool SimplifyDemandedBits(SDValue Op) {
295  unsigned BitWidth = Op.getScalarValueSizeInBits();
297  return SimplifyDemandedBits(Op, DemandedBits);
298  }
299 
300  bool SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits) {
301  EVT VT = Op.getValueType();
302  unsigned NumElts = VT.isVector() ? VT.getVectorNumElements() : 1;
303  APInt DemandedElts = APInt::getAllOnesValue(NumElts);
304  return SimplifyDemandedBits(Op, DemandedBits, DemandedElts);
305  }
306 
307  /// Check the specified vector node value to see if it can be simplified or
308  /// if things it uses can be simplified as it only uses some of the
309  /// elements. If so, return true.
310  bool SimplifyDemandedVectorElts(SDValue Op) {
311  unsigned NumElts = Op.getValueType().getVectorNumElements();
312  APInt DemandedElts = APInt::getAllOnesValue(NumElts);
313  return SimplifyDemandedVectorElts(Op, DemandedElts);
314  }
315 
316  bool SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits,
317  const APInt &DemandedElts);
318  bool SimplifyDemandedVectorElts(SDValue Op, const APInt &DemandedElts,
319  bool AssumeSingleUse = false);
320 
321  bool CombineToPreIndexedLoadStore(SDNode *N);
322  bool CombineToPostIndexedLoadStore(SDNode *N);
323  SDValue SplitIndexingFromLoad(LoadSDNode *LD);
324  bool SliceUpLoad(SDNode *N);
325 
326  // Scalars have size 0 to distinguish from singleton vectors.
327  SDValue ForwardStoreValueToDirectLoad(LoadSDNode *LD);
328  bool getTruncatedStoreValue(StoreSDNode *ST, SDValue &Val);
329  bool extendLoadedValueToExtension(LoadSDNode *LD, SDValue &Val);
330 
331  /// Replace an ISD::EXTRACT_VECTOR_ELT of a load with a narrowed
332  /// load.
333  ///
334  /// \param EVE ISD::EXTRACT_VECTOR_ELT to be replaced.
335  /// \param InVecVT type of the input vector to EVE with bitcasts resolved.
336  /// \param EltNo index of the vector element to load.
337  /// \param OriginalLoad load that EVE came from to be replaced.
338  /// \returns EVE on success SDValue() on failure.
339  SDValue scalarizeExtractedVectorLoad(SDNode *EVE, EVT InVecVT,
340  SDValue EltNo,
341  LoadSDNode *OriginalLoad);
342  void ReplaceLoadWithPromotedLoad(SDNode *Load, SDNode *ExtLoad);
343  SDValue PromoteOperand(SDValue Op, EVT PVT, bool &Replace);
344  SDValue SExtPromoteOperand(SDValue Op, EVT PVT);
345  SDValue ZExtPromoteOperand(SDValue Op, EVT PVT);
346  SDValue PromoteIntBinOp(SDValue Op);
347  SDValue PromoteIntShiftOp(SDValue Op);
348  SDValue PromoteExtend(SDValue Op);
349  bool PromoteLoad(SDValue Op);
350 
351  /// Call the node-specific routine that knows how to fold each
352  /// particular type of node. If that doesn't do anything, try the
353  /// target-specific DAG combines.
354  SDValue combine(SDNode *N);
355 
356  // Visitation implementation - Implement dag node combining for different
357  // node types. The semantics are as follows:
358  // Return Value:
359  // SDValue.getNode() == 0 - No change was made
360  // SDValue.getNode() == N - N was replaced, is dead and has been handled.
361  // otherwise - N should be replaced by the returned Operand.
362  //
363  SDValue visitTokenFactor(SDNode *N);
364  SDValue visitMERGE_VALUES(SDNode *N);
365  SDValue visitADD(SDNode *N);
366  SDValue visitADDLike(SDNode *N);
367  SDValue visitADDLikeCommutative(SDValue N0, SDValue N1, SDNode *LocReference);
368  SDValue visitSUB(SDNode *N);
369  SDValue visitADDSAT(SDNode *N);
370  SDValue visitSUBSAT(SDNode *N);
371  SDValue visitADDC(SDNode *N);
372  SDValue visitADDO(SDNode *N);
373  SDValue visitUADDOLike(SDValue N0, SDValue N1, SDNode *N);
374  SDValue visitSUBC(SDNode *N);
375  SDValue visitSUBO(SDNode *N);
376  SDValue visitADDE(SDNode *N);
377  SDValue visitADDCARRY(SDNode *N);
378  SDValue visitADDCARRYLike(SDValue N0, SDValue N1, SDValue CarryIn, SDNode *N);
379  SDValue visitSUBE(SDNode *N);
380  SDValue visitSUBCARRY(SDNode *N);
381  SDValue visitMUL(SDNode *N);
382  SDValue visitMULFIX(SDNode *N);
383  SDValue useDivRem(SDNode *N);
384  SDValue visitSDIV(SDNode *N);
385  SDValue visitSDIVLike(SDValue N0, SDValue N1, SDNode *N);
386  SDValue visitUDIV(SDNode *N);
387  SDValue visitUDIVLike(SDValue N0, SDValue N1, SDNode *N);
388  SDValue visitREM(SDNode *N);
389  SDValue visitMULHU(SDNode *N);
390  SDValue visitMULHS(SDNode *N);
391  SDValue visitSMUL_LOHI(SDNode *N);
392  SDValue visitUMUL_LOHI(SDNode *N);
393  SDValue visitMULO(SDNode *N);
394  SDValue visitIMINMAX(SDNode *N);
395  SDValue visitAND(SDNode *N);
396  SDValue visitANDLike(SDValue N0, SDValue N1, SDNode *N);
397  SDValue visitOR(SDNode *N);
398  SDValue visitORLike(SDValue N0, SDValue N1, SDNode *N);
399  SDValue visitXOR(SDNode *N);
400  SDValue SimplifyVBinOp(SDNode *N);
401  SDValue visitSHL(SDNode *N);
402  SDValue visitSRA(SDNode *N);
403  SDValue visitSRL(SDNode *N);
404  SDValue visitFunnelShift(SDNode *N);
405  SDValue visitRotate(SDNode *N);
406  SDValue visitABS(SDNode *N);
407  SDValue visitBSWAP(SDNode *N);
408  SDValue visitBITREVERSE(SDNode *N);
409  SDValue visitCTLZ(SDNode *N);
410  SDValue visitCTLZ_ZERO_UNDEF(SDNode *N);
411  SDValue visitCTTZ(SDNode *N);
412  SDValue visitCTTZ_ZERO_UNDEF(SDNode *N);
413  SDValue visitCTPOP(SDNode *N);
414  SDValue visitSELECT(SDNode *N);
415  SDValue visitVSELECT(SDNode *N);
416  SDValue visitSELECT_CC(SDNode *N);
417  SDValue visitSETCC(SDNode *N);
418  SDValue visitSETCCCARRY(SDNode *N);
419  SDValue visitSIGN_EXTEND(SDNode *N);
420  SDValue visitZERO_EXTEND(SDNode *N);
421  SDValue visitANY_EXTEND(SDNode *N);
422  SDValue visitAssertExt(SDNode *N);
423  SDValue visitSIGN_EXTEND_INREG(SDNode *N);
424  SDValue visitSIGN_EXTEND_VECTOR_INREG(SDNode *N);
425  SDValue visitZERO_EXTEND_VECTOR_INREG(SDNode *N);
426  SDValue visitTRUNCATE(SDNode *N);
427  SDValue visitBITCAST(SDNode *N);
428  SDValue visitBUILD_PAIR(SDNode *N);
429  SDValue visitFADD(SDNode *N);
430  SDValue visitFSUB(SDNode *N);
431  SDValue visitFMUL(SDNode *N);
432  SDValue visitFMA(SDNode *N);
433  SDValue visitFDIV(SDNode *N);
434  SDValue visitFREM(SDNode *N);
435  SDValue visitFSQRT(SDNode *N);
436  SDValue visitFCOPYSIGN(SDNode *N);
437  SDValue visitFPOW(SDNode *N);
438  SDValue visitSINT_TO_FP(SDNode *N);
439  SDValue visitUINT_TO_FP(SDNode *N);
440  SDValue visitFP_TO_SINT(SDNode *N);
441  SDValue visitFP_TO_UINT(SDNode *N);
442  SDValue visitFP_ROUND(SDNode *N);
443  SDValue visitFP_EXTEND(SDNode *N);
444  SDValue visitFNEG(SDNode *N);
445  SDValue visitFABS(SDNode *N);
446  SDValue visitFCEIL(SDNode *N);
447  SDValue visitFTRUNC(SDNode *N);
448  SDValue visitFFLOOR(SDNode *N);
449  SDValue visitFMINNUM(SDNode *N);
450  SDValue visitFMAXNUM(SDNode *N);
451  SDValue visitFMINIMUM(SDNode *N);
452  SDValue visitFMAXIMUM(SDNode *N);
453  SDValue visitBRCOND(SDNode *N);
454  SDValue visitBR_CC(SDNode *N);
455  SDValue visitLOAD(SDNode *N);
456 
457  SDValue replaceStoreChain(StoreSDNode *ST, SDValue BetterChain);
458  SDValue replaceStoreOfFPConstant(StoreSDNode *ST);
459 
460  SDValue visitSTORE(SDNode *N);
461  SDValue visitLIFETIME_END(SDNode *N);
462  SDValue visitINSERT_VECTOR_ELT(SDNode *N);
463  SDValue visitEXTRACT_VECTOR_ELT(SDNode *N);
464  SDValue visitBUILD_VECTOR(SDNode *N);
465  SDValue visitCONCAT_VECTORS(SDNode *N);
466  SDValue visitEXTRACT_SUBVECTOR(SDNode *N);
467  SDValue visitVECTOR_SHUFFLE(SDNode *N);
468  SDValue visitSCALAR_TO_VECTOR(SDNode *N);
469  SDValue visitINSERT_SUBVECTOR(SDNode *N);
470  SDValue visitMLOAD(SDNode *N);
471  SDValue visitMSTORE(SDNode *N);
472  SDValue visitMGATHER(SDNode *N);
473  SDValue visitMSCATTER(SDNode *N);
474  SDValue visitFP_TO_FP16(SDNode *N);
475  SDValue visitFP16_TO_FP(SDNode *N);
476  SDValue visitVECREDUCE(SDNode *N);
477 
478  SDValue visitFADDForFMACombine(SDNode *N);
479  SDValue visitFSUBForFMACombine(SDNode *N);
480  SDValue visitFMULForFMADistributiveCombine(SDNode *N);
481 
482  SDValue XformToShuffleWithZero(SDNode *N);
483  bool reassociationCanBreakAddressingModePattern(unsigned Opc,
484  const SDLoc &DL, SDValue N0,
485  SDValue N1);
486  SDValue reassociateOpsCommutative(unsigned Opc, const SDLoc &DL, SDValue N0,
487  SDValue N1);
488  SDValue reassociateOps(unsigned Opc, const SDLoc &DL, SDValue N0,
489  SDValue N1, SDNodeFlags Flags);
490 
491  SDValue visitShiftByConstant(SDNode *N);
492 
493  SDValue foldSelectOfConstants(SDNode *N);
494  SDValue foldVSelectOfConstants(SDNode *N);
495  SDValue foldBinOpIntoSelect(SDNode *BO);
496  bool SimplifySelectOps(SDNode *SELECT, SDValue LHS, SDValue RHS);
497  SDValue hoistLogicOpWithSameOpcodeHands(SDNode *N);
498  SDValue SimplifySelect(const SDLoc &DL, SDValue N0, SDValue N1, SDValue N2);
499  SDValue SimplifySelectCC(const SDLoc &DL, SDValue N0, SDValue N1,
500  SDValue N2, SDValue N3, ISD::CondCode CC,
501  bool NotExtCompare = false);
502  SDValue convertSelectOfFPConstantsToLoadOffset(
503  const SDLoc &DL, SDValue N0, SDValue N1, SDValue N2, SDValue N3,
504  ISD::CondCode CC);
505  SDValue foldSelectCCToShiftAnd(const SDLoc &DL, SDValue N0, SDValue N1,
506  SDValue N2, SDValue N3, ISD::CondCode CC);
507  SDValue foldLogicOfSetCCs(bool IsAnd, SDValue N0, SDValue N1,
508  const SDLoc &DL);
509  SDValue unfoldMaskedMerge(SDNode *N);
510  SDValue unfoldExtremeBitClearingToShifts(SDNode *N);
511  SDValue SimplifySetCC(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond,
512  const SDLoc &DL, bool foldBooleans);
513  SDValue rebuildSetCC(SDValue N);
514 
515  bool isSetCCEquivalent(SDValue N, SDValue &LHS, SDValue &RHS,
516  SDValue &CC) const;
517  bool isOneUseSetCC(SDValue N) const;
518  bool isCheaperToUseNegatedFPOps(SDValue X, SDValue Y);
519 
520  SDValue SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp,
521  unsigned HiOp);
522  SDValue CombineConsecutiveLoads(SDNode *N, EVT VT);
523  SDValue CombineExtLoad(SDNode *N);
524  SDValue CombineZExtLogicopShiftLoad(SDNode *N);
525  SDValue combineRepeatedFPDivisors(SDNode *N);
526  SDValue combineInsertEltToShuffle(SDNode *N, unsigned InsIndex);
527  SDValue ConstantFoldBITCASTofBUILD_VECTOR(SDNode *, EVT);
528  SDValue BuildSDIV(SDNode *N);
529  SDValue BuildSDIVPow2(SDNode *N);
530  SDValue BuildUDIV(SDNode *N);
531  SDValue BuildLogBase2(SDValue V, const SDLoc &DL);
532  SDValue BuildDivEstimate(SDValue N, SDValue Op, SDNodeFlags Flags);
533  SDValue buildRsqrtEstimate(SDValue Op, SDNodeFlags Flags);
534  SDValue buildSqrtEstimate(SDValue Op, SDNodeFlags Flags);
535  SDValue buildSqrtEstimateImpl(SDValue Op, SDNodeFlags Flags, bool Recip);
536  SDValue buildSqrtNROneConst(SDValue Arg, SDValue Est, unsigned Iterations,
537  SDNodeFlags Flags, bool Reciprocal);
538  SDValue buildSqrtNRTwoConst(SDValue Arg, SDValue Est, unsigned Iterations,
539  SDNodeFlags Flags, bool Reciprocal);
540  SDValue MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
541  bool DemandHighBits = true);
542  SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
543  SDNode *MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
544  SDValue InnerPos, SDValue InnerNeg,
545  unsigned PosOpcode, unsigned NegOpcode,
546  const SDLoc &DL);
547  SDNode *MatchRotate(SDValue LHS, SDValue RHS, const SDLoc &DL);
548  SDValue MatchLoadCombine(SDNode *N);
549  SDValue MatchStoreCombine(StoreSDNode *N);
550  SDValue ReduceLoadWidth(SDNode *N);
551  SDValue ReduceLoadOpStoreWidth(SDNode *N);
553  SDValue TransformFPLoadStorePair(SDNode *N);
554  SDValue convertBuildVecZextToZext(SDNode *N);
555  SDValue reduceBuildVecExtToExtBuildVec(SDNode *N);
556  SDValue reduceBuildVecToShuffle(SDNode *N);
557  SDValue createBuildVecShuffle(const SDLoc &DL, SDNode *N,
558  ArrayRef<int> VectorMask, SDValue VecIn1,
559  SDValue VecIn2, unsigned LeftIdx,
560  bool DidSplitVec);
561  SDValue matchVSelectOpSizesWithSetCC(SDNode *Cast);
562 
563  /// Walk up chain skipping non-aliasing memory nodes,
564  /// looking for aliasing nodes and adding them to the Aliases vector.
565  void GatherAllAliases(SDNode *N, SDValue OriginalChain,
566  SmallVectorImpl<SDValue> &Aliases);
567 
568  /// Return true if there is any possibility that the two addresses overlap.
569  bool isAlias(SDNode *Op0, SDNode *Op1) const;
570 
571  /// Walk up chain skipping non-aliasing memory nodes, looking for a better
572  /// chain (aliasing node.)
573  SDValue FindBetterChain(SDNode *N, SDValue Chain);
574 
575  /// Try to replace a store and any possibly adjacent stores on
576  /// consecutive chains with better chains. Return true only if St is
577  /// replaced.
578  ///
579  /// Notice that other chains may still be replaced even if the function
580  /// returns false.
581  bool findBetterNeighborChains(StoreSDNode *St);
582 
583  // Helper for findBetterNeighborChains. Walk up store chain add additional
584  // chained stores that do not overlap and can be parallelized.
585  bool parallelizeChainedStores(StoreSDNode *St);
586 
587  /// Holds a pointer to an LSBaseSDNode as well as information on where it
588  /// is located in a sequence of memory operations connected by a chain.
589  struct MemOpLink {
590  // Ptr to the mem node.
591  LSBaseSDNode *MemNode;
592 
593  // Offset from the base ptr.
594  int64_t OffsetFromBase;
595 
596  MemOpLink(LSBaseSDNode *N, int64_t Offset)
597  : MemNode(N), OffsetFromBase(Offset) {}
598  };
599 
600  /// This is a helper function for visitMUL to check the profitability
601  /// of folding (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2).
602  /// MulNode is the original multiply, AddNode is (add x, c1),
603  /// and ConstNode is c2.
604  bool isMulAddWithConstProfitable(SDNode *MulNode,
605  SDValue &AddNode,
606  SDValue &ConstNode);
607 
608  /// This is a helper function for visitAND and visitZERO_EXTEND. Returns
609  /// true if the (and (load x) c) pattern matches an extload. ExtVT returns
610  /// the type of the loaded value to be extended.
611  bool isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
612  EVT LoadResultTy, EVT &ExtVT);
613 
614  /// Helper function to calculate whether the given Load/Store can have its
615  /// width reduced to ExtVT.
616  bool isLegalNarrowLdSt(LSBaseSDNode *LDSTN, ISD::LoadExtType ExtType,
617  EVT &MemVT, unsigned ShAmt = 0);
618 
619  /// Used by BackwardsPropagateMask to find suitable loads.
620  bool SearchForAndLoads(SDNode *N, SmallVectorImpl<LoadSDNode*> &Loads,
621  SmallPtrSetImpl<SDNode*> &NodesWithConsts,
622  ConstantSDNode *Mask, SDNode *&NodeToMask);
623  /// Attempt to propagate a given AND node back to load leaves so that they
624  /// can be combined into narrow loads.
625  bool BackwardsPropagateMask(SDNode *N, SelectionDAG &DAG);
626 
627  /// Helper function for MergeConsecutiveStores which merges the
628  /// component store chains.
629  SDValue getMergeStoreChains(SmallVectorImpl<MemOpLink> &StoreNodes,
630  unsigned NumStores);
631 
632  /// This is a helper function for MergeConsecutiveStores. When the
633  /// source elements of the consecutive stores are all constants or
634  /// all extracted vector elements, try to merge them into one
635  /// larger store introducing bitcasts if necessary. \return True
636  /// if a merged store was created.
637  bool MergeStoresOfConstantsOrVecElts(SmallVectorImpl<MemOpLink> &StoreNodes,
638  EVT MemVT, unsigned NumStores,
639  bool IsConstantSrc, bool UseVector,
640  bool UseTrunc);
641 
642  /// This is a helper function for MergeConsecutiveStores. Stores
643  /// that potentially may be merged with St are placed in
644  /// StoreNodes. RootNode is a chain predecessor to all store
645  /// candidates.
646  void getStoreMergeCandidates(StoreSDNode *St,
647  SmallVectorImpl<MemOpLink> &StoreNodes,
648  SDNode *&Root);
649 
650  /// Helper function for MergeConsecutiveStores. Checks if
651  /// candidate stores have indirect dependency through their
652  /// operands. RootNode is the predecessor to all stores calculated
653  /// by getStoreMergeCandidates and is used to prune the dependency check.
654  /// \return True if safe to merge.
655  bool checkMergeStoreCandidatesForDependencies(
656  SmallVectorImpl<MemOpLink> &StoreNodes, unsigned NumStores,
657  SDNode *RootNode);
658 
659  /// Merge consecutive store operations into a wide store.
660  /// This optimization uses wide integers or vectors when possible.
661  /// \return number of stores that were merged into a merged store (the
662  /// affected nodes are stored as a prefix in \p StoreNodes).
663  bool MergeConsecutiveStores(StoreSDNode *St);
664 
665  /// Try to transform a truncation where C is a constant:
666  /// (trunc (and X, C)) -> (and (trunc X), (trunc C))
667  ///
668  /// \p N needs to be a truncation and its first operand an AND. Other
669  /// requirements are checked by the function (e.g. that trunc is
670  /// single-use) and if missed an empty SDValue is returned.
671  SDValue distributeTruncateThroughAnd(SDNode *N);
672 
673  /// Helper function to determine whether the target supports operation
674  /// given by \p Opcode for type \p VT, that is, whether the operation
675  /// is legal or custom before legalizing operations, and whether is
676  /// legal (but not custom) after legalization.
677  bool hasOperation(unsigned Opcode, EVT VT) {
678  if (LegalOperations)
679  return TLI.isOperationLegal(Opcode, VT);
680  return TLI.isOperationLegalOrCustom(Opcode, VT);
681  }
682 
683  public:
684  /// Runs the dag combiner on all nodes in the work list
685  void Run(CombineLevel AtLevel);
686 
687  SelectionDAG &getDAG() const { return DAG; }
688 
689  /// Returns a type large enough to hold any valid shift amount - before type
690  /// legalization these can be huge.
691  EVT getShiftAmountTy(EVT LHSTy) {
692  assert(LHSTy.isInteger() && "Shift amount is not an integer type!");
693  return TLI.getShiftAmountTy(LHSTy, DAG.getDataLayout(), LegalTypes);
694  }
695 
696  /// This method returns true if we are running before type legalization or
697  /// if the specified VT is legal.
698  bool isTypeLegal(const EVT &VT) {
699  if (!LegalTypes) return true;
700  return TLI.isTypeLegal(VT);
701  }
702 
703  /// Convenience wrapper around TargetLowering::getSetCCResultType
704  EVT getSetCCResultType(EVT VT) const {
705  return TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
706  }
707 
708  void ExtendSetCCUses(const SmallVectorImpl<SDNode *> &SetCCs,
709  SDValue OrigLoad, SDValue ExtLoad,
711  };
712 
713 /// This class is a DAGUpdateListener that removes any deleted
714 /// nodes from the worklist.
715 class WorklistRemover : public SelectionDAG::DAGUpdateListener {
716  DAGCombiner &DC;
717 
718 public:
719  explicit WorklistRemover(DAGCombiner &dc)
720  : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
721 
722  void NodeDeleted(SDNode *N, SDNode *E) override {
723  DC.removeFromWorklist(N);
724  }
725 };
726 
727 class WorklistInserter : public SelectionDAG::DAGUpdateListener {
728  DAGCombiner &DC;
729 
730 public:
731  explicit WorklistInserter(DAGCombiner &dc)
732  : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
733 
734  // FIXME: Ideally we could add N to the worklist, but this causes exponential
735  // compile time costs in large DAGs, e.g. Halide.
736  void NodeInserted(SDNode *N) override { DC.ConsiderForPruning(N); }
737 };
738 
739 } // end anonymous namespace
740 
741 //===----------------------------------------------------------------------===//
742 // TargetLowering::DAGCombinerInfo implementation
743 //===----------------------------------------------------------------------===//
744 
746  ((DAGCombiner*)DC)->AddToWorklist(N);
747 }
748 
750 CombineTo(SDNode *N, ArrayRef<SDValue> To, bool AddTo) {
751  return ((DAGCombiner*)DC)->CombineTo(N, &To[0], To.size(), AddTo);
752 }
753 
755 CombineTo(SDNode *N, SDValue Res, bool AddTo) {
756  return ((DAGCombiner*)DC)->CombineTo(N, Res, AddTo);
757 }
758 
760 CombineTo(SDNode *N, SDValue Res0, SDValue Res1, bool AddTo) {
761  return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1, AddTo);
762 }
763 
766  return ((DAGCombiner*)DC)->CommitTargetLoweringOpt(TLO);
767 }
768 
769 //===----------------------------------------------------------------------===//
770 // Helper Functions
771 //===----------------------------------------------------------------------===//
772 
773 void DAGCombiner::deleteAndRecombine(SDNode *N) {
774  removeFromWorklist(N);
775 
776  // If the operands of this node are only used by the node, they will now be
777  // dead. Make sure to re-visit them and recursively delete dead nodes.
778  for (const SDValue &Op : N->ops())
779  // For an operand generating multiple values, one of the values may
780  // become dead allowing further simplification (e.g. split index
781  // arithmetic from an indexed load).
782  if (Op->hasOneUse() || Op->getNumValues() > 1)
783  AddToWorklist(Op.getNode());
784 
785  DAG.DeleteNode(N);
786 }
787 
788 /// Return 1 if we can compute the negated form of the specified expression for
789 /// the same cost as the expression itself, or 2 if we can compute the negated
790 /// form more cheaply than the expression itself.
791 static char isNegatibleForFree(SDValue Op, bool LegalOperations,
792  const TargetLowering &TLI,
793  const TargetOptions *Options,
794  bool ForCodeSize,
795  unsigned Depth = 0) {
796  // fneg is removable even if it has multiple uses.
797  if (Op.getOpcode() == ISD::FNEG)
798  return 2;
799 
800  // Don't allow anything with multiple uses unless we know it is free.
801  EVT VT = Op.getValueType();
802  const SDNodeFlags Flags = Op->getFlags();
803  if (!Op.hasOneUse() &&
804  !(Op.getOpcode() == ISD::FP_EXTEND &&
805  TLI.isFPExtFree(VT, Op.getOperand(0).getValueType())))
806  return 0;
807 
808  // Don't recurse exponentially.
809  if (Depth > 6)
810  return 0;
811 
812  switch (Op.getOpcode()) {
813  default: return false;
814  case ISD::ConstantFP: {
815  if (!LegalOperations)
816  return 1;
817 
818  // Don't invert constant FP values after legalization unless the target says
819  // the negated constant is legal.
820  return TLI.isOperationLegal(ISD::ConstantFP, VT) ||
821  TLI.isFPImmLegal(neg(cast<ConstantFPSDNode>(Op)->getValueAPF()), VT,
822  ForCodeSize);
823  }
824  case ISD::BUILD_VECTOR: {
825  // Only permit BUILD_VECTOR of constants.
826  if (llvm::any_of(Op->op_values(), [&](SDValue N) {
827  return !N.isUndef() && !isa<ConstantFPSDNode>(N);
828  }))
829  return 0;
830  if (!LegalOperations)
831  return 1;
832  if (TLI.isOperationLegal(ISD::ConstantFP, VT) &&
834  return 1;
835  return llvm::all_of(Op->op_values(), [&](SDValue N) {
836  return N.isUndef() ||
837  TLI.isFPImmLegal(neg(cast<ConstantFPSDNode>(N)->getValueAPF()), VT,
838  ForCodeSize);
839  });
840  }
841  case ISD::FADD:
842  if (!Options->NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
843  return 0;
844 
845  // After operation legalization, it might not be legal to create new FSUBs.
846  if (LegalOperations && !TLI.isOperationLegalOrCustom(ISD::FSUB, VT))
847  return 0;
848 
849  // fold (fneg (fadd A, B)) -> (fsub (fneg A), B)
850  if (char V = isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI,
851  Options, ForCodeSize, Depth + 1))
852  return V;
853  // fold (fneg (fadd A, B)) -> (fsub (fneg B), A)
854  return isNegatibleForFree(Op.getOperand(1), LegalOperations, TLI, Options,
855  ForCodeSize, Depth + 1);
856  case ISD::FSUB:
857  // We can't turn -(A-B) into B-A when we honor signed zeros.
858  if (!Options->NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
859  return 0;
860 
861  // fold (fneg (fsub A, B)) -> (fsub B, A)
862  return 1;
863 
864  case ISD::FMUL:
865  case ISD::FDIV:
866  // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y) or (fmul X, (fneg Y))
867  if (char V = isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI,
868  Options, ForCodeSize, Depth + 1))
869  return V;
870 
871  // Ignore X * 2.0 because that is expected to be canonicalized to X + X.
872  if (auto *C = isConstOrConstSplatFP(Op.getOperand(1)))
873  if (C->isExactlyValue(2.0) && Op.getOpcode() == ISD::FMUL)
874  return 0;
875 
876  return isNegatibleForFree(Op.getOperand(1), LegalOperations, TLI, Options,
877  ForCodeSize, Depth + 1);
878 
879  case ISD::FMA:
880  case ISD::FMAD: {
881  if (!Options->NoSignedZerosFPMath && !Flags.hasNoSignedZeros())
882  return 0;
883 
884  // fold (fneg (fma X, Y, Z)) -> (fma (fneg X), Y, (fneg Z))
885  // fold (fneg (fma X, Y, Z)) -> (fma X, (fneg Y), (fneg Z))
886  char V2 = isNegatibleForFree(Op.getOperand(2), LegalOperations, TLI,
887  Options, ForCodeSize, Depth + 1);
888  if (!V2)
889  return 0;
890 
891  // One of Op0/Op1 must be cheaply negatible, then select the cheapest.
892  char V0 = isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI,
893  Options, ForCodeSize, Depth + 1);
894  char V1 = isNegatibleForFree(Op.getOperand(1), LegalOperations, TLI,
895  Options, ForCodeSize, Depth + 1);
896  char V01 = std::max(V0, V1);
897  return V01 ? std::max(V01, V2) : 0;
898  }
899 
900  case ISD::FP_EXTEND:
901  case ISD::FP_ROUND:
902  case ISD::FSIN:
903  return isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI, Options,
904  ForCodeSize, Depth + 1);
905  }
906 }
907 
908 /// If isNegatibleForFree returns true, return the newly negated expression.
910  bool LegalOperations, bool ForCodeSize,
911  unsigned Depth = 0) {
912  // fneg is removable even if it has multiple uses.
913  if (Op.getOpcode() == ISD::FNEG)
914  return Op.getOperand(0);
915 
916  assert(Depth <= 6 && "GetNegatedExpression doesn't match isNegatibleForFree");
917  const TargetOptions &Options = DAG.getTarget().Options;
918  const SDNodeFlags Flags = Op->getFlags();
919 
920  switch (Op.getOpcode()) {
921  default: llvm_unreachable("Unknown code");
922  case ISD::ConstantFP: {
923  APFloat V = cast<ConstantFPSDNode>(Op)->getValueAPF();
924  V.changeSign();
925  return DAG.getConstantFP(V, SDLoc(Op), Op.getValueType());
926  }
927  case ISD::BUILD_VECTOR: {
929  for (SDValue C : Op->op_values()) {
930  if (C.isUndef()) {
931  Ops.push_back(C);
932  continue;
933  }
934  APFloat V = cast<ConstantFPSDNode>(C)->getValueAPF();
935  V.changeSign();
936  Ops.push_back(DAG.getConstantFP(V, SDLoc(Op), C.getValueType()));
937  }
938  return DAG.getBuildVector(Op.getValueType(), SDLoc(Op), Ops);
939  }
940  case ISD::FADD:
941  assert((Options.NoSignedZerosFPMath || Flags.hasNoSignedZeros()) &&
942  "Expected NSZ fp-flag");
943 
944  // fold (fneg (fadd A, B)) -> (fsub (fneg A), B)
945  if (isNegatibleForFree(Op.getOperand(0), LegalOperations,
946  DAG.getTargetLoweringInfo(), &Options, ForCodeSize,
947  Depth + 1))
948  return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
949  GetNegatedExpression(Op.getOperand(0), DAG,
950  LegalOperations, ForCodeSize,
951  Depth + 1),
952  Op.getOperand(1), Flags);
953  // fold (fneg (fadd A, B)) -> (fsub (fneg B), A)
954  return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
955  GetNegatedExpression(Op.getOperand(1), DAG,
956  LegalOperations, ForCodeSize,
957  Depth + 1),
958  Op.getOperand(0), Flags);
959  case ISD::FSUB:
960  // fold (fneg (fsub 0, B)) -> B
961  if (ConstantFPSDNode *N0CFP =
962  isConstOrConstSplatFP(Op.getOperand(0), /*AllowUndefs*/ true))
963  if (N0CFP->isZero())
964  return Op.getOperand(1);
965 
966  // fold (fneg (fsub A, B)) -> (fsub B, A)
967  return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
968  Op.getOperand(1), Op.getOperand(0), Flags);
969 
970  case ISD::FMUL:
971  case ISD::FDIV:
972  // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y)
973  if (isNegatibleForFree(Op.getOperand(0), LegalOperations,
974  DAG.getTargetLoweringInfo(), &Options, ForCodeSize,
975  Depth + 1))
976  return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
977  GetNegatedExpression(Op.getOperand(0), DAG,
978  LegalOperations, ForCodeSize,
979  Depth + 1),
980  Op.getOperand(1), Flags);
981 
982  // fold (fneg (fmul X, Y)) -> (fmul X, (fneg Y))
983  return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
984  Op.getOperand(0),
985  GetNegatedExpression(Op.getOperand(1), DAG,
986  LegalOperations, ForCodeSize,
987  Depth + 1), Flags);
988 
989  case ISD::FMA:
990  case ISD::FMAD: {
991  assert((Options.NoSignedZerosFPMath || Flags.hasNoSignedZeros()) &&
992  "Expected NSZ fp-flag");
993 
994  SDValue Neg2 = GetNegatedExpression(Op.getOperand(2), DAG, LegalOperations,
995  ForCodeSize, Depth + 1);
996 
997  char V0 = isNegatibleForFree(Op.getOperand(0), LegalOperations,
998  DAG.getTargetLoweringInfo(), &Options,
999  ForCodeSize, Depth + 1);
1000  char V1 = isNegatibleForFree(Op.getOperand(1), LegalOperations,
1001  DAG.getTargetLoweringInfo(), &Options,
1002  ForCodeSize, Depth + 1);
1003  if (V0 >= V1) {
1004  // fold (fneg (fma X, Y, Z)) -> (fma (fneg X), Y, (fneg Z))
1006  Op.getOperand(0), DAG, LegalOperations, ForCodeSize, Depth + 1);
1007  return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(), Neg0,
1008  Op.getOperand(1), Neg2, Flags);
1009  }
1010 
1011  // fold (fneg (fma X, Y, Z)) -> (fma X, (fneg Y), (fneg Z))
1012  SDValue Neg1 = GetNegatedExpression(Op.getOperand(1), DAG, LegalOperations,
1013  ForCodeSize, Depth + 1);
1014  return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
1015  Op.getOperand(0), Neg1, Neg2, Flags);
1016  }
1017 
1018  case ISD::FP_EXTEND:
1019  case ISD::FSIN:
1020  return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
1021  GetNegatedExpression(Op.getOperand(0), DAG,
1022  LegalOperations, ForCodeSize,
1023  Depth + 1));
1024  case ISD::FP_ROUND:
1025  return DAG.getNode(ISD::FP_ROUND, SDLoc(Op), Op.getValueType(),
1026  GetNegatedExpression(Op.getOperand(0), DAG,
1027  LegalOperations, ForCodeSize,
1028  Depth + 1),
1029  Op.getOperand(1));
1030  }
1031 }
1032 
1033 // APInts must be the same size for most operations, this helper
1034 // function zero extends the shorter of the pair so that they match.
1035 // We provide an Offset so that we can create bitwidths that won't overflow.
1036 static void zeroExtendToMatch(APInt &LHS, APInt &RHS, unsigned Offset = 0) {
1037  unsigned Bits = Offset + std::max(LHS.getBitWidth(), RHS.getBitWidth());
1038  LHS = LHS.zextOrSelf(Bits);
1039  RHS = RHS.zextOrSelf(Bits);
1040 }
1041 
1042 // Return true if this node is a setcc, or is a select_cc
1043 // that selects between the target values used for true and false, making it
1044 // equivalent to a setcc. Also, set the incoming LHS, RHS, and CC references to
1045 // the appropriate nodes based on the type of node we are checking. This
1046 // simplifies life a bit for the callers.
1047 bool DAGCombiner::isSetCCEquivalent(SDValue N, SDValue &LHS, SDValue &RHS,
1048  SDValue &CC) const {
1049  if (N.getOpcode() == ISD::SETCC) {
1050  LHS = N.getOperand(0);
1051  RHS = N.getOperand(1);
1052  CC = N.getOperand(2);
1053  return true;
1054  }
1055 
1056  if (N.getOpcode() != ISD::SELECT_CC ||
1057  !TLI.isConstTrueVal(N.getOperand(2).getNode()) ||
1058  !TLI.isConstFalseVal(N.getOperand(3).getNode()))
1059  return false;
1060 
1061  if (TLI.getBooleanContents(N.getValueType()) ==
1063  return false;
1064 
1065  LHS = N.getOperand(0);
1066  RHS = N.getOperand(1);
1067  CC = N.getOperand(4);
1068  return true;
1069 }
1070 
1071 /// Return true if this is a SetCC-equivalent operation with only one use.
1072 /// If this is true, it allows the users to invert the operation for free when
1073 /// it is profitable to do so.
1074 bool DAGCombiner::isOneUseSetCC(SDValue N) const {
1075  SDValue N0, N1, N2;
1076  if (isSetCCEquivalent(N, N0, N1, N2) && N.getNode()->hasOneUse())
1077  return true;
1078  return false;
1079 }
1080 
1081 // Returns the SDNode if it is a constant float BuildVector
1082 // or constant float.
1084  if (isa<ConstantFPSDNode>(N))
1085  return N.getNode();
1087  return N.getNode();
1088  return nullptr;
1089 }
1090 
1091 // Determines if it is a constant integer or a build vector of constant
1092 // integers (and undefs).
1093 // Do not permit build vector implicit truncation.
1094 static bool isConstantOrConstantVector(SDValue N, bool NoOpaques = false) {
1095  if (ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N))
1096  return !(Const->isOpaque() && NoOpaques);
1097  if (N.getOpcode() != ISD::BUILD_VECTOR)
1098  return false;
1099  unsigned BitWidth = N.getScalarValueSizeInBits();
1100  for (const SDValue &Op : N->op_values()) {
1101  if (Op.isUndef())
1102  continue;
1104  if (!Const || Const->getAPIntValue().getBitWidth() != BitWidth ||
1105  (Const->isOpaque() && NoOpaques))
1106  return false;
1107  }
1108  return true;
1109 }
1110 
1111 // Determines if a BUILD_VECTOR is composed of all-constants possibly mixed with
1112 // undef's.
1113 static bool isAnyConstantBuildVector(SDValue V, bool NoOpaques = false) {
1114  if (V.getOpcode() != ISD::BUILD_VECTOR)
1115  return false;
1116  return isConstantOrConstantVector(V, NoOpaques) ||
1118 }
1119 
1120 bool DAGCombiner::reassociationCanBreakAddressingModePattern(unsigned Opc,
1121  const SDLoc &DL,
1122  SDValue N0,
1123  SDValue N1) {
1124  // Currently this only tries to ensure we don't undo the GEP splits done by
1125  // CodeGenPrepare when shouldConsiderGEPOffsetSplit is true. To ensure this,
1126  // we check if the following transformation would be problematic:
1127  // (load/store (add, (add, x, offset1), offset2)) ->
1128  // (load/store (add, x, offset1+offset2)).
1129 
1130  if (Opc != ISD::ADD || N0.getOpcode() != ISD::ADD)
1131  return false;
1132 
1133  if (N0.hasOneUse())
1134  return false;
1135 
1136  auto *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1));
1137  auto *C2 = dyn_cast<ConstantSDNode>(N1);
1138  if (!C1 || !C2)
1139  return false;
1140 
1141  const APInt &C1APIntVal = C1->getAPIntValue();
1142  const APInt &C2APIntVal = C2->getAPIntValue();
1143  if (C1APIntVal.getBitWidth() > 64 || C2APIntVal.getBitWidth() > 64)
1144  return false;
1145 
1146  const APInt CombinedValueIntVal = C1APIntVal + C2APIntVal;
1147  if (CombinedValueIntVal.getBitWidth() > 64)
1148  return false;
1149  const int64_t CombinedValue = CombinedValueIntVal.getSExtValue();
1150 
1151  for (SDNode *Node : N0->uses()) {
1152  auto LoadStore = dyn_cast<MemSDNode>(Node);
1153  if (LoadStore) {
1154  // Is x[offset2] already not a legal addressing mode? If so then
1155  // reassociating the constants breaks nothing (we test offset2 because
1156  // that's the one we hope to fold into the load or store).
1158  AM.HasBaseReg = true;
1159  AM.BaseOffs = C2APIntVal.getSExtValue();
1160  EVT VT = LoadStore->getMemoryVT();
1161  unsigned AS = LoadStore->getAddressSpace();
1162  Type *AccessTy = VT.getTypeForEVT(*DAG.getContext());
1163  if (!TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy, AS))
1164  continue;
1165 
1166  // Would x[offset1+offset2] still be a legal addressing mode?
1167  AM.BaseOffs = CombinedValue;
1168  if (!TLI.isLegalAddressingMode(DAG.getDataLayout(), AM, AccessTy, AS))
1169  return true;
1170  }
1171  }
1172 
1173  return false;
1174 }
1175 
1176 // Helper for DAGCombiner::reassociateOps. Try to reassociate an expression
1177 // such as (Opc N0, N1), if \p N0 is the same kind of operation as \p Opc.
1178 SDValue DAGCombiner::reassociateOpsCommutative(unsigned Opc, const SDLoc &DL,
1179  SDValue N0, SDValue N1) {
1180  EVT VT = N0.getValueType();
1181 
1182  if (N0.getOpcode() != Opc)
1183  return SDValue();
1184 
1185  // Don't reassociate reductions.
1186  if (N0->getFlags().hasVectorReduction())
1187  return SDValue();
1188 
1190  if (SDNode *C2 = DAG.isConstantIntBuildVectorOrConstantInt(N1)) {
1191  // Reassociate: (op (op x, c1), c2) -> (op x, (op c1, c2))
1192  if (SDValue OpNode = DAG.FoldConstantArithmetic(Opc, DL, VT, C1, C2))
1193  return DAG.getNode(Opc, DL, VT, N0.getOperand(0), OpNode);
1194  return SDValue();
1195  }
1196  if (N0.hasOneUse()) {
1197  // Reassociate: (op (op x, c1), y) -> (op (op x, y), c1)
1198  // iff (op x, c1) has one use
1199  SDValue OpNode = DAG.getNode(Opc, SDLoc(N0), VT, N0.getOperand(0), N1);
1200  if (!OpNode.getNode())
1201  return SDValue();
1202  return DAG.getNode(Opc, DL, VT, OpNode, N0.getOperand(1));
1203  }
1204  }
1205  return SDValue();
1206 }
1207 
1208 // Try to reassociate commutative binops.
1209 SDValue DAGCombiner::reassociateOps(unsigned Opc, const SDLoc &DL, SDValue N0,
1210  SDValue N1, SDNodeFlags Flags) {
1211  assert(TLI.isCommutativeBinOp(Opc) && "Operation not commutative.");
1212  // Don't reassociate reductions.
1213  if (Flags.hasVectorReduction())
1214  return SDValue();
1215 
1216  // Floating-point reassociation is not allowed without loose FP math.
1217  if (N0.getValueType().isFloatingPoint() ||
1219  if (!Flags.hasAllowReassociation() || !Flags.hasNoSignedZeros())
1220  return SDValue();
1221 
1222  if (SDValue Combined = reassociateOpsCommutative(Opc, DL, N0, N1))
1223  return Combined;
1224  if (SDValue Combined = reassociateOpsCommutative(Opc, DL, N1, N0))
1225  return Combined;
1226  return SDValue();
1227 }
1228 
1229 SDValue DAGCombiner::CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
1230  bool AddTo) {
1231  assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
1232  ++NodesCombined;
1233  LLVM_DEBUG(dbgs() << "\nReplacing.1 "; N->dump(&DAG); dbgs() << "\nWith: ";
1234  To[0].getNode()->dump(&DAG);
1235  dbgs() << " and " << NumTo - 1 << " other values\n");
1236  for (unsigned i = 0, e = NumTo; i != e; ++i)
1237  assert((!To[i].getNode() ||
1238  N->getValueType(i) == To[i].getValueType()) &&
1239  "Cannot combine value to value of different type!");
1240 
1241  WorklistRemover DeadNodes(*this);
1242  DAG.ReplaceAllUsesWith(N, To);
1243  if (AddTo) {
1244  // Push the new nodes and any users onto the worklist
1245  for (unsigned i = 0, e = NumTo; i != e; ++i) {
1246  if (To[i].getNode()) {
1247  AddToWorklist(To[i].getNode());
1248  AddUsersToWorklist(To[i].getNode());
1249  }
1250  }
1251  }
1252 
1253  // Finally, if the node is now dead, remove it from the graph. The node
1254  // may not be dead if the replacement process recursively simplified to
1255  // something else needing this node.
1256  if (N->use_empty())
1257  deleteAndRecombine(N);
1258  return SDValue(N, 0);
1259 }
1260 
1261 void DAGCombiner::
1262 CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO) {
1263  // Replace all uses. If any nodes become isomorphic to other nodes and
1264  // are deleted, make sure to remove them from our worklist.
1265  WorklistRemover DeadNodes(*this);
1266  DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New);
1267 
1268  // Push the new node and any (possibly new) users onto the worklist.
1269  AddToWorklist(TLO.New.getNode());
1270  AddUsersToWorklist(TLO.New.getNode());
1271 
1272  // Finally, if the node is now dead, remove it from the graph. The node
1273  // may not be dead if the replacement process recursively simplified to
1274  // something else needing this node.
1275  if (TLO.Old.getNode()->use_empty())
1276  deleteAndRecombine(TLO.Old.getNode());
1277 }
1278 
1279 /// Check the specified integer node value to see if it can be simplified or if
1280 /// things it uses can be simplified by bit propagation. If so, return true.
1281 bool DAGCombiner::SimplifyDemandedBits(SDValue Op, const APInt &DemandedBits,
1282  const APInt &DemandedElts) {
1283  TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
1284  KnownBits Known;
1285  if (!TLI.SimplifyDemandedBits(Op, DemandedBits, DemandedElts, Known, TLO))
1286  return false;
1287 
1288  // Revisit the node.
1289  AddToWorklist(Op.getNode());
1290 
1291  // Replace the old value with the new one.
1292  ++NodesCombined;
1293  LLVM_DEBUG(dbgs() << "\nReplacing.2 "; TLO.Old.getNode()->dump(&DAG);
1294  dbgs() << "\nWith: "; TLO.New.getNode()->dump(&DAG);
1295  dbgs() << '\n');
1296 
1297  CommitTargetLoweringOpt(TLO);
1298  return true;
1299 }
1300 
1301 /// Check the specified vector node value to see if it can be simplified or
1302 /// if things it uses can be simplified as it only uses some of the elements.
1303 /// If so, return true.
1304 bool DAGCombiner::SimplifyDemandedVectorElts(SDValue Op,
1305  const APInt &DemandedElts,
1306  bool AssumeSingleUse) {
1307  TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
1308  APInt KnownUndef, KnownZero;
1309  if (!TLI.SimplifyDemandedVectorElts(Op, DemandedElts, KnownUndef, KnownZero,
1310  TLO, 0, AssumeSingleUse))
1311  return false;
1312 
1313  // Revisit the node.
1314  AddToWorklist(Op.getNode());
1315 
1316  // Replace the old value with the new one.
1317  ++NodesCombined;
1318  LLVM_DEBUG(dbgs() << "\nReplacing.2 "; TLO.Old.getNode()->dump(&DAG);
1319  dbgs() << "\nWith: "; TLO.New.getNode()->dump(&DAG);
1320  dbgs() << '\n');
1321 
1322  CommitTargetLoweringOpt(TLO);
1323  return true;
1324 }
1325 
1326 void DAGCombiner::ReplaceLoadWithPromotedLoad(SDNode *Load, SDNode *ExtLoad) {
1327  SDLoc DL(Load);
1328  EVT VT = Load->getValueType(0);
1329  SDValue Trunc = DAG.getNode(ISD::TRUNCATE, DL, VT, SDValue(ExtLoad, 0));
1330 
1331  LLVM_DEBUG(dbgs() << "\nReplacing.9 "; Load->dump(&DAG); dbgs() << "\nWith: ";
1332  Trunc.getNode()->dump(&DAG); dbgs() << '\n');
1333  WorklistRemover DeadNodes(*this);
1334  DAG.ReplaceAllUsesOfValueWith(SDValue(Load, 0), Trunc);
1335  DAG.ReplaceAllUsesOfValueWith(SDValue(Load, 1), SDValue(ExtLoad, 1));
1336  deleteAndRecombine(Load);
1337  AddToWorklist(Trunc.getNode());
1338 }
1339 
1340 SDValue DAGCombiner::PromoteOperand(SDValue Op, EVT PVT, bool &Replace) {
1341  Replace = false;
1342  SDLoc DL(Op);
1343  if (ISD::isUNINDEXEDLoad(Op.getNode())) {
1344  LoadSDNode *LD = cast<LoadSDNode>(Op);
1345  EVT MemVT = LD->getMemoryVT();
1347  : LD->getExtensionType();
1348  Replace = true;
1349  return DAG.getExtLoad(ExtType, DL, PVT,
1350  LD->getChain(), LD->getBasePtr(),
1351  MemVT, LD->getMemOperand());
1352  }
1353 
1354  unsigned Opc = Op.getOpcode();
1355  switch (Opc) {
1356  default: break;
1357  case ISD::AssertSext:
1358  if (SDValue Op0 = SExtPromoteOperand(Op.getOperand(0), PVT))
1359  return DAG.getNode(ISD::AssertSext, DL, PVT, Op0, Op.getOperand(1));
1360  break;
1361  case ISD::AssertZext:
1362  if (SDValue Op0 = ZExtPromoteOperand(Op.getOperand(0), PVT))
1363  return DAG.getNode(ISD::AssertZext, DL, PVT, Op0, Op.getOperand(1));
1364  break;
1365  case ISD::Constant: {
1366  unsigned ExtOpc =
1368  return DAG.getNode(ExtOpc, DL, PVT, Op);
1369  }
1370  }
1371 
1372  if (!TLI.isOperationLegal(ISD::ANY_EXTEND, PVT))
1373  return SDValue();
1374  return DAG.getNode(ISD::ANY_EXTEND, DL, PVT, Op);
1375 }
1376 
1377 SDValue DAGCombiner::SExtPromoteOperand(SDValue Op, EVT PVT) {
1379  return SDValue();
1380  EVT OldVT = Op.getValueType();
1381  SDLoc DL(Op);
1382  bool Replace = false;
1383  SDValue NewOp = PromoteOperand(Op, PVT, Replace);
1384  if (!NewOp.getNode())
1385  return SDValue();
1386  AddToWorklist(NewOp.getNode());
1387 
1388  if (Replace)
1389  ReplaceLoadWithPromotedLoad(Op.getNode(), NewOp.getNode());
1390  return DAG.getNode(ISD::SIGN_EXTEND_INREG, DL, NewOp.getValueType(), NewOp,
1391  DAG.getValueType(OldVT));
1392 }
1393 
1394 SDValue DAGCombiner::ZExtPromoteOperand(SDValue Op, EVT PVT) {
1395  EVT OldVT = Op.getValueType();
1396  SDLoc DL(Op);
1397  bool Replace = false;
1398  SDValue NewOp = PromoteOperand(Op, PVT, Replace);
1399  if (!NewOp.getNode())
1400  return SDValue();
1401  AddToWorklist(NewOp.getNode());
1402 
1403  if (Replace)
1404  ReplaceLoadWithPromotedLoad(Op.getNode(), NewOp.getNode());
1405  return DAG.getZeroExtendInReg(NewOp, DL, OldVT);
1406 }
1407 
1408 /// Promote the specified integer binary operation if the target indicates it is
1409 /// beneficial. e.g. On x86, it's usually better to promote i16 operations to
1410 /// i32 since i16 instructions are longer.
1411 SDValue DAGCombiner::PromoteIntBinOp(SDValue Op) {
1412  if (!LegalOperations)
1413  return SDValue();
1414 
1415  EVT VT = Op.getValueType();
1416  if (VT.isVector() || !VT.isInteger())
1417  return SDValue();
1418 
1419  // If operation type is 'undesirable', e.g. i16 on x86, consider
1420  // promoting it.
1421  unsigned Opc = Op.getOpcode();
1422  if (TLI.isTypeDesirableForOp(Opc, VT))
1423  return SDValue();
1424 
1425  EVT PVT = VT;
1426  // Consult target whether it is a good idea to promote this operation and
1427  // what's the right type to promote it to.
1428  if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1429  assert(PVT != VT && "Don't know what type to promote to!");
1430 
1431  LLVM_DEBUG(dbgs() << "\nPromoting "; Op.getNode()->dump(&DAG));
1432 
1433  bool Replace0 = false;
1434  SDValue N0 = Op.getOperand(0);
1435  SDValue NN0 = PromoteOperand(N0, PVT, Replace0);
1436 
1437  bool Replace1 = false;
1438  SDValue N1 = Op.getOperand(1);
1439  SDValue NN1 = PromoteOperand(N1, PVT, Replace1);
1440  SDLoc DL(Op);
1441 
1442  SDValue RV =
1443  DAG.getNode(ISD::TRUNCATE, DL, VT, DAG.getNode(Opc, DL, PVT, NN0, NN1));
1444 
1445  // We are always replacing N0/N1's use in N and only need
1446  // additional replacements if there are additional uses.
1447  Replace0 &= !N0->hasOneUse();
1448  Replace1 &= (N0 != N1) && !N1->hasOneUse();
1449 
1450  // Combine Op here so it is preserved past replacements.
1451  CombineTo(Op.getNode(), RV);
1452 
1453  // If operands have a use ordering, make sure we deal with
1454  // predecessor first.
1455  if (Replace0 && Replace1 && N0.getNode()->isPredecessorOf(N1.getNode())) {
1456  std::swap(N0, N1);
1457  std::swap(NN0, NN1);
1458  }
1459 
1460  if (Replace0) {
1461  AddToWorklist(NN0.getNode());
1462  ReplaceLoadWithPromotedLoad(N0.getNode(), NN0.getNode());
1463  }
1464  if (Replace1) {
1465  AddToWorklist(NN1.getNode());
1466  ReplaceLoadWithPromotedLoad(N1.getNode(), NN1.getNode());
1467  }
1468  return Op;
1469  }
1470  return SDValue();
1471 }
1472 
1473 /// Promote the specified integer shift operation if the target indicates it is
1474 /// beneficial. e.g. On x86, it's usually better to promote i16 operations to
1475 /// i32 since i16 instructions are longer.
1476 SDValue DAGCombiner::PromoteIntShiftOp(SDValue Op) {
1477  if (!LegalOperations)
1478  return SDValue();
1479 
1480  EVT VT = Op.getValueType();
1481  if (VT.isVector() || !VT.isInteger())
1482  return SDValue();
1483 
1484  // If operation type is 'undesirable', e.g. i16 on x86, consider
1485  // promoting it.
1486  unsigned Opc = Op.getOpcode();
1487  if (TLI.isTypeDesirableForOp(Opc, VT))
1488  return SDValue();
1489 
1490  EVT PVT = VT;
1491  // Consult target whether it is a good idea to promote this operation and
1492  // what's the right type to promote it to.
1493  if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1494  assert(PVT != VT && "Don't know what type to promote to!");
1495 
1496  LLVM_DEBUG(dbgs() << "\nPromoting "; Op.getNode()->dump(&DAG));
1497 
1498  bool Replace = false;
1499  SDValue N0 = Op.getOperand(0);
1500  SDValue N1 = Op.getOperand(1);
1501  if (Opc == ISD::SRA)
1502  N0 = SExtPromoteOperand(N0, PVT);
1503  else if (Opc == ISD::SRL)
1504  N0 = ZExtPromoteOperand(N0, PVT);
1505  else
1506  N0 = PromoteOperand(N0, PVT, Replace);
1507 
1508  if (!N0.getNode())
1509  return SDValue();
1510 
1511  SDLoc DL(Op);
1512  SDValue RV =
1513  DAG.getNode(ISD::TRUNCATE, DL, VT, DAG.getNode(Opc, DL, PVT, N0, N1));
1514 
1515  if (Replace)
1516  ReplaceLoadWithPromotedLoad(Op.getOperand(0).getNode(), N0.getNode());
1517 
1518  // Deal with Op being deleted.
1519  if (Op && Op.getOpcode() != ISD::DELETED_NODE)
1520  return RV;
1521  }
1522  return SDValue();
1523 }
1524 
1525 SDValue DAGCombiner::PromoteExtend(SDValue Op) {
1526  if (!LegalOperations)
1527  return SDValue();
1528 
1529  EVT VT = Op.getValueType();
1530  if (VT.isVector() || !VT.isInteger())
1531  return SDValue();
1532 
1533  // If operation type is 'undesirable', e.g. i16 on x86, consider
1534  // promoting it.
1535  unsigned Opc = Op.getOpcode();
1536  if (TLI.isTypeDesirableForOp(Opc, VT))
1537  return SDValue();
1538 
1539  EVT PVT = VT;
1540  // Consult target whether it is a good idea to promote this operation and
1541  // what's the right type to promote it to.
1542  if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1543  assert(PVT != VT && "Don't know what type to promote to!");
1544  // fold (aext (aext x)) -> (aext x)
1545  // fold (aext (zext x)) -> (zext x)
1546  // fold (aext (sext x)) -> (sext x)
1547  LLVM_DEBUG(dbgs() << "\nPromoting "; Op.getNode()->dump(&DAG));
1548  return DAG.getNode(Op.getOpcode(), SDLoc(Op), VT, Op.getOperand(0));
1549  }
1550  return SDValue();
1551 }
1552 
1553 bool DAGCombiner::PromoteLoad(SDValue Op) {
1554  if (!LegalOperations)
1555  return false;
1556 
1557  if (!ISD::isUNINDEXEDLoad(Op.getNode()))
1558  return false;
1559 
1560  EVT VT = Op.getValueType();
1561  if (VT.isVector() || !VT.isInteger())
1562  return false;
1563 
1564  // If operation type is 'undesirable', e.g. i16 on x86, consider
1565  // promoting it.
1566  unsigned Opc = Op.getOpcode();
1567  if (TLI.isTypeDesirableForOp(Opc, VT))
1568  return false;
1569 
1570  EVT PVT = VT;
1571  // Consult target whether it is a good idea to promote this operation and
1572  // what's the right type to promote it to.
1573  if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1574  assert(PVT != VT && "Don't know what type to promote to!");
1575 
1576  SDLoc DL(Op);
1577  SDNode *N = Op.getNode();
1578  LoadSDNode *LD = cast<LoadSDNode>(N);
1579  EVT MemVT = LD->getMemoryVT();
1581  : LD->getExtensionType();
1582  SDValue NewLD = DAG.getExtLoad(ExtType, DL, PVT,
1583  LD->getChain(), LD->getBasePtr(),
1584  MemVT, LD->getMemOperand());
1585  SDValue Result = DAG.getNode(ISD::TRUNCATE, DL, VT, NewLD);
1586 
1587  LLVM_DEBUG(dbgs() << "\nPromoting "; N->dump(&DAG); dbgs() << "\nTo: ";
1588  Result.getNode()->dump(&DAG); dbgs() << '\n');
1589  WorklistRemover DeadNodes(*this);
1590  DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result);
1591  DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), NewLD.getValue(1));
1592  deleteAndRecombine(N);
1593  AddToWorklist(Result.getNode());
1594  return true;
1595  }
1596  return false;
1597 }
1598 
1599 /// Recursively delete a node which has no uses and any operands for
1600 /// which it is the only use.
1601 ///
1602 /// Note that this both deletes the nodes and removes them from the worklist.
1603 /// It also adds any nodes who have had a user deleted to the worklist as they
1604 /// may now have only one use and subject to other combines.
1605 bool DAGCombiner::recursivelyDeleteUnusedNodes(SDNode *N) {
1606  if (!N->use_empty())
1607  return false;
1608 
1610  Nodes.insert(N);
1611  do {
1612  N = Nodes.pop_back_val();
1613  if (!N)
1614  continue;
1615 
1616  if (N->use_empty()) {
1617  for (const SDValue &ChildN : N->op_values())
1618  Nodes.insert(ChildN.getNode());
1619 
1620  removeFromWorklist(N);
1621  DAG.DeleteNode(N);
1622  } else {
1623  AddToWorklist(N);
1624  }
1625  } while (!Nodes.empty());
1626  return true;
1627 }
1628 
1629 //===----------------------------------------------------------------------===//
1630 // Main DAG Combiner implementation
1631 //===----------------------------------------------------------------------===//
1632 
1633 void DAGCombiner::Run(CombineLevel AtLevel) {
1634  // set the instance variables, so that the various visit routines may use it.
1635  Level = AtLevel;
1636  LegalOperations = Level >= AfterLegalizeVectorOps;
1637  LegalTypes = Level >= AfterLegalizeTypes;
1638 
1639  WorklistInserter AddNodes(*this);
1640 
1641  // Add all the dag nodes to the worklist.
1642  for (SDNode &Node : DAG.allnodes())
1643  AddToWorklist(&Node);
1644 
1645  // Create a dummy node (which is not added to allnodes), that adds a reference
1646  // to the root node, preventing it from being deleted, and tracking any
1647  // changes of the root.
1648  HandleSDNode Dummy(DAG.getRoot());
1649 
1650  // While we have a valid worklist entry node, try to combine it.
1651  while (SDNode *N = getNextWorklistEntry()) {
1652  // If N has no uses, it is dead. Make sure to revisit all N's operands once
1653  // N is deleted from the DAG, since they too may now be dead or may have a
1654  // reduced number of uses, allowing other xforms.
1655  if (recursivelyDeleteUnusedNodes(N))
1656  continue;
1657 
1658  WorklistRemover DeadNodes(*this);
1659 
1660  // If this combine is running after legalizing the DAG, re-legalize any
1661  // nodes pulled off the worklist.
1662  if (Level == AfterLegalizeDAG) {
1663  SmallSetVector<SDNode *, 16> UpdatedNodes;
1664  bool NIsValid = DAG.LegalizeOp(N, UpdatedNodes);
1665 
1666  for (SDNode *LN : UpdatedNodes) {
1667  AddUsersToWorklist(LN);
1668  AddToWorklist(LN);
1669  }
1670  if (!NIsValid)
1671  continue;
1672  }
1673 
1674  LLVM_DEBUG(dbgs() << "\nCombining: "; N->dump(&DAG));
1675 
1676  // Add any operands of the new node which have not yet been combined to the
1677  // worklist as well. Because the worklist uniques things already, this
1678  // won't repeatedly process the same operand.
1679  CombinedNodes.insert(N);
1680  for (const SDValue &ChildN : N->op_values())
1681  if (!CombinedNodes.count(ChildN.getNode()))
1682  AddToWorklist(ChildN.getNode());
1683 
1684  SDValue RV = combine(N);
1685 
1686  if (!RV.getNode())
1687  continue;
1688 
1689  ++NodesCombined;
1690 
1691  // If we get back the same node we passed in, rather than a new node or
1692  // zero, we know that the node must have defined multiple values and
1693  // CombineTo was used. Since CombineTo takes care of the worklist
1694  // mechanics for us, we have no work to do in this case.
1695  if (RV.getNode() == N)
1696  continue;
1697 
1699  RV.getOpcode() != ISD::DELETED_NODE &&
1700  "Node was deleted but visit returned new node!");
1701 
1702  LLVM_DEBUG(dbgs() << " ... into: "; RV.getNode()->dump(&DAG));
1703 
1704  if (N->getNumValues() == RV.getNode()->getNumValues())
1705  DAG.ReplaceAllUsesWith(N, RV.getNode());
1706  else {
1707  assert(N->getValueType(0) == RV.getValueType() &&
1708  N->getNumValues() == 1 && "Type mismatch");
1709  DAG.ReplaceAllUsesWith(N, &RV);
1710  }
1711 
1712  // Push the new node and any users onto the worklist
1713  AddToWorklist(RV.getNode());
1714  AddUsersToWorklist(RV.getNode());
1715 
1716  // Finally, if the node is now dead, remove it from the graph. The node
1717  // may not be dead if the replacement process recursively simplified to
1718  // something else needing this node. This will also take care of adding any
1719  // operands which have lost a user to the worklist.
1720  recursivelyDeleteUnusedNodes(N);
1721  }
1722 
1723  // If the root changed (e.g. it was a dead load, update the root).
1724  DAG.setRoot(Dummy.getValue());
1725  DAG.RemoveDeadNodes();
1726 }
1727 
1728 SDValue DAGCombiner::visit(SDNode *N) {
1729  switch (N->getOpcode()) {
1730  default: break;
1731  case ISD::TokenFactor: return visitTokenFactor(N);
1732  case ISD::MERGE_VALUES: return visitMERGE_VALUES(N);
1733  case ISD::ADD: return visitADD(N);
1734  case ISD::SUB: return visitSUB(N);
1735  case ISD::SADDSAT:
1736  case ISD::UADDSAT: return visitADDSAT(N);
1737  case ISD::SSUBSAT:
1738  case ISD::USUBSAT: return visitSUBSAT(N);
1739  case ISD::ADDC: return visitADDC(N);
1740  case ISD::SADDO:
1741  case ISD::UADDO: return visitADDO(N);
1742  case ISD::SUBC: return visitSUBC(N);
1743  case ISD::SSUBO:
1744  case ISD::USUBO: return visitSUBO(N);
1745  case ISD::ADDE: return visitADDE(N);
1746  case ISD::ADDCARRY: return visitADDCARRY(N);
1747  case ISD::SUBE: return visitSUBE(N);
1748  case ISD::SUBCARRY: return visitSUBCARRY(N);
1749  case ISD::SMULFIX:
1750  case ISD::SMULFIXSAT:
1751  case ISD::UMULFIX:
1752  case ISD::UMULFIXSAT: return visitMULFIX(N);
1753  case ISD::MUL: return visitMUL(N);
1754  case ISD::SDIV: return visitSDIV(N);
1755  case ISD::UDIV: return visitUDIV(N);
1756  case ISD::SREM:
1757  case ISD::UREM: return visitREM(N);
1758  case ISD::MULHU: return visitMULHU(N);
1759  case ISD::MULHS: return visitMULHS(N);
1760  case ISD::SMUL_LOHI: return visitSMUL_LOHI(N);
1761  case ISD::UMUL_LOHI: return visitUMUL_LOHI(N);
1762  case ISD::SMULO:
1763  case ISD::UMULO: return visitMULO(N);
1764  case ISD::SMIN:
1765  case ISD::SMAX:
1766  case ISD::UMIN:
1767  case ISD::UMAX: return visitIMINMAX(N);
1768  case ISD::AND: return visitAND(N);
1769  case ISD::OR: return visitOR(N);
1770  case ISD::XOR: return visitXOR(N);
1771  case ISD::SHL: return visitSHL(N);
1772  case ISD::SRA: return visitSRA(N);
1773  case ISD::SRL: return visitSRL(N);
1774  case ISD::ROTR:
1775  case ISD::ROTL: return visitRotate(N);
1776  case ISD::FSHL:
1777  case ISD::FSHR: return visitFunnelShift(N);
1778  case ISD::ABS: return visitABS(N);
1779  case ISD::BSWAP: return visitBSWAP(N);
1780  case ISD::BITREVERSE: return visitBITREVERSE(N);
1781  case ISD::CTLZ: return visitCTLZ(N);
1782  case ISD::CTLZ_ZERO_UNDEF: return visitCTLZ_ZERO_UNDEF(N);
1783  case ISD::CTTZ: return visitCTTZ(N);
1784  case ISD::CTTZ_ZERO_UNDEF: return visitCTTZ_ZERO_UNDEF(N);
1785  case ISD::CTPOP: return visitCTPOP(N);
1786  case ISD::SELECT: return visitSELECT(N);
1787  case ISD::VSELECT: return visitVSELECT(N);
1788  case ISD::SELECT_CC: return visitSELECT_CC(N);
1789  case ISD::SETCC: return visitSETCC(N);
1790  case ISD::SETCCCARRY: return visitSETCCCARRY(N);
1791  case ISD::SIGN_EXTEND: return visitSIGN_EXTEND(N);
1792  case ISD::ZERO_EXTEND: return visitZERO_EXTEND(N);
1793  case ISD::ANY_EXTEND: return visitANY_EXTEND(N);
1794  case ISD::AssertSext:
1795  case ISD::AssertZext: return visitAssertExt(N);
1796  case ISD::SIGN_EXTEND_INREG: return visitSIGN_EXTEND_INREG(N);
1797  case ISD::SIGN_EXTEND_VECTOR_INREG: return visitSIGN_EXTEND_VECTOR_INREG(N);
1798  case ISD::ZERO_EXTEND_VECTOR_INREG: return visitZERO_EXTEND_VECTOR_INREG(N);
1799  case ISD::TRUNCATE: return visitTRUNCATE(N);
1800  case ISD::BITCAST: return visitBITCAST(N);
1801  case ISD::BUILD_PAIR: return visitBUILD_PAIR(N);
1802  case ISD::FADD: return visitFADD(N);
1803  case ISD::FSUB: return visitFSUB(N);
1804  case ISD::FMUL: return visitFMUL(N);
1805  case ISD::FMA: return visitFMA(N);
1806  case ISD::FDIV: return visitFDIV(N);
1807  case ISD::FREM: return visitFREM(N);
1808  case ISD::FSQRT: return visitFSQRT(N);
1809  case ISD::FCOPYSIGN: return visitFCOPYSIGN(N);
1810  case ISD::FPOW: return visitFPOW(N);
1811  case ISD::SINT_TO_FP: return visitSINT_TO_FP(N);
1812  case ISD::UINT_TO_FP: return visitUINT_TO_FP(N);
1813  case ISD::FP_TO_SINT: return visitFP_TO_SINT(N);
1814  case ISD::FP_TO_UINT: return visitFP_TO_UINT(N);
1815  case ISD::FP_ROUND: return visitFP_ROUND(N);
1816  case ISD::FP_EXTEND: return visitFP_EXTEND(N);
1817  case ISD::FNEG: return visitFNEG(N);
1818  case ISD::FABS: return visitFABS(N);
1819  case ISD::FFLOOR: return visitFFLOOR(N);
1820  case ISD::FMINNUM: return visitFMINNUM(N);
1821  case ISD::FMAXNUM: return visitFMAXNUM(N);
1822  case ISD::FMINIMUM: return visitFMINIMUM(N);
1823  case ISD::FMAXIMUM: return visitFMAXIMUM(N);
1824  case ISD::FCEIL: return visitFCEIL(N);
1825  case ISD::FTRUNC: return visitFTRUNC(N);
1826  case ISD::BRCOND: return visitBRCOND(N);
1827  case ISD::BR_CC: return visitBR_CC(N);
1828  case ISD::LOAD: return visitLOAD(N);
1829  case ISD::STORE: return visitSTORE(N);
1830  case ISD::INSERT_VECTOR_ELT: return visitINSERT_VECTOR_ELT(N);
1831  case ISD::EXTRACT_VECTOR_ELT: return visitEXTRACT_VECTOR_ELT(N);
1832  case ISD::BUILD_VECTOR: return visitBUILD_VECTOR(N);
1833  case ISD::CONCAT_VECTORS: return visitCONCAT_VECTORS(N);
1834  case ISD::EXTRACT_SUBVECTOR: return visitEXTRACT_SUBVECTOR(N);
1835  case ISD::VECTOR_SHUFFLE: return visitVECTOR_SHUFFLE(N);
1836  case ISD::SCALAR_TO_VECTOR: return visitSCALAR_TO_VECTOR(N);
1837  case ISD::INSERT_SUBVECTOR: return visitINSERT_SUBVECTOR(N);
1838  case ISD::MGATHER: return visitMGATHER(N);
1839  case ISD::MLOAD: return visitMLOAD(N);
1840  case ISD::MSCATTER: return visitMSCATTER(N);
1841  case ISD::MSTORE: return visitMSTORE(N);
1842  case ISD::LIFETIME_END: return visitLIFETIME_END(N);
1843  case ISD::FP_TO_FP16: return visitFP_TO_FP16(N);
1844  case ISD::FP16_TO_FP: return visitFP16_TO_FP(N);
1845  case ISD::VECREDUCE_FADD:
1846  case ISD::VECREDUCE_FMUL:
1847  case ISD::VECREDUCE_ADD:
1848  case ISD::VECREDUCE_MUL:
1849  case ISD::VECREDUCE_AND:
1850  case ISD::VECREDUCE_OR:
1851  case ISD::VECREDUCE_XOR:
1852  case ISD::VECREDUCE_SMAX:
1853  case ISD::VECREDUCE_SMIN:
1854  case ISD::VECREDUCE_UMAX:
1855  case ISD::VECREDUCE_UMIN:
1856  case ISD::VECREDUCE_FMAX:
1857  case ISD::VECREDUCE_FMIN: return visitVECREDUCE(N);
1858  }
1859  return SDValue();
1860 }
1861 
1862 SDValue DAGCombiner::combine(SDNode *N) {
1863  SDValue RV = visit(N);
1864 
1865  // If nothing happened, try a target-specific DAG combine.
1866  if (!RV.getNode()) {
1868  "Node was deleted but visit returned NULL!");
1869 
1870  if (N->getOpcode() >= ISD::BUILTIN_OP_END ||
1872 
1873  // Expose the DAG combiner to the target combiner impls.
1875  DagCombineInfo(DAG, Level, false, this);
1876 
1877  RV = TLI.PerformDAGCombine(N, DagCombineInfo);
1878  }
1879  }
1880 
1881  // If nothing happened still, try promoting the operation.
1882  if (!RV.getNode()) {
1883  switch (N->getOpcode()) {
1884  default: break;
1885  case ISD::ADD:
1886  case ISD::SUB:
1887  case ISD::MUL:
1888  case ISD::AND:
1889  case ISD::OR:
1890  case ISD::XOR:
1891  RV = PromoteIntBinOp(SDValue(N, 0));
1892  break;
1893  case ISD::SHL:
1894  case ISD::SRA:
1895  case ISD::SRL:
1896  RV = PromoteIntShiftOp(SDValue(N, 0));
1897  break;
1898  case ISD::SIGN_EXTEND:
1899  case ISD::ZERO_EXTEND:
1900  case ISD::ANY_EXTEND:
1901  RV = PromoteExtend(SDValue(N, 0));
1902  break;
1903  case ISD::LOAD:
1904  if (PromoteLoad(SDValue(N, 0)))
1905  RV = SDValue(N, 0);
1906  break;
1907  }
1908  }
1909 
1910  // If N is a commutative binary node, try to eliminate it if the commuted
1911  // version is already present in the DAG.
1912  if (!RV.getNode() && TLI.isCommutativeBinOp(N->getOpcode()) &&
1913  N->getNumValues() == 1) {
1914  SDValue N0 = N->getOperand(0);
1915  SDValue N1 = N->getOperand(1);
1916 
1917  // Constant operands are canonicalized to RHS.
1918  if (N0 != N1 && (isa<ConstantSDNode>(N0) || !isa<ConstantSDNode>(N1))) {
1919  SDValue Ops[] = {N1, N0};
1920  SDNode *CSENode = DAG.getNodeIfExists(N->getOpcode(), N->getVTList(), Ops,
1921  N->getFlags());
1922  if (CSENode)
1923  return SDValue(CSENode, 0);
1924  }
1925  }
1926 
1927  return RV;
1928 }
1929 
1930 /// Given a node, return its input chain if it has one, otherwise return a null
1931 /// sd operand.
1933  if (unsigned NumOps = N->getNumOperands()) {
1934  if (N->getOperand(0).getValueType() == MVT::Other)
1935  return N->getOperand(0);
1936  if (N->getOperand(NumOps-1).getValueType() == MVT::Other)
1937  return N->getOperand(NumOps-1);
1938  for (unsigned i = 1; i < NumOps-1; ++i)
1939  if (N->getOperand(i).getValueType() == MVT::Other)
1940  return N->getOperand(i);
1941  }
1942  return SDValue();
1943 }
1944 
1945 SDValue DAGCombiner::visitTokenFactor(SDNode *N) {
1946  // If N has two operands, where one has an input chain equal to the other,
1947  // the 'other' chain is redundant.
1948  if (N->getNumOperands() == 2) {
1949  if (getInputChainForNode(N->getOperand(0).getNode()) == N->getOperand(1))
1950  return N->getOperand(0);
1951  if (getInputChainForNode(N->getOperand(1).getNode()) == N->getOperand(0))
1952  return N->getOperand(1);
1953  }
1954 
1955  // Don't simplify token factors if optnone.
1956  if (OptLevel == CodeGenOpt::None)
1957  return SDValue();
1958 
1959  // If the sole user is a token factor, we should make sure we have a
1960  // chance to merge them together. This prevents TF chains from inhibiting
1961  // optimizations.
1962  if (N->hasOneUse() && N->use_begin()->getOpcode() == ISD::TokenFactor)
1963  AddToWorklist(*(N->use_begin()));
1964 
1965  SmallVector<SDNode *, 8> TFs; // List of token factors to visit.
1966  SmallVector<SDValue, 8> Ops; // Ops for replacing token factor.
1967  SmallPtrSet<SDNode*, 16> SeenOps;
1968  bool Changed = false; // If we should replace this token factor.
1969 
1970  // Start out with this token factor.
1971  TFs.push_back(N);
1972 
1973  // Iterate through token factors. The TFs grows when new token factors are
1974  // encountered.
1975  for (unsigned i = 0; i < TFs.size(); ++i) {
1976  // Limit number of nodes to inline, to avoid quadratic compile times.
1977  // We have to add the outstanding Token Factors to Ops, otherwise we might
1978  // drop Ops from the resulting Token Factors.
1979  if (Ops.size() > TokenFactorInlineLimit) {
1980  for (unsigned j = i; j < TFs.size(); j++)
1981  Ops.emplace_back(TFs[j], 0);
1982  // Drop unprocessed Token Factors from TFs, so we do not add them to the
1983  // combiner worklist later.
1984  TFs.resize(i);
1985  break;
1986  }
1987 
1988  SDNode *TF = TFs[i];
1989  // Check each of the operands.
1990  for (const SDValue &Op : TF->op_values()) {
1991  switch (Op.getOpcode()) {
1992  case ISD::EntryToken:
1993  // Entry tokens don't need to be added to the list. They are
1994  // redundant.
1995  Changed = true;
1996  break;
1997 
1998  case ISD::TokenFactor:
1999  if (Op.hasOneUse() && !is_contained(TFs, Op.getNode())) {
2000  // Queue up for processing.
2001  TFs.push_back(Op.getNode());
2002  Changed = true;
2003  break;
2004  }
2006 
2007  default:
2008  // Only add if it isn't already in the list.
2009  if (SeenOps.insert(Op.getNode()).second)
2010  Ops.push_back(Op);
2011  else
2012  Changed = true;
2013  break;
2014  }
2015  }
2016  }
2017 
2018  // Re-visit inlined Token Factors, to clean them up in case they have been
2019  // removed. Skip the first Token Factor, as this is the current node.
2020  for (unsigned i = 1, e = TFs.size(); i < e; i++)
2021  AddToWorklist(TFs[i]);
2022 
2023  // Remove Nodes that are chained to another node in the list. Do so
2024  // by walking up chains breath-first stopping when we've seen
2025  // another operand. In general we must climb to the EntryNode, but we can exit
2026  // early if we find all remaining work is associated with just one operand as
2027  // no further pruning is possible.
2028 
2029  // List of nodes to search through and original Ops from which they originate.
2031  SmallVector<unsigned, 8> OpWorkCount; // Count of work for each Op.
2032  SmallPtrSet<SDNode *, 16> SeenChains;
2033  bool DidPruneOps = false;
2034 
2035  unsigned NumLeftToConsider = 0;
2036  for (const SDValue &Op : Ops) {
2037  Worklist.push_back(std::make_pair(Op.getNode(), NumLeftToConsider++));
2038  OpWorkCount.push_back(1);
2039  }
2040 
2041  auto AddToWorklist = [&](unsigned CurIdx, SDNode *Op, unsigned OpNumber) {
2042  // If this is an Op, we can remove the op from the list. Remark any
2043  // search associated with it as from the current OpNumber.
2044  if (SeenOps.count(Op) != 0) {
2045  Changed = true;
2046  DidPruneOps = true;
2047  unsigned OrigOpNumber = 0;
2048  while (OrigOpNumber < Ops.size() && Ops[OrigOpNumber].getNode() != Op)
2049  OrigOpNumber++;
2050  assert((OrigOpNumber != Ops.size()) &&
2051  "expected to find TokenFactor Operand");
2052  // Re-mark worklist from OrigOpNumber to OpNumber
2053  for (unsigned i = CurIdx + 1; i < Worklist.size(); ++i) {
2054  if (Worklist[i].second == OrigOpNumber) {
2055  Worklist[i].second = OpNumber;
2056  }
2057  }
2058  OpWorkCount[OpNumber] += OpWorkCount[OrigOpNumber];
2059  OpWorkCount[OrigOpNumber] = 0;
2060  NumLeftToConsider--;
2061  }
2062  // Add if it's a new chain
2063  if (SeenChains.insert(Op).second) {
2064  OpWorkCount[OpNumber]++;
2065  Worklist.push_back(std::make_pair(Op, OpNumber));
2066  }
2067  };
2068 
2069  for (unsigned i = 0; i < Worklist.size() && i < 1024; ++i) {
2070  // We need at least be consider at least 2 Ops to prune.
2071  if (NumLeftToConsider <= 1)
2072  break;
2073  auto CurNode = Worklist[i].first;
2074  auto CurOpNumber = Worklist[i].second;
2075  assert((OpWorkCount[CurOpNumber] > 0) &&
2076  "Node should not appear in worklist");
2077  switch (CurNode->getOpcode()) {
2078  case ISD::EntryToken:
2079  // Hitting EntryToken is the only way for the search to terminate without
2080  // hitting
2081  // another operand's search. Prevent us from marking this operand
2082  // considered.
2083  NumLeftToConsider++;
2084  break;
2085  case ISD::TokenFactor:
2086  for (const SDValue &Op : CurNode->op_values())
2087  AddToWorklist(i, Op.getNode(), CurOpNumber);
2088  break;
2089  case ISD::LIFETIME_START:
2090  case ISD::LIFETIME_END:
2091  case ISD::CopyFromReg:
2092  case ISD::CopyToReg:
2093  AddToWorklist(i, CurNode->getOperand(0).getNode(), CurOpNumber);
2094  break;
2095  default:
2096  if (auto *MemNode = dyn_cast<MemSDNode>(CurNode))
2097  AddToWorklist(i, MemNode->getChain().getNode(), CurOpNumber);
2098  break;
2099  }
2100  OpWorkCount[CurOpNumber]--;
2101  if (OpWorkCount[CurOpNumber] == 0)
2102  NumLeftToConsider--;
2103  }
2104 
2105  // If we've changed things around then replace token factor.
2106  if (Changed) {
2107  SDValue Result;
2108  if (Ops.empty()) {
2109  // The entry token is the only possible outcome.
2110  Result = DAG.getEntryNode();
2111  } else {
2112  if (DidPruneOps) {
2113  SmallVector<SDValue, 8> PrunedOps;
2114  //
2115  for (const SDValue &Op : Ops) {
2116  if (SeenChains.count(Op.getNode()) == 0)
2117  PrunedOps.push_back(Op);
2118  }
2119  Result = DAG.getTokenFactor(SDLoc(N), PrunedOps);
2120  } else {
2121  Result = DAG.getTokenFactor(SDLoc(N), Ops);
2122  }
2123  }
2124  return Result;
2125  }
2126  return SDValue();
2127 }
2128 
2129 /// MERGE_VALUES can always be eliminated.
2130 SDValue DAGCombiner::visitMERGE_VALUES(SDNode *N) {
2131  WorklistRemover DeadNodes(*this);
2132  // Replacing results may cause a different MERGE_VALUES to suddenly
2133  // be CSE'd with N, and carry its uses with it. Iterate until no
2134  // uses remain, to ensure that the node can be safely deleted.
2135  // First add the users of this node to the work list so that they
2136  // can be tried again once they have new operands.
2137  AddUsersToWorklist(N);
2138  do {
2139  // Do as a single replacement to avoid rewalking use lists.
2141  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
2142  Ops.push_back(N->getOperand(i));
2143  DAG.ReplaceAllUsesWith(N, Ops.data());
2144  } while (!N->use_empty());
2145  deleteAndRecombine(N);
2146  return SDValue(N, 0); // Return N so it doesn't get rechecked!
2147 }
2148 
2149 /// If \p N is a ConstantSDNode with isOpaque() == false return it casted to a
2150 /// ConstantSDNode pointer else nullptr.
2153  return Const != nullptr && !Const->isOpaque() ? Const : nullptr;
2154 }
2155 
2156 SDValue DAGCombiner::foldBinOpIntoSelect(SDNode *BO) {
2157  assert(TLI.isBinOp(BO->getOpcode()) && BO->getNumValues() == 1 &&
2158  "Unexpected binary operator");
2159 
2160  // Don't do this unless the old select is going away. We want to eliminate the
2161  // binary operator, not replace a binop with a select.
2162  // TODO: Handle ISD::SELECT_CC.
2163  unsigned SelOpNo = 0;
2164  SDValue Sel = BO->getOperand(0);
2165  if (Sel.getOpcode() != ISD::SELECT || !Sel.hasOneUse()) {
2166  SelOpNo = 1;
2167  Sel = BO->getOperand(1);
2168  }
2169 
2170  if (Sel.getOpcode() != ISD::SELECT || !Sel.hasOneUse())
2171  return SDValue();
2172 
2173  SDValue CT = Sel.getOperand(1);
2174  if (!isConstantOrConstantVector(CT, true) &&
2176  return SDValue();
2177 
2178  SDValue CF = Sel.getOperand(2);
2179  if (!isConstantOrConstantVector(CF, true) &&
2181  return SDValue();
2182 
2183  // Bail out if any constants are opaque because we can't constant fold those.
2184  // The exception is "and" and "or" with either 0 or -1 in which case we can
2185  // propagate non constant operands into select. I.e.:
2186  // and (select Cond, 0, -1), X --> select Cond, 0, X
2187  // or X, (select Cond, -1, 0) --> select Cond, -1, X
2188  auto BinOpcode = BO->getOpcode();
2189  bool CanFoldNonConst =
2190  (BinOpcode == ISD::AND || BinOpcode == ISD::OR) &&
2193 
2194  SDValue CBO = BO->getOperand(SelOpNo ^ 1);
2195  if (!CanFoldNonConst &&
2196  !isConstantOrConstantVector(CBO, true) &&
2198  return SDValue();
2199 
2200  EVT VT = Sel.getValueType();
2201 
2202  // In case of shift value and shift amount may have different VT. For instance
2203  // on x86 shift amount is i8 regardles of LHS type. Bail out if we have
2204  // swapped operands and value types do not match. NB: x86 is fine if operands
2205  // are not swapped with shift amount VT being not bigger than shifted value.
2206  // TODO: that is possible to check for a shift operation, correct VTs and
2207  // still perform optimization on x86 if needed.
2208  if (SelOpNo && VT != CBO.getValueType())
2209  return SDValue();
2210 
2211  // We have a select-of-constants followed by a binary operator with a
2212  // constant. Eliminate the binop by pulling the constant math into the select.
2213  // Example: add (select Cond, CT, CF), CBO --> select Cond, CT + CBO, CF + CBO
2214  SDLoc DL(Sel);
2215  SDValue NewCT = SelOpNo ? DAG.getNode(BinOpcode, DL, VT, CBO, CT)
2216  : DAG.getNode(BinOpcode, DL, VT, CT, CBO);
2217  if (!CanFoldNonConst && !NewCT.isUndef() &&
2218  !isConstantOrConstantVector(NewCT, true) &&
2220  return SDValue();
2221 
2222  SDValue NewCF = SelOpNo ? DAG.getNode(BinOpcode, DL, VT, CBO, CF)
2223  : DAG.getNode(BinOpcode, DL, VT, CF, CBO);
2224  if (!CanFoldNonConst && !NewCF.isUndef() &&
2225  !isConstantOrConstantVector(NewCF, true) &&
2227  return SDValue();
2228 
2229  SDValue SelectOp = DAG.getSelect(DL, VT, Sel.getOperand(0), NewCT, NewCF);
2230  SelectOp->setFlags(BO->getFlags());
2231  return SelectOp;
2232 }
2233 
2235  assert((N->getOpcode() == ISD::ADD || N->getOpcode() == ISD::SUB) &&
2236  "Expecting add or sub");
2237 
2238  // Match a constant operand and a zext operand for the math instruction:
2239  // add Z, C
2240  // sub C, Z
2241  bool IsAdd = N->getOpcode() == ISD::ADD;
2242  SDValue C = IsAdd ? N->getOperand(1) : N->getOperand(0);
2243  SDValue Z = IsAdd ? N->getOperand(0) : N->getOperand(1);
2244  auto *CN = dyn_cast<ConstantSDNode>(C);
2245  if (!CN || Z.getOpcode() != ISD::ZERO_EXTEND)
2246  return SDValue();
2247 
2248  // Match the zext operand as a setcc of a boolean.
2249  if (Z.getOperand(0).getOpcode() != ISD::SETCC ||
2250  Z.getOperand(0).getValueType() != MVT::i1)
2251  return SDValue();
2252 
2253  // Match the compare as: setcc (X & 1), 0, eq.
2254  SDValue SetCC = Z.getOperand(0);
2255  ISD::CondCode CC = cast<CondCodeSDNode>(SetCC->getOperand(2))->get();
2256  if (CC != ISD::SETEQ || !isNullConstant(SetCC.getOperand(1)) ||
2257  SetCC.getOperand(0).getOpcode() != ISD::AND ||
2258  !isOneConstant(SetCC.getOperand(0).getOperand(1)))
2259  return SDValue();
2260 
2261  // We are adding/subtracting a constant and an inverted low bit. Turn that
2262  // into a subtract/add of the low bit with incremented/decremented constant:
2263  // add (zext i1 (seteq (X & 1), 0)), C --> sub C+1, (zext (X & 1))
2264  // sub C, (zext i1 (seteq (X & 1), 0)) --> add C-1, (zext (X & 1))
2265  EVT VT = C.getValueType();
2266  SDLoc DL(N);
2267  SDValue LowBit = DAG.getZExtOrTrunc(SetCC.getOperand(0), DL, VT);
2268  SDValue C1 = IsAdd ? DAG.getConstant(CN->getAPIntValue() + 1, DL, VT) :
2269  DAG.getConstant(CN->getAPIntValue() - 1, DL, VT);
2270  return DAG.getNode(IsAdd ? ISD::SUB : ISD::ADD, DL, VT, C1, LowBit);
2271 }
2272 
2273 /// Try to fold a 'not' shifted sign-bit with add/sub with constant operand into
2274 /// a shift and add with a different constant.
2276  assert((N->getOpcode() == ISD::ADD || N->getOpcode() == ISD::SUB) &&
2277  "Expecting add or sub");
2278 
2279  // We need a constant operand for the add/sub, and the other operand is a
2280  // logical shift right: add (srl), C or sub C, (srl).
2281  // TODO - support non-uniform vector amounts.
2282  bool IsAdd = N->getOpcode() == ISD::ADD;
2283  SDValue ConstantOp = IsAdd ? N->getOperand(1) : N->getOperand(0);
2284  SDValue ShiftOp = IsAdd ? N->getOperand(0) : N->getOperand(1);
2285  ConstantSDNode *C = isConstOrConstSplat(ConstantOp);
2286  if (!C || ShiftOp.getOpcode() != ISD::SRL)
2287  return SDValue();
2288 
2289  // The shift must be of a 'not' value.
2290  SDValue Not = ShiftOp.getOperand(0);
2291  if (!Not.hasOneUse() || !isBitwiseNot(Not))
2292  return SDValue();
2293 
2294  // The shift must be moving the sign bit to the least-significant-bit.
2295  EVT VT = ShiftOp.getValueType();
2296  SDValue ShAmt = ShiftOp.getOperand(1);
2297  ConstantSDNode *ShAmtC = isConstOrConstSplat(ShAmt);
2298  if (!ShAmtC || ShAmtC->getAPIntValue() != (VT.getScalarSizeInBits() - 1))
2299  return SDValue();
2300 
2301  // Eliminate the 'not' by adjusting the shift and add/sub constant:
2302  // add (srl (not X), 31), C --> add (sra X, 31), (C + 1)
2303  // sub C, (srl (not X), 31) --> add (srl X, 31), (C - 1)
2304  SDLoc DL(N);
2305  auto ShOpcode = IsAdd ? ISD::SRA : ISD::SRL;
2306  SDValue NewShift = DAG.getNode(ShOpcode, DL, VT, Not.getOperand(0), ShAmt);
2307  APInt NewC = IsAdd ? C->getAPIntValue() + 1 : C->getAPIntValue() - 1;
2308  return DAG.getNode(ISD::ADD, DL, VT, NewShift, DAG.getConstant(NewC, DL, VT));
2309 }
2310 
2311 /// Try to fold a node that behaves like an ADD (note that N isn't necessarily
2312 /// an ISD::ADD here, it could for example be an ISD::OR if we know that there
2313 /// are no common bits set in the operands).
2314 SDValue DAGCombiner::visitADDLike(SDNode *N) {
2315  SDValue N0 = N->getOperand(0);
2316  SDValue N1 = N->getOperand(1);
2317  EVT VT = N0.getValueType();
2318  SDLoc DL(N);
2319 
2320  // fold vector ops
2321  if (VT.isVector()) {
2322  if (SDValue FoldedVOp = SimplifyVBinOp(N))
2323  return FoldedVOp;
2324 
2325  // fold (add x, 0) -> x, vector edition
2327  return N0;
2329  return N1;
2330  }
2331 
2332  // fold (add x, undef) -> undef
2333  if (N0.isUndef())
2334  return N0;
2335 
2336  if (N1.isUndef())
2337  return N1;
2338 
2340  // canonicalize constant to RHS
2342  return DAG.getNode(ISD::ADD, DL, VT, N1, N0);
2343  // fold (add c1, c2) -> c1+c2
2344  return DAG.FoldConstantArithmetic(ISD::ADD, DL, VT, N0.getNode(),
2345  N1.getNode());
2346  }
2347 
2348  // fold (add x, 0) -> x
2349  if (isNullConstant(N1))
2350  return N0;
2351 
2352  if (isConstantOrConstantVector(N1, /* NoOpaque */ true)) {
2353  // fold ((A-c1)+c2) -> (A+(c2-c1))
2354  if (N0.getOpcode() == ISD::SUB &&
2355  isConstantOrConstantVector(N0.getOperand(1), /* NoOpaque */ true)) {
2356  SDValue Sub = DAG.FoldConstantArithmetic(ISD::SUB, DL, VT, N1.getNode(),
2357  N0.getOperand(1).getNode());
2358  assert(Sub && "Constant folding failed");
2359  return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), Sub);
2360  }
2361 
2362  // fold ((c1-A)+c2) -> (c1+c2)-A
2363  if (N0.getOpcode() == ISD::SUB &&
2364  isConstantOrConstantVector(N0.getOperand(0), /* NoOpaque */ true)) {
2365  SDValue Add = DAG.FoldConstantArithmetic(ISD::ADD, DL, VT, N1.getNode(),
2366  N0.getOperand(0).getNode());
2367  assert(Add && "Constant folding failed");
2368  return DAG.getNode(ISD::SUB, DL, VT, Add, N0.getOperand(1));
2369  }
2370 
2371  // add (sext i1 X), 1 -> zext (not i1 X)
2372  // We don't transform this pattern:
2373  // add (zext i1 X), -1 -> sext (not i1 X)
2374  // because most (?) targets generate better code for the zext form.
2375  if (N0.getOpcode() == ISD::SIGN_EXTEND && N0.hasOneUse() &&
2376  isOneOrOneSplat(N1)) {
2377  SDValue X = N0.getOperand(0);
2378  if ((!LegalOperations ||
2379  (TLI.isOperationLegal(ISD::XOR, X.getValueType()) &&
2380  TLI.isOperationLegal(ISD::ZERO_EXTEND, VT))) &&
2381  X.getScalarValueSizeInBits() == 1) {
2382  SDValue Not = DAG.getNOT(DL, X, X.getValueType());
2383  return DAG.getNode(ISD::ZERO_EXTEND, DL, VT, Not);
2384  }
2385  }
2386 
2387  // Undo the add -> or combine to merge constant offsets from a frame index.
2388  if (N0.getOpcode() == ISD::OR &&
2389  isa<FrameIndexSDNode>(N0.getOperand(0)) &&
2390  isa<ConstantSDNode>(N0.getOperand(1)) &&
2391  DAG.haveNoCommonBitsSet(N0.getOperand(0), N0.getOperand(1))) {
2392  SDValue Add0 = DAG.getNode(ISD::ADD, DL, VT, N1, N0.getOperand(1));
2393  return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), Add0);
2394  }
2395  }
2396 
2397  if (SDValue NewSel = foldBinOpIntoSelect(N))
2398  return NewSel;
2399 
2400  // reassociate add
2401  if (!reassociationCanBreakAddressingModePattern(ISD::ADD, DL, N0, N1)) {
2402  if (SDValue RADD = reassociateOps(ISD::ADD, DL, N0, N1, N->getFlags()))
2403  return RADD;
2404  }
2405  // fold ((0-A) + B) -> B-A
2406  if (N0.getOpcode() == ISD::SUB && isNullOrNullSplat(N0.getOperand(0)))
2407  return DAG.getNode(ISD::SUB, DL, VT, N1, N0.getOperand(1));
2408 
2409  // fold (A + (0-B)) -> A-B
2410  if (N1.getOpcode() == ISD::SUB && isNullOrNullSplat(N1.getOperand(0)))
2411  return DAG.getNode(ISD::SUB, DL, VT, N0, N1.getOperand(1));
2412 
2413  // fold (A+(B-A)) -> B
2414  if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1))
2415  return N1.getOperand(0);
2416 
2417  // fold ((B-A)+A) -> B
2418  if (N0.getOpcode() == ISD::SUB && N1 == N0.getOperand(1))
2419  return N0.getOperand(0);
2420 
2421  // fold ((A-B)+(C-A)) -> (C-B)
2422  if (N0.getOpcode() == ISD::SUB && N1.getOpcode() == ISD::SUB &&
2423  N0.getOperand(0) == N1.getOperand(1))
2424  return DAG.getNode(ISD::SUB, DL, VT, N1.getOperand(0),
2425  N0.getOperand(1));
2426 
2427  // fold ((A-B)+(B-C)) -> (A-C)
2428  if (N0.getOpcode() == ISD::SUB && N1.getOpcode() == ISD::SUB &&
2429  N0.getOperand(1) == N1.getOperand(0))
2430  return DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0),
2431  N1.getOperand(1));
2432 
2433  // fold (A+(B-(A+C))) to (B-C)
2434  if (N1.getOpcode() == ISD::SUB && N1.getOperand(1).getOpcode() == ISD::ADD &&
2435  N0 == N1.getOperand(1).getOperand(0))
2436  return DAG.getNode(ISD::SUB, DL, VT, N1.getOperand(0),
2437  N1.getOperand(1).getOperand(1));
2438 
2439  // fold (A+(B-(C+A))) to (B-C)
2440  if (N1.getOpcode() == ISD::SUB && N1.getOperand(1).getOpcode() == ISD::ADD &&
2441  N0 == N1.getOperand(1).getOperand(1))
2442  return DAG.getNode(ISD::SUB, DL, VT, N1.getOperand(0),
2443  N1.getOperand(1).getOperand(0));
2444 
2445  // fold (A+((B-A)+or-C)) to (B+or-C)
2446  if ((N1.getOpcode() == ISD::SUB || N1.getOpcode() == ISD::ADD) &&
2447  N1.getOperand(0).getOpcode() == ISD::SUB &&
2448  N0 == N1.getOperand(0).getOperand(1))
2449  return DAG.getNode(N1.getOpcode(), DL, VT, N1.getOperand(0).getOperand(0),
2450  N1.getOperand(1));
2451 
2452  // fold (A-B)+(C-D) to (A+C)-(B+D) when A or C is constant
2453  if (N0.getOpcode() == ISD::SUB && N1.getOpcode() == ISD::SUB) {
2454  SDValue N00 = N0.getOperand(0);
2455  SDValue N01 = N0.getOperand(1);
2456  SDValue N10 = N1.getOperand(0);
2457  SDValue N11 = N1.getOperand(1);
2458 
2460  return DAG.getNode(ISD::SUB, DL, VT,
2461  DAG.getNode(ISD::ADD, SDLoc(N0), VT, N00, N10),
2462  DAG.getNode(ISD::ADD, SDLoc(N1), VT, N01, N11));
2463  }
2464 
2465  // fold (add (umax X, C), -C) --> (usubsat X, C)
2466  if (N0.getOpcode() == ISD::UMAX && hasOperation(ISD::USUBSAT, VT)) {
2467  auto MatchUSUBSAT = [](ConstantSDNode *Max, ConstantSDNode *Op) {
2468  return (!Max && !Op) ||
2469  (Max && Op && Max->getAPIntValue() == (-Op->getAPIntValue()));
2470  };
2471  if (ISD::matchBinaryPredicate(N0.getOperand(1), N1, MatchUSUBSAT,
2472  /*AllowUndefs*/ true))
2473  return DAG.getNode(ISD::USUBSAT, DL, VT, N0.getOperand(0),
2474  N0.getOperand(1));
2475  }
2476 
2477  if (SimplifyDemandedBits(SDValue(N, 0)))
2478  return SDValue(N, 0);
2479 
2480  if (isOneOrOneSplat(N1)) {
2481  // fold (add (xor a, -1), 1) -> (sub 0, a)
2482  if (isBitwiseNot(N0))
2483  return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT),
2484  N0.getOperand(0));
2485 
2486  // fold (add (add (xor a, -1), b), 1) -> (sub b, a)
2487  if (N0.getOpcode() == ISD::ADD ||
2488  N0.getOpcode() == ISD::UADDO ||
2489  N0.getOpcode() == ISD::SADDO) {
2490  SDValue A, Xor;
2491 
2492  if (isBitwiseNot(N0.getOperand(0))) {
2493  A = N0.getOperand(1);
2494  Xor = N0.getOperand(0);
2495  } else if (isBitwiseNot(N0.getOperand(1))) {
2496  A = N0.getOperand(0);
2497  Xor = N0.getOperand(1);
2498  }
2499 
2500  if (Xor)
2501  return DAG.getNode(ISD::SUB, DL, VT, A, Xor.getOperand(0));
2502  }
2503 
2504  // Look for:
2505  // add (add x, y), 1
2506  // And if the target does not like this form then turn into:
2507  // sub y, (xor x, -1)
2508  if (!TLI.preferIncOfAddToSubOfNot(VT) && N0.hasOneUse() &&
2509  N0.getOpcode() == ISD::ADD) {
2510  SDValue Not = DAG.getNode(ISD::XOR, DL, VT, N0.getOperand(0),
2511  DAG.getAllOnesConstant(DL, VT));
2512  return DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(1), Not);
2513  }
2514  }
2515 
2516  // (x - y) + -1 -> add (xor y, -1), x
2517  if (N0.hasOneUse() && N0.getOpcode() == ISD::SUB &&
2519  SDValue Xor = DAG.getNode(ISD::XOR, DL, VT, N0.getOperand(1), N1);
2520  return DAG.getNode(ISD::ADD, DL, VT, Xor, N0.getOperand(0));
2521  }
2522 
2523  if (SDValue Combined = visitADDLikeCommutative(N0, N1, N))
2524  return Combined;
2525 
2526  if (SDValue Combined = visitADDLikeCommutative(N1, N0, N))
2527  return Combined;
2528 
2529  return SDValue();
2530 }
2531 
2532 SDValue DAGCombiner::visitADD(SDNode *N) {
2533  SDValue N0 = N->getOperand(0);
2534  SDValue N1 = N->getOperand(1);
2535  EVT VT = N0.getValueType();
2536  SDLoc DL(N);
2537 
2538  if (SDValue Combined = visitADDLike(N))
2539  return Combined;
2540 
2541  if (SDValue V = foldAddSubBoolOfMaskedVal(N, DAG))
2542  return V;
2543 
2544  if (SDValue V = foldAddSubOfSignBit(N, DAG))
2545  return V;
2546 
2547  // fold (a+b) -> (a|b) iff a and b share no bits.
2548  if ((!LegalOperations || TLI.isOperationLegal(ISD::OR, VT)) &&
2549  DAG.haveNoCommonBitsSet(N0, N1))
2550  return DAG.getNode(ISD::OR, DL, VT, N0, N1);
2551 
2552  return SDValue();
2553 }
2554 
2555 SDValue DAGCombiner::visitADDSAT(SDNode *N) {
2556  unsigned Opcode = N->getOpcode();
2557  SDValue N0 = N->getOperand(0);
2558  SDValue N1 = N->getOperand(1);
2559  EVT VT = N0.getValueType();
2560  SDLoc DL(N);
2561 
2562  // fold vector ops
2563  if (VT.isVector()) {
2564  // TODO SimplifyVBinOp
2565 
2566  // fold (add_sat x, 0) -> x, vector edition
2568  return N0;
2570  return N1;
2571  }
2572 
2573  // fold (add_sat x, undef) -> -1
2574  if (N0.isUndef() || N1.isUndef())
2575  return DAG.getAllOnesConstant(DL, VT);
2576 
2578  // canonicalize constant to RHS
2580  return DAG.getNode(Opcode, DL, VT, N1, N0);
2581  // fold (add_sat c1, c2) -> c3
2582  return DAG.FoldConstantArithmetic(Opcode, DL, VT, N0.getNode(),
2583  N1.getNode());
2584  }
2585 
2586  // fold (add_sat x, 0) -> x
2587  if (isNullConstant(N1))
2588  return N0;
2589 
2590  // If it cannot overflow, transform into an add.
2591  if (Opcode == ISD::UADDSAT)
2592  if (DAG.computeOverflowKind(N0, N1) == SelectionDAG::OFK_Never)
2593  return DAG.getNode(ISD::ADD, DL, VT, N0, N1);
2594 
2595  return SDValue();
2596 }
2597 
2598 static SDValue getAsCarry(const TargetLowering &TLI, SDValue V) {
2599  bool Masked = false;
2600 
2601  // First, peel away TRUNCATE/ZERO_EXTEND/AND nodes due to legalization.
2602  while (true) {
2603  if (V.getOpcode() == ISD::TRUNCATE || V.getOpcode() == ISD::ZERO_EXTEND) {
2604  V = V.getOperand(0);
2605  continue;
2606  }
2607 
2608  if (V.getOpcode() == ISD::AND && isOneConstant(V.getOperand(1))) {
2609  Masked = true;
2610  V = V.getOperand(0);
2611  continue;
2612  }
2613 
2614  break;
2615  }
2616 
2617  // If this is not a carry, return.
2618  if (V.getResNo() != 1)
2619  return SDValue();
2620 
2621  if (V.getOpcode() != ISD::ADDCARRY && V.getOpcode() != ISD::SUBCARRY &&
2622  V.getOpcode() != ISD::UADDO && V.getOpcode() != ISD::USUBO)
2623  return SDValue();
2624 
2625  EVT VT = V.getNode()->getValueType(0);
2626  if (!TLI.isOperationLegalOrCustom(V.getOpcode(), VT))
2627  return SDValue();
2628 
2629  // If the result is masked, then no matter what kind of bool it is we can
2630  // return. If it isn't, then we need to make sure the bool type is either 0 or
2631  // 1 and not other values.
2632  if (Masked ||
2633  TLI.getBooleanContents(V.getValueType()) ==
2635  return V;
2636 
2637  return SDValue();
2638 }
2639 
2640 /// Given the operands of an add/sub operation, see if the 2nd operand is a
2641 /// masked 0/1 whose source operand is actually known to be 0/-1. If so, invert
2642 /// the opcode and bypass the mask operation.
2643 static SDValue foldAddSubMasked1(bool IsAdd, SDValue N0, SDValue N1,
2644  SelectionDAG &DAG, const SDLoc &DL) {
2645  if (N1.getOpcode() != ISD::AND || !isOneOrOneSplat(N1->getOperand(1)))
2646  return SDValue();
2647 
2648  EVT VT = N0.getValueType();
2649  if (DAG.ComputeNumSignBits(N1.getOperand(0)) != VT.getScalarSizeInBits())
2650  return SDValue();
2651 
2652  // add N0, (and (AssertSext X, i1), 1) --> sub N0, X
2653  // sub N0, (and (AssertSext X, i1), 1) --> add N0, X
2654  return DAG.getNode(IsAdd ? ISD::SUB : ISD::ADD, DL, VT, N0, N1.getOperand(0));
2655 }
2656 
2657 /// Helper for doing combines based on N0 and N1 being added to each other.
2658 SDValue DAGCombiner::visitADDLikeCommutative(SDValue N0, SDValue N1,
2659  SDNode *LocReference) {
2660  EVT VT = N0.getValueType();
2661  SDLoc DL(LocReference);
2662 
2663  // fold (add x, shl(0 - y, n)) -> sub(x, shl(y, n))
2664  if (N1.getOpcode() == ISD::SHL && N1.getOperand(0).getOpcode() == ISD::SUB &&
2666  return DAG.getNode(ISD::SUB, DL, VT, N0,
2667  DAG.getNode(ISD::SHL, DL, VT,
2668  N1.getOperand(0).getOperand(1),
2669  N1.getOperand(1)));
2670 
2671  if (SDValue V = foldAddSubMasked1(true, N0, N1, DAG, DL))
2672  return V;
2673 
2674  // Look for:
2675  // add (add x, 1), y
2676  // And if the target does not like this form then turn into:
2677  // sub y, (xor x, -1)
2678  if (!TLI.preferIncOfAddToSubOfNot(VT) && N0.hasOneUse() &&
2679  N0.getOpcode() == ISD::ADD && isOneOrOneSplat(N0.getOperand(1))) {
2680  SDValue Not = DAG.getNode(ISD::XOR, DL, VT, N0.getOperand(0),
2681  DAG.getAllOnesConstant(DL, VT));
2682  return DAG.getNode(ISD::SUB, DL, VT, N1, Not);
2683  }
2684 
2685  // Hoist one-use subtraction by non-opaque constant:
2686  // (x - C) + y -> (x + y) - C
2687  // This is necessary because SUB(X,C) -> ADD(X,-C) doesn't work for vectors.
2688  if (N0.hasOneUse() && N0.getOpcode() == ISD::SUB &&
2689  isConstantOrConstantVector(N0.getOperand(1), /*NoOpaques=*/true)) {
2690  SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), N1);
2691  return DAG.getNode(ISD::SUB, DL, VT, Add, N0.getOperand(1));
2692  }
2693  // Hoist one-use subtraction from non-opaque constant:
2694  // (C - x) + y -> (y - x) + C
2695  if (N0.hasOneUse() && N0.getOpcode() == ISD::SUB &&
2696  isConstantOrConstantVector(N0.getOperand(0), /*NoOpaques=*/true)) {
2697  SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N1, N0.getOperand(1));
2698  return DAG.getNode(ISD::ADD, DL, VT, Sub, N0.getOperand(0));
2699  }
2700 
2701  // If the target's bool is represented as 0/1, prefer to make this 'sub 0/1'
2702  // rather than 'add 0/-1' (the zext should get folded).
2703  // add (sext i1 Y), X --> sub X, (zext i1 Y)
2704  if (N0.getOpcode() == ISD::SIGN_EXTEND &&
2705  N0.getOperand(0).getScalarValueSizeInBits() == 1 &&
2707  SDValue ZExt = DAG.getNode(ISD::ZERO_EXTEND, DL, VT, N0.getOperand(0));
2708  return DAG.getNode(ISD::SUB, DL, VT, N1, ZExt);
2709  }
2710 
2711  // add X, (sextinreg Y i1) -> sub X, (and Y 1)
2712  if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
2713  VTSDNode *TN = cast<VTSDNode>(N1.getOperand(1));
2714  if (TN->getVT() == MVT::i1) {
2715  SDValue ZExt = DAG.getNode(ISD::AND, DL, VT, N1.getOperand(0),
2716  DAG.getConstant(1, DL, VT));
2717  return DAG.getNode(ISD::SUB, DL, VT, N0, ZExt);
2718  }
2719  }
2720 
2721  // (add X, (addcarry Y, 0, Carry)) -> (addcarry X, Y, Carry)
2722  if (N1.getOpcode() == ISD::ADDCARRY && isNullConstant(N1.getOperand(1)) &&
2723  N1.getResNo() == 0)
2724  return DAG.getNode(ISD::ADDCARRY, DL, N1->getVTList(),
2725  N0, N1.getOperand(0), N1.getOperand(2));
2726 
2727  // (add X, Carry) -> (addcarry X, 0, Carry)
2729  if (SDValue Carry = getAsCarry(TLI, N1))
2730  return DAG.getNode(ISD::ADDCARRY, DL,
2731  DAG.getVTList(VT, Carry.getValueType()), N0,
2732  DAG.getConstant(0, DL, VT), Carry);
2733 
2734  return SDValue();
2735 }
2736 
2737 SDValue DAGCombiner::visitADDC(SDNode *N) {
2738  SDValue N0 = N->getOperand(0);
2739  SDValue N1 = N->getOperand(1);
2740  EVT VT = N0.getValueType();
2741  SDLoc DL(N);
2742 
2743  // If the flag result is dead, turn this into an ADD.
2744  if (!N->hasAnyUseOfValue(1))
2745  return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
2746  DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
2747 
2748  // canonicalize constant to RHS.
2751  if (N0C && !N1C)
2752  return DAG.getNode(ISD::ADDC, DL, N->getVTList(), N1, N0);
2753 
2754  // fold (addc x, 0) -> x + no carry out
2755  if (isNullConstant(N1))
2756  return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE,
2757  DL, MVT::Glue));
2758 
2759  // If it cannot overflow, transform into an add.
2760  if (DAG.computeOverflowKind(N0, N1) == SelectionDAG::OFK_Never)
2761  return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
2762  DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
2763 
2764  return SDValue();
2765 }
2766 
2767 static SDValue flipBoolean(SDValue V, const SDLoc &DL,
2768  SelectionDAG &DAG, const TargetLowering &TLI) {
2769  EVT VT = V.getValueType();
2770 
2771  SDValue Cst;
2772  switch (TLI.getBooleanContents(VT)) {
2775  Cst = DAG.getConstant(1, DL, VT);
2776  break;
2778  Cst = DAG.getAllOnesConstant(DL, VT);
2779  break;
2780  }
2781 
2782  return DAG.getNode(ISD::XOR, DL, VT, V, Cst);
2783 }
2784 
2785 /**
2786  * Flips a boolean if it is cheaper to compute. If the Force parameters is set,
2787  * then the flip also occurs if computing the inverse is the same cost.
2788  * This function returns an empty SDValue in case it cannot flip the boolean
2789  * without increasing the cost of the computation. If you want to flip a boolean
2790  * no matter what, use flipBoolean.
2791  */
2793  const TargetLowering &TLI,
2794  bool Force) {
2795  if (Force && isa<ConstantSDNode>(V))
2796  return flipBoolean(V, SDLoc(V), DAG, TLI);
2797 
2798  if (V.getOpcode() != ISD::XOR)
2799  return SDValue();
2800 
2801  ConstantSDNode *Const = isConstOrConstSplat(V.getOperand(1), false);
2802  if (!Const)
2803  return SDValue();
2804 
2805  EVT VT = V.getValueType();
2806 
2807  bool IsFlip = false;
2808  switch(TLI.getBooleanContents(VT)) {
2810  IsFlip = Const->isOne();
2811  break;
2813  IsFlip = Const->isAllOnesValue();
2814  break;
2816  IsFlip = (Const->getAPIntValue() & 0x01) == 1;
2817  break;
2818  }
2819 
2820  if (IsFlip)
2821  return V.getOperand(0);
2822  if (Force)
2823  return flipBoolean(V, SDLoc(V), DAG, TLI);
2824  return SDValue();
2825 }
2826 
2827 SDValue DAGCombiner::visitADDO(SDNode *N) {
2828  SDValue N0 = N->getOperand(0);
2829  SDValue N1 = N->getOperand(1);
2830  EVT VT = N0.getValueType();
2831  bool IsSigned = (ISD::SADDO == N->getOpcode());
2832 
2833  EVT CarryVT = N->getValueType(1);
2834  SDLoc DL(N);
2835 
2836  // If the flag result is dead, turn this into an ADD.
2837  if (!N->hasAnyUseOfValue(1))
2838  return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
2839  DAG.getUNDEF(CarryVT));
2840 
2841  // canonicalize constant to RHS.
2844  return DAG.getNode(N->getOpcode(), DL, N->getVTList(), N1, N0);
2845 
2846  // fold (addo x, 0) -> x + no carry out
2847  if (isNullOrNullSplat(N1))
2848  return CombineTo(N, N0, DAG.getConstant(0, DL, CarryVT));
2849 
2850  if (!IsSigned) {
2851  // If it cannot overflow, transform into an add.
2852  if (DAG.computeOverflowKind(N0, N1) == SelectionDAG::OFK_Never)
2853  return CombineTo(N, DAG.getNode(ISD::ADD, DL, VT, N0, N1),
2854  DAG.getConstant(0, DL, CarryVT));
2855 
2856  // fold (uaddo (xor a, -1), 1) -> (usub 0, a) and flip carry.
2857  if (isBitwiseNot(N0) && isOneOrOneSplat(N1)) {
2858  SDValue Sub = DAG.getNode(ISD::USUBO, DL, N->getVTList(),
2859  DAG.getConstant(0, DL, VT), N0.getOperand(0));
2860  return CombineTo(N, Sub,
2861  flipBoolean(Sub.getValue(1), DL, DAG, TLI));
2862  }
2863 
2864  if (SDValue Combined = visitUADDOLike(N0, N1, N))
2865  return Combined;
2866 
2867  if (SDValue Combined = visitUADDOLike(N1, N0, N))
2868  return Combined;
2869  }
2870 
2871  return SDValue();
2872 }
2873 
2874 SDValue DAGCombiner::visitUADDOLike(SDValue N0, SDValue N1, SDNode *N) {
2875  EVT VT = N0.getValueType();
2876  if (VT.isVector())
2877  return SDValue();
2878 
2879  // (uaddo X, (addcarry Y, 0, Carry)) -> (addcarry X, Y, Carry)
2880  // If Y + 1 cannot overflow.
2881  if (N1.getOpcode() == ISD::ADDCARRY && isNullConstant(N1.getOperand(1))) {
2882  SDValue Y = N1.getOperand(0);
2883  SDValue One = DAG.getConstant(1, SDLoc(N), Y.getValueType());
2884  if (DAG.computeOverflowKind(Y, One) == SelectionDAG::OFK_Never)
2885  return DAG.getNode(ISD::ADDCARRY, SDLoc(N), N->getVTList(), N0, Y,
2886  N1.getOperand(2));
2887  }
2888 
2889  // (uaddo X, Carry) -> (addcarry X, 0, Carry)
2891  if (SDValue Carry = getAsCarry(TLI, N1))
2892  return DAG.getNode(ISD::ADDCARRY, SDLoc(N), N->getVTList(), N0,
2893  DAG.getConstant(0, SDLoc(N), VT), Carry);
2894 
2895  return SDValue();
2896 }
2897 
2898 SDValue DAGCombiner::visitADDE(SDNode *N) {
2899  SDValue N0 = N->getOperand(0);
2900  SDValue N1 = N->getOperand(1);
2901  SDValue CarryIn = N->getOperand(2);
2902 
2903  // canonicalize constant to RHS
2906  if (N0C && !N1C)
2907  return DAG.getNode(ISD::ADDE, SDLoc(N), N->getVTList(),
2908  N1, N0, CarryIn);
2909 
2910  // fold (adde x, y, false) -> (addc x, y)
2911  if (CarryIn.getOpcode() == ISD::CARRY_FALSE)
2912  return DAG.getNode(ISD::ADDC, SDLoc(N), N->getVTList(), N0, N1);
2913 
2914  return SDValue();
2915 }
2916 
2917 SDValue DAGCombiner::visitADDCARRY(SDNode *N) {
2918  SDValue N0 = N->getOperand(0);
2919  SDValue N1 = N->getOperand(1);
2920  SDValue CarryIn = N->getOperand(2);
2921  SDLoc DL(N);
2922 
2923  // canonicalize constant to RHS
2926  if (N0C && !N1C)
2927  return DAG.getNode(ISD::ADDCARRY, DL, N->getVTList(), N1, N0, CarryIn);
2928 
2929  // fold (addcarry x, y, false) -> (uaddo x, y)
2930  if (isNullConstant(CarryIn)) {
2931  if (!LegalOperations ||
2933  return DAG.getNode(ISD::UADDO, DL, N->getVTList(), N0, N1);
2934  }
2935 
2936  // fold (addcarry 0, 0, X) -> (and (ext/trunc X), 1) and no carry.
2937  if (isNullConstant(N0) && isNullConstant(N1)) {
2938  EVT VT = N0.getValueType();
2939  EVT CarryVT = CarryIn.getValueType();
2940  SDValue CarryExt = DAG.getBoolExtOrTrunc(CarryIn, DL, VT, CarryVT);
2941  AddToWorklist(CarryExt.getNode());
2942  return CombineTo(N, DAG.getNode(ISD::AND, DL, VT, CarryExt,
2943  DAG.getConstant(1, DL, VT)),
2944  DAG.getConstant(0, DL, CarryVT));
2945  }
2946 
2947  if (SDValue Combined = visitADDCARRYLike(N0, N1, CarryIn, N))
2948  return Combined;
2949 
2950  if (SDValue Combined = visitADDCARRYLike(N1, N0, CarryIn, N))
2951  return Combined;
2952 
2953  return SDValue();
2954 }
2955 
2956 /**
2957  * If we are facing some sort of diamond carry propapagtion pattern try to
2958  * break it up to generate something like:
2959  * (addcarry X, 0, (addcarry A, B, Z):Carry)
2960  *
2961  * The end result is usually an increase in operation required, but because the
2962  * carry is now linearized, other tranforms can kick in and optimize the DAG.
2963  *
2964  * Patterns typically look something like
2965  * (uaddo A, B)
2966  * / \
2967  * Carry Sum
2968  * | \
2969  * | (addcarry *, 0, Z)
2970  * | /
2971  * \ Carry
2972  * | /
2973  * (addcarry X, *, *)
2974  *
2975  * But numerous variation exist. Our goal is to identify A, B, X and Z and
2976  * produce a combine with a single path for carry propagation.
2977  */
2979  SDValue X, SDValue Carry0, SDValue Carry1,
2980  SDNode *N) {
2981  if (Carry1.getResNo() != 1 || Carry0.getResNo() != 1)
2982  return SDValue();
2983  if (Carry1.getOpcode() != ISD::UADDO)
2984  return SDValue();
2985 
2986  SDValue Z;
2987 
2988  /**
2989  * First look for a suitable Z. It will present itself in the form of
2990  * (addcarry Y, 0, Z) or its equivalent (uaddo Y, 1) for Z=true
2991  */
2992  if (Carry0.getOpcode() == ISD::ADDCARRY &&
2993  isNullConstant(Carry0.getOperand(1))) {
2994  Z = Carry0.getOperand(2);
2995  } else if (Carry0.getOpcode() == ISD::UADDO &&
2996  isOneConstant(Carry0.getOperand(1))) {
2997  EVT VT = Combiner.getSetCCResultType(Carry0.getValueType());
2998  Z = DAG.getConstant(1, SDLoc(Carry0.getOperand(1)), VT);
2999  } else {
3000  // We couldn't find a suitable Z.
3001  return SDValue();
3002  }
3003 
3004 
3005  auto cancelDiamond = [&](SDValue A,SDValue B) {
3006  SDLoc DL(N);
3007  SDValue NewY = DAG.getNode(ISD::ADDCARRY, DL, Carry0->getVTList(), A, B, Z);
3008  Combiner.AddToWorklist(NewY.getNode());
3009  return DAG.getNode(ISD::ADDCARRY, DL, N->getVTList(), X,
3010  DAG.getConstant(0, DL, X.getValueType()),
3011  NewY.getValue(1));
3012  };
3013 
3014  /**
3015  * (uaddo A, B)
3016  * |
3017  * Sum
3018  * |
3019  * (addcarry *, 0, Z)
3020  */
3021  if (Carry0.getOperand(0) == Carry1.getValue(0)) {
3022  return cancelDiamond(Carry1.getOperand(0), Carry1.getOperand(1));
3023  }
3024 
3025  /**
3026  * (addcarry A, 0, Z)
3027  * |
3028  * Sum
3029  * |
3030  * (uaddo *, B)
3031  */
3032  if (Carry1.getOperand(0) == Carry0.getValue(0)) {
3033  return cancelDiamond(Carry0.getOperand(0), Carry1.getOperand(1));
3034  }
3035 
3036  if (Carry1.getOperand(1) == Carry0.getValue(0)) {
3037  return cancelDiamond(Carry1.getOperand(0), Carry0.getOperand(0));
3038  }
3039 
3040  return SDValue();
3041 }
3042 
3043 SDValue DAGCombiner::visitADDCARRYLike(SDValue N0, SDValue N1, SDValue CarryIn,
3044  SDNode *N) {
3045  // fold (addcarry (xor a, -1), b, c) -> (subcarry b, a, !c) and flip carry.
3046  if (isBitwiseNot(N0))
3047  if (SDValue NotC = extractBooleanFlip(CarryIn, DAG, TLI, true)) {
3048  SDLoc DL(N);
3049  SDValue Sub = DAG.getNode(ISD::SUBCARRY, DL, N->getVTList(), N1,
3050  N0.getOperand(0), NotC);
3051  return CombineTo(N, Sub,
3052  flipBoolean(Sub.getValue(1), DL, DAG, TLI));
3053  }
3054 
3055  // Iff the flag result is dead:
3056  // (addcarry (add|uaddo X, Y), 0, Carry) -> (addcarry X, Y, Carry)
3057  // Don't do this if the Carry comes from the uaddo. It won't remove the uaddo
3058  // or the dependency between the instructions.
3059  if ((N0.getOpcode() == ISD::ADD ||
3060  (N0.getOpcode() == ISD::UADDO && N0.getResNo() == 0 &&
3061  N0.getValue(1) != CarryIn)) &&
3062  isNullConstant(N1) && !N->hasAnyUseOfValue(1))
3063  return DAG.getNode(ISD::ADDCARRY, SDLoc(N), N->getVTList(),
3064  N0.getOperand(0), N0.getOperand(1), CarryIn);
3065 
3066  /**
3067  * When one of the addcarry argument is itself a carry, we may be facing
3068  * a diamond carry propagation. In which case we try to transform the DAG
3069  * to ensure linear carry propagation if that is possible.
3070  */
3071  if (auto Y = getAsCarry(TLI, N1)) {
3072  // Because both are carries, Y and Z can be swapped.
3073  if (auto R = combineADDCARRYDiamond(*this, DAG, N0, Y, CarryIn, N))
3074  return R;
3075  if (auto R = combineADDCARRYDiamond(*this, DAG, N0, CarryIn, Y, N))
3076  return R;
3077  }
3078 
3079  return SDValue();
3080 }
3081 
3082 // Since it may not be valid to emit a fold to zero for vector initializers
3083 // check if we can before folding.
3084 static SDValue tryFoldToZero(const SDLoc &DL, const TargetLowering &TLI, EVT VT,
3085  SelectionDAG &DAG, bool LegalOperations) {
3086  if (!VT.isVector())
3087  return DAG.getConstant(0, DL, VT);
3088  if (!LegalOperations || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT))
3089  return DAG.getConstant(0, DL, VT);
3090  return SDValue();
3091 }
3092 
3093 SDValue DAGCombiner::visitSUB(SDNode *N) {
3094  SDValue N0 = N->getOperand(0);
3095  SDValue N1 = N->getOperand(1);
3096  EVT VT = N0.getValueType();
3097  SDLoc DL(N);
3098 
3099  // fold vector ops
3100  if (VT.isVector()) {
3101  if (SDValue FoldedVOp = SimplifyVBinOp(N))
3102  return FoldedVOp;
3103 
3104  // fold (sub x, 0) -> x, vector edition
3106  return N0;
3107  }
3108 
3109  // fold (sub x, x) -> 0
3110  // FIXME: Refactor this and xor and other similar operations together.
3111  if (N0 == N1)
3112  return tryFoldToZero(DL, TLI, VT, DAG, LegalOperations);
3115  // fold (sub c1, c2) -> c1-c2
3116  return DAG.FoldConstantArithmetic(ISD::SUB, DL, VT, N0.getNode(),
3117  N1.getNode());
3118  }
3119 
3120  if (SDValue NewSel = foldBinOpIntoSelect(N))
3121  return NewSel;
3122 
3124 
3125  // fold (sub x, c) -> (add x, -c)
3126  if (N1C) {
3127  return DAG.getNode(ISD::ADD, DL, VT, N0,
3128  DAG.getConstant(-N1C->getAPIntValue(), DL, VT));
3129  }
3130 
3131  if (isNullOrNullSplat(N0)) {
3132  unsigned BitWidth = VT.getScalarSizeInBits();
3133  // Right-shifting everything out but the sign bit followed by negation is
3134  // the same as flipping arithmetic/logical shift type without the negation:
3135  // -(X >>u 31) -> (X >>s 31)
3136  // -(X >>s 31) -> (X >>u 31)
3137  if (N1->getOpcode() == ISD::SRA || N1->getOpcode() == ISD::SRL) {
3138  ConstantSDNode *ShiftAmt = isConstOrConstSplat(N1.getOperand(1));
3139  if (ShiftAmt && ShiftAmt->getAPIntValue() == (BitWidth - 1)) {
3140  auto NewSh = N1->getOpcode() == ISD::SRA ? ISD::SRL : ISD::SRA;
3141  if (!LegalOperations || TLI.isOperationLegal(NewSh, VT))
3142  return DAG.getNode(NewSh, DL, VT, N1.getOperand(0), N1.getOperand(1));
3143  }
3144  }
3145 
3146  // 0 - X --> 0 if the sub is NUW.
3147  if (N->getFlags().hasNoUnsignedWrap())
3148  return N0;
3149 
3150  if (DAG.MaskedValueIsZero(N1, ~APInt::getSignMask(BitWidth))) {
3151  // N1 is either 0 or the minimum signed value. If the sub is NSW, then
3152  // N1 must be 0 because negating the minimum signed value is undefined.
3153  if (N->getFlags().hasNoSignedWrap())
3154  return N0;
3155 
3156  // 0 - X --> X if X is 0 or the minimum signed value.
3157  return N1;
3158  }
3159  }
3160 
3161  // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1)
3162  if (isAllOnesOrAllOnesSplat(N0))
3163  return DAG.getNode(ISD::XOR, DL, VT, N1, N0);
3164 
3165  // fold (A - (0-B)) -> A+B
3166  if (N1.getOpcode() == ISD::SUB && isNullOrNullSplat(N1.getOperand(0)))
3167  return DAG.getNode(ISD::ADD, DL, VT, N0, N1.getOperand(1));
3168 
3169  // fold A-(A-B) -> B
3170  if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(0))
3171  return N1.getOperand(1);
3172 
3173  // fold (A+B)-A -> B
3174  if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1)
3175  return N0.getOperand(1);
3176 
3177  // fold (A+B)-B -> A
3178  if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1)
3179  return N0.getOperand(0);
3180 
3181  // fold (A+C1)-C2 -> A+(C1-C2)
3182  if (N0.getOpcode() == ISD::ADD &&
3183  isConstantOrConstantVector(N1, /* NoOpaques */ true) &&
3184  isConstantOrConstantVector(N0.getOperand(1), /* NoOpaques */ true)) {
3185  SDValue NewC = DAG.FoldConstantArithmetic(
3186  ISD::SUB, DL, VT, N0.getOperand(1).getNode(), N1.getNode());
3187  assert(NewC && "Constant folding failed");
3188  return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0), NewC);
3189  }
3190 
3191  // fold C2-(A+C1) -> (C2-C1)-A
3192  if (N1.getOpcode() == ISD::ADD) {
3193  SDValue N11 = N1.getOperand(1);
3194  if (isConstantOrConstantVector(N0, /* NoOpaques */ true) &&
3195  isConstantOrConstantVector(N11, /* NoOpaques */ true)) {
3196  SDValue NewC = DAG.FoldConstantArithmetic(ISD::SUB, DL, VT, N0.getNode(),
3197  N11.getNode());
3198  assert(NewC && "Constant folding failed");
3199  return DAG.getNode(ISD::SUB, DL, VT, NewC, N1.getOperand(0));
3200  }
3201  }
3202 
3203  // fold (A-C1)-C2 -> A-(C1+C2)
3204  if (N0.getOpcode() == ISD::SUB &&
3205  isConstantOrConstantVector(N1, /* NoOpaques */ true) &&
3206  isConstantOrConstantVector(N0.getOperand(1), /* NoOpaques */ true)) {
3207  SDValue NewC = DAG.FoldConstantArithmetic(
3208  ISD::ADD, DL, VT, N0.getOperand(1).getNode(), N1.getNode());
3209  assert(NewC && "Constant folding failed");
3210  return DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0), NewC);
3211  }
3212 
3213  // fold (c1-A)-c2 -> (c1-c2)-A
3214  if (N0.getOpcode() == ISD::SUB &&
3215  isConstantOrConstantVector(N1, /* NoOpaques */ true) &&
3216  isConstantOrConstantVector(N0.getOperand(0), /* NoOpaques */ true)) {
3217  SDValue NewC = DAG.FoldConstantArithmetic(
3218  ISD::SUB, DL, VT, N0.getOperand(0).getNode(), N1.getNode());
3219  assert(NewC && "Constant folding failed");
3220  return DAG.getNode(ISD::SUB, DL, VT, NewC, N0.getOperand(1));
3221  }
3222 
3223  // fold ((A+(B+or-C))-B) -> A+or-C
3224  if (N0.getOpcode() == ISD::ADD &&
3225  (N0.getOperand(1).getOpcode() == ISD::SUB ||
3226  N0.getOperand(1).getOpcode() == ISD::ADD) &&
3227  N0.getOperand(1).getOperand(0) == N1)
3228  return DAG.getNode(N0.getOperand(1).getOpcode(), DL, VT, N0.getOperand(0),
3229  N0.getOperand(1).getOperand(1));
3230 
3231  // fold ((A+(C+B))-B) -> A+C
3232  if (N0.getOpcode() == ISD::ADD && N0.getOperand(1).getOpcode() == ISD::ADD &&
3233  N0.getOperand(1).getOperand(1) == N1)
3234  return DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(0),
3235  N0.getOperand(1).getOperand(0));
3236 
3237  // fold ((A-(B-C))-C) -> A-B
3238  if (N0.getOpcode() == ISD::SUB && N0.getOperand(1).getOpcode() == ISD::SUB &&
3239  N0.getOperand(1).getOperand(1) == N1)
3240  return DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0),
3241  N0.getOperand(1).getOperand(0));
3242 
3243  // fold (A-(B-C)) -> A+(C-B)
3244  if (N1.getOpcode() == ISD::SUB && N1.hasOneUse())
3245  return DAG.getNode(ISD::ADD, DL, VT, N0,
3246  DAG.getNode(ISD::SUB, DL, VT, N1.getOperand(1),
3247  N1.getOperand(0)));
3248 
3249  // fold (X - (-Y * Z)) -> (X + (Y * Z))
3250  if (N1.getOpcode() == ISD::MUL && N1.hasOneUse()) {
3251  if (N1.getOperand(0).getOpcode() == ISD::SUB &&
3253  SDValue Mul = DAG.getNode(ISD::MUL, DL, VT,
3254  N1.getOperand(0).getOperand(1),
3255  N1.getOperand(1));
3256  return DAG.getNode(ISD::ADD, DL, VT, N0, Mul);
3257  }
3258  if (N1.getOperand(1).getOpcode() == ISD::SUB &&
3260  SDValue Mul = DAG.getNode(ISD::MUL, DL, VT,
3261  N1.getOperand(0),
3262  N1.getOperand(1).getOperand(1));
3263  return DAG.getNode(ISD::ADD, DL, VT, N0, Mul);
3264  }
3265  }
3266 
3267  // If either operand of a sub is undef, the result is undef
3268  if (N0.isUndef())
3269  return N0;
3270  if (N1.isUndef())
3271  return N1;
3272 
3273  if (SDValue V = foldAddSubBoolOfMaskedVal(N, DAG))
3274  return V;
3275 
3276  if (SDValue V = foldAddSubOfSignBit(N, DAG))
3277  return V;
3278 
3279  if (SDValue V = foldAddSubMasked1(false, N0, N1, DAG, SDLoc(N)))
3280  return V;
3281 
3282  // (x - y) - 1 -> add (xor y, -1), x
3283  if (N0.hasOneUse() && N0.getOpcode() == ISD::SUB && isOneOrOneSplat(N1)) {
3284  SDValue Xor = DAG.getNode(ISD::XOR, DL, VT, N0.getOperand(1),
3285  DAG.getAllOnesConstant(DL, VT));
3286  return DAG.getNode(ISD::ADD, DL, VT, Xor, N0.getOperand(0));
3287  }
3288 
3289  // Look for:
3290  // sub y, (xor x, -1)
3291  // And if the target does not like this form then turn into:
3292  // add (add x, y), 1
3293  if (TLI.preferIncOfAddToSubOfNot(VT) && N1.hasOneUse() && isBitwiseNot(N1)) {
3294  SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0, N1.getOperand(0));
3295  return DAG.getNode(ISD::ADD, DL, VT, Add, DAG.getConstant(1, DL, VT));
3296  }
3297 
3298  // Hoist one-use addition by non-opaque constant:
3299  // (x + C) - y -> (x - y) + C
3300  if (N0.hasOneUse() && N0.getOpcode() == ISD::ADD &&
3301  isConstantOrConstantVector(N0.getOperand(1), /*NoOpaques=*/true)) {
3302  SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0), N1);
3303  return DAG.getNode(ISD::ADD, DL, VT, Sub, N0.getOperand(1));
3304  }
3305  // y - (x + C) -> (y - x) - C
3306  if (N1.hasOneUse() && N1.getOpcode() == ISD::ADD &&
3307  isConstantOrConstantVector(N1.getOperand(1), /*NoOpaques=*/true)) {
3308  SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, N1.getOperand(0));
3309  return DAG.getNode(ISD::SUB, DL, VT, Sub, N1.getOperand(1));
3310  }
3311  // (x - C) - y -> (x - y) - C
3312  // This is necessary because SUB(X,C) -> ADD(X,-C) doesn't work for vectors.
3313  if (N0.hasOneUse() && N0.getOpcode() == ISD::SUB &&
3314  isConstantOrConstantVector(N0.getOperand(1), /*NoOpaques=*/true)) {
3315  SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0), N1);
3316  return DAG.getNode(ISD::SUB, DL, VT, Sub, N0.getOperand(1));
3317  }
3318  // (C - x) - y -> C - (x + y)
3319  if (N0.hasOneUse() && N0.getOpcode() == ISD::SUB &&
3320  isConstantOrConstantVector(N0.getOperand(0), /*NoOpaques=*/true)) {
3321  SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0.getOperand(1), N1);
3322  return DAG.getNode(ISD::SUB, DL, VT, N0.getOperand(0), Add);
3323  }
3324 
3325  // If the target's bool is represented as 0/-1, prefer to make this 'add 0/-1'
3326  // rather than 'sub 0/1' (the sext should get folded).
3327  // sub X, (zext i1 Y) --> add X, (sext i1 Y)
3328  if (N1.getOpcode() == ISD::ZERO_EXTEND &&
3329  N1.getOperand(0).getScalarValueSizeInBits() == 1 &&
3330  TLI.getBooleanContents(VT) ==
3332  SDValue SExt = DAG.getNode(ISD::SIGN_EXTEND, DL, VT, N1.getOperand(0));
3333  return DAG.getNode(ISD::ADD, DL, VT, N0, SExt);
3334  }
3335 
3336  // fold Y = sra (X, size(X)-1); sub (xor (X, Y), Y) -> (abs X)
3337  if (TLI.isOperationLegalOrCustom(ISD::ABS, VT)) {
3338  if (N0.getOpcode() == ISD::XOR && N1.getOpcode() == ISD::SRA) {
3339  SDValue X0 = N0.getOperand(0), X1 = N0.getOperand(1);
3340  SDValue S0 = N1.getOperand(0);
3341  if ((X0 == S0 && X1 == N1) || (X0 == N1 && X1 == S0)) {
3342  unsigned OpSizeInBits = VT.getScalarSizeInBits();
3344  if (C->getAPIntValue() == (OpSizeInBits - 1))
3345  return DAG.getNode(ISD::ABS, SDLoc(N), VT, S0);
3346  }
3347  }
3348  }
3349 
3350  // If the relocation model supports it, consider symbol offsets.
3351  if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(N0))
3352  if (!LegalOperations && TLI.isOffsetFoldingLegal(GA)) {
3353  // fold (sub Sym, c) -> Sym-c
3354  if (N1C && GA->getOpcode() == ISD::GlobalAddress)
3355  return DAG.getGlobalAddress(GA->getGlobal(), SDLoc(N1C), VT,
3356  GA->getOffset() -
3357  (uint64_t)N1C->getSExtValue());
3358  // fold (sub Sym+c1, Sym+c2) -> c1-c2
3359  if (GlobalAddressSDNode *GB = dyn_cast<GlobalAddressSDNode>(N1))
3360  if (GA->getGlobal() == GB->getGlobal())
3361  return DAG.getConstant((uint64_t)GA->getOffset() - GB->getOffset(),
3362  DL, VT);
3363  }
3364 
3365  // sub X, (sextinreg Y i1) -> add X, (and Y 1)
3366  if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
3367  VTSDNode *TN = cast<VTSDNode>(N1.getOperand(1));
3368  if (TN->getVT() == MVT::i1) {
3369  SDValue ZExt = DAG.getNode(ISD::AND, DL, VT, N1.getOperand(0),
3370  DAG.getConstant(1, DL, VT));
3371  return DAG.getNode(ISD::ADD, DL, VT, N0, ZExt);
3372  }
3373  }
3374 
3375  // Prefer an add for more folding potential and possibly better codegen:
3376  // sub N0, (lshr N10, width-1) --> add N0, (ashr N10, width-1)
3377  if (!LegalOperations && N1.getOpcode() == ISD::SRL && N1.hasOneUse()) {
3378  SDValue ShAmt = N1.getOperand(1);
3379  ConstantSDNode *ShAmtC = isConstOrConstSplat(ShAmt);
3380  if (ShAmtC &&
3381  ShAmtC->getAPIntValue() == (N1.getScalarValueSizeInBits() - 1)) {
3382  SDValue SRA = DAG.getNode(ISD::SRA, DL, VT, N1.getOperand(0), ShAmt);
3383  return DAG.getNode(ISD::ADD, DL, VT, N0, SRA);
3384  }
3385  }
3386 
3387  return SDValue();
3388 }
3389 
3390 SDValue DAGCombiner::visitSUBSAT(SDNode *N) {
3391  SDValue N0 = N->getOperand(0);
3392  SDValue N1 = N->getOperand(1);
3393  EVT VT = N0.getValueType();
3394  SDLoc DL(N);
3395 
3396  // fold vector ops
3397  if (VT.isVector()) {
3398  // TODO SimplifyVBinOp
3399 
3400  // fold (sub_sat x, 0) -> x, vector edition
3402  return N0;
3403  }
3404 
3405  // fold (sub_sat x, undef) -> 0
3406  if (N0.isUndef() || N1.isUndef())
3407  return DAG.getConstant(0, DL, VT);
3408 
3409  // fold (sub_sat x, x) -> 0
3410  if (N0 == N1)
3411  return DAG.getConstant(0, DL, VT);
3412 
3415  // fold (sub_sat c1, c2) -> c3
3416  return DAG.FoldConstantArithmetic(N->getOpcode(), DL, VT, N0.getNode(),
3417  N1.getNode());
3418  }
3419 
3420  // fold (sub_sat x, 0) -> x
3421  if (isNullConstant(N1))
3422  return N0;
3423 
3424  return SDValue();
3425 }
3426 
3427 SDValue DAGCombiner::visitSUBC(SDNode *N) {
3428  SDValue N0 = N->getOperand(0);
3429  SDValue N1 = N->getOperand(1);
3430  EVT VT = N0.getValueType();
3431  SDLoc DL(N);
3432 
3433  // If the flag result is dead, turn this into an SUB.
3434  if (!N->hasAnyUseOfValue(1))
3435  return CombineTo(N, DAG.getNode(ISD::SUB, DL, VT, N0, N1),
3436  DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
3437 
3438  // fold (subc x, x) -> 0 + no borrow
3439  if (N0 == N1)
3440  return CombineTo(N, DAG.getConstant(0, DL, VT),
3441  DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
3442 
3443  // fold (subc x, 0) -> x + no borrow
3444  if (isNullConstant(N1))
3445  return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
3446 
3447  // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1) + no borrow
3448  if (isAllOnesConstant(N0))
3449  return CombineTo(N, DAG.getNode(ISD::XOR, DL, VT, N1, N0),
3450  DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
3451 
3452  return SDValue();
3453 }
3454 
3455 SDValue DAGCombiner::visitSUBO(SDNode *N) {
3456  SDValue N0 = N->getOperand(0);
3457  SDValue N1 = N->getOperand(1);
3458  EVT VT = N0.getValueType();
3459  bool IsSigned = (ISD::SSUBO == N->getOpcode());
3460 
3461  EVT CarryVT = N->getValueType(1);
3462  SDLoc DL(N);
3463 
3464  // If the flag result is dead, turn this into an SUB.
3465  if (!N->hasAnyUseOfValue(1))
3466  return CombineTo(N, DAG.getNode(ISD::SUB, DL, VT, N0, N1),
3467  DAG.getUNDEF(CarryVT));
3468 
3469  // fold (subo x, x) -> 0 + no borrow
3470  if (N0 == N1)
3471  return CombineTo(N, DAG.getConstant(0, DL, VT),
3472  DAG.getConstant(0, DL, CarryVT));
3473 
3475 
3476  // fold (subox, c) -> (addo x, -c)
3477  if (IsSigned && N1C && !N1C->getAPIntValue().isMinSignedValue()) {
3478  return DAG.getNode(ISD::SADDO, DL, N->getVTList(), N0,
3479  DAG.getConstant(-N1C->getAPIntValue(), DL, VT));
3480  }
3481 
3482  // fold (subo x, 0) -> x + no borrow
3483  if (isNullOrNullSplat(N1))
3484  return CombineTo(N, N0, DAG.getConstant(0, DL, CarryVT));
3485 
3486  // Canonicalize (usubo -1, x) -> ~x, i.e. (xor x, -1) + no borrow
3487  if (!IsSigned && isAllOnesOrAllOnesSplat(N0))
3488  return CombineTo(N, DAG.getNode(ISD::XOR, DL, VT, N1, N0),
3489  DAG.getConstant(0, DL, CarryVT));
3490 
3491  return SDValue();
3492 }
3493 
3494 SDValue DAGCombiner::visitSUBE(SDNode *N) {
3495  SDValue N0 = N->getOperand(0);
3496  SDValue N1 = N->getOperand(1);
3497  SDValue CarryIn = N->getOperand(2);
3498 
3499  // fold (sube x, y, false) -> (subc x, y)
3500  if (CarryIn.getOpcode() == ISD::CARRY_FALSE)
3501  return DAG.getNode(ISD::SUBC, SDLoc(N), N->getVTList(), N0, N1);
3502 
3503  return SDValue();
3504 }
3505 
3506 SDValue DAGCombiner::visitSUBCARRY(SDNode *N) {
3507  SDValue N0 = N->getOperand(0);
3508  SDValue N1 = N->getOperand(1);
3509  SDValue CarryIn = N->getOperand(2);
3510 
3511  // fold (subcarry x, y, false) -> (usubo x, y)
3512  if (isNullConstant(CarryIn)) {
3513  if (!LegalOperations ||
3515  return DAG.getNode(ISD::USUBO, SDLoc(N), N->getVTList(), N0, N1);
3516  }
3517 
3518  return SDValue();
3519 }
3520 
3521 // Notice that "mulfix" can be any of SMULFIX, SMULFIXSAT, UMULFIX and
3522 // UMULFIXSAT here.
3523 SDValue DAGCombiner::visitMULFIX(SDNode *N) {
3524  SDValue N0 = N->getOperand(0);
3525  SDValue N1 = N->getOperand(1);
3526  SDValue Scale = N->getOperand(2);
3527  EVT VT = N0.getValueType();
3528 
3529  // fold (mulfix x, undef, scale) -> 0
3530  if (N0.isUndef() || N1.isUndef())
3531  return DAG.getConstant(0, SDLoc(N), VT);
3532 
3533  // Canonicalize constant to RHS (vector doesn't have to splat)
3536  return DAG.getNode(N->getOpcode(), SDLoc(N), VT, N1, N0, Scale);
3537 
3538  // fold (mulfix x, 0, scale) -> 0
3539  if (isNullConstant(N1))
3540  return DAG.getConstant(0, SDLoc(N), VT);
3541 
3542  return SDValue();
3543 }
3544 
3545 SDValue DAGCombiner::visitMUL(SDNode *N) {
3546  SDValue N0 = N->getOperand(0);
3547  SDValue N1 = N->getOperand(1);
3548  EVT VT = N0.getValueType();
3549 
3550  // fold (mul x, undef) -> 0
3551  if (N0.isUndef() || N1.isUndef())
3552  return DAG.getConstant(0, SDLoc(N), VT);
3553 
3554  bool N0IsConst = false;
3555  bool N1IsConst = false;
3556  bool N1IsOpaqueConst = false;
3557  bool N0IsOpaqueConst = false;
3558  APInt ConstValue0, ConstValue1;
3559  // fold vector ops
3560  if (VT.isVector()) {
3561  if (SDValue FoldedVOp = SimplifyVBinOp(N))
3562  return FoldedVOp;
3563 
3564  N0IsConst = ISD::isConstantSplatVector(N0.getNode(), ConstValue0);
3565  N1IsConst = ISD::isConstantSplatVector(N1.getNode(), ConstValue1);
3566  assert((!N0IsConst ||
3567  ConstValue0.getBitWidth() == VT.getScalarSizeInBits()) &&
3568  "Splat APInt should be element width");
3569  assert((!N1IsConst ||
3570  ConstValue1.getBitWidth() == VT.getScalarSizeInBits()) &&
3571  "Splat APInt should be element width");
3572  } else {
3573  N0IsConst = isa<ConstantSDNode>(N0);
3574  if (N0IsConst) {
3575  ConstValue0 = cast<ConstantSDNode>(N0)->getAPIntValue();
3576  N0IsOpaqueConst = cast<ConstantSDNode>(N0)->isOpaque();
3577  }
3578  N1IsConst = isa<ConstantSDNode>(N1);
3579  if (N1IsConst) {
3580  ConstValue1 = cast<ConstantSDNode>(N1)->getAPIntValue();
3581  N1IsOpaqueConst = cast<ConstantSDNode>(N1)->isOpaque();
3582  }
3583  }
3584 
3585  // fold (mul c1, c2) -> c1*c2
3586  if (N0IsConst && N1IsConst && !N0IsOpaqueConst && !N1IsOpaqueConst)
3587  return DAG.FoldConstantArithmetic(ISD::MUL, SDLoc(N), VT,
3588  N0.getNode(), N1.getNode());
3589 
3590  // canonicalize constant to RHS (vector doesn't have to splat)
3593  return DAG.getNode(ISD::MUL, SDLoc(N), VT, N1, N0);
3594  // fold (mul x, 0) -> 0
3595  if (N1IsConst && ConstValue1.isNullValue())
3596  return N1;
3597  // fold (mul x, 1) -> x
3598  if (N1IsConst && ConstValue1.isOneValue())
3599  return N0;
3600 
3601  if (SDValue NewSel = foldBinOpIntoSelect(N))
3602  return NewSel;
3603 
3604  // fold (mul x, -1) -> 0-x
3605  if (N1IsConst && ConstValue1.isAllOnesValue()) {
3606  SDLoc DL(N);
3607  return DAG.getNode(ISD::SUB, DL, VT,
3608  DAG.getConstant(0, DL, VT), N0);
3609  }
3610  // fold (mul x, (1 << c)) -> x << c
3611  if (isConstantOrConstantVector(N1, /*NoOpaques*/ true) &&
3612  DAG.isKnownToBeAPowerOfTwo(N1) &&
3613  (!VT.isVector() || Level <= AfterLegalizeVectorOps)) {
3614  SDLoc DL(N);
3615  SDValue LogBase2 = BuildLogBase2(N1, DL);
3616  EVT ShiftVT = getShiftAmountTy(N0.getValueType());
3617  SDValue Trunc = DAG.getZExtOrTrunc(LogBase2, DL, ShiftVT);
3618  return DAG.getNode(ISD::SHL, DL, VT, N0, Trunc);
3619  }
3620  // fold (mul x, -(1 << c)) -> -(x << c) or (-x) << c
3621  if (N1IsConst && !N1IsOpaqueConst && (-ConstValue1).isPowerOf2()) {
3622  unsigned Log2Val = (-ConstValue1).logBase2();
3623  SDLoc DL(N);
3624  // FIXME: If the input is something that is easily negated (e.g. a
3625  // single-use add), we should put the negate there.
3626  return DAG.getNode(ISD::SUB, DL, VT,
3627  DAG.getConstant(0, DL, VT),
3628  DAG.getNode(ISD::SHL, DL, VT, N0,
3629  DAG.getConstant(Log2Val, DL,
3630  getShiftAmountTy(N0.getValueType()))));
3631  }
3632 
3633  // Try to transform multiply-by-(power-of-2 +/- 1) into shift and add/sub.
3634  // mul x, (2^N + 1) --> add (shl x, N), x
3635  // mul x, (2^N - 1) --> sub (shl x, N), x
3636  // Examples: x * 33 --> (x << 5) + x
3637  // x * 15 --> (x << 4) - x
3638  // x * -33 --> -((x << 5) + x)
3639  // x * -15 --> -((x << 4) - x) ; this reduces --> x - (x << 4)
3640  if (N1IsConst && TLI.decomposeMulByConstant(*DAG.getContext(), VT, N1)) {
3641  // TODO: We could handle more general decomposition of any constant by
3642  // having the target set a limit on number of ops and making a
3643  // callback to determine that sequence (similar to sqrt expansion).
3644  unsigned MathOp = ISD::DELETED_NODE;
3645  APInt MulC = ConstValue1.abs();
3646  if ((MulC - 1).isPowerOf2())
3647  MathOp = ISD::ADD;
3648  else if ((MulC + 1).isPowerOf2())
3649  MathOp = ISD::SUB;
3650 
3651  if (MathOp != ISD::DELETED_NODE) {
3652  unsigned ShAmt =
3653  MathOp == ISD::ADD ? (MulC - 1).logBase2() : (MulC + 1).logBase2();
3654  assert(ShAmt < VT.getScalarSizeInBits() &&
3655  "multiply-by-constant generated out of bounds shift");
3656  SDLoc DL(N);
3657  SDValue Shl =
3658  DAG.getNode(ISD::SHL, DL, VT, N0, DAG.getConstant(ShAmt, DL, VT));
3659  SDValue R = DAG.getNode(MathOp, DL, VT, Shl, N0);
3660  if (ConstValue1.isNegative())
3661  R = DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), R);
3662  return R;
3663  }
3664  }
3665 
3666  // (mul (shl X, c1), c2) -> (mul X, c2 << c1)
3667  if (N0.getOpcode() == ISD::SHL &&
3668  isConstantOrConstantVector(N1, /* NoOpaques */ true) &&
3669  isConstantOrConstantVector(N0.getOperand(1), /* NoOpaques */ true)) {
3670  SDValue C3 = DAG.getNode(ISD::SHL, SDLoc(N), VT, N1, N0.getOperand(1));
3672  return DAG.getNode(ISD::MUL, SDLoc(N), VT, N0.getOperand(0), C3);
3673  }
3674 
3675  // Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one
3676  // use.
3677  {
3678  SDValue Sh(nullptr, 0), Y(nullptr, 0);
3679 
3680  // Check for both (mul (shl X, C), Y) and (mul Y, (shl X, C)).
3681  if (N0.getOpcode() == ISD::SHL &&
3683  N0.getNode()->hasOneUse()) {
3684  Sh = N0; Y = N1;
3685  } else if (N1.getOpcode() == ISD::SHL &&
3687  N1.getNode()->hasOneUse()) {
3688  Sh = N1; Y = N0;
3689  }
3690 
3691  if (Sh.getNode()) {
3692  SDValue Mul = DAG.getNode(ISD::MUL, SDLoc(N), VT, Sh.getOperand(0), Y);
3693  return DAG.getNode(ISD::SHL, SDLoc(N), VT, Mul, Sh.getOperand(1));
3694  }
3695  }
3696 
3697  // fold (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2)
3699  N0.getOpcode() == ISD::ADD &&
3701  isMulAddWithConstProfitable(N, N0, N1))
3702  return DAG.getNode(ISD::ADD, SDLoc(N), VT,
3703  DAG.getNode(ISD::MUL, SDLoc(N0), VT,
3704  N0.getOperand(0), N1),
3705  DAG.getNode(ISD::MUL, SDLoc(N1), VT,
3706  N0.getOperand(1), N1));
3707 
3708  // reassociate mul
3709  if (SDValue RMUL = reassociateOps(ISD::MUL, SDLoc(N), N0, N1, N->getFlags()))
3710  return RMUL;
3711 
3712  return SDValue();
3713 }
3714 
3715 /// Return true if divmod libcall is available.
3716 static bool isDivRemLibcallAvailable(SDNode *Node, bool isSigned,
3717  const TargetLowering &TLI) {
3718  RTLIB::Libcall LC;
3719  EVT NodeType = Node->getValueType(0);
3720  if (!NodeType.isSimple())
3721  return false;
3722  switch (NodeType.getSimpleVT().SimpleTy) {
3723  default: return false; // No libcall for vector types.
3724  case MVT::i8: LC= isSigned ? RTLIB::SDIVREM_I8 : RTLIB::UDIVREM_I8; break;
3725  case MVT::i16: LC= isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16; break;
3726  case MVT::i32: LC= isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32; break;
3727  case MVT::i64: LC= isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64; break;
3728  case MVT::i128: LC= isSigned ? RTLIB::SDIVREM_I128:RTLIB::UDIVREM_I128; break;
3729  }
3730 
3731  return TLI.getLibcallName(LC) != nullptr;
3732 }
3733 
3734 /// Issue divrem if both quotient and remainder are needed.
3735 SDValue DAGCombiner::useDivRem(SDNode *Node) {
3736  if (Node->use_empty())
3737  return SDValue(); // This is a dead node, leave it alone.
3738 
3739  unsigned Opcode = Node->getOpcode();
3740  bool isSigned = (Opcode == ISD::SDIV) || (Opcode == ISD::SREM);
3741  unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
3742 
3743  // DivMod lib calls can still work on non-legal types if using lib-calls.
3744  EVT VT = Node->getValueType(0);
3745  if (VT.isVector() || !VT.isInteger())
3746  return SDValue();
3747 
3748  if (!TLI.isTypeLegal(VT) && !TLI.isOperationCustom(DivRemOpc, VT))
3749  return SDValue();
3750 
3751  // If DIVREM is going to get expanded into a libcall,
3752  // but there is no libcall available, then don't combine.
3753  if (!TLI.isOperationLegalOrCustom(DivRemOpc, VT) &&
3754  !isDivRemLibcallAvailable(Node, isSigned, TLI))
3755  return SDValue();
3756 
3757  // If div is legal, it's better to do the normal expansion
3758  unsigned OtherOpcode = 0;
3759  if ((Opcode == ISD::SDIV) || (Opcode == ISD::UDIV)) {
3760  OtherOpcode = isSigned ? ISD::SREM : ISD::UREM;
3761  if (TLI.isOperationLegalOrCustom(Opcode, VT))
3762  return SDValue();
3763  } else {
3764  OtherOpcode = isSigned ? ISD::SDIV : ISD::UDIV;
3765  if (TLI.isOperationLegalOrCustom(OtherOpcode, VT))
3766  return SDValue();
3767  }
3768 
3769  SDValue Op0 = Node->getOperand(0);
3770  SDValue Op1 = Node->getOperand(1);
3771  SDValue combined;
3772  for (SDNode::use_iterator UI = Op0.getNode()->use_begin(),
3773  UE = Op0.getNode()->use_end(); UI != UE; ++UI) {
3774  SDNode *User = *UI;
3775  if (User == Node || User->getOpcode() == ISD::DELETED_NODE ||
3776  User->use_empty())
3777  continue;
3778  // Convert the other matching node(s), too;
3779  // otherwise, the DIVREM may get target-legalized into something
3780  // target-specific that we won't be able to recognize.
3781  unsigned UserOpc = User->getOpcode();
3782  if ((UserOpc == Opcode || UserOpc == OtherOpcode || UserOpc == DivRemOpc) &&
3783  User->getOperand(0) == Op0 &&
3784  User->getOperand(1) == Op1) {
3785  if (!combined) {
3786  if (UserOpc == OtherOpcode) {
3787  SDVTList VTs = DAG.getVTList(VT, VT);
3788  combined = DAG.getNode(DivRemOpc, SDLoc(Node), VTs, Op0, Op1);
3789  } else if (UserOpc == DivRemOpc) {
3790  combined = SDValue(User, 0);
3791  } else {
3792  assert(UserOpc == Opcode);
3793  continue;
3794  }
3795  }
3796  if (UserOpc == ISD::SDIV || UserOpc == ISD::UDIV)
3797  CombineTo(User, combined);
3798  else if (UserOpc == ISD::SREM || UserOpc == ISD::UREM)
3799  CombineTo(User, combined.getValue(1));
3800  }
3801  }
3802  return combined;
3803 }
3804 
3806  SDValue N0 = N->getOperand(0);
3807  SDValue N1 = N->getOperand(1);
3808  EVT VT = N->getValueType(0);
3809  SDLoc DL(N);
3810 
3811  unsigned Opc = N->getOpcode();
3812  bool IsDiv = (ISD::SDIV == Opc) || (ISD::UDIV == Opc);
3814 
3815  // X / undef -> undef
3816  // X % undef -> undef
3817  // X / 0 -> undef
3818  // X % 0 -> undef
3819  // NOTE: This includes vectors where any divisor element is zero/undef.
3820  if (DAG.isUndef(Opc, {N0, N1}))
3821  return DAG.getUNDEF(VT);
3822 
3823  // undef / X -> 0
3824  // undef % X -> 0
3825  if (N0.isUndef())
3826  return DAG.getConstant(0, DL, VT);
3827 
3828  // 0 / X -> 0
3829  // 0 % X -> 0
3831  if (N0C && N0C->isNullValue())
3832  return N0;
3833 
3834  // X / X -> 1
3835  // X % X -> 0
3836  if (N0 == N1)
3837  return DAG.getConstant(IsDiv ? 1 : 0, DL, VT);
3838 
3839  // X / 1 -> X
3840  // X % 1 -> 0
3841  // If this is a boolean op (single-bit element type), we can't have
3842  // division-by-zero or remainder-by-zero, so assume the divisor is 1.
3843  // TODO: Similarly, if we're zero-extending a boolean divisor, then assume
3844  // it's a 1.
3845  if ((N1C && N1C->isOne()) || (VT.getScalarType() == MVT::i1))
3846  return IsDiv ? N0 : DAG.getConstant(0, DL, VT);
3847 
3848  return SDValue();
3849 }
3850 
3851 SDValue DAGCombiner::visitSDIV(SDNode *N) {
3852  SDValue N0 = N->getOperand(0);
3853  SDValue N1 = N->getOperand(1);
3854  EVT VT = N->getValueType(0);
3855  EVT CCVT = getSetCCResultType(VT);
3856 
3857  // fold vector ops
3858  if (VT.isVector())
3859  if (SDValue FoldedVOp = SimplifyVBinOp(N))
3860  return FoldedVOp;
3861 
3862  SDLoc DL(N);
3863 
3864  // fold (sdiv c1, c2) -> c1/c2
3867  if (N0C && N1C && !N0C->isOpaque() && !N1C->isOpaque())
3868  return DAG.FoldConstantArithmetic(ISD::SDIV, DL, VT, N0C, N1C);
3869  // fold (sdiv X, -1) -> 0-X
3870  if (N1C && N1C->isAllOnesValue())
3871  return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), N0);
3872  // fold (sdiv X, MIN_SIGNED) -> select(X == MIN_SIGNED, 1, 0)
3873  if (N1C && N1C->getAPIntValue().isMinSignedValue())
3874  return DAG.getSelect(DL, VT, DAG.getSetCC(DL, CCVT, N0, N1, ISD::SETEQ),
3875  DAG.getConstant(1, DL, VT),
3876  DAG.getConstant(0, DL, VT));
3877 
3878  if (SDValue V = simplifyDivRem(N, DAG))
3879  return V;
3880 
3881  if (SDValue NewSel = foldBinOpIntoSelect(N))
3882  return NewSel;
3883 
3884  // If we know the sign bits of both operands are zero, strength reduce to a
3885  // udiv instead. Handles (X&15) /s 4 -> X&15 >> 2
3886  if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
3887  return DAG.getNode(ISD::UDIV, DL, N1.getValueType(), N0, N1);
3888 
3889  if (SDValue V = visitSDIVLike(N0, N1, N)) {
3890  // If the corresponding remainder node exists, update its users with
3891  // (Dividend - (Quotient * Divisor).
3892  if (SDNode *RemNode = DAG.getNodeIfExists(ISD::SREM, N->getVTList(),
3893  { N0, N1 })) {
3894  SDValue Mul = DAG.getNode(ISD::MUL, DL, VT, V, N1);
3895  SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, Mul);
3896  AddToWorklist(Mul.getNode());
3897  AddToWorklist(Sub.getNode());
3898  CombineTo(RemNode, Sub);
3899  }
3900  return V;
3901  }
3902 
3903  // sdiv, srem -> sdivrem
3904  // If the divisor is constant, then return DIVREM only if isIntDivCheap() is
3905  // true. Otherwise, we break the simplification logic in visitREM().
3907  if (!N1C || TLI.isIntDivCheap(N->getValueType(0), Attr))
3908  if (SDValue DivRem = useDivRem(N))
3909  return DivRem;
3910 
3911  return SDValue();
3912 }
3913 
3914 SDValue DAGCombiner::visitSDIVLike(SDValue N0, SDValue N1, SDNode *N) {
3915  SDLoc DL(N);
3916  EVT VT = N->getValueType(0);
3917  EVT CCVT = getSetCCResultType(VT);
3918  unsigned BitWidth = VT.getScalarSizeInBits();
3919 
3920  // Helper for determining whether a value is a power-2 constant scalar or a
3921  // vector of such elements.
3922  auto IsPowerOfTwo = [](ConstantSDNode *C) {
3923  if (C->isNullValue() || C->isOpaque())
3924  return false;
3925  if (C->getAPIntValue().isPowerOf2())
3926  return true;
3927  if ((-C->getAPIntValue()).isPowerOf2())
3928  return true;
3929  return false;
3930  };
3931 
3932  // fold (sdiv X, pow2) -> simple ops after legalize
3933  // FIXME: We check for the exact bit here because the generic lowering gives
3934  // better results in that case. The target-specific lowering should learn how
3935  // to handle exact sdivs efficiently.
3936  if (!N->getFlags().hasExact() && ISD::matchUnaryPredicate(N1, IsPowerOfTwo)) {
3937  // Target-specific implementation of sdiv x, pow2.
3938  if (SDValue Res = BuildSDIVPow2(N))
3939  return Res;
3940 
3941  // Create constants that are functions of the shift amount value.
3942  EVT ShiftAmtTy = getShiftAmountTy(N0.getValueType());
3943  SDValue Bits = DAG.getConstant(BitWidth, DL, ShiftAmtTy);
3944  SDValue C1 = DAG.getNode(ISD::CTTZ, DL, VT, N1);
3945  C1 = DAG.getZExtOrTrunc(C1, DL, ShiftAmtTy);
3946  SDValue Inexact = DAG.getNode(ISD::SUB, DL, ShiftAmtTy, Bits, C1);
3947  if (!isConstantOrConstantVector(Inexact))
3948  return SDValue();
3949 
3950  // Splat the sign bit into the register
3951  SDValue Sign = DAG.getNode(ISD::SRA, DL, VT, N0,
3952  DAG.getConstant(BitWidth - 1, DL, ShiftAmtTy));
3953  AddToWorklist(Sign.getNode());
3954 
3955  // Add (N0 < 0) ? abs2 - 1 : 0;
3956  SDValue Srl = DAG.getNode(ISD::SRL, DL, VT, Sign, Inexact);
3957  AddToWorklist(Srl.getNode());
3958  SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N0, Srl);
3959  AddToWorklist(Add.getNode());
3960  SDValue Sra = DAG.getNode(ISD::SRA, DL, VT, Add, C1);
3961  AddToWorklist(Sra.getNode());
3962 
3963  // Special case: (sdiv X, 1) -> X
3964  // Special Case: (sdiv X, -1) -> 0-X
3965  SDValue One = DAG.getConstant(1, DL, VT);
3966  SDValue AllOnes = DAG.getAllOnesConstant(DL, VT);
3967  SDValue IsOne = DAG.getSetCC(DL, CCVT, N1, One, ISD::SETEQ);
3968  SDValue IsAllOnes = DAG.getSetCC(DL, CCVT, N1, AllOnes, ISD::SETEQ);
3969  SDValue IsOneOrAllOnes = DAG.getNode(ISD::OR, DL, CCVT, IsOne, IsAllOnes);
3970  Sra = DAG.getSelect(DL, VT, IsOneOrAllOnes, N0, Sra);
3971 
3972  // If dividing by a positive value, we're done. Otherwise, the result must
3973  // be negated.
3974  SDValue Zero = DAG.getConstant(0, DL, VT);
3975  SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, Zero, Sra);
3976 
3977  // FIXME: Use SELECT_CC once we improve SELECT_CC constant-folding.
3978  SDValue IsNeg = DAG.getSetCC(DL, CCVT, N1, Zero, ISD::SETLT);
3979  SDValue Res = DAG.getSelect(DL, VT, IsNeg, Sub, Sra);
3980  return Res;
3981  }
3982 
3983  // If integer divide is expensive and we satisfy the requirements, emit an
3984  // alternate sequence. Targets may check function attributes for size/speed
3985  // trade-offs.
3987  if (isConstantOrConstantVector(N1) &&
3988  !TLI.isIntDivCheap(N->getValueType(0), Attr))
3989  if (SDValue Op = BuildSDIV(N))
3990  return Op;
3991 
3992  return SDValue();
3993 }
3994 
3995 SDValue DAGCombiner::visitUDIV(SDNode *N) {
3996  SDValue N0 = N->getOperand(0);
3997  SDValue N1 = N->getOperand(1);
3998  EVT VT = N->getValueType(0);
3999  EVT CCVT = getSetCCResultType(VT);
4000 
4001  // fold vector ops
4002  if (VT.isVector())
4003  if (SDValue FoldedVOp = SimplifyVBinOp(N))
4004  return FoldedVOp;
4005 
4006  SDLoc DL(N);
4007 
4008  // fold (udiv c1, c2) -> c1/c2
4011  if (N0C && N1C)
4012  if (SDValue Folded = DAG.FoldConstantArithmetic(ISD::UDIV, DL, VT,
4013  N0C, N1C))
4014  return Folded;
4015  // fold (udiv X, -1) -> select(X == -1, 1, 0)
4016  if (N1C && N1C->getAPIntValue().isAllOnesValue())
4017  return DAG.getSelect(DL, VT, DAG.getSetCC(DL, CCVT, N0, N1, ISD::SETEQ),
4018  DAG.getConstant(1, DL, VT),
4019  DAG.getConstant(0, DL, VT));
4020 
4021  if (SDValue V = simplifyDivRem(N, DAG))
4022  return V;
4023 
4024  if (SDValue NewSel = foldBinOpIntoSelect(N))
4025  return NewSel;
4026 
4027  if (SDValue V = visitUDIVLike(N0, N1, N)) {
4028  // If the corresponding remainder node exists, update its users with
4029  // (Dividend - (Quotient * Divisor).
4030  if (SDNode *RemNode = DAG.getNodeIfExists(ISD::UREM, N->getVTList(),
4031  { N0, N1 })) {
4032  SDValue Mul = DAG.getNode(ISD::MUL, DL, VT, V, N1);
4033  SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, Mul);
4034  AddToWorklist(Mul.getNode());
4035  AddToWorklist(Sub.getNode());
4036  CombineTo(RemNode, Sub);
4037  }
4038  return V;
4039  }
4040 
4041  // sdiv, srem -> sdivrem
4042  // If the divisor is constant, then return DIVREM only if isIntDivCheap() is
4043  // true. Otherwise, we break the simplification logic in visitREM().
4045  if (!N1C || TLI.isIntDivCheap(N->getValueType(0), Attr))
4046  if (SDValue DivRem = useDivRem(N))
4047  return DivRem;
4048 
4049  return SDValue();
4050 }
4051 
4052 SDValue DAGCombiner::visitUDIVLike(SDValue N0, SDValue N1, SDNode *N) {
4053  SDLoc DL(N);
4054  EVT VT = N->getValueType(0);
4055 
4056  // fold (udiv x, (1 << c)) -> x >>u c
4057  if (isConstantOrConstantVector(N1, /*NoOpaques*/ true) &&
4058  DAG.isKnownToBeAPowerOfTwo(N1)) {
4059  SDValue LogBase2 = BuildLogBase2(N1, DL);
4060  AddToWorklist(LogBase2.getNode());
4061 
4062  EVT ShiftVT = getShiftAmountTy(N0.getValueType());
4063  SDValue Trunc = DAG.getZExtOrTrunc(LogBase2, DL, ShiftVT);
4064  AddToWorklist(Trunc.getNode());
4065  return DAG.getNode(ISD::SRL, DL, VT, N0, Trunc);
4066  }
4067 
4068  // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2
4069  if (N1.getOpcode() == ISD::SHL) {
4070  SDValue N10 = N1.getOperand(0);
4071  if (isConstantOrConstantVector(N10, /*NoOpaques*/ true) &&
4072  DAG.isKnownToBeAPowerOfTwo(N10)) {
4073  SDValue LogBase2 = BuildLogBase2(N10, DL);
4074  AddToWorklist(LogBase2.getNode());
4075 
4076  EVT ADDVT = N1.getOperand(1).getValueType();
4077  SDValue Trunc = DAG.getZExtOrTrunc(LogBase2, DL, ADDVT);
4078  AddToWorklist(Trunc.getNode());
4079  SDValue Add = DAG.getNode(ISD::ADD, DL, ADDVT, N1.getOperand(1), Trunc);
4080  AddToWorklist(Add.getNode());
4081  return DAG.getNode(ISD::SRL, DL, VT, N0, Add);
4082  }
4083  }
4084 
4085  // fold (udiv x, c) -> alternate
4087  if (isConstantOrConstantVector(N1) &&
4088  !TLI.isIntDivCheap(N->getValueType(0), Attr))
4089  if (SDValue Op = BuildUDIV(N))
4090  return Op;
4091 
4092  return SDValue();
4093 }
4094 
4095 // handles ISD::SREM and ISD::UREM
4096 SDValue DAGCombiner::visitREM(SDNode *N) {
4097  unsigned Opcode = N->getOpcode();
4098  SDValue N0 = N->getOperand(0);
4099  SDValue N1 = N->getOperand(1);
4100  EVT VT = N->getValueType(0);
4101  EVT CCVT = getSetCCResultType(VT);
4102 
4103  bool isSigned = (Opcode == ISD::SREM);
4104  SDLoc DL(N);
4105 
4106  // fold (rem c1, c2) -> c1%c2
4109  if (N0C && N1C)
4110  if (SDValue Folded = DAG.FoldConstantArithmetic(Opcode, DL, VT, N0C, N1C))
4111  return Folded;
4112  // fold (urem X, -1) -> select(X == -1, 0, x)
4113  if (!isSigned && N1C && N1C->getAPIntValue().isAllOnesValue())
4114  return DAG.getSelect(DL, VT, DAG.getSetCC(DL, CCVT, N0, N1, ISD::SETEQ),
4115  DAG.getConstant(0, DL, VT), N0);
4116 
4117  if (SDValue V = simplifyDivRem(N, DAG))
4118  return V;
4119 
4120  if (SDValue NewSel = foldBinOpIntoSelect(N))
4121  return NewSel;
4122 
4123  if (isSigned) {
4124  // If we know the sign bits of both operands are zero, strength reduce to a
4125  // urem instead. Handles (X & 0x0FFFFFFF) %s 16 -> X&15
4126  if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
4127  return DAG.getNode(ISD::UREM, DL, VT, N0, N1);
4128  } else {
4129  SDValue NegOne = DAG.getAllOnesConstant(DL, VT);
4130  if (DAG.isKnownToBeAPowerOfTwo(N1)) {
4131  // fold (urem x, pow2) -> (and x, pow2-1)
4132  SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N1, NegOne);
4133  AddToWorklist(Add.getNode());
4134  return DAG.getNode(ISD::AND, DL, VT, N0, Add);
4135  }
4136  if (N1.getOpcode() == ISD::SHL &&
4137  DAG.isKnownToBeAPowerOfTwo(N1.getOperand(0))) {
4138  // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1))
4139  SDValue Add = DAG.getNode(ISD::ADD, DL, VT, N1, NegOne);
4140  AddToWorklist(Add.getNode());
4141  return DAG.getNode(ISD::AND, DL, VT, N0, Add);
4142  }
4143  }
4144 
4146 
4147  // If X/C can be simplified by the division-by-constant logic, lower
4148  // X%C to the equivalent of X-X/C*C.
4149  // Reuse the SDIVLike/UDIVLike combines - to avoid mangling nodes, the
4150  // speculative DIV must not cause a DIVREM conversion. We guard against this
4151  // by skipping the simplification if isIntDivCheap(). When div is not cheap,
4152  // combine will not return a DIVREM. Regardless, checking cheapness here
4153  // makes sense since the simplification results in fatter code.
4154  if (DAG.isKnownNeverZero(N1) && !TLI.isIntDivCheap(VT, Attr)) {
4155  SDValue OptimizedDiv =
4156  isSigned ? visitSDIVLike(N0, N1, N) : visitUDIVLike(N0, N1, N);
4157  if (OptimizedDiv.getNode()) {
4158  // If the equivalent Div node also exists, update its users.
4159  unsigned DivOpcode = isSigned ? ISD::SDIV : ISD::UDIV;
4160  if (SDNode *DivNode = DAG.getNodeIfExists(DivOpcode, N->getVTList(),
4161  { N0, N1 }))
4162  CombineTo(DivNode, OptimizedDiv);
4163  SDValue Mul = DAG.getNode(ISD::MUL, DL, VT, OptimizedDiv, N1);
4164  SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, Mul);
4165  AddToWorklist(OptimizedDiv.getNode());
4166  AddToWorklist(Mul.getNode());
4167  return Sub;
4168  }
4169  }
4170 
4171  // sdiv, srem -> sdivrem
4172  if (SDValue DivRem = useDivRem(N))
4173  return DivRem.getValue(1);
4174 
4175  return SDValue();
4176 }
4177 
4178 SDValue DAGCombiner::visitMULHS(SDNode *N) {
4179  SDValue N0 = N->getOperand(0);
4180  SDValue N1 = N->getOperand(1);
4181  EVT VT = N->getValueType(0);
4182  SDLoc DL(N);
4183 
4184  if (VT.isVector()) {
4185  // fold (mulhs x, 0) -> 0
4186  // do not return N0/N1, because undef node may exist.
4187  if (ISD::isBuildVectorAllZeros(N0.getNode()) ||
4189  return DAG.getConstant(0, DL, VT);
4190  }
4191 
4192  // fold (mulhs x, 0) -> 0
4193  if (isNullConstant(N1))
4194  return N1;
4195  // fold (mulhs x, 1) -> (sra x, size(x)-1)
4196  if (isOneConstant(N1))
4197  return DAG.getNode(ISD::SRA, DL, N0.getValueType(), N0,
4198  DAG.getConstant(N0.getScalarValueSizeInBits() - 1, DL,
4199  getShiftAmountTy(N0.getValueType())));
4200 
4201  // fold (mulhs x, undef) -> 0
4202  if (N0.isUndef() || N1.isUndef())
4203  return DAG.getConstant(0, DL, VT);
4204 
4205  // If the type twice as wide is legal, transform the mulhs to a wider multiply
4206  // plus a shift.
4207  if (VT.isSimple() && !VT.isVector()) {
4208  MVT Simple = VT.getSimpleVT();
4209  unsigned SimpleSize = Simple.getSizeInBits();
4210  EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
4211  if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
4212  N0 = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N0);
4213  N1 = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N1);
4214  N1 = DAG.getNode(ISD::MUL, DL, NewVT, N0, N1);
4215  N1 = DAG.getNode(ISD::SRL, DL, NewVT, N1,
4216  DAG.getConstant(SimpleSize, DL,
4217  getShiftAmountTy(N1.getValueType())));
4218  return DAG.getNode(ISD::TRUNCATE, DL, VT, N1);
4219  }
4220  }
4221 
4222  return SDValue();
4223 }
4224 
4225 SDValue DAGCombiner::visitMULHU(SDNode *N) {
4226  SDValue N0 = N->getOperand(0);
4227  SDValue N1 = N->getOperand(1);
4228  EVT VT = N->getValueType(0);
4229  SDLoc DL(N);
4230 
4231  if (VT.isVector()) {
4232  // fold (mulhu x, 0) -> 0
4233  // do not return N0/N1, because undef node may exist.
4234  if (ISD::isBuildVectorAllZeros(N0.getNode()) ||
4236  return DAG.getConstant(0, DL, VT);
4237  }
4238 
4239  // fold (mulhu x, 0) -> 0
4240  if (isNullConstant(N1))
4241  return N1;
4242  // fold (mulhu x, 1) -> 0
4243  if (isOneConstant(N1))
4244  return DAG.getConstant(0, DL, N0.getValueType());
4245  // fold (mulhu x, undef) -> 0
4246  if (N0.isUndef() || N1.isUndef())
4247  return DAG.getConstant(0, DL, VT);
4248 
4249  // fold (mulhu x, (1 << c)) -> x >> (bitwidth - c)
4250  if (isConstantOrConstantVector(N1, /*NoOpaques*/ true) &&
4251  DAG.isKnownToBeAPowerOfTwo(N1) && hasOperation(ISD::SRL, VT)) {
4252  unsigned NumEltBits = VT.getScalarSizeInBits();
4253  SDValue LogBase2 = BuildLogBase2(N1, DL);
4254  SDValue SRLAmt = DAG.getNode(
4255  ISD::SUB, DL, VT, DAG.getConstant(NumEltBits, DL, VT), LogBase2);
4256  EVT ShiftVT = getShiftAmountTy(N0.getValueType());
4257  SDValue Trunc = DAG.getZExtOrTrunc(SRLAmt, DL, ShiftVT);
4258  return DAG.getNode(ISD::SRL, DL, VT, N0, Trunc);
4259  }
4260 
4261  // If the type twice as wide is legal, transform the mulhu to a wider multiply
4262  // plus a shift.
4263  if (VT.isSimple() && !VT.isVector()) {
4264  MVT Simple = VT.getSimpleVT();
4265  unsigned SimpleSize = Simple.getSizeInBits();
4266  EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
4267  if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
4268  N0 = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N0);
4269  N1 = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N1);
4270  N1 = DAG.getNode(ISD::MUL, DL, NewVT, N0, N1);
4271  N1 = DAG.getNode(ISD::SRL, DL, NewVT, N1,
4272  DAG.getConstant(SimpleSize, DL,
4273  getShiftAmountTy(N1.getValueType())));
4274  return DAG.getNode(ISD::TRUNCATE, DL, VT, N1);
4275  }
4276  }
4277 
4278  return SDValue();
4279 }
4280 
4281 /// Perform optimizations common to nodes that compute two values. LoOp and HiOp
4282 /// give the opcodes for the two computations that are being performed. Return
4283 /// true if a simplification was made.
4284 SDValue DAGCombiner::SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp,
4285  unsigned HiOp) {
4286  // If the high half is not needed, just compute the low half.
4287  bool HiExists = N->hasAnyUseOfValue(1);
4288  if (!HiExists && (!LegalOperations ||
4289  TLI.isOperationLegalOrCustom(LoOp, N->getValueType(0)))) {
4290  SDValue Res = DAG.getNode(LoOp, SDLoc(N), N->getValueType(0), N->ops());
4291  return CombineTo(N, Res, Res);
4292  }
4293 
4294  // If the low half is not needed, just compute the high half.
4295  bool LoExists = N->hasAnyUseOfValue(0);
4296  if (!LoExists && (!LegalOperations ||
4297  TLI.isOperationLegalOrCustom(HiOp, N->getValueType(1)))) {
4298  SDValue Res = DAG.getNode(HiOp, SDLoc(N), N->getValueType(1), N->ops());
4299  return CombineTo(N, Res, Res);
4300  }
4301 
4302  // If both halves are used, return as it is.
4303  if (LoExists && HiExists)
4304  return SDValue();
4305 
4306  // If the two computed results can be simplified separately, separate them.
4307  if (LoExists) {
4308  SDValue Lo = DAG.getNode(LoOp, SDLoc(N), N->getValueType(0), N->ops());
4309  AddToWorklist(Lo.getNode());
4310  SDValue LoOpt = combine(Lo.getNode());
4311  if (LoOpt.getNode() && LoOpt.getNode() != Lo.getNode() &&
4312  (!LegalOperations ||
4313  TLI.isOperationLegalOrCustom(LoOpt.getOpcode(), LoOpt.getValueType())))
4314  return CombineTo(N, LoOpt, LoOpt);
4315  }
4316 
4317  if (HiExists) {
4318  SDValue Hi = DAG.getNode(HiOp, SDLoc(N), N->getValueType(1), N->ops());
4319  AddToWorklist(Hi.getNode());
4320  SDValue HiOpt = combine(Hi.getNode());
4321  if (HiOpt.getNode() && HiOpt != Hi &&
4322  (!LegalOperations ||
4323  TLI.isOperationLegalOrCustom(HiOpt.getOpcode(), HiOpt.getValueType())))
4324  return CombineTo(N, HiOpt, HiOpt);
4325  }
4326 
4327  return SDValue();
4328 }
4329 
4330 SDValue DAGCombiner::visitSMUL_LOHI(SDNode *N) {
4331  if (SDValue Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHS))
4332  return Res;
4333 
4334  EVT VT = N->getValueType(0);
4335  SDLoc DL(N);
4336 
4337  // If the type is twice as wide is legal, transform the mulhu to a wider
4338  // multiply plus a shift.
4339  if (VT.isSimple() && !VT.isVector()) {
4340  MVT Simple = VT.getSimpleVT();
4341  unsigned SimpleSize = Simple.getSizeInBits();
4342  EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
4343  if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
4344  SDValue Lo = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N->getOperand(0));
4345  SDValue Hi = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N->getOperand(1));
4346  Lo = DAG.getNode(ISD::MUL, DL, NewVT, Lo, Hi);
4347  // Compute the high part as N1.
4348  Hi = DAG.getNode(ISD::SRL, DL, NewVT, Lo,
4349  DAG.getConstant(SimpleSize, DL,
4350  getShiftAmountTy(Lo.getValueType())));
4351  Hi = DAG.getNode(ISD::TRUNCATE, DL, VT, Hi);
4352  // Compute the low part as N0.
4353  Lo = DAG.getNode(ISD::TRUNCATE, DL, VT, Lo);
4354  return CombineTo(N, Lo, Hi);
4355  }
4356  }
4357 
4358  return SDValue();
4359 }
4360 
4361 SDValue DAGCombiner::visitUMUL_LOHI(SDNode *N) {
4362  if (SDValue Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHU))
4363  return Res;
4364 
4365  EVT VT = N->getValueType(0);
4366  SDLoc DL(N);
4367 
4368  // (umul_lohi N0, 0) -> (0, 0)
4369  if (isNullConstant(N->getOperand(1))) {
4370  SDValue Zero = DAG.getConstant(0, DL, VT);
4371  return CombineTo(N, Zero, Zero);
4372  }
4373 
4374  // (umul_lohi N0, 1) -> (N0, 0)
4375  if (isOneConstant(N->getOperand(1))) {
4376  SDValue Zero = DAG.getConstant(0, DL, VT);
4377  return CombineTo(N, N->getOperand(0), Zero);
4378  }
4379 
4380  // If the type is twice as wide is legal, transform the mulhu to a wider
4381  // multiply plus a shift.
4382  if (VT.isSimple() && !VT.isVector()) {
4383  MVT Simple = VT.getSimpleVT();
4384  unsigned SimpleSize = Simple.getSizeInBits();
4385  EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
4386  if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
4387  SDValue Lo = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N->getOperand(0));
4388  SDValue Hi = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N->getOperand(1));
4389  Lo = DAG.getNode(ISD::MUL, DL, NewVT, Lo, Hi);
4390  // Compute the high part as N1.
4391  Hi = DAG.getNode(ISD::SRL, DL, NewVT, Lo,
4392  DAG.getConstant(SimpleSize, DL,
4393  getShiftAmountTy(Lo.getValueType())));
4394  Hi = DAG.getNode(ISD::TRUNCATE, DL, VT, Hi);
4395  // Compute the low part as N0.
4396  Lo = DAG.getNode(ISD::TRUNCATE, DL, VT, Lo);
4397  return CombineTo(N, Lo, Hi);
4398  }
4399  }
4400 
4401  return SDValue();
4402 }
4403 
4404 SDValue DAGCombiner::visitMULO(SDNode *N) {
4405  SDValue N0 = N->getOperand(0);
4406  SDValue N1 = N->getOperand(1);
4407  EVT VT = N0.getValueType();
4408  bool IsSigned = (ISD::SMULO == N->getOpcode());
4409 
4410  EVT CarryVT = N->getValueType(1);
4411  SDLoc DL(N);
4412 
4413  // canonicalize constant to RHS.
4416  return DAG.getNode(N->getOpcode(), DL, N->getVTList(), N1, N0);
4417 
4418  // fold (mulo x, 0) -> 0 + no carry out
4419  if (isNullOrNullSplat(N1))
4420  return CombineTo(N, DAG.getConstant(0, DL, VT),
4421  DAG.getConstant(0, DL, CarryVT));
4422 
4423  // (mulo x, 2) -> (addo x, x)
4424  if (ConstantSDNode *C2 = isConstOrConstSplat(N1))
4425  if (C2->getAPIntValue() == 2)
4426  return DAG.getNode(IsSigned ? ISD::SADDO : ISD::UADDO, DL,
4427  N->getVTList(), N0, N0);
4428 
4429  return SDValue();
4430 }
4431 
4432 SDValue DAGCombiner::visitIMINMAX(SDNode *N) {
4433  SDValue N0 = N->getOperand(0);
4434  SDValue N1 = N->getOperand(1);
4435  EVT VT = N0.getValueType();
4436 
4437  // fold vector ops
4438  if (VT.isVector())
4439  if (SDValue FoldedVOp = SimplifyVBinOp(N))
4440  return FoldedVOp;
4441 
4442  // fold operation with constant operands.
4445  if (N0C && N1C)
4446  return DAG.FoldConstantArithmetic(N->getOpcode(), SDLoc(N), VT, N0C, N1C);
4447 
4448  // canonicalize constant to RHS
4451  return DAG.getNode(N->getOpcode(), SDLoc(N), VT, N1, N0);
4452 
4453  // Is sign bits are zero, flip between UMIN/UMAX and SMIN/SMAX.
4454  // Only do this if the current op isn't legal and the flipped is.
4455  unsigned Opcode = N->getOpcode();
4456  const TargetLowering &TLI = DAG.getTargetLoweringInfo();
4457  if (!TLI.isOperationLegal(Opcode, VT) &&
4458  (N0.isUndef() || DAG.SignBitIsZero(N0)) &&
4459  (N1.isUndef() || DAG.SignBitIsZero(N1))) {
4460  unsigned AltOpcode;
4461  switch (Opcode) {
4462  case ISD::SMIN: AltOpcode = ISD::UMIN; break;
4463  case ISD::SMAX: AltOpcode = ISD::UMAX; break;
4464  case ISD::UMIN: AltOpcode = ISD::SMIN; break;
4465  case ISD::UMAX: AltOpcode = ISD::SMAX; break;
4466  default: llvm_unreachable("Unknown MINMAX opcode");
4467  }
4468  if (TLI.isOperationLegal(AltOpcode, VT))
4469  return DAG.getNode(AltOpcode, SDLoc(N), VT, N0, N1);
4470  }
4471 
4472  return SDValue();
4473 }
4474 
4475 /// If this is a bitwise logic instruction and both operands have the same
4476 /// opcode, try to sink the other opcode after the logic instruction.
4477 SDValue DAGCombiner::hoistLogicOpWithSameOpcodeHands(SDNode *N) {
4478  SDValue N0 = N->getOperand(0), N1 = N->getOperand(1);
4479  EVT VT = N0.getValueType();
4480  unsigned LogicOpcode = N->getOpcode();
4481  unsigned HandOpcode = N0.getOpcode();
4482  assert((LogicOpcode == ISD::AND || LogicOpcode == ISD::OR ||
4483  LogicOpcode == ISD::XOR) && "Expected logic opcode");
4484  assert(HandOpcode == N1.getOpcode() && "Bad input!");
4485 
4486  // Bail early if none of these transforms apply.
4487  if (N0.getNumOperands() == 0)
4488  return SDValue();
4489 
4490  // FIXME: We should check number of uses of the operands to not increase
4491  // the instruction count for all transforms.
4492 
4493  // Handle size-changing casts.
4494  SDValue X = N0.getOperand(0);
4495  SDValue Y = N1.getOperand(0);
4496  EVT XVT = X.getValueType();
4497  SDLoc DL(N);
4498  if (HandOpcode == ISD::ANY_EXTEND || HandOpcode == ISD::ZERO_EXTEND ||
4499  HandOpcode == ISD::SIGN_EXTEND) {
4500  // If both operands have other uses, this transform would create extra
4501  // instructions without eliminating anything.
4502  if (!N0.hasOneUse() && !N1.hasOneUse())
4503  return SDValue();
4504  // We need matching integer source types.
4505  if (XVT != Y.getValueType())
4506  return SDValue();
4507  // Don't create an illegal op during or after legalization. Don't ever
4508  // create an unsupported vector op.
4509  if ((VT.isVector() || LegalOperations) &&
4510  !TLI.isOperationLegalOrCustom(LogicOpcode, XVT))
4511  return SDValue();
4512  // Avoid infinite looping with PromoteIntBinOp.
4513  // TODO: Should we apply desirable/legal constraints to all opcodes?
4514  if (HandOpcode == ISD::ANY_EXTEND && LegalTypes &&
4515  !TLI.isTypeDesirableForOp(LogicOpcode, XVT))
4516  return SDValue();
4517  // logic_op (hand_op X), (hand_op Y) --> hand_op (logic_op X, Y)
4518  SDValue Logic = DAG.getNode(LogicOpcode, DL, XVT, X, Y);
4519  return DAG.getNode(HandOpcode, DL, VT, Logic);
4520  }
4521 
4522  // logic_op (truncate x), (truncate y) --> truncate (logic_op x, y)
4523  if (HandOpcode == ISD::TRUNCATE) {
4524  // If both operands have other uses, this transform would create extra
4525  // instructions without eliminating anything.
4526  if (!N0.hasOneUse() && !N1.hasOneUse())
4527  return SDValue();
4528  // We need matching source types.
4529  if (XVT != Y.getValueType())
4530  return SDValue();
4531  // Don't create an illegal op during or after legalization.
4532  if (LegalOperations && !TLI.isOperationLegal(LogicOpcode, XVT))
4533  return SDValue();
4534  // Be extra careful sinking truncate. If it's free, there's no benefit in
4535  // widening a binop. Also, don't create a logic op on an illegal type.
4536  if (TLI.isZExtFree(VT, XVT) && TLI.isTruncateFree(XVT, VT))
4537  return SDValue();
4538  if (!TLI.isTypeLegal(XVT))
4539  return SDValue();
4540  SDValue Logic = DAG.getNode(LogicOpcode, DL, XVT, X, Y);
4541  return DAG.getNode(HandOpcode, DL, VT, Logic);
4542  }
4543 
4544  // For binops SHL/SRL/SRA/AND:
4545  // logic_op (OP x, z), (OP y, z) --> OP (logic_op x, y), z
4546  if ((HandOpcode == ISD::SHL || HandOpcode == ISD::SRL ||
4547  HandOpcode == ISD::SRA || HandOpcode == ISD::AND) &&
4548  N0.getOperand(1) == N1.getOperand(1)) {
4549  // If either operand has other uses, this transform is not an improvement.
4550  if (!N0.hasOneUse() || !N1.hasOneUse())
4551  return SDValue();
4552  SDValue Logic = DAG.getNode(LogicOpcode, DL, XVT, X, Y);
4553  return DAG.getNode(HandOpcode, DL, VT, Logic, N0.getOperand(1));
4554  }
4555 
4556  // Unary ops: logic_op (bswap x), (bswap y) --> bswap (logic_op x, y)
4557  if (HandOpcode == ISD::BSWAP) {
4558  // If either operand has other uses, this transform is not an improvement.
4559  if (!N0.hasOneUse() || !N1.hasOneUse())
4560  return SDValue();
4561  SDValue Logic = DAG.getNode(LogicOpcode, DL, XVT, X, Y);
4562  return DAG.getNode(HandOpcode, DL, VT, Logic);
4563  }
4564 
4565  // Simplify xor/and/or (bitcast(A), bitcast(B)) -> bitcast(op (A,B))
4566  // Only perform this optimization up until type legalization, before
4567  // LegalizeVectorOprs. LegalizeVectorOprs promotes vector operations by
4568  // adding bitcasts. For example (xor v4i32) is promoted to (v2i64), and
4569  // we don't want to undo this promotion.
4570  // We also handle SCALAR_TO_VECTOR because xor/or/and operations are cheaper
4571  // on scalars.
4572  if ((HandOpcode == ISD::BITCAST || HandOpcode == ISD::SCALAR_TO_VECTOR) &&
4573  Level <= AfterLegalizeTypes) {
4574  // Input types must be integer and the same.
4575  if (XVT.isInteger() && XVT == Y.getValueType()) {
4576  SDValue Logic = DAG.getNode(LogicOpcode, DL, XVT, X, Y);
4577  return DAG.getNode(HandOpcode, DL, VT, Logic);
4578  }
4579  }
4580 
4581  // Xor/and/or are indifferent to the swizzle operation (shuffle of one value).
4582  // Simplify xor/and/or (shuff(A), shuff(B)) -> shuff(op (A,B))
4583  // If both shuffles use the same mask, and both shuffle within a single
4584  // vector, then it is worthwhile to move the swizzle after the operation.
4585  // The type-legalizer generates this pattern when loading illegal
4586  // vector types from memory. In many cases this allows additional shuffle
4587  // optimizations.
4588  // There are other cases where moving the shuffle after the xor/and/or
4589  // is profitable even if shuffles don't perform a swizzle.
4590  // If both shuffles use the same mask, and both shuffles have the same first
4591  // or second operand, then it might still be profitable to move the shuffle
4592  // after the xor/and/or operation.
4593  if (HandOpcode == ISD::VECTOR_SHUFFLE && Level < AfterLegalizeDAG) {
4594  auto *SVN0 = cast<ShuffleVectorSDNode>(N0);
4595  auto *SVN1 = cast<ShuffleVectorSDNode>(N1);
4596  assert(X.getValueType() == Y.getValueType() &&
4597  "Inputs to shuffles are not the same type");
4598 
4599  // Check that both shuffles use the same mask. The masks are known to be of
4600  // the same length because the result vector type is the same.
4601  // Check also that shuffles have only one use to avoid introducing extra
4602  // instructions.
4603  if (!SVN0->hasOneUse() || !SVN1->hasOneUse() ||
4604  !SVN0->getMask().equals(SVN1->getMask()))
4605  return SDValue();
4606 
4607  // Don't try to fold this node if it requires introducing a
4608  // build vector of all zeros that might be illegal at this stage.
4609  SDValue ShOp = N0.getOperand(1);
4610  if (LogicOpcode == ISD::XOR && !ShOp.isUndef())
4611  ShOp = tryFoldToZero(DL, TLI, VT, DAG, LegalOperations);
4612 
4613  // (logic_op (shuf (A, C), shuf (B, C))) --> shuf (logic_op (A, B), C)
4614  if (N0.getOperand(1) == N1.getOperand(1) && ShOp.getNode()) {
4615  SDValue Logic = DAG.getNode(LogicOpcode, DL, VT,
4616  N0.getOperand(0), N1.getOperand(0));
4617  return DAG.getVectorShuffle(VT, DL, Logic, ShOp, SVN0->getMask());
4618  }
4619 
4620  // Don't try to fold this node if it requires introducing a
4621  // build vector of all zeros that might be illegal at this stage.
4622  ShOp = N0.getOperand(0);
4623  if (LogicOpcode == ISD::XOR && !ShOp.isUndef())
4624  ShOp = tryFoldToZero(DL, TLI, VT, DAG, LegalOperations);
4625 
4626  // (logic_op (shuf (C, A), shuf (C, B))) --> shuf (C, logic_op (A, B))
4627  if (N0.getOperand(0) == N1.getOperand(0) && ShOp.getNode()) {
4628  SDValue Logic = DAG.getNode(LogicOpcode, DL, VT, N0.getOperand(1),
4629  N1.getOperand(1));
4630  return DAG.getVectorShuffle(VT, DL, ShOp, Logic, SVN0->getMask());
4631  }
4632  }
4633 
4634  return SDValue();
4635 }
4636 
4637 /// Try to make (and/or setcc (LL, LR), setcc (RL, RR)) more efficient.
4638 SDValue DAGCombiner::foldLogicOfSetCCs(bool IsAnd, SDValue N0, SDValue N1,
4639  const SDLoc &DL) {
4640  SDValue LL, LR, RL, RR, N0CC, N1CC;
4641  if (!isSetCCEquivalent(N0, LL, LR, N0CC) ||
4642  !isSetCCEquivalent(N1, RL, RR, N1CC))
4643  return SDValue();
4644 
4645  assert(N0.getValueType() == N1.getValueType() &&
4646  "Unexpected operand types for bitwise logic op");
4647  assert(LL.getValueType() == LR.getValueType() &&
4648  RL.getValueType() == RR.getValueType() &&
4649  "Unexpected operand types for setcc");
4650 
4651  // If we're here post-legalization or the logic op type is not i1, the logic
4652  // op type must match a setcc result type. Also, all folds require new
4653  // operations on the left and right operands, so those types must match.
4654  EVT VT = N0.getValueType();
4655  EVT OpVT = LL.getValueType();
4656  if (LegalOperations || VT.getScalarType() != MVT::i1)
4657  if (VT != getSetCCResultType(OpVT))
4658  return SDValue();
4659  if (OpVT != RL.getValueType())
4660  return SDValue();
4661 
4662  ISD::CondCode CC0 = cast<CondCodeSDNode>(N0CC)->get();
4663  ISD::CondCode CC1 = cast<CondCodeSDNode>(N1CC)->get();
4664  bool IsInteger = OpVT.isInteger();
4665  if (LR == RR && CC0 == CC1 && IsInteger) {
4666  bool IsZero = isNullOrNullSplat(LR);
4667  bool IsNeg1 = isAllOnesOrAllOnesSplat(LR);
4668 
4669  // All bits clear?
4670  bool AndEqZero = IsAnd && CC1 == ISD::SETEQ && IsZero;
4671  // All sign bits clear?
4672  bool AndGtNeg1 = IsAnd && CC1 == ISD::SETGT && IsNeg1;
4673  // Any bits set?
4674  bool OrNeZero = !IsAnd && CC1 == ISD::SETNE && IsZero;
4675  // Any sign bits set?
4676  bool OrLtZero = !IsAnd && CC1 == ISD::SETLT && IsZero;
4677 
4678  // (and (seteq X, 0), (seteq Y, 0)) --> (seteq (or X, Y), 0)
4679  // (and (setgt X, -1), (setgt Y, -1)) --> (setgt (or X, Y), -1)
4680  // (or (setne X, 0), (setne Y, 0)) --> (setne (or X, Y), 0)
4681  // (or (setlt X, 0), (setlt Y, 0)) --> (setlt (or X, Y), 0)
4682  if (AndEqZero || AndGtNeg1 || OrNeZero || OrLtZero) {
4683  SDValue Or = DAG.getNode(ISD::OR, SDLoc(N0), OpVT, LL, RL);
4684  AddToWorklist(Or.getNode());
4685  return DAG.getSetCC(DL, VT, Or, LR, CC1);
4686  }
4687 
4688  // All bits set?
4689  bool AndEqNeg1 = IsAnd && CC1 == ISD::SETEQ && IsNeg1;
4690  // All sign bits set?
4691  bool AndLtZero = IsAnd && CC1 == ISD::SETLT && IsZero;
4692  // Any bits clear?
4693  bool OrNeNeg1 = !IsAnd && CC1 == ISD::SETNE && IsNeg1;
4694  // Any sign bits clear?
4695  bool OrGtNeg1 = !IsAnd && CC1 == ISD::SETGT && IsNeg1;
4696 
4697  // (and (seteq X, -1), (seteq Y, -1)) --> (seteq (and X, Y), -1)
4698  // (and (setlt X, 0), (setlt Y, 0)) --> (setlt (and X, Y), 0)
4699  // (or (setne X, -1), (setne Y, -1)) --> (setne (and X, Y), -1)
4700  // (or (setgt X, -1), (setgt Y -1)) --> (setgt (and X, Y), -1)
4701  if (AndEqNeg1 || AndLtZero || OrNeNeg1 || OrGtNeg1) {
4702  SDValue And = DAG.getNode(ISD::AND, SDLoc(N0), OpVT, LL, RL);
4703  AddToWorklist(And.getNode());
4704  return DAG.getSetCC(DL, VT, And, LR, CC1);
4705  }
4706  }
4707 
4708  // TODO: What is the 'or' equivalent of this fold?
4709  // (and (setne X, 0), (setne X, -1)) --> (setuge (add X, 1), 2)
4710  if (IsAnd && LL == RL && CC0 == CC1 && OpVT.getScalarSizeInBits() > 1 &&
4711  IsInteger && CC0 == ISD::SETNE &&
4712  ((isNullConstant(LR) && isAllOnesConstant(RR)) ||
4713  (isAllOnesConstant(LR) && isNullConstant(RR)))) {
4714  SDValue One = DAG.getConstant(1, DL, OpVT);
4715  SDValue Two = DAG.getConstant(2, DL, OpVT);
4716  SDValue Add = DAG.getNode(ISD::ADD, SDLoc(N0), OpVT, LL, One);
4717  AddToWorklist(Add.getNode());
4718  return DAG.getSetCC(DL, VT, Add, Two, ISD::SETUGE);
4719  }
4720 
4721  // Try more general transforms if the predicates match and the only user of
4722  // the compares is the 'and' or 'or'.
4723  if (IsInteger && TLI.convertSetCCLogicToBitwiseLogic(OpVT) && CC0 == CC1 &&
4724  N0.hasOneUse() && N1.hasOneUse()) {
4725  // and (seteq A, B), (seteq C, D) --> seteq (or (xor A, B), (xor C, D)), 0
4726  // or (setne A, B), (setne C, D) --> setne (or (xor A, B), (xor C, D)), 0
4727  if ((IsAnd && CC1 == ISD::SETEQ) || (!IsAnd && CC1 == ISD::SETNE)) {
4728  SDValue XorL = DAG.getNode(ISD::XOR, SDLoc(N0), OpVT, LL, LR);
4729  SDValue XorR = DAG.getNode(ISD::XOR, SDLoc(N1), OpVT, RL, RR);
4730  SDValue Or = DAG.getNode(ISD::OR, DL, OpVT, XorL, XorR);
4731  SDValue Zero = DAG.getConstant(0, DL, OpVT);
4732  return DAG.getSetCC(DL, VT, Or, Zero, CC1);
4733  }
4734 
4735  // Turn compare of constants whose difference is 1 bit into add+and+setcc.
4736  // TODO - support non-uniform vector amounts.
4737  if ((IsAnd && CC1 == ISD::SETNE) || (!IsAnd && CC1 == ISD::SETEQ)) {
4738  // Match a shared variable operand and 2 non-opaque constant operands.
4741  if (LL == RL && C0 && C1 && !C0->isOpaque() && !C1->isOpaque()) {
4742  // Canonicalize larger constant as C0.
4743  if (C1->getAPIntValue().ugt(C0->getAPIntValue()))
4744  std::swap(C0, C1);
4745 
4746  // The difference of the constants must be a single bit.
4747  const APInt &C0Val = C0->getAPIntValue();
4748  const APInt &C1Val = C1->getAPIntValue();
4749  if ((C0Val - C1Val).isPowerOf2()) {
4750  // and/or (setcc X, C0, ne), (setcc X, C1, ne/eq) -->
4751  // setcc ((add X, -C1), ~(C0 - C1)), 0, ne/eq
4752  SDValue OffsetC = DAG.getConstant(-C1Val, DL, OpVT);
4753  SDValue Add = DAG.getNode(ISD::ADD, DL, OpVT, LL, OffsetC);
4754  SDValue MaskC = DAG.getConstant(~(C0Val - C1Val), DL, OpVT);
4755  SDValue And = DAG.getNode(ISD::AND, DL, OpVT, Add, MaskC);
4756  SDValue Zero = DAG.getConstant(0, DL, OpVT);
4757  return DAG.getSetCC(DL, VT, And, Zero, CC0);
4758  }
4759  }
4760  }
4761  }
4762 
4763  // Canonicalize equivalent operands to LL == RL.
4764  if (LL == RR && LR == RL) {
4765  CC1 = ISD::getSetCCSwappedOperands(CC1);
4766  std::swap(RL, RR);
4767  }
4768 
4769  // (and (setcc X, Y, CC0), (setcc X, Y, CC1)) --> (setcc X, Y, NewCC)
4770  // (or (setcc X, Y, CC0), (setcc X, Y, CC1)) --> (setcc X, Y, NewCC)
4771  if (LL == RL && LR == RR) {
4772  ISD::CondCode NewCC = IsAnd ? ISD::getSetCCAndOperation(CC0, CC1, IsInteger)
4773  : ISD::getSetCCOrOperation(CC0, CC1, IsInteger);
4774  if (NewCC != ISD::SETCC_INVALID &&
4775  (!LegalOperations ||
4776  (TLI.isCondCodeLegal(NewCC, LL.getSimpleValueType()) &&
4777  TLI.isOperationLegal(ISD::SETCC, OpVT))))
4778  return DAG.getSetCC(DL, VT, LL, LR, NewCC);
4779  }
4780 
4781  return SDValue();
4782 }
4783 
4784 /// This contains all DAGCombine rules which reduce two values combined by
4785 /// an And operation to a single value. This makes them reusable in the context
4786 /// of visitSELECT(). Rules involving constants are not included as
4787 /// visitSELECT() already handles those cases.
4788 SDValue DAGCombiner::visitANDLike(SDValue N0, SDValue N1, SDNode *N) {
4789  EVT VT = N1.getValueType();
4790  SDLoc DL(N);
4791 
4792  // fold (and x, undef) -> 0
4793  if (N0.isUndef() || N1.isUndef())
4794  return DAG.getConstant(0, DL, VT);
4795 
4796  if (SDValue V = foldLogicOfSetCCs(true, N0, N1, DL))
4797  return V;
4798 
4799  if (N0.getOpcode() == ISD::ADD && N1.getOpcode() == ISD::SRL &&
4800  VT.getSizeInBits() <= 64) {
4801  if (ConstantSDNode *ADDI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
4802  if (ConstantSDNode *SRLI = dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
4803  // Look for (and (add x, c1), (lshr y, c2)). If C1 wasn't a legal
4804  // immediate for an add, but it is legal if its top c2 bits are set,
4805  // transform the ADD so the immediate doesn't need to be materialized
4806  // in a register.
4807  APInt ADDC = ADDI->getAPIntValue();
4808  APInt SRLC = SRLI->getAPIntValue();
4809  if (ADDC.getMinSignedBits() <= 64 &&
4810  SRLC.ult(VT.getSizeInBits()) &&
4811  !TLI.isLegalAddImmediate(ADDC.getSExtValue())) {
4813  SRLC.getZExtValue());
4814  if (DAG.MaskedValueIsZero(N0.getOperand(1), Mask)) {
4815  ADDC |= Mask;
4816  if (TLI.isLegalAddImmediate(ADDC.getSExtValue())) {
4817  SDLoc DL0(N0);
4818  SDValue NewAdd =
4819  DAG.getNode(ISD::ADD, DL0, VT,
4820  N0.getOperand(0), DAG.getConstant(ADDC, DL, VT));
4821  CombineTo(N0.getNode(), NewAdd);
4822  // Return N so it doesn't get rechecked!
4823  return SDValue(N, 0);
4824  }
4825  }
4826  }
4827  }
4828  }