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 <cmath>
  21 using namespace llvm;
  22
  23 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X)
  24 /// when given the operation for (X op Y).
  25 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) {
  26   // To perform this operation, we just need to swap the L and G bits of the
  27   // operation.
  28   unsigned OldL = (Operation >> 2) & 1;
  29   unsigned OldG = (Operation >> 1) & 1;
  30   return ISD::CondCode((Operation & ~6) |  // Keep the N, U, E bits
  31                        (OldL << 1) |       // New G bit
  32                        (OldG << 2));        // New L bit.
  33 }
  34
  35 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where
  36 /// 'op' is a valid SetCC operation.
  37 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) {
  38   unsigned Operation = Op;
  39   if (isInteger)
  40     Operation ^= 7;   // Flip L, G, E bits, but not U.
  41   else
  42     Operation ^= 15;  // Flip all of the condition bits.
  43   if (Operation > ISD::SETTRUE2)
  44     Operation &= ~8;     // Don't let N and U bits get set.
  45   return ISD::CondCode(Operation);
  46 }
  47
  48
  49 /// isSignedOp - For an integer comparison, return 1 if the comparison is a
  50 /// signed operation and 2 if the result is an unsigned comparison.  Return zero
  51 /// if the operation does not depend on the sign of the input (setne and seteq).
  52 static int isSignedOp(ISD::CondCode Opcode) {
  53   switch (Opcode) {
  54   default: assert(0 && "Illegal integer setcc operation!");
  55   case ISD::SETEQ:
  56   case ISD::SETNE: return 0;
  57   case ISD::SETLT:
  58   case ISD::SETLE:
  59   case ISD::SETGT:
  60   case ISD::SETGE: return 1;
  61   case ISD::SETULT:
  62   case ISD::SETULE:
  63   case ISD::SETUGT:
  64   case ISD::SETUGE: return 2;
  65   }
  66 }
  67
  68 /// getSetCCOrOperation - Return the result of a logical OR between different
  69 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)).  This function
  70 /// returns SETCC_INVALID if it is not possible to represent the resultant
  71 /// comparison.
  72 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2,
  73                                        bool isInteger) {
  74   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
  75     // Cannot fold a signed integer setcc with an unsigned integer setcc.
  76     return ISD::SETCC_INVALID;
  77
  78   unsigned Op = Op1 | Op2;  // Combine all of the condition bits.
  79
  80   // If the N and U bits get set then the resultant comparison DOES suddenly
  81   // care about orderedness, and is true when ordered.
  82   if (Op > ISD::SETTRUE2)
  83     Op &= ~16;     // Clear the N bit.
  84   return ISD::CondCode(Op);
  85 }
  86
  87 /// getSetCCAndOperation - Return the result of a logical AND between different
  88 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)).  This
  89 /// function returns zero if it is not possible to represent the resultant
  90 /// comparison.
  91 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2,
  92                                         bool isInteger) {
  93   if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3)
  94     // Cannot fold a signed setcc with an unsigned setcc.
  95     return ISD::SETCC_INVALID;
  96
  97   // Combine all of the condition bits.
  98   return ISD::CondCode(Op1 & Op2);
  99 }
 100
 101 SelectionDAG::~SelectionDAG() {
 102   for (unsigned i = 0, e = AllNodes.size(); i != e; ++i)
 103     delete AllNodes[i];
 104 }
 105
 106 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) {
 107   assert(MVT::isInteger(VT) && "Cannot create FP integer constant!");
 108   // Mask out any bits that are not valid for this constant.
 109   Val &= (1ULL << MVT::getSizeInBits(VT)) - 1;
 110
 111   SDNode *&N = Constants[std::make_pair(Val, VT)];
 112   if (N) return SDOperand(N, 0);
 113   N = new ConstantSDNode(Val, VT);
 114   AllNodes.push_back(N);
 115   return SDOperand(N, 0);
 116 }
 117
 118 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) {
 119   assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!");
 120   if (VT == MVT::f32)
 121     Val = (float)Val;  // Mask out extra precision.
 122
 123   SDNode *&N = ConstantFPs[std::make_pair(Val, VT)];
 124   if (N) return SDOperand(N, 0);
 125   N = new ConstantFPSDNode(Val, VT);
 126   AllNodes.push_back(N);
 127   return SDOperand(N, 0);
 128 }
 129
 130
 131
 132 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV,
 133                                          MVT::ValueType VT) {
 134   SDNode *&N = GlobalValues[GV];
 135   if (N) return SDOperand(N, 0);
 136   N = new GlobalAddressSDNode(GV,VT);
 137   AllNodes.push_back(N);
 138   return SDOperand(N, 0);
 139 }
 140
 141 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) {
 142   SDNode *&N = FrameIndices[FI];
 143   if (N) return SDOperand(N, 0);
 144   N = new FrameIndexSDNode(FI, VT);
 145   AllNodes.push_back(N);
 146   return SDOperand(N, 0);
 147 }
 148
 149 SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) {
 150   SDNode *N = ConstantPoolIndices[CPIdx];
 151   if (N) return SDOperand(N, 0);
 152   N = new ConstantPoolSDNode(CPIdx, VT);
 153   AllNodes.push_back(N);
 154   return SDOperand(N, 0);
 155 }
 156
 157 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) {
 158   SDNode *&N = BBNodes[MBB];
 159   if (N) return SDOperand(N, 0);
 160   N = new BasicBlockSDNode(MBB);
 161   AllNodes.push_back(N);
 162   return SDOperand(N, 0);
 163 }
 164
 165 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) {
 166   SDNode *&N = ExternalSymbols[Sym];
 167   if (N) return SDOperand(N, 0);
 168   N = new ExternalSymbolSDNode(Sym, VT);
 169   AllNodes.push_back(N);
 170   return SDOperand(N, 0);
 171 }
 172
 173 SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, SDOperand N1,
 174                                  SDOperand N2) {
 175   // These setcc operations always fold.
 176   switch (Cond) {
 177   default: break;
 178   case ISD::SETFALSE:
 179   case ISD::SETFALSE2: return getConstant(0, MVT::i1);
 180   case ISD::SETTRUE:
 181   case ISD::SETTRUE2:  return getConstant(1, MVT::i1);
 182   }
 183
 184   if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val))
 185     if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) {
 186       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
 187
 188       // Sign extend the operands if required
 189       if (ISD::isSignedIntSetCC(Cond)) {
 190         C1 = N1C->getSignExtended();
 191         C2 = N2C->getSignExtended();
 192       }
 193
 194       switch (Cond) {
 195       default: assert(0 && "Unknown integer setcc!");
 196       case ISD::SETEQ:  return getConstant(C1 == C2, MVT::i1);
 197       case ISD::SETNE:  return getConstant(C1 != C2, MVT::i1);
 198       case ISD::SETULT: return getConstant(C1 <  C2, MVT::i1);
 199       case ISD::SETUGT: return getConstant(C1 >  C2, MVT::i1);
 200       case ISD::SETULE: return getConstant(C1 <= C2, MVT::i1);
 201       case ISD::SETUGE: return getConstant(C1 >= C2, MVT::i1);
 202       case ISD::SETLT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 203       case ISD::SETGT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 204       case ISD::SETLE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 205       case ISD::SETGE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 206       }
 207     } else {
 208       // Ensure that the constant occurs on the RHS.
 209       Cond = ISD::getSetCCSwappedOperands(Cond);
 210       std::swap(N1, N2);
 211     }
 212
 213   if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val))
 214     if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) {
 215       double C1 = N1C->getValue(), C2 = N2C->getValue();
 216
 217       switch (Cond) {
 218       default: break; // FIXME: Implement the rest of these!
 219       case ISD::SETEQ:  return getConstant(C1 == C2, MVT::i1);
 220       case ISD::SETNE:  return getConstant(C1 != C2, MVT::i1);
 221       case ISD::SETLT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 222       case ISD::SETGT:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 223       case ISD::SETLE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 224       case ISD::SETGE:  return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1);
 225       }
 226     } else {
 227       // Ensure that the constant occurs on the RHS.
 228       Cond = ISD::getSetCCSwappedOperands(Cond);
 229       std::swap(N1, N2);
 230     }
 231
 232   if (N1 == N2) {
 233     // We can always fold X == Y for integer setcc's.
 234     if (MVT::isInteger(N1.getValueType()))
 235       return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1);
 236     unsigned UOF = ISD::getUnorderedFlavor(Cond);
 237     if (UOF == 2)   // FP operators that are undefined on NaNs.
 238       return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1);
 239     if (UOF == ISD::isTrueWhenEqual(Cond))
 240       return getConstant(UOF, MVT::i1);
 241     // Otherwise, we can't fold it.  However, we can simplify it to SETUO/SETO
 242     // if it is not already.
 243     Cond = UOF == 0 ? ISD::SETUO : ISD::SETO;
 244   }
 245
 246
 247   SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), Cond)];
 248   if (N) return SDOperand(N, 0);
 249   N = new SetCCSDNode(Cond, N1, N2);
 250   AllNodes.push_back(N);
 251   return SDOperand(N, 0);
 252 }
 253
 254
 255
 256 /// getNode - Gets or creates the specified node.
 257 ///
 258 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) {
 259   SDNode *N = new SDNode(Opcode, VT);
 260   AllNodes.push_back(N);
 261   return SDOperand(N, 0);
 262 }
 263
 264 static const Type *getTypeFor(MVT::ValueType VT) {
 265   switch (VT) {
 266   default: assert(0 && "Unknown MVT!");
 267   case MVT::i1: return Type::BoolTy;
 268   case MVT::i8: return Type::UByteTy;
 269   case MVT::i16: return Type::UShortTy;
 270   case MVT::i32: return Type::UIntTy;
 271   case MVT::i64: return Type::ULongTy;
 272   case MVT::f32: return Type::FloatTy;
 273   case MVT::f64: return Type::DoubleTy;
 274   }
 275 }
 276
 277 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 278                                 SDOperand Operand) {
 279   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) {
 280     uint64_t Val = C->getValue();
 281     switch (Opcode) {
 282     default: break;
 283     case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT);
 284     case ISD::ZERO_EXTEND: return getConstant(Val, VT);
 285     case ISD::TRUNCATE:    return getConstant(Val, VT);
 286     }
 287   }
 288
 289   if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val))
 290     switch (Opcode) {
 291     case ISD::FP_ROUND:
 292     case ISD::FP_EXTEND:
 293       return getConstantFP(C->getValue(), VT);
 294     }
 295
 296   unsigned OpOpcode = Operand.Val->getOpcode();
 297   switch (Opcode) {
 298   case ISD::SIGN_EXTEND:
 299     if (Operand.getValueType() == VT) return Operand;   // noop extension
 300     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
 301       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 302     break;
 303   case ISD::ZERO_EXTEND:
 304     if (Operand.getValueType() == VT) return Operand;   // noop extension
 305     if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND)
 306       return getNode(OpOpcode, VT, Operand.Val->getOperand(0));
 307     break;
 308   case ISD::TRUNCATE:
 309     if (Operand.getValueType() == VT) return Operand;   // noop truncate
 310     if (OpOpcode == ISD::TRUNCATE)
 311       return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0));
 312     break;
 313   }
 314
 315   SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))];
 316   if (N) return SDOperand(N, 0);
 317   N = new SDNode(Opcode, Operand);
 318   N->setValueTypes(VT);
 319   AllNodes.push_back(N);
 320   return SDOperand(N, 0);
 321 }
 322
 323 static bool isCommutativeBinOp(unsigned Opcode) {
 324   switch (Opcode) {
 325   case ISD::ADD:
 326   case ISD::MUL:
 327   case ISD::AND:
 328   case ISD::OR:
 329   case ISD::XOR: return true;
 330   default: return false; // FIXME: Need commutative info for user ops!
 331   }
 332 }
 333
 334 static bool isAssociativeBinOp(unsigned Opcode) {
 335   switch (Opcode) {
 336   case ISD::ADD:
 337   case ISD::MUL:
 338   case ISD::AND:
 339   case ISD::OR:
 340   case ISD::XOR: return true;
 341   default: return false; // FIXME: Need associative info for user ops!
 342   }
 343 }
 344
 345 static unsigned ExactLog2(uint64_t Val) {
 346   unsigned Count = 0;
 347   while (Val != 1) {
 348     Val >>= 1;
 349     ++Count;
 350   }
 351   return Count;
 352 }
 353
 354 // isInvertibleForFree - Return true if there is no cost to emitting the logical
 355 // inverse of this node.
 356 static bool isInvertibleForFree(SDOperand N) {
 357   if (isa<ConstantSDNode>(N.Val)) return true;
 358   if (isa<SetCCSDNode>(N.Val) && N.Val->hasOneUse())
 359     return true;
 360   return false;
 361 }
 362
 363
 364 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 365                                 SDOperand N1, SDOperand N2) {
 366   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 367   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
 368   if (N1C) {
 369     if (N2C) {
 370       uint64_t C1 = N1C->getValue(), C2 = N2C->getValue();
 371       switch (Opcode) {
 372       case ISD::ADD: return getConstant(C1 + C2, VT);
 373       case ISD::SUB: return getConstant(C1 - C2, VT);
 374       case ISD::MUL: return getConstant(C1 * C2, VT);
 375       case ISD::UDIV:
 376         if (C2) return getConstant(C1 / C2, VT);
 377         break;
 378       case ISD::UREM :
 379         if (C2) return getConstant(C1 % C2, VT);
 380         break;
 381       case ISD::SDIV :
 382         if (C2) return getConstant(N1C->getSignExtended() /
 383                                    N2C->getSignExtended(), VT);
 384         break;
 385       case ISD::SREM :
 386         if (C2) return getConstant(N1C->getSignExtended() %
 387                                    N2C->getSignExtended(), VT);
 388         break;
 389       case ISD::AND  : return getConstant(C1 & C2, VT);
 390       case ISD::OR   : return getConstant(C1 | C2, VT);
 391       case ISD::XOR  : return getConstant(C1 ^ C2, VT);
 392       default: break;
 393       }
 394
 395     } else {      // Cannonicalize constant to RHS if commutative
 396       if (isCommutativeBinOp(Opcode)) {
 397         std::swap(N1C, N2C);
 398         std::swap(N1, N2);
 399       }
 400     }
 401   }
 402
 403   if (N2C) {
 404     uint64_t C2 = N2C->getValue();
 405
 406     switch (Opcode) {
 407     case ISD::ADD:
 408       if (!C2) return N1;         // add X, 0 -> X
 409       break;
 410     case ISD::SUB:
 411       if (!C2) return N1;         // sub X, 0 -> X
 412       break;
 413     case ISD::MUL:
 414       if (!C2) return N2;         // mul X, 0 -> 0
 415       if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X
 416         return getNode(ISD::SUB, VT, getConstant(0, VT), N1);
 417
 418       // FIXME: This should only be done if the target supports shift
 419       // operations.
 420       if ((C2 & C2-1) == 0) {
 421         SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
 422         return getNode(ISD::SHL, VT, N1, ShAmt);
 423       }
 424       break;
 425
 426     case ISD::UDIV:
 427       // FIXME: This should only be done if the target supports shift
 428       // operations.
 429       if ((C2 & C2-1) == 0 && C2) {
 430         SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8);
 431         return getNode(ISD::SRL, VT, N1, ShAmt);
 432       }
 433       break;
 434
 435     case ISD::AND:
 436       if (!C2) return N2;         // X and 0 -> 0
 437       if (N2C->isAllOnesValue())
 438         return N1;                // X and -1 -> X
 439       break;
 440     case ISD::OR:
 441       if (!C2)return N1;          // X or 0 -> X
 442       if (N2C->isAllOnesValue())
 443         return N2;                // X or -1 -> -1
 444       break;
 445     case ISD::XOR:
 446       if (!C2) return N1;        // X xor 0 -> X
 447       if (N2C->isAllOnesValue()) {
 448         if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){
 449           // !(X op Y) -> (X !op Y)
 450           bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
 451           return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger),
 452                           SetCC->getOperand(0), SetCC->getOperand(1));
 453         } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) {
 454           SDNode *Op = N1.Val;
 455           // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible
 456           // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible
 457           SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1);
 458           if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) {
 459             LHS = getNode(ISD::XOR, VT, LHS, N2);  // RHS = ~LHS
 460             RHS = getNode(ISD::XOR, VT, RHS, N2);  // RHS = ~RHS
 461             if (Op->getOpcode() == ISD::AND)
 462               return getNode(ISD::OR, VT, LHS, RHS);
 463             return getNode(ISD::AND, VT, LHS, RHS);
 464           }
 465         }
 466         // X xor -1 -> not(x)  ?
 467       }
 468       break;
 469     }
 470
 471     // Reassociate ((X op C1) op C2) if possible.
 472     if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode))
 473       if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1)))
 474         return getNode(Opcode, VT, N3C->getOperand(0),
 475                        getNode(Opcode, VT, N2, N1.Val->getOperand(1)));
 476   }
 477
 478   ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val);
 479   ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val);
 480   if (N1CFP)
 481     if (N2CFP) {
 482       double C1 = N1CFP->getValue(), C2 = N2CFP->getValue();
 483       switch (Opcode) {
 484       case ISD::ADD: return getConstantFP(C1 + C2, VT);
 485       case ISD::SUB: return getConstantFP(C1 - C2, VT);
 486       case ISD::MUL: return getConstantFP(C1 * C2, VT);
 487       case ISD::SDIV:
 488         if (C2) return getConstantFP(C1 / C2, VT);
 489         break;
 490       case ISD::SREM :
 491         if (C2) return getConstantFP(fmod(C1, C2), VT);
 492         break;
 493       default: break;
 494       }
 495
 496     } else {      // Cannonicalize constant to RHS if commutative
 497       if (isCommutativeBinOp(Opcode)) {
 498         std::swap(N1CFP, N2CFP);
 499         std::swap(N1, N2);
 500       }
 501     }
 502
 503   // Finally, fold operations that do not require constants.
 504   switch (Opcode) {
 505   case ISD::AND:
 506   case ISD::OR:
 507     if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val))
 508       if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) {
 509         SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0);
 510         SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1);
 511         ISD::CondCode Op2 = RHS->getCondition();
 512
 513         // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y)
 514         if (LL == RR && LR == RL) {
 515           Op2 = ISD::getSetCCSwappedOperands(Op2);
 516           goto MatchedBackwards;
 517         }
 518
 519         if (LL == RL && LR == RR) {
 520         MatchedBackwards:
 521           ISD::CondCode Result;
 522           bool isInteger = MVT::isInteger(LL.getValueType());
 523           if (Opcode == ISD::OR)
 524             Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2,
 525                                               isInteger);
 526           else
 527             Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2,
 528                                                isInteger);
 529           if (Result != ISD::SETCC_INVALID)
 530             return getSetCC(Result, LL, LR);
 531         }
 532       }
 533     break;
 534   case ISD::XOR:
 535     if (N1 == N2) return getConstant(0, VT);  // xor X, Y -> 0
 536     break;
 537   }
 538
 539   SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))];
 540   if (N) return SDOperand(N, 0);
 541   N = new SDNode(Opcode, N1, N2);
 542   N->setValueTypes(VT);
 543
 544   AllNodes.push_back(N);
 545   return SDOperand(N, 0);
 546 }
 547
 548 SDOperand SelectionDAG::getLoad(MVT::ValueType VT,
 549                                 SDOperand Chain, SDOperand Ptr) {
 550   SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))];
 551   if (N) return SDOperand(N, 0);
 552   N = new SDNode(ISD::LOAD, Chain, Ptr);
 553
 554   // Loads have a token chain.
 555   N->setValueTypes(VT, MVT::Other);
 556   AllNodes.push_back(N);
 557   return SDOperand(N, 0);
 558 }
 559
 560
 561 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 562                                 SDOperand N1, SDOperand N2, SDOperand N3) {
 563   // Perform various simplifications.
 564   ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val);
 565   ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val);
 566   ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val);
 567   switch (Opcode) {
 568   case ISD::SELECT:
 569     if (N1C)
 570       if (N1C->getValue())
 571         return N2;             // select true, X, Y -> X
 572       else
 573         return N3;             // select false, X, Y -> Y
 574
 575     if (N2 == N3) return N2;   // select C, X, X -> X
 576
 577     if (VT == MVT::i1) {  // Boolean SELECT
 578       if (N2C) {
 579         if (N3C) {
 580           if (N2C->getValue()) // select C, 1, 0 -> C
 581             return N1;
 582           return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C
 583         }
 584
 585         if (N2C->getValue())   // select C, 1, X -> C | X
 586           return getNode(ISD::OR, VT, N1, N3);
 587         else                   // select C, 0, X -> ~C & X
 588           return getNode(ISD::AND, VT,
 589                          getNode(ISD::XOR, N1.getValueType(), N1,
 590                                  getConstant(1, N1.getValueType())), N3);
 591       } else if (N3C) {
 592         if (N3C->getValue())   // select C, X, 1 -> ~C | X
 593           return getNode(ISD::OR, VT,
 594                          getNode(ISD::XOR, N1.getValueType(), N1,
 595                                  getConstant(1, N1.getValueType())), N2);
 596         else                   // select C, X, 0 -> C & X
 597           return getNode(ISD::AND, VT, N1, N2);
 598       }
 599     }
 600
 601     break;
 602   }
 603
 604   SDNode *N = new SDNode(Opcode, N1, N2, N3);
 605   switch (Opcode) {
 606   default:
 607     N->setValueTypes(VT);
 608     break;
 609   case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain
 610     N->setValueTypes(VT, MVT::Other);
 611     break;
 612   }
 613
 614   // FIXME: memoize NODES
 615   AllNodes.push_back(N);
 616   return SDOperand(N, 0);
 617 }
 618
 619 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
 620                                 std::vector<SDOperand> &Children) {
 621   switch (Children.size()) {
 622   case 0: return getNode(Opcode, VT);
 623   case 1: return getNode(Opcode, VT, Children[0]);
 624   case 2: return getNode(Opcode, VT, Children[0], Children[1]);
 625   case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]);
 626   default:
 627     // FIXME: MEMOIZE!!
 628     SDNode *N = new SDNode(Opcode, Children);
 629     N->setValueTypes(VT);
 630     AllNodes.push_back(N);
 631     return SDOperand(N, 0);
 632   }
 633 }
 634
 635
 636
 637 void SDNode::dump() const {
 638   std::cerr << (void*)this << ": ";
 639
 640   for (unsigned i = 0, e = getNumValues(); i != e; ++i) {
 641     if (i) std::cerr << ",";
 642     switch (getValueType(i)) {
 643     default: assert(0 && "Unknown value type!");
 644     case MVT::i1:    std::cerr << "i1"; break;
 645     case MVT::i8:    std::cerr << "i8"; break;
 646     case MVT::i16:   std::cerr << "i16"; break;
 647     case MVT::i32:   std::cerr << "i32"; break;
 648     case MVT::i64:   std::cerr << "i64"; break;
 649     case MVT::f32:   std::cerr << "f32"; break;
 650     case MVT::f64:   std::cerr << "f64"; break;
 651     case MVT::Other: std::cerr << "ch"; break;
 652     }
 653   }
 654   std::cerr << " = ";
 655
 656   switch (getOpcode()) {
 657   default: std::cerr << "<<Unknown>>"; break;
 658   case ISD::EntryToken:    std::cerr << "EntryToken"; break;
 659   case ISD::Constant:      std::cerr << "Constant"; break;
 660   case ISD::ConstantFP:    std::cerr << "ConstantFP"; break;
 661   case ISD::GlobalAddress: std::cerr << "GlobalAddress"; break;
 662   case ISD::FrameIndex:    std::cerr << "FrameIndex"; break;
 663   case ISD::BasicBlock:    std::cerr << "BasicBlock"; break;
 664   case ISD::ExternalSymbol: std::cerr << "ExternalSymbol"; break;
 665   case ISD::ConstantPool:  std::cerr << "ConstantPoolIndex"; break;
 666   case ISD::CopyToReg:     std::cerr << "CopyToReg"; break;
 667   case ISD::CopyFromReg:   std::cerr << "CopyFromReg"; break;
 668
 669   case ISD::ADD:    std::cerr << "add"; break;
 670   case ISD::SUB:    std::cerr << "sub"; break;
 671   case ISD::MUL:    std::cerr << "mul"; break;
 672   case ISD::SDIV:   std::cerr << "sdiv"; break;
 673   case ISD::UDIV:   std::cerr << "udiv"; break;
 674   case ISD::SREM:   std::cerr << "srem"; break;
 675   case ISD::UREM:   std::cerr << "urem"; break;
 676   case ISD::AND:    std::cerr << "and"; break;
 677   case ISD::OR:     std::cerr << "or"; break;
 678   case ISD::XOR:    std::cerr << "xor"; break;
 679   case ISD::SHL:    std::cerr << "shl"; break;
 680   case ISD::SRA:    std::cerr << "sra"; break;
 681   case ISD::SRL:    std::cerr << "srl"; break;
 682
 683   case ISD::SETCC:  std::cerr << "setcc"; break;
 684   case ISD::SELECT: std::cerr << "select"; break;
 685   case ISD::ADDC:   std::cerr << "addc"; break;
 686   case ISD::SUBB:   std::cerr << "subb"; break;
 687
 688     // Conversion operators.
 689   case ISD::SIGN_EXTEND: std::cerr << "sign_extend"; break;
 690   case ISD::ZERO_EXTEND: std::cerr << "zero_extend"; break;
 691   case ISD::TRUNCATE:    std::cerr << "truncate"; break;
 692   case ISD::FP_ROUND:    std::cerr << "fp_round"; break;
 693   case ISD::FP_EXTEND:   std::cerr << "fp_extend"; break;
 694
 695     // Control flow instructions
 696   case ISD::BR:      std::cerr << "br"; break;
 697   case ISD::BRCOND:  std::cerr << "brcond"; break;
 698   case ISD::RET:     std::cerr << "ret"; break;
 699   case ISD::CALL:    std::cerr << "call"; break;
 700   case ISD::ADJCALLSTACKDOWN:  std::cerr << "adjcallstackdown"; break;
 701   case ISD::ADJCALLSTACKUP:    std::cerr << "adjcallstackup"; break;
 702
 703     // Other operators
 704   case ISD::LOAD:    std::cerr << "load"; break;
 705   case ISD::STORE:   std::cerr << "store"; break;
 706   case ISD::DYNAMIC_STACKALLOC: std::cerr << "dynamic_stackalloc"; break;
 707   case ISD::EXTRACT_ELEMENT: std::cerr << "extract_element"; break;
 708   case ISD::BUILD_PAIR: std::cerr << "build_pair"; break;
 709   }
 710
 711   std::cerr << " ";
 712   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 713     if (i) std::cerr << ", ";
 714     std::cerr << (void*)getOperand(i).Val;
 715     if (unsigned RN = getOperand(i).ResNo)
 716       std::cerr << ":" << RN;
 717   }
 718
 719   if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) {
 720     std::cerr << "<" << CSDN->getValue() << ">";
 721   } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) {
 722     std::cerr << "<" << CSDN->getValue() << ">";
 723   } else if (const GlobalAddressSDNode *GADN =
 724              dyn_cast<GlobalAddressSDNode>(this)) {
 725     std::cerr << "<";
 726     WriteAsOperand(std::cerr, GADN->getGlobal()) << ">";
 727   } else if (const FrameIndexSDNode *FIDN =
 728              dyn_cast<FrameIndexSDNode>(this)) {
 729     std::cerr << "<" << FIDN->getIndex() << ">";
 730   } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){
 731     std::cerr << "<" << CP->getIndex() << ">";
 732   } else if (const BasicBlockSDNode *BBDN =
 733              dyn_cast<BasicBlockSDNode>(this)) {
 734     std::cerr << "<";
 735     const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock();
 736     if (LBB)
 737       std::cerr << LBB->getName() << " ";
 738     std::cerr << (const void*)BBDN->getBasicBlock() << ">";
 739   } else if (const CopyRegSDNode *C2V = dyn_cast<CopyRegSDNode>(this)) {
 740     std::cerr << "<reg #" << C2V->getReg() << ">";
 741   } else if (const ExternalSymbolSDNode *ES =
 742              dyn_cast<ExternalSymbolSDNode>(this)) {
 743     std::cerr << "'" << ES->getSymbol() << "'";
 744   } else if (const SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(this)) {
 745     std::cerr << " - condition = ";
 746     switch (SetCC->getCondition()) {
 747     default: assert(0 && "Unknown setcc condition!");
 748     case ISD::SETOEQ:  std::cerr << "setoeq"; break;
 749     case ISD::SETOGT:  std::cerr << "setogt"; break;
 750     case ISD::SETOGE:  std::cerr << "setoge"; break;
 751     case ISD::SETOLT:  std::cerr << "setolt"; break;
 752     case ISD::SETOLE:  std::cerr << "setole"; break;
 753     case ISD::SETONE:  std::cerr << "setone"; break;
 754
 755     case ISD::SETO:    std::cerr << "seto";  break;
 756     case ISD::SETUO:   std::cerr << "setuo"; break;
 757     case ISD::SETUEQ:  std::cerr << "setue"; break;
 758     case ISD::SETUGT:  std::cerr << "setugt"; break;
 759     case ISD::SETUGE:  std::cerr << "setuge"; break;
 760     case ISD::SETULT:  std::cerr << "setult"; break;
 761     case ISD::SETULE:  std::cerr << "setule"; break;
 762     case ISD::SETUNE:  std::cerr << "setune"; break;
 763
 764     case ISD::SETEQ:   std::cerr << "seteq"; break;
 765     case ISD::SETGT:   std::cerr << "setgt"; break;
 766     case ISD::SETGE:   std::cerr << "setge"; break;
 767     case ISD::SETLT:   std::cerr << "setlt"; break;
 768     case ISD::SETLE:   std::cerr << "setle"; break;
 769     case ISD::SETNE:   std::cerr << "setne"; break;
 770     }
 771   }
 772
 773 }
 774
 775 void SelectionDAG::dump() const {
 776   std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:";
 777   for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) {
 778     std::cerr << "\n  ";
 779     AllNodes[i]->dump();
 780   }
 781   std::cerr << "\n\n";
 782 }
 783