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