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   default:
 224     if (N->getNumOperands() == 1)
 225       UnaryOps.erase(std::make_pair(N->getOpcode(),
 226                                     std::make_pair(N->getOperand(0),
 227                                                    N->getValueType(0))));
 228     else if (N->getNumOperands() == 2)
 229       BinaryOps.erase(std::make_pair(N->getOpcode(),
 230                                      std::make_pair(N->getOperand(0),
 231                                                     N->getOperand(1))));
 232     break;
 233   }
 234
 235   // Next, brutally remove the operand list.
 236   while (!N->Operands.empty()) {
 237     SDNode *O = N->Operands.back().Val;
 238     N->Operands.pop_back();
 239     O->removeUser(N);
 240
 241     // Now that we removed this operand, see if there are no uses of it left.
 242     DeleteNodeIfDead(O, NodeSet);
 243   }
 244
 245   // Remove the node from the nodes set and delete it.
 246   std::set<SDNode*> &AllNodeSet = *(std::set<SDNode*>*)NodeSet;
 247   AllNodeSet.erase(N);
 248
 249   // Now that the node is gone, check to see if any of the operands of this node
 250   // are dead now.
 251   delete N;
 252 }
 253
 254
 255 SelectionDAG::~SelectionDAG() {
 256   for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
 257     delete AllNodes[i];
 258 }
 259
 260 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) {
 261   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 262   // Mask out any bits that are not valid for this constant.
 263   if (VT != MVT::i64)
 264     Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1;
 265
 266   SDNode *&N = Constants[std::make_pair(Val, VT)];
 267   if (N) return SDOperand(N, 0);
 268   N = new ConstantSDNode(Val, VT);
 269   AllNodes.push_back(N);
 270   return SDOperand(N, 0);
 271 }
 272
 273 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
 274   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
 275   if (VT == MVT::f32)
 276     Val = (float)Val;  // Mask out extra precision.
 277
 278   SDNode *&N = ConstantFPs[std::make_pair(Val, VT)];
 279   if (N) return SDOperand(N, 0);
 280   N = new ConstantFPSDNode(Val, VT);
 281   AllNodes.push_back(N);
 282   return SDOperand(N, 0);
 283 }
 284
 285
 286
 287 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 288                                          MVT::ValueType VT) {
 289   SDNode *&N = GlobalValues[GV];
 290   if (N) return SDOperand(N, 0);
 291   N = new GlobalAddressSDNode(GV,VT);
 292   AllNodes.push_back(N);
 293   return SDOperand(N, 0);
 294 }
 295
 296 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) {
 297   SDNode *&N = FrameIndices[FI];
 298   if (N) return SDOperand(N, 0);
 299   N = new FrameIndexSDNode(FI, VT);
 300   AllNodes.push_back(N);
 301   return SDOperand(N, 0);
 302 }
 303
 304 SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) {
 305   SDNode *N = ConstantPoolIndices[CPIdx];
 306   if (N) return SDOperand(N, 0);
 307   N = new ConstantPoolSDNode(CPIdx, VT);
 308   AllNodes.push_back(N);
 309   return SDOperand(N, 0);
 310 }
 311
 312 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
 313   SDNode *&N = BBNodes[MBB];
 314   if (N) return SDOperand(N, 0);
 315   N = new BasicBlockSDNode(MBB);
 316   AllNodes.push_back(N);
 317   return SDOperand(N, 0);
 318 }
 319
 320 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
 321   SDNode *&N = ExternalSymbols[Sym];
 322   if (N) return SDOperand(N, 0);
 323   N = new ExternalSymbolSDNode(Sym, VT);
 324   AllNodes.push_back(N);
 325   return SDOperand(N, 0);
 326 }
 327
 328 SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, SDOperand N1,
 329                                  SDOperand N2) {
 330   // These setcc operations always fold.
 331   switch (Cond) {
 332   default: break;
 333   case ISD::SETFALSE:
 334   case ISD::SETFALSE2: return getConstant(0, MVT::i1);
 335   case ISD::SETTRUE:
 336   case ISD::SETTRUE2:  return getConstant(1, MVT::i1);
 337   }
 338
 339   if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val))
 340     if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
 341       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
 342
 343       // Sign extend the operands if required
 344       if (ISD::isSignedIntSetCC(Cond)) {
 345         C1 = N1C->getSignExtended();
 346         C2 = N2C->getSignExtended();
 347       }
 348
 349       switch (Cond) {
 350       default: assert(0 && "Unknown integer setcc!");
 351       case ISD::SETEQ:  return getConstant(C1 == C2, MVT::i1);
 352       case ISD::SETNE:  return getConstant(C1 != C2, MVT::i1);
 353       case ISD::SETULT: return getConstant(C1 <  C2, MVT::i1);
 354       case ISD::SETUGT: return getConstant(C1 >  C2, MVT::i1);
 355       case ISD::SETULE: return getConstant(C1 <= C2, MVT::i1);
 356       case ISD::SETUGE: return getConstant(C1 >= C2, MVT::i1);
 357       case ISD::SETLT:  return getConstant((int64_t)C1 <  (int64_t)C2, MVT::i1);
 358       case ISD::SETGT:  return getConstant((int64_t)C1 >  (int64_t)C2, MVT::i1);
 359       case ISD::SETLE:  return getConstant((int64_t)C1 <= (int64_t)C2, MVT::i1);
 360       case ISD::SETGE:  return getConstant((int64_t)C1 >= (int64_t)C2, MVT::i1);
 361       }
 362     } else {
 363       // Ensure that the constant occurs on the RHS.
 364       Cond = ISD::getSetCCSwappedOperands(Cond);
 365       std::swap(N1, N2);
 366     }
 367
 368   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
 369     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
 370       double C1 = N1C->getValue(), C2 = N2C->getValue();
 371
 372       switch (Cond) {
 373       default: break; // FIXME: Implement the rest of these!
 374       case ISD::SETEQ:  return getConstant(C1 == C2, MVT::i1);
 375       case ISD::SETNE:  return getConstant(C1 != C2, MVT::i1);
 376       case ISD::SETLT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 377       case ISD::SETGT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 378       case ISD::SETLE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 379       case ISD::SETGE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 380       }
 381     } else {
 382       // Ensure that the constant occurs on the RHS.
 383       Cond = ISD::getSetCCSwappedOperands(Cond);
 384       std::swap(N1, N2);
 385     }
 386
 387   if (N1 == N2) {
 388     // We can always fold X == Y for integer setcc's.
 389     if (MVT::isInteger(N1.getValueType()))
 390       return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1);
 391     unsigned UOF = ISD::getUnorderedFlavor(Cond);
 392     if (UOF == 2)   // FP operators that are undefined on NaNs.
 393       return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1);
 394     if (UOF == ISD::isTrueWhenEqual(Cond))
 395       return getConstant(UOF, MVT::i1);
 396     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
 397     // if it is not already.
 398     Cond = UOF == 0 ? ISD::SETUO : ISD::SETO;
 399   }
 400
 401   if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
 402       MVT::isInteger(N1.getValueType())) {
 403     if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB ||
 404         N1.getOpcode() == ISD::XOR) {
 405       // Simplify (X+Y) == (X+Z) -->  Y == Z
 406       if (N1.getOpcode() == N2.getOpcode()) {
 407         if (N1.getOperand(0) == N2.getOperand(0))
 408           return getSetCC(Cond, N1.getOperand(1), N2.getOperand(1));
 409         if (N1.getOperand(1) == N2.getOperand(1))
 410           return getSetCC(Cond, N1.getOperand(0), N2.getOperand(0));
 411         if (isCommutativeBinOp(N1.getOpcode())) {
 412           // If X op Y == Y op X, try other combinations.
 413           if (N1.getOperand(0) == N2.getOperand(1))
 414             return getSetCC(Cond, N1.getOperand(1), N2.getOperand(0));
 415           if (N1.getOperand(1) == N2.getOperand(0))
 416             return getSetCC(Cond, N1.getOperand(1), N2.getOperand(1));
 417         }
 418       }
 419
 420       // Simplify (X+Z) == X -->  Z == 0
 421       if (N1.getOperand(0) == N2)
 422         return getSetCC(Cond, N1.getOperand(1),
 423                         getConstant(0, N1.getValueType()));
 424       if (N1.getOperand(1) == N2) {
 425         if (isCommutativeBinOp(N1.getOpcode()))
 426           return getSetCC(Cond, N1.getOperand(0),
 427                           getConstant(0, N1.getValueType()));
 428         else {
 429           assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!");
 430           // (Z-X) == X  --> Z == X<<1
 431           return getSetCC(Cond, N1.getOperand(0),
 432                           getNode(ISD::SHL, N2.getValueType(),
 433                                   N2, getConstant(1, MVT::i8)));
 434         }
 435       }
 436     }
 437
 438     if (N2.getOpcode() == ISD::ADD || N2.getOpcode() == ISD::SUB ||
 439         N2.getOpcode() == ISD::XOR) {
 440       // Simplify  X == (X+Z) -->  Z == 0
 441       if (N2.getOperand(0) == N1)
 442         return getSetCC(Cond, N2.getOperand(1),
 443                         getConstant(0, N2.getValueType()));
 444       else if (N2.getOperand(1) == N1)
 445         return getSetCC(Cond, N2.getOperand(0),
 446                         getConstant(0, N2.getValueType()));
 447     }
 448   }
 449
 450   SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), Cond)];
 451   if (N) return SDOperand(N, 0);
 452   N = new SetCCSDNode(Cond, N1, N2);
 453   AllNodes.push_back(N);
 454   return SDOperand(N, 0);
 455 }
 456
 457
 458
 459 /// getNode - Gets or creates the specified node.
 460 ///
 461 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
 462   SDNode *N = new SDNode(Opcode, VT);
 463   AllNodes.push_back(N);
 464   return SDOperand(N, 0);
 465 }
 466
 467 static const Type *getTypeFor(MVT::ValueType VT) {
 468   switch (VT) {
 469   default: assert(0 && "Unknown MVT!");
 470   case MVT::i1: return Type::BoolTy;
 471   case MVT::i8: return Type::UByteTy;
 472   case MVT::i16: return Type::UShortTy;
 473   case MVT::i32: return Type::UIntTy;
 474   case MVT::i64: return Type::ULongTy;
 475   case MVT::f32: return Type::FloatTy;
 476   case MVT::f64: return Type::DoubleTy;
 477   }
 478 }
 479
 480 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 481                                 SDOperand Operand) {
 482   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
 483     uint64_t Val = C->getValue();
 484     switch (Opcode) {
 485     default: break;
 486     case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
 487     case ISD::ZERO_EXTEND: return getConstant(Val, VT);
 488     case ISD::TRUNCATE:    return getConstant(Val, VT);
 489     case ISD::SINT_TO_FP:  return getConstantFP(C->getSignExtended(), VT);
 490     case ISD::UINT_TO_FP:  return getConstantFP(C->getValue(), VT);
 491     }
 492   }
 493
 494   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
 495     switch (Opcode) {
 496     case ISD::FP_ROUND:
 497     case ISD::FP_EXTEND:
 498       return getConstantFP(C->getValue(), VT);
 499     case ISD::FP_TO_SINT:
 500       return getConstant((int64_t)C->getValue(), VT);
 501     case ISD::FP_TO_UINT:
 502       return getConstant((uint64_t)C->getValue(), VT);
 503     }
 504
 505   unsigned OpOpcode = Operand.Val->getOpcode();
 506   switch (Opcode) {
 507   case ISD::SIGN_EXTEND:
 508     if (Operand.getValueType() == VT) return Operand;   // noop extension
 509     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
 510       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 511     break;
 512   case ISD::ZERO_EXTEND:
 513     if (Operand.getValueType() == VT) return Operand;   // noop extension
 514     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
 515       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 516     break;
 517   case ISD::TRUNCATE:
 518     if (Operand.getValueType() == VT) return Operand;   // noop truncate
 519     if (OpOpcode == ISD::TRUNCATE)
 520       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
 521     else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) {
 522       // If the source is smaller than the dest, we still need an extend.
 523       if (Operand.Val->getOperand(0).getValueType() < VT)
 524         return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 525       else if (Operand.Val->getOperand(0).getValueType() > VT)
 526         return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
 527       else
 528         return Operand.Val->getOperand(0);
 529     }
 530     break;
 531   }
 532
 533   SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
 534   if (N) return SDOperand(N, 0);
 535   N = new SDNode(Opcode, Operand);
 536   N->setValueTypes(VT);
 537   AllNodes.push_back(N);
 538   return SDOperand(N, 0);
 539 }
 540
 541 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 542                                 SDOperand N1, SDOperand N2) {
 543   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 544   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
 545   if (N1C) {
 546     if (N2C) {
 547       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
 548       switch (Opcode) {
 549       case ISD::ADD: return getConstant(C1 + C2, VT);
 550       case ISD::SUB: return getConstant(C1 - C2, VT);
 551       case ISD::MUL: return getConstant(C1 * C2, VT);
 552       case ISD::UDIV:
 553         if (C2) return getConstant(C1 / C2, VT);
 554         break;
 555       case ISD::UREM :
 556         if (C2) return getConstant(C1 % C2, VT);
 557         break;
 558       case ISD::SDIV :
 559         if (C2) return getConstant(N1C->getSignExtended() /
 560                                    N2C->getSignExtended(), VT);
 561         break;
 562       case ISD::SREM :
 563         if (C2) return getConstant(N1C->getSignExtended() %
 564                                    N2C->getSignExtended(), VT);
 565         break;
 566       case ISD::AND  : return getConstant(C1 & C2, VT);
 567       case ISD::OR   : return getConstant(C1 | C2, VT);
 568       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
 569       case ISD::SHL  : return getConstant(C1 << (int)C2, VT);
 570       case ISD::SRL  : return getConstant(C1 >> (unsigned)C2, VT);
 571       case ISD::SRA  : return getConstant(N1C->getSignExtended() >>(int)C2, VT);
 572       default: break;
 573       }
 574
 575     } else {      // Cannonicalize constant to RHS if commutative
 576       if (isCommutativeBinOp(Opcode)) {
 577         std::swap(N1C, N2C);
 578         std::swap(N1, N2);
 579       }
 580     }
 581   }
 582
 583   if (N2C) {
 584     uint64_t C2 = N2C->getValue();
 585
 586     switch (Opcode) {
 587     case ISD::ADD:
 588       if (!C2) return N1;         // add X, 0 -> X
 589       break;
 590     case ISD::SUB:
 591       if (!C2) return N1;         // sub X, 0 -> X
 592       break;
 593     case ISD::MUL:
 594       if (!C2) return N2;         // mul X, 0 -> 0
 595       if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X
 596         return getNode(ISD::SUB, VT, getConstant(0, VT), N1);
 597
 598       // FIXME: This should only be done if the target supports shift
 599       // operations.
 600       if ((C2 & C2-1) == 0) {
 601         SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
 602         return getNode(ISD::SHL, VT, N1, ShAmt);
 603       }
 604       break;
 605
 606     case ISD::UDIV:
 607       // FIXME: This should only be done if the target supports shift
 608       // operations.
 609       if ((C2 & C2-1) == 0 && C2) {
 610         SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
 611         return getNode(ISD::SRL, VT, N1, ShAmt);
 612       }
 613       break;
 614
 615     case ISD::SHL:
 616     case ISD::SRL:
 617     case ISD::SRA:
 618       if (C2 == 0) return N1;
 619       break;
 620
 621     case ISD::AND:
 622       if (!C2) return N2;         // X and 0 -> 0
 623       if (N2C->isAllOnesValue())
 624         return N1;                // X and -1 -> X
 625       break;
 626     case ISD::OR:
 627       if (!C2)return N1;          // X or 0 -> X
 628       if (N2C->isAllOnesValue())
 629         return N2;                // X or -1 -> -1
 630       break;
 631     case ISD::XOR:
 632       if (!C2) return N1;        // X xor 0 -> X
 633       if (N2C->isAllOnesValue()) {
 634         if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){
 635           // !(X op Y) -> (X !op Y)
 636           bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
 637           return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger),
 638                           SetCC->getOperand(0), SetCC->getOperand(1));
 639         } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) {
 640           SDNode *Op = N1.Val;
 641           // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible
 642           // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible
 643           SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1);
 644           if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
 645             LHS = getNode(ISD::XOR, VT, LHS, N2);  // RHS = ~LHS
 646             RHS = getNode(ISD::XOR, VT, RHS, N2);  // RHS = ~RHS
 647             if (Op->getOpcode() == ISD::AND)
 648               return getNode(ISD::OR, VT, LHS, RHS);
 649             return getNode(ISD::AND, VT, LHS, RHS);
 650           }
 651         }
 652         // X xor -1 -> not(x)  ?
 653       }
 654       break;
 655     }
 656
 657     // Reassociate ((X op C1) op C2) if possible.
 658     if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode))
 659       if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1)))
 660         return getNode(Opcode, VT, N1.Val->getOperand(0),
 661                        getNode(Opcode, VT, N2, N1.Val->getOperand(1)));
 662   }
 663
 664   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
 665   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
 666   if (N1CFP)
 667     if (N2CFP) {
 668       double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
 669       switch (Opcode) {
 670       case ISD::ADD: return getConstantFP(C1 + C2, VT);
 671       case ISD::SUB: return getConstantFP(C1 - C2, VT);
 672       case ISD::MUL: return getConstantFP(C1 * C2, VT);
 673       case ISD::SDIV:
 674         if (C2) return getConstantFP(C1 / C2, VT);
 675         break;
 676       case ISD::SREM :
 677         if (C2) return getConstantFP(fmod(C1, C2), VT);
 678         break;
 679       default: break;
 680       }
 681
 682     } else {      // Cannonicalize constant to RHS if commutative
 683       if (isCommutativeBinOp(Opcode)) {
 684         std::swap(N1CFP, N2CFP);
 685         std::swap(N1, N2);
 686       }
 687     }
 688
 689   // Finally, fold operations that do not require constants.
 690   switch (Opcode) {
 691   case ISD::AND:
 692   case ISD::OR:
 693     if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val))
 694       if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) {
 695         SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0);
 696         SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1);
 697         ISD::CondCode Op2 = RHS->getCondition();
 698
 699         // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y)
 700         if (LL == RR && LR == RL) {
 701           Op2 = ISD::getSetCCSwappedOperands(Op2);
 702           goto MatchedBackwards;
 703         }
 704
 705         if (LL == RL && LR == RR) {
 706         MatchedBackwards:
 707           ISD::CondCode Result;
 708           bool isInteger = MVT::isInteger(LL.getValueType());
 709           if (Opcode == ISD::OR)
 710             Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2,
 711                                               isInteger);
 712           else
 713             Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2,
 714                                                isInteger);
 715           if (Result != ISD::SETCC_INVALID)
 716             return getSetCC(Result, LL, LR);
 717         }
 718       }
 719     break;
 720   case ISD::XOR:
 721     if (N1 == N2) return getConstant(0, VT);  // xor X, Y -> 0
 722     break;
 723   case ISD::SUB:
 724     if (N1.getOpcode() == ISD::ADD) {
 725       if (N1.Val->getOperand(0) == N2)
 726         return N1.Val->getOperand(1);         // (A+B)-A == B
 727       if (N1.Val->getOperand(1) == N2)
 728         return N1.Val->getOperand(0);         // (A+B)-B == A
 729     }
 730     break;
 731   }
 732
 733   SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
 734   if (N) return SDOperand(N, 0);
 735   N = new SDNode(Opcode, N1, N2);
 736   N->setValueTypes(VT);
 737
 738   AllNodes.push_back(N);
 739   return SDOperand(N, 0);
 740 }
 741
 742 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
 743                                 SDOperand Chain, SDOperand Ptr) {
 744   SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
 745   if (N) return SDOperand(N, 0);
 746   N = new SDNode(ISD::LOAD, Chain, Ptr);
 747
 748   // Loads have a token chain.
 749   N->setValueTypes(VT, MVT::Other);
 750   AllNodes.push_back(N);
 751   return SDOperand(N, 0);
 752 }
 753
 754
 755 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 756                                 SDOperand N1, SDOperand N2, SDOperand N3) {
 757   // Perform various simplifications.
 758   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 759   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
 760   ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
 761   switch (Opcode) {
 762   case ISD::SELECT:
 763     if (N1C)
 764       if (N1C->getValue())
 765         return N2;             // select true, X, Y -> X
 766       else
 767         return N3;             // select false, X, Y -> Y
 768
 769     if (N2 == N3) return N2;   // select C, X, X -> X
 770
 771     if (VT == MVT::i1) {  // Boolean SELECT
 772       if (N2C) {
 773         if (N3C) {
 774           if (N2C->getValue()) // select C, 1, 0 -> C
 775             return N1;
 776           return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C
 777         }
 778
 779         if (N2C->getValue())   // select C, 1, X -> C | X
 780           return getNode(ISD::OR, VT, N1, N3);
 781         else                   // select C, 0, X -> ~C & X
 782           return getNode(ISD::AND, VT,
 783                          getNode(ISD::XOR, N1.getValueType(), N1,
 784                                  getConstant(1, N1.getValueType())), N3);
 785       } else if (N3C) {
 786         if (N3C->getValue())   // select C, X, 1 -> ~C | X
 787           return getNode(ISD::OR, VT,
 788                          getNode(ISD::XOR, N1.getValueType(), N1,
 789                                  getConstant(1, N1.getValueType())), N2);
 790         else                   // select C, X, 0 -> C & X
 791           return getNode(ISD::AND, VT, N1, N2);
 792       }
 793     }
 794
 795     break;
 796   case ISD::BRCOND:
 797     if (N2C)
 798       if (N2C->getValue()) // Unconditional branch
 799         return getNode(ISD::BR, MVT::Other, N1, N3);
 800       else
 801         return N1;         // Never-taken branch
 802     break;
 803   }
 804
 805   SDNode *N = new SDNode(Opcode, N1, N2, N3);
 806   switch (Opcode) {
 807   default:
 808     N->setValueTypes(VT);
 809     break;
 810   case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain
 811     N->setValueTypes(VT, MVT::Other);
 812     break;
 813   }
 814
 815   // FIXME: memoize NODES
 816   AllNodes.push_back(N);
 817   return SDOperand(N, 0);
 818 }
 819
 820 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 821                                 std::vector<SDOperand> &Children) {
 822   switch (Children.size()) {
 823   case 0: return getNode(Opcode, VT);
 824   case 1: return getNode(Opcode, VT, Children[0]);
 825   case 2: return getNode(Opcode, VT, Children[0], Children[1]);
 826   case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]);
 827   default:
 828     // FIXME: MEMOIZE!!
 829     SDNode *N = new SDNode(Opcode, Children);
 830     N->setValueTypes(VT);
 831     AllNodes.push_back(N);
 832     return SDOperand(N, 0);
 833   }
 834 }
 835
 836 const char *SDNode::getOperationName() const {
 837   switch (getOpcode()) {
 838   default: return "<<Unknown>>";
 839   case ISD::EntryToken:    return "EntryToken";
 840   case ISD::Constant:      return "Constant";
 841   case ISD::ConstantFP:    return "ConstantFP";
 842   case ISD::GlobalAddress: return "GlobalAddress";
 843   case ISD::FrameIndex:    return "FrameIndex";
 844   case ISD::BasicBlock:    return "BasicBlock";
 845   case ISD::ExternalSymbol: return "ExternalSymbol";
 846   case ISD::ConstantPool:  return "ConstantPoolIndex";
 847   case ISD::CopyToReg:     return "CopyToReg";
 848   case ISD::CopyFromReg:   return "CopyFromReg";
 849
 850   case ISD::ADD:    return "add";
 851   case ISD::SUB:    return "sub";
 852   case ISD::MUL:    return "mul";
 853   case ISD::SDIV:   return "sdiv";
 854   case ISD::UDIV:   return "udiv";
 855   case ISD::SREM:   return "srem";
 856   case ISD::UREM:   return "urem";
 857   case ISD::AND:    return "and";
 858   case ISD::OR:     return "or";
 859   case ISD::XOR:    return "xor";
 860   case ISD::SHL:    return "shl";
 861   case ISD::SRA:    return "sra";
 862   case ISD::SRL:    return "srl";
 863
 864   case ISD::SELECT: return "select";
 865   case ISD::ADDC:   return "addc";
 866   case ISD::SUBB:   return "subb";
 867
 868     // Conversion operators.
 869   case ISD::SIGN_EXTEND: return "sign_extend";
 870   case ISD::ZERO_EXTEND: return "zero_extend";
 871   case ISD::TRUNCATE:    return "truncate";
 872   case ISD::FP_ROUND:    return "fp_round";
 873   case ISD::FP_EXTEND:   return "fp_extend";
 874
 875   case ISD::SINT_TO_FP:  return "sint_to_fp";
 876   case ISD::UINT_TO_FP:  return "uint_to_fp";
 877   case ISD::FP_TO_SINT:  return "fp_to_sint";
 878   case ISD::FP_TO_UINT:  return "fp_to_uint";
 879
 880     // Control flow instructions
 881   case ISD::BR:      return "br";
 882   case ISD::BRCOND:  return "brcond";
 883   case ISD::RET:     return "ret";
 884   case ISD::CALL:    return "call";
 885   case ISD::ADJCALLSTACKDOWN:  return "adjcallstackdown";
 886   case ISD::ADJCALLSTACKUP:    return "adjcallstackup";
 887
 888     // Other operators
 889   case ISD::LOAD:    return "load";
 890   case ISD::STORE:   return "store";
 891   case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc";
 892   case ISD::EXTRACT_ELEMENT: return "extract_element";
 893   case ISD::BUILD_PAIR: return "build_pair";
 894   case ISD::MEMSET:  return "memset";
 895   case ISD::MEMCPY:  return "memcpy";
 896   case ISD::MEMMOVE: return "memmove";
 897
 898   case ISD::SETCC:
 899     const SetCCSDNode *SetCC = cast<SetCCSDNode>(this);
 900     switch (SetCC->getCondition()) {
 901     default: assert(0 && "Unknown setcc condition!");
 902     case ISD::SETOEQ:  return "setcc:setoeq";
 903     case ISD::SETOGT:  return "setcc:setogt";
 904     case ISD::SETOGE:  return "setcc:setoge";
 905     case ISD::SETOLT:  return "setcc:setolt";
 906     case ISD::SETOLE:  return "setcc:setole";
 907     case ISD::SETONE:  return "setcc:setone";
 908
 909     case ISD::SETO:    return "setcc:seto";
 910     case ISD::SETUO:   return "setcc:setuo";
 911     case ISD::SETUEQ:  return "setcc:setue";
 912     case ISD::SETUGT:  return "setcc:setugt";
 913     case ISD::SETUGE:  return "setcc:setuge";
 914     case ISD::SETULT:  return "setcc:setult";
 915     case ISD::SETULE:  return "setcc:setule";
 916     case ISD::SETUNE:  return "setcc:setune";
 917
 918     case ISD::SETEQ:   return "setcc:seteq";
 919     case ISD::SETGT:   return "setcc:setgt";
 920     case ISD::SETGE:   return "setcc:setge";
 921     case ISD::SETLT:   return "setcc:setlt";
 922     case ISD::SETLE:   return "setcc:setle";
 923     case ISD::SETNE:   return "setcc:setne";
 924     }
 925   }
 926 }
 927
 928 void SDNode::dump() const {
 929   std::cerr << (void*)this << ": ";
 930
 931   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
 932     if (i) std::cerr << ",";
 933     switch (getValueType(i)) {
 934     default: assert(0 && "Unknown value type!");
 935     case MVT::i1:    std::cerr << "i1"; break;
 936     case MVT::i8:    std::cerr << "i8"; break;
 937     case MVT::i16:   std::cerr << "i16"; break;
 938     case MVT::i32:   std::cerr << "i32"; break;
 939     case MVT::i64:   std::cerr << "i64"; break;
 940     case MVT::f32:   std::cerr << "f32"; break;
 941     case MVT::f64:   std::cerr << "f64"; break;
 942     case MVT::Other: std::cerr << "ch"; break;
 943     }
 944   }
 945   std::cerr << " = " << getOperationName();
 946
 947   std::cerr << " ";
 948   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 949     if (i) std::cerr << ", ";
 950     std::cerr << (void*)getOperand(i).Val;
 951     if (unsigned RN = getOperand(i).ResNo)
 952       std::cerr << ":" << RN;
 953   }
 954
 955   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
 956     std::cerr << "<" << CSDN->getValue() << ">";
 957   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
 958     std::cerr << "<" << CSDN->getValue() << ">";
 959   } else if (const GlobalAddressSDNode *GADN =
 960              dyn_cast<GlobalAddressSDNode>(this)) {
 961     std::cerr << "<";
 962     WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
 963   } else if (const FrameIndexSDNode *FIDN =
 964              dyn_cast<FrameIndexSDNode>(this)) {
 965     std::cerr << "<" << FIDN->getIndex() << ">";
 966   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
 967     std::cerr << "<" << CP->getIndex() << ">";
 968   } else if (const BasicBlockSDNode *BBDN =
 969              dyn_cast<BasicBlockSDNode>(this)) {
 970     std::cerr << "<";
 971     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
 972     if (LBB)
 973       std::cerr << LBB->getName() << " ";
 974     std::cerr << (const void*)BBDN->getBasicBlock() << ">";
 975   } else if (const CopyRegSDNode *C2V = dyn_cast<CopyRegSDNode>(this)) {
 976     std::cerr << "<reg #" << C2V->getReg() << ">";
 977   } else if (const ExternalSymbolSDNode *ES =
 978              dyn_cast<ExternalSymbolSDNode>(this)) {
 979     std::cerr << "'" << ES->getSymbol() << "'";
 980   }
 981 }
 982
 983 static void DumpNodes(SDNode *N, unsigned indent) {
 984   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 985     if (N->getOperand(i).Val->hasOneUse())
 986       DumpNodes(N->getOperand(i).Val, indent+2);
 987     else
 988       std::cerr << "\n" << std::string(indent+2, ' ')
 989                 << (void*)N->getOperand(i).Val << ": <multiple use>";
 990
 991
 992   std::cerr << "\n" << std::string(indent, ' ');
 993   N->dump();
 994 }
 995
 996 void SelectionDAG::dump() const {
 997   std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
 998   std::vector<SDNode*> Nodes(AllNodes);
 999   std::sort(Nodes.begin(), Nodes.end());
1000
1001   for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
1002     if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val)
1003       DumpNodes(Nodes[i], 2);
1004   }
1005
1006   DumpNodes(getRoot().Val, 2);
1007
1008   std::cerr << "\n\n";
1009 }
1010