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: mul (x, const) -> shifts + adds
  24 // FIXME: undef values
  25 // FIXME: zero extend when top bits are 0 -> drop it ?
  26 // FIXME: make truncate see through SIGN_EXTEND and AND
  27 // FIXME: sext_in_reg(setcc) on targets that return zero or one, and where
  28 //        EVT != MVT::i1 can drop the sext.
  29 // FIXME: (or x, c) -> c iff maskedValueIsZero(x, ~c)
  30 // FIXME: MaskedValueIsZero can see through SRL, so it should be sufficient to:
  31 //if (N1C && MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits),TLI))
  32 //  return DAG.getConstant(0, VT).Val;
  33 // FIXME: (sra (sra x, c1), c2) -> (sra x, c1+c2)
  34 // FIXME: verify that getNode can't return extends with an operand whose type
  35 //        is >= to that of the extend.
  36 // FIXME: divide by zero is currently left unfolded.  do we want to turn this
  37 //        into an undef?
  38 //
  39 //===----------------------------------------------------------------------===//
  40
  41 #define DEBUG_TYPE "dagcombine"
  42 #include "llvm/ADT/Statistic.h"
  43 #include "llvm/CodeGen/SelectionDAG.h"
  44 #include "llvm/Support/MathExtras.h"
  45 #include "llvm/Target/TargetLowering.h"
  46 #include <cmath>
  47 using namespace llvm;
  48
  49 namespace {
  50   Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined");
  51
  52   class DAGCombiner {
  53     SelectionDAG &DAG;
  54     TargetLowering &TLI;
  55     bool AfterLegalize;
  56
  57     // Worklist of all of the nodes that need to be simplified.
  58     std::vector<SDNode*> WorkList;
  59
  60     /// AddUsersToWorkList - When an instruction is simplified, add all users of
  61     /// the instruction to the work lists because they might get more simplified
  62     /// now.
  63     ///
  64     void AddUsersToWorkList(SDNode *N) {
  65       for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
  66            UI != UE; ++UI)
  67         WorkList.push_back(*UI);
  68     }
  69
  70     /// removeFromWorkList - remove all instances of N from the worklist.
  71     void removeFromWorkList(SDNode *N) {
  72       WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N),
  73                      WorkList.end());
  74     }
  75
  76     /// visit - call the node-specific routine that knows how to fold each
  77     /// particular type of node.
  78     SDNode *visit(SDNode *N);
  79
  80     // Visitation implementation - Implement dag node combining for different
  81     // node types.  The semantics are as follows:
  82     // Return Value:
  83     //    null        - No change was made
  84     //   otherwise    - Node N should be replaced by the returned node.
  85     //
  86     SDNode *visitTokenFactor(SDNode *N);
  87     SDNode *visitADD(SDNode *N);
  88     SDNode *visitSUB(SDNode *N);
  89     SDNode *visitMUL(SDNode *N);
  90     SDNode *visitSDIV(SDNode *N);
  91     SDNode *visitUDIV(SDNode *N);
  92     SDNode *visitSREM(SDNode *N);
  93     SDNode *visitUREM(SDNode *N);
  94     SDNode *visitMULHU(SDNode *N);
  95     SDNode *visitMULHS(SDNode *N);
  96     SDNode *visitAND(SDNode *N);
  97     SDNode *visitOR(SDNode *N);
  98     SDNode *visitXOR(SDNode *N);
  99     SDNode *visitSHL(SDNode *N);
 100     SDNode *visitSRA(SDNode *N);
 101     SDNode *visitSRL(SDNode *N);
 102     SDNode *visitCTLZ(SDNode *N);
 103     SDNode *visitCTTZ(SDNode *N);
 104     SDNode *visitCTPOP(SDNode *N);
 105     // select
 106     // select_cc
 107     // setcc
 108     SDNode *visitSIGN_EXTEND(SDNode *N);
 109     SDNode *visitZERO_EXTEND(SDNode *N);
 110     SDNode *visitSIGN_EXTEND_INREG(SDNode *N);
 111     SDNode *visitTRUNCATE(SDNode *N);
 112     SDNode *visitSINT_TO_FP(SDNode *N);
 113     SDNode *visitUINT_TO_FP(SDNode *N);
 114     SDNode *visitFP_TO_SINT(SDNode *N);
 115     SDNode *visitFP_TO_UINT(SDNode *N);
 116     SDNode *visitFP_ROUND(SDNode *N);
 117     SDNode *visitFP_ROUND_INREG(SDNode *N);
 118     SDNode *visitFP_EXTEND(SDNode *N);
 119     SDNode *visitFNEG(SDNode *N);
 120     SDNode *visitFABS(SDNode *N);
 121     // brcond
 122     // brcondtwoway
 123     // br_cc
 124     // brtwoway_cc
 125 public:
 126     DAGCombiner(SelectionDAG &D)
 127       : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {}
 128
 129     /// Run - runs the dag combiner on all nodes in the work list
 130     void Run(bool RunningAfterLegalize);
 131   };
 132 }
 133
 134 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
 135 /// this predicate to simplify operations downstream.  V and Mask are known to
 136 /// be the same type.
 137 static bool MaskedValueIsZero(const SDOperand &Op, uint64_t Mask,
 138                               const TargetLowering &TLI) {
 139   unsigned SrcBits;
 140   if (Mask == 0) return true;
 141
 142   // If we know the result of a setcc has the top bits zero, use this info.
 143   switch (Op.getOpcode()) {
 144   case ISD::Constant:
 145     return (cast<ConstantSDNode>(Op)->getValue() & Mask) == 0;
 146   case ISD::SETCC:
 147     // FIXME: teach this about non ZeroOrOne values, such as 0 or -1
 148     return ((Mask & 1) == 0) &&
 149     TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult;
 150   case ISD::ZEXTLOAD:
 151     SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(3))->getVT());
 152     return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits.
 153   case ISD::ZERO_EXTEND:
 154     SrcBits = MVT::getSizeInBits(Op.getOperand(0).getValueType());
 155     return MaskedValueIsZero(Op.getOperand(0),Mask & ((1ULL << SrcBits)-1),TLI);
 156   case ISD::AssertZext:
 157     SrcBits = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
 158     return (Mask & ((1ULL << SrcBits)-1)) == 0; // Returning only the zext bits.
 159   case ISD::AND:
 160     // (X & C1) & C2 == 0   iff   C1 & C2 == 0.
 161     if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1)))
 162       return MaskedValueIsZero(Op.getOperand(0),AndRHS->getValue() & Mask, TLI);
 163     // FALL THROUGH
 164   case ISD::OR:
 165   case ISD::XOR:
 166     return MaskedValueIsZero(Op.getOperand(0), Mask, TLI) &&
 167     MaskedValueIsZero(Op.getOperand(1), Mask, TLI);
 168   case ISD::SELECT:
 169     return MaskedValueIsZero(Op.getOperand(1), Mask, TLI) &&
 170     MaskedValueIsZero(Op.getOperand(2), Mask, TLI);
 171   case ISD::SELECT_CC:
 172     return MaskedValueIsZero(Op.getOperand(2), Mask, TLI) &&
 173     MaskedValueIsZero(Op.getOperand(3), Mask, TLI);
 174   case ISD::SRL:
 175     // (ushr X, C1) & C2 == 0   iff  X & (C2 << C1) == 0
 176     if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 177       uint64_t NewVal = Mask << ShAmt->getValue();
 178       SrcBits = MVT::getSizeInBits(Op.getValueType());
 179       if (SrcBits != 64) NewVal &= (1ULL << SrcBits)-1;
 180       return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI);
 181     }
 182     return false;
 183   case ISD::SHL:
 184     // (ushl X, C1) & C2 == 0   iff  X & (C2 >> C1) == 0
 185     if (ConstantSDNode *ShAmt = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 186       uint64_t NewVal = Mask >> ShAmt->getValue();
 187       return MaskedValueIsZero(Op.getOperand(0), NewVal, TLI);
 188     }
 189     return false;
 190   case ISD::CTTZ:
 191   case ISD::CTLZ:
 192   case ISD::CTPOP:
 193     // Bit counting instructions can not set the high bits of the result
 194     // register.  The max number of bits sets depends on the input.
 195     return (Mask & (MVT::getSizeInBits(Op.getValueType())*2-1)) == 0;
 196
 197     // TODO we could handle some SRA cases here.
 198   default: break;
 199   }
 200   return false;
 201 }
 202
 203 // isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc
 204 // that selects between the values 1 and 0, making it equivalent to a setcc.
 205 // Also, set the incoming LHS, RHS, and CC references to the appropriate
 206 // nodes based on the type of node we are checking.  This simplifies life a
 207 // bit for the callers.
 208 static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS,
 209                               SDOperand &CC) {
 210   if (N.getOpcode() == ISD::SETCC) {
 211     LHS = N.getOperand(0);
 212     RHS = N.getOperand(1);
 213     CC  = N.getOperand(2);
 214     return true;
 215   }
 216   if (N.getOpcode() == ISD::SELECT_CC &&
 217       N.getOperand(2).getOpcode() == ISD::Constant &&
 218       N.getOperand(3).getOpcode() == ISD::Constant &&
 219       cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 &&
 220       cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) {
 221     LHS = N.getOperand(0);
 222     RHS = N.getOperand(1);
 223     CC  = N.getOperand(4);
 224     return true;
 225   }
 226   return false;
 227 }
 228
 229 // isInvertibleForFree - Return true if there is no cost to emitting the logical
 230 // inverse of this node.
 231 static bool isInvertibleForFree(SDOperand N) {
 232   SDOperand N0, N1, N2;
 233   if (isa<ConstantSDNode>(N.Val)) return true;
 234   if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse())
 235     return true;
 236   return false;
 237 }
 238
 239 void DAGCombiner::Run(bool RunningAfterLegalize) {
 240   // set the instance variable, so that the various visit routines may use it.
 241   AfterLegalize = RunningAfterLegalize;
 242
 243   // Add all the dag nodes to the worklist.
 244   WorkList.insert(WorkList.end(), DAG.allnodes_begin(), DAG.allnodes_end());
 245
 246   // while the worklist isn't empty, inspect the node on the end of it and
 247   // try and combine it.
 248   while (!WorkList.empty()) {
 249     SDNode *N = WorkList.back();
 250     WorkList.pop_back();
 251
 252     // If N has no uses, it is dead.  Make sure to revisit all N's operands once
 253     // N is deleted from the DAG, since they too may now be dead.
 254     if (N->use_empty()) {
 255       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 256         WorkList.push_back(N->getOperand(i).Val);
 257
 258       DAG.DeleteNode(N);
 259       removeFromWorkList(N);
 260       continue;
 261     }
 262
 263     if (SDNode *Result = visit(N)) {
 264       ++NodesCombined;
 265       // If we get back the same node we passed in, rather than a new node or
 266       // zero, we know that the node must have defined multiple values and
 267       // CombineTo was used.  Since CombineTo takes care of the worklist
 268       // mechanics for us, we have no work to do in this case.
 269       if (Result != N) {
 270         DAG.ReplaceAllUsesWith(N, Result);
 271
 272         // Push the new node and any users onto the worklist
 273         WorkList.push_back(Result);
 274         AddUsersToWorkList(Result);
 275
 276         // Nodes can end up on the worklist more than once.  Make sure we do
 277         // not process a node that has been replaced.
 278         removeFromWorkList(N);
 279       }
 280     }
 281   }
 282 }
 283
 284 SDNode *DAGCombiner::visit(SDNode *N) {
 285   switch(N->getOpcode()) {
 286   default: break;
 287   case ISD::TokenFactor:        return visitTokenFactor(N);
 288   case ISD::ADD:                return visitADD(N);
 289   case ISD::SUB:                return visitSUB(N);
 290   case ISD::MUL:                return visitMUL(N);
 291   case ISD::SDIV:               return visitSDIV(N);
 292   case ISD::UDIV:               return visitUDIV(N);
 293   case ISD::SREM:               return visitSREM(N);
 294   case ISD::UREM:               return visitUREM(N);
 295   case ISD::MULHU:              return visitMULHU(N);
 296   case ISD::MULHS:              return visitMULHS(N);
 297   case ISD::AND:                return visitAND(N);
 298   case ISD::OR:                 return visitOR(N);
 299   case ISD::XOR:                return visitXOR(N);
 300   case ISD::SHL:                return visitSHL(N);
 301   case ISD::SRA:                return visitSRA(N);
 302   case ISD::SRL:                return visitSRL(N);
 303   case ISD::CTLZ:               return visitCTLZ(N);
 304   case ISD::CTTZ:               return visitCTTZ(N);
 305   case ISD::CTPOP:              return visitCTPOP(N);
 306   case ISD::SIGN_EXTEND:        return visitSIGN_EXTEND(N);
 307   case ISD::ZERO_EXTEND:        return visitZERO_EXTEND(N);
 308   case ISD::SIGN_EXTEND_INREG:  return visitSIGN_EXTEND_INREG(N);
 309   case ISD::TRUNCATE:           return visitTRUNCATE(N);
 310   case ISD::SINT_TO_FP:         return visitSINT_TO_FP(N);
 311   case ISD::UINT_TO_FP:         return visitUINT_TO_FP(N);
 312   case ISD::FP_TO_SINT:         return visitFP_TO_SINT(N);
 313   case ISD::FP_TO_UINT:         return visitFP_TO_UINT(N);
 314   case ISD::FP_ROUND:           return visitFP_ROUND(N);
 315   case ISD::FP_ROUND_INREG:     return visitFP_ROUND_INREG(N);
 316   case ISD::FP_EXTEND:          return visitFP_EXTEND(N);
 317   case ISD::FNEG:               return visitFNEG(N);
 318   case ISD::FABS:               return visitFABS(N);
 319   }
 320   return 0;
 321 }
 322
 323 SDNode *DAGCombiner::visitTokenFactor(SDNode *N) {
 324   // If the token factor only has one operand, fold TF(x) -> x
 325   if (N->getNumOperands() == 1)
 326     return N->getOperand(0).Val;
 327
 328   // If the token factor has two operands and one is the entry token, replace
 329   // the token factor with the other operand.
 330   if (N->getNumOperands() == 2) {
 331     if (N->getOperand(0).getOpcode() == ISD::EntryToken)
 332       return N->getOperand(1).Val;
 333     if (N->getOperand(1).getOpcode() == ISD::EntryToken)
 334       return N->getOperand(0).Val;
 335   }
 336   return 0;
 337 }
 338
 339 SDNode *DAGCombiner::visitADD(SDNode *N) {
 340   SDOperand N0 = N->getOperand(0);
 341   SDOperand N1 = N->getOperand(1);
 342   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 343   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 344   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
 345   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
 346
 347   // fold (add c1, c2) -> c1+c2
 348   if (N0C && N1C)
 349     return DAG.getConstant(N0C->getValue() + N1C->getValue(),
 350                            N->getValueType(0)).Val;
 351   // fold (add x, 0) -> x
 352   if (N1C && N1C->isNullValue())
 353     return N0.Val;
 354   // fold floating point (add c1, c2) -> c1+c2
 355   if (N0CFP && N1CFP)
 356     return DAG.getConstantFP(N0CFP->getValue() + N1CFP->getValue(),
 357                              N->getValueType(0)).Val;
 358   // fold (A + (-B)) -> A-B
 359   if (N1.getOpcode() == ISD::FNEG)
 360     return DAG.getNode(ISD::SUB, N->getValueType(0), N0, N1.getOperand(0)).Val;
 361   // fold ((-A) + B) -> B-A
 362   if (N0.getOpcode() == ISD::FNEG)
 363     return DAG.getNode(ISD::SUB, N->getValueType(0), N1, N0.getOperand(0)).Val;
 364   // fold ((0-A) + B) -> B-A
 365   if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) &&
 366       cast<ConstantSDNode>(N0.getOperand(0))->isNullValue())
 367     return DAG.getNode(ISD::SUB, N->getValueType(0), N1, N0.getOperand(1)).Val;
 368   // fold (A + (0-B)) -> A-B
 369   if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) &&
 370       cast<ConstantSDNode>(N1.getOperand(0))->isNullValue())
 371     return DAG.getNode(ISD::SUB, N->getValueType(0), N0, N1.getOperand(1)).Val;
 372   // fold (A+(B-A)) -> B for non-fp types
 373   if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1) &&
 374       !MVT::isFloatingPoint(N1.getValueType()))
 375     return N1.getOperand(0).Val;
 376   return 0;
 377 }
 378
 379 SDNode *DAGCombiner::visitSUB(SDNode *N) {
 380   SDOperand N0 = N->getOperand(0);
 381   SDOperand N1 = N->getOperand(1);
 382   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
 383   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 384   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0.Val);
 385   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
 386
 387   // fold (sub c1, c2) -> c1-c2
 388   if (N0C && N1C)
 389     return DAG.getConstant(N0C->getValue() - N1C->getValue(),
 390                            N->getValueType(0)).Val;
 391   // fold (sub x, 0) -> x
 392   if (N1C && N1C->isNullValue())
 393     return N0.Val;
 394   // fold floating point (sub c1, c2) -> c1-c2
 395   if (N0CFP && N1CFP)
 396     return DAG.getConstantFP(N0CFP->getValue() - N1CFP->getValue(),
 397                              N->getValueType(0)).Val;
 398   // fold (A+B)-A -> B
 399   if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1 &&
 400       !MVT::isFloatingPoint(N1.getValueType()))
 401     return N0.getOperand(1).Val;
 402   // fold (A+B)-B -> A
 403   if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1 &&
 404       !MVT::isFloatingPoint(N1.getValueType()))
 405     return N0.getOperand(0).Val;
 406   // fold (A-(-B)) -> A+B
 407   if (N1.getOpcode() == ISD::FNEG)
 408     return DAG.getNode(ISD::ADD, N0.getValueType(), N0, N1.getOperand(0)).Val;
 409   return 0;
 410 }
 411
 412 SDNode *DAGCombiner::visitMUL(SDNode *N) {
 413   SDOperand N0 = N->getOperand(0);
 414   SDOperand N1 = N->getOperand(1);
 415   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 416   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 417   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
 418   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
 419
 420   // fold (mul c1, c2) -> c1*c2
 421   if (N0C && N1C)
 422     return DAG.getConstant(N0C->getValue() * N1C->getValue(),
 423                            N->getValueType(0)).Val;
 424   // fold (mul x, 0) -> 0
 425   if (N1C && N1C->isNullValue())
 426     return N1.Val;
 427   // fold (mul x, -1) -> 0-x
 428   if (N1C && N1C->isAllOnesValue())
 429     return DAG.getNode(ISD::SUB, N->getValueType(0),
 430                        DAG.getConstant(0, N->getValueType(0)), N0).Val;
 431   // fold (mul x, (1 << c)) -> x << c
 432   if (N1C && isPowerOf2_64(N1C->getValue()))
 433     return DAG.getNode(ISD::SHL, N->getValueType(0), N0,
 434                        DAG.getConstant(Log2_64(N1C->getValue()),
 435                                        TLI.getShiftAmountTy())).Val;
 436   // fold floating point (mul c1, c2) -> c1*c2
 437   if (N0CFP && N1CFP)
 438     return DAG.getConstantFP(N0CFP->getValue() * N1CFP->getValue(),
 439                              N->getValueType(0)).Val;
 440   return 0;
 441 }
 442
 443 SDNode *DAGCombiner::visitSDIV(SDNode *N) {
 444   SDOperand N0 = N->getOperand(0);
 445   SDOperand N1 = N->getOperand(1);
 446   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
 447   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 448   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0.Val);
 449   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
 450
 451   // fold (sdiv c1, c2) -> c1/c2
 452   if (N0C && N1C && !N1C->isNullValue())
 453     return DAG.getConstant(N0C->getSignExtended() / N1C->getSignExtended(),
 454                            N->getValueType(0)).Val;
 455   // fold floating point (sdiv c1, c2) -> c1/c2
 456   if (N0CFP && N1CFP)
 457     return DAG.getConstantFP(N0CFP->getValue() / N1CFP->getValue(),
 458                              N->getValueType(0)).Val;
 459   return 0;
 460 }
 461
 462 SDNode *DAGCombiner::visitUDIV(SDNode *N) {
 463   SDOperand N0 = N->getOperand(0);
 464   SDOperand N1 = N->getOperand(1);
 465   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
 466   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 467
 468   // fold (udiv c1, c2) -> c1/c2
 469   if (N0C && N1C && !N1C->isNullValue())
 470     return DAG.getConstant(N0C->getValue() / N1C->getValue(),
 471                            N->getValueType(0)).Val;
 472   // fold (udiv x, (1 << c)) -> x >>u c
 473   if (N1C && isPowerOf2_64(N1C->getValue()))
 474     return DAG.getNode(ISD::SRL, N->getValueType(0), N0,
 475                        DAG.getConstant(Log2_64(N1C->getValue()),
 476                                        TLI.getShiftAmountTy())).Val;
 477   return 0;
 478 }
 479
 480 SDNode *DAGCombiner::visitSREM(SDNode *N) {
 481   SDOperand N0 = N->getOperand(0);
 482   SDOperand N1 = N->getOperand(1);
 483   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 484   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 485   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
 486   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
 487
 488   // fold (srem c1, c2) -> c1%c2
 489   if (N0C && N1C && !N1C->isNullValue())
 490     return DAG.getConstant(N0C->getSignExtended() % N1C->getSignExtended(),
 491                            N->getValueType(0)).Val;
 492   // fold floating point (srem c1, c2) -> fmod(c1, c2)
 493   if (N0CFP && N1CFP)
 494     return DAG.getConstantFP(fmod(N0CFP->getValue(),N1CFP->getValue()),
 495                              N->getValueType(0)).Val;
 496   return 0;
 497 }
 498
 499 SDNode *DAGCombiner::visitUREM(SDNode *N) {
 500   SDOperand N0 = N->getOperand(0);
 501   SDOperand N1 = N->getOperand(1);
 502   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 503   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 504
 505   // fold (urem c1, c2) -> c1%c2
 506   if (N0C && N1C && !N1C->isNullValue())
 507     return DAG.getConstant(N0C->getValue() % N1C->getValue(),
 508                            N->getValueType(0)).Val;
 509   // FIXME: c2 power of 2 -> mask?
 510   return 0;
 511 }
 512
 513 SDNode *DAGCombiner::visitMULHS(SDNode *N) {
 514   SDOperand N0 = N->getOperand(0);
 515   SDOperand N1 = N->getOperand(1);
 516   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 517
 518   // fold (mulhs x, 0) -> 0
 519   if (N1C && N1C->isNullValue())
 520     return N1.Val;
 521
 522   // fold (mulhs x, 1) -> (sra x, size(x)-1)
 523   if (N1C && N1C->getValue() == 1)
 524     return DAG.getNode(ISD::SRA, N0.getValueType(), N0,
 525                        DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1,
 526                                        TLI.getShiftAmountTy())).Val;
 527   return 0;
 528 }
 529
 530 SDNode *DAGCombiner::visitMULHU(SDNode *N) {
 531   SDOperand N0 = N->getOperand(0);
 532   SDOperand N1 = N->getOperand(1);
 533   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 534
 535   // fold (mulhu x, 0) -> 0
 536   if (N1C && N1C->isNullValue())
 537     return N1.Val;
 538
 539   // fold (mulhu x, 1) -> 0
 540   if (N1C && N1C->getValue() == 1)
 541     return DAG.getConstant(0, N0.getValueType()).Val;
 542   return 0;
 543 }
 544
 545 SDNode *DAGCombiner::visitAND(SDNode *N) {
 546   SDOperand N0 = N->getOperand(0);
 547   SDOperand N1 = N->getOperand(1);
 548   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 549   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 550   MVT::ValueType VT = N1.getValueType();
 551
 552   // fold (and c1, c2) -> c1&c2
 553   if (N0C && N1C)
 554     return DAG.getConstant(N0C->getValue() & N1C->getValue(), VT).Val;
 555   // fold (and x, -1) -> x
 556   if (N1C && N1C->isAllOnesValue())
 557     return N0.Val;
 558   // fold (and x, 0) -> 0
 559   if (N1C && MaskedValueIsZero(N0, N1C->getValue(), TLI))
 560     return DAG.getConstant(0, VT).Val;
 561   // fold (and x, mask containing x) -> x
 562   if (N1C) {
 563     uint64_t NotC2 = ~N1C->getValue();
 564     NotC2 &= ~0ULL >> (64-MVT::getSizeInBits(VT));
 565     if (MaskedValueIsZero(N0, NotC2, TLI))
 566       return N0.Val;
 567   }
 568   // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1)
 569   if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG) {
 570     unsigned ExtendBits =
 571     MVT::getSizeInBits(cast<VTSDNode>(N0.getOperand(1))->getVT());
 572     if ((N1C->getValue() & (~0ULL << ExtendBits)) == 0)
 573       return DAG.getNode(ISD::AND, VT, N0.getOperand(0), N1).Val;
 574   }
 575   // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF
 576   if (N0.getOpcode() == ISD::OR)
 577     if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
 578       if ((ORI->getValue() & N1C->getValue()) == N1C->getValue())
 579         return N1.Val;
 580   return 0;
 581 }
 582
 583 SDNode *DAGCombiner::visitOR(SDNode *N) {
 584   SDOperand N0 = N->getOperand(0);
 585   SDOperand N1 = N->getOperand(1);
 586   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 587   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 588
 589   // fold (or c1, c2) -> c1|c2
 590   if (N0C && N1C)
 591     return DAG.getConstant(N0C->getValue() | N1C->getValue(),
 592                            N->getValueType(0)).Val;
 593   // fold (or x, 0) -> x
 594   if (N1C && N1C->isNullValue())
 595     return N0.Val;
 596   // fold (or x, -1) -> -1
 597   if (N1C && N1C->isAllOnesValue())
 598     return N1.Val;
 599   return 0;
 600 }
 601
 602 SDNode *DAGCombiner::visitXOR(SDNode *N) {
 603   SDOperand N0 = N->getOperand(0);
 604   SDOperand N1 = N->getOperand(1);
 605   SDOperand LHS, RHS, CC;
 606   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 607   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 608   MVT::ValueType VT = N0.getValueType();
 609
 610   // fold (xor c1, c2) -> c1^c2
 611   if (N0C && N1C)
 612     return DAG.getConstant(N0C->getValue() ^ N1C->getValue(), VT).Val;
 613   // fold (xor x, 0) -> x
 614   if (N1C && N1C->isNullValue())
 615     return N0.Val;
 616   // fold !(x cc y) -> (x !cc y)
 617   if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) {
 618     bool isInt = MVT::isInteger(LHS.getValueType());
 619     ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(),
 620                                                isInt);
 621     if (N0.getOpcode() == ISD::SETCC)
 622       return DAG.getSetCC(VT, LHS, RHS, NotCC).Val;
 623     if (N0.getOpcode() == ISD::SELECT_CC)
 624       return DAG.getSelectCC(LHS, RHS, N0.getOperand(2), N0.getOperand(3),
 625                              NotCC).Val;
 626     assert(0 && "Unhandled SetCC Equivalent!");
 627     abort();
 628   }
 629   // fold !(x or y) -> (!x and !y) iff x or y are freely invertible
 630   if (N1C && N1C->isAllOnesValue() && N0.getOpcode() == ISD::OR) {
 631     SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
 632     if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
 633       LHS = DAG.getNode(ISD::XOR, VT, LHS, N1);  // RHS = ~LHS
 634       RHS = DAG.getNode(ISD::XOR, VT, RHS, N1);  // RHS = ~RHS
 635       return DAG.getNode(ISD::AND, VT, LHS, RHS).Val;
 636     }
 637   }
 638   // fold !(x and y) -> (!x or !y) iff x or y are freely invertible
 639   if (N1C && N1C->isAllOnesValue() && N0.getOpcode() == ISD::AND) {
 640     SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
 641     if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
 642       LHS = DAG.getNode(ISD::XOR, VT, LHS, N1);  // RHS = ~LHS
 643       RHS = DAG.getNode(ISD::XOR, VT, RHS, N1);  // RHS = ~RHS
 644       return DAG.getNode(ISD::OR, VT, LHS, RHS).Val;
 645     }
 646   }
 647   return 0;
 648 }
 649
 650 SDNode *DAGCombiner::visitSHL(SDNode *N) {
 651   SDOperand N0 = N->getOperand(0);
 652   SDOperand N1 = N->getOperand(1);
 653   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 654   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 655   MVT::ValueType VT = N0.getValueType();
 656   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
 657
 658   // fold (shl c1, c2) -> c1<<c2
 659   if (N0C && N1C)
 660     return DAG.getConstant(N0C->getValue() << N1C->getValue(), VT).Val;
 661   // fold (shl 0, x) -> 0
 662   if (N0C && N0C->isNullValue())
 663     return N0.Val;
 664   // fold (shl x, c >= size(x)) -> undef
 665   if (N1C && N1C->getValue() >= OpSizeInBits)
 666     return DAG.getNode(ISD::UNDEF, VT).Val;
 667   // fold (shl x, 0) -> x
 668   if (N1C && N1C->isNullValue())
 669     return N0.Val;
 670   // if (shl x, c) is known to be zero, return 0
 671   if (N1C && MaskedValueIsZero(N0,(~0ULL >> (64-OpSizeInBits))>>N1C->getValue(),
 672                                TLI))
 673     return DAG.getConstant(0, VT).Val;
 674   // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2)
 675   if (N1C && N0.getOpcode() == ISD::SHL &&
 676       N0.getOperand(1).getOpcode() == ISD::Constant) {
 677     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
 678     uint64_t c2 = N1C->getValue();
 679     if (c1 + c2 > OpSizeInBits)
 680       return DAG.getConstant(0, VT).Val;
 681     return DAG.getNode(ISD::SHL, VT, N0.getOperand(0),
 682                        DAG.getConstant(c1 + c2, N1.getValueType())).Val;
 683   }
 684   // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or
 685   //                               (srl (and x, -1 << c1), c1-c2)
 686   if (N1C && N0.getOpcode() == ISD::SRL &&
 687       N0.getOperand(1).getOpcode() == ISD::Constant) {
 688     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
 689     uint64_t c2 = N1C->getValue();
 690     SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0),
 691                                  DAG.getConstant(~0ULL << c1, VT));
 692     if (c2 > c1)
 693       return DAG.getNode(ISD::SHL, VT, Mask,
 694                          DAG.getConstant(c2-c1, N1.getValueType())).Val;
 695     else
 696       return DAG.getNode(ISD::SRL, VT, Mask,
 697                          DAG.getConstant(c1-c2, N1.getValueType())).Val;
 698   }
 699   // fold (shl (sra x, c1), c1) -> (and x, -1 << c1)
 700   if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1))
 701     return DAG.getNode(ISD::AND, VT, N0.getOperand(0),
 702                        DAG.getConstant(~0ULL << N1C->getValue(), VT)).Val;
 703   return 0;
 704 }
 705
 706 SDNode *DAGCombiner::visitSRA(SDNode *N) {
 707   SDOperand N0 = N->getOperand(0);
 708   SDOperand N1 = N->getOperand(1);
 709   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 710   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 711   MVT::ValueType VT = N0.getValueType();
 712   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
 713
 714   // fold (sra c1, c2) -> c1>>c2
 715   if (N0C && N1C)
 716     return DAG.getConstant(N0C->getSignExtended() >> N1C->getValue(), VT).Val;
 717   // fold (sra 0, x) -> 0
 718   if (N0C && N0C->isNullValue())
 719     return N0.Val;
 720   // fold (sra -1, x) -> -1
 721   if (N0C && N0C->isAllOnesValue())
 722     return N0.Val;
 723   // fold (sra x, c >= size(x)) -> undef
 724   if (N1C && N1C->getValue() >= OpSizeInBits)
 725     return DAG.getNode(ISD::UNDEF, VT).Val;
 726   // fold (sra x, 0) -> x
 727   if (N1C && N1C->isNullValue())
 728     return N0.Val;
 729   // If the sign bit is known to be zero, switch this to a SRL.
 730   if (N1C && MaskedValueIsZero(N0, (1ULL << (OpSizeInBits-1)), TLI))
 731     return DAG.getNode(ISD::SRL, VT, N0, N1).Val;
 732   return 0;
 733 }
 734
 735 SDNode *DAGCombiner::visitSRL(SDNode *N) {
 736   SDOperand N0 = N->getOperand(0);
 737   SDOperand N1 = N->getOperand(1);
 738   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 739   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
 740   MVT::ValueType VT = N0.getValueType();
 741   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
 742
 743   // fold (srl c1, c2) -> c1 >>u c2
 744   if (N0C && N1C)
 745     return DAG.getConstant(N0C->getValue() >> N1C->getValue(), VT).Val;
 746   // fold (srl 0, x) -> 0
 747   if (N0C && N0C->isNullValue())
 748     return N0.Val;
 749   // fold (srl x, c >= size(x)) -> undef
 750   if (N1C && N1C->getValue() >= OpSizeInBits)
 751     return DAG.getNode(ISD::UNDEF, VT).Val;
 752   // fold (srl x, 0) -> x
 753   if (N1C && N1C->isNullValue())
 754     return N0.Val;
 755   // if (srl x, c) is known to be zero, return 0
 756   if (N1C && MaskedValueIsZero(N0,(~0ULL >> (64-OpSizeInBits))<<N1C->getValue(),
 757                                TLI))
 758     return DAG.getConstant(0, VT).Val;
 759   // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2)
 760   if (N1C && N0.getOpcode() == ISD::SRL &&
 761       N0.getOperand(1).getOpcode() == ISD::Constant) {
 762     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
 763     uint64_t c2 = N1C->getValue();
 764     if (c1 + c2 > OpSizeInBits)
 765       return DAG.getConstant(0, VT).Val;
 766     return DAG.getNode(ISD::SRL, VT, N0.getOperand(0),
 767                        DAG.getConstant(c1 + c2, N1.getValueType())).Val;
 768   }
 769   return 0;
 770 }
 771
 772 SDNode *DAGCombiner::visitCTLZ(SDNode *N) {
 773   SDOperand N0 = N->getOperand(0);
 774   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 775
 776   // fold (ctlz c1) -> c2
 777   if (N0C)
 778     return DAG.getConstant(CountLeadingZeros_64(N0C->getValue()),
 779                            N0.getValueType()).Val;
 780   return 0;
 781 }
 782
 783 SDNode *DAGCombiner::visitCTTZ(SDNode *N) {
 784   SDOperand N0 = N->getOperand(0);
 785   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 786
 787   // fold (cttz c1) -> c2
 788   if (N0C)
 789     return DAG.getConstant(CountTrailingZeros_64(N0C->getValue()),
 790                            N0.getValueType()).Val;
 791   return 0;
 792 }
 793
 794 SDNode *DAGCombiner::visitCTPOP(SDNode *N) {
 795   SDOperand N0 = N->getOperand(0);
 796   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 797
 798   // fold (ctpop c1) -> c2
 799   if (N0C)
 800     return DAG.getConstant(CountPopulation_64(N0C->getValue()),
 801                            N0.getValueType()).Val;
 802   return 0;
 803 }
 804
 805 SDNode *DAGCombiner::visitSIGN_EXTEND(SDNode *N) {
 806   SDOperand N0 = N->getOperand(0);
 807   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 808   MVT::ValueType VT = N->getValueType(0);
 809
 810   // fold (sext c1) -> c1
 811   if (N0C)
 812     return DAG.getConstant(N0C->getSignExtended(), VT).Val;
 813   // fold (sext (sext x)) -> (sext x)
 814   if (N0.getOpcode() == ISD::SIGN_EXTEND)
 815     return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0)).Val;
 816   return 0;
 817 }
 818
 819 SDNode *DAGCombiner::visitZERO_EXTEND(SDNode *N) {
 820   SDOperand N0 = N->getOperand(0);
 821   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 822   MVT::ValueType VT = N->getValueType(0);
 823
 824   // fold (zext c1) -> c1
 825   if (N0C)
 826     return DAG.getConstant(N0C->getValue(), VT).Val;
 827   // fold (zext (zext x)) -> (zext x)
 828   if (N0.getOpcode() == ISD::ZERO_EXTEND)
 829     return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0)).Val;
 830   return 0;
 831 }
 832
 833 SDNode *DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) {
 834   SDOperand N0 = N->getOperand(0);
 835   SDOperand N1 = N->getOperand(1);
 836   SDOperand LHS, RHS, CC;
 837   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 838   MVT::ValueType VT = N->getValueType(0);
 839   MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT();
 840
 841   // fold (sext_in_reg c1) -> c1
 842   if (N0C) {
 843     SDOperand Truncate = DAG.getConstant(N0C->getValue(), EVT);
 844     return DAG.getNode(ISD::SIGN_EXTEND, VT, Truncate).Val;
 845   }
 846   // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt1
 847   if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
 848       cast<VTSDNode>(N0.getOperand(1))->getVT() < EVT) {
 849     return N0.Val;
 850   }
 851   // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2
 852   if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
 853       EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) {
 854     return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1).Val;
 855   }
 856   // fold (sext_in_reg (assert_sext x)) -> (assert_sext x)
 857   if (N0.getOpcode() == ISD::AssertSext &&
 858       cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) {
 859     return N0.Val;
 860   }
 861   // fold (sext_in_reg (sextload x)) -> (sextload x)
 862   if (N0.getOpcode() == ISD::SEXTLOAD &&
 863       cast<VTSDNode>(N0.getOperand(3))->getVT() <= EVT) {
 864     return N0.Val;
 865   }
 866   // fold (sext_in_reg (setcc x)) -> setcc x iff (setcc x) == 0 or -1
 867   // FIXME: teach isSetCCEquivalent about 0, -1 and then use it here
 868   if (N0.getOpcode() == ISD::SETCC &&
 869       TLI.getSetCCResultContents() ==
 870         TargetLowering::ZeroOrNegativeOneSetCCResult)
 871     return N0.Val;
 872   // FIXME: this code is currently just ported over from SelectionDAG.cpp
 873   // we probably actually want to handle this in two pieces.  Rather than
 874   // checking all the top bits for zero, just check the sign bit here and turn
 875   // it into a zero extend inreg (AND with constant).
 876   // then, let the code for AND figure out if the mask is superfluous rather
 877   // than doing so here.
 878   if (N0.getOpcode() == ISD::AND &&
 879       N0.getOperand(1).getOpcode() == ISD::Constant) {
 880     uint64_t Mask = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
 881     unsigned NumBits = MVT::getSizeInBits(EVT);
 882     if ((Mask & (~0ULL << (NumBits-1))) == 0)
 883       return N0.Val;
 884   }
 885   return 0;
 886 }
 887
 888 SDNode *DAGCombiner::visitTRUNCATE(SDNode *N) {
 889   SDOperand N0 = N->getOperand(0);
 890   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 891   MVT::ValueType VT = N->getValueType(0);
 892
 893   // noop truncate
 894   if (N0.getValueType() == N->getValueType(0))
 895     return N0.Val;
 896   // fold (truncate c1) -> c1
 897   if (N0C)
 898     return DAG.getConstant(N0C->getValue(), VT).Val;
 899   // fold (truncate (truncate x)) -> (truncate x)
 900   if (N0.getOpcode() == ISD::TRUNCATE)
 901     return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)).Val;
 902   // fold (truncate (ext x)) -> (ext x) or (truncate x) or x
 903   if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND){
 904     if (N0.getValueType() < VT)
 905       // if the source is smaller than the dest, we still need an extend
 906       return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0)).Val;
 907     else if (N0.getValueType() > VT)
 908       // if the source is larger than the dest, than we just need the truncate
 909       return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0)).Val;
 910     else
 911       // if the source and dest are the same type, we can drop both the extend
 912       // and the truncate
 913       return N0.getOperand(0).Val;
 914   }
 915   return 0;
 916 }
 917
 918 SDNode *DAGCombiner::visitSINT_TO_FP(SDNode *N) {
 919   SDOperand N0 = N->getOperand(0);
 920   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 921   MVT::ValueType VT = N->getValueType(0);
 922
 923   // fold (sint_to_fp c1) -> c1fp
 924   if (N0C)
 925     return DAG.getConstantFP(N0C->getSignExtended(), VT).Val;
 926   return 0;
 927 }
 928
 929 SDNode *DAGCombiner::visitUINT_TO_FP(SDNode *N) {
 930   SDOperand N0 = N->getOperand(0);
 931   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
 932   MVT::ValueType VT = N->getValueType(0);
 933
 934   // fold (uint_to_fp c1) -> c1fp
 935   if (N0C)
 936     return DAG.getConstantFP(N0C->getValue(), VT).Val;
 937   return 0;
 938 }
 939
 940 SDNode *DAGCombiner::visitFP_TO_SINT(SDNode *N) {
 941   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
 942
 943   // fold (fp_to_sint c1fp) -> c1
 944   if (N0CFP)
 945     return DAG.getConstant((int64_t)N0CFP->getValue(), N->getValueType(0)).Val;
 946   return 0;
 947 }
 948
 949 SDNode *DAGCombiner::visitFP_TO_UINT(SDNode *N) {
 950   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
 951
 952   // fold (fp_to_uint c1fp) -> c1
 953   if (N0CFP)
 954     return DAG.getConstant((uint64_t)N0CFP->getValue(), N->getValueType(0)).Val;
 955   return 0;
 956 }
 957
 958 SDNode *DAGCombiner::visitFP_ROUND(SDNode *N) {
 959   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
 960
 961   // fold (fp_round c1fp) -> c1fp
 962   if (N0CFP)
 963     return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0)).Val;
 964   return 0;
 965 }
 966
 967 SDNode *DAGCombiner::visitFP_ROUND_INREG(SDNode *N) {
 968   SDOperand N0 = N->getOperand(0);
 969   MVT::ValueType VT = N->getValueType(0);
 970   MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
 971   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
 972
 973   // noop fp_round_inreg
 974   if (EVT == VT)
 975     return N0.Val;
 976   // fold (fp_round_inreg c1fp) -> c1fp
 977   if (N0CFP) {
 978     SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT);
 979     return DAG.getNode(ISD::FP_EXTEND, VT, Round).Val;
 980   }
 981   return 0;
 982 }
 983
 984 SDNode *DAGCombiner::visitFP_EXTEND(SDNode *N) {
 985   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
 986
 987   // fold (fp_extend c1fp) -> c1fp
 988   if (N0CFP)
 989     return DAG.getConstantFP(N0CFP->getValue(), N->getValueType(0)).Val;
 990   return 0;
 991 }
 992
 993 SDNode *DAGCombiner::visitFNEG(SDNode *N) {
 994   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
 995   // fold (neg c1) -> -c1
 996   if (N0CFP)
 997     return DAG.getConstantFP(-N0CFP->getValue(), N->getValueType(0)).Val;
 998   // fold (neg (sub x, y)) -> (sub y, x)
 999   if (N->getOperand(0).getOpcode() == ISD::SUB)
1000     return DAG.getNode(ISD::SUB, N->getValueType(0), N->getOperand(1),
1001                        N->getOperand(0)).Val;
1002   // fold (neg (neg x)) -> x
1003   if (N->getOperand(0).getOpcode() == ISD::FNEG)
1004     return N->getOperand(0).getOperand(0).Val;
1005   return 0;
1006 }
1007
1008 SDNode *DAGCombiner::visitFABS(SDNode *N) {
1009   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N->getOperand(0));
1010   // fold (fabs c1) -> fabs(c1)
1011   if (N0CFP)
1012     return DAG.getConstantFP(fabs(N0CFP->getValue()), N->getValueType(0)).Val;
1013   // fold (fabs (fabs x)) -> (fabs x)
1014   if (N->getOperand(0).getOpcode() == ISD::FABS)
1015     return N->getOperand(0).Val;
1016   // fold (fabs (fneg x)) -> (fabs x)
1017   if (N->getOperand(0).getOpcode() == ISD::FNEG)
1018     return DAG.getNode(ISD::FABS, N->getValueType(0),
1019                        N->getOperand(0).getOperand(0)).Val;
1020   return 0;
1021 }
1022
1023 // SelectionDAG::Combine - This is the entry point for the file.
1024 //
1025 void SelectionDAG::Combine(bool RunningAfterLegalize) {
1026   /// run - This is the main entry point to this class.
1027   ///
1028   DAGCombiner(*this).Run(RunningAfterLegalize);
1029 }