LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 <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