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 <iostream>
  20 #include <set>
  21 #include <cmath>
  22 #include <algorithm>
  23 using namespace llvm;
  24
  25 static bool isCommutativeBinOp(unsigned Opcode) {
  26   switch (Opcode) {
  27   case ISD::ADD:
  28   case ISD::MUL:
  29   case ISD::AND:
  30   case ISD::OR:
  31   case ISD::XOR: return true;
  32   default: return false; // FIXME: Need commutative info for user ops!
  33   }
  34 }
  35
  36 static bool isAssociativeBinOp(unsigned Opcode) {
  37   switch (Opcode) {
  38   case ISD::ADD:
  39   case ISD::MUL:
  40   case ISD::AND:
  41   case ISD::OR:
  42   case ISD::XOR: return true;
  43   default: return false; // FIXME: Need associative info for user ops!
  44   }
  45 }
  46
  47 static unsigned ExactLog2(uint64_t Val) {
  48   unsigned Count = 0;
  49   while (Val != 1) {
  50     Val >>= 1;
  51     ++Count;
  52   }
  53   return Count;
  54 }
  55
  56 // isInvertibleForFree - Return true if there is no cost to emitting the logical
  57 // inverse of this node.
  58 static bool isInvertibleForFree(SDOperand N) {
  59   if (isa<ConstantSDNode>(N.Val)) return true;
  60   if (isa<SetCCSDNode>(N.Val) && N.Val->hasOneUse())
  61     return true;
  62   return false;
  63 }
  64
  65
  66 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
  67 /// when given the operation for (X op Y).
  68 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
  69   // To perform this operation, we just need to swap the L and G bits of the
  70   // operation.
  71   unsigned OldL = (Operation >> 2) & 1;
  72   unsigned OldG = (Operation >> 1) & 1;
  73   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
  74                        (OldL << 1) |       // New G bit
  75                        (OldG << 2));        // New L bit.
  76 }
  77
  78 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
  79 /// 'op' is a valid SetCC operation.
  80 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
  81   unsigned Operation = Op;
  82   if (isInteger)
  83     Operation ^= 7;   // Flip L, G, E bits, but not U.
  84   else
  85     Operation ^= 15;  // Flip all of the condition bits.
  86   if (Operation > ISD::SETTRUE2)
  87     Operation &= ~8;     // Don't let N and U bits get set.
  88   return ISD::CondCode(Operation);
  89 }
  90
  91
  92 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
  93 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
  94 /// if the operation does not depend on the sign of the input (setne and seteq).
  95 static int isSignedOp(ISD::CondCode Opcode) {
  96   switch (Opcode) {
  97   default: assert(0 && "Illegal integer setcc operation!");
  98   case ISD::SETEQ:
  99   case ISD::SETNE: return 0;
 100   case ISD::SETLT:
 101   case ISD::SETLE:
 102   case ISD::SETGT:
 103   case ISD::SETGE: return 1;
 104   case ISD::SETULT:
 105   case ISD::SETULE:
 106   case ISD::SETUGT:
 107   case ISD::SETUGE: return 2;
 108   }
 109 }
 110
 111 /// getSetCCOrOperation - Return the result of a logical OR between different
 112 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
 113 /// returns SETCC_INVALID if it is not possible to represent the resultant
 114 /// comparison.
 115 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 116                                        bool isInteger) {
 117   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 118     // Cannot fold a signed integer setcc with an unsigned integer setcc.
 119     return ISD::SETCC_INVALID;
 120
 121   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
 122
 123   // If the N and U bits get set then the resultant comparison DOES suddenly
 124   // care about orderedness, and is true when ordered.
 125   if (Op > ISD::SETTRUE2)
 126     Op &= ~16;     // Clear the N bit.
 127   return ISD::CondCode(Op);
 128 }
 129
 130 /// getSetCCAndOperation - Return the result of a logical AND between different
 131 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
 132 /// function returns zero if it is not possible to represent the resultant
 133 /// comparison.
 134 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
 135                                         bool isInteger) {
 136   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
 137     // Cannot fold a signed setcc with an unsigned setcc.
 138     return ISD::SETCC_INVALID;
 139
 140   // Combine all of the condition bits.
 141   return ISD::CondCode(Op1 & Op2);
 142 }
 143
 144 /// RemoveDeadNodes - This method deletes all unreachable nodes in the
 145 /// SelectionDAG, including nodes (like loads) that have uses of their token
 146 /// chain but no other uses and no side effect.  If a node is passed in as an
 147 /// argument, it is used as the seed for node deletion.
 148 void SelectionDAG::RemoveDeadNodes(SDNode *N) {
 149   std::set<SDNode*> AllNodeSet(AllNodes.begin(), AllNodes.end());
 150
 151   // Create a dummy node (which is not added to allnodes), that adds a reference
 152   // to the root node, preventing it from being deleted.
 153   SDNode *DummyNode = new SDNode(ISD::EntryToken, getRoot());
 154
 155   DeleteNodeIfDead(N, &AllNodeSet);
 156
 157  Restart:
 158   unsigned NumNodes = AllNodeSet.size();
 159   for (std::set<SDNode*>::iterator I = AllNodeSet.begin(), E = AllNodeSet.end();
 160        I != E; ++I) {
 161     // Try to delete this node.
 162     DeleteNodeIfDead(*I, &AllNodeSet);
 163
 164     // If we actually deleted any nodes, do not use invalid iterators in
 165     // AllNodeSet.
 166     if (AllNodeSet.size() != NumNodes)
 167       goto Restart;
 168   }
 169
 170   // Restore AllNodes.
 171   if (AllNodes.size() != NumNodes)
 172     AllNodes.assign(AllNodeSet.begin(), AllNodeSet.end());
 173
 174   // If the root changed (e.g. it was a dead load, update the root).
 175   setRoot(DummyNode->getOperand(0));
 176
 177   // Now that we are done with the dummy node, delete it.
 178   DummyNode->getOperand(0).Val->removeUser(DummyNode);
 179   delete DummyNode;
 180 }
 181
 182 void SelectionDAG::DeleteNodeIfDead(SDNode *N, void *NodeSet) {
 183   if (!N->use_empty())
 184     return;
 185
 186   // Okay, we really are going to delete this node.  First take this out of the
 187   // appropriate CSE map.
 188   switch (N->getOpcode()) {
 189   case ISD::Constant:
 190     Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(),
 191                                    N->getValueType(0)));
 192     break;
 193   case ISD::ConstantFP:
 194     ConstantFPs.erase(std::make_pair(cast<ConstantFPSDNode>(N)->getValue(),
 195                                      N->getValueType(0)));
 196     break;
 197   case ISD::GlobalAddress:
 198     GlobalValues.erase(cast<GlobalAddressSDNode>(N)->getGlobal());
 199     break;
 200   case ISD::FrameIndex:
 201     FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex());
 202     break;
 203   case ISD::ConstantPool:
 204     ConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->getIndex());
 205     break;
 206   case ISD::BasicBlock:
 207     BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock());
 208     break;
 209   case ISD::ExternalSymbol:
 210     ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol());
 211     break;
 212
 213   case ISD::LOAD:
 214     Loads.erase(std::make_pair(N->getOperand(1),
 215                                std::make_pair(N->getOperand(0),
 216                                               N->getValueType(0))));
 217     break;
 218   case ISD::SETCC:
 219     SetCCs.erase(std::make_pair(std::make_pair(N->getOperand(0),
 220                                                N->getOperand(1)),
 221                                 cast<SetCCSDNode>(N)->getCondition()));
 222     break;
 223   case ISD::TRUNCSTORE:
 224   case ISD::SIGN_EXTEND_INREG:
 225   case ISD::ZERO_EXTEND_INREG:
 226   case ISD::FP_ROUND_INREG:
 227   case ISD::EXTLOAD:
 228   case ISD::SEXTLOAD:
 229   case ISD::ZEXTLOAD: {
 230     EVTStruct NN;
 231     NN.Opcode = ISD::TRUNCSTORE;
 232     NN.VT = N->getValueType(0);
 233     NN.EVT = cast<MVTSDNode>(N)->getExtraValueType();
 234     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 235       NN.Ops.push_back(N->getOperand(i));
 236     MVTSDNodes.erase(NN);
 237     break;
 238   }
 239   default:
 240     if (N->getNumOperands() == 1)
 241       UnaryOps.erase(std::make_pair(N->getOpcode(),
 242                                     std::make_pair(N->getOperand(0),
 243                                                    N->getValueType(0))));
 244     else if (N->getNumOperands() == 2)
 245       BinaryOps.erase(std::make_pair(N->getOpcode(),
 246                                      std::make_pair(N->getOperand(0),
 247                                                     N->getOperand(1))));
 248     break;
 249   }
 250
 251   // Next, brutally remove the operand list.
 252   while (!N->Operands.empty()) {
 253     SDNode *O = N->Operands.back().Val;
 254     N->Operands.pop_back();
 255     O->removeUser(N);
 256
 257     // Now that we removed this operand, see if there are no uses of it left.
 258     DeleteNodeIfDead(O, NodeSet);
 259   }
 260
 261   // Remove the node from the nodes set and delete it.
 262   std::set<SDNode*> &AllNodeSet = *(std::set<SDNode*>*)NodeSet;
 263   AllNodeSet.erase(N);
 264
 265   // Now that the node is gone, check to see if any of the operands of this node
 266   // are dead now.
 267   delete N;
 268 }
 269
 270
 271 SelectionDAG::~SelectionDAG() {
 272   for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
 273     delete AllNodes[i];
 274 }
 275
 276 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) {
 277   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 278   // Mask out any bits that are not valid for this constant.
 279   if (VT != MVT::i64)
 280     Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
 281
 282   SDNode *&N = Constants[std::make_pair(Val, VT)];
 283   if (N) return SDOperand(N, 0);
 284   N = new ConstantSDNode(Val, VT);
 285   AllNodes.push_back(N);
 286   return SDOperand(N, 0);
 287 }
 288
 289 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
 290   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
 291   if (VT == MVT::f32)
 292     Val = (float)Val;  // Mask out extra precision.
 293
 294   SDNode *&N = ConstantFPs[std::make_pair(Val, VT)];
 295   if (N) return SDOperand(N, 0);
 296   N = new ConstantFPSDNode(Val, VT);
 297   AllNodes.push_back(N);
 298   return SDOperand(N, 0);
 299 }
 300
 301
 302
 303 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 304                                          MVT::ValueType VT) {
 305   SDNode *&N = GlobalValues[GV];
 306   if (N) return SDOperand(N, 0);
 307   N = new GlobalAddressSDNode(GV,VT);
 308   AllNodes.push_back(N);
 309   return SDOperand(N, 0);
 310 }
 311
 312 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) {
 313   SDNode *&N = FrameIndices[FI];
 314   if (N) return SDOperand(N, 0);
 315   N = new FrameIndexSDNode(FI, VT);
 316   AllNodes.push_back(N);
 317   return SDOperand(N, 0);
 318 }
 319
 320 SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) {
 321   SDNode *N = ConstantPoolIndices[CPIdx];
 322   if (N) return SDOperand(N, 0);
 323   N = new ConstantPoolSDNode(CPIdx, VT);
 324   AllNodes.push_back(N);
 325   return SDOperand(N, 0);
 326 }
 327
 328 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
 329   SDNode *&N = BBNodes[MBB];
 330   if (N) return SDOperand(N, 0);
 331   N = new BasicBlockSDNode(MBB);
 332   AllNodes.push_back(N);
 333   return SDOperand(N, 0);
 334 }
 335
 336 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
 337   SDNode *&N = ExternalSymbols[Sym];
 338   if (N) return SDOperand(N, 0);
 339   N = new ExternalSymbolSDNode(Sym, VT);
 340   AllNodes.push_back(N);
 341   return SDOperand(N, 0);
 342 }
 343
 344 SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, MVT::ValueType VT,
 345                                  SDOperand N1, SDOperand N2) {
 346   // These setcc operations always fold.
 347   switch (Cond) {
 348   default: break;
 349   case ISD::SETFALSE:
 350   case ISD::SETFALSE2: return getConstant(0, VT);
 351   case ISD::SETTRUE:
 352   case ISD::SETTRUE2:  return getConstant(1, VT);
 353   }
 354
 355   if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val))
 356     if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
 357       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
 358
 359       // Sign extend the operands if required
 360       if (ISD::isSignedIntSetCC(Cond)) {
 361         C1 = N1C->getSignExtended();
 362         C2 = N2C->getSignExtended();
 363       }
 364
 365       switch (Cond) {
 366       default: assert(0 && "Unknown integer setcc!");
 367       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
 368       case ISD::SETNE:  return getConstant(C1 != C2, VT);
 369       case ISD::SETULT: return getConstant(C1 <  C2, VT);
 370       case ISD::SETUGT: return getConstant(C1 >  C2, VT);
 371       case ISD::SETULE: return getConstant(C1 <= C2, VT);
 372       case ISD::SETUGE: return getConstant(C1 >= C2, VT);
 373       case ISD::SETLT:  return getConstant((int64_t)C1 <  (int64_t)C2, VT);
 374       case ISD::SETGT:  return getConstant((int64_t)C1 >  (int64_t)C2, VT);
 375       case ISD::SETLE:  return getConstant((int64_t)C1 <= (int64_t)C2, VT);
 376       case ISD::SETGE:  return getConstant((int64_t)C1 >= (int64_t)C2, VT);
 377       }
 378     } else {
 379       // Ensure that the constant occurs on the RHS.
 380       Cond = ISD::getSetCCSwappedOperands(Cond);
 381       std::swap(N1, N2);
 382     }
 383
 384   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
 385     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
 386       double C1 = N1C->getValue(), C2 = N2C->getValue();
 387
 388       switch (Cond) {
 389       default: break; // FIXME: Implement the rest of these!
 390       case ISD::SETEQ:  return getConstant(C1 == C2, VT);
 391       case ISD::SETNE:  return getConstant(C1 != C2, VT);
 392       case ISD::SETLT:  return getConstant(C1 < C2, VT);
 393       case ISD::SETGT:  return getConstant(C1 > C2, VT);
 394       case ISD::SETLE:  return getConstant(C1 <= C2, VT);
 395       case ISD::SETGE:  return getConstant(C1 >= C2, VT);
 396       }
 397     } else {
 398       // Ensure that the constant occurs on the RHS.
 399       Cond = ISD::getSetCCSwappedOperands(Cond);
 400       std::swap(N1, N2);
 401     }
 402
 403   if (N1 == N2) {
 404     // We can always fold X == Y for integer setcc's.
 405     if (MVT::isInteger(N1.getValueType()))
 406       return getConstant(ISD::isTrueWhenEqual(Cond), VT);
 407     unsigned UOF = ISD::getUnorderedFlavor(Cond);
 408     if (UOF == 2)   // FP operators that are undefined on NaNs.
 409       return getConstant(ISD::isTrueWhenEqual(Cond), VT);
 410     if (UOF == ISD::isTrueWhenEqual(Cond))
 411       return getConstant(UOF, VT);
 412     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
 413     // if it is not already.
 414     Cond = UOF == 0 ? ISD::SETUO : ISD::SETO;
 415   }
 416
 417   if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
 418       MVT::isInteger(N1.getValueType())) {
 419     if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
 420         N1.getOpcode() == ISD::XOR) {
 421       // Simplify (X+Y) == (X+Z) -->  Y == Z
 422       if (N1.getOpcode() == N2.getOpcode()) {
 423         if (N1.getOperand(0) == N2.getOperand(0))
 424           return getSetCC(Cond, VT, N1.getOperand(1), N2.getOperand(1));
 425         if (N1.getOperand(1) == N2.getOperand(1))
 426           return getSetCC(Cond, VT, N1.getOperand(0), N2.getOperand(0));
 427         if (isCommutativeBinOp(N1.getOpcode())) {
 428           // If X op Y == Y op X, try other combinations.
 429           if (N1.getOperand(0) == N2.getOperand(1))
 430             return getSetCC(Cond, VT, N1.getOperand(1), N2.getOperand(0));
 431           if (N1.getOperand(1) == N2.getOperand(0))
 432             return getSetCC(Cond, VT, N1.getOperand(1), N2.getOperand(1));
 433         }
 434       }
 435
 436       // Simplify (X+Z) == X -->  Z == 0
 437       if (N1.getOperand(0) == N2)
 438         return getSetCC(Cond, VT, N1.getOperand(1),
 439                         getConstant(0, N1.getValueType()));
 440       if (N1.getOperand(1) == N2) {
 441         if (isCommutativeBinOp(N1.getOpcode()))
 442           return getSetCC(Cond, VT, N1.getOperand(0),
 443                           getConstant(0, N1.getValueType()));
 444         else {
 445           assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
 446           // (Z-X) == X  --> Z == X<<1
 447           return getSetCC(Cond, VT, N1.getOperand(0),
 448                           getNode(ISD::SHL, N2.getValueType(),
 449                                   N2, getConstant(1, MVT::i8)));
 450         }
 451       }
 452     }
 453
 454     if (N2.getOpcode() == ISD::ADD || N2.getOpcode() == ISD::SUB ||
 455         N2.getOpcode() == ISD::XOR) {
 456       // Simplify  X == (X+Z) -->  Z == 0
 457       if (N2.getOperand(0) == N1)
 458         return getSetCC(Cond, VT, N2.getOperand(1),
 459                         getConstant(0, N2.getValueType()));
 460       else if (N2.getOperand(1) == N1)
 461         return getSetCC(Cond, VT, N2.getOperand(0),
 462                         getConstant(0, N2.getValueType()));
 463     }
 464   }
 465
 466   SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), Cond)];
 467   if (N) return SDOperand(N, 0);
 468   N = new SetCCSDNode(Cond, N1, N2);
 469   N->setValueTypes(VT);
 470   AllNodes.push_back(N);
 471   return SDOperand(N, 0);
 472 }
 473
 474
 475
 476 /// getNode - Gets or creates the specified node.
 477 ///
 478 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
 479   SDNode *N = new SDNode(Opcode, VT);
 480   AllNodes.push_back(N);
 481   return SDOperand(N, 0);
 482 }
 483
 484 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 485                                 SDOperand Operand) {
 486   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
 487     uint64_t Val = C->getValue();
 488     switch (Opcode) {
 489     default: break;
 490     case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
 491     case ISD::ZERO_EXTEND: return getConstant(Val, VT);
 492     case ISD::TRUNCATE:    return getConstant(Val, VT);
 493     case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
 494     case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
 495     }
 496   }
 497
 498   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
 499     switch (Opcode) {
 500     case ISD::FP_ROUND:
 501     case ISD::FP_EXTEND:
 502       return getConstantFP(C->getValue(), VT);
 503     case ISD::FP_TO_SINT:
 504       return getConstant((int64_t)C->getValue(), VT);
 505     case ISD::FP_TO_UINT:
 506       return getConstant((uint64_t)C->getValue(), VT);
 507     }
 508
 509   unsigned OpOpcode = Operand.Val->getOpcode();
 510   switch (Opcode) {
 511   case ISD::SIGN_EXTEND:
 512     if (Operand.getValueType() == VT) return Operand;   // noop extension
 513     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
 514       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 515     break;
 516   case ISD::ZERO_EXTEND:
 517     if (Operand.getValueType() == VT) return Operand;   // noop extension
 518     if (OpOpcode == ISD::ZERO_EXTEND)
 519       return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0));
 520     break;
 521   case ISD::TRUNCATE:
 522     if (Operand.getValueType() == VT) return Operand;   // noop truncate
 523     if (OpOpcode == ISD::TRUNCATE)
 524       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
 525     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) {
 526       // If the source is smaller than the dest, we still need an extend.
 527       if (Operand.Val->getOperand(0).getValueType() < VT)
 528         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 529       else if (Operand.Val->getOperand(0).getValueType() > VT)
 530         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
 531       else
 532         return Operand.Val->getOperand(0);
 533     }
 534     break;
 535   }
 536
 537   SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
 538   if (N) return SDOperand(N, 0);
 539   N = new SDNode(Opcode, Operand);
 540   N->setValueTypes(VT);
 541   AllNodes.push_back(N);
 542   return SDOperand(N, 0);
 543 }
 544
 545 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 546                                 SDOperand N1, SDOperand N2) {
 547 #ifndef NDEBUG
 548   switch (Opcode) {
 549   case ISD::AND:
 550   case ISD::OR:
 551   case ISD::XOR:
 552   case ISD::UDIV:
 553   case ISD::UREM:
 554     assert(MVT::isInteger(VT) && "This operator does not apply to FP types!");
 555     // fall through
 556   case ISD::ADD:
 557   case ISD::SUB:
 558   case ISD::MUL:
 559   case ISD::SDIV:
 560   case ISD::SREM:
 561     assert(N1.getValueType() == N2.getValueType() &&
 562            N1.getValueType() == VT && "Binary operator types must match!");
 563     break;
 564
 565   case ISD::SHL:
 566   case ISD::SRA:
 567   case ISD::SRL:
 568     assert(VT == N1.getValueType() &&
 569            "Shift operators return type must be the same as their first arg");
 570     assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) &&
 571            VT != MVT::i1 && "Shifts only work on integers");
 572     break;
 573   default: break;
 574   }
 575 #endif
 576
 577   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 578   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
 579   if (N1C) {
 580     if (N2C) {
 581       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
 582       switch (Opcode) {
 583       case ISD::ADD: return getConstant(C1 + C2, VT);
 584       case ISD::SUB: return getConstant(C1 - C2, VT);
 585       case ISD::MUL: return getConstant(C1 * C2, VT);
 586       case ISD::UDIV:
 587         if (C2) return getConstant(C1 / C2, VT);
 588         break;
 589       case ISD::UREM :
 590         if (C2) return getConstant(C1 % C2, VT);
 591         break;
 592       case ISD::SDIV :
 593         if (C2) return getConstant(N1C->getSignExtended() /
 594                                    N2C->getSignExtended(), VT);
 595         break;
 596       case ISD::SREM :
 597         if (C2) return getConstant(N1C->getSignExtended() %
 598                                    N2C->getSignExtended(), VT);
 599         break;
 600       case ISD::AND  : return getConstant(C1 & C2, VT);
 601       case ISD::OR   : return getConstant(C1 | C2, VT);
 602       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
 603       case ISD::SHL  : return getConstant(C1 << (int)C2, VT);
 604       case ISD::SRL  : return getConstant(C1 >> (unsigned)C2, VT);
 605       case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
 606       default: break;
 607       }
 608
 609     } else {      // Cannonicalize constant to RHS if commutative
 610       if (isCommutativeBinOp(Opcode)) {
 611         std::swap(N1C, N2C);
 612         std::swap(N1, N2);
 613       }
 614     }
 615   }
 616
 617   if (N2C) {
 618     uint64_t C2 = N2C->getValue();
 619
 620     switch (Opcode) {
 621     case ISD::ADD:
 622       if (!C2) return N1;         // add X, 0 -> X
 623       break;
 624     case ISD::SUB:
 625       if (!C2) return N1;         // sub X, 0 -> X
 626       break;
 627     case ISD::MUL:
 628       if (!C2) return N2;         // mul X, 0 -> 0
 629       if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X
 630         return getNode(ISD::SUB, VT, getConstant(0, VT), N1);
 631
 632       // FIXME: This should only be done if the target supports shift
 633       // operations.
 634       if ((C2 & C2-1) == 0) {
 635         SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
 636         return getNode(ISD::SHL, VT, N1, ShAmt);
 637       }
 638       break;
 639
 640     case ISD::UDIV:
 641       // FIXME: This should only be done if the target supports shift
 642       // operations.
 643       if ((C2 & C2-1) == 0 && C2) {
 644         SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
 645         return getNode(ISD::SRL, VT, N1, ShAmt);
 646       }
 647       break;
 648
 649     case ISD::SHL:
 650     case ISD::SRL:
 651     case ISD::SRA:
 652       if (C2 == 0) return N1;
 653       break;
 654
 655     case ISD::AND:
 656       if (!C2) return N2;         // X and 0 -> 0
 657       if (N2C->isAllOnesValue())
 658         return N1;                // X and -1 -> X
 659       break;
 660     case ISD::OR:
 661       if (!C2)return N1;          // X or 0 -> X
 662       if (N2C->isAllOnesValue())
 663         return N2;                // X or -1 -> -1
 664       break;
 665     case ISD::XOR:
 666       if (!C2) return N1;        // X xor 0 -> X
 667       if (N2C->isAllOnesValue()) {
 668         if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){
 669           // !(X op Y) -> (X !op Y)
 670           bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
 671           return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger),
 672                           SetCC->getValueType(0),
 673                           SetCC->getOperand(0), SetCC->getOperand(1));
 674         } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) {
 675           SDNode *Op = N1.Val;
 676           // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible
 677           // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible
 678           SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1);
 679           if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
 680             LHS = getNode(ISD::XOR, VT, LHS, N2);  // RHS = ~LHS
 681             RHS = getNode(ISD::XOR, VT, RHS, N2);  // RHS = ~RHS
 682             if (Op->getOpcode() == ISD::AND)
 683               return getNode(ISD::OR, VT, LHS, RHS);
 684             return getNode(ISD::AND, VT, LHS, RHS);
 685           }
 686         }
 687         // X xor -1 -> not(x)  ?
 688       }
 689       break;
 690     }
 691
 692     // Reassociate ((X op C1) op C2) if possible.
 693     if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode))
 694       if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1)))
 695         return getNode(Opcode, VT, N1.Val->getOperand(0),
 696                        getNode(Opcode, VT, N2, N1.Val->getOperand(1)));
 697   }
 698
 699   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
 700   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
 701   if (N1CFP)
 702     if (N2CFP) {
 703       double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
 704       switch (Opcode) {
 705       case ISD::ADD: return getConstantFP(C1 + C2, VT);
 706       case ISD::SUB: return getConstantFP(C1 - C2, VT);
 707       case ISD::MUL: return getConstantFP(C1 * C2, VT);
 708       case ISD::SDIV:
 709         if (C2) return getConstantFP(C1 / C2, VT);
 710         break;
 711       case ISD::SREM :
 712         if (C2) return getConstantFP(fmod(C1, C2), VT);
 713         break;
 714       default: break;
 715       }
 716
 717     } else {      // Cannonicalize constant to RHS if commutative
 718       if (isCommutativeBinOp(Opcode)) {
 719         std::swap(N1CFP, N2CFP);
 720         std::swap(N1, N2);
 721       }
 722     }
 723
 724   // Finally, fold operations that do not require constants.
 725   switch (Opcode) {
 726   case ISD::AND:
 727   case ISD::OR:
 728     if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val))
 729       if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) {
 730         SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0);
 731         SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1);
 732         ISD::CondCode Op2 = RHS->getCondition();
 733
 734         // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y)
 735         if (LL == RR && LR == RL) {
 736           Op2 = ISD::getSetCCSwappedOperands(Op2);
 737           goto MatchedBackwards;
 738         }
 739
 740         if (LL == RL && LR == RR) {
 741         MatchedBackwards:
 742           ISD::CondCode Result;
 743           bool isInteger = MVT::isInteger(LL.getValueType());
 744           if (Opcode == ISD::OR)
 745             Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2,
 746                                               isInteger);
 747           else
 748             Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2,
 749                                                isInteger);
 750           if (Result != ISD::SETCC_INVALID)
 751             return getSetCC(Result, LHS->getValueType(0), LL, LR);
 752         }
 753       }
 754     break;
 755   case ISD::XOR:
 756     if (N1 == N2) return getConstant(0, VT);  // xor X, Y -> 0
 757     break;
 758   case ISD::SUB:
 759     if (N1.getOpcode() == ISD::ADD) {
 760       if (N1.Val->getOperand(0) == N2)
 761         return N1.Val->getOperand(1);         // (A+B)-A == B
 762       if (N1.Val->getOperand(1) == N2)
 763         return N1.Val->getOperand(0);         // (A+B)-B == A
 764     }
 765     break;
 766   }
 767
 768   SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
 769   if (N) return SDOperand(N, 0);
 770   N = new SDNode(Opcode, N1, N2);
 771   N->setValueTypes(VT);
 772
 773   AllNodes.push_back(N);
 774   return SDOperand(N, 0);
 775 }
 776
 777 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
 778                                 SDOperand Chain, SDOperand Ptr) {
 779   SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
 780   if (N) return SDOperand(N, 0);
 781   N = new SDNode(ISD::LOAD, Chain, Ptr);
 782
 783   // Loads have a token chain.
 784   N->setValueTypes(VT, MVT::Other);
 785   AllNodes.push_back(N);
 786   return SDOperand(N, 0);
 787 }
 788
 789
 790 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 791                                 SDOperand N1, SDOperand N2, SDOperand N3) {
 792   // Perform various simplifications.
 793   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 794   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
 795   ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
 796   switch (Opcode) {
 797   case ISD::SELECT:
 798     if (N1C)
 799       if (N1C->getValue())
 800         return N2;             // select true, X, Y -> X
 801       else
 802         return N3;             // select false, X, Y -> Y
 803
 804     if (N2 == N3) return N2;   // select C, X, X -> X
 805
 806     if (VT == MVT::i1) {  // Boolean SELECT
 807       if (N2C) {
 808         if (N3C) {
 809           if (N2C->getValue()) // select C, 1, 0 -> C
 810             return N1;
 811           return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C
 812         }
 813
 814         if (N2C->getValue())   // select C, 1, X -> C | X
 815           return getNode(ISD::OR, VT, N1, N3);
 816         else                   // select C, 0, X -> ~C & X
 817           return getNode(ISD::AND, VT,
 818                          getNode(ISD::XOR, N1.getValueType(), N1,
 819                                  getConstant(1, N1.getValueType())), N3);
 820       } else if (N3C) {
 821         if (N3C->getValue())   // select C, X, 1 -> ~C | X
 822           return getNode(ISD::OR, VT,
 823                          getNode(ISD::XOR, N1.getValueType(), N1,
 824                                  getConstant(1, N1.getValueType())), N2);
 825         else                   // select C, X, 0 -> C & X
 826           return getNode(ISD::AND, VT, N1, N2);
 827       }
 828     }
 829
 830     break;
 831   case ISD::BRCOND:
 832     if (N2C)
 833       if (N2C->getValue()) // Unconditional branch
 834         return getNode(ISD::BR, MVT::Other, N1, N3);
 835       else
 836         return N1;         // Never-taken branch
 837     break;
 838   }
 839
 840   SDNode *N = new SDNode(Opcode, N1, N2, N3);
 841   switch (Opcode) {
 842   default:
 843     N->setValueTypes(VT);
 844     break;
 845   case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain
 846     N->setValueTypes(VT, MVT::Other);
 847     break;
 848   }
 849
 850   // FIXME: memoize NODES
 851   AllNodes.push_back(N);
 852   return SDOperand(N, 0);
 853 }
 854
 855 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 856                                 std::vector<SDOperand> &Children) {
 857   switch (Children.size()) {
 858   case 0: return getNode(Opcode, VT);
 859   case 1: return getNode(Opcode, VT, Children[0]);
 860   case 2: return getNode(Opcode, VT, Children[0], Children[1]);
 861   case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]);
 862   default:
 863     // FIXME: MEMOIZE!!
 864     SDNode *N = new SDNode(Opcode, Children);
 865     N->setValueTypes(VT);
 866     AllNodes.push_back(N);
 867     return SDOperand(N, 0);
 868   }
 869 }
 870
 871 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,SDOperand N1,
 872                                 MVT::ValueType EVT) {
 873
 874   switch (Opcode) {
 875   default: assert(0 && "Bad opcode for this accessor!");
 876   case ISD::FP_ROUND_INREG:
 877     assert(VT == N1.getValueType() && "Not an inreg round!");
 878     assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) &&
 879            "Cannot FP_ROUND_INREG integer types");
 880     if (EVT == VT) return N1;  // Not actually rounding
 881     assert(EVT < VT && "Not rounding down!");
 882     break;
 883   case ISD::ZERO_EXTEND_INREG:
 884   case ISD::SIGN_EXTEND_INREG:
 885     assert(VT == N1.getValueType() && "Not an inreg extend!");
 886     assert(MVT::isInteger(VT) && MVT::isInteger(EVT) &&
 887            "Cannot *_EXTEND_INREG FP types");
 888     if (EVT == VT) return N1;  // Not actually extending
 889     assert(EVT < VT && "Not extending!");
 890
 891     // If we are sign extending an extension, use the original source.
 892     if (N1.getOpcode() == ISD::ZERO_EXTEND_INREG ||
 893         N1.getOpcode() == ISD::SIGN_EXTEND_INREG) {
 894       if (N1.getOpcode() == Opcode &&
 895           cast<MVTSDNode>(N1)->getExtraValueType() <= EVT)
 896         return N1;
 897     }
 898
 899     break;
 900   }
 901
 902   EVTStruct NN;
 903   NN.Opcode = Opcode;
 904   NN.VT = VT;
 905   NN.EVT = EVT;
 906   NN.Ops.push_back(N1);
 907
 908   SDNode *&N = MVTSDNodes[NN];
 909   if (N) return SDOperand(N, 0);
 910   N = new MVTSDNode(Opcode, VT, N1, EVT);
 911   AllNodes.push_back(N);
 912   return SDOperand(N, 0);
 913 }
 914
 915 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,SDOperand N1,
 916                                 SDOperand N2, MVT::ValueType EVT) {
 917   switch (Opcode) {
 918   default:  assert(0 && "Bad opcode for this accessor!");
 919   case ISD::EXTLOAD:
 920   case ISD::SEXTLOAD:
 921   case ISD::ZEXTLOAD:
 922     // If they are asking for an extending loat from/to the same thing, return a
 923     // normal load.
 924     if (VT == EVT)
 925       return getNode(ISD::LOAD, VT, N1, N2);
 926     assert(EVT < VT && "Should only be an extending load, not truncating!");
 927     assert((Opcode == ISD::EXTLOAD || MVT::isInteger(VT)) &&
 928            "Cannot sign/zero extend a FP load!");
 929     assert(MVT::isInteger(VT) == MVT::isInteger(EVT) &&
 930            "Cannot convert from FP to Int or Int -> FP!");
 931     break;
 932   }
 933
 934   EVTStruct NN;
 935   NN.Opcode = Opcode;
 936   NN.VT = VT;
 937   NN.EVT = EVT;
 938   NN.Ops.push_back(N1);
 939   NN.Ops.push_back(N2);
 940
 941   SDNode *&N = MVTSDNodes[NN];
 942   if (N) return SDOperand(N, 0);
 943   N = new MVTSDNode(Opcode, VT, MVT::Other, N1, N2, EVT);
 944   AllNodes.push_back(N);
 945   return SDOperand(N, 0);
 946 }
 947
 948 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,SDOperand N1,
 949                                 SDOperand N2, SDOperand N3, MVT::ValueType EVT) {
 950   switch (Opcode) {
 951   default:  assert(0 && "Bad opcode for this accessor!");
 952   case ISD::TRUNCSTORE:
 953 #if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store
 954     // If this is a truncating store of a constant, convert to the desired type
 955     // and store it instead.
 956     if (isa<Constant>(N1)) {
 957       SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1);
 958       if (isa<Constant>(Op))
 959         N1 = Op;
 960     }
 961     // Also for ConstantFP?
 962 #endif
 963     if (N1.getValueType() == EVT)       // Normal store?
 964       return getNode(ISD::STORE, VT, N1, N2, N3);
 965     assert(N2.getValueType() > EVT && "Not a truncation?");
 966     assert(MVT::isInteger(N2.getValueType()) == MVT::isInteger(EVT) &&
 967            "Can't do FP-INT conversion!");
 968     break;
 969   }
 970
 971   EVTStruct NN;
 972   NN.Opcode = Opcode;
 973   NN.VT = VT;
 974   NN.EVT = EVT;
 975   NN.Ops.push_back(N1);
 976   NN.Ops.push_back(N2);
 977   NN.Ops.push_back(N3);
 978
 979   SDNode *&N = MVTSDNodes[NN];
 980   if (N) return SDOperand(N, 0);
 981   N = new MVTSDNode(Opcode, VT, N1, N2, N3, EVT);
 982   AllNodes.push_back(N);
 983   return SDOperand(N, 0);
 984 }
 985
 986
 987 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the
 988 /// indicated value.  This method ignores uses of other values defined by this
 989 /// operation.
 990 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) {
 991   assert(Value < getNumValues() && "Bad value!");
 992
 993   // If there is only one value, this is easy.
 994   if (getNumValues() == 1)
 995     return use_size() == NUses;
 996   if (Uses.size() < NUses) return false;
 997
 998   SDOperand TheValue(this, Value);
 999
1000   std::set<SDNode*> UsersHandled;
1001
1002   for (std::vector<SDNode*>::iterator UI = Uses.begin(), E = Uses.end();
1003        UI != E; ++UI) {
1004     SDNode *User = *UI;
1005     if (User->getNumOperands() == 1 ||
1006         UsersHandled.insert(User).second)     // First time we've seen this?
1007       for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i)
1008         if (User->getOperand(i) == TheValue) {
1009           if (NUses == 0)
1010             return false;   // too many uses
1011           --NUses;
1012         }
1013   }
1014
1015   // Found exactly the right number of uses?
1016   return NUses == 0;
1017 }
1018
1019
1020 const char *SDNode::getOperationName() const {
1021   switch (getOpcode()) {
1022   default: return "<<Unknown>>";
1023   case ISD::EntryToken:    return "EntryToken";
1024   case ISD::TokenFactor:   return "TokenFactor";
1025   case ISD::Constant:      return "Constant";
1026   case ISD::ConstantFP:    return "ConstantFP";
1027   case ISD::GlobalAddress: return "GlobalAddress";
1028   case ISD::FrameIndex:    return "FrameIndex";
1029   case ISD::BasicBlock:    return "BasicBlock";
1030   case ISD::ExternalSymbol: return "ExternalSymbol";
1031   case ISD::ConstantPool:  return "ConstantPoolIndex";
1032   case ISD::CopyToReg:     return "CopyToReg";
1033   case ISD::CopyFromReg:   return "CopyFromReg";
1034   case ISD::ImplicitDef:   return "ImplicitDef";
1035
1036   case ISD::ADD:    return "add";
1037   case ISD::SUB:    return "sub";
1038   case ISD::MUL:    return "mul";
1039   case ISD::SDIV:   return "sdiv";
1040   case ISD::UDIV:   return "udiv";
1041   case ISD::SREM:   return "srem";
1042   case ISD::UREM:   return "urem";
1043   case ISD::AND:    return "and";
1044   case ISD::OR:     return "or";
1045   case ISD::XOR:    return "xor";
1046   case ISD::SHL:    return "shl";
1047   case ISD::SRA:    return "sra";
1048   case ISD::SRL:    return "srl";
1049
1050   case ISD::SELECT: return "select";
1051   case ISD::ADDC:   return "addc";
1052   case ISD::SUBB:   return "subb";
1053
1054     // Conversion operators.
1055   case ISD::SIGN_EXTEND: return "sign_extend";
1056   case ISD::ZERO_EXTEND: return "zero_extend";
1057   case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg";
1058   case ISD::ZERO_EXTEND_INREG: return "zero_extend_inreg";
1059   case ISD::TRUNCATE:    return "truncate";
1060   case ISD::FP_ROUND:    return "fp_round";
1061   case ISD::FP_ROUND_INREG: return "fp_round_inreg";
1062   case ISD::FP_EXTEND:   return "fp_extend";
1063
1064   case ISD::SINT_TO_FP:  return "sint_to_fp";
1065   case ISD::UINT_TO_FP:  return "uint_to_fp";
1066   case ISD::FP_TO_SINT:  return "fp_to_sint";
1067   case ISD::FP_TO_UINT:  return "fp_to_uint";
1068
1069     // Control flow instructions
1070   case ISD::BR:      return "br";
1071   case ISD::BRCOND:  return "brcond";
1072   case ISD::RET:     return "ret";
1073   case ISD::CALL:    return "call";
1074   case ISD::ADJCALLSTACKDOWN:  return "adjcallstackdown";
1075   case ISD::ADJCALLSTACKUP:    return "adjcallstackup";
1076
1077     // Other operators
1078   case ISD::LOAD:    return "load";
1079   case ISD::STORE:   return "store";
1080   case ISD::EXTLOAD:    return "extload";
1081   case ISD::SEXTLOAD:   return "sextload";
1082   case ISD::ZEXTLOAD:   return "zextload";
1083   case ISD::TRUNCSTORE: return "truncstore";
1084
1085   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
1086   case ISD::EXTRACT_ELEMENT: return "extract_element";
1087   case ISD::BUILD_PAIR: return "build_pair";
1088   case ISD::MEMSET:  return "memset";
1089   case ISD::MEMCPY:  return "memcpy";
1090   case ISD::MEMMOVE: return "memmove";
1091
1092   case ISD::SETCC:
1093     const SetCCSDNode *SetCC = cast<SetCCSDNode>(this);
1094     switch (SetCC->getCondition()) {
1095     default: assert(0 && "Unknown setcc condition!");
1096     case ISD::SETOEQ:  return "setcc:setoeq";
1097     case ISD::SETOGT:  return "setcc:setogt";
1098     case ISD::SETOGE:  return "setcc:setoge";
1099     case ISD::SETOLT:  return "setcc:setolt";
1100     case ISD::SETOLE:  return "setcc:setole";
1101     case ISD::SETONE:  return "setcc:setone";
1102
1103     case ISD::SETO:    return "setcc:seto";
1104     case ISD::SETUO:   return "setcc:setuo";
1105     case ISD::SETUEQ:  return "setcc:setue";
1106     case ISD::SETUGT:  return "setcc:setugt";
1107     case ISD::SETUGE:  return "setcc:setuge";
1108     case ISD::SETULT:  return "setcc:setult";
1109     case ISD::SETULE:  return "setcc:setule";
1110     case ISD::SETUNE:  return "setcc:setune";
1111
1112     case ISD::SETEQ:   return "setcc:seteq";
1113     case ISD::SETGT:   return "setcc:setgt";
1114     case ISD::SETGE:   return "setcc:setge";
1115     case ISD::SETLT:   return "setcc:setlt";
1116     case ISD::SETLE:   return "setcc:setle";
1117     case ISD::SETNE:   return "setcc:setne";
1118     }
1119   }
1120 }
1121
1122 void SDNode::dump() const {
1123   std::cerr << (void*)this << ": ";
1124
1125   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
1126     if (i) std::cerr << ",";
1127     if (getValueType(i) == MVT::Other)
1128       std::cerr << "ch";
1129     else
1130       std::cerr << MVT::getValueTypeString(getValueType(i));
1131   }
1132   std::cerr << " = " << getOperationName();
1133
1134   std::cerr << " ";
1135   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1136     if (i) std::cerr << ", ";
1137     std::cerr << (void*)getOperand(i).Val;
1138     if (unsigned RN = getOperand(i).ResNo)
1139       std::cerr << ":" << RN;
1140   }
1141
1142   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
1143     std::cerr << "<" << CSDN->getValue() << ">";
1144   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
1145     std::cerr << "<" << CSDN->getValue() << ">";
1146   } else if (const GlobalAddressSDNode *GADN =
1147              dyn_cast<GlobalAddressSDNode>(this)) {
1148     std::cerr << "<";
1149     WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
1150   } else if (const FrameIndexSDNode *FIDN =
1151              dyn_cast<FrameIndexSDNode>(this)) {
1152     std::cerr << "<" << FIDN->getIndex() << ">";
1153   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
1154     std::cerr << "<" << CP->getIndex() << ">";
1155   } else if (const BasicBlockSDNode *BBDN =
1156              dyn_cast<BasicBlockSDNode>(this)) {
1157     std::cerr << "<";
1158     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
1159     if (LBB)
1160       std::cerr << LBB->getName() << " ";
1161     std::cerr << (const void*)BBDN->getBasicBlock() << ">";
1162   } else if (const RegSDNode *C2V = dyn_cast<RegSDNode>(this)) {
1163     std::cerr << "<reg #" << C2V->getReg() << ">";
1164   } else if (const ExternalSymbolSDNode *ES =
1165              dyn_cast<ExternalSymbolSDNode>(this)) {
1166     std::cerr << "'" << ES->getSymbol() << "'";
1167   } else if (const MVTSDNode *M = dyn_cast<MVTSDNode>(this)) {
1168     std::cerr << " - Ty = " << MVT::getValueTypeString(M->getExtraValueType());
1169   }
1170 }
1171
1172 static void DumpNodes(SDNode *N, unsigned indent) {
1173   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
1174     if (N->getOperand(i).Val->hasOneUse())
1175       DumpNodes(N->getOperand(i).Val, indent+2);
1176     else
1177       std::cerr << "\n" << std::string(indent+2, ' ')
1178                 << (void*)N->getOperand(i).Val << ": <multiple use>";
1179
1180
1181   std::cerr << "\n" << std::string(indent, ' ');
1182   N->dump();
1183 }
1184
1185 void SelectionDAG::dump() const {
1186   std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
1187   std::vector<SDNode*> Nodes(AllNodes);
1188   std::sort(Nodes.begin(), Nodes.end());
1189
1190   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
1191     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
1192       DumpNodes(Nodes[i], 2);
1193   }
1194
1195   DumpNodes(getRoot().Val, 2);
1196
1197   std::cerr << "\n\n";
1198 }
1199