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