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