LLVM API Documentation

DAGCombiner.cpp

Go to the documentation of this file.
00001 //===-- DAGCombiner.cpp - Implement a DAG node combiner -------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by Nate Begeman and is distributed under the
00006 // University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass combines dag nodes to form fewer, simpler DAG nodes.  It can be run
00011 // both before and after the DAG is legalized.
00012 //
00013 // FIXME: Missing folds
00014 // sdiv, udiv, srem, urem (X, const) where X is an integer can be expanded into
00015 //  a sequence of multiplies, shifts, and adds.  This should be controlled by
00016 //  some kind of hint from the target that int div is expensive.
00017 // various folds of mulh[s,u] by constants such as -1, powers of 2, etc.
00018 //
00019 // FIXME: select C, pow2, pow2 -> something smart
00020 // FIXME: trunc(select X, Y, Z) -> select X, trunc(Y), trunc(Z)
00021 // FIXME: Dead stores -> nuke
00022 // FIXME: shr X, (and Y,31) -> shr X, Y   (TRICKY!)
00023 // FIXME: mul (x, const) -> shifts + adds
00024 // FIXME: undef values
00025 // FIXME: make truncate see through SIGN_EXTEND and AND
00026 // FIXME: divide by zero is currently left unfolded.  do we want to turn this
00027 //        into an undef?
00028 // FIXME: select ne (select cc, 1, 0), 0, true, false -> select cc, true, false
00029 // 
00030 //===----------------------------------------------------------------------===//
00031 
00032 #define DEBUG_TYPE "dagcombine"
00033 #include "llvm/ADT/Statistic.h"
00034 #include "llvm/CodeGen/SelectionDAG.h"
00035 #include "llvm/Support/Debug.h"
00036 #include "llvm/Support/MathExtras.h"
00037 #include "llvm/Target/TargetLowering.h"
00038 #include <algorithm>
00039 #include <cmath>
00040 #include <iostream>
00041 using namespace llvm;
00042 
00043 namespace {
00044   Statistic<> NodesCombined ("dagcombiner", "Number of dag nodes combined");
00045 
00046   class DAGCombiner {
00047     SelectionDAG &DAG;
00048     TargetLowering &TLI;
00049     bool AfterLegalize;
00050 
00051     // Worklist of all of the nodes that need to be simplified.
00052     std::vector<SDNode*> WorkList;
00053 
00054     /// AddUsersToWorkList - When an instruction is simplified, add all users of
00055     /// the instruction to the work lists because they might get more simplified
00056     /// now.
00057     ///
00058     void AddUsersToWorkList(SDNode *N) {
00059       for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end();
00060            UI != UE; ++UI)
00061         WorkList.push_back(*UI);
00062     }
00063 
00064     /// removeFromWorkList - remove all instances of N from the worklist.
00065     ///
00066     void removeFromWorkList(SDNode *N) {
00067       WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), N),
00068                      WorkList.end());
00069     }
00070     
00071   public:
00072     void AddToWorkList(SDNode *N) {
00073       WorkList.push_back(N);
00074     }
00075     
00076     SDOperand CombineTo(SDNode *N, const std::vector<SDOperand> &To) {
00077       ++NodesCombined;
00078       DEBUG(std::cerr << "\nReplacing "; N->dump();
00079             std::cerr << "\nWith: "; To[0].Val->dump();
00080             std::cerr << " and " << To.size()-1 << " other values\n");
00081       std::vector<SDNode*> NowDead;
00082       DAG.ReplaceAllUsesWith(N, To, &NowDead);
00083       
00084       // Push the new nodes and any users onto the worklist
00085       for (unsigned i = 0, e = To.size(); i != e; ++i) {
00086         WorkList.push_back(To[i].Val);
00087         AddUsersToWorkList(To[i].Val);
00088       }
00089       
00090       // Nodes can end up on the worklist more than once.  Make sure we do
00091       // not process a node that has been replaced.
00092       removeFromWorkList(N);
00093       for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
00094         removeFromWorkList(NowDead[i]);
00095       
00096       // Finally, since the node is now dead, remove it from the graph.
00097       DAG.DeleteNode(N);
00098       return SDOperand(N, 0);
00099     }
00100     
00101     SDOperand CombineTo(SDNode *N, SDOperand Res) {
00102       std::vector<SDOperand> To;
00103       To.push_back(Res);
00104       return CombineTo(N, To);
00105     }
00106     
00107     SDOperand CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) {
00108       std::vector<SDOperand> To;
00109       To.push_back(Res0);
00110       To.push_back(Res1);
00111       return CombineTo(N, To);
00112     }
00113   private:    
00114     
00115     /// SimplifyDemandedBits - Check the specified integer node value to see if
00116     /// it can be simplified or if things it uses can be simplified by bit
00117     /// propagation.  If so, return true.
00118     bool SimplifyDemandedBits(SDOperand Op) {
00119       TargetLowering::TargetLoweringOpt TLO(DAG);
00120       uint64_t KnownZero, KnownOne;
00121       uint64_t Demanded = MVT::getIntVTBitMask(Op.getValueType());
00122       if (!TLI.SimplifyDemandedBits(Op, Demanded, KnownZero, KnownOne, TLO))
00123         return false;
00124 
00125       // Revisit the node.
00126       WorkList.push_back(Op.Val);
00127       
00128       // Replace the old value with the new one.
00129       ++NodesCombined;
00130       DEBUG(std::cerr << "\nReplacing "; TLO.Old.Val->dump();
00131             std::cerr << "\nWith: "; TLO.New.Val->dump());
00132 
00133       std::vector<SDNode*> NowDead;
00134       DAG.ReplaceAllUsesOfValueWith(TLO.Old, TLO.New, NowDead);
00135       
00136       // Push the new node and any (possibly new) users onto the worklist.
00137       WorkList.push_back(TLO.New.Val);
00138       AddUsersToWorkList(TLO.New.Val);
00139       
00140       // Nodes can end up on the worklist more than once.  Make sure we do
00141       // not process a node that has been replaced.
00142       for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
00143         removeFromWorkList(NowDead[i]);
00144       
00145       // Finally, if the node is now dead, remove it from the graph.  The node
00146       // may not be dead if the replacement process recursively simplified to
00147       // something else needing this node.
00148       if (TLO.Old.Val->use_empty()) {
00149         removeFromWorkList(TLO.Old.Val);
00150         DAG.DeleteNode(TLO.Old.Val);
00151       }
00152       return true;
00153     }
00154 
00155     /// visit - call the node-specific routine that knows how to fold each
00156     /// particular type of node.
00157     SDOperand visit(SDNode *N);
00158 
00159     // Visitation implementation - Implement dag node combining for different
00160     // node types.  The semantics are as follows:
00161     // Return Value:
00162     //   SDOperand.Val == 0   - No change was made
00163     //   SDOperand.Val == N   - N was replaced, is dead, and is already handled.
00164     //   otherwise            - N should be replaced by the returned Operand.
00165     //
00166     SDOperand visitTokenFactor(SDNode *N);
00167     SDOperand visitADD(SDNode *N);
00168     SDOperand visitSUB(SDNode *N);
00169     SDOperand visitMUL(SDNode *N);
00170     SDOperand visitSDIV(SDNode *N);
00171     SDOperand visitUDIV(SDNode *N);
00172     SDOperand visitSREM(SDNode *N);
00173     SDOperand visitUREM(SDNode *N);
00174     SDOperand visitMULHU(SDNode *N);
00175     SDOperand visitMULHS(SDNode *N);
00176     SDOperand visitAND(SDNode *N);
00177     SDOperand visitOR(SDNode *N);
00178     SDOperand visitXOR(SDNode *N);
00179     SDOperand visitVBinOp(SDNode *N, ISD::NodeType IntOp, ISD::NodeType FPOp);
00180     SDOperand visitSHL(SDNode *N);
00181     SDOperand visitSRA(SDNode *N);
00182     SDOperand visitSRL(SDNode *N);
00183     SDOperand visitCTLZ(SDNode *N);
00184     SDOperand visitCTTZ(SDNode *N);
00185     SDOperand visitCTPOP(SDNode *N);
00186     SDOperand visitSELECT(SDNode *N);
00187     SDOperand visitSELECT_CC(SDNode *N);
00188     SDOperand visitSETCC(SDNode *N);
00189     SDOperand visitSIGN_EXTEND(SDNode *N);
00190     SDOperand visitZERO_EXTEND(SDNode *N);
00191     SDOperand visitSIGN_EXTEND_INREG(SDNode *N);
00192     SDOperand visitTRUNCATE(SDNode *N);
00193     SDOperand visitBIT_CONVERT(SDNode *N);
00194     SDOperand visitVBIT_CONVERT(SDNode *N);
00195     SDOperand visitFADD(SDNode *N);
00196     SDOperand visitFSUB(SDNode *N);
00197     SDOperand visitFMUL(SDNode *N);
00198     SDOperand visitFDIV(SDNode *N);
00199     SDOperand visitFREM(SDNode *N);
00200     SDOperand visitFCOPYSIGN(SDNode *N);
00201     SDOperand visitSINT_TO_FP(SDNode *N);
00202     SDOperand visitUINT_TO_FP(SDNode *N);
00203     SDOperand visitFP_TO_SINT(SDNode *N);
00204     SDOperand visitFP_TO_UINT(SDNode *N);
00205     SDOperand visitFP_ROUND(SDNode *N);
00206     SDOperand visitFP_ROUND_INREG(SDNode *N);
00207     SDOperand visitFP_EXTEND(SDNode *N);
00208     SDOperand visitFNEG(SDNode *N);
00209     SDOperand visitFABS(SDNode *N);
00210     SDOperand visitBRCOND(SDNode *N);
00211     SDOperand visitBR_CC(SDNode *N);
00212     SDOperand visitLOAD(SDNode *N);
00213     SDOperand visitXEXTLOAD(SDNode *N);
00214     SDOperand visitSTORE(SDNode *N);
00215     SDOperand visitINSERT_VECTOR_ELT(SDNode *N);
00216     SDOperand visitVINSERT_VECTOR_ELT(SDNode *N);
00217     SDOperand visitVBUILD_VECTOR(SDNode *N);
00218     SDOperand visitVECTOR_SHUFFLE(SDNode *N);
00219     SDOperand visitVVECTOR_SHUFFLE(SDNode *N);
00220 
00221     SDOperand ReassociateOps(unsigned Opc, SDOperand LHS, SDOperand RHS);
00222     
00223     bool SimplifySelectOps(SDNode *SELECT, SDOperand LHS, SDOperand RHS);
00224     SDOperand SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2);
00225     SDOperand SimplifySelectCC(SDOperand N0, SDOperand N1, SDOperand N2, 
00226                                SDOperand N3, ISD::CondCode CC);
00227     SDOperand SimplifySetCC(MVT::ValueType VT, SDOperand N0, SDOperand N1,
00228                             ISD::CondCode Cond, bool foldBooleans = true);
00229     SDOperand ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *, MVT::ValueType);
00230     SDOperand BuildSDIV(SDNode *N);
00231     SDOperand BuildUDIV(SDNode *N);    
00232 public:
00233     DAGCombiner(SelectionDAG &D)
00234       : DAG(D), TLI(D.getTargetLoweringInfo()), AfterLegalize(false) {}
00235     
00236     /// Run - runs the dag combiner on all nodes in the work list
00237     void Run(bool RunningAfterLegalize); 
00238   };
00239 }
00240 
00241 //===----------------------------------------------------------------------===//
00242 //  TargetLowering::DAGCombinerInfo implementation
00243 //===----------------------------------------------------------------------===//
00244 
00245 void TargetLowering::DAGCombinerInfo::AddToWorklist(SDNode *N) {
00246   ((DAGCombiner*)DC)->AddToWorkList(N);
00247 }
00248 
00249 SDOperand TargetLowering::DAGCombinerInfo::
00250 CombineTo(SDNode *N, const std::vector<SDOperand> &To) {
00251   return ((DAGCombiner*)DC)->CombineTo(N, To);
00252 }
00253 
00254 SDOperand TargetLowering::DAGCombinerInfo::
00255 CombineTo(SDNode *N, SDOperand Res) {
00256   return ((DAGCombiner*)DC)->CombineTo(N, Res);
00257 }
00258 
00259 
00260 SDOperand TargetLowering::DAGCombinerInfo::
00261 CombineTo(SDNode *N, SDOperand Res0, SDOperand Res1) {
00262   return ((DAGCombiner*)DC)->CombineTo(N, Res0, Res1);
00263 }
00264 
00265 
00266 
00267 
00268 //===----------------------------------------------------------------------===//
00269 
00270 
00271 struct ms {
00272   int64_t m;  // magic number
00273   int64_t s;  // shift amount
00274 };
00275 
00276 struct mu {
00277   uint64_t m; // magic number
00278   int64_t a;  // add indicator
00279   int64_t s;  // shift amount
00280 };
00281 
00282 /// magic - calculate the magic numbers required to codegen an integer sdiv as
00283 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
00284 /// or -1.
00285 static ms magic32(int32_t d) {
00286   int32_t p;
00287   uint32_t ad, anc, delta, q1, r1, q2, r2, t;
00288   const uint32_t two31 = 0x80000000U;
00289   struct ms mag;
00290   
00291   ad = abs(d);
00292   t = two31 + ((uint32_t)d >> 31);
00293   anc = t - 1 - t%ad;   // absolute value of nc
00294   p = 31;               // initialize p
00295   q1 = two31/anc;       // initialize q1 = 2p/abs(nc)
00296   r1 = two31 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
00297   q2 = two31/ad;        // initialize q2 = 2p/abs(d)
00298   r2 = two31 - q2*ad;   // initialize r2 = rem(2p,abs(d))
00299   do {
00300     p = p + 1;
00301     q1 = 2*q1;        // update q1 = 2p/abs(nc)
00302     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
00303     if (r1 >= anc) {  // must be unsigned comparison
00304       q1 = q1 + 1;
00305       r1 = r1 - anc;
00306     }
00307     q2 = 2*q2;        // update q2 = 2p/abs(d)
00308     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
00309     if (r2 >= ad) {   // must be unsigned comparison
00310       q2 = q2 + 1;
00311       r2 = r2 - ad;
00312     }
00313     delta = ad - r2;
00314   } while (q1 < delta || (q1 == delta && r1 == 0));
00315   
00316   mag.m = (int32_t)(q2 + 1); // make sure to sign extend
00317   if (d < 0) mag.m = -mag.m; // resulting magic number
00318   mag.s = p - 32;            // resulting shift
00319   return mag;
00320 }
00321 
00322 /// magicu - calculate the magic numbers required to codegen an integer udiv as
00323 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
00324 static mu magicu32(uint32_t d) {
00325   int32_t p;
00326   uint32_t nc, delta, q1, r1, q2, r2;
00327   struct mu magu;
00328   magu.a = 0;               // initialize "add" indicator
00329   nc = - 1 - (-d)%d;
00330   p = 31;                   // initialize p
00331   q1 = 0x80000000/nc;       // initialize q1 = 2p/nc
00332   r1 = 0x80000000 - q1*nc;  // initialize r1 = rem(2p,nc)
00333   q2 = 0x7FFFFFFF/d;        // initialize q2 = (2p-1)/d
00334   r2 = 0x7FFFFFFF - q2*d;   // initialize r2 = rem((2p-1),d)
00335   do {
00336     p = p + 1;
00337     if (r1 >= nc - r1 ) {
00338       q1 = 2*q1 + 1;  // update q1
00339       r1 = 2*r1 - nc; // update r1
00340     }
00341     else {
00342       q1 = 2*q1; // update q1
00343       r1 = 2*r1; // update r1
00344     }
00345     if (r2 + 1 >= d - r2) {
00346       if (q2 >= 0x7FFFFFFF) magu.a = 1;
00347       q2 = 2*q2 + 1;     // update q2
00348       r2 = 2*r2 + 1 - d; // update r2
00349     }
00350     else {
00351       if (q2 >= 0x80000000) magu.a = 1;
00352       q2 = 2*q2;     // update q2
00353       r2 = 2*r2 + 1; // update r2
00354     }
00355     delta = d - 1 - r2;
00356   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
00357   magu.m = q2 + 1; // resulting magic number
00358   magu.s = p - 32;  // resulting shift
00359   return magu;
00360 }
00361 
00362 /// magic - calculate the magic numbers required to codegen an integer sdiv as
00363 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
00364 /// or -1.
00365 static ms magic64(int64_t d) {
00366   int64_t p;
00367   uint64_t ad, anc, delta, q1, r1, q2, r2, t;
00368   const uint64_t two63 = 9223372036854775808ULL; // 2^63
00369   struct ms mag;
00370   
00371   ad = d >= 0 ? d : -d;
00372   t = two63 + ((uint64_t)d >> 63);
00373   anc = t - 1 - t%ad;   // absolute value of nc
00374   p = 63;               // initialize p
00375   q1 = two63/anc;       // initialize q1 = 2p/abs(nc)
00376   r1 = two63 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
00377   q2 = two63/ad;        // initialize q2 = 2p/abs(d)
00378   r2 = two63 - q2*ad;   // initialize r2 = rem(2p,abs(d))
00379   do {
00380     p = p + 1;
00381     q1 = 2*q1;        // update q1 = 2p/abs(nc)
00382     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
00383     if (r1 >= anc) {  // must be unsigned comparison
00384       q1 = q1 + 1;
00385       r1 = r1 - anc;
00386     }
00387     q2 = 2*q2;        // update q2 = 2p/abs(d)
00388     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
00389     if (r2 >= ad) {   // must be unsigned comparison
00390       q2 = q2 + 1;
00391       r2 = r2 - ad;
00392     }
00393     delta = ad - r2;
00394   } while (q1 < delta || (q1 == delta && r1 == 0));
00395   
00396   mag.m = q2 + 1;
00397   if (d < 0) mag.m = -mag.m; // resulting magic number
00398   mag.s = p - 64;            // resulting shift
00399   return mag;
00400 }
00401 
00402 /// magicu - calculate the magic numbers required to codegen an integer udiv as
00403 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
00404 static mu magicu64(uint64_t d)
00405 {
00406   int64_t p;
00407   uint64_t nc, delta, q1, r1, q2, r2;
00408   struct mu magu;
00409   magu.a = 0;               // initialize "add" indicator
00410   nc = - 1 - (-d)%d;
00411   p = 63;                   // initialize p
00412   q1 = 0x8000000000000000ull/nc;       // initialize q1 = 2p/nc
00413   r1 = 0x8000000000000000ull - q1*nc;  // initialize r1 = rem(2p,nc)
00414   q2 = 0x7FFFFFFFFFFFFFFFull/d;        // initialize q2 = (2p-1)/d
00415   r2 = 0x7FFFFFFFFFFFFFFFull - q2*d;   // initialize r2 = rem((2p-1),d)
00416   do {
00417     p = p + 1;
00418     if (r1 >= nc - r1 ) {
00419       q1 = 2*q1 + 1;  // update q1
00420       r1 = 2*r1 - nc; // update r1
00421     }
00422     else {
00423       q1 = 2*q1; // update q1
00424       r1 = 2*r1; // update r1
00425     }
00426     if (r2 + 1 >= d - r2) {
00427       if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1;
00428       q2 = 2*q2 + 1;     // update q2
00429       r2 = 2*r2 + 1 - d; // update r2
00430     }
00431     else {
00432       if (q2 >= 0x8000000000000000ull) magu.a = 1;
00433       q2 = 2*q2;     // update q2
00434       r2 = 2*r2 + 1; // update r2
00435     }
00436     delta = d - 1 - r2;
00437   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
00438   magu.m = q2 + 1; // resulting magic number
00439   magu.s = p - 64;  // resulting shift
00440   return magu;
00441 }
00442 
00443 // isSetCCEquivalent - Return true if this node is a setcc, or is a select_cc
00444 // that selects between the values 1 and 0, making it equivalent to a setcc.
00445 // Also, set the incoming LHS, RHS, and CC references to the appropriate 
00446 // nodes based on the type of node we are checking.  This simplifies life a
00447 // bit for the callers.
00448 static bool isSetCCEquivalent(SDOperand N, SDOperand &LHS, SDOperand &RHS,
00449                               SDOperand &CC) {
00450   if (N.getOpcode() == ISD::SETCC) {
00451     LHS = N.getOperand(0);
00452     RHS = N.getOperand(1);
00453     CC  = N.getOperand(2);
00454     return true;
00455   }
00456   if (N.getOpcode() == ISD::SELECT_CC && 
00457       N.getOperand(2).getOpcode() == ISD::Constant &&
00458       N.getOperand(3).getOpcode() == ISD::Constant &&
00459       cast<ConstantSDNode>(N.getOperand(2))->getValue() == 1 &&
00460       cast<ConstantSDNode>(N.getOperand(3))->isNullValue()) {
00461     LHS = N.getOperand(0);
00462     RHS = N.getOperand(1);
00463     CC  = N.getOperand(4);
00464     return true;
00465   }
00466   return false;
00467 }
00468 
00469 // isOneUseSetCC - Return true if this is a SetCC-equivalent operation with only
00470 // one use.  If this is true, it allows the users to invert the operation for
00471 // free when it is profitable to do so.
00472 static bool isOneUseSetCC(SDOperand N) {
00473   SDOperand N0, N1, N2;
00474   if (isSetCCEquivalent(N, N0, N1, N2) && N.Val->hasOneUse())
00475     return true;
00476   return false;
00477 }
00478 
00479 // FIXME: This should probably go in the ISD class rather than being duplicated
00480 // in several files.
00481 static bool isCommutativeBinOp(unsigned Opcode) {
00482   switch (Opcode) {
00483     case ISD::ADD:
00484     case ISD::MUL:
00485     case ISD::AND:
00486     case ISD::OR:
00487     case ISD::XOR: return true;
00488     default: return false; // FIXME: Need commutative info for user ops!
00489   }
00490 }
00491 
00492 SDOperand DAGCombiner::ReassociateOps(unsigned Opc, SDOperand N0, SDOperand N1){
00493   MVT::ValueType VT = N0.getValueType();
00494   // reassoc. (op (op x, c1), y) -> (op (op x, y), c1) iff x+c1 has one use
00495   // reassoc. (op (op x, c1), c2) -> (op x, (op c1, c2))
00496   if (N0.getOpcode() == Opc && isa<ConstantSDNode>(N0.getOperand(1))) {
00497     if (isa<ConstantSDNode>(N1)) {
00498       SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(1), N1);
00499       AddToWorkList(OpNode.Val);
00500       return DAG.getNode(Opc, VT, OpNode, N0.getOperand(0));
00501     } else if (N0.hasOneUse()) {
00502       SDOperand OpNode = DAG.getNode(Opc, VT, N0.getOperand(0), N1);
00503       AddToWorkList(OpNode.Val);
00504       return DAG.getNode(Opc, VT, OpNode, N0.getOperand(1));
00505     }
00506   }
00507   // reassoc. (op y, (op x, c1)) -> (op (op x, y), c1) iff x+c1 has one use
00508   // reassoc. (op c2, (op x, c1)) -> (op x, (op c1, c2))
00509   if (N1.getOpcode() == Opc && isa<ConstantSDNode>(N1.getOperand(1))) {
00510     if (isa<ConstantSDNode>(N0)) {
00511       SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(1), N0);
00512       AddToWorkList(OpNode.Val);
00513       return DAG.getNode(Opc, VT, OpNode, N1.getOperand(0));
00514     } else if (N1.hasOneUse()) {
00515       SDOperand OpNode = DAG.getNode(Opc, VT, N1.getOperand(0), N0);
00516       AddToWorkList(OpNode.Val);
00517       return DAG.getNode(Opc, VT, OpNode, N1.getOperand(1));
00518     }
00519   }
00520   return SDOperand();
00521 }
00522 
00523 void DAGCombiner::Run(bool RunningAfterLegalize) {
00524   // set the instance variable, so that the various visit routines may use it.
00525   AfterLegalize = RunningAfterLegalize;
00526 
00527   // Add all the dag nodes to the worklist.
00528   for (SelectionDAG::allnodes_iterator I = DAG.allnodes_begin(),
00529        E = DAG.allnodes_end(); I != E; ++I)
00530     WorkList.push_back(I);
00531   
00532   // Create a dummy node (which is not added to allnodes), that adds a reference
00533   // to the root node, preventing it from being deleted, and tracking any
00534   // changes of the root.
00535   HandleSDNode Dummy(DAG.getRoot());
00536   
00537   
00538   /// DagCombineInfo - Expose the DAG combiner to the target combiner impls.
00539   TargetLowering::DAGCombinerInfo 
00540     DagCombineInfo(DAG, !RunningAfterLegalize, this);
00541   
00542   // while the worklist isn't empty, inspect the node on the end of it and
00543   // try and combine it.
00544   while (!WorkList.empty()) {
00545     SDNode *N = WorkList.back();
00546     WorkList.pop_back();
00547     
00548     // If N has no uses, it is dead.  Make sure to revisit all N's operands once
00549     // N is deleted from the DAG, since they too may now be dead or may have a
00550     // reduced number of uses, allowing other xforms.
00551     if (N->use_empty() && N != &Dummy) {
00552       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
00553         WorkList.push_back(N->getOperand(i).Val);
00554       
00555       removeFromWorkList(N);
00556       DAG.DeleteNode(N);
00557       continue;
00558     }
00559     
00560     SDOperand RV = visit(N);
00561     
00562     // If nothing happened, try a target-specific DAG combine.
00563     if (RV.Val == 0) {
00564       if (N->getOpcode() >= ISD::BUILTIN_OP_END ||
00565           TLI.hasTargetDAGCombine((ISD::NodeType)N->getOpcode()))
00566         RV = TLI.PerformDAGCombine(N, DagCombineInfo);
00567     }
00568     
00569     if (RV.Val) {
00570       ++NodesCombined;
00571       // If we get back the same node we passed in, rather than a new node or
00572       // zero, we know that the node must have defined multiple values and
00573       // CombineTo was used.  Since CombineTo takes care of the worklist 
00574       // mechanics for us, we have no work to do in this case.
00575       if (RV.Val != N) {
00576         DEBUG(std::cerr << "\nReplacing "; N->dump();
00577               std::cerr << "\nWith: "; RV.Val->dump();
00578               std::cerr << '\n');
00579         std::vector<SDNode*> NowDead;
00580         DAG.ReplaceAllUsesWith(N, std::vector<SDOperand>(1, RV), &NowDead);
00581           
00582         // Push the new node and any users onto the worklist
00583         WorkList.push_back(RV.Val);
00584         AddUsersToWorkList(RV.Val);
00585           
00586         // Nodes can end up on the worklist more than once.  Make sure we do
00587         // not process a node that has been replaced.
00588         removeFromWorkList(N);
00589         for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
00590           removeFromWorkList(NowDead[i]);
00591         
00592         // Finally, since the node is now dead, remove it from the graph.
00593         DAG.DeleteNode(N);
00594       }
00595     }
00596   }
00597   
00598   // If the root changed (e.g. it was a dead load, update the root).
00599   DAG.setRoot(Dummy.getValue());
00600 }
00601 
00602 SDOperand DAGCombiner::visit(SDNode *N) {
00603   switch(N->getOpcode()) {
00604   default: break;
00605   case ISD::TokenFactor:        return visitTokenFactor(N);
00606   case ISD::ADD:                return visitADD(N);
00607   case ISD::SUB:                return visitSUB(N);
00608   case ISD::MUL:                return visitMUL(N);
00609   case ISD::SDIV:               return visitSDIV(N);
00610   case ISD::UDIV:               return visitUDIV(N);
00611   case ISD::SREM:               return visitSREM(N);
00612   case ISD::UREM:               return visitUREM(N);
00613   case ISD::MULHU:              return visitMULHU(N);
00614   case ISD::MULHS:              return visitMULHS(N);
00615   case ISD::AND:                return visitAND(N);
00616   case ISD::OR:                 return visitOR(N);
00617   case ISD::XOR:                return visitXOR(N);
00618   case ISD::SHL:                return visitSHL(N);
00619   case ISD::SRA:                return visitSRA(N);
00620   case ISD::SRL:                return visitSRL(N);
00621   case ISD::CTLZ:               return visitCTLZ(N);
00622   case ISD::CTTZ:               return visitCTTZ(N);
00623   case ISD::CTPOP:              return visitCTPOP(N);
00624   case ISD::SELECT:             return visitSELECT(N);
00625   case ISD::SELECT_CC:          return visitSELECT_CC(N);
00626   case ISD::SETCC:              return visitSETCC(N);
00627   case ISD::SIGN_EXTEND:        return visitSIGN_EXTEND(N);
00628   case ISD::ZERO_EXTEND:        return visitZERO_EXTEND(N);
00629   case ISD::SIGN_EXTEND_INREG:  return visitSIGN_EXTEND_INREG(N);
00630   case ISD::TRUNCATE:           return visitTRUNCATE(N);
00631   case ISD::BIT_CONVERT:        return visitBIT_CONVERT(N);
00632   case ISD::VBIT_CONVERT:       return visitVBIT_CONVERT(N);
00633   case ISD::FADD:               return visitFADD(N);
00634   case ISD::FSUB:               return visitFSUB(N);
00635   case ISD::FMUL:               return visitFMUL(N);
00636   case ISD::FDIV:               return visitFDIV(N);
00637   case ISD::FREM:               return visitFREM(N);
00638   case ISD::FCOPYSIGN:          return visitFCOPYSIGN(N);
00639   case ISD::SINT_TO_FP:         return visitSINT_TO_FP(N);
00640   case ISD::UINT_TO_FP:         return visitUINT_TO_FP(N);
00641   case ISD::FP_TO_SINT:         return visitFP_TO_SINT(N);
00642   case ISD::FP_TO_UINT:         return visitFP_TO_UINT(N);
00643   case ISD::FP_ROUND:           return visitFP_ROUND(N);
00644   case ISD::FP_ROUND_INREG:     return visitFP_ROUND_INREG(N);
00645   case ISD::FP_EXTEND:          return visitFP_EXTEND(N);
00646   case ISD::FNEG:               return visitFNEG(N);
00647   case ISD::FABS:               return visitFABS(N);
00648   case ISD::BRCOND:             return visitBRCOND(N);
00649   case ISD::BR_CC:              return visitBR_CC(N);
00650   case ISD::LOAD:               return visitLOAD(N);
00651   case ISD::EXTLOAD:
00652   case ISD::SEXTLOAD:
00653   case ISD::ZEXTLOAD:           return visitXEXTLOAD(N);
00654   case ISD::STORE:              return visitSTORE(N);
00655   case ISD::INSERT_VECTOR_ELT:  return visitINSERT_VECTOR_ELT(N);
00656   case ISD::VINSERT_VECTOR_ELT: return visitVINSERT_VECTOR_ELT(N);
00657   case ISD::VBUILD_VECTOR:      return visitVBUILD_VECTOR(N);
00658   case ISD::VECTOR_SHUFFLE:     return visitVECTOR_SHUFFLE(N);
00659   case ISD::VVECTOR_SHUFFLE:    return visitVVECTOR_SHUFFLE(N);
00660   case ISD::VADD:               return visitVBinOp(N, ISD::ADD , ISD::FADD);
00661   case ISD::VSUB:               return visitVBinOp(N, ISD::SUB , ISD::FSUB);
00662   case ISD::VMUL:               return visitVBinOp(N, ISD::MUL , ISD::FMUL);
00663   case ISD::VSDIV:              return visitVBinOp(N, ISD::SDIV, ISD::FDIV);
00664   case ISD::VUDIV:              return visitVBinOp(N, ISD::UDIV, ISD::UDIV);
00665   case ISD::VAND:               return visitVBinOp(N, ISD::AND , ISD::AND);
00666   case ISD::VOR:                return visitVBinOp(N, ISD::OR  , ISD::OR);
00667   case ISD::VXOR:               return visitVBinOp(N, ISD::XOR , ISD::XOR);
00668   }
00669   return SDOperand();
00670 }
00671 
00672 SDOperand DAGCombiner::visitTokenFactor(SDNode *N) {
00673   std::vector<SDOperand> Ops;
00674   bool Changed = false;
00675 
00676   // If the token factor has two operands and one is the entry token, replace
00677   // the token factor with the other operand.
00678   if (N->getNumOperands() == 2) {
00679     if (N->getOperand(0).getOpcode() == ISD::EntryToken)
00680       return N->getOperand(1);
00681     if (N->getOperand(1).getOpcode() == ISD::EntryToken)
00682       return N->getOperand(0);
00683   }
00684   
00685   // fold (tokenfactor (tokenfactor)) -> tokenfactor
00686   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
00687     SDOperand Op = N->getOperand(i);
00688     if (Op.getOpcode() == ISD::TokenFactor && Op.hasOneUse()) {
00689       AddToWorkList(Op.Val);  // Remove dead node.
00690       Changed = true;
00691       for (unsigned j = 0, e = Op.getNumOperands(); j != e; ++j)
00692         Ops.push_back(Op.getOperand(j));
00693     } else {
00694       Ops.push_back(Op);
00695     }
00696   }
00697   if (Changed)
00698     return DAG.getNode(ISD::TokenFactor, MVT::Other, Ops);
00699   return SDOperand();
00700 }
00701 
00702 SDOperand DAGCombiner::visitADD(SDNode *N) {
00703   SDOperand N0 = N->getOperand(0);
00704   SDOperand N1 = N->getOperand(1);
00705   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
00706   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
00707   MVT::ValueType VT = N0.getValueType();
00708   
00709   // fold (add c1, c2) -> c1+c2
00710   if (N0C && N1C)
00711     return DAG.getNode(ISD::ADD, VT, N0, N1);
00712   // canonicalize constant to RHS
00713   if (N0C && !N1C)
00714     return DAG.getNode(ISD::ADD, VT, N1, N0);
00715   // fold (add x, 0) -> x
00716   if (N1C && N1C->isNullValue())
00717     return N0;
00718   // fold ((c1-A)+c2) -> (c1+c2)-A
00719   if (N1C && N0.getOpcode() == ISD::SUB)
00720     if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.getOperand(0)))
00721       return DAG.getNode(ISD::SUB, VT,
00722                          DAG.getConstant(N1C->getValue()+N0C->getValue(), VT),
00723                          N0.getOperand(1));
00724   // reassociate add
00725   SDOperand RADD = ReassociateOps(ISD::ADD, N0, N1);
00726   if (RADD.Val != 0)
00727     return RADD;
00728   // fold ((0-A) + B) -> B-A
00729   if (N0.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N0.getOperand(0)) &&
00730       cast<ConstantSDNode>(N0.getOperand(0))->isNullValue())
00731     return DAG.getNode(ISD::SUB, VT, N1, N0.getOperand(1));
00732   // fold (A + (0-B)) -> A-B
00733   if (N1.getOpcode() == ISD::SUB && isa<ConstantSDNode>(N1.getOperand(0)) &&
00734       cast<ConstantSDNode>(N1.getOperand(0))->isNullValue())
00735     return DAG.getNode(ISD::SUB, VT, N0, N1.getOperand(1));
00736   // fold (A+(B-A)) -> B
00737   if (N1.getOpcode() == ISD::SUB && N0 == N1.getOperand(1))
00738     return N1.getOperand(0);
00739 
00740   if (!MVT::isVector(VT) && SimplifyDemandedBits(SDOperand(N, 0)))
00741     return SDOperand();
00742   
00743   // fold (a+b) -> (a|b) iff a and b share no bits.
00744   if (MVT::isInteger(VT) && !MVT::isVector(VT)) {
00745     uint64_t LHSZero, LHSOne;
00746     uint64_t RHSZero, RHSOne;
00747     uint64_t Mask = MVT::getIntVTBitMask(VT);
00748     TLI.ComputeMaskedBits(N0, Mask, LHSZero, LHSOne);
00749     if (LHSZero) {
00750       TLI.ComputeMaskedBits(N1, Mask, RHSZero, RHSOne);
00751       
00752       // If all possibly-set bits on the LHS are clear on the RHS, return an OR.
00753       // If all possibly-set bits on the RHS are clear on the LHS, return an OR.
00754       if ((RHSZero & (~LHSZero & Mask)) == (~LHSZero & Mask) ||
00755           (LHSZero & (~RHSZero & Mask)) == (~RHSZero & Mask))
00756         return DAG.getNode(ISD::OR, VT, N0, N1);
00757     }
00758   }
00759   
00760   return SDOperand();
00761 }
00762 
00763 SDOperand DAGCombiner::visitSUB(SDNode *N) {
00764   SDOperand N0 = N->getOperand(0);
00765   SDOperand N1 = N->getOperand(1);
00766   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
00767   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
00768   MVT::ValueType VT = N0.getValueType();
00769   
00770   // fold (sub x, x) -> 0
00771   if (N0 == N1)
00772     return DAG.getConstant(0, N->getValueType(0));
00773   // fold (sub c1, c2) -> c1-c2
00774   if (N0C && N1C)
00775     return DAG.getNode(ISD::SUB, VT, N0, N1);
00776   // fold (sub x, c) -> (add x, -c)
00777   if (N1C)
00778     return DAG.getNode(ISD::ADD, VT, N0, DAG.getConstant(-N1C->getValue(), VT));
00779   // fold (A+B)-A -> B
00780   if (N0.getOpcode() == ISD::ADD && N0.getOperand(0) == N1)
00781     return N0.getOperand(1);
00782   // fold (A+B)-B -> A
00783   if (N0.getOpcode() == ISD::ADD && N0.getOperand(1) == N1)
00784     return N0.getOperand(0);
00785   return SDOperand();
00786 }
00787 
00788 SDOperand DAGCombiner::visitMUL(SDNode *N) {
00789   SDOperand N0 = N->getOperand(0);
00790   SDOperand N1 = N->getOperand(1);
00791   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
00792   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
00793   MVT::ValueType VT = N0.getValueType();
00794   
00795   // fold (mul c1, c2) -> c1*c2
00796   if (N0C && N1C)
00797     return DAG.getNode(ISD::MUL, VT, N0, N1);
00798   // canonicalize constant to RHS
00799   if (N0C && !N1C)
00800     return DAG.getNode(ISD::MUL, VT, N1, N0);
00801   // fold (mul x, 0) -> 0
00802   if (N1C && N1C->isNullValue())
00803     return N1;
00804   // fold (mul x, -1) -> 0-x
00805   if (N1C && N1C->isAllOnesValue())
00806     return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0);
00807   // fold (mul x, (1 << c)) -> x << c
00808   if (N1C && isPowerOf2_64(N1C->getValue()))
00809     return DAG.getNode(ISD::SHL, VT, N0,
00810                        DAG.getConstant(Log2_64(N1C->getValue()),
00811                                        TLI.getShiftAmountTy()));
00812   // fold (mul x, -(1 << c)) -> -(x << c) or (-x) << c
00813   if (N1C && isPowerOf2_64(-N1C->getSignExtended())) {
00814     // FIXME: If the input is something that is easily negated (e.g. a 
00815     // single-use add), we should put the negate there.
00816     return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT),
00817                        DAG.getNode(ISD::SHL, VT, N0,
00818                             DAG.getConstant(Log2_64(-N1C->getSignExtended()),
00819                                             TLI.getShiftAmountTy())));
00820   }
00821 
00822   // (mul (shl X, c1), c2) -> (mul X, c2 << c1)
00823   if (N1C && N0.getOpcode() == ISD::SHL && 
00824       isa<ConstantSDNode>(N0.getOperand(1))) {
00825     SDOperand C3 = DAG.getNode(ISD::SHL, VT, N1, N0.getOperand(1));
00826     AddToWorkList(C3.Val);
00827     return DAG.getNode(ISD::MUL, VT, N0.getOperand(0), C3);
00828   }
00829   
00830   // Change (mul (shl X, C), Y) -> (shl (mul X, Y), C) when the shift has one
00831   // use.
00832   {
00833     SDOperand Sh(0,0), Y(0,0);
00834     // Check for both (mul (shl X, C), Y)  and  (mul Y, (shl X, C)).
00835     if (N0.getOpcode() == ISD::SHL && isa<ConstantSDNode>(N0.getOperand(1)) &&
00836         N0.Val->hasOneUse()) {
00837       Sh = N0; Y = N1;
00838     } else if (N1.getOpcode() == ISD::SHL && 
00839                isa<ConstantSDNode>(N1.getOperand(1)) && N1.Val->hasOneUse()) {
00840       Sh = N1; Y = N0;
00841     }
00842     if (Sh.Val) {
00843       SDOperand Mul = DAG.getNode(ISD::MUL, VT, Sh.getOperand(0), Y);
00844       return DAG.getNode(ISD::SHL, VT, Mul, Sh.getOperand(1));
00845     }
00846   }
00847   // fold (mul (add x, c1), c2) -> (add (mul x, c2), c1*c2)
00848   if (N1C && N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse() && 
00849       isa<ConstantSDNode>(N0.getOperand(1))) {
00850     return DAG.getNode(ISD::ADD, VT, 
00851                        DAG.getNode(ISD::MUL, VT, N0.getOperand(0), N1),
00852                        DAG.getNode(ISD::MUL, VT, N0.getOperand(1), N1));
00853   }
00854   
00855   // reassociate mul
00856   SDOperand RMUL = ReassociateOps(ISD::MUL, N0, N1);
00857   if (RMUL.Val != 0)
00858     return RMUL;
00859   return SDOperand();
00860 }
00861 
00862 SDOperand DAGCombiner::visitSDIV(SDNode *N) {
00863   SDOperand N0 = N->getOperand(0);
00864   SDOperand N1 = N->getOperand(1);
00865   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
00866   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
00867   MVT::ValueType VT = N->getValueType(0);
00868 
00869   // fold (sdiv c1, c2) -> c1/c2
00870   if (N0C && N1C && !N1C->isNullValue())
00871     return DAG.getNode(ISD::SDIV, VT, N0, N1);
00872   // fold (sdiv X, 1) -> X
00873   if (N1C && N1C->getSignExtended() == 1LL)
00874     return N0;
00875   // fold (sdiv X, -1) -> 0-X
00876   if (N1C && N1C->isAllOnesValue())
00877     return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), N0);
00878   // If we know the sign bits of both operands are zero, strength reduce to a
00879   // udiv instead.  Handles (X&15) /s 4 -> X&15 >> 2
00880   uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1);
00881   if (TLI.MaskedValueIsZero(N1, SignBit) &&
00882       TLI.MaskedValueIsZero(N0, SignBit))
00883     return DAG.getNode(ISD::UDIV, N1.getValueType(), N0, N1);
00884   // fold (sdiv X, pow2) -> simple ops after legalize
00885   if (N1C && N1C->getValue() && !TLI.isIntDivCheap() &&
00886       (isPowerOf2_64(N1C->getSignExtended()) || 
00887        isPowerOf2_64(-N1C->getSignExtended()))) {
00888     // If dividing by powers of two is cheap, then don't perform the following
00889     // fold.
00890     if (TLI.isPow2DivCheap())
00891       return SDOperand();
00892     int64_t pow2 = N1C->getSignExtended();
00893     int64_t abs2 = pow2 > 0 ? pow2 : -pow2;
00894     unsigned lg2 = Log2_64(abs2);
00895     // Splat the sign bit into the register
00896     SDOperand SGN = DAG.getNode(ISD::SRA, VT, N0,
00897                                 DAG.getConstant(MVT::getSizeInBits(VT)-1,
00898                                                 TLI.getShiftAmountTy()));
00899     AddToWorkList(SGN.Val);
00900     // Add (N0 < 0) ? abs2 - 1 : 0;
00901     SDOperand SRL = DAG.getNode(ISD::SRL, VT, SGN,
00902                                 DAG.getConstant(MVT::getSizeInBits(VT)-lg2,
00903                                                 TLI.getShiftAmountTy()));
00904     SDOperand ADD = DAG.getNode(ISD::ADD, VT, N0, SRL);
00905     AddToWorkList(SRL.Val);
00906     AddToWorkList(ADD.Val);    // Divide by pow2
00907     SDOperand SRA = DAG.getNode(ISD::SRA, VT, ADD,
00908                                 DAG.getConstant(lg2, TLI.getShiftAmountTy()));
00909     // If we're dividing by a positive value, we're done.  Otherwise, we must
00910     // negate the result.
00911     if (pow2 > 0)
00912       return SRA;
00913     AddToWorkList(SRA.Val);
00914     return DAG.getNode(ISD::SUB, VT, DAG.getConstant(0, VT), SRA);
00915   }
00916   // if integer divide is expensive and we satisfy the requirements, emit an
00917   // alternate sequence.
00918   if (N1C && (N1C->getSignExtended() < -1 || N1C->getSignExtended() > 1) && 
00919       !TLI.isIntDivCheap()) {
00920     SDOperand Op = BuildSDIV(N);
00921     if (Op.Val) return Op;
00922   }
00923   return SDOperand();
00924 }
00925 
00926 SDOperand DAGCombiner::visitUDIV(SDNode *N) {
00927   SDOperand N0 = N->getOperand(0);
00928   SDOperand N1 = N->getOperand(1);
00929   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
00930   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
00931   MVT::ValueType VT = N->getValueType(0);
00932   
00933   // fold (udiv c1, c2) -> c1/c2
00934   if (N0C && N1C && !N1C->isNullValue())
00935     return DAG.getNode(ISD::UDIV, VT, N0, N1);
00936   // fold (udiv x, (1 << c)) -> x >>u c
00937   if (N1C && isPowerOf2_64(N1C->getValue()))
00938     return DAG.getNode(ISD::SRL, VT, N0, 
00939                        DAG.getConstant(Log2_64(N1C->getValue()),
00940                                        TLI.getShiftAmountTy()));
00941   // fold (udiv x, (shl c, y)) -> x >>u (log2(c)+y) iff c is power of 2
00942   if (N1.getOpcode() == ISD::SHL) {
00943     if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) {
00944       if (isPowerOf2_64(SHC->getValue())) {
00945         MVT::ValueType ADDVT = N1.getOperand(1).getValueType();
00946         SDOperand Add = DAG.getNode(ISD::ADD, ADDVT, N1.getOperand(1),
00947                                     DAG.getConstant(Log2_64(SHC->getValue()),
00948                                                     ADDVT));
00949         AddToWorkList(Add.Val);
00950         return DAG.getNode(ISD::SRL, VT, N0, Add);
00951       }
00952     }
00953   }
00954   // fold (udiv x, c) -> alternate
00955   if (N1C && N1C->getValue() && !TLI.isIntDivCheap()) {
00956     SDOperand Op = BuildUDIV(N);
00957     if (Op.Val) return Op;
00958   }
00959   return SDOperand();
00960 }
00961 
00962 SDOperand DAGCombiner::visitSREM(SDNode *N) {
00963   SDOperand N0 = N->getOperand(0);
00964   SDOperand N1 = N->getOperand(1);
00965   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
00966   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
00967   MVT::ValueType VT = N->getValueType(0);
00968   
00969   // fold (srem c1, c2) -> c1%c2
00970   if (N0C && N1C && !N1C->isNullValue())
00971     return DAG.getNode(ISD::SREM, VT, N0, N1);
00972   // If we know the sign bits of both operands are zero, strength reduce to a
00973   // urem instead.  Handles (X & 0x0FFFFFFF) %s 16 -> X&15
00974   uint64_t SignBit = 1ULL << (MVT::getSizeInBits(VT)-1);
00975   if (TLI.MaskedValueIsZero(N1, SignBit) &&
00976       TLI.MaskedValueIsZero(N0, SignBit))
00977     return DAG.getNode(ISD::UREM, VT, N0, N1);
00978   return SDOperand();
00979 }
00980 
00981 SDOperand DAGCombiner::visitUREM(SDNode *N) {
00982   SDOperand N0 = N->getOperand(0);
00983   SDOperand N1 = N->getOperand(1);
00984   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
00985   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
00986   MVT::ValueType VT = N->getValueType(0);
00987   
00988   // fold (urem c1, c2) -> c1%c2
00989   if (N0C && N1C && !N1C->isNullValue())
00990     return DAG.getNode(ISD::UREM, VT, N0, N1);
00991   // fold (urem x, pow2) -> (and x, pow2-1)
00992   if (N1C && !N1C->isNullValue() && isPowerOf2_64(N1C->getValue()))
00993     return DAG.getNode(ISD::AND, VT, N0, DAG.getConstant(N1C->getValue()-1,VT));
00994   // fold (urem x, (shl pow2, y)) -> (and x, (add (shl pow2, y), -1))
00995   if (N1.getOpcode() == ISD::SHL) {
00996     if (ConstantSDNode *SHC = dyn_cast<ConstantSDNode>(N1.getOperand(0))) {
00997       if (isPowerOf2_64(SHC->getValue())) {
00998         SDOperand Add = DAG.getNode(ISD::ADD, VT, N1,DAG.getConstant(~0ULL,VT));
00999         AddToWorkList(Add.Val);
01000         return DAG.getNode(ISD::AND, VT, N0, Add);
01001       }
01002     }
01003   }
01004   return SDOperand();
01005 }
01006 
01007 SDOperand DAGCombiner::visitMULHS(SDNode *N) {
01008   SDOperand N0 = N->getOperand(0);
01009   SDOperand N1 = N->getOperand(1);
01010   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01011   
01012   // fold (mulhs x, 0) -> 0
01013   if (N1C && N1C->isNullValue())
01014     return N1;
01015   // fold (mulhs x, 1) -> (sra x, size(x)-1)
01016   if (N1C && N1C->getValue() == 1)
01017     return DAG.getNode(ISD::SRA, N0.getValueType(), N0, 
01018                        DAG.getConstant(MVT::getSizeInBits(N0.getValueType())-1,
01019                                        TLI.getShiftAmountTy()));
01020   return SDOperand();
01021 }
01022 
01023 SDOperand DAGCombiner::visitMULHU(SDNode *N) {
01024   SDOperand N0 = N->getOperand(0);
01025   SDOperand N1 = N->getOperand(1);
01026   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01027   
01028   // fold (mulhu x, 0) -> 0
01029   if (N1C && N1C->isNullValue())
01030     return N1;
01031   // fold (mulhu x, 1) -> 0
01032   if (N1C && N1C->getValue() == 1)
01033     return DAG.getConstant(0, N0.getValueType());
01034   return SDOperand();
01035 }
01036 
01037 SDOperand DAGCombiner::visitAND(SDNode *N) {
01038   SDOperand N0 = N->getOperand(0);
01039   SDOperand N1 = N->getOperand(1);
01040   SDOperand LL, LR, RL, RR, CC0, CC1;
01041   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01042   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01043   MVT::ValueType VT = N1.getValueType();
01044   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
01045   
01046   // fold (and c1, c2) -> c1&c2
01047   if (N0C && N1C)
01048     return DAG.getNode(ISD::AND, VT, N0, N1);
01049   // canonicalize constant to RHS
01050   if (N0C && !N1C)
01051     return DAG.getNode(ISD::AND, VT, N1, N0);
01052   // fold (and x, -1) -> x
01053   if (N1C && N1C->isAllOnesValue())
01054     return N0;
01055   // if (and x, c) is known to be zero, return 0
01056   if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
01057     return DAG.getConstant(0, VT);
01058   // reassociate and
01059   SDOperand RAND = ReassociateOps(ISD::AND, N0, N1);
01060   if (RAND.Val != 0)
01061     return RAND;
01062   // fold (and (or x, 0xFFFF), 0xFF) -> 0xFF
01063   if (N1C && N0.getOpcode() == ISD::OR)
01064     if (ConstantSDNode *ORI = dyn_cast<ConstantSDNode>(N0.getOperand(1)))
01065       if ((ORI->getValue() & N1C->getValue()) == N1C->getValue())
01066         return N1;
01067   // fold (and (any_ext V), c) -> (zero_ext V) if 'and' only clears top bits.
01068   if (N1C && N0.getOpcode() == ISD::ANY_EXTEND) {
01069     unsigned InMask = MVT::getIntVTBitMask(N0.getOperand(0).getValueType());
01070     if (TLI.MaskedValueIsZero(N0.getOperand(0),
01071                               ~N1C->getValue() & InMask)) {
01072       SDOperand Zext = DAG.getNode(ISD::ZERO_EXTEND, N0.getValueType(),
01073                                    N0.getOperand(0));
01074       
01075       // Replace uses of the AND with uses of the Zero extend node.
01076       CombineTo(N, Zext);
01077       
01078       // We actually want to replace all uses of the any_extend with the
01079       // zero_extend, to avoid duplicating things.  This will later cause this
01080       // AND to be folded.
01081       CombineTo(N0.Val, Zext);
01082       return SDOperand();
01083     }
01084   }
01085   // fold (and (setcc x), (setcc y)) -> (setcc (and x, y))
01086   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
01087     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
01088     ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
01089     
01090     if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
01091         MVT::isInteger(LL.getValueType())) {
01092       // fold (X == 0) & (Y == 0) -> (X|Y == 0)
01093       if (cast<ConstantSDNode>(LR)->getValue() == 0 && Op1 == ISD::SETEQ) {
01094         SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
01095         AddToWorkList(ORNode.Val);
01096         return DAG.getSetCC(VT, ORNode, LR, Op1);
01097       }
01098       // fold (X == -1) & (Y == -1) -> (X&Y == -1)
01099       if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETEQ) {
01100         SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL);
01101         AddToWorkList(ANDNode.Val);
01102         return DAG.getSetCC(VT, ANDNode, LR, Op1);
01103       }
01104       // fold (X >  -1) & (Y >  -1) -> (X|Y > -1)
01105       if (cast<ConstantSDNode>(LR)->isAllOnesValue() && Op1 == ISD::SETGT) {
01106         SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
01107         AddToWorkList(ORNode.Val);
01108         return DAG.getSetCC(VT, ORNode, LR, Op1);
01109       }
01110     }
01111     // canonicalize equivalent to ll == rl
01112     if (LL == RR && LR == RL) {
01113       Op1 = ISD::getSetCCSwappedOperands(Op1);
01114       std::swap(RL, RR);
01115     }
01116     if (LL == RL && LR == RR) {
01117       bool isInteger = MVT::isInteger(LL.getValueType());
01118       ISD::CondCode Result = ISD::getSetCCAndOperation(Op0, Op1, isInteger);
01119       if (Result != ISD::SETCC_INVALID)
01120         return DAG.getSetCC(N0.getValueType(), LL, LR, Result);
01121     }
01122   }
01123   // fold (and (zext x), (zext y)) -> (zext (and x, y))
01124   if (N0.getOpcode() == ISD::ZERO_EXTEND && 
01125       N1.getOpcode() == ISD::ZERO_EXTEND &&
01126       N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
01127     SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(),
01128                                     N0.getOperand(0), N1.getOperand(0));
01129     AddToWorkList(ANDNode.Val);
01130     return DAG.getNode(ISD::ZERO_EXTEND, VT, ANDNode);
01131   }
01132   // fold (and (shl/srl/sra x), (shl/srl/sra y)) -> (shl/srl/sra (and x, y))
01133   if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) ||
01134        (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL) ||
01135        (N0.getOpcode() == ISD::SRA && N1.getOpcode() == ISD::SRA)) &&
01136       N0.getOperand(1) == N1.getOperand(1)) {
01137     SDOperand ANDNode = DAG.getNode(ISD::AND, N0.getOperand(0).getValueType(),
01138                                     N0.getOperand(0), N1.getOperand(0));
01139     AddToWorkList(ANDNode.Val);
01140     return DAG.getNode(N0.getOpcode(), VT, ANDNode, N0.getOperand(1));
01141   }
01142   // fold (and (sign_extend_inreg x, i16 to i32), 1) -> (and x, 1)
01143   // fold (and (sra)) -> (and (srl)) when possible.
01144   if (!MVT::isVector(VT) &&
01145       SimplifyDemandedBits(SDOperand(N, 0)))
01146     return SDOperand();
01147   // fold (zext_inreg (extload x)) -> (zextload x)
01148   if (N0.getOpcode() == ISD::EXTLOAD) {
01149     MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT();
01150     // If we zero all the possible extended bits, then we can turn this into
01151     // a zextload if we are running before legalize or the operation is legal.
01152     if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) &&
01153         (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) {
01154       SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0),
01155                                          N0.getOperand(1), N0.getOperand(2),
01156                                          EVT);
01157       AddToWorkList(N);
01158       CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
01159       return SDOperand();
01160     }
01161   }
01162   // fold (zext_inreg (sextload x)) -> (zextload x) iff load has one use
01163   if (N0.getOpcode() == ISD::SEXTLOAD && N0.hasOneUse()) {
01164     MVT::ValueType EVT = cast<VTSDNode>(N0.getOperand(3))->getVT();
01165     // If we zero all the possible extended bits, then we can turn this into
01166     // a zextload if we are running before legalize or the operation is legal.
01167     if (TLI.MaskedValueIsZero(N1, ~0ULL << MVT::getSizeInBits(EVT)) &&
01168         (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) {
01169       SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0),
01170                                          N0.getOperand(1), N0.getOperand(2),
01171                                          EVT);
01172       AddToWorkList(N);
01173       CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
01174       return SDOperand();
01175     }
01176   }
01177   
01178   // fold (and (load x), 255) -> (zextload x, i8)
01179   // fold (and (extload x, i16), 255) -> (zextload x, i8)
01180   if (N1C &&
01181       (N0.getOpcode() == ISD::LOAD || N0.getOpcode() == ISD::EXTLOAD ||
01182        N0.getOpcode() == ISD::ZEXTLOAD) &&
01183       N0.hasOneUse()) {
01184     MVT::ValueType EVT, LoadedVT;
01185     if (N1C->getValue() == 255)
01186       EVT = MVT::i8;
01187     else if (N1C->getValue() == 65535)
01188       EVT = MVT::i16;
01189     else if (N1C->getValue() == ~0U)
01190       EVT = MVT::i32;
01191     else
01192       EVT = MVT::Other;
01193     
01194     LoadedVT = N0.getOpcode() == ISD::LOAD ? VT :
01195                            cast<VTSDNode>(N0.getOperand(3))->getVT();
01196     if (EVT != MVT::Other && LoadedVT > EVT &&
01197         (!AfterLegalize || TLI.isOperationLegal(ISD::ZEXTLOAD, EVT))) {
01198       MVT::ValueType PtrType = N0.getOperand(1).getValueType();
01199       // For big endian targets, we need to add an offset to the pointer to load
01200       // the correct bytes.  For little endian systems, we merely need to read
01201       // fewer bytes from the same pointer.
01202       unsigned PtrOff =
01203         (MVT::getSizeInBits(LoadedVT) - MVT::getSizeInBits(EVT)) / 8;
01204       SDOperand NewPtr = N0.getOperand(1);
01205       if (!TLI.isLittleEndian())
01206         NewPtr = DAG.getNode(ISD::ADD, PtrType, NewPtr,
01207                              DAG.getConstant(PtrOff, PtrType));
01208       AddToWorkList(NewPtr.Val);
01209       SDOperand Load =
01210         DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0), NewPtr,
01211                        N0.getOperand(2), EVT);
01212       AddToWorkList(N);
01213       CombineTo(N0.Val, Load, Load.getValue(1));
01214       return SDOperand();
01215     }
01216   }
01217   
01218   return SDOperand();
01219 }
01220 
01221 SDOperand DAGCombiner::visitOR(SDNode *N) {
01222   SDOperand N0 = N->getOperand(0);
01223   SDOperand N1 = N->getOperand(1);
01224   SDOperand LL, LR, RL, RR, CC0, CC1;
01225   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01226   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01227   MVT::ValueType VT = N1.getValueType();
01228   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
01229   
01230   // fold (or c1, c2) -> c1|c2
01231   if (N0C && N1C)
01232     return DAG.getNode(ISD::OR, VT, N0, N1);
01233   // canonicalize constant to RHS
01234   if (N0C && !N1C)
01235     return DAG.getNode(ISD::OR, VT, N1, N0);
01236   // fold (or x, 0) -> x
01237   if (N1C && N1C->isNullValue())
01238     return N0;
01239   // fold (or x, -1) -> -1
01240   if (N1C && N1C->isAllOnesValue())
01241     return N1;
01242   // fold (or x, c) -> c iff (x & ~c) == 0
01243   if (N1C && 
01244       TLI.MaskedValueIsZero(N0,~N1C->getValue() & (~0ULL>>(64-OpSizeInBits))))
01245     return N1;
01246   // reassociate or
01247   SDOperand ROR = ReassociateOps(ISD::OR, N0, N1);
01248   if (ROR.Val != 0)
01249     return ROR;
01250   // Canonicalize (or (and X, c1), c2) -> (and (or X, c2), c1|c2)
01251   if (N1C && N0.getOpcode() == ISD::AND && N0.Val->hasOneUse() &&
01252              isa<ConstantSDNode>(N0.getOperand(1))) {
01253     ConstantSDNode *C1 = cast<ConstantSDNode>(N0.getOperand(1));
01254     return DAG.getNode(ISD::AND, VT, DAG.getNode(ISD::OR, VT, N0.getOperand(0),
01255                                                  N1),
01256                        DAG.getConstant(N1C->getValue() | C1->getValue(), VT));
01257   }
01258   // fold (or (setcc x), (setcc y)) -> (setcc (or x, y))
01259   if (isSetCCEquivalent(N0, LL, LR, CC0) && isSetCCEquivalent(N1, RL, RR, CC1)){
01260     ISD::CondCode Op0 = cast<CondCodeSDNode>(CC0)->get();
01261     ISD::CondCode Op1 = cast<CondCodeSDNode>(CC1)->get();
01262     
01263     if (LR == RR && isa<ConstantSDNode>(LR) && Op0 == Op1 &&
01264         MVT::isInteger(LL.getValueType())) {
01265       // fold (X != 0) | (Y != 0) -> (X|Y != 0)
01266       // fold (X <  0) | (Y <  0) -> (X|Y < 0)
01267       if (cast<ConstantSDNode>(LR)->getValue() == 0 && 
01268           (Op1 == ISD::SETNE || Op1 == ISD::SETLT)) {
01269         SDOperand ORNode = DAG.getNode(ISD::OR, LR.getValueType(), LL, RL);
01270         AddToWorkList(ORNode.Val);
01271         return DAG.getSetCC(VT, ORNode, LR, Op1);
01272       }
01273       // fold (X != -1) | (Y != -1) -> (X&Y != -1)
01274       // fold (X >  -1) | (Y >  -1) -> (X&Y >  -1)
01275       if (cast<ConstantSDNode>(LR)->isAllOnesValue() && 
01276           (Op1 == ISD::SETNE || Op1 == ISD::SETGT)) {
01277         SDOperand ANDNode = DAG.getNode(ISD::AND, LR.getValueType(), LL, RL);
01278         AddToWorkList(ANDNode.Val);
01279         return DAG.getSetCC(VT, ANDNode, LR, Op1);
01280       }
01281     }
01282     // canonicalize equivalent to ll == rl
01283     if (LL == RR && LR == RL) {
01284       Op1 = ISD::getSetCCSwappedOperands(Op1);
01285       std::swap(RL, RR);
01286     }
01287     if (LL == RL && LR == RR) {
01288       bool isInteger = MVT::isInteger(LL.getValueType());
01289       ISD::CondCode Result = ISD::getSetCCOrOperation(Op0, Op1, isInteger);
01290       if (Result != ISD::SETCC_INVALID)
01291         return DAG.getSetCC(N0.getValueType(), LL, LR, Result);
01292     }
01293   }
01294   // fold (or (zext x), (zext y)) -> (zext (or x, y))
01295   if (N0.getOpcode() == ISD::ZERO_EXTEND && 
01296       N1.getOpcode() == ISD::ZERO_EXTEND &&
01297       N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
01298     SDOperand ORNode = DAG.getNode(ISD::OR, N0.getOperand(0).getValueType(),
01299                                    N0.getOperand(0), N1.getOperand(0));
01300     AddToWorkList(ORNode.Val);
01301     return DAG.getNode(ISD::ZERO_EXTEND, VT, ORNode);
01302   }
01303   // fold (or (shl/srl/sra x), (shl/srl/sra y)) -> (shl/srl/sra (or x, y))
01304   if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) ||
01305        (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL) ||
01306        (N0.getOpcode() == ISD::SRA && N1.getOpcode() == ISD::SRA)) &&
01307       N0.getOperand(1) == N1.getOperand(1)) {
01308     SDOperand ORNode = DAG.getNode(ISD::OR, N0.getOperand(0).getValueType(),
01309                                    N0.getOperand(0), N1.getOperand(0));
01310     AddToWorkList(ORNode.Val);
01311     return DAG.getNode(N0.getOpcode(), VT, ORNode, N0.getOperand(1));
01312   }
01313   // canonicalize shl to left side in a shl/srl pair, to match rotate
01314   if (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SHL)
01315     std::swap(N0, N1);
01316   // check for rotl, rotr
01317   if (N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SRL &&
01318       N0.getOperand(0) == N1.getOperand(0) &&
01319       TLI.isOperationLegal(ISD::ROTL, VT) && TLI.isTypeLegal(VT)) {
01320     // fold (or (shl x, C1), (srl x, C2)) -> (rotl x, C1)
01321     if (N0.getOperand(1).getOpcode() == ISD::Constant &&
01322         N1.getOperand(1).getOpcode() == ISD::Constant) {
01323       uint64_t c1val = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
01324       uint64_t c2val = cast<ConstantSDNode>(N1.getOperand(1))->getValue();
01325       if ((c1val + c2val) == OpSizeInBits)
01326         return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), N0.getOperand(1));
01327     }
01328     // fold (or (shl x, y), (srl x, (sub 32, y))) -> (rotl x, y)
01329     if (N1.getOperand(1).getOpcode() == ISD::SUB &&
01330         N0.getOperand(1) == N1.getOperand(1).getOperand(1))
01331       if (ConstantSDNode *SUBC = 
01332           dyn_cast<ConstantSDNode>(N1.getOperand(1).getOperand(0)))
01333         if (SUBC->getValue() == OpSizeInBits)
01334           return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0), N0.getOperand(1));
01335     // fold (or (shl x, (sub 32, y)), (srl x, r)) -> (rotr x, y)
01336     if (N0.getOperand(1).getOpcode() == ISD::SUB &&
01337         N1.getOperand(1) == N0.getOperand(1).getOperand(1))
01338       if (ConstantSDNode *SUBC = 
01339           dyn_cast<ConstantSDNode>(N0.getOperand(1).getOperand(0)))
01340         if (SUBC->getValue() == OpSizeInBits) {
01341           if (TLI.isOperationLegal(ISD::ROTR, VT) && TLI.isTypeLegal(VT))
01342             return DAG.getNode(ISD::ROTR, VT, N0.getOperand(0), 
01343                                N1.getOperand(1));
01344           else
01345             return DAG.getNode(ISD::ROTL, VT, N0.getOperand(0),
01346                                N0.getOperand(1));
01347         }
01348   }
01349   return SDOperand();
01350 }
01351 
01352 SDOperand DAGCombiner::visitXOR(SDNode *N) {
01353   SDOperand N0 = N->getOperand(0);
01354   SDOperand N1 = N->getOperand(1);
01355   SDOperand LHS, RHS, CC;
01356   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01357   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01358   MVT::ValueType VT = N0.getValueType();
01359   
01360   // fold (xor c1, c2) -> c1^c2
01361   if (N0C && N1C)
01362     return DAG.getNode(ISD::XOR, VT, N0, N1);
01363   // canonicalize constant to RHS
01364   if (N0C && !N1C)
01365     return DAG.getNode(ISD::XOR, VT, N1, N0);
01366   // fold (xor x, 0) -> x
01367   if (N1C && N1C->isNullValue())
01368     return N0;
01369   // reassociate xor
01370   SDOperand RXOR = ReassociateOps(ISD::XOR, N0, N1);
01371   if (RXOR.Val != 0)
01372     return RXOR;
01373   // fold !(x cc y) -> (x !cc y)
01374   if (N1C && N1C->getValue() == 1 && isSetCCEquivalent(N0, LHS, RHS, CC)) {
01375     bool isInt = MVT::isInteger(LHS.getValueType());
01376     ISD::CondCode NotCC = ISD::getSetCCInverse(cast<CondCodeSDNode>(CC)->get(),
01377                                                isInt);
01378     if (N0.getOpcode() == ISD::SETCC)
01379       return DAG.getSetCC(VT, LHS, RHS, NotCC);
01380     if (N0.getOpcode() == ISD::SELECT_CC)
01381       return DAG.getSelectCC(LHS, RHS, N0.getOperand(2),N0.getOperand(3),NotCC);
01382     assert(0 && "Unhandled SetCC Equivalent!");
01383     abort();
01384   }
01385   // fold !(x or y) -> (!x and !y) iff x or y are setcc
01386   if (N1C && N1C->getValue() == 1 && 
01387       (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) {
01388     SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
01389     if (isOneUseSetCC(RHS) || isOneUseSetCC(LHS)) {
01390       unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND;
01391       LHS = DAG.getNode(ISD::XOR, VT, LHS, N1);  // RHS = ~LHS
01392       RHS = DAG.getNode(ISD::XOR, VT, RHS, N1);  // RHS = ~RHS
01393       AddToWorkList(LHS.Val); AddToWorkList(RHS.Val);
01394       return DAG.getNode(NewOpcode, VT, LHS, RHS);
01395     }
01396   }
01397   // fold !(x or y) -> (!x and !y) iff x or y are constants
01398   if (N1C && N1C->isAllOnesValue() && 
01399       (N0.getOpcode() == ISD::OR || N0.getOpcode() == ISD::AND)) {
01400     SDOperand LHS = N0.getOperand(0), RHS = N0.getOperand(1);
01401     if (isa<ConstantSDNode>(RHS) || isa<ConstantSDNode>(LHS)) {
01402       unsigned NewOpcode = N0.getOpcode() == ISD::AND ? ISD::OR : ISD::AND;
01403       LHS = DAG.getNode(ISD::XOR, VT, LHS, N1);  // RHS = ~LHS
01404       RHS = DAG.getNode(ISD::XOR, VT, RHS, N1);  // RHS = ~RHS
01405       AddToWorkList(LHS.Val); AddToWorkList(RHS.Val);
01406       return DAG.getNode(NewOpcode, VT, LHS, RHS);
01407     }
01408   }
01409   // fold (xor (xor x, c1), c2) -> (xor x, c1^c2)
01410   if (N1C && N0.getOpcode() == ISD::XOR) {
01411     ConstantSDNode *N00C = dyn_cast<ConstantSDNode>(N0.getOperand(0));
01412     ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0.getOperand(1));
01413     if (N00C)
01414       return DAG.getNode(ISD::XOR, VT, N0.getOperand(1),
01415                          DAG.getConstant(N1C->getValue()^N00C->getValue(), VT));
01416     if (N01C)
01417       return DAG.getNode(ISD::XOR, VT, N0.getOperand(0),
01418                          DAG.getConstant(N1C->getValue()^N01C->getValue(), VT));
01419   }
01420   // fold (xor x, x) -> 0
01421   if (N0 == N1) {
01422     if (!MVT::isVector(VT)) {
01423       return DAG.getConstant(0, VT);
01424     } else if (!AfterLegalize || TLI.isOperationLegal(ISD::BUILD_VECTOR, VT)) {
01425       // Produce a vector of zeros.
01426       SDOperand El = DAG.getConstant(0, MVT::getVectorBaseType(VT));
01427       std::vector<SDOperand> Ops(MVT::getVectorNumElements(VT), El);
01428       return DAG.getNode(ISD::BUILD_VECTOR, VT, Ops);
01429     }
01430   }
01431   // fold (xor (zext x), (zext y)) -> (zext (xor x, y))
01432   if (N0.getOpcode() == ISD::ZERO_EXTEND && 
01433       N1.getOpcode() == ISD::ZERO_EXTEND &&
01434       N0.getOperand(0).getValueType() == N1.getOperand(0).getValueType()) {
01435     SDOperand XORNode = DAG.getNode(ISD::XOR, N0.getOperand(0).getValueType(),
01436                                    N0.getOperand(0), N1.getOperand(0));
01437     AddToWorkList(XORNode.Val);
01438     return DAG.getNode(ISD::ZERO_EXTEND, VT, XORNode);
01439   }
01440   // fold (xor (shl/srl/sra x), (shl/srl/sra y)) -> (shl/srl/sra (xor x, y))
01441   if (((N0.getOpcode() == ISD::SHL && N1.getOpcode() == ISD::SHL) ||
01442        (N0.getOpcode() == ISD::SRL && N1.getOpcode() == ISD::SRL) ||
01443        (N0.getOpcode() == ISD::SRA && N1.getOpcode() == ISD::SRA)) &&
01444       N0.getOperand(1) == N1.getOperand(1)) {
01445     SDOperand XORNode = DAG.getNode(ISD::XOR, N0.getOperand(0).getValueType(),
01446                                     N0.getOperand(0), N1.getOperand(0));
01447     AddToWorkList(XORNode.Val);
01448     return DAG.getNode(N0.getOpcode(), VT, XORNode, N0.getOperand(1));
01449   }
01450 
01451   // Simplify the expression using non-local knowledge.
01452   if (!MVT::isVector(VT) &&
01453       SimplifyDemandedBits(SDOperand(N, 0)))
01454     return SDOperand();
01455   
01456   return SDOperand();
01457 }
01458 
01459 SDOperand DAGCombiner::visitSHL(SDNode *N) {
01460   SDOperand N0 = N->getOperand(0);
01461   SDOperand N1 = N->getOperand(1);
01462   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01463   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01464   MVT::ValueType VT = N0.getValueType();
01465   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
01466   
01467   // fold (shl c1, c2) -> c1<<c2
01468   if (N0C && N1C)
01469     return DAG.getNode(ISD::SHL, VT, N0, N1);
01470   // fold (shl 0, x) -> 0
01471   if (N0C && N0C->isNullValue())
01472     return N0;
01473   // fold (shl x, c >= size(x)) -> undef
01474   if (N1C && N1C->getValue() >= OpSizeInBits)
01475     return DAG.getNode(ISD::UNDEF, VT);
01476   // fold (shl x, 0) -> x
01477   if (N1C && N1C->isNullValue())
01478     return N0;
01479   // if (shl x, c) is known to be zero, return 0
01480   if (TLI.MaskedValueIsZero(SDOperand(N, 0), MVT::getIntVTBitMask(VT)))
01481     return DAG.getConstant(0, VT);
01482   if (SimplifyDemandedBits(SDOperand(N, 0)))
01483     return SDOperand();
01484   // fold (shl (shl x, c1), c2) -> 0 or (shl x, c1+c2)
01485   if (N1C && N0.getOpcode() == ISD::SHL && 
01486       N0.getOperand(1).getOpcode() == ISD::Constant) {
01487     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
01488     uint64_t c2 = N1C->getValue();
01489     if (c1 + c2 > OpSizeInBits)
01490       return DAG.getConstant(0, VT);
01491     return DAG.getNode(ISD::SHL, VT, N0.getOperand(0), 
01492                        DAG.getConstant(c1 + c2, N1.getValueType()));
01493   }
01494   // fold (shl (srl x, c1), c2) -> (shl (and x, -1 << c1), c2-c1) or
01495   //                               (srl (and x, -1 << c1), c1-c2)
01496   if (N1C && N0.getOpcode() == ISD::SRL && 
01497       N0.getOperand(1).getOpcode() == ISD::Constant) {
01498     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
01499     uint64_t c2 = N1C->getValue();
01500     SDOperand Mask = DAG.getNode(ISD::AND, VT, N0.getOperand(0),
01501                                  DAG.getConstant(~0ULL << c1, VT));
01502     if (c2 > c1)
01503       return DAG.getNode(ISD::SHL, VT, Mask, 
01504                          DAG.getConstant(c2-c1, N1.getValueType()));
01505     else
01506       return DAG.getNode(ISD::SRL, VT, Mask, 
01507                          DAG.getConstant(c1-c2, N1.getValueType()));
01508   }
01509   // fold (shl (sra x, c1), c1) -> (and x, -1 << c1)
01510   if (N1C && N0.getOpcode() == ISD::SRA && N1 == N0.getOperand(1))
01511     return DAG.getNode(ISD::AND, VT, N0.getOperand(0),
01512                        DAG.getConstant(~0ULL << N1C->getValue(), VT));
01513   // fold (shl (add x, c1), c2) -> (add (shl x, c2), c1<<c2)
01514   if (N1C && N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse() && 
01515       isa<ConstantSDNode>(N0.getOperand(1))) {
01516     return DAG.getNode(ISD::ADD, VT, 
01517                        DAG.getNode(ISD::SHL, VT, N0.getOperand(0), N1),
01518                        DAG.getNode(ISD::SHL, VT, N0.getOperand(1), N1));
01519   }
01520   return SDOperand();
01521 }
01522 
01523 SDOperand DAGCombiner::visitSRA(SDNode *N) {
01524   SDOperand N0 = N->getOperand(0);
01525   SDOperand N1 = N->getOperand(1);
01526   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01527   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01528   MVT::ValueType VT = N0.getValueType();
01529   
01530   // fold (sra c1, c2) -> c1>>c2
01531   if (N0C && N1C)
01532     return DAG.getNode(ISD::SRA, VT, N0, N1);
01533   // fold (sra 0, x) -> 0
01534   if (N0C && N0C->isNullValue())
01535     return N0;
01536   // fold (sra -1, x) -> -1
01537   if (N0C && N0C->isAllOnesValue())
01538     return N0;
01539   // fold (sra x, c >= size(x)) -> undef
01540   if (N1C && N1C->getValue() >= MVT::getSizeInBits(VT))
01541     return DAG.getNode(ISD::UNDEF, VT);
01542   // fold (sra x, 0) -> x
01543   if (N1C && N1C->isNullValue())
01544     return N0;
01545   // fold (sra (shl x, c1), c1) -> sext_inreg for some c1 and target supports
01546   // sext_inreg.
01547   if (N1C && N0.getOpcode() == ISD::SHL && N1 == N0.getOperand(1)) {
01548     unsigned LowBits = MVT::getSizeInBits(VT) - (unsigned)N1C->getValue();
01549     MVT::ValueType EVT;
01550     switch (LowBits) {
01551     default: EVT = MVT::Other; break;
01552     case  1: EVT = MVT::i1;    break;
01553     case  8: EVT = MVT::i8;    break;
01554     case 16: EVT = MVT::i16;   break;
01555     case 32: EVT = MVT::i32;   break;
01556     }
01557     if (EVT > MVT::Other && TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, EVT))
01558       return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0),
01559                          DAG.getValueType(EVT));
01560   }
01561   
01562   // fold (sra (sra x, c1), c2) -> (sra x, c1+c2)
01563   if (N1C && N0.getOpcode() == ISD::SRA) {
01564     if (ConstantSDNode *C1 = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
01565       unsigned Sum = N1C->getValue() + C1->getValue();
01566       if (Sum >= MVT::getSizeInBits(VT)) Sum = MVT::getSizeInBits(VT)-1;
01567       return DAG.getNode(ISD::SRA, VT, N0.getOperand(0),
01568                          DAG.getConstant(Sum, N1C->getValueType(0)));
01569     }
01570   }
01571   
01572   // If the sign bit is known to be zero, switch this to a SRL.
01573   if (TLI.MaskedValueIsZero(N0, MVT::getIntVTSignBit(VT)))
01574     return DAG.getNode(ISD::SRL, VT, N0, N1);
01575   return SDOperand();
01576 }
01577 
01578 SDOperand DAGCombiner::visitSRL(SDNode *N) {
01579   SDOperand N0 = N->getOperand(0);
01580   SDOperand N1 = N->getOperand(1);
01581   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01582   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01583   MVT::ValueType VT = N0.getValueType();
01584   unsigned OpSizeInBits = MVT::getSizeInBits(VT);
01585   
01586   // fold (srl c1, c2) -> c1 >>u c2
01587   if (N0C && N1C)
01588     return DAG.getNode(ISD::SRL, VT, N0, N1);
01589   // fold (srl 0, x) -> 0
01590   if (N0C && N0C->isNullValue())
01591     return N0;
01592   // fold (srl x, c >= size(x)) -> undef
01593   if (N1C && N1C->getValue() >= OpSizeInBits)
01594     return DAG.getNode(ISD::UNDEF, VT);
01595   // fold (srl x, 0) -> x
01596   if (N1C && N1C->isNullValue())
01597     return N0;
01598   // if (srl x, c) is known to be zero, return 0
01599   if (N1C && TLI.MaskedValueIsZero(SDOperand(N, 0), ~0ULL >> (64-OpSizeInBits)))
01600     return DAG.getConstant(0, VT);
01601   // fold (srl (srl x, c1), c2) -> 0 or (srl x, c1+c2)
01602   if (N1C && N0.getOpcode() == ISD::SRL && 
01603       N0.getOperand(1).getOpcode() == ISD::Constant) {
01604     uint64_t c1 = cast<ConstantSDNode>(N0.getOperand(1))->getValue();
01605     uint64_t c2 = N1C->getValue();
01606     if (c1 + c2 > OpSizeInBits)
01607       return DAG.getConstant(0, VT);
01608     return DAG.getNode(ISD::SRL, VT, N0.getOperand(0), 
01609                        DAG.getConstant(c1 + c2, N1.getValueType()));
01610   }
01611   
01612   // fold (srl (ctlz x), "5") -> x  iff x has one bit set (the low bit).
01613   if (N1C && N0.getOpcode() == ISD::CTLZ && 
01614       N1C->getValue() == Log2_32(MVT::getSizeInBits(VT))) {
01615     uint64_t KnownZero, KnownOne, Mask = MVT::getIntVTBitMask(VT);
01616     TLI.ComputeMaskedBits(N0.getOperand(0), Mask, KnownZero, KnownOne);
01617     
01618     // If any of the input bits are KnownOne, then the input couldn't be all
01619     // zeros, thus the result of the srl will always be zero.
01620     if (KnownOne) return DAG.getConstant(0, VT);
01621     
01622     // If all of the bits input the to ctlz node are known to be zero, then
01623     // the result of the ctlz is "32" and the result of the shift is one.
01624     uint64_t UnknownBits = ~KnownZero & Mask;
01625     if (UnknownBits == 0) return DAG.getConstant(1, VT);
01626     
01627     // Otherwise, check to see if there is exactly one bit input to the ctlz.
01628     if ((UnknownBits & (UnknownBits-1)) == 0) {
01629       // Okay, we know that only that the single bit specified by UnknownBits
01630       // could be set on input to the CTLZ node.  If this bit is set, the SRL
01631       // will return 0, if it is clear, it returns 1.  Change the CTLZ/SRL pair
01632       // to an SRL,XOR pair, which is likely to simplify more.
01633       unsigned ShAmt = CountTrailingZeros_64(UnknownBits);
01634       SDOperand Op = N0.getOperand(0);
01635       if (ShAmt) {
01636         Op = DAG.getNode(ISD::SRL, VT, Op,
01637                          DAG.getConstant(ShAmt, TLI.getShiftAmountTy()));
01638         AddToWorkList(Op.Val);
01639       }
01640       return DAG.getNode(ISD::XOR, VT, Op, DAG.getConstant(1, VT));
01641     }
01642   }
01643   
01644   return SDOperand();
01645 }
01646 
01647 SDOperand DAGCombiner::visitCTLZ(SDNode *N) {
01648   SDOperand N0 = N->getOperand(0);
01649   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01650   MVT::ValueType VT = N->getValueType(0);
01651 
01652   // fold (ctlz c1) -> c2
01653   if (N0C)
01654     return DAG.getNode(ISD::CTLZ, VT, N0);
01655   return SDOperand();
01656 }
01657 
01658 SDOperand DAGCombiner::visitCTTZ(SDNode *N) {
01659   SDOperand N0 = N->getOperand(0);
01660   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01661   MVT::ValueType VT = N->getValueType(0);
01662   
01663   // fold (cttz c1) -> c2
01664   if (N0C)
01665     return DAG.getNode(ISD::CTTZ, VT, N0);
01666   return SDOperand();
01667 }
01668 
01669 SDOperand DAGCombiner::visitCTPOP(SDNode *N) {
01670   SDOperand N0 = N->getOperand(0);
01671   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01672   MVT::ValueType VT = N->getValueType(0);
01673   
01674   // fold (ctpop c1) -> c2
01675   if (N0C)
01676     return DAG.getNode(ISD::CTPOP, VT, N0);
01677   return SDOperand();
01678 }
01679 
01680 SDOperand DAGCombiner::visitSELECT(SDNode *N) {
01681   SDOperand N0 = N->getOperand(0);
01682   SDOperand N1 = N->getOperand(1);
01683   SDOperand N2 = N->getOperand(2);
01684   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01685   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01686   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
01687   MVT::ValueType VT = N->getValueType(0);
01688 
01689   // fold select C, X, X -> X
01690   if (N1 == N2)
01691     return N1;
01692   // fold select true, X, Y -> X
01693   if (N0C && !N0C->isNullValue())
01694     return N1;
01695   // fold select false, X, Y -> Y
01696   if (N0C && N0C->isNullValue())
01697     return N2;
01698   // fold select C, 1, X -> C | X
01699   if (MVT::i1 == VT && N1C && N1C->getValue() == 1)
01700     return DAG.getNode(ISD::OR, VT, N0, N2);
01701   // fold select C, 0, X -> ~C & X
01702   // FIXME: this should check for C type == X type, not i1?
01703   if (MVT::i1 == VT && N1C && N1C->isNullValue()) {
01704     SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
01705     AddToWorkList(XORNode.Val);
01706     return DAG.getNode(ISD::AND, VT, XORNode, N2);
01707   }
01708   // fold select C, X, 1 -> ~C | X
01709   if (MVT::i1 == VT && N2C && N2C->getValue() == 1) {
01710     SDOperand XORNode = DAG.getNode(ISD::XOR, VT, N0, DAG.getConstant(1, VT));
01711     AddToWorkList(XORNode.Val);
01712     return DAG.getNode(ISD::OR, VT, XORNode, N1);
01713   }
01714   // fold select C, X, 0 -> C & X
01715   // FIXME: this should check for C type == X type, not i1?
01716   if (MVT::i1 == VT && N2C && N2C->isNullValue())
01717     return DAG.getNode(ISD::AND, VT, N0, N1);
01718   // fold  X ? X : Y --> X ? 1 : Y --> X | Y
01719   if (MVT::i1 == VT && N0 == N1)
01720     return DAG.getNode(ISD::OR, VT, N0, N2);
01721   // fold X ? Y : X --> X ? Y : 0 --> X & Y
01722   if (MVT::i1 == VT && N0 == N2)
01723     return DAG.getNode(ISD::AND, VT, N0, N1);
01724   // If we can fold this based on the true/false value, do so.
01725   if (SimplifySelectOps(N, N1, N2))
01726     return SDOperand();
01727   // fold selects based on a setcc into other things, such as min/max/abs
01728   if (N0.getOpcode() == ISD::SETCC)
01729     // FIXME:
01730     // Check against MVT::Other for SELECT_CC, which is a workaround for targets
01731     // having to say they don't support SELECT_CC on every type the DAG knows
01732     // about, since there is no way to mark an opcode illegal at all value types
01733     if (TLI.isOperationLegal(ISD::SELECT_CC, MVT::Other))
01734       return DAG.getNode(ISD::SELECT_CC, VT, N0.getOperand(0), N0.getOperand(1),
01735                          N1, N2, N0.getOperand(2));
01736     else
01737       return SimplifySelect(N0, N1, N2);
01738   return SDOperand();
01739 }
01740 
01741 SDOperand DAGCombiner::visitSELECT_CC(SDNode *N) {
01742   SDOperand N0 = N->getOperand(0);
01743   SDOperand N1 = N->getOperand(1);
01744   SDOperand N2 = N->getOperand(2);
01745   SDOperand N3 = N->getOperand(3);
01746   SDOperand N4 = N->getOperand(4);
01747   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01748   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
01749   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2);
01750   ISD::CondCode CC = cast<CondCodeSDNode>(N4)->get();
01751   
01752   // Determine if the condition we're dealing with is constant
01753   SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
01754   ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
01755   
01756   // fold select_cc lhs, rhs, x, x, cc -> x
01757   if (N2 == N3)
01758     return N2;
01759   
01760   // If we can fold this based on the true/false value, do so.
01761   if (SimplifySelectOps(N, N2, N3))
01762     return SDOperand();
01763   
01764   // fold select_cc into other things, such as min/max/abs
01765   return SimplifySelectCC(N0, N1, N2, N3, CC);
01766 }
01767 
01768 SDOperand DAGCombiner::visitSETCC(SDNode *N) {
01769   return SimplifySetCC(N->getValueType(0), N->getOperand(0), N->getOperand(1),
01770                        cast<CondCodeSDNode>(N->getOperand(2))->get());
01771 }
01772 
01773 SDOperand DAGCombiner::visitSIGN_EXTEND(SDNode *N) {
01774   SDOperand N0 = N->getOperand(0);
01775   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01776   MVT::ValueType VT = N->getValueType(0);
01777 
01778   // fold (sext c1) -> c1
01779   if (N0C)
01780     return DAG.getNode(ISD::SIGN_EXTEND, VT, N0);
01781   // fold (sext (sext x)) -> (sext x)
01782   if (N0.getOpcode() == ISD::SIGN_EXTEND)
01783     return DAG.getNode(ISD::SIGN_EXTEND, VT, N0.getOperand(0));
01784   // fold (sext (truncate x)) -> (sextinreg x) iff x size == sext size.
01785   if (N0.getOpcode() == ISD::TRUNCATE && N0.getOperand(0).getValueType() == VT&&
01786       (!AfterLegalize || 
01787        TLI.isOperationLegal(ISD::SIGN_EXTEND_INREG, N0.getValueType())))
01788     return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0),
01789                        DAG.getValueType(N0.getValueType()));
01790   // fold (sext (load x)) -> (sext (truncate (sextload x)))
01791   if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() &&
01792       (!AfterLegalize||TLI.isOperationLegal(ISD::SEXTLOAD, N0.getValueType()))){
01793     SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0),
01794                                        N0.getOperand(1), N0.getOperand(2),
01795                                        N0.getValueType());
01796     CombineTo(N, ExtLoad);
01797     CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
01798               ExtLoad.getValue(1));
01799     return SDOperand();
01800   }
01801 
01802   // fold (sext (sextload x)) -> (sext (truncate (sextload x)))
01803   // fold (sext ( extload x)) -> (sext (truncate (sextload x)))
01804   if ((N0.getOpcode() == ISD::SEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) &&
01805       N0.hasOneUse()) {
01806     SDOperand ExtLoad = DAG.getNode(ISD::SEXTLOAD, VT, N0.getOperand(0),
01807                                     N0.getOperand(1), N0.getOperand(2),
01808                                     N0.getOperand(3));
01809     CombineTo(N, ExtLoad);
01810     CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
01811               ExtLoad.getValue(1));
01812     return SDOperand();
01813   }
01814   
01815   return SDOperand();
01816 }
01817 
01818 SDOperand DAGCombiner::visitZERO_EXTEND(SDNode *N) {
01819   SDOperand N0 = N->getOperand(0);
01820   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01821   MVT::ValueType VT = N->getValueType(0);
01822 
01823   // fold (zext c1) -> c1
01824   if (N0C)
01825     return DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
01826   // fold (zext (zext x)) -> (zext x)
01827   if (N0.getOpcode() == ISD::ZERO_EXTEND)
01828     return DAG.getNode(ISD::ZERO_EXTEND, VT, N0.getOperand(0));
01829   // fold (zext (truncate x)) -> (zextinreg x) iff x size == zext size.
01830   if (N0.getOpcode() == ISD::TRUNCATE && N0.getOperand(0).getValueType() == VT&&
01831       (!AfterLegalize || TLI.isOperationLegal(ISD::AND, N0.getValueType())))
01832     return DAG.getZeroExtendInReg(N0.getOperand(0), N0.getValueType());
01833   // fold (zext (load x)) -> (zext (truncate (zextload x)))
01834   if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse() &&
01835       (!AfterLegalize||TLI.isOperationLegal(ISD::ZEXTLOAD, N0.getValueType()))){
01836     SDOperand ExtLoad = DAG.getExtLoad(ISD::ZEXTLOAD, VT, N0.getOperand(0),
01837                                        N0.getOperand(1), N0.getOperand(2),
01838                                        N0.getValueType());
01839     CombineTo(N, ExtLoad);
01840     CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
01841               ExtLoad.getValue(1));
01842     return SDOperand();
01843   }
01844 
01845   // fold (zext (zextload x)) -> (zext (truncate (zextload x)))
01846   // fold (zext ( extload x)) -> (zext (truncate (zextload x)))
01847   if ((N0.getOpcode() == ISD::ZEXTLOAD || N0.getOpcode() == ISD::EXTLOAD) &&
01848       N0.hasOneUse()) {
01849     SDOperand ExtLoad = DAG.getNode(ISD::ZEXTLOAD, VT, N0.getOperand(0),
01850                                     N0.getOperand(1), N0.getOperand(2),
01851                                     N0.getOperand(3));
01852     CombineTo(N, ExtLoad);
01853     CombineTo(N0.Val, DAG.getNode(ISD::TRUNCATE, N0.getValueType(), ExtLoad),
01854               ExtLoad.getValue(1));
01855     return SDOperand();
01856   }
01857   return SDOperand();
01858 }
01859 
01860 SDOperand DAGCombiner::visitSIGN_EXTEND_INREG(SDNode *N) {
01861   SDOperand N0 = N->getOperand(0);
01862   SDOperand N1 = N->getOperand(1);
01863   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01864   MVT::ValueType VT = N->getValueType(0);
01865   MVT::ValueType EVT = cast<VTSDNode>(N1)->getVT();
01866   unsigned EVTBits = MVT::getSizeInBits(EVT);
01867   
01868   // fold (sext_in_reg c1) -> c1
01869   if (N0C) {
01870     SDOperand Truncate = DAG.getConstant(N0C->getValue(), EVT);
01871     return DAG.getNode(ISD::SIGN_EXTEND, VT, Truncate);
01872   }
01873   // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt1
01874   if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG && 
01875       cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) {
01876     return N0;
01877   }
01878   // fold (sext_in_reg (sext_in_reg x, VT2), VT1) -> (sext_in_reg x, minVT) pt2
01879   if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
01880       EVT < cast<VTSDNode>(N0.getOperand(1))->getVT()) {
01881     return DAG.getNode(ISD::SIGN_EXTEND_INREG, VT, N0.getOperand(0), N1);
01882   }
01883   // fold (sext_in_reg (assert_sext x)) -> (assert_sext x)
01884   if (N0.getOpcode() == ISD::AssertSext && 
01885       cast<VTSDNode>(N0.getOperand(1))->getVT() <= EVT) {
01886     return N0;
01887   }
01888   // fold (sext_in_reg (sextload x)) -> (sextload x)
01889   if (N0.getOpcode() == ISD::SEXTLOAD && 
01890       cast<VTSDNode>(N0.getOperand(3))->getVT() <= EVT) {
01891     return N0;
01892   }
01893   // fold (sext_in_reg (setcc x)) -> setcc x iff (setcc x) == 0 or -1
01894   if (N0.getOpcode() == ISD::SETCC &&
01895       TLI.getSetCCResultContents() == 
01896         TargetLowering::ZeroOrNegativeOneSetCCResult)
01897     return N0;
01898   // fold (sext_in_reg x) -> (zext_in_reg x) if the sign bit is zero
01899   if (TLI.MaskedValueIsZero(N0, 1ULL << (EVTBits-1)))
01900     return DAG.getZeroExtendInReg(N0, EVT);
01901   // fold (sext_in_reg (srl x)) -> sra x
01902   if (N0.getOpcode() == ISD::SRL && 
01903       N0.getOperand(1).getOpcode() == ISD::Constant &&
01904       cast<ConstantSDNode>(N0.getOperand(1))->getValue() == EVTBits) {
01905     return DAG.getNode(ISD::SRA, N0.getValueType(), N0.getOperand(0), 
01906                        N0.getOperand(1));
01907   }
01908   // fold (sext_inreg (extload x)) -> (sextload x)
01909   if (N0.getOpcode() == ISD::EXTLOAD && 
01910       EVT == cast<VTSDNode>(N0.getOperand(3))->getVT() &&
01911       (!AfterLegalize || TLI.isOperationLegal(ISD::SEXTLOAD, EVT))) {
01912     SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0),
01913                                        N0.getOperand(1), N0.getOperand(2),
01914                                        EVT);
01915     CombineTo(N, ExtLoad);
01916     CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
01917     return SDOperand();
01918   }
01919   // fold (sext_inreg (zextload x)) -> (sextload x) iff load has one use
01920   if (N0.getOpcode() == ISD::ZEXTLOAD && N0.hasOneUse() &&
01921       EVT == cast<VTSDNode>(N0.getOperand(3))->getVT() &&
01922       (!AfterLegalize || TLI.isOperationLegal(ISD::SEXTLOAD, EVT))) {
01923     SDOperand ExtLoad = DAG.getExtLoad(ISD::SEXTLOAD, VT, N0.getOperand(0),
01924                                        N0.getOperand(1), N0.getOperand(2),
01925                                        EVT);
01926     CombineTo(N, ExtLoad);
01927     CombineTo(N0.Val, ExtLoad, ExtLoad.getValue(1));
01928     return SDOperand();
01929   }
01930   return SDOperand();
01931 }
01932 
01933 SDOperand DAGCombiner::visitTRUNCATE(SDNode *N) {
01934   SDOperand N0 = N->getOperand(0);
01935   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
01936   MVT::ValueType VT = N->getValueType(0);
01937 
01938   // noop truncate
01939   if (N0.getValueType() == N->getValueType(0))
01940     return N0;
01941   // fold (truncate c1) -> c1
01942   if (N0C)
01943     return DAG.getNode(ISD::TRUNCATE, VT, N0);
01944   // fold (truncate (truncate x)) -> (truncate x)
01945   if (N0.getOpcode() == ISD::TRUNCATE)
01946     return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
01947   // fold (truncate (ext x)) -> (ext x) or (truncate x) or x
01948   if (N0.getOpcode() == ISD::ZERO_EXTEND || N0.getOpcode() == ISD::SIGN_EXTEND){
01949     if (N0.getValueType() < VT)
01950       // if the source is smaller than the dest, we still need an extend
01951       return DAG.getNode(N0.getOpcode(), VT, N0.getOperand(0));
01952     else if (N0.getValueType() > VT)
01953       // if the source is larger than the dest, than we just need the truncate
01954       return DAG.getNode(ISD::TRUNCATE, VT, N0.getOperand(0));
01955     else
01956       // if the source and dest are the same type, we can drop both the extend
01957       // and the truncate
01958       return N0.getOperand(0);
01959   }
01960   // fold (truncate (load x)) -> (smaller load x)
01961   if (N0.getOpcode() == ISD::LOAD && N0.hasOneUse()) {
01962     assert(MVT::getSizeInBits(N0.getValueType()) > MVT::getSizeInBits(VT) &&
01963            "Cannot truncate to larger type!");
01964     MVT::ValueType PtrType = N0.getOperand(1).getValueType();
01965     // For big endian targets, we need to add an offset to the pointer to load
01966     // the correct bytes.  For little endian systems, we merely need to read
01967     // fewer bytes from the same pointer.
01968     uint64_t PtrOff = 
01969       (MVT::getSizeInBits(N0.getValueType()) - MVT::getSizeInBits(VT)) / 8;
01970     SDOperand NewPtr = TLI.isLittleEndian() ? N0.getOperand(1) : 
01971       DAG.getNode(ISD::ADD, PtrType, N0.getOperand(1),
01972                   DAG.getConstant(PtrOff, PtrType));
01973     AddToWorkList(NewPtr.Val);
01974     SDOperand Load = DAG.getLoad(VT, N0.getOperand(0), NewPtr,N0.getOperand(2));
01975     AddToWorkList(N);
01976     CombineTo(N0.Val, Load, Load.getValue(1));
01977     return SDOperand();
01978   }
01979   return SDOperand();
01980 }
01981 
01982 SDOperand DAGCombiner::visitBIT_CONVERT(SDNode *N) {
01983   SDOperand N0 = N->getOperand(0);
01984   MVT::ValueType VT = N->getValueType(0);
01985 
01986   // If the input is a constant, let getNode() fold it.
01987   if (isa<ConstantSDNode>(N0) || isa<ConstantFPSDNode>(N0)) {
01988     SDOperand Res = DAG.getNode(ISD::BIT_CONVERT, VT, N0);
01989     if (Res.Val != N) return Res;
01990   }
01991   
01992   if (N0.getOpcode() == ISD::BIT_CONVERT)  // conv(conv(x,t1),t2) -> conv(x,t2)
01993     return DAG.getNode(ISD::BIT_CONVERT, VT, N0.getOperand(0));
01994 
01995   // fold (conv (load x)) -> (load (conv*)x)
01996   // FIXME: These xforms need to know that the resultant load doesn't need a 
01997   // higher alignment than the original!
01998   if (0 && N0.getOpcode() == ISD::LOAD && N0.hasOneUse()) {
01999     SDOperand Load = DAG.getLoad(VT, N0.getOperand(0), N0.getOperand(1),
02000                                  N0.getOperand(2));
02001     AddToWorkList(N);
02002     CombineTo(N0.Val, DAG.getNode(ISD::BIT_CONVERT, N0.getValueType(), Load),
02003               Load.getValue(1));
02004     return Load;
02005   }
02006   
02007   return SDOperand();
02008 }
02009 
02010 SDOperand DAGCombiner::visitVBIT_CONVERT(SDNode *N) {
02011   SDOperand N0 = N->getOperand(0);
02012   MVT::ValueType VT = N->getValueType(0);
02013 
02014   // If the input is a VBUILD_VECTOR with all constant elements, fold this now.
02015   // First check to see if this is all constant.
02016   if (N0.getOpcode() == ISD::VBUILD_VECTOR && N0.Val->hasOneUse() &&
02017       VT == MVT::Vector) {
02018     bool isSimple = true;
02019     for (unsigned i = 0, e = N0.getNumOperands()-2; i != e; ++i)
02020       if (N0.getOperand(i).getOpcode() != ISD::UNDEF &&
02021           N0.getOperand(i).getOpcode() != ISD::Constant &&
02022           N0.getOperand(i).getOpcode() != ISD::ConstantFP) {
02023         isSimple = false; 
02024         break;
02025       }
02026         
02027     MVT::ValueType DestEltVT = cast<VTSDNode>(N->getOperand(2))->getVT();
02028     if (isSimple && !MVT::isVector(DestEltVT)) {
02029       return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(N0.Val, DestEltVT);
02030     }
02031   }
02032   
02033   return SDOperand();
02034 }
02035 
02036 /// ConstantFoldVBIT_CONVERTofVBUILD_VECTOR - We know that BV is a vbuild_vector
02037 /// node with Constant, ConstantFP or Undef operands.  DstEltVT indicates the 
02038 /// destination element value type.
02039 SDOperand DAGCombiner::
02040 ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(SDNode *BV, MVT::ValueType DstEltVT) {
02041   MVT::ValueType SrcEltVT = BV->getOperand(0).getValueType();
02042   
02043   // If this is already the right type, we're done.
02044   if (SrcEltVT == DstEltVT) return SDOperand(BV, 0);
02045   
02046   unsigned SrcBitSize = MVT::getSizeInBits(SrcEltVT);
02047   unsigned DstBitSize = MVT::getSizeInBits(DstEltVT);
02048   
02049   // If this is a conversion of N elements of one type to N elements of another
02050   // type, convert each element.  This handles FP<->INT cases.
02051   if (SrcBitSize == DstBitSize) {
02052     std::vector<SDOperand> Ops;
02053     for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) {
02054       Ops.push_back(DAG.getNode(ISD::BIT_CONVERT, DstEltVT, BV->getOperand(i)));
02055       AddToWorkList(Ops.back().Val);
02056     }
02057     Ops.push_back(*(BV->op_end()-2)); // Add num elements.
02058     Ops.push_back(DAG.getValueType(DstEltVT));
02059     return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops);
02060   }
02061   
02062   // Otherwise, we're growing or shrinking the elements.  To avoid having to
02063   // handle annoying details of growing/shrinking FP values, we convert them to
02064   // int first.
02065   if (MVT::isFloatingPoint(SrcEltVT)) {
02066     // Convert the input float vector to a int vector where the elements are the
02067     // same sizes.
02068     assert((SrcEltVT == MVT::f32 || SrcEltVT == MVT::f64) && "Unknown FP VT!");
02069     MVT::ValueType IntVT = SrcEltVT == MVT::f32 ? MVT::i32 : MVT::i64;
02070     BV = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, IntVT).Val;
02071     SrcEltVT = IntVT;
02072   }
02073   
02074   // Now we know the input is an integer vector.  If the output is a FP type,
02075   // convert to integer first, then to FP of the right size.
02076   if (MVT::isFloatingPoint(DstEltVT)) {
02077     assert((DstEltVT == MVT::f32 || DstEltVT == MVT::f64) && "Unknown FP VT!");
02078     MVT::ValueType TmpVT = DstEltVT == MVT::f32 ? MVT::i32 : MVT::i64;
02079     SDNode *Tmp = ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(BV, TmpVT).Val;
02080     
02081     // Next, convert to FP elements of the same size.
02082     return ConstantFoldVBIT_CONVERTofVBUILD_VECTOR(Tmp, DstEltVT);
02083   }
02084   
02085   // Okay, we know the src/dst types are both integers of differing types.
02086   // Handling growing first.
02087   assert(MVT::isInteger(SrcEltVT) && MVT::isInteger(DstEltVT));
02088   if (SrcBitSize < DstBitSize) {
02089     unsigned NumInputsPerOutput = DstBitSize/SrcBitSize;
02090     
02091     std::vector<SDOperand> Ops;
02092     for (unsigned i = 0, e = BV->getNumOperands()-2; i != e;
02093          i += NumInputsPerOutput) {
02094       bool isLE = TLI.isLittleEndian();
02095       uint64_t NewBits = 0;
02096       bool EltIsUndef = true;
02097       for (unsigned j = 0; j != NumInputsPerOutput; ++j) {
02098         // Shift the previously computed bits over.
02099         NewBits <<= SrcBitSize;
02100         SDOperand Op = BV->getOperand(i+ (isLE ? (NumInputsPerOutput-j-1) : j));
02101         if (Op.getOpcode() == ISD::UNDEF) continue;
02102         EltIsUndef = false;
02103         
02104         NewBits |= cast<ConstantSDNode>(Op)->getValue();
02105       }
02106       
02107       if (EltIsUndef)
02108         Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT));
02109       else
02110         Ops.push_back(DAG.getConstant(NewBits, DstEltVT));
02111     }
02112 
02113     Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements.
02114     Ops.push_back(DAG.getValueType(DstEltVT));            // Add element size.
02115     return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops);
02116   }
02117   
02118   // Finally, this must be the case where we are shrinking elements: each input
02119   // turns into multiple outputs.
02120   unsigned NumOutputsPerInput = SrcBitSize/DstBitSize;
02121   std::vector<SDOperand> Ops;
02122   for (unsigned i = 0, e = BV->getNumOperands()-2; i != e; ++i) {
02123     if (BV->getOperand(i).getOpcode() == ISD::UNDEF) {
02124       for (unsigned j = 0; j != NumOutputsPerInput; ++j)
02125         Ops.push_back(DAG.getNode(ISD::UNDEF, DstEltVT));
02126       continue;
02127     }
02128     uint64_t OpVal = cast<ConstantSDNode>(BV->getOperand(i))->getValue();
02129 
02130     for (unsigned j = 0; j != NumOutputsPerInput; ++j) {
02131       unsigned ThisVal = OpVal & ((1ULL << DstBitSize)-1);
02132       OpVal >>= DstBitSize;
02133       Ops.push_back(DAG.getConstant(ThisVal, DstEltVT));
02134     }
02135 
02136     // For big endian targets, swap the order of the pieces of each element.
02137     if (!TLI.isLittleEndian())
02138       std::reverse(Ops.end()-NumOutputsPerInput, Ops.end());
02139   }
02140   Ops.push_back(DAG.getConstant(Ops.size(), MVT::i32)); // Add num elements.
02141   Ops.push_back(DAG.getValueType(DstEltVT));            // Add element size.
02142   return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops);
02143 }
02144 
02145 
02146 
02147 SDOperand DAGCombiner::visitFADD(SDNode *N) {
02148   SDOperand N0 = N->getOperand(0);
02149   SDOperand N1 = N->getOperand(1);
02150   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02151   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
02152   MVT::ValueType VT = N->getValueType(0);
02153   
02154   // fold (fadd c1, c2) -> c1+c2
02155   if (N0CFP && N1CFP)
02156     return DAG.getNode(ISD::FADD, VT, N0, N1);
02157   // canonicalize constant to RHS
02158   if (N0CFP && !N1CFP)
02159     return DAG.getNode(ISD::FADD, VT, N1, N0);
02160   // fold (A + (-B)) -> A-B
02161   if (N1.getOpcode() == ISD::FNEG)
02162     return DAG.getNode(ISD::FSUB, VT, N0, N1.getOperand(0));
02163   // fold ((-A) + B) -> B-A
02164   if (N0.getOpcode() == ISD::FNEG)
02165     return DAG.getNode(ISD::FSUB, VT, N1, N0.getOperand(0));
02166   return SDOperand();
02167 }
02168 
02169 SDOperand DAGCombiner::visitFSUB(SDNode *N) {
02170   SDOperand N0 = N->getOperand(0);
02171   SDOperand N1 = N->getOperand(1);
02172   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02173   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
02174   MVT::ValueType VT = N->getValueType(0);
02175   
02176   // fold (fsub c1, c2) -> c1-c2
02177   if (N0CFP && N1CFP)
02178     return DAG.getNode(ISD::FSUB, VT, N0, N1);
02179   // fold (A-(-B)) -> A+B
02180   if (N1.getOpcode() == ISD::FNEG)
02181     return DAG.getNode(ISD::FADD, VT, N0, N1.getOperand(0));
02182   return SDOperand();
02183 }
02184 
02185 SDOperand DAGCombiner::visitFMUL(SDNode *N) {
02186   SDOperand N0 = N->getOperand(0);
02187   SDOperand N1 = N->getOperand(1);
02188   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02189   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
02190   MVT::ValueType VT = N->getValueType(0);
02191 
02192   // fold (fmul c1, c2) -> c1*c2
02193   if (N0CFP && N1CFP)
02194     return DAG.getNode(ISD::FMUL, VT, N0, N1);
02195   // canonicalize constant to RHS
02196   if (N0CFP && !N1CFP)
02197     return DAG.getNode(ISD::FMUL, VT, N1, N0);
02198   // fold (fmul X, 2.0) -> (fadd X, X)
02199   if (N1CFP && N1CFP->isExactlyValue(+2.0))
02200     return DAG.getNode(ISD::FADD, VT, N0, N0);
02201   return SDOperand();
02202 }
02203 
02204 SDOperand DAGCombiner::visitFDIV(SDNode *N) {
02205   SDOperand N0 = N->getOperand(0);
02206   SDOperand N1 = N->getOperand(1);
02207   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02208   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
02209   MVT::ValueType VT = N->getValueType(0);
02210 
02211   // fold (fdiv c1, c2) -> c1/c2
02212   if (N0CFP && N1CFP)
02213     return DAG.getNode(ISD::FDIV, VT, N0, N1);
02214   return SDOperand();
02215 }
02216 
02217 SDOperand DAGCombiner::visitFREM(SDNode *N) {
02218   SDOperand N0 = N->getOperand(0);
02219   SDOperand N1 = N->getOperand(1);
02220   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02221   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
02222   MVT::ValueType VT = N->getValueType(0);
02223 
02224   // fold (frem c1, c2) -> fmod(c1,c2)
02225   if (N0CFP && N1CFP)
02226     return DAG.getNode(ISD::FREM, VT, N0, N1);
02227   return SDOperand();
02228 }
02229 
02230 SDOperand DAGCombiner::visitFCOPYSIGN(SDNode *N) {
02231   SDOperand N0 = N->getOperand(0);
02232   SDOperand N1 = N->getOperand(1);
02233   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02234   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1);
02235   MVT::ValueType VT = N->getValueType(0);
02236 
02237   if (N0CFP && N1CFP)  // Constant fold
02238     return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1);
02239   
02240   if (N1CFP) {
02241     // copysign(x, c1) -> fabs(x)       iff ispos(c1)
02242     // copysign(x, c1) -> fneg(fabs(x)) iff isneg(c1)
02243     union {
02244       double d;
02245       int64_t i;
02246     } u;
02247     u.d = N1CFP->getValue();
02248     if (u.i >= 0)
02249       return DAG.getNode(ISD::FABS, VT, N0);
02250     else
02251       return DAG.getNode(ISD::FNEG, VT, DAG.getNode(ISD::FABS, VT, N0));
02252   }
02253   
02254   // copysign(fabs(x), y) -> copysign(x, y)
02255   // copysign(fneg(x), y) -> copysign(x, y)
02256   // copysign(copysign(x,z), y) -> copysign(x, y)
02257   if (N0.getOpcode() == ISD::FABS || N0.getOpcode() == ISD::FNEG ||
02258       N0.getOpcode() == ISD::FCOPYSIGN)
02259     return DAG.getNode(ISD::FCOPYSIGN, VT, N0.getOperand(0), N1);
02260 
02261   // copysign(x, abs(y)) -> abs(x)
02262   if (N1.getOpcode() == ISD::FABS)
02263     return DAG.getNode(ISD::FABS, VT, N0);
02264   
02265   // copysign(x, copysign(y,z)) -> copysign(x, z)
02266   if (N1.getOpcode() == ISD::FCOPYSIGN)
02267     return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(1));
02268   
02269   // copysign(x, fp_extend(y)) -> copysign(x, y)
02270   // copysign(x, fp_round(y)) -> copysign(x, y)
02271   if (N1.getOpcode() == ISD::FP_EXTEND || N1.getOpcode() == ISD::FP_ROUND)
02272     return DAG.getNode(ISD::FCOPYSIGN, VT, N0, N1.getOperand(0));
02273   
02274   return SDOperand();
02275 }
02276 
02277 
02278 
02279 SDOperand DAGCombiner::visitSINT_TO_FP(SDNode *N) {
02280   SDOperand N0 = N->getOperand(0);
02281   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
02282   MVT::ValueType VT = N->getValueType(0);
02283   
02284   // fold (sint_to_fp c1) -> c1fp
02285   if (N0C)
02286     return DAG.getNode(ISD::SINT_TO_FP, VT, N0);
02287   return SDOperand();
02288 }
02289 
02290 SDOperand DAGCombiner::visitUINT_TO_FP(SDNode *N) {
02291   SDOperand N0 = N->getOperand(0);
02292   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0);
02293   MVT::ValueType VT = N->getValueType(0);
02294 
02295   // fold (uint_to_fp c1) -> c1fp
02296   if (N0C)
02297     return DAG.getNode(ISD::UINT_TO_FP, VT, N0);
02298   return SDOperand();
02299 }
02300 
02301 SDOperand DAGCombiner::visitFP_TO_SINT(SDNode *N) {
02302   SDOperand N0 = N->getOperand(0);
02303   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02304   MVT::ValueType VT = N->getValueType(0);
02305   
02306   // fold (fp_to_sint c1fp) -> c1
02307   if (N0CFP)
02308     return DAG.getNode(ISD::FP_TO_SINT, VT, N0);
02309   return SDOperand();
02310 }
02311 
02312 SDOperand DAGCombiner::visitFP_TO_UINT(SDNode *N) {
02313   SDOperand N0 = N->getOperand(0);
02314   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02315   MVT::ValueType VT = N->getValueType(0);
02316   
02317   // fold (fp_to_uint c1fp) -> c1
02318   if (N0CFP)
02319     return DAG.getNode(ISD::FP_TO_UINT, VT, N0);
02320   return SDOperand();
02321 }
02322 
02323 SDOperand DAGCombiner::visitFP_ROUND(SDNode *N) {
02324   SDOperand N0 = N->getOperand(0);
02325   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02326   MVT::ValueType VT = N->getValueType(0);
02327   
02328   // fold (fp_round c1fp) -> c1fp
02329   if (N0CFP)
02330     return DAG.getNode(ISD::FP_ROUND, VT, N0);
02331   
02332   // fold (fp_round (fp_extend x)) -> x
02333   if (N0.getOpcode() == ISD::FP_EXTEND && VT == N0.getOperand(0).getValueType())
02334     return N0.getOperand(0);
02335   
02336   // fold (fp_round (copysign X, Y)) -> (copysign (fp_round X), Y)
02337   if (N0.getOpcode() == ISD::FCOPYSIGN && N0.Val->hasOneUse()) {
02338     SDOperand Tmp = DAG.getNode(ISD::FP_ROUND, VT, N0.getOperand(0));
02339     AddToWorkList(Tmp.Val);
02340     return DAG.getNode(ISD::FCOPYSIGN, VT, Tmp, N0.getOperand(1));
02341   }
02342   
02343   return SDOperand();
02344 }
02345 
02346 SDOperand DAGCombiner::visitFP_ROUND_INREG(SDNode *N) {
02347   SDOperand N0 = N->getOperand(0);
02348   MVT::ValueType VT = N->getValueType(0);
02349   MVT::ValueType EVT = cast<VTSDNode>(N->getOperand(1))->getVT();
02350   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02351   
02352   // fold (fp_round_inreg c1fp) -> c1fp
02353   if (N0CFP) {
02354     SDOperand Round = DAG.getConstantFP(N0CFP->getValue(), EVT);
02355     return DAG.getNode(ISD::FP_EXTEND, VT, Round);
02356   }
02357   return SDOperand();
02358 }
02359 
02360 SDOperand DAGCombiner::visitFP_EXTEND(SDNode *N) {
02361   SDOperand N0 = N->getOperand(0);
02362   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02363   MVT::ValueType VT = N->getValueType(0);
02364   
02365   // fold (fp_extend c1fp) -> c1fp
02366   if (N0CFP)
02367     return DAG.getNode(ISD::FP_EXTEND, VT, N0);
02368   return SDOperand();
02369 }
02370 
02371 SDOperand DAGCombiner::visitFNEG(SDNode *N) {
02372   SDOperand N0 = N->getOperand(0);
02373   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02374   MVT::ValueType VT = N->getValueType(0);
02375 
02376   // fold (fneg c1) -> -c1
02377   if (N0CFP)
02378     return DAG.getNode(ISD::FNEG, VT, N0);
02379   // fold (fneg (sub x, y)) -> (sub y, x)
02380   if (N0.getOpcode() == ISD::SUB)
02381     return DAG.getNode(ISD::SUB, VT, N0.getOperand(1), N0.getOperand(0));
02382   // fold (fneg (fneg x)) -> x
02383   if (N0.getOpcode() == ISD::FNEG)
02384     return N0.getOperand(0);
02385   return SDOperand();
02386 }
02387 
02388 SDOperand DAGCombiner::visitFABS(SDNode *N) {
02389   SDOperand N0 = N->getOperand(0);
02390   ConstantFPSDNode *N0CFP = dyn_cast<ConstantFPSDNode>(N0);
02391   MVT::ValueType VT = N->getValueType(0);
02392   
02393   // fold (fabs c1) -> fabs(c1)
02394   if (N0CFP)
02395     return DAG.getNode(ISD::FABS, VT, N0);
02396   // fold (fabs (fabs x)) -> (fabs x)
02397   if (N0.getOpcode() == ISD::FABS)
02398     return N->getOperand(0);
02399   // fold (fabs (fneg x)) -> (fabs x)
02400   // fold (fabs (fcopysign x, y)) -> (fabs x)
02401   if (N0.getOpcode() == ISD::FNEG || N0.getOpcode() == ISD::FCOPYSIGN)
02402     return DAG.getNode(ISD::FABS, VT, N0.getOperand(0));
02403   
02404   return SDOperand();
02405 }
02406 
02407 SDOperand DAGCombiner::visitBRCOND(SDNode *N) {
02408   SDOperand Chain = N->getOperand(0);
02409   SDOperand N1 = N->getOperand(1);
02410   SDOperand N2 = N->getOperand(2);
02411   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1);
02412   
02413   // never taken branch, fold to chain
02414   if (N1C && N1C->isNullValue())
02415     return Chain;
02416   // unconditional branch
02417   if (N1C && N1C->getValue() == 1)
02418     return DAG.getNode(ISD::BR, MVT::Other, Chain, N2);
02419   // fold a brcond with a setcc condition into a BR_CC node if BR_CC is legal
02420   // on the target.
02421   if (N1.getOpcode() == ISD::SETCC && 
02422       TLI.isOperationLegal(ISD::BR_CC, MVT::Other)) {
02423     return DAG.getNode(ISD::BR_CC, MVT::Other, Chain, N1.getOperand(2),
02424                        N1.getOperand(0), N1.getOperand(1), N2);
02425   }
02426   return SDOperand();
02427 }
02428 
02429 // Operand List for BR_CC: Chain, CondCC, CondLHS, CondRHS, DestBB.
02430 //
02431 SDOperand DAGCombiner::visitBR_CC(SDNode *N) {
02432   CondCodeSDNode *CC = cast<CondCodeSDNode>(N->getOperand(1));
02433   SDOperand CondLHS = N->getOperand(2), CondRHS = N->getOperand(3);
02434   
02435   // Use SimplifySetCC  to simplify SETCC's.
02436   SDOperand Simp = SimplifySetCC(MVT::i1, CondLHS, CondRHS, CC->get(), false);
02437   ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(Simp.Val);
02438 
02439   // fold br_cc true, dest -> br dest (unconditional branch)
02440   if (SCCC && SCCC->getValue())
02441     return DAG.getNode(ISD::BR, MVT::Other, N->getOperand(0),
02442                        N->getOperand(4));
02443   // fold br_cc false, dest -> unconditional fall through
02444   if (SCCC && SCCC->isNullValue())
02445     return N->getOperand(0);
02446   // fold to a simpler setcc
02447   if (Simp.Val && Simp.getOpcode() == ISD::SETCC)
02448     return DAG.getNode(ISD::BR_CC, MVT::Other, N->getOperand(0), 
02449                        Simp.getOperand(2), Simp.getOperand(0),
02450                        Simp.getOperand(1), N->getOperand(4));
02451   return SDOperand();
02452 }
02453 
02454 SDOperand DAGCombiner::visitLOAD(SDNode *N) {
02455   SDOperand Chain    = N->getOperand(0);
02456   SDOperand Ptr      = N->getOperand(1);
02457   SDOperand SrcValue = N->getOperand(2);
02458 
02459   // If there are no uses of the loaded value, change uses of the chain value
02460   // into uses of the chain input (i.e. delete the dead load).
02461   if (N->hasNUsesOfValue(0, 0))
02462     return CombineTo(N, DAG.getNode(ISD::UNDEF, N->getValueType(0)), Chain);
02463   
02464   // If this load is directly stored, replace the load value with the stored
02465   // value.
02466   // TODO: Handle store large -> read small portion.
02467   // TODO: Handle TRUNCSTORE/EXTLOAD
02468   if (Chain.getOpcode() == ISD::STORE && Chain.getOperand(2) == Ptr &&
02469       Chain.getOperand(1).getValueType() == N->getValueType(0))
02470     return CombineTo(N, Chain.getOperand(1), Chain);
02471   
02472   return SDOperand();
02473 }
02474 
02475 /// visitXEXTLOAD - Handle EXTLOAD/ZEXTLOAD/SEXTLOAD.
02476 SDOperand DAGCombiner::visitXEXTLOAD(SDNode *N) {
02477   SDOperand Chain    = N->getOperand(0);
02478   SDOperand Ptr      = N->getOperand(1);
02479   SDOperand SrcValue = N->getOperand(2);
02480   SDOperand EVT      = N->getOperand(3);
02481   
02482   // If there are no uses of the loaded value, change uses of the chain value
02483   // into uses of the chain input (i.e. delete the dead load).
02484   if (N->hasNUsesOfValue(0, 0))
02485     return CombineTo(N, DAG.getNode(ISD::UNDEF, N->getValueType(0)), Chain);
02486   
02487   return SDOperand();
02488 }
02489 
02490 SDOperand DAGCombiner::visitSTORE(SDNode *N) {
02491   SDOperand Chain    = N->getOperand(0);
02492   SDOperand Value    = N->getOperand(1);
02493   SDOperand Ptr      = N->getOperand(2);
02494   SDOperand SrcValue = N->getOperand(3);
02495  
02496   // If this is a store that kills a previous store, remove the previous store.
02497   if (Chain.getOpcode() == ISD::STORE && Chain.getOperand(2) == Ptr &&
02498       Chain.Val->hasOneUse() /* Avoid introducing DAG cycles */ &&
02499       // Make sure that these stores are the same value type:
02500       // FIXME: we really care that the second store is >= size of the first.
02501       Value.getValueType() == Chain.getOperand(1).getValueType()) {
02502     // Create a new store of Value that replaces both stores.
02503     SDNode *PrevStore = Chain.Val;
02504     if (PrevStore->getOperand(1) == Value) // Same value multiply stored.
02505       return Chain;
02506     SDOperand NewStore = DAG.getNode(ISD::STORE, MVT::Other,
02507                                      PrevStore->getOperand(0), Value, Ptr,
02508                                      SrcValue);
02509     CombineTo(N, NewStore);                 // Nuke this store.
02510     CombineTo(PrevStore, NewStore);  // Nuke the previous store.
02511     return SDOperand(N, 0);
02512   }
02513   
02514   // If this is a store of a bit convert, store the input value.
02515   // FIXME: This needs to know that the resultant store does not need a 
02516   // higher alignment than the original.
02517   if (0 && Value.getOpcode() == ISD::BIT_CONVERT)
02518     return DAG.getNode(ISD::STORE, MVT::Other, Chain, Value.getOperand(0),
02519                        Ptr, SrcValue);
02520   
02521   return SDOperand();
02522 }
02523 
02524 SDOperand DAGCombiner::visitINSERT_VECTOR_ELT(SDNode *N) {
02525   SDOperand InVec = N->getOperand(0);
02526   SDOperand InVal = N->getOperand(1);
02527   SDOperand EltNo = N->getOperand(2);
02528   
02529   // If the invec is a BUILD_VECTOR and if EltNo is a constant, build a new
02530   // vector with the inserted element.
02531   if (InVec.getOpcode() == ISD::BUILD_VECTOR && isa<ConstantSDNode>(EltNo)) {
02532     unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue();
02533     std::vector<SDOperand> Ops(InVec.Val->op_begin(), InVec.Val->op_end());
02534     if (Elt < Ops.size())
02535       Ops[Elt] = InVal;
02536     return DAG.getNode(ISD::BUILD_VECTOR, InVec.getValueType(), Ops);
02537   }
02538   
02539   return SDOperand();
02540 }
02541 
02542 SDOperand DAGCombiner::visitVINSERT_VECTOR_ELT(SDNode *N) {
02543   SDOperand InVec = N->getOperand(0);
02544   SDOperand InVal = N->getOperand(1);
02545   SDOperand EltNo = N->getOperand(2);
02546   SDOperand NumElts = N->getOperand(3);
02547   SDOperand EltType = N->getOperand(4);
02548   
02549   // If the invec is a VBUILD_VECTOR and if EltNo is a constant, build a new
02550   // vector with the inserted element.
02551   if (InVec.getOpcode() == ISD::VBUILD_VECTOR && isa<ConstantSDNode>(EltNo)) {
02552     unsigned Elt = cast<ConstantSDNode>(EltNo)->getValue();
02553     std::vector<SDOperand> Ops(InVec.Val->op_begin(), InVec.Val->op_end());
02554     if (Elt < Ops.size()-2)
02555       Ops[Elt] = InVal;
02556     return DAG.getNode(ISD::VBUILD_VECTOR, InVec.getValueType(), Ops);
02557   }
02558   
02559   return SDOperand();
02560 }
02561 
02562 SDOperand DAGCombiner::visitVBUILD_VECTOR(SDNode *N) {
02563   unsigned NumInScalars = N->getNumOperands()-2;
02564   SDOperand NumElts = N->getOperand(NumInScalars);
02565   SDOperand EltType = N->getOperand(NumInScalars+1);
02566 
02567   // Check to see if this is a VBUILD_VECTOR of a bunch of VEXTRACT_VECTOR_ELT
02568   // operations.  If so, and if the EXTRACT_ELT vector inputs come from at most
02569   // two distinct vectors, turn this into a shuffle node.
02570   SDOperand VecIn1, VecIn2;
02571   for (unsigned i = 0; i != NumInScalars; ++i) {
02572     // Ignore undef inputs.
02573     if (N->getOperand(i).getOpcode() == ISD::UNDEF) continue;
02574     
02575     // If this input is something other than a VEXTRACT_VECTOR_ELT with a
02576     // constant index, bail out.
02577     if (N->getOperand(i).getOpcode() != ISD::VEXTRACT_VECTOR_ELT ||
02578         !isa<ConstantSDNode>(N->getOperand(i).getOperand(1))) {
02579       VecIn1 = VecIn2 = SDOperand(0, 0);
02580       break;
02581     }
02582     
02583     // If the input vector type disagrees with the result of the vbuild_vector,
02584     // we can't make a shuffle.
02585     SDOperand ExtractedFromVec = N->getOperand(i).getOperand(0);
02586     if (*(ExtractedFromVec.Val->op_end()-2) != NumElts ||
02587         *(ExtractedFromVec.Val->op_end()-1) != EltType) {
02588       VecIn1 = VecIn2 = SDOperand(0, 0);
02589       break;
02590     }
02591     
02592     // Otherwise, remember this.  We allow up to two distinct input vectors.
02593     if (ExtractedFromVec == VecIn1 || ExtractedFromVec == VecIn2)
02594       continue;
02595     
02596     if (VecIn1.Val == 0) {
02597       VecIn1 = ExtractedFromVec;
02598     } else if (VecIn2.Val == 0) {
02599       VecIn2 = ExtractedFromVec;
02600     } else {
02601       // Too many inputs.
02602       VecIn1 = VecIn2 = SDOperand(0, 0);
02603       break;
02604     }
02605   }
02606   
02607   // If everything is good, we can make a shuffle operation.
02608   if (VecIn1.Val) {
02609     std::vector<SDOperand> BuildVecIndices;
02610     for (unsigned i = 0; i != NumInScalars; ++i) {
02611       if (N->getOperand(i).getOpcode() == ISD::UNDEF) {
02612         BuildVecIndices.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
02613         continue;
02614       }
02615       
02616       SDOperand Extract = N->getOperand(i);
02617       
02618       // If extracting from the first vector, just use the index directly.
02619       if (Extract.getOperand(0) == VecIn1) {
02620         BuildVecIndices.push_back(Extract.getOperand(1));
02621         continue;
02622       }
02623 
02624       // Otherwise, use InIdx + VecSize
02625       unsigned Idx = cast<ConstantSDNode>(Extract.getOperand(1))->getValue();
02626       BuildVecIndices.push_back(DAG.getConstant(Idx+NumInScalars, MVT::i32));
02627     }
02628     
02629     // Add count and size info.
02630     BuildVecIndices.push_back(NumElts);
02631     BuildVecIndices.push_back(DAG.getValueType(MVT::i32));
02632     
02633     // Return the new VVECTOR_SHUFFLE node.
02634     std::vector<SDOperand> Ops;
02635     Ops.push_back(VecIn1);
02636     if (VecIn2.Val) {
02637       Ops.push_back(VecIn2);
02638     } else {
02639        // Use an undef vbuild_vector as input for the second operand.
02640       std::vector<SDOperand> UnOps(NumInScalars,
02641                                    DAG.getNode(ISD::UNDEF, 
02642                                            cast<VTSDNode>(EltType)->getVT()));
02643       UnOps.push_back(NumElts);
02644       UnOps.push_back(EltType);
02645       Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, UnOps));
02646       AddToWorkList(Ops.back().Val);
02647     }
02648     Ops.push_back(DAG.getNode(ISD::VBUILD_VECTOR,MVT::Vector, BuildVecIndices));
02649     Ops.push_back(NumElts);
02650     Ops.push_back(EltType);
02651     return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, Ops);
02652   }
02653   
02654   return SDOperand();
02655 }
02656 
02657 SDOperand DAGCombiner::visitVECTOR_SHUFFLE(SDNode *N) {
02658   SDOperand ShufMask = N->getOperand(2);
02659   unsigned NumElts = ShufMask.getNumOperands();
02660 
02661   // If the shuffle mask is an identity operation on the LHS, return the LHS.
02662   bool isIdentity = true;
02663   for (unsigned i = 0; i != NumElts; ++i) {
02664     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
02665         cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) {
02666       isIdentity = false;
02667       break;
02668     }
02669   }
02670   if (isIdentity) return N->getOperand(0);
02671 
02672   // If the shuffle mask is an identity operation on the RHS, return the RHS.
02673   isIdentity = true;
02674   for (unsigned i = 0; i != NumElts; ++i) {
02675     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
02676         cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) {
02677       isIdentity = false;
02678       break;
02679     }
02680   }
02681   if (isIdentity) return N->getOperand(1);
02682   
02683   // If the LHS and the RHS are the same node, turn the RHS into an undef.
02684   if (N->getOperand(0) == N->getOperand(1)) {
02685     if (N->getOperand(0).getOpcode() == ISD::UNDEF)
02686       return DAG.getNode(ISD::UNDEF, N->getValueType(0));
02687     // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the
02688     // first operand.
02689     std::vector<SDOperand> MappedOps;
02690     for (unsigned i = 0, e = ShufMask.getNumOperands(); i != e; ++i) {
02691       if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF ||
02692           cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) {
02693         MappedOps.push_back(ShufMask.getOperand(i));
02694       } else {
02695         unsigned NewIdx = 
02696            cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts;
02697         MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32));
02698       }
02699     }
02700     ShufMask = DAG.getNode(ISD::BUILD_VECTOR, ShufMask.getValueType(),
02701                            MappedOps);
02702     AddToWorkList(ShufMask.Val);
02703     return DAG.getNode(ISD::VECTOR_SHUFFLE, N->getValueType(0),
02704                        N->getOperand(0), 
02705                        DAG.getNode(ISD::UNDEF, N->getValueType(0)),
02706                        ShufMask);
02707   }
02708  
02709   return SDOperand();
02710 }
02711 
02712 SDOperand DAGCombiner::visitVVECTOR_SHUFFLE(SDNode *N) {
02713   SDOperand ShufMask = N->getOperand(2);
02714   unsigned NumElts = ShufMask.getNumOperands()-2;
02715   
02716   // If the shuffle mask is an identity operation on the LHS, return the LHS.
02717   bool isIdentity = true;
02718   for (unsigned i = 0; i != NumElts; ++i) {
02719     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
02720         cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i) {
02721       isIdentity = false;
02722       break;
02723     }
02724   }
02725   if (isIdentity) return N->getOperand(0);
02726   
02727   // If the shuffle mask is an identity operation on the RHS, return the RHS.
02728   isIdentity = true;
02729   for (unsigned i = 0; i != NumElts; ++i) {
02730     if (ShufMask.getOperand(i).getOpcode() != ISD::UNDEF &&
02731         cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() != i+NumElts) {
02732       isIdentity = false;
02733       break;
02734     }
02735   }
02736   if (isIdentity) return N->getOperand(1);
02737 
02738   // If the LHS and the RHS are the same node, turn the RHS into an undef.
02739   if (N->getOperand(0) == N->getOperand(1)) {
02740     // Check the SHUFFLE mask, mapping any inputs from the 2nd operand into the
02741     // first operand.
02742     std::vector<SDOperand> MappedOps;
02743     for (unsigned i = 0; i != NumElts; ++i) {
02744       if (ShufMask.getOperand(i).getOpcode() == ISD::UNDEF ||
02745           cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() < NumElts) {
02746         MappedOps.push_back(ShufMask.getOperand(i));
02747       } else {
02748         unsigned NewIdx = 
02749           cast<ConstantSDNode>(ShufMask.getOperand(i))->getValue() - NumElts;
02750         MappedOps.push_back(DAG.getConstant(NewIdx, MVT::i32));
02751       }
02752     }
02753     // Add the type/#elts values.
02754     MappedOps.push_back(ShufMask.getOperand(NumElts));
02755     MappedOps.push_back(ShufMask.getOperand(NumElts+1));
02756 
02757     ShufMask = DAG.getNode(ISD::VBUILD_VECTOR, ShufMask.getValueType(),
02758                            MappedOps);
02759     AddToWorkList(ShufMask.Val);
02760     
02761     // Build the undef vector.
02762     SDOperand UDVal = DAG.getNode(ISD::UNDEF, MappedOps[0].getValueType());
02763     for (unsigned i = 0; i != NumElts; ++i)
02764       MappedOps[i] = UDVal;
02765     MappedOps[NumElts  ] = *(N->getOperand(0).Val->op_end()-2);
02766     MappedOps[NumElts+1] = *(N->getOperand(0).Val->op_end()-1);
02767     UDVal = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, MappedOps);
02768     
02769     return DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, 
02770                        N->getOperand(0), UDVal, ShufMask,
02771                        MappedOps[NumElts], MappedOps[NumElts+1]);
02772   }
02773   
02774   return SDOperand();
02775 }
02776 
02777 /// visitVBinOp - Visit a binary vector operation, like VADD.  IntOp indicates
02778 /// the scalar operation of the vop if it is operating on an integer vector
02779 /// (e.g. ADD) and FPOp indicates the FP version (e.g. FADD).
02780 SDOperand DAGCombiner::visitVBinOp(SDNode *N, ISD::NodeType IntOp, 
02781                                    ISD::NodeType FPOp) {
02782   MVT::ValueType EltType = cast<VTSDNode>(*(N->op_end()-1))->getVT();
02783   ISD::NodeType ScalarOp = MVT::isInteger(EltType) ? IntOp : FPOp;
02784   SDOperand LHS = N->getOperand(0);
02785   SDOperand RHS = N->getOperand(1);
02786   
02787   // If the LHS and RHS are VBUILD_VECTOR nodes, see if we can constant fold
02788   // this operation.
02789   if (LHS.getOpcode() == ISD::VBUILD_VECTOR && 
02790       RHS.getOpcode() == ISD::VBUILD_VECTOR) {
02791     std::vector<SDOperand> Ops;
02792     for (unsigned i = 0, e = LHS.getNumOperands()-2; i != e; ++i) {
02793       SDOperand LHSOp = LHS.getOperand(i);
02794       SDOperand RHSOp = RHS.getOperand(i);
02795       // If these two elements can't be folded, bail out.
02796       if ((LHSOp.getOpcode() != ISD::UNDEF &&
02797            LHSOp.getOpcode() != ISD::Constant &&
02798            LHSOp.getOpcode() != ISD::ConstantFP) ||
02799           (RHSOp.getOpcode() != ISD::UNDEF &&
02800            RHSOp.getOpcode() != ISD::Constant &&
02801            RHSOp.getOpcode() != ISD::ConstantFP))
02802         break;
02803       Ops.push_back(DAG.getNode(ScalarOp, EltType, LHSOp, RHSOp));
02804       AddToWorkList(Ops.back().Val);
02805       assert((Ops.back().getOpcode() == ISD::UNDEF ||
02806               Ops.back().getOpcode() == ISD::Constant ||
02807               Ops.back().getOpcode() == ISD::ConstantFP) &&
02808              "Scalar binop didn't fold!");
02809     }
02810     
02811     if (Ops.size() == LHS.getNumOperands()-2) {
02812       Ops.push_back(*(LHS.Val->op_end()-2));
02813       Ops.push_back(*(LHS.Val->op_end()-1));
02814       return DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops);
02815     }
02816   }
02817   
02818   return SDOperand();
02819 }
02820 
02821 SDOperand DAGCombiner::SimplifySelect(SDOperand N0, SDOperand N1, SDOperand N2){
02822   assert(N0.getOpcode() ==ISD::SETCC && "First argument must be a SetCC node!");
02823   
02824   SDOperand SCC = SimplifySelectCC(N0.getOperand(0), N0.getOperand(1), N1, N2,
02825                                  cast<CondCodeSDNode>(N0.getOperand(2))->get());
02826   // If we got a simplified select_cc node back from SimplifySelectCC, then
02827   // break it down into a new SETCC node, and a new SELECT node, and then return
02828   // the SELECT node, since we were called with a SELECT node.
02829   if (SCC.Val) {
02830     // Check to see if we got a select_cc back (to turn into setcc/select).
02831     // Otherwise, just return whatever node we got back, like fabs.
02832     if (SCC.getOpcode() == ISD::SELECT_CC) {
02833       SDOperand SETCC = DAG.getNode(ISD::SETCC, N0.getValueType(),
02834                                     SCC.getOperand(0), SCC.getOperand(1), 
02835                                     SCC.getOperand(4));
02836       AddToWorkList(SETCC.Val);
02837       return DAG.getNode(ISD::SELECT, SCC.getValueType(), SCC.getOperand(2),
02838                          SCC.getOperand(3), SETCC);
02839     }
02840     return SCC;
02841   }
02842   return SDOperand();
02843 }
02844 
02845 /// SimplifySelectOps - Given a SELECT or a SELECT_CC node, where LHS and RHS
02846 /// are the two values being selected between, see if we can simplify the
02847 /// select.
02848 ///
02849 bool DAGCombiner::SimplifySelectOps(SDNode *TheSelect, SDOperand LHS, 
02850                                     SDOperand RHS) {
02851   
02852   // If this is a select from two identical things, try to pull the operation
02853   // through the select.
02854   if (LHS.getOpcode() == RHS.getOpcode() && LHS.hasOneUse() && RHS.hasOneUse()){
02855 #if 0
02856     std::cerr << "SELECT: ["; LHS.Val->dump();
02857     std::cerr << "] ["; RHS.Val->dump();
02858     std::cerr << "]\n";
02859 #endif
02860     
02861     // If this is a load and the token chain is identical, replace the select
02862     // of two loads with a load through a select of the address to load from.
02863     // This triggers in things like "select bool X, 10.0, 123.0" after the FP
02864     // constants have been dropped into the constant pool.
02865     if ((LHS.getOpcode() == ISD::LOAD ||
02866          LHS.getOpcode() == ISD::EXTLOAD ||
02867          LHS.getOpcode() == ISD::ZEXTLOAD ||
02868          LHS.getOpcode() == ISD::SEXTLOAD) &&
02869         // Token chains must be identical.
02870         LHS.getOperand(0) == RHS.getOperand(0) &&
02871         // If this is an EXTLOAD, the VT's must match.
02872         (LHS.getOpcode() == ISD::LOAD ||
02873          LHS.getOperand(3) == RHS.getOperand(3))) {
02874       // FIXME: this conflates two src values, discarding one.  This is not
02875       // the right thing to do, but nothing uses srcvalues now.  When they do,
02876       // turn SrcValue into a list of locations.
02877       SDOperand Addr;
02878       if (TheSelect->getOpcode() == ISD::SELECT)
02879         Addr = DAG.getNode(ISD::SELECT, LHS.getOperand(1).getValueType(),
02880                            TheSelect->getOperand(0), LHS.getOperand(1),
02881                            RHS.getOperand(1));
02882       else
02883         Addr = DAG.getNode(ISD::SELECT_CC, LHS.getOperand(1).getValueType(),
02884                            TheSelect->getOperand(0),
02885                            TheSelect->getOperand(1), 
02886                            LHS.getOperand(1), RHS.getOperand(1),
02887                            TheSelect->getOperand(4));
02888       
02889       SDOperand Load;
02890       if (LHS.getOpcode() == ISD::LOAD)
02891         Load = DAG.getLoad(TheSelect->getValueType(0), LHS.getOperand(0),
02892                            Addr, LHS.getOperand(2));
02893       else
02894         Load = DAG.getExtLoad(LHS.getOpcode(), TheSelect->getValueType(0),
02895                               LHS.getOperand(0), Addr, LHS.getOperand(2),
02896                               cast<VTSDNode>(LHS.getOperand(3))->getVT());
02897       // Users of the select now use the result of the load.
02898       CombineTo(TheSelect, Load);
02899       
02900       // Users of the old loads now use the new load's chain.  We know the
02901       // old-load value is dead now.
02902       CombineTo(LHS.Val, Load.getValue(0), Load.getValue(1));
02903       CombineTo(RHS.Val, Load.getValue(0), Load.getValue(1));
02904       return true;
02905     }
02906   }
02907   
02908   return false;
02909 }
02910 
02911 SDOperand DAGCombiner::SimplifySelectCC(SDOperand N0, SDOperand N1, 
02912                                         SDOperand N2, SDOperand N3,
02913                                         ISD::CondCode CC) {
02914   
02915   MVT::ValueType VT = N2.getValueType();
02916   ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val);
02917   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
02918   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
02919   ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
02920 
02921   // Determine if the condition we're dealing with is constant
02922   SDOperand SCC = SimplifySetCC(TLI.getSetCCResultTy(), N0, N1, CC, false);
02923   ConstantSDNode *SCCC = dyn_cast_or_null<ConstantSDNode>(SCC.Val);
02924 
02925   // fold select_cc true, x, y -> x
02926   if (SCCC && SCCC->getValue())
02927     return N2;
02928   // fold select_cc false, x, y -> y
02929   if (SCCC && SCCC->getValue() == 0)
02930     return N3;
02931   
02932   // Check to see if we can simplify the select into an fabs node
02933   if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) {
02934     // Allow either -0.0 or 0.0
02935     if (CFP->getValue() == 0.0) {
02936       // select (setg[te] X, +/-0.0), X, fneg(X) -> fabs
02937       if ((CC == ISD::SETGE || CC == ISD::SETGT) &&
02938           N0 == N2 && N3.getOpcode() == ISD::FNEG &&
02939           N2 == N3.getOperand(0))
02940         return DAG.getNode(ISD::FABS, VT, N0);
02941       
02942       // select (setl[te] X, +/-0.0), fneg(X), X -> fabs
02943       if ((CC == ISD::SETLT || CC == ISD::SETLE) &&
02944           N0 == N3 && N2.getOpcode() == ISD::FNEG &&
02945           N2.getOperand(0) == N3)
02946         return DAG.getNode(ISD::FABS, VT, N3);
02947     }
02948   }
02949   
02950   // Check to see if we can perform the "gzip trick", transforming
02951   // select_cc setlt X, 0, A, 0 -> and (sra X, size(X)-1), A
02952   if (N1C && N1C->isNullValue() && N3C && N3C->isNullValue() &&
02953       MVT::isInteger(N0.getValueType()) && 
02954       MVT::isInteger(N2.getValueType()) && CC == ISD::SETLT) {
02955     MVT::ValueType XType = N0.getValueType();
02956     MVT::ValueType AType = N2.getValueType();
02957     if (XType >= AType) {
02958       // and (sra X, size(X)-1, A) -> "and (srl X, C2), A" iff A is a
02959       // single-bit constant.
02960       if (N2C && ((N2C->getValue() & (N2C->getValue()-1)) == 0)) {
02961         unsigned ShCtV = Log2_64(N2C->getValue());
02962         ShCtV = MVT::getSizeInBits(XType)-ShCtV-1;
02963         SDOperand ShCt = DAG.getConstant(ShCtV, TLI.getShiftAmountTy());
02964         SDOperand Shift = DAG.getNode(ISD::SRL, XType, N0, ShCt);
02965         AddToWorkList(Shift.Val);
02966         if (XType > AType) {
02967           Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift);
02968           AddToWorkList(Shift.Val);
02969         }
02970         return DAG.getNode(ISD::AND, AType, Shift, N2);
02971       }
02972       SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
02973                                     DAG.getConstant(MVT::getSizeInBits(XType)-1,
02974                                                     TLI.getShiftAmountTy()));
02975       AddToWorkList(Shift.Val);
02976       if (XType > AType) {
02977         Shift = DAG.getNode(ISD::TRUNCATE, AType, Shift);
02978         AddToWorkList(Shift.Val);
02979       }
02980       return DAG.getNode(ISD::AND, AType, Shift, N2);
02981     }
02982   }
02983   
02984   // fold select C, 16, 0 -> shl C, 4
02985   if (N2C && N3C && N3C->isNullValue() && isPowerOf2_64(N2C->getValue()) &&
02986       TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult) {
02987     // Get a SetCC of the condition
02988     // FIXME: Should probably make sure that setcc is legal if we ever have a
02989     // target where it isn't.
02990     SDOperand Temp, SCC;
02991     // cast from setcc result type to select result type
02992     if (AfterLegalize) {
02993       SCC  = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC);
02994       Temp = DAG.getZeroExtendInReg(SCC, N2.getValueType());
02995     } else {
02996       SCC  = DAG.getSetCC(MVT::i1, N0, N1, CC);
02997       Temp = DAG.getNode(ISD::ZERO_EXTEND, N2.getValueType(), SCC);
02998     }
02999     AddToWorkList(SCC.Val);
03000     AddToWorkList(Temp.Val);
03001     // shl setcc result by log2 n2c
03002     return DAG.getNode(ISD::SHL, N2.getValueType(), Temp,
03003                        DAG.getConstant(Log2_64(N2C->getValue()),
03004                                        TLI.getShiftAmountTy()));
03005   }
03006     
03007   // Check to see if this is the equivalent of setcc
03008   // FIXME: Turn all of these into setcc if setcc if setcc is legal
03009   // otherwise, go ahead with the folds.
03010   if (0 && N3C && N3C->isNullValue() && N2C && (N2C->getValue() == 1ULL)) {
03011     MVT::ValueType XType = N0.getValueType();
03012     if (TLI.isOperationLegal(ISD::SETCC, TLI.getSetCCResultTy())) {
03013       SDOperand Res = DAG.getSetCC(TLI.getSetCCResultTy(), N0, N1, CC);
03014       if (Res.getValueType() != VT)
03015         Res = DAG.getNode(ISD::ZERO_EXTEND, VT, Res);
03016       return Res;
03017     }
03018     
03019     // seteq X, 0 -> srl (ctlz X, log2(size(X)))
03020     if (N1C && N1C->isNullValue() && CC == ISD::SETEQ && 
03021         TLI.isOperationLegal(ISD::CTLZ, XType)) {
03022       SDOperand Ctlz = DAG.getNode(ISD::CTLZ, XType, N0);
03023       return DAG.getNode(ISD::SRL, XType, Ctlz, 
03024                          DAG.getConstant(Log2_32(MVT::getSizeInBits(XType)),
03025                                          TLI.getShiftAmountTy()));
03026     }
03027     // setgt X, 0 -> srl (and (-X, ~X), size(X)-1)
03028     if (N1C && N1C->isNullValue() && CC == ISD::SETGT) { 
03029       SDOperand NegN0 = DAG.getNode(ISD::SUB, XType, DAG.getConstant(0, XType),
03030                                     N0);
03031       SDOperand NotN0 = DAG.getNode(ISD::XOR, XType, N0, 
03032                                     DAG.getConstant(~0ULL, XType));
03033       return DAG.getNode(ISD::SRL, XType, 
03034                          DAG.getNode(ISD::AND, XType, NegN0, NotN0),
03035                          DAG.getConstant(MVT::getSizeInBits(XType)-1,
03036                                          TLI.getShiftAmountTy()));
03037     }
03038     // setgt X, -1 -> xor (srl (X, size(X)-1), 1)
03039     if (N1C && N1C->isAllOnesValue() && CC == ISD::SETGT) {
03040       SDOperand Sign = DAG.getNode(ISD::SRL, XType, N0,
03041                                    DAG.getConstant(MVT::getSizeInBits(XType)-1,
03042                                                    TLI.getShiftAmountTy()));
03043       return DAG.getNode(ISD::XOR, XType, Sign, DAG.getConstant(1, XType));
03044     }
03045   }
03046   
03047   // Check to see if this is an integer abs. select_cc setl[te] X, 0, -X, X ->
03048   // Y = sra (X, size(X)-1); xor (add (X, Y), Y)
03049   if (N1C && N1C->isNullValue() && (CC == ISD::SETLT || CC == ISD::SETLE) &&
03050       N0 == N3 && N2.getOpcode() == ISD::SUB && N0 == N2.getOperand(1)) {
03051     if (ConstantSDNode *SubC = dyn_cast<ConstantSDNode>(N2.getOperand(0))) {
03052       MVT::ValueType XType = N0.getValueType();
03053       if (SubC->isNullValue() && MVT::isInteger(XType)) {
03054         SDOperand Shift = DAG.getNode(ISD::SRA, XType, N0,
03055                                     DAG.getConstant(MVT::getSizeInBits(XType)-1,
03056                                                     TLI.getShiftAmountTy()));
03057         SDOperand Add = DAG.getNode(ISD::ADD, XType, N0, Shift);
03058         AddToWorkList(Shift.Val);
03059         AddToWorkList(Add.Val);
03060         return DAG.getNode(ISD::XOR, XType, Add, Shift);
03061       }
03062     }
03063   }
03064 
03065   return SDOperand();
03066 }
03067 
03068 SDOperand DAGCombiner::SimplifySetCC(MVT::ValueType VT, SDOperand N0,
03069                                      SDOperand N1, ISD::CondCode Cond,
03070                                      bool foldBooleans) {
03071   // These setcc operations always fold.
03072   switch (Cond) {
03073   default: break;
03074   case ISD::SETFALSE:
03075   case ISD::SETFALSE2: return DAG.getConstant(0, VT);
03076   case ISD::SETTRUE:
03077   case ISD::SETTRUE2:  return DAG.getConstant(1, VT);
03078   }
03079 
03080   if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
03081     uint64_t C1 = N1C->getValue();
03082     if (ConstantSDNode *N0C = dyn_cast<ConstantSDNode>(N0.Val)) {
03083       uint64_t C0 = N0C->getValue();
03084 
03085       // Sign extend the operands if required
03086       if (ISD::isSignedIntSetCC(Cond)) {
03087         C0 = N0C->getSignExtended();
03088         C1 = N1C->getSignExtended();
03089       }
03090 
03091       switch (Cond) {
03092       default: assert(0 && "Unknown integer setcc!");
03093       case ISD::SETEQ:  return DAG.getConstant(C0 == C1, VT);
03094       case ISD::SETNE:  return DAG.getConstant(C0 != C1, VT);
03095       case ISD::SETULT: return DAG.getConstant(C0 <  C1, VT);
03096       case ISD::SETUGT: return DAG.getConstant(C0 >  C1, VT);
03097       case ISD::SETULE: return DAG.getConstant(C0 <= C1, VT);
03098       case ISD::SETUGE: return DAG.getConstant(C0 >= C1, VT);
03099       case ISD::SETLT:  return DAG.getConstant((int64_t)C0 <  (int64_t)C1, VT);
03100       case ISD::SETGT:  return DAG.getConstant((int64_t)C0 >  (int64_t)C1, VT);
03101       case ISD::SETLE:  return DAG.getConstant((int64_t)C0 <= (int64_t)C1, VT);
03102       case ISD::SETGE:  return DAG.getConstant((int64_t)C0 >= (int64_t)C1, VT);
03103       }
03104     } else {
03105       // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
03106       if (N0.getOpcode() == ISD::ZERO_EXTEND) {
03107         unsigned InSize = MVT::getSizeInBits(N0.getOperand(0).getValueType());
03108 
03109         // If the comparison constant has bits in the upper part, the
03110         // zero-extended value could never match.
03111         if (C1 & (~0ULL << InSize)) {
03112           unsigned VSize = MVT::getSizeInBits(N0.getValueType());
03113           switch (Cond) {
03114           case ISD::SETUGT:
03115           case ISD::SETUGE:
03116           case ISD::SETEQ: return DAG.getConstant(0, VT);
03117           case ISD::SETULT:
03118           case ISD::SETULE:
03119           case ISD::SETNE: return DAG.getConstant(1, VT);
03120           case ISD::SETGT:
03121           case ISD::SETGE:
03122             // True if the sign bit of C1 is set.
03123             return DAG.getConstant((C1 & (1ULL << VSize)) != 0, VT);
03124           case ISD::SETLT:
03125           case ISD::SETLE:
03126             // True if the sign bit of C1 isn't set.
03127             return DAG.getConstant((C1 & (1ULL << VSize)) == 0, VT);
03128           default:
03129             break;
03130           }
03131         }
03132 
03133         // Otherwise, we can perform the comparison with the low bits.
03134         switch (Cond) {
03135         case ISD::SETEQ:
03136         case ISD::SETNE:
03137         case ISD::SETUGT:
03138         case ISD::SETUGE:
03139         case ISD::SETULT:
03140         case ISD::SETULE:
03141           return DAG.getSetCC(VT, N0.getOperand(0),
03142                           DAG.getConstant(C1, N0.getOperand(0).getValueType()),
03143                           Cond);
03144         default:
03145           break;   // todo, be more careful with signed comparisons
03146         }
03147       } else if (N0.getOpcode() == ISD::SIGN_EXTEND_INREG &&
03148                  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
03149         MVT::ValueType ExtSrcTy = cast<VTSDNode>(N0.getOperand(1))->getVT();
03150         unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
03151         MVT::ValueType ExtDstTy = N0.getValueType();
03152         unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
03153 
03154         // If the extended part has any inconsistent bits, it cannot ever
03155         // compare equal.  In other words, they have to be all ones or all
03156         // zeros.
03157         uint64_t ExtBits =
03158           (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
03159         if ((C1 & ExtBits) != 0 && (C1 & ExtBits) != ExtBits)
03160           return DAG.getConstant(Cond == ISD::SETNE, VT);
03161         
03162         SDOperand ZextOp;
03163         MVT::ValueType Op0Ty = N0.getOperand(0).getValueType();
03164         if (Op0Ty == ExtSrcTy) {
03165           ZextOp = N0.getOperand(0);
03166         } else {
03167           int64_t Imm = ~0ULL >> (64-ExtSrcTyBits);
03168           ZextOp = DAG.getNode(ISD::AND, Op0Ty, N0.getOperand(0),
03169                                DAG.getConstant(Imm, Op0Ty));
03170         }
03171         AddToWorkList(ZextOp.Val);
03172         // Otherwise, make this a use of a zext.
03173         return DAG.getSetCC(VT, ZextOp, 
03174                             DAG.getConstant(C1 & (~0ULL>>(64-ExtSrcTyBits)), 
03175                                             ExtDstTy),
03176                             Cond);
03177       } else if ((N1C->getValue() == 0 || N1C->getValue() == 1) &&
03178                  (Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
03179                  (N0.getOpcode() == ISD::XOR ||
03180                   (N0.getOpcode() == ISD::AND && 
03181                    N0.getOperand(0).getOpcode() == ISD::XOR &&
03182                    N0.getOperand(1) == N0.getOperand(0).getOperand(1))) &&
03183                  isa<ConstantSDNode>(N0.getOperand(1)) &&
03184                  cast<ConstantSDNode>(N0.getOperand(1))->getValue() == 1) {
03185         // If this is (X^1) == 0/1, swap the RHS and eliminate the xor.  We can
03186         // only do this if the top bits are known zero.
03187         if (TLI.MaskedValueIsZero(N1, 
03188                                   MVT::getIntVTBitMask(N0.getValueType())-1)) {
03189           // Okay, get the un-inverted input value.
03190           SDOperand Val;
03191           if (N0.getOpcode() == ISD::XOR)
03192             Val = N0.getOperand(0);
03193           else {
03194             assert(N0.getOpcode() == ISD::AND && 
03195                    N0.getOperand(0).getOpcode() == ISD::XOR);
03196             // ((X^1)&1)^1 -> X & 1
03197             Val = DAG.getNode(ISD::AND, N0.getValueType(),
03198                               N0.getOperand(0).getOperand(0), N0.getOperand(1));
03199           }
03200           return DAG.getSetCC(VT, Val, N1,
03201                               Cond == ISD::SETEQ ? ISD::SETNE : ISD::SETEQ);
03202         }
03203       }
03204       
03205       uint64_t MinVal, MaxVal;
03206       unsigned OperandBitSize = MVT::getSizeInBits(N1C->getValueType(0));
03207       if (ISD::isSignedIntSetCC(Cond)) {
03208         MinVal = 1ULL << (OperandBitSize-1);
03209         if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
03210           MaxVal = ~0ULL >> (65-OperandBitSize);
03211         else
03212           MaxVal = 0;
03213       } else {
03214         MinVal = 0;
03215         MaxVal = ~0ULL >> (64-OperandBitSize);
03216       }
03217 
03218       // Canonicalize GE/LE comparisons to use GT/LT comparisons.
03219       if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
03220         if (C1 == MinVal) return DAG.getConstant(1, VT);   // X >= MIN --> true
03221         --C1;                                          // X >= C0 --> X > (C0-1)
03222         return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
03223                         (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
03224       }
03225 
03226       if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
03227         if (C1 == MaxVal) return DAG.getConstant(1, VT);   // X <= MAX --> true
03228         ++C1;                                          // X <= C0 --> X < (C0+1)
03229         return DAG.getSetCC(VT, N0, DAG.getConstant(C1, N1.getValueType()),
03230                         (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
03231       }
03232 
03233       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal)
03234         return DAG.getConstant(0, VT);      // X < MIN --> false
03235 
03236       // Canonicalize setgt X, Min --> setne X, Min
03237       if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MinVal)
03238         return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
03239       // Canonicalize setlt X, Max --> setne X, Max
03240       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MaxVal)
03241         return DAG.getSetCC(VT, N0, N1, ISD::SETNE);
03242 
03243       // If we have setult X, 1, turn it into seteq X, 0
03244       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C1 == MinVal+1)
03245         return DAG.getSetCC(VT, N0, DAG.getConstant(MinVal, N0.getValueType()),
03246                         ISD::SETEQ);
03247       // If we have setugt X, Max-1, turn it into seteq X, Max
03248       else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C1 == MaxVal-1)
03249         return DAG.getSetCC(VT, N0, DAG.getConstant(MaxVal, N0.getValueType()),
03250                         ISD::SETEQ);
03251 
03252       // If we have "setcc X, C0", check to see if we can shrink the immediate
03253       // by changing cc.
03254 
03255       // SETUGT X, SINTMAX  -> SETLT X, 0
03256       if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
03257           C1 == (~0ULL >> (65-OperandBitSize)))
03258         return DAG.getSetCC(VT, N0, DAG.getConstant(0, N1.getValueType()),
03259                             ISD::SETLT);
03260 
03261       // FIXME: Implement the rest of these.
03262 
03263       // Fold bit comparisons when we can.
03264       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
03265           VT == N0.getValueType() && N0.getOpcode() == ISD::AND)
03266         if (ConstantSDNode *AndRHS =
03267                     dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
03268           if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
03269             // Perform the xform if the AND RHS is a single bit.
03270             if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
03271               return DAG.getNode(ISD::SRL, VT, N0,
03272                              DAG.getConstant(Log2_64(AndRHS->getValue()),
03273                                                    TLI.getShiftAmountTy()));
03274             }
03275           } else if (Cond == ISD::SETEQ && C1 == AndRHS->getValue()) {
03276             // (X & 8) == 8  -->  (X & 8) >> 3
03277             // Perform the xform if C1 is a single bit.
03278             if ((C1 & (C1-1)) == 0) {
03279               return DAG.getNode(ISD::SRL, VT, N0,
03280                              DAG.getConstant(Log2_64(C1),TLI.getShiftAmountTy()));
03281             }
03282           }
03283         }
03284     }
03285   } else if (isa<ConstantSDNode>(N0.Val)) {
03286       // Ensure that the constant occurs on the RHS.
03287     return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
03288   }
03289 
03290   if (ConstantFPSDNode *N0C = dyn_cast<ConstantFPSDNode>(N0.Val))
03291     if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) {
03292       double C0 = N0C->getValue(), C1 = N1C->getValue();
03293 
03294       switch (Cond) {
03295       default: break; // FIXME: Implement the rest of these!
03296       case ISD::SETEQ:  return DAG.getConstant(C0 == C1, VT);
03297       case ISD::SETNE:  return DAG.getConstant(C0 != C1, VT);
03298       case ISD::SETLT:  return DAG.getConstant(C0 < C1, VT);
03299       case ISD::SETGT:  return DAG.getConstant(C0 > C1, VT);
03300       case ISD::SETLE:  return DAG.getConstant(C0 <= C1, VT);
03301       case ISD::SETGE:  return DAG.getConstant(C0 >= C1, VT);
03302       }
03303     } else {
03304       // Ensure that the constant occurs on the RHS.
03305       return DAG.getSetCC(VT, N1, N0, ISD::getSetCCSwappedOperands(Cond));
03306     }
03307 
03308   if (N0 == N1) {
03309     // We can always fold X == Y for integer setcc's.
03310     if (MVT::isInteger(N0.getValueType()))
03311       return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
03312     unsigned UOF = ISD::getUnorderedFlavor(Cond);
03313     if (UOF == 2)   // FP operators that are undefined on NaNs.
03314       return DAG.getConstant(ISD::isTrueWhenEqual(Cond), VT);
03315     if (UOF == unsigned(ISD::isTrueWhenEqual(Cond)))
03316       return DAG.getConstant(UOF, VT);
03317     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
03318     // if it is not already.
03319     ISD::CondCode NewCond = UOF == 0 ? ISD::SETO : ISD::SETUO;
03320     if (NewCond != Cond)
03321       return DAG.getSetCC(VT, N0, N1, NewCond);
03322   }
03323 
03324   if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
03325       MVT::isInteger(N0.getValueType())) {
03326     if (N0.getOpcode() == ISD::ADD || N0.getOpcode() == ISD::SUB ||
03327         N0.getOpcode() == ISD::XOR) {
03328       // Simplify (X+Y) == (X+Z) -->  Y == Z
03329       if (N0.getOpcode() == N1.getOpcode()) {
03330         if (N0.getOperand(0) == N1.getOperand(0))
03331           return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(1), Cond);
03332         if (N0.getOperand(1) == N1.getOperand(1))
03333           return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(0), Cond);
03334         if (isCommutativeBinOp(N0.getOpcode())) {
03335           // If X op Y == Y op X, try other combinations.
03336           if (N0.getOperand(0) == N1.getOperand(1))
03337             return DAG.getSetCC(VT, N0.getOperand(1), N1.getOperand(0), Cond);
03338           if (N0.getOperand(1) == N1.getOperand(0))
03339             return DAG.getSetCC(VT, N0.getOperand(0), N1.getOperand(1), Cond);
03340         }
03341       }
03342       
03343       if (ConstantSDNode *RHSC = dyn_cast<ConstantSDNode>(N1)) {
03344         if (ConstantSDNode *LHSR = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
03345           // Turn (X+C1) == C2 --> X == C2-C1
03346           if (N0.getOpcode() == ISD::ADD && N0.Val->hasOneUse()) {
03347             return DAG.getSetCC(VT, N0.getOperand(0),
03348                               DAG.getConstant(RHSC->getValue()-LHSR->getValue(),
03349                                 N0.getValueType()), Cond);
03350           }
03351           
03352           // Turn (X^C1) == C2 into X == C1^C2 iff X&~C1 = 0.
03353           if (N0.getOpcode() == ISD::XOR)
03354             // If we know that all of the inverted bits are zero, don't bother
03355             // performing the inversion.
03356             if (TLI.MaskedValueIsZero(N0.getOperand(0), ~LHSR->getValue()))
03357               return DAG.getSetCC(VT, N0.getOperand(0),
03358                               DAG.getConstant(LHSR->getValue()^RHSC->getValue(),
03359                                               N0.getValueType()), Cond);
03360         }
03361         
03362         // Turn (C1-X) == C2 --> X == C1-C2
03363         if (ConstantSDNode *SUBC = dyn_cast<ConstantSDNode>(N0.getOperand(0))) {
03364           if (N0.getOpcode() == ISD::SUB && N0.Val->hasOneUse()) {
03365             return DAG.getSetCC(VT, N0.getOperand(1),
03366                              DAG.getConstant(SUBC->getValue()-RHSC->getValue(),
03367                                              N0.getValueType()), Cond);
03368           }
03369         }          
03370       }
03371 
03372       // Simplify (X+Z) == X -->  Z == 0
03373       if (N0.getOperand(0) == N1)
03374         return DAG.getSetCC(VT, N0.getOperand(1),
03375                         DAG.getConstant(0, N0.getValueType()), Cond);
03376       if (N0.getOperand(1) == N1) {
03377         if (isCommutativeBinOp(N0.getOpcode()))
03378           return DAG.getSetCC(VT, N0.getOperand(0),
03379                           DAG.getConstant(0, N0.getValueType()), Cond);
03380         else {
03381           assert(N0.getOpcode() == ISD::SUB && "Unexpected operation!");
03382           // (Z-X) == X  --> Z == X<<1
03383           SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(),
03384                                      N1, 
03385                                      DAG.getConstant(1,TLI.getShiftAmountTy()));
03386           AddToWorkList(SH.Val);
03387           return DAG.getSetCC(VT, N0.getOperand(0), SH, Cond);
03388         }
03389       }
03390     }
03391 
03392     if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
03393         N1.getOpcode() == ISD::XOR) {
03394       // Simplify  X == (X+Z) -->  Z == 0
03395       if (N1.getOperand(0) == N0) {
03396         return DAG.getSetCC(VT, N1.getOperand(1),
03397                         DAG.getConstant(0, N1.getValueType()), Cond);
03398       } else if (N1.getOperand(1) == N0) {
03399         if (isCommutativeBinOp(N1.getOpcode())) {
03400           return DAG.getSetCC(VT, N1.getOperand(0),
03401                           DAG.getConstant(0, N1.getValueType()), Cond);
03402         } else {
03403           assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
03404           // X == (Z-X)  --> X<<1 == Z
03405           SDOperand SH = DAG.getNode(ISD::SHL, N1.getValueType(), N0, 
03406                                      DAG.getConstant(1,TLI.getShiftAmountTy()));
03407           AddToWorkList(SH.Val);
03408           return DAG.getSetCC(VT, SH, N1.getOperand(0), Cond);
03409         }
03410       }
03411     }
03412   }
03413 
03414   // Fold away ALL boolean setcc's.
03415   SDOperand Temp;
03416   if (N0.getValueType() == MVT::i1 && foldBooleans) {
03417     switch (Cond) {
03418     default: assert(0 && "Unknown integer setcc!");
03419     case ISD::SETEQ:  // X == Y  -> (X^Y)^1
03420       Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
03421       N0 = DAG.getNode(ISD::XOR, MVT::i1, Temp, DAG.getConstant(1, MVT::i1));
03422       AddToWorkList(Temp.Val);
03423       break;
03424     case ISD::SETNE:  // X != Y   -->  (X^Y)
03425       N0 = DAG.getNode(ISD::XOR, MVT::i1, N0, N1);
03426       break;
03427     case ISD::SETGT:  // X >s Y   -->  X == 0 & Y == 1  -->  X^1 & Y
03428     case ISD::SETULT: // X <u Y   -->  X == 0 & Y == 1  -->  X^1 & Y
03429       Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
03430       N0 = DAG.getNode(ISD::AND, MVT::i1, N1, Temp);
03431       AddToWorkList(Temp.Val);
03432       break;
03433     case ISD::SETLT:  // X <s Y   --> X == 1 & Y == 0  -->  Y^1 & X
03434     case ISD::SETUGT: // X >u Y   --> X == 1 & Y == 0  -->  Y^1 & X
03435       Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
03436       N0 = DAG.getNode(ISD::AND, MVT::i1, N0, Temp);
03437       AddToWorkList(Temp.Val);
03438       break;
03439     case ISD::SETULE: // X <=u Y  --> X == 0 | Y == 1  -->  X^1 | Y
03440     case ISD::SETGE:  // X >=s Y  --> X == 0 | Y == 1  -->  X^1 | Y
03441       Temp = DAG.getNode(ISD::XOR, MVT::i1, N0, DAG.getConstant(1, MVT::i1));
03442       N0 = DAG.getNode(ISD::OR, MVT::i1, N1, Temp);
03443       AddToWorkList(Temp.Val);
03444       break;
03445     case ISD::SETUGE: // X >=u Y  --> X == 1 | Y == 0  -->  Y^1 | X
03446     case ISD::SETLE:  // X <=s Y  --> X == 1 | Y == 0  -->  Y^1 | X
03447       Temp = DAG.getNode(ISD::XOR, MVT::i1, N1, DAG.getConstant(1, MVT::i1));
03448       N0 = DAG.getNode(ISD::OR, MVT::i1, N0, Temp);
03449       break;
03450     }
03451     if (VT != MVT::i1) {
03452       AddToWorkList(N0.Val);
03453       // FIXME: If running after legalize, we probably can't do this.
03454       N0 = DAG.getNode(ISD::ZERO_EXTEND, VT, N0);
03455     }
03456     return N0;
03457   }
03458 
03459   // Could not fold it.
03460   return SDOperand();
03461 }
03462 
03463 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
03464 /// return a DAG expression to select that will generate the same value by
03465 /// multiplying by a magic number.  See:
03466 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
03467 SDOperand DAGCombiner::BuildSDIV(SDNode *N) {
03468   MVT::ValueType VT = N->getValueType(0);
03469   
03470   // Check to see if we can do this.
03471   if (!TLI.isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
03472     return SDOperand();       // BuildSDIV only operates on i32 or i64
03473   if (!TLI.isOperationLegal(ISD::MULHS, VT))
03474     return SDOperand();       // Make sure the target supports MULHS.
03475   
03476   int64_t d = cast<ConstantSDNode>(N->getOperand(1))->getSignExtended();
03477   ms magics = (VT == MVT::i32) ? magic32(d) : magic64(d);
03478   
03479   // Multiply the numerator (operand 0) by the magic value
03480   SDOperand Q = DAG.getNode(ISD::MULHS, VT, N->getOperand(0),
03481                             DAG.getConstant(magics.m, VT));
03482   // If d > 0 and m < 0, add the numerator
03483   if (d > 0 && magics.m < 0) { 
03484     Q = DAG.getNode(ISD::ADD, VT, Q, N->getOperand(0));
03485     AddToWorkList(Q.Val);
03486   }
03487   // If d < 0 and m > 0, subtract the numerator.
03488   if (d < 0 && magics.m > 0) {
03489     Q = DAG.getNode(ISD::SUB, VT, Q, N->getOperand(0));
03490     AddToWorkList(Q.Val);
03491   }
03492   // Shift right algebraic if shift value is nonzero
03493   if (magics.s > 0) {
03494     Q = DAG.getNode(ISD::SRA, VT, Q, 
03495                     DAG.getConstant(magics.s, TLI.getShiftAmountTy()));
03496     AddToWorkList(Q.Val);
03497   }
03498   // Extract the sign bit and add it to the quotient
03499   SDOperand T =
03500     DAG.getNode(ISD::SRL, VT, Q, DAG.getConstant(MVT::getSizeInBits(VT)-1,
03501                                                  TLI.getShiftAmountTy()));
03502   AddToWorkList(T.Val);
03503   return DAG.getNode(ISD::ADD, VT, Q, T);
03504 }
03505 
03506 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
03507 /// return a DAG expression to select that will generate the same value by
03508 /// multiplying by a magic number.  See:
03509 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
03510 SDOperand DAGCombiner::BuildUDIV(SDNode *N) {
03511   MVT::ValueType VT = N->getValueType(0);
03512   
03513   // Check to see if we can do this.
03514   if (!TLI.isTypeLegal(VT) || (VT != MVT::i32 && VT != MVT::i64))
03515     return SDOperand();       // BuildUDIV only operates on i32 or i64
03516   if (!TLI.isOperationLegal(ISD::MULHU, VT))
03517     return SDOperand();       // Make sure the target supports MULHU.
03518   
03519   uint64_t d = cast<ConstantSDNode>(N->getOperand(1))->getValue();
03520   mu magics = (VT == MVT::i32) ? magicu32(d) : magicu64(d);
03521   
03522   // Multiply the numerator (operand 0) by the magic value
03523   SDOperand Q = DAG.getNode(ISD::MULHU, VT, N->getOperand(0),
03524                             DAG.getConstant(magics.m, VT));
03525   AddToWorkList(Q.Val);
03526 
03527   if (magics.a == 0) {
03528     return DAG.getNode(ISD::SRL, VT, Q, 
03529                        DAG.getConstant(magics.s, TLI.getShiftAmountTy()));
03530   } else {
03531     SDOperand NPQ = DAG.getNode(ISD::SUB, VT, N->getOperand(0), Q);
03532     AddToWorkList(NPQ.Val);
03533     NPQ = DAG.getNode(ISD::SRL, VT, NPQ, 
03534                       DAG.getConstant(1, TLI.getShiftAmountTy()));
03535     AddToWorkList(NPQ.Val);
03536     NPQ = DAG.getNode(ISD::ADD, VT, NPQ, Q);
03537     AddToWorkList(NPQ.Val);
03538     return DAG.getNode(ISD::SRL, VT, NPQ, 
03539                        DAG.getConstant(magics.s-1, TLI.getShiftAmountTy()));
03540   }
03541 }
03542 
03543 // SelectionDAG::Combine - This is the entry point for the file.
03544 //
03545 void SelectionDAG::Combine(bool RunningAfterLegalize) {
03546   /// run - This is the main entry point to this class.
03547   ///
03548   DAGCombiner(*this).Run(RunningAfterLegalize);
03549 }