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