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