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