lib/CodeGen/SelectionDAG/SelectionDAG.cpp

   1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the SelectionDAG class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/SelectionDAG.h"
  15 #include "llvm/Constants.h"
  16 #include "llvm/GlobalValue.h"
  17 #include "llvm/Intrinsics.h"
  18 #include "llvm/Assembly/Writer.h"
  19 #include "llvm/CodeGen/MachineBasicBlock.h"
  20 #include "llvm/Support/MathExtras.h"
  21 #include "llvm/Target/MRegisterInfo.h"
  22 #include "llvm/Target/TargetLowering.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/ADT/SetVector.h"
  26 #include "llvm/ADT/SmallVector.h"
  27 #include "llvm/ADT/StringExtras.h"
  28 #include <iostream>
  29 #include <set>
  30 #include <cmath>
  31 #include <algorithm>
  32 using namespace llvm;
  33
  34 static bool isCommutativeBinOp(unsigned Opcode) {
  35   switch (Opcode) {
  36   case ISD::ADD:
  37   case ISD::MUL:
  38   case ISD::MULHU:
  39   case ISD::MULHS:
  40   case ISD::FADD:
  41   case ISD::FMUL:
  42   case ISD::AND:
  43   case ISD::OR:
  44   case ISD::XOR: return true;
  45   default: return false; // FIXME: Need commutative info for user ops!
  46   }
  47 }
  48
  49 // isInvertibleForFree - Return true if there is no cost to emitting the logical
  50 // inverse of this node.
  51 static bool isInvertibleForFree(SDOperand N) {
  52   if (isa<ConstantSDNode>(N.Val)) return true;
  53   if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse())
  54     return true;
  55   return false;
  56 }
  57
  58 //===----------------------------------------------------------------------===//
  59 //                              ConstantFPSDNode Class
  60 //===----------------------------------------------------------------------===//
  61
  62 /// isExactlyValue - We don't rely on operator== working on double values, as
  63 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
  64 /// As such, this method can be used to do an exact bit-for-bit comparison of
  65 /// two floating point values.
  66 bool ConstantFPSDNode::isExactlyValue(double V) const {
  67   return DoubleToBits(V) == DoubleToBits(Value);
  68 }
  69
  70 //===----------------------------------------------------------------------===//
  71 //                              ISD Namespace
  72 //===----------------------------------------------------------------------===//
  73
  74 /// isBuildVectorAllOnes - Return true if the specified node is a
  75 /// BUILD_VECTOR where all of the elements are ~0 or undef.
  76 bool ISD::isBuildVectorAllOnes(const SDNode *N) {
  77   // Look through a bit convert.
  78   if (N->getOpcode() == ISD::BIT_CONVERT)
  79     N = N->getOperand(0).Val;
  80
  81   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
  82
  83   unsigned i = 0, e = N->getNumOperands();
  84
  85   // Skip over all of the undef values.
  86   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
  87     ++i;
  88
  89   // Do not accept an all-undef vector.
  90   if (i == e) return false;
  91
  92   // Do not accept build_vectors that aren't all constants or which have non-~0
  93   // elements.
  94   SDOperand NotZero = N->getOperand(i);
  95   if (isa<ConstantSDNode>(NotZero)) {
  96     if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue())
  97       return false;
  98   } else if (isa<ConstantFPSDNode>(NotZero)) {
  99     MVT::ValueType VT = NotZero.getValueType();
 100     if (VT== MVT::f64) {
 101       if (DoubleToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) !=
 102           (uint64_t)-1)
 103         return false;
 104     } else {
 105       if (FloatToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) !=
 106           (uint32_t)-1)
 107         return false;
 108     }
 109   } else
 110     return false;
 111
 112   // Okay, we have at least one ~0 value, check to see if the rest match or are
 113   // undefs.
 114   for (++i; i != e; ++i)
 115     if (N->getOperand(i) != NotZero &&
 116         N->getOperand(i).getOpcode() != ISD::UNDEF)
 117       return false;
 118   return true;
 119 }
 120
 121
 122 /// isBuildVectorAllZeros - Return true if the specified node is a
 123 /// BUILD_VECTOR where all of the elements are 0 or undef.
 124 bool ISD::isBuildVectorAllZeros(const SDNode *N) {
 125   // Look through a bit convert.
 126   if (N->getOpcode() == ISD::BIT_CONVERT)
 127     N = N->getOperand(0).Val;
 128
 129   if (N->getOpcode() != ISD::BUILD_VECTOR) return false;
 130
 131   unsigned i = 0, e = N->getNumOperands();
 132
 133   // Skip over all of the undef values.
 134   while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF)
 135     ++i;
 136
 137   // Do not accept an all-undef vector.
 138   if (i == e) return false;
 139
 140   // Do not accept build_vectors that aren't all constants or which have non-~0
 141   // elements.
 142   SDOperand Zero = N->getOperand(i);
 143   if (isa<ConstantSDNode>(Zero)) {
 144     if (!cast<ConstantSDNode>(Zero)->isNullValue())
 145       return false;
 146   } else if (isa<ConstantFPSDNode>(Zero)) {
 147     if (!cast<ConstantFPSDNode>(Zero)->isExactlyValue(0.0))
 148       return false;
 149   } else
 150     return false;
 151
 152   // Okay, we have at least one ~0 value, check to see if the rest match or are
 153   // undefs.
 154   for (++i; i != e; ++i)
 155     if (N->getOperand(i) != Zero &&
 156         N->getOperand(i).getOpcode() != ISD::UNDEF)
 157       return false;
 158   return true;
 159 }
 160
 161 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
 162 /// when given the operation for (X op Y).
 163 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
 164   // To perform this operation, we just need to swap the L and G bits of the
 165   // operation.
 166   unsigned OldL = (Operation >> 2) & 1;
 167   unsigned OldG = (Operation >> 1) & 1;
 168   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
 169                        (OldL << 1) |       // New G bit
 170                        (OldG << 2));        // New L bit.
 171 }
 172
 173 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
 174 /// 'op' is a valid SetCC operation.
 175 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
 176   unsigned Operation = Op;
 177   if (isInteger)
 178     Operation ^= 7;   // Flip L, G, E bits, but not U.
 179   else
 180     Operation ^= 15;  // Flip all of the condition bits.
 181   if (Operation > ISD::SETTRUE2)
 182     Operation &= ~8;     // Don't let N and U bits get set.
 183   return ISD::CondCode(Operation);
 184 }
 185
 186
 187 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
 188 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
 189 /// if the operation does not depend on the sign of the input (setne and seteq).
 190 static int isSignedOp(ISD::CondCode Opcode) {
 191   switch (Opcode) {
 192   default: assert(0 && "Illegal integer setcc operation!");
 193   case ISD::SETEQ:
 194   case ISD::SETNE: return 0;
 195   case ISD::SETLT:
 196   case ISD::SETLE:
 197   case ISD::SETGT:
 198   case ISD::SETGE: return 1;
 199   case ISD::SETULT:
 200   case ISD::SETULE:
 201   case ISD::SETUGT:
 202   case ISD::SETUGE: return 2;
 203   }
 204 }
 205
 206 /// getSetCCOrOperation - Return the result of a logical OR between different
 207 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
 208 /// returns SETCC_INVALID if it is not possible to represent the resultant
 209 /// comparison.
 210 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 211                                        bool isInteger) {
 212   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 213     // Cannot fold a signed integer setcc with an unsigned integer setcc.
 214     return ISD::SETCC_INVALID;
 215
 216   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
 217
 218   // If the N and U bits get set then the resultant comparison DOES suddenly
 219   // care about orderedness, and is true when ordered.
 220   if (Op > ISD::SETTRUE2)
 221     Op &= ~16;     // Clear the U bit if the N bit is set.
 222
 223   // Canonicalize illegal integer setcc's.
 224   if (isInteger && Op == ISD::SETUNE)  // e.g. SETUGT | SETULT
 225     Op = ISD::SETNE;
 226
 227   return ISD::CondCode(Op);
 228 }
 229
 230 /// getSetCCAndOperation - Return the result of a logical AND between different
 231 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
 232 /// function returns zero if it is not possible to represent the resultant
 233 /// comparison.
 234 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 235                                         bool isInteger) {
 236   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 237     // Cannot fold a signed setcc with an unsigned setcc.
 238     return ISD::SETCC_INVALID;
 239
 240   // Combine all of the condition bits.
 241   ISD::CondCode Result = ISD::CondCode(Op1 & Op2);
 242
 243   // Canonicalize illegal integer setcc's.
 244   if (isInteger) {
 245     switch (Result) {
 246     default: break;
 247     case ISD::SETUO : Result = ISD::SETFALSE; break;  // SETUGT & SETULT
 248     case ISD::SETUEQ: Result = ISD::SETEQ   ; break;  // SETUGE & SETULE
 249     case ISD::SETOLT: Result = ISD::SETULT  ; break;  // SETULT & SETNE
 250     case ISD::SETOGT: Result = ISD::SETUGT  ; break;  // SETUGT & SETNE
 251     }
 252   }
 253
 254   return Result;
 255 }
 256
 257 const TargetMachine &SelectionDAG::getTarget() const {
 258   return TLI.getTargetMachine();
 259 }
 260
 261 //===----------------------------------------------------------------------===//
 262 //                              SelectionDAG Class
 263 //===----------------------------------------------------------------------===//
 264
 265 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
 266 /// SelectionDAG.
 267 void SelectionDAG::RemoveDeadNodes() {
 268   // Create a dummy node (which is not added to allnodes), that adds a reference
 269   // to the root node, preventing it from being deleted.
 270   HandleSDNode Dummy(getRoot());
 271
 272   SmallVector<SDNode*, 128> DeadNodes;
 273
 274   // Add all obviously-dead nodes to the DeadNodes worklist.
 275   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I)
 276     if (I->use_empty())
 277       DeadNodes.push_back(I);
 278
 279   // Process the worklist, deleting the nodes and adding their uses to the
 280   // worklist.
 281   while (!DeadNodes.empty()) {
 282     SDNode *N = DeadNodes.back();
 283     DeadNodes.pop_back();
 284
 285     // Take the node out of the appropriate CSE map.
 286     RemoveNodeFromCSEMaps(N);
 287
 288     // Next, brutally remove the operand list.  This is safe to do, as there are
 289     // no cycles in the graph.
 290     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
 291       SDNode *Operand = I->Val;
 292       Operand->removeUser(N);
 293
 294       // Now that we removed this operand, see if there are no uses of it left.
 295       if (Operand->use_empty())
 296         DeadNodes.push_back(Operand);
 297     }
 298     delete[] N->OperandList;
 299     N->OperandList = 0;
 300     N->NumOperands = 0;
 301
 302     // Finally, remove N itself.
 303     AllNodes.erase(N);
 304   }
 305
 306   // If the root changed (e.g. it was a dead load, update the root).
 307   setRoot(Dummy.getValue());
 308 }
 309
 310 void SelectionDAG::DeleteNode(SDNode *N) {
 311   assert(N->use_empty() && "Cannot delete a node that is not dead!");
 312
 313   // First take this out of the appropriate CSE map.
 314   RemoveNodeFromCSEMaps(N);
 315
 316   // Finally, remove uses due to operands of this node, remove from the
 317   // AllNodes list, and delete the node.
 318   DeleteNodeNotInCSEMaps(N);
 319 }
 320
 321 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
 322
 323   // Remove it from the AllNodes list.
 324   AllNodes.remove(N);
 325
 326   // Drop all of the operands and decrement used nodes use counts.
 327   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
 328     I->Val->removeUser(N);
 329   delete[] N->OperandList;
 330   N->OperandList = 0;
 331   N->NumOperands = 0;
 332
 333   delete N;
 334 }
 335
 336 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
 337 /// correspond to it.  This is useful when we're about to delete or repurpose
 338 /// the node.  We don't want future request for structurally identical nodes
 339 /// to return N anymore.
 340 void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
 341   bool Erased = false;
 342   switch (N->getOpcode()) {
 343   case ISD::HANDLENODE: return;  // noop.
 344   case ISD::Constant:
 345     Erased = Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(),
 346                                             N->getValueType(0)));
 347     break;
 348   case ISD::TargetConstant:
 349     Erased = TargetConstants.erase(std::make_pair(
 350                                     cast<ConstantSDNode>(N)->getValue(),
 351                                                   N->getValueType(0)));
 352     break;
 353   case ISD::ConstantFP: {
 354     uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue());
 355     Erased = ConstantFPs.erase(std::make_pair(V, N->getValueType(0)));
 356     break;
 357   }
 358   case ISD::TargetConstantFP: {
 359     uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue());
 360     Erased = TargetConstantFPs.erase(std::make_pair(V, N->getValueType(0)));
 361     break;
 362   }
 363   case ISD::STRING:
 364     Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue());
 365     break;
 366   case ISD::CONDCODE:
 367     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
 368            "Cond code doesn't exist!");
 369     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
 370     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
 371     break;
 372   case ISD::GlobalAddress: {
 373     GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N);
 374     Erased = GlobalValues.erase(std::make_pair(GN->getGlobal(),
 375                                                GN->getOffset()));
 376     break;
 377   }
 378   case ISD::TargetGlobalAddress: {
 379     GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N);
 380     Erased =TargetGlobalValues.erase(std::make_pair(GN->getGlobal(),
 381                                                     GN->getOffset()));
 382     break;
 383   }
 384   case ISD::FrameIndex:
 385     Erased = FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
 386     break;
 387   case ISD::TargetFrameIndex:
 388     Erased = TargetFrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
 389     break;
 390   case ISD::JumpTable:
 391     Erased = JumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex());
 392     break;
 393   case ISD::TargetJumpTable:
 394     Erased =
 395       TargetJumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex());
 396     break;
 397   case ISD::ConstantPool:
 398     Erased = ConstantPoolIndices.
 399       erase(std::make_pair(cast<ConstantPoolSDNode>(N)->get(),
 400                         std::make_pair(cast<ConstantPoolSDNode>(N)->getOffset(),
 401                                  cast<ConstantPoolSDNode>(N)->getAlignment())));
 402     break;
 403   case ISD::TargetConstantPool:
 404     Erased = TargetConstantPoolIndices.
 405       erase(std::make_pair(cast<ConstantPoolSDNode>(N)->get(),
 406                         std::make_pair(cast<ConstantPoolSDNode>(N)->getOffset(),
 407                                  cast<ConstantPoolSDNode>(N)->getAlignment())));
 408     break;
 409   case ISD::BasicBlock:
 410     Erased = BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock());
 411     break;
 412   case ISD::ExternalSymbol:
 413     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 414     break;
 415   case ISD::TargetExternalSymbol:
 416     Erased =
 417       TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 418     break;
 419   case ISD::VALUETYPE:
 420     Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0;
 421     ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0;
 422     break;
 423   case ISD::Register:
 424     Erased = RegNodes.erase(std::make_pair(cast<RegisterSDNode>(N)->getReg(),
 425                                            N->getValueType(0)));
 426     break;
 427   case ISD::SRCVALUE: {
 428     SrcValueSDNode *SVN = cast<SrcValueSDNode>(N);
 429     Erased =ValueNodes.erase(std::make_pair(SVN->getValue(), SVN->getOffset()));
 430     break;
 431   }
 432   default:
 433     // Remove it from the CSE Map.
 434     Erased = CSEMap.RemoveNode(N);
 435     break;
 436   }
 437 #ifndef NDEBUG
 438   // Verify that the node was actually in one of the CSE maps, unless it has a
 439   // flag result (which cannot be CSE'd) or is one of the special cases that are
 440   // not subject to CSE.
 441   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag &&
 442       !N->isTargetOpcode()) {
 443     N->dump();
 444     std::cerr << "\n";
 445     assert(0 && "Node is not in map!");
 446   }
 447 #endif
 448 }
 449
 450 /// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps.  It
 451 /// has been taken out and modified in some way.  If the specified node already
 452 /// exists in the CSE maps, do not modify the maps, but return the existing node
 453 /// instead.  If it doesn't exist, add it and return null.
 454 ///
 455 SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
 456   assert(N->getNumOperands() && "This is a leaf node!");
 457   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 458     return 0;    // Never add these nodes.
 459
 460   // Check that remaining values produced are not flags.
 461   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 462     if (N->getValueType(i) == MVT::Flag)
 463       return 0;   // Never CSE anything that produces a flag.
 464
 465   SDNode *New = CSEMap.GetOrInsertNode(N);
 466   if (New != N) return New;  // Node already existed.
 467   return 0;
 468 }
 469
 470 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 471 /// were replaced with those specified.  If this node is never memoized,
 472 /// return null, otherwise return a pointer to the slot it would take.  If a
 473 /// node already exists with these operands, the slot will be non-null.
 474 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op,
 475                                            void *&InsertPos) {
 476   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 477     return 0;    // Never add these nodes.
 478
 479   // Check that remaining values produced are not flags.
 480   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 481     if (N->getValueType(i) == MVT::Flag)
 482       return 0;   // Never CSE anything that produces a flag.
 483
 484   SelectionDAGCSEMap::NodeID ID;
 485   ID.SetOpcode(N->getOpcode());
 486   ID.SetValueTypes(N->value_begin());
 487   ID.SetOperands(Op);
 488   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 489 }
 490
 491 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 492 /// were replaced with those specified.  If this node is never memoized,
 493 /// return null, otherwise return a pointer to the slot it would take.  If a
 494 /// node already exists with these operands, the slot will be non-null.
 495 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
 496                                            SDOperand Op1, SDOperand Op2,
 497                                            void *&InsertPos) {
 498   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 499     return 0;    // Never add these nodes.
 500
 501   // Check that remaining values produced are not flags.
 502   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 503     if (N->getValueType(i) == MVT::Flag)
 504       return 0;   // Never CSE anything that produces a flag.
 505
 506   SelectionDAGCSEMap::NodeID ID;
 507   ID.SetOpcode(N->getOpcode());
 508   ID.SetValueTypes(N->value_begin());
 509   ID.SetOperands(Op1, Op2);
 510   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 511 }
 512
 513
 514 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands
 515 /// were replaced with those specified.  If this node is never memoized,
 516 /// return null, otherwise return a pointer to the slot it would take.  If a
 517 /// node already exists with these operands, the slot will be non-null.
 518 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N,
 519                                            const SDOperand *Ops,unsigned NumOps,
 520                                            void *&InsertPos) {
 521   if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag)
 522     return 0;    // Never add these nodes.
 523
 524   // Check that remaining values produced are not flags.
 525   for (unsigned i = 1, e = N->getNumValues(); i != e; ++i)
 526     if (N->getValueType(i) == MVT::Flag)
 527       return 0;   // Never CSE anything that produces a flag.
 528
 529   SelectionDAGCSEMap::NodeID ID;
 530   ID.SetOpcode(N->getOpcode());
 531   ID.SetValueTypes(N->value_begin());
 532   ID.SetOperands(Ops, NumOps);
 533   return CSEMap.FindNodeOrInsertPos(ID, InsertPos);
 534 }
 535
 536
 537 SelectionDAG::~SelectionDAG() {
 538   while (!AllNodes.empty()) {
 539     SDNode *N = AllNodes.begin();
 540     delete [] N->OperandList;
 541     N->OperandList = 0;
 542     N->NumOperands = 0;
 543     AllNodes.pop_front();
 544   }
 545 }
 546
 547 SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) {
 548   if (Op.getValueType() == VT) return Op;
 549   int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT));
 550   return getNode(ISD::AND, Op.getValueType(), Op,
 551                  getConstant(Imm, Op.getValueType()));
 552 }
 553
 554 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) {
 555   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 556   assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!");
 557
 558   // Mask out any bits that are not valid for this constant.
 559   if (VT != MVT::i64)
 560     Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
 561
 562   SDNode *&N = Constants[std::make_pair(Val, VT)];
 563   if (N) return SDOperand(N, 0);
 564   N = new ConstantSDNode(false, Val, VT);
 565   AllNodes.push_back(N);
 566   return SDOperand(N, 0);
 567 }
 568
 569 SDOperand SelectionDAG::getString(const std::string &Val) {
 570   StringSDNode *&N = StringNodes[Val];
 571   if (!N) {
 572     N = new StringSDNode(Val);
 573     AllNodes.push_back(N);
 574   }
 575   return SDOperand(N, 0);
 576 }
 577
 578 SDOperand SelectionDAG::getTargetConstant(uint64_t Val, MVT::ValueType VT) {
 579   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 580   // Mask out any bits that are not valid for this constant.
 581   if (VT != MVT::i64)
 582     Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
 583
 584   SDNode *&N = TargetConstants[std::make_pair(Val, VT)];
 585   if (N) return SDOperand(N, 0);
 586   N = new ConstantSDNode(true, Val, VT);
 587   AllNodes.push_back(N);
 588   return SDOperand(N, 0);
 589 }
 590
 591 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
 592   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
 593   if (VT == MVT::f32)
 594     Val = (float)Val;  // Mask out extra precision.
 595
 596   // Do the map lookup using the actual bit pattern for the floating point
 597   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
 598   // we don't have issues with SNANs.
 599   SDNode *&N = ConstantFPs[std::make_pair(DoubleToBits(Val), VT)];
 600   if (N) return SDOperand(N, 0);
 601   N = new ConstantFPSDNode(false, Val, VT);
 602   AllNodes.push_back(N);
 603   return SDOperand(N, 0);
 604 }
 605
 606 SDOperand SelectionDAG::getTargetConstantFP(double Val, MVT::ValueType VT) {
 607   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
 608   if (VT == MVT::f32)
 609     Val = (float)Val;  // Mask out extra precision.
 610
 611   // Do the map lookup using the actual bit pattern for the floating point
 612   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
 613   // we don't have issues with SNANs.
 614   SDNode *&N = TargetConstantFPs[std::make_pair(DoubleToBits(Val), VT)];
 615   if (N) return SDOperand(N, 0);
 616   N = new ConstantFPSDNode(true, Val, VT);
 617   AllNodes.push_back(N);
 618   return SDOperand(N, 0);
 619 }
 620
 621 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 622                                          MVT::ValueType VT, int offset) {
 623   SDNode *&N = GlobalValues[std::make_pair(GV, offset)];
 624   if (N) return SDOperand(N, 0);
 625   N = new GlobalAddressSDNode(false, GV, VT, offset);
 626   AllNodes.push_back(N);
 627   return SDOperand(N, 0);
 628 }
 629
 630 SDOperand SelectionDAG::getTargetGlobalAddress(const GlobalValue *GV,
 631                                                MVT::ValueType VT, int offset) {
 632   SDNode *&N = TargetGlobalValues[std::make_pair(GV, offset)];
 633   if (N) return SDOperand(N, 0);
 634   N = new GlobalAddressSDNode(true, GV, VT, offset);
 635   AllNodes.push_back(N);
 636   return SDOperand(N, 0);
 637 }
 638
 639 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) {
 640   SDNode *&N = FrameIndices[FI];
 641   if (N) return SDOperand(N, 0);
 642   N = new FrameIndexSDNode(FI, VT, false);
 643   AllNodes.push_back(N);
 644   return SDOperand(N, 0);
 645 }
 646
 647 SDOperand SelectionDAG::getTargetFrameIndex(int FI, MVT::ValueType VT) {
 648   SDNode *&N = TargetFrameIndices[FI];
 649   if (N) return SDOperand(N, 0);
 650   N = new FrameIndexSDNode(FI, VT, true);
 651   AllNodes.push_back(N);
 652   return SDOperand(N, 0);
 653 }
 654
 655 SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT) {
 656   SDNode *&N = JumpTableIndices[JTI];
 657   if (N) return SDOperand(N, 0);
 658   N = new JumpTableSDNode(JTI, VT, false);
 659   AllNodes.push_back(N);
 660   return SDOperand(N, 0);
 661 }
 662
 663 SDOperand SelectionDAG::getTargetJumpTable(int JTI, MVT::ValueType VT) {
 664   SDNode *&N = TargetJumpTableIndices[JTI];
 665   if (N) return SDOperand(N, 0);
 666   N = new JumpTableSDNode(JTI, VT, true);
 667   AllNodes.push_back(N);
 668   return SDOperand(N, 0);
 669 }
 670
 671 SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT,
 672                                         unsigned Alignment,  int Offset) {
 673   SDNode *&N = ConstantPoolIndices[std::make_pair(C,
 674                                             std::make_pair(Offset, Alignment))];
 675   if (N) return SDOperand(N, 0);
 676   N = new ConstantPoolSDNode(false, C, VT, Offset, Alignment);
 677   AllNodes.push_back(N);
 678   return SDOperand(N, 0);
 679 }
 680
 681 SDOperand SelectionDAG::getTargetConstantPool(Constant *C, MVT::ValueType VT,
 682                                              unsigned Alignment,  int Offset) {
 683   SDNode *&N = TargetConstantPoolIndices[std::make_pair(C,
 684                                             std::make_pair(Offset, Alignment))];
 685   if (N) return SDOperand(N, 0);
 686   N = new ConstantPoolSDNode(true, C, VT, Offset, Alignment);
 687   AllNodes.push_back(N);
 688   return SDOperand(N, 0);
 689 }
 690
 691 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
 692   SDNode *&N = BBNodes[MBB];
 693   if (N) return SDOperand(N, 0);
 694   N = new BasicBlockSDNode(MBB);
 695   AllNodes.push_back(N);
 696   return SDOperand(N, 0);
 697 }
 698
 699 SDOperand SelectionDAG::getValueType(MVT::ValueType VT) {
 700   if ((unsigned)VT >= ValueTypeNodes.size())
 701     ValueTypeNodes.resize(VT+1);
 702   if (ValueTypeNodes[VT] == 0) {
 703     ValueTypeNodes[VT] = new VTSDNode(VT);
 704     AllNodes.push_back(ValueTypeNodes[VT]);
 705   }
 706
 707   return SDOperand(ValueTypeNodes[VT], 0);
 708 }
 709
 710 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
 711   SDNode *&N = ExternalSymbols[Sym];
 712   if (N) return SDOperand(N, 0);
 713   N = new ExternalSymbolSDNode(false, Sym, VT);
 714   AllNodes.push_back(N);
 715   return SDOperand(N, 0);
 716 }
 717
 718 SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym,
 719                                                 MVT::ValueType VT) {
 720   SDNode *&N = TargetExternalSymbols[Sym];
 721   if (N) return SDOperand(N, 0);
 722   N = new ExternalSymbolSDNode(true, Sym, VT);
 723   AllNodes.push_back(N);
 724   return SDOperand(N, 0);
 725 }
 726
 727 SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
 728   if ((unsigned)Cond >= CondCodeNodes.size())
 729     CondCodeNodes.resize(Cond+1);
 730
 731   if (CondCodeNodes[Cond] == 0) {
 732     CondCodeNodes[Cond] = new CondCodeSDNode(Cond);
 733     AllNodes.push_back(CondCodeNodes[Cond]);
 734   }
 735   return SDOperand(CondCodeNodes[Cond], 0);
 736 }
 737
 738 SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) {
 739   RegisterSDNode *&Reg = RegNodes[std::make_pair(RegNo, VT)];
 740   if (!Reg) {
 741     Reg = new RegisterSDNode(RegNo, VT);
 742     AllNodes.push_back(Reg);
 743   }
 744   return SDOperand(Reg, 0);
 745 }
 746
 747 SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1,
 748                                       SDOperand N2, ISD::CondCode Cond) {
 749   // These setcc operations always fold.
 750   switch (Cond) {
 751   default: break;
 752   case ISD::SETFALSE:
 753   case ISD::SETFALSE2: return getConstant(0, VT);
 754   case ISD::SETTRUE:
 755   case ISD::SETTRUE2:  return getConstant(1, VT);
 756
 757   case ISD::SETOEQ:
 758   case ISD::SETOGT:
 759   case ISD::SETOGE:
 760   case ISD::SETOLT:
 761   case ISD::SETOLE:
 762   case ISD::SETONE:
 763   case ISD::SETO:
 764   case ISD::SETUO:
 765   case ISD::SETUEQ:
 766   case ISD::SETUNE:
 767     assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!");
 768     break;
 769   }
 770
 771   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
 772     uint64_t C2 = N2C->getValue();
 773     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
 774       uint64_t C1 = N1C->getValue();
 775
 776       // Sign extend the operands if required
 777       if (ISD::isSignedIntSetCC(Cond)) {
 778         C1 = N1C->getSignExtended();
 779         C2 = N2C->getSignExtended();
 780       }
 781
 782       switch (Cond) {
 783       default: assert(0 && "Unknown integer setcc!");
 784       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
 785       case ISD::SETNE:  return getConstant(C1 != C2, VT);
 786       case ISD::SETULT: return getConstant(C1 <  C2, VT);
 787       case ISD::SETUGT: return getConstant(C1 >  C2, VT);
 788       case ISD::SETULE: return getConstant(C1 <= C2, VT);
 789       case ISD::SETUGE: return getConstant(C1 >= C2, VT);
 790       case ISD::SETLT:  return getConstant((int64_t)C1 <  (int64_t)C2, VT);
 791       case ISD::SETGT:  return getConstant((int64_t)C1 >  (int64_t)C2, VT);
 792       case ISD::SETLE:  return getConstant((int64_t)C1 <= (int64_t)C2, VT);
 793       case ISD::SETGE:  return getConstant((int64_t)C1 >= (int64_t)C2, VT);
 794       }
 795     } else {
 796       // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
 797       if (N1.getOpcode() == ISD::ZERO_EXTEND) {
 798         unsigned InSize = MVT::getSizeInBits(N1.getOperand(0).getValueType());
 799
 800         // If the comparison constant has bits in the upper part, the
 801         // zero-extended value could never match.
 802         if (C2 & (~0ULL << InSize)) {
 803           unsigned VSize = MVT::getSizeInBits(N1.getValueType());
 804           switch (Cond) {
 805           case ISD::SETUGT:
 806           case ISD::SETUGE:
 807           case ISD::SETEQ: return getConstant(0, VT);
 808           case ISD::SETULT:
 809           case ISD::SETULE:
 810           case ISD::SETNE: return getConstant(1, VT);
 811           case ISD::SETGT:
 812           case ISD::SETGE:
 813             // True if the sign bit of C2 is set.
 814             return getConstant((C2 & (1ULL << VSize)) != 0, VT);
 815           case ISD::SETLT:
 816           case ISD::SETLE:
 817             // True if the sign bit of C2 isn't set.
 818             return getConstant((C2 & (1ULL << VSize)) == 0, VT);
 819           default:
 820             break;
 821           }
 822         }
 823
 824         // Otherwise, we can perform the comparison with the low bits.
 825         switch (Cond) {
 826         case ISD::SETEQ:
 827         case ISD::SETNE:
 828         case ISD::SETUGT:
 829         case ISD::SETUGE:
 830         case ISD::SETULT:
 831         case ISD::SETULE:
 832           return getSetCC(VT, N1.getOperand(0),
 833                           getConstant(C2, N1.getOperand(0).getValueType()),
 834                           Cond);
 835         default:
 836           break;   // todo, be more careful with signed comparisons
 837         }
 838       } else if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG &&
 839                  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
 840         MVT::ValueType ExtSrcTy = cast<VTSDNode>(N1.getOperand(1))->getVT();
 841         unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
 842         MVT::ValueType ExtDstTy = N1.getValueType();
 843         unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
 844
 845         // If the extended part has any inconsistent bits, it cannot ever
 846         // compare equal.  In other words, they have to be all ones or all
 847         // zeros.
 848         uint64_t ExtBits =
 849           (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
 850         if ((C2 & ExtBits) != 0 && (C2 & ExtBits) != ExtBits)
 851           return getConstant(Cond == ISD::SETNE, VT);
 852
 853         // Otherwise, make this a use of a zext.
 854         return getSetCC(VT, getZeroExtendInReg(N1.getOperand(0), ExtSrcTy),
 855                         getConstant(C2 & (~0ULL>>(64-ExtSrcTyBits)), ExtDstTy),
 856                         Cond);
 857       }
 858
 859       uint64_t MinVal, MaxVal;
 860       unsigned OperandBitSize = MVT::getSizeInBits(N2C->getValueType(0));
 861       if (ISD::isSignedIntSetCC(Cond)) {
 862         MinVal = 1ULL << (OperandBitSize-1);
 863         if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
 864           MaxVal = ~0ULL >> (65-OperandBitSize);
 865         else
 866           MaxVal = 0;
 867       } else {
 868         MinVal = 0;
 869         MaxVal = ~0ULL >> (64-OperandBitSize);
 870       }
 871
 872       // Canonicalize GE/LE comparisons to use GT/LT comparisons.
 873       if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
 874         if (C2 == MinVal) return getConstant(1, VT);   // X >= MIN --> true
 875         --C2;                                          // X >= C1 --> X > (C1-1)
 876         return getSetCC(VT, N1, getConstant(C2, N2.getValueType()),
 877                         (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
 878       }
 879
 880       if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
 881         if (C2 == MaxVal) return getConstant(1, VT);   // X <= MAX --> true
 882         ++C2;                                          // X <= C1 --> X < (C1+1)
 883         return getSetCC(VT, N1, getConstant(C2, N2.getValueType()),
 884                         (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
 885       }
 886
 887       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal)
 888         return getConstant(0, VT);      // X < MIN --> false
 889
 890       // Canonicalize setgt X, Min --> setne X, Min
 891       if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MinVal)
 892         return getSetCC(VT, N1, N2, ISD::SETNE);
 893
 894       // If we have setult X, 1, turn it into seteq X, 0
 895       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal+1)
 896         return getSetCC(VT, N1, getConstant(MinVal, N1.getValueType()),
 897                         ISD::SETEQ);
 898       // If we have setugt X, Max-1, turn it into seteq X, Max
 899       else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MaxVal-1)
 900         return getSetCC(VT, N1, getConstant(MaxVal, N1.getValueType()),
 901                         ISD::SETEQ);
 902
 903       // If we have "setcc X, C1", check to see if we can shrink the immediate
 904       // by changing cc.
 905
 906       // SETUGT X, SINTMAX  -> SETLT X, 0
 907       if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
 908           C2 == (~0ULL >> (65-OperandBitSize)))
 909         return getSetCC(VT, N1, getConstant(0, N2.getValueType()), ISD::SETLT);
 910
 911       // FIXME: Implement the rest of these.
 912
 913
 914       // Fold bit comparisons when we can.
 915       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
 916           VT == N1.getValueType() && N1.getOpcode() == ISD::AND)
 917         if (ConstantSDNode *AndRHS =
 918                     dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
 919           if (Cond == ISD::SETNE && C2 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
 920             // Perform the xform if the AND RHS is a single bit.
 921             if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
 922               return getNode(ISD::SRL, VT, N1,
 923                              getConstant(Log2_64(AndRHS->getValue()),
 924                                                    TLI.getShiftAmountTy()));
 925             }
 926           } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) {
 927             // (X & 8) == 8  -->  (X & 8) >> 3
 928             // Perform the xform if C2 is a single bit.
 929             if ((C2 & (C2-1)) == 0) {
 930               return getNode(ISD::SRL, VT, N1,
 931                              getConstant(Log2_64(C2),TLI.getShiftAmountTy()));
 932             }
 933           }
 934         }
 935     }
 936   } else if (isa<ConstantSDNode>(N1.Val)) {
 937       // Ensure that the constant occurs on the RHS.
 938     return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
 939   }
 940
 941   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
 942     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
 943       double C1 = N1C->getValue(), C2 = N2C->getValue();
 944
 945       switch (Cond) {
 946       default: break; // FIXME: Implement the rest of these!
 947       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
 948       case ISD::SETNE:  return getConstant(C1 != C2, VT);
 949       case ISD::SETLT:  return getConstant(C1 < C2, VT);
 950       case ISD::SETGT:  return getConstant(C1 > C2, VT);
 951       case ISD::SETLE:  return getConstant(C1 <= C2, VT);
 952       case ISD::SETGE:  return getConstant(C1 >= C2, VT);
 953       }
 954     } else {
 955       // Ensure that the constant occurs on the RHS.
 956       return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
 957     }
 958
 959   // Could not fold it.
 960   return SDOperand();
 961 }
 962
 963 /// getNode - Gets or creates the specified node.
 964 ///
 965 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
 966   MVT::ValueType *VTs = getNodeValueTypes(VT);
 967   SelectionDAGCSEMap::NodeID ID(Opcode, VTs);
 968   void *IP = 0;
 969   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
 970     return SDOperand(E, 0);
 971   SDNode *N = new SDNode(Opcode, VT);
 972   CSEMap.InsertNode(N, IP);
 973
 974   AllNodes.push_back(N);
 975   return SDOperand(N, 0);
 976 }
 977
 978 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 979                                 SDOperand Operand) {
 980   unsigned Tmp1;
 981   // Constant fold unary operations with an integer constant operand.
 982   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
 983     uint64_t Val = C->getValue();
 984     switch (Opcode) {
 985     default: break;
 986     case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
 987     case ISD::ANY_EXTEND:
 988     case ISD::ZERO_EXTEND: return getConstant(Val, VT);
 989     case ISD::TRUNCATE:    return getConstant(Val, VT);
 990     case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
 991     case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
 992     case ISD::BIT_CONVERT:
 993       if (VT == MVT::f32 && C->getValueType(0) == MVT::i32)
 994         return getConstantFP(BitsToFloat(Val), VT);
 995       else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64)
 996         return getConstantFP(BitsToDouble(Val), VT);
 997       break;
 998     case ISD::BSWAP:
 999       switch(VT) {
1000       default: assert(0 && "Invalid bswap!"); break;
1001       case MVT::i16: return getConstant(ByteSwap_16((unsigned short)Val), VT);
1002       case MVT::i32: return getConstant(ByteSwap_32((unsigned)Val), VT);
1003       case MVT::i64: return getConstant(ByteSwap_64(Val), VT);
1004       }
1005       break;
1006     case ISD::CTPOP:
1007       switch(VT) {
1008       default: assert(0 && "Invalid ctpop!"); break;
1009       case MVT::i1: return getConstant(Val != 0, VT);
1010       case MVT::i8:
1011         Tmp1 = (unsigned)Val & 0xFF;
1012         return getConstant(CountPopulation_32(Tmp1), VT);
1013       case MVT::i16:
1014         Tmp1 = (unsigned)Val & 0xFFFF;
1015         return getConstant(CountPopulation_32(Tmp1), VT);
1016       case MVT::i32:
1017         return getConstant(CountPopulation_32((unsigned)Val), VT);
1018       case MVT::i64:
1019         return getConstant(CountPopulation_64(Val), VT);
1020       }
1021     case ISD::CTLZ:
1022       switch(VT) {
1023       default: assert(0 && "Invalid ctlz!"); break;
1024       case MVT::i1: return getConstant(Val == 0, VT);
1025       case MVT::i8:
1026         Tmp1 = (unsigned)Val & 0xFF;
1027         return getConstant(CountLeadingZeros_32(Tmp1)-24, VT);
1028       case MVT::i16:
1029         Tmp1 = (unsigned)Val & 0xFFFF;
1030         return getConstant(CountLeadingZeros_32(Tmp1)-16, VT);
1031       case MVT::i32:
1032         return getConstant(CountLeadingZeros_32((unsigned)Val), VT);
1033       case MVT::i64:
1034         return getConstant(CountLeadingZeros_64(Val), VT);
1035       }
1036     case ISD::CTTZ:
1037       switch(VT) {
1038       default: assert(0 && "Invalid cttz!"); break;
1039       case MVT::i1: return getConstant(Val == 0, VT);
1040       case MVT::i8:
1041         Tmp1 = (unsigned)Val | 0x100;
1042         return getConstant(CountTrailingZeros_32(Tmp1), VT);
1043       case MVT::i16:
1044         Tmp1 = (unsigned)Val | 0x10000;
1045         return getConstant(CountTrailingZeros_32(Tmp1), VT);
1046       case MVT::i32:
1047         return getConstant(CountTrailingZeros_32((unsigned)Val), VT);
1048       case MVT::i64:
1049         return getConstant(CountTrailingZeros_64(Val), VT);
1050       }
1051     }
1052   }
1053
1054   // Constant fold unary operations with an floating point constant operand.
1055   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
1056     switch (Opcode) {
1057     case ISD::FNEG:
1058       return getConstantFP(-C->getValue(), VT);
1059     case ISD::FABS:
1060       return getConstantFP(fabs(C->getValue()), VT);
1061     case ISD::FP_ROUND:
1062     case ISD::FP_EXTEND:
1063       return getConstantFP(C->getValue(), VT);
1064     case ISD::FP_TO_SINT:
1065       return getConstant((int64_t)C->getValue(), VT);
1066     case ISD::FP_TO_UINT:
1067       return getConstant((uint64_t)C->getValue(), VT);
1068     case ISD::BIT_CONVERT:
1069       if (VT == MVT::i32 && C->getValueType(0) == MVT::f32)
1070         return getConstant(FloatToBits(C->getValue()), VT);
1071       else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64)
1072         return getConstant(DoubleToBits(C->getValue()), VT);
1073       break;
1074     }
1075
1076   unsigned OpOpcode = Operand.Val->getOpcode();
1077   switch (Opcode) {
1078   case ISD::TokenFactor:
1079     return Operand;         // Factor of one node?  No factor.
1080   case ISD::SIGN_EXTEND:
1081     if (Operand.getValueType() == VT) return Operand;   // noop extension
1082     assert(Operand.getValueType() < VT && "Invalid sext node, dst < src!");
1083     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
1084       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1085     break;
1086   case ISD::ZERO_EXTEND:
1087     if (Operand.getValueType() == VT) return Operand;   // noop extension
1088     assert(Operand.getValueType() < VT && "Invalid zext node, dst < src!");
1089     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
1090       return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
1091     break;
1092   case ISD::ANY_EXTEND:
1093     if (Operand.getValueType() == VT) return Operand;   // noop extension
1094     assert(Operand.getValueType() < VT && "Invalid anyext node, dst < src!");
1095     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND)
1096       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
1097       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1098     break;
1099   case ISD::TRUNCATE:
1100     if (Operand.getValueType() == VT) return Operand;   // noop truncate
1101     assert(Operand.getValueType() > VT && "Invalid truncate node, src < dst!");
1102     if (OpOpcode == ISD::TRUNCATE)
1103       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1104     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
1105              OpOpcode == ISD::ANY_EXTEND) {
1106       // If the source is smaller than the dest, we still need an extend.
1107       if (Operand.Val->getOperand(0).getValueType() < VT)
1108         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
1109       else if (Operand.Val->getOperand(0).getValueType() > VT)
1110         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
1111       else
1112         return Operand.Val->getOperand(0);
1113     }
1114     break;
1115   case ISD::BIT_CONVERT:
1116     // Basic sanity checking.
1117     assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType())
1118            && "Cannot BIT_CONVERT between two different types!");
1119     if (VT == Operand.getValueType()) return Operand;  // noop conversion.
1120     if (OpOpcode == ISD::BIT_CONVERT)  // bitconv(bitconv(x)) -> bitconv(x)
1121       return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0));
1122     if (OpOpcode == ISD::UNDEF)
1123       return getNode(ISD::UNDEF, VT);
1124     break;
1125   case ISD::SCALAR_TO_VECTOR:
1126     assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) &&
1127            MVT::getVectorBaseType(VT) == Operand.getValueType() &&
1128            "Illegal SCALAR_TO_VECTOR node!");
1129     break;
1130   case ISD::FNEG:
1131     if (OpOpcode == ISD::FSUB)   // -(X-Y) -> (Y-X)
1132       return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1),
1133                      Operand.Val->getOperand(0));
1134     if (OpOpcode == ISD::FNEG)  // --X -> X
1135       return Operand.Val->getOperand(0);
1136     break;
1137   case ISD::FABS:
1138     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
1139       return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
1140     break;
1141   }
1142
1143   SDNode *N;
1144   MVT::ValueType *VTs = getNodeValueTypes(VT);
1145   if (VT != MVT::Flag) { // Don't CSE flag producing nodes
1146     SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Operand);
1147     void *IP = 0;
1148     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1149       return SDOperand(E, 0);
1150     N = new SDNode(Opcode, Operand);
1151     N->setValueTypes(VTs, 1);
1152     CSEMap.InsertNode(N, IP);
1153   } else {
1154     N = new SDNode(Opcode, Operand);
1155     N->setValueTypes(VTs, 1);
1156   }
1157   AllNodes.push_back(N);
1158   return SDOperand(N, 0);
1159 }
1160
1161
1162
1163 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1164                                 SDOperand N1, SDOperand N2) {
1165 #ifndef NDEBUG
1166   switch (Opcode) {
1167   case ISD::TokenFactor:
1168     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
1169            N2.getValueType() == MVT::Other && "Invalid token factor!");
1170     break;
1171   case ISD::AND:
1172   case ISD::OR:
1173   case ISD::XOR:
1174   case ISD::UDIV:
1175   case ISD::UREM:
1176   case ISD::MULHU:
1177   case ISD::MULHS:
1178     assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
1179     // fall through
1180   case ISD::ADD:
1181   case ISD::SUB:
1182   case ISD::MUL:
1183   case ISD::SDIV:
1184   case ISD::SREM:
1185     assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops");
1186     // fall through.
1187   case ISD::FADD:
1188   case ISD::FSUB:
1189   case ISD::FMUL:
1190   case ISD::FDIV:
1191   case ISD::FREM:
1192     assert(N1.getValueType() == N2.getValueType() &&
1193            N1.getValueType() == VT && "Binary operator types must match!");
1194     break;
1195   case ISD::FCOPYSIGN:   // N1 and result must match.  N1/N2 need not match.
1196     assert(N1.getValueType() == VT &&
1197            MVT::isFloatingPoint(N1.getValueType()) &&
1198            MVT::isFloatingPoint(N2.getValueType()) &&
1199            "Invalid FCOPYSIGN!");
1200     break;
1201   case ISD::SHL:
1202   case ISD::SRA:
1203   case ISD::SRL:
1204   case ISD::ROTL:
1205   case ISD::ROTR:
1206     assert(VT == N1.getValueType() &&
1207            "Shift operators return type must be the same as their first arg");
1208     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
1209            VT != MVT::i1 && "Shifts only work on integers");
1210     break;
1211   case ISD::FP_ROUND_INREG: {
1212     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1213     assert(VT == N1.getValueType() && "Not an inreg round!");
1214     assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
1215            "Cannot FP_ROUND_INREG integer types");
1216     assert(EVT <= VT && "Not rounding down!");
1217     break;
1218   }
1219   case ISD::AssertSext:
1220   case ISD::AssertZext:
1221   case ISD::SIGN_EXTEND_INREG: {
1222     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1223     assert(VT == N1.getValueType() && "Not an inreg extend!");
1224     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
1225            "Cannot *_EXTEND_INREG FP types");
1226     assert(EVT <= VT && "Not extending!");
1227   }
1228
1229   default: break;
1230   }
1231 #endif
1232
1233   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1234   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1235   if (N1C) {
1236     if (Opcode == ISD::SIGN_EXTEND_INREG) {
1237       int64_t Val = N1C->getValue();
1238       unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT());
1239       Val <<= 64-FromBits;
1240       Val >>= 64-FromBits;
1241       return getConstant(Val, VT);
1242     }
1243
1244     if (N2C) {
1245       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
1246       switch (Opcode) {
1247       case ISD::ADD: return getConstant(C1 + C2, VT);
1248       case ISD::SUB: return getConstant(C1 - C2, VT);
1249       case ISD::MUL: return getConstant(C1 * C2, VT);
1250       case ISD::UDIV:
1251         if (C2) return getConstant(C1 / C2, VT);
1252         break;
1253       case ISD::UREM :
1254         if (C2) return getConstant(C1 % C2, VT);
1255         break;
1256       case ISD::SDIV :
1257         if (C2) return getConstant(N1C->getSignExtended() /
1258                                    N2C->getSignExtended(), VT);
1259         break;
1260       case ISD::SREM :
1261         if (C2) return getConstant(N1C->getSignExtended() %
1262                                    N2C->getSignExtended(), VT);
1263         break;
1264       case ISD::AND  : return getConstant(C1 & C2, VT);
1265       case ISD::OR   : return getConstant(C1 | C2, VT);
1266       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
1267       case ISD::SHL  : return getConstant(C1 << C2, VT);
1268       case ISD::SRL  : return getConstant(C1 >> C2, VT);
1269       case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
1270       case ISD::ROTL :
1271         return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)),
1272                            VT);
1273       case ISD::ROTR :
1274         return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)),
1275                            VT);
1276       default: break;
1277       }
1278     } else {      // Cannonicalize constant to RHS if commutative
1279       if (isCommutativeBinOp(Opcode)) {
1280         std::swap(N1C, N2C);
1281         std::swap(N1, N2);
1282       }
1283     }
1284   }
1285
1286   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
1287   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
1288   if (N1CFP) {
1289     if (N2CFP) {
1290       double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
1291       switch (Opcode) {
1292       case ISD::FADD: return getConstantFP(C1 + C2, VT);
1293       case ISD::FSUB: return getConstantFP(C1 - C2, VT);
1294       case ISD::FMUL: return getConstantFP(C1 * C2, VT);
1295       case ISD::FDIV:
1296         if (C2) return getConstantFP(C1 / C2, VT);
1297         break;
1298       case ISD::FREM :
1299         if (C2) return getConstantFP(fmod(C1, C2), VT);
1300         break;
1301       case ISD::FCOPYSIGN: {
1302         union {
1303           double   F;
1304           uint64_t I;
1305         } u1;
1306         union {
1307           double  F;
1308           int64_t I;
1309         } u2;
1310         u1.F = C1;
1311         u2.F = C2;
1312         if (u2.I < 0)  // Sign bit of RHS set?
1313           u1.I |= 1ULL << 63;      // Set the sign bit of the LHS.
1314         else
1315           u1.I &= (1ULL << 63)-1;  // Clear the sign bit of the LHS.
1316         return getConstantFP(u1.F, VT);
1317       }
1318       default: break;
1319       }
1320     } else {      // Cannonicalize constant to RHS if commutative
1321       if (isCommutativeBinOp(Opcode)) {
1322         std::swap(N1CFP, N2CFP);
1323         std::swap(N1, N2);
1324       }
1325     }
1326   }
1327
1328   // Canonicalize an UNDEF to the RHS, even over a constant.
1329   if (N1.getOpcode() == ISD::UNDEF) {
1330     if (isCommutativeBinOp(Opcode)) {
1331       std::swap(N1, N2);
1332     } else {
1333       switch (Opcode) {
1334       case ISD::FP_ROUND_INREG:
1335       case ISD::SIGN_EXTEND_INREG:
1336       case ISD::SUB:
1337       case ISD::FSUB:
1338       case ISD::FDIV:
1339       case ISD::FREM:
1340       case ISD::SRA:
1341         return N1;     // fold op(undef, arg2) -> undef
1342       case ISD::UDIV:
1343       case ISD::SDIV:
1344       case ISD::UREM:
1345       case ISD::SREM:
1346       case ISD::SRL:
1347       case ISD::SHL:
1348         return getConstant(0, VT);    // fold op(undef, arg2) -> 0
1349       }
1350     }
1351   }
1352
1353   // Fold a bunch of operators when the RHS is undef.
1354   if (N2.getOpcode() == ISD::UNDEF) {
1355     switch (Opcode) {
1356     case ISD::ADD:
1357     case ISD::SUB:
1358     case ISD::FADD:
1359     case ISD::FSUB:
1360     case ISD::FMUL:
1361     case ISD::FDIV:
1362     case ISD::FREM:
1363     case ISD::UDIV:
1364     case ISD::SDIV:
1365     case ISD::UREM:
1366     case ISD::SREM:
1367     case ISD::XOR:
1368       return N2;       // fold op(arg1, undef) -> undef
1369     case ISD::MUL:
1370     case ISD::AND:
1371     case ISD::SRL:
1372     case ISD::SHL:
1373       return getConstant(0, VT);  // fold op(arg1, undef) -> 0
1374     case ISD::OR:
1375       return getConstant(MVT::getIntVTBitMask(VT), VT);
1376     case ISD::SRA:
1377       return N1;
1378     }
1379   }
1380
1381   // Finally, fold operations that do not require constants.
1382   switch (Opcode) {
1383   case ISD::FP_ROUND_INREG:
1384     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
1385     break;
1386   case ISD::SIGN_EXTEND_INREG: {
1387     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1388     if (EVT == VT) return N1;  // Not actually extending
1389     break;
1390   }
1391
1392   // FIXME: figure out how to safely handle things like
1393   // int foo(int x) { return 1 << (x & 255); }
1394   // int bar() { return foo(256); }
1395 #if 0
1396   case ISD::SHL:
1397   case ISD::SRL:
1398   case ISD::SRA:
1399     if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1400         cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1)
1401       return getNode(Opcode, VT, N1, N2.getOperand(0));
1402     else if (N2.getOpcode() == ISD::AND)
1403       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) {
1404         // If the and is only masking out bits that cannot effect the shift,
1405         // eliminate the and.
1406         unsigned NumBits = MVT::getSizeInBits(VT);
1407         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1408           return getNode(Opcode, VT, N1, N2.getOperand(0));
1409       }
1410     break;
1411 #endif
1412   }
1413
1414   // Memoize this node if possible.
1415   SDNode *N;
1416   MVT::ValueType *VTs = getNodeValueTypes(VT);
1417   if (VT != MVT::Flag) {
1418     SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2);
1419     void *IP = 0;
1420     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1421       return SDOperand(E, 0);
1422     N = new SDNode(Opcode, N1, N2);
1423     N->setValueTypes(VTs, 1);
1424     CSEMap.InsertNode(N, IP);
1425   } else {
1426     N = new SDNode(Opcode, N1, N2);
1427     N->setValueTypes(VTs, 1);
1428   }
1429
1430   AllNodes.push_back(N);
1431   return SDOperand(N, 0);
1432 }
1433
1434 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1435                                 SDOperand N1, SDOperand N2, SDOperand N3) {
1436   // Perform various simplifications.
1437   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1438   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1439   //ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
1440   switch (Opcode) {
1441   case ISD::SETCC: {
1442     // Use SimplifySetCC  to simplify SETCC's.
1443     SDOperand Simp = SimplifySetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
1444     if (Simp.Val) return Simp;
1445     break;
1446   }
1447   case ISD::SELECT:
1448     if (N1C)
1449       if (N1C->getValue())
1450         return N2;             // select true, X, Y -> X
1451       else
1452         return N3;             // select false, X, Y -> Y
1453
1454     if (N2 == N3) return N2;   // select C, X, X -> X
1455     break;
1456   case ISD::BRCOND:
1457     if (N2C)
1458       if (N2C->getValue()) // Unconditional branch
1459         return getNode(ISD::BR, MVT::Other, N1, N3);
1460       else
1461         return N1;         // Never-taken branch
1462     break;
1463   case ISD::VECTOR_SHUFFLE:
1464     assert(VT == N1.getValueType() && VT == N2.getValueType() &&
1465            MVT::isVector(VT) && MVT::isVector(N3.getValueType()) &&
1466            N3.getOpcode() == ISD::BUILD_VECTOR &&
1467            MVT::getVectorNumElements(VT) == N3.getNumOperands() &&
1468            "Illegal VECTOR_SHUFFLE node!");
1469     break;
1470   }
1471
1472   // Memoize node if it doesn't produce a flag.
1473   SDNode *N;
1474   MVT::ValueType *VTs = getNodeValueTypes(VT);
1475
1476   if (VT != MVT::Flag) {
1477     SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2, N3);
1478     void *IP = 0;
1479     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1480       return SDOperand(E, 0);
1481     N = new SDNode(Opcode, N1, N2, N3);
1482     N->setValueTypes(VTs, 1);
1483     CSEMap.InsertNode(N, IP);
1484   } else {
1485     N = new SDNode(Opcode, N1, N2, N3);
1486     N->setValueTypes(VTs, 1);
1487   }
1488   AllNodes.push_back(N);
1489   return SDOperand(N, 0);
1490 }
1491
1492 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1493                                 SDOperand N1, SDOperand N2, SDOperand N3,
1494                                 SDOperand N4) {
1495   SDOperand Ops[] = { N1, N2, N3, N4 };
1496   return getNode(Opcode, VT, Ops, 4);
1497 }
1498
1499 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1500                                 SDOperand N1, SDOperand N2, SDOperand N3,
1501                                 SDOperand N4, SDOperand N5) {
1502   SDOperand Ops[] = { N1, N2, N3, N4, N5 };
1503   return getNode(Opcode, VT, Ops, 5);
1504 }
1505
1506 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
1507                                 SDOperand Chain, SDOperand Ptr,
1508                                 SDOperand SV) {
1509   MVT::ValueType *VTs = getNodeValueTypes(VT, MVT::Other);
1510
1511   SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, SV);
1512   void *IP = 0;
1513   if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1514     return SDOperand(E, 0);
1515   SDNode *N = new SDNode(ISD::LOAD, Chain, Ptr, SV);
1516   N->setValueTypes(VTs, 2);
1517   CSEMap.InsertNode(N, IP);
1518   AllNodes.push_back(N);
1519   return SDOperand(N, 0);
1520 }
1521
1522 SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT,
1523                                    SDOperand Chain, SDOperand Ptr,
1524                                    SDOperand SV) {
1525   SDOperand Ops[] = { Chain, Ptr, SV, getConstant(Count, MVT::i32),
1526                       getValueType(EVT) };
1527   std::vector<MVT::ValueType> VTs;
1528   VTs.reserve(2);
1529   VTs.push_back(MVT::Vector); VTs.push_back(MVT::Other);  // Add token chain.
1530   return getNode(ISD::VLOAD, VTs, Ops, 5);
1531 }
1532
1533 SDOperand SelectionDAG::getExtLoad(unsigned Opcode, MVT::ValueType VT,
1534                                    SDOperand Chain, SDOperand Ptr, SDOperand SV,
1535                                    MVT::ValueType EVT) {
1536   SDOperand Ops[] = { Chain, Ptr, SV, getValueType(EVT) };
1537   std::vector<MVT::ValueType> VTs;
1538   VTs.reserve(2);
1539   VTs.push_back(VT); VTs.push_back(MVT::Other);  // Add token chain.
1540   return getNode(Opcode, VTs, Ops, 4);
1541 }
1542
1543 SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) {
1544   assert((!V || isa<PointerType>(V->getType())) &&
1545          "SrcValue is not a pointer?");
1546   SDNode *&N = ValueNodes[std::make_pair(V, Offset)];
1547   if (N) return SDOperand(N, 0);
1548
1549   N = new SrcValueSDNode(V, Offset);
1550   AllNodes.push_back(N);
1551   return SDOperand(N, 0);
1552 }
1553
1554 SDOperand SelectionDAG::getVAArg(MVT::ValueType VT,
1555                                  SDOperand Chain, SDOperand Ptr,
1556                                  SDOperand SV) {
1557   SDOperand Ops[] = { Chain, Ptr, SV };
1558   std::vector<MVT::ValueType> VTs;
1559   VTs.reserve(2);
1560   VTs.push_back(VT); VTs.push_back(MVT::Other);  // Add token chain.
1561   return getNode(ISD::VAARG, VTs, Ops, 3);
1562 }
1563
1564 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1565                                 const SDOperand *Ops, unsigned NumOps) {
1566   switch (NumOps) {
1567   case 0: return getNode(Opcode, VT);
1568   case 1: return getNode(Opcode, VT, Ops[0]);
1569   case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
1570   case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
1571   default: break;
1572   }
1573
1574   switch (Opcode) {
1575   default: break;
1576   case ISD::TRUNCSTORE: {
1577     assert(NumOps == 5 && "TRUNCSTORE takes 5 operands!");
1578     MVT::ValueType EVT = cast<VTSDNode>(Ops[4])->getVT();
1579 #if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store
1580     // If this is a truncating store of a constant, convert to the desired type
1581     // and store it instead.
1582     if (isa<Constant>(Ops[0])) {
1583       SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1);
1584       if (isa<Constant>(Op))
1585         N1 = Op;
1586     }
1587     // Also for ConstantFP?
1588 #endif
1589     if (Ops[0].getValueType() == EVT)       // Normal store?
1590       return getNode(ISD::STORE, VT, Ops[0], Ops[1], Ops[2], Ops[3]);
1591     assert(Ops[1].getValueType() > EVT && "Not a truncation?");
1592     assert(MVT::isInteger(Ops[1].getValueType()) == MVT::isInteger(EVT) &&
1593            "Can't do FP-INT conversion!");
1594     break;
1595   }
1596   case ISD::SELECT_CC: {
1597     assert(NumOps == 5 && "SELECT_CC takes 5 operands!");
1598     assert(Ops[0].getValueType() == Ops[1].getValueType() &&
1599            "LHS and RHS of condition must have same type!");
1600     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
1601            "True and False arms of SelectCC must have same type!");
1602     assert(Ops[2].getValueType() == VT &&
1603            "select_cc node must be of same type as true and false value!");
1604     break;
1605   }
1606   case ISD::BR_CC: {
1607     assert(NumOps == 5 && "BR_CC takes 5 operands!");
1608     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
1609            "LHS/RHS of comparison should match types!");
1610     break;
1611   }
1612   }
1613
1614   // Memoize nodes.
1615   SDNode *N;
1616   MVT::ValueType *VTs = getNodeValueTypes(VT);
1617   if (VT != MVT::Flag) {
1618     SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Ops, NumOps);
1619     void *IP = 0;
1620     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1621       return SDOperand(E, 0);
1622     N = new SDNode(Opcode, Ops, NumOps);
1623     N->setValueTypes(VTs, 1);
1624     CSEMap.InsertNode(N, IP);
1625   } else {
1626     N = new SDNode(Opcode, Ops, NumOps);
1627     N->setValueTypes(VTs, 1);
1628   }
1629   AllNodes.push_back(N);
1630   return SDOperand(N, 0);
1631 }
1632
1633 SDOperand SelectionDAG::getNode(unsigned Opcode,
1634                                 std::vector<MVT::ValueType> &ResultTys,
1635                                 const SDOperand *Ops, unsigned NumOps) {
1636   if (ResultTys.size() == 1)
1637     return getNode(Opcode, ResultTys[0], Ops, NumOps);
1638
1639   switch (Opcode) {
1640   case ISD::EXTLOAD:
1641   case ISD::SEXTLOAD:
1642   case ISD::ZEXTLOAD: {
1643     MVT::ValueType EVT = cast<VTSDNode>(Ops[3])->getVT();
1644     assert(NumOps == 4 && ResultTys.size() == 2 && "Bad *EXTLOAD!");
1645     // If they are asking for an extending load from/to the same thing, return a
1646     // normal load.
1647     if (ResultTys[0] == EVT)
1648       return getLoad(ResultTys[0], Ops[0], Ops[1], Ops[2]);
1649     if (MVT::isVector(ResultTys[0])) {
1650       assert(EVT == MVT::getVectorBaseType(ResultTys[0]) &&
1651              "Invalid vector extload!");
1652     } else {
1653       assert(EVT < ResultTys[0] &&
1654              "Should only be an extending load, not truncating!");
1655     }
1656     assert((Opcode == ISD::EXTLOAD || MVT::isInteger(ResultTys[0])) &&
1657            "Cannot sign/zero extend a FP/Vector load!");
1658     assert(MVT::isInteger(ResultTys[0]) == MVT::isInteger(EVT) &&
1659            "Cannot convert from FP to Int or Int -> FP!");
1660     break;
1661   }
1662
1663   // FIXME: figure out how to safely handle things like
1664   // int foo(int x) { return 1 << (x & 255); }
1665   // int bar() { return foo(256); }
1666 #if 0
1667   case ISD::SRA_PARTS:
1668   case ISD::SRL_PARTS:
1669   case ISD::SHL_PARTS:
1670     if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1671         cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
1672       return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1673     else if (N3.getOpcode() == ISD::AND)
1674       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
1675         // If the and is only masking out bits that cannot effect the shift,
1676         // eliminate the and.
1677         unsigned NumBits = MVT::getSizeInBits(VT)*2;
1678         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1679           return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1680       }
1681     break;
1682 #endif
1683   }
1684
1685   // Memoize the node unless it returns a flag.
1686   SDNode *N;
1687   MVT::ValueType *VTs = getNodeValueTypes(ResultTys);
1688   if (ResultTys.back() != MVT::Flag) {
1689     SelectionDAGCSEMap::NodeID ID;
1690     ID.SetOpcode(Opcode);
1691     ID.SetValueTypes(VTs);
1692     ID.SetOperands(&Ops[0], NumOps);
1693     void *IP = 0;
1694     if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP))
1695       return SDOperand(E, 0);
1696     N = new SDNode(Opcode, Ops, NumOps);
1697     N->setValueTypes(VTs, ResultTys.size());
1698     CSEMap.InsertNode(N, IP);
1699   } else {
1700     N = new SDNode(Opcode, Ops, NumOps);
1701     N->setValueTypes(VTs, ResultTys.size());
1702   }
1703   AllNodes.push_back(N);
1704   return SDOperand(N, 0);
1705 }
1706
1707
1708 MVT::ValueType *SelectionDAG::getNodeValueTypes(MVT::ValueType VT) {
1709   return SDNode::getValueTypeList(VT);
1710 }
1711
1712 MVT::ValueType *SelectionDAG::getNodeValueTypes(
1713                                         std::vector<MVT::ValueType> &RetVals) {
1714   switch (RetVals.size()) {
1715   case 0: assert(0 && "Cannot have nodes without results!");
1716   case 1: return SDNode::getValueTypeList(RetVals[0]);
1717   case 2: return getNodeValueTypes(RetVals[0], RetVals[1]);
1718   default: break;
1719   }
1720
1721   std::list<std::vector<MVT::ValueType> >::iterator I =
1722     std::find(VTList.begin(), VTList.end(), RetVals);
1723   if (I == VTList.end()) {
1724     VTList.push_front(RetVals);
1725     I = VTList.begin();
1726   }
1727
1728   return &(*I)[0];
1729 }
1730
1731 MVT::ValueType *SelectionDAG::getNodeValueTypes(MVT::ValueType VT1,
1732                                                 MVT::ValueType VT2) {
1733   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
1734        E = VTList.end(); I != E; ++I) {
1735     if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2)
1736       return &(*I)[0];
1737   }
1738   std::vector<MVT::ValueType> V;
1739   V.push_back(VT1);
1740   V.push_back(VT2);
1741   VTList.push_front(V);
1742   return &(*VTList.begin())[0];
1743 }
1744
1745 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the
1746 /// specified operands.  If the resultant node already exists in the DAG,
1747 /// this does not modify the specified node, instead it returns the node that
1748 /// already exists.  If the resultant node does not exist in the DAG, the
1749 /// input node is returned.  As a degenerate case, if you specify the same
1750 /// input operands as the node already has, the input node is returned.
1751 SDOperand SelectionDAG::
1752 UpdateNodeOperands(SDOperand InN, SDOperand Op) {
1753   SDNode *N = InN.Val;
1754   assert(N->getNumOperands() == 1 && "Update with wrong number of operands");
1755
1756   // Check to see if there is no change.
1757   if (Op == N->getOperand(0)) return InN;
1758
1759   // See if the modified node already exists.
1760   void *InsertPos = 0;
1761   if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos))
1762     return SDOperand(Existing, InN.ResNo);
1763
1764   // Nope it doesn't.  Remove the node from it's current place in the maps.
1765   if (InsertPos)
1766     RemoveNodeFromCSEMaps(N);
1767
1768   // Now we update the operands.
1769   N->OperandList[0].Val->removeUser(N);
1770   Op.Val->addUser(N);
1771   N->OperandList[0] = Op;
1772
1773   // If this gets put into a CSE map, add it.
1774   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
1775   return InN;
1776 }
1777
1778 SDOperand SelectionDAG::
1779 UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) {
1780   SDNode *N = InN.Val;
1781   assert(N->getNumOperands() == 2 && "Update with wrong number of operands");
1782
1783   // Check to see if there is no change.
1784   bool AnyChange = false;
1785   if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1))
1786     return InN;   // No operands changed, just return the input node.
1787
1788   // See if the modified node already exists.
1789   void *InsertPos = 0;
1790   if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos))
1791     return SDOperand(Existing, InN.ResNo);
1792
1793   // Nope it doesn't.  Remove the node from it's current place in the maps.
1794   if (InsertPos)
1795     RemoveNodeFromCSEMaps(N);
1796
1797   // Now we update the operands.
1798   if (N->OperandList[0] != Op1) {
1799     N->OperandList[0].Val->removeUser(N);
1800     Op1.Val->addUser(N);
1801     N->OperandList[0] = Op1;
1802   }
1803   if (N->OperandList[1] != Op2) {
1804     N->OperandList[1].Val->removeUser(N);
1805     Op2.Val->addUser(N);
1806     N->OperandList[1] = Op2;
1807   }
1808
1809   // If this gets put into a CSE map, add it.
1810   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
1811   return InN;
1812 }
1813
1814 SDOperand SelectionDAG::
1815 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) {
1816   SDOperand Ops[] = { Op1, Op2, Op3 };
1817   return UpdateNodeOperands(N, Ops, 3);
1818 }
1819
1820 SDOperand SelectionDAG::
1821 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
1822                    SDOperand Op3, SDOperand Op4) {
1823   SDOperand Ops[] = { Op1, Op2, Op3, Op4 };
1824   return UpdateNodeOperands(N, Ops, 4);
1825 }
1826
1827 SDOperand SelectionDAG::
1828 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2,
1829                    SDOperand Op3, SDOperand Op4, SDOperand Op5) {
1830   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
1831   return UpdateNodeOperands(N, Ops, 5);
1832 }
1833
1834
1835 SDOperand SelectionDAG::
1836 UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) {
1837   SDNode *N = InN.Val;
1838   assert(N->getNumOperands() == NumOps &&
1839          "Update with wrong number of operands");
1840
1841   // Check to see if there is no change.
1842   bool AnyChange = false;
1843   for (unsigned i = 0; i != NumOps; ++i) {
1844     if (Ops[i] != N->getOperand(i)) {
1845       AnyChange = true;
1846       break;
1847     }
1848   }
1849
1850   // No operands changed, just return the input node.
1851   if (!AnyChange) return InN;
1852
1853   // See if the modified node already exists.
1854   void *InsertPos = 0;
1855   if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos))
1856     return SDOperand(Existing, InN.ResNo);
1857
1858   // Nope it doesn't.  Remove the node from it's current place in the maps.
1859   if (InsertPos)
1860     RemoveNodeFromCSEMaps(N);
1861
1862   // Now we update the operands.
1863   for (unsigned i = 0; i != NumOps; ++i) {
1864     if (N->OperandList[i] != Ops[i]) {
1865       N->OperandList[i].Val->removeUser(N);
1866       Ops[i].Val->addUser(N);
1867       N->OperandList[i] = Ops[i];
1868     }
1869   }
1870
1871   // If this gets put into a CSE map, add it.
1872   if (InsertPos) CSEMap.InsertNode(N, InsertPos);
1873   return InN;
1874 }
1875
1876
1877
1878
1879 /// SelectNodeTo - These are used for target selectors to *mutate* the
1880 /// specified node to have the specified return type, Target opcode, and
1881 /// operands.  Note that target opcodes are stored as
1882 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
1883 ///
1884 /// Note that SelectNodeTo returns the resultant node.  If there is already a
1885 /// node of the specified opcode and operands, it returns that node instead of
1886 /// the current one.
1887 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1888                                      MVT::ValueType VT) {
1889   MVT::ValueType *VTs = getNodeValueTypes(VT);
1890   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
1891   void *IP = 0;
1892   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1893     return SDOperand(ON, 0);
1894
1895   RemoveNodeFromCSEMaps(N);
1896
1897   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1898   N->setValueTypes(getNodeValueTypes(VT), 1);
1899
1900   CSEMap.InsertNode(N, IP);
1901   return SDOperand(N, 0);
1902 }
1903
1904 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1905                                      MVT::ValueType VT, SDOperand Op1) {
1906   // If an identical node already exists, use it.
1907   MVT::ValueType *VTs = getNodeValueTypes(VT);
1908   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1);
1909   void *IP = 0;
1910   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1911     return SDOperand(ON, 0);
1912
1913   RemoveNodeFromCSEMaps(N);
1914   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1915   N->setValueTypes(getNodeValueTypes(VT), 1);
1916   N->setOperands(Op1);
1917   CSEMap.InsertNode(N, IP);
1918   return SDOperand(N, 0);
1919 }
1920
1921 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1922                                      MVT::ValueType VT, SDOperand Op1,
1923                                      SDOperand Op2) {
1924   // If an identical node already exists, use it.
1925   MVT::ValueType *VTs = getNodeValueTypes(VT);
1926   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
1927   void *IP = 0;
1928   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1929     return SDOperand(ON, 0);
1930
1931   RemoveNodeFromCSEMaps(N);
1932   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1933   N->setValueTypes(VTs, 1);
1934   N->setOperands(Op1, Op2);
1935
1936   CSEMap.InsertNode(N, IP);   // Memoize the new node.
1937   return SDOperand(N, 0);
1938 }
1939
1940 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1941                                      MVT::ValueType VT, SDOperand Op1,
1942                                      SDOperand Op2, SDOperand Op3) {
1943   // If an identical node already exists, use it.
1944   MVT::ValueType *VTs = getNodeValueTypes(VT);
1945   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2, Op3);
1946   void *IP = 0;
1947   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1948     return SDOperand(ON, 0);
1949
1950   RemoveNodeFromCSEMaps(N);
1951   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1952   N->setValueTypes(VTs, 1);
1953   N->setOperands(Op1, Op2, Op3);
1954
1955   CSEMap.InsertNode(N, IP);   // Memoize the new node.
1956   return SDOperand(N, 0);
1957 }
1958
1959 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1960                                      MVT::ValueType VT, SDOperand Op1,
1961                                      SDOperand Op2, SDOperand Op3,
1962                                      SDOperand Op4) {
1963   // If an identical node already exists, use it.
1964   MVT::ValueType *VTs = getNodeValueTypes(VT);
1965   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
1966   ID.AddOperand(Op1);
1967   ID.AddOperand(Op2);
1968   ID.AddOperand(Op3);
1969   ID.AddOperand(Op4);
1970   void *IP = 0;
1971   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1972     return SDOperand(ON, 0);
1973
1974   RemoveNodeFromCSEMaps(N);
1975   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1976   N->setValueTypes(VTs, 1);
1977   N->setOperands(Op1, Op2, Op3, Op4);
1978
1979   CSEMap.InsertNode(N, IP);   // Memoize the new node.
1980   return SDOperand(N, 0);
1981 }
1982
1983 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1984                                      MVT::ValueType VT, SDOperand Op1,
1985                                      SDOperand Op2, SDOperand Op3,
1986                                      SDOperand Op4, SDOperand Op5) {
1987   MVT::ValueType *VTs = getNodeValueTypes(VT);
1988   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
1989   ID.AddOperand(Op1);
1990   ID.AddOperand(Op2);
1991   ID.AddOperand(Op3);
1992   ID.AddOperand(Op4);
1993   ID.AddOperand(Op5);
1994   void *IP = 0;
1995   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
1996     return SDOperand(ON, 0);
1997
1998   RemoveNodeFromCSEMaps(N);
1999   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2000   N->setValueTypes(VTs, 1);
2001   N->setOperands(Op1, Op2, Op3, Op4, Op5);
2002
2003   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2004   return SDOperand(N, 0);
2005 }
2006
2007 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2008                                      MVT::ValueType VT, SDOperand Op1,
2009                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
2010                                      SDOperand Op5, SDOperand Op6) {
2011   MVT::ValueType *VTs = getNodeValueTypes(VT);
2012   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
2013   ID.AddOperand(Op1);
2014   ID.AddOperand(Op2);
2015   ID.AddOperand(Op3);
2016   ID.AddOperand(Op4);
2017   ID.AddOperand(Op5);
2018   ID.AddOperand(Op6);
2019   void *IP = 0;
2020   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2021     return SDOperand(ON, 0);
2022
2023   RemoveNodeFromCSEMaps(N);
2024   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2025   N->setValueTypes(VTs, 1);
2026   N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6);
2027
2028   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2029   return SDOperand(N, 0);
2030 }
2031
2032 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2033                                      MVT::ValueType VT, SDOperand Op1,
2034                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
2035                                      SDOperand Op5, SDOperand Op6,
2036                                      SDOperand Op7) {
2037   MVT::ValueType *VTs = getNodeValueTypes(VT);
2038   // If an identical node already exists, use it.
2039   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
2040   ID.AddOperand(Op1);
2041   ID.AddOperand(Op2);
2042   ID.AddOperand(Op3);
2043   ID.AddOperand(Op4);
2044   ID.AddOperand(Op5);
2045   ID.AddOperand(Op6);
2046   ID.AddOperand(Op7);
2047   void *IP = 0;
2048   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2049     return SDOperand(ON, 0);
2050
2051   RemoveNodeFromCSEMaps(N);
2052   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2053   N->setValueTypes(VTs, 1);
2054   N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7);
2055
2056   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2057   return SDOperand(N, 0);
2058 }
2059 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2060                                      MVT::ValueType VT, SDOperand Op1,
2061                                      SDOperand Op2, SDOperand Op3,SDOperand Op4,
2062                                      SDOperand Op5, SDOperand Op6,
2063                                      SDOperand Op7, SDOperand Op8) {
2064   // If an identical node already exists, use it.
2065   MVT::ValueType *VTs = getNodeValueTypes(VT);
2066   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
2067   ID.AddOperand(Op1);
2068   ID.AddOperand(Op2);
2069   ID.AddOperand(Op3);
2070   ID.AddOperand(Op4);
2071   ID.AddOperand(Op5);
2072   ID.AddOperand(Op6);
2073   ID.AddOperand(Op7);
2074   ID.AddOperand(Op8);
2075   void *IP = 0;
2076   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2077     return SDOperand(ON, 0);
2078
2079   RemoveNodeFromCSEMaps(N);
2080   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2081   N->setValueTypes(VTs, 1);
2082   N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7, Op8);
2083
2084   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2085   return SDOperand(N, 0);
2086 }
2087
2088 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2089                                      MVT::ValueType VT1, MVT::ValueType VT2,
2090                                      SDOperand Op1, SDOperand Op2) {
2091   MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2092   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2);
2093   void *IP = 0;
2094   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2095     return SDOperand(ON, 0);
2096
2097   RemoveNodeFromCSEMaps(N);
2098   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2099   N->setValueTypes(VTs, 2);
2100   N->setOperands(Op1, Op2);
2101
2102   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2103   return SDOperand(N, 0);
2104 }
2105
2106 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2107                                      MVT::ValueType VT1, MVT::ValueType VT2,
2108                                      SDOperand Op1, SDOperand Op2,
2109                                      SDOperand Op3) {
2110   // If an identical node already exists, use it.
2111   MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2112   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs,
2113                                 Op1, Op2, Op3);
2114   void *IP = 0;
2115   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2116     return SDOperand(ON, 0);
2117
2118   RemoveNodeFromCSEMaps(N);
2119   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2120   N->setValueTypes(VTs, 2);
2121   N->setOperands(Op1, Op2, Op3);
2122
2123   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2124   return SDOperand(N, 0);
2125 }
2126
2127 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2128                                      MVT::ValueType VT1, MVT::ValueType VT2,
2129                                      SDOperand Op1, SDOperand Op2,
2130                                      SDOperand Op3, SDOperand Op4) {
2131   // If an identical node already exists, use it.
2132   MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2133   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
2134   ID.AddOperand(Op1);
2135   ID.AddOperand(Op2);
2136   ID.AddOperand(Op3);
2137   ID.AddOperand(Op4);
2138   void *IP = 0;
2139   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2140     return SDOperand(ON, 0);
2141
2142   RemoveNodeFromCSEMaps(N);
2143   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2144   N->setValueTypes(VTs, 2);
2145   N->setOperands(Op1, Op2, Op3, Op4);
2146
2147   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2148   return SDOperand(N, 0);
2149 }
2150
2151 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
2152                                      MVT::ValueType VT1, MVT::ValueType VT2,
2153                                      SDOperand Op1, SDOperand Op2,
2154                                      SDOperand Op3, SDOperand Op4,
2155                                      SDOperand Op5) {
2156   // If an identical node already exists, use it.
2157   MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2);
2158   SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs);
2159   ID.AddOperand(Op1);
2160   ID.AddOperand(Op2);
2161   ID.AddOperand(Op3);
2162   ID.AddOperand(Op4);
2163   ID.AddOperand(Op5);
2164   void *IP = 0;
2165   if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP))
2166     return SDOperand(ON, 0);
2167
2168   RemoveNodeFromCSEMaps(N);
2169   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
2170   N->setValueTypes(VTs, 2);
2171   N->setOperands(Op1, Op2, Op3, Op4, Op5);
2172
2173   CSEMap.InsertNode(N, IP);   // Memoize the new node.
2174   return SDOperand(N, 0);
2175 }
2176
2177 /// getTargetNode - These are used for target selectors to create a new node
2178 /// with specified return type(s), target opcode, and operands.
2179 ///
2180 /// Note that getTargetNode returns the resultant node.  If there is already a
2181 /// node of the specified opcode and operands, it returns that node instead of
2182 /// the current one.
2183 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) {
2184   return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val;
2185 }
2186 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2187                                     SDOperand Op1) {
2188   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val;
2189 }
2190 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2191                                     SDOperand Op1, SDOperand Op2) {
2192   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val;
2193 }
2194 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2195                                     SDOperand Op1, SDOperand Op2, SDOperand Op3) {
2196   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val;
2197 }
2198 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2199                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2200                                     SDOperand Op4) {
2201   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4).Val;
2202 }
2203 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2204                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2205                                     SDOperand Op4, SDOperand Op5) {
2206   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4, Op5).Val;
2207 }
2208 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2209                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2210                                     SDOperand Op4, SDOperand Op5,
2211                                     SDOperand Op6) {
2212   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6 };
2213   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, 6).Val;
2214 }
2215 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2216                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2217                                     SDOperand Op4, SDOperand Op5, SDOperand Op6,
2218                                     SDOperand Op7) {
2219   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6, Op7 };
2220   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, 7).Val;
2221 }
2222 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2223                                     SDOperand Op1, SDOperand Op2, SDOperand Op3,
2224                                     SDOperand Op4, SDOperand Op5, SDOperand Op6,
2225                                     SDOperand Op7, SDOperand Op8) {
2226   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6, Op7, Op8 };
2227   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, 8).Val;
2228 }
2229 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT,
2230                                     const SDOperand *Ops, unsigned NumOps) {
2231   return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val;
2232 }
2233 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2234                                     MVT::ValueType VT2, SDOperand Op1) {
2235   std::vector<MVT::ValueType> ResultTys;
2236   ResultTys.push_back(VT1);
2237   ResultTys.push_back(VT2);
2238   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, &Op1, 1).Val;
2239 }
2240 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2241                                     MVT::ValueType VT2, SDOperand Op1,
2242                                     SDOperand Op2) {
2243   std::vector<MVT::ValueType> ResultTys;
2244   ResultTys.push_back(VT1);
2245   ResultTys.push_back(VT2);
2246   SDOperand Ops[] = { Op1, Op2 };
2247   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 2).Val;
2248 }
2249 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2250                                     MVT::ValueType VT2, SDOperand Op1,
2251                                     SDOperand Op2, SDOperand Op3) {
2252   std::vector<MVT::ValueType> ResultTys;
2253   ResultTys.push_back(VT1);
2254   ResultTys.push_back(VT2);
2255   SDOperand Ops[] = { Op1, Op2, Op3 };
2256   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 3).Val;
2257 }
2258 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2259                                     MVT::ValueType VT2, SDOperand Op1,
2260                                     SDOperand Op2, SDOperand Op3,
2261                                     SDOperand Op4) {
2262   std::vector<MVT::ValueType> ResultTys;
2263   ResultTys.push_back(VT1);
2264   ResultTys.push_back(VT2);
2265   SDOperand Ops[] = { Op1, Op2, Op3, Op4 };
2266   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 4).Val;
2267 }
2268 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2269                                     MVT::ValueType VT2, SDOperand Op1,
2270                                     SDOperand Op2, SDOperand Op3, SDOperand Op4,
2271                                     SDOperand Op5) {
2272   std::vector<MVT::ValueType> ResultTys;
2273   ResultTys.push_back(VT1);
2274   ResultTys.push_back(VT2);
2275   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
2276   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 5).Val;
2277 }
2278 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2279                                     MVT::ValueType VT2, SDOperand Op1,
2280                                     SDOperand Op2, SDOperand Op3, SDOperand Op4,
2281                                     SDOperand Op5, SDOperand Op6) {
2282   std::vector<MVT::ValueType> ResultTys;
2283   ResultTys.push_back(VT1);
2284   ResultTys.push_back(VT2);
2285   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6 };
2286   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 6).Val;
2287 }
2288 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2289                                     MVT::ValueType VT2, SDOperand Op1,
2290                                     SDOperand Op2, SDOperand Op3, SDOperand Op4,
2291                                     SDOperand Op5, SDOperand Op6,
2292                                     SDOperand Op7) {
2293   std::vector<MVT::ValueType> ResultTys;
2294   ResultTys.push_back(VT1);
2295   ResultTys.push_back(VT2);
2296   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6, Op7 };
2297   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 7).Val;
2298 }
2299 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2300                                     MVT::ValueType VT2, MVT::ValueType VT3,
2301                                     SDOperand Op1, SDOperand Op2) {
2302   std::vector<MVT::ValueType> ResultTys;
2303   ResultTys.push_back(VT1);
2304   ResultTys.push_back(VT2);
2305   ResultTys.push_back(VT3);
2306   SDOperand Ops[] = { Op1, Op2 };
2307   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 2).Val;
2308 }
2309 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2310                                     MVT::ValueType VT2, MVT::ValueType VT3,
2311                                     SDOperand Op1, SDOperand Op2,
2312                                     SDOperand Op3, SDOperand Op4,
2313                                     SDOperand Op5) {
2314   std::vector<MVT::ValueType> ResultTys;
2315   ResultTys.push_back(VT1);
2316   ResultTys.push_back(VT2);
2317   ResultTys.push_back(VT3);
2318   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 };
2319   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 5).Val;
2320 }
2321 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2322                                     MVT::ValueType VT2, MVT::ValueType VT3,
2323                                     SDOperand Op1, SDOperand Op2,
2324                                     SDOperand Op3, SDOperand Op4, SDOperand Op5,
2325                                     SDOperand Op6) {
2326   std::vector<MVT::ValueType> ResultTys;
2327   ResultTys.push_back(VT1);
2328   ResultTys.push_back(VT2);
2329   ResultTys.push_back(VT3);
2330   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6 };
2331   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 6).Val;
2332 }
2333 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2334                                     MVT::ValueType VT2, MVT::ValueType VT3,
2335                                     SDOperand Op1, SDOperand Op2,
2336                                     SDOperand Op3, SDOperand Op4, SDOperand Op5,
2337                                     SDOperand Op6, SDOperand Op7) {
2338   std::vector<MVT::ValueType> ResultTys;
2339   ResultTys.push_back(VT1);
2340   ResultTys.push_back(VT2);
2341   ResultTys.push_back(VT3);
2342   SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5, Op6, Op7 };
2343   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, 7).Val;
2344 }
2345 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1,
2346                                     MVT::ValueType VT2,
2347                                     const SDOperand *Ops, unsigned NumOps) {
2348   std::vector<MVT::ValueType> ResultTys;
2349   ResultTys.push_back(VT1);
2350   ResultTys.push_back(VT2);
2351   return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops, NumOps).Val;
2352 }
2353
2354 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
2355 /// This can cause recursive merging of nodes in the DAG.
2356 ///
2357 /// This version assumes From/To have a single result value.
2358 ///
2359 void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN,
2360                                       std::vector<SDNode*> *Deleted) {
2361   SDNode *From = FromN.Val, *To = ToN.Val;
2362   assert(From->getNumValues() == 1 && To->getNumValues() == 1 &&
2363          "Cannot replace with this method!");
2364   assert(From != To && "Cannot replace uses of with self");
2365
2366   while (!From->use_empty()) {
2367     // Process users until they are all gone.
2368     SDNode *U = *From->use_begin();
2369
2370     // This node is about to morph, remove its old self from the CSE maps.
2371     RemoveNodeFromCSEMaps(U);
2372
2373     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
2374          I != E; ++I)
2375       if (I->Val == From) {
2376         From->removeUser(U);
2377         I->Val = To;
2378         To->addUser(U);
2379       }
2380
2381     // Now that we have modified U, add it back to the CSE maps.  If it already
2382     // exists there, recursively merge the results together.
2383     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
2384       ReplaceAllUsesWith(U, Existing, Deleted);
2385       // U is now dead.
2386       if (Deleted) Deleted->push_back(U);
2387       DeleteNodeNotInCSEMaps(U);
2388     }
2389   }
2390 }
2391
2392 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
2393 /// This can cause recursive merging of nodes in the DAG.
2394 ///
2395 /// This version assumes From/To have matching types and numbers of result
2396 /// values.
2397 ///
2398 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
2399                                       std::vector<SDNode*> *Deleted) {
2400   assert(From != To && "Cannot replace uses of with self");
2401   assert(From->getNumValues() == To->getNumValues() &&
2402          "Cannot use this version of ReplaceAllUsesWith!");
2403   if (From->getNumValues() == 1) {  // If possible, use the faster version.
2404     ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted);
2405     return;
2406   }
2407
2408   while (!From->use_empty()) {
2409     // Process users until they are all gone.
2410     SDNode *U = *From->use_begin();
2411
2412     // This node is about to morph, remove its old self from the CSE maps.
2413     RemoveNodeFromCSEMaps(U);
2414
2415     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
2416          I != E; ++I)
2417       if (I->Val == From) {
2418         From->removeUser(U);
2419         I->Val = To;
2420         To->addUser(U);
2421       }
2422
2423     // Now that we have modified U, add it back to the CSE maps.  If it already
2424     // exists there, recursively merge the results together.
2425     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
2426       ReplaceAllUsesWith(U, Existing, Deleted);
2427       // U is now dead.
2428       if (Deleted) Deleted->push_back(U);
2429       DeleteNodeNotInCSEMaps(U);
2430     }
2431   }
2432 }
2433
2434 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
2435 /// This can cause recursive merging of nodes in the DAG.
2436 ///
2437 /// This version can replace From with any result values.  To must match the
2438 /// number and types of values returned by From.
2439 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
2440                                       const SDOperand *To,
2441                                       std::vector<SDNode*> *Deleted) {
2442   if (From->getNumValues() == 1 && To[0].Val->getNumValues() == 1) {
2443     // Degenerate case handled above.
2444     ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted);
2445     return;
2446   }
2447
2448   while (!From->use_empty()) {
2449     // Process users until they are all gone.
2450     SDNode *U = *From->use_begin();
2451
2452     // This node is about to morph, remove its old self from the CSE maps.
2453     RemoveNodeFromCSEMaps(U);
2454
2455     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
2456          I != E; ++I)
2457       if (I->Val == From) {
2458         const SDOperand &ToOp = To[I->ResNo];
2459         From->removeUser(U);
2460         *I = ToOp;
2461         ToOp.Val->addUser(U);
2462       }
2463
2464     // Now that we have modified U, add it back to the CSE maps.  If it already
2465     // exists there, recursively merge the results together.
2466     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
2467       ReplaceAllUsesWith(U, Existing, Deleted);
2468       // U is now dead.
2469       if (Deleted) Deleted->push_back(U);
2470       DeleteNodeNotInCSEMaps(U);
2471     }
2472   }
2473 }
2474
2475 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving
2476 /// uses of other values produced by From.Val alone.  The Deleted vector is
2477 /// handled the same was as for ReplaceAllUsesWith.
2478 void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To,
2479                                              std::vector<SDNode*> &Deleted) {
2480   assert(From != To && "Cannot replace a value with itself");
2481   // Handle the simple, trivial, case efficiently.
2482   if (From.Val->getNumValues() == 1 && To.Val->getNumValues() == 1) {
2483     ReplaceAllUsesWith(From, To, &Deleted);
2484     return;
2485   }
2486
2487   // Get all of the users in a nice, deterministically ordered, uniqued set.
2488   SetVector<SDNode*> Users(From.Val->use_begin(), From.Val->use_end());
2489
2490   while (!Users.empty()) {
2491     // We know that this user uses some value of From.  If it is the right
2492     // value, update it.
2493     SDNode *User = Users.back();
2494     Users.pop_back();
2495
2496     for (SDOperand *Op = User->OperandList,
2497          *E = User->OperandList+User->NumOperands; Op != E; ++Op) {
2498       if (*Op == From) {
2499         // Okay, we know this user needs to be updated.  Remove its old self
2500         // from the CSE maps.
2501         RemoveNodeFromCSEMaps(User);
2502
2503         // Update all operands that match "From".
2504         for (; Op != E; ++Op) {
2505           if (*Op == From) {
2506             From.Val->removeUser(User);
2507             *Op = To;
2508             To.Val->addUser(User);
2509           }
2510         }
2511
2512         // Now that we have modified User, add it back to the CSE maps.  If it
2513         // already exists there, recursively merge the results together.
2514         if (SDNode *Existing = AddNonLeafNodeToCSEMaps(User)) {
2515           unsigned NumDeleted = Deleted.size();
2516           ReplaceAllUsesWith(User, Existing, &Deleted);
2517
2518           // User is now dead.
2519           Deleted.push_back(User);
2520           DeleteNodeNotInCSEMaps(User);
2521
2522           // We have to be careful here, because ReplaceAllUsesWith could have
2523           // deleted a user of From, which means there may be dangling pointers
2524           // in the "Users" setvector.  Scan over the deleted node pointers and
2525           // remove them from the setvector.
2526           for (unsigned i = NumDeleted, e = Deleted.size(); i != e; ++i)
2527             Users.remove(Deleted[i]);
2528         }
2529         break;   // Exit the operand scanning loop.
2530       }
2531     }
2532   }
2533 }
2534
2535
2536 /// AssignNodeIds - Assign a unique node id for each node in the DAG based on
2537 /// their allnodes order. It returns the maximum id.
2538 unsigned SelectionDAG::AssignNodeIds() {
2539   unsigned Id = 0;
2540   for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){
2541     SDNode *N = I;
2542     N->setNodeId(Id++);
2543   }
2544   return Id;
2545 }
2546
2547 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG
2548 /// based on their topological order. It returns the maximum id and a vector
2549 /// of the SDNodes* in assigned order by reference.
2550 unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) {
2551   unsigned DAGSize = AllNodes.size();
2552   std::vector<unsigned> InDegree(DAGSize);
2553   std::vector<SDNode*> Sources;
2554
2555   // Use a two pass approach to avoid using a std::map which is slow.
2556   unsigned Id = 0;
2557   for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){
2558     SDNode *N = I;
2559     N->setNodeId(Id++);
2560     unsigned Degree = N->use_size();
2561     InDegree[N->getNodeId()] = Degree;
2562     if (Degree == 0)
2563       Sources.push_back(N);
2564   }
2565
2566   TopOrder.clear();
2567   while (!Sources.empty()) {
2568     SDNode *N = Sources.back();
2569     Sources.pop_back();
2570     TopOrder.push_back(N);
2571     for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
2572       SDNode *P = I->Val;
2573       unsigned Degree = --InDegree[P->getNodeId()];
2574       if (Degree == 0)
2575         Sources.push_back(P);
2576     }
2577   }
2578
2579   // Second pass, assign the actual topological order as node ids.
2580   Id = 0;
2581   for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end();
2582        TI != TE; ++TI)
2583     (*TI)->setNodeId(Id++);
2584
2585   return Id;
2586 }
2587
2588
2589
2590 //===----------------------------------------------------------------------===//
2591 //                              SDNode Class
2592 //===----------------------------------------------------------------------===//
2593
2594 // Out-of-line virtual method to give class a home.
2595 void SDNode::ANCHOR() {
2596 }
2597
2598 /// getValueTypeList - Return a pointer to the specified value type.
2599 ///
2600 MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
2601   static MVT::ValueType VTs[MVT::LAST_VALUETYPE];
2602   VTs[VT] = VT;
2603   return &VTs[VT];
2604 }
2605
2606 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
2607 /// indicated value.  This method ignores uses of other values defined by this
2608 /// operation.
2609 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const {
2610   assert(Value < getNumValues() && "Bad value!");
2611
2612   // If there is only one value, this is easy.
2613   if (getNumValues() == 1)
2614     return use_size() == NUses;
2615   if (Uses.size() < NUses) return false;
2616
2617   SDOperand TheValue(const_cast<SDNode *>(this), Value);
2618
2619   std::set<SDNode*> UsersHandled;
2620
2621   for (std::vector<SDNode*>::const_iterator UI = Uses.begin(), E = Uses.end();
2622        UI != E; ++UI) {
2623     SDNode *User = *UI;
2624     if (User->getNumOperands() == 1 ||
2625         UsersHandled.insert(User).second)     // First time we've seen this?
2626       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
2627         if (User->getOperand(i) == TheValue) {
2628           if (NUses == 0)
2629             return false;   // too many uses
2630           --NUses;
2631         }
2632   }
2633
2634   // Found exactly the right number of uses?
2635   return NUses == 0;
2636 }
2637
2638
2639 // isOnlyUse - Return true if this node is the only use of N.
2640 bool SDNode::isOnlyUse(SDNode *N) const {
2641   bool Seen = false;
2642   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
2643     SDNode *User = *I;
2644     if (User == this)
2645       Seen = true;
2646     else
2647       return false;
2648   }
2649
2650   return Seen;
2651 }
2652
2653 // isOperand - Return true if this node is an operand of N.
2654 bool SDOperand::isOperand(SDNode *N) const {
2655   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
2656     if (*this == N->getOperand(i))
2657       return true;
2658   return false;
2659 }
2660
2661 bool SDNode::isOperand(SDNode *N) const {
2662   for (unsigned i = 0, e = N->NumOperands; i != e; ++i)
2663     if (this == N->OperandList[i].Val)
2664       return true;
2665   return false;
2666 }
2667
2668 const char *SDNode::getOperationName(const SelectionDAG *G) const {
2669   switch (getOpcode()) {
2670   default:
2671     if (getOpcode() < ISD::BUILTIN_OP_END)
2672       return "<<Unknown DAG Node>>";
2673     else {
2674       if (G) {
2675         if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
2676           if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
2677             return TII->getName(getOpcode()-ISD::BUILTIN_OP_END);
2678
2679         TargetLowering &TLI = G->getTargetLoweringInfo();
2680         const char *Name =
2681           TLI.getTargetNodeName(getOpcode());
2682         if (Name) return Name;
2683       }
2684
2685       return "<<Unknown Target Node>>";
2686     }
2687
2688   case ISD::PCMARKER:      return "PCMarker";
2689   case ISD::READCYCLECOUNTER: return "ReadCycleCounter";
2690   case ISD::SRCVALUE:      return "SrcValue";
2691   case ISD::EntryToken:    return "EntryToken";
2692   case ISD::TokenFactor:   return "TokenFactor";
2693   case ISD::AssertSext:    return "AssertSext";
2694   case ISD::AssertZext:    return "AssertZext";
2695
2696   case ISD::STRING:        return "String";
2697   case ISD::BasicBlock:    return "BasicBlock";
2698   case ISD::VALUETYPE:     return "ValueType";
2699   case ISD::Register:      return "Register";
2700
2701   case ISD::Constant:      return "Constant";
2702   case ISD::ConstantFP:    return "ConstantFP";
2703   case ISD::GlobalAddress: return "GlobalAddress";
2704   case ISD::FrameIndex:    return "FrameIndex";
2705   case ISD::JumpTable:     return "JumpTable";
2706   case ISD::ConstantPool:  return "ConstantPool";
2707   case ISD::ExternalSymbol: return "ExternalSymbol";
2708   case ISD::INTRINSIC_WO_CHAIN: {
2709     unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue();
2710     return Intrinsic::getName((Intrinsic::ID)IID);
2711   }
2712   case ISD::INTRINSIC_VOID:
2713   case ISD::INTRINSIC_W_CHAIN: {
2714     unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue();
2715     return Intrinsic::getName((Intrinsic::ID)IID);
2716   }
2717
2718   case ISD::BUILD_VECTOR:   return "BUILD_VECTOR";
2719   case ISD::TargetConstant: return "TargetConstant";
2720   case ISD::TargetConstantFP:return "TargetConstantFP";
2721   case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
2722   case ISD::TargetFrameIndex: return "TargetFrameIndex";
2723   case ISD::TargetJumpTable:  return "TargetJumpTable";
2724   case ISD::TargetConstantPool:  return "TargetConstantPool";
2725   case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
2726
2727   case ISD::CopyToReg:     return "CopyToReg";
2728   case ISD::CopyFromReg:   return "CopyFromReg";
2729   case ISD::UNDEF:         return "undef";
2730   case ISD::MERGE_VALUES:  return "mergevalues";
2731   case ISD::INLINEASM:     return "inlineasm";
2732   case ISD::HANDLENODE:    return "handlenode";
2733   case ISD::FORMAL_ARGUMENTS: return "formal_arguments";
2734   case ISD::CALL:          return "call";
2735
2736   // Unary operators
2737   case ISD::FABS:   return "fabs";
2738   case ISD::FNEG:   return "fneg";
2739   case ISD::FSQRT:  return "fsqrt";
2740   case ISD::FSIN:   return "fsin";
2741   case ISD::FCOS:   return "fcos";
2742
2743   // Binary operators
2744   case ISD::ADD:    return "add";
2745   case ISD::SUB:    return "sub";
2746   case ISD::MUL:    return "mul";
2747   case ISD::MULHU:  return "mulhu";
2748   case ISD::MULHS:  return "mulhs";
2749   case ISD::SDIV:   return "sdiv";
2750   case ISD::UDIV:   return "udiv";
2751   case ISD::SREM:   return "srem";
2752   case ISD::UREM:   return "urem";
2753   case ISD::AND:    return "and";
2754   case ISD::OR:     return "or";
2755   case ISD::XOR:    return "xor";
2756   case ISD::SHL:    return "shl";
2757   case ISD::SRA:    return "sra";
2758   case ISD::SRL:    return "srl";
2759   case ISD::ROTL:   return "rotl";
2760   case ISD::ROTR:   return "rotr";
2761   case ISD::FADD:   return "fadd";
2762   case ISD::FSUB:   return "fsub";
2763   case ISD::FMUL:   return "fmul";
2764   case ISD::FDIV:   return "fdiv";
2765   case ISD::FREM:   return "frem";
2766   case ISD::FCOPYSIGN: return "fcopysign";
2767   case ISD::VADD:   return "vadd";
2768   case ISD::VSUB:   return "vsub";
2769   case ISD::VMUL:   return "vmul";
2770   case ISD::VSDIV:  return "vsdiv";
2771   case ISD::VUDIV:  return "vudiv";
2772   case ISD::VAND:   return "vand";
2773   case ISD::VOR:    return "vor";
2774   case ISD::VXOR:   return "vxor";
2775
2776   case ISD::SETCC:       return "setcc";
2777   case ISD::SELECT:      return "select";
2778   case ISD::SELECT_CC:   return "select_cc";
2779   case ISD::VSELECT:     return "vselect";
2780   case ISD::INSERT_VECTOR_ELT:   return "insert_vector_elt";
2781   case ISD::VINSERT_VECTOR_ELT:  return "vinsert_vector_elt";
2782   case ISD::EXTRACT_VECTOR_ELT:  return "extract_vector_elt";
2783   case ISD::VEXTRACT_VECTOR_ELT: return "vextract_vector_elt";
2784   case ISD::SCALAR_TO_VECTOR:    return "scalar_to_vector";
2785   case ISD::VBUILD_VECTOR:       return "vbuild_vector";
2786   case ISD::VECTOR_SHUFFLE:      return "vector_shuffle";
2787   case ISD::VVECTOR_SHUFFLE:     return "vvector_shuffle";
2788   case ISD::VBIT_CONVERT:        return "vbit_convert";
2789   case ISD::ADDC:        return "addc";
2790   case ISD::ADDE:        return "adde";
2791   case ISD::SUBC:        return "subc";
2792   case ISD::SUBE:        return "sube";
2793   case ISD::SHL_PARTS:   return "shl_parts";
2794   case ISD::SRA_PARTS:   return "sra_parts";
2795   case ISD::SRL_PARTS:   return "srl_parts";
2796
2797   // Conversion operators.
2798   case ISD::SIGN_EXTEND: return "sign_extend";
2799   case ISD::ZERO_EXTEND: return "zero_extend";
2800   case ISD::ANY_EXTEND:  return "any_extend";
2801   case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
2802   case ISD::TRUNCATE:    return "truncate";
2803   case ISD::FP_ROUND:    return "fp_round";
2804   case ISD::FP_ROUND_INREG: return "fp_round_inreg";
2805   case ISD::FP_EXTEND:   return "fp_extend";
2806
2807   case ISD::SINT_TO_FP:  return "sint_to_fp";
2808   case ISD::UINT_TO_FP:  return "uint_to_fp";
2809   case ISD::FP_TO_SINT:  return "fp_to_sint";
2810   case ISD::FP_TO_UINT:  return "fp_to_uint";
2811   case ISD::BIT_CONVERT: return "bit_convert";
2812
2813     // Control flow instructions
2814   case ISD::BR:      return "br";
2815   case ISD::BRIND:   return "brind";
2816   case ISD::BRCOND:  return "brcond";
2817   case ISD::BR_CC:   return "br_cc";
2818   case ISD::RET:     return "ret";
2819   case ISD::CALLSEQ_START:  return "callseq_start";
2820   case ISD::CALLSEQ_END:    return "callseq_end";
2821
2822     // Other operators
2823   case ISD::LOAD:               return "load";
2824   case ISD::STORE:              return "store";
2825   case ISD::VLOAD:              return "vload";
2826   case ISD::EXTLOAD:            return "extload";
2827   case ISD::SEXTLOAD:           return "sextload";
2828   case ISD::ZEXTLOAD:           return "zextload";
2829   case ISD::TRUNCSTORE:         return "truncstore";
2830   case ISD::VAARG:              return "vaarg";
2831   case ISD::VACOPY:             return "vacopy";
2832   case ISD::VAEND:              return "vaend";
2833   case ISD::VASTART:            return "vastart";
2834   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
2835   case ISD::EXTRACT_ELEMENT:    return "extract_element";
2836   case ISD::BUILD_PAIR:         return "build_pair";
2837   case ISD::STACKSAVE:          return "stacksave";
2838   case ISD::STACKRESTORE:       return "stackrestore";
2839
2840   // Block memory operations.
2841   case ISD::MEMSET:  return "memset";
2842   case ISD::MEMCPY:  return "memcpy";
2843   case ISD::MEMMOVE: return "memmove";
2844
2845   // Bit manipulation
2846   case ISD::BSWAP:   return "bswap";
2847   case ISD::CTPOP:   return "ctpop";
2848   case ISD::CTTZ:    return "cttz";
2849   case ISD::CTLZ:    return "ctlz";
2850
2851   // Debug info
2852   case ISD::LOCATION: return "location";
2853   case ISD::DEBUG_LOC: return "debug_loc";
2854   case ISD::DEBUG_LABEL: return "debug_label";
2855
2856   case ISD::CONDCODE:
2857     switch (cast<CondCodeSDNode>(this)->get()) {
2858     default: assert(0 && "Unknown setcc condition!");
2859     case ISD::SETOEQ:  return "setoeq";
2860     case ISD::SETOGT:  return "setogt";
2861     case ISD::SETOGE:  return "setoge";
2862     case ISD::SETOLT:  return "setolt";
2863     case ISD::SETOLE:  return "setole";
2864     case ISD::SETONE:  return "setone";
2865
2866     case ISD::SETO:    return "seto";
2867     case ISD::SETUO:   return "setuo";
2868     case ISD::SETUEQ:  return "setue";
2869     case ISD::SETUGT:  return "setugt";
2870     case ISD::SETUGE:  return "setuge";
2871     case ISD::SETULT:  return "setult";
2872     case ISD::SETULE:  return "setule";
2873     case ISD::SETUNE:  return "setune";
2874
2875     case ISD::SETEQ:   return "seteq";
2876     case ISD::SETGT:   return "setgt";
2877     case ISD::SETGE:   return "setge";
2878     case ISD::SETLT:   return "setlt";
2879     case ISD::SETLE:   return "setle";
2880     case ISD::SETNE:   return "setne";
2881     }
2882   }
2883 }
2884
2885 void SDNode::dump() const { dump(0); }
2886 void SDNode::dump(const SelectionDAG *G) const {
2887   std::cerr << (void*)this << ": ";
2888
2889   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
2890     if (i) std::cerr << ",";
2891     if (getValueType(i) == MVT::Other)
2892       std::cerr << "ch";
2893     else
2894       std::cerr << MVT::getValueTypeString(getValueType(i));
2895   }
2896   std::cerr << " = " << getOperationName(G);
2897
2898   std::cerr << " ";
2899   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
2900     if (i) std::cerr << ", ";
2901     std::cerr << (void*)getOperand(i).Val;
2902     if (unsigned RN = getOperand(i).ResNo)
2903       std::cerr << ":" << RN;
2904   }
2905
2906   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
2907     std::cerr << "<" << CSDN->getValue() << ">";
2908   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
2909     std::cerr << "<" << CSDN->getValue() << ">";
2910   } else if (const GlobalAddressSDNode *GADN =
2911              dyn_cast<GlobalAddressSDNode>(this)) {
2912     int offset = GADN->getOffset();
2913     std::cerr << "<";
2914     WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
2915     if (offset > 0)
2916       std::cerr << " + " << offset;
2917     else
2918       std::cerr << " " << offset;
2919   } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
2920     std::cerr << "<" << FIDN->getIndex() << ">";
2921   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
2922     int offset = CP->getOffset();
2923     std::cerr << "<" << *CP->get() << ">";
2924     if (offset > 0)
2925       std::cerr << " + " << offset;
2926     else
2927       std::cerr << " " << offset;
2928   } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
2929     std::cerr << "<";
2930     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
2931     if (LBB)
2932       std::cerr << LBB->getName() << " ";
2933     std::cerr << (const void*)BBDN->getBasicBlock() << ">";
2934   } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
2935     if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) {
2936       std::cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg());
2937     } else {
2938       std::cerr << " #" << R->getReg();
2939     }
2940   } else if (const ExternalSymbolSDNode *ES =
2941              dyn_cast<ExternalSymbolSDNode>(this)) {
2942     std::cerr << "'" << ES->getSymbol() << "'";
2943   } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
2944     if (M->getValue())
2945       std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">";
2946     else
2947       std::cerr << "<null:" << M->getOffset() << ">";
2948   } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
2949     std::cerr << ":" << getValueTypeString(N->getVT());
2950   }
2951 }
2952
2953 static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) {
2954   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
2955     if (N->getOperand(i).Val->hasOneUse())
2956       DumpNodes(N->getOperand(i).Val, indent+2, G);
2957     else
2958       std::cerr << "\n" << std::string(indent+2, ' ')
2959                 << (void*)N->getOperand(i).Val << ": <multiple use>";
2960
2961
2962   std::cerr << "\n" << std::string(indent, ' ');
2963   N->dump(G);
2964 }
2965
2966 void SelectionDAG::dump() const {
2967   std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
2968   std::vector<const SDNode*> Nodes;
2969   for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end();
2970        I != E; ++I)
2971     Nodes.push_back(I);
2972
2973   std::sort(Nodes.begin(), Nodes.end());
2974
2975   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
2976     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
2977       DumpNodes(Nodes[i], 2, this);
2978   }
2979
2980   DumpNodes(getRoot().Val, 2, this);
2981
2982   std::cerr << "\n\n";
2983 }
2984
2985 /// InsertISelMapEntry - A helper function to insert a key / element pair
2986 /// into a SDOperand to SDOperand map. This is added to avoid the map
2987 /// insertion operator from being inlined.
2988 void SelectionDAG::InsertISelMapEntry(std::map<SDOperand, SDOperand> &Map,
2989                                       SDNode *Key, unsigned KeyResNo,
2990                                       SDNode *Element, unsigned ElementResNo) {
2991   Map.insert(std::make_pair(SDOperand(Key, KeyResNo),
2992                             SDOperand(Element, ElementResNo)));
2993 }