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