lib/VMCore/Type.cpp

   1 //===-- Type.cpp - Implement the Type class -------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the Type class for the VMCore library.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/DerivedTypes.h"
  15 #include "llvm/Constants.h"
  16 #include "llvm/Assembly/Writer.h"
  17 #include "llvm/ADT/DepthFirstIterator.h"
  18 #include "llvm/ADT/StringExtras.h"
  19 #include "llvm/ADT/SCCIterator.h"
  20 #include "llvm/ADT/STLExtras.h"
  21 #include "llvm/Support/Compiler.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Support/ManagedStatic.h"
  24 #include "llvm/Support/MathExtras.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include <algorithm>
  27 #include <cstdarg>
  28 using namespace llvm;
  29
  30 // DEBUG_MERGE_TYPES - Enable this #define to see how and when derived types are
  31 // created and later destroyed, all in an effort to make sure that there is only
  32 // a single canonical version of a type.
  33 //
  34 // #define DEBUG_MERGE_TYPES 1
  35
  36 AbstractTypeUser::~AbstractTypeUser() {}
  37
  38
  39 //===----------------------------------------------------------------------===//
  40 //                         Type Class Implementation
  41 //===----------------------------------------------------------------------===//
  42
  43 // Concrete/Abstract TypeDescriptions - We lazily calculate type descriptions
  44 // for types as they are needed.  Because resolution of types must invalidate
  45 // all of the abstract type descriptions, we keep them in a seperate map to make
  46 // this easy.
  47 static ManagedStatic<TypePrinting> ConcreteTypeDescriptions;
  48 static ManagedStatic<TypePrinting> AbstractTypeDescriptions;
  49
  50 /// Because of the way Type subclasses are allocated, this function is necessary
  51 /// to use the correct kind of "delete" operator to deallocate the Type object.
  52 /// Some type objects (FunctionTy, StructTy) allocate additional space after
  53 /// the space for their derived type to hold the contained types array of
  54 /// PATypeHandles. Using this allocation scheme means all the PATypeHandles are
  55 /// allocated with the type object, decreasing allocations and eliminating the
  56 /// need for a std::vector to be used in the Type class itself.
  57 /// @brief Type destruction function
  58 void Type::destroy() const {
  59
  60   // Structures and Functions allocate their contained types past the end of
  61   // the type object itself. These need to be destroyed differently than the
  62   // other types.
  63   if (isa<FunctionType>(this) || isa<StructType>(this)) {
  64     // First, make sure we destruct any PATypeHandles allocated by these
  65     // subclasses.  They must be manually destructed.
  66     for (unsigned i = 0; i < NumContainedTys; ++i)
  67       ContainedTys[i].PATypeHandle::~PATypeHandle();
  68
  69     // Now call the destructor for the subclass directly because we're going
  70     // to delete this as an array of char.
  71     if (isa<FunctionType>(this))
  72       static_cast<const FunctionType*>(this)->FunctionType::~FunctionType();
  73     else
  74       static_cast<const StructType*>(this)->StructType::~StructType();
  75
  76     // Finally, remove the memory as an array deallocation of the chars it was
  77     // constructed from.
  78     operator delete(const_cast<Type *>(this));
  79
  80     return;
  81   }
  82
  83   // For all the other type subclasses, there is either no contained types or
  84   // just one (all Sequentials). For Sequentials, the PATypeHandle is not
  85   // allocated past the type object, its included directly in the SequentialType
  86   // class. This means we can safely just do "normal" delete of this object and
  87   // all the destructors that need to run will be run.
  88   delete this;
  89 }
  90
  91 const Type *Type::getPrimitiveType(TypeID IDNumber) {
  92   switch (IDNumber) {
  93   case VoidTyID      : return VoidTy;
  94   case FloatTyID     : return FloatTy;
  95   case DoubleTyID    : return DoubleTy;
  96   case X86_FP80TyID  : return X86_FP80Ty;
  97   case FP128TyID     : return FP128Ty;
  98   case PPC_FP128TyID : return PPC_FP128Ty;
  99   case LabelTyID     : return LabelTy;
 100   case MetadataTyID  : return MetadataTy;
 101   default:
 102     return 0;
 103   }
 104 }
 105
 106 const Type *Type::getVAArgsPromotedType() const {
 107   if (ID == IntegerTyID && getSubclassData() < 32)
 108     return Type::Int32Ty;
 109   else if (ID == FloatTyID)
 110     return Type::DoubleTy;
 111   else
 112     return this;
 113 }
 114
 115 /// isIntOrIntVector - Return true if this is an integer type or a vector of
 116 /// integer types.
 117 ///
 118 bool Type::isIntOrIntVector() const {
 119   if (isInteger())
 120     return true;
 121   if (ID != Type::VectorTyID) return false;
 122
 123   return cast<VectorType>(this)->getElementType()->isInteger();
 124 }
 125
 126 /// isFPOrFPVector - Return true if this is a FP type or a vector of FP types.
 127 ///
 128 bool Type::isFPOrFPVector() const {
 129   if (ID == Type::FloatTyID || ID == Type::DoubleTyID ||
 130       ID == Type::FP128TyID || ID == Type::X86_FP80TyID ||
 131       ID == Type::PPC_FP128TyID)
 132     return true;
 133   if (ID != Type::VectorTyID) return false;
 134
 135   return cast<VectorType>(this)->getElementType()->isFloatingPoint();
 136 }
 137
 138 // canLosslesllyBitCastTo - Return true if this type can be converted to
 139 // 'Ty' without any reinterpretation of bits.  For example, uint to int.
 140 //
 141 bool Type::canLosslesslyBitCastTo(const Type *Ty) const {
 142   // Identity cast means no change so return true
 143   if (this == Ty)
 144     return true;
 145
 146   // They are not convertible unless they are at least first class types
 147   if (!this->isFirstClassType() || !Ty->isFirstClassType())
 148     return false;
 149
 150   // Vector -> Vector conversions are always lossless if the two vector types
 151   // have the same size, otherwise not.
 152   if (const VectorType *thisPTy = dyn_cast<VectorType>(this))
 153     if (const VectorType *thatPTy = dyn_cast<VectorType>(Ty))
 154       return thisPTy->getBitWidth() == thatPTy->getBitWidth();
 155
 156   // At this point we have only various mismatches of the first class types
 157   // remaining and ptr->ptr. Just select the lossless conversions. Everything
 158   // else is not lossless.
 159   if (isa<PointerType>(this))
 160     return isa<PointerType>(Ty);
 161   return false;  // Other types have no identity values
 162 }
 163
 164 unsigned Type::getPrimitiveSizeInBits() const {
 165   switch (getTypeID()) {
 166   case Type::FloatTyID: return 32;
 167   case Type::DoubleTyID: return 64;
 168   case Type::X86_FP80TyID: return 80;
 169   case Type::FP128TyID: return 128;
 170   case Type::PPC_FP128TyID: return 128;
 171   case Type::IntegerTyID: return cast<IntegerType>(this)->getBitWidth();
 172   case Type::VectorTyID:  return cast<VectorType>(this)->getBitWidth();
 173   default: return 0;
 174   }
 175 }
 176
 177 /// isSizedDerivedType - Derived types like structures and arrays are sized
 178 /// iff all of the members of the type are sized as well.  Since asking for
 179 /// their size is relatively uncommon, move this operation out of line.
 180 bool Type::isSizedDerivedType() const {
 181   if (isa<IntegerType>(this))
 182     return true;
 183
 184   if (const ArrayType *ATy = dyn_cast<ArrayType>(this))
 185     return ATy->getElementType()->isSized();
 186
 187   if (const VectorType *PTy = dyn_cast<VectorType>(this))
 188     return PTy->getElementType()->isSized();
 189
 190   if (!isa<StructType>(this))
 191     return false;
 192
 193   // Okay, our struct is sized if all of the elements are...
 194   for (subtype_iterator I = subtype_begin(), E = subtype_end(); I != E; ++I)
 195     if (!(*I)->isSized())
 196       return false;
 197
 198   return true;
 199 }
 200
 201 /// getForwardedTypeInternal - This method is used to implement the union-find
 202 /// algorithm for when a type is being forwarded to another type.
 203 const Type *Type::getForwardedTypeInternal() const {
 204   assert(ForwardType && "This type is not being forwarded to another type!");
 205
 206   // Check to see if the forwarded type has been forwarded on.  If so, collapse
 207   // the forwarding links.
 208   const Type *RealForwardedType = ForwardType->getForwardedType();
 209   if (!RealForwardedType)
 210     return ForwardType;  // No it's not forwarded again
 211
 212   // Yes, it is forwarded again.  First thing, add the reference to the new
 213   // forward type.
 214   if (RealForwardedType->isAbstract())
 215     cast<DerivedType>(RealForwardedType)->addRef();
 216
 217   // Now drop the old reference.  This could cause ForwardType to get deleted.
 218   cast<DerivedType>(ForwardType)->dropRef();
 219
 220   // Return the updated type.
 221   ForwardType = RealForwardedType;
 222   return ForwardType;
 223 }
 224
 225 void Type::refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 226   abort();
 227 }
 228 void Type::typeBecameConcrete(const DerivedType *AbsTy) {
 229   abort();
 230 }
 231
 232
 233 std::string Type::getDescription() const {
 234   TypePrinting &Map =
 235     isAbstract() ? *AbstractTypeDescriptions : *ConcreteTypeDescriptions;
 236
 237   std::string DescStr;
 238   raw_string_ostream DescOS(DescStr);
 239   Map.print(this, DescOS);
 240   return DescOS.str();
 241 }
 242
 243
 244 bool StructType::indexValid(const Value *V) const {
 245   // Structure indexes require 32-bit integer constants.
 246   if (V->getType() == Type::Int32Ty)
 247     if (const ConstantInt *CU = dyn_cast<ConstantInt>(V))
 248       return indexValid(CU->getZExtValue());
 249   return false;
 250 }
 251
 252 bool StructType::indexValid(unsigned V) const {
 253   return V < NumContainedTys;
 254 }
 255
 256 // getTypeAtIndex - Given an index value into the type, return the type of the
 257 // element.  For a structure type, this must be a constant value...
 258 //
 259 const Type *StructType::getTypeAtIndex(const Value *V) const {
 260   unsigned Idx = (unsigned)cast<ConstantInt>(V)->getZExtValue();
 261   return getTypeAtIndex(Idx);
 262 }
 263
 264 const Type *StructType::getTypeAtIndex(unsigned Idx) const {
 265   assert(indexValid(Idx) && "Invalid structure index!");
 266   return ContainedTys[Idx];
 267 }
 268
 269 //===----------------------------------------------------------------------===//
 270 //                          Primitive 'Type' data
 271 //===----------------------------------------------------------------------===//
 272
 273 const Type *Type::VoidTy       = new Type(Type::VoidTyID);
 274 const Type *Type::FloatTy      = new Type(Type::FloatTyID);
 275 const Type *Type::DoubleTy     = new Type(Type::DoubleTyID);
 276 const Type *Type::X86_FP80Ty   = new Type(Type::X86_FP80TyID);
 277 const Type *Type::FP128Ty      = new Type(Type::FP128TyID);
 278 const Type *Type::PPC_FP128Ty  = new Type(Type::PPC_FP128TyID);
 279 const Type *Type::LabelTy      = new Type(Type::LabelTyID);
 280 const Type *Type::MetadataTy   = new Type(Type::MetadataTyID);
 281
 282 namespace {
 283   struct BuiltinIntegerType : public IntegerType {
 284     explicit BuiltinIntegerType(unsigned W) : IntegerType(W) {}
 285   };
 286 }
 287 const IntegerType *Type::Int1Ty  = new BuiltinIntegerType(1);
 288 const IntegerType *Type::Int8Ty  = new BuiltinIntegerType(8);
 289 const IntegerType *Type::Int16Ty = new BuiltinIntegerType(16);
 290 const IntegerType *Type::Int32Ty = new BuiltinIntegerType(32);
 291 const IntegerType *Type::Int64Ty = new BuiltinIntegerType(64);
 292
 293 //===----------------------------------------------------------------------===//
 294 //                          Derived Type Constructors
 295 //===----------------------------------------------------------------------===//
 296
 297 /// isValidReturnType - Return true if the specified type is valid as a return
 298 /// type.
 299 bool FunctionType::isValidReturnType(const Type *RetTy) {
 300   if (RetTy->isFirstClassType()) {
 301     if (const PointerType *PTy = dyn_cast<PointerType>(RetTy))
 302       return PTy->getElementType() != Type::MetadataTy;
 303     return true;
 304   }
 305   if (RetTy == Type::VoidTy || RetTy == Type::MetadataTy ||
 306       isa<OpaqueType>(RetTy))
 307     return true;
 308
 309   // If this is a multiple return case, verify that each return is a first class
 310   // value and that there is at least one value.
 311   const StructType *SRetTy = dyn_cast<StructType>(RetTy);
 312   if (SRetTy == 0 || SRetTy->getNumElements() == 0)
 313     return false;
 314
 315   for (unsigned i = 0, e = SRetTy->getNumElements(); i != e; ++i)
 316     if (!SRetTy->getElementType(i)->isFirstClassType())
 317       return false;
 318   return true;
 319 }
 320
 321 FunctionType::FunctionType(const Type *Result,
 322                            const std::vector<const Type*> &Params,
 323                            bool IsVarArgs)
 324   : DerivedType(FunctionTyID), isVarArgs(IsVarArgs) {
 325   ContainedTys = reinterpret_cast<PATypeHandle*>(this+1);
 326   NumContainedTys = Params.size() + 1; // + 1 for result type
 327   assert(isValidReturnType(Result) && "invalid return type for function");
 328
 329
 330   bool isAbstract = Result->isAbstract();
 331   new (&ContainedTys[0]) PATypeHandle(Result, this);
 332
 333   for (unsigned i = 0; i != Params.size(); ++i) {
 334     assert((Params[i]->isFirstClassType() || isa<OpaqueType>(Params[i])) &&
 335            "Function arguments must be value types!");
 336     assert((!isa<PointerType>(Params[i]) ||
 337             cast<PointerType>(Params[i])->getElementType() != Type::MetadataTy)
 338            && "Attempt to use metadata* as function argument type!");
 339     new (&ContainedTys[i+1]) PATypeHandle(Params[i], this);
 340     isAbstract |= Params[i]->isAbstract();
 341   }
 342
 343   // Calculate whether or not this type is abstract
 344   setAbstract(isAbstract);
 345 }
 346
 347 StructType::StructType(const std::vector<const Type*> &Types, bool isPacked)
 348   : CompositeType(StructTyID) {
 349   ContainedTys = reinterpret_cast<PATypeHandle*>(this + 1);
 350   NumContainedTys = Types.size();
 351   setSubclassData(isPacked);
 352   bool isAbstract = false;
 353   for (unsigned i = 0; i < Types.size(); ++i) {
 354     assert(Types[i] && "<null> type for structure field!");
 355     assert(Types[i] != Type::VoidTy && "Void type for structure field!");
 356     assert(Types[i] != Type::LabelTy && "Label type for structure field!");
 357     assert(Types[i] != Type::MetadataTy && "Metadata type for structure field");
 358     assert((!isa<PointerType>(Types[i]) ||
 359             cast<PointerType>(Types[i])->getElementType() != Type::MetadataTy)
 360            && "Type 'metadata*' is invalid for structure field.");
 361     new (&ContainedTys[i]) PATypeHandle(Types[i], this);
 362     isAbstract |= Types[i]->isAbstract();
 363   }
 364
 365   // Calculate whether or not this type is abstract
 366   setAbstract(isAbstract);
 367 }
 368
 369 ArrayType::ArrayType(const Type *ElType, uint64_t NumEl)
 370   : SequentialType(ArrayTyID, ElType) {
 371   NumElements = NumEl;
 372
 373   // Calculate whether or not this type is abstract
 374   setAbstract(ElType->isAbstract());
 375 }
 376
 377 VectorType::VectorType(const Type *ElType, unsigned NumEl)
 378   : SequentialType(VectorTyID, ElType) {
 379   NumElements = NumEl;
 380   setAbstract(ElType->isAbstract());
 381   assert(NumEl > 0 && "NumEl of a VectorType must be greater than 0");
 382   assert((ElType->isInteger() || ElType->isFloatingPoint() ||
 383           isa<OpaqueType>(ElType)) &&
 384          "Elements of a VectorType must be a primitive type");
 385
 386 }
 387
 388
 389 PointerType::PointerType(const Type *E, unsigned AddrSpace)
 390   : SequentialType(PointerTyID, E) {
 391   AddressSpace = AddrSpace;
 392   // Calculate whether or not this type is abstract
 393   setAbstract(E->isAbstract());
 394 }
 395
 396 OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) {
 397   setAbstract(true);
 398 #ifdef DEBUG_MERGE_TYPES
 399   DOUT << "Derived new type: " << *this << "\n";
 400 #endif
 401 }
 402
 403 void PATypeHolder::destroy() {
 404   Ty = 0;
 405 }
 406
 407 // dropAllTypeUses - When this (abstract) type is resolved to be equal to
 408 // another (more concrete) type, we must eliminate all references to other
 409 // types, to avoid some circular reference problems.
 410 void DerivedType::dropAllTypeUses() {
 411   if (NumContainedTys != 0) {
 412     // The type must stay abstract.  To do this, we insert a pointer to a type
 413     // that will never get resolved, thus will always be abstract.
 414     static Type *AlwaysOpaqueTy = OpaqueType::get();
 415     static PATypeHolder Holder(AlwaysOpaqueTy);
 416     ContainedTys[0] = AlwaysOpaqueTy;
 417
 418     // Change the rest of the types to be Int32Ty's.  It doesn't matter what we
 419     // pick so long as it doesn't point back to this type.  We choose something
 420     // concrete to avoid overhead for adding to AbstracTypeUser lists and stuff.
 421     for (unsigned i = 1, e = NumContainedTys; i != e; ++i)
 422       ContainedTys[i] = Type::Int32Ty;
 423   }
 424 }
 425
 426
 427 namespace {
 428
 429 /// TypePromotionGraph and graph traits - this is designed to allow us to do
 430 /// efficient SCC processing of type graphs.  This is the exact same as
 431 /// GraphTraits<Type*>, except that we pretend that concrete types have no
 432 /// children to avoid processing them.
 433 struct TypePromotionGraph {
 434   Type *Ty;
 435   TypePromotionGraph(Type *T) : Ty(T) {}
 436 };
 437
 438 }
 439
 440 namespace llvm {
 441   template <> struct GraphTraits<TypePromotionGraph> {
 442     typedef Type NodeType;
 443     typedef Type::subtype_iterator ChildIteratorType;
 444
 445     static inline NodeType *getEntryNode(TypePromotionGraph G) { return G.Ty; }
 446     static inline ChildIteratorType child_begin(NodeType *N) {
 447       if (N->isAbstract())
 448         return N->subtype_begin();
 449       else           // No need to process children of concrete types.
 450         return N->subtype_end();
 451     }
 452     static inline ChildIteratorType child_end(NodeType *N) {
 453       return N->subtype_end();
 454     }
 455   };
 456 }
 457
 458
 459 // PromoteAbstractToConcrete - This is a recursive function that walks a type
 460 // graph calculating whether or not a type is abstract.
 461 //
 462 void Type::PromoteAbstractToConcrete() {
 463   if (!isAbstract()) return;
 464
 465   scc_iterator<TypePromotionGraph> SI = scc_begin(TypePromotionGraph(this));
 466   scc_iterator<TypePromotionGraph> SE = scc_end  (TypePromotionGraph(this));
 467
 468   for (; SI != SE; ++SI) {
 469     std::vector<Type*> &SCC = *SI;
 470
 471     // Concrete types are leaves in the tree.  Since an SCC will either be all
 472     // abstract or all concrete, we only need to check one type.
 473     if (SCC[0]->isAbstract()) {
 474       if (isa<OpaqueType>(SCC[0]))
 475         return;     // Not going to be concrete, sorry.
 476
 477       // If all of the children of all of the types in this SCC are concrete,
 478       // then this SCC is now concrete as well.  If not, neither this SCC, nor
 479       // any parent SCCs will be concrete, so we might as well just exit.
 480       for (unsigned i = 0, e = SCC.size(); i != e; ++i)
 481         for (Type::subtype_iterator CI = SCC[i]->subtype_begin(),
 482                E = SCC[i]->subtype_end(); CI != E; ++CI)
 483           if ((*CI)->isAbstract())
 484             // If the child type is in our SCC, it doesn't make the entire SCC
 485             // abstract unless there is a non-SCC abstract type.
 486             if (std::find(SCC.begin(), SCC.end(), *CI) == SCC.end())
 487               return;               // Not going to be concrete, sorry.
 488
 489       // Okay, we just discovered this whole SCC is now concrete, mark it as
 490       // such!
 491       for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
 492         assert(SCC[i]->isAbstract() && "Why are we processing concrete types?");
 493
 494         SCC[i]->setAbstract(false);
 495       }
 496
 497       for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
 498         assert(!SCC[i]->isAbstract() && "Concrete type became abstract?");
 499         // The type just became concrete, notify all users!
 500         cast<DerivedType>(SCC[i])->notifyUsesThatTypeBecameConcrete();
 501       }
 502     }
 503   }
 504 }
 505
 506
 507 //===----------------------------------------------------------------------===//
 508 //                      Type Structural Equality Testing
 509 //===----------------------------------------------------------------------===//
 510
 511 // TypesEqual - Two types are considered structurally equal if they have the
 512 // same "shape": Every level and element of the types have identical primitive
 513 // ID's, and the graphs have the same edges/nodes in them.  Nodes do not have to
 514 // be pointer equals to be equivalent though.  This uses an optimistic algorithm
 515 // that assumes that two graphs are the same until proven otherwise.
 516 //
 517 static bool TypesEqual(const Type *Ty, const Type *Ty2,
 518                        std::map<const Type *, const Type *> &EqTypes) {
 519   if (Ty == Ty2) return true;
 520   if (Ty->getTypeID() != Ty2->getTypeID()) return false;
 521   if (isa<OpaqueType>(Ty))
 522     return false;  // Two unequal opaque types are never equal
 523
 524   std::map<const Type*, const Type*>::iterator It = EqTypes.find(Ty);
 525   if (It != EqTypes.end())
 526     return It->second == Ty2;    // Looping back on a type, check for equality
 527
 528   // Otherwise, add the mapping to the table to make sure we don't get
 529   // recursion on the types...
 530   EqTypes.insert(It, std::make_pair(Ty, Ty2));
 531
 532   // Two really annoying special cases that breaks an otherwise nice simple
 533   // algorithm is the fact that arraytypes have sizes that differentiates types,
 534   // and that function types can be varargs or not.  Consider this now.
 535   //
 536   if (const IntegerType *ITy = dyn_cast<IntegerType>(Ty)) {
 537     const IntegerType *ITy2 = cast<IntegerType>(Ty2);
 538     return ITy->getBitWidth() == ITy2->getBitWidth();
 539   } else if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) {
 540     const PointerType *PTy2 = cast<PointerType>(Ty2);
 541     return PTy->getAddressSpace() == PTy2->getAddressSpace() &&
 542            TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
 543   } else if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 544     const StructType *STy2 = cast<StructType>(Ty2);
 545     if (STy->getNumElements() != STy2->getNumElements()) return false;
 546     if (STy->isPacked() != STy2->isPacked()) return false;
 547     for (unsigned i = 0, e = STy2->getNumElements(); i != e; ++i)
 548       if (!TypesEqual(STy->getElementType(i), STy2->getElementType(i), EqTypes))
 549         return false;
 550     return true;
 551   } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
 552     const ArrayType *ATy2 = cast<ArrayType>(Ty2);
 553     return ATy->getNumElements() == ATy2->getNumElements() &&
 554            TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes);
 555   } else if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
 556     const VectorType *PTy2 = cast<VectorType>(Ty2);
 557     return PTy->getNumElements() == PTy2->getNumElements() &&
 558            TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
 559   } else if (const FunctionType *FTy = dyn_cast<FunctionType>(Ty)) {
 560     const FunctionType *FTy2 = cast<FunctionType>(Ty2);
 561     if (FTy->isVarArg() != FTy2->isVarArg() ||
 562         FTy->getNumParams() != FTy2->getNumParams() ||
 563         !TypesEqual(FTy->getReturnType(), FTy2->getReturnType(), EqTypes))
 564       return false;
 565     for (unsigned i = 0, e = FTy2->getNumParams(); i != e; ++i) {
 566       if (!TypesEqual(FTy->getParamType(i), FTy2->getParamType(i), EqTypes))
 567         return false;
 568     }
 569     return true;
 570   } else {
 571     assert(0 && "Unknown derived type!");
 572     return false;
 573   }
 574 }
 575
 576 static bool TypesEqual(const Type *Ty, const Type *Ty2) {
 577   std::map<const Type *, const Type *> EqTypes;
 578   return TypesEqual(Ty, Ty2, EqTypes);
 579 }
 580
 581 // AbstractTypeHasCycleThrough - Return true there is a path from CurTy to
 582 // TargetTy in the type graph.  We know that Ty is an abstract type, so if we
 583 // ever reach a non-abstract type, we know that we don't need to search the
 584 // subgraph.
 585 static bool AbstractTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
 586                                 SmallPtrSet<const Type*, 128> &VisitedTypes) {
 587   if (TargetTy == CurTy) return true;
 588   if (!CurTy->isAbstract()) return false;
 589
 590   if (!VisitedTypes.insert(CurTy))
 591     return false;  // Already been here.
 592
 593   for (Type::subtype_iterator I = CurTy->subtype_begin(),
 594        E = CurTy->subtype_end(); I != E; ++I)
 595     if (AbstractTypeHasCycleThrough(TargetTy, *I, VisitedTypes))
 596       return true;
 597   return false;
 598 }
 599
 600 static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
 601                                 SmallPtrSet<const Type*, 128> &VisitedTypes) {
 602   if (TargetTy == CurTy) return true;
 603
 604   if (!VisitedTypes.insert(CurTy))
 605     return false;  // Already been here.
 606
 607   for (Type::subtype_iterator I = CurTy->subtype_begin(),
 608        E = CurTy->subtype_end(); I != E; ++I)
 609     if (ConcreteTypeHasCycleThrough(TargetTy, *I, VisitedTypes))
 610       return true;
 611   return false;
 612 }
 613
 614 /// TypeHasCycleThroughItself - Return true if the specified type has a cycle
 615 /// back to itself.
 616 static bool TypeHasCycleThroughItself(const Type *Ty) {
 617   SmallPtrSet<const Type*, 128> VisitedTypes;
 618
 619   if (Ty->isAbstract()) {  // Optimized case for abstract types.
 620     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 621          I != E; ++I)
 622       if (AbstractTypeHasCycleThrough(Ty, *I, VisitedTypes))
 623         return true;
 624   } else {
 625     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 626          I != E; ++I)
 627       if (ConcreteTypeHasCycleThrough(Ty, *I, VisitedTypes))
 628         return true;
 629   }
 630   return false;
 631 }
 632
 633 /// getSubElementHash - Generate a hash value for all of the SubType's of this
 634 /// type.  The hash value is guaranteed to be zero if any of the subtypes are
 635 /// an opaque type.  Otherwise we try to mix them in as well as possible, but do
 636 /// not look at the subtype's subtype's.
 637 static unsigned getSubElementHash(const Type *Ty) {
 638   unsigned HashVal = 0;
 639   for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 640        I != E; ++I) {
 641     HashVal *= 32;
 642     const Type *SubTy = I->get();
 643     HashVal += SubTy->getTypeID();
 644     switch (SubTy->getTypeID()) {
 645     default: break;
 646     case Type::OpaqueTyID: return 0;    // Opaque -> hash = 0 no matter what.
 647     case Type::IntegerTyID:
 648       HashVal ^= (cast<IntegerType>(SubTy)->getBitWidth() << 3);
 649       break;
 650     case Type::FunctionTyID:
 651       HashVal ^= cast<FunctionType>(SubTy)->getNumParams()*2 +
 652                  cast<FunctionType>(SubTy)->isVarArg();
 653       break;
 654     case Type::ArrayTyID:
 655       HashVal ^= cast<ArrayType>(SubTy)->getNumElements();
 656       break;
 657     case Type::VectorTyID:
 658       HashVal ^= cast<VectorType>(SubTy)->getNumElements();
 659       break;
 660     case Type::StructTyID:
 661       HashVal ^= cast<StructType>(SubTy)->getNumElements();
 662       break;
 663     case Type::PointerTyID:
 664       HashVal ^= cast<PointerType>(SubTy)->getAddressSpace();
 665       break;
 666     }
 667   }
 668   return HashVal ? HashVal : 1;  // Do not return zero unless opaque subty.
 669 }
 670
 671 //===----------------------------------------------------------------------===//
 672 //                       Derived Type Factory Functions
 673 //===----------------------------------------------------------------------===//
 674
 675 namespace llvm {
 676 class TypeMapBase {
 677 protected:
 678   /// TypesByHash - Keep track of types by their structure hash value.  Note
 679   /// that we only keep track of types that have cycles through themselves in
 680   /// this map.
 681   ///
 682   std::multimap<unsigned, PATypeHolder> TypesByHash;
 683
 684 public:
 685   ~TypeMapBase() {
 686     // PATypeHolder won't destroy non-abstract types.
 687     // We can't destroy them by simply iterating, because
 688     // they may contain references to each-other.
 689 #if 0
 690     for (std::multimap<unsigned, PATypeHolder>::iterator I
 691          = TypesByHash.begin(), E = TypesByHash.end(); I != E; ++I) {
 692       Type *Ty = const_cast<Type*>(I->second.Ty);
 693       I->second.destroy();
 694       // We can't invoke destroy or delete, because the type may
 695       // contain references to already freed types.
 696       // So we have to destruct the object the ugly way.
 697       if (Ty) {
 698         Ty->AbstractTypeUsers.clear();
 699         static_cast<const Type*>(Ty)->Type::~Type();
 700         operator delete(Ty);
 701       }
 702     }
 703 #endif
 704   }
 705
 706   void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) {
 707     std::multimap<unsigned, PATypeHolder>::iterator I =
 708       TypesByHash.lower_bound(Hash);
 709     for (; I != TypesByHash.end() && I->first == Hash; ++I) {
 710       if (I->second == Ty) {
 711         TypesByHash.erase(I);
 712         return;
 713       }
 714     }
 715
 716     // This must be do to an opaque type that was resolved.  Switch down to hash
 717     // code of zero.
 718     assert(Hash && "Didn't find type entry!");
 719     RemoveFromTypesByHash(0, Ty);
 720   }
 721
 722   /// TypeBecameConcrete - When Ty gets a notification that TheType just became
 723   /// concrete, drop uses and make Ty non-abstract if we should.
 724   void TypeBecameConcrete(DerivedType *Ty, const DerivedType *TheType) {
 725     // If the element just became concrete, remove 'ty' from the abstract
 726     // type user list for the type.  Do this for as many times as Ty uses
 727     // OldType.
 728     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 729          I != E; ++I)
 730       if (I->get() == TheType)
 731         TheType->removeAbstractTypeUser(Ty);
 732
 733     // If the type is currently thought to be abstract, rescan all of our
 734     // subtypes to see if the type has just become concrete!  Note that this
 735     // may send out notifications to AbstractTypeUsers that types become
 736     // concrete.
 737     if (Ty->isAbstract())
 738       Ty->PromoteAbstractToConcrete();
 739   }
 740 };
 741 }
 742
 743
 744 // TypeMap - Make sure that only one instance of a particular type may be
 745 // created on any given run of the compiler... note that this involves updating
 746 // our map if an abstract type gets refined somehow.
 747 //
 748 namespace llvm {
 749 template<class ValType, class TypeClass>
 750 class TypeMap : public TypeMapBase {
 751   std::map<ValType, PATypeHolder> Map;
 752 public:
 753   typedef typename std::map<ValType, PATypeHolder>::iterator iterator;
 754   ~TypeMap() { print("ON EXIT"); }
 755
 756   inline TypeClass *get(const ValType &V) {
 757     iterator I = Map.find(V);
 758     return I != Map.end() ? cast<TypeClass>((Type*)I->second.get()) : 0;
 759   }
 760
 761   inline void add(const ValType &V, TypeClass *Ty) {
 762     Map.insert(std::make_pair(V, Ty));
 763
 764     // If this type has a cycle, remember it.
 765     TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty));
 766     print("add");
 767   }
 768
 769   /// RefineAbstractType - This method is called after we have merged a type
 770   /// with another one.  We must now either merge the type away with
 771   /// some other type or reinstall it in the map with it's new configuration.
 772   void RefineAbstractType(TypeClass *Ty, const DerivedType *OldType,
 773                         const Type *NewType) {
 774 #ifdef DEBUG_MERGE_TYPES
 775     DOUT << "RefineAbstractType(" << (void*)OldType << "[" << *OldType
 776          << "], " << (void*)NewType << " [" << *NewType << "])\n";
 777 #endif
 778
 779     // Otherwise, we are changing one subelement type into another.  Clearly the
 780     // OldType must have been abstract, making us abstract.
 781     assert(Ty->isAbstract() && "Refining a non-abstract type!");
 782     assert(OldType != NewType);
 783
 784     // Make a temporary type holder for the type so that it doesn't disappear on
 785     // us when we erase the entry from the map.
 786     PATypeHolder TyHolder = Ty;
 787
 788     // The old record is now out-of-date, because one of the children has been
 789     // updated.  Remove the obsolete entry from the map.
 790     unsigned NumErased = Map.erase(ValType::get(Ty));
 791     assert(NumErased && "Element not found!"); NumErased = NumErased;
 792
 793     // Remember the structural hash for the type before we start hacking on it,
 794     // in case we need it later.
 795     unsigned OldTypeHash = ValType::hashTypeStructure(Ty);
 796
 797     // Find the type element we are refining... and change it now!
 798     for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i)
 799       if (Ty->ContainedTys[i] == OldType)
 800         Ty->ContainedTys[i] = NewType;
 801     unsigned NewTypeHash = ValType::hashTypeStructure(Ty);
 802
 803     // If there are no cycles going through this node, we can do a simple,
 804     // efficient lookup in the map, instead of an inefficient nasty linear
 805     // lookup.
 806     if (!TypeHasCycleThroughItself(Ty)) {
 807       typename std::map<ValType, PATypeHolder>::iterator I;
 808       bool Inserted;
 809
 810       tie(I, Inserted) = Map.insert(std::make_pair(ValType::get(Ty), Ty));
 811       if (!Inserted) {
 812         // Refined to a different type altogether?
 813         RemoveFromTypesByHash(OldTypeHash, Ty);
 814
 815         // We already have this type in the table.  Get rid of the newly refined
 816         // type.
 817         TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
 818         Ty->refineAbstractTypeTo(NewTy);
 819         return;
 820       }
 821     } else {
 822       // Now we check to see if there is an existing entry in the table which is
 823       // structurally identical to the newly refined type.  If so, this type
 824       // gets refined to the pre-existing type.
 825       //
 826       std::multimap<unsigned, PATypeHolder>::iterator I, E, Entry;
 827       tie(I, E) = TypesByHash.equal_range(NewTypeHash);
 828       Entry = E;
 829       for (; I != E; ++I) {
 830         if (I->second == Ty) {
 831           // Remember the position of the old type if we see it in our scan.
 832           Entry = I;
 833         } else {
 834           if (TypesEqual(Ty, I->second)) {
 835             TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
 836
 837             // Remove the old entry form TypesByHash.  If the hash values differ
 838             // now, remove it from the old place.  Otherwise, continue scanning
 839             // withing this hashcode to reduce work.
 840             if (NewTypeHash != OldTypeHash) {
 841               RemoveFromTypesByHash(OldTypeHash, Ty);
 842             } else {
 843               if (Entry == E) {
 844                 // Find the location of Ty in the TypesByHash structure if we
 845                 // haven't seen it already.
 846                 while (I->second != Ty) {
 847                   ++I;
 848                   assert(I != E && "Structure doesn't contain type??");
 849                 }
 850                 Entry = I;
 851               }
 852               TypesByHash.erase(Entry);
 853             }
 854             Ty->refineAbstractTypeTo(NewTy);
 855             return;
 856           }
 857         }
 858       }
 859
 860       // If there is no existing type of the same structure, we reinsert an
 861       // updated record into the map.
 862       Map.insert(std::make_pair(ValType::get(Ty), Ty));
 863     }
 864
 865     // If the hash codes differ, update TypesByHash
 866     if (NewTypeHash != OldTypeHash) {
 867       RemoveFromTypesByHash(OldTypeHash, Ty);
 868       TypesByHash.insert(std::make_pair(NewTypeHash, Ty));
 869     }
 870
 871     // If the type is currently thought to be abstract, rescan all of our
 872     // subtypes to see if the type has just become concrete!  Note that this
 873     // may send out notifications to AbstractTypeUsers that types become
 874     // concrete.
 875     if (Ty->isAbstract())
 876       Ty->PromoteAbstractToConcrete();
 877   }
 878
 879   void print(const char *Arg) const {
 880 #ifdef DEBUG_MERGE_TYPES
 881     DOUT << "TypeMap<>::" << Arg << " table contents:\n";
 882     unsigned i = 0;
 883     for (typename std::map<ValType, PATypeHolder>::const_iterator I
 884            = Map.begin(), E = Map.end(); I != E; ++I)
 885       DOUT << " " << (++i) << ". " << (void*)I->second.get() << " "
 886            << *I->second.get() << "\n";
 887 #endif
 888   }
 889
 890   void dump() const { print("dump output"); }
 891 };
 892 }
 893
 894
 895 //===----------------------------------------------------------------------===//
 896 // Function Type Factory and Value Class...
 897 //
 898
 899 //===----------------------------------------------------------------------===//
 900 // Integer Type Factory...
 901 //
 902 namespace llvm {
 903 class IntegerValType {
 904   uint32_t bits;
 905 public:
 906   IntegerValType(uint16_t numbits) : bits(numbits) {}
 907
 908   static IntegerValType get(const IntegerType *Ty) {
 909     return IntegerValType(Ty->getBitWidth());
 910   }
 911
 912   static unsigned hashTypeStructure(const IntegerType *Ty) {
 913     return (unsigned)Ty->getBitWidth();
 914   }
 915
 916   inline bool operator<(const IntegerValType &IVT) const {
 917     return bits < IVT.bits;
 918   }
 919 };
 920 }
 921
 922 static ManagedStatic<TypeMap<IntegerValType, IntegerType> > IntegerTypes;
 923
 924 const IntegerType *IntegerType::get(unsigned NumBits) {
 925   assert(NumBits >= MIN_INT_BITS && "bitwidth too small");
 926   assert(NumBits <= MAX_INT_BITS && "bitwidth too large");
 927
 928   // Check for the built-in integer types
 929   switch (NumBits) {
 930     case  1: return cast<IntegerType>(Type::Int1Ty);
 931     case  8: return cast<IntegerType>(Type::Int8Ty);
 932     case 16: return cast<IntegerType>(Type::Int16Ty);
 933     case 32: return cast<IntegerType>(Type::Int32Ty);
 934     case 64: return cast<IntegerType>(Type::Int64Ty);
 935     default:
 936       break;
 937   }
 938
 939   IntegerValType IVT(NumBits);
 940   IntegerType *ITy = IntegerTypes->get(IVT);
 941   if (ITy) return ITy;           // Found a match, return it!
 942
 943   // Value not found.  Derive a new type!
 944   ITy = new IntegerType(NumBits);
 945   IntegerTypes->add(IVT, ITy);
 946
 947 #ifdef DEBUG_MERGE_TYPES
 948   DOUT << "Derived new type: " << *ITy << "\n";
 949 #endif
 950   return ITy;
 951 }
 952
 953 bool IntegerType::isPowerOf2ByteWidth() const {
 954   unsigned BitWidth = getBitWidth();
 955   return (BitWidth > 7) && isPowerOf2_32(BitWidth);
 956 }
 957
 958 APInt IntegerType::getMask() const {
 959   return APInt::getAllOnesValue(getBitWidth());
 960 }
 961
 962 // FunctionValType - Define a class to hold the key that goes into the TypeMap
 963 //
 964 namespace llvm {
 965 class FunctionValType {
 966   const Type *RetTy;
 967   std::vector<const Type*> ArgTypes;
 968   bool isVarArg;
 969 public:
 970   FunctionValType(const Type *ret, const std::vector<const Type*> &args,
 971                   bool isVA) : RetTy(ret), ArgTypes(args), isVarArg(isVA) {}
 972
 973   static FunctionValType get(const FunctionType *FT);
 974
 975   static unsigned hashTypeStructure(const FunctionType *FT) {
 976     unsigned Result = FT->getNumParams()*2 + FT->isVarArg();
 977     return Result;
 978   }
 979
 980   inline bool operator<(const FunctionValType &MTV) const {
 981     if (RetTy < MTV.RetTy) return true;
 982     if (RetTy > MTV.RetTy) return false;
 983     if (isVarArg < MTV.isVarArg) return true;
 984     if (isVarArg > MTV.isVarArg) return false;
 985     if (ArgTypes < MTV.ArgTypes) return true;
 986     if (ArgTypes > MTV.ArgTypes) return false;
 987     return false;
 988   }
 989 };
 990 }
 991
 992 // Define the actual map itself now...
 993 static ManagedStatic<TypeMap<FunctionValType, FunctionType> > FunctionTypes;
 994
 995 FunctionValType FunctionValType::get(const FunctionType *FT) {
 996   // Build up a FunctionValType
 997   std::vector<const Type *> ParamTypes;
 998   ParamTypes.reserve(FT->getNumParams());
 999   for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
1000     ParamTypes.push_back(FT->getParamType(i));
1001   return FunctionValType(FT->getReturnType(), ParamTypes, FT->isVarArg());
1002 }
1003
1004
1005 // FunctionType::get - The factory function for the FunctionType class...
1006 FunctionType *FunctionType::get(const Type *ReturnType,
1007                                 const std::vector<const Type*> &Params,
1008                                 bool isVarArg) {
1009   FunctionValType VT(ReturnType, Params, isVarArg);
1010   FunctionType *FT = FunctionTypes->get(VT);
1011   if (FT)
1012     return FT;
1013
1014   FT = (FunctionType*) operator new(sizeof(FunctionType) +
1015                                     sizeof(PATypeHandle)*(Params.size()+1));
1016   new (FT) FunctionType(ReturnType, Params, isVarArg);
1017   FunctionTypes->add(VT, FT);
1018
1019 #ifdef DEBUG_MERGE_TYPES
1020   DOUT << "Derived new type: " << FT << "\n";
1021 #endif
1022   return FT;
1023 }
1024
1025 //===----------------------------------------------------------------------===//
1026 // Array Type Factory...
1027 //
1028 namespace llvm {
1029 class ArrayValType {
1030   const Type *ValTy;
1031   uint64_t Size;
1032 public:
1033   ArrayValType(const Type *val, uint64_t sz) : ValTy(val), Size(sz) {}
1034
1035   static ArrayValType get(const ArrayType *AT) {
1036     return ArrayValType(AT->getElementType(), AT->getNumElements());
1037   }
1038
1039   static unsigned hashTypeStructure(const ArrayType *AT) {
1040     return (unsigned)AT->getNumElements();
1041   }
1042
1043   inline bool operator<(const ArrayValType &MTV) const {
1044     if (Size < MTV.Size) return true;
1045     return Size == MTV.Size && ValTy < MTV.ValTy;
1046   }
1047 };
1048 }
1049 static ManagedStatic<TypeMap<ArrayValType, ArrayType> > ArrayTypes;
1050
1051
1052 ArrayType *ArrayType::get(const Type *ElementType, uint64_t NumElements) {
1053   assert(ElementType && "Can't get array of <null> types!");
1054   assert(ElementType != Type::VoidTy && "Array of void is not valid!");
1055   assert(ElementType != Type::LabelTy && "Array of labels is not valid!");
1056   assert(ElementType != Type::MetadataTy && "Array of metadata is not valid!");
1057   assert((!isa<PointerType>(ElementType) ||
1058           cast<PointerType>(ElementType)->getElementType() != Type::MetadataTy)
1059          && "Array of metadata* is not valid!");
1060
1061   ArrayValType AVT(ElementType, NumElements);
1062   ArrayType *AT = ArrayTypes->get(AVT);
1063   if (AT) return AT;           // Found a match, return it!
1064
1065   // Value not found.  Derive a new type!
1066   ArrayTypes->add(AVT, AT = new ArrayType(ElementType, NumElements));
1067
1068 #ifdef DEBUG_MERGE_TYPES
1069   DOUT << "Derived new type: " << *AT << "\n";
1070 #endif
1071   return AT;
1072 }
1073
1074
1075 //===----------------------------------------------------------------------===//
1076 // Vector Type Factory...
1077 //
1078 namespace llvm {
1079 class VectorValType {
1080   const Type *ValTy;
1081   unsigned Size;
1082 public:
1083   VectorValType(const Type *val, int sz) : ValTy(val), Size(sz) {}
1084
1085   static VectorValType get(const VectorType *PT) {
1086     return VectorValType(PT->getElementType(), PT->getNumElements());
1087   }
1088
1089   static unsigned hashTypeStructure(const VectorType *PT) {
1090     return PT->getNumElements();
1091   }
1092
1093   inline bool operator<(const VectorValType &MTV) const {
1094     if (Size < MTV.Size) return true;
1095     return Size == MTV.Size && ValTy < MTV.ValTy;
1096   }
1097 };
1098 }
1099 static ManagedStatic<TypeMap<VectorValType, VectorType> > VectorTypes;
1100
1101
1102 VectorType *VectorType::get(const Type *ElementType, unsigned NumElements) {
1103   assert(ElementType && "Can't get vector of <null> types!");
1104
1105   VectorValType PVT(ElementType, NumElements);
1106   VectorType *PT = VectorTypes->get(PVT);
1107   if (PT) return PT;           // Found a match, return it!
1108
1109   // Value not found.  Derive a new type!
1110   VectorTypes->add(PVT, PT = new VectorType(ElementType, NumElements));
1111
1112 #ifdef DEBUG_MERGE_TYPES
1113   DOUT << "Derived new type: " << *PT << "\n";
1114 #endif
1115   return PT;
1116 }
1117
1118 //===----------------------------------------------------------------------===//
1119 // Struct Type Factory...
1120 //
1121
1122 namespace llvm {
1123 // StructValType - Define a class to hold the key that goes into the TypeMap
1124 //
1125 class StructValType {
1126   std::vector<const Type*> ElTypes;
1127   bool packed;
1128 public:
1129   StructValType(const std::vector<const Type*> &args, bool isPacked)
1130     : ElTypes(args), packed(isPacked) {}
1131
1132   static StructValType get(const StructType *ST) {
1133     std::vector<const Type *> ElTypes;
1134     ElTypes.reserve(ST->getNumElements());
1135     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i)
1136       ElTypes.push_back(ST->getElementType(i));
1137
1138     return StructValType(ElTypes, ST->isPacked());
1139   }
1140
1141   static unsigned hashTypeStructure(const StructType *ST) {
1142     return ST->getNumElements();
1143   }
1144
1145   inline bool operator<(const StructValType &STV) const {
1146     if (ElTypes < STV.ElTypes) return true;
1147     else if (ElTypes > STV.ElTypes) return false;
1148     else return (int)packed < (int)STV.packed;
1149   }
1150 };
1151 }
1152
1153 static ManagedStatic<TypeMap<StructValType, StructType> > StructTypes;
1154
1155 StructType *StructType::get(const std::vector<const Type*> &ETypes,
1156                             bool isPacked) {
1157   StructValType STV(ETypes, isPacked);
1158   StructType *ST = StructTypes->get(STV);
1159   if (ST) return ST;
1160
1161   // Value not found.  Derive a new type!
1162   ST = (StructType*) operator new(sizeof(StructType) +
1163                                   sizeof(PATypeHandle) * ETypes.size());
1164   new (ST) StructType(ETypes, isPacked);
1165   StructTypes->add(STV, ST);
1166
1167 #ifdef DEBUG_MERGE_TYPES
1168   DOUT << "Derived new type: " << *ST << "\n";
1169 #endif
1170   return ST;
1171 }
1172
1173 StructType *StructType::get(const Type *type, ...) {
1174   va_list ap;
1175   std::vector<const llvm::Type*> StructFields;
1176   va_start(ap, type);
1177   while (type) {
1178     StructFields.push_back(type);
1179     type = va_arg(ap, llvm::Type*);
1180   }
1181   return llvm::StructType::get(StructFields);
1182 }
1183
1184
1185
1186 //===----------------------------------------------------------------------===//
1187 // Pointer Type Factory...
1188 //
1189
1190 // PointerValType - Define a class to hold the key that goes into the TypeMap
1191 //
1192 namespace llvm {
1193 class PointerValType {
1194   const Type *ValTy;
1195   unsigned AddressSpace;
1196 public:
1197   PointerValType(const Type *val, unsigned as) : ValTy(val), AddressSpace(as) {}
1198
1199   static PointerValType get(const PointerType *PT) {
1200     return PointerValType(PT->getElementType(), PT->getAddressSpace());
1201   }
1202
1203   static unsigned hashTypeStructure(const PointerType *PT) {
1204     return getSubElementHash(PT);
1205   }
1206
1207   bool operator<(const PointerValType &MTV) const {
1208     if (AddressSpace < MTV.AddressSpace) return true;
1209     return AddressSpace == MTV.AddressSpace && ValTy < MTV.ValTy;
1210   }
1211 };
1212 }
1213
1214 static ManagedStatic<TypeMap<PointerValType, PointerType> > PointerTypes;
1215
1216 PointerType *PointerType::get(const Type *ValueType, unsigned AddressSpace) {
1217   assert(ValueType && "Can't get a pointer to <null> type!");
1218   assert(ValueType != Type::VoidTy &&
1219          "Pointer to void is not valid, use i8* instead!");
1220   assert(ValueType != Type::LabelTy && "Pointer to label is not valid!");
1221   assert((!isa<PointerType>(ValueType) ||
1222           cast<PointerType>(ValueType)->getElementType() != Type::MetadataTy)
1223          && "Pointer to metadata* is not valid!");
1224   PointerValType PVT(ValueType, AddressSpace);
1225
1226   PointerType *PT = PointerTypes->get(PVT);
1227   if (PT) return PT;
1228
1229   // Value not found.  Derive a new type!
1230   PointerTypes->add(PVT, PT = new PointerType(ValueType, AddressSpace));
1231
1232 #ifdef DEBUG_MERGE_TYPES
1233   DOUT << "Derived new type: " << *PT << "\n";
1234 #endif
1235   return PT;
1236 }
1237
1238 PointerType *Type::getPointerTo(unsigned addrs) const {
1239   return PointerType::get(this, addrs);
1240 }
1241
1242 //===----------------------------------------------------------------------===//
1243 //                     Derived Type Refinement Functions
1244 //===----------------------------------------------------------------------===//
1245
1246 // removeAbstractTypeUser - Notify an abstract type that a user of the class
1247 // no longer has a handle to the type.  This function is called primarily by
1248 // the PATypeHandle class.  When there are no users of the abstract type, it
1249 // is annihilated, because there is no way to get a reference to it ever again.
1250 //
1251 void Type::removeAbstractTypeUser(AbstractTypeUser *U) const {
1252   // Search from back to front because we will notify users from back to
1253   // front.  Also, it is likely that there will be a stack like behavior to
1254   // users that register and unregister users.
1255   //
1256   unsigned i;
1257   for (i = AbstractTypeUsers.size(); AbstractTypeUsers[i-1] != U; --i)
1258     assert(i != 0 && "AbstractTypeUser not in user list!");
1259
1260   --i;  // Convert to be in range 0 <= i < size()
1261   assert(i < AbstractTypeUsers.size() && "Index out of range!");  // Wraparound?
1262
1263   AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i);
1264
1265 #ifdef DEBUG_MERGE_TYPES
1266   DOUT << "  remAbstractTypeUser[" << (void*)this << ", "
1267        << *this << "][" << i << "] User = " << U << "\n";
1268 #endif
1269
1270   if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) {
1271 #ifdef DEBUG_MERGE_TYPES
1272     DOUT << "DELETEing unused abstract type: <" << *this
1273          << ">[" << (void*)this << "]" << "\n";
1274 #endif
1275     this->destroy();
1276   }
1277 }
1278
1279 // refineAbstractTypeTo - This function is used when it is discovered that
1280 // the 'this' abstract type is actually equivalent to the NewType specified.
1281 // This causes all users of 'this' to switch to reference the more concrete type
1282 // NewType and for 'this' to be deleted.
1283 //
1284 void DerivedType::refineAbstractTypeTo(const Type *NewType) {
1285   assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!");
1286   assert(this != NewType && "Can't refine to myself!");
1287   assert(ForwardType == 0 && "This type has already been refined!");
1288
1289   // The descriptions may be out of date.  Conservatively clear them all!
1290   if (AbstractTypeDescriptions.isConstructed())
1291     AbstractTypeDescriptions->clear();
1292
1293 #ifdef DEBUG_MERGE_TYPES
1294   DOUT << "REFINING abstract type [" << (void*)this << " "
1295        << *this << "] to [" << (void*)NewType << " "
1296        << *NewType << "]!\n";
1297 #endif
1298
1299   // Make sure to put the type to be refined to into a holder so that if IT gets
1300   // refined, that we will not continue using a dead reference...
1301   //
1302   PATypeHolder NewTy(NewType);
1303
1304   // Any PATypeHolders referring to this type will now automatically forward to
1305   // the type we are resolved to.
1306   ForwardType = NewType;
1307   if (NewType->isAbstract())
1308     cast<DerivedType>(NewType)->addRef();
1309
1310   // Add a self use of the current type so that we don't delete ourself until
1311   // after the function exits.
1312   //
1313   PATypeHolder CurrentTy(this);
1314
1315   // To make the situation simpler, we ask the subclass to remove this type from
1316   // the type map, and to replace any type uses with uses of non-abstract types.
1317   // This dramatically limits the amount of recursive type trouble we can find
1318   // ourselves in.
1319   dropAllTypeUses();
1320
1321   // Iterate over all of the uses of this type, invoking callback.  Each user
1322   // should remove itself from our use list automatically.  We have to check to
1323   // make sure that NewTy doesn't _become_ 'this'.  If it does, resolving types
1324   // will not cause users to drop off of the use list.  If we resolve to ourself
1325   // we succeed!
1326   //
1327   while (!AbstractTypeUsers.empty() && NewTy != this) {
1328     AbstractTypeUser *User = AbstractTypeUsers.back();
1329
1330     unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize;
1331 #ifdef DEBUG_MERGE_TYPES
1332     DOUT << " REFINING user " << OldSize-1 << "[" << (void*)User
1333          << "] of abstract type [" << (void*)this << " "
1334          << *this << "] to [" << (void*)NewTy.get() << " "
1335          << *NewTy << "]!\n";
1336 #endif
1337     User->refineAbstractType(this, NewTy);
1338
1339     assert(AbstractTypeUsers.size() != OldSize &&
1340            "AbsTyUser did not remove self from user list!");
1341   }
1342
1343   // If we were successful removing all users from the type, 'this' will be
1344   // deleted when the last PATypeHolder is destroyed or updated from this type.
1345   // This may occur on exit of this function, as the CurrentTy object is
1346   // destroyed.
1347 }
1348
1349 // notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type that
1350 // the current type has transitioned from being abstract to being concrete.
1351 //
1352 void DerivedType::notifyUsesThatTypeBecameConcrete() {
1353 #ifdef DEBUG_MERGE_TYPES
1354   DOUT << "typeIsREFINED type: " << (void*)this << " " << *this << "\n";
1355 #endif
1356
1357   unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize;
1358   while (!AbstractTypeUsers.empty()) {
1359     AbstractTypeUser *ATU = AbstractTypeUsers.back();
1360     ATU->typeBecameConcrete(this);
1361
1362     assert(AbstractTypeUsers.size() < OldSize-- &&
1363            "AbstractTypeUser did not remove itself from the use list!");
1364   }
1365 }
1366
1367 // refineAbstractType - Called when a contained type is found to be more
1368 // concrete - this could potentially change us from an abstract type to a
1369 // concrete type.
1370 //
1371 void FunctionType::refineAbstractType(const DerivedType *OldType,
1372                                       const Type *NewType) {
1373   FunctionTypes->RefineAbstractType(this, OldType, NewType);
1374 }
1375
1376 void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) {
1377   FunctionTypes->TypeBecameConcrete(this, AbsTy);
1378 }
1379
1380
1381 // refineAbstractType - Called when a contained type is found to be more
1382 // concrete - this could potentially change us from an abstract type to a
1383 // concrete type.
1384 //
1385 void ArrayType::refineAbstractType(const DerivedType *OldType,
1386                                    const Type *NewType) {
1387   ArrayTypes->RefineAbstractType(this, OldType, NewType);
1388 }
1389
1390 void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) {
1391   ArrayTypes->TypeBecameConcrete(this, AbsTy);
1392 }
1393
1394 // refineAbstractType - Called when a contained type is found to be more
1395 // concrete - this could potentially change us from an abstract type to a
1396 // concrete type.
1397 //
1398 void VectorType::refineAbstractType(const DerivedType *OldType,
1399                                    const Type *NewType) {
1400   VectorTypes->RefineAbstractType(this, OldType, NewType);
1401 }
1402
1403 void VectorType::typeBecameConcrete(const DerivedType *AbsTy) {
1404   VectorTypes->TypeBecameConcrete(this, AbsTy);
1405 }
1406
1407 // refineAbstractType - Called when a contained type is found to be more
1408 // concrete - this could potentially change us from an abstract type to a
1409 // concrete type.
1410 //
1411 void StructType::refineAbstractType(const DerivedType *OldType,
1412                                     const Type *NewType) {
1413   StructTypes->RefineAbstractType(this, OldType, NewType);
1414 }
1415
1416 void StructType::typeBecameConcrete(const DerivedType *AbsTy) {
1417   StructTypes->TypeBecameConcrete(this, AbsTy);
1418 }
1419
1420 // refineAbstractType - Called when a contained type is found to be more
1421 // concrete - this could potentially change us from an abstract type to a
1422 // concrete type.
1423 //
1424 void PointerType::refineAbstractType(const DerivedType *OldType,
1425                                      const Type *NewType) {
1426   PointerTypes->RefineAbstractType(this, OldType, NewType);
1427 }
1428
1429 void PointerType::typeBecameConcrete(const DerivedType *AbsTy) {
1430   PointerTypes->TypeBecameConcrete(this, AbsTy);
1431 }
1432
1433 bool SequentialType::indexValid(const Value *V) const {
1434   if (isa<IntegerType>(V->getType()))
1435     return true;
1436   return false;
1437 }
1438
1439 namespace llvm {
1440 std::ostream &operator<<(std::ostream &OS, const Type *T) {
1441   if (T == 0)
1442     OS << "<null> value!\n";
1443   else
1444     T->print(OS);
1445   return OS;
1446 }
1447
1448 std::ostream &operator<<(std::ostream &OS, const Type &T) {
1449   T.print(OS);
1450   return OS;
1451 }
1452
1453 raw_ostream &operator<<(raw_ostream &OS, const Type &T) {
1454   T.print(OS);
1455   return OS;
1456 }
1457 }