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