lib/CodeGen/SelectionDAG/SelectionDAG.cpp

   1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the SelectionDAG class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #include "llvm/CodeGen/SelectionDAG.h"
  14 #include "llvm/Constants.h"
  15 #include "llvm/GlobalAlias.h"
  16 #include "llvm/GlobalVariable.h"
  17 #include "llvm/Intrinsics.h"
  18 #include "llvm/DerivedTypes.h"
  19 #include "llvm/Assembly/Writer.h"
  20 #include "llvm/CallingConv.h"
  21 #include "llvm/CodeGen/MachineBasicBlock.h"
  22 #include "llvm/CodeGen/MachineConstantPool.h"
  23 #include "llvm/CodeGen/MachineFrameInfo.h"
  24 #include "llvm/CodeGen/MachineModuleInfo.h"
  25 #include "llvm/CodeGen/PseudoSourceValue.h"
  26 #include "llvm/Support/MathExtras.h"
  27 #include "llvm/Target/TargetRegisterInfo.h"
  28 #include "llvm/Target/TargetData.h"
  29 #include "llvm/Target/TargetLowering.h"
  30 #include "llvm/Target/TargetInstrInfo.h"
  31 #include "llvm/Target/TargetMachine.h"
  32 #include "llvm/ADT/SetVector.h"
  33 #include "llvm/ADT/SmallPtrSet.h"
  34 #include "llvm/ADT/SmallSet.h"
  35 #include "llvm/ADT/SmallVector.h"
  36 #include "llvm/ADT/StringExtras.h"
  37 #include <algorithm>
  38 #include <cmath>
  39 using namespace llvm;
  40
  41 /// makeVTList - Return an instance of the SDVTList struct initialized with the
  42 /// specified members.
  43 static SDVTList makeVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
  44   SDVTList Res = {VTs, NumVTs};
  45   return Res;
  46 }
  47
  48 static const fltSemantics *MVTToAPFloatSemantics(MVT::ValueType VT) {
  49   switch (VT) {
  50   default: assert(0 && "Unknown FP format");
  51   case MVT::f32:     return &APFloat::IEEEsingle;
  52   case MVT::f64:     return &APFloat::IEEEdouble;
  53   case MVT::f80:     return &APFloat::x87DoubleExtended;
  54   case MVT::f128:    return &APFloat::IEEEquad;
  55   case MVT::ppcf128: return &APFloat::PPCDoubleDouble;
  56   }
  57 }
  58
  59 SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {}
  60
  61 //===----------------------------------------------------------------------===//
  62 //                              ConstantFPSDNode Class
  63 //===----------------------------------------------------------------------===//
  64
  65 /// isExactlyValue - We don't rely on operator== working on double values, as
  66 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
  67 /// As such, this method can be used to do an exact bit-for-bit comparison of
  68 /// two floating point values.
  69 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const {
  70   return Value.bitwiseIsEqual(V);
  71 }
  72
  73 bool ConstantFPSDNode::isValueValidForType(MVT::ValueType VT,
  74                                            const APFloat& Val) {
  75   assert(MVT::isFloatingPoint(VT) && "Can only convert between FP types");
  76
  77   // PPC long double cannot be converted to any other type.
  78   if (VT == MVT::ppcf128 ||
  79       &Val.getSemantics() == &APFloat::PPCDoubleDouble)
  80     return false;
  81
  82   // convert modifies in place, so make a copy.
  83   APFloat Val2 = APFloat(Val);
  84   return Val2.convert(*MVTToAPFloatSemantics(VT),
  85                       APFloat::rmNearestTiesToEven) == APFloat::opOK;
  86 }
  87
  88 //===----------------------------------------------------------------------===//
  89 //                              ISD Namespace
  90 //===----------------------------------------------------------------------===//
  91
  92 /// isBuildVectorAllOnes - Return true if the specified node is a
  93 /// BUILD_VECTOR where all of the elements are ~0 or undef.
  94 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
  95   // Look through a bit convert.
  96   if (N->getOpcode() == ISD::BIT_CONVERT)
  97     N = N->getOperand(0).Val;
  98
  99   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
 100
 101   unsigned i = 0, e = N->getNumOperands();
 102
 103   // Skip over all of the undef values.
 104   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
 105     ++i;
 106
 107   // Do not accept an all-undef vector.
 108   if (i == e) return false;
 109
 110   // Do not accept build_vectors that aren't all constants or which have non-~0
 111   // elements.
 112   SDOperand NotZero = N->getOperand(i);
 113   if (isa<ConstantSDNode>(NotZero)) {
 114     if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue())
 115       return false;
 116   } else if (isa<ConstantFPSDNode>(NotZero)) {
 117     if (!cast<ConstantFPSDNode>(NotZero)->getValueAPF().
 118                 convertToAPInt().isAllOnesValue())
 119       return false;
 120   } else
 121     return false;
 122
 123   // Okay, we have at least one ~0 value, check to see if the rest match or are
 124   // undefs.
 125   for (++i; i != e; ++i)
 126     if (N->getOperand(i) != NotZero &&
 127         N->getOperand(i).getOpcode() != ISD::UNDEF)
 128       return false;
 129   return true;
 130 }
 131
 132
 133 /// isBuildVectorAllZeros - Return true if the specified node is a
 134 /// BUILD_VECTOR where all of the elements are 0 or undef.
 135 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
 136   // Look through a bit convert.
 137   if (N->getOpcode() == ISD::BIT_CONVERT)
 138     N = N->getOperand(0).Val;
 139
 140   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
 141
 142   unsigned i = 0, e = N->getNumOperands();
 143
 144   // Skip over all of the undef values.
 145   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
 146     ++i;
 147
 148   // Do not accept an all-undef vector.
 149   if (i == e) return false;
 150
 151   // Do not accept build_vectors that aren't all constants or which have non-~0
 152   // elements.
 153   SDOperand Zero = N->getOperand(i);
 154   if (isa<ConstantSDNode>(Zero)) {
 155     if (!cast<ConstantSDNode>(Zero)->isNullValue())
 156       return false;
 157   } else if (isa<ConstantFPSDNode>(Zero)) {
 158     if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero())
 159       return false;
 160   } else
 161     return false;
 162
 163   // Okay, we have at least one ~0 value, check to see if the rest match or are
 164   // undefs.
 165   for (++i; i != e; ++i)
 166     if (N->getOperand(i) != Zero &&
 167         N->getOperand(i).getOpcode() != ISD::UNDEF)
 168       return false;
 169   return true;
 170 }
 171
 172 /// isScalarToVector - Return true if the specified node is a
 173 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low
 174 /// element is not an undef.
 175 bool ISD::isScalarToVector(const SDNode *N) {
 176   if (N->getOpcode() == ISD::SCALAR_TO_VECTOR)
 177     return true;
 178
 179   if (N->getOpcode() != ISD::BUILD_VECTOR)
 180     return false;
 181   if (N->getOperand(0).getOpcode() == ISD::UNDEF)
 182     return false;
 183   unsigned NumElems = N->getNumOperands();
 184   for (unsigned i = 1; i < NumElems; ++i) {
 185     SDOperand V = N->getOperand(i);
 186     if (V.getOpcode() != ISD::UNDEF)
 187       return false;
 188   }
 189   return true;
 190 }
 191
 192
 193 /// isDebugLabel - Return true if the specified node represents a debug
 194 /// label (i.e. ISD::LABEL or TargetInstrInfo::LABEL node and third operand
 195 /// is 0).
 196 bool ISD::isDebugLabel(const SDNode *N) {
 197   SDOperand Zero;
 198   if (N->getOpcode() == ISD::LABEL)
 199     Zero = N->getOperand(2);
 200   else if (N->isTargetOpcode() &&
 201            N->getTargetOpcode() == TargetInstrInfo::LABEL)
 202     // Chain moved to last operand.
 203     Zero = N->getOperand(1);
 204   else
 205     return false;
 206   return isa<ConstantSDNode>(Zero) && cast<ConstantSDNode>(Zero)->isNullValue();
 207 }
 208
 209 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
 210 /// when given the operation for (X op Y).
 211 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
 212   // To perform this operation, we just need to swap the L and G bits of the
 213   // operation.
 214   unsigned OldL = (Operation >> 2) & 1;
 215   unsigned OldG = (Operation >> 1) & 1;
 216   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
 217                        (OldL << 1) |       // New G bit
 218                        (OldG << 2));        // New L bit.
 219 }
 220
 221 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
 222 /// 'op' is a valid SetCC operation.
 223 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
 224   unsigned Operation = Op;
 225   if (isInteger)
 226     Operation ^= 7;   // Flip L, G, E bits, but not U.
 227   else
 228     Operation ^= 15;  // Flip all of the condition bits.
 229   if (Operation > ISD::SETTRUE2)
 230     Operation &= ~8;     // Don't let N and U bits get set.
 231   return ISD::CondCode(Operation);
 232 }
 233
 234
 235 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
 236 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
 237 /// if the operation does not depend on the sign of the input (setne and seteq).
 238 static int isSignedOp(ISD::CondCode Opcode) {
 239   switch (Opcode) {
 240   default: assert(0 && "Illegal integer setcc operation!");
 241   case ISD::SETEQ:
 242   case ISD::SETNE: return 0;
 243   case ISD::SETLT:
 244   case ISD::SETLE:
 245   case ISD::SETGT:
 246   case ISD::SETGE: return 1;
 247   case ISD::SETULT:
 248   case ISD::SETULE:
 249   case ISD::SETUGT:
 250   case ISD::SETUGE: return 2;
 251   }
 252 }
 253
 254 /// getSetCCOrOperation - Return the result of a logical OR between different
 255 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
 256 /// returns SETCC_INVALID if it is not possible to represent the resultant
 257 /// comparison.
 258 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 259                                        bool isInteger) {
 260   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 261     // Cannot fold a signed integer setcc with an unsigned integer setcc.
 262     return ISD::SETCC_INVALID;
 263
 264   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
 265
 266   // If the N and U bits get set then the resultant comparison DOES suddenly
 267   // care about orderedness, and is true when ordered.
 268   if (Op > ISD::SETTRUE2)
 269     Op &= ~16;     // Clear the U bit if the N bit is set.
 270
 271   // Canonicalize illegal integer setcc's.
 272   if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
 273     Op = ISD::SETNE;
 274
 275   return ISD::CondCode(Op);
 276 }
 277
 278 /// getSetCCAndOperation - Return the result of a logical AND between different
 279 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
 280 /// function returns zero if it is not possible to represent the resultant
 281 /// comparison.
 282 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 283                                         bool isInteger) {
 284   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 285     // Cannot fold a signed setcc with an unsigned setcc.
 286     return ISD::SETCC_INVALID;
 287
 288   // Combine all of the condition bits.
 289   ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
 290
 291   // Canonicalize illegal integer setcc's.
 292   if (isInteger) {
 293     switch (Result) {
 294     default: break;
 295     case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
 296     case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
 297     case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
 298     case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
 299     }
 300   }
 301
 302   return Result;
 303 }
 304
 305 const TargetMachine &SelectionDAG::getTarget() const {
 306   return TLI.getTargetMachine();
 307 }
 308
 309 //===----------------------------------------------------------------------===//
 310 //                           SDNode Profile Support
 311 //===----------------------------------------------------------------------===//
 312
 313 /// AddNodeIDOpcode - Add the node opcode to the NodeID data.
 314 ///
 315 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC)  {
 316   ID.AddInteger(OpC);
 317 }
 318
 319 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them
 320 /// solely with their pointer.
 321 void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) {
 322   ID.AddPointer(VTList.VTs);
 323 }
 324
 325 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data.
 326 ///
 327 static void AddNodeIDOperands(FoldingSetNodeID &ID,
 328                               SDOperandPtr Ops, unsigned NumOps) {
 329   for (; NumOps; --NumOps, ++Ops) {
 330     ID.AddPointer(Ops->Val);
 331     ID.AddInteger(Ops->ResNo);
 332   }
 333 }
 334
 335 static void AddNodeIDNode(FoldingSetNodeID &ID,
 336                           unsigned short OpC, SDVTList VTList,
 337                           SDOperandPtr OpList, unsigned N) {
 338   AddNodeIDOpcode(ID, OpC);
 339   AddNodeIDValueTypes(ID, VTList);
 340   AddNodeIDOperands(ID, OpList, N);
 341 }
 342
 343
 344 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID
 345 /// data.
 346 static void AddNodeIDNode(FoldingSetNodeID &ID, SDNode *N) {
 347   AddNodeIDOpcode(ID, N->getOpcode());
 348   // Add the return value info.
 349   AddNodeIDValueTypes(ID, N->getVTList());
 350   // Add the operand info.
 351   AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands());
 352
 353   // Handle SDNode leafs with special info.
 354   switch (N->getOpcode()) {
 355   default: break;  // Normal nodes don't need extra info.
 356   case ISD::ARG_FLAGS:
 357     ID.AddInteger(cast<ARG_FLAGSSDNode>(N)->getArgFlags().getRawBits());
 358     break;
 359   case ISD::TargetConstant:
 360   case ISD::Constant:
 361     ID.Add(cast<ConstantSDNode>(N)->getAPIntValue());
 362     break;
 363   case ISD::TargetConstantFP:
 364   case ISD::ConstantFP: {
 365     ID.Add(cast<ConstantFPSDNode>(N)->getValueAPF());
 366     break;
 367   }
 368   case ISD::TargetGlobalAddress:
 369   case ISD::GlobalAddress:
 370   case ISD::TargetGlobalTLSAddress:
 371   case ISD::GlobalTLSAddress: {
 372     GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N);
 373     ID.AddPointer(GA->getGlobal());
 374     ID.AddInteger(GA->getOffset());
 375     break;
 376   }
 377   case ISD::BasicBlock:
 378     ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock());
 379     break;
 380   case ISD::Register:
 381     ID.AddInteger(cast<RegisterSDNode>(N)->getReg());
 382     break;
 383   case ISD::SRCVALUE:
 384     ID.AddPointer(cast<SrcValueSDNode>(N)->getValue());
 385     break;
 386   case ISD::MEMOPERAND: {
 387     const MachineMemOperand &MO = cast<MemOperandSDNode>(N)->MO;
 388     ID.AddPointer(MO.getValue());
 389     ID.AddInteger(MO.getFlags());
 390     ID.AddInteger(MO.getOffset());
 391     ID.AddInteger(MO.getSize());
 392     ID.AddInteger(MO.getAlignment());
 393     break;
 394   }
 395   case ISD::FrameIndex:
 396   case ISD::TargetFrameIndex:
 397     ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex());
 398     break;
 399   case ISD::JumpTable:
 400   case ISD::TargetJumpTable:
 401     ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex());
 402     break;
 403   case ISD::ConstantPool:
 404   case ISD::TargetConstantPool: {
 405     ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N);
 406     ID.AddInteger(CP->getAlignment());
 407     ID.AddInteger(CP->getOffset());
 408     if (CP->isMachineConstantPoolEntry())
 409       CP->getMachineCPVal()->AddSelectionDAGCSEId(ID);
 410     else
 411       ID.AddPointer(CP->getConstVal());
 412     break;
 413   }
 414   case ISD::LOAD: {
 415     LoadSDNode *LD = cast<LoadSDNode>(N);
 416     ID.AddInteger(LD->getAddressingMode());
 417     ID.AddInteger(LD->getExtensionType());
 418     ID.AddInteger((unsigned int)(LD->getMemoryVT()));
 419     ID.AddInteger(LD->getAlignment());
 420     ID.AddInteger(LD->isVolatile());
 421     break;
 422   }
 423   case ISD::STORE: {
 424     StoreSDNode *ST = cast<StoreSDNode>(N);
 425     ID.AddInteger(ST->getAddressingMode());
 426     ID.AddInteger(ST->isTruncatingStore());
 427     ID.AddInteger((unsigned int)(ST->getMemoryVT()));
 428     ID.AddInteger(ST->getAlignment());
 429     ID.AddInteger(ST->isVolatile());
 430     break;
 431   }
 432   }
 433 }
 434
 435 //===----------------------------------------------------------------------===//
 436 //                              SelectionDAG Class
 437 //===----------------------------------------------------------------------===//
 438
 439 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
 440 /// SelectionDAG.
 441 void SelectionDAG::RemoveDeadNodes() {
 442   // Create a dummy node (which is not added to allnodes), that adds a reference
 443   // to the root node, preventing it from being deleted.
 444   HandleSDNode Dummy(getRoot());
 445
 446   SmallVector<SDNode*, 128> DeadNodes;
 447
 448   // Add all obviously-dead nodes to the DeadNodes worklist.
 449   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
 450     if (I->use_empty())
 451       DeadNodes.push_back(I);
 452
 453   // Process the worklist, deleting the nodes and adding their uses to the
 454   // worklist.
 455   while (!DeadNodes.empty()) {
 456     SDNode *N = DeadNodes.back();
 457     DeadNodes.pop_back();
 458
 459     // Take the node out of the appropriate CSE map.
 460     RemoveNodeFromCSEMaps(N);
 461
 462     // Next, brutally remove the operand list.  This is safe to do, as there are
 463     // no cycles in the graph.
 464     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
 465       SDNode *Operand = I->getVal();
 466       Operand->removeUser(std::distance(N->op_begin(), I), N);
 467
 468       // Now that we removed this operand, see if there are no uses of it left.
 469       if (Operand->use_empty())
 470         DeadNodes.push_back(Operand);
 471     }
 472     if (N->OperandsNeedDelete) {
 473       delete[] N->OperandList;
 474     }
 475     N->OperandList = 0;
 476     N->NumOperands = 0;
 477
 478     // Finally, remove N itself.
 479     AllNodes.erase(N);
 480   }
 481
 482   // If the root changed (e.g. it was a dead load, update the root).
 483   setRoot(Dummy.getValue());
 484 }
 485
 486 void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){
 487   SmallVector<SDNode*, 16> DeadNodes;
 488   DeadNodes.push_back(N);
 489
 490   // Process the worklist, deleting the nodes and adding their uses to the
 491   // worklist.
 492   while (!DeadNodes.empty()) {
 493     SDNode *N = DeadNodes.back();
 494     DeadNodes.pop_back();
 495
 496     if (UpdateListener)
 497       UpdateListener->NodeDeleted(N);
 498
 499     // Take the node out of the appropriate CSE map.
 500     RemoveNodeFromCSEMaps(N);
 501
 502     // Next, brutally remove the operand list.  This is safe to do, as there are
 503     // no cycles in the graph.
 504     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
 505       SDNode *Operand = I->getVal();
 506       Operand->removeUser(std::distance(N->op_begin(), I), N);
 507
 508       // Now that we removed this operand, see if there are no uses of it left.
 509       if (Operand->use_empty())
 510         DeadNodes.push_back(Operand);
 511     }
 512     if (N->OperandsNeedDelete) {
 513       delete[] N->OperandList;
 514     }
 515     N->OperandList = 0;
 516     N->NumOperands = 0;
 517
 518     // Finally, remove N itself.
 519     AllNodes.erase(N);
 520   }
 521 }
 522
 523 void SelectionDAG::DeleteNode(SDNode *N) {
 524   assert(N->use_empty() && "Cannot delete a node that is not dead!");
 525
 526   // First take this out of the appropriate CSE map.
 527   RemoveNodeFromCSEMaps(N);
 528
 529   // Finally, remove uses due to operands of this node, remove from the
 530   // AllNodes list, and delete the node.
 531   DeleteNodeNotInCSEMaps(N);
 532 }
 533
 534 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
 535
 536   // Remove it from the AllNodes list.
 537   AllNodes.remove(N);
 538
 539   // Drop all of the operands and decrement used nodes use counts.
 540   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
 541     I->getVal()->removeUser(std::distance(N->op_begin(), I), N);
 542   if (N->OperandsNeedDelete) {
 543     delete[] N->OperandList;
 544   }
 545   N->OperandList = 0;
 546   N->NumOperands = 0;
 547
 548   delete N;
 549 }
 550
 551 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
 552 /// correspond to it.  This is useful when we're about to delete or repurpose
 553 /// the node.  We don't want future request for structurally identical nodes
 554 /// to return N anymore.
 555 void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
 556   bool Erased = false;
 557   switch (N->getOpcode()) {
 558   case ISD::HANDLENODE: return;  // noop.
 559   case ISD::STRING:
 560     Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue());
 561     break;
 562   case ISD::CONDCODE:
 563     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
 564            "Cond code doesn't exist!");
 565     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
 566     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
 567     break;
 568   case ISD::ExternalSymbol:
 569     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 570     break;
 571   case ISD::TargetExternalSymbol:
 572     Erased =
 573       TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 574     break;
 575   case ISD::VALUETYPE: {
 576     MVT::ValueType VT = cast<VTSDNode>(N)->getVT();
 577     if (MVT::isExtendedVT(VT)) {
 578       Erased = ExtendedValueTypeNodes.erase(VT);
 579     } else {
 580       Erased = ValueTypeNodes[VT] != 0;
 581       ValueTypeNodes[VT] = 0;
 582     }
 583     break;
 584   }
 585   default:
 586     // Remove it from the CSE Map.
 587     Erased = CSEMap.RemoveNode(N);
 588     break;
 589   }
 590 #ifndef NDEBUG
 591   // Verify that the node was actually in one of the CSE maps, unless it has a
 592   // flag result (which cannot be CSE'd) or is one of the special cases that are
 593   // not subject to CSE.
 594   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag &&
 595       !N->isTargetOpcode()) {
 596     N->dump(this);
 597     cerr << "\n";
 598     assert(0 && "Node is not in map!");
 599   }
 600 #endif
 601 }
 602
 603 /// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps.  It
 604 /// has been taken out and modified in some way.  If the specified node already
 605 /// exists in the CSE maps, do not modify the maps, but return the existing node
 606 /// instead.  If it doesn't exist, add it and return null.
 607 ///
 608 SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
 609   assert(N->getNumOperands() && "This is a leaf node!");
 610   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 611     return 0;    // Never add these nodes.
 612
 613   // Check that remaining values produced are not flags.
 614   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 615     if (N->getValueType(i) == MVT::Flag)
 616       return 0;   // Never CSE anything that produces a flag.
 617
 618   SDNode *New = CSEMap.GetOrInsertNode(N);
 619   if (New != N) return New;  // Node already existed.
 620   return 0;
 621 }
 622
 623 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 624 /// were replaced with those specified.  If this node is never memoized,
 625 /// return null, otherwise return a pointer to the slot it would take.  If a
 626 /// node already exists with these operands, the slot will be non-null.
 627 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op,
 628                                            void *&InsertPos) {
 629   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 630     return 0;    // Never add these nodes.
 631
 632   // Check that remaining values produced are not flags.
 633   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 634     if (N->getValueType(i) == MVT::Flag)
 635       return 0;   // Never CSE anything that produces a flag.
 636
 637   SDOperand Ops[] = { Op };
 638   FoldingSetNodeID ID;
 639   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1);
 640   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 641 }
 642
 643 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 644 /// were replaced with those specified.  If this node is never memoized,
 645 /// return null, otherwise return a pointer to the slot it would take.  If a
 646 /// node already exists with these operands, the slot will be non-null.
 647 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
 648                                            SDOperand Op1, SDOperand Op2,
 649                                            void *&InsertPos) {
 650   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 651     return 0;    // Never add these nodes.
 652
 653   // Check that remaining values produced are not flags.
 654   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 655     if (N->getValueType(i) == MVT::Flag)
 656       return 0;   // Never CSE anything that produces a flag.
 657
 658   SDOperand Ops[] = { Op1, Op2 };
 659   FoldingSetNodeID ID;
 660   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2);
 661   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 662 }
 663
 664
 665 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 666 /// were replaced with those specified.  If this node is never memoized,
 667 /// return null, otherwise return a pointer to the slot it would take.  If a
 668 /// node already exists with these operands, the slot will be non-null.
 669 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
 670                                            SDOperandPtr Ops,unsigned NumOps,
 671                                            void *&InsertPos) {
 672   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 673     return 0;    // Never add these nodes.
 674
 675   // Check that remaining values produced are not flags.
 676   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 677     if (N->getValueType(i) == MVT::Flag)
 678       return 0;   // Never CSE anything that produces a flag.
 679
 680   FoldingSetNodeID ID;
 681   AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps);
 682
 683   if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) {
 684     ID.AddInteger(LD->getAddressingMode());
 685     ID.AddInteger(LD->getExtensionType());
 686     ID.AddInteger((unsigned int)(LD->getMemoryVT()));
 687     ID.AddInteger(LD->getAlignment());
 688     ID.AddInteger(LD->isVolatile());
 689   } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) {
 690     ID.AddInteger(ST->getAddressingMode());
 691     ID.AddInteger(ST->isTruncatingStore());
 692     ID.AddInteger((unsigned int)(ST->getMemoryVT()));
 693     ID.AddInteger(ST->getAlignment());
 694     ID.AddInteger(ST->isVolatile());
 695   }
 696
 697   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 698 }
 699
 700
 701 SelectionDAG::~SelectionDAG() {
 702   while (!AllNodes.empty()) {
 703     SDNode *N = AllNodes.begin();
 704     N->SetNextInBucket(0);
 705     if (N->OperandsNeedDelete) {
 706       delete [] N->OperandList;
 707     }
 708     N->OperandList = 0;
 709     N->NumOperands = 0;
 710     AllNodes.pop_front();
 711   }
 712 }
 713
 714 SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) {
 715   if (Op.getValueType() == VT) return Op;
 716   APInt Imm = APInt::getLowBitsSet(Op.getValueSizeInBits(),
 717                                    MVT::getSizeInBits(VT));
 718   return getNode(ISD::AND, Op.getValueType(), Op,
 719                  getConstant(Imm, Op.getValueType()));
 720 }
 721
 722 SDOperand SelectionDAG::getString(const std::string &Val) {
 723   StringSDNode *&N = StringNodes[Val];
 724   if (!N) {
 725     N = new StringSDNode(Val);
 726     AllNodes.push_back(N);
 727   }
 728   return SDOperand(N, 0);
 729 }
 730
 731 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT, bool isT) {
 732   MVT::ValueType EltVT =
 733     MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT;
 734
 735   return getConstant(APInt(MVT::getSizeInBits(EltVT), Val), VT, isT);
 736 }
 737
 738 SDOperand SelectionDAG::getConstant(const APInt &Val, MVT::ValueType VT, bool isT) {
 739   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 740
 741   MVT::ValueType EltVT =
 742     MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT;
 743
 744   assert(Val.getBitWidth() == MVT::getSizeInBits(EltVT) &&
 745          "APInt size does not match type size!");
 746
 747   unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant;
 748   FoldingSetNodeID ID;
 749   AddNodeIDNode(ID, Opc, getVTList(EltVT), (SDOperand*)0, 0);
 750   ID.Add(Val);
 751   void *IP = 0;
 752   SDNode *N = NULL;
 753   if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
 754     if (!MVT::isVector(VT))
 755       return SDOperand(N, 0);
 756   if (!N) {
 757     N = new ConstantSDNode(isT, Val, EltVT);
 758     CSEMap.InsertNode(N, IP);
 759     AllNodes.push_back(N);
 760   }
 761
 762   SDOperand Result(N, 0);
 763   if (MVT::isVector(VT)) {
 764     SmallVector<SDOperand, 8> Ops;
 765     Ops.assign(MVT::getVectorNumElements(VT), Result);
 766     Result = getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
 767   }
 768   return Result;
 769 }
 770
 771 SDOperand SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) {
 772   return getConstant(Val, TLI.getPointerTy(), isTarget);
 773 }
 774
 775
 776 SDOperand SelectionDAG::getConstantFP(const APFloat& V, MVT::ValueType VT,
 777                                       bool isTarget) {
 778   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
 779
 780   MVT::ValueType EltVT =
 781     MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT;
 782
 783   // Do the map lookup using the actual bit pattern for the floating point
 784   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
 785   // we don't have issues with SNANs.
 786   unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP;
 787   FoldingSetNodeID ID;
 788   AddNodeIDNode(ID, Opc, getVTList(EltVT), (SDOperand*)0, 0);
 789   ID.Add(V);
 790   void *IP = 0;
 791   SDNode *N = NULL;
 792   if ((N = CSEMap.FindNodeOrInsertPos(ID, IP)))
 793     if (!MVT::isVector(VT))
 794       return SDOperand(N, 0);
 795   if (!N) {
 796     N = new ConstantFPSDNode(isTarget, V, EltVT);
 797     CSEMap.InsertNode(N, IP);
 798     AllNodes.push_back(N);
 799   }
 800
 801   SDOperand Result(N, 0);
 802   if (MVT::isVector(VT)) {
 803     SmallVector<SDOperand, 8> Ops;
 804     Ops.assign(MVT::getVectorNumElements(VT), Result);
 805     Result = getNode(ISD::BUILD_VECTOR, VT, &Ops[0], Ops.size());
 806   }
 807   return Result;
 808 }
 809
 810 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT,
 811                                       bool isTarget) {
 812   MVT::ValueType EltVT =
 813     MVT::isVector(VT) ? MVT::getVectorElementType(VT) : VT;
 814   if (EltVT==MVT::f32)
 815     return getConstantFP(APFloat((float)Val), VT, isTarget);
 816   else
 817     return getConstantFP(APFloat(Val), VT, isTarget);
 818 }
 819
 820 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 821                                          MVT::ValueType VT, int Offset,
 822                                          bool isTargetGA) {
 823   unsigned Opc;
 824
 825   const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV);
 826   if (!GVar) {
 827     // If GV is an alias then use the aliasee for determining thread-localness.
 828     if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV))
 829       GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal());
 830   }
 831
 832   if (GVar && GVar->isThreadLocal())
 833     Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress;
 834   else
 835     Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress;
 836
 837   FoldingSetNodeID ID;
 838   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 839   ID.AddPointer(GV);
 840   ID.AddInteger(Offset);
 841   void *IP = 0;
 842   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 843    return SDOperand(E, 0);
 844   SDNode *N = new GlobalAddressSDNode(isTargetGA, GV, VT, Offset);
 845   CSEMap.InsertNode(N, IP);
 846   AllNodes.push_back(N);
 847   return SDOperand(N, 0);
 848 }
 849
 850 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT,
 851                                       bool isTarget) {
 852   unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex;
 853   FoldingSetNodeID ID;
 854   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 855   ID.AddInteger(FI);
 856   void *IP = 0;
 857   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 858     return SDOperand(E, 0);
 859   SDNode *N = new FrameIndexSDNode(FI, VT, isTarget);
 860   CSEMap.InsertNode(N, IP);
 861   AllNodes.push_back(N);
 862   return SDOperand(N, 0);
 863 }
 864
 865 SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){
 866   unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable;
 867   FoldingSetNodeID ID;
 868   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 869   ID.AddInteger(JTI);
 870   void *IP = 0;
 871   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 872     return SDOperand(E, 0);
 873   SDNode *N = new JumpTableSDNode(JTI, VT, isTarget);
 874   CSEMap.InsertNode(N, IP);
 875   AllNodes.push_back(N);
 876   return SDOperand(N, 0);
 877 }
 878
 879 SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT,
 880                                         unsigned Alignment, int Offset,
 881                                         bool isTarget) {
 882   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
 883   FoldingSetNodeID ID;
 884   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 885   ID.AddInteger(Alignment);
 886   ID.AddInteger(Offset);
 887   ID.AddPointer(C);
 888   void *IP = 0;
 889   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 890     return SDOperand(E, 0);
 891   SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
 892   CSEMap.InsertNode(N, IP);
 893   AllNodes.push_back(N);
 894   return SDOperand(N, 0);
 895 }
 896
 897
 898 SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C,
 899                                         MVT::ValueType VT,
 900                                         unsigned Alignment, int Offset,
 901                                         bool isTarget) {
 902   unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool;
 903   FoldingSetNodeID ID;
 904   AddNodeIDNode(ID, Opc, getVTList(VT), (SDOperand*)0, 0);
 905   ID.AddInteger(Alignment);
 906   ID.AddInteger(Offset);
 907   C->AddSelectionDAGCSEId(ID);
 908   void *IP = 0;
 909   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 910     return SDOperand(E, 0);
 911   SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment);
 912   CSEMap.InsertNode(N, IP);
 913   AllNodes.push_back(N);
 914   return SDOperand(N, 0);
 915 }
 916
 917
 918 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
 919   FoldingSetNodeID ID;
 920   AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), (SDOperand*)0, 0);
 921   ID.AddPointer(MBB);
 922   void *IP = 0;
 923   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 924     return SDOperand(E, 0);
 925   SDNode *N = new BasicBlockSDNode(MBB);
 926   CSEMap.InsertNode(N, IP);
 927   AllNodes.push_back(N);
 928   return SDOperand(N, 0);
 929 }
 930
 931 SDOperand SelectionDAG::getArgFlags(ISD::ArgFlagsTy Flags) {
 932   FoldingSetNodeID ID;
 933   AddNodeIDNode(ID, ISD::ARG_FLAGS, getVTList(MVT::Other), (SDOperand*)0, 0);
 934   ID.AddInteger(Flags.getRawBits());
 935   void *IP = 0;
 936   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 937     return SDOperand(E, 0);
 938   SDNode *N = new ARG_FLAGSSDNode(Flags);
 939   CSEMap.InsertNode(N, IP);
 940   AllNodes.push_back(N);
 941   return SDOperand(N, 0);
 942 }
 943
 944 SDOperand SelectionDAG::getValueType(MVT::ValueType VT) {
 945   if (!MVT::isExtendedVT(VT) && (unsigned)VT >= ValueTypeNodes.size())
 946     ValueTypeNodes.resize(VT+1);
 947
 948   SDNode *&N = MVT::isExtendedVT(VT) ?
 949     ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT];
 950
 951   if (N) return SDOperand(N, 0);
 952   N = new VTSDNode(VT);
 953   AllNodes.push_back(N);
 954   return SDOperand(N, 0);
 955 }
 956
 957 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
 958   SDNode *&N = ExternalSymbols[Sym];
 959   if (N) return SDOperand(N, 0);
 960   N = new ExternalSymbolSDNode(false, Sym, VT);
 961   AllNodes.push_back(N);
 962   return SDOperand(N, 0);
 963 }
 964
 965 SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym,
 966                                                 MVT::ValueType VT) {
 967   SDNode *&N = TargetExternalSymbols[Sym];
 968   if (N) return SDOperand(N, 0);
 969   N = new ExternalSymbolSDNode(true, Sym, VT);
 970   AllNodes.push_back(N);
 971   return SDOperand(N, 0);
 972 }
 973
 974 SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
 975   if ((unsigned)Cond >= CondCodeNodes.size())
 976     CondCodeNodes.resize(Cond+1);
 977
 978   if (CondCodeNodes[Cond] == 0) {
 979     CondCodeNodes[Cond] = new CondCodeSDNode(Cond);
 980     AllNodes.push_back(CondCodeNodes[Cond]);
 981   }
 982   return SDOperand(CondCodeNodes[Cond], 0);
 983 }
 984
 985 SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) {
 986   FoldingSetNodeID ID;
 987   AddNodeIDNode(ID, ISD::Register, getVTList(VT), (SDOperand*)0, 0);
 988   ID.AddInteger(RegNo);
 989   void *IP = 0;
 990   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 991     return SDOperand(E, 0);
 992   SDNode *N = new RegisterSDNode(RegNo, VT);
 993   CSEMap.InsertNode(N, IP);
 994   AllNodes.push_back(N);
 995   return SDOperand(N, 0);
 996 }
 997
 998 SDOperand SelectionDAG::getSrcValue(const Value *V) {
 999   assert((!V || isa<PointerType>(V->getType())) &&
1000          "SrcValue is not a pointer?");
1001
1002   FoldingSetNodeID ID;
1003   AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), (SDOperand*)0, 0);
1004   ID.AddPointer(V);
1005
1006   void *IP = 0;
1007   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1008     return SDOperand(E, 0);
1009
1010   SDNode *N = new SrcValueSDNode(V);
1011   CSEMap.InsertNode(N, IP);
1012   AllNodes.push_back(N);
1013   return SDOperand(N, 0);
1014 }
1015
1016 SDOperand SelectionDAG::getMemOperand(const MachineMemOperand &MO) {
1017   const Value *v = MO.getValue();
1018   assert((!v || isa<PointerType>(v->getType())) &&
1019          "SrcValue is not a pointer?");
1020
1021   FoldingSetNodeID ID;
1022   AddNodeIDNode(ID, ISD::MEMOPERAND, getVTList(MVT::Other), (SDOperand*)0, 0);
1023   ID.AddPointer(v);
1024   ID.AddInteger(MO.getFlags());
1025   ID.AddInteger(MO.getOffset());
1026   ID.AddInteger(MO.getSize());
1027   ID.AddInteger(MO.getAlignment());
1028
1029   void *IP = 0;
1030   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1031     return SDOperand(E, 0);
1032
1033   SDNode *N = new MemOperandSDNode(MO);
1034   CSEMap.InsertNode(N, IP);
1035   AllNodes.push_back(N);
1036   return SDOperand(N, 0);
1037 }
1038
1039 /// CreateStackTemporary - Create a stack temporary, suitable for holding the
1040 /// specified value type.
1041 SDOperand SelectionDAG::CreateStackTemporary(MVT::ValueType VT) {
1042   MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo();
1043   unsigned ByteSize = MVT::getSizeInBits(VT)/8;
1044   const Type *Ty = MVT::getTypeForValueType(VT);
1045   unsigned StackAlign = (unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty);
1046   int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign);
1047   return getFrameIndex(FrameIdx, TLI.getPointerTy());
1048 }
1049
1050
1051 SDOperand SelectionDAG::FoldSetCC(MVT::ValueType VT, SDOperand N1,
1052                                   SDOperand N2, ISD::CondCode Cond) {
1053   // These setcc operations always fold.
1054   switch (Cond) {
1055   default: break;
1056   case ISD::SETFALSE:
1057   case ISD::SETFALSE2: return getConstant(0, VT);
1058   case ISD::SETTRUE:
1059   case ISD::SETTRUE2:  return getConstant(1, VT);
1060
1061   case ISD::SETOEQ:
1062   case ISD::SETOGT:
1063   case ISD::SETOGE:
1064   case ISD::SETOLT:
1065   case ISD::SETOLE:
1066   case ISD::SETONE:
1067   case ISD::SETO:
1068   case ISD::SETUO:
1069   case ISD::SETUEQ:
1070   case ISD::SETUNE:
1071     assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!");
1072     break;
1073   }
1074
1075   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
1076     const APInt &C2 = N2C->getAPIntValue();
1077     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
1078       const APInt &C1 = N1C->getAPIntValue();
1079
1080       switch (Cond) {
1081       default: assert(0 && "Unknown integer setcc!");
1082       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
1083       case ISD::SETNE:  return getConstant(C1 != C2, VT);
1084       case ISD::SETULT: return getConstant(C1.ult(C2), VT);
1085       case ISD::SETUGT: return getConstant(C1.ugt(C2), VT);
1086       case ISD::SETULE: return getConstant(C1.ule(C2), VT);
1087       case ISD::SETUGE: return getConstant(C1.uge(C2), VT);
1088       case ISD::SETLT:  return getConstant(C1.slt(C2), VT);
1089       case ISD::SETGT:  return getConstant(C1.sgt(C2), VT);
1090       case ISD::SETLE:  return getConstant(C1.sle(C2), VT);
1091       case ISD::SETGE:  return getConstant(C1.sge(C2), VT);
1092       }
1093     }
1094   }
1095   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) {
1096     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
1097       // No compile time operations on this type yet.
1098       if (N1C->getValueType(0) == MVT::ppcf128)
1099         return SDOperand();
1100
1101       APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF());
1102       switch (Cond) {
1103       default: break;
1104       case ISD::SETEQ:  if (R==APFloat::cmpUnordered)
1105                           return getNode(ISD::UNDEF, VT);
1106                         // fall through
1107       case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT);
1108       case ISD::SETNE:  if (R==APFloat::cmpUnordered)
1109                           return getNode(ISD::UNDEF, VT);
1110                         // fall through
1111       case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan ||
1112                                            R==APFloat::cmpLessThan, VT);
1113       case ISD::SETLT:  if (R==APFloat::cmpUnordered)
1114                           return getNode(ISD::UNDEF, VT);
1115                         // fall through
1116       case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT);
1117       case ISD::SETGT:  if (R==APFloat::cmpUnordered)
1118                           return getNode(ISD::UNDEF, VT);
1119                         // fall through
1120       case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT);
1121       case ISD::SETLE:  if (R==APFloat::cmpUnordered)
1122                           return getNode(ISD::UNDEF, VT);
1123                         // fall through
1124       case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan ||
1125                                            R==APFloat::cmpEqual, VT);
1126       case ISD::SETGE:  if (R==APFloat::cmpUnordered)
1127                           return getNode(ISD::UNDEF, VT);
1128                         // fall through
1129       case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan ||
1130                                            R==APFloat::cmpEqual, VT);
1131       case ISD::SETO:   return getConstant(R!=APFloat::cmpUnordered, VT);
1132       case ISD::SETUO:  return getConstant(R==APFloat::cmpUnordered, VT);
1133       case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered ||
1134                                            R==APFloat::cmpEqual, VT);
1135       case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT);
1136       case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered ||
1137                                            R==APFloat::cmpLessThan, VT);
1138       case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan ||
1139                                            R==APFloat::cmpUnordered, VT);
1140       case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT);
1141       case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT);
1142       }
1143     } else {
1144       // Ensure that the constant occurs on the RHS.
1145       return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
1146     }
1147   }
1148
1149   // Could not fold it.
1150   return SDOperand();
1151 }
1152
1153 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
1154 /// use this predicate to simplify operations downstream.
1155 bool SelectionDAG::SignBitIsZero(SDOperand Op, unsigned Depth) const {
1156   unsigned BitWidth = Op.getValueSizeInBits();
1157   return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth);
1158 }
1159
1160 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
1161 /// this predicate to simplify operations downstream.  Mask is known to be zero
1162 /// for bits that V cannot have.
1163 bool SelectionDAG::MaskedValueIsZero(SDOperand Op, const APInt &Mask,
1164                                      unsigned Depth) const {
1165   APInt KnownZero, KnownOne;
1166   ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1167   assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1168   return (KnownZero & Mask) == Mask;
1169 }
1170
1171 /// ComputeMaskedBits - Determine which of the bits specified in Mask are
1172 /// known to be either zero or one and return them in the KnownZero/KnownOne
1173 /// bitsets.  This code only analyzes bits in Mask, in order to short-circuit
1174 /// processing.
1175 void SelectionDAG::ComputeMaskedBits(SDOperand Op, const APInt &Mask,
1176                                      APInt &KnownZero, APInt &KnownOne,
1177                                      unsigned Depth) const {
1178   unsigned BitWidth = Mask.getBitWidth();
1179   assert(BitWidth == MVT::getSizeInBits(Op.getValueType()) &&
1180          "Mask size mismatches value type size!");
1181
1182   KnownZero = KnownOne = APInt(BitWidth, 0);   // Don't know anything.
1183   if (Depth == 6 || Mask == 0)
1184     return;  // Limit search depth.
1185
1186   APInt KnownZero2, KnownOne2;
1187
1188   switch (Op.getOpcode()) {
1189   case ISD::Constant:
1190     // We know all of the bits for a constant!
1191     KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue() & Mask;
1192     KnownZero = ~KnownOne & Mask;
1193     return;
1194   case ISD::AND:
1195     // If either the LHS or the RHS are Zero, the result is zero.
1196     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1197     ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownZero,
1198                       KnownZero2, KnownOne2, Depth+1);
1199     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1200     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1201
1202     // Output known-1 bits are only known if set in both the LHS & RHS.
1203     KnownOne &= KnownOne2;
1204     // Output known-0 are known to be clear if zero in either the LHS | RHS.
1205     KnownZero |= KnownZero2;
1206     return;
1207   case ISD::OR:
1208     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1209     ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownOne,
1210                       KnownZero2, KnownOne2, Depth+1);
1211     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1212     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1213
1214     // Output known-0 bits are only known if clear in both the LHS & RHS.
1215     KnownZero &= KnownZero2;
1216     // Output known-1 are known to be set if set in either the LHS | RHS.
1217     KnownOne |= KnownOne2;
1218     return;
1219   case ISD::XOR: {
1220     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1221     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
1222     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1223     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1224
1225     // Output known-0 bits are known if clear or set in both the LHS & RHS.
1226     APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2);
1227     // Output known-1 are known to be set if set in only one of the LHS, RHS.
1228     KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2);
1229     KnownZero = KnownZeroOut;
1230     return;
1231   }
1232   case ISD::SELECT:
1233     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1);
1234     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1);
1235     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1236     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1237
1238     // Only known if known in both the LHS and RHS.
1239     KnownOne &= KnownOne2;
1240     KnownZero &= KnownZero2;
1241     return;
1242   case ISD::SELECT_CC:
1243     ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1);
1244     ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1);
1245     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1246     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1247
1248     // Only known if known in both the LHS and RHS.
1249     KnownOne &= KnownOne2;
1250     KnownZero &= KnownZero2;
1251     return;
1252   case ISD::SETCC:
1253     // If we know the result of a setcc has the top bits zero, use this info.
1254     if (TLI.getSetCCResultContents() == TargetLowering::ZeroOrOneSetCCResult &&
1255         BitWidth > 1)
1256       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1257     return;
1258   case ISD::SHL:
1259     // (shl X, C1) & C2 == 0   iff   (X & C2 >>u C1) == 0
1260     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1261       unsigned ShAmt = SA->getValue();
1262
1263       // If the shift count is an invalid immediate, don't do anything.
1264       if (ShAmt >= BitWidth)
1265         return;
1266
1267       ComputeMaskedBits(Op.getOperand(0), Mask.lshr(ShAmt),
1268                         KnownZero, KnownOne, Depth+1);
1269       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1270       KnownZero <<= ShAmt;
1271       KnownOne  <<= ShAmt;
1272       // low bits known zero.
1273       KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt);
1274     }
1275     return;
1276   case ISD::SRL:
1277     // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
1278     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1279       unsigned ShAmt = SA->getValue();
1280
1281       // If the shift count is an invalid immediate, don't do anything.
1282       if (ShAmt >= BitWidth)
1283         return;
1284
1285       ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt),
1286                         KnownZero, KnownOne, Depth+1);
1287       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1288       KnownZero = KnownZero.lshr(ShAmt);
1289       KnownOne  = KnownOne.lshr(ShAmt);
1290
1291       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1292       KnownZero |= HighBits;  // High bits known zero.
1293     }
1294     return;
1295   case ISD::SRA:
1296     if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1297       unsigned ShAmt = SA->getValue();
1298
1299       // If the shift count is an invalid immediate, don't do anything.
1300       if (ShAmt >= BitWidth)
1301         return;
1302
1303       APInt InDemandedMask = (Mask << ShAmt);
1304       // If any of the demanded bits are produced by the sign extension, we also
1305       // demand the input sign bit.
1306       APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask;
1307       if (HighBits.getBoolValue())
1308         InDemandedMask |= APInt::getSignBit(BitWidth);
1309
1310       ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne,
1311                         Depth+1);
1312       assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1313       KnownZero = KnownZero.lshr(ShAmt);
1314       KnownOne  = KnownOne.lshr(ShAmt);
1315
1316       // Handle the sign bits.
1317       APInt SignBit = APInt::getSignBit(BitWidth);
1318       SignBit = SignBit.lshr(ShAmt);  // Adjust to where it is now in the mask.
1319
1320       if (KnownZero.intersects(SignBit)) {
1321         KnownZero |= HighBits;  // New bits are known zero.
1322       } else if (KnownOne.intersects(SignBit)) {
1323         KnownOne  |= HighBits;  // New bits are known one.
1324       }
1325     }
1326     return;
1327   case ISD::SIGN_EXTEND_INREG: {
1328     MVT::ValueType EVT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1329     unsigned EBits = MVT::getSizeInBits(EVT);
1330
1331     // Sign extension.  Compute the demanded bits in the result that are not
1332     // present in the input.
1333     APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits) & Mask;
1334
1335     APInt InSignBit = APInt::getSignBit(EBits);
1336     APInt InputDemandedBits = Mask & APInt::getLowBitsSet(BitWidth, EBits);
1337
1338     // If the sign extended bits are demanded, we know that the sign
1339     // bit is demanded.
1340     InSignBit.zext(BitWidth);
1341     if (NewBits.getBoolValue())
1342       InputDemandedBits |= InSignBit;
1343
1344     ComputeMaskedBits(Op.getOperand(0), InputDemandedBits,
1345                       KnownZero, KnownOne, Depth+1);
1346     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1347
1348     // If the sign bit of the input is known set or clear, then we know the
1349     // top bits of the result.
1350     if (KnownZero.intersects(InSignBit)) {         // Input sign bit known clear
1351       KnownZero |= NewBits;
1352       KnownOne  &= ~NewBits;
1353     } else if (KnownOne.intersects(InSignBit)) {   // Input sign bit known set
1354       KnownOne  |= NewBits;
1355       KnownZero &= ~NewBits;
1356     } else {                              // Input sign bit unknown
1357       KnownZero &= ~NewBits;
1358       KnownOne  &= ~NewBits;
1359     }
1360     return;
1361   }
1362   case ISD::CTTZ:
1363   case ISD::CTLZ:
1364   case ISD::CTPOP: {
1365     unsigned LowBits = Log2_32(BitWidth)+1;
1366     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits);
1367     KnownOne  = APInt(BitWidth, 0);
1368     return;
1369   }
1370   case ISD::LOAD: {
1371     if (ISD::isZEXTLoad(Op.Val)) {
1372       LoadSDNode *LD = cast<LoadSDNode>(Op);
1373       MVT::ValueType VT = LD->getMemoryVT();
1374       unsigned MemBits = MVT::getSizeInBits(VT);
1375       KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits) & Mask;
1376     }
1377     return;
1378   }
1379   case ISD::ZERO_EXTEND: {
1380     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1381     unsigned InBits = MVT::getSizeInBits(InVT);
1382     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1383     APInt InMask    = Mask;
1384     InMask.trunc(InBits);
1385     KnownZero.trunc(InBits);
1386     KnownOne.trunc(InBits);
1387     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1388     KnownZero.zext(BitWidth);
1389     KnownOne.zext(BitWidth);
1390     KnownZero |= NewBits;
1391     return;
1392   }
1393   case ISD::SIGN_EXTEND: {
1394     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1395     unsigned InBits = MVT::getSizeInBits(InVT);
1396     APInt InSignBit = APInt::getSignBit(InBits);
1397     APInt NewBits   = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask;
1398     APInt InMask = Mask;
1399     InMask.trunc(InBits);
1400
1401     // If any of the sign extended bits are demanded, we know that the sign
1402     // bit is demanded. Temporarily set this bit in the mask for our callee.
1403     if (NewBits.getBoolValue())
1404       InMask |= InSignBit;
1405
1406     KnownZero.trunc(InBits);
1407     KnownOne.trunc(InBits);
1408     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1409
1410     // Note if the sign bit is known to be zero or one.
1411     bool SignBitKnownZero = KnownZero.isNegative();
1412     bool SignBitKnownOne  = KnownOne.isNegative();
1413     assert(!(SignBitKnownZero && SignBitKnownOne) &&
1414            "Sign bit can't be known to be both zero and one!");
1415
1416     // If the sign bit wasn't actually demanded by our caller, we don't
1417     // want it set in the KnownZero and KnownOne result values. Reset the
1418     // mask and reapply it to the result values.
1419     InMask = Mask;
1420     InMask.trunc(InBits);
1421     KnownZero &= InMask;
1422     KnownOne  &= InMask;
1423
1424     KnownZero.zext(BitWidth);
1425     KnownOne.zext(BitWidth);
1426
1427     // If the sign bit is known zero or one, the top bits match.
1428     if (SignBitKnownZero)
1429       KnownZero |= NewBits;
1430     else if (SignBitKnownOne)
1431       KnownOne  |= NewBits;
1432     return;
1433   }
1434   case ISD::ANY_EXTEND: {
1435     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1436     unsigned InBits = MVT::getSizeInBits(InVT);
1437     APInt InMask = Mask;
1438     InMask.trunc(InBits);
1439     KnownZero.trunc(InBits);
1440     KnownOne.trunc(InBits);
1441     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1442     KnownZero.zext(BitWidth);
1443     KnownOne.zext(BitWidth);
1444     return;
1445   }
1446   case ISD::TRUNCATE: {
1447     MVT::ValueType InVT = Op.getOperand(0).getValueType();
1448     unsigned InBits = MVT::getSizeInBits(InVT);
1449     APInt InMask = Mask;
1450     InMask.zext(InBits);
1451     KnownZero.zext(InBits);
1452     KnownOne.zext(InBits);
1453     ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1);
1454     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1455     KnownZero.trunc(BitWidth);
1456     KnownOne.trunc(BitWidth);
1457     break;
1458   }
1459   case ISD::AssertZext: {
1460     MVT::ValueType VT = cast<VTSDNode>(Op.getOperand(1))->getVT();
1461     APInt InMask = APInt::getLowBitsSet(BitWidth, MVT::getSizeInBits(VT));
1462     ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero,
1463                       KnownOne, Depth+1);
1464     KnownZero |= (~InMask) & Mask;
1465     return;
1466   }
1467   case ISD::FGETSIGN:
1468     // All bits are zero except the low bit.
1469     KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1);
1470     return;
1471
1472   case ISD::ADD: {
1473     // If either the LHS or the RHS are Zero, the result is zero.
1474     ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1475     ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1);
1476     assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?");
1477     assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?");
1478
1479     // Output known-0 bits are known if clear or set in both the low clear bits
1480     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
1481     // low 3 bits clear.
1482     unsigned KnownZeroOut = std::min(KnownZero.countTrailingOnes(),
1483                                      KnownZero2.countTrailingOnes());
1484
1485     KnownZero = APInt::getLowBitsSet(BitWidth, KnownZeroOut);
1486     KnownOne = APInt(BitWidth, 0);
1487     return;
1488   }
1489   case ISD::SUB: {
1490     ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0));
1491     if (!CLHS) return;
1492
1493     // We know that the top bits of C-X are clear if X contains less bits
1494     // than C (i.e. no wrap-around can happen).  For example, 20-X is
1495     // positive if we can prove that X is >= 0 and < 16.
1496     if (CLHS->getAPIntValue().isNonNegative()) {
1497       unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros();
1498       // NLZ can't be BitWidth with no sign bit
1499       APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1);
1500       ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero, KnownOne, Depth+1);
1501
1502       // If all of the MaskV bits are known to be zero, then we know the output
1503       // top bits are zero, because we now know that the output is from [0-C].
1504       if ((KnownZero & MaskV) == MaskV) {
1505         unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros();
1506         // Top bits known zero.
1507         KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask;
1508         KnownOne = APInt(BitWidth, 0);   // No one bits known.
1509       } else {
1510         KnownZero = KnownOne = APInt(BitWidth, 0);  // Otherwise, nothing known.
1511       }
1512     }
1513     return;
1514   }
1515   default:
1516     // Allow the target to implement this method for its nodes.
1517     if (Op.getOpcode() >= ISD::BUILTIN_OP_END) {
1518   case ISD::INTRINSIC_WO_CHAIN:
1519   case ISD::INTRINSIC_W_CHAIN:
1520   case ISD::INTRINSIC_VOID:
1521       TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this);
1522     }
1523     return;
1524   }
1525 }
1526
1527 /// ComputeNumSignBits - Return the number of times the sign bit of the
1528 /// register is replicated into the other bits.  We know that at least 1 bit
1529 /// is always equal to the sign bit (itself), but other cases can give us
1530 /// information.  For example, immediately after an "SRA X, 2", we know that
1531 /// the top 3 bits are all equal to each other, so we return 3.
1532 unsigned SelectionDAG::ComputeNumSignBits(SDOperand Op, unsigned Depth) const{
1533   MVT::ValueType VT = Op.getValueType();
1534   assert(MVT::isInteger(VT) && "Invalid VT!");
1535   unsigned VTBits = MVT::getSizeInBits(VT);
1536   unsigned Tmp, Tmp2;
1537
1538   if (Depth == 6)
1539     return 1;  // Limit search depth.
1540
1541   switch (Op.getOpcode()) {
1542   default: break;
1543   case ISD::AssertSext:
1544     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1545     return VTBits-Tmp+1;
1546   case ISD::AssertZext:
1547     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1548     return VTBits-Tmp;
1549
1550   case ISD::Constant: {
1551     const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue();
1552     // If negative, return # leading ones.
1553     if (Val.isNegative())
1554       return Val.countLeadingOnes();
1555
1556     // Return # leading zeros.
1557     return Val.countLeadingZeros();
1558   }
1559
1560   case ISD::SIGN_EXTEND:
1561     Tmp = VTBits-MVT::getSizeInBits(Op.getOperand(0).getValueType());
1562     return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp;
1563
1564   case ISD::SIGN_EXTEND_INREG:
1565     // Max of the input and what this extends.
1566     Tmp = MVT::getSizeInBits(cast<VTSDNode>(Op.getOperand(1))->getVT());
1567     Tmp = VTBits-Tmp+1;
1568
1569     Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1570     return std::max(Tmp, Tmp2);
1571
1572   case ISD::SRA:
1573     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1574     // SRA X, C   -> adds C sign bits.
1575     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1576       Tmp += C->getValue();
1577       if (Tmp > VTBits) Tmp = VTBits;
1578     }
1579     return Tmp;
1580   case ISD::SHL:
1581     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1582       // shl destroys sign bits.
1583       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1584       if (C->getValue() >= VTBits ||      // Bad shift.
1585           C->getValue() >= Tmp) break;    // Shifted all sign bits out.
1586       return Tmp - C->getValue();
1587     }
1588     break;
1589   case ISD::AND:
1590   case ISD::OR:
1591   case ISD::XOR:    // NOT is handled here.
1592     // Logical binary ops preserve the number of sign bits.
1593     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1594     if (Tmp == 1) return 1;  // Early out.
1595     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1596     return std::min(Tmp, Tmp2);
1597
1598   case ISD::SELECT:
1599     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1600     if (Tmp == 1) return 1;  // Early out.
1601     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1602     return std::min(Tmp, Tmp2);
1603
1604   case ISD::SETCC:
1605     // If setcc returns 0/-1, all bits are sign bits.
1606     if (TLI.getSetCCResultContents() ==
1607         TargetLowering::ZeroOrNegativeOneSetCCResult)
1608       return VTBits;
1609     break;
1610   case ISD::ROTL:
1611   case ISD::ROTR:
1612     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
1613       unsigned RotAmt = C->getValue() & (VTBits-1);
1614
1615       // Handle rotate right by N like a rotate left by 32-N.
1616       if (Op.getOpcode() == ISD::ROTR)
1617         RotAmt = (VTBits-RotAmt) & (VTBits-1);
1618
1619       // If we aren't rotating out all of the known-in sign bits, return the
1620       // number that are left.  This handles rotl(sext(x), 1) for example.
1621       Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1622       if (Tmp > RotAmt+1) return Tmp-RotAmt;
1623     }
1624     break;
1625   case ISD::ADD:
1626     // Add can have at most one carry bit.  Thus we know that the output
1627     // is, at worst, one more bit than the inputs.
1628     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1629     if (Tmp == 1) return 1;  // Early out.
1630
1631     // Special case decrementing a value (ADD X, -1):
1632     if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1633       if (CRHS->isAllOnesValue()) {
1634         APInt KnownZero, KnownOne;
1635         APInt Mask = APInt::getAllOnesValue(VTBits);
1636         ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1);
1637
1638         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1639         // sign bits set.
1640         if ((KnownZero | APInt(VTBits, 1)) == Mask)
1641           return VTBits;
1642
1643         // If we are subtracting one from a positive number, there is no carry
1644         // out of the result.
1645         if (KnownZero.isNegative())
1646           return Tmp;
1647       }
1648
1649     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1650     if (Tmp2 == 1) return 1;
1651       return std::min(Tmp, Tmp2)-1;
1652     break;
1653
1654   case ISD::SUB:
1655     Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1);
1656     if (Tmp2 == 1) return 1;
1657
1658     // Handle NEG.
1659     if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0)))
1660       if (CLHS->isNullValue()) {
1661         APInt KnownZero, KnownOne;
1662         APInt Mask = APInt::getAllOnesValue(VTBits);
1663         ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1);
1664         // If the input is known to be 0 or 1, the output is 0/-1, which is all
1665         // sign bits set.
1666         if ((KnownZero | APInt(VTBits, 1)) == Mask)
1667           return VTBits;
1668
1669         // If the input is known to be positive (the sign bit is known clear),
1670         // the output of the NEG has the same number of sign bits as the input.
1671         if (KnownZero.isNegative())
1672           return Tmp2;
1673
1674         // Otherwise, we treat this like a SUB.
1675       }
1676
1677     // Sub can have at most one carry bit.  Thus we know that the output
1678     // is, at worst, one more bit than the inputs.
1679     Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1);
1680     if (Tmp == 1) return 1;  // Early out.
1681       return std::min(Tmp, Tmp2)-1;
1682     break;
1683   case ISD::TRUNCATE:
1684     // FIXME: it's tricky to do anything useful for this, but it is an important
1685     // case for targets like X86.
1686     break;
1687   }
1688
1689   // Handle LOADX separately here. EXTLOAD case will fallthrough.
1690   if (Op.getOpcode() == ISD::LOAD) {
1691     LoadSDNode *LD = cast<LoadSDNode>(Op);
1692     unsigned ExtType = LD->getExtensionType();
1693     switch (ExtType) {
1694     default: break;
1695     case ISD::SEXTLOAD:    // '17' bits known
1696       Tmp = MVT::getSizeInBits(LD->getMemoryVT());
1697       return VTBits-Tmp+1;
1698     case ISD::ZEXTLOAD:    // '16' bits known
1699       Tmp = MVT::getSizeInBits(LD->getMemoryVT());
1700       return VTBits-Tmp;
1701     }
1702   }
1703
1704   // Allow the target to implement this method for its nodes.
1705   if (Op.getOpcode() >= ISD::BUILTIN_OP_END ||
1706       Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN ||
1707       Op.getOpcode() == ISD::INTRINSIC_W_CHAIN ||
1708       Op.getOpcode() == ISD::INTRINSIC_VOID) {
1709     unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth);
1710     if (NumBits > 1) return NumBits;
1711   }
1712
1713   // Finally, if we can prove that the top bits of the result are 0's or 1's,
1714   // use this information.
1715   APInt KnownZero, KnownOne;
1716   APInt Mask = APInt::getAllOnesValue(VTBits);
1717   ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth);
1718
1719   if (KnownZero.isNegative()) {        // sign bit is 0
1720     Mask = KnownZero;
1721   } else if (KnownOne.isNegative()) {  // sign bit is 1;
1722     Mask = KnownOne;
1723   } else {
1724     // Nothing known.
1725     return 1;
1726   }
1727
1728   // Okay, we know that the sign bit in Mask is set.  Use CLZ to determine
1729   // the number of identical bits in the top of the input value.
1730   Mask = ~Mask;
1731   Mask <<= Mask.getBitWidth()-VTBits;
1732   // Return # leading zeros.  We use 'min' here in case Val was zero before
1733   // shifting.  We don't want to return '64' as for an i32 "0".
1734   return std::min(VTBits, Mask.countLeadingZeros());
1735 }
1736
1737
1738 bool SelectionDAG::isVerifiedDebugInfoDesc(SDOperand Op) const {
1739   GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op);
1740   if (!GA) return false;
1741   GlobalVariable *GV = dyn_cast<GlobalVariable>(GA->getGlobal());
1742   if (!GV) return false;
1743   MachineModuleInfo *MMI = getMachineModuleInfo();
1744   return MMI && MMI->hasDebugInfo() && MMI->isVerified(GV);
1745 }
1746
1747
1748 /// getNode - Gets or creates the specified node.
1749 ///
1750 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
1751   FoldingSetNodeID ID;
1752   AddNodeIDNode(ID, Opcode, getVTList(VT), (SDOperand*)0, 0);
1753   void *IP = 0;
1754   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1755     return SDOperand(E, 0);
1756   SDNode *N = new SDNode(Opcode, SDNode::getSDVTList(VT));
1757   CSEMap.InsertNode(N, IP);
1758
1759   AllNodes.push_back(N);
1760   return SDOperand(N, 0);
1761 }
1762
1763 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1764                                 SDOperand Operand) {
1765   // Constant fold unary operations with an integer constant operand.
1766   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
1767     const APInt &Val = C->getAPIntValue();
1768     unsigned BitWidth = MVT::getSizeInBits(VT);
1769     switch (Opcode) {
1770     default: break;
1771     case ISD::SIGN_EXTEND:
1772       return getConstant(APInt(Val).sextOrTrunc(BitWidth), VT);
1773     case ISD::ANY_EXTEND:
1774     case ISD::ZERO_EXTEND:
1775     case ISD::TRUNCATE:
1776       return getConstant(APInt(Val).zextOrTrunc(BitWidth), VT);
1777     case ISD::UINT_TO_FP:
1778     case ISD::SINT_TO_FP: {
1779       const uint64_t zero[] = {0, 0};
1780       // No compile time operations on this type.
1781       if (VT==MVT::ppcf128)
1782         break;
1783       APFloat apf = APFloat(APInt(BitWidth, 2, zero));
1784       (void)apf.convertFromAPInt(Val,
1785                                  Opcode==ISD::SINT_TO_FP,
1786                                  APFloat::rmNearestTiesToEven);
1787       return getConstantFP(apf, VT);
1788     }
1789     case ISD::BIT_CONVERT:
1790       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
1791         return getConstantFP(Val.bitsToFloat(), VT);
1792       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
1793         return getConstantFP(Val.bitsToDouble(), VT);
1794       break;
1795     case ISD::BSWAP:
1796       return getConstant(Val.byteSwap(), VT);
1797     case ISD::CTPOP:
1798       return getConstant(Val.countPopulation(), VT);
1799     case ISD::CTLZ:
1800       return getConstant(Val.countLeadingZeros(), VT);
1801     case ISD::CTTZ:
1802       return getConstant(Val.countTrailingZeros(), VT);
1803     }
1804   }
1805
1806   // Constant fold unary operations with a floating point constant operand.
1807   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) {
1808     APFloat V = C->getValueAPF();    // make copy
1809     if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) {
1810       switch (Opcode) {
1811       case ISD::FNEG:
1812         V.changeSign();
1813         return getConstantFP(V, VT);
1814       case ISD::FABS:
1815         V.clearSign();
1816         return getConstantFP(V, VT);
1817       case ISD::FP_ROUND:
1818       case ISD::FP_EXTEND:
1819         // This can return overflow, underflow, or inexact; we don't care.
1820         // FIXME need to be more flexible about rounding mode.
1821         (void)V.convert(*MVTToAPFloatSemantics(VT),
1822                         APFloat::rmNearestTiesToEven);
1823         return getConstantFP(V, VT);
1824       case ISD::FP_TO_SINT:
1825       case ISD::FP_TO_UINT: {
1826         integerPart x;
1827         assert(integerPartWidth >= 64);
1828         // FIXME need to be more flexible about rounding mode.
1829         APFloat::opStatus s = V.convertToInteger(&x, 64U,
1830                               Opcode==ISD::FP_TO_SINT,
1831                               APFloat::rmTowardZero);
1832         if (s==APFloat::opInvalidOp)     // inexact is OK, in fact usual
1833           break;
1834         return getConstant(x, VT);
1835       }
1836       case ISD::BIT_CONVERT:
1837         if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
1838           return getConstant((uint32_t)V.convertToAPInt().getZExtValue(), VT);
1839         else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
1840           return getConstant(V.convertToAPInt().getZExtValue(), VT);
1841         break;
1842       }
1843     }
1844   }
1845
1846   unsigned OpOpcode = Operand.Val->getOpcode();
1847   switch (Opcode) {
1848   case ISD::TokenFactor:
1849   case ISD::MERGE_VALUES:
1850     return Operand;         // Factor or merge of one node?  No need.
1851   case ISD::FP_ROUND: assert(0 && "Invalid method to make FP_ROUND node");
1852   case ISD::FP_EXTEND:
1853     assert(MVT::isFloatingPoint(VT) &&
1854            MVT::isFloatingPoint(Operand.getValueType()) && "Invalid FP cast!");
1855     if (Operand.getValueType() == VT) return Operand;  // noop conversion.
1856     if (Operand.getOpcode() == ISD::UNDEF)
1857       return getNode(ISD::UNDEF, VT);
1858     break;
1859   case ISD::SIGN_EXTEND:
1860     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1861            "Invalid SIGN_EXTEND!");
1862     if (Operand.getValueType() == VT) return Operand;   // noop extension
1863     assert(MVT::getSizeInBits(Operand.getValueType()) < MVT::getSizeInBits(VT)
1864            && "Invalid sext node, dst < src!");
1865     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
1866       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1867     break;
1868   case ISD::ZERO_EXTEND:
1869     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1870            "Invalid ZERO_EXTEND!");
1871     if (Operand.getValueType() == VT) return Operand;   // noop extension
1872     assert(MVT::getSizeInBits(Operand.getValueType()) < MVT::getSizeInBits(VT)
1873            && "Invalid zext node, dst < src!");
1874     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
1875       return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
1876     break;
1877   case ISD::ANY_EXTEND:
1878     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1879            "Invalid ANY_EXTEND!");
1880     if (Operand.getValueType() == VT) return Operand;   // noop extension
1881     assert(MVT::getSizeInBits(Operand.getValueType()) < MVT::getSizeInBits(VT)
1882            && "Invalid anyext node, dst < src!");
1883     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND)
1884       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
1885       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1886     break;
1887   case ISD::TRUNCATE:
1888     assert(MVT::isInteger(VT) && MVT::isInteger(Operand.getValueType()) &&
1889            "Invalid TRUNCATE!");
1890     if (Operand.getValueType() == VT) return Operand;   // noop truncate
1891     assert(MVT::getSizeInBits(Operand.getValueType()) > MVT::getSizeInBits(VT)
1892            && "Invalid truncate node, src < dst!");
1893     if (OpOpcode == ISD::TRUNCATE)
1894       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1895     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
1896              OpOpcode == ISD::ANY_EXTEND) {
1897       // If the source is smaller than the dest, we still need an extend.
1898       if (MVT::getSizeInBits(Operand.Val->getOperand(0).getValueType())
1899           < MVT::getSizeInBits(VT))
1900         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1901       else if (MVT::getSizeInBits(Operand.Val->getOperand(0).getValueType())
1902                > MVT::getSizeInBits(VT))
1903         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1904       else
1905         return Operand.Val->getOperand(0);
1906     }
1907     break;
1908   case ISD::BIT_CONVERT:
1909     // Basic sanity checking.
1910     assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType())
1911            && "Cannot BIT_CONVERT between types of different sizes!");
1912     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
1913     if (OpOpcode == ISD::BIT_CONVERT)  // bitconv(bitconv(x)) -> bitconv(x)
1914       return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0));
1915     if (OpOpcode == ISD::UNDEF)
1916       return getNode(ISD::UNDEF, VT);
1917     break;
1918   case ISD::SCALAR_TO_VECTOR:
1919     assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) &&
1920            MVT::getVectorElementType(VT) == Operand.getValueType() &&
1921            "Illegal SCALAR_TO_VECTOR node!");
1922     if (OpOpcode == ISD::UNDEF)
1923       return getNode(ISD::UNDEF, VT);
1924     // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined.
1925     if (OpOpcode == ISD::EXTRACT_VECTOR_ELT &&
1926         isa<ConstantSDNode>(Operand.getOperand(1)) &&
1927         Operand.getConstantOperandVal(1) == 0 &&
1928         Operand.getOperand(0).getValueType() == VT)
1929       return Operand.getOperand(0);
1930     break;
1931   case ISD::FNEG:
1932     if (OpOpcode == ISD::FSUB)   // -(X-Y) -> (Y-X)
1933       return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1),
1934                      Operand.Val->getOperand(0));
1935     if (OpOpcode == ISD::FNEG)  // --X -> X
1936       return Operand.Val->getOperand(0);
1937     break;
1938   case ISD::FABS:
1939     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
1940       return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
1941     break;
1942   }
1943
1944   SDNode *N;
1945   SDVTList VTs = getVTList(VT);
1946   if (VT != MVT::Flag) { // Don't CSE flag producing nodes
1947     FoldingSetNodeID ID;
1948     SDOperand Ops[1] = { Operand };
1949     AddNodeIDNode(ID, Opcode, VTs, Ops, 1);
1950     void *IP = 0;
1951     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1952       return SDOperand(E, 0);
1953     N = new UnarySDNode(Opcode, VTs, Operand);
1954     CSEMap.InsertNode(N, IP);
1955   } else {
1956     N = new UnarySDNode(Opcode, VTs, Operand);
1957   }
1958   AllNodes.push_back(N);
1959   return SDOperand(N, 0);
1960 }
1961
1962
1963
1964 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1965                                 SDOperand N1, SDOperand N2) {
1966   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1967   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1968   switch (Opcode) {
1969   default: break;
1970   case ISD::TokenFactor:
1971     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
1972            N2.getValueType() == MVT::Other && "Invalid token factor!");
1973     // Fold trivial token factors.
1974     if (N1.getOpcode() == ISD::EntryToken) return N2;
1975     if (N2.getOpcode() == ISD::EntryToken) return N1;
1976     break;
1977   case ISD::AND:
1978     assert(MVT::isInteger(VT) && N1.getValueType() == N2.getValueType() &&
1979            N1.getValueType() == VT && "Binary operator types must match!");
1980     // (X & 0) -> 0.  This commonly occurs when legalizing i64 values, so it's
1981     // worth handling here.
1982     if (N2C && N2C->isNullValue())
1983       return N2;
1984     if (N2C && N2C->isAllOnesValue())  // X & -1 -> X
1985       return N1;
1986     break;
1987   case ISD::OR:
1988   case ISD::XOR:
1989     assert(MVT::isInteger(VT) && N1.getValueType() == N2.getValueType() &&
1990            N1.getValueType() == VT && "Binary operator types must match!");
1991     // (X ^| 0) -> X.  This commonly occurs when legalizing i64 values, so it's
1992     // worth handling here.
1993     if (N2C && N2C->isNullValue())
1994       return N1;
1995     break;
1996   case ISD::UDIV:
1997   case ISD::UREM:
1998   case ISD::MULHU:
1999   case ISD::MULHS:
2000     assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
2001     // fall through
2002   case ISD::ADD:
2003   case ISD::SUB:
2004   case ISD::MUL:
2005   case ISD::SDIV:
2006   case ISD::SREM:
2007   case ISD::FADD:
2008   case ISD::FSUB:
2009   case ISD::FMUL:
2010   case ISD::FDIV:
2011   case ISD::FREM:
2012     assert(N1.getValueType() == N2.getValueType() &&
2013            N1.getValueType() == VT && "Binary operator types must match!");
2014     break;
2015   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
2016     assert(N1.getValueType() == VT &&
2017            MVT::isFloatingPoint(N1.getValueType()) &&
2018            MVT::isFloatingPoint(N2.getValueType()) &&
2019            "Invalid FCOPYSIGN!");
2020     break;
2021   case ISD::SHL:
2022   case ISD::SRA:
2023   case ISD::SRL:
2024   case ISD::ROTL:
2025   case ISD::ROTR:
2026     assert(VT == N1.getValueType() &&
2027            "Shift operators return type must be the same as their first arg");
2028     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
2029            VT != MVT::i1 && "Shifts only work on integers");
2030     break;
2031   case ISD::FP_ROUND_INREG: {
2032     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
2033     assert(VT == N1.getValueType() && "Not an inreg round!");
2034     assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
2035            "Cannot FP_ROUND_INREG integer types");
2036     assert(MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(VT) &&
2037            "Not rounding down!");
2038     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
2039     break;
2040   }
2041   case ISD::FP_ROUND:
2042     assert(MVT::isFloatingPoint(VT) &&
2043            MVT::isFloatingPoint(N1.getValueType()) &&
2044            MVT::getSizeInBits(VT) <= MVT::getSizeInBits(N1.getValueType()) &&
2045            isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!");
2046     if (N1.getValueType() == VT) return N1;  // noop conversion.
2047     break;
2048   case ISD::AssertSext:
2049   case ISD::AssertZext: {
2050     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
2051     assert(VT == N1.getValueType() && "Not an inreg extend!");
2052     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
2053            "Cannot *_EXTEND_INREG FP types");
2054     assert(MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(VT) &&
2055            "Not extending!");
2056     if (VT == EVT) return N1; // noop assertion.
2057     break;
2058   }
2059   case ISD::SIGN_EXTEND_INREG: {
2060     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
2061     assert(VT == N1.getValueType() && "Not an inreg extend!");
2062     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
2063            "Cannot *_EXTEND_INREG FP types");
2064     assert(MVT::getSizeInBits(EVT) <= MVT::getSizeInBits(VT) &&
2065            "Not extending!");
2066     if (EVT == VT) return N1;  // Not actually extending
2067
2068     if (N1C) {
2069       APInt Val = N1C->getAPIntValue();
2070       unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT());
2071       Val <<= Val.getBitWidth()-FromBits;
2072       Val = Val.ashr(Val.getBitWidth()-FromBits);
2073       return getConstant(Val, VT);
2074     }
2075     break;
2076   }
2077   case ISD::EXTRACT_VECTOR_ELT:
2078     assert(N2C && "Bad EXTRACT_VECTOR_ELT!");
2079
2080     // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF.
2081     if (N1.getOpcode() == ISD::UNDEF)
2082       return getNode(ISD::UNDEF, VT);
2083
2084     // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is
2085     // expanding copies of large vectors from registers.
2086     if (N1.getOpcode() == ISD::CONCAT_VECTORS &&
2087         N1.getNumOperands() > 0) {
2088       unsigned Factor =
2089         MVT::getVectorNumElements(N1.getOperand(0).getValueType());
2090       return getNode(ISD::EXTRACT_VECTOR_ELT, VT,
2091                      N1.getOperand(N2C->getValue() / Factor),
2092                      getConstant(N2C->getValue() % Factor, N2.getValueType()));
2093     }
2094
2095     // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is
2096     // expanding large vector constants.
2097     if (N1.getOpcode() == ISD::BUILD_VECTOR)
2098       return N1.getOperand(N2C->getValue());
2099
2100     // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector
2101     // operations are lowered to scalars.
2102     if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT)
2103       if (ConstantSDNode *IEC = dyn_cast<ConstantSDNode>(N1.getOperand(2))) {
2104         if (IEC == N2C)
2105           return N1.getOperand(1);
2106         else
2107           return getNode(ISD::EXTRACT_VECTOR_ELT, VT, N1.getOperand(0), N2);
2108       }
2109     break;
2110   case ISD::EXTRACT_ELEMENT:
2111     assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!");
2112     assert(!MVT::isVector(N1.getValueType()) &&
2113            MVT::isInteger(N1.getValueType()) &&
2114            !MVT::isVector(VT) && MVT::isInteger(VT) &&
2115            "EXTRACT_ELEMENT only applies to integers!");
2116
2117     // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding
2118     // 64-bit integers into 32-bit parts.  Instead of building the extract of
2119     // the BUILD_PAIR, only to have legalize rip it apart, just do it now.
2120     if (N1.getOpcode() == ISD::BUILD_PAIR)
2121       return N1.getOperand(N2C->getValue());
2122
2123     // EXTRACT_ELEMENT of a constant int is also very common.
2124     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) {
2125       unsigned ElementSize = MVT::getSizeInBits(VT);
2126       unsigned Shift = ElementSize * N2C->getValue();
2127       APInt ShiftedVal = C->getAPIntValue().lshr(Shift);
2128       return getConstant(ShiftedVal.trunc(ElementSize), VT);
2129     }
2130     break;
2131   case ISD::EXTRACT_SUBVECTOR:
2132     if (N1.getValueType() == VT) // Trivial extraction.
2133       return N1;
2134     break;
2135   }
2136
2137   if (N1C) {
2138     if (N2C) {
2139       APInt C1 = N1C->getAPIntValue(), C2 = N2C->getAPIntValue();
2140       switch (Opcode) {
2141       case ISD::ADD: return getConstant(C1 + C2, VT);
2142       case ISD::SUB: return getConstant(C1 - C2, VT);
2143       case ISD::MUL: return getConstant(C1 * C2, VT);
2144       case ISD::UDIV:
2145         if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT);
2146         break;
2147       case ISD::UREM :
2148         if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT);
2149         break;
2150       case ISD::SDIV :
2151         if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT);
2152         break;
2153       case ISD::SREM :
2154         if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT);
2155         break;
2156       case ISD::AND  : return getConstant(C1 & C2, VT);
2157       case ISD::OR   : return getConstant(C1 | C2, VT);
2158       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
2159       case ISD::SHL  : return getConstant(C1 << C2, VT);
2160       case ISD::SRL  : return getConstant(C1.lshr(C2), VT);
2161       case ISD::SRA  : return getConstant(C1.ashr(C2), VT);
2162       case ISD::ROTL : return getConstant(C1.rotl(C2), VT);
2163       case ISD::ROTR : return getConstant(C1.rotr(C2), VT);
2164       default: break;
2165       }
2166     } else {      // Cannonicalize constant to RHS if commutative
2167       if (isCommutativeBinOp(Opcode)) {
2168         std::swap(N1C, N2C);
2169         std::swap(N1, N2);
2170       }
2171     }
2172   }
2173
2174   // Constant fold FP operations.
2175   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
2176   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
2177   if (N1CFP) {
2178     if (!N2CFP && isCommutativeBinOp(Opcode)) {
2179       // Cannonicalize constant to RHS if commutative
2180       std::swap(N1CFP, N2CFP);
2181       std::swap(N1, N2);
2182     } else if (N2CFP && VT != MVT::ppcf128) {
2183       APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF();
2184       APFloat::opStatus s;
2185       switch (Opcode) {
2186       case ISD::FADD:
2187         s = V1.add(V2, APFloat::rmNearestTiesToEven);
2188         if (s != APFloat::opInvalidOp)
2189           return getConstantFP(V1, VT);
2190         break;
2191       case ISD::FSUB:
2192         s = V1.subtract(V2, APFloat::rmNearestTiesToEven);
2193         if (s!=APFloat::opInvalidOp)
2194           return getConstantFP(V1, VT);
2195         break;
2196       case ISD::FMUL:
2197         s = V1.multiply(V2, APFloat::rmNearestTiesToEven);
2198         if (s!=APFloat::opInvalidOp)
2199           return getConstantFP(V1, VT);
2200         break;
2201       case ISD::FDIV:
2202         s = V1.divide(V2, APFloat::rmNearestTiesToEven);
2203         if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
2204           return getConstantFP(V1, VT);
2205         break;
2206       case ISD::FREM :
2207         s = V1.mod(V2, APFloat::rmNearestTiesToEven);
2208         if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero)
2209           return getConstantFP(V1, VT);
2210         break;
2211       case ISD::FCOPYSIGN:
2212         V1.copySign(V2);
2213         return getConstantFP(V1, VT);
2214       default: break;
2215       }
2216     }
2217   }
2218
2219   // Canonicalize an UNDEF to the RHS, even over a constant.
2220   if (N1.getOpcode() == ISD::UNDEF) {
2221     if (isCommutativeBinOp(Opcode)) {
2222       std::swap(N1, N2);
2223     } else {
2224       switch (Opcode) {
2225       case ISD::FP_ROUND_INREG:
2226       case ISD::SIGN_EXTEND_INREG:
2227       case ISD::SUB:
2228       case ISD::FSUB:
2229       case ISD::FDIV:
2230       case ISD::FREM:
2231       case ISD::SRA:
2232         return N1;     // fold op(undef, arg2) -> undef
2233       case ISD::UDIV:
2234       case ISD::SDIV:
2235       case ISD::UREM:
2236       case ISD::SREM:
2237       case ISD::SRL:
2238       case ISD::SHL:
2239         if (!MVT::isVector(VT))
2240           return getConstant(0, VT);    // fold op(undef, arg2) -> 0
2241         // For vectors, we can't easily build an all zero vector, just return
2242         // the LHS.
2243         return N2;
2244       }
2245     }
2246   }
2247
2248   // Fold a bunch of operators when the RHS is undef.
2249   if (N2.getOpcode() == ISD::UNDEF) {
2250     switch (Opcode) {
2251     case ISD::XOR:
2252       if (N1.getOpcode() == ISD::UNDEF)
2253         // Handle undef ^ undef -> 0 special case. This is a common
2254         // idiom (misuse).
2255         return getConstant(0, VT);
2256       // fallthrough
2257     case ISD::ADD:
2258     case ISD::ADDC:
2259     case ISD::ADDE:
2260     case ISD::SUB:
2261     case ISD::FADD:
2262     case ISD::FSUB:
2263     case ISD::FMUL:
2264     case ISD::FDIV:
2265     case ISD::FREM:
2266     case ISD::UDIV:
2267     case ISD::SDIV:
2268     case ISD::UREM:
2269     case ISD::SREM:
2270       return N2;       // fold op(arg1, undef) -> undef
2271     case ISD::MUL:
2272     case ISD::AND:
2273     case ISD::SRL:
2274     case ISD::SHL:
2275       if (!MVT::isVector(VT))
2276         return getConstant(0, VT);  // fold op(arg1, undef) -> 0
2277       // For vectors, we can't easily build an all zero vector, just return
2278       // the LHS.
2279       return N1;
2280     case ISD::OR:
2281       if (!MVT::isVector(VT))
2282         return getConstant(MVT::getIntVTBitMask(VT), VT);
2283       // For vectors, we can't easily build an all one vector, just return
2284       // the LHS.
2285       return N1;
2286     case ISD::SRA:
2287       return N1;
2288     }
2289   }
2290
2291   // Memoize this node if possible.
2292   SDNode *N;
2293   SDVTList VTs = getVTList(VT);
2294   if (VT != MVT::Flag) {
2295     SDOperand Ops[] = { N1, N2 };
2296     FoldingSetNodeID ID;
2297     AddNodeIDNode(ID, Opcode, VTs, Ops, 2);
2298     void *IP = 0;
2299     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2300       return SDOperand(E, 0);
2301     N = new BinarySDNode(Opcode, VTs, N1, N2);
2302     CSEMap.InsertNode(N, IP);
2303   } else {
2304     N = new BinarySDNode(Opcode, VTs, N1, N2);
2305   }
2306
2307   AllNodes.push_back(N);
2308   return SDOperand(N, 0);
2309 }
2310
2311 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2312                                 SDOperand N1, SDOperand N2, SDOperand N3) {
2313   // Perform various simplifications.
2314   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
2315   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
2316   switch (Opcode) {
2317   case ISD::SETCC: {
2318     // Use FoldSetCC to simplify SETCC's.
2319     SDOperand Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
2320     if (Simp.Val) return Simp;
2321     break;
2322   }
2323   case ISD::SELECT:
2324     if (N1C) {
2325      if (N1C->getValue())
2326         return N2;             // select true, X, Y -> X
2327       else
2328         return N3;             // select false, X, Y -> Y
2329     }
2330
2331     if (N2 == N3) return N2;   // select C, X, X -> X
2332     break;
2333   case ISD::BRCOND:
2334     if (N2C) {
2335       if (N2C->getValue()) // Unconditional branch
2336         return getNode(ISD::BR, MVT::Other, N1, N3);
2337       else
2338         return N1;         // Never-taken branch
2339     }
2340     break;
2341   case ISD::VECTOR_SHUFFLE:
2342     assert(VT == N1.getValueType() && VT == N2.getValueType() &&
2343            MVT::isVector(VT) && MVT::isVector(N3.getValueType()) &&
2344            N3.getOpcode() == ISD::BUILD_VECTOR &&
2345            MVT::getVectorNumElements(VT) == N3.getNumOperands() &&
2346            "Illegal VECTOR_SHUFFLE node!");
2347     break;
2348   case ISD::BIT_CONVERT:
2349     // Fold bit_convert nodes from a type to themselves.
2350     if (N1.getValueType() == VT)
2351       return N1;
2352     break;
2353   }
2354
2355   // Memoize node if it doesn't produce a flag.
2356   SDNode *N;
2357   SDVTList VTs = getVTList(VT);
2358   if (VT != MVT::Flag) {
2359     SDOperand Ops[] = { N1, N2, N3 };
2360     FoldingSetNodeID ID;
2361     AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
2362     void *IP = 0;
2363     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2364       return SDOperand(E, 0);
2365     N = new TernarySDNode(Opcode, VTs, N1, N2, N3);
2366     CSEMap.InsertNode(N, IP);
2367   } else {
2368     N = new TernarySDNode(Opcode, VTs, N1, N2, N3);
2369   }
2370   AllNodes.push_back(N);
2371   return SDOperand(N, 0);
2372 }
2373
2374 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2375                                 SDOperand N1, SDOperand N2, SDOperand N3,
2376                                 SDOperand N4) {
2377   SDOperand Ops[] = { N1, N2, N3, N4 };
2378   return getNode(Opcode, VT, Ops, 4);
2379 }
2380
2381 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2382                                 SDOperand N1, SDOperand N2, SDOperand N3,
2383                                 SDOperand N4, SDOperand N5) {
2384   SDOperand Ops[] = { N1, N2, N3, N4, N5 };
2385   return getNode(Opcode, VT, Ops, 5);
2386 }
2387
2388 /// getMemsetValue - Vectorized representation of the memset value
2389 /// operand.
2390 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT,
2391                                 SelectionDAG &DAG) {
2392   MVT::ValueType CurVT = VT;
2393   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) {
2394     uint64_t Val   = C->getValue() & 255;
2395     unsigned Shift = 8;
2396     while (CurVT != MVT::i8) {
2397       Val = (Val << Shift) | Val;
2398       Shift <<= 1;
2399       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
2400     }
2401     return DAG.getConstant(Val, VT);
2402   } else {
2403     Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value);
2404     unsigned Shift = 8;
2405     while (CurVT != MVT::i8) {
2406       Value =
2407         DAG.getNode(ISD::OR, VT,
2408                     DAG.getNode(ISD::SHL, VT, Value,
2409                                 DAG.getConstant(Shift, MVT::i8)), Value);
2410       Shift <<= 1;
2411       CurVT = (MVT::ValueType)((unsigned)CurVT - 1);
2412     }
2413
2414     return Value;
2415   }
2416 }
2417
2418 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only
2419 /// used when a memcpy is turned into a memset when the source is a constant
2420 /// string ptr.
2421 static SDOperand getMemsetStringVal(MVT::ValueType VT,
2422                                     SelectionDAG &DAG,
2423                                     const TargetLowering &TLI,
2424                                     std::string &Str, unsigned Offset) {
2425   uint64_t Val = 0;
2426   unsigned MSB = MVT::getSizeInBits(VT) / 8;
2427   if (TLI.isLittleEndian())
2428     Offset = Offset + MSB - 1;
2429   for (unsigned i = 0; i != MSB; ++i) {
2430     Val = (Val << 8) | (unsigned char)Str[Offset];
2431     Offset += TLI.isLittleEndian() ? -1 : 1;
2432   }
2433   return DAG.getConstant(Val, VT);
2434 }
2435
2436 /// getMemBasePlusOffset - Returns base and offset node for the
2437 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset,
2438                                       SelectionDAG &DAG) {
2439   MVT::ValueType VT = Base.getValueType();
2440   return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT));
2441 }
2442
2443 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required
2444 /// to replace the memset / memcpy is below the threshold. It also returns the
2445 /// types of the sequence of memory ops to perform memset / memcpy.
2446 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps,
2447                                      unsigned Limit, uint64_t Size,
2448                                      unsigned Align,
2449                                      const TargetLowering &TLI) {
2450   MVT::ValueType VT;
2451
2452   if (TLI.allowsUnalignedMemoryAccesses()) {
2453     VT = MVT::i64;
2454   } else {
2455     switch (Align & 7) {
2456     case 0:
2457       VT = MVT::i64;
2458       break;
2459     case 4:
2460       VT = MVT::i32;
2461       break;
2462     case 2:
2463       VT = MVT::i16;
2464       break;
2465     default:
2466       VT = MVT::i8;
2467       break;
2468     }
2469   }
2470
2471   MVT::ValueType LVT = MVT::i64;
2472   while (!TLI.isTypeLegal(LVT))
2473     LVT = (MVT::ValueType)((unsigned)LVT - 1);
2474   assert(MVT::isInteger(LVT));
2475
2476   if (VT > LVT)
2477     VT = LVT;
2478
2479   unsigned NumMemOps = 0;
2480   while (Size != 0) {
2481     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
2482     while (VTSize > Size) {
2483       VT = (MVT::ValueType)((unsigned)VT - 1);
2484       VTSize >>= 1;
2485     }
2486     assert(MVT::isInteger(VT));
2487
2488     if (++NumMemOps > Limit)
2489       return false;
2490     MemOps.push_back(VT);
2491     Size -= VTSize;
2492   }
2493
2494   return true;
2495 }
2496
2497 static SDOperand getMemcpyLoadsAndStores(SelectionDAG &DAG,
2498                                          SDOperand Chain, SDOperand Dst,
2499                                          SDOperand Src, uint64_t Size,
2500                                          unsigned Align,
2501                                          bool AlwaysInline,
2502                                          const Value *DstSV, uint64_t DstOff,
2503                                          const Value *SrcSV, uint64_t SrcOff) {
2504   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2505
2506   // Expand memcpy to a series of store ops if the size operand falls below
2507   // a certain threshold.
2508   std::vector<MVT::ValueType> MemOps;
2509   uint64_t Limit = -1;
2510   if (!AlwaysInline)
2511     Limit = TLI.getMaxStoresPerMemcpy();
2512   if (!MeetsMaxMemopRequirement(MemOps, Limit, Size, Align, TLI))
2513     return SDOperand();
2514
2515   SmallVector<SDOperand, 8> OutChains;
2516
2517   unsigned NumMemOps = MemOps.size();
2518   unsigned SrcDelta = 0;
2519   GlobalAddressSDNode *G = NULL;
2520   std::string Str;
2521   bool CopyFromStr = false;
2522
2523   if (Src.getOpcode() == ISD::GlobalAddress)
2524     G = cast<GlobalAddressSDNode>(Src);
2525   else if (Src.getOpcode() == ISD::ADD &&
2526            Src.getOperand(0).getOpcode() == ISD::GlobalAddress &&
2527            Src.getOperand(1).getOpcode() == ISD::Constant) {
2528     G = cast<GlobalAddressSDNode>(Src.getOperand(0));
2529     SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getValue();
2530   }
2531   if (G) {
2532     GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal());
2533     if (GV && GV->isConstant()) {
2534       Str = GV->getStringValue(false);
2535       if (!Str.empty()) {
2536         CopyFromStr = true;
2537         SrcOff += SrcDelta;
2538       }
2539     }
2540   }
2541
2542   for (unsigned i = 0; i < NumMemOps; i++) {
2543     MVT::ValueType VT = MemOps[i];
2544     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
2545     SDOperand Value, Store;
2546
2547     if (CopyFromStr) {
2548       Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff);
2549       Store =
2550         DAG.getStore(Chain, Value,
2551                      getMemBasePlusOffset(Dst, DstOff, DAG),
2552                      DstSV, DstOff);
2553     } else {
2554       Value = DAG.getLoad(VT, Chain,
2555                           getMemBasePlusOffset(Src, SrcOff, DAG),
2556                           SrcSV, SrcOff, false, Align);
2557       Store =
2558         DAG.getStore(Chain, Value,
2559                      getMemBasePlusOffset(Dst, DstOff, DAG),
2560                      DstSV, DstOff, false, Align);
2561     }
2562     OutChains.push_back(Store);
2563     SrcOff += VTSize;
2564     DstOff += VTSize;
2565   }
2566
2567   return DAG.getNode(ISD::TokenFactor, MVT::Other,
2568                      &OutChains[0], OutChains.size());
2569 }
2570
2571 static SDOperand getMemsetStores(SelectionDAG &DAG,
2572                                  SDOperand Chain, SDOperand Dst,
2573                                  SDOperand Src, uint64_t Size,
2574                                  unsigned Align,
2575                                  const Value *DstSV, uint64_t DstOff) {
2576   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
2577
2578   // Expand memset to a series of load/store ops if the size operand
2579   // falls below a certain threshold.
2580   std::vector<MVT::ValueType> MemOps;
2581   if (!MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(),
2582                                 Size, Align, TLI))
2583     return SDOperand();
2584
2585   SmallVector<SDOperand, 8> OutChains;
2586
2587   unsigned NumMemOps = MemOps.size();
2588   for (unsigned i = 0; i < NumMemOps; i++) {
2589     MVT::ValueType VT = MemOps[i];
2590     unsigned VTSize = MVT::getSizeInBits(VT) / 8;
2591     SDOperand Value = getMemsetValue(Src, VT, DAG);
2592     SDOperand Store = DAG.getStore(Chain, Value,
2593                                    getMemBasePlusOffset(Dst, DstOff, DAG),
2594                                    DstSV, DstOff);
2595     OutChains.push_back(Store);
2596     DstOff += VTSize;
2597   }
2598
2599   return DAG.getNode(ISD::TokenFactor, MVT::Other,
2600                      &OutChains[0], OutChains.size());
2601 }
2602
2603 SDOperand SelectionDAG::getMemcpy(SDOperand Chain, SDOperand Dst,
2604                                   SDOperand Src, SDOperand Size,
2605                                   unsigned Align, bool AlwaysInline,
2606                                   const Value *DstSV, uint64_t DstOff,
2607                                   const Value *SrcSV, uint64_t SrcOff) {
2608
2609   // Check to see if we should lower the memcpy to loads and stores first.
2610   // For cases within the target-specified limits, this is the best choice.
2611   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
2612   if (ConstantSize) {
2613     // Memcpy with size zero? Just return the original chain.
2614     if (ConstantSize->isNullValue())
2615       return Chain;
2616
2617     SDOperand Result =
2618       getMemcpyLoadsAndStores(*this, Chain, Dst, Src, ConstantSize->getValue(),
2619                               Align, false, DstSV, DstOff, SrcSV, SrcOff);
2620     if (Result.Val)
2621       return Result;
2622   }
2623
2624   // Then check to see if we should lower the memcpy with target-specific
2625   // code. If the target chooses to do this, this is the next best.
2626   SDOperand Result =
2627     TLI.EmitTargetCodeForMemcpy(*this, Chain, Dst, Src, Size, Align,
2628                                 AlwaysInline,
2629                                 DstSV, DstOff, SrcSV, SrcOff);
2630   if (Result.Val)
2631     return Result;
2632
2633   // If we really need inline code and the target declined to provide it,
2634   // use a (potentially long) sequence of loads and stores.
2635   if (AlwaysInline) {
2636     assert(ConstantSize && "AlwaysInline requires a constant size!");
2637     return getMemcpyLoadsAndStores(*this, Chain, Dst, Src,
2638                                    ConstantSize->getValue(), Align, true,
2639                                    DstSV, DstOff, SrcSV, SrcOff);
2640   }
2641
2642   // Emit a library call.
2643   TargetLowering::ArgListTy Args;
2644   TargetLowering::ArgListEntry Entry;
2645   Entry.Ty = TLI.getTargetData()->getIntPtrType();
2646   Entry.Node = Dst; Args.push_back(Entry);
2647   Entry.Node = Src; Args.push_back(Entry);
2648   Entry.Node = Size; Args.push_back(Entry);
2649   std::pair<SDOperand,SDOperand> CallResult =
2650     TLI.LowerCallTo(Chain, Type::VoidTy,
2651                     false, false, false, CallingConv::C, false,
2652                     getExternalSymbol("memcpy", TLI.getPointerTy()),
2653                     Args, *this);
2654   return CallResult.second;
2655 }
2656
2657 SDOperand SelectionDAG::getMemmove(SDOperand Chain, SDOperand Dst,
2658                                    SDOperand Src, SDOperand Size,
2659                                    unsigned Align,
2660                                    const Value *DstSV, uint64_t DstOff,
2661                                    const Value *SrcSV, uint64_t SrcOff) {
2662
2663   // TODO: Optimize small memmove cases with simple loads and stores,
2664   // ensuring that all loads precede all stores. This can cause severe
2665   // register pressure, so targets should be careful with the size limit.
2666
2667   // Then check to see if we should lower the memmove with target-specific
2668   // code. If the target chooses to do this, this is the next best.
2669   SDOperand Result =
2670     TLI.EmitTargetCodeForMemmove(*this, Chain, Dst, Src, Size, Align,
2671                                  DstSV, DstOff, SrcSV, SrcOff);
2672   if (Result.Val)
2673     return Result;
2674
2675   // Emit a library call.
2676   TargetLowering::ArgListTy Args;
2677   TargetLowering::ArgListEntry Entry;
2678   Entry.Ty = TLI.getTargetData()->getIntPtrType();
2679   Entry.Node = Dst; Args.push_back(Entry);
2680   Entry.Node = Src; Args.push_back(Entry);
2681   Entry.Node = Size; Args.push_back(Entry);
2682   std::pair<SDOperand,SDOperand> CallResult =
2683     TLI.LowerCallTo(Chain, Type::VoidTy,
2684                     false, false, false, CallingConv::C, false,
2685                     getExternalSymbol("memmove", TLI.getPointerTy()),
2686                     Args, *this);
2687   return CallResult.second;
2688 }
2689
2690 SDOperand SelectionDAG::getMemset(SDOperand Chain, SDOperand Dst,
2691                                   SDOperand Src, SDOperand Size,
2692                                   unsigned Align,
2693                                   const Value *DstSV, uint64_t DstOff) {
2694
2695   // Check to see if we should lower the memset to stores first.
2696   // For cases within the target-specified limits, this is the best choice.
2697   ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size);
2698   if (ConstantSize) {
2699     // Memset with size zero? Just return the original chain.
2700     if (ConstantSize->isNullValue())
2701       return Chain;
2702
2703     SDOperand Result =
2704       getMemsetStores(*this, Chain, Dst, Src, ConstantSize->getValue(), Align,
2705                       DstSV, DstOff);
2706     if (Result.Val)
2707       return Result;
2708   }
2709
2710   // Then check to see if we should lower the memset with target-specific
2711   // code. If the target chooses to do this, this is the next best.
2712   SDOperand Result =
2713     TLI.EmitTargetCodeForMemset(*this, Chain, Dst, Src, Size, Align,
2714                                 DstSV, DstOff);
2715   if (Result.Val)
2716     return Result;
2717
2718   // Emit a library call.
2719   const Type *IntPtrTy = TLI.getTargetData()->getIntPtrType();
2720   TargetLowering::ArgListTy Args;
2721   TargetLowering::ArgListEntry Entry;
2722   Entry.Node = Dst; Entry.Ty = IntPtrTy;
2723   Args.push_back(Entry);
2724   // Extend or truncate the argument to be an i32 value for the call.
2725   if (Src.getValueType() > MVT::i32)
2726     Src = getNode(ISD::TRUNCATE, MVT::i32, Src);
2727   else
2728     Src = getNode(ISD::ZERO_EXTEND, MVT::i32, Src);
2729   Entry.Node = Src; Entry.Ty = Type::Int32Ty; Entry.isSExt = true;
2730   Args.push_back(Entry);
2731   Entry.Node = Size; Entry.Ty = IntPtrTy; Entry.isSExt = false;
2732   Args.push_back(Entry);
2733   std::pair<SDOperand,SDOperand> CallResult =
2734     TLI.LowerCallTo(Chain, Type::VoidTy,
2735                     false, false, false, CallingConv::C, false,
2736                     getExternalSymbol("memset", TLI.getPointerTy()),
2737                     Args, *this);
2738   return CallResult.second;
2739 }
2740
2741 SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain,
2742                                   SDOperand Ptr, SDOperand Cmp,
2743                                   SDOperand Swp, MVT::ValueType VT) {
2744   assert(Opcode == ISD::ATOMIC_LCS && "Invalid Atomic Op");
2745   assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types");
2746   SDVTList VTs = getVTList(Cmp.getValueType(), MVT::Other);
2747   FoldingSetNodeID ID;
2748   SDOperand Ops[] = {Chain, Ptr, Cmp, Swp};
2749   AddNodeIDNode(ID, Opcode, VTs, Ops, 4);
2750   ID.AddInteger((unsigned int)VT);
2751   void* IP = 0;
2752   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2753     return SDOperand(E, 0);
2754   SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Cmp, Swp, VT);
2755   CSEMap.InsertNode(N, IP);
2756   AllNodes.push_back(N);
2757   return SDOperand(N, 0);
2758 }
2759
2760 SDOperand SelectionDAG::getAtomic(unsigned Opcode, SDOperand Chain,
2761                                   SDOperand Ptr, SDOperand Val,
2762                                   MVT::ValueType VT) {
2763   assert((Opcode == ISD::ATOMIC_LAS || Opcode == ISD::ATOMIC_SWAP)
2764          && "Invalid Atomic Op");
2765   SDVTList VTs = getVTList(Val.getValueType(), MVT::Other);
2766   FoldingSetNodeID ID;
2767   SDOperand Ops[] = {Chain, Ptr, Val};
2768   AddNodeIDNode(ID, Opcode, VTs, Ops, 3);
2769   ID.AddInteger((unsigned int)VT);
2770   void* IP = 0;
2771   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2772     return SDOperand(E, 0);
2773   SDNode* N = new AtomicSDNode(Opcode, VTs, Chain, Ptr, Val, VT);
2774   CSEMap.InsertNode(N, IP);
2775   AllNodes.push_back(N);
2776   return SDOperand(N, 0);
2777 }
2778
2779 SDOperand
2780 SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType,
2781                       MVT::ValueType VT, SDOperand Chain,
2782                       SDOperand Ptr, SDOperand Offset,
2783                       const Value *SV, int SVOffset, MVT::ValueType EVT,
2784                       bool isVolatile, unsigned Alignment) {
2785   if (Alignment == 0) { // Ensure that codegen never sees alignment 0
2786     const Type *Ty = 0;
2787     if (VT != MVT::iPTR) {
2788       Ty = MVT::getTypeForValueType(VT);
2789     } else if (SV) {
2790       const PointerType *PT = dyn_cast<PointerType>(SV->getType());
2791       assert(PT && "Value for load must be a pointer");
2792       Ty = PT->getElementType();
2793     }
2794     assert(Ty && "Could not get type information for load");
2795     Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
2796   }
2797
2798   if (VT == EVT) {
2799     ExtType = ISD::NON_EXTLOAD;
2800   } else if (ExtType == ISD::NON_EXTLOAD) {
2801     assert(VT == EVT && "Non-extending load from different memory type!");
2802   } else {
2803     // Extending load.
2804     if (MVT::isVector(VT))
2805       assert(EVT == MVT::getVectorElementType(VT) && "Invalid vector extload!");
2806     else
2807       assert(MVT::getSizeInBits(EVT) < MVT::getSizeInBits(VT) &&
2808              "Should only be an extending load, not truncating!");
2809     assert((ExtType == ISD::EXTLOAD || MVT::isInteger(VT)) &&
2810            "Cannot sign/zero extend a FP/Vector load!");
2811     assert(MVT::isInteger(VT) == MVT::isInteger(EVT) &&
2812            "Cannot convert from FP to Int or Int -> FP!");
2813   }
2814
2815   bool Indexed = AM != ISD::UNINDEXED;
2816   assert(Indexed || Offset.getOpcode() == ISD::UNDEF &&
2817          "Unindexed load with an offset!");
2818
2819   SDVTList VTs = Indexed ?
2820     getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other);
2821   SDOperand Ops[] = { Chain, Ptr, Offset };
2822   FoldingSetNodeID ID;
2823   AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3);
2824   ID.AddInteger(AM);
2825   ID.AddInteger(ExtType);
2826   ID.AddInteger((unsigned int)EVT);
2827   ID.AddInteger(Alignment);
2828   ID.AddInteger(isVolatile);
2829   void *IP = 0;
2830   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2831     return SDOperand(E, 0);
2832   SDNode *N = new LoadSDNode(Ops, VTs, AM, ExtType, EVT, SV, SVOffset,
2833                              Alignment, isVolatile);
2834   CSEMap.InsertNode(N, IP);
2835   AllNodes.push_back(N);
2836   return SDOperand(N, 0);
2837 }
2838
2839 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
2840                                 SDOperand Chain, SDOperand Ptr,
2841                                 const Value *SV, int SVOffset,
2842                                 bool isVolatile, unsigned Alignment) {
2843   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2844   return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, Chain, Ptr, Undef,
2845                  SV, SVOffset, VT, isVolatile, Alignment);
2846 }
2847
2848 SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT,
2849                                    SDOperand Chain, SDOperand Ptr,
2850                                    const Value *SV,
2851                                    int SVOffset, MVT::ValueType EVT,
2852                                    bool isVolatile, unsigned Alignment) {
2853   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2854   return getLoad(ISD::UNINDEXED, ExtType, VT, Chain, Ptr, Undef,
2855                  SV, SVOffset, EVT, isVolatile, Alignment);
2856 }
2857
2858 SDOperand
2859 SelectionDAG::getIndexedLoad(SDOperand OrigLoad, SDOperand Base,
2860                              SDOperand Offset, ISD::MemIndexedMode AM) {
2861   LoadSDNode *LD = cast<LoadSDNode>(OrigLoad);
2862   assert(LD->getOffset().getOpcode() == ISD::UNDEF &&
2863          "Load is already a indexed load!");
2864   return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(),
2865                  LD->getChain(), Base, Offset, LD->getSrcValue(),
2866                  LD->getSrcValueOffset(), LD->getMemoryVT(),
2867                  LD->isVolatile(), LD->getAlignment());
2868 }
2869
2870 SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Val,
2871                                  SDOperand Ptr, const Value *SV, int SVOffset,
2872                                  bool isVolatile, unsigned Alignment) {
2873   MVT::ValueType VT = Val.getValueType();
2874
2875   if (Alignment == 0) { // Ensure that codegen never sees alignment 0
2876     const Type *Ty = 0;
2877     if (VT != MVT::iPTR) {
2878       Ty = MVT::getTypeForValueType(VT);
2879     } else if (SV) {
2880       const PointerType *PT = dyn_cast<PointerType>(SV->getType());
2881       assert(PT && "Value for store must be a pointer");
2882       Ty = PT->getElementType();
2883     }
2884     assert(Ty && "Could not get type information for store");
2885     Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
2886   }
2887   SDVTList VTs = getVTList(MVT::Other);
2888   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2889   SDOperand Ops[] = { Chain, Val, Ptr, Undef };
2890   FoldingSetNodeID ID;
2891   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
2892   ID.AddInteger(ISD::UNINDEXED);
2893   ID.AddInteger(false);
2894   ID.AddInteger((unsigned int)VT);
2895   ID.AddInteger(Alignment);
2896   ID.AddInteger(isVolatile);
2897   void *IP = 0;
2898   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2899     return SDOperand(E, 0);
2900   SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, false,
2901                               VT, SV, SVOffset, Alignment, isVolatile);
2902   CSEMap.InsertNode(N, IP);
2903   AllNodes.push_back(N);
2904   return SDOperand(N, 0);
2905 }
2906
2907 SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Val,
2908                                       SDOperand Ptr, const Value *SV,
2909                                       int SVOffset, MVT::ValueType SVT,
2910                                       bool isVolatile, unsigned Alignment) {
2911   MVT::ValueType VT = Val.getValueType();
2912
2913   if (VT == SVT)
2914     return getStore(Chain, Val, Ptr, SV, SVOffset, isVolatile, Alignment);
2915
2916   assert(MVT::getSizeInBits(VT) > MVT::getSizeInBits(SVT) &&
2917          "Not a truncation?");
2918   assert(MVT::isInteger(VT) == MVT::isInteger(SVT) &&
2919          "Can't do FP-INT conversion!");
2920
2921   if (Alignment == 0) { // Ensure that codegen never sees alignment 0
2922     const Type *Ty = 0;
2923     if (VT != MVT::iPTR) {
2924       Ty = MVT::getTypeForValueType(VT);
2925     } else if (SV) {
2926       const PointerType *PT = dyn_cast<PointerType>(SV->getType());
2927       assert(PT && "Value for store must be a pointer");
2928       Ty = PT->getElementType();
2929     }
2930     assert(Ty && "Could not get type information for store");
2931     Alignment = TLI.getTargetData()->getABITypeAlignment(Ty);
2932   }
2933   SDVTList VTs = getVTList(MVT::Other);
2934   SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType());
2935   SDOperand Ops[] = { Chain, Val, Ptr, Undef };
2936   FoldingSetNodeID ID;
2937   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
2938   ID.AddInteger(ISD::UNINDEXED);
2939   ID.AddInteger(1);
2940   ID.AddInteger((unsigned int)SVT);
2941   ID.AddInteger(Alignment);
2942   ID.AddInteger(isVolatile);
2943   void *IP = 0;
2944   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2945     return SDOperand(E, 0);
2946   SDNode *N = new StoreSDNode(Ops, VTs, ISD::UNINDEXED, true,
2947                               SVT, SV, SVOffset, Alignment, isVolatile);
2948   CSEMap.InsertNode(N, IP);
2949   AllNodes.push_back(N);
2950   return SDOperand(N, 0);
2951 }
2952
2953 SDOperand
2954 SelectionDAG::getIndexedStore(SDOperand OrigStore, SDOperand Base,
2955                               SDOperand Offset, ISD::MemIndexedMode AM) {
2956   StoreSDNode *ST = cast<StoreSDNode>(OrigStore);
2957   assert(ST->getOffset().getOpcode() == ISD::UNDEF &&
2958          "Store is already a indexed store!");
2959   SDVTList VTs = getVTList(Base.getValueType(), MVT::Other);
2960   SDOperand Ops[] = { ST->getChain(), ST->getValue(), Base, Offset };
2961   FoldingSetNodeID ID;
2962   AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4);
2963   ID.AddInteger(AM);
2964   ID.AddInteger(ST->isTruncatingStore());
2965   ID.AddInteger((unsigned int)(ST->getMemoryVT()));
2966   ID.AddInteger(ST->getAlignment());
2967   ID.AddInteger(ST->isVolatile());
2968   void *IP = 0;
2969   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
2970     return SDOperand(E, 0);
2971   SDNode *N = new StoreSDNode(Ops, VTs, AM,
2972                               ST->isTruncatingStore(), ST->getMemoryVT(),
2973                               ST->getSrcValue(), ST->getSrcValueOffset(),
2974                               ST->getAlignment(), ST->isVolatile());
2975   CSEMap.InsertNode(N, IP);
2976   AllNodes.push_back(N);
2977   return SDOperand(N, 0);
2978 }
2979
2980 SDOperand SelectionDAG::getVAArg(MVT::ValueType VT,
2981                                  SDOperand Chain, SDOperand Ptr,
2982                                  SDOperand SV) {
2983   SDOperand Ops[] = { Chain, Ptr, SV };
2984   return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3);
2985 }
2986
2987 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
2988                                 SDOperandPtr Ops, unsigned NumOps) {
2989   switch (NumOps) {
2990   case 0: return getNode(Opcode, VT);
2991   case 1: return getNode(Opcode, VT, Ops[0]);
2992   case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
2993   case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
2994   default: break;
2995   }
2996
2997   switch (Opcode) {
2998   default: break;
2999   case ISD::SELECT_CC: {
3000     assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
3001     assert(Ops[0].getValueType() == Ops[1].getValueType() &&
3002            "LHS and RHS of condition must have same type!");
3003     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
3004            "True and False arms of SelectCC must have same type!");
3005     assert(Ops[2].getValueType() == VT &&
3006            "select_cc node must be of same type as true and false value!");
3007     break;
3008   }
3009   case ISD::BR_CC: {
3010     assert(NumOps == 5 && "BR_CC takes 5 operands!");
3011     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
3012            "LHS/RHS of comparison should match types!");
3013     break;
3014   }
3015   }
3016
3017   // Memoize nodes.
3018   SDNode *N;
3019   SDVTList VTs = getVTList(VT);
3020   if (VT != MVT::Flag) {
3021     FoldingSetNodeID ID;
3022     AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps);
3023     void *IP = 0;
3024     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3025       return SDOperand(E, 0);
3026     N = new SDNode(Opcode, VTs, Ops, NumOps);
3027     CSEMap.InsertNode(N, IP);
3028   } else {
3029     N = new SDNode(Opcode, VTs, Ops, NumOps);
3030   }
3031   AllNodes.push_back(N);
3032   return SDOperand(N, 0);
3033 }
3034
3035 SDOperand SelectionDAG::getNode(unsigned Opcode,
3036                                 std::vector<MVT::ValueType> &ResultTys,
3037                                 SDOperandPtr Ops, unsigned NumOps) {
3038   return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(),
3039                  Ops, NumOps);
3040 }
3041
3042 SDOperand SelectionDAG::getNode(unsigned Opcode,
3043                                 const MVT::ValueType *VTs, unsigned NumVTs,
3044                                 SDOperandPtr Ops, unsigned NumOps) {
3045   if (NumVTs == 1)
3046     return getNode(Opcode, VTs[0], Ops, NumOps);
3047   return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps);
3048 }
3049
3050 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3051                                 SDOperandPtr Ops, unsigned NumOps) {
3052   if (VTList.NumVTs == 1)
3053     return getNode(Opcode, VTList.VTs[0], Ops, NumOps);
3054
3055   switch (Opcode) {
3056   // FIXME: figure out how to safely handle things like
3057   // int foo(int x) { return 1 << (x & 255); }
3058   // int bar() { return foo(256); }
3059 #if 0
3060   case ISD::SRA_PARTS:
3061   case ISD::SRL_PARTS:
3062   case ISD::SHL_PARTS:
3063     if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
3064         cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
3065       return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
3066     else if (N3.getOpcode() == ISD::AND)
3067       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
3068         // If the and is only masking out bits that cannot effect the shift,
3069         // eliminate the and.
3070         unsigned NumBits = MVT::getSizeInBits(VT)*2;
3071         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
3072           return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
3073       }
3074     break;
3075 #endif
3076   }
3077
3078   // Memoize the node unless it returns a flag.
3079   SDNode *N;
3080   if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
3081     FoldingSetNodeID ID;
3082     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
3083     void *IP = 0;
3084     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3085       return SDOperand(E, 0);
3086     if (NumOps == 1)
3087       N = new UnarySDNode(Opcode, VTList, Ops[0]);
3088     else if (NumOps == 2)
3089       N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
3090     else if (NumOps == 3)
3091       N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
3092     else
3093       N = new SDNode(Opcode, VTList, Ops, NumOps);
3094     CSEMap.InsertNode(N, IP);
3095   } else {
3096     if (NumOps == 1)
3097       N = new UnarySDNode(Opcode, VTList, Ops[0]);
3098     else if (NumOps == 2)
3099       N = new BinarySDNode(Opcode, VTList, Ops[0], Ops[1]);
3100     else if (NumOps == 3)
3101       N = new TernarySDNode(Opcode, VTList, Ops[0], Ops[1], Ops[2]);
3102     else
3103       N = new SDNode(Opcode, VTList, Ops, NumOps);
3104   }
3105   AllNodes.push_back(N);
3106   return SDOperand(N, 0);
3107 }
3108
3109 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList) {
3110   return getNode(Opcode, VTList, (SDOperand*)0, 0);
3111 }
3112
3113 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3114                                 SDOperand N1) {
3115   SDOperand Ops[] = { N1 };
3116   return getNode(Opcode, VTList, Ops, 1);
3117 }
3118
3119 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3120                                 SDOperand N1, SDOperand N2) {
3121   SDOperand Ops[] = { N1, N2 };
3122   return getNode(Opcode, VTList, Ops, 2);
3123 }
3124
3125 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3126                                 SDOperand N1, SDOperand N2, SDOperand N3) {
3127   SDOperand Ops[] = { N1, N2, N3 };
3128   return getNode(Opcode, VTList, Ops, 3);
3129 }
3130
3131 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3132                                 SDOperand N1, SDOperand N2, SDOperand N3,
3133                                 SDOperand N4) {
3134   SDOperand Ops[] = { N1, N2, N3, N4 };
3135   return getNode(Opcode, VTList, Ops, 4);
3136 }
3137
3138 SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList,
3139                                 SDOperand N1, SDOperand N2, SDOperand N3,
3140                                 SDOperand N4, SDOperand N5) {
3141   SDOperand Ops[] = { N1, N2, N3, N4, N5 };
3142   return getNode(Opcode, VTList, Ops, 5);
3143 }
3144
3145 SDVTList SelectionDAG::getVTList(MVT::ValueType VT) {
3146   return makeVTList(SDNode::getValueTypeList(VT), 1);
3147 }
3148
3149 SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2) {
3150   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
3151        E = VTList.end(); I != E; ++I) {
3152     if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2)
3153       return makeVTList(&(*I)[0], 2);
3154   }
3155   std::vector<MVT::ValueType> V;
3156   V.push_back(VT1);
3157   V.push_back(VT2);
3158   VTList.push_front(V);
3159   return makeVTList(&(*VTList.begin())[0], 2);
3160 }
3161 SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2,
3162                                  MVT::ValueType VT3) {
3163   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
3164        E = VTList.end(); I != E; ++I) {
3165     if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 &&
3166         (*I)[2] == VT3)
3167       return makeVTList(&(*I)[0], 3);
3168   }
3169   std::vector<MVT::ValueType> V;
3170   V.push_back(VT1);
3171   V.push_back(VT2);
3172   V.push_back(VT3);
3173   VTList.push_front(V);
3174   return makeVTList(&(*VTList.begin())[0], 3);
3175 }
3176
3177 SDVTList SelectionDAG::getVTList(const MVT::ValueType *VTs, unsigned NumVTs) {
3178   switch (NumVTs) {
3179     case 0: assert(0 && "Cannot have nodes without results!");
3180     case 1: return getVTList(VTs[0]);
3181     case 2: return getVTList(VTs[0], VTs[1]);
3182     case 3: return getVTList(VTs[0], VTs[1], VTs[2]);
3183     default: break;
3184   }
3185
3186   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
3187        E = VTList.end(); I != E; ++I) {
3188     if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue;
3189
3190     bool NoMatch = false;
3191     for (unsigned i = 2; i != NumVTs; ++i)
3192       if (VTs[i] != (*I)[i]) {
3193         NoMatch = true;
3194         break;
3195       }
3196     if (!NoMatch)
3197       return makeVTList(&*I->begin(), NumVTs);
3198   }
3199
3200   VTList.push_front(std::vector<MVT::ValueType>(VTs, VTs+NumVTs));
3201   return makeVTList(&*VTList.begin()->begin(), NumVTs);
3202 }
3203
3204
3205 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
3206 /// specified operands.  If the resultant node already exists in the DAG,
3207 /// this does not modify the specified node, instead it returns the node that
3208 /// already exists.  If the resultant node does not exist in the DAG, the
3209 /// input node is returned.  As a degenerate case, if you specify the same
3210 /// input operands as the node already has, the input node is returned.
3211 SDOperand SelectionDAG::
3212 UpdateNodeOperands(SDOperand InN, SDOperand Op) {
3213   SDNode *N = InN.Val;
3214   assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
3215
3216   // Check to see if there is no change.
3217   if (Op == N->getOperand(0)) return InN;
3218
3219   // See if the modified node already exists.
3220   void *InsertPos = 0;
3221   if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
3222     return SDOperand(Existing, InN.ResNo);
3223
3224   // Nope it doesn't.  Remove the node from it's current place in the maps.
3225   if (InsertPos)
3226     RemoveNodeFromCSEMaps(N);
3227
3228   // Now we update the operands.
3229   N->OperandList[0].getVal()->removeUser(0, N);
3230   N->OperandList[0] = Op;
3231   N->OperandList[0].setUser(N);
3232   Op.Val->addUser(0, N);
3233
3234   // If this gets put into a CSE map, add it.
3235   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3236   return InN;
3237 }
3238
3239 SDOperand SelectionDAG::
3240 UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) {
3241   SDNode *N = InN.Val;
3242   assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
3243
3244   // Check to see if there is no change.
3245   if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
3246     return InN;   // No operands changed, just return the input node.
3247
3248   // See if the modified node already exists.
3249   void *InsertPos = 0;
3250   if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
3251     return SDOperand(Existing, InN.ResNo);
3252
3253   // Nope it doesn't.  Remove the node from it's current place in the maps.
3254   if (InsertPos)
3255     RemoveNodeFromCSEMaps(N);
3256
3257   // Now we update the operands.
3258   if (N->OperandList[0] != Op1) {
3259     N->OperandList[0].getVal()->removeUser(0, N);
3260     N->OperandList[0] = Op1;
3261     N->OperandList[0].setUser(N);
3262     Op1.Val->addUser(0, N);
3263   }
3264   if (N->OperandList[1] != Op2) {
3265     N->OperandList[1].getVal()->removeUser(1, N);
3266     N->OperandList[1] = Op2;
3267     N->OperandList[1].setUser(N);
3268     Op2.Val->addUser(1, N);
3269   }
3270
3271   // If this gets put into a CSE map, add it.
3272   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3273   return InN;
3274 }
3275
3276 SDOperand SelectionDAG::
3277 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
3278   SDOperand Ops[] = { Op1, Op2, Op3 };
3279   return UpdateNodeOperands(N, Ops, 3);
3280 }
3281
3282 SDOperand SelectionDAG::
3283 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
3284                    SDOperand Op3, SDOperand Op4) {
3285   SDOperand Ops[] = { Op1, Op2, Op3, Op4 };
3286   return UpdateNodeOperands(N, Ops, 4);
3287 }
3288
3289 SDOperand SelectionDAG::
3290 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
3291                    SDOperand Op3, SDOperand Op4, SDOperand Op5) {
3292   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
3293   return UpdateNodeOperands(N, Ops, 5);
3294 }
3295
3296 SDOperand SelectionDAG::
3297 UpdateNodeOperands(SDOperand InN, SDOperandPtr Ops, unsigned NumOps) {
3298   SDNode *N = InN.Val;
3299   assert(N->getNumOperands() == NumOps &&
3300          "Update with wrong number of operands");
3301
3302   // Check to see if there is no change.
3303   bool AnyChange = false;
3304   for (unsigned i = 0; i != NumOps; ++i) {
3305     if (Ops[i] != N->getOperand(i)) {
3306       AnyChange = true;
3307       break;
3308     }
3309   }
3310
3311   // No operands changed, just return the input node.
3312   if (!AnyChange) return InN;
3313
3314   // See if the modified node already exists.
3315   void *InsertPos = 0;
3316   if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
3317     return SDOperand(Existing, InN.ResNo);
3318
3319   // Nope it doesn't.  Remove the node from it's current place in the maps.
3320   if (InsertPos)
3321     RemoveNodeFromCSEMaps(N);
3322
3323   // Now we update the operands.
3324   for (unsigned i = 0; i != NumOps; ++i) {
3325     if (N->OperandList[i] != Ops[i]) {
3326       N->OperandList[i].getVal()->removeUser(i, N);
3327       N->OperandList[i] = Ops[i];
3328       N->OperandList[i].setUser(N);
3329       Ops[i].Val->addUser(i, N);
3330     }
3331   }
3332
3333   // If this gets put into a CSE map, add it.
3334   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
3335   return InN;
3336 }
3337
3338 /// MorphNodeTo - This frees the operands of the current node, resets the
3339 /// opcode, types, and operands to the specified value.  This should only be
3340 /// used by the SelectionDAG class.
3341 void SDNode::MorphNodeTo(unsigned Opc, SDVTList L,
3342                          SDOperandPtr Ops, unsigned NumOps) {
3343   NodeType = Opc;
3344   ValueList = L.VTs;
3345   NumValues = L.NumVTs;
3346
3347   // Clear the operands list, updating used nodes to remove this from their
3348   // use list.
3349   for (op_iterator I = op_begin(), E = op_end(); I != E; ++I)
3350     I->getVal()->removeUser(std::distance(op_begin(), I), this);
3351
3352   // If NumOps is larger than the # of operands we currently have, reallocate
3353   // the operand list.
3354   if (NumOps > NumOperands) {
3355     if (OperandsNeedDelete) {
3356       delete [] OperandList;
3357     }
3358     OperandList = new SDUse[NumOps];
3359     OperandsNeedDelete = true;
3360   }
3361
3362   // Assign the new operands.
3363   NumOperands = NumOps;
3364
3365   for (unsigned i = 0, e = NumOps; i != e; ++i) {
3366     OperandList[i] = Ops[i];
3367     OperandList[i].setUser(this);
3368     SDNode *N = OperandList[i].getVal();
3369     N->addUser(i, this);
3370     ++N->UsesSize;
3371   }
3372 }
3373
3374 /// SelectNodeTo - These are used for target selectors to *mutate* the
3375 /// specified node to have the specified return type, Target opcode, and
3376 /// operands.  Note that target opcodes are stored as
3377 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
3378 ///
3379 /// Note that SelectNodeTo returns the resultant node.  If there is already a
3380 /// node of the specified opcode and operands, it returns that node instead of
3381 /// the current one.
3382 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3383                                    MVT::ValueType VT) {
3384   SDVTList VTs = getVTList(VT);
3385   FoldingSetNodeID ID;
3386   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, (SDOperand*)0, 0);
3387   void *IP = 0;
3388   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3389     return ON;
3390
3391   RemoveNodeFromCSEMaps(N);
3392
3393   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, SDOperandPtr(), 0);
3394
3395   CSEMap.InsertNode(N, IP);
3396   return N;
3397 }
3398
3399 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3400                                    MVT::ValueType VT, SDOperand Op1) {
3401   // If an identical node already exists, use it.
3402   SDVTList VTs = getVTList(VT);
3403   SDOperand Ops[] = { Op1 };
3404
3405   FoldingSetNodeID ID;
3406   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1);
3407   void *IP = 0;
3408   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3409     return ON;
3410
3411   RemoveNodeFromCSEMaps(N);
3412   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 1);
3413   CSEMap.InsertNode(N, IP);
3414   return N;
3415 }
3416
3417 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3418                                    MVT::ValueType VT, SDOperand Op1,
3419                                    SDOperand Op2) {
3420   // If an identical node already exists, use it.
3421   SDVTList VTs = getVTList(VT);
3422   SDOperand Ops[] = { Op1, Op2 };
3423
3424   FoldingSetNodeID ID;
3425   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3426   void *IP = 0;
3427   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3428     return ON;
3429
3430   RemoveNodeFromCSEMaps(N);
3431
3432   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3433
3434   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3435   return N;
3436 }
3437
3438 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3439                                    MVT::ValueType VT, SDOperand Op1,
3440                                    SDOperand Op2, SDOperand Op3) {
3441   // If an identical node already exists, use it.
3442   SDVTList VTs = getVTList(VT);
3443   SDOperand Ops[] = { Op1, Op2, Op3 };
3444   FoldingSetNodeID ID;
3445   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3446   void *IP = 0;
3447   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3448     return ON;
3449
3450   RemoveNodeFromCSEMaps(N);
3451
3452   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3453
3454   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3455   return N;
3456 }
3457
3458 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3459                                    MVT::ValueType VT, SDOperandPtr Ops,
3460                                    unsigned NumOps) {
3461   // If an identical node already exists, use it.
3462   SDVTList VTs = getVTList(VT);
3463   FoldingSetNodeID ID;
3464   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
3465   void *IP = 0;
3466   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3467     return ON;
3468
3469   RemoveNodeFromCSEMaps(N);
3470   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, NumOps);
3471
3472   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3473   return N;
3474 }
3475
3476 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3477                                    MVT::ValueType VT1, MVT::ValueType VT2,
3478                                    SDOperand Op1, SDOperand Op2) {
3479   SDVTList VTs = getVTList(VT1, VT2);
3480   FoldingSetNodeID ID;
3481   SDOperand Ops[] = { Op1, Op2 };
3482   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3483   void *IP = 0;
3484   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3485     return ON;
3486
3487   RemoveNodeFromCSEMaps(N);
3488   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 2);
3489   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3490   return N;
3491 }
3492
3493 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
3494                                    MVT::ValueType VT1, MVT::ValueType VT2,
3495                                    SDOperand Op1, SDOperand Op2,
3496                                    SDOperand Op3) {
3497   // If an identical node already exists, use it.
3498   SDVTList VTs = getVTList(VT1, VT2);
3499   SDOperand Ops[] = { Op1, Op2, Op3 };
3500   FoldingSetNodeID ID;
3501   AddNodeIDNode(ID, ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3502   void *IP = 0;
3503   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
3504     return ON;
3505
3506   RemoveNodeFromCSEMaps(N);
3507
3508   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc, VTs, Ops, 3);
3509   CSEMap.InsertNode(N, IP);   // Memoize the new node.
3510   return N;
3511 }
3512
3513
3514 /// getTargetNode - These are used for target selectors to create a new node
3515 /// with specified return type(s), target opcode, and operands.
3516 ///
3517 /// Note that getTargetNode returns the resultant node.  If there is already a
3518 /// node of the specified opcode and operands, it returns that node instead of
3519 /// the current one.
3520 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) {
3521   return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val;
3522 }
3523 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3524                                     SDOperand Op1) {
3525   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val;
3526 }
3527 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3528                                     SDOperand Op1, SDOperand Op2) {
3529   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val;
3530 }
3531 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3532                                     SDOperand Op1, SDOperand Op2,
3533                                     SDOperand Op3) {
3534   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
3535 }
3536 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
3537                                     SDOperandPtr Ops, unsigned NumOps) {
3538   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val;
3539 }
3540 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3541                                     MVT::ValueType VT2) {
3542   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3543   SDOperand Op;
3544   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op, 0).Val;
3545 }
3546 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3547                                     MVT::ValueType VT2, SDOperand Op1) {
3548   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3549   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val;
3550 }
3551 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3552                                     MVT::ValueType VT2, SDOperand Op1,
3553                                     SDOperand Op2) {
3554   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3555   SDOperand Ops[] = { Op1, Op2 };
3556   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val;
3557 }
3558 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3559                                     MVT::ValueType VT2, SDOperand Op1,
3560                                     SDOperand Op2, SDOperand Op3) {
3561   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3562   SDOperand Ops[] = { Op1, Op2, Op3 };
3563   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val;
3564 }
3565 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3566                                     MVT::ValueType VT2,
3567                                     SDOperandPtr Ops, unsigned NumOps) {
3568   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
3569   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val;
3570 }
3571 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3572                                     MVT::ValueType VT2, MVT::ValueType VT3,
3573                                     SDOperand Op1, SDOperand Op2) {
3574   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
3575   SDOperand Ops[] = { Op1, Op2 };
3576   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val;
3577 }
3578 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3579                                     MVT::ValueType VT2, MVT::ValueType VT3,
3580                                     SDOperand Op1, SDOperand Op2,
3581                                     SDOperand Op3) {
3582   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
3583   SDOperand Ops[] = { Op1, Op2, Op3 };
3584   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 3).Val;
3585 }
3586 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3587                                     MVT::ValueType VT2, MVT::ValueType VT3,
3588                                     SDOperandPtr Ops, unsigned NumOps) {
3589   const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3);
3590   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val;
3591 }
3592 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
3593                                     MVT::ValueType VT2, MVT::ValueType VT3,
3594                                     MVT::ValueType VT4,
3595                                     SDOperandPtr Ops, unsigned NumOps) {
3596   std::vector<MVT::ValueType> VTList;
3597   VTList.push_back(VT1);
3598   VTList.push_back(VT2);
3599   VTList.push_back(VT3);
3600   VTList.push_back(VT4);
3601   const MVT::ValueType *VTs = getNodeValueTypes(VTList);
3602   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 4, Ops, NumOps).Val;
3603 }
3604 SDNode *SelectionDAG::getTargetNode(unsigned Opcode,
3605                                     std::vector<MVT::ValueType> &ResultTys,
3606                                     SDOperandPtr Ops, unsigned NumOps) {
3607   const MVT::ValueType *VTs = getNodeValueTypes(ResultTys);
3608   return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, ResultTys.size(),
3609                  Ops, NumOps).Val;
3610 }
3611
3612 /// getNodeIfExists - Get the specified node if it's already available, or
3613 /// else return NULL.
3614 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList,
3615                                       SDOperandPtr Ops, unsigned NumOps) {
3616   if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) {
3617     FoldingSetNodeID ID;
3618     AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps);
3619     void *IP = 0;
3620     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
3621       return E;
3622   }
3623   return NULL;
3624 }
3625
3626
3627 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3628 /// This can cause recursive merging of nodes in the DAG.
3629 ///
3630 /// This version assumes From has a single result value.
3631 ///
3632 void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand To,
3633                                       DAGUpdateListener *UpdateListener) {
3634   SDNode *From = FromN.Val;
3635   assert(From->getNumValues() == 1 && FromN.ResNo == 0 &&
3636          "Cannot replace with this method!");
3637   assert(From != To.Val && "Cannot replace uses of with self");
3638
3639   while (!From->use_empty()) {
3640     SDNode::use_iterator UI = From->use_begin();
3641     SDNode *U = UI->getUser();
3642
3643     // This node is about to morph, remove its old self from the CSE maps.
3644     RemoveNodeFromCSEMaps(U);
3645     int operandNum = 0;
3646     for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
3647          I != E; ++I, ++operandNum)
3648       if (I->getVal() == From) {
3649         From->removeUser(operandNum, U);
3650         *I = To;
3651         I->setUser(U);
3652         To.Val->addUser(operandNum, U);
3653       }
3654
3655     // Now that we have modified U, add it back to the CSE maps.  If it already
3656     // exists there, recursively merge the results together.
3657     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
3658       ReplaceAllUsesWith(U, Existing, UpdateListener);
3659       // U is now dead.  Inform the listener if it exists and delete it.
3660       if (UpdateListener)
3661         UpdateListener->NodeDeleted(U);
3662       DeleteNodeNotInCSEMaps(U);
3663     } else {
3664       // If the node doesn't already exist, we updated it.  Inform a listener if
3665       // it exists.
3666       if (UpdateListener)
3667         UpdateListener->NodeUpdated(U);
3668     }
3669   }
3670 }
3671
3672 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3673 /// This can cause recursive merging of nodes in the DAG.
3674 ///
3675 /// This version assumes From/To have matching types and numbers of result
3676 /// values.
3677 ///
3678 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
3679                                       DAGUpdateListener *UpdateListener) {
3680   assert(From != To && "Cannot replace uses of with self");
3681   assert(From->getNumValues() == To->getNumValues() &&
3682          "Cannot use this version of ReplaceAllUsesWith!");
3683   if (From->getNumValues() == 1)   // If possible, use the faster version.
3684     return ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0),
3685                               UpdateListener);
3686
3687   while (!From->use_empty()) {
3688     SDNode::use_iterator UI = From->use_begin();
3689     SDNode *U = UI->getUser();
3690
3691     // This node is about to morph, remove its old self from the CSE maps.
3692     RemoveNodeFromCSEMaps(U);
3693     int operandNum = 0;
3694     for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
3695          I != E; ++I, ++operandNum)
3696       if (I->getVal() == From) {
3697         From->removeUser(operandNum, U);
3698         I->getVal() = To;
3699         To->addUser(operandNum, U);
3700       }
3701
3702     // Now that we have modified U, add it back to the CSE maps.  If it already
3703     // exists there, recursively merge the results together.
3704     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
3705       ReplaceAllUsesWith(U, Existing, UpdateListener);
3706       // U is now dead.  Inform the listener if it exists and delete it.
3707       if (UpdateListener)
3708         UpdateListener->NodeDeleted(U);
3709       DeleteNodeNotInCSEMaps(U);
3710     } else {
3711       // If the node doesn't already exist, we updated it.  Inform a listener if
3712       // it exists.
3713       if (UpdateListener)
3714         UpdateListener->NodeUpdated(U);
3715     }
3716   }
3717 }
3718
3719 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
3720 /// This can cause recursive merging of nodes in the DAG.
3721 ///
3722 /// This version can replace From with any result values.  To must match the
3723 /// number and types of values returned by From.
3724 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
3725                                       SDOperandPtr To,
3726                                       DAGUpdateListener *UpdateListener) {
3727   if (From->getNumValues() == 1)  // Handle the simple case efficiently.
3728     return ReplaceAllUsesWith(SDOperand(From, 0), To[0], UpdateListener);
3729
3730   while (!From->use_empty()) {
3731     SDNode::use_iterator UI = From->use_begin();
3732     SDNode *U = UI->getUser();
3733
3734     // This node is about to morph, remove its old self from the CSE maps.
3735     RemoveNodeFromCSEMaps(U);
3736     int operandNum = 0;
3737     for (SDNode::op_iterator I = U->op_begin(), E = U->op_end();
3738          I != E; ++I, ++operandNum)
3739       if (I->getVal() == From) {
3740         const SDOperand &ToOp = To[I->getSDOperand().ResNo];
3741         From->removeUser(operandNum, U);
3742         *I = ToOp;
3743         I->setUser(U);
3744         ToOp.Val->addUser(operandNum, U);
3745       }
3746
3747     // Now that we have modified U, add it back to the CSE maps.  If it already
3748     // exists there, recursively merge the results together.
3749     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
3750       ReplaceAllUsesWith(U, Existing, UpdateListener);
3751       // U is now dead.  Inform the listener if it exists and delete it.
3752       if (UpdateListener)
3753         UpdateListener->NodeDeleted(U);
3754       DeleteNodeNotInCSEMaps(U);
3755     } else {
3756       // If the node doesn't already exist, we updated it.  Inform a listener if
3757       // it exists.
3758       if (UpdateListener)
3759         UpdateListener->NodeUpdated(U);
3760     }
3761   }
3762 }
3763
3764 namespace {
3765   /// ChainedSetUpdaterListener - This class is a DAGUpdateListener that removes
3766   /// any deleted nodes from the set passed into its constructor and recursively
3767   /// notifies another update listener if specified.
3768   class ChainedSetUpdaterListener :
3769   public SelectionDAG::DAGUpdateListener {
3770     SmallSetVector<SDNode*, 16> &Set;
3771     SelectionDAG::DAGUpdateListener *Chain;
3772   public:
3773     ChainedSetUpdaterListener(SmallSetVector<SDNode*, 16> &set,
3774                               SelectionDAG::DAGUpdateListener *chain)
3775       : Set(set), Chain(chain) {}
3776
3777     virtual void NodeDeleted(SDNode *N) {
3778       Set.remove(N);
3779       if (Chain) Chain->NodeDeleted(N);
3780     }
3781     virtual void NodeUpdated(SDNode *N) {
3782       if (Chain) Chain->NodeUpdated(N);
3783     }
3784   };
3785 }
3786
3787 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
3788 /// uses of other values produced by From.Val alone.  The Deleted vector is
3789 /// handled the same way as for ReplaceAllUsesWith.
3790 void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
3791                                              DAGUpdateListener *UpdateListener){
3792   assert(From != To && "Cannot replace a value with itself");
3793
3794   // Handle the simple, trivial, case efficiently.
3795   if (From.Val->getNumValues() == 1) {
3796     ReplaceAllUsesWith(From, To, UpdateListener);
3797     return;
3798   }
3799
3800   if (From.use_empty()) return;
3801
3802   // Get all of the users of From.Val.  We want these in a nice,
3803   // deterministically ordered and uniqued set, so we use a SmallSetVector.
3804   SmallSetVector<SDNode*, 16> Users;
3805   for (SDNode::use_iterator UI = From.Val->use_begin(),
3806       E = From.Val->use_end(); UI != E; ++UI) {
3807     SDNode *User = UI->getUser();
3808     if (!Users.count(User))
3809       Users.insert(User);
3810   }
3811
3812   // When one of the recursive merges deletes nodes from the graph, we need to
3813   // make sure that UpdateListener is notified *and* that the node is removed
3814   // from Users if present.  CSUL does this.
3815   ChainedSetUpdaterListener CSUL(Users, UpdateListener);
3816
3817   while (!Users.empty()) {
3818     // We know that this user uses some value of From.  If it is the right
3819     // value, update it.
3820     SDNode *User = Users.back();
3821     Users.pop_back();
3822
3823     // Scan for an operand that matches From.
3824     SDNode::op_iterator Op = User->op_begin(), E = User->op_end();
3825     for (; Op != E; ++Op)
3826       if (*Op == From) break;
3827
3828     // If there are no matches, the user must use some other result of From.
3829     if (Op == E) continue;
3830
3831     // Okay, we know this user needs to be updated.  Remove its old self
3832     // from the CSE maps.
3833     RemoveNodeFromCSEMaps(User);
3834
3835     // Update all operands that match "From" in case there are multiple uses.
3836     for (; Op != E; ++Op) {
3837       if (*Op == From) {
3838         From.Val->removeUser(Op-User->op_begin(), User);
3839         *Op = To;
3840         Op->setUser(User);
3841         To.Val->addUser(Op-User->op_begin(), User);
3842       }
3843     }
3844
3845     // Now that we have modified User, add it back to the CSE maps.  If it
3846     // already exists there, recursively merge the results together.
3847     SDNode *Existing = AddNonLeafNodeToCSEMaps(User);
3848     if (!Existing) {
3849       if (UpdateListener) UpdateListener->NodeUpdated(User);
3850       continue;  // Continue on to next user.
3851     }
3852
3853     // If there was already an existing matching node, use ReplaceAllUsesWith
3854     // to replace the dead one with the existing one.  This can cause
3855     // recursive merging of other unrelated nodes down the line.  The merging
3856     // can cause deletion of nodes that used the old value.  To handle this, we
3857     // use CSUL to remove them from the Users set.
3858     ReplaceAllUsesWith(User, Existing, &CSUL);
3859
3860     // User is now dead.  Notify a listener if present.
3861     if (UpdateListener) UpdateListener->NodeDeleted(User);
3862     DeleteNodeNotInCSEMaps(User);
3863   }
3864 }
3865
3866 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on
3867 /// their allnodes order. It returns the maximum id.
3868 unsigned SelectionDAG::AssignNodeIds() {
3869   unsigned Id = 0;
3870   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){
3871     SDNode *N = I;
3872     N->setNodeId(Id++);
3873   }
3874   return Id;
3875 }
3876
3877 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
3878 /// based on their topological order. It returns the maximum id and a vector
3879 /// of the SDNodes* in assigned order by reference.
3880 unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
3881   unsigned DAGSize = AllNodes.size();
3882   std::vector<unsigned> InDegree(DAGSize);
3883   std::vector<SDNode*> Sources;
3884
3885   // Use a two pass approach to avoid using a std::map which is slow.
3886   unsigned Id = 0;
3887   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
3888     SDNode *N = I;
3889     N->setNodeId(Id++);
3890     unsigned Degree = N->use_size();
3891     InDegree[N->getNodeId()] = Degree;
3892     if (Degree == 0)
3893       Sources.push_back(N);
3894   }
3895
3896   TopOrder.clear();
3897   while (!Sources.empty()) {
3898     SDNode *N = Sources.back();
3899     Sources.pop_back();
3900     TopOrder.push_back(N);
3901     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
3902       SDNode *P = I->getVal();
3903       unsigned Degree = --InDegree[P->getNodeId()];
3904       if (Degree == 0)
3905         Sources.push_back(P);
3906     }
3907   }
3908
3909   // Second pass, assign the actual topological order as node ids.
3910   Id = 0;
3911   for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end();
3912        TI != TE; ++TI)
3913     (*TI)->setNodeId(Id++);
3914
3915   return Id;
3916 }
3917
3918
3919
3920 //===----------------------------------------------------------------------===//
3921 //                              SDNode Class
3922 //===----------------------------------------------------------------------===//
3923
3924 // Out-of-line virtual method to give class a home.
3925 void SDNode::ANCHOR() {}
3926 void UnarySDNode::ANCHOR() {}
3927 void BinarySDNode::ANCHOR() {}
3928 void TernarySDNode::ANCHOR() {}
3929 void HandleSDNode::ANCHOR() {}
3930 void StringSDNode::ANCHOR() {}
3931 void ConstantSDNode::ANCHOR() {}
3932 void ConstantFPSDNode::ANCHOR() {}
3933 void GlobalAddressSDNode::ANCHOR() {}
3934 void FrameIndexSDNode::ANCHOR() {}
3935 void JumpTableSDNode::ANCHOR() {}
3936 void ConstantPoolSDNode::ANCHOR() {}
3937 void BasicBlockSDNode::ANCHOR() {}
3938 void SrcValueSDNode::ANCHOR() {}
3939 void MemOperandSDNode::ANCHOR() {}
3940 void RegisterSDNode::ANCHOR() {}
3941 void ExternalSymbolSDNode::ANCHOR() {}
3942 void CondCodeSDNode::ANCHOR() {}
3943 void ARG_FLAGSSDNode::ANCHOR() {}
3944 void VTSDNode::ANCHOR() {}
3945 void LoadSDNode::ANCHOR() {}
3946 void StoreSDNode::ANCHOR() {}
3947 void AtomicSDNode::ANCHOR() {}
3948
3949 HandleSDNode::~HandleSDNode() {
3950   SDVTList VTs = { 0, 0 };
3951   MorphNodeTo(ISD::HANDLENODE, VTs, SDOperandPtr(), 0);  // Drops operand uses.
3952 }
3953
3954 GlobalAddressSDNode::GlobalAddressSDNode(bool isTarget, const GlobalValue *GA,
3955                                          MVT::ValueType VT, int o)
3956   : SDNode(isa<GlobalVariable>(GA) &&
3957            cast<GlobalVariable>(GA)->isThreadLocal() ?
3958            // Thread Local
3959            (isTarget ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress) :
3960            // Non Thread Local
3961            (isTarget ? ISD::TargetGlobalAddress : ISD::GlobalAddress),
3962            getSDVTList(VT)), Offset(o) {
3963   TheGlobal = const_cast<GlobalValue*>(GA);
3964 }
3965
3966 /// getMemOperand - Return a MachineMemOperand object describing the memory
3967 /// reference performed by this load or store.
3968 MachineMemOperand LSBaseSDNode::getMemOperand() const {
3969   int Size = (MVT::getSizeInBits(getMemoryVT()) + 7) >> 3;
3970   int Flags =
3971     getOpcode() == ISD::LOAD ? MachineMemOperand::MOLoad :
3972                                MachineMemOperand::MOStore;
3973   if (IsVolatile) Flags |= MachineMemOperand::MOVolatile;
3974
3975   // Check if the load references a frame index, and does not have
3976   // an SV attached.
3977   const FrameIndexSDNode *FI =
3978     dyn_cast<const FrameIndexSDNode>(getBasePtr().Val);
3979   if (!getSrcValue() && FI)
3980     return MachineMemOperand(PseudoSourceValue::getFixedStack(), Flags,
3981                              FI->getIndex(), Size, Alignment);
3982   else
3983     return MachineMemOperand(getSrcValue(), Flags,
3984                              getSrcValueOffset(), Size, Alignment);
3985 }
3986
3987 /// Profile - Gather unique data for the node.
3988 ///
3989 void SDNode::Profile(FoldingSetNodeID &ID) {
3990   AddNodeIDNode(ID, this);
3991 }
3992
3993 /// getValueTypeList - Return a pointer to the specified value type.
3994 ///
3995 const MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
3996   if (MVT::isExtendedVT(VT)) {
3997     static std::set<MVT::ValueType> EVTs;
3998     return &(*EVTs.insert(VT).first);
3999   } else {
4000     static MVT::ValueType VTs[MVT::LAST_VALUETYPE];
4001     VTs[VT] = VT;
4002     return &VTs[VT];
4003   }
4004 }
4005
4006 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
4007 /// indicated value.  This method ignores uses of other values defined by this
4008 /// operation.
4009 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
4010   assert(Value < getNumValues() && "Bad value!");
4011
4012   // If there is only one value, this is easy.
4013   if (getNumValues() == 1)
4014     return use_size() == NUses;
4015   if (use_size() < NUses) return false;
4016
4017   SDOperand TheValue(const_cast<SDNode *>(this), Value);
4018
4019   SmallPtrSet<SDNode*, 32> UsersHandled;
4020
4021   // TODO: Only iterate over uses of a given value of the node
4022   for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
4023     if (*UI == TheValue) {
4024       if (NUses == 0)
4025         return false;
4026       --NUses;
4027     }
4028   }
4029
4030   // Found exactly the right number of uses?
4031   return NUses == 0;
4032 }
4033
4034
4035 /// hasAnyUseOfValue - Return true if there are any use of the indicated
4036 /// value. This method ignores uses of other values defined by this operation.
4037 bool SDNode::hasAnyUseOfValue(unsigned Value) const {
4038   assert(Value < getNumValues() && "Bad value!");
4039
4040   if (use_empty()) return false;
4041
4042   SDOperand TheValue(const_cast<SDNode *>(this), Value);
4043
4044   SmallPtrSet<SDNode*, 32> UsersHandled;
4045
4046   for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) {
4047     SDNode *User = UI->getUser();
4048     if (User->getNumOperands() == 1 ||
4049         UsersHandled.insert(User))     // First time we've seen this?
4050       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
4051         if (User->getOperand(i) == TheValue) {
4052           return true;
4053         }
4054   }
4055
4056   return false;
4057 }
4058
4059
4060 /// isOnlyUseOf - Return true if this node is the only use of N.
4061 ///
4062 bool SDNode::isOnlyUseOf(SDNode *N) const {
4063   bool Seen = false;
4064   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
4065     SDNode *User = I->getUser();
4066     if (User == this)
4067       Seen = true;
4068     else
4069       return false;
4070   }
4071
4072   return Seen;
4073 }
4074
4075 /// isOperand - Return true if this node is an operand of N.
4076 ///
4077 bool SDOperand::isOperandOf(SDNode *N) const {
4078   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
4079     if (*this == N->getOperand(i))
4080       return true;
4081   return false;
4082 }
4083
4084 bool SDNode::isOperandOf(SDNode *N) const {
4085   for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
4086     if (this == N->OperandList[i].getVal())
4087       return true;
4088   return false;
4089 }
4090
4091 /// reachesChainWithoutSideEffects - Return true if this operand (which must
4092 /// be a chain) reaches the specified operand without crossing any
4093 /// side-effecting instructions.  In practice, this looks through token
4094 /// factors and non-volatile loads.  In order to remain efficient, this only
4095 /// looks a couple of nodes in, it does not do an exhaustive search.
4096 bool SDOperand::reachesChainWithoutSideEffects(SDOperand Dest,
4097                                                unsigned Depth) const {
4098   if (*this == Dest) return true;
4099
4100   // Don't search too deeply, we just want to be able to see through
4101   // TokenFactor's etc.
4102   if (Depth == 0) return false;
4103
4104   // If this is a token factor, all inputs to the TF happen in parallel.  If any
4105   // of the operands of the TF reach dest, then we can do the xform.
4106   if (getOpcode() == ISD::TokenFactor) {
4107     for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
4108       if (getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1))
4109         return true;
4110     return false;
4111   }
4112
4113   // Loads don't have side effects, look through them.
4114   if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) {
4115     if (!Ld->isVolatile())
4116       return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1);
4117   }
4118   return false;
4119 }
4120
4121
4122 static void findPredecessor(SDNode *N, const SDNode *P, bool &found,
4123                             SmallPtrSet<SDNode *, 32> &Visited) {
4124   if (found || !Visited.insert(N))
4125     return;
4126
4127   for (unsigned i = 0, e = N->getNumOperands(); !found && i != e; ++i) {
4128     SDNode *Op = N->getOperand(i).Val;
4129     if (Op == P) {
4130       found = true;
4131       return;
4132     }
4133     findPredecessor(Op, P, found, Visited);
4134   }
4135 }
4136
4137 /// isPredecessorOf - Return true if this node is a predecessor of N. This node
4138 /// is either an operand of N or it can be reached by recursively traversing
4139 /// up the operands.
4140 /// NOTE: this is an expensive method. Use it carefully.
4141 bool SDNode::isPredecessorOf(SDNode *N) const {
4142   SmallPtrSet<SDNode *, 32> Visited;
4143   bool found = false;
4144   findPredecessor(N, this, found, Visited);
4145   return found;
4146 }
4147
4148 uint64_t SDNode::getConstantOperandVal(unsigned Num) const {
4149   assert(Num < NumOperands && "Invalid child # of SDNode!");
4150   return cast<ConstantSDNode>(OperandList[Num])->getValue();
4151 }
4152
4153 std::string SDNode::getOperationName(const SelectionDAG *G) const {
4154   switch (getOpcode()) {
4155   default:
4156     if (getOpcode() < ISD::BUILTIN_OP_END)
4157       return "<<Unknown DAG Node>>";
4158     else {
4159       if (G) {
4160         if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
4161           if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
4162             return TII->get(getOpcode()-ISD::BUILTIN_OP_END).getName();
4163
4164         TargetLowering &TLI = G->getTargetLoweringInfo();
4165         const char *Name =
4166           TLI.getTargetNodeName(getOpcode());
4167         if (Name) return Name;
4168       }
4169
4170       return "<<Unknown Target Node>>";
4171     }
4172
4173   case ISD::PREFETCH:      return "Prefetch";
4174   case ISD::MEMBARRIER:    return "MemBarrier";
4175   case ISD::ATOMIC_LCS:    return "AtomicLCS";
4176   case ISD::ATOMIC_LAS:    return "AtomicLAS";
4177   case ISD::ATOMIC_SWAP:    return "AtomicSWAP";
4178   case ISD::PCMARKER:      return "PCMarker";
4179   case ISD::READCYCLECOUNTER: return "ReadCycleCounter";
4180   case ISD::SRCVALUE:      return "SrcValue";
4181   case ISD::MEMOPERAND:    return "MemOperand";
4182   case ISD::EntryToken:    return "EntryToken";
4183   case ISD::TokenFactor:   return "TokenFactor";
4184   case ISD::AssertSext:    return "AssertSext";
4185   case ISD::AssertZext:    return "AssertZext";
4186
4187   case ISD::STRING:        return "String";
4188   case ISD::BasicBlock:    return "BasicBlock";
4189   case ISD::ARG_FLAGS:     return "ArgFlags";
4190   case ISD::VALUETYPE:     return "ValueType";
4191   case ISD::Register:      return "Register";
4192
4193   case ISD::Constant:      return "Constant";
4194   case ISD::ConstantFP:    return "ConstantFP";
4195   case ISD::GlobalAddress: return "GlobalAddress";
4196   case ISD::GlobalTLSAddress: return "GlobalTLSAddress";
4197   case ISD::FrameIndex:    return "FrameIndex";
4198   case ISD::JumpTable:     return "JumpTable";
4199   case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE";
4200   case ISD::RETURNADDR: return "RETURNADDR";
4201   case ISD::FRAMEADDR: return "FRAMEADDR";
4202   case ISD::FRAME_TO_ARGS_OFFSET: return "FRAME_TO_ARGS_OFFSET";
4203   case ISD::EXCEPTIONADDR: return "EXCEPTIONADDR";
4204   case ISD::EHSELECTION: return "EHSELECTION";
4205   case ISD::EH_RETURN: return "EH_RETURN";
4206   case ISD::ConstantPool:  return "ConstantPool";
4207   case ISD::ExternalSymbol: return "ExternalSymbol";
4208   case ISD::INTRINSIC_WO_CHAIN: {
4209     unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue();
4210     return Intrinsic::getName((Intrinsic::ID)IID);
4211   }
4212   case ISD::INTRINSIC_VOID:
4213   case ISD::INTRINSIC_W_CHAIN: {
4214     unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue();
4215     return Intrinsic::getName((Intrinsic::ID)IID);
4216   }
4217
4218   case ISD::BUILD_VECTOR:   return "BUILD_VECTOR";
4219   case ISD::TargetConstant: return "TargetConstant";
4220   case ISD::TargetConstantFP:return "TargetConstantFP";
4221   case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
4222   case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress";
4223   case ISD::TargetFrameIndex: return "TargetFrameIndex";
4224   case ISD::TargetJumpTable:  return "TargetJumpTable";
4225   case ISD::TargetConstantPool:  return "TargetConstantPool";
4226   case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
4227
4228   case ISD::CopyToReg:     return "CopyToReg";
4229   case ISD::CopyFromReg:   return "CopyFromReg";
4230   case ISD::UNDEF:         return "undef";
4231   case ISD::MERGE_VALUES:  return "merge_values";
4232   case ISD::INLINEASM:     return "inlineasm";
4233   case ISD::LABEL:         return "label";
4234   case ISD::DECLARE:       return "declare";
4235   case ISD::HANDLENODE:    return "handlenode";
4236   case ISD::FORMAL_ARGUMENTS: return "formal_arguments";
4237   case ISD::CALL:          return "call";
4238
4239   // Unary operators
4240   case ISD::FABS:   return "fabs";
4241   case ISD::FNEG:   return "fneg";
4242   case ISD::FSQRT:  return "fsqrt";
4243   case ISD::FSIN:   return "fsin";
4244   case ISD::FCOS:   return "fcos";
4245   case ISD::FPOWI:  return "fpowi";
4246   case ISD::FPOW:   return "fpow";
4247
4248   // Binary operators
4249   case ISD::ADD:    return "add";
4250   case ISD::SUB:    return "sub";
4251   case ISD::MUL:    return "mul";
4252   case ISD::MULHU:  return "mulhu";
4253   case ISD::MULHS:  return "mulhs";
4254   case ISD::SDIV:   return "sdiv";
4255   case ISD::UDIV:   return "udiv";
4256   case ISD::SREM:   return "srem";
4257   case ISD::UREM:   return "urem";
4258   case ISD::SMUL_LOHI:  return "smul_lohi";
4259   case ISD::UMUL_LOHI:  return "umul_lohi";
4260   case ISD::SDIVREM:    return "sdivrem";
4261   case ISD::UDIVREM:    return "divrem";
4262   case ISD::AND:    return "and";
4263   case ISD::OR:     return "or";
4264   case ISD::XOR:    return "xor";
4265   case ISD::SHL:    return "shl";
4266   case ISD::SRA:    return "sra";
4267   case ISD::SRL:    return "srl";
4268   case ISD::ROTL:   return "rotl";
4269   case ISD::ROTR:   return "rotr";
4270   case ISD::FADD:   return "fadd";
4271   case ISD::FSUB:   return "fsub";
4272   case ISD::FMUL:   return "fmul";
4273   case ISD::FDIV:   return "fdiv";
4274   case ISD::FREM:   return "frem";
4275   case ISD::FCOPYSIGN: return "fcopysign";
4276   case ISD::FGETSIGN:  return "fgetsign";
4277
4278   case ISD::SETCC:       return "setcc";
4279   case ISD::SELECT:      return "select";
4280   case ISD::SELECT_CC:   return "select_cc";
4281   case ISD::INSERT_VECTOR_ELT:   return "insert_vector_elt";
4282   case ISD::EXTRACT_VECTOR_ELT:  return "extract_vector_elt";
4283   case ISD::CONCAT_VECTORS:      return "concat_vectors";
4284   case ISD::EXTRACT_SUBVECTOR:   return "extract_subvector";
4285   case ISD::SCALAR_TO_VECTOR:    return "scalar_to_vector";
4286   case ISD::VECTOR_SHUFFLE:      return "vector_shuffle";
4287   case ISD::CARRY_FALSE:         return "carry_false";
4288   case ISD::ADDC:        return "addc";
4289   case ISD::ADDE:        return "adde";
4290   case ISD::SUBC:        return "subc";
4291   case ISD::SUBE:        return "sube";
4292   case ISD::SHL_PARTS:   return "shl_parts";
4293   case ISD::SRA_PARTS:   return "sra_parts";
4294   case ISD::SRL_PARTS:   return "srl_parts";
4295
4296   case ISD::EXTRACT_SUBREG:     return "extract_subreg";
4297   case ISD::INSERT_SUBREG:      return "insert_subreg";
4298
4299   // Conversion operators.
4300   case ISD::SIGN_EXTEND: return "sign_extend";
4301   case ISD::ZERO_EXTEND: return "zero_extend";
4302   case ISD::ANY_EXTEND:  return "any_extend";
4303   case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
4304   case ISD::TRUNCATE:    return "truncate";
4305   case ISD::FP_ROUND:    return "fp_round";
4306   case ISD::FLT_ROUNDS_: return "flt_rounds";
4307   case ISD::FP_ROUND_INREG: return "fp_round_inreg";
4308   case ISD::FP_EXTEND:   return "fp_extend";
4309
4310   case ISD::SINT_TO_FP:  return "sint_to_fp";
4311   case ISD::UINT_TO_FP:  return "uint_to_fp";
4312   case ISD::FP_TO_SINT:  return "fp_to_sint";
4313   case ISD::FP_TO_UINT:  return "fp_to_uint";
4314   case ISD::BIT_CONVERT: return "bit_convert";
4315
4316     // Control flow instructions
4317   case ISD::BR:      return "br";
4318   case ISD::BRIND:   return "brind";
4319   case ISD::BR_JT:   return "br_jt";
4320   case ISD::BRCOND:  return "brcond";
4321   case ISD::BR_CC:   return "br_cc";
4322   case ISD::RET:     return "ret";
4323   case ISD::CALLSEQ_START:  return "callseq_start";
4324   case ISD::CALLSEQ_END:    return "callseq_end";
4325
4326     // Other operators
4327   case ISD::LOAD:               return "load";
4328   case ISD::STORE:              return "store";
4329   case ISD::VAARG:              return "vaarg";
4330   case ISD::VACOPY:             return "vacopy";
4331   case ISD::VAEND:              return "vaend";
4332   case ISD::VASTART:            return "vastart";
4333   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
4334   case ISD::EXTRACT_ELEMENT:    return "extract_element";
4335   case ISD::BUILD_PAIR:         return "build_pair";
4336   case ISD::STACKSAVE:          return "stacksave";
4337   case ISD::STACKRESTORE:       return "stackrestore";
4338   case ISD::TRAP:               return "trap";
4339
4340   // Bit manipulation
4341   case ISD::BSWAP:   return "bswap";
4342   case ISD::CTPOP:   return "ctpop";
4343   case ISD::CTTZ:    return "cttz";
4344   case ISD::CTLZ:    return "ctlz";
4345
4346   // Debug info
4347   case ISD::LOCATION: return "location";
4348   case ISD::DEBUG_LOC: return "debug_loc";
4349
4350   // Trampolines
4351   case ISD::TRAMPOLINE: return "trampoline";
4352
4353   case ISD::CONDCODE:
4354     switch (cast<CondCodeSDNode>(this)->get()) {
4355     default: assert(0 && "Unknown setcc condition!");
4356     case ISD::SETOEQ:  return "setoeq";
4357     case ISD::SETOGT:  return "setogt";
4358     case ISD::SETOGE:  return "setoge";
4359     case ISD::SETOLT:  return "setolt";
4360     case ISD::SETOLE:  return "setole";
4361     case ISD::SETONE:  return "setone";
4362
4363     case ISD::SETO:    return "seto";
4364     case ISD::SETUO:   return "setuo";
4365     case ISD::SETUEQ:  return "setue";
4366     case ISD::SETUGT:  return "setugt";
4367     case ISD::SETUGE:  return "setuge";
4368     case ISD::SETULT:  return "setult";
4369     case ISD::SETULE:  return "setule";
4370     case ISD::SETUNE:  return "setune";
4371
4372     case ISD::SETEQ:   return "seteq";
4373     case ISD::SETGT:   return "setgt";
4374     case ISD::SETGE:   return "setge";
4375     case ISD::SETLT:   return "setlt";
4376     case ISD::SETLE:   return "setle";
4377     case ISD::SETNE:   return "setne";
4378     }
4379   }
4380 }
4381
4382 const char *SDNode::getIndexedModeName(ISD::MemIndexedMode AM) {
4383   switch (AM) {
4384   default:
4385     return "";
4386   case ISD::PRE_INC:
4387     return "<pre-inc>";
4388   case ISD::PRE_DEC:
4389     return "<pre-dec>";
4390   case ISD::POST_INC:
4391     return "<post-inc>";
4392   case ISD::POST_DEC:
4393     return "<post-dec>";
4394   }
4395 }
4396
4397 std::string ISD::ArgFlagsTy::getArgFlagsString() {
4398   std::string S = "< ";
4399
4400   if (isZExt())
4401     S += "zext ";
4402   if (isSExt())
4403     S += "sext ";
4404   if (isInReg())
4405     S += "inreg ";
4406   if (isSRet())
4407     S += "sret ";
4408   if (isByVal())
4409     S += "byval ";
4410   if (isNest())
4411     S += "nest ";
4412   if (getByValAlign())
4413     S += "byval-align:" + utostr(getByValAlign()) + " ";
4414   if (getOrigAlign())
4415     S += "orig-align:" + utostr(getOrigAlign()) + " ";
4416   if (getByValSize())
4417     S += "byval-size:" + utostr(getByValSize()) + " ";
4418   return S + ">";
4419 }
4420
4421 void SDNode::dump() const { dump(0); }
4422 void SDNode::dump(const SelectionDAG *G) const {
4423   cerr << (void*)this << ": ";
4424
4425   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
4426     if (i) cerr << ",";
4427     if (getValueType(i) == MVT::Other)
4428       cerr << "ch";
4429     else
4430       cerr << MVT::getValueTypeString(getValueType(i));
4431   }
4432   cerr << " = " << getOperationName(G);
4433
4434   cerr << " ";
4435   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
4436     if (i) cerr << ", ";
4437     cerr << (void*)getOperand(i).Val;
4438     if (unsigned RN = getOperand(i).ResNo)
4439       cerr << ":" << RN;
4440   }
4441
4442   if (!isTargetOpcode() && getOpcode() == ISD::VECTOR_SHUFFLE) {
4443     SDNode *Mask = getOperand(2).Val;
4444     cerr << "<";
4445     for (unsigned i = 0, e = Mask->getNumOperands(); i != e; ++i) {
4446       if (i) cerr << ",";
4447       if (Mask->getOperand(i).getOpcode() == ISD::UNDEF)
4448         cerr << "u";
4449       else
4450         cerr << cast<ConstantSDNode>(Mask->getOperand(i))->getValue();
4451     }
4452     cerr << ">";
4453   }
4454
4455   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
4456     cerr << "<" << CSDN->getValue() << ">";
4457   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
4458     if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEsingle)
4459       cerr << "<" << CSDN->getValueAPF().convertToFloat() << ">";
4460     else if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEdouble)
4461       cerr << "<" << CSDN->getValueAPF().convertToDouble() << ">";
4462     else {
4463       cerr << "<APFloat(";
4464       CSDN->getValueAPF().convertToAPInt().dump();
4465       cerr << ")>";
4466     }
4467   } else if (const GlobalAddressSDNode *GADN =
4468              dyn_cast<GlobalAddressSDNode>(this)) {
4469     int offset = GADN->getOffset();
4470     cerr << "<";
4471     WriteAsOperand(*cerr.stream(), GADN->getGlobal()) << ">";
4472     if (offset > 0)
4473       cerr << " + " << offset;
4474     else
4475       cerr << " " << offset;
4476   } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
4477     cerr << "<" << FIDN->getIndex() << ">";
4478   } else if (const JumpTableSDNode *JTDN = dyn_cast<JumpTableSDNode>(this)) {
4479     cerr << "<" << JTDN->getIndex() << ">";
4480   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
4481     int offset = CP->getOffset();
4482     if (CP->isMachineConstantPoolEntry())
4483       cerr << "<" << *CP->getMachineCPVal() << ">";
4484     else
4485       cerr << "<" << *CP->getConstVal() << ">";
4486     if (offset > 0)
4487       cerr << " + " << offset;
4488     else
4489       cerr << " " << offset;
4490   } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
4491     cerr << "<";
4492     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
4493     if (LBB)
4494       cerr << LBB->getName() << " ";
4495     cerr << (const void*)BBDN->getBasicBlock() << ">";
4496   } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
4497     if (G && R->getReg() &&
4498         TargetRegisterInfo::isPhysicalRegister(R->getReg())) {
4499       cerr << " " << G->getTarget().getRegisterInfo()->getName(R->getReg());
4500     } else {
4501       cerr << " #" << R->getReg();
4502     }
4503   } else if (const ExternalSymbolSDNode *ES =
4504              dyn_cast<ExternalSymbolSDNode>(this)) {
4505     cerr << "'" << ES->getSymbol() << "'";
4506   } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
4507     if (M->getValue())
4508       cerr << "<" << M->getValue() << ">";
4509     else
4510       cerr << "<null>";
4511   } else if (const MemOperandSDNode *M = dyn_cast<MemOperandSDNode>(this)) {
4512     if (M->MO.getValue())
4513       cerr << "<" << M->MO.getValue() << ":" << M->MO.getOffset() << ">";
4514     else
4515       cerr << "<null:" << M->MO.getOffset() << ">";
4516   } else if (const ARG_FLAGSSDNode *N = dyn_cast<ARG_FLAGSSDNode>(this)) {
4517     cerr << N->getArgFlags().getArgFlagsString();
4518   } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
4519     cerr << ":" << MVT::getValueTypeString(N->getVT());
4520   } else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) {
4521     const Value *SrcValue = LD->getSrcValue();
4522     int SrcOffset = LD->getSrcValueOffset();
4523     cerr << " <";
4524     if (SrcValue)
4525       cerr << SrcValue;
4526     else
4527       cerr << "null";
4528     cerr << ":" << SrcOffset << ">";
4529
4530     bool doExt = true;
4531     switch (LD->getExtensionType()) {
4532     default: doExt = false; break;
4533     case ISD::EXTLOAD:
4534       cerr << " <anyext ";
4535       break;
4536     case ISD::SEXTLOAD:
4537       cerr << " <sext ";
4538       break;
4539     case ISD::ZEXTLOAD:
4540       cerr << " <zext ";
4541       break;
4542     }
4543     if (doExt)
4544       cerr << MVT::getValueTypeString(LD->getMemoryVT()) << ">";
4545
4546     const char *AM = getIndexedModeName(LD->getAddressingMode());
4547     if (*AM)
4548       cerr << " " << AM;
4549     if (LD->isVolatile())
4550       cerr << " <volatile>";
4551     cerr << " alignment=" << LD->getAlignment();
4552   } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) {
4553     const Value *SrcValue = ST->getSrcValue();
4554     int SrcOffset = ST->getSrcValueOffset();
4555     cerr << " <";
4556     if (SrcValue)
4557       cerr << SrcValue;
4558     else
4559       cerr << "null";
4560     cerr << ":" << SrcOffset << ">";
4561
4562     if (ST->isTruncatingStore())
4563       cerr << " <trunc "
4564            << MVT::getValueTypeString(ST->getMemoryVT()) << ">";
4565
4566     const char *AM = getIndexedModeName(ST->getAddressingMode());
4567     if (*AM)
4568       cerr << " " << AM;
4569     if (ST->isVolatile())
4570       cerr << " <volatile>";
4571     cerr << " alignment=" << ST->getAlignment();
4572   }
4573 }
4574
4575 static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
4576   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
4577     if (N->getOperand(i).Val->hasOneUse())
4578       DumpNodes(N->getOperand(i).Val, indent+2, G);
4579     else
4580       cerr << "\n" << std::string(indent+2, ' ')
4581            << (void*)N->getOperand(i).Val << ": <multiple use>";
4582
4583
4584   cerr << "\n" << std::string(indent, ' ');
4585   N->dump(G);
4586 }
4587
4588 void SelectionDAG::dump() const {
4589   cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
4590   std::vector<const SDNode*> Nodes;
4591   for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
4592        I != E; ++I)
4593     Nodes.push_back(I);
4594
4595   std::sort(Nodes.begin(), Nodes.end());
4596
4597   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
4598     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
4599       DumpNodes(Nodes[i], 2, this);
4600   }
4601
4602   if (getRoot().Val) DumpNodes(getRoot().Val, 2, this);
4603
4604   cerr << "\n\n";
4605 }
4606
4607 const Type *ConstantPoolSDNode::getType() const {
4608   if (isMachineConstantPoolEntry())
4609     return Val.MachineCPVal->getType();
4610   return Val.ConstVal->getType();
4611 }