LLVM API Documentation

Type.cpp

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