SelectionDAG.cpp revision a7306db5f7cb7376da77237ada0bd624f99fec6c
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 25static bool isCommutativeBinOp(unsigned Opcode) { 26 switch (Opcode) { 27 case ISD::ADD: 28 case ISD::MUL: 29 case ISD::AND: 30 case ISD::OR: 31 case ISD::XOR: return true; 32 default: return false; // FIXME: Need commutative info for user ops! 33 } 34} 35 36static bool isAssociativeBinOp(unsigned Opcode) { 37 switch (Opcode) { 38 case ISD::ADD: 39 case ISD::MUL: 40 case ISD::AND: 41 case ISD::OR: 42 case ISD::XOR: return true; 43 default: return false; // FIXME: Need associative info for user ops! 44 } 45} 46 47static unsigned ExactLog2(uint64_t Val) { 48 unsigned Count = 0; 49 while (Val != 1) { 50 Val >>= 1; 51 ++Count; 52 } 53 return Count; 54} 55 56// isInvertibleForFree - Return true if there is no cost to emitting the logical 57// inverse of this node. 58static bool isInvertibleForFree(SDOperand N) { 59 if (isa<ConstantSDNode>(N.Val)) return true; 60 if (isa<SetCCSDNode>(N.Val) && N.Val->hasOneUse()) 61 return true; 62 return false; 63} 64 65 66/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 67/// when given the operation for (X op Y). 68ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 69 // To perform this operation, we just need to swap the L and G bits of the 70 // operation. 71 unsigned OldL = (Operation >> 2) & 1; 72 unsigned OldG = (Operation >> 1) & 1; 73 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 74 (OldL << 1) | // New G bit 75 (OldG << 2)); // New L bit. 76} 77 78/// getSetCCInverse - Return the operation corresponding to !(X op Y), where 79/// 'op' is a valid SetCC operation. 80ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 81 unsigned Operation = Op; 82 if (isInteger) 83 Operation ^= 7; // Flip L, G, E bits, but not U. 84 else 85 Operation ^= 15; // Flip all of the condition bits. 86 if (Operation > ISD::SETTRUE2) 87 Operation &= ~8; // Don't let N and U bits get set. 88 return ISD::CondCode(Operation); 89} 90 91 92/// isSignedOp - For an integer comparison, return 1 if the comparison is a 93/// signed operation and 2 if the result is an unsigned comparison. Return zero 94/// if the operation does not depend on the sign of the input (setne and seteq). 95static int isSignedOp(ISD::CondCode Opcode) { 96 switch (Opcode) { 97 default: assert(0 && "Illegal integer setcc operation!"); 98 case ISD::SETEQ: 99 case ISD::SETNE: return 0; 100 case ISD::SETLT: 101 case ISD::SETLE: 102 case ISD::SETGT: 103 case ISD::SETGE: return 1; 104 case ISD::SETULT: 105 case ISD::SETULE: 106 case ISD::SETUGT: 107 case ISD::SETUGE: return 2; 108 } 109} 110 111/// getSetCCOrOperation - Return the result of a logical OR between different 112/// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 113/// returns SETCC_INVALID if it is not possible to represent the resultant 114/// comparison. 115ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 116 bool isInteger) { 117 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 118 // Cannot fold a signed integer setcc with an unsigned integer setcc. 119 return ISD::SETCC_INVALID; 120 121 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 122 123 // If the N and U bits get set then the resultant comparison DOES suddenly 124 // care about orderedness, and is true when ordered. 125 if (Op > ISD::SETTRUE2) 126 Op &= ~16; // Clear the N bit. 127 return ISD::CondCode(Op); 128} 129 130/// getSetCCAndOperation - Return the result of a logical AND between different 131/// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 132/// function returns zero if it is not possible to represent the resultant 133/// comparison. 134ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 135 bool isInteger) { 136 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 137 // Cannot fold a signed setcc with an unsigned setcc. 138 return ISD::SETCC_INVALID; 139 140 // Combine all of the condition bits. 141 return ISD::CondCode(Op1 & Op2); 142} 143 144/// RemoveDeadNodes - This method deletes all unreachable nodes in the 145/// SelectionDAG, including nodes (like loads) that have uses of their token 146/// chain but no other uses and no side effect. If a node is passed in as an 147/// argument, it is used as the seed for node deletion. 148void SelectionDAG::RemoveDeadNodes(SDNode *N) { 149 std::set<SDNode*> AllNodeSet(AllNodes.begin(), AllNodes.end()); 150 151 // Create a dummy node (which is not added to allnodes), that adds a reference 152 // to the root node, preventing it from being deleted. 153 SDNode *DummyNode = new SDNode(ISD::EntryToken, getRoot()); 154 155 DeleteNodeIfDead(N, &AllNodeSet); 156 157 Restart: 158 unsigned NumNodes = AllNodeSet.size(); 159 for (std::set<SDNode*>::iterator I = AllNodeSet.begin(), E = AllNodeSet.end(); 160 I != E; ++I) { 161 // Try to delete this node. 162 DeleteNodeIfDead(*I, &AllNodeSet); 163 164 // If we actually deleted any nodes, do not use invalid iterators in 165 // AllNodeSet. 166 if (AllNodeSet.size() != NumNodes) 167 goto Restart; 168 } 169 170 // Restore AllNodes. 171 if (AllNodes.size() != NumNodes) 172 AllNodes.assign(AllNodeSet.begin(), AllNodeSet.end()); 173 174 // If the root changed (e.g. it was a dead load, update the root). 175 setRoot(DummyNode->getOperand(0)); 176 177 // Now that we are done with the dummy node, delete it. 178 DummyNode->getOperand(0).Val->removeUser(DummyNode); 179 delete DummyNode; 180} 181 182void SelectionDAG::DeleteNodeIfDead(SDNode *N, void *NodeSet) { 183 if (!N->use_empty()) 184 return; 185 186 // Okay, we really are going to delete this node. First take this out of the 187 // appropriate CSE map. 188 switch (N->getOpcode()) { 189 case ISD::Constant: 190 Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(), 191 N->getValueType(0))); 192 break; 193 case ISD::ConstantFP: 194 ConstantFPs.erase(std::make_pair(cast<ConstantFPSDNode>(N)->getValue(), 195 N->getValueType(0))); 196 break; 197 case ISD::GlobalAddress: 198 GlobalValues.erase(cast<GlobalAddressSDNode>(N)->getGlobal()); 199 break; 200 case ISD::FrameIndex: 201 FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex()); 202 break; 203 case ISD::ConstantPool: 204 ConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->getIndex()); 205 break; 206 case ISD::BasicBlock: 207 BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock()); 208 break; 209 case ISD::ExternalSymbol: 210 ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 211 break; 212 213 case ISD::LOAD: 214 Loads.erase(std::make_pair(N->getOperand(1), 215 std::make_pair(N->getOperand(0), 216 N->getValueType(0)))); 217 break; 218 case ISD::SETCC: 219 SetCCs.erase(std::make_pair(std::make_pair(N->getOperand(0), 220 N->getOperand(1)), 221 std::make_pair( 222 cast<SetCCSDNode>(N)->getCondition(), 223 N->getValueType(0)))); 224 break; 225 case ISD::TRUNCSTORE: 226 case ISD::SIGN_EXTEND_INREG: 227 case ISD::ZERO_EXTEND_INREG: 228 case ISD::FP_ROUND_INREG: 229 case ISD::EXTLOAD: 230 case ISD::SEXTLOAD: 231 case ISD::ZEXTLOAD: { 232 EVTStruct NN; 233 NN.Opcode = ISD::TRUNCSTORE; 234 NN.VT = N->getValueType(0); 235 NN.EVT = cast<MVTSDNode>(N)->getExtraValueType(); 236 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 237 NN.Ops.push_back(N->getOperand(i)); 238 MVTSDNodes.erase(NN); 239 break; 240 } 241 default: 242 if (N->getNumOperands() == 1) 243 UnaryOps.erase(std::make_pair(N->getOpcode(), 244 std::make_pair(N->getOperand(0), 245 N->getValueType(0)))); 246 else if (N->getNumOperands() == 2) 247 BinaryOps.erase(std::make_pair(N->getOpcode(), 248 std::make_pair(N->getOperand(0), 249 N->getOperand(1)))); 250 break; 251 } 252 253 // Next, brutally remove the operand list. 254 while (!N->Operands.empty()) { 255 SDNode *O = N->Operands.back().Val; 256 N->Operands.pop_back(); 257 O->removeUser(N); 258 259 // Now that we removed this operand, see if there are no uses of it left. 260 DeleteNodeIfDead(O, NodeSet); 261 } 262 263 // Remove the node from the nodes set and delete it. 264 std::set<SDNode*> &AllNodeSet = *(std::set<SDNode*>*)NodeSet; 265 AllNodeSet.erase(N); 266 267 // Now that the node is gone, check to see if any of the operands of this node 268 // are dead now. 269 delete N; 270} 271 272 273SelectionDAG::~SelectionDAG() { 274 for (unsigned i = 0, e = AllNodes.size(); i != e; ++i) 275 delete AllNodes[i]; 276} 277 278SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) { 279 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 280 // Mask out any bits that are not valid for this constant. 281 if (VT != MVT::i64) 282 Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; 283 284 SDNode *&N = Constants[std::make_pair(Val, VT)]; 285 if (N) return SDOperand(N, 0); 286 N = new ConstantSDNode(Val, VT); 287 AllNodes.push_back(N); 288 return SDOperand(N, 0); 289} 290 291SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) { 292 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 293 if (VT == MVT::f32) 294 Val = (float)Val; // Mask out extra precision. 295 296 SDNode *&N = ConstantFPs[std::make_pair(Val, VT)]; 297 if (N) return SDOperand(N, 0); 298 N = new ConstantFPSDNode(Val, VT); 299 AllNodes.push_back(N); 300 return SDOperand(N, 0); 301} 302 303 304 305SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, 306 MVT::ValueType VT) { 307 SDNode *&N = GlobalValues[GV]; 308 if (N) return SDOperand(N, 0); 309 N = new GlobalAddressSDNode(GV,VT); 310 AllNodes.push_back(N); 311 return SDOperand(N, 0); 312} 313 314SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) { 315 SDNode *&N = FrameIndices[FI]; 316 if (N) return SDOperand(N, 0); 317 N = new FrameIndexSDNode(FI, VT); 318 AllNodes.push_back(N); 319 return SDOperand(N, 0); 320} 321 322SDOperand SelectionDAG::getConstantPool(unsigned CPIdx, MVT::ValueType VT) { 323 SDNode *N = ConstantPoolIndices[CPIdx]; 324 if (N) return SDOperand(N, 0); 325 N = new ConstantPoolSDNode(CPIdx, VT); 326 AllNodes.push_back(N); 327 return SDOperand(N, 0); 328} 329 330SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 331 SDNode *&N = BBNodes[MBB]; 332 if (N) return SDOperand(N, 0); 333 N = new BasicBlockSDNode(MBB); 334 AllNodes.push_back(N); 335 return SDOperand(N, 0); 336} 337 338SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) { 339 SDNode *&N = ExternalSymbols[Sym]; 340 if (N) return SDOperand(N, 0); 341 N = new ExternalSymbolSDNode(Sym, VT); 342 AllNodes.push_back(N); 343 return SDOperand(N, 0); 344} 345 346SDOperand SelectionDAG::getSetCC(ISD::CondCode Cond, MVT::ValueType VT, 347 SDOperand N1, SDOperand N2) { 348 // These setcc operations always fold. 349 switch (Cond) { 350 default: break; 351 case ISD::SETFALSE: 352 case ISD::SETFALSE2: return getConstant(0, VT); 353 case ISD::SETTRUE: 354 case ISD::SETTRUE2: return getConstant(1, VT); 355 } 356 357 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) 358 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) { 359 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 360 361 // Sign extend the operands if required 362 if (ISD::isSignedIntSetCC(Cond)) { 363 C1 = N1C->getSignExtended(); 364 C2 = N2C->getSignExtended(); 365 } 366 367 switch (Cond) { 368 default: assert(0 && "Unknown integer setcc!"); 369 case ISD::SETEQ: return getConstant(C1 == C2, VT); 370 case ISD::SETNE: return getConstant(C1 != C2, VT); 371 case ISD::SETULT: return getConstant(C1 < C2, VT); 372 case ISD::SETUGT: return getConstant(C1 > C2, VT); 373 case ISD::SETULE: return getConstant(C1 <= C2, VT); 374 case ISD::SETUGE: return getConstant(C1 >= C2, VT); 375 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, VT); 376 case ISD::SETGT: return getConstant((int64_t)C1 > (int64_t)C2, VT); 377 case ISD::SETLE: return getConstant((int64_t)C1 <= (int64_t)C2, VT); 378 case ISD::SETGE: return getConstant((int64_t)C1 >= (int64_t)C2, VT); 379 } 380 } else { 381 // Ensure that the constant occurs on the RHS. 382 Cond = ISD::getSetCCSwappedOperands(Cond); 383 std::swap(N1, N2); 384 } 385 386 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) 387 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) { 388 double C1 = N1C->getValue(), C2 = N2C->getValue(); 389 390 switch (Cond) { 391 default: break; // FIXME: Implement the rest of these! 392 case ISD::SETEQ: return getConstant(C1 == C2, VT); 393 case ISD::SETNE: return getConstant(C1 != C2, VT); 394 case ISD::SETLT: return getConstant(C1 < C2, VT); 395 case ISD::SETGT: return getConstant(C1 > C2, VT); 396 case ISD::SETLE: return getConstant(C1 <= C2, VT); 397 case ISD::SETGE: return getConstant(C1 >= C2, VT); 398 } 399 } else { 400 // Ensure that the constant occurs on the RHS. 401 Cond = ISD::getSetCCSwappedOperands(Cond); 402 std::swap(N1, N2); 403 } 404 405 if (N1 == N2) { 406 // We can always fold X == Y for integer setcc's. 407 if (MVT::isInteger(N1.getValueType())) 408 return getConstant(ISD::isTrueWhenEqual(Cond), VT); 409 unsigned UOF = ISD::getUnorderedFlavor(Cond); 410 if (UOF == 2) // FP operators that are undefined on NaNs. 411 return getConstant(ISD::isTrueWhenEqual(Cond), VT); 412 if (UOF == ISD::isTrueWhenEqual(Cond)) 413 return getConstant(UOF, VT); 414 // Otherwise, we can't fold it. However, we can simplify it to SETUO/SETO 415 // if it is not already. 416 Cond = UOF == 0 ? ISD::SETUO : ISD::SETO; 417 } 418 419 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 420 MVT::isInteger(N1.getValueType())) { 421 if (N1.getOpcode() == ISD::ADD || N1.getOpcode() == ISD::SUB || 422 N1.getOpcode() == ISD::XOR) { 423 // Simplify (X+Y) == (X+Z) --> Y == Z 424 if (N1.getOpcode() == N2.getOpcode()) { 425 if (N1.getOperand(0) == N2.getOperand(0)) 426 return getSetCC(Cond, VT, N1.getOperand(1), N2.getOperand(1)); 427 if (N1.getOperand(1) == N2.getOperand(1)) 428 return getSetCC(Cond, VT, N1.getOperand(0), N2.getOperand(0)); 429 if (isCommutativeBinOp(N1.getOpcode())) { 430 // If X op Y == Y op X, try other combinations. 431 if (N1.getOperand(0) == N2.getOperand(1)) 432 return getSetCC(Cond, VT, N1.getOperand(1), N2.getOperand(0)); 433 if (N1.getOperand(1) == N2.getOperand(0)) 434 return getSetCC(Cond, VT, N1.getOperand(1), N2.getOperand(1)); 435 } 436 } 437 438 // Simplify (X+Z) == X --> Z == 0 439 if (N1.getOperand(0) == N2) 440 return getSetCC(Cond, VT, N1.getOperand(1), 441 getConstant(0, N1.getValueType())); 442 if (N1.getOperand(1) == N2) { 443 if (isCommutativeBinOp(N1.getOpcode())) 444 return getSetCC(Cond, VT, N1.getOperand(0), 445 getConstant(0, N1.getValueType())); 446 else { 447 assert(N1.getOpcode() == ISD::SUB && "Unexpected operation!"); 448 // (Z-X) == X --> Z == X<<1 449 if (N2.getValueType() != MVT::i64) // FIXME: HACK HACK HACK! 450 return getSetCC(Cond, VT, N1.getOperand(0), 451 getNode(ISD::SHL, N2.getValueType(), 452 N2, getConstant(1, MVT::i8))); 453 } 454 } 455 } 456 457 if (N2.getOpcode() == ISD::ADD || N2.getOpcode() == ISD::SUB || 458 N2.getOpcode() == ISD::XOR) { 459 // Simplify X == (X+Z) --> Z == 0 460 if (N2.getOperand(0) == N1) 461 return getSetCC(Cond, VT, N2.getOperand(1), 462 getConstant(0, N2.getValueType())); 463 else if (N2.getOperand(1) == N1) 464 return getSetCC(Cond, VT, N2.getOperand(0), 465 getConstant(0, N2.getValueType())); 466 } 467 } 468 469 SetCCSDNode *&N = SetCCs[std::make_pair(std::make_pair(N1, N2), 470 std::make_pair(Cond, VT))]; 471 if (N) return SDOperand(N, 0); 472 N = new SetCCSDNode(Cond, N1, N2); 473 N->setValueTypes(VT); 474 AllNodes.push_back(N); 475 return SDOperand(N, 0); 476} 477 478 479 480/// getNode - Gets or creates the specified node. 481/// 482SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { 483 SDNode *N = new SDNode(Opcode, VT); 484 AllNodes.push_back(N); 485 return SDOperand(N, 0); 486} 487 488SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 489 SDOperand Operand) { 490 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) { 491 uint64_t Val = C->getValue(); 492 switch (Opcode) { 493 default: break; 494 case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT); 495 case ISD::ZERO_EXTEND: return getConstant(Val, VT); 496 case ISD::TRUNCATE: return getConstant(Val, VT); 497 case ISD::SINT_TO_FP: return getConstantFP(C->getSignExtended(), VT); 498 case ISD::UINT_TO_FP: return getConstantFP(C->getValue(), VT); 499 } 500 } 501 502 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) 503 switch (Opcode) { 504 case ISD::FP_ROUND: 505 case ISD::FP_EXTEND: 506 return getConstantFP(C->getValue(), VT); 507 case ISD::FP_TO_SINT: 508 return getConstant((int64_t)C->getValue(), VT); 509 case ISD::FP_TO_UINT: 510 return getConstant((uint64_t)C->getValue(), VT); 511 } 512 513 unsigned OpOpcode = Operand.Val->getOpcode(); 514 switch (Opcode) { 515 case ISD::TokenFactor: 516 return Operand; // Factor of one node? No factor. 517 case ISD::SIGN_EXTEND: 518 if (Operand.getValueType() == VT) return Operand; // noop extension 519 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 520 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 521 break; 522 case ISD::ZERO_EXTEND: 523 if (Operand.getValueType() == VT) return Operand; // noop extension 524 if (OpOpcode == ISD::ZERO_EXTEND) 525 return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0)); 526 break; 527 case ISD::TRUNCATE: 528 if (Operand.getValueType() == VT) return Operand; // noop truncate 529 if (OpOpcode == ISD::TRUNCATE) 530 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 531 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) { 532 // If the source is smaller than the dest, we still need an extend. 533 if (Operand.Val->getOperand(0).getValueType() < VT) 534 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 535 else if (Operand.Val->getOperand(0).getValueType() > VT) 536 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 537 else 538 return Operand.Val->getOperand(0); 539 } 540 break; 541 } 542 543 SDNode *&N = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))]; 544 if (N) return SDOperand(N, 0); 545 N = new SDNode(Opcode, Operand); 546 N->setValueTypes(VT); 547 AllNodes.push_back(N); 548 return SDOperand(N, 0); 549} 550 551SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 552 SDOperand N1, SDOperand N2) { 553#ifndef NDEBUG 554 switch (Opcode) { 555 case ISD::TokenFactor: 556 assert(VT == MVT::Other && N1.getValueType() == MVT::Other && 557 N2.getValueType() == MVT::Other && "Invalid token factor!"); 558 break; 559 case ISD::AND: 560 case ISD::OR: 561 case ISD::XOR: 562 case ISD::UDIV: 563 case ISD::UREM: 564 assert(MVT::isInteger(VT) && "This operator does not apply to FP types!"); 565 // fall through 566 case ISD::ADD: 567 case ISD::SUB: 568 case ISD::MUL: 569 case ISD::SDIV: 570 case ISD::SREM: 571 assert(N1.getValueType() == N2.getValueType() && 572 N1.getValueType() == VT && "Binary operator types must match!"); 573 break; 574 575 case ISD::SHL: 576 case ISD::SRA: 577 case ISD::SRL: 578 assert(VT == N1.getValueType() && 579 "Shift operators return type must be the same as their first arg"); 580 assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) && 581 VT != MVT::i1 && "Shifts only work on integers"); 582 break; 583 default: break; 584 } 585#endif 586 587 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 588 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 589 if (N1C) { 590 if (N2C) { 591 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 592 switch (Opcode) { 593 case ISD::ADD: return getConstant(C1 + C2, VT); 594 case ISD::SUB: return getConstant(C1 - C2, VT); 595 case ISD::MUL: return getConstant(C1 * C2, VT); 596 case ISD::UDIV: 597 if (C2) return getConstant(C1 / C2, VT); 598 break; 599 case ISD::UREM : 600 if (C2) return getConstant(C1 % C2, VT); 601 break; 602 case ISD::SDIV : 603 if (C2) return getConstant(N1C->getSignExtended() / 604 N2C->getSignExtended(), VT); 605 break; 606 case ISD::SREM : 607 if (C2) return getConstant(N1C->getSignExtended() % 608 N2C->getSignExtended(), VT); 609 break; 610 case ISD::AND : return getConstant(C1 & C2, VT); 611 case ISD::OR : return getConstant(C1 | C2, VT); 612 case ISD::XOR : return getConstant(C1 ^ C2, VT); 613 case ISD::SHL : return getConstant(C1 << (int)C2, VT); 614 case ISD::SRL : return getConstant(C1 >> (unsigned)C2, VT); 615 case ISD::SRA : return getConstant(N1C->getSignExtended() >>(int)C2, VT); 616 default: break; 617 } 618 619 } else { // Cannonicalize constant to RHS if commutative 620 if (isCommutativeBinOp(Opcode)) { 621 std::swap(N1C, N2C); 622 std::swap(N1, N2); 623 } 624 } 625 626 switch (Opcode) { 627 default: break; 628 case ISD::SHL: // shl 0, X -> 0 629 if (N1C->isNullValue()) return N1; 630 break; 631 case ISD::SRL: // srl 0, X -> 0 632 if (N1C->isNullValue()) return N1; 633 break; 634 case ISD::SRA: // sra -1, X -> -1 635 if (N1C->isAllOnesValue()) return N1; 636 break; 637 } 638 } 639 640 if (N2C) { 641 uint64_t C2 = N2C->getValue(); 642 643 switch (Opcode) { 644 case ISD::ADD: 645 if (!C2) return N1; // add X, 0 -> X 646 break; 647 case ISD::SUB: 648 if (!C2) return N1; // sub X, 0 -> X 649 break; 650 case ISD::MUL: 651 if (!C2) return N2; // mul X, 0 -> 0 652 if (N2C->isAllOnesValue()) // mul X, -1 -> 0-X 653 return getNode(ISD::SUB, VT, getConstant(0, VT), N1); 654 655 // FIXME: This should only be done if the target supports shift 656 // operations. 657 if ((C2 & C2-1) == 0) { 658 if (N2.getValueType() != MVT::i64) { // FIXME: HACK HACK HACK! 659 SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8); 660 return getNode(ISD::SHL, VT, N1, ShAmt); 661 } 662 } 663 break; 664 665 case ISD::UDIV: 666 // FIXME: This should only be done if the target supports shift 667 // operations. 668 if ((C2 & C2-1) == 0 && C2) { 669 if (N2.getValueType() != MVT::i64) { // FIXME: HACK HACK HACK! 670 SDOperand ShAmt = getConstant(ExactLog2(C2), MVT::i8); 671 return getNode(ISD::SRL, VT, N1, ShAmt); 672 } 673 } 674 break; 675 676 case ISD::SHL: 677 case ISD::SRL: 678 case ISD::SRA: 679 if (C2 == 0) return N1; 680 break; 681 682 case ISD::AND: 683 if (!C2) return N2; // X and 0 -> 0 684 if (N2C->isAllOnesValue()) 685 return N1; // X and -1 -> X 686 break; 687 case ISD::OR: 688 if (!C2)return N1; // X or 0 -> X 689 if (N2C->isAllOnesValue()) 690 return N2; // X or -1 -> -1 691 break; 692 case ISD::XOR: 693 if (!C2) return N1; // X xor 0 -> X 694 if (N2C->isAllOnesValue()) { 695 if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N1.Val)){ 696 // !(X op Y) -> (X !op Y) 697 bool isInteger = MVT::isInteger(SetCC->getOperand(0).getValueType()); 698 return getSetCC(ISD::getSetCCInverse(SetCC->getCondition(),isInteger), 699 SetCC->getValueType(0), 700 SetCC->getOperand(0), SetCC->getOperand(1)); 701 } else if (N1.getOpcode() == ISD::AND || N1.getOpcode() == ISD::OR) { 702 SDNode *Op = N1.Val; 703 // !(X or Y) -> (!X and !Y) iff X or Y are freely invertible 704 // !(X and Y) -> (!X or !Y) iff X or Y are freely invertible 705 SDOperand LHS = Op->getOperand(0), RHS = Op->getOperand(1); 706 if (isInvertibleForFree(RHS) || isInvertibleForFree(LHS)) { 707 LHS = getNode(ISD::XOR, VT, LHS, N2); // RHS = ~LHS 708 RHS = getNode(ISD::XOR, VT, RHS, N2); // RHS = ~RHS 709 if (Op->getOpcode() == ISD::AND) 710 return getNode(ISD::OR, VT, LHS, RHS); 711 return getNode(ISD::AND, VT, LHS, RHS); 712 } 713 } 714 // X xor -1 -> not(x) ? 715 } 716 break; 717 } 718 719 // Reassociate ((X op C1) op C2) if possible. 720 if (N1.getOpcode() == Opcode && isAssociativeBinOp(Opcode)) 721 if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N1.Val->getOperand(1))) 722 return getNode(Opcode, VT, N1.Val->getOperand(0), 723 getNode(Opcode, VT, N2, N1.Val->getOperand(1))); 724 } 725 726 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); 727 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val); 728 if (N1CFP) 729 if (N2CFP) { 730 double C1 = N1CFP->getValue(), C2 = N2CFP->getValue(); 731 switch (Opcode) { 732 case ISD::ADD: return getConstantFP(C1 + C2, VT); 733 case ISD::SUB: return getConstantFP(C1 - C2, VT); 734 case ISD::MUL: return getConstantFP(C1 * C2, VT); 735 case ISD::SDIV: 736 if (C2) return getConstantFP(C1 / C2, VT); 737 break; 738 case ISD::SREM : 739 if (C2) return getConstantFP(fmod(C1, C2), VT); 740 break; 741 default: break; 742 } 743 744 } else { // Cannonicalize constant to RHS if commutative 745 if (isCommutativeBinOp(Opcode)) { 746 std::swap(N1CFP, N2CFP); 747 std::swap(N1, N2); 748 } 749 } 750 751 // Finally, fold operations that do not require constants. 752 switch (Opcode) { 753 case ISD::TokenFactor: 754 if (N1.getOpcode() == ISD::EntryToken) 755 return N2; 756 if (N2.getOpcode() == ISD::EntryToken) 757 return N1; 758 break; 759 760 case ISD::AND: 761 case ISD::OR: 762 if (SetCCSDNode *LHS = dyn_cast<SetCCSDNode>(N1.Val)) 763 if (SetCCSDNode *RHS = dyn_cast<SetCCSDNode>(N2.Val)) { 764 SDOperand LL = LHS->getOperand(0), RL = RHS->getOperand(0); 765 SDOperand LR = LHS->getOperand(1), RR = RHS->getOperand(1); 766 ISD::CondCode Op2 = RHS->getCondition(); 767 768 // (X op1 Y) | (Y op2 X) -> (X op1 Y) | (X swapop2 Y) 769 if (LL == RR && LR == RL) { 770 Op2 = ISD::getSetCCSwappedOperands(Op2); 771 goto MatchedBackwards; 772 } 773 774 if (LL == RL && LR == RR) { 775 MatchedBackwards: 776 ISD::CondCode Result; 777 bool isInteger = MVT::isInteger(LL.getValueType()); 778 if (Opcode == ISD::OR) 779 Result = ISD::getSetCCOrOperation(LHS->getCondition(), Op2, 780 isInteger); 781 else 782 Result = ISD::getSetCCAndOperation(LHS->getCondition(), Op2, 783 isInteger); 784 if (Result != ISD::SETCC_INVALID) 785 return getSetCC(Result, LHS->getValueType(0), LL, LR); 786 } 787 } 788 break; 789 case ISD::XOR: 790 if (N1 == N2) return getConstant(0, VT); // xor X, Y -> 0 791 break; 792 case ISD::SUB: 793 if (N1.getOpcode() == ISD::ADD) { 794 if (N1.Val->getOperand(0) == N2) 795 return N1.Val->getOperand(1); // (A+B)-A == B 796 if (N1.Val->getOperand(1) == N2) 797 return N1.Val->getOperand(0); // (A+B)-B == A 798 } 799 break; 800 } 801 802 SDNode *&N = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))]; 803 if (N) return SDOperand(N, 0); 804 N = new SDNode(Opcode, N1, N2); 805 N->setValueTypes(VT); 806 807 AllNodes.push_back(N); 808 return SDOperand(N, 0); 809} 810 811SDOperand SelectionDAG::getLoad(MVT::ValueType VT, 812 SDOperand Chain, SDOperand Ptr) { 813 SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))]; 814 if (N) return SDOperand(N, 0); 815 N = new SDNode(ISD::LOAD, Chain, Ptr); 816 817 // Loads have a token chain. 818 N->setValueTypes(VT, MVT::Other); 819 AllNodes.push_back(N); 820 return SDOperand(N, 0); 821} 822 823 824SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 825 SDOperand N1, SDOperand N2, SDOperand N3) { 826 // Perform various simplifications. 827 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 828 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 829 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 830 switch (Opcode) { 831 case ISD::SELECT: 832 if (N1C) 833 if (N1C->getValue()) 834 return N2; // select true, X, Y -> X 835 else 836 return N3; // select false, X, Y -> Y 837 838 if (N2 == N3) return N2; // select C, X, X -> X 839 840 if (VT == MVT::i1) { // Boolean SELECT 841 if (N2C) { 842 if (N3C) { 843 if (N2C->getValue()) // select C, 1, 0 -> C 844 return N1; 845 return getNode(ISD::XOR, VT, N1, N3); // select C, 0, 1 -> ~C 846 } 847 848 if (N2C->getValue()) // select C, 1, X -> C | X 849 return getNode(ISD::OR, VT, N1, N3); 850 else // select C, 0, X -> ~C & X 851 return getNode(ISD::AND, VT, 852 getNode(ISD::XOR, N1.getValueType(), N1, 853 getConstant(1, N1.getValueType())), N3); 854 } else if (N3C) { 855 if (N3C->getValue()) // select C, X, 1 -> ~C | X 856 return getNode(ISD::OR, VT, 857 getNode(ISD::XOR, N1.getValueType(), N1, 858 getConstant(1, N1.getValueType())), N2); 859 else // select C, X, 0 -> C & X 860 return getNode(ISD::AND, VT, N1, N2); 861 } 862 } 863 864 break; 865 case ISD::BRCOND: 866 if (N2C) 867 if (N2C->getValue()) // Unconditional branch 868 return getNode(ISD::BR, MVT::Other, N1, N3); 869 else 870 return N1; // Never-taken branch 871 break; 872 } 873 874 SDNode *N = new SDNode(Opcode, N1, N2, N3); 875 switch (Opcode) { 876 default: 877 N->setValueTypes(VT); 878 break; 879 case ISD::DYNAMIC_STACKALLOC: // DYNAMIC_STACKALLOC produces pointer and chain 880 N->setValueTypes(VT, MVT::Other); 881 break; 882 } 883 884 // FIXME: memoize NODES 885 AllNodes.push_back(N); 886 return SDOperand(N, 0); 887} 888 889SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 890 std::vector<SDOperand> &Children) { 891 switch (Children.size()) { 892 case 0: return getNode(Opcode, VT); 893 case 1: return getNode(Opcode, VT, Children[0]); 894 case 2: return getNode(Opcode, VT, Children[0], Children[1]); 895 case 3: return getNode(Opcode, VT, Children[0], Children[1], Children[2]); 896 default: 897 // FIXME: MEMOIZE!! 898 SDNode *N = new SDNode(Opcode, Children); 899 if (Opcode != ISD::ADD_PARTS && Opcode != ISD::SUB_PARTS) { 900 N->setValueTypes(VT); 901 } else { 902 std::vector<MVT::ValueType> V(N->getNumOperands()/2, VT); 903 N->setValueTypes(V); 904 } 905 AllNodes.push_back(N); 906 return SDOperand(N, 0); 907 } 908} 909 910SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,SDOperand N1, 911 MVT::ValueType EVT) { 912 913 switch (Opcode) { 914 default: assert(0 && "Bad opcode for this accessor!"); 915 case ISD::FP_ROUND_INREG: 916 assert(VT == N1.getValueType() && "Not an inreg round!"); 917 assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) && 918 "Cannot FP_ROUND_INREG integer types"); 919 if (EVT == VT) return N1; // Not actually rounding 920 assert(EVT < VT && "Not rounding down!"); 921 break; 922 case ISD::ZERO_EXTEND_INREG: 923 case ISD::SIGN_EXTEND_INREG: 924 assert(VT == N1.getValueType() && "Not an inreg extend!"); 925 assert(MVT::isInteger(VT) && MVT::isInteger(EVT) && 926 "Cannot *_EXTEND_INREG FP types"); 927 if (EVT == VT) return N1; // Not actually extending 928 assert(EVT < VT && "Not extending!"); 929 930 // If we are sign extending an extension, use the original source. 931 if (N1.getOpcode() == ISD::ZERO_EXTEND_INREG || 932 N1.getOpcode() == ISD::SIGN_EXTEND_INREG) { 933 if (N1.getOpcode() == Opcode && 934 cast<MVTSDNode>(N1)->getExtraValueType() <= EVT) 935 return N1; 936 } 937 938 break; 939 } 940 941 EVTStruct NN; 942 NN.Opcode = Opcode; 943 NN.VT = VT; 944 NN.EVT = EVT; 945 NN.Ops.push_back(N1); 946 947 SDNode *&N = MVTSDNodes[NN]; 948 if (N) return SDOperand(N, 0); 949 N = new MVTSDNode(Opcode, VT, N1, EVT); 950 AllNodes.push_back(N); 951 return SDOperand(N, 0); 952} 953 954SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,SDOperand N1, 955 SDOperand N2, MVT::ValueType EVT) { 956 switch (Opcode) { 957 default: assert(0 && "Bad opcode for this accessor!"); 958 case ISD::EXTLOAD: 959 case ISD::SEXTLOAD: 960 case ISD::ZEXTLOAD: 961 // If they are asking for an extending loat from/to the same thing, return a 962 // normal load. 963 if (VT == EVT) 964 return getNode(ISD::LOAD, VT, N1, N2); 965 assert(EVT < VT && "Should only be an extending load, not truncating!"); 966 assert((Opcode == ISD::EXTLOAD || MVT::isInteger(VT)) && 967 "Cannot sign/zero extend a FP load!"); 968 assert(MVT::isInteger(VT) == MVT::isInteger(EVT) && 969 "Cannot convert from FP to Int or Int -> FP!"); 970 break; 971 } 972 973 EVTStruct NN; 974 NN.Opcode = Opcode; 975 NN.VT = VT; 976 NN.EVT = EVT; 977 NN.Ops.push_back(N1); 978 NN.Ops.push_back(N2); 979 980 SDNode *&N = MVTSDNodes[NN]; 981 if (N) return SDOperand(N, 0); 982 N = new MVTSDNode(Opcode, VT, MVT::Other, N1, N2, EVT); 983 AllNodes.push_back(N); 984 return SDOperand(N, 0); 985} 986 987SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,SDOperand N1, 988 SDOperand N2, SDOperand N3, MVT::ValueType EVT) { 989 switch (Opcode) { 990 default: assert(0 && "Bad opcode for this accessor!"); 991 case ISD::TRUNCSTORE: 992#if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store 993 // If this is a truncating store of a constant, convert to the desired type 994 // and store it instead. 995 if (isa<Constant>(N1)) { 996 SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1); 997 if (isa<Constant>(Op)) 998 N1 = Op; 999 } 1000 // Also for ConstantFP? 1001#endif 1002 if (N1.getValueType() == EVT) // Normal store? 1003 return getNode(ISD::STORE, VT, N1, N2, N3); 1004 assert(N2.getValueType() > EVT && "Not a truncation?"); 1005 assert(MVT::isInteger(N2.getValueType()) == MVT::isInteger(EVT) && 1006 "Can't do FP-INT conversion!"); 1007 break; 1008 } 1009 1010 EVTStruct NN; 1011 NN.Opcode = Opcode; 1012 NN.VT = VT; 1013 NN.EVT = EVT; 1014 NN.Ops.push_back(N1); 1015 NN.Ops.push_back(N2); 1016 NN.Ops.push_back(N3); 1017 1018 SDNode *&N = MVTSDNodes[NN]; 1019 if (N) return SDOperand(N, 0); 1020 N = new MVTSDNode(Opcode, VT, N1, N2, N3, EVT); 1021 AllNodes.push_back(N); 1022 return SDOperand(N, 0); 1023} 1024 1025 1026/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 1027/// indicated value. This method ignores uses of other values defined by this 1028/// operation. 1029bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) { 1030 assert(Value < getNumValues() && "Bad value!"); 1031 1032 // If there is only one value, this is easy. 1033 if (getNumValues() == 1) 1034 return use_size() == NUses; 1035 if (Uses.size() < NUses) return false; 1036 1037 SDOperand TheValue(this, Value); 1038 1039 std::set<SDNode*> UsersHandled; 1040 1041 for (std::vector<SDNode*>::iterator UI = Uses.begin(), E = Uses.end(); 1042 UI != E; ++UI) { 1043 SDNode *User = *UI; 1044 if (User->getNumOperands() == 1 || 1045 UsersHandled.insert(User).second) // First time we've seen this? 1046 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 1047 if (User->getOperand(i) == TheValue) { 1048 if (NUses == 0) 1049 return false; // too many uses 1050 --NUses; 1051 } 1052 } 1053 1054 // Found exactly the right number of uses? 1055 return NUses == 0; 1056} 1057 1058 1059const char *SDNode::getOperationName() const { 1060 switch (getOpcode()) { 1061 default: return "<<Unknown>>"; 1062 case ISD::EntryToken: return "EntryToken"; 1063 case ISD::TokenFactor: return "TokenFactor"; 1064 case ISD::Constant: return "Constant"; 1065 case ISD::ConstantFP: return "ConstantFP"; 1066 case ISD::GlobalAddress: return "GlobalAddress"; 1067 case ISD::FrameIndex: return "FrameIndex"; 1068 case ISD::BasicBlock: return "BasicBlock"; 1069 case ISD::ExternalSymbol: return "ExternalSymbol"; 1070 case ISD::ConstantPool: return "ConstantPoolIndex"; 1071 case ISD::CopyToReg: return "CopyToReg"; 1072 case ISD::CopyFromReg: return "CopyFromReg"; 1073 case ISD::ImplicitDef: return "ImplicitDef"; 1074 1075 case ISD::ADD: return "add"; 1076 case ISD::SUB: return "sub"; 1077 case ISD::MUL: return "mul"; 1078 case ISD::SDIV: return "sdiv"; 1079 case ISD::UDIV: return "udiv"; 1080 case ISD::SREM: return "srem"; 1081 case ISD::UREM: return "urem"; 1082 case ISD::AND: return "and"; 1083 case ISD::OR: return "or"; 1084 case ISD::XOR: return "xor"; 1085 case ISD::SHL: return "shl"; 1086 case ISD::SRA: return "sra"; 1087 case ISD::SRL: return "srl"; 1088 1089 case ISD::SELECT: return "select"; 1090 case ISD::ADD_PARTS: return "add_parts"; 1091 case ISD::SUB_PARTS: return "sub_parts"; 1092 1093 // Conversion operators. 1094 case ISD::SIGN_EXTEND: return "sign_extend"; 1095 case ISD::ZERO_EXTEND: return "zero_extend"; 1096 case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg"; 1097 case ISD::ZERO_EXTEND_INREG: return "zero_extend_inreg"; 1098 case ISD::TRUNCATE: return "truncate"; 1099 case ISD::FP_ROUND: return "fp_round"; 1100 case ISD::FP_ROUND_INREG: return "fp_round_inreg"; 1101 case ISD::FP_EXTEND: return "fp_extend"; 1102 1103 case ISD::SINT_TO_FP: return "sint_to_fp"; 1104 case ISD::UINT_TO_FP: return "uint_to_fp"; 1105 case ISD::FP_TO_SINT: return "fp_to_sint"; 1106 case ISD::FP_TO_UINT: return "fp_to_uint"; 1107 1108 // Control flow instructions 1109 case ISD::BR: return "br"; 1110 case ISD::BRCOND: return "brcond"; 1111 case ISD::RET: return "ret"; 1112 case ISD::CALL: return "call"; 1113 case ISD::ADJCALLSTACKDOWN: return "adjcallstackdown"; 1114 case ISD::ADJCALLSTACKUP: return "adjcallstackup"; 1115 1116 // Other operators 1117 case ISD::LOAD: return "load"; 1118 case ISD::STORE: return "store"; 1119 case ISD::EXTLOAD: return "extload"; 1120 case ISD::SEXTLOAD: return "sextload"; 1121 case ISD::ZEXTLOAD: return "zextload"; 1122 case ISD::TRUNCSTORE: return "truncstore"; 1123 1124 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc"; 1125 case ISD::EXTRACT_ELEMENT: return "extract_element"; 1126 case ISD::BUILD_PAIR: return "build_pair"; 1127 case ISD::MEMSET: return "memset"; 1128 case ISD::MEMCPY: return "memcpy"; 1129 case ISD::MEMMOVE: return "memmove"; 1130 1131 case ISD::SETCC: 1132 const SetCCSDNode *SetCC = cast<SetCCSDNode>(this); 1133 switch (SetCC->getCondition()) { 1134 default: assert(0 && "Unknown setcc condition!"); 1135 case ISD::SETOEQ: return "setcc:setoeq"; 1136 case ISD::SETOGT: return "setcc:setogt"; 1137 case ISD::SETOGE: return "setcc:setoge"; 1138 case ISD::SETOLT: return "setcc:setolt"; 1139 case ISD::SETOLE: return "setcc:setole"; 1140 case ISD::SETONE: return "setcc:setone"; 1141 1142 case ISD::SETO: return "setcc:seto"; 1143 case ISD::SETUO: return "setcc:setuo"; 1144 case ISD::SETUEQ: return "setcc:setue"; 1145 case ISD::SETUGT: return "setcc:setugt"; 1146 case ISD::SETUGE: return "setcc:setuge"; 1147 case ISD::SETULT: return "setcc:setult"; 1148 case ISD::SETULE: return "setcc:setule"; 1149 case ISD::SETUNE: return "setcc:setune"; 1150 1151 case ISD::SETEQ: return "setcc:seteq"; 1152 case ISD::SETGT: return "setcc:setgt"; 1153 case ISD::SETGE: return "setcc:setge"; 1154 case ISD::SETLT: return "setcc:setlt"; 1155 case ISD::SETLE: return "setcc:setle"; 1156 case ISD::SETNE: return "setcc:setne"; 1157 } 1158 } 1159} 1160 1161void SDNode::dump() const { 1162 std::cerr << (void*)this << ": "; 1163 1164 for (unsigned i = 0, e = getNumValues(); i != e; ++i) { 1165 if (i) std::cerr << ","; 1166 if (getValueType(i) == MVT::Other) 1167 std::cerr << "ch"; 1168 else 1169 std::cerr << MVT::getValueTypeString(getValueType(i)); 1170 } 1171 std::cerr << " = " << getOperationName(); 1172 1173 std::cerr << " "; 1174 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 1175 if (i) std::cerr << ", "; 1176 std::cerr << (void*)getOperand(i).Val; 1177 if (unsigned RN = getOperand(i).ResNo) 1178 std::cerr << ":" << RN; 1179 } 1180 1181 if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { 1182 std::cerr << "<" << CSDN->getValue() << ">"; 1183 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { 1184 std::cerr << "<" << CSDN->getValue() << ">"; 1185 } else if (const GlobalAddressSDNode *GADN = 1186 dyn_cast<GlobalAddressSDNode>(this)) { 1187 std::cerr << "<"; 1188 WriteAsOperand(std::cerr, GADN->getGlobal()) << ">"; 1189 } else if (const FrameIndexSDNode *FIDN = 1190 dyn_cast<FrameIndexSDNode>(this)) { 1191 std::cerr << "<" << FIDN->getIndex() << ">"; 1192 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ 1193 std::cerr << "<" << CP->getIndex() << ">"; 1194 } else if (const BasicBlockSDNode *BBDN = 1195 dyn_cast<BasicBlockSDNode>(this)) { 1196 std::cerr << "<"; 1197 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); 1198 if (LBB) 1199 std::cerr << LBB->getName() << " "; 1200 std::cerr << (const void*)BBDN->getBasicBlock() << ">"; 1201 } else if (const RegSDNode *C2V = dyn_cast<RegSDNode>(this)) { 1202 std::cerr << "<reg #" << C2V->getReg() << ">"; 1203 } else if (const ExternalSymbolSDNode *ES = 1204 dyn_cast<ExternalSymbolSDNode>(this)) { 1205 std::cerr << "'" << ES->getSymbol() << "'"; 1206 } else if (const MVTSDNode *M = dyn_cast<MVTSDNode>(this)) { 1207 std::cerr << " - Ty = " << MVT::getValueTypeString(M->getExtraValueType()); 1208 } 1209} 1210 1211static void DumpNodes(SDNode *N, unsigned indent) { 1212 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 1213 if (N->getOperand(i).Val->hasOneUse()) 1214 DumpNodes(N->getOperand(i).Val, indent+2); 1215 else 1216 std::cerr << "\n" << std::string(indent+2, ' ') 1217 << (void*)N->getOperand(i).Val << ": <multiple use>"; 1218 1219 1220 std::cerr << "\n" << std::string(indent, ' '); 1221 N->dump(); 1222} 1223 1224void SelectionDAG::dump() const { 1225 std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; 1226 std::vector<SDNode*> Nodes(AllNodes); 1227 std::sort(Nodes.begin(), Nodes.end()); 1228 1229 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 1230 if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val) 1231 DumpNodes(Nodes[i], 2); 1232 } 1233 1234 DumpNodes(getRoot().Val, 2); 1235 1236 std::cerr << "\n\n"; 1237} 1238 1239