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