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