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