LLVM API Documentation
00001 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements the SelectionDAG class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 #include "llvm/CodeGen/SelectionDAG.h" 00014 #include "llvm/Constants.h" 00015 #include "llvm/Analysis/ValueTracking.h" 00016 #include "llvm/Function.h" 00017 #include "llvm/GlobalAlias.h" 00018 #include "llvm/GlobalVariable.h" 00019 #include "llvm/Intrinsics.h" 00020 #include "llvm/DerivedTypes.h" 00021 #include "llvm/Assembly/Writer.h" 00022 #include "llvm/CallingConv.h" 00023 #include "llvm/CodeGen/MachineBasicBlock.h" 00024 #include "llvm/CodeGen/MachineConstantPool.h" 00025 #include "llvm/CodeGen/MachineFrameInfo.h" 00026 #include "llvm/CodeGen/MachineModuleInfo.h" 00027 #include "llvm/CodeGen/PseudoSourceValue.h" 00028 #include "llvm/Target/TargetRegisterInfo.h" 00029 #include "llvm/Target/TargetData.h" 00030 #include "llvm/Target/TargetLowering.h" 00031 #include "llvm/Target/TargetOptions.h" 00032 #include "llvm/Target/TargetInstrInfo.h" 00033 #include "llvm/Target/TargetMachine.h" 00034 #include "llvm/Support/CommandLine.h" 00035 #include "llvm/Support/ErrorHandling.h" 00036 #include "llvm/Support/ManagedStatic.h" 00037 #include "llvm/Support/MathExtras.h" 00038 #include "llvm/Support/raw_ostream.h" 00039 #include "llvm/System/Mutex.h" 00040 #include "llvm/ADT/SetVector.h" 00041 #include "llvm/ADT/SmallPtrSet.h" 00042 #include "llvm/ADT/SmallSet.h" 00043 #include "llvm/ADT/SmallVector.h" 00044 #include "llvm/ADT/StringExtras.h" 00045 #include <algorithm> 00046 #include <cmath> 00047 using namespace llvm; 00048 00049 /// makeVTList - Return an instance of the SDVTList struct initialized with the 00050 /// specified members. 00051 static SDVTList makeVTList(const EVT *VTs, unsigned NumVTs) { 00052 SDVTList Res = {VTs, NumVTs}; 00053 return Res; 00054 } 00055 00056 static const fltSemantics *EVTToAPFloatSemantics(EVT VT) { 00057 switch (VT.getSimpleVT().SimpleTy) { 00058 default: llvm_unreachable("Unknown FP format"); 00059 case MVT::f32: return &APFloat::IEEEsingle; 00060 case MVT::f64: return &APFloat::IEEEdouble; 00061 case MVT::f80: return &APFloat::x87DoubleExtended; 00062 case MVT::f128: return &APFloat::IEEEquad; 00063 case MVT::ppcf128: return &APFloat::PPCDoubleDouble; 00064 } 00065 } 00066 00067 SelectionDAG::DAGUpdateListener::~DAGUpdateListener() {} 00068 00069 //===----------------------------------------------------------------------===// 00070 // ConstantFPSDNode Class 00071 //===----------------------------------------------------------------------===// 00072 00073 /// isExactlyValue - We don't rely on operator== working on double values, as 00074 /// it returns true for things that are clearly not equal, like -0.0 and 0.0. 00075 /// As such, this method can be used to do an exact bit-for-bit comparison of 00076 /// two floating point values. 00077 bool ConstantFPSDNode::isExactlyValue(const APFloat& V) const { 00078 return getValueAPF().bitwiseIsEqual(V); 00079 } 00080 00081 bool ConstantFPSDNode::isValueValidForType(EVT VT, 00082 const APFloat& Val) { 00083 assert(VT.isFloatingPoint() && "Can only convert between FP types"); 00084 00085 // PPC long double cannot be converted to any other type. 00086 if (VT == MVT::ppcf128 || 00087 &Val.getSemantics() == &APFloat::PPCDoubleDouble) 00088 return false; 00089 00090 // convert modifies in place, so make a copy. 00091 APFloat Val2 = APFloat(Val); 00092 bool losesInfo; 00093 (void) Val2.convert(*EVTToAPFloatSemantics(VT), APFloat::rmNearestTiesToEven, 00094 &losesInfo); 00095 return !losesInfo; 00096 } 00097 00098 //===----------------------------------------------------------------------===// 00099 // ISD Namespace 00100 //===----------------------------------------------------------------------===// 00101 00102 /// isBuildVectorAllOnes - Return true if the specified node is a 00103 /// BUILD_VECTOR where all of the elements are ~0 or undef. 00104 bool ISD::isBuildVectorAllOnes(const SDNode *N) { 00105 // Look through a bit convert. 00106 if (N->getOpcode() == ISD::BIT_CONVERT) 00107 N = N->getOperand(0).getNode(); 00108 00109 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 00110 00111 unsigned i = 0, e = N->getNumOperands(); 00112 00113 // Skip over all of the undef values. 00114 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 00115 ++i; 00116 00117 // Do not accept an all-undef vector. 00118 if (i == e) return false; 00119 00120 // Do not accept build_vectors that aren't all constants or which have non-~0 00121 // elements. 00122 SDValue NotZero = N->getOperand(i); 00123 if (isa<ConstantSDNode>(NotZero)) { 00124 if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue()) 00125 return false; 00126 } else if (isa<ConstantFPSDNode>(NotZero)) { 00127 if (!cast<ConstantFPSDNode>(NotZero)->getValueAPF(). 00128 bitcastToAPInt().isAllOnesValue()) 00129 return false; 00130 } else 00131 return false; 00132 00133 // Okay, we have at least one ~0 value, check to see if the rest match or are 00134 // undefs. 00135 for (++i; i != e; ++i) 00136 if (N->getOperand(i) != NotZero && 00137 N->getOperand(i).getOpcode() != ISD::UNDEF) 00138 return false; 00139 return true; 00140 } 00141 00142 00143 /// isBuildVectorAllZeros - Return true if the specified node is a 00144 /// BUILD_VECTOR where all of the elements are 0 or undef. 00145 bool ISD::isBuildVectorAllZeros(const SDNode *N) { 00146 // Look through a bit convert. 00147 if (N->getOpcode() == ISD::BIT_CONVERT) 00148 N = N->getOperand(0).getNode(); 00149 00150 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 00151 00152 unsigned i = 0, e = N->getNumOperands(); 00153 00154 // Skip over all of the undef values. 00155 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 00156 ++i; 00157 00158 // Do not accept an all-undef vector. 00159 if (i == e) return false; 00160 00161 // Do not accept build_vectors that aren't all constants or which have non-0 00162 // elements. 00163 SDValue Zero = N->getOperand(i); 00164 if (isa<ConstantSDNode>(Zero)) { 00165 if (!cast<ConstantSDNode>(Zero)->isNullValue()) 00166 return false; 00167 } else if (isa<ConstantFPSDNode>(Zero)) { 00168 if (!cast<ConstantFPSDNode>(Zero)->getValueAPF().isPosZero()) 00169 return false; 00170 } else 00171 return false; 00172 00173 // Okay, we have at least one 0 value, check to see if the rest match or are 00174 // undefs. 00175 for (++i; i != e; ++i) 00176 if (N->getOperand(i) != Zero && 00177 N->getOperand(i).getOpcode() != ISD::UNDEF) 00178 return false; 00179 return true; 00180 } 00181 00182 /// isScalarToVector - Return true if the specified node is a 00183 /// ISD::SCALAR_TO_VECTOR node or a BUILD_VECTOR node where only the low 00184 /// element is not an undef. 00185 bool ISD::isScalarToVector(const SDNode *N) { 00186 if (N->getOpcode() == ISD::SCALAR_TO_VECTOR) 00187 return true; 00188 00189 if (N->getOpcode() != ISD::BUILD_VECTOR) 00190 return false; 00191 if (N->getOperand(0).getOpcode() == ISD::UNDEF) 00192 return false; 00193 unsigned NumElems = N->getNumOperands(); 00194 for (unsigned i = 1; i < NumElems; ++i) { 00195 SDValue V = N->getOperand(i); 00196 if (V.getOpcode() != ISD::UNDEF) 00197 return false; 00198 } 00199 return true; 00200 } 00201 00202 00203 /// isDebugLabel - Return true if the specified node represents a debug 00204 /// label (i.e. ISD::DBG_LABEL or TargetInstrInfo::DBG_LABEL node). 00205 bool ISD::isDebugLabel(const SDNode *N) { 00206 SDValue Zero; 00207 if (N->getOpcode() == ISD::DBG_LABEL) 00208 return true; 00209 if (N->isMachineOpcode() && 00210 N->getMachineOpcode() == TargetInstrInfo::DBG_LABEL) 00211 return true; 00212 return false; 00213 } 00214 00215 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 00216 /// when given the operation for (X op Y). 00217 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 00218 // To perform this operation, we just need to swap the L and G bits of the 00219 // operation. 00220 unsigned OldL = (Operation >> 2) & 1; 00221 unsigned OldG = (Operation >> 1) & 1; 00222 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 00223 (OldL << 1) | // New G bit 00224 (OldG << 2)); // New L bit. 00225 } 00226 00227 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where 00228 /// 'op' is a valid SetCC operation. 00229 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 00230 unsigned Operation = Op; 00231 if (isInteger) 00232 Operation ^= 7; // Flip L, G, E bits, but not U. 00233 else 00234 Operation ^= 15; // Flip all of the condition bits. 00235 00236 if (Operation > ISD::SETTRUE2) 00237 Operation &= ~8; // Don't let N and U bits get set. 00238 00239 return ISD::CondCode(Operation); 00240 } 00241 00242 00243 /// isSignedOp - For an integer comparison, return 1 if the comparison is a 00244 /// signed operation and 2 if the result is an unsigned comparison. Return zero 00245 /// if the operation does not depend on the sign of the input (setne and seteq). 00246 static int isSignedOp(ISD::CondCode Opcode) { 00247 switch (Opcode) { 00248 default: llvm_unreachable("Illegal integer setcc operation!"); 00249 case ISD::SETEQ: 00250 case ISD::SETNE: return 0; 00251 case ISD::SETLT: 00252 case ISD::SETLE: 00253 case ISD::SETGT: 00254 case ISD::SETGE: return 1; 00255 case ISD::SETULT: 00256 case ISD::SETULE: 00257 case ISD::SETUGT: 00258 case ISD::SETUGE: return 2; 00259 } 00260 } 00261 00262 /// getSetCCOrOperation - Return the result of a logical OR between different 00263 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 00264 /// returns SETCC_INVALID if it is not possible to represent the resultant 00265 /// comparison. 00266 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 00267 bool isInteger) { 00268 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 00269 // Cannot fold a signed integer setcc with an unsigned integer setcc. 00270 return ISD::SETCC_INVALID; 00271 00272 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 00273 00274 // If the N and U bits get set then the resultant comparison DOES suddenly 00275 // care about orderedness, and is true when ordered. 00276 if (Op > ISD::SETTRUE2) 00277 Op &= ~16; // Clear the U bit if the N bit is set. 00278 00279 // Canonicalize illegal integer setcc's. 00280 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT 00281 Op = ISD::SETNE; 00282 00283 return ISD::CondCode(Op); 00284 } 00285 00286 /// getSetCCAndOperation - Return the result of a logical AND between different 00287 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 00288 /// function returns zero if it is not possible to represent the resultant 00289 /// comparison. 00290 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 00291 bool isInteger) { 00292 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 00293 // Cannot fold a signed setcc with an unsigned setcc. 00294 return ISD::SETCC_INVALID; 00295 00296 // Combine all of the condition bits. 00297 ISD::CondCode Result = ISD::CondCode(Op1 & Op2); 00298 00299 // Canonicalize illegal integer setcc's. 00300 if (isInteger) { 00301 switch (Result) { 00302 default: break; 00303 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT 00304 case ISD::SETOEQ: // SETEQ & SETU[LG]E 00305 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE 00306 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE 00307 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE 00308 } 00309 } 00310 00311 return Result; 00312 } 00313 00314 const TargetMachine &SelectionDAG::getTarget() const { 00315 return MF->getTarget(); 00316 } 00317 00318 //===----------------------------------------------------------------------===// 00319 // SDNode Profile Support 00320 //===----------------------------------------------------------------------===// 00321 00322 /// AddNodeIDOpcode - Add the node opcode to the NodeID data. 00323 /// 00324 static void AddNodeIDOpcode(FoldingSetNodeID &ID, unsigned OpC) { 00325 ID.AddInteger(OpC); 00326 } 00327 00328 /// AddNodeIDValueTypes - Value type lists are intern'd so we can represent them 00329 /// solely with their pointer. 00330 static void AddNodeIDValueTypes(FoldingSetNodeID &ID, SDVTList VTList) { 00331 ID.AddPointer(VTList.VTs); 00332 } 00333 00334 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data. 00335 /// 00336 static void AddNodeIDOperands(FoldingSetNodeID &ID, 00337 const SDValue *Ops, unsigned NumOps) { 00338 for (; NumOps; --NumOps, ++Ops) { 00339 ID.AddPointer(Ops->getNode()); 00340 ID.AddInteger(Ops->getResNo()); 00341 } 00342 } 00343 00344 /// AddNodeIDOperands - Various routines for adding operands to the NodeID data. 00345 /// 00346 static void AddNodeIDOperands(FoldingSetNodeID &ID, 00347 const SDUse *Ops, unsigned NumOps) { 00348 for (; NumOps; --NumOps, ++Ops) { 00349 ID.AddPointer(Ops->getNode()); 00350 ID.AddInteger(Ops->getResNo()); 00351 } 00352 } 00353 00354 static void AddNodeIDNode(FoldingSetNodeID &ID, 00355 unsigned short OpC, SDVTList VTList, 00356 const SDValue *OpList, unsigned N) { 00357 AddNodeIDOpcode(ID, OpC); 00358 AddNodeIDValueTypes(ID, VTList); 00359 AddNodeIDOperands(ID, OpList, N); 00360 } 00361 00362 /// AddNodeIDCustom - If this is an SDNode with special info, add this info to 00363 /// the NodeID data. 00364 static void AddNodeIDCustom(FoldingSetNodeID &ID, const SDNode *N) { 00365 switch (N->getOpcode()) { 00366 case ISD::TargetExternalSymbol: 00367 case ISD::ExternalSymbol: 00368 llvm_unreachable("Should only be used on nodes with operands"); 00369 default: break; // Normal nodes don't need extra info. 00370 case ISD::TargetConstant: 00371 case ISD::Constant: 00372 ID.AddPointer(cast<ConstantSDNode>(N)->getConstantIntValue()); 00373 break; 00374 case ISD::TargetConstantFP: 00375 case ISD::ConstantFP: { 00376 ID.AddPointer(cast<ConstantFPSDNode>(N)->getConstantFPValue()); 00377 break; 00378 } 00379 case ISD::TargetGlobalAddress: 00380 case ISD::GlobalAddress: 00381 case ISD::TargetGlobalTLSAddress: 00382 case ISD::GlobalTLSAddress: { 00383 const GlobalAddressSDNode *GA = cast<GlobalAddressSDNode>(N); 00384 ID.AddPointer(GA->getGlobal()); 00385 ID.AddInteger(GA->getOffset()); 00386 ID.AddInteger(GA->getTargetFlags()); 00387 break; 00388 } 00389 case ISD::BasicBlock: 00390 ID.AddPointer(cast<BasicBlockSDNode>(N)->getBasicBlock()); 00391 break; 00392 case ISD::Register: 00393 ID.AddInteger(cast<RegisterSDNode>(N)->getReg()); 00394 break; 00395 case ISD::DBG_STOPPOINT: { 00396 const DbgStopPointSDNode *DSP = cast<DbgStopPointSDNode>(N); 00397 ID.AddInteger(DSP->getLine()); 00398 ID.AddInteger(DSP->getColumn()); 00399 ID.AddPointer(DSP->getCompileUnit()); 00400 break; 00401 } 00402 case ISD::SRCVALUE: 00403 ID.AddPointer(cast<SrcValueSDNode>(N)->getValue()); 00404 break; 00405 case ISD::MEMOPERAND: { 00406 const MachineMemOperand &MO = cast<MemOperandSDNode>(N)->MO; 00407 MO.Profile(ID); 00408 break; 00409 } 00410 case ISD::FrameIndex: 00411 case ISD::TargetFrameIndex: 00412 ID.AddInteger(cast<FrameIndexSDNode>(N)->getIndex()); 00413 break; 00414 case ISD::JumpTable: 00415 case ISD::TargetJumpTable: 00416 ID.AddInteger(cast<JumpTableSDNode>(N)->getIndex()); 00417 ID.AddInteger(cast<JumpTableSDNode>(N)->getTargetFlags()); 00418 break; 00419 case ISD::ConstantPool: 00420 case ISD::TargetConstantPool: { 00421 const ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(N); 00422 ID.AddInteger(CP->getAlignment()); 00423 ID.AddInteger(CP->getOffset()); 00424 if (CP->isMachineConstantPoolEntry()) 00425 CP->getMachineCPVal()->AddSelectionDAGCSEId(ID); 00426 else 00427 ID.AddPointer(CP->getConstVal()); 00428 ID.AddInteger(CP->getTargetFlags()); 00429 break; 00430 } 00431 case ISD::LOAD: { 00432 const LoadSDNode *LD = cast<LoadSDNode>(N); 00433 ID.AddInteger(LD->getMemoryVT().getRawBits()); 00434 ID.AddInteger(LD->getRawSubclassData()); 00435 break; 00436 } 00437 case ISD::STORE: { 00438 const StoreSDNode *ST = cast<StoreSDNode>(N); 00439 ID.AddInteger(ST->getMemoryVT().getRawBits()); 00440 ID.AddInteger(ST->getRawSubclassData()); 00441 break; 00442 } 00443 case ISD::ATOMIC_CMP_SWAP: 00444 case ISD::ATOMIC_SWAP: 00445 case ISD::ATOMIC_LOAD_ADD: 00446 case ISD::ATOMIC_LOAD_SUB: 00447 case ISD::ATOMIC_LOAD_AND: 00448 case ISD::ATOMIC_LOAD_OR: 00449 case ISD::ATOMIC_LOAD_XOR: 00450 case ISD::ATOMIC_LOAD_NAND: 00451 case ISD::ATOMIC_LOAD_MIN: 00452 case ISD::ATOMIC_LOAD_MAX: 00453 case ISD::ATOMIC_LOAD_UMIN: 00454 case ISD::ATOMIC_LOAD_UMAX: { 00455 const AtomicSDNode *AT = cast<AtomicSDNode>(N); 00456 ID.AddInteger(AT->getMemoryVT().getRawBits()); 00457 ID.AddInteger(AT->getRawSubclassData()); 00458 break; 00459 } 00460 case ISD::VECTOR_SHUFFLE: { 00461 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(N); 00462 for (unsigned i = 0, e = N->getValueType(0).getVectorNumElements(); 00463 i != e; ++i) 00464 ID.AddInteger(SVN->getMaskElt(i)); 00465 break; 00466 } 00467 } // end switch (N->getOpcode()) 00468 } 00469 00470 /// AddNodeIDNode - Generic routine for adding a nodes info to the NodeID 00471 /// data. 00472 static void AddNodeIDNode(FoldingSetNodeID &ID, const SDNode *N) { 00473 AddNodeIDOpcode(ID, N->getOpcode()); 00474 // Add the return value info. 00475 AddNodeIDValueTypes(ID, N->getVTList()); 00476 // Add the operand info. 00477 AddNodeIDOperands(ID, N->op_begin(), N->getNumOperands()); 00478 00479 // Handle SDNode leafs with special info. 00480 AddNodeIDCustom(ID, N); 00481 } 00482 00483 /// encodeMemSDNodeFlags - Generic routine for computing a value for use in 00484 /// the CSE map that carries alignment, volatility, indexing mode, and 00485 /// extension/truncation information. 00486 /// 00487 static inline unsigned 00488 encodeMemSDNodeFlags(int ConvType, ISD::MemIndexedMode AM, 00489 bool isVolatile, unsigned Alignment) { 00490 assert((ConvType & 3) == ConvType && 00491 "ConvType may not require more than 2 bits!"); 00492 assert((AM & 7) == AM && 00493 "AM may not require more than 3 bits!"); 00494 return ConvType | 00495 (AM << 2) | 00496 (isVolatile << 5) | 00497 ((Log2_32(Alignment) + 1) << 6); 00498 } 00499 00500 //===----------------------------------------------------------------------===// 00501 // SelectionDAG Class 00502 //===----------------------------------------------------------------------===// 00503 00504 /// doNotCSE - Return true if CSE should not be performed for this node. 00505 static bool doNotCSE(SDNode *N) { 00506 if (N->getValueType(0) == MVT::Flag) 00507 return true; // Never CSE anything that produces a flag. 00508 00509 switch (N->getOpcode()) { 00510 default: break; 00511 case ISD::HANDLENODE: 00512 case ISD::DBG_LABEL: 00513 case ISD::DBG_STOPPOINT: 00514 case ISD::EH_LABEL: 00515 case ISD::DECLARE: 00516 return true; // Never CSE these nodes. 00517 } 00518 00519 // Check that remaining values produced are not flags. 00520 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 00521 if (N->getValueType(i) == MVT::Flag) 00522 return true; // Never CSE anything that produces a flag. 00523 00524 return false; 00525 } 00526 00527 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 00528 /// SelectionDAG. 00529 void SelectionDAG::RemoveDeadNodes() { 00530 // Create a dummy node (which is not added to allnodes), that adds a reference 00531 // to the root node, preventing it from being deleted. 00532 HandleSDNode Dummy(getRoot()); 00533 00534 SmallVector<SDNode*, 128> DeadNodes; 00535 00536 // Add all obviously-dead nodes to the DeadNodes worklist. 00537 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) 00538 if (I->use_empty()) 00539 DeadNodes.push_back(I); 00540 00541 RemoveDeadNodes(DeadNodes); 00542 00543 // If the root changed (e.g. it was a dead load, update the root). 00544 setRoot(Dummy.getValue()); 00545 } 00546 00547 /// RemoveDeadNodes - This method deletes the unreachable nodes in the 00548 /// given list, and any nodes that become unreachable as a result. 00549 void SelectionDAG::RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes, 00550 DAGUpdateListener *UpdateListener) { 00551 00552 // Process the worklist, deleting the nodes and adding their uses to the 00553 // worklist. 00554 while (!DeadNodes.empty()) { 00555 SDNode *N = DeadNodes.pop_back_val(); 00556 00557 if (UpdateListener) 00558 UpdateListener->NodeDeleted(N, 0); 00559 00560 // Take the node out of the appropriate CSE map. 00561 RemoveNodeFromCSEMaps(N); 00562 00563 // Next, brutally remove the operand list. This is safe to do, as there are 00564 // no cycles in the graph. 00565 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) { 00566 SDUse &Use = *I++; 00567 SDNode *Operand = Use.getNode(); 00568 Use.set(SDValue()); 00569 00570 // Now that we removed this operand, see if there are no uses of it left. 00571 if (Operand->use_empty()) 00572 DeadNodes.push_back(Operand); 00573 } 00574 00575 DeallocateNode(N); 00576 } 00577 } 00578 00579 void SelectionDAG::RemoveDeadNode(SDNode *N, DAGUpdateListener *UpdateListener){ 00580 SmallVector<SDNode*, 16> DeadNodes(1, N); 00581 RemoveDeadNodes(DeadNodes, UpdateListener); 00582 } 00583 00584 void SelectionDAG::DeleteNode(SDNode *N) { 00585 // First take this out of the appropriate CSE map. 00586 RemoveNodeFromCSEMaps(N); 00587 00588 // Finally, remove uses due to operands of this node, remove from the 00589 // AllNodes list, and delete the node. 00590 DeleteNodeNotInCSEMaps(N); 00591 } 00592 00593 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { 00594 assert(N != AllNodes.begin() && "Cannot delete the entry node!"); 00595 assert(N->use_empty() && "Cannot delete a node that is not dead!"); 00596 00597 // Drop all of the operands and decrement used node's use counts. 00598 N->DropOperands(); 00599 00600 DeallocateNode(N); 00601 } 00602 00603 void SelectionDAG::DeallocateNode(SDNode *N) { 00604 if (N->OperandsNeedDelete) 00605 delete[] N->OperandList; 00606 00607 // Set the opcode to DELETED_NODE to help catch bugs when node 00608 // memory is reallocated. 00609 N->NodeType = ISD::DELETED_NODE; 00610 00611 NodeAllocator.Deallocate(AllNodes.remove(N)); 00612 } 00613 00614 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that 00615 /// correspond to it. This is useful when we're about to delete or repurpose 00616 /// the node. We don't want future request for structurally identical nodes 00617 /// to return N anymore. 00618 bool SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { 00619 bool Erased = false; 00620 switch (N->getOpcode()) { 00621 case ISD::EntryToken: 00622 llvm_unreachable("EntryToken should not be in CSEMaps!"); 00623 return false; 00624 case ISD::HANDLENODE: return false; // noop. 00625 case ISD::CONDCODE: 00626 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] && 00627 "Cond code doesn't exist!"); 00628 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0; 00629 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0; 00630 break; 00631 case ISD::ExternalSymbol: 00632 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 00633 break; 00634 case ISD::TargetExternalSymbol: { 00635 ExternalSymbolSDNode *ESN = cast<ExternalSymbolSDNode>(N); 00636 Erased = TargetExternalSymbols.erase( 00637 std::pair<std::string,unsigned char>(ESN->getSymbol(), 00638 ESN->getTargetFlags())); 00639 break; 00640 } 00641 case ISD::VALUETYPE: { 00642 EVT VT = cast<VTSDNode>(N)->getVT(); 00643 if (VT.isExtended()) { 00644 Erased = ExtendedValueTypeNodes.erase(VT); 00645 } else { 00646 Erased = ValueTypeNodes[VT.getSimpleVT().SimpleTy] != 0; 00647 ValueTypeNodes[VT.getSimpleVT().SimpleTy] = 0; 00648 } 00649 break; 00650 } 00651 default: 00652 // Remove it from the CSE Map. 00653 Erased = CSEMap.RemoveNode(N); 00654 break; 00655 } 00656 #ifndef NDEBUG 00657 // Verify that the node was actually in one of the CSE maps, unless it has a 00658 // flag result (which cannot be CSE'd) or is one of the special cases that are 00659 // not subject to CSE. 00660 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && 00661 !N->isMachineOpcode() && !doNotCSE(N)) { 00662 N->dump(this); 00663 cerr << "\n"; 00664 llvm_unreachable("Node is not in map!"); 00665 } 00666 #endif 00667 return Erased; 00668 } 00669 00670 /// AddModifiedNodeToCSEMaps - The specified node has been removed from the CSE 00671 /// maps and modified in place. Add it back to the CSE maps, unless an identical 00672 /// node already exists, in which case transfer all its users to the existing 00673 /// node. This transfer can potentially trigger recursive merging. 00674 /// 00675 void 00676 SelectionDAG::AddModifiedNodeToCSEMaps(SDNode *N, 00677 DAGUpdateListener *UpdateListener) { 00678 // For node types that aren't CSE'd, just act as if no identical node 00679 // already exists. 00680 if (!doNotCSE(N)) { 00681 SDNode *Existing = CSEMap.GetOrInsertNode(N); 00682 if (Existing != N) { 00683 // If there was already an existing matching node, use ReplaceAllUsesWith 00684 // to replace the dead one with the existing one. This can cause 00685 // recursive merging of other unrelated nodes down the line. 00686 ReplaceAllUsesWith(N, Existing, UpdateListener); 00687 00688 // N is now dead. Inform the listener if it exists and delete it. 00689 if (UpdateListener) 00690 UpdateListener->NodeDeleted(N, Existing); 00691 DeleteNodeNotInCSEMaps(N); 00692 return; 00693 } 00694 } 00695 00696 // If the node doesn't already exist, we updated it. Inform a listener if 00697 // it exists. 00698 if (UpdateListener) 00699 UpdateListener->NodeUpdated(N); 00700 } 00701 00702 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands 00703 /// were replaced with those specified. If this node is never memoized, 00704 /// return null, otherwise return a pointer to the slot it would take. If a 00705 /// node already exists with these operands, the slot will be non-null. 00706 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDValue Op, 00707 void *&InsertPos) { 00708 if (doNotCSE(N)) 00709 return 0; 00710 00711 SDValue Ops[] = { Op }; 00712 FoldingSetNodeID ID; 00713 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 1); 00714 AddNodeIDCustom(ID, N); 00715 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 00716 } 00717 00718 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands 00719 /// were replaced with those specified. If this node is never memoized, 00720 /// return null, otherwise return a pointer to the slot it would take. If a 00721 /// node already exists with these operands, the slot will be non-null. 00722 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 00723 SDValue Op1, SDValue Op2, 00724 void *&InsertPos) { 00725 if (doNotCSE(N)) 00726 return 0; 00727 00728 SDValue Ops[] = { Op1, Op2 }; 00729 FoldingSetNodeID ID; 00730 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, 2); 00731 AddNodeIDCustom(ID, N); 00732 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 00733 } 00734 00735 00736 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands 00737 /// were replaced with those specified. If this node is never memoized, 00738 /// return null, otherwise return a pointer to the slot it would take. If a 00739 /// node already exists with these operands, the slot will be non-null. 00740 SDNode *SelectionDAG::FindModifiedNodeSlot(SDNode *N, 00741 const SDValue *Ops,unsigned NumOps, 00742 void *&InsertPos) { 00743 if (doNotCSE(N)) 00744 return 0; 00745 00746 FoldingSetNodeID ID; 00747 AddNodeIDNode(ID, N->getOpcode(), N->getVTList(), Ops, NumOps); 00748 AddNodeIDCustom(ID, N); 00749 return CSEMap.FindNodeOrInsertPos(ID, InsertPos); 00750 } 00751 00752 /// VerifyNode - Sanity check the given node. Aborts if it is invalid. 00753 void SelectionDAG::VerifyNode(SDNode *N) { 00754 switch (N->getOpcode()) { 00755 default: 00756 break; 00757 case ISD::BUILD_PAIR: { 00758 EVT VT = N->getValueType(0); 00759 assert(N->getNumValues() == 1 && "Too many results!"); 00760 assert(!VT.isVector() && (VT.isInteger() || VT.isFloatingPoint()) && 00761 "Wrong return type!"); 00762 assert(N->getNumOperands() == 2 && "Wrong number of operands!"); 00763 assert(N->getOperand(0).getValueType() == N->getOperand(1).getValueType() && 00764 "Mismatched operand types!"); 00765 assert(N->getOperand(0).getValueType().isInteger() == VT.isInteger() && 00766 "Wrong operand type!"); 00767 assert(VT.getSizeInBits() == 2 * N->getOperand(0).getValueSizeInBits() && 00768 "Wrong return type size"); 00769 break; 00770 } 00771 case ISD::BUILD_VECTOR: { 00772 assert(N->getNumValues() == 1 && "Too many results!"); 00773 assert(N->getValueType(0).isVector() && "Wrong return type!"); 00774 assert(N->getNumOperands() == N->getValueType(0).getVectorNumElements() && 00775 "Wrong number of operands!"); 00776 EVT EltVT = N->getValueType(0).getVectorElementType(); 00777 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) 00778 assert((I->getValueType() == EltVT || 00779 (EltVT.isInteger() && I->getValueType().isInteger() && 00780 EltVT.bitsLE(I->getValueType()))) && 00781 "Wrong operand type!"); 00782 break; 00783 } 00784 } 00785 } 00786 00787 /// getEVTAlignment - Compute the default alignment value for the 00788 /// given type. 00789 /// 00790 unsigned SelectionDAG::getEVTAlignment(EVT VT) const { 00791 const Type *Ty = VT == MVT::iPTR ? 00792 PointerType::get(Type::getInt8Ty(*getContext()), 0) : 00793 VT.getTypeForEVT(*getContext()); 00794 00795 return TLI.getTargetData()->getABITypeAlignment(Ty); 00796 } 00797 00798 // EntryNode could meaningfully have debug info if we can find it... 00799 SelectionDAG::SelectionDAG(TargetLowering &tli, FunctionLoweringInfo &fli) 00800 : TLI(tli), FLI(fli), DW(0), 00801 EntryNode(ISD::EntryToken, DebugLoc::getUnknownLoc(), 00802 getVTList(MVT::Other)), Root(getEntryNode()) { 00803 AllNodes.push_back(&EntryNode); 00804 } 00805 00806 void SelectionDAG::init(MachineFunction &mf, MachineModuleInfo *mmi, 00807 DwarfWriter *dw) { 00808 MF = &mf; 00809 MMI = mmi; 00810 DW = dw; 00811 Context = &mf.getFunction()->getContext(); 00812 } 00813 00814 SelectionDAG::~SelectionDAG() { 00815 allnodes_clear(); 00816 } 00817 00818 void SelectionDAG::allnodes_clear() { 00819 assert(&*AllNodes.begin() == &EntryNode); 00820 AllNodes.remove(AllNodes.begin()); 00821 while (!AllNodes.empty()) 00822 DeallocateNode(AllNodes.begin()); 00823 } 00824 00825 void SelectionDAG::clear() { 00826 allnodes_clear(); 00827 OperandAllocator.Reset(); 00828 CSEMap.clear(); 00829 00830 ExtendedValueTypeNodes.clear(); 00831 ExternalSymbols.clear(); 00832 TargetExternalSymbols.clear(); 00833 std::fill(CondCodeNodes.begin(), CondCodeNodes.end(), 00834 static_cast<CondCodeSDNode*>(0)); 00835 std::fill(ValueTypeNodes.begin(), ValueTypeNodes.end(), 00836 static_cast<SDNode*>(0)); 00837 00838 EntryNode.UseList = 0; 00839 AllNodes.push_back(&EntryNode); 00840 Root = getEntryNode(); 00841 } 00842 00843 SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, DebugLoc DL, EVT VT) { 00844 if (Op.getValueType() == VT) return Op; 00845 APInt Imm = APInt::getLowBitsSet(Op.getValueSizeInBits(), 00846 VT.getSizeInBits()); 00847 return getNode(ISD::AND, DL, Op.getValueType(), Op, 00848 getConstant(Imm, Op.getValueType())); 00849 } 00850 00851 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1). 00852 /// 00853 SDValue SelectionDAG::getNOT(DebugLoc DL, SDValue Val, EVT VT) { 00854 EVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT; 00855 SDValue NegOne = 00856 getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT); 00857 return getNode(ISD::XOR, DL, VT, Val, NegOne); 00858 } 00859 00860 SDValue SelectionDAG::getConstant(uint64_t Val, EVT VT, bool isT) { 00861 EVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT; 00862 assert((EltVT.getSizeInBits() >= 64 || 00863 (uint64_t)((int64_t)Val >> EltVT.getSizeInBits()) + 1 < 2) && 00864 "getConstant with a uint64_t value that doesn't fit in the type!"); 00865 return getConstant(APInt(EltVT.getSizeInBits(), Val), VT, isT); 00866 } 00867 00868 SDValue SelectionDAG::getConstant(const APInt &Val, EVT VT, bool isT) { 00869 return getConstant(*ConstantInt::get(*Context, Val), VT, isT); 00870 } 00871 00872 SDValue SelectionDAG::getConstant(const ConstantInt &Val, EVT VT, bool isT) { 00873 assert(VT.isInteger() && "Cannot create FP integer constant!"); 00874 00875 EVT EltVT = VT.isVector() ? VT.getVectorElementType() : VT; 00876 assert(Val.getBitWidth() == EltVT.getSizeInBits() && 00877 "APInt size does not match type size!"); 00878 00879 unsigned Opc = isT ? ISD::TargetConstant : ISD::Constant; 00880 FoldingSetNodeID ID; 00881 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0); 00882 ID.AddPointer(&Val); 00883 void *IP = 0; 00884 SDNode *N = NULL; 00885 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) 00886 if (!VT.isVector()) 00887 return SDValue(N, 0); 00888 if (!N) { 00889 N = NodeAllocator.Allocate<ConstantSDNode>(); 00890 new (N) ConstantSDNode(isT, &Val, EltVT); 00891 CSEMap.InsertNode(N, IP); 00892 AllNodes.push_back(N); 00893 } 00894 00895 SDValue Result(N, 0); 00896 if (VT.isVector()) { 00897 SmallVector<SDValue, 8> Ops; 00898 Ops.assign(VT.getVectorNumElements(), Result); 00899 Result = getNode(ISD::BUILD_VECTOR, DebugLoc::getUnknownLoc(), 00900 VT, &Ops[0], Ops.size()); 00901 } 00902 return Result; 00903 } 00904 00905 SDValue SelectionDAG::getIntPtrConstant(uint64_t Val, bool isTarget) { 00906 return getConstant(Val, TLI.getPointerTy(), isTarget); 00907 } 00908 00909 00910 SDValue SelectionDAG::getConstantFP(const APFloat& V, EVT VT, bool isTarget) { 00911 return getConstantFP(*ConstantFP::get(*getContext(), V), VT, isTarget); 00912 } 00913 00914 SDValue SelectionDAG::getConstantFP(const ConstantFP& V, EVT VT, bool isTarget){ 00915 assert(VT.isFloatingPoint() && "Cannot create integer FP constant!"); 00916 00917 EVT EltVT = 00918 VT.isVector() ? VT.getVectorElementType() : VT; 00919 00920 // Do the map lookup using the actual bit pattern for the floating point 00921 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 00922 // we don't have issues with SNANs. 00923 unsigned Opc = isTarget ? ISD::TargetConstantFP : ISD::ConstantFP; 00924 FoldingSetNodeID ID; 00925 AddNodeIDNode(ID, Opc, getVTList(EltVT), 0, 0); 00926 ID.AddPointer(&V); 00927 void *IP = 0; 00928 SDNode *N = NULL; 00929 if ((N = CSEMap.FindNodeOrInsertPos(ID, IP))) 00930 if (!VT.isVector()) 00931 return SDValue(N, 0); 00932 if (!N) { 00933 N = NodeAllocator.Allocate<ConstantFPSDNode>(); 00934 new (N) ConstantFPSDNode(isTarget, &V, EltVT); 00935 CSEMap.InsertNode(N, IP); 00936 AllNodes.push_back(N); 00937 } 00938 00939 SDValue Result(N, 0); 00940 if (VT.isVector()) { 00941 SmallVector<SDValue, 8> Ops; 00942 Ops.assign(VT.getVectorNumElements(), Result); 00943 // FIXME DebugLoc info might be appropriate here 00944 Result = getNode(ISD::BUILD_VECTOR, DebugLoc::getUnknownLoc(), 00945 VT, &Ops[0], Ops.size()); 00946 } 00947 return Result; 00948 } 00949 00950 SDValue SelectionDAG::getConstantFP(double Val, EVT VT, bool isTarget) { 00951 EVT EltVT = 00952 VT.isVector() ? VT.getVectorElementType() : VT; 00953 if (EltVT==MVT::f32) 00954 return getConstantFP(APFloat((float)Val), VT, isTarget); 00955 else 00956 return getConstantFP(APFloat(Val), VT, isTarget); 00957 } 00958 00959 SDValue SelectionDAG::getGlobalAddress(const GlobalValue *GV, 00960 EVT VT, int64_t Offset, 00961 bool isTargetGA, 00962 unsigned char TargetFlags) { 00963 assert((TargetFlags == 0 || isTargetGA) && 00964 "Cannot set target flags on target-independent globals"); 00965 00966 // Truncate (with sign-extension) the offset value to the pointer size. 00967 EVT PTy = TLI.getPointerTy(); 00968 unsigned BitWidth = PTy.getSizeInBits(); 00969 if (BitWidth < 64) 00970 Offset = (Offset << (64 - BitWidth) >> (64 - BitWidth)); 00971 00972 const GlobalVariable *GVar = dyn_cast<GlobalVariable>(GV); 00973 if (!GVar) { 00974 // If GV is an alias then use the aliasee for determining thread-localness. 00975 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(GV)) 00976 GVar = dyn_cast_or_null<GlobalVariable>(GA->resolveAliasedGlobal(false)); 00977 } 00978 00979 unsigned Opc; 00980 if (GVar && GVar->isThreadLocal()) 00981 Opc = isTargetGA ? ISD::TargetGlobalTLSAddress : ISD::GlobalTLSAddress; 00982 else 00983 Opc = isTargetGA ? ISD::TargetGlobalAddress : ISD::GlobalAddress; 00984 00985 FoldingSetNodeID ID; 00986 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 00987 ID.AddPointer(GV); 00988 ID.AddInteger(Offset); 00989 ID.AddInteger(TargetFlags); 00990 void *IP = 0; 00991 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 00992 return SDValue(E, 0); 00993 SDNode *N = NodeAllocator.Allocate<GlobalAddressSDNode>(); 00994 new (N) GlobalAddressSDNode(Opc, GV, VT, Offset, TargetFlags); 00995 CSEMap.InsertNode(N, IP); 00996 AllNodes.push_back(N); 00997 return SDValue(N, 0); 00998 } 00999 01000 SDValue SelectionDAG::getFrameIndex(int FI, EVT VT, bool isTarget) { 01001 unsigned Opc = isTarget ? ISD::TargetFrameIndex : ISD::FrameIndex; 01002 FoldingSetNodeID ID; 01003 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 01004 ID.AddInteger(FI); 01005 void *IP = 0; 01006 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01007 return SDValue(E, 0); 01008 SDNode *N = NodeAllocator.Allocate<FrameIndexSDNode>(); 01009 new (N) FrameIndexSDNode(FI, VT, isTarget); 01010 CSEMap.InsertNode(N, IP); 01011 AllNodes.push_back(N); 01012 return SDValue(N, 0); 01013 } 01014 01015 SDValue SelectionDAG::getJumpTable(int JTI, EVT VT, bool isTarget, 01016 unsigned char TargetFlags) { 01017 assert((TargetFlags == 0 || isTarget) && 01018 "Cannot set target flags on target-independent jump tables"); 01019 unsigned Opc = isTarget ? ISD::TargetJumpTable : ISD::JumpTable; 01020 FoldingSetNodeID ID; 01021 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 01022 ID.AddInteger(JTI); 01023 ID.AddInteger(TargetFlags); 01024 void *IP = 0; 01025 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01026 return SDValue(E, 0); 01027 SDNode *N = NodeAllocator.Allocate<JumpTableSDNode>(); 01028 new (N) JumpTableSDNode(JTI, VT, isTarget, TargetFlags); 01029 CSEMap.InsertNode(N, IP); 01030 AllNodes.push_back(N); 01031 return SDValue(N, 0); 01032 } 01033 01034 SDValue SelectionDAG::getConstantPool(Constant *C, EVT VT, 01035 unsigned Alignment, int Offset, 01036 bool isTarget, 01037 unsigned char TargetFlags) { 01038 assert((TargetFlags == 0 || isTarget) && 01039 "Cannot set target flags on target-independent globals"); 01040 if (Alignment == 0) 01041 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType()); 01042 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 01043 FoldingSetNodeID ID; 01044 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 01045 ID.AddInteger(Alignment); 01046 ID.AddInteger(Offset); 01047 ID.AddPointer(C); 01048 ID.AddInteger(TargetFlags); 01049 void *IP = 0; 01050 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01051 return SDValue(E, 0); 01052 SDNode *N = NodeAllocator.Allocate<ConstantPoolSDNode>(); 01053 new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment, TargetFlags); 01054 CSEMap.InsertNode(N, IP); 01055 AllNodes.push_back(N); 01056 return SDValue(N, 0); 01057 } 01058 01059 01060 SDValue SelectionDAG::getConstantPool(MachineConstantPoolValue *C, EVT VT, 01061 unsigned Alignment, int Offset, 01062 bool isTarget, 01063 unsigned char TargetFlags) { 01064 assert((TargetFlags == 0 || isTarget) && 01065 "Cannot set target flags on target-independent globals"); 01066 if (Alignment == 0) 01067 Alignment = TLI.getTargetData()->getPrefTypeAlignment(C->getType()); 01068 unsigned Opc = isTarget ? ISD::TargetConstantPool : ISD::ConstantPool; 01069 FoldingSetNodeID ID; 01070 AddNodeIDNode(ID, Opc, getVTList(VT), 0, 0); 01071 ID.AddInteger(Alignment); 01072 ID.AddInteger(Offset); 01073 C->AddSelectionDAGCSEId(ID); 01074 ID.AddInteger(TargetFlags); 01075 void *IP = 0; 01076 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01077 return SDValue(E, 0); 01078 SDNode *N = NodeAllocator.Allocate<ConstantPoolSDNode>(); 01079 new (N) ConstantPoolSDNode(isTarget, C, VT, Offset, Alignment, TargetFlags); 01080 CSEMap.InsertNode(N, IP); 01081 AllNodes.push_back(N); 01082 return SDValue(N, 0); 01083 } 01084 01085 SDValue SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 01086 FoldingSetNodeID ID; 01087 AddNodeIDNode(ID, ISD::BasicBlock, getVTList(MVT::Other), 0, 0); 01088 ID.AddPointer(MBB); 01089 void *IP = 0; 01090 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01091 return SDValue(E, 0); 01092 SDNode *N = NodeAllocator.Allocate<BasicBlockSDNode>(); 01093 new (N) BasicBlockSDNode(MBB); 01094 CSEMap.InsertNode(N, IP); 01095 AllNodes.push_back(N); 01096 return SDValue(N, 0); 01097 } 01098 01099 SDValue SelectionDAG::getValueType(EVT VT) { 01100 if (VT.isSimple() && (unsigned)VT.getSimpleVT().SimpleTy >= 01101 ValueTypeNodes.size()) 01102 ValueTypeNodes.resize(VT.getSimpleVT().SimpleTy+1); 01103 01104 SDNode *&N = VT.isExtended() ? 01105 ExtendedValueTypeNodes[VT] : ValueTypeNodes[VT.getSimpleVT().SimpleTy]; 01106 01107 if (N) return SDValue(N, 0); 01108 N = NodeAllocator.Allocate<VTSDNode>(); 01109 new (N) VTSDNode(VT); 01110 AllNodes.push_back(N); 01111 return SDValue(N, 0); 01112 } 01113 01114 SDValue SelectionDAG::getExternalSymbol(const char *Sym, EVT VT) { 01115 SDNode *&N = ExternalSymbols[Sym]; 01116 if (N) return SDValue(N, 0); 01117 N = NodeAllocator.Allocate<ExternalSymbolSDNode>(); 01118 new (N) ExternalSymbolSDNode(false, Sym, 0, VT); 01119 AllNodes.push_back(N); 01120 return SDValue(N, 0); 01121 } 01122 01123 SDValue SelectionDAG::getTargetExternalSymbol(const char *Sym, EVT VT, 01124 unsigned char TargetFlags) { 01125 SDNode *&N = 01126 TargetExternalSymbols[std::pair<std::string,unsigned char>(Sym, 01127 TargetFlags)]; 01128 if (N) return SDValue(N, 0); 01129 N = NodeAllocator.Allocate<ExternalSymbolSDNode>(); 01130 new (N) ExternalSymbolSDNode(true, Sym, TargetFlags, VT); 01131 AllNodes.push_back(N); 01132 return SDValue(N, 0); 01133 } 01134 01135 SDValue SelectionDAG::getCondCode(ISD::CondCode Cond) { 01136 if ((unsigned)Cond >= CondCodeNodes.size()) 01137 CondCodeNodes.resize(Cond+1); 01138 01139 if (CondCodeNodes[Cond] == 0) { 01140 CondCodeSDNode *N = NodeAllocator.Allocate<CondCodeSDNode>(); 01141 new (N) CondCodeSDNode(Cond); 01142 CondCodeNodes[Cond] = N; 01143 AllNodes.push_back(N); 01144 } 01145 return SDValue(CondCodeNodes[Cond], 0); 01146 } 01147 01148 // commuteShuffle - swaps the values of N1 and N2, and swaps all indices in 01149 // the shuffle mask M that point at N1 to point at N2, and indices that point 01150 // N2 to point at N1. 01151 static void commuteShuffle(SDValue &N1, SDValue &N2, SmallVectorImpl<int> &M) { 01152 std::swap(N1, N2); 01153 int NElts = M.size(); 01154 for (int i = 0; i != NElts; ++i) { 01155 if (M[i] >= NElts) 01156 M[i] -= NElts; 01157 else if (M[i] >= 0) 01158 M[i] += NElts; 01159 } 01160 } 01161 01162 SDValue SelectionDAG::getVectorShuffle(EVT VT, DebugLoc dl, SDValue N1, 01163 SDValue N2, const int *Mask) { 01164 assert(N1.getValueType() == N2.getValueType() && "Invalid VECTOR_SHUFFLE"); 01165 assert(VT.isVector() && N1.getValueType().isVector() && 01166 "Vector Shuffle VTs must be a vectors"); 01167 assert(VT.getVectorElementType() == N1.getValueType().getVectorElementType() 01168 && "Vector Shuffle VTs must have same element type"); 01169 01170 // Canonicalize shuffle undef, undef -> undef 01171 if (N1.getOpcode() == ISD::UNDEF && N2.getOpcode() == ISD::UNDEF) 01172 return getUNDEF(VT); 01173 01174 // Validate that all indices in Mask are within the range of the elements 01175 // input to the shuffle. 01176 unsigned NElts = VT.getVectorNumElements(); 01177 SmallVector<int, 8> MaskVec; 01178 for (unsigned i = 0; i != NElts; ++i) { 01179 assert(Mask[i] < (int)(NElts * 2) && "Index out of range"); 01180 MaskVec.push_back(Mask[i]); 01181 } 01182 01183 // Canonicalize shuffle v, v -> v, undef 01184 if (N1 == N2) { 01185 N2 = getUNDEF(VT); 01186 for (unsigned i = 0; i != NElts; ++i) 01187 if (MaskVec[i] >= (int)NElts) MaskVec[i] -= NElts; 01188 } 01189 01190 // Canonicalize shuffle undef, v -> v, undef. Commute the shuffle mask. 01191 if (N1.getOpcode() == ISD::UNDEF) 01192 commuteShuffle(N1, N2, MaskVec); 01193 01194 // Canonicalize all index into lhs, -> shuffle lhs, undef 01195 // Canonicalize all index into rhs, -> shuffle rhs, undef 01196 bool AllLHS = true, AllRHS = true; 01197 bool N2Undef = N2.getOpcode() == ISD::UNDEF; 01198 for (unsigned i = 0; i != NElts; ++i) { 01199 if (MaskVec[i] >= (int)NElts) { 01200 if (N2Undef) 01201 MaskVec[i] = -1; 01202 else 01203 AllLHS = false; 01204 } else if (MaskVec[i] >= 0) { 01205 AllRHS = false; 01206 } 01207 } 01208 if (AllLHS && AllRHS) 01209 return getUNDEF(VT); 01210 if (AllLHS && !N2Undef) 01211 N2 = getUNDEF(VT); 01212 if (AllRHS) { 01213 N1 = getUNDEF(VT); 01214 commuteShuffle(N1, N2, MaskVec); 01215 } 01216 01217 // If Identity shuffle, or all shuffle in to undef, return that node. 01218 bool AllUndef = true; 01219 bool Identity = true; 01220 for (unsigned i = 0; i != NElts; ++i) { 01221 if (MaskVec[i] >= 0 && MaskVec[i] != (int)i) Identity = false; 01222 if (MaskVec[i] >= 0) AllUndef = false; 01223 } 01224 if (Identity && NElts == N1.getValueType().getVectorNumElements()) 01225 return N1; 01226 if (AllUndef) 01227 return getUNDEF(VT); 01228 01229 FoldingSetNodeID ID; 01230 SDValue Ops[2] = { N1, N2 }; 01231 AddNodeIDNode(ID, ISD::VECTOR_SHUFFLE, getVTList(VT), Ops, 2); 01232 for (unsigned i = 0; i != NElts; ++i) 01233 ID.AddInteger(MaskVec[i]); 01234 01235 void* IP = 0; 01236 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01237 return SDValue(E, 0); 01238 01239 // Allocate the mask array for the node out of the BumpPtrAllocator, since 01240 // SDNode doesn't have access to it. This memory will be "leaked" when 01241 // the node is deallocated, but recovered when the NodeAllocator is released. 01242 int *MaskAlloc = OperandAllocator.Allocate<int>(NElts); 01243 memcpy(MaskAlloc, &MaskVec[0], NElts * sizeof(int)); 01244 01245 ShuffleVectorSDNode *N = NodeAllocator.Allocate<ShuffleVectorSDNode>(); 01246 new (N) ShuffleVectorSDNode(VT, dl, N1, N2, MaskAlloc); 01247 CSEMap.InsertNode(N, IP); 01248 AllNodes.push_back(N); 01249 return SDValue(N, 0); 01250 } 01251 01252 SDValue SelectionDAG::getConvertRndSat(EVT VT, DebugLoc dl, 01253 SDValue Val, SDValue DTy, 01254 SDValue STy, SDValue Rnd, SDValue Sat, 01255 ISD::CvtCode Code) { 01256 // If the src and dest types are the same and the conversion is between 01257 // integer types of the same sign or two floats, no conversion is necessary. 01258 if (DTy == STy && 01259 (Code == ISD::CVT_UU || Code == ISD::CVT_SS || Code == ISD::CVT_FF)) 01260 return Val; 01261 01262 FoldingSetNodeID ID; 01263 void* IP = 0; 01264 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01265 return SDValue(E, 0); 01266 CvtRndSatSDNode *N = NodeAllocator.Allocate<CvtRndSatSDNode>(); 01267 SDValue Ops[] = { Val, DTy, STy, Rnd, Sat }; 01268 new (N) CvtRndSatSDNode(VT, dl, Ops, 5, Code); 01269 CSEMap.InsertNode(N, IP); 01270 AllNodes.push_back(N); 01271 return SDValue(N, 0); 01272 } 01273 01274 SDValue SelectionDAG::getRegister(unsigned RegNo, EVT VT) { 01275 FoldingSetNodeID ID; 01276 AddNodeIDNode(ID, ISD::Register, getVTList(VT), 0, 0); 01277 ID.AddInteger(RegNo); 01278 void *IP = 0; 01279 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01280 return SDValue(E, 0); 01281 SDNode *N = NodeAllocator.Allocate<RegisterSDNode>(); 01282 new (N) RegisterSDNode(RegNo, VT); 01283 CSEMap.InsertNode(N, IP); 01284 AllNodes.push_back(N); 01285 return SDValue(N, 0); 01286 } 01287 01288 SDValue SelectionDAG::getDbgStopPoint(DebugLoc DL, SDValue Root, 01289 unsigned Line, unsigned Col, 01290 Value *CU) { 01291 SDNode *N = NodeAllocator.Allocate<DbgStopPointSDNode>(); 01292 new (N) DbgStopPointSDNode(Root, Line, Col, CU); 01293 N->setDebugLoc(DL); 01294 AllNodes.push_back(N); 01295 return SDValue(N, 0); 01296 } 01297 01298 SDValue SelectionDAG::getLabel(unsigned Opcode, DebugLoc dl, 01299 SDValue Root, 01300 unsigned LabelID) { 01301 FoldingSetNodeID ID; 01302 SDValue Ops[] = { Root }; 01303 AddNodeIDNode(ID, Opcode, getVTList(MVT::Other), &Ops[0], 1); 01304 ID.AddInteger(LabelID); 01305 void *IP = 0; 01306 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01307 return SDValue(E, 0); 01308 SDNode *N = NodeAllocator.Allocate<LabelSDNode>(); 01309 new (N) LabelSDNode(Opcode, dl, Root, LabelID); 01310 CSEMap.InsertNode(N, IP); 01311 AllNodes.push_back(N); 01312 return SDValue(N, 0); 01313 } 01314 01315 SDValue SelectionDAG::getSrcValue(const Value *V) { 01316 assert((!V || isa<PointerType>(V->getType())) && 01317 "SrcValue is not a pointer?"); 01318 01319 FoldingSetNodeID ID; 01320 AddNodeIDNode(ID, ISD::SRCVALUE, getVTList(MVT::Other), 0, 0); 01321 ID.AddPointer(V); 01322 01323 void *IP = 0; 01324 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01325 return SDValue(E, 0); 01326 01327 SDNode *N = NodeAllocator.Allocate<SrcValueSDNode>(); 01328 new (N) SrcValueSDNode(V); 01329 CSEMap.InsertNode(N, IP); 01330 AllNodes.push_back(N); 01331 return SDValue(N, 0); 01332 } 01333 01334 SDValue SelectionDAG::getMemOperand(const MachineMemOperand &MO) { 01335 #ifndef NDEBUG 01336 const Value *v = MO.getValue(); 01337 assert((!v || isa<PointerType>(v->getType())) && 01338 "SrcValue is not a pointer?"); 01339 #endif 01340 01341 FoldingSetNodeID ID; 01342 AddNodeIDNode(ID, ISD::MEMOPERAND, getVTList(MVT::Other), 0, 0); 01343 MO.Profile(ID); 01344 01345 void *IP = 0; 01346 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 01347 return SDValue(E, 0); 01348 01349 SDNode *N = NodeAllocator.Allocate<MemOperandSDNode>(); 01350 new (N) MemOperandSDNode(MO); 01351 CSEMap.InsertNode(N, IP); 01352 AllNodes.push_back(N); 01353 return SDValue(N, 0); 01354 } 01355 01356 /// getShiftAmountOperand - Return the specified value casted to 01357 /// the target's desired shift amount type. 01358 SDValue SelectionDAG::getShiftAmountOperand(SDValue Op) { 01359 EVT OpTy = Op.getValueType(); 01360 MVT ShTy = TLI.getShiftAmountTy(); 01361 if (OpTy == ShTy || OpTy.isVector()) return Op; 01362 01363 ISD::NodeType Opcode = OpTy.bitsGT(ShTy) ? ISD::TRUNCATE : ISD::ZERO_EXTEND; 01364 return getNode(Opcode, Op.getDebugLoc(), ShTy, Op); 01365 } 01366 01367 /// CreateStackTemporary - Create a stack temporary, suitable for holding the 01368 /// specified value type. 01369 SDValue SelectionDAG::CreateStackTemporary(EVT VT, unsigned minAlign) { 01370 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo(); 01371 unsigned ByteSize = VT.getStoreSizeInBits()/8; 01372 const Type *Ty = VT.getTypeForEVT(*getContext()); 01373 unsigned StackAlign = 01374 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), minAlign); 01375 01376 int FrameIdx = FrameInfo->CreateStackObject(ByteSize, StackAlign); 01377 return getFrameIndex(FrameIdx, TLI.getPointerTy()); 01378 } 01379 01380 /// CreateStackTemporary - Create a stack temporary suitable for holding 01381 /// either of the specified value types. 01382 SDValue SelectionDAG::CreateStackTemporary(EVT VT1, EVT VT2) { 01383 unsigned Bytes = std::max(VT1.getStoreSizeInBits(), 01384 VT2.getStoreSizeInBits())/8; 01385 const Type *Ty1 = VT1.getTypeForEVT(*getContext()); 01386 const Type *Ty2 = VT2.getTypeForEVT(*getContext()); 01387 const TargetData *TD = TLI.getTargetData(); 01388 unsigned Align = std::max(TD->getPrefTypeAlignment(Ty1), 01389 TD->getPrefTypeAlignment(Ty2)); 01390 01391 MachineFrameInfo *FrameInfo = getMachineFunction().getFrameInfo(); 01392 int FrameIdx = FrameInfo->CreateStackObject(Bytes, Align); 01393 return getFrameIndex(FrameIdx, TLI.getPointerTy()); 01394 } 01395 01396 SDValue SelectionDAG::FoldSetCC(EVT VT, SDValue N1, 01397 SDValue N2, ISD::CondCode Cond, DebugLoc dl) { 01398 // These setcc operations always fold. 01399 switch (Cond) { 01400 default: break; 01401 case ISD::SETFALSE: 01402 case ISD::SETFALSE2: return getConstant(0, VT); 01403 case ISD::SETTRUE: 01404 case ISD::SETTRUE2: return getConstant(1, VT); 01405 01406 case ISD::SETOEQ: 01407 case ISD::SETOGT: 01408 case ISD::SETOGE: 01409 case ISD::SETOLT: 01410 case ISD::SETOLE: 01411 case ISD::SETONE: 01412 case ISD::SETO: 01413 case ISD::SETUO: 01414 case ISD::SETUEQ: 01415 case ISD::SETUNE: 01416 assert(!N1.getValueType().isInteger() && "Illegal setcc for integer!"); 01417 break; 01418 } 01419 01420 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode())) { 01421 const APInt &C2 = N2C->getAPIntValue(); 01422 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) { 01423 const APInt &C1 = N1C->getAPIntValue(); 01424 01425 switch (Cond) { 01426 default: llvm_unreachable("Unknown integer setcc!"); 01427 case ISD::SETEQ: return getConstant(C1 == C2, VT); 01428 case ISD::SETNE: return getConstant(C1 != C2, VT); 01429 case ISD::SETULT: return getConstant(C1.ult(C2), VT); 01430 case ISD::SETUGT: return getConstant(C1.ugt(C2), VT); 01431 case ISD::SETULE: return getConstant(C1.ule(C2), VT); 01432 case ISD::SETUGE: return getConstant(C1.uge(C2), VT); 01433 case ISD::SETLT: return getConstant(C1.slt(C2), VT); 01434 case ISD::SETGT: return getConstant(C1.sgt(C2), VT); 01435 case ISD::SETLE: return getConstant(C1.sle(C2), VT); 01436 case ISD::SETGE: return getConstant(C1.sge(C2), VT); 01437 } 01438 } 01439 } 01440 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.getNode())) { 01441 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.getNode())) { 01442 // No compile time operations on this type yet. 01443 if (N1C->getValueType(0) == MVT::ppcf128) 01444 return SDValue(); 01445 01446 APFloat::cmpResult R = N1C->getValueAPF().compare(N2C->getValueAPF()); 01447 switch (Cond) { 01448 default: break; 01449 case ISD::SETEQ: if (R==APFloat::cmpUnordered) 01450 return getUNDEF(VT); 01451 // fall through 01452 case ISD::SETOEQ: return getConstant(R==APFloat::cmpEqual, VT); 01453 case ISD::SETNE: if (R==APFloat::cmpUnordered) 01454 return getUNDEF(VT); 01455 // fall through 01456 case ISD::SETONE: return getConstant(R==APFloat::cmpGreaterThan || 01457 R==APFloat::cmpLessThan, VT); 01458 case ISD::SETLT: if (R==APFloat::cmpUnordered) 01459 return getUNDEF(VT); 01460 // fall through 01461 case ISD::SETOLT: return getConstant(R==APFloat::cmpLessThan, VT); 01462 case ISD::SETGT: if (R==APFloat::cmpUnordered) 01463 return getUNDEF(VT); 01464 // fall through 01465 case ISD::SETOGT: return getConstant(R==APFloat::cmpGreaterThan, VT); 01466 case ISD::SETLE: if (R==APFloat::cmpUnordered) 01467 return getUNDEF(VT); 01468 // fall through 01469 case ISD::SETOLE: return getConstant(R==APFloat::cmpLessThan || 01470 R==APFloat::cmpEqual, VT); 01471 case ISD::SETGE: if (R==APFloat::cmpUnordered) 01472 return getUNDEF(VT); 01473 // fall through 01474 case ISD::SETOGE: return getConstant(R==APFloat::cmpGreaterThan || 01475 R==APFloat::cmpEqual, VT); 01476 case ISD::SETO: return getConstant(R!=APFloat::cmpUnordered, VT); 01477 case ISD::SETUO: return getConstant(R==APFloat::cmpUnordered, VT); 01478 case ISD::SETUEQ: return getConstant(R==APFloat::cmpUnordered || 01479 R==APFloat::cmpEqual, VT); 01480 case ISD::SETUNE: return getConstant(R!=APFloat::cmpEqual, VT); 01481 case ISD::SETULT: return getConstant(R==APFloat::cmpUnordered || 01482 R==APFloat::cmpLessThan, VT); 01483 case ISD::SETUGT: return getConstant(R==APFloat::cmpGreaterThan || 01484 R==APFloat::cmpUnordered, VT); 01485 case ISD::SETULE: return getConstant(R!=APFloat::cmpGreaterThan, VT); 01486 case ISD::SETUGE: return getConstant(R!=APFloat::cmpLessThan, VT); 01487 } 01488 } else { 01489 // Ensure that the constant occurs on the RHS. 01490 return getSetCC(dl, VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 01491 } 01492 } 01493 01494 // Could not fold it. 01495 return SDValue(); 01496 } 01497 01498 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero. We 01499 /// use this predicate to simplify operations downstream. 01500 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const { 01501 // This predicate is not safe for vector operations. 01502 if (Op.getValueType().isVector()) 01503 return false; 01504 01505 unsigned BitWidth = Op.getValueSizeInBits(); 01506 return MaskedValueIsZero(Op, APInt::getSignBit(BitWidth), Depth); 01507 } 01508 01509 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use 01510 /// this predicate to simplify operations downstream. Mask is known to be zero 01511 /// for bits that V cannot have. 01512 bool SelectionDAG::MaskedValueIsZero(SDValue Op, const APInt &Mask, 01513 unsigned Depth) const { 01514 APInt KnownZero, KnownOne; 01515 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 01516 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01517 return (KnownZero & Mask) == Mask; 01518 } 01519 01520 /// ComputeMaskedBits - Determine which of the bits specified in Mask are 01521 /// known to be either zero or one and return them in the KnownZero/KnownOne 01522 /// bitsets. This code only analyzes bits in Mask, in order to short-circuit 01523 /// processing. 01524 void SelectionDAG::ComputeMaskedBits(SDValue Op, const APInt &Mask, 01525 APInt &KnownZero, APInt &KnownOne, 01526 unsigned Depth) const { 01527 unsigned BitWidth = Mask.getBitWidth(); 01528 assert(BitWidth == Op.getValueType().getSizeInBits() && 01529 "Mask size mismatches value type size!"); 01530 01531 KnownZero = KnownOne = APInt(BitWidth, 0); // Don't know anything. 01532 if (Depth == 6 || Mask == 0) 01533 return; // Limit search depth. 01534 01535 APInt KnownZero2, KnownOne2; 01536 01537 switch (Op.getOpcode()) { 01538 case ISD::Constant: 01539 // We know all of the bits for a constant! 01540 KnownOne = cast<ConstantSDNode>(Op)->getAPIntValue() & Mask; 01541 KnownZero = ~KnownOne & Mask; 01542 return; 01543 case ISD::AND: 01544 // If either the LHS or the RHS are Zero, the result is zero. 01545 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 01546 ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownZero, 01547 KnownZero2, KnownOne2, Depth+1); 01548 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01549 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 01550 01551 // Output known-1 bits are only known if set in both the LHS & RHS. 01552 KnownOne &= KnownOne2; 01553 // Output known-0 are known to be clear if zero in either the LHS | RHS. 01554 KnownZero |= KnownZero2; 01555 return; 01556 case ISD::OR: 01557 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 01558 ComputeMaskedBits(Op.getOperand(0), Mask & ~KnownOne, 01559 KnownZero2, KnownOne2, Depth+1); 01560 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01561 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 01562 01563 // Output known-0 bits are only known if clear in both the LHS & RHS. 01564 KnownZero &= KnownZero2; 01565 // Output known-1 are known to be set if set in either the LHS | RHS. 01566 KnownOne |= KnownOne2; 01567 return; 01568 case ISD::XOR: { 01569 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 01570 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero2, KnownOne2, Depth+1); 01571 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01572 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 01573 01574 // Output known-0 bits are known if clear or set in both the LHS & RHS. 01575 APInt KnownZeroOut = (KnownZero & KnownZero2) | (KnownOne & KnownOne2); 01576 // Output known-1 are known to be set if set in only one of the LHS, RHS. 01577 KnownOne = (KnownZero & KnownOne2) | (KnownOne & KnownZero2); 01578 KnownZero = KnownZeroOut; 01579 return; 01580 } 01581 case ISD::MUL: { 01582 APInt Mask2 = APInt::getAllOnesValue(BitWidth); 01583 ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero, KnownOne, Depth+1); 01584 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1); 01585 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01586 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 01587 01588 // If low bits are zero in either operand, output low known-0 bits. 01589 // Also compute a conserative estimate for high known-0 bits. 01590 // More trickiness is possible, but this is sufficient for the 01591 // interesting case of alignment computation. 01592 KnownOne.clear(); 01593 unsigned TrailZ = KnownZero.countTrailingOnes() + 01594 KnownZero2.countTrailingOnes(); 01595 unsigned LeadZ = std::max(KnownZero.countLeadingOnes() + 01596 KnownZero2.countLeadingOnes(), 01597 BitWidth) - BitWidth; 01598 01599 TrailZ = std::min(TrailZ, BitWidth); 01600 LeadZ = std::min(LeadZ, BitWidth); 01601 KnownZero = APInt::getLowBitsSet(BitWidth, TrailZ) | 01602 APInt::getHighBitsSet(BitWidth, LeadZ); 01603 KnownZero &= Mask; 01604 return; 01605 } 01606 case ISD::UDIV: { 01607 // For the purposes of computing leading zeros we can conservatively 01608 // treat a udiv as a logical right shift by the power of 2 known to 01609 // be less than the denominator. 01610 APInt AllOnes = APInt::getAllOnesValue(BitWidth); 01611 ComputeMaskedBits(Op.getOperand(0), 01612 AllOnes, KnownZero2, KnownOne2, Depth+1); 01613 unsigned LeadZ = KnownZero2.countLeadingOnes(); 01614 01615 KnownOne2.clear(); 01616 KnownZero2.clear(); 01617 ComputeMaskedBits(Op.getOperand(1), 01618 AllOnes, KnownZero2, KnownOne2, Depth+1); 01619 unsigned RHSUnknownLeadingOnes = KnownOne2.countLeadingZeros(); 01620 if (RHSUnknownLeadingOnes != BitWidth) 01621 LeadZ = std::min(BitWidth, 01622 LeadZ + BitWidth - RHSUnknownLeadingOnes - 1); 01623 01624 KnownZero = APInt::getHighBitsSet(BitWidth, LeadZ) & Mask; 01625 return; 01626 } 01627 case ISD::SELECT: 01628 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero, KnownOne, Depth+1); 01629 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero2, KnownOne2, Depth+1); 01630 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01631 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 01632 01633 // Only known if known in both the LHS and RHS. 01634 KnownOne &= KnownOne2; 01635 KnownZero &= KnownZero2; 01636 return; 01637 case ISD::SELECT_CC: 01638 ComputeMaskedBits(Op.getOperand(3), Mask, KnownZero, KnownOne, Depth+1); 01639 ComputeMaskedBits(Op.getOperand(2), Mask, KnownZero2, KnownOne2, Depth+1); 01640 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01641 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 01642 01643 // Only known if known in both the LHS and RHS. 01644 KnownOne &= KnownOne2; 01645 KnownZero &= KnownZero2; 01646 return; 01647 case ISD::SADDO: 01648 case ISD::UADDO: 01649 case ISD::SSUBO: 01650 case ISD::USUBO: 01651 case ISD::SMULO: 01652 case ISD::UMULO: 01653 if (Op.getResNo() != 1) 01654 return; 01655 // The boolean result conforms to getBooleanContents. Fall through. 01656 case ISD::SETCC: 01657 // If we know the result of a setcc has the top bits zero, use this info. 01658 if (TLI.getBooleanContents() == TargetLowering::ZeroOrOneBooleanContent && 01659 BitWidth > 1) 01660 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - 1); 01661 return; 01662 case ISD::SHL: 01663 // (shl X, C1) & C2 == 0 iff (X & C2 >>u C1) == 0 01664 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 01665 unsigned ShAmt = SA->getZExtValue(); 01666 01667 // If the shift count is an invalid immediate, don't do anything. 01668 if (ShAmt >= BitWidth) 01669 return; 01670 01671 ComputeMaskedBits(Op.getOperand(0), Mask.lshr(ShAmt), 01672 KnownZero, KnownOne, Depth+1); 01673 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01674 KnownZero <<= ShAmt; 01675 KnownOne <<= ShAmt; 01676 // low bits known zero. 01677 KnownZero |= APInt::getLowBitsSet(BitWidth, ShAmt); 01678 } 01679 return; 01680 case ISD::SRL: 01681 // (ushr X, C1) & C2 == 0 iff (-1 >> C1) & C2 == 0 01682 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 01683 unsigned ShAmt = SA->getZExtValue(); 01684 01685 // If the shift count is an invalid immediate, don't do anything. 01686 if (ShAmt >= BitWidth) 01687 return; 01688 01689 ComputeMaskedBits(Op.getOperand(0), (Mask << ShAmt), 01690 KnownZero, KnownOne, Depth+1); 01691 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01692 KnownZero = KnownZero.lshr(ShAmt); 01693 KnownOne = KnownOne.lshr(ShAmt); 01694 01695 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask; 01696 KnownZero |= HighBits; // High bits known zero. 01697 } 01698 return; 01699 case ISD::SRA: 01700 if (ConstantSDNode *SA = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 01701 unsigned ShAmt = SA->getZExtValue(); 01702 01703 // If the shift count is an invalid immediate, don't do anything. 01704 if (ShAmt >= BitWidth) 01705 return; 01706 01707 APInt InDemandedMask = (Mask << ShAmt); 01708 // If any of the demanded bits are produced by the sign extension, we also 01709 // demand the input sign bit. 01710 APInt HighBits = APInt::getHighBitsSet(BitWidth, ShAmt) & Mask; 01711 if (HighBits.getBoolValue()) 01712 InDemandedMask |= APInt::getSignBit(BitWidth); 01713 01714 ComputeMaskedBits(Op.getOperand(0), InDemandedMask, KnownZero, KnownOne, 01715 Depth+1); 01716 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01717 KnownZero = KnownZero.lshr(ShAmt); 01718 KnownOne = KnownOne.lshr(ShAmt); 01719 01720 // Handle the sign bits. 01721 APInt SignBit = APInt::getSignBit(BitWidth); 01722 SignBit = SignBit.lshr(ShAmt); // Adjust to where it is now in the mask. 01723 01724 if (KnownZero.intersects(SignBit)) { 01725 KnownZero |= HighBits; // New bits are known zero. 01726 } else if (KnownOne.intersects(SignBit)) { 01727 KnownOne |= HighBits; // New bits are known one. 01728 } 01729 } 01730 return; 01731 case ISD::SIGN_EXTEND_INREG: { 01732 EVT EVT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 01733 unsigned EBits = EVT.getSizeInBits(); 01734 01735 // Sign extension. Compute the demanded bits in the result that are not 01736 // present in the input. 01737 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - EBits) & Mask; 01738 01739 APInt InSignBit = APInt::getSignBit(EBits); 01740 APInt InputDemandedBits = Mask & APInt::getLowBitsSet(BitWidth, EBits); 01741 01742 // If the sign extended bits are demanded, we know that the sign 01743 // bit is demanded. 01744 InSignBit.zext(BitWidth); 01745 if (NewBits.getBoolValue()) 01746 InputDemandedBits |= InSignBit; 01747 01748 ComputeMaskedBits(Op.getOperand(0), InputDemandedBits, 01749 KnownZero, KnownOne, Depth+1); 01750 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01751 01752 // If the sign bit of the input is known set or clear, then we know the 01753 // top bits of the result. 01754 if (KnownZero.intersects(InSignBit)) { // Input sign bit known clear 01755 KnownZero |= NewBits; 01756 KnownOne &= ~NewBits; 01757 } else if (KnownOne.intersects(InSignBit)) { // Input sign bit known set 01758 KnownOne |= NewBits; 01759 KnownZero &= ~NewBits; 01760 } else { // Input sign bit unknown 01761 KnownZero &= ~NewBits; 01762 KnownOne &= ~NewBits; 01763 } 01764 return; 01765 } 01766 case ISD::CTTZ: 01767 case ISD::CTLZ: 01768 case ISD::CTPOP: { 01769 unsigned LowBits = Log2_32(BitWidth)+1; 01770 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - LowBits); 01771 KnownOne.clear(); 01772 return; 01773 } 01774 case ISD::LOAD: { 01775 if (ISD::isZEXTLoad(Op.getNode())) { 01776 LoadSDNode *LD = cast<LoadSDNode>(Op); 01777 EVT VT = LD->getMemoryVT(); 01778 unsigned MemBits = VT.getSizeInBits(); 01779 KnownZero |= APInt::getHighBitsSet(BitWidth, BitWidth - MemBits) & Mask; 01780 } 01781 return; 01782 } 01783 case ISD::ZERO_EXTEND: { 01784 EVT InVT = Op.getOperand(0).getValueType(); 01785 unsigned InBits = InVT.getSizeInBits(); 01786 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask; 01787 APInt InMask = Mask; 01788 InMask.trunc(InBits); 01789 KnownZero.trunc(InBits); 01790 KnownOne.trunc(InBits); 01791 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1); 01792 KnownZero.zext(BitWidth); 01793 KnownOne.zext(BitWidth); 01794 KnownZero |= NewBits; 01795 return; 01796 } 01797 case ISD::SIGN_EXTEND: { 01798 EVT InVT = Op.getOperand(0).getValueType(); 01799 unsigned InBits = InVT.getSizeInBits(); 01800 APInt InSignBit = APInt::getSignBit(InBits); 01801 APInt NewBits = APInt::getHighBitsSet(BitWidth, BitWidth - InBits) & Mask; 01802 APInt InMask = Mask; 01803 InMask.trunc(InBits); 01804 01805 // If any of the sign extended bits are demanded, we know that the sign 01806 // bit is demanded. Temporarily set this bit in the mask for our callee. 01807 if (NewBits.getBoolValue()) 01808 InMask |= InSignBit; 01809 01810 KnownZero.trunc(InBits); 01811 KnownOne.trunc(InBits); 01812 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1); 01813 01814 // Note if the sign bit is known to be zero or one. 01815 bool SignBitKnownZero = KnownZero.isNegative(); 01816 bool SignBitKnownOne = KnownOne.isNegative(); 01817 assert(!(SignBitKnownZero && SignBitKnownOne) && 01818 "Sign bit can't be known to be both zero and one!"); 01819 01820 // If the sign bit wasn't actually demanded by our caller, we don't 01821 // want it set in the KnownZero and KnownOne result values. Reset the 01822 // mask and reapply it to the result values. 01823 InMask = Mask; 01824 InMask.trunc(InBits); 01825 KnownZero &= InMask; 01826 KnownOne &= InMask; 01827 01828 KnownZero.zext(BitWidth); 01829 KnownOne.zext(BitWidth); 01830 01831 // If the sign bit is known zero or one, the top bits match. 01832 if (SignBitKnownZero) 01833 KnownZero |= NewBits; 01834 else if (SignBitKnownOne) 01835 KnownOne |= NewBits; 01836 return; 01837 } 01838 case ISD::ANY_EXTEND: { 01839 EVT InVT = Op.getOperand(0).getValueType(); 01840 unsigned InBits = InVT.getSizeInBits(); 01841 APInt InMask = Mask; 01842 InMask.trunc(InBits); 01843 KnownZero.trunc(InBits); 01844 KnownOne.trunc(InBits); 01845 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1); 01846 KnownZero.zext(BitWidth); 01847 KnownOne.zext(BitWidth); 01848 return; 01849 } 01850 case ISD::TRUNCATE: { 01851 EVT InVT = Op.getOperand(0).getValueType(); 01852 unsigned InBits = InVT.getSizeInBits(); 01853 APInt InMask = Mask; 01854 InMask.zext(InBits); 01855 KnownZero.zext(InBits); 01856 KnownOne.zext(InBits); 01857 ComputeMaskedBits(Op.getOperand(0), InMask, KnownZero, KnownOne, Depth+1); 01858 assert((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"); 01859 KnownZero.trunc(BitWidth); 01860 KnownOne.trunc(BitWidth); 01861 break; 01862 } 01863 case ISD::AssertZext: { 01864 EVT VT = cast<VTSDNode>(Op.getOperand(1))->getVT(); 01865 APInt InMask = APInt::getLowBitsSet(BitWidth, VT.getSizeInBits()); 01866 ComputeMaskedBits(Op.getOperand(0), Mask & InMask, KnownZero, 01867 KnownOne, Depth+1); 01868 KnownZero |= (~InMask) & Mask; 01869 return; 01870 } 01871 case ISD::FGETSIGN: 01872 // All bits are zero except the low bit. 01873 KnownZero = APInt::getHighBitsSet(BitWidth, BitWidth - 1); 01874 return; 01875 01876 case ISD::SUB: { 01877 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) { 01878 // We know that the top bits of C-X are clear if X contains less bits 01879 // than C (i.e. no wrap-around can happen). For example, 20-X is 01880 // positive if we can prove that X is >= 0 and < 16. 01881 if (CLHS->getAPIntValue().isNonNegative()) { 01882 unsigned NLZ = (CLHS->getAPIntValue()+1).countLeadingZeros(); 01883 // NLZ can't be BitWidth with no sign bit 01884 APInt MaskV = APInt::getHighBitsSet(BitWidth, NLZ+1); 01885 ComputeMaskedBits(Op.getOperand(1), MaskV, KnownZero2, KnownOne2, 01886 Depth+1); 01887 01888 // If all of the MaskV bits are known to be zero, then we know the 01889 // output top bits are zero, because we now know that the output is 01890 // from [0-C]. 01891 if ((KnownZero2 & MaskV) == MaskV) { 01892 unsigned NLZ2 = CLHS->getAPIntValue().countLeadingZeros(); 01893 // Top bits known zero. 01894 KnownZero = APInt::getHighBitsSet(BitWidth, NLZ2) & Mask; 01895 } 01896 } 01897 } 01898 } 01899 // fall through 01900 case ISD::ADD: { 01901 // Output known-0 bits are known if clear or set in both the low clear bits 01902 // common to both LHS & RHS. For example, 8+(X<<3) is known to have the 01903 // low 3 bits clear. 01904 APInt Mask2 = APInt::getLowBitsSet(BitWidth, Mask.countTrailingOnes()); 01905 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero2, KnownOne2, Depth+1); 01906 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 01907 unsigned KnownZeroOut = KnownZero2.countTrailingOnes(); 01908 01909 ComputeMaskedBits(Op.getOperand(1), Mask2, KnownZero2, KnownOne2, Depth+1); 01910 assert((KnownZero2 & KnownOne2) == 0 && "Bits known to be one AND zero?"); 01911 KnownZeroOut = std::min(KnownZeroOut, 01912 KnownZero2.countTrailingOnes()); 01913 01914 KnownZero |= APInt::getLowBitsSet(BitWidth, KnownZeroOut); 01915 return; 01916 } 01917 case ISD::SREM: 01918 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 01919 const APInt &RA = Rem->getAPIntValue(); 01920 if (RA.isPowerOf2() || (-RA).isPowerOf2()) { 01921 APInt LowBits = RA.isStrictlyPositive() ? (RA - 1) : ~RA; 01922 APInt Mask2 = LowBits | APInt::getSignBit(BitWidth); 01923 ComputeMaskedBits(Op.getOperand(0), Mask2,KnownZero2,KnownOne2,Depth+1); 01924 01925 // If the sign bit of the first operand is zero, the sign bit of 01926 // the result is zero. If the first operand has no one bits below 01927 // the second operand's single 1 bit, its sign will be zero. 01928 if (KnownZero2[BitWidth-1] || ((KnownZero2 & LowBits) == LowBits)) 01929 KnownZero2 |= ~LowBits; 01930 01931 KnownZero |= KnownZero2 & Mask; 01932 01933 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 01934 } 01935 } 01936 return; 01937 case ISD::UREM: { 01938 if (ConstantSDNode *Rem = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 01939 const APInt &RA = Rem->getAPIntValue(); 01940 if (RA.isPowerOf2()) { 01941 APInt LowBits = (RA - 1); 01942 APInt Mask2 = LowBits & Mask; 01943 KnownZero |= ~LowBits & Mask; 01944 ComputeMaskedBits(Op.getOperand(0), Mask2, KnownZero, KnownOne,Depth+1); 01945 assert((KnownZero & KnownOne) == 0&&"Bits known to be one AND zero?"); 01946 break; 01947 } 01948 } 01949 01950 // Since the result is less than or equal to either operand, any leading 01951 // zero bits in either operand must also exist in the result. 01952 APInt AllOnes = APInt::getAllOnesValue(BitWidth); 01953 ComputeMaskedBits(Op.getOperand(0), AllOnes, KnownZero, KnownOne, 01954 Depth+1); 01955 ComputeMaskedBits(Op.getOperand(1), AllOnes, KnownZero2, KnownOne2, 01956 Depth+1); 01957 01958 uint32_t Leaders = std::max(KnownZero.countLeadingOnes(), 01959 KnownZero2.countLeadingOnes()); 01960 KnownOne.clear(); 01961 KnownZero = APInt::getHighBitsSet(BitWidth, Leaders) & Mask; 01962 return; 01963 } 01964 default: 01965 // Allow the target to implement this method for its nodes. 01966 if (Op.getOpcode() >= ISD::BUILTIN_OP_END) { 01967 case ISD::INTRINSIC_WO_CHAIN: 01968 case ISD::INTRINSIC_W_CHAIN: 01969 case ISD::INTRINSIC_VOID: 01970 TLI.computeMaskedBitsForTargetNode(Op, Mask, KnownZero, KnownOne, *this, 01971 Depth); 01972 } 01973 return; 01974 } 01975 } 01976 01977 /// ComputeNumSignBits - Return the number of times the sign bit of the 01978 /// register is replicated into the other bits. We know that at least 1 bit 01979 /// is always equal to the sign bit (itself), but other cases can give us 01980 /// information. For example, immediately after an "SRA X, 2", we know that 01981 /// the top 3 bits are all equal to each other, so we return 3. 01982 unsigned SelectionDAG::ComputeNumSignBits(SDValue Op, unsigned Depth) const{ 01983 EVT VT = Op.getValueType(); 01984 assert(VT.isInteger() && "Invalid VT!"); 01985 unsigned VTBits = VT.getSizeInBits(); 01986 unsigned Tmp, Tmp2; 01987 unsigned FirstAnswer = 1; 01988 01989 if (Depth == 6) 01990 return 1; // Limit search depth. 01991 01992 switch (Op.getOpcode()) { 01993 default: break; 01994 case ISD::AssertSext: 01995 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits(); 01996 return VTBits-Tmp+1; 01997 case ISD::AssertZext: 01998 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits(); 01999 return VTBits-Tmp; 02000 02001 case ISD::Constant: { 02002 const APInt &Val = cast<ConstantSDNode>(Op)->getAPIntValue(); 02003 // If negative, return # leading ones. 02004 if (Val.isNegative()) 02005 return Val.countLeadingOnes(); 02006 02007 // Return # leading zeros. 02008 return Val.countLeadingZeros(); 02009 } 02010 02011 case ISD::SIGN_EXTEND: 02012 Tmp = VTBits-Op.getOperand(0).getValueType().getSizeInBits(); 02013 return ComputeNumSignBits(Op.getOperand(0), Depth+1) + Tmp; 02014 02015 case ISD::SIGN_EXTEND_INREG: 02016 // Max of the input and what this extends. 02017 Tmp = cast<VTSDNode>(Op.getOperand(1))->getVT().getSizeInBits(); 02018 Tmp = VTBits-Tmp+1; 02019 02020 Tmp2 = ComputeNumSignBits(Op.getOperand(0), Depth+1); 02021 return std::max(Tmp, Tmp2); 02022 02023 case ISD::SRA: 02024 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 02025 // SRA X, C -> adds C sign bits. 02026 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 02027 Tmp += C->getZExtValue(); 02028 if (Tmp > VTBits) Tmp = VTBits; 02029 } 02030 return Tmp; 02031 case ISD::SHL: 02032 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 02033 // shl destroys sign bits. 02034 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 02035 if (C->getZExtValue() >= VTBits || // Bad shift. 02036 C->getZExtValue() >= Tmp) break; // Shifted all sign bits out. 02037 return Tmp - C->getZExtValue(); 02038 } 02039 break; 02040 case ISD::AND: 02041 case ISD::OR: 02042 case ISD::XOR: // NOT is handled here. 02043 // Logical binary ops preserve the number of sign bits at the worst. 02044 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 02045 if (Tmp != 1) { 02046 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 02047 FirstAnswer = std::min(Tmp, Tmp2); 02048 // We computed what we know about the sign bits as our first 02049 // answer. Now proceed to the generic code that uses 02050 // ComputeMaskedBits, and pick whichever answer is better. 02051 } 02052 break; 02053 02054 case ISD::SELECT: 02055 Tmp = ComputeNumSignBits(Op.getOperand(1), Depth+1); 02056 if (Tmp == 1) return 1; // Early out. 02057 Tmp2 = ComputeNumSignBits(Op.getOperand(2), Depth+1); 02058 return std::min(Tmp, Tmp2); 02059 02060 case ISD::SADDO: 02061 case ISD::UADDO: 02062 case ISD::SSUBO: 02063 case ISD::USUBO: 02064 case ISD::SMULO: 02065 case ISD::UMULO: 02066 if (Op.getResNo() != 1) 02067 break; 02068 // The boolean result conforms to getBooleanContents. Fall through. 02069 case ISD::SETCC: 02070 // If setcc returns 0/-1, all bits are sign bits. 02071 if (TLI.getBooleanContents() == 02072 TargetLowering::ZeroOrNegativeOneBooleanContent) 02073 return VTBits; 02074 break; 02075 case ISD::ROTL: 02076 case ISD::ROTR: 02077 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) { 02078 unsigned RotAmt = C->getZExtValue() & (VTBits-1); 02079 02080 // Handle rotate right by N like a rotate left by 32-N. 02081 if (Op.getOpcode() == ISD::ROTR) 02082 RotAmt = (VTBits-RotAmt) & (VTBits-1); 02083 02084 // If we aren't rotating out all of the known-in sign bits, return the 02085 // number that are left. This handles rotl(sext(x), 1) for example. 02086 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 02087 if (Tmp > RotAmt+1) return Tmp-RotAmt; 02088 } 02089 break; 02090 case ISD::ADD: 02091 // Add can have at most one carry bit. Thus we know that the output 02092 // is, at worst, one more bit than the inputs. 02093 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 02094 if (Tmp == 1) return 1; // Early out. 02095 02096 // Special case decrementing a value (ADD X, -1): 02097 if (ConstantSDNode *CRHS = dyn_cast<ConstantSDNode>(Op.getOperand(1))) 02098 if (CRHS->isAllOnesValue()) { 02099 APInt KnownZero, KnownOne; 02100 APInt Mask = APInt::getAllOnesValue(VTBits); 02101 ComputeMaskedBits(Op.getOperand(0), Mask, KnownZero, KnownOne, Depth+1); 02102 02103 // If the input is known to be 0 or 1, the output is 0/-1, which is all 02104 // sign bits set. 02105 if ((KnownZero | APInt(VTBits, 1)) == Mask) 02106 return VTBits; 02107 02108 // If we are subtracting one from a positive number, there is no carry 02109 // out of the result. 02110 if (KnownZero.isNegative()) 02111 return Tmp; 02112 } 02113 02114 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 02115 if (Tmp2 == 1) return 1; 02116 return std::min(Tmp, Tmp2)-1; 02117 break; 02118 02119 case ISD::SUB: 02120 Tmp2 = ComputeNumSignBits(Op.getOperand(1), Depth+1); 02121 if (Tmp2 == 1) return 1; 02122 02123 // Handle NEG. 02124 if (ConstantSDNode *CLHS = dyn_cast<ConstantSDNode>(Op.getOperand(0))) 02125 if (CLHS->isNullValue()) { 02126 APInt KnownZero, KnownOne; 02127 APInt Mask = APInt::getAllOnesValue(VTBits); 02128 ComputeMaskedBits(Op.getOperand(1), Mask, KnownZero, KnownOne, Depth+1); 02129 // If the input is known to be 0 or 1, the output is 0/-1, which is all 02130 // sign bits set. 02131 if ((KnownZero | APInt(VTBits, 1)) == Mask) 02132 return VTBits; 02133 02134 // If the input is known to be positive (the sign bit is known clear), 02135 // the output of the NEG has the same number of sign bits as the input. 02136 if (KnownZero.isNegative()) 02137 return Tmp2; 02138 02139 // Otherwise, we treat this like a SUB. 02140 } 02141 02142 // Sub can have at most one carry bit. Thus we know that the output 02143 // is, at worst, one more bit than the inputs. 02144 Tmp = ComputeNumSignBits(Op.getOperand(0), Depth+1); 02145 if (Tmp == 1) return 1; // Early out. 02146 return std::min(Tmp, Tmp2)-1; 02147 break; 02148 case ISD::TRUNCATE: 02149 // FIXME: it's tricky to do anything useful for this, but it is an important 02150 // case for targets like X86. 02151 break; 02152 } 02153 02154 // Handle LOADX separately here. EXTLOAD case will fallthrough. 02155 if (Op.getOpcode() == ISD::LOAD) { 02156 LoadSDNode *LD = cast<LoadSDNode>(Op); 02157 unsigned ExtType = LD->getExtensionType(); 02158 switch (ExtType) { 02159 default: break; 02160 case ISD::SEXTLOAD: // '17' bits known 02161 Tmp = LD->getMemoryVT().getSizeInBits(); 02162 return VTBits-Tmp+1; 02163 case ISD::ZEXTLOAD: // '16' bits known 02164 Tmp = LD->getMemoryVT().getSizeInBits(); 02165 return VTBits-Tmp; 02166 } 02167 } 02168 02169 // Allow the target to implement this method for its nodes. 02170 if (Op.getOpcode() >= ISD::BUILTIN_OP_END || 02171 Op.getOpcode() == ISD::INTRINSIC_WO_CHAIN || 02172 Op.getOpcode() == ISD::INTRINSIC_W_CHAIN || 02173 Op.getOpcode() == ISD::INTRINSIC_VOID) { 02174 unsigned NumBits = TLI.ComputeNumSignBitsForTargetNode(Op, Depth); 02175 if (NumBits > 1) FirstAnswer = std::max(FirstAnswer, NumBits); 02176 } 02177 02178 // Finally, if we can prove that the top bits of the result are 0's or 1's, 02179 // use this information. 02180 APInt KnownZero, KnownOne; 02181 APInt Mask = APInt::getAllOnesValue(VTBits); 02182 ComputeMaskedBits(Op, Mask, KnownZero, KnownOne, Depth); 02183 02184 if (KnownZero.isNegative()) { // sign bit is 0 02185 Mask = KnownZero; 02186 } else if (KnownOne.isNegative()) { // sign bit is 1; 02187 Mask = KnownOne; 02188 } else { 02189 // Nothing known. 02190 return FirstAnswer; 02191 } 02192 02193 // Okay, we know that the sign bit in Mask is set. Use CLZ to determine 02194 // the number of identical bits in the top of the input value. 02195 Mask = ~Mask; 02196 Mask <<= Mask.getBitWidth()-VTBits; 02197 // Return # leading zeros. We use 'min' here in case Val was zero before 02198 // shifting. We don't want to return '64' as for an i32 "0". 02199 return std::max(FirstAnswer, std::min(VTBits, Mask.countLeadingZeros())); 02200 } 02201 02202 02203 bool SelectionDAG::isVerifiedDebugInfoDesc(SDValue Op) const { 02204 GlobalAddressSDNode *GA = dyn_cast<GlobalAddressSDNode>(Op); 02205 if (!GA) return false; 02206 if (GA->getOffset() != 0) return false; 02207 GlobalVariable *GV = dyn_cast<GlobalVariable>(GA->getGlobal()); 02208 if (!GV) return false; 02209 MachineModuleInfo *MMI = getMachineModuleInfo(); 02210 return MMI && MMI->hasDebugInfo(); 02211 } 02212 02213 02214 /// getShuffleScalarElt - Returns the scalar element that will make up the ith 02215 /// element of the result of the vector shuffle. 02216 SDValue SelectionDAG::getShuffleScalarElt(const ShuffleVectorSDNode *N, 02217 unsigned i) { 02218 EVT VT = N->getValueType(0); 02219 DebugLoc dl = N->getDebugLoc(); 02220 if (N->getMaskElt(i) < 0) 02221 return getUNDEF(VT.getVectorElementType()); 02222 unsigned Index = N->getMaskElt(i); 02223 unsigned NumElems = VT.getVectorNumElements(); 02224 SDValue V = (Index < NumElems) ? N->getOperand(0) : N->getOperand(1); 02225 Index %= NumElems; 02226 02227 if (V.getOpcode() == ISD::BIT_CONVERT) { 02228 V = V.getOperand(0); 02229 EVT VVT = V.getValueType(); 02230 if (!VVT.isVector() || VVT.getVectorNumElements() != (unsigned)NumElems) 02231 return SDValue(); 02232 } 02233 if (V.getOpcode() == ISD::SCALAR_TO_VECTOR) 02234 return (Index == 0) ? V.getOperand(0) 02235 : getUNDEF(VT.getVectorElementType()); 02236 if (V.getOpcode() == ISD::BUILD_VECTOR) 02237 return V.getOperand(Index); 02238 if (const ShuffleVectorSDNode *SVN = dyn_cast<ShuffleVectorSDNode>(V)) 02239 return getShuffleScalarElt(SVN, Index); 02240 return SDValue(); 02241 } 02242 02243 02244 /// getNode - Gets or creates the specified node. 02245 /// 02246 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT) { 02247 FoldingSetNodeID ID; 02248 AddNodeIDNode(ID, Opcode, getVTList(VT), 0, 0); 02249 void *IP = 0; 02250 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 02251 return SDValue(E, 0); 02252 SDNode *N = NodeAllocator.Allocate<SDNode>(); 02253 new (N) SDNode(Opcode, DL, getVTList(VT)); 02254 CSEMap.InsertNode(N, IP); 02255 02256 AllNodes.push_back(N); 02257 #ifndef NDEBUG 02258 VerifyNode(N); 02259 #endif 02260 return SDValue(N, 0); 02261 } 02262 02263 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, 02264 EVT VT, SDValue Operand) { 02265 // Constant fold unary operations with an integer constant operand. 02266 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.getNode())) { 02267 const APInt &Val = C->getAPIntValue(); 02268 unsigned BitWidth = VT.getSizeInBits(); 02269 switch (Opcode) { 02270 default: break; 02271 case ISD::SIGN_EXTEND: 02272 return getConstant(APInt(Val).sextOrTrunc(BitWidth), VT); 02273 case ISD::ANY_EXTEND: 02274 case ISD::ZERO_EXTEND: 02275 case ISD::TRUNCATE: 02276 return getConstant(APInt(Val).zextOrTrunc(BitWidth), VT); 02277 case ISD::UINT_TO_FP: 02278 case ISD::SINT_TO_FP: { 02279 const uint64_t zero[] = {0, 0}; 02280 // No compile time operations on this type. 02281 if (VT==MVT::ppcf128) 02282 break; 02283 APFloat apf = APFloat(APInt(BitWidth, 2, zero)); 02284 (void)apf.convertFromAPInt(Val, 02285 Opcode==ISD::SINT_TO_FP, 02286 APFloat::rmNearestTiesToEven); 02287 return getConstantFP(apf, VT); 02288 } 02289 case ISD::BIT_CONVERT: 02290 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32) 02291 return getConstantFP(Val.bitsToFloat(), VT); 02292 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64) 02293 return getConstantFP(Val.bitsToDouble(), VT); 02294 break; 02295 case ISD::BSWAP: 02296 return getConstant(Val.byteSwap(), VT); 02297 case ISD::CTPOP: 02298 return getConstant(Val.countPopulation(), VT); 02299 case ISD::CTLZ: 02300 return getConstant(Val.countLeadingZeros(), VT); 02301 case ISD::CTTZ: 02302 return getConstant(Val.countTrailingZeros(), VT); 02303 } 02304 } 02305 02306 // Constant fold unary operations with a floating point constant operand. 02307 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.getNode())) { 02308 APFloat V = C->getValueAPF(); // make copy 02309 if (VT != MVT::ppcf128 && Operand.getValueType() != MVT::ppcf128) { 02310 switch (Opcode) { 02311 case ISD::FNEG: 02312 V.changeSign(); 02313 return getConstantFP(V, VT); 02314 case ISD::FABS: 02315 V.clearSign(); 02316 return getConstantFP(V, VT); 02317 case ISD::FP_ROUND: 02318 case ISD::FP_EXTEND: { 02319 bool ignored; 02320 // This can return overflow, underflow, or inexact; we don't care. 02321 // FIXME need to be more flexible about rounding mode. 02322 (void)V.convert(*EVTToAPFloatSemantics(VT), 02323 APFloat::rmNearestTiesToEven, &ignored); 02324 return getConstantFP(V, VT); 02325 } 02326 case ISD::FP_TO_SINT: 02327 case ISD::FP_TO_UINT: { 02328 integerPart x[2]; 02329 bool ignored; 02330 assert(integerPartWidth >= 64); 02331 // FIXME need to be more flexible about rounding mode. 02332 APFloat::opStatus s = V.convertToInteger(x, VT.getSizeInBits(), 02333 Opcode==ISD::FP_TO_SINT, 02334 APFloat::rmTowardZero, &ignored); 02335 if (s==APFloat::opInvalidOp) // inexact is OK, in fact usual 02336 break; 02337 APInt api(VT.getSizeInBits(), 2, x); 02338 return getConstant(api, VT); 02339 } 02340 case ISD::BIT_CONVERT: 02341 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32) 02342 return getConstant((uint32_t)V.bitcastToAPInt().getZExtValue(), VT); 02343 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64) 02344 return getConstant(V.bitcastToAPInt().getZExtValue(), VT); 02345 break; 02346 } 02347 } 02348 } 02349 02350 unsigned OpOpcode = Operand.getNode()->getOpcode(); 02351 switch (Opcode) { 02352 case ISD::TokenFactor: 02353 case ISD::MERGE_VALUES: 02354 case ISD::CONCAT_VECTORS: 02355 return Operand; // Factor, merge or concat of one node? No need. 02356 case ISD::FP_ROUND: llvm_unreachable("Invalid method to make FP_ROUND node"); 02357 case ISD::FP_EXTEND: 02358 assert(VT.isFloatingPoint() && 02359 Operand.getValueType().isFloatingPoint() && "Invalid FP cast!"); 02360 if (Operand.getValueType() == VT) return Operand; // noop conversion. 02361 if (Operand.getOpcode() == ISD::UNDEF) 02362 return getUNDEF(VT); 02363 break; 02364 case ISD::SIGN_EXTEND: 02365 assert(VT.isInteger() && Operand.getValueType().isInteger() && 02366 "Invalid SIGN_EXTEND!"); 02367 if (Operand.getValueType() == VT) return Operand; // noop extension 02368 assert(Operand.getValueType().bitsLT(VT) 02369 && "Invalid sext node, dst < src!"); 02370 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 02371 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0)); 02372 break; 02373 case ISD::ZERO_EXTEND: 02374 assert(VT.isInteger() && Operand.getValueType().isInteger() && 02375 "Invalid ZERO_EXTEND!"); 02376 if (Operand.getValueType() == VT) return Operand; // noop extension 02377 assert(Operand.getValueType().bitsLT(VT) 02378 && "Invalid zext node, dst < src!"); 02379 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x) 02380 return getNode(ISD::ZERO_EXTEND, DL, VT, 02381 Operand.getNode()->getOperand(0)); 02382 break; 02383 case ISD::ANY_EXTEND: 02384 assert(VT.isInteger() && Operand.getValueType().isInteger() && 02385 "Invalid ANY_EXTEND!"); 02386 if (Operand.getValueType() == VT) return Operand; // noop extension 02387 assert(Operand.getValueType().bitsLT(VT) 02388 && "Invalid anyext node, dst < src!"); 02389 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) 02390 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x) 02391 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0)); 02392 break; 02393 case ISD::TRUNCATE: 02394 assert(VT.isInteger() && Operand.getValueType().isInteger() && 02395 "Invalid TRUNCATE!"); 02396 if (Operand.getValueType() == VT) return Operand; // noop truncate 02397 assert(Operand.getValueType().bitsGT(VT) 02398 && "Invalid truncate node, src < dst!"); 02399 if (OpOpcode == ISD::TRUNCATE) 02400 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0)); 02401 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || 02402 OpOpcode == ISD::ANY_EXTEND) { 02403 // If the source is smaller than the dest, we still need an extend. 02404 if (Operand.getNode()->getOperand(0).getValueType().bitsLT(VT)) 02405 return getNode(OpOpcode, DL, VT, Operand.getNode()->getOperand(0)); 02406 else if (Operand.getNode()->getOperand(0).getValueType().bitsGT(VT)) 02407 return getNode(ISD::TRUNCATE, DL, VT, Operand.getNode()->getOperand(0)); 02408 else 02409 return Operand.getNode()->getOperand(0); 02410 } 02411 break; 02412 case ISD::BIT_CONVERT: 02413 // Basic sanity checking. 02414 assert(VT.getSizeInBits() == Operand.getValueType().getSizeInBits() 02415 && "Cannot BIT_CONVERT between types of different sizes!"); 02416 if (VT == Operand.getValueType()) return Operand; // noop conversion. 02417 if (OpOpcode == ISD::BIT_CONVERT) // bitconv(bitconv(x)) -> bitconv(x) 02418 return getNode(ISD::BIT_CONVERT, DL, VT, Operand.getOperand(0)); 02419 if (OpOpcode == ISD::UNDEF) 02420 return getUNDEF(VT); 02421 break; 02422 case ISD::SCALAR_TO_VECTOR: 02423 assert(VT.isVector() && !Operand.getValueType().isVector() && 02424 (VT.getVectorElementType() == Operand.getValueType() || 02425 (VT.getVectorElementType().isInteger() && 02426 Operand.getValueType().isInteger() && 02427 VT.getVectorElementType().bitsLE(Operand.getValueType()))) && 02428 "Illegal SCALAR_TO_VECTOR node!"); 02429 if (OpOpcode == ISD::UNDEF) 02430 return getUNDEF(VT); 02431 // scalar_to_vector(extract_vector_elt V, 0) -> V, top bits are undefined. 02432 if (OpOpcode == ISD::EXTRACT_VECTOR_ELT && 02433 isa<ConstantSDNode>(Operand.getOperand(1)) && 02434 Operand.getConstantOperandVal(1) == 0 && 02435 Operand.getOperand(0).getValueType() == VT) 02436 return Operand.getOperand(0); 02437 break; 02438 case ISD::FNEG: 02439 // -(X-Y) -> (Y-X) is unsafe because when X==Y, -0.0 != +0.0 02440 if (UnsafeFPMath && OpOpcode == ISD::FSUB) 02441 return getNode(ISD::FSUB, DL, VT, Operand.getNode()->getOperand(1), 02442 Operand.getNode()->getOperand(0)); 02443 if (OpOpcode == ISD::FNEG) // --X -> X 02444 return Operand.getNode()->getOperand(0); 02445 break; 02446 case ISD::FABS: 02447 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X) 02448 return getNode(ISD::FABS, DL, VT, Operand.getNode()->getOperand(0)); 02449 break; 02450 } 02451 02452 SDNode *N; 02453 SDVTList VTs = getVTList(VT); 02454 if (VT != MVT::Flag) { // Don't CSE flag producing nodes 02455 FoldingSetNodeID ID; 02456 SDValue Ops[1] = { Operand }; 02457 AddNodeIDNode(ID, Opcode, VTs, Ops, 1); 02458 void *IP = 0; 02459 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 02460 return SDValue(E, 0); 02461 N = NodeAllocator.Allocate<UnarySDNode>(); 02462 new (N) UnarySDNode(Opcode, DL, VTs, Operand); 02463 CSEMap.InsertNode(N, IP); 02464 } else { 02465 N = NodeAllocator.Allocate<UnarySDNode>(); 02466 new (N) UnarySDNode(Opcode, DL, VTs, Operand); 02467 } 02468 02469 AllNodes.push_back(N); 02470 #ifndef NDEBUG 02471 VerifyNode(N); 02472 #endif 02473 return SDValue(N, 0); 02474 } 02475 02476 SDValue SelectionDAG::FoldConstantArithmetic(unsigned Opcode, 02477 EVT VT, 02478 ConstantSDNode *Cst1, 02479 ConstantSDNode *Cst2) { 02480 const APInt &C1 = Cst1->getAPIntValue(), &C2 = Cst2->getAPIntValue(); 02481 02482 switch (Opcode) { 02483 case ISD::ADD: return getConstant(C1 + C2, VT); 02484 case ISD::SUB: return getConstant(C1 - C2, VT); 02485 case ISD::MUL: return getConstant(C1 * C2, VT); 02486 case ISD::UDIV: 02487 if (C2.getBoolValue()) return getConstant(C1.udiv(C2), VT); 02488 break; 02489 case ISD::UREM: 02490 if (C2.getBoolValue()) return getConstant(C1.urem(C2), VT); 02491 break; 02492 case ISD::SDIV: 02493 if (C2.getBoolValue()) return getConstant(C1.sdiv(C2), VT); 02494 break; 02495 case ISD::SREM: 02496 if (C2.getBoolValue()) return getConstant(C1.srem(C2), VT); 02497 break; 02498 case ISD::AND: return getConstant(C1 & C2, VT); 02499 case ISD::OR: return getConstant(C1 | C2, VT); 02500 case ISD::XOR: return getConstant(C1 ^ C2, VT); 02501 case ISD::SHL: return getConstant(C1 << C2, VT); 02502 case ISD::SRL: return getConstant(C1.lshr(C2), VT); 02503 case ISD::SRA: return getConstant(C1.ashr(C2), VT); 02504 case ISD::ROTL: return getConstant(C1.rotl(C2), VT); 02505 case ISD::ROTR: return getConstant(C1.rotr(C2), VT); 02506 default: break; 02507 } 02508 02509 return SDValue(); 02510 } 02511 02512 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 02513 SDValue N1, SDValue N2) { 02514 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 02515 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode()); 02516 switch (Opcode) { 02517 default: break; 02518 case ISD::TokenFactor: 02519 assert(VT == MVT::Other && N1.getValueType() == MVT::Other && 02520 N2.getValueType() == MVT::Other && "Invalid token factor!"); 02521 // Fold trivial token factors. 02522 if (N1.getOpcode() == ISD::EntryToken) return N2; 02523 if (N2.getOpcode() == ISD::EntryToken) return N1; 02524 if (N1 == N2) return N1; 02525 break; 02526 case ISD::CONCAT_VECTORS: 02527 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to 02528 // one big BUILD_VECTOR. 02529 if (N1.getOpcode() == ISD::BUILD_VECTOR && 02530 N2.getOpcode() == ISD::BUILD_VECTOR) { 02531 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(), N1.getNode()->op_end()); 02532 Elts.insert(Elts.end(), N2.getNode()->op_begin(), N2.getNode()->op_end()); 02533 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size()); 02534 } 02535 break; 02536 case ISD::AND: 02537 assert(VT.isInteger() && N1.getValueType() == N2.getValueType() && 02538 N1.getValueType() == VT && "Binary operator types must match!"); 02539 // (X & 0) -> 0. This commonly occurs when legalizing i64 values, so it's 02540 // worth handling here. 02541 if (N2C && N2C->isNullValue()) 02542 return N2; 02543 if (N2C && N2C->isAllOnesValue()) // X & -1 -> X 02544 return N1; 02545 break; 02546 case ISD::OR: 02547 case ISD::XOR: 02548 case ISD::ADD: 02549 case ISD::SUB: 02550 assert(VT.isInteger() && N1.getValueType() == N2.getValueType() && 02551 N1.getValueType() == VT && "Binary operator types must match!"); 02552 // (X ^|+- 0) -> X. This commonly occurs when legalizing i64 values, so 02553 // it's worth handling here. 02554 if (N2C && N2C->isNullValue()) 02555 return N1; 02556 break; 02557 case ISD::UDIV: 02558 case ISD::UREM: 02559 case ISD::MULHU: 02560 case ISD::MULHS: 02561 case ISD::MUL: 02562 case ISD::SDIV: 02563 case ISD::SREM: 02564 assert(VT.isInteger() && "This operator does not apply to FP types!"); 02565 // fall through 02566 case ISD::FADD: 02567 case ISD::FSUB: 02568 case ISD::FMUL: 02569 case ISD::FDIV: 02570 case ISD::FREM: 02571 if (UnsafeFPMath) { 02572 if (Opcode == ISD::FADD) { 02573 // 0+x --> x 02574 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N1)) 02575 if (CFP->getValueAPF().isZero()) 02576 return N2; 02577 // x+0 --> x 02578 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2)) 02579 if (CFP->getValueAPF().isZero()) 02580 return N1; 02581 } else if (Opcode == ISD::FSUB) { 02582 // x-0 --> x 02583 if (ConstantFPSDNode *CFP = dyn_cast<ConstantFPSDNode>(N2)) 02584 if (CFP->getValueAPF().isZero()) 02585 return N1; 02586 } 02587 } 02588 assert(N1.getValueType() == N2.getValueType() && 02589 N1.getValueType() == VT && "Binary operator types must match!"); 02590 break; 02591 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match. 02592 assert(N1.getValueType() == VT && 02593 N1.getValueType().isFloatingPoint() && 02594 N2.getValueType().isFloatingPoint() && 02595 "Invalid FCOPYSIGN!"); 02596 break; 02597 case ISD::SHL: 02598 case ISD::SRA: 02599 case ISD::SRL: 02600 case ISD::ROTL: 02601 case ISD::ROTR: 02602 assert(VT == N1.getValueType() && 02603 "Shift operators return type must be the same as their first arg"); 02604 assert(VT.isInteger() && N2.getValueType().isInteger() && 02605 "Shifts only work on integers"); 02606 02607 // Always fold shifts of i1 values so the code generator doesn't need to 02608 // handle them. Since we know the size of the shift has to be less than the 02609 // size of the value, the shift/rotate count is guaranteed to be zero. 02610 if (VT == MVT::i1) 02611 return N1; 02612 break; 02613 case ISD::FP_ROUND_INREG: { 02614 EVT EVT = cast<VTSDNode>(N2)->getVT(); 02615 assert(VT == N1.getValueType() && "Not an inreg round!"); 02616 assert(VT.isFloatingPoint() && EVT.isFloatingPoint() && 02617 "Cannot FP_ROUND_INREG integer types"); 02618 assert(EVT.bitsLE(VT) && "Not rounding down!"); 02619 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding. 02620 break; 02621 } 02622 case ISD::FP_ROUND: 02623 assert(VT.isFloatingPoint() && 02624 N1.getValueType().isFloatingPoint() && 02625 VT.bitsLE(N1.getValueType()) && 02626 isa<ConstantSDNode>(N2) && "Invalid FP_ROUND!"); 02627 if (N1.getValueType() == VT) return N1; // noop conversion. 02628 break; 02629 case ISD::AssertSext: 02630 case ISD::AssertZext: { 02631 EVT EVT = cast<VTSDNode>(N2)->getVT(); 02632 assert(VT == N1.getValueType() && "Not an inreg extend!"); 02633 assert(VT.isInteger() && EVT.isInteger() && 02634 "Cannot *_EXTEND_INREG FP types"); 02635 assert(EVT.bitsLE(VT) && "Not extending!"); 02636 if (VT == EVT) return N1; // noop assertion. 02637 break; 02638 } 02639 case ISD::SIGN_EXTEND_INREG: { 02640 EVT EVT = cast<VTSDNode>(N2)->getVT(); 02641 assert(VT == N1.getValueType() && "Not an inreg extend!"); 02642 assert(VT.isInteger() && EVT.isInteger() && 02643 "Cannot *_EXTEND_INREG FP types"); 02644 assert(EVT.bitsLE(VT) && "Not extending!"); 02645 if (EVT == VT) return N1; // Not actually extending 02646 02647 if (N1C) { 02648 APInt Val = N1C->getAPIntValue(); 02649 unsigned FromBits = cast<VTSDNode>(N2)->getVT().getSizeInBits(); 02650 Val <<= Val.getBitWidth()-FromBits; 02651 Val = Val.ashr(Val.getBitWidth()-FromBits); 02652 return getConstant(Val, VT); 02653 } 02654 break; 02655 } 02656 case ISD::EXTRACT_VECTOR_ELT: 02657 // EXTRACT_VECTOR_ELT of an UNDEF is an UNDEF. 02658 if (N1.getOpcode() == ISD::UNDEF) 02659 return getUNDEF(VT); 02660 02661 // EXTRACT_VECTOR_ELT of CONCAT_VECTORS is often formed while lowering is 02662 // expanding copies of large vectors from registers. 02663 if (N2C && 02664 N1.getOpcode() == ISD::CONCAT_VECTORS && 02665 N1.getNumOperands() > 0) { 02666 unsigned Factor = 02667 N1.getOperand(0).getValueType().getVectorNumElements(); 02668 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, 02669 N1.getOperand(N2C->getZExtValue() / Factor), 02670 getConstant(N2C->getZExtValue() % Factor, 02671 N2.getValueType())); 02672 } 02673 02674 // EXTRACT_VECTOR_ELT of BUILD_VECTOR is often formed while lowering is 02675 // expanding large vector constants. 02676 if (N2C && N1.getOpcode() == ISD::BUILD_VECTOR) { 02677 SDValue Elt = N1.getOperand(N2C->getZExtValue()); 02678 EVT VEltTy = N1.getValueType().getVectorElementType(); 02679 if (Elt.getValueType() != VEltTy) { 02680 // If the vector element type is not legal, the BUILD_VECTOR operands 02681 // are promoted and implicitly truncated. Make that explicit here. 02682 Elt = getNode(ISD::TRUNCATE, DL, VEltTy, Elt); 02683 } 02684 if (VT != VEltTy) { 02685 // If the vector element type is not legal, the EXTRACT_VECTOR_ELT 02686 // result is implicitly extended. 02687 Elt = getNode(ISD::ANY_EXTEND, DL, VT, Elt); 02688 } 02689 return Elt; 02690 } 02691 02692 // EXTRACT_VECTOR_ELT of INSERT_VECTOR_ELT is often formed when vector 02693 // operations are lowered to scalars. 02694 if (N1.getOpcode() == ISD::INSERT_VECTOR_ELT) { 02695 // If the indices are the same, return the inserted element. 02696 if (N1.getOperand(2) == N2) 02697 return N1.getOperand(1); 02698 // If the indices are known different, extract the element from 02699 // the original vector. 02700 else if (isa<ConstantSDNode>(N1.getOperand(2)) && 02701 isa<ConstantSDNode>(N2)) 02702 return getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, N1.getOperand(0), N2); 02703 } 02704 break; 02705 case ISD::EXTRACT_ELEMENT: 02706 assert(N2C && (unsigned)N2C->getZExtValue() < 2 && "Bad EXTRACT_ELEMENT!"); 02707 assert(!N1.getValueType().isVector() && !VT.isVector() && 02708 (N1.getValueType().isInteger() == VT.isInteger()) && 02709 "Wrong types for EXTRACT_ELEMENT!"); 02710 02711 // EXTRACT_ELEMENT of BUILD_PAIR is often formed while legalize is expanding 02712 // 64-bit integers into 32-bit parts. Instead of building the extract of 02713 // the BUILD_PAIR, only to have legalize rip it apart, just do it now. 02714 if (N1.getOpcode() == ISD::BUILD_PAIR) 02715 return N1.getOperand(N2C->getZExtValue()); 02716 02717 // EXTRACT_ELEMENT of a constant int is also very common. 02718 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N1)) { 02719 unsigned ElementSize = VT.getSizeInBits(); 02720 unsigned Shift = ElementSize * N2C->getZExtValue(); 02721 APInt ShiftedVal = C->getAPIntValue().lshr(Shift); 02722 return getConstant(ShiftedVal.trunc(ElementSize), VT); 02723 } 02724 break; 02725 case ISD::EXTRACT_SUBVECTOR: 02726 if (N1.getValueType() == VT) // Trivial extraction. 02727 return N1; 02728 break; 02729 } 02730 02731 if (N1C) { 02732 if (N2C) { 02733 SDValue SV = FoldConstantArithmetic(Opcode, VT, N1C, N2C); 02734 if (SV.getNode()) return SV; 02735 } else { // Cannonicalize constant to RHS if commutative 02736 if (isCommutativeBinOp(Opcode)) { 02737 std::swap(N1C, N2C); 02738 std::swap(N1, N2); 02739 } 02740 } 02741 } 02742 02743 // Constant fold FP operations. 02744 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.getNode()); 02745 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.getNode()); 02746 if (N1CFP) { 02747 if (!N2CFP && isCommutativeBinOp(Opcode)) { 02748 // Cannonicalize constant to RHS if commutative 02749 std::swap(N1CFP, N2CFP); 02750 std::swap(N1, N2); 02751 } else if (N2CFP && VT != MVT::ppcf128) { 02752 APFloat V1 = N1CFP->getValueAPF(), V2 = N2CFP->getValueAPF(); 02753 APFloat::opStatus s; 02754 switch (Opcode) { 02755 case ISD::FADD: 02756 s = V1.add(V2, APFloat::rmNearestTiesToEven); 02757 if (s != APFloat::opInvalidOp) 02758 return getConstantFP(V1, VT); 02759 break; 02760 case ISD::FSUB: 02761 s = V1.subtract(V2, APFloat::rmNearestTiesToEven); 02762 if (s!=APFloat::opInvalidOp) 02763 return getConstantFP(V1, VT); 02764 break; 02765 case ISD::FMUL: 02766 s = V1.multiply(V2, APFloat::rmNearestTiesToEven); 02767 if (s!=APFloat::opInvalidOp) 02768 return getConstantFP(V1, VT); 02769 break; 02770 case ISD::FDIV: 02771 s = V1.divide(V2, APFloat::rmNearestTiesToEven); 02772 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero) 02773 return getConstantFP(V1, VT); 02774 break; 02775 case ISD::FREM : 02776 s = V1.mod(V2, APFloat::rmNearestTiesToEven); 02777 if (s!=APFloat::opInvalidOp && s!=APFloat::opDivByZero) 02778 return getConstantFP(V1, VT); 02779 break; 02780 case ISD::FCOPYSIGN: 02781 V1.copySign(V2); 02782 return getConstantFP(V1, VT); 02783 default: break; 02784 } 02785 } 02786 } 02787 02788 // Canonicalize an UNDEF to the RHS, even over a constant. 02789 if (N1.getOpcode() == ISD::UNDEF) { 02790 if (isCommutativeBinOp(Opcode)) { 02791 std::swap(N1, N2); 02792 } else { 02793 switch (Opcode) { 02794 case ISD::FP_ROUND_INREG: 02795 case ISD::SIGN_EXTEND_INREG: 02796 case ISD::SUB: 02797 case ISD::FSUB: 02798 case ISD::FDIV: 02799 case ISD::FREM: 02800 case ISD::SRA: 02801 return N1; // fold op(undef, arg2) -> undef 02802 case ISD::UDIV: 02803 case ISD::SDIV: 02804 case ISD::UREM: 02805 case ISD::SREM: 02806 case ISD::SRL: 02807 case ISD::SHL: 02808 if (!VT.isVector()) 02809 return getConstant(0, VT); // fold op(undef, arg2) -> 0 02810 // For vectors, we can't easily build an all zero vector, just return 02811 // the LHS. 02812 return N2; 02813 } 02814 } 02815 } 02816 02817 // Fold a bunch of operators when the RHS is undef. 02818 if (N2.getOpcode() == ISD::UNDEF) { 02819 switch (Opcode) { 02820 case ISD::XOR: 02821 if (N1.getOpcode() == ISD::UNDEF) 02822 // Handle undef ^ undef -> 0 special case. This is a common 02823 // idiom (misuse). 02824 return getConstant(0, VT); 02825 // fallthrough 02826 case ISD::ADD: 02827 case ISD::ADDC: 02828 case ISD::ADDE: 02829 case ISD::SUB: 02830 case ISD::UDIV: 02831 case ISD::SDIV: 02832 case ISD::UREM: 02833 case ISD::SREM: 02834 return N2; // fold op(arg1, undef) -> undef 02835 case ISD::FADD: 02836 case ISD::FSUB: 02837 case ISD::FMUL: 02838 case ISD::FDIV: 02839 case ISD::FREM: 02840 if (UnsafeFPMath) 02841 return N2; 02842 break; 02843 case ISD::MUL: 02844 case ISD::AND: 02845 case ISD::SRL: 02846 case ISD::SHL: 02847 if (!VT.isVector()) 02848 return getConstant(0, VT); // fold op(arg1, undef) -> 0 02849 // For vectors, we can't easily build an all zero vector, just return 02850 // the LHS. 02851 return N1; 02852 case ISD::OR: 02853 if (!VT.isVector()) 02854 return getConstant(APInt::getAllOnesValue(VT.getSizeInBits()), VT); 02855 // For vectors, we can't easily build an all one vector, just return 02856 // the LHS. 02857 return N1; 02858 case ISD::SRA: 02859 return N1; 02860 } 02861 } 02862 02863 // Memoize this node if possible. 02864 SDNode *N; 02865 SDVTList VTs = getVTList(VT); 02866 if (VT != MVT::Flag) { 02867 SDValue Ops[] = { N1, N2 }; 02868 FoldingSetNodeID ID; 02869 AddNodeIDNode(ID, Opcode, VTs, Ops, 2); 02870 void *IP = 0; 02871 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 02872 return SDValue(E, 0); 02873 N = NodeAllocator.Allocate<BinarySDNode>(); 02874 new (N) BinarySDNode(Opcode, DL, VTs, N1, N2); 02875 CSEMap.InsertNode(N, IP); 02876 } else { 02877 N = NodeAllocator.Allocate<BinarySDNode>(); 02878 new (N) BinarySDNode(Opcode, DL, VTs, N1, N2); 02879 } 02880 02881 AllNodes.push_back(N); 02882 #ifndef NDEBUG 02883 VerifyNode(N); 02884 #endif 02885 return SDValue(N, 0); 02886 } 02887 02888 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 02889 SDValue N1, SDValue N2, SDValue N3) { 02890 // Perform various simplifications. 02891 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.getNode()); 02892 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.getNode()); 02893 switch (Opcode) { 02894 case ISD::CONCAT_VECTORS: 02895 // A CONCAT_VECTOR with all operands BUILD_VECTOR can be simplified to 02896 // one big BUILD_VECTOR. 02897 if (N1.getOpcode() == ISD::BUILD_VECTOR && 02898 N2.getOpcode() == ISD::BUILD_VECTOR && 02899 N3.getOpcode() == ISD::BUILD_VECTOR) { 02900 SmallVector<SDValue, 16> Elts(N1.getNode()->op_begin(), N1.getNode()->op_end()); 02901 Elts.insert(Elts.end(), N2.getNode()->op_begin(), N2.getNode()->op_end()); 02902 Elts.insert(Elts.end(), N3.getNode()->op_begin(), N3.getNode()->op_end()); 02903 return getNode(ISD::BUILD_VECTOR, DL, VT, &Elts[0], Elts.size()); 02904 } 02905 break; 02906 case ISD::SETCC: { 02907 // Use FoldSetCC to simplify SETCC's. 02908 SDValue Simp = FoldSetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get(), DL); 02909 if (Simp.getNode()) return Simp; 02910 break; 02911 } 02912 case ISD::SELECT: 02913 if (N1C) { 02914 if (N1C->getZExtValue()) 02915 return N2; // select true, X, Y -> X 02916 else 02917 return N3; // select false, X, Y -> Y 02918 } 02919 02920 if (N2 == N3) return N2; // select C, X, X -> X 02921 break; 02922 case ISD::BRCOND: 02923 if (N2C) { 02924 if (N2C->getZExtValue()) // Unconditional branch 02925 return getNode(ISD::BR, DL, MVT::Other, N1, N3); 02926 else 02927 return N1; // Never-taken branch 02928 } 02929 break; 02930 case ISD::VECTOR_SHUFFLE: 02931 llvm_unreachable("should use getVectorShuffle constructor!"); 02932 break; 02933 case ISD::BIT_CONVERT: 02934 // Fold bit_convert nodes from a type to themselves. 02935 if (N1.getValueType() == VT) 02936 return N1; 02937 break; 02938 } 02939 02940 // Memoize node if it doesn't produce a flag. 02941 SDNode *N; 02942 SDVTList VTs = getVTList(VT); 02943 if (VT != MVT::Flag) { 02944 SDValue Ops[] = { N1, N2, N3 }; 02945 FoldingSetNodeID ID; 02946 AddNodeIDNode(ID, Opcode, VTs, Ops, 3); 02947 void *IP = 0; 02948 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 02949 return SDValue(E, 0); 02950 N = NodeAllocator.Allocate<TernarySDNode>(); 02951 new (N) TernarySDNode(Opcode, DL, VTs, N1, N2, N3); 02952 CSEMap.InsertNode(N, IP); 02953 } else { 02954 N = NodeAllocator.Allocate<TernarySDNode>(); 02955 new (N) TernarySDNode(Opcode, DL, VTs, N1, N2, N3); 02956 } 02957 AllNodes.push_back(N); 02958 #ifndef NDEBUG 02959 VerifyNode(N); 02960 #endif 02961 return SDValue(N, 0); 02962 } 02963 02964 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 02965 SDValue N1, SDValue N2, SDValue N3, 02966 SDValue N4) { 02967 SDValue Ops[] = { N1, N2, N3, N4 }; 02968 return getNode(Opcode, DL, VT, Ops, 4); 02969 } 02970 02971 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 02972 SDValue N1, SDValue N2, SDValue N3, 02973 SDValue N4, SDValue N5) { 02974 SDValue Ops[] = { N1, N2, N3, N4, N5 }; 02975 return getNode(Opcode, DL, VT, Ops, 5); 02976 } 02977 02978 /// getStackArgumentTokenFactor - Compute a TokenFactor to force all 02979 /// the incoming stack arguments to be loaded from the stack. 02980 SDValue SelectionDAG::getStackArgumentTokenFactor(SDValue Chain) { 02981 SmallVector<SDValue, 8> ArgChains; 02982 02983 // Include the original chain at the beginning of the list. When this is 02984 // used by target LowerCall hooks, this helps legalize find the 02985 // CALLSEQ_BEGIN node. 02986 ArgChains.push_back(Chain); 02987 02988 // Add a chain value for each stack argument. 02989 for (SDNode::use_iterator U = getEntryNode().getNode()->use_begin(), 02990 UE = getEntryNode().getNode()->use_end(); U != UE; ++U) 02991 if (LoadSDNode *L = dyn_cast<LoadSDNode>(*U)) 02992 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(L->getBasePtr())) 02993 if (FI->getIndex() < 0) 02994 ArgChains.push_back(SDValue(L, 1)); 02995 02996 // Build a tokenfactor for all the chains. 02997 return getNode(ISD::TokenFactor, Chain.getDebugLoc(), MVT::Other, 02998 &ArgChains[0], ArgChains.size()); 02999 } 03000 03001 /// getMemsetValue - Vectorized representation of the memset value 03002 /// operand. 03003 static SDValue getMemsetValue(SDValue Value, EVT VT, SelectionDAG &DAG, 03004 DebugLoc dl) { 03005 unsigned NumBits = VT.isVector() ? 03006 VT.getVectorElementType().getSizeInBits() : VT.getSizeInBits(); 03007 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) { 03008 APInt Val = APInt(NumBits, C->getZExtValue() & 255); 03009 unsigned Shift = 8; 03010 for (unsigned i = NumBits; i > 8; i >>= 1) { 03011 Val = (Val << Shift) | Val; 03012 Shift <<= 1; 03013 } 03014 if (VT.isInteger()) 03015 return DAG.getConstant(Val, VT); 03016 return DAG.getConstantFP(APFloat(Val), VT); 03017 } 03018 03019 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 03020 Value = DAG.getNode(ISD::ZERO_EXTEND, dl, VT, Value); 03021 unsigned Shift = 8; 03022 for (unsigned i = NumBits; i > 8; i >>= 1) { 03023 Value = DAG.getNode(ISD::OR, dl, VT, 03024 DAG.getNode(ISD::SHL, dl, VT, Value, 03025 DAG.getConstant(Shift, 03026 TLI.getShiftAmountTy())), 03027 Value); 03028 Shift <<= 1; 03029 } 03030 03031 return Value; 03032 } 03033 03034 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only 03035 /// used when a memcpy is turned into a memset when the source is a constant 03036 /// string ptr. 03037 static SDValue getMemsetStringVal(EVT VT, DebugLoc dl, SelectionDAG &DAG, 03038 const TargetLowering &TLI, 03039 std::string &Str, unsigned Offset) { 03040 // Handle vector with all elements zero. 03041 if (Str.empty()) { 03042 if (VT.isInteger()) 03043 return DAG.getConstant(0, VT); 03044 unsigned NumElts = VT.getVectorNumElements(); 03045 MVT EltVT = (VT.getVectorElementType() == MVT::f32) ? MVT::i32 : MVT::i64; 03046 return DAG.getNode(ISD::BIT_CONVERT, dl, VT, 03047 DAG.getConstant(0, 03048 EVT::getVectorVT(*DAG.getContext(), EltVT, NumElts))); 03049 } 03050 03051 assert(!VT.isVector() && "Can't handle vector type here!"); 03052 unsigned NumBits = VT.getSizeInBits(); 03053 unsigned MSB = NumBits / 8; 03054 uint64_t Val = 0; 03055 if (TLI.isLittleEndian()) 03056 Offset = Offset + MSB - 1; 03057 for (unsigned i = 0; i != MSB; ++i) { 03058 Val = (Val << 8) | (unsigned char)Str[Offset]; 03059 Offset += TLI.isLittleEndian() ? -1 : 1; 03060 } 03061 return DAG.getConstant(Val, VT); 03062 } 03063 03064 /// getMemBasePlusOffset - Returns base and offset node for the 03065 /// 03066 static SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, 03067 SelectionDAG &DAG) { 03068 EVT VT = Base.getValueType(); 03069 return DAG.getNode(ISD::ADD, Base.getDebugLoc(), 03070 VT, Base, DAG.getConstant(Offset, VT)); 03071 } 03072 03073 /// isMemSrcFromString - Returns true if memcpy source is a string constant. 03074 /// 03075 static bool isMemSrcFromString(SDValue Src, std::string &Str) { 03076 unsigned SrcDelta = 0; 03077 GlobalAddressSDNode *G = NULL; 03078 if (Src.getOpcode() == ISD::GlobalAddress) 03079 G = cast<GlobalAddressSDNode>(Src); 03080 else if (Src.getOpcode() == ISD::ADD && 03081 Src.getOperand(0).getOpcode() == ISD::GlobalAddress && 03082 Src.getOperand(1).getOpcode() == ISD::Constant) { 03083 G = cast<GlobalAddressSDNode>(Src.getOperand(0)); 03084 SrcDelta = cast<ConstantSDNode>(Src.getOperand(1))->getZExtValue(); 03085 } 03086 if (!G) 03087 return false; 03088 03089 GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal()); 03090 if (GV && GetConstantStringInfo(GV, Str, SrcDelta, false)) 03091 return true; 03092 03093 return false; 03094 } 03095 03096 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required 03097 /// to replace the memset / memcpy is below the threshold. It also returns the 03098 /// types of the sequence of memory ops to perform memset / memcpy. 03099 static 03100 bool MeetsMaxMemopRequirement(std::vector<EVT> &MemOps, 03101 SDValue Dst, SDValue Src, 03102 unsigned Limit, uint64_t Size, unsigned &Align, 03103 std::string &Str, bool &isSrcStr, 03104 SelectionDAG &DAG, 03105 const TargetLowering &TLI) { 03106 isSrcStr = isMemSrcFromString(Src, Str); 03107 bool isSrcConst = isa<ConstantSDNode>(Src); 03108 EVT VT = TLI.getOptimalMemOpType(Size, Align, isSrcConst, isSrcStr, DAG); 03109 bool AllowUnalign = TLI.allowsUnalignedMemoryAccesses(VT); 03110 if (VT != MVT::iAny) { 03111 const Type *Ty = VT.getTypeForEVT(*DAG.getContext()); 03112 unsigned NewAlign = (unsigned) TLI.getTargetData()->getABITypeAlignment(Ty); 03113 // If source is a string constant, this will require an unaligned load. 03114 if (NewAlign > Align && (isSrcConst || AllowUnalign)) { 03115 if (Dst.getOpcode() != ISD::FrameIndex) { 03116 // Can't change destination alignment. It requires a unaligned store. 03117 if (AllowUnalign) 03118 VT = MVT::iAny; 03119 } else { 03120 int FI = cast<FrameIndexSDNode>(Dst)->getIndex(); 03121 MachineFrameInfo *MFI = DAG.getMachineFunction().getFrameInfo(); 03122 if (MFI->isFixedObjectIndex(FI)) { 03123 // Can't change destination alignment. It requires a unaligned store. 03124 if (AllowUnalign) 03125 VT = MVT::iAny; 03126 } else { 03127 // Give the stack frame object a larger alignment if needed. 03128 if (MFI->getObjectAlignment(FI) < NewAlign) 03129 MFI->setObjectAlignment(FI, NewAlign); 03130 Align = NewAlign; 03131 } 03132 } 03133 } 03134 } 03135 03136 if (VT == MVT::iAny) { 03137 if (TLI.allowsUnalignedMemoryAccesses(MVT::i64)) { 03138 VT = MVT::i64; 03139 } else { 03140 switch (Align & 7) { 03141 case 0: VT = MVT::i64; break; 03142 case 4: VT = MVT::i32; break; 03143 case 2: VT = MVT::i16; break; 03144 default: VT = MVT::i8; break; 03145 } 03146 } 03147 03148 MVT LVT = MVT::i64; 03149 while (!TLI.isTypeLegal(LVT)) 03150 LVT = (MVT::SimpleValueType)(LVT.SimpleTy - 1); 03151 assert(LVT.isInteger()); 03152 03153 if (VT.bitsGT(LVT)) 03154 VT = LVT; 03155 } 03156 03157 unsigned NumMemOps = 0; 03158 while (Size != 0) { 03159 unsigned VTSize = VT.getSizeInBits() / 8; 03160 while (VTSize > Size) { 03161 // For now, only use non-vector load / store's for the left-over pieces. 03162 if (VT.isVector()) { 03163 VT = MVT::i64; 03164 while (!TLI.isTypeLegal(VT)) 03165 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1); 03166 VTSize = VT.getSizeInBits() / 8; 03167 } else { 03168 // This can result in a type that is not legal on the target, e.g. 03169 // 1 or 2 bytes on PPC. 03170 VT = (MVT::SimpleValueType)(VT.getSimpleVT().SimpleTy - 1); 03171 VTSize >>= 1; 03172 } 03173 } 03174 03175 if (++NumMemOps > Limit) 03176 return false; 03177 MemOps.push_back(VT); 03178 Size -= VTSize; 03179 } 03180 03181 return true; 03182 } 03183 03184 static SDValue getMemcpyLoadsAndStores(SelectionDAG &DAG, DebugLoc dl, 03185 SDValue Chain, SDValue Dst, 03186 SDValue Src, uint64_t Size, 03187 unsigned Align, bool AlwaysInline, 03188 const Value *DstSV, uint64_t DstSVOff, 03189 const Value *SrcSV, uint64_t SrcSVOff){ 03190 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 03191 03192 // Expand memcpy to a series of load and store ops if the size operand falls 03193 // below a certain threshold. 03194 std::vector<EVT> MemOps; 03195 uint64_t Limit = -1ULL; 03196 if (!AlwaysInline) 03197 Limit = TLI.getMaxStoresPerMemcpy(); 03198 unsigned DstAlign = Align; // Destination alignment can change. 03199 std::string Str; 03200 bool CopyFromStr; 03201 if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign, 03202 Str, CopyFromStr, DAG, TLI)) 03203 return SDValue(); 03204 03205 03206 bool isZeroStr = CopyFromStr && Str.empty(); 03207 SmallVector<SDValue, 8> OutChains; 03208 unsigned NumMemOps = MemOps.size(); 03209 uint64_t SrcOff = 0, DstOff = 0; 03210 for (unsigned i = 0; i < NumMemOps; i++) { 03211 EVT VT = MemOps[i]; 03212 unsigned VTSize = VT.getSizeInBits() / 8; 03213 SDValue Value, Store; 03214 03215 if (CopyFromStr && (isZeroStr || !VT.isVector())) { 03216 // It's unlikely a store of a vector immediate can be done in a single 03217 // instruction. It would require a load from a constantpool first. 03218 // We also handle store a vector with all zero's. 03219 // FIXME: Handle other cases where store of vector immediate is done in 03220 // a single instruction. 03221 Value = getMemsetStringVal(VT, dl, DAG, TLI, Str, SrcOff); 03222 Store = DAG.getStore(Chain, dl, Value, 03223 getMemBasePlusOffset(Dst, DstOff, DAG), 03224 DstSV, DstSVOff + DstOff, false, DstAlign); 03225 } else { 03226 // The type might not be legal for the target. This should only happen 03227 // if the type is smaller than a legal type, as on PPC, so the right 03228 // thing to do is generate a LoadExt/StoreTrunc pair. These simplify 03229 // to Load/Store if NVT==VT. 03230 // FIXME does the case above also need this? 03231 EVT NVT = TLI.getTypeToTransformTo(*DAG.getContext(), VT); 03232 assert(NVT.bitsGE(VT)); 03233 Value = DAG.getExtLoad(ISD::EXTLOAD, dl, NVT, Chain, 03234 getMemBasePlusOffset(Src, SrcOff, DAG), 03235 SrcSV, SrcSVOff + SrcOff, VT, false, Align); 03236 Store = DAG.getTruncStore(Chain, dl, Value, 03237 getMemBasePlusOffset(Dst, DstOff, DAG), 03238 DstSV, DstSVOff + DstOff, VT, false, DstAlign); 03239 } 03240 OutChains.push_back(Store); 03241 SrcOff += VTSize; 03242 DstOff += VTSize; 03243 } 03244 03245 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 03246 &OutChains[0], OutChains.size()); 03247 } 03248 03249 static SDValue getMemmoveLoadsAndStores(SelectionDAG &DAG, DebugLoc dl, 03250 SDValue Chain, SDValue Dst, 03251 SDValue Src, uint64_t Size, 03252 unsigned Align, bool AlwaysInline, 03253 const Value *DstSV, uint64_t DstSVOff, 03254 const Value *SrcSV, uint64_t SrcSVOff){ 03255 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 03256 03257 // Expand memmove to a series of load and store ops if the size operand falls 03258 // below a certain threshold. 03259 std::vector<EVT> MemOps; 03260 uint64_t Limit = -1ULL; 03261 if (!AlwaysInline) 03262 Limit = TLI.getMaxStoresPerMemmove(); 03263 unsigned DstAlign = Align; // Destination alignment can change. 03264 std::string Str; 03265 bool CopyFromStr; 03266 if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, Limit, Size, DstAlign, 03267 Str, CopyFromStr, DAG, TLI)) 03268 return SDValue(); 03269 03270 uint64_t SrcOff = 0, DstOff = 0; 03271 03272 SmallVector<SDValue, 8> LoadValues; 03273 SmallVector<SDValue, 8> LoadChains; 03274 SmallVector<SDValue, 8> OutChains; 03275 unsigned NumMemOps = MemOps.size(); 03276 for (unsigned i = 0; i < NumMemOps; i++) { 03277 EVT VT = MemOps[i]; 03278 unsigned VTSize = VT.getSizeInBits() / 8; 03279 SDValue Value, Store; 03280 03281 Value = DAG.getLoad(VT, dl, Chain, 03282 getMemBasePlusOffset(Src, SrcOff, DAG), 03283 SrcSV, SrcSVOff + SrcOff, false, Align); 03284 LoadValues.push_back(Value); 03285 LoadChains.push_back(Value.getValue(1)); 03286 SrcOff += VTSize; 03287 } 03288 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 03289 &LoadChains[0], LoadChains.size()); 03290 OutChains.clear(); 03291 for (unsigned i = 0; i < NumMemOps; i++) { 03292 EVT VT = MemOps[i]; 03293 unsigned VTSize = VT.getSizeInBits() / 8; 03294 SDValue Value, Store; 03295 03296 Store = DAG.getStore(Chain, dl, LoadValues[i], 03297 getMemBasePlusOffset(Dst, DstOff, DAG), 03298 DstSV, DstSVOff + DstOff, false, DstAlign); 03299 OutChains.push_back(Store); 03300 DstOff += VTSize; 03301 } 03302 03303 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 03304 &OutChains[0], OutChains.size()); 03305 } 03306 03307 static SDValue getMemsetStores(SelectionDAG &DAG, DebugLoc dl, 03308 SDValue Chain, SDValue Dst, 03309 SDValue Src, uint64_t Size, 03310 unsigned Align, 03311 const Value *DstSV, uint64_t DstSVOff) { 03312 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 03313 03314 // Expand memset to a series of load/store ops if the size operand 03315 // falls below a certain threshold. 03316 std::vector<EVT> MemOps; 03317 std::string Str; 03318 bool CopyFromStr; 03319 if (!MeetsMaxMemopRequirement(MemOps, Dst, Src, TLI.getMaxStoresPerMemset(), 03320 Size, Align, Str, CopyFromStr, DAG, TLI)) 03321 return SDValue(); 03322 03323 SmallVector<SDValue, 8> OutChains; 03324 uint64_t DstOff = 0; 03325 03326 unsigned NumMemOps = MemOps.size(); 03327 for (unsigned i = 0; i < NumMemOps; i++) { 03328 EVT VT = MemOps[i]; 03329 unsigned VTSize = VT.getSizeInBits() / 8; 03330 SDValue Value = getMemsetValue(Src, VT, DAG, dl); 03331 SDValue Store = DAG.getStore(Chain, dl, Value, 03332 getMemBasePlusOffset(Dst, DstOff, DAG), 03333 DstSV, DstSVOff + DstOff); 03334 OutChains.push_back(Store); 03335 DstOff += VTSize; 03336 } 03337 03338 return DAG.getNode(ISD::TokenFactor, dl, MVT::Other, 03339 &OutChains[0], OutChains.size()); 03340 } 03341 03342 SDValue SelectionDAG::getMemcpy(SDValue Chain, DebugLoc dl, SDValue Dst, 03343 SDValue Src, SDValue Size, 03344 unsigned Align, bool AlwaysInline, 03345 const Value *DstSV, uint64_t DstSVOff, 03346 const Value *SrcSV, uint64_t SrcSVOff) { 03347 03348 // Check to see if we should lower the memcpy to loads and stores first. 03349 // For cases within the target-specified limits, this is the best choice. 03350 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size); 03351 if (ConstantSize) { 03352 // Memcpy with size zero? Just return the original chain. 03353 if (ConstantSize->isNullValue()) 03354 return Chain; 03355 03356 SDValue Result = 03357 getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src, 03358 ConstantSize->getZExtValue(), 03359 Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff); 03360 if (Result.getNode()) 03361 return Result; 03362 } 03363 03364 // Then check to see if we should lower the memcpy with target-specific 03365 // code. If the target chooses to do this, this is the next best. 03366 SDValue Result = 03367 TLI.EmitTargetCodeForMemcpy(*this, dl, Chain, Dst, Src, Size, Align, 03368 AlwaysInline, 03369 DstSV, DstSVOff, SrcSV, SrcSVOff); 03370 if (Result.getNode()) 03371 return Result; 03372 03373 // If we really need inline code and the target declined to provide it, 03374 // use a (potentially long) sequence of loads and stores. 03375 if (AlwaysInline) { 03376 assert(ConstantSize && "AlwaysInline requires a constant size!"); 03377 return getMemcpyLoadsAndStores(*this, dl, Chain, Dst, Src, 03378 ConstantSize->getZExtValue(), Align, true, 03379 DstSV, DstSVOff, SrcSV, SrcSVOff); 03380 } 03381 03382 // Emit a library call. 03383 TargetLowering::ArgListTy Args; 03384 TargetLowering::ArgListEntry Entry; 03385 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext()); 03386 Entry.Node = Dst; Args.push_back(Entry); 03387 Entry.Node = Src; Args.push_back(Entry); 03388 Entry.Node = Size; Args.push_back(Entry); 03389 // FIXME: pass in DebugLoc 03390 std::pair<SDValue,SDValue> CallResult = 03391 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()), 03392 false, false, false, false, 0, 03393 TLI.getLibcallCallingConv(RTLIB::MEMCPY), false, 03394 /*isReturnValueUsed=*/false, 03395 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMCPY), 03396 TLI.getPointerTy()), 03397 Args, *this, dl); 03398 return CallResult.second; 03399 } 03400 03401 SDValue SelectionDAG::getMemmove(SDValue Chain, DebugLoc dl, SDValue Dst, 03402 SDValue Src, SDValue Size, 03403 unsigned Align, 03404 const Value *DstSV, uint64_t DstSVOff, 03405 const Value *SrcSV, uint64_t SrcSVOff) { 03406 03407 // Check to see if we should lower the memmove to loads and stores first. 03408 // For cases within the target-specified limits, this is the best choice. 03409 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size); 03410 if (ConstantSize) { 03411 // Memmove with size zero? Just return the original chain. 03412 if (ConstantSize->isNullValue()) 03413 return Chain; 03414 03415 SDValue Result = 03416 getMemmoveLoadsAndStores(*this, dl, Chain, Dst, Src, 03417 ConstantSize->getZExtValue(), 03418 Align, false, DstSV, DstSVOff, SrcSV, SrcSVOff); 03419 if (Result.getNode()) 03420 return Result; 03421 } 03422 03423 // Then check to see if we should lower the memmove with target-specific 03424 // code. If the target chooses to do this, this is the next best. 03425 SDValue Result = 03426 TLI.EmitTargetCodeForMemmove(*this, dl, Chain, Dst, Src, Size, Align, 03427 DstSV, DstSVOff, SrcSV, SrcSVOff); 03428 if (Result.getNode()) 03429 return Result; 03430 03431 // Emit a library call. 03432 TargetLowering::ArgListTy Args; 03433 TargetLowering::ArgListEntry Entry; 03434 Entry.Ty = TLI.getTargetData()->getIntPtrType(*getContext()); 03435 Entry.Node = Dst; Args.push_back(Entry); 03436 Entry.Node = Src; Args.push_back(Entry); 03437 Entry.Node = Size; Args.push_back(Entry); 03438 // FIXME: pass in DebugLoc 03439 std::pair<SDValue,SDValue> CallResult = 03440 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()), 03441 false, false, false, false, 0, 03442 TLI.getLibcallCallingConv(RTLIB::MEMMOVE), false, 03443 /*isReturnValueUsed=*/false, 03444 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMMOVE), 03445 TLI.getPointerTy()), 03446 Args, *this, dl); 03447 return CallResult.second; 03448 } 03449 03450 SDValue SelectionDAG::getMemset(SDValue Chain, DebugLoc dl, SDValue Dst, 03451 SDValue Src, SDValue Size, 03452 unsigned Align, 03453 const Value *DstSV, uint64_t DstSVOff) { 03454 03455 // Check to see if we should lower the memset to stores first. 03456 // For cases within the target-specified limits, this is the best choice. 03457 ConstantSDNode *ConstantSize = dyn_cast<ConstantSDNode>(Size); 03458 if (ConstantSize) { 03459 // Memset with size zero? Just return the original chain. 03460 if (ConstantSize->isNullValue()) 03461 return Chain; 03462 03463 SDValue Result = 03464 getMemsetStores(*this, dl, Chain, Dst, Src, ConstantSize->getZExtValue(), 03465 Align, DstSV, DstSVOff); 03466 if (Result.getNode()) 03467 return Result; 03468 } 03469 03470 // Then check to see if we should lower the memset with target-specific 03471 // code. If the target chooses to do this, this is the next best. 03472 SDValue Result = 03473 TLI.EmitTargetCodeForMemset(*this, dl, Chain, Dst, Src, Size, Align, 03474 DstSV, DstSVOff); 03475 if (Result.getNode()) 03476 return Result; 03477 03478 // Emit a library call. 03479 const Type *IntPtrTy = TLI.getTargetData()->getIntPtrType(*getContext()); 03480 TargetLowering::ArgListTy Args; 03481 TargetLowering::ArgListEntry Entry; 03482 Entry.Node = Dst; Entry.Ty = IntPtrTy; 03483 Args.push_back(Entry); 03484 // Extend or truncate the argument to be an i32 value for the call. 03485 if (Src.getValueType().bitsGT(MVT::i32)) 03486 Src = getNode(ISD::TRUNCATE, dl, MVT::i32, Src); 03487 else 03488 Src = getNode(ISD::ZERO_EXTEND, dl, MVT::i32, Src); 03489 Entry.Node = Src; 03490 Entry.Ty = Type::getInt32Ty(*getContext()); 03491 Entry.isSExt = true; 03492 Args.push_back(Entry); 03493 Entry.Node = Size; 03494 Entry.Ty = IntPtrTy; 03495 Entry.isSExt = false; 03496 Args.push_back(Entry); 03497 // FIXME: pass in DebugLoc 03498 std::pair<SDValue,SDValue> CallResult = 03499 TLI.LowerCallTo(Chain, Type::getVoidTy(*getContext()), 03500 false, false, false, false, 0, 03501 TLI.getLibcallCallingConv(RTLIB::MEMSET), false, 03502 /*isReturnValueUsed=*/false, 03503 getExternalSymbol(TLI.getLibcallName(RTLIB::MEMSET), 03504 TLI.getPointerTy()), 03505 Args, *this, dl); 03506 return CallResult.second; 03507 } 03508 03509 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 03510 SDValue Chain, 03511 SDValue Ptr, SDValue Cmp, 03512 SDValue Swp, const Value* PtrVal, 03513 unsigned Alignment) { 03514 assert(Opcode == ISD::ATOMIC_CMP_SWAP && "Invalid Atomic Op"); 03515 assert(Cmp.getValueType() == Swp.getValueType() && "Invalid Atomic Op Types"); 03516 03517 EVT VT = Cmp.getValueType(); 03518 03519 if (Alignment == 0) // Ensure that codegen never sees alignment 0 03520 Alignment = getEVTAlignment(MemVT); 03521 03522 SDVTList VTs = getVTList(VT, MVT::Other); 03523 FoldingSetNodeID ID; 03524 ID.AddInteger(MemVT.getRawBits()); 03525 SDValue Ops[] = {Chain, Ptr, Cmp, Swp}; 03526 AddNodeIDNode(ID, Opcode, VTs, Ops, 4); 03527 void* IP = 0; 03528 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 03529 return SDValue(E, 0); 03530 SDNode* N = NodeAllocator.Allocate<AtomicSDNode>(); 03531 new (N) AtomicSDNode(Opcode, dl, VTs, MemVT, 03532 Chain, Ptr, Cmp, Swp, PtrVal, Alignment); 03533 CSEMap.InsertNode(N, IP); 03534 AllNodes.push_back(N); 03535 return SDValue(N, 0); 03536 } 03537 03538 SDValue SelectionDAG::getAtomic(unsigned Opcode, DebugLoc dl, EVT MemVT, 03539 SDValue Chain, 03540 SDValue Ptr, SDValue Val, 03541 const Value* PtrVal, 03542 unsigned Alignment) { 03543 assert((Opcode == ISD::ATOMIC_LOAD_ADD || 03544 Opcode == ISD::ATOMIC_LOAD_SUB || 03545 Opcode == ISD::ATOMIC_LOAD_AND || 03546 Opcode == ISD::ATOMIC_LOAD_OR || 03547 Opcode == ISD::ATOMIC_LOAD_XOR || 03548 Opcode == ISD::ATOMIC_LOAD_NAND || 03549 Opcode == ISD::ATOMIC_LOAD_MIN || 03550 Opcode == ISD::ATOMIC_LOAD_MAX || 03551 Opcode == ISD::ATOMIC_LOAD_UMIN || 03552 Opcode == ISD::ATOMIC_LOAD_UMAX || 03553 Opcode == ISD::ATOMIC_SWAP) && 03554 "Invalid Atomic Op"); 03555 03556 EVT VT = Val.getValueType(); 03557 03558 if (Alignment == 0) // Ensure that codegen never sees alignment 0 03559 Alignment = getEVTAlignment(MemVT); 03560 03561 SDVTList VTs = getVTList(VT, MVT::Other); 03562 FoldingSetNodeID ID; 03563 ID.AddInteger(MemVT.getRawBits()); 03564 SDValue Ops[] = {Chain, Ptr, Val}; 03565 AddNodeIDNode(ID, Opcode, VTs, Ops, 3); 03566 void* IP = 0; 03567 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 03568 return SDValue(E, 0); 03569 SDNode* N = NodeAllocator.Allocate<AtomicSDNode>(); 03570 new (N) AtomicSDNode(Opcode, dl, VTs, MemVT, 03571 Chain, Ptr, Val, PtrVal, Alignment); 03572 CSEMap.InsertNode(N, IP); 03573 AllNodes.push_back(N); 03574 return SDValue(N, 0); 03575 } 03576 03577 /// getMergeValues - Create a MERGE_VALUES node from the given operands. 03578 /// Allowed to return something different (and simpler) if Simplify is true. 03579 SDValue SelectionDAG::getMergeValues(const SDValue *Ops, unsigned NumOps, 03580 DebugLoc dl) { 03581 if (NumOps == 1) 03582 return Ops[0]; 03583 03584 SmallVector<EVT, 4> VTs; 03585 VTs.reserve(NumOps); 03586 for (unsigned i = 0; i < NumOps; ++i) 03587 VTs.push_back(Ops[i].getValueType()); 03588 return getNode(ISD::MERGE_VALUES, dl, getVTList(&VTs[0], NumOps), 03589 Ops, NumOps); 03590 } 03591 03592 SDValue 03593 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, 03594 const EVT *VTs, unsigned NumVTs, 03595 const SDValue *Ops, unsigned NumOps, 03596 EVT MemVT, const Value *srcValue, int SVOff, 03597 unsigned Align, bool Vol, 03598 bool ReadMem, bool WriteMem) { 03599 return getMemIntrinsicNode(Opcode, dl, makeVTList(VTs, NumVTs), Ops, NumOps, 03600 MemVT, srcValue, SVOff, Align, Vol, 03601 ReadMem, WriteMem); 03602 } 03603 03604 SDValue 03605 SelectionDAG::getMemIntrinsicNode(unsigned Opcode, DebugLoc dl, SDVTList VTList, 03606 const SDValue *Ops, unsigned NumOps, 03607 EVT MemVT, const Value *srcValue, int SVOff, 03608 unsigned Align, bool Vol, 03609 bool ReadMem, bool WriteMem) { 03610 // Memoize the node unless it returns a flag. 03611 MemIntrinsicSDNode *N; 03612 if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { 03613 FoldingSetNodeID ID; 03614 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 03615 void *IP = 0; 03616 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 03617 return SDValue(E, 0); 03618 03619 N = NodeAllocator.Allocate<MemIntrinsicSDNode>(); 03620 new (N) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps, MemVT, 03621 srcValue, SVOff, Align, Vol, ReadMem, WriteMem); 03622 CSEMap.InsertNode(N, IP); 03623 } else { 03624 N = NodeAllocator.Allocate<MemIntrinsicSDNode>(); 03625 new (N) MemIntrinsicSDNode(Opcode, dl, VTList, Ops, NumOps, MemVT, 03626 srcValue, SVOff, Align, Vol, ReadMem, WriteMem); 03627 } 03628 AllNodes.push_back(N); 03629 return SDValue(N, 0); 03630 } 03631 03632 SDValue 03633 SelectionDAG::getLoad(ISD::MemIndexedMode AM, DebugLoc dl, 03634 ISD::LoadExtType ExtType, EVT VT, SDValue Chain, 03635 SDValue Ptr, SDValue Offset, 03636 const Value *SV, int SVOffset, EVT EVT, 03637 bool isVolatile, unsigned Alignment) { 03638 if (Alignment == 0) // Ensure that codegen never sees alignment 0 03639 Alignment = getEVTAlignment(VT); 03640 03641 if (VT == EVT) { 03642 ExtType = ISD::NON_EXTLOAD; 03643 } else if (ExtType == ISD::NON_EXTLOAD) { 03644 assert(VT == EVT && "Non-extending load from different memory type!"); 03645 } else { 03646 // Extending load. 03647 if (VT.isVector()) 03648 assert(EVT.getVectorNumElements() == VT.getVectorNumElements() && 03649 "Invalid vector extload!"); 03650 else 03651 assert(EVT.bitsLT(VT) && 03652 "Should only be an extending load, not truncating!"); 03653 assert((ExtType == ISD::EXTLOAD || VT.isInteger()) && 03654 "Cannot sign/zero extend a FP/Vector load!"); 03655 assert(VT.isInteger() == EVT.isInteger() && 03656 "Cannot convert from FP to Int or Int -> FP!"); 03657 } 03658 03659 bool Indexed = AM != ISD::UNINDEXED; 03660 assert((Indexed || Offset.getOpcode() == ISD::UNDEF) && 03661 "Unindexed load with an offset!"); 03662 03663 SDVTList VTs = Indexed ? 03664 getVTList(VT, Ptr.getValueType(), MVT::Other) : getVTList(VT, MVT::Other); 03665 SDValue Ops[] = { Chain, Ptr, Offset }; 03666 FoldingSetNodeID ID; 03667 AddNodeIDNode(ID, ISD::LOAD, VTs, Ops, 3); 03668 ID.AddInteger(EVT.getRawBits()); 03669 ID.AddInteger(encodeMemSDNodeFlags(ExtType, AM, isVolatile, Alignment)); 03670 void *IP = 0; 03671 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 03672 return SDValue(E, 0); 03673 SDNode *N = NodeAllocator.Allocate<LoadSDNode>(); 03674 new (N) LoadSDNode(Ops, dl, VTs, AM, ExtType, EVT, SV, SVOffset, 03675 Alignment, isVolatile); 03676 CSEMap.InsertNode(N, IP); 03677 AllNodes.push_back(N); 03678 return SDValue(N, 0); 03679 } 03680 03681 SDValue SelectionDAG::getLoad(EVT VT, DebugLoc dl, 03682 SDValue Chain, SDValue Ptr, 03683 const Value *SV, int SVOffset, 03684 bool isVolatile, unsigned Alignment) { 03685 SDValue Undef = getUNDEF(Ptr.getValueType()); 03686 return getLoad(ISD::UNINDEXED, dl, ISD::NON_EXTLOAD, VT, Chain, Ptr, Undef, 03687 SV, SVOffset, VT, isVolatile, Alignment); 03688 } 03689 03690 SDValue SelectionDAG::getExtLoad(ISD::LoadExtType ExtType, DebugLoc dl, EVT VT, 03691 SDValue Chain, SDValue Ptr, 03692 const Value *SV, 03693 int SVOffset, EVT EVT, 03694 bool isVolatile, unsigned Alignment) { 03695 SDValue Undef = getUNDEF(Ptr.getValueType()); 03696 return getLoad(ISD::UNINDEXED, dl, ExtType, VT, Chain, Ptr, Undef, 03697 SV, SVOffset, EVT, isVolatile, Alignment); 03698 } 03699 03700 SDValue 03701 SelectionDAG::getIndexedLoad(SDValue OrigLoad, DebugLoc dl, SDValue Base, 03702 SDValue Offset, ISD::MemIndexedMode AM) { 03703 LoadSDNode *LD = cast<LoadSDNode>(OrigLoad); 03704 assert(LD->getOffset().getOpcode() == ISD::UNDEF && 03705 "Load is already a indexed load!"); 03706 return getLoad(AM, dl, LD->getExtensionType(), OrigLoad.getValueType(), 03707 LD->getChain(), Base, Offset, LD->getSrcValue(), 03708 LD->getSrcValueOffset(), LD->getMemoryVT(), 03709 LD->isVolatile(), LD->getAlignment()); 03710 } 03711 03712 SDValue SelectionDAG::getStore(SDValue Chain, DebugLoc dl, SDValue Val, 03713 SDValue Ptr, const Value *SV, int SVOffset, 03714 bool isVolatile, unsigned Alignment) { 03715 EVT VT = Val.getValueType(); 03716 03717 if (Alignment == 0) // Ensure that codegen never sees alignment 0 03718 Alignment = getEVTAlignment(VT); 03719 03720 SDVTList VTs = getVTList(MVT::Other); 03721 SDValue Undef = getUNDEF(Ptr.getValueType()); 03722 SDValue Ops[] = { Chain, Val, Ptr, Undef }; 03723 FoldingSetNodeID ID; 03724 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 03725 ID.AddInteger(VT.getRawBits()); 03726 ID.AddInteger(encodeMemSDNodeFlags(false, ISD::UNINDEXED, 03727 isVolatile, Alignment)); 03728 void *IP = 0; 03729 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 03730 return SDValue(E, 0); 03731 SDNode *N = NodeAllocator.Allocate<StoreSDNode>(); 03732 new (N) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED, false, 03733 VT, SV, SVOffset, Alignment, isVolatile); 03734 CSEMap.InsertNode(N, IP); 03735 AllNodes.push_back(N); 03736 return SDValue(N, 0); 03737 } 03738 03739 SDValue SelectionDAG::getTruncStore(SDValue Chain, DebugLoc dl, SDValue Val, 03740 SDValue Ptr, const Value *SV, 03741 int SVOffset, EVT SVT, 03742 bool isVolatile, unsigned Alignment) { 03743 EVT VT = Val.getValueType(); 03744 03745 if (VT == SVT) 03746 return getStore(Chain, dl, Val, Ptr, SV, SVOffset, isVolatile, Alignment); 03747 03748 assert(VT.bitsGT(SVT) && "Not a truncation?"); 03749 assert(VT.isInteger() == SVT.isInteger() && 03750 "Can't do FP-INT conversion!"); 03751 03752 if (Alignment == 0) // Ensure that codegen never sees alignment 0 03753 Alignment = getEVTAlignment(VT); 03754 03755 SDVTList VTs = getVTList(MVT::Other); 03756 SDValue Undef = getUNDEF(Ptr.getValueType()); 03757 SDValue Ops[] = { Chain, Val, Ptr, Undef }; 03758 FoldingSetNodeID ID; 03759 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 03760 ID.AddInteger(SVT.getRawBits()); 03761 ID.AddInteger(encodeMemSDNodeFlags(true, ISD::UNINDEXED, 03762 isVolatile, Alignment)); 03763 void *IP = 0; 03764 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 03765 return SDValue(E, 0); 03766 SDNode *N = NodeAllocator.Allocate<StoreSDNode>(); 03767 new (N) StoreSDNode(Ops, dl, VTs, ISD::UNINDEXED, true, 03768 SVT, SV, SVOffset, Alignment, isVolatile); 03769 CSEMap.InsertNode(N, IP); 03770 AllNodes.push_back(N); 03771 return SDValue(N, 0); 03772 } 03773 03774 SDValue 03775 SelectionDAG::getIndexedStore(SDValue OrigStore, DebugLoc dl, SDValue Base, 03776 SDValue Offset, ISD::MemIndexedMode AM) { 03777 StoreSDNode *ST = cast<StoreSDNode>(OrigStore); 03778 assert(ST->getOffset().getOpcode() == ISD::UNDEF && 03779 "Store is already a indexed store!"); 03780 SDVTList VTs = getVTList(Base.getValueType(), MVT::Other); 03781 SDValue Ops[] = { ST->getChain(), ST->getValue(), Base, Offset }; 03782 FoldingSetNodeID ID; 03783 AddNodeIDNode(ID, ISD::STORE, VTs, Ops, 4); 03784 ID.AddInteger(ST->getMemoryVT().getRawBits()); 03785 ID.AddInteger(ST->getRawSubclassData()); 03786 void *IP = 0; 03787 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 03788 return SDValue(E, 0); 03789 SDNode *N = NodeAllocator.Allocate<StoreSDNode>(); 03790 new (N) StoreSDNode(Ops, dl, VTs, AM, 03791 ST->isTruncatingStore(), ST->getMemoryVT(), 03792 ST->getSrcValue(), ST->getSrcValueOffset(), 03793 ST->getAlignment(), ST->isVolatile()); 03794 CSEMap.InsertNode(N, IP); 03795 AllNodes.push_back(N); 03796 return SDValue(N, 0); 03797 } 03798 03799 SDValue SelectionDAG::getVAArg(EVT VT, DebugLoc dl, 03800 SDValue Chain, SDValue Ptr, 03801 SDValue SV) { 03802 SDValue Ops[] = { Chain, Ptr, SV }; 03803 return getNode(ISD::VAARG, dl, getVTList(VT, MVT::Other), Ops, 3); 03804 } 03805 03806 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 03807 const SDUse *Ops, unsigned NumOps) { 03808 switch (NumOps) { 03809 case 0: return getNode(Opcode, DL, VT); 03810 case 1: return getNode(Opcode, DL, VT, Ops[0]); 03811 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]); 03812 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]); 03813 default: break; 03814 } 03815 03816 // Copy from an SDUse array into an SDValue array for use with 03817 // the regular getNode logic. 03818 SmallVector<SDValue, 8> NewOps(Ops, Ops + NumOps); 03819 return getNode(Opcode, DL, VT, &NewOps[0], NumOps); 03820 } 03821 03822 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, EVT VT, 03823 const SDValue *Ops, unsigned NumOps) { 03824 switch (NumOps) { 03825 case 0: return getNode(Opcode, DL, VT); 03826 case 1: return getNode(Opcode, DL, VT, Ops[0]); 03827 case 2: return getNode(Opcode, DL, VT, Ops[0], Ops[1]); 03828 case 3: return getNode(Opcode, DL, VT, Ops[0], Ops[1], Ops[2]); 03829 default: break; 03830 } 03831 03832 switch (Opcode) { 03833 default: break; 03834 case ISD::SELECT_CC: { 03835 assert(NumOps == 5 && "SELECT_CC takes 5 operands!"); 03836 assert(Ops[0].getValueType() == Ops[1].getValueType() && 03837 "LHS and RHS of condition must have same type!"); 03838 assert(Ops[2].getValueType() == Ops[3].getValueType() && 03839 "True and False arms of SelectCC must have same type!"); 03840 assert(Ops[2].getValueType() == VT && 03841 "select_cc node must be of same type as true and false value!"); 03842 break; 03843 } 03844 case ISD::BR_CC: { 03845 assert(NumOps == 5 && "BR_CC takes 5 operands!"); 03846 assert(Ops[2].getValueType() == Ops[3].getValueType() && 03847 "LHS/RHS of comparison should match types!"); 03848 break; 03849 } 03850 } 03851 03852 // Memoize nodes. 03853 SDNode *N; 03854 SDVTList VTs = getVTList(VT); 03855 03856 if (VT != MVT::Flag) { 03857 FoldingSetNodeID ID; 03858 AddNodeIDNode(ID, Opcode, VTs, Ops, NumOps); 03859 void *IP = 0; 03860 03861 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 03862 return SDValue(E, 0); 03863 03864 N = NodeAllocator.Allocate<SDNode>(); 03865 new (N) SDNode(Opcode, DL, VTs, Ops, NumOps); 03866 CSEMap.InsertNode(N, IP); 03867 } else { 03868 N = NodeAllocator.Allocate<SDNode>(); 03869 new (N) SDNode(Opcode, DL, VTs, Ops, NumOps); 03870 } 03871 03872 AllNodes.push_back(N); 03873 #ifndef NDEBUG 03874 VerifyNode(N); 03875 #endif 03876 return SDValue(N, 0); 03877 } 03878 03879 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, 03880 const std::vector<EVT> &ResultTys, 03881 const SDValue *Ops, unsigned NumOps) { 03882 return getNode(Opcode, DL, getVTList(&ResultTys[0], ResultTys.size()), 03883 Ops, NumOps); 03884 } 03885 03886 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, 03887 const EVT *VTs, unsigned NumVTs, 03888 const SDValue *Ops, unsigned NumOps) { 03889 if (NumVTs == 1) 03890 return getNode(Opcode, DL, VTs[0], Ops, NumOps); 03891 return getNode(Opcode, DL, makeVTList(VTs, NumVTs), Ops, NumOps); 03892 } 03893 03894 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 03895 const SDValue *Ops, unsigned NumOps) { 03896 if (VTList.NumVTs == 1) 03897 return getNode(Opcode, DL, VTList.VTs[0], Ops, NumOps); 03898 03899 #if 0 03900 switch (Opcode) { 03901 // FIXME: figure out how to safely handle things like 03902 // int foo(int x) { return 1 << (x & 255); } 03903 // int bar() { return foo(256); } 03904 case ISD::SRA_PARTS: 03905 case ISD::SRL_PARTS: 03906 case ISD::SHL_PARTS: 03907 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG && 03908 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1) 03909 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0)); 03910 else if (N3.getOpcode() == ISD::AND) 03911 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) { 03912 // If the and is only masking out bits that cannot effect the shift, 03913 // eliminate the and. 03914 unsigned NumBits = VT.getSizeInBits()*2; 03915 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 03916 return getNode(Opcode, DL, VT, N1, N2, N3.getOperand(0)); 03917 } 03918 break; 03919 } 03920 #endif 03921 03922 // Memoize the node unless it returns a flag. 03923 SDNode *N; 03924 if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { 03925 FoldingSetNodeID ID; 03926 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 03927 void *IP = 0; 03928 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 03929 return SDValue(E, 0); 03930 if (NumOps == 1) { 03931 N = NodeAllocator.Allocate<UnarySDNode>(); 03932 new (N) UnarySDNode(Opcode, DL, VTList, Ops[0]); 03933 } else if (NumOps == 2) { 03934 N = NodeAllocator.Allocate<BinarySDNode>(); 03935 new (N) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]); 03936 } else if (NumOps == 3) { 03937 N = NodeAllocator.Allocate<TernarySDNode>(); 03938 new (N) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1], Ops[2]); 03939 } else { 03940 N = NodeAllocator.Allocate<SDNode>(); 03941 new (N) SDNode(Opcode, DL, VTList, Ops, NumOps); 03942 } 03943 CSEMap.InsertNode(N, IP); 03944 } else { 03945 if (NumOps == 1) { 03946 N = NodeAllocator.Allocate<UnarySDNode>(); 03947 new (N) UnarySDNode(Opcode, DL, VTList, Ops[0]); 03948 } else if (NumOps == 2) { 03949 N = NodeAllocator.Allocate<BinarySDNode>(); 03950 new (N) BinarySDNode(Opcode, DL, VTList, Ops[0], Ops[1]); 03951 } else if (NumOps == 3) { 03952 N = NodeAllocator.Allocate<TernarySDNode>(); 03953 new (N) TernarySDNode(Opcode, DL, VTList, Ops[0], Ops[1], Ops[2]); 03954 } else { 03955 N = NodeAllocator.Allocate<SDNode>(); 03956 new (N) SDNode(Opcode, DL, VTList, Ops, NumOps); 03957 } 03958 } 03959 AllNodes.push_back(N); 03960 #ifndef NDEBUG 03961 VerifyNode(N); 03962 #endif 03963 return SDValue(N, 0); 03964 } 03965 03966 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList) { 03967 return getNode(Opcode, DL, VTList, 0, 0); 03968 } 03969 03970 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 03971 SDValue N1) { 03972 SDValue Ops[] = { N1 }; 03973 return getNode(Opcode, DL, VTList, Ops, 1); 03974 } 03975 03976 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 03977 SDValue N1, SDValue N2) { 03978 SDValue Ops[] = { N1, N2 }; 03979 return getNode(Opcode, DL, VTList, Ops, 2); 03980 } 03981 03982 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 03983 SDValue N1, SDValue N2, SDValue N3) { 03984 SDValue Ops[] = { N1, N2, N3 }; 03985 return getNode(Opcode, DL, VTList, Ops, 3); 03986 } 03987 03988 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 03989 SDValue N1, SDValue N2, SDValue N3, 03990 SDValue N4) { 03991 SDValue Ops[] = { N1, N2, N3, N4 }; 03992 return getNode(Opcode, DL, VTList, Ops, 4); 03993 } 03994 03995 SDValue SelectionDAG::getNode(unsigned Opcode, DebugLoc DL, SDVTList VTList, 03996 SDValue N1, SDValue N2, SDValue N3, 03997 SDValue N4, SDValue N5) { 03998 SDValue Ops[] = { N1, N2, N3, N4, N5 }; 03999 return getNode(Opcode, DL, VTList, Ops, 5); 04000 } 04001 04002 SDVTList SelectionDAG::getVTList(EVT VT) { 04003 return makeVTList(SDNode::getValueTypeList(VT), 1); 04004 } 04005 04006 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2) { 04007 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 04008 E = VTList.rend(); I != E; ++I) 04009 if (I->NumVTs == 2 && I->VTs[0] == VT1 && I->VTs[1] == VT2) 04010 return *I; 04011 04012 EVT *Array = Allocator.Allocate<EVT>(2); 04013 Array[0] = VT1; 04014 Array[1] = VT2; 04015 SDVTList Result = makeVTList(Array, 2); 04016 VTList.push_back(Result); 04017 return Result; 04018 } 04019 04020 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3) { 04021 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 04022 E = VTList.rend(); I != E; ++I) 04023 if (I->NumVTs == 3 && I->VTs[0] == VT1 && I->VTs[1] == VT2 && 04024 I->VTs[2] == VT3) 04025 return *I; 04026 04027 EVT *Array = Allocator.Allocate<EVT>(3); 04028 Array[0] = VT1; 04029 Array[1] = VT2; 04030 Array[2] = VT3; 04031 SDVTList Result = makeVTList(Array, 3); 04032 VTList.push_back(Result); 04033 return Result; 04034 } 04035 04036 SDVTList SelectionDAG::getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4) { 04037 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 04038 E = VTList.rend(); I != E; ++I) 04039 if (I->NumVTs == 4 && I->VTs[0] == VT1 && I->VTs[1] == VT2 && 04040 I->VTs[2] == VT3 && I->VTs[3] == VT4) 04041 return *I; 04042 04043 EVT *Array = Allocator.Allocate<EVT>(3); 04044 Array[0] = VT1; 04045 Array[1] = VT2; 04046 Array[2] = VT3; 04047 Array[3] = VT4; 04048 SDVTList Result = makeVTList(Array, 4); 04049 VTList.push_back(Result); 04050 return Result; 04051 } 04052 04053 SDVTList SelectionDAG::getVTList(const EVT *VTs, unsigned NumVTs) { 04054 switch (NumVTs) { 04055 case 0: llvm_unreachable("Cannot have nodes without results!"); 04056 case 1: return getVTList(VTs[0]); 04057 case 2: return getVTList(VTs[0], VTs[1]); 04058 case 3: return getVTList(VTs[0], VTs[1], VTs[2]); 04059 default: break; 04060 } 04061 04062 for (std::vector<SDVTList>::reverse_iterator I = VTList.rbegin(), 04063 E = VTList.rend(); I != E; ++I) { 04064 if (I->NumVTs != NumVTs || VTs[0] != I->VTs[0] || VTs[1] != I->VTs[1]) 04065 continue; 04066 04067 bool NoMatch = false; 04068 for (unsigned i = 2; i != NumVTs; ++i) 04069 if (VTs[i] != I->VTs[i]) { 04070 NoMatch = true; 04071 break; 04072 } 04073 if (!NoMatch) 04074 return *I; 04075 } 04076 04077 EVT *Array = Allocator.Allocate<EVT>(NumVTs); 04078 std::copy(VTs, VTs+NumVTs, Array); 04079 SDVTList Result = makeVTList(Array, NumVTs); 04080 VTList.push_back(Result); 04081 return Result; 04082 } 04083 04084 04085 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 04086 /// specified operands. If the resultant node already exists in the DAG, 04087 /// this does not modify the specified node, instead it returns the node that 04088 /// already exists. If the resultant node does not exist in the DAG, the 04089 /// input node is returned. As a degenerate case, if you specify the same 04090 /// input operands as the node already has, the input node is returned. 04091 SDValue SelectionDAG::UpdateNodeOperands(SDValue InN, SDValue Op) { 04092 SDNode *N = InN.getNode(); 04093 assert(N->getNumOperands() == 1 && "Update with wrong number of operands"); 04094 04095 // Check to see if there is no change. 04096 if (Op == N->getOperand(0)) return InN; 04097 04098 // See if the modified node already exists. 04099 void *InsertPos = 0; 04100 if (SDNode *Existing = FindModifiedNodeSlot(N, Op, InsertPos)) 04101 return SDValue(Existing, InN.getResNo()); 04102 04103 // Nope it doesn't. Remove the node from its current place in the maps. 04104 if (InsertPos) 04105 if (!RemoveNodeFromCSEMaps(N)) 04106 InsertPos = 0; 04107 04108 // Now we update the operands. 04109 N->OperandList[0].set(Op); 04110 04111 // If this gets put into a CSE map, add it. 04112 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 04113 return InN; 04114 } 04115 04116 SDValue SelectionDAG:: 04117 UpdateNodeOperands(SDValue InN, SDValue Op1, SDValue Op2) { 04118 SDNode *N = InN.getNode(); 04119 assert(N->getNumOperands() == 2 && "Update with wrong number of operands"); 04120 04121 // Check to see if there is no change. 04122 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1)) 04123 return InN; // No operands changed, just return the input node. 04124 04125 // See if the modified node already exists. 04126 void *InsertPos = 0; 04127 if (SDNode *Existing = FindModifiedNodeSlot(N, Op1, Op2, InsertPos)) 04128 return SDValue(Existing, InN.getResNo()); 04129 04130 // Nope it doesn't. Remove the node from its current place in the maps. 04131 if (InsertPos) 04132 if (!RemoveNodeFromCSEMaps(N)) 04133 InsertPos = 0; 04134 04135 // Now we update the operands. 04136 if (N->OperandList[0] != Op1) 04137 N->OperandList[0].set(Op1); 04138 if (N->OperandList[1] != Op2) 04139 N->OperandList[1].set(Op2); 04140 04141 // If this gets put into a CSE map, add it. 04142 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 04143 return InN; 04144 } 04145 04146 SDValue SelectionDAG:: 04147 UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, SDValue Op3) { 04148 SDValue Ops[] = { Op1, Op2, Op3 }; 04149 return UpdateNodeOperands(N, Ops, 3); 04150 } 04151 04152 SDValue SelectionDAG:: 04153 UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 04154 SDValue Op3, SDValue Op4) { 04155 SDValue Ops[] = { Op1, Op2, Op3, Op4 }; 04156 return UpdateNodeOperands(N, Ops, 4); 04157 } 04158 04159 SDValue SelectionDAG:: 04160 UpdateNodeOperands(SDValue N, SDValue Op1, SDValue Op2, 04161 SDValue Op3, SDValue Op4, SDValue Op5) { 04162 SDValue Ops[] = { Op1, Op2, Op3, Op4, Op5 }; 04163 return UpdateNodeOperands(N, Ops, 5); 04164 } 04165 04166 SDValue SelectionDAG:: 04167 UpdateNodeOperands(SDValue InN, const SDValue *Ops, unsigned NumOps) { 04168 SDNode *N = InN.getNode(); 04169 assert(N->getNumOperands() == NumOps && 04170 "Update with wrong number of operands"); 04171 04172 // Check to see if there is no change. 04173 bool AnyChange = false; 04174 for (unsigned i = 0; i != NumOps; ++i) { 04175 if (Ops[i] != N->getOperand(i)) { 04176 AnyChange = true; 04177 break; 04178 } 04179 } 04180 04181 // No operands changed, just return the input node. 04182 if (!AnyChange) return InN; 04183 04184 // See if the modified node already exists. 04185 void *InsertPos = 0; 04186 if (SDNode *Existing = FindModifiedNodeSlot(N, Ops, NumOps, InsertPos)) 04187 return SDValue(Existing, InN.getResNo()); 04188 04189 // Nope it doesn't. Remove the node from its current place in the maps. 04190 if (InsertPos) 04191 if (!RemoveNodeFromCSEMaps(N)) 04192 InsertPos = 0; 04193 04194 // Now we update the operands. 04195 for (unsigned i = 0; i != NumOps; ++i) 04196 if (N->OperandList[i] != Ops[i]) 04197 N->OperandList[i].set(Ops[i]); 04198 04199 // If this gets put into a CSE map, add it. 04200 if (InsertPos) CSEMap.InsertNode(N, InsertPos); 04201 return InN; 04202 } 04203 04204 /// DropOperands - Release the operands and set this node to have 04205 /// zero operands. 04206 void SDNode::DropOperands() { 04207 // Unlike the code in MorphNodeTo that does this, we don't need to 04208 // watch for dead nodes here. 04209 for (op_iterator I = op_begin(), E = op_end(); I != E; ) { 04210 SDUse &Use = *I++; 04211 Use.set(SDValue()); 04212 } 04213 } 04214 04215 /// SelectNodeTo - These are wrappers around MorphNodeTo that accept a 04216 /// machine opcode. 04217 /// 04218 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04219 EVT VT) { 04220 SDVTList VTs = getVTList(VT); 04221 return SelectNodeTo(N, MachineOpc, VTs, 0, 0); 04222 } 04223 04224 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04225 EVT VT, SDValue Op1) { 04226 SDVTList VTs = getVTList(VT); 04227 SDValue Ops[] = { Op1 }; 04228 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1); 04229 } 04230 04231 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04232 EVT VT, SDValue Op1, 04233 SDValue Op2) { 04234 SDVTList VTs = getVTList(VT); 04235 SDValue Ops[] = { Op1, Op2 }; 04236 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2); 04237 } 04238 04239 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04240 EVT VT, SDValue Op1, 04241 SDValue Op2, SDValue Op3) { 04242 SDVTList VTs = getVTList(VT); 04243 SDValue Ops[] = { Op1, Op2, Op3 }; 04244 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); 04245 } 04246 04247 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04248 EVT VT, const SDValue *Ops, 04249 unsigned NumOps) { 04250 SDVTList VTs = getVTList(VT); 04251 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 04252 } 04253 04254 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04255 EVT VT1, EVT VT2, const SDValue *Ops, 04256 unsigned NumOps) { 04257 SDVTList VTs = getVTList(VT1, VT2); 04258 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 04259 } 04260 04261 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04262 EVT VT1, EVT VT2) { 04263 SDVTList VTs = getVTList(VT1, VT2); 04264 return SelectNodeTo(N, MachineOpc, VTs, (SDValue *)0, 0); 04265 } 04266 04267 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04268 EVT VT1, EVT VT2, EVT VT3, 04269 const SDValue *Ops, unsigned NumOps) { 04270 SDVTList VTs = getVTList(VT1, VT2, VT3); 04271 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 04272 } 04273 04274 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04275 EVT VT1, EVT VT2, EVT VT3, EVT VT4, 04276 const SDValue *Ops, unsigned NumOps) { 04277 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4); 04278 return SelectNodeTo(N, MachineOpc, VTs, Ops, NumOps); 04279 } 04280 04281 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04282 EVT VT1, EVT VT2, 04283 SDValue Op1) { 04284 SDVTList VTs = getVTList(VT1, VT2); 04285 SDValue Ops[] = { Op1 }; 04286 return SelectNodeTo(N, MachineOpc, VTs, Ops, 1); 04287 } 04288 04289 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04290 EVT VT1, EVT VT2, 04291 SDValue Op1, SDValue Op2) { 04292 SDVTList VTs = getVTList(VT1, VT2); 04293 SDValue Ops[] = { Op1, Op2 }; 04294 return SelectNodeTo(N, MachineOpc, VTs, Ops, 2); 04295 } 04296 04297 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04298 EVT VT1, EVT VT2, 04299 SDValue Op1, SDValue Op2, 04300 SDValue Op3) { 04301 SDVTList VTs = getVTList(VT1, VT2); 04302 SDValue Ops[] = { Op1, Op2, Op3 }; 04303 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); 04304 } 04305 04306 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04307 EVT VT1, EVT VT2, EVT VT3, 04308 SDValue Op1, SDValue Op2, 04309 SDValue Op3) { 04310 SDVTList VTs = getVTList(VT1, VT2, VT3); 04311 SDValue Ops[] = { Op1, Op2, Op3 }; 04312 return SelectNodeTo(N, MachineOpc, VTs, Ops, 3); 04313 } 04314 04315 SDNode *SelectionDAG::SelectNodeTo(SDNode *N, unsigned MachineOpc, 04316 SDVTList VTs, const SDValue *Ops, 04317 unsigned NumOps) { 04318 return MorphNodeTo(N, ~MachineOpc, VTs, Ops, NumOps); 04319 } 04320 04321 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04322 EVT VT) { 04323 SDVTList VTs = getVTList(VT); 04324 return MorphNodeTo(N, Opc, VTs, 0, 0); 04325 } 04326 04327 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04328 EVT VT, SDValue Op1) { 04329 SDVTList VTs = getVTList(VT); 04330 SDValue Ops[] = { Op1 }; 04331 return MorphNodeTo(N, Opc, VTs, Ops, 1); 04332 } 04333 04334 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04335 EVT VT, SDValue Op1, 04336 SDValue Op2) { 04337 SDVTList VTs = getVTList(VT); 04338 SDValue Ops[] = { Op1, Op2 }; 04339 return MorphNodeTo(N, Opc, VTs, Ops, 2); 04340 } 04341 04342 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04343 EVT VT, SDValue Op1, 04344 SDValue Op2, SDValue Op3) { 04345 SDVTList VTs = getVTList(VT); 04346 SDValue Ops[] = { Op1, Op2, Op3 }; 04347 return MorphNodeTo(N, Opc, VTs, Ops, 3); 04348 } 04349 04350 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04351 EVT VT, const SDValue *Ops, 04352 unsigned NumOps) { 04353 SDVTList VTs = getVTList(VT); 04354 return MorphNodeTo(N, Opc, VTs, Ops, NumOps); 04355 } 04356 04357 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04358 EVT VT1, EVT VT2, const SDValue *Ops, 04359 unsigned NumOps) { 04360 SDVTList VTs = getVTList(VT1, VT2); 04361 return MorphNodeTo(N, Opc, VTs, Ops, NumOps); 04362 } 04363 04364 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04365 EVT VT1, EVT VT2) { 04366 SDVTList VTs = getVTList(VT1, VT2); 04367 return MorphNodeTo(N, Opc, VTs, (SDValue *)0, 0); 04368 } 04369 04370 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04371 EVT VT1, EVT VT2, EVT VT3, 04372 const SDValue *Ops, unsigned NumOps) { 04373 SDVTList VTs = getVTList(VT1, VT2, VT3); 04374 return MorphNodeTo(N, Opc, VTs, Ops, NumOps); 04375 } 04376 04377 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04378 EVT VT1, EVT VT2, 04379 SDValue Op1) { 04380 SDVTList VTs = getVTList(VT1, VT2); 04381 SDValue Ops[] = { Op1 }; 04382 return MorphNodeTo(N, Opc, VTs, Ops, 1); 04383 } 04384 04385 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04386 EVT VT1, EVT VT2, 04387 SDValue Op1, SDValue Op2) { 04388 SDVTList VTs = getVTList(VT1, VT2); 04389 SDValue Ops[] = { Op1, Op2 }; 04390 return MorphNodeTo(N, Opc, VTs, Ops, 2); 04391 } 04392 04393 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04394 EVT VT1, EVT VT2, 04395 SDValue Op1, SDValue Op2, 04396 SDValue Op3) { 04397 SDVTList VTs = getVTList(VT1, VT2); 04398 SDValue Ops[] = { Op1, Op2, Op3 }; 04399 return MorphNodeTo(N, Opc, VTs, Ops, 3); 04400 } 04401 04402 /// MorphNodeTo - These *mutate* the specified node to have the specified 04403 /// return type, opcode, and operands. 04404 /// 04405 /// Note that MorphNodeTo returns the resultant node. If there is already a 04406 /// node of the specified opcode and operands, it returns that node instead of 04407 /// the current one. Note that the DebugLoc need not be the same. 04408 /// 04409 /// Using MorphNodeTo is faster than creating a new node and swapping it in 04410 /// with ReplaceAllUsesWith both because it often avoids allocating a new 04411 /// node, and because it doesn't require CSE recalculation for any of 04412 /// the node's users. 04413 /// 04414 SDNode *SelectionDAG::MorphNodeTo(SDNode *N, unsigned Opc, 04415 SDVTList VTs, const SDValue *Ops, 04416 unsigned NumOps) { 04417 // If an identical node already exists, use it. 04418 void *IP = 0; 04419 if (VTs.VTs[VTs.NumVTs-1] != MVT::Flag) { 04420 FoldingSetNodeID ID; 04421 AddNodeIDNode(ID, Opc, VTs, Ops, NumOps); 04422 if (SDNode *ON = CSEMap.FindNodeOrInsertPos(ID, IP)) 04423 return ON; 04424 } 04425 04426 if (!RemoveNodeFromCSEMaps(N)) 04427 IP = 0; 04428 04429 // Start the morphing. 04430 N->NodeType = Opc; 04431 N->ValueList = VTs.VTs; 04432 N->NumValues = VTs.NumVTs; 04433 04434 // Clear the operands list, updating used nodes to remove this from their 04435 // use list. Keep track of any operands that become dead as a result. 04436 SmallPtrSet<SDNode*, 16> DeadNodeSet; 04437 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ) { 04438 SDUse &Use = *I++; 04439 SDNode *Used = Use.getNode(); 04440 Use.set(SDValue()); 04441 if (Used->use_empty()) 04442 DeadNodeSet.insert(Used); 04443 } 04444 04445 // If NumOps is larger than the # of operands we currently have, reallocate 04446 // the operand list. 04447 if (NumOps > N->NumOperands) { 04448 if (N->OperandsNeedDelete) 04449 delete[] N->OperandList; 04450 04451 if (N->isMachineOpcode()) { 04452 // We're creating a final node that will live unmorphed for the 04453 // remainder of the current SelectionDAG iteration, so we can allocate 04454 // the operands directly out of a pool with no recycling metadata. 04455 N->OperandList = OperandAllocator.Allocate<SDUse>(NumOps); 04456 N->OperandsNeedDelete = false; 04457 } else { 04458 N->OperandList = new SDUse[NumOps]; 04459 N->OperandsNeedDelete = true; 04460 } 04461 } 04462 04463 // Assign the new operands. 04464 N->NumOperands = NumOps; 04465 for (unsigned i = 0, e = NumOps; i != e; ++i) { 04466 N->OperandList[i].setUser(N); 04467 N->OperandList[i].setInitial(Ops[i]); 04468 } 04469 04470 // Delete any nodes that are still dead after adding the uses for the 04471 // new operands. 04472 SmallVector<SDNode *, 16> DeadNodes; 04473 for (SmallPtrSet<SDNode *, 16>::iterator I = DeadNodeSet.begin(), 04474 E = DeadNodeSet.end(); I != E; ++I) 04475 if ((*I)->use_empty()) 04476 DeadNodes.push_back(*I); 04477 RemoveDeadNodes(DeadNodes); 04478 04479 if (IP) 04480 CSEMap.InsertNode(N, IP); // Memoize the new node. 04481 return N; 04482 } 04483 04484 04485 /// getTargetNode - These are used for target selectors to create a new node 04486 /// with specified return type(s), target opcode, and operands. 04487 /// 04488 /// Note that getTargetNode returns the resultant node. If there is already a 04489 /// node of the specified opcode and operands, it returns that node instead of 04490 /// the current one. 04491 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT) { 04492 return getNode(~Opcode, dl, VT).getNode(); 04493 } 04494 04495 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT, 04496 SDValue Op1) { 04497 return getNode(~Opcode, dl, VT, Op1).getNode(); 04498 } 04499 04500 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT, 04501 SDValue Op1, SDValue Op2) { 04502 return getNode(~Opcode, dl, VT, Op1, Op2).getNode(); 04503 } 04504 04505 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT, 04506 SDValue Op1, SDValue Op2, 04507 SDValue Op3) { 04508 return getNode(~Opcode, dl, VT, Op1, Op2, Op3).getNode(); 04509 } 04510 04511 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT, 04512 const SDValue *Ops, unsigned NumOps) { 04513 return getNode(~Opcode, dl, VT, Ops, NumOps).getNode(); 04514 } 04515 04516 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, 04517 EVT VT1, EVT VT2) { 04518 SDVTList VTs = getVTList(VT1, VT2); 04519 SDValue Op; 04520 return getNode(~Opcode, dl, VTs, &Op, 0).getNode(); 04521 } 04522 04523 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, 04524 EVT VT2, SDValue Op1) { 04525 SDVTList VTs = getVTList(VT1, VT2); 04526 return getNode(~Opcode, dl, VTs, &Op1, 1).getNode(); 04527 } 04528 04529 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, 04530 EVT VT2, SDValue Op1, 04531 SDValue Op2) { 04532 SDVTList VTs = getVTList(VT1, VT2); 04533 SDValue Ops[] = { Op1, Op2 }; 04534 return getNode(~Opcode, dl, VTs, Ops, 2).getNode(); 04535 } 04536 04537 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, 04538 EVT VT2, SDValue Op1, 04539 SDValue Op2, SDValue Op3) { 04540 SDVTList VTs = getVTList(VT1, VT2); 04541 SDValue Ops[] = { Op1, Op2, Op3 }; 04542 return getNode(~Opcode, dl, VTs, Ops, 3).getNode(); 04543 } 04544 04545 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, 04546 EVT VT1, EVT VT2, 04547 const SDValue *Ops, unsigned NumOps) { 04548 SDVTList VTs = getVTList(VT1, VT2); 04549 return getNode(~Opcode, dl, VTs, Ops, NumOps).getNode(); 04550 } 04551 04552 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, 04553 EVT VT1, EVT VT2, EVT VT3, 04554 SDValue Op1, SDValue Op2) { 04555 SDVTList VTs = getVTList(VT1, VT2, VT3); 04556 SDValue Ops[] = { Op1, Op2 }; 04557 return getNode(~Opcode, dl, VTs, Ops, 2).getNode(); 04558 } 04559 04560 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, 04561 EVT VT1, EVT VT2, EVT VT3, 04562 SDValue Op1, SDValue Op2, 04563 SDValue Op3) { 04564 SDVTList VTs = getVTList(VT1, VT2, VT3); 04565 SDValue Ops[] = { Op1, Op2, Op3 }; 04566 return getNode(~Opcode, dl, VTs, Ops, 3).getNode(); 04567 } 04568 04569 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, 04570 EVT VT1, EVT VT2, EVT VT3, 04571 const SDValue *Ops, unsigned NumOps) { 04572 SDVTList VTs = getVTList(VT1, VT2, VT3); 04573 return getNode(~Opcode, dl, VTs, Ops, NumOps).getNode(); 04574 } 04575 04576 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, EVT VT1, 04577 EVT VT2, EVT VT3, EVT VT4, 04578 const SDValue *Ops, unsigned NumOps) { 04579 SDVTList VTs = getVTList(VT1, VT2, VT3, VT4); 04580 return getNode(~Opcode, dl, VTs, Ops, NumOps).getNode(); 04581 } 04582 04583 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, DebugLoc dl, 04584 const std::vector<EVT> &ResultTys, 04585 const SDValue *Ops, unsigned NumOps) { 04586 return getNode(~Opcode, dl, ResultTys, Ops, NumOps).getNode(); 04587 } 04588 04589 /// getTargetExtractSubreg - A convenience function for creating 04590 /// TargetInstrInfo::EXTRACT_SUBREG nodes. 04591 SDValue 04592 SelectionDAG::getTargetExtractSubreg(int SRIdx, DebugLoc DL, EVT VT, 04593 SDValue Operand) { 04594 SDValue SRIdxVal = getTargetConstant(SRIdx, MVT::i32); 04595 SDNode *Subreg = getTargetNode(TargetInstrInfo::EXTRACT_SUBREG, DL, 04596 VT, Operand, SRIdxVal); 04597 return SDValue(Subreg, 0); 04598 } 04599 04600 /// getNodeIfExists - Get the specified node if it's already available, or 04601 /// else return NULL. 04602 SDNode *SelectionDAG::getNodeIfExists(unsigned Opcode, SDVTList VTList, 04603 const SDValue *Ops, unsigned NumOps) { 04604 if (VTList.VTs[VTList.NumVTs-1] != MVT::Flag) { 04605 FoldingSetNodeID ID; 04606 AddNodeIDNode(ID, Opcode, VTList, Ops, NumOps); 04607 void *IP = 0; 04608 if (SDNode *E = CSEMap.FindNodeOrInsertPos(ID, IP)) 04609 return E; 04610 } 04611 return NULL; 04612 } 04613 04614 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 04615 /// This can cause recursive merging of nodes in the DAG. 04616 /// 04617 /// This version assumes From has a single result value. 04618 /// 04619 void SelectionDAG::ReplaceAllUsesWith(SDValue FromN, SDValue To, 04620 DAGUpdateListener *UpdateListener) { 04621 SDNode *From = FromN.getNode(); 04622 assert(From->getNumValues() == 1 && FromN.getResNo() == 0 && 04623 "Cannot replace with this method!"); 04624 assert(From != To.getNode() && "Cannot replace uses of with self"); 04625 04626 // Iterate over all the existing uses of From. New uses will be added 04627 // to the beginning of the use list, which we avoid visiting. 04628 // This specifically avoids visiting uses of From that arise while the 04629 // replacement is happening, because any such uses would be the result 04630 // of CSE: If an existing node looks like From after one of its operands 04631 // is replaced by To, we don't want to replace of all its users with To 04632 // too. See PR3018 for more info. 04633 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); 04634 while (UI != UE) { 04635 SDNode *User = *UI; 04636 04637 // This node is about to morph, remove its old self from the CSE maps. 04638 RemoveNodeFromCSEMaps(User); 04639 04640 // A user can appear in a use list multiple times, and when this 04641 // happens the uses are usually next to each other in the list. 04642 // To help reduce the number of CSE recomputations, process all 04643 // the uses of this user that we can find this way. 04644 do { 04645 SDUse &Use = UI.getUse(); 04646 ++UI; 04647 Use.set(To); 04648 } while (UI != UE && *UI == User); 04649 04650 // Now that we have modified User, add it back to the CSE maps. If it 04651 // already exists there, recursively merge the results together. 04652 AddModifiedNodeToCSEMaps(User, UpdateListener); 04653 } 04654 } 04655 04656 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 04657 /// This can cause recursive merging of nodes in the DAG. 04658 /// 04659 /// This version assumes that for each value of From, there is a 04660 /// corresponding value in To in the same position with the same type. 04661 /// 04662 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, 04663 DAGUpdateListener *UpdateListener) { 04664 #ifndef NDEBUG 04665 for (unsigned i = 0, e = From->getNumValues(); i != e; ++i) 04666 assert((!From->hasAnyUseOfValue(i) || 04667 From->getValueType(i) == To->getValueType(i)) && 04668 "Cannot use this version of ReplaceAllUsesWith!"); 04669 #endif 04670 04671 // Handle the trivial case. 04672 if (From == To) 04673 return; 04674 04675 // Iterate over just the existing users of From. See the comments in 04676 // the ReplaceAllUsesWith above. 04677 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); 04678 while (UI != UE) { 04679 SDNode *User = *UI; 04680 04681 // This node is about to morph, remove its old self from the CSE maps. 04682 RemoveNodeFromCSEMaps(User); 04683 04684 // A user can appear in a use list multiple times, and when this 04685 // happens the uses are usually next to each other in the list. 04686 // To help reduce the number of CSE recomputations, process all 04687 // the uses of this user that we can find this way. 04688 do { 04689 SDUse &Use = UI.getUse(); 04690 ++UI; 04691 Use.setNode(To); 04692 } while (UI != UE && *UI == User); 04693 04694 // Now that we have modified User, add it back to the CSE maps. If it 04695 // already exists there, recursively merge the results together. 04696 AddModifiedNodeToCSEMaps(User, UpdateListener); 04697 } 04698 } 04699 04700 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 04701 /// This can cause recursive merging of nodes in the DAG. 04702 /// 04703 /// This version can replace From with any result values. To must match the 04704 /// number and types of values returned by From. 04705 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, 04706 const SDValue *To, 04707 DAGUpdateListener *UpdateListener) { 04708 if (From->getNumValues() == 1) // Handle the simple case efficiently. 04709 return ReplaceAllUsesWith(SDValue(From, 0), To[0], UpdateListener); 04710 04711 // Iterate over just the existing users of From. See the comments in 04712 // the ReplaceAllUsesWith above. 04713 SDNode::use_iterator UI = From->use_begin(), UE = From->use_end(); 04714 while (UI != UE) { 04715 SDNode *User = *UI; 04716 04717 // This node is about to morph, remove its old self from the CSE maps. 04718 RemoveNodeFromCSEMaps(User); 04719 04720 // A user can appear in a use list multiple times, and when this 04721 // happens the uses are usually next to each other in the list. 04722 // To help reduce the number of CSE recomputations, process all 04723 // the uses of this user that we can find this way. 04724 do { 04725 SDUse &Use = UI.getUse(); 04726 const SDValue &ToOp = To[Use.getResNo()]; 04727 ++UI; 04728 Use.set(ToOp); 04729 } while (UI != UE && *UI == User); 04730 04731 // Now that we have modified User, add it back to the CSE maps. If it 04732 // already exists there, recursively merge the results together. 04733 AddModifiedNodeToCSEMaps(User, UpdateListener); 04734 } 04735 } 04736 04737 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 04738 /// uses of other values produced by From.getNode() alone. The Deleted 04739 /// vector is handled the same way as for ReplaceAllUsesWith. 04740 void SelectionDAG::ReplaceAllUsesOfValueWith(SDValue From, SDValue To, 04741 DAGUpdateListener *UpdateListener){ 04742 // Handle the really simple, really trivial case efficiently. 04743 if (From == To) return; 04744 04745 // Handle the simple, trivial, case efficiently. 04746 if (From.getNode()->getNumValues() == 1) { 04747 ReplaceAllUsesWith(From, To, UpdateListener); 04748 return; 04749 } 04750 04751 // Iterate over just the existing users of From. See the comments in 04752 // the ReplaceAllUsesWith above. 04753 SDNode::use_iterator UI = From.getNode()->use_begin(), 04754 UE = From.getNode()->use_end(); 04755 while (UI != UE) { 04756 SDNode *User = *UI; 04757 bool UserRemovedFromCSEMaps = false; 04758 04759 // A user can appear in a use list multiple times, and when this 04760 // happens the uses are usually next to each other in the list. 04761 // To help reduce the number of CSE recomputations, process all 04762 // the uses of this user that we can find this way. 04763 do { 04764 SDUse &Use = UI.getUse(); 04765 04766 // Skip uses of different values from the same node. 04767 if (Use.getResNo() != From.getResNo()) { 04768 ++UI; 04769 continue; 04770 } 04771 04772 // If this node hasn't been modified yet, it's still in the CSE maps, 04773 // so remove its old self from the CSE maps. 04774 if (!UserRemovedFromCSEMaps) { 04775 RemoveNodeFromCSEMaps(User); 04776 UserRemovedFromCSEMaps = true; 04777 } 04778 04779 ++UI; 04780 Use.set(To); 04781 } while (UI != UE && *UI == User); 04782 04783 // We are iterating over all uses of the From node, so if a use 04784 // doesn't use the specific value, no changes are made. 04785 if (!UserRemovedFromCSEMaps) 04786 continue; 04787 04788 // Now that we have modified User, add it back to the CSE maps. If it 04789 // already exists there, recursively merge the results together. 04790 AddModifiedNodeToCSEMaps(User, UpdateListener); 04791 } 04792 } 04793 04794 namespace { 04795 /// UseMemo - This class is used by SelectionDAG::ReplaceAllUsesOfValuesWith 04796 /// to record information about a use. 04797 struct UseMemo { 04798 SDNode *User; 04799 unsigned Index; 04800 SDUse *Use; 04801 }; 04802 04803 /// operator< - Sort Memos by User. 04804 bool operator<(const UseMemo &L, const UseMemo &R) { 04805 return (intptr_t)L.User < (intptr_t)R.User; 04806 } 04807 } 04808 04809 /// ReplaceAllUsesOfValuesWith - Replace any uses of From with To, leaving 04810 /// uses of other values produced by From.getNode() alone. The same value 04811 /// may appear in both the From and To list. The Deleted vector is 04812 /// handled the same way as for ReplaceAllUsesWith. 04813 void SelectionDAG::ReplaceAllUsesOfValuesWith(const SDValue *From, 04814 const SDValue *To, 04815 unsigned Num, 04816 DAGUpdateListener *UpdateListener){ 04817 // Handle the simple, trivial case efficiently. 04818 if (Num == 1) 04819 return ReplaceAllUsesOfValueWith(*From, *To, UpdateListener); 04820 04821 // Read up all the uses and make records of them. This helps 04822 // processing new uses that are introduced during the 04823 // replacement process. 04824 SmallVector<UseMemo, 4> Uses; 04825 for (unsigned i = 0; i != Num; ++i) { 04826 unsigned FromResNo = From[i].getResNo(); 04827 SDNode *FromNode = From[i].getNode(); 04828 for (SDNode::use_iterator UI = FromNode->use_begin(), 04829 E = FromNode->use_end(); UI != E; ++UI) { 04830 SDUse &Use = UI.getUse(); 04831 if (Use.getResNo() == FromResNo) { 04832 UseMemo Memo = { *UI, i, &Use }; 04833 Uses.push_back(Memo); 04834 } 04835 } 04836 } 04837 04838 // Sort the uses, so that all the uses from a given User are together. 04839 std::sort(Uses.begin(), Uses.end()); 04840 04841 for (unsigned UseIndex = 0, UseIndexEnd = Uses.size(); 04842 UseIndex != UseIndexEnd; ) { 04843 // We know that this user uses some value of From. If it is the right 04844 // value, update it. 04845 SDNode *User = Uses[UseIndex].User; 04846 04847 // This node is about to morph, remove its old self from the CSE maps. 04848 RemoveNodeFromCSEMaps(User); 04849 04850 // The Uses array is sorted, so all the uses for a given User 04851 // are next to each other in the list. 04852 // To help reduce the number of CSE recomputations, process all 04853 // the uses of this user that we can find this way. 04854 do { 04855 unsigned i = Uses[UseIndex].Index; 04856 SDUse &Use = *Uses[UseIndex].Use; 04857 ++UseIndex; 04858 04859 Use.set(To[i]); 04860 } while (UseIndex != UseIndexEnd && Uses[UseIndex].User == User); 04861 04862 // Now that we have modified User, add it back to the CSE maps. If it 04863 // already exists there, recursively merge the results together. 04864 AddModifiedNodeToCSEMaps(User, UpdateListener); 04865 } 04866 } 04867 04868 /// AssignTopologicalOrder - Assign a unique node id for each node in the DAG 04869 /// based on their topological order. It returns the maximum id and a vector 04870 /// of the SDNodes* in assigned order by reference. 04871 unsigned SelectionDAG::AssignTopologicalOrder() { 04872 04873 unsigned DAGSize = 0; 04874 04875 // SortedPos tracks the progress of the algorithm. Nodes before it are 04876 // sorted, nodes after it are unsorted. When the algorithm completes 04877 // it is at the end of the list. 04878 allnodes_iterator SortedPos = allnodes_begin(); 04879 04880 // Visit all the nodes. Move nodes with no operands to the front of 04881 // the list immediately. Annotate nodes that do have operands with their 04882 // operand count. Before we do this, the Node Id fields of the nodes 04883 // may contain arbitrary values. After, the Node Id fields for nodes 04884 // before SortedPos will contain the topological sort index, and the 04885 // Node Id fields for nodes At SortedPos and after will contain the 04886 // count of outstanding operands. 04887 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ) { 04888 SDNode *N = I++; 04889 unsigned Degree = N->getNumOperands(); 04890 if (Degree == 0) { 04891 // A node with no uses, add it to the result array immediately. 04892 N->setNodeId(DAGSize++); 04893 allnodes_iterator Q = N; 04894 if (Q != SortedPos) 04895 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(Q)); 04896 ++SortedPos; 04897 } else { 04898 // Temporarily use the Node Id as scratch space for the degree count. 04899 N->setNodeId(Degree); 04900 } 04901 } 04902 04903 // Visit all the nodes. As we iterate, moves nodes into sorted order, 04904 // such that by the time the end is reached all nodes will be sorted. 04905 for (allnodes_iterator I = allnodes_begin(),E = allnodes_end(); I != E; ++I) { 04906 SDNode *N = I; 04907 for (SDNode::use_iterator UI = N->use_begin(), UE = N->use_end(); 04908 UI != UE; ++UI) { 04909 SDNode *P = *UI; 04910 unsigned Degree = P->getNodeId(); 04911 --Degree; 04912 if (Degree == 0) { 04913 // All of P's operands are sorted, so P may sorted now. 04914 P->setNodeId(DAGSize++); 04915 if (P != SortedPos) 04916 SortedPos = AllNodes.insert(SortedPos, AllNodes.remove(P)); 04917 ++SortedPos; 04918 } else { 04919 // Update P's outstanding operand count. 04920 P->setNodeId(Degree); 04921 } 04922 } 04923 } 04924 04925 assert(SortedPos == AllNodes.end() && 04926 "Topological sort incomplete!"); 04927 assert(AllNodes.front().getOpcode() == ISD::EntryToken && 04928 "First node in topological sort is not the entry token!"); 04929 assert(AllNodes.front().getNodeId() == 0 && 04930 "First node in topological sort has non-zero id!"); 04931 assert(AllNodes.front().getNumOperands() == 0 && 04932 "First node in topological sort has operands!"); 04933 assert(AllNodes.back().getNodeId() == (int)DAGSize-1 && 04934 "Last node in topologic sort has unexpected id!"); 04935 assert(AllNodes.back().use_empty() && 04936 "Last node in topologic sort has users!"); 04937 assert(DAGSize == allnodes_size() && "Node count mismatch!"); 04938 return DAGSize; 04939 } 04940 04941 04942 04943 //===----------------------------------------------------------------------===// 04944 // SDNode Class 04945 //===----------------------------------------------------------------------===// 04946 04947 HandleSDNode::~HandleSDNode() { 04948 DropOperands(); 04949 } 04950 04951 GlobalAddressSDNode::GlobalAddressSDNode(unsigned Opc, const GlobalValue *GA, 04952 EVT VT, int64_t o, unsigned char TF) 04953 : SDNode(Opc, DebugLoc::getUnknownLoc(), getSDVTList(VT)), 04954 Offset(o), TargetFlags(TF) { 04955 TheGlobal = const_cast<GlobalValue*>(GA); 04956 } 04957 04958 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, EVT memvt, 04959 const Value *srcValue, int SVO, 04960 unsigned alignment, bool vol) 04961 : SDNode(Opc, dl, VTs), MemoryVT(memvt), SrcValue(srcValue), SVOffset(SVO) { 04962 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, vol, alignment); 04963 assert(isPowerOf2_32(alignment) && "Alignment is not a power of 2!"); 04964 assert(getAlignment() == alignment && "Alignment representation error!"); 04965 assert(isVolatile() == vol && "Volatile representation error!"); 04966 } 04967 04968 MemSDNode::MemSDNode(unsigned Opc, DebugLoc dl, SDVTList VTs, 04969 const SDValue *Ops, 04970 unsigned NumOps, EVT memvt, const Value *srcValue, 04971 int SVO, unsigned alignment, bool vol) 04972 : SDNode(Opc, dl, VTs, Ops, NumOps), 04973 MemoryVT(memvt), SrcValue(srcValue), SVOffset(SVO) { 04974 SubclassData = encodeMemSDNodeFlags(0, ISD::UNINDEXED, vol, alignment); 04975 assert(isPowerOf2_32(alignment) && "Alignment is not a power of 2!"); 04976 assert(getAlignment() == alignment && "Alignment representation error!"); 04977 assert(isVolatile() == vol && "Volatile representation error!"); 04978 } 04979 04980 /// getMemOperand - Return a MachineMemOperand object describing the memory 04981 /// reference performed by this memory reference. 04982 MachineMemOperand MemSDNode::getMemOperand() const { 04983 int Flags = 0; 04984 if (isa<LoadSDNode>(this)) 04985 Flags = MachineMemOperand::MOLoad; 04986 else if (isa<StoreSDNode>(this)) 04987 Flags = MachineMemOperand::MOStore; 04988 else if (isa<AtomicSDNode>(this)) { 04989 Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOStore; 04990 } 04991 else { 04992 const MemIntrinsicSDNode* MemIntrinNode = dyn_cast<MemIntrinsicSDNode>(this); 04993 assert(MemIntrinNode && "Unknown MemSDNode opcode!"); 04994 if (MemIntrinNode->readMem()) Flags |= MachineMemOperand::MOLoad; 04995 if (MemIntrinNode->writeMem()) Flags |= MachineMemOperand::MOStore; 04996 } 04997 04998 int Size = (getMemoryVT().getSizeInBits() + 7) >> 3; 04999 if (isVolatile()) Flags |= MachineMemOperand::MOVolatile; 05000 05001 // Check if the memory reference references a frame index 05002 const FrameIndexSDNode *FI = 05003 dyn_cast<const FrameIndexSDNode>(getBasePtr().getNode()); 05004 if (!getSrcValue() && FI) 05005 return MachineMemOperand(PseudoSourceValue::getFixedStack(FI->getIndex()), 05006 Flags, 0, Size, getAlignment()); 05007 else 05008 return MachineMemOperand(getSrcValue(), Flags, getSrcValueOffset(), 05009 Size, getAlignment()); 05010 } 05011 05012 /// Profile - Gather unique data for the node. 05013 /// 05014 void SDNode::Profile(FoldingSetNodeID &ID) const { 05015 AddNodeIDNode(ID, this); 05016 } 05017 05018 static ManagedStatic<std::set<EVT, EVT::compareRawBits> > EVTs; 05019 static EVT VTs[MVT::LAST_VALUETYPE]; 05020 static ManagedStatic<sys::SmartMutex<true> > VTMutex; 05021 05022 /// getValueTypeList - Return a pointer to the specified value type. 05023 /// 05024 const EVT *SDNode::getValueTypeList(EVT VT) { 05025 sys::SmartScopedLock<true> Lock(*VTMutex); 05026 if (VT.isExtended()) { 05027 return &(*EVTs->insert(VT).first); 05028 } else { 05029 VTs[VT.getSimpleVT().SimpleTy] = VT; 05030 return &VTs[VT.getSimpleVT().SimpleTy]; 05031 } 05032 } 05033 05034 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 05035 /// indicated value. This method ignores uses of other values defined by this 05036 /// operation. 05037 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { 05038 assert(Value < getNumValues() && "Bad value!"); 05039 05040 // TODO: Only iterate over uses of a given value of the node 05041 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) { 05042 if (UI.getUse().getResNo() == Value) { 05043 if (NUses == 0) 05044 return false; 05045 --NUses; 05046 } 05047 } 05048 05049 // Found exactly the right number of uses? 05050 return NUses == 0; 05051 } 05052 05053 05054 /// hasAnyUseOfValue - Return true if there are any use of the indicated 05055 /// value. This method ignores uses of other values defined by this operation. 05056 bool SDNode::hasAnyUseOfValue(unsigned Value) const { 05057 assert(Value < getNumValues() && "Bad value!"); 05058 05059 for (SDNode::use_iterator UI = use_begin(), E = use_end(); UI != E; ++UI) 05060 if (UI.getUse().getResNo() == Value) 05061 return true; 05062 05063 return false; 05064 } 05065 05066 05067 /// isOnlyUserOf - Return true if this node is the only use of N. 05068 /// 05069 bool SDNode::isOnlyUserOf(SDNode *N) const { 05070 bool Seen = false; 05071 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 05072 SDNode *User = *I; 05073 if (User == this) 05074 Seen = true; 05075 else 05076 return false; 05077 } 05078 05079 return Seen; 05080 } 05081 05082 /// isOperand - Return true if this node is an operand of N. 05083 /// 05084 bool SDValue::isOperandOf(SDNode *N) const { 05085 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 05086 if (*this == N->getOperand(i)) 05087 return true; 05088 return false; 05089 } 05090 05091 bool SDNode::isOperandOf(SDNode *N) const { 05092 for (unsigned i = 0, e = N->NumOperands; i != e; ++i) 05093 if (this == N->OperandList[i].getNode()) 05094 return true; 05095 return false; 05096 } 05097 05098 /// reachesChainWithoutSideEffects - Return true if this operand (which must 05099 /// be a chain) reaches the specified operand without crossing any 05100 /// side-effecting instructions. In practice, this looks through token 05101 /// factors and non-volatile loads. In order to remain efficient, this only 05102 /// looks a couple of nodes in, it does not do an exhaustive search. 05103 bool SDValue::reachesChainWithoutSideEffects(SDValue Dest, 05104 unsigned Depth) const { 05105 if (*this == Dest) return true; 05106 05107 // Don't search too deeply, we just want to be able to see through 05108 // TokenFactor's etc. 05109 if (Depth == 0) return false; 05110 05111 // If this is a token factor, all inputs to the TF happen in parallel. If any 05112 // of the operands of the TF reach dest, then we can do the xform. 05113 if (getOpcode() == ISD::TokenFactor) { 05114 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) 05115 if (getOperand(i).reachesChainWithoutSideEffects(Dest, Depth-1)) 05116 return true; 05117 return false; 05118 } 05119 05120 // Loads don't have side effects, look through them. 05121 if (LoadSDNode *Ld = dyn_cast<LoadSDNode>(*this)) { 05122 if (!Ld->isVolatile()) 05123 return Ld->getChain().reachesChainWithoutSideEffects(Dest, Depth-1); 05124 } 05125 return false; 05126 } 05127 05128 05129 static void findPredecessor(SDNode *N, const SDNode *P, bool &found, 05130 SmallPtrSet<SDNode *, 32> &Visited) { 05131 if (found || !Visited.insert(N)) 05132 return; 05133 05134 for (unsigned i = 0, e = N->getNumOperands(); !found && i != e; ++i) { 05135 SDNode *Op = N->getOperand(i).getNode(); 05136 if (Op == P) { 05137 found = true; 05138 return; 05139 } 05140 findPredecessor(Op, P, found, Visited); 05141 } 05142 } 05143 05144 /// isPredecessorOf - Return true if this node is a predecessor of N. This node 05145 /// is either an operand of N or it can be reached by recursively traversing 05146 /// up the operands. 05147 /// NOTE: this is an expensive method. Use it carefully. 05148 bool SDNode::isPredecessorOf(SDNode *N) const { 05149 SmallPtrSet<SDNode *, 32> Visited; 05150 bool found = false; 05151 findPredecessor(N, this, found, Visited); 05152 return found; 05153 } 05154 05155 uint64_t SDNode::getConstantOperandVal(unsigned Num) const { 05156 assert(Num < NumOperands && "Invalid child # of SDNode!"); 05157 return cast<ConstantSDNode>(OperandList[Num])->getZExtValue(); 05158 } 05159 05160 std::string SDNode::getOperationName(const SelectionDAG *G) const { 05161 switch (getOpcode()) { 05162 default: 05163 if (getOpcode() < ISD::BUILTIN_OP_END) 05164 return "<<Unknown DAG Node>>"; 05165 if (isMachineOpcode()) { 05166 if (G) 05167 if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo()) 05168 if (getMachineOpcode() < TII->getNumOpcodes()) 05169 return TII->get(getMachineOpcode()).getName(); 05170 return "<<Unknown Machine Node>>"; 05171 } 05172 if (G) { 05173 const TargetLowering &TLI = G->getTargetLoweringInfo(); 05174 const char *Name = TLI.getTargetNodeName(getOpcode()); 05175 if (Name) return Name; 05176 return "<<Unknown Target Node>>"; 05177 } 05178 return "<<Unknown Node>>"; 05179 05180 #ifndef NDEBUG 05181 case ISD::DELETED_NODE: 05182 return "<<Deleted Node!>>"; 05183 #endif 05184 case ISD::PREFETCH: return "Prefetch"; 05185 case ISD::MEMBARRIER: return "MemBarrier"; 05186 case ISD::ATOMIC_CMP_SWAP: return "AtomicCmpSwap"; 05187 case ISD::ATOMIC_SWAP: return "AtomicSwap"; 05188 case ISD::ATOMIC_LOAD_ADD: return "AtomicLoadAdd"; 05189 case ISD::ATOMIC_LOAD_SUB: return "AtomicLoadSub"; 05190 case ISD::ATOMIC_LOAD_AND: return "AtomicLoadAnd"; 05191 case ISD::ATOMIC_LOAD_OR: return "AtomicLoadOr"; 05192 case ISD::ATOMIC_LOAD_XOR: return "AtomicLoadXor"; 05193 case ISD::ATOMIC_LOAD_NAND: return "AtomicLoadNand"; 05194 case ISD::ATOMIC_LOAD_MIN: return "AtomicLoadMin"; 05195 case ISD::ATOMIC_LOAD_MAX: return "AtomicLoadMax"; 05196 case ISD::ATOMIC_LOAD_UMIN: return "AtomicLoadUMin"; 05197 case ISD::ATOMIC_LOAD_UMAX: return "AtomicLoadUMax"; 05198 case ISD::PCMARKER: return "PCMarker"; 05199 case ISD::READCYCLECOUNTER: return "ReadCycleCounter"; 05200 case ISD::SRCVALUE: return "SrcValue"; 05201 case ISD::MEMOPERAND: return "MemOperand"; 05202 case ISD::EntryToken: return "EntryToken"; 05203 case ISD::TokenFactor: return "TokenFactor"; 05204 case ISD::AssertSext: return "AssertSext"; 05205 case ISD::AssertZext: return "AssertZext"; 05206 05207 case ISD::BasicBlock: return "BasicBlock"; 05208 case ISD::VALUETYPE: return "ValueType"; 05209 case ISD::Register: return "Register"; 05210 05211 case ISD::Constant: return "Constant"; 05212 case ISD::ConstantFP: return "ConstantFP"; 05213 case ISD::GlobalAddress: return "GlobalAddress"; 05214 case ISD::GlobalTLSAddress: return "GlobalTLSAddress"; 05215 case ISD::FrameIndex: return "FrameIndex"; 05216 case ISD::JumpTable: return "JumpTable"; 05217 case ISD::GLOBAL_OFFSET_TABLE: return "GLOBAL_OFFSET_TABLE"; 05218 case ISD::RETURNADDR: return "RETURNADDR"; 05219 case ISD::FRAMEADDR: return "FRAMEADDR"; 05220 case ISD::FRAME_TO_ARGS_OFFSET: return "FRAME_TO_ARGS_OFFSET"; 05221 case ISD::EXCEPTIONADDR: return "EXCEPTIONADDR"; 05222 case ISD::LSDAADDR: return "LSDAADDR"; 05223 case ISD::EHSELECTION: return "EHSELECTION"; 05224 case ISD::EH_RETURN: return "EH_RETURN"; 05225 case ISD::ConstantPool: return "ConstantPool"; 05226 case ISD::ExternalSymbol: return "ExternalSymbol"; 05227 case ISD::INTRINSIC_WO_CHAIN: { 05228 unsigned IID = cast<ConstantSDNode>(getOperand(0))->getZExtValue(); 05229 return Intrinsic::getName((Intrinsic::ID)IID); 05230 } 05231 case ISD::INTRINSIC_VOID: 05232 case ISD::INTRINSIC_W_CHAIN: { 05233 unsigned IID = cast<ConstantSDNode>(getOperand(1))->getZExtValue(); 05234 return Intrinsic::getName((Intrinsic::ID)IID); 05235 } 05236 05237 case ISD::BUILD_VECTOR: return "BUILD_VECTOR"; 05238 case ISD::TargetConstant: return "TargetConstant"; 05239 case ISD::TargetConstantFP:return "TargetConstantFP"; 05240 case ISD::TargetGlobalAddress: return "TargetGlobalAddress"; 05241 case ISD::TargetGlobalTLSAddress: return "TargetGlobalTLSAddress"; 05242 case ISD::TargetFrameIndex: return "TargetFrameIndex"; 05243 case ISD::TargetJumpTable: return "TargetJumpTable"; 05244 case ISD::TargetConstantPool: return "TargetConstantPool"; 05245 case ISD::TargetExternalSymbol: return "TargetExternalSymbol"; 05246 05247 case ISD::CopyToReg: return "CopyToReg"; 05248 case ISD::CopyFromReg: return "CopyFromReg"; 05249 case ISD::UNDEF: return "undef"; 05250 case ISD::MERGE_VALUES: return "merge_values"; 05251 case ISD::INLINEASM: return "inlineasm"; 05252 case ISD::DBG_LABEL: return "dbg_label"; 05253 case ISD::EH_LABEL: return "eh_label"; 05254 case ISD::DECLARE: return "declare"; 05255 case ISD::HANDLENODE: return "handlenode"; 05256 05257 // Unary operators 05258 case ISD::FABS: return "fabs"; 05259 case ISD::FNEG: return "fneg"; 05260 case ISD::FSQRT: return "fsqrt"; 05261 case ISD::FSIN: return "fsin"; 05262 case ISD::FCOS: return "fcos"; 05263 case ISD::FPOWI: return "fpowi"; 05264 case ISD::FPOW: return "fpow"; 05265 case ISD::FTRUNC: return "ftrunc"; 05266 case ISD::FFLOOR: return "ffloor"; 05267 case ISD::FCEIL: return "fceil"; 05268 case ISD::FRINT: return "frint"; 05269 case ISD::FNEARBYINT: return "fnearbyint"; 05270 05271 // Binary operators 05272 case ISD::ADD: return "add"; 05273 case ISD::SUB: return "sub"; 05274 case ISD::MUL: return "mul"; 05275 case ISD::MULHU: return "mulhu"; 05276 case ISD::MULHS: return "mulhs"; 05277 case ISD::SDIV: return "sdiv"; 05278 case ISD::UDIV: return "udiv"; 05279 case ISD::SREM: return "srem"; 05280 case ISD::UREM: return "urem"; 05281 case ISD::SMUL_LOHI: return "smul_lohi"; 05282 case ISD::UMUL_LOHI: return "umul_lohi"; 05283 case ISD::SDIVREM: return "sdivrem"; 05284 case ISD::UDIVREM: return "udivrem"; 05285 case ISD::AND: return "and"; 05286 case ISD::OR: return "or"; 05287 case ISD::XOR: return "xor"; 05288 case ISD::SHL: return "shl"; 05289 case ISD::SRA: return "sra"; 05290 case ISD::SRL: return "srl"; 05291 case ISD::ROTL: return "rotl"; 05292 case ISD::ROTR: return "rotr"; 05293 case ISD::FADD: return "fadd"; 05294 case ISD::FSUB: return "fsub"; 05295 case ISD::FMUL: return "fmul"; 05296 case ISD::FDIV: return "fdiv"; 05297 case ISD::FREM: return "frem"; 05298 case ISD::FCOPYSIGN: return "fcopysign"; 05299 case ISD::FGETSIGN: return "fgetsign"; 05300 05301 case ISD::SETCC: return "setcc"; 05302 case ISD::VSETCC: return "vsetcc"; 05303 case ISD::SELECT: return "select"; 05304 case ISD::SELECT_CC: return "select_cc"; 05305 case ISD::INSERT_VECTOR_ELT: return "insert_vector_elt"; 05306 case ISD::EXTRACT_VECTOR_ELT: return "extract_vector_elt"; 05307 case ISD::CONCAT_VECTORS: return "concat_vectors"; 05308 case ISD::EXTRACT_SUBVECTOR: return "extract_subvector"; 05309 case ISD::SCALAR_TO_VECTOR: return "scalar_to_vector"; 05310 case ISD::VECTOR_SHUFFLE: return "vector_shuffle"; 05311 case ISD::CARRY_FALSE: return "carry_false"; 05312 case ISD::ADDC: return "addc"; 05313 case ISD::ADDE: return "adde"; 05314 case ISD::SADDO: return "saddo"; 05315 case ISD::UADDO: return "uaddo"; 05316 case ISD::SSUBO: return "ssubo"; 05317 case ISD::USUBO: return "usubo"; 05318 case ISD::SMULO: return "smulo"; 05319 case ISD::UMULO: return "umulo"; 05320 case ISD::SUBC: return "subc"; 05321 case ISD::SUBE: return "sube"; 05322 case ISD::SHL_PARTS: return "shl_parts"; 05323 case ISD::SRA_PARTS: return "sra_parts"; 05324 case ISD::SRL_PARTS: return "srl_parts"; 05325 05326 // Conversion operators. 05327 case ISD::SIGN_EXTEND: return "sign_extend"; 05328 case ISD::ZERO_EXTEND: return "zero_extend"; 05329 case ISD::ANY_EXTEND: return "any_extend"; 05330 case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg"; 05331 case ISD::TRUNCATE: return "truncate"; 05332 case ISD::FP_ROUND: return "fp_round"; 05333 case ISD::FLT_ROUNDS_: return "flt_rounds"; 05334 case ISD::FP_ROUND_INREG: return "fp_round_inreg"; 05335 case ISD::FP_EXTEND: return "fp_extend"; 05336 05337 case ISD::SINT_TO_FP: return "sint_to_fp"; 05338 case ISD::UINT_TO_FP: return "uint_to_fp"; 05339 case ISD::FP_TO_SINT: return "fp_to_sint"; 05340 case ISD::FP_TO_UINT: return "fp_to_uint"; 05341 case ISD::BIT_CONVERT: return "bit_convert"; 05342 05343 case ISD::CONVERT_RNDSAT: { 05344 switch (cast<CvtRndSatSDNode>(this)->getCvtCode()) { 05345 default: llvm_unreachable("Unknown cvt code!"); 05346 case ISD::CVT_FF: return "cvt_ff"; 05347 case ISD::CVT_FS: return "cvt_fs"; 05348 case ISD::CVT_FU: return "cvt_fu"; 05349 case ISD::CVT_SF: return "cvt_sf"; 05350 case ISD::CVT_UF: return "cvt_uf"; 05351 case ISD::CVT_SS: return "cvt_ss"; 05352 case ISD::CVT_SU: return "cvt_su"; 05353 case ISD::CVT_US: return "cvt_us"; 05354 case ISD::CVT_UU: return "cvt_uu"; 05355 } 05356 } 05357 05358 // Control flow instructions 05359 case ISD::BR: return "br"; 05360 case ISD::BRIND: return "brind"; 05361 case ISD::BR_JT: return "br_jt"; 05362 case ISD::BRCOND: return "brcond"; 05363 case ISD::BR_CC: return "br_cc"; 05364 case ISD::CALLSEQ_START: return "callseq_start"; 05365 case ISD::CALLSEQ_END: return "callseq_end"; 05366 05367 // Other operators 05368 case ISD::LOAD: return "load"; 05369 case ISD::STORE: return "store"; 05370 case ISD::VAARG: return "vaarg"; 05371 case ISD::VACOPY: return "vacopy"; 05372 case ISD::VAEND: return "vaend"; 05373 case ISD::VASTART: return "vastart"; 05374 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc"; 05375 case ISD::EXTRACT_ELEMENT: return "extract_element"; 05376 case ISD::BUILD_PAIR: return "build_pair"; 05377 case ISD::STACKSAVE: return "stacksave"; 05378 case ISD::STACKRESTORE: return "stackrestore"; 05379 case ISD::TRAP: return "trap"; 05380 05381 // Bit manipulation 05382 case ISD::BSWAP: return "bswap"; 05383 case ISD::CTPOP: return "ctpop"; 05384 case ISD::CTTZ: return "cttz"; 05385 case ISD::CTLZ: return "ctlz"; 05386 05387 // Debug info 05388 case ISD::DBG_STOPPOINT: return "dbg_stoppoint"; 05389 case ISD::DEBUG_LOC: return "debug_loc"; 05390 05391 // Trampolines 05392 case ISD::TRAMPOLINE: return "trampoline"; 05393 05394 case ISD::CONDCODE: 05395 switch (cast<CondCodeSDNode>(this)->get()) { 05396 default: llvm_unreachable("Unknown setcc condition!"); 05397 case ISD::SETOEQ: return "setoeq"; 05398 case ISD::SETOGT: return "setogt"; 05399 case ISD::SETOGE: return "setoge"; 05400 case ISD::SETOLT: return "setolt"; 05401 case ISD::SETOLE: return "setole"; 05402 case ISD::SETONE: return "setone"; 05403 05404 case ISD::SETO: return "seto"; 05405 case ISD::SETUO: return "setuo"; 05406 case ISD::SETUEQ: return "setue"; 05407 case ISD::SETUGT: return "setugt"; 05408 case ISD::SETUGE: return "setuge"; 05409 case ISD::SETULT: return "setult"; 05410 case ISD::SETULE: return "setule"; 05411 case ISD::SETUNE: return "setune"; 05412 05413 case ISD::SETEQ: return "seteq"; 05414 case ISD::SETGT: return "setgt"; 05415 case ISD::SETGE: return "setge"; 05416 case ISD::SETLT: return "setlt"; 05417 case ISD::SETLE: return "setle"; 05418 case ISD::SETNE: return "setne"; 05419 } 05420 } 05421 } 05422 05423 const char *SDNode::getIndexedModeName(ISD::MemIndexedMode AM) { 05424 switch (AM) { 05425 default: 05426 return ""; 05427 case ISD::PRE_INC: 05428 return "<pre-inc>"; 05429 case ISD::PRE_DEC: 05430 return "<pre-dec>"; 05431 case ISD::POST_INC: 05432 return "<post-inc>"; 05433 case ISD::POST_DEC: 05434 return "<post-dec>"; 05435 } 05436 } 05437 05438 std::string ISD::ArgFlagsTy::getArgFlagsString() { 05439 std::string S = "< "; 05440 05441 if (isZExt()) 05442 S += "zext "; 05443 if (isSExt()) 05444 S += "sext "; 05445 if (isInReg()) 05446 S += "inreg "; 05447 if (isSRet()) 05448 S += "sret "; 05449 if (isByVal()) 05450 S += "byval "; 05451 if (isNest()) 05452 S += "nest "; 05453 if (getByValAlign()) 05454 S += "byval-align:" + utostr(getByValAlign()) + " "; 05455 if (getOrigAlign()) 05456 S += "orig-align:" + utostr(getOrigAlign()) + " "; 05457 if (getByValSize()) 05458 S += "byval-size:" + utostr(getByValSize()) + " "; 05459 return S + ">"; 05460 } 05461 05462 void SDNode::dump() const { dump(0); } 05463 void SDNode::dump(const SelectionDAG *G) const { 05464 print(errs(), G); 05465 } 05466 05467 void SDNode::print_types(raw_ostream &OS, const SelectionDAG *G) const { 05468 OS << (void*)this << ": "; 05469 05470 for (unsigned i = 0, e = getNumValues(); i != e; ++i) { 05471 if (i) OS << ","; 05472 if (getValueType(i) == MVT::Other) 05473 OS << "ch"; 05474 else 05475 OS << getValueType(i).getEVTString(); 05476 } 05477 OS << " = " << getOperationName(G); 05478 } 05479 05480 void SDNode::print_details(raw_ostream &OS, const SelectionDAG *G) const { 05481 if (!isTargetOpcode() && getOpcode() == ISD::VECTOR_SHUFFLE) { 05482 const ShuffleVectorSDNode *SVN = cast<ShuffleVectorSDNode>(this); 05483 OS << "<"; 05484 for (unsigned i = 0, e = ValueList[0].getVectorNumElements(); i != e; ++i) { 05485 int Idx = SVN->getMaskElt(i); 05486 if (i) OS << ","; 05487 if (Idx < 0) 05488 OS << "u"; 05489 else 05490 OS << Idx; 05491 } 05492 OS << ">"; 05493 } 05494 05495 if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { 05496 OS << '<' << CSDN->getAPIntValue() << '>'; 05497 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { 05498 if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEsingle) 05499 OS << '<' << CSDN->getValueAPF().convertToFloat() << '>'; 05500 else if (&CSDN->getValueAPF().getSemantics()==&APFloat::IEEEdouble) 05501 OS << '<' << CSDN->getValueAPF().convertToDouble() << '>'; 05502 else { 05503 OS << "<APFloat("; 05504 CSDN->getValueAPF().bitcastToAPInt().dump(); 05505 OS << ")>"; 05506 } 05507 } else if (const GlobalAddressSDNode *GADN = 05508 dyn_cast<GlobalAddressSDNode>(this)) { 05509 int64_t offset = GADN->getOffset(); 05510 OS << '<'; 05511 WriteAsOperand(OS, GADN->getGlobal()); 05512 OS << '>'; 05513 if (offset > 0) 05514 OS << " + " << offset; 05515 else 05516 OS << " " << offset; 05517 if (unsigned int TF = GADN->getTargetFlags()) 05518 OS << " [TF=" << TF << ']'; 05519 } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) { 05520 OS << "<" << FIDN->getIndex() << ">"; 05521 } else if (const JumpTableSDNode *JTDN = dyn_cast<JumpTableSDNode>(this)) { 05522 OS << "<" << JTDN->getIndex() << ">"; 05523 if (unsigned int TF = JTDN->getTargetFlags()) 05524 OS << " [TF=" << TF << ']'; 05525 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ 05526 int offset = CP->getOffset(); 05527 if (CP->isMachineConstantPoolEntry()) 05528 OS << "<" << *CP->getMachineCPVal() << ">"; 05529 else 05530 OS << "<" << *CP->getConstVal() << ">"; 05531 if (offset > 0) 05532 OS << " + " << offset; 05533 else 05534 OS << " " << offset; 05535 if (unsigned int TF = CP->getTargetFlags()) 05536 OS << " [TF=" << TF << ']'; 05537 } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) { 05538 OS << "<"; 05539 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); 05540 if (LBB) 05541 OS << LBB->getName() << " "; 05542 OS << (const void*)BBDN->getBasicBlock() << ">"; 05543 } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) { 05544 if (G && R->getReg() && 05545 TargetRegisterInfo::isPhysicalRegister(R->getReg())) { 05546 OS << " " << G->getTarget().getRegisterInfo()->getName(R->getReg()); 05547 } else { 05548 OS << " #" << R->getReg(); 05549 } 05550 } else if (const ExternalSymbolSDNode *ES = 05551 dyn_cast<ExternalSymbolSDNode>(this)) { 05552 OS << "'" << ES->getSymbol() << "'"; 05553 if (unsigned int TF = ES->getTargetFlags()) 05554 OS << " [TF=" << TF << ']'; 05555 } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) { 05556 if (M->getValue()) 05557 OS << "<" << M->getValue() << ">"; 05558 else 05559 OS << "<null>"; 05560 } else if (const MemOperandSDNode *M = dyn_cast<MemOperandSDNode>(this)) { 05561 if (M->MO.getValue()) 05562 OS << "<" << M->MO.getValue() << ":" << M->MO.getOffset() << ">"; 05563 else 05564 OS << "<null:" << M->MO.getOffset() << ">"; 05565 } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) { 05566 OS << ":" << N->getVT().getEVTString(); 05567 } 05568 else if (const LoadSDNode *LD = dyn_cast<LoadSDNode>(this)) { 05569 const Value *SrcValue = LD->getSrcValue(); 05570 int SrcOffset = LD->getSrcValueOffset(); 05571 OS << " <"; 05572 if (SrcValue) 05573 OS << SrcValue; 05574 else 05575 OS << "null"; 05576 OS << ":" << SrcOffset << ">"; 05577 05578 bool doExt = true; 05579 switch (LD->getExtensionType()) { 05580 default: doExt = false; break; 05581 case ISD::EXTLOAD: OS << " <anyext "; break; 05582 case ISD::SEXTLOAD: OS << " <sext "; break; 05583 case ISD::ZEXTLOAD: OS << " <zext "; break; 05584 } 05585 if (doExt) 05586 OS << LD->getMemoryVT().getEVTString() << ">"; 05587 05588 const char *AM = getIndexedModeName(LD->getAddressingMode()); 05589 if (*AM) 05590 OS << " " << AM; 05591 if (LD->isVolatile()) 05592 OS << " <volatile>"; 05593 OS << " alignment=" << LD->getAlignment(); 05594 } else if (const StoreSDNode *ST = dyn_cast<StoreSDNode>(this)) { 05595 const Value *SrcValue = ST->getSrcValue(); 05596 int SrcOffset = ST->getSrcValueOffset(); 05597 OS << " <"; 05598 if (SrcValue) 05599 OS << SrcValue; 05600 else 05601 OS << "null"; 05602 OS << ":" << SrcOffset << ">"; 05603 05604 if (ST->isTruncatingStore()) 05605 OS << " <trunc " << ST->getMemoryVT().getEVTString() << ">"; 05606 05607 const char *AM = getIndexedModeName(ST->getAddressingMode()); 05608 if (*AM) 05609 OS << " " << AM; 05610 if (ST->isVolatile()) 05611 OS << " <volatile>"; 05612 OS << " alignment=" << ST->getAlignment(); 05613 } else if (const AtomicSDNode* AT = dyn_cast<AtomicSDNode>(this)) { 05614 const Value *SrcValue = AT->getSrcValue(); 05615 int SrcOffset = AT->getSrcValueOffset(); 05616 OS << " <"; 05617 if (SrcValue) 05618 OS << SrcValue; 05619 else 05620 OS << "null"; 05621 OS << ":" << SrcOffset << ">"; 05622 if (AT->isVolatile()) 05623 OS << " <volatile>"; 05624 OS << " alignment=" << AT->getAlignment(); 05625 } 05626 } 05627 05628 void SDNode::print(raw_ostream &OS, const SelectionDAG *G) const { 05629 print_types(OS, G); 05630 OS << " "; 05631 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 05632 if (i) OS << ", "; 05633 OS << (void*)getOperand(i).getNode(); 05634 if (unsigned RN = getOperand(i).getResNo()) 05635 OS << ":" << RN; 05636 } 05637 print_details(OS, G); 05638 } 05639 05640 static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { 05641 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 05642 if (N->getOperand(i).getNode()->hasOneUse()) 05643 DumpNodes(N->getOperand(i).getNode(), indent+2, G); 05644 else 05645 cerr << "\n" << std::string(indent+2, ' ') 05646 << (void*)N->getOperand(i).getNode() << ": <multiple use>"; 05647 05648 05649 cerr << "\n" << std::string(indent, ' '); 05650 N->dump(G); 05651 } 05652 05653 void SelectionDAG::dump() const { 05654 cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; 05655 05656 for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); 05657 I != E; ++I) { 05658 const SDNode *N = I; 05659 if (!N->hasOneUse() && N != getRoot().getNode()) 05660 DumpNodes(N, 2, this); 05661 } 05662 05663 if (getRoot().getNode()) DumpNodes(getRoot().getNode(), 2, this); 05664 05665 cerr << "\n\n"; 05666 } 05667 05668 void SDNode::printr(raw_ostream &OS, const SelectionDAG *G) const { 05669 print_types(OS, G); 05670 print_details(OS, G); 05671 } 05672 05673 typedef SmallPtrSet<const SDNode *, 128> VisitedSDNodeSet; 05674 static void DumpNodesr(raw_ostream &OS, const SDNode *N, unsigned indent, 05675 const SelectionDAG *G, VisitedSDNodeSet &once) { 05676 if (!once.insert(N)) // If we've been here before, return now. 05677 return; 05678 // Dump the current SDNode, but don't end the line yet. 05679 OS << std::string(indent, ' '); 05680 N->printr(OS, G); 05681 // Having printed this SDNode, walk the children: 05682 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 05683 const SDNode *child = N->getOperand(i).getNode(); 05684 if (i) OS << ","; 05685 OS << " "; 05686 if (child->getNumOperands() == 0) { 05687 // This child has no grandchildren; print it inline right here. 05688 child->printr(OS, G); 05689 once.insert(child); 05690 } else { // Just the address. FIXME: also print the child's opcode 05691 OS << (void*)child; 05692 if (unsigned RN = N->getOperand(i).getResNo()) 05693 OS << ":" << RN; 05694 } 05695 } 05696 OS << "\n"; 05697 // Dump children that have grandchildren on their own line(s). 05698 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 05699 const SDNode *child = N->getOperand(i).getNode(); 05700 DumpNodesr(OS, child, indent+2, G, once); 05701 } 05702 } 05703 05704 void SDNode::dumpr() const { 05705 VisitedSDNodeSet once; 05706 DumpNodesr(errs(), this, 0, 0, once); 05707 } 05708 05709 05710 // getAddressSpace - Return the address space this GlobalAddress belongs to. 05711 unsigned GlobalAddressSDNode::getAddressSpace() const { 05712 return getGlobal()->getType()->getAddressSpace(); 05713 } 05714 05715 05716 const Type *ConstantPoolSDNode::getType() const { 05717 if (isMachineConstantPoolEntry()) 05718 return Val.MachineCPVal->getType(); 05719 return Val.ConstVal->getType(); 05720 } 05721 05722 bool BuildVectorSDNode::isConstantSplat(APInt &SplatValue, 05723 APInt &SplatUndef, 05724 unsigned &SplatBitSize, 05725 bool &HasAnyUndefs, 05726 unsigned MinSplatBits) { 05727 EVT VT = getValueType(0); 05728 assert(VT.isVector() && "Expected a vector type"); 05729 unsigned sz = VT.getSizeInBits(); 05730 if (MinSplatBits > sz) 05731 return false; 05732 05733 SplatValue = APInt(sz, 0); 05734 SplatUndef = APInt(sz, 0); 05735 05736 // Get the bits. Bits with undefined values (when the corresponding element 05737 // of the vector is an ISD::UNDEF value) are set in SplatUndef and cleared 05738 // in SplatValue. If any of the values are not constant, give up and return 05739 // false. 05740 unsigned int nOps = getNumOperands(); 05741 assert(nOps > 0 && "isConstantSplat has 0-size build vector"); 05742 unsigned EltBitSize = VT.getVectorElementType().getSizeInBits(); 05743 for (unsigned i = 0; i < nOps; ++i) { 05744 SDValue OpVal = getOperand(i); 05745 unsigned BitPos = i * EltBitSize; 05746 05747 if (OpVal.getOpcode() == ISD::UNDEF) 05748 SplatUndef |= APInt::getBitsSet(sz, BitPos, BitPos +EltBitSize); 05749 else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(OpVal)) 05750 SplatValue |= (APInt(CN->getAPIntValue()).zextOrTrunc(EltBitSize). 05751 zextOrTrunc(sz) << BitPos); 05752 else if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(OpVal)) 05753 SplatValue |= CN->getValueAPF().bitcastToAPInt().zextOrTrunc(sz) <<BitPos; 05754 else 05755 return false; 05756 } 05757 05758 // The build_vector is all constants or undefs. Find the smallest element 05759 // size that splats the vector. 05760 05761 HasAnyUndefs = (SplatUndef != 0); 05762 while (sz > 8) { 05763 05764 unsigned HalfSize = sz / 2; 05765 APInt HighValue = APInt(SplatValue).lshr(HalfSize).trunc(HalfSize); 05766 APInt LowValue = APInt(SplatValue).trunc(HalfSize); 05767 APInt HighUndef = APInt(SplatUndef).lshr(HalfSize).trunc(HalfSize); 05768 APInt LowUndef = APInt(SplatUndef).trunc(HalfSize); 05769 05770 // If the two halves do not match (ignoring undef bits), stop here. 05771 if ((HighValue & ~LowUndef) != (LowValue & ~HighUndef) || 05772 MinSplatBits > HalfSize) 05773 break; 05774 05775 SplatValue = HighValue | LowValue; 05776 SplatUndef = HighUndef & LowUndef; 05777 05778 sz = HalfSize; 05779 } 05780 05781 SplatBitSize = sz; 05782 return true; 05783 } 05784 05785 bool ShuffleVectorSDNode::isSplatMask(const int *Mask, EVT VT) { 05786 // Find the first non-undef value in the shuffle mask. 05787 unsigned i, e; 05788 for (i = 0, e = VT.getVectorNumElements(); i != e && Mask[i] < 0; ++i) 05789 /* search */; 05790 05791 assert(i != e && "VECTOR_SHUFFLE node with all undef indices!"); 05792 05793 // Make sure all remaining elements are either undef or the same as the first 05794 // non-undef value. 05795 for (int Idx = Mask[i]; i != e; ++i) 05796 if (Mask[i] >= 0 && Mask[i] != Idx) 05797 return false; 05798 return true; 05799 }