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