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     SDValue CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
 160                       bool AddTo = true);
 161
 162     SDValue CombineTo(SDNode *N, SDValue Res, bool AddTo = true) {
 163       return CombineTo(N, &Res, 1, AddTo);
 164     }
 165
 166     SDValue CombineTo(SDNode *N, SDValue Res0, SDValue Res1,
 167                       bool AddTo = true) {
 168       SDValue To[] = { Res0, Res1 };
 169       return CombineTo(N, To, 2, AddTo);
 170     }
 171
 172     void CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO);
 173
 174   private:
 175
 176     /// Check the specified integer node value to see if it can be simplified or
 177     /// if things it uses can be simplified by bit propagation.
 178     /// If so, return true.
 179     bool SimplifyDemandedBits(SDValue Op) {
 180       unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
 181       APInt Demanded = APInt::getAllOnesValue(BitWidth);
 182       return SimplifyDemandedBits(Op, Demanded);
 183     }
 184
 185     bool SimplifyDemandedBits(SDValue Op, const APInt &Demanded);
 186
 187     bool CombineToPreIndexedLoadStore(SDNode *N);
 188     bool CombineToPostIndexedLoadStore(SDNode *N);
 189     SDValue SplitIndexingFromLoad(LoadSDNode *LD);
 190     bool SliceUpLoad(SDNode *N);
 191
 192     /// \brief Replace an ISD::EXTRACT_VECTOR_ELT of a load with a narrowed
 193     ///   load.
 194     ///
 195     /// \param EVE ISD::EXTRACT_VECTOR_ELT to be replaced.
 196     /// \param InVecVT type of the input vector to EVE with bitcasts resolved.
 197     /// \param EltNo index of the vector element to load.
 198     /// \param OriginalLoad load that EVE came from to be replaced.
 199     /// \returns EVE on success SDValue() on failure.
 200     SDValue ReplaceExtractVectorEltOfLoadWithNarrowedLoad(
 201         SDNode *EVE, EVT InVecVT, SDValue EltNo, LoadSDNode *OriginalLoad);
 202     void ReplaceLoadWithPromotedLoad(SDNode *Load, SDNode *ExtLoad);
 203     SDValue PromoteOperand(SDValue Op, EVT PVT, bool &Replace);
 204     SDValue SExtPromoteOperand(SDValue Op, EVT PVT);
 205     SDValue ZExtPromoteOperand(SDValue Op, EVT PVT);
 206     SDValue PromoteIntBinOp(SDValue Op);
 207     SDValue PromoteIntShiftOp(SDValue Op);
 208     SDValue PromoteExtend(SDValue Op);
 209     bool PromoteLoad(SDValue Op);
 210
 211     void ExtendSetCCUses(const SmallVectorImpl<SDNode *> &SetCCs,
 212                          SDValue Trunc, SDValue ExtLoad, SDLoc DL,
 213                          ISD::NodeType ExtType);
 214
 215     /// Call the node-specific routine that knows how to fold each
 216     /// particular type of node. If that doesn't do anything, try the
 217     /// target-specific DAG combines.
 218     SDValue combine(SDNode *N);
 219
 220     // Visitation implementation - Implement dag node combining for different
 221     // node types.  The semantics are as follows:
 222     // Return Value:
 223     //   SDValue.getNode() == 0 - No change was made
 224     //   SDValue.getNode() == N - N was replaced, is dead and has been handled.
 225     //   otherwise              - N should be replaced by the returned Operand.
 226     //
 227     SDValue visitTokenFactor(SDNode *N);
 228     SDValue visitMERGE_VALUES(SDNode *N);
 229     SDValue visitADD(SDNode *N);
 230     SDValue visitSUB(SDNode *N);
 231     SDValue visitADDC(SDNode *N);
 232     SDValue visitSUBC(SDNode *N);
 233     SDValue visitADDE(SDNode *N);
 234     SDValue visitSUBE(SDNode *N);
 235     SDValue visitMUL(SDNode *N);
 236     SDValue visitSDIV(SDNode *N);
 237     SDValue visitUDIV(SDNode *N);
 238     SDValue visitSREM(SDNode *N);
 239     SDValue visitUREM(SDNode *N);
 240     SDValue visitMULHU(SDNode *N);
 241     SDValue visitMULHS(SDNode *N);
 242     SDValue visitSMUL_LOHI(SDNode *N);
 243     SDValue visitUMUL_LOHI(SDNode *N);
 244     SDValue visitSMULO(SDNode *N);
 245     SDValue visitUMULO(SDNode *N);
 246     SDValue visitSDIVREM(SDNode *N);
 247     SDValue visitUDIVREM(SDNode *N);
 248     SDValue visitAND(SDNode *N);
 249     SDValue visitOR(SDNode *N);
 250     SDValue visitXOR(SDNode *N);
 251     SDValue SimplifyVBinOp(SDNode *N);
 252     SDValue SimplifyVUnaryOp(SDNode *N);
 253     SDValue visitSHL(SDNode *N);
 254     SDValue visitSRA(SDNode *N);
 255     SDValue visitSRL(SDNode *N);
 256     SDValue visitRotate(SDNode *N);
 257     SDValue visitCTLZ(SDNode *N);
 258     SDValue visitCTLZ_ZERO_UNDEF(SDNode *N);
 259     SDValue visitCTTZ(SDNode *N);
 260     SDValue visitCTTZ_ZERO_UNDEF(SDNode *N);
 261     SDValue visitCTPOP(SDNode *N);
 262     SDValue visitSELECT(SDNode *N);
 263     SDValue visitVSELECT(SDNode *N);
 264     SDValue visitSELECT_CC(SDNode *N);
 265     SDValue visitSETCC(SDNode *N);
 266     SDValue visitSIGN_EXTEND(SDNode *N);
 267     SDValue visitZERO_EXTEND(SDNode *N);
 268     SDValue visitANY_EXTEND(SDNode *N);
 269     SDValue visitSIGN_EXTEND_INREG(SDNode *N);
 270     SDValue visitTRUNCATE(SDNode *N);
 271     SDValue visitBITCAST(SDNode *N);
 272     SDValue visitBUILD_PAIR(SDNode *N);
 273     SDValue visitFADD(SDNode *N);
 274     SDValue visitFSUB(SDNode *N);
 275     SDValue visitFMUL(SDNode *N);
 276     SDValue visitFMA(SDNode *N);
 277     SDValue visitFDIV(SDNode *N);
 278     SDValue visitFREM(SDNode *N);
 279     SDValue visitFSQRT(SDNode *N);
 280     SDValue visitFCOPYSIGN(SDNode *N);
 281     SDValue visitSINT_TO_FP(SDNode *N);
 282     SDValue visitUINT_TO_FP(SDNode *N);
 283     SDValue visitFP_TO_SINT(SDNode *N);
 284     SDValue visitFP_TO_UINT(SDNode *N);
 285     SDValue visitFP_ROUND(SDNode *N);
 286     SDValue visitFP_ROUND_INREG(SDNode *N);
 287     SDValue visitFP_EXTEND(SDNode *N);
 288     SDValue visitFNEG(SDNode *N);
 289     SDValue visitFABS(SDNode *N);
 290     SDValue visitFCEIL(SDNode *N);
 291     SDValue visitFTRUNC(SDNode *N);
 292     SDValue visitFFLOOR(SDNode *N);
 293     SDValue visitFMINNUM(SDNode *N);
 294     SDValue visitFMAXNUM(SDNode *N);
 295     SDValue visitBRCOND(SDNode *N);
 296     SDValue visitBR_CC(SDNode *N);
 297     SDValue visitLOAD(SDNode *N);
 298     SDValue visitSTORE(SDNode *N);
 299     SDValue visitINSERT_VECTOR_ELT(SDNode *N);
 300     SDValue visitEXTRACT_VECTOR_ELT(SDNode *N);
 301     SDValue visitBUILD_VECTOR(SDNode *N);
 302     SDValue visitCONCAT_VECTORS(SDNode *N);
 303     SDValue visitEXTRACT_SUBVECTOR(SDNode *N);
 304     SDValue visitVECTOR_SHUFFLE(SDNode *N);
 305     SDValue visitINSERT_SUBVECTOR(SDNode *N);
 306     SDValue visitMLOAD(SDNode *N);
 307     SDValue visitMSTORE(SDNode *N);
 308
 309     SDValue XformToShuffleWithZero(SDNode *N);
 310     SDValue ReassociateOps(unsigned Opc, SDLoc DL, SDValue LHS, SDValue RHS);
 311
 312     SDValue visitShiftByConstant(SDNode *N, ConstantSDNode *Amt);
 313
 314     bool SimplifySelectOps(SDNode *SELECT, SDValue LHS, SDValue RHS);
 315     SDValue SimplifyBinOpWithSameOpcodeHands(SDNode *N);
 316     SDValue SimplifySelect(SDLoc DL, SDValue N0, SDValue N1, SDValue N2);
 317     SDValue SimplifySelectCC(SDLoc DL, SDValue N0, SDValue N1, SDValue N2,
 318                              SDValue N3, ISD::CondCode CC,
 319                              bool NotExtCompare = false);
 320     SDValue SimplifySetCC(EVT VT, SDValue N0, SDValue N1, ISD::CondCode Cond,
 321                           SDLoc DL, bool foldBooleans = true);
 322
 323     bool isSetCCEquivalent(SDValue N, SDValue &LHS, SDValue &RHS,
 324                            SDValue &CC) const;
 325     bool isOneUseSetCC(SDValue N) const;
 326
 327     SDValue SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp,
 328                                          unsigned HiOp);
 329     SDValue CombineConsecutiveLoads(SDNode *N, EVT VT);
 330     SDValue ConstantFoldBITCASTofBUILD_VECTOR(SDNode *, EVT);
 331     SDValue BuildSDIV(SDNode *N);
 332     SDValue BuildSDIVPow2(SDNode *N);
 333     SDValue BuildUDIV(SDNode *N);
 334     SDValue BuildReciprocalEstimate(SDValue Op);
 335     SDValue BuildRsqrtEstimate(SDValue Op);
 336     SDValue BuildRsqrtNROneConst(SDValue Op, SDValue Est, unsigned Iterations);
 337     SDValue BuildRsqrtNRTwoConst(SDValue Op, SDValue Est, unsigned Iterations);
 338     SDValue MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
 339                                bool DemandHighBits = true);
 340     SDValue MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1);
 341     SDNode *MatchRotatePosNeg(SDValue Shifted, SDValue Pos, SDValue Neg,
 342                               SDValue InnerPos, SDValue InnerNeg,
 343                               unsigned PosOpcode, unsigned NegOpcode,
 344                               SDLoc DL);
 345     SDNode *MatchRotate(SDValue LHS, SDValue RHS, SDLoc DL);
 346     SDValue ReduceLoadWidth(SDNode *N);
 347     SDValue ReduceLoadOpStoreWidth(SDNode *N);
 348     SDValue TransformFPLoadStorePair(SDNode *N);
 349     SDValue reduceBuildVecExtToExtBuildVec(SDNode *N);
 350     SDValue reduceBuildVecConvertToConvertBuildVec(SDNode *N);
 351
 352     SDValue GetDemandedBits(SDValue V, const APInt &Mask);
 353
 354     /// Walk up chain skipping non-aliasing memory nodes,
 355     /// looking for aliasing nodes and adding them to the Aliases vector.
 356     void GatherAllAliases(SDNode *N, SDValue OriginalChain,
 357                           SmallVectorImpl<SDValue> &Aliases);
 358
 359     /// Return true if there is any possibility that the two addresses overlap.
 360     bool isAlias(LSBaseSDNode *Op0, LSBaseSDNode *Op1) const;
 361
 362     /// Walk up chain skipping non-aliasing memory nodes, looking for a better
 363     /// chain (aliasing node.)
 364     SDValue FindBetterChain(SDNode *N, SDValue Chain);
 365
 366     /// Merge consecutive store operations into a wide store.
 367     /// This optimization uses wide integers or vectors when possible.
 368     /// \return True if some memory operations were changed.
 369     bool MergeConsecutiveStores(StoreSDNode *N);
 370
 371     /// \brief Try to transform a truncation where C is a constant:
 372     ///     (trunc (and X, C)) -> (and (trunc X), (trunc C))
 373     ///
 374     /// \p N needs to be a truncation and its first operand an AND. Other
 375     /// requirements are checked by the function (e.g. that trunc is
 376     /// single-use) and if missed an empty SDValue is returned.
 377     SDValue distributeTruncateThroughAnd(SDNode *N);
 378
 379   public:
 380     DAGCombiner(SelectionDAG &D, AliasAnalysis &A, CodeGenOpt::Level OL)
 381         : DAG(D), TLI(D.getTargetLoweringInfo()), Level(BeforeLegalizeTypes),
 382           OptLevel(OL), LegalOperations(false), LegalTypes(false), AA(A) {
 383       AttributeSet FnAttrs =
 384           DAG.getMachineFunction().getFunction()->getAttributes();
 385       ForCodeSize =
 386           FnAttrs.hasAttribute(AttributeSet::FunctionIndex,
 387                                Attribute::OptimizeForSize) ||
 388           FnAttrs.hasAttribute(AttributeSet::FunctionIndex, Attribute::MinSize);
 389     }
 390
 391     /// Runs the dag combiner on all nodes in the work list
 392     void Run(CombineLevel AtLevel);
 393
 394     SelectionDAG &getDAG() const { return DAG; }
 395
 396     /// Returns a type large enough to hold any valid shift amount - before type
 397     /// legalization these can be huge.
 398     EVT getShiftAmountTy(EVT LHSTy) {
 399       assert(LHSTy.isInteger() && "Shift amount is not an integer type!");
 400       if (LHSTy.isVector())
 401         return LHSTy;
 402       return LegalTypes ? TLI.getScalarShiftAmountTy(LHSTy)
 403                         : TLI.getPointerTy();
 404     }
 405
 406     /// This method returns true if we are running before type legalization or
 407     /// if the specified VT is legal.
 408     bool isTypeLegal(const EVT &VT) {
 409       if (!LegalTypes) return true;
 410       return TLI.isTypeLegal(VT);
 411     }
 412
 413     /// Convenience wrapper around TargetLowering::getSetCCResultType
 414     EVT getSetCCResultType(EVT VT) const {
 415       return TLI.getSetCCResultType(*DAG.getContext(), VT);
 416     }
 417   };
 418 }
 419
 420
 421 namespace {
 422 /// This class is a DAGUpdateListener that removes any deleted
 423 /// nodes from the worklist.
 424 class WorklistRemover : public SelectionDAG::DAGUpdateListener {
 425   DAGCombiner &DC;
 426 public:
 427   explicit WorklistRemover(DAGCombiner &dc)
 428     : SelectionDAG::DAGUpdateListener(dc.getDAG()), DC(dc) {}
 429
 430   void NodeDeleted(SDNode *N, SDNode *E) override {
 431     DC.removeFromWorklist(N);
 432   }
 433 };
 434 }
 435
 436 //===----------------------------------------------------------------------===//
 437 //  TargetLowering::DAGCombinerInfo implementation
 438 //===----------------------------------------------------------------------===//
 439
 440 void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) {
 441   ((DAGCombiner*)DC)->AddToWorklist(N);
 442 }
 443
 444 void TargetLowering::DAGCombinerInfo::RemoveFromWorklist(SDNode *N) {
 445   ((DAGCombiner*)DC)->removeFromWorklist(N);
 446 }
 447
 448 SDValue TargetLowering::DAGCombinerInfo::
 449 CombineTo(SDNode *N, const std::vector<SDValue> &To, bool AddTo) {
 450   return ((DAGCombiner*)DC)->CombineTo(N, &To[0], To.size(), AddTo);
 451 }
 452
 453 SDValue TargetLowering::DAGCombinerInfo::
 454 CombineTo(SDNode *N, SDValue Res, bool AddTo) {
 455   return ((DAGCombiner*)DC)->CombineTo(N, Res, AddTo);
 456 }
 457
 458
 459 SDValue TargetLowering::DAGCombinerInfo::
 460 CombineTo(SDNode *N, SDValue Res0, SDValue Res1, bool AddTo) {
 461   return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1, AddTo);
 462 }
 463
 464 void TargetLowering::DAGCombinerInfo::
 465 CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO) {
 466   return ((DAGCombiner*)DC)->CommitTargetLoweringOpt(TLO);
 467 }
 468
 469 //===----------------------------------------------------------------------===//
 470 // Helper Functions
 471 //===----------------------------------------------------------------------===//
 472
 473 void DAGCombiner::deleteAndRecombine(SDNode *N) {
 474   removeFromWorklist(N);
 475
 476   // If the operands of this node are only used by the node, they will now be
 477   // dead. Make sure to re-visit them and recursively delete dead nodes.
 478   for (const SDValue &Op : N->ops())
 479     // For an operand generating multiple values, one of the values may
 480     // become dead allowing further simplification (e.g. split index
 481     // arithmetic from an indexed load).
 482     if (Op->hasOneUse() || Op->getNumValues() > 1)
 483       AddToWorklist(Op.getNode());
 484
 485   DAG.DeleteNode(N);
 486 }
 487
 488 /// Return 1 if we can compute the negated form of the specified expression for
 489 /// the same cost as the expression itself, or 2 if we can compute the negated
 490 /// form more cheaply than the expression itself.
 491 static char isNegatibleForFree(SDValue Op, bool LegalOperations,
 492                                const TargetLowering &TLI,
 493                                const TargetOptions *Options,
 494                                unsigned Depth = 0) {
 495   // fneg is removable even if it has multiple uses.
 496   if (Op.getOpcode() == ISD::FNEG) return 2;
 497
 498   // Don't allow anything with multiple uses.
 499   if (!Op.hasOneUse()) return 0;
 500
 501   // Don't recurse exponentially.
 502   if (Depth > 6) return 0;
 503
 504   switch (Op.getOpcode()) {
 505   default: return false;
 506   case ISD::ConstantFP:
 507     // Don't invert constant FP values after legalize.  The negated constant
 508     // isn't necessarily legal.
 509     return LegalOperations ? 0 : 1;
 510   case ISD::FADD:
 511     // FIXME: determine better conditions for this xform.
 512     if (!Options->UnsafeFPMath) return 0;
 513
 514     // After operation legalization, it might not be legal to create new FSUBs.
 515     if (LegalOperations &&
 516         !TLI.isOperationLegalOrCustom(ISD::FSUB,  Op.getValueType()))
 517       return 0;
 518
 519     // fold (fneg (fadd A, B)) -> (fsub (fneg A), B)
 520     if (char V = isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI,
 521                                     Options, Depth + 1))
 522       return V;
 523     // fold (fneg (fadd A, B)) -> (fsub (fneg B), A)
 524     return isNegatibleForFree(Op.getOperand(1), LegalOperations, TLI, Options,
 525                               Depth + 1);
 526   case ISD::FSUB:
 527     // We can't turn -(A-B) into B-A when we honor signed zeros.
 528     if (!Options->UnsafeFPMath) return 0;
 529
 530     // fold (fneg (fsub A, B)) -> (fsub B, A)
 531     return 1;
 532
 533   case ISD::FMUL:
 534   case ISD::FDIV:
 535     if (Options->HonorSignDependentRoundingFPMath()) return 0;
 536
 537     // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y) or (fmul X, (fneg Y))
 538     if (char V = isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI,
 539                                     Options, Depth + 1))
 540       return V;
 541
 542     return isNegatibleForFree(Op.getOperand(1), LegalOperations, TLI, Options,
 543                               Depth + 1);
 544
 545   case ISD::FP_EXTEND:
 546   case ISD::FP_ROUND:
 547   case ISD::FSIN:
 548     return isNegatibleForFree(Op.getOperand(0), LegalOperations, TLI, Options,
 549                               Depth + 1);
 550   }
 551 }
 552
 553 /// If isNegatibleForFree returns true, return the newly negated expression.
 554 static SDValue GetNegatedExpression(SDValue Op, SelectionDAG &DAG,
 555                                     bool LegalOperations, unsigned Depth = 0) {
 556   const TargetOptions &Options = DAG.getTarget().Options;
 557   // fneg is removable even if it has multiple uses.
 558   if (Op.getOpcode() == ISD::FNEG) return Op.getOperand(0);
 559
 560   // Don't allow anything with multiple uses.
 561   assert(Op.hasOneUse() && "Unknown reuse!");
 562
 563   assert(Depth <= 6 && "GetNegatedExpression doesn't match isNegatibleForFree");
 564   switch (Op.getOpcode()) {
 565   default: llvm_unreachable("Unknown code");
 566   case ISD::ConstantFP: {
 567     APFloat V = cast<ConstantFPSDNode>(Op)->getValueAPF();
 568     V.changeSign();
 569     return DAG.getConstantFP(V, Op.getValueType());
 570   }
 571   case ISD::FADD:
 572     // FIXME: determine better conditions for this xform.
 573     assert(Options.UnsafeFPMath);
 574
 575     // fold (fneg (fadd A, B)) -> (fsub (fneg A), B)
 576     if (isNegatibleForFree(Op.getOperand(0), LegalOperations,
 577                            DAG.getTargetLoweringInfo(), &Options, Depth+1))
 578       return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
 579                          GetNegatedExpression(Op.getOperand(0), DAG,
 580                                               LegalOperations, Depth+1),
 581                          Op.getOperand(1));
 582     // fold (fneg (fadd A, B)) -> (fsub (fneg B), A)
 583     return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
 584                        GetNegatedExpression(Op.getOperand(1), DAG,
 585                                             LegalOperations, Depth+1),
 586                        Op.getOperand(0));
 587   case ISD::FSUB:
 588     // We can't turn -(A-B) into B-A when we honor signed zeros.
 589     assert(Options.UnsafeFPMath);
 590
 591     // fold (fneg (fsub 0, B)) -> B
 592     if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(Op.getOperand(0)))
 593       if (N0CFP->getValueAPF().isZero())
 594         return Op.getOperand(1);
 595
 596     // fold (fneg (fsub A, B)) -> (fsub B, A)
 597     return DAG.getNode(ISD::FSUB, SDLoc(Op), Op.getValueType(),
 598                        Op.getOperand(1), Op.getOperand(0));
 599
 600   case ISD::FMUL:
 601   case ISD::FDIV:
 602     assert(!Options.HonorSignDependentRoundingFPMath());
 603
 604     // fold (fneg (fmul X, Y)) -> (fmul (fneg X), Y)
 605     if (isNegatibleForFree(Op.getOperand(0), LegalOperations,
 606                            DAG.getTargetLoweringInfo(), &Options, Depth+1))
 607       return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
 608                          GetNegatedExpression(Op.getOperand(0), DAG,
 609                                               LegalOperations, Depth+1),
 610                          Op.getOperand(1));
 611
 612     // fold (fneg (fmul X, Y)) -> (fmul X, (fneg Y))
 613     return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
 614                        Op.getOperand(0),
 615                        GetNegatedExpression(Op.getOperand(1), DAG,
 616                                             LegalOperations, Depth+1));
 617
 618   case ISD::FP_EXTEND:
 619   case ISD::FSIN:
 620     return DAG.getNode(Op.getOpcode(), SDLoc(Op), Op.getValueType(),
 621                        GetNegatedExpression(Op.getOperand(0), DAG,
 622                                             LegalOperations, Depth+1));
 623   case ISD::FP_ROUND:
 624       return DAG.getNode(ISD::FP_ROUND, SDLoc(Op), Op.getValueType(),
 625                          GetNegatedExpression(Op.getOperand(0), DAG,
 626                                               LegalOperations, Depth+1),
 627                          Op.getOperand(1));
 628   }
 629 }
 630
 631 // Return true if this node is a setcc, or is a select_cc
 632 // that selects between the target values used for true and false, making it
 633 // equivalent to a setcc. Also, set the incoming LHS, RHS, and CC references to
 634 // the appropriate nodes based on the type of node we are checking. This
 635 // simplifies life a bit for the callers.
 636 bool DAGCombiner::isSetCCEquivalent(SDValue N, SDValue &LHS, SDValue &RHS,
 637                                     SDValue &CC) const {
 638   if (N.getOpcode() == ISD::SETCC) {
 639     LHS = N.getOperand(0);
 640     RHS = N.getOperand(1);
 641     CC  = N.getOperand(2);
 642     return true;
 643   }
 644
 645   if (N.getOpcode() != ISD::SELECT_CC ||
 646       !TLI.isConstTrueVal(N.getOperand(2).getNode()) ||
 647       !TLI.isConstFalseVal(N.getOperand(3).getNode()))
 648     return false;
 649
 650   if (TLI.getBooleanContents(N.getValueType()) ==
 651       TargetLowering::UndefinedBooleanContent)
 652     return false;
 653
 654   LHS = N.getOperand(0);
 655   RHS = N.getOperand(1);
 656   CC  = N.getOperand(4);
 657   return true;
 658 }
 659
 660 /// Return true if this is a SetCC-equivalent operation with only one use.
 661 /// If this is true, it allows the users to invert the operation for free when
 662 /// it is profitable to do so.
 663 bool DAGCombiner::isOneUseSetCC(SDValue N) const {
 664   SDValue N0, N1, N2;
 665   if (isSetCCEquivalent(N, N0, N1, N2) && N.getNode()->hasOneUse())
 666     return true;
 667   return false;
 668 }
 669
 670 /// Returns true if N is a BUILD_VECTOR node whose
 671 /// elements are all the same constant or undefined.
 672 static bool isConstantSplatVector(SDNode *N, APInt& SplatValue) {
 673   BuildVectorSDNode *C = dyn_cast<BuildVectorSDNode>(N);
 674   if (!C)
 675     return false;
 676
 677   APInt SplatUndef;
 678   unsigned SplatBitSize;
 679   bool HasAnyUndefs;
 680   EVT EltVT = N->getValueType(0).getVectorElementType();
 681   return (C->isConstantSplat(SplatValue, SplatUndef, SplatBitSize,
 682                              HasAnyUndefs) &&
 683           EltVT.getSizeInBits() >= SplatBitSize);
 684 }
 685
 686 // \brief Returns the SDNode if it is a constant BuildVector or constant.
 687 static SDNode *isConstantBuildVectorOrConstantInt(SDValue N) {
 688   if (isa<ConstantSDNode>(N))
 689     return N.getNode();
 690   BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(N);
 691   if (BV && BV->isConstant())
 692     return BV;
 693   return nullptr;
 694 }
 695
 696 // \brief Returns the SDNode if it is a constant splat BuildVector or constant
 697 // int.
 698 static ConstantSDNode *isConstOrConstSplat(SDValue N) {
 699   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N))
 700     return CN;
 701
 702   if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(N)) {
 703     BitVector UndefElements;
 704     ConstantSDNode *CN = BV->getConstantSplatNode(&UndefElements);
 705
 706     // BuildVectors can truncate their operands. Ignore that case here.
 707     // FIXME: We blindly ignore splats which include undef which is overly
 708     // pessimistic.
 709     if (CN && UndefElements.none() &&
 710         CN->getValueType(0) == N.getValueType().getScalarType())
 711       return CN;
 712   }
 713
 714   return nullptr;
 715 }
 716
 717 // \brief Returns the SDNode if it is a constant splat BuildVector or constant
 718 // float.
 719 static ConstantFPSDNode *isConstOrConstSplatFP(SDValue N) {
 720   if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N))
 721     return CN;
 722
 723   if (BuildVectorSDNode *BV = dyn_cast<BuildVectorSDNode>(N)) {
 724     BitVector UndefElements;
 725     ConstantFPSDNode *CN = BV->getConstantFPSplatNode(&UndefElements);
 726
 727     if (CN && UndefElements.none())
 728       return CN;
 729   }
 730
 731   return nullptr;
 732 }
 733
 734 SDValue DAGCombiner::ReassociateOps(unsigned Opc, SDLoc DL,
 735                                     SDValue N0, SDValue N1) {
 736   EVT VT = N0.getValueType();
 737   if (N0.getOpcode() == Opc) {
 738     if (SDNode *L = isConstantBuildVectorOrConstantInt(N0.getOperand(1))) {
 739       if (SDNode *R = isConstantBuildVectorOrConstantInt(N1)) {
 740         // reassoc. (op (op x, c1), c2) -> (op x, (op c1, c2))
 741         if (SDValue OpNode = DAG.FoldConstantArithmetic(Opc, VT, L, R))
 742           return DAG.getNode(Opc, DL, VT, N0.getOperand(0), OpNode);
 743         return SDValue();
 744       }
 745       if (N0.hasOneUse()) {
 746         // reassoc. (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one
 747         // use
 748         SDValue OpNode = DAG.getNode(Opc, SDLoc(N0), VT, N0.getOperand(0), N1);
 749         if (!OpNode.getNode())
 750           return SDValue();
 751         AddToWorklist(OpNode.getNode());
 752         return DAG.getNode(Opc, DL, VT, OpNode, N0.getOperand(1));
 753       }
 754     }
 755   }
 756
 757   if (N1.getOpcode() == Opc) {
 758     if (SDNode *R = isConstantBuildVectorOrConstantInt(N1.getOperand(1))) {
 759       if (SDNode *L = isConstantBuildVectorOrConstantInt(N0)) {
 760         // reassoc. (op c2, (op x, c1)) -> (op x, (op c1, c2))
 761         if (SDValue OpNode = DAG.FoldConstantArithmetic(Opc, VT, R, L))
 762           return DAG.getNode(Opc, DL, VT, N1.getOperand(0), OpNode);
 763         return SDValue();
 764       }
 765       if (N1.hasOneUse()) {
 766         // reassoc. (op y, (op x, c1)) -> (op (op x, y), c1) iff x+c1 has one
 767         // use
 768         SDValue OpNode = DAG.getNode(Opc, SDLoc(N0), VT, N1.getOperand(0), N0);
 769         if (!OpNode.getNode())
 770           return SDValue();
 771         AddToWorklist(OpNode.getNode());
 772         return DAG.getNode(Opc, DL, VT, OpNode, N1.getOperand(1));
 773       }
 774     }
 775   }
 776
 777   return SDValue();
 778 }
 779
 780 SDValue DAGCombiner::CombineTo(SDNode *N, const SDValue *To, unsigned NumTo,
 781                                bool AddTo) {
 782   assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
 783   ++NodesCombined;
 784   DEBUG(dbgs() << "\nReplacing.1 ";
 785         N->dump(&DAG);
 786         dbgs() << "\nWith: ";
 787         To[0].getNode()->dump(&DAG);
 788         dbgs() << " and " << NumTo-1 << " other values\n");
 789   for (unsigned i = 0, e = NumTo; i != e; ++i)
 790     assert((!To[i].getNode() ||
 791             N->getValueType(i) == To[i].getValueType()) &&
 792            "Cannot combine value to value of different type!");
 793
 794   WorklistRemover DeadNodes(*this);
 795   DAG.ReplaceAllUsesWith(N, To);
 796   if (AddTo) {
 797     // Push the new nodes and any users onto the worklist
 798     for (unsigned i = 0, e = NumTo; i != e; ++i) {
 799       if (To[i].getNode()) {
 800         AddToWorklist(To[i].getNode());
 801         AddUsersToWorklist(To[i].getNode());
 802       }
 803     }
 804   }
 805
 806   // Finally, if the node is now dead, remove it from the graph.  The node
 807   // may not be dead if the replacement process recursively simplified to
 808   // something else needing this node.
 809   if (N->use_empty())
 810     deleteAndRecombine(N);
 811   return SDValue(N, 0);
 812 }
 813
 814 void DAGCombiner::
 815 CommitTargetLoweringOpt(const TargetLowering::TargetLoweringOpt &TLO) {
 816   // Replace all uses.  If any nodes become isomorphic to other nodes and
 817   // are deleted, make sure to remove them from our worklist.
 818   WorklistRemover DeadNodes(*this);
 819   DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New);
 820
 821   // Push the new node and any (possibly new) users onto the worklist.
 822   AddToWorklist(TLO.New.getNode());
 823   AddUsersToWorklist(TLO.New.getNode());
 824
 825   // Finally, if the node is now dead, remove it from the graph.  The node
 826   // may not be dead if the replacement process recursively simplified to
 827   // something else needing this node.
 828   if (TLO.Old.getNode()->use_empty())
 829     deleteAndRecombine(TLO.Old.getNode());
 830 }
 831
 832 /// Check the specified integer node value to see if it can be simplified or if
 833 /// things it uses can be simplified by bit propagation. If so, return true.
 834 bool DAGCombiner::SimplifyDemandedBits(SDValue Op, const APInt &Demanded) {
 835   TargetLowering::TargetLoweringOpt TLO(DAG, LegalTypes, LegalOperations);
 836   APInt KnownZero, KnownOne;
 837   if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO))
 838     return false;
 839
 840   // Revisit the node.
 841   AddToWorklist(Op.getNode());
 842
 843   // Replace the old value with the new one.
 844   ++NodesCombined;
 845   DEBUG(dbgs() << "\nReplacing.2 ";
 846         TLO.Old.getNode()->dump(&DAG);
 847         dbgs() << "\nWith: ";
 848         TLO.New.getNode()->dump(&DAG);
 849         dbgs() << '\n');
 850
 851   CommitTargetLoweringOpt(TLO);
 852   return true;
 853 }
 854
 855 void DAGCombiner::ReplaceLoadWithPromotedLoad(SDNode *Load, SDNode *ExtLoad) {
 856   SDLoc dl(Load);
 857   EVT VT = Load->getValueType(0);
 858   SDValue Trunc = DAG.getNode(ISD::TRUNCATE, dl, VT, SDValue(ExtLoad, 0));
 859
 860   DEBUG(dbgs() << "\nReplacing.9 ";
 861         Load->dump(&DAG);
 862         dbgs() << "\nWith: ";
 863         Trunc.getNode()->dump(&DAG);
 864         dbgs() << '\n');
 865   WorklistRemover DeadNodes(*this);
 866   DAG.ReplaceAllUsesOfValueWith(SDValue(Load, 0), Trunc);
 867   DAG.ReplaceAllUsesOfValueWith(SDValue(Load, 1), SDValue(ExtLoad, 1));
 868   deleteAndRecombine(Load);
 869   AddToWorklist(Trunc.getNode());
 870 }
 871
 872 SDValue DAGCombiner::PromoteOperand(SDValue Op, EVT PVT, bool &Replace) {
 873   Replace = false;
 874   SDLoc dl(Op);
 875   if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) {
 876     EVT MemVT = LD->getMemoryVT();
 877     ISD::LoadExtType ExtType = ISD::isNON_EXTLoad(LD)
 878       ? (TLI.isLoadExtLegal(ISD::ZEXTLOAD, PVT, MemVT) ? ISD::ZEXTLOAD
 879                                                        : ISD::EXTLOAD)
 880       : LD->getExtensionType();
 881     Replace = true;
 882     return DAG.getExtLoad(ExtType, dl, PVT,
 883                           LD->getChain(), LD->getBasePtr(),
 884                           MemVT, LD->getMemOperand());
 885   }
 886
 887   unsigned Opc = Op.getOpcode();
 888   switch (Opc) {
 889   default: break;
 890   case ISD::AssertSext:
 891     return DAG.getNode(ISD::AssertSext, dl, PVT,
 892                        SExtPromoteOperand(Op.getOperand(0), PVT),
 893                        Op.getOperand(1));
 894   case ISD::AssertZext:
 895     return DAG.getNode(ISD::AssertZext, dl, PVT,
 896                        ZExtPromoteOperand(Op.getOperand(0), PVT),
 897                        Op.getOperand(1));
 898   case ISD::Constant: {
 899     unsigned ExtOpc =
 900       Op.getValueType().isByteSized() ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
 901     return DAG.getNode(ExtOpc, dl, PVT, Op);
 902   }
 903   }
 904
 905   if (!TLI.isOperationLegal(ISD::ANY_EXTEND, PVT))
 906     return SDValue();
 907   return DAG.getNode(ISD::ANY_EXTEND, dl, PVT, Op);
 908 }
 909
 910 SDValue DAGCombiner::SExtPromoteOperand(SDValue Op, EVT PVT) {
 911   if (!TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, PVT))
 912     return SDValue();
 913   EVT OldVT = Op.getValueType();
 914   SDLoc dl(Op);
 915   bool Replace = false;
 916   SDValue NewOp = PromoteOperand(Op, PVT, Replace);
 917   if (!NewOp.getNode())
 918     return SDValue();
 919   AddToWorklist(NewOp.getNode());
 920
 921   if (Replace)
 922     ReplaceLoadWithPromotedLoad(Op.getNode(), NewOp.getNode());
 923   return DAG.getNode(ISD::SIGN_EXTEND_INREG, dl, NewOp.getValueType(), NewOp,
 924                      DAG.getValueType(OldVT));
 925 }
 926
 927 SDValue DAGCombiner::ZExtPromoteOperand(SDValue Op, EVT PVT) {
 928   EVT OldVT = Op.getValueType();
 929   SDLoc dl(Op);
 930   bool Replace = false;
 931   SDValue NewOp = PromoteOperand(Op, PVT, Replace);
 932   if (!NewOp.getNode())
 933     return SDValue();
 934   AddToWorklist(NewOp.getNode());
 935
 936   if (Replace)
 937     ReplaceLoadWithPromotedLoad(Op.getNode(), NewOp.getNode());
 938   return DAG.getZeroExtendInReg(NewOp, dl, OldVT);
 939 }
 940
 941 /// Promote the specified integer binary operation if the target indicates it is
 942 /// beneficial. e.g. On x86, it's usually better to promote i16 operations to
 943 /// i32 since i16 instructions are longer.
 944 SDValue DAGCombiner::PromoteIntBinOp(SDValue Op) {
 945   if (!LegalOperations)
 946     return SDValue();
 947
 948   EVT VT = Op.getValueType();
 949   if (VT.isVector() || !VT.isInteger())
 950     return SDValue();
 951
 952   // If operation type is 'undesirable', e.g. i16 on x86, consider
 953   // promoting it.
 954   unsigned Opc = Op.getOpcode();
 955   if (TLI.isTypeDesirableForOp(Opc, VT))
 956     return SDValue();
 957
 958   EVT PVT = VT;
 959   // Consult target whether it is a good idea to promote this operation and
 960   // what's the right type to promote it to.
 961   if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
 962     assert(PVT != VT && "Don't know what type to promote to!");
 963
 964     bool Replace0 = false;
 965     SDValue N0 = Op.getOperand(0);
 966     SDValue NN0 = PromoteOperand(N0, PVT, Replace0);
 967     if (!NN0.getNode())
 968       return SDValue();
 969
 970     bool Replace1 = false;
 971     SDValue N1 = Op.getOperand(1);
 972     SDValue NN1;
 973     if (N0 == N1)
 974       NN1 = NN0;
 975     else {
 976       NN1 = PromoteOperand(N1, PVT, Replace1);
 977       if (!NN1.getNode())
 978         return SDValue();
 979     }
 980
 981     AddToWorklist(NN0.getNode());
 982     if (NN1.getNode())
 983       AddToWorklist(NN1.getNode());
 984
 985     if (Replace0)
 986       ReplaceLoadWithPromotedLoad(N0.getNode(), NN0.getNode());
 987     if (Replace1)
 988       ReplaceLoadWithPromotedLoad(N1.getNode(), NN1.getNode());
 989
 990     DEBUG(dbgs() << "\nPromoting ";
 991           Op.getNode()->dump(&DAG));
 992     SDLoc dl(Op);
 993     return DAG.getNode(ISD::TRUNCATE, dl, VT,
 994                        DAG.getNode(Opc, dl, PVT, NN0, NN1));
 995   }
 996   return SDValue();
 997 }
 998
 999 /// Promote the specified integer shift operation if the target indicates it is
