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