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