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