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