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