SelectionDAG.cpp revision 2cacccae194b5ed648c004f6c06fce5565331ee9
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/Intrinsics.h" 18#include "llvm/Assembly/Writer.h" 19#include "llvm/CodeGen/MachineBasicBlock.h" 20#include "llvm/CodeGen/MachineConstantPool.h" 21#include "llvm/Support/MathExtras.h" 22#include "llvm/Target/MRegisterInfo.h" 23#include "llvm/Target/TargetLowering.h" 24#include "llvm/Target/TargetInstrInfo.h" 25#include "llvm/Target/TargetMachine.h" 26#include "llvm/ADT/SetVector.h" 27#include "llvm/ADT/SmallVector.h" 28#include "llvm/ADT/StringExtras.h" 29#include <iostream> 30#include <set> 31#include <cmath> 32#include <algorithm> 33using namespace llvm; 34 35/// makeVTList - Return an instance of the SDVTList struct initialized with the 36/// specified members. 37static SDVTList makeVTList(const MVT::ValueType *VTs, unsigned NumVTs) { 38 SDVTList Res = {VTs, NumVTs}; 39 return Res; 40} 41 42// isInvertibleForFree - Return true if there is no cost to emitting the logical 43// inverse of this node. 44static bool isInvertibleForFree(SDOperand N) { 45 if (isa<ConstantSDNode>(N.Val)) return true; 46 if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse()) 47 return true; 48 return false; 49} 50 51//===----------------------------------------------------------------------===// 52// ConstantFPSDNode Class 53//===----------------------------------------------------------------------===// 54 55/// isExactlyValue - We don't rely on operator== working on double values, as 56/// it returns true for things that are clearly not equal, like -0.0 and 0.0. 57/// As such, this method can be used to do an exact bit-for-bit comparison of 58/// two floating point values. 59bool ConstantFPSDNode::isExactlyValue(double V) const { 60 return DoubleToBits(V) == DoubleToBits(Value); 61} 62 63//===----------------------------------------------------------------------===// 64// ISD Namespace 65//===----------------------------------------------------------------------===// 66 67/// isBuildVectorAllOnes - Return true if the specified node is a 68/// BUILD_VECTOR where all of the elements are ~0 or undef. 69bool ISD::isBuildVectorAllOnes(const SDNode *N) { 70 // Look through a bit convert. 71 if (N->getOpcode() == ISD::BIT_CONVERT) 72 N = N->getOperand(0).Val; 73 74 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 75 76 unsigned i = 0, e = N->getNumOperands(); 77 78 // Skip over all of the undef values. 79 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 80 ++i; 81 82 // Do not accept an all-undef vector. 83 if (i == e) return false; 84 85 // Do not accept build_vectors that aren't all constants or which have non-~0 86 // elements. 87 SDOperand NotZero = N->getOperand(i); 88 if (isa<ConstantSDNode>(NotZero)) { 89 if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue()) 90 return false; 91 } else if (isa<ConstantFPSDNode>(NotZero)) { 92 MVT::ValueType VT = NotZero.getValueType(); 93 if (VT== MVT::f64) { 94 if (DoubleToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) != 95 (uint64_t)-1) 96 return false; 97 } else { 98 if (FloatToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) != 99 (uint32_t)-1) 100 return false; 101 } 102 } else 103 return false; 104 105 // Okay, we have at least one ~0 value, check to see if the rest match or are 106 // undefs. 107 for (++i; i != e; ++i) 108 if (N->getOperand(i) != NotZero && 109 N->getOperand(i).getOpcode() != ISD::UNDEF) 110 return false; 111 return true; 112} 113 114 115/// isBuildVectorAllZeros - Return true if the specified node is a 116/// BUILD_VECTOR where all of the elements are 0 or undef. 117bool ISD::isBuildVectorAllZeros(const SDNode *N) { 118 // Look through a bit convert. 119 if (N->getOpcode() == ISD::BIT_CONVERT) 120 N = N->getOperand(0).Val; 121 122 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 123 124 unsigned i = 0, e = N->getNumOperands(); 125 126 // Skip over all of the undef values. 127 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 128 ++i; 129 130 // Do not accept an all-undef vector. 131 if (i == e) return false; 132 133 // Do not accept build_vectors that aren't all constants or which have non-~0 134 // elements. 135 SDOperand Zero = N->getOperand(i); 136 if (isa<ConstantSDNode>(Zero)) { 137 if (!cast<ConstantSDNode>(Zero)->isNullValue()) 138 return false; 139 } else if (isa<ConstantFPSDNode>(Zero)) { 140 if (!cast<ConstantFPSDNode>(Zero)->isExactlyValue(0.0)) 141 return false; 142 } else 143 return false; 144 145 // Okay, we have at least one ~0 value, check to see if the rest match or are 146 // undefs. 147 for (++i; i != e; ++i) 148 if (N->getOperand(i) != Zero && 149 N->getOperand(i).getOpcode() != ISD::UNDEF) 150 return false; 151 return true; 152} 153 154/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 155/// when given the operation for (X op Y). 156ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 157 // To perform this operation, we just need to swap the L and G bits of the 158 // operation. 159 unsigned OldL = (Operation >> 2) & 1; 160 unsigned OldG = (Operation >> 1) & 1; 161 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 162 (OldL << 1) | // New G bit 163 (OldG << 2)); // New L bit. 164} 165 166/// getSetCCInverse - Return the operation corresponding to !(X op Y), where 167/// 'op' is a valid SetCC operation. 168ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 169 unsigned Operation = Op; 170 if (isInteger) 171 Operation ^= 7; // Flip L, G, E bits, but not U. 172 else 173 Operation ^= 15; // Flip all of the condition bits. 174 if (Operation > ISD::SETTRUE2) 175 Operation &= ~8; // Don't let N and U bits get set. 176 return ISD::CondCode(Operation); 177} 178 179 180/// isSignedOp - For an integer comparison, return 1 if the comparison is a 181/// signed operation and 2 if the result is an unsigned comparison. Return zero 182/// if the operation does not depend on the sign of the input (setne and seteq). 183static int isSignedOp(ISD::CondCode Opcode) { 184 switch (Opcode) { 185 default: assert(0 && "Illegal integer setcc operation!"); 186 case ISD::SETEQ: 187 case ISD::SETNE: return 0; 188 case ISD::SETLT: 189 case ISD::SETLE: 190 case ISD::SETGT: 191 case ISD::SETGE: return 1; 192 case ISD::SETULT: 193 case ISD::SETULE: 194 case ISD::SETUGT: 195 case ISD::SETUGE: return 2; 196 } 197} 198 199/// getSetCCOrOperation - Return the result of a logical OR between different 200/// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 201/// returns SETCC_INVALID if it is not possible to represent the resultant 202/// comparison. 203ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 204 bool isInteger) { 205 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 206 // Cannot fold a signed integer setcc with an unsigned integer setcc. 207 return ISD::SETCC_INVALID; 208 209 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 210 211 // If the N and U bits get set then the resultant comparison DOES suddenly 212 // care about orderedness, and is true when ordered. 213 if (Op > ISD::SETTRUE2) 214 Op &= ~16; // Clear the U bit if the N bit is set. 215 216 // Canonicalize illegal integer setcc's. 217 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT 218 Op = ISD::SETNE; 219 220 return ISD::CondCode(Op); 221} 222 223/// getSetCCAndOperation - Return the result of a logical AND between different 224/// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 225/// function returns zero if it is not possible to represent the resultant 226/// comparison. 227ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 228 bool isInteger) { 229 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 230 // Cannot fold a signed setcc with an unsigned setcc. 231 return ISD::SETCC_INVALID; 232 233 // Combine all of the condition bits. 234 ISD::CondCode Result = ISD::CondCode(Op1 & Op2); 235 236 // Canonicalize illegal integer setcc's. 237 if (isInteger) { 238 switch (Result) { 239 default: break; 240 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT 241 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE 242 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE 243 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE 244 } 245 } 246 247 return Result; 248} 249 250const TargetMachine &SelectionDAG::getTarget() const { 251 return TLI.getTargetMachine(); 252} 253 254//===----------------------------------------------------------------------===// 255// SelectionDAG Class 256//===----------------------------------------------------------------------===// 257 258/// RemoveDeadNodes - This method deletes all unreachable nodes in the 259/// SelectionDAG. 260void SelectionDAG::RemoveDeadNodes() { 261 // Create a dummy node (which is not added to allnodes), that adds a reference 262 // to the root node, preventing it from being deleted. 263 HandleSDNode Dummy(getRoot()); 264 265 SmallVector<SDNode*, 128> DeadNodes; 266 267 // Add all obviously-dead nodes to the DeadNodes worklist. 268 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) 269 if (I->use_empty()) 270 DeadNodes.push_back(I); 271 272 // Process the worklist, deleting the nodes and adding their uses to the 273 // worklist. 274 while (!DeadNodes.empty()) { 275 SDNode *N = DeadNodes.back(); 276 DeadNodes.pop_back(); 277 278 // Take the node out of the appropriate CSE map. 279 RemoveNodeFromCSEMaps(N); 280 281 // Next, brutally remove the operand list. This is safe to do, as there are 282 // no cycles in the graph. 283 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 284 SDNode *Operand = I->Val; 285 Operand->removeUser(N); 286 287 // Now that we removed this operand, see if there are no uses of it left. 288 if (Operand->use_empty()) 289 DeadNodes.push_back(Operand); 290 } 291 delete[] N->OperandList; 292 N->OperandList = 0; 293 N->NumOperands = 0; 294 295 // Finally, remove N itself. 296 AllNodes.erase(N); 297 } 298 299 // If the root changed (e.g. it was a dead load, update the root). 300 setRoot(Dummy.getValue()); 301} 302 303void SelectionDAG::RemoveDeadNode(SDNode *N, std::vector<SDNode*> &Deleted) { 304 SmallVector<SDNode*, 16> DeadNodes; 305 DeadNodes.push_back(N); 306 307 // Process the worklist, deleting the nodes and adding their uses to the 308 // worklist. 309 while (!DeadNodes.empty()) { 310 SDNode *N = DeadNodes.back(); 311 DeadNodes.pop_back(); 312 313 // Take the node out of the appropriate CSE map. 314 RemoveNodeFromCSEMaps(N); 315 316 // Next, brutally remove the operand list. This is safe to do, as there are 317 // no cycles in the graph. 318 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 319 SDNode *Operand = I->Val; 320 Operand->removeUser(N); 321 322 // Now that we removed this operand, see if there are no uses of it left. 323 if (Operand->use_empty()) 324 DeadNodes.push_back(Operand); 325 } 326 delete[] N->OperandList; 327 N->OperandList = 0; 328 N->NumOperands = 0; 329 330 // Finally, remove N itself. 331 Deleted.push_back(N); 332 AllNodes.erase(N); 333 } 334} 335 336void SelectionDAG::DeleteNode(SDNode *N) { 337 assert(N->use_empty() && "Cannot delete a node that is not dead!"); 338 339 // First take this out of the appropriate CSE map. 340 RemoveNodeFromCSEMaps(N); 341 342 // Finally, remove uses due to operands of this node, remove from the 343 // AllNodes list, and delete the node. 344 DeleteNodeNotInCSEMaps(N); 345} 346 347void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { 348 349 // Remove it from the AllNodes list. 350 AllNodes.remove(N); 351 352 // Drop all of the operands and decrement used nodes use counts. 353 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) 354 I->Val->removeUser(N); 355 delete[] N->OperandList; 356 N->OperandList = 0; 357 N->NumOperands = 0; 358 359 delete N; 360} 361 362/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that 363/// correspond to it. This is useful when we're about to delete or repurpose 364/// the node. We don't want future request for structurally identical nodes 365/// to return N anymore. 366void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { 367 bool Erased = false; 368 switch (N->getOpcode()) { 369 case ISD::HANDLENODE: return; // noop. 370 case ISD::STRING: 371 Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue()); 372 break; 373 case ISD::CONDCODE: 374 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] && 375 "Cond code doesn't exist!"); 376 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0; 377 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0; 378 break; 379 case ISD::ExternalSymbol: 380 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 381 break; 382 case ISD::TargetExternalSymbol: 383 Erased = 384 TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 385 break; 386 case ISD::VALUETYPE: 387 Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0; 388 ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0; 389 break; 390 default: 391 // Remove it from the CSE Map. 392 Erased = CSEMap.RemoveNode(N); 393 break; 394 } 395#ifndef NDEBUG 396 // Verify that the node was actually in one of the CSE maps, unless it has a 397 // flag result (which cannot be CSE'd) or is one of the special cases that are 398 // not subject to CSE. 399 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && 400 !N->isTargetOpcode()) { 401 N->dump(); 402 std::cerr << "\n"; 403 assert(0 && "Node is not in map!"); 404 } 405#endif 406} 407 408/// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps. It 409/// has been taken out and modified in some way. If the specified node already 410/// exists in the CSE maps, do not modify the maps, but return the existing node 411/// instead. If it doesn't exist, add it and return null. 412/// 413SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { 414 assert(N->getNumOperands() && "This is a leaf node!"); 415 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 416 return 0; // Never add these nodes. 417 418 // Check that remaining values produced are not flags. 419 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 420 if (N->getValueType(i) == MVT::Flag) 421 return 0; // Never CSE anything that produces a flag. 422 423 SDNode *New = CSEMap.GetOrInsertNode(N); 424 if (New != N) return New; // Node already existed. 425 return 0; 426} 427 428/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 429/// were replaced with those specified. If this node is never memoized, 430/// return null, otherwise return a pointer to the slot it would take. If a 431/// node already exists with these operands, the slot will be non-null. 432SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op, 433 void *&InsertPos) { 434 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 435 return 0; // Never add these nodes. 436 437 // Check that remaining values produced are not flags. 438 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 439 if (N->getValueType(i) == MVT::Flag) 440 return 0; // Never CSE anything that produces a flag. 441 442 SelectionDAGCSEMap::NodeID ID; 443 ID.SetOpcode(N->getOpcode()); 444 ID.SetValueTypes(N->getVTList()); 445 ID.SetOperands(Op); 446 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 447} 448 449/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 450/// were replaced with those specified. If this node is never memoized, 451/// return null, otherwise return a pointer to the slot it would take. If a 452/// node already exists with these operands, the slot will be non-null. 453SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 454 SDOperand Op1, SDOperand Op2, 455 void *&InsertPos) { 456 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 457 return 0; // Never add these nodes. 458 459 // Check that remaining values produced are not flags. 460 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 461 if (N->getValueType(i) == MVT::Flag) 462 return 0; // Never CSE anything that produces a flag. 463 464 SelectionDAGCSEMap::NodeID ID; 465 ID.SetOpcode(N->getOpcode()); 466 ID.SetValueTypes(N->getVTList()); 467 ID.SetOperands(Op1, Op2); 468 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 469} 470 471 472/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 473/// were replaced with those specified. If this node is never memoized, 474/// return null, otherwise return a pointer to the slot it would take. If a 475/// node already exists with these operands, the slot will be non-null. 476SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 477 const SDOperand *Ops,unsigned NumOps, 478 void *&InsertPos) { 479 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 480 return 0; // Never add these nodes. 481 482 // Check that remaining values produced are not flags. 483 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 484 if (N->getValueType(i) == MVT::Flag) 485 return 0; // Never CSE anything that produces a flag. 486 487 SelectionDAGCSEMap::NodeID ID; 488 ID.SetOpcode(N->getOpcode()); 489 ID.SetValueTypes(N->getVTList()); 490 if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(N)) { 491 ID.AddInteger(LD->getAddressingMode()); 492 ID.AddInteger(LD->getExtensionType()); 493 ID.AddInteger(LD->getLoadedVT()); 494 ID.AddPointer(LD->getSrcValue()); 495 ID.AddInteger(LD->getSrcValueOffset()); 496 ID.AddInteger(LD->getAlignment()); 497 ID.AddInteger(LD->isVolatile()); 498 } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(N)) { 499 ID.AddInteger(ST->getAddressingMode()); 500 ID.AddInteger(ST->isTruncatingStore()); 501 ID.AddInteger(ST->getStoredVT()); 502 ID.AddPointer(ST->getSrcValue()); 503 ID.AddInteger(ST->getSrcValueOffset()); 504 ID.AddInteger(ST->getAlignment()); 505 ID.AddInteger(ST->isVolatile()); 506 } 507 ID.SetOperands(Ops, NumOps); 508 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 509} 510 511 512SelectionDAG::~SelectionDAG() { 513 while (!AllNodes.empty()) { 514 SDNode *N = AllNodes.begin(); 515 N->SetNextInBucket(0); 516 delete [] N->OperandList; 517 N->OperandList = 0; 518 N->NumOperands = 0; 519 AllNodes.pop_front(); 520 } 521} 522 523SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) { 524 if (Op.getValueType() == VT) return Op; 525 int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT)); 526 return getNode(ISD::AND, Op.getValueType(), Op, 527 getConstant(Imm, Op.getValueType())); 528} 529 530SDOperand SelectionDAG::getString(const std::string &Val) { 531 StringSDNode *&N = StringNodes[Val]; 532 if (!N) { 533 N = new StringSDNode(Val); 534 AllNodes.push_back(N); 535 } 536 return SDOperand(N, 0); 537} 538 539SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT, bool isT) { 540 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 541 assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!"); 542 543 // Mask out any bits that are not valid for this constant. 544 Val &= MVT::getIntVTBitMask(VT); 545 546 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant; 547 SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); 548 ID.AddInteger(Val); 549 void *IP = 0; 550 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 551 return SDOperand(E, 0); 552 SDNode *N = new ConstantSDNode(isT, Val, VT); 553 CSEMap.InsertNode(N, IP); 554 AllNodes.push_back(N); 555 return SDOperand(N, 0); 556} 557 558 559SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT, 560 bool isTarget) { 561 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 562 if (VT == MVT::f32) 563 Val = (float)Val; // Mask out extra precision. 564 565 // Do the map lookup using the actual bit pattern for the floating point 566 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 567 // we don't have issues with SNANs. 568 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP; 569 SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); 570 ID.AddInteger(DoubleToBits(Val)); 571 void *IP = 0; 572 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 573 return SDOperand(E, 0); 574 SDNode *N = new ConstantFPSDNode(isTarget, Val, VT); 575 CSEMap.InsertNode(N, IP); 576 AllNodes.push_back(N); 577 return SDOperand(N, 0); 578} 579 580SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, 581 MVT::ValueType VT, int Offset, 582 bool isTargetGA) { 583 unsigned Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress; 584 SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); 585 ID.AddPointer(GV); 586 ID.AddInteger(Offset); 587 void *IP = 0; 588 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 589 return SDOperand(E, 0); 590 SDNode *N = new GlobalAddressSDNode(isTargetGA, GV, VT, Offset); 591 CSEMap.InsertNode(N, IP); 592 AllNodes.push_back(N); 593 return SDOperand(N, 0); 594} 595 596SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT, 597 bool isTarget) { 598 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex; 599 SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); 600 ID.AddInteger(FI); 601 void *IP = 0; 602 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 603 return SDOperand(E, 0); 604 SDNode *N = new FrameIndexSDNode(FI, VT, isTarget); 605 CSEMap.InsertNode(N, IP); 606 AllNodes.push_back(N); 607 return SDOperand(N, 0); 608} 609 610SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT, bool isTarget){ 611 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable; 612 SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); 613 ID.AddInteger(JTI); 614 void *IP = 0; 615 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 616 return SDOperand(E, 0); 617 SDNode *N = new JumpTableSDNode(JTI, VT, isTarget); 618 CSEMap.InsertNode(N, IP); 619 AllNodes.push_back(N); 620 return SDOperand(N, 0); 621} 622 623SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT, 624 unsigned Alignment, int Offset, 625 bool isTarget) { 626 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 627 SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); 628 ID.AddInteger(Alignment); 629 ID.AddInteger(Offset); 630 ID.AddPointer(C); 631 void *IP = 0; 632 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 633 return SDOperand(E, 0); 634 SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); 635 CSEMap.InsertNode(N, IP); 636 AllNodes.push_back(N); 637 return SDOperand(N, 0); 638} 639 640 641SDOperand SelectionDAG::getConstantPool(MachineConstantPoolValue *C, 642 MVT::ValueType VT, 643 unsigned Alignment, int Offset, 644 bool isTarget) { 645 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 646 SelectionDAGCSEMap::NodeID ID(Opc, getVTList(VT)); 647 ID.AddInteger(Alignment); 648 ID.AddInteger(Offset); 649 C->AddSelectionDAGCSEId(&ID); 650 void *IP = 0; 651 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 652 return SDOperand(E, 0); 653 SDNode *N = new ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment); 654 CSEMap.InsertNode(N, IP); 655 AllNodes.push_back(N); 656 return SDOperand(N, 0); 657} 658 659 660SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 661 SelectionDAGCSEMap::NodeID ID(ISD::BasicBlock, getVTList(MVT::Other)); 662 ID.AddPointer(MBB); 663 void *IP = 0; 664 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 665 return SDOperand(E, 0); 666 SDNode *N = new BasicBlockSDNode(MBB); 667 CSEMap.InsertNode(N, IP); 668 AllNodes.push_back(N); 669 return SDOperand(N, 0); 670} 671 672SDOperand SelectionDAG::getValueType(MVT::ValueType VT) { 673 if ((unsigned)VT >= ValueTypeNodes.size()) 674 ValueTypeNodes.resize(VT+1); 675 if (ValueTypeNodes[VT] == 0) { 676 ValueTypeNodes[VT] = new VTSDNode(VT); 677 AllNodes.push_back(ValueTypeNodes[VT]); 678 } 679 680 return SDOperand(ValueTypeNodes[VT], 0); 681} 682 683SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) { 684 SDNode *&N = ExternalSymbols[Sym]; 685 if (N) return SDOperand(N, 0); 686 N = new ExternalSymbolSDNode(false, Sym, VT); 687 AllNodes.push_back(N); 688 return SDOperand(N, 0); 689} 690 691SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym, 692 MVT::ValueType VT) { 693 SDNode *&N = TargetExternalSymbols[Sym]; 694 if (N) return SDOperand(N, 0); 695 N = new ExternalSymbolSDNode(true, Sym, VT); 696 AllNodes.push_back(N); 697 return SDOperand(N, 0); 698} 699 700SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) { 701 if ((unsigned)Cond >= CondCodeNodes.size()) 702 CondCodeNodes.resize(Cond+1); 703 704 if (CondCodeNodes[Cond] == 0) { 705 CondCodeNodes[Cond] = new CondCodeSDNode(Cond); 706 AllNodes.push_back(CondCodeNodes[Cond]); 707 } 708 return SDOperand(CondCodeNodes[Cond], 0); 709} 710 711SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) { 712 SelectionDAGCSEMap::NodeID ID(ISD::Register, getVTList(VT)); 713 ID.AddInteger(RegNo); 714 void *IP = 0; 715 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 716 return SDOperand(E, 0); 717 SDNode *N = new RegisterSDNode(RegNo, VT); 718 CSEMap.InsertNode(N, IP); 719 AllNodes.push_back(N); 720 return SDOperand(N, 0); 721} 722 723SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { 724 assert((!V || isa<PointerType>(V->getType())) && 725 "SrcValue is not a pointer?"); 726 727 SelectionDAGCSEMap::NodeID ID(ISD::SRCVALUE, getVTList(MVT::Other)); 728 ID.AddPointer(V); 729 ID.AddInteger(Offset); 730 void *IP = 0; 731 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 732 return SDOperand(E, 0); 733 SDNode *N = new SrcValueSDNode(V, Offset); 734 CSEMap.InsertNode(N, IP); 735 AllNodes.push_back(N); 736 return SDOperand(N, 0); 737} 738 739SDOperand SelectionDAG::FoldSetCC(MVT::ValueType VT, SDOperand N1, 740 SDOperand N2, ISD::CondCode Cond) { 741 // These setcc operations always fold. 742 switch (Cond) { 743 default: break; 744 case ISD::SETFALSE: 745 case ISD::SETFALSE2: return getConstant(0, VT); 746 case ISD::SETTRUE: 747 case ISD::SETTRUE2: return getConstant(1, VT); 748 749 case ISD::SETOEQ: 750 case ISD::SETOGT: 751 case ISD::SETOGE: 752 case ISD::SETOLT: 753 case ISD::SETOLE: 754 case ISD::SETONE: 755 case ISD::SETO: 756 case ISD::SETUO: 757 case ISD::SETUEQ: 758 case ISD::SETUNE: 759 assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!"); 760 break; 761 } 762 763 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) { 764 uint64_t C2 = N2C->getValue(); 765 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 766 uint64_t C1 = N1C->getValue(); 767 768 // Sign extend the operands if required 769 if (ISD::isSignedIntSetCC(Cond)) { 770 C1 = N1C->getSignExtended(); 771 C2 = N2C->getSignExtended(); 772 } 773 774 switch (Cond) { 775 default: assert(0 && "Unknown integer setcc!"); 776 case ISD::SETEQ: return getConstant(C1 == C2, VT); 777 case ISD::SETNE: return getConstant(C1 != C2, VT); 778 case ISD::SETULT: return getConstant(C1 < C2, VT); 779 case ISD::SETUGT: return getConstant(C1 > C2, VT); 780 case ISD::SETULE: return getConstant(C1 <= C2, VT); 781 case ISD::SETUGE: return getConstant(C1 >= C2, VT); 782 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, VT); 783 case ISD::SETGT: return getConstant((int64_t)C1 > (int64_t)C2, VT); 784 case ISD::SETLE: return getConstant((int64_t)C1 <= (int64_t)C2, VT); 785 case ISD::SETGE: return getConstant((int64_t)C1 >= (int64_t)C2, VT); 786 } 787 } 788 } 789 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) 790 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) { 791 double C1 = N1C->getValue(), C2 = N2C->getValue(); 792 793 switch (Cond) { 794 default: break; // FIXME: Implement the rest of these! 795 case ISD::SETEQ: return getConstant(C1 == C2, VT); 796 case ISD::SETNE: return getConstant(C1 != C2, VT); 797 case ISD::SETLT: return getConstant(C1 < C2, VT); 798 case ISD::SETGT: return getConstant(C1 > C2, VT); 799 case ISD::SETLE: return getConstant(C1 <= C2, VT); 800 case ISD::SETGE: return getConstant(C1 >= C2, VT); 801 } 802 } else { 803 // Ensure that the constant occurs on the RHS. 804 return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 805 } 806 807 // Could not fold it. 808 return SDOperand(); 809} 810 811 812/// getNode - Gets or creates the specified node. 813/// 814SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { 815 SelectionDAGCSEMap::NodeID ID(Opcode, getVTList(VT)); 816 void *IP = 0; 817 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 818 return SDOperand(E, 0); 819 SDNode *N = new SDNode(Opcode, VT); 820 CSEMap.InsertNode(N, IP); 821 822 AllNodes.push_back(N); 823 return SDOperand(N, 0); 824} 825 826SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 827 SDOperand Operand) { 828 unsigned Tmp1; 829 // Constant fold unary operations with an integer constant operand. 830 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) { 831 uint64_t Val = C->getValue(); 832 switch (Opcode) { 833 default: break; 834 case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT); 835 case ISD::ANY_EXTEND: 836 case ISD::ZERO_EXTEND: return getConstant(Val, VT); 837 case ISD::TRUNCATE: return getConstant(Val, VT); 838 case ISD::SINT_TO_FP: return getConstantFP(C->getSignExtended(), VT); 839 case ISD::UINT_TO_FP: return getConstantFP(C->getValue(), VT); 840 case ISD::BIT_CONVERT: 841 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32) 842 return getConstantFP(BitsToFloat(Val), VT); 843 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64) 844 return getConstantFP(BitsToDouble(Val), VT); 845 break; 846 case ISD::BSWAP: 847 switch(VT) { 848 default: assert(0 && "Invalid bswap!"); break; 849 case MVT::i16: return getConstant(ByteSwap_16((unsigned short)Val), VT); 850 case MVT::i32: return getConstant(ByteSwap_32((unsigned)Val), VT); 851 case MVT::i64: return getConstant(ByteSwap_64(Val), VT); 852 } 853 break; 854 case ISD::CTPOP: 855 switch(VT) { 856 default: assert(0 && "Invalid ctpop!"); break; 857 case MVT::i1: return getConstant(Val != 0, VT); 858 case MVT::i8: 859 Tmp1 = (unsigned)Val & 0xFF; 860 return getConstant(CountPopulation_32(Tmp1), VT); 861 case MVT::i16: 862 Tmp1 = (unsigned)Val & 0xFFFF; 863 return getConstant(CountPopulation_32(Tmp1), VT); 864 case MVT::i32: 865 return getConstant(CountPopulation_32((unsigned)Val), VT); 866 case MVT::i64: 867 return getConstant(CountPopulation_64(Val), VT); 868 } 869 case ISD::CTLZ: 870 switch(VT) { 871 default: assert(0 && "Invalid ctlz!"); break; 872 case MVT::i1: return getConstant(Val == 0, VT); 873 case MVT::i8: 874 Tmp1 = (unsigned)Val & 0xFF; 875 return getConstant(CountLeadingZeros_32(Tmp1)-24, VT); 876 case MVT::i16: 877 Tmp1 = (unsigned)Val & 0xFFFF; 878 return getConstant(CountLeadingZeros_32(Tmp1)-16, VT); 879 case MVT::i32: 880 return getConstant(CountLeadingZeros_32((unsigned)Val), VT); 881 case MVT::i64: 882 return getConstant(CountLeadingZeros_64(Val), VT); 883 } 884 case ISD::CTTZ: 885 switch(VT) { 886 default: assert(0 && "Invalid cttz!"); break; 887 case MVT::i1: return getConstant(Val == 0, VT); 888 case MVT::i8: 889 Tmp1 = (unsigned)Val | 0x100; 890 return getConstant(CountTrailingZeros_32(Tmp1), VT); 891 case MVT::i16: 892 Tmp1 = (unsigned)Val | 0x10000; 893 return getConstant(CountTrailingZeros_32(Tmp1), VT); 894 case MVT::i32: 895 return getConstant(CountTrailingZeros_32((unsigned)Val), VT); 896 case MVT::i64: 897 return getConstant(CountTrailingZeros_64(Val), VT); 898 } 899 } 900 } 901 902 // Constant fold unary operations with an floating point constant operand. 903 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) 904 switch (Opcode) { 905 case ISD::FNEG: 906 return getConstantFP(-C->getValue(), VT); 907 case ISD::FABS: 908 return getConstantFP(fabs(C->getValue()), VT); 909 case ISD::FP_ROUND: 910 case ISD::FP_EXTEND: 911 return getConstantFP(C->getValue(), VT); 912 case ISD::FP_TO_SINT: 913 return getConstant((int64_t)C->getValue(), VT); 914 case ISD::FP_TO_UINT: 915 return getConstant((uint64_t)C->getValue(), VT); 916 case ISD::BIT_CONVERT: 917 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32) 918 return getConstant(FloatToBits(C->getValue()), VT); 919 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64) 920 return getConstant(DoubleToBits(C->getValue()), VT); 921 break; 922 } 923 924 unsigned OpOpcode = Operand.Val->getOpcode(); 925 switch (Opcode) { 926 case ISD::TokenFactor: 927 return Operand; // Factor of one node? No factor. 928 case ISD::SIGN_EXTEND: 929 if (Operand.getValueType() == VT) return Operand; // noop extension 930 assert(Operand.getValueType() < VT && "Invalid sext node, dst < src!"); 931 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 932 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 933 break; 934 case ISD::ZERO_EXTEND: 935 if (Operand.getValueType() == VT) return Operand; // noop extension 936 assert(Operand.getValueType() < VT && "Invalid zext node, dst < src!"); 937 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x) 938 return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0)); 939 break; 940 case ISD::ANY_EXTEND: 941 if (Operand.getValueType() == VT) return Operand; // noop extension 942 assert(Operand.getValueType() < VT && "Invalid anyext node, dst < src!"); 943 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) 944 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x) 945 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 946 break; 947 case ISD::TRUNCATE: 948 if (Operand.getValueType() == VT) return Operand; // noop truncate 949 assert(Operand.getValueType() > VT && "Invalid truncate node, src < dst!"); 950 if (OpOpcode == ISD::TRUNCATE) 951 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 952 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || 953 OpOpcode == ISD::ANY_EXTEND) { 954 // If the source is smaller than the dest, we still need an extend. 955 if (Operand.Val->getOperand(0).getValueType() < VT) 956 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 957 else if (Operand.Val->getOperand(0).getValueType() > VT) 958 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 959 else 960 return Operand.Val->getOperand(0); 961 } 962 break; 963 case ISD::BIT_CONVERT: 964 // Basic sanity checking. 965 assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType()) 966 && "Cannot BIT_CONVERT between two different types!"); 967 if (VT == Operand.getValueType()) return Operand; // noop conversion. 968 if (OpOpcode == ISD::BIT_CONVERT) // bitconv(bitconv(x)) -> bitconv(x) 969 return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0)); 970 if (OpOpcode == ISD::UNDEF) 971 return getNode(ISD::UNDEF, VT); 972 break; 973 case ISD::SCALAR_TO_VECTOR: 974 assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) && 975 MVT::getVectorBaseType(VT) == Operand.getValueType() && 976 "Illegal SCALAR_TO_VECTOR node!"); 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 SDVTList VTs = getVTList(VT); 993 if (VT != MVT::Flag) { // Don't CSE flag producing nodes 994 SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Operand); 995 void *IP = 0; 996 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 997 return SDOperand(E, 0); 998 N = new SDNode(Opcode, Operand); 999 N->setValueTypes(VTs); 1000 CSEMap.InsertNode(N, IP); 1001 } else { 1002 N = new SDNode(Opcode, Operand); 1003 N->setValueTypes(VTs); 1004 } 1005 AllNodes.push_back(N); 1006 return SDOperand(N, 0); 1007} 1008 1009 1010 1011SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1012 SDOperand N1, SDOperand N2) { 1013#ifndef NDEBUG 1014 switch (Opcode) { 1015 case ISD::TokenFactor: 1016 assert(VT == MVT::Other && N1.getValueType() == MVT::Other && 1017 N2.getValueType() == MVT::Other && "Invalid token factor!"); 1018 break; 1019 case ISD::AND: 1020 case ISD::OR: 1021 case ISD::XOR: 1022 case ISD::UDIV: 1023 case ISD::UREM: 1024 case ISD::MULHU: 1025 case ISD::MULHS: 1026 assert(MVT::isInteger(VT) && "This operator does not apply to FP types!"); 1027 // fall through 1028 case ISD::ADD: 1029 case ISD::SUB: 1030 case ISD::MUL: 1031 case ISD::SDIV: 1032 case ISD::SREM: 1033 assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops"); 1034 // fall through. 1035 case ISD::FADD: 1036 case ISD::FSUB: 1037 case ISD::FMUL: 1038 case ISD::FDIV: 1039 case ISD::FREM: 1040 assert(N1.getValueType() == N2.getValueType() && 1041 N1.getValueType() == VT && "Binary operator types must match!"); 1042 break; 1043 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match. 1044 assert(N1.getValueType() == VT && 1045 MVT::isFloatingPoint(N1.getValueType()) && 1046 MVT::isFloatingPoint(N2.getValueType()) && 1047 "Invalid FCOPYSIGN!"); 1048 break; 1049 case ISD::SHL: 1050 case ISD::SRA: 1051 case ISD::SRL: 1052 case ISD::ROTL: 1053 case ISD::ROTR: 1054 assert(VT == N1.getValueType() && 1055 "Shift operators return type must be the same as their first arg"); 1056 assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) && 1057 VT != MVT::i1 && "Shifts only work on integers"); 1058 break; 1059 case ISD::FP_ROUND_INREG: { 1060 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1061 assert(VT == N1.getValueType() && "Not an inreg round!"); 1062 assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) && 1063 "Cannot FP_ROUND_INREG integer types"); 1064 assert(EVT <= VT && "Not rounding down!"); 1065 break; 1066 } 1067 case ISD::AssertSext: 1068 case ISD::AssertZext: 1069 case ISD::SIGN_EXTEND_INREG: { 1070 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1071 assert(VT == N1.getValueType() && "Not an inreg extend!"); 1072 assert(MVT::isInteger(VT) && MVT::isInteger(EVT) && 1073 "Cannot *_EXTEND_INREG FP types"); 1074 assert(EVT <= VT && "Not extending!"); 1075 } 1076 1077 default: break; 1078 } 1079#endif 1080 1081 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 1082 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 1083 if (N1C) { 1084 if (Opcode == ISD::SIGN_EXTEND_INREG) { 1085 int64_t Val = N1C->getValue(); 1086 unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT()); 1087 Val <<= 64-FromBits; 1088 Val >>= 64-FromBits; 1089 return getConstant(Val, VT); 1090 } 1091 1092 if (N2C) { 1093 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 1094 switch (Opcode) { 1095 case ISD::ADD: return getConstant(C1 + C2, VT); 1096 case ISD::SUB: return getConstant(C1 - C2, VT); 1097 case ISD::MUL: return getConstant(C1 * C2, VT); 1098 case ISD::UDIV: 1099 if (C2) return getConstant(C1 / C2, VT); 1100 break; 1101 case ISD::UREM : 1102 if (C2) return getConstant(C1 % C2, VT); 1103 break; 1104 case ISD::SDIV : 1105 if (C2) return getConstant(N1C->getSignExtended() / 1106 N2C->getSignExtended(), VT); 1107 break; 1108 case ISD::SREM : 1109 if (C2) return getConstant(N1C->getSignExtended() % 1110 N2C->getSignExtended(), VT); 1111 break; 1112 case ISD::AND : return getConstant(C1 & C2, VT); 1113 case ISD::OR : return getConstant(C1 | C2, VT); 1114 case ISD::XOR : return getConstant(C1 ^ C2, VT); 1115 case ISD::SHL : return getConstant(C1 << C2, VT); 1116 case ISD::SRL : return getConstant(C1 >> C2, VT); 1117 case ISD::SRA : return getConstant(N1C->getSignExtended() >>(int)C2, VT); 1118 case ISD::ROTL : 1119 return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)), 1120 VT); 1121 case ISD::ROTR : 1122 return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)), 1123 VT); 1124 default: break; 1125 } 1126 } else { // Cannonicalize constant to RHS if commutative 1127 if (isCommutativeBinOp(Opcode)) { 1128 std::swap(N1C, N2C); 1129 std::swap(N1, N2); 1130 } 1131 } 1132 } 1133 1134 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); 1135 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val); 1136 if (N1CFP) { 1137 if (N2CFP) { 1138 double C1 = N1CFP->getValue(), C2 = N2CFP->getValue(); 1139 switch (Opcode) { 1140 case ISD::FADD: return getConstantFP(C1 + C2, VT); 1141 case ISD::FSUB: return getConstantFP(C1 - C2, VT); 1142 case ISD::FMUL: return getConstantFP(C1 * C2, VT); 1143 case ISD::FDIV: 1144 if (C2) return getConstantFP(C1 / C2, VT); 1145 break; 1146 case ISD::FREM : 1147 if (C2) return getConstantFP(fmod(C1, C2), VT); 1148 break; 1149 case ISD::FCOPYSIGN: { 1150 union { 1151 double F; 1152 uint64_t I; 1153 } u1; 1154 union { 1155 double F; 1156 int64_t I; 1157 } u2; 1158 u1.F = C1; 1159 u2.F = C2; 1160 if (u2.I < 0) // Sign bit of RHS set? 1161 u1.I |= 1ULL << 63; // Set the sign bit of the LHS. 1162 else 1163 u1.I &= (1ULL << 63)-1; // Clear the sign bit of the LHS. 1164 return getConstantFP(u1.F, VT); 1165 } 1166 default: break; 1167 } 1168 } else { // Cannonicalize constant to RHS if commutative 1169 if (isCommutativeBinOp(Opcode)) { 1170 std::swap(N1CFP, N2CFP); 1171 std::swap(N1, N2); 1172 } 1173 } 1174 } 1175 1176 // Canonicalize an UNDEF to the RHS, even over a constant. 1177 if (N1.getOpcode() == ISD::UNDEF) { 1178 if (isCommutativeBinOp(Opcode)) { 1179 std::swap(N1, N2); 1180 } else { 1181 switch (Opcode) { 1182 case ISD::FP_ROUND_INREG: 1183 case ISD::SIGN_EXTEND_INREG: 1184 case ISD::SUB: 1185 case ISD::FSUB: 1186 case ISD::FDIV: 1187 case ISD::FREM: 1188 case ISD::SRA: 1189 return N1; // fold op(undef, arg2) -> undef 1190 case ISD::UDIV: 1191 case ISD::SDIV: 1192 case ISD::UREM: 1193 case ISD::SREM: 1194 case ISD::SRL: 1195 case ISD::SHL: 1196 return getConstant(0, VT); // fold op(undef, arg2) -> 0 1197 } 1198 } 1199 } 1200 1201 // Fold a bunch of operators when the RHS is undef. 1202 if (N2.getOpcode() == ISD::UNDEF) { 1203 switch (Opcode) { 1204 case ISD::ADD: 1205 case ISD::SUB: 1206 case ISD::FADD: 1207 case ISD::FSUB: 1208 case ISD::FMUL: 1209 case ISD::FDIV: 1210 case ISD::FREM: 1211 case ISD::UDIV: 1212 case ISD::SDIV: 1213 case ISD::UREM: 1214 case ISD::SREM: 1215 case ISD::XOR: 1216 return N2; // fold op(arg1, undef) -> undef 1217 case ISD::MUL: 1218 case ISD::AND: 1219 case ISD::SRL: 1220 case ISD::SHL: 1221 return getConstant(0, VT); // fold op(arg1, undef) -> 0 1222 case ISD::OR: 1223 return getConstant(MVT::getIntVTBitMask(VT), VT); 1224 case ISD::SRA: 1225 return N1; 1226 } 1227 } 1228 1229 // Fold operations. 1230 switch (Opcode) { 1231 case ISD::AND: 1232 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's 1233 // worth handling here. 1234 if (N2C && N2C->getValue() == 0) 1235 return N2; 1236 break; 1237 case ISD::FP_ROUND_INREG: 1238 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding. 1239 break; 1240 case ISD::SIGN_EXTEND_INREG: { 1241 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 1242 if (EVT == VT) return N1; // Not actually extending 1243 break; 1244 } 1245 case ISD::EXTRACT_ELEMENT: 1246 assert(N2C && (unsigned)N2C->getValue() < 2 && "Bad EXTRACT_ELEMENT!"); 1247 1248 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding 1249 // 64-bit integers into 32-bit parts. Instead of building the extract of 1250 // the BUILD_PAIR, only to have legalize rip it apart, just do it now. 1251 if (N1.getOpcode() == ISD::BUILD_PAIR) 1252 return N1.getOperand(N2C->getValue()); 1253 1254 // EXTRACT_ELEMENT of a constant int is also very common. 1255 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) { 1256 unsigned Shift = MVT::getSizeInBits(VT) * N2C->getValue(); 1257 return getConstant(C->getValue() >> Shift, VT); 1258 } 1259 break; 1260 1261 // FIXME: figure out how to safely handle things like 1262 // int foo(int x) { return 1 << (x & 255); } 1263 // int bar() { return foo(256); } 1264#if 0 1265 case ISD::SHL: 1266 case ISD::SRL: 1267 case ISD::SRA: 1268 if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG && 1269 cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1) 1270 return getNode(Opcode, VT, N1, N2.getOperand(0)); 1271 else if (N2.getOpcode() == ISD::AND) 1272 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) { 1273 // If the and is only masking out bits that cannot effect the shift, 1274 // eliminate the and. 1275 unsigned NumBits = MVT::getSizeInBits(VT); 1276 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 1277 return getNode(Opcode, VT, N1, N2.getOperand(0)); 1278 } 1279 break; 1280#endif 1281 } 1282 1283 // Memoize this node if possible. 1284 SDNode *N; 1285 SDVTList VTs = getVTList(VT); 1286 if (VT != MVT::Flag) { 1287 SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2); 1288 void *IP = 0; 1289 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1290 return SDOperand(E, 0); 1291 N = new SDNode(Opcode, N1, N2); 1292 N->setValueTypes(VTs); 1293 CSEMap.InsertNode(N, IP); 1294 } else { 1295 N = new SDNode(Opcode, N1, N2); 1296 N->setValueTypes(VTs); 1297 } 1298 1299 AllNodes.push_back(N); 1300 return SDOperand(N, 0); 1301} 1302 1303SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1304 SDOperand N1, SDOperand N2, SDOperand N3) { 1305 // Perform various simplifications. 1306 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 1307 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 1308 //ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 1309 switch (Opcode) { 1310 case ISD::SETCC: { 1311 // Use FoldSetCC to simplify SETCC's. 1312 SDOperand Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get()); 1313 if (Simp.Val) return Simp; 1314 break; 1315 } 1316 case ISD::SELECT: 1317 if (N1C) 1318 if (N1C->getValue()) 1319 return N2; // select true, X, Y -> X 1320 else 1321 return N3; // select false, X, Y -> Y 1322 1323 if (N2 == N3) return N2; // select C, X, X -> X 1324 break; 1325 case ISD::BRCOND: 1326 if (N2C) 1327 if (N2C->getValue()) // Unconditional branch 1328 return getNode(ISD::BR, MVT::Other, N1, N3); 1329 else 1330 return N1; // Never-taken branch 1331 break; 1332 case ISD::VECTOR_SHUFFLE: 1333 assert(VT == N1.getValueType() && VT == N2.getValueType() && 1334 MVT::isVector(VT) && MVT::isVector(N3.getValueType()) && 1335 N3.getOpcode() == ISD::BUILD_VECTOR && 1336 MVT::getVectorNumElements(VT) == N3.getNumOperands() && 1337 "Illegal VECTOR_SHUFFLE node!"); 1338 break; 1339 } 1340 1341 // Memoize node if it doesn't produce a flag. 1342 SDNode *N; 1343 SDVTList VTs = getVTList(VT); 1344 if (VT != MVT::Flag) { 1345 SelectionDAGCSEMap::NodeID ID(Opcode, VTs, N1, N2, N3); 1346 void *IP = 0; 1347 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1348 return SDOperand(E, 0); 1349 N = new SDNode(Opcode, N1, N2, N3); 1350 N->setValueTypes(VTs); 1351 CSEMap.InsertNode(N, IP); 1352 } else { 1353 N = new SDNode(Opcode, N1, N2, N3); 1354 N->setValueTypes(VTs); 1355 } 1356 AllNodes.push_back(N); 1357 return SDOperand(N, 0); 1358} 1359 1360SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1361 SDOperand N1, SDOperand N2, SDOperand N3, 1362 SDOperand N4) { 1363 SDOperand Ops[] = { N1, N2, N3, N4 }; 1364 return getNode(Opcode, VT, Ops, 4); 1365} 1366 1367SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1368 SDOperand N1, SDOperand N2, SDOperand N3, 1369 SDOperand N4, SDOperand N5) { 1370 SDOperand Ops[] = { N1, N2, N3, N4, N5 }; 1371 return getNode(Opcode, VT, Ops, 5); 1372} 1373 1374SDOperand SelectionDAG::getLoad(MVT::ValueType VT, 1375 SDOperand Chain, SDOperand Ptr, 1376 const Value *SV, int SVOffset, 1377 bool isVolatile) { 1378 // FIXME: Alignment == 1 for now. 1379 unsigned Alignment = 1; 1380 SDVTList VTs = getVTList(VT, MVT::Other); 1381 SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); 1382 SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, Undef); 1383 ID.AddInteger(ISD::UNINDEXED); 1384 ID.AddInteger(ISD::NON_EXTLOAD); 1385 ID.AddInteger(VT); 1386 ID.AddPointer(SV); 1387 ID.AddInteger(SVOffset); 1388 ID.AddInteger(Alignment); 1389 ID.AddInteger(isVolatile); 1390 void *IP = 0; 1391 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1392 return SDOperand(E, 0); 1393 SDNode *N = new LoadSDNode(Chain, Ptr, Undef, ISD::UNINDEXED, 1394 ISD::NON_EXTLOAD, VT, SV, SVOffset, Alignment, 1395 isVolatile); 1396 N->setValueTypes(VTs); 1397 CSEMap.InsertNode(N, IP); 1398 AllNodes.push_back(N); 1399 return SDOperand(N, 0); 1400} 1401 1402SDOperand SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, MVT::ValueType VT, 1403 SDOperand Chain, SDOperand Ptr, const Value *SV, 1404 int SVOffset, MVT::ValueType EVT, 1405 bool isVolatile) { 1406 // If they are asking for an extending load from/to the same thing, return a 1407 // normal load. 1408 if (VT == EVT) 1409 ExtType = ISD::NON_EXTLOAD; 1410 1411 if (MVT::isVector(VT)) 1412 assert(EVT == MVT::getVectorBaseType(VT) && "Invalid vector extload!"); 1413 else 1414 assert(EVT < VT && "Should only be an extending load, not truncating!"); 1415 assert((ExtType == ISD::EXTLOAD || MVT::isInteger(VT)) && 1416 "Cannot sign/zero extend a FP/Vector load!"); 1417 assert(MVT::isInteger(VT) == MVT::isInteger(EVT) && 1418 "Cannot convert from FP to Int or Int -> FP!"); 1419 1420 // FIXME: Alignment == 1 for now. 1421 unsigned Alignment = 1; 1422 SDVTList VTs = getVTList(VT, MVT::Other); 1423 SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); 1424 SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, Chain, Ptr, Undef); 1425 ID.AddInteger(ISD::UNINDEXED); 1426 ID.AddInteger(ExtType); 1427 ID.AddInteger(EVT); 1428 ID.AddPointer(SV); 1429 ID.AddInteger(SVOffset); 1430 ID.AddInteger(Alignment); 1431 ID.AddInteger(isVolatile); 1432 void *IP = 0; 1433 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1434 return SDOperand(E, 0); 1435 SDNode *N = new LoadSDNode(Chain, Ptr, Undef, ISD::UNINDEXED, ExtType, EVT, 1436 SV, SVOffset, Alignment, isVolatile); 1437 N->setValueTypes(VTs); 1438 CSEMap.InsertNode(N, IP); 1439 AllNodes.push_back(N); 1440 return SDOperand(N, 0); 1441} 1442 1443SDOperand SelectionDAG::getPreIndexedLoad(SDOperand OrigLoad, SDOperand Base) { 1444 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad); 1445 SDOperand Ptr = LD->getBasePtr(); 1446 MVT::ValueType PtrVT = Ptr.getValueType(); 1447 unsigned Opc = Ptr.getOpcode(); 1448 SDOperand Offset = LD->getOffset(); 1449 assert(Offset.getOpcode() == ISD::UNDEF); 1450 assert((Opc == ISD::ADD || Opc == ISD::SUB) && 1451 "Load address must be <base +/- offset>!"); 1452 ISD::MemOpAddrMode AM = (Opc == ISD::ADD) ? ISD::PRE_INC : ISD::PRE_DEC; 1453 if (Ptr.getOperand(0) == Base) { 1454 Offset = Ptr.getOperand(1); 1455 Ptr = Ptr.getOperand(0); 1456 } else { 1457 assert(Ptr.getOperand(1) == Base); 1458 Offset = Ptr.getOperand(0); 1459 Ptr = Ptr.getOperand(1); 1460 } 1461 1462 MVT::ValueType VT = OrigLoad.getValueType(); 1463 SDVTList VTs = getVTList(VT, PtrVT, MVT::Other); 1464 SelectionDAGCSEMap::NodeID ID(ISD::LOAD, VTs, LD->getChain(), Ptr, Offset); 1465 ID.AddInteger(AM); 1466 ID.AddInteger(LD->getExtensionType()); 1467 ID.AddInteger(LD->getLoadedVT()); 1468 ID.AddPointer(LD->getSrcValue()); 1469 ID.AddInteger(LD->getSrcValueOffset()); 1470 ID.AddInteger(LD->getAlignment()); 1471 ID.AddInteger(LD->isVolatile()); 1472 void *IP = 0; 1473 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1474 return SDOperand(E, 0); 1475 SDNode *N = new LoadSDNode(LD->getChain(), Ptr, Offset, AM, 1476 LD->getExtensionType(), LD->getLoadedVT(), 1477 LD->getSrcValue(), LD->getSrcValueOffset(), 1478 LD->getAlignment(), LD->isVolatile()); 1479 N->setValueTypes(VTs); 1480 CSEMap.InsertNode(N, IP); 1481 AllNodes.push_back(N); 1482 return SDOperand(N, 0); 1483} 1484 1485SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT, 1486 SDOperand Chain, SDOperand Ptr, 1487 SDOperand SV) { 1488 SDOperand Ops[] = { Chain, Ptr, SV, getConstant(Count, MVT::i32), 1489 getValueType(EVT) }; 1490 return getNode(ISD::VLOAD, getVTList(MVT::Vector, MVT::Other), Ops, 5); 1491} 1492 1493SDOperand SelectionDAG::getStore(SDOperand Chain, SDOperand Value, 1494 SDOperand Ptr, const Value *SV, int SVOffset, 1495 bool isVolatile) { 1496 MVT::ValueType VT = Value.getValueType(); 1497 1498 // FIXME: Alignment == 1 for now. 1499 unsigned Alignment = 1; 1500 SDVTList VTs = getVTList(MVT::Other); 1501 SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); 1502 SDOperand Ops[] = { Chain, Value, Ptr, Undef }; 1503 SelectionDAGCSEMap::NodeID ID(ISD::STORE, VTs, Ops, 4); 1504 ID.AddInteger(ISD::UNINDEXED); 1505 ID.AddInteger(false); 1506 ID.AddInteger(VT); 1507 ID.AddPointer(SV); 1508 ID.AddInteger(SVOffset); 1509 ID.AddInteger(Alignment); 1510 ID.AddInteger(isVolatile); 1511 void *IP = 0; 1512 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1513 return SDOperand(E, 0); 1514 SDNode *N = new StoreSDNode(Chain, Value, Ptr, Undef, ISD::UNINDEXED, false, 1515 VT, SV, SVOffset, Alignment, isVolatile); 1516 N->setValueTypes(VTs); 1517 CSEMap.InsertNode(N, IP); 1518 AllNodes.push_back(N); 1519 return SDOperand(N, 0); 1520} 1521 1522SDOperand SelectionDAG::getTruncStore(SDOperand Chain, SDOperand Value, 1523 SDOperand Ptr, const Value *SV, 1524 int SVOffset, MVT::ValueType SVT, 1525 bool isVolatile) { 1526 MVT::ValueType VT = Value.getValueType(); 1527 bool isTrunc = VT != SVT; 1528 1529 assert(VT > SVT && "Not a truncation?"); 1530 assert(MVT::isInteger(VT) == MVT::isInteger(SVT) && 1531 "Can't do FP-INT conversion!"); 1532 1533 // FIXME: Alignment == 1 for now. 1534 unsigned Alignment = 1; 1535 SDVTList VTs = getVTList(MVT::Other); 1536 SDOperand Undef = getNode(ISD::UNDEF, Ptr.getValueType()); 1537 SDOperand Ops[] = { Chain, Value, Ptr, Undef }; 1538 SelectionDAGCSEMap::NodeID ID(ISD::STORE, VTs, Ops, 4); 1539 ID.AddInteger(ISD::UNINDEXED); 1540 ID.AddInteger(isTrunc); 1541 ID.AddInteger(SVT); 1542 ID.AddPointer(SV); 1543 ID.AddInteger(SVOffset); 1544 ID.AddInteger(Alignment); 1545 ID.AddInteger(isVolatile); 1546 void *IP = 0; 1547 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1548 return SDOperand(E, 0); 1549 SDNode *N = new StoreSDNode(Chain, Value, Ptr, Undef, ISD::UNINDEXED, isTrunc, 1550 SVT, SV, SVOffset, Alignment, isVolatile); 1551 N->setValueTypes(VTs); 1552 CSEMap.InsertNode(N, IP); 1553 AllNodes.push_back(N); 1554 return SDOperand(N, 0); 1555} 1556 1557SDOperand SelectionDAG::getVAArg(MVT::ValueType VT, 1558 SDOperand Chain, SDOperand Ptr, 1559 SDOperand SV) { 1560 SDOperand Ops[] = { Chain, Ptr, SV }; 1561 return getNode(ISD::VAARG, getVTList(VT, MVT::Other), Ops, 3); 1562} 1563 1564SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 1565 const SDOperand *Ops, unsigned NumOps) { 1566 switch (NumOps) { 1567 case 0: return getNode(Opcode, VT); 1568 case 1: return getNode(Opcode, VT, Ops[0]); 1569 case 2: return getNode(Opcode, VT, Ops[0], Ops[1]); 1570 case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]); 1571 default: break; 1572 } 1573 1574 switch (Opcode) { 1575 default: break; 1576 case ISD::SELECT_CC: { 1577 assert(NumOps == 5 && "SELECT_CC takes 5 operands!"); 1578 assert(Ops[0].getValueType() == Ops[1].getValueType() && 1579 "LHS and RHS of condition must have same type!"); 1580 assert(Ops[2].getValueType() == Ops[3].getValueType() && 1581 "True and False arms of SelectCC must have same type!"); 1582 assert(Ops[2].getValueType() == VT && 1583 "select_cc node must be of same type as true and false value!"); 1584 break; 1585 } 1586 case ISD::BR_CC: { 1587 assert(NumOps == 5 && "BR_CC takes 5 operands!"); 1588 assert(Ops[2].getValueType() == Ops[3].getValueType() && 1589 "LHS/RHS of comparison should match types!"); 1590 break; 1591 } 1592 } 1593 1594 // Memoize nodes. 1595 SDNode *N; 1596 SDVTList VTs = getVTList(VT); 1597 if (VT != MVT::Flag) { 1598 SelectionDAGCSEMap::NodeID ID(Opcode, VTs, Ops, NumOps); 1599 void *IP = 0; 1600 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1601 return SDOperand(E, 0); 1602 N = new SDNode(Opcode, Ops, NumOps); 1603 N->setValueTypes(VTs); 1604 CSEMap.InsertNode(N, IP); 1605 } else { 1606 N = new SDNode(Opcode, Ops, NumOps); 1607 N->setValueTypes(VTs); 1608 } 1609 AllNodes.push_back(N); 1610 return SDOperand(N, 0); 1611} 1612 1613SDOperand SelectionDAG::getNode(unsigned Opcode, 1614 std::vector<MVT::ValueType> &ResultTys, 1615 const SDOperand *Ops, unsigned NumOps) { 1616 return getNode(Opcode, getNodeValueTypes(ResultTys), ResultTys.size(), 1617 Ops, NumOps); 1618} 1619 1620SDOperand SelectionDAG::getNode(unsigned Opcode, 1621 const MVT::ValueType *VTs, unsigned NumVTs, 1622 const SDOperand *Ops, unsigned NumOps) { 1623 if (NumVTs == 1) 1624 return getNode(Opcode, VTs[0], Ops, NumOps); 1625 return getNode(Opcode, makeVTList(VTs, NumVTs), Ops, NumOps); 1626} 1627 1628SDOperand SelectionDAG::getNode(unsigned Opcode, SDVTList VTList, 1629 const SDOperand *Ops, unsigned NumOps) { 1630 if (VTList.NumVTs == 1) 1631 return getNode(Opcode, VTList.VTs[0], Ops, NumOps); 1632 1633 switch (Opcode) { 1634 // FIXME: figure out how to safely handle things like 1635 // int foo(int x) { return 1 << (x & 255); } 1636 // int bar() { return foo(256); } 1637#if 0 1638 case ISD::SRA_PARTS: 1639 case ISD::SRL_PARTS: 1640 case ISD::SHL_PARTS: 1641 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG && 1642 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1) 1643 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 1644 else if (N3.getOpcode() == ISD::AND) 1645 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) { 1646 // If the and is only masking out bits that cannot effect the shift, 1647 // eliminate the and. 1648 unsigned NumBits = MVT::getSizeInBits(VT)*2; 1649 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 1650 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 1651 } 1652 break; 1653#endif 1654 } 1655 1656 // Memoize the node unless it returns a flag. 1657 SDNode *N; 1658 if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { 1659 SelectionDAGCSEMap::NodeID ID; 1660 ID.SetOpcode(Opcode); 1661 ID.SetValueTypes(VTList); 1662 ID.SetOperands(&Ops[0], NumOps); 1663 void *IP = 0; 1664 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1665 return SDOperand(E, 0); 1666 N = new SDNode(Opcode, Ops, NumOps); 1667 N->setValueTypes(VTList); 1668 CSEMap.InsertNode(N, IP); 1669 } else { 1670 N = new SDNode(Opcode, Ops, NumOps); 1671 N->setValueTypes(VTList); 1672 } 1673 AllNodes.push_back(N); 1674 return SDOperand(N, 0); 1675} 1676 1677SDVTList SelectionDAG::getVTList(MVT::ValueType VT) { 1678 return makeVTList(SDNode::getValueTypeList(VT), 1); 1679} 1680 1681SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2) { 1682 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 1683 E = VTList.end(); I != E; ++I) { 1684 if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2) 1685 return makeVTList(&(*I)[0], 2); 1686 } 1687 std::vector<MVT::ValueType> V; 1688 V.push_back(VT1); 1689 V.push_back(VT2); 1690 VTList.push_front(V); 1691 return makeVTList(&(*VTList.begin())[0], 2); 1692} 1693SDVTList SelectionDAG::getVTList(MVT::ValueType VT1, MVT::ValueType VT2, 1694 MVT::ValueType VT3) { 1695 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 1696 E = VTList.end(); I != E; ++I) { 1697 if (I->size() == 3 && (*I)[0] == VT1 && (*I)[1] == VT2 && 1698 (*I)[2] == VT3) 1699 return makeVTList(&(*I)[0], 3); 1700 } 1701 std::vector<MVT::ValueType> V; 1702 V.push_back(VT1); 1703 V.push_back(VT2); 1704 V.push_back(VT3); 1705 VTList.push_front(V); 1706 return makeVTList(&(*VTList.begin())[0], 3); 1707} 1708 1709SDVTList SelectionDAG::getVTList(const MVT::ValueType *VTs, unsigned NumVTs) { 1710 switch (NumVTs) { 1711 case 0: assert(0 && "Cannot have nodes without results!"); 1712 case 1: return makeVTList(SDNode::getValueTypeList(VTs[0]), 1); 1713 case 2: return getVTList(VTs[0], VTs[1]); 1714 case 3: return getVTList(VTs[0], VTs[1], VTs[2]); 1715 default: break; 1716 } 1717 1718 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 1719 E = VTList.end(); I != E; ++I) { 1720 if (I->size() != NumVTs || VTs[0] != (*I)[0] || VTs[1] != (*I)[1]) continue; 1721 1722 bool NoMatch = false; 1723 for (unsigned i = 2; i != NumVTs; ++i) 1724 if (VTs[i] != (*I)[i]) { 1725 NoMatch = true; 1726 break; 1727 } 1728 if (!NoMatch) 1729 return makeVTList(&*I->begin(), NumVTs); 1730 } 1731 1732 VTList.push_front(std::vector<MVT::ValueType>(VTs, VTs+NumVTs)); 1733 return makeVTList(&*VTList.begin()->begin(), NumVTs); 1734} 1735 1736 1737/// UpdateNodeOperands - *Mutate* the specified node in-place to have the 1738/// specified operands. If the resultant node already exists in the DAG, 1739/// this does not modify the specified node, instead it returns the node that 1740/// already exists. If the resultant node does not exist in the DAG, the 1741/// input node is returned. As a degenerate case, if you specify the same 1742/// input operands as the node already has, the input node is returned. 1743SDOperand SelectionDAG:: 1744UpdateNodeOperands(SDOperand InN, SDOperand Op) { 1745 SDNode *N = InN.Val; 1746 assert(N->getNumOperands() == 1 && "Update with wrong number of operands"); 1747 1748 // Check to see if there is no change. 1749 if (Op == N->getOperand(0)) return InN; 1750 1751 // See if the modified node already exists. 1752 void *InsertPos = 0; 1753 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos)) 1754 return SDOperand(Existing, InN.ResNo); 1755 1756 // Nope it doesn't. Remove the node from it's current place in the maps. 1757 if (InsertPos) 1758 RemoveNodeFromCSEMaps(N); 1759 1760 // Now we update the operands. 1761 N->OperandList[0].Val->removeUser(N); 1762 Op.Val->addUser(N); 1763 N->OperandList[0] = Op; 1764 1765 // If this gets put into a CSE map, add it. 1766 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 1767 return InN; 1768} 1769 1770SDOperand SelectionDAG:: 1771UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { 1772 SDNode *N = InN.Val; 1773 assert(N->getNumOperands() == 2 && "Update with wrong number of operands"); 1774 1775 // Check to see if there is no change. 1776 bool AnyChange = false; 1777 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1)) 1778 return InN; // No operands changed, just return the input node. 1779 1780 // See if the modified node already exists. 1781 void *InsertPos = 0; 1782 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos)) 1783 return SDOperand(Existing, InN.ResNo); 1784 1785 // Nope it doesn't. Remove the node from it's current place in the maps. 1786 if (InsertPos) 1787 RemoveNodeFromCSEMaps(N); 1788 1789 // Now we update the operands. 1790 if (N->OperandList[0] != Op1) { 1791 N->OperandList[0].Val->removeUser(N); 1792 Op1.Val->addUser(N); 1793 N->OperandList[0] = Op1; 1794 } 1795 if (N->OperandList[1] != Op2) { 1796 N->OperandList[1].Val->removeUser(N); 1797 Op2.Val->addUser(N); 1798 N->OperandList[1] = Op2; 1799 } 1800 1801 // If this gets put into a CSE map, add it. 1802 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 1803 return InN; 1804} 1805 1806SDOperand SelectionDAG:: 1807UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) { 1808 SDOperand Ops[] = { Op1, Op2, Op3 }; 1809 return UpdateNodeOperands(N, Ops, 3); 1810} 1811 1812SDOperand SelectionDAG:: 1813UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 1814 SDOperand Op3, SDOperand Op4) { 1815 SDOperand Ops[] = { Op1, Op2, Op3, Op4 }; 1816 return UpdateNodeOperands(N, Ops, 4); 1817} 1818 1819SDOperand SelectionDAG:: 1820UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 1821 SDOperand Op3, SDOperand Op4, SDOperand Op5) { 1822 SDOperand Ops[] = { Op1, Op2, Op3, Op4, Op5 }; 1823 return UpdateNodeOperands(N, Ops, 5); 1824} 1825 1826 1827SDOperand SelectionDAG:: 1828UpdateNodeOperands(SDOperand InN, SDOperand *Ops, unsigned NumOps) { 1829 SDNode *N = InN.Val; 1830 assert(N->getNumOperands() == NumOps && 1831 "Update with wrong number of operands"); 1832 1833 // Check to see if there is no change. 1834 bool AnyChange = false; 1835 for (unsigned i = 0; i != NumOps; ++i) { 1836 if (Ops[i] != N->getOperand(i)) { 1837 AnyChange = true; 1838 break; 1839 } 1840 } 1841 1842 // No operands changed, just return the input node. 1843 if (!AnyChange) return InN; 1844 1845 // See if the modified node already exists. 1846 void *InsertPos = 0; 1847 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos)) 1848 return SDOperand(Existing, InN.ResNo); 1849 1850 // Nope it doesn't. Remove the node from it's current place in the maps. 1851 if (InsertPos) 1852 RemoveNodeFromCSEMaps(N); 1853 1854 // Now we update the operands. 1855 for (unsigned i = 0; i != NumOps; ++i) { 1856 if (N->OperandList[i] != Ops[i]) { 1857 N->OperandList[i].Val->removeUser(N); 1858 Ops[i].Val->addUser(N); 1859 N->OperandList[i] = Ops[i]; 1860 } 1861 } 1862 1863 // If this gets put into a CSE map, add it. 1864 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 1865 return InN; 1866} 1867 1868 1869 1870 1871/// SelectNodeTo - These are used for target selectors to *mutate* the 1872/// specified node to have the specified return type, Target opcode, and 1873/// operands. Note that target opcodes are stored as 1874/// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. 1875/// 1876/// Note that SelectNodeTo returns the resultant node. If there is already a 1877/// node of the specified opcode and operands, it returns that node instead of 1878/// the current one. 1879SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1880 MVT::ValueType VT) { 1881 SDVTList VTs = getVTList(VT); 1882 SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs); 1883 void *IP = 0; 1884 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 1885 return ON; 1886 1887 RemoveNodeFromCSEMaps(N); 1888 1889 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1890 N->setValueTypes(VTs); 1891 1892 CSEMap.InsertNode(N, IP); 1893 return N; 1894} 1895 1896SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1897 MVT::ValueType VT, SDOperand Op1) { 1898 // If an identical node already exists, use it. 1899 SDVTList VTs = getVTList(VT); 1900 SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1); 1901 void *IP = 0; 1902 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 1903 return ON; 1904 1905 RemoveNodeFromCSEMaps(N); 1906 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1907 N->setValueTypes(VTs); 1908 N->setOperands(Op1); 1909 CSEMap.InsertNode(N, IP); 1910 return N; 1911} 1912 1913SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1914 MVT::ValueType VT, SDOperand Op1, 1915 SDOperand Op2) { 1916 // If an identical node already exists, use it. 1917 SDVTList VTs = getVTList(VT); 1918 SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2); 1919 void *IP = 0; 1920 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 1921 return ON; 1922 1923 RemoveNodeFromCSEMaps(N); 1924 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1925 N->setValueTypes(VTs); 1926 N->setOperands(Op1, Op2); 1927 1928 CSEMap.InsertNode(N, IP); // Memoize the new node. 1929 return N; 1930} 1931 1932SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1933 MVT::ValueType VT, SDOperand Op1, 1934 SDOperand Op2, SDOperand Op3) { 1935 // If an identical node already exists, use it. 1936 SDVTList VTs = getVTList(VT); 1937 SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, 1938 Op1, Op2, Op3); 1939 void *IP = 0; 1940 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 1941 return ON; 1942 1943 RemoveNodeFromCSEMaps(N); 1944 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1945 N->setValueTypes(VTs); 1946 N->setOperands(Op1, Op2, Op3); 1947 1948 CSEMap.InsertNode(N, IP); // Memoize the new node. 1949 return N; 1950} 1951 1952SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1953 MVT::ValueType VT, const SDOperand *Ops, 1954 unsigned NumOps) { 1955 // If an identical node already exists, use it. 1956 SDVTList VTs = getVTList(VT); 1957 SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs); 1958 for (unsigned i = 0; i != NumOps; ++i) 1959 ID.AddOperand(Ops[i]); 1960 void *IP = 0; 1961 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 1962 return ON; 1963 1964 RemoveNodeFromCSEMaps(N); 1965 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1966 N->setValueTypes(VTs); 1967 N->setOperands(Ops, NumOps); 1968 1969 CSEMap.InsertNode(N, IP); // Memoize the new node. 1970 return N; 1971} 1972 1973SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1974 MVT::ValueType VT1, MVT::ValueType VT2, 1975 SDOperand Op1, SDOperand Op2) { 1976 SDVTList VTs = getVTList(VT1, VT2); 1977 SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, Op1, Op2); 1978 void *IP = 0; 1979 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 1980 return ON; 1981 1982 RemoveNodeFromCSEMaps(N); 1983 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 1984 N->setValueTypes(VTs); 1985 N->setOperands(Op1, Op2); 1986 1987 CSEMap.InsertNode(N, IP); // Memoize the new node. 1988 return N; 1989} 1990 1991SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 1992 MVT::ValueType VT1, MVT::ValueType VT2, 1993 SDOperand Op1, SDOperand Op2, 1994 SDOperand Op3) { 1995 // If an identical node already exists, use it. 1996 SDVTList VTs = getVTList(VT1, VT2); 1997 SelectionDAGCSEMap::NodeID ID(ISD::BUILTIN_OP_END+TargetOpc, VTs, 1998 Op1, Op2, Op3); 1999 void *IP = 0; 2000 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 2001 return ON; 2002 2003 RemoveNodeFromCSEMaps(N); 2004 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 2005 N->setValueTypes(VTs); 2006 N->setOperands(Op1, Op2, Op3); 2007 2008 CSEMap.InsertNode(N, IP); // Memoize the new node. 2009 return N; 2010} 2011 2012 2013/// getTargetNode - These are used for target selectors to create a new node 2014/// with specified return type(s), target opcode, and operands. 2015/// 2016/// Note that getTargetNode returns the resultant node. If there is already a 2017/// node of the specified opcode and operands, it returns that node instead of 2018/// the current one. 2019SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) { 2020 return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val; 2021} 2022SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2023 SDOperand Op1) { 2024 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val; 2025} 2026SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2027 SDOperand Op1, SDOperand Op2) { 2028 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val; 2029} 2030SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2031 SDOperand Op1, SDOperand Op2, SDOperand Op3) { 2032 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val; 2033} 2034SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 2035 const SDOperand *Ops, unsigned NumOps) { 2036 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops, NumOps).Val; 2037} 2038SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2039 MVT::ValueType VT2, SDOperand Op1) { 2040 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); 2041 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, &Op1, 1).Val; 2042} 2043SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2044 MVT::ValueType VT2, SDOperand Op1, 2045 SDOperand Op2) { 2046 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); 2047 SDOperand Ops[] = { Op1, Op2 }; 2048 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 2).Val; 2049} 2050SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2051 MVT::ValueType VT2, SDOperand Op1, 2052 SDOperand Op2, SDOperand Op3) { 2053 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); 2054 SDOperand Ops[] = { Op1, Op2, Op3 }; 2055 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, 3).Val; 2056} 2057SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2058 MVT::ValueType VT2, 2059 const SDOperand *Ops, unsigned NumOps) { 2060 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2); 2061 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 2, Ops, NumOps).Val; 2062} 2063SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2064 MVT::ValueType VT2, MVT::ValueType VT3, 2065 SDOperand Op1, SDOperand Op2) { 2066 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3); 2067 SDOperand Ops[] = { Op1, Op2 }; 2068 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, 2).Val; 2069} 2070SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 2071 MVT::ValueType VT2, MVT::ValueType VT3, 2072 const SDOperand *Ops, unsigned NumOps) { 2073 const MVT::ValueType *VTs = getNodeValueTypes(VT1, VT2, VT3); 2074 return getNode(ISD::BUILTIN_OP_END+Opcode, VTs, 3, Ops, NumOps).Val; 2075} 2076 2077/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 2078/// This can cause recursive merging of nodes in the DAG. 2079/// 2080/// This version assumes From/To have a single result value. 2081/// 2082void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN, 2083 std::vector<SDNode*> *Deleted) { 2084 SDNode *From = FromN.Val, *To = ToN.Val; 2085 assert(From->getNumValues() == 1 && To->getNumValues() == 1 && 2086 "Cannot replace with this method!"); 2087 assert(From != To && "Cannot replace uses of with self"); 2088 2089 while (!From->use_empty()) { 2090 // Process users until they are all gone. 2091 SDNode *U = *From->use_begin(); 2092 2093 // This node is about to morph, remove its old self from the CSE maps. 2094 RemoveNodeFromCSEMaps(U); 2095 2096 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 2097 I != E; ++I) 2098 if (I->Val == From) { 2099 From->removeUser(U); 2100 I->Val = To; 2101 To->addUser(U); 2102 } 2103 2104 // Now that we have modified U, add it back to the CSE maps. If it already 2105 // exists there, recursively merge the results together. 2106 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 2107 ReplaceAllUsesWith(U, Existing, Deleted); 2108 // U is now dead. 2109 if (Deleted) Deleted->push_back(U); 2110 DeleteNodeNotInCSEMaps(U); 2111 } 2112 } 2113} 2114 2115/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 2116/// This can cause recursive merging of nodes in the DAG. 2117/// 2118/// This version assumes From/To have matching types and numbers of result 2119/// values. 2120/// 2121void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, 2122 std::vector<SDNode*> *Deleted) { 2123 assert(From != To && "Cannot replace uses of with self"); 2124 assert(From->getNumValues() == To->getNumValues() && 2125 "Cannot use this version of ReplaceAllUsesWith!"); 2126 if (From->getNumValues() == 1) { // If possible, use the faster version. 2127 ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted); 2128 return; 2129 } 2130 2131 while (!From->use_empty()) { 2132 // Process users until they are all gone. 2133 SDNode *U = *From->use_begin(); 2134 2135 // This node is about to morph, remove its old self from the CSE maps. 2136 RemoveNodeFromCSEMaps(U); 2137 2138 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 2139 I != E; ++I) 2140 if (I->Val == From) { 2141 From->removeUser(U); 2142 I->Val = To; 2143 To->addUser(U); 2144 } 2145 2146 // Now that we have modified U, add it back to the CSE maps. If it already 2147 // exists there, recursively merge the results together. 2148 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 2149 ReplaceAllUsesWith(U, Existing, Deleted); 2150 // U is now dead. 2151 if (Deleted) Deleted->push_back(U); 2152 DeleteNodeNotInCSEMaps(U); 2153 } 2154 } 2155} 2156 2157/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 2158/// This can cause recursive merging of nodes in the DAG. 2159/// 2160/// This version can replace From with any result values. To must match the 2161/// number and types of values returned by From. 2162void SelectionDAG::ReplaceAllUsesWith(SDNode *From, 2163 const SDOperand *To, 2164 std::vector<SDNode*> *Deleted) { 2165 if (From->getNumValues() == 1 && To[0].Val->getNumValues() == 1) { 2166 // Degenerate case handled above. 2167 ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted); 2168 return; 2169 } 2170 2171 while (!From->use_empty()) { 2172 // Process users until they are all gone. 2173 SDNode *U = *From->use_begin(); 2174 2175 // This node is about to morph, remove its old self from the CSE maps. 2176 RemoveNodeFromCSEMaps(U); 2177 2178 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 2179 I != E; ++I) 2180 if (I->Val == From) { 2181 const SDOperand &ToOp = To[I->ResNo]; 2182 From->removeUser(U); 2183 *I = ToOp; 2184 ToOp.Val->addUser(U); 2185 } 2186 2187 // Now that we have modified U, add it back to the CSE maps. If it already 2188 // exists there, recursively merge the results together. 2189 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 2190 ReplaceAllUsesWith(U, Existing, Deleted); 2191 // U is now dead. 2192 if (Deleted) Deleted->push_back(U); 2193 DeleteNodeNotInCSEMaps(U); 2194 } 2195 } 2196} 2197 2198/// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 2199/// uses of other values produced by From.Val alone. The Deleted vector is 2200/// handled the same was as for ReplaceAllUsesWith. 2201void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 2202 std::vector<SDNode*> &Deleted) { 2203 assert(From != To && "Cannot replace a value with itself"); 2204 // Handle the simple, trivial, case efficiently. 2205 if (From.Val->getNumValues() == 1 && To.Val->getNumValues() == 1) { 2206 ReplaceAllUsesWith(From, To, &Deleted); 2207 return; 2208 } 2209 2210 // Get all of the users in a nice, deterministically ordered, uniqued set. 2211 SetVector<SDNode*> Users(From.Val->use_begin(), From.Val->use_end()); 2212 2213 while (!Users.empty()) { 2214 // We know that this user uses some value of From. If it is the right 2215 // value, update it. 2216 SDNode *User = Users.back(); 2217 Users.pop_back(); 2218 2219 for (SDOperand *Op = User->OperandList, 2220 *E = User->OperandList+User->NumOperands; Op != E; ++Op) { 2221 if (*Op == From) { 2222 // Okay, we know this user needs to be updated. Remove its old self 2223 // from the CSE maps. 2224 RemoveNodeFromCSEMaps(User); 2225 2226 // Update all operands that match "From". 2227 for (; Op != E; ++Op) { 2228 if (*Op == From) { 2229 From.Val->removeUser(User); 2230 *Op = To; 2231 To.Val->addUser(User); 2232 } 2233 } 2234 2235 // Now that we have modified User, add it back to the CSE maps. If it 2236 // already exists there, recursively merge the results together. 2237 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(User)) { 2238 unsigned NumDeleted = Deleted.size(); 2239 ReplaceAllUsesWith(User, Existing, &Deleted); 2240 2241 // User is now dead. 2242 Deleted.push_back(User); 2243 DeleteNodeNotInCSEMaps(User); 2244 2245 // We have to be careful here, because ReplaceAllUsesWith could have 2246 // deleted a user of From, which means there may be dangling pointers 2247 // in the "Users" setvector. Scan over the deleted node pointers and 2248 // remove them from the setvector. 2249 for (unsigned i = NumDeleted, e = Deleted.size(); i != e; ++i) 2250 Users.remove(Deleted[i]); 2251 } 2252 break; // Exit the operand scanning loop. 2253 } 2254 } 2255 } 2256} 2257 2258 2259/// AssignNodeIds - Assign a unique node id for each node in the DAG based on 2260/// their allnodes order. It returns the maximum id. 2261unsigned SelectionDAG::AssignNodeIds() { 2262 unsigned Id = 0; 2263 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I){ 2264 SDNode *N = I; 2265 N->setNodeId(Id++); 2266 } 2267 return Id; 2268} 2269 2270/// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 2271/// based on their topological order. It returns the maximum id and a vector 2272/// of the SDNodes* in assigned order by reference. 2273unsigned SelectionDAG::AssignTopologicalOrder(std::vector<SDNode*> &TopOrder) { 2274 unsigned DAGSize = AllNodes.size(); 2275 std::vector<unsigned> InDegree(DAGSize); 2276 std::vector<SDNode*> Sources; 2277 2278 // Use a two pass approach to avoid using a std::map which is slow. 2279 unsigned Id = 0; 2280 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I){ 2281 SDNode *N = I; 2282 N->setNodeId(Id++); 2283 unsigned Degree = N->use_size(); 2284 InDegree[N->getNodeId()] = Degree; 2285 if (Degree == 0) 2286 Sources.push_back(N); 2287 } 2288 2289 TopOrder.clear(); 2290 while (!Sources.empty()) { 2291 SDNode *N = Sources.back(); 2292 Sources.pop_back(); 2293 TopOrder.push_back(N); 2294 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 2295 SDNode *P = I->Val; 2296 unsigned Degree = --InDegree[P->getNodeId()]; 2297 if (Degree == 0) 2298 Sources.push_back(P); 2299 } 2300 } 2301 2302 // Second pass, assign the actual topological order as node ids. 2303 Id = 0; 2304 for (std::vector<SDNode*>::iterator TI = TopOrder.begin(),TE = TopOrder.end(); 2305 TI != TE; ++TI) 2306 (*TI)->setNodeId(Id++); 2307 2308 return Id; 2309} 2310 2311 2312 2313//===----------------------------------------------------------------------===// 2314// SDNode Class 2315//===----------------------------------------------------------------------===// 2316 2317// Out-of-line virtual method to give class a home. 2318void SDNode::ANCHOR() { 2319} 2320 2321/// getValueTypeList - Return a pointer to the specified value type. 2322/// 2323MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) { 2324 static MVT::ValueType VTs[MVT::LAST_VALUETYPE]; 2325 VTs[VT] = VT; 2326 return &VTs[VT]; 2327} 2328 2329/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 2330/// indicated value. This method ignores uses of other values defined by this 2331/// operation. 2332bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { 2333 assert(Value < getNumValues() && "Bad value!"); 2334 2335 // If there is only one value, this is easy. 2336 if (getNumValues() == 1) 2337 return use_size() == NUses; 2338 if (Uses.size() < NUses) return false; 2339 2340 SDOperand TheValue(const_cast<SDNode *>(this), Value); 2341 2342 std::set<SDNode*> UsersHandled; 2343 2344 for (SDNode::use_iterator UI = Uses.begin(), E = Uses.end(); UI != E; ++UI) { 2345 SDNode *User = *UI; 2346 if (User->getNumOperands() == 1 || 2347 UsersHandled.insert(User).second) // First time we've seen this? 2348 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 2349 if (User->getOperand(i) == TheValue) { 2350 if (NUses == 0) 2351 return false; // too many uses 2352 --NUses; 2353 } 2354 } 2355 2356 // Found exactly the right number of uses? 2357 return NUses == 0; 2358} 2359 2360 2361// isOnlyUse - Return true if this node is the only use of N. 2362bool SDNode::isOnlyUse(SDNode *N) const { 2363 bool Seen = false; 2364 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 2365 SDNode *User = *I; 2366 if (User == this) 2367 Seen = true; 2368 else 2369 return false; 2370 } 2371 2372 return Seen; 2373} 2374 2375// isOperand - Return true if this node is an operand of N. 2376bool SDOperand::isOperand(SDNode *N) const { 2377 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 2378 if (*this == N->getOperand(i)) 2379 return true; 2380 return false; 2381} 2382 2383bool SDNode::isOperand(SDNode *N) const { 2384 for (unsigned i = 0, e = N->NumOperands; i != e; ++i) 2385 if (this == N->OperandList[i].Val) 2386 return true; 2387 return false; 2388} 2389 2390uint64_t SDNode::getConstantOperandVal(unsigned Num) const { 2391 assert(Num < NumOperands && "Invalid child # of SDNode!"); 2392 return cast<ConstantSDNode>(OperandList[Num])->getValue(); 2393} 2394 2395const char *SDNode::getOperationName(const SelectionDAG *G) const { 2396 switch (getOpcode()) { 2397 default: 2398 if (getOpcode() < ISD::BUILTIN_OP_END) 2399 return "<<Unknown DAG Node>>"; 2400 else { 2401 if (G) { 2402 if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo()) 2403 if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes()) 2404 return TII->getName(getOpcode()-ISD::BUILTIN_OP_END); 2405 2406 TargetLowering &TLI = G->getTargetLoweringInfo(); 2407 const char *Name = 2408 TLI.getTargetNodeName(getOpcode()); 2409 if (Name) return Name; 2410 } 2411 2412 return "<<Unknown Target Node>>"; 2413 } 2414 2415 case ISD::PCMARKER: return "PCMarker"; 2416 case ISD::READCYCLECOUNTER: return "ReadCycleCounter"; 2417 case ISD::SRCVALUE: return "SrcValue"; 2418 case ISD::EntryToken: return "EntryToken"; 2419 case ISD::TokenFactor: return "TokenFactor"; 2420 case ISD::AssertSext: return "AssertSext"; 2421 case ISD::AssertZext: return "AssertZext"; 2422 2423 case ISD::STRING: return "String"; 2424 case ISD::BasicBlock: return "BasicBlock"; 2425 case ISD::VALUETYPE: return "ValueType"; 2426 case ISD::Register: return "Register"; 2427 2428 case ISD::Constant: return "Constant"; 2429 case ISD::ConstantFP: return "ConstantFP"; 2430 case ISD::GlobalAddress: return "GlobalAddress"; 2431 case ISD::FrameIndex: return "FrameIndex"; 2432 case ISD::JumpTable: return "JumpTable"; 2433 case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE"; 2434 case ISD::ConstantPool: return "ConstantPool"; 2435 case ISD::ExternalSymbol: return "ExternalSymbol"; 2436 case ISD::INTRINSIC_WO_CHAIN: { 2437 unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue(); 2438 return Intrinsic::getName((Intrinsic::ID)IID); 2439 } 2440 case ISD::INTRINSIC_VOID: 2441 case ISD::INTRINSIC_W_CHAIN: { 2442 unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue(); 2443 return Intrinsic::getName((Intrinsic::ID)IID); 2444 } 2445 2446 case ISD::BUILD_VECTOR: return "BUILD_VECTOR"; 2447 case ISD::TargetConstant: return "TargetConstant"; 2448 case ISD::TargetConstantFP:return "TargetConstantFP"; 2449 case ISD::TargetGlobalAddress: return "TargetGlobalAddress"; 2450 case ISD::TargetFrameIndex: return "TargetFrameIndex"; 2451 case ISD::TargetJumpTable: return "TargetJumpTable"; 2452 case ISD::TargetConstantPool: return "TargetConstantPool"; 2453 case ISD::TargetExternalSymbol: return "TargetExternalSymbol"; 2454 2455 case ISD::CopyToReg: return "CopyToReg"; 2456 case ISD::CopyFromReg: return "CopyFromReg"; 2457 case ISD::UNDEF: return "undef"; 2458 case ISD::MERGE_VALUES: return "mergevalues"; 2459 case ISD::INLINEASM: return "inlineasm"; 2460 case ISD::HANDLENODE: return "handlenode"; 2461 case ISD::FORMAL_ARGUMENTS: return "formal_arguments"; 2462 case ISD::CALL: return "call"; 2463 2464 // Unary operators 2465 case ISD::FABS: return "fabs"; 2466 case ISD::FNEG: return "fneg"; 2467 case ISD::FSQRT: return "fsqrt"; 2468 case ISD::FSIN: return "fsin"; 2469 case ISD::FCOS: return "fcos"; 2470 case ISD::FPOWI: return "fpowi"; 2471 2472 // Binary operators 2473 case ISD::ADD: return "add"; 2474 case ISD::SUB: return "sub"; 2475 case ISD::MUL: return "mul"; 2476 case ISD::MULHU: return "mulhu"; 2477 case ISD::MULHS: return "mulhs"; 2478 case ISD::SDIV: return "sdiv"; 2479 case ISD::UDIV: return "udiv"; 2480 case ISD::SREM: return "srem"; 2481 case ISD::UREM: return "urem"; 2482 case ISD::AND: return "and"; 2483 case ISD::OR: return "or"; 2484 case ISD::XOR: return "xor"; 2485 case ISD::SHL: return "shl"; 2486 case ISD::SRA: return "sra"; 2487 case ISD::SRL: return "srl"; 2488 case ISD::ROTL: return "rotl"; 2489 case ISD::ROTR: return "rotr"; 2490 case ISD::FADD: return "fadd"; 2491 case ISD::FSUB: return "fsub"; 2492 case ISD::FMUL: return "fmul"; 2493 case ISD::FDIV: return "fdiv"; 2494 case ISD::FREM: return "frem"; 2495 case ISD::FCOPYSIGN: return "fcopysign"; 2496 case ISD::VADD: return "vadd"; 2497 case ISD::VSUB: return "vsub"; 2498 case ISD::VMUL: return "vmul"; 2499 case ISD::VSDIV: return "vsdiv"; 2500 case ISD::VUDIV: return "vudiv"; 2501 case ISD::VAND: return "vand"; 2502 case ISD::VOR: return "vor"; 2503 case ISD::VXOR: return "vxor"; 2504 2505 case ISD::SETCC: return "setcc"; 2506 case ISD::SELECT: return "select"; 2507 case ISD::SELECT_CC: return "select_cc"; 2508 case ISD::VSELECT: return "vselect"; 2509 case ISD::INSERT_VECTOR_ELT: return "insert_vector_elt"; 2510 case ISD::VINSERT_VECTOR_ELT: return "vinsert_vector_elt"; 2511 case ISD::EXTRACT_VECTOR_ELT: return "extract_vector_elt"; 2512 case ISD::VEXTRACT_VECTOR_ELT: return "vextract_vector_elt"; 2513 case ISD::SCALAR_TO_VECTOR: return "scalar_to_vector"; 2514 case ISD::VBUILD_VECTOR: return "vbuild_vector"; 2515 case ISD::VECTOR_SHUFFLE: return "vector_shuffle"; 2516 case ISD::VVECTOR_SHUFFLE: return "vvector_shuffle"; 2517 case ISD::VBIT_CONVERT: return "vbit_convert"; 2518 case ISD::ADDC: return "addc"; 2519 case ISD::ADDE: return "adde"; 2520 case ISD::SUBC: return "subc"; 2521 case ISD::SUBE: return "sube"; 2522 case ISD::SHL_PARTS: return "shl_parts"; 2523 case ISD::SRA_PARTS: return "sra_parts"; 2524 case ISD::SRL_PARTS: return "srl_parts"; 2525 2526 // Conversion operators. 2527 case ISD::SIGN_EXTEND: return "sign_extend"; 2528 case ISD::ZERO_EXTEND: return "zero_extend"; 2529 case ISD::ANY_EXTEND: return "any_extend"; 2530 case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg"; 2531 case ISD::TRUNCATE: return "truncate"; 2532 case ISD::FP_ROUND: return "fp_round"; 2533 case ISD::FP_ROUND_INREG: return "fp_round_inreg"; 2534 case ISD::FP_EXTEND: return "fp_extend"; 2535 2536 case ISD::SINT_TO_FP: return "sint_to_fp"; 2537 case ISD::UINT_TO_FP: return "uint_to_fp"; 2538 case ISD::FP_TO_SINT: return "fp_to_sint"; 2539 case ISD::FP_TO_UINT: return "fp_to_uint"; 2540 case ISD::BIT_CONVERT: return "bit_convert"; 2541 2542 // Control flow instructions 2543 case ISD::BR: return "br"; 2544 case ISD::BRIND: return "brind"; 2545 case ISD::BRCOND: return "brcond"; 2546 case ISD::BR_CC: return "br_cc"; 2547 case ISD::RET: return "ret"; 2548 case ISD::CALLSEQ_START: return "callseq_start"; 2549 case ISD::CALLSEQ_END: return "callseq_end"; 2550 2551 // Other operators 2552 case ISD::LOAD: return "load"; 2553 case ISD::STORE: return "store"; 2554 case ISD::VLOAD: return "vload"; 2555 case ISD::VAARG: return "vaarg"; 2556 case ISD::VACOPY: return "vacopy"; 2557 case ISD::VAEND: return "vaend"; 2558 case ISD::VASTART: return "vastart"; 2559 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc"; 2560 case ISD::EXTRACT_ELEMENT: return "extract_element"; 2561 case ISD::BUILD_PAIR: return "build_pair"; 2562 case ISD::STACKSAVE: return "stacksave"; 2563 case ISD::STACKRESTORE: return "stackrestore"; 2564 2565 // Block memory operations. 2566 case ISD::MEMSET: return "memset"; 2567 case ISD::MEMCPY: return "memcpy"; 2568 case ISD::MEMMOVE: return "memmove"; 2569 2570 // Bit manipulation 2571 case ISD::BSWAP: return "bswap"; 2572 case ISD::CTPOP: return "ctpop"; 2573 case ISD::CTTZ: return "cttz"; 2574 case ISD::CTLZ: return "ctlz"; 2575 2576 // Debug info 2577 case ISD::LOCATION: return "location"; 2578 case ISD::DEBUG_LOC: return "debug_loc"; 2579 case ISD::DEBUG_LABEL: return "debug_label"; 2580 2581 case ISD::CONDCODE: 2582 switch (cast<CondCodeSDNode>(this)->get()) { 2583 default: assert(0 && "Unknown setcc condition!"); 2584 case ISD::SETOEQ: return "setoeq"; 2585 case ISD::SETOGT: return "setogt"; 2586 case ISD::SETOGE: return "setoge"; 2587 case ISD::SETOLT: return "setolt"; 2588 case ISD::SETOLE: return "setole"; 2589 case ISD::SETONE: return "setone"; 2590 2591 case ISD::SETO: return "seto"; 2592 case ISD::SETUO: return "setuo"; 2593 case ISD::SETUEQ: return "setue"; 2594 case ISD::SETUGT: return "setugt"; 2595 case ISD::SETUGE: return "setuge"; 2596 case ISD::SETULT: return "setult"; 2597 case ISD::SETULE: return "setule"; 2598 case ISD::SETUNE: return "setune"; 2599 2600 case ISD::SETEQ: return "seteq"; 2601 case ISD::SETGT: return "setgt"; 2602 case ISD::SETGE: return "setge"; 2603 case ISD::SETLT: return "setlt"; 2604 case ISD::SETLE: return "setle"; 2605 case ISD::SETNE: return "setne"; 2606 } 2607 } 2608} 2609 2610const char *SDNode::getAddressingModeName(ISD::MemOpAddrMode AM) { 2611 switch (AM) { 2612 default: 2613 return ""; 2614 case ISD::PRE_INC: 2615 return "<pre-inc>"; 2616 case ISD::PRE_DEC: 2617 return "<pre-dec>"; 2618 case ISD::POST_INC: 2619 return "<post-inc>"; 2620 case ISD::POST_DEC: 2621 return "<post-dec>"; 2622 } 2623} 2624 2625void SDNode::dump() const { dump(0); } 2626void SDNode::dump(const SelectionDAG *G) const { 2627 std::cerr << (void*)this << ": "; 2628 2629 for (unsigned i = 0, e = getNumValues(); i != e; ++i) { 2630 if (i) std::cerr << ","; 2631 if (getValueType(i) == MVT::Other) 2632 std::cerr << "ch"; 2633 else 2634 std::cerr << MVT::getValueTypeString(getValueType(i)); 2635 } 2636 std::cerr << " = " << getOperationName(G); 2637 2638 std::cerr << " "; 2639 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 2640 if (i) std::cerr << ", "; 2641 std::cerr << (void*)getOperand(i).Val; 2642 if (unsigned RN = getOperand(i).ResNo) 2643 std::cerr << ":" << RN; 2644 } 2645 2646 if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { 2647 std::cerr << "<" << CSDN->getValue() << ">"; 2648 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { 2649 std::cerr << "<" << CSDN->getValue() << ">"; 2650 } else if (const GlobalAddressSDNode *GADN = 2651 dyn_cast<GlobalAddressSDNode>(this)) { 2652 int offset = GADN->getOffset(); 2653 std::cerr << "<"; 2654 WriteAsOperand(std::cerr, GADN->getGlobal()) << ">"; 2655 if (offset > 0) 2656 std::cerr << " + " << offset; 2657 else 2658 std::cerr << " " << offset; 2659 } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) { 2660 std::cerr << "<" << FIDN->getIndex() << ">"; 2661 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ 2662 int offset = CP->getOffset(); 2663 if (CP->isMachineConstantPoolEntry()) 2664 std::cerr << "<" << *CP->getMachineCPVal() << ">"; 2665 else 2666 std::cerr << "<" << *CP->getConstVal() << ">"; 2667 if (offset > 0) 2668 std::cerr << " + " << offset; 2669 else 2670 std::cerr << " " << offset; 2671 } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) { 2672 std::cerr << "<"; 2673 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); 2674 if (LBB) 2675 std::cerr << LBB->getName() << " "; 2676 std::cerr << (const void*)BBDN->getBasicBlock() << ">"; 2677 } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) { 2678 if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) { 2679 std::cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg()); 2680 } else { 2681 std::cerr << " #" << R->getReg(); 2682 } 2683 } else if (const ExternalSymbolSDNode *ES = 2684 dyn_cast<ExternalSymbolSDNode>(this)) { 2685 std::cerr << "'" << ES->getSymbol() << "'"; 2686 } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) { 2687 if (M->getValue()) 2688 std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">"; 2689 else 2690 std::cerr << "<null:" << M->getOffset() << ">"; 2691 } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) { 2692 std::cerr << ":" << getValueTypeString(N->getVT()); 2693 } else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) { 2694 bool doExt = true; 2695 switch (LD->getExtensionType()) { 2696 default: doExt = false; break; 2697 case ISD::EXTLOAD: 2698 std::cerr << " <anyext "; 2699 break; 2700 case ISD::SEXTLOAD: 2701 std::cerr << " <sext "; 2702 break; 2703 case ISD::ZEXTLOAD: 2704 std::cerr << " <zext "; 2705 break; 2706 } 2707 if (doExt) 2708 std::cerr << MVT::getValueTypeString(LD->getLoadedVT()) << ">"; 2709 2710 const char *AM = getAddressingModeName(LD->getAddressingMode()); 2711 if (AM != "") 2712 std::cerr << " " << AM; 2713 } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) { 2714 if (ST->isTruncatingStore()) 2715 std::cerr << " <trunc " 2716 << MVT::getValueTypeString(ST->getStoredVT()) << ">"; 2717 2718 const char *AM = getAddressingModeName(ST->getAddressingMode()); 2719 if (AM != "") 2720 std::cerr << " " << AM; 2721 } 2722} 2723 2724static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { 2725 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 2726 if (N->getOperand(i).Val->hasOneUse()) 2727 DumpNodes(N->getOperand(i).Val, indent+2, G); 2728 else 2729 std::cerr << "\n" << std::string(indent+2, ' ') 2730 << (void*)N->getOperand(i).Val << ": <multiple use>"; 2731 2732 2733 std::cerr << "\n" << std::string(indent, ' '); 2734 N->dump(G); 2735} 2736 2737void SelectionDAG::dump() const { 2738 std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; 2739 std::vector<const SDNode*> Nodes; 2740 for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); 2741 I != E; ++I) 2742 Nodes.push_back(I); 2743 2744 std::sort(Nodes.begin(), Nodes.end()); 2745 2746 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 2747 if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val) 2748 DumpNodes(Nodes[i], 2, this); 2749 } 2750 2751 if (getRoot().Val) DumpNodes(getRoot().Val, 2, this); 2752 2753 std::cerr << "\n\n"; 2754} 2755 2756const Type *ConstantPoolSDNode::getType() const { 2757 if (isMachineConstantPoolEntry()) 2758 return Val.MachineCPVal->getType(); 2759 return Val.ConstVal->getType(); 2760} 2761