SelectionDAG.cpp revision 8cd08bf4ac67b9d711fd1f72e6f5e00425d8c6ad
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 2938 if (VT != Elt.getValueType()) 2939 // If the vector element type is not legal, the BUILD_VECTOR operands 2940 // are promoted and implicitly truncated, and the result implicitly 2941 // extended. Make that explicit here. 2942 Elt = getAnyExtOrTrunc(Elt, DL, VT); 2943 2944 return Elt; 2945 } 2946 2947 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector 2948 // operations are lowered to scalars. 2949 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) { 2950 // If the indices are the same, return the inserted element else 2951 // if the indices are known different, extract the element from 2952 // the original vector. 2953 SDValue N1Op2 = N1.getOperand(2); 2954 ConstantSDNode *N1Op2C = dyn_cast<ConstantSDNode>(N1Op2.getNode()); 2955 2956 if (N1Op2C && N2C) { 2957 if (N1Op2C->getZExtValue() == N2C->getZExtValue()) { 2958 if (VT == N1.getOperand(1).getValueType()) 2959 return N1.getOperand(1); 2960 else 2961 return getSExtOrTrunc(N1.getOperand(1), DL, VT); 2962 } 2963 2964 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2); 2965 } 2966 } 2967 break; 2968 case ISD::EXTRACT_ELEMENT: 2969 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!"); 2970 assert(!N1.getValueType().isVector() && !VT.isVector() && 2971 (N1.getValueType().isInteger() == VT.isInteger()) && 2972 N1.getValueType() != VT && 2973 "Wrong types for EXTRACT_ELEMENT!"); 2974 2975 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding 2976 // 64-bit integers into 32-bit parts. Instead of building the extract of 2977 // the BUILD_PAIR, only to have legalize rip it apart, just do it now. 2978 if (N1.getOpcode() == ISD::BUILD_PAIR) 2979 return N1.getOperand(N2C->getZExtValue()); 2980 2981 // EXTRACT_ELEMENT of a constant int is also very common. 2982 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) { 2983 unsigned ElementSize = VT.getSizeInBits(); 2984 unsigned Shift = ElementSize * N2C->getZExtValue(); 2985 APInt ShiftedVal = C->getAPIntValue().lshr(Shift); 2986 return getConstant(ShiftedVal.trunc(ElementSize), VT); 2987 } 2988 break; 2989 case ISD::EXTRACT_SUBVECTOR: { 2990 SDValue Index = N2; 2991 if (VT.isSimple() && N1.getValueType().isSimple()) { 2992 assert(VT.isVector() && N1.getValueType().isVector() && 2993 "Extract subvector VTs must be a vectors!"); 2994 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() && 2995 "Extract subvector VTs must have the same element type!"); 2996 assert(VT.getSimpleVT() <= N1.getValueType().getSimpleVT() && 2997 "Extract subvector must be from larger vector to smaller vector!"); 2998 2999 if (isa<ConstantSDNode>(Index.getNode())) { 3000 assert((VT.getVectorNumElements() + 3001 cast<ConstantSDNode>(Index.getNode())->getZExtValue() 3002 <= N1.getValueType().getVectorNumElements()) 3003 && "Extract subvector overflow!"); 3004 } 3005 3006 // Trivial extraction. 3007 if (VT.getSimpleVT() == N1.getValueType().getSimpleVT()) 3008 return N1; 3009 } 3010 break; 3011 } 3012 } 3013 3014 if (N1C) { 3015 if (N2C) { 3016 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C); 3017 if (SV.getNode()) return SV; 3018 } else { // Cannonicalize constant to RHS if commutative 3019 if (isCommutativeBinOp(Opcode)) { 3020 std::swap(N1C, N2C); 3021 std::swap(N1, N2); 3022 } 3023 } 3024 } 3025 3026 // Constant fold FP operations. 3027 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode()); 3028 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode()); 3029 if (N1CFP) { 3030 if (!N2CFP && isCommutativeBinOp(Opcode)) { 3031 // Cannonicalize constant to RHS if commutative 3032 std::swap(N1CFP, N2CFP); 3033 std::swap(N1, N2); 3034 } else if (N2CFP && VT != MVT::ppcf128) { 3035 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF(); 3036 APFloat::opStatus s; 3037 switch (Opcode) { 3038 case ISD::FADD: 3039 s = V1.add(V2, APFloat::rmNearestTiesToEven); 3040 if (s != APFloat::opInvalidOp) 3041 return getConstantFP(V1, VT); 3042 break; 3043 case ISD::FSUB: 3044 s = V1.subtract(V2, APFloat::rmNearestTiesToEven); 3045 if (s!=APFloat::opInvalidOp) 3046 return getConstantFP(V1, VT); 3047 break; 3048 case ISD::FMUL: 3049 s = V1.multiply(V2, APFloat::rmNearestTiesToEven); 3050 if (s!=APFloat::opInvalidOp) 3051 return getConstantFP(V1, VT); 3052 break; 3053 case ISD::FDIV: 3054 s = V1.divide(V2, APFloat::rmNearestTiesToEven); 3055 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero) 3056 return getConstantFP(V1, VT); 3057 break; 3058 case ISD::FREM : 3059 s = V1.mod(V2, APFloat::rmNearestTiesToEven); 3060 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero) 3061 return getConstantFP(V1, VT); 3062 break; 3063 case ISD::FCOPYSIGN: 3064 V1.copySign(V2); 3065 return getConstantFP(V1, VT); 3066 default: break; 3067 } 3068 } 3069 3070 if (Opcode == ISD::FP_ROUND) { 3071 APFloat V = N1CFP->getValueAPF(); // make copy 3072 bool ignored; 3073 // This can return overflow, underflow, or inexact; we don't care. 3074 // FIXME need to be more flexible about rounding mode. 3075 (void)V.convert(*EVTToAPFloatSemantics(VT), 3076 APFloat::rmNearestTiesToEven, &ignored); 3077 return getConstantFP(V, VT); 3078 } 3079 } 3080 3081 // Canonicalize an UNDEF to the RHS, even over a constant. 3082 if (N1.getOpcode() == ISD::UNDEF) { 3083 if (isCommutativeBinOp(Opcode)) { 3084 std::swap(N1, N2); 3085 } else { 3086 switch (Opcode) { 3087 case ISD::FP_ROUND_INREG: 3088 case ISD::SIGN_EXTEND_INREG: 3089 case ISD::SUB: 3090 case ISD::FSUB: 3091 case ISD::FDIV: 3092 case ISD::FREM: 3093 case ISD::SRA: 3094 return N1; // fold op(undef, arg2) -> undef 3095 case ISD::UDIV: 3096 case ISD::SDIV: 3097 case ISD::UREM: 3098 case ISD::SREM: 3099 case ISD::SRL: 3100 case ISD::SHL: 3101 if (!VT.isVector()) 3102 return getConstant(0, VT); // fold op(undef, arg2) -> 0 3103 // For vectors, we can't easily build an all zero vector, just return 3104 // the LHS. 3105 return N2; 3106 } 3107 } 3108 } 3109 3110 // Fold a bunch of operators when the RHS is undef. 3111 if (N2.getOpcode() == ISD::UNDEF) { 3112 switch (Opcode) { 3113 case ISD::XOR: 3114 if (N1.getOpcode() == ISD::UNDEF) 3115 // Handle undef ^ undef -> 0 special case. This is a common 3116 // idiom (misuse). 3117 return getConstant(0, VT); 3118 // fallthrough 3119 case ISD::ADD: 3120 case ISD::ADDC: 3121 case ISD::ADDE: 3122 case ISD::SUB: 3123 case ISD::UDIV: 3124 case ISD::SDIV: 3125 case ISD::UREM: 3126 case ISD::SREM: 3127 return N2; // fold op(arg1, undef) -> undef 3128 case ISD::FADD: 3129 case ISD::FSUB: 3130 case ISD::FMUL: 3131 case ISD::FDIV: 3132 case ISD::FREM: 3133 if (getTarget().Options.UnsafeFPMath) 3134 return N2; 3135 break; 3136 case ISD::MUL: 3137 case ISD::AND: 3138 case ISD::SRL: 3139 case ISD::SHL: 3140 if (!VT.isVector()) 3141 return getConstant(0, VT); // fold op(arg1, undef) -> 0 3142 // For vectors, we can't easily build an all zero vector, just return 3143 // the LHS. 3144 return N1; 3145 case ISD::OR: 3146 if (!VT.isVector()) 3147 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT); 3148 // For vectors, we can't easily build an all one vector, just return 3149 // the LHS. 3150 return N1; 3151 case ISD::SRA: 3152 return N1; 3153 } 3154 } 3155 3156 // Memoize this node if possible. 3157 SDNode *N; 3158 SDVTList VTs = getVTList(VT); 3159 if (VT != MVT::Glue) { 3160 SDValue Ops[] = { N1, N2 }; 3161 FoldingSetNodeID ID; 3162 AddNodeIDNode(ID, Opcode, VTs, Ops, 2); 3163 void *IP = 0; 3164 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 3165 return SDValue(E, 0); 3166 3167 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2); 3168 CSEMap.InsertNode(N, IP); 3169 } else { 3170 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTs, N1, N2); 3171 } 3172 3173 AllNodes.push_back(N); 3174#ifndef NDEBUG 3175 VerifySDNode(N); 3176#endif 3177 return SDValue(N, 0); 3178} 3179 3180SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 3181 SDValue N1, SDValue N2, SDValue N3) { 3182 // Perform various simplifications. 3183 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 3184 switch (Opcode) { 3185 case ISD::CONCAT_VECTORS: 3186 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to 3187 // one big BUILD_VECTOR. 3188 if (N1.getOpcode() == ISD::BUILD_VECTOR && 3189 N2.getOpcode() == ISD::BUILD_VECTOR && 3190 N3.getOpcode() == ISD::BUILD_VECTOR) { 3191 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(), 3192 N1.getNode()->op_end()); 3193 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end()); 3194 Elts.append(N3.getNode()->op_begin(), N3.getNode()->op_end()); 3195 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size()); 3196 } 3197 break; 3198 case ISD::SETCC: { 3199 // Use FoldSetCC to simplify SETCC's. 3200 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL); 3201 if (Simp.getNode()) return Simp; 3202 break; 3203 } 3204 case ISD::SELECT: 3205 if (N1C) { 3206 if (N1C->getZExtValue()) 3207 return N2; // select true, X, Y -> X 3208 return N3; // select false, X, Y -> Y 3209 } 3210 3211 if (N2 == N3) return N2; // select C, X, X -> X 3212 break; 3213 case ISD::VECTOR_SHUFFLE: 3214 llvm_unreachable("should use getVectorShuffle constructor!"); 3215 case ISD::INSERT_SUBVECTOR: { 3216 SDValue Index = N3; 3217 if (VT.isSimple() && N1.getValueType().isSimple() 3218 && N2.getValueType().isSimple()) { 3219 assert(VT.isVector() && N1.getValueType().isVector() && 3220 N2.getValueType().isVector() && 3221 "Insert subvector VTs must be a vectors"); 3222 assert(VT == N1.getValueType() && 3223 "Dest and insert subvector source types must match!"); 3224 assert(N2.getValueType().getSimpleVT() <= N1.getValueType().getSimpleVT() && 3225 "Insert subvector must be from smaller vector to larger vector!"); 3226 if (isa<ConstantSDNode>(Index.getNode())) { 3227 assert((N2.getValueType().getVectorNumElements() + 3228 cast<ConstantSDNode>(Index.getNode())->getZExtValue() 3229 <= VT.getVectorNumElements()) 3230 && "Insert subvector overflow!"); 3231 } 3232 3233 // Trivial insertion. 3234 if (VT.getSimpleVT() == N2.getValueType().getSimpleVT()) 3235 return N2; 3236 } 3237 break; 3238 } 3239 case ISD::BITCAST: 3240 // Fold bit_convert nodes from a type to themselves. 3241 if (N1.getValueType() == VT) 3242 return N1; 3243 break; 3244 } 3245 3246 // Memoize node if it doesn't produce a flag. 3247 SDNode *N; 3248 SDVTList VTs = getVTList(VT); 3249 if (VT != MVT::Glue) { 3250 SDValue Ops[] = { N1, N2, N3 }; 3251 FoldingSetNodeID ID; 3252 AddNodeIDNode(ID, Opcode, VTs, Ops, 3); 3253 void *IP = 0; 3254 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 3255 return SDValue(E, 0); 3256 3257 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3); 3258 CSEMap.InsertNode(N, IP); 3259 } else { 3260 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTs, N1, N2, N3); 3261 } 3262 3263 AllNodes.push_back(N); 3264#ifndef NDEBUG 3265 VerifySDNode(N); 3266#endif 3267 return SDValue(N, 0); 3268} 3269 3270SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 3271 SDValue N1, SDValue N2, SDValue N3, 3272 SDValue N4) { 3273 SDValue Ops[] = { N1, N2, N3, N4 }; 3274 return getNode(Opcode, DL, VT, Ops, 4); 3275} 3276 3277SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 3278 SDValue N1, SDValue N2, SDValue N3, 3279 SDValue N4, SDValue N5) { 3280 SDValue Ops[] = { N1, N2, N3, N4, N5 }; 3281 return getNode(Opcode, DL, VT, Ops, 5); 3282} 3283 3284/// getStackArgumentTokenFactor - Compute a TokenFactor to force all 3285/// the incoming stack arguments to be loaded from the stack. 3286SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) { 3287 SmallVector<SDValue, 8> ArgChains; 3288 3289 // Include the original chain at the beginning of the list. When this is 3290 // used by target LowerCall hooks, this helps legalize find the 3291 // CALLSEQ_BEGIN node. 3292 ArgChains.push_back(Chain); 3293 3294 // Add a chain value for each stack argument. 3295 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(), 3296 UE = getEntryNode().getNode()->use_end(); U != UE; ++U) 3297 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U)) 3298 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr())) 3299 if (FI->getIndex() < 0) 3300 ArgChains.push_back(SDValue(L, 1)); 3301 3302 // Build a tokenfactor for all the chains. 3303 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other, 3304 &ArgChains[0], ArgChains.size()); 3305} 3306 3307/// SplatByte - Distribute ByteVal over NumBits bits. 3308static APInt SplatByte(unsigned NumBits, uint8_t ByteVal) { 3309 APInt Val = APInt(NumBits, ByteVal); 3310 unsigned Shift = 8; 3311 for (unsigned i = NumBits; i > 8; i >>= 1) { 3312 Val = (Val << Shift) | Val; 3313 Shift <<= 1; 3314 } 3315 return Val; 3316} 3317 3318/// getMemsetValue - Vectorized representation of the memset value 3319/// operand. 3320static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG, 3321 DebugLoc dl) { 3322 assert(Value.getOpcode() != ISD::UNDEF); 3323 3324 unsigned NumBits = VT.getScalarType().getSizeInBits(); 3325 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) { 3326 APInt Val = SplatByte(NumBits, C->getZExtValue() & 255); 3327 if (VT.isInteger()) 3328 return DAG.getConstant(Val, VT); 3329 return DAG.getConstantFP(APFloat(Val), VT); 3330 } 3331 3332 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value); 3333 if (NumBits > 8) { 3334 // Use a multiplication with 0x010101... to extend the input to the 3335 // required length. 3336 APInt Magic = SplatByte(NumBits, 0x01); 3337 Value = DAG.getNode(ISD::MUL, dl, VT, Value, DAG.getConstant(Magic, VT)); 3338 } 3339 3340 return Value; 3341} 3342 3343/// getMemsetStringVal - Similar to getMemsetValue. Except this is only 3344/// used when a memcpy is turned into a memset when the source is a constant 3345/// string ptr. 3346static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG, 3347 const TargetLowering &TLI, StringRef Str) { 3348 // Handle vector with all elements zero. 3349 if (Str.empty()) { 3350 if (VT.isInteger()) 3351 return DAG.getConstant(0, VT); 3352 else if (VT == MVT::f32 || VT == MVT::f64) 3353 return DAG.getConstantFP(0.0, VT); 3354 else if (VT.isVector()) { 3355 unsigned NumElts = VT.getVectorNumElements(); 3356 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64; 3357 return DAG.getNode(ISD::BITCAST, dl, VT, 3358 DAG.getConstant(0, EVT::getVectorVT(*DAG.getContext(), 3359 EltVT, NumElts))); 3360 } else 3361 llvm_unreachable("Expected type!"); 3362 } 3363 3364 assert(!VT.isVector() && "Can't handle vector type here!"); 3365 unsigned NumVTBytes = VT.getSizeInBits() / 8; 3366 unsigned NumBytes = std::min(NumVTBytes, unsigned(Str.size())); 3367 3368 uint64_t Val = 0; 3369 if (TLI.isLittleEndian()) { 3370 for (unsigned i = 0; i != NumBytes; ++i) 3371 Val |= (uint64_t)(unsigned char)Str[i] << i*8; 3372 } else { 3373 for (unsigned i = 0; i != NumBytes; ++i) 3374 Val |= (uint64_t)(unsigned char)Str[i] << (NumVTBytes-i-1)*8; 3375 } 3376 3377 return DAG.getConstant(Val, VT); 3378} 3379 3380/// getMemBasePlusOffset - Returns base and offset node for the 3381/// 3382static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, 3383 SelectionDAG &DAG) { 3384 EVT VT = Base.getValueType(); 3385 return DAG.getNode(ISD::ADD, Base.getDebugLoc(), 3386 VT, Base, DAG.getConstant(Offset, VT)); 3387} 3388 3389/// isMemSrcFromString - Returns true if memcpy source is a string constant. 3390/// 3391static bool isMemSrcFromString(SDValue Src, StringRef &Str) { 3392 unsigned SrcDelta = 0; 3393 GlobalAddressSDNode *G = NULL; 3394 if (Src.getOpcode() == ISD::GlobalAddress) 3395 G = cast<GlobalAddressSDNode>(Src); 3396 else if (Src.getOpcode() == ISD::ADD && 3397 Src.getOperand(0).getOpcode() == ISD::GlobalAddress && 3398 Src.getOperand(1).getOpcode() == ISD::Constant) { 3399 G = cast<GlobalAddressSDNode>(Src.getOperand(0)); 3400 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue(); 3401 } 3402 if (!G) 3403 return false; 3404 3405 return getConstantStringInfo(G->getGlobal(), Str, SrcDelta, false); 3406} 3407 3408/// FindOptimalMemOpLowering - Determines the optimial series memory ops 3409/// to replace the memset / memcpy. Return true if the number of memory ops 3410/// is below the threshold. It returns the types of the sequence of 3411/// memory ops to perform memset / memcpy by reference. 3412static bool FindOptimalMemOpLowering(std::vector<EVT> &MemOps, 3413 unsigned Limit, uint64_t Size, 3414 unsigned DstAlign, unsigned SrcAlign, 3415 bool IsZeroVal, 3416 bool MemcpyStrSrc, 3417 SelectionDAG &DAG, 3418 const TargetLowering &TLI) { 3419 assert((SrcAlign == 0 || SrcAlign >= DstAlign) && 3420 "Expecting memcpy / memset source to meet alignment requirement!"); 3421 // If 'SrcAlign' is zero, that means the memory operation does not need to 3422 // load the value, i.e. memset or memcpy from constant string. Otherwise, 3423 // it's the inferred alignment of the source. 'DstAlign', on the other hand, 3424 // is the specified alignment of the memory operation. If it is zero, that 3425 // means it's possible to change the alignment of the destination. 3426 // 'MemcpyStrSrc' indicates whether the memcpy source is constant so it does 3427 // not need to be loaded. 3428 EVT VT = TLI.getOptimalMemOpType(Size, DstAlign, SrcAlign, 3429 IsZeroVal, MemcpyStrSrc, 3430 DAG.getMachineFunction()); 3431 3432 if (VT == MVT::Other) { 3433 if (DstAlign >= TLI.getTargetData()->getPointerPrefAlignment() || 3434 TLI.allowsUnalignedMemoryAccesses(VT)) { 3435 VT = TLI.getPointerTy(); 3436 } else { 3437 switch (DstAlign & 7) { 3438 case 0: VT = MVT::i64; break; 3439 case 4: VT = MVT::i32; break; 3440 case 2: VT = MVT::i16; break; 3441 default: VT = MVT::i8; break; 3442 } 3443 } 3444 3445 MVT LVT = MVT::i64; 3446 while (!TLI.isTypeLegal(LVT)) 3447 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1); 3448 assert(LVT.isInteger()); 3449 3450 if (VT.bitsGT(LVT)) 3451 VT = LVT; 3452 } 3453 3454 unsigned NumMemOps = 0; 3455 while (Size != 0) { 3456 unsigned VTSize = VT.getSizeInBits() / 8; 3457 while (VTSize > Size) { 3458 // For now, only use non-vector load / store's for the left-over pieces. 3459 if (VT.isVector() || VT.isFloatingPoint()) { 3460 VT = MVT::i64; 3461 while (!TLI.isTypeLegal(VT)) 3462 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1); 3463 VTSize = VT.getSizeInBits() / 8; 3464 } else { 3465 // This can result in a type that is not legal on the target, e.g. 3466 // 1 or 2 bytes on PPC. 3467 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1); 3468 VTSize >>= 1; 3469 } 3470 } 3471 3472 if (++NumMemOps > Limit) 3473 return false; 3474 MemOps.push_back(VT); 3475 Size -= VTSize; 3476 } 3477 3478 return true; 3479} 3480 3481static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl, 3482 SDValue Chain, SDValue Dst, 3483 SDValue Src, uint64_t Size, 3484 unsigned Align, bool isVol, 3485 bool AlwaysInline, 3486 MachinePointerInfo DstPtrInfo, 3487 MachinePointerInfo SrcPtrInfo) { 3488 // Turn a memcpy of undef to nop. 3489 if (Src.getOpcode() == ISD::UNDEF) 3490 return Chain; 3491 3492 // Expand memcpy to a series of load and store ops if the size operand falls 3493 // below a certain threshold. 3494 // TODO: In the AlwaysInline case, if the size is big then generate a loop 3495 // rather than maybe a humongous number of loads and stores. 3496 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 3497 std::vector<EVT> MemOps; 3498 bool DstAlignCanChange = false; 3499 MachineFunction &MF = DAG.getMachineFunction(); 3500 MachineFrameInfo *MFI = MF.getFrameInfo(); 3501 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize); 3502 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst); 3503 if (FI && !MFI->isFixedObjectIndex(FI->getIndex())) 3504 DstAlignCanChange = true; 3505 unsigned SrcAlign = DAG.InferPtrAlignment(Src); 3506 if (Align > SrcAlign) 3507 SrcAlign = Align; 3508 StringRef Str; 3509 bool CopyFromStr = isMemSrcFromString(Src, Str); 3510 bool isZeroStr = CopyFromStr && Str.empty(); 3511 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemcpy(OptSize); 3512 3513 if (!FindOptimalMemOpLowering(MemOps, Limit, Size, 3514 (DstAlignCanChange ? 0 : Align), 3515 (isZeroStr ? 0 : SrcAlign), 3516 true, CopyFromStr, DAG, TLI)) 3517 return SDValue(); 3518 3519 if (DstAlignCanChange) { 3520 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext()); 3521 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty); 3522 if (NewAlign > Align) { 3523 // Give the stack frame object a larger alignment if needed. 3524 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign) 3525 MFI->setObjectAlignment(FI->getIndex(), NewAlign); 3526 Align = NewAlign; 3527 } 3528 } 3529 3530 SmallVector<SDValue, 8> OutChains; 3531 unsigned NumMemOps = MemOps.size(); 3532 uint64_t SrcOff = 0, DstOff = 0; 3533 for (unsigned i = 0; i != NumMemOps; ++i) { 3534 EVT VT = MemOps[i]; 3535 unsigned VTSize = VT.getSizeInBits() / 8; 3536 SDValue Value, Store; 3537 3538 if (CopyFromStr && 3539 (isZeroStr || (VT.isInteger() && !VT.isVector()))) { 3540 // It's unlikely a store of a vector immediate can be done in a single 3541 // instruction. It would require a load from a constantpool first. 3542 // We only handle zero vectors here. 3543 // FIXME: Handle other cases where store of vector immediate is done in 3544 // a single instruction. 3545 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str.substr(SrcOff)); 3546 Store = DAG.getStore(Chain, dl, Value, 3547 getMemBasePlusOffset(Dst, DstOff, DAG), 3548 DstPtrInfo.getWithOffset(DstOff), isVol, 3549 false, Align); 3550 } else { 3551 // The type might not be legal for the target. This should only happen 3552 // if the type is smaller than a legal type, as on PPC, so the right 3553 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify 3554 // to Load/Store if NVT==VT. 3555 // FIXME does the case above also need this? 3556 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT); 3557 assert(NVT.bitsGE(VT)); 3558 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain, 3559 getMemBasePlusOffset(Src, SrcOff, DAG), 3560 SrcPtrInfo.getWithOffset(SrcOff), VT, isVol, false, 3561 MinAlign(SrcAlign, SrcOff)); 3562 Store = DAG.getTruncStore(Chain, dl, Value, 3563 getMemBasePlusOffset(Dst, DstOff, DAG), 3564 DstPtrInfo.getWithOffset(DstOff), VT, isVol, 3565 false, Align); 3566 } 3567 OutChains.push_back(Store); 3568 SrcOff += VTSize; 3569 DstOff += VTSize; 3570 } 3571 3572 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 3573 &OutChains[0], OutChains.size()); 3574} 3575 3576static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl, 3577 SDValue Chain, SDValue Dst, 3578 SDValue Src, uint64_t Size, 3579 unsigned Align, bool isVol, 3580 bool AlwaysInline, 3581 MachinePointerInfo DstPtrInfo, 3582 MachinePointerInfo SrcPtrInfo) { 3583 // Turn a memmove of undef to nop. 3584 if (Src.getOpcode() == ISD::UNDEF) 3585 return Chain; 3586 3587 // Expand memmove to a series of load and store ops if the size operand falls 3588 // below a certain threshold. 3589 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 3590 std::vector<EVT> MemOps; 3591 bool DstAlignCanChange = false; 3592 MachineFunction &MF = DAG.getMachineFunction(); 3593 MachineFrameInfo *MFI = MF.getFrameInfo(); 3594 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize); 3595 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst); 3596 if (FI && !MFI->isFixedObjectIndex(FI->getIndex())) 3597 DstAlignCanChange = true; 3598 unsigned SrcAlign = DAG.InferPtrAlignment(Src); 3599 if (Align > SrcAlign) 3600 SrcAlign = Align; 3601 unsigned Limit = AlwaysInline ? ~0U : TLI.getMaxStoresPerMemmove(OptSize); 3602 3603 if (!FindOptimalMemOpLowering(MemOps, Limit, Size, 3604 (DstAlignCanChange ? 0 : Align), 3605 SrcAlign, true, false, DAG, TLI)) 3606 return SDValue(); 3607 3608 if (DstAlignCanChange) { 3609 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext()); 3610 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty); 3611 if (NewAlign > Align) { 3612 // Give the stack frame object a larger alignment if needed. 3613 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign) 3614 MFI->setObjectAlignment(FI->getIndex(), NewAlign); 3615 Align = NewAlign; 3616 } 3617 } 3618 3619 uint64_t SrcOff = 0, DstOff = 0; 3620 SmallVector<SDValue, 8> LoadValues; 3621 SmallVector<SDValue, 8> LoadChains; 3622 SmallVector<SDValue, 8> OutChains; 3623 unsigned NumMemOps = MemOps.size(); 3624 for (unsigned i = 0; i < NumMemOps; i++) { 3625 EVT VT = MemOps[i]; 3626 unsigned VTSize = VT.getSizeInBits() / 8; 3627 SDValue Value, Store; 3628 3629 Value = DAG.getLoad(VT, dl, Chain, 3630 getMemBasePlusOffset(Src, SrcOff, DAG), 3631 SrcPtrInfo.getWithOffset(SrcOff), isVol, 3632 false, false, SrcAlign); 3633 LoadValues.push_back(Value); 3634 LoadChains.push_back(Value.getValue(1)); 3635 SrcOff += VTSize; 3636 } 3637 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 3638 &LoadChains[0], LoadChains.size()); 3639 OutChains.clear(); 3640 for (unsigned i = 0; i < NumMemOps; i++) { 3641 EVT VT = MemOps[i]; 3642 unsigned VTSize = VT.getSizeInBits() / 8; 3643 SDValue Value, Store; 3644 3645 Store = DAG.getStore(Chain, dl, LoadValues[i], 3646 getMemBasePlusOffset(Dst, DstOff, DAG), 3647 DstPtrInfo.getWithOffset(DstOff), isVol, false, Align); 3648 OutChains.push_back(Store); 3649 DstOff += VTSize; 3650 } 3651 3652 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 3653 &OutChains[0], OutChains.size()); 3654} 3655 3656static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl, 3657 SDValue Chain, SDValue Dst, 3658 SDValue Src, uint64_t Size, 3659 unsigned Align, bool isVol, 3660 MachinePointerInfo DstPtrInfo) { 3661 // Turn a memset of undef to nop. 3662 if (Src.getOpcode() == ISD::UNDEF) 3663 return Chain; 3664 3665 // Expand memset to a series of load/store ops if the size operand 3666 // falls below a certain threshold. 3667 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 3668 std::vector<EVT> MemOps; 3669 bool DstAlignCanChange = false; 3670 MachineFunction &MF = DAG.getMachineFunction(); 3671 MachineFrameInfo *MFI = MF.getFrameInfo(); 3672 bool OptSize = MF.getFunction()->hasFnAttr(Attribute::OptimizeForSize); 3673 FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Dst); 3674 if (FI && !MFI->isFixedObjectIndex(FI->getIndex())) 3675 DstAlignCanChange = true; 3676 bool IsZeroVal = 3677 isa<ConstantSDNode>(Src) && cast<ConstantSDNode>(Src)->isNullValue(); 3678 if (!FindOptimalMemOpLowering(MemOps, TLI.getMaxStoresPerMemset(OptSize), 3679 Size, (DstAlignCanChange ? 0 : Align), 0, 3680 IsZeroVal, false, DAG, TLI)) 3681 return SDValue(); 3682 3683 if (DstAlignCanChange) { 3684 Type *Ty = MemOps[0].getTypeForEVT(*DAG.getContext()); 3685 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty); 3686 if (NewAlign > Align) { 3687 // Give the stack frame object a larger alignment if needed. 3688 if (MFI->getObjectAlignment(FI->getIndex()) < NewAlign) 3689 MFI->setObjectAlignment(FI->getIndex(), NewAlign); 3690 Align = NewAlign; 3691 } 3692 } 3693 3694 SmallVector<SDValue, 8> OutChains; 3695 uint64_t DstOff = 0; 3696 unsigned NumMemOps = MemOps.size(); 3697 3698 // Find the largest store and generate the bit pattern for it. 3699 EVT LargestVT = MemOps[0]; 3700 for (unsigned i = 1; i < NumMemOps; i++) 3701 if (MemOps[i].bitsGT(LargestVT)) 3702 LargestVT = MemOps[i]; 3703 SDValue MemSetValue = getMemsetValue(Src, LargestVT, DAG, dl); 3704 3705 for (unsigned i = 0; i < NumMemOps; i++) { 3706 EVT VT = MemOps[i]; 3707 3708 // If this store is smaller than the largest store see whether we can get 3709 // the smaller value for free with a truncate. 3710 SDValue Value = MemSetValue; 3711 if (VT.bitsLT(LargestVT)) { 3712 if (!LargestVT.isVector() && !VT.isVector() && 3713 TLI.isTruncateFree(LargestVT, VT)) 3714 Value = DAG.getNode(ISD::TRUNCATE, dl, VT, MemSetValue); 3715 else 3716 Value = getMemsetValue(Src, VT, DAG, dl); 3717 } 3718 assert(Value.getValueType() == VT && "Value with wrong type."); 3719 SDValue Store = DAG.getStore(Chain, dl, Value, 3720 getMemBasePlusOffset(Dst, DstOff, DAG), 3721 DstPtrInfo.getWithOffset(DstOff), 3722 isVol, false, Align); 3723 OutChains.push_back(Store); 3724 DstOff += VT.getSizeInBits() / 8; 3725 } 3726 3727 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 3728 &OutChains[0], OutChains.size()); 3729} 3730 3731SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, 3732 SDValue Src, SDValue Size, 3733 unsigned Align, bool isVol, bool AlwaysInline, 3734 MachinePointerInfo DstPtrInfo, 3735 MachinePointerInfo SrcPtrInfo) { 3736 3737 // Check to see if we should lower the memcpy to loads and stores first. 3738 // For cases within the target-specified limits, this is the best choice. 3739 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size); 3740 if (ConstantSize) { 3741 // Memcpy with size zero? Just return the original chain. 3742 if (ConstantSize->isNullValue()) 3743 return Chain; 3744 3745 SDValue Result = getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src, 3746 ConstantSize->getZExtValue(),Align, 3747 isVol, false, DstPtrInfo, SrcPtrInfo); 3748 if (Result.getNode()) 3749 return Result; 3750 } 3751 3752 // Then check to see if we should lower the memcpy with target-specific 3753 // code. If the target chooses to do this, this is the next best. 3754 SDValue Result = 3755 TSI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align, 3756 isVol, AlwaysInline, 3757 DstPtrInfo, SrcPtrInfo); 3758 if (Result.getNode()) 3759 return Result; 3760 3761 // If we really need inline code and the target declined to provide it, 3762 // use a (potentially long) sequence of loads and stores. 3763 if (AlwaysInline) { 3764 assert(ConstantSize && "AlwaysInline requires a constant size!"); 3765 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src, 3766 ConstantSize->getZExtValue(), Align, isVol, 3767 true, DstPtrInfo, SrcPtrInfo); 3768 } 3769 3770 // FIXME: If the memcpy is volatile (isVol), lowering it to a plain libc 3771 // memcpy is not guaranteed to be safe. libc memcpys aren't required to 3772 // respect volatile, so they may do things like read or write memory 3773 // beyond the given memory regions. But fixing this isn't easy, and most 3774 // people don't care. 3775 3776 // Emit a library call. 3777 TargetLowering::ArgListTy Args; 3778 TargetLowering::ArgListEntry Entry; 3779 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext()); 3780 Entry.Node = Dst; Args.push_back(Entry); 3781 Entry.Node = Src; Args.push_back(Entry); 3782 Entry.Node = Size; Args.push_back(Entry); 3783 // FIXME: pass in DebugLoc 3784 TargetLowering:: 3785 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()), 3786 false, false, false, false, 0, 3787 TLI.getLibcallCallingConv(RTLIB::MEMCPY), 3788 /*isTailCall=*/false, 3789 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false, 3790 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY), 3791 TLI.getPointerTy()), 3792 Args, *this, dl); 3793 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI); 3794 3795 return CallResult.second; 3796} 3797 3798SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, 3799 SDValue Src, SDValue Size, 3800 unsigned Align, bool isVol, 3801 MachinePointerInfo DstPtrInfo, 3802 MachinePointerInfo SrcPtrInfo) { 3803 3804 // Check to see if we should lower the memmove to loads and stores first. 3805 // For cases within the target-specified limits, this is the best choice. 3806 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size); 3807 if (ConstantSize) { 3808 // Memmove with size zero? Just return the original chain. 3809 if (ConstantSize->isNullValue()) 3810 return Chain; 3811 3812 SDValue Result = 3813 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src, 3814 ConstantSize->getZExtValue(), Align, isVol, 3815 false, DstPtrInfo, SrcPtrInfo); 3816 if (Result.getNode()) 3817 return Result; 3818 } 3819 3820 // Then check to see if we should lower the memmove with target-specific 3821 // code. If the target chooses to do this, this is the next best. 3822 SDValue Result = 3823 TSI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, isVol, 3824 DstPtrInfo, SrcPtrInfo); 3825 if (Result.getNode()) 3826 return Result; 3827 3828 // FIXME: If the memmove is volatile, lowering it to plain libc memmove may 3829 // not be safe. See memcpy above for more details. 3830 3831 // Emit a library call. 3832 TargetLowering::ArgListTy Args; 3833 TargetLowering::ArgListEntry Entry; 3834 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext()); 3835 Entry.Node = Dst; Args.push_back(Entry); 3836 Entry.Node = Src; Args.push_back(Entry); 3837 Entry.Node = Size; Args.push_back(Entry); 3838 // FIXME: pass in DebugLoc 3839 TargetLowering:: 3840 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()), 3841 false, false, false, false, 0, 3842 TLI.getLibcallCallingConv(RTLIB::MEMMOVE), 3843 /*isTailCall=*/false, 3844 /*doesNotReturn=*/false, /*isReturnValueUsed=*/false, 3845 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE), 3846 TLI.getPointerTy()), 3847 Args, *this, dl); 3848 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI); 3849 3850 return CallResult.second; 3851} 3852 3853SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, 3854 SDValue Src, SDValue Size, 3855 unsigned Align, bool isVol, 3856 MachinePointerInfo DstPtrInfo) { 3857 3858 // Check to see if we should lower the memset to stores first. 3859 // For cases within the target-specified limits, this is the best choice. 3860 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size); 3861 if (ConstantSize) { 3862 // Memset with size zero? Just return the original chain. 3863 if (ConstantSize->isNullValue()) 3864 return Chain; 3865 3866 SDValue Result = 3867 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(), 3868 Align, isVol, DstPtrInfo); 3869 3870 if (Result.getNode()) 3871 return Result; 3872 } 3873 3874 // Then check to see if we should lower the memset with target-specific 3875 // code. If the target chooses to do this, this is the next best. 3876 SDValue Result = 3877 TSI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, isVol, 3878 DstPtrInfo); 3879 if (Result.getNode()) 3880 return Result; 3881 3882 // Emit a library call. 3883 Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext()); 3884 TargetLowering::ArgListTy Args; 3885 TargetLowering::ArgListEntry Entry; 3886 Entry.Node = Dst; Entry.Ty = IntPtrTy; 3887 Args.push_back(Entry); 3888 // Extend or truncate the argument to be an i32 value for the call. 3889 if (Src.getValueType().bitsGT(MVT::i32)) 3890 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src); 3891 else 3892 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src); 3893 Entry.Node = Src; 3894 Entry.Ty = Type::getInt32Ty(*getContext()); 3895 Entry.isSExt = true; 3896 Args.push_back(Entry); 3897 Entry.Node = Size; 3898 Entry.Ty = IntPtrTy; 3899 Entry.isSExt = false; 3900 Args.push_back(Entry); 3901 // FIXME: pass in DebugLoc 3902 TargetLowering:: 3903 CallLoweringInfo CLI(Chain, Type::getVoidTy(*getContext()), 3904 false, false, false, false, 0, 3905 TLI.getLibcallCallingConv(RTLIB::MEMSET), 3906 /*isTailCall=*/false, 3907 /*doesNotReturn*/false, /*isReturnValueUsed=*/false, 3908 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET), 3909 TLI.getPointerTy()), 3910 Args, *this, dl); 3911 std::pair<SDValue,SDValue> CallResult = TLI.LowerCallTo(CLI); 3912 3913 return CallResult.second; 3914} 3915 3916SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 3917 SDValue Chain, SDValue Ptr, SDValue Cmp, 3918 SDValue Swp, MachinePointerInfo PtrInfo, 3919 unsigned Alignment, 3920 AtomicOrdering Ordering, 3921 SynchronizationScope SynchScope) { 3922 if (Alignment == 0) // Ensure that codegen never sees alignment 0 3923 Alignment = getEVTAlignment(MemVT); 3924 3925 MachineFunction &MF = getMachineFunction(); 3926 3927 // All atomics are load and store, except for ATMOIC_LOAD and ATOMIC_STORE. 3928 // For now, atomics are considered to be volatile always. 3929 // FIXME: Volatile isn't really correct; we should keep track of atomic 3930 // orderings in the memoperand. 3931 unsigned Flags = MachineMemOperand::MOVolatile; 3932 if (Opcode != ISD::ATOMIC_STORE) 3933 Flags |= MachineMemOperand::MOLoad; 3934 if (Opcode != ISD::ATOMIC_LOAD) 3935 Flags |= MachineMemOperand::MOStore; 3936 3937 MachineMemOperand *MMO = 3938 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment); 3939 3940 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Cmp, Swp, MMO, 3941 Ordering, SynchScope); 3942} 3943 3944SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 3945 SDValue Chain, 3946 SDValue Ptr, SDValue Cmp, 3947 SDValue Swp, MachineMemOperand *MMO, 3948 AtomicOrdering Ordering, 3949 SynchronizationScope SynchScope) { 3950 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op"); 3951 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types"); 3952 3953 EVT VT = Cmp.getValueType(); 3954 3955 SDVTList VTs = getVTList(VT, MVT::Other); 3956 FoldingSetNodeID ID; 3957 ID.AddInteger(MemVT.getRawBits()); 3958 SDValue Ops[] = {Chain, Ptr, Cmp, Swp}; 3959 AddNodeIDNode(ID, Opcode, VTs, Ops, 4); 3960 ID.AddInteger(MMO->getPointerInfo().getAddrSpace()); 3961 void* IP = 0; 3962 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 3963 cast<AtomicSDNode>(E)->refineAlignment(MMO); 3964 return SDValue(E, 0); 3965 } 3966 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain, 3967 Ptr, Cmp, Swp, MMO, Ordering, 3968 SynchScope); 3969 CSEMap.InsertNode(N, IP); 3970 AllNodes.push_back(N); 3971 return SDValue(N, 0); 3972} 3973 3974SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 3975 SDValue Chain, 3976 SDValue Ptr, SDValue Val, 3977 const Value* PtrVal, 3978 unsigned Alignment, 3979 AtomicOrdering Ordering, 3980 SynchronizationScope SynchScope) { 3981 if (Alignment == 0) // Ensure that codegen never sees alignment 0 3982 Alignment = getEVTAlignment(MemVT); 3983 3984 MachineFunction &MF = getMachineFunction(); 3985 // An atomic store does not load. An atomic load does not store. 3986 // (An atomicrmw obviously both loads and stores.) 3987 // For now, atomics are considered to be volatile always, and they are 3988 // chained as such. 3989 // FIXME: Volatile isn't really correct; we should keep track of atomic 3990 // orderings in the memoperand. 3991 unsigned Flags = MachineMemOperand::MOVolatile; 3992 if (Opcode != ISD::ATOMIC_STORE) 3993 Flags |= MachineMemOperand::MOLoad; 3994 if (Opcode != ISD::ATOMIC_LOAD) 3995 Flags |= MachineMemOperand::MOStore; 3996 3997 MachineMemOperand *MMO = 3998 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags, 3999 MemVT.getStoreSize(), Alignment); 4000 4001 return getAtomic(Opcode, dl, MemVT, Chain, Ptr, Val, MMO, 4002 Ordering, SynchScope); 4003} 4004 4005SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 4006 SDValue Chain, 4007 SDValue Ptr, SDValue Val, 4008 MachineMemOperand *MMO, 4009 AtomicOrdering Ordering, 4010 SynchronizationScope SynchScope) { 4011 assert((Opcode == ISD::ATOMIC_LOAD_ADD || 4012 Opcode == ISD::ATOMIC_LOAD_SUB || 4013 Opcode == ISD::ATOMIC_LOAD_AND || 4014 Opcode == ISD::ATOMIC_LOAD_OR || 4015 Opcode == ISD::ATOMIC_LOAD_XOR || 4016 Opcode == ISD::ATOMIC_LOAD_NAND || 4017 Opcode == ISD::ATOMIC_LOAD_MIN || 4018 Opcode == ISD::ATOMIC_LOAD_MAX || 4019 Opcode == ISD::ATOMIC_LOAD_UMIN || 4020 Opcode == ISD::ATOMIC_LOAD_UMAX || 4021 Opcode == ISD::ATOMIC_SWAP || 4022 Opcode == ISD::ATOMIC_STORE) && 4023 "Invalid Atomic Op"); 4024 4025 EVT VT = Val.getValueType(); 4026 4027 SDVTList VTs = Opcode == ISD::ATOMIC_STORE ? getVTList(MVT::Other) : 4028 getVTList(VT, MVT::Other); 4029 FoldingSetNodeID ID; 4030 ID.AddInteger(MemVT.getRawBits()); 4031 SDValue Ops[] = {Chain, Ptr, Val}; 4032 AddNodeIDNode(ID, Opcode, VTs, Ops, 3); 4033 ID.AddInteger(MMO->getPointerInfo().getAddrSpace()); 4034 void* IP = 0; 4035 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 4036 cast<AtomicSDNode>(E)->refineAlignment(MMO); 4037 return SDValue(E, 0); 4038 } 4039 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain, 4040 Ptr, Val, MMO, 4041 Ordering, SynchScope); 4042 CSEMap.InsertNode(N, IP); 4043 AllNodes.push_back(N); 4044 return SDValue(N, 0); 4045} 4046 4047SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 4048 EVT VT, SDValue Chain, 4049 SDValue Ptr, 4050 const Value* PtrVal, 4051 unsigned Alignment, 4052 AtomicOrdering Ordering, 4053 SynchronizationScope SynchScope) { 4054 if (Alignment == 0) // Ensure that codegen never sees alignment 0 4055 Alignment = getEVTAlignment(MemVT); 4056 4057 MachineFunction &MF = getMachineFunction(); 4058 // An atomic store does not load. An atomic load does not store. 4059 // (An atomicrmw obviously both loads and stores.) 4060 // For now, atomics are considered to be volatile always, and they are 4061 // chained as such. 4062 // FIXME: Volatile isn't really correct; we should keep track of atomic 4063 // orderings in the memoperand. 4064 unsigned Flags = MachineMemOperand::MOVolatile; 4065 if (Opcode != ISD::ATOMIC_STORE) 4066 Flags |= MachineMemOperand::MOLoad; 4067 if (Opcode != ISD::ATOMIC_LOAD) 4068 Flags |= MachineMemOperand::MOStore; 4069 4070 MachineMemOperand *MMO = 4071 MF.getMachineMemOperand(MachinePointerInfo(PtrVal), Flags, 4072 MemVT.getStoreSize(), Alignment); 4073 4074 return getAtomic(Opcode, dl, MemVT, VT, Chain, Ptr, MMO, 4075 Ordering, SynchScope); 4076} 4077 4078SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 4079 EVT VT, SDValue Chain, 4080 SDValue Ptr, 4081 MachineMemOperand *MMO, 4082 AtomicOrdering Ordering, 4083 SynchronizationScope SynchScope) { 4084 assert(Opcode == ISD::ATOMIC_LOAD && "Invalid Atomic Op"); 4085 4086 SDVTList VTs = getVTList(VT, MVT::Other); 4087 FoldingSetNodeID ID; 4088 ID.AddInteger(MemVT.getRawBits()); 4089 SDValue Ops[] = {Chain, Ptr}; 4090 AddNodeIDNode(ID, Opcode, VTs, Ops, 2); 4091 ID.AddInteger(MMO->getPointerInfo().getAddrSpace()); 4092 void* IP = 0; 4093 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 4094 cast<AtomicSDNode>(E)->refineAlignment(MMO); 4095 return SDValue(E, 0); 4096 } 4097 SDNode *N = new (NodeAllocator) AtomicSDNode(Opcode, dl, VTs, MemVT, Chain, 4098 Ptr, MMO, Ordering, SynchScope); 4099 CSEMap.InsertNode(N, IP); 4100 AllNodes.push_back(N); 4101 return SDValue(N, 0); 4102} 4103 4104/// getMergeValues - Create a MERGE_VALUES node from the given operands. 4105SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps, 4106 DebugLoc dl) { 4107 if (NumOps == 1) 4108 return Ops[0]; 4109 4110 SmallVector<EVT, 4> VTs; 4111 VTs.reserve(NumOps); 4112 for (unsigned i = 0; i < NumOps; ++i) 4113 VTs.push_back(Ops[i].getValueType()); 4114 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps), 4115 Ops, NumOps); 4116} 4117 4118SDValue 4119SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, 4120 const EVT *VTs, unsigned NumVTs, 4121 const SDValue *Ops, unsigned NumOps, 4122 EVT MemVT, MachinePointerInfo PtrInfo, 4123 unsigned Align, bool Vol, 4124 bool ReadMem, bool WriteMem) { 4125 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps, 4126 MemVT, PtrInfo, Align, Vol, 4127 ReadMem, WriteMem); 4128} 4129 4130SDValue 4131SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 4132 const SDValue *Ops, unsigned NumOps, 4133 EVT MemVT, MachinePointerInfo PtrInfo, 4134 unsigned Align, bool Vol, 4135 bool ReadMem, bool WriteMem) { 4136 if (Align == 0) // Ensure that codegen never sees alignment 0 4137 Align = getEVTAlignment(MemVT); 4138 4139 MachineFunction &MF = getMachineFunction(); 4140 unsigned Flags = 0; 4141 if (WriteMem) 4142 Flags |= MachineMemOperand::MOStore; 4143 if (ReadMem) 4144 Flags |= MachineMemOperand::MOLoad; 4145 if (Vol) 4146 Flags |= MachineMemOperand::MOVolatile; 4147 MachineMemOperand *MMO = 4148 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Align); 4149 4150 return getMemIntrinsicNode(Opcode, dl, VTList, Ops, NumOps, MemVT, MMO); 4151} 4152 4153SDValue 4154SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 4155 const SDValue *Ops, unsigned NumOps, 4156 EVT MemVT, MachineMemOperand *MMO) { 4157 assert((Opcode == ISD::INTRINSIC_VOID || 4158 Opcode == ISD::INTRINSIC_W_CHAIN || 4159 Opcode == ISD::PREFETCH || 4160 Opcode == ISD::LIFETIME_START || 4161 Opcode == ISD::LIFETIME_END || 4162 (Opcode <= INT_MAX && 4163 (int)Opcode >= ISD::FIRST_TARGET_MEMORY_OPCODE)) && 4164 "Opcode is not a memory-accessing opcode!"); 4165 4166 // Memoize the node unless it returns a flag. 4167 MemIntrinsicSDNode *N; 4168 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) { 4169 FoldingSetNodeID ID; 4170 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 4171 ID.AddInteger(MMO->getPointerInfo().getAddrSpace()); 4172 void *IP = 0; 4173 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 4174 cast<MemIntrinsicSDNode>(E)->refineAlignment(MMO); 4175 return SDValue(E, 0); 4176 } 4177 4178 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps, 4179 MemVT, MMO); 4180 CSEMap.InsertNode(N, IP); 4181 } else { 4182 N = new (NodeAllocator) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps, 4183 MemVT, MMO); 4184 } 4185 AllNodes.push_back(N); 4186 return SDValue(N, 0); 4187} 4188 4189/// InferPointerInfo - If the specified ptr/offset is a frame index, infer a 4190/// MachinePointerInfo record from it. This is particularly useful because the 4191/// code generator has many cases where it doesn't bother passing in a 4192/// MachinePointerInfo to getLoad or getStore when it has "FI+Cst". 4193static MachinePointerInfo InferPointerInfo(SDValue Ptr, int64_t Offset = 0) { 4194 // If this is FI+Offset, we can model it. 4195 if (const FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) 4196 return MachinePointerInfo::getFixedStack(FI->getIndex(), Offset); 4197 4198 // If this is (FI+Offset1)+Offset2, we can model it. 4199 if (Ptr.getOpcode() != ISD::ADD || 4200 !isa<ConstantSDNode>(Ptr.getOperand(1)) || 4201 !isa<FrameIndexSDNode>(Ptr.getOperand(0))) 4202 return MachinePointerInfo(); 4203 4204 int FI = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex(); 4205 return MachinePointerInfo::getFixedStack(FI, Offset+ 4206 cast<ConstantSDNode>(Ptr.getOperand(1))->getSExtValue()); 4207} 4208 4209/// InferPointerInfo - If the specified ptr/offset is a frame index, infer a 4210/// MachinePointerInfo record from it. This is particularly useful because the 4211/// code generator has many cases where it doesn't bother passing in a 4212/// MachinePointerInfo to getLoad or getStore when it has "FI+Cst". 4213static MachinePointerInfo InferPointerInfo(SDValue Ptr, SDValue OffsetOp) { 4214 // If the 'Offset' value isn't a constant, we can't handle this. 4215 if (ConstantSDNode *OffsetNode = dyn_cast<ConstantSDNode>(OffsetOp)) 4216 return InferPointerInfo(Ptr, OffsetNode->getSExtValue()); 4217 if (OffsetOp.getOpcode() == ISD::UNDEF) 4218 return InferPointerInfo(Ptr); 4219 return MachinePointerInfo(); 4220} 4221 4222 4223SDValue 4224SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 4225 EVT VT, DebugLoc dl, SDValue Chain, 4226 SDValue Ptr, SDValue Offset, 4227 MachinePointerInfo PtrInfo, EVT MemVT, 4228 bool isVolatile, bool isNonTemporal, bool isInvariant, 4229 unsigned Alignment, const MDNode *TBAAInfo, 4230 const MDNode *Ranges) { 4231 assert(Chain.getValueType() == MVT::Other && 4232 "Invalid chain type"); 4233 if (Alignment == 0) // Ensure that codegen never sees alignment 0 4234 Alignment = getEVTAlignment(VT); 4235 4236 unsigned Flags = MachineMemOperand::MOLoad; 4237 if (isVolatile) 4238 Flags |= MachineMemOperand::MOVolatile; 4239 if (isNonTemporal) 4240 Flags |= MachineMemOperand::MONonTemporal; 4241 if (isInvariant) 4242 Flags |= MachineMemOperand::MOInvariant; 4243 4244 // If we don't have a PtrInfo, infer the trivial frame index case to simplify 4245 // clients. 4246 if (PtrInfo.V == 0) 4247 PtrInfo = InferPointerInfo(Ptr, Offset); 4248 4249 MachineFunction &MF = getMachineFunction(); 4250 MachineMemOperand *MMO = 4251 MF.getMachineMemOperand(PtrInfo, Flags, MemVT.getStoreSize(), Alignment, 4252 TBAAInfo, Ranges); 4253 return getLoad(AM, ExtType, VT, dl, Chain, Ptr, Offset, MemVT, MMO); 4254} 4255 4256SDValue 4257SelectionDAG::getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, 4258 EVT VT, DebugLoc dl, SDValue Chain, 4259 SDValue Ptr, SDValue Offset, EVT MemVT, 4260 MachineMemOperand *MMO) { 4261 if (VT == MemVT) { 4262 ExtType = ISD::NON_EXTLOAD; 4263 } else if (ExtType == ISD::NON_EXTLOAD) { 4264 assert(VT == MemVT && "Non-extending load from different memory type!"); 4265 } else { 4266 // Extending load. 4267 assert(MemVT.getScalarType().bitsLT(VT.getScalarType()) && 4268 "Should only be an extending load, not truncating!"); 4269 assert(VT.isInteger() == MemVT.isInteger() && 4270 "Cannot convert from FP to Int or Int -> FP!"); 4271 assert(VT.isVector() == MemVT.isVector() && 4272 "Cannot use trunc store to convert to or from a vector!"); 4273 assert((!VT.isVector() || 4274 VT.getVectorNumElements() == MemVT.getVectorNumElements()) && 4275 "Cannot use trunc store to change the number of vector elements!"); 4276 } 4277 4278 bool Indexed = AM != ISD::UNINDEXED; 4279 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) && 4280 "Unindexed load with an offset!"); 4281 4282 SDVTList VTs = Indexed ? 4283 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other); 4284 SDValue Ops[] = { Chain, Ptr, Offset }; 4285 FoldingSetNodeID ID; 4286 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); 4287 ID.AddInteger(MemVT.getRawBits()); 4288 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, MMO->isVolatile(), 4289 MMO->isNonTemporal(), 4290 MMO->isInvariant())); 4291 ID.AddInteger(MMO->getPointerInfo().getAddrSpace()); 4292 void *IP = 0; 4293 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 4294 cast<LoadSDNode>(E)->refineAlignment(MMO); 4295 return SDValue(E, 0); 4296 } 4297 SDNode *N = new (NodeAllocator) LoadSDNode(Ops, dl, VTs, AM, ExtType, 4298 MemVT, MMO); 4299 CSEMap.InsertNode(N, IP); 4300 AllNodes.push_back(N); 4301 return SDValue(N, 0); 4302} 4303 4304SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl, 4305 SDValue Chain, SDValue Ptr, 4306 MachinePointerInfo PtrInfo, 4307 bool isVolatile, bool isNonTemporal, 4308 bool isInvariant, unsigned Alignment, 4309 const MDNode *TBAAInfo, 4310 const MDNode *Ranges) { 4311 SDValue Undef = getUNDEF(Ptr.getValueType()); 4312 return getLoad(ISD::UNINDEXED, ISD::NON_EXTLOAD, VT, dl, Chain, Ptr, Undef, 4313 PtrInfo, VT, isVolatile, isNonTemporal, isInvariant, Alignment, 4314 TBAAInfo, Ranges); 4315} 4316 4317SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT, 4318 SDValue Chain, SDValue Ptr, 4319 MachinePointerInfo PtrInfo, EVT MemVT, 4320 bool isVolatile, bool isNonTemporal, 4321 unsigned Alignment, const MDNode *TBAAInfo) { 4322 SDValue Undef = getUNDEF(Ptr.getValueType()); 4323 return getLoad(ISD::UNINDEXED, ExtType, VT, dl, Chain, Ptr, Undef, 4324 PtrInfo, MemVT, isVolatile, isNonTemporal, false, Alignment, 4325 TBAAInfo); 4326} 4327 4328 4329SDValue 4330SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, 4331 SDValue Offset, ISD::MemIndexedMode AM) { 4332 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad); 4333 assert(LD->getOffset().getOpcode() == ISD::UNDEF && 4334 "Load is already a indexed load!"); 4335 return getLoad(AM, LD->getExtensionType(), OrigLoad.getValueType(), dl, 4336 LD->getChain(), Base, Offset, LD->getPointerInfo(), 4337 LD->getMemoryVT(), LD->isVolatile(), LD->isNonTemporal(), 4338 false, LD->getAlignment()); 4339} 4340 4341SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val, 4342 SDValue Ptr, MachinePointerInfo PtrInfo, 4343 bool isVolatile, bool isNonTemporal, 4344 unsigned Alignment, const MDNode *TBAAInfo) { 4345 assert(Chain.getValueType() == MVT::Other && 4346 "Invalid chain type"); 4347 if (Alignment == 0) // Ensure that codegen never sees alignment 0 4348 Alignment = getEVTAlignment(Val.getValueType()); 4349 4350 unsigned Flags = MachineMemOperand::MOStore; 4351 if (isVolatile) 4352 Flags |= MachineMemOperand::MOVolatile; 4353 if (isNonTemporal) 4354 Flags |= MachineMemOperand::MONonTemporal; 4355 4356 if (PtrInfo.V == 0) 4357 PtrInfo = InferPointerInfo(Ptr); 4358 4359 MachineFunction &MF = getMachineFunction(); 4360 MachineMemOperand *MMO = 4361 MF.getMachineMemOperand(PtrInfo, Flags, 4362 Val.getValueType().getStoreSize(), Alignment, 4363 TBAAInfo); 4364 4365 return getStore(Chain, dl, Val, Ptr, MMO); 4366} 4367 4368SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val, 4369 SDValue Ptr, MachineMemOperand *MMO) { 4370 assert(Chain.getValueType() == MVT::Other && 4371 "Invalid chain type"); 4372 EVT VT = Val.getValueType(); 4373 SDVTList VTs = getVTList(MVT::Other); 4374 SDValue Undef = getUNDEF(Ptr.getValueType()); 4375 SDValue Ops[] = { Chain, Val, Ptr, Undef }; 4376 FoldingSetNodeID ID; 4377 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 4378 ID.AddInteger(VT.getRawBits()); 4379 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, MMO->isVolatile(), 4380 MMO->isNonTemporal(), MMO->isInvariant())); 4381 ID.AddInteger(MMO->getPointerInfo().getAddrSpace()); 4382 void *IP = 0; 4383 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 4384 cast<StoreSDNode>(E)->refineAlignment(MMO); 4385 return SDValue(E, 0); 4386 } 4387 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED, 4388 false, VT, MMO); 4389 CSEMap.InsertNode(N, IP); 4390 AllNodes.push_back(N); 4391 return SDValue(N, 0); 4392} 4393 4394SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, 4395 SDValue Ptr, MachinePointerInfo PtrInfo, 4396 EVT SVT,bool isVolatile, bool isNonTemporal, 4397 unsigned Alignment, 4398 const MDNode *TBAAInfo) { 4399 assert(Chain.getValueType() == MVT::Other && 4400 "Invalid chain type"); 4401 if (Alignment == 0) // Ensure that codegen never sees alignment 0 4402 Alignment = getEVTAlignment(SVT); 4403 4404 unsigned Flags = MachineMemOperand::MOStore; 4405 if (isVolatile) 4406 Flags |= MachineMemOperand::MOVolatile; 4407 if (isNonTemporal) 4408 Flags |= MachineMemOperand::MONonTemporal; 4409 4410 if (PtrInfo.V == 0) 4411 PtrInfo = InferPointerInfo(Ptr); 4412 4413 MachineFunction &MF = getMachineFunction(); 4414 MachineMemOperand *MMO = 4415 MF.getMachineMemOperand(PtrInfo, Flags, SVT.getStoreSize(), Alignment, 4416 TBAAInfo); 4417 4418 return getTruncStore(Chain, dl, Val, Ptr, SVT, MMO); 4419} 4420 4421SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, 4422 SDValue Ptr, EVT SVT, 4423 MachineMemOperand *MMO) { 4424 EVT VT = Val.getValueType(); 4425 4426 assert(Chain.getValueType() == MVT::Other && 4427 "Invalid chain type"); 4428 if (VT == SVT) 4429 return getStore(Chain, dl, Val, Ptr, MMO); 4430 4431 assert(SVT.getScalarType().bitsLT(VT.getScalarType()) && 4432 "Should only be a truncating store, not extending!"); 4433 assert(VT.isInteger() == SVT.isInteger() && 4434 "Can't do FP-INT conversion!"); 4435 assert(VT.isVector() == SVT.isVector() && 4436 "Cannot use trunc store to convert to or from a vector!"); 4437 assert((!VT.isVector() || 4438 VT.getVectorNumElements() == SVT.getVectorNumElements()) && 4439 "Cannot use trunc store to change the number of vector elements!"); 4440 4441 SDVTList VTs = getVTList(MVT::Other); 4442 SDValue Undef = getUNDEF(Ptr.getValueType()); 4443 SDValue Ops[] = { Chain, Val, Ptr, Undef }; 4444 FoldingSetNodeID ID; 4445 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 4446 ID.AddInteger(SVT.getRawBits()); 4447 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, MMO->isVolatile(), 4448 MMO->isNonTemporal(), MMO->isInvariant())); 4449 ID.AddInteger(MMO->getPointerInfo().getAddrSpace()); 4450 void *IP = 0; 4451 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 4452 cast<StoreSDNode>(E)->refineAlignment(MMO); 4453 return SDValue(E, 0); 4454 } 4455 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED, 4456 true, SVT, MMO); 4457 CSEMap.InsertNode(N, IP); 4458 AllNodes.push_back(N); 4459 return SDValue(N, 0); 4460} 4461 4462SDValue 4463SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base, 4464 SDValue Offset, ISD::MemIndexedMode AM) { 4465 StoreSDNode *ST = cast<StoreSDNode>(OrigStore); 4466 assert(ST->getOffset().getOpcode() == ISD::UNDEF && 4467 "Store is already a indexed store!"); 4468 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other); 4469 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset }; 4470 FoldingSetNodeID ID; 4471 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 4472 ID.AddInteger(ST->getMemoryVT().getRawBits()); 4473 ID.AddInteger(ST->getRawSubclassData()); 4474 ID.AddInteger(ST->getPointerInfo().getAddrSpace()); 4475 void *IP = 0; 4476 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 4477 return SDValue(E, 0); 4478 4479 SDNode *N = new (NodeAllocator) StoreSDNode(Ops, dl, VTs, AM, 4480 ST->isTruncatingStore(), 4481 ST->getMemoryVT(), 4482 ST->getMemOperand()); 4483 CSEMap.InsertNode(N, IP); 4484 AllNodes.push_back(N); 4485 return SDValue(N, 0); 4486} 4487 4488SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl, 4489 SDValue Chain, SDValue Ptr, 4490 SDValue SV, 4491 unsigned Align) { 4492 SDValue Ops[] = { Chain, Ptr, SV, getTargetConstant(Align, MVT::i32) }; 4493 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 4); 4494} 4495 4496SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 4497 const SDUse *Ops, unsigned NumOps) { 4498 switch (NumOps) { 4499 case 0: return getNode(Opcode, DL, VT); 4500 case 1: return getNode(Opcode, DL, VT, Ops[0]); 4501 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]); 4502 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]); 4503 default: break; 4504 } 4505 4506 // Copy from an SDUse array into an SDValue array for use with 4507 // the regular getNode logic. 4508 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps); 4509 return getNode(Opcode, DL, VT, &NewOps[0], NumOps); 4510} 4511 4512SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 4513 const SDValue *Ops, unsigned NumOps) { 4514 switch (NumOps) { 4515 case 0: return getNode(Opcode, DL, VT); 4516 case 1: return getNode(Opcode, DL, VT, Ops[0]); 4517 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]); 4518 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]); 4519 default: break; 4520 } 4521 4522 switch (Opcode) { 4523 default: break; 4524 case ISD::SELECT_CC: { 4525 assert(NumOps == 5 && "SELECT_CC takes 5 operands!"); 4526 assert(Ops[0].getValueType() == Ops[1].getValueType() && 4527 "LHS and RHS of condition must have same type!"); 4528 assert(Ops[2].getValueType() == Ops[3].getValueType() && 4529 "True and False arms of SelectCC must have same type!"); 4530 assert(Ops[2].getValueType() == VT && 4531 "select_cc node must be of same type as true and false value!"); 4532 break; 4533 } 4534 case ISD::BR_CC: { 4535 assert(NumOps == 5 && "BR_CC takes 5 operands!"); 4536 assert(Ops[2].getValueType() == Ops[3].getValueType() && 4537 "LHS/RHS of comparison should match types!"); 4538 break; 4539 } 4540 } 4541 4542 // Memoize nodes. 4543 SDNode *N; 4544 SDVTList VTs = getVTList(VT); 4545 4546 if (VT != MVT::Glue) { 4547 FoldingSetNodeID ID; 4548 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps); 4549 void *IP = 0; 4550 4551 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 4552 return SDValue(E, 0); 4553 4554 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps); 4555 CSEMap.InsertNode(N, IP); 4556 } else { 4557 N = new (NodeAllocator) SDNode(Opcode, DL, VTs, Ops, NumOps); 4558 } 4559 4560 AllNodes.push_back(N); 4561#ifndef NDEBUG 4562 VerifySDNode(N); 4563#endif 4564 return SDValue(N, 0); 4565} 4566 4567SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, 4568 const std::vector<EVT> &ResultTys, 4569 const SDValue *Ops, unsigned NumOps) { 4570 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()), 4571 Ops, NumOps); 4572} 4573 4574SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, 4575 const EVT *VTs, unsigned NumVTs, 4576 const SDValue *Ops, unsigned NumOps) { 4577 if (NumVTs == 1) 4578 return getNode(Opcode, DL, VTs[0], Ops, NumOps); 4579 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps); 4580} 4581 4582SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4583 const SDValue *Ops, unsigned NumOps) { 4584 if (VTList.NumVTs == 1) 4585 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps); 4586 4587#if 0 4588 switch (Opcode) { 4589 // FIXME: figure out how to safely handle things like 4590 // int foo(int x) { return 1 << (x & 255); } 4591 // int bar() { return foo(256); } 4592 case ISD::SRA_PARTS: 4593 case ISD::SRL_PARTS: 4594 case ISD::SHL_PARTS: 4595 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG && 4596 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1) 4597 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0)); 4598 else if (N3.getOpcode() == ISD::AND) 4599 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) { 4600 // If the and is only masking out bits that cannot effect the shift, 4601 // eliminate the and. 4602 unsigned NumBits = VT.getScalarType().getSizeInBits()*2; 4603 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 4604 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0)); 4605 } 4606 break; 4607 } 4608#endif 4609 4610 // Memoize the node unless it returns a flag. 4611 SDNode *N; 4612 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) { 4613 FoldingSetNodeID ID; 4614 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 4615 void *IP = 0; 4616 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 4617 return SDValue(E, 0); 4618 4619 if (NumOps == 1) { 4620 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]); 4621 } else if (NumOps == 2) { 4622 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]); 4623 } else if (NumOps == 3) { 4624 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1], 4625 Ops[2]); 4626 } else { 4627 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps); 4628 } 4629 CSEMap.InsertNode(N, IP); 4630 } else { 4631 if (NumOps == 1) { 4632 N = new (NodeAllocator) UnarySDNode(Opcode, DL, VTList, Ops[0]); 4633 } else if (NumOps == 2) { 4634 N = new (NodeAllocator) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]); 4635 } else if (NumOps == 3) { 4636 N = new (NodeAllocator) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1], 4637 Ops[2]); 4638 } else { 4639 N = new (NodeAllocator) SDNode(Opcode, DL, VTList, Ops, NumOps); 4640 } 4641 } 4642 AllNodes.push_back(N); 4643#ifndef NDEBUG 4644 VerifySDNode(N); 4645#endif 4646 return SDValue(N, 0); 4647} 4648 4649SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) { 4650 return getNode(Opcode, DL, VTList, 0, 0); 4651} 4652 4653SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4654 SDValue N1) { 4655 SDValue Ops[] = { N1 }; 4656 return getNode(Opcode, DL, VTList, Ops, 1); 4657} 4658 4659SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4660 SDValue N1, SDValue N2) { 4661 SDValue Ops[] = { N1, N2 }; 4662 return getNode(Opcode, DL, VTList, Ops, 2); 4663} 4664 4665SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4666 SDValue N1, SDValue N2, SDValue N3) { 4667 SDValue Ops[] = { N1, N2, N3 }; 4668 return getNode(Opcode, DL, VTList, Ops, 3); 4669} 4670 4671SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4672 SDValue N1, SDValue N2, SDValue N3, 4673 SDValue N4) { 4674 SDValue Ops[] = { N1, N2, N3, N4 }; 4675 return getNode(Opcode, DL, VTList, Ops, 4); 4676} 4677 4678SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 4679 SDValue N1, SDValue N2, SDValue N3, 4680 SDValue N4, SDValue N5) { 4681 SDValue Ops[] = { N1, N2, N3, N4, N5 }; 4682 return getNode(Opcode, DL, VTList, Ops, 5); 4683} 4684 4685SDVTList SelectionDAG::getVTList(EVT VT) { 4686 return makeVTList(SDNode::getValueTypeList(VT), 1); 4687} 4688 4689SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) { 4690 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 4691 E = VTList.rend(); I != E; ++I) 4692 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2) 4693 return *I; 4694 4695 EVT *Array = Allocator.Allocate<EVT>(2); 4696 Array[0] = VT1; 4697 Array[1] = VT2; 4698 SDVTList Result = makeVTList(Array, 2); 4699 VTList.push_back(Result); 4700 return Result; 4701} 4702 4703SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) { 4704 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 4705 E = VTList.rend(); I != E; ++I) 4706 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 && 4707 I->VTs[2] == VT3) 4708 return *I; 4709 4710 EVT *Array = Allocator.Allocate<EVT>(3); 4711 Array[0] = VT1; 4712 Array[1] = VT2; 4713 Array[2] = VT3; 4714 SDVTList Result = makeVTList(Array, 3); 4715 VTList.push_back(Result); 4716 return Result; 4717} 4718 4719SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) { 4720 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 4721 E = VTList.rend(); I != E; ++I) 4722 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 && 4723 I->VTs[2] == VT3 && I->VTs[3] == VT4) 4724 return *I; 4725 4726 EVT *Array = Allocator.Allocate<EVT>(4); 4727 Array[0] = VT1; 4728 Array[1] = VT2; 4729 Array[2] = VT3; 4730 Array[3] = VT4; 4731 SDVTList Result = makeVTList(Array, 4); 4732 VTList.push_back(Result); 4733 return Result; 4734} 4735 4736SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) { 4737 switch (NumVTs) { 4738 case 0: llvm_unreachable("Cannot have nodes without results!"); 4739 case 1: return getVTList(VTs[0]); 4740 case 2: return getVTList(VTs[0], VTs[1]); 4741 case 3: return getVTList(VTs[0], VTs[1], VTs[2]); 4742 case 4: return getVTList(VTs[0], VTs[1], VTs[2], VTs[3]); 4743 default: break; 4744 } 4745 4746 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 4747 E = VTList.rend(); I != E; ++I) { 4748 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1]) 4749 continue; 4750 4751 if (std::equal(&VTs[2], &VTs[NumVTs], &I->VTs[2])) 4752 return *I; 4753 } 4754 4755 EVT *Array = Allocator.Allocate<EVT>(NumVTs); 4756 std::copy(VTs, VTs+NumVTs, Array); 4757 SDVTList Result = makeVTList(Array, NumVTs); 4758 VTList.push_back(Result); 4759 return Result; 4760} 4761 4762 4763/// UpdateNodeOperands - *Mutate* the specified node in-place to have the 4764/// specified operands. If the resultant node already exists in the DAG, 4765/// this does not modify the specified node, instead it returns the node that 4766/// already exists. If the resultant node does not exist in the DAG, the 4767/// input node is returned. As a degenerate case, if you specify the same 4768/// input operands as the node already has, the input node is returned. 4769SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op) { 4770 assert(N->getNumOperands() == 1 && "Update with wrong number of operands"); 4771 4772 // Check to see if there is no change. 4773 if (Op == N->getOperand(0)) return N; 4774 4775 // See if the modified node already exists. 4776 void *InsertPos = 0; 4777 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos)) 4778 return Existing; 4779 4780 // Nope it doesn't. Remove the node from its current place in the maps. 4781 if (InsertPos) 4782 if (!RemoveNodeFromCSEMaps(N)) 4783 InsertPos = 0; 4784 4785 // Now we update the operands. 4786 N->OperandList[0].set(Op); 4787 4788 // If this gets put into a CSE map, add it. 4789 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 4790 return N; 4791} 4792 4793SDNode *SelectionDAG::UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2) { 4794 assert(N->getNumOperands() == 2 && "Update with wrong number of operands"); 4795 4796 // Check to see if there is no change. 4797 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1)) 4798 return N; // No operands changed, just return the input node. 4799 4800 // See if the modified node already exists. 4801 void *InsertPos = 0; 4802 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos)) 4803 return Existing; 4804 4805 // Nope it doesn't. Remove the node from its current place in the maps. 4806 if (InsertPos) 4807 if (!RemoveNodeFromCSEMaps(N)) 4808 InsertPos = 0; 4809 4810 // Now we update the operands. 4811 if (N->OperandList[0] != Op1) 4812 N->OperandList[0].set(Op1); 4813 if (N->OperandList[1] != Op2) 4814 N->OperandList[1].set(Op2); 4815 4816 // If this gets put into a CSE map, add it. 4817 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 4818 return N; 4819} 4820 4821SDNode *SelectionDAG:: 4822UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, SDValue Op3) { 4823 SDValue Ops[] = { Op1, Op2, Op3 }; 4824 return UpdateNodeOperands(N, Ops, 3); 4825} 4826 4827SDNode *SelectionDAG:: 4828UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 4829 SDValue Op3, SDValue Op4) { 4830 SDValue Ops[] = { Op1, Op2, Op3, Op4 }; 4831 return UpdateNodeOperands(N, Ops, 4); 4832} 4833 4834SDNode *SelectionDAG:: 4835UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2, 4836 SDValue Op3, SDValue Op4, SDValue Op5) { 4837 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 }; 4838 return UpdateNodeOperands(N, Ops, 5); 4839} 4840 4841SDNode *SelectionDAG:: 4842UpdateNodeOperands(SDNode *N, const SDValue *Ops, unsigned NumOps) { 4843 assert(N->getNumOperands() == NumOps && 4844 "Update with wrong number of operands"); 4845 4846 // Check to see if there is no change. 4847 bool AnyChange = false; 4848 for (unsigned i = 0; i != NumOps; ++i) { 4849 if (Ops[i] != N->getOperand(i)) { 4850 AnyChange = true; 4851 break; 4852 } 4853 } 4854 4855 // No operands changed, just return the input node. 4856 if (!AnyChange) return N; 4857 4858 // See if the modified node already exists. 4859 void *InsertPos = 0; 4860 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos)) 4861 return Existing; 4862 4863 // Nope it doesn't. Remove the node from its current place in the maps. 4864 if (InsertPos) 4865 if (!RemoveNodeFromCSEMaps(N)) 4866 InsertPos = 0; 4867 4868 // Now we update the operands. 4869 for (unsigned i = 0; i != NumOps; ++i) 4870 if (N->OperandList[i] != Ops[i]) 4871 N->OperandList[i].set(Ops[i]); 4872 4873 // If this gets put into a CSE map, add it. 4874 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 4875 return N; 4876} 4877 4878/// DropOperands - Release the operands and set this node to have 4879/// zero operands. 4880void SDNode::DropOperands() { 4881 // Unlike the code in MorphNodeTo that does this, we don't need to 4882 // watch for dead nodes here. 4883 for (op_iterator I = op_begin(), E = op_end(); I != E; ) { 4884 SDUse &Use = *I++; 4885 Use.set(SDValue()); 4886 } 4887} 4888 4889/// SelectNodeTo - These are wrappers around MorphNodeTo that accept a 4890/// machine opcode. 4891/// 4892SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4893 EVT VT) { 4894 SDVTList VTs = getVTList(VT); 4895 return SelectNodeTo(N, MachineOpc, VTs, 0, 0); 4896} 4897 4898SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4899 EVT VT, SDValue Op1) { 4900 SDVTList VTs = getVTList(VT); 4901 SDValue Ops[] = { Op1 }; 4902 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1); 4903} 4904 4905SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4906 EVT VT, SDValue Op1, 4907 SDValue Op2) { 4908 SDVTList VTs = getVTList(VT); 4909 SDValue Ops[] = { Op1, Op2 }; 4910 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2); 4911} 4912 4913SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4914 EVT VT, SDValue Op1, 4915 SDValue Op2, SDValue Op3) { 4916 SDVTList VTs = getVTList(VT); 4917 SDValue Ops[] = { Op1, Op2, Op3 }; 4918 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); 4919} 4920 4921SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4922 EVT VT, const SDValue *Ops, 4923 unsigned NumOps) { 4924 SDVTList VTs = getVTList(VT); 4925 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 4926} 4927 4928SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4929 EVT VT1, EVT VT2, const SDValue *Ops, 4930 unsigned NumOps) { 4931 SDVTList VTs = getVTList(VT1, VT2); 4932 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 4933} 4934 4935SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4936 EVT VT1, EVT VT2) { 4937 SDVTList VTs = getVTList(VT1, VT2); 4938 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0); 4939} 4940 4941SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4942 EVT VT1, EVT VT2, EVT VT3, 4943 const SDValue *Ops, unsigned NumOps) { 4944 SDVTList VTs = getVTList(VT1, VT2, VT3); 4945 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 4946} 4947 4948SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4949 EVT VT1, EVT VT2, EVT VT3, EVT VT4, 4950 const SDValue *Ops, unsigned NumOps) { 4951 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4); 4952 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 4953} 4954 4955SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4956 EVT VT1, EVT VT2, 4957 SDValue Op1) { 4958 SDVTList VTs = getVTList(VT1, VT2); 4959 SDValue Ops[] = { Op1 }; 4960 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1); 4961} 4962 4963SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4964 EVT VT1, EVT VT2, 4965 SDValue Op1, SDValue Op2) { 4966 SDVTList VTs = getVTList(VT1, VT2); 4967 SDValue Ops[] = { Op1, Op2 }; 4968 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2); 4969} 4970 4971SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4972 EVT VT1, EVT VT2, 4973 SDValue Op1, SDValue Op2, 4974 SDValue Op3) { 4975 SDVTList VTs = getVTList(VT1, VT2); 4976 SDValue Ops[] = { Op1, Op2, Op3 }; 4977 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); 4978} 4979 4980SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4981 EVT VT1, EVT VT2, EVT VT3, 4982 SDValue Op1, SDValue Op2, 4983 SDValue Op3) { 4984 SDVTList VTs = getVTList(VT1, VT2, VT3); 4985 SDValue Ops[] = { Op1, Op2, Op3 }; 4986 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); 4987} 4988 4989SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 4990 SDVTList VTs, const SDValue *Ops, 4991 unsigned NumOps) { 4992 N = MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps); 4993 // Reset the NodeID to -1. 4994 N->setNodeId(-1); 4995 return N; 4996} 4997 4998/// UpdadeDebugLocOnMergedSDNode - If the opt level is -O0 then it throws away 4999/// the line number information on the merged node since it is not possible to 5000/// preserve the information that operation is associated with multiple lines. 5001/// This will make the debugger working better at -O0, were there is a higher 5002/// probability having other instructions associated with that line. 5003/// 5004SDNode *SelectionDAG::UpdadeDebugLocOnMergedSDNode(SDNode *N, DebugLoc OLoc) { 5005 DebugLoc NLoc = N->getDebugLoc(); 5006 if (!(NLoc.isUnknown()) && (OptLevel == CodeGenOpt::None) && (OLoc != NLoc)) { 5007 N->setDebugLoc(DebugLoc()); 5008 } 5009 return N; 5010} 5011 5012/// MorphNodeTo - This *mutates* the specified node to have the specified 5013/// return type, opcode, and operands. 5014/// 5015/// Note that MorphNodeTo returns the resultant node. If there is already a 5016/// node of the specified opcode and operands, it returns that node instead of 5017/// the current one. Note that the DebugLoc need not be the same. 5018/// 5019/// Using MorphNodeTo is faster than creating a new node and swapping it in 5020/// with ReplaceAllUsesWith both because it often avoids allocating a new 5021/// node, and because it doesn't require CSE recalculation for any of 5022/// the node's users. 5023/// 5024SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 5025 SDVTList VTs, const SDValue *Ops, 5026 unsigned NumOps) { 5027 // If an identical node already exists, use it. 5028 void *IP = 0; 5029 if (VTs.VTs[VTs.NumVTs-1] != MVT::Glue) { 5030 FoldingSetNodeID ID; 5031 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps); 5032 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 5033 return UpdadeDebugLocOnMergedSDNode(ON, N->getDebugLoc()); 5034 } 5035 5036 if (!RemoveNodeFromCSEMaps(N)) 5037 IP = 0; 5038 5039 // Start the morphing. 5040 N->NodeType = Opc; 5041 N->ValueList = VTs.VTs; 5042 N->NumValues = VTs.NumVTs; 5043 5044 // Clear the operands list, updating used nodes to remove this from their 5045 // use list. Keep track of any operands that become dead as a result. 5046 SmallPtrSet<SDNode*, 16> DeadNodeSet; 5047 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) { 5048 SDUse &Use = *I++; 5049 SDNode *Used = Use.getNode(); 5050 Use.set(SDValue()); 5051 if (Used->use_empty()) 5052 DeadNodeSet.insert(Used); 5053 } 5054 5055 if (MachineSDNode *MN = dyn_cast<MachineSDNode>(N)) { 5056 // Initialize the memory references information. 5057 MN->setMemRefs(0, 0); 5058 // If NumOps is larger than the # of operands we can have in a 5059 // MachineSDNode, reallocate the operand list. 5060 if (NumOps > MN->NumOperands || !MN->OperandsNeedDelete) { 5061 if (MN->OperandsNeedDelete) 5062 delete[] MN->OperandList; 5063 if (NumOps > array_lengthof(MN->LocalOperands)) 5064 // We're creating a final node that will live unmorphed for the 5065 // remainder of the current SelectionDAG iteration, so we can allocate 5066 // the operands directly out of a pool with no recycling metadata. 5067 MN->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps), 5068 Ops, NumOps); 5069 else 5070 MN->InitOperands(MN->LocalOperands, Ops, NumOps); 5071 MN->OperandsNeedDelete = false; 5072 } else 5073 MN->InitOperands(MN->OperandList, Ops, NumOps); 5074 } else { 5075 // If NumOps is larger than the # of operands we currently have, reallocate 5076 // the operand list. 5077 if (NumOps > N->NumOperands) { 5078 if (N->OperandsNeedDelete) 5079 delete[] N->OperandList; 5080 N->InitOperands(new SDUse[NumOps], Ops, NumOps); 5081 N->OperandsNeedDelete = true; 5082 } else 5083 N->InitOperands(N->OperandList, Ops, NumOps); 5084 } 5085 5086 // Delete any nodes that are still dead after adding the uses for the 5087 // new operands. 5088 if (!DeadNodeSet.empty()) { 5089 SmallVector<SDNode *, 16> DeadNodes; 5090 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(), 5091 E = DeadNodeSet.end(); I != E; ++I) 5092 if ((*I)->use_empty()) 5093 DeadNodes.push_back(*I); 5094 RemoveDeadNodes(DeadNodes); 5095 } 5096 5097 if (IP) 5098 CSEMap.InsertNode(N, IP); // Memoize the new node. 5099 return N; 5100} 5101 5102 5103/// getMachineNode - These are used for target selectors to create a new node 5104/// with specified return type(s), MachineInstr opcode, and operands. 5105/// 5106/// Note that getMachineNode returns the resultant node. If there is already a 5107/// node of the specified opcode and operands, it returns that node instead of 5108/// the current one. 5109MachineSDNode * 5110SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT) { 5111 SDVTList VTs = getVTList(VT); 5112 return getMachineNode(Opcode, dl, VTs, 0, 0); 5113} 5114 5115MachineSDNode * 5116SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, SDValue Op1) { 5117 SDVTList VTs = getVTList(VT); 5118 SDValue Ops[] = { Op1 }; 5119 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 5120} 5121 5122MachineSDNode * 5123SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 5124 SDValue Op1, SDValue Op2) { 5125 SDVTList VTs = getVTList(VT); 5126 SDValue Ops[] = { Op1, Op2 }; 5127 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 5128} 5129 5130MachineSDNode * 5131SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 5132 SDValue Op1, SDValue Op2, SDValue Op3) { 5133 SDVTList VTs = getVTList(VT); 5134 SDValue Ops[] = { Op1, Op2, Op3 }; 5135 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 5136} 5137 5138MachineSDNode * 5139SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT, 5140 const SDValue *Ops, unsigned NumOps) { 5141 SDVTList VTs = getVTList(VT); 5142 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 5143} 5144 5145MachineSDNode * 5146SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, EVT VT2) { 5147 SDVTList VTs = getVTList(VT1, VT2); 5148 return getMachineNode(Opcode, dl, VTs, 0, 0); 5149} 5150 5151MachineSDNode * 5152SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 5153 EVT VT1, EVT VT2, SDValue Op1) { 5154 SDVTList VTs = getVTList(VT1, VT2); 5155 SDValue Ops[] = { Op1 }; 5156 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 5157} 5158 5159MachineSDNode * 5160SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 5161 EVT VT1, EVT VT2, SDValue Op1, SDValue Op2) { 5162 SDVTList VTs = getVTList(VT1, VT2); 5163 SDValue Ops[] = { Op1, Op2 }; 5164 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 5165} 5166 5167MachineSDNode * 5168SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 5169 EVT VT1, EVT VT2, SDValue Op1, 5170 SDValue Op2, SDValue Op3) { 5171 SDVTList VTs = getVTList(VT1, VT2); 5172 SDValue Ops[] = { Op1, Op2, Op3 }; 5173 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 5174} 5175 5176MachineSDNode * 5177SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 5178 EVT VT1, EVT VT2, 5179 const SDValue *Ops, unsigned NumOps) { 5180 SDVTList VTs = getVTList(VT1, VT2); 5181 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 5182} 5183 5184MachineSDNode * 5185SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 5186 EVT VT1, EVT VT2, EVT VT3, 5187 SDValue Op1, SDValue Op2) { 5188 SDVTList VTs = getVTList(VT1, VT2, VT3); 5189 SDValue Ops[] = { Op1, Op2 }; 5190 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 5191} 5192 5193MachineSDNode * 5194SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 5195 EVT VT1, EVT VT2, EVT VT3, 5196 SDValue Op1, SDValue Op2, SDValue Op3) { 5197 SDVTList VTs = getVTList(VT1, VT2, VT3); 5198 SDValue Ops[] = { Op1, Op2, Op3 }; 5199 return getMachineNode(Opcode, dl, VTs, Ops, array_lengthof(Ops)); 5200} 5201 5202MachineSDNode * 5203SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 5204 EVT VT1, EVT VT2, EVT VT3, 5205 const SDValue *Ops, unsigned NumOps) { 5206 SDVTList VTs = getVTList(VT1, VT2, VT3); 5207 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 5208} 5209 5210MachineSDNode * 5211SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, EVT VT1, 5212 EVT VT2, EVT VT3, EVT VT4, 5213 const SDValue *Ops, unsigned NumOps) { 5214 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4); 5215 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 5216} 5217 5218MachineSDNode * 5219SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc dl, 5220 const std::vector<EVT> &ResultTys, 5221 const SDValue *Ops, unsigned NumOps) { 5222 SDVTList VTs = getVTList(&ResultTys[0], ResultTys.size()); 5223 return getMachineNode(Opcode, dl, VTs, Ops, NumOps); 5224} 5225 5226MachineSDNode * 5227SelectionDAG::getMachineNode(unsigned Opcode, DebugLoc DL, SDVTList VTs, 5228 const SDValue *Ops, unsigned NumOps) { 5229 bool DoCSE = VTs.VTs[VTs.NumVTs-1] != MVT::Glue; 5230 MachineSDNode *N; 5231 void *IP = 0; 5232 5233 if (DoCSE) { 5234 FoldingSetNodeID ID; 5235 AddNodeIDNode(ID, ~Opcode, VTs, Ops, NumOps); 5236 IP = 0; 5237 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) { 5238 return cast<MachineSDNode>(UpdadeDebugLocOnMergedSDNode(E, DL)); 5239 } 5240 } 5241 5242 // Allocate a new MachineSDNode. 5243 N = new (NodeAllocator) MachineSDNode(~Opcode, DL, VTs); 5244 5245 // Initialize the operands list. 5246 if (NumOps > array_lengthof(N->LocalOperands)) 5247 // We're creating a final node that will live unmorphed for the 5248 // remainder of the current SelectionDAG iteration, so we can allocate 5249 // the operands directly out of a pool with no recycling metadata. 5250 N->InitOperands(OperandAllocator.Allocate<SDUse>(NumOps), 5251 Ops, NumOps); 5252 else 5253 N->InitOperands(N->LocalOperands, Ops, NumOps); 5254 N->OperandsNeedDelete = false; 5255 5256 if (DoCSE) 5257 CSEMap.InsertNode(N, IP); 5258 5259 AllNodes.push_back(N); 5260#ifndef NDEBUG 5261 VerifyMachineNode(N); 5262#endif 5263 return N; 5264} 5265 5266/// getTargetExtractSubreg - A convenience function for creating 5267/// TargetOpcode::EXTRACT_SUBREG nodes. 5268SDValue 5269SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT, 5270 SDValue Operand) { 5271 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32); 5272 SDNode *Subreg = getMachineNode(TargetOpcode::EXTRACT_SUBREG, DL, 5273 VT, Operand, SRIdxVal); 5274 return SDValue(Subreg, 0); 5275} 5276 5277/// getTargetInsertSubreg - A convenience function for creating 5278/// TargetOpcode::INSERT_SUBREG nodes. 5279SDValue 5280SelectionDAG::getTargetInsertSubreg(int SRIdx, DebugLoc DL, EVT VT, 5281 SDValue Operand, SDValue Subreg) { 5282 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32); 5283 SDNode *Result = getMachineNode(TargetOpcode::INSERT_SUBREG, DL, 5284 VT, Operand, Subreg, SRIdxVal); 5285 return SDValue(Result, 0); 5286} 5287 5288/// getNodeIfExists - Get the specified node if it's already available, or 5289/// else return NULL. 5290SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList, 5291 const SDValue *Ops, unsigned NumOps) { 5292 if (VTList.VTs[VTList.NumVTs-1] != MVT::Glue) { 5293 FoldingSetNodeID ID; 5294 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 5295 void *IP = 0; 5296 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 5297 return E; 5298 } 5299 return NULL; 5300} 5301 5302/// getDbgValue - Creates a SDDbgValue node. 5303/// 5304SDDbgValue * 5305SelectionDAG::getDbgValue(MDNode *MDPtr, SDNode *N, unsigned R, uint64_t Off, 5306 DebugLoc DL, unsigned O) { 5307 return new (Allocator) SDDbgValue(MDPtr, N, R, Off, DL, O); 5308} 5309 5310SDDbgValue * 5311SelectionDAG::getDbgValue(MDNode *MDPtr, const Value *C, uint64_t Off, 5312 DebugLoc DL, unsigned O) { 5313 return new (Allocator) SDDbgValue(MDPtr, C, Off, DL, O); 5314} 5315 5316SDDbgValue * 5317SelectionDAG::getDbgValue(MDNode *MDPtr, unsigned FI, uint64_t Off, 5318 DebugLoc DL, unsigned O) { 5319 return new (Allocator) SDDbgValue(MDPtr, FI, Off, DL, O); 5320} 5321 5322namespace { 5323 5324/// RAUWUpdateListener - Helper for ReplaceAllUsesWith - When the node 5325/// pointed to by a use iterator is deleted, increment the use iterator 5326/// so that it doesn't dangle. 5327/// 5328class RAUWUpdateListener : public SelectionDAG::DAGUpdateListener { 5329 SDNode::use_iterator &UI; 5330 SDNode::use_iterator &UE; 5331 5332 virtual void NodeDeleted(SDNode *N, SDNode *E) { 5333 // Increment the iterator as needed. 5334 while (UI != UE && N == *UI) 5335 ++UI; 5336 } 5337 5338public: 5339 RAUWUpdateListener(SelectionDAG &d, 5340 SDNode::use_iterator &ui, 5341 SDNode::use_iterator &ue) 5342 : SelectionDAG::DAGUpdateListener(d), UI(ui), UE(ue) {} 5343}; 5344 5345} 5346 5347/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 5348/// This can cause recursive merging of nodes in the DAG. 5349/// 5350/// This version assumes From has a single result value. 5351/// 5352void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To) { 5353 SDNode *From = FromN.getNode(); 5354 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 && 5355 "Cannot replace with this method!"); 5356 assert(From != To.getNode() && "Cannot replace uses of with self"); 5357 5358 // Iterate over all the existing uses of From. New uses will be added 5359 // to the beginning of the use list, which we avoid visiting. 5360 // This specifically avoids visiting uses of From that arise while the 5361 // replacement is happening, because any such uses would be the result 5362 // of CSE: If an existing node looks like From after one of its operands 5363 // is replaced by To, we don't want to replace of all its users with To 5364 // too. See PR3018 for more info. 5365 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); 5366 RAUWUpdateListener Listener(*this, UI, UE); 5367 while (UI != UE) { 5368 SDNode *User = *UI; 5369 5370 // This node is about to morph, remove its old self from the CSE maps. 5371 RemoveNodeFromCSEMaps(User); 5372 5373 // A user can appear in a use list multiple times, and when this 5374 // happens the uses are usually next to each other in the list. 5375 // To help reduce the number of CSE recomputations, process all 5376 // the uses of this user that we can find this way. 5377 do { 5378 SDUse &Use = UI.getUse(); 5379 ++UI; 5380 Use.set(To); 5381 } while (UI != UE && *UI == User); 5382 5383 // Now that we have modified User, add it back to the CSE maps. If it 5384 // already exists there, recursively merge the results together. 5385 AddModifiedNodeToCSEMaps(User); 5386 } 5387 5388 // If we just RAUW'd the root, take note. 5389 if (FromN == getRoot()) 5390 setRoot(To); 5391} 5392 5393/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 5394/// This can cause recursive merging of nodes in the DAG. 5395/// 5396/// This version assumes that for each value of From, there is a 5397/// corresponding value in To in the same position with the same type. 5398/// 5399void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To) { 5400#ifndef NDEBUG 5401 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i) 5402 assert((!From->hasAnyUseOfValue(i) || 5403 From->getValueType(i) == To->getValueType(i)) && 5404 "Cannot use this version of ReplaceAllUsesWith!"); 5405#endif 5406 5407 // Handle the trivial case. 5408 if (From == To) 5409 return; 5410 5411 // Iterate over just the existing users of From. See the comments in 5412 // the ReplaceAllUsesWith above. 5413 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); 5414 RAUWUpdateListener Listener(*this, UI, UE); 5415 while (UI != UE) { 5416 SDNode *User = *UI; 5417 5418 // This node is about to morph, remove its old self from the CSE maps. 5419 RemoveNodeFromCSEMaps(User); 5420 5421 // A user can appear in a use list multiple times, and when this 5422 // happens the uses are usually next to each other in the list. 5423 // To help reduce the number of CSE recomputations, process all 5424 // the uses of this user that we can find this way. 5425 do { 5426 SDUse &Use = UI.getUse(); 5427 ++UI; 5428 Use.setNode(To); 5429 } while (UI != UE && *UI == User); 5430 5431 // Now that we have modified User, add it back to the CSE maps. If it 5432 // already exists there, recursively merge the results together. 5433 AddModifiedNodeToCSEMaps(User); 5434 } 5435 5436 // If we just RAUW'd the root, take note. 5437 if (From == getRoot().getNode()) 5438 setRoot(SDValue(To, getRoot().getResNo())); 5439} 5440 5441/// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 5442/// This can cause recursive merging of nodes in the DAG. 5443/// 5444/// This version can replace From with any result values. To must match the 5445/// number and types of values returned by From. 5446void SelectionDAG::ReplaceAllUsesWith(SDNode *From, const SDValue *To) { 5447 if (From->getNumValues() == 1) // Handle the simple case efficiently. 5448 return ReplaceAllUsesWith(SDValue(From, 0), To[0]); 5449 5450 // Iterate over just the existing users of From. See the comments in 5451 // the ReplaceAllUsesWith above. 5452 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); 5453 RAUWUpdateListener Listener(*this, UI, UE); 5454 while (UI != UE) { 5455 SDNode *User = *UI; 5456 5457 // This node is about to morph, remove its old self from the CSE maps. 5458 RemoveNodeFromCSEMaps(User); 5459 5460 // A user can appear in a use list multiple times, and when this 5461 // happens the uses are usually next to each other in the list. 5462 // To help reduce the number of CSE recomputations, process all 5463 // the uses of this user that we can find this way. 5464 do { 5465 SDUse &Use = UI.getUse(); 5466 const SDValue &ToOp = To[Use.getResNo()]; 5467 ++UI; 5468 Use.set(ToOp); 5469 } while (UI != UE && *UI == User); 5470 5471 // Now that we have modified User, add it back to the CSE maps. If it 5472 // already exists there, recursively merge the results together. 5473 AddModifiedNodeToCSEMaps(User); 5474 } 5475 5476 // If we just RAUW'd the root, take note. 5477 if (From == getRoot().getNode()) 5478 setRoot(SDValue(To[getRoot().getResNo()])); 5479} 5480 5481/// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 5482/// uses of other values produced by From.getNode() alone. The Deleted 5483/// vector is handled the same way as for ReplaceAllUsesWith. 5484void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To){ 5485 // Handle the really simple, really trivial case efficiently. 5486 if (From == To) return; 5487 5488 // Handle the simple, trivial, case efficiently. 5489 if (From.getNode()->getNumValues() == 1) { 5490 ReplaceAllUsesWith(From, To); 5491 return; 5492 } 5493 5494 // Iterate over just the existing users of From. See the comments in 5495 // the ReplaceAllUsesWith above. 5496 SDNode::use_iterator UI = From.getNode()->use_begin(), 5497 UE = From.getNode()->use_end(); 5498 RAUWUpdateListener Listener(*this, UI, UE); 5499 while (UI != UE) { 5500 SDNode *User = *UI; 5501 bool UserRemovedFromCSEMaps = false; 5502 5503 // A user can appear in a use list multiple times, and when this 5504 // happens the uses are usually next to each other in the list. 5505 // To help reduce the number of CSE recomputations, process all 5506 // the uses of this user that we can find this way. 5507 do { 5508 SDUse &Use = UI.getUse(); 5509 5510 // Skip uses of different values from the same node. 5511 if (Use.getResNo() != From.getResNo()) { 5512 ++UI; 5513 continue; 5514 } 5515 5516 // If this node hasn't been modified yet, it's still in the CSE maps, 5517 // so remove its old self from the CSE maps. 5518 if (!UserRemovedFromCSEMaps) { 5519 RemoveNodeFromCSEMaps(User); 5520 UserRemovedFromCSEMaps = true; 5521 } 5522 5523 ++UI; 5524 Use.set(To); 5525 } while (UI != UE && *UI == User); 5526 5527 // We are iterating over all uses of the From node, so if a use 5528 // doesn't use the specific value, no changes are made. 5529 if (!UserRemovedFromCSEMaps) 5530 continue; 5531 5532 // Now that we have modified User, add it back to the CSE maps. If it 5533 // already exists there, recursively merge the results together. 5534 AddModifiedNodeToCSEMaps(User); 5535 } 5536 5537 // If we just RAUW'd the root, take note. 5538 if (From == getRoot()) 5539 setRoot(To); 5540} 5541 5542namespace { 5543 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith 5544 /// to record information about a use. 5545 struct UseMemo { 5546 SDNode *User; 5547 unsigned Index; 5548 SDUse *Use; 5549 }; 5550 5551 /// operator< - Sort Memos by User. 5552 bool operator<(const UseMemo &L, const UseMemo &R) { 5553 return (intptr_t)L.User < (intptr_t)R.User; 5554 } 5555} 5556 5557/// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving 5558/// uses of other values produced by From.getNode() alone. The same value 5559/// may appear in both the From and To list. The Deleted vector is 5560/// handled the same way as for ReplaceAllUsesWith. 5561void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From, 5562 const SDValue *To, 5563 unsigned Num){ 5564 // Handle the simple, trivial case efficiently. 5565 if (Num == 1) 5566 return ReplaceAllUsesOfValueWith(*From, *To); 5567 5568 // Read up all the uses and make records of them. This helps 5569 // processing new uses that are introduced during the 5570 // replacement process. 5571 SmallVector<UseMemo, 4> Uses; 5572 for (unsigned i = 0; i != Num; ++i) { 5573 unsigned FromResNo = From[i].getResNo(); 5574 SDNode *FromNode = From[i].getNode(); 5575 for (SDNode::use_iterator UI = FromNode->use_begin(), 5576 E = FromNode->use_end(); UI != E; ++UI) { 5577 SDUse &Use = UI.getUse(); 5578 if (Use.getResNo() == FromResNo) { 5579 UseMemo Memo = { *UI, i, &Use }; 5580 Uses.push_back(Memo); 5581 } 5582 } 5583 } 5584 5585 // Sort the uses, so that all the uses from a given User are together. 5586 std::sort(Uses.begin(), Uses.end()); 5587 5588 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size(); 5589 UseIndex != UseIndexEnd; ) { 5590 // We know that this user uses some value of From. If it is the right 5591 // value, update it. 5592 SDNode *User = Uses[UseIndex].User; 5593 5594 // This node is about to morph, remove its old self from the CSE maps. 5595 RemoveNodeFromCSEMaps(User); 5596 5597 // The Uses array is sorted, so all the uses for a given User 5598 // are next to each other in the list. 5599 // To help reduce the number of CSE recomputations, process all 5600 // the uses of this user that we can find this way. 5601 do { 5602 unsigned i = Uses[UseIndex].Index; 5603 SDUse &Use = *Uses[UseIndex].Use; 5604 ++UseIndex; 5605 5606 Use.set(To[i]); 5607 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User); 5608 5609 // Now that we have modified User, add it back to the CSE maps. If it 5610 // already exists there, recursively merge the results together. 5611 AddModifiedNodeToCSEMaps(User); 5612 } 5613} 5614 5615/// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 5616/// based on their topological order. It returns the maximum id and a vector 5617/// of the SDNodes* in assigned order by reference. 5618unsigned SelectionDAG::AssignTopologicalOrder() { 5619 5620 unsigned DAGSize = 0; 5621 5622 // SortedPos tracks the progress of the algorithm. Nodes before it are 5623 // sorted, nodes after it are unsorted. When the algorithm completes 5624 // it is at the end of the list. 5625 allnodes_iterator SortedPos = allnodes_begin(); 5626 5627 // Visit all the nodes. Move nodes with no operands to the front of 5628 // the list immediately. Annotate nodes that do have operands with their 5629 // operand count. Before we do this, the Node Id fields of the nodes 5630 // may contain arbitrary values. After, the Node Id fields for nodes 5631 // before SortedPos will contain the topological sort index, and the 5632 // Node Id fields for nodes At SortedPos and after will contain the 5633 // count of outstanding operands. 5634 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) { 5635 SDNode *N = I++; 5636 checkForCycles(N); 5637 unsigned Degree = N->getNumOperands(); 5638 if (Degree == 0) { 5639 // A node with no uses, add it to the result array immediately. 5640 N->setNodeId(DAGSize++); 5641 allnodes_iterator Q = N; 5642 if (Q != SortedPos) 5643 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q)); 5644 assert(SortedPos != AllNodes.end() && "Overran node list"); 5645 ++SortedPos; 5646 } else { 5647 // Temporarily use the Node Id as scratch space for the degree count. 5648 N->setNodeId(Degree); 5649 } 5650 } 5651 5652 // Visit all the nodes. As we iterate, move nodes into sorted order, 5653 // such that by the time the end is reached all nodes will be sorted. 5654 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) { 5655 SDNode *N = I; 5656 checkForCycles(N); 5657 // N is in sorted position, so all its uses have one less operand 5658 // that needs to be sorted. 5659 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 5660 UI != UE; ++UI) { 5661 SDNode *P = *UI; 5662 unsigned Degree = P->getNodeId(); 5663 assert(Degree != 0 && "Invalid node degree"); 5664 --Degree; 5665 if (Degree == 0) { 5666 // All of P's operands are sorted, so P may sorted now. 5667 P->setNodeId(DAGSize++); 5668 if (P != SortedPos) 5669 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P)); 5670 assert(SortedPos != AllNodes.end() && "Overran node list"); 5671 ++SortedPos; 5672 } else { 5673 // Update P's outstanding operand count. 5674 P->setNodeId(Degree); 5675 } 5676 } 5677 if (I == SortedPos) { 5678#ifndef NDEBUG 5679 SDNode *S = ++I; 5680 dbgs() << "Overran sorted position:\n"; 5681 S->dumprFull(); 5682#endif 5683 llvm_unreachable(0); 5684 } 5685 } 5686 5687 assert(SortedPos == AllNodes.end() && 5688 "Topological sort incomplete!"); 5689 assert(AllNodes.front().getOpcode() == ISD::EntryToken && 5690 "First node in topological sort is not the entry token!"); 5691 assert(AllNodes.front().getNodeId() == 0 && 5692 "First node in topological sort has non-zero id!"); 5693 assert(AllNodes.front().getNumOperands() == 0 && 5694 "First node in topological sort has operands!"); 5695 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 && 5696 "Last node in topologic sort has unexpected id!"); 5697 assert(AllNodes.back().use_empty() && 5698 "Last node in topologic sort has users!"); 5699 assert(DAGSize == allnodes_size() && "Node count mismatch!"); 5700 return DAGSize; 5701} 5702 5703/// AssignOrdering - Assign an order to the SDNode. 5704void SelectionDAG::AssignOrdering(const SDNode *SD, unsigned Order) { 5705 assert(SD && "Trying to assign an order to a null node!"); 5706 Ordering->add(SD, Order); 5707} 5708 5709/// GetOrdering - Get the order for the SDNode. 5710unsigned SelectionDAG::GetOrdering(const SDNode *SD) const { 5711 assert(SD && "Trying to get the order of a null node!"); 5712 return Ordering->getOrder(SD); 5713} 5714 5715/// AddDbgValue - Add a dbg_value SDNode. If SD is non-null that means the 5716/// value is produced by SD. 5717void SelectionDAG::AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter) { 5718 DbgInfo->add(DB, SD, isParameter); 5719 if (SD) 5720 SD->setHasDebugValue(true); 5721} 5722 5723/// TransferDbgValues - Transfer SDDbgValues. 5724void SelectionDAG::TransferDbgValues(SDValue From, SDValue To) { 5725 if (From == To || !From.getNode()->getHasDebugValue()) 5726 return; 5727 SDNode *FromNode = From.getNode(); 5728 SDNode *ToNode = To.getNode(); 5729 ArrayRef<SDDbgValue *> DVs = GetDbgValues(FromNode); 5730 SmallVector<SDDbgValue *, 2> ClonedDVs; 5731 for (ArrayRef<SDDbgValue *>::iterator I = DVs.begin(), E = DVs.end(); 5732 I != E; ++I) { 5733 SDDbgValue *Dbg = *I; 5734 if (Dbg->getKind() == SDDbgValue::SDNODE) { 5735 SDDbgValue *Clone = getDbgValue(Dbg->getMDPtr(), ToNode, To.getResNo(), 5736 Dbg->getOffset(), Dbg->getDebugLoc(), 5737 Dbg->getOrder()); 5738 ClonedDVs.push_back(Clone); 5739 } 5740 } 5741 for (SmallVector<SDDbgValue *, 2>::iterator I = ClonedDVs.begin(), 5742 E = ClonedDVs.end(); I != E; ++I) 5743 AddDbgValue(*I, ToNode, false); 5744} 5745 5746//===----------------------------------------------------------------------===// 5747// SDNode Class 5748//===----------------------------------------------------------------------===// 5749 5750HandleSDNode::~HandleSDNode() { 5751 DropOperands(); 5752} 5753 5754GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, DebugLoc DL, 5755 const GlobalValue *GA, 5756 EVT VT, int64_t o, unsigned char TF) 5757 : SDNode(Opc, DL, getSDVTList(VT)), Offset(o), TargetFlags(TF) { 5758 TheGlobal = GA; 5759} 5760 5761MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt, 5762 MachineMemOperand *mmo) 5763 : SDNode(Opc, dl, VTs), MemoryVT(memvt), MMO(mmo) { 5764 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(), 5765 MMO->isNonTemporal(), MMO->isInvariant()); 5766 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!"); 5767 assert(isNonTemporal() == MMO->isNonTemporal() && 5768 "Non-temporal encoding error!"); 5769 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!"); 5770} 5771 5772MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, 5773 const SDValue *Ops, unsigned NumOps, EVT memvt, 5774 MachineMemOperand *mmo) 5775 : SDNode(Opc, dl, VTs, Ops, NumOps), 5776 MemoryVT(memvt), MMO(mmo) { 5777 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, MMO->isVolatile(), 5778 MMO->isNonTemporal(), MMO->isInvariant()); 5779 assert(isVolatile() == MMO->isVolatile() && "Volatile encoding error!"); 5780 assert(memvt.getStoreSize() == MMO->getSize() && "Size mismatch!"); 5781} 5782 5783/// Profile - Gather unique data for the node. 5784/// 5785void SDNode::Profile(FoldingSetNodeID &ID) const { 5786 AddNodeIDNode(ID, this); 5787} 5788 5789namespace { 5790 struct EVTArray { 5791 std::vector<EVT> VTs; 5792 5793 EVTArray() { 5794 VTs.reserve(MVT::LAST_VALUETYPE); 5795 for (unsigned i = 0; i < MVT::LAST_VALUETYPE; ++i) 5796 VTs.push_back(MVT((MVT::SimpleValueType)i)); 5797 } 5798 }; 5799} 5800 5801static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs; 5802static ManagedStatic<EVTArray> SimpleVTArray; 5803static ManagedStatic<sys::SmartMutex<true> > VTMutex; 5804 5805/// getValueTypeList - Return a pointer to the specified value type. 5806/// 5807const EVT *SDNode::getValueTypeList(EVT VT) { 5808 if (VT.isExtended()) { 5809 sys::SmartScopedLock<true> Lock(*VTMutex); 5810 return &(*EVTs->insert(VT).first); 5811 } else { 5812 assert(VT.getSimpleVT() < MVT::LAST_VALUETYPE && 5813 "Value type out of range!"); 5814 return &SimpleVTArray->VTs[VT.getSimpleVT().SimpleTy]; 5815 } 5816} 5817 5818/// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 5819/// indicated value. This method ignores uses of other values defined by this 5820/// operation. 5821bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { 5822 assert(Value < getNumValues() && "Bad value!"); 5823 5824 // TODO: Only iterate over uses of a given value of the node 5825 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { 5826 if (UI.getUse().getResNo() == Value) { 5827 if (NUses == 0) 5828 return false; 5829 --NUses; 5830 } 5831 } 5832 5833 // Found exactly the right number of uses? 5834 return NUses == 0; 5835} 5836 5837 5838/// hasAnyUseOfValue - Return true if there are any use of the indicated 5839/// value. This method ignores uses of other values defined by this operation. 5840bool SDNode::hasAnyUseOfValue(unsigned Value) const { 5841 assert(Value < getNumValues() && "Bad value!"); 5842 5843 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) 5844 if (UI.getUse().getResNo() == Value) 5845 return true; 5846 5847 return false; 5848} 5849 5850 5851/// isOnlyUserOf - Return true if this node is the only use of N. 5852/// 5853bool SDNode::isOnlyUserOf(SDNode *N) const { 5854 bool Seen = false; 5855 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 5856 SDNode *User = *I; 5857 if (User == this) 5858 Seen = true; 5859 else 5860 return false; 5861 } 5862 5863 return Seen; 5864} 5865 5866/// isOperand - Return true if this node is an operand of N. 5867/// 5868bool SDValue::isOperandOf(SDNode *N) const { 5869 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 5870 if (*this == N->getOperand(i)) 5871 return true; 5872 return false; 5873} 5874 5875bool SDNode::isOperandOf(SDNode *N) const { 5876 for (unsigned i = 0, e = N->NumOperands; i != e; ++i) 5877 if (this == N->OperandList[i].getNode()) 5878 return true; 5879 return false; 5880} 5881 5882/// reachesChainWithoutSideEffects - Return true if this operand (which must 5883/// be a chain) reaches the specified operand without crossing any 5884/// side-effecting instructions on any chain path. In practice, this looks 5885/// through token factors and non-volatile loads. In order to remain efficient, 5886/// this only looks a couple of nodes in, it does not do an exhaustive search. 5887bool SDValue::reachesChainWithoutSideEffects(SDValue Dest, 5888 unsigned Depth) const { 5889 if (*this == Dest) return true; 5890 5891 // Don't search too deeply, we just want to be able to see through 5892 // TokenFactor's etc. 5893 if (Depth == 0) return false; 5894 5895 // If this is a token factor, all inputs to the TF happen in parallel. If any 5896 // of the operands of the TF does not reach dest, then we cannot do the xform. 5897 if (getOpcode() == ISD::TokenFactor) { 5898 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 5899 if (!getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1)) 5900 return false; 5901 return true; 5902 } 5903 5904 // Loads don't have side effects, look through them. 5905 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) { 5906 if (!Ld->isVolatile()) 5907 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1); 5908 } 5909 return false; 5910} 5911 5912/// hasPredecessor - Return true if N is a predecessor of this node. 5913/// N is either an operand of this node, or can be reached by recursively 5914/// traversing up the operands. 5915/// NOTE: This is an expensive method. Use it carefully. 5916bool SDNode::hasPredecessor(const SDNode *N) const { 5917 SmallPtrSet<const SDNode *, 32> Visited; 5918 SmallVector<const SDNode *, 16> Worklist; 5919 return hasPredecessorHelper(N, Visited, Worklist); 5920} 5921 5922bool SDNode::hasPredecessorHelper(const SDNode *N, 5923 SmallPtrSet<const SDNode *, 32> &Visited, 5924 SmallVector<const SDNode *, 16> &Worklist) const { 5925 if (Visited.empty()) { 5926 Worklist.push_back(this); 5927 } else { 5928 // Take a look in the visited set. If we've already encountered this node 5929 // we needn't search further. 5930 if (Visited.count(N)) 5931 return true; 5932 } 5933 5934 // Haven't visited N yet. Continue the search. 5935 while (!Worklist.empty()) { 5936 const SDNode *M = Worklist.pop_back_val(); 5937 for (unsigned i = 0, e = M->getNumOperands(); i != e; ++i) { 5938 SDNode *Op = M->getOperand(i).getNode(); 5939 if (Visited.insert(Op)) 5940 Worklist.push_back(Op); 5941 if (Op == N) 5942 return true; 5943 } 5944 } 5945 5946 return false; 5947} 5948 5949uint64_t SDNode::getConstantOperandVal(unsigned Num) const { 5950 assert(Num < NumOperands && "Invalid child # of SDNode!"); 5951 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue(); 5952} 5953 5954SDValue SelectionDAG::UnrollVectorOp(SDNode *N, unsigned ResNE) { 5955 assert(N->getNumValues() == 1 && 5956 "Can't unroll a vector with multiple results!"); 5957 5958 EVT VT = N->getValueType(0); 5959 unsigned NE = VT.getVectorNumElements(); 5960 EVT EltVT = VT.getVectorElementType(); 5961 DebugLoc dl = N->getDebugLoc(); 5962 5963 SmallVector<SDValue, 8> Scalars; 5964 SmallVector<SDValue, 4> Operands(N->getNumOperands()); 5965 5966 // If ResNE is 0, fully unroll the vector op. 5967 if (ResNE == 0) 5968 ResNE = NE; 5969 else if (NE > ResNE) 5970 NE = ResNE; 5971 5972 unsigned i; 5973 for (i= 0; i != NE; ++i) { 5974 for (unsigned j = 0, e = N->getNumOperands(); j != e; ++j) { 5975 SDValue Operand = N->getOperand(j); 5976 EVT OperandVT = Operand.getValueType(); 5977 if (OperandVT.isVector()) { 5978 // A vector operand; extract a single element. 5979 EVT OperandEltVT = OperandVT.getVectorElementType(); 5980 Operands[j] = getNode(ISD::EXTRACT_VECTOR_ELT, dl, 5981 OperandEltVT, 5982 Operand, 5983 getConstant(i, TLI.getPointerTy())); 5984 } else { 5985 // A scalar operand; just use it as is. 5986 Operands[j] = Operand; 5987 } 5988 } 5989 5990 switch (N->getOpcode()) { 5991 default: 5992 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, 5993 &Operands[0], Operands.size())); 5994 break; 5995 case ISD::VSELECT: 5996 Scalars.push_back(getNode(ISD::SELECT, dl, EltVT, 5997 &Operands[0], Operands.size())); 5998 break; 5999 case ISD::SHL: 6000 case ISD::SRA: 6001 case ISD::SRL: 6002 case ISD::ROTL: 6003 case ISD::ROTR: 6004 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, Operands[0], 6005 getShiftAmountOperand(Operands[0].getValueType(), 6006 Operands[1]))); 6007 break; 6008 case ISD::SIGN_EXTEND_INREG: 6009 case ISD::FP_ROUND_INREG: { 6010 EVT ExtVT = cast<VTSDNode>(Operands[1])->getVT().getVectorElementType(); 6011 Scalars.push_back(getNode(N->getOpcode(), dl, EltVT, 6012 Operands[0], 6013 getValueType(ExtVT))); 6014 } 6015 } 6016 } 6017 6018 for (; i < ResNE; ++i) 6019 Scalars.push_back(getUNDEF(EltVT)); 6020 6021 return getNode(ISD::BUILD_VECTOR, dl, 6022 EVT::getVectorVT(*getContext(), EltVT, ResNE), 6023 &Scalars[0], Scalars.size()); 6024} 6025 6026 6027/// isConsecutiveLoad - Return true if LD is loading 'Bytes' bytes from a 6028/// location that is 'Dist' units away from the location that the 'Base' load 6029/// is loading from. 6030bool SelectionDAG::isConsecutiveLoad(LoadSDNode *LD, LoadSDNode *Base, 6031 unsigned Bytes, int Dist) const { 6032 if (LD->getChain() != Base->getChain()) 6033 return false; 6034 EVT VT = LD->getValueType(0); 6035 if (VT.getSizeInBits() / 8 != Bytes) 6036 return false; 6037 6038 SDValue Loc = LD->getOperand(1); 6039 SDValue BaseLoc = Base->getOperand(1); 6040 if (Loc.getOpcode() == ISD::FrameIndex) { 6041 if (BaseLoc.getOpcode() != ISD::FrameIndex) 6042 return false; 6043 const MachineFrameInfo *MFI = getMachineFunction().getFrameInfo(); 6044 int FI = cast<FrameIndexSDNode>(Loc)->getIndex(); 6045 int BFI = cast<FrameIndexSDNode>(BaseLoc)->getIndex(); 6046 int FS = MFI->getObjectSize(FI); 6047 int BFS = MFI->getObjectSize(BFI); 6048 if (FS != BFS || FS != (int)Bytes) return false; 6049 return MFI->getObjectOffset(FI) == (MFI->getObjectOffset(BFI) + Dist*Bytes); 6050 } 6051 6052 // Handle X+C 6053 if (isBaseWithConstantOffset(Loc) && Loc.getOperand(0) == BaseLoc && 6054 cast<ConstantSDNode>(Loc.getOperand(1))->getSExtValue() == Dist*Bytes) 6055 return true; 6056 6057 const GlobalValue *GV1 = NULL; 6058 const GlobalValue *GV2 = NULL; 6059 int64_t Offset1 = 0; 6060 int64_t Offset2 = 0; 6061 bool isGA1 = TLI.isGAPlusOffset(Loc.getNode(), GV1, Offset1); 6062 bool isGA2 = TLI.isGAPlusOffset(BaseLoc.getNode(), GV2, Offset2); 6063 if (isGA1 && isGA2 && GV1 == GV2) 6064 return Offset1 == (Offset2 + Dist*Bytes); 6065 return false; 6066} 6067 6068 6069/// InferPtrAlignment - Infer alignment of a load / store address. Return 0 if 6070/// it cannot be inferred. 6071unsigned SelectionDAG::InferPtrAlignment(SDValue Ptr) const { 6072 // If this is a GlobalAddress + cst, return the alignment. 6073 const GlobalValue *GV; 6074 int64_t GVOffset = 0; 6075 if (TLI.isGAPlusOffset(Ptr.getNode(), GV, GVOffset)) { 6076 unsigned PtrWidth = TLI.getPointerTy().getSizeInBits(); 6077 APInt KnownZero(PtrWidth, 0), KnownOne(PtrWidth, 0); 6078 llvm::ComputeMaskedBits(const_cast<GlobalValue*>(GV), KnownZero, KnownOne, 6079 TLI.getTargetData()); 6080 unsigned AlignBits = KnownZero.countTrailingOnes(); 6081 unsigned Align = AlignBits ? 1 << std::min(31U, AlignBits) : 0; 6082 if (Align) 6083 return MinAlign(Align, GVOffset); 6084 } 6085 6086 // If this is a direct reference to a stack slot, use information about the 6087 // stack slot's alignment. 6088 int FrameIdx = 1 << 31; 6089 int64_t FrameOffset = 0; 6090 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Ptr)) { 6091 FrameIdx = FI->getIndex(); 6092 } else if (isBaseWithConstantOffset(Ptr) && 6093 isa<FrameIndexSDNode>(Ptr.getOperand(0))) { 6094 // Handle FI+Cst 6095 FrameIdx = cast<FrameIndexSDNode>(Ptr.getOperand(0))->getIndex(); 6096 FrameOffset = Ptr.getConstantOperandVal(1); 6097 } 6098 6099 if (FrameIdx != (1 << 31)) { 6100 const MachineFrameInfo &MFI = *getMachineFunction().getFrameInfo(); 6101 unsigned FIInfoAlign = MinAlign(MFI.getObjectAlignment(FrameIdx), 6102 FrameOffset); 6103 return FIInfoAlign; 6104 } 6105 6106 return 0; 6107} 6108 6109// getAddressSpace - Return the address space this GlobalAddress belongs to. 6110unsigned GlobalAddressSDNode::getAddressSpace() const { 6111 return getGlobal()->getType()->getAddressSpace(); 6112} 6113 6114 6115Type *ConstantPoolSDNode::getType() const { 6116 if (isMachineConstantPoolEntry()) 6117 return Val.MachineCPVal->getType(); 6118 return Val.ConstVal->getType(); 6119} 6120 6121bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue, 6122 APInt &SplatUndef, 6123 unsigned &SplatBitSize, 6124 bool &HasAnyUndefs, 6125 unsigned MinSplatBits, 6126 bool isBigEndian) { 6127 EVT VT = getValueType(0); 6128 assert(VT.isVector() && "Expected a vector type"); 6129 unsigned sz = VT.getSizeInBits(); 6130 if (MinSplatBits > sz) 6131 return false; 6132 6133 SplatValue = APInt(sz, 0); 6134 SplatUndef = APInt(sz, 0); 6135 6136 // Get the bits. Bits with undefined values (when the corresponding element 6137 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared 6138 // in SplatValue. If any of the values are not constant, give up and return 6139 // false. 6140 unsigned int nOps = getNumOperands(); 6141 assert(nOps > 0 && "isConstantSplat has 0-size build vector"); 6142 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits(); 6143 6144 for (unsigned j = 0; j < nOps; ++j) { 6145 unsigned i = isBigEndian ? nOps-1-j : j; 6146 SDValue OpVal = getOperand(i); 6147 unsigned BitPos = j * EltBitSize; 6148 6149 if (OpVal.getOpcode() == ISD::UNDEF) 6150 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos + EltBitSize); 6151 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal)) 6152 SplatValue |= CN->getAPIntValue().zextOrTrunc(EltBitSize). 6153 zextOrTrunc(sz) << BitPos; 6154 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal)) 6155 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos; 6156 else 6157 return false; 6158 } 6159 6160 // The build_vector is all constants or undefs. Find the smallest element 6161 // size that splats the vector. 6162 6163 HasAnyUndefs = (SplatUndef != 0); 6164 while (sz > 8) { 6165 6166 unsigned HalfSize = sz / 2; 6167 APInt HighValue = SplatValue.lshr(HalfSize).trunc(HalfSize); 6168 APInt LowValue = SplatValue.trunc(HalfSize); 6169 APInt HighUndef = SplatUndef.lshr(HalfSize).trunc(HalfSize); 6170 APInt LowUndef = SplatUndef.trunc(HalfSize); 6171 6172 // If the two halves do not match (ignoring undef bits), stop here. 6173 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) || 6174 MinSplatBits > HalfSize) 6175 break; 6176 6177 SplatValue = HighValue | LowValue; 6178 SplatUndef = HighUndef & LowUndef; 6179 6180 sz = HalfSize; 6181 } 6182 6183 SplatBitSize = sz; 6184 return true; 6185} 6186 6187bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) { 6188 // Find the first non-undef value in the shuffle mask. 6189 unsigned i, e; 6190 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i) 6191 /* search */; 6192 6193 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!"); 6194 6195 // Make sure all remaining elements are either undef or the same as the first 6196 // non-undef value. 6197 for (int Idx = Mask[i]; i != e; ++i) 6198 if (Mask[i] >= 0 && Mask[i] != Idx) 6199 return false; 6200 return true; 6201} 6202 6203#ifdef XDEBUG 6204static void checkForCyclesHelper(const SDNode *N, 6205 SmallPtrSet<const SDNode*, 32> &Visited, 6206 SmallPtrSet<const SDNode*, 32> &Checked) { 6207 // If this node has already been checked, don't check it again. 6208 if (Checked.count(N)) 6209 return; 6210 6211 // If a node has already been visited on this depth-first walk, reject it as 6212 // a cycle. 6213 if (!Visited.insert(N)) { 6214 dbgs() << "Offending node:\n"; 6215 N->dumprFull(); 6216 errs() << "Detected cycle in SelectionDAG\n"; 6217 abort(); 6218 } 6219 6220 for(unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 6221 checkForCyclesHelper(N->getOperand(i).getNode(), Visited, Checked); 6222 6223 Checked.insert(N); 6224 Visited.erase(N); 6225} 6226#endif 6227 6228void llvm::checkForCycles(const llvm::SDNode *N) { 6229#ifdef XDEBUG 6230 assert(N && "Checking nonexistant SDNode"); 6231 SmallPtrSet<const SDNode*, 32> visited; 6232 SmallPtrSet<const SDNode*, 32> checked; 6233 checkForCyclesHelper(N, visited, checked); 6234#endif 6235} 6236 6237void llvm::checkForCycles(const llvm::SelectionDAG *DAG) { 6238 checkForCycles(DAG->getRoot().getNode()); 6239} 6240