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