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