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: Should add a corresponding version of fold AND with
  20 // ZERO_EXTEND/SIGN_EXTEND by converting them to an ANY_EXTEND node which
  21 // we don't have yet.
  22 //
  23 // FIXME: select C, 16, 0 -> shr C, 4
  24 // FIXME: select C, pow2, pow2 -> something smart
  25 // FIXME: trunc(select X, Y, Z) -> select X, trunc(Y), trunc(Z)
  26 // FIXME: (select C, load A, load B) -> load (select C, A, B)
  27 // FIXME: store -> load -> forward substitute
  28 // FIXME: Dead stores -> nuke
  29 // FIXME: shr X, (and Y,31) -> shr X, Y
  30 // FIXME: TRUNC (LOAD)   -> EXT_LOAD/LOAD(smaller)
  31 // FIXME: mul (x, const) -> shifts + adds
  32 // FIXME: undef values
  33 // FIXME: zero extend when top bits are 0 -> drop it ?
  34 // FIXME: make truncate see through SIGN_EXTEND and AND
  35 // FIXME: sext_in_reg(setcc) on targets that return zero or one, and where
  36 //        EVT != MVT::i1 can drop the sext.
  37 // FIXME: (sra (sra x, c1), c2) -> (sra x, c1+c2)
  38 // FIXME: verify that getNode can't return extends with an operand whose type
  39 //        is >= to that of the extend.
  40 // FIXME: divide by zero is currently left unfolded.  do we want to turn this
  41 //        into an undef?
  42 // FIXME: select ne (select cc, 1, 0), 0, true, false -> select cc, true, false
  43 // FIXME: sext_inreg(SRL) -> SRA:
  44 // int %simple(uint %X) { %tmp.4 = shr uint %X, ubyte 16
  45 //    %tmp.5 = cast uint %tmp.4 to short     %tmp.6 = cast short %tmp.5 to int
  46 //    ret int %tmp.6 }
  47 //
  48 //===----------------------------------------------------------------------===//
  49
  50 #define DEBUG_TYPE "dagcombine"
  51 #include "llvm/ADT/Statistic.h"
  52 #include "llvm/CodeGen/SelectionDAG.h"
  53 #include "llvm/Support/Debug.h"
  54 #include "llvm/Support/MathExtras.h"
  55 #include "llvm/Target/TargetLowering.h"
  56 #include <algorithm>
  57 #include <cmath>
  58 using namespace llvm;
  59
  60 namespace {
  61   Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined");
  62
  63   class DAGCombiner {
  64     SelectionDAG &DAG;
  65     TargetLowering &TLI;
  66     bool AfterLegalize;
  67
  68     // Worklist of all of the nodes that need to be simplified.
  69     std::vector<SDNode*> WorkList;
  70
  71     /// AddUsersToWorkList - When an instruction is simplified, add all users of
  72     /// the instruction to the work lists because they might get more simplified
  73     /// now.
  74     ///
  75     void AddUsersToWorkList(SDNode *N) {
  76       for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
  77            UI != UE; ++UI)
  78         WorkList.push_back(*UI);
  79     }
  80
  81     /// removeFromWorkList - remove all instances of N from the worklist.
  82     void removeFromWorkList(SDNode *N) {
  83       WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N),
  84                      WorkList.end());
  85     }
  86
  87     /// visit - call the node-specific routine that knows how to fold each
  88     /// particular type of node.
  89     SDOperand visit(SDNode *N);
  90
  91     // Visitation implementation - Implement dag node combining for different
  92     // node types.  The semantics are as follows:
  93     // Return Value:
  94     //   SDOperand.Val == 0   - No change was made
  95     //   otherwise            - N should be replaced by the returned Operand.
  96     //
  97     SDOperand visitTokenFactor(SDNode *N);
  98     SDOperand visitADD(SDNode *N);
  99     SDOperand visitSUB(SDNode *N);
 100     SDOperand visitMUL(SDNode *N);
 101     SDOperand visitSDIV(SDNode *N);
 102     SDOperand visitUDIV(SDNode *N);
 103     SDOperand visitSREM(SDNode *N);
 104     SDOperand visitUREM(SDNode *N);
 105     SDOperand visitMULHU(SDNode *N);
 106     SDOperand visitMULHS(SDNode *N);
 107     SDOperand visitAND(SDNode *N);
 108     SDOperand visitOR(SDNode *N);
 109     SDOperand visitXOR(SDNode *N);
 110     SDOperand visitSHL(SDNode *N);
 111     SDOperand visitSRA(SDNode *N);
 112     SDOperand visitSRL(SDNode *N);
 113     SDOperand visitCTLZ(SDNode *N);
 114     SDOperand visitCTTZ(SDNode *N);
 115     SDOperand visitCTPOP(SDNode *N);
 116     SDOperand visitSELECT(SDNode *N);
 117     SDOperand visitSELECT_CC(SDNode *N);
 118     SDOperand visitSETCC(SDNode *N);
 119     SDOperand visitSIGN_EXTEND(SDNode *N);
 120     SDOperand visitZERO_EXTEND(SDNode *N);
 121     SDOperand visitSIGN_EXTEND_INREG(SDNode *N);
 122     SDOperand visitTRUNCATE(SDNode *N);
 123
 124     SDOperand visitFADD(SDNode *N);
 125     SDOperand visitFSUB(SDNode *N);
 126     SDOperand visitFMUL(SDNode *N);
 127     SDOperand visitFDIV(SDNode *N);
 128     SDOperand visitFREM(SDNode *N);
 129     SDOperand visitSINT_TO_FP(SDNode *N);
 130     SDOperand visitUINT_TO_FP(SDNode *N);
 131     SDOperand visitFP_TO_SINT(SDNode *N);
 132     SDOperand visitFP_TO_UINT(SDNode *N);
 133     SDOperand visitFP_ROUND(SDNode *N);
 134     SDOperand visitFP_ROUND_INREG(SDNode *N);
 135     SDOperand visitFP_EXTEND(SDNode *N);
 136     SDOperand visitFNEG(SDNode *N);
 137     SDOperand visitFABS(SDNode *N);
 138     SDOperand visitBRCOND(SDNode *N);
 139     SDOperand visitBRCONDTWOWAY(SDNode *N);
 140     SDOperand visitBR_CC(SDNode *N);
 141     SDOperand visitBRTWOWAY_CC(SDNode *N);
 142
 143     SDOperand SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2);
 144     SDOperand SimplifySelectCC(SDOperand N0, SDOperand N1, SDOperand N2,
 145                                SDOperand N3, ISD::CondCode CC);
 146     SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
 147                             ISD::CondCode Cond, bool foldBooleans = true);
 148 public:
 149     DAGCombiner(SelectionDAG &D)
 150       : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {}
 151
 152     /// Run - runs the dag combiner on all nodes in the work list
 153     void Run(bool RunningAfterLegalize);
 154   };
 155 }
 156
 157 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
 158 /// this predicate to simplify operations downstream.  V and Mask are known to
 159 /// be the same type.
 160 static bool MaskedValueIsZero(const SDOperand &Op, uint64_t Mask,
 161                               const TargetLowering &TLI) {
 162   unsigned SrcBits;
 163   if (Mask == 0) return true;
 164
 165   // If we know the result of a setcc has the top bits zero, use this info.
 166   switch (Op.getOpcode()) {
 167   case ISD::Constant:
 168     return (cast<ConstantSDNode>(Op)->getValue() & Mask) == 0;
 169   case ISD::SETCC:
 170     // FIXME: teach this about non ZeroOrOne values, such as 0 or -1
 171     return ((Mask & 1) == 0) &&
 172     TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult;
 173   case ISD::ZEXTLOAD:
 174     SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
 175     return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits.
 176   case ISD::ZERO_EXTEND:
 177     SrcBits = MVT::getSizeInBits(Op.getOperand(0).getValueType());
 178     return MaskedValueIsZero(Op.getOperand(0),Mask & ((1ULL << SrcBits)-1),TLI);
 179   case ISD::AssertZext:
 180     SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
 181     return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits.
 182   case ISD::AND:
 183     // If either of the operands has zero bits, the result will too.
 184     if (MaskedValueIsZero(Op.getOperand(1), Mask, TLI) ||
 185         MaskedValueIsZero(Op.getOperand(0), Mask, TLI))
 186       return true;
 187
 188     // (X & C1) & C2 == 0   iff   C1 & C2 == 0.
 189     if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
 190       return MaskedValueIsZero(Op.getOperand(0),AndRHS->getValue() & Mask, TLI);
 191     return false;
 192   case ISD::OR:
 193   case ISD::XOR:
 194     return MaskedValueIsZero(Op.getOperand(0), Mask, TLI) &&
 195     MaskedValueIsZero(Op.getOperand(1), Mask, TLI);
 196   case ISD::SELECT:
 197     return MaskedValueIsZero(Op.getOperand(1), Mask, TLI) &&
 198     MaskedValueIsZero(Op.getOperand(2), Mask, TLI);
 199   case ISD::SELECT_CC:
 200     return MaskedValueIsZero(Op.getOperand(2), Mask, TLI) &&
 201     MaskedValueIsZero(Op.getOperand(3), Mask, TLI);
 202   case ISD::SRL:
 203     // (ushr X, C1) & C2 == 0   iff  X & (C2 << C1) == 0
 204     if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 205       uint64_t NewVal = Mask << ShAmt->getValue();
 206       SrcBits = MVT::getSizeInBits(Op.getValueType());
 207       if (SrcBits != 64) NewVal &= (1ULL << SrcBits)-1;
 208       return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI);
 209     }
 210     return false;
 211   case ISD::SHL:
 212     // (ushl X, C1) & C2 == 0   iff  X & (C2 >> C1) == 0
 213     if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 214       uint64_t NewVal = Mask >> ShAmt->getValue();
 215       return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI);
 216     }
 217     return false;
 218   case ISD::ADD:
 219     // (add X, Y) & C == 0 iff (X&C)|(Y&C) == 0 and all bits are low bits.
 220     if ((Mask&(Mask+1)) == 0) {  // All low bits
 221       if (MaskedValueIsZero(Op.getOperand(0), Mask, TLI) &&
 222           MaskedValueIsZero(Op.getOperand(1), Mask, TLI))
 223         return true;
 224     }
 225     break;
 226   case ISD::SUB:
 227     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
 228       // We know that the top bits of C-X are clear if X contains less bits
 229       // than C (i.e. no wrap-around can happen).  For example, 20-X is
 230       // positive if we can prove that X is >= 0 and < 16.
 231       unsigned Bits = MVT::getSizeInBits(CLHS->getValueType(0));
 232       if ((CLHS->getValue() & (1 << (Bits-1))) == 0) {  // sign bit clear
 233         unsigned NLZ = CountLeadingZeros_64(CLHS->getValue()+1);
 234         uint64_t MaskV = (1ULL << (63-NLZ))-1;
 235         if (MaskedValueIsZero(Op.getOperand(1), ~MaskV, TLI)) {
 236           // High bits are clear this value is known to be >= C.
 237           unsigned NLZ2 = CountLeadingZeros_64(CLHS->getValue());
 238           if ((Mask & ((1ULL << (64-NLZ2))-1)) == 0)
 239             return true;
 240         }
 241       }
 242     }
 243     break;
 244   case ISD::CTTZ:
 245   case ISD::CTLZ:
 246   case ISD::CTPOP:
 247     // Bit counting instructions can not set the high bits of the result
 248     // register.  The max number of bits sets depends on the input.
 249     return (Mask & (MVT::getSizeInBits(Op.getValueType())*2-1)) == 0;
 250
 251     // TODO we could handle some SRA cases here.
 252   default: break;
 253   }
 254   return false;
 255 }
 256
 257 // isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc
 258 // that selects between the values 1 and 0, making it equivalent to a setcc.
 259 // Also, set the incoming LHS, RHS, and CC references to the appropriate
 260 // nodes based on the type of node we are checking.  This simplifies life a
 261 // bit for the callers.
 262 static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS,
 263                               SDOperand &CC) {
 264   if (N.getOpcode() == ISD::SETCC) {
 265     LHS = N.getOperand(0);
 266     RHS = N.getOperand(1);
 267     CC  = N.getOperand(2);
 268     return true;
 269   }
 270   if (N.getOpcode() == ISD::SELECT_CC &&
 271       N.getOperand(2).getOpcode() == ISD::Constant &&
 272       N.getOperand(3).getOpcode() == ISD::Constant &&
 273       cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 &&
 274       cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) {
 275     LHS = N.getOperand(0);
 276     RHS = N.getOperand(1);
 277     CC  = N.getOperand(4);
 278     return true;
 279   }
 280   return false;
 281 }
 282
 283 // isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only
 284 // one use.  If this is true, it allows the users to invert the operation for
 285 // free when it is profitable to do so.
 286 static bool isOneUseSetCC(SDOperand N) {
 287   SDOperand N0, N1, N2;
 288   if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse())
 289     return true;
 290   return false;
 291 }
 292
 293 // FIXME: This should probably go in the ISD class rather than being duplicated
 294 // in several files.
 295 static bool isCommutativeBinOp(unsigned Opcode) {
 296   switch (Opcode) {
 297     case ISD::ADD:
 298     case ISD::MUL:
 299     case ISD::AND:
 300     case ISD::OR:
 301     case ISD::XOR: return true;
 302     default: return false; // FIXME: Need commutative info for user ops!
 303   }
 304 }
 305
 306 void DAGCombiner::Run(bool RunningAfterLegalize) {
 307   // set the instance variable, so that the various visit routines may use it.
 308   AfterLegalize = RunningAfterLegalize;
 309
 310   // Add all the dag nodes to the worklist.
 311   WorkList.insert(WorkList.end(), DAG.allnodes_begin(), DAG.allnodes_end());
 312
 313   // Create a dummy node (which is not added to allnodes), that adds a reference
 314   // to the root node, preventing it from being deleted, and tracking any
 315   // changes of the root.
 316   HandleSDNode Dummy(DAG.getRoot());
 317
 318   // while the worklist isn't empty, inspect the node on the end of it and
 319   // try and combine it.
 320   while (!WorkList.empty()) {
 321     SDNode *N = WorkList.back();
 322     WorkList.pop_back();
 323
 324     // If N has no uses, it is dead.  Make sure to revisit all N's operands once
 325     // N is deleted from the DAG, since they too may now be dead or may have a
 326     // reduced number of uses, allowing other xforms.
 327     if (N->use_empty() && N != &Dummy) {
 328       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 329         WorkList.push_back(N->getOperand(i).Val);
 330
 331       removeFromWorkList(N);
 332       DAG.DeleteNode(N);
 333       continue;
 334     }
 335
 336     SDOperand RV = visit(N);
 337     if (RV.Val) {
 338       ++NodesCombined;
 339       // If we get back the same node we passed in, rather than a new node or
 340       // zero, we know that the node must have defined multiple values and
 341       // CombineTo was used.  Since CombineTo takes care of the worklist
 342       // mechanics for us, we have no work to do in this case.
 343       if (RV.Val != N) {
 344         DEBUG(std::cerr << "\nReplacing "; N->dump();
 345               std::cerr << "\nWith: "; RV.Val->dump();
 346               std::cerr << '\n');
 347         DAG.ReplaceAllUsesWith(N, std::vector<SDOperand>(1, RV));
 348
 349         // Push the new node and any users onto the worklist
 350         WorkList.push_back(RV.Val);
 351         AddUsersToWorkList(RV.Val);
 352
 353         // Nodes can end up on the worklist more than once.  Make sure we do
 354         // not process a node that has been replaced.
 355         removeFromWorkList(N);
 356
 357         // Finally, since the node is now dead, remove it from the graph.
 358         DAG.DeleteNode(N);
 359       }
 360     }
 361   }
 362
 363   // If the root changed (e.g. it was a dead load, update the root).
 364   DAG.setRoot(Dummy.getValue());
 365 }
 366
 367 SDOperand DAGCombiner::visit(SDNode *N) {
 368   switch(N->getOpcode()) {
 369   default: break;
 370   case ISD::TokenFactor:        return visitTokenFactor(N);
 371   case ISD::ADD:                return visitADD(N);
 372   case ISD::SUB:                return visitSUB(N);
 373   case ISD::MUL:                return visitMUL(N);
 374   case ISD::SDIV:               return visitSDIV(N);
 375   case ISD::UDIV:               return visitUDIV(N);
 376   case ISD::SREM:               return visitSREM(N);
 377   case ISD::UREM:               return visitUREM(N);
 378   case ISD::MULHU:              return visitMULHU(N);
 379   case ISD::MULHS:              return visitMULHS(N);
 380   case ISD::AND:                return visitAND(N);
 381   case ISD::OR:                 return visitOR(N);
 382   case ISD::XOR:                return visitXOR(N);
 383   case ISD::SHL:                return visitSHL(N);
 384   case ISD::SRA:                return visitSRA(N);
 385   case ISD::SRL:                return visitSRL(N);
 386   case ISD::CTLZ:               return visitCTLZ(N);
 387   case ISD::CTTZ:               return visitCTTZ(N);
 388   case ISD::CTPOP:              return visitCTPOP(N);
 389   case ISD::SELECT:             return visitSELECT(N);
 390   case ISD::SELECT_CC:          return visitSELECT_CC(N);
 391   case ISD::SETCC:              return visitSETCC(N);
 392   case ISD::SIGN_EXTEND:        return visitSIGN_EXTEND(N);
 393   case ISD::ZERO_EXTEND:        return visitZERO_EXTEND(N);
 394   case ISD::SIGN_EXTEND_INREG:  return visitSIGN_EXTEND_INREG(N);
 395   case ISD::TRUNCATE:           return visitTRUNCATE(N);
 396   case ISD::FADD:               return visitFADD(N);
 397   case ISD::FSUB:               return visitFSUB(N);
 398   case ISD::FMUL:               return visitFMUL(N);
 399   case ISD::FDIV:               return visitFDIV(N);
 400   case ISD::FREM:               return visitFREM(N);
 401   case ISD::SINT_TO_FP:         return visitSINT_TO_FP(N);
 402   case ISD::UINT_TO_FP:         return visitUINT_TO_FP(N);
 403   case ISD::FP_TO_SINT:         return visitFP_TO_SINT(N);
 404   case ISD::FP_TO_UINT:         return visitFP_TO_UINT(N);
 405   case ISD::FP_ROUND:           return visitFP_ROUND(N);
 406   case ISD::FP_ROUND_INREG:     return visitFP_ROUND_INREG(N);
 407   case ISD::FP_EXTEND:          return visitFP_EXTEND(N);
 408   case ISD::FNEG:               return visitFNEG(N);
 409   case ISD::FABS:               return visitFABS(N);
 410   case ISD::BRCOND:             return visitBRCOND(N);
 411   case ISD::BRCONDTWOWAY:       return visitBRCONDTWOWAY(N);
 412   case ISD::BR_CC:              return visitBR_CC(N);
 413   case ISD::BRTWOWAY_CC:        return visitBRTWOWAY_CC(N);
 414   }
 415   return SDOperand();
 416 }
 417
 418 SDOperand DAGCombiner::visitTokenFactor(SDNode *N) {
 419   // If the token factor has two operands and one is the entry token, replace
 420   // the token factor with the other operand.
 421   if (N->getNumOperands() == 2) {
 422     if (N->getOperand(0).getOpcode() == ISD::EntryToken)
 423       return N->getOperand(1);
 424     if (N->getOperand(1).getOpcode() == ISD::EntryToken)
 425       return N->getOperand(0);
 426   }
 427   return SDOperand();
 428 }
 429
 430 SDOperand DAGCombiner::visitADD(SDNode *N) {
 431   SDOperand N0 = N->getOperand(0);
 432   SDOperand N1 = N->getOperand(1);
 433   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 434   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 435   MVT::ValueType VT = N0.getValueType();
 436
 437   // fold (add c1, c2) -> c1+c2
 438   if (N0C && N1C)
 439     return DAG.getConstant(N0C->getValue() + N1C->getValue(), VT);
 440   // canonicalize constant to RHS
 441   if (N0C && !N1C) {
 442     std::swap(N0, N1);
 443     std::swap(N0C, N1C);
 444   }
 445   // fold (add x, 0) -> x
 446   if (N1C && N1C->isNullValue())
 447     return N0;
 448   // fold (add (add x, c1), c2) -> (add x, c1+c2)
 449   if (N1C && N0.getOpcode() == ISD::ADD) {
 450     ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
 451     ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
 452     if (N00C)
 453       return DAG.getNode(ISD::ADD, VT, N0.getOperand(1),
 454                          DAG.getConstant(N1C->getValue()+N00C->getValue(), VT));
 455     if (N01C)
 456       return DAG.getNode(ISD::ADD, VT, N0.getOperand(0),
 457                          DAG.getConstant(N1C->getValue()+N01C->getValue(), VT));
 458   }
 459   // fold ((0-A) + B) -> B-A
 460   if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) &&
 461       cast<ConstantSDNode>(N0.getOperand(0))->isNullValue())
 462     return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1));
 463   // fold (A + (0-B)) -> A-B
 464   if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) &&
 465       cast<ConstantSDNode>(N1.getOperand(0))->isNullValue())
 466     return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1));
 467   // fold (A+(B-A)) -> B
 468   if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1))
 469     return N1.getOperand(0);
 470   return SDOperand();
 471 }
 472
 473 SDOperand DAGCombiner::visitSUB(SDNode *N) {
 474   SDOperand N0 = N->getOperand(0);
 475   SDOperand N1 = N->getOperand(1);
 476   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
 477   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 478
 479   // fold (sub c1, c2) -> c1-c2
 480   if (N0C && N1C)
 481     return DAG.getConstant(N0C->getValue() - N1C->getValue(),
 482                            N->getValueType(0));
 483   // fold (sub x, 0) -> x
 484   if (N1C && N1C->isNullValue())
 485     return N0;
 486   // fold (A+B)-A -> B
 487   if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1)
 488     return N0.getOperand(1);
 489   // fold (A+B)-B -> A
 490   if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1)
 491     return N0.getOperand(0);
 492   return SDOperand();
 493 }
 494
 495 SDOperand DAGCombiner::visitMUL(SDNode *N) {
 496   SDOperand N0 = N->getOperand(0);
 497   SDOperand N1 = N->getOperand(1);
 498   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 499   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 500   MVT::ValueType VT = N0.getValueType();
 501
 502   // fold (mul c1, c2) -> c1*c2
 503   if (N0C && N1C)
 504     return DAG.getConstant(N0C->getValue() * N1C->getValue(),
 505                            N->getValueType(0));
 506   // canonicalize constant to RHS
 507   if (N0C && !N1C) {
 508     std::swap(N0, N1);
 509     std::swap(N0C, N1C);
 510   }
 511   // fold (mul x, 0) -> 0
 512   if (N1C && N1C->isNullValue())
 513     return N1;
 514   // fold (mul x, -1) -> 0-x
 515   if (N1C && N1C->isAllOnesValue())
 516     return DAG.getNode(ISD::SUB, N->getValueType(0),
 517                        DAG.getConstant(0, N->getValueType(0)), N0);
 518   // fold (mul x, (1 << c)) -> x << c
 519   if (N1C && isPowerOf2_64(N1C->getValue()))
 520     return DAG.getNode(ISD::SHL, N->getValueType(0), N0,
 521                        DAG.getConstant(Log2_64(N1C->getValue()),
 522                                        TLI.getShiftAmountTy()));
 523   // fold (mul (mul x, c1), c2) -> (mul x, c1*c2)
 524   if (N1C && N0.getOpcode() == ISD::MUL) {
 525     ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
 526     ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
 527     if (N00C)
 528       return DAG.getNode(ISD::MUL, VT, N0.getOperand(1),
 529                          DAG.getConstant(N1C->getValue()*N00C->getValue(), VT));
 530     if (N01C)
 531       return DAG.getNode(ISD::MUL, VT, N0.getOperand(0),
 532                          DAG.getConstant(N1C->getValue()*N01C->getValue(), VT));
 533   }
 534   return SDOperand();
 535 }
 536
 537 SDOperand DAGCombiner::visitSDIV(SDNode *N) {
 538   SDOperand N0 = N->getOperand(0);
 539   SDOperand N1 = N->getOperand(1);
 540   MVT::ValueType VT = N->getValueType(0);
 541   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
 542   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 543
 544   // fold (sdiv c1, c2) -> c1/c2
 545   if (N0C && N1C && !N1C->isNullValue())
 546     return DAG.getConstant(N0C->getSignExtended() / N1C->getSignExtended(),
 547                            N->getValueType(0));
 548
 549   // If we know the sign bits of both operands are zero, strength reduce to a
 550   // udiv instead.  Handles (X&15) /s 4 -> X&15 >> 2
 551   uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1);
 552   if (MaskedValueIsZero(N1, SignBit, TLI) &&
 553       MaskedValueIsZero(N0, SignBit, TLI))
 554     return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1);
 555
 556
 557   return SDOperand();
 558 }
 559
 560 SDOperand DAGCombiner::visitUDIV(SDNode *N) {
 561   SDOperand N0 = N->getOperand(0);
 562   SDOperand N1 = N->getOperand(1);
 563   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
 564   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 565
 566   // fold (udiv c1, c2) -> c1/c2
 567   if (N0C && N1C && !N1C->isNullValue())
 568     return DAG.getConstant(N0C->getValue() / N1C->getValue(),
 569                            N->getValueType(0));
 570   // fold (udiv x, (1 << c)) -> x >>u c
 571   if (N1C && isPowerOf2_64(N1C->getValue()))
 572     return DAG.getNode(ISD::SRL, N->getValueType(0), N0,
 573                        DAG.getConstant(Log2_64(N1C->getValue()),
 574                                        TLI.getShiftAmountTy()));
 575   return SDOperand();
 576 }
 577
 578 SDOperand DAGCombiner::visitSREM(SDNode *N) {
 579   SDOperand N0 = N->getOperand(0);
 580   SDOperand N1 = N->getOperand(1);
 581   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 582   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 583
 584   // fold (srem c1, c2) -> c1%c2
 585   if (N0C && N1C && !N1C->isNullValue())
 586     return DAG.getConstant(N0C->getSignExtended() % N1C->getSignExtended(),
 587                            N->getValueType(0));
 588   return SDOperand();
 589 }
 590
 591 SDOperand DAGCombiner::visitUREM(SDNode *N) {
 592   SDOperand N0 = N->getOperand(0);
 593   SDOperand N1 = N->getOperand(1);
 594   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 595   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 596
 597   // fold (urem c1, c2) -> c1%c2
 598   if (N0C && N1C && !N1C->isNullValue())
 599     return DAG.getConstant(N0C->getValue() % N1C->getValue(),
 600                            N->getValueType(0));
 601   // FIXME: c2 power of 2 -> mask?
 602   return SDOperand();
 603 }
 604
 605 SDOperand DAGCombiner::visitMULHS(SDNode *N) {
 606   SDOperand N0 = N->getOperand(0);
 607   SDOperand N1 = N->getOperand(1);
 608   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 609
 610   // fold (mulhs x, 0) -> 0
 611   if (N1C && N1C->isNullValue())
 612     return N1;
 613   // fold (mulhs x, 1) -> (sra x, size(x)-1)
 614   if (N1C && N1C->getValue() == 1)
 615     return DAG.getNode(ISD::SRA, N0.getValueType(), N0,
 616                        DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1,
 617                                        TLI.getShiftAmountTy()));
 618   return SDOperand();
 619 }
 620
 621 SDOperand DAGCombiner::visitMULHU(SDNode *N) {
 622   SDOperand N0 = N->getOperand(0);
 623   SDOperand N1 = N->getOperand(1);
 624   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 625
 626   // fold (mulhu x, 0) -> 0
 627   if (N1C && N1C->isNullValue())
 628     return N1;
 629   // fold (mulhu x, 1) -> 0
 630   if (N1C && N1C->getValue() == 1)
 631     return DAG.getConstant(0, N0.getValueType());
 632   return SDOperand();
 633 }
 634
 635 SDOperand DAGCombiner::visitAND(SDNode *N) {
 636   SDOperand N0 = N->getOperand(0);
 637   SDOperand N1 = N->getOperand(1);
 638   SDOperand LL, LR, RL, RR, CC0, CC1;
 639   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 640   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 641   MVT::ValueType VT = N1.getValueType();
 642   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
 643
 644   // fold (and c1, c2) -> c1&c2
 645   if (N0C && N1C)
 646     return DAG.getConstant(N0C->getValue() & N1C->getValue(), VT);
 647   // canonicalize constant to RHS
 648   if (N0C && !N1C) {
 649     std::swap(N0, N1);
 650     std::swap(N0C, N1C);
 651   }
 652   // fold (and x, -1) -> x
 653   if (N1C && N1C->isAllOnesValue())
 654     return N0;
 655   // if (and x, c) is known to be zero, return 0
 656   if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI))
 657     return DAG.getConstant(0, VT);
 658   // fold (and x, c) -> x iff (x & ~c) == 0
 659   if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)),
 660                                TLI))
 661     return N0;
 662   // fold (and (and x, c1), c2) -> (and x, c1^c2)
 663   if (N1C && N0.getOpcode() == ISD::AND) {
 664     ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
 665     ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
 666     if (N00C)
 667       return DAG.getNode(ISD::AND, VT, N0.getOperand(1),
 668                          DAG.getConstant(N1C->getValue()&N00C->getValue(), VT));
 669     if (N01C)
 670       return DAG.getNode(ISD::AND, VT, N0.getOperand(0),
 671                          DAG.getConstant(N1C->getValue()&N01C->getValue(), VT));
 672   }
 673   // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1)
 674   if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG) {
 675     unsigned ExtendBits =
 676     MVT::getSizeInBits(cast<VTSDNode>(N0.getOperand(1))->getVT());
 677     if ((N1C->getValue() & (~0ULL << ExtendBits)) == 0)
 678       return DAG.getNode(ISD::AND, VT, N0.getOperand(0), N1);
 679   }
 680   // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF
 681   if (N0.getOpcode() == ISD::OR)
 682     if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
 683       if ((ORI->getValue() & N1C->getValue()) == N1C->getValue())
 684         return N1;
 685   // fold (and (setcc x), (setcc y)) -> (setcc (and x, y))
 686   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
 687     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
 688     ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
 689
 690     if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
 691         MVT::isInteger(LL.getValueType())) {
 692       // fold (X == 0) & (Y == 0) -> (X|Y == 0)
 693       if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) {
 694         SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
 695         WorkList.push_back(ORNode.Val);
 696         return DAG.getSetCC(VT, ORNode, LR, Op1);
 697       }
 698       // fold (X == -1) & (Y == -1) -> (X&Y == -1)
 699       if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) {
 700         SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL);
 701         WorkList.push_back(ANDNode.Val);
 702         return DAG.getSetCC(VT, ANDNode, LR, Op1);
 703       }
 704       // fold (X >  -1) & (Y >  -1) -> (X|Y > -1)
 705       if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) {
 706         SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
 707         WorkList.push_back(ORNode.Val);
 708         return DAG.getSetCC(VT, ORNode, LR, Op1);
 709       }
 710     }
 711     // canonicalize equivalent to ll == rl
 712     if (LL == RR && LR == RL) {
 713       Op1 = ISD::getSetCCSwappedOperands(Op1);
 714       std::swap(RL, RR);
 715     }
 716     if (LL == RL && LR == RR) {
 717       bool isInteger = MVT::isInteger(LL.getValueType());
 718       ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger);
 719       if (Result != ISD::SETCC_INVALID)
 720         return DAG.getSetCC(N0.getValueType(), LL, LR, Result);
 721     }
 722   }
 723   // fold (and (zext x), (zext y)) -> (zext (and x, y))
 724   if (N0.getOpcode() == ISD::ZERO_EXTEND &&
 725       N1.getOpcode() == ISD::ZERO_EXTEND &&
 726       N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
 727     SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(),
 728                                     N0.getOperand(0), N1.getOperand(0));
 729     WorkList.push_back(ANDNode.Val);
 730     return DAG.getNode(ISD::ZERO_EXTEND, VT, ANDNode);
 731   }
 732   // fold (and (shl/srl x), (shl/srl y)) -> (shl/srl (and x, y))
 733   if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) ||
 734        (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL)) &&
 735       N0.getOperand(1) == N1.getOperand(1)) {
 736     SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(),
 737                                     N0.getOperand(0), N1.getOperand(0));
 738     WorkList.push_back(ANDNode.Val);
 739     return DAG.getNode(N0.getOpcode(), VT, ANDNode, N0.getOperand(1));
 740   }
 741   return SDOperand();
 742 }
 743
 744 SDOperand DAGCombiner::visitOR(SDNode *N) {
 745   SDOperand N0 = N->getOperand(0);
 746   SDOperand N1 = N->getOperand(1);
 747   SDOperand LL, LR, RL, RR, CC0, CC1;
 748   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 749   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 750   MVT::ValueType VT = N1.getValueType();
 751   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
 752
 753   // fold (or c1, c2) -> c1|c2
 754   if (N0C && N1C)
 755     return DAG.getConstant(N0C->getValue() | N1C->getValue(),
 756                            N->getValueType(0));
 757   // canonicalize constant to RHS
 758   if (N0C && !N1C) {
 759     std::swap(N0, N1);
 760     std::swap(N0C, N1C);
 761   }
 762   // fold (or x, 0) -> x
 763   if (N1C && N1C->isNullValue())
 764     return N0;
 765   // fold (or x, -1) -> -1
 766   if (N1C && N1C->isAllOnesValue())
 767     return N1;
 768   // fold (or x, c) -> c iff (x & ~c) == 0
 769   if (N1C && MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits)),
 770                                TLI))
 771     return N1;
 772   // fold (or (or x, c1), c2) -> (or x, c1|c2)
 773   if (N1C && N0.getOpcode() == ISD::OR) {
 774     ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
 775     ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
 776     if (N00C)
 777       return DAG.getNode(ISD::OR, VT, N0.getOperand(1),
 778                          DAG.getConstant(N1C->getValue()|N00C->getValue(), VT));
 779     if (N01C)
 780       return DAG.getNode(ISD::OR, VT, N0.getOperand(0),
 781                          DAG.getConstant(N1C->getValue()|N01C->getValue(), VT));
 782   }
 783   // fold (or (setcc x), (setcc y)) -> (setcc (or x, y))
 784   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
 785     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
 786     ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
 787
 788     if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
 789         MVT::isInteger(LL.getValueType())) {
 790       // fold (X != 0) | (Y != 0) -> (X|Y != 0)
 791       // fold (X <  0) | (Y <  0) -> (X|Y < 0)
 792       if (cast<ConstantSDNode>(LR)->getValue() == 0 &&
 793           (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) {
 794         SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
 795         WorkList.push_back(ORNode.Val);
 796         return DAG.getSetCC(VT, ORNode, LR, Op1);
 797       }
 798       // fold (X != -1) | (Y != -1) -> (X&Y != -1)
 799       // fold (X >  -1) | (Y >  -1) -> (X&Y >  -1)
 800       if (cast<ConstantSDNode>(LR)->isAllOnesValue() &&
 801           (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) {
 802         SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL);
 803         WorkList.push_back(ANDNode.Val);
 804         return DAG.getSetCC(VT, ANDNode, LR, Op1);
 805       }
 806     }
 807     // canonicalize equivalent to ll == rl
 808     if (LL == RR && LR == RL) {
 809       Op1 = ISD::getSetCCSwappedOperands(Op1);
 810       std::swap(RL, RR);
 811     }
 812     if (LL == RL && LR == RR) {
 813       bool isInteger = MVT::isInteger(LL.getValueType());
 814       ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger);
 815       if (Result != ISD::SETCC_INVALID)
 816         return DAG.getSetCC(N0.getValueType(), LL, LR, Result);
 817     }
 818   }
 819   // fold (or (zext x), (zext y)) -> (zext (or x, y))
 820   if (N0.getOpcode() == ISD::ZERO_EXTEND &&
 821       N1.getOpcode() == ISD::ZERO_EXTEND &&
 822       N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
 823     SDOperand ORNode = DAG.getNode(ISD::OR, N0.getOperand(0).getValueType(),
 824                                    N0.getOperand(0), N1.getOperand(0));
 825     WorkList.push_back(ORNode.Val);
 826     return DAG.getNode(ISD::ZERO_EXTEND, VT, ORNode);
 827   }
 828   return SDOperand();
 829 }
 830
 831 SDOperand DAGCombiner::visitXOR(SDNode *N) {
 832   SDOperand N0 = N->getOperand(0);
 833   SDOperand N1 = N->getOperand(1);
 834   SDOperand LHS, RHS, CC;
 835   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 836   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 837   MVT::ValueType VT = N0.getValueType();
 838
 839   // fold (xor c1, c2) -> c1^c2
 840   if (N0C && N1C)
 841     return DAG.getConstant(N0C->getValue() ^ N1C->getValue(), VT);
 842   // canonicalize constant to RHS
 843   if (N0C && !N1C) {
 844     std::swap(N0, N1);
 845     std::swap(N0C, N1C);
 846   }
 847   // fold (xor x, 0) -> x
 848   if (N1C && N1C->isNullValue())
 849     return N0;
 850   // fold !(x cc y) -> (x !cc y)
 851   if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) {
 852     bool isInt = MVT::isInteger(LHS.getValueType());
 853     ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(),
 854                                                isInt);
 855     if (N0.getOpcode() == ISD::SETCC)
 856       return DAG.getSetCC(VT, LHS, RHS, NotCC);
 857     if (N0.getOpcode() == ISD::SELECT_CC)
 858       return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC);
 859     assert(0 && "Unhandled SetCC Equivalent!");
 860     abort();
 861   }
 862   // fold !(x or y) -> (!x and !y) iff x or y are setcc
 863   if (N1C && N1C->getValue() == 1 &&
 864       (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) {
 865     SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
 866     if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) {
 867       unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND;
 868       LHS = DAG.getNode(ISD::XOR, VT, LHS, N1);  // RHS = ~LHS
 869       RHS = DAG.getNode(ISD::XOR, VT, RHS, N1);  // RHS = ~RHS
 870       WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val);
 871       return DAG.getNode(NewOpcode, VT, LHS, RHS);
 872     }
 873   }
 874   // fold !(x or y) -> (!x and !y) iff x or y are constants
 875   if (N1C && N1C->isAllOnesValue() &&
 876       (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) {
 877     SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
 878     if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) {
 879       unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND;
 880       LHS = DAG.getNode(ISD::XOR, VT, LHS, N1);  // RHS = ~LHS
 881       RHS = DAG.getNode(ISD::XOR, VT, RHS, N1);  // RHS = ~RHS
 882       WorkList.push_back(LHS.Val); WorkList.push_back(RHS.Val);
 883       return DAG.getNode(NewOpcode, VT, LHS, RHS);
 884     }
 885   }
 886   // fold (xor (xor x, c1), c2) -> (xor x, c1^c2)
 887   if (N1C && N0.getOpcode() == ISD::XOR) {
 888     ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
 889     ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
 890     if (N00C)
 891       return DAG.getNode(ISD::XOR, VT, N0.getOperand(1),
 892                          DAG.getConstant(N1C->getValue()^N00C->getValue(), VT));
 893     if (N01C)
 894       return DAG.getNode(ISD::XOR, VT, N0.getOperand(0),
 895                          DAG.getConstant(N1C->getValue()^N01C->getValue(), VT));
 896   }
 897   // fold (xor x, x) -> 0
 898   if (N0 == N1)
 899     return DAG.getConstant(0, VT);
 900   // fold (xor (zext x), (zext y)) -> (zext (xor x, y))
 901   if (N0.getOpcode() == ISD::ZERO_EXTEND &&
 902       N1.getOpcode() == ISD::ZERO_EXTEND &&
 903       N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
 904     SDOperand XORNode = DAG.getNode(ISD::XOR, N0.getOperand(0).getValueType(),
 905                                    N0.getOperand(0), N1.getOperand(0));
 906     WorkList.push_back(XORNode.Val);
 907     return DAG.getNode(ISD::ZERO_EXTEND, VT, XORNode);
 908   }
 909   return SDOperand();
 910 }
 911
 912 SDOperand DAGCombiner::visitSHL(SDNode *N) {
 913   SDOperand N0 = N->getOperand(0);
 914   SDOperand N1 = N->getOperand(1);
 915   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 916   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 917   MVT::ValueType VT = N0.getValueType();
 918   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
 919
 920   // fold (shl c1, c2) -> c1<<c2
 921   if (N0C && N1C)
 922     return DAG.getConstant(N0C->getValue() << N1C->getValue(), VT);
 923   // fold (shl 0, x) -> 0
 924   if (N0C && N0C->isNullValue())
 925     return N0;
 926   // fold (shl x, c >= size(x)) -> undef
 927   if (N1C && N1C->getValue() >= OpSizeInBits)
 928     return DAG.getNode(ISD::UNDEF, VT);
 929   // fold (shl x, 0) -> x
 930   if (N1C && N1C->isNullValue())
 931     return N0;
 932   // if (shl x, c) is known to be zero, return 0
 933   if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI))
 934     return DAG.getConstant(0, VT);
 935   // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2)
 936   if (N1C && N0.getOpcode() == ISD::SHL &&
 937       N0.getOperand(1).getOpcode() == ISD::Constant) {
 938     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
 939     uint64_t c2 = N1C->getValue();
 940     if (c1 + c2 > OpSizeInBits)
 941       return DAG.getConstant(0, VT);
 942     return DAG.getNode(ISD::SHL, VT, N0.getOperand(0),
 943                        DAG.getConstant(c1 + c2, N1.getValueType()));
 944   }
 945   // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or
 946   //                               (srl (and x, -1 << c1), c1-c2)
 947   if (N1C && N0.getOpcode() == ISD::SRL &&
 948       N0.getOperand(1).getOpcode() == ISD::Constant) {
 949     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
 950     uint64_t c2 = N1C->getValue();
 951     SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0),
 952                                  DAG.getConstant(~0ULL << c1, VT));
 953     if (c2 > c1)
 954       return DAG.getNode(ISD::SHL, VT, Mask,
 955                          DAG.getConstant(c2-c1, N1.getValueType()));
 956     else
 957       return DAG.getNode(ISD::SRL, VT, Mask,
 958                          DAG.getConstant(c1-c2, N1.getValueType()));
 959   }
 960   // fold (shl (sra x, c1), c1) -> (and x, -1 << c1)
 961   if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1))
 962     return DAG.getNode(ISD::AND, VT, N0.getOperand(0),
 963                        DAG.getConstant(~0ULL << N1C->getValue(), VT));
 964   return SDOperand();
 965 }
 966
 967 SDOperand DAGCombiner::visitSRA(SDNode *N) {
 968   SDOperand N0 = N->getOperand(0);
 969   SDOperand N1 = N->getOperand(1);
 970   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 971   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 972   MVT::ValueType VT = N0.getValueType();
 973   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
 974
 975   // fold (sra c1, c2) -> c1>>c2
 976   if (N0C && N1C)
 977     return DAG.getConstant(N0C->getSignExtended() >> N1C->getValue(), VT);
 978   // fold (sra 0, x) -> 0
 979   if (N0C && N0C->isNullValue())
 980     return N0;
 981   // fold (sra -1, x) -> -1
 982   if (N0C && N0C->isAllOnesValue())
 983     return N0;
 984   // fold (sra x, c >= size(x)) -> undef
 985   if (N1C && N1C->getValue() >= OpSizeInBits)
 986     return DAG.getNode(ISD::UNDEF, VT);
 987   // fold (sra x, 0) -> x
 988   if (N1C && N1C->isNullValue())
 989     return N0;
 990   // If the sign bit is known to be zero, switch this to a SRL.
 991   if (N1C && MaskedValueIsZero(N0, (1ULL << (OpSizeInBits-1)), TLI))
 992     return DAG.getNode(ISD::SRL, VT, N0, N1);
 993   return SDOperand();
 994 }
 995
 996 SDOperand DAGCombiner::visitSRL(SDNode *N) {
 997   SDOperand N0 = N->getOperand(0);
 998   SDOperand N1 = N->getOperand(1);
 999   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1000   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1001   MVT::ValueType VT = N0.getValueType();
1002   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
1003
1004   // fold (srl c1, c2) -> c1 >>u c2
1005   if (N0C && N1C)
1006     return DAG.getConstant(N0C->getValue() >> N1C->getValue(), VT);
1007   // fold (srl 0, x) -> 0
1008   if (N0C && N0C->isNullValue())
1009     return N0;
1010   // fold (srl x, c >= size(x)) -> undef
1011   if (N1C && N1C->getValue() >= OpSizeInBits)
1012     return DAG.getNode(ISD::UNDEF, VT);
1013   // fold (srl x, 0) -> x
1014   if (N1C && N1C->isNullValue())
1015     return N0;
1016   // if (srl x, c) is known to be zero, return 0
1017   if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI))
1018     return DAG.getConstant(0, VT);
1019   // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2)
1020   if (N1C && N0.getOpcode() == ISD::SRL &&
1021       N0.getOperand(1).getOpcode() == ISD::Constant) {
1022     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
1023     uint64_t c2 = N1C->getValue();
1024     if (c1 + c2 > OpSizeInBits)
1025       return DAG.getConstant(0, VT);
1026     return DAG.getNode(ISD::SRL, VT, N0.getOperand(0),
1027                        DAG.getConstant(c1 + c2, N1.getValueType()));
1028   }
1029   return SDOperand();
1030 }
1031
1032 SDOperand DAGCombiner::visitCTLZ(SDNode *N) {
1033   SDOperand N0 = N->getOperand(0);
1034   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1035
1036   // fold (ctlz c1) -> c2
1037   if (N0C)
1038     return DAG.getConstant(CountLeadingZeros_64(N0C->getValue()),
1039                            N0.getValueType());
1040   return SDOperand();
1041 }
1042
1043 SDOperand DAGCombiner::visitCTTZ(SDNode *N) {
1044   SDOperand N0 = N->getOperand(0);
1045   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1046
1047   // fold (cttz c1) -> c2
1048   if (N0C)
1049     return DAG.getConstant(CountTrailingZeros_64(N0C->getValue()),
1050                            N0.getValueType());
1051   return SDOperand();
1052 }
1053
1054 SDOperand DAGCombiner::visitCTPOP(SDNode *N) {
1055   SDOperand N0 = N->getOperand(0);
1056   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1057
1058   // fold (ctpop c1) -> c2
1059   if (N0C)
1060     return DAG.getConstant(CountPopulation_64(N0C->getValue()),
1061                            N0.getValueType());
1062   return SDOperand();
1063 }
1064
1065 SDOperand DAGCombiner::visitSELECT(SDNode *N) {
1066   SDOperand N0 = N->getOperand(0);
1067   SDOperand N1 = N->getOperand(1);
1068   SDOperand N2 = N->getOperand(2);
1069   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1070   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1071   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
1072   MVT::ValueType VT = N->getValueType(0);
1073
1074   // fold select C, X, X -> X
1075   if (N1 == N2)
1076     return N1;
1077   // fold select true, X, Y -> X
1078   if (N0C && !N0C->isNullValue())
1079     return N1;
1080   // fold select false, X, Y -> Y
1081   if (N0C && N0C->isNullValue())
1082     return N2;
1083   // fold select C, 1, X -> C | X
1084   if (MVT::i1 == VT && N1C && N1C->getValue() == 1)
1085     return DAG.getNode(ISD::OR, VT, N0, N2);
1086   // fold select C, 0, X -> ~C & X
1087   // FIXME: this should check for C type == X type, not i1?
1088   if (MVT::i1 == VT && N1C && N1C->isNullValue()) {
1089     SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
1090     WorkList.push_back(XORNode.Val);
1091     return DAG.getNode(ISD::AND, VT, XORNode, N2);
1092   }
1093   // fold select C, X, 1 -> ~C | X
1094   if (MVT::i1 == VT && N2C && N2C->getValue() == 1) {
1095     SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
1096     WorkList.push_back(XORNode.Val);
1097     return DAG.getNode(ISD::OR, VT, XORNode, N1);
1098   }
1099   // fold select C, X, 0 -> C & X
1100   // FIXME: this should check for C type == X type, not i1?
1101   if (MVT::i1 == VT && N2C && N2C->isNullValue())
1102     return DAG.getNode(ISD::AND, VT, N0, N1);
1103   // fold  X ? X : Y --> X ? 1 : Y --> X | Y
1104   if (MVT::i1 == VT && N0 == N1)
1105     return DAG.getNode(ISD::OR, VT, N0, N2);
1106   // fold X ? Y : X --> X ? Y : 0 --> X & Y
1107   if (MVT::i1 == VT && N0 == N2)
1108     return DAG.getNode(ISD::AND, VT, N0, N1);
1109   // fold selects based on a setcc into other things, such as min/max/abs
1110   if (N0.getOpcode() == ISD::SETCC)
1111     return SimplifySelect(N0, N1, N2);
1112   return SDOperand();
1113 }
1114
1115 SDOperand DAGCombiner::visitSELECT_CC(SDNode *N) {
1116   SDOperand N0 = N->getOperand(0);
1117   SDOperand N1 = N->getOperand(1);
1118   SDOperand N2 = N->getOperand(2);
1119   SDOperand N3 = N->getOperand(3);
1120   SDOperand N4 = N->getOperand(4);
1121   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1122   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1123   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
1124   ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get();
1125
1126   // Determine if the condition we're dealing with is constant
1127   SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
1128   ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
1129
1130   // fold select_cc lhs, rhs, x, x, cc -> x
1131   if (N2 == N3)
1132     return N2;
1133   // fold select_cc into other things, such as min/max/abs
1134   return SimplifySelectCC(N0, N1, N2, N3, CC);
1135 }
1136
1137 SDOperand DAGCombiner::visitSETCC(SDNode *N) {
1138   return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1),
1139                        cast<CondCodeSDNode>(N->getOperand(2))->get());
1140 }
1141
1142 SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) {
1143   SDOperand N0 = N->getOperand(0);
1144   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1145   MVT::ValueType VT = N->getValueType(0);
1146
1147   // fold (sext c1) -> c1
1148   if (N0C)
1149     return DAG.getConstant(N0C->getSignExtended(), VT);
1150   // fold (sext (sext x)) -> (sext x)
1151   if (N0.getOpcode() == ISD::SIGN_EXTEND)
1152     return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0));
1153   return SDOperand();
1154 }
1155
1156 SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) {
1157   SDOperand N0 = N->getOperand(0);
1158   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1159   MVT::ValueType VT = N->getValueType(0);
1160
1161   // fold (zext c1) -> c1
1162   if (N0C)
1163     return DAG.getConstant(N0C->getValue(), VT);
1164   // fold (zext (zext x)) -> (zext x)
1165   if (N0.getOpcode() == ISD::ZERO_EXTEND)
1166     return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0));
1167   return SDOperand();
1168 }
1169
1170 SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) {
1171   SDOperand N0 = N->getOperand(0);
1172   SDOperand N1 = N->getOperand(1);
1173   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1174   MVT::ValueType VT = N->getValueType(0);
1175   MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT();
1176
1177   // fold (sext_in_reg c1) -> c1
1178   if (N0C) {
1179     SDOperand Truncate = DAG.getConstant(N0C->getValue(), EVT);
1180     return DAG.getNode(ISD::SIGN_EXTEND, VT, Truncate);
1181   }
1182   // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt1
1183   if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1184       cast<VTSDNode>(N0.getOperand(1))->getVT() < EVT) {
1185     return N0;
1186   }
1187   // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2
1188   if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1189       EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) {
1190     return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1);
1191   }
1192   // fold (sext_in_reg (assert_sext x)) -> (assert_sext x)
1193   if (N0.getOpcode() == ISD::AssertSext &&
1194       cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) {
1195     return N0;
1196   }
1197   // fold (sext_in_reg (sextload x)) -> (sextload x)
1198   if (N0.getOpcode() == ISD::SEXTLOAD &&
1199       cast<VTSDNode>(N0.getOperand(3))->getVT() <= EVT) {
1200     return N0;
1201   }
1202   // fold (sext_in_reg (setcc x)) -> setcc x iff (setcc x) == 0 or -1
1203   // FIXME: teach isSetCCEquivalent about 0, -1 and then use it here
1204   if (N0.getOpcode() == ISD::SETCC &&
1205       TLI.getSetCCResultContents() ==
1206         TargetLowering::ZeroOrNegativeOneSetCCResult)
1207     return N0;
1208   // FIXME: this code is currently just ported over from SelectionDAG.cpp
1209   // we probably actually want to handle this in two pieces.  Rather than
1210   // checking all the top bits for zero, just check the sign bit here and turn
1211   // it into a zero extend inreg (AND with constant).
1212   // then, let the code for AND figure out if the mask is superfluous rather
1213   // than doing so here.
1214   if (N0.getOpcode() == ISD::AND &&
1215       N0.getOperand(1).getOpcode() == ISD::Constant) {
1216     uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
1217     unsigned NumBits = MVT::getSizeInBits(EVT);
1218     if ((Mask & (~0ULL << (NumBits-1))) == 0)
1219       return N0;
1220   }
1221   return SDOperand();
1222 }
1223
1224 SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) {
1225   SDOperand N0 = N->getOperand(0);
1226   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1227   MVT::ValueType VT = N->getValueType(0);
1228
1229   // noop truncate
1230   if (N0.getValueType() == N->getValueType(0))
1231     return N0;
1232   // fold (truncate c1) -> c1
1233   if (N0C)
1234     return DAG.getConstant(N0C->getValue(), VT);
1235   // fold (truncate (truncate x)) -> (truncate x)
1236   if (N0.getOpcode() == ISD::TRUNCATE)
1237     return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
1238   // fold (truncate (ext x)) -> (ext x) or (truncate x) or x
1239   if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND){
1240     if (N0.getValueType() < VT)
1241       // if the source is smaller than the dest, we still need an extend
1242       return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0));
1243     else if (N0.getValueType() > VT)
1244       // if the source is larger than the dest, than we just need the truncate
1245       return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
1246     else
1247       // if the source and dest are the same type, we can drop both the extend
1248       // and the truncate
1249       return N0.getOperand(0);
1250   }
1251   return SDOperand();
1252 }
1253
1254 SDOperand DAGCombiner::visitFADD(SDNode *N) {
1255   SDOperand N0 = N->getOperand(0);
1256   SDOperand N1 = N->getOperand(1);
1257   MVT::ValueType VT = N->getValueType(0);
1258
1259   if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1260     if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1261       // fold floating point (fadd c1, c2)
1262       return DAG.getConstantFP(N0CFP->getValue() + N1CFP->getValue(),
1263                                N->getValueType(0));
1264     }
1265   // fold (A + (-B)) -> A-B
1266   if (N1.getOpcode() == ISD::FNEG)
1267     return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0));
1268
1269   // fold ((-A) + B) -> B-A
1270   if (N0.getOpcode() == ISD::FNEG)
1271     return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0));
1272
1273   return SDOperand();
1274 }
1275
1276 SDOperand DAGCombiner::visitFSUB(SDNode *N) {
1277   SDOperand N0 = N->getOperand(0);
1278   SDOperand N1 = N->getOperand(1);
1279   MVT::ValueType VT = N->getValueType(0);
1280
1281   if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1282     if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1283       // fold floating point (fsub c1, c2)
1284       return DAG.getConstantFP(N0CFP->getValue() - N1CFP->getValue(),
1285                                N->getValueType(0));
1286     }
1287   // fold (A-(-B)) -> A+B
1288   if (N1.getOpcode() == ISD::FNEG)
1289     return DAG.getNode(ISD::FADD, N0.getValueType(), N0, N1.getOperand(0));
1290
1291   return SDOperand();
1292 }
1293
1294 SDOperand DAGCombiner::visitFMUL(SDNode *N) {
1295   SDOperand N0 = N->getOperand(0);
1296   SDOperand N1 = N->getOperand(1);
1297   MVT::ValueType VT = N->getValueType(0);
1298
1299   if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1300     if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1301       // fold floating point (fmul c1, c2)
1302       return DAG.getConstantFP(N0CFP->getValue() * N1CFP->getValue(),
1303                                N->getValueType(0));
1304     }
1305   return SDOperand();
1306 }
1307
1308 SDOperand DAGCombiner::visitFDIV(SDNode *N) {
1309   SDOperand N0 = N->getOperand(0);
1310   SDOperand N1 = N->getOperand(1);
1311   MVT::ValueType VT = N->getValueType(0);
1312
1313   if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1314     if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1315       // fold floating point (fdiv c1, c2)
1316       return DAG.getConstantFP(N0CFP->getValue() / N1CFP->getValue(),
1317                                N->getValueType(0));
1318     }
1319   return SDOperand();
1320 }
1321
1322 SDOperand DAGCombiner::visitFREM(SDNode *N) {
1323   SDOperand N0 = N->getOperand(0);
1324   SDOperand N1 = N->getOperand(1);
1325   MVT::ValueType VT = N->getValueType(0);
1326
1327   if (ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0))
1328     if (ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1329       // fold floating point (frem c1, c2) -> fmod(c1, c2)
1330       return DAG.getConstantFP(fmod(N0CFP->getValue(),N1CFP->getValue()),
1331                                N->getValueType(0));
1332     }
1333   return SDOperand();
1334 }
1335
1336
1337 SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) {
1338   SDOperand N0 = N->getOperand(0);
1339   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1340
1341   // fold (sint_to_fp c1) -> c1fp
1342   if (N0C)
1343     return DAG.getConstantFP(N0C->getSignExtended(), N->getValueType(0));
1344   return SDOperand();
1345 }
1346
1347 SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) {
1348   SDOperand N0 = N->getOperand(0);
1349   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
1350
1351   // fold (uint_to_fp c1) -> c1fp
1352   if (N0C)
1353     return DAG.getConstantFP(N0C->getValue(), N->getValueType(0));
1354   return SDOperand();
1355 }
1356
1357 SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) {
1358   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1359
1360   // fold (fp_to_sint c1fp) -> c1
1361   if (N0CFP)
1362     return DAG.getConstant((int64_t)N0CFP->getValue(), N->getValueType(0));
1363   return SDOperand();
1364 }
1365
1366 SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) {
1367   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1368
1369   // fold (fp_to_uint c1fp) -> c1
1370   if (N0CFP)
1371     return DAG.getConstant((uint64_t)N0CFP->getValue(), N->getValueType(0));
1372   return SDOperand();
1373 }
1374
1375 SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) {
1376   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1377
1378   // fold (fp_round c1fp) -> c1fp
1379   if (N0CFP)
1380     return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0));
1381   return SDOperand();
1382 }
1383
1384 SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) {
1385   SDOperand N0 = N->getOperand(0);
1386   MVT::ValueType VT = N->getValueType(0);
1387   MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
1388   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
1389
1390   // fold (fp_round_inreg c1fp) -> c1fp
1391   if (N0CFP) {
1392     SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT);
1393     return DAG.getNode(ISD::FP_EXTEND, VT, Round);
1394   }
1395   return SDOperand();
1396 }
1397
1398 SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) {
1399   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1400
1401   // fold (fp_extend c1fp) -> c1fp
1402   if (N0CFP)
1403     return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0));
1404   return SDOperand();
1405 }
1406
1407 SDOperand DAGCombiner::visitFNEG(SDNode *N) {
1408   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1409   // fold (neg c1) -> -c1
1410   if (N0CFP)
1411     return DAG.getConstantFP(-N0CFP->getValue(), N->getValueType(0));
1412   // fold (neg (sub x, y)) -> (sub y, x)
1413   if (N->getOperand(0).getOpcode() == ISD::SUB)
1414     return DAG.getNode(ISD::SUB, N->getValueType(0), N->getOperand(1),
1415                        N->getOperand(0));
1416   // fold (neg (neg x)) -> x
1417   if (N->getOperand(0).getOpcode() == ISD::FNEG)
1418     return N->getOperand(0).getOperand(0);
1419   return SDOperand();
1420 }
1421
1422 SDOperand DAGCombiner::visitFABS(SDNode *N) {
1423   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1424   // fold (fabs c1) -> fabs(c1)
1425   if (N0CFP)
1426     return DAG.getConstantFP(fabs(N0CFP->getValue()), N->getValueType(0));
1427   // fold (fabs (fabs x)) -> (fabs x)
1428   if (N->getOperand(0).getOpcode() == ISD::FABS)
1429     return N->getOperand(0);
1430   // fold (fabs (fneg x)) -> (fabs x)
1431   if (N->getOperand(0).getOpcode() == ISD::FNEG)
1432     return DAG.getNode(ISD::FABS, N->getValueType(0),
1433                        N->getOperand(0).getOperand(0));
1434   return SDOperand();
1435 }
1436
1437 SDOperand DAGCombiner::visitBRCOND(SDNode *N) {
1438   SDOperand Chain = N->getOperand(0);
1439   SDOperand N1 = N->getOperand(1);
1440   SDOperand N2 = N->getOperand(2);
1441   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1442
1443   // never taken branch, fold to chain
1444   if (N1C && N1C->isNullValue())
1445     return Chain;
1446   // unconditional branch
1447   if (N1C && N1C->getValue() == 1)
1448     return DAG.getNode(ISD::BR, MVT::Other, Chain, N2);
1449   return SDOperand();
1450 }
1451
1452 SDOperand DAGCombiner::visitBRCONDTWOWAY(SDNode *N) {
1453   SDOperand Chain = N->getOperand(0);
1454   SDOperand N1 = N->getOperand(1);
1455   SDOperand N2 = N->getOperand(2);
1456   SDOperand N3 = N->getOperand(3);
1457   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
1458
1459   // unconditional branch to true mbb
1460   if (N1C && N1C->getValue() == 1)
1461     return DAG.getNode(ISD::BR, MVT::Other, Chain, N2);
1462   // unconditional branch to false mbb
1463   if (N1C && N1C->isNullValue())
1464     return DAG.getNode(ISD::BR, MVT::Other, Chain, N3);
1465   return SDOperand();
1466 }
1467
1468 // Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB.
1469 //
1470 SDOperand DAGCombiner::visitBR_CC(SDNode *N) {
1471   CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1));
1472   SDOperand CondLHS = N->getOperand(2), CondRHS = N->getOperand(3);
1473
1474   // Use SimplifySetCC  to simplify SETCC's.
1475   SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false);
1476   ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val);
1477
1478   // fold br_cc true, dest -> br dest (unconditional branch)
1479   if (SCCC && SCCC->getValue())
1480     return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0),
1481                        N->getOperand(4));
1482   // fold br_cc false, dest -> unconditional fall through
1483   if (SCCC && SCCC->isNullValue())
1484     return N->getOperand(0);
1485   // fold to a simpler setcc
1486   if (Simp.Val && Simp.getOpcode() == ISD::SETCC)
1487     return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0),
1488                        Simp.getOperand(2), Simp.getOperand(0),
1489                        Simp.getOperand(1), N->getOperand(4));
1490   return SDOperand();
1491 }
1492
1493 SDOperand DAGCombiner::visitBRTWOWAY_CC(SDNode *N) {
1494   SDOperand Chain = N->getOperand(0);
1495   SDOperand CCN = N->getOperand(1);
1496   SDOperand LHS = N->getOperand(2);
1497   SDOperand RHS = N->getOperand(3);
1498   SDOperand N4 = N->getOperand(4);
1499   SDOperand N5 = N->getOperand(5);
1500
1501   SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), LHS, RHS,
1502                                 cast<CondCodeSDNode>(CCN)->get(), false);
1503   ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
1504
1505   // fold select_cc lhs, rhs, x, x, cc -> x
1506   if (N4 == N5)
1507     return DAG.getNode(ISD::BR, MVT::Other, Chain, N4);
1508   // fold select_cc true, x, y -> x
1509   if (SCCC && SCCC->getValue())
1510     return DAG.getNode(ISD::BR, MVT::Other, Chain, N4);
1511   // fold select_cc false, x, y -> y
1512   if (SCCC && SCCC->isNullValue())
1513     return DAG.getNode(ISD::BR, MVT::Other, Chain, N5);
1514   // fold to a simpler setcc
1515   if (SCC.Val && SCC.getOpcode() == ISD::SETCC)
1516     return DAG.getBR2Way_CC(Chain, SCC.getOperand(2), SCC.getOperand(0),
1517                             SCC.getOperand(1), N4, N5);
1518   return SDOperand();
1519 }
1520
1521 SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){
1522   assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!");
1523
1524   SDOperand SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2,
1525                                  cast<CondCodeSDNode>(N0.getOperand(2))->get());
1526   // If we got a simplified select_cc node back from SimplifySelectCC, then
1527   // break it down into a new SETCC node, and a new SELECT node, and then return
1528   // the SELECT node, since we were called with a SELECT node.
1529   if (SCC.Val) {
1530     // Check to see if we got a select_cc back (to turn into setcc/select).
1531     // Otherwise, just return whatever node we got back, like fabs.
1532     if (SCC.getOpcode() == ISD::SELECT_CC) {
1533       SDOperand SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(),
1534                                     SCC.getOperand(0), SCC.getOperand(1),
1535                                     SCC.getOperand(4));
1536       WorkList.push_back(SETCC.Val);
1537       return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2),
1538                          SCC.getOperand(3), SETCC);
1539     }
1540     return SCC;
1541   }
1542   return SDOperand();
1543 }
1544
1545 SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1,
1546                                         SDOperand N2, SDOperand N3,
1547                                         ISD::CondCode CC) {
1548
1549   MVT::ValueType VT = N2.getValueType();
1550   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
1551   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1552   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1553   ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
1554
1555   // Determine if the condition we're dealing with is constant
1556   SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
1557   ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
1558
1559   // fold select_cc true, x, y -> x
1560   if (SCCC && SCCC->getValue())
1561     return N2;
1562   // fold select_cc false, x, y -> y
1563   if (SCCC && SCCC->getValue() == 0)
1564     return N3;
1565
1566   // Check to see if we can simplify the select into an fabs node
1567   if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) {
1568     // Allow either -0.0 or 0.0
1569     if (CFP->getValue() == 0.0) {
1570       // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs
1571       if ((CC == ISD::SETGE || CC == ISD::SETGT) &&
1572           N0 == N2 && N3.getOpcode() == ISD::FNEG &&
1573           N2 == N3.getOperand(0))
1574         return DAG.getNode(ISD::FABS, VT, N0);
1575
1576       // select (setl[te] X, +/-0.0), fneg(X), X -> fabs
1577       if ((CC == ISD::SETLT || CC == ISD::SETLE) &&
1578           N0 == N3 && N2.getOpcode() == ISD::FNEG &&
1579           N2.getOperand(0) == N3)
1580         return DAG.getNode(ISD::FABS, VT, N3);
1581     }
1582   }
1583
1584   // Check to see if we can perform the "gzip trick", transforming
1585   // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A
1586   if (N1C && N1C->isNullValue() && N3C && N3C->isNullValue() &&
1587       MVT::isInteger(N0.getValueType()) &&
1588       MVT::isInteger(N2.getValueType()) && CC == ISD::SETLT) {
1589     MVT::ValueType XType = N0.getValueType();
1590     MVT::ValueType AType = N2.getValueType();
1591     if (XType >= AType) {
1592       // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a
1593       // single-bit constant.  FIXME: remove once the dag combiner
1594       // exists.
1595       if (N2C && ((N2C->getValue() & (N2C->getValue()-1)) == 0)) {
1596         unsigned ShCtV = Log2_64(N2C->getValue());
1597         ShCtV = MVT::getSizeInBits(XType)-ShCtV-1;
1598         SDOperand ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy());
1599         SDOperand Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt);
1600         WorkList.push_back(Shift.Val);
1601         if (XType > AType) {
1602           Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift);
1603           WorkList.push_back(Shift.Val);
1604         }
1605         return DAG.getNode(ISD::AND, AType, Shift, N2);
1606       }
1607       SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
1608                                     DAG.getConstant(MVT::getSizeInBits(XType)-1,
1609                                                     TLI.getShiftAmountTy()));
1610       WorkList.push_back(Shift.Val);
1611       if (XType > AType) {
1612         Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift);
1613         WorkList.push_back(Shift.Val);
1614       }
1615       return DAG.getNode(ISD::AND, AType, Shift, N2);
1616     }
1617   }
1618
1619   // Check to see if this is the equivalent of setcc
1620   // FIXME: Turn all of these into setcc if setcc if setcc is legal
1621   // otherwise, go ahead with the folds.
1622   if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getValue() == 1ULL)) {
1623     MVT::ValueType XType = N0.getValueType();
1624     if (TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultTy())) {
1625       SDOperand Res = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC);
1626       if (Res.getValueType() != VT)
1627         Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res);
1628       return Res;
1629     }
1630
1631     // seteq X, 0 -> srl (ctlz X, log2(size(X)))
1632     if (N1C && N1C->isNullValue() && CC == ISD::SETEQ &&
1633         TLI.isOperationLegal(ISD::CTLZ, XType)) {
1634       SDOperand Ctlz = DAG.getNode(ISD::CTLZ, XType, N0);
1635       return DAG.getNode(ISD::SRL, XType, Ctlz,
1636                          DAG.getConstant(Log2_32(MVT::getSizeInBits(XType)),
1637                                          TLI.getShiftAmountTy()));
1638     }
1639     // setgt X, 0 -> srl (and (-X, ~X), size(X)-1)
1640     if (N1C && N1C->isNullValue() && CC == ISD::SETGT) {
1641       SDOperand NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType),
1642                                     N0);
1643       SDOperand NotN0 = DAG.getNode(ISD::XOR, XType, N0,
1644                                     DAG.getConstant(~0ULL, XType));
1645       return DAG.getNode(ISD::SRL, XType,
1646                          DAG.getNode(ISD::AND, XType, NegN0, NotN0),
1647                          DAG.getConstant(MVT::getSizeInBits(XType)-1,
1648                                          TLI.getShiftAmountTy()));
1649     }
1650     // setgt X, -1 -> xor (srl (X, size(X)-1), 1)
1651     if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) {
1652       SDOperand Sign = DAG.getNode(ISD::SRL, XType, N0,
1653                                    DAG.getConstant(MVT::getSizeInBits(XType)-1,
1654                                                    TLI.getShiftAmountTy()));
1655       return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType));
1656     }
1657   }
1658
1659   // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X ->
1660   // Y = sra (X, size(X)-1); xor (add (X, Y), Y)
1661   if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) &&
1662       N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) {
1663     if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) {
1664       MVT::ValueType XType = N0.getValueType();
1665       if (SubC->isNullValue() && MVT::isInteger(XType)) {
1666         SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
1667                                     DAG.getConstant(MVT::getSizeInBits(XType)-1,
1668                                                     TLI.getShiftAmountTy()));
1669         SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift);
1670         WorkList.push_back(Shift.Val);
1671         WorkList.push_back(Add.Val);
1672         return DAG.getNode(ISD::XOR, XType, Add, Shift);
1673       }
1674     }
1675   }
1676
1677   return SDOperand();
1678 }
1679
1680 SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0,
1681                                      SDOperand N1, ISD::CondCode Cond,
1682                                      bool foldBooleans) {
1683   // These setcc operations always fold.
1684   switch (Cond) {
1685   default: break;
1686   case ISD::SETFALSE:
1687   case ISD::SETFALSE2: return DAG.getConstant(0, VT);
1688   case ISD::SETTRUE:
1689   case ISD::SETTRUE2:  return DAG.getConstant(1, VT);
1690   }
1691
1692   if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
1693     uint64_t C1 = N1C->getValue();
1694     if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val)) {
1695       uint64_t C0 = N0C->getValue();
1696
1697       // Sign extend the operands if required
1698       if (ISD::isSignedIntSetCC(Cond)) {
1699         C0 = N0C->getSignExtended();
1700         C1 = N1C->getSignExtended();
1701       }
1702
1703       switch (Cond) {
1704       default: assert(0 && "Unknown integer setcc!");
1705       case ISD::SETEQ:  return DAG.getConstant(C0 == C1, VT);
1706       case ISD::SETNE:  return DAG.getConstant(C0 != C1, VT);
1707       case ISD::SETULT: return DAG.getConstant(C0 <  C1, VT);
1708       case ISD::SETUGT: return DAG.getConstant(C0 >  C1, VT);
1709       case ISD::SETULE: return DAG.getConstant(C0 <= C1, VT);
1710       case ISD::SETUGE: return DAG.getConstant(C0 >= C1, VT);
1711       case ISD::SETLT:  return DAG.getConstant((int64_t)C0 <  (int64_t)C1, VT);
1712       case ISD::SETGT:  return DAG.getConstant((int64_t)C0 >  (int64_t)C1, VT);
1713       case ISD::SETLE:  return DAG.getConstant((int64_t)C0 <= (int64_t)C1, VT);
1714       case ISD::SETGE:  return DAG.getConstant((int64_t)C0 >= (int64_t)C1, VT);
1715       }
1716     } else {
1717       // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
1718       if (N0.getOpcode() == ISD::ZERO_EXTEND) {
1719         unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType());
1720
1721         // If the comparison constant has bits in the upper part, the
1722         // zero-extended value could never match.
1723         if (C1 & (~0ULL << InSize)) {
1724           unsigned VSize = MVT::getSizeInBits(N0.getValueType());
1725           switch (Cond) {
1726           case ISD::SETUGT:
1727           case ISD::SETUGE:
1728           case ISD::SETEQ: return DAG.getConstant(0, VT);
1729           case ISD::SETULT:
1730           case ISD::SETULE:
1731           case ISD::SETNE: return DAG.getConstant(1, VT);
1732           case ISD::SETGT:
1733           case ISD::SETGE:
1734             // True if the sign bit of C1 is set.
1735             return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT);
1736           case ISD::SETLT:
1737           case ISD::SETLE:
1738             // True if the sign bit of C1 isn't set.
1739             return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT);
1740           default:
1741             break;
1742           }
1743         }
1744
1745         // Otherwise, we can perform the comparison with the low bits.
1746         switch (Cond) {
1747         case ISD::SETEQ:
1748         case ISD::SETNE:
1749         case ISD::SETUGT:
1750         case ISD::SETUGE:
1751         case ISD::SETULT:
1752         case ISD::SETULE:
1753           return DAG.getSetCC(VT, N0.getOperand(0),
1754                           DAG.getConstant(C1, N0.getOperand(0).getValueType()),
1755                           Cond);
1756         default:
1757           break;   // todo, be more careful with signed comparisons
1758         }
1759       } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1760                  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
1761         MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
1762         unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
1763         MVT::ValueType ExtDstTy = N0.getValueType();
1764         unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
1765
1766         // If the extended part has any inconsistent bits, it cannot ever
1767         // compare equal.  In other words, they have to be all ones or all
1768         // zeros.
1769         uint64_t ExtBits =
1770           (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
1771         if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits)
1772           return DAG.getConstant(Cond == ISD::SETNE, VT);
1773
1774         SDOperand ZextOp;
1775         MVT::ValueType Op0Ty = N0.getOperand(0).getValueType();
1776         if (Op0Ty == ExtSrcTy) {
1777           ZextOp = N0.getOperand(0);
1778         } else {
1779           int64_t Imm = ~0ULL >> (64-ExtSrcTyBits);
1780           ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0),
1781                                DAG.getConstant(Imm, Op0Ty));
1782         }
1783         WorkList.push_back(ZextOp.Val);
1784         // Otherwise, make this a use of a zext.
1785         return DAG.getSetCC(VT, ZextOp,
1786                             DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)),
1787                                             ExtDstTy),
1788                             Cond);
1789       }
1790
1791       uint64_t MinVal, MaxVal;
1792       unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0));
1793       if (ISD::isSignedIntSetCC(Cond)) {
1794         MinVal = 1ULL << (OperandBitSize-1);
1795         if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
1796           MaxVal = ~0ULL >> (65-OperandBitSize);
1797         else
1798           MaxVal = 0;
1799       } else {
1800         MinVal = 0;
1801         MaxVal = ~0ULL >> (64-OperandBitSize);
1802       }
1803
1804       // Canonicalize GE/LE comparisons to use GT/LT comparisons.
1805       if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
1806         if (C1 == MinVal) return DAG.getConstant(1, VT);   // X >= MIN --> true
1807         --C1;                                          // X >= C0 --> X > (C0-1)
1808         return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
1809                         (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
1810       }
1811
1812       if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
1813         if (C1 == MaxVal) return DAG.getConstant(1, VT);   // X <= MAX --> true
1814         ++C1;                                          // X <= C0 --> X < (C0+1)
1815         return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
1816                         (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
1817       }
1818
1819       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
1820         return DAG.getConstant(0, VT);      // X < MIN --> false
1821
1822       // Canonicalize setgt X, Min --> setne X, Min
1823       if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
1824         return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
1825
1826       // If we have setult X, 1, turn it into seteq X, 0
1827       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
1828         return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()),
1829                         ISD::SETEQ);
1830       // If we have setugt X, Max-1, turn it into seteq X, Max
1831       else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
1832         return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()),
1833                         ISD::SETEQ);
1834
1835       // If we have "setcc X, C0", check to see if we can shrink the immediate
1836       // by changing cc.
1837
1838       // SETUGT X, SINTMAX  -> SETLT X, 0
1839       if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
1840           C1 == (~0ULL >> (65-OperandBitSize)))
1841         return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()),
1842                             ISD::SETLT);
1843
1844       // FIXME: Implement the rest of these.
1845
1846       // Fold bit comparisons when we can.
1847       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1848           VT == N0.getValueType() && N0.getOpcode() == ISD::AND)
1849         if (ConstantSDNode *AndRHS =
1850                     dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
1851           if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
1852             // Perform the xform if the AND RHS is a single bit.
1853             if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
1854               return DAG.getNode(ISD::SRL, VT, N0,
1855                              DAG.getConstant(Log2_64(AndRHS->getValue()),
1856                                                    TLI.getShiftAmountTy()));
1857             }
1858           } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) {
1859             // (X & 8) == 8  -->  (X & 8) >> 3
1860             // Perform the xform if C1 is a single bit.
1861             if ((C1 & (C1-1)) == 0) {
1862               return DAG.getNode(ISD::SRL, VT, N0,
1863                              DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy()));
1864             }
1865           }
1866         }
1867     }
1868   } else if (isa<ConstantSDNode>(N0.Val)) {
1869       // Ensure that the constant occurs on the RHS.
1870     return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
1871   }
1872
1873   if (ConstantFPSDNode *N0C = dyn_cast<ConstantFPSDNode>(N0.Val))
1874     if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) {
1875       double C0 = N0C->getValue(), C1 = N1C->getValue();
1876
1877       switch (Cond) {
1878       default: break; // FIXME: Implement the rest of these!
1879       case ISD::SETEQ:  return DAG.getConstant(C0 == C1, VT);
1880       case ISD::SETNE:  return DAG.getConstant(C0 != C1, VT);
1881       case ISD::SETLT:  return DAG.getConstant(C0 < C1, VT);
1882       case ISD::SETGT:  return DAG.getConstant(C0 > C1, VT);
1883       case ISD::SETLE:  return DAG.getConstant(C0 <= C1, VT);
1884       case ISD::SETGE:  return DAG.getConstant(C0 >= C1, VT);
1885       }
1886     } else {
1887       // Ensure that the constant occurs on the RHS.
1888       return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
1889     }
1890
1891   if (N0 == N1) {
1892     // We can always fold X == Y for integer setcc's.
1893     if (MVT::isInteger(N0.getValueType()))
1894       return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
1895     unsigned UOF = ISD::getUnorderedFlavor(Cond);
1896     if (UOF == 2)   // FP operators that are undefined on NaNs.
1897       return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
1898     if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
1899       return DAG.getConstant(UOF, VT);
1900     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
1901     // if it is not already.
1902     ISD::CondCode NewCond = UOF == 0 ? ISD::SETUO : ISD::SETO;
1903     if (NewCond != Cond)
1904       return DAG.getSetCC(VT, N0, N1, NewCond);
1905   }
1906
1907   if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
1908       MVT::isInteger(N0.getValueType())) {
1909     if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
1910         N0.getOpcode() == ISD::XOR) {
1911       // Simplify (X+Y) == (X+Z) -->  Y == Z
1912       if (N0.getOpcode() == N1.getOpcode()) {
1913         if (N0.getOperand(0) == N1.getOperand(0))
1914           return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond);
1915         if (N0.getOperand(1) == N1.getOperand(1))
1916           return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond);
1917         if (isCommutativeBinOp(N0.getOpcode())) {
1918           // If X op Y == Y op X, try other combinations.
1919           if (N0.getOperand(0) == N1.getOperand(1))
1920             return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond);
1921           if (N0.getOperand(1) == N1.getOperand(0))
1922             return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond);
1923         }
1924       }
1925
1926       // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.  Common for condcodes.
1927       if (N0.getOpcode() == ISD::XOR)
1928         if (ConstantSDNode *XORC = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
1929           if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) {
1930             // If we know that all of the inverted bits are zero, don't bother
1931             // performing the inversion.
1932             if (MaskedValueIsZero(N0.getOperand(0), ~XORC->getValue(), TLI))
1933               return DAG.getSetCC(VT, N0.getOperand(0),
1934                               DAG.getConstant(XORC->getValue()^RHSC->getValue(),
1935                                               N0.getValueType()), Cond);
1936           }
1937
1938       // Simplify (X+Z) == X -->  Z == 0
1939       if (N0.getOperand(0) == N1)
1940         return DAG.getSetCC(VT, N0.getOperand(1),
1941                         DAG.getConstant(0, N0.getValueType()), Cond);
1942       if (N0.getOperand(1) == N1) {
1943         if (isCommutativeBinOp(N0.getOpcode()))
1944           return DAG.getSetCC(VT, N0.getOperand(0),
1945                           DAG.getConstant(0, N0.getValueType()), Cond);
1946         else {
1947           assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
1948           // (Z-X) == X  --> Z == X<<1
1949           SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(),
1950                                      N1,
1951                                      DAG.getConstant(1,TLI.getShiftAmountTy()));
1952           WorkList.push_back(SH.Val);
1953           return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond);
1954         }
1955       }
1956     }
1957
1958     if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
1959         N1.getOpcode() == ISD::XOR) {
1960       // Simplify  X == (X+Z) -->  Z == 0
1961       if (N1.getOperand(0) == N0) {
1962         return DAG.getSetCC(VT, N1.getOperand(1),
1963                         DAG.getConstant(0, N1.getValueType()), Cond);
1964       } else if (N1.getOperand(1) == N0) {
1965         if (isCommutativeBinOp(N1.getOpcode())) {
1966           return DAG.getSetCC(VT, N1.getOperand(0),
1967                           DAG.getConstant(0, N1.getValueType()), Cond);
1968         } else {
1969           assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
1970           // X == (Z-X)  --> X<<1 == Z
1971           SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0,
1972                                      DAG.getConstant(1,TLI.getShiftAmountTy()));
1973           WorkList.push_back(SH.Val);
1974           return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond);
1975         }
1976       }
1977     }
1978   }
1979
1980   // Fold away ALL boolean setcc's.
1981   SDOperand Temp;
1982   if (N0.getValueType() == MVT::i1 && foldBooleans) {
1983     switch (Cond) {
1984     default: assert(0 && "Unknown integer setcc!");
1985     case ISD::SETEQ:  // X == Y  -> (X^Y)^1
1986       Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
1987       N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1));
1988       WorkList.push_back(Temp.Val);
1989       break;
1990     case ISD::SETNE:  // X != Y   -->  (X^Y)
1991       N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
1992       break;
1993     case ISD::SETGT:  // X >s Y   -->  X == 0 & Y == 1  -->  X^1 & Y
1994     case ISD::SETULT: // X <u Y   -->  X == 0 & Y == 1  -->  X^1 & Y
1995       Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
1996       N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp);
1997       WorkList.push_back(Temp.Val);
1998       break;
1999     case ISD::SETLT:  // X <s Y   --> X == 1 & Y == 0  -->  Y^1 & X
2000     case ISD::SETUGT: // X >u Y   --> X == 1 & Y == 0  -->  Y^1 & X
2001       Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
2002       N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp);
2003       WorkList.push_back(Temp.Val);
2004       break;
2005     case ISD::SETULE: // X <=u Y  --> X == 0 | Y == 1  -->  X^1 | Y
2006     case ISD::SETGE:  // X >=s Y  --> X == 0 | Y == 1  -->  X^1 | Y
2007       Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
2008       N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp);
2009       WorkList.push_back(Temp.Val);
2010       break;
2011     case ISD::SETUGE: // X >=u Y  --> X == 1 | Y == 0  -->  Y^1 | X
2012     case ISD::SETLE:  // X <=s Y  --> X == 1 | Y == 0  -->  Y^1 | X
2013       Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
2014       N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp);
2015       break;
2016     }
2017     if (VT != MVT::i1) {
2018       WorkList.push_back(N0.Val);
2019       // FIXME: If running after legalize, we probably can't do this.
2020       N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
2021     }
2022     return N0;
2023   }
2024
2025   // Could not fold it.
2026   return SDOperand();
2027 }
2028
2029 // SelectionDAG::Combine - This is the entry point for the file.
2030 //
2031 void SelectionDAG::Combine(bool RunningAfterLegalize) {
2032   /// run - This is the main entry point to this class.
2033   ///
2034   DAGCombiner(*this).Run(RunningAfterLegalize);
2035 }