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 // canLosslesslyBitCastTo - Return true if this type can be converted to
 139 // 'Ty' without any reinterpretation of bits.  For example, i8* to i32*.
 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 /// isValidArgumentType - Return true if the specified type is valid as an
 322 /// argument type.
 323 bool FunctionType::isValidArgumentType(const Type *ArgTy) {
 324   if ((!ArgTy->isFirstClassType() && !isa<OpaqueType>(ArgTy)) ||
 325       (isa<PointerType>(ArgTy) &&
 326        cast<PointerType>(ArgTy)->getElementType() == Type::MetadataTy))
 327     return false;
 328
 329   return true;
 330 }
 331
 332 FunctionType::FunctionType(const Type *Result,
 333                            const std::vector<const Type*> &Params,
 334                            bool IsVarArgs)
 335   : DerivedType(FunctionTyID), isVarArgs(IsVarArgs) {
 336   ContainedTys = reinterpret_cast<PATypeHandle*>(this+1);
 337   NumContainedTys = Params.size() + 1; // + 1 for result type
 338   assert(isValidReturnType(Result) && "invalid return type for function");
 339
 340
 341   bool isAbstract = Result->isAbstract();
 342   new (&ContainedTys[0]) PATypeHandle(Result, this);
 343
 344   for (unsigned i = 0; i != Params.size(); ++i) {
 345     assert(isValidArgumentType(Params[i]) &&
 346            "Not a valid type for function argument!");
 347     new (&ContainedTys[i+1]) PATypeHandle(Params[i], this);
 348     isAbstract |= Params[i]->isAbstract();
 349   }
 350
 351   // Calculate whether or not this type is abstract
 352   setAbstract(isAbstract);
 353 }
 354
 355 StructType::StructType(const std::vector<const Type*> &Types, bool isPacked)
 356   : CompositeType(StructTyID) {
 357   ContainedTys = reinterpret_cast<PATypeHandle*>(this + 1);
 358   NumContainedTys = Types.size();
 359   setSubclassData(isPacked);
 360   bool isAbstract = false;
 361   for (unsigned i = 0; i < Types.size(); ++i) {
 362     assert(Types[i] && "<null> type for structure field!");
 363     assert(isValidElementType(Types[i]) &&
 364            "Invalid type for structure element!");
 365     new (&ContainedTys[i]) PATypeHandle(Types[i], this);
 366     isAbstract |= Types[i]->isAbstract();
 367   }
 368
 369   // Calculate whether or not this type is abstract
 370   setAbstract(isAbstract);
 371 }
 372
 373 ArrayType::ArrayType(const Type *ElType, uint64_t NumEl)
 374   : SequentialType(ArrayTyID, ElType) {
 375   NumElements = NumEl;
 376
 377   // Calculate whether or not this type is abstract
 378   setAbstract(ElType->isAbstract());
 379 }
 380
 381 VectorType::VectorType(const Type *ElType, unsigned NumEl)
 382   : SequentialType(VectorTyID, ElType) {
 383   NumElements = NumEl;
 384   setAbstract(ElType->isAbstract());
 385   assert(NumEl > 0 && "NumEl of a VectorType must be greater than 0");
 386   assert(isValidElementType(ElType) &&
 387          "Elements of a VectorType must be a primitive type");
 388
 389 }
 390
 391
 392 PointerType::PointerType(const Type *E, unsigned AddrSpace)
 393   : SequentialType(PointerTyID, E) {
 394   AddressSpace = AddrSpace;
 395   // Calculate whether or not this type is abstract
 396   setAbstract(E->isAbstract());
 397 }
 398
 399 OpaqueType::OpaqueType() : DerivedType(OpaqueTyID) {
 400   setAbstract(true);
 401 #ifdef DEBUG_MERGE_TYPES
 402   DOUT << "Derived new type: " << *this << "\n";
 403 #endif
 404 }
 405
 406 void PATypeHolder::destroy() {
 407   Ty = 0;
 408 }
 409
 410 // dropAllTypeUses - When this (abstract) type is resolved to be equal to
 411 // another (more concrete) type, we must eliminate all references to other
 412 // types, to avoid some circular reference problems.
 413 void DerivedType::dropAllTypeUses() {
 414   if (NumContainedTys != 0) {
 415     // The type must stay abstract.  To do this, we insert a pointer to a type
 416     // that will never get resolved, thus will always be abstract.
 417     static Type *AlwaysOpaqueTy = OpaqueType::get();
 418     static PATypeHolder Holder(AlwaysOpaqueTy);
 419     ContainedTys[0] = AlwaysOpaqueTy;
 420
 421     // Change the rest of the types to be Int32Ty's.  It doesn't matter what we
 422     // pick so long as it doesn't point back to this type.  We choose something
 423     // concrete to avoid overhead for adding to AbstracTypeUser lists and stuff.
 424     for (unsigned i = 1, e = NumContainedTys; i != e; ++i)
 425       ContainedTys[i] = Type::Int32Ty;
 426   }
 427 }
 428
 429
 430 namespace {
 431
 432 /// TypePromotionGraph and graph traits - this is designed to allow us to do
 433 /// efficient SCC processing of type graphs.  This is the exact same as
 434 /// GraphTraits<Type*>, except that we pretend that concrete types have no
 435 /// children to avoid processing them.
 436 struct TypePromotionGraph {
 437   Type *Ty;
 438   TypePromotionGraph(Type *T) : Ty(T) {}
 439 };
 440
 441 }
 442
 443 namespace llvm {
 444   template <> struct GraphTraits<TypePromotionGraph> {
 445     typedef Type NodeType;
 446     typedef Type::subtype_iterator ChildIteratorType;
 447
 448     static inline NodeType *getEntryNode(TypePromotionGraph G) { return G.Ty; }
 449     static inline ChildIteratorType child_begin(NodeType *N) {
 450       if (N->isAbstract())
 451         return N->subtype_begin();
 452       else           // No need to process children of concrete types.
 453         return N->subtype_end();
 454     }
 455     static inline ChildIteratorType child_end(NodeType *N) {
 456       return N->subtype_end();
 457     }
 458   };
 459 }
 460
 461
 462 // PromoteAbstractToConcrete - This is a recursive function that walks a type
 463 // graph calculating whether or not a type is abstract.
 464 //
 465 void Type::PromoteAbstractToConcrete() {
 466   if (!isAbstract()) return;
 467
 468   scc_iterator<TypePromotionGraph> SI = scc_begin(TypePromotionGraph(this));
 469   scc_iterator<TypePromotionGraph> SE = scc_end  (TypePromotionGraph(this));
 470
 471   for (; SI != SE; ++SI) {
 472     std::vector<Type*> &SCC = *SI;
 473
 474     // Concrete types are leaves in the tree.  Since an SCC will either be all
 475     // abstract or all concrete, we only need to check one type.
 476     if (SCC[0]->isAbstract()) {
 477       if (isa<OpaqueType>(SCC[0]))
 478         return;     // Not going to be concrete, sorry.
 479
 480       // If all of the children of all of the types in this SCC are concrete,
 481       // then this SCC is now concrete as well.  If not, neither this SCC, nor
 482       // any parent SCCs will be concrete, so we might as well just exit.
 483       for (unsigned i = 0, e = SCC.size(); i != e; ++i)
 484         for (Type::subtype_iterator CI = SCC[i]->subtype_begin(),
 485                E = SCC[i]->subtype_end(); CI != E; ++CI)
 486           if ((*CI)->isAbstract())
 487             // If the child type is in our SCC, it doesn't make the entire SCC
 488             // abstract unless there is a non-SCC abstract type.
 489             if (std::find(SCC.begin(), SCC.end(), *CI) == SCC.end())
 490               return;               // Not going to be concrete, sorry.
 491
 492       // Okay, we just discovered this whole SCC is now concrete, mark it as
 493       // such!
 494       for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
 495         assert(SCC[i]->isAbstract() && "Why are we processing concrete types?");
 496
 497         SCC[i]->setAbstract(false);
 498       }
 499
 500       for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
 501         assert(!SCC[i]->isAbstract() && "Concrete type became abstract?");
 502         // The type just became concrete, notify all users!
 503         cast<DerivedType>(SCC[i])->notifyUsesThatTypeBecameConcrete();
 504       }
 505     }
 506   }
 507 }
 508
 509
 510 //===----------------------------------------------------------------------===//
 511 //                      Type Structural Equality Testing
 512 //===----------------------------------------------------------------------===//
 513
 514 // TypesEqual - Two types are considered structurally equal if they have the
 515 // same "shape": Every level and element of the types have identical primitive
 516 // ID's, and the graphs have the same edges/nodes in them.  Nodes do not have to
 517 // be pointer equals to be equivalent though.  This uses an optimistic algorithm
 518 // that assumes that two graphs are the same until proven otherwise.
 519 //
 520 static bool TypesEqual(const Type *Ty, const Type *Ty2,
 521                        std::map<const Type *, const Type *> &EqTypes) {
 522   if (Ty == Ty2) return true;
 523   if (Ty->getTypeID() != Ty2->getTypeID()) return false;
 524   if (isa<OpaqueType>(Ty))
 525     return false;  // Two unequal opaque types are never equal
 526
 527   std::map<const Type*, const Type*>::iterator It = EqTypes.find(Ty);
 528   if (It != EqTypes.end())
 529     return It->second == Ty2;    // Looping back on a type, check for equality
 530
 531   // Otherwise, add the mapping to the table to make sure we don't get
 532   // recursion on the types...
 533   EqTypes.insert(It, std::make_pair(Ty, Ty2));
 534
 535   // Two really annoying special cases that breaks an otherwise nice simple
 536   // algorithm is the fact that arraytypes have sizes that differentiates types,
 537   // and that function types can be varargs or not.  Consider this now.
 538   //
 539   if (const IntegerType *ITy = dyn_cast<IntegerType>(Ty)) {
 540     const IntegerType *ITy2 = cast<IntegerType>(Ty2);
 541     return ITy->getBitWidth() == ITy2->getBitWidth();
 542   } else if (const PointerType *PTy = dyn_cast<PointerType>(Ty)) {
 543     const PointerType *PTy2 = cast<PointerType>(Ty2);
 544     return PTy->getAddressSpace() == PTy2->getAddressSpace() &&
 545            TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
 546   } else if (const StructType *STy = dyn_cast<StructType>(Ty)) {
 547     const StructType *STy2 = cast<StructType>(Ty2);
 548     if (STy->getNumElements() != STy2->getNumElements()) return false;
 549     if (STy->isPacked() != STy2->isPacked()) return false;
 550     for (unsigned i = 0, e = STy2->getNumElements(); i != e; ++i)
 551       if (!TypesEqual(STy->getElementType(i), STy2->getElementType(i), EqTypes))
 552         return false;
 553     return true;
 554   } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
 555     const ArrayType *ATy2 = cast<ArrayType>(Ty2);
 556     return ATy->getNumElements() == ATy2->getNumElements() &&
 557            TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes);
 558   } else if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
 559     const VectorType *PTy2 = cast<VectorType>(Ty2);
 560     return PTy->getNumElements() == PTy2->getNumElements() &&
 561            TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
 562   } else if (const FunctionType *FTy = dyn_cast<FunctionType>(Ty)) {
 563     const FunctionType *FTy2 = cast<FunctionType>(Ty2);
 564     if (FTy->isVarArg() != FTy2->isVarArg() ||
 565         FTy->getNumParams() != FTy2->getNumParams() ||
 566         !TypesEqual(FTy->getReturnType(), FTy2->getReturnType(), EqTypes))
 567       return false;
 568     for (unsigned i = 0, e = FTy2->getNumParams(); i != e; ++i) {
 569       if (!TypesEqual(FTy->getParamType(i), FTy2->getParamType(i), EqTypes))
 570         return false;
 571     }
 572     return true;
 573   } else {
 574     assert(0 && "Unknown derived type!");
 575     return false;
 576   }
 577 }
 578
 579 static bool TypesEqual(const Type *Ty, const Type *Ty2) {
 580   std::map<const Type *, const Type *> EqTypes;
 581   return TypesEqual(Ty, Ty2, EqTypes);
 582 }
 583
 584 // AbstractTypeHasCycleThrough - Return true there is a path from CurTy to
 585 // TargetTy in the type graph.  We know that Ty is an abstract type, so if we
 586 // ever reach a non-abstract type, we know that we don't need to search the
 587 // subgraph.
 588 static bool AbstractTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
 589                                 SmallPtrSet<const Type*, 128> &VisitedTypes) {
 590   if (TargetTy == CurTy) return true;
 591   if (!CurTy->isAbstract()) return false;
 592
 593   if (!VisitedTypes.insert(CurTy))
 594     return false;  // Already been here.
 595
 596   for (Type::subtype_iterator I = CurTy->subtype_begin(),
 597        E = CurTy->subtype_end(); I != E; ++I)
 598     if (AbstractTypeHasCycleThrough(TargetTy, *I, VisitedTypes))
 599       return true;
 600   return false;
 601 }
 602
 603 static bool ConcreteTypeHasCycleThrough(const Type *TargetTy, const Type *CurTy,
 604                                 SmallPtrSet<const Type*, 128> &VisitedTypes) {
 605   if (TargetTy == CurTy) return true;
 606
 607   if (!VisitedTypes.insert(CurTy))
 608     return false;  // Already been here.
 609
 610   for (Type::subtype_iterator I = CurTy->subtype_begin(),
 611        E = CurTy->subtype_end(); I != E; ++I)
 612     if (ConcreteTypeHasCycleThrough(TargetTy, *I, VisitedTypes))
 613       return true;
 614   return false;
 615 }
 616
 617 /// TypeHasCycleThroughItself - Return true if the specified type has a cycle
 618 /// back to itself.
 619 static bool TypeHasCycleThroughItself(const Type *Ty) {
 620   SmallPtrSet<const Type*, 128> VisitedTypes;
 621
 622   if (Ty->isAbstract()) {  // Optimized case for abstract types.
 623     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 624          I != E; ++I)
 625       if (AbstractTypeHasCycleThrough(Ty, *I, VisitedTypes))
 626         return true;
 627   } else {
 628     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 629          I != E; ++I)
 630       if (ConcreteTypeHasCycleThrough(Ty, *I, VisitedTypes))
 631         return true;
 632   }
 633   return false;
 634 }
 635
 636 /// getSubElementHash - Generate a hash value for all of the SubType's of this
 637 /// type.  The hash value is guaranteed to be zero if any of the subtypes are
 638 /// an opaque type.  Otherwise we try to mix them in as well as possible, but do
 639 /// not look at the subtype's subtype's.
 640 static unsigned getSubElementHash(const Type *Ty) {
 641   unsigned HashVal = 0;
 642   for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 643        I != E; ++I) {
 644     HashVal *= 32;
 645     const Type *SubTy = I->get();
 646     HashVal += SubTy->getTypeID();
 647     switch (SubTy->getTypeID()) {
 648     default: break;
 649     case Type::OpaqueTyID: return 0;    // Opaque -> hash = 0 no matter what.
 650     case Type::IntegerTyID:
 651       HashVal ^= (cast<IntegerType>(SubTy)->getBitWidth() << 3);
 652       break;
 653     case Type::FunctionTyID:
 654       HashVal ^= cast<FunctionType>(SubTy)->getNumParams()*2 +
 655                  cast<FunctionType>(SubTy)->isVarArg();
 656       break;
 657     case Type::ArrayTyID:
 658       HashVal ^= cast<ArrayType>(SubTy)->getNumElements();
 659       break;
 660     case Type::VectorTyID:
 661       HashVal ^= cast<VectorType>(SubTy)->getNumElements();
 662       break;
 663     case Type::StructTyID:
 664       HashVal ^= cast<StructType>(SubTy)->getNumElements();
 665       break;
 666     case Type::PointerTyID:
 667       HashVal ^= cast<PointerType>(SubTy)->getAddressSpace();
 668       break;
 669     }
 670   }
 671   return HashVal ? HashVal : 1;  // Do not return zero unless opaque subty.
 672 }
 673
 674 //===----------------------------------------------------------------------===//
 675 //                       Derived Type Factory Functions
 676 //===----------------------------------------------------------------------===//
 677
 678 namespace llvm {
 679 class TypeMapBase {
 680 protected:
 681   /// TypesByHash - Keep track of types by their structure hash value.  Note
 682   /// that we only keep track of types that have cycles through themselves in
 683   /// this map.
 684   ///
 685   std::multimap<unsigned, PATypeHolder> TypesByHash;
 686
 687 public:
 688   ~TypeMapBase() {
 689     // PATypeHolder won't destroy non-abstract types.
 690     // We can't destroy them by simply iterating, because
 691     // they may contain references to each-other.
 692 #if 0
 693     for (std::multimap<unsigned, PATypeHolder>::iterator I
 694          = TypesByHash.begin(), E = TypesByHash.end(); I != E; ++I) {
 695       Type *Ty = const_cast<Type*>(I->second.Ty);
 696       I->second.destroy();
 697       // We can't invoke destroy or delete, because the type may
 698       // contain references to already freed types.
 699       // So we have to destruct the object the ugly way.
 700       if (Ty) {
 701         Ty->AbstractTypeUsers.clear();
 702         static_cast<const Type*>(Ty)->Type::~Type();
 703         operator delete(Ty);
 704       }
 705     }
 706 #endif
 707   }
 708
 709   void RemoveFromTypesByHash(unsigned Hash, const Type *Ty) {
 710     std::multimap<unsigned, PATypeHolder>::iterator I =
 711       TypesByHash.lower_bound(Hash);
 712     for (; I != TypesByHash.end() && I->first == Hash; ++I) {
 713       if (I->second == Ty) {
 714         TypesByHash.erase(I);
 715         return;
 716       }
 717     }
 718
 719     // This must be do to an opaque type that was resolved.  Switch down to hash
 720     // code of zero.
 721     assert(Hash && "Didn't find type entry!");
 722     RemoveFromTypesByHash(0, Ty);
 723   }
 724
 725   /// TypeBecameConcrete - When Ty gets a notification that TheType just became
 726   /// concrete, drop uses and make Ty non-abstract if we should.
 727   void TypeBecameConcrete(DerivedType *Ty, const DerivedType *TheType) {
 728     // If the element just became concrete, remove 'ty' from the abstract
 729     // type user list for the type.  Do this for as many times as Ty uses
 730     // OldType.
 731     for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
 732          I != E; ++I)
 733       if (I->get() == TheType)
 734         TheType->removeAbstractTypeUser(Ty);
 735
 736     // If the type is currently thought to be abstract, rescan all of our
 737     // subtypes to see if the type has just become concrete!  Note that this
 738     // may send out notifications to AbstractTypeUsers that types become
 739     // concrete.
 740     if (Ty->isAbstract())
 741       Ty->PromoteAbstractToConcrete();
 742   }
 743 };
 744 }
 745
 746
 747 // TypeMap - Make sure that only one instance of a particular type may be
 748 // created on any given run of the compiler... note that this involves updating
 749 // our map if an abstract type gets refined somehow.
 750 //
 751 namespace llvm {
 752 template<class ValType, class TypeClass>
 753 class TypeMap : public TypeMapBase {
 754   std::map<ValType, PATypeHolder> Map;
 755 public:
 756   typedef typename std::map<ValType, PATypeHolder>::iterator iterator;
 757   ~TypeMap() { print("ON EXIT"); }
 758
 759   inline TypeClass *get(const ValType &V) {
 760     iterator I = Map.find(V);
 761     return I != Map.end() ? cast<TypeClass>((Type*)I->second.get()) : 0;
 762   }
 763
 764   inline void add(const ValType &V, TypeClass *Ty) {
 765     Map.insert(std::make_pair(V, Ty));
 766
 767     // If this type has a cycle, remember it.
 768     TypesByHash.insert(std::make_pair(ValType::hashTypeStructure(Ty), Ty));
 769     print("add");
 770   }
 771
 772   /// RefineAbstractType - This method is called after we have merged a type
 773   /// with another one.  We must now either merge the type away with
 774   /// some other type or reinstall it in the map with it's new configuration.
 775   void RefineAbstractType(TypeClass *Ty, const DerivedType *OldType,
 776                         const Type *NewType) {
 777 #ifdef DEBUG_MERGE_TYPES
 778     DOUT << "RefineAbstractType(" << (void*)OldType << "[" << *OldType
 779          << "], " << (void*)NewType << " [" << *NewType << "])\n";
 780 #endif
 781
 782     // Otherwise, we are changing one subelement type into another.  Clearly the
 783     // OldType must have been abstract, making us abstract.
 784     assert(Ty->isAbstract() && "Refining a non-abstract type!");
 785     assert(OldType != NewType);
 786
 787     // Make a temporary type holder for the type so that it doesn't disappear on
 788     // us when we erase the entry from the map.
 789     PATypeHolder TyHolder = Ty;
 790
 791     // The old record is now out-of-date, because one of the children has been
 792     // updated.  Remove the obsolete entry from the map.
 793     unsigned NumErased = Map.erase(ValType::get(Ty));
 794     assert(NumErased && "Element not found!"); NumErased = NumErased;
 795
 796     // Remember the structural hash for the type before we start hacking on it,
 797     // in case we need it later.
 798     unsigned OldTypeHash = ValType::hashTypeStructure(Ty);
 799
 800     // Find the type element we are refining... and change it now!
 801     for (unsigned i = 0, e = Ty->getNumContainedTypes(); i != e; ++i)
 802       if (Ty->ContainedTys[i] == OldType)
 803         Ty->ContainedTys[i] = NewType;
 804     unsigned NewTypeHash = ValType::hashTypeStructure(Ty);
 805
 806     // If there are no cycles going through this node, we can do a simple,
 807     // efficient lookup in the map, instead of an inefficient nasty linear
 808     // lookup.
 809     if (!TypeHasCycleThroughItself(Ty)) {
 810       typename std::map<ValType, PATypeHolder>::iterator I;
 811       bool Inserted;
 812
 813       tie(I, Inserted) = Map.insert(std::make_pair(ValType::get(Ty), Ty));
 814       if (!Inserted) {
 815         // Refined to a different type altogether?
 816         RemoveFromTypesByHash(OldTypeHash, Ty);
 817
 818         // We already have this type in the table.  Get rid of the newly refined
 819         // type.
 820         TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
 821         Ty->refineAbstractTypeTo(NewTy);
 822         return;
 823       }
 824     } else {
 825       // Now we check to see if there is an existing entry in the table which is
 826       // structurally identical to the newly refined type.  If so, this type
 827       // gets refined to the pre-existing type.
 828       //
 829       std::multimap<unsigned, PATypeHolder>::iterator I, E, Entry;
 830       tie(I, E) = TypesByHash.equal_range(NewTypeHash);
 831       Entry = E;
 832       for (; I != E; ++I) {
 833         if (I->second == Ty) {
 834           // Remember the position of the old type if we see it in our scan.
 835           Entry = I;
 836         } else {
 837           if (TypesEqual(Ty, I->second)) {
 838             TypeClass *NewTy = cast<TypeClass>((Type*)I->second.get());
 839
 840             // Remove the old entry form TypesByHash.  If the hash values differ
 841             // now, remove it from the old place.  Otherwise, continue scanning
 842             // withing this hashcode to reduce work.
 843             if (NewTypeHash != OldTypeHash) {
 844               RemoveFromTypesByHash(OldTypeHash, Ty);
 845             } else {
 846               if (Entry == E) {
 847                 // Find the location of Ty in the TypesByHash structure if we
 848                 // haven't seen it already.
 849                 while (I->second != Ty) {
 850                   ++I;
 851                   assert(I != E && "Structure doesn't contain type??");
 852                 }
 853                 Entry = I;
 854               }
 855               TypesByHash.erase(Entry);
 856             }
 857             Ty->refineAbstractTypeTo(NewTy);
 858             return;
 859           }
 860         }
 861       }
 862
 863       // If there is no existing type of the same structure, we reinsert an
 864       // updated record into the map.
 865       Map.insert(std::make_pair(ValType::get(Ty), Ty));
 866     }
 867
 868     // If the hash codes differ, update TypesByHash
 869     if (NewTypeHash != OldTypeHash) {
 870       RemoveFromTypesByHash(OldTypeHash, Ty);
 871       TypesByHash.insert(std::make_pair(NewTypeHash, Ty));
 872     }
 873
 874     // If the type is currently thought to be abstract, rescan all of our
 875     // subtypes to see if the type has just become concrete!  Note that this
 876     // may send out notifications to AbstractTypeUsers that types become
 877     // concrete.
 878     if (Ty->isAbstract())
 879       Ty->PromoteAbstractToConcrete();
 880   }
 881
 882   void print(const char *Arg) const {
 883 #ifdef DEBUG_MERGE_TYPES
 884     DOUT << "TypeMap<>::" << Arg << " table contents:\n";
 885     unsigned i = 0;
 886     for (typename std::map<ValType, PATypeHolder>::const_iterator I
 887            = Map.begin(), E = Map.end(); I != E; ++I)
 888       DOUT << " " << (++i) << ". " << (void*)I->second.get() << " "
 889            << *I->second.get() << "\n";
 890 #endif
 891   }
 892
 893   void dump() const { print("dump output"); }
 894 };
 895 }
 896
 897
 898 //===----------------------------------------------------------------------===//
 899 // Function Type Factory and Value Class...
 900 //
 901
 902 //===----------------------------------------------------------------------===//
 903 // Integer Type Factory...
 904 //
 905 namespace llvm {
 906 class IntegerValType {
 907   uint32_t bits;
 908 public:
 909   IntegerValType(uint16_t numbits) : bits(numbits) {}
 910
 911   static IntegerValType get(const IntegerType *Ty) {
 912     return IntegerValType(Ty->getBitWidth());
 913   }
 914
 915   static unsigned hashTypeStructure(const IntegerType *Ty) {
 916     return (unsigned)Ty->getBitWidth();
 917   }
 918
 919   inline bool operator<(const IntegerValType &IVT) const {
 920     return bits < IVT.bits;
 921   }
 922 };
 923 }
 924
 925 static ManagedStatic<TypeMap<IntegerValType, IntegerType> > IntegerTypes;
 926
 927 const IntegerType *IntegerType::get(unsigned NumBits) {
 928   assert(NumBits >= MIN_INT_BITS && "bitwidth too small");
 929   assert(NumBits <= MAX_INT_BITS && "bitwidth too large");
 930
 931   // Check for the built-in integer types
 932   switch (NumBits) {
 933     case  1: return cast<IntegerType>(Type::Int1Ty);
 934     case  8: return cast<IntegerType>(Type::Int8Ty);
 935     case 16: return cast<IntegerType>(Type::Int16Ty);
 936     case 32: return cast<IntegerType>(Type::Int32Ty);
 937     case 64: return cast<IntegerType>(Type::Int64Ty);
 938     default:
 939       break;
 940   }
 941
 942   IntegerValType IVT(NumBits);
 943   IntegerType *ITy = IntegerTypes->get(IVT);
 944   if (ITy) return ITy;           // Found a match, return it!
 945
 946   // Value not found.  Derive a new type!
 947   ITy = new IntegerType(NumBits);
 948   IntegerTypes->add(IVT, ITy);
 949
 950 #ifdef DEBUG_MERGE_TYPES
 951   DOUT << "Derived new type: " << *ITy << "\n";
 952 #endif
 953   return ITy;
 954 }
 955
 956 bool IntegerType::isPowerOf2ByteWidth() const {
 957   unsigned BitWidth = getBitWidth();
 958   return (BitWidth > 7) && isPowerOf2_32(BitWidth);
 959 }
 960
 961 APInt IntegerType::getMask() const {
 962   return APInt::getAllOnesValue(getBitWidth());
 963 }
 964
 965 // FunctionValType - Define a class to hold the key that goes into the TypeMap
 966 //
 967 namespace llvm {
 968 class FunctionValType {
 969   const Type *RetTy;
 970   std::vector<const Type*> ArgTypes;
 971   bool isVarArg;
 972 public:
 973   FunctionValType(const Type *ret, const std::vector<const Type*> &args,
 974                   bool isVA) : RetTy(ret), ArgTypes(args), isVarArg(isVA) {}
 975
 976   static FunctionValType get(const FunctionType *FT);
 977
 978   static unsigned hashTypeStructure(const FunctionType *FT) {
 979     unsigned Result = FT->getNumParams()*2 + FT->isVarArg();
 980     return Result;
 981   }
 982
 983   inline bool operator<(const FunctionValType &MTV) const {
 984     if (RetTy < MTV.RetTy) return true;
 985     if (RetTy > MTV.RetTy) return false;
 986     if (isVarArg < MTV.isVarArg) return true;
 987     if (isVarArg > MTV.isVarArg) return false;
 988     if (ArgTypes < MTV.ArgTypes) return true;
 989     if (ArgTypes > MTV.ArgTypes) return false;
 990     return false;
 991   }
 992 };
 993 }
 994
 995 // Define the actual map itself now...
 996 static ManagedStatic<TypeMap<FunctionValType, FunctionType> > FunctionTypes;
 997
 998 FunctionValType FunctionValType::get(const FunctionType *FT) {
 999   // Build up a FunctionValType
1000   std::vector<const Type *> ParamTypes;
1001   ParamTypes.reserve(FT->getNumParams());
1002   for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
1003     ParamTypes.push_back(FT->getParamType(i));
1004   return FunctionValType(FT->getReturnType(), ParamTypes, FT->isVarArg());
1005 }
1006
1007
1008 // FunctionType::get - The factory function for the FunctionType class...
1009 FunctionType *FunctionType::get(const Type *ReturnType,
1010                                 const std::vector<const Type*> &Params,
1011                                 bool isVarArg) {
1012   FunctionValType VT(ReturnType, Params, isVarArg);
1013   FunctionType *FT = FunctionTypes->get(VT);
1014   if (FT)
1015     return FT;
1016
1017   FT = (FunctionType*) operator new(sizeof(FunctionType) +
1018                                     sizeof(PATypeHandle)*(Params.size()+1));
1019   new (FT) FunctionType(ReturnType, Params, isVarArg);
1020   FunctionTypes->add(VT, FT);
1021
1022 #ifdef DEBUG_MERGE_TYPES
1023   DOUT << "Derived new type: " << FT << "\n";
1024 #endif
1025   return FT;
1026 }
1027
1028 //===----------------------------------------------------------------------===//
1029 // Array Type Factory...
1030 //
1031 namespace llvm {
1032 class ArrayValType {
1033   const Type *ValTy;
1034   uint64_t Size;
1035 public:
1036   ArrayValType(const Type *val, uint64_t sz) : ValTy(val), Size(sz) {}
1037
1038   static ArrayValType get(const ArrayType *AT) {
1039     return ArrayValType(AT->getElementType(), AT->getNumElements());
1040   }
1041
1042   static unsigned hashTypeStructure(const ArrayType *AT) {
1043     return (unsigned)AT->getNumElements();
1044   }
1045
1046   inline bool operator<(const ArrayValType &MTV) const {
1047     if (Size < MTV.Size) return true;
1048     return Size == MTV.Size && ValTy < MTV.ValTy;
1049   }
1050 };
1051 }
1052 static ManagedStatic<TypeMap<ArrayValType, ArrayType> > ArrayTypes;
1053
1054
1055 ArrayType *ArrayType::get(const Type *ElementType, uint64_t NumElements) {
1056   assert(ElementType && "Can't get array of <null> types!");
1057   assert(isValidElementType(ElementType) && "Invalid type for array element!");
1058
1059   ArrayValType AVT(ElementType, NumElements);
1060   ArrayType *AT = ArrayTypes->get(AVT);
1061   if (AT) return AT;           // Found a match, return it!
1062
1063   // Value not found.  Derive a new type!
1064   ArrayTypes->add(AVT, AT = new ArrayType(ElementType, NumElements));
1065
1066 #ifdef DEBUG_MERGE_TYPES
1067   DOUT << "Derived new type: " << *AT << "\n";
1068 #endif
1069   return AT;
1070 }
1071
1072 bool ArrayType::isValidElementType(const Type *ElemTy) {
1073   if (ElemTy == Type::VoidTy || ElemTy == Type::LabelTy ||
1074       ElemTy == Type::MetadataTy)
1075     return false;
1076
1077   if (const PointerType *PTy = dyn_cast<PointerType>(ElemTy))
1078     if (PTy->getElementType() == Type::MetadataTy)
1079       return false;
1080
1081   return true;
1082 }
1083
1084
1085 //===----------------------------------------------------------------------===//
1086 // Vector Type Factory...
1087 //
1088 namespace llvm {
1089 class VectorValType {
1090   const Type *ValTy;
1091   unsigned Size;
1092 public:
1093   VectorValType(const Type *val, int sz) : ValTy(val), Size(sz) {}
1094
1095   static VectorValType get(const VectorType *PT) {
1096     return VectorValType(PT->getElementType(), PT->getNumElements());
1097   }
1098
1099   static unsigned hashTypeStructure(const VectorType *PT) {
1100     return PT->getNumElements();
1101   }
1102
1103   inline bool operator<(const VectorValType &MTV) const {
1104     if (Size < MTV.Size) return true;
1105     return Size == MTV.Size && ValTy < MTV.ValTy;
1106   }
1107 };
1108 }
1109 static ManagedStatic<TypeMap<VectorValType, VectorType> > VectorTypes;
1110
1111
1112 VectorType *VectorType::get(const Type *ElementType, unsigned NumElements) {
1113   assert(ElementType && "Can't get vector of <null> types!");
1114
1115   VectorValType PVT(ElementType, NumElements);
1116   VectorType *PT = VectorTypes->get(PVT);
1117   if (PT) return PT;           // Found a match, return it!
1118
1119   // Value not found.  Derive a new type!
1120   VectorTypes->add(PVT, PT = new VectorType(ElementType, NumElements));
1121
1122 #ifdef DEBUG_MERGE_TYPES
1123   DOUT << "Derived new type: " << *PT << "\n";
1124 #endif
1125   return PT;
1126 }
1127
1128 bool VectorType::isValidElementType(const Type *ElemTy) {
1129   if (ElemTy->isInteger() || ElemTy->isFloatingPoint() ||
1130       isa<OpaqueType>(ElemTy))
1131     return true;
1132
1133   return false;
1134 }
1135
1136 //===----------------------------------------------------------------------===//
1137 // Struct Type Factory...
1138 //
1139
1140 namespace llvm {
1141 // StructValType - Define a class to hold the key that goes into the TypeMap
1142 //
1143 class StructValType {
1144   std::vector<const Type*> ElTypes;
1145   bool packed;
1146 public:
1147   StructValType(const std::vector<const Type*> &args, bool isPacked)
1148     : ElTypes(args), packed(isPacked) {}
1149
1150   static StructValType get(const StructType *ST) {
1151     std::vector<const Type *> ElTypes;
1152     ElTypes.reserve(ST->getNumElements());
1153     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i)
1154       ElTypes.push_back(ST->getElementType(i));
1155
1156     return StructValType(ElTypes, ST->isPacked());
1157   }
1158
1159   static unsigned hashTypeStructure(const StructType *ST) {
1160     return ST->getNumElements();
1161   }
1162
1163   inline bool operator<(const StructValType &STV) const {
1164     if (ElTypes < STV.ElTypes) return true;
1165     else if (ElTypes > STV.ElTypes) return false;
1166     else return (int)packed < (int)STV.packed;
1167   }
1168 };
1169 }
1170
1171 static ManagedStatic<TypeMap<StructValType, StructType> > StructTypes;
1172
1173 StructType *StructType::get(const std::vector<const Type*> &ETypes,
1174                             bool isPacked) {
1175   StructValType STV(ETypes, isPacked);
1176   StructType *ST = StructTypes->get(STV);
1177   if (ST) return ST;
1178
1179   // Value not found.  Derive a new type!
1180   ST = (StructType*) operator new(sizeof(StructType) +
1181                                   sizeof(PATypeHandle) * ETypes.size());
1182   new (ST) StructType(ETypes, isPacked);
1183   StructTypes->add(STV, ST);
1184
1185 #ifdef DEBUG_MERGE_TYPES
1186   DOUT << "Derived new type: " << *ST << "\n";
1187 #endif
1188   return ST;
1189 }
1190
1191 StructType *StructType::get(const Type *type, ...) {
1192   va_list ap;
1193   std::vector<const llvm::Type*> StructFields;
1194   va_start(ap, type);
1195   while (type) {
1196     StructFields.push_back(type);
1197     type = va_arg(ap, llvm::Type*);
1198   }
1199   return llvm::StructType::get(StructFields);
1200 }
1201
1202 bool StructType::isValidElementType(const Type *ElemTy) {
1203   if (ElemTy == Type::VoidTy || ElemTy == Type::LabelTy ||
1204       ElemTy == Type::MetadataTy)
1205     return false;
1206
1207   if (const PointerType *PTy = dyn_cast<PointerType>(ElemTy))
1208     if (PTy->getElementType() == Type::MetadataTy)
1209       return false;
1210
1211   return true;
1212 }
1213
1214
1215 //===----------------------------------------------------------------------===//
1216 // Pointer Type Factory...
1217 //
1218
1219 // PointerValType - Define a class to hold the key that goes into the TypeMap
1220 //
1221 namespace llvm {
1222 class PointerValType {
1223   const Type *ValTy;
1224   unsigned AddressSpace;
1225 public:
1226   PointerValType(const Type *val, unsigned as) : ValTy(val), AddressSpace(as) {}
1227
1228   static PointerValType get(const PointerType *PT) {
1229     return PointerValType(PT->getElementType(), PT->getAddressSpace());
1230   }
1231
1232   static unsigned hashTypeStructure(const PointerType *PT) {
1233     return getSubElementHash(PT);
1234   }
1235
1236   bool operator<(const PointerValType &MTV) const {
1237     if (AddressSpace < MTV.AddressSpace) return true;
1238     return AddressSpace == MTV.AddressSpace && ValTy < MTV.ValTy;
1239   }
1240 };
1241 }
1242
1243 static ManagedStatic<TypeMap<PointerValType, PointerType> > PointerTypes;
1244
1245 PointerType *PointerType::get(const Type *ValueType, unsigned AddressSpace) {
1246   assert(ValueType && "Can't get a pointer to <null> type!");
1247   assert(ValueType != Type::VoidTy &&
1248          "Pointer to void is not valid, use i8* instead!");
1249   assert(isValidElementType(ValueType) && "Invalid type for pointer element!");
1250   PointerValType PVT(ValueType, AddressSpace);
1251
1252   PointerType *PT = PointerTypes->get(PVT);
1253   if (PT) return PT;
1254
1255   // Value not found.  Derive a new type!
1256   PointerTypes->add(PVT, PT = new PointerType(ValueType, AddressSpace));
1257
1258 #ifdef DEBUG_MERGE_TYPES
1259   DOUT << "Derived new type: " << *PT << "\n";
1260 #endif
1261   return PT;
1262 }
1263
1264 PointerType *Type::getPointerTo(unsigned addrs) const {
1265   return PointerType::get(this, addrs);
1266 }
1267
1268 bool PointerType::isValidElementType(const Type *ElemTy) {
1269   if (ElemTy == Type::VoidTy || ElemTy == Type::LabelTy)
1270     return false;
1271
1272   if (const PointerType *PTy = dyn_cast<PointerType>(ElemTy))
1273     if (PTy->getElementType() == Type::MetadataTy)
1274       return false;
1275
1276   return true;
1277 }
1278
1279
1280 //===----------------------------------------------------------------------===//
1281 //                     Derived Type Refinement Functions
1282 //===----------------------------------------------------------------------===//
1283
1284 // removeAbstractTypeUser - Notify an abstract type that a user of the class
1285 // no longer has a handle to the type.  This function is called primarily by
1286 // the PATypeHandle class.  When there are no users of the abstract type, it
1287 // is annihilated, because there is no way to get a reference to it ever again.
1288 //
1289 void Type::removeAbstractTypeUser(AbstractTypeUser *U) const {
1290   // Search from back to front because we will notify users from back to
1291   // front.  Also, it is likely that there will be a stack like behavior to
1292   // users that register and unregister users.
1293   //
1294   unsigned i;
1295   for (i = AbstractTypeUsers.size(); AbstractTypeUsers[i-1] != U; --i)
1296     assert(i != 0 && "AbstractTypeUser not in user list!");
1297
1298   --i;  // Convert to be in range 0 <= i < size()
1299   assert(i < AbstractTypeUsers.size() && "Index out of range!");  // Wraparound?
1300
1301   AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i);
1302
1303 #ifdef DEBUG_MERGE_TYPES
1304   DOUT << "  remAbstractTypeUser[" << (void*)this << ", "
1305        << *this << "][" << i << "] User = " << U << "\n";
1306 #endif
1307
1308   if (AbstractTypeUsers.empty() && getRefCount() == 0 && isAbstract()) {
1309 #ifdef DEBUG_MERGE_TYPES
1310     DOUT << "DELETEing unused abstract type: <" << *this
1311          << ">[" << (void*)this << "]" << "\n";
1312 #endif
1313     this->destroy();
1314   }
1315 }
1316
1317 // refineAbstractTypeTo - This function is used when it is discovered that
1318 // the 'this' abstract type is actually equivalent to the NewType specified.
1319 // This causes all users of 'this' to switch to reference the more concrete type
1320 // NewType and for 'this' to be deleted.
1321 //
1322 void DerivedType::refineAbstractTypeTo(const Type *NewType) {
1323   assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!");
1324   assert(this != NewType && "Can't refine to myself!");
1325   assert(ForwardType == 0 && "This type has already been refined!");
1326
1327   // The descriptions may be out of date.  Conservatively clear them all!
1328   if (AbstractTypeDescriptions.isConstructed())
1329     AbstractTypeDescriptions->clear();
1330
1331 #ifdef DEBUG_MERGE_TYPES
1332   DOUT << "REFINING abstract type [" << (void*)this << " "
1333        << *this << "] to [" << (void*)NewType << " "
1334        << *NewType << "]!\n";
1335 #endif
1336
1337   // Make sure to put the type to be refined to into a holder so that if IT gets
1338   // refined, that we will not continue using a dead reference...
1339   //
1340   PATypeHolder NewTy(NewType);
1341
1342   // Any PATypeHolders referring to this type will now automatically forward to
1343   // the type we are resolved to.
1344   ForwardType = NewType;
1345   if (NewType->isAbstract())
1346     cast<DerivedType>(NewType)->addRef();
1347
1348   // Add a self use of the current type so that we don't delete ourself until
1349   // after the function exits.
1350   //
1351   PATypeHolder CurrentTy(this);
1352
1353   // To make the situation simpler, we ask the subclass to remove this type from
1354   // the type map, and to replace any type uses with uses of non-abstract types.
1355   // This dramatically limits the amount of recursive type trouble we can find
1356   // ourselves in.
1357   dropAllTypeUses();
1358
1359   // Iterate over all of the uses of this type, invoking callback.  Each user
1360   // should remove itself from our use list automatically.  We have to check to
1361   // make sure that NewTy doesn't _become_ 'this'.  If it does, resolving types
1362   // will not cause users to drop off of the use list.  If we resolve to ourself
1363   // we succeed!
1364   //
1365   while (!AbstractTypeUsers.empty() && NewTy != this) {
1366     AbstractTypeUser *User = AbstractTypeUsers.back();
1367
1368     unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize;
1369 #ifdef DEBUG_MERGE_TYPES
1370     DOUT << " REFINING user " << OldSize-1 << "[" << (void*)User
1371          << "] of abstract type [" << (void*)this << " "
1372          << *this << "] to [" << (void*)NewTy.get() << " "
1373          << *NewTy << "]!\n";
1374 #endif
1375     User->refineAbstractType(this, NewTy);
1376
1377     assert(AbstractTypeUsers.size() != OldSize &&
1378            "AbsTyUser did not remove self from user list!");
1379   }
1380
1381   // If we were successful removing all users from the type, 'this' will be
1382   // deleted when the last PATypeHolder is destroyed or updated from this type.
1383   // This may occur on exit of this function, as the CurrentTy object is
1384   // destroyed.
1385 }
1386
1387 // notifyUsesThatTypeBecameConcrete - Notify AbstractTypeUsers of this type that
1388 // the current type has transitioned from being abstract to being concrete.
1389 //
1390 void DerivedType::notifyUsesThatTypeBecameConcrete() {
1391 #ifdef DEBUG_MERGE_TYPES
1392   DOUT << "typeIsREFINED type: " << (void*)this << " " << *this << "\n";
1393 #endif
1394
1395   unsigned OldSize = AbstractTypeUsers.size(); OldSize=OldSize;
1396   while (!AbstractTypeUsers.empty()) {
1397     AbstractTypeUser *ATU = AbstractTypeUsers.back();
1398     ATU->typeBecameConcrete(this);
1399
1400     assert(AbstractTypeUsers.size() < OldSize-- &&
1401            "AbstractTypeUser did not remove itself from the use list!");
1402   }
1403 }
1404
1405 // refineAbstractType - Called when a contained type is found to be more
1406 // concrete - this could potentially change us from an abstract type to a
1407 // concrete type.
1408 //
1409 void FunctionType::refineAbstractType(const DerivedType *OldType,
1410                                       const Type *NewType) {
1411   FunctionTypes->RefineAbstractType(this, OldType, NewType);
1412 }
1413
1414 void FunctionType::typeBecameConcrete(const DerivedType *AbsTy) {
1415   FunctionTypes->TypeBecameConcrete(this, AbsTy);
1416 }
1417
1418
1419 // refineAbstractType - Called when a contained type is found to be more
1420 // concrete - this could potentially change us from an abstract type to a
1421 // concrete type.
1422 //
1423 void ArrayType::refineAbstractType(const DerivedType *OldType,
1424                                    const Type *NewType) {
1425   ArrayTypes->RefineAbstractType(this, OldType, NewType);
1426 }
1427
1428 void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) {
1429   ArrayTypes->TypeBecameConcrete(this, AbsTy);
1430 }
1431
1432 // refineAbstractType - Called when a contained type is found to be more
1433 // concrete - this could potentially change us from an abstract type to a
1434 // concrete type.
1435 //
1436 void VectorType::refineAbstractType(const DerivedType *OldType,
1437                                    const Type *NewType) {
1438   VectorTypes->RefineAbstractType(this, OldType, NewType);
1439 }
1440
1441 void VectorType::typeBecameConcrete(const DerivedType *AbsTy) {
1442   VectorTypes->TypeBecameConcrete(this, AbsTy);
1443 }
1444
1445 // refineAbstractType - Called when a contained type is found to be more
1446 // concrete - this could potentially change us from an abstract type to a
1447 // concrete type.
1448 //
1449 void StructType::refineAbstractType(const DerivedType *OldType,
1450                                     const Type *NewType) {
1451   StructTypes->RefineAbstractType(this, OldType, NewType);
1452 }
1453
1454 void StructType::typeBecameConcrete(const DerivedType *AbsTy) {
1455   StructTypes->TypeBecameConcrete(this, AbsTy);
1456 }
1457
1458 // refineAbstractType - Called when a contained type is found to be more
1459 // concrete - this could potentially change us from an abstract type to a
1460 // concrete type.
1461 //
1462 void PointerType::refineAbstractType(const DerivedType *OldType,
1463                                      const Type *NewType) {
1464   PointerTypes->RefineAbstractType(this, OldType, NewType);
1465 }
1466
1467 void PointerType::typeBecameConcrete(const DerivedType *AbsTy) {
1468   PointerTypes->TypeBecameConcrete(this, AbsTy);
1469 }
1470
1471 bool SequentialType::indexValid(const Value *V) const {
1472   if (isa<IntegerType>(V->getType()))
1473     return true;
1474   return false;
1475 }
1476
1477 namespace llvm {
1478 std::ostream &operator<<(std::ostream &OS, const Type *T) {
1479   if (T == 0)
1480     OS << "<null> value!\n";
1481   else
1482     T->print(OS);
1483   return OS;
1484 }
1485
1486 std::ostream &operator<<(std::ostream &OS, const Type &T) {
1487   T.print(OS);
1488   return OS;
1489 }
1490
1491 raw_ostream &operator<<(raw_ostream &OS, const Type &T) {
1492   T.print(OS);
1493   return OS;
1494 }
1495 }