1000 /// beneficial. e.g. On x86, it's usually better to promote i16 operations to
1001 /// i32 since i16 instructions are longer.
1002 SDValue DAGCombiner::PromoteIntShiftOp(SDValue Op) {
1003   if (!LegalOperations)
1004     return SDValue();
1005
1006   EVT VT = Op.getValueType();
1007   if (VT.isVector() || !VT.isInteger())
1008     return SDValue();
1009
1010   // If operation type is 'undesirable', e.g. i16 on x86, consider
1011   // promoting it.
1012   unsigned Opc = Op.getOpcode();
1013   if (TLI.isTypeDesirableForOp(Opc, VT))
1014     return SDValue();
1015
1016   EVT PVT = VT;
1017   // Consult target whether it is a good idea to promote this operation and
1018   // what's the right type to promote it to.
1019   if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1020     assert(PVT != VT && "Don't know what type to promote to!");
1021
1022     bool Replace = false;
1023     SDValue N0 = Op.getOperand(0);
1024     if (Opc == ISD::SRA)
1025       N0 = SExtPromoteOperand(Op.getOperand(0), PVT);
1026     else if (Opc == ISD::SRL)
1027       N0 = ZExtPromoteOperand(Op.getOperand(0), PVT);
1028     else
1029       N0 = PromoteOperand(N0, PVT, Replace);
1030     if (!N0.getNode())
1031       return SDValue();
1032
1033     AddToWorklist(N0.getNode());
1034     if (Replace)
1035       ReplaceLoadWithPromotedLoad(Op.getOperand(0).getNode(), N0.getNode());
1036
1037     DEBUG(dbgs() << "\nPromoting ";
1038           Op.getNode()->dump(&DAG));
1039     SDLoc dl(Op);
1040     return DAG.getNode(ISD::TRUNCATE, dl, VT,
1041                        DAG.getNode(Opc, dl, PVT, N0, Op.getOperand(1)));
1042   }
1043   return SDValue();
1044 }
1045
1046 SDValue DAGCombiner::PromoteExtend(SDValue Op) {
1047   if (!LegalOperations)
1048     return SDValue();
1049
1050   EVT VT = Op.getValueType();
1051   if (VT.isVector() || !VT.isInteger())
1052     return SDValue();
1053
1054   // If operation type is 'undesirable', e.g. i16 on x86, consider
1055   // promoting it.
1056   unsigned Opc = Op.getOpcode();
1057   if (TLI.isTypeDesirableForOp(Opc, VT))
1058     return SDValue();
1059
1060   EVT PVT = VT;
1061   // Consult target whether it is a good idea to promote this operation and
1062   // what's the right type to promote it to.
1063   if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1064     assert(PVT != VT && "Don't know what type to promote to!");
1065     // fold (aext (aext x)) -> (aext x)
1066     // fold (aext (zext x)) -> (zext x)
1067     // fold (aext (sext x)) -> (sext x)
1068     DEBUG(dbgs() << "\nPromoting ";
1069           Op.getNode()->dump(&DAG));
1070     return DAG.getNode(Op.getOpcode(), SDLoc(Op), VT, Op.getOperand(0));
1071   }
1072   return SDValue();
1073 }
1074
1075 bool DAGCombiner::PromoteLoad(SDValue Op) {
1076   if (!LegalOperations)
1077     return false;
1078
1079   EVT VT = Op.getValueType();
1080   if (VT.isVector() || !VT.isInteger())
1081     return false;
1082
1083   // If operation type is 'undesirable', e.g. i16 on x86, consider
1084   // promoting it.
1085   unsigned Opc = Op.getOpcode();
1086   if (TLI.isTypeDesirableForOp(Opc, VT))
1087     return false;
1088
1089   EVT PVT = VT;
1090   // Consult target whether it is a good idea to promote this operation and
1091   // what's the right type to promote it to.
1092   if (TLI.IsDesirableToPromoteOp(Op, PVT)) {
1093     assert(PVT != VT && "Don't know what type to promote to!");
1094
1095     SDLoc dl(Op);
1096     SDNode *N = Op.getNode();
1097     LoadSDNode *LD = cast<LoadSDNode>(N);
1098     EVT MemVT = LD->getMemoryVT();
1099     ISD::LoadExtType ExtType = ISD::isNON_EXTLoad(LD)
1100       ? (TLI.isLoadExtLegal(ISD::ZEXTLOAD, PVT, MemVT) ? ISD::ZEXTLOAD
1101                                                        : ISD::EXTLOAD)
1102       : LD->getExtensionType();
1103     SDValue NewLD = DAG.getExtLoad(ExtType, dl, PVT,
1104                                    LD->getChain(), LD->getBasePtr(),
1105                                    MemVT, LD->getMemOperand());
1106     SDValue Result = DAG.getNode(ISD::TRUNCATE, dl, VT, NewLD);
1107
1108     DEBUG(dbgs() << "\nPromoting ";
1109           N->dump(&DAG);
1110           dbgs() << "\nTo: ";
1111           Result.getNode()->dump(&DAG);
1112           dbgs() << '\n');
1113     WorklistRemover DeadNodes(*this);
1114     DAG.ReplaceAllUsesOfValueWith(SDValue(N, 0), Result);
1115     DAG.ReplaceAllUsesOfValueWith(SDValue(N, 1), NewLD.getValue(1));
1116     deleteAndRecombine(N);
1117     AddToWorklist(Result.getNode());
1118     return true;
1119   }
1120   return false;
1121 }
1122
1123 /// \brief Recursively delete a node which has no uses and any operands for
1124 /// which it is the only use.
1125 ///
1126 /// Note that this both deletes the nodes and removes them from the worklist.
1127 /// It also adds any nodes who have had a user deleted to the worklist as they
1128 /// may now have only one use and subject to other combines.
1129 bool DAGCombiner::recursivelyDeleteUnusedNodes(SDNode *N) {
1130   if (!N->use_empty())
1131     return false;
1132
1133   SmallSetVector<SDNode *, 16> Nodes;
1134   Nodes.insert(N);
1135   do {
1136     N = Nodes.pop_back_val();
1137     if (!N)
1138       continue;
1139
1140     if (N->use_empty()) {
1141       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1142         Nodes.insert(N->getOperand(i).getNode());
1143
1144       removeFromWorklist(N);
1145       DAG.DeleteNode(N);
1146     } else {
1147       AddToWorklist(N);
1148     }
1149   } while (!Nodes.empty());
1150   return true;
1151 }
1152
1153 //===----------------------------------------------------------------------===//
1154 //  Main DAG Combiner implementation
1155 //===----------------------------------------------------------------------===//
1156
1157 void DAGCombiner::Run(CombineLevel AtLevel) {
1158   // set the instance variables, so that the various visit routines may use it.
1159   Level = AtLevel;
1160   LegalOperations = Level >= AfterLegalizeVectorOps;
1161   LegalTypes = Level >= AfterLegalizeTypes;
1162
1163   // Early exit if this basic block is in an optnone function.
1164   AttributeSet FnAttrs =
1165     DAG.getMachineFunction().getFunction()->getAttributes();
1166   if (FnAttrs.hasAttribute(AttributeSet::FunctionIndex,
1167                            Attribute::OptimizeNone))
1168     return;
1169
1170   // Add all the dag nodes to the worklist.
1171   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
1172        E = DAG.allnodes_end(); I != E; ++I)
1173     AddToWorklist(I);
1174
1175   // Create a dummy node (which is not added to allnodes), that adds a reference
1176   // to the root node, preventing it from being deleted, and tracking any
1177   // changes of the root.
1178   HandleSDNode Dummy(DAG.getRoot());
1179
1180   // while the worklist isn't empty, find a node and
1181   // try and combine it.
1182   while (!WorklistMap.empty()) {
1183     SDNode *N;
1184     // The Worklist holds the SDNodes in order, but it may contain null entries.
1185     do {
1186       N = Worklist.pop_back_val();
1187     } while (!N);
1188
1189     bool GoodWorklistEntry = WorklistMap.erase(N);
1190     (void)GoodWorklistEntry;
1191     assert(GoodWorklistEntry &&
1192            "Found a worklist entry without a corresponding map entry!");
1193
1194     // If N has no uses, it is dead.  Make sure to revisit all N's operands once
1195     // N is deleted from the DAG, since they too may now be dead or may have a
1196     // reduced number of uses, allowing other xforms.
1197     if (recursivelyDeleteUnusedNodes(N))
1198       continue;
1199
1200     WorklistRemover DeadNodes(*this);
1201
1202     // If this combine is running after legalizing the DAG, re-legalize any
1203     // nodes pulled off the worklist.
1204     if (Level == AfterLegalizeDAG) {
1205       SmallSetVector<SDNode *, 16> UpdatedNodes;
1206       bool NIsValid = DAG.LegalizeOp(N, UpdatedNodes);
1207
1208       for (SDNode *LN : UpdatedNodes) {
1209         AddToWorklist(LN);
1210         AddUsersToWorklist(LN);
1211       }
1212       if (!NIsValid)
1213         continue;
1214     }
1215
1216     DEBUG(dbgs() << "\nCombining: "; N->dump(&DAG));
1217
1218     // Add any operands of the new node which have not yet been combined to the
1219     // worklist as well. Because the worklist uniques things already, this
1220     // won't repeatedly process the same operand.
1221     CombinedNodes.insert(N);
1222     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1223       if (!CombinedNodes.count(N->getOperand(i).getNode()))
1224         AddToWorklist(N->getOperand(i).getNode());
1225
1226     SDValue RV = combine(N);
1227
1228     if (!RV.getNode())
1229       continue;
1230
1231     ++NodesCombined;
1232
1233     // If we get back the same node we passed in, rather than a new node or
1234     // zero, we know that the node must have defined multiple values and
1235     // CombineTo was used.  Since CombineTo takes care of the worklist
1236     // mechanics for us, we have no work to do in this case.
1237     if (RV.getNode() == N)
1238       continue;
1239
1240     assert(N->getOpcode() != ISD::DELETED_NODE &&
1241            RV.getNode()->getOpcode() != ISD::DELETED_NODE &&
1242            "Node was deleted but visit returned new node!");
1243
1244     DEBUG(dbgs() << " ... into: ";
1245           RV.getNode()->dump(&DAG));
1246
1247     // Transfer debug value.
1248     DAG.TransferDbgValues(SDValue(N, 0), RV);
1249     if (N->getNumValues() == RV.getNode()->getNumValues())
1250       DAG.ReplaceAllUsesWith(N, RV.getNode());
1251     else {
1252       assert(N->getValueType(0) == RV.getValueType() &&
1253              N->getNumValues() == 1 && "Type mismatch");
1254       SDValue OpV = RV;
1255       DAG.ReplaceAllUsesWith(N, &OpV);
1256     }
1257
1258     // Push the new node and any users onto the worklist
1259     AddToWorklist(RV.getNode());
1260     AddUsersToWorklist(RV.getNode());
1261
1262     // Finally, if the node is now dead, remove it from the graph.  The node
1263     // may not be dead if the replacement process recursively simplified to
1264     // something else needing this node. This will also take care of adding any
1265     // operands which have lost a user to the worklist.
1266     recursivelyDeleteUnusedNodes(N);
1267   }
1268
1269   // If the root changed (e.g. it was a dead load, update the root).
1270   DAG.setRoot(Dummy.getValue());
1271   DAG.RemoveDeadNodes();
1272 }
1273
1274 SDValue DAGCombiner::visit(SDNode *N) {
1275   switch (N->getOpcode()) {
1276   default: break;
1277   case ISD::TokenFactor:        return visitTokenFactor(N);
1278   case ISD::MERGE_VALUES:       return visitMERGE_VALUES(N);
1279   case ISD::ADD:                return visitADD(N);
1280   case ISD::SUB:                return visitSUB(N);
1281   case ISD::ADDC:               return visitADDC(N);
1282   case ISD::SUBC:               return visitSUBC(N);
1283   case ISD::ADDE:               return visitADDE(N);
1284   case ISD::SUBE:               return visitSUBE(N);
1285   case ISD::MUL:                return visitMUL(N);
1286   case ISD::SDIV:               return visitSDIV(N);
1287   case ISD::UDIV:               return visitUDIV(N);
1288   case ISD::SREM:               return visitSREM(N);
1289   case ISD::UREM:               return visitUREM(N);
1290   case ISD::MULHU:              return visitMULHU(N);
1291   case ISD::MULHS:              return visitMULHS(N);
1292   case ISD::SMUL_LOHI:          return visitSMUL_LOHI(N);
1293   case ISD::UMUL_LOHI:          return visitUMUL_LOHI(N);
1294   case ISD::SMULO:              return visitSMULO(N);
1295   case ISD::UMULO:              return visitUMULO(N);
1296   case ISD::SDIVREM:            return visitSDIVREM(N);
1297   case ISD::UDIVREM:            return visitUDIVREM(N);
1298   case ISD::AND:                return visitAND(N);
1299   case ISD::OR:                 return visitOR(N);
1300   case ISD::XOR:                return visitXOR(N);
1301   case ISD::SHL:                return visitSHL(N);
1302   case ISD::SRA:                return visitSRA(N);
1303   case ISD::SRL:                return visitSRL(N);
1304   case ISD::ROTR:
1305   case ISD::ROTL:               return visitRotate(N);
1306   case ISD::CTLZ:               return visitCTLZ(N);
1307   case ISD::CTLZ_ZERO_UNDEF:    return visitCTLZ_ZERO_UNDEF(N);
1308   case ISD::CTTZ:               return visitCTTZ(N);
1309   case ISD::CTTZ_ZERO_UNDEF:    return visitCTTZ_ZERO_UNDEF(N);
1310   case ISD::CTPOP:              return visitCTPOP(N);
1311   case ISD::SELECT:             return visitSELECT(N);
1312   case ISD::VSELECT:            return visitVSELECT(N);
1313   case ISD::SELECT_CC:          return visitSELECT_CC(N);
1314   case ISD::SETCC:              return visitSETCC(N);
1315   case ISD::SIGN_EXTEND:        return visitSIGN_EXTEND(N);
1316   case ISD::ZERO_EXTEND:        return visitZERO_EXTEND(N);
1317   case ISD::ANY_EXTEND:         return visitANY_EXTEND(N);
1318   case ISD::SIGN_EXTEND_INREG:  return visitSIGN_EXTEND_INREG(N);
1319   case ISD::TRUNCATE:           return visitTRUNCATE(N);
1320   case ISD::BITCAST:            return visitBITCAST(N);
1321   case ISD::BUILD_PAIR:         return visitBUILD_PAIR(N);
1322   case ISD::FADD:               return visitFADD(N);
1323   case ISD::FSUB:               return visitFSUB(N);
1324   case ISD::FMUL:               return visitFMUL(N);
1325   case ISD::FMA:                return visitFMA(N);
1326   case ISD::FDIV:               return visitFDIV(N);
1327   case ISD::FREM:               return visitFREM(N);
1328   case ISD::FSQRT:              return visitFSQRT(N);
1329   case ISD::FCOPYSIGN:          return visitFCOPYSIGN(N);
1330   case ISD::SINT_TO_FP:         return visitSINT_TO_FP(N);
1331   case ISD::UINT_TO_FP:         return visitUINT_TO_FP(N);
1332   case ISD::FP_TO_SINT:         return visitFP_TO_SINT(N);
1333   case ISD::FP_TO_UINT:         return visitFP_TO_UINT(N);
1334   case ISD::FP_ROUND:           return visitFP_ROUND(N);
1335   case ISD::FP_ROUND_INREG:     return visitFP_ROUND_INREG(N);
1336   case ISD::FP_EXTEND:          return visitFP_EXTEND(N);
1337   case ISD::FNEG:               return visitFNEG(N);
1338   case ISD::FABS:               return visitFABS(N);
1339   case ISD::FFLOOR:             return visitFFLOOR(N);
1340   case ISD::FMINNUM:            return visitFMINNUM(N);
1341   case ISD::FMAXNUM:            return visitFMAXNUM(N);
1342   case ISD::FCEIL:              return visitFCEIL(N);
1343   case ISD::FTRUNC:             return visitFTRUNC(N);
1344   case ISD::BRCOND:             return visitBRCOND(N);
1345   case ISD::BR_CC:              return visitBR_CC(N);
1346   case ISD::LOAD:               return visitLOAD(N);
1347   case ISD::STORE:              return visitSTORE(N);
1348   case ISD::INSERT_VECTOR_ELT:  return visitINSERT_VECTOR_ELT(N);
1349   case ISD::EXTRACT_VECTOR_ELT: return visitEXTRACT_VECTOR_ELT(N);
1350   case ISD::BUILD_VECTOR:       return visitBUILD_VECTOR(N);
1351   case ISD::CONCAT_VECTORS:     return visitCONCAT_VECTORS(N);
1352   case ISD::EXTRACT_SUBVECTOR:  return visitEXTRACT_SUBVECTOR(N);
1353   case ISD::VECTOR_SHUFFLE:     return visitVECTOR_SHUFFLE(N);
1354   case ISD::INSERT_SUBVECTOR:   return visitINSERT_SUBVECTOR(N);
1355   case ISD::MLOAD:              return visitMLOAD(N);
1356   case ISD::MSTORE:             return visitMSTORE(N);
1357   }
1358   return SDValue();
1359 }
1360
1361 SDValue DAGCombiner::combine(SDNode *N) {
1362   SDValue RV = visit(N);
1363
1364   // If nothing happened, try a target-specific DAG combine.
1365   if (!RV.getNode()) {
1366     assert(N->getOpcode() != ISD::DELETED_NODE &&
1367            "Node was deleted but visit returned NULL!");
1368
1369     if (N->getOpcode() >= ISD::BUILTIN_OP_END ||
1370         TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode())) {
1371
1372       // Expose the DAG combiner to the target combiner impls.
1373       TargetLowering::DAGCombinerInfo
1374         DagCombineInfo(DAG, Level, false, this);
1375
1376       RV = TLI.PerformDAGCombine(N, DagCombineInfo);
1377     }
1378   }
1379
1380   // If nothing happened still, try promoting the operation.
1381   if (!RV.getNode()) {
1382     switch (N->getOpcode()) {
1383     default: break;
1384     case ISD::ADD:
1385     case ISD::SUB:
1386     case ISD::MUL:
1387     case ISD::AND:
1388     case ISD::OR:
1389     case ISD::XOR:
1390       RV = PromoteIntBinOp(SDValue(N, 0));
1391       break;
1392     case ISD::SHL:
1393     case ISD::SRA:
1394     case ISD::SRL:
1395       RV = PromoteIntShiftOp(SDValue(N, 0));
1396       break;
1397     case ISD::SIGN_EXTEND:
1398     case ISD::ZERO_EXTEND:
1399     case ISD::ANY_EXTEND:
1400       RV = PromoteExtend(SDValue(N, 0));
1401       break;
1402     case ISD::LOAD:
1403       if (PromoteLoad(SDValue(N, 0)))
1404         RV = SDValue(N, 0);
1405       break;
1406     }
1407   }
1408
1409   // If N is a commutative binary node, try commuting it to enable more
1410   // sdisel CSE.
1411   if (!RV.getNode() && SelectionDAG::isCommutativeBinOp(N->getOpcode()) &&
1412       N->getNumValues() == 1) {
1413     SDValue N0 = N->getOperand(0);
1414     SDValue N1 = N->getOperand(1);
1415
1416     // Constant operands are canonicalized to RHS.
1417     if (isa<ConstantSDNode>(N0) || !isa<ConstantSDNode>(N1)) {
1418       SDValue Ops[] = {N1, N0};
1419       SDNode *CSENode;
1420       if (const BinaryWithFlagsSDNode *BinNode =
1421               dyn_cast<BinaryWithFlagsSDNode>(N)) {
1422         CSENode = DAG.getNodeIfExists(
1423             N->getOpcode(), N->getVTList(), Ops, BinNode->hasNoUnsignedWrap(),
1424             BinNode->hasNoSignedWrap(), BinNode->isExact());
1425       } else {
1426         CSENode = DAG.getNodeIfExists(N->getOpcode(), N->getVTList(), Ops);
1427       }
1428       if (CSENode)
1429         return SDValue(CSENode, 0);
1430     }
1431   }
1432
1433   return RV;
1434 }
1435
1436 /// Given a node, return its input chain if it has one, otherwise return a null
1437 /// sd operand.
1438 static SDValue getInputChainForNode(SDNode *N) {
1439   if (unsigned NumOps = N->getNumOperands()) {
1440     if (N->getOperand(0).getValueType() == MVT::Other)
1441       return N->getOperand(0);
1442     if (N->getOperand(NumOps-1).getValueType() == MVT::Other)
1443       return N->getOperand(NumOps-1);
1444     for (unsigned i = 1; i < NumOps-1; ++i)
1445       if (N->getOperand(i).getValueType() == MVT::Other)
1446         return N->getOperand(i);
1447   }
1448   return SDValue();
1449 }
1450
1451 SDValue DAGCombiner::visitTokenFactor(SDNode *N) {
1452   // If N has two operands, where one has an input chain equal to the other,
1453   // the 'other' chain is redundant.
1454   if (N->getNumOperands() == 2) {
1455     if (getInputChainForNode(N->getOperand(0).getNode()) == N->getOperand(1))
1456       return N->getOperand(0);
1457     if (getInputChainForNode(N->getOperand(1).getNode()) == N->getOperand(0))
1458       return N->getOperand(1);
1459   }
1460
1461   SmallVector<SDNode *, 8> TFs;     // List of token factors to visit.
1462   SmallVector<SDValue, 8> Ops;    // Ops for replacing token factor.
1463   SmallPtrSet<SDNode*, 16> SeenOps;
1464   bool Changed = false;             // If we should replace this token factor.
1465
1466   // Start out with this token factor.
1467   TFs.push_back(N);
1468
1469   // Iterate through token factors.  The TFs grows when new token factors are
1470   // encountered.
1471   for (unsigned i = 0; i < TFs.size(); ++i) {
1472     SDNode *TF = TFs[i];
1473
1474     // Check each of the operands.
1475     for (unsigned i = 0, ie = TF->getNumOperands(); i != ie; ++i) {
1476       SDValue Op = TF->getOperand(i);
1477
1478       switch (Op.getOpcode()) {
1479       case ISD::EntryToken:
1480         // Entry tokens don't need to be added to the list. They are
1481         // rededundant.
1482         Changed = true;
1483         break;
1484
1485       case ISD::TokenFactor:
1486         if (Op.hasOneUse() &&
1487             std::find(TFs.begin(), TFs.end(), Op.getNode()) == TFs.end()) {
1488           // Queue up for processing.
1489           TFs.push_back(Op.getNode());
1490           // Clean up in case the token factor is removed.
1491           AddToWorklist(Op.getNode());
1492           Changed = true;
1493           break;
1494         }
1495         // Fall thru
1496
1497       default:
1498         // Only add if it isn't already in the list.
1499         if (SeenOps.insert(Op.getNode()).second)
1500           Ops.push_back(Op);
1501         else
1502           Changed = true;
1503         break;
1504       }
1505     }
1506   }
1507
1508   SDValue Result;
1509
1510   // If we've change things around then replace token factor.
1511   if (Changed) {
1512     if (Ops.empty()) {
1513       // The entry token is the only possible outcome.
1514       Result = DAG.getEntryNode();
1515     } else {
1516       // New and improved token factor.
1517       Result = DAG.getNode(ISD::TokenFactor, SDLoc(N), MVT::Other, Ops);
1518     }
1519
1520     // Don't add users to work list.
1521     return CombineTo(N, Result, false);
1522   }
1523
1524   return Result;
1525 }
1526
1527 /// MERGE_VALUES can always be eliminated.
1528 SDValue DAGCombiner::visitMERGE_VALUES(SDNode *N) {
1529   WorklistRemover DeadNodes(*this);
1530   // Replacing results may cause a different MERGE_VALUES to suddenly
1531   // be CSE'd with N, and carry its uses with it. Iterate until no
1532   // uses remain, to ensure that the node can be safely deleted.
1533   // First add the users of this node to the work list so that they
1534   // can be tried again once they have new operands.
1535   AddUsersToWorklist(N);
1536   do {
1537     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1538       DAG.ReplaceAllUsesOfValueWith(SDValue(N, i), N->getOperand(i));
1539   } while (!N->use_empty());
1540   deleteAndRecombine(N);
1541   return SDValue(N, 0);   // Return N so it doesn't get rechecked!
1542 }
1543
1544 SDValue DAGCombiner::visitADD(SDNode *N) {
1545   SDValue N0 = N->getOperand(0);
1546   SDValue N1 = N->getOperand(1);
1547   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1548   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1549   EVT VT = N0.getValueType();
1550
1551   // fold vector ops
1552   if (VT.isVector()) {
1553     SDValue FoldedVOp = SimplifyVBinOp(N);
1554     if (FoldedVOp.getNode()) return FoldedVOp;
1555
1556     // fold (add x, 0) -> x, vector edition
1557     if (ISD::isBuildVectorAllZeros(N1.getNode()))
1558       return N0;
1559     if (ISD::isBuildVectorAllZeros(N0.getNode()))
1560       return N1;
1561   }
1562
1563   // fold (add x, undef) -> undef
1564   if (N0.getOpcode() == ISD::UNDEF)
1565     return N0;
1566   if (N1.getOpcode() == ISD::UNDEF)
1567     return N1;
1568   // fold (add c1, c2) -> c1+c2
1569   if (N0C && N1C)
1570     return DAG.FoldConstantArithmetic(ISD::ADD, VT, N0C, N1C);
1571   // canonicalize constant to RHS
1572   if (N0C && !N1C)
1573     return DAG.getNode(ISD::ADD, SDLoc(N), VT, N1, N0);
1574   // fold (add x, 0) -> x
1575   if (N1C && N1C->isNullValue())
1576     return N0;
1577   // fold (add Sym, c) -> Sym+c
1578   if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(N0))
1579     if (!LegalOperations && TLI.isOffsetFoldingLegal(GA) && N1C &&
1580         GA->getOpcode() == ISD::GlobalAddress)
1581       return DAG.getGlobalAddress(GA->getGlobal(), SDLoc(N1C), VT,
1582                                   GA->getOffset() +
1583                                     (uint64_t)N1C->getSExtValue());
1584   // fold ((c1-A)+c2) -> (c1+c2)-A
1585   if (N1C && N0.getOpcode() == ISD::SUB)
1586     if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getOperand(0)))
1587       return DAG.getNode(ISD::SUB, SDLoc(N), VT,
1588                          DAG.getConstant(N1C->getAPIntValue()+
1589                                          N0C->getAPIntValue(), VT),
1590                          N0.getOperand(1));
1591   // reassociate add
1592   SDValue RADD = ReassociateOps(ISD::ADD, SDLoc(N), N0, N1);
1593   if (RADD.getNode())
1594     return RADD;
1595   // fold ((0-A) + B) -> B-A
1596   if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) &&
1597       cast<ConstantSDNode>(N0.getOperand(0))->isNullValue())
1598     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N1, N0.getOperand(1));
1599   // fold (A + (0-B)) -> A-B
1600   if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) &&
1601       cast<ConstantSDNode>(N1.getOperand(0))->isNullValue())
1602     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N0, N1.getOperand(1));
1603   // fold (A+(B-A)) -> B
1604   if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1))
1605     return N1.getOperand(0);
1606   // fold ((B-A)+A) -> B
1607   if (N0.getOpcode() == ISD::SUB && N1 == N0.getOperand(1))
1608     return N0.getOperand(0);
1609   // fold (A+(B-(A+C))) to (B-C)
1610   if (N1.getOpcode() == ISD::SUB && N1.getOperand(1).getOpcode() == ISD::ADD &&
1611       N0 == N1.getOperand(1).getOperand(0))
1612     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N1.getOperand(0),
1613                        N1.getOperand(1).getOperand(1));
1614   // fold (A+(B-(C+A))) to (B-C)
1615   if (N1.getOpcode() == ISD::SUB && N1.getOperand(1).getOpcode() == ISD::ADD &&
1616       N0 == N1.getOperand(1).getOperand(1))
1617     return DAG.getNode(ISD::SUB, SDLoc(N), VT, N1.getOperand(0),
1618                        N1.getOperand(1).getOperand(0));
1619   // fold (A+((B-A)+or-C)) to (B+or-C)
1620   if ((N1.getOpcode() == ISD::SUB || N1.getOpcode() == ISD::ADD) &&
1621       N1.getOperand(0).getOpcode() == ISD::SUB &&
1622       N0 == N1.getOperand(0).getOperand(1))
1623     return DAG.getNode(N1.getOpcode(), SDLoc(N), VT,
1624                        N1.getOperand(0).getOperand(0), N1.getOperand(1));
1625
1626   // fold (A-B)+(C-D) to (A+C)-(B+D) when A or C is constant
1627   if (N0.getOpcode() == ISD::SUB && N1.getOpcode() == ISD::SUB) {
1628     SDValue N00 = N0.getOperand(0);
1629     SDValue N01 = N0.getOperand(1);
1630     SDValue N10 = N1.getOperand(0);
1631     SDValue N11 = N1.getOperand(1);
1632
1633     if (isa<ConstantSDNode>(N00) || isa<ConstantSDNode>(N10))
1634       return DAG.getNode(ISD::SUB, SDLoc(N), VT,
1635                          DAG.getNode(ISD::ADD, SDLoc(N0), VT, N00, N10),
1636                          DAG.getNode(ISD::ADD, SDLoc(N1), VT, N01, N11));
1637   }
1638
1639   if (!VT.isVector() && SimplifyDemandedBits(SDValue(N, 0)))
1640     return SDValue(N, 0);
1641
1642   // fold (a+b) -> (a|b) iff a and b share no bits.
1643   if (VT.isInteger() && !VT.isVector()) {
1644     APInt LHSZero, LHSOne;
1645     APInt RHSZero, RHSOne;
1646     DAG.computeKnownBits(N0, LHSZero, LHSOne);
1647
1648     if (LHSZero.getBoolValue()) {
1649       DAG.computeKnownBits(N1, RHSZero, RHSOne);
1650
1651       // If all possibly-set bits on the LHS are clear on the RHS, return an OR.
1652       // If all possibly-set bits on the RHS are clear on the LHS, return an OR.
1653       if ((RHSZero & ~LHSZero) == ~LHSZero || (LHSZero & ~RHSZero) == ~RHSZero){
1654         if (!LegalOperations || TLI.isOperationLegal(ISD::OR, VT))
1655           return DAG.getNode(ISD::OR, SDLoc(N), VT, N0, N1);
1656       }
1657     }
1658   }
1659
1660   // fold (add x, shl(0 - y, n)) -> sub(x, shl(y, n))
1661   if (N1.getOpcode() == ISD::SHL &&
1662       N1.getOperand(0).getOpcode() == ISD::SUB)
1663     if (ConstantSDNode *C =
1664           dyn_cast<ConstantSDNode>(N1.getOperand(0).getOperand(0)))
1665       if (C->getAPIntValue() == 0)
1666         return DAG.getNode(ISD::SUB, SDLoc(N), VT, N0,
1667                            DAG.getNode(ISD::SHL, SDLoc(N), VT,
1668                                        N1.getOperand(0).getOperand(1),
1669                                        N1.getOperand(1)));
1670   if (N0.getOpcode() == ISD::SHL &&
1671       N0.getOperand(0).getOpcode() == ISD::SUB)
1672     if (ConstantSDNode *C =
1673           dyn_cast<ConstantSDNode>(N0.getOperand(0).getOperand(0)))
1674       if (C->getAPIntValue() == 0)
1675         return DAG.getNode(ISD::SUB, SDLoc(N), VT, N1,
1676                            DAG.getNode(ISD::SHL, SDLoc(N), VT,
1677                                        N0.getOperand(0).getOperand(1),
1678                                        N0.getOperand(1)));
1679
1680   if (N1.getOpcode() == ISD::AND) {
1681     SDValue AndOp0 = N1.getOperand(0);
1682     ConstantSDNode *AndOp1 = dyn_cast<ConstantSDNode>(N1->getOperand(1));
1683     unsigned NumSignBits = DAG.ComputeNumSignBits(AndOp0);
1684     unsigned DestBits = VT.getScalarType().getSizeInBits();
1685
1686     // (add z, (and (sbbl x, x), 1)) -> (sub z, (sbbl x, x))
1687     // and similar xforms where the inner op is either ~0 or 0.
1688     if (NumSignBits == DestBits && AndOp1 && AndOp1->isOne()) {
1689       SDLoc DL(N);
1690       return DAG.getNode(ISD::SUB, DL, VT, N->getOperand(0), AndOp0);
1691     }
1692   }
1693
1694   // add (sext i1), X -> sub X, (zext i1)
1695   if (N0.getOpcode() == ISD::SIGN_EXTEND &&
1696       N0.getOperand(0).getValueType() == MVT::i1 &&
1697       !TLI.isOperationLegal(ISD::SIGN_EXTEND, MVT::i1)) {
1698     SDLoc DL(N);
1699     SDValue ZExt = DAG.getNode(ISD::ZERO_EXTEND, DL, VT, N0.getOperand(0));
1700     return DAG.getNode(ISD::SUB, DL, VT, N1, ZExt);
1701   }
1702
1703   // add X, (sextinreg Y i1) -> sub X, (and Y 1)
1704   if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
1705     VTSDNode *TN = cast<VTSDNode>(N1.getOperand(1));
1706     if (TN->getVT() == MVT::i1) {
1707       SDLoc DL(N);
1708       SDValue ZExt = DAG.getNode(ISD::AND, DL, VT, N1.getOperand(0),
1709                                  DAG.getConstant(1, VT));
1710       return DAG.getNode(ISD::SUB, DL, VT, N0, ZExt);
1711     }
1712   }
1713
1714   return SDValue();
1715 }
1716
1717 SDValue DAGCombiner::visitADDC(SDNode *N) {
1718   SDValue N0 = N->getOperand(0);
1719   SDValue N1 = N->getOperand(1);
1720   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1721   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1722   EVT VT = N0.getValueType();
1723
1724   // If the flag result is dead, turn this into an ADD.
1725   if (!N->hasAnyUseOfValue(1))
1726     return CombineTo(N, DAG.getNode(ISD::ADD, SDLoc(N), VT, N0, N1),
1727                      DAG.getNode(ISD::CARRY_FALSE,
1728                                  SDLoc(N), MVT::Glue));
1729
1730   // canonicalize constant to RHS.
1731   if (N0C && !N1C)
1732     return DAG.getNode(ISD::ADDC, SDLoc(N), N->getVTList(), N1, N0);
1733
1734   // fold (addc x, 0) -> x + no carry out
1735   if (N1C && N1C->isNullValue())
1736     return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE,
1737                                         SDLoc(N), MVT::Glue));
1738
1739   // fold (addc a, b) -> (or a, b), CARRY_FALSE iff a and b share no bits.
1740   APInt LHSZero, LHSOne;
1741   APInt RHSZero, RHSOne;
1742   DAG.computeKnownBits(N0, LHSZero, LHSOne);
1743
1744   if (LHSZero.getBoolValue()) {
1745     DAG.computeKnownBits(N1, RHSZero, RHSOne);
1746
1747     // If all possibly-set bits on the LHS are clear on the RHS, return an OR.
1748     // If all possibly-set bits on the RHS are clear on the LHS, return an OR.
1749     if ((RHSZero & ~LHSZero) == ~LHSZero || (LHSZero & ~RHSZero) == ~RHSZero)
1750       return CombineTo(N, DAG.getNode(ISD::OR, SDLoc(N), VT, N0, N1),
1751                        DAG.getNode(ISD::CARRY_FALSE,
1752                                    SDLoc(N), MVT::Glue));
1753   }
1754
1755   return SDValue();
1756 }
1757
1758 SDValue DAGCombiner::visitADDE(SDNode *N) {
1759   SDValue N0 = N->getOperand(0);
1760   SDValue N1 = N->getOperand(1);
1761   SDValue CarryIn = N->getOperand(2);
1762   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1763   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1764
1765   // canonicalize constant to RHS
1766   if (N0C && !N1C)
1767     return DAG.getNode(ISD::ADDE, SDLoc(N), N->getVTList(),
1768                        N1, N0, CarryIn);
1769
1770   // fold (adde x, y, false) -> (addc x, y)
1771   if (CarryIn.getOpcode() == ISD::CARRY_FALSE)
1772     return DAG.getNode(ISD::ADDC, SDLoc(N), N->getVTList(), N0, N1);
1773
1774   return SDValue();
1775 }
1776
1777 // Since it may not be valid to emit a fold to zero for vector initializers
1778 // check if we can before folding.
1779 static SDValue tryFoldToZero(SDLoc DL, const TargetLowering &TLI, EVT VT,
1780                              SelectionDAG &DAG,
1781                              bool LegalOperations, bool LegalTypes) {
1782   if (!VT.isVector())
1783     return DAG.getConstant(0, VT);
1784   if (!LegalOperations || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT))
1785     return DAG.getConstant(0, VT);
1786   return SDValue();
1787 }
1788
1789 SDValue DAGCombiner::visitSUB(SDNode *N) {
1790   SDValue N0 = N->getOperand(0);
1791   SDValue N1 = N->getOperand(1);
1792   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getNode());
1793   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode());
1794   ConstantSDNode *N1C1 = N1.getOpcode() != ISD::ADD ? nullptr :
1795     dyn_cast<ConstantSDNode>(N1.getOperand(1).getNode());
1796   EVT VT = N0.getValueType();
1797
1798   // fold vector ops
1799   if (VT.isVector()) {
1800     SDValue FoldedVOp = SimplifyVBinOp(N);
1801     if (FoldedVOp.getNode()) return FoldedVOp;
1802
1803     // fold (sub x, 0) -> x, vector edition
1804     if (ISD::isBuildVectorAllZeros(N1.getNode()))
1805       return N0;
1806   }
1807
1808   // fold (sub x, x) -> 0
1809   // FIXME: Refactor this and xor and other similar operations together.
1810   if (N0 == N1)
1811     return tryFoldToZero(SDLoc(N), TLI, VT, DAG, LegalOperations, LegalTypes);
1812   // fold (sub c1, c2) -> c1-c2
1813   if (N0C && N1C)
1814     return DAG.FoldConstantArithmetic(ISD::SUB, VT, N0C, N1C);
1815   // fold (sub x, c) -> (add x, -c)
1816   if (N1C)
1817     return DAG.getNode(ISD::ADD, SDLoc(N), VT, N0,
1818                        DAG.getConstant(-N1C->getAPIntValue(), VT));
1819   // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1)
1820   if (N0C && N0C->isAllOnesValue())
1821     return DAG.getNode(ISD::XOR, SDLoc(N), VT, N1, N0);
1822   // fold A-(A-B) -> B
1823   if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(0))
1824     return N1.getOperand(1);
1825   // fold (A+B)-A -> B
1826   if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1)
1827     return N0.getOperand(1);
1828   // fold (A+B)-B -> A
1829   if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1)
1830     return N0.getOperand(0);
1831   // fold C2-(A+C1) -> (C2-C1)-A
1832   if (N1.getOpcode() == ISD::ADD && N0C && N1C1) {
1833     SDValue NewC = DAG.getConstant(N0C->getAPIntValue() - N1C1->getAPIntValue(),
1834                                    VT);
1835     return DAG.getNode(ISD::SUB, SDLoc(N), VT, NewC,
1836                        N1.getOperand(0));
1837   }
1838   // fold ((A+(B+or-C))-B) -> A+or-C
1839   if (N0.getOpcode() == ISD::ADD &&
1840       (N0.getOperand(1).getOpcode() == ISD::SUB ||
1841        N0.getOperand(1).getOpcode() == ISD::ADD) &&
1842       N0.getOperand(1).getOperand(0) == N1)
1843     return DAG.getNode(N0.getOperand(1).getOpcode(), SDLoc(N), VT,
1844                        N0.getOperand(0), N0.getOperand(1).getOperand(1));
1845   // fold ((A+(C+B))-B) -> A+C
1846   if (N0.getOpcode() == ISD::ADD &&
1847       N0.getOperand(1).getOpcode() == ISD::ADD &&
1848       N0.getOperand(1).getOperand(1) == N1)
1849     return DAG.getNode(ISD::ADD, SDLoc(N), VT,
1850                        N0.getOperand(0), N0.getOperand(1).getOperand(0));
1851   // fold ((A-(B-C))-C) -> A-B
1852   if (N0.getOpcode() == ISD::SUB &&
1853       N0.getOperand(1).getOpcode() == ISD::SUB &&
1854       N0.getOperand(1).getOperand(1) == N1)
1855     return DAG.getNode(ISD::SUB, SDLoc(N), VT,
1856                        N0.getOperand(0), N0.getOperand(1).getOperand(0));
1857
1858   // If either operand of a sub is undef, the result is undef
1859   if (N0.getOpcode() == ISD::UNDEF)
1860     return N0;
1861   if (N1.getOpcode() == ISD::UNDEF)
1862     return N1;
1863
1864   // If the relocation model supports it, consider symbol offsets.
1865   if (GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(N0))
1866     if (!LegalOperations && TLI.isOffsetFoldingLegal(GA)) {
1867       // fold (sub Sym, c) -> Sym-c
1868       if (N1C && GA->getOpcode() == ISD::GlobalAddress)
1869         return DAG.getGlobalAddress(GA->getGlobal(), SDLoc(N1C), VT,
1870                                     GA->getOffset() -
1871                                       (uint64_t)N1C->getSExtValue());
1872       // fold (sub Sym+c1, Sym+c2) -> c1-c2
1873       if (GlobalAddressSDNode *GB = dyn_cast<GlobalAddressSDNode>(N1))
1874         if (GA->getGlobal() == GB->getGlobal())
1875           return DAG.getConstant((uint64_t)GA->getOffset() - GB->getOffset(),
1876                                  VT);
1877     }
1878
1879   // sub X, (sextinreg Y i1) -> add X, (and Y 1)
1880   if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
1881     VTSDNode *TN = cast<VTSDNode>(N1.getOperand(1));
1882     if (TN->getVT() == MVT::i1) {
1883       SDLoc DL(N);
1884       SDValue ZExt = DAG.getNode(ISD::AND, DL, VT, N1.getOperand(0),
1885                                  DAG.getConstant(1, VT));
1886       return DAG.getNode(ISD::ADD, DL, VT, N0, ZExt);
1887     }
1888   }
1889
1890   return SDValue();
1891 }
1892
1893 SDValue DAGCombiner::visitSUBC(SDNode *N) {
1894   SDValue N0 = N->getOperand(0);
1895   SDValue N1 = N->getOperand(1);
1896   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1897   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1898   EVT VT = N0.getValueType();
1899
1900   // If the flag result is dead, turn this into an SUB.
1901   if (!N->hasAnyUseOfValue(1))
1902     return CombineTo(N, DAG.getNode(ISD::SUB, SDLoc(N), VT, N0, N1),
1903                      DAG.getNode(ISD::CARRY_FALSE, SDLoc(N),
1904                                  MVT::Glue));
1905
1906   // fold (subc x, x) -> 0 + no borrow
1907   if (N0 == N1)
1908     return CombineTo(N, DAG.getConstant(0, VT),
1909                      DAG.getNode(ISD::CARRY_FALSE, SDLoc(N),
1910                                  MVT::Glue));
1911
1912   // fold (subc x, 0) -> x + no borrow
1913   if (N1C && N1C->isNullValue())
1914     return CombineTo(N, N0, DAG.getNode(ISD::CARRY_FALSE, SDLoc(N),
1915                                         MVT::Glue));
1916
1917   // Canonicalize (sub -1, x) -> ~x, i.e. (xor x, -1) + no borrow
1918   if (N0C && N0C->isAllOnesValue())
1919     return CombineTo(N, DAG.getNode(ISD::XOR, SDLoc(N), VT, N1, N0),
1920                      DAG.getNode(ISD::CARRY_FALSE, SDLoc(N),
1921                                  MVT::Glue));
1922
1923   return SDValue();
1924 }
1925
1926 SDValue DAGCombiner::visitSUBE(SDNode *N) {
1927   SDValue N0 = N->getOperand(0);
1928   SDValue N1 = N->getOperand(1);
1929   SDValue CarryIn = N->getOperand(2);
1930
1931   // fold (sube x, y, false) -> (subc x, y)
1932   if (CarryIn.getOpcode() == ISD::CARRY_FALSE)
1933     return DAG.getNode(ISD::SUBC, SDLoc(N), N->getVTList(), N0, N1);
1934
1935   return SDValue();
1936 }
1937
1938 SDValue DAGCombiner::visitMUL(SDNode *N) {
1939   SDValue N0 = N->getOperand(0);
1940   SDValue N1 = N->getOperand(1);
1941   EVT VT = N0.getValueType();
1942
1943   // fold (mul x, undef) -> 0
1944   if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
1945     return DAG.getConstant(0, VT);
1946
1947   bool N0IsConst = false;
1948   bool N1IsConst = false;
1949   APInt ConstValue0, ConstValue1;
1950   // fold vector ops
1951   if (VT.isVector()) {
1952     SDValue FoldedVOp = SimplifyVBinOp(N);
1953     if (FoldedVOp.getNode()) return FoldedVOp;
1954
1955     N0IsConst = isConstantSplatVector(N0.getNode(), ConstValue0);
1956     N1IsConst = isConstantSplatVector(N1.getNode(), ConstValue1);
1957   } else {
1958     N0IsConst = dyn_cast<ConstantSDNode>(N0) != nullptr;
1959     ConstValue0 = N0IsConst ? (dyn_cast<ConstantSDNode>(N0))->getAPIntValue()
1960                             : APInt();
1961     N1IsConst = dyn_cast<ConstantSDNode>(N1) != nullptr;
1962     ConstValue1 = N1IsConst ? (dyn_cast<ConstantSDNode>(N1))->getAPIntValue()
1963                             : APInt();
1964   }
1965
1966   // fold (mul c1, c2) -> c1*c2
1967   if (N0IsConst && N1IsConst)
1968     return DAG.FoldConstantArithmetic(ISD::MUL, VT, N0.getNode(), N1.getNode());
1969
1970   // canonicalize constant to RHS
1971   if (N0IsConst && !N1IsConst)
1972     return DAG.getNode(ISD::MUL, SDLoc(N), VT, N1, N0);
1973   // fold (mul x, 0) -> 0
1974   if (N1IsConst && ConstValue1 == 0)
1975     return N1;
1976   // We require a splat of the entire scalar bit width for non-contiguous
1977   // bit patterns.
1978   bool IsFullSplat =
1979     ConstValue1.getBitWidth() == VT.getScalarType().getSizeInBits();
1980   // fold (mul x, 1) -> x
1981   if (N1IsConst && ConstValue1 == 1 && IsFullSplat)
1982     return N0;
1983   // fold (mul x, -1) -> 0-x
1984   if (N1IsConst && ConstValue1.isAllOnesValue())
1985     return DAG.getNode(ISD::SUB, SDLoc(N), VT,
1986                        DAG.getConstant(0, VT), N0);
1987   // fold (mul x, (1 << c)) -> x << c
1988   if (N1IsConst && ConstValue1.isPowerOf2() && IsFullSplat)
1989     return DAG.getNode(ISD::SHL, SDLoc(N), VT, N0,
1990                        DAG.getConstant(ConstValue1.logBase2(),
1991                                        getShiftAmountTy(N0.getValueType())));
1992   // fold (mul x, -(1 << c)) -> -(x << c) or (-x) << c
1993   if (N1IsConst && (-ConstValue1).isPowerOf2() && IsFullSplat) {
1994     unsigned Log2Val = (-ConstValue1).logBase2();
1995     // FIXME: If the input is something that is easily negated (e.g. a
1996     // single-use add), we should put the negate there.
1997     return DAG.getNode(ISD::SUB, SDLoc(N), VT,
1998                        DAG.getConstant(0, VT),
1999                        DAG.getNode(ISD::SHL, SDLoc(N), VT, N0,
2000                             DAG.getConstant(Log2Val,
2001                                       getShiftAmountTy(N0.getValueType()))));
2002   }
2003
2004   APInt Val;
2005   // (mul (shl X, c1), c2) -> (mul X, c2 << c1)
2006   if (N1IsConst && N0.getOpcode() == ISD::SHL &&
2007       (isConstantSplatVector(N0.getOperand(1).getNode(), Val) ||
2008                      isa<ConstantSDNode>(N0.getOperand(1)))) {
2009     SDValue C3 = DAG.getNode(ISD::SHL, SDLoc(N), VT,
2010                              N1, N0.getOperand(1));
2011     AddToWorklist(C3.getNode());
2012     return DAG.getNode(ISD::MUL, SDLoc(N), VT,
2013                        N0.getOperand(0), C3);
2014   }
2015
2016   // Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one
2017   // use.
2018   {
2019     SDValue Sh(nullptr,0), Y(nullptr,0);
2020     // Check for both (mul (shl X, C), Y)  and  (mul Y, (shl X, C)).
2021     if (N0.getOpcode() == ISD::SHL &&
2022         (isConstantSplatVector(N0.getOperand(1).getNode(), Val) ||
2023                        isa<ConstantSDNode>(N0.getOperand(1))) &&
2024         N0.getNode()->hasOneUse()) {
2025       Sh = N0; Y = N1;
2026     } else if (N1.getOpcode() == ISD::SHL &&
2027                isa<ConstantSDNode>(N1.getOperand(1)) &&
2028                N1.getNode()->hasOneUse()) {
2029       Sh = N1; Y = N0;
2030     }
2031
2032     if (Sh.getNode()) {
2033       SDValue Mul = DAG.getNode(ISD::MUL, SDLoc(N), VT,
2034                                 Sh.getOperand(0), Y);
2035       return DAG.getNode(ISD::SHL, SDLoc(N), VT,
2036                          Mul, Sh.getOperand(1));
2037     }
2038   }
2039
2040   // fold (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2)
2041   if (N1IsConst && N0.getOpcode() == ISD::ADD && N0.getNode()->hasOneUse() &&
2042       (isConstantSplatVector(N0.getOperand(1).getNode(), Val) ||
2043                      isa<ConstantSDNode>(N0.getOperand(1))))
2044     return DAG.getNode(ISD::ADD, SDLoc(N), VT,
2045                        DAG.getNode(ISD::MUL, SDLoc(N0), VT,
2046                                    N0.getOperand(0), N1),
2047                        DAG.getNode(ISD::MUL, SDLoc(N1), VT,
2048                                    N0.getOperand(1), N1));
2049
2050   // reassociate mul
2051   SDValue RMUL = ReassociateOps(ISD::MUL, SDLoc(N), N0, N1);
2052   if (RMUL.getNode())
2053     return RMUL;
2054
2055   return SDValue();
2056 }
2057
2058 SDValue DAGCombiner::visitSDIV(SDNode *N) {
2059   SDValue N0 = N->getOperand(0);
2060   SDValue N1 = N->getOperand(1);
2061   ConstantSDNode *N0C = isConstOrConstSplat(N0);
2062   ConstantSDNode *N1C = isConstOrConstSplat(N1);
2063   EVT VT = N->getValueType(0);
2064
2065   // fold vector ops
2066   if (VT.isVector()) {
2067     SDValue FoldedVOp = SimplifyVBinOp(N);
2068     if (FoldedVOp.getNode()) return FoldedVOp;
2069   }
2070
2071   // fold (sdiv c1, c2) -> c1/c2
2072   if (N0C && N1C && !N1C->isNullValue())
2073     return DAG.FoldConstantArithmetic(ISD::SDIV, VT, N0C, N1C);
2074   // fold (sdiv X, 1) -> X
2075   if (N1C && N1C->getAPIntValue() == 1LL)
2076     return N0;
2077   // fold (sdiv X, -1) -> 0-X
2078   if (N1C && N1C->isAllOnesValue())
2079     return DAG.getNode(ISD::SUB, SDLoc(N), VT,
2080                        DAG.getConstant(0, VT), N0);
2081   // If we know the sign bits of both operands are zero, strength reduce to a
2082   // udiv instead.  Handles (X&15) /s 4 -> X&15 >> 2
2083   if (!VT.isVector()) {
2084     if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
2085       return DAG.getNode(ISD::UDIV, SDLoc(N), N1.getValueType(),
2086                          N0, N1);
2087   }
2088
2089   // fold (sdiv X, pow2) -> simple ops after legalize
2090   if (N1C && !N1C->isNullValue() && (N1C->getAPIntValue().isPowerOf2() ||
2091                                      (-N1C->getAPIntValue()).isPowerOf2())) {
2092     // If dividing by powers of two is cheap, then don't perform the following
2093     // fold.
2094     if (TLI.isPow2SDivCheap())
2095       return SDValue();
2096
2097     // Target-specific implementation of sdiv x, pow2.
2098     SDValue Res = BuildSDIVPow2(N);
2099     if (Res.getNode())
2100       return Res;
2101
2102     unsigned lg2 = N1C->getAPIntValue().countTrailingZeros();
2103
2104     // Splat the sign bit into the register
2105     SDValue SGN =
2106         DAG.getNode(ISD::SRA, SDLoc(N), VT, N0,
2107                     DAG.getConstant(VT.getScalarSizeInBits() - 1,
2108                                     getShiftAmountTy(N0.getValueType())));
2109     AddToWorklist(SGN.getNode());
2110
2111     // Add (N0 < 0) ? abs2 - 1 : 0;
2112     SDValue SRL =
2113         DAG.getNode(ISD::SRL, SDLoc(N), VT, SGN,
2114                     DAG.getConstant(VT.getScalarSizeInBits() - lg2,
2115                                     getShiftAmountTy(SGN.getValueType())));
2116     SDValue ADD = DAG.getNode(ISD::ADD, SDLoc(N), VT, N0, SRL);
2117     AddToWorklist(SRL.getNode());
2118     AddToWorklist(ADD.getNode());    // Divide by pow2
2119     SDValue SRA = DAG.getNode(ISD::SRA, SDLoc(N), VT, ADD,
2120                   DAG.getConstant(lg2, getShiftAmountTy(ADD.getValueType())));
2121
2122     // If we're dividing by a positive value, we're done.  Otherwise, we must
2123     // negate the result.
2124     if (N1C->getAPIntValue().isNonNegative())
2125       return SRA;
2126
2127     AddToWorklist(SRA.getNode());
2128     return DAG.getNode(ISD::SUB, SDLoc(N), VT, DAG.getConstant(0, VT), SRA);
2129   }
2130
2131   // if integer divide is expensive and we satisfy the requirements, emit an
2132   // alternate sequence.
2133   if (N1C && !TLI.isIntDivCheap()) {
2134     SDValue Op = BuildSDIV(N);
2135     if (Op.getNode()) return Op;
2136   }
2137
2138   // undef / X -> 0
2139   if (N0.getOpcode() == ISD::UNDEF)
2140     return DAG.getConstant(0, VT);
2141   // X / undef -> undef
2142   if (N1.getOpcode() == ISD::UNDEF)
2143     return N1;
2144
2145   return SDValue();
2146 }
2147
2148 SDValue DAGCombiner::visitUDIV(SDNode *N) {
2149   SDValue N0 = N->getOperand(0);
2150   SDValue N1 = N->getOperand(1);
2151   ConstantSDNode *N0C = isConstOrConstSplat(N0);
2152   ConstantSDNode *N1C = isConstOrConstSplat(N1);
2153   EVT VT = N->getValueType(0);
2154
2155   // fold vector ops
2156   if (VT.isVector()) {
2157     SDValue FoldedVOp = SimplifyVBinOp(N);
2158     if (FoldedVOp.getNode()) return FoldedVOp;
2159   }
2160
2161   // fold (udiv c1, c2) -> c1/c2
2162   if (N0C && N1C && !N1C->isNullValue())
2163     return DAG.FoldConstantArithmetic(ISD::UDIV, VT, N0C, N1C);
2164   // fold (udiv x, (1 << c)) -> x >>u c
2165   if (N1C && N1C->getAPIntValue().isPowerOf2())
2166     return DAG.getNode(ISD::SRL, SDLoc(N), VT, N0,
2167                        DAG.getConstant(N1C->getAPIntValue().logBase2(),
2168                                        getShiftAmountTy(N0.getValueType())));
2169   // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2
2170   if (N1.getOpcode() == ISD::SHL) {
2171     if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) {
2172       if (SHC->getAPIntValue().isPowerOf2()) {
2173         EVT ADDVT = N1.getOperand(1).getValueType();
2174         SDValue Add = DAG.getNode(ISD::ADD, SDLoc(N), ADDVT,
2175                                   N1.getOperand(1),
2176                                   DAG.getConstant(SHC->getAPIntValue()
2177                                                                   .logBase2(),
2178                                                   ADDVT));
2179         AddToWorklist(Add.getNode());
2180         return DAG.getNode(ISD::SRL, SDLoc(N), VT, N0, Add);
2181       }
2182     }
2183   }
2184   // fold (udiv x, c) -> alternate
2185   if (N1C && !TLI.isIntDivCheap()) {
2186     SDValue Op = BuildUDIV(N);
2187     if (Op.getNode()) return Op;
2188   }
2189
2190   // undef / X -> 0
2191   if (N0.getOpcode() == ISD::UNDEF)
2192     return DAG.getConstant(0, VT);
2193   // X / undef -> undef
2194   if (N1.getOpcode() == ISD::UNDEF)
2195     return N1;
2196
2197   return SDValue();
2198 }
2199
2200 SDValue DAGCombiner::visitSREM(SDNode *N) {
2201   SDValue N0 = N->getOperand(0);
2202   SDValue N1 = N->getOperand(1);
2203   ConstantSDNode *N0C = isConstOrConstSplat(N0);
2204   ConstantSDNode *N1C = isConstOrConstSplat(N1);
2205   EVT VT = N->getValueType(0);
2206
2207   // fold (srem c1, c2) -> c1%c2
2208   if (N0C && N1C && !N1C->isNullValue())
2209     return DAG.FoldConstantArithmetic(ISD::SREM, VT, N0C, N1C);
2210   // If we know the sign bits of both operands are zero, strength reduce to a
2211   // urem instead.  Handles (X & 0x0FFFFFFF) %s 16 -> X&15
2212   if (!VT.isVector()) {
2213     if (DAG.SignBitIsZero(N1) && DAG.SignBitIsZero(N0))
2214       return DAG.getNode(ISD::UREM, SDLoc(N), VT, N0, N1);
2215   }
2216
2217   // If X/C can be simplified by the division-by-constant logic, lower
2218   // X%C to the equivalent of X-X/C*C.
2219   if (N1C && !N1C->isNullValue()) {
2220     SDValue Div = DAG.getNode(ISD::SDIV, SDLoc(N), VT, N0, N1);
2221     AddToWorklist(Div.getNode());
2222     SDValue OptimizedDiv = combine(Div.getNode());
2223     if (OptimizedDiv.getNode() && OptimizedDiv.getNode() != Div.getNode()) {
2224       SDValue Mul = DAG.getNode(ISD::MUL, SDLoc(N), VT,
2225                                 OptimizedDiv, N1);
2226       SDValue Sub = DAG.getNode(ISD::SUB, SDLoc(N), VT, N0, Mul);
2227       AddToWorklist(Mul.getNode());
2228       return Sub;
2229     }
2230   }
2231
2232   // undef % X -> 0
2233   if (N0.getOpcode() == ISD::UNDEF)
2234     return DAG.getConstant(0, VT);
2235   // X % undef -> undef
2236   if (N1.getOpcode() == ISD::UNDEF)
2237     return N1;
2238
2239   return SDValue();
2240 }
2241
2242 SDValue DAGCombiner::visitUREM(SDNode *N) {
2243   SDValue N0 = N->getOperand(0);
2244   SDValue N1 = N->getOperand(1);
2245   ConstantSDNode *N0C = isConstOrConstSplat(N0);
2246   ConstantSDNode *N1C = isConstOrConstSplat(N1);
2247   EVT VT = N->getValueType(0);
2248
2249   // fold (urem c1, c2) -> c1%c2
2250   if (N0C && N1C && !N1C->isNullValue())
2251     return DAG.FoldConstantArithmetic(ISD::UREM, VT, N0C, N1C);
2252   // fold (urem x, pow2) -> (and x, pow2-1)
2253   if (N1C && !N1C->isNullValue() && N1C->getAPIntValue().isPowerOf2())
2254     return DAG.getNode(ISD::AND, SDLoc(N), VT, N0,
2255                        DAG.getConstant(N1C->getAPIntValue()-1,VT));
2256   // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1))
2257   if (N1.getOpcode() == ISD::SHL) {
2258     if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) {
2259       if (SHC->getAPIntValue().isPowerOf2()) {
2260         SDValue Add =
2261           DAG.getNode(ISD::ADD, SDLoc(N), VT, N1,
2262                  DAG.getConstant(APInt::getAllOnesValue(VT.getSizeInBits()),
2263                                  VT));
2264         AddToWorklist(Add.getNode());
2265         return DAG.getNode(ISD::AND, SDLoc(N), VT, N0, Add);
2266       }
2267     }
2268   }
2269
2270   // If X/C can be simplified by the division-by-constant logic, lower
2271   // X%C to the equivalent of X-X/C*C.
2272   if (N1C && !N1C->isNullValue()) {
2273     SDValue Div = DAG.getNode(ISD::UDIV, SDLoc(N), VT, N0, N1);
2274     AddToWorklist(Div.getNode());
2275     SDValue OptimizedDiv = combine(Div.getNode());
2276     if (OptimizedDiv.getNode() && OptimizedDiv.getNode() != Div.getNode()) {
2277       SDValue Mul = DAG.getNode(ISD::MUL, SDLoc(N), VT,
2278                                 OptimizedDiv, N1);
2279       SDValue Sub = DAG.getNode(ISD::SUB, SDLoc(N), VT, N0, Mul);
2280       AddToWorklist(Mul.getNode());
2281       return Sub;
2282     }
2283   }
2284
2285   // undef % X -> 0
2286   if (N0.getOpcode() == ISD::UNDEF)
2287     return DAG.getConstant(0, VT);
2288   // X % undef -> undef
2289   if (N1.getOpcode() == ISD::UNDEF)
2290     return N1;
2291
2292   return SDValue();
2293 }
2294
2295 SDValue DAGCombiner::visitMULHS(SDNode *N) {
2296   SDValue N0 = N->getOperand(0);
2297   SDValue N1 = N->getOperand(1);
2298   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
2299   EVT VT = N->getValueType(0);
2300   SDLoc DL(N);
2301
2302   // fold (mulhs x, 0) -> 0
2303   if (N1C && N1C->isNullValue())
2304     return N1;
2305   // fold (mulhs x, 1) -> (sra x, size(x)-1)
2306   if (N1C && N1C->getAPIntValue() == 1)
2307     return DAG.getNode(ISD::SRA, SDLoc(N), N0.getValueType(), N0,
2308                        DAG.getConstant(N0.getValueType().getSizeInBits() - 1,
2309                                        getShiftAmountTy(N0.getValueType())));
2310   // fold (mulhs x, undef) -> 0
2311   if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
2312     return DAG.getConstant(0, VT);
2313
2314   // If the type twice as wide is legal, transform the mulhs to a wider multiply
2315   // plus a shift.
2316   if (VT.isSimple() && !VT.isVector()) {
2317     MVT Simple = VT.getSimpleVT();
2318     unsigned SimpleSize = Simple.getSizeInBits();
2319     EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
2320     if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
2321       N0 = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N0);
2322       N1 = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N1);
2323       N1 = DAG.getNode(ISD::MUL, DL, NewVT, N0, N1);
2324       N1 = DAG.getNode(ISD::SRL, DL, NewVT, N1,
2325             DAG.getConstant(SimpleSize, getShiftAmountTy(N1.getValueType())));
2326       return DAG.getNode(ISD::TRUNCATE, DL, VT, N1);
2327     }
2328   }
2329
2330   return SDValue();
2331 }
2332
2333 SDValue DAGCombiner::visitMULHU(SDNode *N) {
2334   SDValue N0 = N->getOperand(0);
2335   SDValue N1 = N->getOperand(1);
2336   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
2337   EVT VT = N->getValueType(0);
2338   SDLoc DL(N);
2339
2340   // fold (mulhu x, 0) -> 0
2341   if (N1C && N1C->isNullValue())
2342     return N1;
2343   // fold (mulhu x, 1) -> 0
2344   if (N1C && N1C->getAPIntValue() == 1)
2345     return DAG.getConstant(0, N0.getValueType());
2346   // fold (mulhu x, undef) -> 0
2347   if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
2348     return DAG.getConstant(0, VT);
2349
2350   // If the type twice as wide is legal, transform the mulhu to a wider multiply
2351   // plus a shift.
2352   if (VT.isSimple() && !VT.isVector()) {
2353     MVT Simple = VT.getSimpleVT();
2354     unsigned SimpleSize = Simple.getSizeInBits();
2355     EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
2356     if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
2357       N0 = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N0);
2358       N1 = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N1);
2359       N1 = DAG.getNode(ISD::MUL, DL, NewVT, N0, N1);
2360       N1 = DAG.getNode(ISD::SRL, DL, NewVT, N1,
2361             DAG.getConstant(SimpleSize, getShiftAmountTy(N1.getValueType())));
2362       return DAG.getNode(ISD::TRUNCATE, DL, VT, N1);
2363     }
2364   }
2365
2366   return SDValue();
2367 }
2368
2369 /// Perform optimizations common to nodes that compute two values. LoOp and HiOp
2370 /// give the opcodes for the two computations that are being performed. Return
2371 /// true if a simplification was made.
2372 SDValue DAGCombiner::SimplifyNodeWithTwoResults(SDNode *N, unsigned LoOp,
2373                                                 unsigned HiOp) {
2374   // If the high half is not needed, just compute the low half.
2375   bool HiExists = N->hasAnyUseOfValue(1);
2376   if (!HiExists &&
2377       (!LegalOperations ||
2378        TLI.isOperationLegalOrCustom(LoOp, N->getValueType(0)))) {
2379     SDValue Res = DAG.getNode(LoOp, SDLoc(N), N->getValueType(0), N->ops());
2380     return CombineTo(N, Res, Res);
2381   }
2382
2383   // If the low half is not needed, just compute the high half.
2384   bool LoExists = N->hasAnyUseOfValue(0);
2385   if (!LoExists &&
2386       (!LegalOperations ||
2387        TLI.isOperationLegal(HiOp, N->getValueType(1)))) {
2388     SDValue Res = DAG.getNode(HiOp, SDLoc(N), N->getValueType(1), N->ops());
2389     return CombineTo(N, Res, Res);
2390   }
2391
2392   // If both halves are used, return as it is.
2393   if (LoExists && HiExists)
2394     return SDValue();
2395
2396   // If the two computed results can be simplified separately, separate them.
2397   if (LoExists) {
2398     SDValue Lo = DAG.getNode(LoOp, SDLoc(N), N->getValueType(0), N->ops());
2399     AddToWorklist(Lo.getNode());
2400     SDValue LoOpt = combine(Lo.getNode());
2401     if (LoOpt.getNode() && LoOpt.getNode() != Lo.getNode() &&
2402         (!LegalOperations ||
2403          TLI.isOperationLegal(LoOpt.getOpcode(), LoOpt.getValueType())))
2404       return CombineTo(N, LoOpt, LoOpt);
2405   }
2406
2407   if (HiExists) {
2408     SDValue Hi = DAG.getNode(HiOp, SDLoc(N), N->getValueType(1), N->ops());
2409     AddToWorklist(Hi.getNode());
2410     SDValue HiOpt = combine(Hi.getNode());
2411     if (HiOpt.getNode() && HiOpt != Hi &&
2412         (!LegalOperations ||
2413          TLI.isOperationLegal(HiOpt.getOpcode(), HiOpt.getValueType())))
2414       return CombineTo(N, HiOpt, HiOpt);
2415   }
2416
2417   return SDValue();
2418 }
2419
2420 SDValue DAGCombiner::visitSMUL_LOHI(SDNode *N) {
2421   SDValue Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHS);
2422   if (Res.getNode()) return Res;
2423
2424   EVT VT = N->getValueType(0);
2425   SDLoc DL(N);
2426
2427   // If the type twice as wide is legal, transform the mulhu to a wider multiply
2428   // plus a shift.
2429   if (VT.isSimple() && !VT.isVector()) {
2430     MVT Simple = VT.getSimpleVT();
2431     unsigned SimpleSize = Simple.getSizeInBits();
2432     EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
2433     if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
2434       SDValue Lo = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N->getOperand(0));
2435       SDValue Hi = DAG.getNode(ISD::SIGN_EXTEND, DL, NewVT, N->getOperand(1));
2436       Lo = DAG.getNode(ISD::MUL, DL, NewVT, Lo, Hi);
2437       // Compute the high part as N1.
2438       Hi = DAG.getNode(ISD::SRL, DL, NewVT, Lo,
2439             DAG.getConstant(SimpleSize, getShiftAmountTy(Lo.getValueType())));
2440       Hi = DAG.getNode(ISD::TRUNCATE, DL, VT, Hi);
2441       // Compute the low part as N0.
2442       Lo = DAG.getNode(ISD::TRUNCATE, DL, VT, Lo);
2443       return CombineTo(N, Lo, Hi);
2444     }
2445   }
2446
2447   return SDValue();
2448 }
2449
2450 SDValue DAGCombiner::visitUMUL_LOHI(SDNode *N) {
2451   SDValue Res = SimplifyNodeWithTwoResults(N, ISD::MUL, ISD::MULHU);
2452   if (Res.getNode()) return Res;
2453
2454   EVT VT = N->getValueType(0);
2455   SDLoc DL(N);
2456
2457   // If the type twice as wide is legal, transform the mulhu to a wider multiply
2458   // plus a shift.
2459   if (VT.isSimple() && !VT.isVector()) {
2460     MVT Simple = VT.getSimpleVT();
2461     unsigned SimpleSize = Simple.getSizeInBits();
2462     EVT NewVT = EVT::getIntegerVT(*DAG.getContext(), SimpleSize*2);
2463     if (TLI.isOperationLegal(ISD::MUL, NewVT)) {
2464       SDValue Lo = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N->getOperand(0));
2465       SDValue Hi = DAG.getNode(ISD::ZERO_EXTEND, DL, NewVT, N->getOperand(1));
2466       Lo = DAG.getNode(ISD::MUL, DL, NewVT, Lo, Hi);
2467       // Compute the high part as N1.
2468       Hi = DAG.getNode(ISD::SRL, DL, NewVT, Lo,
2469             DAG.getConstant(SimpleSize, getShiftAmountTy(Lo.getValueType())));
2470       Hi = DAG.getNode(ISD::TRUNCATE, DL, VT, Hi);
2471       // Compute the low part as N0.
2472       Lo = DAG.getNode(ISD::TRUNCATE, DL, VT, Lo);
2473       return CombineTo(N, Lo, Hi);
2474     }
2475   }
2476
2477   return SDValue();
2478 }
2479
2480 SDValue DAGCombiner::visitSMULO(SDNode *N) {
2481   // (smulo x, 2) -> (saddo x, x)
2482   if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(N->getOperand(1)))
2483     if (C2->getAPIntValue() == 2)
2484       return DAG.getNode(ISD::SADDO, SDLoc(N), N->getVTList(),
2485                          N->getOperand(0), N->getOperand(0));
2486
2487   return SDValue();
2488 }
2489
2490 SDValue DAGCombiner::visitUMULO(SDNode *N) {
2491   // (umulo x, 2) -> (uaddo x, x)
2492   if (ConstantSDNode *C2 = dyn_cast<ConstantSDNode>(N->getOperand(1)))
2493     if (C2->getAPIntValue() == 2)
2494       return DAG.getNode(ISD::UADDO, SDLoc(N), N->getVTList(),
2495                          N->getOperand(0), N->getOperand(0));
2496
2497   return SDValue();
2498 }
2499
2500 SDValue DAGCombiner::visitSDIVREM(SDNode *N) {
2501   SDValue Res = SimplifyNodeWithTwoResults(N, ISD::SDIV, ISD::SREM);
2502   if (Res.getNode()) return Res;
2503
2504   return SDValue();
2505 }
2506
2507 SDValue DAGCombiner::visitUDIVREM(SDNode *N) {
2508   SDValue Res = SimplifyNodeWithTwoResults(N, ISD::UDIV, ISD::UREM);
2509   if (Res.getNode()) return Res;
2510
2511   return SDValue();
2512 }
2513
2514 /// If this is a binary operator with two operands of the same opcode, try to
2515 /// simplify it.
2516 SDValue DAGCombiner::SimplifyBinOpWithSameOpcodeHands(SDNode *N) {
2517   SDValue N0 = N->getOperand(0), N1 = N->getOperand(1);
2518   EVT VT = N0.getValueType();
2519   assert(N0.getOpcode() == N1.getOpcode() && "Bad input!");
2520
2521   // Bail early if none of these transforms apply.
2522   if (N0.getNode()->getNumOperands() == 0) return SDValue();
2523
2524   // For each of OP in AND/OR/XOR:
2525   // fold (OP (zext x), (zext y)) -> (zext (OP x, y))
2526   // fold (OP (sext x), (sext y)) -> (sext (OP x, y))
2527   // fold (OP (aext x), (aext y)) -> (aext (OP x, y))
2528   // fold (OP (bswap x), (bswap y)) -> (bswap (OP x, y))
2529   // fold (OP (trunc x), (trunc y)) -> (trunc (OP x, y)) (if trunc isn't free)
2530   //
2531   // do not sink logical op inside of a vector extend, since it may combine
2532   // into a vsetcc.
2533   EVT Op0VT = N0.getOperand(0).getValueType();
2534   if ((N0.getOpcode() == ISD::ZERO_EXTEND ||
2535        N0.getOpcode() == ISD::SIGN_EXTEND ||
2536        N0.getOpcode() == ISD::BSWAP ||
2537        // Avoid infinite looping with PromoteIntBinOp.
2538        (N0.getOpcode() == ISD::ANY_EXTEND &&
2539         (!LegalTypes || TLI.isTypeDesirableForOp(N->getOpcode(), Op0VT))) ||
2540        (N0.getOpcode() == ISD::TRUNCATE &&
2541         (!TLI.isZExtFree(VT, Op0VT) ||
2542          !TLI.isTruncateFree(Op0VT, VT)) &&
2543         TLI.isTypeLegal(Op0VT))) &&
2544       !VT.isVector() &&
2545       Op0VT == N1.getOperand(0).getValueType() &&
2546       (!LegalOperations || TLI.isOperationLegal(N->getOpcode(), Op0VT))) {
2547     SDValue ORNode = DAG.getNode(N->getOpcode(), SDLoc(N0),
2548                                  N0.getOperand(0).getValueType(),
2549                                  N0.getOperand(0), N1.getOperand(0));
2550     AddToWorklist(ORNode.getNode());
2551     return DAG.getNode(N0.getOpcode(), SDLoc(N), VT, ORNode);
2552   }
2553
2554   // For each of OP in SHL/SRL/SRA/AND...
2555   //   fold (and (OP x, z), (OP y, z)) -> (OP (and x, y), z)
2556   //   fold (or  (OP x, z), (OP y, z)) -> (OP (or  x, y), z)
2557   //   fold (xor (OP x, z), (OP y, z)) -> (OP (xor x, y), z)
2558   if ((N0.getOpcode() == ISD::SHL || N0.getOpcode() == ISD::SRL ||
2559        N0.getOpcode() == ISD::SRA || N0.getOpcode() == ISD::AND) &&
2560       N0.getOperand(1) == N1.getOperand(1)) {
2561     SDValue ORNode = DAG.getNode(N->getOpcode(), SDLoc(N0),
2562                                  N0.getOperand(0).getValueType(),
2563                                  N0.getOperand(0), N1.getOperand(0));
2564     AddToWorklist(ORNode.getNode());
2565     return DAG.getNode(N0.getOpcode(), SDLoc(N), VT,
2566                        ORNode, N0.getOperand(1));
2567   }
2568
2569   // Simplify xor/and/or (bitcast(A), bitcast(B)) -> bitcast(op (A,B))
2570   // Only perform this optimization after type legalization and before
2571   // LegalizeVectorOprs. LegalizeVectorOprs promotes vector operations by
2572   // adding bitcasts. For example (xor v4i32) is promoted to (v2i64), and
2573   // we don't want to undo this promotion.
2574   // We also handle SCALAR_TO_VECTOR because xor/or/and operations are cheaper
2575   // on scalars.
2576   if ((N0.getOpcode() == ISD::BITCAST ||
2577        N0.getOpcode() == ISD::SCALAR_TO_VECTOR) &&
2578       Level == AfterLegalizeTypes) {
2579     SDValue In0 = N0.getOperand(0);
2580     SDValue In1 = N1.getOperand(0);
2581     EVT In0Ty = In0.getValueType();
2582     EVT In1Ty = In1.getValueType();
2583     SDLoc DL(N);
2584     // If both incoming values are integers, and the original types are the
2585     // same.
2586     if (In0Ty.isInteger() && In1Ty.isInteger() && In0Ty == In1Ty) {
2587       SDValue Op = DAG.getNode(N->getOpcode(), DL, In0Ty, In0, In1);
2588       SDValue BC = DAG.getNode(N0.getOpcode(), DL, VT, Op);
2589       AddToWorklist(Op.getNode());
2590       return BC;
2591     }
2592   }
2593
2594   // Xor/and/or are indifferent to the swizzle operation (shuffle of one value).
2595   // Simplify xor/and/or (shuff(A), shuff(B)) -> shuff(op (A,B))
2596   // If both shuffles use the same mask, and both shuffle within a single
2597   // vector, then it is worthwhile to move the swizzle after the operation.
2598   // The type-legalizer generates this pattern when loading illegal
2599   // vector types from memory. In many cases this allows additional shuffle
2600   // optimizations.
2601   // There are other cases where moving the shuffle after the xor/and/or
2602   // is profitable even if shuffles don't perform a swizzle.
2603   // If both shuffles use the same mask, and both shuffles have the same first
2604   // or second operand, then it might still be profitable to move the shuffle
2605   // after the xor/and/or operation.
2606   if (N0.getOpcode() == ISD::VECTOR_SHUFFLE && Level < AfterLegalizeDAG) {
2607     ShuffleVectorSDNode *SVN0 = cast<ShuffleVectorSDNode>(N0);
2608     ShuffleVectorSDNode *SVN1 = cast<ShuffleVectorSDNode>(N1);
2609
2610     assert(N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType() &&
2611            "Inputs to shuffles are not the same type");
2612
2613     // Check that both shuffles use the same mask. The masks are known to be of
2614     // the same length because the result vector type is the same.
2615     // Check also that shuffles have only one use to avoid introducing extra
2616     // instructions.
2617     if (SVN0->hasOneUse() && SVN1->hasOneUse() &&
2618         SVN0->getMask().equals(SVN1->getMask())) {
2619       SDValue ShOp = N0->getOperand(1);
2620
2621       // Don't try to fold this node if it requires introducing a
2622       // build vector of all zeros that might be illegal at this stage.
2623       if (N->getOpcode() == ISD::XOR && ShOp.getOpcode() != ISD::UNDEF) {
2624         if (!LegalTypes)
2625           ShOp = DAG.getConstant(0, VT);
2626         else
2627           ShOp = SDValue();
2628       }
2629
2630       // (AND (shuf (A, C), shuf (B, C)) -> shuf (AND (A, B), C)
2631       // (OR  (shuf (A, C), shuf (B, C)) -> shuf (OR  (A, B), C)
2632       // (XOR (shuf (A, C), shuf (B, C)) -> shuf (XOR (A, B), V_0)
2633       if (N0.getOperand(1) == N1.getOperand(1) && ShOp.getNode()) {
2634         SDValue NewNode = DAG.getNode(N->getOpcode(), SDLoc(N), VT,
2635                                       N0->getOperand(0), N1->getOperand(0));
2636         AddToWorklist(NewNode.getNode());
2637         return DAG.getVectorShuffle(VT, SDLoc(N), NewNode, ShOp,
2638                                     &SVN0->getMask()[0]);
2639       }
2640
2641       // Don't try to fold this node if it requires introducing a
2642       // build vector of all zeros that might be illegal at this stage.
2643       ShOp = N0->getOperand(0);
2644       if (N->getOpcode() == ISD::XOR && ShOp.getOpcode() != ISD::UNDEF) {
2645         if (!LegalTypes)
2646           ShOp = DAG.getConstant(0, VT);
2647         else
2648           ShOp = SDValue();
2649       }
2650
2651       // (AND (shuf (C, A), shuf (C, B)) -> shuf (C, AND (A, B))
2652       // (OR  (shuf (C, A), shuf (C, B)) -> shuf (C, OR  (A, B))
2653       // (XOR (shuf (C, A), shuf (C, B)) -> shuf (V_0, XOR (A, B))
2654       if (N0->getOperand(0) == N1->getOperand(0) && ShOp.getNode()) {
2655         SDValue NewNode = DAG.getNode(N->getOpcode(), SDLoc(N), VT,
2656                                       N0->getOperand(1), N1->getOperand(1));
2657         AddToWorklist(NewNode.getNode());
2658         return DAG.getVectorShuffle(VT, SDLoc(N), ShOp, NewNode,
2659                                     &SVN0->getMask()[0]);
2660       }
2661     }
2662   }
2663
2664   return SDValue();
2665 }
2666
2667 SDValue DAGCombiner::visitAND(SDNode *N) {
2668   SDValue N0 = N->getOperand(0);
2669   SDValue N1 = N->getOperand(1);
2670   SDValue LL, LR, RL, RR, CC0, CC1;
2671   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
2672   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
2673   EVT VT = N1.getValueType();
2674   unsigned BitWidth = VT.getScalarType().getSizeInBits();
2675
2676   // fold vector ops
2677   if (VT.isVector()) {
2678     SDValue FoldedVOp = SimplifyVBinOp(N);
2679     if (FoldedVOp.getNode()) return FoldedVOp;
2680
2681     // fold (and x, 0) -> 0, vector edition
2682     if (ISD::isBuildVectorAllZeros(N0.getNode()))
2683       // do not return N0, because undef node may exist in N0
2684       return DAG.getConstant(
2685           APInt::getNullValue(
2686               N0.getValueType().getScalarType().getSizeInBits()),
2687           N0.getValueType());
2688     if (ISD::isBuildVectorAllZeros(N1.getNode()))
2689       // do not return N1, because undef node may exist in N1
2690       return DAG.getConstant(
2691           APInt::getNullValue(
2692               N1.getValueType().getScalarType().getSizeInBits()),
2693           N1.getValueType());
2694
2695     // fold (and x, -1) -> x, vector edition
2696     if (ISD::isBuildVectorAllOnes(N0.getNode()))
2697       return N1;
2698     if (ISD::isBuildVectorAllOnes(N1.getNode()))
2699       return N0;
2700   }
2701
2702   // fold (and x, undef) -> 0
2703   if (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)
2704     return DAG.getConstant(0, VT);
2705   // fold (and c1, c2) -> c1&c2
2706   if (N0C && N1C)
2707     return DAG.FoldConstantArithmetic(ISD::AND, VT, N0C, N1C);
2708   // canonicalize constant to RHS
2709   if (N0C && !N1C)
2710     return DAG.getNode(ISD::AND, SDLoc(N), VT, N1, N0);
2711   // fold (and x, -1) -> x
2712   if (N1C && N1C->isAllOnesValue())
2713     return N0;
2714   // if (and x, c) is known to be zero, return 0
2715   if (N1C && DAG.MaskedValueIsZero(SDValue(N, 0),
2716                                    APInt::getAllOnesValue(BitWidth)))
2717     return DAG.getConstant(0, VT);
2718   // reassociate and
2719   SDValue RAND = ReassociateOps(ISD::AND, SDLoc(N), N0, N1);
2720   if (RAND.getNode())
2721     return RAND;
2722   // fold (and (or x, C), D) -> D if (C & D) == D
2723   if (N1C && N0.getOpcode() == ISD::OR)
2724     if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
2725       if ((ORI->getAPIntValue() & N1C->getAPIntValue()) == N1C->getAPIntValue())
2726         return N1;
2727   // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits.
2728   if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) {
2729     SDValue N0Op0 = N0.getOperand(0);
2730     APInt Mask = ~N1C->getAPIntValue();
2731     Mask = Mask.trunc(N0Op0.getValueSizeInBits());
2732     if (DAG.MaskedValueIsZero(N0Op0, Mask)) {
2733       SDValue Zext = DAG.getNode(ISD::ZERO_EXTEND, SDLoc(N),
2734                                  N0.getValueType(), N0Op0);
2735
2736       // Replace uses of the AND with uses of the Zero extend node.
2737       CombineTo(N, Zext);
2738
2739       // We actually want to replace all uses of the any_extend with the
2740       // zero_extend, to avoid duplicating things.  This will later cause this
2741       // AND to be folded.
2742       CombineTo(N0.getNode(), Zext);
2743       return SDValue(N, 0);   // Return N so it doesn't get rechecked!
2744     }
2745   }
2746   // similarly fold (and (X (load ([non_ext|any_ext|zero_ext] V))), c) ->
2747   // (X (load ([non_ext|zero_ext] V))) if 'and' only clears top bits which must
2748   // already be zero by virtue of the width of the base type of the load.
2749   //
2750   // the 'X' node here can either be nothing or an extract_vector_elt to catch
2751   // more cases.
2752   if ((N0.getOpcode() == ISD::EXTRACT_VECTOR_ELT &&
2753        N0.getOperand(0).getOpcode() == ISD::LOAD) ||
2754       N0.getOpcode() == ISD::LOAD) {
2755     LoadSDNode *Load = cast<LoadSDNode>( (N0.getOpcode() == ISD::LOAD) ?
2756                                          N0 : N0.getOperand(0) );
2757
2758     // Get the constant (if applicable) the zero'th operand is being ANDed with.
2759     // This can be a pure constant or a vector splat, in which case we treat the
2760     // vector as a scalar and use the splat value.
2761     APInt Constant = APInt::getNullValue(1);
2762     if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2763       Constant = C->getAPIntValue();
2764     } else if (BuildVectorSDNode *Vector = dyn_cast<BuildVectorSDNode>(N1)) {
2765       APInt SplatValue, SplatUndef;
2766       unsigned SplatBitSize;
2767       bool HasAnyUndefs;
2768       bool IsSplat = Vector->isConstantSplat(SplatValue, SplatUndef,
2769                                              SplatBitSize, HasAnyUndefs);
2770       if (IsSplat) {
2771         // Undef bits can contribute to a possible optimisation if set, so
2772         // set them.
2773         SplatValue |= SplatUndef;
2774
2775         // The splat value may be something like "0x00FFFFFF", which means 0 for
2776         // the first vector value and FF for the rest, repeating. We need a mask
2777         // that will apply equally to all members of the vector, so AND all the
2778         // lanes of the constant together.
2779         EVT VT = Vector->getValueType(0);
2780         unsigned BitWidth = VT.getVectorElementType().getSizeInBits();
2781
2782         // If the splat value has been compressed to a bitlength lower
2783         // than the size of the vector lane, we need to re-expand it to
2784         // the lane size.
2785         if (BitWidth > SplatBitSize)
2786           for (SplatValue = SplatValue.zextOrTrunc(BitWidth);
2787                SplatBitSize < BitWidth;
2788                SplatBitSize = SplatBitSize * 2)
2789             SplatValue |= SplatValue.shl(SplatBitSize);
2790
2791         Constant = APInt::getAllOnesValue(BitWidth);
2792         for (unsigned i = 0, n = SplatBitSize/BitWidth; i < n; ++i)
2793           Constant &= SplatValue.lshr(i*BitWidth).zextOrTrunc(BitWidth);
2794       }
2795     }
2796
2797     // If we want to change an EXTLOAD to a ZEXTLOAD, ensure a ZEXTLOAD is
2798     // actually legal and isn't going to get expanded, else this is a false
2799     // optimisation.
2800     bool CanZextLoadProfitably = TLI.isLoadExtLegal(ISD::ZEXTLOAD,
2801                                                     Load->getValueType(0),
2802                                                     Load->getMemoryVT());
2803
2804     // Resize the constant to the same size as the original memory access before
2805     // extension. If it is still the AllOnesValue then this AND is completely
2806     // unneeded.
2807     Constant =
2808       Constant.zextOrTrunc(Load->getMemoryVT().getScalarType().getSizeInBits());
2809
2810     bool B;
2811     switch (Load->getExtensionType()) {
2812     default: B = false; break;
2813     case ISD::EXTLOAD: B = CanZextLoadProfitably; break;
2814     case ISD::ZEXTLOAD:
2815     case ISD::NON_EXTLOAD: B = true; break;
2816     }
2817
2818     if (B && Constant.isAllOnesValue()) {
2819       // If the load type was an EXTLOAD, convert to ZEXTLOAD in order to
2820       // preserve semantics once we get rid of the AND.
2821       SDValue NewLoad(Load, 0);
2822       if (Load->getExtensionType() == ISD::EXTLOAD) {
2823         NewLoad = DAG.getLoad(Load->getAddressingMode(), ISD::ZEXTLOAD,
2824                               Load->getValueType(0), SDLoc(Load),
2825                               Load->getChain(), Load->getBasePtr(),
2826                               Load->getOffset(), Load->getMemoryVT(),
2827                               Load->getMemOperand());
2828         // Replace uses of the EXTLOAD with the new ZEXTLOAD.
2829         if (Load->getNumValues() == 3) {
2830           // PRE/POST_INC loads have 3 values.
2831           SDValue To[] = { NewLoad.getValue(0), NewLoad.getValue(1),
2832                            NewLoad.getValue(2) };
2833           CombineTo(Load, To, 3, true);
2834         } else {
2835           CombineTo(Load, NewLoad.getValue(0), NewLoad.getValue(1));
2836         }
2837       }
2838
2839       // Fold the AND away, taking care not to fold to the old load node if we
2840       // replaced it.
2841       CombineTo(N, (N0.getNode() == Load) ? NewLoad : N0);
2842
2843       return SDValue(N, 0); // Return N so it doesn't get rechecked!
2844     }
2845   }
2846   // fold (and (setcc x), (setcc y)) -> (setcc (and x, y))
2847   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
2848     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
2849     ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
2850
2851     if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
2852         LL.getValueType().isInteger()) {
2853       // fold (and (seteq X, 0), (seteq Y, 0)) -> (seteq (or X, Y), 0)
2854       if (cast<ConstantSDNode>(LR)->isNullValue() && Op1 == ISD::SETEQ) {
2855         SDValue ORNode = DAG.getNode(ISD::OR, SDLoc(N0),
2856                                      LR.getValueType(), LL, RL);
2857         AddToWorklist(ORNode.getNode());
2858         return DAG.getSetCC(SDLoc(N), VT, ORNode, LR, Op1);
2859       }
2860       // fold (and (seteq X, -1), (seteq Y, -1)) -> (seteq (and X, Y), -1)
2861       if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) {
2862         SDValue ANDNode = DAG.getNode(ISD::AND, SDLoc(N0),
2863                                       LR.getValueType(), LL, RL);
2864         AddToWorklist(ANDNode.getNode());
2865         return DAG.getSetCC(SDLoc(N), VT, ANDNode, LR, Op1);
2866       }
2867       // fold (and (setgt X,  -1), (setgt Y,  -1)) -> (setgt (or X, Y), -1)
2868       if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) {
2869         SDValue ORNode = DAG.getNode(ISD::OR, SDLoc(N0),
2870                                      LR.getValueType(), LL, RL);
2871         AddToWorklist(ORNode.getNode());
2872         return DAG.getSetCC(SDLoc(N), VT, ORNode, LR, Op1);
2873       }
2874     }
2875     // Simplify (and (setne X, 0), (setne X, -1)) -> (setuge (add X, 1), 2)
2876     if (LL == RL && isa<ConstantSDNode>(LR) && isa<ConstantSDNode>(RR) &&
2877         Op0 == Op1 && LL.getValueType().isInteger() &&
2878       Op0 == ISD::SETNE && ((cast<ConstantSDNode>(LR)->isNullValue() &&
2879                                  cast<ConstantSDNode>(RR)->isAllOnesValue()) ||
2880                                 (cast<ConstantSDNode>(LR)->isAllOnesValue() &&
2881                                  cast<ConstantSDNode>(RR)->isNullValue()))) {
2882       SDValue ADDNode = DAG.getNode(ISD::ADD, SDLoc(N0), LL.getValueType(),
2883                                     LL, DAG.getConstant(1, LL.getValueType()));
2884       AddToWorklist(ADDNode.getNode());
2885       return DAG.getSetCC(SDLoc(N), VT, ADDNode,
2886                           DAG.getConstant(2, LL.getValueType()), ISD::SETUGE);
2887     }
2888     // canonicalize equivalent to ll == rl
2889     if (LL == RR && LR == RL) {
2890       Op1 = ISD::getSetCCSwappedOperands(Op1);
2891       std::swap(RL, RR);
2892     }
2893     if (LL == RL && LR == RR) {
2894       bool isInteger = LL.getValueType().isInteger();
2895       ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger);
2896       if (Result != ISD::SETCC_INVALID &&
2897           (!LegalOperations ||
2898            (TLI.isCondCodeLegal(Result, LL.getSimpleValueType()) &&
2899             TLI.isOperationLegal(ISD::SETCC,
2900                             getSetCCResultType(N0.getSimpleValueType())))))
2901         return DAG.getSetCC(SDLoc(N), N0.getValueType(),
2902                             LL, LR, Result);
2903     }
2904   }
2905
2906   // Simplify: (and (op x...), (op y...))  -> (op (and x, y))
2907   if (N0.getOpcode() == N1.getOpcode()) {
2908     SDValue Tmp = SimplifyBinOpWithSameOpcodeHands(N);
2909     if (Tmp.getNode()) return Tmp;
2910   }
2911
2912   // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1)
2913   // fold (and (sra)) -> (and (srl)) when possible.
2914   if (!VT.isVector() &&
2915       SimplifyDemandedBits(SDValue(N, 0)))
2916     return SDValue(N, 0);
2917
2918   // fold (zext_inreg (extload x)) -> (zextload x)
2919   if (ISD::isEXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode())) {
2920     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2921     EVT MemVT = LN0->getMemoryVT();
2922     // If we zero all the possible extended bits, then we can turn this into
2923     // a zextload if we are running before legalize or the operation is legal.
2924     unsigned BitWidth = N1.getValueType().getScalarType().getSizeInBits();
2925     if (DAG.MaskedValueIsZero(N1, APInt::getHighBitsSet(BitWidth,
2926                            BitWidth - MemVT.getScalarType().getSizeInBits())) &&
2927         ((!LegalOperations && !LN0->isVolatile()) ||
2928          TLI.isLoadExtLegal(ISD::ZEXTLOAD, VT, MemVT))) {
2929       SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, SDLoc(N0), VT,
2930                                        LN0->getChain(), LN0->getBasePtr(),
2931                                        MemVT, LN0->getMemOperand());
2932       AddToWorklist(N);
2933       CombineTo(N0.getNode(), ExtLoad, ExtLoad.getValue(1));
2934       return SDValue(N, 0);   // Return N so it doesn't get rechecked!
2935     }
2936   }
2937   // fold (zext_inreg (sextload x)) -> (zextload x) iff load has one use
2938   if (ISD::isSEXTLoad(N0.getNode()) && ISD::isUNINDEXEDLoad(N0.getNode()) &&
2939       N0.hasOneUse()) {
2940     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2941     EVT MemVT = LN0->getMemoryVT();
2942     // If we zero all the possible extended bits, then we can turn this into
2943     // a zextload if we are running before legalize or the operation is legal.
2944     unsigned BitWidth = N1.getValueType().getScalarType().getSizeInBits();
2945     if (DAG.MaskedValueIsZero(N1, APInt::getHighBitsSet(BitWidth,
2946                            BitWidth - MemVT.getScalarType().getSizeInBits())) &&
2947         ((!LegalOperations && !LN0->isVolatile()) ||
2948          TLI.isLoadExtLegal(ISD::ZEXTLOAD, VT, MemVT))) {
2949       SDValue ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, SDLoc(N0), VT,
2950                                        LN0->getChain(), LN0->getBasePtr(),
2951                                        MemVT, LN0->getMemOperand());
2952       AddToWorklist(N);
2953       CombineTo(N0.getNode(), ExtLoad, ExtLoad.getValue(1));
2954       return SDValue(N, 0);   // Return N so it doesn't get rechecked!
2955     }
2956   }
2957
2958   // fold (and (load x), 255) -> (zextload x, i8)
2959   // fold (and (extload x, i16), 255) -> (zextload x, i8)
2960   // fold (and (any_ext (extload x, i16)), 255) -> (zextload x, i8)
2961   if (N1C && (N0.getOpcode() == ISD::LOAD ||
2962               (N0.getOpcode() == ISD::ANY_EXTEND &&
2963                N0.getOperand(0).getOpcode() == ISD::LOAD))) {
2964     bool HasAnyExt = N0.getOpcode() == ISD::ANY_EXTEND;
2965     LoadSDNode *LN0 = HasAnyExt
2966       ? cast<LoadSDNode>(N0.getOperand(0))
2967       : cast<LoadSDNode>(N0);
2968     if (LN0->getExtensionType() != ISD::SEXTLOAD &&
2969         LN0->isUnindexed() && N0.hasOneUse() && SDValue(LN0, 0).hasOneUse()) {
2970       uint32_t ActiveBits = N1C->getAPIntValue().getActiveBits();
2971       if (ActiveBits > 0 && APIntOps::isMask(ActiveBits, N1C->getAPIntValue())){
2972         EVT ExtVT = EVT::getIntegerVT(*DAG.getContext(), ActiveBits);
2973         EVT LoadedVT = LN0->getMemoryVT();
2974         EVT LoadResultTy = HasAnyExt ? LN0->getValueType(0) : VT;
2975
2976         if (ExtVT == LoadedVT &&
2977             (!LegalOperations || TLI.isLoadExtLegal(ISD::ZEXTLOAD, LoadResultTy,
2978                                                     ExtVT))) {
2979
2980           SDValue NewLoad =
2981             DAG.getExtLoad(ISD::ZEXTLOAD, SDLoc(LN0), LoadResultTy,
2982                            LN0->getChain(), LN0->getBasePtr(), ExtVT,
2983                            LN0->getMemOperand());
2984           AddToWorklist(N);
2985           CombineTo(LN0, NewLoad, NewLoad.getValue(1));
2986           return SDValue(N, 0);   // Return N so it doesn't get rechecked!
2987         }
2988
2989         // Do not change the width of a volatile load.
2990         // Do not generate loads of non-round integer types since these can
2991         // be expensive (and would be wrong if the type is not byte sized).
2992         if (!LN0->isVolatile() && LoadedVT.bitsGT(ExtVT) && ExtVT.isRound() &&
2993             (!LegalOperations || TLI.isLoadExtLegal(ISD::ZEXTLOAD, LoadResultTy,
2994                                                     ExtVT))) {
2995           EVT PtrType = LN0->getOperand(1).getValueType();
2996
2997           unsigned Alignment = LN0->getAlignment();
2998           SDValue NewPtr = LN0->getBasePtr();
2999
3000           // For big endian targets, we need to add an offset to the pointer
3001           // to load the correct bytes.  For little endian systems, we merely
3002           // need to read fewer bytes from the same pointer.
3003           if (TLI.isBigEndian()) {
3004             unsigned LVTStoreBytes = LoadedVT.getStoreSize();
3005             unsigned EVTStoreBytes = ExtVT.getStoreSize();
3006             unsigned PtrOff = LVTStoreBytes - EVTStoreBytes;
3007             NewPtr = DAG.getNode(ISD::ADD, SDLoc(LN0), PtrType,
3008                                  NewPtr, DAG.getConstant(PtrOff, PtrType));
3009             Alignment = MinAlign(Alignment, PtrOff);
3010           }
3011
3012           AddToWorklist(NewPtr.getNode());
3013
3014           SDValue Load =
3015             DAG.getExtLoad(ISD::ZEXTLOAD, SDLoc(LN0), LoadResultTy,
3016                            LN0->getChain(), NewPtr,
3017                            LN0->getPointerInfo(),
3018                            ExtVT, LN0->isVolatile(), LN0->isNonTemporal(),
3019                            LN0->isInvariant(), Alignment, LN0->getAAInfo());
3020           AddToWorklist(N);
3021           CombineTo(LN0, Load, Load.getValue(1));
3022           return SDValue(N, 0);   // Return N so it doesn't get rechecked!
3023         }
3024       }
3025     }
3026   }
3027
3028   if (N0.getOpcode() == ISD::ADD && N1.getOpcode() == ISD::SRL &&
3029       VT.getSizeInBits() <= 64) {
3030     if (ConstantSDNode *ADDI = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
3031       APInt ADDC = ADDI->getAPIntValue();
3032       if (!TLI.isLegalAddImmediate(ADDC.getSExtValue())) {
3033         // Look for (and (add x, c1), (lshr y, c2)). If C1 wasn't a legal
3034         // immediate for an add, but it is legal if its top c2 bits are set,
3035         // transform the ADD so the immediate doesn't need to be materialized
3036         // in a register.
3037         if (ConstantSDNode *SRLI = dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
3038           APInt Mask = APInt::getHighBitsSet(VT.getSizeInBits(),
3039                                              SRLI->getZExtValue());
3040           if (DAG.MaskedValueIsZero(N0.getOperand(1), Mask)) {
3041             ADDC |= Mask;
3042             if (TLI.isLegalAddImmediate(ADDC.getSExtValue())) {
3043               SDValue NewAdd =
3044                 DAG.getNode(ISD::ADD, SDLoc(N0), VT,
3045                             N0.getOperand(0), DAG.getConstant(ADDC, VT));
3046               CombineTo(N0.getNode(), NewAdd);
3047               return SDValue(N, 0); // Return N so it doesn't get rechecked!
3048             }
3049           }
3050         }
3051       }
3052     }
3053   }
3054
3055   // fold (and (or (srl N, 8), (shl N, 8)), 0xffff) -> (srl (bswap N), const)
3056   if (N1C && N1C->getAPIntValue() == 0xffff && N0.getOpcode() == ISD::OR) {
3057     SDValue BSwap = MatchBSwapHWordLow(N0.getNode(), N0.getOperand(0),
3058                                        N0.getOperand(1), false);
3059     if (BSwap.getNode())
3060       return BSwap;
3061   }
3062
3063   return SDValue();
3064 }
3065
3066 /// Match (a >> 8) | (a << 8) as (bswap a) >> 16.
3067 SDValue DAGCombiner::MatchBSwapHWordLow(SDNode *N, SDValue N0, SDValue N1,
3068                                         bool DemandHighBits) {
3069   if (!LegalOperations)
3070     return SDValue();
3071
3072   EVT VT = N->getValueType(0);
3073   if (VT != MVT::i64 && VT != MVT::i32 && VT != MVT::i16)
3074     return SDValue();
3075   if (!TLI.isOperationLegal(ISD::BSWAP, VT))
3076     return SDValue();
3077
3078   // Recognize (and (shl a, 8), 0xff), (and (srl a, 8), 0xff00)
3079   bool LookPassAnd0 = false;
3080   bool LookPassAnd1 = false;
3081   if (N0.getOpcode() == ISD::AND && N0.getOperand(0).getOpcode() == ISD::SRL)
3082       std::swap(N0, N1);
3083   if (N1.getOpcode() == ISD::AND && N1.getOperand(0).getOpcode() == ISD::SHL)
3084       std::swap(N0, N1);
3085   if (N0.getOpcode() == ISD::AND) {
3086     if (!N0.getNode()->hasOneUse())
3087       return SDValue();
3088     ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
3089     if (!N01C || N01C->getZExtValue() != 0xFF00)
3090       return SDValue();
3091     N0 = N0.getOperand(0);
3092     LookPassAnd0 = true;
3093   }
3094
3095   if (N1.getOpcode() == ISD::AND) {
3096     if (!N1.getNode()->hasOneUse())
3097       return SDValue();
3098     ConstantSDNode *N11C = dyn_cast<ConstantSDNode>(N1.getOperand(1));
3099     if (!N11C || N11C->getZExtValue() != 0xFF)
3100       return SDValue();
3101     N1 = N1.getOperand(0);
3102     LookPassAnd1 = true;
3103   }
3104
3105   if (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SHL)
3106     std::swap(N0, N1);
3107   if (N0.getOpcode() != ISD::SHL || N1.getOpcode() != ISD::SRL)
3108     return SDValue();
3109   if (!N0.getNode()->hasOneUse() ||
3110       !N1.getNode()->hasOneUse())
3111     return SDValue();
3112
3113   ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
3114   ConstantSDNode *N11C = dyn_cast<ConstantSDNode>(N1.getOperand(1));
3115   if (!N01C || !N11C)
3116     return SDValue();
3117   if (N01C->getZExtValue() != 8 || N11C->getZExtValue() != 8)
3118     return SDValue();
3119
3120   // Look for (shl (and a, 0xff), 8), (srl (and a, 0xff00), 8)
3121   SDValue N00 = N0->getOperand(0);
3122   if (!LookPassAnd0 && N00.getOpcode() == ISD::AND) {
3123     if (!N00.getNode()->hasOneUse())
3124       return SDValue();
3125     ConstantSDNode *N001C = dyn_cast<ConstantSDNode>(N00.getOperand(1));
3126     if (!N001C || N001C->getZExtValue() != 0xFF)
3127       return SDValue();
3128     N00 = N00.getOperand(0);
3129     LookPassAnd0 = true;
3130   }
3131
3132   SDValue N10 = N1->getOperand(0);
3133   if (!LookPassAnd1 && N10.getOpcode() == ISD::AND) {
3134     if (!N10.getNode()->hasOneUse())
3135       return SDValue();
3136     ConstantSDNode *N101C = dyn_cast<ConstantSDNode>(N10.getOperand(1));
3137     if (!N101C || N101C->getZExtValue() != 0xFF00)
3138       return SDValue();
3139     N10 = N10.getOperand(0);
3140     LookPassAnd1 = true;
3141   }
3142
3143   if (N00 != N10)
3144     return SDValue();
3145
3146   // Make sure everything beyond the low halfword gets set to zero since the SRL
3147   // 16 will clear the top bits.
3148   unsigned OpSizeInBits = VT.getSizeInBits();
3149   if (DemandHighBits && OpSizeInBits > 16) {
3150     // If the left-shift isn't masked out then the only way this is a bswap is
3151     // if all bits beyond the low 8 are 0. In that case the entire pattern
3152     // reduces to a left shift anyway: leave it for other parts of the combiner.
3153     if (!LookPassAnd0)
3154       return SDValue();
3155
3156     // However, if the right shift isn't masked out then it might be because
3157     // it's not needed. See if we can spot that too.
3158     if (!LookPassAnd1 &&
3159         !DAG.MaskedValueIsZero(
3160             N10, APInt::getHighBitsSet(OpSizeInBits, OpSizeInBits - 16)))
3161       return SDValue();
3162   }
3163
3164   SDValue Res = DAG.getNode(ISD::BSWAP, SDLoc(N), VT, N00);
3165   if (OpSizeInBits > 16)
3166     Res = DAG.getNode(ISD::SRL, SDLoc(N), VT, Res,
3167                       DAG.getConstant(OpSizeInBits-16, getShiftAmountTy(VT)));
3168   return Res;
3169 }
3170
3171 /// Return true if the specified node is an element that makes up a 32-bit
3172 /// packed halfword byteswap.
3173 /// ((x & 0x000000ff) << 8) |
3174 /// ((x & 0x0000ff00) >> 8) |
3175 /// ((x & 0x00ff0000) << 8) |
3176 /// ((x & 0xff000000) >> 8)
3177 static bool isBSwapHWordElement(SDValue N, MutableArrayRef<SDNode *> Parts) {
3178   if (!N.getNode()->hasOneUse())
3179     return false;
3180
3181   unsigned Opc = N.getOpcode();
3182   if (Opc != ISD::AND && Opc != ISD::SHL && Opc != ISD::SRL)
3183     return false;
3184
3185   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N.getOperand(1));
3186   if (!N1C)
3187     return false;
3188
3189   unsigned Num;
3190   switch (N1C->getZExtValue()) {
3191   default:
3192     return false;
3193   case 0xFF:       Num = 0; break;
3194   case 0xFF00:     Num = 1; break;
3195   case 0xFF0000:   Num = 2; break;
3196   case 0xFF000000: Num = 3; break;
3197   }
3198
3199   // Look for (x & 0xff) << 8 as well as ((x << 8) & 0xff00).
3200   SDValue N0 = N.getOperand(0);
3201   if (Opc == ISD::AND) {
3202     if (Num == 0 || Num == 2) {
3203       // (x >> 8) & 0xff
3204       // (x >> 8) & 0xff0000
3205       if (N0.getOpcode() != ISD::SRL)
3206         return false;
3207       ConstantSDNode *C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
3208       if (!C || C->getZExtValue() != 8)
3209         return false;
3210     } else {
3211       // (x << 8) & 0xff00
3212       // (x << 8) & 0xff000000
3213       if (N0.getOpcode() != ISD::SHL)
3214         return false;
3215       ConstantSDNode *C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
3216       if (!C || C->getZExtValue() != 8)
3217         return false;
3218     }
3219   } else if (Opc == ISD::SHL) {
3220     // (x & 0xff) << 8
3221     // (x & 0xff0000) << 8
3222     if (Num != 0 && Num != 2)
3223       return false;
3224     ConstantSDNode *C = dyn_cast<ConstantSDNode>(N.getOperand(1));
3225     if (!C || C->getZExtValue() != 8)
3226       return false;
3227   } else { // Opc == ISD::SRL
3228     // (x & 0xff00) >> 8
3229     // (x & 0xff000000) >> 8
3230     if (Num != 1 && Num != 3)
3231       return false;
3232     ConstantSDNode *C = dyn_cast<ConstantSDNode>(N.getOperand(1));
3233     if (!C || C->getZExtValue() != 8)
3234       return false;
3235   }
3236
3237   if (Parts[Num])
3238     return false;
3239
3240   Parts[Num] = N0.getOperand(0).getNode();
3241   return true;
3242 }
3243
3244 /// Match a 32-bit packed halfword bswap. That is
3245 /// ((x & 0x000000ff) << 8) |
3246 /// ((x & 0x0000ff00) >> 8) |
3247 /// ((x & 0x00ff0000) << 8) |
3248 /// ((x & 0xff000000) >> 8)
3249 /// => (rotl (bswap x), 16)
3250 SDValue DAGCombiner::MatchBSwapHWord(SDNode *N, SDValue N0, SDValue N1) {
3251   if (!LegalOperations)
3252     return SDValue();
3253
3254   EVT VT = N->getValueType(0);
3255   if (VT != MVT::i32)
3256     return SDValue();
3257   if (!TLI.isOperationLegal(ISD::BSWAP, VT))
3258     return SDValue();
3259
3260   // Look for either
3261   // (or (or (and), (and)), (or (and), (and)))
3262   // (or (or (or (and), (and)), (and)), (and))
3263   if (N0.getOpcode() != ISD::OR)
3264     return SDValue();
3265   SDValue N00 = N0.getOperand(0);
3266   SDValue N01 = N0.getOperand(1);
3267   SDNode *Parts[4] = {};
3268
3269   if (N1.getOpcode() == ISD::OR &&
3270       N00.getNumOperands() == 2 && N01.getNumOperands() == 2) {
3271     // (or (or (and), (and)), (or (and), (and)))
3272     SDValue N000 = N00.getOperand(0);
3273     if (!isBSwapHWordElement(N000, Parts))
3274       return SDValue();
3275
3276     SDValue N001 = N00.getOperand(1);
3277     if (!isBSwapHWordElement(N001, Parts))
3278       return SDValue();
3279     SDValue N010 = N01.getOperand(0);
3280     if (!isBSwapHWordElement(N010, Parts))
3281       return SDValue();
3282     SDValue N011 = N01.getOperand(1);
3283     if (!isBSwapHWordElement(N011, Parts))
3284       return SDValue();
3285   } else {
3286     // (or (or (or (and), (and)), (and)), (and))
3287     if (!isBSwapHWordElement(N1, Parts))
3288       return SDValue();
3289     if (!isBSwapHWordElement(N01, Parts))
3290       return SDValue();
3291     if (N00.getOpcode() != ISD::OR)
3292       return SDValue();
3293     SDValue N000 = N00.getOperand(0);
3294     if (!isBSwapHWordElement(N000, Parts))
3295       return SDValue();
3296     SDValue N001 = N00.getOperand(1);
3297     if (!isBSwapHWordElement(N001, Parts))
3298       return SDValue();
3299   }
3300
3301   // Make sure the parts are all coming from the same node.
3302   if (Parts[0] != Parts[1] || Parts[0] != Parts[2] || Parts[0] != Parts[3])
3303     return SDValue();
3304
3305   SDValue BSwap = DAG.getNode(ISD::BSWAP, SDLoc(N), VT,
3306                               SDValue(Parts[0],0));
3307
3308   // Result of the bswap should be rotated by 16. If it's not legal, then
3309   // do  (x << 16) | (x >> 16).
3310   SDValue ShAmt = DAG.getConstant(16, getShiftAmountTy(VT));
3311   if (TLI.isOperationLegalOrCustom(ISD::ROTL, VT))
3312     return DAG.getNode(ISD::ROTL, SDLoc(N), VT, BSwap, ShAmt);
3313   if (TLI.isOperationLegalOrCustom(ISD::ROTR, VT))
3314     return DAG.getNode(ISD::ROTR, SDLoc(N), VT, BSwap, ShAmt);
3315   return DAG.getNode(ISD::OR, SDLoc(N), VT,
3316                      DAG.getNode(ISD::SHL, SDLoc(N), VT, BSwap, ShAmt),
3317                      DAG.getNode(ISD::SRL, SDLoc(N), VT, BSwap, ShAmt));
3318 }
3319
3320 SDValue DAGCombiner::visitOR(SDNode *N) {
3321   SDValue N0 = N->getOperand(0);
3322   SDValue N1 = N->getOperand(1);
3323   SDValue LL, LR, RL, RR, CC0, CC1;
3324   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
3325   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
3326   EVT VT = N1.getValueType();
3327
3328   // fold vector ops
3329   if (VT.isVector()) {
3330     SDValue FoldedVOp = SimplifyVBinOp(N);
3331     if (FoldedVOp.getNode()) return FoldedVOp;
3332
3333     // fold (or x, 0) -> x, vector edition
3334     if (ISD::isBuildVectorAllZeros(N0.getNode()))
3335       return N1;
3336     if (ISD::isBuildVectorAllZeros(N1.getNode()))
3337       return N0;
3338
3339     // fold (or x, -1) -> -1, vector edition
3340     if (ISD::isBuildVectorAllOnes(N0.getNode()))
3341       // do not return N0, because undef node may exist in N0
3342       return DAG.getConstant(
3343           APInt::getAllOnesValue(
3344               N0.getValueType().getScalarType().getSizeInBits()),
3345           N0.getValueType());
3346     if (ISD::isBuildVectorAllOnes(N1.getNode()))
3347       // do not return N1, because undef node may exist in N1
3348       return DAG.getConstant(
3349           APInt::getAllOnesValue(
3350               N1.getValueType().getScalarType().getSizeInBits()),
3351           N1.getValueType());
3352
3353     // fold (or (shuf A, V_0, MA), (shuf B, V_0, MB)) -> (shuf A, B, Mask1)
3354     // fold (or (shuf A, V_0, MA), (shuf B, V_0, MB)) -> (shuf B, A, Mask2)
3355     // Do this only if the resulting shuffle is legal.
3356     if (isa<ShuffleVectorSDNode>(N0) &&
3357         isa<ShuffleVectorSDNode>(N1) &&
3358         // Avoid folding a node with illegal type.
3359         TLI.isTypeLegal(VT) &&
3360         N0->getOperand(1) == N1->getOperand(1) &&
3361         ISD::isBuildVectorAllZeros(N0.getOperand(1).getNode())) {
3362       bool CanFold = true;
3363       unsigned NumElts = VT.getVectorNumElements();
3364       const ShuffleVectorSDNode *SV0 = cast<ShuffleVectorSDNode>(N0);
3365       const ShuffleVectorSDNode *SV1 = cast<ShuffleVectorSDNode>(N1);
3366       // We construct two shuffle masks:
3367       // - Mask1 is a shuffle mask for a shuffle with N0 as the first operand
3368       // and N1 as the second operand.
3369       // - Mask2 is a shuffle mask for a shuffle with N1 as the first operand
3370       // and N0 as the second operand.
3371       // We do this because OR is commutable and therefore there might be
3372       // two ways to fold this node into a shuffle.
3373       SmallVector<int,4> Mask1;
3374       SmallVector<int,4> Mask2;
3375
3376       for (unsigned i = 0; i != NumElts && CanFold; ++i) {
3377         int M0 = SV0->getMaskElt(i);
3378         int M1 = SV1->getMaskElt(i);
3379
3380         // Both shuffle indexes are undef. Propagate Undef.
3381         if (M0 < 0 && M1 < 0) {
3382           Mask1.push_back(M0);
3383           Mask2.push_back(M0);
3384           continue;
3385         }
3386
3387         if (M0 < 0 || M1 < 0 ||
3388             (M0 < (int)NumElts && M1 < (int)NumElts) ||
3389             (M0 >= (int)NumElts && M1 >= (int)NumElts)) {
3390           CanFold = false;
3391           break;
3392         }
3393
3394         Mask1.push_back(M0 < (int)NumElts ? M0 : M1 + NumElts);
3395         Mask2.push_back(M1 < (int)NumElts ? M1 : M0 + NumElts);
3396       }
3397
3398       if (CanFold) {
3399         // Fold this sequence only if the resulting shuffle is 'legal'.
3400         if (TLI.isShuffleMaskLegal(Mask1, VT))
3401           return DAG.getVectorShuffle(VT, SDLoc(N), N0->getOperand(0),
3402                                       N1->getOperand(0), &Mask1[0]);
3403         if (TLI.isShuffleMaskLegal(Mask2, VT))
3404           return DAG.getVectorShuffle(VT, SDLoc(N), N1->getOperand(0),
3405                                       N0->getOperand(0), &Mask2[0]);
3406       }
3407     }
3408   }
3409
3410   // fold (or x, undef) -> -1
3411   if (!LegalOperations &&
3412       (N0.getOpcode() == ISD::UNDEF || N1.getOpcode() == ISD::UNDEF)) {
3413     EVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT;
3414     return DAG.getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
3415   }
3416   // fold (or c1, c2) -> c1|c2
3417   if (N0C && N1C)
3418     return DAG.FoldConstantArithmetic(ISD::OR, VT, N0C, N1C);
3419   // canonicalize constant to RHS
3420   if (N0C && !N1C)
3421     return DAG.getNode(ISD::OR, SDLoc(N), VT, N1, N0);
3422   // fold (or x, 0) -> x
3423   if (N1C && N1C->isNullValue())
3424     return N0;
3425   // fold (or x, -1) -> -1
3426   if (N1C && N1C->isAllOnesValue())
3427     return N1;
3428   // fold (or x, c) -> c iff (x & ~c) == 0
3429   if (N1C && DAG.MaskedValueIsZero(N0, ~N1C->getAPIntValue()))
3430     return N1;
3431
3432   // Recognize halfword bswaps as (bswap + rotl 16) or (bswap + shl 16)
3433   SDValue BSwap = MatchBSwapHWord(N, N0, N1);
3434   if (BSwap.getNode())
3435     return BSwap;
3436   BSwap = MatchBSwapHWordLow(N, N0, N1);
3437   if (BSwap.getNode())
3438     return BSwap;
3439
3440   // reassociate or
3441   SDValue ROR = ReassociateOps(ISD::OR, SDLoc(N), N0, N1);
3442   if (ROR.getNode())
3443     return ROR;
3444   // Canonicalize (or (and X, c1), c2) -> (and (or X, c2), c1|c2)
3445   // iff (c1 & c2) == 0.
3446   if (N1C && N0.getOpcode() == ISD::AND && N0.getNode()->hasOneUse() &&
3447              isa<ConstantSDNode>(N0.getOperand(1))) {
3448     ConstantSDNode *C1 = cast<ConstantSDNode>(N0.getOperand(1));
3449     if ((C1->getAPIntValue() & N1C->getAPIntValue()) != 0) {
3450       if (SDValue COR = DAG.FoldConstantArithmetic(ISD::OR, VT, N1C, C1))
3451         return DAG.getNode(
3452             ISD::AND, SDLoc(N), VT,
3453             DAG.getNode(ISD::OR, SDLoc(N0), VT, N0.getOperand(0), N1), COR);
3454       return SDValue();
3455     }
3456   }
3457   // fold (or (setcc x), (setcc y)) -> (setcc (or x, y))
3458   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
3459     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
3460     ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
3461
3462     if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
3463         LL.getValueType().isInteger()) {
3464       // fold (or (setne X, 0), (setne Y, 0)) -> (setne (or X, Y), 0)
3465       // fold (or (setlt X, 0), (setlt Y, 0)) -> (setne (or X, Y), 0)
3466       if (cast<ConstantSDNode>(LR)->isNullValue() &&
3467           (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) {
3468         SDValue ORNode = DAG.getNode(ISD::OR, SDLoc(LR),
3469                                      LR.getValueType(), LL, RL);
3470         AddToWorklist(ORNode.getNode());
3471         return DAG.getSetCC(SDLoc(N), VT, ORNode, LR, Op1);
3472       }
3473       // fold (or (setne X, -1), (setne Y, -1)) -> (setne (and X, Y), -1)
3474       // fold (or (setgt X, -1), (setgt Y  -1)) -> (setgt (and X, Y), -1)
3475       if (cast<ConstantSDNode>(LR)->isAllOnesValue() &&
3476           (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) {
3477         SDValue ANDNode = DAG.getNode(ISD::AND, SDLoc(LR),
3478                                       LR.getValueType(), LL, RL);
3479         AddToWorklist(ANDNode.getNode());
3480         return DAG.getSetCC(SDLoc(N), VT, ANDNode, LR, Op1);
3481       }
3482     }
3483     // canonicalize equivalent to ll == rl
3484     if (LL == RR && LR == RL) {
3485       Op1 = ISD::getSetCCSwappedOperands(Op1);
3486       std::swap(RL, RR);
3487     }
3488     if (LL == RL && LR == RR) {
3489       bool isInteger = LL.getValueType().isInteger();
3490       ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger);
3491       if (Result != ISD::SETCC_INVALID &&
3492           (!LegalOperations ||
3493            (TLI.isCondCodeLegal(Result, LL.getSimpleValueType()) &&
3494             TLI.isOperationLegal(ISD::SETCC,
3495               getSetCCResultType(N0.getValueType())))))
3496         return DAG.getSetCC(SDLoc(N), N0.getValueType(),
3497                             LL, LR, Result);
3498     }
3499   }
3500
3501   // Simplify: (or (op x...), (op y...))  -> (op (or x, y))
3502   if (N0.getOpcode() == N1.getOpcode()) {
3503     SDValue Tmp = SimplifyBinOpWithSameOpcodeHands(N);
3504     if (Tmp.getNode()) return Tmp;
3505   }
3506
3507   // (or (and X, C1), (and Y, C2))  -> (and (or X, Y), C3) if possible.
3508   if (N0.getOpcode() == ISD::AND &&
3509       N1.getOpcode() == ISD::AND &&
3510       N0.getOperand(1).getOpcode() == ISD::Constant &&
3511       N1.getOperand(1).getOpcode() == ISD::Constant &&
3512       // Don't increase # computations.
3513       (N0.getNode()->hasOneUse() || N1.getNode()->hasOneUse())) {
3514     // We can only do this xform if we know that bits from X that are set in C2
3515     // but not in C1 are already zero.  Likewise for Y.
3516     const APInt &LHSMask =
3517       cast<ConstantSDNode>(N0.getOperand(1))->getAPIntValue();
3518     const APInt &RHSMask =
3519       cast<ConstantSDNode>(N1.getOperand(1))->getAPIntValue();
3520
3521     if (DAG.MaskedValueIsZero(N0.getOperand(0), RHSMask&~LHSMask) &&
3522         DAG.MaskedValueIsZero(N1.getOperand(0), LHSMask&~RHSMask)) {
3523       SDValue X = DAG.getNode(ISD::OR, SDLoc(N0), VT,
3524                               N0.getOperand(0), N1.getOperand(0));
3525       return DAG.getNode(ISD::AND, SDLoc(N), VT, X,
3526                          DAG.getConstant(LHSMask | RHSMask, VT));
3527     }
3528   }
3529
3530   // (or (and X, M), (and X, N)) -> (and X, (or M, N))
3531   if (N0.getOpcode() == ISD::AND &&
3532       N1.getOpcode() == ISD::AND &&
3533       N0.getOperand(0) == N1.getOperand(0) &&
3534       // Don't increase # computations.
3535       (N0.getNode()->hasOneUse() || N1.getNode()->hasOneUse())) {
3536     SDValue X = DAG.getNode(ISD::OR, SDLoc(N0), VT,
3537                             N0.getOperand(1), N1.getOperand(1));
3538     return DAG.getNode(ISD::AND, SDLoc(N), VT, N0.getOperand(0), X);
3539   }
3540
3541   // See if this is some rotate idiom.
3542   if (SDNode *Rot = MatchRotate(N0, N1, SDLoc(N)))
3543     return SDValue(Rot, 0);
3544
3545   // Simplify the operands using demanded-bits information.
3546   if (!VT.isVector() &&
3547       SimplifyDemandedBits(SDValue(N, 0)))
3548     return SDValue(N, 0);
3549
3550   return SDValue();
3551 }
3552
3553 /// Match "(X shl/srl V1) & V2" where V2 may not be present.
3554 static bool MatchRotateHalf(SDValue Op, SDValue &Shift, SDValue &Mask) {
3555   if (Op.getOpcode() == ISD::AND) {
3556     if (isa<ConstantSDNode>(Op.getOperand(1))) {
3557       Mask = Op.getOperand(1);
3558       Op = Op.getOperand(0);
3559     } else {
3560       return false;
3561     }
3562   }
3563
3564   if (Op.getOpcode() == ISD::SRL || Op.getOpcode() == ISD::SHL) {
3565     Shift = Op;
3566     return true;
3567   }
3568
3569   return false;
3570 }
3571
3572 // Return true if we can prove that, whenever Neg and Pos are both in the
3573 // range [0, OpSize), Neg == (Pos == 0 ? 0 : OpSize - Pos).  This means that
3574 // for two opposing shifts shift1 and shift2 and a value X with OpBits bits:
3575 //
3576 //     (or (shift1 X, Neg), (shift2 X, Pos))
3577 //
3578 // reduces to a rotate in direction shift2 by Pos or (equivalently) a rotate
3579 // in direction shift1 by Neg.  The range [0, OpSize) means that we only need
3580 // to consider shift amounts with defined behavior.
3581 static bool matchRotateSub(SDValue Pos, SDValue Neg, unsigned OpSize) {
3582   // If OpSize is a power of 2 then:
3583   //
3584   //  (a) (Pos == 0 ? 0 : OpSize - Pos) == (OpSize - Pos) & (OpSize - 1)
3585   //  (b) Neg == Neg & (OpSize - 1) whenever Neg is in [0, OpSize).
3586   //
3587   // So if OpSize is a power of 2 and Neg is (and Neg', OpSize-1), we check
3588   // for the stronger condition:
3589   //
3590   //     Neg & (OpSize - 1) == (OpSize - Pos) & (OpSize - 1)    [A]
3591   //
3592   // for all Neg and Pos.  Since Neg & (OpSize - 1) == Neg' & (OpSize - 1)
3593   // we can just replace Neg with Neg' for the rest of the function.
3594   //
3595   // In other cases we check for the even stronger condition:
3596   //
3597   //     Neg == OpSize - Pos                                    [B]
3598   //
3599   // for all Neg and Pos.  Note that the (or ...) then invokes undefined
3600   // behavior if Pos == 0 (and consequently Neg == OpSize).
3601   //
3602   // We could actually use [A] whenever OpSize is a power of 2, but the
3603   // only extra cases that it would match are those uninteresting ones
3604   // where Neg and Pos are never in range at the same time.  E.g. for
3605   // OpSize == 32, using [A] would allow a Neg of the form (sub 64, Pos)
3606   // as well as (sub 32, Pos), but:
3607   //
3608   //     (or (shift1 X, (sub 64, Pos)), (shift2 X, Pos))
3609   //
3610   // always invokes undefined behavior for 32-bit X.
3611   //
3612   // Below, Mask == OpSize - 1 when using [A] and is all-ones otherwise.
3613   unsigned MaskLoBits = 0;
3614   if (Neg.getOpcode() == ISD::AND &&
3615       isPowerOf2_64(OpSize) &&
3616       Neg.getOperand(1).getOpcode() == ISD::Constant &&
3617       cast<ConstantSDNode>(Neg.getOperand(1))->getAPIntValue() == OpSize - 1) {
3618     Neg = Neg.getOperand(0);
3619     MaskLoBits = Log2_64(OpSize);
3620   }
3621
3622   // Check whether Neg has the form (sub NegC, NegOp1) for some NegC and NegOp1.
3623   if (Neg.getOpcode() != ISD::SUB)
3624     return 0;
3625   ConstantSDNode *NegC = dyn_cast<ConstantSDNode>(Neg.getOperand(0));
3626   if (!NegC)
3627     return 0;
3628   SDValue NegOp1 = Neg.getOperand(1);
3629
3630   // On the RHS of [A], if Pos is Pos' & (OpSize - 1), just replace Pos with
3631   // Pos'.  The truncation is redundant for the purpose of the equality.
3632   if (MaskLoBits &&
3633       Pos.getOpcode() == ISD::AND &&
3634       Pos.getOperand(1).getOpcode() == ISD::Constant &&
3635       cast<ConstantSDNode>(Pos.getOperand(1))->getAPIntValue() == OpSize - 1)
3636     Pos = Pos.getOperand(0);
3637
3638   // The condition we need is now:
3639   //
3640   //     (NegC - NegOp1) & Mask == (OpSize - Pos) & Mask
3641   //
3642   // If NegOp1 == Pos then we need:
3643   //
3644   //              OpSize & Mask == NegC & Mask
3645   //
3646   // (because "x & Mask" is a truncation and distributes through subtraction).
3647   APInt Width;
3648   if (Pos == NegOp1)
3649     Width = NegC->getAPIntValue();
3650   // Check for cases where Pos has the form (add NegOp1, PosC) for some PosC.
3651   // Then the condition we want to prove becomes:
3652   //
3653   //     (NegC - NegOp1) & Mask == (OpSize - (NegOp1 + PosC)) & Mask
3654   //
3655   // which, again because "x & Mask" is a truncation, becomes:
3656   //
3657   //                NegC & Mask == (OpSize - PosC) & Mask
3658   //              OpSize & Mask == (NegC + PosC) & Mask
3659   else if (Pos.getOpcode() == ISD::ADD &&
3660            Pos.getOperand(0) == NegOp1 &&
3661            Pos.getOperand(1).getOpcode() == ISD::Constant)
3662     Width = (cast<ConstantSDNode>(Pos.getOperand(1))->getAPIntValue() +
3663              NegC->getAPIntValue());
3664   else
3665     return false;
3666
3667   // Now we just need to check that OpSize & Mask == Width & Mask.
3668   if (MaskLoBits)
3669     // Opsize & Mask is 0 since Mask is Opsize - 1.
3670     return Width.getLoBits(MaskLoBits) == 0;
3671   return Width == OpSize;
3672 }
3673
3674 // A subroutine of MatchRotate used once we have found an OR of two opposite
3675 // shifts of Shifted.  If Neg == <operand size> - Pos then the OR reduces
3676 // to both (PosOpcode Shifted, Pos) and (NegOpcode Shifted, Neg), with the
3677 // former being preferred if supported.  InnerPos and InnerNeg are Pos and
3678 // Neg with outer conversions stripped away.
3679 SDNode *DAGCombiner::MatchRotatePosNeg(SDValue Shifted, SDValue Pos,
3680                                        SDValue Neg, SDValue InnerPos,
3681                                        SDValue InnerNeg, unsigned PosOpcode,
3682                                        unsigned NegOpcode, SDLoc DL) {
3683   // fold (or (shl x, (*ext y)),
3684   //          (srl x, (*ext (sub 32, y)))) ->
3685   //   (rotl x, y) or (rotr x, (sub 32, y))
3686   //
3687   // fold (or (shl x, (*ext (sub 32, y))),
3688   //          (srl x, (*ext y))) ->
3689   //   (rotr x, y) or (rotl x, (sub 32, y))
3690   EVT VT = Shifted.getValueType();
3691   if (matchRotateSub(InnerPos, InnerNeg, VT.getSizeInBits())) {
3692     bool HasPos = TLI.isOperationLegalOrCustom(PosOpcode, VT);
3693     return DAG.getNode(HasPos ? PosOpcode : NegOpcode, DL, VT, Shifted,
3694                        HasPos ? Pos : Neg).getNode();
3695   }
3696
3697   return nullptr;
3698 }
3699
3700 // MatchRotate - Handle an 'or' of two operands.  If this is one of the many
3701 // idioms for rotate, and if the target supports rotation instructions, generate
3702 // a rot[lr].
3703 SDNode *DAGCombiner::MatchRotate(SDValue LHS, SDValue RHS, SDLoc DL) {
3704   // Must be a legal type.  Expanded 'n promoted things won't work with rotates.
3705   EVT VT = LHS.getValueType();
3706   if (!TLI.isTypeLegal(VT)) return nullptr;
3707
3708   // The target must have at least one rotate flavor.
3709   bool HasROTL = TLI.isOperationLegalOrCustom(ISD::ROTL, VT);
3710   bool HasROTR = TLI.isOperationLegalOrCustom(ISD::ROTR, VT);
3711   if (!HasROTL && !HasROTR) return nullptr;
3712
3713   // Match "(X shl/srl V1) & V2" where V2 may not be present.
3714   SDValue LHSShift;   // The shift.
3715   SDValue LHSMask;    // AND value if any.
3716   if (!MatchRotateHalf(LHS, LHSShift, LHSMask))
3717     return nullptr; // Not part of a rotate.
3718
3719   SDValue RHSShift;   // The shift.
3720   SDValue RHSMask;    // AND value if any.
3721   if (!MatchRotateHalf(RHS, RHSShift, RHSMask))
3722     return nullptr; // Not part of a rotate.
3723
3724   if (LHSShift.getOperand(0) != RHSShift.getOperand(0))
3725     return nullptr;   // Not shifting the same value.
3726
3727   if (LHSShift.getOpcode() == RHSShift.getOpcode())
3728     return nullptr;   // Shifts must disagree.
3729
3730   // Canonicalize shl to left side in a shl/srl pair.
3731   if (RHSShift.getOpcode() == ISD::SHL) {
3732     std::swap(LHS, RHS);
3733     std::swap(LHSShift, RHSShift);
3734     std::swap(LHSMask , RHSMask );
3735   }
3736
3737   unsigned OpSizeInBits = VT.getSizeInBits();
3738   SDValue LHSShiftArg = LHSShift.getOperand(0);
3739   SDValue LHSShiftAmt = LHSShift.getOperand(1);
3740   SDValue RHSShiftArg = RHSShift.getOperand(0);
3741   SDValue RHSShiftAmt = RHSShift.getOperand(1);
3742
3743   // fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1)
3744   // fold (or (shl x, C1), (srl x, C2)) -> (rotr x, C2)
3745   if (LHSShiftAmt.getOpcode() == ISD::Constant &&
3746       RHSShiftAmt.getOpcode() == ISD::Constant) {
3747     uint64_t LShVal = cast<ConstantSDNode>(LHSShiftAmt)->getZExtValue();
3748     uint64_t RShVal = cast<ConstantSDNode>(RHSShiftAmt)->getZExtValue();
3749     if ((LShVal + RShVal) != OpSizeInBits)
3750       return nullptr;
3751
3752     SDValue Rot = DAG.getNode(HasROTL ? ISD::ROTL : ISD::ROTR, DL, VT,
3753                               LHSShiftArg, HasROTL ? LHSShiftAmt : RHSShiftAmt);
3754
3755     // If there is an AND of either shifted operand, apply it to the result.
3756     if (LHSMask.getNode() || RHSMask.getNode()) {
3757       APInt Mask = APInt::getAllOnesValue(OpSizeInBits);
3758
3759       if (LHSMask.getNode()) {
3760         APInt RHSBits = APInt::getLowBitsSet(OpSizeInBits, LShVal);
3761         Mask &= cast<ConstantSDNode>(LHSMask)->getAPIntValue() | RHSBits;
3762       }
3763       if (RHSMask.getNode()) {
3764         APInt LHSBits = APInt::getHighBitsSet(OpSizeInBits, RShVal);
3765         Mask &= cast<ConstantSDNode>(RHSMask)->getAPIntValue() | LHSBits;
3766       }
3767
3768       Rot = DAG.getNode(ISD::AND, DL, VT, Rot, DAG.getConstant(Mask, VT));
3769     }
3770
3771     return Rot.getNode();
3772   }
3773
3774   // If there is a mask here, and we have a variable shift, we can't be sure
3775   // that we're masking out the right stuff.
3776   if (LHSMask.getNode() || RHSMask.getNode())
3777     return nullptr;
3778
3779   // If the shift amount is sign/zext/any-extended just peel it off.
3780   SDValue LExtOp0 = LHSShiftAmt;
3781   SDValue RExtOp0 = RHSShiftAmt;
3782   if ((LHSShiftAmt.getOpcode() == ISD::SIGN_EXTEND ||
3783        LHSShiftAmt.getOpcode() == ISD::ZERO_EXTEND ||
3784        LHSShiftAmt.getOpcode() == ISD::ANY_EXTEND ||
3785        LHSShiftAmt.getOpcode() == ISD::TRUNCATE) &&
3786       (RHSShiftAmt.getOpcode() == ISD::SIGN_EXTEND ||
3787        RHSShiftAmt.getOpcode() == ISD::ZERO_EXTEND ||
3788        RHSShiftAmt.getOpcode() == ISD::ANY_EXTEND ||
3789        RHSShiftAmt.getOpcode() == ISD::TRUNCATE)) {
3790     LExtOp0 = LHSShiftAmt.getOperand(0);
3791     RExtOp0 = RHSShiftAmt.getOperand(0);
3792   }
3793
3794   SDNode *TryL = MatchRotateP