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/Assembly/Writer.h"
  18 #include "llvm/CodeGen/MachineBasicBlock.h"
  19 #include "llvm/Support/MathExtras.h"
  20 #include "llvm/Target/MRegisterInfo.h"
  21 #include "llvm/Target/TargetLowering.h"
  22 #include "llvm/Target/TargetInstrInfo.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include <iostream>
  25 #include <set>
  26 #include <cmath>
  27 #include <algorithm>
  28 using namespace llvm;
  29
  30 static bool isCommutativeBinOp(unsigned Opcode) {
  31   switch (Opcode) {
  32   case ISD::ADD:
  33   case ISD::MUL:
  34   case ISD::FADD:
  35   case ISD::FMUL:
  36   case ISD::AND:
  37   case ISD::OR:
  38   case ISD::XOR: return true;
  39   default: return false; // FIXME: Need commutative info for user ops!
  40   }
  41 }
  42
  43 static bool isAssociativeBinOp(unsigned Opcode) {
  44   switch (Opcode) {
  45   case ISD::ADD:
  46   case ISD::MUL:
  47   case ISD::AND:
  48   case ISD::OR:
  49   case ISD::XOR: return true;
  50   default: return false; // FIXME: Need associative info for user ops!
  51   }
  52 }
  53
  54 // isInvertibleForFree - Return true if there is no cost to emitting the logical
  55 // inverse of this node.
  56 static bool isInvertibleForFree(SDOperand N) {
  57   if (isa<ConstantSDNode>(N.Val)) return true;
  58   if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse())
  59     return true;
  60   return false;
  61 }
  62
  63 //===----------------------------------------------------------------------===//
  64 //                              ConstantFPSDNode Class
  65 //===----------------------------------------------------------------------===//
  66
  67 /// isExactlyValue - We don't rely on operator== working on double values, as
  68 /// it returns true for things that are clearly not equal, like -0.0 and 0.0.
  69 /// As such, this method can be used to do an exact bit-for-bit comparison of
  70 /// two floating point values.
  71 bool ConstantFPSDNode::isExactlyValue(double V) const {
  72   return DoubleToBits(V) == DoubleToBits(Value);
  73 }
  74
  75 //===----------------------------------------------------------------------===//
  76 //                              ISD Class
  77 //===----------------------------------------------------------------------===//
  78
  79 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
  80 /// when given the operation for (X op Y).
  81 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
  82   // To perform this operation, we just need to swap the L and G bits of the
  83   // operation.
  84   unsigned OldL = (Operation >> 2) & 1;
  85   unsigned OldG = (Operation >> 1) & 1;
  86   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
  87                        (OldL << 1) |       // New G bit
  88                        (OldG << 2));        // New L bit.
  89 }
  90
  91 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
  92 /// 'op' is a valid SetCC operation.
  93 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
  94   unsigned Operation = Op;
  95   if (isInteger)
  96     Operation ^= 7;   // Flip L, G, E bits, but not U.
  97   else
  98     Operation ^= 15;  // Flip all of the condition bits.
  99   if (Operation > ISD::SETTRUE2)
 100     Operation &= ~8;     // Don't let N and U bits get set.
 101   return ISD::CondCode(Operation);
 102 }
 103
 104
 105 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
 106 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
 107 /// if the operation does not depend on the sign of the input (setne and seteq).
 108 static int isSignedOp(ISD::CondCode Opcode) {
 109   switch (Opcode) {
 110   default: assert(0 && "Illegal integer setcc operation!");
 111   case ISD::SETEQ:
 112   case ISD::SETNE: return 0;
 113   case ISD::SETLT:
 114   case ISD::SETLE:
 115   case ISD::SETGT:
 116   case ISD::SETGE: return 1;
 117   case ISD::SETULT:
 118   case ISD::SETULE:
 119   case ISD::SETUGT:
 120   case ISD::SETUGE: return 2;
 121   }
 122 }
 123
 124 /// getSetCCOrOperation - Return the result of a logical OR between different
 125 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
 126 /// returns SETCC_INVALID if it is not possible to represent the resultant
 127 /// comparison.
 128 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 129                                        bool isInteger) {
 130   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 131     // Cannot fold a signed integer setcc with an unsigned integer setcc.
 132     return ISD::SETCC_INVALID;
 133
 134   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
 135
 136   // If the N and U bits get set then the resultant comparison DOES suddenly
 137   // care about orderedness, and is true when ordered.
 138   if (Op > ISD::SETTRUE2)
 139     Op &= ~16;     // Clear the N bit.
 140   return ISD::CondCode(Op);
 141 }
 142
 143 /// getSetCCAndOperation - Return the result of a logical AND between different
 144 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
 145 /// function returns zero if it is not possible to represent the resultant
 146 /// comparison.
 147 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 148                                         bool isInteger) {
 149   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 150     // Cannot fold a signed setcc with an unsigned setcc.
 151     return ISD::SETCC_INVALID;
 152
 153   // Combine all of the condition bits.
 154   return ISD::CondCode(Op1 & Op2);
 155 }
 156
 157 const TargetMachine &SelectionDAG::getTarget() const {
 158   return TLI.getTargetMachine();
 159 }
 160
 161 //===----------------------------------------------------------------------===//
 162 //                              SelectionDAG Class
 163 //===----------------------------------------------------------------------===//
 164
 165 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
 166 /// SelectionDAG, including nodes (like loads) that have uses of their token
 167 /// chain but no other uses and no side effect.  If a node is passed in as an
 168 /// argument, it is used as the seed for node deletion.
 169 void SelectionDAG::RemoveDeadNodes(SDNode *N) {
 170   // Create a dummy node (which is not added to allnodes), that adds a reference
 171   // to the root node, preventing it from being deleted.
 172   HandleSDNode Dummy(getRoot());
 173
 174   bool MadeChange = false;
 175
 176   // If we have a hint to start from, use it.
 177   if (N && N->use_empty()) {
 178     DestroyDeadNode(N);
 179     MadeChange = true;
 180   }
 181
 182   for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) {
 183     // Try to delete this node.
 184     SDNode *N = AllNodes[i];
 185     if (N->use_empty() && N->getOpcode() != 65535) {
 186       DestroyDeadNode(N);
 187       MadeChange = true;
 188     }
 189   }
 190
 191   // Walk the nodes list, removing the nodes we've marked as dead.
 192   if (MadeChange) {
 193     for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
 194       if (AllNodes[i]->use_empty()) {
 195         delete AllNodes[i];
 196         AllNodes[i] = AllNodes.back();
 197         AllNodes.pop_back();
 198         --i; --e;
 199       }
 200   }
 201
 202   // If the root changed (e.g. it was a dead load, update the root).
 203   setRoot(Dummy.getValue());
 204 }
 205
 206 /// DestroyDeadNode - We know that N is dead.  Nuke it from the CSE maps for the
 207 /// graph.  If it is the last user of any of its operands, recursively process
 208 /// them the same way.
 209 ///
 210 void SelectionDAG::DestroyDeadNode(SDNode *N) {
 211   // Okay, we really are going to delete this node.  First take this out of the
 212   // appropriate CSE map.
 213   RemoveNodeFromCSEMaps(N);
 214
 215   // Next, brutally remove the operand list.  This is safe to do, as there are
 216   // no cycles in the graph.
 217   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) {
 218     SDNode *O = I->Val;
 219     O->removeUser(N);
 220
 221     // Now that we removed this operand, see if there are no uses of it left.
 222     if (O->use_empty())
 223       DestroyDeadNode(O);
 224   }
 225   delete[] N->OperandList;
 226   N->OperandList = 0;
 227   N->NumOperands = 0;
 228
 229   // Mark the node as dead.
 230   N->MorphNodeTo(65535);
 231 }
 232
 233 void SelectionDAG::DeleteNode(SDNode *N) {
 234   assert(N->use_empty() && "Cannot delete a node that is not dead!");
 235
 236   // First take this out of the appropriate CSE map.
 237   RemoveNodeFromCSEMaps(N);
 238
 239   // Finally, remove uses due to operands of this node, remove from the
 240   // AllNodes list, and delete the node.
 241   DeleteNodeNotInCSEMaps(N);
 242 }
 243
 244 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) {
 245
 246   // Remove it from the AllNodes list.
 247   for (std::vector<SDNode*>::iterator I = AllNodes.begin(); ; ++I) {
 248     assert(I != AllNodes.end() && "Node not in AllNodes list??");
 249     if (*I == N) {
 250       // Erase from the vector, which is not ordered.
 251       std::swap(*I, AllNodes.back());
 252       AllNodes.pop_back();
 253       break;
 254     }
 255   }
 256
 257   // Drop all of the operands and decrement used nodes use counts.
 258   for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I)
 259     I->Val->removeUser(N);
 260   delete[] N->OperandList;
 261   N->OperandList = 0;
 262   N->NumOperands = 0;
 263
 264   delete N;
 265 }
 266
 267 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that
 268 /// correspond to it.  This is useful when we're about to delete or repurpose
 269 /// the node.  We don't want future request for structurally identical nodes
 270 /// to return N anymore.
 271 void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) {
 272   bool Erased = false;
 273   switch (N->getOpcode()) {
 274   case ISD::HANDLENODE: return;  // noop.
 275   case ISD::Constant:
 276     Erased = Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(),
 277                                             N->getValueType(0)));
 278     break;
 279   case ISD::TargetConstant:
 280     Erased = TargetConstants.erase(std::make_pair(
 281                                     cast<ConstantSDNode>(N)->getValue(),
 282                                                   N->getValueType(0)));
 283     break;
 284   case ISD::ConstantFP: {
 285     uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue());
 286     Erased = ConstantFPs.erase(std::make_pair(V, N->getValueType(0)));
 287     break;
 288   }
 289   case ISD::CONDCODE:
 290     assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] &&
 291            "Cond code doesn't exist!");
 292     Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0;
 293     CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0;
 294     break;
 295   case ISD::GlobalAddress:
 296     Erased = GlobalValues.erase(cast<GlobalAddressSDNode>(N)->getGlobal());
 297     break;
 298   case ISD::TargetGlobalAddress:
 299     Erased =TargetGlobalValues.erase(cast<GlobalAddressSDNode>(N)->getGlobal());
 300     break;
 301   case ISD::FrameIndex:
 302     Erased = FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
 303     break;
 304   case ISD::TargetFrameIndex:
 305     Erased = TargetFrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
 306     break;
 307   case ISD::ConstantPool:
 308     Erased = ConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->get());
 309     break;
 310   case ISD::TargetConstantPool:
 311     Erased =TargetConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->get());
 312     break;
 313   case ISD::BasicBlock:
 314     Erased = BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock());
 315     break;
 316   case ISD::ExternalSymbol:
 317     Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 318     break;
 319   case ISD::TargetExternalSymbol:
 320     Erased = TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 321     break;
 322   case ISD::VALUETYPE:
 323     Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0;
 324     ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0;
 325     break;
 326   case ISD::Register:
 327     Erased = RegNodes.erase(std::make_pair(cast<RegisterSDNode>(N)->getReg(),
 328                                            N->getValueType(0)));
 329     break;
 330   case ISD::SRCVALUE: {
 331     SrcValueSDNode *SVN = cast<SrcValueSDNode>(N);
 332     Erased =ValueNodes.erase(std::make_pair(SVN->getValue(), SVN->getOffset()));
 333     break;
 334   }
 335   case ISD::LOAD:
 336     Erased = Loads.erase(std::make_pair(N->getOperand(1),
 337                                         std::make_pair(N->getOperand(0),
 338                                                        N->getValueType(0))));
 339     break;
 340   default:
 341     if (N->getNumValues() == 1) {
 342       if (N->getNumOperands() == 0) {
 343         Erased = NullaryOps.erase(std::make_pair(N->getOpcode(),
 344                                                  N->getValueType(0)));
 345       } else if (N->getNumOperands() == 1) {
 346         Erased =
 347           UnaryOps.erase(std::make_pair(N->getOpcode(),
 348                                         std::make_pair(N->getOperand(0),
 349                                                        N->getValueType(0))));
 350       } else if (N->getNumOperands() == 2) {
 351         Erased =
 352           BinaryOps.erase(std::make_pair(N->getOpcode(),
 353                                          std::make_pair(N->getOperand(0),
 354                                                         N->getOperand(1))));
 355       } else {
 356         std::vector<SDOperand> Ops(N->op_begin(), N->op_end());
 357         Erased =
 358           OneResultNodes.erase(std::make_pair(N->getOpcode(),
 359                                               std::make_pair(N->getValueType(0),
 360                                                              Ops)));
 361       }
 362     } else {
 363       // Remove the node from the ArbitraryNodes map.
 364       std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end());
 365       std::vector<SDOperand>     Ops(N->op_begin(), N->op_end());
 366       Erased =
 367         ArbitraryNodes.erase(std::make_pair(N->getOpcode(),
 368                                             std::make_pair(RV, Ops)));
 369     }
 370     break;
 371   }
 372 #ifndef NDEBUG
 373   // Verify that the node was actually in one of the CSE maps, unless it has a
 374   // flag result (which cannot be CSE'd) or is one of the special cases that are
 375   // not subject to CSE.
 376   if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag &&
 377       N->getOpcode() != ISD::CALL && N->getOpcode() != ISD::CALLSEQ_START &&
 378       N->getOpcode() != ISD::CALLSEQ_END && !N->isTargetOpcode()) {
 379
 380     N->dump();
 381     assert(0 && "Node is not in map!");
 382   }
 383 #endif
 384 }
 385
 386 /// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps.  It
 387 /// has been taken out and modified in some way.  If the specified node already
 388 /// exists in the CSE maps, do not modify the maps, but return the existing node
 389 /// instead.  If it doesn't exist, add it and return null.
 390 ///
 391 SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) {
 392   assert(N->getNumOperands() && "This is a leaf node!");
 393   if (N->getOpcode() == ISD::LOAD) {
 394     SDNode *&L = Loads[std::make_pair(N->getOperand(1),
 395                                       std::make_pair(N->getOperand(0),
 396                                                      N->getValueType(0)))];
 397     if (L) return L;
 398     L = N;
 399   } else if (N->getOpcode() == ISD::HANDLENODE) {
 400     return 0;  // never add it.
 401   } else if (N->getNumOperands() == 1) {
 402     SDNode *&U = UnaryOps[std::make_pair(N->getOpcode(),
 403                                          std::make_pair(N->getOperand(0),
 404                                                         N->getValueType(0)))];
 405     if (U) return U;
 406     U = N;
 407   } else if (N->getNumOperands() == 2) {
 408     SDNode *&B = BinaryOps[std::make_pair(N->getOpcode(),
 409                                           std::make_pair(N->getOperand(0),
 410                                                          N->getOperand(1)))];
 411     if (B) return B;
 412     B = N;
 413   } else if (N->getNumValues() == 1) {
 414     std::vector<SDOperand> Ops(N->op_begin(), N->op_end());
 415     SDNode *&ORN = OneResultNodes[std::make_pair(N->getOpcode(),
 416                                   std::make_pair(N->getValueType(0), Ops))];
 417     if (ORN) return ORN;
 418     ORN = N;
 419   } else {
 420     // Remove the node from the ArbitraryNodes map.
 421     std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end());
 422     std::vector<SDOperand>     Ops(N->op_begin(), N->op_end());
 423     SDNode *&AN = ArbitraryNodes[std::make_pair(N->getOpcode(),
 424                                                 std::make_pair(RV, Ops))];
 425     if (AN) return AN;
 426     AN = N;
 427   }
 428   return 0;
 429 }
 430
 431
 432
 433 SelectionDAG::~SelectionDAG() {
 434   for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) {
 435     SDNode *N = AllNodes[i];
 436     delete [] N->OperandList;
 437     N->OperandList = 0;
 438     N->NumOperands = 0;
 439     delete N;
 440   }
 441 }
 442
 443 SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) {
 444   if (Op.getValueType() == VT) return Op;
 445   int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT));
 446   return getNode(ISD::AND, Op.getValueType(), Op,
 447                  getConstant(Imm, Op.getValueType()));
 448 }
 449
 450 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) {
 451   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 452   // Mask out any bits that are not valid for this constant.
 453   if (VT != MVT::i64)
 454     Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
 455
 456   SDNode *&N = Constants[std::make_pair(Val, VT)];
 457   if (N) return SDOperand(N, 0);
 458   N = new ConstantSDNode(false, Val, VT);
 459   AllNodes.push_back(N);
 460   return SDOperand(N, 0);
 461 }
 462
 463 SDOperand SelectionDAG::getTargetConstant(uint64_t Val, MVT::ValueType VT) {
 464   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 465   // Mask out any bits that are not valid for this constant.
 466   if (VT != MVT::i64)
 467     Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
 468
 469   SDNode *&N = TargetConstants[std::make_pair(Val, VT)];
 470   if (N) return SDOperand(N, 0);
 471   N = new ConstantSDNode(true, Val, VT);
 472   AllNodes.push_back(N);
 473   return SDOperand(N, 0);
 474 }
 475
 476 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
 477   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
 478   if (VT == MVT::f32)
 479     Val = (float)Val;  // Mask out extra precision.
 480
 481   // Do the map lookup using the actual bit pattern for the floating point
 482   // value, so that we don't have problems with 0.0 comparing equal to -0.0, and
 483   // we don't have issues with SNANs.
 484   SDNode *&N = ConstantFPs[std::make_pair(DoubleToBits(Val), VT)];
 485   if (N) return SDOperand(N, 0);
 486   N = new ConstantFPSDNode(Val, VT);
 487   AllNodes.push_back(N);
 488   return SDOperand(N, 0);
 489 }
 490
 491
 492
 493 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 494                                          MVT::ValueType VT) {
 495   SDNode *&N = GlobalValues[GV];
 496   if (N) return SDOperand(N, 0);
 497   N = new GlobalAddressSDNode(false, GV, VT);
 498   AllNodes.push_back(N);
 499   return SDOperand(N, 0);
 500 }
 501
 502 SDOperand SelectionDAG::getTargetGlobalAddress(const GlobalValue *GV,
 503                                                MVT::ValueType VT) {
 504   SDNode *&N = TargetGlobalValues[GV];
 505   if (N) return SDOperand(N, 0);
 506   N = new GlobalAddressSDNode(true, GV, VT);
 507   AllNodes.push_back(N);
 508   return SDOperand(N, 0);
 509 }
 510
 511 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) {
 512   SDNode *&N = FrameIndices[FI];
 513   if (N) return SDOperand(N, 0);
 514   N = new FrameIndexSDNode(FI, VT, false);
 515   AllNodes.push_back(N);
 516   return SDOperand(N, 0);
 517 }
 518
 519 SDOperand SelectionDAG::getTargetFrameIndex(int FI, MVT::ValueType VT) {
 520   SDNode *&N = TargetFrameIndices[FI];
 521   if (N) return SDOperand(N, 0);
 522   N = new FrameIndexSDNode(FI, VT, true);
 523   AllNodes.push_back(N);
 524   return SDOperand(N, 0);
 525 }
 526
 527 SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT) {
 528   SDNode *&N = ConstantPoolIndices[C];
 529   if (N) return SDOperand(N, 0);
 530   N = new ConstantPoolSDNode(C, VT, false);
 531   AllNodes.push_back(N);
 532   return SDOperand(N, 0);
 533 }
 534
 535 SDOperand SelectionDAG::getTargetConstantPool(Constant *C, MVT::ValueType VT) {
 536   SDNode *&N = TargetConstantPoolIndices[C];
 537   if (N) return SDOperand(N, 0);
 538   N = new ConstantPoolSDNode(C, VT, true);
 539   AllNodes.push_back(N);
 540   return SDOperand(N, 0);
 541 }
 542
 543 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
 544   SDNode *&N = BBNodes[MBB];
 545   if (N) return SDOperand(N, 0);
 546   N = new BasicBlockSDNode(MBB);
 547   AllNodes.push_back(N);
 548   return SDOperand(N, 0);
 549 }
 550
 551 SDOperand SelectionDAG::getValueType(MVT::ValueType VT) {
 552   if ((unsigned)VT >= ValueTypeNodes.size())
 553     ValueTypeNodes.resize(VT+1);
 554   if (ValueTypeNodes[VT] == 0) {
 555     ValueTypeNodes[VT] = new VTSDNode(VT);
 556     AllNodes.push_back(ValueTypeNodes[VT]);
 557   }
 558
 559   return SDOperand(ValueTypeNodes[VT], 0);
 560 }
 561
 562 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
 563   SDNode *&N = ExternalSymbols[Sym];
 564   if (N) return SDOperand(N, 0);
 565   N = new ExternalSymbolSDNode(false, Sym, VT);
 566   AllNodes.push_back(N);
 567   return SDOperand(N, 0);
 568 }
 569
 570 SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym, MVT::ValueType VT) {
 571   SDNode *&N = TargetExternalSymbols[Sym];
 572   if (N) return SDOperand(N, 0);
 573   N = new ExternalSymbolSDNode(true, Sym, VT);
 574   AllNodes.push_back(N);
 575   return SDOperand(N, 0);
 576 }
 577
 578 SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) {
 579   if ((unsigned)Cond >= CondCodeNodes.size())
 580     CondCodeNodes.resize(Cond+1);
 581
 582   if (CondCodeNodes[Cond] == 0) {
 583     CondCodeNodes[Cond] = new CondCodeSDNode(Cond);
 584     AllNodes.push_back(CondCodeNodes[Cond]);
 585   }
 586   return SDOperand(CondCodeNodes[Cond], 0);
 587 }
 588
 589 SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) {
 590   RegisterSDNode *&Reg = RegNodes[std::make_pair(RegNo, VT)];
 591   if (!Reg) {
 592     Reg = new RegisterSDNode(RegNo, VT);
 593     AllNodes.push_back(Reg);
 594   }
 595   return SDOperand(Reg, 0);
 596 }
 597
 598 SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1,
 599                                       SDOperand N2, ISD::CondCode Cond) {
 600   // These setcc operations always fold.
 601   switch (Cond) {
 602   default: break;
 603   case ISD::SETFALSE:
 604   case ISD::SETFALSE2: return getConstant(0, VT);
 605   case ISD::SETTRUE:
 606   case ISD::SETTRUE2:  return getConstant(1, VT);
 607   }
 608
 609   if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
 610     uint64_t C2 = N2C->getValue();
 611     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) {
 612       uint64_t C1 = N1C->getValue();
 613
 614       // Sign extend the operands if required
 615       if (ISD::isSignedIntSetCC(Cond)) {
 616         C1 = N1C->getSignExtended();
 617         C2 = N2C->getSignExtended();
 618       }
 619
 620       switch (Cond) {
 621       default: assert(0 && "Unknown integer setcc!");
 622       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
 623       case ISD::SETNE:  return getConstant(C1 != C2, VT);
 624       case ISD::SETULT: return getConstant(C1 <  C2, VT);
 625       case ISD::SETUGT: return getConstant(C1 >  C2, VT);
 626       case ISD::SETULE: return getConstant(C1 <= C2, VT);
 627       case ISD::SETUGE: return getConstant(C1 >= C2, VT);
 628       case ISD::SETLT:  return getConstant((int64_t)C1 <  (int64_t)C2, VT);
 629       case ISD::SETGT:  return getConstant((int64_t)C1 >  (int64_t)C2, VT);
 630       case ISD::SETLE:  return getConstant((int64_t)C1 <= (int64_t)C2, VT);
 631       case ISD::SETGE:  return getConstant((int64_t)C1 >= (int64_t)C2, VT);
 632       }
 633     } else {
 634       // If the LHS is a ZERO_EXTEND, perform the comparison on the input.
 635       if (N1.getOpcode() == ISD::ZERO_EXTEND) {
 636         unsigned InSize = MVT::getSizeInBits(N1.getOperand(0).getValueType());
 637
 638         // If the comparison constant has bits in the upper part, the
 639         // zero-extended value could never match.
 640         if (C2 & (~0ULL << InSize)) {
 641           unsigned VSize = MVT::getSizeInBits(N1.getValueType());
 642           switch (Cond) {
 643           case ISD::SETUGT:
 644           case ISD::SETUGE:
 645           case ISD::SETEQ: return getConstant(0, VT);
 646           case ISD::SETULT:
 647           case ISD::SETULE:
 648           case ISD::SETNE: return getConstant(1, VT);
 649           case ISD::SETGT:
 650           case ISD::SETGE:
 651             // True if the sign bit of C2 is set.
 652             return getConstant((C2 & (1ULL << VSize)) != 0, VT);
 653           case ISD::SETLT:
 654           case ISD::SETLE:
 655             // True if the sign bit of C2 isn't set.
 656             return getConstant((C2 & (1ULL << VSize)) == 0, VT);
 657           default:
 658             break;
 659           }
 660         }
 661
 662         // Otherwise, we can perform the comparison with the low bits.
 663         switch (Cond) {
 664         case ISD::SETEQ:
 665         case ISD::SETNE:
 666         case ISD::SETUGT:
 667         case ISD::SETUGE:
 668         case ISD::SETULT:
 669         case ISD::SETULE:
 670           return getSetCC(VT, N1.getOperand(0),
 671                           getConstant(C2, N1.getOperand(0).getValueType()),
 672                           Cond);
 673         default:
 674           break;   // todo, be more careful with signed comparisons
 675         }
 676       } else if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG &&
 677                  (Cond == ISD::SETEQ || Cond == ISD::SETNE)) {
 678         MVT::ValueType ExtSrcTy = cast<VTSDNode>(N1.getOperand(1))->getVT();
 679         unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy);
 680         MVT::ValueType ExtDstTy = N1.getValueType();
 681         unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy);
 682
 683         // If the extended part has any inconsistent bits, it cannot ever
 684         // compare equal.  In other words, they have to be all ones or all
 685         // zeros.
 686         uint64_t ExtBits =
 687           (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1));
 688         if ((C2 & ExtBits) != 0 && (C2 & ExtBits) != ExtBits)
 689           return getConstant(Cond == ISD::SETNE, VT);
 690
 691         // Otherwise, make this a use of a zext.
 692         return getSetCC(VT, getZeroExtendInReg(N1.getOperand(0), ExtSrcTy),
 693                         getConstant(C2 & (~0ULL>>(64-ExtSrcTyBits)), ExtDstTy),
 694                         Cond);
 695       }
 696
 697       uint64_t MinVal, MaxVal;
 698       unsigned OperandBitSize = MVT::getSizeInBits(N2C->getValueType(0));
 699       if (ISD::isSignedIntSetCC(Cond)) {
 700         MinVal = 1ULL << (OperandBitSize-1);
 701         if (OperandBitSize != 1)   // Avoid X >> 64, which is undefined.
 702           MaxVal = ~0ULL >> (65-OperandBitSize);
 703         else
 704           MaxVal = 0;
 705       } else {
 706         MinVal = 0;
 707         MaxVal = ~0ULL >> (64-OperandBitSize);
 708       }
 709
 710       // Canonicalize GE/LE comparisons to use GT/LT comparisons.
 711       if (Cond == ISD::SETGE || Cond == ISD::SETUGE) {
 712         if (C2 == MinVal) return getConstant(1, VT);   // X >= MIN --> true
 713         --C2;                                          // X >= C1 --> X > (C1-1)
 714         return getSetCC(VT, N1, getConstant(C2, N2.getValueType()),
 715                         (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT);
 716       }
 717
 718       if (Cond == ISD::SETLE || Cond == ISD::SETULE) {
 719         if (C2 == MaxVal) return getConstant(1, VT);   // X <= MAX --> true
 720         ++C2;                                          // X <= C1 --> X < (C1+1)
 721         return getSetCC(VT, N1, getConstant(C2, N2.getValueType()),
 722                         (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT);
 723       }
 724
 725       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal)
 726         return getConstant(0, VT);      // X < MIN --> false
 727
 728       // Canonicalize setgt X, Min --> setne X, Min
 729       if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MinVal)
 730         return getSetCC(VT, N1, N2, ISD::SETNE);
 731
 732       // If we have setult X, 1, turn it into seteq X, 0
 733       if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal+1)
 734         return getSetCC(VT, N1, getConstant(MinVal, N1.getValueType()),
 735                         ISD::SETEQ);
 736       // If we have setugt X, Max-1, turn it into seteq X, Max
 737       else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MaxVal-1)
 738         return getSetCC(VT, N1, getConstant(MaxVal, N1.getValueType()),
 739                         ISD::SETEQ);
 740
 741       // If we have "setcc X, C1", check to see if we can shrink the immediate
 742       // by changing cc.
 743
 744       // SETUGT X, SINTMAX  -> SETLT X, 0
 745       if (Cond == ISD::SETUGT && OperandBitSize != 1 &&
 746           C2 == (~0ULL >> (65-OperandBitSize)))
 747         return getSetCC(VT, N1, getConstant(0, N2.getValueType()), ISD::SETLT);
 748
 749       // FIXME: Implement the rest of these.
 750
 751
 752       // Fold bit comparisons when we can.
 753       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
 754           VT == N1.getValueType() && N1.getOpcode() == ISD::AND)
 755         if (ConstantSDNode *AndRHS =
 756                     dyn_cast<ConstantSDNode>(N1.getOperand(1))) {
 757           if (Cond == ISD::SETNE && C2 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
 758             // Perform the xform if the AND RHS is a single bit.
 759             if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) {
 760               return getNode(ISD::SRL, VT, N1,
 761                              getConstant(Log2_64(AndRHS->getValue()),
 762                                                    TLI.getShiftAmountTy()));
 763             }
 764           } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) {
 765             // (X & 8) == 8  -->  (X & 8) >> 3
 766             // Perform the xform if C2 is a single bit.
 767             if ((C2 & (C2-1)) == 0) {
 768               return getNode(ISD::SRL, VT, N1,
 769                              getConstant(Log2_64(C2),TLI.getShiftAmountTy()));
 770             }
 771           }
 772         }
 773     }
 774   } else if (isa<ConstantSDNode>(N1.Val)) {
 775       // Ensure that the constant occurs on the RHS.
 776     return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
 777   }
 778
 779   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
 780     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
 781       double C1 = N1C->getValue(), C2 = N2C->getValue();
 782
 783       switch (Cond) {
 784       default: break; // FIXME: Implement the rest of these!
 785       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
 786       case ISD::SETNE:  return getConstant(C1 != C2, VT);
 787       case ISD::SETLT:  return getConstant(C1 < C2, VT);
 788       case ISD::SETGT:  return getConstant(C1 > C2, VT);
 789       case ISD::SETLE:  return getConstant(C1 <= C2, VT);
 790       case ISD::SETGE:  return getConstant(C1 >= C2, VT);
 791       }
 792     } else {
 793       // Ensure that the constant occurs on the RHS.
 794       return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond));
 795     }
 796
 797   // Could not fold it.
 798   return SDOperand();
 799 }
 800
 801 /// getNode - Gets or creates the specified node.
 802 ///
 803 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
 804   SDNode *&N = NullaryOps[std::make_pair(Opcode, VT)];
 805   if (!N) {
 806     N = new SDNode(Opcode, VT);
 807     AllNodes.push_back(N);
 808   }
 809   return SDOperand(N, 0);
 810 }
 811
 812 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 813                                 SDOperand Operand) {
 814   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
 815     uint64_t Val = C->getValue();
 816     switch (Opcode) {
 817     default: break;
 818     case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
 819     case ISD::ANY_EXTEND:
 820     case ISD::ZERO_EXTEND: return getConstant(Val, VT);
 821     case ISD::TRUNCATE:    return getConstant(Val, VT);
 822     case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
 823     case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
 824     }
 825   }
 826
 827   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
 828     switch (Opcode) {
 829     case ISD::FNEG:
 830       return getConstantFP(-C->getValue(), VT);
 831     case ISD::FP_ROUND:
 832     case ISD::FP_EXTEND:
 833       return getConstantFP(C->getValue(), VT);
 834     case ISD::FP_TO_SINT:
 835       return getConstant((int64_t)C->getValue(), VT);
 836     case ISD::FP_TO_UINT:
 837       return getConstant((uint64_t)C->getValue(), VT);
 838     }
 839
 840   unsigned OpOpcode = Operand.Val->getOpcode();
 841   switch (Opcode) {
 842   case ISD::TokenFactor:
 843     return Operand;         // Factor of one node?  No factor.
 844   case ISD::SIGN_EXTEND:
 845     if (Operand.getValueType() == VT) return Operand;   // noop extension
 846     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
 847       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 848     break;
 849   case ISD::ZERO_EXTEND:
 850     if (Operand.getValueType() == VT) return Operand;   // noop extension
 851     if (OpOpcode == ISD::ZERO_EXTEND)   // (zext (zext x)) -> (zext x)
 852       return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
 853     break;
 854   case ISD::ANY_EXTEND:
 855     if (Operand.getValueType() == VT) return Operand;   // noop extension
 856     if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND)
 857       // (ext (zext x)) -> (zext x)  and  (ext (sext x)) -> (sext x)
 858       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 859     break;
 860   case ISD::TRUNCATE:
 861     if (Operand.getValueType() == VT) return Operand;   // noop truncate
 862     if (OpOpcode == ISD::TRUNCATE)
 863       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
 864     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND ||
 865              OpOpcode == ISD::ANY_EXTEND) {
 866       // If the source is smaller than the dest, we still need an extend.
 867       if (Operand.Val->getOperand(0).getValueType() < VT)
 868         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 869       else if (Operand.Val->getOperand(0).getValueType() > VT)
 870         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
 871       else
 872         return Operand.Val->getOperand(0);
 873     }
 874     break;
 875   case ISD::FNEG:
 876     if (OpOpcode == ISD::FSUB)   // -(X-Y) -> (Y-X)
 877       return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1),
 878                      Operand.Val->getOperand(0));
 879     if (OpOpcode == ISD::FNEG)  // --X -> X
 880       return Operand.Val->getOperand(0);
 881     break;
 882   case ISD::FABS:
 883     if (OpOpcode == ISD::FNEG)  // abs(-X) -> abs(X)
 884       return getNode(ISD::FABS, VT, Operand.Val->getOperand(0));
 885     break;
 886   }
 887
 888   SDNode *N;
 889   if (VT != MVT::Flag) { // Don't CSE flag producing nodes
 890     SDNode *&E = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
 891     if (E) return SDOperand(E, 0);
 892     E = N = new SDNode(Opcode, Operand);
 893   } else {
 894     N = new SDNode(Opcode, Operand);
 895   }
 896   N->setValueTypes(VT);
 897   AllNodes.push_back(N);
 898   return SDOperand(N, 0);
 899 }
 900
 901
 902
 903 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 904                                 SDOperand N1, SDOperand N2) {
 905 #ifndef NDEBUG
 906   switch (Opcode) {
 907   case ISD::TokenFactor:
 908     assert(VT == MVT::Other && N1.getValueType() == MVT::Other &&
 909            N2.getValueType() == MVT::Other && "Invalid token factor!");
 910     break;
 911   case ISD::AND:
 912   case ISD::OR:
 913   case ISD::XOR:
 914   case ISD::UDIV:
 915   case ISD::UREM:
 916   case ISD::MULHU:
 917   case ISD::MULHS:
 918     assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
 919     // fall through
 920   case ISD::ADD:
 921   case ISD::SUB:
 922   case ISD::MUL:
 923   case ISD::SDIV:
 924   case ISD::SREM:
 925     assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops");
 926     // fall through.
 927   case ISD::FADD:
 928   case ISD::FSUB:
 929   case ISD::FMUL:
 930   case ISD::FDIV:
 931   case ISD::FREM:
 932     assert(N1.getValueType() == N2.getValueType() &&
 933            N1.getValueType() == VT && "Binary operator types must match!");
 934     break;
 935
 936   case ISD::SHL:
 937   case ISD::SRA:
 938   case ISD::SRL:
 939     assert(VT == N1.getValueType() &&
 940            "Shift operators return type must be the same as their first arg");
 941     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
 942            VT != MVT::i1 && "Shifts only work on integers");
 943     break;
 944   case ISD::FP_ROUND_INREG: {
 945     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
 946     assert(VT == N1.getValueType() && "Not an inreg round!");
 947     assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
 948            "Cannot FP_ROUND_INREG integer types");
 949     assert(EVT <= VT && "Not rounding down!");
 950     break;
 951   }
 952   case ISD::AssertSext:
 953   case ISD::AssertZext:
 954   case ISD::SIGN_EXTEND_INREG: {
 955     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
 956     assert(VT == N1.getValueType() && "Not an inreg extend!");
 957     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
 958            "Cannot *_EXTEND_INREG FP types");
 959     assert(EVT <= VT && "Not extending!");
 960   }
 961
 962   default: break;
 963   }
 964 #endif
 965
 966   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 967   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
 968   if (N1C) {
 969     if (N2C) {
 970       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
 971       switch (Opcode) {
 972       case ISD::ADD: return getConstant(C1 + C2, VT);
 973       case ISD::SUB: return getConstant(C1 - C2, VT);
 974       case ISD::MUL: return getConstant(C1 * C2, VT);
 975       case ISD::UDIV:
 976         if (C2) return getConstant(C1 / C2, VT);
 977         break;
 978       case ISD::UREM :
 979         if (C2) return getConstant(C1 % C2, VT);
 980         break;
 981       case ISD::SDIV :
 982         if (C2) return getConstant(N1C->getSignExtended() /
 983                                    N2C->getSignExtended(), VT);
 984         break;
 985       case ISD::SREM :
 986         if (C2) return getConstant(N1C->getSignExtended() %
 987                                    N2C->getSignExtended(), VT);
 988         break;
 989       case ISD::AND  : return getConstant(C1 & C2, VT);
 990       case ISD::OR   : return getConstant(C1 | C2, VT);
 991       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
 992       case ISD::SHL  : return getConstant(C1 << C2, VT);
 993       case ISD::SRL  : return getConstant(C1 >> C2, VT);
 994       case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
 995       default: break;
 996       }
 997     } else {      // Cannonicalize constant to RHS if commutative
 998       if (isCommutativeBinOp(Opcode)) {
 999         std::swap(N1C, N2C);
1000         std::swap(N1, N2);
1001       }
1002     }
1003   }
1004
1005   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
1006   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
1007   if (N1CFP) {
1008     if (N2CFP) {
1009       double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
1010       switch (Opcode) {
1011       case ISD::FADD: return getConstantFP(C1 + C2, VT);
1012       case ISD::FSUB: return getConstantFP(C1 - C2, VT);
1013       case ISD::FMUL: return getConstantFP(C1 * C2, VT);
1014       case ISD::FDIV:
1015         if (C2) return getConstantFP(C1 / C2, VT);
1016         break;
1017       case ISD::FREM :
1018         if (C2) return getConstantFP(fmod(C1, C2), VT);
1019         break;
1020       default: break;
1021       }
1022     } else {      // Cannonicalize constant to RHS if commutative
1023       if (isCommutativeBinOp(Opcode)) {
1024         std::swap(N1CFP, N2CFP);
1025         std::swap(N1, N2);
1026       }
1027     }
1028   }
1029
1030   // Finally, fold operations that do not require constants.
1031   switch (Opcode) {
1032   case ISD::FP_ROUND_INREG:
1033     if (cast<VTSDNode>(N2)->getVT() == VT) return N1;  // Not actually rounding.
1034     break;
1035   case ISD::SIGN_EXTEND_INREG: {
1036     MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT();
1037     if (EVT == VT) return N1;  // Not actually extending
1038     break;
1039   }
1040
1041   // FIXME: figure out how to safely handle things like
1042   // int foo(int x) { return 1 << (x & 255); }
1043   // int bar() { return foo(256); }
1044 #if 0
1045   case ISD::SHL:
1046   case ISD::SRL:
1047   case ISD::SRA:
1048     if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1049         cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1)
1050       return getNode(Opcode, VT, N1, N2.getOperand(0));
1051     else if (N2.getOpcode() == ISD::AND)
1052       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) {
1053         // If the and is only masking out bits that cannot effect the shift,
1054         // eliminate the and.
1055         unsigned NumBits = MVT::getSizeInBits(VT);
1056         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1057           return getNode(Opcode, VT, N1, N2.getOperand(0));
1058       }
1059     break;
1060 #endif
1061   }
1062
1063   // Memoize this node if possible.
1064   SDNode *N;
1065   if (Opcode != ISD::CALLSEQ_START && Opcode != ISD::CALLSEQ_END &&
1066       VT != MVT::Flag) {
1067     SDNode *&BON = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
1068     if (BON) return SDOperand(BON, 0);
1069
1070     BON = N = new SDNode(Opcode, N1, N2);
1071   } else {
1072     N = new SDNode(Opcode, N1, N2);
1073   }
1074
1075   N->setValueTypes(VT);
1076   AllNodes.push_back(N);
1077   return SDOperand(N, 0);
1078 }
1079
1080 // setAdjCallChain - This method changes the token chain of an
1081 // CALLSEQ_START/END node to be the specified operand.
1082 void SDNode::setAdjCallChain(SDOperand N) {
1083   assert(N.getValueType() == MVT::Other);
1084   assert((getOpcode() == ISD::CALLSEQ_START ||
1085           getOpcode() == ISD::CALLSEQ_END) && "Cannot adjust this node!");
1086
1087   OperandList[0].Val->removeUser(this);
1088   OperandList[0] = N;
1089   OperandList[0].Val->Uses.push_back(this);
1090 }
1091
1092
1093
1094 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
1095                                 SDOperand Chain, SDOperand Ptr,
1096                                 SDOperand SV) {
1097   SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
1098   if (N) return SDOperand(N, 0);
1099   N = new SDNode(ISD::LOAD, Chain, Ptr, SV);
1100
1101   // Loads have a token chain.
1102   setNodeValueTypes(N, VT, MVT::Other);
1103   AllNodes.push_back(N);
1104   return SDOperand(N, 0);
1105 }
1106
1107
1108 SDOperand SelectionDAG::getExtLoad(unsigned Opcode, MVT::ValueType VT,
1109                                    SDOperand Chain, SDOperand Ptr, SDOperand SV,
1110                                    MVT::ValueType EVT) {
1111   std::vector<SDOperand> Ops;
1112   Ops.reserve(4);
1113   Ops.push_back(Chain);
1114   Ops.push_back(Ptr);
1115   Ops.push_back(SV);
1116   Ops.push_back(getValueType(EVT));
1117   std::vector<MVT::ValueType> VTs;
1118   VTs.reserve(2);
1119   VTs.push_back(VT); VTs.push_back(MVT::Other);  // Add token chain.
1120   return getNode(Opcode, VTs, Ops);
1121 }
1122
1123 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1124                                 SDOperand N1, SDOperand N2, SDOperand N3) {
1125   // Perform various simplifications.
1126   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
1127   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
1128   ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
1129   switch (Opcode) {
1130   case ISD::SETCC: {
1131     // Use SimplifySetCC  to simplify SETCC's.
1132     SDOperand Simp = SimplifySetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get());
1133     if (Simp.Val) return Simp;
1134     break;
1135   }
1136   case ISD::SELECT:
1137     if (N1C)
1138       if (N1C->getValue())
1139         return N2;             // select true, X, Y -> X
1140       else
1141         return N3;             // select false, X, Y -> Y
1142
1143     if (N2 == N3) return N2;   // select C, X, X -> X
1144     break;
1145   case ISD::BRCOND:
1146     if (N2C)
1147       if (N2C->getValue()) // Unconditional branch
1148         return getNode(ISD::BR, MVT::Other, N1, N3);
1149       else
1150         return N1;         // Never-taken branch
1151     break;
1152   }
1153
1154   std::vector<SDOperand> Ops;
1155   Ops.reserve(3);
1156   Ops.push_back(N1);
1157   Ops.push_back(N2);
1158   Ops.push_back(N3);
1159
1160   // Memoize node if it doesn't produce a flag.
1161   SDNode *N;
1162   if (VT != MVT::Flag) {
1163     SDNode *&E = OneResultNodes[std::make_pair(Opcode,std::make_pair(VT, Ops))];
1164     if (E) return SDOperand(E, 0);
1165     E = N = new SDNode(Opcode, N1, N2, N3);
1166   } else {
1167     N = new SDNode(Opcode, N1, N2, N3);
1168   }
1169   N->setValueTypes(VT);
1170   AllNodes.push_back(N);
1171   return SDOperand(N, 0);
1172 }
1173
1174 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1175                                 SDOperand N1, SDOperand N2, SDOperand N3,
1176                                 SDOperand N4) {
1177   std::vector<SDOperand> Ops;
1178   Ops.reserve(4);
1179   Ops.push_back(N1);
1180   Ops.push_back(N2);
1181   Ops.push_back(N3);
1182   Ops.push_back(N4);
1183   return getNode(Opcode, VT, Ops);
1184 }
1185
1186 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1187                                 SDOperand N1, SDOperand N2, SDOperand N3,
1188                                 SDOperand N4, SDOperand N5) {
1189   std::vector<SDOperand> Ops;
1190   Ops.reserve(5);
1191   Ops.push_back(N1);
1192   Ops.push_back(N2);
1193   Ops.push_back(N3);
1194   Ops.push_back(N4);
1195   Ops.push_back(N5);
1196   return getNode(Opcode, VT, Ops);
1197 }
1198
1199
1200 SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) {
1201   assert((!V || isa<PointerType>(V->getType())) &&
1202          "SrcValue is not a pointer?");
1203   SDNode *&N = ValueNodes[std::make_pair(V, Offset)];
1204   if (N) return SDOperand(N, 0);
1205
1206   N = new SrcValueSDNode(V, Offset);
1207   AllNodes.push_back(N);
1208   return SDOperand(N, 0);
1209 }
1210
1211 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
1212                                 std::vector<SDOperand> &Ops) {
1213   switch (Ops.size()) {
1214   case 0: return getNode(Opcode, VT);
1215   case 1: return getNode(Opcode, VT, Ops[0]);
1216   case 2: return getNode(Opcode, VT, Ops[0], Ops[1]);
1217   case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]);
1218   default: break;
1219   }
1220
1221   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(Ops[1].Val);
1222   switch (Opcode) {
1223   default: break;
1224   case ISD::BRCONDTWOWAY:
1225     if (N1C)
1226       if (N1C->getValue()) // Unconditional branch to true dest.
1227         return getNode(ISD::BR, MVT::Other, Ops[0], Ops[2]);
1228       else                 // Unconditional branch to false dest.
1229         return getNode(ISD::BR, MVT::Other, Ops[0], Ops[3]);
1230     break;
1231   case ISD::BRTWOWAY_CC:
1232     assert(Ops.size() == 6 && "BRTWOWAY_CC takes 6 operands!");
1233     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
1234            "LHS and RHS of comparison must have same type!");
1235     break;
1236   case ISD::TRUNCSTORE: {
1237     assert(Ops.size() == 5 && "TRUNCSTORE takes 5 operands!");
1238     MVT::ValueType EVT = cast<VTSDNode>(Ops[4])->getVT();
1239 #if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store
1240     // If this is a truncating store of a constant, convert to the desired type
1241     // and store it instead.
1242     if (isa<Constant>(Ops[0])) {
1243       SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1);
1244       if (isa<Constant>(Op))
1245         N1 = Op;
1246     }
1247     // Also for ConstantFP?
1248 #endif
1249     if (Ops[0].getValueType() == EVT)       // Normal store?
1250       return getNode(ISD::STORE, VT, Ops[0], Ops[1], Ops[2], Ops[3]);
1251     assert(Ops[1].getValueType() > EVT && "Not a truncation?");
1252     assert(MVT::isInteger(Ops[1].getValueType()) == MVT::isInteger(EVT) &&
1253            "Can't do FP-INT conversion!");
1254     break;
1255   }
1256   case ISD::SELECT_CC: {
1257     assert(Ops.size() == 5 && "SELECT_CC takes 5 operands!");
1258     assert(Ops[0].getValueType() == Ops[1].getValueType() &&
1259            "LHS and RHS of condition must have same type!");
1260     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
1261            "True and False arms of SelectCC must have same type!");
1262     assert(Ops[2].getValueType() == VT &&
1263            "select_cc node must be of same type as true and false value!");
1264     break;
1265   }
1266   case ISD::BR_CC: {
1267     assert(Ops.size() == 5 && "BR_CC takes 5 operands!");
1268     assert(Ops[2].getValueType() == Ops[3].getValueType() &&
1269            "LHS/RHS of comparison should match types!");
1270     break;
1271   }
1272   }
1273
1274   // Memoize nodes.
1275   SDNode *N;
1276   if (VT != MVT::Flag) {
1277     SDNode *&E =
1278       OneResultNodes[std::make_pair(Opcode, std::make_pair(VT, Ops))];
1279     if (E) return SDOperand(E, 0);
1280     E = N = new SDNode(Opcode, Ops);
1281   } else {
1282     N = new SDNode(Opcode, Ops);
1283   }
1284   N->setValueTypes(VT);
1285   AllNodes.push_back(N);
1286   return SDOperand(N, 0);
1287 }
1288
1289 SDOperand SelectionDAG::getNode(unsigned Opcode,
1290                                 std::vector<MVT::ValueType> &ResultTys,
1291                                 std::vector<SDOperand> &Ops) {
1292   if (ResultTys.size() == 1)
1293     return getNode(Opcode, ResultTys[0], Ops);
1294
1295   switch (Opcode) {
1296   case ISD::EXTLOAD:
1297   case ISD::SEXTLOAD:
1298   case ISD::ZEXTLOAD: {
1299     MVT::ValueType EVT = cast<VTSDNode>(Ops[3])->getVT();
1300     assert(Ops.size() == 4 && ResultTys.size() == 2 && "Bad *EXTLOAD!");
1301     // If they are asking for an extending load from/to the same thing, return a
1302     // normal load.
1303     if (ResultTys[0] == EVT)
1304       return getLoad(ResultTys[0], Ops[0], Ops[1], Ops[2]);
1305     assert(EVT < ResultTys[0] &&
1306            "Should only be an extending load, not truncating!");
1307     assert((Opcode == ISD::EXTLOAD || MVT::isInteger(ResultTys[0])) &&
1308            "Cannot sign/zero extend a FP load!");
1309     assert(MVT::isInteger(ResultTys[0]) == MVT::isInteger(EVT) &&
1310            "Cannot convert from FP to Int or Int -> FP!");
1311     break;
1312   }
1313
1314   // FIXME: figure out how to safely handle things like
1315   // int foo(int x) { return 1 << (x & 255); }
1316   // int bar() { return foo(256); }
1317 #if 0
1318   case ISD::SRA_PARTS:
1319   case ISD::SRL_PARTS:
1320   case ISD::SHL_PARTS:
1321     if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG &&
1322         cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1)
1323       return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1324     else if (N3.getOpcode() == ISD::AND)
1325       if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) {
1326         // If the and is only masking out bits that cannot effect the shift,
1327         // eliminate the and.
1328         unsigned NumBits = MVT::getSizeInBits(VT)*2;
1329         if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1)
1330           return getNode(Opcode, VT, N1, N2, N3.getOperand(0));
1331       }
1332     break;
1333 #endif
1334   }
1335
1336   // Memoize the node unless it returns a flag.
1337   SDNode *N;
1338   if (ResultTys.back() != MVT::Flag) {
1339     SDNode *&E =
1340       ArbitraryNodes[std::make_pair(Opcode, std::make_pair(ResultTys, Ops))];
1341     if (E) return SDOperand(E, 0);
1342     E = N = new SDNode(Opcode, Ops);
1343   } else {
1344     N = new SDNode(Opcode, Ops);
1345   }
1346   setNodeValueTypes(N, ResultTys);
1347   AllNodes.push_back(N);
1348   return SDOperand(N, 0);
1349 }
1350
1351 void SelectionDAG::setNodeValueTypes(SDNode *N,
1352                                      std::vector<MVT::ValueType> &RetVals) {
1353   switch (RetVals.size()) {
1354   case 0: return;
1355   case 1: N->setValueTypes(RetVals[0]); return;
1356   case 2: setNodeValueTypes(N, RetVals[0], RetVals[1]); return;
1357   default: break;
1358   }
1359
1360   std::list<std::vector<MVT::ValueType> >::iterator I =
1361     std::find(VTList.begin(), VTList.end(), RetVals);
1362   if (I == VTList.end()) {
1363     VTList.push_front(RetVals);
1364     I = VTList.begin();
1365   }
1366
1367   N->setValueTypes(&(*I)[0], I->size());
1368 }
1369
1370 void SelectionDAG::setNodeValueTypes(SDNode *N, MVT::ValueType VT1,
1371                                      MVT::ValueType VT2) {
1372   for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(),
1373        E = VTList.end(); I != E; ++I) {
1374     if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2) {
1375       N->setValueTypes(&(*I)[0], 2);
1376       return;
1377     }
1378   }
1379   std::vector<MVT::ValueType> V;
1380   V.push_back(VT1);
1381   V.push_back(VT2);
1382   VTList.push_front(V);
1383   N->setValueTypes(&(*VTList.begin())[0], 2);
1384 }
1385
1386
1387 /// SelectNodeTo - These are used for target selectors to *mutate* the
1388 /// specified node to have the specified return type, Target opcode, and
1389 /// operands.  Note that target opcodes are stored as
1390 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field.
1391 void SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1392                                 MVT::ValueType VT) {
1393   RemoveNodeFromCSEMaps(N);
1394   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1395   N->setValueTypes(VT);
1396 }
1397 void SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1398                                 MVT::ValueType VT, SDOperand Op1) {
1399   RemoveNodeFromCSEMaps(N);
1400   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1401   N->setValueTypes(VT);
1402   N->setOperands(Op1);
1403 }
1404 void SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1405                                 MVT::ValueType VT, SDOperand Op1,
1406                                 SDOperand Op2) {
1407   RemoveNodeFromCSEMaps(N);
1408   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1409   N->setValueTypes(VT);
1410   N->setOperands(Op1, Op2);
1411 }
1412 void SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1413                                 MVT::ValueType VT1, MVT::ValueType VT2,
1414                                 SDOperand Op1, SDOperand Op2) {
1415   RemoveNodeFromCSEMaps(N);
1416   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1417   setNodeValueTypes(N, VT1, VT2);
1418   N->setOperands(Op1, Op2);
1419 }
1420 void SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1421                                 MVT::ValueType VT, SDOperand Op1,
1422                                 SDOperand Op2, SDOperand Op3) {
1423   RemoveNodeFromCSEMaps(N);
1424   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1425   N->setValueTypes(VT);
1426   N->setOperands(Op1, Op2, Op3);
1427 }
1428 void SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1429                                 MVT::ValueType VT1, MVT::ValueType VT2,
1430                                 SDOperand Op1, SDOperand Op2, SDOperand Op3) {
1431   RemoveNodeFromCSEMaps(N);
1432   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1433   setNodeValueTypes(N, VT1, VT2);
1434   N->setOperands(Op1, Op2, Op3);
1435 }
1436
1437 void SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1438                                 MVT::ValueType VT, SDOperand Op1,
1439                                 SDOperand Op2, SDOperand Op3, SDOperand Op4) {
1440   RemoveNodeFromCSEMaps(N);
1441   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1442   N->setValueTypes(VT);
1443   N->setOperands(Op1, Op2, Op3, Op4);
1444 }
1445 void SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc,
1446                                 MVT::ValueType VT, SDOperand Op1,
1447                                 SDOperand Op2, SDOperand Op3, SDOperand Op4,
1448                                 SDOperand Op5) {
1449   RemoveNodeFromCSEMaps(N);
1450   N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc);
1451   N->setValueTypes(VT);
1452   N->setOperands(Op1, Op2, Op3, Op4, Op5);
1453 }
1454
1455 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
1456 /// This can cause recursive merging of nodes in the DAG.
1457 ///
1458 /// This version assumes From/To have a single result value.
1459 ///
1460 void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN,
1461                                       std::vector<SDNode*> *Deleted) {
1462   SDNode *From = FromN.Val, *To = ToN.Val;
1463   assert(From->getNumValues() == 1 && To->getNumValues() == 1 &&
1464          "Cannot replace with this method!");
1465   assert(From != To && "Cannot replace uses of with self");
1466
1467   while (!From->use_empty()) {
1468     // Process users until they are all gone.
1469     SDNode *U = *From->use_begin();
1470
1471     // This node is about to morph, remove its old self from the CSE maps.
1472     RemoveNodeFromCSEMaps(U);
1473
1474     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
1475          I != E; ++I)
1476       if (I->Val == From) {
1477         From->removeUser(U);
1478         I->Val = To;
1479         To->addUser(U);
1480       }
1481
1482     // Now that we have modified U, add it back to the CSE maps.  If it already
1483     // exists there, recursively merge the results together.
1484     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
1485       ReplaceAllUsesWith(U, Existing, Deleted);
1486       // U is now dead.
1487       if (Deleted) Deleted->push_back(U);
1488       DeleteNodeNotInCSEMaps(U);
1489     }
1490   }
1491 }
1492
1493 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
1494 /// This can cause recursive merging of nodes in the DAG.
1495 ///
1496 /// This version assumes From/To have matching types and numbers of result
1497 /// values.
1498 ///
1499 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To,
1500                                       std::vector<SDNode*> *Deleted) {
1501   assert(From != To && "Cannot replace uses of with self");
1502   assert(From->getNumValues() == To->getNumValues() &&
1503          "Cannot use this version of ReplaceAllUsesWith!");
1504   if (From->getNumValues() == 1) {  // If possible, use the faster version.
1505     ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted);
1506     return;
1507   }
1508
1509   while (!From->use_empty()) {
1510     // Process users until they are all gone.
1511     SDNode *U = *From->use_begin();
1512
1513     // This node is about to morph, remove its old self from the CSE maps.
1514     RemoveNodeFromCSEMaps(U);
1515
1516     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
1517          I != E; ++I)
1518       if (I->Val == From) {
1519         From->removeUser(U);
1520         I->Val = To;
1521         To->addUser(U);
1522       }
1523
1524     // Now that we have modified U, add it back to the CSE maps.  If it already
1525     // exists there, recursively merge the results together.
1526     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
1527       ReplaceAllUsesWith(U, Existing, Deleted);
1528       // U is now dead.
1529       if (Deleted) Deleted->push_back(U);
1530       DeleteNodeNotInCSEMaps(U);
1531     }
1532   }
1533 }
1534
1535 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead.
1536 /// This can cause recursive merging of nodes in the DAG.
1537 ///
1538 /// This version can replace From with any result values.  To must match the
1539 /// number and types of values returned by From.
1540 void SelectionDAG::ReplaceAllUsesWith(SDNode *From,
1541                                       const std::vector<SDOperand> &To,
1542                                       std::vector<SDNode*> *Deleted) {
1543   assert(From->getNumValues() == To.size() &&
1544          "Incorrect number of values to replace with!");
1545   if (To.size() == 1 && To[0].Val->getNumValues() == 1) {
1546     // Degenerate case handled above.
1547     ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted);
1548     return;
1549   }
1550
1551   while (!From->use_empty()) {
1552     // Process users until they are all gone.
1553     SDNode *U = *From->use_begin();
1554
1555     // This node is about to morph, remove its old self from the CSE maps.
1556     RemoveNodeFromCSEMaps(U);
1557
1558     for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands;
1559          I != E; ++I)
1560       if (I->Val == From) {
1561         const SDOperand &ToOp = To[I->ResNo];
1562         From->removeUser(U);
1563         *I = ToOp;
1564         ToOp.Val->addUser(U);
1565       }
1566
1567     // Now that we have modified U, add it back to the CSE maps.  If it already
1568     // exists there, recursively merge the results together.
1569     if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) {
1570       ReplaceAllUsesWith(U, Existing, Deleted);
1571       // U is now dead.
1572       if (Deleted) Deleted->push_back(U);
1573       DeleteNodeNotInCSEMaps(U);
1574     }
1575   }
1576 }
1577
1578
1579 //===----------------------------------------------------------------------===//
1580 //                              SDNode Class
1581 //===----------------------------------------------------------------------===//
1582
1583
1584 /// getValueTypeList - Return a pointer to the specified value type.
1585 ///
1586 MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) {
1587   static MVT::ValueType VTs[MVT::LAST_VALUETYPE];
1588   VTs[VT] = VT;
1589   return &VTs[VT];
1590 }
1591
1592 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
1593 /// indicated value.  This method ignores uses of other values defined by this
1594 /// operation.
1595 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) {
1596   assert(Value < getNumValues() && "Bad value!");
1597
1598   // If there is only one value, this is easy.
1599   if (getNumValues() == 1)
1600     return use_size() == NUses;
1601   if (Uses.size() < NUses) return false;
1602
1603   SDOperand TheValue(this, Value);
1604
1605   std::set<SDNode*> UsersHandled;
1606
1607   for (std::vector<SDNode*>::iterator UI = Uses.begin(), E = Uses.end();
1608        UI != E; ++UI) {
1609     SDNode *User = *UI;
1610     if (User->getNumOperands() == 1 ||
1611         UsersHandled.insert(User).second)     // First time we've seen this?
1612       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
1613         if (User->getOperand(i) == TheValue) {
1614           if (NUses == 0)
1615             return false;   // too many uses
1616           --NUses;
1617         }
1618   }
1619
1620   // Found exactly the right number of uses?
1621   return NUses == 0;
1622 }
1623
1624
1625 const char *SDNode::getOperationName(const SelectionDAG *G) const {
1626   switch (getOpcode()) {
1627   default:
1628     if (getOpcode() < ISD::BUILTIN_OP_END)
1629       return "<<Unknown DAG Node>>";
1630     else {
1631       if (G)
1632         if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo())
1633           if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes())
1634             return TII->getName(getOpcode()-ISD::BUILTIN_OP_END);
1635       return "<<Unknown Target Node>>";
1636     }
1637
1638   case ISD::PCMARKER:      return "PCMarker";
1639   case ISD::SRCVALUE:      return "SrcValue";
1640   case ISD::VALUETYPE:     return "ValueType";
1641   case ISD::EntryToken:    return "EntryToken";
1642   case ISD::TokenFactor:   return "TokenFactor";
1643   case ISD::AssertSext:    return "AssertSext";
1644   case ISD::AssertZext:    return "AssertZext";
1645   case ISD::Constant:      return "Constant";
1646   case ISD::TargetConstant: return "TargetConstant";
1647   case ISD::ConstantFP:    return "ConstantFP";
1648   case ISD::GlobalAddress: return "GlobalAddress";
1649   case ISD::TargetGlobalAddress: return "TargetGlobalAddress";
1650   case ISD::FrameIndex:    return "FrameIndex";
1651   case ISD::TargetFrameIndex: return "TargetFrameIndex";
1652   case ISD::BasicBlock:    return "BasicBlock";
1653   case ISD::Register:      return "Register";
1654   case ISD::ExternalSymbol: return "ExternalSymbol";
1655   case ISD::TargetExternalSymbol: return "TargetExternalSymbol";
1656   case ISD::ConstantPool:  return "ConstantPool";
1657   case ISD::TargetConstantPool:  return "TargetConstantPool";
1658   case ISD::CopyToReg:     return "CopyToReg";
1659   case ISD::CopyFromReg:   return "CopyFromReg";
1660   case ISD::ImplicitDef:   return "ImplicitDef";
1661   case ISD::UNDEF:         return "undef";
1662
1663   // Unary operators
1664   case ISD::FABS:   return "fabs";
1665   case ISD::FNEG:   return "fneg";
1666   case ISD::FSQRT:  return "fsqrt";
1667   case ISD::FSIN:   return "fsin";
1668   case ISD::FCOS:   return "fcos";
1669
1670   // Binary operators
1671   case ISD::ADD:    return "add";
1672   case ISD::SUB:    return "sub";
1673   case ISD::MUL:    return "mul";
1674   case ISD::MULHU:  return "mulhu";
1675   case ISD::MULHS:  return "mulhs";
1676   case ISD::SDIV:   return "sdiv";
1677   case ISD::UDIV:   return "udiv";
1678   case ISD::SREM:   return "srem";
1679   case ISD::UREM:   return "urem";
1680   case ISD::AND:    return "and";
1681   case ISD::OR:     return "or";
1682   case ISD::XOR:    return "xor";
1683   case ISD::SHL:    return "shl";
1684   case ISD::SRA:    return "sra";
1685   case ISD::SRL:    return "srl";
1686   case ISD::FADD:   return "fadd";
1687   case ISD::FSUB:   return "fsub";
1688   case ISD::FMUL:   return "fmul";
1689   case ISD::FDIV:   return "fdiv";
1690   case ISD::FREM:   return "frem";
1691
1692   case ISD::SETCC:       return "setcc";
1693   case ISD::SELECT:      return "select";
1694   case ISD::SELECT_CC:   return "select_cc";
1695   case ISD::ADD_PARTS:   return "add_parts";
1696   case ISD::SUB_PARTS:   return "sub_parts";
1697   case ISD::SHL_PARTS:   return "shl_parts";
1698   case ISD::SRA_PARTS:   return "sra_parts";
1699   case ISD::SRL_PARTS:   return "srl_parts";
1700
1701   // Conversion operators.
1702   case ISD::SIGN_EXTEND: return "sign_extend";
1703   case ISD::ZERO_EXTEND: return "zero_extend";
1704   case ISD::ANY_EXTEND:  return "any_extend";
1705   case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
1706   case ISD::TRUNCATE:    return "truncate";
1707   case ISD::FP_ROUND:    return "fp_round";
1708   case ISD::FP_ROUND_INREG: return "fp_round_inreg";
1709   case ISD::FP_EXTEND:   return "fp_extend";
1710
1711   case ISD::SINT_TO_FP:  return "sint_to_fp";
1712   case ISD::UINT_TO_FP:  return "uint_to_fp";
1713   case ISD::FP_TO_SINT:  return "fp_to_sint";
1714   case ISD::FP_TO_UINT:  return "fp_to_uint";
1715
1716     // Control flow instructions
1717   case ISD::BR:      return "br";
1718   case ISD::BRCOND:  return "brcond";
1719   case ISD::BRCONDTWOWAY:  return "brcondtwoway";
1720   case ISD::BR_CC:  return "br_cc";
1721   case ISD::BRTWOWAY_CC:  return "brtwoway_cc";
1722   case ISD::RET:     return "ret";
1723   case ISD::CALL:    return "call";
1724   case ISD::TAILCALL:return "tailcall";
1725   case ISD::CALLSEQ_START:  return "callseq_start";
1726   case ISD::CALLSEQ_END:    return "callseq_end";
1727
1728     // Other operators
1729   case ISD::LOAD:    return "load";
1730   case ISD::STORE:   return "store";
1731   case ISD::EXTLOAD:    return "extload";
1732   case ISD::SEXTLOAD:   return "sextload";
1733   case ISD::ZEXTLOAD:   return "zextload";
1734   case ISD::TRUNCSTORE: return "truncstore";
1735
1736   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
1737   case ISD::EXTRACT_ELEMENT: return "extract_element";
1738   case ISD::BUILD_PAIR: return "build_pair";
1739   case ISD::MEMSET:  return "memset";
1740   case ISD::MEMCPY:  return "memcpy";
1741   case ISD::MEMMOVE: return "memmove";
1742
1743   // Bit counting
1744   case ISD::CTPOP:   return "ctpop";
1745   case ISD::CTTZ:    return "cttz";
1746   case ISD::CTLZ:    return "ctlz";
1747
1748   // IO Intrinsics
1749   case ISD::READPORT: return "readport";
1750   case ISD::WRITEPORT: return "writeport";
1751   case ISD::READIO: return "readio";
1752   case ISD::WRITEIO: return "writeio";
1753
1754   case ISD::CONDCODE:
1755     switch (cast<CondCodeSDNode>(this)->get()) {
1756     default: assert(0 && "Unknown setcc condition!");
1757     case ISD::SETOEQ:  return "setoeq";
1758     case ISD::SETOGT:  return "setogt";
1759     case ISD::SETOGE:  return "setoge";
1760     case ISD::SETOLT:  return "setolt";
1761     case ISD::SETOLE:  return "setole";
1762     case ISD::SETONE:  return "setone";
1763
1764     case ISD::SETO:    return "seto";
1765     case ISD::SETUO:   return "setuo";
1766     case ISD::SETUEQ:  return "setue";
1767     case ISD::SETUGT:  return "setugt";
1768     case ISD::SETUGE:  return "setuge";
1769     case ISD::SETULT:  return "setult";
1770     case ISD::SETULE:  return "setule";
1771     case ISD::SETUNE:  return "setune";
1772
1773     case ISD::SETEQ:   return "seteq";
1774     case ISD::SETGT:   return "setgt";
1775     case ISD::SETGE:   return "setge";
1776     case ISD::SETLT:   return "setlt";
1777     case ISD::SETLE:   return "setle";
1778     case ISD::SETNE:   return "setne";
1779     }
1780   }
1781 }
1782
1783 void SDNode::dump() const { dump(0); }
1784 void SDNode::dump(const SelectionDAG *G) const {
1785   std::cerr << (void*)this << ": ";
1786
1787   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
1788     if (i) std::cerr << ",";
1789     if (getValueType(i) == MVT::Other)
1790       std::cerr << "ch";
1791     else
1792       std::cerr << MVT::getValueTypeString(getValueType(i));
1793   }
1794   std::cerr << " = " << getOperationName(G);
1795
1796   std::cerr << " ";
1797   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1798     if (i) std::cerr << ", ";
1799     std::cerr << (void*)getOperand(i).Val;
1800     if (unsigned RN = getOperand(i).ResNo)
1801       std::cerr << ":" << RN;
1802   }
1803
1804   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
1805     std::cerr << "<" << CSDN->getValue() << ">";
1806   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
1807     std::cerr << "<" << CSDN->getValue() << ">";
1808   } else if (const GlobalAddressSDNode *GADN =
1809              dyn_cast<GlobalAddressSDNode>(this)) {
1810     std::cerr << "<";
1811     WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
1812   } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) {
1813     std::cerr << "<" << FIDN->getIndex() << ">";
1814   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
1815     std::cerr << "<" << *CP->get() << ">";
1816   } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) {
1817     std::cerr << "<";
1818     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
1819     if (LBB)
1820       std::cerr << LBB->getName() << " ";
1821     std::cerr << (const void*)BBDN->getBasicBlock() << ">";
1822   } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) {
1823     if (G && MRegisterInfo::isPhysicalRegister(R->getReg())) {
1824       std::cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg());
1825     } else {
1826       std::cerr << " #" << R->getReg();
1827     }
1828   } else if (const ExternalSymbolSDNode *ES =
1829              dyn_cast<ExternalSymbolSDNode>(this)) {
1830     std::cerr << "'" << ES->getSymbol() << "'";
1831   } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) {
1832     if (M->getValue())
1833       std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">";
1834     else
1835       std::cerr << "<null:" << M->getOffset() << ">";
1836   } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) {
1837     std::cerr << ":" << getValueTypeString(N->getVT());
1838   }
1839 }
1840
1841 static void DumpNodes(SDNode *N, unsigned indent, const SelectionDAG *G) {
1842   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1843     if (N->getOperand(i).Val->hasOneUse())
1844       DumpNodes(N->getOperand(i).Val, indent+2, G);
1845     else
1846       std::cerr << "\n" << std::string(indent+2, ' ')
1847                 << (void*)N->getOperand(i).Val << ": <multiple use>";
1848
1849
1850   std::cerr << "\n" << std::string(indent, ' ');
1851   N->dump(G);
1852 }
1853
1854 void SelectionDAG::dump() const {
1855   std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
1856   std::vector<SDNode*> Nodes(AllNodes);
1857   std::sort(Nodes.begin(), Nodes.end());
1858
1859   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
1860     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
1861       DumpNodes(Nodes[i], 2, this);
1862   }
1863
1864   DumpNodes(getRoot().Val, 2, this);
1865
1866   std::cerr << "\n\n";
1867 }
1868