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                                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 less 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     unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros();
1271     if (RHSUnknownLeadingOnes != BitWidth)
1272       LeadZ = std::min(BitWidth,
1273                        LeadZ + BitWidth - RHSUnknownLeadingOnes - 1);
1274
1275     KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask;
1276     return;
1277   }
1278   case ISD::SELECT:
1279     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
1280     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
1281     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1282     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1283
1284     // Only known if known in both the LHS and RHS.
1285     KnownOne &= KnownOne2;
1286     KnownZero &= KnownZero2;
1287     return;
1288   case ISD::SELECT_CC:
1289     ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1);
1290     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1);
1291     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1292     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1293
1294     // Only known if known in both the LHS and RHS.
1295     KnownOne &= KnownOne2;
1296     KnownZero &= KnownZero2;
1297     return;
1298   case ISD::SETCC:
1299     // If we know the result of a setcc has the top bits zero, use this info.
1300     if (TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult &&
1301         BitWidth > 1)
1302       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1303     return;
1304   case ISD::SHL:
1305     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
1306     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1307       unsigned ShAmt = SA->getValue();
1308
1309       // If the shift count is an invalid immediate, don't do anything.
1310       if (ShAmt >= BitWidth)
1311         return;
1312
1313       ComputeMaskedBits(Op.getOperand(0), Mask.lshr(ShAmt),
1314                         KnownZero, KnownOne, Depth+1);
1315       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1316       KnownZero <<= ShAmt;
1317       KnownOne  <<= ShAmt;
1318       // low bits known zero.
1319       KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1320     }
1321     return;
1322   case ISD::SRL:
1323     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
1324     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1325       unsigned ShAmt = SA->getValue();
1326
1327       // If the shift count is an invalid immediate, don't do anything.
1328       if (ShAmt >= BitWidth)
1329         return;
1330
1331       ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt),
1332                         KnownZero, KnownOne, Depth+1);
1333       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1334       KnownZero = KnownZero.lshr(ShAmt);
1335       KnownOne  = KnownOne.lshr(ShAmt);
1336
1337       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1338       KnownZero |= HighBits;  // High bits known zero.
1339     }
1340     return;
1341   case ISD::SRA:
1342     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1343       unsigned ShAmt = SA->getValue();
1344
1345       // If the shift count is an invalid immediate, don't do anything.
1346       if (ShAmt >= BitWidth)
1347         return;
1348
1349       APInt InDemandedMask = (Mask << ShAmt);
1350       // If any of the demanded bits are produced by the sign extension, we also
1351       // demand the input sign bit.
1352       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1353       if (HighBits.getBoolValue())
1354         InDemandedMask |= APInt::getSignBit(BitWidth);
1355
1356       ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne,
1357                         Depth+1);
1358       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1359       KnownZero = KnownZero.lshr(ShAmt);
1360       KnownOne  = KnownOne.lshr(ShAmt);
1361
1362       // Handle the sign bits.
1363       APInt SignBit = APInt::getSignBit(BitWidth);
1364       SignBit = SignBit.lshr(ShAmt);  // Adjust to where it is now in the mask.
1365
1366       if (KnownZero.intersects(SignBit)) {
1367         KnownZero |= HighBits;  // New bits are known zero.
1368       } else if (KnownOne.intersects(SignBit)) {
1369         KnownOne  |= HighBits;  // New bits are known one.
1370       }
1371     }
1372     return;
1373   case ISD::SIGN_EXTEND_INREG: {
1374     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1375     unsigned EBits = MVT::getSizeInBits(EVT);
1376
1377     // Sign extension.  Compute the demanded bits in the result that are not
1378     // present in the input.
1379     APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits) & Mask;
1380
1381     APInt InSignBit = APInt::getSignBit(EBits);
1382     APInt InputDemandedBits = Mask & APInt::getLowBitsSet(BitWidth, EBits);
1383
1384     // If the sign extended bits are demanded, we know that the sign
1385     // bit is demanded.
1386     InSignBit.zext(BitWidth);
1387     if (NewBits.getBoolValue())
1388       InputDemandedBits |= InSignBit;
1389
1390     ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
1391                       KnownZero, KnownOne, Depth+1);
1392     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1393
1394     // If the sign bit of the input is known set or clear, then we know the
1395     // top bits of the result.
1396     if (KnownZero.intersects(InSignBit)) {         // Input sign bit known clear
1397       KnownZero |= NewBits;
1398       KnownOne  &= ~NewBits;
1399     } else if (KnownOne.intersects(InSignBit)) {   // Input sign bit known set
1400       KnownOne  |= NewBits;
1401       KnownZero &= ~NewBits;
1402     } else {                              // Input sign bit unknown
1403       KnownZero &= ~NewBits;
1404       KnownOne  &= ~NewBits;
1405     }
1406     return;
1407   }
1408   case ISD::CTTZ:
1409   case ISD::CTLZ:
1410   case ISD::CTPOP: {
1411     unsigned LowBits = Log2_32(BitWidth)+1;
1412     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1413     KnownOne  = APInt(BitWidth, 0);
1414     return;
1415   }
1416   case ISD::LOAD: {
1417     if (ISD::isZEXTLoad(Op.Val)) {
1418       LoadSDNode *LD = cast<LoadSDNode>(Op);
1419       MVT::ValueType VT = LD->getMemoryVT();
1420       unsigned MemBits = MVT::getSizeInBits(VT);
1421       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits) & Mask;
1422     }
1423     return;
1424   }
1425   case ISD::ZERO_EXTEND: {
1426     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1427     unsigned InBits = MVT::getSizeInBits(InVT);
1428     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1429     APInt InMask    = Mask;
1430     InMask.trunc(InBits);
1431     KnownZero.trunc(InBits);
1432     KnownOne.trunc(InBits);
1433     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1434     KnownZero.zext(BitWidth);
1435     KnownOne.zext(BitWidth);
1436     KnownZero |= NewBits;
1437     return;
1438   }
1439   case ISD::SIGN_EXTEND: {
1440     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1441     unsigned InBits = MVT::getSizeInBits(InVT);
1442     APInt InSignBit = APInt::getSignBit(InBits);
1443     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1444     APInt InMask = Mask;
1445     InMask.trunc(InBits);
1446
1447     // If any of the sign extended bits are demanded, we know that the sign
1448     // bit is demanded. Temporarily set this bit in the mask for our callee.
1449     if (NewBits.getBoolValue())
1450       InMask |= InSignBit;
1451
1452     KnownZero.trunc(InBits);
1453     KnownOne.trunc(InBits);
1454     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1455
1456     // Note if the sign bit is known to be zero or one.
1457     bool SignBitKnownZero = KnownZero.isNegative();
1458     bool SignBitKnownOne  = KnownOne.isNegative();
1459     assert(!(SignBitKnownZero && SignBitKnownOne) &&
1460            "Sign bit can't be known to be both zero and one!");
1461
1462     // If the sign bit wasn't actually demanded by our caller, we don't
1463     // want it set in the KnownZero and KnownOne result values. Reset the
1464     // mask and reapply it to the result values.
1465     InMask = Mask;
1466     InMask.trunc(InBits);
1467     KnownZero &= InMask;
1468     KnownOne  &= InMask;
1469
1470     KnownZero.zext(BitWidth);
1471     KnownOne.zext(BitWidth);
1472
1473     // If the sign bit is known zero or one, the top bits match.
1474     if (SignBitKnownZero)
1475       KnownZero |= NewBits;
1476     else if (SignBitKnownOne)
1477       KnownOne  |= NewBits;
1478     return;
1479   }
1480   case ISD::ANY_EXTEND: {
1481     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1482     unsigned InBits = MVT::getSizeInBits(InVT);
1483     APInt InMask = Mask;
1484     InMask.trunc(InBits);
1485     KnownZero.trunc(InBits);
1486     KnownOne.trunc(InBits);
1487     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1488     KnownZero.zext(BitWidth);
1489     KnownOne.zext(BitWidth);
1490     return;
1491   }
1492   case ISD::TRUNCATE: {
1493     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1494     unsigned InBits = MVT::getSizeInBits(InVT);
1495     APInt InMask = Mask;
1496     InMask.zext(InBits);
1497     KnownZero.zext(InBits);
1498     KnownOne.zext(InBits);
1499     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1500     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1501     KnownZero.trunc(BitWidth);
1502     KnownOne.trunc(BitWidth);
1503     break;
1504   }
1505   case ISD::AssertZext: {
1506     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1507     APInt InMask = APInt::getLowBitsSet(BitWidth, MVT::getSizeInBits(VT));
1508     ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
1509                       KnownOne, Depth+1);
1510     KnownZero |= (~InMask) & Mask;
1511     return;
1512   }
1513   case ISD::FGETSIGN:
1514     // All bits are zero except the low bit.
1515     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1516     return;
1517
1518   case ISD::SUB: {
1519     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) {
1520       // We know that the top bits of C-X are clear if X contains less bits
1521       // than C (i.e. no wrap-around can happen).  For example, 20-X is
1522       // positive if we can prove that X is >= 0 and < 16.
1523       if (CLHS->getAPIntValue().isNonNegative()) {
1524         unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
1525         // NLZ can't be BitWidth with no sign bit
1526         APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
1527         ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero2, KnownOne2,
1528                           Depth+1);
1529
1530         // If all of the MaskV bits are known to be zero, then we know the
1531         // output top bits are zero, because we now know that the output is
1532         // from [0-C].
1533         if ((KnownZero2 & MaskV) == MaskV) {
1534           unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
1535           // Top bits known zero.
1536           KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask;
1537         }
1538       }
1539     }
1540   }
1541   // fall through
1542   case ISD::ADD: {
1543     // Output known-0 bits are known if clear or set in both the low clear bits
1544     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
1545     // low 3 bits clear.
1546     APInt Mask2 = APInt::getLowBitsSet(BitWidth, Mask.countTrailingOnes());
1547     ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1);
1548     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1549     unsigned KnownZeroOut = KnownZero2.countTrailingOnes();
1550
1551     ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero2, KnownOne2, Depth+1);
1552     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1553     KnownZeroOut = std::min(KnownZeroOut,
1554                             KnownZero2.countTrailingOnes());
1555
1556     KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut);
1557     return;
1558   }
1559   case ISD::SREM:
1560     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1561       APInt RA = Rem->getAPIntValue();
1562       if (RA.isPowerOf2() || (-RA).isPowerOf2()) {
1563         APInt LowBits = RA.isStrictlyPositive() ? (RA - 1) : ~RA;
1564         APInt Mask2 = LowBits | APInt::getSignBit(BitWidth);
1565         ComputeMaskedBits(Op.getOperand(0), Mask2,KnownZero2,KnownOne2,Depth+1);
1566
1567         // The sign of a remainder is equal to the sign of the first
1568         // operand (zero being positive).
1569         if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits))
1570           KnownZero2 |= ~LowBits;
1571         else if (KnownOne2[BitWidth-1])
1572           KnownOne2 |= ~LowBits;
1573
1574         KnownZero |= KnownZero2 & Mask;
1575         KnownOne |= KnownOne2 & Mask;
1576
1577         assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
1578       }
1579     }
1580     return;
1581   case ISD::UREM: {
1582     if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1583       APInt RA = Rem->getAPIntValue();
1584       if (RA.isPowerOf2()) {
1585         APInt LowBits = (RA - 1);
1586         APInt Mask2 = LowBits & Mask;
1587         KnownZero |= ~LowBits & Mask;
1588         ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero, KnownOne,Depth+1);
1589         assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?");
1590         break;
1591       }
1592     }
1593
1594     // Since the result is less than or equal to either operand, any leading
1595     // zero bits in either operand must also exist in the result.
1596     APInt AllOnes = APInt::getAllOnesValue(BitWidth);
1597     ComputeMaskedBits(Op.getOperand(0), AllOnes, KnownZero, KnownOne,
1598                       Depth+1);
1599     ComputeMaskedBits(Op.getOperand(1), AllOnes, KnownZero2, KnownOne2,
1600                       Depth+1);
1601
1602     uint32_t Leaders = std::max(KnownZero.countLeadingOnes(),
1603                                 KnownZero2.countLeadingOnes());
1604     KnownOne.clear();
1605     KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask;
1606     return;
1607   }
1608   default:
1609     // Allow the target to implement this method for its nodes.
1610     if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
1611   case ISD::INTRINSIC_WO_CHAIN:
1612   case ISD::INTRINSIC_W_CHAIN:
1613   case ISD::INTRINSIC_VOID:
1614       TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this);
1615     }
1616     return;
1617   }
1618 }
1619
1620 /// ComputeNumSignBits - Return the number of times the sign bit of the
1621 /// register is replicated into the other bits.  We know that at least 1 bit
1622 /// is always equal to the sign bit (itself), but other cases can give us
1623 /// information.  For example, immediately after an "SRA X, 2", we know that
1624 /// the top 3 bits are all equal to each other, so we return 3.
1625 unsigned SelectionDAG::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{
1626   MVT::ValueType VT = Op.getValueType();
1627   assert(MVT::isInteger(VT) && "Invalid VT!");
1628   unsigned VTBits = MVT::getSizeInBits(VT);
1629   unsigned Tmp, Tmp2;
1630
1631   if (Depth == 6)
1632     return 1;  // Limit search depth.
1633
1634   switch (Op.getOpcode()) {
1635   default: break;
1636   case ISD::AssertSext:
1637     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1638     return VTBits-Tmp+1;
1639   case ISD::AssertZext:
1640     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1641     return VTBits-Tmp;
1642
1643   case ISD::Constant: {
1644     const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
1645     // If negative, return # leading ones.
1646     if (Val.isNegative())
1647       return Val.countLeadingOnes();
1648
1649     // Return # leading zeros.
1650     return Val.countLeadingZeros();
1651   }
1652
1653   case ISD::SIGN_EXTEND:
1654     Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType());
1655     return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
1656
1657   case ISD::SIGN_EXTEND_INREG:
1658     // Max of the input and what this extends.
1659     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1660     Tmp = VTBits-Tmp+1;
1661
1662     Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1663     return std::max(Tmp, Tmp2);
1664
1665   case ISD::SRA:
1666     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1667     // SRA X, C   -> adds C sign bits.
1668     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1669       Tmp += C->getValue();
1670       if (Tmp > VTBits) Tmp = VTBits;
1671     }
1672     return Tmp;
1673   case ISD::SHL:
1674     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1675       // shl destroys sign bits.
1676       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1677       if (C->getValue() >= VTBits ||      // Bad shift.
1678           C->getValue() >= Tmp) break;    // Shifted all sign bits out.
1679       return Tmp - C->getValue();
1680     }
1681     break;
1682   case ISD::AND:
1683   case ISD::OR:
1684   case ISD::XOR:    // NOT is handled here.
1685     // Logical binary ops preserve the number of sign bits.
1686     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1687     if (Tmp == 1) return 1;  // Early out.
1688     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1689     return std::min(Tmp, Tmp2);
1690
1691   case ISD::SELECT:
1692     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1693     if (Tmp == 1) return 1;  // Early out.
1694     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1695     return std::min(Tmp, Tmp2);
1696
1697   case ISD::SETCC:
1698     // If setcc returns 0/-1, all bits are sign bits.
1699     if (TLI.getSetCCResultContents() ==
1700         TargetLowering::ZeroOrNegativeOneSetCCResult)
1701       return VTBits;
1702     break;
1703   case ISD::ROTL:
1704   case ISD::ROTR:
1705     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1706       unsigned RotAmt = C->getValue() & (VTBits-1);
1707
1708       // Handle rotate right by N like a rotate left by 32-N.
1709       if (Op.getOpcode() == ISD::ROTR)
1710         RotAmt = (VTBits-RotAmt) & (VTBits-1);
1711
1712       // If we aren't rotating out all of the known-in sign bits, return the
1713       // number that are left.  This handles rotl(sext(x), 1) for example.
1714       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1715       if (Tmp > RotAmt+1) return Tmp-RotAmt;
1716     }
1717     break;
1718   case ISD::ADD:
1719     // Add can have at most one carry bit.  Thus we know that the output
1720     // is, at worst, one more bit than the inputs.
1721     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1722     if (Tmp == 1) return 1;  // Early out.
1723
1724     // Special case decrementing a value (ADD X, -1):
1725     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1726       if (CRHS->isAllOnesValue()) {
1727         APInt KnownZero, KnownOne;
1728         APInt Mask = APInt::getAllOnesValue(VTBits);
1729         ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
1730
1731         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1732         // sign bits set.
1733         if ((KnownZero | APInt(VTBits, 1)) == Mask)
1734           return VTBits;
1735
1736         // If we are subtracting one from a positive number, there is no carry
1737         // out of the result.
1738         if (KnownZero.isNegative())
1739           return Tmp;
1740       }
1741
1742     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1743     if (Tmp2 == 1) return 1;
1744       return std::min(Tmp, Tmp2)-1;
1745     break;
1746
1747   case ISD::SUB:
1748     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1749     if (Tmp2 == 1) return 1;
1750
1751     // Handle NEG.
1752     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1753       if (CLHS->isNullValue()) {
1754         APInt KnownZero, KnownOne;
1755         APInt Mask = APInt::getAllOnesValue(VTBits);
1756         ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1757         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1758         // sign bits set.
1759         if ((KnownZero | APInt(VTBits, 1)) == Mask)
1760           return VTBits;
1761
1762         // If the input is known to be positive (the sign bit is known clear),
1763         // the output of the NEG has the same number of sign bits as the input.
1764         if (KnownZero.isNegative())
1765           return Tmp2;
1766
1767         // Otherwise, we treat this like a SUB.
1768       }
1769
1770     // Sub can have at most one carry bit.  Thus we know that the output
1771     // is, at worst, one more bit than the inputs.
1772     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1773     if (Tmp == 1) return 1;  // Early out.
1774       return std::min(Tmp, Tmp2)-1;
1775     break;
1776   case ISD::TRUNCATE:
1777     // FIXME: it's tricky to do anything useful for this, but it is an important
1778     // case for targets like X86.
1779     break;
1780   }
1781
1782   // Handle LOADX separately here. EXTLOAD case will fallthrough.
1783   if (Op.getOpcode() == ISD::LOAD) {
1784     LoadSDNode *LD = cast<LoadSDNode>(Op);
1785     unsigned ExtType = LD->getExtensionType();
1786     switch (ExtType) {
1787     default: break;
1788     case ISD::SEXTLOAD:    // '17' bits known
1789       Tmp = MVT::getSizeInBits(LD->getMemoryVT());
1790       return VTBits-Tmp+1;
1791     case ISD::ZEXTLOAD:    // '16' bits known
1792       Tmp = MVT::getSizeInBits(LD->getMemoryVT());
1793       return VTBits-Tmp;
1794     }
1795   }
1796
1797   // Allow the target to implement this method for its nodes.
1798   if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1799       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1800       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1801       Op.getOpcode() == ISD::INTRINSIC_VOID) {
1802     unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
1803     if (NumBits > 1) return NumBits;
1804   }
1805
1806   // Finally, if we can prove that the top bits of the result are 0's or 1's,
1807   // use this information.
1808   APInt KnownZero, KnownOne;
1809   APInt Mask = APInt::getAllOnesValue(VTBits);
1810   ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1811
1812   if (KnownZero.isNegative()) {        // sign bit is 0
1813     Mask = KnownZero;
1814   } else if (KnownOne.isNegative()) {  // sign bit is 1;
1815     Mask = KnownOne;
1816   } else {
1817     // Nothing known.
1818     return 1;
1819   }
1820
1821   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
1822   // the number of identical bits in the top of the input value.
1823   Mask = ~Mask;
1824   Mask <<= Mask.getBitWidth()-VTBits;
1825   // Return # leading zeros.  We use 'min' here in case Val was zero before
1826   // shifting.  We don't want to return '64' as for an i32 "0".
1827   return std::min(VTBits, Mask.countLeadingZeros());
1828 }
1829
1830
1831 bool SelectionDAG::isVerifiedDebugInfoDesc(SDOperand Op) const {
1832   GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
1833   if (!GA) return false;
1834   GlobalVariable *GV = dyn_cast<GlobalVariable>(GA->getGlobal());
1835   if (!GV) return false;
1836   MachineModuleInfo *MMI = getMachineModuleInfo();
1837   return MMI && MMI->hasDebugInfo() && MMI->isVerified(GV);
1838 }
1839
1840
1841 /// getNode - Gets or creates the specified node.
1842 ///
1843 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
1844   FoldingSetNodeID ID;
1845   AddNodeIDNode(ID, Opcode, getVTList(VT), (SDOperand*)0, 0);
1846   void *IP = 0;
1847   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1848     return SDOperand(E, 0);
1849   SDNode *N = new SDNode(Opcode, SDNode::getSDVTList(VT));
1850   CSEMap.InsertNode(N, IP);
1851
1852   AllNodes.push_back(N);
1853   return SDOperand(N, 0);
1854 }
1855
1856 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1857                                 SDOperand Operand) {
1858   // Constant fold unary operations with an integer constant operand.
1859   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
1860     const APInt &Val = C->getAPIntValue();
1861     unsigned BitWidth = MVT::getSizeInBits(VT);
1862     switch (Opcode) {
1863     default: break;
1864     case ISD::SIGN_EXTEND:
1865       return getConstant(APInt(Val).sextOrTrunc(BitWidth), VT);
1866     case ISD::ANY_EXTEND:
1867     case ISD::ZERO_EXTEND:
1868     case ISD::TRUNCATE:
1869       return getConstant(APInt(Val).zextOrTrunc(BitWidth), VT);
1870     case ISD::UINT_TO_FP:
1871     case ISD::SINT_TO_FP: {
1872       const uint64_t zero[] = {0, 0};
1873       // No compile time operations on this type.
1874       if (VT==MVT::ppcf128)
1875         break;
1876       APFloat apf = APFloat(APInt(BitWidth, 2, zero));
1877       (void)apf.convertFromAPInt(Val,
1878                                  Opcode==ISD::SINT_TO_FP,
1879                                  APFloat::rmNearestTiesToEven);
1880       return getConstantFP(apf, VT);
1881     }
1882     case ISD::BIT_CONVERT:
1883       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
1884         return getConstantFP(Val.bitsToFloat(), VT);
1885       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
1886         return getConstantFP(Val.bitsToDouble(), VT);
1887       break;
1888     case ISD::BSWAP:
1889       return getConstant(Val.byteSwap(), VT);
1890     case ISD::CTPOP:
1891       return getConstant(Val.countPopulation(), VT);
1892     case ISD::CTLZ:
1893       return getConstant(Val.countLeadingZeros(), VT);
1894     case ISD::CTTZ:
1895       return getConstant(Val.countTrailingZeros(), VT);
1896     }
1897   }
1898
1899   // Constant fold unary operations with a floating point constant operand.
1900   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) {
1901     APFloat V = C->getValueAPF();    // make copy
1902     if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
1903       switch (Opcode) {
1904       case ISD::FNEG:
1905         V.changeSign();
1906         return getConstantFP(V, VT);
1907       case ISD::FABS:
1908         V.clearSign();
1909         return getConstantFP(V, VT);
1910       case ISD::FP_ROUND:
1911       case ISD::FP_EXTEND:
1912         // This can return overflow, underflow, or inexact; we don't care.
1913         // FIXME need to be more flexible about rounding mode.
1914         (void)V.convert(*MVTToAPFloatSemantics(VT),
1915                         APFloat::rmNearestTiesToEven);
1916         return getConstantFP(V, VT);
1917       case ISD::FP_TO_SINT:
1918       case ISD::FP_TO_UINT: {
1919         integerPart x;
1920         assert(integerPartWidth >= 64);
1921         // FIXME need to be more flexible about rounding mode.
1922         APFloat::opStatus s = V.convertToInteger(&x, 64U,
1923                               Opcode==ISD::FP_TO_SINT,
1924                               APFloat::rmTowardZero);
1925         if (s==APFloat::opInvalidOp)     // inexact is OK, in fact usual
1926           break;
1927         return getConstant(x, VT);
1928       }
1929       case ISD::BIT_CONVERT:
1930         if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
1931           return getConstant((uint32_t)V.convertToAPInt().getZExtValue(), VT);
1932         else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
1933           return getConstant(V.convertToAPInt().getZExtValue(), VT);
1934         break;
1935       }
1936     }
1937   }
1938
1939   unsigned OpOpcode = Operand.Val->getOpcode();
1940   switch (Opcode) {
1941   case ISD::TokenFactor:
1942   case ISD::MERGE_VALUES:
1943     return Operand;         // Factor or merge of one node?  No need.
1944   case ISD::FP_ROUND: assert(0 && "Invalid method to make FP_ROUND node");
1945   case ISD::FP_EXTEND:
1946     assert(MVT::isFloatingPoint(VT) &&
1947            MVT::isFloatingPoint(Operand.getValueType()) && "Invalid FP cast!");
1948     if (Operand.getValueType() == VT) return Operand;  // noop conversion.
1949     if (Operand.getOpcode() == ISD::UNDEF)
1950       return getNode(ISD::UNDEF, VT);
1951     break;
1952   case ISD::SIGN_EXTEND:
1953     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1954            "Invalid SIGN_EXTEND!");
1955     if (Operand.getValueType() == VT) return Operand;   // noop extension
1956     assert(MVT::getSizeInBits(Operand.getValueType()) < MVT::getSizeInBits(VT)
1957            && "Invalid sext node, dst < src!");
1958     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
1959       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1960     break;
1961   case ISD::ZERO_EXTEND:
1962     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1963            "Invalid ZERO_EXTEND!");
1964     if (Operand.getValueType() == VT) return Operand;   // noop extension
1965     assert(MVT::getSizeInBits(Operand.getValueType()) < MVT::getSizeInBits(VT)
1966            && "Invalid zext node, dst < src!");
1967     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
1968       return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
1969     break;
1970   case ISD::ANY_EXTEND:
1971     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1972            "Invalid ANY_EXTEND!");
1973     if (Operand.getValueType() == VT) return Operand;   // noop extension
1974     assert(MVT::getSizeInBits(Operand.getValueType()) < MVT::getSizeInBits(VT)
1975            && "Invalid anyext node, dst < src!");
1976     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND)
1977       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
1978       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1979     break;
1980   case ISD::TRUNCATE:
1981     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1982            "Invalid TRUNCATE!");
1983     if (Operand.getValueType() == VT) return Operand;   // noop truncate
1984     assert(MVT::getSizeInBits(Operand.getValueType()) > MVT::getSizeInBits(VT)
1985            && "Invalid truncate node, src < dst!");
1986     if (OpOpcode == ISD::TRUNCATE)
1987       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1988     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
1989              OpOpcode == ISD::ANY_EXTEND) {
1990       // If the source is smaller than the dest, we still need an extend.
1991       if (MVT::getSizeInBits(Operand.Val->getOperand(0).getValueType())
1992           < MVT::getSizeInBits(VT))
1993         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1994       else if (MVT::getSizeInBits(Operand.Val->getOperand(0).getValueType())
1995                > MVT::getSizeInBits(VT))
1996         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1997       else
1998         return Operand.Val->getOperand(0);
1999     }
2000     break;
2001   case ISD::BIT_CONVERT:
2002     // Basic sanity checking.
2003     assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType())
2004            && "Cannot BIT_CONVERT between types of different sizes!");
2005     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
2006     if (OpOpcode == ISD::BIT_CONVERT)  // bitconv(bitconv(x)) -> bitconv(x)
2007       return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0));
2008     if (OpOpcode == ISD::UNDEF)
2009       return getNode(ISD::UNDEF, VT);
2010     break;
2011   case ISD::SCALAR_TO_VECTOR:
2012     assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) &&
2013            MVT::getVectorElementType(VT) == Operand.getValueType() &&
2014            "Illegal SCALAR_TO_VECTOR node!");
2015     if (OpOpcode == ISD::UNDEF)
2016       return getNode(ISD::UNDEF, VT);
2017     // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
2018     if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
2019         isa<ConstantSDNode>(Operand.getOperand(1)) &&
2020         Operand.getConstantOperandVal(1) == 0 &&
2021         Operand.getOperand(0).getValueType() == VT)
2022       return Operand.getOperand(0);
2023     break;
2024   case ISD::FNEG:
2025     if (OpOpcode == ISD::FSUB)   // -(X-Y) -> (Y-X)
2026       return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1),
2027                      Operand.Val->getOperand(0));
2028     if (OpOpcode == ISD::FNEG)  // --X -> X
2029       return Operand.Val->getOperand(0);
2030     break;
2031   case ISD::FABS:
2032     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
2033       return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
2034     break;
2035   }
2036
2037   SDNode *N;
2038   SDVTList VTs = getVTList(VT);
2039   if (VT != MVT::Flag) { // Don't CSE flag producing nodes
2040     FoldingSetNodeID ID;
2041     SDOperand Ops[1] = { Operand };
2042     AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
2043     void *IP = 0;
2044     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2045       return SDOperand(E, 0);
2046     N = new UnarySDNode(Opcode, VTs, Operand);
2047     CSEMap.InsertNode(N, IP);
2048   } else {
2049     N = new UnarySDNode(Opcode, VTs, Operand);
2050   }
2051   AllNodes.push_back(N);
2052   return SDOperand(N, 0);
2053 }
2054
2055
2056
2057 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2058                                 SDOperand N1, SDOperand N2) {
2059   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
2060   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
2061   switch (Opcode) {
2062   default: break;
2063   case ISD::TokenFactor:
2064     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
2065            N2.getValueType() == MVT::Other && "Invalid token factor!");
2066     // Fold trivial token factors.
2067     if (N1.getOpcode() == ISD::EntryToken) return N2;
2068     if (N2.getOpcode() == ISD::EntryToken) return N1;
2069     break;
2070   case ISD::AND:
2071     assert(MVT::isInteger(VT) && N1.getValueType() == N2.getValueType() &&
2072            N1.getValueType() == VT && "Binary operator types must match!");
2073     // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
2074     // worth handling here.
2075     if (N2C && N2C->isNullValue())
2076       return N2;
2077     if (N2C && N2C->isAllOnesValue())  // X & -1 -> X
2078       return N1;
2079     break;
2080   case ISD::OR:
2081   case ISD::XOR:
2082     assert(MVT::isInteger(VT) && N1.getValueType() == N2.getValueType() &&
2083            N1.getValueType() == VT && "Binary operator types must match!");
2084     // (X ^| 0) -> X.  This commonly occurs when legalizing i64 values, so it's
2085     // worth handling here.
2086     if (N2C && N2C->isNullValue())
2087       return N1;
2088     break;
2089   case ISD::UDIV:
2090   case ISD::UREM:
2091   case ISD::MULHU:
2092   case ISD::MULHS:
2093     assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
2094     // fall through
2095   case ISD::ADD:
2096   case ISD::SUB:
2097   case ISD::MUL:
2098   case ISD::SDIV:
2099   case ISD::SREM:
2100   case ISD::FADD:
2101   case ISD::FSUB:
2102   case ISD::FMUL:
2103   case ISD::FDIV:
2104   case ISD::FREM:
2105     assert(N1.getValueType() == N2.getValueType() &&
2106            N1.getValueType() == VT && "Binary operator types must match!");
2107     break;
2108   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
2109     assert(N1.getValueType() == VT &&
2110            MVT::isFloatingPoint(N1.getValueType()) &&
2111            MVT::isFloatingPoint(N2.getValueType()) &&
2112            "Invalid FCOPYSIGN!");
2113     break;
2114   case ISD::SHL:
2115   case ISD::SRA:
2116   case ISD::SRL:
2117   case ISD::ROTL:
2118   case ISD::ROTR:
2119     assert(VT == N1.getValueType() &&
2120            "Shift operators return type must be the same as their first arg");
2121     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
2122            VT != MVT::i1 && "Shifts only work on integers");
2123     break;
2124   case ISD::FP_ROUND_INREG: {
2125     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
2126     assert(VT == N1.getValueType() && "Not an inreg round!");
2127     assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
2128            "Cannot FP_ROUND_INREG integer types");
2129     assert(MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(VT) &&
2130            "Not rounding down!");
2131     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
2132     break;
2133   }
2134   case ISD::FP_ROUND:
2135     assert(MVT::isFloatingPoint(VT) &&
2136            MVT::isFloatingPoint(N1.getValueType()) &&
2137            MVT::getSizeInBits(VT) <= MVT::getSizeInBits(N1.getValueType()) &&
2138            isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2139     if (N1.getValueType() == VT) return N1;  // noop conversion.
2140     break;
2141   case ISD::AssertSext:
2142   case ISD::AssertZext: {
2143     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
2144     assert(VT == N1.getValueType() && "Not an inreg extend!");
2145     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
2146            "Cannot *_EXTEND_INREG FP types");
2147     assert(MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(VT) &&
2148            "Not extending!");
2149     if (VT == EVT) return N1; // noop assertion.
2150     break;
2151   }
2152   case ISD::SIGN_EXTEND_INREG: {
2153     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
2154     assert(VT == N1.getValueType() && "Not an inreg extend!");
2155     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
2156            "Cannot *_EXTEND_INREG FP types");
2157     assert(MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(VT) &&
2158            "Not extending!");
2159     if (EVT == VT) return N1;  // Not actually extending
2160
2161     if (N1C) {
2162       APInt Val = N1C->getAPIntValue();
2163       unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT());
2164       Val <<= Val.getBitWidth()-FromBits;
2165       Val = Val.ashr(Val.getBitWidth()-FromBits);
2166       return getConstant(Val, VT);
2167     }
2168     break;
2169   }
2170   case ISD::EXTRACT_VECTOR_ELT:
2171     assert(N2C && "Bad EXTRACT_VECTOR_ELT!");
2172
2173     // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2174     if (N1.getOpcode() == ISD::UNDEF)
2175       return getNode(ISD::UNDEF, VT);
2176
2177     // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2178     // expanding copies of large vectors from registers.
2179     if (N1.getOpcode() == ISD::CONCAT_VECTORS &&
2180         N1.getNumOperands() > 0) {
2181       unsigned Factor =
2182         MVT::getVectorNumElements(N1.getOperand(0).getValueType());
2183       return getNode(ISD::EXTRACT_VECTOR_ELT, VT,
2184                      N1.getOperand(N2C->getValue() / Factor),
2185                      getConstant(N2C->getValue() % Factor, N2.getValueType()));
2186     }
2187
2188     // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2189     // expanding large vector constants.
2190     if (N1.getOpcode() == ISD::BUILD_VECTOR)
2191       return N1.getOperand(N2C->getValue());
2192
2193     // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2194     // operations are lowered to scalars.
2195     if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT)
2196       if (ConstantSDNode *IEC = dyn_cast<ConstantSDNode>(N1.getOperand(2))) {
2197         if (IEC == N2C)
2198           return N1.getOperand(1);
2199         else
2200           return getNode(ISD::EXTRACT_VECTOR_ELT, VT, N1.getOperand(0), N2);
2201       }
2202     break;
2203   case ISD::EXTRACT_ELEMENT:
2204     assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!");
2205     assert(!MVT::isVector(N1.getValueType()) &&
2206            MVT::isInteger(N1.getValueType()) &&
2207            !MVT::isVector(VT) && MVT::isInteger(VT) &&
2208            "EXTRACT_ELEMENT only applies to integers!");
2209
2210     // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2211     // 64-bit integers into 32-bit parts.  Instead of building the extract of
2212     // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2213     if (N1.getOpcode() == ISD::BUILD_PAIR)
2214       return N1.getOperand(N2C->getValue());
2215
2216     // EXTRACT_ELEMENT of a constant int is also very common.
2217     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2218       unsigned ElementSize = MVT::getSizeInBits(VT);
2219       unsigned Shift = ElementSize * N2C->getValue();
2220       APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2221       return getConstant(ShiftedVal.trunc(ElementSize), VT);
2222     }
2223     break;
2224   case ISD::EXTRACT_SUBVECTOR:
2225     if (N1.getValueType() == VT) // Trivial extraction.
2226       return N1;
2227     break;
2228   }
2229
2230   if (N1C) {
2231     if (N2C) {
2232       APInt C1 = N1C->getAPIntValue(), C2 = N2C->getAPIntValue();
2233       switch (Opcode) {
2234       case ISD::ADD: return getConstant(C1 + C2, VT);
2235       case ISD::SUB: return getConstant(C1 - C2, VT);
2236       case ISD::MUL: return getConstant(C1 * C2, VT);
2237       case ISD::UDIV:
2238         if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2239         break;
2240       case ISD::UREM :
2241         if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2242         break;
2243       case ISD::SDIV :
2244         if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2245         break;
2246       case ISD::SREM :
2247         if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2248         break;
2249       case ISD::AND  : return getConstant(C1 & C2, VT);
2250       case ISD::OR   : return getConstant(C1 | C2, VT);
2251       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
2252       case ISD::SHL  : return getConstant(C1 << C2, VT);
2253       case ISD::SRL  : return getConstant(C1.lshr(C2), VT);
2254       case ISD::SRA  : return getConstant(C1.ashr(C2), VT);
2255       case ISD::ROTL : return getConstant(C1.rotl(C2), VT);
2256       case ISD::ROTR : return getConstant(C1.rotr(C2), VT);
2257       default: break;
2258       }
2259     } else {      // Cannonicalize constant to RHS if commutative
2260       if (isCommutativeBinOp(Opcode)) {
2261         std::swap(N1C, N2C);
2262         std::swap(N1, N2);
2263       }
2264     }
2265   }
2266
2267   // Constant fold FP operations.
2268   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
2269   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
2270   if (N1CFP) {
2271     if (!N2CFP && isCommutativeBinOp(Opcode)) {
2272       // Cannonicalize constant to RHS if commutative
2273       std::swap(N1CFP, N2CFP);
2274       std::swap(N1, N2);
2275     } else if (N2CFP && VT != MVT::ppcf128) {
2276       APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
2277       APFloat::opStatus s;
2278       switch (Opcode) {
2279       case ISD::FADD:
2280         s = V1.add(V2, APFloat::rmNearestTiesToEven);
2281         if (s != APFloat::opInvalidOp)
2282           return getConstantFP(V1, VT);
2283         break;
2284       case ISD::FSUB:
2285         s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
2286         if (s!=APFloat::opInvalidOp)
2287           return getConstantFP(V1, VT);
2288         break;
2289       case ISD::FMUL:
2290         s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
2291         if (s!=APFloat::opInvalidOp)
2292           return getConstantFP(V1, VT);
2293         break;
2294       case ISD::FDIV:
2295         s = V1.divide(V2, APFloat::rmNearestTiesToEven);
2296         if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
2297           return getConstantFP(V1, VT);
2298         break;
2299       case ISD::FREM :
2300         s = V1.mod(V2, APFloat::rmNearestTiesToEven);
2301         if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
2302           return getConstantFP(V1, VT);
2303         break;
2304       case ISD::FCOPYSIGN:
2305         V1.copySign(V2);
2306         return getConstantFP(V1, VT);
2307       default: break;
2308       }
2309     }
2310   }
2311
2312   // Canonicalize an UNDEF to the RHS, even over a constant.
2313   if (N1.getOpcode() == ISD::UNDEF) {
2314     if (isCommutativeBinOp(Opcode)) {
2315       std::swap(N1, N2);
2316     } else {
2317       switch (Opcode) {
2318       case ISD::FP_ROUND_INREG:
2319       case ISD::SIGN_EXTEND_INREG:
2320       case ISD::SUB:
2321       case ISD::FSUB:
2322       case ISD::FDIV:
2323       case ISD::FREM:
2324       case ISD::SRA:
2325         return N1;     // fold op(undef, arg2) -> undef
2326       case ISD::UDIV:
2327       case ISD::SDIV:
2328       case ISD::UREM:
2329       case ISD::SREM:
2330       case ISD::SRL:
2331       case ISD::SHL:
2332         if (!MVT::isVector(VT))
2333           return getConstant(0, VT);    // fold op(undef, arg2) -> 0
2334         // For vectors, we can't easily build an all zero vector, just return
2335         // the LHS.
2336         return N2;
2337       }
2338     }
2339   }
2340
2341   // Fold a bunch of operators when the RHS is undef.
2342   if (N2.getOpcode() == ISD::UNDEF) {
2343     switch (Opcode) {
2344     case ISD::XOR:
2345       if (N1.getOpcode() == ISD::UNDEF)
2346         // Handle undef ^ undef -> 0 special case. This is a common
2347         // idiom (misuse).
2348         return getConstant(0, VT);
2349       // fallthrough
2350     case ISD::ADD:
2351     case ISD::ADDC:
2352     case ISD::ADDE:
2353     case ISD::SUB:
2354     case ISD::FADD:
2355     case ISD::FSUB:
2356     case ISD::FMUL:
2357     case ISD::FDIV:
2358     case ISD::FREM:
2359     case ISD::UDIV:
2360     case ISD::SDIV:
2361     case ISD::UREM:
2362     case ISD::SREM:
2363       return N2;       // fold op(arg1, undef) -> undef
2364     case ISD::MUL:
2365     case ISD::AND:
2366     case ISD::SRL:
2367     case ISD::SHL:
2368       if (!MVT::isVector(VT))
2369         return getConstant(0, VT);  // fold op(arg1, undef) -> 0
2370       // For vectors, we can't easily build an all zero vector, just return
2371       // the LHS.
2372       return N1;
2373     case ISD::OR:
2374       if (!MVT::isVector(VT))
2375         return getConstant(MVT::getIntVTBitMask(VT), VT);
2376       // For vectors, we can't easily build an all one vector, just return
2377       // the LHS.
2378       return N1;
2379     case ISD::SRA:
2380       return N1;
2381     }
2382   }
2383
2384   // Memoize this node if possible.
2385   SDNode *N;
2386   SDVTList VTs = getVTList(VT);
2387   if (VT != MVT::Flag) {
2388     SDOperand Ops[] = { N1, N2 };
2389     FoldingSetNodeID ID;
2390     AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
2391     void *IP = 0;
2392     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2393       return SDOperand(E, 0);
2394     N = new BinarySDNode(Opcode, VTs, N1, N2);
2395     CSEMap.InsertNode(N, IP);
2396   } else {
2397     N = new BinarySDNode(Opcode, VTs, N1, N2);
2398   }
2399
2400   AllNodes.push_back(N);
2401   return SDOperand(N, 0);
2402 }
2403
2404 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2405                                 SDOperand N1, SDOperand N2, SDOperand N3) {
2406   // Perform various simplifications.
2407   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
2408   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
2409   switch (Opcode) {
2410   case ISD::SETCC: {
2411     // Use FoldSetCC to simplify SETCC's.
2412     SDOperand Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
2413     if (Simp.Val) return Simp;
2414     break;
2415   }
2416   case ISD::SELECT:
2417     if (N1C) {
2418      if (N1C->getValue())
2419         return N2;             // select true, X, Y -> X
2420       else
2421         return N3;             // select false, X, Y -> Y
2422     }
2423
2424     if (N2 == N3) return N2;   // select C, X, X -> X
2425     break;
2426   case ISD::BRCOND:
2427     if (N2C) {
2428       if (N2C->getValue()) // Unconditional branch
2429         return getNode(ISD::BR, MVT::Other, N1, N3);
2430       else
2431         return N1;         // Never-taken branch
2432     }
2433     break;
2434   case ISD::VECTOR_SHUFFLE:
2435     assert(VT == N1.getValueType() && VT == N2.getValueType() &&
2436            MVT::isVector(VT) && MVT::isVector(N3.getValueType()) &&
2437            N3.getOpcode() == ISD::BUILD_VECTOR &&
2438            MVT::getVectorNumElements(VT) == N3.getNumOperands() &&
2439            "Illegal VECTOR_SHUFFLE node!");
2440     break;
2441   case ISD::BIT_CONVERT:
2442     // Fold bit_convert nodes from a type to themselves.
2443     if (N1.getValueType() == VT)
2444       return N1;
2445     break;
2446   }
2447
2448   // Memoize node if it doesn't produce a flag.
2449   SDNode *N;
2450   SDVTList VTs = getVTList(VT);
2451   if (VT != MVT::Flag) {
2452     SDOperand Ops[] = { N1, N2, N3 };
2453     FoldingSetNodeID ID;
2454     AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
2455     void *IP = 0;
2456     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2457       return SDOperand(E, 0);
2458     N = new TernarySDNode(Opcode, VTs, N1, N2, N3);
2459     CSEMap.InsertNode(N, IP);
2460   } else {
2461     N = new TernarySDNode(Opcode, VTs, N1, N2, N3);
2462   }
2463   AllNodes.push_back(N);
2464   return SDOperand(N, 0);
2465 }
2466
2467 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2468                                 SDOperand N1, SDOperand N2, SDOperand N3,
2469                                 SDOperand N4) {
2470   SDOperand Ops[] = { N1, N2, N3, N4 };
2471   return getNode(Opcode, VT, Ops, 4);
2472 }
2473
2474 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2475                                 SDOperand N1, SDOperand N2, SDOperand N3,
2476                                 SDOperand N4, SDOperand N5) {
2477   SDOperand Ops[] = { N1, N2, N3, N4, N5 };
2478   return getNode(Opcode, VT, Ops, 5);
2479 }
2480
2481 /// getMemsetValue - Vectorized representation of the memset value
2482 /// operand.
2483 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
2484                                 SelectionDAG &DAG) {
2485   MVT::ValueType CurVT = VT;
2486   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
2487     uint64_t Val   = C->getValue() & 255;
2488     unsigned Shift = 8;
2489     while (CurVT != MVT::i8) {
2490       Val = (Val << Shift) | Val;
2491       Shift <<= 1;
2492       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
2493     }
2494     return DAG.getConstant(Val, VT);
2495   } else {
2496     Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
2497     unsigned Shift = 8;
2498     while (CurVT != MVT::i8) {
2499       Value =
2500         DAG.getNode(ISD::OR, VT,
2501                     DAG.getNode(ISD::SHL, VT, Value,
2502                                 DAG.getConstant(Shift, MVT::i8)), Value);
2503       Shift <<= 1;
2504       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
2505     }
2506
2507     return Value;
2508   }
2509 }
2510
2511 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
2512 /// used when a memcpy is turned into a memset when the source is a constant
2513 /// string ptr.
2514 static SDOperand getMemsetStringVal(MVT::ValueType VT,
2515                                     SelectionDAG &DAG,
2516                                     const TargetLowering &TLI,
2517                                     std::string &Str, unsigned Offset) {
2518   uint64_t Val = 0;
2519   unsigned MSB = MVT::getSizeInBits(VT) / 8;
2520   if (TLI.isLittleEndian())
2521     Offset = Offset + MSB - 1;
2522   for (unsigned i = 0; i != MSB; ++i) {
2523     Val = (Val << 8) | (unsigned char)Str[Offset];
2524     Offset += TLI.isLittleEndian() ? -1 : 1;
2525   }
2526   return DAG.getConstant(Val, VT);
2527 }
2528
2529 /// getMemBasePlusOffset - Returns base and offset node for the
2530 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
2531                                       SelectionDAG &DAG) {
2532   MVT::ValueType VT = Base.getValueType();
2533   return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
2534 }
2535
2536 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
2537 /// to replace the memset / memcpy is below the threshold. It also returns the
2538 /// types of the sequence of memory ops to perform memset / memcpy.
2539 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
2540                                      unsigned Limit, uint64_t Size,
2541                                      unsigned Align,
2542                                      const TargetLowering &TLI) {
2543   MVT::ValueType VT;
2544
2545   if (TLI.allowsUnalignedMemoryAccesses()) {
2546     VT = MVT::i64;
2547   } else {
2548     switch (Align & 7) {
2549     case 0:
2550       VT = MVT::i64;
2551       break;
2552     case 4:
2553       VT = MVT::i32;
2554       break;
2555     case 2:
2556       VT = MVT::i16;
2557       break;
2558     default:
2559       VT = MVT::i8;
2560       break;
2561     }
2562   }
2563
2564   MVT::ValueType LVT = MVT::i64;
2565   while (!TLI.isTypeLegal(LVT))
2566     LVT = (MVT::ValueType)((unsigned)LVT - 1);
2567   assert(MVT::isInteger(LVT));
2568
2569   if (VT > LVT)
2570     VT = LVT;
2571
2572   unsigned NumMemOps = 0;
2573   while (Size != 0) {
2574     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
2575     while (VTSize > Size) {
2576       VT = (MVT::ValueType)((unsigned)VT - 1);
2577       VTSize >>= 1;
2578     }
2579     assert(MVT::isInteger(VT));
2580
2581     if (++NumMemOps > Limit)
2582       return false;
2583     MemOps.push_back(VT);
2584     Size -= VTSize;
2585   }
2586
2587   return true;
2588 }
2589
2590 static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG,
2591                                          SDOperand Chain, SDOperand Dst,
2592                                          SDOperand Src, uint64_t Size,
2593                                          unsigned Align,
2594                                          bool AlwaysInline,
2595                                          const Value *DstSV, uint64_t DstSVOff,
2596                                          const Value *SrcSV, uint64_t SrcSVOff){
2597   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2598
2599   // Expand memcpy to a series of store ops if the size operand falls below
2600   // a certain threshold.
2601   std::vector<MVT::ValueType> MemOps;
2602   uint64_t Limit = -1;
2603   if (!AlwaysInline)
2604     Limit = TLI.getMaxStoresPerMemcpy();
2605   if (!MeetsMaxMemopRequirement(MemOps, Limit, Size, Align, TLI))
2606     return SDOperand();
2607
2608   SmallVector<SDOperand, 8> OutChains;
2609
2610   unsigned NumMemOps = MemOps.size();
2611   unsigned SrcDelta = 0;
2612   GlobalAddressSDNode *G = NULL;
2613   std::string Str;
2614   bool CopyFromStr = false;
2615   uint64_t SrcOff = 0, DstOff = 0;
2616
2617   if (Src.getOpcode() == ISD::GlobalAddress)
2618     G = cast<GlobalAddressSDNode>(Src);
2619   else if (Src.getOpcode() == ISD::ADD &&
2620            Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
2621            Src.getOperand(1).getOpcode() == ISD::Constant) {
2622     G = cast<GlobalAddressSDNode>(Src.getOperand(0));
2623     SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getValue();
2624   }
2625   if (G) {
2626     GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
2627     if (GV && GV->isConstant()) {
2628       Str = GV->getStringValue(false);
2629       if (!Str.empty()) {
2630         CopyFromStr = true;
2631         SrcOff += SrcDelta;
2632       }
2633     }
2634   }
2635
2636   for (unsigned i = 0; i < NumMemOps; i++) {
2637     MVT::ValueType VT = MemOps[i];
2638     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
2639     SDOperand Value, Store;
2640
2641     if (CopyFromStr) {
2642       Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
2643       Store =
2644         DAG.getStore(Chain, Value,
2645                      getMemBasePlusOffset(Dst, DstOff, DAG),
2646                      DstSV, DstSVOff + DstOff);
2647     } else {
2648       Value = DAG.getLoad(VT, Chain,
2649                           getMemBasePlusOffset(Src, SrcOff, DAG),
2650                           SrcSV, SrcSVOff + SrcOff, false, Align);
2651       Store =
2652         DAG.getStore(Chain, Value,
2653                      getMemBasePlusOffset(Dst, DstOff, DAG),
2654                      DstSV, DstSVOff + DstOff, false, Align);
2655     }
2656     OutChains.push_back(Store);
2657     SrcOff += VTSize;
2658     DstOff += VTSize;
2659   }
2660
2661   return DAG.getNode(ISD::TokenFactor, MVT::Other,
2662                      &OutChains[0], OutChains.size());
2663 }
2664
2665 static SDOperand getMemsetStores(SelectionDAG &DAG,
2666                                  SDOperand Chain, SDOperand Dst,
2667                                  SDOperand Src, uint64_t Size,
2668                                  unsigned Align,
2669                                  const Value *DstSV, uint64_t DstSVOff) {
2670   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2671
2672   // Expand memset to a series of load/store ops if the size operand
2673   // falls below a certain threshold.
2674   std::vector<MVT::ValueType> MemOps;
2675   if (!MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
2676                                 Size, Align, TLI))
2677     return SDOperand();
2678
2679   SmallVector<SDOperand, 8> OutChains;
2680   uint64_t DstOff = 0;
2681
2682   unsigned NumMemOps = MemOps.size();
2683   for (unsigned i = 0; i < NumMemOps; i++) {
2684     MVT::ValueType VT = MemOps[i];
2685     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
2686     SDOperand Value = getMemsetValue(Src, VT, DAG);
2687     SDOperand Store = DAG.getStore(Chain, Value,
2688                                    getMemBasePlusOffset(Dst, DstOff, DAG),
2689                                    DstSV, DstSVOff + DstOff);
2690     OutChains.push_back(Store);
2691     DstOff += VTSize;
2692   }
2693
2694   return DAG.getNode(ISD::TokenFactor, MVT::Other,
2695                      &OutChains[0], OutChains.size());
2696 }
2697
2698 SDOperand SelectionDAG::getMemcpy(SDOperand Chain, SDOperand Dst,
2699                                   SDOperand Src, SDOperand Size,
2700                                   unsigned Align, bool AlwaysInline,
2701                                   const Value *DstSV, uint64_t DstSVOff,
2702                                   const Value *SrcSV, uint64_t SrcSVOff) {
2703
2704   // Check to see if we should lower the memcpy to loads and stores first.
2705   // For cases within the target-specified limits, this is the best choice.
2706   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
2707   if (ConstantSize) {
2708     // Memcpy with size zero? Just return the original chain.
2709     if (ConstantSize->isNullValue())
2710       return Chain;
2711
2712     SDOperand Result =
2713       getMemcpyLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(),
2714                               Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff);
2715     if (Result.Val)
2716       return Result;
2717   }
2718
2719   // Then check to see if we should lower the memcpy with target-specific
2720   // code. If the target chooses to do this, this is the next best.
2721   SDOperand Result =
2722     TLI.EmitTargetCodeForMemcpy(*this, Chain, Dst, Src, Size, Align,
2723                                 AlwaysInline,
2724                                 DstSV, DstSVOff, SrcSV, SrcSVOff);
2725   if (Result.Val)
2726     return Result;
2727
2728   // If we really need inline code and the target declined to provide it,
2729   // use a (potentially long) sequence of loads and stores.
2730   if (AlwaysInline) {
2731     assert(ConstantSize && "AlwaysInline requires a constant size!");
2732     return getMemcpyLoadsAndStores(*this, Chain, Dst, Src,
2733                                    ConstantSize->getValue(), Align, true,
2734                                    DstSV, DstSVOff, SrcSV, SrcSVOff);
2735   }
2736
2737   // Emit a library call.
2738   TargetLowering::ArgListTy Args;
2739   TargetLowering::ArgListEntry Entry;
2740   Entry.Ty = TLI.getTargetData()->getIntPtrType();
2741   Entry.Node = Dst; Args.push_back(Entry);
2742   Entry.Node = Src; Args.push_back(Entry);
2743   Entry.Node = Size; Args.push_back(Entry);
2744   std::pair<SDOperand,SDOperand> CallResult =
2745     TLI.LowerCallTo(Chain, Type::VoidTy,
2746                     false, false, false, CallingConv::C, false,
2747                     getExternalSymbol("memcpy", TLI.getPointerTy()),
2748                     Args, *this);
2749   return CallResult.second;
2750 }
2751
2752 SDOperand SelectionDAG::getMemmove(SDOperand Chain, SDOperand Dst,
2753                                    SDOperand Src, SDOperand Size,
2754                                    unsigned Align,
2755                                    const Value *DstSV, uint64_t DstSVOff,
2756                                    const Value *SrcSV, uint64_t SrcSVOff) {
2757
2758   // TODO: Optimize small memmove cases with simple loads and stores,
2759   // ensuring that all loads precede all stores. This can cause severe
2760   // register pressure, so targets should be careful with the size limit.
2761
2762   // Then check to see if we should lower the memmove with target-specific
2763   // code. If the target chooses to do this, this is the next best.
2764   SDOperand Result =
2765     TLI.EmitTargetCodeForMemmove(*this, Chain, Dst, Src, Size, Align,
2766                                  DstSV, DstSVOff, SrcSV, SrcSVOff);
2767   if (Result.Val)
2768     return Result;
2769
2770   // Emit a library call.
2771   TargetLowering::ArgListTy Args;
2772   TargetLowering::ArgListEntry Entry;
2773   Entry.Ty = TLI.getTargetData()->getIntPtrType();
2774   Entry.Node = Dst; Args.push_back(Entry);
2775   Entry.Node = Src; Args.push_back(Entry);
2776   Entry.Node = Size; Args.push_back(Entry);
2777   std::pair<SDOperand,SDOperand> CallResult =
2778     TLI.LowerCallTo(Chain, Type::VoidTy,
2779                     false, false, false, CallingConv::C, false,
2780                     getExternalSymbol("memmove", TLI.getPointerTy()),
2781                     Args, *this);
2782   return CallResult.second;
2783 }
2784
2785 SDOperand SelectionDAG::getMemset(SDOperand Chain, SDOperand Dst,
2786                                   SDOperand Src, SDOperand Size,
2787                                   unsigned Align,
2788                                   const Value *DstSV, uint64_t DstSVOff) {
2789
2790   // Check to see if we should lower the memset to stores first.
2791   // For cases within the target-specified limits, this is the best choice.
2792   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
2793   if (ConstantSize) {
2794     // Memset with size zero? Just return the original chain.
2795     if (ConstantSize->isNullValue())
2796       return Chain;
2797
2798     SDOperand Result =
2799       getMemsetStores(*this, Chain, Dst, Src, ConstantSize->getValue(), Align,
2800                       DstSV, DstSVOff);
2801     if (Result.Val)
2802       return Result;
2803   }
2804
2805   // Then check to see if we should lower the memset with target-specific
2806   // code. If the target chooses to do this, this is the next best.
2807   SDOperand Result =
2808     TLI.EmitTargetCodeForMemset(*this, Chain, Dst, Src, Size, Align,
2809                                 DstSV, DstSVOff);
2810   if (Result.Val)
2811     return Result;
2812
2813   // Emit a library call.
2814   const Type *IntPtrTy = TLI.getTargetData()->getIntPtrType();
2815   TargetLowering::ArgListTy Args;
2816   TargetLowering::ArgListEntry Entry;
2817   Entry.Node = Dst; Entry.Ty = IntPtrTy;
2818   Args.push_back(Entry);
2819   // Extend or truncate the argument to be an i32 value for the call.
2820   if (Src.getValueType() > MVT::i32)
2821     Src = getNode(ISD::TRUNCATE, MVT::i32, Src);
2822   else
2823     Src = getNode(ISD::ZERO_EXTEND, MVT::i32, Src);
2824   Entry.Node = Src; Entry.Ty = Type::Int32Ty; Entry.isSExt = true;
2825   Args.push_back(Entry);
2826   Entry.Node = Size; Entry.Ty = IntPtrTy; Entry.isSExt = false;
2827   Args.push_back(Entry);
2828   std::pair<SDOperand,SDOperand> CallResult =
2829     TLI.LowerCallTo(Chain, Type::VoidTy,
2830                     false, false, false, CallingConv::C, false,
2831                     getExternalSymbol("memset", TLI.getPointerTy()),
2832                     Args, *this);
2833   return CallResult.second;
2834 }
2835
2836 SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain,
2837                                   SDOperand Ptr, SDOperand Cmp,
2838                                   SDOperand Swp, MVT::ValueType VT) {
2839   assert(Opcode == ISD::ATOMIC_LCS && "Invalid Atomic Op");
2840   assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
2841   SDVTList VTs = getVTList(Cmp.getValueType(), MVT::Other);
2842   FoldingSetNodeID ID;
2843   SDOperand Ops[] = {Chain, Ptr, Cmp, Swp};
2844   AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
2845   ID.AddInteger((unsigned int)VT);
2846   void* IP = 0;
2847   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2848     return SDOperand(E, 0);
2849   SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, VT);
2850   CSEMap.InsertNode(N, IP);
2851   AllNodes.push_back(N);
2852   return SDOperand(N, 0);
2853 }
2854
2855 SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain,
2856                                   SDOperand Ptr, SDOperand Val,
2857                                   MVT::ValueType VT) {
2858   assert((   Opcode == ISD::ATOMIC_LAS || Opcode == ISD::ATOMIC_LSS
2859           || Opcode == ISD::ATOMIC_SWAP || Opcode == ISD::ATOMIC_LOAD_AND
2860           || Opcode == ISD::ATOMIC_LOAD_OR || Opcode == ISD::ATOMIC_LOAD_XOR
2861           || Opcode == ISD::ATOMIC_LOAD_MIN || Opcode == ISD::ATOMIC_LOAD_MAX
2862           || Opcode == ISD::ATOMIC_LOAD_UMIN || Opcode == ISD::ATOMIC_LOAD_UMAX)
2863          && "Invalid Atomic Op");
2864   SDVTList VTs = getVTList(Val.getValueType(), MVT::Other);
2865   FoldingSetNodeID ID;
2866   SDOperand Ops[] = {Chain, Ptr, Val};
2867   AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
2868   ID.AddInteger((unsigned int)VT);
2869   void* IP = 0;
2870   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2871     return SDOperand(E, 0);
2872   SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, VT);
2873   CSEMap.InsertNode(N, IP);
2874   AllNodes.push_back(N);
2875   return SDOperand(N, 0);
2876 }
2877
2878 SDOperand
2879 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
2880                       MVT::ValueType VT, SDOperand Chain,
2881                       SDOperand Ptr, SDOperand Offset,
2882                       const Value *SV, int SVOffset, MVT::ValueType EVT,
2883                       bool isVolatile, unsigned Alignment) {
2884   if (Alignment == 0) { // Ensure that codegen never sees alignment 0
2885     const Type *Ty = 0;
2886     if (VT != MVT::iPTR) {
2887       Ty = MVT::getTypeForValueType(VT);
2888     } else if (SV) {
2889       const PointerType *PT = dyn_cast<PointerType>(SV->getType());
2890       assert(PT && "Value for load must be a pointer");
2891       Ty = PT->getElementType();
2892     }
2893     assert(Ty && "Could not get type information for load");
2894     Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
2895   }
2896
2897   if (VT == EVT) {
2898     ExtType = ISD::NON_EXTLOAD;
2899   } else if (ExtType == ISD::NON_EXTLOAD) {
2900     assert(VT == EVT && "Non-extending load from different memory type!");
2901   } else {
2902     // Extending load.
2903     if (MVT::isVector(VT))
2904       assert(EVT == MVT::getVectorElementType(VT) && "Invalid vector extload!");
2905     else
2906       assert(MVT::getSizeInBits(EVT) < MVT::getSizeInBits(VT) &&
2907              "Should only be an extending load, not truncating!");
2908     assert((ExtType == ISD::EXTLOAD || MVT::isInteger(VT)) &&
2909            "Cannot sign/zero extend a FP/Vector load!");
2910     assert(MVT::isInteger(VT) == MVT::isInteger(EVT) &&
2911            "Cannot convert from FP to Int or Int -> FP!");
2912   }
2913
2914   bool Indexed = AM != ISD::UNINDEXED;
2915   assert(Indexed || Offset.getOpcode() == ISD::UNDEF &&
2916          "Unindexed load with an offset!");
2917
2918   SDVTList VTs = Indexed ?
2919     getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
2920   SDOperand Ops[] = { Chain, Ptr, Offset };
2921   FoldingSetNodeID ID;
2922   AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
2923   ID.AddInteger(AM);
2924   ID.AddInteger(ExtType);
2925   ID.AddInteger((unsigned int)EVT);
2926   ID.AddInteger(Alignment);
2927   ID.AddInteger(isVolatile);
2928   void *IP = 0;
2929   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2930     return SDOperand(E, 0);
2931   SDNode *N = new LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset,
2932                              Alignment, isVolatile);
2933   CSEMap.InsertNode(N, IP);
2934   AllNodes.push_back(N);
2935   return SDOperand(N, 0);
2936 }
2937
2938 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
2939                                 SDOperand Chain, SDOperand Ptr,
2940                                 const Value *SV, int SVOffset,
2941                                 bool isVolatile, unsigned Alignment) {
2942   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2943   return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, Chain, Ptr, Undef,
2944                  SV, SVOffset, VT, isVolatile, Alignment);
2945 }
2946
2947 SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT,
2948                                    SDOperand Chain, SDOperand Ptr,
2949                                    const Value *SV,
2950                                    int SVOffset, MVT::ValueType EVT,
2951                                    bool isVolatile, unsigned Alignment) {
2952   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2953   return getLoad(ISD::UNINDEXED, ExtType, VT, Chain, Ptr, Undef,
2954                  SV, SVOffset, EVT, isVolatile, Alignment);
2955 }
2956
2957 SDOperand
2958 SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base,
2959                              SDOperand Offset, ISD::MemIndexedMode AM) {
2960   LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
2961   assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
2962          "Load is already a indexed load!");
2963   return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(),
2964                  LD->getChain(), Base, Offset, LD->getSrcValue(),
2965                  LD->getSrcValueOffset(), LD->getMemoryVT(),
2966                  LD->isVolatile(), LD->getAlignment());
2967 }
2968
2969 SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val,
2970                                  SDOperand Ptr, const Value *SV, int SVOffset,
2971                                  bool isVolatile, unsigned Alignment) {
2972   MVT::ValueType VT = Val.getValueType();
2973
2974   if (Alignment == 0) { // Ensure that codegen never sees alignment 0
2975     const Type *Ty = 0;
2976     if (VT != MVT::iPTR) {
2977       Ty = MVT::getTypeForValueType(VT);
2978     } else if (SV) {
2979       const PointerType *PT = dyn_cast<PointerType>(SV->getType());
2980       assert(PT && "Value for store must be a pointer");
2981       Ty = PT->getElementType();
2982     }
2983     assert(Ty && "Could not get type information for store");
2984     Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
2985   }
2986   SDVTList VTs = getVTList(MVT::Other);
2987   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2988   SDOperand Ops[] = { Chain, Val, Ptr, Undef };
2989   FoldingSetNodeID ID;
2990   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
2991   ID.AddInteger(ISD::UNINDEXED);
2992   ID.AddInteger(false);
2993   ID.AddInteger((unsigned int)VT);
2994   ID.AddInteger(Alignment);
2995   ID.AddInteger(isVolatile);
2996   void *IP = 0;
2997   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2998     return SDOperand(E, 0);
2999   SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, false,
3000                               VT, SV, SVOffset, Alignment, isVolatile);
3001   CSEMap.InsertNode(N, IP);
3002   AllNodes.push_back(N);
3003   return SDOperand(N, 0);
3004 }
3005
3006 SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val,
3007                                       SDOperand Ptr, const Value *SV,
3008                                       int SVOffset, MVT::ValueType SVT,
3009                                       bool isVolatile, unsigned Alignment) {
3010   MVT::ValueType VT = Val.getValueType();
3011
3012   if (VT == SVT)
3013     return getStore(Chain, Val, Ptr, SV, SVOffset, isVolatile, Alignment);
3014
3015   assert(MVT::getSizeInBits(VT) > MVT::getSizeInBits(SVT) &&
3016          "Not a truncation?");
3017   assert(MVT::isInteger(VT) == MVT::isInteger(SVT) &&
3018          "Can't do FP-INT conversion!");
3019
3020   if (Alignment == 0) { // Ensure that codegen never sees alignment 0
3021     const Type *Ty = 0;
3022     if (VT != MVT::iPTR) {
3023       Ty = MVT::getTypeForValueType(VT);
3024     } else if (SV) {
3025       const PointerType *PT = dyn_cast<PointerType>(SV->getType());
3026       assert(PT && "Value for store must be a pointer");
3027       Ty = PT->getElementType();
3028     }
3029     assert(Ty && "Could not get type information for store");
3030     Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
3031   }
3032   SDVTList VTs = getVTList(MVT::Other);
3033   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
3034   SDOperand Ops[] = { Chain, Val, Ptr, Undef };
3035   FoldingSetNodeID ID;
3036   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
3037   ID.AddInteger(ISD::UNINDEXED);
3038   ID.AddInteger(1);
3039   ID.AddInteger((unsigned int)SVT);
3040   ID.AddInteger(Alignment);
3041   ID.AddInteger(isVolatile);
3042   void *IP = 0;
3043   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3044     return SDOperand(E, 0);
3045   SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, true,
3046                               SVT, SV, SVOffset, Alignment, isVolatile);
3047   CSEMap.InsertNode(N, IP);
3048   AllNodes.push_back(N);
3049   return SDOperand(N, 0);
3050 }
3051
3052 SDOperand
3053 SelectionDAG::getIndexedStore(SDOperand OrigStore, SDOperand Base,
3054                               SDOperand Offset, ISD::MemIndexedMode AM) {
3055   StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
3056   assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
3057          "Store is already a indexed store!");
3058   SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
3059   SDOperand Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
3060   FoldingSetNodeID ID;
3061   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
3062   ID.AddInteger(AM);
3063   ID.AddInteger(ST->isTruncatingStore());
3064   ID.AddInteger((unsigned int)(ST->getMemoryVT()));
3065   ID.AddInteger(ST->getAlignment());
3066   ID.AddInteger(ST->isVolatile());
3067   void *IP = 0;
3068   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3069     return SDOperand(E, 0);
3070   SDNode *N = new StoreSDNode(Ops, VTs, AM,
3071                               ST->isTruncatingStore(), ST->getMemoryVT(),
3072                               ST->getSrcValue(), ST->getSrcValueOffset(),
3073                               ST->getAlignment(), ST->isVolatile());
3074   CSEMap.InsertNode(N, IP);
3075   AllNodes.push_back(N);
3076   return SDOperand(N, 0);
3077 }
3078
3079 SDOperand SelectionDAG::getVAArg(MVT::ValueType VT,
3080                                  SDOperand Chain, SDOperand Ptr,
3081                                  SDOperand SV) {
3082   SDOperand Ops[] = { Chain, Ptr, SV };
3083   return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3);
3084 }
3085
3086 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
3087                                 SDOperandPtr Ops, unsigned NumOps) {
3088   switch (NumOps) {
3089   case 0: return getNode(Opcode, VT);
3090   case 1: return getNode(Opcode, VT, Ops[0]);
3091   case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
3092   case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
3093   default: break;
3094   }
3095
3096   switch (Opcode) {
3097   default: break;
3098   case ISD::SELECT_CC: {
3099     assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
3100     assert(Ops[0].getValueType() == Ops[1].getValueType() &&
3101            "LHS and RHS of condition must have same type!");
3102     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
3103            "True and False arms of SelectCC must have same type!");
3104     assert(Ops[2].getValueType() == VT &&
3105            "select_cc node must be of same type as true and false value!");
3106     break;
3107   }
3108   case ISD::BR_CC: {
3109     assert(NumOps == 5 && "BR_CC takes 5 operands!");
3110     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
3111            "LHS/RHS of comparison should match types!");
3112     break;
3113   }
3114   }
3115
3116   // Memoize nodes.
3117   SDNode *N;
3118   SDVTList VTs = getVTList(VT);
3119   if (VT != MVT::Flag) {
3120     FoldingSetNodeID ID;
3121     AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
3122     void *IP = 0;
3123     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3124       return SDOperand(E, 0);
3125     N = new SDNode(Opcode, VTs, Ops, NumOps);
3126     CSEMap.InsertNode(N, IP);
3127   } else {
3128     N = new SDNode(Opcode, VTs, Ops, NumOps);
3129   }
3130   AllNodes.push_back(N);
3131   return SDOperand(N, 0);
3132 }
3133
3134 SDOperand SelectionDAG::getNode(unsigned Opcode,
3135                                 std::vector<MVT::ValueType> &ResultTys,
3136                                 SDOperandPtr Ops, unsigned NumOps) {
3137   return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(),
3138                  Ops, NumOps);
3139 }
3140
3141 SDOperand SelectionDAG::getNode(unsigned Opcode,
3142                                 const MVT::ValueType *VTs, unsigned NumVTs,
3143                                 SDOperandPtr Ops, unsigned NumOps) {
3144   if (NumVTs == 1)
3145     return getNode(Opcode, VTs[0], Ops, NumOps);
3146   return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps);
3147 }
3148
3149 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3150                                 SDOperandPtr Ops, unsigned NumOps) {
3151   if (VTList.NumVTs == 1)
3152     return getNode(Opcode, VTList.VTs[0], Ops, NumOps);
3153
3154   switch (Opcode) {
3155   // FIXME: figure out how to safely handle things like
3156   // int foo(int x) { return 1 << (x & 255); }
3157   // int bar() { return foo(256); }
3158 #if 0
3159   case ISD::SRA_PARTS:
3160   case ISD::SRL_PARTS:
3161   case ISD::SHL_PARTS:
3162     if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
3163         cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
3164       return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
3165     else if (N3.getOpcode() == ISD::AND)
3166       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
3167         // If the and is only masking out bits that cannot effect the shift,
3168         // eliminate the and.
3169         unsigned NumBits = MVT::getSizeInBits(VT)*2;
3170         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
3171           return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
3172       }
3173     break;
3174 #endif
3175   }
3176
3177   // Memoize the node unless it returns a flag.
3178   SDNode *N;
3179   if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
3180     FoldingSetNodeID ID;
3181     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
3182     void *IP = 0;
3183     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3184       return SDOperand(E, 0);
3185     if (NumOps == 1)
3186       N = new UnarySDNode(Opcode, VTList, Ops[0]);
3187     else if (NumOps == 2)
3188       N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
3189     else if (NumOps == 3)
3190       N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
3191     else
3192       N = new SDNode(Opcode, VTList, Ops, NumOps);
3193     CSEMap.InsertNode(N, IP);
3194   } else {
3195     if (NumOps == 1)
3196       N = new UnarySDNode(Opcode, VTList, Ops[0]);
3197     else if (NumOps == 2)
3198       N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
3199     else if (NumOps == 3)
3200       N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
3201     else
3202       N = new SDNode(Opcode, VTList, Ops, NumOps);
3203   }
3204   AllNodes.push_back(N);
3205   return SDOperand(N, 0);
3206 }
3207
3208 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList) {
3209   return getNode(Opcode, VTList, (SDOperand*)0, 0);
3210 }
3211
3212 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3213                                 SDOperand N1) {
3214   SDOperand Ops[] = { N1 };
3215   return getNode(Opcode, VTList, Ops, 1);
3216 }
3217
3218 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3219                                 SDOperand N1, SDOperand N2) {
3220   SDOperand Ops[] = { N1, N2 };
3221   return getNode(Opcode, VTList, Ops, 2);
3222 }
3223
3224 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3225                                 SDOperand N1, SDOperand N2, SDOperand N3) {
3226   SDOperand Ops[] = { N1, N2, N3 };
3227   return getNode(Opcode, VTList, Ops, 3);
3228 }
3229
3230 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3231                                 SDOperand N1, SDOperand N2, SDOperand N3,
3232                                 SDOperand N4) {
3233   SDOperand Ops[] = { N1, N2, N3, N4 };
3234   return getNode(Opcode, VTList, Ops, 4);
3235 }
3236
3237 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3238                                 SDOperand N1, SDOperand N2, SDOperand N3,
3239                                 SDOperand N4, SDOperand N5) {
3240   SDOperand Ops[] = { N1, N2, N3, N4, N5 };
3241   return getNode(Opcode, VTList, Ops, 5);
3242 }
3243
3244 SDVTList SelectionDAG::getVTList(MVT::ValueType VT) {
3245   return makeVTList(SDNode::getValueTypeList(VT), 1);
3246 }
3247
3248 SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2) {
3249   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
3250        E = VTList.end(); I != E; ++I) {
3251     if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2)
3252       return makeVTList(&(*I)[0], 2);
3253   }
3254   std::vector<MVT::ValueType> V;
3255   V.push_back(VT1);
3256   V.push_back(VT2);
3257   VTList.push_front(V);
3258   return makeVTList(&(*VTList.begin())[0], 2);
3259 }
3260 SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2,
3261                                  MVT::ValueType VT3) {
3262   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
3263        E = VTList.end(); I != E; ++I) {
3264     if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 &&
3265         (*I)[2] == VT3)
3266       return makeVTList(&(*I)[0], 3);
3267   }
3268   std::vector<MVT::ValueType> V;
3269   V.push_back(VT1);
3270   V.push_back(VT2);
3271   V.push_back(VT3);
3272   VTList.push_front(V);
3273   return makeVTList(&(*VTList.begin())[0], 3);
3274 }
3275
3276 SDVTList SelectionDAG::getVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
3277   switch (NumVTs) {
3278     case 0: assert(0 && "Cannot have nodes without results!");
3279     case 1: return getVTList(VTs[0]);
3280     case 2: return getVTList(VTs[0], VTs[1]);
3281     case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
3282     default: break;
3283   }
3284
3285   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
3286        E = VTList.end(); I != E; ++I) {
3287     if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue;
3288
3289     bool NoMatch = false;
3290     for (unsigned i = 2; i != NumVTs; ++i)
3291       if (VTs[i] != (*I)[i]) {
3292         NoMatch = true;
3293         break;
3294       }
3295     if (!NoMatch)
3296       return makeVTList(&*I->begin(), NumVTs);
3297   }
3298
3299   VTList.push_front(std::vector<MVT::ValueType>(VTs, VTs+NumVTs));
3300   return makeVTList(&*VTList.begin()->begin(), NumVTs);
3301 }
3302
3303
3304 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
3305 /// specified operands.  If the resultant node already exists in the DAG,
3306 /// this does not modify the specified node, instead it returns the node that
3307 /// already exists.  If the resultant node does not exist in the DAG, the
3308 /// input node is returned.  As a degenerate case, if you specify the same
3309 /// input operands as the node already has, the input node is returned.
3310 SDOperand SelectionDAG::
3311 UpdateNodeOperands(SDOperand InN, SDOperand Op) {
3312   SDNode *N = InN.Val;
3313   assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
3314
3315   // Check to see if there is no change.
3316   if (Op == N->getOperand(0)) return InN;
3317
3318   // See if the modified node already exists.
3319   void *InsertPos = 0;
3320   if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
3321     return SDOperand(Existing, InN.ResNo);
3322
3323   // Nope it doesn't.  Remove the node from it's current place in the maps.
3324   if (InsertPos)
3325     RemoveNodeFromCSEMaps(N);
3326
3327   // Now we update the operands.
3328   N->OperandList[0].getVal()->removeUser(0, N);
3329   N->OperandList[0] = Op;
3330   N->OperandList[0].setUser(N);
3331   Op.Val->addUser(0, N);
3332
3333   // If this gets put into a CSE map, add it.
3334   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3335   return InN;
3336 }
3337
3338 SDOperand SelectionDAG::
3339 UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) {
3340   SDNode *N = InN.Val;
3341   assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
3342
3343   // Check to see if there is no change.
3344   if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
3345     return InN;   // No operands changed, just return the input node.
3346
3347   // See if the modified node already exists.
3348   void *InsertPos = 0;
3349   if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
3350     return SDOperand(Existing, InN.ResNo);
3351
3352   // Nope it doesn't.  Remove the node from it's current place in the maps.
3353   if (InsertPos)
3354     RemoveNodeFromCSEMaps(N);
3355
3356   // Now we update the operands.
3357   if (N->OperandList[0] != Op1) {
3358     N->OperandList[0].getVal()->removeUser(0, N);
3359     N->OperandList[0] = Op1;
3360     N->OperandList[0].setUser(N);
3361     Op1.Val->addUser(0, N);
3362   }
3363   if (N->OperandList[1] != Op2) {
3364     N->OperandList[1].getVal()->removeUser(1, N);
3365     N->OperandList[1] = Op2;
3366     N->OperandList[1].setUser(N);
3367     Op2.Val->addUser(1, N);
3368   }
3369
3370   // If this gets put into a CSE map, add it.
3371   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3372   return InN;
3373 }
3374
3375 SDOperand SelectionDAG::
3376 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
3377   SDOperand Ops[] = { Op1, Op2, Op3 };
3378   return UpdateNodeOperands(N, Ops, 3);
3379 }
3380
3381 SDOperand SelectionDAG::
3382 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
3383                    SDOperand Op3, SDOperand Op4) {
3384   SDOperand Ops[] = { Op1, Op2, Op3, Op4 };
3385   return UpdateNodeOperands(N, Ops, 4);
3386 }
3387
3388 SDOperand SelectionDAG::
3389 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
3390                    SDOperand Op3, SDOperand Op4, SDOperand Op5) {
3391   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
3392   return UpdateNodeOperands(N, Ops, 5);
3393 }
3394
3395 SDOperand SelectionDAG::
3396 UpdateNodeOperands(SDOperand InN, SDOperandPtr Ops, unsigned NumOps) {
3397   SDNode *N = InN.Val;
3398   assert(N->getNumOperands() == NumOps &&
3399          "Update with wrong number of operands");
3400
3401   // Check to see if there is no change.
3402   bool AnyChange = false;
3403   for (unsigned i = 0; i != NumOps; ++i) {
3404     if (Ops[i] != N->getOperand(i)) {
3405       AnyChange = true;
3406       break;
3407     }
3408   }
3409
3410   // No operands changed, just return the input node.
3411   if (!AnyChange) return InN;
3412
3413   // See if the modified node already exists.
3414   void *InsertPos = 0;
3415   if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
3416     return SDOperand(Existing, InN.ResNo);
3417
3418   // Nope it doesn't.  Remove the node from its current place in the maps.
3419   if (InsertPos)
3420     RemoveNodeFromCSEMaps(N);
3421
3422   // Now we update the operands.
3423   for (unsigned i = 0; i != NumOps; ++i) {
3424     if (N->OperandList[i] != Ops[i]) {
3425       N->OperandList[i].getVal()->removeUser(i, N);
3426       N->OperandList[i] = Ops[i];
3427       N->OperandList[i].setUser(N);
3428       Ops[i].Val->addUser(i, N);
3429     }
3430   }
3431
3432   // If this gets put into a CSE map, add it.
3433   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3434   return InN;
3435 }
3436
3437 /// MorphNodeTo - This frees the operands of the current node, resets the
3438 /// opcode, types, and operands to the specified value.  This should only be
3439 /// used by the SelectionDAG class.
3440 void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
3441                          SDOperandPtr Ops, unsigned NumOps) {
3442   NodeType = Opc;
3443   ValueList = L.VTs;
3444   NumValues = L.NumVTs;
3445
3446   // Clear the operands list, updating used nodes to remove this from their
3447   // use list.
3448   for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
3449     I->getVal()->removeUser(std::distance(op_begin(), I), this);
3450
3451   // If NumOps is larger than the # of operands we currently have, reallocate
3452   // the operand list.
3453   if (NumOps > NumOperands) {
3454     if (OperandsNeedDelete) {
3455       delete [] OperandList;
3456     }
3457     OperandList = new SDUse[NumOps];
3458     OperandsNeedDelete = true;
3459   }
3460
3461   // Assign the new operands.
3462   NumOperands = NumOps;
3463
3464   for (unsigned i = 0, e = NumOps; i != e; ++i) {
3465     OperandList[i] = Ops[i];
3466     OperandList[i].setUser(this);
3467     SDNode *N = OperandList[i].getVal();
3468     N->addUser(i, this);
3469     ++N->UsesSize;
3470   }
3471 }
3472
3473 /// SelectNodeTo - These are used for target selectors to *mutate* the
3474 /// specified node to have the specified return type, Target opcode, and
3475 /// operands.  Note that target opcodes are stored as
3476 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
3477 ///
3478 /// Note that SelectNodeTo returns the resultant node.  If there is already a
3479 /// node of the specified opcode and operands, it returns that node instead of
3480 /// the current one.
3481 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3482                                    MVT::ValueType VT) {
3483   SDVTList VTs = getVTList(VT);
3484   FoldingSetNodeID ID;
3485   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, (SDOperand*)0, 0);
3486   void *IP = 0;
3487   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3488     return ON;
3489
3490   RemoveNodeFromCSEMaps(N);
3491
3492   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, SDOperandPtr(), 0);
3493
3494   CSEMap.InsertNode(N, IP);
3495   return N;
3496 }
3497
3498 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3499                                    MVT::ValueType VT, SDOperand Op1) {
3500   // If an identical node already exists, use it.
3501   SDVTList VTs = getVTList(VT);
3502   SDOperand Ops[] = { Op1 };
3503
3504   FoldingSetNodeID ID;
3505   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1);
3506   void *IP = 0;
3507   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3508     return ON;
3509
3510   RemoveNodeFromCSEMaps(N);
3511   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1);
3512   CSEMap.InsertNode(N, IP);
3513   return N;
3514 }
3515
3516 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3517                                    MVT::ValueType VT, SDOperand Op1,
3518                                    SDOperand Op2) {
3519   // If an identical node already exists, use it.
3520   SDVTList VTs = getVTList(VT);
3521   SDOperand Ops[] = { Op1, Op2 };
3522
3523   FoldingSetNodeID ID;
3524   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3525   void *IP = 0;
3526   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3527     return ON;
3528
3529   RemoveNodeFromCSEMaps(N);
3530
3531   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3532
3533   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3534   return N;
3535 }
3536
3537 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3538                                    MVT::ValueType VT, SDOperand Op1,
3539                                    SDOperand Op2, SDOperand Op3) {
3540   // If an identical node already exists, use it.
3541   SDVTList VTs = getVTList(VT);
3542   SDOperand Ops[] = { Op1, Op2, Op3 };
3543   FoldingSetNodeID ID;
3544   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3545   void *IP = 0;
3546   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3547     return ON;
3548
3549   RemoveNodeFromCSEMaps(N);
3550
3551   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3552
3553   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3554   return N;
3555 }
3556
3557 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3558                                    MVT::ValueType VT, SDOperandPtr Ops,
3559                                    unsigned NumOps) {
3560   // If an identical node already exists, use it.
3561   SDVTList VTs = getVTList(VT);
3562   FoldingSetNodeID ID;
3563   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
3564   void *IP = 0;
3565   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3566     return ON;
3567
3568   RemoveNodeFromCSEMaps(N);
3569   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
3570
3571   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3572   return N;
3573 }
3574
3575 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3576                                    MVT::ValueType VT1, MVT::ValueType VT2,
3577                                    SDOperand Op1, SDOperand Op2) {
3578   SDVTList VTs = getVTList(VT1, VT2);
3579   FoldingSetNodeID ID;
3580   SDOperand Ops[] = { Op1, Op2 };
3581   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3582   void *IP = 0;
3583   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3584     return ON;
3585
3586   RemoveNodeFromCSEMaps(N);
3587   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3588   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3589   return N;
3590 }
3591
3592 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3593                                    MVT::ValueType VT1, MVT::ValueType VT2,
3594                                    SDOperand Op1, SDOperand Op2,
3595                                    SDOperand Op3) {
3596   // If an identical node already exists, use it.
3597   SDVTList VTs = getVTList(VT1, VT2);
3598   SDOperand Ops[] = { Op1, Op2, Op3 };
3599   FoldingSetNodeID ID;
3600   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3601   void *IP = 0;
3602   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3603     return ON;
3604
3605   RemoveNodeFromCSEMaps(N);
3606
3607   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3608   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3609   return N;
3610 }
3611
3612
3613 /// getTargetNode - These are used for target selectors to create a new node
3614 /// with specified return type(s), target opcode, and operands.
3615 ///
3616 /// Note that getTargetNode returns the resultant node.  If there is already a
3617 /// node of the specified opcode and operands, it returns that node instead of
3618 /// the current one.
3619 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) {
3620   return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val;
3621 }
3622 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3623                                     SDOperand Op1) {
3624   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val;
3625 }
3626 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3627                                     SDOperand Op1, SDOperand Op2) {
3628   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val;
3629 }
3630 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3631                                     SDOperand Op1, SDOperand Op2,
3632                                     SDOperand Op3) {
3633   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
3634 }
3635 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3636                                     SDOperandPtr Ops, unsigned NumOps) {
3637   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val;
3638 }
3639 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3640                                     MVT::ValueType VT2) {
3641   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3642   SDOperand Op;
3643   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op, 0).Val;
3644 }
3645 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3646                                     MVT::ValueType VT2, SDOperand Op1) {
3647   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3648   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val;
3649 }
3650 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3651                                     MVT::ValueType VT2, SDOperand Op1,
3652                                     SDOperand Op2) {
3653   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3654   SDOperand Ops[] = { Op1, Op2 };
3655   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val;
3656 }
3657 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3658                                     MVT::ValueType VT2, SDOperand Op1,
3659                                     SDOperand Op2, SDOperand Op3) {
3660   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3661   SDOperand Ops[] = { Op1, Op2, Op3 };
3662   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val;
3663 }
3664 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3665                                     MVT::ValueType VT2,
3666                                     SDOperandPtr Ops, unsigned NumOps) {
3667   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3668   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val;
3669 }
3670 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3671                                     MVT::ValueType VT2, MVT::ValueType VT3,
3672                                     SDOperand Op1, SDOperand Op2) {
3673   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
3674   SDOperand Ops[] = { Op1, Op2 };
3675   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val;
3676 }
3677 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3678                                     MVT::ValueType VT2, MVT::ValueType VT3,
3679                                     SDOperand Op1, SDOperand Op2,
3680                                     SDOperand Op3) {
3681   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
3682   SDOperand Ops[] = { Op1, Op2, Op3 };
3683   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 3).Val;
3684 }
3685 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3686                                     MVT::ValueType VT2, MVT::ValueType VT3,
3687                                     SDOperandPtr Ops, unsigned NumOps) {
3688   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
3689   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val;
3690 }
3691 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3692                                     MVT::ValueType VT2, MVT::ValueType VT3,
3693                                     MVT::ValueType VT4,
3694                                     SDOperandPtr Ops, unsigned NumOps) {
3695   std::vector<MVT::ValueType> VTList;
3696   VTList.push_back(VT1);
3697   VTList.push_back(VT2);
3698   VTList.push_back(VT3);
3699   VTList.push_back(VT4);
3700   const MVT::ValueType *VTs = getNodeValueTypes(VTList);
3701   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 4, Ops, NumOps).Val;
3702 }
3703 SDNode *SelectionDAG::getTargetNode(unsigned Opcode,
3704                                     std::vector<MVT::ValueType> &ResultTys,
3705                                     SDOperandPtr Ops, unsigned NumOps) {
3706   const MVT::ValueType *VTs = getNodeValueTypes(ResultTys);
3707   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, ResultTys.size(),
3708                  Ops, NumOps).Val;
3709 }
3710
3711 /// getNodeIfExists - Get the specified node if it's already available, or
3712 /// else return NULL.
3713 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
3714                                       SDOperandPtr Ops, unsigned NumOps) {
3715   if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
3716     FoldingSetNodeID ID;
3717     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
3718     void *IP = 0;
3719     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3720       return E;
3721   }
3722   return NULL;
3723 }
3724
3725
3726 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3727 /// This can cause recursive merging of nodes in the DAG.
3728 ///
3729 /// This version assumes From has a single result value.
3730 ///
3731 void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To,
3732                                       DAGUpdateListener *UpdateListener) {
3733   SDNode *From = FromN.Val;
3734   assert(From->getNumValues() == 1 && FromN.ResNo == 0 &&
3735          "Cannot replace with this method!");
3736   assert(From != To.Val && "Cannot replace uses of with self");
3737
3738   while (!From->use_empty()) {
3739     SDNode::use_iterator UI = From->use_begin();
3740     SDNode *U = UI->getUser();
3741
3742     // This node is about to morph, remove its old self from the CSE maps.
3743     RemoveNodeFromCSEMaps(U);
3744     int operandNum = 0;
3745     for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
3746          I != E; ++I, ++operandNum)
3747       if (I->getVal() == From) {
3748         From->removeUser(operandNum, U);
3749         *I = To;
3750         I->setUser(U);
3751         To.Val->addUser(operandNum, U);
3752       }
3753
3754     // Now that we have modified U, add it back to the CSE maps.  If it already
3755     // exists there, recursively merge the results together.
3756     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
3757       ReplaceAllUsesWith(U, Existing, UpdateListener);
3758       // U is now dead.  Inform the listener if it exists and delete it.
3759       if (UpdateListener)
3760         UpdateListener->NodeDeleted(U);
3761       DeleteNodeNotInCSEMaps(U);
3762     } else {
3763       // If the node doesn't already exist, we updated it.  Inform a listener if
3764       // it exists.
3765       if (UpdateListener)
3766         UpdateListener->NodeUpdated(U);
3767     }
3768   }
3769 }
3770
3771 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3772 /// This can cause recursive merging of nodes in the DAG.
3773 ///
3774 /// This version assumes From/To have matching types and numbers of result
3775 /// values.
3776 ///
3777 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
3778                                       DAGUpdateListener *UpdateListener) {
3779   assert(From != To && "Cannot replace uses of with self");
3780   assert(From->getNumValues() == To->getNumValues() &&
3781          "Cannot use this version of ReplaceAllUsesWith!");
3782   if (From->getNumValues() == 1)   // If possible, use the faster version.
3783     return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0),
3784                               UpdateListener);
3785
3786   while (!From->use_empty()) {
3787     SDNode::use_iterator UI = From->use_begin();
3788     SDNode *U = UI->getUser();
3789
3790     // This node is about to morph, remove its old self from the CSE maps.
3791     RemoveNodeFromCSEMaps(U);
3792     int operandNum = 0;
3793     for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
3794          I != E; ++I, ++operandNum)
3795       if (I->getVal() == From) {
3796         From->removeUser(operandNum, U);
3797         I->getVal() = To;
3798         To->addUser(operandNum, U);
3799       }
3800
3801     // Now that we have modified U, add it back to the CSE maps.  If it already
3802     // exists there, recursively merge the results together.
3803     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
3804       ReplaceAllUsesWith(U, Existing, UpdateListener);
3805       // U is now dead.  Inform the listener if it exists and delete it.
3806       if (UpdateListener)
3807         UpdateListener->NodeDeleted(U);
3808       DeleteNodeNotInCSEMaps(U);
3809     } else {
3810       // If the node doesn't already exist, we updated it.  Inform a listener if
3811       // it exists.
3812       if (UpdateListener)
3813         UpdateListener->NodeUpdated(U);
3814     }
3815   }
3816 }
3817
3818 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3819 /// This can cause recursive merging of nodes in the DAG.
3820 ///
3821 /// This version can replace From with any result values.  To must match the
3822 /// number and types of values returned by From.
3823 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
3824                                       SDOperandPtr To,
3825                                       DAGUpdateListener *UpdateListener) {
3826   if (From->getNumValues() == 1)  // Handle the simple case efficiently.
3827     return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener);
3828
3829   while (!From->use_empty()) {
3830     SDNode::use_iterator UI = From->use_begin();
3831     SDNode *U = UI->getUser();
3832
3833     // This node is about to morph, remove its old self from the CSE maps.
3834     RemoveNodeFromCSEMaps(U);
3835     int operandNum = 0;
3836     for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
3837          I != E; ++I, ++operandNum)
3838       if (I->getVal() == From) {
3839         const SDOperand &ToOp = To[I->getSDOperand().ResNo];
3840         From->removeUser(operandNum, U);
3841         *I = ToOp;
3842         I->setUser(U);
3843         ToOp.Val->addUser(operandNum, U);
3844       }
3845
3846     // Now that we have modified U, add it back to the CSE maps.  If it already
3847     // exists there, recursively merge the results together.
3848     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
3849       ReplaceAllUsesWith(U, Existing, UpdateListener);
3850       // U is now dead.  Inform the listener if it exists and delete it.
3851       if (UpdateListener)
3852         UpdateListener->NodeDeleted(U);
3853       DeleteNodeNotInCSEMaps(U);
3854     } else {
3855       // If the node doesn't already exist, we updated it.  Inform a listener if
3856       // it exists.
3857       if (UpdateListener)
3858         UpdateListener->NodeUpdated(U);
3859     }
3860   }
3861 }
3862
3863 namespace {
3864   /// ChainedSetUpdaterListener - This class is a DAGUpdateListener that removes
3865   /// any deleted nodes from the set passed into its constructor and recursively
3866   /// notifies another update listener if specified.
3867   class ChainedSetUpdaterListener :
3868   public SelectionDAG::DAGUpdateListener {
3869     SmallSetVector<SDNode*, 16> &Set;
3870     SelectionDAG::DAGUpdateListener *Chain;
3871   public:
3872     ChainedSetUpdaterListener(SmallSetVector<SDNode*, 16> &set,
3873                               SelectionDAG::DAGUpdateListener *chain)
3874       : Set(set), Chain(chain) {}
3875
3876     virtual void NodeDeleted(SDNode *N) {
3877       Set.remove(N);
3878       if (Chain) Chain->NodeDeleted(N);
3879     }
3880     virtual void NodeUpdated(SDNode *N) {
3881       if (Chain) Chain->NodeUpdated(N);
3882     }
3883   };
3884 }
3885
3886 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
3887 /// uses of other values produced by From.Val alone.  The Deleted vector is
3888 /// handled the same way as for ReplaceAllUsesWith.
3889 void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
3890                                              DAGUpdateListener *UpdateListener){
3891   assert(From != To && "Cannot replace a value with itself");
3892
3893   // Handle the simple, trivial, case efficiently.
3894   if (From.Val->getNumValues() == 1) {
3895     ReplaceAllUsesWith(From, To, UpdateListener);
3896     return;
3897   }
3898
3899   if (From.use_empty()) return;
3900
3901   // Get all of the users of From.Val.  We want these in a nice,
3902   // deterministically ordered and uniqued set, so we use a SmallSetVector.
3903   SmallSetVector<SDNode*, 16> Users;
3904   for (SDNode::use_iterator UI = From.Val->use_begin(),
3905       E = From.Val->use_end(); UI != E; ++UI) {
3906     SDNode *User = UI->getUser();
3907     if (!Users.count(User))
3908       Users.insert(User);
3909   }
3910
3911   // When one of the recursive merges deletes nodes from the graph, we need to
3912   // make sure that UpdateListener is notified *and* that the node is removed
3913   // from Users if present.  CSUL does this.
3914   ChainedSetUpdaterListener CSUL(Users, UpdateListener);
3915
3916   while (!Users.empty()) {
3917     // We know that this user uses some value of From.  If it is the right
3918     // value, update it.
3919     SDNode *User = Users.back();
3920     Users.pop_back();
3921
3922     // Scan for an operand that matches From.
3923     SDNode::op_iterator Op = User->op_begin(), E = User->op_end();
3924     for (; Op != E; ++Op)
3925       if (*Op == From) break;
3926
3927     // If there are no matches, the user must use some other result of From.
3928     if (Op == E) continue;
3929
3930     // Okay, we know this user needs to be updated.  Remove its old self
3931     // from the CSE maps.
3932     RemoveNodeFromCSEMaps(User);
3933
3934     // Update all operands that match "From" in case there are multiple uses.
3935     for (; Op != E; ++Op) {
3936       if (*Op == From) {
3937         From.Val->removeUser(Op-User->op_begin(), User);
3938         *Op = To;
3939         Op->setUser(User);
3940         To.Val->addUser(Op-User->op_begin(), User);
3941       }
3942     }
3943
3944     // Now that we have modified User, add it back to the CSE maps.  If it
3945     // already exists there, recursively merge the results together.
3946     SDNode *Existing = AddNonLeafNodeToCSEMaps(User);
3947     if (!Existing) {
3948       if (UpdateListener) UpdateListener->NodeUpdated(User);
3949       continue;  // Continue on to next user.
3950     }
3951
3952     // If there was already an existing matching node, use ReplaceAllUsesWith
3953     // to replace the dead one with the existing one.  This can cause
3954     // recursive merging of other unrelated nodes down the line.  The merging
3955     // can cause deletion of nodes that used the old value.  To handle this, we
3956     // use CSUL to remove them from the Users set.
3957     ReplaceAllUsesWith(User, Existing, &CSUL);
3958
3959     // User is now dead.  Notify a listener if present.
3960     if (UpdateListener) UpdateListener->NodeDeleted(User);
3961     DeleteNodeNotInCSEMaps(User);
3962   }
3963 }
3964
3965 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on
3966 /// their allnodes order. It returns the maximum id.
3967 unsigned SelectionDAG::AssignNodeIds() {
3968   unsigned Id = 0;
3969   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){
3970     SDNode *N = I;
3971     N->setNodeId(Id++);
3972   }
3973   return Id;
3974 }
3975
3976 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
3977 /// based on their topological order. It returns the maximum id and a vector
3978 /// of the SDNodes* in assigned order by reference.
3979 unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
3980   unsigned DAGSize = AllNodes.size();
3981   std::vector<unsigned> InDegree(DAGSize);
3982   std::vector<SDNode*> Sources;
3983
3984   // Use a two pass approach to avoid using a std::map which is slow.
3985   unsigned Id = 0;
3986   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
3987     SDNode *N = I;
3988     N->setNodeId(Id++);
3989     unsigned Degree = N->use_size();
3990     InDegree[N->getNodeId()] = Degree;
3991     if (Degree == 0)
3992       Sources.push_back(N);
3993   }
3994
3995   TopOrder.clear();
3996   while (!Sources.empty()) {
3997     SDNode *N = Sources.back();
3998     Sources.pop_back();
3999     TopOrder.push_back(N);
4000     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
4001       SDNode *P = I->getVal();
4002       unsigned Degree = --InDegree[P->getNodeId()];
4003       if (Degree == 0)
4004         Sources.push_back(P);
4005     }
4006   }
4007
4008   // Second pass, assign the actual topological order as node ids.
4009   Id = 0;
4010   for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end();
4011        TI != TE; ++TI)
4012     (*TI)->setNodeId(Id++);
4013
4014   return Id;
4015 }
4016
4017
4018
4019 //===----------------------------------------------------------------------===//
4020 //                              SDNode Class
4021 //===----------------------------------------------------------------------===//
4022
4023 // Out-of-line virtual method to give class a home.
4024 void SDNode::ANCHOR() {}
4025 void UnarySDNode::ANCHOR() {}
4026 void BinarySDNode::ANCHOR() {}
4027 void TernarySDNode::ANCHOR() {}
4028 void HandleSDNode::ANCHOR() {}
4029 void StringSDNode::ANCHOR() {}
4030 void ConstantSDNode::ANCHOR() {}
4031 void ConstantFPSDNode::ANCHOR() {}
4032 void GlobalAddressSDNode::ANCHOR() {}
4033 void FrameIndexSDNode::ANCHOR() {}
4034 void JumpTableSDNode::ANCHOR() {}
4035 void ConstantPoolSDNode::ANCHOR() {}
4036 void BasicBlockSDNode::ANCHOR() {}
4037 void SrcValueSDNode::ANCHOR() {}
4038 void MemOperandSDNode::ANCHOR() {}
4039 void RegisterSDNode::ANCHOR() {}
4040 void ExternalSymbolSDNode::ANCHOR() {}
4041 void CondCodeSDNode::ANCHOR() {}
4042 void ARG_FLAGSSDNode::ANCHOR() {}
4043 void VTSDNode::ANCHOR() {}
4044 void LoadSDNode::ANCHOR() {}
4045 void StoreSDNode::ANCHOR() {}
4046 void AtomicSDNode::ANCHOR() {}
4047
4048 HandleSDNode::~HandleSDNode() {
4049   SDVTList VTs = { 0, 0 };
4050   MorphNodeTo(ISD::HANDLENODE, VTs, SDOperandPtr(), 0);  // Drops operand uses.
4051 }
4052
4053 GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA,
4054                                          MVT::ValueType VT, int o)
4055   : SDNode(isa<GlobalVariable>(GA) &&
4056            cast<GlobalVariable>(GA)->isThreadLocal() ?
4057            // Thread Local
4058            (isTarget ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress) :
4059            // Non Thread Local
4060            (isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress),
4061            getSDVTList(VT)), Offset(o) {
4062   TheGlobal = const_cast<GlobalValue*>(GA);
4063 }
4064
4065 /// getMemOperand - Return a MachineMemOperand object describing the memory
4066 /// reference performed by this load or store.
4067 MachineMemOperand LSBaseSDNode::getMemOperand() const {
4068   int Size = (MVT::getSizeInBits(getMemoryVT()) + 7) >> 3;
4069   int Flags =
4070     getOpcode() == ISD::LOAD ? MachineMemOperand::MOLoad :
4071                                MachineMemOperand::MOStore;
4072   if (IsVolatile) Flags |= MachineMemOperand::MOVolatile;
4073
4074   // Check if the load references a frame index, and does not have
4075   // an SV attached.
4076   const FrameIndexSDNode *FI =
4077     dyn_cast<const FrameIndexSDNode>(getBasePtr().Val);
4078   if (!getSrcValue() && FI)
4079     return MachineMemOperand(PseudoSourceValue::getFixedStack(), Flags,
4080                              FI->getIndex(), Size, Alignment);
4081   else
4082     return MachineMemOperand(getSrcValue(), Flags,
4083                              getSrcValueOffset(), Size, Alignment);
4084 }
4085
4086 /// Profile - Gather unique data for the node.
4087 ///
4088 void SDNode::Profile(FoldingSetNodeID &ID) {
4089   AddNodeIDNode(ID, this);
4090 }
4091
4092 /// getValueTypeList - Return a pointer to the specified value type.
4093 ///
4094 const MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
4095   if (MVT::isExtendedVT(VT)) {
4096     static std::set<MVT::ValueType> EVTs;
4097     return &(*EVTs.insert(VT).first);
4098   } else {
4099     static MVT::ValueType VTs[MVT::LAST_VALUETYPE];
4100     VTs[VT] = VT;
4101     return &VTs[VT];
4102   }
4103 }
4104
4105 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
4106 /// indicated value.  This method ignores uses of other values defined by this
4107 /// operation.
4108 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
4109   assert(Value < getNumValues() && "Bad value!");
4110
4111   // If there is only one value, this is easy.
4112   if (getNumValues() == 1)
4113     return use_size() == NUses;
4114   if (use_size() < NUses) return false;
4115
4116   SDOperand TheValue(const_cast<SDNode *>(this), Value);
4117
4118   SmallPtrSet<SDNode*, 32> UsersHandled;
4119
4120   // TODO: Only iterate over uses of a given value of the node
4121   for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
4122     if (*UI == TheValue) {
4123       if (NUses == 0)
4124         return false;
4125       --NUses;
4126     }
4127   }
4128
4129   // Found exactly the right number of uses?
4130   return NUses == 0;
4131 }
4132
4133
4134 /// hasAnyUseOfValue - Return true if there are any use of the indicated
4135 /// value. This method ignores uses of other values defined by this operation.
4136 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
4137   assert(Value < getNumValues() && "Bad value!");
4138
4139   if (use_empty()) return false;
4140
4141   SDOperand TheValue(const_cast<SDNode *>(this), Value);
4142
4143   SmallPtrSet<SDNode*, 32> UsersHandled;
4144
4145   for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
4146     SDNode *User = UI->getUser();
4147     if (User->getNumOperands() == 1 ||
4148         UsersHandled.insert(User))     // First time we've seen this?
4149       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
4150         if (User->getOperand(i) == TheValue) {
4151           return true;
4152         }
4153   }
4154
4155   return false;
4156 }
4157
4158
4159 /// isOnlyUseOf - Return true if this node is the only use of N.
4160 ///
4161 bool SDNode::isOnlyUseOf(SDNode *N) const {
4162   bool Seen = false;
4163   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
4164     SDNode *User = I->getUser();
4165     if (User == this)
4166       Seen = true;
4167     else
4168       return false;
4169   }
4170
4171   return Seen;
4172 }
4173
4174 /// isOperand - Return true if this node is an operand of N.
4175 ///
4176 bool SDOperand::isOperandOf(SDNode *N) const {
4177   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
4178     if (*this == N->getOperand(i))
4179       return true;
4180   return false;
4181 }
4182
4183 bool SDNode::isOperandOf(SDNode *N) const {
4184   for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
4185     if (this == N->OperandList[i].getVal())
4186       return true;
4187   return false;
4188 }
4189
4190 /// reachesChainWithoutSideEffects - Return true if this operand (which must
4191 /// be a chain) reaches the specified operand without crossing any
4192 /// side-effecting instructions.  In practice, this looks through token
4193 /// factors and non-volatile loads.  In order to remain efficient, this only
4194 /// looks a couple of nodes in, it does not do an exhaustive search.
4195 bool SDOperand::reachesChainWithoutSideEffects(SDOperand Dest,
4196                                                unsigned Depth) const {
4197   if (*this == Dest) return true;
4198
4199   // Don't search too deeply, we just want to be able to see through
4200   // TokenFactor's etc.
4201   if (Depth == 0) return false;
4202
4203   // If this is a token factor, all inputs to the TF happen in parallel.  If any
4204   // of the operands of the TF reach dest, then we can do the xform.
4205   if (getOpcode() == ISD::TokenFactor) {
4206     for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
4207       if (getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
4208         return true;
4209     return false;
4210   }
4211
4212   // Loads don't have side effects, look through them.
4213   if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
4214     if (!Ld->isVolatile())
4215       return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
4216   }
4217   return false;
4218 }
4219
4220
4221 static void findPredecessor(SDNode *N, const SDNode *P, bool &found,
4222                             SmallPtrSet<SDNode *, 32> &Visited) {
4223   if (found || !Visited.insert(N))
4224     return;
4225
4226   for (unsigned i = 0, e = N->getNumOperands(); !found && i != e; ++i) {
4227     SDNode *Op = N->getOperand(i).Val;
4228     if (Op == P) {
4229       found = true;
4230       return;
4231     }
4232     findPredecessor(Op, P, found, Visited);
4233   }
4234 }
4235
4236 /// isPredecessorOf - Return true if this node is a predecessor of N. This node
4237 /// is either an operand of N or it can be reached by recursively traversing
4238 /// up the operands.
4239 /// NOTE: this is an expensive method. Use it carefully.
4240 bool SDNode::isPredecessorOf(SDNode *N) const {
4241   SmallPtrSet<SDNode *, 32> Visited;
4242   bool found = false;
4243   findPredecessor(N, this, found, Visited);
4244   return found;
4245 }
4246
4247 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
4248   assert(Num < NumOperands && "Invalid child # of SDNode!");
4249   return cast<ConstantSDNode>(OperandList[Num])->getValue();
4250 }
4251
4252 std::string SDNode::getOperationName(const SelectionDAG *G) const {
4253   switch (getOpcode()) {
4254   default:
4255     if (getOpcode() < ISD::BUILTIN_OP_END)
4256       return "<<Unknown DAG Node>>";
4257     else {
4258       if (G) {
4259         if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
4260           if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
4261             return TII->get(getOpcode()-ISD::BUILTIN_OP_END).getName();
4262
4263         TargetLowering &TLI = G->getTargetLoweringInfo();
4264         const char *Name =
4265           TLI.getTargetNodeName(getOpcode());
4266         if (Name) return Name;
4267       }
4268
4269       return "<<Unknown Target Node>>";
4270     }
4271
4272   case ISD::PREFETCH:      return "Prefetch";
4273   case ISD::MEMBARRIER:    return "MemBarrier";
4274   case ISD::ATOMIC_LCS:    return "AtomicLCS";
4275   case ISD::ATOMIC_LAS:    return "AtomicLAS";
4276   case ISD::ATOMIC_LSS:    return "AtomicLSS";
4277   case ISD::ATOMIC_LOAD_AND:  return "AtomicLoadAnd";
4278   case ISD::ATOMIC_LOAD_OR:   return "AtomicLoadOr";
4279   case ISD::ATOMIC_LOAD_XOR:  return "AtomicLoadXor";
4280   case ISD::ATOMIC_LOAD_MIN:  return "AtomicLoadMin";
4281   case ISD::ATOMIC_LOAD_MAX:  return "AtomicLoadMax";
4282   case ISD::ATOMIC_LOAD_UMIN: return "AtomicLoadUMin";
4283   case ISD::ATOMIC_LOAD_UMAX: return "AtomicLoadUMax";
4284   case ISD::ATOMIC_SWAP:   return "AtomicSWAP";
4285   case ISD::PCMARKER:      return "PCMarker";
4286   case ISD::READCYCLECOUNTER: return "ReadCycleCounter";
4287   case ISD::SRCVALUE:      return "SrcValue";
4288   case ISD::MEMOPERAND:    return "MemOperand";
4289   case ISD::EntryToken:    return "EntryToken";
4290   case ISD::TokenFactor:   return "TokenFactor";
4291   case ISD::AssertSext:    return "AssertSext";
4292   case ISD::AssertZext:    return "AssertZext";
4293
4294   case ISD::STRING:        return "String";
4295   case ISD::BasicBlock:    return "BasicBlock";
4296   case ISD::ARG_FLAGS:     return "ArgFlags";
4297   case ISD::VALUETYPE:     return "ValueType";
4298   case ISD::Register:      return "Register";
4299
4300   case ISD::Constant:      return "Constant";
4301   case ISD::ConstantFP:    return "ConstantFP";
4302   case ISD::GlobalAddress: return "GlobalAddress";
4303   case ISD::GlobalTLSAddress: return "GlobalTLSAddress";
4304   case ISD::FrameIndex:    return "FrameIndex";
4305   case ISD::JumpTable:     return "JumpTable";
4306   case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE";
4307   case ISD::RETURNADDR: return "RETURNADDR";
4308   case ISD::FRAMEADDR: return "FRAMEADDR";
4309   case ISD::FRAME_TO_ARGS_OFFSET: return "FRAME_TO_ARGS_OFFSET";
4310   case ISD::EXCEPTIONADDR: return "EXCEPTIONADDR";
4311   case ISD::EHSELECTION: return "EHSELECTION";
4312   case ISD::EH_RETURN: return "EH_RETURN";
4313   case ISD::ConstantPool:  return "ConstantPool";
4314   case ISD::ExternalSymbol: return "ExternalSymbol";
4315   case ISD::INTRINSIC_WO_CHAIN: {
4316     unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue();
4317     return Intrinsic::getName((Intrinsic::ID)IID);
4318   }
4319   case ISD::INTRINSIC_VOID:
4320   case ISD::INTRINSIC_W_CHAIN: {
4321     unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue();
4322     return Intrinsic::getName((Intrinsic::ID)IID);
4323   }
4324
4325   case ISD::BUILD_VECTOR:   return "BUILD_VECTOR";
4326   case ISD::TargetConstant: return "TargetConstant";
4327   case ISD::TargetConstantFP:return "TargetConstantFP";
4328   case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
4329   case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress";
4330   case ISD::TargetFrameIndex: return "TargetFrameIndex";
4331   case ISD::TargetJumpTable:  return "TargetJumpTable";
4332   case ISD::TargetConstantPool:  return "TargetConstantPool";
4333   case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
4334
4335   case ISD::CopyToReg:     return "CopyToReg";
4336   case ISD::CopyFromReg:   return "CopyFromReg";
4337   case ISD::UNDEF:         return "undef";
4338   case ISD::MERGE_VALUES:  return "merge_values";
4339   case ISD::INLINEASM:     return "inlineasm";
4340   case ISD::LABEL:         return "label";
4341   case ISD::DECLARE:       return "declare";
4342   case ISD::HANDLENODE:    return "handlenode";
4343   case ISD::FORMAL_ARGUMENTS: return "formal_arguments";
4344   case ISD::CALL:          return "call";
4345
4346   // Unary operators
4347   case ISD::FABS:   return "fabs";
4348   case ISD::FNEG:   return "fneg";
4349   case ISD::FSQRT:  return "fsqrt";
4350   case ISD::FSIN:   return "fsin";
4351   case ISD::FCOS:   return "fcos";
4352   case ISD::FPOWI:  return "fpowi";
4353   case ISD::FPOW:   return "fpow";
4354
4355   // Binary operators
4356   case ISD::ADD:    return "add";
4357   case ISD::SUB:    return "sub";
4358   case ISD::MUL:    return "mul";
4359   case ISD::MULHU:  return "mulhu";
4360   case ISD::MULHS:  return "mulhs";
4361   case ISD::SDIV:   return "sdiv";
4362   case ISD::UDIV:   return "udiv";
4363   case ISD::SREM:   return "srem";
4364   case ISD::UREM:   return "urem";
4365   case ISD::SMUL_LOHI:  return "smul_lohi";
4366   case ISD::UMUL_LOHI:  return "umul_lohi";
4367   case ISD::SDIVREM:    return "sdivrem";
4368   case ISD::UDIVREM:    return "divrem";
4369   case ISD::AND:    return "and";
4370   case ISD::OR:     return "or";
4371   case ISD::XOR:    return "xor";
4372   case ISD::SHL:    return "shl";
4373   case ISD::SRA:    return "sra";
4374   case ISD::SRL:    return "srl";
4375   case ISD::ROTL:   return "rotl";
4376   case ISD::ROTR:   return "rotr";
4377   case ISD::FADD:   return "fadd";
4378   case ISD::FSUB:   return "fsub";
4379   case ISD::FMUL:   return "fmul";
4380   case ISD::FDIV:   return "fdiv";
4381   case ISD::FREM:   return "frem";
4382   case ISD::FCOPYSIGN: return "fcopysign";
4383   case ISD::FGETSIGN:  return "fgetsign";
4384
4385   case ISD::SETCC:       return "setcc";
4386   case ISD::SELECT:      return "select";
4387   case ISD::SELECT_CC:   return "select_cc";
4388   case ISD::INSERT_VECTOR_ELT:   return "insert_vector_elt";
4389   case ISD::EXTRACT_VECTOR_ELT:  return "extract_vector_elt";
4390   case ISD::CONCAT_VECTORS:      return "concat_vectors";
4391   case ISD::EXTRACT_SUBVECTOR:   return "extract_subvector";
4392   case ISD::SCALAR_TO_VECTOR:    return "scalar_to_vector";
4393   case ISD::VECTOR_SHUFFLE:      return "vector_shuffle";
4394   case ISD::CARRY_FALSE:         return "carry_false";
4395   case ISD::ADDC:        return "addc";
4396   case ISD::ADDE:        return "adde";
4397   case ISD::SUBC:        return "subc";
4398   case ISD::SUBE:        return "sube";
4399   case ISD::SHL_PARTS:   return "shl_parts";
4400   case ISD::SRA_PARTS:   return "sra_parts";
4401   case ISD::SRL_PARTS:   return "srl_parts";
4402
4403   case ISD::EXTRACT_SUBREG:     return "extract_subreg";
4404   case ISD::INSERT_SUBREG:      return "insert_subreg";
4405
4406   // Conversion operators.
4407   case ISD::SIGN_EXTEND: return "sign_extend";
4408   case ISD::ZERO_EXTEND: return "zero_extend";
4409   case ISD::ANY_EXTEND:  return "any_extend";
4410   case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
4411   case ISD::TRUNCATE:    return "truncate";
4412   case ISD::FP_ROUND:    return "fp_round";
4413   case ISD::FLT_ROUNDS_: return "flt_rounds";
4414   case ISD::FP_ROUND_INREG: return "fp_round_inreg";
4415   case ISD::FP_EXTEND:   return "fp_extend";
4416
4417   case ISD::SINT_TO_FP:  return "sint_to_fp";
4418   case ISD::UINT_TO_FP:  return "uint_to_fp";
4419   case ISD::FP_TO_SINT:  return "fp_to_sint";
4420   case ISD::FP_TO_UINT:  return "fp_to_uint";
4421   case ISD::BIT_CONVERT: return "bit_convert";
4422
4423     // Control flow instructions
4424   case ISD::BR:      return "br";
4425   case ISD::BRIND:   return "brind";
4426   case ISD::BR_JT:   return "br_jt";
4427   case ISD::BRCOND:  return "brcond";
4428   case ISD::BR_CC:   return "br_cc";
4429   case ISD::RET:     return "ret";
4430   case ISD::CALLSEQ_START:  return "callseq_start";
4431   case ISD::CALLSEQ_END:    return "callseq_end";
4432
4433     // Other operators
4434   case ISD::LOAD:               return "load";
4435   case ISD::STORE:              return "store";
4436   case ISD::VAARG:              return "vaarg";
4437   case ISD::VACOPY:             return "vacopy";
4438   case ISD::VAEND:              return "vaend";
4439   case ISD::VASTART:            return "vastart";
4440   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
4441   case ISD::EXTRACT_ELEMENT:    return "extract_element";
4442   case ISD::BUILD_PAIR:         return "build_pair";
4443   case ISD::STACKSAVE:          return "stacksave";
4444   case ISD::STACKRESTORE:       return "stackrestore";
4445   case ISD::TRAP:               return "trap";
4446
4447   // Bit manipulation
4448   case ISD::BSWAP:   return "bswap";
4449   case ISD::CTPOP:   return "ctpop";
4450   case ISD::CTTZ:    return "cttz";
4451   case ISD::CTLZ:    return "ctlz";
4452
4453   // Debug info
4454   case ISD::LOCATION: return "location";
4455   case ISD::DEBUG_LOC: return "debug_loc";
4456
4457   // Trampolines
4458   case ISD::TRAMPOLINE: return "trampoline";
4459
4460   case ISD::CONDCODE:
4461     switch (cast<CondCodeSDNode>(this)->get()) {
4462     default: assert(0 && "Unknown setcc condition!");
4463     case ISD::SETOEQ:  return "setoeq";
4464     case ISD::SETOGT:  return "setogt";
4465     case ISD::SETOGE:  return "setoge";
4466     case ISD::SETOLT:  return "setolt";
4467     case ISD::SETOLE:  return "setole";
4468     case ISD::SETONE:  return "setone";
4469
4470     case ISD::SETO:    return "seto";
4471     case ISD::SETUO:   return "setuo";
4472     case ISD::SETUEQ:  return "setue";
4473     case ISD::SETUGT:  return "setugt";
4474     case ISD::SETUGE:  return "setuge";
4475     case ISD::SETULT:  return "setult";
4476     case ISD::SETULE:  return "setule";
4477     case ISD::SETUNE:  return "setune";
4478
4479     case ISD::SETEQ:   return "seteq";
4480     case ISD::SETGT:   return "setgt";
4481     case ISD::SETGE:   return "setge";
4482     case ISD::SETLT:   return "setlt";
4483     case ISD::SETLE:   return "setle";
4484     case ISD::SETNE:   return "setne";
4485     }
4486   }
4487 }
4488
4489 const char *SDNode::getIndexedModeName(ISD::MemIndexedMode AM) {
4490   switch (AM) {
4491   default:
4492     return "";
4493   case ISD::PRE_INC:
4494     return "<pre-inc>";
4495   case ISD::PRE_DEC:
4496     return "<pre-dec>";
4497   case ISD::POST_INC:
4498     return "<post-inc>";
4499   case ISD::POST_DEC:
4500     return "<post-dec>";
4501   }
4502 }
4503
4504 std::string ISD::ArgFlagsTy::getArgFlagsString() {
4505   std::string S = "< ";
4506
4507   if (isZExt())
4508     S += "zext ";
4509   if (isSExt())
4510     S += "sext ";
4511   if (isInReg())
4512     S += "inreg ";
4513   if (isSRet())
4514     S += "sret ";
4515   if (isByVal())
4516     S += "byval ";
4517   if (isNest())
4518     S += "nest ";
4519   if (getByValAlign())
4520     S += "byval-align:" + utostr(getByValAlign()) + " ";
4521   if (getOrigAlign())
4522     S += "orig-align:" + utostr(getOrigAlign()) + " ";
4523   if (getByValSize())
4524     S += "byval-size:" + utostr(getByValSize()) + " ";
4525   return S + ">";
4526 }
4527
4528 void SDNode::dump() const { dump(0); }
4529 void SDNode::dump(const SelectionDAG *G) const {
4530   cerr << (void*)this << ": ";
4531
4532   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
4533     if (i) cerr << ",";
4534     if (getValueType(i) == MVT::Other)
4535       cerr << "ch";
4536     else
4537       cerr << MVT::getValueTypeString(getValueType(i));
4538   }
4539   cerr << " = " << getOperationName(G);
4540
4541   cerr << " ";
4542   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
4543     if (i) cerr << ", ";
4544     cerr << (void*)getOperand(i).Val;
4545     if (unsigned RN = getOperand(i).ResNo)
4546       cerr << ":" << RN;
4547   }
4548
4549   if (!isTargetOpcode() && getOpcode() == ISD::VECTOR_SHUFFLE) {
4550     SDNode *Mask = getOperand(2).Val;
4551     cerr << "<";
4552     for (unsigned i = 0, e = Mask->getNumOperands(); i != e; ++i) {
4553       if (i) cerr << ",";
4554       if (Mask->getOperand(i).getOpcode() == ISD::UNDEF)
4555         cerr << "u";
4556       else
4557         cerr << cast<ConstantSDNode>(Mask->getOperand(i))->getValue();
4558     }
4559     cerr << ">";
4560   }
4561
4562   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
4563     cerr << "<" << CSDN->getValue() << ">";
4564   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
4565     if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEsingle)
4566       cerr << "<" << CSDN->getValueAPF().convertToFloat() << ">";
4567     else if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEdouble)
4568       cerr << "<" << CSDN->getValueAPF().convertToDouble() << ">";
4569     else {
4570       cerr << "<APFloat(";
4571       CSDN->getValueAPF().convertToAPInt().dump();
4572       cerr << ")>";
4573     }
4574   } else if (const GlobalAddressSDNode *GADN =
4575              dyn_cast<GlobalAddressSDNode>(this)) {
4576     int offset = GADN->getOffset();
4577     cerr << "<";
4578     WriteAsOperand(*cerr.stream(), GADN->getGlobal()) << ">";
4579     if (offset > 0)
4580       cerr << " + " << offset;
4581     else
4582       cerr << " " << offset;
4583   } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
4584     cerr << "<" << FIDN->getIndex() << ">";
4585   } else if (const JumpTableSDNode *JTDN = dyn_cast<JumpTableSDNode>(this)) {
4586     cerr << "<" << JTDN->getIndex() << ">";
4587   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
4588     int offset = CP->getOffset();
4589     if (CP->isMachineConstantPoolEntry())
4590       cerr << "<" << *CP->getMachineCPVal() << ">";
4591     else
4592       cerr << "<" << *CP->getConstVal() << ">";
4593     if (offset > 0)
4594       cerr << " + " << offset;
4595     else
4596       cerr << " " << offset;
4597   } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
4598     cerr << "<";
4599     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
4600     if (LBB)
4601       cerr << LBB->getName() << " ";
4602     cerr << (const void*)BBDN->getBasicBlock() << ">";
4603   } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
4604     if (G && R->getReg() &&
4605         TargetRegisterInfo::isPhysicalRegister(R->getReg())) {
4606       cerr << " " << G->getTarget().getRegisterInfo()->getName(R->getReg());
4607     } else {
4608       cerr << " #" << R->getReg();
4609     }
4610   } else if (const ExternalSymbolSDNode *ES =
4611              dyn_cast<ExternalSymbolSDNode>(this)) {
4612     cerr << "'" << ES->getSymbol() << "'";
4613   } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
4614     if (M->getValue())
4615       cerr << "<" << M->getValue() << ">";
4616     else
4617       cerr << "<null>";
4618   } else if (const MemOperandSDNode *M = dyn_cast<MemOperandSDNode>(this)) {
4619     if (M->MO.getValue())
4620       cerr << "<" << M->MO.getValue() << ":" << M->MO.getOffset() << ">";
4621     else
4622       cerr << "<null:" << M->MO.getOffset() << ">";
4623   } else if (const ARG_FLAGSSDNode *N = dyn_cast<ARG_FLAGSSDNode>(this)) {
4624     cerr << N->getArgFlags().getArgFlagsString();
4625   } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
4626     cerr << ":" << MVT::getValueTypeString(N->getVT());
4627   } else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) {
4628     const Value *SrcValue = LD->getSrcValue();
4629     int SrcOffset = LD->getSrcValueOffset();
4630     cerr << " <";
4631     if (SrcValue)
4632       cerr << SrcValue;
4633     else
4634       cerr << "null";
4635     cerr << ":" << SrcOffset << ">";
4636
4637     bool doExt = true;
4638     switch (LD->getExtensionType()) {
4639     default: doExt = false; break;
4640     case ISD::EXTLOAD:
4641       cerr << " <anyext ";
4642       break;
4643     case ISD::SEXTLOAD:
4644       cerr << " <sext ";
4645       break;
4646     case ISD::ZEXTLOAD:
4647       cerr << " <zext ";
4648       break;
4649     }
4650     if (doExt)
4651       cerr << MVT::getValueTypeString(LD->getMemoryVT()) << ">";
4652
4653     const char *AM = getIndexedModeName(LD->getAddressingMode());
4654     if (*AM)
4655       cerr << " " << AM;
4656     if (LD->isVolatile())
4657       cerr << " <volatile>";
4658     cerr << " alignment=" << LD->getAlignment();
4659   } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) {
4660     const Value *SrcValue = ST->getSrcValue();
4661     int SrcOffset = ST->getSrcValueOffset();
4662     cerr << " <";
4663     if (SrcValue)
4664       cerr << SrcValue;
4665     else
4666       cerr << "null";
4667     cerr << ":" << SrcOffset << ">";
4668
4669     if (ST->isTruncatingStore())
4670       cerr << " <trunc "
4671            << MVT::getValueTypeString(ST->getMemoryVT()) << ">";
4672
4673     const char *AM = getIndexedModeName(ST->getAddressingMode());
4674     if (*AM)
4675       cerr << " " << AM;
4676     if (ST->isVolatile())
4677       cerr << " <volatile>";
4678     cerr << " alignment=" << ST->getAlignment();
4679   }
4680 }
4681
4682 static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
4683   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
4684     if (N->getOperand(i).Val->hasOneUse())
4685       DumpNodes(N->getOperand(i).Val, indent+2, G);
4686     else
4687       cerr << "\n" << std::string(indent+2, ' ')
4688            << (void*)N->getOperand(i).Val << ": <multiple use>";
4689
4690
4691   cerr << "\n" << std::string(indent, ' ');
4692   N->dump(G);
4693 }
4694
4695 void SelectionDAG::dump() const {
4696   cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
4697   std::vector<const SDNode*> Nodes;
4698   for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
4699        I != E; ++I)
4700     Nodes.push_back(I);
4701
4702   std::sort(Nodes.begin(), Nodes.end());
4703
4704   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
4705     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
4706       DumpNodes(Nodes[i], 2, this);
4707   }
4708
4709   if (getRoot().Val) DumpNodes(getRoot().Val, 2, this);
4710
4711   cerr << "\n\n";
4712 }
4713
4714 const Type *ConstantPoolSDNode::getType() const {
4715   if (isMachineConstantPoolEntry())
4716     return Val.MachineCPVal->getType();
4717   return Val.ConstVal->getType();
4718 }