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