1 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This implements the SelectionDAG class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/SelectionDAG.h" 15 #include "SDNodeDbgValue.h" 16 #include "llvm/ADT/SetVector.h" 17 #include "llvm/ADT/SmallPtrSet.h" 18 #include "llvm/ADT/SmallSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/StringExtras.h" 21 #include "llvm/Analysis/ValueTracking.h" 22 #include "llvm/CodeGen/MachineBasicBlock.h" 23 #include "llvm/CodeGen/MachineConstantPool.h" 24 #include "llvm/CodeGen/MachineFrameInfo.h" 25 #include "llvm/CodeGen/MachineModuleInfo.h" 26 #include "llvm/IR/CallingConv.h" 27 #include "llvm/IR/Constants.h" 28 #include "llvm/IR/DataLayout.h" 29 #include "llvm/IR/DebugInfo.h" 30 #include "llvm/IR/DerivedTypes.h" 31 #include "llvm/IR/Function.h" 32 #include "llvm/IR/GlobalAlias.h" 33 #include "llvm/IR/GlobalVariable.h" 34 #include "llvm/IR/Intrinsics.h" 35 #include "llvm/Support/CommandLine.h" 36 #include "llvm/Support/Debug.h" 37 #include "llvm/Support/ErrorHandling.h" 38 #include "llvm/Support/ManagedStatic.h" 39 #include "llvm/Support/MathExtras.h" 40 #include "llvm/Support/Mutex.h" 41 #include "llvm/Support/raw_ostream.h" 42 #include "llvm/Target/TargetInstrInfo.h" 43 #include "llvm/Target/TargetIntrinsicInfo.h" 44 #include "llvm/Target/TargetLowering.h" 45 #include "llvm/Target/TargetMachine.h" 46 #include "llvm/Target/TargetOptions.h" 47 #include "llvm/Target/TargetRegisterInfo.h" 48 #include "llvm/Target/TargetSelectionDAGInfo.h" 49 #include <algorithm> 50 #include <cmath> 51 52 using namespace llvm; 53 54 /// makeVTList - Return an instance of the SDVTList struct initialized with the 55 /// specified members. 56 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) { 57 SDVTList Res = {VTs, NumVTs}; 58 return Res; 59 } 60 61 // Default null implementations of the callbacks. 62 void SelectionDAG::DAGUpdateListener::NodeDeleted(SDNode*, SDNode*) {} 63 void SelectionDAG::DAGUpdateListener::NodeUpdated(SDNode*) {} 64 65 //===----------------------------------------------------------------------===// 66 // ConstantFPSDNode Class 67 //===----------------------------------------------------------------------===// 68 69 /// isExactlyValue - We don't rely on operator== working on double values, as 70 /// it returns true for things that are clearly not equal, like -0.0 and 0.0. 71 /// As such, this method can be used to do an exact bit-for-bit comparison of 72 /// two floating point values. 73 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const { 74 return getValueAPF().bitwiseIsEqual(V); 75 } 76 77 bool ConstantFPSDNode::isValueValidForType(EVT VT, 78 const APFloat& Val) { 79 assert(VT.isFloatingPoint() && "Can only convert between FP types"); 80 81 // convert modifies in place, so make a copy. 82 APFloat Val2 = APFloat(Val); 83 bool losesInfo; 84 (void) Val2.convert(SelectionDAG::EVTToAPFloatSemantics(VT), 85 APFloat::rmNearestTiesToEven, 86 &losesInfo); 87 return !losesInfo; 88 } 89 90 //===----------------------------------------------------------------------===// 91 // ISD Namespace 92 //===----------------------------------------------------------------------===// 93 94 /// isBuildVectorAllOnes - Return true if the specified node is a 95 /// BUILD_VECTOR where all of the elements are ~0 or undef. 96 bool ISD::isBuildVectorAllOnes(const SDNode *N) { 97 // Look through a bit convert. 98 if (N->getOpcode() == ISD::BITCAST) 99 N = N->getOperand(0).getNode(); 100 101 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 102 103 unsigned i = 0, e = N->getNumOperands(); 104 105 // Skip over all of the undef values. 106 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 107 ++i; 108 109 // Do not accept an all-undef vector. 110 if (i == e) return false; 111 112 // Do not accept build_vectors that aren't all constants or which have non-~0 113 // elements. We have to be a bit careful here, as the type of the constant 114 // may not be the same as the type of the vector elements due to type 115 // legalization (the elements are promoted to a legal type for the target and 116 // a vector of a type may be legal when the base element type is not). 117 // We only want to check enough bits to cover the vector elements, because 118 // we care if the resultant vector is all ones, not whether the individual 119 // constants are. 120 SDValue NotZero = N->getOperand(i); 121 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits(); 122 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(NotZero)) { 123 if (CN->getAPIntValue().countTrailingOnes() < EltSize) 124 return false; 125 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(NotZero)) { 126 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingOnes() < EltSize) 127 return false; 128 } else 129 return false; 130 131 // Okay, we have at least one ~0 value, check to see if the rest match or are 132 // undefs. Even with the above element type twiddling, this should be OK, as 133 // the same type legalization should have applied to all the elements. 134 for (++i; i != e; ++i) 135 if (N->getOperand(i) != NotZero && 136 N->getOperand(i).getOpcode() != ISD::UNDEF) 137 return false; 138 return true; 139 } 140 141 142 /// isBuildVectorAllZeros - Return true if the specified node is a 143 /// BUILD_VECTOR where all of the elements are 0 or undef. 144 bool ISD::isBuildVectorAllZeros(const SDNode *N) { 145 // Look through a bit convert. 146 if (N->getOpcode() == ISD::BITCAST) 147 N = N->getOperand(0).getNode(); 148 149 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 150 151 bool IsAllUndef = true; 152 for (unsigned i = 0, e = N->getNumOperands(); i < e; ++i) { 153 if (N->getOperand(i).getOpcode() == ISD::UNDEF) 154 continue; 155 IsAllUndef = false; 156 // Do not accept build_vectors that aren't all constants or which have non-0 157 // elements. We have to be a bit careful here, as the type of the constant 158 // may not be the same as the type of the vector elements due to type 159 // legalization (the elements are promoted to a legal type for the target 160 // and a vector of a type may be legal when the base element type is not). 161 // We only want to check enough bits to cover the vector elements, because 162 // we care if the resultant vector is all zeros, not whether the individual 163 // constants are. 164 SDValue Zero = N->getOperand(i); 165 unsigned EltSize = N->getValueType(0).getVectorElementType().getSizeInBits(); 166 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Zero)) { 167 if (CN->getAPIntValue().countTrailingZeros() < EltSize) 168 return false; 169 } else if (ConstantFPSDNode *CFPN = dyn_cast<ConstantFPSDNode>(Zero)) { 170 if (CFPN->getValueAPF().bitcastToAPInt().countTrailingZeros() < EltSize) 171 return false; 172 } else 173 return false; 174 } 175 176 // Do not accept an all-undef vector. 177 if (IsAllUndef) 178 return false; 179 return true; 180 } 181 182 /// \brief Return true if the specified node is a BUILD_VECTOR node of 183 /// all ConstantSDNode or undef. 184 bool ISD::isBuildVectorOfConstantSDNodes(const SDNode *N) { 185 if (N->getOpcode() != ISD::BUILD_VECTOR) 186 return false; 187 188 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 189 SDValue Op = N->getOperand(i); 190 if (Op.getOpcode() == ISD::UNDEF) 191 continue; 192 if (!isa<ConstantSDNode>(Op)) 193 return false; 194 } 195 return true; 196 } 197 198 /// isScalarToVector - Return true if the specified node is a 199 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low 200 /// element is not an undef. 201 bool ISD::isScalarToVector(const SDNode *N) { 202 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR) 203 return true; 204 205 if (N->getOpcode() != ISD::BUILD_VECTOR) 206 return false; 207 if (N->getOperand(0).getOpcode() == ISD::UNDEF) 208 return false; 209 unsigned NumElems = N->getNumOperands(); 210 if (NumElems == 1) 211 return false; 212 for (unsigned i = 1; i < NumElems; ++i) { 213 SDValue V = N->getOperand(i); 214 if (V.getOpcode() != ISD::UNDEF) 215 return false; 216 } 217 return true; 218 } 219 220 /// allOperandsUndef - Return true if the node has at least one operand 221 /// and all operands of the specified node are ISD::UNDEF. 222 bool ISD::allOperandsUndef(const SDNode *N) { 223 // Return false if the node has no operands. 224 // This is "logically inconsistent" with the definition of "all" but 225 // is probably the desired behavior. 226 if (N->getNumOperands() == 0) 227 return false; 228 229 for (unsigned i = 0, e = N->getNumOperands(); i != e ; ++i) 230 if (N->getOperand(i).getOpcode() != ISD::UNDEF) 231 return false; 232 233 return true; 234 } 235 236 ISD::NodeType ISD::getExtForLoadExtType(ISD::LoadExtType ExtType) { 237 switch (ExtType) { 238 case ISD::EXTLOAD: 239 return ISD::ANY_EXTEND; 240 case ISD::SEXTLOAD: 241 return ISD::SIGN_EXTEND; 242 case ISD::ZEXTLOAD: 243 return ISD::ZERO_EXTEND; 244 default: 245 break; 246 } 247 248 llvm_unreachable("Invalid LoadExtType"); 249 } 250 251 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 252 /// when given the operation for (X op Y). 253 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 254 // To perform this operation, we just need to swap the L and G bits of the 255 // operation. 256 unsigned OldL = (Operation >> 2) & 1; 257 unsigned OldG = (Operation >> 1) & 1; 258 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 259 (OldL << 1) | // New G bit 260 (OldG << 2)); // New L bit. 261 } 262 263 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where 264 /// 'op' is a valid SetCC operation. 265 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 266 unsigned Operation = Op; 267 if (isInteger) 268 Operation ^= 7; // Flip L, G, E bits, but not U. 269 else 270 Operation ^= 15; // Flip all of the condition bits. 271 272 if (Operation > ISD::SETTRUE2) 273 Operation &= ~8; // Don't let N and U bits get set. 274 275 return ISD::CondCode(Operation); 276 } 277 278 279 /// isSignedOp - For an integer comparison, return 1 if the comparison is a 280 /// signed operation and 2 if the result is an unsigned comparison. Return zero 281 /// if the operation does not depend on the sign of the input (setne and seteq). 282 static int isSignedOp(ISD::CondCode Opcode) { 283 switch (Opcode) { 284 default: llvm_unreachable("Illegal integer setcc operation!"); 285 case ISD::SETEQ: 286 case ISD::SETNE: return 0; 287 case ISD::SETLT: 288 case ISD::SETLE: 289 case ISD::SETGT: 290 case ISD::SETGE: return 1; 291 case ISD::SETULT: 292 case ISD::SETULE: 293 case ISD::SETUGT: 294 case ISD::SETUGE: return 2; 295 } 296 } 297 298 /// getSetCCOrOperation - Return the result of a logical OR between different 299 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 300 /// returns SETCC_INVALID if it is not possible to represent the resultant 301 /// comparison. 302 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 303 bool isInteger) { 304 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 305 // Cannot fold a signed integer setcc with an unsigned integer setcc. 306 return ISD::SETCC_INVALID; 307 308 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 309 310 // If the N and U bits get set then the resultant comparison DOES suddenly 311 // care about orderedness, and is true when ordered. 312 if (Op > ISD::SETTRUE2) 313 Op &= ~16; // Clear the U bit if the N bit is set. 314 315 // Canonicalize illegal integer setcc's. 316 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT 317 Op = ISD::SETNE; 318 319 return ISD::CondCode(Op); 320 } 321 322 /// getSetCCAndOperation - Return the result of a logical AND between different 323 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 324 /// function returns zero if it is not possible to represent the resultant 325 /// comparison. 326 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 327 bool isInteger) { 328 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 329 // Cannot fold a signed setcc with an unsigned setcc. 330 return ISD::SETCC_INVALID; 331 332 // Combine all of the condition bits. 333 ISD::CondCode Result = ISD::CondCode(Op1 & Op2); 334 335 // Canonicalize illegal integer setcc's. 336 if (isInteger) { 337 switch (Result) { 338 default: break; 339 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT 340 case ISD::SETOEQ: // SETEQ & SETU[LG]E 341 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE 342 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE 343 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE 344 } 345 } 346 347 return Result; 348 } 349 350 //===----------------------------------------------------------------------===// 351 // SDNode Profile Support 352 //===----------------------------------------------------------------------===// 353 354 /// AddNodeIDOpcode - Add the node opcode to the NodeID data. 355 /// 356 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) { 357 ID.AddInteger(OpC); 358 } 359 360 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them 361 /// solely with their pointer. 362 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) { 363 ID.AddPointer(VTList.VTs); 364 } 365 366 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data. 367 /// 368 static void AddNodeIDOperands(FoldingSetNodeID &ID, 369 ArrayRef<SDValue> Ops) { 370 for (auto& Op : Ops) { 371 ID.AddPointer(Op.getNode()); 372 ID.AddInteger(Op.getResNo()); 373 } 374 } 375 376 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data. 377 /// 378 static void AddNodeIDOperands(FoldingSetNodeID &ID, 379 ArrayRef<SDUse> Ops) { 380 for (auto& Op : Ops) { 381 ID.AddPointer(Op.getNode()); 382 ID.AddInteger(Op.getResNo()); 383 } 384 } 385 386 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, bool nuw, bool nsw, 387 bool exact) { 388 ID.AddBoolean(nuw); 389 ID.AddBoolean(nsw); 390 ID.AddBoolean(exact); 391 } 392 393 /// AddBinaryNodeIDCustom - Add BinarySDNodes special infos 394 static void AddBinaryNodeIDCustom(FoldingSetNodeID &ID, unsigned Opcode, 395 bool nuw, bool nsw, bool exact) { 396 if (isBinOpWithFlags(Opcode)) 397 AddBinaryNodeIDCustom(ID, nuw, nsw, exact); 398 } 399 400 static void AddNodeIDNode(FoldingSetNodeID &ID, unsigned short OpC, 401 SDVTList VTList, ArrayRef<SDValue> OpList) { 402 AddNodeIDOpcode(ID, OpC); 403 AddNodeIDValueTypes(ID, VTList); 404 AddNodeIDOperands(ID, OpList); 405 } 406 407 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to 408 /// the NodeID data. 409 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) { 410 switch (N->getOpcode()) { 411 case ISD::TargetExternalSymbol: 412 case ISD::ExternalSymbol: 413 llvm_unreachable("Should only be used on nodes with operands"); 414 default: break; // Normal nodes don't need extra info. 415 case ISD::TargetConstant: 416 case ISD::Constant: { 417 const ConstantSDNode *C = cast<ConstantSDNode>(N); 418 ID.AddPointer(C->getConstantIntValue()); 419 ID.AddBoolean(C->isOpaque()); 420 break; 421 } 422 case ISD::TargetConstantFP: 423 case ISD::ConstantFP: { 424 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue()); 425 break; 426 } 427 case ISD::TargetGlobalAddress: 428 case ISD::GlobalAddress: 429 case ISD::TargetGlobalTLSAddress: 430 case ISD::GlobalTLSAddress: { 431 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N); 432 ID.AddPointer(GA->getGlobal()); 433 ID.AddInteger(GA->getOffset()); 434 ID.AddInteger(GA->getTargetFlags()); 435 ID.AddInteger(GA->getAddressSpace()); 436 break; 437 } 438 case ISD::BasicBlock: 439 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock()); 440 break; 441 case ISD::Register: 442 ID.AddInteger(cast<RegisterSDNode>(N)->getReg()); 443 break; 444 case ISD::RegisterMask: 445 ID.AddPointer(cast<RegisterMaskSDNode>(N)->getRegMask()); 446 break; 447 case ISD::SRCVALUE: 448 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue()); 449 break; 450 case ISD::FrameIndex: 451 case ISD::TargetFrameIndex: 452 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex()); 453 break; 454 case ISD::JumpTable: 455 case ISD::TargetJumpTable: 456 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex()); 457 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags()); 458 break; 459 case ISD::ConstantPool: 460 case ISD::TargetConstantPool: { 461 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N); 462 ID.AddInteger(CP->getAlignment()); 463 ID.AddInteger(CP->getOffset()); 464 if (CP->isMachineConstantPoolEntry()) 465 CP->getMachineCPVal()->addSelectionDAGCSEId(ID); 466 else 467 ID.AddPointer(CP->getConstVal()); 468 ID.AddInteger(CP->getTargetFlags()); 469 break; 470 } 471 case ISD::TargetIndex: { 472 const TargetIndexSDNode *TI = cast<TargetIndexSDNode>(N); 473 ID.AddInteger(TI->getIndex()); 474 ID.AddInteger(TI->getOffset()); 475 ID.AddInteger(TI->getTargetFlags()); 476 break; 477 } 478 case ISD::LOAD: { 479 const LoadSDNode *LD = cast<LoadSDNode>(N); 480 ID.AddInteger(LD->getMemoryVT().getRawBits()); 481 ID.AddInteger(LD->getRawSubclassData()); 482 ID.AddInteger(LD->getPointerInfo().getAddrSpace()); 483 break; 484 } 485 case ISD::STORE: { 486 const StoreSDNode *ST = cast<StoreSDNode>(N); 487 ID.AddInteger(ST->getMemoryVT().getRawBits()); 488 ID.AddInteger(ST->getRawSubclassData()); 489 ID.AddInteger(ST->getPointerInfo().getAddrSpace()); 490 break; 491 } 492 case ISD::SDIV: 493 case ISD::UDIV: 494 case ISD::SRA: 495 case ISD::SRL: 496 case ISD::MUL: 497 case ISD::ADD: 498 case ISD::SUB: 499 case ISD::SHL: { 500 const BinaryWithFlagsSDNode *BinNode = cast<BinaryWithFlagsSDNode>(N); 501 AddBinaryNodeIDCustom(ID, N->getOpcode(), BinNode->hasNoUnsignedWrap(), 502 BinNode->hasNoSignedWrap(), BinNode->isExact()); 503 break; 504 } 505 case ISD::ATOMIC_CMP_SWAP: 506 case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS: 507 case ISD::ATOMIC_SWAP: 508 case ISD::ATOMIC_LOAD_ADD: 509 case ISD::ATOMIC_LOAD_SUB: 510 case ISD::ATOMIC_LOAD_AND: 511 case ISD::ATOMIC_LOAD_OR: 512 case ISD::ATOMIC_LOAD_XOR: 513 case ISD::ATOMIC_LOAD_NAND: 514 case ISD::ATOMIC_LOAD_MIN: 515 case ISD::ATOMIC_LOAD_MAX: 516 case ISD::ATOMIC_LOAD_UMIN: 517 case ISD::ATOMIC_LOAD_UMAX: 518 case ISD::ATOMIC_LOAD: 519 case ISD::ATOMIC_STORE: { 520 const AtomicSDNode *AT = cast<AtomicSDNode>(N); 521 ID.AddInteger(AT->getMemoryVT().getRawBits()); 522 ID.AddInteger(AT->getRawSubclassData()); 523 ID.AddInteger(AT->getPointerInfo().getAddrSpace()); 524 break; 525 } 526 case ISD::PREFETCH: { 527 const MemSDNode *PF = cast<MemSDNode>(N); 528 ID.AddInteger(PF->getPointerInfo().getAddrSpace()); 529 break; 530 } 531 case ISD::VECTOR_SHUFFLE: { 532 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N); 533 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements(); 534 i != e; ++i) 535 ID.AddInteger(SVN->getMaskElt(i)); 536 break; 537 } 538 case ISD::TargetBlockAddress: 539 case ISD::BlockAddress: { 540 const BlockAddressSDNode *BA = cast<BlockAddressSDNode>(N); 541 ID.AddPointer(BA->getBlockAddress()); 542 ID.AddInteger(BA->getOffset()); 543 ID.AddInteger(BA->getTargetFlags()); 544 break; 545 } 546 } // end switch (N->getOpcode()) 547 548 // Target specific memory nodes could also have address spaces to check. 549 if (N->isTargetMemoryOpcode()) 550 ID.AddInteger(cast<MemSDNode>(N)->getPointerInfo().getAddrSpace()); 551 } 552 553 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID 554 /// data. 555 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) { 556 AddNodeIDOpcode(ID, N->getOpcode()); 557 // Add the return value info. 558 AddNodeIDValueTypes(ID, N->getVTList()); 559 // Add the operand info. 560 AddNodeIDOperands(ID, N->ops()); 561 562 // Handle SDNode leafs with special info. 563 AddNodeIDCustom(ID, N); 564 } 565 566 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in 567 /// the CSE map that carries volatility, temporalness, indexing mode, and 568 /// extension/truncation information. 569 /// 570 static inline unsigned 571 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, bool isVolatile, 572 bool isNonTemporal, bool isInvariant) { 573 assert((ConvType & 3) == ConvType && 574 "ConvType may not require more than 2 bits!"); 575 assert((AM & 7) == AM && 576 "AM may not require more than 3 bits!"); 577 return ConvType | 578 (AM << 2) | 579 (isVolatile << 5) | 580 (isNonTemporal << 6) | 581 (isInvariant << 7); 582 } 583 584 //===----------------------------------------------------------------------===// 585 // SelectionDAG Class 586 //===----------------------------------------------------------------------===// 587 588 /// doNotCSE - Return true if CSE should not be performed for this node. 589 static bool doNotCSE(SDNode *N) { 590 if (N->getValueType(0) == MVT::Glue) 591 return true; // Never CSE anything that produces a flag. 592 593 switch (N->getOpcode()) { 594 default: break; 595 case ISD::HANDLENODE: 596 case ISD::EH_LABEL: 597 return true; // Never CSE these nodes. 598 } 599 600 // Check that remaining values produced are not flags. 601 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 602 if (N->getValueType(i) == MVT::Glue) 603 return true; // Never CSE anything that produces a flag. 604 605 return false; 606 } 607 608 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 609 /// SelectionDAG. 610 void SelectionDAG::RemoveDeadNodes() { 611 // Create a dummy node (which is not added to allnodes), that adds a reference 612 // to the root node, preventing it from being deleted. 613 HandleSDNode Dummy(getRoot()); 614 615 SmallVector<SDNode*, 128> DeadNodes; 616 617 // Add all obviously-dead nodes to the DeadNodes worklist. 618 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) 619 if (I->use_empty()) 620 DeadNodes.push_back(I); 621 622 RemoveDeadNodes(DeadNodes); 623 624 // If the root changed (e.g. it was a dead load, update the root). 625 setRoot(Dummy.getValue()); 626 } 627 628 /// RemoveDeadNodes - This method deletes the unreachable nodes in the 629 /// given list, and any nodes that become unreachable as a result. 630 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes) { 631 632 // Process the worklist, deleting the nodes and adding their uses to the 633 // worklist. 634 while (!DeadNodes.empty()) { 635 SDNode *N = DeadNodes.pop_back_val(); 636 637 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next) 638 DUL->NodeDeleted(N, nullptr); 639 640 // Take the node out of the appropriate CSE map. 641 RemoveNodeFromCSEMaps(N); 642 643 // Next, brutally remove the operand list. This is safe to do, as there are 644 // no cycles in the graph. 645 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) { 646 SDUse &Use = *I++; 647 SDNode *Operand = Use.getNode(); 648 Use.set(SDValue()); 649 650 // Now that we removed this operand, see if there are no uses of it left. 651 if (Operand->use_empty()) 652 DeadNodes.push_back(Operand); 653 } 654 655 DeallocateNode(N); 656 } 657 } 658 659 void SelectionDAG::RemoveDeadNode(SDNode *N){ 660 SmallVector<SDNode*, 16> DeadNodes(1, N); 661 662 // Create a dummy node that adds a reference to the root node, preventing 663 // it from being deleted. (This matters if the root is an operand of the 664 // dead node.) 665 HandleSDNode Dummy(getRoot()); 666 667 RemoveDeadNodes(DeadNodes); 668 } 669 670 void SelectionDAG::DeleteNode(SDNode *N) { 671 // First take this out of the appropriate CSE map. 672 RemoveNodeFromCSEMaps(N); 673 674 // Finally, remove uses due to operands of this node, remove from the 675 // AllNodes list, and delete the node. 676 DeleteNodeNotInCSEMaps(N); 677 } 678 679 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { 680 assert(N != AllNodes.begin() && "Cannot delete the entry node!"); 681 assert(N->use_empty() && "Cannot delete a node that is not dead!"); 682 683 // Drop all of the operands and decrement used node's use counts. 684 N->DropOperands(); 685 686 DeallocateNode(N); 687 } 688 689 void SelectionDAG::DeallocateNode(SDNode *N) { 690 if (N->OperandsNeedDelete) 691 delete[] N->OperandList; 692 693 // Set the opcode to DELETED_NODE to help catch bugs when node 694 // memory is reallocated. 695 N->NodeType = ISD::DELETED_NODE; 696 697 NodeAllocator.Deallocate(AllNodes.remove(N)); 698 699 // If any of the SDDbgValue nodes refer to this SDNode, invalidate them. 700 ArrayRef<SDDbgValue*> DbgVals = DbgInfo->getSDDbgValues(N); 701 for (unsigned i = 0, e = DbgVals.size(); i != e; ++i) 702 DbgVals[i]->setIsInvalidated(); 703 } 704 705 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that 706 /// correspond to it. This is useful when we're about to delete or repurpose 707 /// the node. We don't want future request for structurally identical nodes 708 /// to return N anymore. 709 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { 710 bool Erased = false; 711 switch (N->getOpcode()) { 712 case ISD::HANDLENODE: return false; // noop. 713 case ISD::CONDCODE: 714 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] && 715 "Cond code doesn't exist!"); 716 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != nullptr; 717 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = nullptr; 718 break; 719 case ISD::ExternalSymbol: 720 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 721 break; 722 case ISD::TargetExternalSymbol: { 723 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N); 724 Erased = TargetExternalSymbols.erase( 725 std::pair<std::string,unsigned char>(ESN->getSymbol(), 726 ESN->getTargetFlags())); 727 break; 728 } 729 case ISD::VALUETYPE: { 730 EVT VT = cast<VTSDNode>(N)->getVT(); 731 if (VT.isExtended()) { 732 Erased = ExtendedValueTypeNodes.erase(VT); 733 } else { 734 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != nullptr; 735 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = nullptr; 736 } 737 break; 738 } 739 default: 740 // Remove it from the CSE Map. 741 assert(N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!"); 742 assert(N->getOpcode() != ISD::EntryToken && "EntryToken in CSEMap!"); 743 Erased = CSEMap.RemoveNode(N); 744 break; 745 } 746 #ifndef NDEBUG 747 // Verify that the node was actually in one of the CSE maps, unless it has a 748 // flag result (which cannot be CSE'd) or is one of the special cases that are 749 // not subject to CSE. 750 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Glue && 751 !N->isMachineOpcode() && !doNotCSE(N)) { 752 N->dump(this); 753 dbgs() << "\n"; 754 llvm_unreachable("Node is not in map!"); 755 } 756 #endif 757 return Erased; 758 } 759 760 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE 761 /// maps and modified in place. Add it back to the CSE maps, unless an identical 762 /// node already exists, in which case transfer all its users to the existing 763 /// node. This transfer can potentially trigger recursive merging. 764 /// 765 void 766 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N) { 767 // For node types that aren't CSE'd, just act as if no identical node 768 // already exists. 769 if (!doNotCSE(N)) { 770 SDNode *Existing = CSEMap.GetOrInsertNode(N); 771 if (Existing != N) { 772 // If there was already an existing matching node, use ReplaceAllUsesWith 773 // to replace the dead one with the existing one. This can cause 774 // recursive merging of other unrelated nodes down the line. 775 ReplaceAllUsesWith(N, Existing); 776 777 // N is now dead. Inform the listeners and delete it. 778 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next) 779 DUL->NodeDeleted(N, Existing); 780 DeleteNodeNotInCSEMaps(N); 781 return; 782 } 783 } 784 785 // If the node doesn't already exist, we updated it. Inform listeners. 786 for (DAGUpdateListener *DUL = UpdateListeners; DUL; DUL = DUL->Next) 787 DUL->NodeUpdated(N); 788 } 789 790 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands 791 /// were replaced with those specified. If this node is never memoized, 792 /// return null, otherwise return a pointer to the slot it would take. If a 793 /// node already exists with these operands, the slot will be non-null. 794 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op, 795 void *&InsertPos) { 796 if (doNotCSE(N)) 797 return nullptr; 798 799 SDValue Ops[] = { Op }; 800 FoldingSetNodeID ID; 801 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops); 802 AddNodeIDCustom(ID, N); 803 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos); 804 return Node; 805 } 806 807 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands 808 /// were replaced with those specified. If this node is never memoized, 809 /// return null, otherwise return a pointer to the slot it would take. If a 810 /// node already exists with these operands, the slot will be non-null. 811 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 812 SDValue Op1, SDValue Op2, 813 void *&InsertPos) { 814 if (doNotCSE(N)) 815 return nullptr; 816 817 SDValue Ops[] = { Op1, Op2 }; 818 FoldingSetNodeID ID; 819 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops); 820 AddNodeIDCustom(ID, N); 821 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos); 822 return Node; 823 } 824 825 826 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands 827 /// were replaced with those specified. If this node is never memoized, 828 /// return null, otherwise return a pointer to the slot it would take. If a 829 /// node already exists with these operands, the slot will be non-null. 830 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops, 831 void *&InsertPos) { 832 if (doNotCSE(N)) 833 return nullptr; 834 835 FoldingSetNodeID ID; 836 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops); 837 AddNodeIDCustom(ID, N); 838 SDNode *Node = CSEMap.FindNodeOrInsertPos(ID, InsertPos); 839 return Node; 840 } 841 842 #ifndef NDEBUG 843 /// VerifyNodeCommon - Sanity check the given node. Aborts if it is invalid. 844 static void VerifyNodeCommon(SDNode *N) { 845 switch (N->getOpcode()) { 846 default: 847 break; 848 case ISD::BUILD_PAIR: { 849 EVT VT = N->getValueType(0); 850 assert(N->getNumValues() == 1 && "Too many results!"); 851 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) && 852 "Wrong return type!"); 853 assert(N->getNumOperands() == 2 && "Wrong number of operands!"); 854 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() && 855 "Mismatched operand types!"); 856 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() && 857 "Wrong operand type!"); 858 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() && 859 "Wrong return type size"); 860 break; 861 } 862 case ISD::BUILD_VECTOR: { 863 assert(N->getNumValues() == 1 && "Too many results!"); 864 assert(N->getValueType(0).isVector() && "Wrong return type!"); 865 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() && 866 "Wrong number of operands!"); 867 EVT EltVT = N->getValueType(0).getVectorElementType(); 868 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 869 assert((I->getValueType() == EltVT || 870 (EltVT.isInteger() && I->getValueType().isInteger() && 871 EltVT.bitsLE(I->getValueType()))) && 872 "Wrong operand type!"); 873 assert(I->getValueType() == N->getOperand(0).getValueType() && 874 "Operands must all have the same type"); 875 } 876 break; 877 } 878 } 879 } 880 881 /// VerifySDNode - Sanity check the given SDNode. Aborts if it is invalid. 882 static void VerifySDNode(SDNode *N) { 883 // The SDNode allocators cannot be used to allocate nodes with fields that are 884 // not present in an SDNode! 885 assert(!isa<MemSDNode>(N) && "Bad MemSDNode!"); 886 assert(!isa<ShuffleVectorSDNode>(N) && "Bad ShuffleVectorSDNode!"); 887 assert(!isa<ConstantSDNode>(N) && "Bad ConstantSDNode!"); 888 assert(!isa<ConstantFPSDNode>(N) && "Bad ConstantFPSDNode!"); 889 assert(!isa<GlobalAddressSDNode>(N) && "Bad GlobalAddressSDNode!"); 890 assert(!isa<FrameIndexSDNode>(N) && "Bad FrameIndexSDNode!"); 891 assert(!isa<JumpTableSDNode>(N) && "Bad JumpTableSDNode!"); 892 assert(!isa<ConstantPoolSDNode>(N) && "Bad ConstantPoolSDNode!"); 893 assert(!isa<BasicBlockSDNode>(N) && "Bad BasicBlockSDNode!"); 894 assert(!isa<SrcValueSDNode>(N) && "Bad SrcValueSDNode!"); 895 assert(!isa<MDNodeSDNode>(N) && "Bad MDNodeSDNode!"); 896 assert(!isa<RegisterSDNode>(N) && "Bad RegisterSDNode!"); 897 assert(!isa<BlockAddressSDNode>(N) && "Bad BlockAddressSDNode!"); 898 assert(!isa<EHLabelSDNode>(N) && "Bad EHLabelSDNode!"); 899 assert(!isa<ExternalSymbolSDNode>(N) && "Bad ExternalSymbolSDNode!"); 900 assert(!isa<CondCodeSDNode>(N) && "Bad CondCodeSDNode!"); 901 assert(!isa<CvtRndSatSDNode>(N) && "Bad CvtRndSatSDNode!"); 902 assert(!isa<VTSDNode>(N) && "Bad VTSDNode!"); 903 assert(!isa<MachineSDNode>(N) && "Bad MachineSDNode!"); 904 905 VerifyNodeCommon(N); 906 } 907 908 /// VerifyMachineNode - Sanity check the given MachineNode. Aborts if it is 909 /// invalid. 910 static void VerifyMachineNode(SDNode *N) { 911 // The MachineNode allocators cannot be used to allocate nodes with fields 912 // that are not present in a MachineNode! 913 // Currently there are no such nodes. 914 915 VerifyNodeCommon(N); 916 } 917 #endif // NDEBUG 918 919 /// getEVTAlignment - Compute the default alignment value for the 920 /// given type. 921 /// 922 unsigned SelectionDAG::getEVTAlignment(EVT VT) const { 923 Type *Ty = VT == MVT::iPTR ? 924 PointerType::get(Type::getInt8Ty(*getContext()), 0) : 925 VT.getTypeForEVT(*getContext()); 926 927 return TM.getTargetLowering()->getDataLayout()->getABITypeAlignment(Ty); 928 } 929 930 // EntryNode could meaningfully have debug info if we can find it... 931 SelectionDAG::SelectionDAG(const TargetMachine &tm, CodeGenOpt::Level OL) 932 : TM(tm), TSI(*tm.getSelectionDAGInfo()), TLI(nullptr), OptLevel(OL), 933 EntryNode(ISD::EntryToken, 0, DebugLoc(), getVTList(MVT::Other)), 934 Root(getEntryNode()), NewNodesMustHaveLegalTypes(false), 935 UpdateListeners(nullptr) { 936 AllNodes.push_back(&EntryNode); 937 DbgInfo = new SDDbgInfo(); 938 } 939 940 void SelectionDAG::init(MachineFunction &mf, const TargetLowering *tli) { 941 MF = &mf; 942 TLI = tli; 943 Context = &mf.getFunction()->getContext(); 944 } 945 946 SelectionDAG::~SelectionDAG() { 947 assert(!UpdateListeners && "Dangling registered DAGUpdateListeners"); 948 allnodes_clear(); 949 delete DbgInfo; 950 } 951 952 void SelectionDAG::allnodes_clear() { 953 assert(&*AllNodes.begin() == &EntryNode); 954 AllNodes.remove(AllNodes.begin()); 955 while (!AllNodes.empty()) 956 DeallocateNode(AllNodes.begin()); 957 } 958 959 BinarySDNode *SelectionDAG::GetBinarySDNode(unsigned Opcode, SDLoc DL, 960 SDVTList VTs, SDValue N1, 961 SDValue N2, bool nuw, bool nsw, 962 bool exact) { 963 if (isBinOpWithFlags(Opcode)) { 964 BinaryWithFlagsSDNode *FN = new (NodeAllocator) BinaryWithFlagsSDNode( 965 Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2); 966 FN->setHasNoUnsignedWrap(nuw); 967 FN->setHasNoSignedWrap(nsw); 968 FN->setIsExact(exact); 969 970 return FN; 971 } 972 973 BinarySDNode *N = new (NodeAllocator) 974 BinarySDNode(Opcode, DL.getIROrder(), DL.getDebugLoc(), VTs, N1, N2); 975 return N; 976 } 977 978 void SelectionDAG::clear() { 979 allnodes_clear(); 980 OperandAllocator.Reset(); 981 CSEMap.clear(); 982 983 ExtendedValueTypeNodes.clear(); 984 ExternalSymbols.clear(); 985 TargetExternalSymbols.clear(); 986 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(), 987 static_cast<CondCodeSDNode*>(nullptr)); 988 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(), 989 static_cast<SDNode*>(nullptr)); 990 991 EntryNode.UseList = nullptr; 992 AllNodes.push_back(&EntryNode); 993 Root = getEntryNode(); 994 DbgInfo->clear(); 995 } 996 997 SDValue SelectionDAG::getAnyExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) { 998 return VT.bitsGT(Op.getValueType()) ? 999 getNode(ISD::ANY_EXTEND, DL, VT, Op) : 1000 getNode(ISD::TRUNCATE, DL, VT, Op); 1001 } 1002 1003 SDValue SelectionDAG::getSExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) { 1004 return VT.bitsGT(Op.getValueType()) ? 1005 getNode(ISD::SIGN_EXTEND, DL, VT, Op) : 1006 getNode(ISD::TRUNCATE, DL, VT, Op); 1007 } 1008 1009 SDValue SelectionDAG::getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT) { 1010 return VT.bitsGT(Op.getValueType()) ? 1011 getNode(ISD::ZERO_EXTEND, DL, VT, Op) : 1012 getNode(ISD::TRUNCATE, DL, VT, Op); 1013 } 1014 1015 SDValue SelectionDAG::getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT, 1016 EVT OpVT) { 1017 if (VT.bitsLE(Op.getValueType())) 1018 return getNode(ISD::TRUNCATE, SL, VT, Op); 1019 1020 TargetLowering::BooleanContent BType = TLI->getBooleanContents(OpVT); 1021 return getNode(TLI->getExtendForContent(BType), SL, VT, Op); 1022 } 1023 1024 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) { 1025 assert(!VT.isVector() && 1026 "getZeroExtendInReg should use the vector element type instead of " 1027 "the vector type!"); 1028 if (Op.getValueType() == VT) return Op; 1029 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits(); 1030 APInt Imm = APInt::getLowBitsSet(BitWidth, 1031 VT.getSizeInBits()); 1032 return getNode(ISD::AND, DL, Op.getValueType(), Op, 1033 getConstant(Imm, Op.getValueType())); 1034 } 1035 1036 SDValue SelectionDAG::getAnyExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) { 1037 assert(VT.isVector() && "This DAG node is restricted to vector types."); 1038 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() && 1039 "The sizes of the input and result must match in order to perform the " 1040 "extend in-register."); 1041 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() && 1042 "The destination vector type must have fewer lanes than the input."); 1043 return getNode(ISD::ANY_EXTEND_VECTOR_INREG, DL, VT, Op); 1044 } 1045 1046 SDValue SelectionDAG::getSignExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) { 1047 assert(VT.isVector() && "This DAG node is restricted to vector types."); 1048 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() && 1049 "The sizes of the input and result must match in order to perform the " 1050 "extend in-register."); 1051 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() && 1052 "The destination vector type must have fewer lanes than the input."); 1053 return getNode(ISD::SIGN_EXTEND_VECTOR_INREG, DL, VT, Op); 1054 } 1055 1056 SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) { 1057 assert(VT.isVector() && "This DAG node is restricted to vector types."); 1058 assert(VT.getSizeInBits() == Op.getValueType().getSizeInBits() && 1059 "The sizes of the input and result must match in order to perform the " 1060 "extend in-register."); 1061 assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() && 1062 "The destination vector type must have fewer lanes than the input."); 1063 return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op); 1064 } 1065 1066 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). 1067 /// 1068 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) { 1069 EVT EltVT = VT.getScalarType(); 1070 SDValue NegOne = 1071 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT); 1072 return getNode(ISD::XOR, DL, VT, Val, NegOne); 1073 } 1074 1075 SDValue SelectionDAG::getLogicalNOT(SDLoc DL, SDValue Val, EVT VT) { 1076 EVT EltVT = VT.getScalarType(); 1077 SDValue TrueValue; 1078 switch (TLI->getBooleanContents(VT)) { 1079 case TargetLowering::ZeroOrOneBooleanContent: 1080 case TargetLowering::UndefinedBooleanContent: 1081 TrueValue = getConstant(1, VT); 1082 break; 1083 case TargetLowering::ZeroOrNegativeOneBooleanContent: 1084 TrueValue = getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), 1085 VT); 1086 break; 1087 } 1088 return getNode(ISD::XOR, DL, VT, Val, TrueValue); 1089 } 1090 1091 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT, bool isO) { 1092 EVT EltVT = VT.getScalarType(); 1093 assert((EltVT.getSizeInBits() >= 64 || 1094 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) && 1095 "getConstant with a uint64_t value that doesn't fit in the type!"); 1096 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT, isO); 1097 } 1098 1099 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT, bool isO) 1100 { 1101 return getConstant(*ConstantInt::get(*Context, Val), VT, isT, isO); 1102 } 1103 1104 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT, 1105 bool isO) { 1106 assert(VT.isInteger() && "Cannot create FP integer constant!"); 1107 1108 EVT EltVT = VT.getScalarType(); 1109 const ConstantInt *Elt = &Val; 1110 1111 const TargetLowering *TLI = TM.getTargetLowering(); 1112 1113 // In some cases the vector type is legal but the element type is illegal and 1114 // needs to be promoted, for example v8i8 on ARM. In this case, promote the 1115 // inserted value (the type does not need to match the vector element type). 1116 // Any extra bits introduced will be truncated away. 1117 if (VT.isVector() && TLI->getTypeAction(*getContext(), EltVT) == 1118 TargetLowering::TypePromoteInteger) { 1119 EltVT = TLI->getTypeToTransformTo(*getContext(), EltVT); 1120 APInt NewVal = Elt->getValue().zext(EltVT.getSizeInBits()); 1121 Elt = ConstantInt::get(*getContext(), NewVal); 1122 } 1123 // In other cases the element type is illegal and needs to be expanded, for 1124 // example v2i64 on MIPS32. In this case, find the nearest legal type, split 1125 // the value into n parts and use a vector type with n-times the elements. 1126 // Then bitcast to the type requested. 1127 // Legalizing constants too early makes the DAGCombiner's job harder so we 1128 // only legalize if the DAG tells us we must produce legal types. 1129 else if (NewNodesMustHaveLegalTypes && VT.isVector() && 1130 TLI->getTypeAction(*getContext(), EltVT) == 1131 TargetLowering::TypeExpandInteger) { 1132 APInt NewVal = Elt->getValue(); 1133 EVT ViaEltVT = TLI->getTypeToTransformTo(*getContext(), EltVT); 1134 unsigned ViaEltSizeInBits = ViaEltVT.getSizeInBits(); 1135 unsigned ViaVecNumElts = VT.getSizeInBits() / ViaEltSizeInBits; 1136 EVT ViaVecVT = EVT::getVectorVT(*getContext(), ViaEltVT, ViaVecNumElts); 1137 1138 // Check the temporary vector is the correct size. If this fails then 1139 // getTypeToTransformTo() probably returned a type whose size (in bits) 1140 // isn't a power-of-2 factor of the requested type size. 1141 assert(ViaVecVT.getSizeInBits() == VT.getSizeInBits()); 1142 1143 SmallVector<SDValue, 2> EltParts; 1144 for (unsigned i = 0; i < ViaVecNumElts / VT.getVectorNumElements(); ++i) { 1145 EltParts.push_back(getConstant(NewVal.lshr(i * ViaEltSizeInBits) 1146 .trunc(ViaEltSizeInBits), 1147 ViaEltVT, isT, isO)); 1148 } 1149 1150 // EltParts is currently in little endian order. If we actually want 1151 // big-endian order then reverse it now. 1152 if (TLI->isBigEndian()) 1153 std::reverse(EltParts.begin(), EltParts.end()); 1154 1155 // The elements must be reversed when the element order is different 1156 // to the endianness of the elements (because the BITCAST is itself a 1157 // vector shuffle in this situation). However, we do not need any code to 1158 // perform this reversal because getConstant() is producing a vector 1159 // splat. 1160 // This situation occurs in MIPS MSA. 1161 1162 SmallVector<SDValue, 8> Ops; 1163 for (unsigned i = 0; i < VT.getVectorNumElements(); ++i) 1164 Ops.insert(Ops.end(), EltParts.begin(), EltParts.end()); 1165 1166 SDValue Result = getNode(ISD::BITCAST, SDLoc(), VT, 1167 getNode(ISD::BUILD_VECTOR, SDLoc(), ViaVecVT, 1168 Ops)); 1169 return Result; 1170 } 1171 1172 assert(Elt->getBitWidth() == EltVT.getSizeInBits() && 1173 "APInt size does not match type size!"); 1174 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant; 1175 FoldingSetNodeID ID; 1176 AddNodeIDNode(ID, Opc, getVTList(EltVT), None); 1177 ID.AddPointer(Elt); 1178 ID.AddBoolean(isO); 1179 void *IP = nullptr; 1180 SDNode *N = nullptr; 1181 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) 1182 if (!VT.isVector()) 1183 return SDValue(N, 0); 1184 1185 if (!N) { 1186 N = new (NodeAllocator) ConstantSDNode(isT, isO, Elt, EltVT); 1187 CSEMap.InsertNode(N, IP); 1188 AllNodes.push_back(N); 1189 } 1190 1191 SDValue Result(N, 0); 1192 if (VT.isVector()) { 1193 SmallVector<SDValue, 8> Ops; 1194 Ops.assign(VT.getVectorNumElements(), Result); 1195 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops); 1196 } 1197 return Result; 1198 } 1199 1200 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) { 1201 return getConstant(Val, TM.getTargetLowering()->getPointerTy(), isTarget); 1202 } 1203 1204 1205 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) { 1206 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget); 1207 } 1208 1209 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){ 1210 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!"); 1211 1212 EVT EltVT = VT.getScalarType(); 1213 1214 // Do the map lookup using the actual bit pattern for the floating point 1215 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 1216 // we don't have issues with SNANs. 1217 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP; 1218 FoldingSetNodeID ID; 1219 AddNodeIDNode(ID, Opc, getVTList(EltVT), None); 1220 ID.AddPointer(&V); 1221 void *IP = nullptr; 1222 SDNode *N = nullptr; 1223 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) 1224 if (!VT.isVector()) 1225 return SDValue(N, 0); 1226 1227 if (!N) { 1228 N = new (NodeAllocator) ConstantFPSDNode(isTarget, &V, EltVT); 1229 CSEMap.InsertNode(N, IP); 1230 AllNodes.push_back(N); 1231 } 1232 1233 SDValue Result(N, 0); 1234 if (VT.isVector()) { 1235 SmallVector<SDValue, 8> Ops; 1236 Ops.assign(VT.getVectorNumElements(), Result); 1237 // FIXME SDLoc info might be appropriate here 1238 Result = getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Ops); 1239 } 1240 return Result; 1241 } 1242 1243 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) { 1244 EVT EltVT = VT.getScalarType(); 1245 if (EltVT==MVT::f32) 1246 return getConstantFP(APFloat((float)Val), VT, isTarget); 1247 else if (EltVT==MVT::f64) 1248 return getConstantFP(APFloat(Val), VT, isTarget); 1249 else if (EltVT==MVT::f80 || EltVT==MVT::f128 || EltVT==MVT::ppcf128 || 1250 EltVT==MVT::f16) { 1251 bool ignored; 1252 APFloat apf = APFloat(Val); 1253 apf.convert(EVTToAPFloatSemantics(EltVT), APFloat::rmNearestTiesToEven, 1254 &ignored); 1255 return getConstantFP(apf, VT, isTarget); 1256 } else 1257 llvm_unreachable("Unsupported type in getConstantFP"); 1258 } 1259 1260 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, SDLoc DL, 1261 EVT VT, int64_t Offset, 1262 bool isTargetGA, 1263 unsigned char TargetFlags) { 1264 assert((TargetFlags == 0 || isTargetGA) && 1265 "Cannot set target flags on target-independent globals"); 1266 const TargetLowering *TLI = TM.getTargetLowering(); 1267 1268 // Truncate (with sign-extension) the offset value to the pointer size. 1269 unsigned BitWidth = TLI->getPointerTypeSizeInBits(GV->getType()); 1270 if (BitWidth < 64) 1271 Offset = SignExtend64(Offset, BitWidth); 1272 1273 unsigned Opc; 1274 if (GV->isThreadLocal()) 1275 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress; 1276 else 1277 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress; 1278 1279 FoldingSetNodeID ID; 1280 AddNodeIDNode(ID, Opc, getVTList(VT), None); 1281 ID.AddPointer(GV); 1282 ID.AddInteger(Offset); 1283 ID.AddInteger(TargetFlags); 1284 ID.AddInteger(GV->getType()->getAddressSpace()); 1285 void *IP = nullptr; 1286 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1287 return SDValue(E, 0); 1288 1289 SDNode *N = new (NodeAllocator) GlobalAddressSDNode(Opc, DL.getIROrder(), 1290 DL.getDebugLoc(), GV, VT, 1291 Offset, TargetFlags); 1292 CSEMap.InsertNode(N, IP); 1293 AllNodes.push_back(N); 1294 return SDValue(N, 0); 1295 } 1296 1297 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) { 1298 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex; 1299 FoldingSetNodeID ID; 1300 AddNodeIDNode(ID, Opc, getVTList(VT), None); 1301 ID.AddInteger(FI); 1302 void *IP = nullptr; 1303 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1304 return SDValue(E, 0); 1305 1306 SDNode *N = new (NodeAllocator) FrameIndexSDNode(FI, VT, isTarget); 1307 CSEMap.InsertNode(N, IP); 1308 AllNodes.push_back(N); 1309 return SDValue(N, 0); 1310 } 1311 1312 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget, 1313 unsigned char TargetFlags) { 1314 assert((TargetFlags == 0 || isTarget) && 1315 "Cannot set target flags on target-independent jump tables"); 1316 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable; 1317 FoldingSetNodeID ID; 1318 AddNodeIDNode(ID, Opc, getVTList(VT), None); 1319 ID.AddInteger(JTI); 1320 ID.AddInteger(TargetFlags); 1321 void *IP = nullptr; 1322 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1323 return SDValue(E, 0); 1324 1325 SDNode *N = new (NodeAllocator) JumpTableSDNode(JTI, VT, isTarget, 1326 TargetFlags); 1327 CSEMap.InsertNode(N, IP); 1328 AllNodes.push_back(N); 1329 return SDValue(N, 0); 1330 } 1331 1332 SDValue SelectionDAG::getConstantPool(const Constant *C, EVT VT, 1333 unsigned Alignment, int Offset, 1334 bool isTarget, 1335 unsigned char TargetFlags) { 1336 assert((TargetFlags == 0 || isTarget) && 1337 "Cannot set target flags on target-independent globals"); 1338 if (Alignment == 0) 1339 Alignment = 1340 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType()); 1341 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 1342 FoldingSetNodeID ID; 1343 AddNodeIDNode(ID, Opc, getVTList(VT), None); 1344 ID.AddInteger(Alignment); 1345 ID.AddInteger(Offset); 1346 ID.AddPointer(C); 1347 ID.AddInteger(TargetFlags); 1348 void *IP = nullptr; 1349 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1350 return SDValue(E, 0); 1351 1352 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset, 1353 Alignment, TargetFlags); 1354 CSEMap.InsertNode(N, IP); 1355 AllNodes.push_back(N); 1356 return SDValue(N, 0); 1357 } 1358 1359 1360 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT, 1361 unsigned Alignment, int Offset, 1362 bool isTarget, 1363 unsigned char TargetFlags) { 1364 assert((TargetFlags == 0 || isTarget) && 1365 "Cannot set target flags on target-independent globals"); 1366 if (Alignment == 0) 1367 Alignment = 1368 TM.getTargetLowering()->getDataLayout()->getPrefTypeAlignment(C->getType()); 1369 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 1370 FoldingSetNodeID ID; 1371 AddNodeIDNode(ID, Opc, getVTList(VT), None); 1372 ID.AddInteger(Alignment); 1373 ID.AddInteger(Offset); 1374 C->addSelectionDAGCSEId(ID); 1375 ID.AddInteger(TargetFlags); 1376 void *IP = nullptr; 1377 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1378 return SDValue(E, 0); 1379 1380 SDNode *N = new (NodeAllocator) ConstantPoolSDNode(isTarget, C, VT, Offset, 1381 Alignment, TargetFlags); 1382 CSEMap.InsertNode(N, IP); 1383 AllNodes.push_back(N); 1384 return SDValue(N, 0); 1385 } 1386 1387 SDValue SelectionDAG::getTargetIndex(int Index, EVT VT, int64_t Offset, 1388 unsigned char TargetFlags) { 1389 FoldingSetNodeID ID; 1390 AddNodeIDNode(ID, ISD::TargetIndex, getVTList(VT), None); 1391 ID.AddInteger(Index); 1392 ID.AddInteger(Offset); 1393 ID.AddInteger(TargetFlags); 1394 void *IP = nullptr; 1395 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1396 return SDValue(E, 0); 1397 1398 SDNode *N = new (NodeAllocator) TargetIndexSDNode(Index, VT, Offset, 1399 TargetFlags); 1400 CSEMap.InsertNode(N, IP); 1401 AllNodes.push_back(N); 1402 return SDValue(N, 0); 1403 } 1404 1405 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 1406 FoldingSetNodeID ID; 1407 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), None); 1408 ID.AddPointer(MBB); 1409 void *IP = nullptr; 1410 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1411 return SDValue(E, 0); 1412 1413 SDNode *N = new (NodeAllocator) BasicBlockSDNode(MBB); 1414 CSEMap.InsertNode(N, IP); 1415 AllNodes.push_back(N); 1416 return SDValue(N, 0); 1417 } 1418 1419 SDValue SelectionDAG::getValueType(EVT VT) { 1420 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >= 1421 ValueTypeNodes.size()) 1422 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1); 1423 1424 SDNode *&N = VT.isExtended() ? 1425 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy]; 1426 1427 if (N) return SDValue(N, 0); 1428 N = new (NodeAllocator) VTSDNode(VT); 1429 AllNodes.push_back(N); 1430 return SDValue(N, 0); 1431 } 1432 1433 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) { 1434 SDNode *&N = ExternalSymbols[Sym]; 1435 if (N) return SDValue(N, 0); 1436 N = new (NodeAllocator) ExternalSymbolSDNode(false, Sym, 0, VT); 1437 AllNodes.push_back(N); 1438 return SDValue(N, 0); 1439 } 1440 1441 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT, 1442 unsigned char TargetFlags) { 1443 SDNode *&N = 1444 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym, 1445 TargetFlags)]; 1446 if (N) return SDValue(N, 0); 1447 N = new (NodeAllocator) ExternalSymbolSDNode(true, Sym, TargetFlags, VT); 1448 AllNodes.push_back(N); 1449 return SDValue(N, 0); 1450 } 1451 1452 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) { 1453 if ((unsigned)Cond >= CondCodeNodes.size()) 1454 CondCodeNodes.resize(Cond+1); 1455 1456 if (!CondCodeNodes[Cond]) { 1457 CondCodeSDNode *N = new (NodeAllocator) CondCodeSDNode(Cond); 1458 CondCodeNodes[Cond] = N; 1459 AllNodes.push_back(N); 1460 } 1461 1462 return SDValue(CondCodeNodes[Cond], 0); 1463 } 1464 1465 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in 1466 // the shuffle mask M that point at N1 to point at N2, and indices that point 1467 // N2 to point at N1. 1468 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) { 1469 std::swap(N1, N2); 1470 int NElts = M.size(); 1471 for (int i = 0; i != NElts; ++i) { 1472 if (M[i] >= NElts) 1473 M[i] -= NElts; 1474 else if (M[i] >= 0) 1475 M[i] += NElts; 1476 } 1477 } 1478 1479 SDValue SelectionDAG::getVectorShuffle(EVT VT, SDLoc dl, SDValue N1, 1480 SDValue N2, const int *Mask) { 1481 assert(VT == N1.getValueType() && VT == N2.getValueType() && 1482 "Invalid VECTOR_SHUFFLE"); 1483 1484 // Canonicalize shuffle undef, undef -> undef 1485 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF) 1486 return getUNDEF(VT); 1487 1488 // Validate that all indices in Mask are within the range of the elements 1489 // input to the shuffle. 1490 unsigned NElts = VT.getVectorNumElements(); 1491 SmallVector<int, 8> MaskVec; 1492 for (unsigned i = 0; i != NElts; ++i) { 1493 assert(Mask[i] < (int)(NElts * 2) && "Index out of range"); 1494 MaskVec.push_back(Mask[i]); 1495 } 1496 1497 // Canonicalize shuffle v, v -> v, undef 1498 if (N1 == N2) { 1499 N2 = getUNDEF(VT); 1500 for (unsigned i = 0; i != NElts; ++i) 1501 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts; 1502 } 1503 1504 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask. 1505 if (N1.getOpcode() == ISD::UNDEF) 1506 commuteShuffle(N1, N2, MaskVec); 1507 1508 // Canonicalize all index into lhs, -> shuffle lhs, undef 1509 // Canonicalize all index into rhs, -> shuffle rhs, undef 1510 bool AllLHS = true, AllRHS = true; 1511 bool N2Undef = N2.getOpcode() == ISD::UNDEF; 1512 for (unsigned i = 0; i != NElts; ++i) { 1513 if (MaskVec[i] >= (int)NElts) { 1514 if (N2Undef) 1515 MaskVec[i] = -1; 1516 else 1517 AllLHS = false; 1518 } else if (MaskVec[i] >= 0) { 1519 AllRHS = false; 1520 } 1521 } 1522 if (AllLHS && AllRHS) 1523 return getUNDEF(VT); 1524 if (AllLHS && !N2Undef) 1525 N2 = getUNDEF(VT); 1526 if (AllRHS) { 1527 N1 = getUNDEF(VT); 1528 commuteShuffle(N1, N2, MaskVec); 1529 } 1530 // Reset our undef status after accounting for the mask. 1531 N2Undef = N2.getOpcode() == ISD::UNDEF; 1532 // Re-check whether both sides ended up undef. 1533 if (N1.getOpcode() == ISD::UNDEF && N2Undef) 1534 return getUNDEF(VT); 1535 1536 // If Identity shuffle return that node. 1537 bool Identity = true; 1538 for (unsigned i = 0; i != NElts; ++i) { 1539 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false; 1540 } 1541 if (Identity && NElts) 1542 return N1; 1543 1544 // Shuffling a constant splat doesn't change the result. 1545 if (N2Undef) { 1546 SDValue V = N1; 1547 1548 // Look through any bitcasts. We check that these don't change the number 1549 // (and size) of elements and just changes their types. 1550 while (V.getOpcode() == ISD::BITCAST) 1551 V = V->getOperand(0); 1552 1553 // A splat should always show up as a build vector node. 1554 if (auto *BV = dyn_cast<BuildVectorSDNode>(V)) { 1555 BitVector UndefElements; 1556 SDValue Splat = BV->getSplatValue(&UndefElements); 1557 // If this is a splat of an undef, shuffling it is also undef. 1558 if (Splat && Splat.getOpcode() == ISD::UNDEF) 1559 return getUNDEF(VT); 1560 1561 // We only have a splat which can skip shuffles if there is a splatted 1562 // value and no undef lanes rearranged by the shuffle. 1563 if (Splat && UndefElements.none()) { 1564 // Splat of <x, x, ..., x>, return <x, x, ..., x>, provided that the 1565 // number of elements match or the value splatted is a zero constant. 1566 if (V.getValueType().getVectorNumElements() == 1567 VT.getVectorNumElements()) 1568 return N1; 1569 if (auto *C = dyn_cast<ConstantSDNode>(Splat)) 1570 if (C->isNullValue()) 1571 return N1; 1572 } 1573 } 1574 } 1575 1576 FoldingSetNodeID ID; 1577 SDValue Ops[2] = { N1, N2 }; 1578 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops); 1579 for (unsigned i = 0; i != NElts; ++i) 1580 ID.AddInteger(MaskVec[i]); 1581 1582 void* IP = nullptr; 1583 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1584 return SDValue(E, 0); 1585 1586 // Allocate the mask array for the node out of the BumpPtrAllocator, since 1587 // SDNode doesn't have access to it. This memory will be "leaked" when 1588 // the node is deallocated, but recovered when the NodeAllocator is released. 1589 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts); 1590 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int)); 1591 1592 ShuffleVectorSDNode *N = 1593 new (NodeAllocator) ShuffleVectorSDNode(VT, dl.getIROrder(), 1594 dl.getDebugLoc(), N1, N2, 1595 MaskAlloc); 1596 CSEMap.InsertNode(N, IP); 1597 AllNodes.push_back(N); 1598 return SDValue(N, 0); 1599 } 1600 1601 SDValue SelectionDAG::getConvertRndSat(EVT VT, SDLoc dl, 1602 SDValue Val, SDValue DTy, 1603 SDValue STy, SDValue Rnd, SDValue Sat, 1604 ISD::CvtCode Code) { 1605 // If the src and dest types are the same and the conversion is between 1606 // integer types of the same sign or two floats, no conversion is necessary. 1607 if (DTy == STy && 1608 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF)) 1609 return Val; 1610 1611 FoldingSetNodeID ID; 1612 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat }; 1613 AddNodeIDNode(ID, ISD::CONVERT_RNDSAT, getVTList(VT), Ops); 1614 void* IP = nullptr; 1615 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1616 return SDValue(E, 0); 1617 1618 CvtRndSatSDNode *N = new (NodeAllocator) CvtRndSatSDNode(VT, dl.getIROrder(), 1619 dl.getDebugLoc(), 1620 Ops, Code); 1621 CSEMap.InsertNode(N, IP); 1622 AllNodes.push_back(N); 1623 return SDValue(N, 0); 1624 } 1625 1626 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) { 1627 FoldingSetNodeID ID; 1628 AddNodeIDNode(ID, ISD::Register, getVTList(VT), None); 1629 ID.AddInteger(RegNo); 1630 void *IP = nullptr; 1631 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1632 return SDValue(E, 0); 1633 1634 SDNode *N = new (NodeAllocator) RegisterSDNode(RegNo, VT); 1635 CSEMap.InsertNode(N, IP); 1636 AllNodes.push_back(N); 1637 return SDValue(N, 0); 1638 } 1639 1640 SDValue SelectionDAG::getRegisterMask(const uint32_t *RegMask) { 1641 FoldingSetNodeID ID; 1642 AddNodeIDNode(ID, ISD::RegisterMask, getVTList(MVT::Untyped), None); 1643 ID.AddPointer(RegMask); 1644 void *IP = nullptr; 1645 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1646 return SDValue(E, 0); 1647 1648 SDNode *N = new (NodeAllocator) RegisterMaskSDNode(RegMask); 1649 CSEMap.InsertNode(N, IP); 1650 AllNodes.push_back(N); 1651 return SDValue(N, 0); 1652 } 1653 1654 SDValue SelectionDAG::getEHLabel(SDLoc dl, SDValue Root, MCSymbol *Label) { 1655 FoldingSetNodeID ID; 1656 SDValue Ops[] = { Root }; 1657 AddNodeIDNode(ID, ISD::EH_LABEL, getVTList(MVT::Other), Ops); 1658 ID.AddPointer(Label); 1659 void *IP = nullptr; 1660 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1661 return SDValue(E, 0); 1662 1663 SDNode *N = new (NodeAllocator) EHLabelSDNode(dl.getIROrder(), 1664 dl.getDebugLoc(), Root, Label); 1665 CSEMap.InsertNode(N, IP); 1666 AllNodes.push_back(N); 1667 return SDValue(N, 0); 1668 } 1669 1670 1671 SDValue SelectionDAG::getBlockAddress(const BlockAddress *BA, EVT VT, 1672 int64_t Offset, 1673 bool isTarget, 1674 unsigned char TargetFlags) { 1675 unsigned Opc = isTarget ? ISD::TargetBlockAddress : ISD::BlockAddress; 1676 1677 FoldingSetNodeID ID; 1678 AddNodeIDNode(ID, Opc, getVTList(VT), None); 1679 ID.AddPointer(BA); 1680 ID.AddInteger(Offset); 1681 ID.AddInteger(TargetFlags); 1682 void *IP = nullptr; 1683 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1684 return SDValue(E, 0); 1685 1686 SDNode *N = new (NodeAllocator) BlockAddressSDNode(Opc, VT, BA, Offset, 1687 TargetFlags); 1688 CSEMap.InsertNode(N, IP); 1689 AllNodes.push_back(N); 1690 return SDValue(N, 0); 1691 } 1692 1693 SDValue SelectionDAG::getSrcValue(const Value *V) { 1694 assert((!V || V->getType()->isPointerTy()) && 1695 "SrcValue is not a pointer?"); 1696 1697 FoldingSetNodeID ID; 1698 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), None); 1699 ID.AddPointer(V); 1700 1701 void *IP = nullptr; 1702 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1703 return SDValue(E, 0); 1704 1705 SDNode *N = new (NodeAllocator) SrcValueSDNode(V); 1706 CSEMap.InsertNode(N, IP); 1707 AllNodes.push_back(N); 1708 return SDValue(N, 0); 1709 } 1710 1711 /// getMDNode - Return an MDNodeSDNode which holds an MDNode. 1712 SDValue SelectionDAG::getMDNode(const MDNode *MD) { 1713 FoldingSetNodeID ID; 1714 AddNodeIDNode(ID, ISD::MDNODE_SDNODE, getVTList(MVT::Other), None); 1715 ID.AddPointer(MD); 1716 1717 void *IP = nullptr; 1718 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1719 return SDValue(E, 0); 1720 1721 SDNode *N = new (NodeAllocator) MDNodeSDNode(MD); 1722 CSEMap.InsertNode(N, IP); 1723 AllNodes.push_back(N); 1724 return SDValue(N, 0); 1725 } 1726 1727 /// getAddrSpaceCast - Return an AddrSpaceCastSDNode. 1728 SDValue SelectionDAG::getAddrSpaceCast(SDLoc dl, EVT VT, SDValue Ptr, 1729 unsigned SrcAS, unsigned DestAS) { 1730 SDValue Ops[] = {Ptr}; 1731 FoldingSetNodeID ID; 1732 AddNodeIDNode(ID, ISD::ADDRSPACECAST, getVTList(VT), Ops); 1733 ID.AddInteger(SrcAS); 1734 ID.AddInteger(DestAS); 1735 1736 void *IP = nullptr; 1737 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 1738 return SDValue(E, 0); 1739 1740 SDNode *N = new (NodeAllocator) AddrSpaceCastSDNode(dl.getIROrder(), 1741 dl.getDebugLoc(), 1742 VT, Ptr, SrcAS, DestAS); 1743 CSEMap.InsertNode(N, IP); 1744 AllNodes.push_back(N); 1745 return SDValue(N, 0); 1746 } 1747 1748 /// getShiftAmountOperand - Return the specified value casted to 1749 /// the target's desired shift amount type. 1750 SDValue SelectionDAG::getShiftAmountOperand(EVT LHSTy, SDValue Op) { 1751 EVT OpTy = Op.getValueType(); 1752 EVT ShTy = TM.getTargetLowering()->getShiftAmountTy(LHSTy); 1753 if (OpTy == ShTy || OpTy.isVector()) return Op; 1754 1755 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND; 1756 return getNode(Opcode, SDLoc(Op), ShTy, Op); 1757 } 1758 1759 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 1760 /// specified value type. 1761 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) { 1762 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo(); 1763 unsigned ByteSize = VT.getStoreSize(); 1764 Type *Ty = VT.getTypeForEVT(*getContext()); 1765 const TargetLowering *TLI = TM.getTargetLowering(); 1766 unsigned StackAlign = 1767 std::max((unsigned)TLI->getDataLayout()->getPrefTypeAlignment(Ty), minAlign); 1768 1769 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign, false); 1770 return getFrameIndex(FrameIdx, TLI->getPointerTy()); 1771 } 1772 1773 /// CreateStackTemporary - Create a stack temporary suitable for holding 1774 /// either of the specified value types. 1775 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) { 1776 unsigned Bytes = std::max(VT1.getStoreSizeInBits(), 1777 VT2.getStoreSizeInBits())/8; 1778 Type *Ty1 = VT1.getTypeForEVT(*getContext()); 1779 Type *Ty2 = VT2.getTypeForEVT(*getContext()); 1780 const TargetLowering *TLI = TM.getTargetLowering(); 1781 const DataLayout *TD = TLI->getDataLayout(); 1782 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1), 1783 TD->getPrefTypeAlignment(Ty2)); 1784 1785 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo(); 1786 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align, false); 1787 return getFrameIndex(FrameIdx, TLI->getPointerTy()); 1788 } 1789 1790 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1, 1791 SDValue N2, ISD::CondCode Cond, SDLoc dl) { 1792 // These setcc operations always fold. 1793 switch (Cond) { 1794 default: break; 1795 case ISD::SETFALSE: 1796 case ISD::SETFALSE2: return getConstant(0, VT); 1797 case ISD::SETTRUE: 1798 case ISD::SETTRUE2: { 1799 const TargetLowering *TLI = TM.getTargetLowering(); 1800 TargetLowering::BooleanContent Cnt = 1801 TLI->getBooleanContents(N1->getValueType(0)); 1802 return getConstant( 1803 Cnt == TargetLowering::ZeroOrNegativeOneBooleanContent ? -1ULL : 1, VT); 1804 } 1805 1806 case ISD::SETOEQ: 1807 case ISD::SETOGT: 1808 case ISD::SETOGE: 1809 case ISD::SETOLT: 1810 case ISD::SETOLE: 1811 case ISD::SETONE: 1812 case ISD::SETO: 1813 case ISD::SETUO: 1814 case ISD::SETUEQ: 1815 case ISD::SETUNE: 1816 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!"); 1817 break; 1818 } 1819 1820 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) { 1821 const APInt &C2 = N2C->getAPIntValue(); 1822 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) { 1823 const APInt &C1 = N1C->getAPIntValue(); 1824 1825 switch (Cond) { 1826 default: llvm_unreachable("Unknown integer setcc!"); 1827 case ISD::SETEQ: return getConstant(C1 == C2, VT); 1828 case ISD::SETNE: return getConstant(C1 != C2, VT); 1829 case ISD::SETULT: return getConstant(C1.ult(C2), VT); 1830 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT); 1831 case ISD::SETULE: return getConstant(C1.ule(C2), VT); 1832 case ISD::SETUGE: return getConstant(C1.uge(C2), VT); 1833 case ISD::SETLT: return getConstant(C1.slt(C2), VT); 1834 case ISD::SETGT: return getConstant(C1.sgt(C2), VT); 1835 case ISD::SETLE: return getConstant(C1.sle(C2), VT); 1836 case ISD::SETGE: return getConstant(C1.sge(C2), VT); 1837 } 1838 } 1839 } 1840 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) { 1841 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) { 1842 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF()); 1843 switch (Cond) { 1844 default: break; 1845 case ISD::SETEQ: if (R==APFloat::cmpUnordered) 1846 return getUNDEF(VT); 1847 // fall through 1848 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT); 1849 case ISD::SETNE: if (R==APFloat::cmpUnordered) 1850 return getUNDEF(VT); 1851 // fall through 1852 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan || 1853 R==APFloat::cmpLessThan, VT); 1854 case ISD::SETLT: if (R==APFloat::cmpUnordered) 1855 return getUNDEF(VT); 1856 // fall through 1857 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT); 1858 case ISD::SETGT: if (R==APFloat::cmpUnordered) 1859 return getUNDEF(VT); 1860 // fall through 1861 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT); 1862 case ISD::SETLE: if (R==APFloat::cmpUnordered) 1863 return getUNDEF(VT); 1864 // fall through 1865 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan || 1866 R==APFloat::cmpEqual, VT); 1867 case ISD::SETGE: if (R==APFloat::cmpUnordered) 1868 return getUNDEF(VT); 1869 // fall through 1870 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan || 1871 R==APFloat::cmpEqual, VT); 1872 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT); 1873 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT); 1874 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered || 1875 R==APFloat::cmpEqual, VT); 1876 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT); 1877 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered || 1878 R==APFloat::cmpLessThan, VT); 1879 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan || 1880 R==APFloat::cmpUnordered, VT); 1881 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT); 1882 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT); 1883 } 1884 } else { 1885 // Ensure that the constant occurs on the RHS. 1886 ISD::CondCode SwappedCond = ISD::getSetCCSwappedOperands(Cond); 1887 MVT CompVT = N1.getValueType().getSimpleVT(); 1888 if (!TM.getTargetLowering()->isCondCodeLegal(SwappedCond, CompVT)) 1889 return SDValue(); 1890 1891 return getSetCC(dl, VT, N2, N1, SwappedCond); 1892 } 1893 } 1894 1895 // Could not fold it. 1896 return SDValue(); 1897 } 1898 1899 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 1900 /// use this predicate to simplify operations downstream. 1901 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const { 1902 // This predicate is not safe for vector operations. 1903 if (Op.getValueType().isVector()) 1904 return false; 1905 1906 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits(); 1907 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth); 1908 } 1909 1910 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 1911 /// this predicate to simplify operations downstream. Mask is known to be zero 1912 /// for bits that V cannot have. 1913 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask, 1914 unsigned Depth) const { 1915 APInt KnownZero, KnownOne; 1916 computeKnownBits(Op, KnownZero, KnownOne, Depth); 1917 return (KnownZero & Mask) == Mask; 1918 } 1919 1920 /// Determine which bits of Op are known to be either zero or one and return 1921 /// them in the KnownZero/KnownOne bitsets. 1922 void SelectionDAG::computeKnownBits(SDValue Op, APInt &KnownZero, 1923 APInt &KnownOne, unsigned Depth) const { 1924 const TargetLowering *TLI = TM.getTargetLowering(); 1925 unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits(); 1926 1927 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything. 1928 if (Depth == 6) 1929 return; // Limit search depth. 1930 1931 APInt KnownZero2, KnownOne2; 1932 1933 switch (Op.getOpcode()) { 1934 case ISD::Constant: 1935 // We know all of the bits for a constant! 1936 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue(); 1937 KnownZero = ~KnownOne; 1938 break; 1939 case ISD::AND: 1940 // If either the LHS or the RHS are Zero, the result is zero. 1941 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1); 1942 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1); 1943 1944 // Output known-1 bits are only known if set in both the LHS & RHS. 1945 KnownOne &= KnownOne2; 1946 // Output known-0 are known to be clear if zero in either the LHS | RHS. 1947 KnownZero |= KnownZero2; 1948 break; 1949 case ISD::OR: 1950 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1); 1951 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1); 1952 1953 // Output known-0 bits are only known if clear in both the LHS & RHS. 1954 KnownZero &= KnownZero2; 1955 // Output known-1 are known to be set if set in either the LHS | RHS. 1956 KnownOne |= KnownOne2; 1957 break; 1958 case ISD::XOR: { 1959 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1); 1960 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1); 1961 1962 // Output known-0 bits are known if clear or set in both the LHS & RHS. 1963 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 1964 // Output known-1 are known to be set if set in only one of the LHS, RHS. 1965 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 1966 KnownZero = KnownZeroOut; 1967 break; 1968 } 1969 case ISD::MUL: { 1970 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1); 1971 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1); 1972 1973 // If low bits are zero in either operand, output low known-0 bits. 1974 // Also compute a conserative estimate for high known-0 bits. 1975 // More trickiness is possible, but this is sufficient for the 1976 // interesting case of alignment computation. 1977 KnownOne.clearAllBits(); 1978 unsigned TrailZ = KnownZero.countTrailingOnes() + 1979 KnownZero2.countTrailingOnes(); 1980 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 1981 KnownZero2.countLeadingOnes(), 1982 BitWidth) - BitWidth; 1983 1984 TrailZ = std::min(TrailZ, BitWidth); 1985 LeadZ = std::min(LeadZ, BitWidth); 1986 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 1987 APInt::getHighBitsSet(BitWidth, LeadZ); 1988 break; 1989 } 1990 case ISD::UDIV: { 1991 // For the purposes of computing leading zeros we can conservatively 1992 // treat a udiv as a logical right shift by the power of 2 known to 1993 // be less than the denominator. 1994 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1); 1995 unsigned LeadZ = KnownZero2.countLeadingOnes(); 1996 1997 KnownOne2.clearAllBits(); 1998 KnownZero2.clearAllBits(); 1999 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1); 2000 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 2001 if (RHSUnknownLeadingOnes != BitWidth) 2002 LeadZ = std::min(BitWidth, 2003 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 2004 2005 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ); 2006 break; 2007 } 2008 case ISD::SELECT: 2009 computeKnownBits(Op.getOperand(2), KnownZero, KnownOne, Depth+1); 2010 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1); 2011 2012 // Only known if known in both the LHS and RHS. 2013 KnownOne &= KnownOne2; 2014 KnownZero &= KnownZero2; 2015 break; 2016 case ISD::SELECT_CC: 2017 computeKnownBits(Op.getOperand(3), KnownZero, KnownOne, Depth+1); 2018 computeKnownBits(Op.getOperand(2), KnownZero2, KnownOne2, Depth+1); 2019 2020 // Only known if known in both the LHS and RHS. 2021 KnownOne &= KnownOne2; 2022 KnownZero &= KnownZero2; 2023 break; 2024 case ISD::SADDO: 2025 case ISD::UADDO: 2026 case ISD::SSUBO: 2027 case ISD::USUBO: 2028 case ISD::SMULO: 2029 case ISD::UMULO: 2030 if (Op.getResNo() != 1) 2031 break; 2032 // The boolean result conforms to getBooleanContents. 2033 // If we know the result of a setcc has the top bits zero, use this info. 2034 // We know that we have an integer-based boolean since these operations 2035 // are only available for integer. 2036 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) == 2037 TargetLowering::ZeroOrOneBooleanContent && 2038 BitWidth > 1) 2039 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1); 2040 break; 2041 case ISD::SETCC: 2042 // If we know the result of a setcc has the top bits zero, use this info. 2043 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) == 2044 TargetLowering::ZeroOrOneBooleanContent && 2045 BitWidth > 1) 2046 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1); 2047 break; 2048 case ISD::SHL: 2049 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 2050 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2051 unsigned ShAmt = SA->getZExtValue(); 2052 2053 // If the shift count is an invalid immediate, don't do anything. 2054 if (ShAmt >= BitWidth) 2055 break; 2056 2057 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2058 KnownZero <<= ShAmt; 2059 KnownOne <<= ShAmt; 2060 // low bits known zero. 2061 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt); 2062 } 2063 break; 2064 case ISD::SRL: 2065 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 2066 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2067 unsigned ShAmt = SA->getZExtValue(); 2068 2069 // If the shift count is an invalid immediate, don't do anything. 2070 if (ShAmt >= BitWidth) 2071 break; 2072 2073 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2074 KnownZero = KnownZero.lshr(ShAmt); 2075 KnownOne = KnownOne.lshr(ShAmt); 2076 2077 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt); 2078 KnownZero |= HighBits; // High bits known zero. 2079 } 2080 break; 2081 case ISD::SRA: 2082 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2083 unsigned ShAmt = SA->getZExtValue(); 2084 2085 // If the shift count is an invalid immediate, don't do anything. 2086 if (ShAmt >= BitWidth) 2087 break; 2088 2089 // If any of the demanded bits are produced by the sign extension, we also 2090 // demand the input sign bit. 2091 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt); 2092 2093 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2094 KnownZero = KnownZero.lshr(ShAmt); 2095 KnownOne = KnownOne.lshr(ShAmt); 2096 2097 // Handle the sign bits. 2098 APInt SignBit = APInt::getSignBit(BitWidth); 2099 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask. 2100 2101 if (KnownZero.intersects(SignBit)) { 2102 KnownZero |= HighBits; // New bits are known zero. 2103 } else if (KnownOne.intersects(SignBit)) { 2104 KnownOne |= HighBits; // New bits are known one. 2105 } 2106 } 2107 break; 2108 case ISD::SIGN_EXTEND_INREG: { 2109 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 2110 unsigned EBits = EVT.getScalarType().getSizeInBits(); 2111 2112 // Sign extension. Compute the demanded bits in the result that are not 2113 // present in the input. 2114 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits); 2115 2116 APInt InSignBit = APInt::getSignBit(EBits); 2117 APInt InputDemandedBits = APInt::getLowBitsSet(BitWidth, EBits); 2118 2119 // If the sign extended bits are demanded, we know that the sign 2120 // bit is demanded. 2121 InSignBit = InSignBit.zext(BitWidth); 2122 if (NewBits.getBoolValue()) 2123 InputDemandedBits |= InSignBit; 2124 2125 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2126 KnownOne &= InputDemandedBits; 2127 KnownZero &= InputDemandedBits; 2128 2129 // If the sign bit of the input is known set or clear, then we know the 2130 // top bits of the result. 2131 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear 2132 KnownZero |= NewBits; 2133 KnownOne &= ~NewBits; 2134 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set 2135 KnownOne |= NewBits; 2136 KnownZero &= ~NewBits; 2137 } else { // Input sign bit unknown 2138 KnownZero &= ~NewBits; 2139 KnownOne &= ~NewBits; 2140 } 2141 break; 2142 } 2143 case ISD::CTTZ: 2144 case ISD::CTTZ_ZERO_UNDEF: 2145 case ISD::CTLZ: 2146 case ISD::CTLZ_ZERO_UNDEF: 2147 case ISD::CTPOP: { 2148 unsigned LowBits = Log2_32(BitWidth)+1; 2149 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 2150 KnownOne.clearAllBits(); 2151 break; 2152 } 2153 case ISD::LOAD: { 2154 LoadSDNode *LD = cast<LoadSDNode>(Op); 2155 // If this is a ZEXTLoad and we are looking at the loaded value. 2156 if (ISD::isZEXTLoad(Op.getNode()) && Op.getResNo() == 0) { 2157 EVT VT = LD->getMemoryVT(); 2158 unsigned MemBits = VT.getScalarType().getSizeInBits(); 2159 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits); 2160 } else if (const MDNode *Ranges = LD->getRanges()) { 2161 computeKnownBitsFromRangeMetadata(*Ranges, KnownZero); 2162 } 2163 break; 2164 } 2165 case ISD::ZERO_EXTEND: { 2166 EVT InVT = Op.getOperand(0).getValueType(); 2167 unsigned InBits = InVT.getScalarType().getSizeInBits(); 2168 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits); 2169 KnownZero = KnownZero.trunc(InBits); 2170 KnownOne = KnownOne.trunc(InBits); 2171 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2172 KnownZero = KnownZero.zext(BitWidth); 2173 KnownOne = KnownOne.zext(BitWidth); 2174 KnownZero |= NewBits; 2175 break; 2176 } 2177 case ISD::SIGN_EXTEND: { 2178 EVT InVT = Op.getOperand(0).getValueType(); 2179 unsigned InBits = InVT.getScalarType().getSizeInBits(); 2180 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits); 2181 2182 KnownZero = KnownZero.trunc(InBits); 2183 KnownOne = KnownOne.trunc(InBits); 2184 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2185 2186 // Note if the sign bit is known to be zero or one. 2187 bool SignBitKnownZero = KnownZero.isNegative(); 2188 bool SignBitKnownOne = KnownOne.isNegative(); 2189 2190 KnownZero = KnownZero.zext(BitWidth); 2191 KnownOne = KnownOne.zext(BitWidth); 2192 2193 // If the sign bit is known zero or one, the top bits match. 2194 if (SignBitKnownZero) 2195 KnownZero |= NewBits; 2196 else if (SignBitKnownOne) 2197 KnownOne |= NewBits; 2198 break; 2199 } 2200 case ISD::ANY_EXTEND: { 2201 EVT InVT = Op.getOperand(0).getValueType(); 2202 unsigned InBits = InVT.getScalarType().getSizeInBits(); 2203 KnownZero = KnownZero.trunc(InBits); 2204 KnownOne = KnownOne.trunc(InBits); 2205 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2206 KnownZero = KnownZero.zext(BitWidth); 2207 KnownOne = KnownOne.zext(BitWidth); 2208 break; 2209 } 2210 case ISD::TRUNCATE: { 2211 EVT InVT = Op.getOperand(0).getValueType(); 2212 unsigned InBits = InVT.getScalarType().getSizeInBits(); 2213 KnownZero = KnownZero.zext(InBits); 2214 KnownOne = KnownOne.zext(InBits); 2215 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2216 KnownZero = KnownZero.trunc(BitWidth); 2217 KnownOne = KnownOne.trunc(BitWidth); 2218 break; 2219 } 2220 case ISD::AssertZext: { 2221 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 2222 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits()); 2223 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2224 KnownZero |= (~InMask); 2225 KnownOne &= (~KnownZero); 2226 break; 2227 } 2228 case ISD::FGETSIGN: 2229 // All bits are zero except the low bit. 2230 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1); 2231 break; 2232 2233 case ISD::SUB: { 2234 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) { 2235 // We know that the top bits of C-X are clear if X contains less bits 2236 // than C (i.e. no wrap-around can happen). For example, 20-X is 2237 // positive if we can prove that X is >= 0 and < 16. 2238 if (CLHS->getAPIntValue().isNonNegative()) { 2239 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros(); 2240 // NLZ can't be BitWidth with no sign bit 2241 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 2242 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1); 2243 2244 // If all of the MaskV bits are known to be zero, then we know the 2245 // output top bits are zero, because we now know that the output is 2246 // from [0-C]. 2247 if ((KnownZero2 & MaskV) == MaskV) { 2248 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros(); 2249 // Top bits known zero. 2250 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2); 2251 } 2252 } 2253 } 2254 } 2255 // fall through 2256 case ISD::ADD: 2257 case ISD::ADDE: { 2258 // Output known-0 bits are known if clear or set in both the low clear bits 2259 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the 2260 // low 3 bits clear. 2261 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth+1); 2262 unsigned KnownZeroOut = KnownZero2.countTrailingOnes(); 2263 2264 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1); 2265 KnownZeroOut = std::min(KnownZeroOut, 2266 KnownZero2.countTrailingOnes()); 2267 2268 if (Op.getOpcode() == ISD::ADD) { 2269 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut); 2270 break; 2271 } 2272 2273 // With ADDE, a carry bit may be added in, so we can only use this 2274 // information if we know (at least) that the low two bits are clear. We 2275 // then return to the caller that the low bit is unknown but that other bits 2276 // are known zero. 2277 if (KnownZeroOut >= 2) // ADDE 2278 KnownZero |= APInt::getBitsSet(BitWidth, 1, KnownZeroOut); 2279 break; 2280 } 2281 case ISD::SREM: 2282 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2283 const APInt &RA = Rem->getAPIntValue().abs(); 2284 if (RA.isPowerOf2()) { 2285 APInt LowBits = RA - 1; 2286 computeKnownBits(Op.getOperand(0), KnownZero2,KnownOne2,Depth+1); 2287 2288 // The low bits of the first operand are unchanged by the srem. 2289 KnownZero = KnownZero2 & LowBits; 2290 KnownOne = KnownOne2 & LowBits; 2291 2292 // If the first operand is non-negative or has all low bits zero, then 2293 // the upper bits are all zero. 2294 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 2295 KnownZero |= ~LowBits; 2296 2297 // If the first operand is negative and not all low bits are zero, then 2298 // the upper bits are all one. 2299 if (KnownOne2[BitWidth-1] && ((KnownOne2 & LowBits) != 0)) 2300 KnownOne |= ~LowBits; 2301 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 2302 } 2303 } 2304 break; 2305 case ISD::UREM: { 2306 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2307 const APInt &RA = Rem->getAPIntValue(); 2308 if (RA.isPowerOf2()) { 2309 APInt LowBits = (RA - 1); 2310 computeKnownBits(Op.getOperand(0), KnownZero2, KnownOne2, Depth + 1); 2311 2312 // The upper bits are all zero, the lower ones are unchanged. 2313 KnownZero = KnownZero2 | ~LowBits; 2314 KnownOne = KnownOne2 & LowBits; 2315 break; 2316 } 2317 } 2318 2319 // Since the result is less than or equal to either operand, any leading 2320 // zero bits in either operand must also exist in the result. 2321 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2322 computeKnownBits(Op.getOperand(1), KnownZero2, KnownOne2, Depth+1); 2323 2324 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(), 2325 KnownZero2.countLeadingOnes()); 2326 KnownOne.clearAllBits(); 2327 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders); 2328 break; 2329 } 2330 case ISD::FrameIndex: 2331 case ISD::TargetFrameIndex: 2332 if (unsigned Align = InferPtrAlignment(Op)) { 2333 // The low bits are known zero if the pointer is aligned. 2334 KnownZero = APInt::getLowBitsSet(BitWidth, Log2_32(Align)); 2335 break; 2336 } 2337 break; 2338 2339 default: 2340 if (Op.getOpcode() < ISD::BUILTIN_OP_END) 2341 break; 2342 // Fallthrough 2343 case ISD::INTRINSIC_WO_CHAIN: 2344 case ISD::INTRINSIC_W_CHAIN: 2345 case ISD::INTRINSIC_VOID: 2346 // Allow the target to implement this method for its nodes. 2347 TLI->computeKnownBitsForTargetNode(Op, KnownZero, KnownOne, *this, Depth); 2348 break; 2349 } 2350 2351 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 2352 } 2353 2354 /// ComputeNumSignBits - Return the number of times the sign bit of the 2355 /// register is replicated into the other bits. We know that at least 1 bit 2356 /// is always equal to the sign bit (itself), but other cases can give us 2357 /// information. For example, immediately after an "SRA X, 2", we know that 2358 /// the top 3 bits are all equal to each other, so we return 3. 2359 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{ 2360 const TargetLowering *TLI = TM.getTargetLowering(); 2361 EVT VT = Op.getValueType(); 2362 assert(VT.isInteger() && "Invalid VT!"); 2363 unsigned VTBits = VT.getScalarType().getSizeInBits(); 2364 unsigned Tmp, Tmp2; 2365 unsigned FirstAnswer = 1; 2366 2367 if (Depth == 6) 2368 return 1; // Limit search depth. 2369 2370 switch (Op.getOpcode()) { 2371 default: break; 2372 case ISD::AssertSext: 2373 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits(); 2374 return VTBits-Tmp+1; 2375 case ISD::AssertZext: 2376 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits(); 2377 return VTBits-Tmp; 2378 2379 case ISD::Constant: { 2380 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue(); 2381 return Val.getNumSignBits(); 2382 } 2383 2384 case ISD::SIGN_EXTEND: 2385 Tmp = 2386 VTBits-Op.getOperand(0).getValueType().getScalarType().getSizeInBits(); 2387 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp; 2388 2389 case ISD::SIGN_EXTEND_INREG: 2390 // Max of the input and what this extends. 2391 Tmp = 2392 cast<VTSDNode>(Op.getOperand(1))->getVT().getScalarType().getSizeInBits(); 2393 Tmp = VTBits-Tmp+1; 2394 2395 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2396 return std::max(Tmp, Tmp2); 2397 2398 case ISD::SRA: 2399 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2400 // SRA X, C -> adds C sign bits. 2401 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2402 Tmp += C->getZExtValue(); 2403 if (Tmp > VTBits) Tmp = VTBits; 2404 } 2405 return Tmp; 2406 case ISD::SHL: 2407 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2408 // shl destroys sign bits. 2409 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2410 if (C->getZExtValue() >= VTBits || // Bad shift. 2411 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out. 2412 return Tmp - C->getZExtValue(); 2413 } 2414 break; 2415 case ISD::AND: 2416 case ISD::OR: 2417 case ISD::XOR: // NOT is handled here. 2418 // Logical binary ops preserve the number of sign bits at the worst. 2419 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2420 if (Tmp != 1) { 2421 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 2422 FirstAnswer = std::min(Tmp, Tmp2); 2423 // We computed what we know about the sign bits as our first 2424 // answer. Now proceed to the generic code that uses 2425 // computeKnownBits, and pick whichever answer is better. 2426 } 2427 break; 2428 2429 case ISD::SELECT: 2430 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1); 2431 if (Tmp == 1) return 1; // Early out. 2432 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1); 2433 return std::min(Tmp, Tmp2); 2434 2435 case ISD::SADDO: 2436 case ISD::UADDO: 2437 case ISD::SSUBO: 2438 case ISD::USUBO: 2439 case ISD::SMULO: 2440 case ISD::UMULO: 2441 if (Op.getResNo() != 1) 2442 break; 2443 // The boolean result conforms to getBooleanContents. Fall through. 2444 // If setcc returns 0/-1, all bits are sign bits. 2445 // We know that we have an integer-based boolean since these operations 2446 // are only available for integer. 2447 if (TLI->getBooleanContents(Op.getValueType().isVector(), false) == 2448 TargetLowering::ZeroOrNegativeOneBooleanContent) 2449 return VTBits; 2450 break; 2451 case ISD::SETCC: 2452 // If setcc returns 0/-1, all bits are sign bits. 2453 if (TLI->getBooleanContents(Op.getOperand(0).getValueType()) == 2454 TargetLowering::ZeroOrNegativeOneBooleanContent) 2455 return VTBits; 2456 break; 2457 case ISD::ROTL: 2458 case ISD::ROTR: 2459 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 2460 unsigned RotAmt = C->getZExtValue() & (VTBits-1); 2461 2462 // Handle rotate right by N like a rotate left by 32-N. 2463 if (Op.getOpcode() == ISD::ROTR) 2464 RotAmt = (VTBits-RotAmt) & (VTBits-1); 2465 2466 // If we aren't rotating out all of the known-in sign bits, return the 2467 // number that are left. This handles rotl(sext(x), 1) for example. 2468 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2469 if (Tmp > RotAmt+1) return Tmp-RotAmt; 2470 } 2471 break; 2472 case ISD::ADD: 2473 // Add can have at most one carry bit. Thus we know that the output 2474 // is, at worst, one more bit than the inputs. 2475 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2476 if (Tmp == 1) return 1; // Early out. 2477 2478 // Special case decrementing a value (ADD X, -1): 2479 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 2480 if (CRHS->isAllOnesValue()) { 2481 APInt KnownZero, KnownOne; 2482 computeKnownBits(Op.getOperand(0), KnownZero, KnownOne, Depth+1); 2483 2484 // If the input is known to be 0 or 1, the output is 0/-1, which is all 2485 // sign bits set. 2486 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue()) 2487 return VTBits; 2488 2489 // If we are subtracting one from a positive number, there is no carry 2490 // out of the result. 2491 if (KnownZero.isNegative()) 2492 return Tmp; 2493 } 2494 2495 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 2496 if (Tmp2 == 1) return 1; 2497 return std::min(Tmp, Tmp2)-1; 2498 2499 case ISD::SUB: 2500 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 2501 if (Tmp2 == 1) return 1; 2502 2503 // Handle NEG. 2504 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) 2505 if (CLHS->isNullValue()) { 2506 APInt KnownZero, KnownOne; 2507 computeKnownBits(Op.getOperand(1), KnownZero, KnownOne, Depth+1); 2508 // If the input is known to be 0 or 1, the output is 0/-1, which is all 2509 // sign bits set. 2510 if ((KnownZero | APInt(VTBits, 1)).isAllOnesValue()) 2511 return VTBits; 2512 2513 // If the input is known to be positive (the sign bit is known clear), 2514 // the output of the NEG has the same number of sign bits as the input. 2515 if (KnownZero.isNegative()) 2516 return Tmp2; 2517 2518 // Otherwise, we treat this like a SUB. 2519 } 2520 2521 // Sub can have at most one carry bit. Thus we know that the output 2522 // is, at worst, one more bit than the inputs. 2523 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 2524 if (Tmp == 1) return 1; // Early out. 2525 return std::min(Tmp, Tmp2)-1; 2526 case ISD::TRUNCATE: 2527 // FIXME: it's tricky to do anything useful for this, but it is an important 2528 // case for targets like X86. 2529 break; 2530 } 2531 2532 // If we are looking at the loaded value of the SDNode. 2533 if (Op.getResNo() == 0) { 2534 // Handle LOADX separately here. EXTLOAD case will fallthrough. 2535 if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op)) { 2536 unsigned ExtType = LD->getExtensionType(); 2537 switch (ExtType) { 2538 default: break; 2539 case ISD::SEXTLOAD: // '17' bits known 2540 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits(); 2541 return VTBits-Tmp+1; 2542 case ISD::ZEXTLOAD: // '16' bits known 2543 Tmp = LD->getMemoryVT().getScalarType().getSizeInBits(); 2544 return VTBits-Tmp; 2545 } 2546 } 2547 } 2548 2549 // Allow the target to implement this method for its nodes. 2550 if (Op.getOpcode() >= ISD::BUILTIN_OP_END || 2551 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 2552 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 2553 Op.getOpcode() == ISD::INTRINSIC_VOID) { 2554 unsigned NumBits = TLI->ComputeNumSignBitsForTargetNode(Op, *this, Depth); 2555 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits); 2556 } 2557 2558 // Finally, if we can prove that the top bits of the result are 0's or 1's, 2559 // use this information. 2560 APInt KnownZero, KnownOne; 2561 computeKnownBits(Op, KnownZero, KnownOne, Depth); 2562 2563 APInt Mask; 2564 if (KnownZero.isNegative()) { // sign bit is 0 2565 Mask = KnownZero; 2566 } else if (KnownOne.isNegative()) { // sign bit is 1; 2567 Mask = KnownOne; 2568 } else { 2569 // Nothing known. 2570 return FirstAnswer; 2571 } 2572 2573 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 2574 // the number of identical bits in the top of the input value. 2575 Mask = ~Mask; 2576 Mask <<= Mask.getBitWidth()-VTBits; 2577 // Return # leading zeros. We use 'min' here in case Val was zero before 2578 // shifting. We don't want to return '64' as for an i32 "0". 2579 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros())); 2580 } 2581 2582 /// isBaseWithConstantOffset - Return true if the specified operand is an 2583 /// ISD::ADD with a ConstantSDNode on the right-hand side, or if it is an 2584 /// ISD::OR with a ConstantSDNode that is guaranteed to have the same 2585 /// semantics as an ADD. This handles the equivalence: 2586 /// X|Cst == X+Cst iff X&Cst = 0. 2587 bool SelectionDAG::isBaseWithConstantOffset(SDValue Op) const { 2588 if ((Op.getOpcode() != ISD::ADD && Op.getOpcode() != ISD::OR) || 2589 !isa<ConstantSDNode>(Op.getOperand(1))) 2590 return false; 2591 2592 if (Op.getOpcode() == ISD::OR && 2593 !MaskedValueIsZero(Op.getOperand(0), 2594 cast<ConstantSDNode>(Op.getOperand(1))->getAPIntValue())) 2595 return false; 2596 2597 return true; 2598 } 2599 2600 2601 bool SelectionDAG::isKnownNeverNaN(SDValue Op) const { 2602 // If we're told that NaNs won't happen, assume they won't. 2603 if (getTarget().Options.NoNaNsFPMath) 2604 return true; 2605 2606 // If the value is a constant, we can obviously see if it is a NaN or not. 2607 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op)) 2608 return !C->getValueAPF().isNaN(); 2609 2610 // TODO: Recognize more cases here. 2611 2612 return false; 2613 } 2614 2615 bool SelectionDAG::isKnownNeverZero(SDValue Op) const { 2616 // If the value is a constant, we can obviously see if it is a zero or not. 2617 if (const ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Op)) 2618 return !C->isZero(); 2619 2620 // TODO: Recognize more cases here. 2621 switch (Op.getOpcode()) { 2622 default: break; 2623 case ISD::OR: 2624 if (const ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 2625 return !C->isNullValue(); 2626 break; 2627 } 2628 2629 return false; 2630 } 2631 2632 bool SelectionDAG::isEqualTo(SDValue A, SDValue B) const { 2633 // Check the obvious case. 2634 if (A == B) return true; 2635 2636 // For for negative and positive zero. 2637 if (const ConstantFPSDNode *CA = dyn_cast<ConstantFPSDNode>(A)) 2638 if (const ConstantFPSDNode *CB = dyn_cast<ConstantFPSDNode>(B)) 2639 if (CA->isZero() && CB->isZero()) return true; 2640 2641 // Otherwise they may not be equal. 2642 return false; 2643 } 2644 2645 /// getNode - Gets or creates the specified node. 2646 /// 2647 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT) { 2648 FoldingSetNodeID ID; 2649 AddNodeIDNode(ID, Opcode, getVTList(VT), None); 2650 void *IP = nullptr; 2651 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2652 return SDValue(E, 0); 2653 2654 SDNode *N = new (NodeAllocator) SDNode(Opcode, DL.getIROrder(), 2655 DL.getDebugLoc(), getVTList(VT)); 2656 CSEMap.InsertNode(N, IP); 2657 2658 AllNodes.push_back(N); 2659 #ifndef NDEBUG 2660 VerifySDNode(N); 2661 #endif 2662 return SDValue(N, 0); 2663 } 2664 2665 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, 2666 EVT VT, SDValue Operand) { 2667 // Constant fold unary operations with an integer constant operand. Even 2668 // opaque constant will be folded, because the folding of unary operations 2669 // doesn't create new constants with different values. Nevertheless, the 2670 // opaque flag is preserved during folding to prevent future folding with 2671 // other constants. 2672 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) { 2673 const APInt &Val = C->getAPIntValue(); 2674 switch (Opcode) { 2675 default: break; 2676 case ISD::SIGN_EXTEND: 2677 return getConstant(Val.sextOrTrunc(VT.getSizeInBits()), VT, 2678 C->isTargetOpcode(), C->isOpaque()); 2679 case ISD::ANY_EXTEND: 2680 case ISD::ZERO_EXTEND: 2681 case ISD::TRUNCATE: 2682 return getConstant(Val.zextOrTrunc(VT.getSizeInBits()), VT, 2683 C->isTargetOpcode(), C->isOpaque()); 2684 case ISD::UINT_TO_FP: 2685 case ISD::SINT_TO_FP: { 2686 APFloat apf(EVTToAPFloatSemantics(VT), 2687 APInt::getNullValue(VT.getSizeInBits())); 2688 (void)apf.convertFromAPInt(Val, 2689 Opcode==ISD::SINT_TO_FP, 2690 APFloat::rmNearestTiesToEven); 2691 return getConstantFP(apf, VT); 2692 } 2693 case ISD::BITCAST: 2694 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32) 2695 return getConstantFP(APFloat(APFloat::IEEEsingle, Val), VT); 2696 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64) 2697 return getConstantFP(APFloat(APFloat::IEEEdouble, Val), VT); 2698 break; 2699 case ISD::BSWAP: 2700 return getConstant(Val.byteSwap(), VT, C->isTargetOpcode(), 2701 C->isOpaque()); 2702 case ISD::CTPOP: 2703 return getConstant(Val.countPopulation(), VT, C->isTargetOpcode(), 2704 C->isOpaque()); 2705 case ISD::CTLZ: 2706 case ISD::CTLZ_ZERO_UNDEF: 2707 return getConstant(Val.countLeadingZeros(), VT, C->isTargetOpcode(), 2708 C->isOpaque()); 2709 case ISD::CTTZ: 2710 case ISD::CTTZ_ZERO_UNDEF: 2711 return getConstant(Val.countTrailingZeros(), VT, C->isTargetOpcode(), 2712 C->isOpaque()); 2713 } 2714 } 2715 2716 // Constant fold unary operations with a floating point constant operand. 2717 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) { 2718 APFloat V = C->getValueAPF(); // make copy 2719 switch (Opcode) { 2720 case ISD::FNEG: 2721 V.changeSign(); 2722 return getConstantFP(V, VT); 2723 case ISD::FABS: 2724 V.clearSign(); 2725 return getConstantFP(V, VT); 2726 case ISD::FCEIL: { 2727 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardPositive); 2728 if (fs == APFloat::opOK || fs == APFloat::opInexact) 2729 return getConstantFP(V, VT); 2730 break; 2731 } 2732 case ISD::FTRUNC: { 2733 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardZero); 2734 if (fs == APFloat::opOK || fs == APFloat::opInexact) 2735 return getConstantFP(V, VT); 2736 break; 2737 } 2738 case ISD::FFLOOR: { 2739 APFloat::opStatus fs = V.roundToIntegral(APFloat::rmTowardNegative); 2740 if (fs == APFloat::opOK || fs == APFloat::opInexact) 2741 return getConstantFP(V, VT); 2742 break; 2743 } 2744 case ISD::FP_EXTEND: { 2745 bool ignored; 2746 // This can return overflow, underflow, or inexact; we don't care. 2747 // FIXME need to be more flexible about rounding mode. 2748 (void)V.convert(EVTToAPFloatSemantics(VT), 2749 APFloat::rmNearestTiesToEven, &ignored); 2750 return getConstantFP(V, VT); 2751 } 2752 case ISD::FP_TO_SINT: 2753 case ISD::FP_TO_UINT: { 2754 integerPart x[2]; 2755 bool ignored; 2756 assert(integerPartWidth >= 64); 2757 // FIXME need to be more flexible about rounding mode. 2758 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(), 2759 Opcode==ISD::FP_TO_SINT, 2760 APFloat::rmTowardZero, &ignored); 2761 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual 2762 break; 2763 APInt api(VT.getSizeInBits(), x); 2764 return getConstant(api, VT); 2765 } 2766 case ISD::BITCAST: 2767 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32) 2768 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT); 2769 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64) 2770 return getConstant(V.bitcastToAPInt().getZExtValue(), VT); 2771 break; 2772 } 2773 } 2774 2775 unsigned OpOpcode = Operand.getNode()->getOpcode(); 2776 switch (Opcode) { 2777 case ISD::TokenFactor: 2778 case ISD::MERGE_VALUES: 2779 case ISD::CONCAT_VECTORS: 2780 return Operand; // Factor, merge or concat of one node? No need. 2781 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node"); 2782 case ISD::FP_EXTEND: 2783 assert(VT.isFloatingPoint() && 2784 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!"); 2785 if (Operand.getValueType() == VT) return Operand; // noop conversion. 2786 assert((!VT.isVector() || 2787 VT.getVectorNumElements() == 2788 Operand.getValueType().getVectorNumElements()) && 2789 "Vector element count mismatch!"); 2790 if (Operand.getOpcode() == ISD::UNDEF) 2791 return getUNDEF(VT); 2792 break; 2793 case ISD::SIGN_EXTEND: 2794 assert(VT.isInteger() && Operand.getValueType().isInteger() && 2795 "Invalid SIGN_EXTEND!"); 2796 if (Operand.getValueType() == VT) return Operand; // noop extension 2797 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) && 2798 "Invalid sext node, dst < src!"); 2799 assert((!VT.isVector() || 2800 VT.getVectorNumElements() == 2801 Operand.getValueType().getVectorNumElements()) && 2802 "Vector element count mismatch!"); 2803 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 2804 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0)); 2805 else if (OpOpcode == ISD::UNDEF) 2806 // sext(undef) = 0, because the top bits will all be the same. 2807 return getConstant(0, VT); 2808 break; 2809 case ISD::ZERO_EXTEND: 2810 assert(VT.isInteger() && Operand.getValueType().isInteger() && 2811 "Invalid ZERO_EXTEND!"); 2812 if (Operand.getValueType() == VT) return Operand; // noop extension 2813 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) && 2814 "Invalid zext node, dst < src!"); 2815 assert((!VT.isVector() || 2816 VT.getVectorNumElements() == 2817 Operand.getValueType().getVectorNumElements()) && 2818 "Vector element count mismatch!"); 2819 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x) 2820 return getNode(ISD::ZERO_EXTEND, DL, VT, 2821 Operand.getNode()->getOperand(0)); 2822 else if (OpOpcode == ISD::UNDEF) 2823 // zext(undef) = 0, because the top bits will be zero. 2824 return getConstant(0, VT); 2825 break; 2826 case ISD::ANY_EXTEND: 2827 assert(VT.isInteger() && Operand.getValueType().isInteger() && 2828 "Invalid ANY_EXTEND!"); 2829 if (Operand.getValueType() == VT) return Operand; // noop extension 2830 assert(Operand.getValueType().getScalarType().bitsLT(VT.getScalarType()) && 2831 "Invalid anyext node, dst < src!"); 2832 assert((!VT.isVector() || 2833 VT.getVectorNumElements() == 2834 Operand.getValueType().getVectorNumElements()) && 2835 "Vector element count mismatch!"); 2836 2837 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || 2838 OpOpcode == ISD::ANY_EXTEND) 2839 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x) 2840 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0)); 2841 else if (OpOpcode == ISD::UNDEF) 2842 return getUNDEF(VT); 2843 2844 // (ext (trunx x)) -> x 2845 if (OpOpcode == ISD::TRUNCATE) { 2846 SDValue OpOp = Operand.getNode()->getOperand(0); 2847 if (OpOp.getValueType() == VT) 2848 return OpOp; 2849 } 2850 break; 2851 case ISD::TRUNCATE: 2852 assert(VT.isInteger() && Operand.getValueType().isInteger() && 2853 "Invalid TRUNCATE!"); 2854 if (Operand.getValueType() == VT) return Operand; // noop truncate 2855 assert(Operand.getValueType().getScalarType().bitsGT(VT.getScalarType()) && 2856 "Invalid truncate node, src < dst!"); 2857 assert((!VT.isVector() || 2858 VT.getVectorNumElements() == 2859 Operand.getValueType().getVectorNumElements()) && 2860 "Vector element count mismatch!"); 2861 if (OpOpcode == ISD::TRUNCATE) 2862 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0)); 2863 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || 2864 OpOpcode == ISD::ANY_EXTEND) { 2865 // If the source is smaller than the dest, we still need an extend. 2866 if (Operand.getNode()->getOperand(0).getValueType().getScalarType() 2867 .bitsLT(VT.getScalarType())) 2868 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0)); 2869 if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT)) 2870 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0)); 2871 return Operand.getNode()->getOperand(0); 2872 } 2873 if (OpOpcode == ISD::UNDEF) 2874 return getUNDEF(VT); 2875 break; 2876 case ISD::BITCAST: 2877 // Basic sanity checking. 2878 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits() 2879 && "Cannot BITCAST between types of different sizes!"); 2880 if (VT == Operand.getValueType()) return Operand; // noop conversion. 2881 if (OpOpcode == ISD::BITCAST) // bitconv(bitconv(x)) -> bitconv(x) 2882 return getNode(ISD::BITCAST, DL, VT, Operand.getOperand(0)); 2883 if (OpOpcode == ISD::UNDEF) 2884 return getUNDEF(VT); 2885 break; 2886 case ISD::SCALAR_TO_VECTOR: 2887 assert(VT.isVector() && !Operand.getValueType().isVector() && 2888 (VT.getVectorElementType() == Operand.getValueType() || 2889 (VT.getVectorElementType().isInteger() && 2890 Operand.getValueType().isInteger() && 2891 VT.getVectorElementType().bitsLE(Operand.getValueType()))) && 2892 "Illegal SCALAR_TO_VECTOR node!"); 2893 if (OpOpcode == ISD::UNDEF) 2894 return getUNDEF(VT); 2895 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined. 2896 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT && 2897 isa<ConstantSDNode>(Operand.getOperand(1)) && 2898 Operand.getConstantOperandVal(1) == 0 && 2899 Operand.getOperand(0).getValueType() == VT) 2900 return Operand.getOperand(0); 2901 break; 2902 case ISD::FNEG: 2903 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0 2904 if (getTarget().Options.UnsafeFPMath && OpOpcode == ISD::FSUB) 2905 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1), 2906 Operand.getNode()->getOperand(0)); 2907 if (OpOpcode == ISD::FNEG) // --X -> X 2908 return Operand.getNode()->getOperand(0); 2909 break; 2910 case ISD::FABS: 2911 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X) 2912 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0)); 2913 break; 2914 } 2915 2916 SDNode *N; 2917 SDVTList VTs = getVTList(VT); 2918 if (VT != MVT::Glue) { // Don't CSE flag producing nodes 2919 FoldingSetNodeID ID; 2920 SDValue Ops[1] = { Operand }; 2921 AddNodeIDNode(ID, Opcode, VTs, Ops); 2922 void *IP = nullptr; 2923 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 2924 return SDValue(E, 0); 2925 2926 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(), 2927 DL.getDebugLoc(), VTs, Operand); 2928 CSEMap.InsertNode(N, IP); 2929 } else { 2930 N = new (NodeAllocator) UnarySDNode(Opcode, DL.getIROrder(), 2931 DL.getDebugLoc(), VTs, Operand); 2932 } 2933 2934 AllNodes.push_back(N); 2935 #ifndef NDEBUG 2936 VerifySDNode(N); 2937 #endif 2938 return SDValue(N, 0); 2939 } 2940 2941 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, EVT VT, 2942 SDNode *Cst1, SDNode *Cst2) { 2943 // If the opcode is a target-specific ISD node, there's nothing we can 2944 // do here and the operand rules may not line up with the below, so 2945 // bail early. 2946 if (Opcode >= ISD::BUILTIN_OP_END) 2947 return SDValue(); 2948 2949 SmallVector<std::pair<ConstantSDNode *, ConstantSDNode *>, 4> Inputs; 2950 SmallVector<SDValue, 4> Outputs; 2951 EVT SVT = VT.getScalarType(); 2952 2953 ConstantSDNode *Scalar1 = dyn_cast<ConstantSDNode>(Cst1); 2954 ConstantSDNode *Scalar2 = dyn_cast<ConstantSDNode>(Cst2); 2955 if (Scalar1 && Scalar2 && (Scalar1->isOpaque() || Scalar2->isOpaque())) 2956 return SDValue(); 2957 2958 if (Scalar1 && Scalar2) 2959 // Scalar instruction. 2960 Inputs.push_back(std::make_pair(Scalar1, Scalar2)); 2961 else { 2962 // For vectors extract each constant element into Inputs so we can constant 2963 // fold them individually. 2964 BuildVectorSDNode *BV1 = dyn_cast<BuildVectorSDNode>(Cst1); 2965 BuildVectorSDNode *BV2 = dyn_cast<BuildVectorSDNode>(Cst2); 2966 if (!BV1 || !BV2) 2967 return SDValue(); 2968 2969 assert(BV1->getNumOperands() == BV2->getNumOperands() && "Out of sync!"); 2970 2971 for (unsigned I = 0, E = BV1->getNumOperands(); I != E; ++I) { 2972 ConstantSDNode *V1 = dyn_cast<ConstantSDNode>(BV1->getOperand(I)); 2973 ConstantSDNode *V2 = dyn_cast<ConstantSDNode>(BV2->getOperand(I)); 2974 if (!V1 || !V2) // Not a constant, bail. 2975 return SDValue(); 2976 2977 if (V1->isOpaque() || V2->isOpaque()) 2978 return SDValue(); 2979 2980 // Avoid BUILD_VECTOR nodes that perform implicit truncation. 2981 // FIXME: This is valid and could be handled by truncating the APInts. 2982 if (V1->getValueType(0) != SVT || V2->getValueType(0) != SVT) 2983 return SDValue(); 2984 2985 Inputs.push_back(std::make_pair(V1, V2)); 2986 } 2987 } 2988 2989 // We have a number of constant values, constant fold them element by element. 2990 for (unsigned I = 0, E = Inputs.size(); I != E; ++I) { 2991 const APInt &C1 = Inputs[I].first->getAPIntValue(); 2992 const APInt &C2 = Inputs[I].second->getAPIntValue(); 2993 2994 switch (Opcode) { 2995 case ISD::ADD: 2996 Outputs.push_back(getConstant(C1 + C2, SVT)); 2997 break; 2998 case ISD::SUB: 2999 Outputs.push_back(getConstant(C1 - C2, SVT)); 3000 break; 3001 case ISD::MUL: 3002 Outputs.push_back(getConstant(C1 * C2, SVT)); 3003 break; 3004 case ISD::UDIV: 3005 if (!C2.getBoolValue()) 3006 return SDValue(); 3007 Outputs.push_back(getConstant(C1.udiv(C2), SVT)); 3008 break; 3009 case ISD::UREM: 3010 if (!C2.getBoolValue()) 3011 return SDValue(); 3012 Outputs.push_back(getConstant(C1.urem(C2), SVT)); 3013 break; 3014 case ISD::SDIV: 3015 if (!C2.getBoolValue()) 3016 return SDValue(); 3017 Outputs.push_back(getConstant(C1.sdiv(C2), SVT)); 3018 break; 3019 case ISD::SREM: 3020 if (!C2.getBoolValue()) 3021 return SDValue(); 3022 Outputs.push_back(getConstant(C1.srem(C2), SVT)); 3023 break; 3024 case ISD::AND: 3025 Outputs.push_back(getConstant(C1 & C2, SVT)); 3026 break; 3027 case ISD::OR: 3028 Outputs.push_back(getConstant(C1 | C2, SVT)); 3029 break; 3030 case ISD::XOR: 3031 Outputs.push_back(getConstant(C1 ^ C2, SVT)); 3032 break; 3033 case ISD::SHL: 3034 Outputs.push_back(getConstant(C1 << C2, SVT)); 3035 break; 3036 case ISD::SRL: 3037 Outputs.push_back(getConstant(C1.lshr(C2), SVT)); 3038 break; 3039 case ISD::SRA: 3040 Outputs.push_back(getConstant(C1.ashr(C2), SVT)); 3041 break; 3042 case ISD::ROTL: 3043 Outputs.push_back(getConstant(C1.rotl(C2), SVT)); 3044 break; 3045 case ISD::ROTR: 3046 Outputs.push_back(getConstant(C1.rotr(C2), SVT)); 3047 break; 3048 default: 3049 return SDValue(); 3050 } 3051 } 3052 3053 assert((Scalar1 && Scalar2) || (VT.getVectorNumElements() == Outputs.size() && 3054 "Expected a scalar or vector!")); 3055 3056 // Handle the scalar case first. 3057 if (!VT.isVector()) 3058 return Outputs.back(); 3059 3060 // We may have a vector type but a scalar result. Create a splat. 3061 Outputs.resize(VT.getVectorNumElements(), Outputs.back()); 3062 3063 // Build a big vector out of the scalar elements we generated. 3064 return getNode(ISD::BUILD_VECTOR, SDLoc(), VT, Outputs); 3065 } 3066 3067 SDValue SelectionDAG::getNode(unsigned Opcode, SDLoc DL, EVT VT, SDValue N1, 3068 SDValue N2, bool nuw, bool nsw, bool exact) { 3069 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 3070 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode()); 3071 switch (Opcode) { 3072 default: break; 3073 case ISD::TokenFactor: 3074 assert(VT == MVT::Other && N1.getValueType() == MVT::Other && 3075 N2.getValueType() == MVT::Other && "Invalid token factor!"); 3076 // Fold trivial token factors. 3077 if (N1.getOpcode() == ISD::EntryToken) return N2; 3078 if (N2.getOpcode() == ISD::EntryToken) return N1; 3079 if (N1 == N2) return N1; 3080 break; 3081 case ISD::CONCAT_VECTORS: 3082 // Concat of UNDEFs is UNDEF. 3083 if (N1.getOpcode() == ISD::UNDEF && 3084 N2.getOpcode() == ISD::UNDEF) 3085 return getUNDEF(VT); 3086 3087 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to 3088 // one big BUILD_VECTOR. 3089 if (N1.getOpcode() == ISD::BUILD_VECTOR && 3090 N2.getOpcode() == ISD::BUILD_VECTOR) { 3091 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(), 3092 N1.getNode()->op_end()); 3093 Elts.append(N2.getNode()->op_begin(), N2.getNode()->op_end()); 3094 return getNode(ISD::BUILD_VECTOR, DL, VT, Elts); 3095 } 3096 break; 3097 case ISD::AND: 3098 assert(VT.isInteger() && "This operator does not apply to FP types!"); 3099 assert(N1.getValueType() == N2.getValueType() && 3100 N1.getValueType() == VT && "Binary operator types must match!"); 3101 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's 3102 // worth handling here. 3103 if (N2C && N2C->isNullValue()) 3104 return N2; 3105 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X 3106 return N1; 3107 break; 3108 case ISD::OR: 3109 case ISD::XOR: 3110 case ISD::ADD: 3111 case ISD::SUB: 3112 assert(VT.isInteger() && "This operator does not apply to FP types!"); 3113 assert(N1.getValueType() == N2.getValueType() && 3114 N1.getValueType() == VT && "Binary operator types must match!"); 3115 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so 3116 // it's worth handling here. 3117 if (N2C && N2C->isNullValue()) 3118 return N1; 3119 break; 3120 case ISD::UDIV: 3121 case ISD::UREM: 3122 case ISD::MULHU: 3123 case ISD::MULHS: 3124 case ISD::MUL: 3125 case ISD::SDIV: 3126 case ISD::SREM: 3127 assert(VT.isInteger() && "This operator does not apply to FP types!"); 3128 assert(N1.getValueType() == N2.getValueType() && 3129 N1.getValueType() == VT && "Binary operator types must match!"); 3130 break; 3131 case ISD::FADD: 3132 case ISD::FSUB: 3133 case ISD::FMUL: 3134 case ISD::FDIV: 3135 case ISD::FREM: 3136 if (getTarget().Options.UnsafeFPMath) { 3137 if (Opcode == ISD::FADD) { 3138 // 0+x --> x 3139 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) 3140 if (CFP->getValueAPF().isZero()) 3141 return N2; 3142 // x+0 --> x 3143 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2)) 3144 if (CFP->getValueAPF().isZero()) 3145 return N1; 3146 } else if (Opcode == ISD::FSUB) { 3147 // x-0 --> x 3148 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2)) 3149 if (CFP->getValueAPF().isZero()) 3150 return N1; 3151 } else if (Opcode == ISD::FMUL) { 3152 ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1); 3153 SDValue V = N2; 3154 3155 // If the first operand isn't the constant, try the second 3156 if (!CFP) { 3157 CFP = dyn_cast<ConstantFPSDNode>(N2); 3158 V = N1; 3159 } 3160 3161 if (CFP) { 3162 // 0*x --> 0 3163 if (CFP->isZero()) 3164 return SDValue(CFP,0); 3165 // 1*x --> x 3166 if (CFP->isExactlyValue(1.0)) 3167 return V; 3168 } 3169 } 3170 } 3171 assert(VT.isFloatingPoint() && "This operator only applies to FP types!"); 3172 assert(N1.getValueType() == N2.getValueType() && 3173 N1.getValueType() == VT && "Binary operator types must match!"); 3174 break; 3175 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match. 3176 assert(N1.getValueType() == VT && 3177 N1.getValueType().isFloatingPoint() && 3178 N2.getValueType().isFloatingPoint() && 3179 "Invalid FCOPYSIGN!"); 3180 break; 3181 case ISD::SHL: 3182 case ISD::SRA: 3183 case ISD::SRL: 3184 case ISD::ROTL: 3185 case ISD::ROTR: 3186 assert(VT == N1.getValueType() && 3187 "Shift operators return type must be the same as their first arg"); 3188 assert(VT.isInteger() && N2.getValueType().isInteger() && 3189 "Shifts only work on integers"); 3190 assert((!VT.isVector() || VT == N2.getValueType()) && 3191 "Vector shift amounts must be in the same as their first arg"); 3192 // Verify that the shift amount VT is bit enough to hold valid shift 3193 // amounts. This catches things like trying to shift an i1024 value by an 3194 // i8, which is easy to fall into in generic code that uses 3195 // TLI.getShiftAmount(). 3196 assert(N2.getValueType().getSizeInBits() >= 3197 Log2_32_Ceil(N1.getValueType().getSizeInBits()) && 3198 "Invalid use of small shift amount with oversized value!"); 3199 3200 // Always fold shifts of i1 values so the code generator doesn't need to 3201 // handle them. Since we know the size of the shift has to be less than the 3202 // size of the value, the shift/rotate count is guaranteed to be zero. 3203 if (VT == MVT::i1) 3204 return N1; 3205 if (N2C && N2C->isNullValue()) 3206 return N1; 3207 break; 3208 case ISD::FP_ROUND_INREG: { 3209 EVT EVT = cast<VTSDNode>(N2)->getVT(); 3210 assert(VT == N1.getValueType() && "Not an inreg round!"); 3211 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() && 3212 "Cannot FP_ROUND_INREG integer types"); 3213 assert(EVT.isVector() == VT.isVector() && 3214 "FP_ROUND_INREG type should be vector iff the operand " 3215 "type is vector!"); 3216 assert((!EVT.isVector() || 3217 EVT.getVectorNumElements() == VT.getVectorNumElements()) && 3218 "Vector element counts must match in FP_ROUND_INREG"); 3219 assert(EVT.bitsLE(VT) && "Not rounding down!"); 3220 (void)EVT; 3221 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding. 3222 break; 3223 } 3224 case ISD::FP_ROUND: 3225 assert(VT.isFloatingPoint() && 3226 N1.getValueType().isFloatingPoint() && 3227 VT.bitsLE(N1.getValueType()) && 3228 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!"); 3229 if (N1.getValueType() == VT) return N1; // noop conversion. 3230 break; 3231 case ISD::AssertSext: 3232 case ISD::AssertZext: { 3233 EVT EVT = cast<VTSDNode>(N2)->getVT(); 3234 assert(VT == N1.getValueType() && "Not an inreg extend!"); 3235 assert(VT.isInteger() && EVT.isInteger() && 3236 "Cannot *_EXTEND_INREG FP types"); 3237 assert(!EVT.isVector() && 3238 "AssertSExt/AssertZExt type should be the vector element type " 3239 "rather than the vector type!"); 3240 assert(EVT.bitsLE(VT) && "Not extending!"); 3241 if (VT == EVT) return N1; // noop assertion. 3242 break; 3243 } 3244 case ISD::SIGN_EXTEND_INREG: { 3245 EVT EVT = cast<VTSDNode>(N2)->getVT(); 3246 assert(VT == N1.getValueType() && "Not an inreg extend!"); 3247 assert(VT.isInteger() && EVT.isInteger() && 3248 "Cannot *_EXTEND_INREG FP types"); 3249 assert(EVT.isVector() == VT.isVector() && 3250 "SIGN_EXTEND_INREG type should be vector iff the operand " 3251 "type is vector!"); 3252 assert((!EVT.isVector() || 3253 EVT.getVectorNumElements() == VT.getVectorNumElements()) && 3254 "Vector element counts must match in SIGN_EXTEND_INREG"); 3255 assert(EVT.bitsLE(VT) && "Not extending!"); 3256 if (EVT == VT) return N1; // Not actually extending 3257 3258 if (N1C) { 3259 APInt Val = N1C->getAPIntValue(); 3260 unsigned FromBits = EVT.getScalarType().