SelectionDAG.cpp revision de2ace1758286f8442a13532d9cd7d3c4cce47ef
1//===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the SelectionDAG class. 11// 12//===----------------------------------------------------------------------===// 13#include "llvm/CodeGen/SelectionDAG.h" 14#include "llvm/Constants.h" 15#include "llvm/Analysis/ValueTracking.h" 16#include "llvm/Function.h" 17#include "llvm/GlobalAlias.h" 18#include "llvm/GlobalVariable.h" 19#include "llvm/Intrinsics.h" 20#include "llvm/DerivedTypes.h" 21#include "llvm/Assembly/Writer.h" 22#include "llvm/CallingConv.h" 23#include "llvm/CodeGen/MachineBasicBlock.h" 24#include "llvm/CodeGen/MachineConstantPool.h" 25#include "llvm/CodeGen/MachineFrameInfo.h" 26#include "llvm/CodeGen/MachineModuleInfo.h" 27#include "llvm/CodeGen/PseudoSourceValue.h" 28#include "llvm/Target/TargetRegisterInfo.h" 29#include "llvm/Target/TargetData.h" 30#include "llvm/Target/TargetFrameInfo.h" 31#include "llvm/Target/TargetLowering.h" 32#include "llvm/Target/TargetOptions.h" 33#include "llvm/Target/TargetInstrInfo.h" 34#include "llvm/Target/TargetIntrinsicInfo.h" 35#include "llvm/Target/TargetMachine.h" 36#include "llvm/Support/CommandLine.h" 37#include "llvm/Support/ErrorHandling.h" 38#include "llvm/Support/ManagedStatic.h" 39#include "llvm/Support/MathExtras.h" 40#include "llvm/Support/raw_ostream.h" 41#include "llvm/System/Mutex.h" 42#include "llvm/ADT/SetVector.h" 43#include "llvm/ADT/SmallPtrSet.h" 44#include "llvm/ADT/SmallSet.h" 45#include "llvm/ADT/SmallVector.h" 46#include "llvm/ADT/StringExtras.h" 47#include <algorithm> 48#include <cmath> 49using namespace llvm; 50 51/// makeVTList - Return an instance of the SDVTList struct initialized with the 52/// specified members. 53static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) { 54 SDVTList Res = {VTs, NumVTs}; 55 return Res; 56} 57 58static const fltSemantics *EVTToAPFloatSemantics(EVT VT) { 59 switch (VT.getSimpleVT().SimpleTy) { 60 default: llvm_unreachable("Unknown FP format"); 61 case MVT::f32: return &APFloat::IEEEsingle; 62 case MVT::f64: return &APFloat::IEEEdouble; 63 case MVT::f80: return &APFloat::x87DoubleExtended; 64 case MVT::f128: return &APFloat::IEEEquad; 65 case MVT::ppcf128: return &APFloat::PPCDoubleDouble; 66 } 67} 68 69SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {} 70 71//===----------------------------------------------------------------------===// 72// ConstantFPSDNode Class 73//===----------------------------------------------------------------------===// 74 75/// isExactlyValue - We don't rely on operator== working on double values, as 76/// it returns true for things that are clearly not equal, like -0.0 and 0.0. 77/// As such, this method can be used to do an exact bit-for-bit comparison of 78/// two floating point values. 79bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const { 80 return getValueAPF().bitwiseIsEqual(V); 81} 82 83bool ConstantFPSDNode::isValueValidForType(EVT VT, 84 const APFloat& Val) { 85 assert(VT.isFloatingPoint() && "Can only convert between FP types"); 86 87 // PPC long double cannot be converted to any other type. 88 if (VT == MVT::ppcf128 || 89 &Val.getSemantics() == &APFloat::PPCDoubleDouble) 90 return false; 91 92 // convert modifies in place, so make a copy. 93 APFloat Val2 = APFloat(Val); 94 bool losesInfo; 95 (void) Val2.convert(*EVTToAPFloatSemantics(VT), APFloat::rmNearestTiesToEven, 96 &losesInfo); 97 return !losesInfo; 98} 99 100//===----------------------------------------------------------------------===// 101// ISD Namespace 102//===----------------------------------------------------------------------===// 103 104/// isBuildVectorAllOnes - Return true if the specified node is a 105/// BUILD_VECTOR where all of the elements are ~0 or undef. 106bool ISD::isBuildVectorAllOnes(const SDNode *N) { 107 // Look through a bit convert. 108 if (N->getOpcode() == ISD::BIT_CONVERT) 109 N = N->getOperand(0).getNode(); 110 111 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 112 113 unsigned i = 0, e = N->getNumOperands(); 114 115 // Skip over all of the undef values. 116 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 117 ++i; 118 119 // Do not accept an all-undef vector. 120 if (i == e) return false; 121 122 // Do not accept build_vectors that aren't all constants or which have non-~0 123 // elements. 124 SDValue NotZero = N->getOperand(i); 125 if (isa<ConstantSDNode>(NotZero)) { 126 if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue()) 127 return false; 128 } else if (isa<ConstantFPSDNode>(NotZero)) { 129 if (!cast<ConstantFPSDNode>(NotZero)->getValueAPF(). 130 bitcastToAPInt().isAllOnesValue()) 131 return false; 132 } else 133 return false; 134 135 // Okay, we have at least one ~0 value, check to see if the rest match or are 136 // undefs. 137 for (++i; i != e; ++i) 138 if (N->getOperand(i) != NotZero && 139 N->getOperand(i).getOpcode() != ISD::UNDEF) 140 return false; 141 return true; 142} 143 144 145/// isBuildVectorAllZeros - Return true if the specified node is a 146/// BUILD_VECTOR where all of the elements are 0 or undef. 147bool ISD::isBuildVectorAllZeros(const SDNode *N) { 148 // Look through a bit convert. 149 if (N->getOpcode() == ISD::BIT_CONVERT) 150 N = N->getOperand(0).getNode(); 151 152 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 153 154 unsigned i = 0, e = N->getNumOperands(); 155 156 // Skip over all of the undef values. 157 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 158 ++i; 159 160 // Do not accept an all-undef vector. 161 if (i == e) return false; 162 163 // Do not accept build_vectors that aren't all constants or which have non-0 164 // elements. 165 SDValue Zero = N->getOperand(i); 166 if (isa<ConstantSDNode>(Zero)) { 167 if (!cast<ConstantSDNode>(Zero)->isNullValue()) 168 return false; 169 } else if (isa<ConstantFPSDNode>(Zero)) { 170 if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero()) 171 return false; 172 } else 173 return false; 174 175 // Okay, we have at least one 0 value, check to see if the rest match or are 176 // undefs. 177 for (++i; i != e; ++i) 178 if (N->getOperand(i) != Zero && 179 N->getOperand(i).getOpcode() != ISD::UNDEF) 180 return false; 181 return true; 182} 183 184/// isScalarToVector - Return true if the specified node is a 185/// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low 186/// element is not an undef. 187bool ISD::isScalarToVector(const SDNode *N) { 188 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR) 189 return true; 190 191 if (N->getOpcode() != ISD::BUILD_VECTOR) 192 return false; 193 if (N->getOperand(0).getOpcode() == ISD::UNDEF) 194 return false; 195 unsigned NumElems = N->getNumOperands(); 196 for (unsigned i = 1; i < NumElems; ++i) { 197 SDValue V = N->getOperand(i); 198 if (V.getOpcode() != ISD::UNDEF) 199 return false; 200 } 201 return true; 202} 203 204/// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 205/// when given the operation for (X op Y). 206ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 207 // To perform this operation, we just need to swap the L and G bits of the 208 // operation. 209 unsigned OldL = (Operation >> 2) & 1; 210 unsigned OldG = (Operation >> 1) & 1; 211 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 212 (OldL << 1) | // New G bit 213 (OldG << 2)); // New L bit. 214} 215 216/// getSetCCInverse - Return the operation corresponding to !(X op Y), where 217/// 'op' is a valid SetCC operation. 218ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 219 unsigned Operation = Op; 220 if (isInteger) 221 Operation ^= 7; // Flip L, G, E bits, but not U. 222 else 223 Operation ^= 15; // Flip all of the condition bits. 224 225 if (Operation > ISD::SETTRUE2) 226 Operation &= ~8; // Don't let N and U bits get set. 227 228 return ISD::CondCode(Operation); 229} 230 231 232/// isSignedOp - For an integer comparison, return 1 if the comparison is a 233/// signed operation and 2 if the result is an unsigned comparison. Return zero 234/// if the operation does not depend on the sign of the input (setne and seteq). 235static int isSignedOp(ISD::CondCode Opcode) { 236 switch (Opcode) { 237 default: llvm_unreachable("Illegal integer setcc operation!"); 238 case ISD::SETEQ: 239 case ISD::SETNE: return 0; 240 case ISD::SETLT: 241 case ISD::SETLE: 242 case ISD::SETGT: 243 case ISD::SETGE: return 1; 244 case ISD::SETULT: 245 case ISD::SETULE: 246 case ISD::SETUGT: 247 case ISD::SETUGE: return 2; 248 } 249} 250 251/// getSetCCOrOperation - Return the result of a logical OR between different 252/// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 253/// returns SETCC_INVALID if it is not possible to represent the resultant 254/// comparison. 255ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 256 bool isInteger) { 257 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 258 // Cannot fold a signed integer setcc with an unsigned integer setcc. 259 return ISD::SETCC_INVALID; 260 261 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 262 263 // If the N and U bits get set then the resultant comparison DOES suddenly 264 // care about orderedness, and is true when ordered. 265 if (Op > ISD::SETTRUE2) 266 Op &= ~16; // Clear the U bit if the N bit is set. 267 268 // Canonicalize illegal integer setcc's. 269 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT 270 Op = ISD::SETNE; 271 272 return ISD::CondCode(Op); 273} 274 275/// getSetCCAndOperation - Return the result of a logical AND between different 276/// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 277/// function returns zero if it is not possible to represent the resultant 278/// comparison. 279ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 280 bool isInteger) { 281 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 282 // Cannot fold a signed setcc with an unsigned setcc. 283 return ISD::SETCC_INVALID; 284 285 // Combine all of the condition bits. 286 ISD::CondCode Result = ISD::CondCode(Op1 & Op2); 287 288 // Canonicalize illegal integer setcc's. 289 if (isInteger) { 290 switch (Result) { 291 default: break; 292 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT 293 case ISD::SETOEQ: // SETEQ & SETU[LG]E 294 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE 295 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE 296 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE 297 } 298 } 299 300 return Result; 301} 302 303const TargetMachine &SelectionDAG::getTarget() const { 304 return MF->getTarget(); 305} 306 307//===----------------------------------------------------------------------===// 308// SDNode Profile Support 309//===----------------------------------------------------------------------===// 310 311/// AddNodeIDOpcode - Add the node opcode to the NodeID data. 312/// 313static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) { 314 ID.AddInteger(OpC); 315} 316 317/// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them 318/// solely with their pointer. 319static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) { 320 ID.AddPointer(VTList.VTs); 321} 322 323/// AddNodeIDOperands - Various routines for adding operands to the NodeID data. 324/// 325static void AddNodeIDOperands(FoldingSetNodeID &ID, 326 const SDValue *Ops, unsigned NumOps) { 327 for (; NumOps; --NumOps, ++Ops) { 328 ID.AddPointer(Ops->getNode()); 329 ID.AddInteger(Ops->getResNo()); 330 } 331} 332 333/// AddNodeIDOperands - Various routines for adding operands to the NodeID data. 334/// 335static void AddNodeIDOperands(FoldingSetNodeID &ID, 336 const SDUse *Ops, unsigned NumOps) { 337 for (; NumOps; --NumOps, ++Ops) { 338 ID.AddPointer(Ops->getNode()); 339 ID.AddInteger(Ops->getResNo()); 340 } 341} 342 343static void AddNodeIDNode(FoldingSetNodeID &ID, 344 unsigned short OpC, SDVTList VTList, 345 const SDValue *OpList, unsigned N) { 346 AddNodeIDOpcode(ID, OpC); 347 AddNodeIDValueTypes(ID, VTList); 348 AddNodeIDOperands(ID, OpList, N); 349} 350 351/// AddNodeIDCustom - If this is an SDNode with special info, add this info to 352/// the NodeID data. 353static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) { 354 switch (N->getOpcode()) { 355 case ISD::TargetExternalSymbol: 356 case ISD::ExternalSymbol: 357 llvm_unreachable("Should only be used on nodes with operands"); 358 default: break; // Normal nodes don't need extra info. 359 case ISD::TargetConstant: 360 case ISD::Constant: 361 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue()); 362 break; 363 case ISD::TargetConstantFP: 364 case ISD::ConstantFP: { 365 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue()); 366 break; 367 } 368 case ISD::TargetGlobalAddress: 369 case ISD::GlobalAddress: 370 case ISD::TargetGlobalTLSAddress: 371 case ISD::GlobalTLSAddress: { 372 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N); 373 ID.AddPointer(GA->getGlobal()); 374 ID.AddInteger(GA->getOffset()); 375 ID.AddInteger(GA->getTargetFlags()); 376 break; 377 } 378 case ISD::BasicBlock: 379 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock()); 380 break; 381 case ISD::Register: 382 ID.AddInteger(cast<RegisterSDNode>(N)->getReg()); 383 break; 384 385 case ISD::SRCVALUE: 386 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue()); 387 break; 388 case ISD::FrameIndex: 389 case ISD::TargetFrameIndex: 390 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex()); 391 break; 392 case ISD::JumpTable: 393 case ISD::TargetJumpTable: 394 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex()); 395 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags()); 396 break; 397 case ISD::ConstantPool: 398 case ISD::TargetConstantPool: { 399 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N); 400 ID.AddInteger(CP->getAlignment()); 401 ID.AddInteger(CP->getOffset()); 402 if (CP->isMachineConstantPoolEntry()) 403 CP->getMachineCPVal()->AddSelectionDAGCSEId(ID); 404 else 405 ID.AddPointer(CP->getConstVal()); 406 ID.AddInteger(CP->getTargetFlags()); 407 break; 408 } 409 case ISD::LOAD: { 410 const LoadSDNode *LD = cast<LoadSDNode>(N); 411 ID.AddInteger(LD->getMemoryVT().getRawBits()); 412 ID.AddInteger(LD->getRawSubclassData()); 413 break; 414 } 415 case ISD::STORE: { 416 const StoreSDNode *ST = cast<StoreSDNode>(N); 417 ID.AddInteger(ST->getMemoryVT().getRawBits()); 418 ID.AddInteger(ST->getRawSubclassData()); 419 break; 420 } 421 case ISD::ATOMIC_CMP_SWAP: 422 case ISD::ATOMIC_SWAP: 423 case ISD::ATOMIC_LOAD_ADD: 424 case ISD::ATOMIC_LOAD_SUB: 425 case ISD::ATOMIC_LOAD_AND: 426 case ISD::ATOMIC_LOAD_OR: 427 case ISD::ATOMIC_LOAD_XOR: 428 case ISD::ATOMIC_LOAD_NAND: 429 case ISD::ATOMIC_LOAD_MIN: 430 case ISD::ATOMIC_LOAD_MAX: 431 case ISD::ATOMIC_LOAD_UMIN: 432 case ISD::ATOMIC_LOAD_UMAX: { 433 const AtomicSDNode *AT = cast<AtomicSDNode>(N); 434 ID.AddInteger(AT->getMemoryVT().getRawBits()); 435 ID.AddInteger(AT->getRawSubclassData()); 436 break; 437 } 438 case ISD::VECTOR_SHUFFLE: { 439 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N); 440 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements(); 441 i != e; ++i) 442 ID.AddInteger(SVN->getMaskElt(i)); 443 break; 444 } 445 case ISD::TargetBlockAddress: 446 case ISD::BlockAddress: { 447 ID.AddPointer(cast<BlockAddressSDNode>(N)->getBlockAddress()); 448 ID.AddInteger(cast<BlockAddressSDNode>(N)->getTargetFlags()); 449 break; 450 } 451 } // end switch (N->getOpcode()) 452} 453 454/// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID 455/// data. 456static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) { 457 AddNodeIDOpcode(ID, N->getOpcode()); 458 // Add the return value info. 459 AddNodeIDValueTypes(ID, N->getVTList()); 460 // Add the operand info. 461 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands()); 462 463 // Handle SDNode leafs with special info. 464 AddNodeIDCustom(ID, N); 465} 466 467/// encodeMemSDNodeFlags - Generic routine for computing a value for use in 468/// the CSE map that carries volatility, indexing mode, and 469/// extension/truncation information. 470/// 471static inline unsigned 472encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile) { 473 assert((ConvType & 3) == ConvType && 474 "ConvType may not require more than 2 bits!"); 475 assert((AM & 7) == AM && 476 "AM may not require more than 3 bits!"); 477 return ConvType | 478 (AM << 2) | 479 (isVolatile << 5); 480} 481 482//===----------------------------------------------------------------------===// 483// SelectionDAG Class 484//===----------------------------------------------------------------------===// 485 486/// doNotCSE - Return true if CSE should not be performed for this node. 487static bool doNotCSE(SDNode *N) { 488 if (N->getValueType(0) == MVT::Flag) 489 return true; // Never CSE anything that produces a flag. 490 491 switch (N->getOpcode()) { 492 default: break; 493 case ISD::HANDLENODE: 494 case ISD::EH_LABEL: 495 return true; // Never CSE these nodes. 496 } 497 498 // Check that remaining values produced are not flags. 499 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 500 if (N->getValueType(i) == MVT::Flag) 501 return true; // Never CSE anything that produces a flag. 502 503 return false; 504} 505 506/// RemoveDeadNodes - This method deletes all unreachable nodes in the 507/// SelectionDAG. 508void SelectionDAG::RemoveDeadNodes() { 509 // Create a dummy node (which is not added to allnodes), that adds a reference 510 // to the root node, preventing it from being deleted. 511 HandleSDNode Dummy(getRoot()); 512 513 SmallVector<SDNode*, 128> DeadNodes; 514 515 // Add all obviously-dead nodes to the DeadNodes worklist. 516 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) 517 if (I->use_empty()) 518 DeadNodes.push_back(I); 519 520 RemoveDeadNodes(DeadNodes); 521 522 // If the root changed (e.g. it was a dead load, update the root). 523 setRoot(Dummy.getValue()); 524} 525 526/// RemoveDeadNodes - This method deletes the unreachable nodes in the 527/// given list, and any nodes that become unreachable as a result. 528void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes, 529 DAGUpdateListener *UpdateListener) { 530 531 // Process the worklist, deleting the nodes and adding their uses to the 532 // worklist. 533 while (!DeadNodes.empty()) { 534 SDNode *N = DeadNodes.pop_back_val(); 535 536 if (UpdateListener) 537 UpdateListener->NodeDeleted(N, 0); 538 539 // Take the node out of the appropriate CSE map. 540 RemoveNodeFromCSEMaps(N); 541 542 // Next, brutally remove the operand list. This is safe to do, as there are 543 // no cycles in the graph. 544 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) { 545 SDUse &Use = *I++; 546 SDNode *Operand = Use.getNode(); 547 Use.set(SDValue()); 548 549 // Now that we removed this operand, see if there are no uses of it left. 550 if (Operand->use_empty()) 551 DeadNodes.push_back(Operand); 552 } 553 554 DeallocateNode(N); 555 } 556} 557 558void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){ 559 SmallVector<SDNode*, 16> DeadNodes(1, N); 560 RemoveDeadNodes(DeadNodes, UpdateListener); 561} 562 563void SelectionDAG::DeleteNode(SDNode *N) { 564 // First take this out of the appropriate CSE map. 565 RemoveNodeFromCSEMaps(N); 566 567 // Finally, remove uses due to operands of this node, remove from the 568 // AllNodes list, and delete the node. 569 DeleteNodeNotInCSEMaps(N); 570} 571 572void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { 573 assert(N != AllNodes.begin() && "Cannot delete the entry node!"); 574 assert(N->use_empty() && "Cannot delete a node that is not dead!"); 575 576 // Drop all of the operands and decrement used node's use counts. 577 N->DropOperands(); 578 579 DeallocateNode(N); 580} 581 582void SelectionDAG::DeallocateNode(SDNode *N) { 583 if (N->OperandsNeedDelete) 584 delete[] N->OperandList; 585 586 // Set the opcode to DELETED_NODE to help catch bugs when node 587 // memory is reallocated. 588 N->NodeType = ISD::DELETED_NODE; 589 590 NodeAllocator.Deallocate(AllNodes.remove(N)); 591} 592 593/// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that 594/// correspond to it. This is useful when we're about to delete or repurpose 595/// the node. We don't want future request for structurally identical nodes 596/// to return N anymore. 597bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { 598 bool Erased = false; 599 switch (N->getOpcode()) { 600 case ISD::EntryToken: 601 llvm_unreachable("EntryToken should not be in CSEMaps!"); 602 return false; 603 case ISD::HANDLENODE: return false; // noop. 604 case ISD::CONDCODE: 605 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] && 606 "Cond code doesn't exist!"); 607 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0; 608 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0; 609 break; 610 case ISD::ExternalSymbol: 611 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 612 break; 613 case ISD::TargetExternalSymbol: { 614 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N); 615 Erased = TargetExternalSymbols.erase( 616 std::pair<std::string,unsigned char>(ESN->getSymbol(), 617 ESN->getTargetFlags())); 618 break; 619 } 620 case ISD::VALUETYPE: { 621 EVT VT = cast<VTSDNode>(N)->getVT(); 622 if (VT.isExtended()) { 623 Erased = ExtendedValueTypeNodes.erase(VT); 624 } else { 625 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0; 626 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0; 627 } 628 break; 629 } 630 default: 631 // Remove it from the CSE Map. 632 Erased = CSEMap.RemoveNode(N); 633 break; 634 } 635#ifndef NDEBUG 636 // Verify that the node was actually in one of the CSE maps, unless it has a 637 // flag result (which cannot be CSE'd) or is one of the special cases that are 638 // not subject to CSE. 639 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && 640 !N->isMachineOpcode() && !doNotCSE(N)) { 641 N->dump(this); 642 errs() << "\n"; 643 llvm_unreachable("Node is not in map!"); 644 } 645#endif 646 return Erased; 647} 648 649/// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE 650/// maps and modified in place. Add it back to the CSE maps, unless an identical 651/// node already exists, in which case transfer all its users to the existing 652/// node. This transfer can potentially trigger recursive merging. 653/// 654void 655SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N, 656 DAGUpdateListener *UpdateListener) { 657 // For node types that aren't CSE'd, just act as if no identical node 658 // already exists. 659 if (!doNotCSE(N)) { 660 SDNode *Existing = CSEMap.GetOrInsertNode(N); 661 if (Existing != N) { 662 // If there was already an existing matching node, use ReplaceAllUsesWith 663 // to replace the dead one with the existing one. This can cause 664 // recursive merging of other unrelated nodes down the line. 665 ReplaceAllUsesWith(N, Existing, UpdateListener); 666 667 // N is now dead. Inform the listener if it exists and delete it. 668 if (UpdateListener) 669 UpdateListener->NodeDeleted(N, Existing); 670 DeleteNodeNotInCSEMaps(N); 671 return; 672 } 673 } 674 675 // If the node doesn't already exist, we updated it. Inform a listener if 676 // it exists. 677 if (UpdateListener) 678 UpdateListener->NodeUpdated(N); 679} 680 681/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 682/// were replaced with those specified. If this node is never memoized, 683/// return null, otherwise return a pointer to the slot it would take. If a 684/// node already exists with these operands, the slot will be non-null. 685SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op, 686 void *&InsertPos) { 687 if (doNotCSE(N)) 688 return 0; 689 690 SDValue Ops[] = { Op }; 691 FoldingSetNodeID ID; 692 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1); 693 AddNodeIDCustom(ID, N); 694 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 695} 696 697/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 698/// were replaced with those specified. If this node is never memoized, 699/// return null, otherwise return a pointer to the slot it would take. If a 700/// node already exists with these operands, the slot will be non-null. 701SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 702 SDValue Op1, SDValue Op2, 703 void *&InsertPos) { 704 if (doNotCSE(N)) 705 return 0; 706 707 SDValue Ops[] = { Op1, Op2 }; 708 FoldingSetNodeID ID; 709 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2); 710 AddNodeIDCustom(ID, N); 711 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 712} 713 714 715/// FindModifiedNodeSlot - Find a slot for the specified node if its operands 716/// were replaced with those specified. If this node is never memoized, 717/// return null, otherwise return a pointer to the slot it would take. If a 718/// node already exists with these operands, the slot will be non-null. 719SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 720 const SDValue *Ops,unsigned NumOps, 721 void *&InsertPos) { 722 if (doNotCSE(N)) 723 return 0; 724 725 FoldingSetNodeID ID; 726 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps); 727 AddNodeIDCustom(ID, N); 728 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 729} 730 731/// VerifyNode - Sanity check the given node. Aborts if it is invalid. 732void SelectionDAG::VerifyNode(SDNode *N) { 733 switch (N->getOpcode()) { 734 default: 735 break; 736 case ISD::BUILD_PAIR: { 737 EVT VT = N->getValueType(0); 738 assert(N->getNumValues() == 1 && "Too many results!"); 739 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) && 740 "Wrong return type!"); 741 assert(N->getNumOperands() == 2 && "Wrong number of operands!"); 742 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() && 743 "Mismatched operand types!"); 744 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() && 745 "Wrong operand type!"); 746 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() && 747 "Wrong return type size"); 748 break; 749 } 750 case ISD::BUILD_VECTOR: { 751 assert(N->getNumValues() == 1 && "Too many results!"); 752 assert(N->getValueType(0).isVector() && "Wrong return type!"); 753 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() && 754 "Wrong number of operands!"); 755 EVT EltVT = N->getValueType(0).getVectorElementType(); 756 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) 757 assert((I->getValueType() == EltVT || 758 (EltVT.isInteger() && I->getValueType().isInteger() && 759 EltVT.bitsLE(I->getValueType()))) && 760 "Wrong operand type!"); 761 break; 762 } 763 } 764} 765 766/// getEVTAlignment - Compute the default alignment value for the 767/// given type. 768/// 769unsigned SelectionDAG::getEVTAlignment(EVT VT) const { 770 const Type *Ty = VT == MVT::iPTR ? 771 PointerType::get(Type::getInt8Ty(*getContext()), 0) : 772 VT.getTypeForEVT(*getContext()); 773 774 return TLI.getTargetData()->getABITypeAlignment(Ty); 775} 776 777// EntryNode could meaningfully have debug info if we can find it... 778SelectionDAG::SelectionDAG(TargetLowering &tli, FunctionLoweringInfo &fli) 779 : TLI(tli), FLI(fli), DW(0), 780 EntryNode(ISD::EntryToken, DebugLoc::getUnknownLoc(), 781 getVTList(MVT::Other)), Root(getEntryNode()) { 782 AllNodes.push_back(&EntryNode); 783} 784 785void SelectionDAG::init(MachineFunction &mf, MachineModuleInfo *mmi, 786 DwarfWriter *dw) { 787 MF = &mf; 788 MMI = mmi; 789 DW = dw; 790 Context = &mf.getFunction()->getContext(); 791} 792 793SelectionDAG::~SelectionDAG() { 794 allnodes_clear(); 795} 796 797void SelectionDAG::allnodes_clear() { 798 assert(&*AllNodes.begin() == &EntryNode); 799 AllNodes.remove(AllNodes.begin()); 800 while (!AllNodes.empty()) 801 DeallocateNode(AllNodes.begin()); 802} 803 804void SelectionDAG::clear() { 805 allnodes_clear(); 806 OperandAllocator.Reset(); 807 CSEMap.clear(); 808 809 ExtendedValueTypeNodes.clear(); 810 ExternalSymbols.clear(); 811 TargetExternalSymbols.clear(); 812 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(), 813 static_cast<CondCodeSDNode*>(0)); 814 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(), 815 static_cast<SDNode*>(0)); 816 817 EntryNode.UseList = 0; 818 AllNodes.push_back(&EntryNode); 819 Root = getEntryNode(); 820} 821 822SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) { 823 return VT.bitsGT(Op.getValueType()) ? 824 getNode(ISD::SIGN_EXTEND, DL, VT, Op) : 825 getNode(ISD::TRUNCATE, DL, VT, Op); 826} 827 828SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, DebugLoc DL, EVT VT) { 829 return VT.bitsGT(Op.getValueType()) ? 830 getNode(ISD::ZERO_EXTEND, DL, VT, Op) : 831 getNode(ISD::TRUNCATE, DL, VT, Op); 832} 833 834SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT VT) { 835 if (Op.getValueType() == VT) return Op; 836 APInt Imm = APInt::getLowBitsSet(Op.getValueSizeInBits(), 837 VT.getSizeInBits()); 838 return getNode(ISD::AND, DL, Op.getValueType(), Op, 839 getConstant(Imm, Op.getValueType())); 840} 841 842/// getNOT - Create a bitwise NOT operation as (XOR Val, -1). 843/// 844SDValue SelectionDAG::getNOT(DebugLoc DL, SDValue Val, EVT VT) { 845 EVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT; 846 SDValue NegOne = 847 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT); 848 return getNode(ISD::XOR, DL, VT, Val, NegOne); 849} 850 851SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) { 852 EVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT; 853 assert((EltVT.getSizeInBits() >= 64 || 854 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) && 855 "getConstant with a uint64_t value that doesn't fit in the type!"); 856 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT); 857} 858 859SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) { 860 return getConstant(*ConstantInt::get(*Context, Val), VT, isT); 861} 862 863SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) { 864 assert(VT.isInteger() && "Cannot create FP integer constant!"); 865 866 EVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT; 867 assert(Val.getBitWidth() == EltVT.getSizeInBits() && 868 "APInt size does not match type size!"); 869 870 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant; 871 FoldingSetNodeID ID; 872 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0); 873 ID.AddPointer(&Val); 874 void *IP = 0; 875 SDNode *N = NULL; 876 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) 877 if (!VT.isVector()) 878 return SDValue(N, 0); 879 if (!N) { 880 N = NodeAllocator.Allocate<ConstantSDNode>(); 881 new (N) ConstantSDNode(isT, &Val, EltVT); 882 CSEMap.InsertNode(N, IP); 883 AllNodes.push_back(N); 884 } 885 886 SDValue Result(N, 0); 887 if (VT.isVector()) { 888 SmallVector<SDValue, 8> Ops; 889 Ops.assign(VT.getVectorNumElements(), Result); 890 Result = getNode(ISD::BUILD_VECTOR, DebugLoc::getUnknownLoc(), 891 VT, &Ops[0], Ops.size()); 892 } 893 return Result; 894} 895 896SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) { 897 return getConstant(Val, TLI.getPointerTy(), isTarget); 898} 899 900 901SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) { 902 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget); 903} 904 905SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){ 906 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!"); 907 908 EVT EltVT = 909 VT.isVector() ? VT.getVectorElementType() : VT; 910 911 // Do the map lookup using the actual bit pattern for the floating point 912 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 913 // we don't have issues with SNANs. 914 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP; 915 FoldingSetNodeID ID; 916 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0); 917 ID.AddPointer(&V); 918 void *IP = 0; 919 SDNode *N = NULL; 920 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) 921 if (!VT.isVector()) 922 return SDValue(N, 0); 923 if (!N) { 924 N = NodeAllocator.Allocate<ConstantFPSDNode>(); 925 new (N) ConstantFPSDNode(isTarget, &V, EltVT); 926 CSEMap.InsertNode(N, IP); 927 AllNodes.push_back(N); 928 } 929 930 SDValue Result(N, 0); 931 if (VT.isVector()) { 932 SmallVector<SDValue, 8> Ops; 933 Ops.assign(VT.getVectorNumElements(), Result); 934 // FIXME DebugLoc info might be appropriate here 935 Result = getNode(ISD::BUILD_VECTOR, DebugLoc::getUnknownLoc(), 936 VT, &Ops[0], Ops.size()); 937 } 938 return Result; 939} 940 941SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) { 942 EVT EltVT = 943 VT.isVector() ? VT.getVectorElementType() : VT; 944 if (EltVT==MVT::f32) 945 return getConstantFP(APFloat((float)Val), VT, isTarget); 946 else 947 return getConstantFP(APFloat(Val), VT, isTarget); 948} 949 950SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, 951 EVT VT, int64_t Offset, 952 bool isTargetGA, 953 unsigned char TargetFlags) { 954 assert((TargetFlags == 0 || isTargetGA) && 955 "Cannot set target flags on target-independent globals"); 956 957 // Truncate (with sign-extension) the offset value to the pointer size. 958 EVT PTy = TLI.getPointerTy(); 959 unsigned BitWidth = PTy.getSizeInBits(); 960 if (BitWidth < 64) 961 Offset = (Offset << (64 - BitWidth) >> (64 - BitWidth)); 962 963 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV); 964 if (!GVar) { 965 // If GV is an alias then use the aliasee for determining thread-localness. 966 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV)) 967 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false)); 968 } 969 970 unsigned Opc; 971 if (GVar && GVar->isThreadLocal()) 972 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress; 973 else 974 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress; 975 976 FoldingSetNodeID ID; 977 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 978 ID.AddPointer(GV); 979 ID.AddInteger(Offset); 980 ID.AddInteger(TargetFlags); 981 void *IP = 0; 982 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 983 return SDValue(E, 0); 984 SDNode *N = NodeAllocator.Allocate<GlobalAddressSDNode>(); 985 new (N) GlobalAddressSDNode(Opc, GV, VT, Offset, TargetFlags); 986 CSEMap.InsertNode(N, IP); 987 AllNodes.push_back(N); 988 return SDValue(N, 0); 989} 990 991SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) { 992 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex; 993 FoldingSetNodeID ID; 994 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 995 ID.AddInteger(FI); 996 void *IP = 0; 997 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 998 return SDValue(E, 0); 999 SDNode *N = NodeAllocator.Allocate<FrameIndexSDNode>(); 1000 new (N) FrameIndexSDNode(FI, VT, isTarget); 1001 CSEMap.InsertNode(N, IP); 1002 AllNodes.push_back(N); 1003 return SDValue(N, 0); 1004} 1005 1006SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget, 1007 unsigned char TargetFlags) { 1008 assert((TargetFlags == 0 || isTarget) && 1009 "Cannot set target flags on target-independent jump tables"); 1010 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable; 1011 FoldingSetNodeID ID; 1012 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 1013 ID.AddInteger(JTI); 1014 ID.AddInteger(TargetFlags); 1015 void *IP = 0; 1016 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1017 return SDValue(E, 0); 1018 SDNode *N = NodeAllocator.Allocate<JumpTableSDNode>(); 1019 new (N) JumpTableSDNode(JTI, VT, isTarget, TargetFlags); 1020 CSEMap.InsertNode(N, IP); 1021 AllNodes.push_back(N); 1022 return SDValue(N, 0); 1023} 1024 1025SDValue SelectionDAG::getConstantPool(Constant *C, EVT VT, 1026 unsigned Alignment, int Offset, 1027 bool isTarget, 1028 unsigned char TargetFlags) { 1029 assert((TargetFlags == 0 || isTarget) && 1030 "Cannot set target flags on target-independent globals"); 1031 if (Alignment == 0) 1032 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType()); 1033 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 1034 FoldingSetNodeID ID; 1035 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 1036 ID.AddInteger(Alignment); 1037 ID.AddInteger(Offset); 1038 ID.AddPointer(C); 1039 ID.AddInteger(TargetFlags); 1040 void *IP = 0; 1041 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1042 return SDValue(E, 0); 1043 SDNode *N = NodeAllocator.Allocate<ConstantPoolSDNode>(); 1044 new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment, TargetFlags); 1045 CSEMap.InsertNode(N, IP); 1046 AllNodes.push_back(N); 1047 return SDValue(N, 0); 1048} 1049 1050 1051SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT, 1052 unsigned Alignment, int Offset, 1053 bool isTarget, 1054 unsigned char TargetFlags) { 1055 assert((TargetFlags == 0 || isTarget) && 1056 "Cannot set target flags on target-independent globals"); 1057 if (Alignment == 0) 1058 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType()); 1059 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 1060 FoldingSetNodeID ID; 1061 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 1062 ID.AddInteger(Alignment); 1063 ID.AddInteger(Offset); 1064 C->AddSelectionDAGCSEId(ID); 1065 ID.AddInteger(TargetFlags); 1066 void *IP = 0; 1067 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1068 return SDValue(E, 0); 1069 SDNode *N = NodeAllocator.Allocate<ConstantPoolSDNode>(); 1070 new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment, TargetFlags); 1071 CSEMap.InsertNode(N, IP); 1072 AllNodes.push_back(N); 1073 return SDValue(N, 0); 1074} 1075 1076SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 1077 FoldingSetNodeID ID; 1078 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0); 1079 ID.AddPointer(MBB); 1080 void *IP = 0; 1081 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1082 return SDValue(E, 0); 1083 SDNode *N = NodeAllocator.Allocate<BasicBlockSDNode>(); 1084 new (N) BasicBlockSDNode(MBB); 1085 CSEMap.InsertNode(N, IP); 1086 AllNodes.push_back(N); 1087 return SDValue(N, 0); 1088} 1089 1090SDValue SelectionDAG::getValueType(EVT VT) { 1091 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >= 1092 ValueTypeNodes.size()) 1093 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1); 1094 1095 SDNode *&N = VT.isExtended() ? 1096 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy]; 1097 1098 if (N) return SDValue(N, 0); 1099 N = NodeAllocator.Allocate<VTSDNode>(); 1100 new (N) VTSDNode(VT); 1101 AllNodes.push_back(N); 1102 return SDValue(N, 0); 1103} 1104 1105SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) { 1106 SDNode *&N = ExternalSymbols[Sym]; 1107 if (N) return SDValue(N, 0); 1108 N = NodeAllocator.Allocate<ExternalSymbolSDNode>(); 1109 new (N) ExternalSymbolSDNode(false, Sym, 0, VT); 1110 AllNodes.push_back(N); 1111 return SDValue(N, 0); 1112} 1113 1114SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT, 1115 unsigned char TargetFlags) { 1116 SDNode *&N = 1117 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym, 1118 TargetFlags)]; 1119 if (N) return SDValue(N, 0); 1120 N = NodeAllocator.Allocate<ExternalSymbolSDNode>(); 1121 new (N) ExternalSymbolSDNode(true, Sym, TargetFlags, VT); 1122 AllNodes.push_back(N); 1123 return SDValue(N, 0); 1124} 1125 1126SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) { 1127 if ((unsigned)Cond >= CondCodeNodes.size()) 1128 CondCodeNodes.resize(Cond+1); 1129 1130 if (CondCodeNodes[Cond] == 0) { 1131 CondCodeSDNode *N = NodeAllocator.Allocate<CondCodeSDNode>(); 1132 new (N) CondCodeSDNode(Cond); 1133 CondCodeNodes[Cond] = N; 1134 AllNodes.push_back(N); 1135 } 1136 return SDValue(CondCodeNodes[Cond], 0); 1137} 1138 1139// commuteShuffle - swaps the values of N1 and N2, and swaps all indices in 1140// the shuffle mask M that point at N1 to point at N2, and indices that point 1141// N2 to point at N1. 1142static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) { 1143 std::swap(N1, N2); 1144 int NElts = M.size(); 1145 for (int i = 0; i != NElts; ++i) { 1146 if (M[i] >= NElts) 1147 M[i] -= NElts; 1148 else if (M[i] >= 0) 1149 M[i] += NElts; 1150 } 1151} 1152 1153SDValue SelectionDAG::getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, 1154 SDValue N2, const int *Mask) { 1155 assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE"); 1156 assert(VT.isVector() && N1.getValueType().isVector() && 1157 "Vector Shuffle VTs must be a vectors"); 1158 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() 1159 && "Vector Shuffle VTs must have same element type"); 1160 1161 // Canonicalize shuffle undef, undef -> undef 1162 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF) 1163 return getUNDEF(VT); 1164 1165 // Validate that all indices in Mask are within the range of the elements 1166 // input to the shuffle. 1167 unsigned NElts = VT.getVectorNumElements(); 1168 SmallVector<int, 8> MaskVec; 1169 for (unsigned i = 0; i != NElts; ++i) { 1170 assert(Mask[i] < (int)(NElts * 2) && "Index out of range"); 1171 MaskVec.push_back(Mask[i]); 1172 } 1173 1174 // Canonicalize shuffle v, v -> v, undef 1175 if (N1 == N2) { 1176 N2 = getUNDEF(VT); 1177 for (unsigned i = 0; i != NElts; ++i) 1178 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts; 1179 } 1180 1181 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask. 1182 if (N1.getOpcode() == ISD::UNDEF) 1183 commuteShuffle(N1, N2, MaskVec); 1184 1185 // Canonicalize all index into lhs, -> shuffle lhs, undef 1186 // Canonicalize all index into rhs, -> shuffle rhs, undef 1187 bool AllLHS = true, AllRHS = true; 1188 bool N2Undef = N2.getOpcode() == ISD::UNDEF; 1189 for (unsigned i = 0; i != NElts; ++i) { 1190 if (MaskVec[i] >= (int)NElts) { 1191 if (N2Undef) 1192 MaskVec[i] = -1; 1193 else 1194 AllLHS = false; 1195 } else if (MaskVec[i] >= 0) { 1196 AllRHS = false; 1197 } 1198 } 1199 if (AllLHS && AllRHS) 1200 return getUNDEF(VT); 1201 if (AllLHS && !N2Undef) 1202 N2 = getUNDEF(VT); 1203 if (AllRHS) { 1204 N1 = getUNDEF(VT); 1205 commuteShuffle(N1, N2, MaskVec); 1206 } 1207 1208 // If Identity shuffle, or all shuffle in to undef, return that node. 1209 bool AllUndef = true; 1210 bool Identity = true; 1211 for (unsigned i = 0; i != NElts; ++i) { 1212 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false; 1213 if (MaskVec[i] >= 0) AllUndef = false; 1214 } 1215 if (Identity && NElts == N1.getValueType().getVectorNumElements()) 1216 return N1; 1217 if (AllUndef) 1218 return getUNDEF(VT); 1219 1220 FoldingSetNodeID ID; 1221 SDValue Ops[2] = { N1, N2 }; 1222 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2); 1223 for (unsigned i = 0; i != NElts; ++i) 1224 ID.AddInteger(MaskVec[i]); 1225 1226 void* IP = 0; 1227 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1228 return SDValue(E, 0); 1229 1230 // Allocate the mask array for the node out of the BumpPtrAllocator, since 1231 // SDNode doesn't have access to it. This memory will be "leaked" when 1232 // the node is deallocated, but recovered when the NodeAllocator is released. 1233 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts); 1234 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int)); 1235 1236 ShuffleVectorSDNode *N = NodeAllocator.Allocate<ShuffleVectorSDNode>(); 1237 new (N) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc); 1238 CSEMap.InsertNode(N, IP); 1239 AllNodes.push_back(N); 1240 return SDValue(N, 0); 1241} 1242 1243SDValue SelectionDAG::getConvertRndSat(EVT VT, DebugLoc dl, 1244 SDValue Val, SDValue DTy, 1245 SDValue STy, SDValue Rnd, SDValue Sat, 1246 ISD::CvtCode Code) { 1247 // If the src and dest types are the same and the conversion is between 1248 // integer types of the same sign or two floats, no conversion is necessary. 1249 if (DTy == STy && 1250 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF)) 1251 return Val; 1252 1253 FoldingSetNodeID ID; 1254 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat }; 1255 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), &Ops[0], 5); 1256 void* IP = 0; 1257 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1258 return SDValue(E, 0); 1259 CvtRndSatSDNode *N = NodeAllocator.Allocate<CvtRndSatSDNode>(); 1260 new (N) CvtRndSatSDNode(VT, dl, Ops, 5, Code); 1261 CSEMap.InsertNode(N, IP); 1262 AllNodes.push_back(N); 1263 return SDValue(N, 0); 1264} 1265 1266SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) { 1267 FoldingSetNodeID ID; 1268 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0); 1269 ID.AddInteger(RegNo); 1270 void *IP = 0; 1271 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1272 return SDValue(E, 0); 1273 SDNode *N = NodeAllocator.Allocate<RegisterSDNode>(); 1274 new (N) RegisterSDNode(RegNo, VT); 1275 CSEMap.InsertNode(N, IP); 1276 AllNodes.push_back(N); 1277 return SDValue(N, 0); 1278} 1279 1280SDValue SelectionDAG::getLabel(unsigned Opcode, DebugLoc dl, 1281 SDValue Root, 1282 unsigned LabelID) { 1283 FoldingSetNodeID ID; 1284 SDValue Ops[] = { Root }; 1285 AddNodeIDNode(ID, Opcode, getVTList(MVT::Other), &Ops[0], 1); 1286 ID.AddInteger(LabelID); 1287 void *IP = 0; 1288 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1289 return SDValue(E, 0); 1290 SDNode *N = NodeAllocator.Allocate<LabelSDNode>(); 1291 new (N) LabelSDNode(Opcode, dl, Root, LabelID); 1292 CSEMap.InsertNode(N, IP); 1293 AllNodes.push_back(N); 1294 return SDValue(N, 0); 1295} 1296 1297SDValue SelectionDAG::getBlockAddress(BlockAddress *BA, EVT VT, 1298 bool isTarget, 1299 unsigned char TargetFlags) { 1300 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress; 1301 1302 FoldingSetNodeID ID; 1303 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 1304 ID.AddPointer(BA); 1305 ID.AddInteger(TargetFlags); 1306 void *IP = 0; 1307 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1308 return SDValue(E, 0); 1309 SDNode *N = NodeAllocator.Allocate<BlockAddressSDNode>(); 1310 new (N) BlockAddressSDNode(Opc, VT, BA, TargetFlags); 1311 CSEMap.InsertNode(N, IP); 1312 AllNodes.push_back(N); 1313 return SDValue(N, 0); 1314} 1315 1316SDValue SelectionDAG::getSrcValue(const Value *V) { 1317 assert((!V || isa<PointerType>(V->getType())) && 1318 "SrcValue is not a pointer?"); 1319 1320 FoldingSetNodeID ID; 1321 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0); 1322 ID.AddPointer(V); 1323 1324 void *IP = 0; 1325 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1326 return SDValue(E, 0); 1327 1328 SDNode *N = NodeAllocator.Allocate<SrcValueSDNode>(); 1329 new (N) SrcValueSDNode(V); 1330 CSEMap.InsertNode(N, IP); 1331 AllNodes.push_back(N); 1332 return SDValue(N, 0); 1333} 1334 1335/// getShiftAmountOperand - Return the specified value casted to 1336/// the target's desired shift amount type. 1337SDValue SelectionDAG::getShiftAmountOperand(SDValue Op) { 1338 EVT OpTy = Op.getValueType(); 1339 MVT ShTy = TLI.getShiftAmountTy(); 1340 if (OpTy == ShTy || OpTy.isVector()) return Op; 1341 1342 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND; 1343 return getNode(Opcode, Op.getDebugLoc(), ShTy, Op); 1344} 1345 1346/// CreateStackTemporary - Create a stack temporary, suitable for holding the 1347/// specified value type. 1348SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) { 1349 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo(); 1350 unsigned ByteSize = VT.getStoreSize(); 1351 const Type *Ty = VT.getTypeForEVT(*getContext()); 1352 unsigned StackAlign = 1353 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign); 1354 1355 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false); 1356 return getFrameIndex(FrameIdx, TLI.getPointerTy()); 1357} 1358 1359/// CreateStackTemporary - Create a stack temporary suitable for holding 1360/// either of the specified value types. 1361SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) { 1362 unsigned Bytes = std::max(VT1.getStoreSizeInBits(), 1363 VT2.getStoreSizeInBits())/8; 1364 const Type *Ty1 = VT1.getTypeForEVT(*getContext()); 1365 const Type *Ty2 = VT2.getTypeForEVT(*getContext()); 1366 const TargetData *TD = TLI.getTargetData(); 1367 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1), 1368 TD->getPrefTypeAlignment(Ty2)); 1369 1370 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo(); 1371 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false); 1372 return getFrameIndex(FrameIdx, TLI.getPointerTy()); 1373} 1374 1375SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1, 1376 SDValue N2, ISD::CondCode Cond, DebugLoc dl) { 1377 // These setcc operations always fold. 1378 switch (Cond) { 1379 default: break; 1380 case ISD::SETFALSE: 1381 case ISD::SETFALSE2: return getConstant(0, VT); 1382 case ISD::SETTRUE: 1383 case ISD::SETTRUE2: return getConstant(1, VT); 1384 1385 case ISD::SETOEQ: 1386 case ISD::SETOGT: 1387 case ISD::SETOGE: 1388 case ISD::SETOLT: 1389 case ISD::SETOLE: 1390 case ISD::SETONE: 1391 case ISD::SETO: 1392 case ISD::SETUO: 1393 case ISD::SETUEQ: 1394 case ISD::SETUNE: 1395 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!"); 1396 break; 1397 } 1398 1399 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) { 1400 const APInt &C2 = N2C->getAPIntValue(); 1401 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) { 1402 const APInt &C1 = N1C->getAPIntValue(); 1403 1404 switch (Cond) { 1405 default: llvm_unreachable("Unknown integer setcc!"); 1406 case ISD::SETEQ: return getConstant(C1 == C2, VT); 1407 case ISD::SETNE: return getConstant(C1 != C2, VT); 1408 case ISD::SETULT: return getConstant(C1.ult(C2), VT); 1409 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT); 1410 case ISD::SETULE: return getConstant(C1.ule(C2), VT); 1411 case ISD::SETUGE: return getConstant(C1.uge(C2), VT); 1412 case ISD::SETLT: return getConstant(C1.slt(C2), VT); 1413 case ISD::SETGT: return getConstant(C1.sgt(C2), VT); 1414 case ISD::SETLE: return getConstant(C1.sle(C2), VT); 1415 case ISD::SETGE: return getConstant(C1.sge(C2), VT); 1416 } 1417 } 1418 } 1419 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) { 1420 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) { 1421 // No compile time operations on this type yet. 1422 if (N1C->getValueType(0) == MVT::ppcf128) 1423 return SDValue(); 1424 1425 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF()); 1426 switch (Cond) { 1427 default: break; 1428 case ISD::SETEQ: if (R==APFloat::cmpUnordered) 1429 return getUNDEF(VT); 1430 // fall through 1431 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT); 1432 case ISD::SETNE: if (R==APFloat::cmpUnordered) 1433 return getUNDEF(VT); 1434 // fall through 1435 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan || 1436 R==APFloat::cmpLessThan, VT); 1437 case ISD::SETLT: if (R==APFloat::cmpUnordered) 1438 return getUNDEF(VT); 1439 // fall through 1440 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT); 1441 case ISD::SETGT: if (R==APFloat::cmpUnordered) 1442 return getUNDEF(VT); 1443 // fall through 1444 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT); 1445 case ISD::SETLE: if (R==APFloat::cmpUnordered) 1446 return getUNDEF(VT); 1447 // fall through 1448 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan || 1449 R==APFloat::cmpEqual, VT); 1450 case ISD::SETGE: if (R==APFloat::cmpUnordered) 1451 return getUNDEF(VT); 1452 // fall through 1453 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan || 1454 R==APFloat::cmpEqual, VT); 1455 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT); 1456 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT); 1457 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered || 1458 R==APFloat::cmpEqual, VT); 1459 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT); 1460 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered || 1461 R==APFloat::cmpLessThan, VT); 1462 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan || 1463 R==APFloat::cmpUnordered, VT); 1464 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT); 1465 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT); 1466 } 1467 } else { 1468 // Ensure that the constant occurs on the RHS. 1469 return getSetCC(dl, VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 1470 } 1471 } 1472 1473 // Could not fold it. 1474 return SDValue(); 1475} 1476 1477/// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 1478/// use this predicate to simplify operations downstream. 1479bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const { 1480 // This predicate is not safe for vector operations. 1481 if (Op.getValueType().isVector()) 1482 return false; 1483 1484 unsigned BitWidth = Op.getValueSizeInBits(); 1485 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth); 1486} 1487 1488/// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 1489/// this predicate to simplify operations downstream. Mask is known to be zero 1490/// for bits that V cannot have. 1491bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask, 1492 unsigned Depth) const { 1493 APInt KnownZero, KnownOne; 1494 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 1495 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1496 return (KnownZero & Mask) == Mask; 1497} 1498 1499/// ComputeMaskedBits - Determine which of the bits specified in Mask are 1500/// known to be either zero or one and return them in the KnownZero/KnownOne 1501/// bitsets. This code only analyzes bits in Mask, in order to short-circuit 1502/// processing. 1503void SelectionDAG::ComputeMaskedBits(SDValue Op, const APInt &Mask, 1504 APInt &KnownZero, APInt &KnownOne, 1505 unsigned Depth) const { 1506 unsigned BitWidth = Mask.getBitWidth(); 1507 assert(BitWidth == Op.getValueType().getSizeInBits() && 1508 "Mask size mismatches value type size!"); 1509 1510 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything. 1511 if (Depth == 6 || Mask == 0) 1512 return; // Limit search depth. 1513 1514 APInt KnownZero2, KnownOne2; 1515 1516 switch (Op.getOpcode()) { 1517 case ISD::Constant: 1518 // We know all of the bits for a constant! 1519 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue() & Mask; 1520 KnownZero = ~KnownOne & Mask; 1521 return; 1522 case ISD::AND: 1523 // If either the LHS or the RHS are Zero, the result is zero. 1524 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1525 ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownZero, 1526 KnownZero2, KnownOne2, Depth+1); 1527 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1528 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1529 1530 // Output known-1 bits are only known if set in both the LHS & RHS. 1531 KnownOne &= KnownOne2; 1532 // Output known-0 are known to be clear if zero in either the LHS | RHS. 1533 KnownZero |= KnownZero2; 1534 return; 1535 case ISD::OR: 1536 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1537 ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownOne, 1538 KnownZero2, KnownOne2, Depth+1); 1539 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1540 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1541 1542 // Output known-0 bits are only known if clear in both the LHS & RHS. 1543 KnownZero &= KnownZero2; 1544 // Output known-1 are known to be set if set in either the LHS | RHS. 1545 KnownOne |= KnownOne2; 1546 return; 1547 case ISD::XOR: { 1548 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 1549 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 1550 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1551 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1552 1553 // Output known-0 bits are known if clear or set in both the LHS & RHS. 1554 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 1555 // Output known-1 are known to be set if set in only one of the LHS, RHS. 1556 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 1557 KnownZero = KnownZeroOut; 1558 return; 1559 } 1560 case ISD::MUL: { 1561 APInt Mask2 = APInt::getAllOnesValue(BitWidth); 1562 ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero, KnownOne, Depth+1); 1563 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1); 1564 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1565 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1566 1567 // If low bits are zero in either operand, output low known-0 bits. 1568 // Also compute a conserative estimate for high known-0 bits. 1569 // More trickiness is possible, but this is sufficient for the 1570 // interesting case of alignment computation. 1571 KnownOne.clear(); 1572 unsigned TrailZ = KnownZero.countTrailingOnes() + 1573 KnownZero2.countTrailingOnes(); 1574 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 1575 KnownZero2.countLeadingOnes(), 1576 BitWidth) - BitWidth; 1577 1578 TrailZ = std::min(TrailZ, BitWidth); 1579 LeadZ = std::min(LeadZ, BitWidth); 1580 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 1581 APInt::getHighBitsSet(BitWidth, LeadZ); 1582 KnownZero &= Mask; 1583 return; 1584 } 1585 case ISD::UDIV: { 1586 // For the purposes of computing leading zeros we can conservatively 1587 // treat a udiv as a logical right shift by the power of 2 known to 1588 // be less than the denominator. 1589 APInt AllOnes = APInt::getAllOnesValue(BitWidth); 1590 ComputeMaskedBits(Op.getOperand(0), 1591 AllOnes, KnownZero2, KnownOne2, Depth+1); 1592 unsigned LeadZ = KnownZero2.countLeadingOnes(); 1593 1594 KnownOne2.clear(); 1595 KnownZero2.clear(); 1596 ComputeMaskedBits(Op.getOperand(1), 1597 AllOnes, KnownZero2, KnownOne2, Depth+1); 1598 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 1599 if (RHSUnknownLeadingOnes != BitWidth) 1600 LeadZ = std::min(BitWidth, 1601 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 1602 1603 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask; 1604 return; 1605 } 1606 case ISD::SELECT: 1607 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1); 1608 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1); 1609 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1610 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1611 1612 // Only known if known in both the LHS and RHS. 1613 KnownOne &= KnownOne2; 1614 KnownZero &= KnownZero2; 1615 return; 1616 case ISD::SELECT_CC: 1617 ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1); 1618 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1); 1619 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1620 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1621 1622 // Only known if known in both the LHS and RHS. 1623 KnownOne &= KnownOne2; 1624 KnownZero &= KnownZero2; 1625 return; 1626 case ISD::SADDO: 1627 case ISD::UADDO: 1628 case ISD::SSUBO: 1629 case ISD::USUBO: 1630 case ISD::SMULO: 1631 case ISD::UMULO: 1632 if (Op.getResNo() != 1) 1633 return; 1634 // The boolean result conforms to getBooleanContents. Fall through. 1635 case ISD::SETCC: 1636 // If we know the result of a setcc has the top bits zero, use this info. 1637 if (TLI.getBooleanContents() == TargetLowering::ZeroOrOneBooleanContent && 1638 BitWidth > 1) 1639 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1); 1640 return; 1641 case ISD::SHL: 1642 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 1643 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1644 unsigned ShAmt = SA->getZExtValue(); 1645 1646 // If the shift count is an invalid immediate, don't do anything. 1647 if (ShAmt >= BitWidth) 1648 return; 1649 1650 ComputeMaskedBits(Op.getOperand(0), Mask.lshr(ShAmt), 1651 KnownZero, KnownOne, Depth+1); 1652 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1653 KnownZero <<= ShAmt; 1654 KnownOne <<= ShAmt; 1655 // low bits known zero. 1656 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt); 1657 } 1658 return; 1659 case ISD::SRL: 1660 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 1661 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1662 unsigned ShAmt = SA->getZExtValue(); 1663 1664 // If the shift count is an invalid immediate, don't do anything. 1665 if (ShAmt >= BitWidth) 1666 return; 1667 1668 ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt), 1669 KnownZero, KnownOne, Depth+1); 1670 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1671 KnownZero = KnownZero.lshr(ShAmt); 1672 KnownOne = KnownOne.lshr(ShAmt); 1673 1674 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask; 1675 KnownZero |= HighBits; // High bits known zero. 1676 } 1677 return; 1678 case ISD::SRA: 1679 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1680 unsigned ShAmt = SA->getZExtValue(); 1681 1682 // If the shift count is an invalid immediate, don't do anything. 1683 if (ShAmt >= BitWidth) 1684 return; 1685 1686 APInt InDemandedMask = (Mask << ShAmt); 1687 // If any of the demanded bits are produced by the sign extension, we also 1688 // demand the input sign bit. 1689 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask; 1690 if (HighBits.getBoolValue()) 1691 InDemandedMask |= APInt::getSignBit(BitWidth); 1692 1693 ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne, 1694 Depth+1); 1695 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1696 KnownZero = KnownZero.lshr(ShAmt); 1697 KnownOne = KnownOne.lshr(ShAmt); 1698 1699 // Handle the sign bits. 1700 APInt SignBit = APInt::getSignBit(BitWidth); 1701 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask. 1702 1703 if (KnownZero.intersects(SignBit)) { 1704 KnownZero |= HighBits; // New bits are known zero. 1705 } else if (KnownOne.intersects(SignBit)) { 1706 KnownOne |= HighBits; // New bits are known one. 1707 } 1708 } 1709 return; 1710 case ISD::SIGN_EXTEND_INREG: { 1711 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 1712 unsigned EBits = EVT.getSizeInBits(); 1713 1714 // Sign extension. Compute the demanded bits in the result that are not 1715 // present in the input. 1716 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits) & Mask; 1717 1718 APInt InSignBit = APInt::getSignBit(EBits); 1719 APInt InputDemandedBits = Mask & APInt::getLowBitsSet(BitWidth, EBits); 1720 1721 // If the sign extended bits are demanded, we know that the sign 1722 // bit is demanded. 1723 InSignBit.zext(BitWidth); 1724 if (NewBits.getBoolValue()) 1725 InputDemandedBits |= InSignBit; 1726 1727 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits, 1728 KnownZero, KnownOne, Depth+1); 1729 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1730 1731 // If the sign bit of the input is known set or clear, then we know the 1732 // top bits of the result. 1733 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear 1734 KnownZero |= NewBits; 1735 KnownOne &= ~NewBits; 1736 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set 1737 KnownOne |= NewBits; 1738 KnownZero &= ~NewBits; 1739 } else { // Input sign bit unknown 1740 KnownZero &= ~NewBits; 1741 KnownOne &= ~NewBits; 1742 } 1743 return; 1744 } 1745 case ISD::CTTZ: 1746 case ISD::CTLZ: 1747 case ISD::CTPOP: { 1748 unsigned LowBits = Log2_32(BitWidth)+1; 1749 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 1750 KnownOne.clear(); 1751 return; 1752 } 1753 case ISD::LOAD: { 1754 if (ISD::isZEXTLoad(Op.getNode())) { 1755 LoadSDNode *LD = cast<LoadSDNode>(Op); 1756 EVT VT = LD->getMemoryVT(); 1757 unsigned MemBits = VT.getSizeInBits(); 1758 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits) & Mask; 1759 } 1760 return; 1761 } 1762 case ISD::ZERO_EXTEND: { 1763 EVT InVT = Op.getOperand(0).getValueType(); 1764 unsigned InBits = InVT.getSizeInBits(); 1765 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask; 1766 APInt InMask = Mask; 1767 InMask.trunc(InBits); 1768 KnownZero.trunc(InBits); 1769 KnownOne.trunc(InBits); 1770 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1); 1771 KnownZero.zext(BitWidth); 1772 KnownOne.zext(BitWidth); 1773 KnownZero |= NewBits; 1774 return; 1775 } 1776 case ISD::SIGN_EXTEND: { 1777 EVT InVT = Op.getOperand(0).getValueType(); 1778 unsigned InBits = InVT.getSizeInBits(); 1779 APInt InSignBit = APInt::getSignBit(InBits); 1780 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask; 1781 APInt InMask = Mask; 1782 InMask.trunc(InBits); 1783 1784 // If any of the sign extended bits are demanded, we know that the sign 1785 // bit is demanded. Temporarily set this bit in the mask for our callee. 1786 if (NewBits.getBoolValue()) 1787 InMask |= InSignBit; 1788 1789 KnownZero.trunc(InBits); 1790 KnownOne.trunc(InBits); 1791 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1); 1792 1793 // Note if the sign bit is known to be zero or one. 1794 bool SignBitKnownZero = KnownZero.isNegative(); 1795 bool SignBitKnownOne = KnownOne.isNegative(); 1796 assert(!(SignBitKnownZero && SignBitKnownOne) && 1797 "Sign bit can't be known to be both zero and one!"); 1798 1799 // If the sign bit wasn't actually demanded by our caller, we don't 1800 // want it set in the KnownZero and KnownOne result values. Reset the 1801 // mask and reapply it to the result values. 1802 InMask = Mask; 1803 InMask.trunc(InBits); 1804 KnownZero &= InMask; 1805 KnownOne &= InMask; 1806 1807 KnownZero.zext(BitWidth); 1808 KnownOne.zext(BitWidth); 1809 1810 // If the sign bit is known zero or one, the top bits match. 1811 if (SignBitKnownZero) 1812 KnownZero |= NewBits; 1813 else if (SignBitKnownOne) 1814 KnownOne |= NewBits; 1815 return; 1816 } 1817 case ISD::ANY_EXTEND: { 1818 EVT InVT = Op.getOperand(0).getValueType(); 1819 unsigned InBits = InVT.getSizeInBits(); 1820 APInt InMask = Mask; 1821 InMask.trunc(InBits); 1822 KnownZero.trunc(InBits); 1823 KnownOne.trunc(InBits); 1824 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1); 1825 KnownZero.zext(BitWidth); 1826 KnownOne.zext(BitWidth); 1827 return; 1828 } 1829 case ISD::TRUNCATE: { 1830 EVT InVT = Op.getOperand(0).getValueType(); 1831 unsigned InBits = InVT.getSizeInBits(); 1832 APInt InMask = Mask; 1833 InMask.zext(InBits); 1834 KnownZero.zext(InBits); 1835 KnownOne.zext(InBits); 1836 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1); 1837 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 1838 KnownZero.trunc(BitWidth); 1839 KnownOne.trunc(BitWidth); 1840 break; 1841 } 1842 case ISD::AssertZext: { 1843 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 1844 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits()); 1845 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 1846 KnownOne, Depth+1); 1847 KnownZero |= (~InMask) & Mask; 1848 return; 1849 } 1850 case ISD::FGETSIGN: 1851 // All bits are zero except the low bit. 1852 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1); 1853 return; 1854 1855 case ISD::SUB: { 1856 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) { 1857 // We know that the top bits of C-X are clear if X contains less bits 1858 // than C (i.e. no wrap-around can happen). For example, 20-X is 1859 // positive if we can prove that X is >= 0 and < 16. 1860 if (CLHS->getAPIntValue().isNonNegative()) { 1861 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros(); 1862 // NLZ can't be BitWidth with no sign bit 1863 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 1864 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero2, KnownOne2, 1865 Depth+1); 1866 1867 // If all of the MaskV bits are known to be zero, then we know the 1868 // output top bits are zero, because we now know that the output is 1869 // from [0-C]. 1870 if ((KnownZero2 & MaskV) == MaskV) { 1871 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros(); 1872 // Top bits known zero. 1873 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask; 1874 } 1875 } 1876 } 1877 } 1878 // fall through 1879 case ISD::ADD: { 1880 // Output known-0 bits are known if clear or set in both the low clear bits 1881 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the 1882 // low 3 bits clear. 1883 APInt Mask2 = APInt::getLowBitsSet(BitWidth, Mask.countTrailingOnes()); 1884 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1); 1885 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1886 unsigned KnownZeroOut = KnownZero2.countTrailingOnes(); 1887 1888 ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero2, KnownOne2, Depth+1); 1889 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 1890 KnownZeroOut = std::min(KnownZeroOut, 1891 KnownZero2.countTrailingOnes()); 1892 1893 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut); 1894 return; 1895 } 1896 case ISD::SREM: 1897 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1898 const APInt &RA = Rem->getAPIntValue(); 1899 if (RA.isPowerOf2() || (-RA).isPowerOf2()) { 1900 APInt LowBits = RA.isStrictlyPositive() ? (RA - 1) : ~RA; 1901 APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 1902 ComputeMaskedBits(Op.getOperand(0), Mask2,KnownZero2,KnownOne2,Depth+1); 1903 1904 // If the sign bit of the first operand is zero, the sign bit of 1905 // the result is zero. If the first operand has no one bits below 1906 // the second operand's single 1 bit, its sign will be zero. 1907 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 1908 KnownZero2 |= ~LowBits; 1909 1910 KnownZero |= KnownZero2 & Mask; 1911 1912 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 1913 } 1914 } 1915 return; 1916 case ISD::UREM: { 1917 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 1918 const APInt &RA = Rem->getAPIntValue(); 1919 if (RA.isPowerOf2()) { 1920 APInt LowBits = (RA - 1); 1921 APInt Mask2 = LowBits & Mask; 1922 KnownZero |= ~LowBits & Mask; 1923 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero, KnownOne,Depth+1); 1924 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 1925 break; 1926 } 1927 } 1928 1929 // Since the result is less than or equal to either operand, any leading 1930 // zero bits in either operand must also exist in the result. 1931 APInt AllOnes = APInt::getAllOnesValue(BitWidth); 1932 ComputeMaskedBits(Op.getOperand(0), AllOnes, KnownZero, KnownOne, 1933 Depth+1); 1934 ComputeMaskedBits(Op.getOperand(1), AllOnes, KnownZero2, KnownOne2, 1935 Depth+1); 1936 1937 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(), 1938 KnownZero2.countLeadingOnes()); 1939 KnownOne.clear(); 1940 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask; 1941 return; 1942 } 1943 default: 1944 // Allow the target to implement this method for its nodes. 1945 if (Op.getOpcode() >= ISD::BUILTIN_OP_END) { 1946 case ISD::INTRINSIC_WO_CHAIN: 1947 case ISD::INTRINSIC_W_CHAIN: 1948 case ISD::INTRINSIC_VOID: 1949 TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this, 1950 Depth); 1951 } 1952 return; 1953 } 1954} 1955 1956/// ComputeNumSignBits - Return the number of times the sign bit of the 1957/// register is replicated into the other bits. We know that at least 1 bit 1958/// is always equal to the sign bit (itself), but other cases can give us 1959/// information. For example, immediately after an "SRA X, 2", we know that 1960/// the top 3 bits are all equal to each other, so we return 3. 1961unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{ 1962 EVT VT = Op.getValueType(); 1963 assert(VT.isInteger() && "Invalid VT!"); 1964 unsigned VTBits = VT.getSizeInBits(); 1965 unsigned Tmp, Tmp2; 1966 unsigned FirstAnswer = 1; 1967 1968 if (Depth == 6) 1969 return 1; // Limit search depth. 1970 1971 switch (Op.getOpcode()) { 1972 default: break; 1973 case ISD::AssertSext: 1974 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits(); 1975 return VTBits-Tmp+1; 1976 case ISD::AssertZext: 1977 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits(); 1978 return VTBits-Tmp; 1979 1980 case ISD::Constant: { 1981 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue(); 1982 // If negative, return # leading ones. 1983 if (Val.isNegative()) 1984 return Val.countLeadingOnes(); 1985 1986 // Return # leading zeros. 1987 return Val.countLeadingZeros(); 1988 } 1989 1990 case ISD::SIGN_EXTEND: 1991 Tmp = VTBits-Op.getOperand(0).getValueType().getSizeInBits(); 1992 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp; 1993 1994 case ISD::SIGN_EXTEND_INREG: 1995 // Max of the input and what this extends. 1996 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits(); 1997 Tmp = VTBits-Tmp+1; 1998 1999 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2000 return std::max(Tmp, Tmp2); 2001 2002 case ISD::SRA: 2003 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2004 // SRA X, C -> adds C sign bits. 2005 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2006 Tmp += C->getZExtValue(); 2007 if (Tmp > VTBits) Tmp = VTBits; 2008 } 2009 return Tmp; 2010 case ISD::SHL: 2011 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2012 // shl destroys sign bits. 2013 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2014 if (C->getZExtValue() >= VTBits || // Bad shift. 2015 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out. 2016 return Tmp - C->getZExtValue(); 2017 } 2018 break; 2019 case ISD::AND: 2020 case ISD::OR: 2021 case ISD::XOR: // NOT is handled here. 2022 // Logical binary ops preserve the number of sign bits at the worst. 2023 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2024 if (Tmp != 1) { 2025 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 2026 FirstAnswer = std::min(Tmp, Tmp2); 2027 // We computed what we know about the sign bits as our first 2028 // answer. Now proceed to the generic code that uses 2029 // ComputeMaskedBits, and pick whichever answer is better. 2030 } 2031 break; 2032 2033 case ISD::SELECT: 2034 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1); 2035 if (Tmp == 1) return 1; // Early out. 2036 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1); 2037 return std::min(Tmp, Tmp2); 2038 2039 case ISD::SADDO: 2040 case ISD::UADDO: 2041 case ISD::SSUBO: 2042 case ISD::USUBO: 2043 case ISD::SMULO: 2044 case ISD::UMULO: 2045 if (Op.getResNo() != 1) 2046 break; 2047 // The boolean result conforms to getBooleanContents. Fall through. 2048 case ISD::SETCC: 2049 // If setcc returns 0/-1, all bits are sign bits. 2050 if (TLI.getBooleanContents() == 2051 TargetLowering::ZeroOrNegativeOneBooleanContent) 2052 return VTBits; 2053 break; 2054 case ISD::ROTL: 2055 case ISD::ROTR: 2056 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2057 unsigned RotAmt = C->getZExtValue() & (VTBits-1); 2058 2059 // Handle rotate right by N like a rotate left by 32-N. 2060 if (Op.getOpcode() == ISD::ROTR) 2061 RotAmt = (VTBits-RotAmt) & (VTBits-1); 2062 2063 // If we aren't rotating out all of the known-in sign bits, return the 2064 // number that are left. This handles rotl(sext(x), 1) for example. 2065 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2066 if (Tmp > RotAmt+1) return Tmp-RotAmt; 2067 } 2068 break; 2069 case ISD::ADD: 2070 // Add can have at most one carry bit. Thus we know that the output 2071 // is, at worst, one more bit than the inputs. 2072 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2073 if (Tmp == 1) return 1; // Early out. 2074 2075 // Special case decrementing a value (ADD X, -1): 2076 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 2077 if (CRHS->isAllOnesValue()) { 2078 APInt KnownZero, KnownOne; 2079 APInt Mask = APInt::getAllOnesValue(VTBits); 2080 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 2081 2082 // If the input is known to be 0 or 1, the output is 0/-1, which is all 2083 // sign bits set. 2084 if ((KnownZero | APInt(VTBits, 1)) == Mask) 2085 return VTBits; 2086 2087 // If we are subtracting one from a positive number, there is no carry 2088 // out of the result. 2089 if (KnownZero.isNegative()) 2090 return Tmp; 2091 } 2092 2093 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 2094 if (Tmp2 == 1) return 1; 2095 return std::min(Tmp, Tmp2)-1; 2096 break; 2097 2098 case ISD::SUB: 2099 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 2100 if (Tmp2 == 1) return 1; 2101 2102 // Handle NEG. 2103 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) 2104 if (CLHS->isNullValue()) { 2105 APInt KnownZero, KnownOne; 2106 APInt Mask = APInt::getAllOnesValue(VTBits); 2107 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 2108 // If the input is known to be 0 or 1, the output is 0/-1, which is all 2109 // sign bits set. 2110 if ((KnownZero | APInt(VTBits, 1)) == Mask) 2111 return VTBits; 2112 2113 // If the input is known to be positive (the sign bit is known clear), 2114 // the output of the NEG has the same number of sign bits as the input. 2115 if (KnownZero.isNegative()) 2116 return Tmp2; 2117 2118 // Otherwise, we treat this like a SUB. 2119 } 2120 2121 // Sub can have at most one carry bit. Thus we know that the output 2122 // is, at worst, one more bit than the inputs. 2123 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2124 if (Tmp == 1) return 1; // Early out. 2125 return std::min(Tmp, Tmp2)-1; 2126 break; 2127 case ISD::TRUNCATE: 2128 // FIXME: it's tricky to do anything useful for this, but it is an important 2129 // case for targets like X86. 2130 break; 2131 } 2132 2133 // Handle LOADX separately here. EXTLOAD case will fallthrough. 2134 if (Op.getOpcode() == ISD::LOAD) { 2135 LoadSDNode *LD = cast<LoadSDNode>(Op); 2136 unsigned ExtType = LD->getExtensionType(); 2137 switch (ExtType) { 2138 default: break; 2139 case ISD::SEXTLOAD: // '17' bits known 2140 Tmp = LD->getMemoryVT().getSizeInBits(); 2141 return VTBits-Tmp+1; 2142 case ISD::ZEXTLOAD: // '16' bits known 2143 Tmp = LD->getMemoryVT().getSizeInBits(); 2144 return VTBits-Tmp; 2145 } 2146 } 2147 2148 // Allow the target to implement this method for its nodes. 2149 if (Op.getOpcode() >= ISD::BUILTIN_OP_END || 2150 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 2151 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 2152 Op.getOpcode() == ISD::INTRINSIC_VOID) { 2153 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth); 2154 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits); 2155 } 2156 2157 // Finally, if we can prove that the top bits of the result are 0's or 1's, 2158 // use this information. 2159 APInt KnownZero, KnownOne; 2160 APInt Mask = APInt::getAllOnesValue(VTBits); 2161 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 2162 2163 if (KnownZero.isNegative()) { // sign bit is 0 2164 Mask = KnownZero; 2165 } else if (KnownOne.isNegative()) { // sign bit is 1; 2166 Mask = KnownOne; 2167 } else { 2168 // Nothing known. 2169 return FirstAnswer; 2170 } 2171 2172 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 2173 // the number of identical bits in the top of the input value. 2174 Mask = ~Mask; 2175 Mask <<= Mask.getBitWidth()-VTBits; 2176 // Return # leading zeros. We use 'min' here in case Val was zero before 2177 // shifting. We don't want to return '64' as for an i32 "0". 2178 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros())); 2179} 2180 2181bool SelectionDAG::isKnownNeverNaN(SDValue Op) const { 2182 // If we're told that NaNs won't happen, assume they won't. 2183 if (FiniteOnlyFPMath()) 2184 return true; 2185 2186 // If the value is a constant, we can obviously see if it is a NaN or not. 2187 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op)) 2188 return !C->getValueAPF().isNaN(); 2189 2190 // TODO: Recognize more cases here. 2191 2192 return false; 2193} 2194 2195bool SelectionDAG::isVerifiedDebugInfoDesc(SDValue Op) const { 2196 GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op); 2197 if (!GA) return false; 2198 if (GA->getOffset() != 0) return false; 2199 GlobalVariable *GV = dyn_cast<GlobalVariable>(GA->getGlobal()); 2200 if (!GV) return false; 2201 MachineModuleInfo *MMI = getMachineModuleInfo(); 2202 return MMI && MMI->hasDebugInfo(); 2203} 2204 2205 2206/// getShuffleScalarElt - Returns the scalar element that will make up the ith 2207/// element of the result of the vector shuffle. 2208SDValue SelectionDAG::getShuffleScalarElt(const ShuffleVectorSDNode *N, 2209 unsigned i) { 2210 EVT VT = N->getValueType(0); 2211 DebugLoc dl = N->getDebugLoc(); 2212 if (N->getMaskElt(i) < 0) 2213 return getUNDEF(VT.getVectorElementType()); 2214 unsigned Index = N->getMaskElt(i); 2215 unsigned NumElems = VT.getVectorNumElements(); 2216 SDValue V = (Index < NumElems) ? N->getOperand(0) : N->getOperand(1); 2217 Index %= NumElems; 2218 2219 if (V.getOpcode() == ISD::BIT_CONVERT) { 2220 V = V.getOperand(0); 2221 EVT VVT = V.getValueType(); 2222 if (!VVT.isVector() || VVT.getVectorNumElements() != (unsigned)NumElems) 2223 return SDValue(); 2224 } 2225 if (V.getOpcode() == ISD::SCALAR_TO_VECTOR) 2226 return (Index == 0) ? V.getOperand(0) 2227 : getUNDEF(VT.getVectorElementType()); 2228 if (V.getOpcode() == ISD::BUILD_VECTOR) 2229 return V.getOperand(Index); 2230 if (const ShuffleVectorSDNode *SVN = dyn_cast<ShuffleVectorSDNode>(V)) 2231 return getShuffleScalarElt(SVN, Index); 2232 return SDValue(); 2233} 2234 2235 2236/// getNode - Gets or creates the specified node. 2237/// 2238SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) { 2239 FoldingSetNodeID ID; 2240 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0); 2241 void *IP = 0; 2242 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2243 return SDValue(E, 0); 2244 SDNode *N = NodeAllocator.Allocate<SDNode>(); 2245 new (N) SDNode(Opcode, DL, getVTList(VT)); 2246 CSEMap.InsertNode(N, IP); 2247 2248 AllNodes.push_back(N); 2249#ifndef NDEBUG 2250 VerifyNode(N); 2251#endif 2252 return SDValue(N, 0); 2253} 2254 2255SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, 2256 EVT VT, SDValue Operand) { 2257 // Constant fold unary operations with an integer constant operand. 2258 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) { 2259 const APInt &Val = C->getAPIntValue(); 2260 unsigned BitWidth = VT.getSizeInBits(); 2261 switch (Opcode) { 2262 default: break; 2263 case ISD::SIGN_EXTEND: 2264 return getConstant(APInt(Val).sextOrTrunc(BitWidth), VT); 2265 case ISD::ANY_EXTEND: 2266 case ISD::ZERO_EXTEND: 2267 case ISD::TRUNCATE: 2268 return getConstant(APInt(Val).zextOrTrunc(BitWidth), VT); 2269 case ISD::UINT_TO_FP: 2270 case ISD::SINT_TO_FP: { 2271 const uint64_t zero[] = {0, 0}; 2272 // No compile time operations on this type. 2273 if (VT==MVT::ppcf128) 2274 break; 2275 APFloat apf = APFloat(APInt(BitWidth, 2, zero)); 2276 (void)apf.convertFromAPInt(Val, 2277 Opcode==ISD::SINT_TO_FP, 2278 APFloat::rmNearestTiesToEven); 2279 return getConstantFP(apf, VT); 2280 } 2281 case ISD::BIT_CONVERT: 2282 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32) 2283 return getConstantFP(Val.bitsToFloat(), VT); 2284 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64) 2285 return getConstantFP(Val.bitsToDouble(), VT); 2286 break; 2287 case ISD::BSWAP: 2288 return getConstant(Val.byteSwap(), VT); 2289 case ISD::CTPOP: 2290 return getConstant(Val.countPopulation(), VT); 2291 case ISD::CTLZ: 2292 return getConstant(Val.countLeadingZeros(), VT); 2293 case ISD::CTTZ: 2294 return getConstant(Val.countTrailingZeros(), VT); 2295 } 2296 } 2297 2298 // Constant fold unary operations with a floating point constant operand. 2299 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) { 2300 APFloat V = C->getValueAPF(); // make copy 2301 if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) { 2302 switch (Opcode) { 2303 case ISD::FNEG: 2304 V.changeSign(); 2305 return getConstantFP(V, VT); 2306 case ISD::FABS: 2307 V.clearSign(); 2308 return getConstantFP(V, VT); 2309 case ISD::FP_ROUND: 2310 case ISD::FP_EXTEND: { 2311 bool ignored; 2312 // This can return overflow, underflow, or inexact; we don't care. 2313 // FIXME need to be more flexible about rounding mode. 2314 (void)V.convert(*EVTToAPFloatSemantics(VT), 2315 APFloat::rmNearestTiesToEven, &ignored); 2316 return getConstantFP(V, VT); 2317 } 2318 case ISD::FP_TO_SINT: 2319 case ISD::FP_TO_UINT: { 2320 integerPart x[2]; 2321 bool ignored; 2322 assert(integerPartWidth >= 64); 2323 // FIXME need to be more flexible about rounding mode. 2324 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(), 2325 Opcode==ISD::FP_TO_SINT, 2326 APFloat::rmTowardZero, &ignored); 2327 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual 2328 break; 2329 APInt api(VT.getSizeInBits(), 2, x); 2330 return getConstant(api, VT); 2331 } 2332 case ISD::BIT_CONVERT: 2333 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32) 2334 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT); 2335 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64) 2336 return getConstant(V.bitcastToAPInt().getZExtValue(), VT); 2337 break; 2338 } 2339 } 2340 } 2341 2342 unsigned OpOpcode = Operand.getNode()->getOpcode(); 2343 switch (Opcode) { 2344 case ISD::TokenFactor: 2345 case ISD::MERGE_VALUES: 2346 case ISD::CONCAT_VECTORS: 2347 return Operand; // Factor, merge or concat of one node? No need. 2348 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node"); 2349 case ISD::FP_EXTEND: 2350 assert(VT.isFloatingPoint() && 2351 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!"); 2352 if (Operand.getValueType() == VT) return Operand; // noop conversion. 2353 if (Operand.getOpcode() == ISD::UNDEF) 2354 return getUNDEF(VT); 2355 break; 2356 case ISD::SIGN_EXTEND: 2357 assert(VT.isInteger() && Operand.getValueType().isInteger() && 2358 "Invalid SIGN_EXTEND!"); 2359 if (Operand.getValueType() == VT) return Operand; // noop extension 2360 assert(Operand.getValueType().bitsLT(VT) 2361 && "Invalid sext node, dst < src!"); 2362 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 2363 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0)); 2364 break; 2365 case ISD::ZERO_EXTEND: 2366 assert(VT.isInteger() && Operand.getValueType().isInteger() && 2367 "Invalid ZERO_EXTEND!"); 2368 if (Operand.getValueType() == VT) return Operand; // noop extension 2369 assert(Operand.getValueType().bitsLT(VT) 2370 && "Invalid zext node, dst < src!"); 2371 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x) 2372 return getNode(ISD::ZERO_EXTEND, DL, VT, 2373 Operand.getNode()->getOperand(0)); 2374 break; 2375 case ISD::ANY_EXTEND: 2376 assert(VT.isInteger() && Operand.getValueType().isInteger() && 2377 "Invalid ANY_EXTEND!"); 2378 if (Operand.getValueType() == VT) return Operand; // noop extension 2379 assert(Operand.getValueType().bitsLT(VT) 2380 && "Invalid anyext node, dst < src!"); 2381 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) 2382 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x) 2383 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0)); 2384 break; 2385 case ISD::TRUNCATE: 2386 assert(VT.isInteger() && Operand.getValueType().isInteger() && 2387 "Invalid TRUNCATE!"); 2388 if (Operand.getValueType() == VT) return Operand; // noop truncate 2389 assert(Operand.getValueType().bitsGT(VT) 2390 && "Invalid truncate node, src < dst!"); 2391 if (OpOpcode == ISD::TRUNCATE) 2392 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0)); 2393 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || 2394 OpOpcode == ISD::ANY_EXTEND) { 2395 // If the source is smaller than the dest, we still need an extend. 2396 if (Operand.getNode()->getOperand(0).getValueType().bitsLT(VT)) 2397 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0)); 2398 else if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT)) 2399 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0)); 2400 else 2401 return Operand.getNode()->getOperand(0); 2402 } 2403 break; 2404 case ISD::BIT_CONVERT: 2405 // Basic sanity checking. 2406 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits() 2407 && "Cannot BIT_CONVERT between types of different sizes!"); 2408 if (VT == Operand.getValueType()) return Operand; // noop conversion. 2409 if (OpOpcode == ISD::BIT_CONVERT) // bitconv(bitconv(x)) -> bitconv(x) 2410 return getNode(ISD::BIT_CONVERT, DL, VT, Operand.getOperand(0)); 2411 if (OpOpcode == ISD::UNDEF) 2412 return getUNDEF(VT); 2413 break; 2414 case ISD::SCALAR_TO_VECTOR: 2415 assert(VT.isVector() && !Operand.getValueType().isVector() && 2416 (VT.getVectorElementType() == Operand.getValueType() || 2417 (VT.getVectorElementType().isInteger() && 2418 Operand.getValueType().isInteger() && 2419 VT.getVectorElementType().bitsLE(Operand.getValueType()))) && 2420 "Illegal SCALAR_TO_VECTOR node!"); 2421 if (OpOpcode == ISD::UNDEF) 2422 return getUNDEF(VT); 2423 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined. 2424 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT && 2425 isa<ConstantSDNode>(Operand.getOperand(1)) && 2426 Operand.getConstantOperandVal(1) == 0 && 2427 Operand.getOperand(0).getValueType() == VT) 2428 return Operand.getOperand(0); 2429 break; 2430 case ISD::FNEG: 2431 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0 2432 if (UnsafeFPMath && OpOpcode == ISD::FSUB) 2433 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1), 2434 Operand.getNode()->getOperand(0)); 2435 if (OpOpcode == ISD::FNEG) // --X -> X 2436 return Operand.getNode()->getOperand(0); 2437 break; 2438 case ISD::FABS: 2439 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X) 2440 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0)); 2441 break; 2442 } 2443 2444 SDNode *N; 2445 SDVTList VTs = getVTList(VT); 2446 if (VT != MVT::Flag) { // Don't CSE flag producing nodes 2447 FoldingSetNodeID ID; 2448 SDValue Ops[1] = { Operand }; 2449 AddNodeIDNode(ID, Opcode, VTs, Ops, 1); 2450 void *IP = 0; 2451 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2452 return SDValue(E, 0); 2453 N = NodeAllocator.Allocate<UnarySDNode>(); 2454 new (N) UnarySDNode(Opcode, DL, VTs, Operand); 2455 CSEMap.InsertNode(N, IP); 2456 } else { 2457 N = NodeAllocator.Allocate<UnarySDNode>(); 2458 new (N) UnarySDNode(Opcode, DL, VTs, Operand); 2459 } 2460 2461 AllNodes.push_back(N); 2462#ifndef NDEBUG 2463 VerifyNode(N); 2464#endif 2465 return SDValue(N, 0); 2466} 2467 2468SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, 2469 EVT VT, 2470 ConstantSDNode *Cst1, 2471 ConstantSDNode *Cst2) { 2472 const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue(); 2473 2474 switch (Opcode) { 2475 case ISD::ADD: return getConstant(C1 + C2, VT); 2476 case ISD::SUB: return getConstant(C1 - C2, VT); 2477 case ISD::MUL: return getConstant(C1 * C2, VT); 2478 case ISD::UDIV: 2479 if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT); 2480 break; 2481 case ISD::UREM: 2482 if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT); 2483 break; 2484 case ISD::SDIV: 2485 if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT); 2486 break; 2487 case ISD::SREM: 2488 if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT); 2489 break; 2490 case ISD::AND: return getConstant(C1 & C2, VT); 2491 case ISD::OR: return getConstant(C1 | C2, VT); 2492 case ISD::XOR: return getConstant(C1 ^ C2, VT); 2493 case ISD::SHL: return getConstant(C1 << C2, VT); 2494 case ISD::SRL: return getConstant(C1.lshr(C2), VT); 2495 case ISD::SRA: return getConstant(C1.ashr(C2), VT); 2496 case ISD::ROTL: return getConstant(C1.rotl(C2), VT); 2497 case ISD::ROTR: return getConstant(C1.rotr(C2), VT); 2498 default: break; 2499 } 2500 2501 return SDValue(); 2502} 2503 2504SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 2505 SDValue N1, SDValue N2) { 2506 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 2507 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode()); 2508 switch (Opcode) { 2509 default: break; 2510 case ISD::TokenFactor: 2511 assert(VT == MVT::Other && N1.getValueType() == MVT::Other && 2512 N2.getValueType() == MVT::Other && "Invalid token factor!"); 2513 // Fold trivial token factors. 2514 if (N1.getOpcode() == ISD::EntryToken) return N2; 2515 if (N2.getOpcode() == ISD::EntryToken) return N1; 2516 if (N1 == N2) return N1; 2517 break; 2518 case ISD::CONCAT_VECTORS: 2519 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to 2520 // one big BUILD_VECTOR. 2521 if (N1.getOpcode() == ISD::BUILD_VECTOR && 2522 N2.getOpcode() == ISD::BUILD_VECTOR) { 2523 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(), N1.getNode()->op_end()); 2524 Elts.insert(Elts.end(), N2.getNode()->op_begin(), N2.getNode()->op_end()); 2525 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size()); 2526 } 2527 break; 2528 case ISD::AND: 2529 assert(VT.isInteger() && N1.getValueType() == N2.getValueType() && 2530 N1.getValueType() == VT && "Binary operator types must match!"); 2531 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's 2532 // worth handling here. 2533 if (N2C && N2C->isNullValue()) 2534 return N2; 2535 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X 2536 return N1; 2537 break; 2538 case ISD::OR: 2539 case ISD::XOR: 2540 case ISD::ADD: 2541 case ISD::SUB: 2542 assert(VT.isInteger() && N1.getValueType() == N2.getValueType() && 2543 N1.getValueType() == VT && "Binary operator types must match!"); 2544 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so 2545 // it's worth handling here. 2546 if (N2C && N2C->isNullValue()) 2547 return N1; 2548 break; 2549 case ISD::UDIV: 2550 case ISD::UREM: 2551 case ISD::MULHU: 2552 case ISD::MULHS: 2553 case ISD::MUL: 2554 case ISD::SDIV: 2555 case ISD::SREM: 2556 assert(VT.isInteger() && "This operator does not apply to FP types!"); 2557 // fall through 2558 case ISD::FADD: 2559 case ISD::FSUB: 2560 case ISD::FMUL: 2561 case ISD::FDIV: 2562 case ISD::FREM: 2563 if (UnsafeFPMath) { 2564 if (Opcode == ISD::FADD) { 2565 // 0+x --> x 2566 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) 2567 if (CFP->getValueAPF().isZero()) 2568 return N2; 2569 // x+0 --> x 2570 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2)) 2571 if (CFP->getValueAPF().isZero()) 2572 return N1; 2573 } else if (Opcode == ISD::FSUB) { 2574 // x-0 --> x 2575 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2)) 2576 if (CFP->getValueAPF().isZero()) 2577 return N1; 2578 } 2579 } 2580 assert(N1.getValueType() == N2.getValueType() && 2581 N1.getValueType() == VT && "Binary operator types must match!"); 2582 break; 2583 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match. 2584 assert(N1.getValueType() == VT && 2585 N1.getValueType().isFloatingPoint() && 2586 N2.getValueType().isFloatingPoint() && 2587 "Invalid FCOPYSIGN!"); 2588 break; 2589 case ISD::SHL: 2590 case ISD::SRA: 2591 case ISD::SRL: 2592 case ISD::ROTL: 2593 case ISD::ROTR: 2594 assert(VT == N1.getValueType() && 2595 "Shift operators return type must be the same as their first arg"); 2596 assert(VT.isInteger() && N2.getValueType().isInteger() && 2597 "Shifts only work on integers"); 2598 2599 // Always fold shifts of i1 values so the code generator doesn't need to 2600 // handle them. Since we know the size of the shift has to be less than the 2601 // size of the value, the shift/rotate count is guaranteed to be zero. 2602 if (VT == MVT::i1) 2603 return N1; 2604 break; 2605 case ISD::FP_ROUND_INREG: { 2606 EVT EVT = cast<VTSDNode>(N2)->getVT(); 2607 assert(VT == N1.getValueType() && "Not an inreg round!"); 2608 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() && 2609 "Cannot FP_ROUND_INREG integer types"); 2610 assert(EVT.bitsLE(VT) && "Not rounding down!"); 2611 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding. 2612 break; 2613 } 2614 case ISD::FP_ROUND: 2615 assert(VT.isFloatingPoint() && 2616 N1.getValueType().isFloatingPoint() && 2617 VT.bitsLE(N1.getValueType()) && 2618 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!"); 2619 if (N1.getValueType() == VT) return N1; // noop conversion. 2620 break; 2621 case ISD::AssertSext: 2622 case ISD::AssertZext: { 2623 EVT EVT = cast<VTSDNode>(N2)->getVT(); 2624 assert(VT == N1.getValueType() && "Not an inreg extend!"); 2625 assert(VT.isInteger() && EVT.isInteger() && 2626 "Cannot *_EXTEND_INREG FP types"); 2627 assert(EVT.bitsLE(VT) && "Not extending!"); 2628 if (VT == EVT) return N1; // noop assertion. 2629 break; 2630 } 2631 case ISD::SIGN_EXTEND_INREG: { 2632 EVT EVT = cast<VTSDNode>(N2)->getVT(); 2633 assert(VT == N1.getValueType() && "Not an inreg extend!"); 2634 assert(VT.isInteger() && EVT.isInteger() && 2635 "Cannot *_EXTEND_INREG FP types"); 2636 assert(EVT.bitsLE(VT) && "Not extending!"); 2637 if (EVT == VT) return N1; // Not actually extending 2638 2639 if (N1C) { 2640 APInt Val = N1C->getAPIntValue(); 2641 unsigned FromBits = cast<VTSDNode>(N2)->getVT().getSizeInBits(); 2642 Val <<= Val.getBitWidth()-FromBits; 2643 Val = Val.ashr(Val.getBitWidth()-FromBits); 2644 return getConstant(Val, VT); 2645 } 2646 break; 2647 } 2648 case ISD::EXTRACT_VECTOR_ELT: 2649 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF. 2650 if (N1.getOpcode() == ISD::UNDEF) 2651 return getUNDEF(VT); 2652 2653 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is 2654 // expanding copies of large vectors from registers. 2655 if (N2C && 2656 N1.getOpcode() == ISD::CONCAT_VECTORS && 2657 N1.getNumOperands() > 0) { 2658 unsigned Factor = 2659 N1.getOperand(0).getValueType().getVectorNumElements(); 2660 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, 2661 N1.getOperand(N2C->getZExtValue() / Factor), 2662 getConstant(N2C->getZExtValue() % Factor, 2663 N2.getValueType())); 2664 } 2665 2666 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is 2667 // expanding large vector constants. 2668 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) { 2669 SDValue Elt = N1.getOperand(N2C->getZExtValue()); 2670 EVT VEltTy = N1.getValueType().getVectorElementType(); 2671 if (Elt.getValueType() != VEltTy) { 2672 // If the vector element type is not legal, the BUILD_VECTOR operands 2673 // are promoted and implicitly truncated. Make that explicit here. 2674 Elt = getNode(ISD::TRUNCATE, DL, VEltTy, Elt); 2675 } 2676 if (VT != VEltTy) { 2677 // If the vector element type is not legal, the EXTRACT_VECTOR_ELT 2678 // result is implicitly extended. 2679 Elt = getNode(ISD::ANY_EXTEND, DL, VT, Elt); 2680 } 2681 return Elt; 2682 } 2683 2684 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector 2685 // operations are lowered to scalars. 2686 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) { 2687 // If the indices are the same, return the inserted element. 2688 if (N1.getOperand(2) == N2) 2689 return N1.getOperand(1); 2690 // If the indices are known different, extract the element from 2691 // the original vector. 2692 else if (isa<ConstantSDNode>(N1.getOperand(2)) && 2693 isa<ConstantSDNode>(N2)) 2694 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2); 2695 } 2696 break; 2697 case ISD::EXTRACT_ELEMENT: 2698 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!"); 2699 assert(!N1.getValueType().isVector() && !VT.isVector() && 2700 (N1.getValueType().isInteger() == VT.isInteger()) && 2701 "Wrong types for EXTRACT_ELEMENT!"); 2702 2703 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding 2704 // 64-bit integers into 32-bit parts. Instead of building the extract of 2705 // the BUILD_PAIR, only to have legalize rip it apart, just do it now. 2706 if (N1.getOpcode() == ISD::BUILD_PAIR) 2707 return N1.getOperand(N2C->getZExtValue()); 2708 2709 // EXTRACT_ELEMENT of a constant int is also very common. 2710 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) { 2711 unsigned ElementSize = VT.getSizeInBits(); 2712 unsigned Shift = ElementSize * N2C->getZExtValue(); 2713 APInt ShiftedVal = C->getAPIntValue().lshr(Shift); 2714 return getConstant(ShiftedVal.trunc(ElementSize), VT); 2715 } 2716 break; 2717 case ISD::EXTRACT_SUBVECTOR: 2718 if (N1.getValueType() == VT) // Trivial extraction. 2719 return N1; 2720 break; 2721 } 2722 2723 if (N1C) { 2724 if (N2C) { 2725 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C); 2726 if (SV.getNode()) return SV; 2727 } else { // Cannonicalize constant to RHS if commutative 2728 if (isCommutativeBinOp(Opcode)) { 2729 std::swap(N1C, N2C); 2730 std::swap(N1, N2); 2731 } 2732 } 2733 } 2734 2735 // Constant fold FP operations. 2736 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode()); 2737 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode()); 2738 if (N1CFP) { 2739 if (!N2CFP && isCommutativeBinOp(Opcode)) { 2740 // Cannonicalize constant to RHS if commutative 2741 std::swap(N1CFP, N2CFP); 2742 std::swap(N1, N2); 2743 } else if (N2CFP && VT != MVT::ppcf128) { 2744 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF(); 2745 APFloat::opStatus s; 2746 switch (Opcode) { 2747 case ISD::FADD: 2748 s = V1.add(V2, APFloat::rmNearestTiesToEven); 2749 if (s != APFloat::opInvalidOp) 2750 return getConstantFP(V1, VT); 2751 break; 2752 case ISD::FSUB: 2753 s = V1.subtract(V2, APFloat::rmNearestTiesToEven); 2754 if (s!=APFloat::opInvalidOp) 2755 return getConstantFP(V1, VT); 2756 break; 2757 case ISD::FMUL: 2758 s = V1.multiply(V2, APFloat::rmNearestTiesToEven); 2759 if (s!=APFloat::opInvalidOp) 2760 return getConstantFP(V1, VT); 2761 break; 2762 case ISD::FDIV: 2763 s = V1.divide(V2, APFloat::rmNearestTiesToEven); 2764 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero) 2765 return getConstantFP(V1, VT); 2766 break; 2767 case ISD::FREM : 2768 s = V1.mod(V2, APFloat::rmNearestTiesToEven); 2769 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero) 2770 return getConstantFP(V1, VT); 2771 break; 2772 case ISD::FCOPYSIGN: 2773 V1.copySign(V2); 2774 return getConstantFP(V1, VT); 2775 default: break; 2776 } 2777 } 2778 } 2779 2780 // Canonicalize an UNDEF to the RHS, even over a constant. 2781 if (N1.getOpcode() == ISD::UNDEF) { 2782 if (isCommutativeBinOp(Opcode)) { 2783 std::swap(N1, N2); 2784 } else { 2785 switch (Opcode) { 2786 case ISD::FP_ROUND_INREG: 2787 case ISD::SIGN_EXTEND_INREG: 2788 case ISD::SUB: 2789 case ISD::FSUB: 2790 case ISD::FDIV: 2791 case ISD::FREM: 2792 case ISD::SRA: 2793 return N1; // fold op(undef, arg2) -> undef 2794 case ISD::UDIV: 2795 case ISD::SDIV: 2796 case ISD::UREM: 2797 case ISD::SREM: 2798 case ISD::SRL: 2799 case ISD::SHL: 2800 if (!VT.isVector()) 2801 return getConstant(0, VT); // fold op(undef, arg2) -> 0 2802 // For vectors, we can't easily build an all zero vector, just return 2803 // the LHS. 2804 return N2; 2805 } 2806 } 2807 } 2808 2809 // Fold a bunch of operators when the RHS is undef. 2810 if (N2.getOpcode() == ISD::UNDEF) { 2811 switch (Opcode) { 2812 case ISD::XOR: 2813 if (N1.getOpcode() == ISD::UNDEF) 2814 // Handle undef ^ undef -> 0 special case. This is a common 2815 // idiom (misuse). 2816 return getConstant(0, VT); 2817 // fallthrough 2818 case ISD::ADD: 2819 case ISD::ADDC: 2820 case ISD::ADDE: 2821 case ISD::SUB: 2822 case ISD::UDIV: 2823 case ISD::SDIV: 2824 case ISD::UREM: 2825 case ISD::SREM: 2826 return N2; // fold op(arg1, undef) -> undef 2827 case ISD::FADD: 2828 case ISD::FSUB: 2829 case ISD::FMUL: 2830 case ISD::FDIV: 2831 case ISD::FREM: 2832 if (UnsafeFPMath) 2833 return N2; 2834 break; 2835 case ISD::MUL: 2836 case ISD::AND: 2837 case ISD::SRL: 2838 case ISD::SHL: 2839 if (!VT.isVector()) 2840 return getConstant(0, VT); // fold op(arg1, undef) -> 0 2841 // For vectors, we can't easily build an all zero vector, just return 2842 // the LHS. 2843 return N1; 2844 case ISD::OR: 2845 if (!VT.isVector()) 2846 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT); 2847 // For vectors, we can't easily build an all one vector, just return 2848 // the LHS. 2849 return N1; 2850 case ISD::SRA: 2851 return N1; 2852 } 2853 } 2854 2855 // Memoize this node if possible. 2856 SDNode *N; 2857 SDVTList VTs = getVTList(VT); 2858 if (VT != MVT::Flag) { 2859 SDValue Ops[] = { N1, N2 }; 2860 FoldingSetNodeID ID; 2861 AddNodeIDNode(ID, Opcode, VTs, Ops, 2); 2862 void *IP = 0; 2863 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2864 return SDValue(E, 0); 2865 N = NodeAllocator.Allocate<BinarySDNode>(); 2866 new (N) BinarySDNode(Opcode, DL, VTs, N1, N2); 2867 CSEMap.InsertNode(N, IP); 2868 } else { 2869 N = NodeAllocator.Allocate<BinarySDNode>(); 2870 new (N) BinarySDNode(Opcode, DL, VTs, N1, N2); 2871 } 2872 2873 AllNodes.push_back(N); 2874#ifndef NDEBUG 2875 VerifyNode(N); 2876#endif 2877 return SDValue(N, 0); 2878} 2879 2880SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 2881 SDValue N1, SDValue N2, SDValue N3) { 2882 // Perform various simplifications. 2883 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 2884 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode()); 2885 switch (Opcode) { 2886 case ISD::CONCAT_VECTORS: 2887 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to 2888 // one big BUILD_VECTOR. 2889 if (N1.getOpcode() == ISD::BUILD_VECTOR && 2890 N2.getOpcode() == ISD::BUILD_VECTOR && 2891 N3.getOpcode() == ISD::BUILD_VECTOR) { 2892 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(), N1.getNode()->op_end()); 2893 Elts.insert(Elts.end(), N2.getNode()->op_begin(), N2.getNode()->op_end()); 2894 Elts.insert(Elts.end(), N3.getNode()->op_begin(), N3.getNode()->op_end()); 2895 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size()); 2896 } 2897 break; 2898 case ISD::SETCC: { 2899 // Use FoldSetCC to simplify SETCC's. 2900 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL); 2901 if (Simp.getNode()) return Simp; 2902 break; 2903 } 2904 case ISD::SELECT: 2905 if (N1C) { 2906 if (N1C->getZExtValue()) 2907 return N2; // select true, X, Y -> X 2908 else 2909 return N3; // select false, X, Y -> Y 2910 } 2911 2912 if (N2 == N3) return N2; // select C, X, X -> X 2913 break; 2914 case ISD::BRCOND: 2915 if (N2C) { 2916 if (N2C->getZExtValue()) // Unconditional branch 2917 return getNode(ISD::BR, DL, MVT::Other, N1, N3); 2918 else 2919 return N1; // Never-taken branch 2920 } 2921 break; 2922 case ISD::VECTOR_SHUFFLE: 2923 llvm_unreachable("should use getVectorShuffle constructor!"); 2924 break; 2925 case ISD::BIT_CONVERT: 2926 // Fold bit_convert nodes from a type to themselves. 2927 if (N1.getValueType() == VT) 2928 return N1; 2929 break; 2930 } 2931 2932 // Memoize node if it doesn't produce a flag. 2933 SDNode *N; 2934 SDVTList VTs = getVTList(VT); 2935 if (VT != MVT::Flag) { 2936 SDValue Ops[] = { N1, N2, N3 }; 2937 FoldingSetNodeID ID; 2938 AddNodeIDNode(ID, Opcode, VTs, Ops, 3); 2939 void *IP = 0; 2940 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2941 return SDValue(E, 0); 2942 N = NodeAllocator.Allocate<TernarySDNode>(); 2943 new (N) TernarySDNode(Opcode, DL, VTs, N1, N2, N3); 2944 CSEMap.InsertNode(N, IP); 2945 } else { 2946 N = NodeAllocator.Allocate<TernarySDNode>(); 2947 new (N) TernarySDNode(Opcode, DL, VTs, N1, N2, N3); 2948 } 2949 AllNodes.push_back(N); 2950#ifndef NDEBUG 2951 VerifyNode(N); 2952#endif 2953 return SDValue(N, 0); 2954} 2955 2956SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 2957 SDValue N1, SDValue N2, SDValue N3, 2958 SDValue N4) { 2959 SDValue Ops[] = { N1, N2, N3, N4 }; 2960 return getNode(Opcode, DL, VT, Ops, 4); 2961} 2962 2963SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 2964 SDValue N1, SDValue N2, SDValue N3, 2965 SDValue N4, SDValue N5) { 2966 SDValue Ops[] = { N1, N2, N3, N4, N5 }; 2967 return getNode(Opcode, DL, VT, Ops, 5); 2968} 2969 2970/// getStackArgumentTokenFactor - Compute a TokenFactor to force all 2971/// the incoming stack arguments to be loaded from the stack. 2972SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) { 2973 SmallVector<SDValue, 8> ArgChains; 2974 2975 // Include the original chain at the beginning of the list. When this is 2976 // used by target LowerCall hooks, this helps legalize find the 2977 // CALLSEQ_BEGIN node. 2978 ArgChains.push_back(Chain); 2979 2980 // Add a chain value for each stack argument. 2981 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(), 2982 UE = getEntryNode().getNode()->use_end(); U != UE; ++U) 2983 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U)) 2984 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr())) 2985 if (FI->getIndex() < 0) 2986 ArgChains.push_back(SDValue(L, 1)); 2987 2988 // Build a tokenfactor for all the chains. 2989 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other, 2990 &ArgChains[0], ArgChains.size()); 2991} 2992 2993/// getMemsetValue - Vectorized representation of the memset value 2994/// operand. 2995static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG, 2996 DebugLoc dl) { 2997 unsigned NumBits = VT.isVector() ? 2998 VT.getVectorElementType().getSizeInBits() : VT.getSizeInBits(); 2999 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) { 3000 APInt Val = APInt(NumBits, C->getZExtValue() & 255); 3001 unsigned Shift = 8; 3002 for (unsigned i = NumBits; i > 8; i >>= 1) { 3003 Val = (Val << Shift) | Val; 3004 Shift <<= 1; 3005 } 3006 if (VT.isInteger()) 3007 return DAG.getConstant(Val, VT); 3008 return DAG.getConstantFP(APFloat(Val), VT); 3009 } 3010 3011 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 3012 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value); 3013 unsigned Shift = 8; 3014 for (unsigned i = NumBits; i > 8; i >>= 1) { 3015 Value = DAG.getNode(ISD::OR, dl, VT, 3016 DAG.getNode(ISD::SHL, dl, VT, Value, 3017 DAG.getConstant(Shift, 3018 TLI.getShiftAmountTy())), 3019 Value); 3020 Shift <<= 1; 3021 } 3022 3023 return Value; 3024} 3025 3026/// getMemsetStringVal - Similar to getMemsetValue. Except this is only 3027/// used when a memcpy is turned into a memset when the source is a constant 3028/// string ptr. 3029static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG, 3030 const TargetLowering &TLI, 3031 std::string &Str, unsigned Offset) { 3032 // Handle vector with all elements zero. 3033 if (Str.empty()) { 3034 if (VT.isInteger()) 3035 return DAG.getConstant(0, VT); 3036 unsigned NumElts = VT.getVectorNumElements(); 3037 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64; 3038 return DAG.getNode(ISD::BIT_CONVERT, dl, VT, 3039 DAG.getConstant(0, 3040 EVT::getVectorVT(*DAG.getContext(), EltVT, NumElts))); 3041 } 3042 3043 assert(!VT.isVector() && "Can't handle vector type here!"); 3044 unsigned NumBits = VT.getSizeInBits(); 3045 unsigned MSB = NumBits / 8; 3046 uint64_t Val = 0; 3047 if (TLI.isLittleEndian()) 3048 Offset = Offset + MSB - 1; 3049 for (unsigned i = 0; i != MSB; ++i) { 3050 Val = (Val << 8) | (unsigned char)Str[Offset]; 3051 Offset += TLI.isLittleEndian() ? -1 : 1; 3052 } 3053 return DAG.getConstant(Val, VT); 3054} 3055 3056/// getMemBasePlusOffset - Returns base and offset node for the 3057/// 3058static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, 3059 SelectionDAG &DAG) { 3060 EVT VT = Base.getValueType(); 3061 return DAG.getNode(ISD::ADD, Base.getDebugLoc(), 3062 VT, Base, DAG.getConstant(Offset, VT)); 3063} 3064 3065/// isMemSrcFromString - Returns true if memcpy source is a string constant. 3066/// 3067static bool isMemSrcFromString(SDValue Src, std::string &Str) { 3068 unsigned SrcDelta = 0; 3069 GlobalAddressSDNode *G = NULL; 3070 if (Src.getOpcode() == ISD::GlobalAddress) 3071 G = cast<GlobalAddressSDNode>(Src); 3072 else if (Src.getOpcode() == ISD::ADD && 3073 Src.getOperand(0).getOpcode() == ISD::GlobalAddress && 3074 Src.getOperand(1).getOpcode() == ISD::Constant) { 3075 G = cast<GlobalAddressSDNode>(Src.getOperand(0)); 3076 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue(); 3077 } 3078 if (!G) 3079 return false; 3080 3081 GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal()); 3082 if (GV && GetConstantStringInfo(GV, Str, SrcDelta, false)) 3083 return true; 3084 3085 return false; 3086} 3087 3088/// MeetsMaxMemopRequirement - Determines if the number of memory ops required 3089/// to replace the memset / memcpy is below the threshold. It also returns the 3090/// types of the sequence of memory ops to perform memset / memcpy. 3091static 3092bool MeetsMaxMemopRequirement(std::vector<EVT> &MemOps, 3093 SDValue Dst, SDValue Src, 3094 unsigned Limit, uint64_t Size, unsigned &Align, 3095 std::string &Str, bool &isSrcStr, 3096 SelectionDAG &DAG, 3097 const TargetLowering &TLI) { 3098 isSrcStr = isMemSrcFromString(Src, Str); 3099 bool isSrcConst = isa<ConstantSDNode>(Src); 3100 EVT VT = TLI.getOptimalMemOpType(Size, Align, isSrcConst, isSrcStr, DAG); 3101 bool AllowUnalign = TLI.allowsUnalignedMemoryAccesses(VT); 3102 if (VT != MVT::iAny) { 3103 const Type *Ty = VT.getTypeForEVT(*DAG.getContext()); 3104 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty); 3105 // If source is a string constant, this will require an unaligned load. 3106 if (NewAlign > Align && (isSrcConst || AllowUnalign)) { 3107 if (Dst.getOpcode() != ISD::FrameIndex) { 3108 // Can't change destination alignment. It requires a unaligned store. 3109 if (AllowUnalign) 3110 VT = MVT::iAny; 3111 } else { 3112 int FI = cast<FrameIndexSDNode>(Dst)->getIndex(); 3113 MachineFrameInfo *MFI = DAG.getMachineFunction().getFrameInfo(); 3114 if (MFI->isFixedObjectIndex(FI)) { 3115 // Can't change destination alignment. It requires a unaligned store. 3116 if (AllowUnalign) 3117 VT = MVT::iAny; 3118 } else { 3119 // Give the stack frame object a larger alignment if needed. 3120 if (MFI->getObjectAlignment(FI) < NewAlign) 3121 MFI->setObjectAlignment(FI, NewAlign); 3122 Align = NewAlign; 3123 } 3124 } 3125 } 3126 } 3127 3128 if (VT == MVT::iAny) { 3129 if (TLI.allowsUnalignedMemoryAccesses(MVT::i64)) { 3130 VT = MVT::i64; 3131 } else { 3132 switch (Align & 7) { 3133 case 0: VT = MVT::i64; break; 3134 case 4: VT = MVT::i32; break; 3135 case 2: VT = MVT::i16; break; 3136 default: VT = MVT::i8; break; 3137 } 3138 } 3139 3140 MVT LVT = MVT::i64; 3141 while (!TLI.isTypeLegal(LVT)) 3142 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1); 3143 assert(LVT.isInteger()); 3144 3145 if (VT.bitsGT(LVT)) 3146 VT = LVT; 3147 } 3148 3149 unsigned NumMemOps = 0; 3150 while (Size != 0) { 3151 unsigned VTSize = VT.getSizeInBits() / 8; 3152 while (VTSize > Size) { 3153 // For now, only use non-vector load / store's for the left-over pieces. 3154 if (VT.isVector()) { 3155 VT = MVT::i64; 3156 while (!TLI.isTypeLegal(VT)) 3157 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1); 3158 VTSize = VT.getSizeInBits() / 8; 3159 } else { 3160 // This can result in a type that is not legal on the target, e.g. 3161 // 1 or 2 bytes on PPC. 3162 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1); 3163 VTSize >>= 1; 3164 } 3165 } 3166 3167 if (++NumMemOps > Limit) 3168 return false; 3169 MemOps.push_back(VT); 3170 Size -= VTSize; 3171 } 3172 3173 return true; 3174} 3175 3176static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl, 3177 SDValue Chain, SDValue Dst, 3178 SDValue Src, uint64_t Size, 3179 unsigned Align, bool AlwaysInline, 3180 const Value *DstSV, uint64_t DstSVOff, 3181 const Value *SrcSV, uint64_t SrcSVOff){ 3182 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 3183 3184 // Expand memcpy to a series of load and store ops if the size operand falls 3185 // below a certain threshold. 3186 std::vector<EVT> MemOps; 3187 uint64_t Limit = -1ULL; 3188 if (!AlwaysInline) 3189 Limit = TLI.getMaxStoresPerMemcpy(); 3190 unsigned DstAlign = Align; // Destination alignment can change. 3191 std::string Str; 3192 bool CopyFromStr; 3193 if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign, 3194 Str, CopyFromStr, DAG, TLI)) 3195 return SDValue(); 3196 3197 3198 bool isZeroStr = CopyFromStr && Str.empty(); 3199 SmallVector<SDValue, 8> OutChains; 3200 unsigned NumMemOps = MemOps.size(); 3201 uint64_t SrcOff = 0, DstOff = 0; 3202 for (unsigned i = 0; i != NumMemOps; ++i) { 3203 EVT VT = MemOps[i]; 3204 unsigned VTSize = VT.getSizeInBits() / 8; 3205 SDValue Value, Store; 3206 3207 if (CopyFromStr && (isZeroStr || !VT.isVector())) { 3208 // It's unlikely a store of a vector immediate can be done in a single 3209 // instruction. It would require a load from a constantpool first. 3210 // We also handle store a vector with all zero's. 3211 // FIXME: Handle other cases where store of vector immediate is done in 3212 // a single instruction. 3213 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str, SrcOff); 3214 Store = DAG.getStore(Chain, dl, Value, 3215 getMemBasePlusOffset(Dst, DstOff, DAG), 3216 DstSV, DstSVOff + DstOff, false, DstAlign); 3217 } else { 3218 // The type might not be legal for the target. This should only happen 3219 // if the type is smaller than a legal type, as on PPC, so the right 3220 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify 3221 // to Load/Store if NVT==VT. 3222 // FIXME does the case above also need this? 3223 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT); 3224 assert(NVT.bitsGE(VT)); 3225 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain, 3226 getMemBasePlusOffset(Src, SrcOff, DAG), 3227 SrcSV, SrcSVOff + SrcOff, VT, false, Align); 3228 Store = DAG.getTruncStore(Chain, dl, Value, 3229 getMemBasePlusOffset(Dst, DstOff, DAG), 3230 DstSV, DstSVOff + DstOff, VT, false, DstAlign); 3231 } 3232 OutChains.push_back(Store); 3233 SrcOff += VTSize; 3234 DstOff += VTSize; 3235 } 3236 3237 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 3238 &OutChains[0], OutChains.size()); 3239} 3240 3241static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl, 3242 SDValue Chain, SDValue Dst, 3243 SDValue Src, uint64_t Size, 3244 unsigned Align, bool AlwaysInline, 3245 const Value *DstSV, uint64_t DstSVOff, 3246 const Value *SrcSV, uint64_t SrcSVOff){ 3247 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 3248 3249 // Expand memmove to a series of load and store ops if the size operand falls 3250 // below a certain threshold. 3251 std::vector<EVT> MemOps; 3252 uint64_t Limit = -1ULL; 3253 if (!AlwaysInline) 3254 Limit = TLI.getMaxStoresPerMemmove(); 3255 unsigned DstAlign = Align; // Destination alignment can change. 3256 std::string Str; 3257 bool CopyFromStr; 3258 if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign, 3259 Str, CopyFromStr, DAG, TLI)) 3260 return SDValue(); 3261 3262 uint64_t SrcOff = 0, DstOff = 0; 3263 3264 SmallVector<SDValue, 8> LoadValues; 3265 SmallVector<SDValue, 8> LoadChains; 3266 SmallVector<SDValue, 8> OutChains; 3267 unsigned NumMemOps = MemOps.size(); 3268 for (unsigned i = 0; i < NumMemOps; i++) { 3269 EVT VT = MemOps[i]; 3270 unsigned VTSize = VT.getSizeInBits() / 8; 3271 SDValue Value, Store; 3272 3273 Value = DAG.getLoad(VT, dl, Chain, 3274 getMemBasePlusOffset(Src, SrcOff, DAG), 3275 SrcSV, SrcSVOff + SrcOff, false, Align); 3276 LoadValues.push_back(Value); 3277 LoadChains.push_back(Value.getValue(1)); 3278 SrcOff += VTSize; 3279 } 3280 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 3281 &LoadChains[0], LoadChains.size()); 3282 OutChains.clear(); 3283 for (unsigned i = 0; i < NumMemOps; i++) { 3284 EVT VT = MemOps[i]; 3285 unsigned VTSize = VT.getSizeInBits() / 8; 3286 SDValue Value, Store; 3287 3288 Store = DAG.getStore(Chain, dl, LoadValues[i], 3289 getMemBasePlusOffset(Dst, DstOff, DAG), 3290 DstSV, DstSVOff + DstOff, false, DstAlign); 3291 OutChains.push_back(Store); 3292 DstOff += VTSize; 3293 } 3294 3295 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 3296 &OutChains[0], OutChains.size()); 3297} 3298 3299static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl, 3300 SDValue Chain, SDValue Dst, 3301 SDValue Src, uint64_t Size, 3302 unsigned Align, 3303 const Value *DstSV, uint64_t DstSVOff) { 3304 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 3305 3306 // Expand memset to a series of load/store ops if the size operand 3307 // falls below a certain threshold. 3308 std::vector<EVT> MemOps; 3309 std::string Str; 3310 bool CopyFromStr; 3311 if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, TLI.getMaxStoresPerMemset(), 3312 Size, Align, Str, CopyFromStr, DAG, TLI)) 3313 return SDValue(); 3314 3315 SmallVector<SDValue, 8> OutChains; 3316 uint64_t DstOff = 0; 3317 3318 unsigned NumMemOps = MemOps.size(); 3319 for (unsigned i = 0; i < NumMemOps; i++) { 3320 EVT VT = MemOps[i]; 3321 unsigned VTSize = VT.getSizeInBits() / 8; 3322 SDValue Value = getMemsetValue(Src, VT, DAG, dl); 3323 SDValue Store = DAG.getStore(Chain, dl, Value, 3324 getMemBasePlusOffset(Dst, DstOff, DAG), 3325 DstSV, DstSVOff + DstOff); 3326 OutChains.push_back(Store); 3327 DstOff += VTSize; 3328 } 3329 3330 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 3331 &OutChains[0], OutChains.size()); 3332} 3333 3334SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, 3335 SDValue Src, SDValue Size, 3336 unsigned Align, bool AlwaysInline, 3337 const Value *DstSV, uint64_t DstSVOff, 3338 const Value *SrcSV, uint64_t SrcSVOff) { 3339 3340 // Check to see if we should lower the memcpy to loads and stores first. 3341 // For cases within the target-specified limits, this is the best choice. 3342 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size); 3343 if (ConstantSize) { 3344 // Memcpy with size zero? Just return the original chain. 3345 if (ConstantSize->isNullValue()) 3346 return Chain; 3347 3348 SDValue Result = 3349 getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src, 3350 ConstantSize->getZExtValue(), 3351 Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff); 3352 if (Result.getNode()) 3353 return Result; 3354 } 3355 3356 // Then check to see if we should lower the memcpy with target-specific 3357 // code. If the target chooses to do this, this is the next best. 3358 SDValue Result = 3359 TLI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align, 3360 AlwaysInline, 3361 DstSV, DstSVOff, SrcSV, SrcSVOff); 3362 if (Result.getNode()) 3363 return Result; 3364 3365 // If we really need inline code and the target declined to provide it, 3366 // use a (potentially long) sequence of loads and stores. 3367 if (AlwaysInline) { 3368 assert(ConstantSize && "AlwaysInline requires a constant size!"); 3369 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src, 3370 ConstantSize->getZExtValue(), Align, true, 3371 DstSV, DstSVOff, SrcSV, SrcSVOff); 3372 } 3373 3374 // Emit a library call. 3375 TargetLowering::ArgListTy Args; 3376 TargetLowering::ArgListEntry Entry; 3377 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext()); 3378 Entry.Node = Dst; Args.push_back(Entry); 3379 Entry.Node = Src; Args.push_back(Entry); 3380 Entry.Node = Size; Args.push_back(Entry); 3381 // FIXME: pass in DebugLoc 3382 std::pair<SDValue,SDValue> CallResult = 3383 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()), 3384 false, false, false, false, 0, 3385 TLI.getLibcallCallingConv(RTLIB::MEMCPY), false, 3386 /*isReturnValueUsed=*/false, 3387 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY), 3388 TLI.getPointerTy()), 3389 Args, *this, dl); 3390 return CallResult.second; 3391} 3392 3393SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, 3394 SDValue Src, SDValue Size, 3395 unsigned Align, 3396 const Value *DstSV, uint64_t DstSVOff, 3397 const Value *SrcSV, uint64_t SrcSVOff) { 3398 3399 // Check to see if we should lower the memmove to loads and stores first. 3400 // For cases within the target-specified limits, this is the best choice. 3401 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size); 3402 if (ConstantSize) { 3403 // Memmove with size zero? Just return the original chain. 3404 if (ConstantSize->isNullValue()) 3405 return Chain; 3406 3407 SDValue Result = 3408 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src, 3409 ConstantSize->getZExtValue(), 3410 Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff); 3411 if (Result.getNode()) 3412 return Result; 3413 } 3414 3415 // Then check to see if we should lower the memmove with target-specific 3416 // code. If the target chooses to do this, this is the next best. 3417 SDValue Result = 3418 TLI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, 3419 DstSV, DstSVOff, SrcSV, SrcSVOff); 3420 if (Result.getNode()) 3421 return Result; 3422 3423 // Emit a library call. 3424 TargetLowering::ArgListTy Args; 3425 TargetLowering::ArgListEntry Entry; 3426 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext()); 3427 Entry.Node = Dst; Args.push_back(Entry); 3428 Entry.Node = Src; Args.push_back(Entry); 3429 Entry.Node = Size; Args.push_back(Entry); 3430 // FIXME: pass in DebugLoc 3431 std::pair<SDValue,SDValue> CallResult = 3432 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()), 3433 false, false, false, false, 0, 3434 TLI.getLibcallCallingConv(RTLIB::MEMMOVE), false, 3435 /*isReturnValueUsed=*/false, 3436 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE), 3437 TLI.getPointerTy()), 3438 Args, *this, dl); 3439 return CallResult.second; 3440} 3441 3442SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, 3443 SDValue Src, SDValue Size, 3444 unsigned Align, 3445 const Value *DstSV, uint64_t DstSVOff) { 3446 3447 // Check to see if we should lower the memset to stores first. 3448 // For cases within the target-specified limits, this is the best choice. 3449 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size); 3450 if (ConstantSize) { 3451 // Memset with size zero? Just return the original chain. 3452 if (ConstantSize->isNullValue()) 3453 return Chain; 3454 3455 SDValue Result = 3456 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(), 3457 Align, DstSV, DstSVOff); 3458 if (Result.getNode()) 3459 return Result; 3460 } 3461 3462 // Then check to see if we should lower the memset with target-specific 3463 // code. If the target chooses to do this, this is the next best. 3464 SDValue Result = 3465 TLI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, 3466 DstSV, DstSVOff); 3467 if (Result.getNode()) 3468 return Result; 3469 3470 // Emit a library call. 3471 const Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext()); 3472 TargetLowering::ArgListTy Args; 3473 TargetLowering::ArgListEntry Entry; 3474 Entry.Node = Dst; Entry.Ty = IntPtrTy; 3475 Args.push_back(Entry); 3476 // Extend or truncate the argument to be an i32 value for the call. 3477 if (Src.getValueType().bitsGT(MVT::i32)) 3478 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src); 3479 else 3480 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src); 3481 Entry.Node = Src; 3482 Entry.Ty = Type::getInt32Ty(*getContext()); 3483 Entry.isSExt = true; 3484 Args.push_back(Entry); 3485 Entry.Node = Size; 3486 Entry.Ty = IntPtrTy; 3487 Entry.isSExt = false; 3488 Args.push_back(Entry); 3489 // FIXME: pass in DebugLoc 3490 std::pair<SDValue,SDValue> CallResult = 3491 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()), 3492 false, false, false, false, 0, 3493 TLI.getLibcallCallingConv(RTLIB::MEMSET), false, 3494 /*isReturnValueUsed=*/false, 3495 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET), 3496 TLI.getPointerTy()), 3497 Args, *this, dl); 3498 return CallResult.second; 3499} 3500 3501SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 3502 SDValue Chain, 3503 SDValue Ptr, SDValue Cmp, 3504 SDValue Swp, const Value* PtrVal, 3505 unsigned Alignment) { 3506 if (Alignment == 0) // Ensure that codegen never sees alignment 0 3507 Alignment = getEVTAlignment(MemVT); 3508 3509 // Check if the memory reference references a frame index 3510 if (!PtrVal) 3511 if (const FrameIndexSDNode *FI = 3512 dyn_cast<const FrameIndexSDNode>(Ptr.getNode())) 3513 PtrVal = PseudoSourceValue::getFixedStack(FI->getIndex()); 3514 3515 MachineFunction &MF = getMachineFunction(); 3516 unsigned Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore; 3517 3518 // For now, atomics are considered to be volatile always. 3519 Flags |= MachineMemOperand::MOVolatile; 3520 3521 MachineMemOperand *MMO = 3522 MF.getMachineMemOperand(PtrVal, Flags, 0, 3523 MemVT.getStoreSize(), Alignment); 3524 3525 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO); 3526} 3527 3528SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 3529 SDValue Chain, 3530 SDValue Ptr, SDValue Cmp, 3531 SDValue Swp, MachineMemOperand *MMO) { 3532 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op"); 3533 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types"); 3534 3535 EVT VT = Cmp.getValueType(); 3536 3537 SDVTList VTs = getVTList(VT, MVT::Other); 3538 FoldingSetNodeID ID; 3539 ID.AddInteger(MemVT.getRawBits()); 3540 SDValue Ops[] = {Chain, Ptr, Cmp, Swp}; 3541 AddNodeIDNode(ID, Opcode, VTs, Ops, 4); 3542 void* IP = 0; 3543 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 3544 cast<AtomicSDNode>(E)->refineAlignment(MMO); 3545 return SDValue(E, 0); 3546 } 3547 SDNode* N = NodeAllocator.Allocate<AtomicSDNode>(); 3548 new (N) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain, Ptr, Cmp, Swp, MMO); 3549 CSEMap.InsertNode(N, IP); 3550 AllNodes.push_back(N); 3551 return SDValue(N, 0); 3552} 3553 3554SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 3555 SDValue Chain, 3556 SDValue Ptr, SDValue Val, 3557 const Value* PtrVal, 3558 unsigned Alignment) { 3559 if (Alignment == 0) // Ensure that codegen never sees alignment 0 3560 Alignment = getEVTAlignment(MemVT); 3561 3562 // Check if the memory reference references a frame index 3563 if (!PtrVal) 3564 if (const FrameIndexSDNode *FI = 3565 dyn_cast<const FrameIndexSDNode>(Ptr.getNode())) 3566 PtrVal = PseudoSourceValue::getFixedStack(FI->getIndex()); 3567 3568 MachineFunction &MF = getMachineFunction(); 3569 unsigned Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore; 3570 3571 // For now, atomics are considered to be volatile always. 3572 Flags |= MachineMemOperand::MOVolatile; 3573 3574 MachineMemOperand *MMO = 3575 MF.getMachineMemOperand(PtrVal, Flags, 0, 3576 MemVT.getStoreSize(), Alignment); 3577 3578 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO); 3579} 3580 3581SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 3582 SDValue Chain, 3583 SDValue Ptr, SDValue Val, 3584 MachineMemOperand *MMO) { 3585 assert((Opcode == ISD::ATOMIC_LOAD_ADD || 3586 Opcode == ISD::ATOMIC_LOAD_SUB || 3587 Opcode == ISD::ATOMIC_LOAD_AND || 3588 Opcode == ISD::ATOMIC_LOAD_OR || 3589 Opcode == ISD::ATOMIC_LOAD_XOR || 3590 Opcode == ISD::ATOMIC_LOAD_NAND || 3591 Opcode == ISD::ATOMIC_LOAD_MIN || 3592 Opcode == ISD::ATOMIC_LOAD_MAX || 3593 Opcode == ISD::ATOMIC_LOAD_UMIN || 3594 Opcode == ISD::ATOMIC_LOAD_UMAX || 3595 Opcode == ISD::ATOMIC_SWAP) && 3596 "Invalid Atomic Op"); 3597 3598 EVT VT = Val.getValueType(); 3599 3600 SDVTList VTs = getVTList(VT, MVT::Other); 3601 FoldingSetNodeID ID; 3602 ID.AddInteger(MemVT.getRawBits()); 3603 SDValue Ops[] = {Chain, Ptr, Val}; 3604 AddNodeIDNode(ID, Opcode, VTs, Ops, 3); 3605 void* IP = 0; 3606 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 3607 cast<AtomicSDNode>(E)->refineAlignment(MMO); 3608 return SDValue(E, 0); 3609 } 3610 SDNode* N = NodeAllocator.Allocate<AtomicSDNode>(); 3611 new (N) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain, Ptr, Val, MMO); 3612 CSEMap.InsertNode(N, IP); 3613 AllNodes.push_back(N); 3614 return SDValue(N, 0); 3615} 3616 3617/// getMergeValues - Create a MERGE_VALUES node from the given operands. 3618/// Allowed to return something different (and simpler) if Simplify is true. 3619SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps, 3620 DebugLoc dl) { 3621 if (NumOps == 1) 3622 return Ops[0]; 3623 3624 SmallVector<EVT, 4> VTs; 3625 VTs.reserve(NumOps); 3626 for (unsigned i = 0; i < NumOps; ++i) 3627 VTs.push_back(Ops[i].getValueType()); 3628 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps), 3629 Ops, NumOps); 3630} 3631 3632SDValue 3633SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, 3634 const EVT *VTs, unsigned NumVTs, 3635 const SDValue *Ops, unsigned NumOps, 3636 EVT MemVT, const Value *srcValue, int SVOff, 3637 unsigned Align, bool Vol, 3638 bool ReadMem, bool WriteMem) { 3639 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps, 3640 MemVT, srcValue, SVOff, Align, Vol, 3641 ReadMem, WriteMem); 3642} 3643 3644SDValue 3645SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 3646 const SDValue *Ops, unsigned NumOps, 3647 EVT MemVT, const Value *srcValue, int SVOff, 3648 unsigned Align, bool Vol, 3649 bool ReadMem, bool WriteMem) { 3650 if (Align == 0) // Ensure that codegen never sees alignment 0 3651 Align = getEVTAlignment(MemVT); 3652 3653 MachineFunction &MF = getMachineFunction(); 3654 unsigned Flags = 0; 3655 if (WriteMem) 3656 Flags |= MachineMemOperand::MOStore; 3657 if (ReadMem) 3658 Flags |= MachineMemOperand::MOLoad; 3659 if (Vol) 3660 Flags |= MachineMemOperand::MOVolatile; 3661 MachineMemOperand *MMO = 3662 MF.getMachineMemOperand(srcValue, Flags, SVOff, 3663 MemVT.getStoreSize(), Align); 3664 3665 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO); 3666} 3667 3668SDValue 3669SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 3670 const SDValue *Ops, unsigned NumOps, 3671 EVT MemVT, MachineMemOperand *MMO) { 3672 assert((Opcode == ISD::INTRINSIC_VOID || 3673 Opcode == ISD::INTRINSIC_W_CHAIN || 3674 (Opcode <= INT_MAX && 3675 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) && 3676 "Opcode is not a memory-accessing opcode!"); 3677 3678 // Memoize the node unless it returns a flag. 3679 MemIntrinsicSDNode *N; 3680 if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { 3681 FoldingSetNodeID ID; 3682 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 3683 void *IP = 0; 3684 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 3685 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO); 3686 return SDValue(E, 0); 3687 } 3688 3689 N = NodeAllocator.Allocate<MemIntrinsicSDNode>(); 3690 new (N) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO); 3691 CSEMap.InsertNode(N, IP); 3692 } else { 3693 N = NodeAllocator.Allocate<MemIntrinsicSDNode>(); 3694 new (N) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO); 3695 } 3696 AllNodes.push_back(N); 3697 return SDValue(N, 0); 3698} 3699 3700SDValue 3701SelectionDAG::getLoad(ISD::MemIndexedMode AM, DebugLoc dl, 3702 ISD::LoadExtType ExtType, EVT VT, SDValue Chain, 3703 SDValue Ptr, SDValue Offset, 3704 const Value *SV, int SVOffset, EVT MemVT, 3705 bool isVolatile, unsigned Alignment) { 3706 if (Alignment == 0) // Ensure that codegen never sees alignment 0 3707 Alignment = getEVTAlignment(VT); 3708 3709 // Check if the memory reference references a frame index 3710 if (!SV) 3711 if (const FrameIndexSDNode *FI = 3712 dyn_cast<const FrameIndexSDNode>(Ptr.getNode())) 3713 SV = PseudoSourceValue::getFixedStack(FI->getIndex()); 3714 3715 MachineFunction &MF = getMachineFunction(); 3716 unsigned Flags = MachineMemOperand::MOLoad; 3717 if (isVolatile) 3718 Flags |= MachineMemOperand::MOVolatile; 3719 MachineMemOperand *MMO = 3720 MF.getMachineMemOperand(SV, Flags, SVOffset, 3721 MemVT.getStoreSize(), Alignment); 3722 return getLoad(AM, dl, ExtType, VT, Chain, Ptr, Offset, MemVT, MMO); 3723} 3724 3725SDValue 3726SelectionDAG::getLoad(ISD::MemIndexedMode AM, DebugLoc dl, 3727 ISD::LoadExtType ExtType, EVT VT, SDValue Chain, 3728 SDValue Ptr, SDValue Offset, EVT MemVT, 3729 MachineMemOperand *MMO) { 3730 if (VT == MemVT) { 3731 ExtType = ISD::NON_EXTLOAD; 3732 } else if (ExtType == ISD::NON_EXTLOAD) { 3733 assert(VT == MemVT && "Non-extending load from different memory type!"); 3734 } else { 3735 // Extending load. 3736 if (VT.isVector()) 3737 assert(MemVT.getVectorNumElements() == VT.getVectorNumElements() && 3738 "Invalid vector extload!"); 3739 else 3740 assert(MemVT.bitsLT(VT) && 3741 "Should only be an extending load, not truncating!"); 3742 assert((ExtType == ISD::EXTLOAD || VT.isInteger()) && 3743 "Cannot sign/zero extend a FP/Vector load!"); 3744 assert(VT.isInteger() == MemVT.isInteger() && 3745 "Cannot convert from FP to Int or Int -> FP!"); 3746 } 3747 3748 bool Indexed = AM != ISD::UNINDEXED; 3749 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) && 3750 "Unindexed load with an offset!"); 3751 3752 SDVTList VTs = Indexed ? 3753 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other); 3754 SDValue Ops[] = { Chain, Ptr, Offset }; 3755 FoldingSetNodeID ID; 3756 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); 3757 ID.AddInteger(MemVT.getRawBits()); 3758 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile())); 3759 void *IP = 0; 3760 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 3761 cast<LoadSDNode>(E)->refineAlignment(MMO); 3762 return SDValue(E, 0); 3763 } 3764 SDNode *N = NodeAllocator.Allocate<LoadSDNode>(); 3765 new (N) LoadSDNode(Ops, dl, VTs, AM, ExtType, MemVT, MMO); 3766 CSEMap.InsertNode(N, IP); 3767 AllNodes.push_back(N); 3768 return SDValue(N, 0); 3769} 3770 3771SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl, 3772 SDValue Chain, SDValue Ptr, 3773 const Value *SV, int SVOffset, 3774 bool isVolatile, unsigned Alignment) { 3775 SDValue Undef = getUNDEF(Ptr.getValueType()); 3776 return getLoad(ISD::UNINDEXED, dl, ISD::NON_EXTLOAD, VT, Chain, Ptr, Undef, 3777 SV, SVOffset, VT, isVolatile, Alignment); 3778} 3779 3780SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT, 3781 SDValue Chain, SDValue Ptr, 3782 const Value *SV, 3783 int SVOffset, EVT MemVT, 3784 bool isVolatile, unsigned Alignment) { 3785 SDValue Undef = getUNDEF(Ptr.getValueType()); 3786 return getLoad(ISD::UNINDEXED, dl, ExtType, VT, Chain, Ptr, Undef, 3787 SV, SVOffset, MemVT, isVolatile, Alignment); 3788} 3789 3790SDValue 3791SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, 3792 SDValue Offset, ISD::MemIndexedMode AM) { 3793 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad); 3794 assert(LD->getOffset().getOpcode() == ISD::UNDEF && 3795 "Load is already a indexed load!"); 3796 return getLoad(AM, dl, LD->getExtensionType(), OrigLoad.getValueType(), 3797 LD->getChain(), Base, Offset, LD->getSrcValue(), 3798 LD->getSrcValueOffset(), LD->getMemoryVT(), 3799 LD->isVolatile(), LD->getAlignment()); 3800} 3801 3802SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val, 3803 SDValue Ptr, const Value *SV, int SVOffset, 3804 bool isVolatile, unsigned Alignment) { 3805 if (Alignment == 0) // Ensure that codegen never sees alignment 0 3806 Alignment = getEVTAlignment(Val.getValueType()); 3807 3808 // Check if the memory reference references a frame index 3809 if (!SV) 3810 if (const FrameIndexSDNode *FI = 3811 dyn_cast<const FrameIndexSDNode>(Ptr.getNode())) 3812 SV = PseudoSourceValue::getFixedStack(FI->getIndex()); 3813 3814 MachineFunction &MF = getMachineFunction(); 3815 unsigned Flags = MachineMemOperand::MOStore; 3816 if (isVolatile) 3817 Flags |= MachineMemOperand::MOVolatile; 3818 MachineMemOperand *MMO = 3819 MF.getMachineMemOperand(SV, Flags, SVOffset, 3820 Val.getValueType().getStoreSize(), Alignment); 3821 3822 return getStore(Chain, dl, Val, Ptr, MMO); 3823} 3824 3825SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val, 3826 SDValue Ptr, MachineMemOperand *MMO) { 3827 EVT VT = Val.getValueType(); 3828 SDVTList VTs = getVTList(MVT::Other); 3829 SDValue Undef = getUNDEF(Ptr.getValueType()); 3830 SDValue Ops[] = { Chain, Val, Ptr, Undef }; 3831 FoldingSetNodeID ID; 3832 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 3833 ID.AddInteger(VT.getRawBits()); 3834 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile())); 3835 void *IP = 0; 3836 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 3837 cast<StoreSDNode>(E)->refineAlignment(MMO); 3838 return SDValue(E, 0); 3839 } 3840 SDNode *N = NodeAllocator.Allocate<StoreSDNode>(); 3841 new (N) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED, false, VT, MMO); 3842 CSEMap.InsertNode(N, IP); 3843 AllNodes.push_back(N); 3844 return SDValue(N, 0); 3845} 3846 3847SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, 3848 SDValue Ptr, const Value *SV, 3849 int SVOffset, EVT SVT, 3850 bool isVolatile, unsigned Alignment) { 3851 if (Alignment == 0) // Ensure that codegen never sees alignment 0 3852 Alignment = getEVTAlignment(SVT); 3853 3854 // Check if the memory reference references a frame index 3855 if (!SV) 3856 if (const FrameIndexSDNode *FI = 3857 dyn_cast<const FrameIndexSDNode>(Ptr.getNode())) 3858 SV = PseudoSourceValue::getFixedStack(FI->getIndex()); 3859 3860 MachineFunction &MF = getMachineFunction(); 3861 unsigned Flags = MachineMemOperand::MOStore; 3862 if (isVolatile) 3863 Flags |= MachineMemOperand::MOVolatile; 3864 MachineMemOperand *MMO = 3865 MF.getMachineMemOperand(SV, Flags, SVOffset, SVT.getStoreSize(), Alignment); 3866 3867 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO); 3868} 3869 3870SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, 3871 SDValue Ptr, EVT SVT, 3872 MachineMemOperand *MMO) { 3873 EVT VT = Val.getValueType(); 3874 3875 if (VT == SVT) 3876 return getStore(Chain, dl, Val, Ptr, MMO); 3877 3878 assert(VT.bitsGT(SVT) && "Not a truncation?"); 3879 assert(VT.isInteger() == SVT.isInteger() && 3880 "Can't do FP-INT conversion!"); 3881 3882 3883 SDVTList VTs = getVTList(MVT::Other); 3884 SDValue Undef = getUNDEF(Ptr.getValueType()); 3885 SDValue Ops[] = { Chain, Val, Ptr, Undef }; 3886 FoldingSetNodeID ID; 3887 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 3888 ID.AddInteger(SVT.getRawBits()); 3889 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile())); 3890 void *IP = 0; 3891 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 3892 cast<StoreSDNode>(E)->refineAlignment(MMO); 3893 return SDValue(E, 0); 3894 } 3895 SDNode *N = NodeAllocator.Allocate<StoreSDNode>(); 3896 new (N) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED, true, SVT, MMO); 3897 CSEMap.InsertNode(N, IP); 3898 AllNodes.push_back(N); 3899 return SDValue(N, 0); 3900} 3901 3902SDValue 3903SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base, 3904 SDValue Offset, ISD::MemIndexedMode AM) { 3905 StoreSDNode *ST = cast<StoreSDNode>(OrigStore); 3906 assert(ST->getOffset().getOpcode() == ISD::UNDEF && 3907 "Store is already a indexed store!"); 3908 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other); 3909 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset }; 3910 FoldingSetNodeID ID; 3911 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 3912 ID.AddInteger(ST->getMemoryVT().getRawBits()); 3913 ID.AddInteger(ST->getRawSubclassData()); 3914 void *IP = 0; 3915 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 3916 return SDValue(E, 0); 3917 SDNode *N = NodeAllocator.Allocate<StoreSDNode>(); 3918 new (N) StoreSDNode(Ops, dl, VTs, AM, 3919 ST->isTruncatingStore(), ST->getMemoryVT(), 3920 ST->getMemOperand()); 3921 CSEMap.InsertNode(N, IP); 3922 AllNodes.push_back(N); 3923 return SDValue(N, 0); 3924} 3925 3926SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl, 3927 SDValue Chain, SDValue Ptr, 3928 SDValue SV) { 3929 SDValue Ops[] = { Chain, Ptr, SV }; 3930 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 3); 3931} 3932 3933SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 3934 const SDUse *Ops, unsigned NumOps) { 3935 switch (NumOps) { 3936 case 0: return getNode(Opcode, DL, VT); 3937 case 1: return getNode(Opcode, DL, VT, Ops[0]); 3938 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]); 3939 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]); 3940 default: break; 3941 } 3942 3943 // Copy from an SDUse array into an SDValue array for use with 3944 // the regular getNode logic. 3945 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps); 3946 return getNode(Opcode, DL, VT, &NewOps[0], NumOps); 3947} 3948 3949SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 3950 const SDValue *Ops, unsigned NumOps) { 3951 switch (NumOps) { 3952 case 0: return getNode(Opcode, DL, VT); 3953 case 1: return getNode(Opcode, DL, VT, Ops[0]); 3954 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]); 3955 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]); 3956 default: break; 3957 } 3958 3959 switch (Opcode) { 3960 default: break; 3961 case ISD::SELECT_CC: { 3962 assert(NumOps == 5 && "SELECT_CC takes 5 operands!"); 3963 assert(Ops[0].getValueType() == Ops[1].getValueType() && 3964 "LHS and RHS of condition must have same type!"); 3965 assert(Ops[2].getValueType() == Ops[3].getValueType() && 3966 "True and False arms of SelectCC must have same type!"); 3967 assert(Ops[2].getValueType() == VT && 3968 "select_cc node must be of same type as true and false value!"); 3969 break; 3970 } 3971 case ISD::BR_CC: { 3972 assert(NumOps == 5 && "BR_CC takes 5 operands!"); 3973 assert(Ops[2].getValueType() == Ops[3].getValueType() && 3974 "LHS/RHS of comparison should match types!"); 3975 break; 3976 } 3977 } 3978 3979 // Memoize nodes. 3980 SDNode *N; 3981 SDVTList VTs = getVTList(VT); 3982 3983 if (VT != MVT::Flag) { 3984 FoldingSetNodeID ID; 3985 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps); 3986 void *IP = 0; 3987 3988 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 3989 return SDValue(E, 0); 3990 3991 N = NodeAllocator.Allocate<SDNode>(); 3992 new (N) SDNode(Opcode, DL, VTs, Ops, NumOps); 3993 CSEMap.InsertNode(N, IP); 3994 } else { 3995 N = NodeAllocator.Allocate<SDNode>(); 3996 new (N) SDNode(Opcode, DL, VTs, Ops, NumOps); 3997 } 3998 3999 AllNodes.push_back(N); 4000#ifndef NDEBUG 4001 VerifyNode(N); 4002#endif 4003 return SDValue(N, 0); 4004} 4005 4006SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, 4007 const std::vector<EVT> &ResultTys, 4008 const SDValue *Ops, unsigned NumOps) { 4009 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()), 4010 Ops, NumOps); 4011} 4012 4013SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, 4014 const EVT *VTs, unsigned NumVTs, 4015 const SDValue *Ops, unsigned NumOps) { 4016 if (NumVTs == 1) 4017 return getNode(Opcode, DL, VTs[0], Ops, NumOps); 4018 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps); 4019} 4020 4021SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4022 const SDValue *Ops, unsigned NumOps) { 4023 if (VTList.NumVTs == 1) 4024 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps); 4025 4026#if 0 4027 switch (Opcode) { 4028 // FIXME: figure out how to safely handle things like 4029 // int foo(int x) { return 1 << (x & 255); } 4030 // int bar() { return foo(256); } 4031 case ISD::SRA_PARTS: 4032 case ISD::SRL_PARTS: 4033 case ISD::SHL_PARTS: 4034 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG && 4035 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1) 4036 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0)); 4037 else if (N3.getOpcode() == ISD::AND) 4038 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) { 4039 // If the and is only masking out bits that cannot effect the shift, 4040 // eliminate the and. 4041 unsigned NumBits = VT.getSizeInBits()*2; 4042 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 4043 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0)); 4044 } 4045 break; 4046 } 4047#endif 4048 4049 // Memoize the node unless it returns a flag. 4050 SDNode *N; 4051 if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { 4052 FoldingSetNodeID ID; 4053 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 4054 void *IP = 0; 4055 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 4056 return SDValue(E, 0); 4057 if (NumOps == 1) { 4058 N = NodeAllocator.Allocate<UnarySDNode>(); 4059 new (N) UnarySDNode(Opcode, DL, VTList, Ops[0]); 4060 } else if (NumOps == 2) { 4061 N = NodeAllocator.Allocate<BinarySDNode>(); 4062 new (N) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]); 4063 } else if (NumOps == 3) { 4064 N = NodeAllocator.Allocate<TernarySDNode>(); 4065 new (N) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1], Ops[2]); 4066 } else { 4067 N = NodeAllocator.Allocate<SDNode>(); 4068 new (N) SDNode(Opcode, DL, VTList, Ops, NumOps); 4069 } 4070 CSEMap.InsertNode(N, IP); 4071 } else { 4072 if (NumOps == 1) { 4073 N = NodeAllocator.Allocate<UnarySDNode>(); 4074 new (N) UnarySDNode(Opcode, DL, VTList, Ops[0]); 4075 } else if (NumOps == 2) { 4076 N = NodeAllocator.Allocate<BinarySDNode>(); 4077 new (N) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]); 4078 } else if (NumOps == 3) { 4079 N = NodeAllocator.Allocate<TernarySDNode>(); 4080 new (N) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1], Ops[2]); 4081 } else { 4082 N = NodeAllocator.Allocate<SDNode>(); 4083 new (N) SDNode(Opcode, DL, VTList, Ops, NumOps); 4084 } 4085 } 4086 AllNodes.push_back(N); 4087#ifndef NDEBUG 4088 VerifyNode(N); 4089#endif 4090 return SDValue(N, 0); 4091} 4092 4093SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) { 4094 return getNode(Opcode, DL, VTList, 0, 0); 4095} 4096 4097SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4098 SDValue N1) { 4099 SDValue Ops[] = { N1 }; 4100 return getNode(Opcode, DL, VTList, Ops, 1); 4101} 4102 4103SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4104 SDValue N1, SDValue N2) { 4105 SDValue Ops[] = { N1, N2 }; 4106 return getNode(Opcode, DL, VTList, Ops, 2); 4107} 4108 4109SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4110 SDValue N1, SDValue N2, SDValue N3) { 4111 SDValue Ops[] = { N1, N2, N3 }; 4112 return getNode(Opcode, DL, VTList, Ops, 3); 4113} 4114 4115SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4116 SDValue N1, SDValue N2, SDValue N3, 4117 SDValue N4) { 4118 SDValue Ops[] = { N1, N2, N3, N4 }; 4119 return getNode(Opcode, DL, VTList, Ops, 4); 4120} 4121 4122SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4123 SDValue N1, SDValue N2, SDValue N3, 4124 SDValue N4, SDValue N5) { 4125 SDValue Ops[] = { N1, N2, N3, N4, N5 }; 4126 return getNode(Opcode, DL, VTList, Ops, 5); 4127} 4128 4129SDVTList SelectionDAG::getVTList(EVT VT) { 4130 return makeVTList(SDNode::getValueTypeList(VT), 1); 4131} 4132 4133SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) { 4134 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 4135 E = VTList.rend(); I != E; ++I) 4136 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2) 4137 return *I; 4138 4139 EVT *Array = Allocator.Allocate<EVT>(2); 4140 Array[0] = VT1; 4141 Array[1] = VT2; 4142 SDVTList Result = makeVTList(Array, 2); 4143 VTList.push_back(Result); 4144 return Result; 4145} 4146 4147SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) { 4148 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 4149 E = VTList.rend(); I != E; ++I) 4150 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 && 4151 I->VTs[2] == VT3) 4152 return *I; 4153 4154 EVT *Array = Allocator.Allocate<EVT>(3); 4155 Array[0] = VT1; 4156 Array[1] = VT2; 4157 Array[2] = VT3; 4158 SDVTList Result = makeVTList(Array, 3); 4159 VTList.push_back(Result); 4160 return Result; 4161} 4162 4163SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) { 4164 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 4165 E = VTList.rend(); I != E; ++I) 4166 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 && 4167 I->VTs[2] == VT3 && I->VTs[3] == VT4) 4168 return *I; 4169 4170 EVT *Array = Allocator.Allocate<EVT>(3); 4171 Array[0] = VT1; 4172 Array[1] = VT2; 4173 Array[2] = VT3; 4174 Array[3] = VT4; 4175 SDVTList Result = makeVTList(Array, 4); 4176 VTList.push_back(Result); 4177 return Result; 4178} 4179 4180SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) { 4181 switch (NumVTs) { 4182 case 0: llvm_unreachable("Cannot have nodes without results!"); 4183 case 1: return getVTList(VTs[0]); 4184 case 2: return getVTList(VTs[0], VTs[1]); 4185 case 3: return getVTList(VTs[0], VTs[1], VTs[2]); 4186 default: break; 4187 } 4188 4189 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 4190 E = VTList.rend(); I != E; ++I) { 4191 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1]) 4192 continue; 4193 4194 bool NoMatch = false; 4195 for (unsigned i = 2; i != NumVTs; ++i) 4196 if (VTs[i] != I->VTs[i]) { 4197 NoMatch = true; 4198 break; 4199 } 4200 if (!NoMatch) 4201 return *I; 4202 } 4203 4204 EVT *Array = Allocator.Allocate<EVT>(NumVTs); 4205 std::copy(VTs, VTs+NumVTs, Array); 4206 SDVTList Result = makeVTList(Array, NumVTs); 4207 VTList.push_back(Result); 4208 return Result; 4209} 4210 4211 4212/// UpdateNodeOperands - *Mutate* the specified node in-place to have the 4213/// specified operands. If the resultant node already exists in the DAG, 4214/// this does not modify the specified node, instead it returns the node that 4215/// already exists. If the resultant node does not exist in the DAG, the 4216/// input node is returned. As a degenerate case, if you specify the same 4217/// input operands as the node already has, the input node is returned. 4218SDValue SelectionDAG::UpdateNodeOperands(SDValue InN, SDValue Op) { 4219 SDNode *N = InN.getNode(); 4220 assert(N->getNumOperands() == 1 && "Update with wrong number of operands"); 4221 4222 // Check to see if there is no change. 4223 if (Op == N->getOperand(0)) return InN; 4224 4225 // See if the modified node already exists. 4226 void *InsertPos = 0; 4227 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos)) 4228 return SDValue(Existing, InN.getResNo()); 4229 4230 // Nope it doesn't. Remove the node from its current place in the maps. 4231 if (InsertPos) 4232 if (!RemoveNodeFromCSEMaps(N)) 4233 InsertPos = 0; 4234 4235 // Now we update the operands. 4236 N->OperandList[0].set(Op); 4237 4238 // If this gets put into a CSE map, add it. 4239 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 4240 return InN; 4241} 4242 4243SDValue SelectionDAG:: 4244UpdateNodeOperands(SDValue InN, SDValue Op1, SDValue Op2) { 4245 SDNode *N = InN.getNode(); 4246 assert(N->getNumOperands() == 2 && "Update with wrong number of operands"); 4247 4248 // Check to see if there is no change. 4249 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1)) 4250 return InN; // No operands changed, just return the input node. 4251 4252 // See if the modified node already exists. 4253 void *InsertPos = 0; 4254 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos)) 4255 return SDValue(Existing, InN.getResNo()); 4256 4257 // Nope it doesn't. Remove the node from its current place in the maps. 4258 if (InsertPos) 4259 if (!RemoveNodeFromCSEMaps(N)) 4260 InsertPos = 0; 4261 4262 // Now we update the operands. 4263 if (N->OperandList[0] != Op1) 4264 N->OperandList[0].set(Op1); 4265 if (N->OperandList[1] != Op2) 4266 N->OperandList[1].set(Op2); 4267 4268 // If this gets put into a CSE map, add it. 4269 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 4270 return InN; 4271} 4272 4273SDValue SelectionDAG:: 4274UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, SDValue Op3) { 4275 SDValue Ops[] = { Op1, Op2, Op3 }; 4276 return UpdateNodeOperands(N, Ops, 3); 4277} 4278 4279SDValue SelectionDAG:: 4280UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 4281 SDValue Op3, SDValue Op4) { 4282 SDValue Ops[] = { Op1, Op2, Op3, Op4 }; 4283 return UpdateNodeOperands(N, Ops, 4); 4284} 4285 4286SDValue SelectionDAG:: 4287UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 4288 SDValue Op3, SDValue Op4, SDValue Op5) { 4289 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 }; 4290 return UpdateNodeOperands(N, Ops, 5); 4291} 4292 4293SDValue SelectionDAG:: 4294UpdateNodeOperands(SDValue InN, const SDValue *Ops, unsigned NumOps) { 4295 SDNode *N = InN.getNode(); 4296 assert(N->getNumOperands() == NumOps && 4297 "Update with wrong number of operands"); 4298 4299 // Check to see if there is no change. 4300 bool AnyChange = false; 4301 for (unsigned i = 0; i != NumOps; ++i) { 4302 if (Ops[i] != N->getOperand(i)) { 4303 AnyChange = true; 4304 break; 4305 } 4306 } 4307 4308 // No operands changed, just return the input node. 4309 if (!AnyChange) return InN; 4310 4311 // See if the modified node already exists. 4312 void *InsertPos = 0; 4313 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos)) 4314 return SDValue(Existing, InN.getResNo()); 4315 4316 // Nope it doesn't. Remove the node from its current place in the maps. 4317 if (InsertPos) 4318 if (!RemoveNodeFromCSEMaps(N)) 4319 InsertPos = 0; 4320 4321 // Now we update the operands. 4322 for (unsigned i = 0; i != NumOps; ++i) 4323 if (N->OperandList[i] != Ops[i]) 4324 N->OperandList[i].set(Ops[i]); 4325 4326 // If this gets put into a CSE map, add it. 4327 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 4328 return InN; 4329} 4330 4331/// DropOperands - Release the operands and set this node to have 4332/// zero operands. 4333void SDNode::DropOperands() { 4334 // Unlike the code in MorphNodeTo that does this, we don't need to 4335 // watch for dead nodes here. 4336 for (op_iterator I = op_begin(), E = op_end(); I != E; ) { 4337 SDUse &Use = *I++; 4338 Use.set(SDValue()); 4339 } 4340} 4341 4342/// SelectNodeTo - These are wrappers around MorphNodeTo that accept a 4343/// machine opcode. 4344/// 4345SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4346 EVT VT) { 4347 SDVTList VTs = getVTList(VT); 4348 return SelectNodeTo(N, MachineOpc, VTs, 0, 0); 4349} 4350 4351SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4352 EVT VT, SDValue Op1) { 4353 SDVTList VTs = getVTList(VT); 4354 SDValue Ops[] = { Op1 }; 4355 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1); 4356} 4357 4358SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4359 EVT VT, SDValue Op1, 4360 SDValue Op2) { 4361 SDVTList VTs = getVTList(VT); 4362 SDValue Ops[] = { Op1, Op2 }; 4363 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2); 4364} 4365 4366SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4367 EVT VT, SDValue Op1, 4368 SDValue Op2, SDValue Op3) { 4369 SDVTList VTs = getVTList(VT); 4370 SDValue Ops[] = { Op1, Op2, Op3 }; 4371 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); 4372} 4373 4374SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4375 EVT VT, const SDValue *Ops, 4376 unsigned NumOps) { 4377 SDVTList VTs = getVTList(VT); 4378 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 4379} 4380 4381SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4382 EVT VT1, EVT VT2, const SDValue *Ops, 4383 unsigned NumOps) { 4384 SDVTList VTs = getVTList(VT1, VT2); 4385 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 4386} 4387 4388SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4389 EVT VT1, EVT VT2) { 4390 SDVTList VTs = getVTList(VT1, VT2); 4391 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0); 4392} 4393 4394SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4395 EVT VT1, EVT VT2, EVT VT3, 4396 const SDValue *Ops, unsigned NumOps) { 4397 SDVTList VTs = getVTList(VT1, VT2, VT3); 4398 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 4399} 4400 4401SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4402 EVT VT1, EVT VT2, EVT VT3, EVT VT4, 4403 const SDValue *Ops, unsigned NumOps) { 4404 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4); 4405 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 4406} 4407 4408SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4409 EVT VT1, EVT VT2, 4410 SDValue Op1) { 4411 SDVTList VTs = getVTList(VT1, VT2); 4412 SDValue Ops[] = { Op1 }; 4413 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1); 4414} 4415 4416SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4417 EVT VT1, EVT VT2, 4418 SDValue Op1, SDValue Op2) { 4419 SDVTList VTs = getVTList(VT1, VT2); 4420 SDValue Ops[] = { Op1, Op2 }; 4421 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2); 4422} 4423 4424SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4425 EVT VT1, EVT VT2, 4426 SDValue Op1, SDValue Op2, 4427 SDValue Op3) { 4428 SDVTList VTs = getVTList(VT1, VT2); 4429 SDValue Ops[] = { Op1, Op2, Op3 }; 4430 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); 4431} 4432 4433SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4434 EVT VT1, EVT VT2, EVT VT3, 4435 SDValue Op1, SDValue Op2, 4436 SDValue Op3) { 4437 SDVTList VTs = getVTList(VT1, VT2, VT3); 4438 SDValue Ops[] = { Op1, Op2, Op3 }; 4439 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); 4440} 4441 4442SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4443 SDVTList VTs, const SDValue *Ops, 4444 unsigned NumOps) { 4445 return MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps); 4446} 4447 4448SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4449 EVT VT) { 4450 SDVTList VTs = getVTList(VT); 4451 return MorphNodeTo(N, Opc, VTs, 0, 0); 4452} 4453 4454SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4455 EVT VT, SDValue Op1) { 4456 SDVTList VTs = getVTList(VT); 4457 SDValue Ops[] = { Op1 }; 4458 return MorphNodeTo(N, Opc, VTs, Ops, 1); 4459} 4460 4461SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4462 EVT VT, SDValue Op1, 4463 SDValue Op2) { 4464 SDVTList VTs = getVTList(VT); 4465 SDValue Ops[] = { Op1, Op2 }; 4466 return MorphNodeTo(N, Opc, VTs, Ops, 2); 4467} 4468 4469SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4470 EVT VT, SDValue Op1, 4471 SDValue Op2, SDValue Op3) { 4472 SDVTList VTs = getVTList(VT); 4473 SDValue Ops[] = { Op1, Op2, Op3 }; 4474 return MorphNodeTo(N, Opc, VTs, Ops, 3); 4475} 4476 4477SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4478 EVT VT, const SDValue *Ops, 4479 unsigned NumOps) { 4480 SDVTList VTs = getVTList(VT); 4481 return MorphNodeTo(N, Opc, VTs, Ops, NumOps); 4482} 4483 4484SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4485 EVT VT1, EVT VT2, const SDValue *Ops, 4486 unsigned NumOps) { 4487 SDVTList VTs = getVTList(VT1, VT2); 4488 return MorphNodeTo(N, Opc, VTs, Ops, NumOps); 4489} 4490 4491SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4492 EVT VT1, EVT VT2) { 4493 SDVTList VTs = getVTList(VT1, VT2); 4494 return MorphNodeTo(N, Opc, VTs, (SDValue *)0, 0); 4495} 4496 4497SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4498 EVT VT1, EVT VT2, EVT VT3, 4499 const SDValue *Ops, unsigned NumOps) { 4500 SDVTList VTs = getVTList(VT1, VT2, VT3); 4501 return MorphNodeTo(N, Opc, VTs, Ops, NumOps); 4502} 4503 4504SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4505 EVT VT1, EVT VT2, 4506 SDValue Op1) { 4507 SDVTList VTs = getVTList(VT1, VT2); 4508 SDValue Ops[] = { Op1 }; 4509 return MorphNodeTo(N, Opc, VTs, Ops, 1); 4510} 4511 4512SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4513 EVT VT1, EVT VT2, 4514 SDValue Op1, SDValue Op2) { 4515 SDVTList VTs = getVTList(VT1, VT2); 4516 SDValue Ops[] = { Op1, Op2 }; 4517 return MorphNodeTo(N, Opc, VTs, Ops, 2); 4518} 4519 4520SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4521 EVT VT1, EVT VT2, 4522 SDValue Op1, SDValue Op2, 4523 SDValue Op3) { 4524 SDVTList VTs = getVTList(VT1, VT2); 4525 SDValue Ops[] = { Op1, Op2, Op3 }; 4526 return MorphNodeTo(N, Opc, VTs, Ops, 3); 4527} 4528 4529/// MorphNodeTo - These *mutate* the specified node to have the specified 4530/// return type, opcode, and operands. 4531/// 4532/// Note that MorphNodeTo returns the resultant node. If there is already a 4533/// node of the specified opcode and operands, it returns that node instead of 4534/// the current one. Note that the DebugLoc need not be the same. 4535/// 4536/// Using MorphNodeTo is faster than creating a new node and swapping it in 4537/// with ReplaceAllUsesWith both because it often avoids allocating a new 4538/// node, and because it doesn't require CSE recalculation for any of 4539/// the node's users. 4540/// 4541SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 4542 SDVTList VTs, const SDValue *Ops, 4543 unsigned NumOps) { 4544 // If an identical node already exists, use it. 4545 void *IP = 0; 4546 if (VTs.VTs[VTs.NumVTs-1] != MVT::Flag) { 4547 FoldingSetNodeID ID; 4548 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps); 4549 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 4550 return ON; 4551 } 4552 4553 if (!RemoveNodeFromCSEMaps(N)) 4554 IP = 0; 4555 4556 // Start the morphing. 4557 N->NodeType = Opc; 4558 N->ValueList = VTs.VTs; 4559 N->NumValues = VTs.NumVTs; 4560 4561 // Clear the operands list, updating used nodes to remove this from their 4562 // use list. Keep track of any operands that become dead as a result. 4563 SmallPtrSet<SDNode*, 16> DeadNodeSet; 4564 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) { 4565 SDUse &Use = *I++; 4566 SDNode *Used = Use.getNode(); 4567 Use.set(SDValue()); 4568 if (Used->use_empty()) 4569 DeadNodeSet.insert(Used); 4570 } 4571 4572 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) { 4573 // Initialize the memory references information. 4574 MN->setMemRefs(0, 0); 4575 // If NumOps is larger than the # of operands we can have in a 4576 // MachineSDNode, reallocate the operand list. 4577 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) { 4578 if (MN->OperandsNeedDelete) 4579 delete[] MN->OperandList; 4580 if (NumOps > array_lengthof(MN->LocalOperands)) 4581 // We're creating a final node that will live unmorphed for the 4582 // remainder of the current SelectionDAG iteration, so we can allocate 4583 // the operands directly out of a pool with no recycling metadata. 4584 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps), 4585 Ops, NumOps); 4586 else 4587 MN->InitOperands(MN->LocalOperands, Ops, NumOps); 4588 MN->OperandsNeedDelete = false; 4589 } else 4590 MN->InitOperands(MN->OperandList, Ops, NumOps); 4591 } else { 4592 // If NumOps is larger than the # of operands we currently have, reallocate 4593 // the operand list. 4594 if (NumOps > N->NumOperands) { 4595 if (N->OperandsNeedDelete) 4596 delete[] N->OperandList; 4597 N->InitOperands(new SDUse[NumOps], Ops, NumOps); 4598 N->OperandsNeedDelete = true; 4599 } else 4600 N->InitOperands(N->OperandList, Ops, NumOps); 4601 } 4602 4603 // Delete any nodes that are still dead after adding the uses for the 4604 // new operands. 4605 SmallVector<SDNode *, 16> DeadNodes; 4606 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(), 4607 E = DeadNodeSet.end(); I != E; ++I) 4608 if ((*I)->use_empty()) 4609 DeadNodes.push_back(*I); 4610 RemoveDeadNodes(DeadNodes); 4611 4612 if (IP) 4613 CSEMap.InsertNode(N, IP); // Memoize the new node. 4614 return N; 4615} 4616 4617 4618/// getMachineNode - These are used for target selectors to create a new node 4619/// with specified return type(s), MachineInstr opcode, and operands. 4620/// 4621/// Note that getMachineNode returns the resultant node. If there is already a 4622/// node of the specified opcode and operands, it returns that node instead of 4623/// the current one. 4624MachineSDNode * 4625SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) { 4626 SDVTList VTs = getVTList(VT); 4627 return getMachineNode(Opcode, dl, VTs, 0, 0); 4628} 4629 4630MachineSDNode * 4631SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) { 4632 SDVTList VTs = getVTList(VT); 4633 SDValue Ops[] = { Op1 }; 4634 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 4635} 4636 4637MachineSDNode * 4638SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 4639 SDValue Op1, SDValue Op2) { 4640 SDVTList VTs = getVTList(VT); 4641 SDValue Ops[] = { Op1, Op2 }; 4642 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 4643} 4644 4645MachineSDNode * 4646SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 4647 SDValue Op1, SDValue Op2, SDValue Op3) { 4648 SDVTList VTs = getVTList(VT); 4649 SDValue Ops[] = { Op1, Op2, Op3 }; 4650 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 4651} 4652 4653MachineSDNode * 4654SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 4655 const SDValue *Ops, unsigned NumOps) { 4656 SDVTList VTs = getVTList(VT); 4657 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 4658} 4659 4660MachineSDNode * 4661SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) { 4662 SDVTList VTs = getVTList(VT1, VT2); 4663 return getMachineNode(Opcode, dl, VTs, 0, 0); 4664} 4665 4666MachineSDNode * 4667SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 4668 EVT VT1, EVT VT2, SDValue Op1) { 4669 SDVTList VTs = getVTList(VT1, VT2); 4670 SDValue Ops[] = { Op1 }; 4671 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 4672} 4673 4674MachineSDNode * 4675SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 4676 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) { 4677 SDVTList VTs = getVTList(VT1, VT2); 4678 SDValue Ops[] = { Op1, Op2 }; 4679 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 4680} 4681 4682MachineSDNode * 4683SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 4684 EVT VT1, EVT VT2, SDValue Op1, 4685 SDValue Op2, SDValue Op3) { 4686 SDVTList VTs = getVTList(VT1, VT2); 4687 SDValue Ops[] = { Op1, Op2, Op3 }; 4688 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 4689} 4690 4691MachineSDNode * 4692SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 4693 EVT VT1, EVT VT2, 4694 const SDValue *Ops, unsigned NumOps) { 4695 SDVTList VTs = getVTList(VT1, VT2); 4696 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 4697} 4698 4699MachineSDNode * 4700SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 4701 EVT VT1, EVT VT2, EVT VT3, 4702 SDValue Op1, SDValue Op2) { 4703 SDVTList VTs = getVTList(VT1, VT2, VT3); 4704 SDValue Ops[] = { Op1, Op2 }; 4705 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 4706} 4707 4708MachineSDNode * 4709SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 4710 EVT VT1, EVT VT2, EVT VT3, 4711 SDValue Op1, SDValue Op2, SDValue Op3) { 4712 SDVTList VTs = getVTList(VT1, VT2, VT3); 4713 SDValue Ops[] = { Op1, Op2, Op3 }; 4714 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 4715} 4716 4717MachineSDNode * 4718SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 4719 EVT VT1, EVT VT2, EVT VT3, 4720 const SDValue *Ops, unsigned NumOps) { 4721 SDVTList VTs = getVTList(VT1, VT2, VT3); 4722 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 4723} 4724 4725MachineSDNode * 4726SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, 4727 EVT VT2, EVT VT3, EVT VT4, 4728 const SDValue *Ops, unsigned NumOps) { 4729 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4); 4730 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 4731} 4732 4733MachineSDNode * 4734SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 4735 const std::vector<EVT> &ResultTys, 4736 const SDValue *Ops, unsigned NumOps) { 4737 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size()); 4738 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 4739} 4740 4741MachineSDNode * 4742SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 4743 const SDValue *Ops, unsigned NumOps) { 4744 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Flag; 4745 MachineSDNode *N; 4746 void *IP; 4747 4748 if (DoCSE) { 4749 FoldingSetNodeID ID; 4750 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps); 4751 IP = 0; 4752 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 4753 return cast<MachineSDNode>(E); 4754 } 4755 4756 // Allocate a new MachineSDNode. 4757 N = NodeAllocator.Allocate<MachineSDNode>(); 4758 new (N) MachineSDNode(~Opcode, DL, VTs); 4759 4760 // Initialize the operands list. 4761 if (NumOps > array_lengthof(N->LocalOperands)) 4762 // We're creating a final node that will live unmorphed for the 4763 // remainder of the current SelectionDAG iteration, so we can allocate 4764 // the operands directly out of a pool with no recycling metadata. 4765 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps), 4766 Ops, NumOps); 4767 else 4768 N->InitOperands(N->LocalOperands, Ops, NumOps); 4769 N->OperandsNeedDelete = false; 4770 4771 if (DoCSE) 4772 CSEMap.InsertNode(N, IP); 4773 4774 AllNodes.push_back(N); 4775#ifndef NDEBUG 4776 VerifyNode(N); 4777#endif 4778 return N; 4779} 4780 4781/// getTargetExtractSubreg - A convenience function for creating 4782/// TargetInstrInfo::EXTRACT_SUBREG nodes. 4783SDValue 4784SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT, 4785 SDValue Operand) { 4786 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32); 4787 SDNode *Subreg = getMachineNode(TargetInstrInfo::EXTRACT_SUBREG, DL, 4788 VT, Operand, SRIdxVal); 4789 return SDValue(Subreg, 0); 4790} 4791 4792/// getTargetInsertSubreg - A convenience function for creating 4793/// TargetInstrInfo::INSERT_SUBREG nodes. 4794SDValue 4795SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT, 4796 SDValue Operand, SDValue Subreg) { 4797 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32); 4798 SDNode *Result = getMachineNode(TargetInstrInfo::INSERT_SUBREG, DL, 4799 VT, Operand, Subreg, SRIdxVal); 4800 return SDValue(Result, 0); 4801} 4802 4803/// getNodeIfExists - Get the specified node if it's already available, or 4804/// else return NULL. 4805SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList, 4806 const SDValue *Ops, unsigned NumOps) { 4807 if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { 4808 FoldingSetNodeID ID; 4809 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 4810 void *IP = 0; 4811 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 4812 return E; 4813 } 4814 return NULL; 4815} 4816 4817/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 4818/// This can cause recursive merging of nodes in the DAG. 4819/// 4820/// This version assumes From has a single result value. 4821/// 4822void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To, 4823 DAGUpdateListener *UpdateListener) { 4824 SDNode *From = FromN.getNode(); 4825 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 && 4826 "Cannot replace with this method!"); 4827 assert(From != To.getNode() && "Cannot replace uses of with self"); 4828 4829 // Iterate over all the existing uses of From. New uses will be added 4830 // to the beginning of the use list, which we avoid visiting. 4831 // This specifically avoids visiting uses of From that arise while the 4832 // replacement is happening, because any such uses would be the result 4833 // of CSE: If an existing node looks like From after one of its operands 4834 // is replaced by To, we don't want to replace of all its users with To 4835 // too. See PR3018 for more info. 4836 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); 4837 while (UI != UE) { 4838 SDNode *User = *UI; 4839 4840 // This node is about to morph, remove its old self from the CSE maps. 4841 RemoveNodeFromCSEMaps(User); 4842 4843 // A user can appear in a use list multiple times, and when this 4844 // happens the uses are usually next to each other in the list. 4845 // To help reduce the number of CSE recomputations, process all 4846 // the uses of this user that we can find this way. 4847 do { 4848 SDUse &Use = UI.getUse(); 4849 ++UI; 4850 Use.set(To); 4851 } while (UI != UE && *UI == User); 4852 4853 // Now that we have modified User, add it back to the CSE maps. If it 4854 // already exists there, recursively merge the results together. 4855 AddModifiedNodeToCSEMaps(User, UpdateListener); 4856 } 4857} 4858 4859/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 4860/// This can cause recursive merging of nodes in the DAG. 4861/// 4862/// This version assumes that for each value of From, there is a 4863/// corresponding value in To in the same position with the same type. 4864/// 4865void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, 4866 DAGUpdateListener *UpdateListener) { 4867#ifndef NDEBUG 4868 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i) 4869 assert((!From->hasAnyUseOfValue(i) || 4870 From->getValueType(i) == To->getValueType(i)) && 4871 "Cannot use this version of ReplaceAllUsesWith!"); 4872#endif 4873 4874 // Handle the trivial case. 4875 if (From == To) 4876 return; 4877 4878 // Iterate over just the existing users of From. See the comments in 4879 // the ReplaceAllUsesWith above. 4880 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); 4881 while (UI != UE) { 4882 SDNode *User = *UI; 4883 4884 // This node is about to morph, remove its old self from the CSE maps. 4885 RemoveNodeFromCSEMaps(User); 4886 4887 // A user can appear in a use list multiple times, and when this 4888 // happens the uses are usually next to each other in the list. 4889 // To help reduce the number of CSE recomputations, process all 4890 // the uses of this user that we can find this way. 4891 do { 4892 SDUse &Use = UI.getUse(); 4893 ++UI; 4894 Use.setNode(To); 4895 } while (UI != UE && *UI == User); 4896 4897 // Now that we have modified User, add it back to the CSE maps. If it 4898 // already exists there, recursively merge the results together. 4899 AddModifiedNodeToCSEMaps(User, UpdateListener); 4900 } 4901} 4902 4903/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 4904/// This can cause recursive merging of nodes in the DAG. 4905/// 4906/// This version can replace From with any result values. To must match the 4907/// number and types of values returned by From. 4908void SelectionDAG::ReplaceAllUsesWith(SDNode *From, 4909 const SDValue *To, 4910 DAGUpdateListener *UpdateListener) { 4911 if (From->getNumValues() == 1) // Handle the simple case efficiently. 4912 return ReplaceAllUsesWith(SDValue(From, 0), To[0], UpdateListener); 4913 4914 // Iterate over just the existing users of From. See the comments in 4915 // the ReplaceAllUsesWith above. 4916 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); 4917 while (UI != UE) { 4918 SDNode *User = *UI; 4919 4920 // This node is about to morph, remove its old self from the CSE maps. 4921 RemoveNodeFromCSEMaps(User); 4922 4923 // A user can appear in a use list multiple times, and when this 4924 // happens the uses are usually next to each other in the list. 4925 // To help reduce the number of CSE recomputations, process all 4926 // the uses of this user that we can find this way. 4927 do { 4928 SDUse &Use = UI.getUse(); 4929 const SDValue &ToOp = To[Use.getResNo()]; 4930 ++UI; 4931 Use.set(ToOp); 4932 } while (UI != UE && *UI == User); 4933 4934 // Now that we have modified User, add it back to the CSE maps. If it 4935 // already exists there, recursively merge the results together. 4936 AddModifiedNodeToCSEMaps(User, UpdateListener); 4937 } 4938} 4939 4940/// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 4941/// uses of other values produced by From.getNode() alone. The Deleted 4942/// vector is handled the same way as for ReplaceAllUsesWith. 4943void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To, 4944 DAGUpdateListener *UpdateListener){ 4945 // Handle the really simple, really trivial case efficiently. 4946 if (From == To) return; 4947 4948 // Handle the simple, trivial, case efficiently. 4949 if (From.getNode()->getNumValues() == 1) { 4950 ReplaceAllUsesWith(From, To, UpdateListener); 4951 return; 4952 } 4953 4954 // Iterate over just the existing users of From. See the comments in 4955 // the ReplaceAllUsesWith above. 4956 SDNode::use_iterator UI = From.getNode()->use_begin(), 4957 UE = From.getNode()->use_end(); 4958 while (UI != UE) { 4959 SDNode *User = *UI; 4960 bool UserRemovedFromCSEMaps = false; 4961 4962 // A user can appear in a use list multiple times, and when this 4963 // happens the uses are usually next to each other in the list. 4964 // To help reduce the number of CSE recomputations, process all 4965 // the uses of this user that we can find this way. 4966 do { 4967 SDUse &Use = UI.getUse(); 4968 4969 // Skip uses of different values from the same node. 4970 if (Use.getResNo() != From.getResNo()) { 4971 ++UI; 4972 continue; 4973 } 4974 4975 // If this node hasn't been modified yet, it's still in the CSE maps, 4976 // so remove its old self from the CSE maps. 4977 if (!UserRemovedFromCSEMaps) { 4978 RemoveNodeFromCSEMaps(User); 4979 UserRemovedFromCSEMaps = true; 4980 } 4981 4982 ++UI; 4983 Use.set(To); 4984 } while (UI != UE && *UI == User); 4985 4986 // We are iterating over all uses of the From node, so if a use 4987 // doesn't use the specific value, no changes are made. 4988 if (!UserRemovedFromCSEMaps) 4989 continue; 4990 4991 // Now that we have modified User, add it back to the CSE maps. If it 4992 // already exists there, recursively merge the results together. 4993 AddModifiedNodeToCSEMaps(User, UpdateListener); 4994 } 4995} 4996 4997namespace { 4998 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith 4999 /// to record information about a use. 5000 struct UseMemo { 5001 SDNode *User; 5002 unsigned Index; 5003 SDUse *Use; 5004 }; 5005 5006 /// operator< - Sort Memos by User. 5007 bool operator<(const UseMemo &L, const UseMemo &R) { 5008 return (intptr_t)L.User < (intptr_t)R.User; 5009 } 5010} 5011 5012/// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving 5013/// uses of other values produced by From.getNode() alone. The same value 5014/// may appear in both the From and To list. The Deleted vector is 5015/// handled the same way as for ReplaceAllUsesWith. 5016void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From, 5017 const SDValue *To, 5018 unsigned Num, 5019 DAGUpdateListener *UpdateListener){ 5020 // Handle the simple, trivial case efficiently. 5021 if (Num == 1) 5022 return ReplaceAllUsesOfValueWith(*From, *To, UpdateListener); 5023 5024 // Read up all the uses and make records of them. This helps 5025 // processing new uses that are introduced during the 5026 // replacement process. 5027 SmallVector<UseMemo, 4> Uses; 5028 for (unsigned i = 0; i != Num; ++i) { 5029 unsigned FromResNo = From[i].getResNo(); 5030 SDNode *FromNode = From[i].getNode(); 5031 for (SDNode::use_iterator UI = FromNode->use_begin(), 5032 E = FromNode->use_end(); UI != E; ++UI) { 5033 SDUse &Use = UI.getUse(); 5034 if (Use.getResNo() == FromResNo) { 5035 UseMemo Memo = { *UI, i, &Use }; 5036 Uses.push_back(Memo); 5037 } 5038 } 5039 } 5040 5041 // Sort the uses, so that all the uses from a given User are together. 5042 std::sort(Uses.begin(), Uses.end()); 5043 5044 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size(); 5045 UseIndex != UseIndexEnd; ) { 5046 // We know that this user uses some value of From. If it is the right 5047 // value, update it. 5048 SDNode *User = Uses[UseIndex].User; 5049 5050 // This node is about to morph, remove its old self from the CSE maps. 5051 RemoveNodeFromCSEMaps(User); 5052 5053 // The Uses array is sorted, so all the uses for a given User 5054 // are next to each other in the list. 5055 // To help reduce the number of CSE recomputations, process all 5056 // the uses of this user that we can find this way. 5057 do { 5058 unsigned i = Uses[UseIndex].Index; 5059 SDUse &Use = *Uses[UseIndex].Use; 5060 ++UseIndex; 5061 5062 Use.set(To[i]); 5063 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User); 5064 5065 // Now that we have modified User, add it back to the CSE maps. If it 5066 // already exists there, recursively merge the results together. 5067 AddModifiedNodeToCSEMaps(User, UpdateListener); 5068 } 5069} 5070 5071/// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 5072/// based on their topological order. It returns the maximum id and a vector 5073/// of the SDNodes* in assigned order by reference. 5074unsigned SelectionDAG::AssignTopologicalOrder() { 5075 5076 unsigned DAGSize = 0; 5077 5078 // SortedPos tracks the progress of the algorithm. Nodes before it are 5079 // sorted, nodes after it are unsorted. When the algorithm completes 5080 // it is at the end of the list. 5081 allnodes_iterator SortedPos = allnodes_begin(); 5082 5083 // Visit all the nodes. Move nodes with no operands to the front of 5084 // the list immediately. Annotate nodes that do have operands with their 5085 // operand count. Before we do this, the Node Id fields of the nodes 5086 // may contain arbitrary values. After, the Node Id fields for nodes 5087 // before SortedPos will contain the topological sort index, and the 5088 // Node Id fields for nodes At SortedPos and after will contain the 5089 // count of outstanding operands. 5090 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) { 5091 SDNode *N = I++; 5092 unsigned Degree = N->getNumOperands(); 5093 if (Degree == 0) { 5094 // A node with no uses, add it to the result array immediately. 5095 N->setNodeId(DAGSize++); 5096 allnodes_iterator Q = N; 5097 if (Q != SortedPos) 5098 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q)); 5099 ++SortedPos; 5100 } else { 5101 // Temporarily use the Node Id as scratch space for the degree count. 5102 N->setNodeId(Degree); 5103 } 5104 } 5105 5106 // Visit all the nodes. As we iterate, moves nodes into sorted order, 5107 // such that by the time the end is reached all nodes will be sorted. 5108 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) { 5109 SDNode *N = I; 5110 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 5111 UI != UE; ++UI) { 5112 SDNode *P = *UI; 5113 unsigned Degree = P->getNodeId(); 5114 --Degree; 5115 if (Degree == 0) { 5116 // All of P's operands are sorted, so P may sorted now. 5117 P->setNodeId(DAGSize++); 5118 if (P != SortedPos) 5119 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P)); 5120 ++SortedPos; 5121 } else { 5122 // Update P's outstanding operand count. 5123 P->setNodeId(Degree); 5124 } 5125 } 5126 } 5127 5128 assert(SortedPos == AllNodes.end() && 5129 "Topological sort incomplete!"); 5130 assert(AllNodes.front().getOpcode() == ISD::EntryToken && 5131 "First node in topological sort is not the entry token!"); 5132 assert(AllNodes.front().getNodeId() == 0 && 5133 "First node in topological sort has non-zero id!"); 5134 assert(AllNodes.front().getNumOperands() == 0 && 5135 "First node in topological sort has operands!"); 5136 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 && 5137 "Last node in topologic sort has unexpected id!"); 5138 assert(AllNodes.back().use_empty() && 5139 "Last node in topologic sort has users!"); 5140 assert(DAGSize == allnodes_size() && "Node count mismatch!"); 5141 return DAGSize; 5142} 5143 5144 5145 5146//===----------------------------------------------------------------------===// 5147// SDNode Class 5148//===----------------------------------------------------------------------===// 5149 5150HandleSDNode::~HandleSDNode() { 5151 DropOperands(); 5152} 5153 5154GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, const GlobalValue *GA, 5155 EVT VT, int64_t o, unsigned char TF) 5156 : SDNode(Opc, DebugLoc::getUnknownLoc(), getSDVTList(VT)), 5157 Offset(o), TargetFlags(TF) { 5158 TheGlobal = const_cast<GlobalValue*>(GA); 5159} 5160 5161MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt, 5162 MachineMemOperand *mmo) 5163 : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) { 5164 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile()); 5165 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!"); 5166 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!"); 5167} 5168 5169MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, 5170 const SDValue *Ops, unsigned NumOps, EVT memvt, 5171 MachineMemOperand *mmo) 5172 : SDNode(Opc, dl, VTs, Ops, NumOps), 5173 MemoryVT(memvt), MMO(mmo) { 5174 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile()); 5175 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!"); 5176 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!"); 5177} 5178 5179/// Profile - Gather unique data for the node. 5180/// 5181void SDNode::Profile(FoldingSetNodeID &ID) const { 5182 AddNodeIDNode(ID, this); 5183} 5184 5185namespace { 5186 struct EVTArray { 5187 std::vector<EVT> VTs; 5188 5189 EVTArray() { 5190 VTs.reserve(MVT::LAST_VALUETYPE); 5191 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i) 5192 VTs.push_back(MVT((MVT::SimpleValueType)i)); 5193 } 5194 }; 5195} 5196 5197static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs; 5198static ManagedStatic<EVTArray> SimpleVTArray; 5199static ManagedStatic<sys::SmartMutex<true> > VTMutex; 5200 5201/// getValueTypeList - Return a pointer to the specified value type. 5202/// 5203const EVT *SDNode::getValueTypeList(EVT VT) { 5204 if (VT.isExtended()) { 5205 sys::SmartScopedLock<true> Lock(*VTMutex); 5206 return &(*EVTs->insert(VT).first); 5207 } else { 5208 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy]; 5209 } 5210} 5211 5212/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 5213/// indicated value. This method ignores uses of other values defined by this 5214/// operation. 5215bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { 5216 assert(Value < getNumValues() && "Bad value!"); 5217 5218 // TODO: Only iterate over uses of a given value of the node 5219 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { 5220 if (UI.getUse().getResNo() == Value) { 5221 if (NUses == 0) 5222 return false; 5223 --NUses; 5224 } 5225 } 5226 5227 // Found exactly the right number of uses? 5228 return NUses == 0; 5229} 5230 5231 5232/// hasAnyUseOfValue - Return true if there are any use of the indicated 5233/// value. This method ignores uses of other values defined by this operation. 5234bool SDNode::hasAnyUseOfValue(unsigned Value) const { 5235 assert(Value < getNumValues() && "Bad value!"); 5236 5237 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) 5238 if (UI.getUse().getResNo() == Value) 5239 return true; 5240 5241 return false; 5242} 5243 5244 5245/// isOnlyUserOf - Return true if this node is the only use of N. 5246/// 5247bool SDNode::isOnlyUserOf(SDNode *N) const { 5248 bool Seen = false; 5249 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 5250 SDNode *User = *I; 5251 if (User == this) 5252 Seen = true; 5253 else 5254 return false; 5255 } 5256 5257 return Seen; 5258} 5259 5260/// isOperand - Return true if this node is an operand of N. 5261/// 5262bool SDValue::isOperandOf(SDNode *N) const { 5263 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 5264 if (*this == N->getOperand(i)) 5265 return true; 5266 return false; 5267} 5268 5269bool SDNode::isOperandOf(SDNode *N) const { 5270 for (unsigned i = 0, e = N->NumOperands; i != e; ++i) 5271 if (this == N->OperandList[i].getNode()) 5272 return true; 5273 return false; 5274} 5275 5276/// reachesChainWithoutSideEffects - Return true if this operand (which must 5277/// be a chain) reaches the specified operand without crossing any 5278/// side-effecting instructions. In practice, this looks through token 5279/// factors and non-volatile loads. In order to remain efficient, this only 5280/// looks a couple of nodes in, it does not do an exhaustive search. 5281bool SDValue::reachesChainWithoutSideEffects(SDValue Dest, 5282 unsigned Depth) const { 5283 if (*this == Dest) return true; 5284 5285 // Don't search too deeply, we just want to be able to see through 5286 // TokenFactor's etc. 5287 if (Depth == 0) return false; 5288 5289 // If this is a token factor, all inputs to the TF happen in parallel. If any 5290 // of the operands of the TF reach dest, then we can do the xform. 5291 if (getOpcode() == ISD::TokenFactor) { 5292 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 5293 if (getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1)) 5294 return true; 5295 return false; 5296 } 5297 5298 // Loads don't have side effects, look through them. 5299 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) { 5300 if (!Ld->isVolatile()) 5301 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1); 5302 } 5303 return false; 5304} 5305 5306/// isPredecessorOf - Return true if this node is a predecessor of N. This node 5307/// is either an operand of N or it can be reached by traversing up the operands. 5308/// NOTE: this is an expensive method. Use it carefully. 5309bool SDNode::isPredecessorOf(SDNode *N) const { 5310 SmallPtrSet<SDNode *, 32> Visited; 5311 SmallVector<SDNode *, 16> Worklist; 5312 Worklist.push_back(N); 5313 5314 do { 5315 N = Worklist.pop_back_val(); 5316 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 5317 SDNode *Op = N->getOperand(i).getNode(); 5318 if (Op == this) 5319 return true; 5320 if (Visited.insert(Op)) 5321 Worklist.push_back(Op); 5322 } 5323 } while (!Worklist.empty()); 5324 5325 return false; 5326} 5327 5328uint64_t SDNode::getConstantOperandVal(unsigned Num) const { 5329 assert(Num < NumOperands && "Invalid child # of SDNode!"); 5330 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue(); 5331} 5332 5333std::string SDNode::getOperationName(const SelectionDAG *G) const { 5334 switch (getOpcode()) { 5335 default: 5336 if (getOpcode() < ISD::BUILTIN_OP_END) 5337 return "<<Unknown DAG Node>>"; 5338 if (isMachineOpcode()) { 5339 if (G) 5340 if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo()) 5341 if (getMachineOpcode() < TII->getNumOpcodes()) 5342 return TII->get(getMachineOpcode()).getName(); 5343 return "<<Unknown Machine Node>>"; 5344 } 5345 if (G) { 5346 const TargetLowering &TLI = G->getTargetLoweringInfo(); 5347 const char *Name = TLI.getTargetNodeName(getOpcode()); 5348 if (Name) return Name; 5349 return "<<Unknown Target Node>>"; 5350 } 5351 return "<<Unknown Node>>"; 5352 5353#ifndef NDEBUG 5354 case ISD::DELETED_NODE: 5355 return "<<Deleted Node!>>"; 5356#endif 5357 case ISD::PREFETCH: return "Prefetch"; 5358 case ISD::MEMBARRIER: return "MemBarrier"; 5359 case ISD::ATOMIC_CMP_SWAP: return "AtomicCmpSwap"; 5360 case ISD::ATOMIC_SWAP: return "AtomicSwap"; 5361 case ISD::ATOMIC_LOAD_ADD: return "AtomicLoadAdd"; 5362 case ISD::ATOMIC_LOAD_SUB: return "AtomicLoadSub"; 5363 case ISD::ATOMIC_LOAD_AND: return "AtomicLoadAnd"; 5364 case ISD::ATOMIC_LOAD_OR: return "AtomicLoadOr"; 5365 case ISD::ATOMIC_LOAD_XOR: return "AtomicLoadXor"; 5366 case ISD::ATOMIC_LOAD_NAND: return "AtomicLoadNand"; 5367 case ISD::ATOMIC_LOAD_MIN: return "AtomicLoadMin"; 5368 case ISD::ATOMIC_LOAD_MAX: return "AtomicLoadMax"; 5369 case ISD::ATOMIC_LOAD_UMIN: return "AtomicLoadUMin"; 5370 case ISD::ATOMIC_LOAD_UMAX: return "AtomicLoadUMax"; 5371 case ISD::PCMARKER: return "PCMarker"; 5372 case ISD::READCYCLECOUNTER: return "ReadCycleCounter"; 5373 case ISD::SRCVALUE: return "SrcValue"; 5374 case ISD::EntryToken: return "EntryToken"; 5375 case ISD::TokenFactor: return "TokenFactor"; 5376 case ISD::AssertSext: return "AssertSext"; 5377 case ISD::AssertZext: return "AssertZext"; 5378 5379 case ISD::BasicBlock: return "BasicBlock"; 5380 case ISD::VALUETYPE: return "ValueType"; 5381 case ISD::Register: return "Register"; 5382 5383 case ISD::Constant: return "Constant"; 5384 case ISD::ConstantFP: return "ConstantFP"; 5385 case ISD::GlobalAddress: return "GlobalAddress"; 5386 case ISD::GlobalTLSAddress: return "GlobalTLSAddress"; 5387 case ISD::FrameIndex: return "FrameIndex"; 5388 case ISD::JumpTable: return "JumpTable"; 5389 case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE"; 5390 case ISD::RETURNADDR: return "RETURNADDR"; 5391 case ISD::FRAMEADDR: return "FRAMEADDR"; 5392 case ISD::FRAME_TO_ARGS_OFFSET: return "FRAME_TO_ARGS_OFFSET"; 5393 case ISD::EXCEPTIONADDR: return "EXCEPTIONADDR"; 5394 case ISD::LSDAADDR: return "LSDAADDR"; 5395 case ISD::EHSELECTION: return "EHSELECTION"; 5396 case ISD::EH_RETURN: return "EH_RETURN"; 5397 case ISD::ConstantPool: return "ConstantPool"; 5398 case ISD::ExternalSymbol: return "ExternalSymbol"; 5399 case ISD::BlockAddress: return "BlockAddress"; 5400 case ISD::INTRINSIC_WO_CHAIN: 5401 case ISD::INTRINSIC_VOID: 5402 case ISD::INTRINSIC_W_CHAIN: { 5403 unsigned OpNo = getOpcode() == ISD::INTRINSIC_WO_CHAIN ? 0 : 1; 5404 unsigned IID = cast<ConstantSDNode>(getOperand(OpNo))->getZExtValue(); 5405 if (IID < Intrinsic::num_intrinsics) 5406 return Intrinsic::getName((Intrinsic::ID)IID); 5407 else if (const TargetIntrinsicInfo *TII = G->getTarget().getIntrinsicInfo()) 5408 return TII->getName(IID); 5409 llvm_unreachable("Invalid intrinsic ID"); 5410 } 5411 5412 case ISD::BUILD_VECTOR: return "BUILD_VECTOR"; 5413 case ISD::TargetConstant: return "TargetConstant"; 5414 case ISD::TargetConstantFP:return "TargetConstantFP"; 5415 case ISD::TargetGlobalAddress: return "TargetGlobalAddress"; 5416 case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress"; 5417 case ISD::TargetFrameIndex: return "TargetFrameIndex"; 5418 case ISD::TargetJumpTable: return "TargetJumpTable"; 5419 case ISD::TargetConstantPool: return "TargetConstantPool"; 5420 case ISD::TargetExternalSymbol: return "TargetExternalSymbol"; 5421 case ISD::TargetBlockAddress: return "TargetBlockAddress"; 5422 5423 case ISD::CopyToReg: return "CopyToReg"; 5424 case ISD::CopyFromReg: return "CopyFromReg"; 5425 case ISD::UNDEF: return "undef"; 5426 case ISD::MERGE_VALUES: return "merge_values"; 5427 case ISD::INLINEASM: return "inlineasm"; 5428 case ISD::EH_LABEL: return "eh_label"; 5429 case ISD::HANDLENODE: return "handlenode"; 5430 5431 // Unary operators 5432 case ISD::FABS: return "fabs"; 5433 case ISD::FNEG: return "fneg"; 5434 case ISD::FSQRT: return "fsqrt"; 5435 case ISD::FSIN: return "fsin"; 5436 case ISD::FCOS: return "fcos"; 5437 case ISD::FPOWI: return "fpowi"; 5438 case ISD::FPOW: return "fpow"; 5439 case ISD::FTRUNC: return "ftrunc"; 5440 case ISD::FFLOOR: return "ffloor"; 5441 case ISD::FCEIL: return "fceil"; 5442 case ISD::FRINT: return "frint"; 5443 case ISD::FNEARBYINT: return "fnearbyint"; 5444 5445 // Binary operators 5446 case ISD::ADD: return "add"; 5447 case ISD::SUB: return "sub"; 5448 case ISD::MUL: return "mul"; 5449 case ISD::MULHU: return "mulhu"; 5450 case ISD::MULHS: return "mulhs"; 5451 case ISD::SDIV: return "sdiv"; 5452 case ISD::UDIV: return "udiv"; 5453 case ISD::SREM: return "srem"; 5454 case ISD::UREM: return "urem"; 5455 case ISD::SMUL_LOHI: return "smul_lohi"; 5456 case ISD::UMUL_LOHI: return "umul_lohi"; 5457 case ISD::SDIVREM: return "sdivrem"; 5458 case ISD::UDIVREM: return "udivrem"; 5459 case ISD::AND: return "and"; 5460 case ISD::OR: return "or"; 5461 case ISD::XOR: return "xor"; 5462 case ISD::SHL: return "shl"; 5463 case ISD::SRA: return "sra"; 5464 case ISD::SRL: return "srl"; 5465 case ISD::ROTL: return "rotl"; 5466 case ISD::ROTR: return "rotr"; 5467 case ISD::FADD: return "fadd"; 5468 case ISD::FSUB: return "fsub"; 5469 case ISD::FMUL: return "fmul"; 5470 case ISD::FDIV: return "fdiv"; 5471 case ISD::FREM: return "frem"; 5472 case ISD::FCOPYSIGN: return "fcopysign"; 5473 case ISD::FGETSIGN: return "fgetsign"; 5474 5475 case ISD::SETCC: return "setcc"; 5476 case ISD::VSETCC: return "vsetcc"; 5477 case ISD::SELECT: return "select"; 5478 case ISD::SELECT_CC: return "select_cc"; 5479 case ISD::INSERT_VECTOR_ELT: return "insert_vector_elt"; 5480 case ISD::EXTRACT_VECTOR_ELT: return "extract_vector_elt"; 5481 case ISD::CONCAT_VECTORS: return "concat_vectors"; 5482 case ISD::EXTRACT_SUBVECTOR: return "extract_subvector"; 5483 case ISD::SCALAR_TO_VECTOR: return "scalar_to_vector"; 5484 case ISD::VECTOR_SHUFFLE: return "vector_shuffle"; 5485 case ISD::CARRY_FALSE: return "carry_false"; 5486 case ISD::ADDC: return "addc"; 5487 case ISD::ADDE: return "adde"; 5488 case ISD::SADDO: return "saddo"; 5489 case ISD::UADDO: return "uaddo"; 5490 case ISD::SSUBO: return "ssubo"; 5491 case ISD::USUBO: return "usubo"; 5492 case ISD::SMULO: return "smulo"; 5493 case ISD::UMULO: return "umulo"; 5494 case ISD::SUBC: return "subc"; 5495 case ISD::SUBE: return "sube"; 5496 case ISD::SHL_PARTS: return "shl_parts"; 5497 case ISD::SRA_PARTS: return "sra_parts"; 5498 case ISD::SRL_PARTS: return "srl_parts"; 5499 5500 // Conversion operators. 5501 case ISD::SIGN_EXTEND: return "sign_extend"; 5502 case ISD::ZERO_EXTEND: return "zero_extend"; 5503 case ISD::ANY_EXTEND: return "any_extend"; 5504 case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg"; 5505 case ISD::TRUNCATE: return "truncate"; 5506 case ISD::FP_ROUND: return "fp_round"; 5507 case ISD::FLT_ROUNDS_: return "flt_rounds"; 5508 case ISD::FP_ROUND_INREG: return "fp_round_inreg"; 5509 case ISD::FP_EXTEND: return "fp_extend"; 5510 5511 case ISD::SINT_TO_FP: return "sint_to_fp"; 5512 case ISD::UINT_TO_FP: return "uint_to_fp"; 5513 case ISD::FP_TO_SINT: return "fp_to_sint"; 5514 case ISD::FP_TO_UINT: return "fp_to_uint"; 5515 case ISD::BIT_CONVERT: return "bit_convert"; 5516 5517 case ISD::CONVERT_RNDSAT: { 5518 switch (cast<CvtRndSatSDNode>(this)->getCvtCode()) { 5519 default: llvm_unreachable("Unknown cvt code!"); 5520 case ISD::CVT_FF: return "cvt_ff"; 5521 case ISD::CVT_FS: return "cvt_fs"; 5522 case ISD::CVT_FU: return "cvt_fu"; 5523 case ISD::CVT_SF: return "cvt_sf"; 5524 case ISD::CVT_UF: return "cvt_uf"; 5525 case ISD::CVT_SS: return "cvt_ss"; 5526 case ISD::CVT_SU: return "cvt_su"; 5527 case ISD::CVT_US: return "cvt_us"; 5528 case ISD::CVT_UU: return "cvt_uu"; 5529 } 5530 } 5531 5532 // Control flow instructions 5533 case ISD::BR: return "br"; 5534 case ISD::BRIND: return "brind"; 5535 case ISD::BR_JT: return "br_jt"; 5536 case ISD::BRCOND: return "brcond"; 5537 case ISD::BR_CC: return "br_cc"; 5538 case ISD::CALLSEQ_START: return "callseq_start"; 5539 case ISD::CALLSEQ_END: return "callseq_end"; 5540 5541 // Other operators 5542 case ISD::LOAD: return "load"; 5543 case ISD::STORE: return "store"; 5544 case ISD::VAARG: return "vaarg"; 5545 case ISD::VACOPY: return "vacopy"; 5546 case ISD::VAEND: return "vaend"; 5547 case ISD::VASTART: return "vastart"; 5548 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc"; 5549 case ISD::EXTRACT_ELEMENT: return "extract_element"; 5550 case ISD::BUILD_PAIR: return "build_pair"; 5551 case ISD::STACKSAVE: return "stacksave"; 5552 case ISD::STACKRESTORE: return "stackrestore"; 5553 case ISD::TRAP: return "trap"; 5554 5555 // Bit manipulation 5556 case ISD::BSWAP: return "bswap"; 5557 case ISD::CTPOP: return "ctpop"; 5558 case ISD::CTTZ: return "cttz"; 5559 case ISD::CTLZ: return "ctlz"; 5560 5561 // Trampolines 5562 case ISD::TRAMPOLINE: return "trampoline"; 5563 5564 case ISD::CONDCODE: 5565 switch (cast<CondCodeSDNode>(this)->get()) { 5566 default: llvm_unreachable("Unknown setcc condition!"); 5567 case ISD::SETOEQ: return "setoeq"; 5568 case ISD::SETOGT: return "setogt"; 5569 case ISD::SETOGE: return "setoge"; 5570 case ISD::SETOLT: return "setolt"; 5571 case ISD::SETOLE: return "setole"; 5572 case ISD::SETONE: return "setone"; 5573 5574 case ISD::SETO: return "seto"; 5575 case ISD::SETUO: return "setuo"; 5576 case ISD::SETUEQ: return "setue"; 5577 case ISD::SETUGT: return "setugt"; 5578 case ISD::SETUGE: return "setuge"; 5579 case ISD::SETULT: return "setult"; 5580 case ISD::SETULE: return "setule"; 5581 case ISD::SETUNE: return "setune"; 5582 5583 case ISD::SETEQ: return "seteq"; 5584 case ISD::SETGT: return "setgt"; 5585 case ISD::SETGE: return "setge"; 5586 case ISD::SETLT: return "setlt"; 5587 case ISD::SETLE: return "setle"; 5588 case ISD::SETNE: return "setne"; 5589 } 5590 } 5591} 5592 5593const char *SDNode::getIndexedModeName(ISD::MemIndexedMode AM) { 5594 switch (AM) { 5595 default: 5596 return ""; 5597 case ISD::PRE_INC: 5598 return "<pre-inc>"; 5599 case ISD::PRE_DEC: 5600 return "<pre-dec>"; 5601 case ISD::POST_INC: 5602 return "<post-inc>"; 5603 case ISD::POST_DEC: 5604 return "<post-dec>"; 5605 } 5606} 5607 5608std::string ISD::ArgFlagsTy::getArgFlagsString() { 5609 std::string S = "< "; 5610 5611 if (isZExt()) 5612 S += "zext "; 5613 if (isSExt()) 5614 S += "sext "; 5615 if (isInReg()) 5616 S += "inreg "; 5617 if (isSRet()) 5618 S += "sret "; 5619 if (isByVal()) 5620 S += "byval "; 5621 if (isNest()) 5622 S += "nest "; 5623 if (getByValAlign()) 5624 S += "byval-align:" + utostr(getByValAlign()) + " "; 5625 if (getOrigAlign()) 5626 S += "orig-align:" + utostr(getOrigAlign()) + " "; 5627 if (getByValSize()) 5628 S += "byval-size:" + utostr(getByValSize()) + " "; 5629 return S + ">"; 5630} 5631 5632void SDNode::dump() const { dump(0); } 5633void SDNode::dump(const SelectionDAG *G) const { 5634 print(errs(), G); 5635} 5636 5637void SDNode::print_types(raw_ostream &OS, const SelectionDAG *G) const { 5638 OS << (void*)this << ": "; 5639 5640 for (unsigned i = 0, e = getNumValues(); i != e; ++i) { 5641 if (i) OS << ","; 5642 if (getValueType(i) == MVT::Other) 5643 OS << "ch"; 5644 else 5645 OS << getValueType(i).getEVTString(); 5646 } 5647 OS << " = " << getOperationName(G); 5648} 5649 5650void SDNode::print_details(raw_ostream &OS, const SelectionDAG *G) const { 5651 if (const MachineSDNode *MN = dyn_cast<MachineSDNode>(this)) { 5652 if (!MN->memoperands_empty()) { 5653 OS << "<"; 5654 OS << "Mem:"; 5655 for (MachineSDNode::mmo_iterator i = MN->memoperands_begin(), 5656 e = MN->memoperands_end(); i != e; ++i) { 5657 OS << **i; 5658 if (next(i) != e) 5659 OS << " "; 5660 } 5661 OS << ">"; 5662 } 5663 } else if (const ShuffleVectorSDNode *SVN = 5664 dyn_cast<ShuffleVectorSDNode>(this)) { 5665 OS << "<"; 5666 for (unsigned i = 0, e = ValueList[0].getVectorNumElements(); i != e; ++i) { 5667 int Idx = SVN->getMaskElt(i); 5668 if (i) OS << ","; 5669 if (Idx < 0) 5670 OS << "u"; 5671 else 5672 OS << Idx; 5673 } 5674 OS << ">"; 5675 } else if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { 5676 OS << '<' << CSDN->getAPIntValue() << '>'; 5677 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { 5678 if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEsingle) 5679 OS << '<' << CSDN->getValueAPF().convertToFloat() << '>'; 5680 else if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEdouble) 5681 OS << '<' << CSDN->getValueAPF().convertToDouble() << '>'; 5682 else { 5683 OS << "<APFloat("; 5684 CSDN->getValueAPF().bitcastToAPInt().dump(); 5685 OS << ")>"; 5686 } 5687 } else if (const GlobalAddressSDNode *GADN = 5688 dyn_cast<GlobalAddressSDNode>(this)) { 5689 int64_t offset = GADN->getOffset(); 5690 OS << '<'; 5691 WriteAsOperand(OS, GADN->getGlobal()); 5692 OS << '>'; 5693 if (offset > 0) 5694 OS << " + " << offset; 5695 else 5696 OS << " " << offset; 5697 if (unsigned int TF = GADN->getTargetFlags()) 5698 OS << " [TF=" << TF << ']'; 5699 } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) { 5700 OS << "<" << FIDN->getIndex() << ">"; 5701 } else if (const JumpTableSDNode *JTDN = dyn_cast<JumpTableSDNode>(this)) { 5702 OS << "<" << JTDN->getIndex() << ">"; 5703 if (unsigned int TF = JTDN->getTargetFlags()) 5704 OS << " [TF=" << TF << ']'; 5705 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ 5706 int offset = CP->getOffset(); 5707 if (CP->isMachineConstantPoolEntry()) 5708 OS << "<" << *CP->getMachineCPVal() << ">"; 5709 else 5710 OS << "<" << *CP->getConstVal() << ">"; 5711 if (offset > 0) 5712 OS << " + " << offset; 5713 else 5714 OS << " " << offset; 5715 if (unsigned int TF = CP->getTargetFlags()) 5716 OS << " [TF=" << TF << ']'; 5717 } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) { 5718 OS << "<"; 5719 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); 5720 if (LBB) 5721 OS << LBB->getName() << " "; 5722 OS << (const void*)BBDN->getBasicBlock() << ">"; 5723 } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) { 5724 if (G && R->getReg() && 5725 TargetRegisterInfo::isPhysicalRegister(R->getReg())) { 5726 OS << " %" << G->getTarget().getRegisterInfo()->getName(R->getReg()); 5727 } else { 5728 OS << " %reg" << R->getReg(); 5729 } 5730 } else if (const ExternalSymbolSDNode *ES = 5731 dyn_cast<ExternalSymbolSDNode>(this)) { 5732 OS << "'" << ES->getSymbol() << "'"; 5733 if (unsigned int TF = ES->getTargetFlags()) 5734 OS << " [TF=" << TF << ']'; 5735 } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) { 5736 if (M->getValue()) 5737 OS << "<" << M->getValue() << ">"; 5738 else 5739 OS << "<null>"; 5740 } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) { 5741 OS << ":" << N->getVT().getEVTString(); 5742 } 5743 else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) { 5744 OS << "<" << *LD->getMemOperand(); 5745 5746 bool doExt = true; 5747 switch (LD->getExtensionType()) { 5748 default: doExt = false; break; 5749 case ISD::EXTLOAD: OS << ", anyext"; break; 5750 case ISD::SEXTLOAD: OS << ", sext"; break; 5751 case ISD::ZEXTLOAD: OS << ", zext"; break; 5752 } 5753 if (doExt) 5754 OS << " from " << LD->getMemoryVT().getEVTString(); 5755 5756 const char *AM = getIndexedModeName(LD->getAddressingMode()); 5757 if (*AM) 5758 OS << ", " << AM; 5759 5760 OS << ">"; 5761 } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) { 5762 OS << "<" << *ST->getMemOperand(); 5763 5764 if (ST->isTruncatingStore()) 5765 OS << ", trunc to " << ST->getMemoryVT().getEVTString(); 5766 5767 const char *AM = getIndexedModeName(ST->getAddressingMode()); 5768 if (*AM) 5769 OS << ", " << AM; 5770 5771 OS << ">"; 5772 } else if (const MemSDNode* M = dyn_cast<MemSDNode>(this)) { 5773 OS << "<" << *M->getMemOperand() << ">"; 5774 } else if (const BlockAddressSDNode *BA = 5775 dyn_cast<BlockAddressSDNode>(this)) { 5776 OS << "<"; 5777 WriteAsOperand(OS, BA->getBlockAddress()->getFunction(), false); 5778 OS << ", "; 5779 WriteAsOperand(OS, BA->getBlockAddress()->getBasicBlock(), false); 5780 OS << ">"; 5781 if (unsigned int TF = BA->getTargetFlags()) 5782 OS << " [TF=" << TF << ']'; 5783 } 5784} 5785 5786void SDNode::print(raw_ostream &OS, const SelectionDAG *G) const { 5787 print_types(OS, G); 5788 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 5789 if (i) OS << ", "; else OS << " "; 5790 OS << (void*)getOperand(i).getNode(); 5791 if (unsigned RN = getOperand(i).getResNo()) 5792 OS << ":" << RN; 5793 } 5794 print_details(OS, G); 5795} 5796 5797static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { 5798 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 5799 if (N->getOperand(i).getNode()->hasOneUse()) 5800 DumpNodes(N->getOperand(i).getNode(), indent+2, G); 5801 else 5802 errs() << "\n" << std::string(indent+2, ' ') 5803 << (void*)N->getOperand(i).getNode() << ": <multiple use>"; 5804 5805 5806 errs() << "\n"; 5807 errs().indent(indent); 5808 N->dump(G); 5809} 5810 5811SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) { 5812 assert(N->getNumValues() == 1 && 5813 "Can't unroll a vector with multiple results!"); 5814 5815 EVT VT = N->getValueType(0); 5816 unsigned NE = VT.getVectorNumElements(); 5817 EVT EltVT = VT.getVectorElementType(); 5818 DebugLoc dl = N->getDebugLoc(); 5819 5820 SmallVector<SDValue, 8> Scalars; 5821 SmallVector<SDValue, 4> Operands(N->getNumOperands()); 5822 5823 // If ResNE is 0, fully unroll the vector op. 5824 if (ResNE == 0) 5825 ResNE = NE; 5826 else if (NE > ResNE) 5827 NE = ResNE; 5828 5829 unsigned i; 5830 for (i= 0; i != NE; ++i) { 5831 for (unsigned j = 0; j != N->getNumOperands(); ++j) { 5832 SDValue Operand = N->getOperand(j); 5833 EVT OperandVT = Operand.getValueType(); 5834 if (OperandVT.isVector()) { 5835 // A vector operand; extract a single element. 5836 EVT OperandEltVT = OperandVT.getVectorElementType(); 5837 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl, 5838 OperandEltVT, 5839 Operand, 5840 getConstant(i, MVT::i32)); 5841 } else { 5842 // A scalar operand; just use it as is. 5843 Operands[j] = Operand; 5844 } 5845 } 5846 5847 switch (N->getOpcode()) { 5848 default: 5849 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, 5850 &Operands[0], Operands.size())); 5851 break; 5852 case ISD::SHL: 5853 case ISD::SRA: 5854 case ISD::SRL: 5855 case ISD::ROTL: 5856 case ISD::ROTR: 5857 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0], 5858 getShiftAmountOperand(Operands[1]))); 5859 break; 5860 } 5861 } 5862 5863 for (; i < ResNE; ++i) 5864 Scalars.push_back(getUNDEF(EltVT)); 5865 5866 return getNode(ISD::BUILD_VECTOR, dl, 5867 EVT::getVectorVT(*getContext(), EltVT, ResNE), 5868 &Scalars[0], Scalars.size()); 5869} 5870 5871/// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if 5872/// it cannot be inferred. 5873unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const { 5874 // If this is a direct reference to a stack slot, use information about the 5875 // stack slot's alignment. 5876 int FrameIdx = 1 << 31; 5877 int64_t FrameOffset = 0; 5878 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) { 5879 FrameIdx = FI->getIndex(); 5880 } else if (Ptr.getOpcode() == ISD::ADD && 5881 isa<ConstantSDNode>(Ptr.getOperand(1)) && 5882 isa<FrameIndexSDNode>(Ptr.getOperand(0))) { 5883 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex(); 5884 FrameOffset = Ptr.getConstantOperandVal(1); 5885 } 5886 5887 if (FrameIdx != (1 << 31)) { 5888 // FIXME: Handle FI+CST. 5889 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo(); 5890 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx), 5891 FrameOffset); 5892 if (MFI.isFixedObjectIndex(FrameIdx)) { 5893 int64_t ObjectOffset = MFI.getObjectOffset(FrameIdx) + FrameOffset; 5894 5895 // The alignment of the frame index can be determined from its offset from 5896 // the incoming frame position. If the frame object is at offset 32 and 5897 // the stack is guaranteed to be 16-byte aligned, then we know that the 5898 // object is 16-byte aligned. 5899 unsigned StackAlign = getTarget().getFrameInfo()->getStackAlignment(); 5900 unsigned Align = MinAlign(ObjectOffset, StackAlign); 5901 5902 // Finally, the frame object itself may have a known alignment. Factor 5903 // the alignment + offset into a new alignment. For example, if we know 5904 // the FI is 8 byte aligned, but the pointer is 4 off, we really have a 5905 // 4-byte alignment of the resultant pointer. Likewise align 4 + 4-byte 5906 // offset = 4-byte alignment, align 4 + 1-byte offset = align 1, etc. 5907 return std::max(Align, FIInfoAlign); 5908 } 5909 return FIInfoAlign; 5910 } 5911 5912 return 0; 5913} 5914 5915void SelectionDAG::dump() const { 5916 errs() << "SelectionDAG has " << AllNodes.size() << " nodes:"; 5917 5918 for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); 5919 I != E; ++I) { 5920 const SDNode *N = I; 5921 if (!N->hasOneUse() && N != getRoot().getNode()) 5922 DumpNodes(N, 2, this); 5923 } 5924 5925 if (getRoot().getNode()) DumpNodes(getRoot().getNode(), 2, this); 5926 5927 errs() << "\n\n"; 5928} 5929 5930void SDNode::printr(raw_ostream &OS, const SelectionDAG *G) const { 5931 print_types(OS, G); 5932 print_details(OS, G); 5933} 5934 5935typedef SmallPtrSet<const SDNode *, 128> VisitedSDNodeSet; 5936static void DumpNodesr(raw_ostream &OS, const SDNode *N, unsigned indent, 5937 const SelectionDAG *G, VisitedSDNodeSet &once) { 5938 if (!once.insert(N)) // If we've been here before, return now. 5939 return; 5940 // Dump the current SDNode, but don't end the line yet. 5941 OS << std::string(indent, ' '); 5942 N->printr(OS, G); 5943 // Having printed this SDNode, walk the children: 5944 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 5945 const SDNode *child = N->getOperand(i).getNode(); 5946 if (i) OS << ","; 5947 OS << " "; 5948 if (child->getNumOperands() == 0) { 5949 // This child has no grandchildren; print it inline right here. 5950 child->printr(OS, G); 5951 once.insert(child); 5952 } else { // Just the address. FIXME: also print the child's opcode 5953 OS << (void*)child; 5954 if (unsigned RN = N->getOperand(i).getResNo()) 5955 OS << ":" << RN; 5956 } 5957 } 5958 OS << "\n"; 5959 // Dump children that have grandchildren on their own line(s). 5960 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 5961 const SDNode *child = N->getOperand(i).getNode(); 5962 DumpNodesr(OS, child, indent+2, G, once); 5963 } 5964} 5965 5966void SDNode::dumpr() const { 5967 VisitedSDNodeSet once; 5968 DumpNodesr(errs(), this, 0, 0, once); 5969} 5970 5971void SDNode::dumpr(const SelectionDAG *G) const { 5972 VisitedSDNodeSet once; 5973 DumpNodesr(errs(), this, 0, G, once); 5974} 5975 5976 5977// getAddressSpace - Return the address space this GlobalAddress belongs to. 5978unsigned GlobalAddressSDNode::getAddressSpace() const { 5979 return getGlobal()->getType()->getAddressSpace(); 5980} 5981 5982 5983const Type *ConstantPoolSDNode::getType() const { 5984 if (isMachineConstantPoolEntry()) 5985 return Val.MachineCPVal->getType(); 5986 return Val.ConstVal->getType(); 5987} 5988 5989bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue, 5990 APInt &SplatUndef, 5991 unsigned &SplatBitSize, 5992 bool &HasAnyUndefs, 5993 unsigned MinSplatBits, 5994 bool isBigEndian) { 5995 EVT VT = getValueType(0); 5996 assert(VT.isVector() && "Expected a vector type"); 5997 unsigned sz = VT.getSizeInBits(); 5998 if (MinSplatBits > sz) 5999 return false; 6000 6001 SplatValue = APInt(sz, 0); 6002 SplatUndef = APInt(sz, 0); 6003 6004 // Get the bits. Bits with undefined values (when the corresponding element 6005 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared 6006 // in SplatValue. If any of the values are not constant, give up and return 6007 // false. 6008 unsigned int nOps = getNumOperands(); 6009 assert(nOps > 0 && "isConstantSplat has 0-size build vector"); 6010 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits(); 6011 6012 for (unsigned j = 0; j < nOps; ++j) { 6013 unsigned i = isBigEndian ? nOps-1-j : j; 6014 SDValue OpVal = getOperand(i); 6015 unsigned BitPos = j * EltBitSize; 6016 6017 if (OpVal.getOpcode() == ISD::UNDEF) 6018 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize); 6019 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal)) 6020 SplatValue |= (APInt(CN->getAPIntValue()).zextOrTrunc(EltBitSize). 6021 zextOrTrunc(sz) << BitPos); 6022 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal)) 6023 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos; 6024 else 6025 return false; 6026 } 6027 6028 // The build_vector is all constants or undefs. Find the smallest element 6029 // size that splats the vector. 6030 6031 HasAnyUndefs = (SplatUndef != 0); 6032 while (sz > 8) { 6033 6034 unsigned HalfSize = sz / 2; 6035 APInt HighValue = APInt(SplatValue).lshr(HalfSize).trunc(HalfSize); 6036 APInt LowValue = APInt(SplatValue).trunc(HalfSize); 6037 APInt HighUndef = APInt(SplatUndef).lshr(HalfSize).trunc(HalfSize); 6038 APInt LowUndef = APInt(SplatUndef).trunc(HalfSize); 6039 6040 // If the two halves do not match (ignoring undef bits), stop here. 6041 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) || 6042 MinSplatBits > HalfSize) 6043 break; 6044 6045 SplatValue = HighValue | LowValue; 6046 SplatUndef = HighUndef & LowUndef; 6047 6048 sz = HalfSize; 6049 } 6050 6051 SplatBitSize = sz; 6052 return true; 6053} 6054 6055bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) { 6056 // Find the first non-undef value in the shuffle mask. 6057 unsigned i, e; 6058 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i) 6059 /* search */; 6060 6061 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!"); 6062 6063 // Make sure all remaining elements are either undef or the same as the first 6064 // non-undef value. 6065 for (int Idx = Mask[i]; i != e; ++i) 6066 if (Mask[i] >= 0 && Mask[i] != Idx) 6067 return false; 6068 return true; 6069} 6070 6071