LLVM API Documentation
00001 //===-- SelectionDAG.cpp - Implement the SelectionDAG data structures -----===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements the SelectionDAG class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/CodeGen/SelectionDAG.h" 00015 #include "llvm/Constants.h" 00016 #include "llvm/GlobalValue.h" 00017 #include "llvm/Intrinsics.h" 00018 #include "llvm/Assembly/Writer.h" 00019 #include "llvm/CodeGen/MachineBasicBlock.h" 00020 #include "llvm/Support/MathExtras.h" 00021 #include "llvm/Target/MRegisterInfo.h" 00022 #include "llvm/Target/TargetLowering.h" 00023 #include "llvm/Target/TargetInstrInfo.h" 00024 #include "llvm/Target/TargetMachine.h" 00025 #include "llvm/ADT/SetVector.h" 00026 #include "llvm/ADT/StringExtras.h" 00027 #include <iostream> 00028 #include <set> 00029 #include <cmath> 00030 #include <algorithm> 00031 using namespace llvm; 00032 00033 static bool isCommutativeBinOp(unsigned Opcode) { 00034 switch (Opcode) { 00035 case ISD::ADD: 00036 case ISD::MUL: 00037 case ISD::MULHU: 00038 case ISD::MULHS: 00039 case ISD::FADD: 00040 case ISD::FMUL: 00041 case ISD::AND: 00042 case ISD::OR: 00043 case ISD::XOR: return true; 00044 default: return false; // FIXME: Need commutative info for user ops! 00045 } 00046 } 00047 00048 // isInvertibleForFree - Return true if there is no cost to emitting the logical 00049 // inverse of this node. 00050 static bool isInvertibleForFree(SDOperand N) { 00051 if (isa<ConstantSDNode>(N.Val)) return true; 00052 if (N.Val->getOpcode() == ISD::SETCC && N.Val->hasOneUse()) 00053 return true; 00054 return false; 00055 } 00056 00057 //===----------------------------------------------------------------------===// 00058 // ConstantFPSDNode Class 00059 //===----------------------------------------------------------------------===// 00060 00061 /// isExactlyValue - We don't rely on operator== working on double values, as 00062 /// it returns true for things that are clearly not equal, like -0.0 and 0.0. 00063 /// As such, this method can be used to do an exact bit-for-bit comparison of 00064 /// two floating point values. 00065 bool ConstantFPSDNode::isExactlyValue(double V) const { 00066 return DoubleToBits(V) == DoubleToBits(Value); 00067 } 00068 00069 //===----------------------------------------------------------------------===// 00070 // ISD Namespace 00071 //===----------------------------------------------------------------------===// 00072 00073 /// isBuildVectorAllOnes - Return true if the specified node is a 00074 /// BUILD_VECTOR where all of the elements are ~0 or undef. 00075 bool ISD::isBuildVectorAllOnes(const SDNode *N) { 00076 // Look through a bit convert. 00077 if (N->getOpcode() == ISD::BIT_CONVERT) 00078 N = N->getOperand(0).Val; 00079 00080 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 00081 00082 unsigned i = 0, e = N->getNumOperands(); 00083 00084 // Skip over all of the undef values. 00085 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 00086 ++i; 00087 00088 // Do not accept an all-undef vector. 00089 if (i == e) return false; 00090 00091 // Do not accept build_vectors that aren't all constants or which have non-~0 00092 // elements. 00093 SDOperand NotZero = N->getOperand(i); 00094 if (isa<ConstantSDNode>(NotZero)) { 00095 if (!cast<ConstantSDNode>(NotZero)->isAllOnesValue()) 00096 return false; 00097 } else if (isa<ConstantFPSDNode>(NotZero)) { 00098 MVT::ValueType VT = NotZero.getValueType(); 00099 if (VT== MVT::f64) { 00100 if (DoubleToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) != 00101 (uint64_t)-1) 00102 return false; 00103 } else { 00104 if (FloatToBits(cast<ConstantFPSDNode>(NotZero)->getValue()) != 00105 (uint32_t)-1) 00106 return false; 00107 } 00108 } else 00109 return false; 00110 00111 // Okay, we have at least one ~0 value, check to see if the rest match or are 00112 // undefs. 00113 for (++i; i != e; ++i) 00114 if (N->getOperand(i) != NotZero && 00115 N->getOperand(i).getOpcode() != ISD::UNDEF) 00116 return false; 00117 return true; 00118 } 00119 00120 00121 /// isBuildVectorAllZeros - Return true if the specified node is a 00122 /// BUILD_VECTOR where all of the elements are 0 or undef. 00123 bool ISD::isBuildVectorAllZeros(const SDNode *N) { 00124 // Look through a bit convert. 00125 if (N->getOpcode() == ISD::BIT_CONVERT) 00126 N = N->getOperand(0).Val; 00127 00128 if (N->getOpcode() != ISD::BUILD_VECTOR) return false; 00129 00130 unsigned i = 0, e = N->getNumOperands(); 00131 00132 // Skip over all of the undef values. 00133 while (i != e && N->getOperand(i).getOpcode() == ISD::UNDEF) 00134 ++i; 00135 00136 // Do not accept an all-undef vector. 00137 if (i == e) return false; 00138 00139 // Do not accept build_vectors that aren't all constants or which have non-~0 00140 // elements. 00141 SDOperand Zero = N->getOperand(i); 00142 if (isa<ConstantSDNode>(Zero)) { 00143 if (!cast<ConstantSDNode>(Zero)->isNullValue()) 00144 return false; 00145 } else if (isa<ConstantFPSDNode>(Zero)) { 00146 if (!cast<ConstantFPSDNode>(Zero)->isExactlyValue(0.0)) 00147 return false; 00148 } else 00149 return false; 00150 00151 // Okay, we have at least one ~0 value, check to see if the rest match or are 00152 // undefs. 00153 for (++i; i != e; ++i) 00154 if (N->getOperand(i) != Zero && 00155 N->getOperand(i).getOpcode() != ISD::UNDEF) 00156 return false; 00157 return true; 00158 } 00159 00160 /// getSetCCSwappedOperands - Return the operation corresponding to (Y op X) 00161 /// when given the operation for (X op Y). 00162 ISD::CondCode ISD::getSetCCSwappedOperands(ISD::CondCode Operation) { 00163 // To perform this operation, we just need to swap the L and G bits of the 00164 // operation. 00165 unsigned OldL = (Operation >> 2) & 1; 00166 unsigned OldG = (Operation >> 1) & 1; 00167 return ISD::CondCode((Operation & ~6) | // Keep the N, U, E bits 00168 (OldL << 1) | // New G bit 00169 (OldG << 2)); // New L bit. 00170 } 00171 00172 /// getSetCCInverse - Return the operation corresponding to !(X op Y), where 00173 /// 'op' is a valid SetCC operation. 00174 ISD::CondCode ISD::getSetCCInverse(ISD::CondCode Op, bool isInteger) { 00175 unsigned Operation = Op; 00176 if (isInteger) 00177 Operation ^= 7; // Flip L, G, E bits, but not U. 00178 else 00179 Operation ^= 15; // Flip all of the condition bits. 00180 if (Operation > ISD::SETTRUE2) 00181 Operation &= ~8; // Don't let N and U bits get set. 00182 return ISD::CondCode(Operation); 00183 } 00184 00185 00186 /// isSignedOp - For an integer comparison, return 1 if the comparison is a 00187 /// signed operation and 2 if the result is an unsigned comparison. Return zero 00188 /// if the operation does not depend on the sign of the input (setne and seteq). 00189 static int isSignedOp(ISD::CondCode Opcode) { 00190 switch (Opcode) { 00191 default: assert(0 && "Illegal integer setcc operation!"); 00192 case ISD::SETEQ: 00193 case ISD::SETNE: return 0; 00194 case ISD::SETLT: 00195 case ISD::SETLE: 00196 case ISD::SETGT: 00197 case ISD::SETGE: return 1; 00198 case ISD::SETULT: 00199 case ISD::SETULE: 00200 case ISD::SETUGT: 00201 case ISD::SETUGE: return 2; 00202 } 00203 } 00204 00205 /// getSetCCOrOperation - Return the result of a logical OR between different 00206 /// comparisons of identical values: ((X op1 Y) | (X op2 Y)). This function 00207 /// returns SETCC_INVALID if it is not possible to represent the resultant 00208 /// comparison. 00209 ISD::CondCode ISD::getSetCCOrOperation(ISD::CondCode Op1, ISD::CondCode Op2, 00210 bool isInteger) { 00211 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 00212 // Cannot fold a signed integer setcc with an unsigned integer setcc. 00213 return ISD::SETCC_INVALID; 00214 00215 unsigned Op = Op1 | Op2; // Combine all of the condition bits. 00216 00217 // If the N and U bits get set then the resultant comparison DOES suddenly 00218 // care about orderedness, and is true when ordered. 00219 if (Op > ISD::SETTRUE2) 00220 Op &= ~16; // Clear the U bit if the N bit is set. 00221 00222 // Canonicalize illegal integer setcc's. 00223 if (isInteger && Op == ISD::SETUNE) // e.g. SETUGT | SETULT 00224 Op = ISD::SETNE; 00225 00226 return ISD::CondCode(Op); 00227 } 00228 00229 /// getSetCCAndOperation - Return the result of a logical AND between different 00230 /// comparisons of identical values: ((X op1 Y) & (X op2 Y)). This 00231 /// function returns zero if it is not possible to represent the resultant 00232 /// comparison. 00233 ISD::CondCode ISD::getSetCCAndOperation(ISD::CondCode Op1, ISD::CondCode Op2, 00234 bool isInteger) { 00235 if (isInteger && (isSignedOp(Op1) | isSignedOp(Op2)) == 3) 00236 // Cannot fold a signed setcc with an unsigned setcc. 00237 return ISD::SETCC_INVALID; 00238 00239 // Combine all of the condition bits. 00240 ISD::CondCode Result = ISD::CondCode(Op1 & Op2); 00241 00242 // Canonicalize illegal integer setcc's. 00243 if (isInteger) { 00244 switch (Result) { 00245 default: break; 00246 case ISD::SETUO : Result = ISD::SETFALSE; break; // SETUGT & SETULT 00247 case ISD::SETUEQ: Result = ISD::SETEQ ; break; // SETUGE & SETULE 00248 case ISD::SETOLT: Result = ISD::SETULT ; break; // SETULT & SETNE 00249 case ISD::SETOGT: Result = ISD::SETUGT ; break; // SETUGT & SETNE 00250 } 00251 } 00252 00253 return Result; 00254 } 00255 00256 const TargetMachine &SelectionDAG::getTarget() const { 00257 return TLI.getTargetMachine(); 00258 } 00259 00260 //===----------------------------------------------------------------------===// 00261 // SelectionDAG Class 00262 //===----------------------------------------------------------------------===// 00263 00264 /// RemoveDeadNodes - This method deletes all unreachable nodes in the 00265 /// SelectionDAG, including nodes (like loads) that have uses of their token 00266 /// chain but no other uses and no side effect. If a node is passed in as an 00267 /// argument, it is used as the seed for node deletion. 00268 void SelectionDAG::RemoveDeadNodes(SDNode *N) { 00269 // Create a dummy node (which is not added to allnodes), that adds a reference 00270 // to the root node, preventing it from being deleted. 00271 HandleSDNode Dummy(getRoot()); 00272 00273 bool MadeChange = false; 00274 00275 // If we have a hint to start from, use it. 00276 if (N && N->use_empty()) { 00277 DestroyDeadNode(N); 00278 MadeChange = true; 00279 } 00280 00281 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ++I) 00282 if (I->use_empty() && I->getOpcode() != 65535) { 00283 // Node is dead, recursively delete newly dead uses. 00284 DestroyDeadNode(I); 00285 MadeChange = true; 00286 } 00287 00288 // Walk the nodes list, removing the nodes we've marked as dead. 00289 if (MadeChange) { 00290 for (allnodes_iterator I = allnodes_begin(), E = allnodes_end(); I != E; ) { 00291 SDNode *N = I++; 00292 if (N->use_empty()) 00293 AllNodes.erase(N); 00294 } 00295 } 00296 00297 // If the root changed (e.g. it was a dead load, update the root). 00298 setRoot(Dummy.getValue()); 00299 } 00300 00301 /// DestroyDeadNode - We know that N is dead. Nuke it from the CSE maps for the 00302 /// graph. If it is the last user of any of its operands, recursively process 00303 /// them the same way. 00304 /// 00305 void SelectionDAG::DestroyDeadNode(SDNode *N) { 00306 // Okay, we really are going to delete this node. First take this out of the 00307 // appropriate CSE map. 00308 RemoveNodeFromCSEMaps(N); 00309 00310 // Next, brutally remove the operand list. This is safe to do, as there are 00311 // no cycles in the graph. 00312 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) { 00313 SDNode *O = I->Val; 00314 O->removeUser(N); 00315 00316 // Now that we removed this operand, see if there are no uses of it left. 00317 if (O->use_empty()) 00318 DestroyDeadNode(O); 00319 } 00320 delete[] N->OperandList; 00321 N->OperandList = 0; 00322 N->NumOperands = 0; 00323 00324 // Mark the node as dead. 00325 N->MorphNodeTo(65535); 00326 } 00327 00328 void SelectionDAG::DeleteNode(SDNode *N) { 00329 assert(N->use_empty() && "Cannot delete a node that is not dead!"); 00330 00331 // First take this out of the appropriate CSE map. 00332 RemoveNodeFromCSEMaps(N); 00333 00334 // Finally, remove uses due to operands of this node, remove from the 00335 // AllNodes list, and delete the node. 00336 DeleteNodeNotInCSEMaps(N); 00337 } 00338 00339 void SelectionDAG::DeleteNodeNotInCSEMaps(SDNode *N) { 00340 00341 // Remove it from the AllNodes list. 00342 AllNodes.remove(N); 00343 00344 // Drop all of the operands and decrement used nodes use counts. 00345 for (SDNode::op_iterator I = N->op_begin(), E = N->op_end(); I != E; ++I) 00346 I->Val->removeUser(N); 00347 delete[] N->OperandList; 00348 N->OperandList = 0; 00349 N->NumOperands = 0; 00350 00351 delete N; 00352 } 00353 00354 /// RemoveNodeFromCSEMaps - Take the specified node out of the CSE map that 00355 /// correspond to it. This is useful when we're about to delete or repurpose 00356 /// the node. We don't want future request for structurally identical nodes 00357 /// to return N anymore. 00358 void SelectionDAG::RemoveNodeFromCSEMaps(SDNode *N) { 00359 bool Erased = false; 00360 switch (N->getOpcode()) { 00361 case ISD::HANDLENODE: return; // noop. 00362 case ISD::Constant: 00363 Erased = Constants.erase(std::make_pair(cast<ConstantSDNode>(N)->getValue(), 00364 N->getValueType(0))); 00365 break; 00366 case ISD::TargetConstant: 00367 Erased = TargetConstants.erase(std::make_pair( 00368 cast<ConstantSDNode>(N)->getValue(), 00369 N->getValueType(0))); 00370 break; 00371 case ISD::ConstantFP: { 00372 uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue()); 00373 Erased = ConstantFPs.erase(std::make_pair(V, N->getValueType(0))); 00374 break; 00375 } 00376 case ISD::TargetConstantFP: { 00377 uint64_t V = DoubleToBits(cast<ConstantFPSDNode>(N)->getValue()); 00378 Erased = TargetConstantFPs.erase(std::make_pair(V, N->getValueType(0))); 00379 break; 00380 } 00381 case ISD::STRING: 00382 Erased = StringNodes.erase(cast<StringSDNode>(N)->getValue()); 00383 break; 00384 case ISD::CONDCODE: 00385 assert(CondCodeNodes[cast<CondCodeSDNode>(N)->get()] && 00386 "Cond code doesn't exist!"); 00387 Erased = CondCodeNodes[cast<CondCodeSDNode>(N)->get()] != 0; 00388 CondCodeNodes[cast<CondCodeSDNode>(N)->get()] = 0; 00389 break; 00390 case ISD::GlobalAddress: { 00391 GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N); 00392 Erased = GlobalValues.erase(std::make_pair(GN->getGlobal(), 00393 GN->getOffset())); 00394 break; 00395 } 00396 case ISD::TargetGlobalAddress: { 00397 GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(N); 00398 Erased =TargetGlobalValues.erase(std::make_pair(GN->getGlobal(), 00399 GN->getOffset())); 00400 break; 00401 } 00402 case ISD::FrameIndex: 00403 Erased = FrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex()); 00404 break; 00405 case ISD::TargetFrameIndex: 00406 Erased = TargetFrameIndices.erase(cast<FrameIndexSDNode>(N)->getIndex()); 00407 break; 00408 case ISD::JumpTable: 00409 Erased = JumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex()); 00410 break; 00411 case ISD::TargetJumpTable: 00412 Erased = 00413 TargetJumpTableIndices.erase(cast<JumpTableSDNode>(N)->getIndex()); 00414 break; 00415 case ISD::ConstantPool: 00416 Erased = ConstantPoolIndices. 00417 erase(std::make_pair(cast<ConstantPoolSDNode>(N)->get(), 00418 std::make_pair(cast<ConstantPoolSDNode>(N)->getOffset(), 00419 cast<ConstantPoolSDNode>(N)->getAlignment()))); 00420 break; 00421 case ISD::TargetConstantPool: 00422 Erased = TargetConstantPoolIndices. 00423 erase(std::make_pair(cast<ConstantPoolSDNode>(N)->get(), 00424 std::make_pair(cast<ConstantPoolSDNode>(N)->getOffset(), 00425 cast<ConstantPoolSDNode>(N)->getAlignment()))); 00426 break; 00427 case ISD::BasicBlock: 00428 Erased = BBNodes.erase(cast<BasicBlockSDNode>(N)->getBasicBlock()); 00429 break; 00430 case ISD::ExternalSymbol: 00431 Erased = ExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 00432 break; 00433 case ISD::TargetExternalSymbol: 00434 Erased = 00435 TargetExternalSymbols.erase(cast<ExternalSymbolSDNode>(N)->getSymbol()); 00436 break; 00437 case ISD::VALUETYPE: 00438 Erased = ValueTypeNodes[cast<VTSDNode>(N)->getVT()] != 0; 00439 ValueTypeNodes[cast<VTSDNode>(N)->getVT()] = 0; 00440 break; 00441 case ISD::Register: 00442 Erased = RegNodes.erase(std::make_pair(cast<RegisterSDNode>(N)->getReg(), 00443 N->getValueType(0))); 00444 break; 00445 case ISD::SRCVALUE: { 00446 SrcValueSDNode *SVN = cast<SrcValueSDNode>(N); 00447 Erased =ValueNodes.erase(std::make_pair(SVN->getValue(), SVN->getOffset())); 00448 break; 00449 } 00450 case ISD::LOAD: 00451 Erased = Loads.erase(std::make_pair(N->getOperand(1), 00452 std::make_pair(N->getOperand(0), 00453 N->getValueType(0)))); 00454 break; 00455 default: 00456 if (N->getNumValues() == 1) { 00457 if (N->getNumOperands() == 0) { 00458 Erased = NullaryOps.erase(std::make_pair(N->getOpcode(), 00459 N->getValueType(0))); 00460 } else if (N->getNumOperands() == 1) { 00461 Erased = 00462 UnaryOps.erase(std::make_pair(N->getOpcode(), 00463 std::make_pair(N->getOperand(0), 00464 N->getValueType(0)))); 00465 } else if (N->getNumOperands() == 2) { 00466 Erased = 00467 BinaryOps.erase(std::make_pair(N->getOpcode(), 00468 std::make_pair(N->getOperand(0), 00469 N->getOperand(1)))); 00470 } else { 00471 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 00472 Erased = 00473 OneResultNodes.erase(std::make_pair(N->getOpcode(), 00474 std::make_pair(N->getValueType(0), 00475 Ops))); 00476 } 00477 } else { 00478 // Remove the node from the ArbitraryNodes map. 00479 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 00480 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 00481 Erased = 00482 ArbitraryNodes.erase(std::make_pair(N->getOpcode(), 00483 std::make_pair(RV, Ops))); 00484 } 00485 break; 00486 } 00487 #ifndef NDEBUG 00488 // Verify that the node was actually in one of the CSE maps, unless it has a 00489 // flag result (which cannot be CSE'd) or is one of the special cases that are 00490 // not subject to CSE. 00491 if (!Erased && N->getValueType(N->getNumValues()-1) != MVT::Flag && 00492 !N->isTargetOpcode()) { 00493 N->dump(); 00494 assert(0 && "Node is not in map!"); 00495 } 00496 #endif 00497 } 00498 00499 /// AddNonLeafNodeToCSEMaps - Add the specified node back to the CSE maps. It 00500 /// has been taken out and modified in some way. If the specified node already 00501 /// exists in the CSE maps, do not modify the maps, but return the existing node 00502 /// instead. If it doesn't exist, add it and return null. 00503 /// 00504 SDNode *SelectionDAG::AddNonLeafNodeToCSEMaps(SDNode *N) { 00505 assert(N->getNumOperands() && "This is a leaf node!"); 00506 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 00507 return 0; // Never add these nodes. 00508 00509 // Check that remaining values produced are not flags. 00510 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 00511 if (N->getValueType(i) == MVT::Flag) 00512 return 0; // Never CSE anything that produces a flag. 00513 00514 if (N->getNumValues() == 1) { 00515 if (N->getNumOperands() == 1) { 00516 SDNode *&U = UnaryOps[std::make_pair(N->getOpcode(), 00517 std::make_pair(N->getOperand(0), 00518 N->getValueType(0)))]; 00519 if (U) return U; 00520 U = N; 00521 } else if (N->getNumOperands() == 2) { 00522 SDNode *&B = BinaryOps[std::make_pair(N->getOpcode(), 00523 std::make_pair(N->getOperand(0), 00524 N->getOperand(1)))]; 00525 if (B) return B; 00526 B = N; 00527 } else { 00528 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 00529 SDNode *&ORN = OneResultNodes[std::make_pair(N->getOpcode(), 00530 std::make_pair(N->getValueType(0), Ops))]; 00531 if (ORN) return ORN; 00532 ORN = N; 00533 } 00534 } else { 00535 if (N->getOpcode() == ISD::LOAD) { 00536 SDNode *&L = Loads[std::make_pair(N->getOperand(1), 00537 std::make_pair(N->getOperand(0), 00538 N->getValueType(0)))]; 00539 if (L) return L; 00540 L = N; 00541 } else { 00542 // Remove the node from the ArbitraryNodes map. 00543 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 00544 std::vector<SDOperand> Ops(N->op_begin(), N->op_end()); 00545 SDNode *&AN = ArbitraryNodes[std::make_pair(N->getOpcode(), 00546 std::make_pair(RV, Ops))]; 00547 if (AN) return AN; 00548 AN = N; 00549 } 00550 } 00551 return 0; 00552 } 00553 00554 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands 00555 /// were replaced with those specified. If this node is never memoized, 00556 /// return null, otherwise return a pointer to the slot it would take. If a 00557 /// node already exists with these operands, the slot will be non-null. 00558 SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, SDOperand Op) { 00559 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 00560 return 0; // Never add these nodes. 00561 00562 // Check that remaining values produced are not flags. 00563 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 00564 if (N->getValueType(i) == MVT::Flag) 00565 return 0; // Never CSE anything that produces a flag. 00566 00567 if (N->getNumValues() == 1) { 00568 return &UnaryOps[std::make_pair(N->getOpcode(), 00569 std::make_pair(Op, N->getValueType(0)))]; 00570 } else { 00571 // Remove the node from the ArbitraryNodes map. 00572 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 00573 std::vector<SDOperand> Ops; 00574 Ops.push_back(Op); 00575 return &ArbitraryNodes[std::make_pair(N->getOpcode(), 00576 std::make_pair(RV, Ops))]; 00577 } 00578 return 0; 00579 } 00580 00581 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands 00582 /// were replaced with those specified. If this node is never memoized, 00583 /// return null, otherwise return a pointer to the slot it would take. If a 00584 /// node already exists with these operands, the slot will be non-null. 00585 SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, 00586 SDOperand Op1, SDOperand Op2) { 00587 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 00588 return 0; // Never add these nodes. 00589 00590 // Check that remaining values produced are not flags. 00591 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 00592 if (N->getValueType(i) == MVT::Flag) 00593 return 0; // Never CSE anything that produces a flag. 00594 00595 if (N->getNumValues() == 1) { 00596 return &BinaryOps[std::make_pair(N->getOpcode(), 00597 std::make_pair(Op1, Op2))]; 00598 } else { 00599 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 00600 std::vector<SDOperand> Ops; 00601 Ops.push_back(Op1); 00602 Ops.push_back(Op2); 00603 return &ArbitraryNodes[std::make_pair(N->getOpcode(), 00604 std::make_pair(RV, Ops))]; 00605 } 00606 return 0; 00607 } 00608 00609 00610 /// FindModifiedNodeSlot - Find a slot for the specified node if its operands 00611 /// were replaced with those specified. If this node is never memoized, 00612 /// return null, otherwise return a pointer to the slot it would take. If a 00613 /// node already exists with these operands, the slot will be non-null. 00614 SDNode **SelectionDAG::FindModifiedNodeSlot(SDNode *N, 00615 const std::vector<SDOperand> &Ops) { 00616 if (N->getOpcode() == ISD::HANDLENODE || N->getValueType(0) == MVT::Flag) 00617 return 0; // Never add these nodes. 00618 00619 // Check that remaining values produced are not flags. 00620 for (unsigned i = 1, e = N->getNumValues(); i != e; ++i) 00621 if (N->getValueType(i) == MVT::Flag) 00622 return 0; // Never CSE anything that produces a flag. 00623 00624 if (N->getNumValues() == 1) { 00625 if (N->getNumOperands() == 1) { 00626 return &UnaryOps[std::make_pair(N->getOpcode(), 00627 std::make_pair(Ops[0], 00628 N->getValueType(0)))]; 00629 } else if (N->getNumOperands() == 2) { 00630 return &BinaryOps[std::make_pair(N->getOpcode(), 00631 std::make_pair(Ops[0], Ops[1]))]; 00632 } else { 00633 return &OneResultNodes[std::make_pair(N->getOpcode(), 00634 std::make_pair(N->getValueType(0), 00635 Ops))]; 00636 } 00637 } else { 00638 if (N->getOpcode() == ISD::LOAD) { 00639 return &Loads[std::make_pair(Ops[1], 00640 std::make_pair(Ops[0], N->getValueType(0)))]; 00641 } else { 00642 std::vector<MVT::ValueType> RV(N->value_begin(), N->value_end()); 00643 return &ArbitraryNodes[std::make_pair(N->getOpcode(), 00644 std::make_pair(RV, Ops))]; 00645 } 00646 } 00647 return 0; 00648 } 00649 00650 00651 SelectionDAG::~SelectionDAG() { 00652 while (!AllNodes.empty()) { 00653 SDNode *N = AllNodes.begin(); 00654 delete [] N->OperandList; 00655 N->OperandList = 0; 00656 N->NumOperands = 0; 00657 AllNodes.pop_front(); 00658 } 00659 } 00660 00661 SDOperand SelectionDAG::getZeroExtendInReg(SDOperand Op, MVT::ValueType VT) { 00662 if (Op.getValueType() == VT) return Op; 00663 int64_t Imm = ~0ULL >> (64-MVT::getSizeInBits(VT)); 00664 return getNode(ISD::AND, Op.getValueType(), Op, 00665 getConstant(Imm, Op.getValueType())); 00666 } 00667 00668 SDOperand SelectionDAG::getConstant(uint64_t Val, MVT::ValueType VT) { 00669 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 00670 assert(!MVT::isVector(VT) && "Cannot create Vector ConstantSDNodes!"); 00671 00672 // Mask out any bits that are not valid for this constant. 00673 if (VT != MVT::i64) 00674 Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; 00675 00676 SDNode *&N = Constants[std::make_pair(Val, VT)]; 00677 if (N) return SDOperand(N, 0); 00678 N = new ConstantSDNode(false, Val, VT); 00679 AllNodes.push_back(N); 00680 return SDOperand(N, 0); 00681 } 00682 00683 SDOperand SelectionDAG::getString(const std::string &Val) { 00684 StringSDNode *&N = StringNodes[Val]; 00685 if (!N) { 00686 N = new StringSDNode(Val); 00687 AllNodes.push_back(N); 00688 } 00689 return SDOperand(N, 0); 00690 } 00691 00692 SDOperand SelectionDAG::getTargetConstant(uint64_t Val, MVT::ValueType VT) { 00693 assert(MVT::isInteger(VT) && "Cannot create FP integer constant!"); 00694 // Mask out any bits that are not valid for this constant. 00695 if (VT != MVT::i64) 00696 Val &= ((uint64_t)1 << MVT::getSizeInBits(VT)) - 1; 00697 00698 SDNode *&N = TargetConstants[std::make_pair(Val, VT)]; 00699 if (N) return SDOperand(N, 0); 00700 N = new ConstantSDNode(true, Val, VT); 00701 AllNodes.push_back(N); 00702 return SDOperand(N, 0); 00703 } 00704 00705 SDOperand SelectionDAG::getConstantFP(double Val, MVT::ValueType VT) { 00706 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 00707 if (VT == MVT::f32) 00708 Val = (float)Val; // Mask out extra precision. 00709 00710 // Do the map lookup using the actual bit pattern for the floating point 00711 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 00712 // we don't have issues with SNANs. 00713 SDNode *&N = ConstantFPs[std::make_pair(DoubleToBits(Val), VT)]; 00714 if (N) return SDOperand(N, 0); 00715 N = new ConstantFPSDNode(false, Val, VT); 00716 AllNodes.push_back(N); 00717 return SDOperand(N, 0); 00718 } 00719 00720 SDOperand SelectionDAG::getTargetConstantFP(double Val, MVT::ValueType VT) { 00721 assert(MVT::isFloatingPoint(VT) && "Cannot create integer FP constant!"); 00722 if (VT == MVT::f32) 00723 Val = (float)Val; // Mask out extra precision. 00724 00725 // Do the map lookup using the actual bit pattern for the floating point 00726 // value, so that we don't have problems with 0.0 comparing equal to -0.0, and 00727 // we don't have issues with SNANs. 00728 SDNode *&N = TargetConstantFPs[std::make_pair(DoubleToBits(Val), VT)]; 00729 if (N) return SDOperand(N, 0); 00730 N = new ConstantFPSDNode(true, Val, VT); 00731 AllNodes.push_back(N); 00732 return SDOperand(N, 0); 00733 } 00734 00735 SDOperand SelectionDAG::getGlobalAddress(const GlobalValue *GV, 00736 MVT::ValueType VT, int offset) { 00737 SDNode *&N = GlobalValues[std::make_pair(GV, offset)]; 00738 if (N) return SDOperand(N, 0); 00739 N = new GlobalAddressSDNode(false, GV, VT, offset); 00740 AllNodes.push_back(N); 00741 return SDOperand(N, 0); 00742 } 00743 00744 SDOperand SelectionDAG::getTargetGlobalAddress(const GlobalValue *GV, 00745 MVT::ValueType VT, int offset) { 00746 SDNode *&N = TargetGlobalValues[std::make_pair(GV, offset)]; 00747 if (N) return SDOperand(N, 0); 00748 N = new GlobalAddressSDNode(true, GV, VT, offset); 00749 AllNodes.push_back(N); 00750 return SDOperand(N, 0); 00751 } 00752 00753 SDOperand SelectionDAG::getFrameIndex(int FI, MVT::ValueType VT) { 00754 SDNode *&N = FrameIndices[FI]; 00755 if (N) return SDOperand(N, 0); 00756 N = new FrameIndexSDNode(FI, VT, false); 00757 AllNodes.push_back(N); 00758 return SDOperand(N, 0); 00759 } 00760 00761 SDOperand SelectionDAG::getTargetFrameIndex(int FI, MVT::ValueType VT) { 00762 SDNode *&N = TargetFrameIndices[FI]; 00763 if (N) return SDOperand(N, 0); 00764 N = new FrameIndexSDNode(FI, VT, true); 00765 AllNodes.push_back(N); 00766 return SDOperand(N, 0); 00767 } 00768 00769 SDOperand SelectionDAG::getJumpTable(int JTI, MVT::ValueType VT) { 00770 SDNode *&N = JumpTableIndices[JTI]; 00771 if (N) return SDOperand(N, 0); 00772 N = new JumpTableSDNode(JTI, VT, false); 00773 AllNodes.push_back(N); 00774 return SDOperand(N, 0); 00775 } 00776 00777 SDOperand SelectionDAG::getTargetJumpTable(int JTI, MVT::ValueType VT) { 00778 SDNode *&N = TargetJumpTableIndices[JTI]; 00779 if (N) return SDOperand(N, 0); 00780 N = new JumpTableSDNode(JTI, VT, true); 00781 AllNodes.push_back(N); 00782 return SDOperand(N, 0); 00783 } 00784 00785 SDOperand SelectionDAG::getConstantPool(Constant *C, MVT::ValueType VT, 00786 unsigned Alignment, int Offset) { 00787 SDNode *&N = ConstantPoolIndices[std::make_pair(C, 00788 std::make_pair(Offset, Alignment))]; 00789 if (N) return SDOperand(N, 0); 00790 N = new ConstantPoolSDNode(false, C, VT, Offset, Alignment); 00791 AllNodes.push_back(N); 00792 return SDOperand(N, 0); 00793 } 00794 00795 SDOperand SelectionDAG::getTargetConstantPool(Constant *C, MVT::ValueType VT, 00796 unsigned Alignment, int Offset) { 00797 SDNode *&N = TargetConstantPoolIndices[std::make_pair(C, 00798 std::make_pair(Offset, Alignment))]; 00799 if (N) return SDOperand(N, 0); 00800 N = new ConstantPoolSDNode(true, C, VT, Offset, Alignment); 00801 AllNodes.push_back(N); 00802 return SDOperand(N, 0); 00803 } 00804 00805 SDOperand SelectionDAG::getBasicBlock(MachineBasicBlock *MBB) { 00806 SDNode *&N = BBNodes[MBB]; 00807 if (N) return SDOperand(N, 0); 00808 N = new BasicBlockSDNode(MBB); 00809 AllNodes.push_back(N); 00810 return SDOperand(N, 0); 00811 } 00812 00813 SDOperand SelectionDAG::getValueType(MVT::ValueType VT) { 00814 if ((unsigned)VT >= ValueTypeNodes.size()) 00815 ValueTypeNodes.resize(VT+1); 00816 if (ValueTypeNodes[VT] == 0) { 00817 ValueTypeNodes[VT] = new VTSDNode(VT); 00818 AllNodes.push_back(ValueTypeNodes[VT]); 00819 } 00820 00821 return SDOperand(ValueTypeNodes[VT], 0); 00822 } 00823 00824 SDOperand SelectionDAG::getExternalSymbol(const char *Sym, MVT::ValueType VT) { 00825 SDNode *&N = ExternalSymbols[Sym]; 00826 if (N) return SDOperand(N, 0); 00827 N = new ExternalSymbolSDNode(false, Sym, VT); 00828 AllNodes.push_back(N); 00829 return SDOperand(N, 0); 00830 } 00831 00832 SDOperand SelectionDAG::getTargetExternalSymbol(const char *Sym, 00833 MVT::ValueType VT) { 00834 SDNode *&N = TargetExternalSymbols[Sym]; 00835 if (N) return SDOperand(N, 0); 00836 N = new ExternalSymbolSDNode(true, Sym, VT); 00837 AllNodes.push_back(N); 00838 return SDOperand(N, 0); 00839 } 00840 00841 SDOperand SelectionDAG::getCondCode(ISD::CondCode Cond) { 00842 if ((unsigned)Cond >= CondCodeNodes.size()) 00843 CondCodeNodes.resize(Cond+1); 00844 00845 if (CondCodeNodes[Cond] == 0) { 00846 CondCodeNodes[Cond] = new CondCodeSDNode(Cond); 00847 AllNodes.push_back(CondCodeNodes[Cond]); 00848 } 00849 return SDOperand(CondCodeNodes[Cond], 0); 00850 } 00851 00852 SDOperand SelectionDAG::getRegister(unsigned RegNo, MVT::ValueType VT) { 00853 RegisterSDNode *&Reg = RegNodes[std::make_pair(RegNo, VT)]; 00854 if (!Reg) { 00855 Reg = new RegisterSDNode(RegNo, VT); 00856 AllNodes.push_back(Reg); 00857 } 00858 return SDOperand(Reg, 0); 00859 } 00860 00861 SDOperand SelectionDAG::SimplifySetCC(MVT::ValueType VT, SDOperand N1, 00862 SDOperand N2, ISD::CondCode Cond) { 00863 // These setcc operations always fold. 00864 switch (Cond) { 00865 default: break; 00866 case ISD::SETFALSE: 00867 case ISD::SETFALSE2: return getConstant(0, VT); 00868 case ISD::SETTRUE: 00869 case ISD::SETTRUE2: return getConstant(1, VT); 00870 00871 case ISD::SETOEQ: 00872 case ISD::SETOGT: 00873 case ISD::SETOGE: 00874 case ISD::SETOLT: 00875 case ISD::SETOLE: 00876 case ISD::SETONE: 00877 case ISD::SETO: 00878 case ISD::SETUO: 00879 case ISD::SETUEQ: 00880 case ISD::SETUNE: 00881 assert(!MVT::isInteger(N1.getValueType()) && "Illegal setcc for integer!"); 00882 break; 00883 } 00884 00885 if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val)) { 00886 uint64_t C2 = N2C->getValue(); 00887 if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val)) { 00888 uint64_t C1 = N1C->getValue(); 00889 00890 // Sign extend the operands if required 00891 if (ISD::isSignedIntSetCC(Cond)) { 00892 C1 = N1C->getSignExtended(); 00893 C2 = N2C->getSignExtended(); 00894 } 00895 00896 switch (Cond) { 00897 default: assert(0 && "Unknown integer setcc!"); 00898 case ISD::SETEQ: return getConstant(C1 == C2, VT); 00899 case ISD::SETNE: return getConstant(C1 != C2, VT); 00900 case ISD::SETULT: return getConstant(C1 < C2, VT); 00901 case ISD::SETUGT: return getConstant(C1 > C2, VT); 00902 case ISD::SETULE: return getConstant(C1 <= C2, VT); 00903 case ISD::SETUGE: return getConstant(C1 >= C2, VT); 00904 case ISD::SETLT: return getConstant((int64_t)C1 < (int64_t)C2, VT); 00905 case ISD::SETGT: return getConstant((int64_t)C1 > (int64_t)C2, VT); 00906 case ISD::SETLE: return getConstant((int64_t)C1 <= (int64_t)C2, VT); 00907 case ISD::SETGE: return getConstant((int64_t)C1 >= (int64_t)C2, VT); 00908 } 00909 } else { 00910 // If the LHS is a ZERO_EXTEND, perform the comparison on the input. 00911 if (N1.getOpcode() == ISD::ZERO_EXTEND) { 00912 unsigned InSize = MVT::getSizeInBits(N1.getOperand(0).getValueType()); 00913 00914 // If the comparison constant has bits in the upper part, the 00915 // zero-extended value could never match. 00916 if (C2 & (~0ULL << InSize)) { 00917 unsigned VSize = MVT::getSizeInBits(N1.getValueType()); 00918 switch (Cond) { 00919 case ISD::SETUGT: 00920 case ISD::SETUGE: 00921 case ISD::SETEQ: return getConstant(0, VT); 00922 case ISD::SETULT: 00923 case ISD::SETULE: 00924 case ISD::SETNE: return getConstant(1, VT); 00925 case ISD::SETGT: 00926 case ISD::SETGE: 00927 // True if the sign bit of C2 is set. 00928 return getConstant((C2 & (1ULL << VSize)) != 0, VT); 00929 case ISD::SETLT: 00930 case ISD::SETLE: 00931 // True if the sign bit of C2 isn't set. 00932 return getConstant((C2 & (1ULL << VSize)) == 0, VT); 00933 default: 00934 break; 00935 } 00936 } 00937 00938 // Otherwise, we can perform the comparison with the low bits. 00939 switch (Cond) { 00940 case ISD::SETEQ: 00941 case ISD::SETNE: 00942 case ISD::SETUGT: 00943 case ISD::SETUGE: 00944 case ISD::SETULT: 00945 case ISD::SETULE: 00946 return getSetCC(VT, N1.getOperand(0), 00947 getConstant(C2, N1.getOperand(0).getValueType()), 00948 Cond); 00949 default: 00950 break; // todo, be more careful with signed comparisons 00951 } 00952 } else if (N1.getOpcode() == ISD::SIGN_EXTEND_INREG && 00953 (Cond == ISD::SETEQ || Cond == ISD::SETNE)) { 00954 MVT::ValueType ExtSrcTy = cast<VTSDNode>(N1.getOperand(1))->getVT(); 00955 unsigned ExtSrcTyBits = MVT::getSizeInBits(ExtSrcTy); 00956 MVT::ValueType ExtDstTy = N1.getValueType(); 00957 unsigned ExtDstTyBits = MVT::getSizeInBits(ExtDstTy); 00958 00959 // If the extended part has any inconsistent bits, it cannot ever 00960 // compare equal. In other words, they have to be all ones or all 00961 // zeros. 00962 uint64_t ExtBits = 00963 (~0ULL >> (64-ExtSrcTyBits)) & (~0ULL << (ExtDstTyBits-1)); 00964 if ((C2 & ExtBits) != 0 && (C2 & ExtBits) != ExtBits) 00965 return getConstant(Cond == ISD::SETNE, VT); 00966 00967 // Otherwise, make this a use of a zext. 00968 return getSetCC(VT, getZeroExtendInReg(N1.getOperand(0), ExtSrcTy), 00969 getConstant(C2 & (~0ULL>>(64-ExtSrcTyBits)), ExtDstTy), 00970 Cond); 00971 } 00972 00973 uint64_t MinVal, MaxVal; 00974 unsigned OperandBitSize = MVT::getSizeInBits(N2C->getValueType(0)); 00975 if (ISD::isSignedIntSetCC(Cond)) { 00976 MinVal = 1ULL << (OperandBitSize-1); 00977 if (OperandBitSize != 1) // Avoid X >> 64, which is undefined. 00978 MaxVal = ~0ULL >> (65-OperandBitSize); 00979 else 00980 MaxVal = 0; 00981 } else { 00982 MinVal = 0; 00983 MaxVal = ~0ULL >> (64-OperandBitSize); 00984 } 00985 00986 // Canonicalize GE/LE comparisons to use GT/LT comparisons. 00987 if (Cond == ISD::SETGE || Cond == ISD::SETUGE) { 00988 if (C2 == MinVal) return getConstant(1, VT); // X >= MIN --> true 00989 --C2; // X >= C1 --> X > (C1-1) 00990 return getSetCC(VT, N1, getConstant(C2, N2.getValueType()), 00991 (Cond == ISD::SETGE) ? ISD::SETGT : ISD::SETUGT); 00992 } 00993 00994 if (Cond == ISD::SETLE || Cond == ISD::SETULE) { 00995 if (C2 == MaxVal) return getConstant(1, VT); // X <= MAX --> true 00996 ++C2; // X <= C1 --> X < (C1+1) 00997 return getSetCC(VT, N1, getConstant(C2, N2.getValueType()), 00998 (Cond == ISD::SETLE) ? ISD::SETLT : ISD::SETULT); 00999 } 01000 01001 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal) 01002 return getConstant(0, VT); // X < MIN --> false 01003 01004 // Canonicalize setgt X, Min --> setne X, Min 01005 if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MinVal) 01006 return getSetCC(VT, N1, N2, ISD::SETNE); 01007 01008 // If we have setult X, 1, turn it into seteq X, 0 01009 if ((Cond == ISD::SETLT || Cond == ISD::SETULT) && C2 == MinVal+1) 01010 return getSetCC(VT, N1, getConstant(MinVal, N1.getValueType()), 01011 ISD::SETEQ); 01012 // If we have setugt X, Max-1, turn it into seteq X, Max 01013 else if ((Cond == ISD::SETGT || Cond == ISD::SETUGT) && C2 == MaxVal-1) 01014 return getSetCC(VT, N1, getConstant(MaxVal, N1.getValueType()), 01015 ISD::SETEQ); 01016 01017 // If we have "setcc X, C1", check to see if we can shrink the immediate 01018 // by changing cc. 01019 01020 // SETUGT X, SINTMAX -> SETLT X, 0 01021 if (Cond == ISD::SETUGT && OperandBitSize != 1 && 01022 C2 == (~0ULL >> (65-OperandBitSize))) 01023 return getSetCC(VT, N1, getConstant(0, N2.getValueType()), ISD::SETLT); 01024 01025 // FIXME: Implement the rest of these. 01026 01027 01028 // Fold bit comparisons when we can. 01029 if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) && 01030 VT == N1.getValueType() && N1.getOpcode() == ISD::AND) 01031 if (ConstantSDNode *AndRHS = 01032 dyn_cast<ConstantSDNode>(N1.getOperand(1))) { 01033 if (Cond == ISD::SETNE && C2 == 0) {// (X & 8) != 0 --> (X & 8) >> 3 01034 // Perform the xform if the AND RHS is a single bit. 01035 if ((AndRHS->getValue() & (AndRHS->getValue()-1)) == 0) { 01036 return getNode(ISD::SRL, VT, N1, 01037 getConstant(Log2_64(AndRHS->getValue()), 01038 TLI.getShiftAmountTy())); 01039 } 01040 } else if (Cond == ISD::SETEQ && C2 == AndRHS->getValue()) { 01041 // (X & 8) == 8 --> (X & 8) >> 3 01042 // Perform the xform if C2 is a single bit. 01043 if ((C2 & (C2-1)) == 0) { 01044 return getNode(ISD::SRL, VT, N1, 01045 getConstant(Log2_64(C2),TLI.getShiftAmountTy())); 01046 } 01047 } 01048 } 01049 } 01050 } else if (isa<ConstantSDNode>(N1.Val)) { 01051 // Ensure that the constant occurs on the RHS. 01052 return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 01053 } 01054 01055 if (ConstantFPSDNode *N1C = dyn_cast<ConstantFPSDNode>(N1.Val)) 01056 if (ConstantFPSDNode *N2C = dyn_cast<ConstantFPSDNode>(N2.Val)) { 01057 double C1 = N1C->getValue(), C2 = N2C->getValue(); 01058 01059 switch (Cond) { 01060 default: break; // FIXME: Implement the rest of these! 01061 case ISD::SETEQ: return getConstant(C1 == C2, VT); 01062 case ISD::SETNE: return getConstant(C1 != C2, VT); 01063 case ISD::SETLT: return getConstant(C1 < C2, VT); 01064 case ISD::SETGT: return getConstant(C1 > C2, VT); 01065 case ISD::SETLE: return getConstant(C1 <= C2, VT); 01066 case ISD::SETGE: return getConstant(C1 >= C2, VT); 01067 } 01068 } else { 01069 // Ensure that the constant occurs on the RHS. 01070 return getSetCC(VT, N2, N1, ISD::getSetCCSwappedOperands(Cond)); 01071 } 01072 01073 // Could not fold it. 01074 return SDOperand(); 01075 } 01076 01077 /// getNode - Gets or creates the specified node. 01078 /// 01079 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT) { 01080 SDNode *&N = NullaryOps[std::make_pair(Opcode, VT)]; 01081 if (!N) { 01082 N = new SDNode(Opcode, VT); 01083 AllNodes.push_back(N); 01084 } 01085 return SDOperand(N, 0); 01086 } 01087 01088 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 01089 SDOperand Operand) { 01090 unsigned Tmp1; 01091 // Constant fold unary operations with an integer constant operand. 01092 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Operand.Val)) { 01093 uint64_t Val = C->getValue(); 01094 switch (Opcode) { 01095 default: break; 01096 case ISD::SIGN_EXTEND: return getConstant(C->getSignExtended(), VT); 01097 case ISD::ANY_EXTEND: 01098 case ISD::ZERO_EXTEND: return getConstant(Val, VT); 01099 case ISD::TRUNCATE: return getConstant(Val, VT); 01100 case ISD::SINT_TO_FP: return getConstantFP(C->getSignExtended(), VT); 01101 case ISD::UINT_TO_FP: return getConstantFP(C->getValue(), VT); 01102 case ISD::BIT_CONVERT: 01103 if (VT == MVT::f32 && C->getValueType(0) == MVT::i32) 01104 return getConstantFP(BitsToFloat(Val), VT); 01105 else if (VT == MVT::f64 && C->getValueType(0) == MVT::i64) 01106 return getConstantFP(BitsToDouble(Val), VT); 01107 break; 01108 case ISD::BSWAP: 01109 switch(VT) { 01110 default: assert(0 && "Invalid bswap!"); break; 01111 case MVT::i16: return getConstant(ByteSwap_16((unsigned short)Val), VT); 01112 case MVT::i32: return getConstant(ByteSwap_32((unsigned)Val), VT); 01113 case MVT::i64: return getConstant(ByteSwap_64(Val), VT); 01114 } 01115 break; 01116 case ISD::CTPOP: 01117 switch(VT) { 01118 default: assert(0 && "Invalid ctpop!"); break; 01119 case MVT::i1: return getConstant(Val != 0, VT); 01120 case MVT::i8: 01121 Tmp1 = (unsigned)Val & 0xFF; 01122 return getConstant(CountPopulation_32(Tmp1), VT); 01123 case MVT::i16: 01124 Tmp1 = (unsigned)Val & 0xFFFF; 01125 return getConstant(CountPopulation_32(Tmp1), VT); 01126 case MVT::i32: 01127 return getConstant(CountPopulation_32((unsigned)Val), VT); 01128 case MVT::i64: 01129 return getConstant(CountPopulation_64(Val), VT); 01130 } 01131 case ISD::CTLZ: 01132 switch(VT) { 01133 default: assert(0 && "Invalid ctlz!"); break; 01134 case MVT::i1: return getConstant(Val == 0, VT); 01135 case MVT::i8: 01136 Tmp1 = (unsigned)Val & 0xFF; 01137 return getConstant(CountLeadingZeros_32(Tmp1)-24, VT); 01138 case MVT::i16: 01139 Tmp1 = (unsigned)Val & 0xFFFF; 01140 return getConstant(CountLeadingZeros_32(Tmp1)-16, VT); 01141 case MVT::i32: 01142 return getConstant(CountLeadingZeros_32((unsigned)Val), VT); 01143 case MVT::i64: 01144 return getConstant(CountLeadingZeros_64(Val), VT); 01145 } 01146 case ISD::CTTZ: 01147 switch(VT) { 01148 default: assert(0 && "Invalid cttz!"); break; 01149 case MVT::i1: return getConstant(Val == 0, VT); 01150 case MVT::i8: 01151 Tmp1 = (unsigned)Val | 0x100; 01152 return getConstant(CountTrailingZeros_32(Tmp1), VT); 01153 case MVT::i16: 01154 Tmp1 = (unsigned)Val | 0x10000; 01155 return getConstant(CountTrailingZeros_32(Tmp1), VT); 01156 case MVT::i32: 01157 return getConstant(CountTrailingZeros_32((unsigned)Val), VT); 01158 case MVT::i64: 01159 return getConstant(CountTrailingZeros_64(Val), VT); 01160 } 01161 } 01162 } 01163 01164 // Constant fold unary operations with an floating point constant operand. 01165 if (ConstantFPSDNode *C = dyn_cast<ConstantFPSDNode>(Operand.Val)) 01166 switch (Opcode) { 01167 case ISD::FNEG: 01168 return getConstantFP(-C->getValue(), VT); 01169 case ISD::FABS: 01170 return getConstantFP(fabs(C->getValue()), VT); 01171 case ISD::FP_ROUND: 01172 case ISD::FP_EXTEND: 01173 return getConstantFP(C->getValue(), VT); 01174 case ISD::FP_TO_SINT: 01175 return getConstant((int64_t)C->getValue(), VT); 01176 case ISD::FP_TO_UINT: 01177 return getConstant((uint64_t)C->getValue(), VT); 01178 case ISD::BIT_CONVERT: 01179 if (VT == MVT::i32 && C->getValueType(0) == MVT::f32) 01180 return getConstant(FloatToBits(C->getValue()), VT); 01181 else if (VT == MVT::i64 && C->getValueType(0) == MVT::f64) 01182 return getConstant(DoubleToBits(C->getValue()), VT); 01183 break; 01184 } 01185 01186 unsigned OpOpcode = Operand.Val->getOpcode(); 01187 switch (Opcode) { 01188 case ISD::TokenFactor: 01189 return Operand; // Factor of one node? No factor. 01190 case ISD::SIGN_EXTEND: 01191 if (Operand.getValueType() == VT) return Operand; // noop extension 01192 assert(Operand.getValueType() < VT && "Invalid sext node, dst < src!"); 01193 if (OpOpcode == ISD::SIGN_EXTEND || OpOpcode == ISD::ZERO_EXTEND) 01194 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 01195 break; 01196 case ISD::ZERO_EXTEND: 01197 if (Operand.getValueType() == VT) return Operand; // noop extension 01198 assert(Operand.getValueType() < VT && "Invalid zext node, dst < src!"); 01199 if (OpOpcode == ISD::ZERO_EXTEND) // (zext (zext x)) -> (zext x) 01200 return getNode(ISD::ZERO_EXTEND, VT, Operand.Val->getOperand(0)); 01201 break; 01202 case ISD::ANY_EXTEND: 01203 if (Operand.getValueType() == VT) return Operand; // noop extension 01204 assert(Operand.getValueType() < VT && "Invalid anyext node, dst < src!"); 01205 if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND) 01206 // (ext (zext x)) -> (zext x) and (ext (sext x)) -> (sext x) 01207 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 01208 break; 01209 case ISD::TRUNCATE: 01210 if (Operand.getValueType() == VT) return Operand; // noop truncate 01211 assert(Operand.getValueType() > VT && "Invalid truncate node, src < dst!"); 01212 if (OpOpcode == ISD::TRUNCATE) 01213 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 01214 else if (OpOpcode == ISD::ZERO_EXTEND || OpOpcode == ISD::SIGN_EXTEND || 01215 OpOpcode == ISD::ANY_EXTEND) { 01216 // If the source is smaller than the dest, we still need an extend. 01217 if (Operand.Val->getOperand(0).getValueType() < VT) 01218 return getNode(OpOpcode, VT, Operand.Val->getOperand(0)); 01219 else if (Operand.Val->getOperand(0).getValueType() > VT) 01220 return getNode(ISD::TRUNCATE, VT, Operand.Val->getOperand(0)); 01221 else 01222 return Operand.Val->getOperand(0); 01223 } 01224 break; 01225 case ISD::BIT_CONVERT: 01226 // Basic sanity checking. 01227 assert(MVT::getSizeInBits(VT) == MVT::getSizeInBits(Operand.getValueType()) 01228 && "Cannot BIT_CONVERT between two different types!"); 01229 if (VT == Operand.getValueType()) return Operand; // noop conversion. 01230 if (OpOpcode == ISD::BIT_CONVERT) // bitconv(bitconv(x)) -> bitconv(x) 01231 return getNode(ISD::BIT_CONVERT, VT, Operand.getOperand(0)); 01232 if (OpOpcode == ISD::UNDEF) 01233 return getNode(ISD::UNDEF, VT); 01234 break; 01235 case ISD::SCALAR_TO_VECTOR: 01236 assert(MVT::isVector(VT) && !MVT::isVector(Operand.getValueType()) && 01237 MVT::getVectorBaseType(VT) == Operand.getValueType() && 01238 "Illegal SCALAR_TO_VECTOR node!"); 01239 break; 01240 case ISD::FNEG: 01241 if (OpOpcode == ISD::FSUB) // -(X-Y) -> (Y-X) 01242 return getNode(ISD::FSUB, VT, Operand.Val->getOperand(1), 01243 Operand.Val->getOperand(0)); 01244 if (OpOpcode == ISD::FNEG) // --X -> X 01245 return Operand.Val->getOperand(0); 01246 break; 01247 case ISD::FABS: 01248 if (OpOpcode == ISD::FNEG) // abs(-X) -> abs(X) 01249 return getNode(ISD::FABS, VT, Operand.Val->getOperand(0)); 01250 break; 01251 } 01252 01253 SDNode *N; 01254 if (VT != MVT::Flag) { // Don't CSE flag producing nodes 01255 SDNode *&E = UnaryOps[std::make_pair(Opcode, std::make_pair(Operand, VT))]; 01256 if (E) return SDOperand(E, 0); 01257 E = N = new SDNode(Opcode, Operand); 01258 } else { 01259 N = new SDNode(Opcode, Operand); 01260 } 01261 N->setValueTypes(VT); 01262 AllNodes.push_back(N); 01263 return SDOperand(N, 0); 01264 } 01265 01266 01267 01268 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 01269 SDOperand N1, SDOperand N2) { 01270 #ifndef NDEBUG 01271 switch (Opcode) { 01272 case ISD::TokenFactor: 01273 assert(VT == MVT::Other && N1.getValueType() == MVT::Other && 01274 N2.getValueType() == MVT::Other && "Invalid token factor!"); 01275 break; 01276 case ISD::AND: 01277 case ISD::OR: 01278 case ISD::XOR: 01279 case ISD::UDIV: 01280 case ISD::UREM: 01281 case ISD::MULHU: 01282 case ISD::MULHS: 01283 assert(MVT::isInteger(VT) && "This operator does not apply to FP types!"); 01284 // fall through 01285 case ISD::ADD: 01286 case ISD::SUB: 01287 case ISD::MUL: 01288 case ISD::SDIV: 01289 case ISD::SREM: 01290 assert(MVT::isInteger(N1.getValueType()) && "Should use F* for FP ops"); 01291 // fall through. 01292 case ISD::FADD: 01293 case ISD::FSUB: 01294 case ISD::FMUL: 01295 case ISD::FDIV: 01296 case ISD::FREM: 01297 assert(N1.getValueType() == N2.getValueType() && 01298 N1.getValueType() == VT && "Binary operator types must match!"); 01299 break; 01300 case ISD::FCOPYSIGN: // N1 and result must match. N1/N2 need not match. 01301 assert(N1.getValueType() == VT && 01302 MVT::isFloatingPoint(N1.getValueType()) && 01303 MVT::isFloatingPoint(N2.getValueType()) && 01304 "Invalid FCOPYSIGN!"); 01305 break; 01306 case ISD::SHL: 01307 case ISD::SRA: 01308 case ISD::SRL: 01309 case ISD::ROTL: 01310 case ISD::ROTR: 01311 assert(VT == N1.getValueType() && 01312 "Shift operators return type must be the same as their first arg"); 01313 assert(MVT::isInteger(VT) && MVT::isInteger(N2.getValueType()) && 01314 VT != MVT::i1 && "Shifts only work on integers"); 01315 break; 01316 case ISD::FP_ROUND_INREG: { 01317 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 01318 assert(VT == N1.getValueType() && "Not an inreg round!"); 01319 assert(MVT::isFloatingPoint(VT) && MVT::isFloatingPoint(EVT) && 01320 "Cannot FP_ROUND_INREG integer types"); 01321 assert(EVT <= VT && "Not rounding down!"); 01322 break; 01323 } 01324 case ISD::AssertSext: 01325 case ISD::AssertZext: 01326 case ISD::SIGN_EXTEND_INREG: { 01327 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 01328 assert(VT == N1.getValueType() && "Not an inreg extend!"); 01329 assert(MVT::isInteger(VT) && MVT::isInteger(EVT) && 01330 "Cannot *_EXTEND_INREG FP types"); 01331 assert(EVT <= VT && "Not extending!"); 01332 } 01333 01334 default: break; 01335 } 01336 #endif 01337 01338 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 01339 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 01340 if (N1C) { 01341 if (Opcode == ISD::SIGN_EXTEND_INREG) { 01342 int64_t Val = N1C->getValue(); 01343 unsigned FromBits = MVT::getSizeInBits(cast<VTSDNode>(N2)->getVT()); 01344 Val <<= 64-FromBits; 01345 Val >>= 64-FromBits; 01346 return getConstant(Val, VT); 01347 } 01348 01349 if (N2C) { 01350 uint64_t C1 = N1C->getValue(), C2 = N2C->getValue(); 01351 switch (Opcode) { 01352 case ISD::ADD: return getConstant(C1 + C2, VT); 01353 case ISD::SUB: return getConstant(C1 - C2, VT); 01354 case ISD::MUL: return getConstant(C1 * C2, VT); 01355 case ISD::UDIV: 01356 if (C2) return getConstant(C1 / C2, VT); 01357 break; 01358 case ISD::UREM : 01359 if (C2) return getConstant(C1 % C2, VT); 01360 break; 01361 case ISD::SDIV : 01362 if (C2) return getConstant(N1C->getSignExtended() / 01363 N2C->getSignExtended(), VT); 01364 break; 01365 case ISD::SREM : 01366 if (C2) return getConstant(N1C->getSignExtended() % 01367 N2C->getSignExtended(), VT); 01368 break; 01369 case ISD::AND : return getConstant(C1 & C2, VT); 01370 case ISD::OR : return getConstant(C1 | C2, VT); 01371 case ISD::XOR : return getConstant(C1 ^ C2, VT); 01372 case ISD::SHL : return getConstant(C1 << C2, VT); 01373 case ISD::SRL : return getConstant(C1 >> C2, VT); 01374 case ISD::SRA : return getConstant(N1C->getSignExtended() >>(int)C2, VT); 01375 case ISD::ROTL : 01376 return getConstant((C1 << C2) | (C1 >> (MVT::getSizeInBits(VT) - C2)), 01377 VT); 01378 case ISD::ROTR : 01379 return getConstant((C1 >> C2) | (C1 << (MVT::getSizeInBits(VT) - C2)), 01380 VT); 01381 default: break; 01382 } 01383 } else { // Cannonicalize constant to RHS if commutative 01384 if (isCommutativeBinOp(Opcode)) { 01385 std::swap(N1C, N2C); 01386 std::swap(N1, N2); 01387 } 01388 } 01389 } 01390 01391 ConstantFPSDNode *N1CFP = dyn_cast<ConstantFPSDNode>(N1.Val); 01392 ConstantFPSDNode *N2CFP = dyn_cast<ConstantFPSDNode>(N2.Val); 01393 if (N1CFP) { 01394 if (N2CFP) { 01395 double C1 = N1CFP->getValue(), C2 = N2CFP->getValue(); 01396 switch (Opcode) { 01397 case ISD::FADD: return getConstantFP(C1 + C2, VT); 01398 case ISD::FSUB: return getConstantFP(C1 - C2, VT); 01399 case ISD::FMUL: return getConstantFP(C1 * C2, VT); 01400 case ISD::FDIV: 01401 if (C2) return getConstantFP(C1 / C2, VT); 01402 break; 01403 case ISD::FREM : 01404 if (C2) return getConstantFP(fmod(C1, C2), VT); 01405 break; 01406 case ISD::FCOPYSIGN: { 01407 union { 01408 double F; 01409 uint64_t I; 01410 } u1; 01411 union { 01412 double F; 01413 int64_t I; 01414 } u2; 01415 u1.F = C1; 01416 u2.F = C2; 01417 if (u2.I < 0) // Sign bit of RHS set? 01418 u1.I |= 1ULL << 63; // Set the sign bit of the LHS. 01419 else 01420 u1.I &= (1ULL << 63)-1; // Clear the sign bit of the LHS. 01421 return getConstantFP(u1.F, VT); 01422 } 01423 default: break; 01424 } 01425 } else { // Cannonicalize constant to RHS if commutative 01426 if (isCommutativeBinOp(Opcode)) { 01427 std::swap(N1CFP, N2CFP); 01428 std::swap(N1, N2); 01429 } 01430 } 01431 } 01432 01433 // Canonicalize an UNDEF to the RHS, even over a constant. 01434 if (N1.getOpcode() == ISD::UNDEF) { 01435 if (isCommutativeBinOp(Opcode)) { 01436 std::swap(N1, N2); 01437 } else { 01438 switch (Opcode) { 01439 case ISD::FP_ROUND_INREG: 01440 case ISD::SIGN_EXTEND_INREG: 01441 case ISD::SUB: 01442 case ISD::FSUB: 01443 case ISD::FDIV: 01444 case ISD::FREM: 01445 case ISD::SRA: 01446 return N1; // fold op(undef, arg2) -> undef 01447 case ISD::UDIV: 01448 case ISD::SDIV: 01449 case ISD::UREM: 01450 case ISD::SREM: 01451 case ISD::SRL: 01452 case ISD::SHL: 01453 return getConstant(0, VT); // fold op(undef, arg2) -> 0 01454 } 01455 } 01456 } 01457 01458 // Fold a bunch of operators when the RHS is undef. 01459 if (N2.getOpcode() == ISD::UNDEF) { 01460 switch (Opcode) { 01461 case ISD::ADD: 01462 case ISD::SUB: 01463 case ISD::FADD: 01464 case ISD::FSUB: 01465 case ISD::FMUL: 01466 case ISD::FDIV: 01467 case ISD::FREM: 01468 case ISD::UDIV: 01469 case ISD::SDIV: 01470 case ISD::UREM: 01471 case ISD::SREM: 01472 case ISD::XOR: 01473 return N2; // fold op(arg1, undef) -> undef 01474 case ISD::MUL: 01475 case ISD::AND: 01476 case ISD::SRL: 01477 case ISD::SHL: 01478 return getConstant(0, VT); // fold op(arg1, undef) -> 0 01479 case ISD::OR: 01480 return getConstant(MVT::getIntVTBitMask(VT), VT); 01481 case ISD::SRA: 01482 return N1; 01483 } 01484 } 01485 01486 // Finally, fold operations that do not require constants. 01487 switch (Opcode) { 01488 case ISD::FP_ROUND_INREG: 01489 if (cast<VTSDNode>(N2)->getVT() == VT) return N1; // Not actually rounding. 01490 break; 01491 case ISD::SIGN_EXTEND_INREG: { 01492 MVT::ValueType EVT = cast<VTSDNode>(N2)->getVT(); 01493 if (EVT == VT) return N1; // Not actually extending 01494 break; 01495 } 01496 01497 // FIXME: figure out how to safely handle things like 01498 // int foo(int x) { return 1 << (x & 255); } 01499 // int bar() { return foo(256); } 01500 #if 0 01501 case ISD::SHL: 01502 case ISD::SRL: 01503 case ISD::SRA: 01504 if (N2.getOpcode() == ISD::SIGN_EXTEND_INREG && 01505 cast<VTSDNode>(N2.getOperand(1))->getVT() != MVT::i1) 01506 return getNode(Opcode, VT, N1, N2.getOperand(0)); 01507 else if (N2.getOpcode() == ISD::AND) 01508 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N2.getOperand(1))) { 01509 // If the and is only masking out bits that cannot effect the shift, 01510 // eliminate the and. 01511 unsigned NumBits = MVT::getSizeInBits(VT); 01512 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 01513 return getNode(Opcode, VT, N1, N2.getOperand(0)); 01514 } 01515 break; 01516 #endif 01517 } 01518 01519 // Memoize this node if possible. 01520 SDNode *N; 01521 if (VT != MVT::Flag) { 01522 SDNode *&BON = BinaryOps[std::make_pair(Opcode, std::make_pair(N1, N2))]; 01523 if (BON) return SDOperand(BON, 0); 01524 01525 BON = N = new SDNode(Opcode, N1, N2); 01526 } else { 01527 N = new SDNode(Opcode, N1, N2); 01528 } 01529 01530 N->setValueTypes(VT); 01531 AllNodes.push_back(N); 01532 return SDOperand(N, 0); 01533 } 01534 01535 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 01536 SDOperand N1, SDOperand N2, SDOperand N3) { 01537 // Perform various simplifications. 01538 ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N1.Val); 01539 ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N2.Val); 01540 //ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N3.Val); 01541 switch (Opcode) { 01542 case ISD::SETCC: { 01543 // Use SimplifySetCC to simplify SETCC's. 01544 SDOperand Simp = SimplifySetCC(VT, N1, N2, cast<CondCodeSDNode>(N3)->get()); 01545 if (Simp.Val) return Simp; 01546 break; 01547 } 01548 case ISD::SELECT: 01549 if (N1C) 01550 if (N1C->getValue()) 01551 return N2; // select true, X, Y -> X 01552 else 01553 return N3; // select false, X, Y -> Y 01554 01555 if (N2 == N3) return N2; // select C, X, X -> X 01556 break; 01557 case ISD::BRCOND: 01558 if (N2C) 01559 if (N2C->getValue()) // Unconditional branch 01560 return getNode(ISD::BR, MVT::Other, N1, N3); 01561 else 01562 return N1; // Never-taken branch 01563 break; 01564 case ISD::VECTOR_SHUFFLE: 01565 assert(VT == N1.getValueType() && VT == N2.getValueType() && 01566 MVT::isVector(VT) && MVT::isVector(N3.getValueType()) && 01567 N3.getOpcode() == ISD::BUILD_VECTOR && 01568 MVT::getVectorNumElements(VT) == N3.getNumOperands() && 01569 "Illegal VECTOR_SHUFFLE node!"); 01570 break; 01571 } 01572 01573 std::vector<SDOperand> Ops; 01574 Ops.reserve(3); 01575 Ops.push_back(N1); 01576 Ops.push_back(N2); 01577 Ops.push_back(N3); 01578 01579 // Memoize node if it doesn't produce a flag. 01580 SDNode *N; 01581 if (VT != MVT::Flag) { 01582 SDNode *&E = OneResultNodes[std::make_pair(Opcode,std::make_pair(VT, Ops))]; 01583 if (E) return SDOperand(E, 0); 01584 E = N = new SDNode(Opcode, N1, N2, N3); 01585 } else { 01586 N = new SDNode(Opcode, N1, N2, N3); 01587 } 01588 N->setValueTypes(VT); 01589 AllNodes.push_back(N); 01590 return SDOperand(N, 0); 01591 } 01592 01593 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 01594 SDOperand N1, SDOperand N2, SDOperand N3, 01595 SDOperand N4) { 01596 std::vector<SDOperand> Ops; 01597 Ops.reserve(4); 01598 Ops.push_back(N1); 01599 Ops.push_back(N2); 01600 Ops.push_back(N3); 01601 Ops.push_back(N4); 01602 return getNode(Opcode, VT, Ops); 01603 } 01604 01605 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 01606 SDOperand N1, SDOperand N2, SDOperand N3, 01607 SDOperand N4, SDOperand N5) { 01608 std::vector<SDOperand> Ops; 01609 Ops.reserve(5); 01610 Ops.push_back(N1); 01611 Ops.push_back(N2); 01612 Ops.push_back(N3); 01613 Ops.push_back(N4); 01614 Ops.push_back(N5); 01615 return getNode(Opcode, VT, Ops); 01616 } 01617 01618 SDOperand SelectionDAG::getLoad(MVT::ValueType VT, 01619 SDOperand Chain, SDOperand Ptr, 01620 SDOperand SV) { 01621 SDNode *&N = Loads[std::make_pair(Ptr, std::make_pair(Chain, VT))]; 01622 if (N) return SDOperand(N, 0); 01623 N = new SDNode(ISD::LOAD, Chain, Ptr, SV); 01624 01625 // Loads have a token chain. 01626 setNodeValueTypes(N, VT, MVT::Other); 01627 AllNodes.push_back(N); 01628 return SDOperand(N, 0); 01629 } 01630 01631 SDOperand SelectionDAG::getVecLoad(unsigned Count, MVT::ValueType EVT, 01632 SDOperand Chain, SDOperand Ptr, 01633 SDOperand SV) { 01634 std::vector<SDOperand> Ops; 01635 Ops.reserve(5); 01636 Ops.push_back(Chain); 01637 Ops.push_back(Ptr); 01638 Ops.push_back(SV); 01639 Ops.push_back(getConstant(Count, MVT::i32)); 01640 Ops.push_back(getValueType(EVT)); 01641 std::vector<MVT::ValueType> VTs; 01642 VTs.reserve(2); 01643 VTs.push_back(MVT::Vector); VTs.push_back(MVT::Other); // Add token chain. 01644 return getNode(ISD::VLOAD, VTs, Ops); 01645 } 01646 01647 SDOperand SelectionDAG::getExtLoad(unsigned Opcode, MVT::ValueType VT, 01648 SDOperand Chain, SDOperand Ptr, SDOperand SV, 01649 MVT::ValueType EVT) { 01650 std::vector<SDOperand> Ops; 01651 Ops.reserve(4); 01652 Ops.push_back(Chain); 01653 Ops.push_back(Ptr); 01654 Ops.push_back(SV); 01655 Ops.push_back(getValueType(EVT)); 01656 std::vector<MVT::ValueType> VTs; 01657 VTs.reserve(2); 01658 VTs.push_back(VT); VTs.push_back(MVT::Other); // Add token chain. 01659 return getNode(Opcode, VTs, Ops); 01660 } 01661 01662 SDOperand SelectionDAG::getSrcValue(const Value *V, int Offset) { 01663 assert((!V || isa<PointerType>(V->getType())) && 01664 "SrcValue is not a pointer?"); 01665 SDNode *&N = ValueNodes[std::make_pair(V, Offset)]; 01666 if (N) return SDOperand(N, 0); 01667 01668 N = new SrcValueSDNode(V, Offset); 01669 AllNodes.push_back(N); 01670 return SDOperand(N, 0); 01671 } 01672 01673 SDOperand SelectionDAG::getVAArg(MVT::ValueType VT, 01674 SDOperand Chain, SDOperand Ptr, 01675 SDOperand SV) { 01676 std::vector<SDOperand> Ops; 01677 Ops.reserve(3); 01678 Ops.push_back(Chain); 01679 Ops.push_back(Ptr); 01680 Ops.push_back(SV); 01681 std::vector<MVT::ValueType> VTs; 01682 VTs.reserve(2); 01683 VTs.push_back(VT); VTs.push_back(MVT::Other); // Add token chain. 01684 return getNode(ISD::VAARG, VTs, Ops); 01685 } 01686 01687 SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT, 01688 std::vector<SDOperand> &Ops) { 01689 switch (Ops.size()) { 01690 case 0: return getNode(Opcode, VT); 01691 case 1: return getNode(Opcode, VT, Ops[0]); 01692 case 2: return getNode(Opcode, VT, Ops[0], Ops[1]); 01693 case 3: return getNode(Opcode, VT, Ops[0], Ops[1], Ops[2]); 01694 default: break; 01695 } 01696 01697 switch (Opcode) { 01698 default: break; 01699 case ISD::TRUNCSTORE: { 01700 assert(Ops.size() == 5 && "TRUNCSTORE takes 5 operands!"); 01701 MVT::ValueType EVT = cast<VTSDNode>(Ops[4])->getVT(); 01702 #if 0 // FIXME: If the target supports EVT natively, convert to a truncate/store 01703 // If this is a truncating store of a constant, convert to the desired type 01704 // and store it instead. 01705 if (isa<Constant>(Ops[0])) { 01706 SDOperand Op = getNode(ISD::TRUNCATE, EVT, N1); 01707 if (isa<Constant>(Op)) 01708 N1 = Op; 01709 } 01710 // Also for ConstantFP? 01711 #endif 01712 if (Ops[0].getValueType() == EVT) // Normal store? 01713 return getNode(ISD::STORE, VT, Ops[0], Ops[1], Ops[2], Ops[3]); 01714 assert(Ops[1].getValueType() > EVT && "Not a truncation?"); 01715 assert(MVT::isInteger(Ops[1].getValueType()) == MVT::isInteger(EVT) && 01716 "Can't do FP-INT conversion!"); 01717 break; 01718 } 01719 case ISD::SELECT_CC: { 01720 assert(Ops.size() == 5 && "SELECT_CC takes 5 operands!"); 01721 assert(Ops[0].getValueType() == Ops[1].getValueType() && 01722 "LHS and RHS of condition must have same type!"); 01723 assert(Ops[2].getValueType() == Ops[3].getValueType() && 01724 "True and False arms of SelectCC must have same type!"); 01725 assert(Ops[2].getValueType() == VT && 01726 "select_cc node must be of same type as true and false value!"); 01727 break; 01728 } 01729 case ISD::BR_CC: { 01730 assert(Ops.size() == 5 && "BR_CC takes 5 operands!"); 01731 assert(Ops[2].getValueType() == Ops[3].getValueType() && 01732 "LHS/RHS of comparison should match types!"); 01733 break; 01734 } 01735 } 01736 01737 // Memoize nodes. 01738 SDNode *N; 01739 if (VT != MVT::Flag) { 01740 SDNode *&E = 01741 OneResultNodes[std::make_pair(Opcode, std::make_pair(VT, Ops))]; 01742 if (E) return SDOperand(E, 0); 01743 E = N = new SDNode(Opcode, Ops); 01744 } else { 01745 N = new SDNode(Opcode, Ops); 01746 } 01747 N->setValueTypes(VT); 01748 AllNodes.push_back(N); 01749 return SDOperand(N, 0); 01750 } 01751 01752 SDOperand SelectionDAG::getNode(unsigned Opcode, 01753 std::vector<MVT::ValueType> &ResultTys, 01754 std::vector<SDOperand> &Ops) { 01755 if (ResultTys.size() == 1) 01756 return getNode(Opcode, ResultTys[0], Ops); 01757 01758 switch (Opcode) { 01759 case ISD::EXTLOAD: 01760 case ISD::SEXTLOAD: 01761 case ISD::ZEXTLOAD: { 01762 MVT::ValueType EVT = cast<VTSDNode>(Ops[3])->getVT(); 01763 assert(Ops.size() == 4 && ResultTys.size() == 2 && "Bad *EXTLOAD!"); 01764 // If they are asking for an extending load from/to the same thing, return a 01765 // normal load. 01766 if (ResultTys[0] == EVT) 01767 return getLoad(ResultTys[0], Ops[0], Ops[1], Ops[2]); 01768 if (MVT::isVector(ResultTys[0])) { 01769 assert(EVT == MVT::getVectorBaseType(ResultTys[0]) && 01770 "Invalid vector extload!"); 01771 } else { 01772 assert(EVT < ResultTys[0] && 01773 "Should only be an extending load, not truncating!"); 01774 } 01775 assert((Opcode == ISD::EXTLOAD || MVT::isInteger(ResultTys[0])) && 01776 "Cannot sign/zero extend a FP/Vector load!"); 01777 assert(MVT::isInteger(ResultTys[0]) == MVT::isInteger(EVT) && 01778 "Cannot convert from FP to Int or Int -> FP!"); 01779 break; 01780 } 01781 01782 // FIXME: figure out how to safely handle things like 01783 // int foo(int x) { return 1 << (x & 255); } 01784 // int bar() { return foo(256); } 01785 #if 0 01786 case ISD::SRA_PARTS: 01787 case ISD::SRL_PARTS: 01788 case ISD::SHL_PARTS: 01789 if (N3.getOpcode() == ISD::SIGN_EXTEND_INREG && 01790 cast<VTSDNode>(N3.getOperand(1))->getVT() != MVT::i1) 01791 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 01792 else if (N3.getOpcode() == ISD::AND) 01793 if (ConstantSDNode *AndRHS = dyn_cast<ConstantSDNode>(N3.getOperand(1))) { 01794 // If the and is only masking out bits that cannot effect the shift, 01795 // eliminate the and. 01796 unsigned NumBits = MVT::getSizeInBits(VT)*2; 01797 if ((AndRHS->getValue() & (NumBits-1)) == NumBits-1) 01798 return getNode(Opcode, VT, N1, N2, N3.getOperand(0)); 01799 } 01800 break; 01801 #endif 01802 } 01803 01804 // Memoize the node unless it returns a flag. 01805 SDNode *N; 01806 if (ResultTys.back() != MVT::Flag) { 01807 SDNode *&E = 01808 ArbitraryNodes[std::make_pair(Opcode, std::make_pair(ResultTys, Ops))]; 01809 if (E) return SDOperand(E, 0); 01810 E = N = new SDNode(Opcode, Ops); 01811 } else { 01812 N = new SDNode(Opcode, Ops); 01813 } 01814 setNodeValueTypes(N, ResultTys); 01815 AllNodes.push_back(N); 01816 return SDOperand(N, 0); 01817 } 01818 01819 void SelectionDAG::setNodeValueTypes(SDNode *N, 01820 std::vector<MVT::ValueType> &RetVals) { 01821 switch (RetVals.size()) { 01822 case 0: return; 01823 case 1: N->setValueTypes(RetVals[0]); return; 01824 case 2: setNodeValueTypes(N, RetVals[0], RetVals[1]); return; 01825 default: break; 01826 } 01827 01828 std::list<std::vector<MVT::ValueType> >::iterator I = 01829 std::find(VTList.begin(), VTList.end(), RetVals); 01830 if (I == VTList.end()) { 01831 VTList.push_front(RetVals); 01832 I = VTList.begin(); 01833 } 01834 01835 N->setValueTypes(&(*I)[0], I->size()); 01836 } 01837 01838 void SelectionDAG::setNodeValueTypes(SDNode *N, MVT::ValueType VT1, 01839 MVT::ValueType VT2) { 01840 for (std::list<std::vector<MVT::ValueType> >::iterator I = VTList.begin(), 01841 E = VTList.end(); I != E; ++I) { 01842 if (I->size() == 2 && (*I)[0] == VT1 && (*I)[1] == VT2) { 01843 N->setValueTypes(&(*I)[0], 2); 01844 return; 01845 } 01846 } 01847 std::vector<MVT::ValueType> V; 01848 V.push_back(VT1); 01849 V.push_back(VT2); 01850 VTList.push_front(V); 01851 N->setValueTypes(&(*VTList.begin())[0], 2); 01852 } 01853 01854 /// UpdateNodeOperands - *Mutate* the specified node in-place to have the 01855 /// specified operands. If the resultant node already exists in the DAG, 01856 /// this does not modify the specified node, instead it returns the node that 01857 /// already exists. If the resultant node does not exist in the DAG, the 01858 /// input node is returned. As a degenerate case, if you specify the same 01859 /// input operands as the node already has, the input node is returned. 01860 SDOperand SelectionDAG:: 01861 UpdateNodeOperands(SDOperand InN, SDOperand Op) { 01862 SDNode *N = InN.Val; 01863 assert(N->getNumOperands() == 1 && "Update with wrong number of operands"); 01864 01865 // Check to see if there is no change. 01866 if (Op == N->getOperand(0)) return InN; 01867 01868 // See if the modified node already exists. 01869 SDNode **NewSlot = FindModifiedNodeSlot(N, Op); 01870 if (NewSlot && *NewSlot) 01871 return SDOperand(*NewSlot, InN.ResNo); 01872 01873 // Nope it doesn't. Remove the node from it's current place in the maps. 01874 if (NewSlot) 01875 RemoveNodeFromCSEMaps(N); 01876 01877 // Now we update the operands. 01878 N->OperandList[0].Val->removeUser(N); 01879 Op.Val->addUser(N); 01880 N->OperandList[0] = Op; 01881 01882 // If this gets put into a CSE map, add it. 01883 if (NewSlot) *NewSlot = N; 01884 return InN; 01885 } 01886 01887 SDOperand SelectionDAG:: 01888 UpdateNodeOperands(SDOperand InN, SDOperand Op1, SDOperand Op2) { 01889 SDNode *N = InN.Val; 01890 assert(N->getNumOperands() == 2 && "Update with wrong number of operands"); 01891 01892 // Check to see if there is no change. 01893 bool AnyChange = false; 01894 if (Op1 == N->getOperand(0) && Op2 == N->getOperand(1)) 01895 return InN; // No operands changed, just return the input node. 01896 01897 // See if the modified node already exists. 01898 SDNode **NewSlot = FindModifiedNodeSlot(N, Op1, Op2); 01899 if (NewSlot && *NewSlot) 01900 return SDOperand(*NewSlot, InN.ResNo); 01901 01902 // Nope it doesn't. Remove the node from it's current place in the maps. 01903 if (NewSlot) 01904 RemoveNodeFromCSEMaps(N); 01905 01906 // Now we update the operands. 01907 if (N->OperandList[0] != Op1) { 01908 N->OperandList[0].Val->removeUser(N); 01909 Op1.Val->addUser(N); 01910 N->OperandList[0] = Op1; 01911 } 01912 if (N->OperandList[1] != Op2) { 01913 N->OperandList[1].Val->removeUser(N); 01914 Op2.Val->addUser(N); 01915 N->OperandList[1] = Op2; 01916 } 01917 01918 // If this gets put into a CSE map, add it. 01919 if (NewSlot) *NewSlot = N; 01920 return InN; 01921 } 01922 01923 SDOperand SelectionDAG:: 01924 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, SDOperand Op3) { 01925 std::vector<SDOperand> Ops; 01926 Ops.push_back(Op1); 01927 Ops.push_back(Op2); 01928 Ops.push_back(Op3); 01929 return UpdateNodeOperands(N, Ops); 01930 } 01931 01932 SDOperand SelectionDAG:: 01933 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 01934 SDOperand Op3, SDOperand Op4) { 01935 std::vector<SDOperand> Ops; 01936 Ops.push_back(Op1); 01937 Ops.push_back(Op2); 01938 Ops.push_back(Op3); 01939 Ops.push_back(Op4); 01940 return UpdateNodeOperands(N, Ops); 01941 } 01942 01943 SDOperand SelectionDAG:: 01944 UpdateNodeOperands(SDOperand N, SDOperand Op1, SDOperand Op2, 01945 SDOperand Op3, SDOperand Op4, SDOperand Op5) { 01946 std::vector<SDOperand> Ops; 01947 Ops.push_back(Op1); 01948 Ops.push_back(Op2); 01949 Ops.push_back(Op3); 01950 Ops.push_back(Op4); 01951 Ops.push_back(Op5); 01952 return UpdateNodeOperands(N, Ops); 01953 } 01954 01955 01956 SDOperand SelectionDAG:: 01957 UpdateNodeOperands(SDOperand InN, const std::vector<SDOperand> &Ops) { 01958 SDNode *N = InN.Val; 01959 assert(N->getNumOperands() == Ops.size() && 01960 "Update with wrong number of operands"); 01961 01962 // Check to see if there is no change. 01963 unsigned NumOps = Ops.size(); 01964 bool AnyChange = false; 01965 for (unsigned i = 0; i != NumOps; ++i) { 01966 if (Ops[i] != N->getOperand(i)) { 01967 AnyChange = true; 01968 break; 01969 } 01970 } 01971 01972 // No operands changed, just return the input node. 01973 if (!AnyChange) return InN; 01974 01975 // See if the modified node already exists. 01976 SDNode **NewSlot = FindModifiedNodeSlot(N, Ops); 01977 if (NewSlot && *NewSlot) 01978 return SDOperand(*NewSlot, InN.ResNo); 01979 01980 // Nope it doesn't. Remove the node from it's current place in the maps. 01981 if (NewSlot) 01982 RemoveNodeFromCSEMaps(N); 01983 01984 // Now we update the operands. 01985 for (unsigned i = 0; i != NumOps; ++i) { 01986 if (N->OperandList[i] != Ops[i]) { 01987 N->OperandList[i].Val->removeUser(N); 01988 Ops[i].Val->addUser(N); 01989 N->OperandList[i] = Ops[i]; 01990 } 01991 } 01992 01993 // If this gets put into a CSE map, add it. 01994 if (NewSlot) *NewSlot = N; 01995 return InN; 01996 } 01997 01998 01999 02000 02001 /// SelectNodeTo - These are used for target selectors to *mutate* the 02002 /// specified node to have the specified return type, Target opcode, and 02003 /// operands. Note that target opcodes are stored as 02004 /// ISD::BUILTIN_OP_END+TargetOpcode in the node opcode field. 02005 /// 02006 /// Note that SelectNodeTo returns the resultant node. If there is already a 02007 /// node of the specified opcode and operands, it returns that node instead of 02008 /// the current one. 02009 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02010 MVT::ValueType VT) { 02011 // If an identical node already exists, use it. 02012 SDNode *&ON = NullaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, VT)]; 02013 if (ON) return SDOperand(ON, 0); 02014 02015 RemoveNodeFromCSEMaps(N); 02016 02017 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02018 N->setValueTypes(VT); 02019 02020 ON = N; // Memoize the new node. 02021 return SDOperand(N, 0); 02022 } 02023 02024 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02025 MVT::ValueType VT, SDOperand Op1) { 02026 // If an identical node already exists, use it. 02027 SDNode *&ON = UnaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02028 std::make_pair(Op1, VT))]; 02029 if (ON) return SDOperand(ON, 0); 02030 02031 RemoveNodeFromCSEMaps(N); 02032 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02033 N->setValueTypes(VT); 02034 N->setOperands(Op1); 02035 02036 ON = N; // Memoize the new node. 02037 return SDOperand(N, 0); 02038 } 02039 02040 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02041 MVT::ValueType VT, SDOperand Op1, 02042 SDOperand Op2) { 02043 // If an identical node already exists, use it. 02044 SDNode *&ON = BinaryOps[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02045 std::make_pair(Op1, Op2))]; 02046 if (ON) return SDOperand(ON, 0); 02047 02048 RemoveNodeFromCSEMaps(N); 02049 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02050 N->setValueTypes(VT); 02051 N->setOperands(Op1, Op2); 02052 02053 ON = N; // Memoize the new node. 02054 return SDOperand(N, 0); 02055 } 02056 02057 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02058 MVT::ValueType VT, SDOperand Op1, 02059 SDOperand Op2, SDOperand Op3) { 02060 // If an identical node already exists, use it. 02061 std::vector<SDOperand> OpList; 02062 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 02063 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02064 std::make_pair(VT, OpList))]; 02065 if (ON) return SDOperand(ON, 0); 02066 02067 RemoveNodeFromCSEMaps(N); 02068 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02069 N->setValueTypes(VT); 02070 N->setOperands(Op1, Op2, Op3); 02071 02072 ON = N; // Memoize the new node. 02073 return SDOperand(N, 0); 02074 } 02075 02076 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02077 MVT::ValueType VT, SDOperand Op1, 02078 SDOperand Op2, SDOperand Op3, 02079 SDOperand Op4) { 02080 // If an identical node already exists, use it. 02081 std::vector<SDOperand> OpList; 02082 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 02083 OpList.push_back(Op4); 02084 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02085 std::make_pair(VT, OpList))]; 02086 if (ON) return SDOperand(ON, 0); 02087 02088 RemoveNodeFromCSEMaps(N); 02089 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02090 N->setValueTypes(VT); 02091 N->setOperands(Op1, Op2, Op3, Op4); 02092 02093 ON = N; // Memoize the new node. 02094 return SDOperand(N, 0); 02095 } 02096 02097 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02098 MVT::ValueType VT, SDOperand Op1, 02099 SDOperand Op2, SDOperand Op3,SDOperand Op4, 02100 SDOperand Op5) { 02101 // If an identical node already exists, use it. 02102 std::vector<SDOperand> OpList; 02103 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 02104 OpList.push_back(Op4); OpList.push_back(Op5); 02105 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02106 std::make_pair(VT, OpList))]; 02107 if (ON) return SDOperand(ON, 0); 02108 02109 RemoveNodeFromCSEMaps(N); 02110 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02111 N->setValueTypes(VT); 02112 N->setOperands(Op1, Op2, Op3, Op4, Op5); 02113 02114 ON = N; // Memoize the new node. 02115 return SDOperand(N, 0); 02116 } 02117 02118 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02119 MVT::ValueType VT, SDOperand Op1, 02120 SDOperand Op2, SDOperand Op3,SDOperand Op4, 02121 SDOperand Op5, SDOperand Op6) { 02122 // If an identical node already exists, use it. 02123 std::vector<SDOperand> OpList; 02124 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 02125 OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); 02126 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02127 std::make_pair(VT, OpList))]; 02128 if (ON) return SDOperand(ON, 0); 02129 02130 RemoveNodeFromCSEMaps(N); 02131 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02132 N->setValueTypes(VT); 02133 N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6); 02134 02135 ON = N; // Memoize the new node. 02136 return SDOperand(N, 0); 02137 } 02138 02139 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02140 MVT::ValueType VT, SDOperand Op1, 02141 SDOperand Op2, SDOperand Op3,SDOperand Op4, 02142 SDOperand Op5, SDOperand Op6, 02143 SDOperand Op7) { 02144 // If an identical node already exists, use it. 02145 std::vector<SDOperand> OpList; 02146 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 02147 OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); 02148 OpList.push_back(Op7); 02149 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02150 std::make_pair(VT, OpList))]; 02151 if (ON) return SDOperand(ON, 0); 02152 02153 RemoveNodeFromCSEMaps(N); 02154 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02155 N->setValueTypes(VT); 02156 N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7); 02157 02158 ON = N; // Memoize the new node. 02159 return SDOperand(N, 0); 02160 } 02161 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02162 MVT::ValueType VT, SDOperand Op1, 02163 SDOperand Op2, SDOperand Op3,SDOperand Op4, 02164 SDOperand Op5, SDOperand Op6, 02165 SDOperand Op7, SDOperand Op8) { 02166 // If an identical node already exists, use it. 02167 std::vector<SDOperand> OpList; 02168 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 02169 OpList.push_back(Op4); OpList.push_back(Op5); OpList.push_back(Op6); 02170 OpList.push_back(Op7); OpList.push_back(Op8); 02171 SDNode *&ON = OneResultNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02172 std::make_pair(VT, OpList))]; 02173 if (ON) return SDOperand(ON, 0); 02174 02175 RemoveNodeFromCSEMaps(N); 02176 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02177 N->setValueTypes(VT); 02178 N->setOperands(Op1, Op2, Op3, Op4, Op5, Op6, Op7, Op8); 02179 02180 ON = N; // Memoize the new node. 02181 return SDOperand(N, 0); 02182 } 02183 02184 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02185 MVT::ValueType VT1, MVT::ValueType VT2, 02186 SDOperand Op1, SDOperand Op2) { 02187 // If an identical node already exists, use it. 02188 std::vector<SDOperand> OpList; 02189 OpList.push_back(Op1); OpList.push_back(Op2); 02190 std::vector<MVT::ValueType> VTList; 02191 VTList.push_back(VT1); VTList.push_back(VT2); 02192 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02193 std::make_pair(VTList, OpList))]; 02194 if (ON) return SDOperand(ON, 0); 02195 02196 RemoveNodeFromCSEMaps(N); 02197 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02198 setNodeValueTypes(N, VT1, VT2); 02199 N->setOperands(Op1, Op2); 02200 02201 ON = N; // Memoize the new node. 02202 return SDOperand(N, 0); 02203 } 02204 02205 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02206 MVT::ValueType VT1, MVT::ValueType VT2, 02207 SDOperand Op1, SDOperand Op2, 02208 SDOperand Op3) { 02209 // If an identical node already exists, use it. 02210 std::vector<SDOperand> OpList; 02211 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 02212 std::vector<MVT::ValueType> VTList; 02213 VTList.push_back(VT1); VTList.push_back(VT2); 02214 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02215 std::make_pair(VTList, OpList))]; 02216 if (ON) return SDOperand(ON, 0); 02217 02218 RemoveNodeFromCSEMaps(N); 02219 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02220 setNodeValueTypes(N, VT1, VT2); 02221 N->setOperands(Op1, Op2, Op3); 02222 02223 ON = N; // Memoize the new node. 02224 return SDOperand(N, 0); 02225 } 02226 02227 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02228 MVT::ValueType VT1, MVT::ValueType VT2, 02229 SDOperand Op1, SDOperand Op2, 02230 SDOperand Op3, SDOperand Op4) { 02231 // If an identical node already exists, use it. 02232 std::vector<SDOperand> OpList; 02233 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 02234 OpList.push_back(Op4); 02235 std::vector<MVT::ValueType> VTList; 02236 VTList.push_back(VT1); VTList.push_back(VT2); 02237 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02238 std::make_pair(VTList, OpList))]; 02239 if (ON) return SDOperand(ON, 0); 02240 02241 RemoveNodeFromCSEMaps(N); 02242 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02243 setNodeValueTypes(N, VT1, VT2); 02244 N->setOperands(Op1, Op2, Op3, Op4); 02245 02246 ON = N; // Memoize the new node. 02247 return SDOperand(N, 0); 02248 } 02249 02250 SDOperand SelectionDAG::SelectNodeTo(SDNode *N, unsigned TargetOpc, 02251 MVT::ValueType VT1, MVT::ValueType VT2, 02252 SDOperand Op1, SDOperand Op2, 02253 SDOperand Op3, SDOperand Op4, 02254 SDOperand Op5) { 02255 // If an identical node already exists, use it. 02256 std::vector<SDOperand> OpList; 02257 OpList.push_back(Op1); OpList.push_back(Op2); OpList.push_back(Op3); 02258 OpList.push_back(Op4); OpList.push_back(Op5); 02259 std::vector<MVT::ValueType> VTList; 02260 VTList.push_back(VT1); VTList.push_back(VT2); 02261 SDNode *&ON = ArbitraryNodes[std::make_pair(ISD::BUILTIN_OP_END+TargetOpc, 02262 std::make_pair(VTList, OpList))]; 02263 if (ON) return SDOperand(ON, 0); 02264 02265 RemoveNodeFromCSEMaps(N); 02266 N->MorphNodeTo(ISD::BUILTIN_OP_END+TargetOpc); 02267 setNodeValueTypes(N, VT1, VT2); 02268 N->setOperands(Op1, Op2, Op3, Op4, Op5); 02269 02270 ON = N; // Memoize the new node. 02271 return SDOperand(N, 0); 02272 } 02273 02274 /// getTargetNode - These are used for target selectors to create a new node 02275 /// with specified return type(s), target opcode, and operands. 02276 /// 02277 /// Note that getTargetNode returns the resultant node. If there is already a 02278 /// node of the specified opcode and operands, it returns that node instead of 02279 /// the current one. 02280 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT) { 02281 return getNode(ISD::BUILTIN_OP_END+Opcode, VT).Val; 02282 } 02283 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 02284 SDOperand Op1) { 02285 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1).Val; 02286 } 02287 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 02288 SDOperand Op1, SDOperand Op2) { 02289 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2).Val; 02290 } 02291 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 02292 SDOperand Op1, SDOperand Op2, SDOperand Op3) { 02293 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3).Val; 02294 } 02295 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 02296 SDOperand Op1, SDOperand Op2, SDOperand Op3, 02297 SDOperand Op4) { 02298 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4).Val; 02299 } 02300 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 02301 SDOperand Op1, SDOperand Op2, SDOperand Op3, 02302 SDOperand Op4, SDOperand Op5) { 02303 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Op1, Op2, Op3, Op4, Op5).Val; 02304 } 02305 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 02306 SDOperand Op1, SDOperand Op2, SDOperand Op3, 02307 SDOperand Op4, SDOperand Op5, SDOperand Op6) { 02308 std::vector<SDOperand> Ops; 02309 Ops.reserve(6); 02310 Ops.push_back(Op1); 02311 Ops.push_back(Op2); 02312 Ops.push_back(Op3); 02313 Ops.push_back(Op4); 02314 Ops.push_back(Op5); 02315 Ops.push_back(Op6); 02316 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; 02317 } 02318 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 02319 SDOperand Op1, SDOperand Op2, SDOperand Op3, 02320 SDOperand Op4, SDOperand Op5, SDOperand Op6, 02321 SDOperand Op7) { 02322 std::vector<SDOperand> Ops; 02323 Ops.reserve(7); 02324 Ops.push_back(Op1); 02325 Ops.push_back(Op2); 02326 Ops.push_back(Op3); 02327 Ops.push_back(Op4); 02328 Ops.push_back(Op5); 02329 Ops.push_back(Op6); 02330 Ops.push_back(Op7); 02331 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; 02332 } 02333 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 02334 SDOperand Op1, SDOperand Op2, SDOperand Op3, 02335 SDOperand Op4, SDOperand Op5, SDOperand Op6, 02336 SDOperand Op7, SDOperand Op8) { 02337 std::vector<SDOperand> Ops; 02338 Ops.reserve(8); 02339 Ops.push_back(Op1); 02340 Ops.push_back(Op2); 02341 Ops.push_back(Op3); 02342 Ops.push_back(Op4); 02343 Ops.push_back(Op5); 02344 Ops.push_back(Op6); 02345 Ops.push_back(Op7); 02346 Ops.push_back(Op8); 02347 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; 02348 } 02349 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT, 02350 std::vector<SDOperand> &Ops) { 02351 return getNode(ISD::BUILTIN_OP_END+Opcode, VT, Ops).Val; 02352 } 02353 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02354 MVT::ValueType VT2, SDOperand Op1) { 02355 std::vector<MVT::ValueType> ResultTys; 02356 ResultTys.push_back(VT1); 02357 ResultTys.push_back(VT2); 02358 std::vector<SDOperand> Ops; 02359 Ops.push_back(Op1); 02360 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02361 } 02362 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02363 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2) { 02364 std::vector<MVT::ValueType> ResultTys; 02365 ResultTys.push_back(VT1); 02366 ResultTys.push_back(VT2); 02367 std::vector<SDOperand> Ops; 02368 Ops.push_back(Op1); 02369 Ops.push_back(Op2); 02370 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02371 } 02372 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02373 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 02374 SDOperand Op3) { 02375 std::vector<MVT::ValueType> ResultTys; 02376 ResultTys.push_back(VT1); 02377 ResultTys.push_back(VT2); 02378 std::vector<SDOperand> Ops; 02379 Ops.push_back(Op1); 02380 Ops.push_back(Op2); 02381 Ops.push_back(Op3); 02382 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02383 } 02384 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02385 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 02386 SDOperand Op3, SDOperand Op4) { 02387 std::vector<MVT::ValueType> ResultTys; 02388 ResultTys.push_back(VT1); 02389 ResultTys.push_back(VT2); 02390 std::vector<SDOperand> Ops; 02391 Ops.push_back(Op1); 02392 Ops.push_back(Op2); 02393 Ops.push_back(Op3); 02394 Ops.push_back(Op4); 02395 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02396 } 02397 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02398 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 02399 SDOperand Op3, SDOperand Op4, SDOperand Op5) { 02400 std::vector<MVT::ValueType> ResultTys; 02401 ResultTys.push_back(VT1); 02402 ResultTys.push_back(VT2); 02403 std::vector<SDOperand> Ops; 02404 Ops.push_back(Op1); 02405 Ops.push_back(Op2); 02406 Ops.push_back(Op3); 02407 Ops.push_back(Op4); 02408 Ops.push_back(Op5); 02409 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02410 } 02411 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02412 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 02413 SDOperand Op3, SDOperand Op4, SDOperand Op5, 02414 SDOperand Op6) { 02415 std::vector<MVT::ValueType> ResultTys; 02416 ResultTys.push_back(VT1); 02417 ResultTys.push_back(VT2); 02418 std::vector<SDOperand> Ops; 02419 Ops.push_back(Op1); 02420 Ops.push_back(Op2); 02421 Ops.push_back(Op3); 02422 Ops.push_back(Op4); 02423 Ops.push_back(Op5); 02424 Ops.push_back(Op6); 02425 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02426 } 02427 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02428 MVT::ValueType VT2, SDOperand Op1, SDOperand Op2, 02429 SDOperand Op3, SDOperand Op4, SDOperand Op5, 02430 SDOperand Op6, SDOperand Op7) { 02431 std::vector<MVT::ValueType> ResultTys; 02432 ResultTys.push_back(VT1); 02433 ResultTys.push_back(VT2); 02434 std::vector<SDOperand> Ops; 02435 Ops.push_back(Op1); 02436 Ops.push_back(Op2); 02437 Ops.push_back(Op3); 02438 Ops.push_back(Op4); 02439 Ops.push_back(Op5); 02440 Ops.push_back(Op6); 02441 Ops.push_back(Op7); 02442 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02443 } 02444 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02445 MVT::ValueType VT2, MVT::ValueType VT3, 02446 SDOperand Op1, SDOperand Op2) { 02447 std::vector<MVT::ValueType> ResultTys; 02448 ResultTys.push_back(VT1); 02449 ResultTys.push_back(VT2); 02450 ResultTys.push_back(VT3); 02451 std::vector<SDOperand> Ops; 02452 Ops.push_back(Op1); 02453 Ops.push_back(Op2); 02454 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02455 } 02456 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02457 MVT::ValueType VT2, MVT::ValueType VT3, 02458 SDOperand Op1, SDOperand Op2, 02459 SDOperand Op3, SDOperand Op4, SDOperand Op5) { 02460 std::vector<MVT::ValueType> ResultTys; 02461 ResultTys.push_back(VT1); 02462 ResultTys.push_back(VT2); 02463 ResultTys.push_back(VT3); 02464 std::vector<SDOperand> Ops; 02465 Ops.push_back(Op1); 02466 Ops.push_back(Op2); 02467 Ops.push_back(Op3); 02468 Ops.push_back(Op4); 02469 Ops.push_back(Op5); 02470 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02471 } 02472 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02473 MVT::ValueType VT2, MVT::ValueType VT3, 02474 SDOperand Op1, SDOperand Op2, 02475 SDOperand Op3, SDOperand Op4, SDOperand Op5, 02476 SDOperand Op6) { 02477 std::vector<MVT::ValueType> ResultTys; 02478 ResultTys.push_back(VT1); 02479 ResultTys.push_back(VT2); 02480 ResultTys.push_back(VT3); 02481 std::vector<SDOperand> Ops; 02482 Ops.push_back(Op1); 02483 Ops.push_back(Op2); 02484 Ops.push_back(Op3); 02485 Ops.push_back(Op4); 02486 Ops.push_back(Op5); 02487 Ops.push_back(Op6); 02488 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02489 } 02490 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02491 MVT::ValueType VT2, MVT::ValueType VT3, 02492 SDOperand Op1, SDOperand Op2, 02493 SDOperand Op3, SDOperand Op4, SDOperand Op5, 02494 SDOperand Op6, SDOperand Op7) { 02495 std::vector<MVT::ValueType> ResultTys; 02496 ResultTys.push_back(VT1); 02497 ResultTys.push_back(VT2); 02498 ResultTys.push_back(VT3); 02499 std::vector<SDOperand> Ops; 02500 Ops.push_back(Op1); 02501 Ops.push_back(Op2); 02502 Ops.push_back(Op3); 02503 Ops.push_back(Op4); 02504 Ops.push_back(Op5); 02505 Ops.push_back(Op6); 02506 Ops.push_back(Op7); 02507 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02508 } 02509 SDNode *SelectionDAG::getTargetNode(unsigned Opcode, MVT::ValueType VT1, 02510 MVT::ValueType VT2, std::vector<SDOperand> &Ops) { 02511 std::vector<MVT::ValueType> ResultTys; 02512 ResultTys.push_back(VT1); 02513 ResultTys.push_back(VT2); 02514 return getNode(ISD::BUILTIN_OP_END+Opcode, ResultTys, Ops).Val; 02515 } 02516 02517 // ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 02518 /// This can cause recursive merging of nodes in the DAG. 02519 /// 02520 /// This version assumes From/To have a single result value. 02521 /// 02522 void SelectionDAG::ReplaceAllUsesWith(SDOperand FromN, SDOperand ToN, 02523 std::vector<SDNode*> *Deleted) { 02524 SDNode *From = FromN.Val, *To = ToN.Val; 02525 assert(From->getNumValues() == 1 && To->getNumValues() == 1 && 02526 "Cannot replace with this method!"); 02527 assert(From != To && "Cannot replace uses of with self"); 02528 02529 while (!From->use_empty()) { 02530 // Process users until they are all gone. 02531 SDNode *U = *From->use_begin(); 02532 02533 // This node is about to morph, remove its old self from the CSE maps. 02534 RemoveNodeFromCSEMaps(U); 02535 02536 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 02537 I != E; ++I) 02538 if (I->Val == From) { 02539 From->removeUser(U); 02540 I->Val = To; 02541 To->addUser(U); 02542 } 02543 02544 // Now that we have modified U, add it back to the CSE maps. If it already 02545 // exists there, recursively merge the results together. 02546 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 02547 ReplaceAllUsesWith(U, Existing, Deleted); 02548 // U is now dead. 02549 if (Deleted) Deleted->push_back(U); 02550 DeleteNodeNotInCSEMaps(U); 02551 } 02552 } 02553 } 02554 02555 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 02556 /// This can cause recursive merging of nodes in the DAG. 02557 /// 02558 /// This version assumes From/To have matching types and numbers of result 02559 /// values. 02560 /// 02561 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, SDNode *To, 02562 std::vector<SDNode*> *Deleted) { 02563 assert(From != To && "Cannot replace uses of with self"); 02564 assert(From->getNumValues() == To->getNumValues() && 02565 "Cannot use this version of ReplaceAllUsesWith!"); 02566 if (From->getNumValues() == 1) { // If possible, use the faster version. 02567 ReplaceAllUsesWith(SDOperand(From, 0), SDOperand(To, 0), Deleted); 02568 return; 02569 } 02570 02571 while (!From->use_empty()) { 02572 // Process users until they are all gone. 02573 SDNode *U = *From->use_begin(); 02574 02575 // This node is about to morph, remove its old self from the CSE maps. 02576 RemoveNodeFromCSEMaps(U); 02577 02578 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 02579 I != E; ++I) 02580 if (I->Val == From) { 02581 From->removeUser(U); 02582 I->Val = To; 02583 To->addUser(U); 02584 } 02585 02586 // Now that we have modified U, add it back to the CSE maps. If it already 02587 // exists there, recursively merge the results together. 02588 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 02589 ReplaceAllUsesWith(U, Existing, Deleted); 02590 // U is now dead. 02591 if (Deleted) Deleted->push_back(U); 02592 DeleteNodeNotInCSEMaps(U); 02593 } 02594 } 02595 } 02596 02597 /// ReplaceAllUsesWith - Modify anything using 'From' to use 'To' instead. 02598 /// This can cause recursive merging of nodes in the DAG. 02599 /// 02600 /// This version can replace From with any result values. To must match the 02601 /// number and types of values returned by From. 02602 void SelectionDAG::ReplaceAllUsesWith(SDNode *From, 02603 const std::vector<SDOperand> &To, 02604 std::vector<SDNode*> *Deleted) { 02605 assert(From->getNumValues() == To.size() && 02606 "Incorrect number of values to replace with!"); 02607 if (To.size() == 1 && To[0].Val->getNumValues() == 1) { 02608 // Degenerate case handled above. 02609 ReplaceAllUsesWith(SDOperand(From, 0), To[0], Deleted); 02610 return; 02611 } 02612 02613 while (!From->use_empty()) { 02614 // Process users until they are all gone. 02615 SDNode *U = *From->use_begin(); 02616 02617 // This node is about to morph, remove its old self from the CSE maps. 02618 RemoveNodeFromCSEMaps(U); 02619 02620 for (SDOperand *I = U->OperandList, *E = U->OperandList+U->NumOperands; 02621 I != E; ++I) 02622 if (I->Val == From) { 02623 const SDOperand &ToOp = To[I->ResNo]; 02624 From->removeUser(U); 02625 *I = ToOp; 02626 ToOp.Val->addUser(U); 02627 } 02628 02629 // Now that we have modified U, add it back to the CSE maps. If it already 02630 // exists there, recursively merge the results together. 02631 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(U)) { 02632 ReplaceAllUsesWith(U, Existing, Deleted); 02633 // U is now dead. 02634 if (Deleted) Deleted->push_back(U); 02635 DeleteNodeNotInCSEMaps(U); 02636 } 02637 } 02638 } 02639 02640 /// ReplaceAllUsesOfValueWith - Replace any uses of From with To, leaving 02641 /// uses of other values produced by From.Val alone. The Deleted vector is 02642 /// handled the same was as for ReplaceAllUsesWith. 02643 void SelectionDAG::ReplaceAllUsesOfValueWith(SDOperand From, SDOperand To, 02644 std::vector<SDNode*> &Deleted) { 02645 assert(From != To && "Cannot replace a value with itself"); 02646 // Handle the simple, trivial, case efficiently. 02647 if (From.Val->getNumValues() == 1 && To.Val->getNumValues() == 1) { 02648 ReplaceAllUsesWith(From, To, &Deleted); 02649 return; 02650 } 02651 02652 // Get all of the users in a nice, deterministically ordered, uniqued set. 02653 SetVector<SDNode*> Users(From.Val->use_begin(), From.Val->use_end()); 02654 02655 while (!Users.empty()) { 02656 // We know that this user uses some value of From. If it is the right 02657 // value, update it. 02658 SDNode *User = Users.back(); 02659 Users.pop_back(); 02660 02661 for (SDOperand *Op = User->OperandList, 02662 *E = User->OperandList+User->NumOperands; Op != E; ++Op) { 02663 if (*Op == From) { 02664 // Okay, we know this user needs to be updated. Remove its old self 02665 // from the CSE maps. 02666 RemoveNodeFromCSEMaps(User); 02667 02668 // Update all operands that match "From". 02669 for (; Op != E; ++Op) { 02670 if (*Op == From) { 02671 From.Val->removeUser(User); 02672 *Op = To; 02673 To.Val->addUser(User); 02674 } 02675 } 02676 02677 // Now that we have modified User, add it back to the CSE maps. If it 02678 // already exists there, recursively merge the results together. 02679 if (SDNode *Existing = AddNonLeafNodeToCSEMaps(User)) { 02680 unsigned NumDeleted = Deleted.size(); 02681 ReplaceAllUsesWith(User, Existing, &Deleted); 02682 02683 // User is now dead. 02684 Deleted.push_back(User); 02685 DeleteNodeNotInCSEMaps(User); 02686 02687 // We have to be careful here, because ReplaceAllUsesWith could have 02688 // deleted a user of From, which means there may be dangling pointers 02689 // in the "Users" setvector. Scan over the deleted node pointers and 02690 // remove them from the setvector. 02691 for (unsigned i = NumDeleted, e = Deleted.size(); i != e; ++i) 02692 Users.remove(Deleted[i]); 02693 } 02694 break; // Exit the operand scanning loop. 02695 } 02696 } 02697 } 02698 } 02699 02700 02701 //===----------------------------------------------------------------------===// 02702 // SDNode Class 02703 //===----------------------------------------------------------------------===// 02704 02705 // Out-of-line virtual method to give class a home. 02706 void SDNode::ANCHOR() { 02707 } 02708 02709 02710 /// getValueTypeList - Return a pointer to the specified value type. 02711 /// 02712 MVT::ValueType *SDNode::getValueTypeList(MVT::ValueType VT) { 02713 static MVT::ValueType VTs[MVT::LAST_VALUETYPE]; 02714 VTs[VT] = VT; 02715 return &VTs[VT]; 02716 } 02717 02718 /// hasNUsesOfValue - Return true if there are exactly NUSES uses of the 02719 /// indicated value. This method ignores uses of other values defined by this 02720 /// operation. 02721 bool SDNode::hasNUsesOfValue(unsigned NUses, unsigned Value) const { 02722 assert(Value < getNumValues() && "Bad value!"); 02723 02724 // If there is only one value, this is easy. 02725 if (getNumValues() == 1) 02726 return use_size() == NUses; 02727 if (Uses.size() < NUses) return false; 02728 02729 SDOperand TheValue(const_cast<SDNode *>(this), Value); 02730 02731 std::set<SDNode*> UsersHandled; 02732 02733 for (std::vector<SDNode*>::const_iterator UI = Uses.begin(), E = Uses.end(); 02734 UI != E; ++UI) { 02735 SDNode *User = *UI; 02736 if (User->getNumOperands() == 1 || 02737 UsersHandled.insert(User).second) // First time we've seen this? 02738 for (unsigned i = 0, e = User->getNumOperands(); i != e; ++i) 02739 if (User->getOperand(i) == TheValue) { 02740 if (NUses == 0) 02741 return false; // too many uses 02742 --NUses; 02743 } 02744 } 02745 02746 // Found exactly the right number of uses? 02747 return NUses == 0; 02748 } 02749 02750 02751 // isOnlyUse - Return true if this node is the only use of N. 02752 bool SDNode::isOnlyUse(SDNode *N) const { 02753 bool Seen = false; 02754 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 02755 SDNode *User = *I; 02756 if (User == this) 02757 Seen = true; 02758 else 02759 return false; 02760 } 02761 02762 return Seen; 02763 } 02764 02765 // isOperand - Return true if this node is an operand of N. 02766 bool SDOperand::isOperand(SDNode *N) const { 02767 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 02768 if (*this == N->getOperand(i)) 02769 return true; 02770 return false; 02771 } 02772 02773 bool SDNode::isOperand(SDNode *N) const { 02774 for (unsigned i = 0, e = N->NumOperands; i != e; ++i) 02775 if (this == N->OperandList[i].Val) 02776 return true; 02777 return false; 02778 } 02779 02780 const char *SDNode::getOperationName(const SelectionDAG *G) const { 02781 switch (getOpcode()) { 02782 default: 02783 if (getOpcode() < ISD::BUILTIN_OP_END) 02784 return "<<Unknown DAG Node>>"; 02785 else { 02786 if (G) { 02787 if (const TargetInstrInfo *TII = G->getTarget().getInstrInfo()) 02788 if (getOpcode()-ISD::BUILTIN_OP_END < TII->getNumOpcodes()) 02789 return TII->getName(getOpcode()-ISD::BUILTIN_OP_END); 02790 02791 TargetLowering &TLI = G->getTargetLoweringInfo(); 02792 const char *Name = 02793 TLI.getTargetNodeName(getOpcode()); 02794 if (Name) return Name; 02795 } 02796 02797 return "<<Unknown Target Node>>"; 02798 } 02799 02800 case ISD::PCMARKER: return "PCMarker"; 02801 case ISD::READCYCLECOUNTER: return "ReadCycleCounter"; 02802 case ISD::SRCVALUE: return "SrcValue"; 02803 case ISD::EntryToken: return "EntryToken"; 02804 case ISD::TokenFactor: return "TokenFactor"; 02805 case ISD::AssertSext: return "AssertSext"; 02806 case ISD::AssertZext: return "AssertZext"; 02807 02808 case ISD::STRING: return "String"; 02809 case ISD::BasicBlock: return "BasicBlock"; 02810 case ISD::VALUETYPE: return "ValueType"; 02811 case ISD::Register: return "Register"; 02812 02813 case ISD::Constant: return "Constant"; 02814 case ISD::ConstantFP: return "ConstantFP"; 02815 case ISD::GlobalAddress: return "GlobalAddress"; 02816 case ISD::FrameIndex: return "FrameIndex"; 02817 case ISD::JumpTable: return "JumpTable"; 02818 case ISD::ConstantPool: return "ConstantPool"; 02819 case ISD::ExternalSymbol: return "ExternalSymbol"; 02820 case ISD::INTRINSIC_WO_CHAIN: { 02821 unsigned IID = cast<ConstantSDNode>(getOperand(0))->getValue(); 02822 return Intrinsic::getName((Intrinsic::ID)IID); 02823 } 02824 case ISD::INTRINSIC_VOID: 02825 case ISD::INTRINSIC_W_CHAIN: { 02826 unsigned IID = cast<ConstantSDNode>(getOperand(1))->getValue(); 02827 return Intrinsic::getName((Intrinsic::ID)IID); 02828 } 02829 02830 case ISD::BUILD_VECTOR: return "BUILD_VECTOR"; 02831 case ISD::TargetConstant: return "TargetConstant"; 02832 case ISD::TargetConstantFP:return "TargetConstantFP"; 02833 case ISD::TargetGlobalAddress: return "TargetGlobalAddress"; 02834 case ISD::TargetFrameIndex: return "TargetFrameIndex"; 02835 case ISD::TargetJumpTable: return "TargetJumpTable"; 02836 case ISD::TargetConstantPool: return "TargetConstantPool"; 02837 case ISD::TargetExternalSymbol: return "TargetExternalSymbol"; 02838 02839 case ISD::CopyToReg: return "CopyToReg"; 02840 case ISD::CopyFromReg: return "CopyFromReg"; 02841 case ISD::UNDEF: return "undef"; 02842 case ISD::MERGE_VALUES: return "mergevalues"; 02843 case ISD::INLINEASM: return "inlineasm"; 02844 case ISD::HANDLENODE: return "handlenode"; 02845 case ISD::FORMAL_ARGUMENTS: return "formal_arguments"; 02846 case ISD::CALL: return "call"; 02847 02848 // Unary operators 02849 case ISD::FABS: return "fabs"; 02850 case ISD::FNEG: return "fneg"; 02851 case ISD::FSQRT: return "fsqrt"; 02852 case ISD::FSIN: return "fsin"; 02853 case ISD::FCOS: return "fcos"; 02854 02855 // Binary operators 02856 case ISD::ADD: return "add"; 02857 case ISD::SUB: return "sub"; 02858 case ISD::MUL: return "mul"; 02859 case ISD::MULHU: return "mulhu"; 02860 case ISD::MULHS: return "mulhs"; 02861 case ISD::SDIV: return "sdiv"; 02862 case ISD::UDIV: return "udiv"; 02863 case ISD::SREM: return "srem"; 02864 case ISD::UREM: return "urem"; 02865 case ISD::AND: return "and"; 02866 case ISD::OR: return "or"; 02867 case ISD::XOR: return "xor"; 02868 case ISD::SHL: return "shl"; 02869 case ISD::SRA: return "sra"; 02870 case ISD::SRL: return "srl"; 02871 case ISD::ROTL: return "rotl"; 02872 case ISD::ROTR: return "rotr"; 02873 case ISD::FADD: return "fadd"; 02874 case ISD::FSUB: return "fsub"; 02875 case ISD::FMUL: return "fmul"; 02876 case ISD::FDIV: return "fdiv"; 02877 case ISD::FREM: return "frem"; 02878 case ISD::FCOPYSIGN: return "fcopysign"; 02879 case ISD::VADD: return "vadd"; 02880 case ISD::VSUB: return "vsub"; 02881 case ISD::VMUL: return "vmul"; 02882 case ISD::VSDIV: return "vsdiv"; 02883 case ISD::VUDIV: return "vudiv"; 02884 case ISD::VAND: return "vand"; 02885 case ISD::VOR: return "vor"; 02886 case ISD::VXOR: return "vxor"; 02887 02888 case ISD::SETCC: return "setcc"; 02889 case ISD::SELECT: return "select"; 02890 case ISD::SELECT_CC: return "select_cc"; 02891 case ISD::VSELECT: return "vselect"; 02892 case ISD::INSERT_VECTOR_ELT: return "insert_vector_elt"; 02893 case ISD::VINSERT_VECTOR_ELT: return "vinsert_vector_elt"; 02894 case ISD::EXTRACT_VECTOR_ELT: return "extract_vector_elt"; 02895 case ISD::VEXTRACT_VECTOR_ELT: return "vextract_vector_elt"; 02896 case ISD::SCALAR_TO_VECTOR: return "scalar_to_vector"; 02897 case ISD::VBUILD_VECTOR: return "vbuild_vector"; 02898 case ISD::VECTOR_SHUFFLE: return "vector_shuffle"; 02899 case ISD::VVECTOR_SHUFFLE: return "vvector_shuffle"; 02900 case ISD::VBIT_CONVERT: return "vbit_convert"; 02901 case ISD::ADDC: return "addc"; 02902 case ISD::ADDE: return "adde"; 02903 case ISD::SUBC: return "subc"; 02904 case ISD::SUBE: return "sube"; 02905 case ISD::SHL_PARTS: return "shl_parts"; 02906 case ISD::SRA_PARTS: return "sra_parts"; 02907 case ISD::SRL_PARTS: return "srl_parts"; 02908 02909 // Conversion operators. 02910 case ISD::SIGN_EXTEND: return "sign_extend"; 02911 case ISD::ZERO_EXTEND: return "zero_extend"; 02912 case ISD::ANY_EXTEND: return "any_extend"; 02913 case ISD::SIGN_EXTEND_INREG: return "sign_extend_inreg"; 02914 case ISD::TRUNCATE: return "truncate"; 02915 case ISD::FP_ROUND: return "fp_round"; 02916 case ISD::FP_ROUND_INREG: return "fp_round_inreg"; 02917 case ISD::FP_EXTEND: return "fp_extend"; 02918 02919 case ISD::SINT_TO_FP: return "sint_to_fp"; 02920 case ISD::UINT_TO_FP: return "uint_to_fp"; 02921 case ISD::FP_TO_SINT: return "fp_to_sint"; 02922 case ISD::FP_TO_UINT: return "fp_to_uint"; 02923 case ISD::BIT_CONVERT: return "bit_convert"; 02924 02925 // Control flow instructions 02926 case ISD::BR: return "br"; 02927 case ISD::BRIND: return "brind"; 02928 case ISD::BRCOND: return "brcond"; 02929 case ISD::BR_CC: return "br_cc"; 02930 case ISD::RET: return "ret"; 02931 case ISD::CALLSEQ_START: return "callseq_start"; 02932 case ISD::CALLSEQ_END: return "callseq_end"; 02933 02934 // Other operators 02935 case ISD::LOAD: return "load"; 02936 case ISD::STORE: return "store"; 02937 case ISD::VLOAD: return "vload"; 02938 case ISD::EXTLOAD: return "extload"; 02939 case ISD::SEXTLOAD: return "sextload"; 02940 case ISD::ZEXTLOAD: return "zextload"; 02941 case ISD::TRUNCSTORE: return "truncstore"; 02942 case ISD::VAARG: return "vaarg"; 02943 case ISD::VACOPY: return "vacopy"; 02944 case ISD::VAEND: return "vaend"; 02945 case ISD::VASTART: return "vastart"; 02946 case ISD::DYNAMIC_STACKALLOC: return "dynamic_stackalloc"; 02947 case ISD::EXTRACT_ELEMENT: return "extract_element"; 02948 case ISD::BUILD_PAIR: return "build_pair"; 02949 case ISD::STACKSAVE: return "stacksave"; 02950 case ISD::STACKRESTORE: return "stackrestore"; 02951 02952 // Block memory operations. 02953 case ISD::MEMSET: return "memset"; 02954 case ISD::MEMCPY: return "memcpy"; 02955 case ISD::MEMMOVE: return "memmove"; 02956 02957 // Bit manipulation 02958 case ISD::BSWAP: return "bswap"; 02959 case ISD::CTPOP: return "ctpop"; 02960 case ISD::CTTZ: return "cttz"; 02961 case ISD::CTLZ: return "ctlz"; 02962 02963 // Debug info 02964 case ISD::LOCATION: return "location"; 02965 case ISD::DEBUG_LOC: return "debug_loc"; 02966 case ISD::DEBUG_LABEL: return "debug_label"; 02967 02968 case ISD::CONDCODE: 02969 switch (cast<CondCodeSDNode>(this)->get()) { 02970 default: assert(0 && "Unknown setcc condition!"); 02971 case ISD::SETOEQ: return "setoeq"; 02972 case ISD::SETOGT: return "setogt"; 02973 case ISD::SETOGE: return "setoge"; 02974 case ISD::SETOLT: return "setolt"; 02975 case ISD::SETOLE: return "setole"; 02976 case ISD::SETONE: return "setone"; 02977 02978 case ISD::SETO: return "seto"; 02979 case ISD::SETUO: return "setuo"; 02980 case ISD::SETUEQ: return "setue"; 02981 case ISD::SETUGT: return "setugt"; 02982 case ISD::SETUGE: return "setuge"; 02983 case ISD::SETULT: return "setult"; 02984 case ISD::SETULE: return "setule"; 02985 case ISD::SETUNE: return "setune"; 02986 02987 case ISD::SETEQ: return "seteq"; 02988 case ISD::SETGT: return "setgt"; 02989 case ISD::SETGE: return "setge"; 02990 case ISD::SETLT: return "setlt"; 02991 case ISD::SETLE: return "setle"; 02992 case ISD::SETNE: return "setne"; 02993 } 02994 } 02995 } 02996 02997 void SDNode::dump() const { dump(0); } 02998 void SDNode::dump(const SelectionDAG *G) const { 02999 std::cerr << (void*)this << ": "; 03000 03001 for (unsigned i = 0, e = getNumValues(); i != e; ++i) { 03002 if (i) std::cerr << ","; 03003 if (getValueType(i) == MVT::Other) 03004 std::cerr << "ch"; 03005 else 03006 std::cerr << MVT::getValueTypeString(getValueType(i)); 03007 } 03008 std::cerr << " = " << getOperationName(G); 03009 03010 std::cerr << " "; 03011 for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { 03012 if (i) std::cerr << ", "; 03013 std::cerr << (void*)getOperand(i).Val; 03014 if (unsigned RN = getOperand(i).ResNo) 03015 std::cerr << ":" << RN; 03016 } 03017 03018 if (const ConstantSDNode *CSDN = dyn_cast<ConstantSDNode>(this)) { 03019 std::cerr << "<" << CSDN->getValue() << ">"; 03020 } else if (const ConstantFPSDNode *CSDN = dyn_cast<ConstantFPSDNode>(this)) { 03021 std::cerr << "<" << CSDN->getValue() << ">"; 03022 } else if (const GlobalAddressSDNode *GADN = 03023 dyn_cast<GlobalAddressSDNode>(this)) { 03024 int offset = GADN->getOffset(); 03025 std::cerr << "<"; 03026 WriteAsOperand(std::cerr, GADN->getGlobal()) << ">"; 03027 if (offset > 0) 03028 std::cerr << " + " << offset; 03029 else 03030 std::cerr << " " << offset; 03031 } else if (const FrameIndexSDNode *FIDN = dyn_cast<FrameIndexSDNode>(this)) { 03032 std::cerr << "<" << FIDN->getIndex() << ">"; 03033 } else if (const ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(this)){ 03034 int offset = CP->getOffset(); 03035 std::cerr << "<" << *CP->get() << ">"; 03036 if (offset > 0) 03037 std::cerr << " + " << offset; 03038 else 03039 std::cerr << " " << offset; 03040 } else if (const BasicBlockSDNode *BBDN = dyn_cast<BasicBlockSDNode>(this)) { 03041 std::cerr << "<"; 03042 const Value *LBB = (const Value*)BBDN->getBasicBlock()->getBasicBlock(); 03043 if (LBB) 03044 std::cerr << LBB->getName() << " "; 03045 std::cerr << (const void*)BBDN->getBasicBlock() << ">"; 03046 } else if (const RegisterSDNode *R = dyn_cast<RegisterSDNode>(this)) { 03047 if (G && R->getReg() && MRegisterInfo::isPhysicalRegister(R->getReg())) { 03048 std::cerr << " " <<G->getTarget().getRegisterInfo()->getName(R->getReg()); 03049 } else { 03050 std::cerr << " #" << R->getReg(); 03051 } 03052 } else if (const ExternalSymbolSDNode *ES = 03053 dyn_cast<ExternalSymbolSDNode>(this)) { 03054 std::cerr << "'" << ES->getSymbol() << "'"; 03055 } else if (const SrcValueSDNode *M = dyn_cast<SrcValueSDNode>(this)) { 03056 if (M->getValue()) 03057 std::cerr << "<" << M->getValue() << ":" << M->getOffset() << ">"; 03058 else 03059 std::cerr << "<null:" << M->getOffset() << ">"; 03060 } else if (const VTSDNode *N = dyn_cast<VTSDNode>(this)) { 03061 std::cerr << ":" << getValueTypeString(N->getVT()); 03062 } 03063 } 03064 03065 static void DumpNodes(const SDNode *N, unsigned indent, const SelectionDAG *G) { 03066 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 03067 if (N->getOperand(i).Val->hasOneUse()) 03068 DumpNodes(N->getOperand(i).Val, indent+2, G); 03069 else 03070 std::cerr << "\n" << std::string(indent+2, ' ') 03071 << (void*)N->getOperand(i).Val << ": <multiple use>"; 03072 03073 03074 std::cerr << "\n" << std::string(indent, ' '); 03075 N->dump(G); 03076 } 03077 03078 void SelectionDAG::dump() const { 03079 std::cerr << "SelectionDAG has " << AllNodes.size() << " nodes:"; 03080 std::vector<const SDNode*> Nodes; 03081 for (allnodes_const_iterator I = allnodes_begin(), E = allnodes_end(); 03082 I != E; ++I) 03083 Nodes.push_back(I); 03084 03085 std::sort(Nodes.begin(), Nodes.end()); 03086 03087 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { 03088 if (!Nodes[i]->hasOneUse() && Nodes[i] != getRoot().Val) 03089 DumpNodes(Nodes[i], 2, this); 03090 } 03091 03092 DumpNodes(getRoot().Val, 2, this); 03093 03094 std::cerr << "\n\n"; 03095 } 03096 03097 /// InsertISelMapEntry - A helper function to insert a key / element pair 03098 /// into a SDOperand to SDOperand map. This is added to avoid the map 03099 /// insertion operator from being inlined. 03100 void SelectionDAG::InsertISelMapEntry(std::map<SDOperand, SDOperand> &Map, 03101 SDNode *Key, unsigned KeyResNo, 03102 SDNode *Element, unsigned ElementResNo) { 03103 Map.insert(std::make_pair(SDOperand(Key, KeyResNo), 03104 SDOperand(Element, ElementResNo))); 03105 } 03106 03107 /// InsertInFlightSetEntry - A helper function to insert a SDNode* to a 03108 /// SDNode* set. This is added to avoid the set insertion operator from being 03109 /// inlined. 03110 void SelectionDAG::InsertInFlightSetEntry(std::set<SDNode*> &Set, SDNode *N) { 03111 Set.insert(N); 03112 } 03113 03114 /// RemoveInFlightSetEntry - A helper function to remove a SDNode* from a 03115 /// SDNode* set. This is added to avoid the set removal operator from being 03116 /// inlined. 03117 void SelectionDAG::RemoveInFlightSetEntry(std::set<SDNode*> &Set, SDNode *N) { 03118 Set.erase(N); 03119 }