lib/CodeGen/SelectionDAG/DAGCombiner.cpp

   1 //===-- DAGCombiner.cpp - Implement a DAG node combiner -------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Nate Begeman and is distributed under the
   6 // University of Illinois Open Source 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 // FIXME: Missing folds
  14 // sdiv, udiv, srem, urem (X, const) where X is an integer can be expanded into
  15 //  a sequence of multiplies, shifts, and adds.  This should be controlled by
  16 //  some kind of hint from the target that int div is expensive.
  17 // various folds of mulh[s,u] by constants such as -1, powers of 2, etc.
  18 //
  19 // FIXME: select C, pow2, pow2 -> something smart
  20 // FIXME: trunc(select X, Y, Z) -> select X, trunc(Y), trunc(Z)
  21 // FIXME: Dead stores -> nuke
  22 // FIXME: shr X, (and Y,31) -> shr X, Y   (TRICKY!)
  23 // FIXME: mul (x, const) -> shifts + adds
  24 // FIXME: undef values
  25 // FIXME: divide by zero is currently left unfolded.  do we want to turn this
  26 //        into an undef?
  27 // FIXME: select ne (select cc, 1, 0), 0, true, false -> select cc, true, false
  28 //
  29 //===----------------------------------------------------------------------===//
  30
  31 #define DEBUG_TYPE "dagcombine"
  32 #include "llvm/ADT/Statistic.h"
  33 #include "llvm/Analysis/AliasAnalysis.h"
  34 #include "llvm/CodeGen/SelectionDAG.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/MathExtras.h"
  37 #include "llvm/Target/TargetLowering.h"
  38 #include "llvm/Target/TargetOptions.h"
  39 #include "llvm/Support/Compiler.h"
  40 #include "llvm/Support/CommandLine.h"
  41 #include <algorithm>
  42 using namespace llvm;
  43
  44 STATISTIC(NodesCombined   , "Number of dag nodes combined");
  45 STATISTIC(PreIndexedNodes , "Number of pre-indexed nodes created");
  46 STATISTIC(PostIndexedNodes, "Number of post-indexed nodes created");
  47
  48 namespace {
  49 #ifndef NDEBUG
  50   static cl::opt<bool>
  51     ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
  52                     cl::desc("Pop up a window to show dags before the first "
  53                              "dag combine pass"));
  54   static cl::opt<bool>
  55     ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
  56                     cl::desc("Pop up a window to show dags before the second "
  57                              "dag combine pass"));
  58 #else
  59   static const bool ViewDAGCombine1 = false;
  60   static const bool ViewDAGCombine2 = false;
  61 #endif
  62
  63   static cl::opt<bool>
  64     CombinerAA("combiner-alias-analysis", cl::Hidden,
  65                cl::desc("Turn on alias analysis during testing"));
  66
  67   static cl::opt<bool>
  68     CombinerGlobalAA("combiner-global-alias-analysis", cl::Hidden,
  69                cl::desc("Include global information in alias analysis"));
  70
  71 //------------------------------ DAGCombiner ---------------------------------//
  72
  73   class VISIBILITY_HIDDEN DAGCombiner {
  74     SelectionDAG &DAG;
  75     TargetLowering &TLI;
  76     bool AfterLegalize;
  77
  78     // Worklist of all of the nodes that need to be simplified.
  79     std::vector<SDNode*> WorkList;
  80
  81     // AA - Used for DAG load/store alias analysis.
  82     AliasAnalysis &AA;
  83
  84     /// AddUsersToWorkList - When an instruction is simplified, add all users of
  85     /// the instruction to the work lists because they might get more simplified
  86     /// now.
  87     ///
  88     void AddUsersToWorkList(SDNode *N) {
  89       for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
  90            UI != UE; ++UI)
  91         AddToWorkList(*UI);
  92     }
  93
  94     /// removeFromWorkList - remove all instances of N from the worklist.
  95     ///
  96     void removeFromWorkList(SDNode *N) {
  97       WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N),
  98                      WorkList.end());
  99     }
 100
 101   public:
 102     /// AddToWorkList - Add to the work list making sure it's instance is at the
 103     /// the back (next to be processed.)
 104     void AddToWorkList(SDNode *N) {
 105       removeFromWorkList(N);
 106       WorkList.push_back(N);
 107     }
 108
 109     SDOperand CombineTo(SDNode *N, const SDOperand *To, unsigned NumTo,
 110                         bool AddTo = true) {
 111       assert(N->getNumValues() == NumTo && "Broken CombineTo call!");
 112       ++NodesCombined;
 113       DOUT << "\nReplacing.1 "; DEBUG(N->dump());
 114       DOUT << "\nWith: "; DEBUG(To[0].Val->dump(&DAG));
 115       DOUT << " and " << NumTo-1 << " other values\n";
 116       std::vector<SDNode*> NowDead;
 117       DAG.ReplaceAllUsesWith(N, To, &NowDead);
 118
 119       if (AddTo) {
 120         // Push the new nodes and any users onto the worklist
 121         for (unsigned i = 0, e = NumTo; i != e; ++i) {
 122           AddToWorkList(To[i].Val);
 123           AddUsersToWorkList(To[i].Val);
 124         }
 125       }
 126
 127       // Nodes can be reintroduced into the worklist.  Make sure we do not
 128       // process a node that has been replaced.
 129       removeFromWorkList(N);
 130       for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
 131         removeFromWorkList(NowDead[i]);
 132
 133       // Finally, since the node is now dead, remove it from the graph.
 134       DAG.DeleteNode(N);
 135       return SDOperand(N, 0);
 136     }
 137
 138     SDOperand CombineTo(SDNode *N, SDOperand Res, bool AddTo = true) {
 139       return CombineTo(N, &Res, 1, AddTo);
 140     }
 141
 142     SDOperand CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1,
 143                         bool AddTo = true) {
 144       SDOperand To[] = { Res0, Res1 };
 145       return CombineTo(N, To, 2, AddTo);
 146     }
 147   private:
 148
 149     /// SimplifyDemandedBits - Check the specified integer node value to see if
 150     /// it can be simplified or if things it uses can be simplified by bit
 151     /// propagation.  If so, return true.
 152     bool SimplifyDemandedBits(SDOperand Op) {
 153       TargetLowering::TargetLoweringOpt TLO(DAG);
 154       uint64_t KnownZero, KnownOne;
 155       uint64_t Demanded = MVT::getIntVTBitMask(Op.getValueType());
 156       if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO))
 157         return false;
 158
 159       // Revisit the node.
 160       AddToWorkList(Op.Val);
 161
 162       // Replace the old value with the new one.
 163       ++NodesCombined;
 164       DOUT << "\nReplacing.2 "; DEBUG(TLO.Old.Val->dump());
 165       DOUT << "\nWith: "; DEBUG(TLO.New.Val->dump(&DAG));
 166       DOUT << '\n';
 167
 168       std::vector<SDNode*> NowDead;
 169       DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, NowDead);
 170
 171       // Push the new node and any (possibly new) users onto the worklist.
 172       AddToWorkList(TLO.New.Val);
 173       AddUsersToWorkList(TLO.New.Val);
 174
 175       // Nodes can end up on the worklist more than once.  Make sure we do
 176       // not process a node that has been replaced.
 177       for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
 178         removeFromWorkList(NowDead[i]);
 179
 180       // Finally, if the node is now dead, remove it from the graph.  The node
 181       // may not be dead if the replacement process recursively simplified to
 182       // something else needing this node.
 183       if (TLO.Old.Val->use_empty()) {
 184         removeFromWorkList(TLO.Old.Val);
 185         DAG.DeleteNode(TLO.Old.Val);
 186       }
 187       return true;
 188     }
 189
 190     bool CombineToPreIndexedLoadStore(SDNode *N);
 191     bool CombineToPostIndexedLoadStore(SDNode *N);
 192
 193
 194     /// visit - call the node-specific routine that knows how to fold each
 195     /// particular type of node.
 196     SDOperand visit(SDNode *N);
 197
 198     // Visitation implementation - Implement dag node combining for different
 199     // node types.  The semantics are as follows:
 200     // Return Value:
 201     //   SDOperand.Val == 0   - No change was made
 202     //   SDOperand.Val == N   - N was replaced, is dead, and is already handled.
 203     //   otherwise            - N should be replaced by the returned Operand.
 204     //
 205     SDOperand visitTokenFactor(SDNode *N);
 206     SDOperand visitADD(SDNode *N);
 207     SDOperand visitSUB(SDNode *N);
 208     SDOperand visitMUL(SDNode *N);
 209     SDOperand visitSDIV(SDNode *N);
 210     SDOperand visitUDIV(SDNode *N);
 211     SDOperand visitSREM(SDNode *N);
 212     SDOperand visitUREM(SDNode *N);
 213     SDOperand visitMULHU(SDNode *N);
 214     SDOperand visitMULHS(SDNode *N);
 215     SDOperand visitAND(SDNode *N);
 216     SDOperand visitOR(SDNode *N);
 217     SDOperand visitXOR(SDNode *N);
 218     SDOperand visitVBinOp(SDNode *N, ISD::NodeType IntOp, ISD::NodeType FPOp);
 219     SDOperand visitSHL(SDNode *N);
 220     SDOperand visitSRA(SDNode *N);
 221     SDOperand visitSRL(SDNode *N);
 222     SDOperand visitCTLZ(SDNode *N);
 223     SDOperand visitCTTZ(SDNode *N);
 224     SDOperand visitCTPOP(SDNode *N);
 225     SDOperand visitSELECT(SDNode *N);
 226     SDOperand visitSELECT_CC(SDNode *N);
 227     SDOperand visitSETCC(SDNode *N);
 228     SDOperand visitSIGN_EXTEND(SDNode *N);
 229     SDOperand visitZERO_EXTEND(SDNode *N);
 230     SDOperand visitANY_EXTEND(SDNode *N);
 231     SDOperand visitSIGN_EXTEND_INREG(SDNode *N);
 232     SDOperand visitTRUNCATE(SDNode *N);
 233     SDOperand visitBIT_CONVERT(SDNode *N);
 234     SDOperand visitVBIT_CONVERT(SDNode *N);
 235     SDOperand visitFADD(SDNode *N);
 236     SDOperand visitFSUB(SDNode *N);
 237     SDOperand visitFMUL(SDNode *N);
 238     SDOperand visitFDIV(SDNode *N);
 239     SDOperand visitFREM(SDNode *N);
 240     SDOperand visitFCOPYSIGN(SDNode *N);
 241     SDOperand visitSINT_TO_FP(SDNode *N);
 242     SDOperand visitUINT_TO_FP(SDNode *N);
 243     SDOperand visitFP_TO_SINT(SDNode *N);
 244     SDOperand visitFP_TO_UINT(SDNode *N);
 245     SDOperand visitFP_ROUND(SDNode *N);
 246     SDOperand visitFP_ROUND_INREG(SDNode *N);
 247     SDOperand visitFP_EXTEND(SDNode *N);
 248     SDOperand visitFNEG(SDNode *N);
 249     SDOperand visitFABS(SDNode *N);
 250     SDOperand visitBRCOND(SDNode *N);
 251     SDOperand visitBR_CC(SDNode *N);
 252     SDOperand visitLOAD(SDNode *N);
 253     SDOperand visitSTORE(SDNode *N);
 254     SDOperand visitINSERT_VECTOR_ELT(SDNode *N);
 255     SDOperand visitVINSERT_VECTOR_ELT(SDNode *N);
 256     SDOperand visitVBUILD_VECTOR(SDNode *N);
 257     SDOperand visitVECTOR_SHUFFLE(SDNode *N);
 258     SDOperand visitVVECTOR_SHUFFLE(SDNode *N);
 259
 260     SDOperand XformToShuffleWithZero(SDNode *N);
 261     SDOperand ReassociateOps(unsigned Opc, SDOperand LHS, SDOperand RHS);
 262
 263     bool SimplifySelectOps(SDNode *SELECT, SDOperand LHS, SDOperand RHS);
 264     SDOperand SimplifyBinOpWithSameOpcodeHands(SDNode *N);
 265     SDOperand SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2);
 266     SDOperand SimplifySelectCC(SDOperand N0, SDOperand N1, SDOperand N2,
 267                                SDOperand N3, ISD::CondCode CC);
 268     SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
 269                             ISD::CondCode Cond, bool foldBooleans = true);
 270     SDOperand ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *, MVT::ValueType);
 271     SDOperand BuildSDIV(SDNode *N);
 272     SDOperand BuildUDIV(SDNode *N);
 273     SDNode *MatchRotate(SDOperand LHS, SDOperand RHS);
 274
 275     /// GatherAllAliases - Walk up chain skipping non-aliasing memory nodes,
 276     /// looking for aliasing nodes and adding them to the Aliases vector.
 277     void GatherAllAliases(SDNode *N, SDOperand OriginalChain,
 278                           SmallVector<SDOperand, 8> &Aliases);
 279
 280     /// isAlias - Return true if there is any possibility that the two addresses
 281     /// overlap.
 282     bool isAlias(SDOperand Ptr1, int64_t Size1,
 283                  const Value *SrcValue1, int SrcValueOffset1,
 284                  SDOperand Ptr2, int64_t Size2,
 285                  const Value *SrcValue2, int SrcValueOffset2);
 286
 287     /// FindAliasInfo - Extracts the relevant alias information from the memory
 288     /// node.  Returns true if the operand was a load.
 289     bool FindAliasInfo(SDNode *N,
 290                        SDOperand &Ptr, int64_t &Size,
 291                        const Value *&SrcValue, int &SrcValueOffset);
 292
 293     /// FindBetterChain - Walk up chain skipping non-aliasing memory nodes,
 294     /// looking for a better chain (aliasing node.)
 295     SDOperand FindBetterChain(SDNode *N, SDOperand Chain);
 296
 297 public:
 298     DAGCombiner(SelectionDAG &D, AliasAnalysis &A)
 299       : DAG(D),
 300         TLI(D.getTargetLoweringInfo()),
 301         AfterLegalize(false),
 302         AA(A) {}
 303
 304     /// Run - runs the dag combiner on all nodes in the work list
 305     void Run(bool RunningAfterLegalize);
 306   };
 307 }
 308
 309 //===----------------------------------------------------------------------===//
 310 //  TargetLowering::DAGCombinerInfo implementation
 311 //===----------------------------------------------------------------------===//
 312
 313 void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) {
 314   ((DAGCombiner*)DC)->AddToWorkList(N);
 315 }
 316
 317 SDOperand TargetLowering::DAGCombinerInfo::
 318 CombineTo(SDNode *N, const std::vector<SDOperand> &To) {
 319   return ((DAGCombiner*)DC)->CombineTo(N, &To[0], To.size());
 320 }
 321
 322 SDOperand TargetLowering::DAGCombinerInfo::
 323 CombineTo(SDNode *N, SDOperand Res) {
 324   return ((DAGCombiner*)DC)->CombineTo(N, Res);
 325 }
 326
 327
 328 SDOperand TargetLowering::DAGCombinerInfo::
 329 CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) {
 330   return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1);
 331 }
 332
 333
 334
 335
 336 //===----------------------------------------------------------------------===//
 337
 338
 339 // isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc
 340 // that selects between the values 1 and 0, making it equivalent to a setcc.
 341 // Also, set the incoming LHS, RHS, and CC references to the appropriate
 342 // nodes based on the type of node we are checking.  This simplifies life a
 343 // bit for the callers.
 344 static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS,
 345                               SDOperand &CC) {
 346   if (N.getOpcode() == ISD::SETCC) {
 347     LHS = N.getOperand(0);
 348     RHS = N.getOperand(1);
 349     CC  = N.getOperand(2);
 350     return true;
 351   }
 352   if (N.getOpcode() == ISD::SELECT_CC &&
 353       N.getOperand(2).getOpcode() == ISD::Constant &&
 354       N.getOperand(3).getOpcode() == ISD::Constant &&
 355       cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 &&
 356       cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) {
 357     LHS = N.getOperand(0);
 358     RHS = N.getOperand(1);
 359     CC  = N.getOperand(4);
 360     return true;
 361   }
 362   return false;
 363 }
 364
 365 // isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only
 366 // one use.  If this is true, it allows the users to invert the operation for
 367 // free when it is profitable to do so.
 368 static bool isOneUseSetCC(SDOperand N) {
 369   SDOperand N0, N1, N2;
 370   if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse())
 371     return true;
 372   return false;
 373 }
 374
 375 SDOperand DAGCombiner::ReassociateOps(unsigned Opc, SDOperand N0, SDOperand N1){
 376   MVT::ValueType VT = N0.getValueType();
 377   // reassoc. (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one use
 378   // reassoc. (op (op x, c1), c2) -> (op x, (op c1, c2))
 379   if (N0.getOpcode() == Opc && isa<ConstantSDNode>(N0.getOperand(1))) {
 380     if (isa<ConstantSDNode>(N1)) {
 381       SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(1), N1);
 382       AddToWorkList(OpNode.Val);
 383       return DAG.getNode(Opc, VT, OpNode, N0.getOperand(0));
 384     } else if (N0.hasOneUse()) {
 385       SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(0), N1);
 386       AddToWorkList(OpNode.Val);
 387       return DAG.getNode(Opc, VT, OpNode, N0.getOperand(1));
 388     }
 389   }
 390   // reassoc. (op y, (op x, c1)) -> (op (op x, y), c1) iff x+c1 has one use
 391   // reassoc. (op c2, (op x, c1)) -> (op x, (op c1, c2))
 392   if (N1.getOpcode() == Opc && isa<ConstantSDNode>(N1.getOperand(1))) {
 393     if (isa<ConstantSDNode>(N0)) {
 394       SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(1), N0);
 395       AddToWorkList(OpNode.Val);
 396       return DAG.getNode(Opc, VT, OpNode, N1.getOperand(0));
 397     } else if (N1.hasOneUse()) {
 398       SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(0), N0);
 399       AddToWorkList(OpNode.Val);
 400       return DAG.getNode(Opc, VT, OpNode, N1.getOperand(1));
 401     }
 402   }
 403   return SDOperand();
 404 }
 405
 406 void DAGCombiner::Run(bool RunningAfterLegalize) {
 407   // set the instance variable, so that the various visit routines may use it.
 408   AfterLegalize = RunningAfterLegalize;
 409
 410   // Add all the dag nodes to the worklist.
 411   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
 412        E = DAG.allnodes_end(); I != E; ++I)
 413     WorkList.push_back(I);
 414
 415   // Create a dummy node (which is not added to allnodes), that adds a reference
 416   // to the root node, preventing it from being deleted, and tracking any
 417   // changes of the root.
 418   HandleSDNode Dummy(DAG.getRoot());
 419
 420   // The root of the dag may dangle to deleted nodes until the dag combiner is
 421   // done.  Set it to null to avoid confusion.
 422   DAG.setRoot(SDOperand());
 423
 424   /// DagCombineInfo - Expose the DAG combiner to the target combiner impls.
 425   TargetLowering::DAGCombinerInfo
 426     DagCombineInfo(DAG, !RunningAfterLegalize, false, this);
 427
 428   // while the worklist isn't empty, inspect the node on the end of it and
 429   // try and combine it.
 430   while (!WorkList.empty()) {
 431     SDNode *N = WorkList.back();
 432     WorkList.pop_back();
 433
 434     // If N has no uses, it is dead.  Make sure to revisit all N's operands once
 435     // N is deleted from the DAG, since they too may now be dead or may have a
 436     // reduced number of uses, allowing other xforms.
 437     if (N->use_empty() && N != &Dummy) {
 438       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 439         AddToWorkList(N->getOperand(i).Val);
 440
 441       DAG.DeleteNode(N);
 442       continue;
 443     }
 444
 445     SDOperand RV = visit(N);
 446
 447     // If nothing happened, try a target-specific DAG combine.
 448     if (RV.Val == 0) {
 449       assert(N->getOpcode() != ISD::DELETED_NODE &&
 450              "Node was deleted but visit returned NULL!");
 451       if (N->getOpcode() >= ISD::BUILTIN_OP_END ||
 452           TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode()))
 453         RV = TLI.PerformDAGCombine(N, DagCombineInfo);
 454     }
 455
 456     if (RV.Val) {
 457       ++NodesCombined;
 458       // If we get back the same node we passed in, rather than a new node or
 459       // zero, we know that the node must have defined multiple values and
 460       // CombineTo was used.  Since CombineTo takes care of the worklist
 461       // mechanics for us, we have no work to do in this case.
 462       if (RV.Val != N) {
 463         assert(N->getOpcode() != ISD::DELETED_NODE &&
 464                RV.Val->getOpcode() != ISD::DELETED_NODE &&
 465                "Node was deleted but visit returned new node!");
 466
 467         DOUT << "\nReplacing.3 "; DEBUG(N->dump());
 468         DOUT << "\nWith: "; DEBUG(RV.Val->dump(&DAG));
 469         DOUT << '\n';
 470         std::vector<SDNode*> NowDead;
 471         if (N->getNumValues() == RV.Val->getNumValues())
 472           DAG.ReplaceAllUsesWith(N, RV.Val, &NowDead);
 473         else {
 474           assert(N->getValueType(0) == RV.getValueType() && "Type mismatch");
 475           SDOperand OpV = RV;
 476           DAG.ReplaceAllUsesWith(N, &OpV, &NowDead);
 477         }
 478
 479         // Push the new node and any users onto the worklist
 480         AddToWorkList(RV.Val);
 481         AddUsersToWorkList(RV.Val);
 482
 483         // Nodes can be reintroduced into the worklist.  Make sure we do not
 484         // process a node that has been replaced.
 485         removeFromWorkList(N);
 486         for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
 487           removeFromWorkList(NowDead[i]);
 488
 489         // Finally, since the node is now dead, remove it from the graph.
 490         DAG.DeleteNode(N);
 491       }
 492     }
 493   }
 494
 495   // If the root changed (e.g. it was a dead load, update the root).
 496   DAG.setRoot(Dummy.getValue());
 497 }
 498
 499 SDOperand DAGCombiner::visit(SDNode *N) {
 500   switch(N->getOpcode()) {
 501   default: break;
 502   case ISD::TokenFactor:        return visitTokenFactor(N);
 503   case ISD::ADD:                return visitADD(N);
 504   case ISD::SUB:                return visitSUB(N);
 505   case ISD::MUL:                return visitMUL(N);
 506   case ISD::SDIV:               return visitSDIV(N);
 507   case ISD::UDIV:               return visitUDIV(N);
 508   case ISD::SREM:               return visitSREM(N);
 509   case ISD::UREM:               return visitUREM(N);
 510   case ISD::MULHU:              return visitMULHU(N);
 511   case ISD::MULHS:              return visitMULHS(N);
 512   case ISD::AND:                return visitAND(N);
 513   case ISD::OR:                 return visitOR(N);
 514   case ISD::XOR:                return visitXOR(N);
 515   case ISD::SHL:                return visitSHL(N);
 516   case ISD::SRA:                return visitSRA(N);
 517   case ISD::SRL:                return visitSRL(N);
 518   case ISD::CTLZ:               return visitCTLZ(N);
 519   case ISD::CTTZ:               return visitCTTZ(N);
 520   case ISD::CTPOP:              return visitCTPOP(N);
 521   case ISD::SELECT:             return visitSELECT(N);
 522   case ISD::SELECT_CC:          return visitSELECT_CC(N);
 523   case ISD::SETCC:              return visitSETCC(N);
 524   case ISD::SIGN_EXTEND:        return visitSIGN_EXTEND(N);
 525   case ISD::ZERO_EXTEND:        return visitZERO_EXTEND(N);
 526   case ISD::ANY_EXTEND:         return visitANY_EXTEND(N);
 527   case ISD::SIGN_EXTEND_INREG:  return visitSIGN_EXTEND_INREG(N);
 528   case ISD::TRUNCATE:           return visitTRUNCATE(N);
 529   case ISD::BIT_CONVERT:        return visitBIT_CONVERT(N);
 530   case ISD::VBIT_CONVERT:       return visitVBIT_CONVERT(N);
 531   case ISD::FADD:               return visitFADD(N);
 532   case ISD::FSUB:               return visitFSUB(N);
 533   case ISD::FMUL:               return visitFMUL(N);
 534   case ISD::FDIV:               return visitFDIV(N);
 535   case ISD::FREM:               return visitFREM(N);
 536   case ISD::FCOPYSIGN:          return visitFCOPYSIGN(N);
 537   case ISD::SINT_TO_FP:         return visitSINT_TO_FP(N);
 538   case ISD::UINT_TO_FP:         return visitUINT_TO_FP(N);
 539   case ISD::FP_TO_SINT:         return visitFP_TO_SINT(N);
 540   case ISD::FP_TO_UINT:         return visitFP_TO_UINT(N);
 541   case ISD::FP_ROUND:           return visitFP_ROUND(N);
 542   case ISD::FP_ROUND_INREG:     return visitFP_ROUND_INREG(N);
 543   case ISD::FP_EXTEND:          return visitFP_EXTEND(N);
 544   case ISD::FNEG:               return visitFNEG(N);
 545   case ISD::FABS:               return visitFABS(N);
 546   case ISD::BRCOND:             return visitBRCOND(N);
 547   case ISD::BR_CC:              return visitBR_CC(N);
 548   case ISD::LOAD:               return visitLOAD(N);
 549   case ISD::STORE:              return visitSTORE(N);
 550   case ISD::INSERT_VECTOR_ELT:  return visitINSERT_VECTOR_ELT(N);
 551   case ISD::VINSERT_VECTOR_ELT: return visitVINSERT_VECTOR_ELT(N);
 552   case ISD::VBUILD_VECTOR:      return visitVBUILD_VECTOR(N);
 553   case ISD::VECTOR_SHUFFLE:     return visitVECTOR_SHUFFLE(N);
 554   case ISD::VVECTOR_SHUFFLE:    return visitVVECTOR_SHUFFLE(N);
 555   case ISD::VADD:               return visitVBinOp(N, ISD::ADD , ISD::FADD);
 556   case ISD::VSUB:               return visitVBinOp(N, ISD::SUB , ISD::FSUB);
 557   case ISD::VMUL:               return visitVBinOp(N, ISD::MUL , ISD::FMUL);
 558   case ISD::VSDIV:              return visitVBinOp(N, ISD::SDIV, ISD::FDIV);
 559   case ISD::VUDIV:              return visitVBinOp(N, ISD::UDIV, ISD::UDIV);
 560   case ISD::VAND:               return visitVBinOp(N, ISD::AND , ISD::AND);
 561   case ISD::VOR:                return visitVBinOp(N, ISD::OR  , ISD::OR);
 562   case ISD::VXOR:               return visitVBinOp(N, ISD::XOR , ISD::XOR);
 563   }
 564   return SDOperand();
 565 }
 566
 567 /// getInputChainForNode - Given a node, return its input chain if it has one,
 568 /// otherwise return a null sd operand.
 569 static SDOperand getInputChainForNode(SDNode *N) {
 570   if (unsigned NumOps = N->getNumOperands()) {
 571     if (N->getOperand(0).getValueType() == MVT::Other)
 572       return N->getOperand(0);
 573     else if (N->getOperand(NumOps-1).getValueType() == MVT::Other)
 574       return N->getOperand(NumOps-1);
 575     for (unsigned i = 1; i < NumOps-1; ++i)
 576       if (N->getOperand(i).getValueType() == MVT::Other)
 577         return N->getOperand(i);
 578   }
 579   return SDOperand(0, 0);
 580 }
 581
 582 SDOperand DAGCombiner::visitTokenFactor(SDNode *N) {
 583   // If N has two operands, where one has an input chain equal to the other,
 584   // the 'other' chain is redundant.
 585   if (N->getNumOperands() == 2) {
 586     if (getInputChainForNode(N->getOperand(0).Val) == N->getOperand(1))
 587       return N->getOperand(0);
 588     if (getInputChainForNode(N->getOperand(1).Val) == N->getOperand(0))
 589       return N->getOperand(1);
 590   }
 591
 592
 593   SmallVector<SDNode *, 8> TFs;   // List of token factors to visit.
 594   SmallVector<SDOperand, 8> Ops;  // Ops for replacing token factor.
 595   bool Changed = false;           // If we should replace this token factor.
 596
 597   // Start out with this token factor.
 598   TFs.push_back(N);
 599
 600   // Iterate through token factors.  The TFs grows when new token factors are
 601   // encountered.
 602   for (unsigned i = 0; i < TFs.size(); ++i) {
 603     SDNode *TF = TFs[i];
 604
 605     // Check each of the operands.
 606     for (unsigned i = 0, ie = TF->getNumOperands(); i != ie; ++i) {
 607       SDOperand Op = TF->getOperand(i);
 608
 609       switch (Op.getOpcode()) {
 610       case ISD::EntryToken:
 611         // Entry tokens don't need to be added to the list. They are
 612         // rededundant.
 613         Changed = true;
 614         break;
 615
 616       case ISD::TokenFactor:
 617         if ((CombinerAA || Op.hasOneUse()) &&
 618             std::find(TFs.begin(), TFs.end(), Op.Val) == TFs.end()) {
 619           // Queue up for processing.
 620           TFs.push_back(Op.Val);
 621           // Clean up in case the token factor is removed.
 622           AddToWorkList(Op.Val);
 623           Changed = true;
 624           break;
 625         }
 626         // Fall thru
 627
 628       default:
 629         // Only add if not there prior.
 630         if (std::find(Ops.begin(), Ops.end(), Op) == Ops.end())
 631           Ops.push_back(Op);
 632         break;
 633       }
 634     }
 635   }
 636
 637   SDOperand Result;
 638
 639   // If we've change things around then replace token factor.
 640   if (Changed) {
 641     if (Ops.size() == 0) {
 642       // The entry token is the only possible outcome.
 643       Result = DAG.getEntryNode();
 644     } else {
 645       // New and improved token factor.
 646       Result = DAG.getNode(ISD::TokenFactor, MVT::Other, &Ops[0], Ops.size());
 647     }
 648
 649     // Don't add users to work list.
 650     return CombineTo(N, Result, false);
 651   }
 652
 653   return Result;
 654 }
 655
 656 static
 657 SDOperand combineShlAddConstant(SDOperand N0, SDOperand N1, SelectionDAG &DAG) {
 658   MVT::ValueType VT = N0.getValueType();
 659   SDOperand N00 = N0.getOperand(0);
 660   SDOperand N01 = N0.getOperand(1);
 661   ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N01);
 662   if (N01C && N00.getOpcode() == ISD::ADD && N00.Val->hasOneUse() &&
 663       isa<ConstantSDNode>(N00.getOperand(1))) {
 664     N0 = DAG.getNode(ISD::ADD, VT,
 665                      DAG.getNode(ISD::SHL, VT, N00.getOperand(0), N01),
 666                      DAG.getNode(ISD::SHL, VT, N00.getOperand(1), N01));
 667     return DAG.getNode(ISD::ADD, VT, N0, N1);
 668   }
 669   return SDOperand();
 670 }
 671
 672 SDOperand DAGCombiner::visitADD(SDNode *N) {
 673   SDOperand N0 = N->getOperand(0);
 674   SDOperand N1 = N->getOperand(1);
 675   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 676   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 677   MVT::ValueType VT = N0.getValueType();
 678
 679   // fold (add c1, c2) -> c1+c2
 680   if (N0C && N1C)
 681     return DAG.getNode(ISD::ADD, VT, N0, N1);
 682   // canonicalize constant to RHS
 683   if (N0C && !N1C)
 684     return DAG.getNode(ISD::ADD, VT, N1, N0);
 685   // fold (add x, 0) -> x
 686   if (N1C && N1C->isNullValue())
 687     return N0;
 688   // fold ((c1-A)+c2) -> (c1+c2)-A
 689   if (N1C && N0.getOpcode() == ISD::SUB)
 690     if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getOperand(0)))
 691       return DAG.getNode(ISD::SUB, VT,
 692                          DAG.getConstant(N1C->getValue()+N0C->getValue(), VT),
 693                          N0.getOperand(1));
 694   // reassociate add
 695   SDOperand RADD = ReassociateOps(ISD::ADD, N0, N1);
 696   if (RADD.Val != 0)
 697     return RADD;
 698   // fold ((0-A) + B) -> B-A
 699   if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) &&
 700       cast<ConstantSDNode>(N0.getOperand(0))->isNullValue())
 701     return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1));
 702   // fold (A + (0-B)) -> A-B
 703   if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) &&
 704       cast<ConstantSDNode>(N1.getOperand(0))->isNullValue())
 705     return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1));
 706   // fold (A+(B-A)) -> B
 707   if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1))
 708     return N1.getOperand(0);
 709
 710   if (!MVT::isVector(VT) && SimplifyDemandedBits(SDOperand(N, 0)))
 711     return SDOperand(N, 0);
 712
 713   // fold (a+b) -> (a|b) iff a and b share no bits.
 714   if (MVT::isInteger(VT) && !MVT::isVector(VT)) {
 715     uint64_t LHSZero, LHSOne;
 716     uint64_t RHSZero, RHSOne;
 717     uint64_t Mask = MVT::getIntVTBitMask(VT);
 718     TLI.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne);
 719     if (LHSZero) {
 720       TLI.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne);
 721
 722       // If all possibly-set bits on the LHS are clear on the RHS, return an OR.
 723       // If all possibly-set bits on the RHS are clear on the LHS, return an OR.
 724       if ((RHSZero & (~LHSZero & Mask)) == (~LHSZero & Mask) ||
 725           (LHSZero & (~RHSZero & Mask)) == (~RHSZero & Mask))
 726         return DAG.getNode(ISD::OR, VT, N0, N1);
 727     }
 728   }
 729
 730   // fold (add (shl (add x, c1), c2), ) -> (add (add (shl x, c2), c1<<c2), )
 731   if (N0.getOpcode() == ISD::SHL && N0.Val->hasOneUse()) {
 732     SDOperand Result = combineShlAddConstant(N0, N1, DAG);
 733     if (Result.Val) return Result;
 734   }
 735   if (N1.getOpcode() == ISD::SHL && N1.Val->hasOneUse()) {
 736     SDOperand Result = combineShlAddConstant(N1, N0, DAG);
 737     if (Result.Val) return Result;
 738   }
 739
 740   return SDOperand();
 741 }
 742
 743 SDOperand DAGCombiner::visitSUB(SDNode *N) {
 744   SDOperand N0 = N->getOperand(0);
 745   SDOperand N1 = N->getOperand(1);
 746   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
 747   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 748   MVT::ValueType VT = N0.getValueType();
 749
 750   // fold (sub x, x) -> 0
 751   if (N0 == N1)
 752     return DAG.getConstant(0, N->getValueType(0));
 753   // fold (sub c1, c2) -> c1-c2
 754   if (N0C && N1C)
 755     return DAG.getNode(ISD::SUB, VT, N0, N1);
 756   // fold (sub x, c) -> (add x, -c)
 757   if (N1C)
 758     return DAG.getNode(ISD::ADD, VT, N0, DAG.getConstant(-N1C->getValue(), VT));
 759   // fold (A+B)-A -> B
 760   if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1)
 761     return N0.getOperand(1);
 762   // fold (A+B)-B -> A
 763   if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1)
 764     return N0.getOperand(0);
 765   return SDOperand();
 766 }
 767
 768 SDOperand DAGCombiner::visitMUL(SDNode *N) {
 769   SDOperand N0 = N->getOperand(0);
 770   SDOperand N1 = N->getOperand(1);
 771   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 772   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 773   MVT::ValueType VT = N0.getValueType();
 774
 775   // fold (mul c1, c2) -> c1*c2
 776   if (N0C && N1C)
 777     return DAG.getNode(ISD::MUL, VT, N0, N1);
 778   // canonicalize constant to RHS
 779   if (N0C && !N1C)
 780     return DAG.getNode(ISD::MUL, VT, N1, N0);
 781   // fold (mul x, 0) -> 0
 782   if (N1C && N1C->isNullValue())
 783     return N1;
 784   // fold (mul x, -1) -> 0-x
 785   if (N1C && N1C->isAllOnesValue())
 786     return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0);
 787   // fold (mul x, (1 << c)) -> x << c
 788   if (N1C && isPowerOf2_64(N1C->getValue()))
 789     return DAG.getNode(ISD::SHL, VT, N0,
 790                        DAG.getConstant(Log2_64(N1C->getValue()),
 791                                        TLI.getShiftAmountTy()));
 792   // fold (mul x, -(1 << c)) -> -(x << c) or (-x) << c
 793   if (N1C && isPowerOf2_64(-N1C->getSignExtended())) {
 794     // FIXME: If the input is something that is easily negated (e.g. a
 795     // single-use add), we should put the negate there.
 796     return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT),
 797                        DAG.getNode(ISD::SHL, VT, N0,
 798                             DAG.getConstant(Log2_64(-N1C->getSignExtended()),
 799                                             TLI.getShiftAmountTy())));
 800   }
 801
 802   // (mul (shl X, c1), c2) -> (mul X, c2 << c1)
 803   if (N1C && N0.getOpcode() == ISD::SHL &&
 804       isa<ConstantSDNode>(N0.getOperand(1))) {
 805     SDOperand C3 = DAG.getNode(ISD::SHL, VT, N1, N0.getOperand(1));
 806     AddToWorkList(C3.Val);
 807     return DAG.getNode(ISD::MUL, VT, N0.getOperand(0), C3);
 808   }
 809
 810   // Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one
 811   // use.
 812   {
 813     SDOperand Sh(0,0), Y(0,0);
 814     // Check for both (mul (shl X, C), Y)  and  (mul Y, (shl X, C)).
 815     if (N0.getOpcode() == ISD::SHL && isa<ConstantSDNode>(N0.getOperand(1)) &&
 816         N0.Val->hasOneUse()) {
 817       Sh = N0; Y = N1;
 818     } else if (N1.getOpcode() == ISD::SHL &&
 819                isa<ConstantSDNode>(N1.getOperand(1)) && N1.Val->hasOneUse()) {
 820       Sh = N1; Y = N0;
 821     }
 822     if (Sh.Val) {
 823       SDOperand Mul = DAG.getNode(ISD::MUL, VT, Sh.getOperand(0), Y);
 824       return DAG.getNode(ISD::SHL, VT, Mul, Sh.getOperand(1));
 825     }
 826   }
 827   // fold (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2)
 828   if (N1C && N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse() &&
 829       isa<ConstantSDNode>(N0.getOperand(1))) {
 830     return DAG.getNode(ISD::ADD, VT,
 831                        DAG.getNode(ISD::MUL, VT, N0.getOperand(0), N1),
 832                        DAG.getNode(ISD::MUL, VT, N0.getOperand(1), N1));
 833   }
 834
 835   // reassociate mul
 836   SDOperand RMUL = ReassociateOps(ISD::MUL, N0, N1);
 837   if (RMUL.Val != 0)
 838     return RMUL;
 839   return SDOperand();
 840 }
 841
 842 SDOperand DAGCombiner::visitSDIV(SDNode *N) {
 843   SDOperand N0 = N->getOperand(0);
 844   SDOperand N1 = N->getOperand(1);
 845   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
 846   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 847   MVT::ValueType VT = N->getValueType(0);
 848
 849   // fold (sdiv c1, c2) -> c1/c2
 850   if (N0C && N1C && !N1C->isNullValue())
 851     return DAG.getNode(ISD::SDIV, VT, N0, N1);
 852   // fold (sdiv X, 1) -> X
 853   if (N1C && N1C->getSignExtended() == 1LL)
 854     return N0;
 855   // fold (sdiv X, -1) -> 0-X
 856   if (N1C && N1C->isAllOnesValue())
 857     return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0);
 858   // If we know the sign bits of both operands are zero, strength reduce to a
 859   // udiv instead.  Handles (X&15) /s 4 -> X&15 >> 2
 860   uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1);
 861   if (TLI.MaskedValueIsZero(N1, SignBit) &&
 862       TLI.MaskedValueIsZero(N0, SignBit))
 863     return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1);
 864   // fold (sdiv X, pow2) -> simple ops after legalize
 865   if (N1C && N1C->getValue() && !TLI.isIntDivCheap() &&
 866       (isPowerOf2_64(N1C->getSignExtended()) ||
 867        isPowerOf2_64(-N1C->getSignExtended()))) {
 868     // If dividing by powers of two is cheap, then don't perform the following
 869     // fold.
 870     if (TLI.isPow2DivCheap())
 871       return SDOperand();
 872     int64_t pow2 = N1C->getSignExtended();
 873     int64_t abs2 = pow2 > 0 ? pow2 : -pow2;
 874     unsigned lg2 = Log2_64(abs2);
 875     // Splat the sign bit into the register
 876     SDOperand SGN = DAG.getNode(ISD::SRA, VT, N0,
 877                                 DAG.getConstant(MVT::getSizeInBits(VT)-1,
 878                                                 TLI.getShiftAmountTy()));
 879     AddToWorkList(SGN.Val);
 880     // Add (N0 < 0) ? abs2 - 1 : 0;
 881     SDOperand SRL = DAG.getNode(ISD::SRL, VT, SGN,
 882                                 DAG.getConstant(MVT::getSizeInBits(VT)-lg2,
 883                                                 TLI.getShiftAmountTy()));
 884     SDOperand ADD = DAG.getNode(ISD::ADD, VT, N0, SRL);
 885     AddToWorkList(SRL.Val);
 886     AddToWorkList(ADD.Val);    // Divide by pow2
 887     SDOperand SRA = DAG.getNode(ISD::SRA, VT, ADD,
 888                                 DAG.getConstant(lg2, TLI.getShiftAmountTy()));
 889     // If we're dividing by a positive value, we're done.  Otherwise, we must
 890     // negate the result.
 891     if (pow2 > 0)
 892       return SRA;
 893     AddToWorkList(SRA.Val);
 894     return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), SRA);
 895   }
 896   // if integer divide is expensive and we satisfy the requirements, emit an
 897   // alternate sequence.
 898   if (N1C && (N1C->getSignExtended() < -1 || N1C->getSignExtended() > 1) &&
 899       !TLI.isIntDivCheap()) {
 900     SDOperand Op = BuildSDIV(N);
 901     if (Op.Val) return Op;
 902   }
 903   return SDOperand();
 904 }
 905
 906 SDOperand DAGCombiner::visitUDIV(SDNode *N) {
 907   SDOperand N0 = N->getOperand(0);
 908   SDOperand N1 = N->getOperand(1);
 909   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
 910   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 911   MVT::ValueType VT = N->getValueType(0);
 912
 913   // fold (udiv c1, c2) -> c1/c2
 914   if (N0C && N1C && !N1C->isNullValue())
 915     return DAG.getNode(ISD::UDIV, VT, N0, N1);
 916   // fold (udiv x, (1 << c)) -> x >>u c
 917   if (N1C && isPowerOf2_64(N1C->getValue()))
 918     return DAG.getNode(ISD::SRL, VT, N0,
 919                        DAG.getConstant(Log2_64(N1C->getValue()),
 920                                        TLI.getShiftAmountTy()));
 921   // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2
 922   if (N1.getOpcode() == ISD::SHL) {
 923     if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) {
 924       if (isPowerOf2_64(SHC->getValue())) {
 925         MVT::ValueType ADDVT = N1.getOperand(1).getValueType();
 926         SDOperand Add = DAG.getNode(ISD::ADD, ADDVT, N1.getOperand(1),
 927                                     DAG.getConstant(Log2_64(SHC->getValue()),
 928                                                     ADDVT));
 929         AddToWorkList(Add.Val);
 930         return DAG.getNode(ISD::SRL, VT, N0, Add);
 931       }
 932     }
 933   }
 934   // fold (udiv x, c) -> alternate
 935   if (N1C && N1C->getValue() && !TLI.isIntDivCheap()) {
 936     SDOperand Op = BuildUDIV(N);
 937     if (Op.Val) return Op;
 938   }
 939   return SDOperand();
 940 }
 941
 942 SDOperand DAGCombiner::visitSREM(SDNode *N) {
 943   SDOperand N0 = N->getOperand(0);
 944   SDOperand N1 = N->getOperand(1);
 945   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 946   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 947   MVT::ValueType VT = N->getValueType(0);
 948
 949   // fold (srem c1, c2) -> c1%c2
 950   if (N0C && N1C && !N1C->isNullValue())
 951     return DAG.getNode(ISD::SREM, VT, N0, N1);
 952   // If we know the sign bits of both operands are zero, strength reduce to a
 953   // urem instead.  Handles (X & 0x0FFFFFFF) %s 16 -> X&15
 954   uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1);
 955   if (TLI.MaskedValueIsZero(N1, SignBit) &&
 956       TLI.MaskedValueIsZero(N0, SignBit))
 957     return DAG.getNode(ISD::UREM, VT, N0, N1);
 958
 959   // Unconditionally lower X%C -> X-X/C*C.  This allows the X/C logic to hack on
 960   // the remainder operation.
 961   if (N1C && !N1C->isNullValue()) {
 962     SDOperand Div = DAG.getNode(ISD::SDIV, VT, N0, N1);
 963     SDOperand Mul = DAG.getNode(ISD::MUL, VT, Div, N1);
 964     SDOperand Sub = DAG.getNode(ISD::SUB, VT, N0, Mul);
 965     AddToWorkList(Div.Val);
 966     AddToWorkList(Mul.Val);
 967     return Sub;
 968   }
 969
 970   return SDOperand();
 971 }
 972
 973 SDOperand DAGCombiner::visitUREM(SDNode *N) {
 974   SDOperand N0 = N->getOperand(0);
 975   SDOperand N1 = N->getOperand(1);
 976   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 977   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 978   MVT::ValueType VT = N->getValueType(0);
 979
 980   // fold (urem c1, c2) -> c1%c2
 981   if (N0C && N1C && !N1C->isNullValue())
 982     return DAG.getNode(ISD::UREM, VT, N0, N1);
 983   // fold (urem x, pow2) -> (and x, pow2-1)
 984   if (N1C && !N1C->isNullValue() && isPowerOf2_64(N1C->getValue()))
 985     return DAG.getNode(ISD::AND, VT, N0, DAG.getConstant(N1C->getValue()-1,VT));
 986   // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1))
 987   if (N1.getOpcode() == ISD::SHL) {
 988     if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) {
 989       if (isPowerOf2_64(SHC->getValue())) {
 990         SDOperand Add = DAG.getNode(ISD::ADD, VT, N1,DAG.getConstant(~0ULL,VT));
 991         AddToWorkList(Add.Val);
 992         return DAG.getNode(ISD::AND, VT, N0, Add);
 993       }
 994     }
 995   }
 996
 997   // Unconditionally lower X%C -> X-X/C*C.  This allows the X/C logic to hack on
 998   // the remainder operation.
 999   if (N1C && !N1C->isNullValue()) {
1000     SDOperand Div = DAG.getNode(ISD::UDIV, VT, N0, N1);
1001     SDOperand Mul = DAG.getNode(ISD::MUL, VT, Div, N1);
1002     SDOperand Sub = DAG.getNode(ISD::SUB, VT, N0, Mul);
1003     AddToWorkList(Div.Val);
1004     AddToWorkList(Mul.Val);
1005     return Sub;
1006   }
1007
1008   return SDOperand();
1009 }
1010
1011 SDOperand DAGCombiner::visitMULHS(SDNode *N) {
1012   SDOperand N0 = N->getOperand(0);
1013   SDOperand N1 = N->getOperand(1);
1014   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1015
1016   // fold (mulhs x, 0) -> 0
1017   if (N1C && N1C->isNullValue())
1018     return N1;
1019   // fold (mulhs x, 1) -> (sra x, size(x)-1)
1020   if (N1C && N1C->getValue() == 1)
1021     return DAG.getNode(ISD::SRA, N0.getValueType(), N0,
1022                        DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1,
1023                                        TLI.getShiftAmountTy()));
1024   return SDOperand();
1025 }
1026
1027 SDOperand DAGCombiner::visitMULHU(SDNode *N) {
1028   SDOperand N0 = N->getOperand(0);
1029   SDOperand N1 = N->getOperand(1);
1030   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1031
1032   // fold (mulhu x, 0) -> 0
1033   if (N1C && N1C->isNullValue())
1034     return N1;
1035   // fold (mulhu x, 1) -> 0
1036   if (N1C && N1C->getValue() == 1)
1037     return DAG.getConstant(0, N0.getValueType());
1038   return SDOperand();
1039 }
1040
1041 /// SimplifyBinOpWithSameOpcodeHands - If this is a binary operator with
1042 /// two operands of the same opcode, try to simplify it.
1043 SDOperand DAGCombiner::SimplifyBinOpWithSameOpcodeHands(SDNode *N) {
1044   SDOperand N0 = N->getOperand(0), N1 = N->getOperand(1);
1045   MVT::ValueType VT = N0.getValueType();
1046   assert(N0.getOpcode() == N1.getOpcode() && "Bad input!");
1047
1048   // For each of OP in AND/OR/XOR:
1049   // fold (OP (zext x), (zext y)) -> (zext (OP x, y))
1050   // fold (OP (sext x), (sext y)) -> (sext (OP x, y))
1051   // fold (OP (aext x), (aext y)) -> (aext (OP x, y))
1052   // fold (OP (trunc x), (trunc y)) -> (trunc (OP x, y))
1053   if ((N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND||
1054        N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::TRUNCATE) &&
1055       N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
1056     SDOperand ORNode = DAG.getNode(N->getOpcode(),
1057                                    N0.getOperand(0).getValueType(),
1058                                    N0.getOperand(0), N1.getOperand(0));
1059     AddToWorkList(ORNode.Val);
1060     return DAG.getNode(N0.getOpcode(), VT, ORNode);
1061   }
1062
1063   // For each of OP in SHL/SRL/SRA/AND...
1064   //   fold (and (OP x, z), (OP y, z)) -> (OP (and x, y), z)
1065   //   fold (or  (OP x, z), (OP y, z)) -> (OP (or  x, y), z)
1066   //   fold (xor (OP x, z), (OP y, z)) -> (OP (xor x, y), z)
1067   if ((N0.getOpcode() == ISD::SHL || N0.getOpcode() == ISD::SRL ||
1068        N0.getOpcode() == ISD::SRA || N0.getOpcode() == ISD::AND) &&
1069       N0.getOperand(1) == N1.getOperand(1)) {
1070     SDOperand ORNode = DAG.getNode(N->getOpcode(),
1071                                    N0.getOperand(0).getValueType(),
1072                                    N0.getOperand(0), N1.getOperand(0));
1073     AddToWorkList(ORNode.Val);
1074     return DAG.getNode(N0.getOpcode(), VT, ORNode, N0.getOperand(1));
1075   }
1076
1077   return SDOperand();
1078 }
1079
1080 SDOperand DAGCombiner::visitAND(SDNode *N) {
1081   SDOperand N0 = N->getOperand(0);
1082   SDOperand N1 = N->getOperand(1);
1083   SDOperand LL, LR, RL, RR, CC0, CC1;
1084   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1085   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1086   MVT::ValueType VT = N1.getValueType();
1087
1088   // fold (and c1, c2) -> c1&c2
1089   if (N0C && N1C)
1090     return DAG.getNode(ISD::AND, VT, N0, N1);
1091   // canonicalize constant to RHS
1092   if (N0C && !N1C)
1093     return DAG.getNode(ISD::AND, VT, N1, N0);
1094   // fold (and x, -1) -> x
1095   if (N1C && N1C->isAllOnesValue())
1096     return N0;
1097   // if (and x, c) is known to be zero, return 0
1098   if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
1099     return DAG.getConstant(0, VT);
1100   // reassociate and
1101   SDOperand RAND = ReassociateOps(ISD::AND, N0, N1);
1102   if (RAND.Val != 0)
1103     return RAND;
1104   // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF
1105   if (N1C && N0.getOpcode() == ISD::OR)
1106     if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
1107       if ((ORI->getValue() & N1C->getValue()) == N1C->getValue())
1108         return N1;
1109   // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits.
1110   if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) {
1111     unsigned InMask = MVT::getIntVTBitMask(N0.getOperand(0).getValueType());
1112     if (TLI.MaskedValueIsZero(N0.getOperand(0),
1113                               ~N1C->getValue() & InMask)) {
1114       SDOperand Zext = DAG.getNode(ISD::ZERO_EXTEND, N0.getValueType(),
1115                                    N0.getOperand(0));
1116
1117       // Replace uses of the AND with uses of the Zero extend node.
1118       CombineTo(N, Zext);
1119
1120       // We actually want to replace all uses of the any_extend with the
1121       // zero_extend, to avoid duplicating things.  This will later cause this
1122       // AND to be folded.
1123       CombineTo(N0.Val, Zext);
1124       return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
1125     }
1126   }
1127   // fold (and (setcc x), (setcc y)) -> (setcc (and x, y))
1128   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
1129     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
1130     ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
1131
1132     if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
1133         MVT::isInteger(LL.getValueType())) {
1134       // fold (X == 0) & (Y == 0) -> (X|Y == 0)
1135       if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) {
1136         SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
1137         AddToWorkList(ORNode.Val);
1138         return DAG.getSetCC(VT, ORNode, LR, Op1);
1139       }
1140       // fold (X == -1) & (Y == -1) -> (X&Y == -1)
1141       if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) {
1142         SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL);
1143         AddToWorkList(ANDNode.Val);
1144         return DAG.getSetCC(VT, ANDNode, LR, Op1);
1145       }
1146       // fold (X >  -1) & (Y >  -1) -> (X|Y > -1)
1147       if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) {
1148         SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
1149         AddToWorkList(ORNode.Val);
1150         return DAG.getSetCC(VT, ORNode, LR, Op1);
1151       }
1152     }
1153     // canonicalize equivalent to ll == rl
1154     if (LL == RR && LR == RL) {
1155       Op1 = ISD::getSetCCSwappedOperands(Op1);
1156       std::swap(RL, RR);
1157     }
1158     if (LL == RL && LR == RR) {
1159       bool isInteger = MVT::isInteger(LL.getValueType());
1160       ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger);
1161       if (Result != ISD::SETCC_INVALID)
1162         return DAG.getSetCC(N0.getValueType(), LL, LR, Result);
1163     }
1164   }
1165
1166   // Simplify: and (op x...), (op y...)  -> (op (and x, y))
1167   if (N0.getOpcode() == N1.getOpcode()) {
1168     SDOperand Tmp = SimplifyBinOpWithSameOpcodeHands(N);
1169     if (Tmp.Val) return Tmp;
1170   }
1171
1172   // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1)
1173   // fold (and (sra)) -> (and (srl)) when possible.
1174   if (!MVT::isVector(VT) &&
1175       SimplifyDemandedBits(SDOperand(N, 0)))
1176     return SDOperand(N, 0);
1177   // fold (zext_inreg (extload x)) -> (zextload x)
1178   if (ISD::isEXTLoad(N0.Val)) {
1179     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
1180     MVT::ValueType EVT = LN0->getLoadedVT();
1181     // If we zero all the possible extended bits, then we can turn this into
1182     // a zextload if we are running before legalize or the operation is legal.
1183     if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) &&
1184         (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) {
1185       SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
1186                                          LN0->getBasePtr(), LN0->getSrcValue(),
1187                                          LN0->getSrcValueOffset(), EVT);
1188       AddToWorkList(N);
1189       CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
1190       return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
1191     }
1192   }
1193   // fold (zext_inreg (sextload x)) -> (zextload x) iff load has one use
1194   if (ISD::isSEXTLoad(N0.Val) && N0.hasOneUse()) {
1195     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
1196     MVT::ValueType EVT = LN0->getLoadedVT();
1197     // If we zero all the possible extended bits, then we can turn this into
1198     // a zextload if we are running before legalize or the operation is legal.
1199     if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) &&
1200         (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) {
1201       SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
1202                                          LN0->getBasePtr(), LN0->getSrcValue(),
1203                                          LN0->getSrcValueOffset(), EVT);
1204       AddToWorkList(N);
1205       CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
1206       return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
1207     }
1208   }
1209
1210   // fold (and (load x), 255) -> (zextload x, i8)
1211   // fold (and (extload x, i16), 255) -> (zextload x, i8)
1212   if (N1C && N0.getOpcode() == ISD::LOAD) {
1213     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
1214     if (LN0->getExtensionType() != ISD::SEXTLOAD &&
1215         N0.hasOneUse()) {
1216       MVT::ValueType EVT, LoadedVT;
1217       if (N1C->getValue() == 255)
1218         EVT = MVT::i8;
1219       else if (N1C->getValue() == 65535)
1220         EVT = MVT::i16;
1221       else if (N1C->getValue() == ~0U)
1222         EVT = MVT::i32;
1223       else
1224         EVT = MVT::Other;
1225
1226       LoadedVT = LN0->getLoadedVT();
1227       if (EVT != MVT::Other && LoadedVT > EVT &&
1228           (!AfterLegalize || TLI.isLoadXLegal(ISD::ZEXTLOAD, EVT))) {
1229         MVT::ValueType PtrType = N0.getOperand(1).getValueType();
1230         // For big endian targets, we need to add an offset to the pointer to
1231         // load the correct bytes.  For little endian systems, we merely need to
1232         // read fewer bytes from the same pointer.
1233         unsigned PtrOff =
1234           (MVT::getSizeInBits(LoadedVT) - MVT::getSizeInBits(EVT)) / 8;
1235         SDOperand NewPtr = LN0->getBasePtr();
1236         if (!TLI.isLittleEndian())
1237           NewPtr = DAG.getNode(ISD::ADD, PtrType, NewPtr,
1238                                DAG.getConstant(PtrOff, PtrType));
1239         AddToWorkList(NewPtr.Val);
1240         SDOperand Load =
1241           DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(), NewPtr,
1242                          LN0->getSrcValue(), LN0->getSrcValueOffset(), EVT);
1243         AddToWorkList(N);
1244         CombineTo(N0.Val, Load, Load.getValue(1));
1245         return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
1246       }
1247     }
1248   }
1249
1250   return SDOperand();
1251 }
1252
1253 SDOperand DAGCombiner::visitOR(SDNode *N) {
1254   SDOperand N0 = N->getOperand(0);
1255   SDOperand N1 = N->getOperand(1);
1256   SDOperand LL, LR, RL, RR, CC0, CC1;
1257   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1258   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1259   MVT::ValueType VT = N1.getValueType();
1260   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
1261
1262   // fold (or c1, c2) -> c1|c2
1263   if (N0C && N1C)
1264     return DAG.getNode(ISD::OR, VT, N0, N1);
1265   // canonicalize constant to RHS
1266   if (N0C && !N1C)
1267     return DAG.getNode(ISD::OR, VT, N1, N0);
1268   // fold (or x, 0) -> x
1269   if (N1C && N1C->isNullValue())
1270     return N0;
1271   // fold (or x, -1) -> -1
1272   if (N1C && N1C->isAllOnesValue())
1273     return N1;
1274   // fold (or x, c) -> c iff (x & ~c) == 0
1275   if (N1C &&
1276       TLI.MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits))))
1277     return N1;
1278   // reassociate or
1279   SDOperand ROR = ReassociateOps(ISD::OR, N0, N1);
1280   if (ROR.Val != 0)
1281     return ROR;
1282   // Canonicalize (or (and X, c1), c2) -> (and (or X, c2), c1|c2)
1283   if (N1C && N0.getOpcode() == ISD::AND && N0.Val->hasOneUse() &&
1284              isa<ConstantSDNode>(N0.getOperand(1))) {
1285     ConstantSDNode *C1 = cast<ConstantSDNode>(N0.getOperand(1));
1286     return DAG.getNode(ISD::AND, VT, DAG.getNode(ISD::OR, VT, N0.getOperand(0),
1287                                                  N1),
1288                        DAG.getConstant(N1C->getValue() | C1->getValue(), VT));
1289   }
1290   // fold (or (setcc x), (setcc y)) -> (setcc (or x, y))
1291   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
1292     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
1293     ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
1294
1295     if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
1296         MVT::isInteger(LL.getValueType())) {
1297       // fold (X != 0) | (Y != 0) -> (X|Y != 0)
1298       // fold (X <  0) | (Y <  0) -> (X|Y < 0)
1299       if (cast<ConstantSDNode>(LR)->getValue() == 0 &&
1300           (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) {
1301         SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
1302         AddToWorkList(ORNode.Val);
1303         return DAG.getSetCC(VT, ORNode, LR, Op1);
1304       }
1305       // fold (X != -1) | (Y != -1) -> (X&Y != -1)
1306       // fold (X >  -1) | (Y >  -1) -> (X&Y >  -1)
1307       if (cast<ConstantSDNode>(LR)->isAllOnesValue() &&
1308           (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) {
1309         SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL);
1310         AddToWorkList(ANDNode.Val);
1311         return DAG.getSetCC(VT, ANDNode, LR, Op1);
1312       }
1313     }
1314     // canonicalize equivalent to ll == rl
1315     if (LL == RR && LR == RL) {
1316       Op1 = ISD::getSetCCSwappedOperands(Op1);
1317       std::swap(RL, RR);
1318     }
1319     if (LL == RL && LR == RR) {
1320       bool isInteger = MVT::isInteger(LL.getValueType());
1321       ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger);
1322       if (Result != ISD::SETCC_INVALID)
1323         return DAG.getSetCC(N0.getValueType(), LL, LR, Result);
1324     }
1325   }
1326
1327   // Simplify: or (op x...), (op y...)  -> (op (or x, y))
1328   if (N0.getOpcode() == N1.getOpcode()) {
1329     SDOperand Tmp = SimplifyBinOpWithSameOpcodeHands(N);
1330     if (Tmp.Val) return Tmp;
1331   }
1332
1333   // (X & C1) | (Y & C2)  -> (X|Y) & C3  if possible.
1334   if (N0.getOpcode() == ISD::AND &&
1335       N1.getOpcode() == ISD::AND &&
1336       N0.getOperand(1).getOpcode() == ISD::Constant &&
1337       N1.getOperand(1).getOpcode() == ISD::Constant &&
1338       // Don't increase # computations.
1339       (N0.Val->hasOneUse() || N1.Val->hasOneUse())) {
1340     // We can only do this xform if we know that bits from X that are set in C2
1341     // but not in C1 are already zero.  Likewise for Y.
1342     uint64_t LHSMask = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
1343     uint64_t RHSMask = cast<ConstantSDNode>(N1.getOperand(1))->getValue();
1344
1345     if (TLI.MaskedValueIsZero(N0.getOperand(0), RHSMask&~LHSMask) &&
1346         TLI.MaskedValueIsZero(N1.getOperand(0), LHSMask&~RHSMask)) {
1347       SDOperand X =DAG.getNode(ISD::OR, VT, N0.getOperand(0), N1.getOperand(0));
1348       return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(LHSMask|RHSMask, VT));
1349     }
1350   }
1351
1352
1353   // See if this is some rotate idiom.
1354   if (SDNode *Rot = MatchRotate(N0, N1))
1355     return SDOperand(Rot, 0);
1356
1357   return SDOperand();
1358 }
1359
1360
1361 /// MatchRotateHalf - Match "(X shl/srl V1) & V2" where V2 may not be present.
1362 static bool MatchRotateHalf(SDOperand Op, SDOperand &Shift, SDOperand &Mask) {
1363   if (Op.getOpcode() == ISD::AND) {
1364     if (isa<ConstantSDNode>(Op.getOperand(1))) {
1365       Mask = Op.getOperand(1);
1366       Op = Op.getOperand(0);
1367     } else {
1368       return false;
1369     }
1370   }
1371
1372   if (Op.getOpcode() == ISD::SRL || Op.getOpcode() == ISD::SHL) {
1373     Shift = Op;
1374     return true;
1375   }
1376   return false;
1377 }
1378
1379
1380 // MatchRotate - Handle an 'or' of two operands.  If this is one of the many
1381 // idioms for rotate, and if the target supports rotation instructions, generate
1382 // a rot[lr].
1383 SDNode *DAGCombiner::MatchRotate(SDOperand LHS, SDOperand RHS) {
1384   // Must be a legal type.  Expanded an promoted things won't work with rotates.
1385   MVT::ValueType VT = LHS.getValueType();
1386   if (!TLI.isTypeLegal(VT)) return 0;
1387
1388   // The target must have at least one rotate flavor.
1389   bool HasROTL = TLI.isOperationLegal(ISD::ROTL, VT);
1390   bool HasROTR = TLI.isOperationLegal(ISD::ROTR, VT);
1391   if (!HasROTL && !HasROTR) return 0;
1392
1393   // Match "(X shl/srl V1) & V2" where V2 may not be present.
1394   SDOperand LHSShift;   // The shift.
1395   SDOperand LHSMask;    // AND value if any.
1396   if (!MatchRotateHalf(LHS, LHSShift, LHSMask))
1397     return 0; // Not part of a rotate.
1398
1399   SDOperand RHSShift;   // The shift.
1400   SDOperand RHSMask;    // AND value if any.
1401   if (!MatchRotateHalf(RHS, RHSShift, RHSMask))
1402     return 0; // Not part of a rotate.
1403
1404   if (LHSShift.getOperand(0) != RHSShift.getOperand(0))
1405     return 0;   // Not shifting the same value.
1406
1407   if (LHSShift.getOpcode() == RHSShift.getOpcode())
1408     return 0;   // Shifts must disagree.
1409
1410   // Canonicalize shl to left side in a shl/srl pair.
1411   if (RHSShift.getOpcode() == ISD::SHL) {
1412     std::swap(LHS, RHS);
1413     std::swap(LHSShift, RHSShift);
1414     std::swap(LHSMask , RHSMask );
1415   }
1416
1417   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
1418
1419   // fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1)
1420   // fold (or (shl x, C1), (srl x, C2)) -> (rotr x, C2)
1421   if (LHSShift.getOperand(1).getOpcode() == ISD::Constant &&
1422       RHSShift.getOperand(1).getOpcode() == ISD::Constant) {
1423     uint64_t LShVal = cast<ConstantSDNode>(LHSShift.getOperand(1))->getValue();
1424     uint64_t RShVal = cast<ConstantSDNode>(RHSShift.getOperand(1))->getValue();
1425     if ((LShVal + RShVal) != OpSizeInBits)
1426       return 0;
1427
1428     SDOperand Rot;
1429     if (HasROTL)
1430       Rot = DAG.getNode(ISD::ROTL, VT, LHSShift.getOperand(0),
1431                         LHSShift.getOperand(1));
1432     else
1433       Rot = DAG.getNode(ISD::ROTR, VT, LHSShift.getOperand(0),
1434                         RHSShift.getOperand(1));
1435
1436     // If there is an AND of either shifted operand, apply it to the result.
1437     if (LHSMask.Val || RHSMask.Val) {
1438       uint64_t Mask = MVT::getIntVTBitMask(VT);
1439
1440       if (LHSMask.Val) {
1441         uint64_t RHSBits = (1ULL << LShVal)-1;
1442         Mask &= cast<ConstantSDNode>(LHSMask)->getValue() | RHSBits;
1443       }
1444       if (RHSMask.Val) {
1445         uint64_t LHSBits = ~((1ULL << (OpSizeInBits-RShVal))-1);
1446         Mask &= cast<ConstantSDNode>(RHSMask)->getValue() | LHSBits;
1447       }
1448
1449       Rot = DAG.getNode(ISD::AND, VT, Rot, DAG.getConstant(Mask, VT));
1450     }
1451
1452     return Rot.Val;
1453   }
1454
1455   // If there is a mask here, and we have a variable shift, we can't be sure
1456   // that we're masking out the right stuff.
1457   if (LHSMask.Val || RHSMask.Val)
1458     return 0;
1459
1460   // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotl x, y)
1461   // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotr x, (sub 32, y))
1462   if (RHSShift.getOperand(1).getOpcode() == ISD::SUB &&
1463       LHSShift.getOperand(1) == RHSShift.getOperand(1).getOperand(1)) {
1464     if (ConstantSDNode *SUBC =
1465           dyn_cast<ConstantSDNode>(RHSShift.getOperand(1).getOperand(0))) {
1466       if (SUBC->getValue() == OpSizeInBits)
1467         if (HasROTL)
1468           return DAG.getNode(ISD::ROTL, VT, LHSShift.getOperand(0),
1469                              LHSShift.getOperand(1)).Val;
1470         else
1471           return DAG.getNode(ISD::ROTR, VT, LHSShift.getOperand(0),
1472                              LHSShift.getOperand(1)).Val;
1473     }
1474   }
1475
1476   // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotr x, y)
1477   // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotl x, (sub 32, y))
1478   if (LHSShift.getOperand(1).getOpcode() == ISD::SUB &&
1479       RHSShift.getOperand(1) == LHSShift.getOperand(1).getOperand(1)) {
1480     if (ConstantSDNode *SUBC =
1481           dyn_cast<ConstantSDNode>(LHSShift.getOperand(1).getOperand(0))) {
1482       if (SUBC->getValue() == OpSizeInBits)
1483         if (HasROTL)
1484           return DAG.getNode(ISD::ROTL, VT, LHSShift.getOperand(0),
1485                              LHSShift.getOperand(1)).Val;
1486         else
1487           return DAG.getNode(ISD::ROTR, VT, LHSShift.getOperand(0),
1488                              RHSShift.getOperand(1)).Val;
1489     }
1490   }
1491
1492   return 0;
1493 }
1494
1495
1496 SDOperand DAGCombiner::visitXOR(SDNode *N) {
1497   SDOperand N0 = N->getOperand(0);
1498   SDOperand N1 = N->getOperand(1);
1499   SDOperand LHS, RHS, CC;
1500   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1501   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1502   MVT::ValueType VT = N0.getValueType();
1503
1504   // fold (xor c1, c2) -> c1^c2
1505   if (N0C && N1C)
1506     return DAG.getNode(ISD::XOR, VT, N0, N1);
1507   // canonicalize constant to RHS
1508   if (N0C && !N1C)
1509     return DAG.getNode(ISD::XOR, VT, N1, N0);
1510   // fold (xor x, 0) -> x
1511   if (N1C && N1C->isNullValue())
1512     return N0;
1513   // reassociate xor
1514   SDOperand RXOR = ReassociateOps(ISD::XOR, N0, N1);
1515   if (RXOR.Val != 0)
1516     return RXOR;
1517   // fold !(x cc y) -> (x !cc y)
1518   if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) {
1519     bool isInt = MVT::isInteger(LHS.getValueType());
1520     ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(),
1521                                                isInt);
1522     if (N0.getOpcode() == ISD::SETCC)
1523       return DAG.getSetCC(VT, LHS, RHS, NotCC);
1524     if (N0.getOpcode() == ISD::SELECT_CC)
1525       return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC);
1526     assert(0 && "Unhandled SetCC Equivalent!");
1527     abort();
1528   }
1529   // fold !(x or y) -> (!x and !y) iff x or y are setcc
1530   if (N1C && N1C->getValue() == 1 && VT == MVT::i1 &&
1531       (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) {
1532     SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
1533     if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) {
1534       unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND;
1535       LHS = DAG.getNode(ISD::XOR, VT, LHS, N1);  // RHS = ~LHS
1536       RHS = DAG.getNode(ISD::XOR, VT, RHS, N1);  // RHS = ~RHS
1537       AddToWorkList(LHS.Val); AddToWorkList(RHS.Val);
1538       return DAG.getNode(NewOpcode, VT, LHS, RHS);
1539     }
1540   }
1541   // fold !(x or y) -> (!x and !y) iff x or y are constants
1542   if (N1C && N1C->isAllOnesValue() &&
1543       (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) {
1544     SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
1545     if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) {
1546       unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND;
1547       LHS = DAG.getNode(ISD::XOR, VT, LHS, N1);  // RHS = ~LHS
1548       RHS = DAG.getNode(ISD::XOR, VT, RHS, N1);  // RHS = ~RHS
1549       AddToWorkList(LHS.Val); AddToWorkList(RHS.Val);
1550       return DAG.getNode(NewOpcode, VT, LHS, RHS);
1551     }
1552   }
1553   // fold (xor (xor x, c1), c2) -> (xor x, c1^c2)
1554   if (N1C && N0.getOpcode() == ISD::XOR) {
1555     ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
1556     ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
1557     if (N00C)
1558       return DAG.getNode(ISD::XOR, VT, N0.getOperand(1),
1559                          DAG.getConstant(N1C->getValue()^N00C->getValue(), VT));
1560     if (N01C)
1561       return DAG.getNode(ISD::XOR, VT, N0.getOperand(0),
1562                          DAG.getConstant(N1C->getValue()^N01C->getValue(), VT));
1563   }
1564   // fold (xor x, x) -> 0
1565   if (N0 == N1) {
1566     if (!MVT::isVector(VT)) {
1567       return DAG.getConstant(0, VT);
1568     } else if (!AfterLegalize || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT)) {
1569       // Produce a vector of zeros.
1570       SDOperand El = DAG.getConstant(0, MVT::getVectorBaseType(VT));
1571       std::vector<SDOperand> Ops(MVT::getVectorNumElements(VT), El);
1572       return DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
1573     }
1574   }
1575
1576   // Simplify: xor (op x...), (op y...)  -> (op (xor x, y))
1577   if (N0.getOpcode() == N1.getOpcode()) {
1578     SDOperand Tmp = SimplifyBinOpWithSameOpcodeHands(N);
1579     if (Tmp.Val) return Tmp;
1580   }
1581
1582   // Simplify the expression using non-local knowledge.
1583   if (!MVT::isVector(VT) &&
1584       SimplifyDemandedBits(SDOperand(N, 0)))
1585     return SDOperand(N, 0);
1586
1587   return SDOperand();
1588 }
1589
1590 SDOperand DAGCombiner::visitSHL(SDNode *N) {
1591   SDOperand N0 = N->getOperand(0);
1592   SDOperand N1 = N->getOperand(1);
1593   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1594   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1595   MVT::ValueType VT = N0.getValueType();
1596   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
1597
1598   // fold (shl c1, c2) -> c1<<c2
1599   if (N0C && N1C)
1600     return DAG.getNode(ISD::SHL, VT, N0, N1);
1601   // fold (shl 0, x) -> 0
1602   if (N0C && N0C->isNullValue())
1603     return N0;
1604   // fold (shl x, c >= size(x)) -> undef
1605   if (N1C && N1C->getValue() >= OpSizeInBits)
1606     return DAG.getNode(ISD::UNDEF, VT);
1607   // fold (shl x, 0) -> x
1608   if (N1C && N1C->isNullValue())
1609     return N0;
1610   // if (shl x, c) is known to be zero, return 0
1611   if (TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
1612     return DAG.getConstant(0, VT);
1613   if (SimplifyDemandedBits(SDOperand(N, 0)))
1614     return SDOperand(N, 0);
1615   // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2)
1616   if (N1C && N0.getOpcode() == ISD::SHL &&
1617       N0.getOperand(1).getOpcode() == ISD::Constant) {
1618     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
1619     uint64_t c2 = N1C->getValue();
1620     if (c1 + c2 > OpSizeInBits)
1621       return DAG.getConstant(0, VT);
1622     return DAG.getNode(ISD::SHL, VT, N0.getOperand(0),
1623                        DAG.getConstant(c1 + c2, N1.getValueType()));
1624   }
1625   // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or
1626   //                               (srl (and x, -1 << c1), c1-c2)
1627   if (N1C && N0.getOpcode() == ISD::SRL &&
1628       N0.getOperand(1).getOpcode() == ISD::Constant) {
1629     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
1630     uint64_t c2 = N1C->getValue();
1631     SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0),
1632                                  DAG.getConstant(~0ULL << c1, VT));
1633     if (c2 > c1)
1634       return DAG.getNode(ISD::SHL, VT, Mask,
1635                          DAG.getConstant(c2-c1, N1.getValueType()));
1636     else
1637       return DAG.getNode(ISD::SRL, VT, Mask,
1638                          DAG.getConstant(c1-c2, N1.getValueType()));
1639   }
1640   // fold (shl (sra x, c1), c1) -> (and x, -1 << c1)
1641   if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1))
1642     return DAG.getNode(ISD::AND, VT, N0.getOperand(0),
1643                        DAG.getConstant(~0ULL << N1C->getValue(), VT));
1644   return SDOperand();
1645 }
1646
1647 SDOperand DAGCombiner::visitSRA(SDNode *N) {
1648   SDOperand N0 = N->getOperand(0);
1649   SDOperand N1 = N->getOperand(1);
1650   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1651   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1652   MVT::ValueType VT = N0.getValueType();
1653
1654   // fold (sra c1, c2) -> c1>>c2
1655   if (N0C && N1C)
1656     return DAG.getNode(ISD::SRA, VT, N0, N1);
1657   // fold (sra 0, x) -> 0
1658   if (N0C && N0C->isNullValue())
1659     return N0;
1660   // fold (sra -1, x) -> -1
1661   if (N0C && N0C->isAllOnesValue())
1662     return N0;
1663   // fold (sra x, c >= size(x)) -> undef
1664   if (N1C && N1C->getValue() >= MVT::getSizeInBits(VT))
1665     return DAG.getNode(ISD::UNDEF, VT);
1666   // fold (sra x, 0) -> x
1667   if (N1C && N1C->isNullValue())
1668     return N0;
1669   // fold (sra (shl x, c1), c1) -> sext_inreg for some c1 and target supports
1670   // sext_inreg.
1671   if (N1C && N0.getOpcode() == ISD::SHL && N1 == N0.getOperand(1)) {
1672     unsigned LowBits = MVT::getSizeInBits(VT) - (unsigned)N1C->getValue();
1673     MVT::ValueType EVT;
1674     switch (LowBits) {
1675     default: EVT = MVT::Other; break;
1676     case  1: EVT = MVT::i1;    break;
1677     case  8: EVT = MVT::i8;    break;
1678     case 16: EVT = MVT::i16;   break;
1679     case 32: EVT = MVT::i32;   break;
1680     }
1681     if (EVT > MVT::Other && TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, EVT))
1682       return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0),
1683                          DAG.getValueType(EVT));
1684   }
1685
1686   // fold (sra (sra x, c1), c2) -> (sra x, c1+c2)
1687   if (N1C && N0.getOpcode() == ISD::SRA) {
1688     if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
1689       unsigned Sum = N1C->getValue() + C1->getValue();
1690       if (Sum >= MVT::getSizeInBits(VT)) Sum = MVT::getSizeInBits(VT)-1;
1691       return DAG.getNode(ISD::SRA, VT, N0.getOperand(0),
1692                          DAG.getConstant(Sum, N1C->getValueType(0)));
1693     }
1694   }
1695
1696   // Simplify, based on bits shifted out of the LHS.
1697   if (N1C && SimplifyDemandedBits(SDOperand(N, 0)))
1698     return SDOperand(N, 0);
1699
1700
1701   // If the sign bit is known to be zero, switch this to a SRL.
1702   if (TLI.MaskedValueIsZero(N0, MVT::getIntVTSignBit(VT)))
1703     return DAG.getNode(ISD::SRL, VT, N0, N1);
1704   return SDOperand();
1705 }
1706
1707 SDOperand DAGCombiner::visitSRL(SDNode *N) {
1708   SDOperand N0 = N->getOperand(0);
1709   SDOperand N1 = N->getOperand(1);
1710   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1711   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1712   MVT::ValueType VT = N0.getValueType();
1713   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
1714
1715   // fold (srl c1, c2) -> c1 >>u c2
1716   if (N0C && N1C)
1717     return DAG.getNode(ISD::SRL, VT, N0, N1);
1718   // fold (srl 0, x) -> 0
1719   if (N0C && N0C->isNullValue())
1720     return N0;
1721   // fold (srl x, c >= size(x)) -> undef
1722   if (N1C && N1C->getValue() >= OpSizeInBits)
1723     return DAG.getNode(ISD::UNDEF, VT);
1724   // fold (srl x, 0) -> x
1725   if (N1C && N1C->isNullValue())
1726     return N0;
1727   // if (srl x, c) is known to be zero, return 0
1728   if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits)))
1729     return DAG.getConstant(0, VT);
1730   // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2)
1731   if (N1C && N0.getOpcode() == ISD::SRL &&
1732       N0.getOperand(1).getOpcode() == ISD::Constant) {
1733     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
1734     uint64_t c2 = N1C->getValue();
1735     if (c1 + c2 > OpSizeInBits)
1736       return DAG.getConstant(0, VT);
1737     return DAG.getNode(ISD::SRL, VT, N0.getOperand(0),
1738                        DAG.getConstant(c1 + c2, N1.getValueType()));
1739   }
1740
1741   // fold (srl (anyextend x), c) -> (anyextend (srl x, c))
1742   if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) {
1743     // Shifting in all undef bits?
1744     MVT::ValueType SmallVT = N0.getOperand(0).getValueType();
1745     if (N1C->getValue() >= MVT::getSizeInBits(SmallVT))
1746       return DAG.getNode(ISD::UNDEF, VT);
1747
1748     SDOperand SmallShift = DAG.getNode(ISD::SRL, SmallVT, N0.getOperand(0), N1);
1749     AddToWorkList(SmallShift.Val);
1750     return DAG.getNode(ISD::ANY_EXTEND, VT, SmallShift);
1751   }
1752
1753   // fold (srl (sra X, Y), 31) -> (srl X, 31).  This srl only looks at the sign
1754   // bit, which is unmodified by sra.
1755   if (N1C && N1C->getValue()+1 == MVT::getSizeInBits(VT)) {
1756     if (N0.getOpcode() == ISD::SRA)
1757       return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), N1);
1758   }
1759
1760   // fold (srl (ctlz x), "5") -> x  iff x has one bit set (the low bit).
1761   if (N1C && N0.getOpcode() == ISD::CTLZ &&
1762       N1C->getValue() == Log2_32(MVT::getSizeInBits(VT))) {
1763     uint64_t KnownZero, KnownOne, Mask = MVT::getIntVTBitMask(VT);
1764     TLI.ComputeMaskedBits(N0.getOperand(0), Mask, KnownZero, KnownOne);
1765
1766     // If any of the input bits are KnownOne, then the input couldn't be all
1767     // zeros, thus the result of the srl will always be zero.
1768     if (KnownOne) return DAG.getConstant(0, VT);
1769
1770     // If all of the bits input the to ctlz node are known to be zero, then
1771     // the result of the ctlz is "32" and the result of the shift is one.
1772     uint64_t UnknownBits = ~KnownZero & Mask;
1773     if (UnknownBits == 0) return DAG.getConstant(1, VT);
1774
1775     // Otherwise, check to see if there is exactly one bit input to the ctlz.
1776     if ((UnknownBits & (UnknownBits-1)) == 0) {
1777       // Okay, we know that only that the single bit specified by UnknownBits
1778       // could be set on input to the CTLZ node.  If this bit is set, the SRL
1779       // will return 0, if it is clear, it returns 1.  Change the CTLZ/SRL pair
1780       // to an SRL,XOR pair, which is likely to simplify more.
1781       unsigned ShAmt = CountTrailingZeros_64(UnknownBits);
1782       SDOperand Op = N0.getOperand(0);
1783       if (ShAmt) {
1784         Op = DAG.getNode(ISD::SRL, VT, Op,
1785                          DAG.getConstant(ShAmt, TLI.getShiftAmountTy()));
1786         AddToWorkList(Op.Val);
1787       }
1788       return DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(1, VT));
1789     }
1790   }
1791
1792   return SDOperand();
1793 }
1794
1795 SDOperand DAGCombiner::visitCTLZ(SDNode *N) {
1796   SDOperand N0 = N->getOperand(0);
1797   MVT::ValueType VT = N->getValueType(0);
1798
1799   // fold (ctlz c1) -> c2
1800   if (isa<ConstantSDNode>(N0))
1801     return DAG.getNode(ISD::CTLZ, VT, N0);
1802   return SDOperand();
1803 }
1804
1805 SDOperand DAGCombiner::visitCTTZ(SDNode *N) {
1806   SDOperand N0 = N->getOperand(0);
1807   MVT::ValueType VT = N->getValueType(0);
1808
1809   // fold (cttz c1) -> c2
1810   if (isa<ConstantSDNode>(N0))
1811     return DAG.getNode(ISD::CTTZ, VT, N0);
1812   return SDOperand();
1813 }
1814
1815 SDOperand DAGCombiner::visitCTPOP(SDNode *N) {
1816   SDOperand N0 = N->getOperand(0);
1817   MVT::ValueType VT = N->getValueType(0);
1818
1819   // fold (ctpop c1) -> c2
1820   if (isa<ConstantSDNode>(N0))
1821     return DAG.getNode(ISD::CTPOP, VT, N0);
1822   return SDOperand();
1823 }
1824
1825 SDOperand DAGCombiner::visitSELECT(SDNode *N) {
1826   SDOperand N0 = N->getOperand(0);
1827   SDOperand N1 = N->getOperand(1);
1828   SDOperand N2 = N->getOperand(2);
1829   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1830   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1831   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
1832   MVT::ValueType VT = N->getValueType(0);
1833
1834   // fold select C, X, X -> X
1835   if (N1 == N2)
1836     return N1;
1837   // fold select true, X, Y -> X
1838   if (N0C && !N0C->isNullValue())
1839     return N1;
1840   // fold select false, X, Y -> Y
1841   if (N0C && N0C->isNullValue())
1842     return N2;
1843   // fold select C, 1, X -> C | X
1844   if (MVT::i1 == VT && N1C && N1C->getValue() == 1)
1845     return DAG.getNode(ISD::OR, VT, N0, N2);
1846   // fold select C, 0, X -> ~C & X
1847   // FIXME: this should check for C type == X type, not i1?
1848   if (MVT::i1 == VT && N1C && N1C->isNullValue()) {
1849     SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
1850     AddToWorkList(XORNode.Val);
1851     return DAG.getNode(ISD::AND, VT, XORNode, N2);
1852   }
1853   // fold select C, X, 1 -> ~C | X
1854   if (MVT::i1 == VT && N2C && N2C->getValue() == 1) {
1855     SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
1856     AddToWorkList(XORNode.Val);
1857     return DAG.getNode(ISD::OR, VT, XORNode, N1);
1858   }
1859   // fold select C, X, 0 -> C & X
1860   // FIXME: this should check for C type == X type, not i1?
1861   if (MVT::i1 == VT && N2C && N2C->isNullValue())
1862     return DAG.getNode(ISD::AND, VT, N0, N1);
1863   // fold  X ? X : Y --> X ? 1 : Y --> X | Y
1864   if (MVT::i1 == VT && N0 == N1)
1865     return DAG.getNode(ISD::OR, VT, N0, N2);
1866   // fold X ? Y : X --> X ? Y : 0 --> X & Y
1867   if (MVT::i1 == VT && N0 == N2)
1868     return DAG.getNode(ISD::AND, VT, N0, N1);
1869
1870   // If we can fold this based on the true/false value, do so.
1871   if (SimplifySelectOps(N, N1, N2))
1872     return SDOperand(N, 0);  // Don't revisit N.
1873
1874   // fold selects based on a setcc into other things, such as min/max/abs
1875   if (N0.getOpcode() == ISD::SETCC)
1876     // FIXME:
1877     // Check against MVT::Other for SELECT_CC, which is a workaround for targets
1878     // having to say they don't support SELECT_CC on every type the DAG knows
1879     // about, since there is no way to mark an opcode illegal at all value types
1880     if (TLI.isOperationLegal(ISD::SELECT_CC, MVT::Other))
1881       return DAG.getNode(ISD::SELECT_CC, VT, N0.getOperand(0), N0.getOperand(1),
1882                          N1, N2, N0.getOperand(2));
1883     else
1884       return SimplifySelect(N0, N1, N2);
1885   return SDOperand();
1886 }
1887
1888 SDOperand DAGCombiner::visitSELECT_CC(SDNode *N) {
1889   SDOperand N0 = N->getOperand(0);
1890   SDOperand N1 = N->getOperand(1);
1891   SDOperand N2 = N->getOperand(2);
1892   SDOperand N3 = N->getOperand(3);
1893   SDOperand N4 = N->getOperand(4);
1894   ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get();
1895
1896   // fold select_cc lhs, rhs, x, x, cc -> x
1897   if (N2 == N3)
1898     return N2;
1899
1900   // Determine if the condition we're dealing with is constant
1901   SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
1902   if (SCC.Val) AddToWorkList(SCC.Val);
1903
1904   if (ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val)) {
1905     if (SCCC->getValue())
1906       return N2;    // cond always true -> true val
1907     else
1908       return N3;    // cond always false -> false val
1909   }
1910
1911   // Fold to a simpler select_cc
1912   if (SCC.Val && SCC.getOpcode() == ISD::SETCC)
1913     return DAG.getNode(ISD::SELECT_CC, N2.getValueType(),
1914                        SCC.getOperand(0), SCC.getOperand(1), N2, N3,
1915                        SCC.getOperand(2));
1916
1917   // If we can fold this based on the true/false value, do so.
1918   if (SimplifySelectOps(N, N2, N3))
1919     return SDOperand(N, 0);  // Don't revisit N.
1920
1921   // fold select_cc into other things, such as min/max/abs
1922   return SimplifySelectCC(N0, N1, N2, N3, CC);
1923 }
1924
1925 SDOperand DAGCombiner::visitSETCC(SDNode *N) {
1926   return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1),
1927                        cast<CondCodeSDNode>(N->getOperand(2))->get());
1928 }
1929
1930 SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) {
1931   SDOperand N0 = N->getOperand(0);
1932   MVT::ValueType VT = N->getValueType(0);
1933
1934   // fold (sext c1) -> c1
1935   if (isa<ConstantSDNode>(N0))
1936     return DAG.getNode(ISD::SIGN_EXTEND, VT, N0);
1937
1938   // fold (sext (sext x)) -> (sext x)
1939   // fold (sext (aext x)) -> (sext x)
1940   if (N0.getOpcode() == ISD::SIGN_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND)
1941     return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0));
1942
1943   if (N0.getOpcode() == ISD::TRUNCATE) {
1944     // See if the value being truncated is already sign extended.  If so, just
1945     // eliminate the trunc/sext pair.
1946     SDOperand Op = N0.getOperand(0);
1947     unsigned OpBits   = MVT::getSizeInBits(Op.getValueType());
1948     unsigned MidBits  = MVT::getSizeInBits(N0.getValueType());
1949     unsigned DestBits = MVT::getSizeInBits(VT);
1950     unsigned NumSignBits = TLI.ComputeNumSignBits(Op);
1951
1952     if (OpBits == DestBits) {
1953       // Op is i32, Mid is i8, and Dest is i32.  If Op has more than 24 sign
1954       // bits, it is already ready.
1955       if (NumSignBits > DestBits-MidBits)
1956         return Op;
1957     } else if (OpBits < DestBits) {
1958       // Op is i32, Mid is i8, and Dest is i64.  If Op has more than 24 sign
1959       // bits, just sext from i32.
1960       if (NumSignBits > OpBits-MidBits)
1961         return DAG.getNode(ISD::SIGN_EXTEND, VT, Op);
1962     } else {
1963       // Op is i64, Mid is i8, and Dest is i32.  If Op has more than 56 sign
1964       // bits, just truncate to i32.
1965       if (NumSignBits > OpBits-MidBits)
1966         return DAG.getNode(ISD::TRUNCATE, VT, Op);
1967     }
1968
1969     // fold (sext (truncate x)) -> (sextinreg x).
1970     if (!AfterLegalize || TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG,
1971                                                N0.getValueType())) {
1972       if (Op.getValueType() < VT)
1973         Op = DAG.getNode(ISD::ANY_EXTEND, VT, Op);
1974       else if (Op.getValueType() > VT)
1975         Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
1976       return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, Op,
1977                          DAG.getValueType(N0.getValueType()));
1978     }
1979   }
1980
1981   // fold (sext (load x)) -> (sext (truncate (sextload x)))
1982   if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() &&
1983       (!AfterLegalize||TLI.isLoadXLegal(ISD::SEXTLOAD, N0.getValueType()))){
1984     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
1985     SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(),
1986                                        LN0->getBasePtr(), LN0->getSrcValue(),
1987                                        LN0->getSrcValueOffset(),
1988                                        N0.getValueType());
1989     CombineTo(N, ExtLoad);
1990     CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
1991               ExtLoad.getValue(1));
1992     return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
1993   }
1994
1995   // fold (sext (sextload x)) -> (sext (truncate (sextload x)))
1996   // fold (sext ( extload x)) -> (sext (truncate (sextload x)))
1997   if ((ISD::isSEXTLoad(N0.Val) || ISD::isEXTLoad(N0.Val)) && N0.hasOneUse()) {
1998     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
1999     MVT::ValueType EVT = LN0->getLoadedVT();
2000     if (!AfterLegalize || TLI.isLoadXLegal(ISD::SEXTLOAD, EVT)) {
2001       SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(),
2002                                          LN0->getBasePtr(), LN0->getSrcValue(),
2003                                          LN0->getSrcValueOffset(), EVT);
2004       CombineTo(N, ExtLoad);
2005       CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
2006                 ExtLoad.getValue(1));
2007       return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
2008     }
2009   }
2010
2011   return SDOperand();
2012 }
2013
2014 SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) {
2015   SDOperand N0 = N->getOperand(0);
2016   MVT::ValueType VT = N->getValueType(0);
2017
2018   // fold (zext c1) -> c1
2019   if (isa<ConstantSDNode>(N0))
2020     return DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
2021   // fold (zext (zext x)) -> (zext x)
2022   // fold (zext (aext x)) -> (zext x)
2023   if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::ANY_EXTEND)
2024     return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0));
2025
2026   // fold (zext (truncate x)) -> (and x, mask)
2027   if (N0.getOpcode() == ISD::TRUNCATE &&
2028       (!AfterLegalize || TLI.isOperationLegal(ISD::AND, VT))) {
2029     SDOperand Op = N0.getOperand(0);
2030     if (Op.getValueType() < VT) {
2031       Op = DAG.getNode(ISD::ANY_EXTEND, VT, Op);
2032     } else if (Op.getValueType() > VT) {
2033       Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
2034     }
2035     return DAG.getZeroExtendInReg(Op, N0.getValueType());
2036   }
2037
2038   // fold (zext (and (trunc x), cst)) -> (and x, cst).
2039   if (N0.getOpcode() == ISD::AND &&
2040       N0.getOperand(0).getOpcode() == ISD::TRUNCATE &&
2041       N0.getOperand(1).getOpcode() == ISD::Constant) {
2042     SDOperand X = N0.getOperand(0).getOperand(0);
2043     if (X.getValueType() < VT) {
2044       X = DAG.getNode(ISD::ANY_EXTEND, VT, X);
2045     } else if (X.getValueType() > VT) {
2046       X = DAG.getNode(ISD::TRUNCATE, VT, X);
2047     }
2048     uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
2049     return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(Mask, VT));
2050   }
2051
2052   // fold (zext (load x)) -> (zext (truncate (zextload x)))
2053   if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() &&
2054       (!AfterLegalize||TLI.isLoadXLegal(ISD::ZEXTLOAD, N0.getValueType()))) {
2055     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2056     SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
2057                                        LN0->getBasePtr(), LN0->getSrcValue(),
2058                                        LN0->getSrcValueOffset(),
2059                                        N0.getValueType());
2060     CombineTo(N, ExtLoad);
2061     CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
2062               ExtLoad.getValue(1));
2063     return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
2064   }
2065
2066   // fold (zext (zextload x)) -> (zext (truncate (zextload x)))
2067   // fold (zext ( extload x)) -> (zext (truncate (zextload x)))
2068   if ((ISD::isZEXTLoad(N0.Val) || ISD::isEXTLoad(N0.Val)) && N0.hasOneUse()) {
2069     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2070     MVT::ValueType EVT = LN0->getLoadedVT();
2071     SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, LN0->getChain(),
2072                                        LN0->getBasePtr(), LN0->getSrcValue(),
2073                                        LN0->getSrcValueOffset(), EVT);
2074     CombineTo(N, ExtLoad);
2075     CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
2076               ExtLoad.getValue(1));
2077     return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
2078   }
2079   return SDOperand();
2080 }
2081
2082 SDOperand DAGCombiner::visitANY_EXTEND(SDNode *N) {
2083   SDOperand N0 = N->getOperand(0);
2084   MVT::ValueType VT = N->getValueType(0);
2085
2086   // fold (aext c1) -> c1
2087   if (isa<ConstantSDNode>(N0))
2088     return DAG.getNode(ISD::ANY_EXTEND, VT, N0);
2089   // fold (aext (aext x)) -> (aext x)
2090   // fold (aext (zext x)) -> (zext x)
2091   // fold (aext (sext x)) -> (sext x)
2092   if (N0.getOpcode() == ISD::ANY_EXTEND  ||
2093       N0.getOpcode() == ISD::ZERO_EXTEND ||
2094       N0.getOpcode() == ISD::SIGN_EXTEND)
2095     return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0));
2096
2097   // fold (aext (truncate x))
2098   if (N0.getOpcode() == ISD::TRUNCATE) {
2099     SDOperand TruncOp = N0.getOperand(0);
2100     if (TruncOp.getValueType() == VT)
2101       return TruncOp; // x iff x size == zext size.
2102     if (TruncOp.getValueType() > VT)
2103       return DAG.getNode(ISD::TRUNCATE, VT, TruncOp);
2104     return DAG.getNode(ISD::ANY_EXTEND, VT, TruncOp);
2105   }
2106
2107   // fold (aext (and (trunc x), cst)) -> (and x, cst).
2108   if (N0.getOpcode() == ISD::AND &&
2109       N0.getOperand(0).getOpcode() == ISD::TRUNCATE &&
2110       N0.getOperand(1).getOpcode() == ISD::Constant) {
2111     SDOperand X = N0.getOperand(0).getOperand(0);
2112     if (X.getValueType() < VT) {
2113       X = DAG.getNode(ISD::ANY_EXTEND, VT, X);
2114     } else if (X.getValueType() > VT) {
2115       X = DAG.getNode(ISD::TRUNCATE, VT, X);
2116     }
2117     uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
2118     return DAG.getNode(ISD::AND, VT, X, DAG.getConstant(Mask, VT));
2119   }
2120
2121   // fold (aext (load x)) -> (aext (truncate (extload x)))
2122   if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() &&
2123       (!AfterLegalize||TLI.isLoadXLegal(ISD::EXTLOAD, N0.getValueType()))) {
2124     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2125     SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(),
2126                                        LN0->getBasePtr(), LN0->getSrcValue(),
2127                                        LN0->getSrcValueOffset(),
2128                                        N0.getValueType());
2129     CombineTo(N, ExtLoad);
2130     CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
2131               ExtLoad.getValue(1));
2132     return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
2133   }
2134
2135   // fold (aext (zextload x)) -> (aext (truncate (zextload x)))
2136   // fold (aext (sextload x)) -> (aext (truncate (sextload x)))
2137   // fold (aext ( extload x)) -> (aext (truncate (extload  x)))
2138   if (N0.getOpcode() == ISD::LOAD && !ISD::isNON_EXTLoad(N0.Val) &&
2139       N0.hasOneUse()) {
2140     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2141     MVT::ValueType EVT = LN0->getLoadedVT();
2142     SDOperand ExtLoad = DAG.getExtLoad(LN0->getExtensionType(), VT,
2143                                        LN0->getChain(), LN0->getBasePtr(),
2144                                        LN0->getSrcValue(),
2145                                        LN0->getSrcValueOffset(), EVT);
2146     CombineTo(N, ExtLoad);
2147     CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
2148               ExtLoad.getValue(1));
2149     return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
2150   }
2151   return SDOperand();
2152 }
2153
2154
2155 SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) {
2156   SDOperand N0 = N->getOperand(0);
2157   SDOperand N1 = N->getOperand(1);
2158   MVT::ValueType VT = N->getValueType(0);
2159   MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT();
2160   unsigned EVTBits = MVT::getSizeInBits(EVT);
2161
2162   // fold (sext_in_reg c1) -> c1
2163   if (isa<ConstantSDNode>(N0) || N0.getOpcode() == ISD::UNDEF)
2164     return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0, N1);
2165
2166   // If the input is already sign extended, just drop the extension.
2167   if (TLI.ComputeNumSignBits(N0) >= MVT::getSizeInBits(VT)-EVTBits+1)
2168     return N0;
2169
2170   // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2
2171   if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
2172       EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) {
2173     return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1);
2174   }
2175
2176   // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is zero
2177   if (TLI.MaskedValueIsZero(N0, 1ULL << (EVTBits-1)))
2178     return DAG.getZeroExtendInReg(N0, EVT);
2179
2180   // fold (sext_in_reg (srl X, 24), i8) -> sra X, 24
2181   // fold (sext_in_reg (srl X, 23), i8) -> sra X, 23 iff possible.
2182   // We already fold "(sext_in_reg (srl X, 25), i8) -> srl X, 25" above.
2183   if (N0.getOpcode() == ISD::SRL) {
2184     if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
2185       if (ShAmt->getValue()+EVTBits <= MVT::getSizeInBits(VT)) {
2186         // We can turn this into an SRA iff the input to the SRL is already sign
2187         // extended enough.
2188         unsigned InSignBits = TLI.ComputeNumSignBits(N0.getOperand(0));
2189         if (MVT::getSizeInBits(VT)-(ShAmt->getValue()+EVTBits) < InSignBits)
2190           return DAG.getNode(ISD::SRA, VT, N0.getOperand(0), N0.getOperand(1));
2191       }
2192   }
2193
2194   // fold (sext_inreg (extload x)) -> (sextload x)
2195   if (ISD::isEXTLoad(N0.Val) &&
2196       EVT == cast<LoadSDNode>(N0)->getLoadedVT() &&
2197       (!AfterLegalize || TLI.isLoadXLegal(ISD::SEXTLOAD, EVT))) {
2198     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2199     SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(),
2200                                        LN0->getBasePtr(), LN0->getSrcValue(),
2201                                        LN0->getSrcValueOffset(), EVT);
2202     CombineTo(N, ExtLoad);
2203     CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
2204     return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
2205   }
2206   // fold (sext_inreg (zextload x)) -> (sextload x) iff load has one use
2207   if (ISD::isZEXTLoad(N0.Val) && N0.hasOneUse() &&
2208       EVT == cast<LoadSDNode>(N0)->getLoadedVT() &&
2209       (!AfterLegalize || TLI.isLoadXLegal(ISD::SEXTLOAD, EVT))) {
2210     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2211     SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, LN0->getChain(),
2212                                        LN0->getBasePtr(), LN0->getSrcValue(),
2213                                        LN0->getSrcValueOffset(), EVT);
2214     CombineTo(N, ExtLoad);
2215     CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
2216     return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
2217   }
2218   return SDOperand();
2219 }
2220
2221 SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) {
2222   SDOperand N0 = N->getOperand(0);
2223   MVT::ValueType VT = N->getValueType(0);
2224
2225   // noop truncate
2226   if (N0.getValueType() == N->getValueType(0))
2227     return N0;
2228   // fold (truncate c1) -> c1
2229   if (isa<ConstantSDNode>(N0))
2230     return DAG.getNode(ISD::TRUNCATE, VT, N0);
2231   // fold (truncate (truncate x)) -> (truncate x)
2232   if (N0.getOpcode() == ISD::TRUNCATE)
2233     return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
2234   // fold (truncate (ext x)) -> (ext x) or (truncate x) or x
2235   if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND||
2236       N0.getOpcode() == ISD::ANY_EXTEND) {
2237     if (N0.getOperand(0).getValueType() < VT)
2238       // if the source is smaller than the dest, we still need an extend
2239       return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0));
2240     else if (N0.getOperand(0).getValueType() > VT)
2241       // if the source is larger than the dest, than we just need the truncate
2242       return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
2243     else
2244       // if the source and dest are the same type, we can drop both the extend
2245       // and the truncate
2246       return N0.getOperand(0);
2247   }
2248   // fold (truncate (load x)) -> (smaller load x)
2249   if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() &&
2250       // Do not allow folding to i1 here.  i1 is implicitly stored in memory in
2251       // zero extended form: by shrinking the load, we lose track of the fact
2252       // that it is already zero extended.
2253       // FIXME: This should be reevaluated.
2254       VT != MVT::i1) {
2255     assert(MVT::getSizeInBits(N0.getValueType()) > MVT::getSizeInBits(VT) &&
2256            "Cannot truncate to larger type!");
2257     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2258     MVT::ValueType PtrType = N0.getOperand(1).getValueType();
2259     // For big endian targets, we need to add an offset to the pointer to load
2260     // the correct bytes.  For little endian systems, we merely need to read
2261     // fewer bytes from the same pointer.
2262     uint64_t PtrOff =
2263       (MVT::getSizeInBits(N0.getValueType()) - MVT::getSizeInBits(VT)) / 8;
2264     SDOperand NewPtr = TLI.isLittleEndian() ? LN0->getBasePtr() :
2265       DAG.getNode(ISD::ADD, PtrType, LN0->getBasePtr(),
2266                   DAG.getConstant(PtrOff, PtrType));
2267     AddToWorkList(NewPtr.Val);
2268     SDOperand Load = DAG.getLoad(VT, LN0->getChain(), NewPtr,
2269                                  LN0->getSrcValue(), LN0->getSrcValueOffset());
2270     AddToWorkList(N);
2271     CombineTo(N0.Val, Load, Load.getValue(1));
2272     return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
2273   }
2274   return SDOperand();
2275 }
2276
2277 SDOperand DAGCombiner::visitBIT_CONVERT(SDNode *N) {
2278   SDOperand N0 = N->getOperand(0);
2279   MVT::ValueType VT = N->getValueType(0);
2280
2281   // If the input is a constant, let getNode() fold it.
2282   if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) {
2283     SDOperand Res = DAG.getNode(ISD::BIT_CONVERT, VT, N0);
2284     if (Res.Val != N) return Res;
2285   }
2286
2287   if (N0.getOpcode() == ISD::BIT_CONVERT)  // conv(conv(x,t1),t2) -> conv(x,t2)
2288     return DAG.getNode(ISD::BIT_CONVERT, VT, N0.getOperand(0));
2289
2290   // fold (conv (load x)) -> (load (conv*)x)
2291   // FIXME: These xforms need to know that the resultant load doesn't need a
2292   // higher alignment than the original!
2293   if (0 && ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse()) {
2294     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2295     SDOperand Load = DAG.getLoad(VT, LN0->getChain(), LN0->getBasePtr(),
2296                                  LN0->getSrcValue(), LN0->getSrcValueOffset());
2297     AddToWorkList(N);
2298     CombineTo(N0.Val, DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load),
2299               Load.getValue(1));
2300     return Load;
2301   }
2302
2303   return SDOperand();
2304 }
2305
2306 SDOperand DAGCombiner::visitVBIT_CONVERT(SDNode *N) {
2307   SDOperand N0 = N->getOperand(0);
2308   MVT::ValueType VT = N->getValueType(0);
2309
2310   // If the input is a VBUILD_VECTOR with all constant elements, fold this now.
2311   // First check to see if this is all constant.
2312   if (N0.getOpcode() == ISD::VBUILD_VECTOR && N0.Val->hasOneUse() &&
2313       VT == MVT::Vector) {
2314     bool isSimple = true;
2315     for (unsigned i = 0, e = N0.getNumOperands()-2; i != e; ++i)
2316       if (N0.getOperand(i).getOpcode() != ISD::UNDEF &&
2317           N0.getOperand(i).getOpcode() != ISD::Constant &&
2318           N0.getOperand(i).getOpcode() != ISD::ConstantFP) {
2319         isSimple = false;
2320         break;
2321       }
2322
2323     MVT::ValueType DestEltVT = cast<VTSDNode>(N->getOperand(2))->getVT();
2324     if (isSimple && !MVT::isVector(DestEltVT)) {
2325       return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(N0.Val, DestEltVT);
2326     }
2327   }
2328
2329   return SDOperand();
2330 }
2331
2332 /// ConstantFoldVBIT_CONVERTofVBUILD_VECTOR - We know that BV is a vbuild_vector
2333 /// node with Constant, ConstantFP or Undef operands.  DstEltVT indicates the
2334 /// destination element value type.
2335 SDOperand DAGCombiner::
2336 ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *BV, MVT::ValueType DstEltVT) {
2337   MVT::ValueType SrcEltVT = BV->getOperand(0).getValueType();
2338
2339   // If this is already the right type, we're done.
2340   if (SrcEltVT == DstEltVT) return SDOperand(BV, 0);
2341
2342   unsigned SrcBitSize = MVT::getSizeInBits(SrcEltVT);
2343   unsigned DstBitSize = MVT::getSizeInBits(DstEltVT);
2344
2345   // If this is a conversion of N elements of one type to N elements of another
2346   // type, convert each element.  This handles FP<->INT cases.
2347   if (SrcBitSize == DstBitSize) {
2348     SmallVector<SDOperand, 8> Ops;
2349     for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) {
2350       Ops.push_back(DAG.getNode(ISD::BIT_CONVERT, DstEltVT, BV->getOperand(i)));
2351       AddToWorkList(Ops.back().Val);
2352     }
2353     Ops.push_back(*(BV->op_end()-2)); // Add num elements.
2354     Ops.push_back(DAG.getValueType(DstEltVT));
2355     return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
2356   }
2357
2358   // Otherwise, we're growing or shrinking the elements.  To avoid having to
2359   // handle annoying details of growing/shrinking FP values, we convert them to
2360   // int first.
2361   if (MVT::isFloatingPoint(SrcEltVT)) {
2362     // Convert the input float vector to a int vector where the elements are the
2363     // same sizes.
2364     assert((SrcEltVT == MVT::f32 || SrcEltVT == MVT::f64) && "Unknown FP VT!");
2365     MVT::ValueType IntVT = SrcEltVT == MVT::f32 ? MVT::i32 : MVT::i64;
2366     BV = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, IntVT).Val;
2367     SrcEltVT = IntVT;
2368   }
2369
2370   // Now we know the input is an integer vector.  If the output is a FP type,
2371   // convert to integer first, then to FP of the right size.
2372   if (MVT::isFloatingPoint(DstEltVT)) {
2373     assert((DstEltVT == MVT::f32 || DstEltVT == MVT::f64) && "Unknown FP VT!");
2374     MVT::ValueType TmpVT = DstEltVT == MVT::f32 ? MVT::i32 : MVT::i64;
2375     SDNode *Tmp = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, TmpVT).Val;
2376
2377     // Next, convert to FP elements of the same size.
2378     return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(Tmp, DstEltVT);
2379   }
2380
2381   // Okay, we know the src/dst types are both integers of differing types.
2382   // Handling growing first.
2383   assert(MVT::isInteger(SrcEltVT) && MVT::isInteger(DstEltVT));
2384   if (SrcBitSize < DstBitSize) {
2385     unsigned NumInputsPerOutput = DstBitSize/SrcBitSize;
2386
2387     SmallVector<SDOperand, 8> Ops;
2388     for (unsigned i = 0, e = BV->getNumOperands()-2; i != e;
2389          i += NumInputsPerOutput) {
2390       bool isLE = TLI.isLittleEndian();
2391       uint64_t NewBits = 0;
2392       bool EltIsUndef = true;
2393       for (unsigned j = 0; j != NumInputsPerOutput; ++j) {
2394         // Shift the previously computed bits over.
2395         NewBits <<= SrcBitSize;
2396         SDOperand Op = BV->getOperand(i+ (isLE ? (NumInputsPerOutput-j-1) : j));
2397         if (Op.getOpcode() == ISD::UNDEF) continue;
2398         EltIsUndef = false;
2399
2400         NewBits |= cast<ConstantSDNode>(Op)->getValue();
2401       }
2402
2403       if (EltIsUndef)
2404         Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT));
2405       else
2406         Ops.push_back(DAG.getConstant(NewBits, DstEltVT));
2407     }
2408
2409     Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements.
2410     Ops.push_back(DAG.getValueType(DstEltVT));            // Add element size.
2411     return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
2412   }
2413
2414   // Finally, this must be the case where we are shrinking elements: each input
2415   // turns into multiple outputs.
2416   unsigned NumOutputsPerInput = SrcBitSize/DstBitSize;
2417   SmallVector<SDOperand, 8> Ops;
2418   for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) {
2419     if (BV->getOperand(i).getOpcode() == ISD::UNDEF) {
2420       for (unsigned j = 0; j != NumOutputsPerInput; ++j)
2421         Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT));
2422       continue;
2423     }
2424     uint64_t OpVal = cast<ConstantSDNode>(BV->getOperand(i))->getValue();
2425
2426     for (unsigned j = 0; j != NumOutputsPerInput; ++j) {
2427       unsigned ThisVal = OpVal & ((1ULL << DstBitSize)-1);
2428       OpVal >>= DstBitSize;
2429       Ops.push_back(DAG.getConstant(ThisVal, DstEltVT));
2430     }
2431
2432     // For big endian targets, swap the order of the pieces of each element.
2433     if (!TLI.isLittleEndian())
2434       std::reverse(Ops.end()-NumOutputsPerInput, Ops.end());
2435   }
2436   Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements.
2437   Ops.push_back(DAG.getValueType(DstEltVT));            // Add element size.
2438   return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
2439 }
2440
2441
2442
2443 SDOperand DAGCombiner::visitFADD(SDNode *N) {
2444   SDOperand N0 = N->getOperand(0);
2445   SDOperand N1 = N->getOperand(1);
2446   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2447   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
2448   MVT::ValueType VT = N->getValueType(0);
2449
2450   // fold (fadd c1, c2) -> c1+c2
2451   if (N0CFP && N1CFP)
2452     return DAG.getNode(ISD::FADD, VT, N0, N1);
2453   // canonicalize constant to RHS
2454   if (N0CFP && !N1CFP)
2455     return DAG.getNode(ISD::FADD, VT, N1, N0);
2456   // fold (A + (-B)) -> A-B
2457   if (N1.getOpcode() == ISD::FNEG)
2458     return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0));
2459   // fold ((-A) + B) -> B-A
2460   if (N0.getOpcode() == ISD::FNEG)
2461     return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0));
2462
2463   // If allowed, fold (fadd (fadd x, c1), c2) -> (fadd x, (fadd c1, c2))
2464   if (UnsafeFPMath && N1CFP && N0.getOpcode() == ISD::FADD &&
2465       N0.Val->hasOneUse() && isa<ConstantFPSDNode>(N0.getOperand(1)))
2466     return DAG.getNode(ISD::FADD, VT, N0.getOperand(0),
2467                        DAG.getNode(ISD::FADD, VT, N0.getOperand(1), N1));
2468
2469   return SDOperand();
2470 }
2471
2472 SDOperand DAGCombiner::visitFSUB(SDNode *N) {
2473   SDOperand N0 = N->getOperand(0);
2474   SDOperand N1 = N->getOperand(1);
2475   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2476   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
2477   MVT::ValueType VT = N->getValueType(0);
2478
2479   // fold (fsub c1, c2) -> c1-c2
2480   if (N0CFP && N1CFP)
2481     return DAG.getNode(ISD::FSUB, VT, N0, N1);
2482   // fold (A-(-B)) -> A+B
2483   if (N1.getOpcode() == ISD::FNEG)
2484     return DAG.getNode(ISD::FADD, VT, N0, N1.getOperand(0));
2485   return SDOperand();
2486 }
2487
2488 SDOperand DAGCombiner::visitFMUL(SDNode *N) {
2489   SDOperand N0 = N->getOperand(0);
2490   SDOperand N1 = N->getOperand(1);
2491   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2492   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
2493   MVT::ValueType VT = N->getValueType(0);
2494
2495   // fold (fmul c1, c2) -> c1*c2
2496   if (N0CFP && N1CFP)
2497     return DAG.getNode(ISD::FMUL, VT, N0, N1);
2498   // canonicalize constant to RHS
2499   if (N0CFP && !N1CFP)
2500     return DAG.getNode(ISD::FMUL, VT, N1, N0);
2501   // fold (fmul X, 2.0) -> (fadd X, X)
2502   if (N1CFP && N1CFP->isExactlyValue(+2.0))
2503     return DAG.getNode(ISD::FADD, VT, N0, N0);
2504
2505   // If allowed, fold (fmul (fmul x, c1), c2) -> (fmul x, (fmul c1, c2))
2506   if (UnsafeFPMath && N1CFP && N0.getOpcode() == ISD::FMUL &&
2507       N0.Val->hasOneUse() && isa<ConstantFPSDNode>(N0.getOperand(1)))
2508     return DAG.getNode(ISD::FMUL, VT, N0.getOperand(0),
2509                        DAG.getNode(ISD::FMUL, VT, N0.getOperand(1), N1));
2510
2511   return SDOperand();
2512 }
2513
2514 SDOperand DAGCombiner::visitFDIV(SDNode *N) {
2515   SDOperand N0 = N->getOperand(0);
2516   SDOperand N1 = N->getOperand(1);
2517   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2518   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
2519   MVT::ValueType VT = N->getValueType(0);
2520
2521   // fold (fdiv c1, c2) -> c1/c2
2522   if (N0CFP && N1CFP)
2523     return DAG.getNode(ISD::FDIV, VT, N0, N1);
2524   return SDOperand();
2525 }
2526
2527 SDOperand DAGCombiner::visitFREM(SDNode *N) {
2528   SDOperand N0 = N->getOperand(0);
2529   SDOperand N1 = N->getOperand(1);
2530   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2531   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
2532   MVT::ValueType VT = N->getValueType(0);
2533
2534   // fold (frem c1, c2) -> fmod(c1,c2)
2535   if (N0CFP && N1CFP)
2536     return DAG.getNode(ISD::FREM, VT, N0, N1);
2537   return SDOperand();
2538 }
2539
2540 SDOperand DAGCombiner::visitFCOPYSIGN(SDNode *N) {
2541   SDOperand N0 = N->getOperand(0);
2542   SDOperand N1 = N->getOperand(1);
2543   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2544   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
2545   MVT::ValueType VT = N->getValueType(0);
2546
2547   if (N0CFP && N1CFP)  // Constant fold
2548     return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1);
2549
2550   if (N1CFP) {
2551     // copysign(x, c1) -> fabs(x)       iff ispos(c1)
2552     // copysign(x, c1) -> fneg(fabs(x)) iff isneg(c1)
2553     union {
2554       double d;
2555       int64_t i;
2556     } u;
2557     u.d = N1CFP->getValue();
2558     if (u.i >= 0)
2559       return DAG.getNode(ISD::FABS, VT, N0);
2560     else
2561       return DAG.getNode(ISD::FNEG, VT, DAG.getNode(ISD::FABS, VT, N0));
2562   }
2563
2564   // copysign(fabs(x), y) -> copysign(x, y)
2565   // copysign(fneg(x), y) -> copysign(x, y)
2566   // copysign(copysign(x,z), y) -> copysign(x, y)
2567   if (N0.getOpcode() == ISD::FABS || N0.getOpcode() == ISD::FNEG ||
2568       N0.getOpcode() == ISD::FCOPYSIGN)
2569     return DAG.getNode(ISD::FCOPYSIGN, VT, N0.getOperand(0), N1);
2570
2571   // copysign(x, abs(y)) -> abs(x)
2572   if (N1.getOpcode() == ISD::FABS)
2573     return DAG.getNode(ISD::FABS, VT, N0);
2574
2575   // copysign(x, copysign(y,z)) -> copysign(x, z)
2576   if (N1.getOpcode() == ISD::FCOPYSIGN)
2577     return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(1));
2578
2579   // copysign(x, fp_extend(y)) -> copysign(x, y)
2580   // copysign(x, fp_round(y)) -> copysign(x, y)
2581   if (N1.getOpcode() == ISD::FP_EXTEND || N1.getOpcode() == ISD::FP_ROUND)
2582     return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(0));
2583
2584   return SDOperand();
2585 }
2586
2587
2588
2589 SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) {
2590   SDOperand N0 = N->getOperand(0);
2591   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
2592   MVT::ValueType VT = N->getValueType(0);
2593
2594   // fold (sint_to_fp c1) -> c1fp
2595   if (N0C)
2596     return DAG.getNode(ISD::SINT_TO_FP, VT, N0);
2597   return SDOperand();
2598 }
2599
2600 SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) {
2601   SDOperand N0 = N->getOperand(0);
2602   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
2603   MVT::ValueType VT = N->getValueType(0);
2604
2605   // fold (uint_to_fp c1) -> c1fp
2606   if (N0C)
2607     return DAG.getNode(ISD::UINT_TO_FP, VT, N0);
2608   return SDOperand();
2609 }
2610
2611 SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) {
2612   SDOperand N0 = N->getOperand(0);
2613   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2614   MVT::ValueType VT = N->getValueType(0);
2615
2616   // fold (fp_to_sint c1fp) -> c1
2617   if (N0CFP)
2618     return DAG.getNode(ISD::FP_TO_SINT, VT, N0);
2619   return SDOperand();
2620 }
2621
2622 SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) {
2623   SDOperand N0 = N->getOperand(0);
2624   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2625   MVT::ValueType VT = N->getValueType(0);
2626
2627   // fold (fp_to_uint c1fp) -> c1
2628   if (N0CFP)
2629     return DAG.getNode(ISD::FP_TO_UINT, VT, N0);
2630   return SDOperand();
2631 }
2632
2633 SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) {
2634   SDOperand N0 = N->getOperand(0);
2635   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2636   MVT::ValueType VT = N->getValueType(0);
2637
2638   // fold (fp_round c1fp) -> c1fp
2639   if (N0CFP)
2640     return DAG.getNode(ISD::FP_ROUND, VT, N0);
2641
2642   // fold (fp_round (fp_extend x)) -> x
2643   if (N0.getOpcode() == ISD::FP_EXTEND && VT == N0.getOperand(0).getValueType())
2644     return N0.getOperand(0);
2645
2646   // fold (fp_round (copysign X, Y)) -> (copysign (fp_round X), Y)
2647   if (N0.getOpcode() == ISD::FCOPYSIGN && N0.Val->hasOneUse()) {
2648     SDOperand Tmp = DAG.getNode(ISD::FP_ROUND, VT, N0.getOperand(0));
2649     AddToWorkList(Tmp.Val);
2650     return DAG.getNode(ISD::FCOPYSIGN, VT, Tmp, N0.getOperand(1));
2651   }
2652
2653   return SDOperand();
2654 }
2655
2656 SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) {
2657   SDOperand N0 = N->getOperand(0);
2658   MVT::ValueType VT = N->getValueType(0);
2659   MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
2660   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2661
2662   // fold (fp_round_inreg c1fp) -> c1fp
2663   if (N0CFP) {
2664     SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT);
2665     return DAG.getNode(ISD::FP_EXTEND, VT, Round);
2666   }
2667   return SDOperand();
2668 }
2669
2670 SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) {
2671   SDOperand N0 = N->getOperand(0);
2672   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2673   MVT::ValueType VT = N->getValueType(0);
2674
2675   // fold (fp_extend c1fp) -> c1fp
2676   if (N0CFP)
2677     return DAG.getNode(ISD::FP_EXTEND, VT, N0);
2678
2679   // fold (fpext (load x)) -> (fpext (fpround (extload x)))
2680   if (ISD::isNON_EXTLoad(N0.Val) && N0.hasOneUse() &&
2681       (!AfterLegalize||TLI.isLoadXLegal(ISD::EXTLOAD, N0.getValueType()))) {
2682     LoadSDNode *LN0 = cast<LoadSDNode>(N0);
2683     SDOperand ExtLoad = DAG.getExtLoad(ISD::EXTLOAD, VT, LN0->getChain(),
2684                                        LN0->getBasePtr(), LN0->getSrcValue(),
2685                                        LN0->getSrcValueOffset(),
2686                                        N0.getValueType());
2687     CombineTo(N, ExtLoad);
2688     CombineTo(N0.Val, DAG.getNode(ISD::FP_ROUND, N0.getValueType(), ExtLoad),
2689               ExtLoad.getValue(1));
2690     return SDOperand(N, 0);   // Return N so it doesn't get rechecked!
2691   }
2692
2693
2694   return SDOperand();
2695 }
2696
2697 SDOperand DAGCombiner::visitFNEG(SDNode *N) {
2698   SDOperand N0 = N->getOperand(0);
2699   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2700   MVT::ValueType VT = N->getValueType(0);
2701
2702   // fold (fneg c1) -> -c1
2703   if (N0CFP)
2704     return DAG.getNode(ISD::FNEG, VT, N0);
2705   // fold (fneg (sub x, y)) -> (sub y, x)
2706   if (N0.getOpcode() == ISD::SUB)
2707     return DAG.getNode(ISD::SUB, VT, N0.getOperand(1), N0.getOperand(0));
2708   // fold (fneg (fneg x)) -> x
2709   if (N0.getOpcode() == ISD::FNEG)
2710     return N0.getOperand(0);
2711   return SDOperand();
2712 }
2713
2714 SDOperand DAGCombiner::visitFABS(SDNode *N) {
2715   SDOperand N0 = N->getOperand(0);
2716   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
2717   MVT::ValueType VT = N->getValueType(0);
2718
2719   // fold (fabs c1) -> fabs(c1)
2720   if (N0CFP)
2721     return DAG.getNode(ISD::FABS, VT, N0);
2722   // fold (fabs (fabs x)) -> (fabs x)
2723   if (N0.getOpcode() == ISD::FABS)
2724     return N->getOperand(0);
2725   // fold (fabs (fneg x)) -> (fabs x)
2726   // fold (fabs (fcopysign x, y)) -> (fabs x)
2727   if (N0.getOpcode() == ISD::FNEG || N0.getOpcode() == ISD::FCOPYSIGN)
2728     return DAG.getNode(ISD::FABS, VT, N0.getOperand(0));
2729
2730   return SDOperand();
2731 }
2732
2733 SDOperand DAGCombiner::visitBRCOND(SDNode *N) {
2734   SDOperand Chain = N->getOperand(0);
2735   SDOperand N1 = N->getOperand(1);
2736   SDOperand N2 = N->getOperand(2);
2737   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
2738
2739   // never taken branch, fold to chain
2740   if (N1C && N1C->isNullValue())
2741     return Chain;
2742   // unconditional branch
2743   if (N1C && N1C->getValue() == 1)
2744     return DAG.getNode(ISD::BR, MVT::Other, Chain, N2);
2745   // fold a brcond with a setcc condition into a BR_CC node if BR_CC is legal
2746   // on the target.
2747   if (N1.getOpcode() == ISD::SETCC &&
2748       TLI.isOperationLegal(ISD::BR_CC, MVT::Other)) {
2749     return DAG.getNode(ISD::BR_CC, MVT::Other, Chain, N1.getOperand(2),
2750                        N1.getOperand(0), N1.getOperand(1), N2);
2751   }
2752   return SDOperand();
2753 }
2754
2755 // Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB.
2756 //
2757 SDOperand DAGCombiner::visitBR_CC(SDNode *N) {
2758   CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1));
2759   SDOperand CondLHS = N->getOperand(2), CondRHS = N->getOperand(3);
2760
2761   // Use SimplifySetCC  to simplify SETCC's.
2762   SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false);
2763   if (Simp.Val) AddToWorkList(Simp.Val);
2764
2765   ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val);
2766
2767   // fold br_cc true, dest -> br dest (unconditional branch)
2768   if (SCCC && SCCC->getValue())
2769     return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0),
2770                        N->getOperand(4));
2771   // fold br_cc false, dest -> unconditional fall through
2772   if (SCCC && SCCC->isNullValue())
2773     return N->getOperand(0);
2774
2775   // fold to a simpler setcc
2776   if (Simp.Val && Simp.getOpcode() == ISD::SETCC)
2777     return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0),
2778                        Simp.getOperand(2), Simp.getOperand(0),
2779                        Simp.getOperand(1), N->getOperand(4));
2780   return SDOperand();
2781 }
2782
2783
2784 /// CombineToPreIndexedLoadStore - Try turning a load / store and a
2785 /// pre-indexed load / store when the base pointer is a add or subtract
2786 /// and it has other uses besides the load / store. After the
2787 /// transformation, the new indexed load / store has effectively folded
2788 /// the add / subtract in and all of its other uses are redirected to the
2789 /// new load / store.
2790 bool DAGCombiner::CombineToPreIndexedLoadStore(SDNode *N) {
2791   if (!AfterLegalize)
2792     return false;
2793
2794   bool isLoad = true;
2795   SDOperand Ptr;
2796   MVT::ValueType VT;
2797   if (LoadSDNode *LD  = dyn_cast<LoadSDNode>(N)) {
2798     if (LD->getAddressingMode() != ISD::UNINDEXED)
2799       return false;
2800     VT = LD->getLoadedVT();
2801     if (LD->getAddressingMode() != ISD::UNINDEXED &&
2802         !TLI.isIndexedLoadLegal(ISD::PRE_INC, VT) &&
2803         !TLI.isIndexedLoadLegal(ISD::PRE_DEC, VT))
2804       return false;
2805     Ptr = LD->getBasePtr();
2806   } else if (StoreSDNode *ST  = dyn_cast<StoreSDNode>(N)) {
2807     if (ST->getAddressingMode() != ISD::UNINDEXED)
2808       return false;
2809     VT = ST->getStoredVT();
2810     if (!TLI.isIndexedStoreLegal(ISD::PRE_INC, VT) &&
2811         !TLI.isIndexedStoreLegal(ISD::PRE_DEC, VT))
2812       return false;
2813     Ptr = ST->getBasePtr();
2814     isLoad = false;
2815   } else
2816     return false;
2817
2818   // If the pointer is not an add/sub, or if it doesn't have multiple uses, bail
2819   // out.  There is no reason to make this a preinc/predec.
2820   if ((Ptr.getOpcode() != ISD::ADD && Ptr.getOpcode() != ISD::SUB) ||
2821       Ptr.Val->hasOneUse())
2822     return false;
2823
2824   // Ask the target to do addressing mode selection.
2825   SDOperand BasePtr;
2826   SDOperand Offset;
2827   ISD::MemIndexedMode AM = ISD::UNINDEXED;
2828   if (!TLI.getPreIndexedAddressParts(N, BasePtr, Offset, AM, DAG))
2829     return false;
2830
2831   // Try turning it into a pre-indexed load / store except when:
2832   // 1) The base is a frame index.
2833   // 2) If N is a store and the ptr is either the same as or is a
2834   //    predecessor of the value being stored.
2835   // 3) Another use of base ptr is a predecessor of N. If ptr is folded
2836   //    that would create a cycle.
2837   // 4) All uses are load / store ops that use it as base ptr.
2838
2839   // Check #1.  Preinc'ing a frame index would require copying the stack pointer
2840   // (plus the implicit offset) to a register to preinc anyway.
2841   if (isa<FrameIndexSDNode>(BasePtr))
2842     return false;
2843
2844   // Check #2.
2845   if (!isLoad) {
2846     SDOperand Val = cast<StoreSDNode>(N)->getValue();
2847     if (Val == Ptr || Ptr.Val->isPredecessor(Val.Val))
2848       return false;
2849   }
2850
2851   // Now check for #2 and #3.
2852   bool RealUse = false;
2853   for (SDNode::use_iterator I = Ptr.Val->use_begin(),
2854          E = Ptr.Val->use_end(); I != E; ++I) {
2855     SDNode *Use = *I;
2856     if (Use == N)
2857       continue;
2858     if (Use->isPredecessor(N))
2859       return false;
2860
2861     if (!((Use->getOpcode() == ISD::LOAD &&
2862            cast<LoadSDNode>(Use)->getBasePtr() == Ptr) ||
2863           (Use->getOpcode() == ISD::STORE) &&
2864           cast<StoreSDNode>(Use)->getBasePtr() == Ptr))
2865       RealUse = true;
2866   }
2867   if (!RealUse)
2868     return false;
2869
2870   SDOperand Result;
2871   if (isLoad)
2872     Result = DAG.getIndexedLoad(SDOperand(N,0), BasePtr, Offset, AM);
2873   else
2874     Result = DAG.getIndexedStore(SDOperand(N,0), BasePtr, Offset, AM);
2875   ++PreIndexedNodes;
2876   ++NodesCombined;
2877   DOUT << "\nReplacing.4 "; DEBUG(N->dump());
2878   DOUT << "\nWith: "; DEBUG(Result.Val->dump(&DAG));
2879   DOUT << '\n';
2880   std::vector<SDNode*> NowDead;
2881   if (isLoad) {
2882     DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0),
2883                                   NowDead);
2884     DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2),
2885                                   NowDead);
2886   } else {
2887     DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1),
2888                                   NowDead);
2889   }
2890
2891   // Nodes can end up on the worklist more than once.  Make sure we do
2892   // not process a node that has been replaced.
2893   for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
2894     removeFromWorkList(NowDead[i]);
2895   // Finally, since the node is now dead, remove it from the graph.
2896   DAG.DeleteNode(N);
2897
2898   // Replace the uses of Ptr with uses of the updated base value.
2899   DAG.ReplaceAllUsesOfValueWith(Ptr, Result.getValue(isLoad ? 1 : 0),
2900                                 NowDead);
2901   removeFromWorkList(Ptr.Val);
2902   for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
2903     removeFromWorkList(NowDead[i]);
2904   DAG.DeleteNode(Ptr.Val);
2905
2906   return true;
2907 }
2908
2909 /// CombineToPostIndexedLoadStore - Try combine a load / store with a
2910 /// add / sub of the base pointer node into a post-indexed load / store.
2911 /// The transformation folded the add / subtract into the new indexed
2912 /// load / store effectively and all of its uses are redirected to the
2913 /// new load / store.
2914 bool DAGCombiner::CombineToPostIndexedLoadStore(SDNode *N) {
2915   if (!AfterLegalize)
2916     return false;
2917
2918   bool isLoad = true;
2919   SDOperand Ptr;
2920   MVT::ValueType VT;
2921   if (LoadSDNode *LD  = dyn_cast<LoadSDNode>(N)) {
2922     if (LD->getAddressingMode() != ISD::UNINDEXED)
2923       return false;
2924     VT = LD->getLoadedVT();
2925     if (!TLI.isIndexedLoadLegal(ISD::POST_INC, VT) &&
2926         !TLI.isIndexedLoadLegal(ISD::POST_DEC, VT))
2927       return false;
2928     Ptr = LD->getBasePtr();
2929   } else if (StoreSDNode *ST  = dyn_cast<StoreSDNode>(N)) {
2930     if (ST->getAddressingMode() != ISD::UNINDEXED)
2931       return false;
2932     VT = ST->getStoredVT();
2933     if (!TLI.isIndexedStoreLegal(ISD::POST_INC, VT) &&
2934         !TLI.isIndexedStoreLegal(ISD::POST_DEC, VT))
2935       return false;
2936     Ptr = ST->getBasePtr();
2937     isLoad = false;
2938   } else
2939     return false;
2940
2941   if (Ptr.Val->hasOneUse())
2942     return false;
2943
2944   for (SDNode::use_iterator I = Ptr.Val->use_begin(),
2945          E = Ptr.Val->use_end(); I != E; ++I) {
2946     SDNode *Op = *I;
2947     if (Op == N ||
2948         (Op->getOpcode() != ISD::ADD && Op->getOpcode() != ISD::SUB))
2949       continue;
2950
2951     SDOperand BasePtr;
2952     SDOperand Offset;
2953     ISD::MemIndexedMode AM = ISD::UNINDEXED;
2954     if (TLI.getPostIndexedAddressParts(N, Op, BasePtr, Offset, AM, DAG)) {
2955       if (Ptr == Offset)
2956         std::swap(BasePtr, Offset);
2957       if (Ptr != BasePtr)
2958         continue;
2959
2960       // Try turning it into a post-indexed load / store except when
2961       // 1) All uses are load / store ops that use it as base ptr.
2962       // 2) Op must be independent of N, i.e. Op is neither a predecessor
2963       //    nor a successor of N. Otherwise, if Op is folded that would
2964       //    create a cycle.
2965
2966       // Check for #1.
2967       bool TryNext = false;
2968       for (SDNode::use_iterator II = BasePtr.Val->use_begin(),
2969              EE = BasePtr.Val->use_end(); II != EE; ++II) {
2970         SDNode *Use = *II;
2971         if (Use == Ptr.Val)
2972           continue;
2973
2974         // If all the uses are load / store addresses, then don't do the
2975         // transformation.
2976         if (Use->getOpcode() == ISD::ADD || Use->getOpcode() == ISD::SUB){
2977           bool RealUse = false;
2978           for (SDNode::use_iterator III = Use->use_begin(),
2979                  EEE = Use->use_end(); III != EEE; ++III) {
2980             SDNode *UseUse = *III;
2981             if (!((UseUse->getOpcode() == ISD::LOAD &&
2982                    cast<LoadSDNode>(UseUse)->getBasePtr().Val == Use) ||
2983                   (UseUse->getOpcode() == ISD::STORE) &&
2984                   cast<StoreSDNode>(UseUse)->getBasePtr().Val == Use))
2985               RealUse = true;
2986           }
2987
2988           if (!RealUse) {
2989             TryNext = true;
2990             break;
2991           }
2992         }
2993       }
2994       if (TryNext)
2995         continue;
2996
2997       // Check for #2
2998       if (!Op->isPredecessor(N) && !N->isPredecessor(Op)) {
2999         SDOperand Result = isLoad
3000           ? DAG.getIndexedLoad(SDOperand(N,0), BasePtr, Offset, AM)
3001           : DAG.getIndexedStore(SDOperand(N,0), BasePtr, Offset, AM);
3002         ++PostIndexedNodes;
3003         ++NodesCombined;
3004         DOUT << "\nReplacing.5 "; DEBUG(N->dump());
3005         DOUT << "\nWith: "; DEBUG(Result.Val->dump(&DAG));
3006         DOUT << '\n';
3007         std::vector<SDNode*> NowDead;
3008         if (isLoad) {
3009           DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0),
3010                                         NowDead);
3011           DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2),
3012                                         NowDead);
3013         } else {
3014           DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(1),
3015                                         NowDead);
3016         }
3017
3018         // Nodes can end up on the worklist more than once.  Make sure we do
3019         // not process a node that has been replaced.
3020         for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
3021           removeFromWorkList(NowDead[i]);
3022         // Finally, since the node is now dead, remove it from the graph.
3023         DAG.DeleteNode(N);
3024
3025         // Replace the uses of Use with uses of the updated base value.
3026         DAG.ReplaceAllUsesOfValueWith(SDOperand(Op, 0),
3027                                       Result.getValue(isLoad ? 1 : 0),
3028                                       NowDead);
3029         removeFromWorkList(Op);
3030         for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
3031           removeFromWorkList(NowDead[i]);
3032         DAG.DeleteNode(Op);
3033
3034         return true;
3035       }
3036     }
3037   }
3038   return false;
3039 }
3040
3041
3042 SDOperand DAGCombiner::visitLOAD(SDNode *N) {
3043   LoadSDNode *LD  = cast<LoadSDNode>(N);
3044   SDOperand Chain = LD->getChain();
3045   SDOperand Ptr   = LD->getBasePtr();
3046
3047   // If there are no uses of the loaded value, change uses of the chain value
3048   // into uses of the chain input (i.e. delete the dead load).
3049   if (N->hasNUsesOfValue(0, 0))
3050     return CombineTo(N, DAG.getNode(ISD::UNDEF, N->getValueType(0)), Chain);
3051
3052   // If this load is directly stored, replace the load value with the stored
3053   // value.
3054   // TODO: Handle store large -> read small portion.
3055   // TODO: Handle TRUNCSTORE/LOADEXT
3056   if (LD->getExtensionType() == ISD::NON_EXTLOAD) {
3057     if (ISD::isNON_TRUNCStore(Chain.Val)) {
3058       StoreSDNode *PrevST = cast<StoreSDNode>(Chain);
3059       if (PrevST->getBasePtr() == Ptr &&
3060           PrevST->getValue().getValueType() == N->getValueType(0))
3061       return CombineTo(N, Chain.getOperand(1), Chain);
3062     }
3063   }
3064
3065   if (CombinerAA) {
3066     // Walk up chain skipping non-aliasing memory nodes.
3067     SDOperand BetterChain = FindBetterChain(N, Chain);
3068
3069     // If there is a better chain.
3070     if (Chain != BetterChain) {
3071       SDOperand ReplLoad;
3072
3073       // Replace the chain to void dependency.
3074       if (LD->getExtensionType() == ISD::NON_EXTLOAD) {
3075         ReplLoad = DAG.getLoad(N->getValueType(0), BetterChain, Ptr,
3076                               LD->getSrcValue(), LD->getSrcValueOffset());
3077       } else {
3078         ReplLoad = DAG.getExtLoad(LD->getExtensionType(),
3079                                   LD->getValueType(0),
3080                                   BetterChain, Ptr, LD->getSrcValue(),
3081                                   LD->getSrcValueOffset(),
3082                                   LD->getLoadedVT());
3083       }
3084
3085       // Create token factor to keep old chain connected.
3086       SDOperand Token = DAG.getNode(ISD::TokenFactor, MVT::Other,
3087                                     Chain, ReplLoad.getValue(1));
3088
3089       // Replace uses with load result and token factor. Don't add users
3090       // to work list.
3091       return CombineTo(N, ReplLoad.getValue(0), Token, false);
3092     }
3093   }
3094
3095   // Try transforming N to an indexed load.
3096   if (CombineToPreIndexedLoadStore(N) || CombineToPostIndexedLoadStore(N))
3097     return SDOperand(N, 0);
3098
3099   return SDOperand();
3100 }
3101
3102 SDOperand DAGCombiner::visitSTORE(SDNode *N) {
3103   StoreSDNode *ST  = cast<StoreSDNode>(N);
3104   SDOperand Chain = ST->getChain();
3105   SDOperand Value = ST->getValue();
3106   SDOperand Ptr   = ST->getBasePtr();
3107
3108   // If this is a store of a bit convert, store the input value.
3109   // FIXME: This needs to know that the resultant store does not need a
3110   // higher alignment than the original.
3111   if (0 && Value.getOpcode() == ISD::BIT_CONVERT) {
3112     return DAG.getStore(Chain, Value.getOperand(0), Ptr, ST->getSrcValue(),
3113                         ST->getSrcValueOffset());
3114   }
3115
3116   // Turn 'store float 1.0, Ptr' -> 'store int 0x12345678, Ptr'
3117   if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(Value)) {
3118     if (Value.getOpcode() != ISD::TargetConstantFP) {
3119       SDOperand Tmp;
3120       switch (CFP->getValueType(0)) {
3121       default: assert(0 && "Unknown FP type");
3122       case MVT::f32:
3123         if (!AfterLegalize || TLI.isTypeLegal(MVT::i32)) {
3124           Tmp = DAG.getConstant(FloatToBits(CFP->getValue()), MVT::i32);
3125           return DAG.getStore(Chain, Tmp, Ptr, ST->getSrcValue(),
3126                               ST->getSrcValueOffset());
3127         }
3128         break;
3129       case MVT::f64:
3130         if (!AfterLegalize || TLI.isTypeLegal(MVT::i64)) {
3131           Tmp = DAG.getConstant(DoubleToBits(CFP->getValue()), MVT::i64);
3132           return DAG.getStore(Chain, Tmp, Ptr, ST->getSrcValue(),
3133                               ST->getSrcValueOffset());
3134         } else if (TLI.isTypeLegal(MVT::i32)) {
3135           // Many FP stores are not make apparent until after legalize, e.g. for
3136           // argument passing.  Since this is so common, custom legalize the
3137           // 64-bit integer store into two 32-bit stores.
3138           uint64_t Val = DoubleToBits(CFP->getValue());
3139           SDOperand Lo = DAG.getConstant(Val & 0xFFFFFFFF, MVT::i32);
3140           SDOperand Hi = DAG.getConstant(Val >> 32, MVT::i32);
3141           if (!TLI.isLittleEndian()) std::swap(Lo, Hi);
3142
3143           SDOperand St0 = DAG.getStore(Chain, Lo, Ptr, ST->getSrcValue(),
3144                                        ST->getSrcValueOffset());
3145           Ptr = DAG.getNode(ISD::ADD, Ptr.getValueType(), Ptr,
3146                             DAG.getConstant(4, Ptr.getValueType()));
3147           SDOperand St1 = DAG.getStore(Chain, Hi, Ptr, ST->getSrcValue(),
3148                                        ST->getSrcValueOffset()+4);
3149           return DAG.getNode(ISD::TokenFactor, MVT::Other, St0, St1);
3150         }
3151         break;
3152       }
3153     }
3154   }
3155
3156   if (CombinerAA) {
3157     // Walk up chain skipping non-aliasing memory nodes.
3158     SDOperand BetterChain = FindBetterChain(N, Chain);
3159
3160     // If there is a better chain.
3161     if (Chain != BetterChain) {
3162       // Replace the chain to avoid dependency.
3163       SDOperand ReplStore;
3164       if (ST->isTruncatingStore()) {
3165         ReplStore = DAG.getTruncStore(BetterChain, Value, Ptr,
3166           ST->getSrcValue(),ST->getSrcValueOffset(), ST->getStoredVT());
3167       } else {
3168         ReplStore = DAG.getStore(BetterChain, Value, Ptr,
3169           ST->getSrcValue(), ST->getSrcValueOffset());
3170       }
3171
3172       // Create token to keep both nodes around.
3173       SDOperand Token =
3174         DAG.getNode(ISD::TokenFactor, MVT::Other, Chain, ReplStore);
3175
3176       // Don't add users to work list.
3177       return CombineTo(N, Token, false);
3178     }
3179   }
3180
3181   // Try transforming N to an indexed store.
3182   if (CombineToPreIndexedLoadStore(N) || CombineToPostIndexedLoadStore(N))
3183     return SDOperand(N, 0);
3184
3185   return SDOperand();
3186 }
3187
3188 SDOperand DAGCombiner::visitINSERT_VECTOR_ELT(SDNode *N) {
3189   SDOperand InVec = N->getOperand(0);
3190   SDOperand InVal = N->getOperand(1);
3191   SDOperand EltNo = N->getOperand(2);
3192
3193   // If the invec is a BUILD_VECTOR and if EltNo is a constant, build a new
3194   // vector with the inserted element.
3195   if (InVec.getOpcode() == ISD::BUILD_VECTOR && isa<ConstantSDNode>(EltNo)) {
3196     unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue();
3197     SmallVector<SDOperand, 8> Ops(InVec.Val->op_begin(), InVec.Val->op_end());
3198     if (Elt < Ops.size())
3199       Ops[Elt] = InVal;
3200     return DAG.getNode(ISD::BUILD_VECTOR, InVec.getValueType(),
3201                        &Ops[0], Ops.size());
3202   }
3203
3204   return SDOperand();
3205 }
3206
3207 SDOperand DAGCombiner::visitVINSERT_VECTOR_ELT(SDNode *N) {
3208   SDOperand InVec = N->getOperand(0);
3209   SDOperand InVal = N->getOperand(1);
3210   SDOperand EltNo = N->getOperand(2);
3211   SDOperand NumElts = N->getOperand(3);
3212   SDOperand EltType = N->getOperand(4);
3213
3214   // If the invec is a VBUILD_VECTOR and if EltNo is a constant, build a new
3215   // vector with the inserted element.
3216   if (InVec.getOpcode() == ISD::VBUILD_VECTOR && isa<ConstantSDNode>(EltNo)) {
3217     unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue();
3218     SmallVector<SDOperand, 8> Ops(InVec.Val->op_begin(), InVec.Val->op_end());
3219     if (Elt < Ops.size()-2)
3220       Ops[Elt] = InVal;
3221     return DAG.getNode(ISD::VBUILD_VECTOR, InVec.getValueType(),
3222                        &Ops[0], Ops.size());
3223   }
3224
3225   return SDOperand();
3226 }
3227
3228 SDOperand DAGCombiner::visitVBUILD_VECTOR(SDNode *N) {
3229   unsigned NumInScalars = N->getNumOperands()-2;
3230   SDOperand NumElts = N->getOperand(NumInScalars);
3231   SDOperand EltType = N->getOperand(NumInScalars+1);
3232
3233   // Check to see if this is a VBUILD_VECTOR of a bunch of VEXTRACT_VECTOR_ELT
3234   // operations.  If so, and if the EXTRACT_ELT vector inputs come from at most
3235   // two distinct vectors, turn this into a shuffle node.
3236   SDOperand VecIn1, VecIn2;
3237   for (unsigned i = 0; i != NumInScalars; ++i) {
3238     // Ignore undef inputs.
3239     if (N->getOperand(i).getOpcode() == ISD::UNDEF) continue;
3240
3241     // If this input is something other than a VEXTRACT_VECTOR_ELT with a
3242     // constant index, bail out.
3243     if (N->getOperand(i).getOpcode() != ISD::VEXTRACT_VECTOR_ELT ||
3244         !isa<ConstantSDNode>(N->getOperand(i).getOperand(1))) {
3245       VecIn1 = VecIn2 = SDOperand(0, 0);
3246       break;
3247     }
3248
3249     // If the input vector type disagrees with the result of the vbuild_vector,
3250     // we can't make a shuffle.
3251     SDOperand ExtractedFromVec = N->getOperand(i).getOperand(0);
3252     if (*(ExtractedFromVec.Val->op_end()-2) != NumElts ||
3253         *(ExtractedFromVec.Val->op_end()-1) != EltType) {
3254       VecIn1 = VecIn2 = SDOperand(0, 0);
3255       break;
3256     }
3257
3258     // Otherwise, remember this.  We allow up to two distinct input vectors.
3259     if (ExtractedFromVec == VecIn1 || ExtractedFromVec == VecIn2)
3260       continue;
3261
3262     if (VecIn1.Val == 0) {
3263       VecIn1 = ExtractedFromVec;
3264     } else if (VecIn2.Val == 0) {
3265       VecIn2 = ExtractedFromVec;
3266     } else {
3267       // Too many inputs.
3268       VecIn1 = VecIn2 = SDOperand(0, 0);
3269       break;
3270     }
3271   }
3272
3273   // If everything is good, we can make a shuffle operation.
3274   if (VecIn1.Val) {
3275     SmallVector<SDOperand, 8> BuildVecIndices;
3276     for (unsigned i = 0; i != NumInScalars; ++i) {
3277       if (N->getOperand(i).getOpcode() == ISD::UNDEF) {
3278         BuildVecIndices.push_back(DAG.getNode(ISD::UNDEF, TLI.getPointerTy()));
3279         continue;
3280       }
3281
3282       SDOperand Extract = N->getOperand(i);
3283
3284       // If extracting from the first vector, just use the index directly.
3285       if (Extract.getOperand(0) == VecIn1) {
3286         BuildVecIndices.push_back(Extract.getOperand(1));
3287         continue;
3288       }
3289
3290       // Otherwise, use InIdx + VecSize
3291       unsigned Idx = cast<ConstantSDNode>(Extract.getOperand(1))->getValue();
3292       BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars,
3293                                                 TLI.getPointerTy()));
3294     }
3295
3296     // Add count and size info.
3297     BuildVecIndices.push_back(NumElts);
3298     BuildVecIndices.push_back(DAG.getValueType(TLI.getPointerTy()));
3299
3300     // Return the new VVECTOR_SHUFFLE node.
3301     SDOperand Ops[5];
3302     Ops[0] = VecIn1;
3303     if (VecIn2.Val) {
3304       Ops[1] = VecIn2;
3305     } else {
3306        // Use an undef vbuild_vector as input for the second operand.
3307       std::vector<SDOperand> UnOps(NumInScalars,
3308                                    DAG.getNode(ISD::UNDEF,
3309                                            cast<VTSDNode>(EltType)->getVT()));
3310       UnOps.push_back(NumElts);
3311       UnOps.push_back(EltType);
3312       Ops[1] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
3313                            &UnOps[0], UnOps.size());
3314       AddToWorkList(Ops[1].Val);
3315     }
3316     Ops[2] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
3317                          &BuildVecIndices[0], BuildVecIndices.size());
3318     Ops[3] = NumElts;
3319     Ops[4] = EltType;
3320     return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, Ops, 5);
3321   }
3322
3323   return SDOperand();
3324 }
3325
3326 SDOperand DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) {
3327   SDOperand ShufMask = N->getOperand(2);
3328   unsigned NumElts = ShufMask.getNumOperands();
3329
3330   // If the shuffle mask is an identity operation on the LHS, return the LHS.
3331   bool isIdentity = true;
3332   for (unsigned i = 0; i != NumElts; ++i) {
3333     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
3334         cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) {
3335       isIdentity = false;
3336       break;
3337     }
3338   }
3339   if (isIdentity) return N->getOperand(0);
3340
3341   // If the shuffle mask is an identity operation on the RHS, return the RHS.
3342   isIdentity = true;
3343   for (unsigned i = 0; i != NumElts; ++i) {
3344     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
3345         cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) {
3346       isIdentity = false;
3347       break;
3348     }
3349   }
3350   if (isIdentity) return N->getOperand(1);
3351
3352   // Check if the shuffle is a unary shuffle, i.e. one of the vectors is not
3353   // needed at all.
3354   bool isUnary = true;
3355   bool isSplat = true;
3356   int VecNum = -1;
3357   unsigned BaseIdx = 0;
3358   for (unsigned i = 0; i != NumElts; ++i)
3359     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF) {
3360       unsigned Idx = cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue();
3361       int V = (Idx < NumElts) ? 0 : 1;
3362       if (VecNum == -1) {
3363         VecNum = V;
3364         BaseIdx = Idx;
3365       } else {
3366         if (BaseIdx != Idx)
3367           isSplat = false;
3368         if (VecNum != V) {
3369           isUnary = false;
3370           break;
3371         }
3372       }
3373     }
3374
3375   SDOperand N0 = N->getOperand(0);
3376   SDOperand N1 = N->getOperand(1);
3377   // Normalize unary shuffle so the RHS is undef.
3378   if (isUnary && VecNum == 1)
3379     std::swap(N0, N1);
3380
3381   // If it is a splat, check if the argument vector is a build_vector with
3382   // all scalar elements the same.
3383   if (isSplat) {
3384     SDNode *V = N0.Val;
3385     if (V->getOpcode() == ISD::BIT_CONVERT)
3386       V = V->getOperand(0).Val;
3387     if (V->getOpcode() == ISD::BUILD_VECTOR) {
3388       unsigned NumElems = V->getNumOperands()-2;
3389       if (NumElems > BaseIdx) {
3390         SDOperand Base;
3391         bool AllSame = true;
3392         for (unsigned i = 0; i != NumElems; ++i) {
3393           if (V->getOperand(i).getOpcode() != ISD::UNDEF) {
3394             Base = V->getOperand(i);
3395             break;
3396           }
3397         }
3398         // Splat of <u, u, u, u>, return <u, u, u, u>
3399         if (!Base.Val)
3400           return N0;
3401         for (unsigned i = 0; i != NumElems; ++i) {
3402           if (V->getOperand(i).getOpcode() != ISD::UNDEF &&
3403               V->getOperand(i) != Base) {
3404             AllSame = false;
3405             break;
3406           }
3407         }
3408         // Splat of <x, x, x, x>, return <x, x, x, x>
3409         if (AllSame)
3410           return N0;
3411       }
3412     }
3413   }
3414
3415   // If it is a unary or the LHS and the RHS are the same node, turn the RHS
3416   // into an undef.
3417   if (isUnary || N0 == N1) {
3418     if (N0.getOpcode() == ISD::UNDEF)
3419       return DAG.getNode(ISD::UNDEF, N->getValueType(0));
3420     // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the
3421     // first operand.
3422     SmallVector<SDOperand, 8> MappedOps;
3423     for (unsigned i = 0, e = ShufMask.getNumOperands(); i != e; ++i) {
3424       if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF ||
3425           cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) {
3426         MappedOps.push_back(ShufMask.getOperand(i));
3427       } else {
3428         unsigned NewIdx =
3429            cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts;
3430         MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32));
3431       }
3432     }
3433     ShufMask = DAG.getNode(ISD::BUILD_VECTOR, ShufMask.getValueType(),
3434                            &MappedOps[0], MappedOps.size());
3435     AddToWorkList(ShufMask.Val);
3436     return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getValueType(0),
3437                        N0,
3438                        DAG.getNode(ISD::UNDEF, N->getValueType(0)),
3439                        ShufMask);
3440   }
3441
3442   return SDOperand();
3443 }
3444
3445 SDOperand DAGCombiner::visitVVECTOR_SHUFFLE(SDNode *N) {
3446   SDOperand ShufMask = N->getOperand(2);
3447   unsigned NumElts = ShufMask.getNumOperands()-2;
3448
3449   // If the shuffle mask is an identity operation on the LHS, return the LHS.
3450   bool isIdentity = true;
3451   for (unsigned i = 0; i != NumElts; ++i) {
3452     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
3453         cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) {
3454       isIdentity = false;
3455       break;
3456     }
3457   }
3458   if (isIdentity) return N->getOperand(0);
3459
3460   // If the shuffle mask is an identity operation on the RHS, return the RHS.
3461   isIdentity = true;
3462   for (unsigned i = 0; i != NumElts; ++i) {
3463     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
3464         cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) {
3465       isIdentity = false;
3466       break;
3467     }
3468   }
3469   if (isIdentity) return N->getOperand(1);
3470
3471   // Check if the shuffle is a unary shuffle, i.e. one of the vectors is not
3472   // needed at all.
3473   bool isUnary = true;
3474   bool isSplat = true;
3475   int VecNum = -1;
3476   unsigned BaseIdx = 0;
3477   for (unsigned i = 0; i != NumElts; ++i)
3478     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF) {
3479       unsigned Idx = cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue();
3480       int V = (Idx < NumElts) ? 0 : 1;
3481       if (VecNum == -1) {
3482         VecNum = V;
3483         BaseIdx = Idx;
3484       } else {
3485         if (BaseIdx != Idx)
3486           isSplat = false;
3487         if (VecNum != V) {
3488           isUnary = false;
3489           break;
3490         }
3491       }
3492     }
3493
3494   SDOperand N0 = N->getOperand(0);
3495   SDOperand N1 = N->getOperand(1);
3496   // Normalize unary shuffle so the RHS is undef.
3497   if (isUnary && VecNum == 1)
3498     std::swap(N0, N1);
3499
3500   // If it is a splat, check if the argument vector is a build_vector with
3501   // all scalar elements the same.
3502   if (isSplat) {
3503     SDNode *V = N0.Val;
3504
3505     // If this is a vbit convert that changes the element type of the vector but
3506     // not the number of vector elements, look through it.  Be careful not to
3507     // look though conversions that change things like v4f32 to v2f64.
3508     if (V->getOpcode() == ISD::VBIT_CONVERT) {
3509       SDOperand ConvInput = V->getOperand(0);
3510       if (ConvInput.getValueType() == MVT::Vector &&
3511           NumElts ==
3512           ConvInput.getConstantOperandVal(ConvInput.getNumOperands()-2))
3513         V = ConvInput.Val;
3514     }
3515
3516     if (V->getOpcode() == ISD::VBUILD_VECTOR) {
3517       unsigned NumElems = V->getNumOperands()-2;
3518       if (NumElems > BaseIdx) {
3519         SDOperand Base;
3520         bool AllSame = true;
3521         for (unsigned i = 0; i != NumElems; ++i) {
3522           if (V->getOperand(i).getOpcode() != ISD::UNDEF) {
3523             Base = V->getOperand(i);
3524             break;
3525           }
3526         }
3527         // Splat of <u, u, u, u>, return <u, u, u, u>
3528         if (!Base.Val)
3529           return N0;
3530         for (unsigned i = 0; i != NumElems; ++i) {
3531           if (V->getOperand(i).getOpcode() != ISD::UNDEF &&
3532               V->getOperand(i) != Base) {
3533             AllSame = false;
3534             break;
3535           }
3536         }
3537         // Splat of <x, x, x, x>, return <x, x, x, x>
3538         if (AllSame)
3539           return N0;
3540       }
3541     }
3542   }
3543
3544   // If it is a unary or the LHS and the RHS are the same node, turn the RHS
3545   // into an undef.
3546   if (isUnary || N0 == N1) {
3547     // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the
3548     // first operand.
3549     SmallVector<SDOperand, 8> MappedOps;
3550     for (unsigned i = 0; i != NumElts; ++i) {
3551       if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF ||
3552           cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) {
3553         MappedOps.push_back(ShufMask.getOperand(i));
3554       } else {
3555         unsigned NewIdx =
3556           cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts;
3557         MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32));
3558       }
3559     }
3560     // Add the type/#elts values.
3561     MappedOps.push_back(ShufMask.getOperand(NumElts));
3562     MappedOps.push_back(ShufMask.getOperand(NumElts+1));
3563
3564     ShufMask = DAG.getNode(ISD::VBUILD_VECTOR, ShufMask.getValueType(),
3565                            &MappedOps[0], MappedOps.size());
3566     AddToWorkList(ShufMask.Val);
3567
3568     // Build the undef vector.
3569     SDOperand UDVal = DAG.getNode(ISD::UNDEF, MappedOps[0].getValueType());
3570     for (unsigned i = 0; i != NumElts; ++i)
3571       MappedOps[i] = UDVal;
3572     MappedOps[NumElts  ] = *(N0.Val->op_end()-2);
3573     MappedOps[NumElts+1] = *(N0.Val->op_end()-1);
3574     UDVal = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
3575                         &MappedOps[0], MappedOps.size());
3576
3577     return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
3578                        N0, UDVal, ShufMask,
3579                        MappedOps[NumElts], MappedOps[NumElts+1]);
3580   }
3581
3582   return SDOperand();
3583 }
3584
3585 /// XformToShuffleWithZero - Returns a vector_shuffle if it able to transform
3586 /// a VAND to a vector_shuffle with the destination vector and a zero vector.
3587 /// e.g. VAND V, <0xffffffff, 0, 0xffffffff, 0>. ==>
3588 ///      vector_shuffle V, Zero, <0, 4, 2, 4>
3589 SDOperand DAGCombiner::XformToShuffleWithZero(SDNode *N) {
3590   SDOperand LHS = N->getOperand(0);
3591   SDOperand RHS = N->getOperand(1);
3592   if (N->getOpcode() == ISD::VAND) {
3593     SDOperand DstVecSize = *(LHS.Val->op_end()-2);
3594     SDOperand DstVecEVT  = *(LHS.Val->op_end()-1);
3595     if (RHS.getOpcode() == ISD::VBIT_CONVERT)
3596       RHS = RHS.getOperand(0);
3597     if (RHS.getOpcode() == ISD::VBUILD_VECTOR) {
3598       std::vector<SDOperand> IdxOps;
3599       unsigned NumOps = RHS.getNumOperands();
3600       unsigned NumElts = NumOps-2;
3601       MVT::ValueType EVT = cast<VTSDNode>(RHS.getOperand(NumOps-1))->getVT();
3602       for (unsigned i = 0; i != NumElts; ++i) {
3603         SDOperand Elt = RHS.getOperand(i);
3604         if (!isa<ConstantSDNode>(Elt))
3605           return SDOperand();
3606         else if (cast<ConstantSDNode>(Elt)->isAllOnesValue())
3607           IdxOps.push_back(DAG.getConstant(i, EVT));
3608         else if (cast<ConstantSDNode>(Elt)->isNullValue())
3609           IdxOps.push_back(DAG.getConstant(NumElts, EVT));
3610         else
3611           return SDOperand();
3612       }
3613
3614       // Let's see if the target supports this vector_shuffle.
3615       if (!TLI.isVectorClearMaskLegal(IdxOps, EVT, DAG))
3616         return SDOperand();
3617
3618       // Return the new VVECTOR_SHUFFLE node.
3619       SDOperand NumEltsNode = DAG.getConstant(NumElts, MVT::i32);
3620       SDOperand EVTNode = DAG.getValueType(EVT);
3621       std::vector<SDOperand> Ops;
3622       LHS = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, LHS, NumEltsNode,
3623                         EVTNode);
3624       Ops.push_back(LHS);
3625       AddToWorkList(LHS.Val);
3626       std::vector<SDOperand> ZeroOps(NumElts, DAG.getConstant(0, EVT));
3627       ZeroOps.push_back(NumEltsNode);
3628       ZeroOps.push_back(EVTNode);
3629       Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
3630                                 &ZeroOps[0], ZeroOps.size()));
3631       IdxOps.push_back(NumEltsNode);
3632       IdxOps.push_back(EVTNode);
3633       Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
3634                                 &IdxOps[0], IdxOps.size()));
3635       Ops.push_back(NumEltsNode);
3636       Ops.push_back(EVTNode);
3637       SDOperand Result = DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
3638                                      &Ops[0], Ops.size());
3639       if (NumEltsNode != DstVecSize || EVTNode != DstVecEVT) {
3640         Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result,
3641                              DstVecSize, DstVecEVT);
3642       }
3643       return Result;
3644     }
3645   }
3646   return SDOperand();
3647 }
3648
3649 /// visitVBinOp - Visit a binary vector operation, like VADD.  IntOp indicates
3650 /// the scalar operation of the vop if it is operating on an integer vector
3651 /// (e.g. ADD) and FPOp indicates the FP version (e.g. FADD).
3652 SDOperand DAGCombiner::visitVBinOp(SDNode *N, ISD::NodeType IntOp,
3653                                    ISD::NodeType FPOp) {
3654   MVT::ValueType EltType = cast<VTSDNode>(*(N->op_end()-1))->getVT();
3655   ISD::NodeType ScalarOp = MVT::isInteger(EltType) ? IntOp : FPOp;
3656   SDOperand LHS = N->getOperand(0);
3657   SDOperand RHS = N->getOperand(1);
3658   SDOperand Shuffle = XformToShuffleWithZero(N);
3659   if (Shuffle.Val) return Shuffle;
3660
3661   // If the LHS and RHS are VBUILD_VECTOR nodes, see if we can constant fold
3662   // this operation.
3663   if (LHS.getOpcode() == ISD::VBUILD_VECTOR &&
3664       RHS.getOpcode() == ISD::VBUILD_VECTOR) {
3665     SmallVector<SDOperand, 8> Ops;
3666     for (unsigned i = 0, e = LHS.getNumOperands()-2; i != e; ++i) {
3667       SDOperand LHSOp = LHS.getOperand(i);
3668       SDOperand RHSOp = RHS.getOperand(i);
3669       // If these two elements can't be folded, bail out.
3670       if ((LHSOp.getOpcode() != ISD::UNDEF &&
3671            LHSOp.getOpcode() != ISD::Constant &&
3672            LHSOp.getOpcode() != ISD::ConstantFP) ||
3673           (RHSOp.getOpcode() != ISD::UNDEF &&
3674            RHSOp.getOpcode() != ISD::Constant &&
3675            RHSOp.getOpcode() != ISD::ConstantFP))
3676         break;
3677       // Can't fold divide by zero.
3678       if (N->getOpcode() == ISD::VSDIV || N->getOpcode() == ISD::VUDIV) {
3679         if ((RHSOp.getOpcode() == ISD::Constant &&
3680              cast<ConstantSDNode>(RHSOp.Val)->isNullValue()) ||
3681             (RHSOp.getOpcode() == ISD::ConstantFP &&
3682              !cast<ConstantFPSDNode>(RHSOp.Val)->getValue()))
3683           break;
3684       }
3685       Ops.push_back(DAG.getNode(ScalarOp, EltType, LHSOp, RHSOp));
3686       AddToWorkList(Ops.back().Val);
3687       assert((Ops.back().getOpcode() == ISD::UNDEF ||
3688               Ops.back().getOpcode() == ISD::Constant ||
3689               Ops.back().getOpcode() == ISD::ConstantFP) &&
3690              "Scalar binop didn't fold!");
3691     }
3692
3693     if (Ops.size() == LHS.getNumOperands()-2) {
3694       Ops.push_back(*(LHS.Val->op_end()-2));
3695       Ops.push_back(*(LHS.Val->op_end()-1));
3696       return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
3697     }
3698   }
3699
3700   return SDOperand();
3701 }
3702
3703 SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){
3704   assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!");
3705
3706   SDOperand SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2,
3707                                  cast<CondCodeSDNode>(N0.getOperand(2))->get());
3708   // If we got a simplified select_cc node back from SimplifySelectCC, then
3709   // break it down into a new SETCC node, and a new SELECT node, and then return
3710   // the SELECT node, since we were called with a SELECT node.
3711   if (SCC.Val) {
3712     // Check to see if we got a select_cc back (to turn into setcc/select).
3713     // Otherwise, just return whatever node we got back, like fabs.
3714     if (SCC.getOpcode() == ISD::SELECT_CC) {
3715       SDOperand SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(),
3716                                     SCC.getOperand(0), SCC.getOperand(1),
3717                                     SCC.getOperand(4));
3718       AddToWorkList(SETCC.Val);
3719       return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2),
3720                          SCC.getOperand(3), SETCC);
3721     }
3722     return SCC;
3723   }
3724   return SDOperand();
3725 }
3726
3727 /// SimplifySelectOps - Given a SELECT or a SELECT_CC node, where LHS and RHS
3728 /// are the two values being selected between, see if we can simplify the
3729 /// select.  Callers of this should assume that TheSelect is deleted if this
3730 /// returns true.  As such, they should return the appropriate thing (e.g. the
3731 /// node) back to the top-level of the DAG combiner loop to avoid it being
3732 /// looked at.
3733 ///
3734 bool DAGCombiner::SimplifySelectOps(SDNode *TheSelect, SDOperand LHS,
3735                                     SDOperand RHS) {
3736
3737   // If this is a select from two identical things, try to pull the operation
3738   // through the select.
3739   if (LHS.getOpcode() == RHS.getOpcode() && LHS.hasOneUse() && RHS.hasOneUse()){
3740     // If this is a load and the token chain is identical, replace the select
3741     // of two loads with a load through a select of the address to load from.
3742     // This triggers in things like "select bool X, 10.0, 123.0" after the FP
3743     // constants have been dropped into the constant pool.
3744     if (LHS.getOpcode() == ISD::LOAD &&
3745         // Token chains must be identical.
3746         LHS.getOperand(0) == RHS.getOperand(0)) {
3747       LoadSDNode *LLD = cast<LoadSDNode>(LHS);
3748       LoadSDNode *RLD = cast<LoadSDNode>(RHS);
3749
3750       // If this is an EXTLOAD, the VT's must match.
3751       if (LLD->getLoadedVT() == RLD->getLoadedVT()) {
3752         // FIXME: this conflates two src values, discarding one.  This is not
3753         // the right thing to do, but nothing uses srcvalues now.  When they do,
3754         // turn SrcValue into a list of locations.
3755         SDOperand Addr;
3756         if (TheSelect->getOpcode() == ISD::SELECT) {
3757           // Check that the condition doesn't reach either load.  If so, folding
3758           // this will induce a cycle into the DAG.
3759           if (!LLD->isPredecessor(TheSelect->getOperand(0).Val) &&
3760               !RLD->isPredecessor(TheSelect->getOperand(0).Val)) {
3761             Addr = DAG.getNode(ISD::SELECT, LLD->getBasePtr().getValueType(),
3762                                TheSelect->getOperand(0), LLD->getBasePtr(),
3763                                RLD->getBasePtr());
3764           }
3765         } else {
3766           // Check that the condition doesn't reach either load.  If so, folding
3767           // this will induce a cycle into the DAG.
3768           if (!LLD->isPredecessor(TheSelect->getOperand(0).Val) &&
3769               !RLD->isPredecessor(TheSelect->getOperand(0).Val) &&
3770               !LLD->isPredecessor(TheSelect->getOperand(1).Val) &&
3771               !RLD->isPredecessor(TheSelect->getOperand(1).Val)) {
3772             Addr = DAG.getNode(ISD::SELECT_CC, LLD->getBasePtr().getValueType(),
3773                              TheSelect->getOperand(0),
3774                              TheSelect->getOperand(1),
3775                              LLD->getBasePtr(), RLD->getBasePtr(),
3776                              TheSelect->getOperand(4));
3777           }
3778         }
3779
3780         if (Addr.Val) {
3781           SDOperand Load;
3782           if (LLD->getExtensionType() == ISD::NON_EXTLOAD)
3783             Load = DAG.getLoad(TheSelect->getValueType(0), LLD->getChain(),
3784                                Addr,LLD->getSrcValue(),
3785                                LLD->getSrcValueOffset());
3786           else {
3787             Load = DAG.getExtLoad(LLD->getExtensionType(),
3788                                   TheSelect->getValueType(0),
3789                                   LLD->getChain(), Addr, LLD->getSrcValue(),
3790                                   LLD->getSrcValueOffset(),
3791                                   LLD->getLoadedVT());
3792           }
3793           // Users of the select now use the result of the load.
3794           CombineTo(TheSelect, Load);
3795
3796           // Users of the old loads now use the new load's chain.  We know the
3797           // old-load value is dead now.
3798           CombineTo(LHS.Val, Load.getValue(0), Load.getValue(1));
3799           CombineTo(RHS.Val, Load.getValue(0), Load.getValue(1));
3800           return true;
3801         }
3802       }
3803     }
3804   }
3805
3806   return false;
3807 }
3808
3809 SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1,
3810                                         SDOperand N2, SDOperand N3,
3811                                         ISD::CondCode CC) {
3812
3813   MVT::ValueType VT = N2.getValueType();
3814   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
3815   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
3816   ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
3817
3818   // Determine if the condition we're dealing with is constant
3819   SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
3820   if (SCC.Val) AddToWorkList(SCC.Val);
3821   ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
3822
3823   // fold select_cc true, x, y -> x
3824   if (SCCC && SCCC->getValue())
3825     return N2;
3826   // fold select_cc false, x, y -> y
3827   if (SCCC && SCCC->getValue() == 0)
3828     return N3;
3829
3830   // Check to see if we can simplify the select into an fabs node
3831   if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) {
3832     // Allow either -0.0 or 0.0
3833     if (CFP->getValue() == 0.0) {
3834       // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs
3835       if ((CC == ISD::SETGE || CC == ISD::SETGT) &&
3836           N0 == N2 && N3.getOpcode() == ISD::FNEG &&
3837           N2 == N3.getOperand(0))
3838         return DAG.getNode(ISD::FABS, VT, N0);
3839
3840       // select (setl[te] X, +/-0.0), fneg(X), X -> fabs
3841       if ((CC == ISD::SETLT || CC == ISD::SETLE) &&
3842           N0 == N3 && N2.getOpcode() == ISD::FNEG &&
3843           N2.getOperand(0) == N3)
3844         return DAG.getNode(ISD::FABS, VT, N3);
3845     }
3846   }
3847
3848   // Check to see if we can perform the "gzip trick", transforming
3849   // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A
3850   if (N1C && N3C && N3C->isNullValue() && CC == ISD::SETLT &&
3851       MVT::isInteger(N0.getValueType()) &&
3852       MVT::isInteger(N2.getValueType()) &&
3853       (N1C->isNullValue() ||                    // (a < 0) ? b : 0
3854        (N1C->getValue() == 1 && N0 == N2))) {   // (a < 1) ? a : 0
3855     MVT::ValueType XType = N0.getValueType();
3856     MVT::ValueType AType = N2.getValueType();
3857     if (XType >= AType) {
3858       // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a
3859       // single-bit constant.
3860       if (N2C && ((N2C->getValue() & (N2C->getValue()-1)) == 0)) {
3861         unsigned ShCtV = Log2_64(N2C->getValue());
3862         ShCtV = MVT::getSizeInBits(XType)-ShCtV-1;
3863         SDOperand ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy());
3864         SDOperand Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt);
3865         AddToWorkList(Shift.Val);
3866         if (XType > AType) {
3867           Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift);
3868           AddToWorkList(Shift.Val);
3869         }
3870         return DAG.getNode(ISD::AND, AType, Shift, N2);
3871       }
3872       SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
3873                                     DAG.getConstant(MVT::getSizeInBits(XType)-1,
3874                                                     TLI.getShiftAmountTy()));
3875       AddToWorkList(Shift.Val);
3876       if (XType > AType) {
3877         Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift);
3878         AddToWorkList(Shift.Val);
3879       }
3880       return DAG.getNode(ISD::AND, AType, Shift, N2);
3881     }
3882   }
3883
3884   // fold select C, 16, 0 -> shl C, 4
3885   if (N2C && N3C && N3C->isNullValue() && isPowerOf2_64(N2C->getValue()) &&
3886       TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) {
3887     // Get a SetCC of the condition
3888     // FIXME: Should probably make sure that setcc is legal if we ever have a
3889     // target where it isn't.
3890     SDOperand Temp, SCC;
3891     // cast from setcc result type to select result type
3892     if (AfterLegalize) {
3893       SCC  = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC);
3894       if (N2.getValueType() < SCC.getValueType())
3895         Temp = DAG.getZeroExtendInReg(SCC, N2.getValueType());
3896       else
3897         Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC);
3898     } else {
3899       SCC  = DAG.getSetCC(MVT::i1, N0, N1, CC);
3900       Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC);
3901     }
3902     AddToWorkList(SCC.Val);
3903     AddToWorkList(Temp.Val);
3904     // shl setcc result by log2 n2c
3905     return DAG.getNode(ISD::SHL, N2.getValueType(), Temp,
3906                        DAG.getConstant(Log2_64(N2C->getValue()),
3907                                        TLI.getShiftAmountTy()));
3908   }
3909
3910   // Check to see if this is the equivalent of setcc
3911   // FIXME: Turn all of these into setcc if setcc if setcc is legal
3912   // otherwise, go ahead with the folds.
3913   if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getValue() == 1ULL)) {
3914     MVT::ValueType XType = N0.getValueType();
3915     if (TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultTy())) {
3916       SDOperand Res = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC);
3917       if (Res.getValueType() != VT)
3918         Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res);
3919       return Res;
3920     }
3921
3922     // seteq X, 0 -> srl (ctlz X, log2(size(X)))
3923     if (N1C && N1C->isNullValue() && CC == ISD::SETEQ &&
3924         TLI.isOperationLegal(ISD::CTLZ, XType)) {
3925       SDOperand Ctlz = DAG.getNode(ISD::CTLZ, XType, N0);
3926       return DAG.getNode(ISD::SRL, XType, Ctlz,
3927                          DAG.getConstant(Log2_32(MVT::getSizeInBits(XType)),
3928                                          TLI.getShiftAmountTy()));
3929     }
3930     // setgt X, 0 -> srl (and (-X, ~X), size(X)-1)
3931     if (N1C && N1C->isNullValue() && CC == ISD::SETGT) {
3932       SDOperand NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType),
3933                                     N0);
3934       SDOperand NotN0 = DAG.getNode(ISD::XOR, XType, N0,
3935                                     DAG.getConstant(~0ULL, XType));
3936       return DAG.getNode(ISD::SRL, XType,
3937                          DAG.getNode(ISD::AND, XType, NegN0, NotN0),
3938                          DAG.getConstant(MVT::getSizeInBits(XType)-1,
3939                                          TLI.getShiftAmountTy()));
3940     }
3941     // setgt X, -1 -> xor (srl (X, size(X)-1), 1)
3942     if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) {
3943       SDOperand Sign = DAG.getNode(ISD::SRL, XType, N0,
3944                                    DAG.getConstant(MVT::getSizeInBits(XType)-1,
3945                                                    TLI.getShiftAmountTy()));
3946       return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType));
3947     }
3948   }
3949
3950   // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X ->
3951   // Y = sra (X, size(X)-1); xor (add (X, Y), Y)
3952   if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) &&
3953       N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) {
3954     if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) {
3955       MVT::ValueType XType = N0.getValueType();
3956       if (SubC->isNullValue() && MVT::isInteger(XType)) {
3957         SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
3958                                     DAG.getConstant(MVT::getSizeInBits(XType)-1,
3959                                                     TLI.getShiftAmountTy()));
3960         SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift);
3961         AddToWorkList(Shift.Val);
3962         AddToWorkList(Add.Val);
3963         return DAG.getNode(ISD::XOR, XType, Add, Shift);
3964       }
3965     }
3966   }
3967
3968   return SDOperand();
3969 }
3970
3971 /// SimplifySetCC - This is a stub for TargetLowering::SimplifySetCC.
3972 SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0,
3973                                      SDOperand N1, ISD::CondCode Cond,
3974                                      bool foldBooleans) {
3975   TargetLowering::DAGCombinerInfo
3976     DagCombineInfo(DAG, !AfterLegalize, false, this);
3977   return TLI.SimplifySetCC(VT, N0, N1, Cond, foldBooleans, DagCombineInfo);
3978 }
3979
3980 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
3981 /// return a DAG expression to select that will generate the same value by
3982 /// multiplying by a magic number.  See:
3983 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
3984 SDOperand DAGCombiner::BuildSDIV(SDNode *N) {
3985   std::vector<SDNode*> Built;
3986   SDOperand S = TLI.BuildSDIV(N, DAG, &Built);
3987
3988   for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end();
3989        ii != ee; ++ii)
3990     AddToWorkList(*ii);
3991   return S;
3992 }
3993
3994 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
3995 /// return a DAG expression to select that will generate the same value by
3996 /// multiplying by a magic number.  See:
3997 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
3998 SDOperand DAGCombiner::BuildUDIV(SDNode *N) {
3999   std::vector<SDNode*> Built;
4000   SDOperand S = TLI.BuildUDIV(N, DAG, &Built);
4001
4002   for (std::vector<SDNode*>::iterator ii = Built.begin(), ee = Built.end();
4003        ii != ee; ++ii)
4004     AddToWorkList(*ii);
4005   return S;
4006 }
4007
4008 /// FindBaseOffset - Return true if base is known not to alias with anything
4009 /// but itself.  Provides base object and offset as results.
4010 static bool FindBaseOffset(SDOperand Ptr, SDOperand &Base, int64_t &Offset) {
4011   // Assume it is a primitive operation.
4012   Base = Ptr; Offset = 0;
4013
4014   // If it's an adding a simple constant then integrate the offset.
4015   if (Base.getOpcode() == ISD::ADD) {
4016     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Base.getOperand(1))) {
4017       Base = Base.getOperand(0);
4018       Offset += C->getValue();
4019     }
4020   }
4021
4022   // If it's any of the following then it can't alias with anything but itself.
4023   return isa<FrameIndexSDNode>(Base) ||
4024          isa<ConstantPoolSDNode>(Base) ||
4025          isa<GlobalAddressSDNode>(Base);
4026 }
4027
4028 /// isAlias - Return true if there is any possibility that the two addresses
4029 /// overlap.
4030 bool DAGCombiner::isAlias(SDOperand Ptr1, int64_t Size1,
4031                           const Value *SrcValue1, int SrcValueOffset1,
4032                           SDOperand Ptr2, int64_t Size2,
4033                           const Value *SrcValue2, int SrcValueOffset2)
4034 {
4035   // If they are the same then they must be aliases.
4036   if (Ptr1 == Ptr2) return true;
4037
4038   // Gather base node and offset information.
4039   SDOperand Base1, Base2;
4040   int64_t Offset1, Offset2;
4041   bool KnownBase1 = FindBaseOffset(Ptr1, Base1, Offset1);
4042   bool KnownBase2 = FindBaseOffset(Ptr2, Base2, Offset2);
4043
4044   // If they have a same base address then...
4045   if (Base1 == Base2) {
4046     // Check to see if the addresses overlap.
4047     return!((Offset1 + Size1) <= Offset2 || (Offset2 + Size2) <= Offset1);
4048   }
4049
4050   // If we know both bases then they can't alias.
4051   if (KnownBase1 && KnownBase2) return false;
4052
4053   if (CombinerGlobalAA) {
4054     // Use alias analysis information.
4055     int Overlap1 = Size1 + SrcValueOffset1 + Offset1;
4056     int Overlap2 = Size2 + SrcValueOffset2 + Offset2;
4057     AliasAnalysis::AliasResult AAResult =
4058                              AA.alias(SrcValue1, Overlap1, SrcValue2, Overlap2);
4059     if (AAResult == AliasAnalysis::NoAlias)
4060       return false;
4061   }
4062
4063   // Otherwise we have to assume they alias.
4064   return true;
4065 }
4066
4067 /// FindAliasInfo - Extracts the relevant alias information from the memory
4068 /// node.  Returns true if the operand was a load.
4069 bool DAGCombiner::FindAliasInfo(SDNode *N,
4070                         SDOperand &Ptr, int64_t &Size,
4071                         const Value *&SrcValue, int &SrcValueOffset) {
4072   if (LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
4073     Ptr = LD->getBasePtr();
4074     Size = MVT::getSizeInBits(LD->getLoadedVT()) >> 3;
4075     SrcValue = LD->getSrcValue();
4076     SrcValueOffset = LD->getSrcValueOffset();
4077     return true;
4078   } else if (StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
4079     Ptr = ST->getBasePtr();
4080     Size = MVT::getSizeInBits(ST->getStoredVT()) >> 3;
4081     SrcValue = ST->getSrcValue();
4082     SrcValueOffset = ST->getSrcValueOffset();
4083   } else {
4084     assert(0 && "FindAliasInfo expected a memory operand");
4085   }
4086
4087   return false;
4088 }
4089
4090 /// GatherAllAliases - Walk up chain skipping non-aliasing memory nodes,
4091 /// looking for aliasing nodes and adding them to the Aliases vector.
4092 void DAGCombiner::GatherAllAliases(SDNode *N, SDOperand OriginalChain,
4093                                    SmallVector<SDOperand, 8> &Aliases) {
4094   SmallVector<SDOperand, 8> Chains;     // List of chains to visit.
4095   std::set<SDNode *> Visited;           // Visited node set.
4096
4097   // Get alias information for node.
4098   SDOperand Ptr;
4099   int64_t Size;
4100   const Value *SrcValue;
4101   int SrcValueOffset;
4102   bool IsLoad = FindAliasInfo(N, Ptr, Size, SrcValue, SrcValueOffset);
4103
4104   // Starting off.
4105   Chains.push_back(OriginalChain);
4106
4107   // Look at each chain and determine if it is an alias.  If so, add it to the
4108   // aliases list.  If not, then continue up the chain looking for the next
4109   // candidate.
4110   while (!Chains.empty()) {
4111     SDOperand Chain = Chains.back();
4112     Chains.pop_back();
4113
4114      // Don't bother if we've been before.
4115     if (Visited.find(Chain.Val) != Visited.end()) continue;
4116     Visited.insert(Chain.Val);
4117
4118     switch (Chain.getOpcode()) {
4119     case ISD::EntryToken:
4120       // Entry token is ideal chain operand, but handled in FindBetterChain.
4121       break;
4122
4123     case ISD::LOAD:
4124     case ISD::STORE: {
4125       // Get alias information for Chain.
4126       SDOperand OpPtr;
4127       int64_t OpSize;
4128       const Value *OpSrcValue;
4129       int OpSrcValueOffset;
4130       bool IsOpLoad = FindAliasInfo(Chain.Val, OpPtr, OpSize,
4131                                     OpSrcValue, OpSrcValueOffset);
4132
4133       // If chain is alias then stop here.
4134       if (!(IsLoad && IsOpLoad) &&
4135           isAlias(Ptr, Size, SrcValue, SrcValueOffset,
4136                   OpPtr, OpSize, OpSrcValue, OpSrcValueOffset)) {
4137         Aliases.push_back(Chain);
4138       } else {
4139         // Look further up the chain.
4140         Chains.push_back(Chain.getOperand(0));
4141         // Clean up old chain.
4142         AddToWorkList(Chain.Val);
4143       }
4144       break;
4145     }
4146
4147     case ISD::TokenFactor:
4148       // We have to check each of the operands of the token factor, so we queue
4149       // then up.  Adding the  operands to the queue (stack) in reverse order
4150       // maintains the original order and increases the likelihood that getNode
4151       // will find a matching token factor (CSE.)
4152       for (unsigned n = Chain.getNumOperands(); n;)
4153         Chains.push_back(Chain.getOperand(--n));
4154       // Eliminate the token factor if we can.
4155       AddToWorkList(Chain.Val);
4156       break;
4157
4158     default:
4159       // For all other instructions we will just have to take what we can get.
4160       Aliases.push_back(Chain);
4161       break;
4162     }
4163   }
4164 }
4165
4166 /// FindBetterChain - Walk up chain skipping non-aliasing memory nodes, looking
4167 /// for a better chain (aliasing node.)
4168 SDOperand DAGCombiner::FindBetterChain(SDNode *N, SDOperand OldChain) {
4169   SmallVector<SDOperand, 8> Aliases;  // Ops for replacing token factor.
4170
4171   // Accumulate all the aliases to this node.
4172   GatherAllAliases(N, OldChain, Aliases);
4173
4174   if (Aliases.size() == 0) {
4175     // If no operands then chain to entry token.
4176     return DAG.getEntryNode();
4177   } else if (Aliases.size() == 1) {
4178     // If a single operand then chain to it.  We don't need to revisit it.
4179     return Aliases[0];
4180   }
4181
4182   // Construct a custom tailored token factor.
4183   SDOperand NewChain = DAG.getNode(ISD::TokenFactor, MVT::Other,
4184                                    &Aliases[0], Aliases.size());
4185
4186   // Make sure the old chain gets cleaned up.
4187   if (NewChain != OldChain) AddToWorkList(OldChain.Val);
4188
4189   return NewChain;
4190 }
4191
4192 // SelectionDAG::Combine - This is the entry point for the file.
4193 //
4194 void SelectionDAG::Combine(bool RunningAfterLegalize, AliasAnalysis &AA) {
4195   if (!RunningAfterLegalize && ViewDAGCombine1)
4196     viewGraph();
4197   if (RunningAfterLegalize && ViewDAGCombine2)
4198     viewGraph();
4199   /// run - This is the main entry point to this class.
4200   ///
4201   DAGCombiner(*this, AA).Run(RunningAfterLegalize);
4202 }