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