lib/VMCore/Type.cpp

   1 //===-- Type.cpp - Implement the Type class ----------------------*- C++ -*--=//
   2 //
   3 // This file implements the Type class for the VMCore library.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/DerivedTypes.h"
   8 #include "llvm/Support/StringExtras.h"
   9 #include "llvm/SymbolTable.h"
  10 #include "llvm/Support/STLExtras.h"
  11
  12 // DEBUG_MERGE_TYPES - Enable this #define to see how and when derived types are
  13 // created and later destroyed, all in an effort to make sure that there is only
  14 // a single cannonical version of a type.
  15 //
  16 //#define DEBUG_MERGE_TYPES 1
  17
  18
  19
  20 //===----------------------------------------------------------------------===//
  21 //                         Type Class Implementation
  22 //===----------------------------------------------------------------------===//
  23
  24 static unsigned CurUID = 0;
  25 static vector<const Type *> UIDMappings;
  26
  27 Type::Type(const string &name, PrimitiveID id)
  28   : Value(Type::TypeTy, Value::TypeVal) {
  29   setDescription(name);
  30   ID = id;
  31   Abstract = false;
  32   ConstRulesImpl = 0;
  33   UID = CurUID++;       // Assign types UID's as they are created
  34   UIDMappings.push_back(this);
  35 }
  36
  37 void Type::setName(const string &Name, SymbolTable *ST) {
  38   assert(ST && "Type::setName - Must provide symbol table argument!");
  39
  40   if (Name.size()) ST->insert(Name, this);
  41 }
  42
  43
  44 const Type *Type::getUniqueIDType(unsigned UID) {
  45   assert(UID < UIDMappings.size() &&
  46          "Type::getPrimitiveType: UID out of range!");
  47   return UIDMappings[UID];
  48 }
  49
  50 const Type *Type::getPrimitiveType(PrimitiveID IDNumber) {
  51   switch (IDNumber) {
  52   case VoidTyID  : return VoidTy;
  53   case BoolTyID  : return BoolTy;
  54   case UByteTyID : return UByteTy;
  55   case SByteTyID : return SByteTy;
  56   case UShortTyID: return UShortTy;
  57   case ShortTyID : return ShortTy;
  58   case UIntTyID  : return UIntTy;
  59   case IntTyID   : return IntTy;
  60   case ULongTyID : return ULongTy;
  61   case LongTyID  : return LongTy;
  62   case FloatTyID : return FloatTy;
  63   case DoubleTyID: return DoubleTy;
  64   case TypeTyID  : return TypeTy;
  65   case LabelTyID : return LabelTy;
  66   default:
  67     return 0;
  68   }
  69 }
  70
  71 //===----------------------------------------------------------------------===//
  72 //                           Auxilliary classes
  73 //===----------------------------------------------------------------------===//
  74 //
  75 // These classes are used to implement specialized behavior for each different
  76 // type.
  77 //
  78 class SignedIntType : public Type {
  79   int Size;
  80 public:
  81   SignedIntType(const string &Name, PrimitiveID id, int size) : Type(Name, id) {
  82     Size = size;
  83   }
  84
  85   // isSigned - Return whether a numeric type is signed.
  86   virtual bool isSigned() const { return 1; }
  87
  88   // isIntegral - Equivalent to isSigned() || isUnsigned, but with only a single
  89   // virtual function invocation.
  90   //
  91   virtual bool isIntegral() const { return 1; }
  92 };
  93
  94 class UnsignedIntType : public Type {
  95   uint64_t Size;
  96 public:
  97   UnsignedIntType(const string &N, PrimitiveID id, int size) : Type(N, id) {
  98     Size = size;
  99   }
 100
 101   // isUnsigned - Return whether a numeric type is signed.
 102   virtual bool isUnsigned() const { return 1; }
 103
 104   // isIntegral - Equivalent to isSigned() || isUnsigned, but with only a single
 105   // virtual function invocation.
 106   //
 107   virtual bool isIntegral() const { return 1; }
 108 };
 109
 110 static struct TypeType : public Type {
 111   TypeType() : Type("type", TypeTyID) {}
 112 } TheTypeType;   // Implement the type that is global.
 113
 114
 115 //===----------------------------------------------------------------------===//
 116 //                           Static 'Type' data
 117 //===----------------------------------------------------------------------===//
 118
 119 const Type *Type::VoidTy   = new            Type("void"  , VoidTyID),
 120            *Type::BoolTy   = new            Type("bool"  , BoolTyID),
 121            *Type::SByteTy  = new   SignedIntType("sbyte" , SByteTyID, 1),
 122            *Type::UByteTy  = new UnsignedIntType("ubyte" , UByteTyID, 1),
 123            *Type::ShortTy  = new   SignedIntType("short" ,  ShortTyID, 2),
 124            *Type::UShortTy = new UnsignedIntType("ushort", UShortTyID, 2),
 125            *Type::IntTy    = new   SignedIntType("int"   ,  IntTyID, 4),
 126            *Type::UIntTy   = new UnsignedIntType("uint"  , UIntTyID, 4),
 127            *Type::LongTy   = new   SignedIntType("long"  ,  LongTyID, 8),
 128            *Type::ULongTy  = new UnsignedIntType("ulong" , ULongTyID, 8),
 129            *Type::FloatTy  = new            Type("float" , FloatTyID),
 130            *Type::DoubleTy = new            Type("double", DoubleTyID),
 131            *Type::TypeTy   =        &TheTypeType,
 132            *Type::LabelTy  = new            Type("label" , LabelTyID);
 133
 134
 135 //===----------------------------------------------------------------------===//
 136 //                          Derived Type Constructors
 137 //===----------------------------------------------------------------------===//
 138
 139 MethodType::MethodType(const Type *Result, const vector<const Type*> &Params,
 140                        bool IsVarArgs) : DerivedType("", MethodTyID),
 141     ResultType(PATypeHandle<Type>(Result, this)),
 142     isVarArgs(IsVarArgs) {
 143   ParamTys.reserve(Params.size());
 144   for (unsigned i = 0; i < Params.size()-IsVarArgs; ++i)
 145     ParamTys.push_back(PATypeHandle<Type>(Params[i], this));
 146
 147   setDerivedTypeProperties();
 148 }
 149
 150 ArrayType::ArrayType(const Type *ElType, int NumEl)
 151   : DerivedType("", ArrayTyID), ElementType(PATypeHandle<Type>(ElType, this)) {
 152   NumElements = NumEl;
 153   setDerivedTypeProperties();
 154 }
 155
 156 StructType::StructType(const vector<const Type*> &Types)
 157   : DerivedType("", StructTyID) {
 158   ETypes.reserve(Types.size());
 159   for (unsigned i = 0; i < Types.size(); ++i)
 160     ETypes.push_back(PATypeHandle<Type>(Types[i], this));
 161   setDerivedTypeProperties();
 162 }
 163
 164 PointerType::PointerType(const Type *E) : DerivedType("", PointerTyID),
 165                           ValueType(PATypeHandle<Type>(E, this)) {
 166   setDerivedTypeProperties();
 167 }
 168
 169 OpaqueType::OpaqueType() : DerivedType("", OpaqueTyID) {
 170   setAbstract(true);
 171   setDescription("opaque"+utostr(getUniqueID()));
 172 #ifdef DEBUG_MERGE_TYPES
 173   cerr << "Derived new type: " << getDescription() << endl;
 174 #endif
 175 }
 176
 177
 178
 179
 180 //===----------------------------------------------------------------------===//
 181 //               Derived Type setDerivedTypeProperties Function
 182 //===----------------------------------------------------------------------===//
 183
 184 // getTypeProps - This is a recursive function that walks a type hierarchy
 185 // calculating the description for a type and whether or not it is abstract or
 186 // recursive.  Worst case it will have to do a lot of traversing if you have
 187 // some whacko opaque types, but in most cases, it will do some simple stuff
 188 // when it hits non-abstract types that aren't recursive.
 189 //
 190 static string getTypeProps(const Type *Ty, vector<const Type *> &TypeStack,
 191                            bool &isAbstract, bool &isRecursive) {
 192   string Result;
 193   if (!Ty->isAbstract() && !Ty->isRecursive() && // Base case for the recursion
 194       Ty->getDescription().size()) {
 195     Result = Ty->getDescription();               // Primitive = leaf type
 196   } else if (Ty->isOpaqueType()) {               // Base case for the recursion
 197     Result = Ty->getDescription();               // Opaque = leaf type
 198     isAbstract = true;                           // This whole type is abstract!
 199   } else {
 200     // Check to see if the Type is already on the stack...
 201     unsigned Slot = 0, CurSize = TypeStack.size();
 202     while (Slot < CurSize && TypeStack[Slot] != Ty) ++Slot; // Scan for type
 203
 204     // This is another base case for the recursion.  In this case, we know
 205     // that we have looped back to a type that we have previously visited.
 206     // Generate the appropriate upreference to handle this.
 207     //
 208     if (Slot < CurSize) {
 209       Result = "\\" + utostr(CurSize-Slot);       // Here's the upreference
 210       isRecursive = true;                         // We know we are recursive
 211     } else {                      // Recursive case: abstract derived type...
 212       TypeStack.push_back(Ty);    // Add us to the stack..
 213
 214       switch (Ty->getPrimitiveID()) {
 215       case Type::MethodTyID: {
 216         const MethodType *MTy = (const MethodType*)Ty;
 217         Result = getTypeProps(MTy->getReturnType(), TypeStack,
 218                               isAbstract, isRecursive)+" (";
 219         for (MethodType::ParamTypes::const_iterator
 220                I = MTy->getParamTypes().begin(),
 221                E = MTy->getParamTypes().end(); I != E; ++I) {
 222           if (I != MTy->getParamTypes().begin())
 223             Result += ", ";
 224           Result += getTypeProps(*I, TypeStack, isAbstract, isRecursive);
 225         }
 226         if (MTy->isVarArg()) {
 227           if (!MTy->getParamTypes().empty()) Result += ", ";
 228           Result += "...";
 229         }
 230         Result += ")";
 231         break;
 232       }
 233       case Type::StructTyID: {
 234         const StructType *STy = (const StructType*)Ty;
 235         Result = "{ ";
 236         for (StructType::ElementTypes::const_iterator
 237                I = STy->getElementTypes().begin(),
 238                E = STy->getElementTypes().end(); I != E; ++I) {
 239           if (I != STy->getElementTypes().begin())
 240             Result += ", ";
 241           Result += getTypeProps(*I, TypeStack, isAbstract, isRecursive);
 242         }
 243         Result += " }";
 244         break;
 245       }
 246       case Type::PointerTyID: {
 247         const PointerType *PTy = (const PointerType*)Ty;
 248         Result = getTypeProps(PTy->getValueType(), TypeStack,
 249                               isAbstract, isRecursive) + " *";
 250         break;
 251       }
 252       case Type::ArrayTyID: {
 253         const ArrayType *ATy = (const ArrayType*)Ty;
 254         int NumElements = ATy->getNumElements();
 255         Result = "[";
 256         if (NumElements != -1) Result += itostr(NumElements) + " x ";
 257         Result += getTypeProps(ATy->getElementType(), TypeStack,
 258                                isAbstract, isRecursive) + "]";
 259         break;
 260       }
 261       default:
 262         assert(0 && "Unhandled case in getTypeProps!");
 263         Result = "<error>";
 264       }
 265
 266       TypeStack.pop_back();       // Remove self from stack...
 267     }
 268   }
 269   return Result;
 270 }
 271
 272
 273 // setDerivedTypeProperties - This function is used to calculate the
 274 // isAbstract, isRecursive, and the Description settings for a type.  The
 275 // getTypeProps function does all the dirty work.
 276 //
 277 void DerivedType::setDerivedTypeProperties() {
 278   vector<const Type *> TypeStack;
 279   bool isAbstract = false, isRecursive = false;
 280
 281   setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive));
 282   setAbstract(isAbstract);
 283   setRecursive(isRecursive);
 284 }
 285
 286
 287 //===----------------------------------------------------------------------===//
 288 //                      Type Structural Equality Testing
 289 //===----------------------------------------------------------------------===//
 290
 291 // TypesEqual - Two types are considered structurally equal if they have the
 292 // same "shape": Every level and element of the types have identical primitive
 293 // ID's, and the graphs have the same edges/nodes in them.  Nodes do not have to
 294 // be pointer equals to be equivalent though.  This uses an optimistic algorithm
 295 // that assumes that two graphs are the same until proven otherwise.
 296 //
 297 static bool TypesEqual(const Type *Ty, const Type *Ty2,
 298                        map<const Type *, const Type *> &EqTypes) {
 299   if (Ty == Ty2) return true;
 300   if (Ty->getPrimitiveID() != Ty2->getPrimitiveID()) return false;
 301   if (Ty->isPrimitiveType()) return true;
 302
 303   if (Ty != Ty2) {
 304     map<const Type*, const Type*>::iterator I = EqTypes.find(Ty);
 305     if (I != EqTypes.end())
 306       return I->second == Ty2;    // Looping back on a type, check for equality
 307
 308     // Otherwise, add the mapping to the table to make sure we don't get
 309     // recursion on the types...
 310     EqTypes.insert(make_pair(Ty, Ty2));
 311   }
 312
 313   // Iterate over the types and make sure the the contents are equivalent...
 314   Type::contype_iterator I  = Ty ->contype_begin(), IE  = Ty ->contype_end();
 315   Type::contype_iterator I2 = Ty2->contype_begin(), IE2 = Ty2->contype_end();
 316   for (; I != IE && I2 != IE2; ++I, ++I2)
 317     if (!TypesEqual(*I, *I2, EqTypes)) return false;
 318
 319   // One really annoying special case that breaks an otherwise nice simple
 320   // algorithm is the fact that arraytypes have sizes that differentiates types,
 321   // consider this now.
 322   if (Ty->isArrayType())
 323     if (((const ArrayType*)Ty)->getNumElements() !=
 324         ((const ArrayType*)Ty2)->getNumElements()) return false;
 325
 326   return I == IE && I2 == IE2;    // Types equal if both iterators are done
 327 }
 328
 329 static bool TypesEqual(const Type *Ty, const Type *Ty2) {
 330   map<const Type *, const Type *> EqTypes;
 331   return TypesEqual(Ty, Ty2, EqTypes);
 332 }
 333
 334
 335
 336 //===----------------------------------------------------------------------===//
 337 //                       Derived Type Factory Functions
 338 //===----------------------------------------------------------------------===//
 339
 340 // TypeMap - Make sure that only one instance of a particular type may be
 341 // created on any given run of the compiler... note that this involves updating
 342 // our map if an abstract type gets refined somehow...
 343 //
 344 template<class ValType, class TypeClass>
 345 class TypeMap : public AbstractTypeUser {
 346   typedef map<ValType, PATypeHandle<TypeClass> > MapTy;
 347   MapTy Map;
 348 public:
 349
 350   ~TypeMap() { print("ON EXIT"); }
 351
 352   inline TypeClass *get(const ValType &V) {
 353     map<ValType, PATypeHandle<TypeClass> >::iterator I = Map.find(V);
 354     // TODO: FIXME: When Types are not CONST.
 355     return (I != Map.end()) ? (TypeClass*)I->second.get() : 0;
 356   }
 357
 358   inline void add(const ValType &V, TypeClass *T) {
 359     Map.insert(make_pair(V, PATypeHandle<TypeClass>(T, this)));
 360     print("add");
 361   }
 362
 363   // containsEquivalent - Return true if the typemap contains a type that is
 364   // structurally equivalent to the specified type.
 365   //
 366   inline const TypeClass *containsEquivalent(const TypeClass *Ty) {
 367     for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
 368       if (I->second.get() != Ty && TypesEqual(Ty, I->second.get()))
 369         return (TypeClass*)I->second.get();  // FIXME TODO when types not const
 370     return 0;
 371   }
 372
 373   // refineAbstractType - This is called when one of the contained abstract
 374   // types gets refined... this simply removes the abstract type from our table.
 375   // We expect that whoever refined the type will add it back to the table,
 376   // corrected.
 377   //
 378   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 379     if (OldTy == NewTy) return;
 380 #ifdef DEBUG_MERGE_TYPES
 381     cerr << "Removing Old type from Tab: " << (void*)OldTy << ", "
 382          << OldTy->getDescription() << "  replacement == " << (void*)NewTy
 383          << ", " << NewTy->getDescription() << endl;
 384 #endif
 385     for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
 386       if (I->second == OldTy) {
 387         Map.erase(I);
 388         print("refineAbstractType after");
 389         return;
 390       }
 391     assert(0 && "Abstract type not found in table!");
 392   }
 393
 394   void remove(const ValType &OldVal) {
 395     MapTy::iterator I = Map.find(OldVal);
 396     assert(I != Map.end() && "TypeMap::remove, element not found!");
 397     Map.erase(I);
 398   }
 399
 400   void print(const char *Arg) {
 401 #ifdef DEBUG_MERGE_TYPES
 402     cerr << "TypeMap<>::" << Arg << " table contents:\n";
 403     unsigned i = 0;
 404     for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I)
 405       cerr << " " << (++i) << ". " << I->second << " "
 406            << I->second->getDescription() << endl;
 407 #endif
 408   }
 409 };
 410
 411
 412 // ValTypeBase - This is the base class that is used by the various
 413 // instantiations of TypeMap.  This class is an AbstractType user that notifies
 414 // the underlying TypeMap when it gets modified.
 415 //
 416 template<class ValType, class TypeClass>
 417 class ValTypeBase : public AbstractTypeUser {
 418   TypeMap<ValType, TypeClass> &MyTable;
 419 protected:
 420   inline ValTypeBase(TypeMap<ValType, TypeClass> &tab) : MyTable(tab) {}
 421
 422   // Subclass should override this... to update self as usual
 423   virtual void doRefinement(const DerivedType *OldTy, const Type *NewTy) = 0;
 424
 425   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
 426     if (OldTy == NewTy) return;
 427     TypeMap<ValType, TypeClass> &Table = MyTable;     // Copy MyTable reference
 428     ValType Tmp(*(ValType*)this);                     // Copy this.
 429     PATypeHandle<TypeClass> OldType(Table.get(*(ValType*)this), this);
 430     Table.remove(*(ValType*)this);                    // Destroy's this!
 431
 432     // Refine temporary to new state...
 433     Tmp.doRefinement(OldTy, NewTy);
 434
 435     Table.add((ValType&)Tmp, (TypeClass*)OldType.get());
 436   }
 437 };
 438
 439
 440
 441 //===----------------------------------------------------------------------===//
 442 // Method Type Factory and Value Class...
 443 //
 444
 445 // MethodValType - Define a class to hold the key that goes into the TypeMap
 446 //
 447 class MethodValType : public ValTypeBase<MethodValType, MethodType> {
 448   PATypeHandle<Type> RetTy;
 449   vector<PATypeHandle<Type> > ArgTypes;
 450 public:
 451   MethodValType(const Type *ret, const vector<const Type*> &args,
 452                 TypeMap<MethodValType, MethodType> &Tab)
 453     : ValTypeBase<MethodValType, MethodType>(Tab), RetTy(ret, this) {
 454     for (unsigned i = 0; i < args.size(); ++i)
 455       ArgTypes.push_back(PATypeHandle<Type>(args[i], this));
 456   }
 457
 458   // We *MUST* have an explicit copy ctor so that the TypeHandles think that
 459   // this MethodValType owns them, not the old one!
 460   //
 461   MethodValType(const MethodValType &MVT)
 462     : ValTypeBase<MethodValType, MethodType>(MVT), RetTy(MVT.RetTy, this) {
 463     ArgTypes.reserve(MVT.ArgTypes.size());
 464     for (unsigned i = 0; i < MVT.ArgTypes.size(); ++i)
 465       ArgTypes.push_back(PATypeHandle<Type>(MVT.ArgTypes[i], this));
 466   }
 467
 468   // Subclass should override this... to update self as usual
 469   virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
 470     if (RetTy == OldType) RetTy = NewType;
 471     for (unsigned i = 0; i < ArgTypes.size(); ++i)
 472       if (ArgTypes[i] == OldType) ArgTypes[i] = NewType;
 473   }
 474
 475   inline bool operator<(const MethodValType &MTV) const {
 476     return RetTy.get() <  MTV.RetTy.get() ||
 477           (RetTy.get() == MTV.RetTy.get() && ArgTypes < MTV.ArgTypes);
 478   }
 479 };
 480
 481 // Define the actual map itself now...
 482 static TypeMap<MethodValType, MethodType> MethodTypes;
 483
 484 // MethodType::get - The factory function for the MethodType class...
 485 MethodType *MethodType::get(const Type *ReturnType,
 486                             const vector<const Type*> &Params) {
 487   MethodValType VT(ReturnType, Params, MethodTypes);
 488   MethodType *MT = MethodTypes.get(VT);
 489   if (MT) return MT;
 490
 491   bool IsVarArg = Params.size() && (Params[Params.size()-1] == Type::VoidTy);
 492   MethodTypes.add(VT, MT = new MethodType(ReturnType, Params, IsVarArg));
 493
 494 #ifdef DEBUG_MERGE_TYPES
 495   cerr << "Derived new type: " << MT << endl;
 496 #endif
 497   return MT;
 498 }
 499
 500 //===----------------------------------------------------------------------===//
 501 // Array Type Factory...
 502 //
 503 class ArrayValType : public ValTypeBase<ArrayValType, ArrayType> {
 504   PATypeHandle<Type> ValTy;
 505   int Size;
 506 public:
 507   ArrayValType(const Type *val, int sz, TypeMap<ArrayValType, ArrayType> &Tab)
 508     : ValTypeBase<ArrayValType, ArrayType>(Tab), ValTy(val, this), Size(sz) {}
 509
 510   // We *MUST* have an explicit copy ctor so that the ValTy thinks that this
 511   // ArrayValType owns it, not the old one!
 512   //
 513   ArrayValType(const ArrayValType &AVT)
 514     : ValTypeBase<ArrayValType, ArrayType>(AVT), ValTy(AVT.ValTy, this),
 515       Size(AVT.Size) {}
 516
 517   // Subclass should override this... to update self as usual
 518   virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
 519     if (ValTy == OldType) ValTy = NewType;
 520   }
 521
 522   inline bool operator<(const ArrayValType &MTV) const {
 523     if (Size < MTV.Size) return true;
 524     return Size == MTV.Size && ValTy.get() < MTV.ValTy.get();
 525   }
 526 };
 527
 528 static TypeMap<ArrayValType, ArrayType> ArrayTypes;
 529
 530 ArrayType *ArrayType::get(const Type *ElementType, int NumElements = -1) {
 531   assert(ElementType && "Can't get array of null types!");
 532
 533   ArrayValType AVT(ElementType, NumElements, ArrayTypes);
 534   ArrayType *AT = ArrayTypes.get(AVT);
 535   if (AT) return AT;           // Found a match, return it!
 536
 537   // Value not found.  Derive a new type!
 538   ArrayTypes.add(AVT, AT = new ArrayType(ElementType, NumElements));
 539
 540 #ifdef DEBUG_MERGE_TYPES
 541   cerr << "Derived new type: " << AT->getDescription() << endl;
 542 #endif
 543   return AT;
 544 }
 545
 546 //===----------------------------------------------------------------------===//
 547 // Struct Type Factory...
 548 //
 549
 550 // StructValType - Define a class to hold the key that goes into the TypeMap
 551 //
 552 class StructValType : public ValTypeBase<StructValType, StructType> {
 553   vector<PATypeHandle<Type> > ElTypes;
 554 public:
 555   StructValType(const vector<const Type*> &args,
 556                 TypeMap<StructValType, StructType> &Tab)
 557     : ValTypeBase<StructValType, StructType>(Tab) {
 558     for (unsigned i = 0; i < args.size(); ++i)
 559       ElTypes.push_back(PATypeHandle<Type>(args[i], this));
 560   }
 561
 562   // We *MUST* have an explicit copy ctor so that the TypeHandles think that
 563   // this StructValType owns them, not the old one!
 564   //
 565   StructValType(const StructValType &SVT)
 566     : ValTypeBase<StructValType, StructType>(SVT){
 567     ElTypes.reserve(SVT.ElTypes.size());
 568     for (unsigned i = 0; i < SVT.ElTypes.size(); ++i)
 569       ElTypes.push_back(PATypeHandle<Type>(SVT.ElTypes[i], this));
 570   }
 571
 572   // Subclass should override this... to update self as usual
 573   virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
 574     for (unsigned i = 0; i < ElTypes.size(); ++i)
 575       if (ElTypes[i] == OldType) ElTypes[i] = NewType;
 576   }
 577
 578   inline bool operator<(const StructValType &STV) const {
 579     return ElTypes < STV.ElTypes;
 580   }
 581 };
 582
 583 static TypeMap<StructValType, StructType> StructTypes;
 584
 585 StructType *StructType::get(const vector<const Type*> &ETypes) {
 586   StructValType STV(ETypes, StructTypes);
 587   StructType *ST = StructTypes.get(STV);
 588   if (ST) return ST;
 589
 590   // Value not found.  Derive a new type!
 591   StructTypes.add(STV, ST = new StructType(ETypes));
 592
 593 #ifdef DEBUG_MERGE_TYPES
 594   cerr << "Derived new type: " << ST->getDescription() << endl;
 595 #endif
 596   return ST;
 597 }
 598
 599 //===----------------------------------------------------------------------===//
 600 // Pointer Type Factory...
 601 //
 602
 603 // PointerValType - Define a class to hold the key that goes into the TypeMap
 604 //
 605 class PointerValType : public ValTypeBase<PointerValType, PointerType> {
 606   PATypeHandle<Type> ValTy;
 607 public:
 608   PointerValType(const Type *val, TypeMap<PointerValType, PointerType> &Tab)
 609     : ValTypeBase<PointerValType, PointerType>(Tab), ValTy(val, this) {}
 610
 611   // We *MUST* have an explicit copy ctor so that the ValTy thinks that this
 612   // PointerValType owns it, not the old one!
 613   //
 614   PointerValType(const PointerValType &PVT)
 615     : ValTypeBase<PointerValType, PointerType>(PVT), ValTy(PVT.ValTy, this) {}
 616
 617   // Subclass should override this... to update self as usual
 618   virtual void doRefinement(const DerivedType *OldType, const Type *NewType) {
 619     if (ValTy == OldType) ValTy = NewType;
 620   }
 621
 622   inline bool operator<(const PointerValType &MTV) const {
 623     return ValTy.get() < MTV.ValTy.get();
 624   }
 625 };
 626
 627 static TypeMap<PointerValType, PointerType> PointerTypes;
 628
 629 PointerType *PointerType::get(const Type *ValueType) {
 630   assert(ValueType && "Can't get a pointer to <null> type!");
 631   PointerValType PVT(ValueType, PointerTypes);
 632
 633   PointerType *PT = PointerTypes.get(PVT);
 634   if (PT) return PT;
 635
 636   // Value not found.  Derive a new type!
 637   PointerTypes.add(PVT, PT = new PointerType(ValueType));
 638
 639 #ifdef DEBUG_MERGE_TYPES
 640   cerr << "Derived new type: " << PT->getDescription() << endl;
 641 #endif
 642   return PT;
 643 }
 644
 645
 646
 647 //===----------------------------------------------------------------------===//
 648 //                     Derived Type Refinement Functions
 649 //===----------------------------------------------------------------------===//
 650
 651 // removeAbstractTypeUser - Notify an abstract type that a user of the class
 652 // no longer has a handle to the type.  This function is called primarily by
 653 // the PATypeHandle class.  When there are no users of the abstract type, it
 654 // is anihilated, because there is no way to get a reference to it ever again.
 655 //
 656 void DerivedType::removeAbstractTypeUser(AbstractTypeUser *U) const {
 657   // Search from back to front because we will notify users from back to
 658   // front.  Also, it is likely that there will be a stack like behavior to
 659   // users that register and unregister users.
 660   //
 661   for (unsigned i = AbstractTypeUsers.size(); i > 0; --i) {
 662     if (AbstractTypeUsers[i-1] == U) {
 663       AbstractTypeUsers.erase(AbstractTypeUsers.begin()+i-1);
 664
 665 #ifdef DEBUG_MERGE_TYPES
 666       cerr << "  removeAbstractTypeUser[" << (void*)this << ", "
 667            << getDescription() << "][" << AbstractTypeUsers.size()
 668            << "] User = " << U << endl;
 669 #endif
 670
 671       if (AbstractTypeUsers.empty()) {
 672 #ifdef DEBUG_MERGE_TYPES
 673         cerr << "DELETEing unused abstract type: " << getDescription()
 674              << " " << (void*)this << endl;
 675 #endif
 676         delete this;                  // No users of this abstract type!
 677       }
 678       return;
 679     }
 680   }
 681   assert(isAbstract() && "removeAbstractTypeUser: Type not abstract!");
 682   assert(0 && "AbstractTypeUser not in user list!");
 683 }
 684
 685
 686 // refineAbstractTypeTo - This function is used to when it is discovered that
 687 // the 'this' abstract type is actually equivalent to the NewType specified.
 688 // This causes all users of 'this' to switch to reference the more concrete
 689 // type NewType and for 'this' to be deleted.
 690 //
 691 void DerivedType::refineAbstractTypeTo(const Type *NewType) {
 692   assert(isAbstract() && "refineAbstractTypeTo: Current type is not abstract!");
 693   assert(this != NewType && "Can't refine to myself!");
 694
 695 #ifdef DEBUG_MERGE_TYPES
 696   cerr << "REFINING abstract type [" << (void*)this << " " << getDescription()
 697        << "] to [" << (void*)NewType << " " << NewType->getDescription()
 698        << "]!\n";
 699 #endif
 700
 701
 702   // Make sure to put the type to be refined to into a holder so that if IT gets
 703   // refined, that we will not continue using a dead reference...
 704   //
 705   PATypeHolder<Type> NewTy(NewType);
 706
 707   // Add a self use of the current type so that we don't delete ourself until
 708   // after this while loop.  We are careful to never invoke refine on ourself,
 709   // so this extra reference shouldn't be a problem.  Note that we must only
 710   // remove a single reference at the end, but we must tolerate multiple self
 711   // references because we could be refineAbstractTypeTo'ing recursively on the
 712   // same type.
 713   //
 714   addAbstractTypeUser(this);
 715
 716   // Count the number of self uses.  Stop looping when sizeof(list) == NSU.
 717   unsigned NumSelfUses = 0;
 718
 719   // Iterate over all of the uses of this type, invoking callback.  Each user
 720   // should remove itself from our use list automatically.
 721   //
 722   while (AbstractTypeUsers.size() > NumSelfUses) {
 723     AbstractTypeUser *User = AbstractTypeUsers.back();
 724
 725     if (User == this) {
 726       // Move self use to the start of the list.  Increment NSU.
 727       swap(AbstractTypeUsers.back(), AbstractTypeUsers[NumSelfUses++]);
 728     } else {
 729       unsigned OldSize = AbstractTypeUsers.size();
 730 #ifdef DEBUG_MERGE_TYPES
 731       cerr << " REFINING user " << OldSize-1 << " of abstract type ["
 732            << (void*)this << " " << getDescription() << "] to ["
 733            << (void*)NewTy.get() << " " << NewTy->getDescription() << "]!\n";
 734 #endif
 735       AbstractTypeUsers.back()->refineAbstractType(this, NewTy);
 736
 737       assert(AbstractTypeUsers.size() != OldSize &&
 738              "AbsTyUser did not remove self from user list!");
 739     }
 740   }
 741
 742   // Remove a single self use, even though there may be several here. This will
 743   // probably 'delete this', so no instance variables may be used after this
 744   // occurs...
 745   assert(AbstractTypeUsers.back() == this && "Only self uses should be left!");
 746   removeAbstractTypeUser(this);
 747 }
 748
 749
 750 // typeIsRefined - Notify AbstractTypeUsers of this type that the current type
 751 // has been refined a bit.  The pointer is still valid and still should be
 752 // used, but the subtypes have changed.
 753 //
 754 void DerivedType::typeIsRefined() {
 755   assert(isRefining >= 0 && isRefining <= 2 && "isRefining out of bounds!");
 756   if (isRefining == 2) return;  // Kill recursion here...
 757   ++isRefining;
 758
 759 #ifdef DEBUG_MERGE_TYPES
 760   cerr << "typeIsREFINED type: " << (void*)this <<" "<<getDescription() << endl;
 761 #endif
 762   for (unsigned i = 0; i < AbstractTypeUsers.size(); ) {
 763     AbstractTypeUser *ATU = AbstractTypeUsers[i];
 764 #ifdef DEBUG_MERGE_TYPES
 765     cerr << " typeIsREFINED user " << i << " of abstract type ["
 766          << (void*)this << " " << getDescription() << "]\n";
 767 #endif
 768     ATU->refineAbstractType(this, this);
 769
 770     // If the user didn't remove itself from the list, continue...
 771     if (AbstractTypeUsers.size() > i && AbstractTypeUsers[i] == ATU)
 772       ++i;
 773   }
 774
 775   --isRefining;
 776 }
 777
 778
 779
 780
 781 // refineAbstractType - Called when a contained type is found to be more
 782 // concrete - this could potentially change us from an abstract type to a
 783 // concrete type.
 784 //
 785 void MethodType::refineAbstractType(const DerivedType *OldType,
 786                                     const Type *NewType) {
 787 #ifdef DEBUG_MERGE_TYPES
 788   cerr << "MethodTy::refineAbstractTy(" << (void*)OldType << "["
 789        << OldType->getDescription() << "], " << (void*)NewType << " ["
 790        << NewType->getDescription() << "])\n";
 791 #endif
 792
 793   if (OldType == ResultType) {
 794     ResultType = NewType;
 795   } else {
 796     unsigned i;
 797     for (i = 0; i < ParamTys.size(); ++i)
 798       if (OldType == ParamTys[i]) {
 799         ParamTys[i] = NewType;
 800         break;
 801       }
 802     assert(i != ParamTys.size() && "Did not contain oldtype!");
 803   }
 804
 805
 806   // Notify everyone that I have changed!
 807   if (const MethodType *MTy = MethodTypes.containsEquivalent(this)) {
 808 #ifndef _NDEBUG
 809     // Calculate accurate name for debugging purposes
 810     vector<const Type *> TypeStack;
 811     bool isAbstract = false, isRecursive = false;
 812     setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive));
 813 #endif
 814
 815 #ifdef DEBUG_MERGE_TYPES
 816     cerr << "Type " << (void*)this << " equilivant to existing " << (void*)MTy
 817          << " - destroying!\n";
 818 #endif
 819     refineAbstractTypeTo(MTy);      // Different type altogether...
 820     return;
 821   }
 822   setDerivedTypeProperties();  // Update the name and isAbstract
 823   typeIsRefined();
 824 }
 825
 826
 827 // refineAbstractType - Called when a contained type is found to be more
 828 // concrete - this could potentially change us from an abstract type to a
 829 // concrete type.
 830 //
 831 void ArrayType::refineAbstractType(const DerivedType *OldType,
 832                                    const Type *NewType) {
 833 #ifdef DEBUG_MERGE_TYPES
 834   cerr << "ArrayTy::refineAbstractTy(" << (void*)OldType << "["
 835        << OldType->getDescription() << "], " << (void*)NewType << " ["
 836        << NewType->getDescription() << "])\n";
 837 #endif
 838   assert(OldType == ElementType && "Cannot refine from OldType!");
 839   ElementType = NewType;
 840
 841   // Notify everyone that I have changed!
 842   if (const ArrayType *ATy = ArrayTypes.containsEquivalent(this)) {
 843 #ifndef _NDEBUG
 844     // Calculate accurate name for debugging purposes
 845     vector<const Type *> TypeStack;
 846     bool isAbstract = false, isRecursive = false;
 847     setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive));
 848 #endif
 849
 850 #ifdef DEBUG_MERGE_TYPES
 851     cerr << "Type " << (void*)this << " equilivant to existing " << (void*)ATy
 852          << " - destroying!\n";
 853 #endif
 854     refineAbstractTypeTo(ATy);      // Different type altogether...
 855     return;
 856   }
 857   setDerivedTypeProperties();   // Update the name and isAbstract
 858   typeIsRefined();              // Same type, different contents...
 859 }
 860
 861
 862 // refineAbstractType - Called when a contained type is found to be more
 863 // concrete - this could potentially change us from an abstract type to a
 864 // concrete type.
 865 //
 866 void StructType::refineAbstractType(const DerivedType *OldType,
 867                                     const Type *NewType) {
 868 #ifdef DEBUG_MERGE_TYPES
 869   cerr << "StructTy::refineAbstractTy(" << (void*)OldType << "["
 870        << OldType->getDescription() << "], " << (void*)NewType << " ["
 871        << NewType->getDescription() << "])\n";
 872 #endif
 873
 874   if (OldType != NewType) {
 875     unsigned i;
 876     for (i = 0; i < ETypes.size(); ++i)
 877       if (OldType == ETypes[i]) {
 878         ETypes[i] = NewType;
 879         break;
 880       }
 881     assert(i != ETypes.size() && "Did not contain oldtype!");
 882   }
 883
 884   vector<const Type *> ElTypes(
 885       map_iterator(ETypes.begin(), mem_fun_ref(&PATypeHandle<Type>::get)),
 886       map_iterator(ETypes.end()  , mem_fun_ref(&PATypeHandle<Type>::get)));
 887
 888
 889   // Notify everyone that I have changed!
 890   if (const StructType *STy = StructTypes.containsEquivalent(this)) {
 891 #ifndef _NDEBUG
 892     // Calculate accurate name for debugging purposes
 893     vector<const Type *> TypeStack;
 894     bool isAbstract = false, isRecursive = false;
 895     setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive));
 896 #endif
 897
 898 #ifdef DEBUG_MERGE_TYPES
 899     cerr << "Type " << (void*)this << " equilivant to existing " << (void*)STy
 900          << " - destroying!\n";
 901 #endif
 902     refineAbstractTypeTo(STy);      // Different type altogether...
 903     return;
 904   }
 905   setDerivedTypeProperties();          // Update the name and isAbstract
 906   typeIsRefined();                   // Same type, different contents...
 907 }
 908
 909 // refineAbstractType - Called when a contained type is found to be more
 910 // concrete - this could potentially change us from an abstract type to a
 911 // concrete type.
 912 //
 913 void PointerType::refineAbstractType(const DerivedType *OldType,
 914                                      const Type *NewType) {
 915 #ifdef DEBUG_MERGE_TYPES
 916   cerr << "PointerTy::refineAbstractTy(" << (void*)OldType << "["
 917        << OldType->getDescription() << "], " << (void*)NewType << " ["
 918        << NewType->getDescription() << "])\n";
 919 #endif
 920   assert(OldType == ValueType && "Cannot refine from OldType!");
 921   ValueType = NewType;
 922
 923   // Notify everyone that I have changed!
 924   if (const PointerType *PTy = PointerTypes.containsEquivalent(this)) {
 925 #ifndef _NDEBUG
 926     // Calculate accurate name for debugging purposes
 927     vector<const Type *> TypeStack;
 928     bool isAbstract = false, isRecursive = false;
 929     setDescription(getTypeProps(this, TypeStack, isAbstract, isRecursive));
 930 #endif
 931
 932 #ifdef DEBUG_MERGE_TYPES
 933     cerr << "Type " << (void*)this << " equilivant to existing " << (void*)PTy
 934          << " - destroying!\n";
 935 #endif
 936     refineAbstractTypeTo(PTy);      // Different type altogether...
 937     return;
 938   }
 939   setDerivedTypeProperties();  // Update the name and isAbstract
 940   typeIsRefined();                   // Same type, different contents...
 941 }
 942