Generates conditional branch instead of fake ones for Select instruction in some...
[oota-llvm.git] / lib / CodeGen / SelectionDAG / DAGCombiner.cpp
1 //===-- DAGCombiner.cpp - Implement a DAG node combiner -------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass combines dag nodes to form fewer, simpler DAG nodes.  It can be run
11 // both before and after the DAG is legalized.
12 //
13 // This pass is not a substitute for the LLVM IR instcombine pass. This pass is
14 // primarily intended to handle simplification opportunities that are implicit
15 // in the LLVM IR and exposed by the various codegen lowering phases.
16 //
17 //===----------------------------------------------------------------------===//
18
19 #include "llvm/CodeGen/SelectionDAG.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/ADT/SmallBitVector.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/CodeGen/MachineFrameInfo.h"
26 #include "llvm/CodeGen/MachineFunction.h"
27 #include "llvm/IR/DataLayout.h"
28 #include "llvm/IR/DerivedTypes.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/LLVMContext.h"
31 #include "llvm/Support/CommandLine.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Support/ErrorHandling.h"
34 #include "llvm/Support/MathExtras.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include "llvm/Target/TargetLowering.h"
37 #include "llvm/Target/TargetOptions.h"
38 #include "llvm/Target/TargetRegisterInfo.h"
39 #include "llvm/Target/TargetSubtargetInfo.h"
40 #include <algorithm>
41 using namespace llvm;
42
43 #define DEBUG_TYPE "dagcombine"
44
45 STATISTIC(NodesCombined   , "Number of dag nodes combined");
46 STATISTIC(PreIndexedNodes , "Number of pre-indexed nodes created");
47 STATISTIC(PostIndexedNodes, "Number of post-indexed nodes created");
48 STATISTIC(OpsNarrowed     , "Number of load/op/store narrowed");
49 STATISTIC(LdStFP2Int      , "Number of fp load/store pairs transformed to int");
50 STATISTIC(SlicedLoads, "Number of load sliced");
51
52 namespace {
53   static cl::opt<bool>
54     CombinerAA("combiner-alias-analysis", cl::Hidden,
55                cl::desc("Enable DAG combiner alias-analysis heuristics"));
56
57   static cl::opt<bool>
58     CombinerGlobalAA("combiner-global-alias-analysis", cl::Hidden,
59                cl::desc("Enable DAG combiner's use of IR alias analysis"));
60
61   static cl::opt<bool>
62     UseTBAA("combiner-use-tbaa", cl::Hidden, cl::init(true),
63                cl::desc("Enable DAG combiner's use of TBAA"));
64
65 #ifndef NDEBUG
66   static cl::opt<std::string>
67     CombinerAAOnlyFunc("combiner-aa-only-func", cl::Hidden,
68                cl::desc("Only use DAG-combiner alias analysis in this"
69                         " function"));
70 #endif
71
72   /// Hidden option to stress test load slicing, i.e., when this option
73   /// is enabled, load slicing bypasses most of its profitability guards.
74   static cl::opt<bool>
75   StressLoadSlicing("combiner-stress-load-slicing", cl::Hidden,
76                     cl::desc("Bypass the profitability model of load "
77                              "slicing"),
78                     cl::init(false));
79
80   static cl::opt<bool>
81     MaySplitLoadIndex("combiner-split-load-index", cl::Hidden, cl::init(true),
82                       cl::desc("DAG combiner may split indexing from loads"));
83
84 //------------------------------ DAGCombiner ---------------------------------//
85
86   class DAGCombiner {
87     SelectionDAG &DAG;
88     const TargetLowering &TLI;
89     CombineLevel Level;
90     CodeGenOpt::Level OptLevel;
91     bool LegalOperations;
92     bool LegalTypes;
93     bool ForCodeSize;
94
95     /// \brief Worklist of all of the nodes that need to be simplified.
96     ///
97     /// This must behave as a stack -- new nodes to process are pushed onto the
98     /// back and when processing we pop off of the back.
99     ///
100     /// The worklist will not contain duplicates but may contain null entries
101     /// due to nodes being deleted from the underlying DAG.
102     SmallVector<SDNode *, 64> Worklist;
103
104     /// \brief Mapping from an SDNode to its position on the worklist.
105     ///
106     /// This is used to find and remove nodes from the worklist (by nulling
107     /// them) when they are deleted from the underlying DAG. It relies on
108     /// stable indices of nodes within the worklist.
109     DenseMap<SDNode *, unsigned> WorklistMap;
110
111     /// \brief Set of nodes which have been combined (at least once).
112     ///
113     /// This is used to allow us to reliably add any operands of a DAG node
114     /// which have not yet been combined to the worklist.
115     SmallPtrSet<SDNode *, 64> CombinedNodes;
116
117     // AA - Used for DAG load/store alias analysis.
118     AliasAnalysis &AA;
119
120     /// When an instruction is simplified, add all users of the instruction to
121     /// the work lists because they might get more simplified now.
122     void AddUsersToWorklist(SDNode *N) {
123       for (SDNode *Node : N->uses())
124         AddToWorklist(Node);
125     }
126
127     /// Call the node-specific routine that folds each particular type of node.
128     SDValue visit(SDNode *N);
129
130   public:
131     /// Add to the worklist making sure its instance is at the back (next to be
132     /// processed.)
133     void AddToWorklist(SDNode *N) {
134       // Skip handle nodes as they can't usefully be combined and confuse the
135       // zero-use deletion strategy.
136       if (N->getOpcode() == ISD::HANDLENODE)
137         return;
138
139       if (WorklistMap.insert(std::make_pair(N, Worklist.size())).second)
140         Worklist.push_back(N);
141     }
142
143     /// Remove all instances of N from the worklist.
144     void removeFromWorklist(SDNode *N) {
145       CombinedNodes.erase(N);
146
147       auto It = WorklistMap.find(N);
148       if (It == WorklistMap.end())
149         return; // Not in the worklist.
150
151       // Null out the entry rather than erasing it to avoid a linear operation.
152       Worklist[It->second] = nullptr;
153       WorklistMap.erase(It);
154     }
155
156     void deleteAndRecombine(SDNode *N);
157     bool recursivelyDeleteUnusedNodes(SDNode *N);
158
159     /// Replaces all uses of the results of one DAG node with new values.
160     SDValue CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
161                       bool AddTo = true);
162
163     /// Replaces all uses of the results of one DAG node with new values.
164     SDValue CombineTo(SDNode *N, SDValue Res, bool AddTo = true) {
165       return CombineTo(N, &Res, 1, AddTo);
166     }
167
168     /// Replaces all uses of the results of one DAG node with new values.
169     SDValue CombineTo(SDNode *N, SDValue Res0, SDValue Res1,
170                       bool AddTo = true) {
171       SDValue To[] = { Res0, Res1 };
172       return CombineTo(N, To, 2, AddTo);
173     }
174
175     void CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO);
176
177   private:
178
179     /// Check the specified integer node value to see if it can be simplified or
180     /// if things it uses can be simplified by bit propagation.
181     /// If so, return true.
182     bool SimplifyDemandedBits(SDValue Op) {
183       unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
184       APInt Demanded = APInt::getAllOnesValue(BitWidth);
185       return SimplifyDemandedBits(Op, Demanded);
186     }
187
188     bool SimplifyDemandedBits(SDValue Op, const APInt &Demanded);
189
190     bool CombineToPreIndexedLoadStore(SDNode *N);
191     bool CombineToPostIndexedLoadStore(SDNode *N);
192     SDValue SplitIndexingFromLoad(LoadSDNode *LD);
193     bool SliceUpLoad(SDNode *N);
194
195     /// \brief Replace an ISD::EXTRACT_VECTOR_ELT of a load with a narrowed
196     ///   load.
197     ///
198     /// \param EVE ISD::EXTRACT_VECTOR_ELT to be replaced.
199     /// \param InVecVT type of the input vector to EVE with bitcasts resolved.
200     /// \param EltNo index of the vector element to load.
201     /// \param OriginalLoad load that EVE came from to be replaced.
202     /// \returns EVE on success SDValue() on failure.
203     SDValue ReplaceExtractVectorEltOfLoadWithNarrowedLoad(
204         SDNode *EVE, EVT InVecVT, SDValue EltNo, LoadSDNode *OriginalLoad);
205     void ReplaceLoadWithPromotedLoad(SDNode *Load, SDNode *ExtLoad);
206     SDValue PromoteOperand(SDValue Op, EVT PVT, bool &Replace);
207     SDValue SExtPromoteOperand(SDValue Op, EVT PVT);
208     SDValue ZExtPromoteOperand(SDValue Op, EVT PVT);
209     SDValue PromoteIntBinOp(SDValue Op);
210     SDValue PromoteIntShiftOp(SDValue Op);
211     SDValue PromoteExtend(SDValue Op);
212     bool PromoteLoad(SDValue Op);
213
214     void ExtendSetCCUses(const SmallVectorImpl<SDNode *> &SetCCs,
215                          SDValue Trunc, SDValue ExtLoad, SDLoc DL,
216                          ISD::NodeType ExtType);
217
218     /// Call the node-specific routine that knows how to fold each
219     /// particular type of node. If that doesn't do anything, try the
220     /// target-specific DAG combines.
221     SDValue combine(SDNode *N);
222
223     // Visitation implementation - Implement dag node combining for different
224     // node types.  The semantics are as follows:
225     // Return Value:
226     //   SDValue.getNode() == 0 - No change was made
227     //   SDValue.getNode() == N - N was replaced, is dead and has been handled.
228     //   otherwise              - N should be replaced by the returned Operand.
229     //
230     SDValue visitTokenFactor(SDNode *N);
231     SDValue visitMERGE_VALUES(SDNode *N);
232     SDValue visitADD(SDNode *N);
233     SDValue visitSUB(SDNode *N);
234     SDValue visitADDC(SDNode *N);
235     SDValue visitSUBC(SDNode *N);
236     SDValue visitADDE(SDNode *N);
237     SDValue visitSUBE(SDNode *N);
238     SDValue visitMUL(SDNode *N);
239     SDValue useDivRem(SDNode *N);
240     SDValue visitSDIV(SDNode *N);
241     SDValue visitUDIV(SDNode *N);
242     SDValue visitREM(SDNode *N);
243     SDValue visitMULHU(SDNode *N);
244     SDValue visitMULHS(SDNode *N);
245     SDValue visitSMUL_LOHI(SDNode *N);
246     SDValue visitUMUL_LOHI(SDNode *N);
247     SDValue visitSMULO(SDNode *N);
248     SDValue visitUMULO(SDNode *N);
249     SDValue visitIMINMAX(SDNode *N);
250     SDValue visitAND(SDNode *N);
251     SDValue visitANDLike(SDValue N0, SDValue N1, SDNode *LocReference);
252     SDValue visitOR(SDNode *N);
253     SDValue visitORLike(SDValue N0, SDValue N1, SDNode *LocReference);
254     SDValue visitXOR(SDNode *N);
255     SDValue SimplifyVBinOp(SDNode *N);
256     SDValue visitSHL(SDNode *N);
257     SDValue visitSRA(SDNode *N);
258     SDValue visitSRL(SDNode *N);
259     SDValue visitRotate(SDNode *N);
260     SDValue visitBSWAP(SDNode *N);
261     SDValue visitCTLZ(SDNode *N);
262     SDValue visitCTLZ_ZERO_UNDEF(SDNode *N);
263     SDValue visitCTTZ(SDNode *N);
264     SDValue visitCTTZ_ZERO_UNDEF(SDNode *N);
265     SDValue visitCTPOP(SDNode *N);
266     SDValue visitSELECT(SDNode *N);
267     SDValue visitVSELECT(SDNode *N);
268     SDValue visitSELECT_CC(SDNode *N);
269     SDValue visitSETCC(SDNode *N);
270     SDValue visitSETCCE(SDNode *N);
271     SDValue visitSIGN_EXTEND(SDNode *N);
272     SDValue visitZERO_EXTEND(SDNode *N);
273     SDValue visitANY_EXTEND(SDNode *N);
274     SDValue visitSIGN_EXTEND_INREG(SDNode *N);
275     SDValue visitSIGN_EXTEND_VECTOR_INREG(SDNode *N);
276     SDValue visitTRUNCATE(SDNode *N);
277     SDValue visitBITCAST(SDNode *N);
278     SDValue visitBUILD_PAIR(SDNode *N);
279     SDValue visitFADD(SDNode *N);
280     SDValue visitFSUB(SDNode *N);
281     SDValue visitFMUL(SDNode *N);
282     SDValue visitFMA(SDNode *N);
283     SDValue visitFDIV(SDNode *N);
284     SDValue visitFREM(SDNode *N);
285     SDValue visitFSQRT(SDNode *N);
286     SDValue visitFCOPYSIGN(SDNode *N);
287     SDValue visitSINT_TO_FP(SDNode *N);
288     SDValue visitUINT_TO_FP(SDNode *N);
289     SDValue visitFP_TO_SINT(SDNode *N);
290     SDValue visitFP_TO_UINT(SDNode *N);
291     SDValue visitFP_ROUND(SDNode *N);
292     SDValue visitFP_ROUND_INREG(SDNode *N);
293     SDValue visitFP_EXTEND(SDNode *N);
294     SDValue visitFNEG(SDNode *N);
295     SDValue visitFABS(SDNode *N);
296     SDValue visitFCEIL(SDNode *N);
297     SDValue visitFTRUNC(SDNode *N);
298     SDValue visitFFLOOR(SDNode *N);
299     SDValue visitFMINNUM(SDNode *N);
300     SDValue visitFMAXNUM(SDNode *N);
301     SDValue visitBRCOND(SDNode *N);
302     SDValue visitBR_CC(SDNode *N);
303     SDValue visitLOAD(SDNode *N);
304
305     SDValue replaceStoreChain(StoreSDNode *ST, SDValue BetterChain);
306     SDValue replaceStoreOfFPConstant(StoreSDNode *ST);
307
308     SDValue visitSTORE(SDNode *N);
309     SDValue visitINSERT_VECTOR_ELT(SDNode *N);
310     SDValue visitEXTRACT_VECTOR_ELT(SDNode *N);
311     SDValue visitBUILD_VECTOR(SDNode *N);
312     SDValue visitCONCAT_VECTORS(SDNode *N);
313     SDValue visitEXTRACT_SUBVECTOR(SDNode *N);
314     SDValue visitVECTOR_SHUFFLE(SDNode *N);
315     SDValue visitSCALAR_TO_VECTOR(SDNode *N);
316     SDValue visitINSERT_SUBVECTOR(SDNode *N);
317     SDValue visitMLOAD(SDNode *N);
318     SDValue visitMSTORE(SDNode *N);
319     SDValue visitMGATHER(SDNode *N);
320     SDValue visitMSCATTER(SDNode *N);
321     SDValue visitFP_TO_FP16(SDNode *N);
322     SDValue visitFP16_TO_FP(SDNode *N);
323
324     SDValue visitFADDForFMACombine(SDNode *N);
325     SDValue visitFSUBForFMACombine(SDNode *N);
326     SDValue visitFMULForFMACombine(SDNode *N);
327
328     SDValue XformToShuffleWithZero(SDNode *N);
329     SDValue ReassociateOps(unsigned Opc, SDLoc DL, SDValue LHS, SDValue RHS);
330
331     SDValue visitShiftByConstant(SDNode *N, ConstantSDNode *Amt);
332
333     bool SimplifySelectOps(SDNode *SELECT, SDValue LHS, SDValue RHS);
334     SDValue SimplifyBinOpWithSameOpcodeHands(SDNode *N);
335     SDValue SimplifySelect(SDLoc DL, SDValue N0, SDValue N1, SDValue N2);
336     SDValue SimplifySelectCC(SDLoc DL, SDValue N0, SDValue N1, SDValue N2,
337                              SDValue N3, ISD::CondCode CC,
338                              bool NotExtCompare = false);
339     SDValue SimplifySetCC(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond,
340                           SDLoc DL, bool foldBooleans = true);
341
342     bool isSetCCEquivalent(SDValue N, SDValue &LHS, SDValue &RHS,
343                            SDValue &CC) const;
344     bool isOneUseSetCC(SDValue N) const;
345
346     SDValue SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp,
347                                          unsigned HiOp);
348     SDValue CombineConsecutiveLoads(SDNode *N, EVT VT);
349     SDValue CombineExtLoad(SDNode *N);
350     SDValue combineRepeatedFPDivisors(SDNode *N);
351     SDValue ConstantFoldBITCASTofBUILD_VECTOR(SDNode *, EVT);
352     SDValue BuildSDIV(SDNode *N);
353     SDValue BuildSDIVPow2(SDNode *N);
354     SDValue BuildUDIV(SDNode *N);
355     SDValue BuildReciprocalEstimate(SDValue Op, SDNodeFlags *Flags);
356     SDValue BuildRsqrtEstimate(SDValue Op, SDNodeFlags *Flags);
357     SDValue BuildRsqrtNROneConst(SDValue Op, SDValue Est, unsigned Iterations,
358                                  SDNodeFlags *Flags);
359     SDValue BuildRsqrtNRTwoConst(SDValue Op, SDValue Est, unsigned Iterations,
360                                  SDNodeFlags *Flags);
361     SDValue MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
362                                bool DemandHighBits = true);
363     SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
364     SDNode *MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
365                               SDValue InnerPos, SDValue InnerNeg,
366                               unsigned PosOpcode, unsigned NegOpcode,
367                               SDLoc DL);
368     SDNode *MatchRotate(SDValue LHS, SDValue RHS, SDLoc DL);
369     SDValue ReduceLoadWidth(SDNode *N);
370     SDValue ReduceLoadOpStoreWidth(SDNode *N);
371     SDValue TransformFPLoadStorePair(SDNode *N);
372     SDValue reduceBuildVecExtToExtBuildVec(SDNode *N);
373     SDValue reduceBuildVecConvertToConvertBuildVec(SDNode *N);
374
375     SDValue GetDemandedBits(SDValue V, const APInt &Mask);
376
377     /// Walk up chain skipping non-aliasing memory nodes,
378     /// looking for aliasing nodes and adding them to the Aliases vector.
379     void GatherAllAliases(SDNode *N, SDValue OriginalChain,
380                           SmallVectorImpl<SDValue> &Aliases);
381
382     /// Return true if there is any possibility that the two addresses overlap.
383     bool isAlias(LSBaseSDNode *Op0, LSBaseSDNode *Op1) const;
384
385     /// Walk up chain skipping non-aliasing memory nodes, looking for a better
386     /// chain (aliasing node.)
387     SDValue FindBetterChain(SDNode *N, SDValue Chain);
388
389     /// Do FindBetterChain for a store and any possibly adjacent stores on
390     /// consecutive chains.
391     bool findBetterNeighborChains(StoreSDNode *St);
392
393     /// Holds a pointer to an LSBaseSDNode as well as information on where it
394     /// is located in a sequence of memory operations connected by a chain.
395     struct MemOpLink {
396       MemOpLink (LSBaseSDNode *N, int64_t Offset, unsigned Seq):
397       MemNode(N), OffsetFromBase(Offset), SequenceNum(Seq) { }
398       // Ptr to the mem node.
399       LSBaseSDNode *MemNode;
400       // Offset from the base ptr.
401       int64_t OffsetFromBase;
402       // What is the sequence number of this mem node.
403       // Lowest mem operand in the DAG starts at zero.
404       unsigned SequenceNum;
405     };
406
407     /// This is a helper function for visitMUL to check the profitability
408     /// of folding (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2).
409     /// MulNode is the original multiply, AddNode is (add x, c1),
410     /// and ConstNode is c2.
411     bool isMulAddWithConstProfitable(SDNode *MulNode,
412                                      SDValue &AddNode,
413                                      SDValue &ConstNode);
414
415     /// This is a helper function for MergeStoresOfConstantsOrVecElts. Returns a
416     /// constant build_vector of the stored constant values in Stores.
417     SDValue getMergedConstantVectorStore(SelectionDAG &DAG,
418                                          SDLoc SL,
419                                          ArrayRef<MemOpLink> Stores,
420                                          SmallVectorImpl<SDValue> &Chains,
421                                          EVT Ty) const;
422
423     /// This is a helper function for visitAND and visitZERO_EXTEND.  Returns
424     /// true if the (and (load x) c) pattern matches an extload.  ExtVT returns
425     /// the type of the loaded value to be extended.  LoadedVT returns the type
426     /// of the original loaded value.  NarrowLoad returns whether the load would
427     /// need to be narrowed in order to match.
428     bool isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
429                           EVT LoadResultTy, EVT &ExtVT, EVT &LoadedVT,
430                           bool &NarrowLoad);
431
432     /// This is a helper function for MergeConsecutiveStores. When the source
433     /// elements of the consecutive stores are all constants or all extracted
434     /// vector elements, try to merge them into one larger store.
435     /// \return True if a merged store was created.
436     bool MergeStoresOfConstantsOrVecElts(SmallVectorImpl<MemOpLink> &StoreNodes,
437                                          EVT MemVT, unsigned NumStores,
438                                          bool IsConstantSrc, bool UseVector);
439
440     /// This is a helper function for MergeConsecutiveStores.
441     /// Stores that may be merged are placed in StoreNodes.
442     /// Loads that may alias with those stores are placed in AliasLoadNodes.
443     void getStoreMergeAndAliasCandidates(
444         StoreSDNode* St, SmallVectorImpl<MemOpLink> &StoreNodes,
445         SmallVectorImpl<LSBaseSDNode*> &AliasLoadNodes);
446
447     /// Merge consecutive store operations into a wide store.
448     /// This optimization uses wide integers or vectors when possible.
449     /// \return True if some memory operations were changed.
450     bool MergeConsecutiveStores(StoreSDNode *N);
451
452     /// \brief Try to transform a truncation where C is a constant:
453     ///     (trunc (and X, C)) -> (and (trunc X), (trunc C))
454     ///
455     /// \p N needs to be a truncation and its first operand an AND. Other
456     /// requirements are checked by the function (e.g. that trunc is
457     /// single-use) and if missed an empty SDValue is returned.
458     SDValue distributeTruncateThroughAnd(SDNode *N);
459
460   public:
461     DAGCombiner(SelectionDAG &D, AliasAnalysis &A, CodeGenOpt::Level OL)
462         : DAG(D), TLI(D.getTargetLoweringInfo()), Level(BeforeLegalizeTypes),
463           OptLevel(OL), LegalOperations(false), LegalTypes(false), AA(A) {
464       ForCodeSize = DAG.getMachineFunction().getFunction()->optForSize();
465     }
466
467     /// Runs the dag combiner on all nodes in the work list
468     void Run(CombineLevel AtLevel);
469
470     SelectionDAG &getDAG() const { return DAG; }
471
472     /// Returns a type large enough to hold any valid shift amount - before type
473     /// legalization these can be huge.
474     EVT getShiftAmountTy(EVT LHSTy) {
475       assert(LHSTy.isInteger() && "Shift amount is not an integer type!");
476       if (LHSTy.isVector())
477         return LHSTy;
478       auto &DL = DAG.getDataLayout();
479       return LegalTypes ? TLI.getScalarShiftAmountTy(DL, LHSTy)
480                         : TLI.getPointerTy(DL);
481     }
482
483     /// This method returns true if we are running before type legalization or
484     /// if the specified VT is legal.
485     bool isTypeLegal(const EVT &VT) {
486       if (!LegalTypes) return true;
487       return TLI.isTypeLegal(VT);
488     }
489
490     /// Convenience wrapper around TargetLowering::getSetCCResultType
491     EVT getSetCCResultType(EVT VT) const {
492       return TLI.getSetCCResultType(DAG.getDataLayout(), *DAG.getContext(), VT);
493     }
494   };
495 }
496
497
498 namespace {
499 /// This class is a DAGUpdateListener that removes any deleted
500 /// nodes from the worklist.
501 class WorklistRemover : public SelectionDAG::DAGUpdateListener {
502   DAGCombiner &DC;
503 public:
504   explicit WorklistRemover(DAGCombiner &dc)
505     : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
506
507   void NodeDeleted(SDNode *N, SDNode *E) override {
508     DC.removeFromWorklist(N);
509   }
510 };
511 }
512
513 //===----------------------------------------------------------------------===//
514 //  TargetLowering::DAGCombinerInfo implementation
515 //===----------------------------------------------------------------------===//
516
517 void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) {
518   ((DAGCombiner*)DC)->AddToWorklist(N);
519 }
520
521 void TargetLowering::DAGCombinerInfo::RemoveFromWorklist(SDNode *N) {
522   ((DAGCombiner*)DC)->removeFromWorklist(N);
523 }
524
525 SDValue TargetLowering::DAGCombinerInfo::
526 CombineTo(SDNode *N, ArrayRef<SDValue> To, bool AddTo) {
527   return ((DAGCombiner*)DC)->CombineTo(N, &To[0], To.size(), AddTo);
528 }
529
530 SDValue TargetLowering::DAGCombinerInfo::
531 CombineTo(SDNode *N, SDValue Res, bool AddTo) {
532   return ((DAGCombiner*)DC)->CombineTo(N, Res, AddTo);
533 }
534
535
536 SDValue TargetLowering::DAGCombinerInfo::
537 CombineTo(SDNode *N, SDValue Res0, SDValue Res1, bool AddTo) {
538   return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1, AddTo);
539 }
540
541 void TargetLowering::DAGCombinerInfo::
542 CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO) {
543   return ((DAGCombiner*)DC)->CommitTargetLoweringOpt(TLO);
544 }
545
546 //===----------------------------------------------------------------------===//
547 // Helper Functions
548 //===----------------------------------------------------------------------===//
549
550 void DAGCombiner::deleteAndRecombine(SDNode *N) {
551   removeFromWorklist(N);
552
553   // If the operands of this node are only used by the node, they will now be
554   // dead. Make sure to re-visit them and recursively delete dead nodes.
555   for (const SDValue &Op : N->ops())
556     // For an operand generating multiple values, one of the values may
557     // become dead allowing further simplification (e.g. split index
558     // arithmetic from an indexed load).
559     if (Op->hasOneUse() || Op->getNumValues() > 1)
560       AddToWorklist(Op.getNode());
561
562   DAG.DeleteNode(N);
563 }
564
565 /// Return 1 if we can compute the negated form of the specified expression for
566 /// the same cost as the expression itself, or 2 if we can compute the negated
567 /// form more cheaply than the expression itself.
568 static char isNegatibleForFree(SDValue Op, bool LegalOperations,
569                                const TargetLowering &TLI,
570                                const TargetOptions *Options,
571                                unsigned Depth = 0) {
572   // fneg is removable even if it has multiple uses.
573   if (Op.getOpcode() == ISD::FNEG) return 2;
574
575   // Don't allow anything with multiple uses.
576   if (!Op.hasOneUse()) return 0;
577
578   // Don't recurse exponentially.
579   if (Depth > 6) return 0;
580
581   switch (Op.getOpcode()) {
582   default: return false;
583   case ISD::ConstantFP:
584     // Don't invert constant FP values after legalize.  The negated constant
585     // isn't necessarily legal.
586     return LegalOperations ? 0 : 1;
587   case ISD::FADD:
588     // FIXME: determine better conditions for this xform.
589     if (!Options->UnsafeFPMath) return 0;
590
591     // After operation legalization, it might not be legal to create new FSUBs.
592     if (LegalOperations &&
593         !TLI.isOperationLegalOrCustom(ISD::FSUB,  Op.getValueType()))
594       return 0;
595
596     // fold (fneg (fadd A, B)) -> (fsub (fneg A), B)
597     if (char V = isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI,
598                                     Options, Depth + 1))
599       return V;
600     // fold (fneg (fadd A, B)) -> (fsub (fneg B), A)
601     return isNegatibleForFree(Op.getOperand(1), LegalOperations, TLI, Options,
602                               Depth + 1);
603   case ISD::FSUB:
604     // We can't turn -(A-B) into B-A when we honor signed zeros.
605     if (!Options->UnsafeFPMath) return 0;
606
607     // fold (fneg (fsub A, B)) -> (fsub B, A)
608     return 1;
609
610   case ISD::FMUL:
611   case ISD::FDIV:
612     if (Options->HonorSignDependentRoundingFPMath()) return 0;
613
614     // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y) or (fmul X, (fneg Y))
615     if (char V = isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI,
616                                     Options, Depth + 1))
617       return V;
618
619     return isNegatibleForFree(Op.getOperand(1), LegalOperations, TLI, Options,
620                               Depth + 1);
621
622   case ISD::FP_EXTEND:
623   case ISD::FP_ROUND:
624   case ISD::FSIN:
625     return isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI, Options,
626                               Depth + 1);
627   }
628 }
629
630 /// If isNegatibleForFree returns true, return the newly negated expression.
631 static SDValue GetNegatedExpression(SDValue Op, SelectionDAG &DAG,
632                                     bool LegalOperations, unsigned Depth = 0) {
633   const TargetOptions &Options = DAG.getTarget().Options;
634   // fneg is removable even if it has multiple uses.
635   if (Op.getOpcode() == ISD::FNEG) return Op.getOperand(0);
636
637   // Don't allow anything with multiple uses.
638   assert(Op.hasOneUse() && "Unknown reuse!");
639
640   assert(Depth <= 6 && "GetNegatedExpression doesn't match isNegatibleForFree");
641
642   const SDNodeFlags *Flags = Op.getNode()->getFlags();
643
644   switch (Op.getOpcode()) {
645   default: llvm_unreachable("Unknown code");
646   case ISD::ConstantFP: {
647     APFloat V = cast<ConstantFPSDNode>(Op)->getValueAPF();
648     V.changeSign();
649     return DAG.getConstantFP(V, SDLoc(Op), Op.getValueType());
650   }
651   case ISD::FADD:
652     // FIXME: determine better conditions for this xform.
653     assert(Options.UnsafeFPMath);
654
655     // fold (fneg (fadd A, B)) -> (fsub (fneg A), B)
656     if (isNegatibleForFree(Op.getOperand(0), LegalOperations,
657                            DAG.getTargetLoweringInfo(), &Options, Depth+1))
658       return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
659                          GetNegatedExpression(Op.getOperand(0), DAG,
660                                               LegalOperations, Depth+1),
661                          Op.getOperand(1), Flags);
662     // fold (fneg (fadd A, B)) -> (fsub (fneg B), A)
663     return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
664                        GetNegatedExpression(Op.getOperand(1), DAG,
665                                             LegalOperations, Depth+1),
666                        Op.getOperand(0), Flags);
667   case ISD::FSUB:
668     // We can't turn -(A-B) into B-A when we honor signed zeros.
669     assert(Options.UnsafeFPMath);
670
671     // fold (fneg (fsub 0, B)) -> B
672     if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(Op.getOperand(0)))
673       if (N0CFP->isZero())
674         return Op.getOperand(1);
675
676     // fold (fneg (fsub A, B)) -> (fsub B, A)
677     return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
678                        Op.getOperand(1), Op.getOperand(0), Flags);
679
680   case ISD::FMUL:
681   case ISD::FDIV:
682     assert(!Options.HonorSignDependentRoundingFPMath());
683
684     // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y)
685     if (isNegatibleForFree(Op.getOperand(0), LegalOperations,
686                            DAG.getTargetLoweringInfo(), &Options, Depth+1))
687       return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
688                          GetNegatedExpression(Op.getOperand(0), DAG,
689                                               LegalOperations, Depth+1),
690                          Op.getOperand(1), Flags);
691
692     // fold (fneg (fmul X, Y)) -> (fmul X, (fneg Y))
693     return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
694                        Op.getOperand(0),
695                        GetNegatedExpression(Op.getOperand(1), DAG,
696                                             LegalOperations, Depth+1), Flags);
697
698   case ISD::FP_EXTEND:
699   case ISD::FSIN:
700     return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
701                        GetNegatedExpression(Op.getOperand(0), DAG,
702                                             LegalOperations, Depth+1));
703   case ISD::FP_ROUND:
704       return DAG.getNode(ISD::FP_ROUND, SDLoc(Op), Op.getValueType(),
705                          GetNegatedExpression(Op.getOperand(0), DAG,
706                                               LegalOperations, Depth+1),
707                          Op.getOperand(1));
708   }
709 }
710
711 // Return true if this node is a setcc, or is a select_cc
712 // that selects between the target values used for true and false, making it
713 // equivalent to a setcc. Also, set the incoming LHS, RHS, and CC references to
714 // the appropriate nodes based on the type of node we are checking. This
715 // simplifies life a bit for the callers.
716 bool DAGCombiner::isSetCCEquivalent(SDValue N, SDValue &LHS, SDValue &RHS,
717                                     SDValue &CC) const {
718   if (N.getOpcode() == ISD::SETCC) {
719     LHS = N.getOperand(0);
720     RHS = N.getOperand(1);
721     CC  = N.getOperand(2);
722     return true;
723   }
724
725   if (N.getOpcode() != ISD::SELECT_CC ||
726       !TLI.isConstTrueVal(N.getOperand(2).getNode()) ||
727       !TLI.isConstFalseVal(N.getOperand(3).getNode()))
728     return false;
729
730   if (TLI.getBooleanContents(N.getValueType()) ==
731       TargetLowering::UndefinedBooleanContent)
732     return false;
733
734   LHS = N.getOperand(0);
735   RHS = N.getOperand(1);
736   CC  = N.getOperand(4);
737   return true;
738 }
739
740 /// Return true if this is a SetCC-equivalent operation with only one use.
741 /// If this is true, it allows the users to invert the operation for free when
742 /// it is profitable to do so.
743 bool DAGCombiner::isOneUseSetCC(SDValue N) const {
744   SDValue N0, N1, N2;
745   if (isSetCCEquivalent(N, N0, N1, N2) && N.getNode()->hasOneUse())
746     return true;
747   return false;
748 }
749
750 /// Returns true if N is a BUILD_VECTOR node whose
751 /// elements are all the same constant or undefined.
752 static bool isConstantSplatVector(SDNode *N, APInt& SplatValue) {
753   BuildVectorSDNode *C = dyn_cast<BuildVectorSDNode>(N);
754   if (!C)
755     return false;
756
757   APInt SplatUndef;
758   unsigned SplatBitSize;
759   bool HasAnyUndefs;
760   EVT EltVT = N->getValueType(0).getVectorElementType();
761   return (C->isConstantSplat(SplatValue, SplatUndef, SplatBitSize,
762                              HasAnyUndefs) &&
763           EltVT.getSizeInBits() >= SplatBitSize);
764 }
765
766 // \brief Returns the SDNode if it is a constant integer BuildVector
767 // or constant integer.
768 static SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N) {
769   if (isa<ConstantSDNode>(N))
770     return N.getNode();
771   if (ISD::isBuildVectorOfConstantSDNodes(N.getNode()))
772     return N.getNode();
773   return nullptr;
774 }
775
776 // \brief Returns the SDNode if it is a constant float BuildVector
777 // or constant float.
778 static SDNode *isConstantFPBuildVectorOrConstantFP(SDValue N) {
779   if (isa<ConstantFPSDNode>(N))
780     return N.getNode();
781   if (ISD::isBuildVectorOfConstantFPSDNodes(N.getNode()))
782     return N.getNode();
783   return nullptr;
784 }
785
786 // \brief Returns the SDNode if it is a constant splat BuildVector or constant
787 // int.
788 static ConstantSDNode *isConstOrConstSplat(SDValue N) {
789   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N))
790     return CN;
791
792   if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(N)) {
793     BitVector UndefElements;
794     ConstantSDNode *CN = BV->getConstantSplatNode(&UndefElements);
795
796     // BuildVectors can truncate their operands. Ignore that case here.
797     // FIXME: We blindly ignore splats which include undef which is overly
798     // pessimistic.
799     if (CN && UndefElements.none() &&
800         CN->getValueType(0) == N.getValueType().getScalarType())
801       return CN;
802   }
803
804   return nullptr;
805 }
806
807 // \brief Returns the SDNode if it is a constant splat BuildVector or constant
808 // float.
809 static ConstantFPSDNode *isConstOrConstSplatFP(SDValue N) {
810   if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N))
811     return CN;
812
813   if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(N)) {
814     BitVector UndefElements;
815     ConstantFPSDNode *CN = BV->getConstantFPSplatNode(&UndefElements);
816
817     if (CN && UndefElements.none())
818       return CN;
819   }
820
821   return nullptr;
822 }
823
824 SDValue DAGCombiner::ReassociateOps(unsigned Opc, SDLoc DL,
825                                     SDValue N0, SDValue N1) {
826   EVT VT = N0.getValueType();
827   if (N0.getOpcode() == Opc) {
828     if (SDNode *L = isConstantIntBuildVectorOrConstantInt(N0.getOperand(1))) {
829       if (SDNode *R = isConstantIntBuildVectorOrConstantInt(N1)) {
830         // reassoc. (op (op x, c1), c2) -> (op x, (op c1, c2))
831         if (SDValue OpNode = DAG.FoldConstantArithmetic(Opc, DL, VT, L, R))
832           return DAG.getNode(Opc, DL, VT, N0.getOperand(0), OpNode);
833         return SDValue();
834       }
835       if (N0.hasOneUse()) {
836         // reassoc. (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one
837         // use
838         SDValue OpNode = DAG.getNode(Opc, SDLoc(N0), VT, N0.getOperand(0), N1);
839         if (!OpNode.getNode())
840           return SDValue();
841         AddToWorklist(OpNode.getNode());
842         return DAG.getNode(Opc, DL, VT, OpNode, N0.getOperand(1));
843       }
844     }
845   }
846
847   if (N1.getOpcode() == Opc) {
848     if (SDNode *R = isConstantIntBuildVectorOrConstantInt(N1.getOperand(1))) {
849       if (SDNode *L = isConstantIntBuildVectorOrConstantInt(N0)) {
850         // reassoc. (op c2, (op x, c1)) -> (op x, (op c1, c2))
851         if (SDValue OpNode = DAG.FoldConstantArithmetic(Opc, DL, VT, R, L))
852           return DAG.getNode(Opc, DL, VT, N1.getOperand(0), OpNode);
853         return SDValue();
854       }
855       if (N1.hasOneUse()) {
856         // reassoc. (op y, (op x, c1)) -> (op (op x, y), c1) iff x+c1 has one
857         // use
858         SDValue OpNode = DAG.getNode(Opc, SDLoc(N0), VT, N1.getOperand(0), N0);
859         if (!OpNode.getNode())
860           return SDValue();
861         AddToWorklist(OpNode.getNode());
862         return DAG.getNode(Opc, DL, VT, OpNode, N1.getOperand(1));
863       }
864     }
865   }
866
867   return SDValue();
868 }
869
870 SDValue DAGCombiner::CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
871                                bool AddTo) {
872   assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
873   ++NodesCombined;
874   DEBUG(dbgs() << "\nReplacing.1 ";
875         N->dump(&DAG);
876         dbgs() << "\nWith: ";
877         To[0].getNode()->dump(&DAG);
878         dbgs() << " and " << NumTo-1 << " other values\n");
879   for (unsigned i = 0, e = NumTo; i != e; ++i)
880     assert((!To[i].getNode() ||
881             N->getValueType(i) == To[i].getValueType()) &&
882            "Cannot combine value to value of different type!");
883
884   WorklistRemover DeadNodes(*this);
885   DAG.ReplaceAllUsesWith(N, To);
886   if (AddTo) {
887     // Push the new nodes and any users onto the worklist
888     for (unsigned i = 0, e = NumTo; i != e; ++i) {
889       if (To[i].getNode()) {
890         AddToWorklist(To[i].getNode());
891         AddUsersToWorklist(To[i].getNode());
892       }
893     }
894   }
895
896   // Finally, if the node is now dead, remove it from the graph.  The node
897   // may not be dead if the replacement process recursively simplified to
898   // something else needing this node.
899   if (N->use_empty())
900     deleteAndRecombine(N);
901   return SDValue(N, 0);
902 }
903
904 void DAGCombiner::
905 CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO) {
906   // Replace all uses.  If any nodes become isomorphic to other nodes and
907   // are deleted, make sure to remove them from our worklist.
908   WorklistRemover DeadNodes(*this);
909   DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New);
910
911   // Push the new node and any (possibly new) users onto the worklist.
912   AddToWorklist(TLO.New.getNode());
913   AddUsersToWorklist(TLO.New.getNode());
914
915   // Finally, if the node is now dead, remove it from the graph.  The node
916   // may not be dead if the replacement process recursively simplified to
917   // something else needing this node.
918   if (TLO.Old.getNode()->use_empty())
919     deleteAndRecombine(TLO.Old.getNode());
920 }
921
922 /// Check the specified integer node value to see if it can be simplified or if
923 /// things it uses can be simplified by bit propagation. If so, return true.
924 bool DAGCombiner::SimplifyDemandedBits(SDValue Op, const APInt &Demanded) {
925   TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
926   APInt KnownZero, KnownOne;
927
928   // XXX-disabled:
929   auto Opcode = Op.getOpcode();
930   if (Opcode == ISD::AND || Opcode == ISD::OR) {
931     auto* Op1 = Op.getOperand(0).getNode();
932     auto* Op2 = Op.getOperand(1).getNode();
933     auto* Op1C = dyn_cast<ConstantSDNode>(Op1);
934     auto* Op2C = dyn_cast<ConstantSDNode>(Op2);
935
936     // and X, 0
937     if (Opcode == ISD::AND && !Op1C && Op2C && Op2C->isNullValue()) {
938       return false;
939     }
940
941     // or (and X, 0), Y
942     if (Opcode == ISD::OR) {
943       if (Op1->getOpcode() == ISD::AND) {
944         auto* Op11 = Op1->getOperand(0).getNode();
945         auto* Op12 = Op1->getOperand(1).getNode();
946         auto* Op11C = dyn_cast<ConstantSDNode>(Op11);
947         auto* Op12C = dyn_cast<ConstantSDNode>(Op12);
948         if (!Op11C && Op12C && Op12C->isNullValue()) {
949           return false;
950         }
951       }
952       if (Op1->getOpcode() == ISD::TRUNCATE) {
953         // or (trunc (and %0, 0)), Y
954         auto* Op11 = Op1->getOperand(0).getNode();
955         if (Op11->getOpcode() == ISD::AND) {
956           auto* Op111 = Op11->getOperand(0).getNode();
957           auto* Op112 = Op11->getOperand(1).getNode();
958           auto* Op111C = dyn_cast<ConstantSDNode>(Op111);
959           auto* Op112C = dyn_cast<ConstantSDNode>(Op112);
960           if (!Op111C && Op112C && Op112C->isNullValue()) {
961             // or (and X, 0), Y
962             return false;
963           }
964         }
965       }
966     }
967   }
968
969   // trunc (and X, 0)
970   if (Opcode == ISD::TRUNCATE) {
971     auto* Op1 = Op.getOperand(0).getNode();
972     if (Op1->getOpcode() == ISD::AND) {
973       auto* Op11 = Op1->getOperand(0).getNode();
974       auto* Op12 = Op1->getOperand(1).getNode();
975       auto* Op11C = dyn_cast<ConstantSDNode>(Op11);
976       auto* Op12C = dyn_cast<ConstantSDNode>(Op12);
977       if (!Op11C && Op12C && Op12C->isNullValue()) {
978         return false;
979       }
980     }
981   }
982
983   if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO))
984     return false;
985
986   // Revisit the node.
987   AddToWorklist(Op.getNode());
988
989   // Replace the old value with the new one.
990   ++NodesCombined;
991   DEBUG(dbgs() << "\nReplacing.2 ";
992         TLO.Old.getNode()->dump(&DAG);
993         dbgs() << "\nWith: ";
994         TLO.New.getNode()->dump(&DAG);
995         dbgs() << '\n');
996
997   CommitTargetLoweringOpt(TLO);
998   return true;
999 }
1000
1001 void DAGCombiner::ReplaceLoadWithPromotedLoad(SDNode *Load, SDNode *ExtLoad) {
1002   SDLoc dl(Load);
1003   EVT VT = Load->getValueType(0);
1004   SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, VT, SDValue(ExtLoad, 0));
1005
1006   DEBUG(dbgs() << "\nReplacing.9 ";
1007         Load->dump(&DAG);
1008         dbgs() << "\nWith: ";
1009         Trunc.getNode()->dump(&DAG);
1010         dbgs() << '\n');
1011   WorklistRemover DeadNodes(*this);
1012   DAG.ReplaceAllUsesOfValueWith(SDValue(Load, 0), Trunc);
1013   DAG.ReplaceAllUsesOfValueWith(SDValue(Load, 1), SDValue(ExtLoad, 1));
1014   deleteAndRecombine(Load);
1015   AddToWorklist(Trunc.getNode());
1016 }
1017
1018 SDValue DAGCombiner::PromoteOperand(SDValue Op, EVT PVT, bool &Replace) {
1019   Replace = false;
1020   SDLoc dl(Op);
1021   if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
1022     EVT MemVT = LD->getMemoryVT();
1023     ISD::LoadExtType ExtType = ISD::isNON_EXTLoad(LD)
1024       ? (TLI.isLoadExtLegal(ISD::ZEXTLOAD, PVT, MemVT) ? ISD::ZEXTLOAD
1025                                                        : ISD::EXTLOAD)
1026       : LD->getExtensionType();
1027     Replace = true;
1028     return DAG.getExtLoad(ExtType, dl, PVT,
1029                           LD->getChain(), LD->getBasePtr(),
1030                           MemVT, LD->getMemOperand());
1031   }
1032
1033   unsigned Opc = Op.getOpcode();
1034   switch (Opc) {
1035   default: break;
1036   case ISD::AssertSext:
1037     return DAG.getNode(ISD::AssertSext, dl, PVT,
1038                        SExtPromoteOperand(Op.getOperand(0), PVT),
1039                        Op.getOperand(1));
1040   case ISD::AssertZext:
1041     return DAG.getNode(ISD::AssertZext, dl, PVT,
1042                        ZExtPromoteOperand(Op.getOperand(0), PVT),
1043                        Op.getOperand(1));
1044   case ISD::Constant: {
1045     unsigned ExtOpc =
1046       Op.getValueType().isByteSized() ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
1047     return DAG.getNode(ExtOpc, dl, PVT, Op);
1048   }
1049   }
1050
1051   if (!TLI.isOperationLegal(ISD::ANY_EXTEND, PVT))
1052     return SDValue();
1053   return DAG.getNode(ISD::ANY_EXTEND, dl, PVT, Op);
1054 }
1055
1056 SDValue DAGCombiner::SExtPromoteOperand(SDValue Op, EVT PVT) {
1057   if (!TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, PVT))
1058     return SDValue();
1059   EVT OldVT = Op.getValueType();
1060   SDLoc dl(Op);
1061   bool Replace = false;
1062   SDValue NewOp = PromoteOperand(Op, PVT, Replace);
1063   if (!NewOp.getNode())
1064     return SDValue();
1065   AddToWorklist(NewOp.getNode());
1066
1067   if (Replace)
1068     ReplaceLoadWithPromotedLoad(Op.getNode(), NewOp.getNode());
1069   return DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, NewOp.getValueType(), NewOp,
1070                      DAG.getValueType(OldVT));
1071 }
1072
1073 SDValue DAGCombiner::ZExtPromoteOperand(SDValue Op, EVT PVT) {
1074   EVT OldVT = Op.getValueType();
1075   SDLoc dl(Op);
1076   bool Replace = false;
1077   SDValue NewOp = PromoteOperand(Op, PVT, Replace);
1078   if (!NewOp.getNode())
1079     return SDValue();
1080   AddToWorklist(NewOp.getNode());
1081
1082   if (Replace)
1083     ReplaceLoadWithPromotedLoad(Op.getNode(), NewOp.getNode());
1084   return DAG.getZeroExtendInReg(NewOp, dl, OldVT);
1085 }
1086
1087 /// Promote the specified integer binary operation if the target indicates it is
1088 /// beneficial. e.g. On x86, it's usually better to promote i16 operations to
1089 /// i32 since i16 instructions are longer.
1090 SDValue DAGCombiner::PromoteIntBinOp(SDValue Op) {
1091   if (!LegalOperations)
1092     return SDValue();
1093
1094   EVT VT = Op.getValueType();
1095   if (VT.isVector() || !VT.isInteger())
1096     return SDValue();
1097
1098   // If operation type is 'undesirable', e.g. i16 on x86, consider
1099   // promoting it.
1100   unsigned Opc = Op.getOpcode();
1101   if (TLI.isTypeDesirableForOp(Opc, VT))
1102     return SDValue();
1103
1104   EVT PVT = VT;
1105   // Consult target whether it is a good idea to promote this operation and
1106   // what's the right type to promote it to.
1107   if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1108     assert(PVT != VT && "Don't know what type to promote to!");
1109
1110     bool Replace0 = false;
1111     SDValue N0 = Op.getOperand(0);
1112     SDValue NN0 = PromoteOperand(N0, PVT, Replace0);
1113     if (!NN0.getNode())
1114       return SDValue();
1115
1116     bool Replace1 = false;
1117     SDValue N1 = Op.getOperand(1);
1118     SDValue NN1;
1119     if (N0 == N1)
1120       NN1 = NN0;
1121     else {
1122       NN1 = PromoteOperand(N1, PVT, Replace1);
1123       if (!NN1.getNode())
1124         return SDValue();
1125     }
1126
1127     AddToWorklist(NN0.getNode());
1128     if (NN1.getNode())
1129       AddToWorklist(NN1.getNode());
1130
1131     if (Replace0)
1132       ReplaceLoadWithPromotedLoad(N0.getNode(), NN0.getNode());
1133     if (Replace1)
1134       ReplaceLoadWithPromotedLoad(N1.getNode(), NN1.getNode());
1135
1136     DEBUG(dbgs() << "\nPromoting ";
1137           Op.getNode()->dump(&DAG));
1138     SDLoc dl(Op);
1139     return DAG.getNode(ISD::TRUNCATE, dl, VT,
1140                        DAG.getNode(Opc, dl, PVT, NN0, NN1));
1141   }
1142   return SDValue();
1143 }
1144
1145 /// Promote the specified integer shift operation if the target indicates it is
1146 /// beneficial. e.g. On x86, it's usually better to promote i16 operations to
1147 /// i32 since i16 instructions are longer.
1148 SDValue DAGCombiner::PromoteIntShiftOp(SDValue Op) {
1149   if (!LegalOperations)
1150     return SDValue();
1151
1152   EVT VT = Op.getValueType();
1153   if (VT.isVector() || !VT.isInteger())
1154     return SDValue();
1155
1156   // If operation type is 'undesirable', e.g. i16 on x86, consider
1157   // promoting it.
1158   unsigned Opc = Op.getOpcode();
1159   if (TLI.isTypeDesirableForOp(Opc, VT))
1160     return SDValue();
1161
1162   EVT PVT = VT;
1163   // Consult target whether it is a good idea to promote this operation and
1164   // what's the right type to promote it to.
1165   if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1166     assert(PVT != VT && "Don't know what type to promote to!");
1167
1168     bool Replace = false;
1169     SDValue N0 = Op.getOperand(0);
1170     if (Opc == ISD::SRA)
1171       N0 = SExtPromoteOperand(Op.getOperand(0), PVT);
1172     else if (Opc == ISD::SRL)
1173       N0 = ZExtPromoteOperand(Op.getOperand(0), PVT);
1174     else
1175       N0 = PromoteOperand(N0, PVT, Replace);
1176     if (!N0.getNode())
1177       return SDValue();
1178
1179     AddToWorklist(N0.getNode());
1180     if (Replace)
1181       ReplaceLoadWithPromotedLoad(Op.getOperand(0).getNode(), N0.getNode());
1182
1183     DEBUG(dbgs() << "\nPromoting ";
1184           Op.getNode()->dump(&DAG));
1185     SDLoc dl(Op);
1186     return DAG.getNode(ISD::TRUNCATE, dl, VT,
1187                        DAG.getNode(Opc, dl, PVT, N0, Op.getOperand(1)));
1188   }
1189   return SDValue();
1190 }
1191
1192 SDValue DAGCombiner::PromoteExtend(SDValue Op) {
1193   if (!LegalOperations)
1194     return SDValue();
1195
1196   EVT VT = Op.getValueType();
1197   if (VT.isVector() || !VT.isInteger())
1198     return SDValue();
1199
1200   // If operation type is 'undesirable', e.g. i16 on x86, consider
1201   // promoting it.
1202   unsigned Opc = Op.getOpcode();
1203   if (TLI.isTypeDesirableForOp(Opc, VT))
1204     return SDValue();
1205
1206   EVT PVT = VT;
1207   // Consult target whether it is a good idea to promote this operation and
1208   // what's the right type to promote it to.
1209   if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1210     assert(PVT != VT && "Don't know what type to promote to!");
1211     // fold (aext (aext x)) -> (aext x)
1212     // fold (aext (zext x)) -> (zext x)
1213     // fold (aext (sext x)) -> (sext x)
1214     DEBUG(dbgs() << "\nPromoting ";
1215           Op.getNode()->dump(&DAG));
1216     return DAG.getNode(Op.getOpcode(), SDLoc(Op), VT, Op.getOperand(0));
1217   }
1218   return SDValue();
1219 }
1220
1221 bool DAGCombiner::PromoteLoad(SDValue Op) {
1222   if (!LegalOperations)
1223     return false;
1224
1225   EVT VT = Op.getValueType();
1226   if (VT.isVector() || !VT.isInteger())
1227     return false;
1228
1229   // If operation type is 'undesirable', e.g. i16 on x86, consider
1230   // promoting it.
1231   unsigned Opc = Op.getOpcode();
1232   if (TLI.isTypeDesirableForOp(Opc, VT))
1233     return false;
1234
1235   EVT PVT = VT;
1236   // Consult target whether it is a good idea to promote this operation and
1237   // what's the right type to promote it to.
1238   if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1239     assert(PVT != VT && "Don't know what type to promote to!");
1240
1241     SDLoc dl(Op);
1242     SDNode *N = Op.getNode();
1243     LoadSDNode *LD = cast<LoadSDNode>(N);
1244     EVT MemVT = LD->getMemoryVT();
1245     ISD::LoadExtType ExtType = ISD::isNON_EXTLoad(LD)
1246       ? (TLI.isLoadExtLegal(ISD::ZEXTLOAD, PVT, MemVT) ? ISD::ZEXTLOAD
1247                                                        : ISD::EXTLOAD)
1248       : LD->getExtensionType();
1249     SDValue NewLD = DAG.getExtLoad(ExtType, dl, PVT,
1250                                    LD->getChain(), LD->getBasePtr(),
1251                                    MemVT, LD->getMemOperand());
1252     SDValue Result = DAG.getNode(ISD::TRUNCATE, dl, VT, NewLD);
1253
1254     DEBUG(dbgs() << "\nPromoting ";
1255           N->dump(&DAG);
1256           dbgs() << "\nTo: ";
1257           Result.getNode()->dump(&DAG);
1258           dbgs() << '\n');
1259     WorklistRemover DeadNodes(*this);
1260     DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result);
1261     DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), NewLD.getValue(1));
1262     deleteAndRecombine(N);
1263     AddToWorklist(Result.getNode());
1264     return true;
1265   }
1266   return false;
1267 }
1268
1269 /// \brief Recursively delete a node which has no uses and any operands for
1270 /// which it is the only use.
1271 ///
1272 /// Note that this both deletes the nodes and removes them from the worklist.
1273 /// It also adds any nodes who have had a user deleted to the worklist as they
1274 /// may now have only one use and subject to other combines.
1275 bool DAGCombiner::recursivelyDeleteUnusedNodes(SDNode *N) {
1276   if (!N->use_empty())
1277     return false;
1278
1279   SmallSetVector<SDNode *, 16> Nodes;
1280   Nodes.insert(N);
1281   do {
1282     N = Nodes.pop_back_val();
1283     if (!N)
1284       continue;
1285
1286     if (N->use_empty()) {
1287       for (const SDValue &ChildN : N->op_values())
1288         Nodes.insert(ChildN.getNode());
1289
1290       removeFromWorklist(N);
1291       DAG.DeleteNode(N);
1292     } else {
1293       AddToWorklist(N);
1294     }
1295   } while (!Nodes.empty());
1296   return true;
1297 }
1298
1299 //===----------------------------------------------------------------------===//
1300 //  Main DAG Combiner implementation
1301 //===----------------------------------------------------------------------===//
1302
1303 void DAGCombiner::Run(CombineLevel AtLevel) {
1304   // set the instance variables, so that the various visit routines may use it.
1305   Level = AtLevel;
1306   LegalOperations = Level >= AfterLegalizeVectorOps;
1307   LegalTypes = Level >= AfterLegalizeTypes;
1308
1309   // Add all the dag nodes to the worklist.
1310   for (SDNode &Node : DAG.allnodes())
1311     AddToWorklist(&Node);
1312
1313   // Create a dummy node (which is not added to allnodes), that adds a reference
1314   // to the root node, preventing it from being deleted, and tracking any
1315   // changes of the root.
1316   HandleSDNode Dummy(DAG.getRoot());
1317
1318   // while the worklist isn't empty, find a node and
1319   // try and combine it.
1320   while (!WorklistMap.empty()) {
1321     SDNode *N;
1322     // The Worklist holds the SDNodes in order, but it may contain null entries.
1323     do {
1324       N = Worklist.pop_back_val();
1325     } while (!N);
1326
1327     bool GoodWorklistEntry = WorklistMap.erase(N);
1328     (void)GoodWorklistEntry;
1329     assert(GoodWorklistEntry &&
1330            "Found a worklist entry without a corresponding map entry!");
1331
1332     // If N has no uses, it is dead.  Make sure to revisit all N's operands once
1333     // N is deleted from the DAG, since they too may now be dead or may have a
1334     // reduced number of uses, allowing other xforms.
1335     if (recursivelyDeleteUnusedNodes(N))
1336       continue;
1337
1338     WorklistRemover DeadNodes(*this);
1339
1340     // If this combine is running after legalizing the DAG, re-legalize any
1341     // nodes pulled off the worklist.
1342     if (Level == AfterLegalizeDAG) {
1343       SmallSetVector<SDNode *, 16> UpdatedNodes;
1344       bool NIsValid = DAG.LegalizeOp(N, UpdatedNodes);
1345
1346       for (SDNode *LN : UpdatedNodes) {
1347         AddToWorklist(LN);
1348         AddUsersToWorklist(LN);
1349       }
1350       if (!NIsValid)
1351         continue;
1352     }
1353
1354     DEBUG(dbgs() << "\nCombining: "; N->dump(&DAG));
1355
1356     // Add any operands of the new node which have not yet been combined to the
1357     // worklist as well. Because the worklist uniques things already, this
1358     // won't repeatedly process the same operand.
1359     CombinedNodes.insert(N);
1360     for (const SDValue &ChildN : N->op_values())
1361       if (!CombinedNodes.count(ChildN.getNode()))
1362         AddToWorklist(ChildN.getNode());
1363
1364     SDValue RV = combine(N);
1365
1366     if (!RV.getNode())
1367       continue;
1368
1369     ++NodesCombined;
1370
1371     // If we get back the same node we passed in, rather than a new node or
1372     // zero, we know that the node must have defined multiple values and
1373     // CombineTo was used.  Since CombineTo takes care of the worklist
1374     // mechanics for us, we have no work to do in this case.
1375     if (RV.getNode() == N)
1376       continue;
1377
1378     assert(N->getOpcode() != ISD::DELETED_NODE &&
1379            RV.getNode()->getOpcode() != ISD::DELETED_NODE &&
1380            "Node was deleted but visit returned new node!");
1381
1382     DEBUG(dbgs() << " ... into: ";
1383           RV.getNode()->dump(&DAG));
1384
1385     // Transfer debug value.
1386     DAG.TransferDbgValues(SDValue(N, 0), RV);
1387     if (N->getNumValues() == RV.getNode()->getNumValues())
1388       DAG.ReplaceAllUsesWith(N, RV.getNode());
1389     else {
1390       assert(N->getValueType(0) == RV.getValueType() &&
1391              N->getNumValues() == 1 && "Type mismatch");
1392       SDValue OpV = RV;
1393       DAG.ReplaceAllUsesWith(N, &OpV);
1394     }
1395
1396     // Push the new node and any users onto the worklist
1397     AddToWorklist(RV.getNode());
1398     AddUsersToWorklist(RV.getNode());
1399
1400     // Finally, if the node is now dead, remove it from the graph.  The node
1401     // may not be dead if the replacement process recursively simplified to
1402     // something else needing this node. This will also take care of adding any
1403     // operands which have lost a user to the worklist.
1404     recursivelyDeleteUnusedNodes(N);
1405   }
1406
1407   // If the root changed (e.g. it was a dead load, update the root).
1408   DAG.setRoot(Dummy.getValue());
1409   DAG.RemoveDeadNodes();
1410 }
1411
1412 SDValue DAGCombiner::visit(SDNode *N) {
1413   switch (N->getOpcode()) {
1414   default: break;
1415   case ISD::TokenFactor:        return visitTokenFactor(N);
1416   case ISD::MERGE_VALUES:       return visitMERGE_VALUES(N);
1417   case ISD::ADD:                return visitADD(N);
1418   case ISD::SUB:                return visitSUB(N);
1419   case ISD::ADDC:               return visitADDC(N);
1420   case ISD::SUBC:               return visitSUBC(N);
1421   case ISD::ADDE:               return visitADDE(N);
1422   case ISD::SUBE:               return visitSUBE(N);
1423   case ISD::MUL:                return visitMUL(N);
1424   case ISD::SDIV:               return visitSDIV(N);
1425   case ISD::UDIV:               return visitUDIV(N);
1426   case ISD::SREM:
1427   case ISD::UREM:               return visitREM(N);
1428   case ISD::MULHU:              return visitMULHU(N);
1429   case ISD::MULHS:              return visitMULHS(N);
1430   case ISD::SMUL_LOHI:          return visitSMUL_LOHI(N);
1431   case ISD::UMUL_LOHI:          return visitUMUL_LOHI(N);
1432   case ISD::SMULO:              return visitSMULO(N);
1433   case ISD::UMULO:              return visitUMULO(N);
1434   case ISD::SMIN:
1435   case ISD::SMAX:
1436   case ISD::UMIN:
1437   case ISD::UMAX:               return visitIMINMAX(N);
1438   case ISD::AND:                return visitAND(N);
1439   case ISD::OR:                 return visitOR(N);
1440   case ISD::XOR:                return visitXOR(N);
1441   case ISD::SHL:                return visitSHL(N);
1442   case ISD::SRA:                return visitSRA(N);
1443   case ISD::SRL:                return visitSRL(N);
1444   case ISD::ROTR:
1445   case ISD::ROTL:               return visitRotate(N);
1446   case ISD::BSWAP:              return visitBSWAP(N);
1447   case ISD::CTLZ:               return visitCTLZ(N);
1448   case ISD::CTLZ_ZERO_UNDEF:    return visitCTLZ_ZERO_UNDEF(N);
1449   case ISD::CTTZ:               return visitCTTZ(N);
1450   case ISD::CTTZ_ZERO_UNDEF:    return visitCTTZ_ZERO_UNDEF(N);
1451   case ISD::CTPOP:              return visitCTPOP(N);
1452   case ISD::SELECT:             return visitSELECT(N);
1453   case ISD::VSELECT:            return visitVSELECT(N);
1454   case ISD::SELECT_CC:          return visitSELECT_CC(N);
1455   case ISD::SETCC:              return visitSETCC(N);
1456   case ISD::SETCCE:             return visitSETCCE(N);
1457   case ISD::SIGN_EXTEND:        return visitSIGN_EXTEND(N);
1458   case ISD::ZERO_EXTEND:        return visitZERO_EXTEND(N);
1459   case ISD::ANY_EXTEND:         return visitANY_EXTEND(N);
1460   case ISD::SIGN_EXTEND_INREG:  return visitSIGN_EXTEND_INREG(N);
1461   case ISD::SIGN_EXTEND_VECTOR_INREG: return visitSIGN_EXTEND_VECTOR_INREG(N);
1462   case ISD::TRUNCATE:           return visitTRUNCATE(N);
1463   case ISD::BITCAST:            return visitBITCAST(N);
1464   case ISD::BUILD_PAIR:         return visitBUILD_PAIR(N);
1465   case ISD::FADD:               return visitFADD(N);
1466   case ISD::FSUB:               return visitFSUB(N);
1467   case ISD::FMUL:               return visitFMUL(N);
1468   case ISD::FMA:                return visitFMA(N);
1469   case ISD::FDIV:               return visitFDIV(N);
1470   case ISD::FREM:               return visitFREM(N);
1471   case ISD::FSQRT:              return visitFSQRT(N);
1472   case ISD::FCOPYSIGN:          return visitFCOPYSIGN(N);
1473   case ISD::SINT_TO_FP:         return visitSINT_TO_FP(N);
1474   case ISD::UINT_TO_FP:         return visitUINT_TO_FP(N);
1475   case ISD::FP_TO_SINT:         return visitFP_TO_SINT(N);
1476   case ISD::FP_TO_UINT:         return visitFP_TO_UINT(N);
1477   case ISD::FP_ROUND:           return visitFP_ROUND(N);
1478   case ISD::FP_ROUND_INREG:     return visitFP_ROUND_INREG(N);
1479   case ISD::FP_EXTEND:          return visitFP_EXTEND(N);
1480   case ISD::FNEG:               return visitFNEG(N);
1481   case ISD::FABS:               return visitFABS(N);
1482   case ISD::FFLOOR:             return visitFFLOOR(N);
1483   case ISD::FMINNUM:            return visitFMINNUM(N);
1484   case ISD::FMAXNUM:            return visitFMAXNUM(N);
1485   case ISD::FCEIL:              return visitFCEIL(N);
1486   case ISD::FTRUNC:             return visitFTRUNC(N);
1487   case ISD::BRCOND:             return visitBRCOND(N);
1488   case ISD::BR_CC:              return visitBR_CC(N);
1489   case ISD::LOAD:               return visitLOAD(N);
1490   case ISD::STORE:              return visitSTORE(N);
1491   case ISD::INSERT_VECTOR_ELT:  return visitINSERT_VECTOR_ELT(N);
1492   case ISD::EXTRACT_VECTOR_ELT: return visitEXTRACT_VECTOR_ELT(N);
1493   case ISD::BUILD_VECTOR:       return visitBUILD_VECTOR(N);
1494   case ISD::CONCAT_VECTORS:     return visitCONCAT_VECTORS(N);
1495   case ISD::EXTRACT_SUBVECTOR:  return visitEXTRACT_SUBVECTOR(N);
1496   case ISD::VECTOR_SHUFFLE:     return visitVECTOR_SHUFFLE(N);
1497   case ISD::SCALAR_TO_VECTOR:   return visitSCALAR_TO_VECTOR(N);
1498   case ISD::INSERT_SUBVECTOR:   return visitINSERT_SUBVECTOR(N);
1499   case ISD::MGATHER:            return visitMGATHER(N);
1500   case ISD::MLOAD:              return visitMLOAD(N);
1501   case ISD::MSCATTER:           return visitMSCATTER(N);
1502   case ISD::MSTORE:             return visitMSTORE(N);
1503   case ISD::FP_TO_FP16:         return visitFP_TO_FP16(N);
1504   case ISD::FP16_TO_FP:         return visitFP16_TO_FP(N);
1505   }
1506   return SDValue();
1507 }
1508
1509 SDValue DAGCombiner::combine(SDNode *N) {
1510   SDValue RV = visit(N);
1511
1512   // If nothing happened, try a target-specific DAG combine.
1513   if (!RV.getNode()) {
1514     assert(N->getOpcode() != ISD::DELETED_NODE &&
1515            "Node was deleted but visit returned NULL!");
1516
1517     if (N->getOpcode() >= ISD::BUILTIN_OP_END ||
1518         TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode())) {
1519
1520       // Expose the DAG combiner to the target combiner impls.
1521       TargetLowering::DAGCombinerInfo
1522         DagCombineInfo(DAG, Level, false, this);
1523
1524       RV = TLI.PerformDAGCombine(N, DagCombineInfo);
1525     }
1526   }
1527
1528   // If nothing happened still, try promoting the operation.
1529   if (!RV.getNode()) {
1530     switch (N->getOpcode()) {
1531     default: break;
1532     case ISD::ADD:
1533     case ISD::SUB:
1534     case ISD::MUL:
1535     case ISD::AND:
1536     case ISD::OR:
1537     case ISD::XOR:
1538       RV = PromoteIntBinOp(SDValue(N, 0));
1539       break;
1540     case ISD::SHL:
1541     case ISD::SRA:
1542     case ISD::SRL:
1543       RV = PromoteIntShiftOp(SDValue(N, 0));
1544       break;
1545     case ISD::SIGN_EXTEND:
1546     case ISD::ZERO_EXTEND:
1547     case ISD::ANY_EXTEND:
1548       RV = PromoteExtend(SDValue(N, 0));
1549       break;
1550     case ISD::LOAD:
1551       if (PromoteLoad(SDValue(N, 0)))
1552         RV = SDValue(N, 0);
1553       break;
1554     }
1555   }
1556
1557   // If N is a commutative binary node, try commuting it to enable more
1558   // sdisel CSE.
1559   if (!RV.getNode() && SelectionDAG::isCommutativeBinOp(N->getOpcode()) &&
1560       N->getNumValues() == 1) {
1561     SDValue N0 = N->getOperand(0);
1562     SDValue N1 = N->getOperand(1);
1563
1564     // Constant operands are canonicalized to RHS.
1565     if (isa<ConstantSDNode>(N0) || !isa<ConstantSDNode>(N1)) {
1566       SDValue Ops[] = {N1, N0};
1567       SDNode *CSENode = DAG.getNodeIfExists(N->getOpcode(), N->getVTList(), Ops,
1568                                             N->getFlags());
1569       if (CSENode)
1570         return SDValue(CSENode, 0);
1571     }
1572   }
1573
1574   return RV;
1575 }
1576
1577 /// Given a node, return its input chain if it has one, otherwise return a null
1578 /// sd operand.
1579 static SDValue getInputChainForNode(SDNode *N) {
1580   if (unsigned NumOps = N->getNumOperands()) {
1581     if (N->getOperand(0).getValueType() == MVT::Other)
1582       return N->getOperand(0);
1583     if (N->getOperand(NumOps-1).getValueType() == MVT::Other)
1584       return N->getOperand(NumOps-1);
1585     for (unsigned i = 1; i < NumOps-1; ++i)
1586       if (N->getOperand(i).getValueType() == MVT::Other)
1587         return N->getOperand(i);
1588   }
1589   return SDValue();
1590 }
1591
1592 SDValue DAGCombiner::visitTokenFactor(SDNode *N) {
1593   // If N has two operands, where one has an input chain equal to the other,
1594   // the 'other' chain is redundant.
1595   if (N->getNumOperands() == 2) {
1596     if (getInputChainForNode(N->getOperand(0).getNode()) == N->getOperand(1))
1597       return N->getOperand(0);
1598     if (getInputChainForNode(N->getOperand(1).getNode()) == N->getOperand(0))
1599       return N->getOperand(1);
1600   }
1601
1602   SmallVector<SDNode *, 8> TFs;     // List of token factors to visit.
1603   SmallVector<SDValue, 8> Ops;    // Ops for replacing token factor.
1604   SmallPtrSet<SDNode*, 16> SeenOps;
1605   bool Changed = false;             // If we should replace this token factor.
1606
1607   // Start out with this token factor.
1608   TFs.push_back(N);
1609
1610   // Iterate through token factors.  The TFs grows when new token factors are
1611   // encountered.
1612   for (unsigned i = 0; i < TFs.size(); ++i) {
1613     SDNode *TF = TFs[i];
1614
1615     // Check each of the operands.
1616     for (const SDValue &Op : TF->op_values()) {
1617
1618       switch (Op.getOpcode()) {
1619       case ISD::EntryToken:
1620         // Entry tokens don't need to be added to the list. They are
1621         // redundant.
1622         Changed = true;
1623         break;
1624
1625       case ISD::TokenFactor:
1626         if (Op.hasOneUse() &&
1627             std::find(TFs.begin(), TFs.end(), Op.getNode()) == TFs.end()) {
1628           // Queue up for processing.
1629           TFs.push_back(Op.getNode());
1630           // Clean up in case the token factor is removed.
1631           AddToWorklist(Op.getNode());
1632           Changed = true;
1633           break;
1634         }
1635         // Fall thru
1636
1637       default:
1638         // Only add if it isn't already in the list.
1639         if (SeenOps.insert(Op.getNode()).second)
1640           Ops.push_back(Op);
1641         else
1642           Changed = true;
1643         break;
1644       }
1645     }
1646   }
1647
1648   SDValue Result;
1649
1650   // If we've changed things around then replace token factor.
1651   if (Changed) {
1652     if (Ops.empty()) {
1653       // The entry token is the only possible outcome.
1654       Result = DAG.getEntryNode();
1655     } else {
1656       // New and improved token factor.
1657       Result = DAG.getNode(ISD::TokenFactor, SDLoc(N), MVT::Other, Ops);
1658     }
1659
1660     // Add users to worklist if AA is enabled, since it may introduce
1661     // a lot of new chained token factors while removing memory deps.
1662     bool UseAA = CombinerAA.getNumOccurrences() > 0 ? CombinerAA
1663       : DAG.getSubtarget().useAA();
1664     return CombineTo(N, Result, UseAA /*add to worklist*/);
1665   }
1666
1667   return Result;
1668 }
1669
1670 /// MERGE_VALUES can always be eliminated.
1671 SDValue DAGCombiner::visitMERGE_VALUES(SDNode *N) {
1672   WorklistRemover DeadNodes(*this);
1673   // Replacing results may cause a different MERGE_VALUES to suddenly
1674   // be CSE'd with N, and carry its uses with it. Iterate until no
1675   // uses remain, to ensure that the node can be safely deleted.
1676   // First add the users of this node to the work list so that they
1677   // can be tried again once they have new operands.
1678   AddUsersToWorklist(N);
1679   do {
1680     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1681       DAG.ReplaceAllUsesOfValueWith(SDValue(N, i), N->getOperand(i));
1682   } while (!N->use_empty());
1683   deleteAndRecombine(N);
1684   return SDValue(N, 0);   // Return N so it doesn't get rechecked!
1685 }
1686
1687 /// If \p N is a ContantSDNode with isOpaque() == false return it casted to a
1688 /// ContantSDNode pointer else nullptr.
1689 static ConstantSDNode *getAsNonOpaqueConstant(SDValue N) {
1690   ConstantSDNode *Const = dyn_cast<ConstantSDNode>(N);
1691   return Const != nullptr && !Const->isOpaque() ? Const : nullptr;
1692 }
1693
1694 SDValue DAGCombiner::visitADD(SDNode *N) {
1695   SDValue N0 = N->getOperand(0);
1696   SDValue N1 = N->getOperand(1);
1697   EVT VT = N0.getValueType();
1698
1699   // fold vector ops
1700   if (VT.isVector()) {
1701     if (SDValue FoldedVOp = SimplifyVBinOp(N))
1702       return FoldedVOp;
1703
1704     // fold (add x, 0) -> x, vector edition
1705     if (ISD::isBuildVectorAllZeros(N1.getNode()))
1706       return N0;
1707     if (ISD::isBuildVectorAllZeros(N0.getNode()))
1708       return N1;
1709   }
1710
1711   // fold (add x, undef) -> undef
1712   if (N0.getOpcode() == ISD::UNDEF)
1713     return N0;
1714   if (N1.getOpcode() == ISD::UNDEF)
1715     return N1;
1716   // fold (add c1, c2) -> c1+c2
1717   ConstantSDNode *N0C = getAsNonOpaqueConstant(N0);
1718   ConstantSDNode *N1C = getAsNonOpaqueConstant(N1);
1719   if (N0C && N1C)
1720     return DAG.FoldConstantArithmetic(ISD::ADD, SDLoc(N), VT, N0C, N1C);
1721   // canonicalize constant to RHS
1722   if (isConstantIntBuildVectorOrConstantInt(N0) &&
1723      !isConstantIntBuildVectorOrConstantInt(N1))
1724     return DAG.getNode(ISD::ADD, SDLoc(N), VT, N1, N0);
1725   // fold (add x, 0) -> x
1726   if (isNullConstant(N1))
1727     return N0;
1728   // fold (add Sym, c) -> Sym+c
1729   if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(N0))
1730     if (!LegalOperations && TLI.isOffsetFoldingLegal(GA) && N1C &&
1731         GA->getOpcode() == ISD::GlobalAddress)
1732       return DAG.getGlobalAddress(GA->getGlobal(), SDLoc(N1C), VT,
1733                                   GA->getOffset() +
1734                                     (uint64_t)N1C->getSExtValue());
1735   // fold ((c1-A)+c2) -> (c1+c2)-A
1736   if (N1C && N0.getOpcode() == ISD::SUB)
1737     if (ConstantSDNode *N0C = getAsNonOpaqueConstant(N0.getOperand(0))) {
1738       SDLoc DL(N);
1739       return DAG.getNode(ISD::SUB, DL, VT,
1740                          DAG.getConstant(N1C->getAPIntValue()+
1741                                          N0C->getAPIntValue(), DL, VT),
1742                          N0.getOperand(1));
1743     }
1744   // reassociate add
1745   if (SDValue RADD = ReassociateOps(ISD::ADD, SDLoc(N), N0, N1))
1746     return RADD;
1747   // fold ((0-A) + B) -> B-A
1748   if (N0.getOpcode() == ISD::SUB && isNullConstant(N0.getOperand(0)))
1749     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N1, N0.getOperand(1));
1750   // fold (A + (0-B)) -> A-B
1751   if (N1.getOpcode() == ISD::SUB && isNullConstant(N1.getOperand(0)))
1752     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N0, N1.getOperand(1));
1753   // fold (A+(B-A)) -> B
1754   if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1))
1755     return N1.getOperand(0);
1756   // fold ((B-A)+A) -> B
1757   if (N0.getOpcode() == ISD::SUB && N1 == N0.getOperand(1))
1758     return N0.getOperand(0);
1759   // fold (A+(B-(A+C))) to (B-C)
1760   if (N1.getOpcode() == ISD::SUB && N1.getOperand(1).getOpcode() == ISD::ADD &&
1761       N0 == N1.getOperand(1).getOperand(0))
1762     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N1.getOperand(0),
1763                        N1.getOperand(1).getOperand(1));
1764   // fold (A+(B-(C+A))) to (B-C)
1765   if (N1.getOpcode() == ISD::SUB && N1.getOperand(1).getOpcode() == ISD::ADD &&
1766       N0 == N1.getOperand(1).getOperand(1))
1767     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N1.getOperand(0),
1768                        N1.getOperand(1).getOperand(0));
1769   // fold (A+((B-A)+or-C)) to (B+or-C)
1770   if ((N1.getOpcode() == ISD::SUB || N1.getOpcode() == ISD::ADD) &&
1771       N1.getOperand(0).getOpcode() == ISD::SUB &&
1772       N0 == N1.getOperand(0).getOperand(1))
1773     return DAG.getNode(N1.getOpcode(), SDLoc(N), VT,
1774                        N1.getOperand(0).getOperand(0), N1.getOperand(1));
1775
1776   // fold (A-B)+(C-D) to (A+C)-(B+D) when A or C is constant
1777   if (N0.getOpcode() == ISD::SUB && N1.getOpcode() == ISD::SUB) {
1778     SDValue N00 = N0.getOperand(0);
1779     SDValue N01 = N0.getOperand(1);
1780     SDValue N10 = N1.getOperand(0);
1781     SDValue N11 = N1.getOperand(1);
1782
1783     if (isa<ConstantSDNode>(N00) || isa<ConstantSDNode>(N10))
1784       return DAG.getNode(ISD::SUB, SDLoc(N), VT,
1785                          DAG.getNode(ISD::ADD, SDLoc(N0), VT, N00, N10),
1786                          DAG.getNode(ISD::ADD, SDLoc(N1), VT, N01, N11));
1787   }
1788
1789   if (!VT.isVector() && SimplifyDemandedBits(SDValue(N, 0)))
1790     return SDValue(N, 0);
1791
1792   // fold (a+b) -> (a|b) iff a and b share no bits.
1793   if ((!LegalOperations || TLI.isOperationLegal(ISD::OR, VT)) &&
1794       VT.isInteger() && !VT.isVector() && DAG.haveNoCommonBitsSet(N0, N1))
1795     return DAG.getNode(ISD::OR, SDLoc(N), VT, N0, N1);
1796
1797   // fold (add x, shl(0 - y, n)) -> sub(x, shl(y, n))
1798   if (N1.getOpcode() == ISD::SHL && N1.getOperand(0).getOpcode() == ISD::SUB &&
1799       isNullConstant(N1.getOperand(0).getOperand(0)))
1800     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N0,
1801                        DAG.getNode(ISD::SHL, SDLoc(N), VT,
1802                                    N1.getOperand(0).getOperand(1),
1803                                    N1.getOperand(1)));
1804   if (N0.getOpcode() == ISD::SHL && N0.getOperand(0).getOpcode() == ISD::SUB &&
1805       isNullConstant(N0.getOperand(0).getOperand(0)))
1806     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N1,
1807                        DAG.getNode(ISD::SHL, SDLoc(N), VT,
1808                                    N0.getOperand(0).getOperand(1),
1809                                    N0.getOperand(1)));
1810
1811   if (N1.getOpcode() == ISD::AND) {
1812     SDValue AndOp0 = N1.getOperand(0);
1813     unsigned NumSignBits = DAG.ComputeNumSignBits(AndOp0);
1814     unsigned DestBits = VT.getScalarType().getSizeInBits();
1815
1816     // (add z, (and (sbbl x, x), 1)) -> (sub z, (sbbl x, x))
1817     // and similar xforms where the inner op is either ~0 or 0.
1818     if (NumSignBits == DestBits && isOneConstant(N1->getOperand(1))) {
1819       SDLoc DL(N);
1820       return DAG.getNode(ISD::SUB, DL, VT, N->getOperand(0), AndOp0);
1821     }
1822   }
1823
1824   // add (sext i1), X -> sub X, (zext i1)
1825   if (N0.getOpcode() == ISD::SIGN_EXTEND &&
1826       N0.getOperand(0).getValueType() == MVT::i1 &&
1827       !TLI.isOperationLegal(ISD::SIGN_EXTEND, MVT::i1)) {
1828     SDLoc DL(N);
1829     SDValue ZExt = DAG.getNode(ISD::ZERO_EXTEND, DL, VT, N0.getOperand(0));
1830     return DAG.getNode(ISD::SUB, DL, VT, N1, ZExt);
1831   }
1832
1833   // add X, (sextinreg Y i1) -> sub X, (and Y 1)
1834   if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
1835     VTSDNode *TN = cast<VTSDNode>(N1.getOperand(1));
1836     if (TN->getVT() == MVT::i1) {
1837       SDLoc DL(N);
1838       SDValue ZExt = DAG.getNode(ISD::AND, DL, VT, N1.getOperand(0),
1839                                  DAG.getConstant(1, DL, VT));
1840       return DAG.getNode(ISD::SUB, DL, VT, N0, ZExt);
1841     }
1842   }
1843
1844   return SDValue();
1845 }
1846
1847 SDValue DAGCombiner::visitADDC(SDNode *N) {
1848   SDValue N0 = N->getOperand(0);
1849   SDValue N1 = N->getOperand(1);
1850   EVT VT = N0.getValueType();
1851
1852   // If the flag result is dead, turn this into an ADD.
1853   if (!N->hasAnyUseOfValue(1))
1854     return CombineTo(N, DAG.getNode(ISD::ADD, SDLoc(N), VT, N0, N1),
1855                      DAG.getNode(ISD::CARRY_FALSE,
1856                                  SDLoc(N), MVT::Glue));
1857
1858   // canonicalize constant to RHS.
1859   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1860   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1861   if (N0C && !N1C)
1862     return DAG.getNode(ISD::ADDC, SDLoc(N), N->getVTList(), N1, N0);
1863
1864   // fold (addc x, 0) -> x + no carry out
1865   if (isNullConstant(N1))
1866     return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE,
1867                                         SDLoc(N), MVT::Glue));
1868
1869   // fold (addc a, b) -> (or a, b), CARRY_FALSE iff a and b share no bits.
1870   APInt LHSZero, LHSOne;
1871   APInt RHSZero, RHSOne;
1872   DAG.computeKnownBits(N0, LHSZero, LHSOne);
1873
1874   if (LHSZero.getBoolValue()) {
1875     DAG.computeKnownBits(N1, RHSZero, RHSOne);
1876
1877     // If all possibly-set bits on the LHS are clear on the RHS, return an OR.
1878     // If all possibly-set bits on the RHS are clear on the LHS, return an OR.
1879     if ((RHSZero & ~LHSZero) == ~LHSZero || (LHSZero & ~RHSZero) == ~RHSZero)
1880       return CombineTo(N, DAG.getNode(ISD::OR, SDLoc(N), VT, N0, N1),
1881                        DAG.getNode(ISD::CARRY_FALSE,
1882                                    SDLoc(N), MVT::Glue));
1883   }
1884
1885   return SDValue();
1886 }
1887
1888 SDValue DAGCombiner::visitADDE(SDNode *N) {
1889   SDValue N0 = N->getOperand(0);
1890   SDValue N1 = N->getOperand(1);
1891   SDValue CarryIn = N->getOperand(2);
1892
1893   // canonicalize constant to RHS
1894   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1895   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1896   if (N0C && !N1C)
1897     return DAG.getNode(ISD::ADDE, SDLoc(N), N->getVTList(),
1898                        N1, N0, CarryIn);
1899
1900   // fold (adde x, y, false) -> (addc x, y)
1901   if (CarryIn.getOpcode() == ISD::CARRY_FALSE)
1902     return DAG.getNode(ISD::ADDC, SDLoc(N), N->getVTList(), N0, N1);
1903
1904   return SDValue();
1905 }
1906
1907 // Since it may not be valid to emit a fold to zero for vector initializers
1908 // check if we can before folding.
1909 static SDValue tryFoldToZero(SDLoc DL, const TargetLowering &TLI, EVT VT,
1910                              SelectionDAG &DAG,
1911                              bool LegalOperations, bool LegalTypes) {
1912   if (!VT.isVector())
1913     return DAG.getConstant(0, DL, VT);
1914   if (!LegalOperations || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT))
1915     return DAG.getConstant(0, DL, VT);
1916   return SDValue();
1917 }
1918
1919 SDValue DAGCombiner::visitSUB(SDNode *N) {
1920   SDValue N0 = N->getOperand(0);
1921   SDValue N1 = N->getOperand(1);
1922   EVT VT = N0.getValueType();
1923
1924   // fold vector ops
1925   if (VT.isVector()) {
1926     if (SDValue FoldedVOp = SimplifyVBinOp(N))
1927       return FoldedVOp;
1928
1929     // fold (sub x, 0) -> x, vector edition
1930     if (ISD::isBuildVectorAllZeros(N1.getNode()))
1931       return N0;
1932   }
1933
1934   // fold (sub x, x) -> 0
1935   // FIXME: Refactor this and xor and other similar operations together.
1936   if (N0 == N1)
1937     return tryFoldToZero(SDLoc(N), TLI, VT, DAG, LegalOperations, LegalTypes);
1938   // fold (sub c1, c2) -> c1-c2
1939   ConstantSDNode *N0C = getAsNonOpaqueConstant(N0);
1940   ConstantSDNode *N1C = getAsNonOpaqueConstant(N1);
1941   if (N0C && N1C)
1942     return DAG.FoldConstantArithmetic(ISD::SUB, SDLoc(N), VT, N0C, N1C);
1943   // fold (sub x, c) -> (add x, -c)
1944   if (N1C) {
1945     SDLoc DL(N);
1946     return DAG.getNode(ISD::ADD, DL, VT, N0,
1947                        DAG.getConstant(-N1C->getAPIntValue(), DL, VT));
1948   }
1949   // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1)
1950   if (isAllOnesConstant(N0))
1951     return DAG.getNode(ISD::XOR, SDLoc(N), VT, N1, N0);
1952   // fold A-(A-B) -> B
1953   if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(0))
1954     return N1.getOperand(1);
1955   // fold (A+B)-A -> B
1956   if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1)
1957     return N0.getOperand(1);
1958   // fold (A+B)-B -> A
1959   if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1)
1960     return N0.getOperand(0);
1961   // fold C2-(A+C1) -> (C2-C1)-A
1962   ConstantSDNode *N1C1 = N1.getOpcode() != ISD::ADD ? nullptr :
1963     dyn_cast<ConstantSDNode>(N1.getOperand(1).getNode());
1964   if (N1.getOpcode() == ISD::ADD && N0C && N1C1) {
1965     SDLoc DL(N);
1966     SDValue NewC = DAG.getConstant(N0C->getAPIntValue() - N1C1->getAPIntValue(),
1967                                    DL, VT);
1968     return DAG.getNode(ISD::SUB, DL, VT, NewC,
1969                        N1.getOperand(0));
1970   }
1971   // fold ((A+(B+or-C))-B) -> A+or-C
1972   if (N0.getOpcode() == ISD::ADD &&
1973       (N0.getOperand(1).getOpcode() == ISD::SUB ||
1974        N0.getOperand(1).getOpcode() == ISD::ADD) &&
1975       N0.getOperand(1).getOperand(0) == N1)
1976     return DAG.getNode(N0.getOperand(1).getOpcode(), SDLoc(N), VT,
1977                        N0.getOperand(0), N0.getOperand(1).getOperand(1));
1978   // fold ((A+(C+B))-B) -> A+C
1979   if (N0.getOpcode() == ISD::ADD &&
1980       N0.getOperand(1).getOpcode() == ISD::ADD &&
1981       N0.getOperand(1).getOperand(1) == N1)
1982     return DAG.getNode(ISD::ADD, SDLoc(N), VT,
1983                        N0.getOperand(0), N0.getOperand(1).getOperand(0));
1984   // fold ((A-(B-C))-C) -> A-B
1985   if (N0.getOpcode() == ISD::SUB &&
1986       N0.getOperand(1).getOpcode() == ISD::SUB &&
1987       N0.getOperand(1).getOperand(1) == N1)
1988     return DAG.getNode(ISD::SUB, SDLoc(N), VT,
1989                        N0.getOperand(0), N0.getOperand(1).getOperand(0));
1990
1991   // If either operand of a sub is undef, the result is undef
1992   if (N0.getOpcode() == ISD::UNDEF)
1993     return N0;
1994   if (N1.getOpcode() == ISD::UNDEF)
1995     return N1;
1996
1997   // If the relocation model supports it, consider symbol offsets.
1998   if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(N0))
1999     if (!LegalOperations && TLI.isOffsetFoldingLegal(GA)) {
2000       // fold (sub Sym, c) -> Sym-c
2001       if (N1C && GA->getOpcode() == ISD::GlobalAddress)
2002         return DAG.getGlobalAddress(GA->getGlobal(), SDLoc(N1C), VT,
2003                                     GA->getOffset() -
2004                                       (uint64_t)N1C->getSExtValue());
2005       // fold (sub Sym+c1, Sym+c2) -> c1-c2
2006       if (GlobalAddressSDNode *GB = dyn_cast<GlobalAddressSDNode>(N1))
2007         if (GA->getGlobal() == GB->getGlobal())
2008           return DAG.getConstant((uint64_t)GA->getOffset() - GB->getOffset(),
2009                                  SDLoc(N), VT);
2010     }
2011
2012   // sub X, (sextinreg Y i1) -> add X, (and Y 1)
2013   if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
2014     VTSDNode *TN = cast<VTSDNode>(N1.getOperand(1));
2015     if (TN->getVT() == MVT::i1) {
2016       SDLoc DL(N);
2017       SDValue ZExt = DAG.getNode(ISD::AND, DL, VT, N1.getOperand(0),
2018                                  DAG.getConstant(1, DL, VT));
2019       return DAG.getNode(ISD::ADD, DL, VT, N0, ZExt);
2020     }
2021   }
2022
2023   return SDValue();
2024 }
2025
2026 SDValue DAGCombiner::visitSUBC(SDNode *N) {
2027   SDValue N0 = N->getOperand(0);
2028   SDValue N1 = N->getOperand(1);
2029   EVT VT = N0.getValueType();
2030   SDLoc DL(N);
2031
2032   // If the flag result is dead, turn this into an SUB.
2033   if (!N->hasAnyUseOfValue(1))
2034     return CombineTo(N, DAG.getNode(ISD::SUB, DL, VT, N0, N1),
2035                      DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
2036
2037   // fold (subc x, x) -> 0 + no borrow
2038   if (N0 == N1)
2039     return CombineTo(N, DAG.getConstant(0, DL, VT),
2040                      DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
2041
2042   // fold (subc x, 0) -> x + no borrow
2043   if (isNullConstant(N1))
2044     return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
2045
2046   // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1) + no borrow
2047   if (isAllOnesConstant(N0))
2048     return CombineTo(N, DAG.getNode(ISD::XOR, DL, VT, N1, N0),
2049                      DAG.getNode(ISD::CARRY_FALSE, DL, MVT::Glue));
2050
2051   return SDValue();
2052 }
2053
2054 SDValue DAGCombiner::visitSUBE(SDNode *N) {
2055   SDValue N0 = N->getOperand(0);
2056   SDValue N1 = N->getOperand(1);
2057   SDValue CarryIn = N->getOperand(2);
2058
2059   // fold (sube x, y, false) -> (subc x, y)
2060   if (CarryIn.getOpcode() == ISD::CARRY_FALSE)
2061     return DAG.getNode(ISD::SUBC, SDLoc(N), N->getVTList(), N0, N1);
2062
2063   return SDValue();
2064 }
2065
2066 SDValue DAGCombiner::visitMUL(SDNode *N) {
2067   SDValue N0 = N->getOperand(0);
2068   SDValue N1 = N->getOperand(1);
2069   EVT VT = N0.getValueType();
2070
2071   // fold (mul x, undef) -> 0
2072   if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
2073     return DAG.getConstant(0, SDLoc(N), VT);
2074
2075   bool N0IsConst = false;
2076   bool N1IsConst = false;
2077   bool N1IsOpaqueConst = false;
2078   bool N0IsOpaqueConst = false;
2079   APInt ConstValue0, ConstValue1;
2080   // fold vector ops
2081   if (VT.isVector()) {
2082     if (SDValue FoldedVOp = SimplifyVBinOp(N))
2083       return FoldedVOp;
2084
2085     N0IsConst = isConstantSplatVector(N0.getNode(), ConstValue0);
2086     N1IsConst = isConstantSplatVector(N1.getNode(), ConstValue1);
2087   } else {
2088     N0IsConst = isa<ConstantSDNode>(N0);
2089     if (N0IsConst) {
2090       ConstValue0 = cast<ConstantSDNode>(N0)->getAPIntValue();
2091       N0IsOpaqueConst = cast<ConstantSDNode>(N0)->isOpaque();
2092     }
2093     N1IsConst = isa<ConstantSDNode>(N1);
2094     if (N1IsConst) {
2095       ConstValue1 = cast<ConstantSDNode>(N1)->getAPIntValue();
2096       N1IsOpaqueConst = cast<ConstantSDNode>(N1)->isOpaque();
2097     }
2098   }
2099
2100   // fold (mul c1, c2) -> c1*c2
2101   if (N0IsConst && N1IsConst && !N0IsOpaqueConst && !N1IsOpaqueConst)
2102     return DAG.FoldConstantArithmetic(ISD::MUL, SDLoc(N), VT,
2103                                       N0.getNode(), N1.getNode());
2104
2105   // canonicalize constant to RHS (vector doesn't have to splat)
2106   if (isConstantIntBuildVectorOrConstantInt(N0) &&
2107      !isConstantIntBuildVectorOrConstantInt(N1))
2108     return DAG.getNode(ISD::MUL, SDLoc(N), VT, N1, N0);
2109   // fold (mul x, 0) -> 0
2110   if (N1IsConst && ConstValue1 == 0)
2111     return N1;
2112   // We require a splat of the entire scalar bit width for non-contiguous
2113   // bit patterns.
2114   bool IsFullSplat =
2115     ConstValue1.getBitWidth() == VT.getScalarType().getSizeInBits();
2116   // fold (mul x, 1) -> x
2117   if (N1IsConst && ConstValue1 == 1 && IsFullSplat)
2118     return N0;
2119   // fold (mul x, -1) -> 0-x
2120   if (N1IsConst && ConstValue1.isAllOnesValue()) {
2121     SDLoc DL(N);
2122     return DAG.getNode(ISD::SUB, DL, VT,
2123                        DAG.getConstant(0, DL, VT), N0);
2124   }
2125   // fold (mul x, (1 << c)) -> x << c
2126   if (N1IsConst && !N1IsOpaqueConst && ConstValue1.isPowerOf2() &&
2127       IsFullSplat) {
2128     SDLoc DL(N);
2129     return DAG.getNode(ISD::SHL, DL, VT, N0,
2130                        DAG.getConstant(ConstValue1.logBase2(), DL,
2131                                        getShiftAmountTy(N0.getValueType())));
2132   }
2133   // fold (mul x, -(1 << c)) -> -(x << c) or (-x) << c
2134   if (N1IsConst && !N1IsOpaqueConst && (-ConstValue1).isPowerOf2() &&
2135       IsFullSplat) {
2136     unsigned Log2Val = (-ConstValue1).logBase2();
2137     SDLoc DL(N);
2138     // FIXME: If the input is something that is easily negated (e.g. a
2139     // single-use add), we should put the negate there.
2140     return DAG.getNode(ISD::SUB, DL, VT,
2141                        DAG.getConstant(0, DL, VT),
2142                        DAG.getNode(ISD::SHL, DL, VT, N0,
2143                             DAG.getConstant(Log2Val, DL,
2144                                       getShiftAmountTy(N0.getValueType()))));
2145   }
2146
2147   APInt Val;
2148   // (mul (shl X, c1), c2) -> (mul X, c2 << c1)
2149   if (N1IsConst && N0.getOpcode() == ISD::SHL &&
2150       (isConstantSplatVector(N0.getOperand(1).getNode(), Val) ||
2151                      isa<ConstantSDNode>(N0.getOperand(1)))) {
2152     SDValue C3 = DAG.getNode(ISD::SHL, SDLoc(N), VT,
2153                              N1, N0.getOperand(1));
2154     AddToWorklist(C3.getNode());
2155     return DAG.getNode(ISD::MUL, SDLoc(N), VT,
2156                        N0.getOperand(0), C3);
2157   }
2158
2159   // Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one
2160   // use.
2161   {
2162     SDValue Sh(nullptr,0), Y(nullptr,0);
2163     // Check for both (mul (shl X, C), Y)  and  (mul Y, (shl X, C)).
2164     if (N0.getOpcode() == ISD::SHL &&
2165         (isConstantSplatVector(N0.getOperand(1).getNode(), Val) ||
2166                        isa<ConstantSDNode>(N0.getOperand(1))) &&
2167         N0.getNode()->hasOneUse()) {
2168       Sh = N0; Y = N1;
2169     } else if (N1.getOpcode() == ISD::SHL &&
2170                isa<ConstantSDNode>(N1.getOperand(1)) &&
2171                N1.getNode()->hasOneUse()) {
2172       Sh = N1; Y = N0;
2173     }
2174
2175     if (Sh.getNode()) {
2176       SDValue Mul = DAG.getNode(ISD::MUL, SDLoc(N), VT,
2177                                 Sh.getOperand(0), Y);
2178       return DAG.getNode(ISD::SHL, SDLoc(N), VT,
2179                          Mul, Sh.getOperand(1));
2180     }
2181   }
2182
2183   // fold (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2)
2184   if (isConstantIntBuildVectorOrConstantInt(N1) &&
2185       N0.getOpcode() == ISD::ADD &&
2186       isConstantIntBuildVectorOrConstantInt(N0.getOperand(1)) &&
2187       isMulAddWithConstProfitable(N, N0, N1))
2188       return DAG.getNode(ISD::ADD, SDLoc(N), VT,
2189                          DAG.getNode(ISD::MUL, SDLoc(N0), VT,
2190                                      N0.getOperand(0), N1),
2191                          DAG.getNode(ISD::MUL, SDLoc(N1), VT,
2192                                      N0.getOperand(1), N1));
2193
2194   // reassociate mul
2195   if (SDValue RMUL = ReassociateOps(ISD::MUL, SDLoc(N), N0, N1))
2196     return RMUL;
2197
2198   return SDValue();
2199 }
2200
2201 /// Return true if divmod libcall is available.
2202 static bool isDivRemLibcallAvailable(SDNode *Node, bool isSigned,
2203                                      const TargetLowering &TLI) {
2204   RTLIB::Libcall LC;
2205   switch (Node->getSimpleValueType(0).SimpleTy) {
2206   default: return false; // No libcall for vector types.
2207   case MVT::i8:   LC= isSigned ? RTLIB::SDIVREM_I8  : RTLIB::UDIVREM_I8;  break;
2208   case MVT::i16:  LC= isSigned ? RTLIB::SDIVREM_I16 : RTLIB::UDIVREM_I16; break;
2209   case MVT::i32:  LC= isSigned ? RTLIB::SDIVREM_I32 : RTLIB::UDIVREM_I32; break;
2210   case MVT::i64:  LC= isSigned ? RTLIB::SDIVREM_I64 : RTLIB::UDIVREM_I64; break;
2211   case MVT::i128: LC= isSigned ? RTLIB::SDIVREM_I128:RTLIB::UDIVREM_I128; break;
2212   }
2213
2214   return TLI.getLibcallName(LC) != nullptr;
2215 }
2216
2217 /// Issue divrem if both quotient and remainder are needed.
2218 SDValue DAGCombiner::useDivRem(SDNode *Node) {
2219   if (Node->use_empty())
2220     return SDValue(); // This is a dead node, leave it alone.
2221
2222   EVT VT = Node->getValueType(0);
2223   if (!TLI.isTypeLegal(VT))
2224     return SDValue();
2225
2226   unsigned Opcode = Node->getOpcode();
2227   bool isSigned = (Opcode == ISD::SDIV) || (Opcode == ISD::SREM);
2228
2229   unsigned DivRemOpc = isSigned ? ISD::SDIVREM : ISD::UDIVREM;
2230   // If DIVREM is going to get expanded into a libcall,
2231   // but there is no libcall available, then don't combine.
2232   if (!TLI.isOperationLegalOrCustom(DivRemOpc, VT) &&
2233       !isDivRemLibcallAvailable(Node, isSigned, TLI))
2234     return SDValue();
2235
2236   // If div is legal, it's better to do the normal expansion
2237   unsigned OtherOpcode = 0;
2238   if ((Opcode == ISD::SDIV) || (Opcode == ISD::UDIV)) {
2239     OtherOpcode = isSigned ? ISD::SREM : ISD::UREM;
2240     if (TLI.isOperationLegalOrCustom(Opcode, VT))
2241       return SDValue();
2242   } else {
2243     OtherOpcode = isSigned ? ISD::SDIV : ISD::UDIV;
2244     if (TLI.isOperationLegalOrCustom(OtherOpcode, VT))
2245       return SDValue();
2246   }
2247
2248   SDValue Op0 = Node->getOperand(0);
2249   SDValue Op1 = Node->getOperand(1);
2250   SDValue combined;
2251   for (SDNode::use_iterator UI = Op0.getNode()->use_begin(),
2252          UE = Op0.getNode()->use_end(); UI != UE; ++UI) {
2253     SDNode *User = *UI;
2254     if (User == Node || User->use_empty())
2255       continue;
2256     // Convert the other matching node(s), too;
2257     // otherwise, the DIVREM may get target-legalized into something
2258     // target-specific that we won't be able to recognize.
2259     unsigned UserOpc = User->getOpcode();
2260     if ((UserOpc == Opcode || UserOpc == OtherOpcode || UserOpc == DivRemOpc) &&
2261         User->getOperand(0) == Op0 &&
2262         User->getOperand(1) == Op1) {
2263       if (!combined) {
2264         if (UserOpc == OtherOpcode) {
2265           SDVTList VTs = DAG.getVTList(VT, VT);
2266           combined = DAG.getNode(DivRemOpc, SDLoc(Node), VTs, Op0, Op1);
2267         } else if (UserOpc == DivRemOpc) {
2268           combined = SDValue(User, 0);
2269         } else {
2270           assert(UserOpc == Opcode);
2271           continue;
2272         }
2273       }
2274       if (UserOpc == ISD::SDIV || UserOpc == ISD::UDIV)
2275         CombineTo(User, combined);
2276       else if (UserOpc == ISD::SREM || UserOpc == ISD::UREM)
2277         CombineTo(User, combined.getValue(1));
2278     }
2279   }
2280   return combined;
2281 }
2282
2283 SDValue DAGCombiner::visitSDIV(SDNode *N) {
2284   SDValue N0 = N->getOperand(0);
2285   SDValue N1 = N->getOperand(1);
2286   EVT VT = N->getValueType(0);
2287
2288   // fold vector ops
2289   if (VT.isVector())
2290     if (SDValue FoldedVOp = SimplifyVBinOp(N))
2291       return FoldedVOp;
2292
2293   SDLoc DL(N);
2294
2295   // fold (sdiv c1, c2) -> c1/c2
2296   ConstantSDNode *N0C = isConstOrConstSplat(N0);
2297   ConstantSDNode *N1C = isConstOrConstSplat(N1);
2298   if (N0C && N1C && !N0C->isOpaque() && !N1C->isOpaque())
2299     return DAG.FoldConstantArithmetic(ISD::SDIV, DL, VT, N0C, N1C);
2300   // fold (sdiv X, 1) -> X
2301   if (N1C && N1C->isOne())
2302     return N0;
2303   // fold (sdiv X, -1) -> 0-X
2304   if (N1C && N1C->isAllOnesValue())
2305     return DAG.getNode(ISD::SUB, DL, VT,
2306                        DAG.getConstant(0, DL, VT), N0);
2307
2308   // If we know the sign bits of both operands are zero, strength reduce to a
2309   // udiv instead.  Handles (X&15) /s 4 -> X&15 >> 2
2310   if (!VT.isVector()) {
2311     if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
2312       return DAG.getNode(ISD::UDIV, DL, N1.getValueType(), N0, N1);
2313   }
2314
2315   // fold (sdiv X, pow2) -> simple ops after legalize
2316   // FIXME: We check for the exact bit here because the generic lowering gives
2317   // better results in that case. The target-specific lowering should learn how
2318   // to handle exact sdivs efficiently.
2319   if (N1C && !N1C->isNullValue() && !N1C->isOpaque() &&
2320       !cast<BinaryWithFlagsSDNode>(N)->Flags.hasExact() &&
2321       (N1C->getAPIntValue().isPowerOf2() ||
2322        (-N1C->getAPIntValue()).isPowerOf2())) {
2323     // Target-specific implementation of sdiv x, pow2.
2324     if (SDValue Res = BuildSDIVPow2(N))
2325       return Res;
2326
2327     unsigned lg2 = N1C->getAPIntValue().countTrailingZeros();
2328
2329     // Splat the sign bit into the register
2330     SDValue SGN =
2331         DAG.getNode(ISD::SRA, DL, VT, N0,
2332                     DAG.getConstant(VT.getScalarSizeInBits() - 1, DL,
2333                                     getShiftAmountTy(N0.getValueType())));
2334     AddToWorklist(SGN.getNode());
2335
2336     // Add (N0 < 0) ? abs2 - 1 : 0;
2337     SDValue SRL =
2338         DAG.getNode(ISD::SRL, DL, VT, SGN,
2339                     DAG.getConstant(VT.getScalarSizeInBits() - lg2, DL,
2340                                     getShiftAmountTy(SGN.getValueType())));
2341     SDValue ADD = DAG.getNode(ISD::ADD, DL, VT, N0, SRL);
2342     AddToWorklist(SRL.getNode());
2343     AddToWorklist(ADD.getNode());    // Divide by pow2
2344     SDValue SRA = DAG.getNode(ISD::SRA, DL, VT, ADD,
2345                   DAG.getConstant(lg2, DL,
2346                                   getShiftAmountTy(ADD.getValueType())));
2347
2348     // If we're dividing by a positive value, we're done.  Otherwise, we must
2349     // negate the result.
2350     if (N1C->getAPIntValue().isNonNegative())
2351       return SRA;
2352
2353     AddToWorklist(SRA.getNode());
2354     return DAG.getNode(ISD::SUB, DL, VT, DAG.getConstant(0, DL, VT), SRA);
2355   }
2356
2357   // If integer divide is expensive and we satisfy the requirements, emit an
2358   // alternate sequence.  Targets may check function attributes for size/speed
2359   // trade-offs.
2360   AttributeSet Attr = DAG.getMachineFunction().getFunction()->getAttributes();
2361   if (N1C && !TLI.isIntDivCheap(N->getValueType(0), Attr))
2362     if (SDValue Op = BuildSDIV(N))
2363       return Op;
2364
2365   // sdiv, srem -> sdivrem
2366   // If the divisor is constant, then return DIVREM only if isIntDivCheap() is true.
2367   // Otherwise, we break the simplification logic in visitREM().
2368   if (!N1C || TLI.isIntDivCheap(N->getValueType(0), Attr))
2369     if (SDValue DivRem = useDivRem(N))
2370         return DivRem;
2371
2372   // undef / X -> 0
2373   if (N0.getOpcode() == ISD::UNDEF)
2374     return DAG.getConstant(0, DL, VT);
2375   // X / undef -> undef
2376   if (N1.getOpcode() == ISD::UNDEF)
2377     return N1;
2378
2379   return SDValue();
2380 }
2381
2382 SDValue DAGCombiner::visitUDIV(SDNode *N) {
2383   SDValue N0 = N->getOperand(0);
2384   SDValue N1 = N->getOperand(1);
2385   EVT VT = N->getValueType(0);
2386
2387   // fold vector ops
2388   if (VT.isVector())
2389     if (SDValue FoldedVOp = SimplifyVBinOp(N))
2390       return FoldedVOp;
2391
2392   SDLoc DL(N);
2393
2394   // fold (udiv c1, c2) -> c1/c2
2395   ConstantSDNode *N0C = isConstOrConstSplat(N0);
2396   ConstantSDNode *N1C = isConstOrConstSplat(N1);
2397   if (N0C && N1C)
2398     if (SDValue Folded = DAG.FoldConstantArithmetic(ISD::UDIV, DL, VT,
2399                                                     N0C, N1C))
2400       return Folded;
2401   // fold (udiv x, (1 << c)) -> x >>u c
2402   if (N1C && !N1C->isOpaque() && N1C->getAPIntValue().isPowerOf2())
2403     return DAG.getNode(ISD::SRL, DL, VT, N0,
2404                        DAG.getConstant(N1C->getAPIntValue().logBase2(), DL,
2405                                        getShiftAmountTy(N0.getValueType())));
2406
2407   // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2
2408   if (N1.getOpcode() == ISD::SHL) {
2409     if (ConstantSDNode *SHC = getAsNonOpaqueConstant(N1.getOperand(0))) {
2410       if (SHC->getAPIntValue().isPowerOf2()) {
2411         EVT ADDVT = N1.getOperand(1).getValueType();
2412         SDValue Add = DAG.getNode(ISD::ADD, DL, ADDVT,
2413                                   N1.getOperand(1),
2414                                   DAG.getConstant(SHC->getAPIntValue()
2415                                                                   .logBase2(),
2416                                                   DL, ADDVT));
2417         AddToWorklist(Add.getNode());
2418         return DAG.getNode(ISD::SRL, DL, VT, N0, Add);
2419       }
2420     }
2421   }
2422
2423   // fold (udiv x, c) -> alternate
2424   AttributeSet Attr = DAG.getMachineFunction().getFunction()->getAttributes();
2425   if (N1C && !TLI.isIntDivCheap(N->getValueType(0), Attr))
2426     if (SDValue Op = BuildUDIV(N))
2427       return Op;
2428
2429   // sdiv, srem -> sdivrem
2430   // If the divisor is constant, then return DIVREM only if isIntDivCheap() is true.
2431   // Otherwise, we break the simplification logic in visitREM().
2432   if (!N1C || TLI.isIntDivCheap(N->getValueType(0), Attr))
2433     if (SDValue DivRem = useDivRem(N))
2434         return DivRem;
2435
2436   // undef / X -> 0
2437   if (N0.getOpcode() == ISD::UNDEF)
2438     return DAG.getConstant(0, DL, VT);
2439   // X / undef -> undef
2440   if (N1.getOpcode() == ISD::UNDEF)
2441     return N1;
2442
2443   return SDValue();
2444 }
2445
2446 // handles ISD::SREM and ISD::UREM
2447 SDValue DAGCombiner::visitREM(SDNode *N) {
2448   unsigned Opcode = N->getOpcode();
2449   SDValue N0 = N->getOperand(0);
2450   SDValue N1 = N->getOperand(1);
2451   EVT VT = N->getValueType(0);
2452   bool isSigned = (Opcode == ISD::SREM);
2453   SDLoc DL(N);
2454
2455   // fold (rem c1, c2) -> c1%c2
2456   ConstantSDNode *N0C = isConstOrConstSplat(N0);
2457   ConstantSDNode *N1C = isConstOrConstSplat(N1);
2458   if (N0C && N1C)
2459     if (SDValue Folded = DAG.FoldConstantArithmetic(Opcode, DL, VT, N0C, N1C))
2460       return Folded;
2461
2462   if (isSigned) {
2463     // If we know the sign bits of both operands are zero, strength reduce to a
2464     // urem instead.  Handles (X & 0x0FFFFFFF) %s 16 -> X&15
2465     if (!VT.isVector()) {
2466       if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
2467         return DAG.getNode(ISD::UREM, DL, VT, N0, N1);
2468     }
2469   } else {
2470     // fold (urem x, pow2) -> (and x, pow2-1)
2471     if (N1C && !N1C->isNullValue() && !N1C->isOpaque() &&
2472         N1C->getAPIntValue().isPowerOf2()) {
2473       return DAG.getNode(ISD::AND, DL, VT, N0,
2474                          DAG.getConstant(N1C->getAPIntValue() - 1, DL, VT));
2475     }
2476     // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1))
2477     if (N1.getOpcode() == ISD::SHL) {
2478       if (ConstantSDNode *SHC = getAsNonOpaqueConstant(N1.getOperand(0))) {
2479         if (SHC->getAPIntValue().isPowerOf2()) {
2480           SDValue Add =
2481             DAG.getNode(ISD::ADD, DL, VT, N1,
2482                  DAG.getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), DL,
2483                                  VT));
2484           AddToWorklist(Add.getNode());
2485           return DAG.getNode(ISD::AND, DL, VT, N0, Add);
2486         }
2487       }
2488     }
2489   }
2490
2491   AttributeSet Attr = DAG.getMachineFunction().getFunction()->getAttributes();
2492
2493   // If X/C can be simplified by the division-by-constant logic, lower
2494   // X%C to the equivalent of X-X/C*C.
2495   // To avoid mangling nodes, this simplification requires that the combine()
2496   // call for the speculative DIV must not cause a DIVREM conversion.  We guard
2497   // against this by skipping the simplification if isIntDivCheap().  When
2498   // div is not cheap, combine will not return a DIVREM.  Regardless,
2499   // checking cheapness here makes sense since the simplification results in
2500   // fatter code.
2501   if (N1C && !N1C->isNullValue() && !TLI.isIntDivCheap(VT, Attr)) {
2502     unsigned DivOpcode = isSigned ? ISD::SDIV : ISD::UDIV;
2503     SDValue Div = DAG.getNode(DivOpcode, DL, VT, N0, N1);
2504     AddToWorklist(Div.getNode());
2505     SDValue OptimizedDiv = combine(Div.getNode());
2506     if (OptimizedDiv.getNode() && OptimizedDiv.getNode() != Div.getNode()) {
2507       assert((OptimizedDiv.getOpcode() != ISD::UDIVREM) &&
2508              (OptimizedDiv.getOpcode() != ISD::SDIVREM));
2509       SDValue Mul = DAG.getNode(ISD::MUL, DL, VT, OptimizedDiv, N1);
2510       SDValue Sub = DAG.getNode(ISD::SUB, DL, VT, N0, Mul);
2511       AddToWorklist(Mul.getNode());
2512       return Sub;
2513     }
2514   }
2515
2516   // sdiv, srem -> sdivrem
2517   if (SDValue DivRem = useDivRem(N))
2518     return DivRem.getValue(1);
2519
2520   // undef % X -> 0
2521   if (N0.getOpcode() == ISD::UNDEF)
2522     return DAG.getConstant(0, DL, VT);
2523   // X % undef -> undef
2524   if (N1.getOpcode() == ISD::UNDEF)
2525     return N1;
2526
2527   return SDValue();
2528 }
2529
2530 SDValue DAGCombiner::visitMULHS(SDNode *N) {
2531   SDValue N0 = N->getOperand(0);
2532   SDValue N1 = N->getOperand(1);
2533   EVT VT = N->getValueType(0);
2534   SDLoc DL(N);
2535
2536   // fold (mulhs x, 0) -> 0
2537   if (isNullConstant(N1))
2538     return N1;
2539   // fold (mulhs x, 1) -> (sra x, size(x)-1)
2540   if (isOneConstant(N1)) {
2541     SDLoc DL(N);
2542     return DAG.getNode(ISD::SRA, DL, N0.getValueType(), N0,
2543                        DAG.getConstant(N0.getValueType().getSizeInBits() - 1,
2544                                        DL,
2545                                        getShiftAmountTy(N0.getValueType())));
2546   }
2547   // fold (mulhs x, undef) -> 0
2548   if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
2549     return DAG.getConstant(0, SDLoc(N), VT);
2550
2551   // If the type twice as wide is legal, transform the mulhs to a wider multiply
2552   // plus a shift.
2553   if (VT.isSimple() && !VT.isVector()) {
2554     MVT Simple = VT.getSimpleVT();
2555     unsigned SimpleSize = Simple.getSizeInBits();
2556     EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
2557     if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
2558       N0 = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N0);
2559       N1 = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N1);
2560       N1 = DAG.getNode(ISD::MUL, DL, NewVT, N0, N1);
2561       N1 = DAG.getNode(ISD::SRL, DL, NewVT, N1,
2562             DAG.getConstant(SimpleSize, DL,
2563                             getShiftAmountTy(N1.getValueType())));
2564       return DAG.getNode(ISD::TRUNCATE, DL, VT, N1);
2565     }
2566   }
2567
2568   return SDValue();
2569 }
2570
2571 SDValue DAGCombiner::visitMULHU(SDNode *N) {
2572   SDValue N0 = N->getOperand(0);
2573   SDValue N1 = N->getOperand(1);
2574   EVT VT = N->getValueType(0);
2575   SDLoc DL(N);
2576
2577   // fold (mulhu x, 0) -> 0
2578   if (isNullConstant(N1))
2579     return N1;
2580   // fold (mulhu x, 1) -> 0
2581   if (isOneConstant(N1))
2582     return DAG.getConstant(0, DL, N0.getValueType());
2583   // fold (mulhu x, undef) -> 0
2584   if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
2585     return DAG.getConstant(0, DL, VT);
2586
2587   // If the type twice as wide is legal, transform the mulhu to a wider multiply
2588   // plus a shift.
2589   if (VT.isSimple() && !VT.isVector()) {
2590     MVT Simple = VT.getSimpleVT();
2591     unsigned SimpleSize = Simple.getSizeInBits();
2592     EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
2593     if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
2594       N0 = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N0);
2595       N1 = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N1);
2596       N1 = DAG.getNode(ISD::MUL, DL, NewVT, N0, N1);
2597       N1 = DAG.getNode(ISD::SRL, DL, NewVT, N1,
2598             DAG.getConstant(SimpleSize, DL,
2599                             getShiftAmountTy(N1.getValueType())));
2600       return DAG.getNode(ISD::TRUNCATE, DL, VT, N1);
2601     }
2602   }
2603
2604   return SDValue();
2605 }
2606
2607 /// Perform optimizations common to nodes that compute two values. LoOp and HiOp
2608 /// give the opcodes for the two computations that are being performed. Return
2609 /// true if a simplification was made.
2610 SDValue DAGCombiner::SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp,
2611                                                 unsigned HiOp) {
2612   // If the high half is not needed, just compute the low half.
2613   bool HiExists = N->hasAnyUseOfValue(1);
2614   if (!HiExists &&
2615       (!LegalOperations ||
2616        TLI.isOperationLegalOrCustom(LoOp, N->getValueType(0)))) {
2617     SDValue Res = DAG.getNode(LoOp, SDLoc(N), N->getValueType(0), N->ops());
2618     return CombineTo(N, Res, Res);
2619   }
2620
2621   // If the low half is not needed, just compute the high half.
2622   bool LoExists = N->hasAnyUseOfValue(0);
2623   if (!LoExists &&
2624       (!LegalOperations ||
2625        TLI.isOperationLegal(HiOp, N->getValueType(1)))) {
2626     SDValue Res = DAG.getNode(HiOp, SDLoc(N), N->getValueType(1), N->ops());
2627     return CombineTo(N, Res, Res);
2628   }
2629
2630   // If both halves are used, return as it is.
2631   if (LoExists && HiExists)
2632     return SDValue();
2633
2634   // If the two computed results can be simplified separately, separate them.
2635   if (LoExists) {
2636     SDValue Lo = DAG.getNode(LoOp, SDLoc(N), N->getValueType(0), N->ops());
2637     AddToWorklist(Lo.getNode());
2638     SDValue LoOpt = combine(Lo.getNode());
2639     if (LoOpt.getNode() && LoOpt.getNode() != Lo.getNode() &&
2640         (!LegalOperations ||
2641          TLI.isOperationLegal(LoOpt.getOpcode(), LoOpt.getValueType())))
2642       return CombineTo(N, LoOpt, LoOpt);
2643   }
2644
2645   if (HiExists) {
2646     SDValue Hi = DAG.getNode(HiOp, SDLoc(N), N->getValueType(1), N->ops());
2647     AddToWorklist(Hi.getNode());
2648     SDValue HiOpt = combine(Hi.getNode());
2649     if (HiOpt.getNode() && HiOpt != Hi &&
2650         (!LegalOperations ||
2651          TLI.isOperationLegal(HiOpt.getOpcode(), HiOpt.getValueType())))
2652       return CombineTo(N, HiOpt, HiOpt);
2653   }
2654
2655   return SDValue();
2656 }
2657
2658 SDValue DAGCombiner::visitSMUL_LOHI(SDNode *N) {
2659   if (SDValue Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHS))
2660     return Res;
2661
2662   EVT VT = N->getValueType(0);
2663   SDLoc DL(N);
2664
2665   // If the type is twice as wide is legal, transform the mulhu to a wider
2666   // multiply plus a shift.
2667   if (VT.isSimple() && !VT.isVector()) {
2668     MVT Simple = VT.getSimpleVT();
2669     unsigned SimpleSize = Simple.getSizeInBits();
2670     EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
2671     if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
2672       SDValue Lo = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N->getOperand(0));
2673       SDValue Hi = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N->getOperand(1));
2674       Lo = DAG.getNode(ISD::MUL, DL, NewVT, Lo, Hi);
2675       // Compute the high part as N1.
2676       Hi = DAG.getNode(ISD::SRL, DL, NewVT, Lo,
2677             DAG.getConstant(SimpleSize, DL,
2678                             getShiftAmountTy(Lo.getValueType())));
2679       Hi = DAG.getNode(ISD::TRUNCATE, DL, VT, Hi);
2680       // Compute the low part as N0.
2681       Lo = DAG.getNode(ISD::TRUNCATE, DL, VT, Lo);
2682       return CombineTo(N, Lo, Hi);
2683     }
2684   }
2685
2686   return SDValue();
2687 }
2688
2689 SDValue DAGCombiner::visitUMUL_LOHI(SDNode *N) {
2690   if (SDValue Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHU))
2691     return Res;
2692
2693   EVT VT = N->getValueType(0);
2694   SDLoc DL(N);
2695
2696   // If the type is twice as wide is legal, transform the mulhu to a wider
2697   // multiply plus a shift.
2698   if (VT.isSimple() && !VT.isVector()) {
2699     MVT Simple = VT.getSimpleVT();
2700     unsigned SimpleSize = Simple.getSizeInBits();
2701     EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
2702     if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
2703       SDValue Lo = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N->getOperand(0));
2704       SDValue Hi = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N->getOperand(1));
2705       Lo = DAG.getNode(ISD::MUL, DL, NewVT, Lo, Hi);
2706       // Compute the high part as N1.
2707       Hi = DAG.getNode(ISD::SRL, DL, NewVT, Lo,
2708             DAG.getConstant(SimpleSize, DL,
2709                             getShiftAmountTy(Lo.getValueType())));
2710       Hi = DAG.getNode(ISD::TRUNCATE, DL, VT, Hi);
2711       // Compute the low part as N0.
2712       Lo = DAG.getNode(ISD::TRUNCATE, DL, VT, Lo);
2713       return CombineTo(N, Lo, Hi);
2714     }
2715   }
2716
2717   return SDValue();
2718 }
2719
2720 SDValue DAGCombiner::visitSMULO(SDNode *N) {
2721   // (smulo x, 2) -> (saddo x, x)
2722   if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(N->getOperand(1)))
2723     if (C2->getAPIntValue() == 2)
2724       return DAG.getNode(ISD::SADDO, SDLoc(N), N->getVTList(),
2725                          N->getOperand(0), N->getOperand(0));
2726
2727   return SDValue();
2728 }
2729
2730 SDValue DAGCombiner::visitUMULO(SDNode *N) {
2731   // (umulo x, 2) -> (uaddo x, x)
2732   if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(N->getOperand(1)))
2733     if (C2->getAPIntValue() == 2)
2734       return DAG.getNode(ISD::UADDO, SDLoc(N), N->getVTList(),
2735                          N->getOperand(0), N->getOperand(0));
2736
2737   return SDValue();
2738 }
2739
2740 SDValue DAGCombiner::visitIMINMAX(SDNode *N) {
2741   SDValue N0 = N->getOperand(0);
2742   SDValue N1 = N->getOperand(1);
2743   EVT VT = N0.getValueType();
2744
2745   // fold vector ops
2746   if (VT.isVector())
2747     if (SDValue FoldedVOp = SimplifyVBinOp(N))
2748       return FoldedVOp;
2749
2750   // fold (add c1, c2) -> c1+c2
2751   ConstantSDNode *N0C = getAsNonOpaqueConstant(N0);
2752   ConstantSDNode *N1C = getAsNonOpaqueConstant(N1);
2753   if (N0C && N1C)
2754     return DAG.FoldConstantArithmetic(N->getOpcode(), SDLoc(N), VT, N0C, N1C);
2755
2756   // canonicalize constant to RHS
2757   if (isConstantIntBuildVectorOrConstantInt(N0) &&
2758      !isConstantIntBuildVectorOrConstantInt(N1))
2759     return DAG.getNode(N->getOpcode(), SDLoc(N), VT, N1, N0);
2760
2761   return SDValue();
2762 }
2763
2764 /// If this is a binary operator with two operands of the same opcode, try to
2765 /// simplify it.
2766 SDValue DAGCombiner::SimplifyBinOpWithSameOpcodeHands(SDNode *N) {
2767   SDValue N0 = N->getOperand(0), N1 = N->getOperand(1);
2768   EVT VT = N0.getValueType();
2769   assert(N0.getOpcode() == N1.getOpcode() && "Bad input!");
2770
2771   // Bail early if none of these transforms apply.
2772   if (N0.getNode()->getNumOperands() == 0) return SDValue();
2773
2774   // For each of OP in AND/OR/XOR:
2775   // fold (OP (zext x), (zext y)) -> (zext (OP x, y))
2776   // fold (OP (sext x), (sext y)) -> (sext (OP x, y))
2777   // fold (OP (aext x), (aext y)) -> (aext (OP x, y))
2778   // fold (OP (bswap x), (bswap y)) -> (bswap (OP x, y))
2779   // fold (OP (trunc x), (trunc y)) -> (trunc (OP x, y)) (if trunc isn't free)
2780   //
2781   // do not sink logical op inside of a vector extend, since it may combine
2782   // into a vsetcc.
2783   EVT Op0VT = N0.getOperand(0).getValueType();
2784   if ((N0.getOpcode() == ISD::ZERO_EXTEND ||
2785        N0.getOpcode() == ISD::SIGN_EXTEND ||
2786        N0.getOpcode() == ISD::BSWAP ||
2787        // Avoid infinite looping with PromoteIntBinOp.
2788        (N0.getOpcode() == ISD::ANY_EXTEND &&
2789         (!LegalTypes || TLI.isTypeDesirableForOp(N->getOpcode(), Op0VT))) ||
2790        (N0.getOpcode() == ISD::TRUNCATE &&
2791         (!TLI.isZExtFree(VT, Op0VT) ||
2792          !TLI.isTruncateFree(Op0VT, VT)) &&
2793         TLI.isTypeLegal(Op0VT))) &&
2794       !VT.isVector() &&
2795       Op0VT == N1.getOperand(0).getValueType() &&
2796       (!LegalOperations || TLI.isOperationLegal(N->getOpcode(), Op0VT))) {
2797     SDValue ORNode = DAG.getNode(N->getOpcode(), SDLoc(N0),
2798                                  N0.getOperand(0).getValueType(),
2799                                  N0.getOperand(0), N1.getOperand(0));
2800     AddToWorklist(ORNode.getNode());
2801     return DAG.getNode(N0.getOpcode(), SDLoc(N), VT, ORNode);
2802   }
2803
2804   // For each of OP in SHL/SRL/SRA/AND...
2805   //   fold (and (OP x, z), (OP y, z)) -> (OP (and x, y), z)
2806   //   fold (or  (OP x, z), (OP y, z)) -> (OP (or  x, y), z)
2807   //   fold (xor (OP x, z), (OP y, z)) -> (OP (xor x, y), z)
2808   if ((N0.getOpcode() == ISD::SHL || N0.getOpcode() == ISD::SRL ||
2809        N0.getOpcode() == ISD::SRA || N0.getOpcode() == ISD::AND) &&
2810       N0.getOperand(1) == N1.getOperand(1)) {
2811     SDValue ORNode = DAG.getNode(N->getOpcode(), SDLoc(N0),
2812                                  N0.getOperand(0).getValueType(),
2813                                  N0.getOperand(0), N1.getOperand(0));
2814     AddToWorklist(ORNode.getNode());
2815     return DAG.getNode(N0.getOpcode(), SDLoc(N), VT,
2816                        ORNode, N0.getOperand(1));
2817   }
2818
2819   // Simplify xor/and/or (bitcast(A), bitcast(B)) -> bitcast(op (A,B))
2820   // Only perform this optimization after type legalization and before
2821   // LegalizeVectorOprs. LegalizeVectorOprs promotes vector operations by
2822   // adding bitcasts. For example (xor v4i32) is promoted to (v2i64), and
2823   // we don't want to undo this promotion.
2824   // We also handle SCALAR_TO_VECTOR because xor/or/and operations are cheaper
2825   // on scalars.
2826   if ((N0.getOpcode() == ISD::BITCAST ||
2827        N0.getOpcode() == ISD::SCALAR_TO_VECTOR) &&
2828       Level == AfterLegalizeTypes) {
2829     SDValue In0 = N0.getOperand(0);
2830     SDValue In1 = N1.getOperand(0);
2831     EVT In0Ty = In0.getValueType();
2832     EVT In1Ty = In1.getValueType();
2833     SDLoc DL(N);
2834     // If both incoming values are integers, and the original types are the
2835     // same.
2836     if (In0Ty.isInteger() && In1Ty.isInteger() && In0Ty == In1Ty) {
2837       SDValue Op = DAG.getNode(N->getOpcode(), DL, In0Ty, In0, In1);
2838       SDValue BC = DAG.getNode(N0.getOpcode(), DL, VT, Op);
2839       AddToWorklist(Op.getNode());
2840       return BC;
2841     }
2842   }
2843
2844   // Xor/and/or are indifferent to the swizzle operation (shuffle of one value).
2845   // Simplify xor/and/or (shuff(A), shuff(B)) -> shuff(op (A,B))
2846   // If both shuffles use the same mask, and both shuffle within a single
2847   // vector, then it is worthwhile to move the swizzle after the operation.
2848   // The type-legalizer generates this pattern when loading illegal
2849   // vector types from memory. In many cases this allows additional shuffle
2850   // optimizations.
2851   // There are other cases where moving the shuffle after the xor/and/or
2852   // is profitable even if shuffles don't perform a swizzle.
2853   // If both shuffles use the same mask, and both shuffles have the same first
2854   // or second operand, then it might still be profitable to move the shuffle
2855   // after the xor/and/or operation.
2856   if (N0.getOpcode() == ISD::VECTOR_SHUFFLE && Level < AfterLegalizeDAG) {
2857     ShuffleVectorSDNode *SVN0 = cast<ShuffleVectorSDNode>(N0);
2858     ShuffleVectorSDNode *SVN1 = cast<ShuffleVectorSDNode>(N1);
2859
2860     assert(N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType() &&
2861            "Inputs to shuffles are not the same type");
2862
2863     // Check that both shuffles use the same mask. The masks are known to be of
2864     // the same length because the result vector type is the same.
2865     // Check also that shuffles have only one use to avoid introducing extra
2866     // instructions.
2867     if (SVN0->hasOneUse() && SVN1->hasOneUse() &&
2868         SVN0->getMask().equals(SVN1->getMask())) {
2869       SDValue ShOp = N0->getOperand(1);
2870
2871       // Don't try to fold this node if it requires introducing a
2872       // build vector of all zeros that might be illegal at this stage.
2873       if (N->getOpcode() == ISD::XOR && ShOp.getOpcode() != ISD::UNDEF) {
2874         if (!LegalTypes)
2875           ShOp = DAG.getConstant(0, SDLoc(N), VT);
2876         else
2877           ShOp = SDValue();
2878       }
2879
2880       // (AND (shuf (A, C), shuf (B, C)) -> shuf (AND (A, B), C)
2881       // (OR  (shuf (A, C), shuf (B, C)) -> shuf (OR  (A, B), C)
2882       // (XOR (shuf (A, C), shuf (B, C)) -> shuf (XOR (A, B), V_0)
2883       if (N0.getOperand(1) == N1.getOperand(1) && ShOp.getNode()) {
2884         SDValue NewNode = DAG.getNode(N->getOpcode(), SDLoc(N), VT,
2885                                       N0->getOperand(0), N1->getOperand(0));
2886         AddToWorklist(NewNode.getNode());
2887         return DAG.getVectorShuffle(VT, SDLoc(N), NewNode, ShOp,
2888                                     &SVN0->getMask()[0]);
2889       }
2890
2891       // Don't try to fold this node if it requires introducing a
2892       // build vector of all zeros that might be illegal at this stage.
2893       ShOp = N0->getOperand(0);
2894       if (N->getOpcode() == ISD::XOR && ShOp.getOpcode() != ISD::UNDEF) {
2895         if (!LegalTypes)
2896           ShOp = DAG.getConstant(0, SDLoc(N), VT);
2897         else
2898           ShOp = SDValue();
2899       }
2900
2901       // (AND (shuf (C, A), shuf (C, B)) -> shuf (C, AND (A, B))
2902       // (OR  (shuf (C, A), shuf (C, B)) -> shuf (C, OR  (A, B))
2903       // (XOR (shuf (C, A), shuf (C, B)) -> shuf (V_0, XOR (A, B))
2904       if (N0->getOperand(0) == N1->getOperand(0) && ShOp.getNode()) {
2905         SDValue NewNode = DAG.getNode(N->getOpcode(), SDLoc(N), VT,
2906                                       N0->getOperand(1), N1->getOperand(1));
2907         AddToWorklist(NewNode.getNode());
2908         return DAG.getVectorShuffle(VT, SDLoc(N), ShOp, NewNode,
2909                                     &SVN0->getMask()[0]);
2910       }
2911     }
2912   }
2913
2914   return SDValue();
2915 }
2916
2917 /// This contains all DAGCombine rules which reduce two values combined by
2918 /// an And operation to a single value. This makes them reusable in the context
2919 /// of visitSELECT(). Rules involving constants are not included as
2920 /// visitSELECT() already handles those cases.
2921 SDValue DAGCombiner::visitANDLike(SDValue N0, SDValue N1,
2922                                   SDNode *LocReference) {
2923   EVT VT = N1.getValueType();
2924
2925   // fold (and x, undef) -> 0
2926   if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
2927     return DAG.getConstant(0, SDLoc(LocReference), VT);
2928   // fold (and (setcc x), (setcc y)) -> (setcc (and x, y))
2929   SDValue LL, LR, RL, RR, CC0, CC1;
2930   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
2931     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
2932     ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
2933
2934     if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
2935         LL.getValueType().isInteger()) {
2936       // fold (and (seteq X, 0), (seteq Y, 0)) -> (seteq (or X, Y), 0)
2937       if (isNullConstant(LR) && Op1 == ISD::SETEQ) {
2938         SDValue ORNode = DAG.getNode(ISD::OR, SDLoc(N0),
2939                                      LR.getValueType(), LL, RL);
2940         AddToWorklist(ORNode.getNode());
2941         return DAG.getSetCC(SDLoc(LocReference), VT, ORNode, LR, Op1);
2942       }
2943       if (isAllOnesConstant(LR)) {
2944         // fold (and (seteq X, -1), (seteq Y, -1)) -> (seteq (and X, Y), -1)
2945         if (Op1 == ISD::SETEQ) {
2946           SDValue ANDNode = DAG.getNode(ISD::AND, SDLoc(N0),
2947                                         LR.getValueType(), LL, RL);
2948           AddToWorklist(ANDNode.getNode());
2949           return DAG.getSetCC(SDLoc(LocReference), VT, ANDNode, LR, Op1);
2950         }
2951         // fold (and (setgt X, -1), (setgt Y, -1)) -> (setgt (or X, Y), -1)
2952         if (Op1 == ISD::SETGT) {
2953           SDValue ORNode = DAG.getNode(ISD::OR, SDLoc(N0),
2954                                        LR.getValueType(), LL, RL);
2955           AddToWorklist(ORNode.getNode());
2956           return DAG.getSetCC(SDLoc(LocReference), VT, ORNode, LR, Op1);
2957         }
2958       }
2959     }
2960     // Simplify (and (setne X, 0), (setne X, -1)) -> (setuge (add X, 1), 2)
2961     if (LL == RL && isa<ConstantSDNode>(LR) && isa<ConstantSDNode>(RR) &&
2962         Op0 == Op1 && LL.getValueType().isInteger() &&
2963       Op0 == ISD::SETNE && ((isNullConstant(LR) && isAllOnesConstant(RR)) ||
2964                             (isAllOnesConstant(LR) && isNullConstant(RR)))) {
2965       SDLoc DL(N0);
2966       SDValue ADDNode = DAG.getNode(ISD::ADD, DL, LL.getValueType(),
2967                                     LL, DAG.getConstant(1, DL,
2968                                                         LL.getValueType()));
2969       AddToWorklist(ADDNode.getNode());
2970       return DAG.getSetCC(SDLoc(LocReference), VT, ADDNode,
2971                           DAG.getConstant(2, DL, LL.getValueType()),
2972                           ISD::SETUGE);
2973     }
2974     // canonicalize equivalent to ll == rl
2975     if (LL == RR && LR == RL) {
2976       Op1 = ISD::getSetCCSwappedOperands(Op1);
2977       std::swap(RL, RR);
2978     }
2979     if (LL == RL && LR == RR) {
2980       bool isInteger = LL.getValueType().isInteger();
2981       ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger);
2982       if (Result != ISD::SETCC_INVALID &&
2983           (!LegalOperations ||
2984            (TLI.isCondCodeLegal(Result, LL.getSimpleValueType()) &&
2985             TLI.isOperationLegal(ISD::SETCC, LL.getValueType())))) {
2986         EVT CCVT = getSetCCResultType(LL.getValueType());
2987         if (N0.getValueType() == CCVT ||
2988             (!LegalOperations && N0.getValueType() == MVT::i1))
2989           return DAG.getSetCC(SDLoc(LocReference), N0.getValueType(),
2990                               LL, LR, Result);
2991       }
2992     }
2993   }
2994
2995   if (N0.getOpcode() == ISD::ADD && N1.getOpcode() == ISD::SRL &&
2996       VT.getSizeInBits() <= 64) {
2997     if (ConstantSDNode *ADDI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
2998       APInt ADDC = ADDI->getAPIntValue();
2999       if (!TLI.isLegalAddImmediate(ADDC.getSExtValue())) {
3000         // Look for (and (add x, c1), (lshr y, c2)). If C1 wasn't a legal
3001         // immediate for an add, but it is legal if its top c2 bits are set,
3002         // transform the ADD so the immediate doesn't need to be materialized
3003         // in a register.
3004         if (ConstantSDNode *SRLI = dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
3005           APInt Mask = APInt::getHighBitsSet(VT.getSizeInBits(),
3006                                              SRLI->getZExtValue());
3007           if (DAG.MaskedValueIsZero(N0.getOperand(1), Mask)) {
3008             ADDC |= Mask;
3009             if (TLI.isLegalAddImmediate(ADDC.getSExtValue())) {
3010               SDLoc DL(N0);
3011               SDValue NewAdd =
3012                 DAG.getNode(ISD::ADD, DL, VT,
3013                             N0.getOperand(0), DAG.getConstant(ADDC, DL, VT));
3014               CombineTo(N0.getNode(), NewAdd);
3015               // Return N so it doesn't get rechecked!
3016               return SDValue(LocReference, 0);
3017             }
3018           }
3019         }
3020       }
3021     }
3022   }
3023
3024   return SDValue();
3025 }
3026
3027 bool DAGCombiner::isAndLoadExtLoad(ConstantSDNode *AndC, LoadSDNode *LoadN,
3028                                    EVT LoadResultTy, EVT &ExtVT, EVT &LoadedVT,
3029                                    bool &NarrowLoad) {
3030   uint32_t ActiveBits = AndC->getAPIntValue().getActiveBits();
3031
3032   if (ActiveBits == 0 || !APIntOps::isMask(ActiveBits, AndC->getAPIntValue()))
3033     return false;
3034
3035   ExtVT = EVT::getIntegerVT(*DAG.getContext(), ActiveBits);
3036   LoadedVT = LoadN->getMemoryVT();
3037
3038   if (ExtVT == LoadedVT &&
3039       (!LegalOperations ||
3040        TLI.isLoadExtLegal(ISD::ZEXTLOAD, LoadResultTy, ExtVT))) {
3041     // ZEXTLOAD will match without needing to change the size of the value being
3042     // loaded.
3043     NarrowLoad = false;
3044     return true;
3045   }
3046
3047   // Do not change the width of a volatile load.
3048   if (LoadN->isVolatile())
3049     return false;
3050
3051   // Do not generate loads of non-round integer types since these can
3052   // be expensive (and would be wrong if the type is not byte sized).
3053   if (!LoadedVT.bitsGT(ExtVT) || !ExtVT.isRound())
3054     return false;
3055
3056   if (LegalOperations &&
3057       !TLI.isLoadExtLegal(ISD::ZEXTLOAD, LoadResultTy, ExtVT))
3058     return false;
3059
3060   if (!TLI.shouldReduceLoadWidth(LoadN, ISD::ZEXTLOAD, ExtVT))
3061     return false;
3062
3063   NarrowLoad = true;
3064   return true;
3065 }
3066
3067 SDValue DAGCombiner::visitAND(SDNode *N) {
3068   SDValue N0 = N->getOperand(0);
3069   SDValue N1 = N->getOperand(1);
3070   EVT VT = N1.getValueType();
3071
3072   // fold vector ops
3073   if (VT.isVector()) {
3074     if (SDValue FoldedVOp = SimplifyVBinOp(N))
3075       return FoldedVOp;
3076
3077     // fold (and x, 0) -> 0, vector edition
3078     if (ISD::isBuildVectorAllZeros(N0.getNode()))
3079       // do not return N0, because undef node may exist in N0
3080       return DAG.getConstant(
3081           APInt::getNullValue(
3082               N0.getValueType().getScalarType().getSizeInBits()),
3083           SDLoc(N), N0.getValueType());
3084     if (ISD::isBuildVectorAllZeros(N1.getNode()))
3085       // do not return N1, because undef node may exist in N1
3086       return DAG.getConstant(
3087           APInt::getNullValue(
3088               N1.getValueType().getScalarType().getSizeInBits()),
3089           SDLoc(N), N1.getValueType());
3090
3091     // fold (and x, -1) -> x, vector edition
3092     if (ISD::isBuildVectorAllOnes(N0.getNode()))
3093       return N1;
3094     if (ISD::isBuildVectorAllOnes(N1.getNode()))
3095       return N0;
3096   }
3097
3098   // fold (and c1, c2) -> c1&c2
3099   ConstantSDNode *N0C = getAsNonOpaqueConstant(N0);
3100   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3101
3102   // XXX-disabled: (and x, 0) should not be folded.
3103   // (and (and x, 0), y) shouldn't either.
3104   if (!N0C && N1C && N1C->isNullValue()) {
3105     return SDValue();
3106   }
3107   if (!N0C) {
3108     if (N0.getOpcode() == ISD::AND) {
3109       auto* N01 = N0.getOperand(1).getNode();
3110       auto* N01C = dyn_cast<ConstantSDNode>(N01);
3111       if (N01C && N01C->isNullValue()) {
3112         return SDValue();
3113       }
3114     }
3115   }
3116
3117   if (N0C && N1C && !N1C->isOpaque())
3118     return DAG.FoldConstantArithmetic(ISD::AND, SDLoc(N), VT, N0C, N1C);
3119   // canonicalize constant to RHS
3120   if (isConstantIntBuildVectorOrConstantInt(N0) &&
3121      !isConstantIntBuildVectorOrConstantInt(N1))
3122     return DAG.getNode(ISD::AND, SDLoc(N), VT, N1, N0);
3123   // fold (and x, -1) -> x
3124   if (isAllOnesConstant(N1))
3125     return N0;
3126   // if (and x, c) is known to be zero, return 0
3127   unsigned BitWidth = VT.getScalarType().getSizeInBits();
3128   if (N1C && DAG.MaskedValueIsZero(SDValue(N, 0),
3129                                    APInt::getAllOnesValue(BitWidth)))
3130     return DAG.getConstant(0, SDLoc(N), VT);
3131   // reassociate and
3132   if (SDValue RAND = ReassociateOps(ISD::AND, SDLoc(N), N0, N1))
3133     return RAND;
3134   // fold (and (or x, C), D) -> D if (C & D) == D
3135   if (N1C && N0.getOpcode() == ISD::OR)
3136     if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
3137       if ((ORI->getAPIntValue() & N1C->getAPIntValue()) == N1C->getAPIntValue())
3138         return N1;
3139   // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits.
3140   if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) {
3141     SDValue N0Op0 = N0.getOperand(0);
3142     APInt Mask = ~N1C->getAPIntValue();
3143     Mask = Mask.trunc(N0Op0.getValueSizeInBits());
3144     if (DAG.MaskedValueIsZero(N0Op0, Mask)) {
3145       SDValue Zext = DAG.getNode(ISD::ZERO_EXTEND, SDLoc(N),
3146                                  N0.getValueType(), N0Op0);
3147
3148       // Replace uses of the AND with uses of the Zero extend node.
3149       CombineTo(N, Zext);
3150
3151       // We actually want to replace all uses of the any_extend with the
3152       // zero_extend, to avoid duplicating things.  This will later cause this
3153       // AND to be folded.
3154       CombineTo(N0.getNode(), Zext);
3155       return SDValue(N, 0);   // Return N so it doesn't get rechecked!
3156     }
3157   }
3158   // similarly fold (and (X (load ([non_ext|any_ext|zero_ext] V))), c) ->
3159   // (X (load ([non_ext|zero_ext] V))) if 'and' only clears top bits which must
3160   // already be zero by virtue of the width of the base type of the load.
3161   //
3162   // the 'X' node here can either be nothing or an extract_vector_elt to catch
3163   // more cases.
3164   if ((N0.getOpcode() == ISD::EXTRACT_VECTOR_ELT &&
3165        N0.getOperand(0).getOpcode() == ISD::LOAD) ||
3166       N0.getOpcode() == ISD::LOAD) {
3167     LoadSDNode *Load = cast<LoadSDNode>( (N0.getOpcode() == ISD::LOAD) ?
3168                                          N0 : N0.getOperand(0) );
3169
3170     // Get the constant (if applicable) the zero'th operand is being ANDed with.
3171     // This can be a pure constant or a vector splat, in which case we treat the
3172     // vector as a scalar and use the splat value.
3173     APInt Constant = APInt::getNullValue(1);
3174     if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
3175       Constant = C->getAPIntValue();
3176     } else if (BuildVectorSDNode *Vector = dyn_cast<BuildVectorSDNode>(N1)) {
3177       APInt SplatValue, SplatUndef;
3178       unsigned SplatBitSize;
3179       bool HasAnyUndefs;
3180       bool IsSplat = Vector->isConstantSplat(SplatValue, SplatUndef,
3181                                              SplatBitSize, HasAnyUndefs);
3182       if (IsSplat) {
3183         // Undef bits can contribute to a possible optimisation if set, so
3184         // set them.
3185         SplatValue |= SplatUndef;
3186
3187         // The splat value may be something like "0x00FFFFFF", which means 0 for
3188         // the first vector value and FF for the rest, repeating. We need a mask
3189         // that will apply equally to all members of the vector, so AND all the
3190         // lanes of the constant together.
3191         EVT VT = Vector->getValueType(0);
3192         unsigned BitWidth = VT.getVectorElementType().getSizeInBits();
3193
3194         // If the splat value has been compressed to a bitlength lower
3195         // than the size of the vector lane, we need to re-expand it to
3196         // the lane size.
3197         if (BitWidth > SplatBitSize)
3198           for (SplatValue = SplatValue.zextOrTrunc(BitWidth);
3199                SplatBitSize < BitWidth;
3200                SplatBitSize = SplatBitSize * 2)
3201             SplatValue |= SplatValue.shl(SplatBitSize);
3202
3203         // Make sure that variable 'Constant' is only set if 'SplatBitSize' is a
3204         // multiple of 'BitWidth'. Otherwise, we could propagate a wrong value.
3205         if (SplatBitSize % BitWidth == 0) {
3206           Constant = APInt::getAllOnesValue(BitWidth);
3207           for (unsigned i = 0, n = SplatBitSize/BitWidth; i < n; ++i)
3208             Constant &= SplatValue.lshr(i*BitWidth).zextOrTrunc(BitWidth);
3209         }
3210       }
3211     }
3212
3213     // If we want to change an EXTLOAD to a ZEXTLOAD, ensure a ZEXTLOAD is
3214     // actually legal and isn't going to get expanded, else this is a false
3215     // optimisation.
3216     bool CanZextLoadProfitably = TLI.isLoadExtLegal(ISD::ZEXTLOAD,
3217                                                     Load->getValueType(0),
3218                                                     Load->getMemoryVT());
3219
3220     // Resize the constant to the same size as the original memory access before
3221     // extension. If it is still the AllOnesValue then this AND is completely
3222     // unneeded.
3223     Constant =
3224       Constant.zextOrTrunc(Load->getMemoryVT().getScalarType().getSizeInBits());
3225
3226     bool B;
3227     switch (Load->getExtensionType()) {
3228     default: B = false; break;
3229     case ISD::EXTLOAD: B = CanZextLoadProfitably; break;
3230     case ISD::ZEXTLOAD:
3231     case ISD::NON_EXTLOAD: B = true; break;
3232     }
3233
3234     if (B && Constant.isAllOnesValue()) {
3235       // If the load type was an EXTLOAD, convert to ZEXTLOAD in order to
3236       // preserve semantics once we get rid of the AND.
3237       SDValue NewLoad(Load, 0);
3238       if (Load->getExtensionType() == ISD::EXTLOAD) {
3239         NewLoad = DAG.getLoad(Load->getAddressingMode(), ISD::ZEXTLOAD,
3240                               Load->getValueType(0), SDLoc(Load),
3241                               Load->getChain(), Load->getBasePtr(),
3242                               Load->getOffset(), Load->getMemoryVT(),
3243                               Load->getMemOperand());
3244         // Replace uses of the EXTLOAD with the new ZEXTLOAD.
3245         if (Load->getNumValues() == 3) {
3246           // PRE/POST_INC loads have 3 values.
3247           SDValue To[] = { NewLoad.getValue(0), NewLoad.getValue(1),
3248                            NewLoad.getValue(2) };
3249           CombineTo(Load, To, 3, true);
3250         } else {
3251           CombineTo(Load, NewLoad.getValue(0), NewLoad.getValue(1));
3252         }
3253       }
3254
3255       // Fold the AND away, taking care not to fold to the old load node if we
3256       // replaced it.
3257       CombineTo(N, (N0.getNode() == Load) ? NewLoad : N0);
3258
3259       return SDValue(N, 0); // Return N so it doesn't get rechecked!
3260     }
3261   }
3262
3263   // fold (and (load x), 255) -> (zextload x, i8)
3264   // fold (and (extload x, i16), 255) -> (zextload x, i8)
3265   // fold (and (any_ext (extload x, i16)), 255) -> (zextload x, i8)
3266   if (N1C && (N0.getOpcode() == ISD::LOAD ||
3267               (N0.getOpcode() == ISD::ANY_EXTEND &&
3268                N0.getOperand(0).getOpcode() == ISD::LOAD))) {
3269     bool HasAnyExt = N0.getOpcode() == ISD::ANY_EXTEND;
3270     LoadSDNode *LN0 = HasAnyExt
3271       ? cast<LoadSDNode>(N0.getOperand(0))
3272       : cast<LoadSDNode>(N0);
3273     if (LN0->getExtensionType() != ISD::SEXTLOAD &&
3274         LN0->isUnindexed() && N0.hasOneUse() && SDValue(LN0, 0).hasOneUse()) {
3275       auto NarrowLoad = false;
3276       EVT LoadResultTy = HasAnyExt ? LN0->getValueType(0) : VT;
3277       EVT ExtVT, LoadedVT;
3278       if (isAndLoadExtLoad(N1C, LN0, LoadResultTy, ExtVT, LoadedVT,
3279                            NarrowLoad)) {
3280         if (!NarrowLoad) {
3281           SDValue NewLoad =
3282             DAG.getExtLoad(ISD::ZEXTLOAD, SDLoc(LN0), LoadResultTy,
3283                            LN0->getChain(), LN0->getBasePtr(), ExtVT,
3284                            LN0->getMemOperand());
3285           AddToWorklist(N);
3286           CombineTo(LN0, NewLoad, NewLoad.getValue(1));
3287           return SDValue(N, 0);   // Return N so it doesn't get rechecked!
3288         } else {
3289           EVT PtrType = LN0->getOperand(1).getValueType();
3290
3291           unsigned Alignment = LN0->getAlignment();
3292           SDValue NewPtr = LN0->getBasePtr();
3293
3294           // For big endian targets, we need to add an offset to the pointer
3295           // to load the correct bytes.  For little endian systems, we merely
3296           // need to read fewer bytes from the same pointer.
3297           if (DAG.getDataLayout().isBigEndian()) {
3298             unsigned LVTStoreBytes = LoadedVT.getStoreSize();
3299             unsigned EVTStoreBytes = ExtVT.getStoreSize();
3300             unsigned PtrOff = LVTStoreBytes - EVTStoreBytes;
3301             SDLoc DL(LN0);
3302             NewPtr = DAG.getNode(ISD::ADD, DL, PtrType,
3303                                  NewPtr, DAG.getConstant(PtrOff, DL, PtrType));
3304             Alignment = MinAlign(Alignment, PtrOff);
3305           }
3306
3307           AddToWorklist(NewPtr.getNode());
3308
3309           SDValue Load =
3310             DAG.getExtLoad(ISD::ZEXTLOAD, SDLoc(LN0), LoadResultTy,
3311                            LN0->getChain(), NewPtr,
3312                         &nb