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