lib/CodeGen/SelectionDAG/SelectionDAG.cpp

   1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the SelectionDAG class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/SelectionDAG.h"
  15 #include "llvm/Constants.h"
  16 #include "llvm/GlobalValue.h"
  17 #include "llvm/Intrinsics.h"
  18 #include "llvm/Assembly/Writer.h"
  19 #include "llvm/CodeGen/MachineBasicBlock.h"
  20 #include "llvm/Support/MathExtras.h"
  21 #include "llvm/Target/MRegisterInfo.h"
  22 #include "llvm/Target/TargetLowering.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/ADT/SetVector.h"
  26 #include "llvm/ADT/SmallVector.h"
  27 #include "llvm/ADT/StringExtras.h"
  28 #include <iostream>
  29 #include <set>
  30 #include <cmath>
  31 #include <algorithm>
  32 using namespace llvm;
  33
  34 /// makeVTList - Return an instance of the SDVTList struct initialized with the
  35 /// specified members.
  36 static SDVTList makeVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
  37   SDVTList Res = {VTs, NumVTs};
  38   return Res;
  39 }
  40
  41 static bool isCommutativeBinOp(unsigned Opcode) {
  42   switch (Opcode) {
  43   case ISD::ADD:
  44   case ISD::MUL:
  45   case ISD::MULHU:
  46   case ISD::MULHS:
  47   case ISD::FADD:
  48   case ISD::FMUL:
  49   case ISD::AND:
  50   case ISD::OR:
  51   case ISD::XOR: return true;
  52   default: return false; // FIXME: Need commutative info for user ops!
  53   }
  54 }
  55
  56 // isInvertibleForFree - Return true if there is no cost to emitting the logical
  57 // inverse of this node.
  58 static bool isInvertibleForFree(SDOperand N) {
  59   if (isa<ConstantSDNode>(N.Val)) return true;
  60   if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse())
  61     return true;
  62   return false;
  63 }
  64
  65 //===----------------------------------------------------------------------===//
  66 //                              ConstantFPSDNode Class
  67 //===----------------------------------------------------------------------===//
  68
  69 /// isExactlyValue - We don't rely on operator== working on double values, as
  70 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
  71 /// As such, this method can be used to do an exact bit-for-bit comparison of
  72 /// two floating point values.
  73 bool ConstantFPSDNode::isExactlyValue(double V) const {
  74   return DoubleToBits(V) == DoubleToBits(Value);
  75 }
  76
  77 //===----------------------------------------------------------------------===//
  78 //                              ISD Namespace
  79 //===----------------------------------------------------------------------===//
  80
  81 /// isBuildVectorAllOnes - Return true if the specified node is a
  82 /// BUILD_VECTOR where all of the elements are ~0 or undef.
  83 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
  84   // Look through a bit convert.
  85   if (N->getOpcode() == ISD::BIT_CONVERT)
  86     N = N->getOperand(0).Val;
  87
  88   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
  89
  90   unsigned i = 0, e = N->getNumOperands();
  91
  92   // Skip over all of the undef values.
  93   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
  94     ++i;
  95
  96   // Do not accept an all-undef vector.
  97   if (i == e) return false;
  98
  99   // Do not accept build_vectors that aren't all constants or which have non-~0
 100   // elements.
 101   SDOperand NotZero = N->getOperand(i);
 102   if (isa<ConstantSDNode>(NotZero)) {
 103     if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue())
 104       return false;
 105   } else if (isa<ConstantFPSDNode>(NotZero)) {
 106     MVT::ValueType VT = NotZero.getValueType();
 107     if (VT== MVT::f64) {
 108       if (DoubleToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) !=
 109           (uint64_t)-1)
 110         return false;
 111     } else {
 112       if (FloatToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) !=
 113           (uint32_t)-1)
 114         return false;
 115     }
 116   } else
 117     return false;
 118
 119   // Okay, we have at least one ~0 value, check to see if the rest match or are
 120   // undefs.
 121   for (++i; i != e; ++i)
 122     if (N->getOperand(i) != NotZero &&
 123         N->getOperand(i).getOpcode() != ISD::UNDEF)
 124       return false;
 125   return true;
 126 }
 127
 128
 129 /// isBuildVectorAllZeros - Return true if the specified node is a
 130 /// BUILD_VECTOR where all of the elements are 0 or undef.
 131 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
 132   // Look through a bit convert.
 133   if (N->getOpcode() == ISD::BIT_CONVERT)
 134     N = N->getOperand(0).Val;
 135
 136   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
 137
 138   unsigned i = 0, e = N->getNumOperands();
 139
 140   // Skip over all of the undef values.
 141   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
 142     ++i;
 143
 144   // Do not accept an all-undef vector.
 145   if (i == e) return false;
 146
 147   // Do not accept build_vectors that aren't all constants or which have non-~0
 148   // elements.
 149   SDOperand Zero = N->getOperand(i);
 150   if (isa<ConstantSDNode>(Zero)) {
 151     if (!cast<ConstantSDNode>(Zero)->isNullValue())
 152       return false;
 153   } else if (isa<ConstantFPSDNode>(Zero)) {
 154     if (!cast<ConstantFPSDNode>(Zero)->isExactlyValue(0.0))
 155       return false;
 156   } else
 157     return false;
 158
 159   // Okay, we have at least one ~0 value, check to see if the rest match or are
 160   // undefs.
 161   for (++i; i != e; ++i)
 162     if (N->getOperand(i) != Zero &&
 163         N->getOperand(i).getOpcode() != ISD::UNDEF)
 164       return false;
 165   return true;
 166 }
 167
 168 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
 169 /// when given the operation for (X op Y).
 170 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
 171   // To perform this operation, we just need to swap the L and G bits of the
 172   // operation.
 173   unsigned OldL = (Operation >> 2) & 1;
 174   unsigned OldG = (Operation >> 1) & 1;
 175   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
 176                        (OldL << 1) |       // New G bit
 177                        (OldG << 2));        // New L bit.
 178 }
 179
 180 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
 181 /// 'op' is a valid SetCC operation.
 182 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
 183   unsigned Operation = Op;
 184   if (isInteger)
 185     Operation ^= 7;   // Flip L, G, E bits, but not U.
 186   else
 187     Operation ^= 15;  // Flip all of the condition bits.
 188   if (Operation > ISD::SETTRUE2)
 189     Operation &= ~8;     // Don't let N and U bits get set.
 190   return ISD::CondCode(Operation);
 191 }
 192
 193
 194 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
 195 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
 196 /// if the operation does not depend on the sign of the input (setne and seteq).
 197 static int isSignedOp(ISD::CondCode Opcode) {
 198   switch (Opcode) {
 199   default: assert(0 && "Illegal integer setcc operation!");
 200   case ISD::SETEQ:
 201   case ISD::SETNE: return 0;
 202   case ISD::SETLT:
 203   case ISD::SETLE:
 204   case ISD::SETGT:
 205   case ISD::SETGE: return 1;
 206   case ISD::SETULT:
 207   case ISD::SETULE:
 208   case ISD::SETUGT:
 209   case ISD::SETUGE: return 2;
 210   }
 211 }
 212
 213 /// getSetCCOrOperation - Return the result of a logical OR between different
 214 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
 215 /// returns SETCC_INVALID if it is not possible to represent the resultant
 216 /// comparison.
 217 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 218                                        bool isInteger) {
 219   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 220     // Cannot fold a signed integer setcc with an unsigned integer setcc.
 221     return ISD::SETCC_INVALID;
 222
 223   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
 224
 225   // If the N and U bits get set then the resultant comparison DOES suddenly
 226   // care about orderedness, and is true when ordered.
 227   if (Op > ISD::SETTRUE2)
 228     Op &= ~16;     // Clear the U bit if the N bit is set.
 229
 230   // Canonicalize illegal integer setcc's.
 231   if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
 232     Op = ISD::SETNE;
 233
 234   return ISD::CondCode(Op);
 235 }
 236
 237 /// getSetCCAndOperation - Return the result of a logical AND between different
 238 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
 239 /// function returns zero if it is not possible to represent the resultant
 240 /// comparison.
 241 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 242                                         bool isInteger) {
 243   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 244     // Cannot fold a signed setcc with an unsigned setcc.
 245     return ISD::SETCC_INVALID;
 246
 247   // Combine all of the condition bits.
 248   ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
 249
 250   // Canonicalize illegal integer setcc's.
 251   if (isInteger) {
 252     switch (Result) {
 253     default: break;
 254     case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
 255     case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
 256     case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
 257     case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
 258     }
 259   }
 260
 261   return Result;
 262 }
 263
 264 const TargetMachine &SelectionDAG::getTarget() const {
 265   return TLI.getTargetMachine();
 266 }
 267
 268 //===----------------------------------------------------------------------===//
 269 //                              SelectionDAG Class
 270 //===----------------------------------------------------------------------===//
 271
 272 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
 273 /// SelectionDAG.
 274 void SelectionDAG::RemoveDeadNodes() {
 275   // Create a dummy node (which is not added to allnodes), that adds a reference
 276   // to the root node, preventing it from being deleted.
 277   HandleSDNode Dummy(getRoot());
 278
 279   SmallVector<SDNode*, 128> DeadNodes;
 280
 281   // Add all obviously-dead nodes to the DeadNodes worklist.
 282   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
 283     if (I->use_empty())
 284       DeadNodes.push_back(I);
 285
 286   // Process the worklist, deleting the nodes and adding their uses to the
 287   // worklist.
 288   while (!DeadNodes.empty()) {
 289     SDNode *N = DeadNodes.back();
 290     DeadNodes.pop_back();
 291
 292     // Take the node out of the appropriate CSE map.
 293     RemoveNodeFromCSEMaps(N);
 294
 295     // Next, brutally remove the operand list.  This is safe to do, as there are
 296     // no cycles in the graph.
 297     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
 298       SDNode *Operand = I->Val;
 299       Operand->removeUser(N);
 300
 301       // Now that we removed this operand, see if there are no uses of it left.
 302       if (Operand->use_empty())
 303         DeadNodes.push_back(Operand);
 304     }
 305     delete[] N->OperandList;
 306     N->OperandList = 0;
 307     N->NumOperands = 0;
 308
 309     // Finally, remove N itself.
 310     AllNodes.erase(N);
 311   }
 312
 313   // If the root changed (e.g. it was a dead load, update the root).
 314   setRoot(Dummy.getValue());
 315 }
 316
 317 void SelectionDAG::DeleteNode(SDNode *N) {
 318   assert(N->use_empty() && "Cannot delete a node that is not dead!");
 319
 320   // First take this out of the appropriate CSE map.
 321   RemoveNodeFromCSEMaps(N);
 322
 323   // Finally, remove uses due to operands of this node, remove from the
 324   // AllNodes list, and delete the node.
 325   DeleteNodeNotInCSEMaps(N);
 326 }
 327
 328 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
 329
 330   // Remove it from the AllNodes list.
 331   AllNodes.remove(N);
 332
 333   // Drop all of the operands and decrement used nodes use counts.
 334   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
 335     I->Val->removeUser(N);
 336   delete[] N->OperandList;
 337   N->OperandList = 0;
 338   N->NumOperands = 0;
 339
 340   delete N;
 341 }
 342
 343 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
 344 /// correspond to it.  This is useful when we're about to delete or repurpose
 345 /// the node.  We don't want future request for structurally identical nodes
 346 /// to return N anymore.
 347 void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
 348   bool Erased = false;
 349   switch (N->getOpcode()) {
 350   case ISD::HANDLENODE: return;  // noop.
 351   case ISD::STRING:
 352     Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue());
 353     break;
 354   case ISD::CONDCODE:
 355     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
 356            "Cond code doesn't exist!");
 357     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
 358     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
 359     break;
 360   case ISD::ExternalSymbol:
 361     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 362     break;
 363   case ISD::TargetExternalSymbol:
 364     Erased =
 365       TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 366     break;
 367   case ISD::VALUETYPE:
 368     Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0;
 369     ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0;
 370     break;
 371   default:
 372     // Remove it from the CSE Map.
 373     Erased = CSEMap.RemoveNode(N);
 374     break;
 375   }
 376 #ifndef NDEBUG
 377   // Verify that the node was actually in one of the CSE maps, unless it has a
 378   // flag result (which cannot be CSE'd) or is one of the special cases that are
 379   // not subject to CSE.
 380   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag &&
 381       !N->isTargetOpcode()) {
 382     N->dump();
 383     std::cerr << "\n";
 384     assert(0 && "Node is not in map!");
 385   }
 386 #endif
 387 }
 388
 389 /// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps.  It
 390 /// has been taken out and modified in some way.  If the specified node already
 391 /// exists in the CSE maps, do not modify the maps, but return the existing node
 392 /// instead.  If it doesn't exist, add it and return null.
 393 ///
 394 SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
 395   assert(N->getNumOperands() && "This is a leaf node!");
 396   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 397     return 0;    // Never add these nodes.
 398
 399   // Check that remaining values produced are not flags.
 400   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 401     if (N->getValueType(i) == MVT::Flag)
 402       return 0;   // Never CSE anything that produces a flag.
 403
 404   SDNode *New = CSEMap.GetOrInsertNode(N);
 405   if (New != N) return New;  // Node already existed.
 406   return 0;
 407 }
 408
 409 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 410 /// were replaced with those specified.  If this node is never memoized,
 411 /// return null, otherwise return a pointer to the slot it would take.  If a
 412 /// node already exists with these operands, the slot will be non-null.
 413 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op,
 414                                            void *&InsertPos) {
 415   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 416     return 0;    // Never add these nodes.
 417
 418   // Check that remaining values produced are not flags.
 419   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 420     if (N->getValueType(i) == MVT::Flag)
 421       return 0;   // Never CSE anything that produces a flag.
 422
 423   SelectionDAGCSEMap::NodeID ID;
 424   ID.SetOpcode(N->getOpcode());
 425   ID.SetValueTypes(N->getVTList());
 426   ID.SetOperands(Op);
 427   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 428 }
 429
 430 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 431 /// were replaced with those specified.  If this node is never memoized,
 432 /// return null, otherwise return a pointer to the slot it would take.  If a
 433 /// node already exists with these operands, the slot will be non-null.
 434 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
 435                                            SDOperand Op1, SDOperand Op2,
 436                                            void *&InsertPos) {
 437   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 438     return 0;    // Never add these nodes.
 439
 440   // Check that remaining values produced are not flags.
 441   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 442     if (N->getValueType(i) == MVT::Flag)
 443       return 0;   // Never CSE anything that produces a flag.
 444
 445   SelectionDAGCSEMap::NodeID ID;
 446   ID.SetOpcode(N->getOpcode());
 447   ID.SetValueTypes(N->getVTList());
 448   ID.SetOperands(Op1, Op2);
 449   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 450 }
 451
 452
 453 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 454 /// were replaced with those specified.  If this node is never memoized,
 455 /// return null, otherwise return a pointer to the slot it would take.  If a
 456 /// node already exists with these operands, the slot will be non-null.
 457 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
 458                                            const SDOperand *Ops,unsigned NumOps,
 459                                            void *&InsertPos) {
 460   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 461     return 0;    // Never add these nodes.
 462
 463   // Check that remaining values produced are not flags.
 464   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 465     if (N->getValueType(i) == MVT::Flag)
 466       return 0;   // Never CSE anything that produces a flag.
 467
 468   SelectionDAGCSEMap::NodeID ID;
 469   ID.SetOpcode(N->getOpcode());
 470   ID.SetValueTypes(N->getVTList());
 471   ID.SetOperands(Ops, NumOps);
 472   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 473 }
 474
 475
 476 SelectionDAG::~SelectionDAG() {
 477   while (!AllNodes.empty()) {
 478     SDNode *N = AllNodes.begin();
 479     N->SetNextInBucket(0);
 480     delete [] N->OperandList;
 481     N->OperandList = 0;
 482     N->NumOperands = 0;
 483     AllNodes.pop_front();
 484   }
 485 }
 486
 487 SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) {
 488   if (Op.getValueType() == VT) return Op;
 489   int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT));
 490   return getNode(ISD::AND, Op.getValueType(), Op,
 491                  getConstant(Imm, Op.getValueType()));
 492 }
 493
 494 SDOperand SelectionDAG::getString(const std::string &Val) {
 495   StringSDNode *&N = StringNodes[Val];
 496   if (!N) {
 497     N = new StringSDNode(Val);
 498     AllNodes.push_back(N);
 499   }
 500   return SDOperand(N, 0);
 501 }
 502
 503 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT, bool isT) {
 504   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 505   assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!");
 506
 507   // Mask out any bits that are not valid for this constant.
 508   Val &= MVT::getIntVTBitMask(VT);
 509
 510   unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
 511   SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
 512   ID.AddInteger(Val);
 513   void *IP = 0;
 514   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 515     return SDOperand(E, 0);
 516   SDNode *N = new ConstantSDNode(isT, Val, VT);
 517   CSEMap.InsertNode(N, IP);
 518   AllNodes.push_back(N);
 519   return SDOperand(N, 0);
 520 }
 521
 522
 523 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT,
 524                                       bool isTarget) {
 525   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
 526   if (VT == MVT::f32)
 527     Val = (float)Val;  // Mask out extra precision.
 528
 529   // Do the map lookup using the actual bit pattern for the floating point
 530   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
 531   // we don't have issues with SNANs.
 532   unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
 533   SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
 534   ID.AddInteger(DoubleToBits(Val));
 535   void *IP = 0;
 536   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 537     return SDOperand(E, 0);
 538   SDNode *N = new ConstantFPSDNode(isTarget, Val, VT);
 539   CSEMap.InsertNode(N, IP);
 540   AllNodes.push_back(N);
 541   return SDOperand(N, 0);
 542 }
 543
 544 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 545                                          MVT::ValueType VT, int Offset,
 546                                          bool isTargetGA) {
 547   unsigned Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
 548   SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
 549   ID.AddPointer(GV);
 550   ID.AddInteger(Offset);
 551   void *IP = 0;
 552   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 553    return SDOperand(E, 0);
 554   SDNode *N = new GlobalAddressSDNode(isTargetGA, GV, VT, Offset);
 555   CSEMap.InsertNode(N, IP);
 556   AllNodes.push_back(N);
 557   return SDOperand(N, 0);
 558 }
 559
 560 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT,
 561                                       bool isTarget) {
 562   unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
 563   SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
 564   ID.AddInteger(FI);
 565   void *IP = 0;
 566   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 567     return SDOperand(E, 0);
 568   SDNode *N = new FrameIndexSDNode(FI, VT, isTarget);
 569   CSEMap.InsertNode(N, IP);
 570   AllNodes.push_back(N);
 571   return SDOperand(N, 0);
 572 }
 573
 574 SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){
 575   unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
 576   SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
 577   ID.AddInteger(JTI);
 578   void *IP = 0;
 579   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 580     return SDOperand(E, 0);
 581   SDNode *N = new JumpTableSDNode(JTI, VT, isTarget);
 582   CSEMap.InsertNode(N, IP);
 583   AllNodes.push_back(N);
 584   return SDOperand(N, 0);
 585 }
 586
 587 SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT,
 588                                         unsigned Alignment, int Offset,
 589                                         bool isTarget) {
 590   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
 591   SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT));
 592   ID.AddInteger(Alignment);
 593   ID.AddInteger(Offset);
 594   ID.AddPointer(C);
 595   void *IP = 0;
 596   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 597     return SDOperand(E, 0);
 598   SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
 599   CSEMap.InsertNode(N, IP);
 600   AllNodes.push_back(N);
 601   return SDOperand(N, 0);
 602 }
 603
 604
 605 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
 606   SelectionDAGCSEMap::NodeID ID(ISD::BasicBlock, getVTList(MVT::Other));
 607   ID.AddPointer(MBB);
 608   void *IP = 0;
 609   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 610     return SDOperand(E, 0);
 611   SDNode *N = new BasicBlockSDNode(MBB);
 612   CSEMap.InsertNode(N, IP);
 613   AllNodes.push_back(N);
 614   return SDOperand(N, 0);
 615 }
 616
 617 SDOperand SelectionDAG::getValueType(MVT::ValueType VT) {
 618   if ((unsigned)VT >= ValueTypeNodes.size())
 619     ValueTypeNodes.resize(VT+1);
 620   if (ValueTypeNodes[VT] == 0) {
 621     ValueTypeNodes[VT] = new VTSDNode(VT);
 622     AllNodes.push_back(ValueTypeNodes[VT]);
 623   }
 624
 625   return SDOperand(ValueTypeNodes[VT], 0);
 626 }
 627
 628 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
 629   SDNode *&N = ExternalSymbols[Sym];
 630   if (N) return SDOperand(N, 0);
 631   N = new ExternalSymbolSDNode(false, Sym, VT);
 632   AllNodes.push_back(N);
 633   return SDOperand(N, 0);
 634 }
 635
 636 SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym,
 637                                                 MVT::ValueType VT) {
 638   SDNode *&N = TargetExternalSymbols[Sym];
 639   if (N) return SDOperand(N, 0);
 640   N = new ExternalSymbolSDNode(true, Sym, VT);
 641   AllNodes.push_back(N);
 642   return SDOperand(N, 0);
 643 }
 644
 645 SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
 646   if ((unsigned)Cond >= CondCodeNodes.size())
 647     CondCodeNodes.resize(Cond+1);
 648
 649   if (CondCodeNodes[Cond] == 0) {
 650     CondCodeNodes[Cond] = new CondCodeSDNode(Cond);
 651     AllNodes.push_back(CondCodeNodes[Cond]);
 652   }
 653   return SDOperand(CondCodeNodes[Cond], 0);
 654 }
 655
 656 SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) {
 657   SelectionDAGCSEMap::NodeID ID(ISD::Register, getVTList(VT));
 658   ID.AddInteger(RegNo);
 659   void *IP = 0;
 660   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 661     return SDOperand(E, 0);
 662   SDNode *N = new RegisterSDNode(RegNo, VT);
 663   CSEMap.InsertNode(N, IP);
 664   AllNodes.push_back(N);
 665   return SDOperand(N, 0);
 666 }
 667
 668 SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) {
 669   assert((!V || isa<PointerType>(V->getType())) &&
 670          "SrcValue is not a pointer?");
 671
 672   SelectionDAGCSEMap::NodeID ID(ISD::SRCVALUE, getVTList(MVT::Other));
 673   ID.AddPointer(V);
 674   ID.AddInteger(Offset);
 675   void *IP = 0;
 676   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 677     return SDOperand(E, 0);
 678   SDNode *N = new SrcValueSDNode(V, Offset);
 679   CSEMap.InsertNode(N, IP);
 680   AllNodes.push_back(N);
 681   return SDOperand(N, 0);
 682 }
 683
 684 SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1,
 685                                       SDOperand N2, ISD::CondCode Cond) {
 686   // These setcc operations always fold.
 687   switch (Cond) {
 688   default: break;
 689   case ISD::SETFALSE:
 690   case ISD::SETFALSE2: return getConstant(0, VT);
 691   case ISD::SETTRUE:
 692   case ISD::SETTRUE2:  return getConstant(1, VT);
 693
 694   case ISD::SETOEQ:
 695   case ISD::SETOGT:
 696   case ISD::SETOGE:
 697   case ISD::SETOLT:
 698   case ISD::SETOLE:
 699   case ISD::SETONE:
 700   case ISD::SETO:
 701   case ISD::SETUO:
 702   case ISD::SETUEQ:
 703   case ISD::SETUNE:
 704     assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!");
 705     break;
 706   }
 707
 708   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
 709     uint64_t C2 = N2C->getValue();
 710     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
 711       uint64_t C1 = N1C->getValue();
 712
 713       // Sign extend the operands if required
 714       if (ISD::isSignedIntSetCC(Cond)) {
 715         C1 = N1C->getSignExtended();
 716         C2 = N2C->getSignExtended();
 717       }
 718
 719       switch (Cond) {
 720       default: assert(0 && "Unknown integer setcc!");
 721       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
 722       case ISD::SETNE:  return getConstant(C1 != C2, VT);
 723       case ISD::SETULT: return getConstant(C1 <  C2, VT);
 724       case ISD::SETUGT: return getConstant(C1 >  C2, VT);
 725       case ISD::SETULE: return getConstant(C1 <= C2, VT);
 726       case ISD::SETUGE: return getConstant(C1 >= C2, VT);
 727       case ISD::SETLT:  return getConstant((int64_t)C1 <  (int64_t)C2, VT);
 728       case ISD::SETGT:  return getConstant((int64_t)C1 >  (int64_t)C2, VT);
 729       case ISD::SETLE:  return getConstant((int64_t)C1 <= (int64_t)C2, VT);
 730       case ISD::SETGE:  return getConstant((int64_t)C1 >= (int64_t)C2, VT);
 731       }
 732     } else {
 733       // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
 734       if (N1.getOpcode() == ISD::ZERO_EXTEND) {
 735         unsigned InSize = MVT::getSizeInBits(N1.getOperand(0).getValueType());
 736
 737         // If the comparison constant has bits in the upper part, the
 738         // zero-extended value could never match.
 739         if (C2 & (~0ULL << InSize)) {
 740           unsigned VSize = MVT::getSizeInBits(N1.getValueType());
 741           switch (Cond) {
 742           case ISD::SETUGT:
 743           case ISD::SETUGE:
 744           case ISD::SETEQ: return getConstant(0, VT);
 745           case ISD::SETULT:
 746           case ISD::SETULE:
 747           case ISD::SETNE: return getConstant(1, VT);
 748           case ISD::SETGT:
 749           case ISD::SETGE:
 750             // True if the sign bit of C2 is set.
 751             return getConstant((C2 & (1ULL << VSize)) != 0, VT);
 752           case ISD::SETLT:
 753           case ISD::SETLE:
 754             // True if the sign bit of C2 isn't set.
 755             return getConstant((C2 & (1ULL << VSize)) == 0, VT);
 756           default:
 757             break;
 758           }
 759         }
 760
 761         // Otherwise, we can perform the comparison with the low bits.
 762         switch (Cond) {
 763         case ISD::SETEQ:
 764         case ISD::SETNE:
 765         case ISD::SETUGT:
 766         case ISD::SETUGE:
 767         case ISD::SETULT:
 768         case ISD::SETULE:
 769           return getSetCC(VT, N1.getOperand(0),
 770                           getConstant(C2, N1.getOperand(0).getValueType()),
 771                           Cond);
 772         default:
 773           break;   // todo, be more careful with signed comparisons
 774         }
 775       } else if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG &&
 776                  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
 777         MVT::ValueType ExtSrcTy = cast<VTSDNode>(N1.getOperand(1))->getVT();
 778         unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
 779         MVT::ValueType ExtDstTy = N1.getValueType();
 780         unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
 781
 782         // If the extended part has any inconsistent bits, it cannot ever
 783         // compare equal.  In other words, they have to be all ones or all
 784         // zeros.
 785         uint64_t ExtBits =
 786           (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
 787         if ((C2 & ExtBits) != 0 && (C2 & ExtBits) != ExtBits)
 788           return getConstant(Cond == ISD::SETNE, VT);
 789
 790         // Otherwise, make this a use of a zext.
 791         return getSetCC(VT, getZeroExtendInReg(N1.getOperand(0), ExtSrcTy),
 792                         getConstant(C2 & (~0ULL>>(64-ExtSrcTyBits)), ExtDstTy),
 793                         Cond);
 794       }
 795
 796       uint64_t MinVal, MaxVal;
 797       unsigned OperandBitSize = MVT::getSizeInBits(N2C->getValueType(0));
 798       if (ISD::isSignedIntSetCC(Cond)) {
 799         MinVal = 1ULL << (OperandBitSize-1);
 800         if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
 801           MaxVal = ~0ULL >> (65-OperandBitSize);
 802         else
 803           MaxVal = 0;
 804       } else {
 805         MinVal = 0;
 806         MaxVal = ~0ULL >> (64-OperandBitSize);
 807       }
 808
 809       // Canonicalize GE/LE comparisons to use GT/LT comparisons.
 810       if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
 811         if (C2 == MinVal) return getConstant(1, VT);   // X >= MIN --> true
 812         --C2;                                          // X >= C1 --> X > (C1-1)
 813         return getSetCC(VT, N1, getConstant(C2, N2.getValueType()),
 814                         (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
 815       }
 816
 817       if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
 818         if (C2 == MaxVal) return getConstant(1, VT);   // X <= MAX --> true
 819         ++C2;                                          // X <= C1 --> X < (C1+1)
 820         return getSetCC(VT, N1, getConstant(C2, N2.getValueType()),
 821                         (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
 822       }
 823
 824       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal)
 825         return getConstant(0, VT);      // X < MIN --> false
 826
 827       // Canonicalize setgt X, Min --> setne X, Min
 828       if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MinVal)
 829         return getSetCC(VT, N1, N2, ISD::SETNE);
 830
 831       // If we have setult X, 1, turn it into seteq X, 0
 832       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal+1)
 833         return getSetCC(VT, N1, getConstant(MinVal, N1.getValueType()),
 834                         ISD::SETEQ);
 835       // If we have setugt X, Max-1, turn it into seteq X, Max
 836       else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MaxVal-1)
 837         return getSetCC(VT, N1, getConstant(MaxVal, N1.getValueType()),
 838                         ISD::SETEQ);
 839
 840       // If we have "setcc X, C1", check to see if we can shrink the immediate
 841       // by changing cc.
 842
 843       // SETUGT X, SINTMAX  -> SETLT X, 0
 844       if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
 845           C2 == (~0ULL >> (65-OperandBitSize)))
 846         return getSetCC(VT, N1, getConstant(0, N2.getValueType()), ISD::SETLT);
 847
 848       // FIXME: Implement the rest of these.
 849
 850
 851       // Fold bit comparisons when we can.
 852       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
 853           VT == N1.getValueType() && N1.getOpcode() == ISD::AND)
 854         if (ConstantSDNode *AndRHS =
 855                     dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
 856           if (Cond == ISD::SETNE && C2 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
 857             // Perform the xform if the AND RHS is a single bit.
 858             if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
 859               return getNode(ISD::SRL, VT, N1,
 860                              getConstant(Log2_64(AndRHS->getValue()),
 861                                                    TLI.getShiftAmountTy()));
 862             }
 863           } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) {
 864             // (X & 8) == 8  -->  (X & 8) >> 3
 865             // Perform the xform if C2 is a single bit.
 866             if ((C2 & (C2-1)) == 0) {
 867               return getNode(ISD::SRL, VT, N1,
 868                              getConstant(Log2_64(C2),TLI.getShiftAmountTy()));
 869             }
 870           }
 871         }
 872     }
 873   } else if (isa<ConstantSDNode>(N1.Val)) {
 874       // Ensure that the constant occurs on the RHS.
 875     return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
 876   }
 877
 878   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
 879     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
 880       double C1 = N1C->getValue(), C2 = N2C->getValue();
 881
 882       switch (Cond) {
 883       default: break; // FIXME: Implement the rest of these!
 884       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
 885       case ISD::SETNE:  return getConstant(C1 != C2, VT);
 886       case ISD::SETLT:  return getConstant(C1 < C2, VT);
 887       case ISD::SETGT:  return getConstant(C1 > C2, VT);
 888       case ISD::SETLE:  return getConstant(C1 <= C2, VT);
 889       case ISD::SETGE:  return getConstant(C1 >= C2, VT);
 890       }
 891     } else {
 892       // Ensure that the constant occurs on the RHS.
 893       return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
 894     }
 895
 896   // Could not fold it.
 897   return SDOperand();
 898 }
 899
 900 /// getNode - Gets or creates the specified node.
 901 ///
 902 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
 903   SelectionDAGCSEMap::NodeID ID(Opcode, getVTList(VT));
 904   void *IP = 0;
 905   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 906     return SDOperand(E, 0);
 907   SDNode *N = new SDNode(Opcode, VT);
 908   CSEMap.InsertNode(N, IP);
 909
 910   AllNodes.push_back(N);
 911   return SDOperand(N, 0);
 912 }
 913
 914 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 915                                 SDOperand Operand) {
 916   unsigned Tmp1;
 917   // Constant fold unary operations with an integer constant operand.
 918   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
 919     uint64_t Val = C->getValue();
 920     switch (Opcode) {
 921     default: break;
 922     case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
 923     case ISD::ANY_EXTEND:
 924     case ISD::ZERO_EXTEND: return getConstant(Val, VT);
 925     case ISD::TRUNCATE:    return getConstant(Val, VT);
 926     case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
 927     case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
 928     case ISD::BIT_CONVERT:
 929       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
 930         return getConstantFP(BitsToFloat(Val), VT);
 931       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
 932         return getConstantFP(BitsToDouble(Val), VT);
 933       break;
 934     case ISD::BSWAP:
 935       switch(VT) {
 936       default: assert(0 && "Invalid bswap!"); break;
 937       case MVT::i16: return getConstant(ByteSwap_16((unsigned short)Val), VT);
 938       case MVT::i32: return getConstant(ByteSwap_32((unsigned)Val), VT);
 939       case MVT::i64: return getConstant(ByteSwap_64(Val), VT);
 940       }
 941       break;
 942     case ISD::CTPOP:
 943       switch(VT) {
 944       default: assert(0 && "Invalid ctpop!"); break;
 945       case MVT::i1: return getConstant(Val != 0, VT);
 946       case MVT::i8:
 947         Tmp1 = (unsigned)Val & 0xFF;
 948         return getConstant(CountPopulation_32(Tmp1), VT);
 949       case MVT::i16:
 950         Tmp1 = (unsigned)Val & 0xFFFF;
 951         return getConstant(CountPopulation_32(Tmp1), VT);
 952       case MVT::i32:
 953         return getConstant(CountPopulation_32((unsigned)Val), VT);
 954       case MVT::i64:
 955         return getConstant(CountPopulation_64(Val), VT);
 956       }
 957     case ISD::CTLZ:
 958       switch(VT) {
 959       default: assert(0 && "Invalid ctlz!"); break;
 960       case MVT::i1: return getConstant(Val == 0, VT);
 961       case MVT::i8:
 962         Tmp1 = (unsigned)Val & 0xFF;
 963         return getConstant(CountLeadingZeros_32(Tmp1)-24, VT);
 964       case MVT::i16:
 965         Tmp1 = (unsigned)Val & 0xFFFF;
 966         return getConstant(CountLeadingZeros_32(Tmp1)-16, VT);
 967       case MVT::i32:
 968         return getConstant(CountLeadingZeros_32((unsigned)Val), VT);
 969       case MVT::i64:
 970         return getConstant(CountLeadingZeros_64(Val), VT);
 971       }
 972     case ISD::CTTZ:
 973       switch(VT) {
 974       default: assert(0 && "Invalid cttz!"); break;
 975       case MVT::i1: return getConstant(Val == 0, VT);
 976       case MVT::i8:
 977         Tmp1 = (unsigned)Val | 0x100;
 978         return getConstant(CountTrailingZeros_32(Tmp1), VT);
 979       case MVT::i16:
 980         Tmp1 = (unsigned)Val | 0x10000;
 981         return getConstant(CountTrailingZeros_32(Tmp1), VT);
 982       case MVT::i32:
 983         return getConstant(CountTrailingZeros_32((unsigned)Val), VT);
 984       case MVT::i64:
 985         return getConstant(CountTrailingZeros_64(Val), VT);
 986       }
 987     }
 988   }
 989
 990   // Constant fold unary operations with an floating point constant operand.
 991   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
 992     switch (Opcode) {
 993     case ISD::FNEG:
 994       return getConstantFP(-C->getValue(), VT);
 995     case ISD::FABS:
 996       return getConstantFP(fabs(C->getValue()), VT);
 997     case ISD::FP_ROUND:
 998     case ISD::FP_EXTEND:
 999       return getConstantFP(C->getValue(), VT);
1000     case ISD::FP_TO_SINT:
1001       return getConstant((int64_t)C->getValue(), VT);
1002     case ISD::FP_TO_UINT:
1003       return getConstant((uint64_t)C->getValue(), VT);
1004     case ISD::BIT_CONVERT:
1005       if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
1006         return getConstant(FloatToBits(C->getValue()), VT);
1007       else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
1008         return getConstant(DoubleToBits(C->getValue()), VT);
1009       break;
1010     }
1011
1012   unsigned OpOpcode = Operand.Val->getOpcode();
1013   switch (Opcode) {
1014   case ISD::TokenFactor:
1015     return Operand;         // Factor of one node?  No factor.
1016   case ISD::SIGN_EXTEND:
1017     if (Operand.getValueType() == VT) return Operand;   // noop extension
1018     assert(Operand.getValueType() < VT && "Invalid sext node, dst < src!");
1019     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
1020       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1021     break;
1022   case ISD::ZERO_EXTEND:
1023     if (Operand.getValueType() == VT) return Operand;   // noop extension
1024     assert(Operand.getValueType() < VT && "Invalid zext node, dst < src!");
1025     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
1026       return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
1027     break;
1028   case ISD::ANY_EXTEND:
1029     if (Operand.getValueType() == VT) return Operand;   // noop extension
1030     assert(Operand.getValueType() < VT && "Invalid anyext node, dst < src!");
1031     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND)
1032       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
1033       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1034     break;
1035   case ISD::TRUNCATE:
1036     if (Operand.getValueType() == VT) return Operand;   // noop truncate
1037     assert(Operand.getValueType() > VT && "Invalid truncate node, src < dst!");
1038     if (OpOpcode == ISD::TRUNCATE)
1039       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1040     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
1041              OpOpcode == ISD::ANY_EXTEND) {
1042       // If the source is smaller than the dest, we still need an extend.
1043       if (Operand.Val->getOperand(0).getValueType() < VT)
1044         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1045       else if (Operand.Val->getOperand(0).getValueType() > VT)
1046         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1047       else
1048         return Operand.Val->getOperand(0);
1049     }
1050     break;
1051   case ISD::BIT_CONVERT:
1052     // Basic sanity checking.
1053     assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType())
1054            && "Cannot BIT_CONVERT between two different types!");
1055     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
1056     if (OpOpcode == ISD::BIT_CONVERT)  // bitconv(bitconv(x)) -> bitconv(x)
1057       return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0));
1058     if (OpOpcode == ISD::UNDEF)
1059       return getNode(ISD::UNDEF, VT);
1060     break;
1061   case ISD::SCALAR_TO_VECTOR:
1062     assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) &&
1063            MVT::getVectorBaseType(VT) == Operand.getValueType() &&
1064            "Illegal SCALAR_TO_VECTOR node!");
1065     break;
1066   case ISD::FNEG:
1067     if (OpOpcode == ISD::FSUB)   // -(X-Y) -> (Y-X)
1068       return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1),
1069                      Operand.Val->getOperand(0));
1070     if (OpOpcode == ISD::FNEG)  // --X -> X
1071       return Operand.Val->getOperand(0);
1072     break;
1073   case ISD::FABS:
1074     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
1075       return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
1076     break;
1077   }
1078
1079   SDNode *N;
1080   SDVTList VTs = getVTList(VT);
1081   if (VT != MVT::Flag) { // Don't CSE flag producing nodes
1082     SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Operand);
1083     void *IP = 0;
1084     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1085       return SDOperand(E, 0);
1086     N = new SDNode(Opcode, Operand);
1087     N->setValueTypes(VTs);
1088     CSEMap.InsertNode(N, IP);
1089   } else {
1090     N = new SDNode(Opcode, Operand);
1091     N->setValueTypes(VTs);
1092   }
1093   AllNodes.push_back(N);
1094   return SDOperand(N, 0);
1095 }
1096
1097
1098
1099 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1100                                 SDOperand N1, SDOperand N2) {
1101 #ifndef NDEBUG
1102   switch (Opcode) {
1103   case ISD::TokenFactor:
1104     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
1105            N2.getValueType() == MVT::Other && "Invalid token factor!");
1106     break;
1107   case ISD::AND:
1108   case ISD::OR:
1109   case ISD::XOR:
1110   case ISD::UDIV:
1111   case ISD::UREM:
1112   case ISD::MULHU:
1113   case ISD::MULHS:
1114     assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
1115     // fall through
1116   case ISD::ADD:
1117   case ISD::SUB:
1118   case ISD::MUL:
1119   case ISD::SDIV:
1120   case ISD::SREM:
1121     assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops");
1122     // fall through.
1123   case ISD::FADD:
1124   case ISD::FSUB:
1125   case ISD::FMUL:
1126   case ISD::FDIV:
1127   case ISD::FREM:
1128     assert(N1.getValueType() == N2.getValueType() &&
1129            N1.getValueType() == VT && "Binary operator types must match!");
1130     break;
1131   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
1132     assert(N1.getValueType() == VT &&
1133            MVT::isFloatingPoint(N1.getValueType()) &&
1134            MVT::isFloatingPoint(N2.getValueType()) &&
1135            "Invalid FCOPYSIGN!");
1136     break;
1137   case ISD::SHL:
1138   case ISD::SRA:
1139   case ISD::SRL:
1140   case ISD::ROTL:
1141   case ISD::ROTR:
1142     assert(VT == N1.getValueType() &&
1143            "Shift operators return type must be the same as their first arg");
1144     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
1145            VT != MVT::i1 && "Shifts only work on integers");
1146     break;
1147   case ISD::FP_ROUND_INREG: {
1148     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1149     assert(VT == N1.getValueType() && "Not an inreg round!");
1150     assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
1151            "Cannot FP_ROUND_INREG integer types");
1152     assert(EVT <= VT && "Not rounding down!");
1153     break;
1154   }
1155   case ISD::AssertSext:
1156   case ISD::AssertZext:
1157   case ISD::SIGN_EXTEND_INREG: {
1158     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1159     assert(VT == N1.getValueType() && "Not an inreg extend!");
1160     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
1161            "Cannot *_EXTEND_INREG FP types");
1162     assert(EVT <= VT && "Not extending!");
1163   }
1164
1165   default: break;
1166   }
1167 #endif
1168
1169   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1170   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1171   if (N1C) {
1172     if (Opcode == ISD::SIGN_EXTEND_INREG) {
1173       int64_t Val = N1C->getValue();
1174       unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT());
1175       Val <<= 64-FromBits;
1176       Val >>= 64-FromBits;
1177       return getConstant(Val, VT);
1178     }
1179
1180     if (N2C) {
1181       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
1182       switch (Opcode) {
1183       case ISD::ADD: return getConstant(C1 + C2, VT);
1184       case ISD::SUB: return getConstant(C1 - C2, VT);
1185       case ISD::MUL: return getConstant(C1 * C2, VT);
1186       case ISD::UDIV:
1187         if (C2) return getConstant(C1 / C2, VT);
1188         break;
1189       case ISD::UREM :
1190         if (C2) return getConstant(C1 % C2, VT);
1191         break;
1192       case ISD::SDIV :
1193         if (C2) return getConstant(N1C->getSignExtended() /
1194                                    N2C->getSignExtended(), VT);
1195         break;
1196       case ISD::SREM :
1197         if (C2) return getConstant(N1C->getSignExtended() %
1198                                    N2C->getSignExtended(), VT);
1199         break;
1200       case ISD::AND  : return getConstant(C1 & C2, VT);
1201       case ISD::OR   : return getConstant(C1 | C2, VT);
1202       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
1203       case ISD::SHL  : return getConstant(C1 << C2, VT);
1204       case ISD::SRL  : return getConstant(C1 >> C2, VT);
1205       case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
1206       case ISD::ROTL :
1207         return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)),
1208                            VT);
1209       case ISD::ROTR :
1210         return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)),
1211                            VT);
1212       default: break;
1213       }
1214     } else {      // Cannonicalize constant to RHS if commutative
1215       if (isCommutativeBinOp(Opcode)) {
1216         std::swap(N1C, N2C);
1217         std::swap(N1, N2);
1218       }
1219     }
1220   }
1221
1222   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
1223   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
1224   if (N1CFP) {
1225     if (N2CFP) {
1226       double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
1227       switch (Opcode) {
1228       case ISD::FADD: return getConstantFP(C1 + C2, VT);
1229       case ISD::FSUB: return getConstantFP(C1 - C2, VT);
1230       case ISD::FMUL: return getConstantFP(C1 * C2, VT);
1231       case ISD::FDIV:
1232         if (C2) return getConstantFP(C1 / C2, VT);
1233         break;
1234       case ISD::FREM :
1235         if (C2) return getConstantFP(fmod(C1, C2), VT);
1236         break;
1237       case ISD::FCOPYSIGN: {
1238         union {
1239           double   F;
1240           uint64_t I;
1241         } u1;
1242         union {
1243           double  F;
1244           int64_t I;
1245         } u2;
1246         u1.F = C1;
1247         u2.F = C2;
1248         if (u2.I < 0)  // Sign bit of RHS set?
1249           u1.I |= 1ULL << 63;      // Set the sign bit of the LHS.
1250         else
1251           u1.I &= (1ULL << 63)-1;  // Clear the sign bit of the LHS.
1252         return getConstantFP(u1.F, VT);
1253       }
1254       default: break;
1255       }
1256     } else {      // Cannonicalize constant to RHS if commutative
1257       if (isCommutativeBinOp(Opcode)) {
1258         std::swap(N1CFP, N2CFP);
1259         std::swap(N1, N2);
1260       }
1261     }
1262   }
1263
1264   // Canonicalize an UNDEF to the RHS, even over a constant.
1265   if (N1.getOpcode() == ISD::UNDEF) {
1266     if (isCommutativeBinOp(Opcode)) {
1267       std::swap(N1, N2);
1268     } else {
1269       switch (Opcode) {
1270       case ISD::FP_ROUND_INREG:
1271       case ISD::SIGN_EXTEND_INREG:
1272       case ISD::SUB:
1273       case ISD::FSUB:
1274       case ISD::FDIV:
1275       case ISD::FREM:
1276       case ISD::SRA:
1277         return N1;     // fold op(undef, arg2) -> undef
1278       case ISD::UDIV:
1279       case ISD::SDIV:
1280       case ISD::UREM:
1281       case ISD::SREM:
1282       case ISD::SRL:
1283       case ISD::SHL:
1284         return getConstant(0, VT);    // fold op(undef, arg2) -> 0
1285       }
1286     }
1287   }
1288
1289   // Fold a bunch of operators when the RHS is undef.
1290   if (N2.getOpcode() == ISD::UNDEF) {
1291     switch (Opcode) {
1292     case ISD::ADD:
1293     case ISD::SUB:
1294     case ISD::FADD:
1295     case ISD::FSUB:
1296     case ISD::FMUL:
1297     case ISD::FDIV:
1298     case ISD::FREM:
1299     case ISD::UDIV:
1300     case ISD::SDIV:
1301     case ISD::UREM:
1302     case ISD::SREM:
1303     case ISD::XOR:
1304       return N2;       // fold op(arg1, undef) -> undef
1305     case ISD::MUL:
1306     case ISD::AND:
1307     case ISD::SRL:
1308     case ISD::SHL:
1309       return getConstant(0, VT);  // fold op(arg1, undef) -> 0
1310     case ISD::OR:
1311       return getConstant(MVT::getIntVTBitMask(VT), VT);
1312     case ISD::SRA:
1313       return N1;
1314     }
1315   }
1316
1317   // Finally, fold operations that do not require constants.
1318   switch (Opcode) {
1319   case ISD::FP_ROUND_INREG:
1320     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
1321     break;
1322   case ISD::SIGN_EXTEND_INREG: {
1323     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1324     if (EVT == VT) return N1;  // Not actually extending
1325     break;
1326   }
1327
1328   // FIXME: figure out how to safely handle things like
1329   // int foo(int x) { return 1 << (x & 255); }
1330   // int bar() { return foo(256); }
1331 #if 0
1332   case ISD::SHL:
1333   case ISD::SRL:
1334   case ISD::SRA:
1335     if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1336         cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1)
1337       return getNode(Opcode, VT, N1, N2.getOperand(0));
1338     else if (N2.getOpcode() == ISD::AND)
1339       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) {
1340         // If the and is only masking out bits that cannot effect the shift,
1341         // eliminate the and.
1342         unsigned NumBits = MVT::getSizeInBits(VT);
1343         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1344           return getNode(Opcode, VT, N1, N2.getOperand(0));
1345       }
1346     break;
1347 #endif
1348   }
1349
1350   // Memoize this node if possible.
1351   SDNode *N;
1352   SDVTList VTs = getVTList(VT);
1353   if (VT != MVT::Flag) {
1354     SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2);
1355     void *IP = 0;
1356     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1357       return SDOperand(E, 0);
1358     N = new SDNode(Opcode, N1, N2);
1359     N->setValueTypes(VTs);
1360     CSEMap.InsertNode(N, IP);
1361   } else {
1362     N = new SDNode(Opcode, N1, N2);
1363     N->setValueTypes(VTs);
1364   }
1365
1366   AllNodes.push_back(N);
1367   return SDOperand(N, 0);
1368 }
1369
1370 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1371                                 SDOperand N1, SDOperand N2, SDOperand N3) {
1372   // Perform various simplifications.
1373   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1374   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1375   //ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
1376   switch (Opcode) {
1377   case ISD::SETCC: {
1378     // Use SimplifySetCC  to simplify SETCC's.
1379     SDOperand Simp = SimplifySetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
1380     if (Simp.Val) return Simp;
1381     break;
1382   }
1383   case ISD::SELECT:
1384     if (N1C)
1385       if (N1C->getValue())
1386         return N2;             // select true, X, Y -> X
1387       else
1388         return N3;             // select false, X, Y -> Y
1389
1390     if (N2 == N3) return N2;   // select C, X, X -> X
1391     break;
1392   case ISD::BRCOND:
1393     if (N2C)
1394       if (N2C->getValue()) // Unconditional branch
1395         return getNode(ISD::BR, MVT::Other, N1, N3);
1396       else
1397         return N1;         // Never-taken branch
1398     break;
1399   case ISD::VECTOR_SHUFFLE:
1400     assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1401            MVT::isVector(VT) && MVT::isVector(N3.getValueType()) &&
1402            N3.getOpcode() == ISD::BUILD_VECTOR &&
1403            MVT::getVectorNumElements(VT) == N3.getNumOperands() &&
1404            "Illegal VECTOR_SHUFFLE node!");
1405     break;
1406   }
1407
1408   // Memoize node if it doesn't produce a flag.
1409   SDNode *N;
1410   SDVTList VTs = getVTList(VT);
1411   if (VT != MVT::Flag) {
1412     SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2, N3);
1413     void *IP = 0;
1414     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1415       return SDOperand(E, 0);
1416     N = new SDNode(Opcode, N1, N2, N3);
1417     N->setValueTypes(VTs);
1418     CSEMap.InsertNode(N, IP);
1419   } else {
1420     N = new SDNode(Opcode, N1, N2, N3);
1421     N->setValueTypes(VTs);
1422   }
1423   AllNodes.push_back(N);
1424   return SDOperand(N, 0);
1425 }
1426
1427 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1428                                 SDOperand N1, SDOperand N2, SDOperand N3,
1429                                 SDOperand N4) {
1430   SDOperand Ops[] = { N1, N2, N3, N4 };
1431   return getNode(Opcode, VT, Ops, 4);
1432 }
1433
1434 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1435                                 SDOperand N1, SDOperand N2, SDOperand N3,
1436                                 SDOperand N4, SDOperand N5) {
1437   SDOperand Ops[] = { N1, N2, N3, N4, N5 };
1438   return getNode(Opcode, VT, Ops, 5);
1439 }
1440
1441 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
1442                                 SDOperand Chain, SDOperand Ptr,
1443                                 SDOperand SV) {
1444   SDVTList VTs = getVTList(VT, MVT::Other);
1445
1446   SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, SV);
1447   void *IP = 0;
1448   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1449     return SDOperand(E, 0);
1450   SDNode *N = new SDNode(ISD::LOAD, Chain, Ptr, SV);
1451   N->setValueTypes(VTs);
1452   CSEMap.InsertNode(N, IP);
1453   AllNodes.push_back(N);
1454   return SDOperand(N, 0);
1455 }
1456
1457 SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT,
1458                                    SDOperand Chain, SDOperand Ptr,
1459                                    SDOperand SV) {
1460   SDOperand Ops[] = { Chain, Ptr, SV, getConstant(Count, MVT::i32),
1461                       getValueType(EVT) };
1462   return getNode(ISD::VLOAD, getVTList(MVT::Vector, MVT::Other), Ops, 5);
1463 }
1464
1465 SDOperand SelectionDAG::getExtLoad(unsigned Opcode, MVT::ValueType VT,
1466                                    SDOperand Chain, SDOperand Ptr, SDOperand SV,
1467                                    MVT::ValueType EVT) {
1468   SDOperand Ops[] = { Chain, Ptr, SV, getValueType(EVT) };
1469   return getNode(Opcode, getVTList(VT, MVT::Other), Ops, 4);
1470 }
1471
1472 SDOperand SelectionDAG::getVAArg(MVT::ValueType VT,
1473                                  SDOperand Chain, SDOperand Ptr,
1474                                  SDOperand SV) {
1475   SDOperand Ops[] = { Chain, Ptr, SV };
1476   return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3);
1477 }
1478
1479 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1480                                 const SDOperand *Ops, unsigned NumOps) {
1481   switch (NumOps) {
1482   case 0: return getNode(Opcode, VT);
1483   case 1: return getNode(Opcode, VT, Ops[0]);
1484   case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
1485   case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
1486   default: break;
1487   }
1488
1489   switch (Opcode) {
1490   default: break;
1491   case ISD::TRUNCSTORE: {
1492     assert(NumOps == 5 && "TRUNCSTORE takes 5 operands!");
1493     MVT::ValueType EVT = cast<VTSDNode>(Ops[4])->getVT();
1494 #if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store
1495     // If this is a truncating store of a constant, convert to the desired type
1496     // and store it instead.
1497     if (isa<Constant>(Ops[0])) {
1498       SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1);
1499       if (isa<Constant>(Op))
1500         N1 = Op;
1501     }
1502     // Also for ConstantFP?
1503 #endif
1504     if (Ops[0].getValueType() == EVT)       // Normal store?
1505       return getNode(ISD::STORE, VT, Ops[0], Ops[1], Ops[2], Ops[3]);
1506     assert(Ops[1].getValueType() > EVT && "Not a truncation?");
1507     assert(MVT::isInteger(Ops[1].getValueType()) == MVT::isInteger(EVT) &&
1508            "Can't do FP-INT conversion!");
1509     break;
1510   }
1511   case ISD::SELECT_CC: {
1512     assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
1513     assert(Ops[0].getValueType() == Ops[1].getValueType() &&
1514            "LHS and RHS of condition must have same type!");
1515     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
1516            "True and False arms of SelectCC must have same type!");
1517     assert(Ops[2].getValueType() == VT &&
1518            "select_cc node must be of same type as true and false value!");
1519     break;
1520   }
1521   case ISD::BR_CC: {
1522     assert(NumOps == 5 && "BR_CC takes 5 operands!");
1523     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
1524            "LHS/RHS of comparison should match types!");
1525     break;
1526   }
1527   }
1528
1529   // Memoize nodes.
1530   SDNode *N;
1531   SDVTList VTs = getVTList(VT);
1532   if (VT != MVT::Flag) {
1533     SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Ops, NumOps);
1534     void *IP = 0;
1535     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1536       return SDOperand(E, 0);
1537     N = new SDNode(Opcode, Ops, NumOps);
1538     N->setValueTypes(VTs);
1539     CSEMap.InsertNode(N, IP);
1540   } else {
1541     N = new SDNode(Opcode, Ops, NumOps);
1542     N->setValueTypes(VTs);
1543   }
1544   AllNodes.push_back(N);
1545   return SDOperand(N, 0);
1546 }
1547
1548 SDOperand SelectionDAG::getNode(unsigned Opcode,
1549                                 std::vector<MVT::ValueType> &ResultTys,
1550                                 const SDOperand *Ops, unsigned NumOps) {
1551   return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(),
1552                  Ops, NumOps);
1553 }
1554
1555 SDOperand SelectionDAG::getNode(unsigned Opcode,
1556                                 const MVT::ValueType *VTs, unsigned NumVTs,
1557                                 const SDOperand *Ops, unsigned NumOps) {
1558   if (NumVTs == 1)
1559     return getNode(Opcode, VTs[0], Ops, NumOps);
1560   return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps);
1561 }
1562
1563 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
1564                                 const SDOperand *Ops, unsigned NumOps) {
1565   if (VTList.NumVTs == 1)
1566     return getNode(Opcode, VTList.VTs[0], Ops, NumOps);
1567
1568   switch (Opcode) {
1569   case ISD::EXTLOAD:
1570   case ISD::SEXTLOAD:
1571   case ISD::ZEXTLOAD: {
1572     MVT::ValueType EVT = cast<VTSDNode>(Ops[3])->getVT();
1573     assert(NumOps == 4 && VTList.NumVTs == 2 && "Bad *EXTLOAD!");
1574     // If they are asking for an extending load from/to the same thing, return a
1575     // normal load.
1576     if (VTList.VTs[0] == EVT)
1577       return getLoad(VTList.VTs[0], Ops[0], Ops[1], Ops[2]);
1578     if (MVT::isVector(VTList.VTs[0])) {
1579       assert(EVT == MVT::getVectorBaseType(VTList.VTs[0]) &&
1580              "Invalid vector extload!");
1581     } else {
1582       assert(EVT < VTList.VTs[0] &&
1583              "Should only be an extending load, not truncating!");
1584     }
1585     assert((Opcode == ISD::EXTLOAD || MVT::isInteger(VTList.VTs[0])) &&
1586            "Cannot sign/zero extend a FP/Vector load!");
1587     assert(MVT::isInteger(VTList.VTs[0]) == MVT::isInteger(EVT) &&
1588            "Cannot convert from FP to Int or Int -> FP!");
1589     break;
1590   }
1591
1592   // FIXME: figure out how to safely handle things like
1593   // int foo(int x) { return 1 << (x & 255); }
1594   // int bar() { return foo(256); }
1595 #if 0
1596   case ISD::SRA_PARTS:
1597   case ISD::SRL_PARTS:
1598   case ISD::SHL_PARTS:
1599     if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1600         cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
1601       return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1602     else if (N3.getOpcode() == ISD::AND)
1603       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
1604         // If the and is only masking out bits that cannot effect the shift,
1605         // eliminate the and.
1606         unsigned NumBits = MVT::getSizeInBits(VT)*2;
1607         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1608           return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1609       }
1610     break;
1611 #endif
1612   }
1613
1614   // Memoize the node unless it returns a flag.
1615   SDNode *N;
1616   if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
1617     SelectionDAGCSEMap::NodeID ID;
1618     ID.SetOpcode(Opcode);
1619     ID.SetValueTypes(VTList);
1620     ID.SetOperands(&Ops[0], NumOps);
1621     void *IP = 0;
1622     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1623       return SDOperand(E, 0);
1624     N = new SDNode(Opcode, Ops, NumOps);
1625     N->setValueTypes(VTList);
1626     CSEMap.InsertNode(N, IP);
1627   } else {
1628     N = new SDNode(Opcode, Ops, NumOps);
1629     N->setValueTypes(VTList);
1630   }
1631   AllNodes.push_back(N);
1632   return SDOperand(N, 0);
1633 }
1634
1635 SDVTList SelectionDAG::getVTList(MVT::ValueType VT) {
1636   return makeVTList(SDNode::getValueTypeList(VT), 1);
1637 }
1638
1639 SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2) {
1640   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
1641        E = VTList.end(); I != E; ++I) {
1642     if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2)
1643       return makeVTList(&(*I)[0], 2);
1644   }
1645   std::vector<MVT::ValueType> V;
1646   V.push_back(VT1);
1647   V.push_back(VT2);
1648   VTList.push_front(V);
1649   return makeVTList(&(*VTList.begin())[0], 2);
1650 }
1651 SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2,
1652                                  MVT::ValueType VT3) {
1653   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
1654        E = VTList.end(); I != E; ++I) {
1655     if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 &&
1656         (*I)[2] == VT3)
1657       return makeVTList(&(*I)[0], 3);
1658   }
1659   std::vector<MVT::ValueType> V;
1660   V.push_back(VT1);
1661   V.push_back(VT2);
1662   V.push_back(VT3);
1663   VTList.push_front(V);
1664   return makeVTList(&(*VTList.begin())[0], 3);
1665 }
1666
1667 SDVTList SelectionDAG::getVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
1668   switch (NumVTs) {
1669     case 0: assert(0 && "Cannot have nodes without results!");
1670     case 1: return makeVTList(SDNode::getValueTypeList(VTs[0]), 1);
1671     case 2: return getVTList(VTs[0], VTs[1]);
1672     case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
1673     default: break;
1674   }
1675
1676   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
1677        E = VTList.end(); I != E; ++I) {
1678     if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue;
1679
1680     bool NoMatch = false;
1681     for (unsigned i = 2; i != NumVTs; ++i)
1682       if (VTs[i] != (*I)[i]) {
1683         NoMatch = true;
1684         break;
1685       }
1686     if (!NoMatch)
1687       return makeVTList(&*I->begin(), NumVTs);
1688   }
1689
1690   VTList.push_front(std::vector<MVT::ValueType>(VTs, VTs+NumVTs));
1691   return makeVTList(&*VTList.begin()->begin(), NumVTs);
1692 }
1693
1694
1695 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
1696 /// specified operands.  If the resultant node already exists in the DAG,
1697 /// this does not modify the specified node, instead it returns the node that
1698 /// already exists.  If the resultant node does not exist in the DAG, the
1699 /// input node is returned.  As a degenerate case, if you specify the same
1700 /// input operands as the node already has, the input node is returned.
1701 SDOperand SelectionDAG::
1702 UpdateNodeOperands(SDOperand InN, SDOperand Op) {
1703   SDNode *N = InN.Val;
1704   assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
1705
1706   // Check to see if there is no change.
1707   if (Op == N->getOperand(0)) return InN;
1708
1709   // See if the modified node already exists.
1710   void *InsertPos = 0;
1711   if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
1712     return SDOperand(Existing, InN.ResNo);
1713
1714   // Nope it doesn't.  Remove the node from it's current place in the maps.
1715   if (InsertPos)
1716     RemoveNodeFromCSEMaps(N);
1717
1718   // Now we update the operands.
1719   N->OperandList[0].Val->removeUser(N);
1720   Op.Val->addUser(N);
1721   N->OperandList[0] = Op;
1722
1723   // If this gets put into a CSE map, add it.
1724   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
1725   return InN;
1726 }
1727
1728 SDOperand SelectionDAG::
1729 UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) {
1730   SDNode *N = InN.Val;
1731   assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
1732
1733   // Check to see if there is no change.
1734   bool AnyChange = false;
1735   if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
1736     return InN;   // No operands changed, just return the input node.
1737
1738   // See if the modified node already exists.
1739   void *InsertPos = 0;
1740   if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
1741     return SDOperand(Existing, InN.ResNo);
1742
1743   // Nope it doesn't.  Remove the node from it's current place in the maps.
1744   if (InsertPos)
1745     RemoveNodeFromCSEMaps(N);
1746
1747   // Now we update the operands.
1748   if (N->OperandList[0] != Op1) {
1749     N->OperandList[0].Val->removeUser(N);
1750     Op1.Val->addUser(N);
1751     N->OperandList[0] = Op1;
1752   }
1753   if (N->OperandList[1] != Op2) {
1754     N->OperandList[1].Val->removeUser(N);
1755     Op2.Val->addUser(N);
1756     N->OperandList[1] = Op2;
1757   }
1758
1759   // If this gets put into a CSE map, add it.
1760   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
1761   return InN;
1762 }
1763
1764 SDOperand SelectionDAG::
1765 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
1766   SDOperand Ops[] = { Op1, Op2, Op3 };
1767   return UpdateNodeOperands(N, Ops, 3);
1768 }
1769
1770 SDOperand SelectionDAG::
1771 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
1772                    SDOperand Op3, SDOperand Op4) {
1773   SDOperand Ops[] = { Op1, Op2, Op3, Op4 };
1774   return UpdateNodeOperands(N, Ops, 4);
1775 }
1776
1777 SDOperand SelectionDAG::
1778 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
1779                    SDOperand Op3, SDOperand Op4, SDOperand Op5) {
1780   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
1781   return UpdateNodeOperands(N, Ops, 5);
1782 }
1783
1784
1785 SDOperand SelectionDAG::
1786 UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) {
1787   SDNode *N = InN.Val;
1788   assert(N->getNumOperands() == NumOps &&
1789          "Update with wrong number of operands");
1790
1791   // Check to see if there is no change.
1792   bool AnyChange = false;
1793   for (unsigned i = 0; i != NumOps; ++i) {
1794     if (Ops[i] != N->getOperand(i)) {
1795       AnyChange = true;
1796       break;
1797     }
1798   }
1799
1800   // No operands changed, just return the input node.
1801   if (!AnyChange) return InN;
1802
1803   // See if the modified node already exists.
1804   void *InsertPos = 0;
1805   if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
1806     return SDOperand(Existing, InN.ResNo);
1807
1808   // Nope it doesn't.  Remove the node from it's current place in the maps.
1809   if (InsertPos)
1810     RemoveNodeFromCSEMaps(N);
1811
1812   // Now we update the operands.
1813   for (unsigned i = 0; i != NumOps; ++i) {
1814     if (N->OperandList[i] != Ops[i]) {
1815       N->OperandList[i].Val->removeUser(N);
1816       Ops[i].Val->addUser(N);
1817       N->OperandList[i] = Ops[i];
1818     }
1819   }
1820
1821   // If this gets put into a CSE map, add it.
1822   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
1823   return InN;
1824 }
1825
1826
1827
1828
1829 /// SelectNodeTo - These are used for target selectors to *mutate* the
1830 /// specified node to have the specified return type, Target opcode, and
1831 /// operands.  Note that target opcodes are stored as
1832 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
1833 ///
1834 /// Note that SelectNodeTo returns the resultant node.  If there is already a
1835 /// node of the specified opcode and operands, it returns that node instead of
1836 /// the current one.
1837 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1838                                      MVT::ValueType VT) {
1839   SDVTList VTs = getVTList(VT);
1840   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
1841   void *IP = 0;
1842   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1843     return SDOperand(ON, 0);
1844
1845   RemoveNodeFromCSEMaps(N);
1846
1847   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1848   N->setValueTypes(VTs);
1849
1850   CSEMap.InsertNode(N, IP);
1851   return SDOperand(N, 0);
1852 }
1853
1854 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1855                                      MVT::ValueType VT, SDOperand Op1) {
1856   // If an identical node already exists, use it.
1857   SDVTList VTs = getVTList(VT);
1858   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1);
1859   void *IP = 0;
1860   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1861     return SDOperand(ON, 0);
1862
1863   RemoveNodeFromCSEMaps(N);
1864   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1865   N->setValueTypes(VTs);
1866   N->setOperands(Op1);
1867   CSEMap.InsertNode(N, IP);
1868   return SDOperand(N, 0);
1869 }
1870
1871 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1872                                      MVT::ValueType VT, SDOperand Op1,
1873                                      SDOperand Op2) {
1874   // If an identical node already exists, use it.
1875   SDVTList VTs = getVTList(VT);
1876   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
1877   void *IP = 0;
1878   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1879     return SDOperand(ON, 0);
1880
1881   RemoveNodeFromCSEMaps(N);
1882   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1883   N->setValueTypes(VTs);
1884   N->setOperands(Op1, Op2);
1885
1886   CSEMap.InsertNode(N, IP);   // Memoize the new node.
1887   return SDOperand(N, 0);
1888 }
1889
1890 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1891                                      MVT::ValueType VT, SDOperand Op1,
1892                                      SDOperand Op2, SDOperand Op3) {
1893   // If an identical node already exists, use it.
1894   SDVTList VTs = getVTList(VT);
1895   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs,
1896                                 Op1, Op2, Op3);
1897   void *IP = 0;
1898   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1899     return SDOperand(ON, 0);
1900
1901   RemoveNodeFromCSEMaps(N);
1902   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1903   N->setValueTypes(VTs);
1904   N->setOperands(Op1, Op2, Op3);
1905
1906   CSEMap.InsertNode(N, IP);   // Memoize the new node.
1907   return SDOperand(N, 0);
1908 }
1909
1910 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1911                                      MVT::ValueType VT, SDOperand Op1,
1912                                      SDOperand Op2, SDOperand Op3,
1913                                      SDOperand Op4) {
1914   // If an identical node already exists, use it.
1915   SDVTList VTs = getVTList(VT);
1916   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
1917   ID.AddOperand(Op1);
1918   ID.AddOperand(Op2);
1919   ID.AddOperand(Op3);
1920   ID.AddOperand(Op4);
1921   void *IP = 0;
1922   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1923     return SDOperand(ON, 0);
1924
1925   RemoveNodeFromCSEMaps(N);
1926   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1927   N->setValueTypes(VTs);
1928   N->setOperands(Op1, Op2, Op3, Op4);
1929
1930   CSEMap.InsertNode(N, IP);   // Memoize the new node.
1931   return SDOperand(N, 0);
1932 }
1933
1934 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1935                                      MVT::ValueType VT, SDOperand Op1,
1936                                      SDOperand Op2, SDOperand Op3,
1937                                      SDOperand Op4, SDOperand Op5) {
1938   SDVTList VTs = getVTList(VT);
1939   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
1940   ID.AddOperand(Op1);
1941   ID.AddOperand(Op2);
1942   ID.AddOperand(Op3);
1943   ID.AddOperand(Op4);
1944   ID.AddOperand(Op5);
1945   void *IP = 0;
1946   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1947     return SDOperand(ON, 0);
1948
1949   RemoveNodeFromCSEMaps(N);
1950   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1951   N->setValueTypes(VTs);
1952   N->setOperands(Op1, Op2, Op3, Op4, Op5);
1953
1954   CSEMap.InsertNode(N, IP);   // Memoize the new node.
1955   return SDOperand(N, 0);
1956 }
1957
1958 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1959                                      MVT::ValueType VT, SDOperand Op1,
1960                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
1961                                      SDOperand Op5, SDOperand Op6) {
1962   SDVTList VTs = getVTList(VT);
1963   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
1964   ID.AddOperand(Op1);
1965   ID.AddOperand(Op2);
1966   ID.AddOperand(Op3);
1967   ID.AddOperand(Op4);
1968   ID.AddOperand(Op5);
1969   ID.AddOperand(Op6);
1970   void *IP = 0;
1971   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1972     return SDOperand(ON, 0);
1973
1974   RemoveNodeFromCSEMaps(N);
1975   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1976   N->setValueTypes(VTs);
1977   N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6);
1978
1979   CSEMap.InsertNode(N, IP);   // Memoize the new node.
1980   return SDOperand(N, 0);
1981 }
1982
1983 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1984                                      MVT::ValueType VT, SDOperand Op1,
1985                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
1986                                      SDOperand Op5, SDOperand Op6,
1987                                      SDOperand Op7) {
1988   SDVTList VTs = getVTList(VT);
1989   // If an identical node already exists, use it.
1990   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
1991   ID.AddOperand(Op1);
1992   ID.AddOperand(Op2);
1993   ID.AddOperand(Op3);
1994   ID.AddOperand(Op4);
1995   ID.AddOperand(Op5);
1996   ID.AddOperand(Op6);
1997   ID.AddOperand(Op7);
1998   void *IP = 0;
1999   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2000     return SDOperand(ON, 0);
2001
2002   RemoveNodeFromCSEMaps(N);
2003   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2004   N->setValueTypes(VTs);
2005   N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7);
2006
2007   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2008   return SDOperand(N, 0);
2009 }
2010 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2011                                      MVT::ValueType VT, SDOperand Op1,
2012                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
2013                                      SDOperand Op5, SDOperand Op6,
2014                                      SDOperand Op7, SDOperand Op8) {
2015   // If an identical node already exists, use it.
2016   SDVTList VTs = getVTList(VT);
2017   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
2018   ID.AddOperand(Op1);
2019   ID.AddOperand(Op2);
2020   ID.AddOperand(Op3);
2021   ID.AddOperand(Op4);
2022   ID.AddOperand(Op5);
2023   ID.AddOperand(Op6);
2024   ID.AddOperand(Op7);
2025   ID.AddOperand(Op8);
2026   void *IP = 0;
2027   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2028     return SDOperand(ON, 0);
2029
2030   RemoveNodeFromCSEMaps(N);
2031   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2032   N->setValueTypes(VTs);
2033   N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7, Op8);
2034
2035   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2036   return SDOperand(N, 0);
2037 }
2038
2039 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2040                                      MVT::ValueType VT1, MVT::ValueType VT2,
2041                                      SDOperand Op1, SDOperand Op2) {
2042   SDVTList VTs = getVTList(VT1, VT2);
2043   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
2044   void *IP = 0;
2045   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2046     return SDOperand(ON, 0);
2047
2048   RemoveNodeFromCSEMaps(N);
2049   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2050   N->setValueTypes(VTs);
2051   N->setOperands(Op1, Op2);
2052
2053   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2054   return SDOperand(N, 0);
2055 }
2056
2057 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2058                                      MVT::ValueType VT1, MVT::ValueType VT2,
2059                                      SDOperand Op1, SDOperand Op2,
2060                                      SDOperand Op3) {
2061   // If an identical node already exists, use it.
2062   SDVTList VTs = getVTList(VT1, VT2);
2063   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs,
2064                                 Op1, Op2, Op3);
2065   void *IP = 0;
2066   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2067     return SDOperand(ON, 0);
2068
2069   RemoveNodeFromCSEMaps(N);
2070   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2071   N->setValueTypes(VTs);
2072   N->setOperands(Op1, Op2, Op3);
2073
2074   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2075   return SDOperand(N, 0);
2076 }
2077
2078 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2079                                      MVT::ValueType VT1, MVT::ValueType VT2,
2080                                      SDOperand Op1, SDOperand Op2,
2081                                      SDOperand Op3, SDOperand Op4) {
2082   // If an identical node already exists, use it.
2083   SDVTList VTs = getVTList(VT1, VT2);
2084   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
2085   ID.AddOperand(Op1);
2086   ID.AddOperand(Op2);
2087   ID.AddOperand(Op3);
2088   ID.AddOperand(Op4);
2089   void *IP = 0;
2090   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2091     return SDOperand(ON, 0);
2092
2093   RemoveNodeFromCSEMaps(N);
2094   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2095   N->setValueTypes(VTs);
2096   N->setOperands(Op1, Op2, Op3, Op4);
2097
2098   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2099   return SDOperand(N, 0);
2100 }
2101
2102 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2103                                      MVT::ValueType VT1, MVT::ValueType VT2,
2104                                      SDOperand Op1, SDOperand Op2,
2105                                      SDOperand Op3, SDOperand Op4,
2106                                      SDOperand Op5) {
2107   // If an identical node already exists, use it.
2108   SDVTList VTs = getVTList(VT1, VT2);
2109   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
2110   ID.AddOperand(Op1);
2111   ID.AddOperand(Op2);
2112   ID.AddOperand(Op3);
2113   ID.AddOperand(Op4);
2114   ID.AddOperand(Op5);
2115   void *IP = 0;
2116   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2117     return SDOperand(ON, 0);
2118
2119   RemoveNodeFromCSEMaps(N);
2120   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2121   N->setValueTypes(VTs);
2122   N->setOperands(Op1, Op2, Op3, Op4, Op5);
2123
2124   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2125   return SDOperand(N, 0);
2126 }
2127
2128 /// getTargetNode - These are used for target selectors to create a new node
2129 /// with specified return type(s), target opcode, and operands.
2130 ///
2131 /// Note that getTargetNode returns the resultant node.  If there is already a
2132 /// node of the specified opcode and operands, it returns that node instead of
2133 /// the current one.
2134 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) {
2135   return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val;
2136 }
2137 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2138                                     SDOperand Op1) {
2139   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val;
2140 }
2141 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2142                                     SDOperand Op1, SDOperand Op2) {
2143   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val;
2144 }
2145 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2146                                     SDOperand Op1, SDOperand Op2, SDOperand Op3) {
2147   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
2148 }
2149 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2150                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2151                                     SDOperand Op4) {
2152   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4).Val;
2153 }
2154 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2155                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2156                                     SDOperand Op4, SDOperand Op5) {
2157   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4, Op5).Val;
2158 }
2159 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2160                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2161                                     SDOperand Op4, SDOperand Op5,
2162                                     SDOperand Op6) {
2163   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6 };
2164   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, 6).Val;
2165 }
2166 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2167                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2168                                     SDOperand Op4, SDOperand Op5, SDOperand Op6,
2169                                     SDOperand Op7) {
2170   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6, Op7 };
2171   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, 7).Val;
2172 }
2173 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2174                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2175                                     SDOperand Op4, SDOperand Op5, SDOperand Op6,
2176                                     SDOperand Op7, SDOperand Op8) {
2177   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6, Op7, Op8 };
2178   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, 8).Val;
2179 }
2180 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2181                                     const SDOperand *Ops, unsigned NumOps) {
2182   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val;
2183 }
2184 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2185                                     MVT::ValueType VT2, SDOperand Op1) {
2186   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2187   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val;
2188 }
2189 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2190                                     MVT::ValueType VT2, SDOperand Op1,
2191                                     SDOperand Op2) {
2192   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2193   SDOperand Ops[] = { Op1, Op2 };
2194   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val;
2195 }
2196 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2197                                     MVT::ValueType VT2, SDOperand Op1,
2198                                     SDOperand Op2, SDOperand Op3) {
2199   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2200   SDOperand Ops[] = { Op1, Op2, Op3 };
2201   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val;
2202 }
2203 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2204                                     MVT::ValueType VT2, SDOperand Op1,
2205                                     SDOperand Op2, SDOperand Op3,
2206                                     SDOperand Op4) {
2207   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2208   SDOperand Ops[] = { Op1, Op2, Op3, Op4 };
2209   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 4).Val;
2210 }
2211 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2212                                     MVT::ValueType VT2, SDOperand Op1,
2213                                     SDOperand Op2, SDOperand Op3, SDOperand Op4,
2214                                     SDOperand Op5) {
2215   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2216   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
2217   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 5).Val;
2218 }
2219 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2220                                     MVT::ValueType VT2, SDOperand Op1,
2221                                     SDOperand Op2, SDOperand Op3, SDOperand Op4,
2222                                     SDOperand Op5, SDOperand Op6) {
2223   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2224   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6 };
2225   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 6).Val;
2226 }
2227 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2228                                     MVT::ValueType VT2, SDOperand Op1,
2229                                     SDOperand Op2, SDOperand Op3, SDOperand Op4,
2230                                     SDOperand Op5, SDOperand Op6,
2231                                     SDOperand Op7) {
2232   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2233   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6, Op7 };
2234   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 7).Val;
2235 }
2236 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2237                                     MVT::ValueType VT2, MVT::ValueType VT3,
2238                                     SDOperand Op1, SDOperand Op2) {
2239   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
2240   SDOperand Ops[] = { Op1, Op2 };
2241   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val;
2242 }
2243 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2244                                     MVT::ValueType VT2, MVT::ValueType VT3,
2245                                     SDOperand Op1, SDOperand Op2,
2246                                     SDOperand Op3, SDOperand Op4,
2247                                     SDOperand Op5) {
2248   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
2249   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
2250   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 5).Val;
2251 }
2252 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2253                                     MVT::ValueType VT2, MVT::ValueType VT3,
2254                                     SDOperand Op1, SDOperand Op2,
2255                                     SDOperand Op3, SDOperand Op4, SDOperand Op5,
2256                                     SDOperand Op6) {
2257   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
2258   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6 };
2259   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 6).Val;
2260 }
2261 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2262                                     MVT::ValueType VT2, MVT::ValueType VT3,
2263                                     SDOperand Op1, SDOperand Op2,
2264                                     SDOperand Op3, SDOperand Op4, SDOperand Op5,
2265                                     SDOperand Op6, SDOperand Op7) {
2266   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
2267   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6, Op7 };
2268   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 7).Val;
2269 }
2270 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2271                                     MVT::ValueType VT2,
2272                                     const SDOperand *Ops, unsigned NumOps) {
2273   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2274   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val;
2275 }
2276
2277 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
2278 /// This can cause recursive merging of nodes in the DAG.
2279 ///
2280 /// This version assumes From/To have a single result value.
2281 ///
2282 void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN,
2283                                       std::vector<SDNode*> *Deleted) {
2284   SDNode *From = FromN.Val, *To = ToN.Val;
2285   assert(From->getNumValues() == 1 && To->getNumValues() == 1 &&
2286          "Cannot replace with this method!");
2287   assert(From != To && "Cannot replace uses of with self");
2288
2289   while (!From->use_empty()) {
2290     // Process users until they are all gone.
2291     SDNode *U = *From->use_begin();
2292
2293     // This node is about to morph, remove its old self from the CSE maps.
2294     RemoveNodeFromCSEMaps(U);
2295
2296     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
2297          I != E; ++I)
2298       if (I->Val == From) {
2299         From->removeUser(U);
2300         I->Val = To;
2301         To->addUser(U);
2302       }
2303
2304     // Now that we have modified U, add it back to the CSE maps.  If it already
2305     // exists there, recursively merge the results together.
2306     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
2307       ReplaceAllUsesWith(U, Existing, Deleted);
2308       // U is now dead.
2309       if (Deleted) Deleted->push_back(U);
2310       DeleteNodeNotInCSEMaps(U);
2311     }
2312   }
2313 }
2314
2315 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
2316 /// This can cause recursive merging of nodes in the DAG.
2317 ///
2318 /// This version assumes From/To have matching types and numbers of result
2319 /// values.
2320 ///
2321 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
2322                                       std::vector<SDNode*> *Deleted) {
2323   assert(From != To && "Cannot replace uses of with self");
2324   assert(From->getNumValues() == To->getNumValues() &&
2325          "Cannot use this version of ReplaceAllUsesWith!");
2326   if (From->getNumValues() == 1) {  // If possible, use the faster version.
2327     ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted);
2328     return;
2329   }
2330
2331   while (!From->use_empty()) {
2332     // Process users until they are all gone.
2333     SDNode *U = *From->use_begin();
2334
2335     // This node is about to morph, remove its old self from the CSE maps.
2336     RemoveNodeFromCSEMaps(U);
2337
2338     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
2339          I != E; ++I)
2340       if (I->Val == From) {
2341         From->removeUser(U);
2342         I->Val = To;
2343         To->addUser(U);
2344       }
2345
2346     // Now that we have modified U, add it back to the CSE maps.  If it already
2347     // exists there, recursively merge the results together.
2348     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
2349       ReplaceAllUsesWith(U, Existing, Deleted);
2350       // U is now dead.
2351       if (Deleted) Deleted->push_back(U);
2352       DeleteNodeNotInCSEMaps(U);
2353     }
2354   }
2355 }
2356
2357 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
2358 /// This can cause recursive merging of nodes in the DAG.
2359 ///
2360 /// This version can replace From with any result values.  To must match the
2361 /// number and types of values returned by From.
2362 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
2363                                       const SDOperand *To,
2364                                       std::vector<SDNode*> *Deleted) {
2365   if (From->getNumValues() == 1 && To[0].Val->getNumValues() == 1) {
2366     // Degenerate case handled above.
2367     ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted);
2368     return;
2369   }
2370
2371   while (!From->use_empty()) {
2372     // Process users until they are all gone.
2373     SDNode *U = *From->use_begin();
2374
2375     // This node is about to morph, remove its old self from the CSE maps.
2376     RemoveNodeFromCSEMaps(U);
2377
2378     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
2379          I != E; ++I)
2380       if (I->Val == From) {
2381         const SDOperand &ToOp = To[I->ResNo];
2382         From->removeUser(U);
2383         *I = ToOp;
2384         ToOp.Val->addUser(U);
2385       }
2386
2387     // Now that we have modified U, add it back to the CSE maps.  If it already
2388     // exists there, recursively merge the results together.
2389     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
2390       ReplaceAllUsesWith(U, Existing, Deleted);
2391       // U is now dead.
2392       if (Deleted) Deleted->push_back(U);
2393       DeleteNodeNotInCSEMaps(U);
2394     }
2395   }
2396 }
2397
2398 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
2399 /// uses of other values produced by From.Val alone.  The Deleted vector is
2400 /// handled the same was as for ReplaceAllUsesWith.
2401 void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
2402                                              std::vector<SDNode*> &Deleted) {
2403   assert(From != To && "Cannot replace a value with itself");
2404   // Handle the simple, trivial, case efficiently.
2405   if (From.Val->getNumValues() == 1 && To.Val->getNumValues() == 1) {
2406     ReplaceAllUsesWith(From, To, &Deleted);
2407     return;
2408   }
2409
2410   // Get all of the users in a nice, deterministically ordered, uniqued set.
2411   SetVector<SDNode*> Users(From.Val->use_begin(), From.Val->use_end());
2412
2413   while (!Users.empty()) {
2414     // We know that this user uses some value of From.  If it is the right
2415     // value, update it.
2416     SDNode *User = Users.back();
2417     Users.pop_back();
2418
2419     for (SDOperand *Op = User->OperandList,
2420          *E = User->OperandList+User->NumOperands; Op != E; ++Op) {
2421       if (*Op == From) {
2422         // Okay, we know this user needs to be updated.  Remove its old self
2423         // from the CSE maps.
2424         RemoveNodeFromCSEMaps(User);
2425
2426         // Update all operands that match "From".
2427         for (; Op != E; ++Op) {
2428           if (*Op == From) {
2429             From.Val->removeUser(User);
2430             *Op = To;
2431             To.Val->addUser(User);
2432           }
2433         }
2434
2435         // Now that we have modified User, add it back to the CSE maps.  If it
2436         // already exists there, recursively merge the results together.
2437         if (SDNode *Existing = AddNonLeafNodeToCSEMaps(User)) {
2438           unsigned NumDeleted = Deleted.size();
2439           ReplaceAllUsesWith(User, Existing, &Deleted);
2440
2441           // User is now dead.
2442           Deleted.push_back(User);
2443           DeleteNodeNotInCSEMaps(User);
2444
2445           // We have to be careful here, because ReplaceAllUsesWith could have
2446           // deleted a user of From, which means there may be dangling pointers
2447           // in the "Users" setvector.  Scan over the deleted node pointers and
2448           // remove them from the setvector.
2449           for (unsigned i = NumDeleted, e = Deleted.size(); i != e; ++i)
2450             Users.remove(Deleted[i]);
2451         }
2452         break;   // Exit the operand scanning loop.
2453       }
2454     }
2455   }
2456 }
2457
2458
2459 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on
2460 /// their allnodes order. It returns the maximum id.
2461 unsigned SelectionDAG::AssignNodeIds() {
2462   unsigned Id = 0;
2463   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){
2464     SDNode *N = I;
2465     N->setNodeId(Id++);
2466   }
2467   return Id;
2468 }
2469
2470 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
2471 /// based on their topological order. It returns the maximum id and a vector
2472 /// of the SDNodes* in assigned order by reference.
2473 unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
2474   unsigned DAGSize = AllNodes.size();
2475   std::vector<unsigned> InDegree(DAGSize);
2476   std::vector<SDNode*> Sources;
2477
2478   // Use a two pass approach to avoid using a std::map which is slow.
2479   unsigned Id = 0;
2480   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
2481     SDNode *N = I;
2482     N->setNodeId(Id++);
2483     unsigned Degree = N->use_size();
2484     InDegree[N->getNodeId()] = Degree;
2485     if (Degree == 0)
2486       Sources.push_back(N);
2487   }
2488
2489   TopOrder.clear();
2490   while (!Sources.empty()) {
2491     SDNode *N = Sources.back();
2492     Sources.pop_back();
2493     TopOrder.push_back(N);
2494     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
2495       SDNode *P = I->Val;
2496       unsigned Degree = --InDegree[P->getNodeId()];
2497       if (Degree == 0)
2498         Sources.push_back(P);
2499     }
2500   }
2501
2502   // Second pass, assign the actual topological order as node ids.
2503   Id = 0;
2504   for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end();
2505        TI != TE; ++TI)
2506     (*TI)->setNodeId(Id++);
2507
2508   return Id;
2509 }
2510
2511
2512
2513 //===----------------------------------------------------------------------===//
2514 //                              SDNode Class
2515 //===----------------------------------------------------------------------===//
2516
2517 // Out-of-line virtual method to give class a home.
2518 void SDNode::ANCHOR() {
2519 }
2520
2521 /// getValueTypeList - Return a pointer to the specified value type.
2522 ///
2523 MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
2524   static MVT::ValueType VTs[MVT::LAST_VALUETYPE];
2525   VTs[VT] = VT;
2526   return &VTs[VT];
2527 }
2528
2529 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
2530 /// indicated value.  This method ignores uses of other values defined by this
2531 /// operation.
2532 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
2533   assert(Value < getNumValues() && "Bad value!");
2534
2535   // If there is only one value, this is easy.
2536   if (getNumValues() == 1)
2537     return use_size() == NUses;
2538   if (Uses.size() < NUses) return false;
2539
2540   SDOperand TheValue(const_cast<SDNode *>(this), Value);
2541
2542   std::set<SDNode*> UsersHandled;
2543
2544   for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) {
2545     SDNode *User = *UI;
2546     if (User->getNumOperands() == 1 ||
2547         UsersHandled.insert(User).second)     // First time we've seen this?
2548       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
2549         if (User->getOperand(i) == TheValue) {
2550           if (NUses == 0)
2551             return false;   // too many uses
2552           --NUses;
2553         }
2554   }
2555
2556   // Found exactly the right number of uses?
2557   return NUses == 0;
2558 }
2559
2560
2561 // isOnlyUse - Return true if this node is the only use of N.
2562 bool SDNode::isOnlyUse(SDNode *N) const {
2563   bool Seen = false;
2564   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
2565     SDNode *User = *I;
2566     if (User == this)
2567       Seen = true;
2568     else
2569       return false;
2570   }
2571
2572   return Seen;
2573 }
2574
2575 // isOperand - Return true if this node is an operand of N.
2576 bool SDOperand::isOperand(SDNode *N) const {
2577   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
2578     if (*this == N->getOperand(i))
2579       return true;
2580   return false;
2581 }
2582
2583 bool SDNode::isOperand(SDNode *N) const {
2584   for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
2585     if (this == N->OperandList[i].Val)
2586       return true;
2587   return false;
2588 }
2589
2590 const char *SDNode::getOperationName(const SelectionDAG *G) const {
2591   switch (getOpcode()) {
2592   default:
2593     if (getOpcode() < ISD::BUILTIN_OP_END)
2594       return "<<Unknown DAG Node>>";
2595     else {
2596       if (G) {
2597         if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
2598           if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
2599             return TII->getName(getOpcode()-ISD::BUILTIN_OP_END);
2600
2601         TargetLowering &TLI = G->getTargetLoweringInfo();
2602         const char *Name =
2603           TLI.getTargetNodeName(getOpcode());
2604         if (Name) return Name;
2605       }
2606
2607       return "<<Unknown Target Node>>";
2608     }
2609
2610   case ISD::PCMARKER:      return "PCMarker";
2611   case ISD::READCYCLECOUNTER: return "ReadCycleCounter";
2612   case ISD::SRCVALUE:      return "SrcValue";
2613   case ISD::EntryToken:    return "EntryToken";
2614   case ISD::TokenFactor:   return "TokenFactor";
2615   case ISD::AssertSext:    return "AssertSext";
2616   case ISD::AssertZext:    return "AssertZext";
2617
2618   case ISD::STRING:        return "String";
2619   case ISD::BasicBlock:    return "BasicBlock";
2620   case ISD::VALUETYPE:     return "ValueType";
2621   case ISD::Register:      return "Register";
2622
2623   case ISD::Constant:      return "Constant";
2624   case ISD::ConstantFP:    return "ConstantFP";
2625   case ISD::GlobalAddress: return "GlobalAddress";
2626   case ISD::FrameIndex:    return "FrameIndex";
2627   case ISD::JumpTable:     return "JumpTable";
2628   case ISD::ConstantPool:  return "ConstantPool";
2629   case ISD::ExternalSymbol: return "ExternalSymbol";
2630   case ISD::INTRINSIC_WO_CHAIN: {
2631     unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue();
2632     return Intrinsic::getName((Intrinsic::ID)IID);
2633   }
2634   case ISD::INTRINSIC_VOID:
2635   case ISD::INTRINSIC_W_CHAIN: {
2636     unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue();
2637     return Intrinsic::getName((Intrinsic::ID)IID);
2638   }
2639
2640   case ISD::BUILD_VECTOR:   return "BUILD_VECTOR";
2641   case ISD::TargetConstant: return "TargetConstant";
2642   case ISD::TargetConstantFP:return "TargetConstantFP";
2643   case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
2644   case ISD::TargetFrameIndex: return "TargetFrameIndex";
2645   case ISD::TargetJumpTable:  return "TargetJumpTable";
2646   case ISD::TargetConstantPool:  return "TargetConstantPool";
2647   case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
2648
2649   case ISD::CopyToReg:     return "CopyToReg";
2650   case ISD::CopyFromReg:   return "CopyFromReg";
2651   case ISD::UNDEF:         return "undef";
2652   case ISD::MERGE_VALUES:  return "mergevalues";
2653   case ISD::INLINEASM:     return "inlineasm";
2654   case ISD::HANDLENODE:    return "handlenode";
2655   case ISD::FORMAL_ARGUMENTS: return "formal_arguments";
2656   case ISD::CALL:          return "call";
2657
2658   // Unary operators
2659   case ISD::FABS:   return "fabs";
2660   case ISD::FNEG:   return "fneg";
2661   case ISD::FSQRT:  return "fsqrt";
2662   case ISD::FSIN:   return "fsin";
2663   case ISD::FCOS:   return "fcos";
2664
2665   // Binary operators
2666   case ISD::ADD:    return "add";
2667   case ISD::SUB:    return "sub";
2668   case ISD::MUL:    return "mul";
2669   case ISD::MULHU:  return "mulhu";
2670   case ISD::MULHS:  return "mulhs";
2671   case ISD::SDIV:   return "sdiv";
2672   case ISD::UDIV:   return "udiv";
2673   case ISD::SREM:   return "srem";
2674   case ISD::UREM:   return "urem";
2675   case ISD::AND:    return "and";
2676   case ISD::OR:     return "or";
2677   case ISD::XOR:    return "xor";
2678   case ISD::SHL:    return "shl";
2679   case ISD::SRA:    return "sra";
2680   case ISD::SRL:    return "srl";
2681   case ISD::ROTL:   return "rotl";
2682   case ISD::ROTR:   return "rotr";
2683   case ISD::FADD:   return "fadd";
2684   case ISD::FSUB:   return "fsub";
2685   case ISD::FMUL:   return "fmul";
2686   case ISD::FDIV:   return "fdiv";
2687   case ISD::FREM:   return "frem";
2688   case ISD::FCOPYSIGN: return "fcopysign";
2689   case ISD::VADD:   return "vadd";
2690   case ISD::VSUB:   return "vsub";
2691   case ISD::VMUL:   return "vmul";
2692   case ISD::VSDIV:  return "vsdiv";
2693   case ISD::VUDIV:  return "vudiv";
2694   case ISD::VAND:   return "vand";
2695   case ISD::VOR:    return "vor";
2696   case ISD::VXOR:   return "vxor";
2697
2698   case ISD::SETCC:       return "setcc";
2699   case ISD::SELECT:      return "select";
2700   case ISD::SELECT_CC:   return "select_cc";
2701   case ISD::VSELECT:     return "vselect";
2702   case ISD::INSERT_VECTOR_ELT:   return "insert_vector_elt";
2703   case ISD::VINSERT_VECTOR_ELT:  return "vinsert_vector_elt";
2704   case ISD::EXTRACT_VECTOR_ELT:  return "extract_vector_elt";
2705   case ISD::VEXTRACT_VECTOR_ELT: return "vextract_vector_elt";
2706   case ISD::SCALAR_TO_VECTOR:    return "scalar_to_vector";
2707   case ISD::VBUILD_VECTOR:       return "vbuild_vector";
2708   case ISD::VECTOR_SHUFFLE:      return "vector_shuffle";
2709   case ISD::VVECTOR_SHUFFLE:     return "vvector_shuffle";
2710   case ISD::VBIT_CONVERT:        return "vbit_convert";
2711   case ISD::ADDC:        return "addc";
2712   case ISD::ADDE:        return "adde";
2713   case ISD::SUBC:        return "subc";
2714   case ISD::SUBE:        return "sube";
2715   case ISD::SHL_PARTS:   return "shl_parts";
2716   case ISD::SRA_PARTS:   return "sra_parts";
2717   case ISD::SRL_PARTS:   return "srl_parts";
2718
2719   // Conversion operators.
2720   case ISD::SIGN_EXTEND: return "sign_extend";
2721   case ISD::ZERO_EXTEND: return "zero_extend";
2722   case ISD::ANY_EXTEND:  return "any_extend";
2723   case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
2724   case ISD::TRUNCATE:    return "truncate";
2725   case ISD::FP_ROUND:    return "fp_round";
2726   case ISD::FP_ROUND_INREG: return "fp_round_inreg";
2727   case ISD::FP_EXTEND:   return "fp_extend";
2728
2729   case ISD::SINT_TO_FP:  return "sint_to_fp";
2730   case ISD::UINT_TO_FP:  return "uint_to_fp";
2731   case ISD::FP_TO_SINT:  return "fp_to_sint";
2732   case ISD::FP_TO_UINT:  return "fp_to_uint";
2733   case ISD::BIT_CONVERT: return "bit_convert";
2734
2735     // Control flow instructions
2736   case ISD::BR:      return "br";
2737   case ISD::BRIND:   return "brind";
2738   case ISD::BRCOND:  return "brcond";
2739   case ISD::BR_CC:   return "br_cc";
2740   case ISD::RET:     return "ret";
2741   case ISD::CALLSEQ_START:  return "callseq_start";
2742   case ISD::CALLSEQ_END:    return "callseq_end";
2743
2744     // Other operators
2745   case ISD::LOAD:               return "load";
2746   case ISD::STORE:              return "store";
2747   case ISD::VLOAD:              return "vload";
2748   case ISD::EXTLOAD:            return "extload";
2749   case ISD::SEXTLOAD:           return "sextload";
2750   case ISD::ZEXTLOAD:           return "zextload";
2751   case ISD::TRUNCSTORE:         return "truncstore";
2752   case ISD::VAARG:              return "vaarg";
2753   case ISD::VACOPY:             return "vacopy";
2754   case ISD::VAEND:              return "vaend";
2755   case ISD::VASTART:            return "vastart";
2756   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
2757   case ISD::EXTRACT_ELEMENT:    return "extract_element";
2758   case ISD::BUILD_PAIR:         return "build_pair";
2759   case ISD::STACKSAVE:          return "stacksave";
2760   case ISD::STACKRESTORE:       return "stackrestore";
2761
2762   // Block memory operations.
2763   case ISD::MEMSET:  return "memset";
2764   case ISD::MEMCPY:  return "memcpy";
2765   case ISD::MEMMOVE: return "memmove";
2766
2767   // Bit manipulation
2768   case ISD::BSWAP:   return "bswap";
2769   case ISD::CTPOP:   return "ctpop";
2770   case ISD::CTTZ:    return "cttz";
2771   case ISD::CTLZ:    return "ctlz";
2772
2773   // Debug info
2774   case ISD::LOCATION: return "location";
2775   case ISD::DEBUG_LOC: return "debug_loc";
2776   case ISD::DEBUG_LABEL: return "debug_label";
2777
2778   case ISD::CONDCODE:
2779     switch (cast<CondCodeSDNode>(this)->get()) {
2780     default: assert(0 && "Unknown setcc condition!");
2781     case ISD::SETOEQ:  return "setoeq";
2782     case ISD::SETOGT:  return "setogt";
2783     case ISD::SETOGE:  return "setoge";
2784     case ISD::SETOLT:  return "setolt";
2785     case ISD::SETOLE:  return "setole";
2786     case ISD::SETONE:  return "setone";
2787
2788     case ISD::SETO:    return "seto";
2789     case ISD::SETUO:   return "setuo";
2790     case ISD::SETUEQ:  return "setue";
2791     case ISD::SETUGT:  return "setugt";
2792     case ISD::SETUGE:  return "setuge";
2793     case ISD::SETULT:  return "setult";
2794     case ISD::SETULE:  return "setule";
2795     case ISD::SETUNE:  return "setune";
2796
2797     case ISD::SETEQ:   return "seteq";
2798     case ISD::SETGT:   return "setgt";
2799     case ISD::SETGE:   return "setge";
2800     case ISD::SETLT:   return "setlt";
2801     case ISD::SETLE:   return "setle";
2802     case ISD::SETNE:   return "setne";
2803     }
2804   }
2805 }
2806
2807 void SDNode::dump() const { dump(0); }
2808 void SDNode::dump(const SelectionDAG *G) const {
2809   std::cerr << (void*)this << ": ";
2810
2811   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
2812     if (i) std::cerr << ",";
2813     if (getValueType(i) == MVT::Other)
2814       std::cerr << "ch";
2815     else
2816       std::cerr << MVT::getValueTypeString(getValueType(i));
2817   }
2818   std::cerr << " = " << getOperationName(G);
2819
2820   std::cerr << " ";
2821   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
2822     if (i) std::cerr << ", ";
2823     std::cerr << (void*)getOperand(i).Val;
2824     if (unsigned RN = getOperand(i).ResNo)
2825       std::cerr << ":" << RN;
2826   }
2827
2828   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
2829     std::cerr << "<" << CSDN->getValue() << ">";
2830   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
2831     std::cerr << "<" << CSDN->getValue() << ">";
2832   } else if (const GlobalAddressSDNode *GADN =
2833              dyn_cast<GlobalAddressSDNode>(this)) {
2834     int offset = GADN->getOffset();
2835     std::cerr << "<";
2836     WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
2837     if (offset > 0)
2838       std::cerr << " + " << offset;
2839     else
2840       std::cerr << " " << offset;
2841   } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
2842     std::cerr << "<" << FIDN->getIndex() << ">";
2843   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
2844     int offset = CP->getOffset();
2845     std::cerr << "<" << *CP->get() << ">";
2846     if (offset > 0)
2847       std::cerr << " + " << offset;
2848     else
2849       std::cerr << " " << offset;
2850   } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
2851     std::cerr << "<";
2852     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
2853     if (LBB)
2854       std::cerr << LBB->getName() << " ";
2855     std::cerr << (const void*)BBDN->getBasicBlock() << ">";
2856   } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
2857     if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) {
2858       std::cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg());
2859     } else {
2860       std::cerr << " #" << R->getReg();
2861     }
2862   } else if (const ExternalSymbolSDNode *ES =
2863              dyn_cast<ExternalSymbolSDNode>(this)) {
2864     std::cerr << "'" << ES->getSymbol() << "'";
2865   } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
2866     if (M->getValue())
2867       std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">";
2868     else
2869       std::cerr << "<null:" << M->getOffset() << ">";
2870   } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
2871     std::cerr << ":" << getValueTypeString(N->getVT());
2872   }
2873 }
2874
2875 static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
2876   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
2877     if (N->getOperand(i).Val->hasOneUse())
2878       DumpNodes(N->getOperand(i).Val, indent+2, G);
2879     else
2880       std::cerr << "\n" << std::string(indent+2, ' ')
2881                 << (void*)N->getOperand(i).Val << ": <multiple use>";
2882
2883
2884   std::cerr << "\n" << std::string(indent, ' ');
2885   N->dump(G);
2886 }
2887
2888 void SelectionDAG::dump() const {
2889   std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
2890   std::vector<const SDNode*> Nodes;
2891   for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
2892        I != E; ++I)
2893     Nodes.push_back(I);
2894
2895   std::sort(Nodes.begin(), Nodes.end());
2896
2897   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
2898     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
2899       DumpNodes(Nodes[i], 2, this);
2900   }
2901
2902   DumpNodes(getRoot().Val, 2, this);
2903
2904   std::cerr << "\n\n";
2905 }
2906