LLVM API Documentation
00001 //===-- Type.cpp - Implement the Type class -------------------------------===// 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 file implements the Type class for the VMCore library. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/AbstractTypeUser.h" 00015 #include "llvm/DerivedTypes.h" 00016 #include "llvm/SymbolTable.h" 00017 #include "llvm/Constants.h" 00018 #include "llvm/ADT/DepthFirstIterator.h" 00019 #include "llvm/ADT/StringExtras.h" 00020 #include "llvm/ADT/SCCIterator.h" 00021 #include "llvm/ADT/STLExtras.h" 00022 #include <algorithm> 00023 #include <iostream> 00024 using namespace llvm; 00025 00026 // DEBUG_MERGE_TYPES - Enable this #define to see how and when derived types are 00027 // created and later destroyed, all in an effort to make sure that there is only 00028 // a single canonical version of a type. 00029 // 00030 //#define DEBUG_MERGE_TYPES 1 00031 00032 AbstractTypeUser::~AbstractTypeUser() {} 00033 00034 //===----------------------------------------------------------------------===// 00035 // Type Class Implementation 00036 //===----------------------------------------------------------------------===// 00037 00038 // Concrete/Abstract TypeDescriptions - We lazily calculate type descriptions 00039 // for types as they are needed. Because resolution of types must invalidate 00040 // all of the abstract type descriptions, we keep them in a seperate map to make 00041 // this easy. 00042 static std::map<const Type*, std::string> ConcreteTypeDescriptions; 00043 static std::map<const Type*, std::string> AbstractTypeDescriptions; 00044 00045 Type::Type( const std::string& name, TypeID id ) 00046 : RefCount(0), ForwardType(0) { 00047 if (!name.empty()) 00048 ConcreteTypeDescriptions[this] = name; 00049 ID = id; 00050 Abstract = false; 00051 } 00052 00053 const Type *Type::getPrimitiveType(TypeID IDNumber) { 00054 switch (IDNumber) { 00055 case VoidTyID : return VoidTy; 00056 case BoolTyID : return BoolTy; 00057 case UByteTyID : return UByteTy; 00058 case SByteTyID : return SByteTy; 00059 case UShortTyID: return UShortTy; 00060 case ShortTyID : return ShortTy; 00061 case UIntTyID : return UIntTy; 00062 case IntTyID : return IntTy; 00063 case ULongTyID : return ULongTy; 00064 case LongTyID : return LongTy; 00065 case FloatTyID : return FloatTy; 00066 case DoubleTyID: return DoubleTy; 00067 case LabelTyID : return LabelTy; 00068 default: 00069 return 0; 00070 } 00071 } 00072 00073 // isLosslesslyConvertibleTo - Return true if this type can be converted to 00074 // 'Ty' without any reinterpretation of bits. For example, uint to int. 00075 // 00076 bool Type::isLosslesslyConvertibleTo(const Type *Ty) const { 00077 if (this == Ty) return true; 00078 if ((!isPrimitiveType() && !isa<PointerType>(this)) || 00079 (!isa<PointerType>(Ty) && !Ty->isPrimitiveType())) return false; 00080 00081 if (getTypeID() == Ty->getTypeID()) 00082 return true; // Handles identity cast, and cast of differing pointer types 00083 00084 // Now we know that they are two differing primitive or pointer types 00085 switch (getTypeID()) { 00086 case Type::UByteTyID: return Ty == Type::SByteTy; 00087 case Type::SByteTyID: return Ty == Type::UByteTy; 00088 case Type::UShortTyID: return Ty == Type::ShortTy; 00089 case Type::ShortTyID: return Ty == Type::UShortTy; 00090 case Type::UIntTyID: return Ty == Type::IntTy; 00091 case Type::IntTyID: return Ty == Type::UIntTy; 00092 case Type::ULongTyID: return Ty == Type::LongTy; 00093 case Type::LongTyID: return Ty == Type::ULongTy; 00094 case Type::PointerTyID: return isa<PointerType>(Ty); 00095 default: 00096 return false; // Other types have no identity values 00097 } 00098 } 00099 00100 /// getUnsignedVersion - If this is an integer type, return the unsigned 00101 /// variant of this type. For example int -> uint. 00102 const Type *Type::getUnsignedVersion() const { 00103 switch (getTypeID()) { 00104 default: 00105 assert(isInteger()&&"Type::getUnsignedVersion is only valid for integers!"); 00106 case Type::UByteTyID: 00107 case Type::SByteTyID: return Type::UByteTy; 00108 case Type::UShortTyID: 00109 case Type::ShortTyID: return Type::UShortTy; 00110 case Type::UIntTyID: 00111 case Type::IntTyID: return Type::UIntTy; 00112 case Type::ULongTyID: 00113 case Type::LongTyID: return Type::ULongTy; 00114 } 00115 } 00116 00117 /// getSignedVersion - If this is an integer type, return the signed variant 00118 /// of this type. For example uint -> int. 00119 const Type *Type::getSignedVersion() const { 00120 switch (getTypeID()) { 00121 default: 00122 assert(isInteger() && "Type::getSignedVersion is only valid for integers!"); 00123 case Type::UByteTyID: 00124 case Type::SByteTyID: return Type::SByteTy; 00125 case Type::UShortTyID: 00126 case Type::ShortTyID: return Type::ShortTy; 00127 case Type::UIntTyID: 00128 case Type::IntTyID: return Type::IntTy; 00129 case Type::ULongTyID: 00130 case Type::LongTyID: return Type::LongTy; 00131 } 00132 } 00133 00134 00135 // getPrimitiveSize - Return the basic size of this type if it is a primitive 00136 // type. These are fixed by LLVM and are not target dependent. This will 00137 // return zero if the type does not have a size or is not a primitive type. 00138 // 00139 unsigned Type::getPrimitiveSize() const { 00140 switch (getTypeID()) { 00141 #define HANDLE_PRIM_TYPE(TY,SIZE) case TY##TyID: return SIZE; 00142 #include "llvm/Type.def" 00143 default: return 0; 00144 } 00145 } 00146 00147 /// isSizedDerivedType - Derived types like structures and arrays are sized 00148 /// iff all of the members of the type are sized as well. Since asking for 00149 /// their size is relatively uncommon, move this operation out of line. 00150 bool Type::isSizedDerivedType() const { 00151 if (const ArrayType *ATy = dyn_cast<ArrayType>(this)) 00152 return ATy->getElementType()->isSized(); 00153 00154 if (const PackedType *PTy = dyn_cast<PackedType>(this)) 00155 return PTy->getElementType()->isSized(); 00156 00157 if (!isa<StructType>(this)) return false; 00158 00159 // Okay, our struct is sized if all of the elements are... 00160 for (subtype_iterator I = subtype_begin(), E = subtype_end(); I != E; ++I) 00161 if (!(*I)->isSized()) return false; 00162 00163 return true; 00164 } 00165 00166 /// getForwardedTypeInternal - This method is used to implement the union-find 00167 /// algorithm for when a type is being forwarded to another type. 00168 const Type *Type::getForwardedTypeInternal() const { 00169 assert(ForwardType && "This type is not being forwarded to another type!"); 00170 00171 // Check to see if the forwarded type has been forwarded on. If so, collapse 00172 // the forwarding links. 00173 const Type *RealForwardedType = ForwardType->getForwardedType(); 00174 if (!RealForwardedType) 00175 return ForwardType; // No it's not forwarded again 00176 00177 // Yes, it is forwarded again. First thing, add the reference to the new 00178 // forward type. 00179 if (RealForwardedType->isAbstract()) 00180 cast<DerivedType>(RealForwardedType)->addRef(); 00181 00182 // Now drop the old reference. This could cause ForwardType to get deleted. 00183 cast<DerivedType>(ForwardType)->dropRef(); 00184 00185 // Return the updated type. 00186 ForwardType = RealForwardedType; 00187 return ForwardType; 00188 } 00189 00190 // getTypeDescription - This is a recursive function that walks a type hierarchy 00191 // calculating the description for a type. 00192 // 00193 static std::string getTypeDescription(const Type *Ty, 00194 std::vector<const Type *> &TypeStack) { 00195 if (isa<OpaqueType>(Ty)) { // Base case for the recursion 00196 std::map<const Type*, std::string>::iterator I = 00197 AbstractTypeDescriptions.lower_bound(Ty); 00198 if (I != AbstractTypeDescriptions.end() && I->first == Ty) 00199 return I->second; 00200 std::string Desc = "opaque"; 00201 AbstractTypeDescriptions.insert(std::make_pair(Ty, Desc)); 00202 return Desc; 00203 } 00204 00205 if (!Ty->isAbstract()) { // Base case for the recursion 00206 std::map<const Type*, std::string>::iterator I = 00207 ConcreteTypeDescriptions.find(Ty); 00208 if (I != ConcreteTypeDescriptions.end()) return I->second; 00209 } 00210 00211 // Check to see if the Type is already on the stack... 00212 unsigned Slot = 0, CurSize = TypeStack.size(); 00213 while (Slot < CurSize && TypeStack[Slot] != Ty) ++Slot; // Scan for type 00214 00215 // This is another base case for the recursion. In this case, we know 00216 // that we have looped back to a type that we have previously visited. 00217 // Generate the appropriate upreference to handle this. 00218 // 00219 if (Slot < CurSize) 00220 return "\\" + utostr(CurSize-Slot); // Here's the upreference 00221 00222 // Recursive case: derived types... 00223 std::string Result; 00224 TypeStack.push_back(Ty); // Add us to the stack.. 00225 00226 switch (Ty->getTypeID()) { 00227 case Type::FunctionTyID: { 00228 const FunctionType *FTy = cast<FunctionType>(Ty); 00229 Result = getTypeDescription(FTy->getReturnType(), TypeStack) + " ("; 00230 for (FunctionType::param_iterator I = FTy->param_begin(), 00231 E = FTy->param_end(); I != E; ++I) { 00232 if (I != FTy->param_begin()) 00233 Result += ", "; 00234 Result += getTypeDescription(*I, TypeStack); 00235 } 00236 if (FTy->isVarArg()) { 00237 if (FTy->getNumParams()) Result += ", "; 00238 Result += "..."; 00239 } 00240 Result += ")"; 00241 break; 00242 } 00243 case Type::StructTyID: { 00244 const StructType *STy = cast<StructType>(Ty); 00245 Result = "{ "; 00246 for (StructType::element_iterator I = STy->element_begin(), 00247 E = STy->element_end(); I != E; ++I) { 00248 if (I != STy->element_begin()) 00249 Result += ", "; 00250 Result += getTypeDescription(*I, TypeStack); 00251 } 00252 Result += " }"; 00253 break; 00254 } 00255 case Type::PointerTyID: { 00256 const PointerType *PTy = cast<PointerType>(Ty); 00257 Result = getTypeDescription(PTy->getElementType(), TypeStack) + " *"; 00258 break; 00259 } 00260 case Type::ArrayTyID: { 00261 const ArrayType *ATy = cast<ArrayType>(Ty); 00262 unsigned NumElements = ATy->getNumElements(); 00263 Result = "["; 00264 Result += utostr(NumElements) + " x "; 00265 Result += getTypeDescription(ATy->getElementType(), TypeStack) + "]"; 00266 break; 00267 } 00268 case Type::PackedTyID: { 00269 const PackedType *PTy = cast<PackedType>(Ty); 00270 unsigned NumElements = PTy->getNumElements(); 00271 Result = "<"; 00272 Result += utostr(NumElements) + " x "; 00273 Result += getTypeDescription(PTy->getElementType(), TypeStack) + ">"; 00274 break; 00275 } 00276 default: 00277 Result = "<error>"; 00278 assert(0 && "Unhandled type in getTypeDescription!"); 00279 } 00280 00281 TypeStack.pop_back(); // Remove self from stack... 00282 00283 return Result; 00284 } 00285 00286 00287 00288 static const std::string &getOrCreateDesc(std::map<const Type*,std::string>&Map, 00289 const Type *Ty) { 00290 std::map<const Type*, std::string>::iterator I = Map.find(Ty); 00291 if (I != Map.end()) return I->second; 00292 00293 std::vector<const Type *> TypeStack; 00294 return Map[Ty] = getTypeDescription(Ty, TypeStack); 00295 } 00296 00297 00298 const std::string &Type::getDescription() const { 00299 if (isAbstract()) 00300 return getOrCreateDesc(AbstractTypeDescriptions, this); 00301 else 00302 return getOrCreateDesc(ConcreteTypeDescriptions, this); 00303 } 00304 00305 00306 bool StructType::indexValid(const Value *V) const { 00307 // Structure indexes require unsigned integer constants. 00308 if (V->getType() == Type::UIntTy) 00309 if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(V)) 00310 return CU->getValue() < ContainedTys.size(); 00311 return false; 00312 } 00313 00314 // getTypeAtIndex - Given an index value into the type, return the type of the 00315 // element. For a structure type, this must be a constant value... 00316 // 00317 const Type *StructType::getTypeAtIndex(const Value *V) const { 00318 assert(indexValid(V) && "Invalid structure index!"); 00319 unsigned Idx = (unsigned)cast<ConstantUInt>(V)->getValue(); 00320 return ContainedTys[Idx]; 00321 } 00322 00323 00324 //===----------------------------------------------------------------------===// 00325 // Static 'Type' data 00326 //===----------------------------------------------------------------------===// 00327 00328 namespace { 00329 struct PrimType : public Type { 00330 PrimType(const char *S, TypeID ID) : Type(S, ID) {} 00331 }; 00332 } 00333 00334 static PrimType TheVoidTy ("void" , Type::VoidTyID); 00335 static PrimType TheBoolTy ("bool" , Type::BoolTyID); 00336 static PrimType TheSByteTy ("sbyte" , Type::SByteTyID); 00337 static PrimType TheUByteTy ("ubyte" , Type::UByteTyID); 00338 static PrimType TheShortTy ("short" , Type::ShortTyID); 00339 static PrimType TheUShortTy("ushort", Type::UShortTyID); 00340 static PrimType TheIntTy ("int" , Type::IntTyID); 00341 static PrimType TheUIntTy ("uint" , Type::UIntTyID); 00342 static PrimType TheLongTy ("long" , Type::LongTyID); 00343 static PrimType TheULongTy ("ulong" , Type::ULongTyID); 00344 static PrimType TheFloatTy ("float" , Type::FloatTyID); 00345 static PrimType TheDoubleTy("double", Type::DoubleTyID); 00346 static PrimType TheLabelTy ("label" , Type::LabelTyID); 00347 00348 Type *Type::VoidTy = &TheVoidTy; 00349 Type *Type::BoolTy = &TheBoolTy; 00350 Type *Type::SByteTy = &TheSByteTy; 00351 Type *Type::UByteTy = &TheUByteTy; 00352 Type *Type::ShortTy = &TheShortTy; 00353 Type *Type::UShortTy = &TheUShortTy; 00354 Type *Type::IntTy = &TheIntTy; 00355 Type *Type::UIntTy = &TheUIntTy; 00356 Type *Type::LongTy = &TheLongTy; 00357 Type *Type::ULongTy = &TheULongTy; 00358 Type *Type::FloatTy = &TheFloatTy; 00359 Type *Type::DoubleTy = &TheDoubleTy; 00360 Type *Type::LabelTy = &TheLabelTy; 00361 00362 00363 //===----------------------------------------------------------------------===// 00364 // Derived Type Constructors 00365 //===----------------------------------------------------------------------===// 00366 00367 FunctionType::FunctionType(const Type *Result, 00368 const std::vector<const Type*> &Params, 00369 bool IsVarArgs) : DerivedType(FunctionTyID), 00370 isVarArgs(IsVarArgs) { 00371 assert((Result->isFirstClassType() || Result == Type::VoidTy || 00372 isa<OpaqueType>(Result)) && 00373 "LLVM functions cannot return aggregates"); 00374 bool isAbstract = Result->isAbstract(); 00375 ContainedTys.reserve(Params.size()+1); 00376 ContainedTys.push_back(PATypeHandle(Result, this)); 00377 00378 for (unsigned i = 0; i != Params.size(); ++i) { 00379 assert((Params[i]->isFirstClassType() || isa<OpaqueType>(Params[i])) && 00380 "Function arguments must be value types!"); 00381 00382 ContainedTys.push_back(PATypeHandle(Params[i], this)); 00383 isAbstract |= Params[i]->isAbstract(); 00384 } 00385 00386 // Calculate whether or not this type is abstract 00387 setAbstract(isAbstract); 00388 } 00389 00390 StructType::StructType(const std::vector<const Type*> &Types) 00391 : CompositeType(StructTyID) { 00392 ContainedTys.reserve(Types.size()); 00393 bool isAbstract = false; 00394 for (unsigned i = 0; i < Types.size(); ++i) { 00395 assert(Types[i] != Type::VoidTy && "Void type for structure field!!"); 00396 ContainedTys.push_back(PATypeHandle(Types[i], this)); 00397 isAbstract |= Types[i]->isAbstract(); 00398 } 00399 00400 // Calculate whether or not this type is abstract 00401 setAbstract(isAbstract); 00402 } 00403 00404 ArrayType::ArrayType(const Type *ElType, unsigned NumEl) 00405 : SequentialType(ArrayTyID, ElType) { 00406 NumElements = NumEl; 00407 00408 // Calculate whether or not this type is abstract 00409 setAbstract(ElType->isAbstract()); 00410 } 00411 00412 PackedType::PackedType(const Type *ElType, unsigned NumEl) 00413 : SequentialType(PackedTyID, ElType) { 00414 NumElements = NumEl; 00415 00416 assert(NumEl > 0 && "NumEl of a PackedType must be greater than 0"); 00417 assert((ElType->isIntegral() || ElType->isFloatingPoint()) && 00418 "Elements of a PackedType must be a primitive type"); 00419 } 00420 00421 00422 PointerType::PointerType(const Type *E) : SequentialType(PointerTyID, E) { 00423 // Calculate whether or not this type is abstract 00424 setAbstract(E->isAbstract()); 00425 } 00426 00427 OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) { 00428 setAbstract(true); 00429 #ifdef DEBUG_MERGE_TYPES 00430 std::cerr << "Derived new type: " << *this << "\n"; 00431 #endif 00432 } 00433 00434 // dropAllTypeUses - When this (abstract) type is resolved to be equal to 00435 // another (more concrete) type, we must eliminate all references to other 00436 // types, to avoid some circular reference problems. 00437 void DerivedType::dropAllTypeUses() { 00438 if (!ContainedTys.empty()) { 00439 while (ContainedTys.size() > 1) 00440 ContainedTys.pop_back(); 00441 00442 // The type must stay abstract. To do this, we insert a pointer to a type 00443 // that will never get resolved, thus will always be abstract. 00444 static Type *AlwaysOpaqueTy = OpaqueType::get(); 00445 static PATypeHolder Holder(AlwaysOpaqueTy); 00446 ContainedTys[0] = AlwaysOpaqueTy; 00447 } 00448 } 00449 00450 00451 00452 /// TypePromotionGraph and graph traits - this is designed to allow us to do 00453 /// efficient SCC processing of type graphs. This is the exact same as 00454 /// GraphTraits<Type*>, except that we pretend that concrete types have no 00455 /// children to avoid processing them. 00456 struct TypePromotionGraph { 00457 Type *Ty; 00458 TypePromotionGraph(Type *T) : Ty(T) {} 00459 }; 00460 00461 namespace llvm { 00462 template <> struct GraphTraits<TypePromotionGraph> { 00463 typedef Type NodeType; 00464 typedef Type::subtype_iterator ChildIteratorType; 00465 00466 static inline NodeType *getEntryNode(TypePromotionGraph G) { return G.Ty; } 00467 static inline ChildIteratorType child_begin(NodeType *N) { 00468 if (N->isAbstract()) 00469 return N->subtype_begin(); 00470 else // No need to process children of concrete types. 00471 return N->subtype_end(); 00472 } 00473 static inline ChildIteratorType child_end(NodeType *N) { 00474 return N->subtype_end(); 00475 } 00476 }; 00477 } 00478 00479 00480 // PromoteAbstractToConcrete - This is a recursive function that walks a type 00481 // graph calculating whether or not a type is abstract. 00482 // 00483 // This method returns true if the type is found to still be abstract. 00484 // 00485 void Type::PromoteAbstractToConcrete() { 00486 if (!isAbstract()) return; 00487 00488 scc_iterator<TypePromotionGraph> SI = scc_begin(TypePromotionGraph(this)); 00489 scc_iterator<TypePromotionGraph> SE = scc_end (TypePromotionGraph(this)); 00490 00491 for (; SI != SE; ++SI) { 00492 std::vector<Type*> &SCC = *SI; 00493 00494 // Concrete types are leaves in the tree. Since an SCC will either be all 00495 // abstract or all concrete, we only need to check one type. 00496 if (SCC[0]->isAbstract()) { 00497 if (isa<OpaqueType>(SCC[0])) 00498 return; // Not going to be concrete, sorry. 00499 00500 // If all of the children of all of the types in this SCC are concrete, 00501 // then this SCC is now concrete as well. If not, neither this SCC, nor 00502 // any parent SCCs will be concrete, so we might as well just exit. 00503 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 00504 for (Type::subtype_iterator CI = SCC[i]->subtype_begin(), 00505 E = SCC[i]->subtype_end(); CI != E; ++CI) 00506 if ((*CI)->isAbstract()) 00507 return; // Not going to be concrete, sorry. 00508 00509 // Okay, we just discovered this whole SCC is now concrete, mark it as 00510 // such! 00511 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 00512 assert(SCC[i]->isAbstract() && "Why are we processing concrete types?"); 00513 00514 SCC[i]->setAbstract(false); 00515 // The type just became concrete, notify all users! 00516 cast<DerivedType>(SCC[i])->notifyUsesThatTypeBecameConcrete(); 00517 } 00518 } 00519 } 00520 } 00521 00522 00523 //===----------------------------------------------------------------------===// 00524 // Type Structural Equality Testing 00525 //===----------------------------------------------------------------------===// 00526 00527 // TypesEqual - Two types are considered structurally equal if they have the 00528 // same "shape": Every level and element of the types have identical primitive 00529 // ID's, and the graphs have the same edges/nodes in them. Nodes do not have to 00530 // be pointer equals to be equivalent though. This uses an optimistic algorithm 00531 // that assumes that two graphs are the same until proven otherwise. 00532 // 00533 static bool TypesEqual(const Type *Ty, const Type *Ty2, 00534 std::map<const Type *, const Type *> &EqTypes) { 00535 if (Ty == Ty2) return true; 00536 if (Ty->getTypeID() != Ty2->getTypeID()) return false; 00537 if (isa<OpaqueType>(Ty)) 00538 return false; // Two unequal opaque types are never equal 00539 00540 std::map<const Type*, const Type*>::iterator It = EqTypes.lower_bound(Ty); 00541 if (It != EqTypes.end() && It->first == Ty) 00542 return It->second == Ty2; // Looping back on a type, check for equality 00543 00544 // Otherwise, add the mapping to the table to make sure we don't get 00545 // recursion on the types... 00546 EqTypes.insert(It, std::make_pair(Ty, Ty2)); 00547 00548 // Two really annoying special cases that breaks an otherwise nice simple 00549 // algorithm is the fact that arraytypes have sizes that differentiates types, 00550 // and that function types can be varargs or not. Consider this now. 00551 // 00552 if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) { 00553 return TypesEqual(PTy->getElementType(), 00554 cast<PointerType>(Ty2)->getElementType(), EqTypes); 00555 } else if (const StructType *STy = dyn_cast<StructType>(Ty)) { 00556 const StructType *STy2 = cast<StructType>(Ty2); 00557 if (STy->getNumElements() != STy2->getNumElements()) return false; 00558 for (unsigned i = 0, e = STy2->getNumElements(); i != e; ++i) 00559 if (!TypesEqual(STy->getElementType(i), STy2->getElementType(i), EqTypes)) 00560 return false; 00561 return true; 00562 } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 00563 const ArrayType *ATy2 = cast<ArrayType>(Ty2); 00564 return ATy->getNumElements() == ATy2->getNumElements() && 00565 TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes); 00566 } else if (const PackedType *PTy = dyn_cast<PackedType>(Ty)) { 00567 const PackedType *PTy2 = cast<PackedType>(Ty2); 00568 return PTy->getNumElements() == PTy2->getNumElements() && 00569 TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes); 00570 } else if (const FunctionType *FTy = dyn_cast<FunctionType>(Ty)) { 00571 const FunctionType *FTy2 = cast<FunctionType>(Ty2); 00572 if (FTy->isVarArg() != FTy2->isVarArg() || 00573 FTy->getNumParams() != FTy2->getNumParams() || 00574 !TypesEqual(FTy->getReturnType(), FTy2->getReturnType(), EqTypes)) 00575 return false; 00576 for (unsigned i = 0, e = FTy2->getNumParams(); i != e; ++i) 00577 if (!TypesEqual(FTy->getParamType(i), FTy2->getParamType(i), EqTypes)) 00578 return false; 00579 return true; 00580 } else { 00581 assert(0 && "Unknown derived type!"); 00582 return false; 00583 } 00584 } 00585 00586 static bool TypesEqual(const Type *Ty, const Type *Ty2) { 00587 std::map<const Type *, const Type *> EqTypes; 00588 return TypesEqual(Ty, Ty2, EqTypes); 00589 } 00590 00591 // AbstractTypeHasCycleThrough - Return true there is a path from CurTy to 00592 // TargetTy in the type graph. We know that Ty is an abstract type, so if we 00593 // ever reach a non-abstract type, we know that we don't need to search the 00594 // subgraph. 00595 static bool AbstractTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, 00596 std::set<const Type*> &VisitedTypes) { 00597 if (TargetTy == CurTy) return true; 00598 if (!CurTy->isAbstract()) return false; 00599 00600 if (!VisitedTypes.insert(CurTy).second) 00601 return false; // Already been here. 00602 00603 for (Type::subtype_iterator I = CurTy->subtype_begin(), 00604 E = CurTy->subtype_end(); I != E; ++I) 00605 if (AbstractTypeHasCycleThrough(TargetTy, *I, VisitedTypes)) 00606 return true; 00607 return false; 00608 } 00609 00610 static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy, 00611 std::set<const Type*> &VisitedTypes) { 00612 if (TargetTy == CurTy) return true; 00613 00614 if (!VisitedTypes.insert(CurTy).second) 00615 return false; // Already been here. 00616 00617 for (Type::subtype_iterator I = CurTy->subtype_begin(), 00618 E = CurTy->subtype_end(); I != E; ++I) 00619 if (ConcreteTypeHasCycleThrough(TargetTy, *I, VisitedTypes)) 00620 return true; 00621 return false; 00622 } 00623 00624 /// TypeHasCycleThroughItself - Return true if the specified type has a cycle 00625 /// back to itself. 00626 static bool TypeHasCycleThroughItself(const Type *Ty) { 00627 std::set<const Type*> VisitedTypes; 00628 00629 if (Ty->isAbstract()) { // Optimized case for abstract types. 00630 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); 00631 I != E; ++I) 00632 if (AbstractTypeHasCycleThrough(Ty, *I, VisitedTypes)) 00633 return true; 00634 } else { 00635 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end(); 00636 I != E; ++I) 00637 if (ConcreteTypeHasCycleThrough(Ty, *I, VisitedTypes)) 00638 return true; 00639 } 00640 return false; 00641 } 00642 00643 00644 //===----------------------------------------------------------------------===// 00645 // Derived Type Factory Functions 00646 //===----------------------------------------------------------------------===// 00647 00648 // TypeMap - Make sure that only one instance of a particular type may be 00649 // created on any given run of the compiler... note that this involves updating 00650 // our map if an abstract type gets refined somehow. 00651 // 00652 namespace llvm { 00653 template<class ValType, class TypeClass> 00654 class TypeMap { 00655 std::map<ValType, PATypeHolder> Map; 00656 00657 /// TypesByHash - Keep track of types by their structure hash value. Note 00658 /// that we only keep track of types that have cycles through themselves in 00659 /// this map. 00660 /// 00661 std::multimap<unsigned, PATypeHolder> TypesByHash; 00662 00663 friend void Type::clearAllTypeMaps(); 00664 00665 private: 00666 void clear(std::vector<Type *> &DerivedTypes) { 00667 for (typename std::map<ValType, PATypeHolder>::iterator I = Map.begin(), 00668 E = Map.end(); I != E; ++I) 00669 DerivedTypes.push_back(I->second.get()); 00670 TypesByHash.clear(); 00671 Map.clear(); 00672 } 00673 public: 00674 typedef typename std::map<ValType, PATypeHolder>::iterator iterator; 00675 ~TypeMap() { print("ON EXIT"); } 00676 00677 inline TypeClass *get(const ValType &V) { 00678 iterator I = Map.find(V); 00679 return I != Map.end() ? cast<TypeClass>((Type*)I->second.get()) : 0; 00680 } 00681 00682 inline void add(const ValType &V, TypeClass *Ty) { 00683 Map.insert(std::make_pair(V, Ty)); 00684 00685 // If this type has a cycle, remember it. 00686 TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty)); 00687 print("add"); 00688 } 00689 00690 void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) { 00691 std::multimap<unsigned, PATypeHolder>::iterator I = 00692 TypesByHash.lower_bound(Hash); 00693 while (I->second != Ty) { 00694 ++I; 00695 assert(I != TypesByHash.end() && I->first == Hash); 00696 } 00697 TypesByHash.erase(I); 00698 } 00699 00700 /// finishRefinement - This method is called after we have updated an existing 00701 /// type with its new components. We must now either merge the type away with 00702 /// some other type or reinstall it in the map with it's new configuration. 00703 /// The specified iterator tells us what the type USED to look like. 00704 void finishRefinement(TypeClass *Ty, const DerivedType *OldType, 00705 const Type *NewType) { 00706 assert((Ty->isAbstract() || !OldType->isAbstract()) && 00707 "Refining a non-abstract type!"); 00708 #ifdef DEBUG_MERGE_TYPES 00709 std::cerr << "refineAbstractTy(" << (void*)OldType << "[" << *OldType 00710 << "], " << (void*)NewType << " [" << *NewType << "])\n"; 00711 #endif 00712 00713 // Make a temporary type holder for the type so that it doesn't disappear on 00714 // us when we erase the entry from the map. 00715 PATypeHolder TyHolder = Ty; 00716 00717 // The old record is now out-of-date, because one of the children has been 00718 // updated. Remove the obsolete entry from the map. 00719 Map.erase(ValType::get(Ty)); 00720 00721 // Remember the structural hash for the type before we start hacking on it, 00722 // in case we need it later. 00723 unsigned OldTypeHash = ValType::hashTypeStructure(Ty); 00724 00725 // Find the type element we are refining... and change it now! 00726 for (unsigned i = 0, e = Ty->ContainedTys.size(); i != e; ++i) 00727 if (Ty->ContainedTys[i] == OldType) { 00728 Ty->ContainedTys[i].removeUserFromConcrete(); 00729 Ty->ContainedTys[i] = NewType; 00730 } 00731 00732 unsigned TypeHash = ValType::hashTypeStructure(Ty); 00733 00734 // If there are no cycles going through this node, we can do a simple, 00735 // efficient lookup in the map, instead of an inefficient nasty linear 00736 // lookup. 00737 if (!Ty->isAbstract() || !TypeHasCycleThroughItself(Ty)) { 00738 typename std::map<ValType, PATypeHolder>::iterator I; 00739 bool Inserted; 00740 00741 ValType V = ValType::get(Ty); 00742 tie(I, Inserted) = Map.insert(std::make_pair(V, Ty)); 00743 if (!Inserted) { 00744 // Refined to a different type altogether? 00745 RemoveFromTypesByHash(TypeHash, Ty); 00746 00747 // We already have this type in the table. Get rid of the newly refined 00748 // type. 00749 TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get()); 00750 Ty->refineAbstractTypeTo(NewTy); 00751 return; 00752 } 00753 00754 } else { 00755 // Now we check to see if there is an existing entry in the table which is 00756 // structurally identical to the newly refined type. If so, this type 00757 // gets refined to the pre-existing type. 00758 // 00759 std::multimap<unsigned, PATypeHolder>::iterator I, E, Entry; 00760 tie(I, E) = TypesByHash.equal_range(OldTypeHash); 00761 Entry = E; 00762 for (; I != E; ++I) { 00763 if (I->second != Ty) { 00764 if (TypesEqual(Ty, I->second)) { 00765 assert(Ty->isAbstract() && "Replacing a non-abstract type?"); 00766 TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get()); 00767 00768 if (Entry == E) { 00769 // Find the location of Ty in the TypesByHash structure. 00770 while (I->second != Ty) { 00771 ++I; 00772 assert(I != E && "Structure doesn't contain type??"); 00773 } 00774 Entry = I; 00775 } 00776 00777 TypesByHash.erase(Entry); 00778 Ty->refineAbstractTypeTo(NewTy); 00779 return; 00780 } 00781 } else { 00782 // Remember the position of 00783 Entry = I; 00784 } 00785 } 00786 00787 00788 // If there is no existing type of the same structure, we reinsert an 00789 // updated record into the map. 00790 Map.insert(std::make_pair(ValType::get(Ty), Ty)); 00791 } 00792 00793 // If the hash codes differ, update TypesByHash 00794 if (TypeHash != OldTypeHash) { 00795 RemoveFromTypesByHash(OldTypeHash, Ty); 00796 TypesByHash.insert(std::make_pair(TypeHash, Ty)); 00797 } 00798 00799 // If the type is currently thought to be abstract, rescan all of our 00800 // subtypes to see if the type has just become concrete! 00801 if (Ty->isAbstract()) 00802 Ty->PromoteAbstractToConcrete(); 00803 } 00804 00805 void print(const char *Arg) const { 00806 #ifdef DEBUG_MERGE_TYPES 00807 std::cerr << "TypeMap<>::" << Arg << " table contents:\n"; 00808 unsigned i = 0; 00809 for (typename std::map<ValType, PATypeHolder>::const_iterator I 00810 = Map.begin(), E = Map.end(); I != E; ++I) 00811 std::cerr << " " << (++i) << ". " << (void*)I->second.get() << " " 00812 << *I->second.get() << "\n"; 00813 #endif 00814 } 00815 00816 void dump() const { print("dump output"); } 00817 }; 00818 } 00819 00820 00821 //===----------------------------------------------------------------------===// 00822 // Function Type Factory and Value Class... 00823 // 00824 00825 // FunctionValType - Define a class to hold the key that goes into the TypeMap 00826 // 00827 namespace llvm { 00828 class FunctionValType { 00829 const Type *RetTy; 00830 std::vector<const Type*> ArgTypes; 00831 bool isVarArg; 00832 public: 00833 FunctionValType(const Type *ret, const std::vector<const Type*> &args, 00834 bool IVA) : RetTy(ret), isVarArg(IVA) { 00835 for (unsigned i = 0; i < args.size(); ++i) 00836 ArgTypes.push_back(args[i]); 00837 } 00838 00839 static FunctionValType get(const FunctionType *FT); 00840 00841 static unsigned hashTypeStructure(const FunctionType *FT) { 00842 return FT->getNumParams()*2+FT->isVarArg(); 00843 } 00844 00845 // Subclass should override this... to update self as usual 00846 void doRefinement(const DerivedType *OldType, const Type *NewType) { 00847 if (RetTy == OldType) RetTy = NewType; 00848 for (unsigned i = 0, e = ArgTypes.size(); i != e; ++i) 00849 if (ArgTypes[i] == OldType) ArgTypes[i] = NewType; 00850 } 00851 00852 inline bool operator<(const FunctionValType &MTV) const { 00853 if (RetTy < MTV.RetTy) return true; 00854 if (RetTy > MTV.RetTy) return false; 00855 00856 if (ArgTypes < MTV.ArgTypes) return true; 00857 return ArgTypes == MTV.ArgTypes && isVarArg < MTV.isVarArg; 00858 } 00859 }; 00860 } 00861 00862 // Define the actual map itself now... 00863 static TypeMap<FunctionValType, FunctionType> FunctionTypes; 00864 00865 FunctionValType FunctionValType::get(const FunctionType *FT) { 00866 // Build up a FunctionValType 00867 std::vector<const Type *> ParamTypes; 00868 ParamTypes.reserve(FT->getNumParams()); 00869 for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i) 00870 ParamTypes.push_back(FT->getParamType(i)); 00871 return FunctionValType(FT->getReturnType(), ParamTypes, FT->isVarArg()); 00872 } 00873 00874 00875 // FunctionType::get - The factory function for the FunctionType class... 00876 FunctionType *FunctionType::get(const Type *ReturnType, 00877 const std::vector<const Type*> &Params, 00878 bool isVarArg) { 00879 FunctionValType VT(ReturnType, Params, isVarArg); 00880 FunctionType *MT = FunctionTypes.get(VT); 00881 if (MT) return MT; 00882 00883 FunctionTypes.add(VT, MT = new FunctionType(ReturnType, Params, isVarArg)); 00884 00885 #ifdef DEBUG_MERGE_TYPES 00886 std::cerr << "Derived new type: " << MT << "\n"; 00887 #endif 00888 return MT; 00889 } 00890 00891 //===----------------------------------------------------------------------===// 00892 // Array Type Factory... 00893 // 00894 namespace llvm { 00895 class ArrayValType { 00896 const Type *ValTy; 00897 unsigned Size; 00898 public: 00899 ArrayValType(const Type *val, int sz) : ValTy(val), Size(sz) {} 00900 00901 static ArrayValType get(const ArrayType *AT) { 00902 return ArrayValType(AT->getElementType(), AT->getNumElements()); 00903 } 00904 00905 static unsigned hashTypeStructure(const ArrayType *AT) { 00906 return AT->getNumElements(); 00907 } 00908 00909 // Subclass should override this... to update self as usual 00910 void doRefinement(const DerivedType *OldType, const Type *NewType) { 00911 assert(ValTy == OldType); 00912 ValTy = NewType; 00913 } 00914 00915 inline bool operator<(const ArrayValType &MTV) const { 00916 if (Size < MTV.Size) return true; 00917 return Size == MTV.Size && ValTy < MTV.ValTy; 00918 } 00919 }; 00920 } 00921 static TypeMap<ArrayValType, ArrayType> ArrayTypes; 00922 00923 00924 ArrayType *ArrayType::get(const Type *ElementType, unsigned NumElements) { 00925 assert(ElementType && "Can't get array of null types!"); 00926 00927 ArrayValType AVT(ElementType, NumElements); 00928 ArrayType *AT = ArrayTypes.get(AVT); 00929 if (AT) return AT; // Found a match, return it! 00930 00931 // Value not found. Derive a new type! 00932 ArrayTypes.add(AVT, AT = new ArrayType(ElementType, NumElements)); 00933 00934 #ifdef DEBUG_MERGE_TYPES 00935 std::cerr << "Derived new type: " << *AT << "\n"; 00936 #endif 00937 return AT; 00938 } 00939 00940 00941 //===----------------------------------------------------------------------===// 00942 // Packed Type Factory... 00943 // 00944 namespace llvm { 00945 class PackedValType { 00946 const Type *ValTy; 00947 unsigned Size; 00948 public: 00949 PackedValType(const Type *val, int sz) : ValTy(val), Size(sz) {} 00950 00951 static PackedValType get(const PackedType *PT) { 00952 return PackedValType(PT->getElementType(), PT->getNumElements()); 00953 } 00954 00955 static unsigned hashTypeStructure(const PackedType *PT) { 00956 return PT->getNumElements(); 00957 } 00958 00959 // Subclass should override this... to update self as usual 00960 void doRefinement(const DerivedType *OldType, const Type *NewType) { 00961 assert(ValTy == OldType); 00962 ValTy = NewType; 00963 } 00964 00965 inline bool operator<(const PackedValType &MTV) const { 00966 if (Size < MTV.Size) return true; 00967 return Size == MTV.Size && ValTy < MTV.ValTy; 00968 } 00969 }; 00970 } 00971 static TypeMap<PackedValType, PackedType> PackedTypes; 00972 00973 00974 PackedType *PackedType::get(const Type *ElementType, unsigned NumElements) { 00975 assert(ElementType && "Can't get packed of null types!"); 00976 00977 PackedValType PVT(ElementType, NumElements); 00978 PackedType *PT = PackedTypes.get(PVT); 00979 if (PT) return PT; // Found a match, return it! 00980 00981 // Value not found. Derive a new type! 00982 PackedTypes.add(PVT, PT = new PackedType(ElementType, NumElements)); 00983 00984 #ifdef DEBUG_MERGE_TYPES 00985 std::cerr << "Derived new type: " << *PT << "\n"; 00986 #endif 00987 return PT; 00988 } 00989 00990 //===----------------------------------------------------------------------===// 00991 // Struct Type Factory... 00992 // 00993 00994 namespace llvm { 00995 // StructValType - Define a class to hold the key that goes into the TypeMap 00996 // 00997 class StructValType { 00998 std::vector<const Type*> ElTypes; 00999 public: 01000 StructValType(const std::vector<const Type*> &args) : ElTypes(args) {} 01001 01002 static StructValType get(const StructType *ST) { 01003 std::vector<const Type *> ElTypes; 01004 ElTypes.reserve(ST->getNumElements()); 01005 for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) 01006 ElTypes.push_back(ST->getElementType(i)); 01007 01008 return StructValType(ElTypes); 01009 } 01010 01011 static unsigned hashTypeStructure(const StructType *ST) { 01012 return ST->getNumElements(); 01013 } 01014 01015 // Subclass should override this... to update self as usual 01016 void doRefinement(const DerivedType *OldType, const Type *NewType) { 01017 for (unsigned i = 0; i < ElTypes.size(); ++i) 01018 if (ElTypes[i] == OldType) ElTypes[i] = NewType; 01019 } 01020 01021 inline bool operator<(const StructValType &STV) const { 01022 return ElTypes < STV.ElTypes; 01023 } 01024 }; 01025 } 01026 01027 static TypeMap<StructValType, StructType> StructTypes; 01028 01029 StructType *StructType::get(const std::vector<const Type*> &ETypes) { 01030 StructValType STV(ETypes); 01031 StructType *ST = StructTypes.get(STV); 01032 if (ST) return ST; 01033 01034 // Value not found. Derive a new type! 01035 StructTypes.add(STV, ST = new StructType(ETypes)); 01036 01037 #ifdef DEBUG_MERGE_TYPES 01038 std::cerr << "Derived new type: " << *ST << "\n"; 01039 #endif 01040 return ST; 01041 } 01042 01043 01044 01045 //===----------------------------------------------------------------------===// 01046 // Pointer Type Factory... 01047 // 01048 01049 // PointerValType - Define a class to hold the key that goes into the TypeMap 01050 // 01051 namespace llvm { 01052 class PointerValType { 01053 const Type *ValTy; 01054 public: 01055 PointerValType(const Type *val) : ValTy(val) {} 01056 01057 static PointerValType get(const PointerType *PT) { 01058 return PointerValType(PT->getElementType()); 01059 } 01060 01061 static unsigned hashTypeStructure(const PointerType *PT) { 01062 return 0; 01063 } 01064 01065 // Subclass should override this... to update self as usual 01066 void doRefinement(const DerivedType *OldType, const Type *NewType) { 01067 assert(ValTy == OldType); 01068 ValTy = NewType; 01069 } 01070 01071 bool operator<(const PointerValType &MTV) const { 01072 return ValTy < MTV.ValTy; 01073 } 01074 }; 01075 } 01076 01077 static TypeMap<PointerValType, PointerType> PointerTypes; 01078 01079 PointerType *PointerType::get(const Type *ValueType) { 01080 assert(ValueType && "Can't get a pointer to <null> type!"); 01081 PointerValType PVT(ValueType); 01082 01083 PointerType *PT = PointerTypes.get(PVT); 01084 if (PT) return PT; 01085 01086 // Value not found. Derive a new type! 01087 PointerTypes.add(PVT, PT = new PointerType(ValueType)); 01088 01089 #ifdef DEBUG_MERGE_TYPES 01090 std::cerr << "Derived new type: " << *PT << "\n"; 01091 #endif 01092 return PT; 01093 } 01094 01095 01096 //===----------------------------------------------------------------------===// 01097 // Derived Type Refinement Functions 01098 //===----------------------------------------------------------------------===// 01099 01100 // removeAbstractTypeUser - Notify an abstract type that a user of the class 01101 // no longer has a handle to the type. This function is called primarily by 01102 // the PATypeHandle class. When there are no users of the abstract type, it 01103 // is annihilated, because there is no way to get a reference to it ever again. 01104 // 01105 void DerivedType::removeAbstractTypeUser(AbstractTypeUser *U) const { 01106 // Search from back to front because we will notify users from back to 01107 // front. Also, it is likely that there will be a stack like behavior to 01108 // users that register and unregister users. 01109 // 01110 unsigned i; 01111 for (i = AbstractTypeUsers.size(); AbstractTypeUsers[i-1] != U; --i) 01112 assert(i != 0 && "AbstractTypeUser not in user list!"); 01113 01114 --i; // Convert to be in range 0 <= i < size() 01115 assert(i < AbstractTypeUsers.size() && "Index out of range!"); // Wraparound? 01116 01117 AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i); 01118 01119 #ifdef DEBUG_MERGE_TYPES 01120 std::cerr << " remAbstractTypeUser[" << (void*)this << ", " 01121 << *this << "][" << i << "] User = " << U << "\n"; 01122 #endif 01123 01124 if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) { 01125 #ifdef DEBUG_MERGE_TYPES 01126 std::cerr << "DELETEing unused abstract type: <" << *this 01127 << ">[" << (void*)this << "]" << "\n"; 01128 #endif 01129 delete this; // No users of this abstract type! 01130 } 01131 } 01132 01133 01134 // refineAbstractTypeTo - This function is used to when it is discovered that 01135 // the 'this' abstract type is actually equivalent to the NewType specified. 01136 // This causes all users of 'this' to switch to reference the more concrete type 01137 // NewType and for 'this' to be deleted. 01138 // 01139 void DerivedType::refineAbstractTypeTo(const Type *NewType) { 01140 assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!"); 01141 assert(this != NewType && "Can't refine to myself!"); 01142 assert(ForwardType == 0 && "This type has already been refined!"); 01143 01144 // The descriptions may be out of date. Conservatively clear them all! 01145 AbstractTypeDescriptions.clear(); 01146 01147 #ifdef DEBUG_MERGE_TYPES 01148 std::cerr << "REFINING abstract type [" << (void*)this << " " 01149 << *this << "] to [" << (void*)NewType << " " 01150 << *NewType << "]!\n"; 01151 #endif 01152 01153 // Make sure to put the type to be refined to into a holder so that if IT gets 01154 // refined, that we will not continue using a dead reference... 01155 // 01156 PATypeHolder NewTy(NewType); 01157 01158 // Any PATypeHolders referring to this type will now automatically forward to 01159 // the type we are resolved to. 01160 ForwardType = NewType; 01161 if (NewType->isAbstract()) 01162 cast<DerivedType>(NewType)->addRef(); 01163 01164 // Add a self use of the current type so that we don't delete ourself until 01165 // after the function exits. 01166 // 01167 PATypeHolder CurrentTy(this); 01168 01169 // To make the situation simpler, we ask the subclass to remove this type from 01170 // the type map, and to replace any type uses with uses of non-abstract types. 01171 // This dramatically limits the amount of recursive type trouble we can find 01172 // ourselves in. 01173 dropAllTypeUses(); 01174 01175 // Iterate over all of the uses of this type, invoking callback. Each user 01176 // should remove itself from our use list automatically. We have to check to 01177 // make sure that NewTy doesn't _become_ 'this'. If it does, resolving types 01178 // will not cause users to drop off of the use list. If we resolve to ourself 01179 // we succeed! 01180 // 01181 while (!AbstractTypeUsers.empty() && NewTy != this) { 01182 AbstractTypeUser *User = AbstractTypeUsers.back(); 01183 01184 unsigned OldSize = AbstractTypeUsers.size(); 01185 #ifdef DEBUG_MERGE_TYPES 01186 std::cerr << " REFINING user " << OldSize-1 << "[" << (void*)User 01187 << "] of abstract type [" << (void*)this << " " 01188 << *this << "] to [" << (void*)NewTy.get() << " " 01189 << *NewTy << "]!\n"; 01190 #endif 01191 User->refineAbstractType(this, NewTy); 01192 01193 assert(AbstractTypeUsers.size() != OldSize && 01194 "AbsTyUser did not remove self from user list!"); 01195 } 01196 01197 // If we were successful removing all users from the type, 'this' will be 01198 // deleted when the last PATypeHolder is destroyed or updated from this type. 01199 // This may occur on exit of this function, as the CurrentTy object is 01200 // destroyed. 01201 } 01202 01203 // notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type that 01204 // the current type has transitioned from being abstract to being concrete. 01205 // 01206 void DerivedType::notifyUsesThatTypeBecameConcrete() { 01207 #ifdef DEBUG_MERGE_TYPES 01208 std::cerr << "typeIsREFINED type: " << (void*)this << " " << *this << "\n"; 01209 #endif 01210 01211 unsigned OldSize = AbstractTypeUsers.size(); 01212 while (!AbstractTypeUsers.empty()) { 01213 AbstractTypeUser *ATU = AbstractTypeUsers.back(); 01214 ATU->typeBecameConcrete(this); 01215 01216 assert(AbstractTypeUsers.size() < OldSize-- && 01217 "AbstractTypeUser did not remove itself from the use list!"); 01218 } 01219 } 01220 01221 01222 01223 01224 // refineAbstractType - Called when a contained type is found to be more 01225 // concrete - this could potentially change us from an abstract type to a 01226 // concrete type. 01227 // 01228 void FunctionType::refineAbstractType(const DerivedType *OldType, 01229 const Type *NewType) { 01230 FunctionTypes.finishRefinement(this, OldType, NewType); 01231 } 01232 01233 void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) { 01234 refineAbstractType(AbsTy, AbsTy); 01235 } 01236 01237 01238 // refineAbstractType - Called when a contained type is found to be more 01239 // concrete - this could potentially change us from an abstract type to a 01240 // concrete type. 01241 // 01242 void ArrayType::refineAbstractType(const DerivedType *OldType, 01243 const Type *NewType) { 01244 ArrayTypes.finishRefinement(this, OldType, NewType); 01245 } 01246 01247 void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) { 01248 refineAbstractType(AbsTy, AbsTy); 01249 } 01250 01251 // refineAbstractType - Called when a contained type is found to be more 01252 // concrete - this could potentially change us from an abstract type to a 01253 // concrete type. 01254 // 01255 void PackedType::refineAbstractType(const DerivedType *OldType, 01256 const Type *NewType) { 01257 PackedTypes.finishRefinement(this, OldType, NewType); 01258 } 01259 01260 void PackedType::typeBecameConcrete(const DerivedType *AbsTy) { 01261 refineAbstractType(AbsTy, AbsTy); 01262 } 01263 01264 // refineAbstractType - Called when a contained type is found to be more 01265 // concrete - this could potentially change us from an abstract type to a 01266 // concrete type. 01267 // 01268 void StructType::refineAbstractType(const DerivedType *OldType, 01269 const Type *NewType) { 01270 StructTypes.finishRefinement(this, OldType, NewType); 01271 } 01272 01273 void StructType::typeBecameConcrete(const DerivedType *AbsTy) { 01274 refineAbstractType(AbsTy, AbsTy); 01275 } 01276 01277 // refineAbstractType - Called when a contained type is found to be more 01278 // concrete - this could potentially change us from an abstract type to a 01279 // concrete type. 01280 // 01281 void PointerType::refineAbstractType(const DerivedType *OldType, 01282 const Type *NewType) { 01283 PointerTypes.finishRefinement(this, OldType, NewType); 01284 } 01285 01286 void PointerType::typeBecameConcrete(const DerivedType *AbsTy) { 01287 refineAbstractType(AbsTy, AbsTy); 01288 } 01289 01290 bool SequentialType::indexValid(const Value *V) const { 01291 const Type *Ty = V->getType(); 01292 switch (Ty->getTypeID()) { 01293 case Type::IntTyID: 01294 case Type::UIntTyID: 01295 case Type::LongTyID: 01296 case Type::ULongTyID: 01297 return true; 01298 default: 01299 return false; 01300 } 01301 } 01302 01303 namespace llvm { 01304 std::ostream &operator<<(std::ostream &OS, const Type *T) { 01305 if (T == 0) 01306 OS << "<null> value!\n"; 01307 else 01308 T->print(OS); 01309 return OS; 01310 } 01311 01312 std::ostream &operator<<(std::ostream &OS, const Type &T) { 01313 T.print(OS); 01314 return OS; 01315 } 01316 } 01317 01318 /// clearAllTypeMaps - This method frees all internal memory used by the 01319 /// type subsystem, which can be used in environments where this memory is 01320 /// otherwise reported as a leak. 01321 void Type::clearAllTypeMaps() { 01322 std::vector<Type *> DerivedTypes; 01323 01324 FunctionTypes.clear(DerivedTypes); 01325 PointerTypes.clear(DerivedTypes); 01326 StructTypes.clear(DerivedTypes); 01327 ArrayTypes.clear(DerivedTypes); 01328 PackedTypes.clear(DerivedTypes); 01329 01330 for(std::vector<Type *>::iterator I = DerivedTypes.begin(), 01331 E = DerivedTypes.end(); I != E; ++I) 01332 (*I)->ContainedTys.clear(); 01333 for(std::vector<Type *>::iterator I = DerivedTypes.begin(), 01334 E = DerivedTypes.end(); I != E; ++I) 01335 delete *I; 01336 DerivedTypes.clear(); 01337 } 01338 01339 // vim: sw=2