lib/CodeGen/SelectionDAG/SelectionDAG.cpp

   1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the SelectionDAG class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #include "llvm/CodeGen/SelectionDAG.h"
  14 #include "llvm/Constants.h"
  15 #include "llvm/GlobalAlias.h"
  16 #include "llvm/GlobalVariable.h"
  17 #include "llvm/Intrinsics.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/Assembly/Writer.h"
  20 #include "llvm/CallingConv.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/CodeGen/MachineConstantPool.h"
  23 #include "llvm/CodeGen/MachineFrameInfo.h"
  24 #include "llvm/CodeGen/MachineModuleInfo.h"
  25 #include "llvm/CodeGen/PseudoSourceValue.h"
  26 #include "llvm/Support/MathExtras.h"
  27 #include "llvm/Target/TargetRegisterInfo.h"
  28 #include "llvm/Target/TargetData.h"
  29 #include "llvm/Target/TargetLowering.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31 #include "llvm/Target/TargetMachine.h"
  32 #include "llvm/ADT/SetVector.h"
  33 #include "llvm/ADT/SmallPtrSet.h"
  34 #include "llvm/ADT/SmallSet.h"
  35 #include "llvm/ADT/SmallVector.h"
  36 #include "llvm/ADT/StringExtras.h"
  37 #include <algorithm>
  38 #include <cmath>
  39 using namespace llvm;
  40
  41 /// makeVTList - Return an instance of the SDVTList struct initialized with the
  42 /// specified members.
  43 static SDVTList makeVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
  44   SDVTList Res = {VTs, NumVTs};
  45   return Res;
  46 }
  47
  48 static const fltSemantics *MVTToAPFloatSemantics(MVT::ValueType VT) {
  49   switch (VT) {
  50   default: assert(0 && "Unknown FP format");
  51   case MVT::f32:     return &APFloat::IEEEsingle;
  52   case MVT::f64:     return &APFloat::IEEEdouble;
  53   case MVT::f80:     return &APFloat::x87DoubleExtended;
  54   case MVT::f128:    return &APFloat::IEEEquad;
  55   case MVT::ppcf128: return &APFloat::PPCDoubleDouble;
  56   }
  57 }
  58
  59 SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {}
  60
  61 //===----------------------------------------------------------------------===//
  62 //                              ConstantFPSDNode Class
  63 //===----------------------------------------------------------------------===//
  64
  65 /// isExactlyValue - We don't rely on operator== working on double values, as
  66 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
  67 /// As such, this method can be used to do an exact bit-for-bit comparison of
  68 /// two floating point values.
  69 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
  70   return Value.bitwiseIsEqual(V);
  71 }
  72
  73 bool ConstantFPSDNode::isValueValidForType(MVT::ValueType VT,
  74                                            const APFloat& Val) {
  75   assert(MVT::isFloatingPoint(VT) && "Can only convert between FP types");
  76
  77   // PPC long double cannot be converted to any other type.
  78   if (VT == MVT::ppcf128 ||
  79       &Val.getSemantics() == &APFloat::PPCDoubleDouble)
  80     return false;
  81
  82   // convert modifies in place, so make a copy.
  83   APFloat Val2 = APFloat(Val);
  84   return Val2.convert(*MVTToAPFloatSemantics(VT),
  85                       APFloat::rmNearestTiesToEven) == APFloat::opOK;
  86 }
  87
  88 //===----------------------------------------------------------------------===//
  89 //                              ISD Namespace
  90 //===----------------------------------------------------------------------===//
  91
  92 /// isBuildVectorAllOnes - Return true if the specified node is a
  93 /// BUILD_VECTOR where all of the elements are ~0 or undef.
  94 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
  95   // Look through a bit convert.
  96   if (N->getOpcode() == ISD::BIT_CONVERT)
  97     N = N->getOperand(0).Val;
  98
  99   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
 100
 101   unsigned i = 0, e = N->getNumOperands();
 102
 103   // Skip over all of the undef values.
 104   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
 105     ++i;
 106
 107   // Do not accept an all-undef vector.
 108   if (i == e) return false;
 109
 110   // Do not accept build_vectors that aren't all constants or which have non-~0
 111   // elements.
 112   SDOperand NotZero = N->getOperand(i);
 113   if (isa<ConstantSDNode>(NotZero)) {
 114     if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue())
 115       return false;
 116   } else if (isa<ConstantFPSDNode>(NotZero)) {
 117     if (!cast<ConstantFPSDNode>(NotZero)->getValueAPF().
 118                 convertToAPInt().isAllOnesValue())
 119       return false;
 120   } else
 121     return false;
 122
 123   // Okay, we have at least one ~0 value, check to see if the rest match or are
 124   // undefs.
 125   for (++i; i != e; ++i)
 126     if (N->getOperand(i) != NotZero &&
 127         N->getOperand(i).getOpcode() != ISD::UNDEF)
 128       return false;
 129   return true;
 130 }
 131
 132
 133 /// isBuildVectorAllZeros - Return true if the specified node is a
 134 /// BUILD_VECTOR where all of the elements are 0 or undef.
 135 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
 136   // Look through a bit convert.
 137   if (N->getOpcode() == ISD::BIT_CONVERT)
 138     N = N->getOperand(0).Val;
 139
 140   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
 141
 142   unsigned i = 0, e = N->getNumOperands();
 143
 144   // Skip over all of the undef values.
 145   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
 146     ++i;
 147
 148   // Do not accept an all-undef vector.
 149   if (i == e) return false;
 150
 151   // Do not accept build_vectors that aren't all constants or which have non-~0
 152   // elements.
 153   SDOperand Zero = N->getOperand(i);
 154   if (isa<ConstantSDNode>(Zero)) {
 155     if (!cast<ConstantSDNode>(Zero)->isNullValue())
 156       return false;
 157   } else if (isa<ConstantFPSDNode>(Zero)) {
 158     if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero())
 159       return false;
 160   } else
 161     return false;
 162
 163   // Okay, we have at least one ~0 value, check to see if the rest match or are
 164   // undefs.
 165   for (++i; i != e; ++i)
 166     if (N->getOperand(i) != Zero &&
 167         N->getOperand(i).getOpcode() != ISD::UNDEF)
 168       return false;
 169   return true;
 170 }
 171
 172 /// isScalarToVector - Return true if the specified node is a
 173 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
 174 /// element is not an undef.
 175 bool ISD::isScalarToVector(const SDNode *N) {
 176   if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
 177     return true;
 178
 179   if (N->getOpcode() != ISD::BUILD_VECTOR)
 180     return false;
 181   if (N->getOperand(0).getOpcode() == ISD::UNDEF)
 182     return false;
 183   unsigned NumElems = N->getNumOperands();
 184   for (unsigned i = 1; i < NumElems; ++i) {
 185     SDOperand V = N->getOperand(i);
 186     if (V.getOpcode() != ISD::UNDEF)
 187       return false;
 188   }
 189   return true;
 190 }
 191
 192
 193 /// isDebugLabel - Return true if the specified node represents a debug
 194 /// label (i.e. ISD::LABEL or TargetInstrInfo::LABEL node and third operand
 195 /// is 0).
 196 bool ISD::isDebugLabel(const SDNode *N) {
 197   SDOperand Zero;
 198   if (N->getOpcode() == ISD::LABEL)
 199     Zero = N->getOperand(2);
 200   else if (N->isTargetOpcode() &&
 201            N->getTargetOpcode() == TargetInstrInfo::LABEL)
 202     // Chain moved to last operand.
 203     Zero = N->getOperand(1);
 204   else
 205     return false;
 206   return isa<ConstantSDNode>(Zero) && cast<ConstantSDNode>(Zero)->isNullValue();
 207 }
 208
 209 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
 210 /// when given the operation for (X op Y).
 211 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
 212   // To perform this operation, we just need to swap the L and G bits of the
 213   // operation.
 214   unsigned OldL = (Operation >> 2) & 1;
 215   unsigned OldG = (Operation >> 1) & 1;
 216   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
 217                        (OldL << 1) |       // New G bit
 218                        (OldG << 2));        // New L bit.
 219 }
 220
 221 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
 222 /// 'op' is a valid SetCC operation.
 223 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
 224   unsigned Operation = Op;
 225   if (isInteger)
 226     Operation ^= 7;   // Flip L, G, E bits, but not U.
 227   else
 228     Operation ^= 15;  // Flip all of the condition bits.
 229   if (Operation > ISD::SETTRUE2)
 230     Operation &= ~8;     // Don't let N and U bits get set.
 231   return ISD::CondCode(Operation);
 232 }
 233
 234
 235 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
 236 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
 237 /// if the operation does not depend on the sign of the input (setne and seteq).
 238 static int isSignedOp(ISD::CondCode Opcode) {
 239   switch (Opcode) {
 240   default: assert(0 && "Illegal integer setcc operation!");
 241   case ISD::SETEQ:
 242   case ISD::SETNE: return 0;
 243   case ISD::SETLT:
 244   case ISD::SETLE:
 245   case ISD::SETGT:
 246   case ISD::SETGE: return 1;
 247   case ISD::SETULT:
 248   case ISD::SETULE:
 249   case ISD::SETUGT:
 250   case ISD::SETUGE: return 2;
 251   }
 252 }
 253
 254 /// getSetCCOrOperation - Return the result of a logical OR between different
 255 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
 256 /// returns SETCC_INVALID if it is not possible to represent the resultant
 257 /// comparison.
 258 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 259                                        bool isInteger) {
 260   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 261     // Cannot fold a signed integer setcc with an unsigned integer setcc.
 262     return ISD::SETCC_INVALID;
 263
 264   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
 265
 266   // If the N and U bits get set then the resultant comparison DOES suddenly
 267   // care about orderedness, and is true when ordered.
 268   if (Op > ISD::SETTRUE2)
 269     Op &= ~16;     // Clear the U bit if the N bit is set.
 270
 271   // Canonicalize illegal integer setcc's.
 272   if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
 273     Op = ISD::SETNE;
 274
 275   return ISD::CondCode(Op);
 276 }
 277
 278 /// getSetCCAndOperation - Return the result of a logical AND between different
 279 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
 280 /// function returns zero if it is not possible to represent the resultant
 281 /// comparison.
 282 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 283                                         bool isInteger) {
 284   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 285     // Cannot fold a signed setcc with an unsigned setcc.
 286     return ISD::SETCC_INVALID;
 287
 288   // Combine all of the condition bits.
 289   ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
 290
 291   // Canonicalize illegal integer setcc's.
 292   if (isInteger) {
 293     switch (Result) {
 294     default: break;
 295     case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
 296     case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
 297     case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
 298     case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
 299     }
 300   }
 301
 302   return Result;
 303 }
 304
 305 const TargetMachine &SelectionDAG::getTarget() const {
 306   return TLI.getTargetMachine();
 307 }
 308
 309 //===----------------------------------------------------------------------===//
 310 //                           SDNode Profile Support
 311 //===----------------------------------------------------------------------===//
 312
 313 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
 314 ///
 315 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC)  {
 316   ID.AddInteger(OpC);
 317 }
 318
 319 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
 320 /// solely with their pointer.
 321 void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
 322   ID.AddPointer(VTList.VTs);
 323 }
 324
 325 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
 326 ///
 327 static void AddNodeIDOperands(FoldingSetNodeID &ID,
 328                               SDOperandPtr Ops, unsigned NumOps) {
 329   for (; NumOps; --NumOps, ++Ops) {
 330     ID.AddPointer(Ops->Val);
 331     ID.AddInteger(Ops->ResNo);
 332   }
 333 }
 334
 335 static void AddNodeIDNode(FoldingSetNodeID &ID,
 336                           unsigned short OpC, SDVTList VTList,
 337                           SDOperandPtr OpList, unsigned N) {
 338   AddNodeIDOpcode(ID, OpC);
 339   AddNodeIDValueTypes(ID, VTList);
 340   AddNodeIDOperands(ID, OpList, N);
 341 }
 342
 343
 344 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
 345 /// data.
 346 static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) {
 347   AddNodeIDOpcode(ID, N->getOpcode());
 348   // Add the return value info.
 349   AddNodeIDValueTypes(ID, N->getVTList());
 350   // Add the operand info.
 351   AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
 352
 353   // Handle SDNode leafs with special info.
 354   switch (N->getOpcode()) {
 355   default: break;  // Normal nodes don't need extra info.
 356   case ISD::ARG_FLAGS:
 357     ID.AddInteger(cast<ARG_FLAGSSDNode>(N)->getArgFlags().getRawBits());
 358     break;
 359   case ISD::TargetConstant:
 360   case ISD::Constant:
 361     ID.Add(cast<ConstantSDNode>(N)->getAPIntValue());
 362     break;
 363   case ISD::TargetConstantFP:
 364   case ISD::ConstantFP: {
 365     ID.Add(cast<ConstantFPSDNode>(N)->getValueAPF());
 366     break;
 367   }
 368   case ISD::TargetGlobalAddress:
 369   case ISD::GlobalAddress:
 370   case ISD::TargetGlobalTLSAddress:
 371   case ISD::GlobalTLSAddress: {
 372     GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
 373     ID.AddPointer(GA->getGlobal());
 374     ID.AddInteger(GA->getOffset());
 375     break;
 376   }
 377   case ISD::BasicBlock:
 378     ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
 379     break;
 380   case ISD::Register:
 381     ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
 382     break;
 383   case ISD::SRCVALUE:
 384     ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
 385     break;
 386   case ISD::MEMOPERAND: {
 387     const MachineMemOperand &MO = cast<MemOperandSDNode>(N)->MO;
 388     ID.AddPointer(MO.getValue());
 389     ID.AddInteger(MO.getFlags());
 390     ID.AddInteger(MO.getOffset());
 391     ID.AddInteger(MO.getSize());
 392     ID.AddInteger(MO.getAlignment());
 393     break;
 394   }
 395   case ISD::FrameIndex:
 396   case ISD::TargetFrameIndex:
 397     ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
 398     break;
 399   case ISD::JumpTable:
 400   case ISD::TargetJumpTable:
 401     ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
 402     break;
 403   case ISD::ConstantPool:
 404   case ISD::TargetConstantPool: {
 405     ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
 406     ID.AddInteger(CP->getAlignment());
 407     ID.AddInteger(CP->getOffset());
 408     if (CP->isMachineConstantPoolEntry())
 409       CP->getMachineCPVal()->AddSelectionDAGCSEId(ID);
 410     else
 411       ID.AddPointer(CP->getConstVal());
 412     break;
 413   }
 414   case ISD::LOAD: {
 415     LoadSDNode *LD = cast<LoadSDNode>(N);
 416     ID.AddInteger(LD->getAddressingMode());
 417     ID.AddInteger(LD->getExtensionType());
 418     ID.AddInteger((unsigned int)(LD->getMemoryVT()));
 419     ID.AddInteger(LD->getAlignment());
 420     ID.AddInteger(LD->isVolatile());
 421     break;
 422   }
 423   case ISD::STORE: {
 424     StoreSDNode *ST = cast<StoreSDNode>(N);
 425     ID.AddInteger(ST->getAddressingMode());
 426     ID.AddInteger(ST->isTruncatingStore());
 427     ID.AddInteger((unsigned int)(ST->getMemoryVT()));
 428     ID.AddInteger(ST->getAlignment());
 429     ID.AddInteger(ST->isVolatile());
 430     break;
 431   }
 432   }
 433 }
 434
 435 //===----------------------------------------------------------------------===//
 436 //                              SelectionDAG Class
 437 //===----------------------------------------------------------------------===//
 438
 439 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
 440 /// SelectionDAG.
 441 void SelectionDAG::RemoveDeadNodes() {
 442   // Create a dummy node (which is not added to allnodes), that adds a reference
 443   // to the root node, preventing it from being deleted.
 444   HandleSDNode Dummy(getRoot());
 445
 446   SmallVector<SDNode*, 128> DeadNodes;
 447
 448   // Add all obviously-dead nodes to the DeadNodes worklist.
 449   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
 450     if (I->use_empty())
 451       DeadNodes.push_back(I);
 452
 453   // Process the worklist, deleting the nodes and adding their uses to the
 454   // worklist.
 455   while (!DeadNodes.empty()) {
 456     SDNode *N = DeadNodes.back();
 457     DeadNodes.pop_back();
 458
 459     // Take the node out of the appropriate CSE map.
 460     RemoveNodeFromCSEMaps(N);
 461
 462     // Next, brutally remove the operand list.  This is safe to do, as there are
 463     // no cycles in the graph.
 464     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
 465       SDNode *Operand = I->getVal();
 466       Operand->removeUser(std::distance(N->op_begin(), I), N);
 467
 468       // Now that we removed this operand, see if there are no uses of it left.
 469       if (Operand->use_empty())
 470         DeadNodes.push_back(Operand);
 471     }
 472     if (N->OperandsNeedDelete) {
 473       delete[] N->OperandList;
 474     }
 475     N->OperandList = 0;
 476     N->NumOperands = 0;
 477
 478     // Finally, remove N itself.
 479     AllNodes.erase(N);
 480   }
 481
 482   // If the root changed (e.g. it was a dead load, update the root).
 483   setRoot(Dummy.getValue());
 484 }
 485
 486 void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
 487   SmallVector<SDNode*, 16> DeadNodes;
 488   DeadNodes.push_back(N);
 489
 490   // Process the worklist, deleting the nodes and adding their uses to the
 491   // worklist.
 492   while (!DeadNodes.empty()) {
 493     SDNode *N = DeadNodes.back();
 494     DeadNodes.pop_back();
 495
 496     if (UpdateListener)
 497       UpdateListener->NodeDeleted(N);
 498
 499     // Take the node out of the appropriate CSE map.
 500     RemoveNodeFromCSEMaps(N);
 501
 502     // Next, brutally remove the operand list.  This is safe to do, as there are
 503     // no cycles in the graph.
 504     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
 505       SDNode *Operand = I->getVal();
 506       Operand->removeUser(std::distance(N->op_begin(), I), N);
 507
 508       // Now that we removed this operand, see if there are no uses of it left.
 509       if (Operand->use_empty())
 510         DeadNodes.push_back(Operand);
 511     }
 512     if (N->OperandsNeedDelete) {
 513       delete[] N->OperandList;
 514     }
 515     N->OperandList = 0;
 516     N->NumOperands = 0;
 517
 518     // Finally, remove N itself.
 519     AllNodes.erase(N);
 520   }
 521 }
 522
 523 void SelectionDAG::DeleteNode(SDNode *N) {
 524   assert(N->use_empty() && "Cannot delete a node that is not dead!");
 525
 526   // First take this out of the appropriate CSE map.
 527   RemoveNodeFromCSEMaps(N);
 528
 529   // Finally, remove uses due to operands of this node, remove from the
 530   // AllNodes list, and delete the node.
 531   DeleteNodeNotInCSEMaps(N);
 532 }
 533
 534 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
 535
 536   // Remove it from the AllNodes list.
 537   AllNodes.remove(N);
 538
 539   // Drop all of the operands and decrement used nodes use counts.
 540   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
 541     I->getVal()->removeUser(std::distance(N->op_begin(), I), N);
 542   if (N->OperandsNeedDelete) {
 543     delete[] N->OperandList;
 544   }
 545   N->OperandList = 0;
 546   N->NumOperands = 0;
 547
 548   delete N;
 549 }
 550
 551 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
 552 /// correspond to it.  This is useful when we're about to delete or repurpose
 553 /// the node.  We don't want future request for structurally identical nodes
 554 /// to return N anymore.
 555 void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
 556   bool Erased = false;
 557   switch (N->getOpcode()) {
 558   case ISD::HANDLENODE: return;  // noop.
 559   case ISD::STRING:
 560     Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue());
 561     break;
 562   case ISD::CONDCODE:
 563     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
 564            "Cond code doesn't exist!");
 565     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
 566     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
 567     break;
 568   case ISD::ExternalSymbol:
 569     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 570     break;
 571   case ISD::TargetExternalSymbol:
 572     Erased =
 573       TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 574     break;
 575   case ISD::VALUETYPE: {
 576     MVT::ValueType VT = cast<VTSDNode>(N)->getVT();
 577     if (MVT::isExtendedVT(VT)) {
 578       Erased = ExtendedValueTypeNodes.erase(VT);
 579     } else {
 580       Erased = ValueTypeNodes[VT] != 0;
 581       ValueTypeNodes[VT] = 0;
 582     }
 583     break;
 584   }
 585   default:
 586     // Remove it from the CSE Map.
 587     Erased = CSEMap.RemoveNode(N);
 588     break;
 589   }
 590 #ifndef NDEBUG
 591   // Verify that the node was actually in one of the CSE maps, unless it has a
 592   // flag result (which cannot be CSE'd) or is one of the special cases that are
 593   // not subject to CSE.
 594   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag &&
 595       !N->isTargetOpcode()) {
 596     N->dump(this);
 597     cerr << "\n";
 598     assert(0 && "Node is not in map!");
 599   }
 600 #endif
 601 }
 602
 603 /// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps.  It
 604 /// has been taken out and modified in some way.  If the specified node already
 605 /// exists in the CSE maps, do not modify the maps, but return the existing node
 606 /// instead.  If it doesn't exist, add it and return null.
 607 ///
 608 SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
 609   assert(N->getNumOperands() && "This is a leaf node!");
 610   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 611     return 0;    // Never add these nodes.
 612
 613   // Check that remaining values produced are not flags.
 614   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 615     if (N->getValueType(i) == MVT::Flag)
 616       return 0;   // Never CSE anything that produces a flag.
 617
 618   SDNode *New = CSEMap.GetOrInsertNode(N);
 619   if (New != N) return New;  // Node already existed.
 620   return 0;
 621 }
 622
 623 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 624 /// were replaced with those specified.  If this node is never memoized,
 625 /// return null, otherwise return a pointer to the slot it would take.  If a
 626 /// node already exists with these operands, the slot will be non-null.
 627 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op,
 628                                            void *&InsertPos) {
 629   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 630     return 0;    // Never add these nodes.
 631
 632   // Check that remaining values produced are not flags.
 633   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 634     if (N->getValueType(i) == MVT::Flag)
 635       return 0;   // Never CSE anything that produces a flag.
 636
 637   SDOperand Ops[] = { Op };
 638   FoldingSetNodeID ID;
 639   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
 640   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 641 }
 642
 643 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 644 /// were replaced with those specified.  If this node is never memoized,
 645 /// return null, otherwise return a pointer to the slot it would take.  If a
 646 /// node already exists with these operands, the slot will be non-null.
 647 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
 648                                            SDOperand Op1, SDOperand Op2,
 649                                            void *&InsertPos) {
 650   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 651     return 0;    // Never add these nodes.
 652
 653   // Check that remaining values produced are not flags.
 654   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 655     if (N->getValueType(i) == MVT::Flag)
 656       return 0;   // Never CSE anything that produces a flag.
 657
 658   SDOperand Ops[] = { Op1, Op2 };
 659   FoldingSetNodeID ID;
 660   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
 661   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 662 }
 663
 664
 665 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 666 /// were replaced with those specified.  If this node is never memoized,
 667 /// return null, otherwise return a pointer to the slot it would take.  If a
 668 /// node already exists with these operands, the slot will be non-null.
 669 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
 670                                            SDOperandPtr Ops,unsigned NumOps,
 671                                            void *&InsertPos) {
 672   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 673     return 0;    // Never add these nodes.
 674
 675   // Check that remaining values produced are not flags.
 676   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 677     if (N->getValueType(i) == MVT::Flag)
 678       return 0;   // Never CSE anything that produces a flag.
 679
 680   FoldingSetNodeID ID;
 681   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
 682
 683   if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
 684     ID.AddInteger(LD->getAddressingMode());
 685     ID.AddInteger(LD->getExtensionType());
 686     ID.AddInteger((unsigned int)(LD->getMemoryVT()));
 687     ID.AddInteger(LD->getAlignment());
 688     ID.AddInteger(LD->isVolatile());
 689   } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
 690     ID.AddInteger(ST->getAddressingMode());
 691     ID.AddInteger(ST->isTruncatingStore());
 692     ID.AddInteger((unsigned int)(ST->getMemoryVT()));
 693     ID.AddInteger(ST->getAlignment());
 694     ID.AddInteger(ST->isVolatile());
 695   }
 696
 697   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 698 }
 699
 700
 701 SelectionDAG::~SelectionDAG() {
 702   while (!AllNodes.empty()) {
 703     SDNode *N = AllNodes.begin();
 704     N->SetNextInBucket(0);
 705     if (N->OperandsNeedDelete) {
 706       delete [] N->OperandList;
 707     }
 708     N->OperandList = 0;
 709     N->NumOperands = 0;
 710     AllNodes.pop_front();
 711   }
 712 }
 713
 714 SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) {
 715   if (Op.getValueType() == VT) return Op;
 716   APInt Imm = APInt::getLowBitsSet(Op.getValueSizeInBits(),
 717                                    MVT::getSizeInBits(VT));
 718   return getNode(ISD::AND, Op.getValueType(), Op,
 719                  getConstant(Imm, Op.getValueType()));
 720 }
 721
 722 SDOperand SelectionDAG::getString(const std::string &Val) {
 723   StringSDNode *&N = StringNodes[Val];
 724   if (!N) {
 725     N = new StringSDNode(Val);
 726     AllNodes.push_back(N);
 727   }
 728   return SDOperand(N, 0);
 729 }
 730
 731 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT, bool isT) {
 732   MVT::ValueType EltVT =
 733     MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT;
 734
 735   return getConstant(APInt(MVT::getSizeInBits(EltVT), Val), VT, isT);
 736 }
 737
 738 SDOperand SelectionDAG::getConstant(const APInt &Val, MVT::ValueType VT, bool isT) {
 739   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 740
 741   MVT::ValueType EltVT =
 742     MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT;
 743
 744   assert(Val.getBitWidth() == MVT::getSizeInBits(EltVT) &&
 745          "APInt size does not match type size!");
 746
 747   unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
 748   FoldingSetNodeID ID;
 749   AddNodeIDNode(ID, Opc, getVTList(EltVT), (SDOperand*)0, 0);
 750   ID.Add(Val);
 751   void *IP = 0;
 752   SDNode *N = NULL;
 753   if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
 754     if (!MVT::isVector(VT))
 755       return SDOperand(N, 0);
 756   if (!N) {
 757     N = new ConstantSDNode(isT, Val, EltVT);
 758     CSEMap.InsertNode(N, IP);
 759     AllNodes.push_back(N);
 760   }
 761
 762   SDOperand Result(N, 0);
 763   if (MVT::isVector(VT)) {
 764     SmallVector<SDOperand, 8> Ops;
 765     Ops.assign(MVT::getVectorNumElements(VT), Result);
 766     Result = getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
 767   }
 768   return Result;
 769 }
 770
 771 SDOperand SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
 772   return getConstant(Val, TLI.getPointerTy(), isTarget);
 773 }
 774
 775
 776 SDOperand SelectionDAG::getConstantFP(const APFloat& V, MVT::ValueType VT,
 777                                       bool isTarget) {
 778   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
 779
 780   MVT::ValueType EltVT =
 781     MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT;
 782
 783   // Do the map lookup using the actual bit pattern for the floating point
 784   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
 785   // we don't have issues with SNANs.
 786   unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
 787   FoldingSetNodeID ID;
 788   AddNodeIDNode(ID, Opc, getVTList(EltVT), (SDOperand*)0, 0);
 789   ID.Add(V);
 790   void *IP = 0;
 791   SDNode *N = NULL;
 792   if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
 793     if (!MVT::isVector(VT))
 794       return SDOperand(N, 0);
 795   if (!N) {
 796     N = new ConstantFPSDNode(isTarget, V, EltVT);
 797     CSEMap.InsertNode(N, IP);
 798     AllNodes.push_back(N);
 799   }
 800
 801   SDOperand Result(N, 0);
 802   if (MVT::isVector(VT)) {
 803     SmallVector<SDOperand, 8> Ops;
 804     Ops.assign(MVT::getVectorNumElements(VT), Result);
 805     Result = getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
 806   }
 807   return Result;
 808 }
 809
 810 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT,
 811                                       bool isTarget) {
 812   MVT::ValueType EltVT =
 813     MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT;
 814   if (EltVT==MVT::f32)
 815     return getConstantFP(APFloat((float)Val), VT, isTarget);
 816   else
 817     return getConstantFP(APFloat(Val), VT, isTarget);
 818 }
 819
 820 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 821                                          MVT::ValueType VT, int Offset,
 822                                          bool isTargetGA) {
 823   unsigned Opc;
 824
 825   const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
 826   if (!GVar) {
 827     // If GV is an alias then use the aliasee for determining thread-localness.
 828     if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
 829       GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal());
 830   }
 831
 832   if (GVar && GVar->isThreadLocal())
 833     Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
 834   else
 835     Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
 836
 837   FoldingSetNodeID ID;
 838   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 839   ID.AddPointer(GV);
 840   ID.AddInteger(Offset);
 841   void *IP = 0;
 842   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 843    return SDOperand(E, 0);
 844   SDNode *N = new GlobalAddressSDNode(isTargetGA, GV, VT, Offset);
 845   CSEMap.InsertNode(N, IP);
 846   AllNodes.push_back(N);
 847   return SDOperand(N, 0);
 848 }
 849
 850 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT,
 851                                       bool isTarget) {
 852   unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
 853   FoldingSetNodeID ID;
 854   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 855   ID.AddInteger(FI);
 856   void *IP = 0;
 857   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 858     return SDOperand(E, 0);
 859   SDNode *N = new FrameIndexSDNode(FI, VT, isTarget);
 860   CSEMap.InsertNode(N, IP);
 861   AllNodes.push_back(N);
 862   return SDOperand(N, 0);
 863 }
 864
 865 SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){
 866   unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
 867   FoldingSetNodeID ID;
 868   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 869   ID.AddInteger(JTI);
 870   void *IP = 0;
 871   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 872     return SDOperand(E, 0);
 873   SDNode *N = new JumpTableSDNode(JTI, VT, isTarget);
 874   CSEMap.InsertNode(N, IP);
 875   AllNodes.push_back(N);
 876   return SDOperand(N, 0);
 877 }
 878
 879 SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT,
 880                                         unsigned Alignment, int Offset,
 881                                         bool isTarget) {
 882   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
 883   FoldingSetNodeID ID;
 884   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 885   ID.AddInteger(Alignment);
 886   ID.AddInteger(Offset);
 887   ID.AddPointer(C);
 888   void *IP = 0;
 889   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 890     return SDOperand(E, 0);
 891   SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
 892   CSEMap.InsertNode(N, IP);
 893   AllNodes.push_back(N);
 894   return SDOperand(N, 0);
 895 }
 896
 897
 898 SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C,
 899                                         MVT::ValueType VT,
 900                                         unsigned Alignment, int Offset,
 901                                         bool isTarget) {
 902   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
 903   FoldingSetNodeID ID;
 904   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 905   ID.AddInteger(Alignment);
 906   ID.AddInteger(Offset);
 907   C->AddSelectionDAGCSEId(ID);
 908   void *IP = 0;
 909   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 910     return SDOperand(E, 0);
 911   SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
 912   CSEMap.InsertNode(N, IP);
 913   AllNodes.push_back(N);
 914   return SDOperand(N, 0);
 915 }
 916
 917
 918 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
 919   FoldingSetNodeID ID;
 920   AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), (SDOperand*)0, 0);
 921   ID.AddPointer(MBB);
 922   void *IP = 0;
 923   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 924     return SDOperand(E, 0);
 925   SDNode *N = new BasicBlockSDNode(MBB);
 926   CSEMap.InsertNode(N, IP);
 927   AllNodes.push_back(N);
 928   return SDOperand(N, 0);
 929 }
 930
 931 SDOperand SelectionDAG::getArgFlags(ISD::ArgFlagsTy Flags) {
 932   FoldingSetNodeID ID;
 933   AddNodeIDNode(ID, ISD::ARG_FLAGS, getVTList(MVT::Other), (SDOperand*)0, 0);
 934   ID.AddInteger(Flags.getRawBits());
 935   void *IP = 0;
 936   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 937     return SDOperand(E, 0);
 938   SDNode *N = new ARG_FLAGSSDNode(Flags);
 939   CSEMap.InsertNode(N, IP);
 940   AllNodes.push_back(N);
 941   return SDOperand(N, 0);
 942 }
 943
 944 SDOperand SelectionDAG::getValueType(MVT::ValueType VT) {
 945   if (!MVT::isExtendedVT(VT) && (unsigned)VT >= ValueTypeNodes.size())
 946     ValueTypeNodes.resize(VT+1);
 947
 948   SDNode *&N = MVT::isExtendedVT(VT) ?
 949     ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT];
 950
 951   if (N) return SDOperand(N, 0);
 952   N = new VTSDNode(VT);
 953   AllNodes.push_back(N);
 954   return SDOperand(N, 0);
 955 }
 956
 957 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
 958   SDNode *&N = ExternalSymbols[Sym];
 959   if (N) return SDOperand(N, 0);
 960   N = new ExternalSymbolSDNode(false, Sym, VT);
 961   AllNodes.push_back(N);
 962   return SDOperand(N, 0);
 963 }
 964
 965 SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym,
 966                                                 MVT::ValueType VT) {
 967   SDNode *&N = TargetExternalSymbols[Sym];
 968   if (N) return SDOperand(N, 0);
 969   N = new ExternalSymbolSDNode(true, Sym, VT);
 970   AllNodes.push_back(N);
 971   return SDOperand(N, 0);
 972 }
 973
 974 SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
 975   if ((unsigned)Cond >= CondCodeNodes.size())
 976     CondCodeNodes.resize(Cond+1);
 977
 978   if (CondCodeNodes[Cond] == 0) {
 979     CondCodeNodes[Cond] = new CondCodeSDNode(Cond);
 980     AllNodes.push_back(CondCodeNodes[Cond]);
 981   }
 982   return SDOperand(CondCodeNodes[Cond], 0);
 983 }
 984
 985 SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) {
 986   FoldingSetNodeID ID;
 987   AddNodeIDNode(ID, ISD::Register, getVTList(VT), (SDOperand*)0, 0);
 988   ID.AddInteger(RegNo);
 989   void *IP = 0;
 990   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 991     return SDOperand(E, 0);
 992   SDNode *N = new RegisterSDNode(RegNo, VT);
 993   CSEMap.InsertNode(N, IP);
 994   AllNodes.push_back(N);
 995   return SDOperand(N, 0);
 996 }
 997
 998 SDOperand SelectionDAG::getSrcValue(const Value *V) {
 999   assert((!V || isa<PointerType>(V->getType())) &&
1000          "SrcValue is not a pointer?");
1001
1002   FoldingSetNodeID ID;
1003   AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), (SDOperand*)0, 0);
1004   ID.AddPointer(V);
1005
1006   void *IP = 0;
1007   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1008     return SDOperand(E, 0);
1009
1010   SDNode *N = new SrcValueSDNode(V);
1011   CSEMap.InsertNode(N, IP);
1012   AllNodes.push_back(N);
1013   return SDOperand(N, 0);
1014 }
1015
1016 SDOperand SelectionDAG::getMemOperand(const MachineMemOperand &MO) {
1017   const Value *v = MO.getValue();
1018   assert((!v || isa<PointerType>(v->getType())) &&
1019          "SrcValue is not a pointer?");
1020
1021   FoldingSetNodeID ID;
1022   AddNodeIDNode(ID, ISD::MEMOPERAND, getVTList(MVT::Other), (SDOperand*)0, 0);
1023   ID.AddPointer(v);
1024   ID.AddInteger(MO.getFlags());
1025   ID.AddInteger(MO.getOffset());
1026   ID.AddInteger(MO.getSize());
1027   ID.AddInteger(MO.getAlignment());
1028
1029   void *IP = 0;
1030   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1031     return SDOperand(E, 0);
1032
1033   SDNode *N = new MemOperandSDNode(MO);
1034   CSEMap.InsertNode(N, IP);
1035   AllNodes.push_back(N);
1036   return SDOperand(N, 0);
1037 }
1038
1039 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1040 /// specified value type.
1041 SDOperand SelectionDAG::CreateStackTemporary(MVT::ValueType VT) {
1042   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1043   unsigned ByteSize = MVT::getSizeInBits(VT)/8;
1044   const Type *Ty = MVT::getTypeForValueType(VT);
1045   unsigned StackAlign = (unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty);
1046   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign);
1047   return getFrameIndex(FrameIdx, TLI.getPointerTy());
1048 }
1049
1050
1051 SDOperand SelectionDAG::FoldSetCC(MVT::ValueType VT, SDOperand N1,
1052                                   SDOperand N2, ISD::CondCode Cond) {
1053   // These setcc operations always fold.
1054   switch (Cond) {
1055   default: break;
1056   case ISD::SETFALSE:
1057   case ISD::SETFALSE2: return getConstant(0, VT);
1058   case ISD::SETTRUE:
1059   case ISD::SETTRUE2:  return getConstant(1, VT);
1060
1061   case ISD::SETOEQ:
1062   case ISD::SETOGT:
1063   case ISD::SETOGE:
1064   case ISD::SETOLT:
1065   case ISD::SETOLE:
1066   case ISD::SETONE:
1067   case ISD::SETO:
1068   case ISD::SETUO:
1069   case ISD::SETUEQ:
1070   case ISD::SETUNE:
1071     assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!");
1072     break;
1073   }
1074
1075   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
1076     const APInt &C2 = N2C->getAPIntValue();
1077     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
1078       const APInt &C1 = N1C->getAPIntValue();
1079
1080       switch (Cond) {
1081       default: assert(0 && "Unknown integer setcc!");
1082       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
1083       case ISD::SETNE:  return getConstant(C1 != C2, VT);
1084       case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1085       case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1086       case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1087       case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1088       case ISD::SETLT:  return getConstant(C1.slt(C2), VT);
1089       case ISD::SETGT:  return getConstant(C1.sgt(C2), VT);
1090       case ISD::SETLE:  return getConstant(C1.sle(C2), VT);
1091       case ISD::SETGE:  return getConstant(C1.sge(C2), VT);
1092       }
1093     }
1094   }
1095   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) {
1096     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
1097       // No compile time operations on this type yet.
1098       if (N1C->getValueType(0) == MVT::ppcf128)
1099         return SDOperand();
1100
1101       APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1102       switch (Cond) {
1103       default: break;
1104       case ISD::SETEQ:  if (R==APFloat::cmpUnordered)
1105                           return getNode(ISD::UNDEF, VT);
1106                         // fall through
1107       case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1108       case ISD::SETNE:  if (R==APFloat::cmpUnordered)
1109                           return getNode(ISD::UNDEF, VT);
1110                         // fall through
1111       case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1112                                            R==APFloat::cmpLessThan, VT);
1113       case ISD::SETLT:  if (R==APFloat::cmpUnordered)
1114                           return getNode(ISD::UNDEF, VT);
1115                         // fall through
1116       case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1117       case ISD::SETGT:  if (R==APFloat::cmpUnordered)
1118                           return getNode(ISD::UNDEF, VT);
1119                         // fall through
1120       case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1121       case ISD::SETLE:  if (R==APFloat::cmpUnordered)
1122                           return getNode(ISD::UNDEF, VT);
1123                         // fall through
1124       case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1125                                            R==APFloat::cmpEqual, VT);
1126       case ISD::SETGE:  if (R==APFloat::cmpUnordered)
1127                           return getNode(ISD::UNDEF, VT);
1128                         // fall through
1129       case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1130                                            R==APFloat::cmpEqual, VT);
1131       case ISD::SETO:   return getConstant(R!=APFloat::cmpUnordered, VT);
1132       case ISD::SETUO:  return getConstant(R==APFloat::cmpUnordered, VT);
1133       case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1134                                            R==APFloat::cmpEqual, VT);
1135       case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1136       case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1137                                            R==APFloat::cmpLessThan, VT);
1138       case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1139                                            R==APFloat::cmpUnordered, VT);
1140       case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1141       case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1142       }
1143     } else {
1144       // Ensure that the constant occurs on the RHS.
1145       return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1146     }
1147   }
1148
1149   // Could not fold it.
1150   return SDOperand();
1151 }
1152
1153 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
1154 /// use this predicate to simplify operations downstream.
1155 bool SelectionDAG::SignBitIsZero(SDOperand Op, unsigned Depth) const {
1156   unsigned BitWidth = Op.getValueSizeInBits();
1157   return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1158 }
1159
1160 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
1161 /// this predicate to simplify operations downstream.  Mask is known to be zero
1162 /// for bits that V cannot have.
1163 bool SelectionDAG::MaskedValueIsZero(SDOperand Op, const APInt &Mask,
1164                                      unsigned Depth) const {
1165   APInt KnownZero, KnownOne;
1166   ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1167   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1168   return (KnownZero & Mask) == Mask;
1169 }
1170
1171 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1172 /// known to be either zero or one and return them in the KnownZero/KnownOne
1173 /// bitsets.  This code only analyzes bits in Mask, in order to short-circuit
1174 /// processing.
1175 void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask,
1176                                      APInt &KnownZero, APInt &KnownOne,
1177                                      unsigned Depth) const {
1178   unsigned BitWidth = Mask.getBitWidth();
1179   assert(BitWidth == MVT::getSizeInBits(Op.getValueType()) &&
1180          "Mask size mismatches value type size!");
1181
1182   KnownZero = KnownOne = APInt(BitWidth, 0);   // Don't know anything.
1183   if (Depth == 6 || Mask == 0)
1184     return;  // Limit search depth.
1185
1186   APInt KnownZero2, KnownOne2;
1187
1188   switch (Op.getOpcode()) {
1189   case ISD::Constant:
1190     // We know all of the bits for a constant!
1191     KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue() & Mask;
1192     KnownZero = ~KnownOne & Mask;
1193     return;
1194   case ISD::AND:
1195     // If either the LHS or the RHS are Zero, the result is zero.
1196     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1197     ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownZero,
1198                       KnownZero2, KnownOne2, Depth+1);
1199     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1200     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1201
1202     // Output known-1 bits are only known if set in both the LHS & RHS.
1203     KnownOne &= KnownOne2;
1204     // Output known-0 are known to be clear if zero in either the LHS | RHS.
1205     KnownZero |= KnownZero2;
1206     return;
1207   case ISD::OR:
1208     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1209     ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownOne,
1210                       KnownZero2, KnownOne2, Depth+1);
1211     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1212     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1213
1214     // Output known-0 bits are only known if clear in both the LHS & RHS.
1215     KnownZero &= KnownZero2;
1216     // Output known-1 are known to be set if set in either the LHS | RHS.
1217     KnownOne |= KnownOne2;
1218     return;
1219   case ISD::XOR: {
1220     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1221     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
1222     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1223     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1224
1225     // Output known-0 bits are known if clear or set in both the LHS & RHS.
1226     APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1227     // Output known-1 are known to be set if set in only one of the LHS, RHS.
1228     KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1229     KnownZero = KnownZeroOut;
1230     return;
1231   }
1232   case ISD::MUL: {
1233     APInt Mask2 = APInt::getAllOnesValue(BitWidth);
1234     ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero, KnownOne, Depth+1);
1235     ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
1236     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1237     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1238
1239     // If low bits are zero in either operand, output low known-0 bits.
1240     // Also compute a conserative estimate for high known-0 bits.
1241     // More trickiness is possible, but this is sufficient for the
1242     // interesting case of alignment computation.
1243     KnownOne.clear();
1244     unsigned TrailZ = KnownZero.countTrailingOnes() +
1245                       KnownZero2.countTrailingOnes();
1246     unsigned LeadZ =  std::max(KnownZero.countLeadingOnes() +
1247                                KnownZero2.countLeadingOnes() +
1248                                1, BitWidth) - BitWidth;
1249
1250     TrailZ = std::min(TrailZ, BitWidth);
1251     LeadZ = std::min(LeadZ, BitWidth);
1252     KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) |
1253                 APInt::getHighBitsSet(BitWidth, LeadZ);
1254     KnownZero &= Mask;
1255     return;
1256   }
1257   case ISD::UDIV: {
1258     // For the purposes of computing leading zeros we can conservatively
1259     // treat a udiv as a logical right shift by the power of 2 known to
1260     // be greater than the denominator.
1261     APInt AllOnes = APInt::getAllOnesValue(BitWidth);
1262     ComputeMaskedBits(Op.getOperand(0),
1263                       AllOnes, KnownZero2, KnownOne2, Depth+1);
1264     unsigned LeadZ = KnownZero2.countLeadingOnes();
1265
1266     KnownOne2.clear();
1267     KnownZero2.clear();
1268     ComputeMaskedBits(Op.getOperand(1),
1269                       AllOnes, KnownZero2, KnownOne2, Depth+1);
1270     LeadZ = std::min(BitWidth,
1271                      LeadZ + BitWidth - KnownOne2.countLeadingZeros());
1272
1273     KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask;
1274     return;
1275   }
1276   case ISD::SELECT:
1277     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
1278     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
1279     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1280     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1281
1282     // Only known if known in both the LHS and RHS.
1283     KnownOne &= KnownOne2;
1284     KnownZero &= KnownZero2;
1285     return;
1286   case ISD::SELECT_CC:
1287     ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1);
1288     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1);
1289     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1290     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1291
1292     // Only known if known in both the LHS and RHS.
1293     KnownOne &= KnownOne2;
1294     KnownZero &= KnownZero2;
1295     return;
1296   case ISD::SETCC:
1297     // If we know the result of a setcc has the top bits zero, use this info.
1298     if (TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult &&
1299         BitWidth > 1)
1300       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1301     return;
1302   case ISD::SHL:
1303     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
1304     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1305       unsigned ShAmt = SA->getValue();
1306
1307       // If the shift count is an invalid immediate, don't do anything.
1308       if (ShAmt >= BitWidth)
1309         return;
1310
1311       ComputeMaskedBits(Op.getOperand(0), Mask.lshr(ShAmt),
1312                         KnownZero, KnownOne, Depth+1);
1313       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1314       KnownZero <<= ShAmt;
1315       KnownOne  <<= ShAmt;
1316       // low bits known zero.
1317       KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1318     }
1319     return;
1320   case ISD::SRL:
1321     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
1322     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1323       unsigned ShAmt = SA->getValue();
1324
1325       // If the shift count is an invalid immediate, don't do anything.
1326       if (ShAmt >= BitWidth)
1327         return;
1328
1329       ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt),
1330                         KnownZero, KnownOne, Depth+1);
1331       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1332       KnownZero = KnownZero.lshr(ShAmt);
1333       KnownOne  = KnownOne.lshr(ShAmt);
1334
1335       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1336       KnownZero |= HighBits;  // High bits known zero.
1337     }
1338     return;
1339   case ISD::SRA:
1340     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1341       unsigned ShAmt = SA->getValue();
1342
1343       // If the shift count is an invalid immediate, don't do anything.
1344       if (ShAmt >= BitWidth)
1345         return;
1346
1347       APInt InDemandedMask = (Mask << ShAmt);
1348       // If any of the demanded bits are produced by the sign extension, we also
1349       // demand the input sign bit.
1350       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1351       if (HighBits.getBoolValue())
1352         InDemandedMask |= APInt::getSignBit(BitWidth);
1353
1354       ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne,
1355                         Depth+1);
1356       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1357       KnownZero = KnownZero.lshr(ShAmt);
1358       KnownOne  = KnownOne.lshr(ShAmt);
1359
1360       // Handle the sign bits.
1361       APInt SignBit = APInt::getSignBit(BitWidth);
1362       SignBit = SignBit.lshr(ShAmt);  // Adjust to where it is now in the mask.
1363
1364       if (KnownZero.intersects(SignBit)) {
1365         KnownZero |= HighBits;  // New bits are known zero.
1366       } else if (KnownOne.intersects(SignBit)) {
1367         KnownOne  |= HighBits;  // New bits are known one.
1368       }
1369     }
1370     return;
1371   case ISD::SIGN_EXTEND_INREG: {
1372     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1373     unsigned EBits = MVT::getSizeInBits(EVT);
1374
1375     // Sign extension.  Compute the demanded bits in the result that are not
1376     // present in the input.
1377     APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits) & Mask;
1378
1379     APInt InSignBit = APInt::getSignBit(EBits);
1380     APInt InputDemandedBits = Mask & APInt::getLowBitsSet(BitWidth, EBits);
1381
1382     // If the sign extended bits are demanded, we know that the sign
1383     // bit is demanded.
1384     InSignBit.zext(BitWidth);
1385     if (NewBits.getBoolValue())
1386       InputDemandedBits |= InSignBit;
1387
1388     ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
1389                       KnownZero, KnownOne, Depth+1);
1390     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1391
1392     // If the sign bit of the input is known set or clear, then we know the
1393     // top bits of the result.
1394     if (KnownZero.intersects(InSignBit)) {         // Input sign bit known clear
1395       KnownZero |= NewBits;
1396       KnownOne  &= ~NewBits;
1397     } else if (KnownOne.intersects(InSignBit)) {   // Input sign bit known set
1398       KnownOne  |= NewBits;
1399       KnownZero &= ~NewBits;
1400     } else {                              // Input sign bit unknown
1401       KnownZero &= ~NewBits;
1402       KnownOne  &= ~NewBits;
1403     }
1404     return;
1405   }
1406   case ISD::CTTZ:
1407   case ISD::CTLZ:
1408   case ISD::CTPOP: {
1409     unsigned LowBits = Log2_32(BitWidth)+1;
1410     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1411     KnownOne  = APInt(BitWidth, 0);
1412     return;
1413   }
1414   case ISD::LOAD: {
1415     if (ISD::isZEXTLoad(Op.Val)) {
1416       LoadSDNode *LD = cast<LoadSDNode>(Op);
1417       MVT::ValueType VT = LD->getMemoryVT();
1418       unsigned MemBits = MVT::getSizeInBits(VT);
1419       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits) & Mask;
1420     }
1421     return;
1422   }
1423   case ISD::ZERO_EXTEND: {
1424     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1425     unsigned InBits = MVT::getSizeInBits(InVT);
1426     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1427     APInt InMask    = Mask;
1428     InMask.trunc(InBits);
1429     KnownZero.trunc(InBits);
1430     KnownOne.trunc(InBits);
1431     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1432     KnownZero.zext(BitWidth);
1433     KnownOne.zext(BitWidth);
1434     KnownZero |= NewBits;
1435     return;
1436   }
1437   case ISD::SIGN_EXTEND: {
1438     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1439     unsigned InBits = MVT::getSizeInBits(InVT);
1440     APInt InSignBit = APInt::getSignBit(InBits);
1441     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1442     APInt InMask = Mask;
1443     InMask.trunc(InBits);
1444
1445     // If any of the sign extended bits are demanded, we know that the sign
1446     // bit is demanded. Temporarily set this bit in the mask for our callee.
1447     if (NewBits.getBoolValue())
1448       InMask |= InSignBit;
1449
1450     KnownZero.trunc(InBits);
1451     KnownOne.trunc(InBits);
1452     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1453
1454     // Note if the sign bit is known to be zero or one.
1455     bool SignBitKnownZero = KnownZero.isNegative();
1456     bool SignBitKnownOne  = KnownOne.isNegative();
1457     assert(!(SignBitKnownZero && SignBitKnownOne) &&
1458            "Sign bit can't be known to be both zero and one!");
1459
1460     // If the sign bit wasn't actually demanded by our caller, we don't
1461     // want it set in the KnownZero and KnownOne result values. Reset the
1462     // mask and reapply it to the result values.
1463     InMask = Mask;
1464     InMask.trunc(InBits);
1465     KnownZero &= InMask;
1466     KnownOne  &= InMask;
1467
1468     KnownZero.zext(BitWidth);
1469     KnownOne.zext(BitWidth);
1470
1471     // If the sign bit is known zero or one, the top bits match.
1472     if (SignBitKnownZero)
1473       KnownZero |= NewBits;
1474     else if (SignBitKnownOne)
1475       KnownOne  |= NewBits;
1476     return;
1477   }
1478   case ISD::ANY_EXTEND: {
1479     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1480     unsigned InBits = MVT::getSizeInBits(InVT);
1481     APInt InMask = Mask;
1482     InMask.trunc(InBits);
1483     KnownZero.trunc(InBits);
1484     KnownOne.trunc(InBits);
1485     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1486     KnownZero.zext(BitWidth);
1487     KnownOne.zext(BitWidth);
1488     return;
1489   }
1490   case ISD::TRUNCATE: {
1491     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1492     unsigned InBits = MVT::getSizeInBits(InVT);
1493     APInt InMask = Mask;
1494     InMask.zext(InBits);
1495     KnownZero.zext(InBits);
1496     KnownOne.zext(InBits);
1497     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1498     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1499     KnownZero.trunc(BitWidth);
1500     KnownOne.trunc(BitWidth);
1501     break;
1502   }
1503   case ISD::AssertZext: {
1504     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1505     APInt InMask = APInt::getLowBitsSet(BitWidth, MVT::getSizeInBits(VT));
1506     ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
1507                       KnownOne, Depth+1);
1508     KnownZero |= (~InMask) & Mask;
1509     return;
1510   }
1511   case ISD::FGETSIGN:
1512     // All bits are zero except the low bit.
1513     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1514     return;
1515
1516   case ISD::SUB: {
1517     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
1518       // We know that the top bits of C-X are clear if X contains less bits
1519       // than C (i.e. no wrap-around can happen).  For example, 20-X is
1520       // positive if we can prove that X is >= 0 and < 16.
1521       if (CLHS->getAPIntValue().isNonNegative()) {
1522         unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
1523         // NLZ can't be BitWidth with no sign bit
1524         APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
1525         ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero2, KnownOne2,
1526                           Depth+1);
1527
1528         // If all of the MaskV bits are known to be zero, then we know the
1529         // output top bits are zero, because we now know that the output is
1530         // from [0-C].
1531         if ((KnownZero2 & MaskV) == MaskV) {
1532           unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
1533           // Top bits known zero.
1534           KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask;
1535         }
1536       }
1537     }
1538   }
1539   // fall through
1540   case ISD::ADD: {
1541     // Output known-0 bits are known if clear or set in both the low clear bits
1542     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
1543     // low 3 bits clear.
1544     APInt Mask2 = APInt::getLowBitsSet(BitWidth, Mask.countTrailingOnes());
1545     ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
1546     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1547     unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
1548
1549     ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero2, KnownOne2, Depth+1);
1550     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1551     KnownZeroOut = std::min(KnownZeroOut,
1552                             KnownZero2.countTrailingOnes());
1553
1554     KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
1555     return;
1556   }
1557   case ISD::SREM:
1558     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1559       APInt RA = Rem->getAPIntValue();
1560       if (RA.isPowerOf2() || (-RA).isPowerOf2()) {
1561         APInt LowBits = RA.isStrictlyPositive() ? ((RA - 1) | RA) : ~RA;
1562         APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
1563         ComputeMaskedBits(Op.getOperand(0), Mask2,KnownZero2,KnownOne2,Depth+1);
1564
1565         // The sign of a remainder is equal to the sign of the first
1566         // operand (zero being positive).
1567         if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
1568           KnownZero2 |= ~LowBits;
1569         else if (KnownOne2[BitWidth-1])
1570           KnownOne2 |= ~LowBits;
1571
1572         KnownZero |= KnownZero2 & Mask;
1573         KnownOne |= KnownOne2 & Mask;
1574
1575         assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
1576       }
1577     }
1578     return;
1579   case ISD::UREM: {
1580     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1581       APInt RA = Rem->getAPIntValue();
1582       if (RA.isStrictlyPositive() && RA.isPowerOf2()) {
1583         APInt LowBits = (RA - 1) | RA;
1584         APInt Mask2 = LowBits & Mask;
1585         KnownZero |= ~LowBits & Mask;
1586         ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero, KnownOne,Depth+1);
1587         assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
1588         break;
1589       }
1590     }
1591
1592     // Since the result is less than or equal to either operand, any leading
1593     // zero bits in either operand must also exist in the result.
1594     APInt AllOnes = APInt::getAllOnesValue(BitWidth);
1595     ComputeMaskedBits(Op.getOperand(0), AllOnes, KnownZero, KnownOne,
1596                       Depth+1);
1597     ComputeMaskedBits(Op.getOperand(1), AllOnes, KnownZero2, KnownOne2,
1598                       Depth+1);
1599
1600     uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
1601                                 KnownZero2.countLeadingOnes());
1602     KnownOne.clear();
1603     KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask;
1604     return;
1605   }
1606   default:
1607     // Allow the target to implement this method for its nodes.
1608     if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
1609   case ISD::INTRINSIC_WO_CHAIN:
1610   case ISD::INTRINSIC_W_CHAIN:
1611   case ISD::INTRINSIC_VOID:
1612       TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this);
1613     }
1614     return;
1615   }
1616 }
1617
1618 /// ComputeNumSignBits - Return the number of times the sign bit of the
1619 /// register is replicated into the other bits.  We know that at least 1 bit
1620 /// is always equal to the sign bit (itself), but other cases can give us
1621 /// information.  For example, immediately after an "SRA X, 2", we know that
1622 /// the top 3 bits are all equal to each other, so we return 3.
1623 unsigned SelectionDAG::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{
1624   MVT::ValueType VT = Op.getValueType();
1625   assert(MVT::isInteger(VT) && "Invalid VT!");
1626   unsigned VTBits = MVT::getSizeInBits(VT);
1627   unsigned Tmp, Tmp2;
1628
1629   if (Depth == 6)
1630     return 1;  // Limit search depth.
1631
1632   switch (Op.getOpcode()) {
1633   default: break;
1634   case ISD::AssertSext:
1635     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1636     return VTBits-Tmp+1;
1637   case ISD::AssertZext:
1638     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1639     return VTBits-Tmp;
1640
1641   case ISD::Constant: {
1642     const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
1643     // If negative, return # leading ones.
1644     if (Val.isNegative())
1645       return Val.countLeadingOnes();
1646
1647     // Return # leading zeros.
1648     return Val.countLeadingZeros();
1649   }
1650
1651   case ISD::SIGN_EXTEND:
1652     Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType());
1653     return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
1654
1655   case ISD::SIGN_EXTEND_INREG:
1656     // Max of the input and what this extends.
1657     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1658     Tmp = VTBits-Tmp+1;
1659
1660     Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1661     return std::max(Tmp, Tmp2);
1662
1663   case ISD::SRA:
1664     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1665     // SRA X, C   -> adds C sign bits.
1666     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1667       Tmp += C->getValue();
1668       if (Tmp > VTBits) Tmp = VTBits;
1669     }
1670     return Tmp;
1671   case ISD::SHL:
1672     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1673       // shl destroys sign bits.
1674       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1675       if (C->getValue() >= VTBits ||      // Bad shift.
1676           C->getValue() >= Tmp) break;    // Shifted all sign bits out.
1677       return Tmp - C->getValue();
1678     }
1679     break;
1680   case ISD::AND:
1681   case ISD::OR:
1682   case ISD::XOR:    // NOT is handled here.
1683     // Logical binary ops preserve the number of sign bits.
1684     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1685     if (Tmp == 1) return 1;  // Early out.
1686     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1687     return std::min(Tmp, Tmp2);
1688
1689   case ISD::SELECT:
1690     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1691     if (Tmp == 1) return 1;  // Early out.
1692     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1693     return std::min(Tmp, Tmp2);
1694
1695   case ISD::SETCC:
1696     // If setcc returns 0/-1, all bits are sign bits.
1697     if (TLI.getSetCCResultContents() ==
1698         TargetLowering::ZeroOrNegativeOneSetCCResult)
1699       return VTBits;
1700     break;
1701   case ISD::ROTL:
1702   case ISD::ROTR:
1703     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1704       unsigned RotAmt = C->getValue() & (VTBits-1);
1705
1706       // Handle rotate right by N like a rotate left by 32-N.
1707       if (Op.getOpcode() == ISD::ROTR)
1708         RotAmt = (VTBits-RotAmt) & (VTBits-1);
1709
1710       // If we aren't rotating out all of the known-in sign bits, return the
1711       // number that are left.  This handles rotl(sext(x), 1) for example.
1712       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1713       if (Tmp > RotAmt+1) return Tmp-RotAmt;
1714     }
1715     break;
1716   case ISD::ADD:
1717     // Add can have at most one carry bit.  Thus we know that the output
1718     // is, at worst, one more bit than the inputs.
1719     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1720     if (Tmp == 1) return 1;  // Early out.
1721
1722     // Special case decrementing a value (ADD X, -1):
1723     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1724       if (CRHS->isAllOnesValue()) {
1725         APInt KnownZero, KnownOne;
1726         APInt Mask = APInt::getAllOnesValue(VTBits);
1727         ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
1728
1729         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1730         // sign bits set.
1731         if ((KnownZero | APInt(VTBits, 1)) == Mask)
1732           return VTBits;
1733
1734         // If we are subtracting one from a positive number, there is no carry
1735         // out of the result.
1736         if (KnownZero.isNegative())
1737           return Tmp;
1738       }
1739
1740     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1741     if (Tmp2 == 1) return 1;
1742       return std::min(Tmp, Tmp2)-1;
1743     break;
1744
1745   case ISD::SUB:
1746     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1747     if (Tmp2 == 1) return 1;
1748
1749     // Handle NEG.
1750     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1751       if (CLHS->isNullValue()) {
1752         APInt KnownZero, KnownOne;
1753         APInt Mask = APInt::getAllOnesValue(VTBits);
1754         ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1755         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1756         // sign bits set.
1757         if ((KnownZero | APInt(VTBits, 1)) == Mask)
1758           return VTBits;
1759
1760         // If the input is known to be positive (the sign bit is known clear),
1761         // the output of the NEG has the same number of sign bits as the input.
1762         if (KnownZero.isNegative())
1763           return Tmp2;
1764
1765         // Otherwise, we treat this like a SUB.
1766       }
1767
1768     // Sub can have at most one carry bit.  Thus we know that the output
1769     // is, at worst, one more bit than the inputs.
1770     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1771     if (Tmp == 1) return 1;  // Early out.
1772       return std::min(Tmp, Tmp2)-1;
1773     break;
1774   case ISD::TRUNCATE:
1775     // FIXME: it's tricky to do anything useful for this, but it is an important
1776     // case for targets like X86.
1777     break;
1778   }
1779
1780   // Handle LOADX separately here. EXTLOAD case will fallthrough.
1781   if (Op.getOpcode() == ISD::LOAD) {
1782     LoadSDNode *LD = cast<LoadSDNode>(Op);
1783     unsigned ExtType = LD->getExtensionType();
1784     switch (ExtType) {
1785     default: break;
1786     case ISD::SEXTLOAD:    // '17' bits known
1787       Tmp = MVT::getSizeInBits(LD->getMemoryVT());
1788       return VTBits-Tmp+1;
1789     case ISD::ZEXTLOAD:    // '16' bits known
1790       Tmp = MVT::getSizeInBits(LD->getMemoryVT());
1791       return VTBits-Tmp;
1792     }
1793   }
1794
1795   // Allow the target to implement this method for its nodes.
1796   if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1797       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1798       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1799       Op.getOpcode() == ISD::INTRINSIC_VOID) {
1800     unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
1801     if (NumBits > 1) return NumBits;
1802   }
1803
1804   // Finally, if we can prove that the top bits of the result are 0's or 1's,
1805   // use this information.
1806   APInt KnownZero, KnownOne;
1807   APInt Mask = APInt::getAllOnesValue(VTBits);
1808   ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1809
1810   if (KnownZero.isNegative()) {        // sign bit is 0
1811     Mask = KnownZero;
1812   } else if (KnownOne.isNegative()) {  // sign bit is 1;
1813     Mask = KnownOne;
1814   } else {
1815     // Nothing known.
1816     return 1;
1817   }
1818
1819   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
1820   // the number of identical bits in the top of the input value.
1821   Mask = ~Mask;
1822   Mask <<= Mask.getBitWidth()-VTBits;
1823   // Return # leading zeros.  We use 'min' here in case Val was zero before
1824   // shifting.  We don't want to return '64' as for an i32 "0".
1825   return std::min(VTBits, Mask.countLeadingZeros());
1826 }
1827
1828
1829 bool SelectionDAG::isVerifiedDebugInfoDesc(SDOperand Op) const {
1830   GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
1831   if (!GA) return false;
1832   GlobalVariable *GV = dyn_cast<GlobalVariable>(GA->getGlobal());
1833   if (!GV) return false;
1834   MachineModuleInfo *MMI = getMachineModuleInfo();
1835   return MMI && MMI->hasDebugInfo() && MMI->isVerified(GV);
1836 }
1837
1838
1839 /// getNode - Gets or creates the specified node.
1840 ///
1841 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
1842   FoldingSetNodeID ID;
1843   AddNodeIDNode(ID, Opcode, getVTList(VT), (SDOperand*)0, 0);
1844   void *IP = 0;
1845   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1846     return SDOperand(E, 0);
1847   SDNode *N = new SDNode(Opcode, SDNode::getSDVTList(VT));
1848   CSEMap.InsertNode(N, IP);
1849
1850   AllNodes.push_back(N);
1851   return SDOperand(N, 0);
1852 }
1853
1854 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1855                                 SDOperand Operand) {
1856   // Constant fold unary operations with an integer constant operand.
1857   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
1858     const APInt &Val = C->getAPIntValue();
1859     unsigned BitWidth = MVT::getSizeInBits(VT);
1860     switch (Opcode) {
1861     default: break;
1862     case ISD::SIGN_EXTEND:
1863       return getConstant(APInt(Val).sextOrTrunc(BitWidth), VT);
1864     case ISD::ANY_EXTEND:
1865     case ISD::ZERO_EXTEND:
1866     case ISD::TRUNCATE:
1867       return getConstant(APInt(Val).zextOrTrunc(BitWidth), VT);
1868     case ISD::UINT_TO_FP:
1869     case ISD::SINT_TO_FP: {
1870       const uint64_t zero[] = {0, 0};
1871       // No compile time operations on this type.
1872       if (VT==MVT::ppcf128)
1873         break;
1874       APFloat apf = APFloat(APInt(BitWidth, 2, zero));
1875       (void)apf.convertFromAPInt(Val,
1876                                  Opcode==ISD::SINT_TO_FP,
1877                                  APFloat::rmNearestTiesToEven);
1878       return getConstantFP(apf, VT);
1879     }
1880     case ISD::BIT_CONVERT:
1881       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
1882         return getConstantFP(Val.bitsToFloat(), VT);
1883       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
1884         return getConstantFP(Val.bitsToDouble(), VT);
1885       break;
1886     case ISD::BSWAP:
1887       return getConstant(Val.byteSwap(), VT);
1888     case ISD::CTPOP:
1889       return getConstant(Val.countPopulation(), VT);
1890     case ISD::CTLZ:
1891       return getConstant(Val.countLeadingZeros(), VT);
1892     case ISD::CTTZ:
1893       return getConstant(Val.countTrailingZeros(), VT);
1894     }
1895   }
1896
1897   // Constant fold unary operations with a floating point constant operand.
1898   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) {
1899     APFloat V = C->getValueAPF();    // make copy
1900     if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
1901       switch (Opcode) {
1902       case ISD::FNEG:
1903         V.changeSign();
1904         return getConstantFP(V, VT);
1905       case ISD::FABS:
1906         V.clearSign();
1907         return getConstantFP(V, VT);
1908       case ISD::FP_ROUND:
1909       case ISD::FP_EXTEND:
1910         // This can return overflow, underflow, or inexact; we don't care.
1911         // FIXME need to be more flexible about rounding mode.
1912         (void)V.convert(*MVTToAPFloatSemantics(VT),
1913                         APFloat::rmNearestTiesToEven);
1914         return getConstantFP(V, VT);
1915       case ISD::FP_TO_SINT:
1916       case ISD::FP_TO_UINT: {
1917         integerPart x;
1918         assert(integerPartWidth >= 64);
1919         // FIXME need to be more flexible about rounding mode.
1920         APFloat::opStatus s = V.convertToInteger(&x, 64U,
1921                               Opcode==ISD::FP_TO_SINT,
1922                               APFloat::rmTowardZero);
1923         if (s==APFloat::opInvalidOp)     // inexact is OK, in fact usual
1924           break;
1925         return getConstant(x, VT);
1926       }
1927       case ISD::BIT_CONVERT:
1928         if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
1929           return getConstant((uint32_t)V.convertToAPInt().getZExtValue(), VT);
1930         else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
1931           return getConstant(V.convertToAPInt().getZExtValue(), VT);
1932         break;
1933       }
1934     }
1935   }
1936
1937   unsigned OpOpcode = Operand.Val->getOpcode();
1938   switch (Opcode) {
1939   case ISD::TokenFactor:
1940   case ISD::MERGE_VALUES:
1941     return Operand;         // Factor or merge of one node?  No need.
1942   case ISD::FP_ROUND: assert(0 && "Invalid method to make FP_ROUND node");
1943   case ISD::FP_EXTEND:
1944     assert(MVT::isFloatingPoint(VT) &&
1945            MVT::isFloatingPoint(Operand.getValueType()) && "Invalid FP cast!");
1946     if (Operand.getValueType() == VT) return Operand;  // noop conversion.
1947     if (Operand.getOpcode() == ISD::UNDEF)
1948       return getNode(ISD::UNDEF, VT);
1949     break;
1950   case ISD::SIGN_EXTEND:
1951     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1952            "Invalid SIGN_EXTEND!");
1953     if (Operand.getValueType() == VT) return Operand;   // noop extension
1954     assert(MVT::getSizeInBits(Operand.getValueType()) < MVT::getSizeInBits(VT)
1955            && "Invalid sext node, dst < src!");
1956     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
1957       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1958     break;
1959   case ISD::ZERO_EXTEND:
1960     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1961            "Invalid ZERO_EXTEND!");
1962     if (Operand.getValueType() == VT) return Operand;   // noop extension
1963     assert(MVT::getSizeInBits(Operand.getValueType()) < MVT::getSizeInBits(VT)
1964            && "Invalid zext node, dst < src!");
1965     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
1966       return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
1967     break;
1968   case ISD::ANY_EXTEND:
1969     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1970            "Invalid ANY_EXTEND!");
1971     if (Operand.getValueType() == VT) return Operand;   // noop extension
1972     assert(MVT::getSizeInBits(Operand.getValueType()) < MVT::getSizeInBits(VT)
1973            && "Invalid anyext node, dst < src!");
1974     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND)
1975       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
1976       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1977     break;
1978   case ISD::TRUNCATE:
1979     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1980            "Invalid TRUNCATE!");
1981     if (Operand.getValueType() == VT) return Operand;   // noop truncate
1982     assert(MVT::getSizeInBits(Operand.getValueType()) > MVT::getSizeInBits(VT)
1983            && "Invalid truncate node, src < dst!");
1984     if (OpOpcode == ISD::TRUNCATE)
1985       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1986     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
1987              OpOpcode == ISD::ANY_EXTEND) {
1988       // If the source is smaller than the dest, we still need an extend.
1989       if (MVT::getSizeInBits(Operand.Val->getOperand(0).getValueType())
1990           < MVT::getSizeInBits(VT))
1991         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1992       else if (MVT::getSizeInBits(Operand.Val->getOperand(0).getValueType())
1993                > MVT::getSizeInBits(VT))
1994         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1995       else
1996         return Operand.Val->getOperand(0);
1997     }
1998     break;
1999   case ISD::BIT_CONVERT:
2000     // Basic sanity checking.
2001     assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType())
2002            && "Cannot BIT_CONVERT between types of different sizes!");
2003     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
2004     if (OpOpcode == ISD::BIT_CONVERT)  // bitconv(bitconv(x)) -> bitconv(x)
2005       return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0));
2006     if (OpOpcode == ISD::UNDEF)
2007       return getNode(ISD::UNDEF, VT);
2008     break;
2009   case ISD::SCALAR_TO_VECTOR:
2010     assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) &&
2011            MVT::getVectorElementType(VT) == Operand.getValueType() &&
2012            "Illegal SCALAR_TO_VECTOR node!");
2013     if (OpOpcode == ISD::UNDEF)
2014       return getNode(ISD::UNDEF, VT);
2015     // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2016     if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2017         isa<ConstantSDNode>(Operand.getOperand(1)) &&
2018         Operand.getConstantOperandVal(1) == 0 &&
2019         Operand.getOperand(0).getValueType() == VT)
2020       return Operand.getOperand(0);
2021     break;
2022   case ISD::FNEG:
2023     if (OpOpcode == ISD::FSUB)   // -(X-Y) -> (Y-X)
2024       return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1),
2025                      Operand.Val->getOperand(0));
2026     if (OpOpcode == ISD::FNEG)  // --X -> X
2027       return Operand.Val->getOperand(0);
2028     break;
2029   case ISD::FABS:
2030     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
2031       return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
2032     break;
2033   }
2034
2035   SDNode *N;
2036   SDVTList VTs = getVTList(VT);
2037   if (VT != MVT::Flag) { // Don't CSE flag producing nodes
2038     FoldingSetNodeID ID;
2039     SDOperand Ops[1] = { Operand };
2040     AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2041     void *IP = 0;
2042     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2043       return SDOperand(E, 0);
2044     N = new UnarySDNode(Opcode, VTs, Operand);
2045     CSEMap.InsertNode(N, IP);
2046   } else {
2047     N = new UnarySDNode(Opcode, VTs, Operand);
2048   }
2049   AllNodes.push_back(N);
2050   return SDOperand(N, 0);
2051 }
2052
2053
2054
2055 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2056                                 SDOperand N1, SDOperand N2) {
2057   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
2058   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
2059   switch (Opcode) {
2060   default: break;
2061   case ISD::TokenFactor:
2062     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2063            N2.getValueType() == MVT::Other && "Invalid token factor!");
2064     // Fold trivial token factors.
2065     if (N1.getOpcode() == ISD::EntryToken) return N2;
2066     if (N2.getOpcode() == ISD::EntryToken) return N1;
2067     break;
2068   case ISD::AND:
2069     assert(MVT::isInteger(VT) && N1.getValueType() == N2.getValueType() &&
2070            N1.getValueType() == VT && "Binary operator types must match!");
2071     // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
2072     // worth handling here.
2073     if (N2C && N2C->isNullValue())
2074       return N2;
2075     if (N2C && N2C->isAllOnesValue())  // X & -1 -> X
2076       return N1;
2077     break;
2078   case ISD::OR:
2079   case ISD::XOR:
2080     assert(MVT::isInteger(VT) && N1.getValueType() == N2.getValueType() &&
2081            N1.getValueType() == VT && "Binary operator types must match!");
2082     // (X ^| 0) -> X.  This commonly occurs when legalizing i64 values, so it's
2083     // worth handling here.
2084     if (N2C && N2C->isNullValue())
2085       return N1;
2086     break;
2087   case ISD::UDIV:
2088   case ISD::UREM:
2089   case ISD::MULHU:
2090   case ISD::MULHS:
2091     assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
2092     // fall through
2093   case ISD::ADD:
2094   case ISD::SUB:
2095   case ISD::MUL:
2096   case ISD::SDIV:
2097   case ISD::SREM:
2098   case ISD::FADD:
2099   case ISD::FSUB:
2100   case ISD::FMUL:
2101   case ISD::FDIV:
2102   case ISD::FREM:
2103     assert(N1.getValueType() == N2.getValueType() &&
2104            N1.getValueType() == VT && "Binary operator types must match!");
2105     break;
2106   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
2107     assert(N1.getValueType() == VT &&
2108            MVT::isFloatingPoint(N1.getValueType()) &&
2109            MVT::isFloatingPoint(N2.getValueType()) &&
2110            "Invalid FCOPYSIGN!");
2111     break;
2112   case ISD::SHL:
2113   case ISD::SRA:
2114   case ISD::SRL:
2115   case ISD::ROTL:
2116   case ISD::ROTR:
2117     assert(VT == N1.getValueType() &&
2118            "Shift operators return type must be the same as their first arg");
2119     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
2120            VT != MVT::i1 && "Shifts only work on integers");
2121     break;
2122   case ISD::FP_ROUND_INREG: {
2123     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
2124     assert(VT == N1.getValueType() && "Not an inreg round!");
2125     assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
2126            "Cannot FP_ROUND_INREG integer types");
2127     assert(MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(VT) &&
2128            "Not rounding down!");
2129     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
2130     break;
2131   }
2132   case ISD::FP_ROUND:
2133     assert(MVT::isFloatingPoint(VT) &&
2134            MVT::isFloatingPoint(N1.getValueType()) &&
2135            MVT::getSizeInBits(VT) <= MVT::getSizeInBits(N1.getValueType()) &&
2136            isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2137     if (N1.getValueType() == VT) return N1;  // noop conversion.
2138     break;
2139   case ISD::AssertSext:
2140   case ISD::AssertZext: {
2141     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
2142     assert(VT == N1.getValueType() && "Not an inreg extend!");
2143     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
2144            "Cannot *_EXTEND_INREG FP types");
2145     assert(MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(VT) &&
2146            "Not extending!");
2147     if (VT == EVT) return N1; // noop assertion.
2148     break;
2149   }
2150   case ISD::SIGN_EXTEND_INREG: {
2151     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
2152     assert(VT == N1.getValueType() && "Not an inreg extend!");
2153     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
2154            "Cannot *_EXTEND_INREG FP types");
2155     assert(MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(VT) &&
2156            "Not extending!");
2157     if (EVT == VT) return N1;  // Not actually extending
2158
2159     if (N1C) {
2160       APInt Val = N1C->getAPIntValue();
2161       unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT());
2162       Val <<= Val.getBitWidth()-FromBits;
2163       Val = Val.ashr(Val.getBitWidth()-FromBits);
2164       return getConstant(Val, VT);
2165     }
2166     break;
2167   }
2168   case ISD::EXTRACT_VECTOR_ELT:
2169     assert(N2C && "Bad EXTRACT_VECTOR_ELT!");
2170
2171     // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2172     if (N1.getOpcode() == ISD::UNDEF)
2173       return getNode(ISD::UNDEF, VT);
2174
2175     // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2176     // expanding copies of large vectors from registers.
2177     if (N1.getOpcode() == ISD::CONCAT_VECTORS &&
2178         N1.getNumOperands() > 0) {
2179       unsigned Factor =
2180         MVT::getVectorNumElements(N1.getOperand(0).getValueType());
2181       return getNode(ISD::EXTRACT_VECTOR_ELT, VT,
2182                      N1.getOperand(N2C->getValue() / Factor),
2183                      getConstant(N2C->getValue() % Factor, N2.getValueType()));
2184     }
2185
2186     // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2187     // expanding large vector constants.
2188     if (N1.getOpcode() == ISD::BUILD_VECTOR)
2189       return N1.getOperand(N2C->getValue());
2190
2191     // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2192     // operations are lowered to scalars.
2193     if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT)
2194       if (ConstantSDNode *IEC = dyn_cast<ConstantSDNode>(N1.getOperand(2))) {
2195         if (IEC == N2C)
2196           return N1.getOperand(1);
2197         else
2198           return getNode(ISD::EXTRACT_VECTOR_ELT, VT, N1.getOperand(0), N2);
2199       }
2200     break;
2201   case ISD::EXTRACT_ELEMENT:
2202     assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!");
2203     assert(!MVT::isVector(N1.getValueType()) &&
2204            MVT::isInteger(N1.getValueType()) &&
2205            !MVT::isVector(VT) && MVT::isInteger(VT) &&
2206            "EXTRACT_ELEMENT only applies to integers!");
2207
2208     // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2209     // 64-bit integers into 32-bit parts.  Instead of building the extract of
2210     // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2211     if (N1.getOpcode() == ISD::BUILD_PAIR)
2212       return N1.getOperand(N2C->getValue());
2213
2214     // EXTRACT_ELEMENT of a constant int is also very common.
2215     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2216       unsigned ElementSize = MVT::getSizeInBits(VT);
2217       unsigned Shift = ElementSize * N2C->getValue();
2218       APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2219       return getConstant(ShiftedVal.trunc(ElementSize), VT);
2220     }
2221     break;
2222   case ISD::EXTRACT_SUBVECTOR:
2223     if (N1.getValueType() == VT) // Trivial extraction.
2224       return N1;
2225     break;
2226   }
2227
2228   if (N1C) {
2229     if (N2C) {
2230       APInt C1 = N1C->getAPIntValue(), C2 = N2C->getAPIntValue();
2231       switch (Opcode) {
2232       case ISD::ADD: return getConstant(C1 + C2, VT);
2233       case ISD::SUB: return getConstant(C1 - C2, VT);
2234       case ISD::MUL: return getConstant(C1 * C2, VT);
2235       case ISD::UDIV:
2236         if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2237         break;
2238       case ISD::UREM :
2239         if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2240         break;
2241       case ISD::SDIV :
2242         if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2243         break;
2244       case ISD::SREM :
2245         if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2246         break;
2247       case ISD::AND  : return getConstant(C1 & C2, VT);
2248       case ISD::OR   : return getConstant(C1 | C2, VT);
2249       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
2250       case ISD::SHL  : return getConstant(C1 << C2, VT);
2251       case ISD::SRL  : return getConstant(C1.lshr(C2), VT);
2252       case ISD::SRA  : return getConstant(C1.ashr(C2), VT);
2253       case ISD::ROTL : return getConstant(C1.rotl(C2), VT);
2254       case ISD::ROTR : return getConstant(C1.rotr(C2), VT);
2255       default: break;
2256       }
2257     } else {      // Cannonicalize constant to RHS if commutative
2258       if (isCommutativeBinOp(Opcode)) {
2259         std::swap(N1C, N2C);
2260         std::swap(N1, N2);
2261       }
2262     }
2263   }
2264
2265   // Constant fold FP operations.
2266   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
2267   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
2268   if (N1CFP) {
2269     if (!N2CFP && isCommutativeBinOp(Opcode)) {
2270       // Cannonicalize constant to RHS if commutative
2271       std::swap(N1CFP, N2CFP);
2272       std::swap(N1, N2);
2273     } else if (N2CFP && VT != MVT::ppcf128) {
2274       APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
2275       APFloat::opStatus s;
2276       switch (Opcode) {
2277       case ISD::FADD:
2278         s = V1.add(V2, APFloat::rmNearestTiesToEven);
2279         if (s != APFloat::opInvalidOp)
2280           return getConstantFP(V1, VT);
2281         break;
2282       case ISD::FSUB:
2283         s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
2284         if (s!=APFloat::opInvalidOp)
2285           return getConstantFP(V1, VT);
2286         break;
2287       case ISD::FMUL:
2288         s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
2289         if (s!=APFloat::opInvalidOp)
2290           return getConstantFP(V1, VT);
2291         break;
2292       case ISD::FDIV:
2293         s = V1.divide(V2, APFloat::rmNearestTiesToEven);
2294         if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
2295           return getConstantFP(V1, VT);
2296         break;
2297       case ISD::FREM :
2298         s = V1.mod(V2, APFloat::rmNearestTiesToEven);
2299         if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
2300           return getConstantFP(V1, VT);
2301         break;
2302       case ISD::FCOPYSIGN:
2303         V1.copySign(V2);
2304         return getConstantFP(V1, VT);
2305       default: break;
2306       }
2307     }
2308   }
2309
2310   // Canonicalize an UNDEF to the RHS, even over a constant.
2311   if (N1.getOpcode() == ISD::UNDEF) {
2312     if (isCommutativeBinOp(Opcode)) {
2313       std::swap(N1, N2);
2314     } else {
2315       switch (Opcode) {
2316       case ISD::FP_ROUND_INREG:
2317       case ISD::SIGN_EXTEND_INREG:
2318       case ISD::SUB:
2319       case ISD::FSUB:
2320       case ISD::FDIV:
2321       case ISD::FREM:
2322       case ISD::SRA:
2323         return N1;     // fold op(undef, arg2) -> undef
2324       case ISD::UDIV:
2325       case ISD::SDIV:
2326       case ISD::UREM:
2327       case ISD::SREM:
2328       case ISD::SRL:
2329       case ISD::SHL:
2330         if (!MVT::isVector(VT))
2331           return getConstant(0, VT);    // fold op(undef, arg2) -> 0
2332         // For vectors, we can't easily build an all zero vector, just return
2333         // the LHS.
2334         return N2;
2335       }
2336     }
2337   }
2338
2339   // Fold a bunch of operators when the RHS is undef.
2340   if (N2.getOpcode() == ISD::UNDEF) {
2341     switch (Opcode) {
2342     case ISD::XOR:
2343       if (N1.getOpcode() == ISD::UNDEF)
2344         // Handle undef ^ undef -> 0 special case. This is a common
2345         // idiom (misuse).
2346         return getConstant(0, VT);
2347       // fallthrough
2348     case ISD::ADD:
2349     case ISD::ADDC:
2350     case ISD::ADDE:
2351     case ISD::SUB:
2352     case ISD::FADD:
2353     case ISD::FSUB:
2354     case ISD::FMUL:
2355     case ISD::FDIV:
2356     case ISD::FREM:
2357     case ISD::UDIV:
2358     case ISD::SDIV:
2359     case ISD::UREM:
2360     case ISD::SREM:
2361       return N2;       // fold op(arg1, undef) -> undef
2362     case ISD::MUL:
2363     case ISD::AND:
2364     case ISD::SRL:
2365     case ISD::SHL:
2366       if (!MVT::isVector(VT))
2367         return getConstant(0, VT);  // fold op(arg1, undef) -> 0
2368       // For vectors, we can't easily build an all zero vector, just return
2369       // the LHS.
2370       return N1;
2371     case ISD::OR:
2372       if (!MVT::isVector(VT))
2373         return getConstant(MVT::getIntVTBitMask(VT), VT);
2374       // For vectors, we can't easily build an all one vector, just return
2375       // the LHS.
2376       return N1;
2377     case ISD::SRA:
2378       return N1;
2379     }
2380   }
2381
2382   // Memoize this node if possible.
2383   SDNode *N;
2384   SDVTList VTs = getVTList(VT);
2385   if (VT != MVT::Flag) {
2386     SDOperand Ops[] = { N1, N2 };
2387     FoldingSetNodeID ID;
2388     AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
2389     void *IP = 0;
2390     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2391       return SDOperand(E, 0);
2392     N = new BinarySDNode(Opcode, VTs, N1, N2);
2393     CSEMap.InsertNode(N, IP);
2394   } else {
2395     N = new BinarySDNode(Opcode, VTs, N1, N2);
2396   }
2397
2398   AllNodes.push_back(N);
2399   return SDOperand(N, 0);
2400 }
2401
2402 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2403                                 SDOperand N1, SDOperand N2, SDOperand N3) {
2404   // Perform various simplifications.
2405   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
2406   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
2407   switch (Opcode) {
2408   case ISD::SETCC: {
2409     // Use FoldSetCC to simplify SETCC's.
2410     SDOperand Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
2411     if (Simp.Val) return Simp;
2412     break;
2413   }
2414   case ISD::SELECT:
2415     if (N1C) {
2416      if (N1C->getValue())
2417         return N2;             // select true, X, Y -> X
2418       else
2419         return N3;             // select false, X, Y -> Y
2420     }
2421
2422     if (N2 == N3) return N2;   // select C, X, X -> X
2423     break;
2424   case ISD::BRCOND:
2425     if (N2C) {
2426       if (N2C->getValue()) // Unconditional branch
2427         return getNode(ISD::BR, MVT::Other, N1, N3);
2428       else
2429         return N1;         // Never-taken branch
2430     }
2431     break;
2432   case ISD::VECTOR_SHUFFLE:
2433     assert(VT == N1.getValueType() && VT == N2.getValueType() &&
2434            MVT::isVector(VT) && MVT::isVector(N3.getValueType()) &&
2435            N3.getOpcode() == ISD::BUILD_VECTOR &&
2436            MVT::getVectorNumElements(VT) == N3.getNumOperands() &&
2437            "Illegal VECTOR_SHUFFLE node!");
2438     break;
2439   case ISD::BIT_CONVERT:
2440     // Fold bit_convert nodes from a type to themselves.
2441     if (N1.getValueType() == VT)
2442       return N1;
2443     break;
2444   }
2445
2446   // Memoize node if it doesn't produce a flag.
2447   SDNode *N;
2448   SDVTList VTs = getVTList(VT);
2449   if (VT != MVT::Flag) {
2450     SDOperand Ops[] = { N1, N2, N3 };
2451     FoldingSetNodeID ID;
2452     AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
2453     void *IP = 0;
2454     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2455       return SDOperand(E, 0);
2456     N = new TernarySDNode(Opcode, VTs, N1, N2, N3);
2457     CSEMap.InsertNode(N, IP);
2458   } else {
2459     N = new TernarySDNode(Opcode, VTs, N1, N2, N3);
2460   }
2461   AllNodes.push_back(N);
2462   return SDOperand(N, 0);
2463 }
2464
2465 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2466                                 SDOperand N1, SDOperand N2, SDOperand N3,
2467                                 SDOperand N4) {
2468   SDOperand Ops[] = { N1, N2, N3, N4 };
2469   return getNode(Opcode, VT, Ops, 4);
2470 }
2471
2472 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2473                                 SDOperand N1, SDOperand N2, SDOperand N3,
2474                                 SDOperand N4, SDOperand N5) {
2475   SDOperand Ops[] = { N1, N2, N3, N4, N5 };
2476   return getNode(Opcode, VT, Ops, 5);
2477 }
2478
2479 /// getMemsetValue - Vectorized representation of the memset value
2480 /// operand.
2481 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
2482                                 SelectionDAG &DAG) {
2483   MVT::ValueType CurVT = VT;
2484   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
2485     uint64_t Val   = C->getValue() & 255;
2486     unsigned Shift = 8;
2487     while (CurVT != MVT::i8) {
2488       Val = (Val << Shift) | Val;
2489       Shift <<= 1;
2490       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
2491     }
2492     return DAG.getConstant(Val, VT);
2493   } else {
2494     Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
2495     unsigned Shift = 8;
2496     while (CurVT != MVT::i8) {
2497       Value =
2498         DAG.getNode(ISD::OR, VT,
2499                     DAG.getNode(ISD::SHL, VT, Value,
2500                                 DAG.getConstant(Shift, MVT::i8)), Value);
2501       Shift <<= 1;
2502       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
2503     }
2504
2505     return Value;
2506   }
2507 }
2508
2509 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
2510 /// used when a memcpy is turned into a memset when the source is a constant
2511 /// string ptr.
2512 static SDOperand getMemsetStringVal(MVT::ValueType VT,
2513                                     SelectionDAG &DAG,
2514                                     const TargetLowering &TLI,
2515                                     std::string &Str, unsigned Offset) {
2516   uint64_t Val = 0;
2517   unsigned MSB = MVT::getSizeInBits(VT) / 8;
2518   if (TLI.isLittleEndian())
2519     Offset = Offset + MSB - 1;
2520   for (unsigned i = 0; i != MSB; ++i) {
2521     Val = (Val << 8) | (unsigned char)Str[Offset];
2522     Offset += TLI.isLittleEndian() ? -1 : 1;
2523   }
2524   return DAG.getConstant(Val, VT);
2525 }
2526
2527 /// getMemBasePlusOffset - Returns base and offset node for the
2528 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
2529                                       SelectionDAG &DAG) {
2530   MVT::ValueType VT = Base.getValueType();
2531   return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
2532 }
2533
2534 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
2535 /// to replace the memset / memcpy is below the threshold. It also returns the
2536 /// types of the sequence of memory ops to perform memset / memcpy.
2537 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
2538                                      unsigned Limit, uint64_t Size,
2539                                      unsigned Align,
2540                                      const TargetLowering &TLI) {
2541   MVT::ValueType VT;
2542
2543   if (TLI.allowsUnalignedMemoryAccesses()) {
2544     VT = MVT::i64;
2545   } else {
2546     switch (Align & 7) {
2547     case 0:
2548       VT = MVT::i64;
2549       break;
2550     case 4:
2551       VT = MVT::i32;
2552       break;
2553     case 2:
2554       VT = MVT::i16;
2555       break;
2556     default:
2557       VT = MVT::i8;
2558       break;
2559     }
2560   }
2561
2562   MVT::ValueType LVT = MVT::i64;
2563   while (!TLI.isTypeLegal(LVT))
2564     LVT = (MVT::ValueType)((unsigned)LVT - 1);
2565   assert(MVT::isInteger(LVT));
2566
2567   if (VT > LVT)
2568     VT = LVT;
2569
2570   unsigned NumMemOps = 0;
2571   while (Size != 0) {
2572     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
2573     while (VTSize > Size) {
2574       VT = (MVT::ValueType)((unsigned)VT - 1);
2575       VTSize >>= 1;
2576     }
2577     assert(MVT::isInteger(VT));
2578
2579     if (++NumMemOps > Limit)
2580       return false;
2581     MemOps.push_back(VT);
2582     Size -= VTSize;
2583   }
2584
2585   return true;
2586 }
2587
2588 static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG,
2589                                          SDOperand Chain, SDOperand Dst,
2590                                          SDOperand Src, uint64_t Size,
2591                                          unsigned Align,
2592                                          bool AlwaysInline,
2593                                          const Value *DstSV, uint64_t DstSVOff,
2594                                          const Value *SrcSV, uint64_t SrcSVOff){
2595   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2596
2597   // Expand memcpy to a series of store ops if the size operand falls below
2598   // a certain threshold.
2599   std::vector<MVT::ValueType> MemOps;
2600   uint64_t Limit = -1;
2601   if (!AlwaysInline)
2602     Limit = TLI.getMaxStoresPerMemcpy();
2603   if (!MeetsMaxMemopRequirement(MemOps, Limit, Size, Align, TLI))
2604     return SDOperand();
2605
2606   SmallVector<SDOperand, 8> OutChains;
2607
2608   unsigned NumMemOps = MemOps.size();
2609   unsigned SrcDelta = 0;
2610   GlobalAddressSDNode *G = NULL;
2611   std::string Str;
2612   bool CopyFromStr = false;
2613   uint64_t SrcOff = 0, DstOff = 0;
2614
2615   if (Src.getOpcode() == ISD::GlobalAddress)
2616     G = cast<GlobalAddressSDNode>(Src);
2617   else if (Src.getOpcode() == ISD::ADD &&
2618            Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
2619            Src.getOperand(1).getOpcode() == ISD::Constant) {
2620     G = cast<GlobalAddressSDNode>(Src.getOperand(0));
2621     SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getValue();
2622   }
2623   if (G) {
2624     GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
2625     if (GV && GV->isConstant()) {
2626       Str = GV->getStringValue(false);
2627       if (!Str.empty()) {
2628         CopyFromStr = true;
2629         SrcOff += SrcDelta;
2630       }
2631     }
2632   }
2633
2634   for (unsigned i = 0; i < NumMemOps; i++) {
2635     MVT::ValueType VT = MemOps[i];
2636     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
2637     SDOperand Value, Store;
2638
2639     if (CopyFromStr) {
2640       Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
2641       Store =
2642         DAG.getStore(Chain, Value,
2643                      getMemBasePlusOffset(Dst, DstOff, DAG),
2644                      DstSV, DstSVOff + DstOff);
2645     } else {
2646       Value = DAG.getLoad(VT, Chain,
2647                           getMemBasePlusOffset(Src, SrcOff, DAG),
2648                           SrcSV, SrcSVOff + SrcOff, false, Align);
2649       Store =
2650         DAG.getStore(Chain, Value,
2651                      getMemBasePlusOffset(Dst, DstOff, DAG),
2652                      DstSV, DstSVOff + DstOff, false, Align);
2653     }
2654     OutChains.push_back(Store);
2655     SrcOff += VTSize;
2656     DstOff += VTSize;
2657   }
2658
2659   return DAG.getNode(ISD::TokenFactor, MVT::Other,
2660                      &OutChains[0], OutChains.size());
2661 }
2662
2663 static SDOperand getMemsetStores(SelectionDAG &DAG,
2664                                  SDOperand Chain, SDOperand Dst,
2665                                  SDOperand Src, uint64_t Size,
2666                                  unsigned Align,
2667                                  const Value *DstSV, uint64_t DstSVOff) {
2668   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2669
2670   // Expand memset to a series of load/store ops if the size operand
2671   // falls below a certain threshold.
2672   std::vector<MVT::ValueType> MemOps;
2673   if (!MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
2674                                 Size, Align, TLI))
2675     return SDOperand();
2676
2677   SmallVector<SDOperand, 8> OutChains;
2678   uint64_t DstOff = 0;
2679
2680   unsigned NumMemOps = MemOps.size();
2681   for (unsigned i = 0; i < NumMemOps; i++) {
2682     MVT::ValueType VT = MemOps[i];
2683     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
2684     SDOperand Value = getMemsetValue(Src, VT, DAG);
2685     SDOperand Store = DAG.getStore(Chain, Value,
2686                                    getMemBasePlusOffset(Dst, DstOff, DAG),
2687                                    DstSV, DstSVOff + DstOff);
2688     OutChains.push_back(Store);
2689     DstOff += VTSize;
2690   }
2691
2692   return DAG.getNode(ISD::TokenFactor, MVT::Other,
2693                      &OutChains[0], OutChains.size());
2694 }
2695
2696 SDOperand SelectionDAG::getMemcpy(SDOperand Chain, SDOperand Dst,
2697                                   SDOperand Src, SDOperand Size,
2698                                   unsigned Align, bool AlwaysInline,
2699                                   const Value *DstSV, uint64_t DstSVOff,
2700                                   const Value *SrcSV, uint64_t SrcSVOff) {
2701
2702   // Check to see if we should lower the memcpy to loads and stores first.
2703   // For cases within the target-specified limits, this is the best choice.
2704   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
2705   if (ConstantSize) {
2706     // Memcpy with size zero? Just return the original chain.
2707     if (ConstantSize->isNullValue())
2708       return Chain;
2709
2710     SDOperand Result =
2711       getMemcpyLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(),
2712                               Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff);
2713     if (Result.Val)
2714       return Result;
2715   }
2716
2717   // Then check to see if we should lower the memcpy with target-specific
2718   // code. If the target chooses to do this, this is the next best.
2719   SDOperand Result =
2720     TLI.EmitTargetCodeForMemcpy(*this, Chain, Dst, Src, Size, Align,
2721                                 AlwaysInline,
2722                                 DstSV, DstSVOff, SrcSV, SrcSVOff);
2723   if (Result.Val)
2724     return Result;
2725
2726   // If we really need inline code and the target declined to provide it,
2727   // use a (potentially long) sequence of loads and stores.
2728   if (AlwaysInline) {
2729     assert(ConstantSize && "AlwaysInline requires a constant size!");
2730     return getMemcpyLoadsAndStores(*this, Chain, Dst, Src,
2731                                    ConstantSize->getValue(), Align, true,
2732                                    DstSV, DstSVOff, SrcSV, SrcSVOff);
2733   }
2734
2735   // Emit a library call.
2736   TargetLowering::ArgListTy Args;
2737   TargetLowering::ArgListEntry Entry;
2738   Entry.Ty = TLI.getTargetData()->getIntPtrType();
2739   Entry.Node = Dst; Args.push_back(Entry);
2740   Entry.Node = Src; Args.push_back(Entry);
2741   Entry.Node = Size; Args.push_back(Entry);
2742   std::pair<SDOperand,SDOperand> CallResult =
2743     TLI.LowerCallTo(Chain, Type::VoidTy,
2744                     false, false, false, CallingConv::C, false,
2745                     getExternalSymbol("memcpy", TLI.getPointerTy()),
2746                     Args, *this);
2747   return CallResult.second;
2748 }
2749
2750 SDOperand SelectionDAG::getMemmove(SDOperand Chain, SDOperand Dst,
2751                                    SDOperand Src, SDOperand Size,
2752                                    unsigned Align,
2753                                    const Value *DstSV, uint64_t DstSVOff,
2754                                    const Value *SrcSV, uint64_t SrcSVOff) {
2755
2756   // TODO: Optimize small memmove cases with simple loads and stores,
2757   // ensuring that all loads precede all stores. This can cause severe
2758   // register pressure, so targets should be careful with the size limit.
2759
2760   // Then check to see if we should lower the memmove with target-specific
2761   // code. If the target chooses to do this, this is the next best.
2762   SDOperand Result =
2763     TLI.EmitTargetCodeForMemmove(*this, Chain, Dst, Src, Size, Align,
2764                                  DstSV, DstSVOff, SrcSV, SrcSVOff);
2765   if (Result.Val)
2766     return Result;
2767
2768   // Emit a library call.
2769   TargetLowering::ArgListTy Args;
2770   TargetLowering::ArgListEntry Entry;
2771   Entry.Ty = TLI.getTargetData()->getIntPtrType();
2772   Entry.Node = Dst; Args.push_back(Entry);
2773   Entry.Node = Src; Args.push_back(Entry);
2774   Entry.Node = Size; Args.push_back(Entry);
2775   std::pair<SDOperand,SDOperand> CallResult =
2776     TLI.LowerCallTo(Chain, Type::VoidTy,
2777                     false, false, false, CallingConv::C, false,
2778                     getExternalSymbol("memmove", TLI.getPointerTy()),
2779                     Args, *this);
2780   return CallResult.second;
2781 }
2782
2783 SDOperand SelectionDAG::getMemset(SDOperand Chain, SDOperand Dst,
2784                                   SDOperand Src, SDOperand Size,
2785                                   unsigned Align,
2786                                   const Value *DstSV, uint64_t DstSVOff) {
2787
2788   // Check to see if we should lower the memset to stores first.
2789   // For cases within the target-specified limits, this is the best choice.
2790   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
2791   if (ConstantSize) {
2792     // Memset with size zero? Just return the original chain.
2793     if (ConstantSize->isNullValue())
2794       return Chain;
2795
2796     SDOperand Result =
2797       getMemsetStores(*this, Chain, Dst, Src, ConstantSize->getValue(), Align,
2798                       DstSV, DstSVOff);
2799     if (Result.Val)
2800       return Result;
2801   }
2802
2803   // Then check to see if we should lower the memset with target-specific
2804   // code. If the target chooses to do this, this is the next best.
2805   SDOperand Result =
2806     TLI.EmitTargetCodeForMemset(*this, Chain, Dst, Src, Size, Align,
2807                                 DstSV, DstSVOff);
2808   if (Result.Val)
2809     return Result;
2810
2811   // Emit a library call.
2812   const Type *IntPtrTy = TLI.getTargetData()->getIntPtrType();
2813   TargetLowering::ArgListTy Args;
2814   TargetLowering::ArgListEntry Entry;
2815   Entry.Node = Dst; Entry.Ty = IntPtrTy;
2816   Args.push_back(Entry);
2817   // Extend or truncate the argument to be an i32 value for the call.
2818   if (Src.getValueType() > MVT::i32)
2819     Src = getNode(ISD::TRUNCATE, MVT::i32, Src);
2820   else
2821     Src = getNode(ISD::ZERO_EXTEND, MVT::i32, Src);
2822   Entry.Node = Src; Entry.Ty = Type::Int32Ty; Entry.isSExt = true;
2823   Args.push_back(Entry);
2824   Entry.Node = Size; Entry.Ty = IntPtrTy; Entry.isSExt = false;
2825   Args.push_back(Entry);
2826   std::pair<SDOperand,SDOperand> CallResult =
2827     TLI.LowerCallTo(Chain, Type::VoidTy,
2828                     false, false, false, CallingConv::C, false,
2829                     getExternalSymbol("memset", TLI.getPointerTy()),
2830                     Args, *this);
2831   return CallResult.second;
2832 }
2833
2834 SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain,
2835                                   SDOperand Ptr, SDOperand Cmp,
2836                                   SDOperand Swp, MVT::ValueType VT) {
2837   assert(Opcode == ISD::ATOMIC_LCS && "Invalid Atomic Op");
2838   assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
2839   SDVTList VTs = getVTList(Cmp.getValueType(), MVT::Other);
2840   FoldingSetNodeID ID;
2841   SDOperand Ops[] = {Chain, Ptr, Cmp, Swp};
2842   AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
2843   ID.AddInteger((unsigned int)VT);
2844   void* IP = 0;
2845   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2846     return SDOperand(E, 0);
2847   SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, VT);
2848   CSEMap.InsertNode(N, IP);
2849   AllNodes.push_back(N);
2850   return SDOperand(N, 0);
2851 }
2852
2853 SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain,
2854                                   SDOperand Ptr, SDOperand Val,
2855                                   MVT::ValueType VT) {
2856   assert((Opcode == ISD::ATOMIC_LAS || Opcode == ISD::ATOMIC_SWAP)
2857          && "Invalid Atomic Op");
2858   SDVTList VTs = getVTList(Val.getValueType(), MVT::Other);
2859   FoldingSetNodeID ID;
2860   SDOperand Ops[] = {Chain, Ptr, Val};
2861   AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
2862   ID.AddInteger((unsigned int)VT);
2863   void* IP = 0;
2864   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2865     return SDOperand(E, 0);
2866   SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, VT);
2867   CSEMap.InsertNode(N, IP);
2868   AllNodes.push_back(N);
2869   return SDOperand(N, 0);
2870 }
2871
2872 SDOperand
2873 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
2874                       MVT::ValueType VT, SDOperand Chain,
2875                       SDOperand Ptr, SDOperand Offset,
2876                       const Value *SV, int SVOffset, MVT::ValueType EVT,
2877                       bool isVolatile, unsigned Alignment) {
2878   if (Alignment == 0) { // Ensure that codegen never sees alignment 0
2879     const Type *Ty = 0;
2880     if (VT != MVT::iPTR) {
2881       Ty = MVT::getTypeForValueType(VT);
2882     } else if (SV) {
2883       const PointerType *PT = dyn_cast<PointerType>(SV->getType());
2884       assert(PT && "Value for load must be a pointer");
2885       Ty = PT->getElementType();
2886     }
2887     assert(Ty && "Could not get type information for load");
2888     Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
2889   }
2890
2891   if (VT == EVT) {
2892     ExtType = ISD::NON_EXTLOAD;
2893   } else if (ExtType == ISD::NON_EXTLOAD) {
2894     assert(VT == EVT && "Non-extending load from different memory type!");
2895   } else {
2896     // Extending load.
2897     if (MVT::isVector(VT))
2898       assert(EVT == MVT::getVectorElementType(VT) && "Invalid vector extload!");
2899     else
2900       assert(MVT::getSizeInBits(EVT) < MVT::getSizeInBits(VT) &&
2901              "Should only be an extending load, not truncating!");
2902     assert((ExtType == ISD::EXTLOAD || MVT::isInteger(VT)) &&
2903            "Cannot sign/zero extend a FP/Vector load!");
2904     assert(MVT::isInteger(VT) == MVT::isInteger(EVT) &&
2905            "Cannot convert from FP to Int or Int -> FP!");
2906   }
2907
2908   bool Indexed = AM != ISD::UNINDEXED;
2909   assert(Indexed || Offset.getOpcode() == ISD::UNDEF &&
2910          "Unindexed load with an offset!");
2911
2912   SDVTList VTs = Indexed ?
2913     getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
2914   SDOperand Ops[] = { Chain, Ptr, Offset };
2915   FoldingSetNodeID ID;
2916   AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
2917   ID.AddInteger(AM);
2918   ID.AddInteger(ExtType);
2919   ID.AddInteger((unsigned int)EVT);
2920   ID.AddInteger(Alignment);
2921   ID.AddInteger(isVolatile);
2922   void *IP = 0;
2923   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2924     return SDOperand(E, 0);
2925   SDNode *N = new LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset,
2926                              Alignment, isVolatile);
2927   CSEMap.InsertNode(N, IP);
2928   AllNodes.push_back(N);
2929   return SDOperand(N, 0);
2930 }
2931
2932 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
2933                                 SDOperand Chain, SDOperand Ptr,
2934                                 const Value *SV, int SVOffset,
2935                                 bool isVolatile, unsigned Alignment) {
2936   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2937   return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, Chain, Ptr, Undef,
2938                  SV, SVOffset, VT, isVolatile, Alignment);
2939 }
2940
2941 SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT,
2942                                    SDOperand Chain, SDOperand Ptr,
2943                                    const Value *SV,
2944                                    int SVOffset, MVT::ValueType EVT,
2945                                    bool isVolatile, unsigned Alignment) {
2946   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2947   return getLoad(ISD::UNINDEXED, ExtType, VT, Chain, Ptr, Undef,
2948                  SV, SVOffset, EVT, isVolatile, Alignment);
2949 }
2950
2951 SDOperand
2952 SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base,
2953                              SDOperand Offset, ISD::MemIndexedMode AM) {
2954   LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
2955   assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
2956          "Load is already a indexed load!");
2957   return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(),
2958                  LD->getChain(), Base, Offset, LD->getSrcValue(),
2959                  LD->getSrcValueOffset(), LD->getMemoryVT(),
2960                  LD->isVolatile(), LD->getAlignment());
2961 }
2962
2963 SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val,
2964                                  SDOperand Ptr, const Value *SV, int SVOffset,
2965                                  bool isVolatile, unsigned Alignment) {
2966   MVT::ValueType VT = Val.getValueType();
2967
2968   if (Alignment == 0) { // Ensure that codegen never sees alignment 0
2969     const Type *Ty = 0;
2970     if (VT != MVT::iPTR) {
2971       Ty = MVT::getTypeForValueType(VT);
2972     } else if (SV) {
2973       const PointerType *PT = dyn_cast<PointerType>(SV->getType());
2974       assert(PT && "Value for store must be a pointer");
2975       Ty = PT->getElementType();
2976     }
2977     assert(Ty && "Could not get type information for store");
2978     Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
2979   }
2980   SDVTList VTs = getVTList(MVT::Other);
2981   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2982   SDOperand Ops[] = { Chain, Val, Ptr, Undef };
2983   FoldingSetNodeID ID;
2984   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
2985   ID.AddInteger(ISD::UNINDEXED);
2986   ID.AddInteger(false);
2987   ID.AddInteger((unsigned int)VT);
2988   ID.AddInteger(Alignment);
2989   ID.AddInteger(isVolatile);
2990   void *IP = 0;
2991   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2992     return SDOperand(E, 0);
2993   SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, false,
2994                               VT, SV, SVOffset, Alignment, isVolatile);
2995   CSEMap.InsertNode(N, IP);
2996   AllNodes.push_back(N);
2997   return SDOperand(N, 0);
2998 }
2999
3000 SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val,
3001                                       SDOperand Ptr, const Value *SV,
3002                                       int SVOffset, MVT::ValueType SVT,
3003                                       bool isVolatile, unsigned Alignment) {
3004   MVT::ValueType VT = Val.getValueType();
3005
3006   if (VT == SVT)
3007     return getStore(Chain, Val, Ptr, SV, SVOffset, isVolatile, Alignment);
3008
3009   assert(MVT::getSizeInBits(VT) > MVT::getSizeInBits(SVT) &&
3010          "Not a truncation?");
3011   assert(MVT::isInteger(VT) == MVT::isInteger(SVT) &&
3012          "Can't do FP-INT conversion!");
3013
3014   if (Alignment == 0) { // Ensure that codegen never sees alignment 0
3015     const Type *Ty = 0;
3016     if (VT != MVT::iPTR) {
3017       Ty = MVT::getTypeForValueType(VT);
3018     } else if (SV) {
3019       const PointerType *PT = dyn_cast<PointerType>(SV->getType());
3020       assert(PT && "Value for store must be a pointer");
3021       Ty = PT->getElementType();
3022     }
3023     assert(Ty && "Could not get type information for store");
3024     Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
3025   }
3026   SDVTList VTs = getVTList(MVT::Other);
3027   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
3028   SDOperand Ops[] = { Chain, Val, Ptr, Undef };
3029   FoldingSetNodeID ID;
3030   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
3031   ID.AddInteger(ISD::UNINDEXED);
3032   ID.AddInteger(1);
3033   ID.AddInteger((unsigned int)SVT);
3034   ID.AddInteger(Alignment);
3035   ID.AddInteger(isVolatile);
3036   void *IP = 0;
3037   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3038     return SDOperand(E, 0);
3039   SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, true,
3040                               SVT, SV, SVOffset, Alignment, isVolatile);
3041   CSEMap.InsertNode(N, IP);
3042   AllNodes.push_back(N);
3043   return SDOperand(N, 0);
3044 }
3045
3046 SDOperand
3047 SelectionDAG::getIndexedStore(SDOperand OrigStore, SDOperand Base,
3048                               SDOperand Offset, ISD::MemIndexedMode AM) {
3049   StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
3050   assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
3051          "Store is already a indexed store!");
3052   SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
3053   SDOperand Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
3054   FoldingSetNodeID ID;
3055   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
3056   ID.AddInteger(AM);
3057   ID.AddInteger(ST->isTruncatingStore());
3058   ID.AddInteger((unsigned int)(ST->getMemoryVT()));
3059   ID.AddInteger(ST->getAlignment());
3060   ID.AddInteger(ST->isVolatile());
3061   void *IP = 0;
3062   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3063     return SDOperand(E, 0);
3064   SDNode *N = new StoreSDNode(Ops, VTs, AM,
3065                               ST->isTruncatingStore(), ST->getMemoryVT(),
3066                               ST->getSrcValue(), ST->getSrcValueOffset(),
3067                               ST->getAlignment(), ST->isVolatile());
3068   CSEMap.InsertNode(N, IP);
3069   AllNodes.push_back(N);
3070   return SDOperand(N, 0);
3071 }
3072
3073 SDOperand SelectionDAG::getVAArg(MVT::ValueType VT,
3074                                  SDOperand Chain, SDOperand Ptr,
3075                                  SDOperand SV) {
3076   SDOperand Ops[] = { Chain, Ptr, SV };
3077   return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3);
3078 }
3079
3080 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
3081                                 SDOperandPtr Ops, unsigned NumOps) {
3082   switch (NumOps) {
3083   case 0: return getNode(Opcode, VT);
3084   case 1: return getNode(Opcode, VT, Ops[0]);
3085   case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
3086   case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
3087   default: break;
3088   }
3089
3090   switch (Opcode) {
3091   default: break;
3092   case ISD::SELECT_CC: {
3093     assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
3094     assert(Ops[0].getValueType() == Ops[1].getValueType() &&
3095            "LHS and RHS of condition must have same type!");
3096     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
3097            "True and False arms of SelectCC must have same type!");
3098     assert(Ops[2].getValueType() == VT &&
3099            "select_cc node must be of same type as true and false value!");
3100     break;
3101   }
3102   case ISD::BR_CC: {
3103     assert(NumOps == 5 && "BR_CC takes 5 operands!");
3104     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
3105            "LHS/RHS of comparison should match types!");
3106     break;
3107   }
3108   }
3109
3110   // Memoize nodes.
3111   SDNode *N;
3112   SDVTList VTs = getVTList(VT);
3113   if (VT != MVT::Flag) {
3114     FoldingSetNodeID ID;
3115     AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
3116     void *IP = 0;
3117     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3118       return SDOperand(E, 0);
3119     N = new SDNode(Opcode, VTs, Ops, NumOps);
3120     CSEMap.InsertNode(N, IP);
3121   } else {
3122     N = new SDNode(Opcode, VTs, Ops, NumOps);
3123   }
3124   AllNodes.push_back(N);
3125   return SDOperand(N, 0);
3126 }
3127
3128 SDOperand SelectionDAG::getNode(unsigned Opcode,
3129                                 std::vector<MVT::ValueType> &ResultTys,
3130                                 SDOperandPtr Ops, unsigned NumOps) {
3131   return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(),
3132                  Ops, NumOps);
3133 }
3134
3135 SDOperand SelectionDAG::getNode(unsigned Opcode,
3136                                 const MVT::ValueType *VTs, unsigned NumVTs,
3137                                 SDOperandPtr Ops, unsigned NumOps) {
3138   if (NumVTs == 1)
3139     return getNode(Opcode, VTs[0], Ops, NumOps);
3140   return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps);
3141 }
3142
3143 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3144                                 SDOperandPtr Ops, unsigned NumOps) {
3145   if (VTList.NumVTs == 1)
3146     return getNode(Opcode, VTList.VTs[0], Ops, NumOps);
3147
3148   switch (Opcode) {
3149   // FIXME: figure out how to safely handle things like
3150   // int foo(int x) { return 1 << (x & 255); }
3151   // int bar() { return foo(256); }
3152 #if 0
3153   case ISD::SRA_PARTS:
3154   case ISD::SRL_PARTS:
3155   case ISD::SHL_PARTS:
3156     if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
3157         cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
3158       return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
3159     else if (N3.getOpcode() == ISD::AND)
3160       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
3161         // If the and is only masking out bits that cannot effect the shift,
3162         // eliminate the and.
3163         unsigned NumBits = MVT::getSizeInBits(VT)*2;
3164         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
3165           return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
3166       }
3167     break;
3168 #endif
3169   }
3170
3171   // Memoize the node unless it returns a flag.
3172   SDNode *N;
3173   if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
3174     FoldingSetNodeID ID;
3175     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
3176     void *IP = 0;
3177     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3178       return SDOperand(E, 0);
3179     if (NumOps == 1)
3180       N = new UnarySDNode(Opcode, VTList, Ops[0]);
3181     else if (NumOps == 2)
3182       N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
3183     else if (NumOps == 3)
3184       N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
3185     else
3186       N = new SDNode(Opcode, VTList, Ops, NumOps);
3187     CSEMap.InsertNode(N, IP);
3188   } else {
3189     if (NumOps == 1)
3190       N = new UnarySDNode(Opcode, VTList, Ops[0]);
3191     else if (NumOps == 2)
3192       N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
3193     else if (NumOps == 3)
3194       N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
3195     else
3196       N = new SDNode(Opcode, VTList, Ops, NumOps);
3197   }
3198   AllNodes.push_back(N);
3199   return SDOperand(N, 0);
3200 }
3201
3202 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList) {
3203   return getNode(Opcode, VTList, (SDOperand*)0, 0);
3204 }
3205
3206 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3207                                 SDOperand N1) {
3208   SDOperand Ops[] = { N1 };
3209   return getNode(Opcode, VTList, Ops, 1);
3210 }
3211
3212 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3213                                 SDOperand N1, SDOperand N2) {
3214   SDOperand Ops[] = { N1, N2 };
3215   return getNode(Opcode, VTList, Ops, 2);
3216 }
3217
3218 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3219                                 SDOperand N1, SDOperand N2, SDOperand N3) {
3220   SDOperand Ops[] = { N1, N2, N3 };
3221   return getNode(Opcode, VTList, Ops, 3);
3222 }
3223
3224 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3225                                 SDOperand N1, SDOperand N2, SDOperand N3,
3226                                 SDOperand N4) {
3227   SDOperand Ops[] = { N1, N2, N3, N4 };
3228   return getNode(Opcode, VTList, Ops, 4);
3229 }
3230
3231 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3232                                 SDOperand N1, SDOperand N2, SDOperand N3,
3233                                 SDOperand N4, SDOperand N5) {
3234   SDOperand Ops[] = { N1, N2, N3, N4, N5 };
3235   return getNode(Opcode, VTList, Ops, 5);
3236 }
3237
3238 SDVTList SelectionDAG::getVTList(MVT::ValueType VT) {
3239   return makeVTList(SDNode::getValueTypeList(VT), 1);
3240 }
3241
3242 SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2) {
3243   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
3244        E = VTList.end(); I != E; ++I) {
3245     if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2)
3246       return makeVTList(&(*I)[0], 2);
3247   }
3248   std::vector<MVT::ValueType> V;
3249   V.push_back(VT1);
3250   V.push_back(VT2);
3251   VTList.push_front(V);
3252   return makeVTList(&(*VTList.begin())[0], 2);
3253 }
3254 SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2,
3255                                  MVT::ValueType VT3) {
3256   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
3257        E = VTList.end(); I != E; ++I) {
3258     if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 &&
3259         (*I)[2] == VT3)
3260       return makeVTList(&(*I)[0], 3);
3261   }
3262   std::vector<MVT::ValueType> V;
3263   V.push_back(VT1);
3264   V.push_back(VT2);
3265   V.push_back(VT3);
3266   VTList.push_front(V);
3267   return makeVTList(&(*VTList.begin())[0], 3);
3268 }
3269
3270 SDVTList SelectionDAG::getVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
3271   switch (NumVTs) {
3272     case 0: assert(0 && "Cannot have nodes without results!");
3273     case 1: return getVTList(VTs[0]);
3274     case 2: return getVTList(VTs[0], VTs[1]);
3275     case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
3276     default: break;
3277   }
3278
3279   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
3280        E = VTList.end(); I != E; ++I) {
3281     if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue;
3282
3283     bool NoMatch = false;
3284     for (unsigned i = 2; i != NumVTs; ++i)
3285       if (VTs[i] != (*I)[i]) {
3286         NoMatch = true;
3287         break;
3288       }
3289     if (!NoMatch)
3290       return makeVTList(&*I->begin(), NumVTs);
3291   }
3292
3293   VTList.push_front(std::vector<MVT::ValueType>(VTs, VTs+NumVTs));
3294   return makeVTList(&*VTList.begin()->begin(), NumVTs);
3295 }
3296
3297
3298 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
3299 /// specified operands.  If the resultant node already exists in the DAG,
3300 /// this does not modify the specified node, instead it returns the node that
3301 /// already exists.  If the resultant node does not exist in the DAG, the
3302 /// input node is returned.  As a degenerate case, if you specify the same
3303 /// input operands as the node already has, the input node is returned.
3304 SDOperand SelectionDAG::
3305 UpdateNodeOperands(SDOperand InN, SDOperand Op) {
3306   SDNode *N = InN.Val;
3307   assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
3308
3309   // Check to see if there is no change.
3310   if (Op == N->getOperand(0)) return InN;
3311
3312   // See if the modified node already exists.
3313   void *InsertPos = 0;
3314   if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
3315     return SDOperand(Existing, InN.ResNo);
3316
3317   // Nope it doesn't.  Remove the node from it's current place in the maps.
3318   if (InsertPos)
3319     RemoveNodeFromCSEMaps(N);
3320
3321   // Now we update the operands.
3322   N->OperandList[0].getVal()->removeUser(0, N);
3323   N->OperandList[0] = Op;
3324   N->OperandList[0].setUser(N);
3325   Op.Val->addUser(0, N);
3326
3327   // If this gets put into a CSE map, add it.
3328   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3329   return InN;
3330 }
3331
3332 SDOperand SelectionDAG::
3333 UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) {
3334   SDNode *N = InN.Val;
3335   assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
3336
3337   // Check to see if there is no change.
3338   if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
3339     return InN;   // No operands changed, just return the input node.
3340
3341   // See if the modified node already exists.
3342   void *InsertPos = 0;
3343   if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
3344     return SDOperand(Existing, InN.ResNo);
3345
3346   // Nope it doesn't.  Remove the node from it's current place in the maps.
3347   if (InsertPos)
3348     RemoveNodeFromCSEMaps(N);
3349
3350   // Now we update the operands.
3351   if (N->OperandList[0] != Op1) {
3352     N->OperandList[0].getVal()->removeUser(0, N);
3353     N->OperandList[0] = Op1;
3354     N->OperandList[0].setUser(N);
3355     Op1.Val->addUser(0, N);
3356   }
3357   if (N->OperandList[1] != Op2) {
3358     N->OperandList[1].getVal()->removeUser(1, N);
3359     N->OperandList[1] = Op2;
3360     N->OperandList[1].setUser(N);
3361     Op2.Val->addUser(1, N);
3362   }
3363
3364   // If this gets put into a CSE map, add it.
3365   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3366   return InN;
3367 }
3368
3369 SDOperand SelectionDAG::
3370 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
3371   SDOperand Ops[] = { Op1, Op2, Op3 };
3372   return UpdateNodeOperands(N, Ops, 3);
3373 }
3374
3375 SDOperand SelectionDAG::
3376 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
3377                    SDOperand Op3, SDOperand Op4) {
3378   SDOperand Ops[] = { Op1, Op2, Op3, Op4 };
3379   return UpdateNodeOperands(N, Ops, 4);
3380 }
3381
3382 SDOperand SelectionDAG::
3383 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
3384                    SDOperand Op3, SDOperand Op4, SDOperand Op5) {
3385   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
3386   return UpdateNodeOperands(N, Ops, 5);
3387 }
3388
3389 SDOperand SelectionDAG::
3390 UpdateNodeOperands(SDOperand InN, SDOperandPtr Ops, unsigned NumOps) {
3391   SDNode *N = InN.Val;
3392   assert(N->getNumOperands() == NumOps &&
3393          "Update with wrong number of operands");
3394
3395   // Check to see if there is no change.
3396   bool AnyChange = false;
3397   for (unsigned i = 0; i != NumOps; ++i) {
3398     if (Ops[i] != N->getOperand(i)) {
3399       AnyChange = true;
3400       break;
3401     }
3402   }
3403
3404   // No operands changed, just return the input node.
3405   if (!AnyChange) return InN;
3406
3407   // See if the modified node already exists.
3408   void *InsertPos = 0;
3409   if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
3410     return SDOperand(Existing, InN.ResNo);
3411
3412   // Nope it doesn't.  Remove the node from it's current place in the maps.
3413   if (InsertPos)
3414     RemoveNodeFromCSEMaps(N);
3415
3416   // Now we update the operands.
3417   for (unsigned i = 0; i != NumOps; ++i) {
3418     if (N->OperandList[i] != Ops[i]) {
3419       N->OperandList[i].getVal()->removeUser(i, N);
3420       N->OperandList[i] = Ops[i];
3421       N->OperandList[i].setUser(N);
3422       Ops[i].Val->addUser(i, N);
3423     }
3424   }
3425
3426   // If this gets put into a CSE map, add it.
3427   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3428   return InN;
3429 }
3430
3431 /// MorphNodeTo - This frees the operands of the current node, resets the
3432 /// opcode, types, and operands to the specified value.  This should only be
3433 /// used by the SelectionDAG class.
3434 void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
3435                          SDOperandPtr Ops, unsigned NumOps) {
3436   NodeType = Opc;
3437   ValueList = L.VTs;
3438   NumValues = L.NumVTs;
3439
3440   // Clear the operands list, updating used nodes to remove this from their
3441   // use list.
3442   for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
3443     I->getVal()->removeUser(std::distance(op_begin(), I), this);
3444
3445   // If NumOps is larger than the # of operands we currently have, reallocate
3446   // the operand list.
3447   if (NumOps > NumOperands) {
3448     if (OperandsNeedDelete) {
3449       delete [] OperandList;
3450     }
3451     OperandList = new SDUse[NumOps];
3452     OperandsNeedDelete = true;
3453   }
3454
3455   // Assign the new operands.
3456   NumOperands = NumOps;
3457
3458   for (unsigned i = 0, e = NumOps; i != e; ++i) {
3459     OperandList[i] = Ops[i];
3460     OperandList[i].setUser(this);
3461     SDNode *N = OperandList[i].getVal();
3462     N->addUser(i, this);
3463     ++N->UsesSize;
3464   }
3465 }
3466
3467 /// SelectNodeTo - These are used for target selectors to *mutate* the
3468 /// specified node to have the specified return type, Target opcode, and
3469 /// operands.  Note that target opcodes are stored as
3470 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
3471 ///
3472 /// Note that SelectNodeTo returns the resultant node.  If there is already a
3473 /// node of the specified opcode and operands, it returns that node instead of
3474 /// the current one.
3475 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3476                                    MVT::ValueType VT) {
3477   SDVTList VTs = getVTList(VT);
3478   FoldingSetNodeID ID;
3479   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, (SDOperand*)0, 0);
3480   void *IP = 0;
3481   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3482     return ON;
3483
3484   RemoveNodeFromCSEMaps(N);
3485
3486   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, SDOperandPtr(), 0);
3487
3488   CSEMap.InsertNode(N, IP);
3489   return N;
3490 }
3491
3492 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3493                                    MVT::ValueType VT, SDOperand Op1) {
3494   // If an identical node already exists, use it.
3495   SDVTList VTs = getVTList(VT);
3496   SDOperand Ops[] = { Op1 };
3497
3498   FoldingSetNodeID ID;
3499   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1);
3500   void *IP = 0;
3501   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3502     return ON;
3503
3504   RemoveNodeFromCSEMaps(N);
3505   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1);
3506   CSEMap.InsertNode(N, IP);
3507   return N;
3508 }
3509
3510 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3511                                    MVT::ValueType VT, SDOperand Op1,
3512                                    SDOperand Op2) {
3513   // If an identical node already exists, use it.
3514   SDVTList VTs = getVTList(VT);
3515   SDOperand Ops[] = { Op1, Op2 };
3516
3517   FoldingSetNodeID ID;
3518   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3519   void *IP = 0;
3520   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3521     return ON;
3522
3523   RemoveNodeFromCSEMaps(N);
3524
3525   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3526
3527   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3528   return N;
3529 }
3530
3531 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3532                                    MVT::ValueType VT, SDOperand Op1,
3533                                    SDOperand Op2, SDOperand Op3) {
3534   // If an identical node already exists, use it.
3535   SDVTList VTs = getVTList(VT);
3536   SDOperand Ops[] = { Op1, Op2, Op3 };
3537   FoldingSetNodeID ID;
3538   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3539   void *IP = 0;
3540   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3541     return ON;
3542
3543   RemoveNodeFromCSEMaps(N);
3544
3545   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3546
3547   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3548   return N;
3549 }
3550
3551 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3552                                    MVT::ValueType VT, SDOperandPtr Ops,
3553                                    unsigned NumOps) {
3554   // If an identical node already exists, use it.
3555   SDVTList VTs = getVTList(VT);
3556   FoldingSetNodeID ID;
3557   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
3558   void *IP = 0;
3559   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3560     return ON;
3561
3562   RemoveNodeFromCSEMaps(N);
3563   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
3564
3565   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3566   return N;
3567 }
3568
3569 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3570                                    MVT::ValueType VT1, MVT::ValueType VT2,
3571                                    SDOperand Op1, SDOperand Op2) {
3572   SDVTList VTs = getVTList(VT1, VT2);
3573   FoldingSetNodeID ID;
3574   SDOperand Ops[] = { Op1, Op2 };
3575   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3576   void *IP = 0;
3577   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3578     return ON;
3579
3580   RemoveNodeFromCSEMaps(N);
3581   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3582   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3583   return N;
3584 }
3585
3586 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3587                                    MVT::ValueType VT1, MVT::ValueType VT2,
3588                                    SDOperand Op1, SDOperand Op2,
3589                                    SDOperand Op3) {
3590   // If an identical node already exists, use it.
3591   SDVTList VTs = getVTList(VT1, VT2);
3592   SDOperand Ops[] = { Op1, Op2, Op3 };
3593   FoldingSetNodeID ID;
3594   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3595   void *IP = 0;
3596   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3597     return ON;
3598
3599   RemoveNodeFromCSEMaps(N);
3600
3601   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3602   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3603   return N;
3604 }
3605
3606
3607 /// getTargetNode - These are used for target selectors to create a new node
3608 /// with specified return type(s), target opcode, and operands.
3609 ///
3610 /// Note that getTargetNode returns the resultant node.  If there is already a
3611 /// node of the specified opcode and operands, it returns that node instead of
3612 /// the current one.
3613 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) {
3614   return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val;
3615 }
3616 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3617                                     SDOperand Op1) {
3618   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val;
3619 }
3620 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3621                                     SDOperand Op1, SDOperand Op2) {
3622   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val;
3623 }
3624 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3625                                     SDOperand Op1, SDOperand Op2,
3626                                     SDOperand Op3) {
3627   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
3628 }
3629 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3630                                     SDOperandPtr Ops, unsigned NumOps) {
3631   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val;
3632 }
3633 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3634                                     MVT::ValueType VT2) {
3635   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3636   SDOperand Op;
3637   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op, 0).Val;
3638 }
3639 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3640                                     MVT::ValueType VT2, SDOperand Op1) {
3641   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3642   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val;
3643 }
3644 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3645                                     MVT::ValueType VT2, SDOperand Op1,
3646                                     SDOperand Op2) {
3647   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3648   SDOperand Ops[] = { Op1, Op2 };
3649   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val;
3650 }
3651 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3652                                     MVT::ValueType VT2, SDOperand Op1,
3653                                     SDOperand Op2, SDOperand Op3) {
3654   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3655   SDOperand Ops[] = { Op1, Op2, Op3 };
3656   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val;
3657 }
3658 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3659                                     MVT::ValueType VT2,
3660                                     SDOperandPtr Ops, unsigned NumOps) {
3661   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3662   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val;
3663 }
3664 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3665                                     MVT::ValueType VT2, MVT::ValueType VT3,
3666                                     SDOperand Op1, SDOperand Op2) {
3667   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
3668   SDOperand Ops[] = { Op1, Op2 };
3669   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val;
3670 }
3671 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3672                                     MVT::ValueType VT2, MVT::ValueType VT3,
3673                                     SDOperand Op1, SDOperand Op2,
3674                                     SDOperand Op3) {
3675   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
3676   SDOperand Ops[] = { Op1, Op2, Op3 };
3677   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 3).Val;
3678 }
3679 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3680                                     MVT::ValueType VT2, MVT::ValueType VT3,
3681                                     SDOperandPtr Ops, unsigned NumOps) {
3682   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
3683   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val;
3684 }
3685 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3686                                     MVT::ValueType VT2, MVT::ValueType VT3,
3687                                     MVT::ValueType VT4,
3688                                     SDOperandPtr Ops, unsigned NumOps) {
3689   std::vector<MVT::ValueType> VTList;
3690   VTList.push_back(VT1);
3691   VTList.push_back(VT2);
3692   VTList.push_back(VT3);
3693   VTList.push_back(VT4);
3694   const MVT::ValueType *VTs = getNodeValueTypes(VTList);
3695   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 4, Ops, NumOps).Val;
3696 }
3697 SDNode *SelectionDAG::getTargetNode(unsigned Opcode,
3698                                     std::vector<MVT::ValueType> &ResultTys,
3699                                     SDOperandPtr Ops, unsigned NumOps) {
3700   const MVT::ValueType *VTs = getNodeValueTypes(ResultTys);
3701   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, ResultTys.size(),
3702                  Ops, NumOps).Val;
3703 }
3704
3705 /// getNodeIfExists - Get the specified node if it's already available, or
3706 /// else return NULL.
3707 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
3708                                       SDOperandPtr Ops, unsigned NumOps) {
3709   if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
3710     FoldingSetNodeID ID;
3711     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
3712     void *IP = 0;
3713     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3714       return E;
3715   }
3716   return NULL;
3717 }
3718
3719
3720 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3721 /// This can cause recursive merging of nodes in the DAG.
3722 ///
3723 /// This version assumes From has a single result value.
3724 ///
3725 void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To,
3726                                       DAGUpdateListener *UpdateListener) {
3727   SDNode *From = FromN.Val;
3728   assert(From->getNumValues() == 1 && FromN.ResNo == 0 &&
3729          "Cannot replace with this method!");
3730   assert(From != To.Val && "Cannot replace uses of with self");
3731
3732   while (!From->use_empty()) {
3733     SDNode::use_iterator UI = From->use_begin();
3734     SDNode *U = UI->getUser();
3735
3736     // This node is about to morph, remove its old self from the CSE maps.
3737     RemoveNodeFromCSEMaps(U);
3738     int operandNum = 0;
3739     for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
3740          I != E; ++I, ++operandNum)
3741       if (I->getVal() == From) {
3742         From->removeUser(operandNum, U);
3743         *I = To;
3744         I->setUser(U);
3745         To.Val->addUser(operandNum, U);
3746       }
3747
3748     // Now that we have modified U, add it back to the CSE maps.  If it already
3749     // exists there, recursively merge the results together.
3750     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
3751       ReplaceAllUsesWith(U, Existing, UpdateListener);
3752       // U is now dead.  Inform the listener if it exists and delete it.
3753       if (UpdateListener)
3754         UpdateListener->NodeDeleted(U);
3755       DeleteNodeNotInCSEMaps(U);
3756     } else {
3757       // If the node doesn't already exist, we updated it.  Inform a listener if
3758       // it exists.
3759       if (UpdateListener)
3760         UpdateListener->NodeUpdated(U);
3761     }
3762   }
3763 }
3764
3765 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3766 /// This can cause recursive merging of nodes in the DAG.
3767 ///
3768 /// This version assumes From/To have matching types and numbers of result
3769 /// values.
3770 ///
3771 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
3772                                       DAGUpdateListener *UpdateListener) {
3773   assert(From != To && "Cannot replace uses of with self");
3774   assert(From->getNumValues() == To->getNumValues() &&
3775          "Cannot use this version of ReplaceAllUsesWith!");
3776   if (From->getNumValues() == 1)   // If possible, use the faster version.
3777     return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0),
3778                               UpdateListener);
3779
3780   while (!From->use_empty()) {
3781     SDNode::use_iterator UI = From->use_begin();
3782     SDNode *U = UI->getUser();
3783
3784     // This node is about to morph, remove its old self from the CSE maps.
3785     RemoveNodeFromCSEMaps(U);
3786     int operandNum = 0;
3787     for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
3788          I != E; ++I, ++operandNum)
3789       if (I->getVal() == From) {
3790         From->removeUser(operandNum, U);
3791         I->getVal() = To;
3792         To->addUser(operandNum, U);
3793       }
3794
3795     // Now that we have modified U, add it back to the CSE maps.  If it already
3796     // exists there, recursively merge the results together.
3797     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
3798       ReplaceAllUsesWith(U, Existing, UpdateListener);
3799       // U is now dead.  Inform the listener if it exists and delete it.
3800       if (UpdateListener)
3801         UpdateListener->NodeDeleted(U);
3802       DeleteNodeNotInCSEMaps(U);
3803     } else {
3804       // If the node doesn't already exist, we updated it.  Inform a listener if
3805       // it exists.
3806       if (UpdateListener)
3807         UpdateListener->NodeUpdated(U);
3808     }
3809   }
3810 }
3811
3812 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3813 /// This can cause recursive merging of nodes in the DAG.
3814 ///
3815 /// This version can replace From with any result values.  To must match the
3816 /// number and types of values returned by From.
3817 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
3818                                       SDOperandPtr To,
3819                                       DAGUpdateListener *UpdateListener) {
3820   if (From->getNumValues() == 1)  // Handle the simple case efficiently.
3821     return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener);
3822
3823   while (!From->use_empty()) {
3824     SDNode::use_iterator UI = From->use_begin();
3825     SDNode *U = UI->getUser();
3826
3827     // This node is about to morph, remove its old self from the CSE maps.
3828     RemoveNodeFromCSEMaps(U);
3829     int operandNum = 0;
3830     for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
3831          I != E; ++I, ++operandNum)
3832       if (I->getVal() == From) {
3833         const SDOperand &ToOp = To[I->getSDOperand().ResNo];
3834         From->removeUser(operandNum, U);
3835         *I = ToOp;
3836         I->setUser(U);
3837         ToOp.Val->addUser(operandNum, U);
3838       }
3839
3840     // Now that we have modified U, add it back to the CSE maps.  If it already
3841     // exists there, recursively merge the results together.
3842     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
3843       ReplaceAllUsesWith(U, Existing, UpdateListener);
3844       // U is now dead.  Inform the listener if it exists and delete it.
3845       if (UpdateListener)
3846         UpdateListener->NodeDeleted(U);
3847       DeleteNodeNotInCSEMaps(U);
3848     } else {
3849       // If the node doesn't already exist, we updated it.  Inform a listener if
3850       // it exists.
3851       if (UpdateListener)
3852         UpdateListener->NodeUpdated(U);
3853     }
3854   }
3855 }
3856
3857 namespace {
3858   /// ChainedSetUpdaterListener - This class is a DAGUpdateListener that removes
3859   /// any deleted nodes from the set passed into its constructor and recursively
3860   /// notifies another update listener if specified.
3861   class ChainedSetUpdaterListener :
3862   public SelectionDAG::DAGUpdateListener {
3863     SmallSetVector<SDNode*, 16> &Set;
3864     SelectionDAG::DAGUpdateListener *Chain;
3865   public:
3866     ChainedSetUpdaterListener(SmallSetVector<SDNode*, 16> &set,
3867                               SelectionDAG::DAGUpdateListener *chain)
3868       : Set(set), Chain(chain) {}
3869
3870     virtual void NodeDeleted(SDNode *N) {
3871       Set.remove(N);
3872       if (Chain) Chain->NodeDeleted(N);
3873     }
3874     virtual void NodeUpdated(SDNode *N) {
3875       if (Chain) Chain->NodeUpdated(N);
3876     }
3877   };
3878 }
3879
3880 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
3881 /// uses of other values produced by From.Val alone.  The Deleted vector is
3882 /// handled the same way as for ReplaceAllUsesWith.
3883 void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
3884                                              DAGUpdateListener *UpdateListener){
3885   assert(From != To && "Cannot replace a value with itself");
3886
3887   // Handle the simple, trivial, case efficiently.
3888   if (From.Val->getNumValues() == 1) {
3889     ReplaceAllUsesWith(From, To, UpdateListener);
3890     return;
3891   }
3892
3893   if (From.use_empty()) return;
3894
3895   // Get all of the users of From.Val.  We want these in a nice,
3896   // deterministically ordered and uniqued set, so we use a SmallSetVector.
3897   SmallSetVector<SDNode*, 16> Users;
3898   for (SDNode::use_iterator UI = From.Val->use_begin(),
3899       E = From.Val->use_end(); UI != E; ++UI) {
3900     SDNode *User = UI->getUser();
3901     if (!Users.count(User))
3902       Users.insert(User);
3903   }
3904
3905   // When one of the recursive merges deletes nodes from the graph, we need to
3906   // make sure that UpdateListener is notified *and* that the node is removed
3907   // from Users if present.  CSUL does this.
3908   ChainedSetUpdaterListener CSUL(Users, UpdateListener);
3909
3910   while (!Users.empty()) {
3911     // We know that this user uses some value of From.  If it is the right
3912     // value, update it.
3913     SDNode *User = Users.back();
3914     Users.pop_back();
3915
3916     // Scan for an operand that matches From.
3917     SDNode::op_iterator Op = User->op_begin(), E = User->op_end();
3918     for (; Op != E; ++Op)
3919       if (*Op == From) break;
3920
3921     // If there are no matches, the user must use some other result of From.
3922     if (Op == E) continue;
3923
3924     // Okay, we know this user needs to be updated.  Remove its old self
3925     // from the CSE maps.
3926     RemoveNodeFromCSEMaps(User);
3927
3928     // Update all operands that match "From" in case there are multiple uses.
3929     for (; Op != E; ++Op) {
3930       if (*Op == From) {
3931         From.Val->removeUser(Op-User->op_begin(), User);
3932         *Op = To;
3933         Op->setUser(User);
3934         To.Val->addUser(Op-User->op_begin(), User);
3935       }
3936     }
3937
3938     // Now that we have modified User, add it back to the CSE maps.  If it
3939     // already exists there, recursively merge the results together.
3940     SDNode *Existing = AddNonLeafNodeToCSEMaps(User);
3941     if (!Existing) {
3942       if (UpdateListener) UpdateListener->NodeUpdated(User);
3943       continue;  // Continue on to next user.
3944     }
3945
3946     // If there was already an existing matching node, use ReplaceAllUsesWith
3947     // to replace the dead one with the existing one.  This can cause
3948     // recursive merging of other unrelated nodes down the line.  The merging
3949     // can cause deletion of nodes that used the old value.  To handle this, we
3950     // use CSUL to remove them from the Users set.
3951     ReplaceAllUsesWith(User, Existing, &CSUL);
3952
3953     // User is now dead.  Notify a listener if present.
3954     if (UpdateListener) UpdateListener->NodeDeleted(User);
3955     DeleteNodeNotInCSEMaps(User);
3956   }
3957 }
3958
3959 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on
3960 /// their allnodes order. It returns the maximum id.
3961 unsigned SelectionDAG::AssignNodeIds() {
3962   unsigned Id = 0;
3963   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){
3964     SDNode *N = I;
3965     N->setNodeId(Id++);
3966   }
3967   return Id;
3968 }
3969
3970 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
3971 /// based on their topological order. It returns the maximum id and a vector
3972 /// of the SDNodes* in assigned order by reference.
3973 unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
3974   unsigned DAGSize = AllNodes.size();
3975   std::vector<unsigned> InDegree(DAGSize);
3976   std::vector<SDNode*> Sources;
3977
3978   // Use a two pass approach to avoid using a std::map which is slow.
3979   unsigned Id = 0;
3980   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
3981     SDNode *N = I;
3982     N->setNodeId(Id++);
3983     unsigned Degree = N->use_size();
3984     InDegree[N->getNodeId()] = Degree;
3985     if (Degree == 0)
3986       Sources.push_back(N);
3987   }
3988
3989   TopOrder.clear();
3990   while (!Sources.empty()) {
3991     SDNode *N = Sources.back();
3992     Sources.pop_back();
3993     TopOrder.push_back(N);
3994     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
3995       SDNode *P = I->getVal();
3996       unsigned Degree = --InDegree[P->getNodeId()];
3997       if (Degree == 0)
3998         Sources.push_back(P);
3999     }
4000   }
4001
4002   // Second pass, assign the actual topological order as node ids.
4003   Id = 0;
4004   for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end();
4005        TI != TE; ++TI)
4006     (*TI)->setNodeId(Id++);
4007
4008   return Id;
4009 }
4010
4011
4012
4013 //===----------------------------------------------------------------------===//
4014 //                              SDNode Class
4015 //===----------------------------------------------------------------------===//
4016
4017 // Out-of-line virtual method to give class a home.
4018 void SDNode::ANCHOR() {}
4019 void UnarySDNode::ANCHOR() {}
4020 void BinarySDNode::ANCHOR() {}
4021 void TernarySDNode::ANCHOR() {}
4022 void HandleSDNode::ANCHOR() {}
4023 void StringSDNode::ANCHOR() {}
4024 void ConstantSDNode::ANCHOR() {}
4025 void ConstantFPSDNode::ANCHOR() {}
4026 void GlobalAddressSDNode::ANCHOR() {}
4027 void FrameIndexSDNode::ANCHOR() {}
4028 void JumpTableSDNode::ANCHOR() {}
4029 void ConstantPoolSDNode::ANCHOR() {}
4030 void BasicBlockSDNode::ANCHOR() {}
4031 void SrcValueSDNode::ANCHOR() {}
4032 void MemOperandSDNode::ANCHOR() {}
4033 void RegisterSDNode::ANCHOR() {}
4034 void ExternalSymbolSDNode::ANCHOR() {}
4035 void CondCodeSDNode::ANCHOR() {}
4036 void ARG_FLAGSSDNode::ANCHOR() {}
4037 void VTSDNode::ANCHOR() {}
4038 void LoadSDNode::ANCHOR() {}
4039 void StoreSDNode::ANCHOR() {}
4040 void AtomicSDNode::ANCHOR() {}
4041
4042 HandleSDNode::~HandleSDNode() {
4043   SDVTList VTs = { 0, 0 };
4044   MorphNodeTo(ISD::HANDLENODE, VTs, SDOperandPtr(), 0);  // Drops operand uses.
4045 }
4046
4047 GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA,
4048                                          MVT::ValueType VT, int o)
4049   : SDNode(isa<GlobalVariable>(GA) &&
4050            cast<GlobalVariable>(GA)->isThreadLocal() ?
4051            // Thread Local
4052            (isTarget ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress) :
4053            // Non Thread Local
4054            (isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress),
4055            getSDVTList(VT)), Offset(o) {
4056   TheGlobal = const_cast<GlobalValue*>(GA);
4057 }
4058
4059 /// getMemOperand - Return a MachineMemOperand object describing the memory
4060 /// reference performed by this load or store.
4061 MachineMemOperand LSBaseSDNode::getMemOperand() const {
4062   int Size = (MVT::getSizeInBits(getMemoryVT()) + 7) >> 3;
4063   int Flags =
4064     getOpcode() == ISD::LOAD ? MachineMemOperand::MOLoad :
4065                                MachineMemOperand::MOStore;
4066   if (IsVolatile) Flags |= MachineMemOperand::MOVolatile;
4067
4068   // Check if the load references a frame index, and does not have
4069   // an SV attached.
4070   const FrameIndexSDNode *FI =
4071     dyn_cast<const FrameIndexSDNode>(getBasePtr().Val);
4072   if (!getSrcValue() && FI)
4073     return MachineMemOperand(PseudoSourceValue::getFixedStack(), Flags,
4074                              FI->getIndex(), Size, Alignment);
4075   else
4076     return MachineMemOperand(getSrcValue(), Flags,
4077                              getSrcValueOffset(), Size, Alignment);
4078 }
4079
4080 /// Profile - Gather unique data for the node.
4081 ///
4082 void SDNode::Profile(FoldingSetNodeID &ID) {
4083   AddNodeIDNode(ID, this);
4084 }
4085
4086 /// getValueTypeList - Return a pointer to the specified value type.
4087 ///
4088 const MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
4089   if (MVT::isExtendedVT(VT)) {
4090     static std::set<MVT::ValueType> EVTs;
4091     return &(*EVTs.insert(VT).first);
4092   } else {
4093     static MVT::ValueType VTs[MVT::LAST_VALUETYPE];
4094     VTs[VT] = VT;
4095     return &VTs[VT];
4096   }
4097 }
4098
4099 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
4100 /// indicated value.  This method ignores uses of other values defined by this
4101 /// operation.
4102 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
4103   assert(Value < getNumValues() && "Bad value!");
4104
4105   // If there is only one value, this is easy.
4106   if (getNumValues() == 1)
4107     return use_size() == NUses;
4108   if (use_size() < NUses) return false;
4109
4110   SDOperand TheValue(const_cast<SDNode *>(this), Value);
4111
4112   SmallPtrSet<SDNode*, 32> UsersHandled;
4113
4114   // TODO: Only iterate over uses of a given value of the node
4115   for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
4116     if (*UI == TheValue) {
4117       if (NUses == 0)
4118         return false;
4119       --NUses;
4120     }
4121   }
4122
4123   // Found exactly the right number of uses?
4124   return NUses == 0;
4125 }
4126
4127
4128 /// hasAnyUseOfValue - Return true if there are any use of the indicated
4129 /// value. This method ignores uses of other values defined by this operation.
4130 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
4131   assert(Value < getNumValues() && "Bad value!");
4132
4133   if (use_empty()) return false;
4134
4135   SDOperand TheValue(const_cast<SDNode *>(this), Value);
4136
4137   SmallPtrSet<SDNode*, 32> UsersHandled;
4138
4139   for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
4140     SDNode *User = UI->getUser();
4141     if (User->getNumOperands() == 1 ||
4142         UsersHandled.insert(User))     // First time we've seen this?
4143       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
4144         if (User->getOperand(i) == TheValue) {
4145           return true;
4146         }
4147   }
4148
4149   return false;
4150 }
4151
4152
4153 /// isOnlyUseOf - Return true if this node is the only use of N.
4154 ///
4155 bool SDNode::isOnlyUseOf(SDNode *N) const {
4156   bool Seen = false;
4157   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
4158     SDNode *User = I->getUser();
4159     if (User == this)
4160       Seen = true;
4161     else
4162       return false;
4163   }
4164
4165   return Seen;
4166 }
4167
4168 /// isOperand - Return true if this node is an operand of N.
4169 ///
4170 bool SDOperand::isOperandOf(SDNode *N) const {
4171   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
4172     if (*this == N->getOperand(i))
4173       return true;
4174   return false;
4175 }
4176
4177 bool SDNode::isOperandOf(SDNode *N) const {
4178   for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
4179     if (this == N->OperandList[i].getVal())
4180       return true;
4181   return false;
4182 }
4183
4184 /// reachesChainWithoutSideEffects - Return true if this operand (which must
4185 /// be a chain) reaches the specified operand without crossing any
4186 /// side-effecting instructions.  In practice, this looks through token
4187 /// factors and non-volatile loads.  In order to remain efficient, this only
4188 /// looks a couple of nodes in, it does not do an exhaustive search.
4189 bool SDOperand::reachesChainWithoutSideEffects(SDOperand Dest,
4190                                                unsigned Depth) const {
4191   if (*this == Dest) return true;
4192
4193   // Don't search too deeply, we just want to be able to see through
4194   // TokenFactor's etc.
4195   if (Depth == 0) return false;
4196
4197   // If this is a token factor, all inputs to the TF happen in parallel.  If any
4198   // of the operands of the TF reach dest, then we can do the xform.
4199   if (getOpcode() == ISD::TokenFactor) {
4200     for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
4201       if (getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
4202         return true;
4203     return false;
4204   }
4205
4206   // Loads don't have side effects, look through them.
4207   if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
4208     if (!Ld->isVolatile())
4209       return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
4210   }
4211   return false;
4212 }
4213
4214
4215 static void findPredecessor(SDNode *N, const SDNode *P, bool &found,
4216                             SmallPtrSet<SDNode *, 32> &Visited) {
4217   if (found || !Visited.insert(N))
4218     return;
4219
4220   for (unsigned i = 0, e = N->getNumOperands(); !found && i != e; ++i) {
4221     SDNode *Op = N->getOperand(i).Val;
4222     if (Op == P) {
4223       found = true;
4224       return;
4225     }
4226     findPredecessor(Op, P, found, Visited);
4227   }
4228 }
4229
4230 /// isPredecessorOf - Return true if this node is a predecessor of N. This node
4231 /// is either an operand of N or it can be reached by recursively traversing
4232 /// up the operands.
4233 /// NOTE: this is an expensive method. Use it carefully.
4234 bool SDNode::isPredecessorOf(SDNode *N) const {
4235   SmallPtrSet<SDNode *, 32> Visited;
4236   bool found = false;
4237   findPredecessor(N, this, found, Visited);
4238   return found;
4239 }
4240
4241 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
4242   assert(Num < NumOperands && "Invalid child # of SDNode!");
4243   return cast<ConstantSDNode>(OperandList[Num])->getValue();
4244 }
4245
4246 std::string SDNode::getOperationName(const SelectionDAG *G) const {
4247   switch (getOpcode()) {
4248   default:
4249     if (getOpcode() < ISD::BUILTIN_OP_END)
4250       return "<<Unknown DAG Node>>";
4251     else {
4252       if (G) {
4253         if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
4254           if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
4255             return TII->get(getOpcode()-ISD::BUILTIN_OP_END).getName();
4256
4257         TargetLowering &TLI = G->getTargetLoweringInfo();
4258         const char *Name =
4259           TLI.getTargetNodeName(getOpcode());
4260         if (Name) return Name;
4261       }
4262
4263       return "<<Unknown Target Node>>";
4264     }
4265
4266   case ISD::PREFETCH:      return "Prefetch";
4267   case ISD::MEMBARRIER:    return "MemBarrier";
4268   case ISD::ATOMIC_LCS:    return "AtomicLCS";
4269   case ISD::ATOMIC_LAS:    return "AtomicLAS";
4270   case ISD::ATOMIC_SWAP:    return "AtomicSWAP";
4271   case ISD::PCMARKER:      return "PCMarker";
4272   case ISD::READCYCLECOUNTER: return "ReadCycleCounter";
4273   case ISD::SRCVALUE:      return "SrcValue";
4274   case ISD::MEMOPERAND:    return "MemOperand";
4275   case ISD::EntryToken:    return "EntryToken";
4276   case ISD::TokenFactor:   return "TokenFactor";
4277   case ISD::AssertSext:    return "AssertSext";
4278   case ISD::AssertZext:    return "AssertZext";
4279
4280   case ISD::STRING:        return "String";
4281   case ISD::BasicBlock:    return "BasicBlock";
4282   case ISD::ARG_FLAGS:     return "ArgFlags";
4283   case ISD::VALUETYPE:     return "ValueType";
4284   case ISD::Register:      return "Register";
4285
4286   case ISD::Constant:      return "Constant";
4287   case ISD::ConstantFP:    return "ConstantFP";
4288   case ISD::GlobalAddress: return "GlobalAddress";
4289   case ISD::GlobalTLSAddress: return "GlobalTLSAddress";
4290   case ISD::FrameIndex:    return "FrameIndex";
4291   case ISD::JumpTable:     return "JumpTable";
4292   case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE";
4293   case ISD::RETURNADDR: return "RETURNADDR";
4294   case ISD::FRAMEADDR: return "FRAMEADDR";
4295   case ISD::FRAME_TO_ARGS_OFFSET: return "FRAME_TO_ARGS_OFFSET";
4296   case ISD::EXCEPTIONADDR: return "EXCEPTIONADDR";
4297   case ISD::EHSELECTION: return "EHSELECTION";
4298   case ISD::EH_RETURN: return "EH_RETURN";
4299   case ISD::ConstantPool:  return "ConstantPool";
4300   case ISD::ExternalSymbol: return "ExternalSymbol";
4301   case ISD::INTRINSIC_WO_CHAIN: {
4302     unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue();
4303     return Intrinsic::getName((Intrinsic::ID)IID);
4304   }
4305   case ISD::INTRINSIC_VOID:
4306   case ISD::INTRINSIC_W_CHAIN: {
4307     unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue();
4308     return Intrinsic::getName((Intrinsic::ID)IID);
4309   }
4310
4311   case ISD::BUILD_VECTOR:   return "BUILD_VECTOR";
4312   case ISD::TargetConstant: return "TargetConstant";
4313   case ISD::TargetConstantFP:return "TargetConstantFP";
4314   case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
4315   case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress";
4316   case ISD::TargetFrameIndex: return "TargetFrameIndex";
4317   case ISD::TargetJumpTable:  return "TargetJumpTable";
4318   case ISD::TargetConstantPool:  return "TargetConstantPool";
4319   case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
4320
4321   case ISD::CopyToReg:     return "CopyToReg";
4322   case ISD::CopyFromReg:   return "CopyFromReg";
4323   case ISD::UNDEF:         return "undef";
4324   case ISD::MERGE_VALUES:  return "merge_values";
4325   case ISD::INLINEASM:     return "inlineasm";
4326   case ISD::LABEL:         return "label";
4327   case ISD::DECLARE:       return "declare";
4328   case ISD::HANDLENODE:    return "handlenode";
4329   case ISD::FORMAL_ARGUMENTS: return "formal_arguments";
4330   case ISD::CALL:          return "call";
4331
4332   // Unary operators
4333   case ISD::FABS:   return "fabs";
4334   case ISD::FNEG:   return "fneg";
4335   case ISD::FSQRT:  return "fsqrt";
4336   case ISD::FSIN:   return "fsin";
4337   case ISD::FCOS:   return "fcos";
4338   case ISD::FPOWI:  return "fpowi";
4339   case ISD::FPOW:   return "fpow";
4340
4341   // Binary operators
4342   case ISD::ADD:    return "add";
4343   case ISD::SUB:    return "sub";
4344   case ISD::MUL:    return "mul";
4345   case ISD::MULHU:  return "mulhu";
4346   case ISD::MULHS:  return "mulhs";
4347   case ISD::SDIV:   return "sdiv";
4348   case ISD::UDIV:   return "udiv";
4349   case ISD::SREM:   return "srem";
4350   case ISD::UREM:   return "urem";
4351   case ISD::SMUL_LOHI:  return "smul_lohi";
4352   case ISD::UMUL_LOHI:  return "umul_lohi";
4353   case ISD::SDIVREM:    return "sdivrem";
4354   case ISD::UDIVREM:    return "divrem";
4355   case ISD::AND:    return "and";
4356   case ISD::OR:     return "or";
4357   case ISD::XOR:    return "xor";
4358   case ISD::SHL:    return "shl";
4359   case ISD::SRA:    return "sra";
4360   case ISD::SRL:    return "srl";
4361   case ISD::ROTL:   return "rotl";
4362   case ISD::ROTR:   return "rotr";
4363   case ISD::FADD:   return "fadd";
4364   case ISD::FSUB:   return "fsub";
4365   case ISD::FMUL:   return "fmul";
4366   case ISD::FDIV:   return "fdiv";
4367   case ISD::FREM:   return "frem";
4368   case ISD::FCOPYSIGN: return "fcopysign";
4369   case ISD::FGETSIGN:  return "fgetsign";
4370
4371   case ISD::SETCC:       return "setcc";
4372   case ISD::SELECT:      return "select";
4373   case ISD::SELECT_CC:   return "select_cc";
4374   case ISD::INSERT_VECTOR_ELT:   return "insert_vector_elt";
4375   case ISD::EXTRACT_VECTOR_ELT:  return "extract_vector_elt";
4376   case ISD::CONCAT_VECTORS:      return "concat_vectors";
4377   case ISD::EXTRACT_SUBVECTOR:   return "extract_subvector";
4378   case ISD::SCALAR_TO_VECTOR:    return "scalar_to_vector";
4379   case ISD::VECTOR_SHUFFLE:      return "vector_shuffle";
4380   case ISD::CARRY_FALSE:         return "carry_false";
4381   case ISD::ADDC:        return "addc";
4382   case ISD::ADDE:        return "adde";
4383   case ISD::SUBC:        return "subc";
4384   case ISD::SUBE:        return "sube";
4385   case ISD::SHL_PARTS:   return "shl_parts";
4386   case ISD::SRA_PARTS:   return "sra_parts";
4387   case ISD::SRL_PARTS:   return "srl_parts";
4388
4389   case ISD::EXTRACT_SUBREG:     return "extract_subreg";
4390   case ISD::INSERT_SUBREG:      return "insert_subreg";
4391
4392   // Conversion operators.
4393   case ISD::SIGN_EXTEND: return "sign_extend";
4394   case ISD::ZERO_EXTEND: return "zero_extend";
4395   case ISD::ANY_EXTEND:  return "any_extend";
4396   case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
4397   case ISD::TRUNCATE:    return "truncate";
4398   case ISD::FP_ROUND:    return "fp_round";
4399   case ISD::FLT_ROUNDS_: return "flt_rounds";
4400   case ISD::FP_ROUND_INREG: return "fp_round_inreg";
4401   case ISD::FP_EXTEND:   return "fp_extend";
4402
4403   case ISD::SINT_TO_FP:  return "sint_to_fp";
4404   case ISD::UINT_TO_FP:  return "uint_to_fp";
4405   case ISD::FP_TO_SINT:  return "fp_to_sint";
4406   case ISD::FP_TO_UINT:  return "fp_to_uint";
4407   case ISD::BIT_CONVERT: return "bit_convert";
4408
4409     // Control flow instructions
4410   case ISD::BR:      return "br";
4411   case ISD::BRIND:   return "brind";
4412   case ISD::BR_JT:   return "br_jt";
4413   case ISD::BRCOND:  return "brcond";
4414   case ISD::BR_CC:   return "br_cc";
4415   case ISD::RET:     return "ret";
4416   case ISD::CALLSEQ_START:  return "callseq_start";
4417   case ISD::CALLSEQ_END:    return "callseq_end";
4418
4419     // Other operators
4420   case ISD::LOAD:               return "load";
4421   case ISD::STORE:              return "store";
4422   case ISD::VAARG:              return "vaarg";
4423   case ISD::VACOPY:             return "vacopy";
4424   case ISD::VAEND:              return "vaend";
4425   case ISD::VASTART:            return "vastart";
4426   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
4427   case ISD::EXTRACT_ELEMENT:    return "extract_element";
4428   case ISD::BUILD_PAIR:         return "build_pair";
4429   case ISD::STACKSAVE:          return "stacksave";
4430   case ISD::STACKRESTORE:       return "stackrestore";
4431   case ISD::TRAP:               return "trap";
4432
4433   // Bit manipulation
4434   case ISD::BSWAP:   return "bswap";
4435   case ISD::CTPOP:   return "ctpop";
4436   case ISD::CTTZ:    return "cttz";
4437   case ISD::CTLZ:    return "ctlz";
4438
4439   // Debug info
4440   case ISD::LOCATION: return "location";
4441   case ISD::DEBUG_LOC: return "debug_loc";
4442
4443   // Trampolines
4444   case ISD::TRAMPOLINE: return "trampoline";
4445
4446   case ISD::CONDCODE:
4447     switch (cast<CondCodeSDNode>(this)->get()) {
4448     default: assert(0 && "Unknown setcc condition!");
4449     case ISD::SETOEQ:  return "setoeq";
4450     case ISD::SETOGT:  return "setogt";
4451     case ISD::SETOGE:  return "setoge";
4452     case ISD::SETOLT:  return "setolt";
4453     case ISD::SETOLE:  return "setole";
4454     case ISD::SETONE:  return "setone";
4455
4456     case ISD::SETO:    return "seto";
4457     case ISD::SETUO:   return "setuo";
4458     case ISD::SETUEQ:  return "setue";
4459     case ISD::SETUGT:  return "setugt";
4460     case ISD::SETUGE:  return "setuge";
4461     case ISD::SETULT:  return "setult";
4462     case ISD::SETULE:  return "setule";
4463     case ISD::SETUNE:  return "setune";
4464
4465     case ISD::SETEQ:   return "seteq";
4466     case ISD::SETGT:   return "setgt";
4467     case ISD::SETGE:   return "setge";
4468     case ISD::SETLT:   return "setlt";
4469     case ISD::SETLE:   return "setle";
4470     case ISD::SETNE:   return "setne";
4471     }
4472   }
4473 }
4474
4475 const char *SDNode::getIndexedModeName(ISD::MemIndexedMode AM) {
4476   switch (AM) {
4477   default:
4478     return "";
4479   case ISD::PRE_INC:
4480     return "<pre-inc>";
4481   case ISD::PRE_DEC:
4482     return "<pre-dec>";
4483   case ISD::POST_INC:
4484     return "<post-inc>";
4485   case ISD::POST_DEC:
4486     return "<post-dec>";
4487   }
4488 }
4489
4490 std::string ISD::ArgFlagsTy::getArgFlagsString() {
4491   std::string S = "< ";
4492
4493   if (isZExt())
4494     S += "zext ";
4495   if (isSExt())
4496     S += "sext ";
4497   if (isInReg())
4498     S += "inreg ";
4499   if (isSRet())
4500     S += "sret ";
4501   if (isByVal())
4502     S += "byval ";
4503   if (isNest())
4504     S += "nest ";
4505   if (getByValAlign())
4506     S += "byval-align:" + utostr(getByValAlign()) + " ";
4507   if (getOrigAlign())
4508     S += "orig-align:" + utostr(getOrigAlign()) + " ";
4509   if (getByValSize())
4510     S += "byval-size:" + utostr(getByValSize()) + " ";
4511   return S + ">";
4512 }
4513
4514 void SDNode::dump() const { dump(0); }
4515 void SDNode::dump(const SelectionDAG *G) const {
4516   cerr << (void*)this << ": ";
4517
4518   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
4519     if (i) cerr << ",";
4520     if (getValueType(i) == MVT::Other)
4521       cerr << "ch";
4522     else
4523       cerr << MVT::getValueTypeString(getValueType(i));
4524   }
4525   cerr << " = " << getOperationName(G);
4526
4527   cerr << " ";
4528   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
4529     if (i) cerr << ", ";
4530     cerr << (void*)getOperand(i).Val;
4531     if (unsigned RN = getOperand(i).ResNo)
4532       cerr << ":" << RN;
4533   }
4534
4535   if (!isTargetOpcode() && getOpcode() == ISD::VECTOR_SHUFFLE) {
4536     SDNode *Mask = getOperand(2).Val;
4537     cerr << "<";
4538     for (unsigned i = 0, e = Mask->getNumOperands(); i != e; ++i) {
4539       if (i) cerr << ",";
4540       if (Mask->getOperand(i).getOpcode() == ISD::UNDEF)
4541         cerr << "u";
4542       else
4543         cerr << cast<ConstantSDNode>(Mask->getOperand(i))->getValue();
4544     }
4545     cerr << ">";
4546   }
4547
4548   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
4549     cerr << "<" << CSDN->getValue() << ">";
4550   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
4551     if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEsingle)
4552       cerr << "<" << CSDN->getValueAPF().convertToFloat() << ">";
4553     else if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEdouble)
4554       cerr << "<" << CSDN->getValueAPF().convertToDouble() << ">";
4555     else {
4556       cerr << "<APFloat(";
4557       CSDN->getValueAPF().convertToAPInt().dump();
4558       cerr << ")>";
4559     }
4560   } else if (const GlobalAddressSDNode *GADN =
4561              dyn_cast<GlobalAddressSDNode>(this)) {
4562     int offset = GADN->getOffset();
4563     cerr << "<";
4564     WriteAsOperand(*cerr.stream(), GADN->getGlobal()) << ">";
4565     if (offset > 0)
4566       cerr << " + " << offset;
4567     else
4568       cerr << " " << offset;
4569   } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
4570     cerr << "<" << FIDN->getIndex() << ">";
4571   } else if (const JumpTableSDNode *JTDN = dyn_cast<JumpTableSDNode>(this)) {
4572     cerr << "<" << JTDN->getIndex() << ">";
4573   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
4574     int offset = CP->getOffset();
4575     if (CP->isMachineConstantPoolEntry())
4576       cerr << "<" << *CP->getMachineCPVal() << ">";
4577     else
4578       cerr << "<" << *CP->getConstVal() << ">";
4579     if (offset > 0)
4580       cerr << " + " << offset;
4581     else
4582       cerr << " " << offset;
4583   } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
4584     cerr << "<";
4585     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
4586     if (LBB)
4587       cerr << LBB->getName() << " ";
4588     cerr << (const void*)BBDN->getBasicBlock() << ">";
4589   } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
4590     if (G && R->getReg() &&
4591         TargetRegisterInfo::isPhysicalRegister(R->getReg())) {
4592       cerr << " " << G->getTarget().getRegisterInfo()->getName(R->getReg());
4593     } else {
4594       cerr << " #" << R->getReg();
4595     }
4596   } else if (const ExternalSymbolSDNode *ES =
4597              dyn_cast<ExternalSymbolSDNode>(this)) {
4598     cerr << "'" << ES->getSymbol() << "'";
4599   } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
4600     if (M->getValue())
4601       cerr << "<" << M->getValue() << ">";
4602     else
4603       cerr << "<null>";
4604   } else if (const MemOperandSDNode *M = dyn_cast<MemOperandSDNode>(this)) {
4605     if (M->MO.getValue())
4606       cerr << "<" << M->MO.getValue() << ":" << M->MO.getOffset() << ">";
4607     else
4608       cerr << "<null:" << M->MO.getOffset() << ">";
4609   } else if (const ARG_FLAGSSDNode *N = dyn_cast<ARG_FLAGSSDNode>(this)) {
4610     cerr << N->getArgFlags().getArgFlagsString();
4611   } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
4612     cerr << ":" << MVT::getValueTypeString(N->getVT());
4613   } else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) {
4614     const Value *SrcValue = LD->getSrcValue();
4615     int SrcOffset = LD->getSrcValueOffset();
4616     cerr << " <";
4617     if (SrcValue)
4618       cerr << SrcValue;
4619     else
4620       cerr << "null";
4621     cerr << ":" << SrcOffset << ">";
4622
4623     bool doExt = true;
4624     switch (LD->getExtensionType()) {
4625     default: doExt = false; break;
4626     case ISD::EXTLOAD:
4627       cerr << " <anyext ";
4628       break;
4629     case ISD::SEXTLOAD:
4630       cerr << " <sext ";
4631       break;
4632     case ISD::ZEXTLOAD:
4633       cerr << " <zext ";
4634       break;
4635     }
4636     if (doExt)
4637       cerr << MVT::getValueTypeString(LD->getMemoryVT()) << ">";
4638
4639     const char *AM = getIndexedModeName(LD->getAddressingMode());
4640     if (*AM)
4641       cerr << " " << AM;
4642     if (LD->isVolatile())
4643       cerr << " <volatile>";
4644     cerr << " alignment=" << LD->getAlignment();
4645   } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) {
4646     const Value *SrcValue = ST->getSrcValue();
4647     int SrcOffset = ST->getSrcValueOffset();
4648     cerr << " <";
4649     if (SrcValue)
4650       cerr << SrcValue;
4651     else
4652       cerr << "null";
4653     cerr << ":" << SrcOffset << ">";
4654
4655     if (ST->isTruncatingStore())
4656       cerr << " <trunc "
4657            << MVT::getValueTypeString(ST->getMemoryVT()) << ">";
4658
4659     const char *AM = getIndexedModeName(ST->getAddressingMode());
4660     if (*AM)
4661       cerr << " " << AM;
4662     if (ST->isVolatile())
4663       cerr << " <volatile>";
4664     cerr << " alignment=" << ST->getAlignment();
4665   }
4666 }
4667
4668 static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
4669   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
4670     if (N->getOperand(i).Val->hasOneUse())
4671       DumpNodes(N->getOperand(i).Val, indent+2, G);
4672     else
4673       cerr << "\n" << std::string(indent+2, ' ')
4674            << (void*)N->getOperand(i).Val << ": <multiple use>";
4675
4676
4677   cerr << "\n" << std::string(indent, ' ');
4678   N->dump(G);
4679 }
4680
4681 void SelectionDAG::dump() const {
4682   cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
4683   std::vector<const SDNode*> Nodes;
4684   for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
4685        I != E; ++I)
4686     Nodes.push_back(I);
4687
4688   std::sort(Nodes.begin(), Nodes.end());
4689
4690   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
4691     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
4692       DumpNodes(Nodes[i], 2, this);
4693   }
4694
4695   if (getRoot().Val) DumpNodes(getRoot().Val, 2, this);
4696
4697   cerr << "\n\n";
4698 }
4699
4700 const Type *ConstantPoolSDNode::getType() const {
4701   if (isMachineConstantPoolEntry())
4702     return Val.MachineCPVal->getType();
4703   return Val.ConstVal->getType();
4704 }