SelectionDAG.cpp revision c3aae25116e66c177579b0b79182b09340b19753
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> 21using namespace llvm; 22 23/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 24/// when given the operation for (X op Y). 25ISD::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. 37ISD::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). 52static 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. 72ISD::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. 91ISD::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 101SelectionDAG::~SelectionDAG() { 102 for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) 103 delete AllNodes[i]; 104} 105 106SDOperand 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 118SDOperand 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 132SDOperand 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 141SDOperand 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 149SDOperand 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 157SDOperand 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 165SDOperand 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 173SDOperand 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/// 258SDOperand 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 264static 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 277SDOperand 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 323static 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 334static 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 345static 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. 356static 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 364SDOperand 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 548SDOperand 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 561SDOperand 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 619SDOperand 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 637void 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 775void 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 784