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