lib/VMCore/Type.cpp

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