SelectionDAG.cpp revision 8c6f1ee5aa376118f1cb7b16b62994fc255eac56
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 "llvm/Support/MathExtras.h" 20#include "llvm/Target/MRegisterInfo.h" 21#include "llvm/Target/TargetLowering.h" 22#include "llvm/Target/TargetInstrInfo.h" 23#include "llvm/Target/TargetMachine.h" 24#include "llvm/ADT/StringExtras.h" 25#include <iostream> 26#include <set> 27#include <cmath> 28#include <algorithm> 29using namespace llvm; 30 31static bool isCommutativeBinOp(unsigned Opcode) { 32 switch (Opcode) { 33 case ISD::ADD: 34 case ISD::MUL: 35 case ISD::MULHU: 36 case ISD::MULHS: 37 case ISD::FADD: 38 case ISD::FMUL: 39 case ISD::AND: 40 case ISD::OR: 41 case ISD::XOR: return true; 42 default: return false; // FIXME: Need commutative info for user ops! 43 } 44} 45 46static bool isAssociativeBinOp(unsigned Opcode) { 47 switch (Opcode) { 48 case ISD::ADD: 49 case ISD::MUL: 50 case ISD::AND: 51 case ISD::OR: 52 case ISD::XOR: return true; 53 default: return false; // FIXME: Need associative info for user ops! 54 } 55} 56 57// isInvertibleForFree - Return true if there is no cost to emitting the logical 58// inverse of this node. 59static bool isInvertibleForFree(SDOperand N) { 60 if (isa<ConstantSDNode>(N.Val)) return true; 61 if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse()) 62 return true; 63 return false; 64} 65 66//===----------------------------------------------------------------------===// 67// ConstantFPSDNode Class 68//===----------------------------------------------------------------------===// 69 70/// isExactlyValue - We don't rely on operator== working on double values, as 71/// it returns true for things that are clearly not equal, like -0.0 and 0.0. 72/// As such, this method can be used to do an exact bit-for-bit comparison of 73/// two floating point values. 74bool ConstantFPSDNode::isExactlyValue(double V) const { 75 return DoubleToBits(V) == DoubleToBits(Value); 76} 77 78//===----------------------------------------------------------------------===// 79// ISD Class 80//===----------------------------------------------------------------------===// 81 82/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 83/// when given the operation for (X op Y). 84ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 85 // To perform this operation, we just need to swap the L and G bits of the 86 // operation. 87 unsigned OldL = (Operation >> 2) & 1; 88 unsigned OldG = (Operation >> 1) & 1; 89 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 90 (OldL << 1) | // New G bit 91 (OldG << 2)); // New L bit. 92} 93 94/// getSetCCInverse - Return the operation corresponding to !(X op Y), where 95/// 'op' is a valid SetCC operation. 96ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 97 unsigned Operation = Op; 98 if (isInteger) 99 Operation ^= 7; // Flip L, G, E bits, but not U. 100 else 101 Operation ^= 15; // Flip all of the condition bits. 102 if (Operation > ISD::SETTRUE2) 103 Operation &= ~8; // Don't let N and U bits get set. 104 return ISD::CondCode(Operation); 105} 106 107 108/// isSignedOp - For an integer comparison, return 1 if the comparison is a 109/// signed operation and 2 if the result is an unsigned comparison. Return zero 110/// if the operation does not depend on the sign of the input (setne and seteq). 111static int isSignedOp(ISD::CondCode Opcode) { 112 switch (Opcode) { 113 default: assert(0 && "Illegal integer setcc operation!"); 114 case ISD::SETEQ: 115 case ISD::SETNE: return 0; 116 case ISD::SETLT: 117 case ISD::SETLE: 118 case ISD::SETGT: 119 case ISD::SETGE: return 1; 120 case ISD::SETULT: 121 case ISD::SETULE: 122 case ISD::SETUGT: 123 case ISD::SETUGE: return 2; 124 } 125} 126 127/// getSetCCOrOperation - Return the result of a logical OR between different 128/// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 129/// returns SETCC_INVALID if it is not possible to represent the resultant 130/// comparison. 131ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 132 bool isInteger) { 133 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 134 // Cannot fold a signed integer setcc with an unsigned integer setcc. 135 return ISD::SETCC_INVALID; 136 137 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 138 139 // If the N and U bits get set then the resultant comparison DOES suddenly 140 // care about orderedness, and is true when ordered. 141 if (Op > ISD::SETTRUE2) 142 Op &= ~16; // Clear the N bit. 143 return ISD::CondCode(Op); 144} 145 146/// getSetCCAndOperation - Return the result of a logical AND between different 147/// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 148/// function returns zero if it is not possible to represent the resultant 149/// comparison. 150ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 151 bool isInteger) { 152 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 153 // Cannot fold a signed setcc with an unsigned setcc. 154 return ISD::SETCC_INVALID; 155 156 // Combine all of the condition bits. 157 return ISD::CondCode(Op1 & Op2); 158} 159 160const TargetMachine &SelectionDAG::getTarget() const { 161 return TLI.getTargetMachine(); 162} 163 164//===----------------------------------------------------------------------===// 165// SelectionDAG Class 166//===----------------------------------------------------------------------===// 167 168/// RemoveDeadNodes - This method deletes all unreachable nodes in the 169/// SelectionDAG, including nodes (like loads) that have uses of their token 170/// chain but no other uses and no side effect. If a node is passed in as an 171/// argument, it is used as the seed for node deletion. 172void SelectionDAG::RemoveDeadNodes(SDNode *N) { 173 // Create a dummy node (which is not added to allnodes), that adds a reference 174 // to the root node, preventing it from being deleted. 175 HandleSDNode Dummy(getRoot()); 176 177 bool MadeChange = false; 178 179 // If we have a hint to start from, use it. 180 if (N && N->use_empty()) { 181 DestroyDeadNode(N); 182 MadeChange = true; 183 } 184 185 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) 186 if (I->use_empty() && I->getOpcode() != 65535) { 187 // Node is dead, recursively delete newly dead uses. 188 DestroyDeadNode(I); 189 MadeChange = true; 190 } 191 192 // Walk the nodes list, removing the nodes we've marked as dead. 193 if (MadeChange) { 194 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ) { 195 SDNode *N = I++; 196 if (N->use_empty()) 197 AllNodes.erase(N); 198 } 199 } 200 201 // If the root changed (e.g. it was a dead load, update the root). 202 setRoot(Dummy.getValue()); 203} 204 205/// DestroyDeadNode - We know that N is dead. Nuke it from the CSE maps for the 206/// graph. If it is the last user of any of its operands, recursively process 207/// them the same way. 208/// 209void SelectionDAG::DestroyDeadNode(SDNode *N) { 210 // Okay, we really are going to delete this node. First take this out of the 211 // appropriate CSE map. 212 RemoveNodeFromCSEMaps(N); 213 214 // Next, brutally remove the operand list. This is safe to do, as there are 215 // no cycles in the graph. 216 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 217 SDNode *O = I->Val; 218 O->removeUser(N); 219 220 // Now that we removed this operand, see if there are no uses of it left. 221 if (O->use_empty()) 222 DestroyDeadNode(O); 223 } 224 delete[] N->OperandList; 225 N->OperandList = 0; 226 N->NumOperands = 0; 227 228 // Mark the node as dead. 229 N->MorphNodeTo(65535); 230} 231 232void SelectionDAG::DeleteNode(SDNode *N) { 233 assert(N->use_empty() && "Cannot delete a node that is not dead!"); 234 235 // First take this out of the appropriate CSE map. 236 RemoveNodeFromCSEMaps(N); 237 238 // Finally, remove uses due to operands of this node, remove from the 239 // AllNodes list, and delete the node. 240 DeleteNodeNotInCSEMaps(N); 241} 242 243void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { 244 245 // Remove it from the AllNodes list. 246 AllNodes.remove(N); 247 248 // Drop all of the operands and decrement used nodes use counts. 249 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) 250 I->Val->removeUser(N); 251 delete[] N->OperandList; 252 N->OperandList = 0; 253 N->NumOperands = 0; 254 255 delete N; 256} 257 258/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that 259/// correspond to it. This is useful when we're about to delete or repurpose 260/// the node. We don't want future request for structurally identical nodes 261/// to return N anymore. 262void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { 263 bool Erased = false; 264 switch (N->getOpcode()) { 265 case ISD::HANDLENODE: return; // noop. 266 case ISD::Constant: 267 Erased = Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(), 268 N->getValueType(0))); 269 break; 270 case ISD::TargetConstant: 271 Erased = TargetConstants.erase(std::make_pair( 272 cast<ConstantSDNode>(N)->getValue(), 273 N->getValueType(0))); 274 break; 275 case ISD::ConstantFP: { 276 uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue()); 277 Erased = ConstantFPs.erase(std::make_pair(V, N->getValueType(0))); 278 break; 279 } 280 case ISD::STRING: 281 Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue()); 282 break; 283 case ISD::CONDCODE: 284 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] && 285 "Cond code doesn't exist!"); 286 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0; 287 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0; 288 break; 289 case ISD::GlobalAddress: { 290 GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N); 291 Erased = GlobalValues.erase(std::make_pair(GN->getGlobal(), 292 GN->getOffset())); 293 break; 294 } 295 case ISD::TargetGlobalAddress: { 296 GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N); 297 Erased =TargetGlobalValues.erase(std::make_pair(GN->getGlobal(), 298 GN->getOffset())); 299 break; 300 } 301 case ISD::FrameIndex: 302 Erased = FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex()); 303 break; 304 case ISD::TargetFrameIndex: 305 Erased = TargetFrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex()); 306 break; 307 case ISD::ConstantPool: 308 Erased = ConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->get()); 309 break; 310 case ISD::TargetConstantPool: 311 Erased =TargetConstantPoolIndices.erase(cast<ConstantPoolSDNode>(N)->get()); 312 break; 313 case ISD::BasicBlock: 314 Erased = BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock()); 315 break; 316 case ISD::ExternalSymbol: 317 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 318 break; 319 case ISD::TargetExternalSymbol: 320 Erased = TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 321 break; 322 case ISD::VALUETYPE: 323 Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0; 324 ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0; 325 break; 326 case ISD::Register: 327 Erased = RegNodes.erase(std::make_pair(cast<RegisterSDNode>(N)->getReg(), 328 N->getValueType(0))); 329 break; 330 case ISD::SRCVALUE: { 331 SrcValueSDNode *SVN = cast<SrcValueSDNode>(N); 332 Erased =ValueNodes.erase(std::make_pair(SVN->getValue(), SVN->getOffset())); 333 break; 334 } 335 case ISD::LOAD: 336 Erased = Loads.erase(std::make_pair(N->getOperand(1), 337 std::make_pair(N->getOperand(0), 338 N->getValueType(0)))); 339 break; 340 default: 341 if (N->getNumValues() == 1) { 342 if (N->getNumOperands() == 0) { 343 Erased = NullaryOps.erase(std::make_pair(N->getOpcode(), 344 N->getValueType(0))); 345 } else if (N->getNumOperands() == 1) { 346 Erased = 347 UnaryOps.erase(std::make_pair(N->getOpcode(), 348 std::make_pair(N->getOperand(0), 349 N->getValueType(0)))); 350 } else if (N->getNumOperands() == 2) { 351 Erased = 352 BinaryOps.erase(std::make_pair(N->getOpcode(), 353 std::make_pair(N->getOperand(0), 354 N->getOperand(1)))); 355 } else { 356 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 357 Erased = 358 OneResultNodes.erase(std::make_pair(N->getOpcode(), 359 std::make_pair(N->getValueType(0), 360 Ops))); 361 } 362 } else { 363 // Remove the node from the ArbitraryNodes map. 364 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 365 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 366 Erased = 367 ArbitraryNodes.erase(std::make_pair(N->getOpcode(), 368 std::make_pair(RV, Ops))); 369 } 370 break; 371 } 372#ifndef NDEBUG 373 // Verify that the node was actually in one of the CSE maps, unless it has a 374 // flag result (which cannot be CSE'd) or is one of the special cases that are 375 // not subject to CSE. 376 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && 377 N->getOpcode() != ISD::CALL && N->getOpcode() != ISD::CALLSEQ_START && 378 N->getOpcode() != ISD::CALLSEQ_END && !N->isTargetOpcode()) { 379 380 N->dump(); 381 assert(0 && "Node is not in map!"); 382 } 383#endif 384} 385 386/// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps. It 387/// has been taken out and modified in some way. If the specified node already 388/// exists in the CSE maps, do not modify the maps, but return the existing node 389/// instead. If it doesn't exist, add it and return null. 390/// 391SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { 392 assert(N->getNumOperands() && "This is a leaf node!"); 393 if (N->getOpcode() == ISD::CALLSEQ_START || 394 N->getOpcode() == ISD::CALLSEQ_END || 395 N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 396 return 0; // Never add these nodes. 397 398 // Check that remaining values produced are not flags. 399 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 400 if (N->getValueType(i) == MVT::Flag) 401 return 0; // Never CSE anything that produces a flag. 402 403 if (N->getNumValues() == 1) { 404 if (N->getNumOperands() == 1) { 405 SDNode *&U = UnaryOps[std::make_pair(N->getOpcode(), 406 std::make_pair(N->getOperand(0), 407 N->getValueType(0)))]; 408 if (U) return U; 409 U = N; 410 } else if (N->getNumOperands() == 2) { 411 SDNode *&B = BinaryOps[std::make_pair(N->getOpcode(), 412 std::make_pair(N->getOperand(0), 413 N->getOperand(1)))]; 414 if (B) return B; 415 B = N; 416 } else { 417 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 418 SDNode *&ORN = OneResultNodes[std::make_pair(N->getOpcode(), 419 std::make_pair(N->getValueType(0), Ops))]; 420 if (ORN) return ORN; 421 ORN = N; 422 } 423 } else { 424 if (N->getOpcode() == ISD::LOAD) { 425 SDNode *&L = Loads[std::make_pair(N->getOperand(1), 426 std::make_pair(N->getOperand(0), 427 N->getValueType(0)))]; 428 if (L) return L; 429 L = N; 430 } else { 431 // Remove the node from the ArbitraryNodes map. 432 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 433 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 434 SDNode *&AN = ArbitraryNodes[std::make_pair(N->getOpcode(), 435 std::make_pair(RV, Ops))]; 436 if (AN) return AN; 437 AN = N; 438 } 439 } 440 return 0; 441} 442 443 444 445SelectionDAG::~SelectionDAG() { 446 while (!AllNodes.empty()) { 447 SDNode *N = AllNodes.begin(); 448 delete [] N->OperandList; 449 N->OperandList = 0; 450 N->NumOperands = 0; 451 AllNodes.pop_front(); 452 } 453} 454 455SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) { 456 if (Op.getValueType() == VT) return Op; 457 int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT)); 458 return getNode(ISD::AND, Op.getValueType(), Op, 459 getConstant(Imm, Op.getValueType())); 460} 461 462SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) { 463 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 464 // Mask out any bits that are not valid for this constant. 465 if (VT != MVT::i64) 466 Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; 467 468 SDNode *&N = Constants[std::make_pair(Val, VT)]; 469 if (N) return SDOperand(N, 0); 470 N = new ConstantSDNode(false, Val, VT); 471 AllNodes.push_back(N); 472 return SDOperand(N, 0); 473} 474 475SDOperand SelectionDAG::getString(const std::string &Val) { 476 StringSDNode *&N = StringNodes[Val]; 477 if (!N) { 478 N = new StringSDNode(Val); 479 AllNodes.push_back(N); 480 } 481 return SDOperand(N, 0); 482} 483 484SDOperand SelectionDAG::getTargetConstant(uint64_t Val, MVT::ValueType VT) { 485 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 486 // Mask out any bits that are not valid for this constant. 487 if (VT != MVT::i64) 488 Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; 489 490 SDNode *&N = TargetConstants[std::make_pair(Val, VT)]; 491 if (N) return SDOperand(N, 0); 492 N = new ConstantSDNode(true, Val, VT); 493 AllNodes.push_back(N); 494 return SDOperand(N, 0); 495} 496 497SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) { 498 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 499 if (VT == MVT::f32) 500 Val = (float)Val; // Mask out extra precision. 501 502 // Do the map lookup using the actual bit pattern for the floating point 503 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 504 // we don't have issues with SNANs. 505 SDNode *&N = ConstantFPs[std::make_pair(DoubleToBits(Val), VT)]; 506 if (N) return SDOperand(N, 0); 507 N = new ConstantFPSDNode(Val, VT); 508 AllNodes.push_back(N); 509 return SDOperand(N, 0); 510} 511 512SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, 513 MVT::ValueType VT, int offset) { 514 SDNode *&N = GlobalValues[std::make_pair(GV, offset)]; 515 if (N) return SDOperand(N, 0); 516 N = new GlobalAddressSDNode(false, GV, VT, offset); 517 AllNodes.push_back(N); 518 return SDOperand(N, 0); 519} 520 521SDOperand SelectionDAG::getTargetGlobalAddress(const GlobalValue *GV, 522 MVT::ValueType VT, int offset) { 523 SDNode *&N = TargetGlobalValues[std::make_pair(GV, offset)]; 524 if (N) return SDOperand(N, 0); 525 N = new GlobalAddressSDNode(true, GV, VT, offset); 526 AllNodes.push_back(N); 527 return SDOperand(N, 0); 528} 529 530SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) { 531 SDNode *&N = FrameIndices[FI]; 532 if (N) return SDOperand(N, 0); 533 N = new FrameIndexSDNode(FI, VT, false); 534 AllNodes.push_back(N); 535 return SDOperand(N, 0); 536} 537 538SDOperand SelectionDAG::getTargetFrameIndex(int FI, MVT::ValueType VT) { 539 SDNode *&N = TargetFrameIndices[FI]; 540 if (N) return SDOperand(N, 0); 541 N = new FrameIndexSDNode(FI, VT, true); 542 AllNodes.push_back(N); 543 return SDOperand(N, 0); 544} 545 546SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT) { 547 SDNode *&N = ConstantPoolIndices[C]; 548 if (N) return SDOperand(N, 0); 549 N = new ConstantPoolSDNode(C, VT, false); 550 AllNodes.push_back(N); 551 return SDOperand(N, 0); 552} 553 554SDOperand SelectionDAG::getTargetConstantPool(Constant *C, MVT::ValueType VT) { 555 SDNode *&N = TargetConstantPoolIndices[C]; 556 if (N) return SDOperand(N, 0); 557 N = new ConstantPoolSDNode(C, VT, true); 558 AllNodes.push_back(N); 559 return SDOperand(N, 0); 560} 561 562SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 563 SDNode *&N = BBNodes[MBB]; 564 if (N) return SDOperand(N, 0); 565 N = new BasicBlockSDNode(MBB); 566 AllNodes.push_back(N); 567 return SDOperand(N, 0); 568} 569 570SDOperand SelectionDAG::getValueType(MVT::ValueType VT) { 571 if ((unsigned)VT >= ValueTypeNodes.size()) 572 ValueTypeNodes.resize(VT+1); 573 if (ValueTypeNodes[VT] == 0) { 574 ValueTypeNodes[VT] = new VTSDNode(VT); 575 AllNodes.push_back(ValueTypeNodes[VT]); 576 } 577 578 return SDOperand(ValueTypeNodes[VT], 0); 579} 580 581SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) { 582 SDNode *&N = ExternalSymbols[Sym]; 583 if (N) return SDOperand(N, 0); 584 N = new ExternalSymbolSDNode(false, Sym, VT); 585 AllNodes.push_back(N); 586 return SDOperand(N, 0); 587} 588 589SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym, MVT::ValueType VT) { 590 SDNode *&N = TargetExternalSymbols[Sym]; 591 if (N) return SDOperand(N, 0); 592 N = new ExternalSymbolSDNode(true, Sym, VT); 593 AllNodes.push_back(N); 594 return SDOperand(N, 0); 595} 596 597SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) { 598 if ((unsigned)Cond >= CondCodeNodes.size()) 599 CondCodeNodes.resize(Cond+1); 600 601 if (CondCodeNodes[Cond] == 0) { 602 CondCodeNodes[Cond] = new CondCodeSDNode(Cond); 603 AllNodes.push_back(CondCodeNodes[Cond]); 604 } 605 return SDOperand(CondCodeNodes[Cond], 0); 606} 607 608SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) { 609 RegisterSDNode *&Reg = RegNodes[std::make_pair(RegNo, VT)]; 610 if (!Reg) { 611 Reg = new RegisterSDNode(RegNo, VT); 612 AllNodes.push_back(Reg); 613 } 614 return SDOperand(Reg, 0); 615} 616 617SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1, 618 SDOperand N2, ISD::CondCode Cond) { 619 // These setcc operations always fold. 620 switch (Cond) { 621 default: break; 622 case ISD::SETFALSE: 623 case ISD::SETFALSE2: return getConstant(0, VT); 624 case ISD::SETTRUE: 625 case ISD::SETTRUE2: return getConstant(1, VT); 626 } 627 628 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) { 629 uint64_t C2 = N2C->getValue(); 630 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 631 uint64_t C1 = N1C->getValue(); 632 633 // Sign extend the operands if required 634 if (ISD::isSignedIntSetCC(Cond)) { 635 C1 = N1C->getSignExtended(); 636 C2 = N2C->getSignExtended(); 637 } 638 639 switch (Cond) { 640 default: assert(0 && "Unknown integer setcc!"); 641 case ISD::SETEQ: return getConstant(C1 == C2, VT); 642 case ISD::SETNE: return getConstant(C1 != C2, VT); 643 case ISD::SETULT: return getConstant(C1 < C2, VT); 644 case ISD::SETUGT: return getConstant(C1 > C2, VT); 645 case ISD::SETULE: return getConstant(C1 <= C2, VT); 646 case ISD::SETUGE: return getConstant(C1 >= C2, VT); 647 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, VT); 648 case ISD::SETGT: return getConstant((int64_t)C1 > (int64_t)C2, VT); 649 case ISD::SETLE: return getConstant((int64_t)C1 <= (int64_t)C2, VT); 650 case ISD::SETGE: return getConstant((int64_t)C1 >= (int64_t)C2, VT); 651 } 652 } else { 653 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 654 if (N1.getOpcode() == ISD::ZERO_EXTEND) { 655 unsigned InSize = MVT::getSizeInBits(N1.getOperand(0).getValueType()); 656 657 // If the comparison constant has bits in the upper part, the 658 // zero-extended value could never match. 659 if (C2 & (~0ULL << InSize)) { 660 unsigned VSize = MVT::getSizeInBits(N1.getValueType()); 661 switch (Cond) { 662 case ISD::SETUGT: 663 case ISD::SETUGE: 664 case ISD::SETEQ: return getConstant(0, VT); 665 case ISD::SETULT: 666 case ISD::SETULE: 667 case ISD::SETNE: return getConstant(1, VT); 668 case ISD::SETGT: 669 case ISD::SETGE: 670 // True if the sign bit of C2 is set. 671 return getConstant((C2 & (1ULL << VSize)) != 0, VT); 672 case ISD::SETLT: 673 case ISD::SETLE: 674 // True if the sign bit of C2 isn't set. 675 return getConstant((C2 & (1ULL << VSize)) == 0, VT); 676 default: 677 break; 678 } 679 } 680 681 // Otherwise, we can perform the comparison with the low bits. 682 switch (Cond) { 683 case ISD::SETEQ: 684 case ISD::SETNE: 685 case ISD::SETUGT: 686 case ISD::SETUGE: 687 case ISD::SETULT: 688 case ISD::SETULE: 689 return getSetCC(VT, N1.getOperand(0), 690 getConstant(C2, N1.getOperand(0).getValueType()), 691 Cond); 692 default: 693 break; // todo, be more careful with signed comparisons 694 } 695 } else if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG && 696 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 697 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N1.getOperand(1))->getVT(); 698 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); 699 MVT::ValueType ExtDstTy = N1.getValueType(); 700 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); 701 702 // If the extended part has any inconsistent bits, it cannot ever 703 // compare equal. In other words, they have to be all ones or all 704 // zeros. 705 uint64_t ExtBits = 706 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); 707 if ((C2 & ExtBits) != 0 && (C2 & ExtBits) != ExtBits) 708 return getConstant(Cond == ISD::SETNE, VT); 709 710 // Otherwise, make this a use of a zext. 711 return getSetCC(VT, getZeroExtendInReg(N1.getOperand(0), ExtSrcTy), 712 getConstant(C2 & (~0ULL>>(64-ExtSrcTyBits)), ExtDstTy), 713 Cond); 714 } 715 716 uint64_t MinVal, MaxVal; 717 unsigned OperandBitSize = MVT::getSizeInBits(N2C->getValueType(0)); 718 if (ISD::isSignedIntSetCC(Cond)) { 719 MinVal = 1ULL << (OperandBitSize-1); 720 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. 721 MaxVal = ~0ULL >> (65-OperandBitSize); 722 else 723 MaxVal = 0; 724 } else { 725 MinVal = 0; 726 MaxVal = ~0ULL >> (64-OperandBitSize); 727 } 728 729 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 730 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 731 if (C2 == MinVal) return getConstant(1, VT); // X >= MIN --> true 732 --C2; // X >= C1 --> X > (C1-1) 733 return getSetCC(VT, N1, getConstant(C2, N2.getValueType()), 734 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 735 } 736 737 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 738 if (C2 == MaxVal) return getConstant(1, VT); // X <= MAX --> true 739 ++C2; // X <= C1 --> X < (C1+1) 740 return getSetCC(VT, N1, getConstant(C2, N2.getValueType()), 741 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 742 } 743 744 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal) 745 return getConstant(0, VT); // X < MIN --> false 746 747 // Canonicalize setgt X, Min --> setne X, Min 748 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MinVal) 749 return getSetCC(VT, N1, N2, ISD::SETNE); 750 751 // If we have setult X, 1, turn it into seteq X, 0 752 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal+1) 753 return getSetCC(VT, N1, getConstant(MinVal, N1.getValueType()), 754 ISD::SETEQ); 755 // If we have setugt X, Max-1, turn it into seteq X, Max 756 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MaxVal-1) 757 return getSetCC(VT, N1, getConstant(MaxVal, N1.getValueType()), 758 ISD::SETEQ); 759 760 // If we have "setcc X, C1", check to see if we can shrink the immediate 761 // by changing cc. 762 763 // SETUGT X, SINTMAX -> SETLT X, 0 764 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 765 C2 == (~0ULL >> (65-OperandBitSize))) 766 return getSetCC(VT, N1, getConstant(0, N2.getValueType()), ISD::SETLT); 767 768 // FIXME: Implement the rest of these. 769 770 771 // Fold bit comparisons when we can. 772 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 773 VT == N1.getValueType() && N1.getOpcode() == ISD::AND) 774 if (ConstantSDNode *AndRHS = 775 dyn_cast<ConstantSDNode>(N1.getOperand(1))) { 776 if (Cond == ISD::SETNE && C2 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 777 // Perform the xform if the AND RHS is a single bit. 778 if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) { 779 return getNode(ISD::SRL, VT, N1, 780 getConstant(Log2_64(AndRHS->getValue()), 781 TLI.getShiftAmountTy())); 782 } 783 } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) { 784 // (X & 8) == 8 --> (X & 8) >> 3 785 // Perform the xform if C2 is a single bit. 786 if ((C2 & (C2-1)) == 0) { 787 return getNode(ISD::SRL, VT, N1, 788 getConstant(Log2_64(C2),TLI.getShiftAmountTy())); 789 } 790 } 791 } 792 } 793 } else if (isa<ConstantSDNode>(N1.Val)) { 794 // Ensure that the constant occurs on the RHS. 795 return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 796 } 797 798 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) 799 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) { 800 double C1 = N1C->getValue(), C2 = N2C->getValue(); 801 802 switch (Cond) { 803 default: break; // FIXME: Implement the rest of these! 804 case ISD::SETEQ: return getConstant(C1 == C2, VT); 805 case ISD::SETNE: return getConstant(C1 != C2, VT); 806 case ISD::SETLT: return getConstant(C1 < C2, VT); 807 case ISD::SETGT: return getConstant(C1 > C2, VT); 808 case ISD::SETLE: return getConstant(C1 <= C2, VT); 809 case ISD::SETGE: return getConstant(C1 >= C2, VT); 810 } 811 } else { 812 // Ensure that the constant occurs on the RHS. 813 return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 814 } 815 816 // Could not fold it. 817 return SDOperand(); 818} 819 820/// getNode - Gets or creates the specified node. 821/// 822SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { 823 SDNode *&N = NullaryOps[std::make_pair(Opcode, VT)]; 824 if (!N) { 825 N = new SDNode(Opcode, VT); 826 AllNodes.push_back(N); 827 } 828 return SDOperand(N, 0); 829} 830 831SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 832 SDOperand Operand) { 833 unsigned Tmp1; 834 // Constant fold unary operations with an integer constant operand. 835 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) { 836 uint64_t Val = C->getValue(); 837 switch (Opcode) { 838 default: break; 839 case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT); 840 case ISD::ANY_EXTEND: 841 case ISD::ZERO_EXTEND: return getConstant(Val, VT); 842 case ISD::TRUNCATE: return getConstant(Val, VT); 843 case ISD::SINT_TO_FP: return getConstantFP(C->getSignExtended(), VT); 844 case ISD::UINT_TO_FP: return getConstantFP(C->getValue(), VT); 845 case ISD::BIT_CONVERT: 846 if (VT == MVT::f32) { 847 assert(C->getValueType(0) == MVT::i32 && "Invalid bit_convert!"); 848 return getConstantFP(BitsToFloat(Val), VT); 849 } else if (VT == MVT::f64) { 850 assert(C->getValueType(0) == MVT::i64 && "Invalid bit_convert!"); 851 return getConstantFP(BitsToDouble(Val), VT); 852 } 853 break; 854 case ISD::BSWAP: 855 switch(VT) { 856 default: assert(0 && "Invalid bswap!"); break; 857 case MVT::i16: return getConstant(ByteSwap_16((unsigned short)Val), VT); 858 case MVT::i32: return getConstant(ByteSwap_32((unsigned)Val), VT); 859 case MVT::i64: return getConstant(ByteSwap_64(Val), VT); 860 } 861 break; 862 case ISD::CTPOP: 863 switch(VT) { 864 default: assert(0 && "Invalid ctpop!"); break; 865 case MVT::i1: return getConstant(Val != 0, VT); 866 case MVT::i8: 867 Tmp1 = (unsigned)Val & 0xFF; 868 return getConstant(CountPopulation_32(Tmp1), VT); 869 case MVT::i16: 870 Tmp1 = (unsigned)Val & 0xFFFF; 871 return getConstant(CountPopulation_32(Tmp1), VT); 872 case MVT::i32: 873 return getConstant(CountPopulation_32((unsigned)Val), VT); 874 case MVT::i64: 875 return getConstant(CountPopulation_64(Val), VT); 876 } 877 case ISD::CTLZ: 878 switch(VT) { 879 default: assert(0 && "Invalid ctlz!"); break; 880 case MVT::i1: return getConstant(Val == 0, VT); 881 case MVT::i8: 882 Tmp1 = (unsigned)Val & 0xFF; 883 return getConstant(CountLeadingZeros_32(Tmp1)-24, VT); 884 case MVT::i16: 885 Tmp1 = (unsigned)Val & 0xFFFF; 886 return getConstant(CountLeadingZeros_32(Tmp1)-16, VT); 887 case MVT::i32: 888 return getConstant(CountLeadingZeros_32((unsigned)Val), VT); 889 case MVT::i64: 890 return getConstant(CountLeadingZeros_64(Val), VT); 891 } 892 case ISD::CTTZ: 893 switch(VT) { 894 default: assert(0 && "Invalid cttz!"); break; 895 case MVT::i1: return getConstant(Val == 0, VT); 896 case MVT::i8: 897 Tmp1 = (unsigned)Val | 0x100; 898 return getConstant(CountTrailingZeros_32(Tmp1), VT); 899 case MVT::i16: 900 Tmp1 = (unsigned)Val | 0x10000; 901 return getConstant(CountTrailingZeros_32(Tmp1), VT); 902 case MVT::i32: 903 return getConstant(CountTrailingZeros_32((unsigned)Val), VT); 904 case MVT::i64: 905 return getConstant(CountTrailingZeros_64(Val), VT); 906 } 907 } 908 } 909 910 // Constant fold unary operations with an floating point constant operand. 911 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) 912 switch (Opcode) { 913 case ISD::FNEG: 914 return getConstantFP(-C->getValue(), VT); 915 case ISD::FABS: 916 return getConstantFP(fabs(C->getValue()), VT); 917 case ISD::FP_ROUND: 918 case ISD::FP_EXTEND: 919 return getConstantFP(C->getValue(), VT); 920 case ISD::FP_TO_SINT: 921 return getConstant((int64_t)C->getValue(), VT); 922 case ISD::FP_TO_UINT: 923 return getConstant((uint64_t)C->getValue(), VT); 924 case ISD::BIT_CONVERT: 925 if (VT == MVT::i32) { 926 assert(C->getValueType(0) == MVT::f32 && "Invalid bit_convert!"); 927 return getConstant(FloatToBits(C->getValue()), VT); 928 } else if (VT == MVT::i64) { 929 assert(C->getValueType(0) == MVT::f64 && "Invalid bit_convert!"); 930 return getConstant(DoubleToBits(C->getValue()), VT); 931 } 932 break; 933 } 934 935 unsigned OpOpcode = Operand.Val->getOpcode(); 936 switch (Opcode) { 937 case ISD::TokenFactor: 938 return Operand; // Factor of one node? No factor. 939 case ISD::SIGN_EXTEND: 940 if (Operand.getValueType() == VT) return Operand; // noop extension 941 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 942 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 943 break; 944 case ISD::ZERO_EXTEND: 945 if (Operand.getValueType() == VT) return Operand; // noop extension 946 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x) 947 return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0)); 948 break; 949 case ISD::ANY_EXTEND: 950 if (Operand.getValueType() == VT) return Operand; // noop extension 951 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) 952 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x) 953 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 954 break; 955 case ISD::TRUNCATE: 956 if (Operand.getValueType() == VT) return Operand; // noop truncate 957 if (OpOpcode == ISD::TRUNCATE) 958 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 959 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || 960 OpOpcode == ISD::ANY_EXTEND) { 961 // If the source is smaller than the dest, we still need an extend. 962 if (Operand.Val->getOperand(0).getValueType() < VT) 963 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 964 else if (Operand.Val->getOperand(0).getValueType() > VT) 965 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 966 else 967 return Operand.Val->getOperand(0); 968 } 969 break; 970 case ISD::BIT_CONVERT: 971 // Basic sanity checking. 972 assert(MVT::getSizeInBits(VT)==MVT::getSizeInBits(Operand.getValueType()) && 973 "Cannot BIT_CONVERT between two different types!"); 974 if (VT == Operand.getValueType()) return Operand; // noop conversion. 975 if (OpOpcode == ISD::BIT_CONVERT) // bitconv(bitconv(x)) -> bitconv(x) 976 return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0)); 977 break; 978 case ISD::FNEG: 979 if (OpOpcode == ISD::FSUB) // -(X-Y) -> (Y-X) 980 return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1), 981 Operand.Val->getOperand(0)); 982 if (OpOpcode == ISD::FNEG) // --X -> X 983 return Operand.Val->getOperand(0); 984 break; 985 case ISD::FABS: 986 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X) 987 return getNode(ISD::FABS, VT, Operand.Val->getOperand(0)); 988 break; 989 } 990 991 SDNode *N; 992 if (VT != MVT::Flag) { // Don't CSE flag producing nodes 993 SDNode *&E = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))]; 994 if (E) return SDOperand(E, 0); 995 E = N = new SDNode(Opcode, Operand); 996 } else { 997 N = new SDNode(Opcode, Operand); 998 } 999 N->setValueTypes(VT); 1000 AllNodes.push_back(N); 1001 return SDOperand(N, 0); 1002} 1003 1004 1005 1006SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1007 SDOperand N1, SDOperand N2) { 1008#ifndef NDEBUG 1009 switch (Opcode) { 1010 case ISD::TokenFactor: 1011 assert(VT == MVT::Other && N1.getValueType() == MVT::Other && 1012 N2.getValueType() == MVT::Other && "Invalid token factor!"); 1013 break; 1014 case ISD::AND: 1015 case ISD::OR: 1016 case ISD::XOR: 1017 case ISD::UDIV: 1018 case ISD::UREM: 1019 case ISD::MULHU: 1020 case ISD::MULHS: 1021 assert(MVT::isInteger(VT) && "This operator does not apply to FP types!"); 1022 // fall through 1023 case ISD::ADD: 1024 case ISD::SUB: 1025 case ISD::MUL: 1026 case ISD::SDIV: 1027 case ISD::SREM: 1028 assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops"); 1029 // fall through. 1030 case ISD::FADD: 1031 case ISD::FSUB: 1032 case ISD::FMUL: 1033 case ISD::FDIV: 1034 case ISD::FREM: 1035 assert(N1.getValueType() == N2.getValueType() && 1036 N1.getValueType() == VT && "Binary operator types must match!"); 1037 break; 1038 1039 case ISD::SHL: 1040 case ISD::SRA: 1041 case ISD::SRL: 1042 case ISD::ROTL: 1043 case ISD::ROTR: 1044 assert(VT == N1.getValueType() && 1045 "Shift operators return type must be the same as their first arg"); 1046 assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) && 1047 VT != MVT::i1 && "Shifts only work on integers"); 1048 break; 1049 case ISD::FP_ROUND_INREG: { 1050 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1051 assert(VT == N1.getValueType() && "Not an inreg round!"); 1052 assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) && 1053 "Cannot FP_ROUND_INREG integer types"); 1054 assert(EVT <= VT && "Not rounding down!"); 1055 break; 1056 } 1057 case ISD::AssertSext: 1058 case ISD::AssertZext: 1059 case ISD::SIGN_EXTEND_INREG: { 1060 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1061 assert(VT == N1.getValueType() && "Not an inreg extend!"); 1062 assert(MVT::isInteger(VT) && MVT::isInteger(EVT) && 1063 "Cannot *_EXTEND_INREG FP types"); 1064 assert(EVT <= VT && "Not extending!"); 1065 } 1066 1067 default: break; 1068 } 1069#endif 1070 1071 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 1072 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 1073 if (N1C) { 1074 if (N2C) { 1075 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 1076 switch (Opcode) { 1077 case ISD::ADD: return getConstant(C1 + C2, VT); 1078 case ISD::SUB: return getConstant(C1 - C2, VT); 1079 case ISD::MUL: return getConstant(C1 * C2, VT); 1080 case ISD::UDIV: 1081 if (C2) return getConstant(C1 / C2, VT); 1082 break; 1083 case ISD::UREM : 1084 if (C2) return getConstant(C1 % C2, VT); 1085 break; 1086 case ISD::SDIV : 1087 if (C2) return getConstant(N1C->getSignExtended() / 1088 N2C->getSignExtended(), VT); 1089 break; 1090 case ISD::SREM : 1091 if (C2) return getConstant(N1C->getSignExtended() % 1092 N2C->getSignExtended(), VT); 1093 break; 1094 case ISD::AND : return getConstant(C1 & C2, VT); 1095 case ISD::OR : return getConstant(C1 | C2, VT); 1096 case ISD::XOR : return getConstant(C1 ^ C2, VT); 1097 case ISD::SHL : return getConstant(C1 << C2, VT); 1098 case ISD::SRL : return getConstant(C1 >> C2, VT); 1099 case ISD::SRA : return getConstant(N1C->getSignExtended() >>(int)C2, VT); 1100 case ISD::ROTL : 1101 return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)), 1102 VT); 1103 case ISD::ROTR : 1104 return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)), 1105 VT); 1106 default: break; 1107 } 1108 } else { // Cannonicalize constant to RHS if commutative 1109 if (isCommutativeBinOp(Opcode)) { 1110 std::swap(N1C, N2C); 1111 std::swap(N1, N2); 1112 } 1113 } 1114 } 1115 1116 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); 1117 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val); 1118 if (N1CFP) { 1119 if (N2CFP) { 1120 double C1 = N1CFP->getValue(), C2 = N2CFP->getValue(); 1121 switch (Opcode) { 1122 case ISD::FADD: return getConstantFP(C1 + C2, VT); 1123 case ISD::FSUB: return getConstantFP(C1 - C2, VT); 1124 case ISD::FMUL: return getConstantFP(C1 * C2, VT); 1125 case ISD::FDIV: 1126 if (C2) return getConstantFP(C1 / C2, VT); 1127 break; 1128 case ISD::FREM : 1129 if (C2) return getConstantFP(fmod(C1, C2), VT); 1130 break; 1131 default: break; 1132 } 1133 } else { // Cannonicalize constant to RHS if commutative 1134 if (isCommutativeBinOp(Opcode)) { 1135 std::swap(N1CFP, N2CFP); 1136 std::swap(N1, N2); 1137 } 1138 } 1139 } 1140 1141 // Finally, fold operations that do not require constants. 1142 switch (Opcode) { 1143 case ISD::FP_ROUND_INREG: 1144 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding. 1145 break; 1146 case ISD::SIGN_EXTEND_INREG: { 1147 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1148 if (EVT == VT) return N1; // Not actually extending 1149 break; 1150 } 1151 1152 // FIXME: figure out how to safely handle things like 1153 // int foo(int x) { return 1 << (x & 255); } 1154 // int bar() { return foo(256); } 1155#if 0 1156 case ISD::SHL: 1157 case ISD::SRL: 1158 case ISD::SRA: 1159 if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG && 1160 cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1) 1161 return getNode(Opcode, VT, N1, N2.getOperand(0)); 1162 else if (N2.getOpcode() == ISD::AND) 1163 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) { 1164 // If the and is only masking out bits that cannot effect the shift, 1165 // eliminate the and. 1166 unsigned NumBits = MVT::getSizeInBits(VT); 1167 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 1168 return getNode(Opcode, VT, N1, N2.getOperand(0)); 1169 } 1170 break; 1171#endif 1172 } 1173 1174 // Memoize this node if possible. 1175 SDNode *N; 1176 if (Opcode != ISD::CALLSEQ_START && Opcode != ISD::CALLSEQ_END && 1177 VT != MVT::Flag) { 1178 SDNode *&BON = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))]; 1179 if (BON) return SDOperand(BON, 0); 1180 1181 BON = N = new SDNode(Opcode, N1, N2); 1182 } else { 1183 N = new SDNode(Opcode, N1, N2); 1184 } 1185 1186 N->setValueTypes(VT); 1187 AllNodes.push_back(N); 1188 return SDOperand(N, 0); 1189} 1190 1191SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1192 SDOperand N1, SDOperand N2, SDOperand N3) { 1193 // Perform various simplifications. 1194 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 1195 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 1196 ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 1197 switch (Opcode) { 1198 case ISD::SETCC: { 1199 // Use SimplifySetCC to simplify SETCC's. 1200 SDOperand Simp = SimplifySetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get()); 1201 if (Simp.Val) return Simp; 1202 break; 1203 } 1204 case ISD::SELECT: 1205 if (N1C) 1206 if (N1C->getValue()) 1207 return N2; // select true, X, Y -> X 1208 else 1209 return N3; // select false, X, Y -> Y 1210 1211 if (N2 == N3) return N2; // select C, X, X -> X 1212 break; 1213 case ISD::BRCOND: 1214 if (N2C) 1215 if (N2C->getValue()) // Unconditional branch 1216 return getNode(ISD::BR, MVT::Other, N1, N3); 1217 else 1218 return N1; // Never-taken branch 1219 break; 1220 } 1221 1222 std::vector<SDOperand> Ops; 1223 Ops.reserve(3); 1224 Ops.push_back(N1); 1225 Ops.push_back(N2); 1226 Ops.push_back(N3); 1227 1228 // Memoize node if it doesn't produce a flag. 1229 SDNode *N; 1230 if (VT != MVT::Flag) { 1231 SDNode *&E = OneResultNodes[std::make_pair(Opcode,std::make_pair(VT, Ops))]; 1232 if (E) return SDOperand(E, 0); 1233 E = N = new SDNode(Opcode, N1, N2, N3); 1234 } else { 1235 N = new SDNode(Opcode, N1, N2, N3); 1236 } 1237 N->setValueTypes(VT); 1238 AllNodes.push_back(N); 1239 return SDOperand(N, 0); 1240} 1241 1242SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1243 SDOperand N1, SDOperand N2, SDOperand N3, 1244 SDOperand N4) { 1245 std::vector<SDOperand> Ops; 1246 Ops.reserve(4); 1247 Ops.push_back(N1); 1248 Ops.push_back(N2); 1249 Ops.push_back(N3); 1250 Ops.push_back(N4); 1251 return getNode(Opcode, VT, Ops); 1252} 1253 1254SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1255 SDOperand N1, SDOperand N2, SDOperand N3, 1256 SDOperand N4, SDOperand N5) { 1257 std::vector<SDOperand> Ops; 1258 Ops.reserve(5); 1259 Ops.push_back(N1); 1260 Ops.push_back(N2); 1261 Ops.push_back(N3); 1262 Ops.push_back(N4); 1263 Ops.push_back(N5); 1264 return getNode(Opcode, VT, Ops); 1265} 1266 1267// setAdjCallChain - This method changes the token chain of an 1268// CALLSEQ_START/END node to be the specified operand. 1269void SDNode::setAdjCallChain(SDOperand N) { 1270 assert(N.getValueType() == MVT::Other); 1271 assert((getOpcode() == ISD::CALLSEQ_START || 1272 getOpcode() == ISD::CALLSEQ_END) && "Cannot adjust this node!"); 1273 1274 OperandList[0].Val->removeUser(this); 1275 OperandList[0] = N; 1276 OperandList[0].Val->Uses.push_back(this); 1277} 1278 1279 1280 1281SDOperand SelectionDAG::getLoad(MVT::ValueType VT, 1282 SDOperand Chain, SDOperand Ptr, 1283 SDOperand SV) { 1284 SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))]; 1285 if (N) return SDOperand(N, 0); 1286 N = new SDNode(ISD::LOAD, Chain, Ptr, SV); 1287 1288 // Loads have a token chain. 1289 setNodeValueTypes(N, VT, MVT::Other); 1290 AllNodes.push_back(N); 1291 return SDOperand(N, 0); 1292} 1293 1294SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT, 1295 SDOperand Chain, SDOperand Ptr, 1296 SDOperand SV) { 1297 SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, EVT))]; 1298 if (N) return SDOperand(N, 0); 1299 std::vector<SDOperand> Ops; 1300 Ops.reserve(5); 1301 Ops.push_back(Chain); 1302 Ops.push_back(Ptr); 1303 Ops.push_back(getConstant(Count, MVT::i32)); 1304 Ops.push_back(getValueType(EVT)); 1305 Ops.push_back(SV); 1306 std::vector<MVT::ValueType> VTs; 1307 VTs.reserve(2); 1308 VTs.push_back(MVT::Vector); VTs.push_back(MVT::Other); // Add token chain. 1309 return getNode(ISD::VLOAD, VTs, Ops); 1310} 1311 1312SDOperand SelectionDAG::getExtLoad(unsigned Opcode, MVT::ValueType VT, 1313 SDOperand Chain, SDOperand Ptr, SDOperand SV, 1314 MVT::ValueType EVT) { 1315 std::vector<SDOperand> Ops; 1316 Ops.reserve(4); 1317 Ops.push_back(Chain); 1318 Ops.push_back(Ptr); 1319 Ops.push_back(SV); 1320 Ops.push_back(getValueType(EVT)); 1321 std::vector<MVT::ValueType> VTs; 1322 VTs.reserve(2); 1323 VTs.push_back(VT); VTs.push_back(MVT::Other); // Add token chain. 1324 return getNode(Opcode, VTs, Ops); 1325} 1326 1327SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { 1328 assert((!V || isa<PointerType>(V->getType())) && 1329 "SrcValue is not a pointer?"); 1330 SDNode *&N = ValueNodes[std::make_pair(V, Offset)]; 1331 if (N) return SDOperand(N, 0); 1332 1333 N = new SrcValueSDNode(V, Offset); 1334 AllNodes.push_back(N); 1335 return SDOperand(N, 0); 1336} 1337 1338SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1339 std::vector<SDOperand> &Ops) { 1340 switch (Ops.size()) { 1341 case 0: return getNode(Opcode, VT); 1342 case 1: return getNode(Opcode, VT, Ops[0]); 1343 case 2: return getNode(Opcode, VT, Ops[0], Ops[1]); 1344 case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]); 1345 default: break; 1346 } 1347 1348 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(Ops[1].Val); 1349 switch (Opcode) { 1350 default: break; 1351 case ISD::BRCONDTWOWAY: 1352 if (N1C) 1353 if (N1C->getValue()) // Unconditional branch to true dest. 1354 return getNode(ISD::BR, MVT::Other, Ops[0], Ops[2]); 1355 else // Unconditional branch to false dest. 1356 return getNode(ISD::BR, MVT::Other, Ops[0], Ops[3]); 1357 break; 1358 case ISD::BRTWOWAY_CC: 1359 assert(Ops.size() == 6 && "BRTWOWAY_CC takes 6 operands!"); 1360 assert(Ops[2].getValueType() == Ops[3].getValueType() && 1361 "LHS and RHS of comparison must have same type!"); 1362 break; 1363 case ISD::TRUNCSTORE: { 1364 assert(Ops.size() == 5 && "TRUNCSTORE takes 5 operands!"); 1365 MVT::ValueType EVT = cast<VTSDNode>(Ops[4])->getVT(); 1366#if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store 1367 // If this is a truncating store of a constant, convert to the desired type 1368 // and store it instead. 1369 if (isa<Constant>(Ops[0])) { 1370 SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1); 1371 if (isa<Constant>(Op)) 1372 N1 = Op; 1373 } 1374 // Also for ConstantFP? 1375#endif 1376 if (Ops[0].getValueType() == EVT) // Normal store? 1377 return getNode(ISD::STORE, VT, Ops[0], Ops[1], Ops[2], Ops[3]); 1378 assert(Ops[1].getValueType() > EVT && "Not a truncation?"); 1379 assert(MVT::isInteger(Ops[1].getValueType()) == MVT::isInteger(EVT) && 1380 "Can't do FP-INT conversion!"); 1381 break; 1382 } 1383 case ISD::SELECT_CC: { 1384 assert(Ops.size() == 5 && "SELECT_CC takes 5 operands!"); 1385 assert(Ops[0].getValueType() == Ops[1].getValueType() && 1386 "LHS and RHS of condition must have same type!"); 1387 assert(Ops[2].getValueType() == Ops[3].getValueType() && 1388 "True and False arms of SelectCC must have same type!"); 1389 assert(Ops[2].getValueType() == VT && 1390 "select_cc node must be of same type as true and false value!"); 1391 break; 1392 } 1393 case ISD::BR_CC: { 1394 assert(Ops.size() == 5 && "BR_CC takes 5 operands!"); 1395 assert(Ops[2].getValueType() == Ops[3].getValueType() && 1396 "LHS/RHS of comparison should match types!"); 1397 break; 1398 } 1399 } 1400 1401 // Memoize nodes. 1402 SDNode *N; 1403 if (VT != MVT::Flag) { 1404 SDNode *&E = 1405 OneResultNodes[std::make_pair(Opcode, std::make_pair(VT, Ops))]; 1406 if (E) return SDOperand(E, 0); 1407 E = N = new SDNode(Opcode, Ops); 1408 } else { 1409 N = new SDNode(Opcode, Ops); 1410 } 1411 N->setValueTypes(VT); 1412 AllNodes.push_back(N); 1413 return SDOperand(N, 0); 1414} 1415 1416SDOperand SelectionDAG::getNode(unsigned Opcode, 1417 std::vector<MVT::ValueType> &ResultTys, 1418 std::vector<SDOperand> &Ops) { 1419 if (ResultTys.size() == 1) 1420 return getNode(Opcode, ResultTys[0], Ops); 1421 1422 switch (Opcode) { 1423 case ISD::EXTLOAD: 1424 case ISD::SEXTLOAD: 1425 case ISD::ZEXTLOAD: { 1426 MVT::ValueType EVT = cast<VTSDNode>(Ops[3])->getVT(); 1427 assert(Ops.size() == 4 && ResultTys.size() == 2 && "Bad *EXTLOAD!"); 1428 // If they are asking for an extending load from/to the same thing, return a 1429 // normal load. 1430 if (ResultTys[0] == EVT) 1431 return getLoad(ResultTys[0], Ops[0], Ops[1], Ops[2]); 1432 assert(EVT < ResultTys[0] && 1433 "Should only be an extending load, not truncating!"); 1434 assert((Opcode == ISD::EXTLOAD || MVT::isInteger(ResultTys[0])) && 1435 "Cannot sign/zero extend a FP load!"); 1436 assert(MVT::isInteger(ResultTys[0]) == MVT::isInteger(EVT) && 1437 "Cannot convert from FP to Int or Int -> FP!"); 1438 break; 1439 } 1440 1441 // FIXME: figure out how to safely handle things like 1442 // int foo(int x) { return 1 << (x & 255); } 1443 // int bar() { return foo(256); } 1444#if 0 1445 case ISD::SRA_PARTS: 1446 case ISD::SRL_PARTS: 1447 case ISD::SHL_PARTS: 1448 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG && 1449 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1) 1450 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 1451 else if (N3.getOpcode() == ISD::AND) 1452 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) { 1453 // If the and is only masking out bits that cannot effect the shift, 1454 // eliminate the and. 1455 unsigned NumBits = MVT::getSizeInBits(VT)*2; 1456 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 1457 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 1458 } 1459 break; 1460#endif 1461 } 1462 1463 // Memoize the node unless it returns a flag. 1464 SDNode *N; 1465 if (ResultTys.back() != MVT::Flag) { 1466 SDNode *&E = 1467 ArbitraryNodes[std::make_pair(Opcode, std::make_pair(ResultTys, Ops))]; 1468 if (E) return SDOperand(E, 0); 1469 E = N = new SDNode(Opcode, Ops); 1470 } else { 1471 N = new SDNode(Opcode, Ops); 1472 } 1473 setNodeValueTypes(N, ResultTys); 1474 AllNodes.push_back(N); 1475 return SDOperand(N, 0); 1476} 1477 1478void SelectionDAG::setNodeValueTypes(SDNode *N, 1479 std::vector<MVT::ValueType> &RetVals) { 1480 switch (RetVals.size()) { 1481 case 0: return; 1482 case 1: N->setValueTypes(RetVals[0]); return; 1483 case 2: setNodeValueTypes(N, RetVals[0], RetVals[1]); return; 1484 default: break; 1485 } 1486 1487 std::list<std::vector<MVT::ValueType> >::iterator I = 1488 std::find(VTList.begin(), VTList.end(), RetVals); 1489 if (I == VTList.end()) { 1490 VTList.push_front(RetVals); 1491 I = VTList.begin(); 1492 } 1493 1494 N->setValueTypes(&(*I)[0], I->size()); 1495} 1496 1497void SelectionDAG::setNodeValueTypes(SDNode *N, MVT::ValueType VT1, 1498 MVT::ValueType VT2) { 1499 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 1500 E = VTList.end(); I != E; ++I) { 1501 if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2) { 1502 N->setValueTypes(&(*I)[0], 2); 1503 return; 1504 } 1505 } 1506 std::vector<MVT::ValueType> V; 1507 V.push_back(VT1); 1508 V.push_back(VT2); 1509 VTList.push_front(V); 1510 N->setValueTypes(&(*VTList.begin())[0], 2); 1511} 1512 1513 1514/// SelectNodeTo - These are used for target selectors to *mutate* the 1515/// specified node to have the specified return type, Target opcode, and 1516/// operands. Note that target opcodes are stored as 1517/// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. 1518/// 1519/// Note that SelectNodeTo returns the resultant node. If there is already a 1520/// node of the specified opcode and operands, it returns that node instead of 1521/// the current one. 1522SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1523 MVT::ValueType VT) { 1524 // If an identical node already exists, use it. 1525 SDNode *&ON = NullaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, VT)]; 1526 if (ON) return SDOperand(ON, 0); 1527 1528 RemoveNodeFromCSEMaps(N); 1529 1530 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1531 N->setValueTypes(VT); 1532 1533 ON = N; // Memoize the new node. 1534 return SDOperand(N, 0); 1535} 1536 1537SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1538 MVT::ValueType VT, SDOperand Op1) { 1539 // If an identical node already exists, use it. 1540 SDNode *&ON = UnaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1541 std::make_pair(Op1, VT))]; 1542 if (ON) return SDOperand(ON, 0); 1543 1544 RemoveNodeFromCSEMaps(N); 1545 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1546 N->setValueTypes(VT); 1547 N->setOperands(Op1); 1548 1549 ON = N; // Memoize the new node. 1550 return SDOperand(N, 0); 1551} 1552 1553SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1554 MVT::ValueType VT, SDOperand Op1, 1555 SDOperand Op2) { 1556 // If an identical node already exists, use it. 1557 SDNode *&ON = BinaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1558 std::make_pair(Op1, Op2))]; 1559 if (ON) return SDOperand(ON, 0); 1560 1561 RemoveNodeFromCSEMaps(N); 1562 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1563 N->setValueTypes(VT); 1564 N->setOperands(Op1, Op2); 1565 1566 ON = N; // Memoize the new node. 1567 return SDOperand(N, 0); 1568} 1569 1570SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1571 MVT::ValueType VT, SDOperand Op1, 1572 SDOperand Op2, SDOperand Op3) { 1573 // If an identical node already exists, use it. 1574 std::vector<SDOperand> OpList; 1575 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 1576 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1577 std::make_pair(VT, OpList))]; 1578 if (ON) return SDOperand(ON, 0); 1579 1580 RemoveNodeFromCSEMaps(N); 1581 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1582 N->setValueTypes(VT); 1583 N->setOperands(Op1, Op2, Op3); 1584 1585 ON = N; // Memoize the new node. 1586 return SDOperand(N, 0); 1587} 1588 1589SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1590 MVT::ValueType VT, SDOperand Op1, 1591 SDOperand Op2, SDOperand Op3, 1592 SDOperand Op4) { 1593 // If an identical node already exists, use it. 1594 std::vector<SDOperand> OpList; 1595 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 1596 OpList.push_back(Op4); 1597 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1598 std::make_pair(VT, OpList))]; 1599 if (ON) return SDOperand(ON, 0); 1600 1601 RemoveNodeFromCSEMaps(N); 1602 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1603 N->setValueTypes(VT); 1604 N->setOperands(Op1, Op2, Op3, Op4); 1605 1606 ON = N; // Memoize the new node. 1607 return SDOperand(N, 0); 1608} 1609 1610SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1611 MVT::ValueType VT, SDOperand Op1, 1612 SDOperand Op2, SDOperand Op3,SDOperand Op4, 1613 SDOperand Op5) { 1614 // If an identical node already exists, use it. 1615 std::vector<SDOperand> OpList; 1616 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 1617 OpList.push_back(Op4); OpList.push_back(Op5); 1618 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1619 std::make_pair(VT, OpList))]; 1620 if (ON) return SDOperand(ON, 0); 1621 1622 RemoveNodeFromCSEMaps(N); 1623 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1624 N->setValueTypes(VT); 1625 N->setOperands(Op1, Op2, Op3, Op4, Op5); 1626 1627 ON = N; // Memoize the new node. 1628 return SDOperand(N, 0); 1629} 1630 1631SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1632 MVT::ValueType VT, SDOperand Op1, 1633 SDOperand Op2, SDOperand Op3,SDOperand Op4, 1634 SDOperand Op5, SDOperand Op6) { 1635 // If an identical node already exists, use it. 1636 std::vector<SDOperand> OpList; 1637 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 1638 OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); 1639 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1640 std::make_pair(VT, OpList))]; 1641 if (ON) return SDOperand(ON, 0); 1642 1643 RemoveNodeFromCSEMaps(N); 1644 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1645 N->setValueTypes(VT); 1646 N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6); 1647 1648 ON = N; // Memoize the new node. 1649 return SDOperand(N, 0); 1650} 1651 1652SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1653 MVT::ValueType VT, SDOperand Op1, 1654 SDOperand Op2, SDOperand Op3,SDOperand Op4, 1655 SDOperand Op5, SDOperand Op6, 1656 SDOperand Op7) { 1657 // If an identical node already exists, use it. 1658 std::vector<SDOperand> OpList; 1659 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 1660 OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); 1661 OpList.push_back(Op7); 1662 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1663 std::make_pair(VT, OpList))]; 1664 if (ON) return SDOperand(ON, 0); 1665 1666 RemoveNodeFromCSEMaps(N); 1667 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1668 N->setValueTypes(VT); 1669 N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7); 1670 1671 ON = N; // Memoize the new node. 1672 return SDOperand(N, 0); 1673} 1674 1675SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1676 MVT::ValueType VT1, MVT::ValueType VT2, 1677 SDOperand Op1, SDOperand Op2) { 1678 // If an identical node already exists, use it. 1679 std::vector<SDOperand> OpList; 1680 OpList.push_back(Op1); OpList.push_back(Op2); 1681 std::vector<MVT::ValueType> VTList; 1682 VTList.push_back(VT1); VTList.push_back(VT2); 1683 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1684 std::make_pair(VTList, OpList))]; 1685 if (ON) return SDOperand(ON, 0); 1686 1687 RemoveNodeFromCSEMaps(N); 1688 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1689 setNodeValueTypes(N, VT1, VT2); 1690 N->setOperands(Op1, Op2); 1691 1692 ON = N; // Memoize the new node. 1693 return SDOperand(N, 0); 1694} 1695 1696SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1697 MVT::ValueType VT1, MVT::ValueType VT2, 1698 SDOperand Op1, SDOperand Op2, 1699 SDOperand Op3) { 1700 // If an identical node already exists, use it. 1701 std::vector<SDOperand> OpList; 1702 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 1703 std::vector<MVT::ValueType> VTList; 1704 VTList.push_back(VT1); VTList.push_back(VT2); 1705 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1706 std::make_pair(VTList, OpList))]; 1707 if (ON) return SDOperand(ON, 0); 1708 1709 RemoveNodeFromCSEMaps(N); 1710 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1711 setNodeValueTypes(N, VT1, VT2); 1712 N->setOperands(Op1, Op2, Op3); 1713 1714 ON = N; // Memoize the new node. 1715 return SDOperand(N, 0); 1716} 1717 1718SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1719 MVT::ValueType VT1, MVT::ValueType VT2, 1720 SDOperand Op1, SDOperand Op2, 1721 SDOperand Op3, SDOperand Op4) { 1722 // If an identical node already exists, use it. 1723 std::vector<SDOperand> OpList; 1724 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 1725 OpList.push_back(Op4); 1726 std::vector<MVT::ValueType> VTList; 1727 VTList.push_back(VT1); VTList.push_back(VT2); 1728 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1729 std::make_pair(VTList, OpList))]; 1730 if (ON) return SDOperand(ON, 0); 1731 1732 RemoveNodeFromCSEMaps(N); 1733 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1734 setNodeValueTypes(N, VT1, VT2); 1735 N->setOperands(Op1, Op2, Op3, Op4); 1736 1737 ON = N; // Memoize the new node. 1738 return SDOperand(N, 0); 1739} 1740 1741SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1742 MVT::ValueType VT1, MVT::ValueType VT2, 1743 SDOperand Op1, SDOperand Op2, 1744 SDOperand Op3, SDOperand Op4, 1745 SDOperand Op5) { 1746 // If an identical node already exists, use it. 1747 std::vector<SDOperand> OpList; 1748 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 1749 OpList.push_back(Op4); OpList.push_back(Op5); 1750 std::vector<MVT::ValueType> VTList; 1751 VTList.push_back(VT1); VTList.push_back(VT2); 1752 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 1753 std::make_pair(VTList, OpList))]; 1754 if (ON) return SDOperand(ON, 0); 1755 1756 RemoveNodeFromCSEMaps(N); 1757 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1758 setNodeValueTypes(N, VT1, VT2); 1759 N->setOperands(Op1, Op2, Op3, Op4, Op5); 1760 1761 ON = N; // Memoize the new node. 1762 return SDOperand(N, 0); 1763} 1764 1765// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 1766/// This can cause recursive merging of nodes in the DAG. 1767/// 1768/// This version assumes From/To have a single result value. 1769/// 1770void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN, 1771 std::vector<SDNode*> *Deleted) { 1772 SDNode *From = FromN.Val, *To = ToN.Val; 1773 assert(From->getNumValues() == 1 && To->getNumValues() == 1 && 1774 "Cannot replace with this method!"); 1775 assert(From != To && "Cannot replace uses of with self"); 1776 1777 while (!From->use_empty()) { 1778 // Process users until they are all gone. 1779 SDNode *U = *From->use_begin(); 1780 1781 // This node is about to morph, remove its old self from the CSE maps. 1782 RemoveNodeFromCSEMaps(U); 1783 1784 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 1785 I != E; ++I) 1786 if (I->Val == From) { 1787 From->removeUser(U); 1788 I->Val = To; 1789 To->addUser(U); 1790 } 1791 1792 // Now that we have modified U, add it back to the CSE maps. If it already 1793 // exists there, recursively merge the results together. 1794 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 1795 ReplaceAllUsesWith(U, Existing, Deleted); 1796 // U is now dead. 1797 if (Deleted) Deleted->push_back(U); 1798 DeleteNodeNotInCSEMaps(U); 1799 } 1800 } 1801} 1802 1803/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 1804/// This can cause recursive merging of nodes in the DAG. 1805/// 1806/// This version assumes From/To have matching types and numbers of result 1807/// values. 1808/// 1809void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, 1810 std::vector<SDNode*> *Deleted) { 1811 assert(From != To && "Cannot replace uses of with self"); 1812 assert(From->getNumValues() == To->getNumValues() && 1813 "Cannot use this version of ReplaceAllUsesWith!"); 1814 if (From->getNumValues() == 1) { // If possible, use the faster version. 1815 ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted); 1816 return; 1817 } 1818 1819 while (!From->use_empty()) { 1820 // Process users until they are all gone. 1821 SDNode *U = *From->use_begin(); 1822 1823 // This node is about to morph, remove its old self from the CSE maps. 1824 RemoveNodeFromCSEMaps(U); 1825 1826 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 1827 I != E; ++I) 1828 if (I->Val == From) { 1829 From->removeUser(U); 1830 I->Val = To; 1831 To->addUser(U); 1832 } 1833 1834 // Now that we have modified U, add it back to the CSE maps. If it already 1835 // exists there, recursively merge the results together. 1836 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 1837 ReplaceAllUsesWith(U, Existing, Deleted); 1838 // U is now dead. 1839 if (Deleted) Deleted->push_back(U); 1840 DeleteNodeNotInCSEMaps(U); 1841 } 1842 } 1843} 1844 1845/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 1846/// This can cause recursive merging of nodes in the DAG. 1847/// 1848/// This version can replace From with any result values. To must match the 1849/// number and types of values returned by From. 1850void SelectionDAG::ReplaceAllUsesWith(SDNode *From, 1851 const std::vector<SDOperand> &To, 1852 std::vector<SDNode*> *Deleted) { 1853 assert(From->getNumValues() == To.size() && 1854 "Incorrect number of values to replace with!"); 1855 if (To.size() == 1 && To[0].Val->getNumValues() == 1) { 1856 // Degenerate case handled above. 1857 ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted); 1858 return; 1859 } 1860 1861 while (!From->use_empty()) { 1862 // Process users until they are all gone. 1863 SDNode *U = *From->use_begin(); 1864 1865 // This node is about to morph, remove its old self from the CSE maps. 1866 RemoveNodeFromCSEMaps(U); 1867 1868 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 1869 I != E; ++I) 1870 if (I->Val == From) { 1871 const SDOperand &ToOp = To[I->ResNo]; 1872 From->removeUser(U); 1873 *I = ToOp; 1874 ToOp.Val->addUser(U); 1875 } 1876 1877 // Now that we have modified U, add it back to the CSE maps. If it already 1878 // exists there, recursively merge the results together. 1879 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 1880 ReplaceAllUsesWith(U, Existing, Deleted); 1881 // U is now dead. 1882 if (Deleted) Deleted->push_back(U); 1883 DeleteNodeNotInCSEMaps(U); 1884 } 1885 } 1886} 1887 1888 1889//===----------------------------------------------------------------------===// 1890// SDNode Class 1891//===----------------------------------------------------------------------===// 1892 1893 1894/// getValueTypeList - Return a pointer to the specified value type. 1895/// 1896MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) { 1897 static MVT::ValueType VTs[MVT::LAST_VALUETYPE]; 1898 VTs[VT] = VT; 1899 return &VTs[VT]; 1900} 1901 1902/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 1903/// indicated value. This method ignores uses of other values defined by this 1904/// operation. 1905bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) { 1906 assert(Value < getNumValues() && "Bad value!"); 1907 1908 // If there is only one value, this is easy. 1909 if (getNumValues() == 1) 1910 return use_size() == NUses; 1911 if (Uses.size() < NUses) return false; 1912 1913 SDOperand TheValue(this, Value); 1914 1915 std::set<SDNode*> UsersHandled; 1916 1917 for (std::vector<SDNode*>::iterator UI = Uses.begin(), E = Uses.end(); 1918 UI != E; ++UI) { 1919 SDNode *User = *UI; 1920 if (User->getNumOperands() == 1 || 1921 UsersHandled.insert(User).second) // First time we've seen this? 1922 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 1923 if (User->getOperand(i) == TheValue) { 1924 if (NUses == 0) 1925 return false; // too many uses 1926 --NUses; 1927 } 1928 } 1929 1930 // Found exactly the right number of uses? 1931 return NUses == 0; 1932} 1933 1934 1935const char *SDNode::getOperationName(const SelectionDAG *G) const { 1936 switch (getOpcode()) { 1937 default: 1938 if (getOpcode() < ISD::BUILTIN_OP_END) 1939 return "<<Unknown DAG Node>>"; 1940 else { 1941 if (G) { 1942 if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo()) 1943 if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes()) 1944 return TII->getName(getOpcode()-ISD::BUILTIN_OP_END); 1945 1946 TargetLowering &TLI = G->getTargetLoweringInfo(); 1947 const char *Name = 1948 TLI.getTargetNodeName(getOpcode()); 1949 if (Name) return Name; 1950 } 1951 1952 return "<<Unknown Target Node>>"; 1953 } 1954 1955 case ISD::PCMARKER: return "PCMarker"; 1956 case ISD::READCYCLECOUNTER: return "ReadCycleCounter"; 1957 case ISD::SRCVALUE: return "SrcValue"; 1958 case ISD::VALUETYPE: return "ValueType"; 1959 case ISD::STRING: return "String"; 1960 case ISD::EntryToken: return "EntryToken"; 1961 case ISD::TokenFactor: return "TokenFactor"; 1962 case ISD::AssertSext: return "AssertSext"; 1963 case ISD::AssertZext: return "AssertZext"; 1964 case ISD::Constant: return "Constant"; 1965 case ISD::TargetConstant: return "TargetConstant"; 1966 case ISD::ConstantFP: return "ConstantFP"; 1967 case ISD::ConstantVec: return "ConstantVec"; 1968 case ISD::GlobalAddress: return "GlobalAddress"; 1969 case ISD::TargetGlobalAddress: return "TargetGlobalAddress"; 1970 case ISD::FrameIndex: return "FrameIndex"; 1971 case ISD::TargetFrameIndex: return "TargetFrameIndex"; 1972 case ISD::BasicBlock: return "BasicBlock"; 1973 case ISD::Register: return "Register"; 1974 case ISD::ExternalSymbol: return "ExternalSymbol"; 1975 case ISD::TargetExternalSymbol: return "TargetExternalSymbol"; 1976 case ISD::ConstantPool: return "ConstantPool"; 1977 case ISD::TargetConstantPool: return "TargetConstantPool"; 1978 case ISD::CopyToReg: return "CopyToReg"; 1979 case ISD::CopyFromReg: return "CopyFromReg"; 1980 case ISD::UNDEF: return "undef"; 1981 case ISD::MERGE_VALUES: return "mergevalues"; 1982 1983 // Unary operators 1984 case ISD::FABS: return "fabs"; 1985 case ISD::FNEG: return "fneg"; 1986 case ISD::FSQRT: return "fsqrt"; 1987 case ISD::FSIN: return "fsin"; 1988 case ISD::FCOS: return "fcos"; 1989 1990 // Binary operators 1991 case ISD::ADD: return "add"; 1992 case ISD::SUB: return "sub"; 1993 case ISD::MUL: return "mul"; 1994 case ISD::MULHU: return "mulhu"; 1995 case ISD::MULHS: return "mulhs"; 1996 case ISD::SDIV: return "sdiv"; 1997 case ISD::UDIV: return "udiv"; 1998 case ISD::SREM: return "srem"; 1999 case ISD::UREM: return "urem"; 2000 case ISD::AND: return "and"; 2001 case ISD::OR: return "or"; 2002 case ISD::XOR: return "xor"; 2003 case ISD::SHL: return "shl"; 2004 case ISD::SRA: return "sra"; 2005 case ISD::SRL: return "srl"; 2006 case ISD::ROTL: return "rotl"; 2007 case ISD::ROTR: return "rotr"; 2008 case ISD::FADD: return "fadd"; 2009 case ISD::FSUB: return "fsub"; 2010 case ISD::FMUL: return "fmul"; 2011 case ISD::FDIV: return "fdiv"; 2012 case ISD::FREM: return "frem"; 2013 case ISD::VADD: return "vadd"; 2014 case ISD::VSUB: return "vsub"; 2015 case ISD::VMUL: return "vmul"; 2016 2017 case ISD::SETCC: return "setcc"; 2018 case ISD::SELECT: return "select"; 2019 case ISD::SELECT_CC: return "select_cc"; 2020 case ISD::ADD_PARTS: return "add_parts"; 2021 case ISD::SUB_PARTS: return "sub_parts"; 2022 case ISD::SHL_PARTS: return "shl_parts"; 2023 case ISD::SRA_PARTS: return "sra_parts"; 2024 case ISD::SRL_PARTS: return "srl_parts"; 2025 2026 // Conversion operators. 2027 case ISD::SIGN_EXTEND: return "sign_extend"; 2028 case ISD::ZERO_EXTEND: return "zero_extend"; 2029 case ISD::ANY_EXTEND: return "any_extend"; 2030 case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg"; 2031 case ISD::TRUNCATE: return "truncate"; 2032 case ISD::FP_ROUND: return "fp_round"; 2033 case ISD::FP_ROUND_INREG: return "fp_round_inreg"; 2034 case ISD::FP_EXTEND: return "fp_extend"; 2035 2036 case ISD::SINT_TO_FP: return "sint_to_fp"; 2037 case ISD::UINT_TO_FP: return "uint_to_fp"; 2038 case ISD::FP_TO_SINT: return "fp_to_sint"; 2039 case ISD::FP_TO_UINT: return "fp_to_uint"; 2040 case ISD::BIT_CONVERT: return "bit_convert"; 2041 2042 // Control flow instructions 2043 case ISD::BR: return "br"; 2044 case ISD::BRCOND: return "brcond"; 2045 case ISD::BRCONDTWOWAY: return "brcondtwoway"; 2046 case ISD::BR_CC: return "br_cc"; 2047 case ISD::BRTWOWAY_CC: return "brtwoway_cc"; 2048 case ISD::RET: return "ret"; 2049 case ISD::CALL: return "call"; 2050 case ISD::TAILCALL:return "tailcall"; 2051 case ISD::CALLSEQ_START: return "callseq_start"; 2052 case ISD::CALLSEQ_END: return "callseq_end"; 2053 2054 // Other operators 2055 case ISD::LOAD: return "load"; 2056 case ISD::STORE: return "store"; 2057 case ISD::VLOAD: return "vload"; 2058 case ISD::EXTLOAD: return "extload"; 2059 case ISD::SEXTLOAD: return "sextload"; 2060 case ISD::ZEXTLOAD: return "zextload"; 2061 case ISD::TRUNCSTORE: return "truncstore"; 2062 2063 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc"; 2064 case ISD::EXTRACT_ELEMENT: return "extract_element"; 2065 case ISD::BUILD_PAIR: return "build_pair"; 2066 case ISD::STACKSAVE: return "stacksave"; 2067 case ISD::STACKRESTORE: return "stackrestore"; 2068 2069 // Block memory operations. 2070 case ISD::MEMSET: return "memset"; 2071 case ISD::MEMCPY: return "memcpy"; 2072 case ISD::MEMMOVE: return "memmove"; 2073 2074 // Bit manipulation 2075 case ISD::BSWAP: return "bswap"; 2076 case ISD::CTPOP: return "ctpop"; 2077 case ISD::CTTZ: return "cttz"; 2078 case ISD::CTLZ: return "ctlz"; 2079 2080 // IO Intrinsics 2081 case ISD::READPORT: return "readport"; 2082 case ISD::WRITEPORT: return "writeport"; 2083 case ISD::READIO: return "readio"; 2084 case ISD::WRITEIO: return "writeio"; 2085 2086 // Debug info 2087 case ISD::LOCATION: return "location"; 2088 case ISD::DEBUG_LOC: return "debug_loc"; 2089 case ISD::DEBUG_LABEL: return "debug_label"; 2090 2091 case ISD::CONDCODE: 2092 switch (cast<CondCodeSDNode>(this)->get()) { 2093 default: assert(0 && "Unknown setcc condition!"); 2094 case ISD::SETOEQ: return "setoeq"; 2095 case ISD::SETOGT: return "setogt"; 2096 case ISD::SETOGE: return "setoge"; 2097 case ISD::SETOLT: return "setolt"; 2098 case ISD::SETOLE: return "setole"; 2099 case ISD::SETONE: return "setone"; 2100 2101 case ISD::SETO: return "seto"; 2102 case ISD::SETUO: return "setuo"; 2103 case ISD::SETUEQ: return "setue"; 2104 case ISD::SETUGT: return "setugt"; 2105 case ISD::SETUGE: return "setuge"; 2106 case ISD::SETULT: return "setult"; 2107 case ISD::SETULE: return "setule"; 2108 case ISD::SETUNE: return "setune"; 2109 2110 case ISD::SETEQ: return "seteq"; 2111 case ISD::SETGT: return "setgt"; 2112 case ISD::SETGE: return "setge"; 2113 case ISD::SETLT: return "setlt"; 2114 case ISD::SETLE: return "setle"; 2115 case ISD::SETNE: return "setne"; 2116 } 2117 } 2118} 2119 2120void SDNode::dump() const { dump(0); } 2121void SDNode::dump(const SelectionDAG *G) const { 2122 std::cerr << (void*)this << ": "; 2123 2124 for (unsigned i = 0, e = getNumValues(); i != e; ++i) { 2125 if (i) std::cerr << ","; 2126 if (getValueType(i) == MVT::Other) 2127 std::cerr << "ch"; 2128 else 2129 std::cerr << MVT::getValueTypeString(getValueType(i)); 2130 } 2131 std::cerr << " = " << getOperationName(G); 2132 2133 std::cerr << " "; 2134 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 2135 if (i) std::cerr << ", "; 2136 std::cerr << (void*)getOperand(i).Val; 2137 if (unsigned RN = getOperand(i).ResNo) 2138 std::cerr << ":" << RN; 2139 } 2140 2141 if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { 2142 std::cerr << "<" << CSDN->getValue() << ">"; 2143 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { 2144 std::cerr << "<" << CSDN->getValue() << ">"; 2145 } else if (const GlobalAddressSDNode *GADN = 2146 dyn_cast<GlobalAddressSDNode>(this)) { 2147 int offset = GADN->getOffset(); 2148 std::cerr << "<"; 2149 WriteAsOperand(std::cerr, GADN->getGlobal()) << ">"; 2150 if (offset > 0) 2151 std::cerr << " + " << offset; 2152 else 2153 std::cerr << " " << offset; 2154 } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) { 2155 std::cerr << "<" << FIDN->getIndex() << ">"; 2156 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ 2157 std::cerr << "<" << *CP->get() << ">"; 2158 } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) { 2159 std::cerr << "<"; 2160 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); 2161 if (LBB) 2162 std::cerr << LBB->getName() << " "; 2163 std::cerr << (const void*)BBDN->getBasicBlock() << ">"; 2164 } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) { 2165 if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) { 2166 std::cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg()); 2167 } else { 2168 std::cerr << " #" << R->getReg(); 2169 } 2170 } else if (const ExternalSymbolSDNode *ES = 2171 dyn_cast<ExternalSymbolSDNode>(this)) { 2172 std::cerr << "'" << ES->getSymbol() << "'"; 2173 } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) { 2174 if (M->getValue()) 2175 std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">"; 2176 else 2177 std::cerr << "<null:" << M->getOffset() << ">"; 2178 } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) { 2179 std::cerr << ":" << getValueTypeString(N->getVT()); 2180 } 2181} 2182 2183static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { 2184 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 2185 if (N->getOperand(i).Val->hasOneUse()) 2186 DumpNodes(N->getOperand(i).Val, indent+2, G); 2187 else 2188 std::cerr << "\n" << std::string(indent+2, ' ') 2189 << (void*)N->getOperand(i).Val << ": <multiple use>"; 2190 2191 2192 std::cerr << "\n" << std::string(indent, ' '); 2193 N->dump(G); 2194} 2195 2196void SelectionDAG::dump() const { 2197 std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; 2198 std::vector<const SDNode*> Nodes; 2199 for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); 2200 I != E; ++I) 2201 Nodes.push_back(I); 2202 2203 std::sort(Nodes.begin(), Nodes.end()); 2204 2205 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 2206 if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val) 2207 DumpNodes(Nodes[i], 2, this); 2208 } 2209 2210 DumpNodes(getRoot().Val, 2, this); 2211 2212 std::cerr << "\n\n"; 2213} 2214 2215