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 is distributed under the University of Illinois Open Source
00006 // 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 "LLVMContextImpl.h"
00015 #include "llvm/DerivedTypes.h"
00016 #include "llvm/Constants.h"
00017 #include "llvm/Assembly/Writer.h"
00018 #include "llvm/LLVMContext.h"
00019 #include "llvm/Metadata.h"
00020 #include "llvm/ADT/DepthFirstIterator.h"
00021 #include "llvm/ADT/StringExtras.h"
00022 #include "llvm/ADT/SCCIterator.h"
00023 #include "llvm/ADT/STLExtras.h"
00024 #include "llvm/Support/Compiler.h"
00025 #include "llvm/Support/Debug.h"
00026 #include "llvm/Support/ErrorHandling.h"
00027 #include "llvm/Support/ManagedStatic.h"
00028 #include "llvm/Support/MathExtras.h"
00029 #include "llvm/Support/raw_ostream.h"
00030 #include "llvm/System/Mutex.h"
00031 #include "llvm/System/RWMutex.h"
00032 #include "llvm/System/Threading.h"
00033 #include <algorithm>
00034 #include <cstdarg>
00035 using namespace llvm;
00036 
00037 // DEBUG_MERGE_TYPES - Enable this #define to see how and when derived types are
00038 // created and later destroyed, all in an effort to make sure that there is only
00039 // a single canonical version of a type.
00040 //
00041 // #define DEBUG_MERGE_TYPES 1
00042 
00043 AbstractTypeUser::~AbstractTypeUser() {}
00044 
00045 
00046 //===----------------------------------------------------------------------===//
00047 //                         Type Class Implementation
00048 //===----------------------------------------------------------------------===//
00049 
00050 /// Because of the way Type subclasses are allocated, this function is necessary
00051 /// to use the correct kind of "delete" operator to deallocate the Type object.
00052 /// Some type objects (FunctionTy, StructTy) allocate additional space after 
00053 /// the space for their derived type to hold the contained types array of
00054 /// PATypeHandles. Using this allocation scheme means all the PATypeHandles are
00055 /// allocated with the type object, decreasing allocations and eliminating the
00056 /// need for a std::vector to be used in the Type class itself. 
00057 /// @brief Type destruction function
00058 void Type::destroy() const {
00059 
00060   // Structures and Functions allocate their contained types past the end of
00061   // the type object itself. These need to be destroyed differently than the
00062   // other types.
00063   if (isa<FunctionType>(this) || isa<StructType>(this)) {
00064     // First, make sure we destruct any PATypeHandles allocated by these
00065     // subclasses.  They must be manually destructed. 
00066     for (unsigned i = 0; i < NumContainedTys; ++i)
00067       ContainedTys[i].PATypeHandle::~PATypeHandle();
00068 
00069     // Now call the destructor for the subclass directly because we're going
00070     // to delete this as an array of char.
00071     if (isa<FunctionType>(this))
00072       static_cast<const FunctionType*>(this)->FunctionType::~FunctionType();
00073     else
00074       static_cast<const StructType*>(this)->StructType::~StructType();
00075 
00076     // Finally, remove the memory as an array deallocation of the chars it was
00077     // constructed from.
00078     operator delete(const_cast<Type *>(this));
00079 
00080     return;
00081   }
00082 
00083   // For all the other type subclasses, there is either no contained types or 
00084   // just one (all Sequentials). For Sequentials, the PATypeHandle is not
00085   // allocated past the type object, its included directly in the SequentialType
00086   // class. This means we can safely just do "normal" delete of this object and
00087   // all the destructors that need to run will be run.
00088   delete this; 
00089 }
00090 
00091 const Type *Type::getPrimitiveType(LLVMContext &C, TypeID IDNumber) {
00092   switch (IDNumber) {
00093   case VoidTyID      : return getVoidTy(C);
00094   case FloatTyID     : return getFloatTy(C);
00095   case DoubleTyID    : return getDoubleTy(C);
00096   case X86_FP80TyID  : return getX86_FP80Ty(C);
00097   case FP128TyID     : return getFP128Ty(C);
00098   case PPC_FP128TyID : return getPPC_FP128Ty(C);
00099   case LabelTyID     : return getLabelTy(C);
00100   case MetadataTyID  : return getMetadataTy(C);
00101   default:
00102     return 0;
00103   }
00104 }
00105 
00106 const Type *Type::getVAArgsPromotedType(LLVMContext &C) const {
00107   if (ID == IntegerTyID && getSubclassData() < 32)
00108     return Type::getInt32Ty(C);
00109   else if (ID == FloatTyID)
00110     return Type::getDoubleTy(C);
00111   else
00112     return this;
00113 }
00114 
00115 /// getScalarType - If this is a vector type, return the element type,
00116 /// otherwise return this.
00117 const Type *Type::getScalarType() const {
00118   if (const VectorType *VTy = dyn_cast<VectorType>(this))
00119     return VTy->getElementType();
00120   return this;
00121 }
00122 
00123 /// isIntOrIntVector - Return true if this is an integer type or a vector of
00124 /// integer types.
00125 ///
00126 bool Type::isIntOrIntVector() const {
00127   if (isInteger())
00128     return true;
00129   if (ID != Type::VectorTyID) return false;
00130   
00131   return cast<VectorType>(this)->getElementType()->isInteger();
00132 }
00133 
00134 /// isFPOrFPVector - Return true if this is a FP type or a vector of FP types.
00135 ///
00136 bool Type::isFPOrFPVector() const {
00137   if (ID == Type::FloatTyID || ID == Type::DoubleTyID || 
00138       ID == Type::FP128TyID || ID == Type::X86_FP80TyID || 
00139       ID == Type::PPC_FP128TyID)
00140     return true;
00141   if (ID != Type::VectorTyID) return false;
00142   
00143   return cast<VectorType>(this)->getElementType()->isFloatingPoint();
00144 }
00145 
00146 // canLosslesslyBitCastTo - Return true if this type can be converted to
00147 // 'Ty' without any reinterpretation of bits.  For example, i8* to i32*.
00148 //
00149 bool Type::canLosslesslyBitCastTo(const Type *Ty) const {
00150   // Identity cast means no change so return true
00151   if (this == Ty) 
00152     return true;
00153   
00154   // They are not convertible unless they are at least first class types
00155   if (!this->isFirstClassType() || !Ty->isFirstClassType())
00156     return false;
00157 
00158   // Vector -> Vector conversions are always lossless if the two vector types
00159   // have the same size, otherwise not.
00160   if (const VectorType *thisPTy = dyn_cast<VectorType>(this))
00161     if (const VectorType *thatPTy = dyn_cast<VectorType>(Ty))
00162       return thisPTy->getBitWidth() == thatPTy->getBitWidth();
00163 
00164   // At this point we have only various mismatches of the first class types
00165   // remaining and ptr->ptr. Just select the lossless conversions. Everything
00166   // else is not lossless.
00167   if (isa<PointerType>(this))
00168     return isa<PointerType>(Ty);
00169   return false;  // Other types have no identity values
00170 }
00171 
00172 unsigned Type::getPrimitiveSizeInBits() const {
00173   switch (getTypeID()) {
00174   case Type::FloatTyID: return 32;
00175   case Type::DoubleTyID: return 64;
00176   case Type::X86_FP80TyID: return 80;
00177   case Type::FP128TyID: return 128;
00178   case Type::PPC_FP128TyID: return 128;
00179   case Type::IntegerTyID: return cast<IntegerType>(this)->getBitWidth();
00180   case Type::VectorTyID:  return cast<VectorType>(this)->getBitWidth();
00181   default: return 0;
00182   }
00183 }
00184 
00185 /// getScalarSizeInBits - If this is a vector type, return the
00186 /// getPrimitiveSizeInBits value for the element type. Otherwise return the
00187 /// getPrimitiveSizeInBits value for this type.
00188 unsigned Type::getScalarSizeInBits() const {
00189   return getScalarType()->getPrimitiveSizeInBits();
00190 }
00191 
00192 /// getFPMantissaWidth - Return the width of the mantissa of this type.  This
00193 /// is only valid on floating point types.  If the FP type does not
00194 /// have a stable mantissa (e.g. ppc long double), this method returns -1.
00195 int Type::getFPMantissaWidth() const {
00196   if (const VectorType *VTy = dyn_cast<VectorType>(this))
00197     return VTy->getElementType()->getFPMantissaWidth();
00198   assert(isFloatingPoint() && "Not a floating point type!");
00199   if (ID == FloatTyID) return 24;
00200   if (ID == DoubleTyID) return 53;
00201   if (ID == X86_FP80TyID) return 64;
00202   if (ID == FP128TyID) return 113;
00203   assert(ID == PPC_FP128TyID && "unknown fp type");
00204   return -1;
00205 }
00206 
00207 /// isSizedDerivedType - Derived types like structures and arrays are sized
00208 /// iff all of the members of the type are sized as well.  Since asking for
00209 /// their size is relatively uncommon, move this operation out of line.
00210 bool Type::isSizedDerivedType() const {
00211   if (isa<IntegerType>(this))
00212     return true;
00213 
00214   if (const ArrayType *ATy = dyn_cast<ArrayType>(this))
00215     return ATy->getElementType()->isSized();
00216 
00217   if (const VectorType *PTy = dyn_cast<VectorType>(this))
00218     return PTy->getElementType()->isSized();
00219 
00220   if (!isa<StructType>(this)) 
00221     return false;
00222 
00223   // Okay, our struct is sized if all of the elements are...
00224   for (subtype_iterator I = subtype_begin(), E = subtype_end(); I != E; ++I)
00225     if (!(*I)->isSized()) 
00226       return false;
00227 
00228   return true;
00229 }
00230 
00231 /// getForwardedTypeInternal - This method is used to implement the union-find
00232 /// algorithm for when a type is being forwarded to another type.
00233 const Type *Type::getForwardedTypeInternal() const {
00234   assert(ForwardType && "This type is not being forwarded to another type!");
00235 
00236   // Check to see if the forwarded type has been forwarded on.  If so, collapse
00237   // the forwarding links.
00238   const Type *RealForwardedType = ForwardType->getForwardedType();
00239   if (!RealForwardedType)
00240     return ForwardType;  // No it's not forwarded again
00241 
00242   // Yes, it is forwarded again.  First thing, add the reference to the new
00243   // forward type.
00244   if (RealForwardedType->isAbstract())
00245     cast<DerivedType>(RealForwardedType)->addRef();
00246 
00247   // Now drop the old reference.  This could cause ForwardType to get deleted.
00248   cast<DerivedType>(ForwardType)->dropRef();
00249 
00250   // Return the updated type.
00251   ForwardType = RealForwardedType;
00252   return ForwardType;
00253 }
00254 
00255 void Type::refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
00256   llvm_unreachable("Attempting to refine a derived type!");
00257 }
00258 void Type::typeBecameConcrete(const DerivedType *AbsTy) {
00259   llvm_unreachable("DerivedType is already a concrete type!");
00260 }
00261 
00262 
00263 std::string Type::getDescription() const {
00264   LLVMContextImpl *pImpl = getContext().pImpl;
00265   TypePrinting &Map =
00266     isAbstract() ?
00267       pImpl->AbstractTypeDescriptions :
00268       pImpl->ConcreteTypeDescriptions;
00269   
00270   std::string DescStr;
00271   raw_string_ostream DescOS(DescStr);
00272   Map.print(this, DescOS);
00273   return DescOS.str();
00274 }
00275 
00276 
00277 bool StructType::indexValid(const Value *V) const {
00278   // Structure indexes require 32-bit integer constants.
00279   if (V->getType() == Type::getInt32Ty(V->getContext()))
00280     if (const ConstantInt *CU = dyn_cast<ConstantInt>(V))
00281       return indexValid(CU->getZExtValue());
00282   return false;
00283 }
00284 
00285 bool StructType::indexValid(unsigned V) const {
00286   return V < NumContainedTys;
00287 }
00288 
00289 // getTypeAtIndex - Given an index value into the type, return the type of the
00290 // element.  For a structure type, this must be a constant value...
00291 //
00292 const Type *StructType::getTypeAtIndex(const Value *V) const {
00293   unsigned Idx = (unsigned)cast<ConstantInt>(V)->getZExtValue();
00294   return getTypeAtIndex(Idx);
00295 }
00296 
00297 const Type *StructType::getTypeAtIndex(unsigned Idx) const {
00298   assert(indexValid(Idx) && "Invalid structure index!");
00299   return ContainedTys[Idx];
00300 }
00301 
00302 //===----------------------------------------------------------------------===//
00303 //                          Primitive 'Type' data
00304 //===----------------------------------------------------------------------===//
00305 
00306 const Type *Type::getVoidTy(LLVMContext &C) {
00307   return C.pImpl->VoidTy;
00308 }
00309 
00310 const Type *Type::getLabelTy(LLVMContext &C) {
00311   return C.pImpl->LabelTy;
00312 }
00313 
00314 const Type *Type::getFloatTy(LLVMContext &C) {
00315   return C.pImpl->FloatTy;
00316 }
00317 
00318 const Type *Type::getDoubleTy(LLVMContext &C) {
00319   return C.pImpl->DoubleTy;
00320 }
00321 
00322 const Type *Type::getMetadataTy(LLVMContext &C) {
00323   return C.pImpl->MetadataTy;
00324 }
00325 
00326 const Type *Type::getX86_FP80Ty(LLVMContext &C) {
00327   return C.pImpl->X86_FP80Ty;
00328 }
00329 
00330 const Type *Type::getFP128Ty(LLVMContext &C) {
00331   return C.pImpl->FP128Ty;
00332 }
00333 
00334 const Type *Type::getPPC_FP128Ty(LLVMContext &C) {
00335   return C.pImpl->PPC_FP128Ty;
00336 }
00337 
00338 const IntegerType *Type::getInt1Ty(LLVMContext &C) {
00339   return C.pImpl->Int1Ty;
00340 }
00341 
00342 const IntegerType *Type::getInt8Ty(LLVMContext &C) {
00343   return C.pImpl->Int8Ty;
00344 }
00345 
00346 const IntegerType *Type::getInt16Ty(LLVMContext &C) {
00347   return C.pImpl->Int16Ty;
00348 }
00349 
00350 const IntegerType *Type::getInt32Ty(LLVMContext &C) {
00351   return C.pImpl->Int32Ty;
00352 }
00353 
00354 const IntegerType *Type::getInt64Ty(LLVMContext &C) {
00355   return C.pImpl->Int64Ty;
00356 }
00357 
00358 //===----------------------------------------------------------------------===//
00359 //                          Derived Type Constructors
00360 //===----------------------------------------------------------------------===//
00361 
00362 /// isValidReturnType - Return true if the specified type is valid as a return
00363 /// type.
00364 bool FunctionType::isValidReturnType(const Type *RetTy) {
00365   if (RetTy->isFirstClassType()) {
00366     if (const PointerType *PTy = dyn_cast<PointerType>(RetTy))
00367       return PTy->getElementType() != Type::getMetadataTy(RetTy->getContext());
00368     return true;
00369   }
00370   if (RetTy == Type::getVoidTy(RetTy->getContext()) ||
00371       RetTy == Type::getMetadataTy(RetTy->getContext()) ||
00372       isa<OpaqueType>(RetTy))
00373     return true;
00374   
00375   // If this is a multiple return case, verify that each return is a first class
00376   // value and that there is at least one value.
00377   const StructType *SRetTy = dyn_cast<StructType>(RetTy);
00378   if (SRetTy == 0 || SRetTy->getNumElements() == 0)
00379     return false;
00380   
00381   for (unsigned i = 0, e = SRetTy->getNumElements(); i != e; ++i)
00382     if (!SRetTy->getElementType(i)->isFirstClassType())
00383       return false;
00384   return true;
00385 }
00386 
00387 /// isValidArgumentType - Return true if the specified type is valid as an
00388 /// argument type.
00389 bool FunctionType::isValidArgumentType(const Type *ArgTy) {
00390   if ((!ArgTy->isFirstClassType() && !isa<OpaqueType>(ArgTy)) ||
00391       (isa<PointerType>(ArgTy) &&
00392        cast<PointerType>(ArgTy)->getElementType() == 
00393             Type::getMetadataTy(ArgTy->getContext())))
00394     return false;
00395 
00396   return true;
00397 }
00398 
00399 FunctionType::FunctionType(const Type *Result,
00400                            const std::vector<const Type*> &Params,
00401                            bool IsVarArgs)
00402   : DerivedType(Result->getContext(), FunctionTyID), isVarArgs(IsVarArgs) {
00403   ContainedTys = reinterpret_cast<PATypeHandle*>(this+1);
00404   NumContainedTys = Params.size() + 1; // + 1 for result type
00405   assert(isValidReturnType(Result) && "invalid return type for function");
00406 
00407 
00408   bool isAbstract = Result->isAbstract();
00409   new (&ContainedTys[0]) PATypeHandle(Result, this);
00410 
00411   for (unsigned i = 0; i != Params.size(); ++i) {
00412     assert(isValidArgumentType(Params[i]) &&
00413            "Not a valid type for function argument!");
00414     new (&ContainedTys[i+1]) PATypeHandle(Params[i], this);
00415     isAbstract |= Params[i]->isAbstract();
00416   }
00417 
00418   // Calculate whether or not this type is abstract
00419   setAbstract(isAbstract);
00420 }
00421 
00422 StructType::StructType(LLVMContext &C, 
00423                        const std::vector<const Type*> &Types, bool isPacked)
00424   : CompositeType(C, StructTyID) {
00425   ContainedTys = reinterpret_cast<PATypeHandle*>(this + 1);
00426   NumContainedTys = Types.size();
00427   setSubclassData(isPacked);
00428   bool isAbstract = false;
00429   for (unsigned i = 0; i < Types.size(); ++i) {
00430     assert(Types[i] && "<null> type for structure field!");
00431     assert(isValidElementType(Types[i]) &&
00432            "Invalid type for structure element!");
00433     new (&ContainedTys[i]) PATypeHandle(Types[i], this);
00434     isAbstract |= Types[i]->isAbstract();
00435   }
00436 
00437   // Calculate whether or not this type is abstract
00438   setAbstract(isAbstract);
00439 }
00440 
00441 ArrayType::ArrayType(const Type *ElType, uint64_t NumEl)
00442   : SequentialType(ArrayTyID, ElType) {
00443   NumElements = NumEl;
00444 
00445   // Calculate whether or not this type is abstract
00446   setAbstract(ElType->isAbstract());
00447 }
00448 
00449 VectorType::VectorType(const Type *ElType, unsigned NumEl)
00450   : SequentialType(VectorTyID, ElType) {
00451   NumElements = NumEl;
00452   setAbstract(ElType->isAbstract());
00453   assert(NumEl > 0 && "NumEl of a VectorType must be greater than 0");
00454   assert(isValidElementType(ElType) &&
00455          "Elements of a VectorType must be a primitive type");
00456 
00457 }
00458 
00459 
00460 PointerType::PointerType(const Type *E, unsigned AddrSpace)
00461   : SequentialType(PointerTyID, E) {
00462   AddressSpace = AddrSpace;
00463   // Calculate whether or not this type is abstract
00464   setAbstract(E->isAbstract());
00465 }
00466 
00467 OpaqueType::OpaqueType(LLVMContext &C) : DerivedType(C, OpaqueTyID) {
00468   setAbstract(true);
00469 #ifdef DEBUG_MERGE_TYPES
00470   DOUT << "Derived new type: " << *this << "\n";
00471 #endif
00472 }
00473 
00474 void PATypeHolder::destroy() {
00475   Ty = 0;
00476 }
00477 
00478 // dropAllTypeUses - When this (abstract) type is resolved to be equal to
00479 // another (more concrete) type, we must eliminate all references to other
00480 // types, to avoid some circular reference problems.
00481 void DerivedType::dropAllTypeUses() {
00482   if (NumContainedTys != 0) {
00483     // The type must stay abstract.  To do this, we insert a pointer to a type
00484     // that will never get resolved, thus will always be abstract.
00485     static Type *AlwaysOpaqueTy = 0;
00486     static PATypeHolder* Holder = 0;
00487     Type *tmp = AlwaysOpaqueTy;
00488     if (llvm_is_multithreaded()) {
00489       sys::MemoryFence();
00490       if (!tmp) {
00491         llvm_acquire_global_lock();
00492         tmp = AlwaysOpaqueTy;
00493         if (!tmp) {
00494           tmp = OpaqueType::get(getContext());
00495           PATypeHolder* tmp2 = new PATypeHolder(tmp);
00496           sys::MemoryFence();
00497           AlwaysOpaqueTy = tmp;
00498           Holder = tmp2;
00499         }
00500       
00501         llvm_release_global_lock();
00502       }
00503     } else {
00504       AlwaysOpaqueTy = OpaqueType::get(getContext());
00505       Holder = new PATypeHolder(AlwaysOpaqueTy);
00506     } 
00507         
00508     ContainedTys[0] = AlwaysOpaqueTy;
00509 
00510     // Change the rest of the types to be Int32Ty's.  It doesn't matter what we
00511     // pick so long as it doesn't point back to this type.  We choose something
00512     // concrete to avoid overhead for adding to AbstracTypeUser lists and stuff.
00513     for (unsigned i = 1, e = NumContainedTys; i != e; ++i)
00514       ContainedTys[i] = Type::getInt32Ty(getContext());
00515   }
00516 }
00517 
00518 
00519 namespace {
00520 
00521 /// TypePromotionGraph and graph traits - this is designed to allow us to do
00522 /// efficient SCC processing of type graphs.  This is the exact same as
00523 /// GraphTraits<Type*>, except that we pretend that concrete types have no
00524 /// children to avoid processing them.
00525 struct TypePromotionGraph {
00526   Type *Ty;
00527   TypePromotionGraph(Type *T) : Ty(T) {}
00528 };
00529 
00530 }
00531 
00532 namespace llvm {
00533   template <> struct GraphTraits<TypePromotionGraph> {
00534     typedef Type NodeType;
00535     typedef Type::subtype_iterator ChildIteratorType;
00536 
00537     static inline NodeType *getEntryNode(TypePromotionGraph G) { return G.Ty; }
00538     static inline ChildIteratorType child_begin(NodeType *N) {
00539       if (N->isAbstract())
00540         return N->subtype_begin();
00541       else           // No need to process children of concrete types.
00542         return N->subtype_end();
00543     }
00544     static inline ChildIteratorType child_end(NodeType *N) {
00545       return N->subtype_end();
00546     }
00547   };
00548 }
00549 
00550 
00551 // PromoteAbstractToConcrete - This is a recursive function that walks a type
00552 // graph calculating whether or not a type is abstract.
00553 //
00554 void Type::PromoteAbstractToConcrete() {
00555   if (!isAbstract()) return;
00556 
00557   scc_iterator<TypePromotionGraph> SI = scc_begin(TypePromotionGraph(this));
00558   scc_iterator<TypePromotionGraph> SE = scc_end  (TypePromotionGraph(this));
00559 
00560   for (; SI != SE; ++SI) {
00561     std::vector<Type*> &SCC = *SI;
00562 
00563     // Concrete types are leaves in the tree.  Since an SCC will either be all
00564     // abstract or all concrete, we only need to check one type.
00565     if (SCC[0]->isAbstract()) {
00566       if (isa<OpaqueType>(SCC[0]))
00567         return;     // Not going to be concrete, sorry.
00568 
00569       // If all of the children of all of the types in this SCC are concrete,
00570       // then this SCC is now concrete as well.  If not, neither this SCC, nor
00571       // any parent SCCs will be concrete, so we might as well just exit.
00572       for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00573         for (Type::subtype_iterator CI = SCC[i]->subtype_begin(),
00574                E = SCC[i]->subtype_end(); CI != E; ++CI)
00575           if ((*CI)->isAbstract())
00576             // If the child type is in our SCC, it doesn't make the entire SCC
00577             // abstract unless there is a non-SCC abstract type.
00578             if (std::find(SCC.begin(), SCC.end(), *CI) == SCC.end())
00579               return;               // Not going to be concrete, sorry.
00580 
00581       // Okay, we just discovered this whole SCC is now concrete, mark it as
00582       // such!
00583       for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00584         assert(SCC[i]->isAbstract() && "Why are we processing concrete types?");
00585 
00586         SCC[i]->setAbstract(false);
00587       }
00588 
00589       for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00590         assert(!SCC[i]->isAbstract() && "Concrete type became abstract?");
00591         // The type just became concrete, notify all users!
00592         cast<DerivedType>(SCC[i])->notifyUsesThatTypeBecameConcrete();
00593       }
00594     }
00595   }
00596 }
00597 
00598 
00599 //===----------------------------------------------------------------------===//
00600 //                      Type Structural Equality Testing
00601 //===----------------------------------------------------------------------===//
00602 
00603 // TypesEqual - Two types are considered structurally equal if they have the
00604 // same "shape": Every level and element of the types have identical primitive
00605 // ID's, and the graphs have the same edges/nodes in them.  Nodes do not have to
00606 // be pointer equals to be equivalent though.  This uses an optimistic algorithm
00607 // that assumes that two graphs are the same until proven otherwise.
00608 //
00609 static bool TypesEqual(const Type *Ty, const Type *Ty2,
00610                        std::map<const Type *, const Type *> &EqTypes) {
00611   if (Ty == Ty2) return true;
00612   if (Ty->getTypeID() != Ty2->getTypeID()) return false;
00613   if (isa<OpaqueType>(Ty))
00614     return false;  // Two unequal opaque types are never equal
00615 
00616   std::map<const Type*, const Type*>::iterator It = EqTypes.find(Ty);
00617   if (It != EqTypes.end())
00618     return It->second == Ty2;    // Looping back on a type, check for equality
00619 
00620   // Otherwise, add the mapping to the table to make sure we don't get
00621   // recursion on the types...
00622   EqTypes.insert(It, std::make_pair(Ty, Ty2));
00623 
00624   // Two really annoying special cases that breaks an otherwise nice simple
00625   // algorithm is the fact that arraytypes have sizes that differentiates types,
00626   // and that function types can be varargs or not.  Consider this now.
00627   //
00628   if (const IntegerType *ITy = dyn_cast<IntegerType>(Ty)) {
00629     const IntegerType *ITy2 = cast<IntegerType>(Ty2);
00630     return ITy->getBitWidth() == ITy2->getBitWidth();
00631   } else if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) {
00632     const PointerType *PTy2 = cast<PointerType>(Ty2);
00633     return PTy->getAddressSpace() == PTy2->getAddressSpace() &&
00634            TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
00635   } else if (const StructType *STy = dyn_cast<StructType>(Ty)) {
00636     const StructType *STy2 = cast<StructType>(Ty2);
00637     if (STy->getNumElements() != STy2->getNumElements()) return false;
00638     if (STy->isPacked() != STy2->isPacked()) return false;
00639     for (unsigned i = 0, e = STy2->getNumElements(); i != e; ++i)
00640       if (!TypesEqual(STy->getElementType(i), STy2->getElementType(i), EqTypes))
00641         return false;
00642     return true;
00643   } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
00644     const ArrayType *ATy2 = cast<ArrayType>(Ty2);
00645     return ATy->getNumElements() == ATy2->getNumElements() &&
00646            TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes);
00647   } else if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
00648     const VectorType *PTy2 = cast<VectorType>(Ty2);
00649     return PTy->getNumElements() == PTy2->getNumElements() &&
00650            TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
00651   } else if (const FunctionType *FTy = dyn_cast<FunctionType>(Ty)) {
00652     const FunctionType *FTy2 = cast<FunctionType>(Ty2);
00653     if (FTy->isVarArg() != FTy2->isVarArg() ||
00654         FTy->getNumParams() != FTy2->getNumParams() ||
00655         !TypesEqual(FTy->getReturnType(), FTy2->getReturnType(), EqTypes))
00656       return false;
00657     for (unsigned i = 0, e = FTy2->getNumParams(); i != e; ++i) {
00658       if (!TypesEqual(FTy->getParamType(i), FTy2->getParamType(i), EqTypes))
00659         return false;
00660     }
00661     return true;
00662   } else {
00663     llvm_unreachable("Unknown derived type!");
00664     return false;
00665   }
00666 }
00667 
00668 static bool TypesEqual(const Type *Ty, const Type *Ty2) {
00669   std::map<const Type *, const Type *> EqTypes;
00670   return TypesEqual(Ty, Ty2, EqTypes);
00671 }
00672 
00673 // AbstractTypeHasCycleThrough - Return true there is a path from CurTy to
00674 // TargetTy in the type graph.  We know that Ty is an abstract type, so if we
00675 // ever reach a non-abstract type, we know that we don't need to search the
00676 // subgraph.
00677 static bool AbstractTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
00678                                 SmallPtrSet<const Type*, 128> &VisitedTypes) {
00679   if (TargetTy == CurTy) return true;
00680   if (!CurTy->isAbstract()) return false;
00681 
00682   if (!VisitedTypes.insert(CurTy))
00683     return false;  // Already been here.
00684 
00685   for (Type::subtype_iterator I = CurTy->subtype_begin(),
00686        E = CurTy->subtype_end(); I != E; ++I)
00687     if (AbstractTypeHasCycleThrough(TargetTy, *I, VisitedTypes))
00688       return true;
00689   return false;
00690 }
00691 
00692 static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
00693                                 SmallPtrSet<const Type*, 128> &VisitedTypes) {
00694   if (TargetTy == CurTy) return true;
00695 
00696   if (!VisitedTypes.insert(CurTy))
00697     return false;  // Already been here.
00698 
00699   for (Type::subtype_iterator I = CurTy->subtype_begin(),
00700        E = CurTy->subtype_end(); I != E; ++I)
00701     if (ConcreteTypeHasCycleThrough(TargetTy, *I, VisitedTypes))
00702       return true;
00703   return false;
00704 }
00705 
00706 /// TypeHasCycleThroughItself - Return true if the specified type has a cycle
00707 /// back to itself.
00708 static bool TypeHasCycleThroughItself(const Type *Ty) {
00709   SmallPtrSet<const Type*, 128> VisitedTypes;
00710 
00711   if (Ty->isAbstract()) {  // Optimized case for abstract types.
00712     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
00713          I != E; ++I)
00714       if (AbstractTypeHasCycleThrough(Ty, *I, VisitedTypes))
00715         return true;
00716   } else {
00717     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
00718          I != E; ++I)
00719       if (ConcreteTypeHasCycleThrough(Ty, *I, VisitedTypes))
00720         return true;
00721   }
00722   return false;
00723 }
00724 
00725 //===----------------------------------------------------------------------===//
00726 // Function Type Factory and Value Class...
00727 //
00728 const IntegerType *IntegerType::get(LLVMContext &C, unsigned NumBits) {
00729   assert(NumBits >= MIN_INT_BITS && "bitwidth too small");
00730   assert(NumBits <= MAX_INT_BITS && "bitwidth too large");
00731 
00732   // Check for the built-in integer types
00733   switch (NumBits) {
00734     case  1: return cast<IntegerType>(Type::getInt1Ty(C));
00735     case  8: return cast<IntegerType>(Type::getInt8Ty(C));
00736     case 16: return cast<IntegerType>(Type::getInt16Ty(C));
00737     case 32: return cast<IntegerType>(Type::getInt32Ty(C));
00738     case 64: return cast<IntegerType>(Type::getInt64Ty(C));
00739     default: 
00740       break;
00741   }
00742 
00743   LLVMContextImpl *pImpl = C.pImpl;
00744   
00745   IntegerValType IVT(NumBits);
00746   IntegerType *ITy = 0;
00747   
00748   // First, see if the type is already in the table, for which
00749   // a reader lock suffices.
00750   sys::SmartScopedLock<true> L(pImpl->TypeMapLock);
00751   ITy = pImpl->IntegerTypes.get(IVT);
00752     
00753   if (!ITy) {
00754     // Value not found.  Derive a new type!
00755     ITy = new IntegerType(C, NumBits);
00756     pImpl->IntegerTypes.add(IVT, ITy);
00757   }
00758 #ifdef DEBUG_MERGE_TYPES
00759   DOUT << "Derived new type: " << *ITy << "\n";
00760 #endif
00761   return ITy;
00762 }
00763 
00764 bool IntegerType::isPowerOf2ByteWidth() const {
00765   unsigned BitWidth = getBitWidth();
00766   return (BitWidth > 7) && isPowerOf2_32(BitWidth);
00767 }
00768 
00769 APInt IntegerType::getMask() const {
00770   return APInt::getAllOnesValue(getBitWidth());
00771 }
00772 
00773 FunctionValType FunctionValType::get(const FunctionType *FT) {
00774   // Build up a FunctionValType
00775   std::vector<const Type *> ParamTypes;
00776   ParamTypes.reserve(FT->getNumParams());
00777   for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
00778     ParamTypes.push_back(FT->getParamType(i));
00779   return FunctionValType(FT->getReturnType(), ParamTypes, FT->isVarArg());
00780 }
00781 
00782 
00783 // FunctionType::get - The factory function for the FunctionType class...
00784 FunctionType *FunctionType::get(const Type *ReturnType,
00785                                 const std::vector<const Type*> &Params,
00786                                 bool isVarArg) {
00787   FunctionValType VT(ReturnType, Params, isVarArg);
00788   FunctionType *FT = 0;
00789   
00790   LLVMContextImpl *pImpl = ReturnType->getContext().pImpl;
00791   
00792   sys::SmartScopedLock<true> L(pImpl->TypeMapLock);
00793   FT = pImpl->FunctionTypes.get(VT);
00794   
00795   if (!FT) {
00796     FT = (FunctionType*) operator new(sizeof(FunctionType) +
00797                                     sizeof(PATypeHandle)*(Params.size()+1));
00798     new (FT) FunctionType(ReturnType, Params, isVarArg);
00799     pImpl->FunctionTypes.add(VT, FT);
00800   }
00801 
00802 #ifdef DEBUG_MERGE_TYPES
00803   DOUT << "Derived new type: " << FT << "\n";
00804 #endif
00805   return FT;
00806 }
00807 
00808 ArrayType *ArrayType::get(const Type *ElementType, uint64_t NumElements) {
00809   assert(ElementType && "Can't get array of <null> types!");
00810   assert(isValidElementType(ElementType) && "Invalid type for array element!");
00811 
00812   ArrayValType AVT(ElementType, NumElements);
00813   ArrayType *AT = 0;
00814 
00815   LLVMContextImpl *pImpl = ElementType->getContext().pImpl;
00816   
00817   sys::SmartScopedLock<true> L(pImpl->TypeMapLock);
00818   AT = pImpl->ArrayTypes.get(AVT);
00819       
00820   if (!AT) {
00821     // Value not found.  Derive a new type!
00822     pImpl->ArrayTypes.add(AVT, AT = new ArrayType(ElementType, NumElements));
00823   }
00824 #ifdef DEBUG_MERGE_TYPES
00825   DOUT << "Derived new type: " << *AT << "\n";
00826 #endif
00827   return AT;
00828 }
00829 
00830 bool ArrayType::isValidElementType(const Type *ElemTy) {
00831   if (ElemTy == Type::getVoidTy(ElemTy->getContext()) ||
00832       ElemTy == Type::getLabelTy(ElemTy->getContext()) ||
00833       ElemTy == Type::getMetadataTy(ElemTy->getContext()))
00834     return false;
00835 
00836   if (const PointerType *PTy = dyn_cast<PointerType>(ElemTy))
00837     if (PTy->getElementType() == Type::getMetadataTy(ElemTy->getContext()))
00838       return false;
00839 
00840   return true;
00841 }
00842 
00843 VectorType *VectorType::get(const Type *ElementType, unsigned NumElements) {
00844   assert(ElementType && "Can't get vector of <null> types!");
00845 
00846   VectorValType PVT(ElementType, NumElements);
00847   VectorType *PT = 0;
00848   
00849   LLVMContextImpl *pImpl = ElementType->getContext().pImpl;
00850   
00851   sys::SmartScopedLock<true> L(pImpl->TypeMapLock);
00852   PT = pImpl->VectorTypes.get(PVT);
00853     
00854   if (!PT) {
00855     pImpl->VectorTypes.add(PVT, PT = new VectorType(ElementType, NumElements));
00856   }
00857 #ifdef DEBUG_MERGE_TYPES
00858   DOUT << "Derived new type: " << *PT << "\n";
00859 #endif
00860   return PT;
00861 }
00862 
00863 bool VectorType::isValidElementType(const Type *ElemTy) {
00864   if (ElemTy->isInteger() || ElemTy->isFloatingPoint() ||
00865       isa<OpaqueType>(ElemTy))
00866     return true;
00867 
00868   return false;
00869 }
00870 
00871 //===----------------------------------------------------------------------===//
00872 // Struct Type Factory...
00873 //
00874 
00875 StructType *StructType::get(LLVMContext &Context,
00876                             const std::vector<const Type*> &ETypes, 
00877                             bool isPacked) {
00878   StructValType STV(ETypes, isPacked);
00879   StructType *ST = 0;
00880   
00881   LLVMContextImpl *pImpl = Context.pImpl;
00882   
00883   sys::SmartScopedLock<true> L(pImpl->TypeMapLock);
00884   ST = pImpl->StructTypes.get(STV);
00885     
00886   if (!ST) {
00887     // Value not found.  Derive a new type!
00888     ST = (StructType*) operator new(sizeof(StructType) +
00889                                     sizeof(PATypeHandle) * ETypes.size());
00890     new (ST) StructType(Context, ETypes, isPacked);
00891     pImpl->StructTypes.add(STV, ST);
00892   }
00893 #ifdef DEBUG_MERGE_TYPES
00894   DOUT << "Derived new type: " << *ST << "\n";
00895 #endif
00896   return ST;
00897 }
00898 
00899 StructType *StructType::get(LLVMContext &Context, const Type *type, ...) {
00900   va_list ap;
00901   std::vector<const llvm::Type*> StructFields;
00902   va_start(ap, type);
00903   while (type) {
00904     StructFields.push_back(type);
00905     type = va_arg(ap, llvm::Type*);
00906   }
00907   return llvm::StructType::get(Context, StructFields);
00908 }
00909 
00910 bool StructType::isValidElementType(const Type *ElemTy) {
00911   if (ElemTy == Type::getVoidTy(ElemTy->getContext()) ||
00912       ElemTy == Type::getLabelTy(ElemTy->getContext()) ||
00913       ElemTy == Type::getMetadataTy(ElemTy->getContext()))
00914     return false;
00915 
00916   if (const PointerType *PTy = dyn_cast<PointerType>(ElemTy))
00917     if (PTy->getElementType() == Type::getMetadataTy(ElemTy->getContext()))
00918       return false;
00919 
00920   return true;
00921 }
00922 
00923 
00924 //===----------------------------------------------------------------------===//
00925 // Pointer Type Factory...
00926 //
00927 
00928 PointerType *PointerType::get(const Type *ValueType, unsigned AddressSpace) {
00929   assert(ValueType && "Can't get a pointer to <null> type!");
00930   assert(ValueType != Type::getVoidTy(ValueType->getContext()) &&
00931          "Pointer to void is not valid, use i8* instead!");
00932   assert(isValidElementType(ValueType) && "Invalid type for pointer element!");
00933   PointerValType PVT(ValueType, AddressSpace);
00934 
00935   PointerType *PT = 0;
00936   
00937   LLVMContextImpl *pImpl = ValueType->getContext().pImpl;
00938   
00939   sys::SmartScopedLock<true> L(pImpl->TypeMapLock);
00940   PT = pImpl->PointerTypes.get(PVT);
00941   
00942   if (!PT) {
00943     // Value not found.  Derive a new type!
00944     pImpl->PointerTypes.add(PVT, PT = new PointerType(ValueType, AddressSpace));
00945   }
00946 #ifdef DEBUG_MERGE_TYPES
00947   DOUT << "Derived new type: " << *PT << "\n";
00948 #endif
00949   return PT;
00950 }
00951 
00952 PointerType *Type::getPointerTo(unsigned addrs) const {
00953   return PointerType::get(this, addrs);
00954 }
00955 
00956 bool PointerType::isValidElementType(const Type *ElemTy) {
00957   if (ElemTy == Type::getVoidTy(ElemTy->getContext()) ||
00958       ElemTy == Type::getLabelTy(ElemTy->getContext()))
00959     return false;
00960 
00961   if (const PointerType *PTy = dyn_cast<PointerType>(ElemTy))
00962     if (PTy->getElementType() == Type::getMetadataTy(ElemTy->getContext()))
00963       return false;
00964 
00965   return true;
00966 }
00967 
00968 
00969 //===----------------------------------------------------------------------===//
00970 //                     Derived Type Refinement Functions
00971 //===----------------------------------------------------------------------===//
00972 
00973 // addAbstractTypeUser - Notify an abstract type that there is a new user of
00974 // it.  This function is called primarily by the PATypeHandle class.
00975 void Type::addAbstractTypeUser(AbstractTypeUser *U) const {
00976   assert(isAbstract() && "addAbstractTypeUser: Current type not abstract!");
00977   LLVMContextImpl *pImpl = getContext().pImpl;
00978   pImpl->AbstractTypeUsersLock.acquire();
00979   AbstractTypeUsers.push_back(U);
00980   pImpl->AbstractTypeUsersLock.release();
00981 }
00982 
00983 
00984 // removeAbstractTypeUser - Notify an abstract type that a user of the class
00985 // no longer has a handle to the type.  This function is called primarily by
00986 // the PATypeHandle class.  When there are no users of the abstract type, it
00987 // is annihilated, because there is no way to get a reference to it ever again.
00988 //
00989 void Type::removeAbstractTypeUser(AbstractTypeUser *U) const {
00990   LLVMContextImpl *pImpl = getContext().pImpl;
00991   pImpl->AbstractTypeUsersLock.acquire();
00992   
00993   // Search from back to front because we will notify users from back to
00994   // front.  Also, it is likely that there will be a stack like behavior to
00995   // users that register and unregister users.
00996   //
00997   unsigned i;
00998   for (i = AbstractTypeUsers.size(); AbstractTypeUsers[i-1] != U; --i)
00999     assert(i != 0 && "AbstractTypeUser not in user list!");
01000 
01001   --i;  // Convert to be in range 0 <= i < size()
01002   assert(i < AbstractTypeUsers.size() && "Index out of range!");  // Wraparound?
01003 
01004   AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i);
01005 
01006 #ifdef DEBUG_MERGE_TYPES
01007   DOUT << "  remAbstractTypeUser[" << (void*)this << ", "
01008        << *this << "][" << i << "] User = " << U << "\n";
01009 #endif
01010 
01011   if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) {
01012 #ifdef DEBUG_MERGE_TYPES
01013     DOUT << "DELETEing unused abstract type: <" << *this
01014          << ">[" << (void*)this << "]" << "\n";
01015 #endif
01016   
01017   this->destroy();
01018   }
01019   
01020   pImpl->AbstractTypeUsersLock.release();
01021 }
01022 
01023 // unlockedRefineAbstractTypeTo - This function is used when it is discovered
01024 // that the 'this' abstract type is actually equivalent to the NewType
01025 // specified. This causes all users of 'this' to switch to reference the more 
01026 // concrete type NewType and for 'this' to be deleted.  Only used for internal
01027 // callers.
01028 //
01029 void DerivedType::unlockedRefineAbstractTypeTo(const Type *NewType) {
01030   assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!");
01031   assert(this != NewType && "Can't refine to myself!");
01032   assert(ForwardType == 0 && "This type has already been refined!");
01033 
01034   LLVMContextImpl *pImpl = getContext().pImpl;
01035 
01036   // The descriptions may be out of date.  Conservatively clear them all!
01037   pImpl->AbstractTypeDescriptions.clear();
01038 
01039 #ifdef DEBUG_MERGE_TYPES
01040   DOUT << "REFINING abstract type [" << (void*)this << " "
01041        << *this << "] to [" << (void*)NewType << " "
01042        << *NewType << "]!\n";
01043 #endif
01044 
01045   // Make sure to put the type to be refined to into a holder so that if IT gets
01046   // refined, that we will not continue using a dead reference...
01047   //
01048   PATypeHolder NewTy(NewType);
01049   // Any PATypeHolders referring to this type will now automatically forward o
01050   // the type we are resolved to.
01051   ForwardType = NewType;
01052   if (NewType->isAbstract())
01053     cast<DerivedType>(NewType)->addRef();
01054 
01055   // Add a self use of the current type so that we don't delete ourself until
01056   // after the function exits.
01057   //
01058   PATypeHolder CurrentTy(this);
01059 
01060   // To make the situation simpler, we ask the subclass to remove this type from
01061   // the type map, and to replace any type uses with uses of non-abstract types.
01062   // This dramatically limits the amount of recursive type trouble we can find
01063   // ourselves in.
01064   dropAllTypeUses();
01065 
01066   // Iterate over all of the uses of this type, invoking callback.  Each user
01067   // should remove itself from our use list automatically.  We have to check to
01068   // make sure that NewTy doesn't _become_ 'this'.  If it does, resolving types
01069   // will not cause users to drop off of the use list.  If we resolve to ourself
01070   // we succeed!
01071   //
01072   pImpl->AbstractTypeUsersLock.acquire();
01073   while (!AbstractTypeUsers.empty() && NewTy != this) {
01074     AbstractTypeUser *User = AbstractTypeUsers.back();
01075 
01076     unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize;
01077 #ifdef DEBUG_MERGE_TYPES
01078     DOUT << " REFINING user " << OldSize-1 << "[" << (void*)User
01079          << "] of abstract type [" << (void*)this << " "
01080          << *this << "] to [" << (void*)NewTy.get() << " "
01081          << *NewTy << "]!\n";
01082 #endif
01083     User->refineAbstractType(this, NewTy);
01084 
01085     assert(AbstractTypeUsers.size() != OldSize &&
01086            "AbsTyUser did not remove self from user list!");
01087   }
01088   pImpl->AbstractTypeUsersLock.release();
01089 
01090   // If we were successful removing all users from the type, 'this' will be
01091   // deleted when the last PATypeHolder is destroyed or updated from this type.
01092   // This may occur on exit of this function, as the CurrentTy object is
01093   // destroyed.
01094 }
01095 
01096 // refineAbstractTypeTo - This function is used by external callers to notify
01097 // us that this abstract type is equivalent to another type.
01098 //
01099 void DerivedType::refineAbstractTypeTo(const Type *NewType) {
01100   // All recursive calls will go through unlockedRefineAbstractTypeTo,
01101   // to avoid deadlock problems.
01102   sys::SmartScopedLock<true> L(NewType->getContext().pImpl->TypeMapLock);
01103   unlockedRefineAbstractTypeTo(NewType);
01104 }
01105 
01106 // notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type that
01107 // the current type has transitioned from being abstract to being concrete.
01108 //
01109 void DerivedType::notifyUsesThatTypeBecameConcrete() {
01110 #ifdef DEBUG_MERGE_TYPES
01111   DOUT << "typeIsREFINED type: " << (void*)this << " " << *this << "\n";
01112 #endif
01113 
01114   LLVMContextImpl *pImpl = getContext().pImpl;
01115 
01116   pImpl->AbstractTypeUsersLock.acquire();
01117   unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize;
01118   while (!AbstractTypeUsers.empty()) {
01119     AbstractTypeUser *ATU = AbstractTypeUsers.back();
01120     ATU->typeBecameConcrete(this);
01121 
01122     assert(AbstractTypeUsers.size() < OldSize-- &&
01123            "AbstractTypeUser did not remove itself from the use list!");
01124   }
01125   pImpl->AbstractTypeUsersLock.release();
01126 }
01127 
01128 // refineAbstractType - Called when a contained type is found to be more
01129 // concrete - this could potentially change us from an abstract type to a
01130 // concrete type.
01131 //
01132 void FunctionType::refineAbstractType(const DerivedType *OldType,
01133                                       const Type *NewType) {
01134   LLVMContextImpl *pImpl = OldType->getContext().pImpl;
01135   pImpl->FunctionTypes.RefineAbstractType(this, OldType, NewType);
01136 }
01137 
01138 void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) {
01139   LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
01140   pImpl->FunctionTypes.TypeBecameConcrete(this, AbsTy);
01141 }
01142 
01143 
01144 // refineAbstractType - Called when a contained type is found to be more
01145 // concrete - this could potentially change us from an abstract type to a
01146 // concrete type.
01147 //
01148 void ArrayType::refineAbstractType(const DerivedType *OldType,
01149                                    const Type *NewType) {
01150   LLVMContextImpl *pImpl = OldType->getContext().pImpl;
01151   pImpl->ArrayTypes.RefineAbstractType(this, OldType, NewType);
01152 }
01153 
01154 void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) {
01155   LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
01156   pImpl->ArrayTypes.TypeBecameConcrete(this, AbsTy);
01157 }
01158 
01159 // refineAbstractType - Called when a contained type is found to be more
01160 // concrete - this could potentially change us from an abstract type to a
01161 // concrete type.
01162 //
01163 void VectorType::refineAbstractType(const DerivedType *OldType,
01164                                    const Type *NewType) {
01165   LLVMContextImpl *pImpl = OldType->getContext().pImpl;
01166   pImpl->VectorTypes.RefineAbstractType(this, OldType, NewType);
01167 }
01168 
01169 void VectorType::typeBecameConcrete(const DerivedType *AbsTy) {
01170   LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
01171   pImpl->VectorTypes.TypeBecameConcrete(this, AbsTy);
01172 }
01173 
01174 // refineAbstractType - Called when a contained type is found to be more
01175 // concrete - this could potentially change us from an abstract type to a
01176 // concrete type.
01177 //
01178 void StructType::refineAbstractType(const DerivedType *OldType,
01179                                     const Type *NewType) {
01180   LLVMContextImpl *pImpl = OldType->getContext().pImpl;
01181   pImpl->StructTypes.RefineAbstractType(this, OldType, NewType);
01182 }
01183 
01184 void StructType::typeBecameConcrete(const DerivedType *AbsTy) {
01185   LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
01186   pImpl->StructTypes.TypeBecameConcrete(this, AbsTy);
01187 }
01188 
01189 // refineAbstractType - Called when a contained type is found to be more
01190 // concrete - this could potentially change us from an abstract type to a
01191 // concrete type.
01192 //
01193 void PointerType::refineAbstractType(const DerivedType *OldType,
01194                                      const Type *NewType) {
01195   LLVMContextImpl *pImpl = OldType->getContext().pImpl;
01196   pImpl->PointerTypes.RefineAbstractType(this, OldType, NewType);
01197 }
01198 
01199 void PointerType::typeBecameConcrete(const DerivedType *AbsTy) {
01200   LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
01201   pImpl->PointerTypes.TypeBecameConcrete(this, AbsTy);
01202 }
01203 
01204 bool SequentialType::indexValid(const Value *V) const {
01205   if (isa<IntegerType>(V->getType())) 
01206     return true;
01207   return false;
01208 }
01209 
01210 namespace llvm {
01211 std::ostream &operator<<(std::ostream &OS, const Type *T) {
01212   if (T == 0)
01213     OS << "<null> value!\n";
01214   else
01215     T->print(OS);
01216   return OS;
01217 }
01218 
01219 std::ostream &operator<<(std::ostream &OS, const Type &T) {
01220   T.print(OS);
01221   return OS;
01222 }
01223 
01224 raw_ostream &operator<<(raw_ostream &OS, const Type &T) {
01225   T.print(OS);
01226   return OS;
01227 }
01228 }