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