SelectionDAG.cpp revision fd8c39b77331fbb6f994665b45eba1b2cc6ced6d
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 std::vector<SDNode*> Operands; 195 while (!N->Operands.empty()) { 196 SDOperand O = N->Operands.back(); 197 N->Operands.pop_back(); 198 Operands.push_back(O.Val); 199 O.Val->removeUser(N); 200 } 201 202 // Remove the node from the nodes set and delete it. 203 std::set<SDNode*> &AllNodeSet = *(std::set<SDNode*>*)NodeSet; 204 AllNodeSet.erase(N); 205 delete 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 210 // Remove duplicate operand entries. 211 std::sort(Operands.begin(), Operands.end()); 212 Operands.erase(std::unique(Operands.begin(), Operands.end()), 213 Operands.end()); 214 215 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 216 DeleteNodeIfDead(Operands[i], NodeSet); 217} 218 219 220SelectionDAG::~SelectionDAG() { 221 for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) 222 delete AllNodes[i]; 223} 224 225SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) { 226 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 227 // Mask out any bits that are not valid for this constant. 228 Val &= (1ULL << MVT::getSizeInBits(VT)) - 1; 229 230 SDNode *&N = Constants[std::make_pair(Val, VT)]; 231 if (N) return SDOperand(N, 0); 232 N = new ConstantSDNode(Val, VT); 233 AllNodes.push_back(N); 234 return SDOperand(N, 0); 235} 236 237SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) { 238 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 239 if (VT == MVT::f32) 240 Val = (float)Val; // Mask out extra precision. 241 242 SDNode *&N = ConstantFPs[std::make_pair(Val, VT)]; 243 if (N) return SDOperand(N, 0); 244 N = new ConstantFPSDNode(Val, VT); 245 AllNodes.push_back(N); 246 return SDOperand(N, 0); 247} 248 249 250 251SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, 252 MVT::ValueType VT) { 253 SDNode *&N = GlobalValues[GV]; 254 if (N) return SDOperand(N, 0); 255 N = new GlobalAddressSDNode(GV,VT); 256 AllNodes.push_back(N); 257 return SDOperand(N, 0); 258} 259 260SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) { 261 SDNode *&N = FrameIndices[FI]; 262 if (N) return SDOperand(N, 0); 263 N = new FrameIndexSDNode(FI, VT); 264 AllNodes.push_back(N); 265 return SDOperand(N, 0); 266} 267 268SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) { 269 SDNode *N = ConstantPoolIndices[CPIdx]; 270 if (N) return SDOperand(N, 0); 271 N = new ConstantPoolSDNode(CPIdx, VT); 272 AllNodes.push_back(N); 273 return SDOperand(N, 0); 274} 275 276SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 277 SDNode *&N = BBNodes[MBB]; 278 if (N) return SDOperand(N, 0); 279 N = new BasicBlockSDNode(MBB); 280 AllNodes.push_back(N); 281 return SDOperand(N, 0); 282} 283 284SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) { 285 SDNode *&N = ExternalSymbols[Sym]; 286 if (N) return SDOperand(N, 0); 287 N = new ExternalSymbolSDNode(Sym, VT); 288 AllNodes.push_back(N); 289 return SDOperand(N, 0); 290} 291 292SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, SDOperand N1, 293 SDOperand N2) { 294 // These setcc operations always fold. 295 switch (Cond) { 296 default: break; 297 case ISD::SETFALSE: 298 case ISD::SETFALSE2: return getConstant(0, MVT::i1); 299 case ISD::SETTRUE: 300 case ISD::SETTRUE2: return getConstant(1, MVT::i1); 301 } 302 303 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) 304 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) { 305 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 306 307 // Sign extend the operands if required 308 if (ISD::isSignedIntSetCC(Cond)) { 309 C1 = N1C->getSignExtended(); 310 C2 = N2C->getSignExtended(); 311 } 312 313 switch (Cond) { 314 default: assert(0 && "Unknown integer setcc!"); 315 case ISD::SETEQ: return getConstant(C1 == C2, MVT::i1); 316 case ISD::SETNE: return getConstant(C1 != C2, MVT::i1); 317 case ISD::SETULT: return getConstant(C1 < C2, MVT::i1); 318 case ISD::SETUGT: return getConstant(C1 > C2, MVT::i1); 319 case ISD::SETULE: return getConstant(C1 <= C2, MVT::i1); 320 case ISD::SETUGE: return getConstant(C1 >= C2, MVT::i1); 321 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 322 case ISD::SETGT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 323 case ISD::SETLE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 324 case ISD::SETGE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 325 } 326 } else { 327 // Ensure that the constant occurs on the RHS. 328 Cond = ISD::getSetCCSwappedOperands(Cond); 329 std::swap(N1, N2); 330 } 331 332 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) 333 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) { 334 double C1 = N1C->getValue(), C2 = N2C->getValue(); 335 336 switch (Cond) { 337 default: break; // FIXME: Implement the rest of these! 338 case ISD::SETEQ: return getConstant(C1 == C2, MVT::i1); 339 case ISD::SETNE: return getConstant(C1 != C2, MVT::i1); 340 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 341 case ISD::SETGT: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 342 case ISD::SETLE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 343 case ISD::SETGE: return getConstant((int64_t)C1 < (int64_t)C2, MVT::i1); 344 } 345 } else { 346 // Ensure that the constant occurs on the RHS. 347 Cond = ISD::getSetCCSwappedOperands(Cond); 348 std::swap(N1, N2); 349 } 350 351 if (N1 == N2) { 352 // We can always fold X == Y for integer setcc's. 353 if (MVT::isInteger(N1.getValueType())) 354 return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1); 355 unsigned UOF = ISD::getUnorderedFlavor(Cond); 356 if (UOF == 2) // FP operators that are undefined on NaNs. 357 return getConstant(ISD::isTrueWhenEqual(Cond), MVT::i1); 358 if (UOF == ISD::isTrueWhenEqual(Cond)) 359 return getConstant(UOF, MVT::i1); 360 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 361 // if it is not already. 362 Cond = UOF == 0 ? ISD::SETUO : ISD::SETO; 363 } 364 365 366 SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), Cond)]; 367 if (N) return SDOperand(N, 0); 368 N = new SetCCSDNode(Cond, N1, N2); 369 AllNodes.push_back(N); 370 return SDOperand(N, 0); 371} 372 373 374 375/// getNode - Gets or creates the specified node. 376/// 377SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { 378 SDNode *N = new SDNode(Opcode, VT); 379 AllNodes.push_back(N); 380 return SDOperand(N, 0); 381} 382 383static const Type *getTypeFor(MVT::ValueType VT) { 384 switch (VT) { 385 default: assert(0 && "Unknown MVT!"); 386 case MVT::i1: return Type::BoolTy; 387 case MVT::i8: return Type::UByteTy; 388 case MVT::i16: return Type::UShortTy; 389 case MVT::i32: return Type::UIntTy; 390 case MVT::i64: return Type::ULongTy; 391 case MVT::f32: return Type::FloatTy; 392 case MVT::f64: return Type::DoubleTy; 393 } 394} 395 396SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 397 SDOperand Operand) { 398 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) { 399 uint64_t Val = C->getValue(); 400 switch (Opcode) { 401 default: break; 402 case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT); 403 case ISD::ZERO_EXTEND: return getConstant(Val, VT); 404 case ISD::TRUNCATE: return getConstant(Val, VT); 405 } 406 } 407 408 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) 409 switch (Opcode) { 410 case ISD::FP_ROUND: 411 case ISD::FP_EXTEND: 412 return getConstantFP(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, N3C->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 } 666 667 SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))]; 668 if (N) return SDOperand(N, 0); 669 N = new SDNode(Opcode, N1, N2); 670 N->setValueTypes(VT); 671 672 AllNodes.push_back(N); 673 return SDOperand(N, 0); 674} 675 676SDOperand SelectionDAG::getLoad(MVT::ValueType VT, 677 SDOperand Chain, SDOperand Ptr) { 678 SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))]; 679 if (N) return SDOperand(N, 0); 680 N = new SDNode(ISD::LOAD, Chain, Ptr); 681 682 // Loads have a token chain. 683 N->setValueTypes(VT, MVT::Other); 684 AllNodes.push_back(N); 685 return SDOperand(N, 0); 686} 687 688 689SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 690 SDOperand N1, SDOperand N2, SDOperand N3) { 691 // Perform various simplifications. 692 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 693 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 694 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 695 switch (Opcode) { 696 case ISD::SELECT: 697 if (N1C) 698 if (N1C->getValue()) 699 return N2; // select true, X, Y -> X 700 else 701 return N3; // select false, X, Y -> Y 702 703 if (N2 == N3) return N2; // select C, X, X -> X 704 705 if (VT == MVT::i1) { // Boolean SELECT 706 if (N2C) { 707 if (N3C) { 708 if (N2C->getValue()) // select C, 1, 0 -> C 709 return N1; 710 return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C 711 } 712 713 if (N2C->getValue()) // select C, 1, X -> C | X 714 return getNode(ISD::OR, VT, N1, N3); 715 else // select C, 0, X -> ~C & X 716 return getNode(ISD::AND, VT, 717 getNode(ISD::XOR, N1.getValueType(), N1, 718 getConstant(1, N1.getValueType())), N3); 719 } else if (N3C) { 720 if (N3C->getValue()) // select C, X, 1 -> ~C | X 721 return getNode(ISD::OR, VT, 722 getNode(ISD::XOR, N1.getValueType(), N1, 723 getConstant(1, N1.getValueType())), N2); 724 else // select C, X, 0 -> C & X 725 return getNode(ISD::AND, VT, N1, N2); 726 } 727 } 728 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